Module vecmath
Package de.grogra.vecmath.geom

Class Octree

java.lang.Object
de.grogra.vecmath.geom.Octree
public abstract class Octree extends Object
Abstract base class for octrees.
Author:
Michael Tauer, Ole Kniemeyer

  • Field Details

    • 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:

    • 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:

  • Constructor Details

    • Octree

      public Octree()

  • Method Details

    • 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

    • finishCells

      protected void finishCells()

    • 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

    • 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

    • 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

    • getCellCount

      public int getCellCount()
      Returns the number of octree cells of this octree.
      Returns:
      number of cells

    • getRoot

      public Octree.Cell getRoot()
      Returns the root cell of the octree. The cell hierarchy contains all finite volumes.
      Returns:
      root cell of octree

    • 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

    • getInfiniteVolumes

      protected abstract 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

    • 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

    • 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