From b71946ce8b1b7ce9ca3d26c554d4a9862aabd577 Mon Sep 17 00:00:00 2001 From: Rami Santina Date: Mon, 20 Jun 2011 14:27:56 +0300 Subject: Handle curved triangles overlaps. subdivde overlaping triangles for the case when 2 triangles intersect either by vextex of Traingle A in Triangle B or an edge in A intersects an edge in B VectorUtil: -added tri2triIntersection test (not optimized) -added seg2segIntersection test (not optimized) --- .../classes/com/jogamp/graph/math/VectorUtil.java | 134 ++++++++++++++++----- 1 file changed, 104 insertions(+), 30 deletions(-) (limited to 'src/jogl/classes/com/jogamp/graph/math') diff --git a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java index 2b4a7fd9d..b1f2023f3 100755 --- a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java +++ b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java @@ -44,7 +44,7 @@ public class VectorUtil { this.dir = dir; } } - + public static final int COLLINEAR = 0; /** compute the dot product of two points @@ -88,7 +88,7 @@ public class VectorUtil { newVector[2] = vector[2]*scale; return newVector; } - + /** Adds to vectors * @param v1 vector 1 * @param v2 vector 2 @@ -135,7 +135,7 @@ public class VectorUtil { return out; } - + /** Matrix Vector multiplication * @param rawMatrix column matrix (4x4) * @param vec vector(x,y,z) @@ -151,7 +151,7 @@ public class VectorUtil { return out; } - + /** Calculate the midpoint of two values * @param p1 first value * @param p2 second vale @@ -169,9 +169,9 @@ public class VectorUtil { public static float[] mid(float[] p1, float[] p2) { float[] midPoint = new float[3]; - midPoint[0] = (p1[0] + p2[0])/2.0f; - midPoint[1] = (p1[1] + p2[1])/2.0f; - midPoint[2] = (p1[2] + p2[2])/2.0f; + midPoint[0] = (p1[0] + p2[0])*0.5f; + midPoint[1] = (p1[1] + p2[1])*0.5f; + midPoint[2] = (p1[2] + p2[2])*0.5f; return midPoint; } @@ -206,8 +206,8 @@ public class VectorUtil { public static boolean checkEquality(float[] v1, float[] v2) { if(Float.compare(v1[0], v2[0]) == 0 && - Float.compare(v1[1], v2[1]) == 0 && - Float.compare(v1[2], v2[2]) == 0 ) + Float.compare(v1[1], v2[1]) == 0 && + Float.compare(v1[2], v2[2]) == 0 ) return true; return false; } @@ -220,7 +220,7 @@ public class VectorUtil { public static boolean checkEqualityVec2(float[] v1, float[] v2) { if(Float.compare(v1[0], v2[0]) == 0 && - Float.compare(v1[1], v2[1]) == 0) + Float.compare(v1[1], v2[1]) == 0) return true; return false; } @@ -287,7 +287,7 @@ public class VectorUtil { public static float triArea(Vertex a, Vertex b, Vertex c){ return (b.getX() - a.getX()) * (c.getY() - a.getY()) - (b.getY() - a.getY())*(c.getX() - a.getX()); } - + /** Check if a vertex is in triangle using * barycentric coordinates computation. * @param a first triangle vertex @@ -297,25 +297,25 @@ public class VectorUtil { * @return true if p is in triangle (a, b, c), false otherwise. */ public static boolean vertexInTriangle(float[] a, float[] b, float[] c, float[] p){ - // Compute vectors - float[] ac = computeVector(a, c); //v0 - float[] ab = computeVector(a, b); //v1 - float[] ap = computeVector(a, p); //v2 - - // Compute dot products - float dot00 = dot(ac, ac); - float dot01 = dot(ac, ab); - float dot02 = dot(ac, ap); - float dot11 = dot(ab, ab); - float dot12 = dot(ab, ap); - - // Compute barycentric coordinates - float invDenom = 1 / (dot00 * dot11 - dot01 * dot01); - float u = (dot11 * dot02 - dot01 * dot12) * invDenom; - float v = (dot00 * dot12 - dot01 * dot02) * invDenom; - - // Check if point is in triangle - return (u > 0) && (v > 0) && (u + v < 1); + // Compute vectors + float[] ac = computeVector(a, c); //v0 + float[] ab = computeVector(a, b); //v1 + float[] ap = computeVector(a, p); //v2 + + // Compute dot products + float dot00 = dot(ac, ac); + float dot01 = dot(ac, ab); + float dot02 = dot(ac, ap); + float dot11 = dot(ab, ab); + float dot12 = dot(ab, ap); + + // Compute barycentric coordinates + float invDenom = 1 / (dot00 * dot11 - dot01 * dot01); + float u = (dot11 * dot02 - dot01 * dot12) * invDenom; + float v = (dot00 * dot12 - dot01 * dot02) * invDenom; + + // Check if point is in triangle + return (u >= 0) && (v >= 0) && (u + v < 1); } /** Check if points are in ccw order @@ -353,7 +353,81 @@ public class VectorUtil { } return area; } + + /** Compute the general winding of the vertices + * @param vertices array of Vertices + * @return CCW or CW {@link Winding} + */ public static Winding getWinding(ArrayList vertices) { return area(vertices) >= 0 ? Winding.CCW : Winding.CW ; } + + + /** Compute intersection between two segments + * @param a vertex 1 of first segment + * @param b vertex 2 of first segment + * @param c vertex 1 of second segment + * @param d vertex 2 of second segment + * @return the intersection coordinates if the segments intersect, otherwise + * returns null + */ + public static float[] seg2SegIntersection(Vertex a, Vertex b, Vertex c, Vertex d) { + float determinant = (a.getX()-b.getX())*(c.getY()-d.getY()) - (a.getY()-b.getY())*(c.getX()-d.getX()); + + if (determinant == 0) + return null; + + float alpha = (a.getX()*b.getY()-a.getY()*b.getX()); + float beta = (c.getX()*d.getY()-c.getY()*d.getY()); + float xi = ((c.getX()-d.getX())*alpha-(a.getX()-b.getX())*beta)/determinant; + float yi = ((c.getY()-d.getY())*alpha-(a.getY()-b.getY())*beta)/determinant; + + float gamma = (xi - a.getX())/(b.getX() - a.getX()); + float gamma1 = (xi - c.getX())/(d.getX() - c.getX()); + if(gamma <= 0 || gamma >= 1) return null; + if(gamma1 <= 0 || gamma1 >= 1) return null; + + return new float[]{xi,yi,0}; + } + + /** Compute intersection between two lines + * @param a vertex 1 of first line + * @param b vertex 2 of first line + * @param c vertex 1 of second line + * @param d vertex 2 of second line + * @return the intersection coordinates if the lines intersect, otherwise + * returns null + */ + public static float[] line2lineIntersection(Vertex a, Vertex b, Vertex c, Vertex d) { + float determinant = (a.getX()-b.getX())*(c.getY()-d.getY()) - (a.getY()-b.getY())*(c.getX()-d.getX()); + + if (determinant == 0) + return null; + + float alpha = (a.getX()*b.getY()-a.getY()*b.getX()); + float beta = (c.getX()*d.getY()-c.getY()*d.getY()); + float xi = ((c.getX()-d.getX())*alpha-(a.getX()-b.getX())*beta)/determinant; + float yi = ((c.getY()-d.getY())*alpha-(a.getY()-b.getY())*beta)/determinant; + + return new float[]{xi,yi,0}; + } + + /** Check if a segment intersects with a triangle + * @param a vertex 1 of the triangle + * @param b vertex 2 of the triangle + * @param c vertex 3 of the triangle + * @param d vertex 1 of first segment + * @param e vertex 2 of first segment + * @return true if the segment intersects at least one segment of the triangle, false otherwise + */ + public static boolean tri2SegIntersection(Vertex a, Vertex b, Vertex c, Vertex d, Vertex e){ + if(seg2SegIntersection(a, b, d, e) != null) + return true; + if(seg2SegIntersection(b, c, d, e) != null) + return true; + if(seg2SegIntersection(a, c, d, e) != null) + return true; + + return false; + } } -- cgit v1.2.3