Cleanup Newell's algorithm implementation
authorAntonio Ospite <ospite@studenti.unina.it>
Wed, 17 Jan 2007 22:34:39 +0000 (23:34 +0100)
committerAntonio Ospite <ospite@studenti.unina.it>
Thu, 24 Sep 2009 16:51:47 +0000 (18:51 +0200)
Signed-off-by: Antonio Ospite <ospite@studenti.unina.it>
vrm.py

diff --git a/vrm.py b/vrm.py
index 7cf79bc..5e2c128 100755 (executable)
--- a/vrm.py
+++ b/vrm.py
@@ -85,13 +85,16 @@ from Blender.Mathutils import *
 from math import *
 import sys, time
 
 from math import *
 import sys, time
 
+# Constants
+EPS = 10e-5
+
 
 # Some global settings
 
 class config:
     polygons = dict()
     polygons['SHOW'] = True
 
 # Some global settings
 
 class config:
     polygons = dict()
     polygons['SHOW'] = True
-    polygons['SHADING'] = 'FLAT'
+    polygons['SHADING'] = 'TOON'
     #polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'
     polygons['HSR'] = 'NEWELL'
     # Hidden to the user for now
     #polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'
     polygons['HSR'] = 'NEWELL'
     # Hidden to the user for now
@@ -102,7 +105,7 @@ class config:
     edges = dict()
     edges['SHOW'] = False
     edges['SHOW_HIDDEN'] = False
     edges = dict()
     edges['SHOW'] = False
     edges['SHOW_HIDDEN'] = False
-    edges['STYLE'] = 'MESH'
+    edges['STYLE'] = 'MESH' # or SILHOUETTE
     edges['WIDTH'] = 2
     edges['COLOR'] = [0, 0, 0]
 
     edges['WIDTH'] = 2
     edges['COLOR'] = [0, 0, 0]
 
@@ -114,20 +117,14 @@ class config:
 
 
 # Utility functions
 
 
 # Utility functions
-print_debug = False
-def debug(msg):
-    if print_debug:
-        sys.stderr.write(msg)
-
-EPS = 10e-5
-
 def sign(x):
 def sign(x):
-    if x < -EPS:
+
+    if x < 0:
         return -1
         return -1
-    elif x > EPS:
+    elif x > 0:
         return 1
         return 1
-    else:
-        return 0
+    #else:
+    #    return 0
 
 
 # ---------------------------------------------------------------------
 
 
 # ---------------------------------------------------------------------
@@ -810,8 +807,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 = "opacity: %g;" % (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)
@@ -1034,6 +1031,10 @@ class Renderer:
 
             mesh = obj.getData(mesh=1)
 
 
             mesh = obj.getData(mesh=1)
 
+            # Triangolarize the mesh??
+            for f in mesh.faces: f.sel = 1
+            mesh.quadToTriangle()
+
             self._doModelingTransformation(mesh, obj.matrix)
 
             self._doBackFaceCulling(mesh)
             self._doModelingTransformation(mesh, obj.matrix)
 
             self._doBackFaceCulling(mesh)
@@ -1356,7 +1357,7 @@ class Renderer:
             for l in self.lights:
                 light_obj = l
                 light_pos = self._getObjPosition(l)
             for l in self.lights:
                 light_obj = l
                 light_pos = self._getObjPosition(l)
-                light = light_obj.data
+                light = light_obj.getData()
             
                 L = Vector(light_pos).normalize()
 
             
                 L = Vector(light_pos).normalize()
 
@@ -1457,7 +1458,6 @@ class Renderer:
         # The sorting requires circa n*log(n) steps
         n = len(mesh.faces)
         progress.setActivity("HSR: Painter", n*log(n))
         # The sorting requires circa n*log(n) steps
         n = len(mesh.faces)
         progress.setActivity("HSR: Painter", n*log(n))
-        
 
         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])+EPS)
 
         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])+EPS)
@@ -1472,92 +1472,24 @@ class Renderer:
 
         nmesh.update()
 
 
         nmesh.update()
 
-    def __topologicalDepthSort(self, mesh):
-        """Occlusion based on topological occlusion.
-        
-        Build the occlusion graph of the mesh,
-        and then do topological sort on that graph
-        """
-        return
-
     def __newellDepthSort(self, mesh):
         """Newell's depth sorting.
 
         """
     def __newellDepthSort(self, mesh):
         """Newell's depth sorting.
 
         """
-        global EPS
-
-        by_furthest_z = (lambda f1, f2:
-                cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2])+EPS)
-                )
-
-        mesh.quadToTriangle()
-
-        from split import Distance, isOnSegment
-
-        def projectionsOverlap(P, Q):
-
-            for i in range(0, len(P.v)):
-
-                v1 = Vector(P.v[i-1])
-                v1[2] = 0
-                v2 = Vector(P.v[i])
-                v2[2] = 0
-
-                EPS = 10e-5
-
-                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
-
-                    #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)
-
-                    # 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):
-
-                        #l1 = (ret[0] - v1).length
-                        #l2 = (ret[0] - v2).length
+        from hsrtk import *
 
 
-                        #l3 = (ret[1] - v3).length
-                        #l4 = (ret[1] - v4).length
+        # Find non planar quads and convert them to triangle
+        #for f in mesh.faces:
+        #    f.sel = 0
+        #    if is_nonplanar_quad(f.v):
+        #        print "NON QUAD??"
+        #        f.sel = 1
 
 
-                        #print "New DISTACES againt the intersection point:"
-                        #print l1, l2, l3, l4
-                        #print "-----------------------\n"
 
 
-                        #if  l1 < EPS or l2 < EPS or l3 < EPS or l4 < EPS:
-                        #    continue
-
-                        debug("Projections OVERLAP!!\n")
-                        debug("line1:"+
-                                " M "+ str(v1[0])+','+str(v1[1]) + ' L ' + str(v2[0])+','+str(v2[1]) + '\n' +
-                                " M "+ str(v3[0])+','+str(v3[1]) + ' L ' + str(v4[0])+','+str(v4[1]) + '\n' +
-                                "\n")
-                        debug("return: "+ str(ret)+"\n")
-                        return True
-
-            return False
-
-
-        from facesplit import facesplit
+        # Now reselect all faces
+        for f in mesh.faces:
+            f.sel = 1
 
         # FIXME: using NMesh to sort faces. We should avoid that!
         nmesh = NMesh.GetRaw(mesh.name)
 
         # FIXME: using NMesh to sort faces. We should avoid that!
         nmesh = NMesh.GetRaw(mesh.name)
@@ -1576,19 +1508,14 @@ class Renderer:
         facelist = nmesh.faces[:]
         maplist = []
 
         facelist = nmesh.faces[:]
         maplist = []
 
-        EPS = 10e-5
-
-        global progress
 
         # The steps are _at_least_ equal to len(facelist), we do not count the
         # feces coming out from splitting!!
 
         # The steps are _at_least_ equal to len(facelist), we do not count the
         # feces coming out from splitting!!
+        global progress
         progress.setActivity("HSR: Newell", len(facelist))
         #progress.setQuiet(True)
 
         
         progress.setActivity("HSR: Newell", len(facelist))
         #progress.setQuiet(True)
 
         
-        #split_done = 0
-        #marked_face = 0
-
         while len(facelist):
             debug("\n----------------------\n")
             debug("len(facelits): %d\n" % len(facelist))
         while len(facelist):
             debug("\n----------------------\n")
             debug("len(facelits): %d\n" % len(facelist))
@@ -1597,7 +1524,7 @@ class Renderer:
             pSign = sign(P.normal[2])
 
             # We can discard faces parallel to the view vector
             pSign = sign(P.normal[2])
 
             # We can discard faces parallel to the view vector
-            if pSign == 0:
+            if P.normal[2] == 0:
                 facelist.remove(P)
                 continue
 
                 facelist.remove(P)
                 continue
 
@@ -1611,13 +1538,14 @@ class Renderer:
                 debug("\n")
 
                 qSign = sign(Q.normal[2])
                 debug("\n")
 
                 qSign = sign(Q.normal[2])
+                # TODO: check also if Q is parallel??
  
  
-                # We need to test only those Qs whose furthest vertex
+                # Test 0: We need to test only those Qs whose furthest vertex
                 # is closer to the observer than the closest vertex of P.
 
                 zP = [v.co[2] for v in P.v]
                 zQ = [v.co[2] for v in Q.v]
                 # is closer to the observer than the closest vertex of P.
 
                 zP = [v.co[2] for v in P.v]
                 zQ = [v.co[2] for v in Q.v]
-                notZOverlap = min(zP) > max(zQ) + EPS
+                notZOverlap = min(zP) > max(zQ)+EPS
 
                 if notZOverlap:
                     debug("\nTest 0\n")
 
                 if notZOverlap:
                     debug("\nTest 0\n")
@@ -1628,6 +1556,7 @@ class Renderer:
                     else:
                         debug("met a marked face\n")
                         continue
                     else:
                         debug("met a marked face\n")
                         continue
+
                 
                 # Test 1: X extent overlapping
                 xP = [v.co[0] for v in P.v]
                 
                 # Test 1: X extent overlapping
                 xP = [v.co[0] for v in P.v]
@@ -1640,6 +1569,7 @@ class Renderer:
                     debug("NOT X OVERLAP!\n")
                     continue
 
                     debug("NOT X OVERLAP!\n")
                     continue
 
+
                 # 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]
@@ -1679,21 +1609,18 @@ class Renderer:
                     debug("Q IN FRONT OF P!\n")
                     continue
 
                     debug("Q IN FRONT OF P!\n")
                     continue
 
-                # Test 5: Line Intersections... TODO
-                # Check if polygons effectively overlap each other, not only
-                # boundig boxes as done before.
-                # Since we We are working in normalized projection coordinates
-                # we kust check if polygons intersect.
+
+                # Test 5: Check if projections of polygons effectively overlap,
+                # in previous tests we checked only bounding boxes.
 
                 if not projectionsOverlap(P, Q):
                     debug("\nTest 5\n")
                     debug("Projections do not overlap!\n")
                     continue
 
 
                 if not projectionsOverlap(P, Q):
                     debug("\nTest 5\n")
                     debug("Projections do not overlap!\n")
                     continue
 
+                # We still can't say if P obscures Q.
 
 
-                # We still do not know if P obscures Q.
-
-                # But if Q is marked we do a split trying to resolve a
+                # But if Q is marked we do a face-split trying to resolve a
                 # difficulty (maybe a visibility cycle).
                 if Q.smooth == 1:
                     # Split P or Q
                 # difficulty (maybe a visibility cycle).
                 if Q.smooth == 1:
                     # Split P or Q
@@ -1706,6 +1633,7 @@ class Renderer:
 
                 # The question now is: Does Q obscure 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:
                 # Test 3bis: Q vertices are all behind the plane of P
                 n = 0
                 for Qi in Q:
@@ -1757,15 +1685,19 @@ class Renderer:
 
                 progress.update()
 
 
                 progress.update()
 
+            if facelist == None:
+                maplist = [P, Q]
+                print [v.co for v in P]
+                print [v.co for v in Q]
+                break
+
             # end of while len(facelist)
          
 
         nmesh.faces = maplist
 
             # end of while len(facelist)
          
 
         nmesh.faces = maplist
 
-        for f in nmesh.faces:
-            f.sel = 1
         nmesh.update()
         nmesh.update()
-        #print nmesh.faces
+
 
     def _doHiddenSurfaceRemoval(self, mesh):
         """Do HSR for the given mesh.
 
     def _doHiddenSurfaceRemoval(self, mesh):
         """Do HSR for the given mesh.