Archived

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

Large scenes + Octrees

This topic is 6019 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

This topic touches on octrees and scene graphics system. I''v not used octrees before but now have read some articles and searched topics and I think I know it quite well. Here I describe what I think about scene. Someone might take this as a small tutorial but I hope to get also replies to my questions. My scene is a big area that contains all. Scene is divided into portals. Portals might be for example qubic areas. Scene is divided into portals just to handle smaller areas as scene might be very HUGE. Also portals that are not near could be save to disk and load when they are needed so that only few surrounding portals are handled in memory. Each portal has its own vertices and faces. Portals are organised by octree algorithm. First octre node contains the whole portal. This node is divided into 8 pieces (the cube is divided into 8 little cubes). Faces inside each little cube is added to corresponding child node. Each node is divided into smaller and smaller cubes until we reach decided minimum cube size. Here comes the part I''v not yet decided wich way to go. Where to place all vertex and face data in a portal? Suggestion is that I render using indexed trianglelists. Here are possibilities: 1. All faces & vertices are placed in the portal. Then tail nodes just include array of faceindex for each face that belongs to the node. Weakness is that it''s hard to render. 2. Same as 1 but each tailnode includes faces instead of faceindices. 3. Each tailnode has its own vertex & face buffers. This is very good for rendering but has larger memory usage. 4. I''m totally on the wrong track. I would prefer the third method. Or the fourth? It should be API independent because I''m writing wrapper. That all was for static scene. But how to work with dynamic objects? Articles about octrees used to calc bounding box for nodes. I thought that spheres could be also good. It requires just a centerpoint and radius. It''s very simple to check how far the sphere is or if ray intersects a sphere!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hey,

Can''t tell you anything about octrees, cause I never dit them. Although I did quadtrees, which rock

About the bounding boxes:
Why boundingboxes? The cool thing about them is, that you can
calculate so-called outcodes.

Whit these you can optimize for example your clipping routines.

So with boxes, you know not only if it is in or out, but also where it is in or out!

Gr,
BoRReL

Share this post


Link to post
Share on other sites
It depends on the nature of the polygon data in the octree. If all the trianges belong to the same mesh (same rendering mode: texture, lighting, etc...), the the first one is the best way to go. But instead of rendering each tailnode one at a time, you accumulate a list of faces to render during your tree-traversal, then send them down the pipe all at once. This has the cool advantage of being able to filter out duplicate faces (in case your octree doesn''t split polygons).

If your portal has multiple meshes, then you can take the same approach, only you have to accumulate multiple face lists, and also store which mesh each face in a tailnode belongs to.

This, of course, is assuming static data. I''ll just go on this assumption for now, because dynamic octrees take a bit more effort

Morbo

Share this post


Link to post
Share on other sites
Are quadtrees same as octrees but in 2d? That might be good for large flat scenes. Still if using octree for large flat scene, result is that boxes are not cubes, instead very flat boxes. Not very good I think?
Obviously bounding box has its advantages over sphere.

More over the facedata. I looked source of a 3d engine with octrees (Little3d or something). Interesting was that All faces had three vertices. I was totally disappointed. It''s a waste of memory and also slow! However, it''s very very very simple that way. But I have so far used indexed triangle lists. They are faster if triangles share vertices and that is the case often for me.

Morbo: I got quite a well what you wrote but I''m also a little embarrassed. Duplicate faces, I don''t have them, so I don''t need to filter them out?? Or did I understood wrong?

Dynamic octrees are still mysteries for me. But assuming I make a cargame, the only dynamic objects are cars. They could simply be implemented withoud octrees. Jus a mesh inside a bounding box.

Share this post


Link to post
Share on other sites
Yup, quadtrees are just flat octrees. They are indeed better for flat scenes than octrees. IIRC, Tribes 2 uses quadtrees for terrain.

Depending on how you build your octree, you can end up with duplicate faces. This can happen if instead of splitting faces that cross node boundaries, you store the duplicate the face and store it in both nodes. This causes overdraw but saves adding a bunch of split polygons to the scene. The same issue comes up with other spacial structures, like BSP trees. In Quake 3 they did this because the cost of overdraw was less than splitting the faces.

And don''t worry about the dynamic part, I was being flipant. I don''t think I''ve ever seen an dynamic octree implemented. Maybe something for a boring weekend...or not.

Share this post


Link to post
Share on other sites
Just my 2 cents.

Instead of breaking up my polygons that touch more than 1 node of my octree, I keep a pointer to the polygon in all nodes that it touches. I also have a flag on the polygon which is set when the polygon is drawn for the first time, then when it is encountered again by the next node which references that polygon it checks the flag and if it was already drawn it does not draw it again (or literally in my case, it does not add it to my dynamically created array of indices). Costs a few ticks but if you have lots of large variant polygons it is cheaper than clipping or overdrawing (atleast in my testing).

Of course this means resetting the flag on alot of polygons each frame, but if you are creative it shouldn''t cost you much (hint: let the octree help you).

Seeya,
Krippy

Share this post


Link to post
Share on other sites
Thank you for any cents and hints! Things are getting brighter and brighter. I''m gradually getting to point to start implementing my octree''ed scene.

Someone has octree that has fixed size cubes (all little eight cubes inside a larger cube are the same size) and I found also that someone used boxes that are sized to fit all faces inside it. The second one doesn''t have duplicate faces. But I''m still considering the first way and use extra flag as Krippy explained.

How do you send rendered triangles to renderer. I ended up to have indexed trianglelists but send triangles separately to renderer, since indexed triangles are not cheap to render if only few of the triangles are being rendered. Anyone (dis)agree?

Share this post


Link to post
Share on other sites
That''s true. So instead of sending the triangles off one at a time, accumulate a list of indices (or vertices, whichever works for you) and send them off all at once, after the tree traversal. This is a little memory intensive, but is much better than flooding the pipeline with a bunch of primitives.

Share this post


Link to post
Share on other sites