Oh yeah, what the heck is ROAM?

Why do you need to know whether its a left or right child?

otherwise yes, elegant recursive solutions often result in more work being done than their iterative counter parts, which renders the recursive solution useless.
When that''s not the case, the recursion just takes a little longer.

When recursiving a tree, you need to call the recurse function for each node. The logrithmically deepening actually unrelated (contrary to what i said earlier)

its the difference between loop overhead & function call overhead per node.

The more nodes it''s used on, the worse the recursion becomes; as observed by the factorial times given by Byondo.

...
I don''t think you can transverse a non-thread (no parent or next pointers) tree without recursion (hence a stack).


...
If I were implementing ROAM I''d probably use recursion first and then make an iterative version.

How often do you ROAM the terrain? Do you build a bunch of terrains (like MIP) or ROAM every frame, or just once in a while?

ROAM == Realtime Optimally Adapting Meshes

used for making landscapes with dynamic LOD and were large flat areas use fewer triangles than areas with lots of "height-detail" (kinda..

Look it up...

Try a distributed raytracer with iteration. You''re going to have quite a handful there. And your maintenance of that handful is going to cost you CPU cycles.

Challenge: Demonstrate the savings by using iteration.

if you''re ray tracing, your not in real-time

upload your ray tracer to your web site gimme a url to it, and I''ll see how hard it would be to make iterative version.

going from a recursive FFT to an iterative FFT is really really hard, if its that hard i''m not going to do it :p if its easier than that I''ll think about it.

quote: Original post by Magmai Kai Holmlor

if you''re ray tracing, your not in real-time

upload your ray tracer to your web site gimme a url to it, and I''ll see how hard it would be to make iterative version.

going from a recursive FFT to an iterative FFT is really really hard, if its that hard i''m not going to do it :p if its easier than that I''ll think about it.

Realtime has nothing to do with it. Speed has everything to do it. The idea is, some hypothetical person is developing a distributed raytracer and wants as much speed as possible. The solution is obviously recursive, yet the poor individual has been possibly persuaded to believe otherwise from reading this thread.

The mathematics are not relevant to the question of implementation. The structure is. The structure of the ray tree is not known in advance, but is built as the rays are traced. A parent ray is fired, and contains perhaps 100 bytes of data. Each parent ray may then spawn from zero to say, 64 child rays. Each of these child rays may spawn even more rays, but probably statistically much less than the 64. Each of those child rays may spawn some child rays, but probably very few.

The calculated value of each child ray is averaged with each of its siblings and added to the value of the parent ray.

What''s the real question here:

A) There exists one iterative algorithm more efficient than it''s recursive implementation?
B) There exists x iterative algorithms more efficient than their recursive implementations?
C) All iterative algorithms are more efficient than their recursive implementations?

At this point, I think it is agreed that A is trivial and C is ridiculous; what intelligent discussion can result from the argument about the correct value of x?

c is true

What does that neccessitate recursion?
Thread the tree.

convince me that

CurrentNode = CurrentNode->Child[j];
...
CurrentNode = CurrentNode->Parent->Child[j+1];

is not better than

call RayTrace(CurrentNode->Child[j], ...);


...
How many total nodes are there in the tree?
Multiple that by 0.142 and that how many Hz you lose using recursion vs iteration.

So if there's only 100,000 nodes to process you won't notice the difference.

With ROAM you do it often, perhaps every frame, so you lose that many Hz each frame.

I guess I'm stuck in 33MHz mind set, where 3MHz is 10%... it won't make that kind of difference anymore, but it is a place where you could optimize your code.


Edited by - Magmai Kai Holmlor on November 12, 2000 10:54:32 PM

You probably require a stack for that...

Thanks for reminding me about the html tag.

Ok, so, as I see it, if you can implement iteration, it''s perfect, do it instead of recursion.

WMiller
I''m not getting it. Could you write a sample struct?


Tia,
Adrian