Archived

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

large outdoor scene (octrees, culling?)

This topic is 5015 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all. I'm working on creating an outdoor scene; currently I'm using vertex arrays and GL_TRIANGLE_STRIPs, and this works well, except when the terrain gets too large. (Well, it's kind of a weird situation, so I guess I'll ask 2 questions...) 1. When I'm rendering just a flat gl_triangle_strip by itself that's 200x200 verts, it renders about 85FPS when colored. However, when rendering in wireframe, that drops down to about 26FPS. Is there a reason why? 2. My main question: Since I'm going to be wanting a larger landscape than this, I'm been looking into using Octrees. I think I have a good understanding of how they're used and why they're used, I have a couple fuzzy spots. (a) What steps would I take to put my Vertex Arrays into an Octree? How would I render them? Currently, I have an Index of vertices, and I call:
 
glDrawElements(GL_TRIANGLE_STRIP, numberOfIndices, GL_UNSIGNED_SHORT, indices);
 
I guess I'm just not certain on how I go about placing all my polys into the octree and having the octree handle the rest. I read the tutorials on gametutorials.com, and it looks like he ends up rendering via glVertex3f() calls using GL_TRIANGLES. I would prefer to use triangle_strips and glDrawElements() since this is already implemented... Can anybody give me some pointers or steer me in the right direction? BTW, for the first question... I have an Athlon 1.4GhZ, 512MB RAM, and an nVidia TI 4200 w/ 128M, WinXP. [edited by - ichor on March 24, 2004 5:01:15 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Modern graphics cards can''t draw lines (wireframe), they have to emulate them by drawing 2 triangles per line and that''s why it''s slower.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Modern graphics cards can''t draw lines (wireframe), they have to emulate them by drawing 2 triangles per line and that''s why it''s slower.


Actuarly there is no real speed difference if you would render a line or just use two triangles.
It''s certanly not the cause of the 60FPS drop, you did something else, something bad.
Perhaps something that would force it to fall back to software mode.

---------------------------------
For an overdose of l33tness, flashbang.nu

Share this post


Link to post
Share on other sites
Sorry ''bout the CODE vs code tags...fixed now.

quote:

you did something else, something bad.
Perhaps something that would force it to fall back to software mode.



Well, the code is basically a 1-liner... If it needs to go to Wireframe mode and it isn''t already, then:


glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);


otherwise,

glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);



Anybody have help as far as the octree/culling goes? Thanks!

Share this post


Link to post
Share on other sites
so the general algorithm for adding things to an octree is to pre-define some sort of optimal number of polygons per leaf node. this is kind of subjective to start with and you'll end up tuning that later as you find that perhaps collision is too slow or you're making too many node checks.

but basically start with one big box whose boundaries are found by scanning through your scene and picking out the highest x y & z coords of the objects thereing. you can performance boost this by having your level editor save this out for you so you don't have to search everything. or perhaps just search the bounds of your terrain and your highest objects or something

anyway, start adding polys to this box. if you surpass the max number of polys, split that box into 8 axis-aligned boxes (octtree) or 4 axis aligned boxes (quadtree). at that point you should probably take what's already in the box and split it amongst the sub-divisions so you'll end up with all your geometry in a leaf node. once you get to this point it's just a recursive algorithm where you make the same checks with each sub box and sub-divide them as necessary.

once you get to the end and all your polys are sitting in leaf nodes you'll want to go through each leaf node and take all the objects you've divided up and build one vertex array for each node box. that way you can draw an entire leaf node with just one gl call.

the difficult things are splitting objects. i found it easiest to skip the whole splitting triangles part and just throwing triangles that cross node bounds into one box or the other. this works find as long as your triangles are relatively small. if they are big you'll have to split them. splitting triangles is annoying b/c there are several edge cases you need to consider. it's possible, for instance to have a single triangle that spans multiple leaf nodes. hassle hassle.

anyway, check out the articles & resources section of this site. there are a bunch of good quadtree/octtree articles that supply more detailed explainations of the general algorithm.


the algorithm for using an octtree to do the culling is really easy. you just recurse your octtree/quadtree from root to leaf and if a current node intersects the view frustum, and if it's a leaf node, draw it. if it's not a leaf node recurse it's children and apply the same test. if it doesn't intersect just return from the function without testing the children.

-me

[edited by - Palidine on March 24, 2004 5:29:50 PM]

Share this post


Link to post
Share on other sites
answer to your speed drop.

When you're rendering filled polygons a lot of the vertices are thrown out very quickly because they are already obscured. With wirerame mode less vertices are obscured, resulting in OpenGl having to rasterise vertices that would have previously been skipped.

Alternative to what sounds like a brute force algorithm is to look into using a level of detail system. If your going to use quad trees anyway you may get some performance gain from a rottger like algorithm.

It is possible to still use vertex arrays, through the use of a little larger memory overhead. what you can do is:

1. every few frames (or every frame if you prefer) traverse the quad tree and copy all triangles for rendering into a second buffer (a preallocated pool).


2. throw this second buffer at opengl as a vertex array.

or you could just create a new list of indices and send them to opengl.

Another method I heard some one musing over was to have a quad tree of display lists (or vertex arrays), each level of the tree had increasingly high Level of detail. carefully designed the different patches mesh perfectly with out seams, I would think the performance would be quite resonable.

Good Luck.

Alex

[edited by - aleks_1661 on March 24, 2004 10:03:28 PM]

Share this post


Link to post
Share on other sites