From e1d954439572d7e6776c0d928d1882e1cf200675 Mon Sep 17 00:00:00 2001
From: Sven Gothel <sgothel@jausoft.com>
Date: Wed, 16 May 2012 15:30:27 +0200
Subject: Graph minor linear optimization: Passing array storage (reduce temp
array) and use array ref access.
---
.../com/jogamp/graph/curve/OutlineShape.java | 24 ++--
.../classes/com/jogamp/graph/math/VectorUtil.java | 122 ++++++++++++++-------
2 files changed, 99 insertions(+), 47 deletions(-)
(limited to 'src/jogl/classes')
diff --git a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
index e60fba02b..f79dd6644 100755
--- a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
+++ b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
@@ -427,6 +427,10 @@ public class OutlineShape implements Comparable<OutlineShape> {
}while(!overlaps.isEmpty());
}
+ private final float[] tempVecAC = new float[3];
+ private final float[] tempVecAB = new float[3];
+ private final float[] tempVecAP = new float[3];
+
private Vertex checkTriOverlaps(Vertex a, Vertex b, Vertex c) {
int count = getOutlineNumber();
for (int cc = 0; cc < count; cc++) {
@@ -445,15 +449,19 @@ public class OutlineShape implements Comparable<OutlineShape> {
continue;
}
- if(VectorUtil.vertexInTriangle(a.getCoord(), b.getCoord(), c.getCoord(), current.getCoord())
- || VectorUtil.vertexInTriangle(a.getCoord(), b.getCoord(), c.getCoord(), nextV.getCoord())
- || VectorUtil.vertexInTriangle(a.getCoord(), b.getCoord(), c.getCoord(), prevV.getCoord())) {
-
- return current;
+ {
+ final float[] coordA = a.getCoord();
+ final float[] coordB = b.getCoord();
+ final float[] coordC = c.getCoord();
+ if(VectorUtil.vertexInTriangle(coordA, coordB, coordC, current.getCoord(), tempVecAC, tempVecAB, tempVecAP) ||
+ VectorUtil.vertexInTriangle(coordA, coordB, coordC, nextV.getCoord(), tempVecAC, tempVecAB, tempVecAP) ||
+ VectorUtil.vertexInTriangle(coordA, coordB, coordC, prevV.getCoord(), tempVecAC, tempVecAB, tempVecAP) ) {
+ return current;
+ }
}
- if(VectorUtil.tri2SegIntersection(a, b, c, prevV, current)
- || VectorUtil.tri2SegIntersection(a, b, c, current, nextV)
- || VectorUtil.tri2SegIntersection(a, b, c, prevV, nextV)) {
+ if(VectorUtil.testTri2SegIntersection(a, b, c, prevV, current) ||
+ VectorUtil.testTri2SegIntersection(a, b, c, current, nextV) ||
+ VectorUtil.testTri2SegIntersection(a, b, c, prevV, nextV)) {
return current;
}
}
diff --git a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
index d51afcbab..b41515aa4 100755
--- a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
+++ b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
@@ -249,19 +249,17 @@ public class VectorUtil {
}
/** Compute Vector
+ * @param vector storage for resulting Vector V1V2
* @param v1 vertex 1
* @param v2 vertex2 2
- * @return Vector V1V2
*/
- public static float[] computeVector(float[] v1, float[] v2)
+ public static void computeVector(float[] vector, float[] v1, float[] v2)
{
- float[] vector = new float[3];
vector[0] = v2[0] - v1[0];
vector[1] = v2[1] - v1[1];
- vector[2] = v2[2] - v1[2];
- return vector;
+ vector[2] = v2[2] - v1[2];
}
-
+
/** Check if vertices in triangle circumcircle
* @param a triangle vertex 1
* @param b triangle vertex 2
@@ -271,10 +269,14 @@ public class VectorUtil {
* vertices a, b, c. from paper by Guibas and Stolfi (1985).
*/
public static boolean inCircle(Vertex a, Vertex b, Vertex c, Vertex d){
- return (a.getX() * a.getX() + a.getY() * a.getY()) * triArea(b, c, d) -
- (b.getX() * b.getX() + b.getY() * b.getY()) * triArea(a, c, d) +
- (c.getX() * c.getX() + c.getY() * c.getY()) * triArea(a, b, d) -
- (d.getX() * d.getX() + d.getY() * d.getY()) * triArea(a, b, c) > 0;
+ final float[] A = a.getCoord();
+ final float[] B = b.getCoord();
+ final float[] C = c.getCoord();
+ final float[] D = d.getCoord();
+ return (A[0] * A[0] + A[1] * A[1]) * triArea(B, C, D) -
+ (B[0] * B[0] + B[1] * B[1]) * triArea(A, C, D) +
+ (C[0] * C[0] + C[1] * C[1]) * triArea(A, B, D) -
+ (D[0] * D[0] + D[1] * D[1]) * triArea(A, B, C) > 0;
}
/** Computes oriented area of a triangle
@@ -285,9 +287,23 @@ public class VectorUtil {
* is positive if the triangle is oriented counterclockwise.
*/
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());
+ final float[] A = a.getCoord();
+ final float[] B = b.getCoord();
+ final float[] C = c.getCoord();
+ return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1])*(C[0] - A[0]);
}
+ /** Computes oriented area of a triangle
+ * @param A first vertex
+ * @param B second vertex
+ * @param C third vertex
+ * @return compute twice the area of the oriented triangle (a,b,c), the area
+ * is positive if the triangle is oriented counterclockwise.
+ */
+ public static float triArea(float[] A, float[] B, float[] C){
+ return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1])*(C[0] - A[0]);
+ }
+
/** Check if a vertex is in triangle using
* barycentric coordinates computation.
* @param a first triangle vertex
@@ -296,23 +312,24 @@ public class VectorUtil {
* @param p the vertex in question
* @return true if p is in triangle (a, b, c), false otherwise.
*/
- public static boolean vertexInTriangle(float[] a, float[] b, float[] c, float[] p){
+ public static boolean vertexInTriangle(float[] a, float[] b, float[] c, float[] p,
+ float[] ac, float[] ab, float[] ap){
// Compute vectors
- float[] ac = computeVector(a, c); //v0
- float[] ab = computeVector(a, b); //v1
- float[] ap = computeVector(a, p); //v2
+ computeVector(ac, a, c); //v0
+ computeVector(ab, a, b); //v1
+ computeVector(ap, 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);
+ final float dot00 = dot(ac, ac);
+ final float dot01 = dot(ac, ab);
+ final float dot02 = dot(ac, ap);
+ final float dot11 = dot(ab, ab);
+ final 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;
+ final float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
+ final float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+ final float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v < 1);
@@ -372,24 +389,56 @@ public class VectorUtil {
* 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());
+ final 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;
+ final float alpha = (a.getX()*b.getY()-a.getY()*b.getX());
+ final float beta = (c.getX()*d.getY()-c.getY()*d.getY());
+ final float xi = ((c.getX()-d.getX())*alpha-(a.getX()-b.getX())*beta)/determinant;
+ final 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());
+ final float gamma = (xi - a.getX())/(b.getX() - a.getX());
+ final 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 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 true if the segments intersect, otherwise returns false
+ */
+ public static boolean testSeg2SegIntersection(Vertex a, Vertex b, Vertex c, Vertex d) {
+ final float[] A = a.getCoord();
+ final float[] B = b.getCoord();
+ final float[] C = c.getCoord();
+ final float[] D = d.getCoord();
+
+ final float determinant = (A[0]-B[0])*(C[1]-D[1]) - (A[1]-B[1])*(C[0]-D[0]);
+
+ if (determinant == 0) {
+ return false;
+ }
+
+ final float alpha = (A[0]*B[1]-A[1]*B[0]);
+ final float beta = (C[0]*D[1]-C[1]*D[1]);
+ final float xi = ((C[0]-D[0])*alpha-(A[0]-B[0])*beta)/determinant;
+
+ final float gamma = (xi - A[0])/(B[0] - A[0]);
+ final float gamma1 = (xi - C[0])/(D[0] - C[0]);
+ if(gamma <= 0 || gamma >= 1 || gamma1 <= 0 || gamma1 >= 1) {
+ return false;
+ }
+
+ return true;
+ }
+
/** Compute intersection between two lines
* @param a vertex 1 of first line
* @param b vertex 2 of first line
@@ -420,14 +469,9 @@ public class VectorUtil {
* @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;
+ public static boolean testTri2SegIntersection(Vertex a, Vertex b, Vertex c, Vertex d, Vertex e){
+ return testSeg2SegIntersection(a, b, d, e) ||
+ testSeg2SegIntersection(b, c, d, e) ||
+ testSeg2SegIntersection(a, c, d, e) ;
}
}
--
cgit v1.2.3