Michael Ludwig avatar Michael Ludwig committed 2d12fc5

Repair implementations of Octree and SimpleSpatialIndex

Comments (0)

Files changed (9)

ferox-math/src/main/java/com/ferox/math/bounds/Grid.java

-package com.ferox.math.bounds;
-
-public class Grid<T> implements SpatialIndex<T> {
-
-    @Override
-    public Object add(T item, ReadOnlyAxisAlignedBox bounds) {
-        // TODO Auto-generated method stub
-        return null;
-    }
-
-    @Override
-    public void update(T item, ReadOnlyAxisAlignedBox bounds, Object key) {
-        // TODO Auto-generated method stub
-        
-    }
-
-    @Override
-    public void remove(T item, Object key) {
-        // TODO Auto-generated method stub
-        
-    }
-
-    @Override
-    public void query(ReadOnlyAxisAlignedBox volume, QueryCallback<T> callback) {
-        // TODO Auto-generated method stub
-        
-    }
-
-    @Override
-    public void query(Frustum f, QueryCallback<T> callback) {
-        // TODO Auto-generated method stub
-        
-    }
-
-    @Override
-    public void query(IntersectionCallback<T> callback) {
-        // TODO Auto-generated method stub
-        
-    }
-
-}

ferox-math/src/main/java/com/ferox/math/bounds/IntersectionCallback.java

-package com.ferox.math.bounds;
-
-/**
- * IntersectionCallback is a callback that can be passed into a SpatialIndex
- * to discover all intersecting pairs of items within the hierarchy.
- * 
- * @author Michael Ludwig
- * @param <T> The item type processed by the callback, and stored in the
- *            hierarchy
- */
-public interface IntersectionCallback<T> {
-    /**
-     * <p>
-     * Invoked by a SpatialIndex when its
-     * {@link SpatialIndex#query(IntersectionCallback)} method is called,
-     * for each intersecting pair. The order of the items is not important, a
-     * SpatialIndex will only call process() once for each unique pair of
-     * items within it.
-     * </p>
-     * <p>
-     * Item intersection is determined by the bounds the items were last updated
-     * with, or their original bounds used when adding to the hierarchy, if they
-     * were never updated. These bounds are provided to the callback.
-     * </p>
-     * 
-     * @param itemA The first item in the intersection
-     * @param boundsA The first item's bounds
-     * @param itemB The second item in the intersection
-     * @param boundsB The second item's bounds
-     */
-    public void process(T itemA, ReadOnlyAxisAlignedBox boundsA, T itemB, ReadOnlyAxisAlignedBox boundsB);
-}

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

 import java.util.HashSet;
 import java.util.Set;
 
-import com.ferox.math.ReadOnlyVector3f;
-import com.ferox.math.Vector3f;
+import com.ferox.math.Const;
+import com.ferox.math.Vector3;
 import com.ferox.math.bounds.Frustum.FrustumIntersection;
 import com.ferox.util.Bag;
 
  * Octree is a SpatialIndex implementation that represents the octree data
  * structure. The octree partitions space into an organized hierarchy of cubes.
  * A cube node within the octree can be evenly split into 8 nested cubes which
- * partition its space. Many octree implementations restrict the size of the
- * root node, but this implementation can expand as needed to include items.
- * Similarly, this octree supports relatively fast updates for moving objects.
+ * partition its space.
  * </p>
  * <p>
  * This octree only stores items as deep as possible before they overlap an edge
  * of a node. This means that updates and removals are very fast, but many items
- * can be placed at the top of the tree, reducing the efficiency of queries
- * (especially intersection pair queries).
+ * can be placed at the top of the tree, reducing the efficiency of queries.
  * </p>
  * 
  * @author Michael Ludwig
     private Node<T> root;
     private final AxisAlignedBox rootBounds; // all other node bounds implicit from this
     
-    private final Bag<Key<T>> nullBounds;
     private final Set<Node<T>> pendingRemovals;
 
     /**
      * Create a new Octree with dimensions of 100 and an initial max depth of 6.
-     * As the octree expands to enclose more nodes, its depth and dimensions can
-     * increase.
      */
     public Octree() {
-        this(100f);
+        this(100.0);
     }
 
     /**
      * @param side The desired side length for the root node
      * @throws IllegalArgumentException if side is less than 0
      */
-    public Octree(float side) {
+    public Octree(double side) {
         this(side, DEFAULT_MAX_DEPTH);
     }
 
      * @throws IllegalArgumentException if side is less than 0, or if
      *             initialMaxDepth < 1
      */
-    public Octree(float side, int initialMaxDepth) {
-        this(new AxisAlignedBox(new Vector3f(-side / 2f, -side / 2f, -side / 2f), 
-                                new Vector3f(side / 2f, side / 2f, side / 2f)),
+    public Octree(double side, int initialMaxDepth) {
+        this(new AxisAlignedBox(new Vector3(-side / 2, -side / 2, -side / 2), 
+                                new Vector3(side / 2, side / 2, side / 2)),
              initialMaxDepth);
     }
 
      * @param extents The desired root node bounds
      * @throws NullPointerException if extents is null
      */
-    public Octree(ReadOnlyAxisAlignedBox extents) {
+    public Octree(@Const AxisAlignedBox extents) {
         this(extents, DEFAULT_MAX_DEPTH);
     }
 
      * @throws NullPointerException if extents is null
      * @throws IllegalArgumentException if initialMaxDepth < 1
      */
-    public Octree(ReadOnlyAxisAlignedBox extents, int initialMaxDepth) {
+    public Octree(@Const AxisAlignedBox extents, int initialMaxDepth) {
         if (extents == null)
             throw new NullPointerException("Extents cannot be null");
         if (initialMaxDepth <= 0)
             throw new IllegalArgumentException("Initial max depth must be at least 1, not: " + initialMaxDepth);
-        if (extents.getMax().getX() < extents.getMin().getX() ||
-            extents.getMax().getY() < extents.getMin().getY() ||
-            extents.getMax().getZ() < extents.getMin().getZ())
+        if (extents.max.x < extents.min.x ||
+            extents.max.y < extents.min.y ||
+            extents.max.z < extents.min.z)
             throw new IllegalArgumentException("Invalid root bounds: " + extents);
         
         rootBounds = new AxisAlignedBox(extents);
         root = new Node<T>(null, initialMaxDepth - 1);
-        nullBounds = new Bag<Key<T>>();
         pendingRemovals = new HashSet<Node<T>>();
         
         queryNumber = 0;
     }
     
     @Override
-    public Object add(T item, ReadOnlyAxisAlignedBox bounds) {
+    public Object add(T item, @Const AxisAlignedBox bounds) {
         if (item == null)
             throw new NullPointerException("Item cannot be null");
         
-        expandOctreeMaybe(bounds);
-        Key<T> newKey = new Key<T>(item, bounds, this);
-        if (bounds == null) {
-            newKey.addToNull();
-        } else
+        if (inOctree(bounds)) {
+            Key<T> newKey = new Key<T>(item, bounds, this);
             newKey.addToRoot();
-        
-        return newKey;
+
+            return newKey;
+        } else {
+            // can't fit in tree
+            return null;
+        }
     }
 
     @Override
             Key<T> ok = (Key<T>) key;
             if (ok.owner == this && ok.data == item) {
                 // key is valid, now remove it
-                if (ok.bounds == null)
-                    ok.removeFromNull();
-                else
-                    ok.removeFromRoot();
+                ok.removeFromRoot();
                 return;
             }
         }
     }
 
     @Override
-    public void update(T item, ReadOnlyAxisAlignedBox bounds, Object key) {
+    public boolean update(T item, @Const AxisAlignedBox bounds, Object key) {
         if (item == null)
             throw new NullPointerException("Item cannot be null");
         if (key == null)
         if (key instanceof Key) {
             Key<T> ok = (Key<T>) key;
             if (ok.owner == this && ok.data == item) {
-                // key is valid, so update it
-                expandOctreeMaybe(bounds);
-                ok.update(bounds);
-                return;
+                // key is valid
+                if (inOctree(bounds)) {
+                    // item is still in the octree, so update it
+                    ok.update(bounds);
+                    return true;
+                } else {
+                    // item has moved outside of the tree, so remove it
+                    ok.removeFromRoot();
+                    return false;
+                }
             }
         }
         
     }
     
     @Override
-    public void query(ReadOnlyAxisAlignedBox volume, QueryCallback<T> callback) {
+    public void query(@Const AxisAlignedBox volume, QueryCallback<T> callback) {
         if (volume == null)
             throw new NullPointerException("Query volume cannot be null");
         if (callback == null)
         pruneTree();
         
         root.visitIntersecting(volume, new AabbQueryCallback<T>(callback, ++queryNumber), rootBounds, false);
-        
-        // now report all null bound elements, too
-        int count = nullBounds.size();
-        for (int i = 0; i < count; i++)
-            callback.process(nullBounds.get(i).data);
     }
 
     @Override
         
         if (rootTest != FrustumIntersection.OUTSIDE)
             root.visitFrustum(f, new FrustumQueryCallback<T>(callback, planeState, ++queryNumber), rootBounds, planeState);
-        
-        // visit all children with null bounds
-        int count = nullBounds.size();
-        for (int i = 0; i < count; i++)
-            callback.process(nullBounds.get(i).data);
-    }
-
-    @Override
-    public void query(IntersectionCallback<T> callback) {
-        if (callback == null)
-            throw new NullPointerException("Callback cannot be null");
-        
-        // prune tree before query to make it the most efficient possible
-        pruneTree();
-        queryIntersections(root, callback);
-    }
-    
-    /*
-     * Internal implementations of queries based on the supported strategies
-     */
-    
-    private void queryIntersections(Node<T> node, IntersectionCallback<T> callback) {
-        // append all intersections within this node
-        detectIntersections(node, node, callback);
-        
-        // traverse parents
-        Node<T> p = node.parent;
-        while(p != null) {
-            detectIntersections(node, p, callback);
-            p = p.parent;
-        }
-        
-        // recurse to children
-        if (node.children != null) {
-            for (int i = 0; i < node.children.length; i++) {
-                if (node.children[i] != null)
-                    queryIntersections(node.children[i], callback);
-            }
-        }
-    }
-    
-    private void detectIntersections(Node<T> n1, Node<T> n2, IntersectionCallback<T> callback) {
-        if (n1.items == null || n2.items == null)
-            return; // can't have any intersections
-        
-        Key<T> e1, e2;
-        
-        // find intersections between n1 and n2's children
-        if (n1 == n2) {
-            // same node optimizations
-            int ct = n1.items.size();
-            for (int i = 0; i < ct; i++) {
-                e1 = n1.items.get(i);
-                for (int j = i + 1; j < ct; j++) {
-                    e2 = n1.items.get(j);
-                    if (e1.bounds.intersects(e2.bounds))
-                        callback.process(e1.data, e2.data);
-                }
-            }
-        } else {
-            int ct1 = n1.items.size();
-            int ct2 = n2.items.size();
-
-            for (int i = 0; i < ct1; i++) {
-                e1 = n1.items.get(i);
-                for (int j = 0; j < ct2; j++) {
-                    e2 = n2.items.get(j);
-                    if (e1.bounds.intersects(e2.bounds))
-                        callback.process(e1.data, e2.data);
-                }
-            }
-        }
     }
     
     /*
         pendingRemovals.clear();
     }
     
-    private void expandOctreeMaybe(ReadOnlyAxisAlignedBox dataBounds) {
-        if (dataBounds == null || rootBounds.contains(dataBounds))
-            return;
-        
-        ReadOnlyVector3f dMin = dataBounds.getMin();
-        
-        Vector3f extents = new Vector3f();
-        Vector3f center = new Vector3f();
-        
-        Node<T> newRoot;
-        
-        ReadOnlyVector3f rMin, rMax;
-        int rootChildIndex;
-        while(!rootBounds.contains(dataBounds)) {
-            // the current root will be placed within the positive 
-            // half-plane for any axis if it is even partially above
-            // the data bounds, otherwise it is in the negative
-            rootChildIndex = 0;
-            rMin = rootBounds.getMin();
-            rMax = rootBounds.getMax();
-            if (rMin.getX() > dMin.getX()) {
-                rootChildIndex |= POS_X;
-                center.setX(rMin.getX());
-            } else
-                center.setX(rMax.getX());
-            
-            if (rMin.getY() > dMin.getY()) {
-                rootChildIndex |= POS_Y;
-                center.setY(rMin.getY());
-            } else
-                center.setY(rMax.getY());
-            
-            if (rMin.getZ() > dMin.getZ()) {
-                rootChildIndex |= POS_Z;
-                center.setZ(rMin.getZ());
-            } else
-                center.setZ(rMax.getZ());
-            
-            rMax.sub(rMin, extents); // get axis lengths of the root
-            rootBounds.getMin().set(center.getX() - extents.getX(), center.getY() - extents.getY(), center.getZ() - extents.getZ());
-            rootBounds.getMax().set(center.getX() + extents.getX(), center.getY() + extents.getY(), center.getZ() + extents.getZ());
-            
-            newRoot = new Node<T>(null, root.depth + 1);
-            newRoot.children = new Node[8];
-            newRoot.children[rootChildIndex] = root;
-            
-            root.parent = newRoot;
-            root = newRoot;
-        }
+    private boolean inOctree(@Const AxisAlignedBox dataBounds) {
+        if (dataBounds == null)
+            throw new NullPointerException("Bounds cannot be null");
+        return rootBounds.contains(dataBounds);
     }
     
     /*
     private static boolean inPositiveZ(int index) {
         return (index & POS_Z) != 0;
     }
-    private static int getChildIndex(ReadOnlyAxisAlignedBox nodeBounds, ReadOnlyVector3f pointInNode) {
-        ReadOnlyVector3f min = nodeBounds.getMin();
-        ReadOnlyVector3f max = nodeBounds.getMax();
-        
+    private static int getChildIndex(@Const AxisAlignedBox nodeBounds, @Const Vector3 pointInNode) {
         int index = 0;
-        if ((min.getX() + max.getX()) < 2f * pointInNode.getX())
+        if ((nodeBounds.min.x + nodeBounds.max.x) < 2 * pointInNode.x)
             index |= POS_X;
-        if ((min.getY() + max.getY()) < 2f * pointInNode.getY())
+        if ((nodeBounds.min.y + nodeBounds.max.y) < 2 * pointInNode.y)
             index |= POS_Y;
-        if ((min.getZ() + max.getZ()) < 2f * pointInNode.getZ())
+        if ((nodeBounds.min.z + nodeBounds.max.z) < 2 * pointInNode.z)
             index |= POS_Z;
         return index;
     }
     
     private static void updateForChild(int child, AxisAlignedBox bounds) {
-        Vector3f min = bounds.getMin();
-        Vector3f max = bounds.getMax();
-        
         if (inPositiveX(child))
-            min.setX((min.getX() + max.getX()) / 2f);
+            bounds.min.x = (bounds.min.x + bounds.max.x) / 2;
         else
-            max.setX((min.getX() + max.getX()) / 2f);
+            bounds.max.x = (bounds.min.x + bounds.max.x) / 2;
         
         if (inPositiveY(child))
-            min.setY((min.getY() + max.getY()) / 2f);
+            bounds.min.y = (bounds.min.y + bounds.max.y) / 2;
         else
-            max.setY((min.getY() + max.getY()) / 2f);
+            bounds.max.y = (bounds.min.y + bounds.max.y) / 2;
         
         if (inPositiveZ(child))
-            min.setZ((min.getZ() + max.getZ()) / 2f);
+            bounds.min.z = (bounds.min.z + bounds.max.z) / 2;
         else
-            max.setZ((min.getZ() + max.getZ()) / 2f);
+            bounds.max.z = (bounds.min.z + bounds.max.z) / 2;
     }
     
     private static void updateForParent(int child, AxisAlignedBox bounds) {
-        Vector3f min = bounds.getMin();
-        Vector3f max = bounds.getMax();
-        
         if (inPositiveX(child))
-            min.setX(2 * min.getX() - max.getX());
+            bounds.min.x = 2 * bounds.min.x - bounds.max.x;
         else
-            max.setX(2 * max.getX() - min.getX());
+            bounds.max.x = 2 * bounds.max.x - bounds.min.x;
         
         if (inPositiveY(child))
-            min.setY(2 * min.getY() - max.getY());
+            bounds.min.y = 2 * bounds.min.y - bounds.max.y;
         else
-            max.setY(2 * max.getY() - min.getY());
+            bounds.max.y = 2 * bounds.max.y - bounds.min.y;
         
         if (inPositiveZ(child))
-            min.setZ(2 * min.getZ() - max.getZ());
+            bounds.min.z = 2 * bounds.min.z - bounds.max.z;
         else
-            max.setZ(2 * max.getZ() - min.getZ());
+            bounds.max.z = 2 * bounds.max.z - bounds.min.z;
     }
     
     private static class Node<T> {
          * @param createChildren True if child nodes can be created if they'd be
          *            contained in the query
          */
-        public void visitContaining(ReadOnlyAxisAlignedBox query, NodeCallback<ReadOnlyAxisAlignedBox, T> callback, AxisAlignedBox nodeBounds, boolean createChildren) {
+        public void visitContaining(@Const AxisAlignedBox query, NodeCallback<AxisAlignedBox, T> callback, AxisAlignedBox nodeBounds, boolean createChildren) {
             // since we assume this node contains query, run the callback right away
             callback.visit(query, this, nodeBounds);
             
             // now visit children, if we have any
             if (!isLeaf() && (children != null || createChildren)) {
-                int minChildIndex = getChildIndex(nodeBounds, query.getMin());
-                int maxChildIndex = getChildIndex(nodeBounds, query.getMax());
+                int minChildIndex = getChildIndex(nodeBounds, query.min);
+                int maxChildIndex = getChildIndex(nodeBounds, query.max);
                 
                 if (minChildIndex == maxChildIndex) {
                     // query fits within a single child, so we can go deeper
          * @param createChildren True if child nodes can be created if they'd be
          *            contained in the query
          */
-        public void visitIntersecting(ReadOnlyAxisAlignedBox query, NodeCallback<ReadOnlyAxisAlignedBox, T> callback, AxisAlignedBox nodeBounds, boolean createChildren) {
+        public void visitIntersecting(@Const AxisAlignedBox query, NodeCallback<AxisAlignedBox, T> callback, AxisAlignedBox nodeBounds, boolean createChildren) {
             // visit the callback
             callback.visit(query, this, nodeBounds);
             
             if (!isLeaf() && (children != null || createChildren)) {
-                int minIndex = getChildIndex(nodeBounds, query.getMin());
-                int maxIndex = getChildIndex(nodeBounds, query.getMax());
+                int minIndex = getChildIndex(nodeBounds, query.min);
+                int maxIndex = getChildIndex(nodeBounds, query.max);
                 int constraint = ~(minIndex ^ maxIndex);
                 int childMatch = minIndex & constraint; // note that maxIndex & constraint would work too
                 
         Node<T> parent;
         int nodeIndex;
         
-        AxisAlignedBox bounds;
+        final AxisAlignedBox bounds;
         int queryNumber;
         
-        public Key(T data, ReadOnlyAxisAlignedBox bounds, Octree<T> owner) {
+        public Key(T data, @Const AxisAlignedBox bounds, Octree<T> owner) {
             this.data = data;
             this.owner = owner;
-            this.bounds = (bounds == null ? null : new AxisAlignedBox(bounds));
+            this.bounds = new AxisAlignedBox(bounds);
         }
         
-        public void removeFromNull() {
-            owner.nullBounds.remove(nodeIndex);
-            if (owner.nullBounds.size() != nodeIndex)
-                owner.nullBounds.get(nodeIndex).nodeIndex = nodeIndex;
-            nodeIndex = -1;
-        }
-        
-        public void addToNull() {
-            owner.nullBounds.add(this);
-            nodeIndex = owner.nullBounds.size() - 1;
-        }
-        
-        public void update(ReadOnlyAxisAlignedBox newBounds) {
-            if (newBounds == null) {
-                if (bounds != null) {
-                    // bounds switched to null, so remove it from root and add to null list
-                    removeFromRoot();
-                    addToNull();
-                } // else, no real update occurred
-            } else {
-                if (bounds == null) {
-                    // bounds switched from null, do a full add
-                    removeFromNull();
-                    bounds = new AxisAlignedBox(newBounds);
-                    addToRoot();
-                } else {
-                    // regular update within the tree, do a remove and then a re-add
-                    if (!bounds.equals(newBounds)) {
-                        removeFromRoot();
-                        bounds.set(newBounds);
-                        addToRoot();
-                    }
-                }
+        public void update(@Const AxisAlignedBox newBounds) {
+            // regular update within the tree, do a remove and then a re-add
+            if (!bounds.equals(newBounds)) {
+                removeFromRoot();
+                bounds.set(newBounds);
+                addToRoot();
             }
         }
         
      */
     
     private static interface NodeCallback<Q, T> {
-        public void visit(Q query, Node<T> node, ReadOnlyAxisAlignedBox nodeBounds);
+        public void visit(Q query, Node<T> node, AxisAlignedBox nodeBounds);
     }
     
-    private static class DeepestNodeCallback<T> implements NodeCallback<ReadOnlyAxisAlignedBox, T> {
+    private static class DeepestNodeCallback<T> implements NodeCallback<AxisAlignedBox, T> {
         Node<T> deepestNode;
         
         @Override
-        public void visit(ReadOnlyAxisAlignedBox query, Node<T> node, ReadOnlyAxisAlignedBox nodeBounds) {
+        public void visit(@Const AxisAlignedBox query, Node<T> node, AxisAlignedBox nodeBounds) {
             if (deepestNode == null || node.depth < deepestNode.depth)
                 deepestNode = node;
         }
     }
     
-    private static class AabbQueryCallback<T> implements NodeCallback<ReadOnlyAxisAlignedBox, T> {
+    private static class AabbQueryCallback<T> implements NodeCallback<AxisAlignedBox, T> {
         final QueryCallback<T> callback;
         final int query;
         
         }
         
         @Override
-        public void visit(ReadOnlyAxisAlignedBox query, Node<T> node, ReadOnlyAxisAlignedBox nodeBounds) {
+        public void visit(@Const AxisAlignedBox query, Node<T> node, AxisAlignedBox nodeBounds) {
             if (node.items != null) {
                 Key<T> key;
                 int count = node.items.size();
                     key.queryNumber = this.query;
                     
                     if (query.intersects(key.bounds))
-                        callback.process(key.data);
+                        callback.process(key.data, key.bounds);
                 }
             }
         }
         }
         
         @Override
-        public void visit(Frustum query, Node<T> node, ReadOnlyAxisAlignedBox nodeBounds) {
+        public void visit(Frustum query, Node<T> node, AxisAlignedBox nodeBounds) {
             if (node.items != null) {
                 // save old plane state to restore after each child
                 int save = ps.get();
                     key.queryNumber = this.query;
                     
                     if (key.bounds.intersects(query, ps) != FrustumIntersection.OUTSIDE)
-                        callback.process(key.data);
+                        callback.process(key.data, key.bounds);
                     
                     // restore plane state
                     ps.set(save);

ferox-math/src/main/java/com/ferox/math/bounds/Octree2.java

-package com.ferox.math.bounds;
-
-public class Octree2 {
- // FIXME: I think the Octree class can be heavily optimized and improved/simplified
-    // I need to decide to which style of octree is best, or if I need both: data stored in multiple leaves,
-    // or data stored in smallest containing node.
-    
-    // I will need to analyze the situations where each performs the best, and
-    // then determine how that fits in with Grid's responsibilities.
-    
-    // It would be nice if I could simplify the use of interfaces within Octree
-    // so that I could avoid that type abstraction.  Additionally, if I could somehow
-    // figure out how to pack the data so that the queries can somehow take advantage
-    // of the memory cache, that would be great.
-    //  - The memory cache is probably a bust, a linear octree requires a layout
-    //    pattern that represents a space-filling curve, and I feel like that might
-    //    not have the best cache performance.
-    
-    // So what are the pros/cons of a leaf-only octree, dynamic octree, and grid:
-    // Grid:
-    //   - constant memory size based on grid dimensions -> pro
-    //   - 3D memory cost limits size of grid to something small like 16, even 32 is getting up to 32000 grid cells
-    //   - constant iteration cost over all cells, which can be costly for visibility of a general frustum
-    //   - visibility query could be implemented like an octree query
-    //   - but then you might as well allocate a complete leaf-only octree and use that
-    //   - if z was limited, grid might pay off more because you could put more resolution in xy planes
-    
-    // leaf-only octree:
-    //   - visibility queries with frustums have overwork since you might encounter the same object in more than one cell
-    //   - as a hierarchy, its queries will theoretically be faster than a grid, especially if many things are outside of view
-    //   - a complete tree is better, otherwise memory use is unpredictable and potentially breaking if oom occurs
-    //   - hot spots will not occur, because they will just go in multiple cells
-    //   - updates/moving objects are expensive, although with a complete tree it might be less so, so long as you could still keep track of emptiness of zones, etc.
-    
-    // dynamic octrees
-    //   - visibility queries are theoretically efficient because you will only see something once in the tree
-    //   - however, hot spots occur which can push objects up to higher than expected nodes, and congest the root making performance hit n^2
-    //   - updates are pretty fast since you can walk from the current node up and/or down until the new bounds are completely contained
-    //   - intersection queries between elements suffer from hot spots as well
-    //   - general aabb queries are still pretty fast although hot spots still hurt
-    
-    // loose octree:
-    //   - this might be a better solution to the dynamic octree since it removes hot spots
-    //   - each node has a buffer around it that elements can fit into, allowing smaller objects to still fit within low level or leaf nodes
-    //     large objects on edges still move up to the root, but those should be few so it's not an issue
-    //   - intersection between entities will be more expensive but it might be entirely reasonable for 
-    //     visibility queries.
-    //
-    
-    
-    // I think I should write a fast static octree that is complete, with the understanding that most octrees,
-    // don't require that high of a resolution.  I will not need to implement growing or node removal,
-    // if I can keep track of node counts.  With this, I might be able to get updates faster than a total
-    // removal and then re-add.
-    //
-    // The static octree will be good enough and do better than the grid I think, although being able to
-    // limit resolution along a certain dimension seems valuable, although if I don't need to allocate
-    // the complete tree, I get the same benefits.  Hmmm, there is a trade off here, I should investigate how
-    // much memory is actually used up.
-    
-    //  EX: 32x32x32 is the leaf-level of the octree.  That is 33000 leafs, no array 0+ elements in each
-    //   next is 16x16x16 -> 4000 nodes, each with an array of 8
-    //   next is 8x8x8 -> 512 nodes, each with an array of 8
-    //   next is 4x4x4 -> 64 nodes, each ""
-    //   next is 2x2x2 -> 8 nodes, each ""
-    //   next is 1x1x1 -> 1 node, with an array of 8
-    
-    // That is < 5000 8 element arrays -> 5000 lightweight objects + 40000 length array
-    // and 33000 more lightweight leafs (assuming separate type)
-    // each of these might take an int, plus 2 or 3 points, so lets say 32 bytes per object
-    // 38000 * 32 + 40000 * 4 = 1376000 = 1.3 MB
-    
-    // That doesn't seem terrible, although 64x64x64 is probably getting more expensive, closer to 10MB
-    
-    // Of course, if I allow for the static octree to not be fully allocated at the start, then I really
-    // don't need to worry about the grid as an index option since the portions of the octree not filled
-    // will not be allocated.  This is probably what people expect, but then I have to figure out how
-    // to make the updates faster than remove/add.
-    //
-    // Looking at the graphs from gamedev.net, sort/sweep will be the best for finding pairs of intersections.
-    // a grid does reasonably, but would require maintenance.  sorting is pretty quick
-    // Does this mean I should remove the intersections pair query from spatial-index? It would mean that
-    // the physics engine cannot use plugin spatial indices, which is kind of lame but than again if I'm
-    // just doing axis sweeping why spend the trouble when the rest of the spatial index is best used for
-    // single-input queries.
-    
-    // I think it would be best to remove the intersection-pairs query from the interface, but I should
-    // add one that supports ray queries.
-    // - This brings up the point that we should support some potentially more detailed bounds or shape
-    //   description to support building trees about primitives, or more specific bounds than the aabb.
-    // - This would also let me reuse some code if I ever wanted to get into raytracing (wait a while why don't you)
-    // - Also per-triangle picking support would be pretty cool since that is what the ray query will
-    //   be most used for in the game engine (and not a ray tracer)
-    
-    // Is it required for the spatial indices to store aabb's for every element? If we go ahead and put
-    // triangles into the index, there would be an aabb per triangle which for large models would be too
-    // expensive.  In some cases, it seems much better to take some interface that can be used to
-    // query its edges or intersections or something.
-    
-    
-    // Other decisions that I have made are:
-    // 1. The visibility system will generate a list of objects so that it can be iterated over.
-    //     This will be a significant performance boost when most objects are not visible, which I 
-    //     think is a reasonable assumption.
-    // 2. I need to figure out how this information is passed around since the key store system
-    //     doesn't work when part of the key depends on the given camera.
-    //     The genericness of the setVisible() on renderable is still good and that will stay around I think,
-    //     but I want to provide an alternate access path
-    // 3. I'm not sure what to do about light influences, since only 2 out of 3 renderers care about them,
-    //     because deferred shaders just handle the lights directly.  Is it worth embedding that
-    //     information in with Material?  Is it weird to have deferred shaders ignore that information
-    //     or disable its computation?
-    // 4. I do not like that the vector/matrices of a component are shared by all components, I'm positive
-    //    that that will become bug prone.  It would be simpler if there were only canonical instances,
-    //    since we can't do caching on the component instance when multiple instances could point to the
-    //    same component.
-    
-    // I think the solution I came up with for information sharing is to have some way of describing
-    // interests, so anyone can ask for "controllers interested in visible entities" and then 
-    // send the entities to them, and certain controllers would then expose this interest. Now I'm
-    // not sure exactly what this interface would be because you'd have to specify the entity as well as
-    // the camera.  Mayhaps the "interest" is an interface that exposes the injection methods.
-}

ferox-math/src/main/java/com/ferox/math/bounds/Plane.java

     }
     
     // FIXME: verify behavior, math and document behavior
+    // FIXME: this doesn't have much to do with Planes, so we should move it somewhere
+    // else
     public static void getTangentSpace(@Const Vector3 normal, Vector3 tan0, Vector3 tan1) {
         // Gratz to Erwin Couman's and Bullet for this code
         

ferox-math/src/main/java/com/ferox/math/bounds/QueryCallback.java

 package com.ferox.math.bounds;
 
+import com.ferox.math.Const;
+
 /**
  * QueryCallback is a callback that can be passed into a SpatialIndex when
  * querying the hierarchy with a frustum or box query.
     /**
      * <p>
      * Invoked by a SpatialIndex when its
-     * {@link SpatialIndex#query(ReadOnlyAxisAlignedBox, QueryCallback)} or
+     * {@link SpatialIndex#query(AxisAlignedBox, QueryCallback)} or
      * {@link SpatialIndex#query(Frustum, QueryCallback)} method is called, for
      * each item satisfying the query.
      * </p>
      * updated with, or their original bounds used when adding to the hierarchy,
      * if they were never updated. The bounds of the item are provided to the
      * callback, although the instance should not be held onto as the
-     * SpatialIndex may cache the instance.
+     * SpatialIndex may re-use the instance for the next item.
+     * </p>
+     * <p>
+     * Similarly, the bounds should not be modified.
      * </p>
      * 
      * @param item The item passing the query
      * @param bounds The bounds the given item had in the index
      */
-    public void process(T item, ReadOnlyAxisAlignedBox bounds);
+    public void process(T item, @Const AxisAlignedBox bounds);
 }

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

 package com.ferox.math.bounds;
 
+import com.ferox.math.Const;
 import com.ferox.math.bounds.Frustum.FrustumIntersection;
 import com.ferox.util.Bag;
 
 /**
- * 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.
+ * 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.
  * 
  * @author Michael Ludwig
  * @param <T> The Class type of elements within this hierarchy
     }
     
     @Override
-    public Object add(T item, ReadOnlyAxisAlignedBox bounds) {
+    public Object add(T item, @Const AxisAlignedBox bounds) {
         if (item == null)
             throw new NullPointerException("Item cannot be null");
-        SimpleKey<T> newKey = new SimpleKey<T>(this, item);
+        SimpleKey<T> newKey = new SimpleKey<T>(this, item, bounds);
         newKey.index = elements.size();
-        newKey.bounds = bounds;
         
         elements.add(newKey);
         return newKey;
     }
     
     @Override
-    @SuppressWarnings({ "unchecked", "rawtypes" })
-    public boolean update(T item, ReadOnlyAxisAlignedBox bounds, Object key) {
+    @SuppressWarnings({ "rawtypes" })
+    public boolean update(T item, @Const AxisAlignedBox bounds, Object key) {
         if (item == null)
             throw new NullPointerException("Item cannot be null");
         if (key == null)
             SimpleKey sk = (SimpleKey) key;
             if (sk.owner == this && sk.data == item) {
                 // key is valid, update bounds and return
-                sk.bounds = bounds;
+                sk.bounds.set(bounds);
                 return true;
             }
         }
     }
 
     @Override
-    public void query(ReadOnlyAxisAlignedBox volume, QueryCallback<T> callback) {
+    public void query(@Const AxisAlignedBox volume, QueryCallback<T> callback) {
         if (volume == null)
             throw new NullPointerException("Query bound volume cannot be null");
         if (callback == null)
         for (int i = 0; i < sz; i++) {
             key = elements.get(i);
             if (key.bounds == null || key.bounds.intersects(volume))
-                callback.process(key.data);
+                callback.process(key.data, key.bounds);
         }
     }
 
         int sz = elements.size();
         for (int i = 0; i < sz; i++) {
             key = elements.get(i);
-            // we can't use a PlaneState because each item has no spatial locality
+            // we can't use a PlaneState because each item has no spatial relationship
             // with the items around it in elements
-            if (key.bounds == null || key.bounds.intersects(frustum, null) != FrustumIntersection.OUTSIDE)
-                callback.process(key.data);
-        }
-    }
-    
-    @Override
-    public void query(IntersectionCallback<T> callback) {
-        if (callback == null)
-            throw new NullPointerException("Callback cannot be null");
-        
-        int ct = elements.size();
-        SimpleKey<T> e1, e2;
-        for (int i = 0; i < ct; i++) {
-            e1 = elements.get(i);
-            for (int j = i + 1; j < ct; j++) {
-                e2 = elements.get(j);
-                if (e1.bounds == null || e2.bounds == null || e1.bounds.intersects(e2.bounds))
-                    callback.process(e1.data, e2.data);
-            }
+            if (key.bounds.intersects(frustum, null) != FrustumIntersection.OUTSIDE)
+                callback.process(key.data, key.bounds);
         }
     }
 
     private static class SimpleKey<T> {
         private final T data;
-        private ReadOnlyAxisAlignedBox bounds;
+        private final AxisAlignedBox bounds;
         
         private int index;
         private final SimpleSpatialIndex<T> owner;
         
-        public SimpleKey(SimpleSpatialIndex<T> owner, T data) {
+        public SimpleKey(SimpleSpatialIndex<T> owner, T data, @Const AxisAlignedBox bounds) {
             this.owner = owner;
             this.data = data;
+            this.bounds = new AxisAlignedBox(bounds);
         }
     }
 }

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

 package com.ferox.math.bounds;
 
+import com.ferox.math.Const;
 import com.ferox.math.bounds.Frustum.FrustumIntersection;
 
 /**
      *         hierarchy, or null on a failure
      * @throws NullPointerException if item or bounds is null
      */
-    public Object add(T item, ReadOnlyAxisAlignedBox bounds);
+    public Object add(T item, @Const AxisAlignedBox bounds);
 
     /**
      * <p>
      * @throws IllegalArgumentException if the given key is invalid, or if item
      *             isn't in the hierarchy
      */
-    public boolean update(T item, ReadOnlyAxisAlignedBox bounds, Object key);
+    public boolean update(T item, @Const AxisAlignedBox bounds, Object key);
 
     /**
      * Remove <tt>item</tt> from this hierarchy so that the given item can no
      * @param callback A QueryCallback to run on each item within the query
      * @throws NullPointerException if volume or callback is null
      */
-    public void query(ReadOnlyAxisAlignedBox volume, QueryCallback<T> callback);
+    public void query(@Const AxisAlignedBox volume, QueryCallback<T> callback);
 
     /**
      * <p>
      * @throws NullPointerException if frustum or callback is null
      */
     public void query(Frustum f, QueryCallback<T> callback);
-
-    /**
-     * <p>
-     * Query this SpatialIndex for all pairs of intersecting items that have
-     * been added to this hierarchy. Intersections are determined by
-     * {@link ReadOnlyAxisAlignedBox#intersects(ReadOnlyAxisAlignedBox)}, between the bounds
-     * provided with the items when they were added or updated.
-     * </p>
-     * <p>
-     * A pair of items is considered unique, and any combination of two items
-     * that intersect will not be passed to the callback more than once.
-     * </p>
-     * 
-     * @param callback The IntersectionCallback to run on each pair that is
-     *            intersecting
-     * @throws NullPointerException if callback is null
-     */
-    public void query(IntersectionCallback<T> callback);
 }

ferox-math/src/main/java/com/ferox/math/bounds/SpatialIndex2.java

-package com.ferox.math.bounds;
-
-import java.util.Iterator;
-
-import com.ferox.math.ReadOnlyRay3f;
-
-// FIXME: it makes more sense to have specialized index's for triangles
-// while this is a general index for other objects. Triangle structures
-// will want to pack the triangles in an array, and have nodes reference them
-// by index.  Most likely they will not need to be live updated as well.
-
-// This means that ray queries are not a valuable part of this interface,
-// So I can remove that query, and get rid of the ugly ray types.
-
-// I've also been thinking more heavily about the problems with entreri's shared
-// properties and caching, as well as the math library. If I move the caching
-// to the component instance level, the setters will be responsible for looking
-// up the canonical instance and clearing its cache.
-
-// The math library might be better to move to read-only annotations or 
-// tuples or something
-public interface SpatialIndex2<T extends Intersectable> extends Iterable<T> {
-
-    public void query(Frustum f, QueryCallback<T> callback);
-    
-    public void query(ReadOnlyAxisAlignedBox aabb, QueryCallback<T> callback);
-    
-    // FIXME: this should have a special callback to provide the intersection 
-    // information
-    public void query(ReadOnlyRay3f ray, QueryCallback<T> callback);
-    
-    // FIXME: is this the right way to do things? what is the best way to
-    // organize objects as well as triangles? Is it even good to use the
-    // same exact implementation for those different use cases?
-    
-    // Should I hold onto the bounds, I will have to think how to do updates
-    // without holding onto the old bounds. That requires the notebook. 
-    public Object add(T obj);
-    
-    public void update(T obj, Object key);
-    
-    public void remove(Object key);
-    
-    public int size();
-    
-    public Iterator<T> iterator();
-}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.