Added GLU_TESS_AVOID_DEGENERATE_TRIANGLES boolean property to the GLU

tessellator to try to improve the triangulation to support
antialiasing in the JavaFX graphics stack. The new code largely works
as intended, but is not as robust as desired, and also does not
completely solve the problem. Checking in nonetheless to checkpoint
the work.


git-svn-id: file:///usr/local/projects/SUN/JOGL/git-svn/svn-server-sync/jogl/branches/JOGL_2_SANDBOX@1802 232f8b59-042b-4e1e-8c03-345bb8c30851

3 files changed, 67 insertions, 4 deletions

diff --git a/src/classes/com/sun/opengl/impl/glu/tessellator/GLUtessellatorImpl.java b/src/classes/com/sun/opengl/impl/glu/tessellator/GLUtessellatorImpl.java
index 4f36c7018..f4efb116a 100644
--- a/src/classes/com/sun/opengl/impl/glu/tessellator/GLUtessellatorImpl.java
+++ b/src/classes/com/sun/opengl/impl/glu/tessellator/GLUtessellatorImpl.java
@@ -85,6 +85,10 @@ public class GLUtessellatorImpl implements GLUtessellator {
 
     boolean flagBoundary;	/* mark boundary edges (use EdgeFlag) */
     boolean boundaryOnly;	/* Extract contours, not triangles */
+    boolean avoidDegenerateTris; /* JOGL-specific hint to try to improve triangulation
+                                    by avoiding producing degenerate (zero-area) triangles;
+                                    has not been tested exhaustively and is therefore an option */
+
     GLUface lonelyTriList;
     /* list of triangles which could not be rendered as strips or fans */
 
@@ -234,6 +238,10 @@ public class GLUtessellatorImpl implements GLUtessellator {
                 boundaryOnly = (value != 0);
                 return;
 
+            case GLU.GLU_TESS_AVOID_DEGENERATE_TRIANGLES:
+                avoidDegenerateTris = (value != 0);
+                return;
+
             default:
                 callErrorOrErrorData(GLU.GLU_INVALID_ENUM);
                 return;
@@ -261,6 +269,9 @@ public class GLUtessellatorImpl implements GLUtessellator {
                 assert (boundaryOnly == true || boundaryOnly == false);
                 value[value_offset] = boundaryOnly ? 1 : 0;
                 break;
+            case GLU.GLU_TESS_AVOID_DEGENERATE_TRIANGLES:
+                value[value_offset] = avoidDegenerateTris ? 1 : 0;
+                break;
             default:
                 value[value_offset] = 0.0;
                 callErrorOrErrorData(GLU.GLU_INVALID_ENUM);
@@ -526,7 +537,7 @@ public class GLUtessellatorImpl implements GLUtessellator {
                 if (boundaryOnly) {
                     rc = TessMono.__gl_meshSetWindingNumber(mesh, 1, true);
                 } else {
-                    rc = TessMono.__gl_meshTessellateInterior(mesh);
+                    rc = TessMono.__gl_meshTessellateInterior(mesh, avoidDegenerateTris);
                 }
                 if (!rc) throw new RuntimeException();	/* could've used a label */
 
diff --git a/src/classes/com/sun/opengl/impl/glu/tessellator/Geom.java b/src/classes/com/sun/opengl/impl/glu/tessellator/Geom.java
index 6b31cc30e..1287a60e0 100644
--- a/src/classes/com/sun/opengl/impl/glu/tessellator/Geom.java
+++ b/src/classes/com/sun/opengl/impl/glu/tessellator/Geom.java
@@ -315,4 +315,24 @@ class Geom {
     static double VertL1dist(GLUvertex u, GLUvertex v) {
         return Math.abs(u.s - v.s) + Math.abs(u.t - v.t);
     }
+
+    /***********************************************************************/
+
+    // Compute the cosine of the angle between the edges between o and
+    // v1 and between o and v2
+    static double EdgeCos(GLUvertex o, GLUvertex v1, GLUvertex v2) {
+        double ov1s = v1.s - o.s;
+        double ov1t = v1.t - o.t;
+        double ov2s = v2.s - o.s;
+        double ov2t = v2.t - o.t;
+        double dotp = ov1s * ov2s + ov1t * ov2t;
+        double len = Math.sqrt(ov1s * ov1s + ov1t * ov1t) * Math.sqrt(ov2s * ov2s + ov2t * ov2t);
+        if (len > 0.0) {
+            dotp /= len;
+        }
+        return dotp;
+    }
+
+    static final double EPSILON = 1.0e-5;
+    static final double ONE_MINUS_EPSILON = 1.0 - EPSILON;
 }
diff --git a/src/classes/com/sun/opengl/impl/glu/tessellator/TessMono.java b/src/classes/com/sun/opengl/impl/glu/tessellator/TessMono.java
index 62c653bfe..fe0f7946c 100644
--- a/src/classes/com/sun/opengl/impl/glu/tessellator/TessMono.java
+++ b/src/classes/com/sun/opengl/impl/glu/tessellator/TessMono.java
@@ -80,7 +80,7 @@ class TessMono {
  * to the fan is a simple orientation test.  By making the fan as large
  * as possible, we restore the invariant (check it yourself).
  */
-    static boolean __gl_meshTessellateMonoRegion(GLUface face) {
+    static boolean __gl_meshTessellateMonoRegion(GLUface face, boolean avoidDegenerateTris) {
         GLUhalfEdge up, lo;
 
         /* All edges are oriented CCW around the boundary of the region.
@@ -97,7 +97,37 @@ class TessMono {
             ;
         lo = up.Onext.Sym;
 
+        boolean mustConnect = false; // hack for avoidDegenerateTris
+
         while (up.Lnext != lo) {
+            if (avoidDegenerateTris && !mustConnect) {
+                // Skip over regions where several vertices are collinear,
+                // to try to avoid producing degenerate (zero-area) triangles
+                //
+                // The "mustConnect" flag is a hack to try to avoid
+                // skipping too large regions and causing incorrect
+                // triangulations. This entire modification is overall
+                // not robust and needs more work
+                if (Geom.EdgeCos(lo.Lnext.Org, lo.Org, lo.Lnext.Lnext.Org) <= -Geom.ONE_MINUS_EPSILON) {
+                    // Lines around lo
+                    do {
+                        lo = lo.Onext.Sym;
+                        mustConnect = true;
+                    } while (up.Lnext != lo &&
+                             Geom.EdgeCos(lo.Lnext.Org, lo.Org, lo.Lnext.Lnext.Org) <= -Geom.ONE_MINUS_EPSILON);
+                } else if (Geom.EdgeCos(up.Onext.Sym.Org, up.Org, up.Onext.Sym.Onext.Sym.Org) <= -Geom.ONE_MINUS_EPSILON) {
+                    // Lines around up
+                    do {
+                        up = up.Lnext;
+                        mustConnect = true;
+                    } while (up.Lnext != lo &&
+                             Geom.EdgeCos(up.Onext.Sym.Org, up.Org, up.Onext.Sym.Onext.Sym.Org) <= -Geom.ONE_MINUS_EPSILON);
+                }
+
+                if (up.Lnext == lo)
+                    break;
+            }
+
             if (Geom.VertLeq(up.Sym.Org, lo.Org)) {
                 /* up.Sym.Org is on the left.  It is safe to form triangles from lo.Org.
                  * The EdgeGoesLeft test guarantees progress even when some triangles
@@ -106,6 +136,7 @@ class TessMono {
                 while (lo.Lnext != up && (Geom.EdgeGoesLeft(lo.Lnext)
                         || Geom.EdgeSign(lo.Org, lo.Sym.Org, lo.Lnext.Sym.Org) <= 0)) {
                     GLUhalfEdge tempHalfEdge = Mesh.__gl_meshConnect(lo.Lnext, lo);
+                    mustConnect = false;
                     if (tempHalfEdge == null) return false;
                     lo = tempHalfEdge.Sym;
                 }
@@ -115,6 +146,7 @@ class TessMono {
                 while (lo.Lnext != up && (Geom.EdgeGoesRight(up.Onext.Sym)
                         || Geom.EdgeSign(up.Sym.Org, up.Org, up.Onext.Sym.Org) >= 0)) {
                     GLUhalfEdge tempHalfEdge = Mesh.__gl_meshConnect(up, up.Onext.Sym);
+                    mustConnect = false;
                     if (tempHalfEdge == null) return false;
                     up = tempHalfEdge.Sym;
                 }
@@ -140,7 +172,7 @@ class TessMono {
  * the mesh which is marked "inside" the polygon.  Each such region
  * must be monotone.
  */
-    public static boolean __gl_meshTessellateInterior(GLUmesh mesh) {
+    public static boolean __gl_meshTessellateInterior(GLUmesh mesh, boolean avoidDegenerateTris) {
         GLUface f, next;
 
         /*LINTED*/
@@ -148,7 +180,7 @@ class TessMono {
             /* Make sure we don''t try to tessellate the new triangles. */
             next = f.next;
             if (f.inside) {
-                if (!__gl_meshTessellateMonoRegion(f)) return false;
+                if (!__gl_meshTessellateMonoRegion(f, avoidDegenerateTris)) return false;
             }
         }