From: mvale…@esoterica.pt (Mario Francisco Valente)
Subject: Re: Octrees
Date: 1995/11/18
Message-ID: #1/1
X-Deja-AN: 119646778
references:
organization: Esoterica, Portugal
newsgroups: comp.graphics.algorithms,rec.games.programmer
John McCarthy (r…@jecalpha.ka.sub.org) wrote:
: : Space looks like: Tree looks like:
: : +——————-+ _____________
: : | Quad 1 | Quad 2 | / | | \
: Ok, we could do this, and I understand what an octree is. But what good is it?
: Why is it important to have only 1 vertex in a section, and how can this
: informtation be used for better/faster rendering/plotting/whatever?
OK, lets see if I remember my work on octrees :-)
As said before an octree is a data structure built to represent
reality. Now this “reality” is in fact a cube, enveloping your universe.
The octree root node represents this universe and has 8 children nodes.
Each node represents a 3D quarter of the cube ( you divide each dimension
of the cube in half, as represented in previous BUAG that I’m not going
to repat :-)
In turn each of these nodes has 8 chidlren representing its own subdivision
in 8 parts. You repeat this until you get to the pixel level ( until you’ve
subdivided cubes so much that their dimension [ you’ll have to keep track
of the universe dimension and the number of subdivisions ] is now the
dimension of a pixel [ you choose what a pixel represents, 1 milimeter or
1 km ] ).
What good is it ?
Well, if you render the octree you’ll only have to plot the REALLY
needed pixels. Lets suppose that in your universe there’s only a ship
in the left-backside-superior quadrant/octant. You eliminate 7/8 of
the space ( and volume of pixels ) you’ll have to render.
Furthermore, if this is done in the right way ( meaning, from front to
back and with some testing ) you can eliminate lots of other pixels because
they’re hidden pixels.
Also furthermore ( and this is the area where I’ve done some work )
you can use the recursive rendering process to introduce a fractal
process, thereby incorporating fractal textures into the process with
no loss of speed.
The need to have a vertex in each section means that when you reach
the pixel level subdividing cubes you have to be able to determine
if the pixel is a filled or not. Notice that starting in the upper
level cubes the state of a cube can be 1 of 3: empty ( a chunk that
you can ignore when rendering ), filled ( a chunk you can ignore
because at the pixel level all the pixels will fill this area ) or
crossed ( a cube you’ll have to subdivide to get finer “grain” ).
Let me just add ( to finish the rather long post ) that I used
octrees in my work together with a different form of representing
objects: no CSG, vertex lists, etc; I used hyperplanes ( read geometric
mathematical definitions of surfaces ) to define obejcts; a cube for
example is defined by the intersection of 6 hyperplanes;; the advantage
of this is that you get the normal for each pixel easily ( its in the
plane’s equation ) thereby being able to do lighting easily, without
any convoluted calculations.
Thats it. Hope I was able to put it through.
C U!
Mario Valente
—
Et in Arcadia Ego
