Overview | Package | Class | Tree | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 / 4d + r 2d
  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

Overview | Package | Class | Tree | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD