3D collision detection

3D libraries are conceived as just drawing primitives, and nothing more. That's why graphics programmers are asked to reinvent the wheel several times.

One of those wheels is the "world space" partitioning. In particular, the collision detection of meshes.

I don't know how serious engines handle it on a per-pixel/vertex basis, but I think they just do miracles. I implemented something simpler for my PLT by using cheap bounding spheres.

The improved geometries loader "keeps in mind" the minimum and maximum coordinates for each axis, while it constructs the vertex arrays; at the end of the loading process, it uses those coordinates to find the middle point of the mesh and the farthest vertex from it: they are the bounding sphere center and radius, respectively.

Checking if a mesh collides with another is straightforward:

• transform the bounding centers from model to world space, and compute the distance (let's call this value "D") between them
• sum up the two bounding radius (let's call it "S")
• if D > S meshes don't collide
  

It's kind of a cheat, but it works.
Of course, using complex meshes will reveal its nature: it's far from being accurate. But it so fast!

I think there's a couple of possible optimizations.

The first one is, well, "CAD driven": I could simply cut down every model into many "groups", and give everyone its own bounding sphere. The drawback is, obviously, that the designer is asked to think meshes as a collection of separate tranches, and everything works better if each partition fills out its "space". Moreover, this solution makes LOD design slightly more complex.

The second one is more challenging: compute the partitions on fly, during geometry loading, by using a stochastic approach: areas denser of polygons are more likely to be relevant for the mesh, and should be enclosed by their own bounding sphere.

Wavefront .OBJ files & Vertex Buffer Objects

OBJ files are handy for many reasons:

• they're text files
• well documented
• easy to parse
• and many professional softwares can export them

This is why they are so popular as standard files for 3D graphics.

Their structure is basically a (long) list of vectors definitions (spatial, normals, texture coordinates, and so on) followed by a (long) list of structures defining faces. What are faces? Faces are tuples of indexes, which point specific vertexes, normals and texture coordinate in the previous lists. At least three vertexes are needed for each face, because it forms a triangle, that is the smaller polygon we can create.

Why is this needed? Well, because a single vertex could be shared by many faces (=polygons). That's important in real-time 3D programming, because avoiding redundancy is good for performances!

This is the very same idea behind OpenGL's indexed vertex arrays: rather than sending to the video card a list of vertexes, normals and texture coordinates (the so called immediate mode) we prepare a couple of arrays filled with informations, and another array of indexes which tell OpenGL what vertex use in a certain primitive.

Sounds good, uh? Well, there is a couple of drawbacks actually.

The biggest is that every index points simultaneously at vertex, normals and texture arrays! For instance, if our first index is "1", that face points vertex[1], normal[1] and texture_coord[1]. That's a real nightmare, because there's no ensurance that our modeling softwares will produce .OBJ files featuring correctly ordered lists! Moreover, there's often a few of vertexes (which are often shared by many faces) and lot of normals!

So what?? Well, OpenGL does not aid us in any way: you gotta solve with your hands. My solution is the following:

• parse the OBJ file, loading vertexes, normals, and faces;
• from faces, create a definitive vertex index and a temporary arrays for normals and textures coordinates;
• for each i in number_of_indexes do
  definitive_normal_array[ index_array[i] ] :=
  Temporary_normals_array[ TemporaryNormalIndexes[i] ]

And there you go, you have correct normals bound to the right vertex. You could even have time for re-normalizing them, if they aren't.

The most interesting way for drawing this series of arrays is the use of Vertex Buffer Objects (VBO). They're similar to the indexed vertex arrays, but have interesting features... like dropping geometries in the fastest video card memory and use it! The boost of performances is impressive, and they are easy enough to deal with.

My PLTmesh::Draw() method is this:

// PLT_VBOnames are references to the VBOS - see glGenBuffers()

glEnableClientState(GL_NORMAL_ARRAY);
glBindBuffer(GL_ARRAY_BUFFER, PLT_VBOnames[2]);
glNormalPointer(GL_FLOAT, 0, NULL);

glEnableClientState(GL_VERTEX_ARRAY);
glBindBuffer(GL_ARRAY_BUFFER, PLT_VBOnames[0]);
glVertexPointer(3, GL_FLOAT, 0, (char *) NULL );

glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, PLT_VBOnames[1]);

glDrawElements(GL_TRIANGLES, this->IndexesArray.size(), GL_UNSIGNED_INT, (GLvoid*)((char*)NULL));

glDisableClientState(GL_VERTEX_ARRAY);
glDisableClientState(GL_NORMAL_ARRAY);

glBindBuffer(GL_ARRAY_BUFFER, 0);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);

Quite simple and clear! :)