de.grogra.vecmath.geom
Class Octree

java.lang.Object
  de.grogra.vecmath.geom.Octree

public abstract class Octree
extends java.lang.Object

Abstract base class for octrees.

Author:

Michael Tauer, Ole Kniemeyer

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

MAX_DEPTH

public static final int MAX_DEPTH

The maximum depth which can be handled by this octree implementation. No subdivision corresponds to a depth of 0, a single subdivision in eight cells to a depth of 1 etc.

See Also:

Constant Field Values

MAX_GRID_SIZE

public static final int MAX_GRID_SIZE

The grid size (number of cells in a single direction) which corresponds to the maximum depth, 1 << MAX_DEPTH.

See Also:

Constant Field Values

Constructor Detail

Octree

public Octree()

Method Detail

computeIntersections

public 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. 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.

Parameters:

line - a line

which - 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 list

excludeStart - 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()

Returns:

true iff the beginning of the line lies within the volume

createState

public abstract Octree.State createState()

This factory methods creates a new instance of 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).

Returns:

new instance of suitable State subclass

finishCells

protected void finishCells()

getCellCount

public int getCellCount()

Returns the number of octree cells of this octree.

Returns:

number of cells

getDepth

public int getDepth()

Returns the depth of this octree. A depth of 0 indicates that only the root cell is present etc.

Returns:

depth of octree

getInfiniteVolumes

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.

Returns:

list of infinite volumes, or null

getMax

public Point3d getMax()

Returns the maximum coordinates of the octree box. All finite objects are contained in this box. The returned value must not be modified.

Returns:

maximum coordinates of octree box

getMin

public Point3d getMin()

Returns the minimum coordinates of the octree box. All finite objects are contained in this box. The returned value must not be modified.

Returns:

minimum coordinates of octree box

getRoot

public Octree.Cell getRoot()

Returns the root cell of the octree. The cell hierarchy contains all finite volumes.

Returns:

root cell of octree

initialize

protected void initialize(int maxDepth,
                          int minObjects,
                          Tuple3d min,
                          Tuple3d max,
                          Octree.Cell root)

Initializes the octree. The root cell has to contain all finite volumes, it will be subdivided by this method.

Parameters:

maxDepth - maximum allowed depth of octree

minObjects - minimum volumes per cell. Only cells having more then minObjects volumes are checked for subdivision

min - minimum coordinates of octree box

max - maximum coordinates of octree box

root - root cell of the octree

suggestDepth

public static int suggestDepth(int numberOfVolumes)

Suggests a maximal octree depth for the given numberOfVolumes. The computed value minimizes the heuristic cost function c(d) = N / 4^d + r 2^d where N is 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.

Parameters:

numberOfVolumes - number of volumes in the scene

Returns:

suggested value for maximal octree depth