Other fixes to the Newell's algorithm implementation
authorAntonio Ospite <ospite@studenti.unina.it>
Sun, 14 Jan 2007 09:48:50 +0000 (10:48 +0100)
committerAntonio Ospite <ospite@studenti.unina.it>
Thu, 24 Sep 2009 16:49:58 +0000 (18:49 +0200)
Signed-off-by: Antonio Ospite <ospite@studenti.unina.it>
vrm.py

diff --git a/vrm.py b/vrm.py
index 82922f8..7cf79bc 100755 (executable)
--- a/vrm.py
+++ b/vrm.py
@@ -114,18 +114,20 @@ class config:
 
 
 # Utility functions
 
 
 # Utility functions
-print_debug = True
+print_debug = False
 def debug(msg):
     if print_debug:
         sys.stderr.write(msg)
 
 def debug(msg):
     if print_debug:
         sys.stderr.write(msg)
 
+EPS = 10e-5
+
 def sign(x):
 def sign(x):
-    if x == 0:
-        return 0
-    elif x < 0:
+    if x < -EPS:
         return -1
         return -1
-    else:
+    elif x > EPS:
         return 1
         return 1
+    else:
+        return 0
 
 
 # ---------------------------------------------------------------------
 
 
 # ---------------------------------------------------------------------
@@ -808,7 +810,8 @@ class SVGVectorWriter(VectorWriter):
             opacity_string = ""
             if color[3] != 255:
                 opacity = float(color[3])/255.0
             opacity_string = ""
             if color[3] != 255:
                 opacity = float(color[3])/255.0
-                opacity_string = " fill-opacity: %g; stroke-opacity: %g; opacity: 1;" % (opacity, opacity)
+                #opacity_string = " fill-opacity: %g; stroke-opacity: %g; opacity: 1;" % (opacity, opacity)
+                opacity_string = "opacity: %g;" % (opacity)
 
             self.file.write("\tstyle=\"fill:" + str_col + ";")
             self.file.write(opacity_string)
 
             self.file.write("\tstyle=\"fill:" + str_col + ";")
             self.file.write(opacity_string)
@@ -818,8 +821,9 @@ class SVGVectorWriter(VectorWriter):
             # see http://www.antigrain.com/svg/index.html for more info
             stroke_width = 1.0
 
             # see http://www.antigrain.com/svg/index.html for more info
             stroke_width = 1.0
 
-            if config.polygons['EXPANSION_TRICK']:
-                str_col = "#000000" # For debug
+            # EXPANSION TRICK is not that useful where there is transparency
+            if config.polygons['EXPANSION_TRICK'] and color[3] == 255:
+                # str_col = "#000000" # For debug
                 self.file.write(" stroke:%s;\n" % str_col)
                 self.file.write(" stroke-width:" + str(stroke_width) + ";\n")
                 self.file.write(" stroke-linecap:round;stroke-linejoin:round")
                 self.file.write(" stroke:%s;\n" % str_col)
                 self.file.write(" stroke-width:" + str(stroke_width) + ";\n")
                 self.file.write(" stroke-linecap:round;stroke-linejoin:round")
@@ -1033,16 +1037,19 @@ class Renderer:
             self._doModelingTransformation(mesh, obj.matrix)
 
             self._doBackFaceCulling(mesh)
             self._doModelingTransformation(mesh, obj.matrix)
 
             self._doBackFaceCulling(mesh)
-            if True:
+
+            # When doing HSR with NEWELL we may want to flip all normals
+            # toward the viewer
+            if config.polygons['HSR'] == "NEWELL":
                 for f in mesh.faces:
                     f.sel = 1-f.sel
                 mesh.flipNormals()
                 for f in mesh.faces:
                     f.sel = 1
 
                 for f in mesh.faces:
                     f.sel = 1-f.sel
                 mesh.flipNormals()
                 for f in mesh.faces:
                     f.sel = 1
 
-
             self._doLighting(mesh)
 
             self._doLighting(mesh)
 
+
             # Do "projection" now so we perform further processing
             # in Normalized View Coordinates
             self._doProjection(mesh, self.proj)
             # Do "projection" now so we perform further processing
             # in Normalized View Coordinates
             self._doProjection(mesh, self.proj)
@@ -1159,8 +1166,8 @@ class Renderer:
     def _doConvertGeometricObjsToMesh(self, scene):
         """Convert all "geometric" objects to mesh ones.
         """
     def _doConvertGeometricObjsToMesh(self, scene):
         """Convert all "geometric" objects to mesh ones.
         """
-        #geometricObjTypes = ['Mesh', 'Surf', 'Curve', 'Text']
-        geometricObjTypes = ['Mesh', 'Surf', 'Curve']
+        geometricObjTypes = ['Mesh', 'Surf', 'Curve', 'Text']
+        #geometricObjTypes = ['Mesh', 'Surf', 'Curve']
 
         Objects = scene.getChildren()
         objList = [ o for o in Objects if o.getType() in geometricObjTypes ]
 
         Objects = scene.getChildren()
         objList = [ o for o in Objects if o.getType() in geometricObjTypes ]
@@ -1453,7 +1460,7 @@ class Renderer:
         
 
         by_furthest_z = (lambda f1, f2: progress.update() and
         
 
         by_furthest_z = (lambda f1, f2: progress.update() and
-                cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2]))
+                cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2])+EPS)
                 )
 
         # FIXME: using NMesh to sort faces. We should avoid that!
                 )
 
         # FIXME: using NMesh to sort faces. We should avoid that!
@@ -1477,11 +1484,13 @@ class Renderer:
         """Newell's depth sorting.
 
         """
         """Newell's depth sorting.
 
         """
+        global EPS
+
         by_furthest_z = (lambda f1, f2:
         by_furthest_z = (lambda f1, f2:
-                cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2]))
+                cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2])+EPS)
                 )
 
                 )
 
-        mesh.quadToTriangle(0)
+        mesh.quadToTriangle()
 
         from split import Distance, isOnSegment
 
 
         from split import Distance, isOnSegment
 
@@ -1494,29 +1503,48 @@ class Renderer:
                 v2 = Vector(P.v[i])
                 v2[2] = 0
 
                 v2 = Vector(P.v[i])
                 v2[2] = 0
 
-                EPS = 10e-7
+                EPS = 10e-5
 
                 for j in range(0, len(Q.v)):
 
                 for j in range(0, len(Q.v)):
+
                     v3 = Vector(Q.v[j-1])
                     v3[2] = 0
                     v4 = Vector(Q.v[j])
                     v4[2] = 0
                     v3 = Vector(Q.v[j-1])
                     v3[2] = 0
                     v4 = Vector(Q.v[j])
                     v4[2] = 0
+
+                    #print "\n\nTEST if we have coincidence!"
+                    #print v1, v2
+                    #print v3, v4
+                    #print "distances:"
+                    d1 = (v1-v3).length
+                    d2 = (v1-v4).length
+                    d3 = (v2-v3).length
+                    d4 = (v2-v4).length
+                    #print d1, d2, d3, d4
+                    #print "-----------------------\n"
+
+                    if d1 < EPS or d2 < EPS or d3 < EPS or d4 < EPS:
+                        continue
                     
                     
+                    # TODO: Replace with LineIntersect2D in newer API
                     ret = LineIntersect(v1, v2, v3, v4)
                     ret = LineIntersect(v1, v2, v3, v4)
+
                     # if line v1-v2 and v3-v4 intersect both return
                     # values are the same.
                     # if line v1-v2 and v3-v4 intersect both return
                     # values are the same.
-                    if ret and ret[0] == ret[1]  and isOnSegment(v1, v2,
-                            ret[0], True) and isOnSegment(v3, v4, ret[1], True):
+                    if ret and ret[0] == ret[1]  and isOnSegment(v1, v2, ret[0], True) and isOnSegment(v3, v4, ret[1], True):
 
 
+                        #l1 = (ret[0] - v1).length
+                        #l2 = (ret[0] - v2).length
 
 
-                        l1 = (ret[0] - v1).length
-                        l2 = (ret[0] - v2).length
+                        #l3 = (ret[1] - v3).length
+                        #l4 = (ret[1] - v4).length
 
 
-                        l3 = (ret[1] - v3).length
-                        l4 = (ret[1] - v4).length
+                        #print "New DISTACES againt the intersection point:"
+                        #print l1, l2, l3, l4
+                        #print "-----------------------\n"
 
 
-                        if  (l1 < EPS or l2 < EPS) and (l3 < EPS or l4 < EPS):
-                            continue
+                        #if  l1 < EPS or l2 < EPS or l3 < EPS or l4 < EPS:
+                        #    continue
 
                         debug("Projections OVERLAP!!\n")
                         debug("line1:"+
 
                         debug("Projections OVERLAP!!\n")
                         debug("line1:"+
@@ -1548,45 +1576,31 @@ class Renderer:
         facelist = nmesh.faces[:]
         maplist = []
 
         facelist = nmesh.faces[:]
         maplist = []
 
-        EPS = 10e-8
-        #EPS = 0
+        EPS = 10e-5
 
         global progress
 
         global progress
+
         # The steps are _at_least_ equal to len(facelist), we do not count the
         # The steps are _at_least_ equal to len(facelist), we do not count the
-        # feces coming out from plitting!!
+        # feces coming out from splitting!!
         progress.setActivity("HSR: Newell", len(facelist))
         progress.setActivity("HSR: Newell", len(facelist))
-        progress.setQuiet(True)
+        #progress.setQuiet(True)
 
         
 
         
-        steps = -1
-        split_done = 0
-        marked_face = 0
+        #split_done = 0
+        #marked_face = 0
 
         while len(facelist):
 
         while len(facelist):
-            print "\n----------------------"
+            debug("\n----------------------\n")
+            debug("len(facelits): %d\n" % len(facelist))
             P = facelist[0]
             P = facelist[0]
-            
-            #steps += 1
-            #if steps == 3:
-            #    maplist = facelist
-            #    break
-            print len(facelist)
-            if len(facelist) == 33:
-                #maplist = facelist
-                break
-
 
 
-            #pSign = 1
-            #if P.normal[2] < 0:
-            #    pSign = -1
             pSign = sign(P.normal[2])
 
             pSign = sign(P.normal[2])
 
-            # We can discard faces thar are perpendicular to the view
+            # We can discard faces parallel to the view vector
             if pSign == 0:
                 facelist.remove(P)
                 continue
 
             if pSign == 0:
                 facelist.remove(P)
                 continue
 
-
             split_done = 0
             face_marked = 0
 
             split_done = 0
             face_marked = 0
 
@@ -1596,9 +1610,6 @@ class Renderer:
                 debug("Q.smooth: " + str(Q.smooth) + "\n")
                 debug("\n")
 
                 debug("Q.smooth: " + str(Q.smooth) + "\n")
                 debug("\n")
 
-                #qSign = 1
-                #if Q.normal[2] < 0:
-                #    qSign = -1
                 qSign = sign(Q.normal[2])
  
                 # We need to test only those Qs whose furthest vertex
                 qSign = sign(Q.normal[2])
  
                 # We need to test only those Qs whose furthest vertex
@@ -1606,9 +1617,9 @@ class Renderer:
 
                 zP = [v.co[2] for v in P.v]
                 zQ = [v.co[2] for v in Q.v]
 
                 zP = [v.co[2] for v in P.v]
                 zQ = [v.co[2] for v in Q.v]
-                ZOverlap = min(zP) < max(zQ)
+                notZOverlap = min(zP) > max(zQ) + EPS
 
 
-                if not ZOverlap:
+                if notZOverlap:
                     debug("\nTest 0\n")
                     debug("NOT Z OVERLAP!\n")
                     if Q.smooth == 0:
                     debug("\nTest 0\n")
                     debug("NOT Z OVERLAP!\n")
                     if Q.smooth == 0:
@@ -1621,7 +1632,8 @@ class Renderer:
                 # Test 1: X extent overlapping
                 xP = [v.co[0] for v in P.v]
                 xQ = [v.co[0] for v in Q.v]
                 # Test 1: X extent overlapping
                 xP = [v.co[0] for v in P.v]
                 xQ = [v.co[0] for v in Q.v]
-                notXOverlap = (max(xP) <= min(xQ)) or (max(xQ) <= min(xP))
+                #notXOverlap = (max(xP) <= min(xQ)) or (max(xQ) <= min(xP))
+                notXOverlap = (min(xQ) >= max(xP)-EPS) or (min(xP) >= max(xQ)-EPS)
 
                 if notXOverlap:
                     debug("\nTest 1\n")
 
                 if notXOverlap:
                     debug("\nTest 1\n")
@@ -1631,7 +1643,8 @@ class Renderer:
                 # Test 2: Y extent Overlapping
                 yP = [v.co[1] for v in P.v]
                 yQ = [v.co[1] for v in Q.v]
                 # Test 2: Y extent Overlapping
                 yP = [v.co[1] for v in P.v]
                 yQ = [v.co[1] for v in Q.v]
-                notYOverlap = (max(yP) <= min(yQ)) or (max(yQ) <= min(yP))
+                #notYOverlap = (max(yP) <= min(yQ)) or (max(yQ) <= min(yP))
+                notYOverlap = (min(yQ) >= max(yP)-EPS) or (min(yP) >= max(yQ)-EPS)
 
                 if notYOverlap:
                     debug("\nTest 2\n")
 
                 if notYOverlap:
                     debug("\nTest 2\n")
@@ -1643,7 +1656,7 @@ class Renderer:
                 n = 0
                 for Pi in P:
                     d = qSign * Distance(Vector(Pi), Q)
                 n = 0
                 for Pi in P:
                     d = qSign * Distance(Vector(Pi), Q)
-                    if d >= -EPS:
+                    if d <= EPS:
                         n += 1
                 pVerticesBehindPlaneQ = (n == len(P))
 
                         n += 1
                 pVerticesBehindPlaneQ = (n == len(P))
 
@@ -1657,7 +1670,7 @@ class Renderer:
                 n = 0
                 for Qi in Q:
                     d = pSign * Distance(Vector(Qi), P)
                 n = 0
                 for Qi in Q:
                     d = pSign * Distance(Vector(Qi), P)
-                    if d <= EPS:
+                    if d >= -EPS:
                         n += 1
                 qVerticesInFrontPlaneP = (n == len(Q))
 
                         n += 1
                 qVerticesInFrontPlaneP = (n == len(Q))
 
@@ -1686,19 +1699,18 @@ class Renderer:
                     # Split P or Q
                     debug("Possibly a cycle detected!\n")
                     debug("Split here!!\n")
                     # Split P or Q
                     debug("Possibly a cycle detected!\n")
                     debug("Split here!!\n")
-                    old_facelist = facelist[:]
+
                     facelist = facesplit(P, Q, facelist, nmesh)
                     split_done = 1
                     break 
 
                     facelist = facesplit(P, Q, facelist, nmesh)
                     split_done = 1
                     break 
 
-
                 # The question now is: Does Q obscure P?
 
                 # Test 3bis: Q vertices are all behind the plane of P
                 n = 0
                 for Qi in Q:
                     d = pSign * Distance(Vector(Qi), P)
                 # The question now is: Does Q obscure P?
 
                 # Test 3bis: Q vertices are all behind the plane of P
                 n = 0
                 for Qi in Q:
                     d = pSign * Distance(Vector(Qi), P)
-                    if d >= -EPS:
+                    if d <= EPS:
                         n += 1
                 qVerticesBehindPlaneP = (n == len(Q))
 
                         n += 1
                 qVerticesBehindPlaneP = (n == len(Q))
 
@@ -1711,7 +1723,7 @@ class Renderer:
                 n = 0
                 for Pi in P:
                     d = qSign * Distance(Vector(Pi), Q)
                 n = 0
                 for Pi in P:
                     d = qSign * Distance(Vector(Pi), Q)
-                    if d <= EPS:
+                    if d >= -EPS:
                         n += 1
                 pVerticesInFrontPlaneQ = (n == len(P))
 
                         n += 1
                 pVerticesInFrontPlaneQ = (n == len(P))
 
@@ -1727,68 +1739,25 @@ class Renderer:
                     debug("Test 3bis or 4bis failed\n")
                     debug("Split here!!2\n")
 
                     debug("Test 3bis or 4bis failed\n")
                     debug("Split here!!2\n")
 
-                    old_facelist = facelist[:]
                     facelist = facesplit(P, Q, facelist, nmesh)
                     facelist = facesplit(P, Q, facelist, nmesh)
-
-                    steps += 1
-                    if steps == 2:
-                        maplist = [P, Q]
-                        print P, Q
                     split_done = 1
                     break 
                     split_done = 1
                     break 
-
                     
                 facelist.remove(Q)
                 facelist.insert(0, Q)
                 Q.smooth = 1
                 face_marked = 1
                     
                 facelist.remove(Q)
                 facelist.insert(0, Q)
                 Q.smooth = 1
                 face_marked = 1
-
-                # Make merked faces BLUE. so to see them
-                #for c in Q.col:
-                #    c.r = 0
-                #    c.g = 0
-                #    c.b = 255
-                #    c.a = 255
-                
                 debug("Q marked!\n")
                 debug("Q marked!\n")
-                print [f.smooth for f in facelist]
                 break
            
             # Write P!                     
             if split_done == 0 and face_marked == 0:
                 break
            
             # Write P!                     
             if split_done == 0 and face_marked == 0:
-                P = facelist[0]
                 facelist.remove(P)
                 maplist.append(P)
 
                 progress.update()
                 facelist.remove(P)
                 maplist.append(P)
 
                 progress.update()
-                #if progress.progressModel.getProgress() == 100:
-                #    break
-            if steps == 2:
-                """
-                for c in Q.col:
-                    c.r = 0
-                    c.g = 0
-                    c.b = 255
-                    c.a = 255
-                for c in P.col:
-                    c.r = 0
-                    c.g = 0
-                    c.b = 255
-                    c.a = 255
-                """
-                print steps
-                #maplist.append(P)
-                #maplist.append(Q)
-
-               # for f in facelist:
-               #     if f not in old_facelist:
-               #         print "splitted?"
-               #         maplist.append(f)
-
-                break
-            """
-            """
 
 
+            # end of while len(facelist)
          
 
         nmesh.faces = maplist
          
 
         nmesh.faces = maplist
@@ -1796,7 +1765,7 @@ class Renderer:
         for f in nmesh.faces:
             f.sel = 1
         nmesh.update()
         for f in nmesh.faces:
             f.sel = 1
         nmesh.update()
-        print nmesh.faces
+        #print nmesh.faces
 
     def _doHiddenSurfaceRemoval(self, mesh):
         """Do HSR for the given mesh.
 
     def _doHiddenSurfaceRemoval(self, mesh):
         """Do HSR for the given mesh.