# Dynamic Octrees

Is it viable to make an Dynamic octree?
The octree would hold everything, not only to allow us to know what is visible and whats not, but also to detect colisions!

What would be the best way to do it?

Lemme explain better
Imagine we have 100.000 objects, how would anyone do colision detection?

The explanation is very simple.You make a quadtree instead of octree and you subdivide untill there is only one object in each leaf.Then you start the check from the root in which leaf the camera is and test for collision only the object in the leaf and the “invader”!

There was an interesting article by Ratcliff, “Sphere Tree Culling”, on Games Programming Gems II. Seems to work all right for fast dynamic object culling.

The advantage of this is that it naturally groups the objects into clusters, so if you do dynamic collision detection, it’s quite useful. And the algorithm applies not only for pairwise collision tests, but also for ray-tracing and frustum culling.

There is a simpler algorithm, wich works well for up to say, 1,000 objects. You have 3 lists, one for the x axis, one for the y axis, one for the z axis. You store references to those objects on the lists, by sorting them by their corresponding span on the axis.

<code>

x axis …AAAAAAAAAAAAAAAA…
…BBBBBBBBBBBBB…

y axis …AAAAAAAAAA…
…BBBBBBBBBBBBB…

z axis …AAAAAAAAAA…
…BBBBBBBB…
</code>

the AAAAAAA on axis x corresponds to the range of bounding box of object A along the axis X.

the BBBBBBB on axis x corresponds to the range of the bounding box of object B along the axis X.

on axis X, A and B intersect, so we need to check if the spans on axis Y and Z intersect. They do on Y, but not on Z. So the objects bounding boxes are separated, and you don’t test collision between objects.

By sorting the spans by their min values along each axis, you can quickly reject objects that are separated. This works particularly well for objects of roughly the same size. If you want, you can do the test only in 2D or even 1D. Also, because you move objects slightly every frame, and their bounding boxes varies little between frames, it’s easy re-sort the array everytime an object moves. You just move up or down the span node in the list.

Unfortunatly, I havent found anything on “Sphere Tree Culling” nor about Dynamic Octrees/Quadtree’s.

My problem is, lets say I have over 100000 objects or so, and some may be static (never moves) and there are the non-static. I started thinking that it could be more easy to make a normal octree for the static, and for the others just make a linked list or “zone” them somehow. This way, I could recurse trough the octree to see test colision with the static objects near my moveble object. After that i would loop thourgh the “zoned” lists of the non-static to see if they are colliding.

Does anyone see any flaw, or knows how to speed it up? or better process?

you need to have a look at the book Game Programming gems II to find out about dynamic sphere tree culling. Because it’s in the (very expensive) book, I doubt you’ll find any free material concerning it on the net.

Yeah, you can build an octree based on the static objects, and just link the areas of the octree to the list of mobiles that overlap them.

I had a friend who research (like at PhD levels, eek!)on autonomous agents, which involves 10,000s agents roaming a city. He uses a fast delaunay triangulation to quickly find the nearest neighbours, to move them about, and to model walls and static features. The algo works in 2D. He also uses the static triangulation for A* A.I. algorithm, and path planning.

If you’re using 100,000 objects (jesus!), many of them being static, it’s always gonna be a problem finding a capable collision algorithm

also, have a look at
http://www.acm.org/tog/resources/RTNews/html/rtnv14n1.html

talking about loose octrees. If you don’t mind wasting memory.

it’s pretty damn quick, no allocation, no tree trasversal either to insert an object, it’s all worked out from the object’s position and radius.

Basically, the octree is a 3D mipmap. You insert an object in the appropriate map where the radius of the object fits 2 ‘pixels’ (or nodes) at most, and you insert object in the map by the object’s centre position.

To test for culling or collision detection, you have to consider that the node the object is in has double the size (thus overlapping half of the neighbouring nodes).

That allows for an object to cover only one node at all time. Also finding the right node to store the object is trivial.

The problem is, it’s quite hungry for memory for a naive impementation. Say you want 64 ‘mipmaps’. that’s 646464 + 323232 + 16x16x16 + 8x8x8 + 4x4x4 + 2x2x2 + 1 = 300, 000 cells (so either 600k if you store 16 bits indices, or 1.2 meg if you store pointers to lists).