forsyth_optimize.zig (8526B)
1 const std = @import("std"); 2 const assert = std.debug.assert; 3 4 const Mesh = @import("mesh.zig"); 5 6 const ScoreParameters = struct { 7 last_tri: f32 = 0.75, 8 cache_decay_power: f32 = 1.5, 9 valence_boost_scale: f32 = 2.0, 10 valence_boost_power: f32 = 0.5, 11 }; 12 13 const Vertex = struct { 14 cache_idx: ?u32 = undefined, 15 score: f32 = 0, 16 num_triangles: u32 = 0, 17 max_triangles: u32 = 0, 18 triangles: []u32 = undefined, 19 20 fn scoreFn( 21 self: *const Vertex, 22 max_cache_idx: u32, 23 params: ScoreParameters, 24 ) f32 { 25 // Vertex will never be used again 26 const num_active = self.max_triangles - self.num_triangles; 27 if (num_active <= 0) { 28 return -1.0; 29 } 30 31 // Boost score for lonely vertices so they go away fast 32 const valence_boost = std.math.pow( 33 f32, 34 @floatFromInt(num_active), 35 -params.valence_boost_power, 36 ); 37 const score = params.valence_boost_scale * valence_boost; 38 39 // No adjustments for vertices not in the cache yet 40 if (self.cache_idx == null) { 41 return score; 42 } 43 44 // Vertices from last triangle all get the same score 45 const cache_idx = self.cache_idx.?; 46 if (cache_idx < 3) { 47 return score + params.last_tri; 48 } 49 50 // For other vertices, score depends on cache position 51 assert(cache_idx < max_cache_idx); 52 const scale = 1.0 / @as(f32, @floatFromInt(max_cache_idx - 3)); 53 const adjusted_idx: f32 = @floatFromInt(cache_idx - 3); 54 const cache_score = 1.0 - adjusted_idx * scale; 55 return score + std.math.pow(f32, cache_score, params.cache_decay_power); 56 } 57 }; 58 59 const Triangle = struct { 60 added: bool = false, 61 score: f32 = 0, 62 vertices: [3]u32 = undefined, 63 }; 64 65 fn LRUCache(comptime T: type) type { 66 return struct { 67 const Self = @This(); 68 const List = std.DoublyLinkedList(T); 69 70 allocator: std.mem.Allocator, 71 list: List, 72 max_size: u32, 73 74 pub fn init(allocator: std.mem.Allocator, max_size: u32) Self { 75 return .{ 76 .list = std.DoublyLinkedList(T){}, 77 .allocator = allocator, 78 .max_size = max_size, 79 }; 80 } 81 82 pub fn deinit(self: *Self) void { 83 while (self.list.pop()) |node| { 84 self.allocator.destroy(node); 85 } 86 } 87 88 fn find(cache: *const Self, value: T) ?*List.Node { 89 var it = cache.list.first; 90 while (it) |node| : (it = node.next) { 91 if (node.data == value) { 92 return node; 93 } 94 } 95 return null; 96 } 97 98 pub fn insert(cache: *Self, value: T) !?*List.Node { 99 var node = cache.find(value); 100 if (node != null) { 101 cache.list.remove(node.?); 102 } else { 103 node = try cache.allocator.create(List.Node); 104 node.?.data = value; 105 } 106 cache.list.prepend(node.?); 107 108 if (cache.list.len > cache.max_size) { 109 return cache.list.pop(); 110 } 111 return null; 112 } 113 114 pub fn first(cache: *Self) ?*List.Node { 115 return cache.list.first; 116 } 117 }; 118 } 119 120 pub fn optimize( 121 allocator: std.mem.Allocator, 122 mesh: *Mesh, 123 max_cache_idx: u32, 124 params: ScoreParameters, 125 ) !void { 126 // Initialize vertex data structure 127 const vertices = try allocator.alloc(Vertex, mesh.positions.len); 128 defer allocator.free(vertices); 129 130 @memset(vertices, Vertex{}); 131 for (0..mesh.indices.len / 3) |i| { 132 const mesh_offset = i * 3; 133 const a = mesh.indices[mesh_offset]; 134 const b = mesh.indices[mesh_offset + 1]; 135 const c = mesh.indices[mesh_offset + 2]; 136 137 vertices[a].max_triangles += 1; 138 vertices[b].max_triangles += 1; 139 vertices[c].max_triangles += 1; 140 } 141 for (vertices) |*vertex| { 142 vertex.triangles = try allocator.alloc(u32, vertex.max_triangles); 143 vertex.max_triangles = 0; 144 } 145 for (0..mesh.indices.len / 3) |i| { 146 const mesh_offset = i * 3; 147 const a = mesh.indices[mesh_offset]; 148 const b = mesh.indices[mesh_offset + 1]; 149 const c = mesh.indices[mesh_offset + 2]; 150 151 const idx: u32 = @intCast(i); 152 vertices[a].triangles[vertices[a].max_triangles] = idx; 153 vertices[b].triangles[vertices[b].max_triangles] = idx; 154 vertices[c].triangles[vertices[c].max_triangles] = idx; 155 156 vertices[a].max_triangles += 1; 157 vertices[b].max_triangles += 1; 158 vertices[c].max_triangles += 1; 159 } 160 for (vertices) |*vertex| { 161 vertex.score = vertex.scoreFn(max_cache_idx, params); 162 } 163 164 // Initialize triangle data structure 165 const triangles = try allocator.alloc(Triangle, mesh.indices.len / 3); 166 defer allocator.free(triangles); 167 168 @memset(triangles, Triangle{}); 169 for (triangles, 0..) |*tri, i| { 170 const mesh_offset = i * 3; 171 const a = mesh.indices[mesh_offset]; 172 const b = mesh.indices[mesh_offset + 1]; 173 const c = mesh.indices[mesh_offset + 2]; 174 tri.vertices[0] = a; 175 tri.vertices[1] = b; 176 tri.vertices[2] = c; 177 tri.score = vertices[a].score + vertices[b].score + vertices[c].score; 178 } 179 180 // Store new indices here 181 const indices = try allocator.alloc(u32, mesh.indices.len); 182 183 // Run algorithm 184 var cache = LRUCache(u32).init(allocator, max_cache_idx); 185 defer cache.deinit(); 186 187 for (0..triangles.len) |i| { 188 var tri = bestTriangleFromCache(vertices, triangles, &cache); 189 if (tri == null) { 190 tri = bestTriangleOverall(triangles); 191 } 192 assert(tri != null); 193 194 const offset = i * 3; 195 indices[offset] = triangles[tri.?].vertices[0]; 196 indices[offset + 1] = triangles[tri.?].vertices[1]; 197 indices[offset + 2] = triangles[tri.?].vertices[2]; 198 199 try addTriangleToCache( 200 allocator, 201 tri.?, 202 vertices, 203 triangles, 204 &cache, 205 params, 206 ); 207 } 208 209 allocator.free(mesh.indices); 210 mesh.indices = indices; 211 } 212 213 fn addTriangleToCache( 214 allocator: std.mem.Allocator, 215 triangle_idx: u32, 216 vertices: []Vertex, 217 triangles: []Triangle, 218 cache: *LRUCache(u32), 219 params: ScoreParameters, 220 ) !void { 221 assert(!triangles[triangle_idx].added); 222 223 // Insert triangle 224 triangles[triangle_idx].added = true; 225 for (triangles[triangle_idx].vertices) |idx| { 226 const removed = try cache.insert(idx); 227 if (removed != null) { 228 const vtx = &vertices[removed.?.data]; 229 vtx.cache_idx = null; 230 vtx.score = vtx.scoreFn(cache.max_size, params); 231 allocator.destroy(removed.?); 232 } 233 vertices[idx].num_triangles += 1; 234 } 235 236 // Update all other cache entries 237 var it = cache.first(); 238 var cache_idx: u32 = 0; 239 while (it) |node| : (it = node.next) { 240 const vtx = &vertices[node.data]; 241 if (cache_idx < cache.max_size) { 242 vtx.cache_idx = cache_idx; 243 } else { 244 vtx.cache_idx = null; 245 } 246 cache_idx += 1; 247 vtx.score = vtx.scoreFn(cache.max_size, params); 248 } 249 } 250 251 fn bestTriangleOverall(triangles: []Triangle) ?u32 { 252 var best_triangle: ?u32 = null; 253 var best_score: f32 = 0.0; 254 for (triangles, 0..) |tri, i| { 255 if (!tri.added and tri.score > best_score) { 256 best_triangle = @intCast(i); 257 best_score = tri.score; 258 } 259 } 260 return best_triangle; 261 } 262 263 fn bestTriangleFromCache( 264 vertices: []Vertex, 265 triangles: []Triangle, 266 cache: *LRUCache(u32), 267 ) ?u32 { 268 var best_score: f32 = 0.0; 269 var best_triangle: ?u32 = null; 270 var it = cache.first(); 271 while (it) |node| : (it = node.next) { 272 const vtx = &vertices[node.data]; 273 for (vtx.triangles) |idx| { 274 const tri = &triangles[idx]; 275 if (tri.added) { 276 continue; 277 } 278 const a = vertices[tri.vertices[0]]; 279 const b = vertices[tri.vertices[1]]; 280 const c = vertices[tri.vertices[2]]; 281 tri.score = a.score + b.score + c.score; 282 283 if (tri.score > best_score) { 284 best_triangle = idx; 285 best_score = tri.score; 286 } 287 } 288 } 289 return best_triangle; 290 }