Archived

This topic is now archived and is closed to further replies.

Edgeman

algroistms, which one to choose?

Recommended Posts

Hello, I have a question regarding which algroistm i should use for my terrian. I''ve heard of ROAM, CLOD, etc., but i''m not sure which one to choose! I want to make a type fps game where you will be able to walk around and such. The maps will be very large and I want to really optimize it so FPS will be decent. Any ideas on which one is ideal for what I want to do? Also, how would I go about optimzing my game so whatever is out of view is not drawn (ex: stuff behind moutains/hills)? Thank you

Share this post


Link to post
Share on other sites
The problem with most LOD algorithms is that for terrain sizes similar to those in most FPS games it can cost more than just sending everything to the card (especially when you can store the whole terrain in a static vertex buffer). If you really want LOD, the first place to start looking IMHO would be geomipmaps. These are just a series of heightmaps with progressively less detail (just like texture mipmaps, hence the name) and the further the chunk of terrain you''re drawing, the lower the resolution geomipmap you use to draw it. For example, you could have a 1024x1024, a 512x512, 256x256, etc.. versions of your heightmap. It''s fairly quick and easy to implement (compared to other LOD techniques), making it a good starting place. If it turns out that this method doesn''t cut it for what you''re after then move onto looking at stuff like ROAM.

As for not drawing stuff that is out of view, this is called occlusion culling (or perhaps hidden surface removal). As for how... google is god


Joanus D''Mentia
---------------
If nothing sticks to teflon, how do they make teflon stick to the frypan?

Share this post


Link to post
Share on other sites
I''ve written both a ROAM and a Quadtree engine, and to tell you the truth, there''s not that much difference.....

Both techniques exist to draw less polygons that are further away, without the viewer knowing it....

The idea behind each technique, is to examine each point (or a group of points) and decide whether or not it should make it into the final mesh.... You recurse down the tree and see if there are any verticies that, if not drawn, would make a noticeable difference to the viewer.....


In my experience, simplicity is key, and after writting both engines, I decided to dump my ROAM engine for simplicities sake, and alter my Quadtree one slightly....

I had the landscape divided recursively into 4 segments (each segment would have 4 smaller segments, and each smaller, etc etc)... At load time, I would recurse through the tree and for each quadrant, see what the highest peak was in that quadrant (easily done with recursion)... Then when it came time to render, I would look at the position of the camera and compare it to the highest peak value of each quadrant, if the quadrant needed to be drawn, I would recursively go through each of that quadrants quadrants and see if they needed to be drawn, and the process would repeat...

The technique worked shockingly well, and slightly faster than ROAM (it was sending more polys to the card, but spending a lot less time deciding which ones to send, therefore, it was faster, just what Edgeman was saying)....

IMHO, ROAM is a nice academic way of ensuring that only the needed polys get drawn, but in the real world, fretting over a few extra polys is rather silly.

-Mr.Oreo

Share this post


Link to post
Share on other sites
quote:
Original post by MisterOreo
IMHO, ROAM is a nice academic way of ensuring that only the needed polys get drawn, but in the real world, fretting over a few extra polys is rather silly.


somehow you forget that roam is from a time where we didnt have cards that could render a few 100 000 multitextured polys per scene with 60fps. its not academic, just outdated (or at least in need of modifications). just like occlusion culling will probably be in a while. roam is complicated, because back then youd rather spend more cpu time to relieve your slow card while today you should aim for minimum cpu usage (simple frustum culling and a crude occlusion culling).

in maybe 10 years people might look at our code and laugh about how silly it is to cull anything when the card does it much faster anyway. imagine an architecture where the card could poll infos on meshes like radius or bounding box, do the typical culling for all of them and then request only the visible meshes. doing that in specialized hardware would mean you just leave the geometry with extra info where the card can find it and dont bother. anyway, back to terrains.

my approach would look like this: geomipmaps and zgrid (just when i thought i came up with something new eberly tells me that defender 3d already used something like that in 95 *sigh*.. i guess its hard to invent something really new today *g*)

current state of it can be seen here:
http://festini.device-zero.de/downloads/dzlse.zip

lod isnt perfect yet (at least the selection of it), but if your fps type game wont have people in planes it should work quite well. else you need either a lot of memory or have to use fog ,-)

Share this post


Link to post
Share on other sites