meshlets_adjacency.zig (13921B)
1 const std = @import("std"); 2 const assert = std.debug.assert; 3 4 const HalfEdgeMap = @import("half_edge_map.zig"); 5 const Mesh = @import("mesh.zig"); 6 7 const meshlets = @import("meshlets.zig"); 8 const ClusterDescriptor = meshlets.ClusterDescriptor; 9 const ClusterMesh = meshlets.ClusterMesh; 10 11 pub fn buildClusters( 12 allocator: std.mem.Allocator, 13 mesh: *const Mesh, 14 max_vertices: u32, 15 max_triangles: u32, 16 ) !ClusterMesh { 17 // Only triangle meshes are supported 18 assert(mesh.indices.len % 3 == 0); 19 // Must have at least one triangle 20 assert(max_vertices >= 3); 21 assert(max_triangles >= 1); 22 23 // 'unused' tracks which vertices have not been used 24 // unused[vtx_idx] = 1 -> not used 25 // unused[vtx_idx] = 0 -> used 26 const unused = try allocator.alloc(u8, mesh.positions.len); 27 defer allocator.free(unused); 28 @memset(unused, 1); 29 30 const indices = try allocator.alloc(u32, mesh.indices.len); 31 var descriptors = std.ArrayList(ClusterDescriptor).init(allocator); 32 defer descriptors.deinit(); 33 34 var num_vertices: u32 = 0; 35 var num_triangles: u32 = 0; 36 var cluster_offset: u32 = 0; 37 38 var map = try HalfEdgeMap.init(mesh.indices, allocator); 39 var tri: [3]u32 = undefined; 40 var adjacent = std.ArrayList(u32).init(allocator); 41 const usage = try buildUsageMap(mesh, allocator); 42 43 for (0..mesh.indices.len / 3) |_| { 44 // Fetch next triangle 45 if (adjacent.items.len > 0) { 46 var min_extra: u32 = std.math.maxInt(u32); 47 var min_score: u32 = std.math.maxInt(u32); 48 var idx_best: u32 = 0; 49 const num_adjacent = adjacent.items.len / 3; 50 for (0..num_adjacent) |triangle_idx| { 51 const i = @as(u32, @intCast(triangle_idx)) * 3; 52 const adj = [3]u32{ 53 adjacent.items[i], 54 adjacent.items[i + 1], 55 adjacent.items[i + 2], 56 }; 57 58 var extra: u32 = 1; 59 if (inSlice(u32, indices[cluster_offset..], adj[2])) { 60 extra = 0; 61 } 62 63 if ((usage[adj[0]] == 1) or (usage[adj[1]] == 1) or (usage[adj[2]] == 1)) { 64 extra = 0; 65 } 66 67 if (extra > min_extra) { 68 continue; 69 } 70 const score = usage[adj[0]] + usage[adj[1]] + usage[adj[2]] - 3; 71 72 if ((extra < min_extra) or (score < min_score)) { 73 min_extra = extra; 74 min_score = score; 75 tri = adj; 76 idx_best = i; 77 } 78 } 79 tri = [3]u32{ 80 adjacent.items[idx_best], 81 adjacent.items[idx_best + 1], 82 adjacent.items[idx_best + 2], 83 }; 84 _ = adjacent.orderedRemove(idx_best); 85 _ = adjacent.orderedRemove(idx_best); 86 _ = adjacent.orderedRemove(idx_best); 87 } else { 88 tri = map.pop(); 89 } 90 const a = tri[0]; 91 const b = tri[1]; 92 const c = tri[2]; 93 usage[a] -= 1; 94 usage[b] -= 1; 95 usage[c] -= 1; 96 97 // Triangles must be non-degenerate 98 assert(a != b and a != c and b != c); 99 100 // Vertices must be contained in the mesh 101 const a_valid = a < mesh.positions.len; 102 const b_valid = b < mesh.positions.len; 103 const c_valid = c < mesh.positions.len; 104 assert(a_valid and b_valid and c_valid); 105 106 // Verify cluster has space 107 const num_extra = unused[a] + unused[b] + unused[c]; 108 const too_many_vertices = num_vertices + num_extra >= max_vertices; 109 const too_many_triangles = num_triangles >= max_triangles; 110 if (too_many_vertices or too_many_triangles) { 111 // Save cluster info 112 try descriptors.append(.{ 113 .offset = cluster_offset, 114 .num_vertices = num_vertices, 115 .num_triangles = num_triangles, 116 }); 117 118 // Reset state for next cluster 119 @memset(unused, 1); 120 cluster_offset += num_triangles * 3; 121 num_vertices = 0; 122 num_triangles = 0; 123 124 // Add all adjacent triangles back to the half-edge map 125 for (0..adjacent.items.len / 3) |i| { 126 const idx = i * 3; 127 const adj = [3]u32{ 128 adjacent.items[idx], 129 adjacent.items[idx + 1], 130 adjacent.items[idx + 2], 131 }; 132 map.insert(adj); 133 } 134 adjacent.clearAndFree(); 135 } 136 137 // Mark vertices as used 138 unused[a] = 0; 139 unused[b] = 0; 140 unused[c] = 0; 141 142 // Add triangle to cluster 143 const offset = cluster_offset + num_triangles * 3; 144 indices[offset] = a; 145 indices[offset + 1] = b; 146 indices[offset + 2] = c; 147 148 num_vertices += num_extra; 149 num_triangles += 1; 150 151 // Get newly adjacent triangles 152 for (0..3) |side| { 153 const triangle = map.adjacentTo(tri, @intCast(side)) orelse { 154 continue; 155 }; 156 try adjacent.appendSlice(&triangle); 157 std.debug.assert(map.remove(triangle)); 158 } 159 160 // If we're out of adjacent triangles, this cluster is done 161 const no_more_adjacent = adjacent.items.len <= 0; 162 if (no_more_adjacent) { 163 // Save cluster info 164 try descriptors.append(.{ 165 .offset = cluster_offset, 166 .num_vertices = num_vertices, 167 .num_triangles = num_triangles, 168 }); 169 170 // Reset state for next cluster 171 @memset(unused, 1); 172 cluster_offset += num_triangles * 3; 173 num_vertices = 0; 174 num_triangles = 0; 175 continue; 176 } 177 } 178 179 // Add final cluster 180 if (num_triangles > 0) { 181 try descriptors.append(.{ 182 .offset = cluster_offset, 183 .num_vertices = num_vertices, 184 .num_triangles = num_triangles, 185 }); 186 } 187 188 // Total size of mesh should not change 189 assert(mesh.indices.len == cluster_offset + num_triangles * 3); 190 191 return .{ 192 .positions = mesh.positions, 193 .normals = mesh.normals, 194 .tex_coords = mesh.tex_coords, 195 .tangents = mesh.tangents, 196 .bitangents = mesh.bitangents, 197 .indices = indices, 198 .descriptors = try descriptors.toOwnedSlice(), 199 }; 200 } 201 202 pub fn buildUsageMap( 203 mesh: *const Mesh, 204 allocator: std.mem.Allocator, 205 ) ![]u32 { 206 const num_vertices = mesh.positions.len; 207 const map = try allocator.alloc(u32, num_vertices); 208 @memset(map, 0); 209 for (mesh.indices) |idx| { 210 map[idx] += 1; 211 } 212 return map; 213 } 214 215 fn inSlice(comptime T: type, slice: []const T, item: T) bool { 216 for (slice) |iter_item| { 217 if (iter_item == item) { 218 return true; 219 } 220 } 221 return false; 222 } 223 224 //const ClusterOptions = struct { 225 // max_verts: u32, 226 // max_prims: u32, 227 //}; 228 // 229 //const ClusterDescriptor = struct { 230 // offset: u32, 231 // num_prims: u32, 232 // num_verts: u32, 233 //}; 234 // 235 //pub fn buildClusters(mesh: *const Mesh, allocator: std.mem.Allocator) !void { 236 // const max_prims = 126; 237 // var offset: u32 = 0; 238 // 239 // var map = try HalfEdgeMap.init(mesh.indices, allocator); 240 // var tri: ?[3]u32 = null; 241 // 242 // var descriptors = std.ArrayList(ClusterDescriptor).init(allocator); 243 // // this holds offsets and counts for all clusters 244 // 245 // const indices: []u32 = try allocator.alloc(u32, mesh.indices.len); 246 // // this holds the actual index data for all clusters 247 // // should be free'd by caller (eventually) 248 // 249 // while (map.count() > 0) { 250 // if (tri == null) { 251 // tri = map.pop(); 252 // } 253 // const cluster_end = @min(offset + max_prims * 3, mesh.indices.len); 254 // const cluster = indices[offset..cluster_end]; 255 // 256 // //result = try buildClusterFewest(allocator, &map, usage, tri.?); 257 // const result = try buildClusterSimple( 258 // allocator, 259 // &map, 260 // tri.?, 261 // cluster, 262 // ); 263 // offset += result.descriptor.num_prims * 3; 264 // try descriptors.append(result.descriptor); 265 // tri = result.next; 266 // } 267 // std.log.info("offset: {}", .{offset}); 268 // std.debug.assert(offset == indices.len); 269 // std.log.info("num clusters: {}", .{descriptors.items.len}); 270 //} 271 // 272 //const ClusterResult = struct { 273 // descriptor: ClusterDescriptor, 274 // next: ?[3]u32, 275 //}; 276 // 277 //pub const Triangle = struct { 278 // a: u32, 279 // b: u32, 280 // c: u32, 281 // 282 // pub fn permute(self: *const Triangle) Triangle { 283 // return .{ .a = self.b, .b = self.c, .c = self.a }; 284 // } 285 // 286 // pub fn reverse(self: *const Triangle) Triangle { 287 // return .{ .a = self.c, .b = self.b, .c = self.a }; 288 // } 289 //}; 290 // 291 //fn buildClusterSimple( 292 // allocator: std.mem.Allocator, 293 // map: *HalfEdgeMap, 294 // initial_triangle: [3]u32, 295 // cluster: []u32, 296 //) !ClusterResult { 297 // const max_prims = 126; 298 // 299 // var vertices = std.AutoHashMap(u32, void).init(allocator); 300 // var adjacent = std.ArrayList(Triangle).init(allocator); 301 // var tri: ?Triangle = .{ 302 // .a = initial_triangle[0], 303 // .b = initial_triangle[1], 304 // .c = initial_triangle[2], 305 // }; 306 // 307 // var idx: u32 = 0; 308 // while (idx < max_prims * 3) { 309 // // Add the most recent triangle to the cluster 310 // cluster[idx] = tri.?.a; 311 // cluster[idx + 1] = tri.?.b; 312 // cluster[idx + 2] = tri.?.c; 313 // //@memcpy(cluster[idx .. idx + 3], &tri.?); 314 // try vertices.put(tri.?.a, {}); 315 // try vertices.put(tri.?.b, {}); 316 // try vertices.put(tri.?.c, {}); 317 // idx += 3; 318 // 319 // // Get newly adjacent triangles 320 // for (0..3) |side| { 321 // const triangle = map.adjacentTo(tri.?, @intCast(side)) orelse { 322 // continue; 323 // }; 324 // try adjacent.append(triangle); 325 // std.debug.assert(map.remove(triangle)); 326 // } 327 // if (adjacent.items.len <= 0) { 328 // tri = null; 329 // break; 330 // } 331 // 332 // // Oldest adjacent triangle is up next 333 // tri = [3]u32{ 334 // adjacent.items[0].a, 335 // adjacent.items[0].b, 336 // adjacent.items[0].c, 337 // }; 338 // _ = adjacent.orderedRemove(0); 339 // } 340 // 341 // // Add all adjacent triangles back to the half-edge map 342 // for (adjacent.items) |adj_tri| { 343 // //const adj = [3]u32{ adj_tri.a, adj_tri.b, adj_tri.c }; 344 // map.insert(adj_tri); 345 // } 346 // if (tri != null) { 347 // const triangle = .{ 348 // .a = tri.?[0], 349 // .b = tri.?[1], 350 // .c = tri.?[2], 351 // }; 352 // map.insert(triangle); 353 // } 354 // 355 // return .{ 356 // .descriptor = .{ 357 // .offset = undefined, 358 // .num_prims = idx / 3, 359 // .num_verts = vertices.count(), 360 // }, 361 // .next = null, //tri, 362 // }; 363 //} 364 // 365 //fn buildClusterFewest( 366 // allocator: std.mem.Allocator, 367 // map: *HalfEdgeMap, 368 // usage: []u32, 369 // initial_triangle: [3]u32, 370 //) !ClusterResult { 371 // var cluster = std.ArrayList(u32).init(allocator); 372 // var adjacent = std.ArrayList(u32).init(allocator); 373 // var tri: ?[3]u32 = initial_triangle; 374 // while (cluster.items.len < 126 * 3) { 375 // // Add the most recent triangle to the cluster 376 // try cluster.appendSlice(&tri.?); 377 // 378 // // Get newly adjacent triangles 379 // for (0..3) |side| { 380 // const triangle = map.adjacentTo(tri.?, @intCast(side)) orelse { 381 // continue; 382 // }; 383 // try adjacent.appendSlice(&triangle); 384 // std.debug.assert(map.remove(triangle)); 385 // } 386 // if (adjacent.items.len <= 0) { 387 // tri = null; 388 // break; 389 // } 390 // 391 // var min_extra: u32 = std.math.maxInt(u32); 392 // var min_score: u32 = std.math.maxInt(u32); 393 // var idx_best: u32 = 0; 394 // const num_adjacent = adjacent.items.len / 3; 395 // for (0..num_adjacent) |triangle_idx| { 396 // const i = @as(u32, @intCast(triangle_idx)) * 3; 397 // const adj = [3]u32{ 398 // adjacent.items[i], 399 // adjacent.items[i + 1], 400 // adjacent.items[i + 2], 401 // }; 402 // 403 // var extra: u32 = 1; 404 // if (inSlice(u32, cluster.items, adj[2])) { 405 // extra = 0; 406 // } 407 // 408 // if ((usage[adj[0]] == 1) or (usage[adj[1]] == 1) or (usage[adj[2]] == 1)) { 409 // extra = 0; 410 // } 411 // 412 // if (extra > min_extra) { 413 // continue; 414 // } 415 // const score = usage[adj[0]] + usage[adj[1]] + usage[adj[2]] - 3; 416 // 417 // if ((extra < min_extra) or (score < min_score)) { 418 // min_extra = extra; 419 // min_score = score; 420 // tri = adj; 421 // idx_best = i; 422 // } 423 // } 424 // _ = adjacent.orderedRemove(idx_best); 425 // _ = adjacent.orderedRemove(idx_best); 426 // _ = adjacent.orderedRemove(idx_best); 427 // usage[tri.?[0]] -= 1; 428 // usage[tri.?[1]] -= 1; 429 // usage[tri.?[2]] -= 1; 430 // } 431 // const num_adjacent = adjacent.items.len / 3; 432 // for (0..num_adjacent) |triangle_idx| { 433 // const i = @as(u32, @intCast(triangle_idx)) * 3; 434 // const adj = [3]u32{ 435 // adjacent.items[i], 436 // adjacent.items[i + 1], 437 // adjacent.items[i + 2], 438 // }; 439 // map.insert(adj); 440 // } 441 // std.log.info("cluster size: {}", .{cluster.items.len / 3}); 442 // return .{ 443 // .cluster = cluster, 444 // .next = tri, 445 // }; 446 //}