From 09c8337778f6d2e595016d02023297d958cf6316 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Sun, 5 May 2019 16:54:37 +0300 Subject: [PATCH] Rewrite triangle strip generation in the Blender exporter The old algorithm had many of the right ideas but was too clever by half and consequently very complex. Use a simpler score-based algorithm developed by Tom Forsyth. Also reorder vertices to make memory accesses to them occur in a more linear fashion. Options related to cache optimization were removed since there's no good reason not to optimize. --- blender/io_mspgl/__init__.py | 11 -- blender/io_mspgl/export_mesh.py | 193 +++----------------------------- blender/io_mspgl/mesh.py | 189 +++++++++++++++++++++++-------- 3 files changed, 159 insertions(+), 234 deletions(-) diff --git a/blender/io_mspgl/__init__.py b/blender/io_mspgl/__init__.py index a275110e..e1efbc21 100644 --- a/blender/io_mspgl/__init__.py +++ b/blender/io_mspgl/__init__.py @@ -33,9 +33,6 @@ class ExportMspGLBase(ExportHelper): class ExportMspGLMeshBase(ExportMspGLBase): use_strips = bpy.props.BoolProperty(name="Use strips", description="Combine faces into triangle strips", default=True) use_degen_tris = bpy.props.BoolProperty(name="Use degen tris", description="Concatenate triangle strips with degenerate triangles", default=False) - max_strip_len = bpy.props.IntProperty(name="Max strip length", description="Maximum length for a triangle strip", default=1024, min=4, max=16384) - optimize_cache = bpy.props.BoolProperty(name="Optimize cache", description="Optimize element order for vertex cache", default=True) - cache_size = bpy.props.IntProperty(name="Cache size", description="Simulated vertex cache size used in optimization", default=64, min=8, max=1024) def draw(self, context): self.general_col = self.layout.column() @@ -44,14 +41,6 @@ class ExportMspGLMeshBase(ExportMspGLBase): col.label("Triangle strips") col.prop(self, "use_strips") col.prop(self, "use_degen_tris") - col.prop(self, "max_strip_len") - - self.layout.separator() - - col = self.layout.column() - col.label("Vertex cache") - col.prop(self, "optimize_cache") - col.prop(self, "cache_size") class ExportMspGLMesh(bpy.types.Operator, ExportMspGLMeshBase): bl_idname = "export_mesh.mspgl_mesh" diff --git a/blender/io_mspgl/export_mesh.py b/blender/io_mspgl/export_mesh.py index 39619f8b..771f825e 100644 --- a/blender/io_mspgl/export_mesh.py +++ b/blender/io_mspgl/export_mesh.py @@ -2,190 +2,29 @@ import itertools import bpy import mathutils -class VertexCache: - def __init__(self, size): - self.size = size - self.slots = [-1]*self.size - - def fetch(self, v): - hit = v.index in self.slots - if hit: - self.slots.remove(v.index) - self.slots.append(v.index) - if not hit: - del self.slots[0] - return hit - - def fetch_strip(self, strip): - hits = 0 - for v in strip: - if self.fetch(v): - hits += 1 - return hits - - def test_strip(self, strip): - hits = 0 - for i in range(len(strip)): - if i>=self.size: - break - if strip[i].index in self.slots[i:]: - hits += 1 - return hits - - class MeshExporter: def __init__(self): self.show_progress = True self.use_strips = True self.use_degen_tris = False - self.max_strip_len = 1024 - self.optimize_cache = True - self.cache_size = 64 self.material_tex = False - def stripify(self, mesh, progress=None): - for f in mesh.faces: - f.flag = False - - faces_done = 0 - strips = [] - loose = [] - - cache = None - if self.optimize_cache: - cache = VertexCache(self.cache_size) - - island = [] - face_neighbors = [] - island_strips = [] - while 1: - if not island: - # No current island; find any unused face to start from - queue = [] - for f in mesh.faces: - if not f.flag: - f.flag = True - queue.append(f) - break - - if not queue: - break - - # Find all faces connected to the first one - while queue: - face = queue.pop(0) - island.append(face) - - for n in face.get_neighbors(): - if not n.flag: - n.flag = True - queue.append(n) - - face_neighbors = [f.get_neighbors() for f in island] - - # Unflag the island for the next phase - for f in island: - f.flag = False - - # Find an unused face with as few unused neighbors as possible, but - # at least one. This heuristic gives a preference to faces in corners - # or along borders of a non-closed island. - best = 5 - face = None - for i, f in enumerate(island): - if f.flag: - continue - - score = sum(not n.flag for n in face_neighbors[i]) - if score>0 and scorebest_hits: - best = i - best_hits = hits - - strip = island_strips.pop(best) - strips.append(strip) - - if cache: - cache.fetch_strip(strip) - - faces_done += len(island) - progress.set_progress(faces_done/len(mesh.faces)) - - # Collect any faces that weren't used in strips - loose += [f for f in island if not f.flag] - for f in island: - f.flag = True - - island = [] - island_strips = [] - - if cache: - cache = VertexCache(self.cache_size) - total_hits = 0 - - if self.use_degen_tris and strips: - big_strip = [] - - for s in strips: - if big_strip: - # Generate glue elements, ensuring that the next strip begins at - # an even position - glue = [big_strip[-1], s[0]] - if len(big_strip)%2: - glue += [s[0]] + def join_strips(self, strips): + big_strip = [] - big_strip += glue - if cache: - total_hits += cache.fetch_strip(glue) - - big_strip += s - if cache: - total_hits += cache.fetch_strip(s) - - for f in loose: - # Add loose faces to the end. This wastes space, using five - # elements per triangle and six elements per quad. + for s in strips: + if big_strip: + # Generate glue elements, ensuring that the next strip begins at + # an even position + glue = [big_strip[-1], s[0]] if len(big_strip)%2: - order = (-1, -2, 0, 1) - else: - order = (0, 1, -1, -2) - vertices = [f.vertices[i] for i in order[:len(f.vertices)]] - - if big_strip: - glue = [big_strip[-1], vertices[0]] - big_strip += glue - if cache: - total_hits += cache.fetch_strip(glue) + glue += [s[0]] - big_strip += vertices - if cache: - total_hits += cache.fetch_strip(vertices) + big_strip += glue - strips = [big_strip] - loose = [] + big_strip += s - return strips, loose + return big_strip def export(self, context, out_file, obj=None, progress=None): if obj is None: @@ -196,17 +35,19 @@ class MeshExporter: if not progress: progress = Progress(self.show_progress and context) - progress.push_task("", 0.0, 0.65) + progress.push_task("", 0.0, 0.9) mesh = create_mesh_from_object(context, obj, progress) strips = [] loose = mesh.faces if self.use_strips: - progress.set_task("Creating strips", 0.65, 0.95) - strips, loose = self.stripify(mesh, progress) + strips = mesh.vertex_sequence + if self.use_degen_tris: + strips = [self.join_strips(strips)] + loose = [] - progress.set_task("Writing file", 0.95, 1.0) + progress.set_task("Writing file", 0.9, 1.0) from .outfile import open_output out_file = open_output(out_file) 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 -- 2.45.2