# Banging head against wall - collision detection

This topic is 3566 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello all. I've been having some problems with collision detection and could really use some help. I've created a system where I read a model from file and voxelize it; I then do collision detection on the voxel trees (which are octrees, of course). Most of it works well, but sometimes I get wrong results (false positives and negatives). I can't figure out why. I can create and render the tree just fine, and collisions between zero-level trees (that is, OBB's) works fine, but if I try to do collision testing between the leafs of two trees I often get wrong results. I'm posting the relevant code I'm using to render the trees and perform the (simplified for debugging) collision tests. If you could find any errors, I'd be very grateful. Please note that this is all simplified debugging code, so no need to point out obvious inefficiencies or the inaccuracy of sphere-sphere collision testing. It's becoming clear that the error cannot be the collision test, nor the offset calculation. I have no idea what the problem is; perhaps the way I render things. If you're glancing through the code, please focus on the first and third code sections; these are the ones I believe might be most likely to contain an error that I would miss. I'm using the CML math library and have asked the CML devs for help too; I'm reposting here to improve my chances to find a solution. First, the obvious thing: the rendering code. The following is executed each time I render an object in my efforts to debug the problems:
	glPushMatrix();
glTranslatef(position[0], position[1], position[2]);
glMultMatrixf(alignment.data());
glCallList(collisionTreeList);
glPopMatrix();


The collisionTreeList is built from an octree. The relevant member of the octree is called voxel, which is a Cube with two opposing corners (reached with operator[]). After having loaded a tree from a file, I create the display list like so:
	Octree *tempTree;
stack<Octree*> renderStack;
renderStack.push(collisionTree);
collisionTreeList = glGenLists(1);
glNewList(collisionTreeList, GL_COMPILE);
glColor3f(0.8, 0.8, 0.8);
while(!renderStack.empty())
{
tempTree = renderStack.top();
renderStack.pop();
for(int i = 0; i <8>HasChild(ChildIndex(i)))
renderStack.push(tempTree->GetChild(ChildIndex(i)));
}
//if(tempTree->IsSolid())
if(tempTree->IsLeaf())
{
glNormal3f(0, 0, -1);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[0][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[0][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[1][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[1][1], tempTree->voxel[0][2]);

glNormal3f(0, 0, 1);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[0][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[0][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[1][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[1][1], tempTree->voxel[1][2]);

glNormal3f(0, -1, 0);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[0][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[0][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[0][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[0][1], tempTree->voxel[1][2]);

glNormal3f(0, 1, 0);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[1][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[1][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[1][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[1][1], tempTree->voxel[1][2]);

glNormal3f(-1, 0, 0);

glVertex3f(tempTree->voxel[0][0], tempTree->voxel[0][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[0][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[1][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[0][0], tempTree->voxel[1][1], tempTree->voxel[0][2]);

glNormal3f(1, 0, 0);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[0][1], tempTree->voxel[0][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[0][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[1][1], tempTree->voxel[1][2]);
glVertex3f(tempTree->voxel[1][0], tempTree->voxel[1][1], tempTree->voxel[0][2]);
glEnd();
}
}
glEndList();


As you see, I go through the tree until I find the leaf nodes and then create a box from the corners of the voxel in each leaf. During program flow, I update the rotation and position of each object like so:
void MobileObject::Tick(float seconds)
{
for(int i = 0; i < 3; ++i)
position += velocity*seconds;

matrix_orthogonalize_3x3(alignment);
}


Finally, for each pair of objects, I perform the collision test. I've created a naive tree traversal and distance test for this debug build, but the problem persists. Parts of this you've seen before, but here is the complete collision test:
bool Object::Collide(const Object &other)
{
//if either object lacks a collision tree, obviously no collision can occur
if(!collisionTree || !other.collisionTree)
return false;

std::vector<Octree> leftStack, rightStack, tempStack;
Octree *leftTree, *rightTree;
vector3f leftPos, rightPos;

leftStack.push_back(collisionTree);
rightStack.push_back(other.collisionTree);

//this loop finds all leaves in each object and puts them in leftStack and rightStack.
tempStack.clear();
while(!leftStack.empty())
{
leftTree = leftStack.back();
leftStack.pop_back();

if(leftTree->IsLeaf())
tempStack.push_back(leftTree);
else for(int i = 0; i <8>HasChild(i))
tempStack.push_back(leftTree->GetChild(i));
}
}
leftStack.swap(tempStack);

tempStack.clear();
while(!rightStack.empty())
{
rightTree = rightStack.back();
rightStack.pop_back();

if(rightTree->IsLeaf())
tempStack.push_back(rightTree);
else for(int i = 0; i <8>HasChild(i))
tempStack.push_back(rightTree->GetChild(i));
}
}
rightStack.swap(tempStack);

//now, perform the actual test
for(int i = 0; i <leftStack>GetOffset());
leftTree = leftStack;
for(int j = 0; j <rightStack>GetOffset());
rightTree = rightStack[j];

if((leftPos - rightPos).length() <fabs>voxel[0][0] - leftTree->voxel[1][0]) * 0.5 +
fabs(rightTree->voxel[0][0] - rightTree->voxel[1][0]) * 0.5)
{
std::cout << "done " << i << " " << j << std::endl;
return true;
}
}
}
return false;
}


For reference, the Octree is defined like so (.cpp not shown - if there was an error in creating leaves or traversing the tree, it would also show when creating the display list, so I considered it unnessecary to add).
class Octree
{
public:
Cube voxel;

Octree(unsigned int depth, float size, float oX, float oY, float oZ); //size = shortest distance to edge from origin
~Octree();

bool AddPoint(float x, float y, float z);
inline bool IsSolid();
inline bool IsLeaf();
inline int Height();

bool HasChild(int index);
Octree* GetChild(int index);
inline const cml::vector3f GetOffset();

Cube GenerateCubeAt(float x, float y, float z) const;

void Prune();
private:
bool solid;
std::bitset<8> hasChild;
unsigned int levelsAboveBottom;
cml::vector3f centre;
Octree *child[8];

Octree(Octree ©) {}; //hidden, empty copyconstructor.
bool AddChild(ChildIndex index, float x, float y, float z); //checks child for existence, adds it otherwise. Adds point to child either way.
};

bool Octree::IsSolid()
{
return solid;
}

bool Octree::IsLeaf()
{
return hasChild.none();
}

int Octree::Height()
{
return levelsAboveBottom;
}

const cml::vector3f Octree::GetOffset()
{
//return centre; //removed during debugging
return (voxel[0] + voxel[1])*0.5;
}


[Edited by - Hnefi on May 17, 2008 7:48:21 AM]

##### Share on other sites
EDIT: I didn't read what you had posted about the code below. My second guess would be double checking the transformations by drawing something where the center of each box should be, so you know the positions are correct.

I rarely work in 3D, so I can't check the transformations you were asking about. However, this piece of code:

if((leftPos - rightPos).length() <fabs>voxel[0][0] - leftTree->voxel[1][0]) * 0.5 +        fabs(rightTree->voxel[0][0] - rightTree->voxel[1][0]) * 0.5)      {        std::cout << "done " << i << " " << j << std::endl;       return true;      }

seems suspicious if you're trying to check if 2 OBB's are intersecting. I've always been under the impression that OBB's are checked for intersection by computing the boxes' surface normals and checking for overlap. Distance calculation ((leftPos - rightPos).length()) seems like it should be for a sphere. If you know that code is correct, you don't have to explain how it works to me, I just thought I'd point that out.

##### Share on other sites
Finally found the bug. Simple traversal error.