Path: utzoo!utgpu!attcan!uunet!lll-winken!lll-tis!ames!ncar!oddjob!uxc!uxc.cso.uiuc.edu!osiris.cso.uiuc.edu!leather
From: leather@osiris.cso.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: Request for info on octrees...
Message-ID: <8800007@osiris.cso.uiuc.edu>
Date: 28 Jul 88 19:02:00 GMT
References: <3708@okstate.UUCP>
Lines: 59
Nf-ID: #R:okstate.UUCP:3708:osiris.cso.uiuc.edu:8800007:000:3226
Nf-From: osiris.cso.uiuc.edu!leather    Jul 28 14:02:00 1988


> /* 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