

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object de.grogra.vecmath.geom.Octree
public abstract class Octree
Abstract base class for octrees.
Nested Class Summary  

static class 
Octree.Cell
A Cell represents a cell of an Octree . 
static class 
Octree.State
An instance of State represents the state which
is needed for octree algorithms, namely for the methods
computeIntersections(de.grogra.vecmath.geom.Line, int, de.grogra.vecmath.geom.IntersectionList, de.grogra.vecmath.geom.Intersection, de.grogra.vecmath.geom.Intersection, de.grogra.vecmath.geom.Octree.State) and Octree.Cell.getVolume(int, de.grogra.vecmath.geom.Octree.State) . 
Field Summary  

static int 
MAX_DEPTH
The maximum depth which can be handled by this octree implementation. 
static int 
MAX_GRID_SIZE
The grid size (number of cells in a single direction) which corresponds to the maximum depth, 1 << MAX_DEPTH . 
Constructor Summary  

Octree()

Method Summary  

boolean 
computeIntersections(Line line,
int which,
IntersectionList list,
Intersection excludeStart,
Intersection excludeEnd,
Octree.State state)
Computes intersections between the boundary surfaces of the volumes of this union and the specified line . 
abstract Octree.State 
createState()
This factory methods creates a new instance of Octree.State which is suitable as state for this octree. 
protected void 
finishCells()

int 
getCellCount()
Returns the number of octree cells of this octree. 
int 
getDepth()
Returns the depth of this octree. 
protected abstract java.util.ArrayList 
getInfiniteVolumes()
Returns a list of infinite volumes which shall be treated as part of the octree, though they cannot be included in the hierarchy of octree cells. 
Point3d 
getMax()
Returns the maximum coordinates of the octree box. 
Point3d 
getMin()
Returns the minimum coordinates of the octree box. 
Octree.Cell 
getRoot()
Returns the root cell of the octree. 
protected void 
initialize(int maxDepth,
int minObjects,
Tuple3d min,
Tuple3d max,
Octree.Cell root)
Initializes the octree. 
static int 
suggestDepth(int numberOfVolumes)
Suggests a maximal octree depth for the given numberOfVolumes . 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

public static final int MAX_DEPTH
public static final int MAX_GRID_SIZE
1 << MAX_DEPTH
.
Constructor Detail 

public Octree()
Method Detail 

public boolean computeIntersections(Line line, int which, IntersectionList list, Intersection excludeStart, Intersection excludeEnd, Octree.State state)
line
.
For the parameters, see Volume.computeIntersections(de.grogra.vecmath.geom.Line, int, de.grogra.vecmath.geom.IntersectionList, de.grogra.vecmath.geom.Intersection, de.grogra.vecmath.geom.Intersection)
.
The additional parameter state
has to be preallocated
by invocation of createState()
and may be used for
multiple invocations of this method. This is preferable to
the ordinary computeIntersections
method of the
interface Volume
for performance reasons.
line
 a linewhich
 one of Intersection.ALL
,
Intersection.CLOSEST
, Intersection.ANY
, this
determines which intersections have to be added to list
list
 the intersections are added to this listexcludeStart
 intersection at start point which shall be excluded, or null
excludeEnd
 intersection at end point which shall be excluded, or null
state
 instance of State
as returned by createState()
true
iff the beginning of the line lies
within the volumepublic abstract Octree.State createState()
Octree.State
which is suitable as state for this octree.
State information is needed in the methods
computeIntersections(de.grogra.vecmath.geom.Line, int, de.grogra.vecmath.geom.IntersectionList, de.grogra.vecmath.geom.Intersection, de.grogra.vecmath.geom.Intersection, de.grogra.vecmath.geom.Octree.State)
and Octree.Cell.getVolume(int, de.grogra.vecmath.geom.Octree.State)
.
State
subclassprotected void finishCells()
public int getCellCount()
public int getDepth()
protected abstract java.util.ArrayList getInfiniteVolumes()
null
public Point3d getMax()
public Point3d getMin()
public Octree.Cell getRoot()
protected void initialize(int maxDepth, int minObjects, Tuple3d min, Tuple3d max, Octree.Cell root)
root
cell has to contain
all finite volumes, it will be subdivided by this method.
maxDepth
 maximum allowed depth of octreeminObjects
 minimum volumes per cell. Only cells having
more then minObjects
volumes are checked for
subdivisionmin
 minimum coordinates of octree boxmax
 maximum coordinates of octree boxroot
 root cell of the octreepublic static int suggestDepth(int numberOfVolumes)
numberOfVolumes
. The computed value minimizes
the heuristic cost function
numberOfVolumes
and r the relative cost
of passing an octree cell compared to intersecting a volume. The
first part of this function estimates the number of
ray/volume intersections for a single ray, the second part
estimates the number of passed octree cells.
Based on experimental data, r = 0.1 has been chosen.
numberOfVolumes
 number of volumes in the scene


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 