X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=blender%2Fio_mspgl%2Fmesh.py;h=c3767bd9f18884718941977115da2d66f3a1a756;hb=e55b081c9b9927168530fdf7fafcae5aed295569;hp=b58637b7f76bb00515c82f29d211c7a380d51395;hpb=7370746bcad955eb813418d0e1d5686f22c99369;p=libs%2Fgl.git diff --git a/blender/io_mspgl/mesh.py b/blender/io_mspgl/mesh.py index b58637b7..c3767bd9 100644 --- a/blender/io_mspgl/mesh.py +++ b/blender/io_mspgl/mesh.py @@ -9,12 +9,16 @@ class Edge: def __init__(self, edge): if edge.__class__==Edge: self._edge = edge._edge - self.vertices = edge.vertices[:] self.smooth = edge.smooth else: self._edge = edge self.smooth = False - self.key = edge.key + if edge: + self.vertices = edge.vertices[:] + self.key = edge.key + else: + self.vertices = [] + self.key = None self.faces = [] def __getattr__(self, attr): @@ -221,6 +225,8 @@ class Mesh: else: self.lines = [] + self.vertex_sequence = [] + def __getattr__(self, attr): return getattr(self._mesh, attr) @@ -275,6 +281,68 @@ class Mesh: self.lines += other.lines + def prepare_triangles(self, progress): + face_count = len(self.faces) + for i in range(face_count): + f = self.faces[i] + nverts = len(f.vertices) + if nverts==3: + continue + + # Calculate normals at each vertex of the face + edge_vecs = [] + for j in range(nverts): + edge_vecs.append(f.vertices[(j+1)%nverts].co-f.vertices[j].co) + + normals = [] + for j in range(nverts): + normals.append(edge_vecs[j-1].cross(edge_vecs[j]).normalized()) + + # Check which diagonal results in a flatter triangulation + flatness1 = normals[0].dot(normals[2]) + flatness2 = normals[1].dot(normals[3]) + cut_index = 1 if flatness1>flatness2 else 0 + + nf = Face(f) + nf.index = len(self.faces) + self.faces.append(nf) + + ne = Edge(None) + ne.index = len(self.edges) + self.edges.append(ne) + + nf.vertices = [f.vertices[cut_index], f.vertices[2], f.vertices[3]] + nf.loop_indices = [f.loop_indices[cut_index], f.loop_indices[2], f.loop_indices[3]] + for v in nf.vertices: + v.faces.append(nf) + + ne.vertices = [f.vertices[cut_index], f.vertices[2+cut_index]] + for v in ne.vertices: + v.edges.append(ne) + ne.key = make_edge_key(ne.vertices[0].index, ne.vertices[1].index) + ne.smooth = True + + f.vertices[3-cut_index].faces.remove(f) + del f.vertices[3-cut_index] + f.loop_indices = [f.loop_indices[0], f.loop_indices[1], f.loop_indices[2+cut_index]] + + ne.faces = [f, nf] + if cut_index==0: + nf.edges = [ne, f.edges[2], f.edges[3]] + f.edges = [f.edges[0], f.edges[1], ne] + else: + nf.edges = [f.edges[1], f.edges[2], ne] + f.edges = [f.edges[0], ne, f.edges[3]] + for e in nf.edges: + if e!=ne: + e.faces.remove(f) + e.faces.append(nf) + + f.normal = normals[1-cut_index] + nf.normal = normals[3-cut_index] + + progress.set_progress(i/face_count) + def prepare_smoothing(self, progress): smooth_limit = -1 if self.smoothing=='NONE': @@ -532,6 +600,141 @@ class Mesh: progress.set_progress(i/len(self.vertices)) + def prepare_sequence(self, progress): + progress.push_task("Reordering faces", 0.0, 0.5) + self.reorder_faces(progress) + + progress.set_task("Building sequence", 0.5, 1.0) + sequence = None + for i, f in enumerate(self.faces): + if sequence: + if len(sequence)==3: + # Rotate the first three vertices so that the new face can be added + if sequence[0] in f.vertices and sequence[1] not in f.vertices: + sequence.append(sequence[0]) + del sequence[0] + elif sequence[2] not in f.vertices and sequence[1] in f.vertices: + sequence.insert(0, sequence[-1]) + del sequence[-1] + + if sequence[-1] not in f.vertices: + sequence = None + else: + to_add = [v for v in f.vertices if v!=sequence[-1] and v!=sequence[-2]] + if len(to_add)==2: + if (f.vertices[1]==sequence[-1]) != (len(sequence)%2==1): + to_add.reverse() + sequence.append(sequence[-1]) + sequence += to_add + + if not sequence: + sequence = f.vertices[:] + self.vertex_sequence.append(sequence) + + progress.set_progress(i/len(self.faces)) + + progress.pop_task() + + self.reorder_vertices() + + def reorder_faces(self, progress): + # Tom Forsyth's vertex cache optimization algorithm + # http://eelpi.gotdns.org/papers/fast_vert_cache_opt.html + + for f in self.faces: + f.flag = False + + last_triangle_score = 0.75 + cache_decay_power = 1.5 + valence_boost_scale = 2.0 + valence_boost_power = -0.5 + + max_cache_size = 32 + cached_vertices = [] + + # Keep track of the score and number of unused faces for each vertex + vertex_info = [[0, len(v.faces)] for v in self.vertices] + for vi in vertex_info: + vi[0] = valence_boost_scale*(vi[1]**valence_boost_power) + + face = None + reordered_faces = [] + + n_processed = 0 + while 1: + if not face: + # Previous iteration gave no candidate for best face (or this is + # the first iteration). Scan all faces for the highest score. + best_score = 0 + for f in self.faces: + if f.flag: + continue + + score = sum(vertex_info[v.index][0] for v in f.vertices) + if score>best_score: + best_score = score + face = f + + if not face: + break + + reordered_faces.append(face) + face.flag = True + + for v in face.vertices: + vertex_info[v.index][1] -= 1 + + # Shuffle the vertex into the front of the cache + if v in cached_vertices: + cached_vertices.remove(v) + cached_vertices.insert(0, v) + + # Update scores for all vertices in the cache + for i, v in enumerate(cached_vertices): + score = 0 + if i<3: + score += last_triangle_score + elif ibest_score: + best_score = score + face = f + + del cached_vertices[max_cache_size:] + + n_processed += 1 + progress.set_progress(n_processed/len(self.faces)) + + self.faces = reordered_faces + for i, f in enumerate(self.faces): + f.index = i + + def reorder_vertices(self): + for v in self.vertices: + v.index = -1 + + reordered_vertices = [] + for s in self.vertex_sequence: + for v in s: + if v.index<0: + v.index = len(reordered_vertices) + reordered_vertices.append(v) + + self.vertices = reordered_vertices + + for e in self.edges: + e.key = make_edge_key(e.vertices[0].index, e.vertices[1].index) + def drop_references(self): for v in self.vertices: v._vertex = None @@ -545,56 +748,12 @@ class Mesh: u._layer = None self._mesh = None - def create_strip(self, face, max_len): - # Find an edge with another unused face next to it - edge = None - for e in face.edges: - other = e.other_face(face) - if other and not other.flag: - edge = e - break - - if not edge: - return None - - # Add initial vertices so that we'll complete the edge on the first - # iteration - vertices = face.pivot_vertices(*edge.vertices) - if len(vertices)==3: - result = [vertices[-1], vertices[0]] - else: - result = [vertices[-2], vertices[-1]] - - while 1: - face.flag = True - - vertices = face.pivot_vertices(*result[-2:]) - k = len(result)%2 - - # Quads need special handling because the winding of every other - # triangle in the strip is reversed - if len(vertices)==4 and not k: - result.append(vertices[3]) - result.append(vertices[2]) - if len(vertices)==4 and k: - result.append(vertices[3]) - - if len(result)>=max_len: - break - - # Hop over the last edge - edge = face.get_edge(*result[-2:]) - face = edge.other_face(face) - if not face or face.flag: - break - - return result def create_mesh_from_object(context, obj, progress): if obj.type!="MESH": raise Exception("Object is not a mesh") - progress.push_task("Preparing mesh", 0.0, 0.3) + progress.push_task("Preparing mesh", 0.0, 0.2) objs = [(obj, mathutils.Matrix())] i = 0 @@ -629,12 +788,16 @@ def create_mesh_from_object(context, obj, progress): else: mesh = me - progress.set_task("Smoothing", 0.3, 0.6) + progress.set_task("Triangulating", 0.2, 0.3) + mesh.prepare_triangles(progress) + progress.set_task("Smoothing", 0.3, 0.5) mesh.prepare_smoothing(progress) - progress.set_task("Vertex groups", 0.6, 0.7) + progress.set_task("Vertex groups", 0.5, 0.6) mesh.prepare_vertex_groups(obj) - progress.set_task("Preparing UVs", 0.7, 1.0) + progress.set_task("Preparing UVs", 0.6, 0.8) mesh.prepare_uv(obj, progress) + progress.set_task("Render sequence", 0.8, 1.0) + mesh.prepare_sequence(progress) # Discard the temporary Blender meshes after making sure there's no # references to the data