Much better TUVM … did a google search and found …

Loose Octrees for Dynamic Raytracing, by Eric Haines

from http://www.acm.org/tog/resources/RTNews/html/rtnv14n1.html#art4

In a dynamic animation environment, one problem for ray tracers to solve is

updating the spatial ray tracing structure as quickly as possible. This is

especially true if multiprocessor machines are being used. Reinhard,

Smits, and Hansen give one solution in their work, “Dynamic Acceleration

Structures for Interactive Ray Tracing,” http://www.cs.utah.edu/~reinhard/egwr/. In this paper they insert objects

into a grid. As objects move outside the grid, they do a modulo operation for

the object’s location. So, say an object is in the rightmost grid cell, #9,

in a 10x10x10 grid. It moves outside the grid - instead of recreating the

grid, the object is moved to cell #0, but is noted as being in a “copy” of

the grid at X location 1. Another way to express it is that each grid

coordinate has a number 0-9, but think of the world as being filled with

these grids, in a repeating grid. This meta-grid is accessed with the higher

numerals of the object’s location number. Everything starts in grid #0. So 10

would mean meta-grid #1 along the axis, 20 is meta-grid #2, etc. Now when a

ray travels through a grid cell containing something outside the normal grid,

the object’s real location is also checked. If the meta-grid location does

not match the ray’s meta-grid location, the object is not actually there, so

it’s not tested. As time goes on and more objects move outside the grid, this

scheme becomes less efficient as more objects have to be tested but can never

be hit. See the paper for how the authors decide to regenerate the grid when

it becomes inefficient.

What’s clever about their scheme is that when an object moves, it is quick to

remove it from the grid and reinsert it. The grid does not have to be

regenerated. This scheme can also work with a hierarchy of grids (i.e. nested

grids). The authors note that normal octrees suffer from non-constant

insertion and deletion times, as the tree has to be traversed and an object

may get put into two or more nodes.

Thatcher Ulrich’s “loose octree” spatial partitioning scheme has some

interesting features. Meant for collision detection, it may also have

application to real-time ray tracing. The basic idea is that you make each

octree node actually enclose twice the space, in each direction, as its

location in the octree. That is, normally an octree node does not overlap its

neighbors - space is precisely partitioned. In Ulrich’s scheme, the octree

node box is extended by 1/2 in the six directions of its face. Anything

listed in this node is inside this extended box.

This makes for a less-efficient partitioning of space, but has a great

advantage for dynamic objects. As an object moves or otherwise changes, it

can be removed and inserted in the tree “instantly”. Say you want to insert

spheres into this structure. The radius of the sphere determines exactly what

level of the octree you need to insert it at. For example, if the extended

octree node at some level is, say, 12x12x12 units, then a sphere with a

radius of 3 or less must fit inside this extended node if the center of the

sphere is inside the unextended octree node. If the radius is 1.5 or less, it

can be inserted in the next octree node down (6x6x6) or further, as it must

fit there. So just knowing the sphere’s center and radius fully determines

which octree node to insert it into, without searching or bounds testing

(other than walking down the tree to the node itself).

Similarly, deletion from the octree is quick: each object exists in one and

only one octree node, which can be found immediately and so deleted from. It

might even be faster to hash the octree nodes by their level and address (as

Glassner did in his original scheme) to more quickly delete from them.

This gives at least some hope that octrees could be used in a dynamic ray

tracing system. Another nice feature of octrees is that if an object moves

outside the bounding box of the entire octree, this octree can become a

sub-node of a larger octree made on the fly that also encloses the space the

object moved to. I have to admit that the loose octree structure seems pretty

inefficient to trace rays against, but really I am just brainstorming here,

presenting a possible use for a clever, new data structure with some useful

properties. I can imagine combining loose octrees with other schemes, e.g.

also creating bounding boxes within each populated node lazily, as needed, to

further speed intersection testing.

See more about the loose octree idea at http://www.tulrich.com/geekstuff/partitioning.html, and read more about it in

the book “Game Programming Gems.” There are some optimizations I do not

mention here, like being able to sometimes push some objects one level deeper

into the octree.

[This message has been edited by pleopard (edited 02-28-2002).]