From 12b9790a8286085423bb649e7632644f31142d24 Mon Sep 17 00:00:00 2001
From: megacz <adam@megacz.com>
Date: Sat, 28 Feb 2009 15:34:37 -0800
Subject: [PATCH] MarchingCubes.java: snap points to grid if they are close;
 this eliminates many mesh irregularities

---
 src/edu/berkeley/qfat/voxel/MarchingCubes.java |   31 +++++++++++++++++-------
 1 file changed, 22 insertions(+), 9 deletions(-)

diff --git a/src/edu/berkeley/qfat/voxel/MarchingCubes.java b/src/edu/berkeley/qfat/voxel/MarchingCubes.java
index 58434f4..a365585 100644
--- a/src/edu/berkeley/qfat/voxel/MarchingCubes.java
+++ b/src/edu/berkeley/qfat/voxel/MarchingCubes.java
@@ -74,11 +74,9 @@ public class MarchingCubes {
 
         // Find which vertices are inside of the surface and which are outside
         iFlagIndex = 0;
-        for(iVertexTest = 0; iVertexTest < 8; iVertexTest++) {
-            if (afCubeValue[iVertexTest] >= threshold) {
+        for(iVertexTest = 0; iVertexTest < 8; iVertexTest++)
+            if (afCubeValue[iVertexTest] >= threshold)
                 iFlagIndex |= 1<<iVertexTest;
-            }
-        }
         
         // Find which edges are intersected by the surface
         iEdgeFlags = aiCubeEdgeFlags[iFlagIndex];
@@ -92,7 +90,9 @@ public class MarchingCubes {
             // If there is an intersection on this edge
             if ((iEdgeFlags & (1<<iEdge))==0) continue;
             fOffset = fGetOffset(afCubeValue[ a2iEdgeConnection[iEdge][0] ], 
-                                 afCubeValue[ a2iEdgeConnection[iEdge][1] ], threshold);
+                                 afCubeValue[ a2iEdgeConnection[iEdge][1] ],
+                                 threshold,
+                                 fScale * 0.1);
             
             asEdgeVertex[iEdge].fX = fX + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][0]  +  fOffset * a2fEdgeDirection[iEdge][0]) * fScale;
             asEdgeVertex[iEdge].fY = fY + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][1]  +  fOffset * a2fEdgeDirection[iEdge][1]) * fScale;
@@ -115,9 +115,14 @@ public class MarchingCubes {
                 // questionable, but we do it anyways
                 norm = norm.plus(new Vec(asEdgeNorm[iVertex].fX,   asEdgeNorm[iVertex].fY,   asEdgeNorm[iVertex].fZ));
             }
-            if (points[0].equals(points[1])) continue;
-            if (points[0].equals(points[2])) continue;
-            if (points[1].equals(points[2])) continue;
+
+            // Eliminate triangles with "length-zero" sides.
+            // Unfortunately this puts holes in the mesh.
+            if (points[0].equals(points[1]) ||
+                points[0].equals(points[2]) ||
+                points[1].equals(points[2]))
+                continue;
+
             mesh.newT(points[0], points[1], points[2], norm.norm().times(-1));
         }
     }
@@ -162,9 +167,17 @@ public class MarchingCubes {
 
     // fGetOffset finds the approximate point of intersection of the surface
     // between two points with the values fValue1 and fValue2
-    static double fGetOffset(double fValue1, double fValue2, double fValueDesired) {
+    static double fGetOffset(double fValue1, double fValue2, double fValueDesired, double EPSILON) {
         double fDelta = fValue2 - fValue1;
         if(fDelta == 0.0) return 0.5;
+
+        // the following two lines are a hack; they "snap" the
+        // estimate to one grid point or the other if the distance is
+        // less than some EPSILON.  This ensures that the resulting
+        // mesh is watertight and meets the requirements of Mesh.java
+        if (Math.abs(fValueDesired-fValue1) < EPSILON) return 0;
+        if (Math.abs(fValueDesired-fValue2) < EPSILON) return 1;
+
         return (fValueDesired - fValue1)/fDelta;
     }
 
-- 
1.7.10.4