rlaramee
Class OctreeNode

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

Direct Known Subclasses:

OctreeInternalNode, OctreeLeafNode

public abstract class OctreeNode

extends java.lang.Object

Description: The Octree is made up of Octree Nodes. In the tree representation, the lower level nodes store data at a higher resolution. Each node is an octant of a parent node.

Internal nodes also have 2 values: the minimum and maximum values of all its decendants [children].

Leaf nodes have 8 data values and a minimum and maximum of those data values. It is the leaf nodes that are rendered.

Each octant is labeled using the convention from page 87 of Applications of Spacial Data Structures by H. Samet.
Note: it is only the labeling convention taken from H. Samet, not the numbering. (H. Samet uses a different numbering convention.) The octants are numbered using the convention from page 233 of The Visualization Toolkit (first edition) Figure 8-11 This is the same as the cube-vertex numbering and labeling.

start date Fri 30 April 1999

Version:

1.0

Author:

Robert S Laramee

See Also:

Field Summary

private byte	childNumber an int uses 4 bytes, 3 too many
private Cube	cube octree node has a cube as a member
private boolean	debug
private OctreeNode	parentNode a pointer is 4 bytes
private boolean	processed has this octree node been processed by the MC algorithm ?
private OctreeNode	siblingNode node to the "right"
private java.util.Vector	triangleList replace this with an array or an ArrayList for more efficiency Note: a cube in the Marching Cubes algorithm can contain no more than 5 triangles.

Constructor Summary

OctreeNode(Cube newCube)

Method Summary

void	accumulateUniqueDirections(byte edge, byte[] uniqueDirections) This method is called from IsoSurface.computeTriangle() It responsible for aggregating the unique directions to search for octree node neighbors given the edge.
abstract boolean	addEdgeVertex(SharedEdgeVertex newSharedVertex)
abstract boolean	addFacialVertex(SharedFacialVertex sv)
void	addNodeFromTop(OctreeNode newNode) addNodeFromTop() adds a node onto the Octree starting with the root.
void	addTriangle(Triangle triangle) addTriangle() adds a triangle onto the octree node's list
abstract void	addTriangleEdge(TriangleEdge triangleEdge)
private boolean	alreadyThere(java.util.Vector vertexList, TriangleVertex triangleVertex)
abstract void	assembleChainGang()
byte	classifyNode(OctreeNode newNode) This function identifies which of this node's octants the node being passed belongs to/in.
private OctreeNode	createChild(byte childLevel, byte childOctant) This is called from OctreeNode.getChild(int, int) Creates a new placeholder child node.
OctreeNode	createParent(Octree octree) This is called from Octree.addNodeFromBottom() Creates a new placeholder parent node.
void	deletePreviousSurface() The method is called from MarchingCubes.execute() It used when using the same octree to render multiple isosurfaces since octree nodes may have triangles left over from prior isosurface computations.
abstract byte	deleteTriangles(IsoSurface surface)
boolean	encompassesSurface(float isoValue) encompassesSurface() is called from MachingCubes.execute()
boolean	errorCheck() The purpose of this function is look for errors in the octree nodes (coordinate and data values) and their corresponding triangles.
abstract byte	faceWithMaxChains()
private OctreeNode	findAncestor(byte direction)
void	freeMemory() This method attempts to free up all the resources a node takes up in order to help out the gargbage collector.
abstract byte	generateTriangleFans(IsoSurface surface)
abstract OctreeARnode	getARnode()
OctreeNode	getChild(byte childn) This version of getChild() is called from OctreeNode.getNext(), OctreeNode.getFaceNeighbor(), Draw3d.renderNode()
private OctreeNode	getChild(byte level, byte childn, Octree octree) This method (always) returns a child node.
byte	getChildNumber()
abstract OctreeNode	getChildZero()
Cube	getCube()
abstract java.util.Vector	getEdgeVertexList()
java.util.Vector	getEdgeVerticesOfCoarserNeighbor(byte fineEdge, byte fineOctant, byte fineToCoarseDir, OctreeNode coarseNode) Deprecated. Is this method still being used?
OctreeNode	getFaceNeighbor(byte direction) Locate the face-neighbor of node N , of size greater than or equal to N , in direction D .
abstract java.util.Vector	getFacialVertexList()
byte	getLevel()
abstract float	getMaximum()
abstract float	getMinimum()
OctreeNode	getNext(boolean skipBranch) The getNext() algorithm for an AR octree:
int	getNumTriangles() This method is called from MarchingCubes.processSubDivide()
OctreeNode	getParent()
short	getResolution()
OctreeNode	getSibling()
OctreeNode	getSibling(int number) Deprecated. -use getSibling() instead
Triangle	getTriangle(byte n) Don't forget, getTriangle() may be called for a qualified node that has not actually generated its triangles yet because it has not been traversed.
java.util.Vector	getTriangleList()
private boolean	isAdjacent(byte f, byte o) P3_____________P2 This is the cube representation /| /| used to write the isAdjacent() / | / | and reflect() methods.
boolean	isEqual(OctreeNode otherNode) Checks to see if 2 OctreeNodes are the same.
protected boolean	isLeafNode() This method identifies a leaf node - a node with no children
OctreeNode[]	mapAdjacentChildrenFineToCoarseDir(byte fromFineToCoarseDir) This method is called from IsoSurfaceAdaptive.processSubdivide() .
byte[]	mapDirectionsFromEdge(byte edge) This is called from OctreeNode.accumulateDirectionsFromEdge() .
byte[]	mapDirectionsFromOctant(byte octant, byte deltaResolution) Deprecated. -use OctreeNode.mapDirectionsFromEdge() instead
private byte	mapOctant(byte octant)
abstract byte	maxChainsPerFace()
abstract SharedEdgeVertex	onCoarseEdge(TriangleVertex fv, byte octant, byte direction)
abstract SharedFacialVertex	onCoarseFace(TriangleVertex fv, byte octant, byte direction)
private void	p(int n) called from OctreeNode.reflect()
private void	p(java.lang.String bool)
abstract void	print() Print out a node's private data members.
private byte	reflect(byte f, byte o) This returns the octant (child number) number of the cube of equal size (not necessarily a brother) that shares the face, f, of a cube in octant o.
void	removeNodes()
private boolean	removeTriangles() This method is called from OctreeNode.subDivide()
private boolean	set3pointers(byte octant, OctreeNode newChildNode, Octree octree) This method takes an octree node and sets the parent, childZero and sibling pointers.
boolean	set8children(Cube[] childCubes)
boolean	setChild(byte octant, OctreeNode newChildNode, Octree octree) The new child node may take the place of a placeholder node.
boolean	setChildNumber(byte n)
abstract boolean	setChildZero(OctreeNode node)
void	setCube(Cube newCube)
abstract boolean	setEdgeVertexList(java.util.Vector newList)
abstract boolean	setFacialVertexList(java.util.Vector newList)
void	setLevel(byte l)
abstract boolean	setMaximum(float max)
abstract boolean	setMinimum(float min)
private void	setParent(OctreeNode parent)
void	setResolution(short res)
private boolean	setSibling(OctreeNode newOctreeNode)
void	setTriangleList(java.util.Vector v)
private boolean	sharedFineEdge(byte coarseEdge, byte fineEdge, byte fineOctant, byte fineDirection) Deprecated. this method has to be re-evaluated and probably rewritten to handle more than one level of resolution difference.
Cube[]	subDivide(OctreeNode[] fourChildren, byte fromFineToCoarseDir) The way we are going to collaborate on this is to let the OctreeNode be responsible for identifying which 9 out of the 19 (0-18) possible vertices are shared between the adjacent nodes (because it is the OctreeNode not the cube that can find neighbors).
private OctreeNode	traverseChildren()
private OctreeNode	traverseSiblings()
abstract boolean	updateEdgeVertices()
boolean	updateTriangle(byte triangleNumber, byte vertexNumber, TriangleVertex newVertex)

Methods inherited from class java.lang.Object

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

Field Detail

parentNode

private OctreeNode parentNode

a pointer is 4 bytes

siblingNode

private OctreeNode siblingNode

node to the "right"

cube

private Cube cube

octree node has a cube as a member

triangleList

private java.util.Vector triangleList

replace this with an array or an ArrayList for more efficiency Note: a cube in the Marching Cubes algorithm can contain no more than 5 triangles.

childNumber

private byte childNumber

an int uses 4 bytes, 3 too many

processed

private boolean processed

has this octree node been processed by the MC algorithm ?

debug

private boolean debug

Constructor Detail

OctreeNode

public OctreeNode(Cube newCube)

Method Detail

getMinimum

public abstract float getMinimum()

See Also:

OctreeLeafNode and OctreeInternalNode classes for the implementation of these methods

getMaximum

public abstract float getMaximum()

setMinimum

public abstract boolean setMinimum(float min)

setMaximum

public abstract boolean setMaximum(float max)

getChildZero

public abstract OctreeNode getChildZero()

setChildZero

public abstract boolean setChildZero(OctreeNode node)

getEdgeVertexList

public abstract java.util.Vector getEdgeVertexList()

See Also:

OctreeInternalNode.getEdgeVertexList() for the implementation of these methods

setEdgeVertexList

public abstract boolean setEdgeVertexList(java.util.Vector newList)

addEdgeVertex

public abstract boolean addEdgeVertex(SharedEdgeVertex newSharedVertex)

getFacialVertexList

public abstract java.util.Vector getFacialVertexList()

setFacialVertexList

public abstract boolean setFacialVertexList(java.util.Vector newList)

addFacialVertex

public abstract boolean addFacialVertex(SharedFacialVertex sv)

updateEdgeVertices

public abstract boolean updateEdgeVertices()

See Also:

OctreeInternalNode.updateEdgeVertices()

onCoarseEdge

public abstract SharedEdgeVertex onCoarseEdge(TriangleVertex fv,
                                              byte octant,
                                              byte direction)

See Also:

OctreeInternalNode.onCoarseEdge()

onCoarseFace

public abstract SharedFacialVertex onCoarseFace(TriangleVertex fv,
                                                byte octant,
                                                byte direction)

See Also:

OctreeInternalNode.onCoarseFace()

addTriangleEdge

public abstract void addTriangleEdge(TriangleEdge triangleEdge)

See Also:

OctreeInternalNode.addTriangleEdge()

getARnode

public abstract OctreeARnode getARnode()

See Also:

OctreeInternalNode.getARnode()

deleteTriangles

public abstract byte deleteTriangles(IsoSurface surface)

See Also:

OctreeInternalNode.deleteTriangles()

assembleChainGang

public abstract void assembleChainGang()

See Also:

OctreeARnode class for the implementation of these methods

maxChainsPerFace

public abstract byte maxChainsPerFace()

faceWithMaxChains

public abstract byte faceWithMaxChains()

generateTriangleFans

public abstract byte generateTriangleFans(IsoSurface surface)

getCube

public Cube getCube()

Returns:

cube -this octree node's cube

setCube

public void setCube(Cube newCube)

Parameters:

newCube - set this octree node's cube to this newCube

getResolution

public short getResolution()

Returns:

the resolution of this octree node

setResolution

public void setResolution(short res)

Parameters:

the - resolution of this octree node

getTriangleList

public java.util.Vector getTriangleList()

Returns:

this octree node's vector list of triangles

getTriangle

public Triangle getTriangle(byte n)

Don't forget, getTriangle() may be called for a qualified node that has not actually generated its triangles yet because it has not been traversed. This can be due to checking all of a node's neighbors for inconsistent interpolation.
(That is why the warning was commented out.)

Parameters:

n - the triangle number to return

Returns:

Triangle n -the n^th triangle from this octree node's list of triangles

deletePreviousSurface

public void deletePreviousSurface()

The method is called from MarchingCubes.execute() It used when using the same octree to render multiple isosurfaces since octree nodes may have triangles left over from prior isosurface computations.

setTriangleList

public void setTriangleList(java.util.Vector v)

Parameters:

v - a new vector to hold a list of triangles

removeTriangles

private boolean removeTriangles()

This method is called from OctreeNode.subDivide()

When a node is subdivided, it's coarser resolution triangles must be removed. The MC algorithm generates a maximum of 5 triangles per cube

Returns:

TRUE if the triangles were actually removed

getNumTriangles

public int getNumTriangles()

This method is called from MarchingCubes.processSubDivide()

Returns:

the number of triangles this octreeNode has.

getLevel

public byte getLevel()

Returns:

level -the level in the octree this node is in

setLevel

public void setLevel(byte l)

Parameters:

newLevel - the level in the octree this node is in

getChildNumber

public byte getChildNumber()

Returns:

child number -a number from 0-7 indicating which parent node's octant this node is in

setChildNumber

public boolean setChildNumber(byte n)

Parameters:

child - number a number from 0-7 indicating which parent node's octant this node is in

Returns:

TRUE if the call to set() was successful

getParent

public OctreeNode getParent()

Returns:

this octree node's parent node

setParent

private void setParent(OctreeNode parent)

Parameters:

OctreeNode - this octree node's parent node

getSibling

public OctreeNode getSibling()

Returns:

OctreeNode this octree node's sibling i.e. the octree node in the next highest octant e.g. if this is octree node number 1 at 2^3 resolution, this returns octree node number 2 at 2^3 resolution

setSibling

private boolean setSibling(OctreeNode newOctreeNode)

Parameters:

OctreeNode - this octree node's sibling octree node

getEdgeVerticesOfCoarserNeighbor

public java.util.Vector getEdgeVerticesOfCoarserNeighbor(byte fineEdge,
                                                         byte fineOctant,
                                                         byte fineToCoarseDir,
                                                         OctreeNode coarseNode)

Deprecated. Is this method still being used?

This method is similar to the compareVertices() method. Given an edge, identify any TriangleVertices that this octreeNode may have on that edge.

Parameters:

fineEdge - the finer resolution neighboring octree node edge

fineOctant - the octant that the calling finer resolution octree node neigbor is in

fineDirection - the direction in which to look for shared edge

coarseNode - the coarser resolution neighboring octree node

Returns:

coarseEdgeVertices -a set of edge vertices

alreadyThere

private boolean alreadyThere(java.util.Vector vertexList,
                             TriangleVertex triangleVertex)

Parameters:

vertexList - a vector of TriangleVertex objects

triangleVertex - 1 TriangleVertex object

Returns:

TRUE if the given triangleVertex is already in the list

sharedFineEdge

private boolean sharedFineEdge(byte coarseEdge,
                               byte fineEdge,
                               byte fineOctant,
                               byte fineDirection)

Deprecated. this method has to be re-evaluated and probably rewritten to handle more than one level of resolution difference.

We're searching for shared edge intersections. This method is called from: OctreeNode.getEdgeVerticesOfCoarserNeighbor() .

Note that it is a finer resolution cube that updates the vertices of coarser resolution neighbors. Distinguishing shared edge intersections is going to depend on the calling octree node's octant and direction.

             P3_____e2______P2   This is the cube representation
             /|            /|    used write the method.
           e10|          e11|    It is the same as the VTK's except 
   y     P7______e6____P6/  |    for the orientation of the 
   ^      |   e3        |   e1   y,z axes.
   |      |   |         |   |    
   |      e7  |         e5  |
   |--->  | P0|_____e0__|___|P1
  /    x  |  /          |  /
 /        | e8          | e9
z         |/_____e4_____|/
         P4             P5
 

It is also important to note that this method does not check for facial intersections. We'll give that responsibility to another method in order to make things a little simpler.

Parameters:

coarseEdge - this octree node edge

fineEdge - the finer resolution octree node's edge intersection

fineOctant - the octant that the calling finer resolution octree node neigbor is in

fineDirection - the direction in which to look for shared edge

Returns:

TRUE if the given edges are shared

subDivide

public Cube[] subDivide(OctreeNode[] fourChildren,
                        byte fromFineToCoarseDir)

The way we are going to collaborate on this is to let the OctreeNode be responsible for identifying which 9 out of the 19 (0-18) possible vertices are shared between the adjacent nodes (because it is the OctreeNode not the cube that can find neighbors).

Then, the OctreeNode will pass these 9 values along to the cube in order to finish the actual subDivision algorithm.

Also, we have to remember to delete this nodes triangles if it has to be subdivided because we don't want to render this node's coarser triangles.

Parameters:

fineAdjacentChildren - the 4 the finer resolution neighboring children to this node -which is being subdivided. It is a finer resolution neighbor that made the request for this node/cube to subdivide

fromFineToCoarseDir - the direction from the finer resolution neighbor to this coarse node

Returns:

an array of 8 ordered-by-octant, child cubes 0-7

mapDirectionsFromOctant

public byte[] mapDirectionsFromOctant(byte octant,
                                      byte deltaResolution)

Deprecated. -use OctreeNode.mapDirectionsFromEdge() instead

This is called from OctreeNode.isCoarserThanNeighbors() and IsoSurface.findARnodes() .

For a given octant, an octreeNode only has face neighbors of coarser resolutions in 3 possible directions. For a given octant, an octreeNode may have face neighbors of finer resolutoins in all 6 directions.

One might infer that since both of these neighbors share a common edge, we only have to update a vertex on this common edge for one of the neighbors. However, this reasoning won't work unless both of the neighbors are there and both have triangles.

Parameters:

octant - the octant an octreeNode belongs in

directions - the directions to inspect neighbors in

accumulateUniqueDirections

public void accumulateUniqueDirections(byte edge,
                                       byte[] uniqueDirections)

This method is called from IsoSurface.computeTriangle() It responsible for aggregating the unique directions to search for octree node neighbors given the edge.

Parameters:

edge - the edge that a triangle vertex lies on

directions - the directions that abut this edge.

mapDirectionsFromEdge

public byte[] mapDirectionsFromEdge(byte edge)

This is called from OctreeNode.accumulateDirectionsFromEdge() .

For a given edge, an octreeNode only has face neighbors of different resolutions in 2 possible directions. One might infer that since both of these neighbors share a common edge, we only have to update a vertex on this common edge for one of the neighbors. However, this reasoning won't work unless both of the neighbors are there and both have triangles.

Parameters:

octant - the octant an octreeNode belongs in

directions - the directions to inspect neighbors in

mapAdjacentChildrenFineToCoarseDir

public OctreeNode[] mapAdjacentChildrenFineToCoarseDir(byte fromFineToCoarseDir)

This method is called from IsoSurfaceAdaptive.processSubdivide() . The given direction is the direction from the fine neighbor to the coarse neighbor (that needs to be subdivided) .

Parameters:

fromFineToCoarseDirection - the direction the fine neighbor is requesting the subdivision from

node - the octree node calling this method

Returns:

fourChildren -the four child nodes adjacent to an octree node from the given direction

freeMemory

public void freeMemory()

This method attempts to free up all the resources a node takes up in order to help out the gargbage collector.

Use this method with caution.

Returns:

TRUE on success.

removeNodes

public void removeNodes()

getFaceNeighbor

public OctreeNode getFaceNeighbor(byte direction)

Locate the face-neighbor of node N , of size greater than or equal to N , in direction D .

 IF such a node does not exist THEN
    return null
 

To understand this method, you have to understand the \ isAdjacent() and reflect() methods. A node calls isAdjacent() until a common ancestor is found, and then calls reflect() down the list of adjacent nodes.

Parameters:

direction - the direction we're seeking the face-neighbor in

Returns:

the face neighbor of this octree node in the given direction

findAncestor

private OctreeNode findAncestor(byte direction)

Parameters:

direction - the direction we are seeking our face neighbor in e.g. LEFT, RIGHT, DOWN, UP, BACK, FRONT

Returns:

the ancestor of this octree node and this octree node's face neighbor

isLeafNode

protected boolean isLeafNode()

This method identifies a leaf node - a node with no children

Returns:

TRUE if this is a leaf node

isAdjacent

private boolean isAdjacent(byte f,
                           byte o)

             P3_____________P2   This is the cube representation
             /|            /|    used to write the isAdjacent()
            / |           / |    and reflect() methods.  It is
   y     P7____________P6/  |    the same as the VTK's except 
   ^      |   |         |   |    for the orientation of the 
   |      |   |         |   |    y,z axes.
   |      |   |         |   |
   |--->  | P0|_________|___|P1
  /    x  |  /          |  /
 /        | /           | /
z         |_____________|/
         P4             P5
 

This method returns TRUE if and only if octant, o, is adjacent to face, f, of o's containing block. For example the right face of a cube is adjacent to it's parent's containing cube if it is in octant 1,2,5, or 6. See pages 86-88 of Application's of Spatial Data Structures by H. Samet. Note orientation of axes on page 86.

Parameters:

a - face defined in Constant.java

an - octant number

Returns:

TRUE if this face is adjacent to the given octant

p

private void p(java.lang.String bool)

Parameters:

string - a boolean string indicating TRUE or FALSE

reflect

private byte reflect(byte f,
                     byte o)

This returns the octant (child number) number of the cube of equal size (not necessarily a brother) that shares the face, f, of a cube in octant o. For example reflect(LEFT, 0) returns octant 1 i.e. the LEFT face of a cube in octant 0 is shared by a cube of equal size in octant 1.

See pages 86-88 of Applications of Spacial Data by H. Samet. Note orientation of axes on page 86.

Parameters:

a - face defined in Constant.java

an - octant number

Returns:

-the reflected octant number

p

private void p(int n)

called from OctreeNode.reflect()

Parameters:

n - a number from 0 to 7

addNodeFromTop

public void addNodeFromTop(OctreeNode newNode)

addNodeFromTop() adds a node onto the Octree starting with the root. To add a node to the octree, starting with the root:

Classify the new node as to which octant it belongs in.

 IF we're at the correct resolution (the next finer resolution) THEN
    set the child and parent pointers (we're done)
 ELSE
    Follow child pointer to that octant.
    Recurse down the tree until we reach the new node's level.
 

Parameters:

newNode - a new octree node

classifyNode

public byte classifyNode(OctreeNode newNode)

This function identifies which of this node's octants the node being passed belongs to/in.

Parameters:

newNode - an octree node

Returns:

octant -a number from 0 to 7 identifying an octant

mapOctant

private byte mapOctant(byte octant)

Parameters:

octant - an octant ID passed from classifyNode()

Returns:

the octant number

encompassesSurface

public boolean encompassesSurface(float isoValue)

encompassesSurface() is called from MachingCubes.execute()

We are going to skip the children of nodes when the isovalue is not within the nodes' minimum and maximum. This not as restrictive as processCube() because it has nothing to do with whether a node is leaf node or an internal node.

Parameters:

octreeNode - the OctreeNode we are deciding on

isoValue - the isosurface value to render

Returns:

TRUE if the isoValue is between this node's min and max scalar values

set8children

public boolean set8children(Cube[] childCubes)

Parameters:

childCubes - an array of 8 child cubes

Returns:

TRUE if the call to set() was successful

setChild

public boolean setChild(byte octant,
                        OctreeNode newChildNode,
                        Octree octree)

The new child node may take the place of a placeholder node. Therefore, if we detect a child node that is already there (a placeholder) we'll just update the placeholder's cube with the new cube (rather than resetting all the pointers).

Parameters:

octant - the octant it's being added too

newChildNode - a new child node

optional parameters:

octree - a reference to the octree so we may add a pointer to the new node (but only if it really is a new node and not updating a placeholder node) This parameter is used *only* from Octree.addNodeFromBottom()

Returns:

TRUE if the newChildNode is really new and did not update a placeholder node

set3pointers

private boolean set3pointers(byte octant,
                             OctreeNode newChildNode,
                             Octree octree)

This method takes an octree node and sets the parent, childZero and sibling pointers. It was removed to make setChild() a shorter method

Parameters:

octant - the octant it's being added too

newChildNode - a new child node

octree - a reference to the octree so we may add a pointer to the new node (but only if it really is a new node and not updating a placeholder node) This parameter is used *only* from Octree.addNodeFromBottom()

Returns:

TRUE if the pointers were set

getChild

private OctreeNode getChild(byte level,
                            byte childn,
                            Octree octree)

This method (always) returns a child node. It's called from OctreeNode.addNode() and OctreeNode.setChild() If the node's data hasn't been populated yet, we create a new empty (placeholder) node

Parameters:

level - level of node

octant - an octant ID passed from classifyNode()

octree - a reference to the octree, needed only by setChild(int, OctreeNode, Octree)

Returns:

an octree node

getChild

public OctreeNode getChild(byte childn)

This version of getChild() is called from OctreeNode.getNext(), OctreeNode.getFaceNeighbor(), Draw3d.renderNode()

Parameters:

childn - a number from 0-7 indicating which child node to return

Returns:

OctreeNode -the octree node in the octant requested

createChild

private OctreeNode createChild(byte childLevel,
                               byte childOctant)

This is called from OctreeNode.getChild(int, int) Creates a new placeholder child node. This placeholder should get replaced when the real octree node is read from secondary storage.

Parameters:

level - level of node

octant - an octant ID passed from getChild()

Returns:

the new node

createParent

public OctreeNode createParent(Octree octree)

This is called from Octree.addNodeFromBottom() Creates a new placeholder parent node. This placeholder should get replaced when the real octree node is read from secondary storage. Cube.setCoordinates() sets the x,y,z coordinates of the other 7 vertices.

Parameters:

octree - -an optional parameter, a pointer to the octree

Returns:

the new node

getNext

public OctreeNode getNext(boolean skipBranch)

The getNext() algorithm for an AR octree:

 IF the direction is FROMABOVE OR FROM LEFT THEN 
    get next available child
 IF no children THEN return next sibling
 IF no children OR siblings THEN return parent node
 ELSE
 IF the direction is FROMBELOW THEN traverse siblings
 IF no siblings are found THEN return the parent node
 

Parameters:

skipBranch - is TRUE if we are to skip this octree node's children

Returns:

OctreeNode the next octree node

getSibling

public OctreeNode getSibling(int number)

Deprecated. -use getSibling() instead

getSibling() is called from OctreeNode.getNext() It's intended to return a node's next sibling on the right (when looking at a picture of an octree) This method was rewritten to take advantage of the new siblingNode pointer.

Parameters:

number - a number from 0-7 indicating which sibling to return

traverseChildren

private OctreeNode traverseChildren()

Returns:

-a child node, if one exists

traverseSiblings

private OctreeNode traverseSiblings()

Returns:

-the next nearest sibling node, if one exists

isEqual

public boolean isEqual(OctreeNode otherNode)

Checks to see if 2 OctreeNodes are the same. Two nodes are considered the same if both their 0 ^th vertices are in the same spot.

Parameters:

otherNode - the other node that may be equal to this one

Returns:

TRUE if the given node is in the same spot in coordinate space as this one

addTriangle

public void addTriangle(Triangle triangle)

addTriangle() adds a triangle onto the octree node's list

Remember, the initilization of the triangleList has been postponed until we actually have some triangles, in order to save memory

Parameters:

cube - a new cube

updateTriangle

public boolean updateTriangle(byte triangleNumber,
                              byte vertexNumber,
                              TriangleVertex newVertex)

Parameters:

triangleNumber - which triangle from this node's triangleList to update

vertexNumber - which vertex from the given triangle to update

triangleVertex - the new TriangleVertex to insert

Returns:

-TRUE if the update is successful

errorCheck

public boolean 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 from Octree.errorCheck()

print

public abstract void print()

Print out a node's private data members. This method must be over-ridden.