[ODE] HashSpace bug?
Patrick Enoch
Hendrix_ at gmx.net
Wed May 2 02:55:39 MST 2007
Hello ODE-list,
I have changed the following routine in order not to use up all
stackspace. It used to crash with 1200 objects, now it runs fine. (I
guess I could increase the thread's stacksize, too, and the old code
would run fine. - ODE is running in a seperate thread in my case.)
######################################################
#define ALLOCA_collide malloc
#define FREEA_collide free
static void free_linked_dxAABB_list( dxAABB* iter )
{
while (iter!=0)
{
dxAABB *nxt = iter->next;
FREEA_collide( iter );
iter = nxt;
}
}
static void free_linked_Node_list( Node* iter )
{
while (iter!=0)
{
Node *nxt = iter->next;
FREEA_collide( iter );
iter = nxt;
}
}
void dxHashSpace::collide (void *data, dNearCallback *callback)
{
dAASSERT(this && callback);
dxGeom *geom;
dxAABB *aabb;
int i,maxlevel;
// 0 or 1 geoms can't collide with anything
if (count < 2) return;
lock_count++;
cleanGeoms();
// create a list of auxiliary information for all geom axis
aligned bounding
// boxes. set the level for all AABBs. put AABBs larger than the
space's
// global_maxlevel in the big_boxes list, check everything else
against
// that list at the end. for AABBs that are not too big, record
the maximum
// level that we need.
int n = 0; // number of AABBs in main list
dxAABB *first_aabb = 0; // list of AABBs in hash table
dxAABB *big_boxes = 0; // list of AABBs too big for hash table
maxlevel = global_minlevel - 1;
for (geom = first; geom; geom=geom->next) {
if (!GEOM_ENABLED(geom)){
continue;
}
dxAABB *aabb = (dxAABB*) ALLOCA_collide (sizeof(dxAABB));
aabb->geom = geom;
// compute level, but prevent cells from getting too small
int level = findLevel (geom->aabb);
if (level < global_minlevel) level = global_minlevel;
if (level <= global_maxlevel) {
// aabb goes in main list
aabb->next = first_aabb;
first_aabb = aabb;
aabb->level = level;
if (level > maxlevel) maxlevel = level;
// cellsize = 2^level
dReal cellsize = (dReal) ldexp (1.0,level);
// discretize AABB position to cell size
for (i=0; i < 6; i++) aabb->dbounds[i] = (int)
floor (geom->aabb[i]/cellsize);
// set AABB index
aabb->index = n;
n++;
}
else {
// aabb is too big, put it in the big_boxes list. we don't
care about
// setting level, dbounds, index, or the maxlevel
aabb->next = big_boxes;
big_boxes = aabb;
}
}
// for `n' objects, an n*n array of bits is used to record if
those objects
// have been intersection-tested against each other yet. this
array can
// grow large with high n, but oh well...
int tested_rowsize = (n+7) >> 3; // number of bytes needed for n bits
unsigned char *tested = (unsigned char *) ALLOCA_collide (n *
tested_rowsize);
memset (tested,0,n * tested_rowsize);
// create a hash table to store all AABBs. each AABB may take up
to 8 cells.
// we use chaining to resolve collisions, but we use a relatively
large table
// to reduce the chance of collisions.
// compute hash table size sz to be a prime > 8*n
for (i=0; i<NUM_PRIMES; i++) {
if (prime[i] >= (8*n)) break;
}
if (i >= NUM_PRIMES) i = NUM_PRIMES-1; // probably pointless
int sz = prime[i];
// allocate and initialize hash table node pointers
Node **table = (Node **) ALLOCA_collide (sizeof(Node*) * sz);
for (i=0; i<sz; i++) table[i] = 0;
//dMessage( 0, "+ coll" );
// add each AABB to the hash table (may need to add it to up to 8
cells)
for (aabb=first_aabb; aabb; aabb=aabb->next) {
int *dbounds = aabb->dbounds;
//dMessage( 0, "+ aabb" );
// X only once?
unsigned long xonlyonce=-1; // always true, even after --
if (dbounds[0]==dbounds[1])
{
xonlyonce=1; // only true first time, then --
}
for (int xi = dbounds[0]; xi <= dbounds[1] && xonlyonce; xi++) {
unsigned long yonlyonce=-1;
if (dbounds[2]==dbounds[3])
{
yonlyonce=1;
}
for (int yi = dbounds[2]; yi <= dbounds[3] && yonlyonce; yi++) {
unsigned long zonlyonce=-1;
if (dbounds[4]==dbounds[5])
{
zonlyonce=1;
}
for (int zi = dbounds[4]; zi <= dbounds[5] && zonlyonce; zi++) {
// get the hash index
unsigned long hi = getVirtualAddress (aabb->level,xi,yi,zi) % sz;
//dMessage( 0, "lop" );
// add a new node to the hash table
Node *node = (Node*) ALLOCA_collide (sizeof (Node));
node->x = xi;
node->y = yi;
node->z = zi;
node->aabb = aabb;
node->next = table[hi];
table[hi] = node;
zonlyonce--;
}
yonlyonce--;
}
xonlyonce--;
}
//dMessage( 0, "- aabb" );
}
//dMessage( 0, "- coll" );
// now that all AABBs are loaded into the hash table, we do the
actual
// collision detection. for all AABBs, check for other AABBs in the
// same cells for collisions, and then check for other AABBs in all
// intersecting higher level cells.
//dMessage(0, "+ coll21");
int db[6]; // discrete bounds at current level
for (aabb=first_aabb; aabb; aabb=aabb->next) {
// we are searching for collisions with aabb
for (i=0; i<6; i++) db[i] = aabb->dbounds[i];
for (int level = aabb->level; level <= maxlevel; level++) {
// X only once?
unsigned long xonlyonce=-1; // always true, even after --
if (db[0]==db[1])
{
xonlyonce=1; // only true first time, then --
}
for (int xi = db[0]; xi <= db[1] && xonlyonce; xi++) {
unsigned long yonlyonce=-1;
if (db[2]==db[3])
{
yonlyonce=1;
}
for (int yi = db[2]; yi <= db[3] && yonlyonce; yi++) {
unsigned long zonlyonce=-1;
if (db[4]==db[5])
{
zonlyonce=1;
}
for (int zi = db[4]; zi <= db[5] && zonlyonce; zi++) {
// get the hash index
unsigned long hi = getVirtualAddress (level,xi,yi,zi) % sz;
// search all nodes at this index
Node *node;
for (node = table[hi]; node; node=node->next) {
// node points to an AABB that may intersect aabb
if (node->aabb == aabb) continue;
if (node->aabb->level == level &&
node->x == xi && node->y == yi && node->z == zi) {
// see if aabb and node->aabb have already been tested
// against each other
unsigned char mask;
if (aabb->index <= node->aabb->index) {
i = (aabb->index * tested_rowsize)+(node->aabb->index >> 3);
mask = 1 << (node->aabb->index & 7);
}
else {
i = (node->aabb->index * tested_rowsize)+(aabb->index >> 3);
mask = 1 << (aabb->index & 7);
}
dIASSERT (i >= 0 && i < (tested_rowsize*n));
if ((tested[i] & mask)==0) {
collideAABBs (aabb->geom,node->aabb->geom,data,callback);
}
tested[i] |= mask;
}
}
zonlyonce--;
}
yonlyonce--;
}
xonlyonce--;
}
// get the discrete bounds for the next level up
for (i=0; i<6; i++) db[i] >>= 1;
}
}
//dMessage(0, "+ coll22");
// every AABB in the normal list must now be intersected against
every
// AABB in the big_boxes list. so let's hope there are not too
many objects
// in the big_boxes list.
for (aabb=first_aabb; aabb; aabb=aabb->next) {
for (dxAABB *aabb2=big_boxes; aabb2; aabb2=aabb2->next) {
collideAABBs (aabb->geom,aabb2->geom,data,callback);
}
}
//dMessage(0, "+ coll23");
// intersected all AABBs in the big_boxes list together
for (aabb=big_boxes; aabb; aabb=aabb->next) {
for (dxAABB *aabb2=aabb->next; aabb2; aabb2=aabb2->next) {
collideAABBs (aabb->geom,aabb2->geom,data,callback);
}
}
//dMessage(0, "- coll2");
lock_count--;
// free linked lists
free_linked_dxAABB_list( first_aabb );
free_linked_dxAABB_list( big_boxes );
for (i=0; i<sz; i++)
{
free_linked_Node_list( table[i] );
}
FREEA_collide( table );
FREEA_collide( tested );
}
######################################################
Best,
Patrick
On 7. Mar 2007, at 20:36 Uhr, Mark Williams wrote:
>
> Lines 497-502 of collision_space.cpp (ODE 0.8) show that HashSpaces
> are
> likely to needlessly crash when dealing with large numbers of objects,
> because the direct alloca() call (rather than using the ALLOCA macro)
> there can quite easily exceed the stack size.
>
> I've also noticed that defining dUSE_MALLOC_FOR_ALLOCA will in many
> cases leak large amounts of memory.
>
>
>
> Cheers,
> Mark
>
>
>
>
> _______________________________________________
> ODE mailing list
> ODE at ode.org
> http://mooshika.org/mailman/listinfo/ode
More information about the ODE
mailing list