Storing connectivity without linked lists

Suppose you had 100 people. Some of those people held hands. Some, didn't.

QUESTION: How many arrays would it take to store the connectivity information?

ANSWER: ONLY 1.

This beautiful idea probably stems from graph theory, but I've seen an implementation of something similar when storing edge to edge connectivity information in one of Eric Lengyel's implementation of finding unique edges. The reason this works is you invert the concept of an array. Instead of using the index of an array to store a value, the index of the array IS the value. In this case, the index of the array is the person, and the value is the next person your connected to.

So suppose you had 5 people, 0..4, and person 0, person 2, and person 3 were holding hands, and person 1 and person 4 were not holding anyone's hands.

The array would look like this { 0x02, 0xFF, 0x03, 0x00, 0xFF }. This means person 0 is holding hands with person 2, person 1 is holding hands with nobody (0xFF means end of the chain), person 2 is holding hands with person 3, and person 3 is holding hands with person 0, and person 4 is again, holding hands with nobody. Now in this case, this is circular connectivity. But suppose you only wanted to keep track of who on the left was holding your hand. Also assume that person 0 is holding the next person in their left hand. Then the array looks like this: { 0x02, 0xFF, 0x03, 0xFF, 0xFF }. The cool thing about it is the minute you find someone who is holding hands, you can instantly traverse the array and find all the other people holding hands. In this example, the connectivity goes in one direction.

This similar concept explains how Eric Lengyel's code works: http://www.terathon.com/code/edges.php

Simply stated, any time you discover a unique edge, you can use this algorithm to associate the connectivity of multiple edges with one edge. And no matter what which link ("hand") of the chain your in, you can always find the end of the chain (0xFF) because the connectivity goes in one direction. Since the connectivity goes in only direction, you only ever need one value for every one unique element. This means that, in the people example, as long as you only need to know who is holding your left hand, then the array will never need to be bigger than the number of people total.

With the edge concept, it is slighty different. You can, at most, have 3 * triangleCount individual edges, but some of those edges may not be unique. Generally, triangles are considering sharing an edge if, given triangles T0 and T1, there exists an edge such that edge index 0 < edge index 1 on T0, and edge index 1 < edge index 0 on T1. However, it is still possible that MORE than 2 triangles can share an edge. Let's say 3 triangles T0, T1, and T2 share an edge E, so that the actual geometry looks like a flattened mercedes logo. Then while there will be three triangles all sharing one edge, in this case there will only be two *unique* edges, E0 and E1, where E0 shares faces with T0 and T1, and E1 shares faces with T1 and T2.

In order for this algorithm to handle these cases, we want to store the connectivity of all the edges that are not unique. To do this, we define a semantic such that the first edge (defined by 2 indices) you encounter where triangle indices i0 < i1 starts the chain. And any subsequent edge with the same semantic i0 < i1 continues the connectivity chain. Using this semantic allows us to use connectivity when required, but NOT when we are dealing with normal edges that only are sharing two faces (triangles) per edge. Please see the code for more details :-)

AABB vs OBB

It seems I can't help but stir controversy. I got an e-mail from the LPSM again - [the] League [of] People Smarter [than] Me. This league is quite large, and no matter how hard I try, they are always there..smarter..better.

However, that is a good thing :-) Because wisdom is meant to be shared. I've just been told that AABB trees generally are superior to OBB trees when it comes to physics because the speed of traversing these trees outmatches any false positives. According to the Erwin, the author of the Bullet open source physics engine, most physics engines use this approach. So I invite anyone to check out his work and its very liberal licensing terms - http://www.continuousphysics.com/Bullet/

Unfortunately my game (huh, what game?) is not intense in the physics dept. so I won't be using the library. However I definately will take a peek under the hood and see if I can learn some new things :)

Oriented Box collision detection

I want to direct your attention to two useful tutorials for developing a hierarchical based collision detection system.

The first link covers the OBB (oriented bounding box) tree - http://www.owlnet.rice.edu/~comp650/Spring01/presentations/OBB/OBBTree.ppt

The second covers a tutorial on the mathematics behind principal component analysis, which is useful to understand some of the mathematics in the OBB Tree paper: http://csnet.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf

There are also two books I recommend as well. The first is Computational Geometry by Berg, Kreveld, Overmars, and Schwarzkopf, and the second is - as mentioned before - Christer Ericson's book Real Time Collision Detection.