edu.mines.jtk.sgl
Class BoundingBoxTree

java.lang.Object
  edu.mines.jtk.sgl.BoundingBoxTree

public class BoundingBoxTree
extends java.lang.Object

A binary tree of axis-aligned bounding boxes for an array of points. This tree is useful when constructing a bounding volume hierarchy for large sets of geometric primitives such as triangles or quads.

Each node in the tree contains a bounding box for a a subset of points. Those points are represented by a subarray of indices of point (x,y,z) coordinates. Point coordinates are specified when constructing a tree.

The bounding box for the root node is that for the entire set of points, with indices 0 through n-1, where n is the total number of points in the tree. The tree recursively splits this bounding box in two so that each child represents roughly half of the points in its parent.

This recursive splitting continues while splits will create child nodes with numbers of points not less than a specified minimum. When the total number of points in the tree is less than the specified minimum, then the tree consists of only the root node.

A bounding box tree is much like a k-d tree for k=3 dimensions.

Version:

2006.06.24

Author:

Dave Hale, Colorado School of Mines

Nested Class Summary

class

BoundingBoxTree.Node A node in the binary tree of bounding boxes.

Constructor Summary

BoundingBoxTree(int minSize, float[] xyz)
Constructs a bounding box tree for points with specified coordinates.

BoundingBoxTree(int minSize, float[] x, float[] y, float[] z)
Constructs a bounding box tree for points with specified coordinates.

Method Summary

BoundingBoxTree.Node

getRoot() Gets the root node of this tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

BoundingBoxTree

public BoundingBoxTree(int minSize,
                       float[] xyz)

Constructs a bounding box tree for points with specified coordinates. The (x,y,z) coordinates are packed into the specified array such that (xyz[0],xyz[1],xyz[2]) are the (x,y,z) coordinates of the 1st point, (xyz[3],xyz[4],xyz[5]) are the (x,y,z) coordinates of the 2nd point, and so on.

Parameters:

minSize - the minimum number of points in a child node.

xyz - array of packed (x,y,z) coordinates.

BoundingBoxTree

public BoundingBoxTree(int minSize,
                       float[] x,
                       float[] y,
                       float[] z)

Constructs a bounding box tree for points with specified coordinates.

Parameters:

minSize - the minimum number of points in a child node.

x - array of x coordinates.

y - array of y coordinates.

z - array of z coordinates.

Method Detail

getRoot

public BoundingBoxTree.Node getRoot()

Gets the root node of this tree.

Returns:

the root node.