Cleanup Newell's algorithm implementation

Signed-off-by: Antonio Ospite <ospite@studenti.unina.it>

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.