sanders@osiris.cso.uiuc.edu (07/27/88)
pardon my ignorance, but what is an octree? ---------------------------------------------------------------------- Susan Sanders Lady Ghita Alessia USA CERL Barony of Wurm Wald, Exchequer University of Illinois Middle Kingdom "Evolution Police: Natural Selection Division"
leather@osiris.cso.uiuc.edu (07/29/88)
> /* Written 12:21 pm Jul 26, 1988 by sanders@osiris.cso.uiuc.edu in osiris.cso.uiuc.edu:comp.graphics */ > pardon my ignorance, but what is an octree? > > ---------------------------------------------------------------------- > Susan Sanders Lady Ghita Alessia > USA CERL Barony of Wurm Wald, Exchequer > University of Illinois Middle Kingdom A quote from COMPUTER GRAPHICS by Donald Hearn (Dept. of C.S., University/Illinois) and M. Pauline Baker (Dept. of C.S., Western Illinois University) PRENTICE-HALL, INC., Englewood Cliffs, New Jersey 07632 1986 page 215: -------------------------------------------------------------------------------- 10-6 Octrees Heirarchical tree structures, called octrees, are used to represent solid objects in some graphics systems. The tree structure is organized sot that each node corresponds to a region of three- dimensional space. This representation for solods takes advantage of spatial coherence to reduce storage requirements for three- dimensional objects. It also provides a convenient representation for displaying objects with hidden surfaces removed and for performing various object manipulations. The octree encoding procedure for a three-dimensional space is an extension of an encoding scheme for two-dimensional space, called quadtree encoding. Quadtrees are generated by successively dividing a two-dimensional region into quadrants. Each node in the quadtree has 4 data elements, one for each of the quadrants in the region (Fig. 10-39 <not included>). If all pixels within a quadrant have the same color (a homogeneous quadrant), the corresponding data element in the node stores that color. In addition, a flag is set in the data element to indicate that the quadrant is homogeneous. ... Otherwise the quadrant is said to be heterogeneous, and that quadrant is itself divided into quadrants (Fig. 10-40 <not included>). The corresponding data element in the new node now flags the quadrant as heterogeneous and stores the pointer to the next node in the quadtree. ... An octree encoding scheme divides regions of three-dimensional space into octants and stores eight data elements in each node of the tree (Fig. 10-42 <not included>). Individual elements of a three-dimensional space are called volume-elements, or voxels. When all voxels in an octant are of the same type, this type value is stored in the corresponding data element of the node. Empty regions of space are represented by voxel type "void." Any heterogeneous octant is sub- divided into octants, and the corresponding data element in the node points to the next node in the octree. -------------------------------------------------------------------------------- I hope this answers your question sufficiently. Any good graphics text, (this was the textbook for CS318 - Computer Graphics, Spring 87, UofI), should have a section on octrees for your further enlightenment. -------------------------------------------------------------------------------- David Leatherman Graduate Student Dept. of C.S. University of Illinois at Urbana-Champaign UUCP: leather@osiris.cso.uiuc.edu
hutch@net1.ucsd.edu (Jim Hutchison) (08/03/88)
<>
Octrees. They are what they sound like, 8 legged trees. Other than looking
like bizarre spiders, they are useful for subdividing 3-dimensional space.
You can subdivide a large box into 4 boxes on top of 4 other boxes.
This has been used to represent solid data with some heavy costs in memory
and speed (for images of "reasonable" resolution). As solids, they have
some amazing properties. You can do cut-aways and cross sections with
great facility, rotations are also quite reasonable. Guess what, this
works out well for 3-D medical imaging. You can find many of the ref's
for this type of application listed as "Voxels". Pixar came out with a
product using what looked very very much like voxels, but they had another
name. I am aware of why.
On another hand, since octrees subdivide space, you can use them as bounding
volumes for raytracing. Put you objects in the appropriate leaf, and take
a modified (similiar to anti-aliased) Bresenham walk following your ray
through the 3 space described by the model & octree.
Beyond these vague gestulations, I don't know.
/* Jim Hutchison UUCP: {dcdwest,ucbvax}!cs!net1!hutch
ARPA: JHutchison@ucsd.edu */hutch@net1.ucsd.edu (Jim Hutchison) (08/03/88)
In article <1070@ucsd.EDU> hutch@net1.UUCP (Jim Hutchison) writes: >name. I am aware of why. Oops, no I am not aware of why (typo). A fellow Named Franz Herbert, whom used to work with me, did his masters thesis on a binary implementation of octrees. He suggested that voxel was a bad choice of names. This does not tell either of us why. The name refers apparently to a simpler object than current manifestations, this is all I remember (HELP!). /* Jim Hutchison UUCP: {dcdwest,ucbvax}!cs!net1!hutch ARPA: JHutchison@ucsd.edu */
ceb@edai.ed.ac.uk (Colin Bridgewater) (08/05/88)
In article <1074@ucsd.EDU> hutch@net1.UUCP (Jim Hutchison) writes: >In article <1070@ucsd.EDU> hutch@net1.UUCP (Jim Hutchison) writes: >>name. I am aware of why. > >Franz Herbert.....suggested that voxel was a bad choice of name.... >This does not tell either of us why. Voxel seems to have been chosen in order to keep some continuity between 2D and 3D image processing. Pixel and Voxel are each respectively 'picture element' and 'volume element'. Since 'picture element' became 'pixel', why not call the 3D equivalent a 'voxel'. Does this clear things up, or have I answered a non-existent problem (again). Colin Bridgewater (joke for UK people: "daft looking cars these voxels")
hutch@net1.ucsd.edu (Jim Hutchison) (08/08/88)
In article <157@edai.ed.ac.uk> ceb@edai (Colin Bridgewater) writes: > Voxel seems to have been chosen in order to keep some continuity between > 2D and 3D image processing. Pixel and Voxel are each respectively 'picture > element' and 'volume element'. Since 'picture element' became 'pixel', > why not call the 3D equivalent a 'voxel'. > Does this clear things up, or have I answered a non-existent problem (again). Indeed the point in the name. Unfortunately Voxels are not always as similiar in size as pixels. Pixels are well behaved little polygons all the same size (squares, rectangles, hexagons, etc.). Voxels are optimally the size of the largest volume of similiar material/color they can encompass. Voxels are more a data structure than a sampling region. Or do I misunderstand pixels? /* Jim Hutchison UUCP: {dcdwest,ucbvax}!cs!net1!hutch ARPA: JHutchison@ucsd.edu */
dmark@cs.Buffalo.EDU (David Mark) (08/08/88)
In article <1081@ucsd.EDU> hutch@net1.UUCP (Jim Hutchison) writes: > > [some material removed] Unfortunately Voxels are not always as >similiar in size as pixels. Pixels are well behaved little polygons >all the same size (squares, rectangles, hexagons, etc.). Voxels are >optimally the size of the largest volume of similiar material/color >they can encompass. Voxels are more a data structure than a sampling >region. Or do I misunderstand pixels? No, you misunderstand *voxels*. In the octtree literature I am familiar with, all voxels are the same size. If any sub-cube above some minimum threshold is partly inside and partly outside the solid, it is subdivided into 8 sub-cubes of the next lower level. Sub-cubes which are uniformly inside or uniformly outside the solid are "leaf-nodes" in the octtree. THE voxel is the smallest allowable sub-cube. This is, I believe, the way voxels are defined in octtree papers by Gargantini, Samet, and others. David M. Mark dmark@joey.cs.buffalo.edu