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