projects / vrm.git / blobdiff
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Fixes to Newell algorithm implementation
[vrm.git] / vrm.py
diff --git a/vrm.py b/vrm.py
index bc44cfd..82922f8 100755 (executable)
--- a/vrm.py
+++ b/vrm.py
@@ -92,8 +92,8 @@ class config:
     polygons = dict()
     polygons['SHOW'] = True
     polygons['SHADING'] = 'FLAT'
     polygons = dict()
     polygons['SHOW'] = True
     polygons['SHADING'] = 'FLAT'
-    polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'
-    #polygons['HSR'] = 'NEWELL'
+    #polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'
+    polygons['HSR'] = 'NEWELL'
     # Hidden to the user for now
     polygons['EXPANSION_TRICK'] = True
 
     # Hidden to the user for now
     polygons['EXPANSION_TRICK'] = True
 
@@ -113,12 +113,20 @@ class config:
 
 
 
 
 
 
-# Debug utility function
-print_debug = False
+# Utility functions
+print_debug = True
 def debug(msg):
     if print_debug:
         sys.stderr.write(msg)
 
 def debug(msg):
     if print_debug:
         sys.stderr.write(msg)
 
+def sign(x):
+    if x == 0:
+        return 0
+    elif x < 0:
+        return -1
+    else:
+        return 1
+
 
 # ---------------------------------------------------------------------
 #
 
 # ---------------------------------------------------------------------
 #
@@ -436,8 +444,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 +470,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 +819,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 +1019,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':
@@ -1015,6 +1033,13 @@ class Renderer:
             self._doModelingTransformation(mesh, obj.matrix)
 
             self._doBackFaceCulling(mesh)
             self._doModelingTransformation(mesh, obj.matrix)
 
             self._doBackFaceCulling(mesh)
+            if True:
+                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)
 
@@ -1134,7 +1159,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 +1322,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,26 +1481,55 @@ 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 Distance(point, face):
-            """ Calculate the distance between a point and a face.
+        mesh.quadToTriangle(0)
 
 
-            An alternative but more expensive method can be:
+        from split import Distance, isOnSegment
 
 
-                ip = Intersect(Vector(face[0]), Vector(face[1]), Vector(face[2]),
-                        Vector(face.no), Vector(point), 0)
+        def projectionsOverlap(P, Q):
 
 
-                d = Vector(ip - point).length
-            """
+            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-7
+
+                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], True) and isOnSegment(v3, v4, ret[1], True):
 
 
-            plNormal = Vector(face.no)
-            plVert0 = Vector(face[0])
 
 
-            #d = abs( (point * plNormal ) - (plVert0 * plNormal) )
-            d = (point * plNormal ) - (plVert0 * plNormal)
-            debug("d: "+ str(d) + "\n")
+                        l1 = (ret[0] - v1).length
+                        l2 = (ret[0] - v2).length
 
 
-            return d
+                        l3 = (ret[1] - v3).length
+                        l4 = (ret[1] - v4).length
 
 
+                        if  (l1 < EPS or l2 < EPS) and (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
 
         # 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)
@@ -1493,17 +1548,47 @@ class Renderer:
         facelist = nmesh.faces[:]
         maplist = []
 
         facelist = nmesh.faces[:]
         maplist = []
 
-        EPS = 10e-7
+        EPS = 10e-8
+        #EPS = 0
 
         global progress
 
         global progress
+        # The steps are _at_least_ equal to len(facelist), we do not count the
+        # feces coming out from plitting!!
         progress.setActivity("HSR: Newell", len(facelist))
         progress.setActivity("HSR: Newell", len(facelist))
+        progress.setQuiet(True)
+
+        
+        steps = -1
+        split_done = 0
+        marked_face = 0
 
         while len(facelist):
 
         while len(facelist):
+            print "\n----------------------"
             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])
+
+            # We can discard faces thar are perpendicular to the view
+            if pSign == 0:
+                facelist.remove(P)
+                continue
+
 
 
-            pSign = 1
-            if P.sel == 0:
-                pSign = -1
+            split_done = 0
+            face_marked = 0
 
             for Q in facelist[1:]:
 
 
             for Q in facelist[1:]:
 
@@ -1511,10 +1596,11 @@ class Renderer:
                 debug("Q.smooth: " + str(Q.smooth) + "\n")
                 debug("\n")
 
                 debug("Q.smooth: " + str(Q.smooth) + "\n")
                 debug("\n")
 
-                qSign = 1
-                if Q.sel == 0:
-                    qSign = -1
-
+                #qSign = 1
+                #if Q.normal[2] < 0:
+                #    qSign = -1
+                qSign = sign(Q.normal[2])
+ 
                 # 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,26 +1609,33 @@ class Renderer:
                 ZOverlap = min(zP) < max(zQ)
 
                 if not ZOverlap:
                 ZOverlap = min(zP) < max(zQ)
 
                 if not ZOverlap:
-                    if not Q.smooth:
-                        # We can safely print P
+                    debug("\nTest 0\n")
+                    debug("NOT Z OVERLAP!\n")
+                    if Q.smooth == 0:
+                        # If Q is not marked then we can safely print P
                         break
                     else:
                         break
                     else:
+                        debug("met a marked face\n")
                         continue
                 
                 # Test 1: X extent overlapping
                 xP = [v.co[0] for v in P.v]
                 xQ = [v.co[0] for v in Q.v]
                         continue
                 
                 # 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))
 
                 if notXOverlap:
 
                 if notXOverlap:
+                    debug("\nTest 1\n")
+                    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]
                     continue
 
                 # 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))
 
                 if notYOverlap:
 
                 if notYOverlap:
+                    debug("\nTest 2\n")
+                    debug("NOT Y OVERLAP!\n")
                     continue
                 
 
                     continue
                 
 
@@ -1550,7 +1643,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))
 
@@ -1564,7 +1657,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))
 
@@ -1574,13 +1667,29 @@ 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 done before.
+                # Since we We are working in normalized projection coordinates
+                # we kust check if polygons intersect.
+
+                if not projectionsOverlap(P, Q):
+                    debug("\nTest 5\n")
+                    debug("Projections do not overlap!\n")
+                    continue
 
 
 
 
-                # We do not know 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
+                # difficulty (maybe a visibility cycle).
                 if Q.smooth == 1:
                 if Q.smooth == 1:
-                    # Split P or Q, TODO
+                    # Split P or Q
+                    debug("Possibly a cycle detected!\n")
                     debug("Split here!!\n")
                     debug("Split here!!\n")
-                    continue
+                    old_facelist = facelist[:]
+                    facelist = facesplit(P, Q, facelist, nmesh)
+                    split_done = 1
+                    break 
 
 
                 # The question now is: Does Q obscure P?
 
 
                 # The question now is: Does Q obscure P?
@@ -1589,67 +1698,105 @@ 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
                 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:
                     d = qSign * Distance(Vector(Pi), Q)
 
                 # Test 4bis: P vertices in front of the plane of 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))
 
+                if pVerticesInFrontPlaneQ:
+                    debug("\nTest 4bis\n")
+                    debug("P IN FRONT OF Q!\n")
 
 
-                """
-                import intersection
-
+                
+                # We don't even know if Q does obscure P, so they should
+                # intersect each other, split one of them in two parts.
                 if not qVerticesBehindPlaneP and not pVerticesInFrontPlaneQ:
                 if not qVerticesBehindPlaneP and not pVerticesInFrontPlaneQ:
-                    # Split P or Q, TODO
-                    print "Test 3bis or 4bis failed"
-                    print "Split here!!2\n"
-
-                    newfaces = intersection.splitOn(nmesh, P, Q, 0)
-                    facelist.remove(Q)
-                    for nf in newfaces:
-                        if nf:
-                            nf.col = Q.col
-                            facelist.append(nf)
-
-                    break
-
-                # We do not know
-                if Q.smooth:
-                    # split P or Q
-                    print "Split here!!\n"
-                    newfaces = intersection.splitOn(nmesh, P, Q, 0)
-                    facelist.remove(Q)
-                    for nf in newfaces:
-                        if nf:
-                            nf.col = Q.col
-                            facelist.append(nf)
-
-                    break
-                """ 
+                    debug("\nSimple Intersection?\n")
+                    debug("Test 3bis or 4bis failed\n")
+                    debug("Split here!!2\n")
 
 
-                Q.smooth = 1
+                    old_facelist = facelist[:]
+                    facelist = facesplit(P, Q, facelist, nmesh)
+
+                    steps += 1
+                    if steps == 2:
+                        maplist = [P, Q]
+                        print P, Q
+                    split_done = 1
+                    break 
+
+                    
                 facelist.remove(Q)
                 facelist.insert(0, Q)
                 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")
+                print [f.smooth for f in facelist]
+                break
            
             # Write P!                     
            
             # Write P!                     
-            facelist.remove(P)
-            maplist.append(P)
+            if split_done == 0 and face_marked == 0:
+                P = facelist[0]
+                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)
 
 
-            progress.update()
+               # for f in facelist:
+               #     if f not in old_facelist:
+               #         print "splitted?"
+               #         maplist.append(f)
+
+                break
+            """
+            """
+
+         
 
 
-        
         nmesh.faces = maplist
 
         for f in nmesh.faces:
             f.sel = 1
         nmesh.update()
         nmesh.faces = maplist
 
         for f in nmesh.faces:
             f.sel = 1
         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.
@@ -1658,11 +1805,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)
 
 
VRM: A vector rendering script for Blender