RE: [Algorithms] ROAM

[Discoe, B. <ben...@in...>]

> From: Johan Hammes [mailto:jh...@mw...]
> Has anyone seen a decent implementation of ROAM?

That depends on whether you mean implementations of the *full* ROAM
algorithm.  There have been many variations, the most popular of which omit
the split-and-merge queues (split-only ROAM), which tends to be a win in
both code complexity and speed.

To the best of my knowledge, there has not been a fast, publicly available
*full* implementation.

Split-only, on the other hand, has plenty very fast implementations, as
listed at http://vterrain.org/LOD/implementations.html

..including the overall fastest known CLOD implementation to date,
SMTerrain, which is a split-only ROAM approach.

> What is the amount of cpu time used by the algorithm per frame
> for a standard scene with about 3000 triangles in the view?

I'm afraid it's not as simple as that.  The answer will vary by CPU speed,
memory speed, memory latency, bus speed, card speed, camera location, camera
movement, and cache size!  Believe me, i have done tests in regards to most
of these factors, and an algorithm which uses negligible time in one
configuration can significantly affect framerate in another.

The best advice is: implement the application you want, use the scenery you
want, run it on the hardware you're targeting, set up some speed test based
on expected camera movement, and THEN compare speed and visual quality
between the terrain LOD algorithms you are comparing.

> The first publication on roam was horribly slow

Well a publication is just words, surely it was not slow, except it was hard
to read :)
If you mean the first full ROAM implementations, yes they there were
reportedly generally slow by those who did them.

-Ben
http://vterrain.org/