lib/geometry/src/mesh.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Indexed triangle meshes and the linear scan over their triangles.
2 //!
3 //! The scan tests every triangle in index order. It is the reference a `Bvh`
4 //! answers identically to, and the right query for a mesh too small to earn a
5 //! tree. Every nearest query orders candidates by `(t, triangle index)`, so of
6 //! two triangles met at the same `t` the lower index wins.
7 const std = @import("std");
8 const linear = @import("linear");
9 const intersect = @import("intersect.zig");
10 const primitive = @import("primitive.zig");
11 const sweep = @import("sweep.zig");
12
13 const assert = std.debug.assert;
14 const Aabb = primitive.Aabb;
15 const Capsule = primitive.Capsule;
16 const Ray = primitive.Ray;
17 const Sphere = primitive.Sphere;
18 const Triangle = primitive.Triangle;
19 const Vec3 = linear.Vec3;
20
21 /// The most triangles a mesh may hold, so that every tree node index fits in
22 /// a `u32`.
23 pub const max_triangles: usize = std.math.maxInt(u32) / 2;
24
25 /// A borrowed triangle list: triangle `i` joins the positions named by
26 /// `indices[3 i .. 3 i + 3]`.
27 pub const Mesh = struct {
28 positions: []const Vec3,
29 indices: []const u32,
30
31 pub fn triangleCount(mesh: Mesh) usize {
32 assert(mesh.indices.len % 3 == 0);
33 return mesh.indices.len / 3;
34 }
35
36 /// Whether the index list names whole triangles over existing, finite
37 /// positions, within `max_triangles`.
38 pub fn isWellFormed(mesh: Mesh) bool {
39 if (mesh.indices.len % 3 != 0) return false;
40 if (mesh.indices.len / 3 > max_triangles) return false;
41 for (mesh.indices) |index| {
42 if (index >= mesh.positions.len) return false;
43 }
44 for (mesh.positions) |p| {
45 if (!std.math.isFinite(p.x) or !std.math.isFinite(p.y) or !std.math.isFinite(p.z)) return false;
46 }
47 return true;
48 }
49
50 pub fn triangle(mesh: Mesh, index: usize) Triangle {
51 const base = index * 3;
52 assert(base + 3 <= mesh.indices.len);
53 return .{
54 .a = mesh.positions[mesh.indices[base + 0]],
55 .b = mesh.positions[mesh.indices[base + 1]],
56 .c = mesh.positions[mesh.indices[base + 2]],
57 };
58 }
59
60 /// The box around every triangle, empty for a mesh with none.
61 pub fn bounds(mesh: Mesh) Aabb {
62 var box = Aabb.empty;
63 for (mesh.indices) |index| box = box.joinPoint(mesh.positions[index]);
64 return box;
65 }
66
67 /// The nearest triangle the ray meets with `t` in `[t_min, t_max]`.
68 pub fn raycast(mesh: Mesh, ray: Ray, t_min: f32, t_max: f32) ?RayHit {
69 assert(t_min <= t_max);
70 var best: ?RayHit = null;
71 for (0..mesh.triangleCount()) |index| {
72 const hit = intersect.rayTriangle(ray, mesh.triangle(index)) orelse continue;
73 if (hit.t < t_min or hit.t > t_max) continue;
74 if (best) |held| {
75 if (hit.t >= held.t) continue;
76 }
77 best = .{ .t = hit.t, .u = hit.u, .v = hit.v, .triangle = @intCast(index) };
78 }
79 return best;
80 }
81
82 /// Whether the ray meets any triangle with `t` in `[t_min, t_max]`.
83 pub fn raycastAny(mesh: Mesh, ray: Ray, t_min: f32, t_max: f32) bool {
84 assert(t_min <= t_max);
85 for (0..mesh.triangleCount()) |index| {
86 const hit = intersect.rayTriangle(ray, mesh.triangle(index)) orelse continue;
87 if (hit.t >= t_min and hit.t <= t_max) return true;
88 }
89 return false;
90 }
91
92 /// The triangles the sphere touches, lowest indices first, into `out`.
93 pub fn overlapSphere(mesh: Mesh, sphere: Sphere, out: []u32) Overlap {
94 var count: usize = 0;
95 for (0..mesh.triangleCount()) |index| {
96 if (!intersect.sphereTriangle(sphere, mesh.triangle(index))) continue;
97 if (count == out.len) return .{ .count = count, .complete = false };
98 out[count] = @intCast(index);
99 count += 1;
100 }
101 return .{ .count = count, .complete = true };
102 }
103
104 /// The triangles the capsule touches, lowest indices first, into `out`.
105 pub fn overlapCapsule(mesh: Mesh, capsule: Capsule, out: []u32) Overlap {
106 var count: usize = 0;
107 for (0..mesh.triangleCount()) |index| {
108 if (!intersect.capsuleTriangle(capsule, mesh.triangle(index))) continue;
109 if (count == out.len) return .{ .count = count, .complete = false };
110 out[count] = @intCast(index);
111 count += 1;
112 }
113 return .{ .count = count, .complete = true };
114 }
115
116 /// The first triangle the sphere touches as it moves by `displacement`.
117 pub fn sweepSphere(mesh: Mesh, sphere: Sphere, displacement: Vec3) ?SweepHit {
118 var best: ?SweepHit = null;
119 for (0..mesh.triangleCount()) |index| {
120 const hit = sweep.sphereTriangle(sphere, displacement, mesh.triangle(index)) orelse continue;
121 if (best) |held| {
122 if (hit.t >= held.t) continue;
123 }
124 best = .{ .t = hit.t, .point = hit.point, .normal = hit.normal, .triangle = @intCast(index) };
125 }
126 return best;
127 }
128
129 /// The first triangle the capsule touches as it moves by `displacement`.
130 pub fn sweepCapsule(mesh: Mesh, capsule: Capsule, displacement: Vec3) ?SweepHit {
131 var best: ?SweepHit = null;
132 for (0..mesh.triangleCount()) |index| {
133 const hit = sweep.capsuleTriangle(capsule, displacement, mesh.triangle(index)) orelse continue;
134 if (best) |held| {
135 if (hit.t >= held.t) continue;
136 }
137 best = .{ .t = hit.t, .point = hit.point, .normal = hit.normal, .triangle = @intCast(index) };
138 }
139 return best;
140 }
141 };
142
143 /// A ray meeting a mesh triangle: the ray parameter, the barycentric weights
144 /// of vertices `b` and `c`, and the triangle index in the mesh.
145 pub const RayHit = struct {
146 t: f32,
147 u: f32,
148 v: f32,
149 triangle: u32,
150 };
151
152 /// A sweep's first contact with a mesh triangle, as `sweep.Hit` reports it,
153 /// with the triangle index in the mesh.
154 pub const SweepHit = struct {
155 t: f32,
156 point: Vec3,
157 normal: Vec3,
158 triangle: u32,
159 };
160
161 /// How many triangle indices an overlap query wrote, and whether those were
162 /// all the triangles it touched. An incomplete answer holds the lowest
163 /// indices that fit.
164 pub const Overlap = struct {
165 count: usize,
166 complete: bool,
167 };
168
169 const testing = std.testing;
170
171 const quad_positions = [_]Vec3{
172 Vec3.init(-1, -1, 0), Vec3.init(1, -1, 0), Vec3.init(1, 1, 0), Vec3.init(-1, 1, 0),
173 Vec3.init(-1, -1, -2), Vec3.init(1, -1, -2), Vec3.init(1, 1, -2),
174 };
175 const quad_indices = [_]u32{ 0, 1, 2, 0, 2, 3, 4, 5, 6 };
176 const quad = Mesh{ .positions = &quad_positions, .indices = &quad_indices };
177
178 test "a mesh checks its index list" {
179 try testing.expect(quad.isWellFormed());
180 try testing.expectEqual(@as(usize, 3), quad.triangleCount());
181 try testing.expect(!(Mesh{ .positions = &quad_positions, .indices = &.{ 0, 1 } }).isWellFormed());
182 try testing.expect(!(Mesh{ .positions = &quad_positions, .indices = &.{ 0, 1, 7 } }).isWellFormed());
183 try testing.expectEqual(Vec3.init(1, 1, 0), quad.bounds().max);
184 try testing.expectEqual(Vec3.init(-1, -1, -2), quad.bounds().min);
185 }
186
187 test "the scan reports the nearest triangle and the lower index on a shared edge" {
188 const down = Ray{ .origin = Vec3.init(0.5, -0.5, 3), .direction = Vec3.init(0, 0, -1) };
189 const hit = quad.raycast(down, 0, 100).?;
190 try testing.expectEqual(@as(f32, 3), hit.t);
191 try testing.expectEqual(@as(u32, 0), hit.triangle);
192 try testing.expectEqual(@as(u32, 2), quad.raycast(down, 4, 100).?.triangle);
193 try testing.expectEqual(@as(?RayHit, null), quad.raycast(down, 0, 2));
194
195 const diagonal = Ray{ .origin = Vec3.init(0, 0, 3), .direction = Vec3.init(0, 0, -1) };
196 try testing.expectEqual(@as(u32, 0), quad.raycast(diagonal, 0, 100).?.triangle);
197 try testing.expect(quad.raycastAny(diagonal, 0, 100));
198 try testing.expect(!quad.raycastAny(diagonal, 0, 2));
199 }
200
201 test "the scan collects overlaps in index order and flags a full buffer" {
202 var out: [3]u32 = undefined;
203 const ball = Sphere{ .center = Vec3.init(0.5, -0.5, -1), .radius = 1.5 };
204 const all = quad.overlapSphere(ball, &out);
205 try testing.expectEqual(Overlap{ .count = 3, .complete = true }, all);
206 try testing.expectEqualSlices(u32, &.{ 0, 1, 2 }, out[0..3]);
207 const some = quad.overlapSphere(ball, out[0..1]);
208 try testing.expectEqual(Overlap{ .count = 1, .complete = false }, some);
209 const rod = Capsule{ .a = Vec3.init(0.5, -0.5, -3), .b = Vec3.init(0.5, -0.5, -1), .radius = 0.1 };
210 try testing.expectEqual(Overlap{ .count = 1, .complete = true }, quad.overlapCapsule(rod, &out));
211 try testing.expectEqual(@as(u32, 2), out[0]);
212 }
213
214 test "the scan sweeps to the first contact" {
215 const ball = Sphere{ .center = Vec3.init(0.5, -0.5, 2), .radius = 0.5 };
216 const hit = quad.sweepSphere(ball, Vec3.init(0, 0, -6)).?;
217 try testing.expectEqual(@as(f32, 0.25), hit.t);
218 try testing.expectEqual(@as(u32, 0), hit.triangle);
219 const rod = Capsule{ .a = Vec3.init(0.5, -0.5, 2), .b = Vec3.init(0.5, -0.5, 3), .radius = 0.5 };
220 try testing.expectEqual(@as(u32, 0), quad.sweepCapsule(rod, Vec3.init(0, 0, -6)).?.triangle);
221 try testing.expectEqual(@as(?SweepHit, null), quad.sweepSphere(ball, Vec3.init(0, 0, 1)));
222 }