From f86a7893490bc1295b6f8dfb1611c14645b00371 Mon Sep 17 00:00:00 2001
From: Sven Gothel <sgothel@jausoft.com>
Date: Wed, 16 May 2012 16:47:30 +0200
Subject: Graph minor linear optimization: use vertexInTriangle3(..) reduces
redundant computations
---
.../com/jogamp/graph/curve/OutlineShape.java | 13 ++--
.../classes/com/jogamp/graph/math/VectorUtil.java | 71 +++++++++++++++++++++-
2 files changed, 73 insertions(+), 11 deletions(-)
(limited to 'src/jogl')
diff --git a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
index f79dd6644..38b68702f 100755
--- a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
+++ b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
@@ -449,15 +449,10 @@ public class OutlineShape implements Comparable<OutlineShape> {
continue;
}
- {
- 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.vertexInTriangle3(a.getCoord(), b.getCoord(), c.getCoord(),
+ current.getCoord(), nextV.getCoord(), prevV.getCoord(),
+ tempVecAC, tempVecAB, tempVecAP) ) {
+ return current;
}
if(VectorUtil.testTri2SegIntersection(a, b, c, prevV, current) ||
VectorUtil.testTri2SegIntersection(a, b, c, current, nextV) ||
diff --git a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
index b41515aa4..524ca1171 100755
--- a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
+++ b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
@@ -312,7 +312,8 @@ 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
computeVector(ac, a, c); //v0
@@ -322,8 +323,8 @@ public class VectorUtil {
// Compute dot products
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 dot02 = dot(ac, ap);
final float dot12 = dot(ab, ap);
// Compute barycentric coordinates
@@ -335,6 +336,72 @@ public class VectorUtil {
return (u >= 0) && (v >= 0) && (u + v < 1);
}
+ /** Check if one of three vertices are in triangle using
+ * barycentric coordinates computation.
+ * @param a first triangle vertex
+ * @param b second triangle vertex
+ * @param c third triangle vertex
+ * @param p1 the vertex in question
+ * @param p2 the vertex in question
+ * @param p3 the vertex in question
+ * @return true if p1 or p2 or p3 is in triangle (a, b, c), false otherwise.
+ */
+ public static boolean vertexInTriangle3(float[] a, float[] b, float[] c,
+ float[] p1, float[] p2, float[] p3,
+ float[] ac, float[] ab, float[] ap){
+ // Compute vectors
+ computeVector(ac, a, c); //v0
+ computeVector(ab, a, b); //v1
+
+ // Compute dot products
+ final float dotAC_AC = dot(ac, ac);
+ final float dotAC_AB = dot(ac, ab);
+ final float dotAB_AB = dot(ab, ab);
+
+ // Compute barycentric coordinates
+ final float invDenom = 1 / (dotAC_AC * dotAB_AB - dotAC_AB * dotAC_AB);
+ {
+ computeVector(ap, a, p1); //v2
+ final float dotAC_AP1 = dot(ac, ap);
+ final float dotAB_AP1 = dot(ab, ap);
+ final float u1 = (dotAB_AB * dotAC_AP1 - dotAC_AB * dotAB_AP1) * invDenom;
+ final float v1 = (dotAC_AC * dotAB_AP1 - dotAC_AB * dotAC_AP1) * invDenom;
+
+ // Check if point is in triangle
+ if ( (u1 >= 0) && (v1 >= 0) && (u1 + v1 < 1) ) {
+ return true;
+ }
+ }
+
+ {
+ computeVector(ap, a, p2); //v2
+ final float dotAC_AP2 = dot(ac, ap);
+ final float dotAB_AP2 = dot(ab, ap);
+ final float u = (dotAB_AB * dotAC_AP2 - dotAC_AB * dotAB_AP2) * invDenom;
+ final float v = (dotAC_AC * dotAB_AP2 - dotAC_AB * dotAC_AP2) * invDenom;
+
+ // Check if point is in triangle
+ if ( (u >= 0) && (v >= 0) && (u + v < 1) ) {
+ return true;
+ }
+ }
+
+ {
+ computeVector(ap, a, p3); //v2
+ final float dotAC_AP3 = dot(ac, ap);
+ final float dotAB_AP3 = dot(ab, ap);
+ final float u = (dotAB_AB * dotAC_AP3 - dotAC_AB * dotAB_AP3) * invDenom;
+ final float v = (dotAC_AC * dotAB_AP3 - dotAC_AB * dotAC_AP3) * invDenom;
+
+ // Check if point is in triangle
+ if ( (u >= 0) && (v >= 0) && (u + v < 1) ) {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
/** Check if points are in ccw order
* @param a first vertex
* @param b second vertex
--
cgit v1.2.3