I'm need an efficient (and explained) algorithm for Ray-AABB intersection tests. I just need to know if they intersect, not the actual point of intersection. I have actually thought of something: 1. Compute the closest point between the ray and the AABB center. 2. Check if that point is within the AABB If this works, it should, at least in theory, be pretty fast. Would it work? Is there something more efficient? (EDIT: There seems to be an obvious case where it does not work, in fact...) I also need a good algorithm to find the neighbor nodes for an octree node. Just in case you people are wondering, this is for raytracing octree traversal. I am thinking of doing something like: 1. Locate the leaf node in which the ray origin resides 2. Raytrace all the objects in that node 2a. If there is an intersection, we return that object 3. If there is no intersection, find the node our ray intersects among the (up to) 6 neighbor nodes 3a. If the neighbor node intersected is not a leaf node, locate the nearest leaf node in the ray's path 4. Raytrace all the objects in that node... Go to 2a I am still unsure though. There might be more efficient ways and... Can I get away with testing 6 neighbors, or do I need to test the diagonal neighbors too? Anyone experienced this? And if we know a node is intersected by the ray, but want to find the first leaf node to test, what would be a simple method?

As for quickly finding neighbors...you could just store a pointer to the neighbors in each page. This would be expensive in terms of memory, but fast in terms of access speed.

To save memory (at the cost of some speed, since we are concerned both with memory and the file size for persisted quadtrees), the way we deal with this with our quadtree implementation is to label each page according to its position in the tree. We have a hash function to avoid storing strings, but the concept is best grasped by considering the labels to be strings. I'll show this for quadtrees, and hopefully you will see that it is extensible to octrees. The root node is labeled "*". Its 4 children are labelled "*?" where ? becomes 0, 1, 2, or 3 depending on where it is located with respect to *. 0 means north-east, 1 means north-west, 1 means south-west, and 2 means south-east. So, the top-two levels of the tree look like this:

                                 *                          -------|-------                          |   |     |   |                         *0  *1    *2  *3

Now, any subsequent page that is subdivided gets another block of 4. The names of its children are equal to the parent name with an extra "?" character appened at the end. So, if *1 was subdivided its children are *10, *11, *12, and *13. The tree looks like this:

                                 *                          -------|-------                          |   |     |   |                         *0  *1    *2  *3                              |                       -------|-------                       |   |     |   |                      *10 *11   *12 *13

Lets look at this top down. Imagine that the leaf nodes are *0, *3 and the children of *1 and *2 (e.g., *0 and *3 are not subdivided but *1 and *2 are subdivided). From the top down this looks like the following:

      |----------------------|----------------------|      |          |           |                      |      |    *11   |    *10    |                      |      |          |           |                      |      |          |           |                      |      |----------------------|          *0          |      |          |           |                      |      |    *12   |    *13    |                      |      |          |           |                      |      |          |           |                      |      |---------------------------------------------|      |          |           |                      |      |    *21   |    *20    |                      |      |          |           |                      |      |          |           |                      |      |----------------------|          *3          |      |          |           |                      |      |    *22   |    *23    |                      |      |          |           |                      |      |          |           |                      |      |---------------------------------------------|

That sequence of naming occurs all the way down.

Now, for any node, you can find its neighbor by searching for the appropriate named node. Lets say we have a node called *xxxxpy. Here, p uniquely identifies the node's parent at the same level of the hierarchy. y identifies the node within its parent. You can find the values of a neighbor's p and y using various increment/decrement and modulus operations. For example, a node's north parent (on top) will have a y value of

y' = (3 - y) % 4

and a p value of

p' = (y' > y) ? p - 1 : p;

I'm using the ' superscript as shorthand notation for the neighbor. So, the neighbor of *xxxxpy is *xxxxp'y'.

Note that I've used the C conditional operation ?: to determine the neighbor's parent value, p'.

See how this works. For node *23, the north neighbor has:

y' = (3 - 3) % 4 = 0

And,

p' = (0 > 3) ? 2 - 1 : 2 = (false) ? 1 : 2 = 2;

So, the north neighbor of *23 is *20.

Lets try *22. The neighbor has y' = (3 - 2) % 4 = 1 and p' = (1 > 2) ? 2 - 1 : 2 = 2. So the north neighbor of *22 is *21.

Now, lets try one at the boundary between two subdivisions. Lets look at the north neighbor of *21. The north neighbor has:

y' = (3 - 1) % 4 = 2 % 4 = 2

And,

p' = (2 > 1) ? 2 - 1 : 2 = (true) ? 2 - 1 : 2 = 1;

So, the north neighbor of *22 is *12.

Hmmm. You should see that you can do the same type of modulus operation for the south, east, and west neighbors, and that you can extend this for octrees.

If you have a fast hash table lookup of octree nodes based on the name, you can very rapidly find any immediate neighbor of any arbitrary node in the quadtree/octree using this approach.

If the parent of the expected neighbor hasn't been subdivided, then the immediate neighbor, which will be larger than the node of interest, will be the parent of the predicted neighbor. For example, if the node of interest is *20 and *1 was not subdivided, instead of the north neighbor being *13 as predicted, the neighbor will be be the parent of the (nonexistent) *13, e.g., the north neighbor of *20 is *1.

In any case, that's my lecture. I hope it helps!

That seems interesting. Would it be fair to assume that the first node to check for intersection is the node who's center is closest to the ray's origin?

Another idea may be to use a direct-access octree. Moving about the "tree" is really just performed mathematically and is as fast as you can get imho. The problem that I found, is that the structure must be spatially rigid (the divisions are on 2^n boundaries) and the logical recursion depth is finite as well (although there are ways to deal with this if necessary). This tends to result in a lot of geometry getting promoted to higher levels - which is a NonOptimalThing(tm). I started to incorporate the idea of "loose octrees" in conjunction with the direct-access idea, but I got diverted to other activities and never picked it back up again.

If you want, I can dig up some shoddy test code to work with if you want. Graham's idea also sounds pretty good and would probably be very quick without the limitations I listed. It would be interesting to find out the metrics.


Hope that helps.


#dth-0

Quote:Original post by Eelco
afaik no neighboring information is needed.

-check against the top node
-if its not a leaf, check which nodes you intersect with, in what order
-recurse to the childnodes in the right order
-if a leaf is a node, check against the stuff contained in it
-as soon as youve found a hit this way, youre sure its the very first one and you can stop processing.

fast, simple, and doesnt require neighbor information. there are more complicated methods that do involve neighbor pointers, but im not sure they are worth the trouble.

They are "worth the trouble", especially in a raytracer, its much faster to go straight in line through the neighbors than recurse back and forth to find the next node all the time. Plus your method doesn't work. You can't be sure a hit is the first one as soon as you found it, you have to check all child nodes for intersection in order to find the first, second and third hits since you're not sure which child node was hit by the ray first...

I think I've got it mostly figured out. I will adapt Jyk's algorithm to my octree (just got a question though, what is d.Absolute()? A vector with the absolute value of each component?).

1. When theres a raytracing request, I will call TraceRay() on the root octree node.
2. If the current node is not a leaf, it will test all the children nodes for intersection and call TraceRay() on the one which's center is closest to the ray's origin (I will use squared distance, for speed).
3. If the current node is a leaf, it will raytrace all the objects contained, selecting the nearest on the ray's path
4. If a nearest object was found, it will be returned
5. If a nearest object is not found, I will raytrace the "walls" of the node to tell which neighbor to go through and call TraceRay() on that neighbor, this will be very fast
6. If the neighbor is NULL, that means its the end of the ray's path, and I will return NULL
7. If the neighbor is not a leaf... Back to step 2.

To do the actual neighbor resolving, I will just use raytracing, for simplicity's sake. I don't really care about the octree building time. I will find the nearest node on the ray's path (going straight through each "wall" of the current node). I obviously will only care about resolving neighbors of leaf nodes... I will probably code a recursive ResolveNeighbor(node, ray) function that will find the nearest node, ignoring the current node.

I still got questions, however ;) I'm looking for accurate Disc-AABB and Sphere-AABB intersection tests. I will probably start by using bounding AABBs for those, but that may not be efficient.

[Edited by - Max_Payne on November 30, 2004 10:54:28 AM]

I just realized... This can be optimized even further:

If we go through a neighbor and that neighbor is not a leaf, then instead of raytracing all its nodes... Knowing which side of the neighbor we got in from, we can simply compare the intersection point coordinates in "X" and "Y" (relatively to that "wall"), and tell which child node to go in directly... So this whole neighbor traversal algorithm is going to be very fast in the end, as it will require no sqrts or divides, and no useless recursion... Intersection tests will only be needed when building the octree in fact (ResolveNeighbor())... Its beautiful ;)

Hm, my function will probably be pretty simple as well, as I can get rid of the whole if (this.IsLeaf()) case, along with the recursion. I can probably replace that by something like:

CurrentNode = Neighbor;

while (!CurrentNode.IsLeaf())
{
if (Intersection.X > CurrentNode.Center.X)
else
...
}

The code might be redundant because of the number of possible entry faces (6), but I think thats pretty much as fast as this can get.

Quote:Original post by Max_Payne

Quote:Original post by Eelco
They are "worth the trouble", especially in a raytracer, its much faster to go straight in line through the neighbors than recurse back and forth to find the next node all the time. Plus your method doesn't work. You can't be sure a hit is the first one as soon as you found it, you have to check all child nodes for intersection in order to find the first, second and third hits since you're not sure which child node was hit by the ray first...

uhm, what can i say... no?
you can stop when youve found your first intersection. thats why you traverse the childnodes in the right order, and since they dont overlap, this works perfectly fine all of the time. its the whole point of spatial divisioning.

And what is the "right order"? With a cheap intersection test, you just know a ray intersected a node, not where. This ray, going through your node, can go through as many as tree of the immediate child nodes of that node. You have to be able to tell which one is the right one. To do what, you have to do tests on all of the 8 child nodes, and find the first one that needs to be tested. You then need to test the other nodes that were intersected... It becomes a big recursion.

While with my algorithm... I locate the exact child node that was intersected, and in 90% of the cases, I just hop right from one node to another. In some cases, I will have to go down one or two levels at most, but I won't have to find the way up in the recursion tree again. In fact, it might even be possible to implement this easily in a fully iterative manner, with no recursion at all, which would be one step further when it comes to speed (and an additional stack overflow protection).