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()
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"
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 score<best:
- face = f
- best = score
-
- if face:
- # Create a strip starting from the face. This will flag the faces.
- strip = mesh.create_strip(face, self.max_strip_len)
- if strip:
- island_strips.append(strip)
- else:
- face.flag = True
- else:
- # Couldn't find a candidate face for starting a strip, so we're
- # done with this island
- while island_strips:
- best = 0
- if cache:
- # Find the strip that benefits the most from the current
- # contents of the vertex cache
- best_hits = 0
- for i in range(len(island_strips)):
- hits = cache.test_strip(island_strips[i])
- if hits>best_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:
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)
else:
self.lines = []
+ self.vertex_sequence = []
+
def __getattr__(self, attr):
return getattr(self._mesh, attr)
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 i<max_cache_size:
+ score += (1-(i-3)/(max_cache_size-3))**cache_decay_power
+ if vertex_info[v.index][1]:
+ score += valence_boost_scale*(vertex_info[v.index][1]**valence_boost_power)
+ vertex_info[v.index][0] = score
+
+ face = None
+ best_score = 0
+ for v in cached_vertices:
+ for f in v.faces:
+ if not f.flag:
+ score = sum(vertex_info[fv.index][0] for fv in f.vertices)
+ if score>best_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
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":
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
projects / libs / gl.git / commitdiff