🔒 Locked

Octree traversal/Ray-AABB intersection/Octree neighbors

Started by Max_Payne Nov 29, 2004 at 11:59 AM 25 replies 11k views

Original Post

Nov 29, 2004 at 11:59 AM

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?

grhodes_at_work

Nov 29, 2004 at 3:53 PM

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!

Zakwayda

Nov 29, 2004 at 7:01 PM

Quote:
I 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.

bool AABB::IntersectSegment(const Vector3& p1, const Vector3& p2) const{    Vector3 d = (p2 - p1) * 0.5f;    Vector3 c = p1 + d;    Vector3 ad = d.Absolute();    c -= m_center;    if (fabsf(c[0]) > m_extents[0] + fabsf(d[0]))        return false;    if (fabsf(c[1]) > m_extents[1] + fabsf(d[1]))        return false;    if (fabsf(c[2]) > m_extents[2] + fabsf(d[2]))        return false;				    if (fabsf(d[1] * c[2] - d[2] * c[1]) > (m_extents[1] * ad[2]) + (m_extents[2] * ad[1]))        return false;    if (fabsf(d[2] * c[0] - d[0] * c[2]) > (m_extents[2] * ad[0]) + (m_extents[0] * ad[2]))        return false;    if (fabsf(d[0] * c[1] - d[1] * c[0]) > (m_extents[0] * ad[1]) + (m_extents[1] * ad[0]))        return false;			    return true;}

This is some old code that I haven't used in a while, but I'm pretty sure it's correct (let me know if you try it and it doesn't work).

Anyway, this is a fast boolean line segment/AABB test using the separating axis theorem. If you're already familiar with the SAT, you can probably skip the rest of this explanation.

The SAT states that if there exists an axis onto which the projections of two objects are disjoint, then the two objects are disjoint. The trick is knowing which axes to test.

In the general case, for two convex polytopes, the axes to test are the normals to the faces of each polytope, and the cross products of each edge from one polytope with each edge of the other.

Here we can simplify based on the fact that:

1. The AABBs face normals are axis-aligned.

2. Half of the AABB face normals are negatives of the others and are therefore redundant (axes which are negatives of each other are equivalent as far as the SAT is concerned).

3. The line segment can be viewed as a 'degenerate' polytope.

What this all boils down to is that we have 6 axes to test:

1. The three axes of the AABB, which are the world axes.

2. The cross products of the segment direction and the three world axes.

What we do is compare the sum of the projected 'radii' of the AABB and line segment onto the axis in question. If the sum is less than the projected difference vector between the two, there is no intersection - it's similar to the familiar test for circle intersection.

Anyway, I think I got all that right...in any case, that's the general idea.

'Hope some of that is helpful to you.

Max_Payne

Nov 29, 2004 at 7:14 PM

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?

xiuhcoatl

Nov 29, 2004 at 7:19 PM

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

Eelco

Nov 30, 2004 at 2:58 AM

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.

Max_Payne

Nov 30, 2004 at 9:54 AM

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]

Max_Payne

Nov 30, 2004 at 10:32 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.

Eelco

Nov 30, 2004 at 12:05 PM

Quote:
Original post by Max_Payne
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...

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.

i dont think the speedup you get by saving yourself a bit of recursion is going to be very big, since you only need log(n) recursion steps anyway, but if you can spare the memory why not?

Max_Payne

Nov 30, 2004 at 12:29 PM

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).

Eelco

Nov 30, 2004 at 1:05 PM

Quote:
Original post by Max_Payne
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.

it takes excactly three divides to find out for each and every child if its intersected, and if so along which part of the ray, thus in what order. three divides which you need to perform anyway.
you enter a node passing down the position along the ray where its entered and exited, and intersect with all three planes by doing one simple divide to obtain all you need to know about this node and its children.

Quote:

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).

im hard pressed to imagine a stack overflow. 100 recursions will fit within the stack easily, but its quite impossible to store a tree with 8^100 nodes: there arnt even that many particles in the visible universe.

also, whats so hard about 'finding your way up in the recursion tree'? i was under the impression that this could be done with a simple return statement. after this return statement youll automagicly end up where you want to be at no cost at all: in the appropriate neighbor node. you already did the intersections for the parent node, which are conveniently popped from the stack when you return from the child, so youll just continue processing the little block of if statements to decide in what order the nodes are hit, recurse to those that are, until there are none left and you go up one level again with the same efficiency.

Max_Payne

Nov 30, 2004 at 3:26 PM

Quote:
Original post by Eelco
it takes excactly three divides to find out for each and every child if its intersected, and if so along which part of the ray, thus in what order. three divides which you need to perform anyway.

Oh, thats all, and how do you do all that in three divides?

Quote:
also, whats so hard about 'finding your way up in the recursion tree'? i was under the impression that this could be done with a simple return statement. after this return statement youll automagicly end up where you want to be at no cost at all

Wrong, there is a cost to a return statement, and when you want to trace a billion rays, the cost adds up pretty quick. Going up and down the stack while testing nodes for intersections in a *questionable* order makes no sense. With my traversal algorithm, I'll end up finding an intersection in the first node in 50% of the cases (since you have alot of chances to hit near occluders).

Did you even implement what you are talking about? Because I don't see how you can traverse nodes "in the right order" by somehow magically sorting them with "no cost at all". There is a reason neighbor traversal exist: its the most efficient raytracing octree traversal solution, because it makes use of precompiled data (the neighbor nodes).

And don't get me wrong, your solution will *work*, it just won't be as fast... This is because if you just test nodes for intersection in the order you find them in your tree, you're not exploiting the fact that raytracing effectively look for the *first* hit in the ray's path.

Eelco

Nov 30, 2004 at 4:26 PM

Quote:
Original post by Max_Payne
Quote:
Original post by Eelco
it takes excactly three divides to find out for each and every child if its intersected, and if so along which part of the ray, thus in what order. three divides which you need to perform anyway.

Oh, thats all, and how do you do all that in three divides?

its basic octree/kd-tree traversal theory. because all planes are oriented along the coordinate system axes, all you need to do to get the distance along the ray to each of the three splittingplanes that define the child nodes, and divide the distance to a plane by the matching component of the directionvector of your ray. i just realized you can precalc the inverse directionray and turn these three divides into three multiplies, but thats probably common tree traversal knowledge.

Quote:

Quote:
also, whats so hard about 'finding your way up in the recursion tree'? i was under the impression that this could be done with a simple return statement. after this return statement youll automagicly end up where you want to be at no cost at all

Wrong, there is a cost to a return statement, and when you want to trace a billion rays, the cost adds up pretty quick. Going up and down the stack while testing nodes for intersections in a *questionable* order makes no sense. With my traversal algorithm, I'll end up finding an intersection in the first node in 50% of the cases (since you have alot of chances to hit near occluders).

i know calling and returning from functions takes time. ofcource it does. however, the question boils down to this: is it faster to return a couple of times to the parent node (50% of the time this will be one level back, 25% of the time 2 levels, 12.5% 3, ect), or is it faster to figure out what neighbor we will end up in, forfeiting all the intersection information stored in the stack, then having to do 6 intersection tests, against all planes of the new cube, because we come there with empty hands so to speak?

btw, the sorting thing isnt *questionable*, it works and im really sure of that.

Quote:

Did you even implement what you are talking about? Because I don't see how you can traverse nodes "in the right order" by somehow magically sorting them with "no cost at all". There is a reason neighbor traversal exist: its the most efficient raytracing octree traversal solution, because it makes use of precompiled data (the neighbor nodes).

as a matter of fact i havnt implemented anything of it at all, but please dont be too quick to dismiss my input based on that. i did quite some reading on this subject.

ive just looked it up, and the conclusion from this (quite torough) paper* is that traversal in a neighbor linked structure is generally SLOWER than in a recursive manner (page 110)

however, since you dont depend on the information in the stack, it can be faster for short (mainly secondary) rays close to a surface, since you dont have to traverse the tree from the top down but can start directly from the origin-node so if you have a high probability of hitting a surface after only a couple of traversals it is faster.

and yeah sorting 8 entries can be hardcoded with a couple of if's at no cost at all indeed.

Quote:

And don't get me wrong, your solution will *work*, it just won't be as fast... This is because if you just test nodes for intersection in the order you find them in your tree, you're not exploiting the fact that raytracing effectively look for the *first* hit in the ray's path.

you might want to consider not to state your suspicions as fact.

i really recommend reading the relevant parts of the paper i mentioned. its a bit large (220 pages) but it goes really indepth regarding the best spatially divisioning methods for raytracing. its general conclusion is that kd-trees are by far the best choice, and will certainly be a better improvement over your octree than adding neighbor nodes, which is only beneficial under special circumstances. however, im not saying you shouldnt also investigate the possible benefits of adding neighbor links. im just saying: invesigate first before you discover youve wasted a lot of time.

its called 'heuristic ray shooting algorithms' by 'vlastimil havran'. im affraid i dont have a linky cause its on my harddisk.

Zakwayda

Nov 30, 2004 at 5:47 PM

Max,

Vector3::Absolute() does what you said - returns a vector with the absolute value of each component. Looking at the code I posted, I see that I created a vector ad = d.Absolute(), but then used fabsf(d[]) in the next few lines when I should have used ad[] - I don't know why I did that. Once (if) you get the code working, you might fix that.

As to your other questions, by disc, do you mean a 2d disc, or just a 'short cylinder'?.

Fortunately, the sphere/AABB test is pretty easy. As you would expect, if the distance from the sphere center to the AABB is greater than the sphere radius, the sphere and AABB do not intersect. So all you need is a function that returns the distance from a point to an AABB. This turns out to be pretty easy, and might look something like this:

bool SquaredDistancePointAABB(const Vector3& p, const Vector3& min, const Vector3& max){    float dsquared = 0.0f;    for (int i = 0; i < 3; i++)    {        if (p > max)            dsquared += (p - max) * (p - max);        else if (p < min)            dsquared += (min - p) * (min - p);    }        return dsquared;}

(That's off the top of my head, so I may not have gotten it exactly right - I think I did though...)

Anyway, the algorithm essentially classifies the point in relation to the 27 Voronoi regions of the AABB (including the interior). Due to the axis-aligned axes, it all reduces to some pretty simple code.

If the point is in a region associated with a face, the distance is simply the distance to that face. Likewise for the regions associated with the AABB's edges and corners.

Anyway, I hope that is helpful to you (if you haven't figured it out already).

Max_Payne

Nov 30, 2004 at 7:21 PM

Quote:
Original post by Eelco
i know calling and returning from functions takes time. ofcource it does. however, the question boils down to this: is it faster to return a couple of times to the parent node (50% of the time this will be one level back, 25% of the time 2 levels, 12.5% 3, ect), or is it faster to figure out what neighbor we will end up in, forfeiting all the intersection information stored in the stack, then having to do 6 intersection tests, against all planes of the new cube, because we come there with empty hands so to speak?

You only have 3 intersection tests to actually do (ie: if RayDirection.Y > 0, you're not going to test the bottom neighbor)... And... You only have one plane to test per intersection test, since you're *inside* a node, and each face of the node you're in leads to a neighbor. So you don't have to fully test the neighbor nodes for intersection, which is interesting in terms of performance.

Quote:
as a matter of fact i havnt implemented anything of it at all, but please dont be too quick to dismiss my input based on that. i did quite some reading on this subject.

It takes more than reading to understand this, it requires some active thinking.

Quote:
and yeah sorting 8 entries can be hardcoded with a couple of if's at no cost at all indeed.

Overhead is overhead, but its mainly the fact that you have to test 8 nodes for intersection, and your function calls, that will make such a recursive approach less efficiant than neighbor traversal.

Quote:
you might want to consider not to state your suspicions as fact.

Well you might want to think about what I said. I am examining the algorithms for this on a concrete basis, you are merely guessing that your solution would *probably be almost as fast* and avoiding the questions, trying to negate the fact that you're going to be performing more operations, and that hence, its going to be slower.

Eelco

Dec 1, 2004 at 3:15 AM

Quote:
Original post by Max_Payne
Quote:
Original post by Eelco
i know calling and returning from functions takes time. ofcource it does. however, the question boils down to this: is it faster to return a couple of times to the parent node (50% of the time this will be one level back, 25% of the time 2 levels, 12.5% 3, ect), or is it faster to figure out what neighbor we will end up in, forfeiting all the intersection information stored in the stack, then having to do 6 intersection tests, against all planes of the new cube, because we come there with empty hands so to speak?

You only have 3 intersection tests to actually do (ie: if RayDirection.Y > 0, you're not going to test the bottom neighbor)... And... You only have one plane to test per intersection test, since you're *inside* a node, and each face of the node you're in leads to a neighbor. So you don't have to fully test the neighbor nodes for intersection, which is interesting in terms of performance.

as i said, the question is, in what case do you need to do more operations. i know neighbor traversal can be optimized quite nicely aswell, but is it faster than recursion? its a complex question which i dont think either one of us is qualified to answer on the top of our heads. thats why i looked it up, and gave you a reference to check it for yourself. its all there, including a table containing all operations needed per node for several types of algorithms, and a detailled explanation of under which conditions which algorithm is faster.

Quote:

Quote:
as a matter of fact i havnt implemented anything of it at all, but please dont be too quick to dismiss my input based on that. i did quite some reading on this subject.

It takes more than reading to understand this, it requires some active thinking.

i find a combination of reading and active thinking to be most productive, but thanks for the suggestion anyway.

Quote:

Quote:
and yeah sorting 8 entries can be hardcoded with a couple of if's at no cost at all indeed.

Overhead is overhead, but its mainly the fact that you have to test 8 nodes for intersection, and your function calls, that will make such a recursive approach less efficiant than neighbor traversal.

since youre obviously not going to listen to my explanations as to why i think recursion is hard to improve upon, ill say it one last time: read the paper.

Quote:

Quote:
you might want to consider not to state your suspicions as fact.

Well you might want to think about what I said. I am examining the algorithms for this on a concrete basis, you are merely guessing that your solution would *probably be almost as fast* and avoiding the questions, trying to negate the fact that you're going to be performing more operations, and that hence, its going to be slower.

im sorry, but it seems you completely ignored the first paragraph of my previous post where i wasnt trying to avoid any questions at all, but infact formulating them, later answering them AND backing it up with other peoples research.

but hey if you want to beat the odds and be smarter than the guy who probably did years of very torough research into this very subject, are infact even too desinterested to comment on the suggestion i gave you regarding his paper, kd-trees and its relevance to your subject, all i can do is leave this thread with the bitter taste of wasted time.

nonetheless the best of luck with your project. is it going to be distributed photon mapping or something like that? should be interesting. too bad i cant be of any help. its really frustrating im appearantly that bad at getting my message across.

Max_Payne

Dec 1, 2004 at 6:57 AM

Quote:
Original post by Eelco
as i said, the question is, in what case do you need to do more operations. i know neighbor traversal can be optimized quite nicely aswell, but is it faster than recursion? its a complex question which i dont think either one of us is qualified to answer on the top of our heads. thats why i looked it up, and gave you a reference to check it for yourself. its all there, including a table containing all operations needed per node for several types of algorithms, and a detailled explanation of under which conditions which algorithm is faster.

Its rather obvious that neighbor traversal is faster, for many reasons, but I think the way I stated it best goes as follows : It makes use of precompiled information and saves time by using it.

Quote:
since youre obviously not going to listen to my explanations as to why i think recursion is hard to improve upon, ill say it one last time: read the paper.

You're not providing any valid arguments so far and my implementation of neighbor traversal is almost ready so ;)

Quote:
im sorry, but it seems you completely ignored the first paragraph of my previous post where i wasnt trying to avoid any questions at all, but infact formulating them, later answering them AND backing it up with other peoples research.

Research, research. We're on a web forum, you're saying one option is best, for discutable reasons, why don't you just prove it. I'm not going to read a 200 page paper by Idontknowho just for fun.

Eelco

Dec 1, 2004 at 11:24 AM

Quote:
Original post by Max_Payne
Quote:
Original post by Eelco
as i said, the question is, in what case do you need to do more operations. i know neighbor traversal can be optimized quite nicely aswell, but is it faster than recursion? its a complex question which i dont think either one of us is qualified to answer on the top of our heads. thats why i looked it up, and gave you a reference to check it for yourself. its all there, including a table containing all operations needed per node for several types of algorithms, and a detailled explanation of under which conditions which algorithm is faster.

Its rather obvious that neighbor traversal is faster, for many reasons, but I think the way I stated it best goes as follows : It makes use of precompiled information and saves time by using it.

wow, youre even more arrogant than me.

Quote:

Quote:
since youre obviously not going to listen to my explanations as to why i think recursion is hard to improve upon, ill say it one last time: read the paper.

You're not providing any valid arguments so far and my implementation of neighbor traversal is almost ready so ;)

yeah that explains why you dont want to hear of any alternatives. just tell me you dont want to hear about alternatives and ill shut up, instead of just repeating your poorly backed assertions about efficiency are more accurate than the results of someoneelses torough labor.

Quote:

Quote:

Quote:
im sorry, but it seems you completely ignored the first paragraph of my previous post where i wasnt trying to avoid any questions at all, but infact formulating them, later answering them AND backing it up with other peoples research.

Research, research. We're on a web forum, you're saying one option is best, for discutable reasons, why don't you just prove it. I'm not going to read a 200 page paper by Idontknowho just for fun.

why i dont just prove it? gee, let me see, that would take me only a couple of weeks. im sorry but i find the already considerable estimated hour ive put in this thread more than your attitude deserves. i have looked up and given you the exact pagenumber where the point im trying to make is covered, would you like a linenumber aswell?

Max_Payne

Dec 1, 2004 at 11:36 AM

Quote:
yeah that explains why you dont want to hear of any alternatives. just tell me you dont want to hear about alternatives and ill shut up, instead of just repeating your poorly backed assertions about efficiency are more accurate than the results of someoneelses torough labor.

You should be able to back up what you say by yourself. You think other alternatives are better? Then why don't you provide us with clear reasons why.

But anyways, I completed some "pseudocode" of what my iterative function will look like. Its going to be a long function, but it will also be quite efficient. I should hopefully have time to implement it tonight. Code is worth 10000 words:

CSceneObject* COctree::TraceRay(const CRay& Ray, CVector3& NearestPoint, float& NearestDistance){    // Get the ray origin and direction    Origin    = Ray.Origin;    Direction = Ray.Direction;    // We start at the root node    COctreeNode* pCurrentNode = m_pRootNode;    // Locate the starting point leaf node    while (!pCurrentNode->IsLeaf())    {        pCurrentNode = LocatePoint(Child nodes...);    }    // Initialize the nearest object and nearest distance    CSceneObject* pNearestObject = NULL;    NearestDistance = infinity;    // Declare variables for intersection testing    float Distance;    CVector3 Point;    // Begin testing for intersections    do    {        // Test all objects of this node for intersection        for (all objects in this leaf node)        {            if (Objectintersected && Distance < NearestDistance)            {                pNearestObject   = pCurrentObject;                   NearestDistance  = Distance;                NearestPoint     = Point;            }        }        // If we have an intersection, return it        if (pNearestObject)            return pNearestObject;        // If the ray intersects the top plane        if (Direction.Y > 0)        {            // Compute the intersection point            Point = ...;            // If the intersection is within our boundaries            if (We intersect the top plane within our boundaries)            {                pCurrentNode = pCurrentNode->TopNeighbor;                while (!pCurrentNode.IsLeaf())                {                    if (Point.X > pCurrentNode->m_Center.Z)                    {                        if (Point.Z > pCurrentNode->m_Center.Z)                        {                            pCurrentNode = pCurrentNode->m_pNeighbor...                            break;                        }                        else                        {                            pCurrentNode = pCurrentNode->m_pNeighbor...                            break;                        }                    }                    else                    {                        ... Same as above                     }                }            }        }        // If the ray intersects the bottom plane        else if (Direction < 0)        {            ... Same as above        }        //        // Same as the two previous blocks for front and back, left and right planes        //        // We should never get here with proper rays, but we don't want infinite loops        return NULL;    // Repeat as long as we are still in the octree    } while (pCurrentNode);    // No match found    return NULL;}

Although this function will be quite long in implementation (easily 300 lines with the comments), it is quite easy to follow... It is also entirely iterative and very efficient.

[Edited by - Max_Payne on December 1, 2004 11:36:00 AM]

Eelco

Dec 1, 2004 at 12:20 PM

Quote:
Original post by Max_Payne
Quote:
yeah that explains why you dont want to hear of any alternatives. just tell me you dont want to hear about alternatives and ill shut up, instead of just repeating your poorly backed assertions about efficiency are more accurate than the results of someoneelses torough labor.

You should be able to back up what you say by yourself. You think other alternatives are better? Then why don't you provide us with clear reasons why.

quite simple. im trying to help you, but at the same time i have something called a real life. ive given you enough information to make the decision on your own, and i dont feel like summarizing this paper because youre too lazy to look it up.

take my advice or leave it. whatever you want.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.