PDA

View Full Version : Octrees and Moving Objects


Tachikoma
04-24-2004, 07:30 AM
I was thinking of building a real-time 3D engine beased on octrees - mainly because it's fairly easy to implement, and useful for visibility testing, collision detection, ray intersection testing, etc. However, I also realised that managing dynamic/moving objects in octrees is a real pain. Basically you'd have to update parts of the octree in real-time when the object moves. I was wondering if there is a efficient method for doing this? The scenery will be both indoors and outdoors.

operativem
04-25-2004, 10:43 PM
I'd stay away from octrees. Far Away. 1.) The process you describe, updating the octree to move objects, is an N-squared problem. 2.) Octrees are useful for optimizing specific geometric structures, not on general content, and I think you probably want your engine to work on general content. I could go on and on --- but I won't waste your time. If I were you, I'd stick with a directed acyclic graph for your world format. Just my 2 cents.

Tachikoma
04-27-2004, 07:23 AM
That directed acyclic graph structure is similar to bounding volume hierarchies, no?

The reason why chose octrees is because it allows quick visibility testing and collision detection. How does directed acyclic graphs fare with visibility testing and collision detection? I need to read up more on this matter.

djwarder
04-27-2004, 11:44 AM
You could look at "sphere trees"? There's a good article in one of the 'Game Prog Gems' books, or you could look at these URLs ...

http://www.gamedev.net/community/forums/topic.asp?topic_id=196534

http://www.cs.tcd.ie/publications/tech-reports/reports.99/TCD-CS-1999-10.pdf

http://www.eg.org/EG/CGF/Volume14/Issue2/v14i2pp105-116_abstract.pdf

Give them a try. I'm going to use them eventually for my project, just as a sidenote!!

Dan

djwarder
04-27-2004, 11:47 AM
just checked - book its in is 'Game Programming Gems 2' (article called "Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching")

May help?

Tachikoma
04-27-2004, 12:51 PM
ha, coolness thanks for the links. :)

operativem
04-27-2004, 09:22 PM
Yes, the DAG is an object hierarchy, visibility testing is almost trivial: test each node for visibility (against the view volume) as you traverse the hierarchy. Using a hierarchy, with balanced nesting, allows you to create an optimal rendering list, as, if a parent node isn't visible, neither are any of its children (and traversal stops there.)

This is a ***far better*** solution than using an octree because it can be used to optimize any style of content, whereas octrees are good for data that conforms to a roughly cubic shape. (My opinion.) When I think about using an octree to optimize terrain or a database with roads, terrain, and architecture, it immediately seems rather ridiculous! (Just as using a BSP would seem ridiculous.)

Furthermore, unless I'm mistaken, an octree (like a BSP) requires literal subdivision of a database unless the scene geometry conforms exactly to the size parameters of the octree algorithm. This is an especially ugly problem. (My opinion.)

This, of course, says nothing about the biggest problem of all. Dynamically updating the octree requires you to solve several problems required to exponential cost algorithms. If you need to update the base of the tree, you have to update everything else that comes after it. That's probably not the sort of thing I want to think about doing just so I can move an object around. Now, with an object hierarchy, you can have complex parenting/re-parenting issues, but generally, those problems are solved by using orphans or by not re-parenting nodes. (I'll go into this more in a later post).

If I were designing/implementing a scene graph (something I've done commercially), I would not want to make scene graph design decisions based on things like collision detection since they're not really related. Collision detection is specific to the runtime application, not the database. (My opinion.) I'd rather have an extraordinarily flexible scene graph and spend more time optimizing the collision detection code.

Lastly, using an object hierarchy for your scene graph doesn't prevent you from using an octree or a BSP tree for parts of your world if necessary. I've designed systems that combine both and also use portals as well.

In the end, a flexible, well-implemented scene graph pays for itself many, many times over. I've made a few posts of late in a different thread about the importance of a flexible, well-implemented scene graph. In those posts I referenced OpenFlight (http://www.multigen.com) as an example of an extremely well-designed scene graph. Also, http://www.openscenegraph.org. Check them out.

(I am not associated with MultiGen or OpenSceneGraph in any way.)

Tachikoma
04-28-2004, 09:10 AM
Thanks for the info Operativem! :)

I'm inrerested in respresenting a mix of outdoor and indoor scenery, perhaps a mix with lots of trees and accessible buildings. I also want these objects to be potential dynamic, meaning they should be movable by destruction or by some form of collision/interaction. How suitable is this DAG/Scnene Graph strategy for such complex scenes?

operativem
04-29-2004, 01:23 AM
Yeah --- A DAG-based scene graph is completely perfect for what you describe. I believe Mario64 and San Francisco Rush 64 were built on OpenFlight, as well as numerous other N64-era titles.

If you're using a BSP however, dynamic geometry is more difficult, as the BSP has to be rebuilt, and this is also an exponential cost sort of algorithm. (For the record, I don't really like BSP trees very much either.)

Given the unbelievable rendering and CPU power available today, I'm not sure it's necessary to use a BSP tree. You can probably get away with using a combination of simpler, invisible collision geometry and bounding box collisions. (This is a common trick on many console games.)

Additionally, using a DAG with a high-degree of user control allows you to articulate parts of your model/scene in ways that an octree certainly would never allow (since the octree is in control of the scene graph when used). This is what gives you the ability to modify the scene graph in real-time, with small math.

I could spend all day extolling the benefits of using a DAG. (Actually, at one point in my life, it was my job to do just that!)

Tachikoma
04-29-2004, 04:34 AM
Once again, thanks for your input. :)

playrev
05-26-2004, 02:40 AM
Just try "Loose-Octrees", they rock! :thumbsup:

They just invalidate much of what was said against octrees....:p

google for it!

And by the way, I really would like to see what would happen to most of terrain engines without a quadtree.....:curious:

Cheers,
playREV

CGTalk Moderation
01-18-2006, 02:00 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.