I have an OpenGL game that renders a full 3D world. I have noticed a considerable slowdown when having a world of > 10k polygons. Here is what I do: 1. Check distance to all objects in the world. Those that are within a certain range are rendered and taken to the next stage. 2. Check which polygon vertices fall inside the view frustum. Those that do are rendered, all other are ignored. 3. Apply volumetric fog, texturing, lighting (custom pre-lighting system is used) and detail texturing. 4. Render the stuff that needs to be rendered. I get an FPS of about 30-40. It's noticeable that the game runs a bit slow when you walk around the world. I dunno which of all possible techniques is the most efficient but here are those I know exist: Display lists Vertex lists Octree Do I need any of those, will they help me? [Edited by - azjerei on January 1, 2005 4:14:59 PM]

First you need to find out if you are GPU- or CPU limited. 10K polys and 40 FPS means only 400K poly per second, which is really low. If you are using immediate mode, however, you can't expect much higher frame reates with some gfx drivers.
You can subsequently try using display lists (rendering itself should be magnitudes faster, depending on the driver), vertex arrays (could be a little faster than display lists) and VBOs (should be the fastest solution, as much as rendering goes).
Octree's and friends have little to do with the actual rendering. These are tools for scene management that are used to determine, which part of the scene is to be rendered.

OpenGL does step one for you. You should at least be using vertex arrays for models. Vertex buffer objects are an extension which allow you to load the vertex arrays into the card's high performance memory. Check them out too.

An octree can help for culling out stuff and can also speed up collision detection.

Anyway, profile your application and find out what the major slow down is. Is it rendering? If you aren't using vertex arrays or display lists probably. But it could also be your math code (like unoptimized math functions), AI, physics, or anything else. You really have to profile to know.

After re-reading your post, it's pretty obvious that you are CPU limited. A brute force distance testing each frame is a huge overhead if you have a big world with many objects (at least I hope that you do that on a per-object basis and not per-poly; otherwise I'd be very impressed if you still get 30 - 40 fps[smile]).
Depending on your scene geometry, a simple quadtree might be enough to speed up step 1) significantly.

Quote:Original post by Puzzler183
OpenGL does step one for you.

Not really. It is definately not possible to get reasonable frame rates if you throw several million polys at the card each frame, even if only a few ten thousand are actually being rendered especially in IM.

Quote:A brute force distance testing each frame is a huge overhead if you have a big world with many objects

Yes, but I have not clue as to how to limit the amount of drawn objects (yes, we have many objects, each with many polys). Is it wise to actually render offscreen objects for the sake of keeping track of NPCs and projectiles?

Quote:Original post by azjerei

Quote:A brute force distance testing each frame is a huge overhead if you have a big world with many objects

Yes, but I have not clue as to how to limit the amount of drawn objects (yes, we have many objects, each with many polys). Is it wise to actually render offscreen objects for the sake of keeping track of NPCs and projectiles?

As you have no experience with space partitioning techniques, I'd suggest taking a step-by-step approach (you may hum this New Kids On The Block-song now [grin]).

First devide your world into sectors of reasonable size. For all objets in the world, assign a sector id to them. If the camera moves, find out which sector it is in and render all objects in that sector. Next check the 6 neighbouring sectors and render each if the viewing frustum crosses one of their borders.
This reduces the overhead significantly as you only test at the most 3 sectors (since the camera is facing in one direction only and thus never more than 3 adjacent sectors can be crossed by the frustum provided their size is well chosen). You can place the objects in the rendered sectors in a rendering queue.

Step 1) Implement that and render the object list. Observe the frame rate.

Step 2)
Once you got that working, take all the objects in the render queue you obtained from step 1) and test if their bounding sphere is inside the viewing frustum (e.g. squared distance between bounding sphere centre and one of the frustum egdes is less than squared bounding sphere radius → at most 6 tests per object). Remove all objects that are outside the frustum from the render queue.
Don't care about single polys!

Step 3)
After successfull implementation of step 2) apply front to back sorting to the render queue. Sub-sort the objects by texture/material. Render the final queue.

Step 4a)
Your high level render optimisation is nearly completed. You can now apply LOD techniques to the objects if you want/need to.

Step 4b)
Replace step 1) with a more sophisticated technique like quadtrees for outdoor scenes or BSP/ABT/Loose Octrees for indoor or mixed scenes.

The above is high level optimisation. The actual rendering performance can be improved by leaving IM and using:

a) Display lists.
b) vertex arrays.
c) VBOs.

Good luck with that and keep asking if something is unclear [smile]
Pat.

Practical algorithms are

1) Octree
2) Portals
3) Hybrid solutions

(google, google, google...:)


Your polygon-vertices against view frustum test is useless because

1) You test too much vertices and this can be slower that send them directly to OpenGL
2) OpenGL repeats (faster) what you have done :) so you do the same thing twice!
3) Your test is inaccurate because you can have vertices outside view frustum but the polygon is visible...you should discard vertices that lies outside the same plane but this is too conservative and slow!

And display lists, vertex array are optimizations...space subdivision and polygon set selection are the core.

try to google with

Octree, bsp, portals, sectors, polygon reduction, polygon culling,....