X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;ds=sidebyside;f=blender%2Fio_mspgl%2Fmesh.py;h=08f0bb4ac814ea196d1411de15720c0ff17eb993;hb=09c8337778f6d2e595016d02023297d958cf6316;hp=10c2c21430e997465f1f870820b310ba56d98286;hpb=3aefe3f4132cccc64d21fd7a0ca14eb5967d77f5;p=libs%2Fgl.git diff --git a/blender/io_mspgl/mesh.py b/blender/io_mspgl/mesh.py index 10c2c214..08f0bb4a 100644 --- a/blender/io_mspgl/mesh.py +++ b/blender/io_mspgl/mesh.py @@ -225,6 +225,8 @@ class Mesh: else: self.lines = [] + self.vertex_sequence = [] + def __getattr__(self, attr): return getattr(self._mesh, attr) @@ -594,6 +596,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 @@ -607,50 +744,6 @@ 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": @@ -693,12 +786,14 @@ def create_mesh_from_object(context, obj, progress): progress.set_task("Triangulating", 0.2, 0.3) mesh.prepare_triangles(progress) - progress.set_task("Smoothing", 0.3, 0.6) + 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