diff options
author | Scott Barta <sbarta@google.com> | 2012-03-01 12:35:35 -0800 |
---|---|---|
committer | Scott Barta <sbarta@google.com> | 2012-03-01 12:40:08 -0800 |
commit | 59b2e6871c65f58fdad78cd7229c292f6a177578 (patch) | |
tree | 2d4e7bfc05b93f40b34675d77e403dd1c25efafd /engine/src/core/com/jme3/collision | |
parent | f9b30489e75ac1eabc365064959804e99534f7ab (diff) | |
download | jmonkeyengine-59b2e6871c65f58fdad78cd7229c292f6a177578.tar.gz |
Adds the jMonkeyEngine library to the build.
Adds the jMonkeyEngine open source 3D game engine to the build. This
is built as a static library and is only used by the Finsky client.
Change-Id: I06a3f054df7b8a67757267d884854f70c5a16ca0
Diffstat (limited to 'engine/src/core/com/jme3/collision')
10 files changed, 1961 insertions, 0 deletions
diff --git a/engine/src/core/com/jme3/collision/Collidable.java b/engine/src/core/com/jme3/collision/Collidable.java new file mode 100644 index 0000000..65c0631 --- /dev/null +++ b/engine/src/core/com/jme3/collision/Collidable.java @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision; + +/** + * Interface for Collidable objects. + * Classes that implement this interface are marked as collidable, meaning + * they support collision detection between other objects that are also + * collidable. + * + * @author Kirill Vainer + */ +public interface Collidable { + + /** + * Check collision with another Collidable. + * + * @param other The object to check collision against + * @param results Will contain the list of {@link CollisionResult}s. + * @return how many collisions were found between this and other + */ + public int collideWith(Collidable other, CollisionResults results) throws UnsupportedCollisionException; +} diff --git a/engine/src/core/com/jme3/collision/CollisionResult.java b/engine/src/core/com/jme3/collision/CollisionResult.java new file mode 100644 index 0000000..aef3936 --- /dev/null +++ b/engine/src/core/com/jme3/collision/CollisionResult.java @@ -0,0 +1,138 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision; + +import com.jme3.math.Triangle; +import com.jme3.math.Vector3f; +import com.jme3.scene.Geometry; +import com.jme3.scene.Mesh; + +/** + * A <code>CollisionResult</code> represents a single collision instance + * between two {@link Collidable}. A collision check can result in many + * collision instances (places where collision has occured). + * + * @author Kirill Vainer + */ +public class CollisionResult implements Comparable<CollisionResult> { + + private Geometry geometry; + private Vector3f contactPoint; + private Vector3f contactNormal; + private float distance; + private int triangleIndex; + + public CollisionResult(Geometry geometry, Vector3f contactPoint, float distance, int triangleIndex) { + this.geometry = geometry; + this.contactPoint = contactPoint; + this.distance = distance; + this.triangleIndex = triangleIndex; + } + + public CollisionResult(Vector3f contactPoint, float distance) { + this.contactPoint = contactPoint; + this.distance = distance; + } + + public CollisionResult(){ + } + + public void setGeometry(Geometry geom){ + this.geometry = geom; + } + + public void setContactNormal(Vector3f norm){ + this.contactNormal = norm; + } + + public void setContactPoint(Vector3f point){ + this.contactPoint = point; + } + + public void setDistance(float dist){ + this.distance = dist; + } + + public void setTriangleIndex(int index){ + this.triangleIndex = index; + } + + public Triangle getTriangle(Triangle store){ + if (store == null) + store = new Triangle(); + + Mesh m = geometry.getMesh(); + m.getTriangle(triangleIndex, store); + store.calculateCenter(); + store.calculateNormal(); + return store; + } + + public int compareTo(CollisionResult other) { + if (distance < other.distance) + return -1; + else if (distance > other.distance) + return 1; + else + return 0; + } + + @Override + public boolean equals(Object obj) { + if(obj instanceof CollisionResult){ + return ((CollisionResult)obj).compareTo(this) == 0; + } + return super.equals(obj); + } + + public Vector3f getContactPoint() { + return contactPoint; + } + + public Vector3f getContactNormal() { + return contactNormal; + } + + public float getDistance() { + return distance; + } + + public Geometry getGeometry() { + return geometry; + } + + public int getTriangleIndex() { + return triangleIndex; + } + +} diff --git a/engine/src/core/com/jme3/collision/CollisionResults.java b/engine/src/core/com/jme3/collision/CollisionResults.java new file mode 100644 index 0000000..ec691c1 --- /dev/null +++ b/engine/src/core/com/jme3/collision/CollisionResults.java @@ -0,0 +1,136 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Iterator; + +/** + * <code>CollisionResults</code> is a collection returned as a result of a + * collision detection operation done by {@link Collidable}. + * + * @author Kirill Vainer + */ +public class CollisionResults implements Iterable<CollisionResult> { + + private final ArrayList<CollisionResult> results = new ArrayList<CollisionResult>(); + private boolean sorted = true; + + /** + * Clears all collision results added to this list + */ + public void clear(){ + results.clear(); + } + + /** + * Iterator for iterating over the collision results. + * + * @return the iterator + */ + public Iterator<CollisionResult> iterator() { + if (!sorted){ + Collections.sort(results); + sorted = true; + } + + return results.iterator(); + } + + public void addCollision(CollisionResult result){ + results.add(result); + sorted = false; + } + + public int size(){ + return results.size(); + } + + public CollisionResult getClosestCollision(){ + if (size() == 0) + return null; + + if (!sorted){ + Collections.sort(results); + sorted = true; + } + + return results.get(0); + } + + public CollisionResult getFarthestCollision(){ + if (size() == 0) + return null; + + if (!sorted){ + Collections.sort(results); + sorted = true; + } + + return results.get(size()-1); + } + + public CollisionResult getCollision(int index){ + if (!sorted){ + Collections.sort(results); + sorted = true; + } + + return results.get(index); + } + + /** + * Internal use only. + * @param index + * @return + */ + public CollisionResult getCollisionDirect(int index){ + return results.get(index); + } + + @Override + public String toString(){ + StringBuilder sb = new StringBuilder(); + sb.append("CollisionResults["); + for (CollisionResult result : results){ + sb.append(result).append(", "); + } + if (results.size() > 0) + sb.setLength(sb.length()-2); + + sb.append("]"); + return sb.toString(); + } + +} diff --git a/engine/src/core/com/jme3/collision/MotionAllowedListener.java b/engine/src/core/com/jme3/collision/MotionAllowedListener.java new file mode 100644 index 0000000..7703e5a --- /dev/null +++ b/engine/src/core/com/jme3/collision/MotionAllowedListener.java @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision; + +import com.jme3.math.Vector3f; + +public interface MotionAllowedListener { + + /** + * Check if motion allowed. Modify position and velocity vectors + * appropriately if not allowed.. + * + * @param position + * @param velocity + */ + public void checkMotionAllowed(Vector3f position, Vector3f velocity); + +} diff --git a/engine/src/core/com/jme3/collision/SweepSphere.java b/engine/src/core/com/jme3/collision/SweepSphere.java new file mode 100644 index 0000000..9d43f89 --- /dev/null +++ b/engine/src/core/com/jme3/collision/SweepSphere.java @@ -0,0 +1,440 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision; + +import com.jme3.math.*; + +/** + * No longer public .. + * + * @author Kirill Vainer + */ +@Deprecated +class SweepSphere implements Collidable { + + private Vector3f velocity = new Vector3f(); + private Vector3f center = new Vector3f(); + private Vector3f dimension = new Vector3f(); + private Vector3f invDim = new Vector3f(); + + private final Triangle scaledTri = new Triangle(); + private final Plane triPlane = new Plane(); + private final Vector3f temp1 = new Vector3f(), + temp2 = new Vector3f(), + temp3 = new Vector3f(); + private final Vector3f sVelocity = new Vector3f(), + sCenter = new Vector3f(); + + public Vector3f getCenter() { + return center; + } + + public void setCenter(Vector3f center) { + this.center.set(center); + } + + public Vector3f getDimension() { + return dimension; + } + + public void setDimension(Vector3f dimension) { + this.dimension.set(dimension); + this.invDim.set(1,1,1).divideLocal(dimension); + } + + public void setDimension(float x, float y, float z){ + this.dimension.set(x,y,z); + this.invDim.set(1,1,1).divideLocal(dimension); + } + + public void setDimension(float dim){ + this.dimension.set(dim, dim, dim); + this.invDim.set(1,1,1).divideLocal(dimension); + } + + public Vector3f getVelocity() { + return velocity; + } + + public void setVelocity(Vector3f velocity) { + this.velocity.set(velocity); + } + + private boolean pointsOnSameSide(Vector3f p1, Vector3f p2, Vector3f line1, Vector3f line2) { + // V1 = (line2 - line1) x (p1 - line1) + // V2 = (p2 - line1) x (line2 - line1) + + temp1.set(line2).subtractLocal(line1); + temp3.set(temp1); + temp2.set(p1).subtractLocal(line1); + temp1.crossLocal(temp2); + + temp2.set(p2).subtractLocal(line1); + temp3.crossLocal(temp2); + + // V1 . V2 >= 0 + return temp1.dot(temp3) >= 0; + } + + private boolean isPointInTriangle(Vector3f point, AbstractTriangle tri) { + if (pointsOnSameSide(point, tri.get1(), tri.get2(), tri.get3()) + && pointsOnSameSide(point, tri.get2(), tri.get1(), tri.get3()) + && pointsOnSameSide(point, tri.get3(), tri.get1(), tri.get2())) + return true; + return false; + } + + private static float getLowestRoot(float a, float b, float c, float maxR) { + float determinant = b * b - 4f * a * c; + if (determinant < 0){ + return Float.NaN; + } + + float sqrtd = FastMath.sqrt(determinant); + float r1 = (-b - sqrtd) / (2f * a); + float r2 = (-b + sqrtd) / (2f * a); + + if (r1 > r2){ + float temp = r2; + r2 = r1; + r1 = temp; + } + + if (r1 > 0 && r1 < maxR){ + return r1; + } + + if (r2 > 0 && r2 < maxR){ + return r2; + } + + return Float.NaN; + } + + private float collideWithVertex(Vector3f sCenter, Vector3f sVelocity, + float velocitySquared, Vector3f vertex, float t) { + // A = velocity * velocity + // B = 2 * (velocity . (center - vertex)); + // C = ||vertex - center||^2 - 1f; + + temp1.set(sCenter).subtractLocal(vertex); + float a = velocitySquared; + float b = 2f * sVelocity.dot(temp1); + float c = temp1.negateLocal().lengthSquared() - 1f; + float newT = getLowestRoot(a, b, c, t); + +// float A = velocitySquared; +// float B = sCenter.subtract(vertex).dot(sVelocity) * 2f; +// float C = vertex.subtract(sCenter).lengthSquared() - 1f; +// +// float newT = getLowestRoot(A, B, C, Float.MAX_VALUE); +// if (newT > 1.0f) +// newT = Float.NaN; + + return newT; + } + + private float collideWithSegment(Vector3f sCenter, + Vector3f sVelocity, + float velocitySquared, + Vector3f l1, + Vector3f l2, + float t, + Vector3f store) { + Vector3f edge = temp1.set(l2).subtractLocal(l1); + Vector3f base = temp2.set(l1).subtractLocal(sCenter); + + float edgeSquared = edge.lengthSquared(); + float baseSquared = base.lengthSquared(); + + float EdotV = edge.dot(sVelocity); + float EdotB = edge.dot(base); + + float a = (edgeSquared * -velocitySquared) + EdotV * EdotV; + float b = (edgeSquared * 2f * sVelocity.dot(base)) + - (2f * EdotV * EdotB); + float c = (edgeSquared * (1f - baseSquared)) + EdotB * EdotB; + float newT = getLowestRoot(a, b, c, t); + if (!Float.isNaN(newT)){ + float f = (EdotV * newT - EdotB) / edgeSquared; + if (f >= 0f && f < 1f){ + store.scaleAdd(f, edge, l1); + return newT; + } + } + return Float.NaN; + } + + private CollisionResult collideWithTriangle(AbstractTriangle tri){ + // scale scaledTriangle based on dimension + scaledTri.get1().set(tri.get1()).multLocal(invDim); + scaledTri.get2().set(tri.get2()).multLocal(invDim); + scaledTri.get3().set(tri.get3()).multLocal(invDim); +// Vector3f sVelocity = velocity.mult(invDim); +// Vector3f sCenter = center.mult(invDim); + velocity.mult(invDim, sVelocity); + center.mult(invDim, sCenter); + + triPlane.setPlanePoints(scaledTri); + + float normalDotVelocity = triPlane.getNormal().dot(sVelocity); + // XXX: sVelocity.normalize() needed? + // back facing scaledTriangles not considered + if (normalDotVelocity > 0f) + return null; + + float t0, t1; + boolean embedded = false; + + float signedDistanceToPlane = triPlane.pseudoDistance(sCenter); + if (normalDotVelocity == 0.0f){ + // we are travelling exactly parrallel to the plane + if (FastMath.abs(signedDistanceToPlane) >= 1.0f){ + // no collision possible + return null; + }else{ + // we are embedded + t0 = 0; + t1 = 1; + embedded = true; + System.out.println("EMBEDDED"); + return null; + } + }else{ + t0 = (-1f - signedDistanceToPlane) / normalDotVelocity; + t1 = ( 1f - signedDistanceToPlane) / normalDotVelocity; + + if (t0 > t1){ + float tf = t1; + t1 = t0; + t0 = tf; + } + + if (t0 > 1.0f || t1 < 0.0f){ + // collision is out of this sVelocity range + return null; + } + + // clamp the interval to [0, 1] + t0 = Math.max(t0, 0.0f); + t1 = Math.min(t1, 1.0f); + } + + boolean foundCollision = false; + float minT = 1f; + + Vector3f contactPoint = new Vector3f(); + Vector3f contactNormal = new Vector3f(); + +// if (!embedded){ + // check against the inside of the scaledTriangle + // contactPoint = sCenter - p.normal + t0 * sVelocity + contactPoint.set(sVelocity); + contactPoint.multLocal(t0); + contactPoint.addLocal(sCenter); + contactPoint.subtractLocal(triPlane.getNormal()); + + // test to see if the collision is on a scaledTriangle interior + if (isPointInTriangle(contactPoint, scaledTri) && !embedded){ + foundCollision = true; + + minT = t0; + + // scale collision point back into R3 + contactPoint.multLocal(dimension); + contactNormal.set(velocity).multLocal(t0); + contactNormal.addLocal(center); + contactNormal.subtractLocal(contactPoint).normalizeLocal(); + +// contactNormal.set(triPlane.getNormal()); + + CollisionResult result = new CollisionResult(); + result.setContactPoint(contactPoint); + result.setContactNormal(contactNormal); + result.setDistance(minT * velocity.length()); + return result; + } +// } + + float velocitySquared = sVelocity.lengthSquared(); + + Vector3f v1 = scaledTri.get1(); + Vector3f v2 = scaledTri.get2(); + Vector3f v3 = scaledTri.get3(); + + // vertex 1 + float newT; + newT = collideWithVertex(sCenter, sVelocity, velocitySquared, v1, minT); + if (!Float.isNaN(newT)){ + minT = newT; + contactPoint.set(v1); + foundCollision = true; + } + + // vertex 2 + newT = collideWithVertex(sCenter, sVelocity, velocitySquared, v2, minT); + if (!Float.isNaN(newT)){ + minT = newT; + contactPoint.set(v2); + foundCollision = true; + } + + // vertex 3 + newT = collideWithVertex(sCenter, sVelocity, velocitySquared, v3, minT); + if (!Float.isNaN(newT)){ + minT = newT; + contactPoint.set(v3); + foundCollision = true; + } + + // edge 1-2 + newT = collideWithSegment(sCenter, sVelocity, velocitySquared, v1, v2, minT, contactPoint); + if (!Float.isNaN(newT)){ + minT = newT; + foundCollision = true; + } + + // edge 2-3 + newT = collideWithSegment(sCenter, sVelocity, velocitySquared, v2, v3, minT, contactPoint); + if (!Float.isNaN(newT)){ + minT = newT; + foundCollision = true; + } + + // edge 3-1 + newT = collideWithSegment(sCenter, sVelocity, velocitySquared, v3, v1, minT, contactPoint); + if (!Float.isNaN(newT)){ + minT = newT; + foundCollision = true; + } + + if (foundCollision){ + // compute contact normal based on minimum t + contactPoint.multLocal(dimension); + contactNormal.set(velocity).multLocal(t0); + contactNormal.addLocal(center); + contactNormal.subtractLocal(contactPoint).normalizeLocal(); + + CollisionResult result = new CollisionResult(); + result.setContactPoint(contactPoint); + result.setContactNormal(contactNormal); + result.setDistance(minT * velocity.length()); + + return result; + }else{ + return null; + } + } + + public CollisionResult collideWithSweepSphere(SweepSphere other){ + temp1.set(velocity).subtractLocal(other.velocity); + temp2.set(center).subtractLocal(other.center); + temp3.set(dimension).addLocal(other.dimension); + // delta V + // delta C + // Rsum + + float a = temp1.lengthSquared(); + float b = 2f * temp1.dot(temp2); + float c = temp2.lengthSquared() - temp3.getX() * temp3.getX(); + float t = getLowestRoot(a, b, c, 1); + + // no collision + if (Float.isNaN(t)) + return null; + + CollisionResult result = new CollisionResult(); + result.setDistance(velocity.length() * t); + + temp1.set(velocity).multLocal(t).addLocal(center); + temp2.set(other.velocity).multLocal(t).addLocal(other.center); + temp3.set(temp2).subtractLocal(temp1); + // temp3 contains center to other.center vector + + // normalize it to get normal + temp2.set(temp3).normalizeLocal(); + result.setContactNormal(new Vector3f(temp2)); + + // temp3 is contact point + temp3.set(temp2).multLocal(dimension).addLocal(temp1); + result.setContactPoint(new Vector3f(temp3)); + + return result; + } + + public static void main(String[] args){ + SweepSphere ss = new SweepSphere(); + ss.setCenter(Vector3f.ZERO); + ss.setDimension(1); + ss.setVelocity(new Vector3f(10, 10, 10)); + + SweepSphere ss2 = new SweepSphere(); + ss2.setCenter(new Vector3f(5, 5, 5)); + ss2.setDimension(1); + ss2.setVelocity(new Vector3f(-10, -10, -10)); + + CollisionResults cr = new CollisionResults(); + ss.collideWith(ss2, cr); + if (cr.size() > 0){ + CollisionResult c = cr.getClosestCollision(); + System.out.println("D = "+c.getDistance()); + System.out.println("P = "+c.getContactPoint()); + System.out.println("N = "+c.getContactNormal()); + } + } + + public int collideWith(Collidable other, CollisionResults results) + throws UnsupportedCollisionException { + if (other instanceof AbstractTriangle){ + AbstractTriangle tri = (AbstractTriangle) other; + CollisionResult result = collideWithTriangle(tri); + if (result != null){ + results.addCollision(result); + return 1; + } + return 0; + }else if (other instanceof SweepSphere){ + SweepSphere sph = (SweepSphere) other; + + CollisionResult result = collideWithSweepSphere(sph); + if (result != null){ + results.addCollision(result); + return 1; + } + return 0; + }else{ + throw new UnsupportedCollisionException(); + } + } + +} diff --git a/engine/src/core/com/jme3/collision/UnsupportedCollisionException.java b/engine/src/core/com/jme3/collision/UnsupportedCollisionException.java new file mode 100644 index 0000000..ddd6779 --- /dev/null +++ b/engine/src/core/com/jme3/collision/UnsupportedCollisionException.java @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision; + +/** + * Thrown by {@link Collidable} when the requested collision query could not + * be completed because one of the collidables does not support colliding with + * the other. + * + * @author Kirill Vainer + */ +public class UnsupportedCollisionException extends UnsupportedOperationException { + + public UnsupportedCollisionException(Throwable arg0) { + super(arg0); + } + + public UnsupportedCollisionException(String arg0, Throwable arg1) { + super(arg0, arg1); + } + + public UnsupportedCollisionException(String arg0) { + super(arg0); + } + + public UnsupportedCollisionException() { + super(); + } + +} diff --git a/engine/src/core/com/jme3/collision/bih/BIHNode.java b/engine/src/core/com/jme3/collision/bih/BIHNode.java new file mode 100644 index 0000000..0f5c1c8 --- /dev/null +++ b/engine/src/core/com/jme3/collision/bih/BIHNode.java @@ -0,0 +1,430 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package com.jme3.collision.bih; + +import com.jme3.bounding.BoundingBox; +import com.jme3.collision.Collidable; +import com.jme3.collision.CollisionResult; +import com.jme3.collision.CollisionResults; +import com.jme3.export.*; +import com.jme3.math.Matrix4f; +import com.jme3.math.Ray; +import com.jme3.math.Triangle; +import com.jme3.math.Vector3f; +import com.jme3.util.TempVars; +import java.io.IOException; +import static java.lang.Math.max; +import static java.lang.Math.min; +import java.util.ArrayList; + +/** + * Bounding Interval Hierarchy. + * Based on: + * + * Instant Ray Tracing: The Bounding Interval Hierarchy + * By Carsten Wächter and Alexander Keller + */ +public final class BIHNode implements Savable { + + private int leftIndex, rightIndex; + private BIHNode left; + private BIHNode right; + private float leftPlane; + private float rightPlane; + private int axis; + + //Do not do this: It increases memory usage of each BIHNode by at least 56 bytes! + // + //private Triangle tmpTriangle = new Triangle(); + + public BIHNode(int l, int r) { + leftIndex = l; + rightIndex = r; + axis = 3; // indicates leaf + } + + public BIHNode(int axis) { + this.axis = axis; + } + + public BIHNode() { + } + + public BIHNode getLeftChild() { + return left; + } + + public void setLeftChild(BIHNode left) { + this.left = left; + } + + public float getLeftPlane() { + return leftPlane; + } + + public void setLeftPlane(float leftPlane) { + this.leftPlane = leftPlane; + } + + public BIHNode getRightChild() { + return right; + } + + public void setRightChild(BIHNode right) { + this.right = right; + } + + public float getRightPlane() { + return rightPlane; + } + + public void setRightPlane(float rightPlane) { + this.rightPlane = rightPlane; + } + + public void write(JmeExporter ex) throws IOException { + OutputCapsule oc = ex.getCapsule(this); + oc.write(leftIndex, "left_index", 0); + oc.write(rightIndex, "right_index", 0); + oc.write(leftPlane, "left_plane", 0); + oc.write(rightPlane, "right_plane", 0); + oc.write(axis, "axis", 0); + oc.write(left, "left_node", null); + oc.write(right, "right_node", null); + } + + public void read(JmeImporter im) throws IOException { + InputCapsule ic = im.getCapsule(this); + leftIndex = ic.readInt("left_index", 0); + rightIndex = ic.readInt("right_index", 0); + leftPlane = ic.readFloat("left_plane", 0); + rightPlane = ic.readFloat("right_plane", 0); + axis = ic.readInt("axis", 0); + left = (BIHNode) ic.readSavable("left_node", null); + right = (BIHNode) ic.readSavable("right_node", null); + } + + public static final class BIHStackData { + + private final BIHNode node; + private final float min, max; + + BIHStackData(BIHNode node, float min, float max) { + this.node = node; + this.min = min; + this.max = max; + } + } + + public final int intersectWhere(Collidable col, + BoundingBox box, + Matrix4f worldMatrix, + BIHTree tree, + CollisionResults results) { + + TempVars vars = TempVars.get(); + ArrayList<BIHStackData> stack = vars.bihStack; + stack.clear(); + + float[] minExts = {box.getCenter().x - box.getXExtent(), + box.getCenter().y - box.getYExtent(), + box.getCenter().z - box.getZExtent()}; + + float[] maxExts = {box.getCenter().x + box.getXExtent(), + box.getCenter().y + box.getYExtent(), + box.getCenter().z + box.getZExtent()}; + + stack.add(new BIHStackData(this, 0, 0)); + + Triangle t = new Triangle(); + int cols = 0; + + stackloop: + while (stack.size() > 0) { + BIHNode node = stack.remove(stack.size() - 1).node; + + while (node.axis != 3) { + int a = node.axis; + + float maxExt = maxExts[a]; + float minExt = minExts[a]; + + if (node.leftPlane < node.rightPlane) { + // means there's a gap in the middle + // if the box is in that gap, we stop there + if (minExt > node.leftPlane + && maxExt < node.rightPlane) { + continue stackloop; + } + } + + if (maxExt < node.rightPlane) { + node = node.left; + } else if (minExt > node.leftPlane) { + node = node.right; + } else { + stack.add(new BIHStackData(node.right, 0, 0)); + node = node.left; + } +// if (maxExt < node.leftPlane +// && maxExt < node.rightPlane){ +// node = node.left; +// }else if (minExt > node.leftPlane +// && minExt > node.rightPlane){ +// node = node.right; +// }else{ + +// } + } + + for (int i = node.leftIndex; i <= node.rightIndex; i++) { + tree.getTriangle(i, t.get1(), t.get2(), t.get3()); + if (worldMatrix != null) { + worldMatrix.mult(t.get1(), t.get1()); + worldMatrix.mult(t.get2(), t.get2()); + worldMatrix.mult(t.get3(), t.get3()); + } + + int added = col.collideWith(t, results); + + if (added > 0) { + int index = tree.getTriangleIndex(i); + int start = results.size() - added; + + for (int j = start; j < results.size(); j++) { + CollisionResult cr = results.getCollisionDirect(j); + cr.setTriangleIndex(index); + } + + cols += added; + } + } + } + vars.release(); + return cols; + } + + public final int intersectBrute(Ray r, + Matrix4f worldMatrix, + BIHTree tree, + float sceneMin, + float sceneMax, + CollisionResults results) { + float tHit = Float.POSITIVE_INFINITY; + + TempVars vars = TempVars.get(); + + Vector3f v1 = vars.vect1, + v2 = vars.vect2, + v3 = vars.vect3; + + int cols = 0; + + ArrayList<BIHStackData> stack = vars.bihStack; + stack.clear(); + stack.add(new BIHStackData(this, 0, 0)); + stackloop: + while (stack.size() > 0) { + + BIHStackData data = stack.remove(stack.size() - 1); + BIHNode node = data.node; + + leafloop: + while (node.axis != 3) { // while node is not a leaf + BIHNode nearNode, farNode; + nearNode = node.left; + farNode = node.right; + + stack.add(new BIHStackData(farNode, 0, 0)); + node = nearNode; + } + + // a leaf + for (int i = node.leftIndex; i <= node.rightIndex; i++) { + tree.getTriangle(i, v1, v2, v3); + + if (worldMatrix != null) { + worldMatrix.mult(v1, v1); + worldMatrix.mult(v2, v2); + worldMatrix.mult(v3, v3); + } + + float t = r.intersects(v1, v2, v3); + if (t < tHit) { + tHit = t; + Vector3f contactPoint = new Vector3f(r.direction).multLocal(tHit).addLocal(r.origin); + CollisionResult cr = new CollisionResult(contactPoint, tHit); + cr.setTriangleIndex(tree.getTriangleIndex(i)); + results.addCollision(cr); + cols++; + } + } + } + vars.release(); + return cols; + } + + public final int intersectWhere(Ray r, + Matrix4f worldMatrix, + BIHTree tree, + float sceneMin, + float sceneMax, + CollisionResults results) { + + TempVars vars = TempVars.get(); + ArrayList<BIHStackData> stack = vars.bihStack; + stack.clear(); + +// float tHit = Float.POSITIVE_INFINITY; + + Vector3f o = vars.vect1.set(r.getOrigin()); + Vector3f d = vars.vect2.set(r.getDirection()); + + Matrix4f inv =vars.tempMat4.set(worldMatrix).invertLocal(); + + inv.mult(r.getOrigin(), r.getOrigin()); + + // Fixes rotation collision bug + inv.multNormal(r.getDirection(), r.getDirection()); +// inv.multNormalAcross(r.getDirection(), r.getDirection()); + + float[] origins = {r.getOrigin().x, + r.getOrigin().y, + r.getOrigin().z}; + + float[] invDirections = {1f / r.getDirection().x, + 1f / r.getDirection().y, + 1f / r.getDirection().z}; + + r.getDirection().normalizeLocal(); + + Vector3f v1 = vars.vect3, + v2 = vars.vect4, + v3 = vars.vect5; + int cols = 0; + + stack.add(new BIHStackData(this, sceneMin, sceneMax)); + stackloop: + while (stack.size() > 0) { + + BIHStackData data = stack.remove(stack.size() - 1); + BIHNode node = data.node; + float tMin = data.min, + tMax = data.max; + + if (tMax < tMin) { + continue; + } + + leafloop: + while (node.axis != 3) { // while node is not a leaf + int a = node.axis; + + // find the origin and direction value for the given axis + float origin = origins[a]; + float invDirection = invDirections[a]; + + float tNearSplit, tFarSplit; + BIHNode nearNode, farNode; + + tNearSplit = (node.leftPlane - origin) * invDirection; + tFarSplit = (node.rightPlane - origin) * invDirection; + nearNode = node.left; + farNode = node.right; + + if (invDirection < 0) { + float tmpSplit = tNearSplit; + tNearSplit = tFarSplit; + tFarSplit = tmpSplit; + + BIHNode tmpNode = nearNode; + nearNode = farNode; + farNode = tmpNode; + } + + if (tMin > tNearSplit && tMax < tFarSplit) { + continue stackloop; + } + + if (tMin > tNearSplit) { + tMin = max(tMin, tFarSplit); + node = farNode; + } else if (tMax < tFarSplit) { + tMax = min(tMax, tNearSplit); + node = nearNode; + } else { + stack.add(new BIHStackData(farNode, max(tMin, tFarSplit), tMax)); + tMax = min(tMax, tNearSplit); + node = nearNode; + } + } + +// if ( (node.rightIndex - node.leftIndex) > minTrisPerNode){ +// // on demand subdivision +// node.subdivide(); +// stack.add(new BIHStackData(node, tMin, tMax)); +// continue stackloop; +// } + + // a leaf + for (int i = node.leftIndex; i <= node.rightIndex; i++) { + tree.getTriangle(i, v1, v2, v3); + + float t = r.intersects(v1, v2, v3); + if (!Float.isInfinite(t)) { + if (worldMatrix != null) { + worldMatrix.mult(v1, v1); + worldMatrix.mult(v2, v2); + worldMatrix.mult(v3, v3); + float t_world = new Ray(o, d).intersects(v1, v2, v3); + t = t_world; + } + + Vector3f contactNormal = Triangle.computeTriangleNormal(v1, v2, v3, null); + Vector3f contactPoint = new Vector3f(d).multLocal(t).addLocal(o); + float worldSpaceDist = o.distance(contactPoint); + + CollisionResult cr = new CollisionResult(contactPoint, worldSpaceDist); + cr.setContactNormal(contactNormal); + cr.setTriangleIndex(tree.getTriangleIndex(i)); + results.addCollision(cr); + cols++; + } + } + } + vars.release(); + r.setOrigin(o); + r.setDirection(d); + + return cols; + } +} diff --git a/engine/src/core/com/jme3/collision/bih/BIHTree.java b/engine/src/core/com/jme3/collision/bih/BIHTree.java new file mode 100644 index 0000000..3660922 --- /dev/null +++ b/engine/src/core/com/jme3/collision/bih/BIHTree.java @@ -0,0 +1,482 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package com.jme3.collision.bih; + +import com.jme3.bounding.BoundingBox; +import com.jme3.bounding.BoundingSphere; +import com.jme3.bounding.BoundingVolume; +import com.jme3.collision.Collidable; +import com.jme3.collision.CollisionResults; +import com.jme3.collision.UnsupportedCollisionException; +import com.jme3.export.InputCapsule; +import com.jme3.export.JmeExporter; +import com.jme3.export.JmeImporter; +import com.jme3.export.OutputCapsule; +import com.jme3.math.FastMath; +import com.jme3.math.Matrix4f; +import com.jme3.math.Ray; +import com.jme3.math.Vector3f; +import com.jme3.scene.CollisionData; +import com.jme3.scene.Mesh; +import com.jme3.scene.Mesh.Mode; +import com.jme3.scene.VertexBuffer.Type; +import com.jme3.scene.mesh.IndexBuffer; +import com.jme3.scene.mesh.VirtualIndexBuffer; +import com.jme3.scene.mesh.WrappedIndexBuffer; +import com.jme3.util.TempVars; +import java.io.IOException; +import static java.lang.Math.max; +import java.nio.FloatBuffer; + +public class BIHTree implements CollisionData { + + public static final int MAX_TREE_DEPTH = 100; + public static final int MAX_TRIS_PER_NODE = 21; + private Mesh mesh; + private BIHNode root; + private int maxTrisPerNode; + private int numTris; + private float[] pointData; + private int[] triIndices; + + private transient CollisionResults boundResults = new CollisionResults(); + private transient float[] bihSwapTmp; + + private static final TriangleAxisComparator[] comparators = new TriangleAxisComparator[] + { + new TriangleAxisComparator(0), + new TriangleAxisComparator(1), + new TriangleAxisComparator(2) + }; + + private void initTriList(FloatBuffer vb, IndexBuffer ib) { + pointData = new float[numTris * 3 * 3]; + int p = 0; + for (int i = 0; i < numTris * 3; i += 3) { + int vert = ib.get(i) * 3; + pointData[p++] = vb.get(vert++); + pointData[p++] = vb.get(vert++); + pointData[p++] = vb.get(vert); + + vert = ib.get(i + 1) * 3; + pointData[p++] = vb.get(vert++); + pointData[p++] = vb.get(vert++); + pointData[p++] = vb.get(vert); + + vert = ib.get(i + 2) * 3; + pointData[p++] = vb.get(vert++); + pointData[p++] = vb.get(vert++); + pointData[p++] = vb.get(vert); + } + + triIndices = new int[numTris]; + for (int i = 0; i < numTris; i++) { + triIndices[i] = i; + } + } + + public BIHTree(Mesh mesh, int maxTrisPerNode) { + this.mesh = mesh; + this.maxTrisPerNode = maxTrisPerNode; + + if (maxTrisPerNode < 1 || mesh == null) { + throw new IllegalArgumentException(); + } + + bihSwapTmp = new float[9]; + + FloatBuffer vb = (FloatBuffer) mesh.getBuffer(Type.Position).getData(); + IndexBuffer ib = mesh.getIndexBuffer(); + if (ib == null) { + ib = new VirtualIndexBuffer(mesh.getVertexCount(), mesh.getMode()); + } else if (mesh.getMode() != Mode.Triangles) { + ib = new WrappedIndexBuffer(mesh); + } + + numTris = ib.size() / 3; + initTriList(vb, ib); + } + + public BIHTree(Mesh mesh) { + this(mesh, MAX_TRIS_PER_NODE); + } + + public BIHTree() { + } + + public void construct() { + BoundingBox sceneBbox = createBox(0, numTris - 1); + root = createNode(0, numTris - 1, sceneBbox, 0); + } + + private BoundingBox createBox(int l, int r) { + TempVars vars = TempVars.get(); + + Vector3f min = vars.vect1.set(new Vector3f(Float.POSITIVE_INFINITY, Float.POSITIVE_INFINITY, Float.POSITIVE_INFINITY)); + Vector3f max = vars.vect2.set(new Vector3f(Float.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY)); + + Vector3f v1 = vars.vect3, + v2 = vars.vect4, + v3 = vars.vect5; + + for (int i = l; i <= r; i++) { + getTriangle(i, v1, v2, v3); + BoundingBox.checkMinMax(min, max, v1); + BoundingBox.checkMinMax(min, max, v2); + BoundingBox.checkMinMax(min, max, v3); + } + + BoundingBox bbox = new BoundingBox(min, max); + vars.release(); + return bbox; + } + + int getTriangleIndex(int triIndex) { + return triIndices[triIndex]; + } + + private int sortTriangles(int l, int r, float split, int axis) { + int pivot = l; + int j = r; + + TempVars vars = TempVars.get(); + + Vector3f v1 = vars.vect1, + v2 = vars.vect2, + v3 = vars.vect3; + + while (pivot <= j) { + getTriangle(pivot, v1, v2, v3); + v1.addLocal(v2).addLocal(v3).multLocal(FastMath.ONE_THIRD); + if (v1.get(axis) > split) { + swapTriangles(pivot, j); + --j; + } else { + ++pivot; + } + } + + vars.release(); + pivot = (pivot == l && j < pivot) ? j : pivot; + return pivot; + } + + private void setMinMax(BoundingBox bbox, boolean doMin, int axis, float value) { + Vector3f min = bbox.getMin(null); + Vector3f max = bbox.getMax(null); + + if (doMin) { + min.set(axis, value); + } else { + max.set(axis, value); + } + + bbox.setMinMax(min, max); + } + + private float getMinMax(BoundingBox bbox, boolean doMin, int axis) { + if (doMin) { + return bbox.getMin(null).get(axis); + } else { + return bbox.getMax(null).get(axis); + } + } + +// private BIHNode createNode2(int l, int r, BoundingBox nodeBbox, int depth){ +// if ((r - l) < maxTrisPerNode || depth > 100) +// return createLeaf(l, r); +// +// BoundingBox currentBox = createBox(l, r); +// int axis = depth % 3; +// float split = currentBox.getCenter().get(axis); +// +// TriangleAxisComparator comparator = comparators[axis]; +// Arrays.sort(tris, l, r, comparator); +// int splitIndex = -1; +// +// float leftPlane, rightPlane = Float.POSITIVE_INFINITY; +// leftPlane = tris[l].getExtreme(axis, false); +// for (int i = l; i <= r; i++){ +// BIHTriangle tri = tris[i]; +// if (splitIndex == -1){ +// float v = tri.getCenter().get(axis); +// if (v > split){ +// if (i == 0){ +// // no left plane +// splitIndex = -2; +// }else{ +// splitIndex = i; +// // first triangle assigned to right +// rightPlane = tri.getExtreme(axis, true); +// } +// }else{ +// // triangle assigned to left +// float ex = tri.getExtreme(axis, false); +// if (ex > leftPlane) +// leftPlane = ex; +// } +// }else{ +// float ex = tri.getExtreme(axis, true); +// if (ex < rightPlane) +// rightPlane = ex; +// } +// } +// +// if (splitIndex < 0){ +// splitIndex = (r - l) / 2; +// +// leftPlane = Float.NEGATIVE_INFINITY; +// rightPlane = Float.POSITIVE_INFINITY; +// +// for (int i = l; i < splitIndex; i++){ +// float ex = tris[i].getExtreme(axis, false); +// if (ex > leftPlane){ +// leftPlane = ex; +// } +// } +// for (int i = splitIndex; i <= r; i++){ +// float ex = tris[i].getExtreme(axis, true); +// if (ex < rightPlane){ +// rightPlane = ex; +// } +// } +// } +// +// BIHNode node = new BIHNode(axis); +// node.leftPlane = leftPlane; +// node.rightPlane = rightPlane; +// +// node.leftIndex = l; +// node.rightIndex = r; +// +// BoundingBox leftBbox = new BoundingBox(currentBox); +// setMinMax(leftBbox, false, axis, split); +// node.left = createNode2(l, splitIndex-1, leftBbox, depth+1); +// +// BoundingBox rightBbox = new BoundingBox(currentBox); +// setMinMax(rightBbox, true, axis, split); +// node.right = createNode2(splitIndex, r, rightBbox, depth+1); +// +// return node; +// } + private BIHNode createNode(int l, int r, BoundingBox nodeBbox, int depth) { + if ((r - l) < maxTrisPerNode || depth > MAX_TREE_DEPTH) { + return new BIHNode(l, r); + } + + BoundingBox currentBox = createBox(l, r); + + Vector3f exteriorExt = nodeBbox.getExtent(null); + Vector3f interiorExt = currentBox.getExtent(null); + exteriorExt.subtractLocal(interiorExt); + + int axis = 0; + if (exteriorExt.x > exteriorExt.y) { + if (exteriorExt.x > exteriorExt.z) { + axis = 0; + } else { + axis = 2; + } + } else { + if (exteriorExt.y > exteriorExt.z) { + axis = 1; + } else { + axis = 2; + } + } + if (exteriorExt.equals(Vector3f.ZERO)) { + axis = 0; + } + +// Arrays.sort(tris, l, r, comparators[axis]); + float split = currentBox.getCenter().get(axis); + int pivot = sortTriangles(l, r, split, axis); + if (pivot == l || pivot == r) { + pivot = (r + l) / 2; + } + + //If one of the partitions is empty, continue with recursion: same level but different bbox + if (pivot < l) { + //Only right + BoundingBox rbbox = new BoundingBox(currentBox); + setMinMax(rbbox, true, axis, split); + return createNode(l, r, rbbox, depth + 1); + } else if (pivot > r) { + //Only left + BoundingBox lbbox = new BoundingBox(currentBox); + setMinMax(lbbox, false, axis, split); + return createNode(l, r, lbbox, depth + 1); + } else { + //Build the node + BIHNode node = new BIHNode(axis); + + //Left child + BoundingBox lbbox = new BoundingBox(currentBox); + setMinMax(lbbox, false, axis, split); + + //The left node right border is the plane most right + node.setLeftPlane(getMinMax(createBox(l, max(l, pivot - 1)), false, axis)); + node.setLeftChild(createNode(l, max(l, pivot - 1), lbbox, depth + 1)); //Recursive call + + //Right Child + BoundingBox rbbox = new BoundingBox(currentBox); + setMinMax(rbbox, true, axis, split); + //The right node left border is the plane most left + node.setRightPlane(getMinMax(createBox(pivot, r), true, axis)); + node.setRightChild(createNode(pivot, r, rbbox, depth + 1)); //Recursive call + + return node; + } + } + + public void getTriangle(int index, Vector3f v1, Vector3f v2, Vector3f v3) { + int pointIndex = index * 9; + + v1.x = pointData[pointIndex++]; + v1.y = pointData[pointIndex++]; + v1.z = pointData[pointIndex++]; + + v2.x = pointData[pointIndex++]; + v2.y = pointData[pointIndex++]; + v2.z = pointData[pointIndex++]; + + v3.x = pointData[pointIndex++]; + v3.y = pointData[pointIndex++]; + v3.z = pointData[pointIndex++]; + } + + public void swapTriangles(int index1, int index2) { + int p1 = index1 * 9; + int p2 = index2 * 9; + + // store p1 in tmp + System.arraycopy(pointData, p1, bihSwapTmp, 0, 9); + + // copy p2 to p1 + System.arraycopy(pointData, p2, pointData, p1, 9); + + // copy tmp to p2 + System.arraycopy(bihSwapTmp, 0, pointData, p2, 9); + + // swap indices + int tmp2 = triIndices[index1]; + triIndices[index1] = triIndices[index2]; + triIndices[index2] = tmp2; + } + + private int collideWithRay(Ray r, + Matrix4f worldMatrix, + BoundingVolume worldBound, + CollisionResults results) { + + boundResults.clear(); + worldBound.collideWith(r, boundResults); + if (boundResults.size() > 0) { + float tMin = boundResults.getClosestCollision().getDistance(); + float tMax = boundResults.getFarthestCollision().getDistance(); + + if (tMax <= 0) { + tMax = Float.POSITIVE_INFINITY; + } else if (tMin == tMax) { + tMin = 0; + } + + if (tMin <= 0) { + tMin = 0; + } + + if (r.getLimit() < Float.POSITIVE_INFINITY) { + tMax = Math.min(tMax, r.getLimit()); + if (tMin > tMax){ + return 0; + } + } + +// return root.intersectBrute(r, worldMatrix, this, tMin, tMax, results); + return root.intersectWhere(r, worldMatrix, this, tMin, tMax, results); + } + return 0; + } + + private int collideWithBoundingVolume(BoundingVolume bv, + Matrix4f worldMatrix, + CollisionResults results) { + BoundingBox bbox; + if (bv instanceof BoundingSphere) { + BoundingSphere sphere = (BoundingSphere) bv; + bbox = new BoundingBox(bv.getCenter().clone(), sphere.getRadius(), + sphere.getRadius(), + sphere.getRadius()); + } else if (bv instanceof BoundingBox) { + bbox = new BoundingBox((BoundingBox) bv); + } else { + throw new UnsupportedCollisionException(); + } + + bbox.transform(worldMatrix.invert(), bbox); + return root.intersectWhere(bv, bbox, worldMatrix, this, results); + } + + public int collideWith(Collidable other, + Matrix4f worldMatrix, + BoundingVolume worldBound, + CollisionResults results) { + + if (other instanceof Ray) { + Ray ray = (Ray) other; + return collideWithRay(ray, worldMatrix, worldBound, results); + } else if (other instanceof BoundingVolume) { + BoundingVolume bv = (BoundingVolume) other; + return collideWithBoundingVolume(bv, worldMatrix, results); + } else { + throw new UnsupportedCollisionException(); + } + } + + public void write(JmeExporter ex) throws IOException { + OutputCapsule oc = ex.getCapsule(this); + oc.write(mesh, "mesh", null); + oc.write(root, "root", null); + oc.write(maxTrisPerNode, "tris_per_node", 0); + oc.write(pointData, "points", null); + oc.write(triIndices, "indices", null); + } + + public void read(JmeImporter im) throws IOException { + InputCapsule ic = im.getCapsule(this); + mesh = (Mesh) ic.readSavable("mesh", null); + root = (BIHNode) ic.readSavable("root", null); + maxTrisPerNode = ic.readInt("tris_per_node", 0); + pointData = ic.readFloatArray("points", null); + triIndices = ic.readIntArray("indices", null); + } +} diff --git a/engine/src/core/com/jme3/collision/bih/BIHTriangle.java b/engine/src/core/com/jme3/collision/bih/BIHTriangle.java new file mode 100644 index 0000000..2229da0 --- /dev/null +++ b/engine/src/core/com/jme3/collision/bih/BIHTriangle.java @@ -0,0 +1,111 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision.bih; + +import com.jme3.math.FastMath; +import com.jme3.math.Vector3f; + +public final class BIHTriangle { + + private final Vector3f pointa = new Vector3f(); + private final Vector3f pointb = new Vector3f(); + private final Vector3f pointc = new Vector3f(); + private final Vector3f center = new Vector3f(); + + public BIHTriangle(Vector3f p1, Vector3f p2, Vector3f p3) { + pointa.set(p1); + pointb.set(p2); + pointc.set(p3); + center.set(pointa); + center.addLocal(pointb).addLocal(pointc).multLocal(FastMath.ONE_THIRD); + } + + public Vector3f get1(){ + return pointa; + } + + public Vector3f get2(){ + return pointb; + } + + public Vector3f get3(){ + return pointc; + } + + public Vector3f getCenter() { + return center; + } + + public Vector3f getNormal(){ + Vector3f normal = new Vector3f(pointb); + normal.subtractLocal(pointa).crossLocal(pointc.x-pointa.x, pointc.y-pointa.y, pointc.z-pointa.z); + normal.normalizeLocal(); + return normal; + } + + public float getExtreme(int axis, boolean left){ + float v1, v2, v3; + switch (axis){ + case 0: v1 = pointa.x; v2 = pointb.x; v3 = pointc.x; break; + case 1: v1 = pointa.y; v2 = pointb.y; v3 = pointc.y; break; + case 2: v1 = pointa.z; v2 = pointb.z; v3 = pointc.z; break; + default: assert false; return 0; + } + if (left){ + if (v1 < v2){ + if (v1 < v3) + return v1; + else + return v3; + }else{ + if (v2 < v3) + return v2; + else + return v3; + } + }else{ + if (v1 > v2){ + if (v1 > v3) + return v1; + else + return v3; + }else{ + if (v2 > v3) + return v2; + else + return v3; + } + } + } + +} diff --git a/engine/src/core/com/jme3/collision/bih/TriangleAxisComparator.java b/engine/src/core/com/jme3/collision/bih/TriangleAxisComparator.java new file mode 100644 index 0000000..895dd5a --- /dev/null +++ b/engine/src/core/com/jme3/collision/bih/TriangleAxisComparator.java @@ -0,0 +1,63 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.collision.bih; + +import com.jme3.math.Vector3f; +import java.util.Comparator; + +public class TriangleAxisComparator implements Comparator<BIHTriangle> { + + private final int axis; + + public TriangleAxisComparator(int axis){ + this.axis = axis; + } + + public int compare(BIHTriangle o1, BIHTriangle o2) { + float v1, v2; + Vector3f c1 = o1.getCenter(); + Vector3f c2 = o2.getCenter(); + switch (axis){ + case 0: v1 = c1.x; v2 = c2.x; break; + case 1: v1 = c1.y; v2 = c2.y; break; + case 2: v1 = c1.z; v2 = c2.z; break; + default: assert false; return 0; + } + if (v1 > v2) + return 1; + else if (v1 < v2) + return -1; + else + return 0; + } +}
\ No newline at end of file |