From 6522c892513097a6f9da53d64b5c38cf8d417c31 Mon Sep 17 00:00:00 2001 From: Antonio Ospite Date: Wed, 17 Jan 2007 23:34:39 +0100 Subject: [PATCH] Cleanup Newell's algorithm implementation Signed-off-by: Antonio Ospite --- vrm.py | 162 +++++++++++++++++++---------------------------------------------- 1 file changed, 47 insertions(+), 115 deletions(-) diff --git a/vrm.py b/vrm.py index 7cf79bc..5e2c128 100755 --- a/vrm.py +++ b/vrm.py @@ -85,13 +85,16 @@ from Blender.Mathutils import * from math import * import sys, time +# Constants +EPS = 10e-5 + # 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 @@ -102,7 +105,7 @@ class config: 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] @@ -114,20 +117,14 @@ class config: # Utility functions -print_debug = False -def debug(msg): - if print_debug: - sys.stderr.write(msg) - -EPS = 10e-5 - def sign(x): - if x < -EPS: + + if x < 0: return -1 - elif x > EPS: + elif x > 0: 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 = " 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) @@ -1034,6 +1031,10 @@ class Renderer: 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) @@ -1356,7 +1357,7 @@ class Renderer: 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() @@ -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)) - 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() - 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. """ - 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) @@ -1576,19 +1508,14 @@ class Renderer: 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!! + global progress 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)) @@ -1597,7 +1524,7 @@ class Renderer: 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 @@ -1611,13 +1538,14 @@ class Renderer: 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] - notZOverlap = min(zP) > max(zQ) + EPS + notZOverlap = min(zP) > max(zQ)+EPS if notZOverlap: debug("\nTest 0\n") @@ -1628,6 +1556,7 @@ class Renderer: else: debug("met a marked face\n") continue + # 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 + # 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 - # 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 + # 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 @@ -1706,6 +1633,7 @@ class Renderer: # 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: @@ -1757,15 +1685,19 @@ class Renderer: 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 - for f in nmesh.faces: - f.sel = 1 nmesh.update() - #print nmesh.faces + def _doHiddenSurfaceRemoval(self, mesh): """Do HSR for the given mesh. -- 2.1.4