Hello!
I’ve built a scene using an octree, which is pre-calculated at the beginning. Every object in the scene were static but now I want to add some moving objects. How can I do it keeping them inside the octree? Or is it better to manage them outside the octree?
Do you know any link about that?
Any idea will be welcom. 
I know it isn’t an OpenGL question but I thought you could give me some hints 
Thanks!
-nemesis-
Originally posted by nemesis:
I know it isn’t an OpenGL question but I thought you could give me some hints
Something is quite wrong with this sentence…
Hints?
Loose Octree.
Game Programming Gems 1.
www.gamedev.net
www.flipcode.com
Sorry, I meant clues…
I’m not english, as you may have guessed 
Thank you, richardve, for these links but I already knew them. I also tried with google but with no success…
Could you give me any more specific link?
-nemesis-
[This message has been edited by nemesis (edited 02-27-2002).]
Originally posted by nemesis:
Sorry, I meant clues…
Ah, you mean clue as in code?
I’m not english, as you may have guessed
I’m not English either, but that’s not what I was trying to tell you…
Could you give me any more specific link?
You mean: Could you spoonfeed me?
http://www.satori.org/gamegems/files.htm
http://www.google.com/search?q=loose+octree&hl=xx-elmer (first link)
You mean: Could you spoonfeed me?
Of course not!!
OK, I’ll rewrite the question:
Do you have any experience in what I’m talking about* and, therefore, could you give me some advice?
Links may also help but I’m more interested in your ideas…
-nemesis-
Try inserting them as seperate meshes into the octree (don’t use meshtris for octree construction). Then find out if the octree-node that contains the mesh is visible.
If you necessarily have to actually insert the objects polygons into the octree I can only recommend loose octree’s as described above.
An expert on these data structures I’m NOT however, I have successfully implemented octress and quadtrees for processing huge volumes of terrain contour/line segment data and terrain elevation/face data (ref http://www.magnacom-inc.com/pleopard/Gallery/DGNView5Snaps/ ). I started looking into the use of octrees and quadtrees because I found numerous references on the internet that claimed they were ideally suited for STATIC NON-CHANGING geometries. One reference (http://www.gamasutra.com/features/19970801/octree.htm) claims that “Although primarily used in static environments, they can also be used in dynamic environments with a few modifications”. I have no clue what those “few modifications” are however, you might be able to find some good search keywords from this article that will help you find more helpful info.
Good luck!
[This message has been edited by pleopard (edited 02-28-2002).]
Originally posted by pleopard:
they can also be used in dynamic environments with a few modifications". I have no clue what those “few modifications” are however
“Octree with a few modifications” aka “Loose Octree”
Originally posted by nemesis:
[b]Do you have any experience in what I’m talking about* and, therefore, could you give me some advice?
- remember… moving objects inside an octree.[/b]
I’ve been experimenting with Loose Octrees and you can have perfectly dynamic worlds with Loose Octrees.
Loose Octrees Are Great (and a bit more expensive (memory)).
Better?
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).]
Yeah, better, richardve.
Thank you all for your links and advices.
I’ll read all that info about that famous Ulrich’s “loose octree”.
-nemesis-