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