Add test 5 of Newell algorithm

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

diff --git a/vrm.py b/vrm.py
index bc44cfd..9095307 100755 (executable)
--- a/vrm.py
+++ b/vrm.py
@@ -93,7 +93,7 @@ class config:
     polygons['SHOW'] = True
     polygons['SHADING'] = 'FLAT'
     polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'
     polygons['SHOW'] = True
     polygons['SHADING'] = 'FLAT'
     polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'

-    #polygons['HSR'] = 'NEWELL'
+    polygons['HSR'] = 'NEWELL'

     # Hidden to the user for now
     polygons['EXPANSION_TRICK'] = True
 
     # Hidden to the user for now
     polygons['EXPANSION_TRICK'] = True
 


@@ -114,7 +114,7 @@ class config:
 
 
 # Debug utility function
 
 
 # Debug utility function

-print_debug = False
+print_debug = True

 def debug(msg):
     if print_debug:
         sys.stderr.write(msg)
 def debug(msg):
     if print_debug:
         sys.stderr.write(msg)


@@ -436,8 +436,13 @@ class ProgressIndicator:
         self.refresh_rate = 10
         self.shows_counter = 0
 
         self.refresh_rate = 10
         self.shows_counter = 0
 

+        self.quiet = False
+

         self.progressModel = None
 
         self.progressModel = None
 

+    def setQuiet(self, value):
+        self.quiet = value
+

     def setActivity(self, name, steps):
         """Initialize the Model.
 
     def setActivity(self, name, steps):
         """Initialize the Model.
 


@@ -457,6 +462,9 @@ class ProgressIndicator:
         assert(self.progressModel)
 
         if self.progressModel.update():
         assert(self.progressModel)
 
         if self.progressModel.update():

+            if self.quiet:
+                return
+

             self.show(self.progressModel.getProgress(),
                     self.progressModel.getName())
 
             self.show(self.progressModel.getProgress(),
                     self.progressModel.getName())
 


@@ -803,6 +811,7 @@ class SVGVectorWriter(VectorWriter):
             stroke_width = 1.0
 
             if config.polygons['EXPANSION_TRICK']:
             stroke_width = 1.0
 
             if config.polygons['EXPANSION_TRICK']:

+                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")


@@ -1002,6 +1011,7 @@ class Renderer:
         Objects = workScene.getChildren()
         print "Total Objects: %d" % len(Objects)
         for i,obj in enumerate(Objects):
         Objects = workScene.getChildren()
         print "Total Objects: %d" % len(Objects)
         for i,obj in enumerate(Objects):

+            print "\n\n-------"

             print "Rendering Object: %d" % i
 
             if obj.getType() != 'Mesh':
             print "Rendering Object: %d" % i
 
             if obj.getType() != 'Mesh':


@@ -1134,7 +1144,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', '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 ]


@@ -1296,26 +1307,26 @@ class Renderer:
             mat = None
             if materials:
                 mat = materials[f.mat]
             mat = None
             if materials:
                 mat = materials[f.mat]

-                # Check if it is a shadeless material
-                if mat.getMode() & Material.Modes['SHADELESS']:
-                    I = mat.getRGBCol()
-                    # Convert to a value between 0 and 255
-                    tmp_col = [ int(c * 255.0) for c in I]
-
-                    for c in f.col:
-                        c.r = tmp_col[0]
-                        c.g = tmp_col[1]
-                        c.b = tmp_col[2]
-                        #c.a = tmp_col[3]
-
-                    continue
-
-

 
             # A new default material
             if mat == None:
                 mat = Material.New('defMat')
 
 
             # A new default material
             if mat == None:
                 mat = Material.New('defMat')
 

+            # Check if it is a shadeless material
+            elif mat.getMode() & Material.Modes['SHADELESS']:
+                I = mat.getRGBCol()
+                # Convert to a value between 0 and 255
+                tmp_col = [ int(c * 255.0) for c in I]
+
+                for c in f.col:
+                    c.r = tmp_col[0]
+                    c.g = tmp_col[1]
+                    c.b = tmp_col[2]
+                    #c.a = tmp_col[3]
+
+                continue
+
+

             # do vertex color calculation
 
             TotDiffSpec = Vector([0.0, 0.0, 0.0])
             # do vertex color calculation
 
             TotDiffSpec = Vector([0.0, 0.0, 0.0])


@@ -1455,6 +1466,29 @@ class Renderer:
                 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]))
                 )
 

+
+        def isOnSegment(v1, v2, p):
+
+            # when p is at extreme points
+            if p == v1 or p == v2:
+                return False
+
+
+            EPS = 10e-7
+
+            l1 = (v1-p).length
+            l2 = (v2-p).length
+            l = (v1-v2).length
+
+            print "l: ", l, " l1: ", l1, " l2: ", l2, "diff: %.9f" % (l - (l1+l2) )
+
+            if abs(l - (l1+l2)) < EPS:
+                return True
+            else:
+                return False
+
+
+

         def Distance(point, face):
             """ Calculate the distance between a point and a face.
 
         def Distance(point, face):
             """ Calculate the distance between a point and a face.
 


@@ -1471,7 +1505,7 @@ class Renderer:
 
             #d = abs( (point * plNormal ) - (plVert0 * plNormal) )
             d = (point * plNormal ) - (plVert0 * plNormal)
 
             #d = abs( (point * plNormal ) - (plVert0 * plNormal) )
             d = (point * plNormal ) - (plVert0 * plNormal)

-            debug("d: "+ str(d) + "\n")
+            debug("d: %.10f - sel: %d, %s\n" % (d, face.sel, str(point)) )

 
             return d
 
 
             return d
 


@@ -1493,11 +1527,14 @@ class Renderer:
         facelist = nmesh.faces[:]
         maplist = []
 
         facelist = nmesh.faces[:]
         maplist = []
 

-        EPS = 10e-7
+        #EPS = 10e-7
+        EPS = 0

 
         global progress
         progress.setActivity("HSR: Newell", len(facelist))
 
         global progress
         progress.setActivity("HSR: Newell", len(facelist))

+        progress.setQuiet(True)

 
 

+        #while len(facelist)-1:

         while len(facelist):
             P = facelist[0]
 
         while len(facelist):
             P = facelist[0]
 


@@ -1505,6 +1542,7 @@ class Renderer:
             if P.sel == 0:
                 pSign = -1
 
             if P.sel == 0:
                 pSign = -1
 

+            #while False:

             for Q in facelist[1:]:
 
                 debug("P.smooth: " + str(P.smooth) + "\n")
             for Q in facelist[1:]:
 
                 debug("P.smooth: " + str(P.smooth) + "\n")


@@ -1514,7 +1552,7 @@ class Renderer:
                 qSign = 1
                 if Q.sel == 0:
                     qSign = -1
                 qSign = 1
                 if Q.sel == 0:
                     qSign = -1

-
+ 

                 # We need to test only those Qs whose furthest vertex
                 # is closer to the observer than the closest vertex of P.
 
                 # We need to test only those Qs whose furthest vertex
                 # is closer to the observer than the closest vertex of P.
 


@@ -1523,6 +1561,8 @@ class Renderer:
                 ZOverlap = min(zP) < max(zQ)
 
                 if not ZOverlap:
                 ZOverlap = min(zP) < max(zQ)
 
                 if not ZOverlap:

+                    debug("\nTest 0\n")
+                    debug("NOT Z OVERLAP!\n")

                     if not Q.smooth:
                         # We can safely print P
                         break
                     if not Q.smooth:
                         # We can safely print P
                         break


@@ -1535,6 +1575,8 @@ class Renderer:
                 notXOverlap = (max(xP) < min(xQ)) or (max(xQ) < min(xP))
 
                 if notXOverlap:
                 notXOverlap = (max(xP) < min(xQ)) or (max(xQ) < min(xP))
 
                 if notXOverlap:

+                    debug("\nTest 1\n")
+                    debug("NOT X OVERLAP!\n")

                     continue
 
                 # Test 2: Y extent Overlapping
                     continue
 
                 # Test 2: Y extent Overlapping


@@ -1543,14 +1585,17 @@ class Renderer:
                 notYOverlap = (max(yP) < min(yQ)) or (max(yQ) < min(yP))
 
                 if notYOverlap:
                 notYOverlap = (max(yP) < min(yQ)) or (max(yQ) < min(yP))
 
                 if notYOverlap:

+                    debug("\nTest 2\n")
+                    debug("NOT Y OVERLAP!\n")

                     continue
                 
 
                 # Test 3: P vertices are all behind the plane of Q
                 n = 0
                 for Pi in P:
                     continue
                 
 
                 # Test 3: P vertices are all behind the plane of Q
                 n = 0
                 for Pi in P:

+                    print P.col[0]

                     d = qSign * Distance(Vector(Pi), Q)
                     d = qSign * Distance(Vector(Pi), Q)

-                    if d < EPS:
+                    if d > EPS:

                         n += 1
                 pVerticesBehindPlaneQ = (n == len(P))
 
                         n += 1
                 pVerticesBehindPlaneQ = (n == len(P))
 


@@ -1563,8 +1608,9 @@ class Renderer:
                 # Test 4: Q vertices in front of the plane of P
                 n = 0
                 for Qi in Q:
                 # Test 4: Q vertices in front of the plane of P
                 n = 0
                 for Qi in Q:

+                    print Q.col[0]

                     d = pSign * Distance(Vector(Qi), P)
                     d = pSign * Distance(Vector(Qi), P)

-                    if d >= EPS:
+                    if d <= EPS:

                         n += 1
                 qVerticesInFrontPlaneP = (n == len(Q))
 
                         n += 1
                 qVerticesInFrontPlaneP = (n == len(Q))
 


@@ -1574,11 +1620,51 @@ class Renderer:
                     continue
 
                 # Test 5: Line Intersections... TODO
                     continue
 
                 # Test 5: Line Intersections... TODO

+                # Check if polygons effectively overlap each other, not only
+                # boundig boxes as dome before.
+                # Since we We are working in normalized projection coordinates
+                # we kust check if polygons intersect.
+
+                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
+
+                        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
+                            
+                            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]) and isOnSegment(v3, v4, ret[1]):
+                                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
+
+                if not projectionsOverlap(P, Q):
+                    debug("\nTest 5\n")
+                    debug("Projections do not overlap!\n")
+                    continue

 
 
                 # We do not know if P obscures Q.
                 if Q.smooth == 1:
                     # Split P or Q, TODO
 
 
                 # We do not know if P obscures Q.
                 if Q.smooth == 1:
                     # Split P or Q, TODO

+                    debug("Cycle detected!\n")

                     debug("Split here!!\n")
                     continue
 
                     debug("Split here!!\n")
                     continue
 


@@ -1588,35 +1674,47 @@ class Renderer:
                 # 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:

+                    print Q.col[0]

                     d = pSign * Distance(Vector(Qi), P)
                     d = pSign * Distance(Vector(Qi), P)

-                    if d < EPS:
+                    if d > EPS:

                         n += 1
                 qVerticesBehindPlaneP = (n == len(Q))
 
                         n += 1
                 qVerticesBehindPlaneP = (n == len(Q))
 

+                if qVerticesBehindPlaneP:
+                    debug("\nTest 3bis\n")
+                    debug("Q BEHIND P!\n")
+

 
                 # Test 4bis: P vertices in front of the plane of Q
                 n = 0
                 for Pi in P:
 
                 # Test 4bis: P vertices in front of the plane of Q
                 n = 0
                 for Pi in P:

+                    print P.col[0]

                     d = qSign * Distance(Vector(Pi), Q)
                     d = qSign * Distance(Vector(Pi), Q)

-                    if d >= EPS:
+                    if d <= EPS:

                         n += 1
                 pVerticesInFrontPlaneQ = (n == len(P))
 
                         n += 1
                 pVerticesInFrontPlaneQ = (n == len(P))
 

+                if pVerticesInFrontPlaneQ:
+                    debug("\nTest 4bis\n")
+                    debug("P IN FRONT OF Q!\n")
+

 
 

-                """

                 import intersection
 
                 if not qVerticesBehindPlaneP and not pVerticesInFrontPlaneQ:
                 import intersection
 
                 if not qVerticesBehindPlaneP and not pVerticesInFrontPlaneQ:

+                    debug("\nSimple Intersection?\n")

                     # Split P or Q, TODO
                     print "Test 3bis or 4bis failed"
                     print "Split here!!2\n"
 
                     # Split P or Q, TODO
                     print "Test 3bis or 4bis failed"
                     print "Split here!!2\n"
 

-                    newfaces = intersection.splitOn(nmesh, P, Q, 0)
+                    """newfaces = intersection.splitOn(P, Q, 0)
+                    print newfaces

                     facelist.remove(Q)
                     for nf in newfaces:
                         if nf:
                             nf.col = Q.col
                             facelist.append(nf)
                     facelist.remove(Q)
                     for nf in newfaces:
                         if nf:
                             nf.col = Q.col
                             facelist.append(nf)

+                    """

 
                     break
 
 
                     break
 


@@ -1624,25 +1722,27 @@ class Renderer:
                 if Q.smooth:
                     # split P or Q
                     print "Split here!!\n"
                 if Q.smooth:
                     # split P or Q
                     print "Split here!!\n"

-                    newfaces = intersection.splitOn(nmesh, P, Q, 0)
+                    """
+                    newfaces = intersection.splitOn(P, Q, 0)

                     facelist.remove(Q)
                     for nf in newfaces:
                         if nf:
                             nf.col = Q.col
                             facelist.append(nf)
 
                     facelist.remove(Q)
                     for nf in newfaces:
                         if nf:
                             nf.col = Q.col
                             facelist.append(nf)
 

+                    """ 

                     break
                     break

-                """ 

 
                 Q.smooth = 1
                 facelist.remove(Q)
                 facelist.insert(0, Q)
            
             # Write P!                     
 
                 Q.smooth = 1
                 facelist.remove(Q)
                 facelist.insert(0, Q)
            
             # Write P!                     

+            P = facelist[0]

             facelist.remove(P)
             maplist.append(P)
 
             facelist.remove(P)
             maplist.append(P)
 

-            progress.update()
+            progress .update()

 
         
         nmesh.faces = maplist
 
         
         nmesh.faces = maplist


@@ -1658,11 +1758,11 @@ class Renderer:
             return
 
         if config.polygons['HSR'] == 'PAINTER':
             return
 
         if config.polygons['HSR'] == 'PAINTER':

-            print "\n\nUsing the Painter algorithm for HSR.\n"
+            print "\nUsing the Painter algorithm for HSR."

             self.__simpleDepthSort(mesh)
 
         elif config.polygons['HSR'] == 'NEWELL':
             self.__simpleDepthSort(mesh)
 
         elif config.polygons['HSR'] == 'NEWELL':

-            print "\n\nUsing the Newell's algorithm for HSR.\n"
+            print "\nUsing the Newell's algorithm for HSR."

             self.__newellDepthSort(mesh)
 
 
             self.__newellDepthSort(mesh)