rlaramee
Class Octree

java.lang.Object
  |
  +--rlaramee.Octree

public class Octree

extends java.lang.Object

Description: An OctTree is our data structure for storing and organizing the volume data in an adaptive resolution representation. Each level of an octree represents a different level of resolution.

Octree Optimization Tests:

Implemented
-----------

1. removing polygonList from the TriangleVertex class -saves memory
2. adding 3 new classes: IsoXvertex, IsoYvertex, IsoZvertex -saves memory
3. turning on/off min/max recursion -saves processing
4. changing addNodeFromBottom() to octant based sort as opposed to coordinate based sort -reduces paging
5. turning on/off garbage collection -reduces paging
6. removed number, error, and index from cube responsibilities -saves space
7. serialized the octree -saves processing, increases I/O time
8. increased initial heap size -slowed the program down
9. adding 128K memory to 256K total -reduces paging, thrashing
10. partitioning the octree -saves paging
11. added 2 new classes: leafNode, internalNode

Bugs ----

1. Constant.NUMLEVELS is wrong

start date Fri 30 April 1999

Version:

1.0

Author:

Robert S Laramee

See Also:

Field Summary

private int	bottomNodes # of nodes to reach bottom
private static int	direction default direction
private byte	finestLevel
private OctreeNode[]	octreeNodeArray
private int	octreeNodeArrayIndex
private int	representation TRUE if this is an AR octree
private OctreeNode	root
private int	size total # of nodes added
private int	throwAwayCount number of nodes not added to the tree

Constructor Summary

Octree(int representation)
constructor

Method Summary

void	addNodeFromBottom(OctreeNode octreeNode) addNodeFromBottom() adds a node onto the Octree.
void	addNodeFromTop(OctreeNode newNode) addNodeFromTop() adds a node onto the Octree.
boolean	addToOctreeNodeArray(OctreeNode octreeNode) Can an octree node already be in the octree node array? This node may already have children, so look for them in the octreeNodeArray.
private int	computeArrayIndexByCoord(OctreeNode octreeNode) The Octree has something that acts like a node caching mechanism.
int	computeArrayIndexByOctant(OctreeNode octreeNode) core dumb = 293,557,248 bytes, 16 Apr 00
private int	computeArrayIndexOfOneLevelByOctant(OctreeNode octreeNode) This method assumes that the octree nodes being read in are already sorted in DFS order.
private int	computeArrayIndexOfOneLevelByOctant(OctreeNode octreeNode, int bottomLevel, int currentOffset) Unlike the procedure above, this method does not assume that the octree nodes being added to the tree are already DFS sorted.
boolean	deleteNodes() This method is called from Gridded3DMRSet.makeIsoSurface() in order to free up memory
boolean	deleteNodesDeprecated() Deprecated. -the method does not work, the way the octree is being traversed, there is no way to avoid a null pointer exception.
void	errorCheck() The purpose of this function is look for errors in the octree nodes (coordinate and data values) and their corresponding triangles.
private int	getColumnHeight(int level)
private int	getColumnScale(int level)
static int	getDirection() getDirection() and setDirection() are used in order to remember from which direction we called OctreeNode.getNext()
byte	getFinestLevel()
private int	getLayerDepth(int level)
private int	getLayerScale(int level)
static int	getLengthOfOneDimension(int level)
OctreeNode	getNextByIndex() This can be called from MarchingCubes.execute() for debugging purposes.
int	getNumBottomNodes()
static int	getNumNodesAtLevel(int level)
OctreeNode	getOctreeNodeAtArrayIndex(int i) We don't want to issue an out of bounds warning because a child node maybe looking for a parent node that is not above the bottom level of storage in the octree node array
int	getRepresentation()
OctreeNode	getRoot()
private int	getRowLength(int level)
private int	getRowScale(int level) 1 cube at level 7 has a row length of 128 (in block space)
int	getSize()
int	getThrowAwayCount()
private int	levelOffsetByCoord(int level)
private int	levelOffsetByOctant(int level)
void	printArray() Print each level in the octree node array starting at the top, level 7, down to the bottom, level 3.
static void	setDirection(int newDir) getDirection() and setDirection() are used in order to remember from which direction we called OctreeNode.getNext()
boolean	setFinestLevel(byte newLevel)
void	setNumBottomNodes() Increases the number of leaf nodes in the octree by 1
private boolean	setOctreeNodeToArrayIndex(int i, OctreeNode newNode)
void	setRepresentation(int newRep)
void	setSize() Increases the size of the octree by 1
void	setThrowAwayCount() Increases the number of leaf nodes not added to the octree by 1 Called from BinaryCubeReader.throwAway()
private int	thisLevelOffsetByCoord(int level, int xCoord, int yCoord, int zCoord) There's a lot of extra code here for legibility purposes.
private int	thisLevelOffsetByOctant(int level, int bottomLevel, int octant) The cube array is ordered by octants within levels.

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait

Field Detail

direction

private static int direction

default direction

root

private OctreeNode root

size

private int size

total # of nodes added

bottomNodes

private int bottomNodes

# of nodes to reach bottom

octreeNodeArrayIndex

private int octreeNodeArrayIndex

finestLevel

private byte finestLevel

representation

private int representation

TRUE if this is an AR octree

throwAwayCount

private int throwAwayCount

number of nodes not added to the tree

octreeNodeArray

private OctreeNode[] octreeNodeArray

Constructor Detail

Octree

public Octree(int representation)

constructor

Parameters:

representation - either multi-resolution or adaptive resolution

Method Detail

getSize

public int getSize()

Returns:

the current size of the octree including both internal and leaf nodes

setSize

public void setSize()

Increases the size of the octree by 1

getNumBottomNodes

public int getNumBottomNodes()

Returns:

the number of leaf nodes in the octree

setNumBottomNodes

public void setNumBottomNodes()

Increases the number of leaf nodes in the octree by 1

setThrowAwayCount

public void setThrowAwayCount()

Increases the number of leaf nodes not added to the octree by 1 Called from BinaryCubeReader.throwAway()

getThrowAwayCount

public int getThrowAwayCount()

Returns:

the number of leaf nodes that were not added to the tree

getRepresentation

public int getRepresentation()

Returns:

the AR representation

setRepresentation

public void setRepresentation(int newRep)

Parameters:

newARlevel - the new AR representation threshold

Returns:

TRUE if the call to set() was successful

getFinestLevel

public byte getFinestLevel()

Returns:

the finest level of resolution in the octree node

setFinestLevel

public boolean setFinestLevel(byte newLevel)

Parameters:

the - finest level of resolution the octree node currently being added to the octree belongs in

Returns:

TRUE if the set() was successful

getDirection

public static int getDirection()

getDirection() and setDirection() are used in order to remember from which direction we called OctreeNode.getNext()

Returns:

direction -the direction we are currently traversing the octree in: either Constant.FROMLEFT , Constant.FROMTOP , Constant.FROMBOTTOM

setDirection

public static void setDirection(int newDir)

getDirection() and setDirection() are used in order to remember from which direction we called OctreeNode.getNext()

Parameters:

direction - the direction we are currently traversing the octree in: either Constant.FROMLEFT , Constant.FROMTOP , Constant.FROMBOTTOM

getRoot

public OctreeNode getRoot()

Returns:

the root node of the octree

getOctreeNodeAtArrayIndex

public OctreeNode getOctreeNodeAtArrayIndex(int i)

We don't want to issue an out of bounds warning because a child node maybe looking for a parent node that is not above the bottom level of storage in the octree node array

Parameters:

i - an octree node array index

Returns:

the octree node at that array index

setOctreeNodeToArrayIndex

private boolean setOctreeNodeToArrayIndex(int i,
                                          OctreeNode newNode)

Parameters:

i - an octree node array index

newNode - the octree node at that array index

Returns:

TRUE if the set() was a success

deleteNodes

public boolean deleteNodes()

This method is called from Gridded3DMRSet.makeIsoSurface() in order to free up memory

Returns:

TRUE if successful

deleteNodesDeprecated

public boolean deleteNodesDeprecated()

Deprecated. -the method does not work, the way the octree is being traversed, there is no way to avoid a null pointer exception.

This method is called from Gridded3DMRSet.makeIsoSurface() in order to free up memory

Parameters:

octant - the octant in which to delete the nodes

Returns:

TRUE if successful

addNodeFromTop

public void addNodeFromTop(OctreeNode newNode)

addNodeFromTop() adds a node onto the Octree. To add a node to the octree start with the root. Reject the root node or nodes with an invalid level.

Parameters:

newNode - an octree node

addNodeFromBottom

public void addNodeFromBottom(OctreeNode octreeNode)

addNodeFromBottom() adds a node onto the Octree. To add a node we want to utilize the octree node array. Instead of starting at the root (top) of the octree, we look for this node's parent node in the octree node array. Conceptually, it's like starting from the bottom. The purpose of this function is not to always recurse to the root node.

 IF the parent node is in the array 
 THEN use the parent pointer to set the parent's new child
 ELSE create the parent node AND set its octree node array pointer
 THEN use the parent pointer to set the parent's new child
 

Reject the root node or nodes with an invalid level.

Parameters:

octreeNode - an octree node

addToOctreeNodeArray

public boolean addToOctreeNodeArray(OctreeNode octreeNode)

Can an octree node already be in the octree node array? This node may already have children, so look for them in the octreeNodeArray.

Parameters:

octreeNode - the octree node to add

Returns:

TRUE if successful.

computeArrayIndexByOctant

public int computeArrayIndexByOctant(OctreeNode octreeNode)

core dumb = 293,557,248 bytes, 16 Apr 00

Parameters:

octreeNode - the node whose array index we are computing

level - the level of the octreeNode

Returns:

index -the correct offset into the array of cubes

computeArrayIndexOfOneLevelByOctant

private int computeArrayIndexOfOneLevelByOctant(OctreeNode octreeNode)

This method assumes that the octree nodes being read in are already sorted in DFS order. Therefore all we have to do in order to compute a parent's position in an array is divide the total number of (bottom) nodes read in and divide by 8.

Parameters:

octreeNode - the octree node whose index we are computing

Returns:

the array index of 1 level of the octree that this node belongs in

computeArrayIndexOfOneLevelByOctant

private int computeArrayIndexOfOneLevelByOctant(OctreeNode octreeNode,
                                                int bottomLevel,
                                                int currentOffset)

Unlike the procedure above, this method does not assume that the octree nodes being added to the tree are already DFS sorted. That's why this procedure recurses all the way up to the root node.

Parameters:

octreeNode - the node whose array index we are computing

bottomLevel - the level of the original octree node from computeArrayIndexByOctant()

currentOffset - the offset into the array of cubes thus far

Returns:

index -the correct offset into the array of cubes

computeArrayIndexByCoord

private int computeArrayIndexByCoord(OctreeNode octreeNode)

The Octree has something that acts like a node caching mechanism. It holds an array of pointers to each node in the top 5 levels in the octree. In particular it stores pointers to these nodes:

 octree level   number of nodes
 ------------   ---------------
  7              1 -the root
  6              8 (2 x 2 x 2) -the root's 8 children
  5             64 (4 x 4 x 4)
  4            512 (8 x 8 x 8)
  3          4,096 (16 x 16 x 16)
 --------------------------------
  6          4,681 total

  2         32,768 (32 x 32 x 32)
 --------------------------------
  7         37,449 -with level 2
 

Parameters:

octree - node

Returns:

the index in the octree node array for the given node

thisLevelOffsetByOctant

private int thisLevelOffsetByOctant(int level,
                                    int bottomLevel,
                                    int octant)

The cube array is ordered by octants within levels. For example, all of the cubes that lie in octant 0 at level 6 are in array indices
[0 to (64^3 - 1)]

all of the cubes that lie in octant 1 at level 5 are in and are children of child 0 at level 6 are in array indices
[ (0 * (64^3 - 1)) + (1 * 32^3 to 2 * (32^3 - 1) ]

etc.

        dimensions in    dimensions in  
 level   block space    coordinate space   level scale
 -----  -------------   -----------------  -----------
  7       1 x 1 x 1     128 x 128 x 128    128^3
  6       2 x 2 x 2      64 x 64 x 64       64^3
  5       4 x 4 x 4      32 x 32 x 32       32^3
  4       8 x 8 x 8      16 x 16 x 16       16^3
  3      16 x 16 x 16     8 x 8 x 8          8^3
  2      32 x 32 x 32     4 x 4 x 4          4^3 
  1      64 x 64 x 64     2 x 2 x 2          2^3
  0     128 x 128 x 128   1 x 1 x 1          1^3
 

Parameters:

level - level in the octree

bottomLevel - the level of the original octree node from computeArrayIndexByOctant()

octant - the octant at that level

thisLevelOffsetByCoord

private int thisLevelOffsetByCoord(int level,
                                   int xCoord,
                                   int yCoord,
                                   int zCoord)

There's a lot of extra code here for legibility purposes. All coordinates are in the range of 0-128.

Parameters:

level - the level of the cube (and node)

xCoord - the x block coordinate index of the cube

yCoord - the y block coordinate index of the cube

zCoord - the z block coordinate index of the cube

Returns:

the index offset into the octreeNodeArray at the given level, given the x,y,z block/cube coordinate indices (of the 0th vertex)

levelOffsetByOctant

private int levelOffsetByOctant(int level)

Parameters:

level - a level of the octree

Returns:

the index offset into the octree node array that the given level starts at

levelOffsetByCoord

private int levelOffsetByCoord(int level)

Parameters:

level - a level of the octree

Returns:

the index offset into the octree node array that the given level starts at

getNumNodesAtLevel

public static int getNumNodesAtLevel(int level)

Parameters:

level - a level in the octree

Returns:

offset -the number of nodes in the level

getLengthOfOneDimension

public static int getLengthOfOneDimension(int level)

Parameters:

level - a level in an octree

the - number of cubes along 1 x,y,z dimension in that level

getRowScale

private int getRowScale(int level)

1 cube at level 7 has a row length of 128 (in block space)

 level       1 cube length
 -----       -------------
  7            128
  6             64
  5             32
  4             16
  3              8
  2              4
  1              2
  0              1
 

Parameters:

level - a level in the octree

Returns:

the length of 1 row of 1 cube at that level

getColumnScale

private int getColumnScale(int level)

Parameters:

level - a level in the octree

Returns:

the length of 1 column of 1 cube at that level

getLayerScale

private int getLayerScale(int level)

Parameters:

level - a level in the octree

Returns:

the length of 1 layer of 1 cube at that level

getRowLength

private int getRowLength(int level)

Parameters:

level - a level in the octree

Returns:

rowLength -the length of a row in that level

getColumnHeight

private int getColumnHeight(int level)

Parameters:

level - a level in the octree

Returns:

columnHeight -the number of columns in that level

getLayerDepth

private int getLayerDepth(int level)

Parameters:

level - a level in the octree

Returns:

layerDepth -the number of layers in that level

getNextByIndex

public OctreeNode getNextByIndex()

This can be called from MarchingCubes.execute() for debugging purposes.

Returns:

an octree node from the next array index in the octree node array

errorCheck

public void errorCheck()

The purpose of this function is look for errors in the octree nodes (coordinate and data values) and their corresponding triangles. It's called immediately after the surface is generated (from Gridded3DMRSet.java ).

printArray

public void printArray()

Print each level in the octree node array starting at the top, level 7, down to the bottom, level 3.