Commits

Karsten Schmidt  committed 763ad7a

adding SpatialBins & CoordinateExtractor, updating VerletPhysics2D & AttractionBehavior2D to support optional spatial indexing using SpatialBins

  • Participants
  • Parent commits 2da65df
  • Branches spatialphysics

Comments (0)

Files changed (7)

File src.core/toxi/geom/CoordinateExtractor.java

+package toxi.geom;
+
+public interface CoordinateExtractor<T> {
+
+    public float coordinate(T obj);
+}

File src.core/toxi/geom/SpatialBins.java

+package toxi.geom;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+
+import toxi.math.MathUtils;
+
+public class SpatialBins<T> {
+
+    private final float invBinWidth;
+    private final float minOffset;
+    private final int numBins;
+    private int numItems;
+
+    private final List<HashSet<T>> bins;
+    private final CoordinateExtractor<T> extractor;
+
+    public SpatialBins(float min, float max, int numBins,
+            CoordinateExtractor<T> extractor) {
+        this.extractor = extractor;
+        this.bins = new ArrayList<HashSet<T>>();
+        for (int i = 0; i < numBins; i++) {
+            bins.add(new HashSet<T>());
+        }
+        this.minOffset = min;
+        this.numBins = numBins;
+        this.invBinWidth = numBins / (max - min);
+    }
+
+    public void clear() {
+        for (HashSet<T> bin : bins) {
+            bin.clear();
+        }
+        numItems = 0;
+    }
+
+    public int index(T p) {
+        int id = (int) MathUtils.clip((extractor.coordinate(p) - minOffset)
+                * invBinWidth, 0, numBins - 1);
+        if (bins.get(id).add(p)) {
+            numItems++;
+        }
+        return id;
+    }
+
+    public boolean isIndexed(T item) {
+        // TODO Auto-generated method stub
+        return false;
+    }
+
+    public List<T> itemsWithin(float pos, float radius) {
+        int id = (int) MathUtils.clip((pos - minOffset) * invBinWidth, 0,
+                numBins);
+        int tol = (int) Math.ceil(radius * invBinWidth);
+        List<T> items = null;
+        for (int i = Math.max(id - tol, 0), n = Math.min(
+                Math.min(id + tol, numBins), numBins - 1); i <= n; i++) {
+            if (items == null) {
+                items = new ArrayList<T>();
+            }
+            items.addAll(bins.get(i));
+        }
+        return items;
+    }
+
+    public int reindex(float oldPos, T p) {
+        int id1 = (int) MathUtils.clip((oldPos - minOffset) * invBinWidth, 0,
+                numBins);
+        int id2 = (int) MathUtils.clip((extractor.coordinate(p) - minOffset)
+                * invBinWidth, 0, numBins);
+        if (id1 != id2) {
+            if (bins.get(id1).remove(p)) {
+                numItems--;
+            }
+            if (bins.get(id2).add(p)) {
+                numItems++;
+            }
+            return id2;
+        }
+        return id1;
+    }
+
+    public int size() {
+        return numItems;
+    }
+
+    public int unindex(T p) {
+        int id = (int) MathUtils.clip((extractor.coordinate(p) - minOffset)
+                * invBinWidth, 0, numBins);
+        bins.get(id).remove(p);
+        return id;
+    }
+}

File src.physics/toxi/physics2d/VerletPhysics2D.java

 import java.util.List;
 
 import toxi.geom.Rect;
+import toxi.geom.SpatialBins;
 import toxi.geom.Vec2D;
 import toxi.physics2d.behaviors.GravityBehavior2D;
 import toxi.physics2d.behaviors.ParticleBehavior2D;
 
     protected float drag;
 
+    protected SpatialBins<VerletParticle2D> index;
+
     /**
      * Initializes a Verlet engine instance using the default values.
      */
     }
 
     /**
+     * @return the index
+     */
+    public SpatialBins<VerletParticle2D> getIndex() {
+        return index;
+    }
+
+    /**
      * Attempts to find the spring element between the 2 particles supplied
      * 
      * @param a
     }
 
     /**
+     * @param index
+     *            the index to set
+     */
+    public void setIndex(SpatialBins<VerletParticle2D> index) {
+        this.index = index;
+    }
+
+    /**
      * @param timeStep
      *            the timeStep to set
      */
         updateParticles();
         updateSprings();
         applyConstaints();
+        updateIndex();
         return this;
     }
 
      */
     protected void updateParticles() {
         for (ParticleBehavior2D b : behaviors) {
-            for (VerletParticle2D p : particles) {
-                b.apply(p);
+            if (index != null && b.supportsSpatialIndex()) {
+                b.applyWithSpaceHash(index);
+            } else {
+                for (VerletParticle2D p : particles) {
+                    b.apply(p);
+                }
             }
         }
         for (VerletParticle2D p : particles) {
         }
     }
 
+    private void updateIndex() {
+        if (index != null) {
+            index.clear();
+            for (VerletParticle2D p : particles) {
+                index.index(p);
+            }
+        }
+    }
+
     /**
      * Updates all spring connections based on new particle positions
      */

File src.physics/toxi/physics2d/behaviors/AttractionBehavior2D.java

 
 package toxi.physics2d.behaviors;
 
+import java.util.List;
+
+import toxi.geom.SpatialBins;
 import toxi.geom.Vec2D;
 import toxi.physics2d.VerletParticle2D;
 
         }
     }
 
+    public void applyWithSpaceHash(SpatialBins<VerletParticle2D> spaceHash) {
+        List<VerletParticle2D> selection = spaceHash.itemsWithin(attractor.x,
+                radius);
+        if (selection != null) {
+            for (VerletParticle2D p : selection) {
+                final float prev = p.x;
+                apply(p);
+                spaceHash.reindex(prev, p);
+            }
+        }
+    }
+
     public void configure(float timeStep) {
         this.timeStep = timeStep;
         setStrength(strength);
         this.attrStrength = strength * timeStep;
     }
 
+    public boolean supportsSpatialIndex() {
+        return true;
+    }
+
 }

File src.physics/toxi/physics2d/behaviors/ConstantForceBehavior2D.java

 
 package toxi.physics2d.behaviors;
 
+import toxi.geom.SpatialBins;
 import toxi.geom.Vec2D;
 import toxi.physics2d.VerletParticle2D;
 
         p.addForce(scaledForce);
     }
 
+    public void applyWithSpaceHash(SpatialBins<VerletParticle2D> spaceHash) {
+        throw new UnsupportedOperationException("not implemented");
+    }
+
     public void configure(float timeStep) {
         this.timeStep = timeStep;
         setForce(force);
         this.scaledForce = force.scale(timeStep);
     }
 
+    public boolean supportsSpatialIndex() {
+        return false;
+    }
+
 }

File src.physics/toxi/physics2d/behaviors/ParticleBehavior2D.java

 
 package toxi.physics2d.behaviors;
 
+import toxi.geom.SpatialBins;
 import toxi.physics2d.VerletParticle2D;
 
 public interface ParticleBehavior2D {
      */
     public void apply(VerletParticle2D p);
 
+    public void applyWithSpaceHash(SpatialBins<VerletParticle2D> spaceHash);
+
     public void configure(float timeStep);
+
+    public boolean supportsSpatialIndex();
 }

File src.test/toxi/test/AttractTest2D.java

 import java.util.Iterator;
 
 import processing.core.PApplet;
+import toxi.geom.CoordinateExtractor;
 import toxi.geom.Rect;
+import toxi.geom.SpatialBins;
 import toxi.geom.Vec2D;
 import toxi.physics2d.VerletParticle2D;
 import toxi.physics2d.VerletPhysics2D;
 public class AttractTest2D extends PApplet {
 
     public static void main(String[] args) {
-        PApplet.main(new String[] { "toxi.test.AttractTest2D" });
+        PApplet.main(new String[] {
+            "toxi.test.AttractTest2D"
+        });
     }
 
     ToxiclibsSupport gfx;
 
     private void addParticle() {
         VerletParticle2D p = new VerletParticle2D(Vec2D.randomVector().scale(5)
-                .addSelf(width / 2, 0));
+                .addSelf(width * 0.5f, 0));
         physics.addParticle(p);
-        for (int j = 0; j < physics.particles.size(); j++) {
-            physics.particles.get(j).addBehavior(
-                    new AttractionBehavior2D(p, 10, -2f, 0.01f),
-                    physics.getTimeStep());
-        }
+        // add a negative attraction force field around the new particle
+        physics.addBehavior(new AttractionBehavior2D(p, 20, -1.2f, 0.01f));
     }
 
     public void draw() {
             VerletParticle2D p = i.next();
             ellipse(p.x, p.y, 5, 5);
         }
+        text("fps: " + frameRate, 20, 20);
     }
 
     public void mouseDragged() {
 
     public void mousePressed() {
         mousePos = new Vec2D(mouseX, mouseY);
-        mouseAttractor = new AttractionBehavior2D(mousePos, 500, 0.9f);
+        mouseAttractor = new AttractionBehavior2D(mousePos, 400, 1.2f);
         physics.addBehavior(mouseAttractor);
     }
 
         physics.setDrag(0.1f);
         physics.setWorldBounds(new Rect(0, 0, width, height));
         physics.addBehavior(new GravityBehavior2D(new Vec2D(0, 0.15f)));
+        physics.setIndex(new SpatialBins<VerletParticle2D>(0, width, 80,
+                new CoordinateExtractor<VerletParticle2D>() {
+
+                    public final float coordinate(VerletParticle2D p) {
+                        return p.x;
+                    }
+                }));
+        textFont(createFont("SansSerif", 10));
     }
 }