I'm back

Need to start blogging again... fast forward to today. I'm on the DirectX 11 driver team for AMD and working on two articles for an upcoming book. I wonder what kind of (mis)information I've posted about in the past on this blog.

One constant - I'm still in Orlando.

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.

Wealth of Material

Sorry for the lack of updates.. I am going in this transitionary period where I'm working and learning new things and do not have much to comment on. Geometrics seems to have some exciting stuff with geometric algebra and real-time radiosity, but I don't think it is anything anyone without a really clever knowledge of the papers and the radiosity algorithms couldn't do. This is really hard stuff, though. At least for me.

I'm reading a great paper by Robin Greene discussing Spherical Harmonic Lighting.. what I read and what I implement is usually 2 levels behind. Hopefully in the future I can close that gap :-) It is amazing how many well written papers are out there and the wealth of material..you know, past what you can get from books. The GI (global illumination) books out there aren't necessarily that accessible. To be accessible, a book must be able to present a complex problem in the most thorough way without being overwhelming, without lacking a good solid introduction, and without being overly terse or esoteric.

I've also read, recently, most of the Age of Spiritual Machines and am wondering about the future of AI and humans as well. I do believe it is possible to have machine level intelligence. Part of me wonders then am I in the wrong field? Perhaps I should be working towards immortality ;-)

Matthew

The 4th of July

I finally spent some time with my Dad and Grandmother up in Illinois over the 4th of July weekend. That was nice for a chance. Otherwise, just been working hard. I released my first alpha a few days ago for my game.

Right now I'm starting to learn more interesting 3d concepts..splines, shaders, etc. Luckily I haven't lost all my hair yet, because I'm going to need some to spare for these new things :)

Numerical precision - Update

I just got a post from a few people including Christer Ericcson on the importance of scaling your epsilon value. Although my post is right to some extent (it is a good start, and definately superior to doing absolutely nothing), unfortunately it is also inadequate. In addition to a fixed tolerance, one should also consider scaling the epsilon value so you have a relative tolerance level. For more information see his response on my last blog entry about Numerical Precision.