Jump to content
  • Advertisement

Archived

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

Hybrid

Octree Questions

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

I read the other thread entitled 'Combining Octrees and BSP trees... is it possible?' and from what Yann said - Octrees are the way to go instead of BSP. They seem easier to implement (which is good for a relative beginner like me) and can handle dynamic objects. So I hope to use Octrees in my scene/demo. However I have a few questions regarding the optimum way to go about them. 1) For the static data, it may contain different objects within the same leaf, and they may have different material properties. I read somewhere in this forum, that vertex arrays could be contained within the leaf for quick(er) rendering, but I guess different materials/textures sort of makes that awkward as you can't have one array. Am I right about that? 2) For static objects, is it always best to split polygons that cross the partioning planes of nodes (e.g. an object that can be contained in 2+ different nodes at the same time)? Or is it best to just store duplicates of the actual object. Now for dynamic objects, where my main confusion lies... 3) When I create my initial octree from the static geometry, some octree nodes may be completely empty at a high level, so it may not be partitioned to the full depth/level. But when dealing with dynamic objects (e.g. particle system) hundreds of dynamic objects may enter that empty node, so surely it would be an advantage to partition that node to the full level anyway, even if empty? So that when dynamic objects do move into that empty space they can be put in smaller nodes immediately? 4) Overall, isn't sorting and actually moving dynamic objects from node to node a slow process? Especially in a particle system? Are there any optimisations? Perhaps if I ask more questions this could become one of those good reference threads P.S. For collision detection, I'll either use a completely separate octree (with less polygons/convex hulls for faster collision detection) or just add the collision objects to the same octree but with separate pointers and perform collision detection on them. Oh, and this is in OpenGL if that helps with the rendering questions (vertex arrays etc..) [edited by - Hybrid on February 6, 2003 9:32:33 PM] [edited by - Hybrid on February 6, 2003 9:33:23 PM]

Share this post


Link to post
Share on other sites
Advertisement
I''ll try to give some answers:

1) If you have different shader states, for example, simple texture binds in every node, you should store every node that is thought to be visible. Before you actually render the scene, you organize all the geometry so that you change the states as little as possible.

2) You''ll have to compare the results of splitting and duplication to see what''s best for you. You could also look into octrees with loose boxes (boxes that change their size a lil'' to fit polygon-masses better).

3) Paritioning the full octree can be very mem-consuming. Also, there is no full level in octrees, the depth depends heavily on how the geometry looks like. You could add/remove nodes on the fly that only contain particles or alike. Depending on how advanced the particles are, perhaps you only need to add one big node in an empty space.

4) You shouldn''t have particles, where you don''t see them. Particles don''t affect more than the visual, affection is mostly handled by simpler ways (boxes, spheres etc). Therefore, you shouldn''t have particles 1 mile away, since they aren''t making anything better anyway.

I bet there''s something I forgot, but this post is big ''nuff

Share this post


Link to post
Share on other sites
okay, thanks. I did have a look at loose octrees to do away with the process of splitting polygons.

It''s mainly dynamic objects that I am concerned about. I mean people say octrees can handle dynamic objects but to me it seems like it might be a rather intensive process having to move objects from node to node a lot (perhaps every frame).

The particles in my scene are always likely to be local with most of them in view. Quantity wise, I''m looking at 500-1000+, so as you can see having to move lots of them around an octree sounds like hell for the CPU.

Share this post


Link to post
Share on other sites
I''m in same situation as you, except that I''m doing an outdoor engine. I''m not quite sure how I should go onwards from this.

I have planned on going the cube in frustum route, but I''m not so sure how the CPU can handle it. My maps are basically heightmaps, and in order for them to look decent in 800/600 resolution there has to be quite a lot of polygons and vertices involved, which could turn my whole rendering process into a trainwreck.

However, my second though was to store the abstract position of each of objects in sort of simplified octree and then pass these values from the object specifit datastructures to the renderer. However, this approach, too, has problems. First of all I think this would rape the rendering pipeline if I have to resort on calling multiple functions instead of drawing just polygons, secondly there lies problem withing interpreting the object specific data.

Now I need some octree theory, which everyone says exists, but can be found only from incomplete "lol I know this shit u don''t" articles. What I mean by incomplete, are incomplete in providing something new and only state the facts that a) there are a lot of these kinds of bs articles written b) octree is so easy to do I won''t explain it here.

Share this post


Link to post
Share on other sites
Octrees and ''loose'' octrees are explained well in the book ''Game Programming Gems'' they are relatively small articles, with not much actual code, they concentrate on the theory.

Right now, I''m thinking of having an octree for static GRAPHIC objects, and another octree for the COLLISION detection which may contain lower polgon representation of the grpahic objects to speed things up. But its really figuring out how dyanmic objects fit into this thats the problem.

Share this post


Link to post
Share on other sites
quote:

It''s mainly dynamic objects that I am concerned about. I mean people say octrees can handle dynamic objects but to me it seems like it might be a rather intensive process having to move objects from node to node a lot (perhaps every frame).


Octrees are not very well suited for dynamic geometry, as the reinsertion process can be expensive. They are useful for static geometry. But that''s just the same with BSPs. You have different options: either use a totally different structure, or, if you want to stay with octrees, then treat your dynamic objects separately, as separate AABBs. When they move, you can reinsert the object using different techniques. It''s always a trade-off between the quality of the localization and the performance of the insertion algorithm.

About octree articles: IIRC, there was a nice introducory article about octrees on Gamasutra. Just check their programming article section (you need membership, but it''s free).

Share this post


Link to post
Share on other sites
quote:
Original post by Yann L
You have different options: either use a totally different structure *snip*

What other structures are there that allow for good spatial division and dynamic objects. I mean if BSP''s, Octree''s and Quadtree''s are not well suited then what is? Preferably the structure should be EASY to code

Share this post


Link to post
Share on other sites
There are a lot of other stuctures: raw Kd-trees, OBB trees, ABTs, spherical trees, and many more. Some of them are pretty well suited for dynamic geometry, but it ultimately depends on the properties of your scene geometry. Choosing a good hierarchical representation for a 3D engine is a hard, yet crucial decision. It will have a very large impact on the final performance characteristics of your engine.

Unfortunately, pretty much all the smart and fast structures are not really easy to code. I''d say, the most simple is the axis aligned fixed grid Kd family: quadtrees, octrees. You should start with those, and go further once you know exactly what you need.

Share this post


Link to post
Share on other sites
Let me tell you how I would handle this:

(keep in mind that with actual 3D hw it is often faster to draw a bit more geometry than needed, than, doing more accurate culling which will speed up the 3D hw but slower the CPU.
It is a question of balancing CPU and GPU ressources.


- I would use a Sector-Portal/octree system where each sector is in fact an octree.

- The octree I would use is a bit special since it NEVER split polygons at building time.

More explanations on my PARTICULAR octree technique (don''t know if someone has used this technique before)

For static geometry :
Each triangle get stored in the smallest (deepest) octree node in which it entirely fit. (So we don''t need splitting)
This result in an octree where leaf nodes AND internal nodes may contain geometry.

For moving geometry (say characters, vehicles, etc):
That''s the same as above expect you don''t process geometry on a per triangle basis but a per mesh basis.
Instead: you store a pointer (or ID) of your mesh in the deepest octree node which fully contain the mesh (or the mesh''s bounding box for faster determination)


When a object move:
- while(the object can''t fit anymore in the node it is actually in) : move it to the parent node (just a pointer or ID copying, not much overhead). If we are in the root node and the mesh can''t fit neither, then consider moving it to an other sector (You should be intersecting a portal)


For optimal state changes, I''m also trying to find a GOOD way to handle that, so I won''t be very helpful here. Just keep in mind that building a render list each frame is not a good idea because of memory alloc/dealloc which is very slow to do each frame. (expect if you use some kind of pool of preallocated structures)





For the particle system I wouldn''t cull it on a per particle bais, but I would compute a dynamic bounding box of the whole particle system and treat it like any other moving geometry (see above)


Share this post


Link to post
Share on other sites
I intend to do quite the same as you, Bender77. My octree scheme will be, in fact, a single, world-sized octree where objects (not polygons) get inserted.

- Insertion from root, based on object radius. Object stays in the smaller box it can fit in.

- Dynamic objects are moved to parent object, which in turn moves them elsewhere if they don''t fit, or fit too loosely(recursively).

- No portals, instead a precompiled visibility set : each node keeps track of nodes that are invisible from there, these nodes are simply ignored at render time

- Octree node factory: The engine always keeps close at hand a set of 32 readily available nodes. It allocates new ones on it''s spare time, when it can afford memory allocation.

ToohrVyk
-------------
Extatica - a free 3d game engine
Available soon!
Click here to learn more

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!