Commits

Michael Ludwig committed 2d3e831

Document Functions and SpatialIndices.

  • Participants
  • Parent commits 8c43dcf

Comments (0)

Files changed (5)

File ferox-math/src/main/java/com/ferox/math/Functions.java

 package com.ferox.math;
 
+/**
+ * Functions is a static collection of functions that provide additional or more
+ * performant alternatives to {@link Math}.
+ * 
+ * @author Michael Ludwig
+ */
 public final class Functions {
     private Functions() {}
     
+    /**
+     * <p>
+     * Compute the smallest power-of-two that is greater than or equal to the
+     * given integer. If num is less than or equal to 0, 1 is always returned.
+     * If num is already a power-of-two, num is returned.
+     * </p>
+     * <p>
+     * This runs in constant time.
+     * </p>
+     * 
+     * @param num The input
+     * @return Smallest power-of-two greater than or equal to num
+     */
     public static int potCeil(int num) {
         if (num <= 0)
             return 1;
         return num;
     }
     
+    /**
+     * Compute the integer log base 2 of the given number. If num is not a power
+     * of two (i.e. its log base 2 is not an integral value), this effectively
+     * returns <code>log2(potCeil(num))</code>. If num is less than or equal to
+     * 0, results are undefined.
+     * 
+     * @param num The number to compute the log base 2 of
+     * @return The log base 2 of the number, after rounding up to the nearest
+     *         power of two
+     */
     public static int log2(int num) {
         return 32 - Integer.numberOfLeadingZeros(num - 1);
     }
     
+    /**
+     * Return true if the given integer is a power of two. This is an efficient,
+     * constant time implementation. Numbers less than or equal to 0 will always
+     * return false.
+     * 
+     * @param num The number to check
+     * @return True if num is a power of two
+     */
     public static boolean isPowerOfTwo(int num) {
         if (num <= 0)
             return false;
         return (num & (num - 1)) == 0;
     }
-    
-    public static void main(String[] args) {
-        for (int i = -10; i <= 100; i++) {
-            int power2 = potCeil(i);
-            int log2Orig = log2(i);
-            int log2power = log2(power2);
-            boolean isPower2Orig = isPowerOfTwo(i);
-            boolean isPower2Power = isPowerOfTwo(power2);
-            
-            System.out.println(i + "(" + isPower2Orig + ") -> " + power2 + "(" + isPower2Power + "), log2: " + log2Orig + " -> " + log2power);
-        }
-    }
 }

File ferox-math/src/main/java/com/ferox/math/bounds/Octree.java

 import com.ferox.math.Vector3;
 import com.ferox.math.bounds.Frustum.FrustumIntersection;
 
+/**
+ * <p>
+ * Octree is a SpatialIndex implementation that uses a octree to efficiently
+ * cull areas in the viewing frustum that don't have objects within them. This
+ * particular implementation is a fully-allocated octree on top of a spatial
+ * grid. This means that inserts are almost constant time, and that AABB queries
+ * are very fast.
+ * </p>
+ * <p>
+ * Unless all three dimensions are required to suitably index the space,
+ * a {@link QuadTree} will generally perform faster and use less memory.
+ * </p>
+ * 
+ * @author Michael Ludwig
+ * @param <T> The data type stored in the octree
+ */
 public class Octree<T> implements SpatialIndex<T> {
     private static final int POS_X = 0x1;
     private static final int POS_Y = 0x2;
     
     private int queryIdCounter;
     
+    /**
+     * Construct a new Octree that has X, Y, and Z dimensions of 100, and an
+     * estimated object size of 2 units, which allows the tree to have a depth
+     * of 6.
+     */
     public Octree() {
         this(100, 2.0);
     }
     
+    /**
+     * <p>
+     * Construct a new Octree that has X, Y, and Z dimensions equal to
+     * <tt>sideLength</tt>, and the depth of the tree is controlled by the
+     * estimated object size, <tt>objSize</tt>. <tt>objSize</tt> should be the
+     * approximate dimension of the average object contained in this index. If
+     * it is too big or too small, query performance may suffer.
+     * </p>
+     * 
+     * @param sideLength The side length of the root bounds of the octree
+     * @param objSize The estimated object size
+     */
     public Octree(double sideLength, double objSize) {
         this(new AxisAlignedBox(new Vector3(-sideLength / 2.0, -sideLength / 2.0, -sideLength / 2.0),
                                 new Vector3(sideLength / 2.0, sideLength / 2.0, sideLength / 2.0)), 
              Functions.log2((int) Math.ceil(sideLength / objSize)));
     }
     
+    /**
+     * <P>
+     * Construct a new Octree with the given root bounds, <tt>aabb</tt> and tree
+     * depth. The depth of the tree and the X, Y, and Z dimensions of the root
+     * bounds determine the size the leaf octree nodes. If objects are
+     * significantly larger than this, they will be contained in multiple nodes
+     * and it may hurt performance.
+     * </p>
+     * <p>
+     * The root bounds are copied so future changes to <tt>aabb</tt> will not
+     * affect this tree.
+     * </p>
+     * 
+     * @param aabb The root bounds of the tree
+     * @param depth The depth of the tree
+     * @throws NullPointerException if aabb is null
+     */
     public Octree(@Const AxisAlignedBox aabb, int depth) {
         this.depth = depth;
         rootBounds = aabb.clone();
     
     @Override
     public boolean remove(T element) {
+        if (element == null)
+            throw new NullPointerException("Item cannot be null");
+        
         int item = -1;
         for (int i = 0; i < size; i++) {
             if (elements[i] == element) {
         }
     }
     
+    @Override
     public boolean add(T element, @Const AxisAlignedBox bounds) {
+        if (element == null)
+            throw new NullPointerException("Item cannot be null");
+        if (bounds == null)
+            throw new NullPointerException("Item bounds cannot be null");
+        
         if (!rootBounds.contains(bounds))
             return false; // skip the element
         
         return true;
     }
     
+    @Override
     public void clear() {
         clear(false);
     }
     
+    @Override
     public void clear(boolean fast) {
         // fill quadtree counts with 0s, but only up to the leaf nodes because
         // they hold cell indices, which don't change
         queryIdCounter = 0;
     }
     
+    @Override
     @SuppressWarnings("unchecked")
     public void query(@Const AxisAlignedBox bounds, QueryCallback<T> callback) {
+        if (bounds == null)
+            throw new NullPointerException("Bounds cannot be null");
+        if (callback == null)
+            throw new NullPointerException("Callback cannot be null");
+        
         // hash x/z of bounds and do spatial hash query over intersecting cells
         int minX = Math.max(0, hashCellX(bounds.min));
         int minY = Math.max(0, hashCellY(bounds.min));
         }
     }
     
+    @Override
     public void query(Frustum f, QueryCallback<T> callback) {
+        if (f == null)
+            throw new NullPointerException("Frustum cannot be null");
+        if (callback == null)
+            throw new NullPointerException("Callback cannot be null");
+        
         // start at root quadtree and walk the tree to compute intersections,
         // building in place an aabb for testing.
         query(0, 0, new AxisAlignedBox(rootBounds), ++queryIdCounter, 
         
         private int lifetime;
         
-        // this is the parent index of the quadtree index that actually holds
+        // this is the parent index of the octree index that actually holds
         // this cell, because the leaves don't store count information
         private final int quadTreeIndex;
         
-        private Cell(Octree<?> tree, int quadLeaf) {
-            quadTreeIndex = quadLeaf; //tree.getParentIndex(quadLeaf);
+        private Cell(Octree<?> tree, int octLeaf) {
+            quadTreeIndex = octLeaf;
             keys = new int[INCREMENT];
             size = 0;
             lifetime = 0;
             keys[size] = item;
             size++;
             
-            // update quadtree counts by 1
+            // update octree counts by 1
             updateTree(tree, 1);
         }
         
                     keys[i] = keys[size - 1];
                     size--;
                     
-                    // decrement quadtree counts by 1
+                    // decrement octree counts by 1
                     updateTree(tree, -1);
                     break;
                 }

File ferox-math/src/main/java/com/ferox/math/bounds/QuadTree.java

 import com.ferox.math.Vector3;
 import com.ferox.math.bounds.Frustum.FrustumIntersection;
 
+/**
+ * <p>
+ * QuadTree is a SpatialIndex implementation that uses a quadtree to efficiently
+ * cull areas in the viewing frustum that don't have objects within them. This
+ * particular implementation is a fully-allocated quadtree on top of a spatial
+ * grid. This means that inserts are almost constant time, and that AABB queries
+ * are very fast.
+ * </p>
+ * <p>
+ * The quadtree is extend to three dimensions by having the 2D quadtree defined
+ * in the XZ plane, and imposing a minimum and maximum Y value for every object
+ * within the quadtree. This means the quadtree is well suited to 3D games that
+ * predominantly 2D in their logic (i.e. an RTS).
+ * </p>
+ * 
+ * @author Michael Ludwig
+ * @param <T> The data type stored in the quadtree
+ */
 public class QuadTree<T> implements SpatialIndex<T> {
     private static final int POS_X = 0x1;
     private static final int POS_Y = 0x2;
     
     private int queryIdCounter;
     
+    /**
+     * Construct a new QuadTree that has X and Z dimensions of 100, and an
+     * estimated object size of 2 units, which allows the tree to have a depth
+     * of 6.
+     */
     public QuadTree() {
         this(100, 2.0);
     }
     
+    /**
+     * <p>
+     * Construct a new QuadTree that has X and Z dimensions equal to
+     * <tt>sideLength</tt>, and the depth of the tree is controlled by the
+     * estimated object size, <tt>objSize</tt>. <tt>objSize</tt> should be the
+     * approximate dimension of the average object contained in this index. If
+     * it is too big or too small, query performance may suffer.
+     * </p>
+     * <p>
+     * The height of the root bounds is estimated as 20 times the object size.
+     * </p>
+     * 
+     * @param sideLength The side length of the root bounds of the quadtree
+     * @param objSize The estimated object size
+     */
     public QuadTree(double sideLength, double objSize) {
-        this(new AxisAlignedBox(new Vector3(-sideLength / 2.0, -100 * objSize, -sideLength / 2.0),
-                                new Vector3(sideLength / 2.0, 100 * objSize, sideLength / 2.0)), 
+        this(new AxisAlignedBox(new Vector3(-sideLength / 2.0, -10 * objSize, -sideLength / 2.0),
+                                new Vector3(sideLength / 2.0, 10 * objSize, sideLength / 2.0)), 
              Functions.log2((int) Math.ceil(sideLength / objSize)));
     }
     
+    /**
+     * <P>
+     * Construct a new QuadTree with the given root bounds, <tt>aabb</tt> and
+     * tree depth. The depth of the tree and the X and Z dimensions of the root
+     * bounds determine the size the leaf quadtree nodes. If objects are
+     * significantly larger than this, they will be contained in multiple nodes
+     * and it may hurt performance.
+     * </p>
+     * <p>
+     * The root bounds are copied so future changes to <tt>aabb</tt> will not
+     * affect this tree.
+     * </p>
+     * 
+     * @param aabb The root bounds of the tree
+     * @param depth The depth of the tree
+     * @throws NullPointerException if aabb is null
+     */
     public QuadTree(@Const AxisAlignedBox aabb, int depth) {
+        if (aabb == null)
+            throw new NullPointerException("Root bounds cannot be null");
+        
         this.depth = depth;
         rootBounds = aabb.clone();
         
     
     @Override
     public boolean remove(T element) {
+        if (element == null)
+            throw new NullPointerException("Item cannot be null");
+        
         int item = -1;
         for (int i = 0; i < size; i++) {
             if (elements[i] == element) {
         }
     }
     
+    @Override
     public boolean add(T element, @Const AxisAlignedBox bounds) {
+        if (element == null)
+            throw new NullPointerException("Item cannot be null");
+        if (bounds == null)
+            throw new NullPointerException("Item bounds cannot be null");
+        
         if (!rootBounds.contains(bounds))
             return false; // skip the element
         
         return true;
     }
     
+    @Override
     public void clear() {
         clear(false);
     }
     
+    @Override
     public void clear(boolean fast) {
         // fill quadtree counts with 0s, but only up to the leaf nodes because
         // they hold cell indices, which don't change
         queryIdCounter = 0;
     }
     
+    @Override
     @SuppressWarnings("unchecked")
     public void query(@Const AxisAlignedBox bounds, QueryCallback<T> callback) {
+        if (bounds == null)
+            throw new NullPointerException("Bounds cannot be null");
+        if (callback == null)
+            throw new NullPointerException("Callback cannot be null");
+        
         // hash x/z of bounds and do spatial hash query over intersecting cells
         int minX = Math.max(0, hashCellX(bounds.min));
         int minY = Math.max(0, hashCellY(bounds.min));
         }
     }
     
+    @Override
     public void query(Frustum f, QueryCallback<T> callback) {
+        if (f == null)
+            throw new NullPointerException("Frustum cannot be null");
+        if (callback == null)
+            throw new NullPointerException("Callback cannot be null");
+        
         // start at root quadtree and walk the tree to compute intersections,
         // building in place an aabb for testing.
         query(0, 0, new AxisAlignedBox(rootBounds), ++queryIdCounter, 
         private final int quadTreeIndex;
         
         private Cell(QuadTree<?> tree, int quadLeaf) {
-            quadTreeIndex = quadLeaf; //tree.getParentIndex(quadLeaf);
+            quadTreeIndex = quadLeaf;
             keys = new int[INCREMENT];
             size = 0;
             lifetime = 0;

File ferox-math/src/main/java/com/ferox/math/bounds/SimpleSpatialIndex.java

  * SimpleSpatialIndex is a SpatialIndex that performs no spatial organization.
  * Each query performs a linear scan through the elements within the hierarchy.
  * Inserts, updates and removals are always constant time, and the
- * SimpleSpatialIndex always accepts every element added to it. It is intended
- * that this hierarchy be used to test the validity of other implementations, or
- * as a last-resort to contain items in a hierarch.
+ * SimpleSpatialIndex always accepts every element added to it.
  * 
  * @author Michael Ludwig
  * @param <T> The Class type of elements within this hierarchy

File ferox-math/src/main/java/com/ferox/math/bounds/SpatialIndex.java

  * A SpatialIndex partitions the three dimensions of a space to provide
  * efficient spatial queries. These queries are generally of the form: find all
  * objects that are within a certain region. For SpatialIndex, a region can
- * either be a {@link Frustum} or an {@link ReadOnlyAxisAlignedBox}. It is assumed that
- * each region exists within the same space as the SpatialHierachy.
+ * either be a {@link Frustum} or an {@link ReadOnlyAxisAlignedBox}. It is
+ * assumed that each region exists within the same transform space as the
+ * SpatialIndex.
  * </p>
  * <p>
- * Implementations of SpatialIndex are required to allow dynamic updates to
- * the objects within the hierarchy. This is often much faster than removing and
- * re-adding an object because much of the initial work that was done to place
- * the object initially will remain the same. This is because objects generally
- * have good spatial and temporal locality. To facilitate this, when an object
- * is added to the SpatialIndex, it has a key returned which contains the
- * implementation dependent information needed to quickly update an object's
- * location within the hierarchy.
+ * SpatialIndices are intended for collections of higher-level entities, such as
+ * a physics object, or entire geometries. It is not meant to store indices of
+ * the triangles within a geometry, although the algorithms will likely be very
+ * similar triangle/primitive specific indices will likely be much more
+ * efficient.
+ * </p>
+ * <p>
+ * If a SpatialIndex is meant to contain dynamic objects that move from
+ * frame-to-frame, the expected workflow is to add every object to the index,
+ * process with the index, and then clear it before the next frame. If sporadic
+ * updates to objects are needed, you must remove and then re-add the object.
  * </p>
  * 
  * @author Michael Ludwig
     /**
      * <p>
      * Add <tt>item</tt> to this SpatialIndex using the given <tt>bounds</tt> to
-     * represent the extents of the item. It is assumed that the item has not
-     * already been added. If this is the case,
-     * {@link #update(Object, ReadOnlyAxisAlignedBox, Object)} should be used
-     * instead. On a successful add, a non-null key is returned. This key must
-     * be used in {@link #update(Object, ReadOnlyAxisAlignedBox, Object)} and
-     * {@link #remove(Object, Object)} when modifying <tt>item</tt>.
+     * represent the extents of the item. If the item is already in the index,
+     * the item may be reported multiple times in queries.
      * </p>
      * <p>
      * Some implementations of SpatialIndex may have constraints on their
      * spatial dimensions. If <tt>bounds</tt> is unable to fit within these
-     * constraints, a null key is returned and the item was not added to the
+     * constraints, a false is returned and the item was not added to the
      * hierarchy.
      * </p>
      * <p>
      * Implementations must copy the provided bounds so that any subsequent
-     * changes to the bounds instance to do not contaminate the hierarchy.
+     * changes to the bounds instance to do not affect the index.
      * </p>
      * 
      * @param item The item to add
      * @param bounds The extends of <tt>item</tt>
-     * @return A key object representing where the item was placed in the
-     *         hierarchy, or null on a failure
+     * @return True if the item was added to the index, false otherwise
      * @throws NullPointerException if item or bounds is null
      */
     public boolean add(T item, @Const AxisAlignedBox bounds);
 
     /**
-     * Remove <tt>item</tt> from this hierarchy so that the given item can no
-     * longer be returned in queries to the SpatialIndex. The given
-     * <tt>key</tt> must be the key provided by a previous call to
-     * {@link #add(Object, ReadOnlyAxisAlignedBox)} and the given item must still be
-     * within the hierarchy. After removal, the key for an item is invalidated
-     * and a new key will be provided if the item is re-added.
+     * Remove <tt>item</tt> from this hierarchy so that the given item will no
+     * longer be returned in queries on the SpatialIndex. False is returned if
+     * the index was not modified (i.e. the item was not in this collection).
      * 
      * @param item The item to remove
-     * @param key The key previously returned by add() for this item
-     * @throws NullPointerException if item or key are null
-     * @throws IllegalArgumentException if the given key is invalid, or if item
-     *             isn't within the hierarchy
+     * @return True if the collection was modified
+     * @throws NullPointerException if item is null
      */
     public boolean remove(T item);
     
     /**
+     * Empty this SpatialIndex so that it no longer contains any items. If
+     * <tt>fast</tt> is true, the index is not required to remove references to
+     * old items. This can be more efficient if the index will be re-filled and
+     * the old references will be overwritten. However, this may also prevent
+     * items from being garbage collected if they are not overwritten.
      * 
-     * @param fast
+     * @param fast True if the index can optimize the clear
      */
     public void clear(boolean fast);
+    
+    /**
+     * Empty this SpatialIndex so that it no longer contains any items. This is
+     * a convenience for <code>clear(false);</code>.
+     */
+    public void clear();
 
     /**
      * <p>
-     * Query this SpatialIndex for all previously added items that have
-     * their provided bounds {@link ReadOnlyAxisAlignedBox#intersects(ReadOnlyAxisAlignedBox)
+     * Query this SpatialIndex for all previously added items that have their
+     * provided bounds
+     * {@link ReadOnlyAxisAlignedBox#intersects(ReadOnlyAxisAlignedBox)
      * intersecting} with <tt>volume</tt>.
      * </p>
      * <p>
      * The provided QueryCallback has its {@link QueryCallback#process(Object)}
-     * for each intersecting item. An item will be passed to the callback once
-     * per query.
+     * invoked for each intersecting item. An item will be passed to the
+     * callback once per query.
      * </p>
      * 
      * @param volume The volume representing the spatial query
 
     /**
      * <p>
-     * Query this SpatialIndex for all previously added items that have
-     * their provided bounds
-     * {@link ReadOnlyAxisAlignedBox#intersects(Frustum, PlaneState) intersecting} with
-     * <tt>frustum</tt>. An item's bounds intersects with the Frustum if its
-     * FrustumIntersection is not {@link FrustumIntersection#OUTSIDE}.
+     * Query this SpatialIndex for all previously added items that have their
+     * provided bounds
+     * {@link ReadOnlyAxisAlignedBox#intersects(Frustum, PlaneState)
+     * intersecting} with <tt>frustum</tt>. An item's bounds intersects with the
+     * Frustum if its FrustumIntersection is not
+     * {@link FrustumIntersection#OUTSIDE}.
      * </p>
      * <p>
      * The provided QueryCallback has its {@link QueryCallback#process(Object)}
-     * for each intersecting item. An item will be passed to the callback once
-     * per query.
+     * invoked for each intersecting item. An item will be passed to the
+     * callback once per query.
      * </p>
      * 
      * @param frustum The frustum representing the spatial query