lib/geometry/src/test.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const linear = @import("linear");
4 const geometry = @import("root.zig");
5
6 const Allocator = std.mem.Allocator;
7 const Bvh = geometry.Bvh;
8 const Capsule = geometry.Capsule;
9 const Mesh = geometry.Mesh;
10 const Ray = geometry.Ray;
11 const Sphere = geometry.Sphere;
12 const Storage = geometry.Storage;
13 const Vec3 = linear.Vec3;
14
15 test "geometry package namespace" {
16 std.testing.refAllDecls(geometry);
17 }
18
19 test {
20 _ = @import("bvh.zig");
21 _ = @import("closest.zig");
22 _ = @import("intersect.zig");
23 _ = @import("mesh.zig");
24 _ = @import("primitive.zig");
25 _ = @import("sweep.zig");
26 _ = @import("tolerance.zig");
27 }
28
29 fn settings() hypothesis.Settings {
30 return hypothesis.Settings.quick()
31 .withSeed(0x4745_4f4d_4554_0001)
32 .withSeedFromEnv()
33 .withDatabase("zig-out/hypothesis-failures/geometry");
34 }
35
36 fn drawLane(data: *hypothesis.ConjectureData, bound: f64) !f32 {
37 return @floatCast(try data.drawFloat(-bound, bound));
38 }
39
40 fn drawVec3(data: *hypothesis.ConjectureData, bound: f64) !Vec3 {
41 return .{
42 .x = try drawLane(data, bound),
43 .y = try drawLane(data, bound),
44 .z = try drawLane(data, bound),
45 };
46 }
47
48 /// A mesh with its tree, owning every buffer both borrow.
49 const Fixture = struct {
50 positions: []Vec3,
51 indices: []u32,
52 storage: Storage,
53 bvh: Bvh,
54
55 fn mesh(fixture: Fixture) Mesh {
56 return .{ .positions = fixture.positions, .indices = fixture.indices };
57 }
58
59 fn deinit(fixture: Fixture, gpa: Allocator) void {
60 fixture.storage.free(gpa);
61 gpa.free(fixture.indices);
62 gpa.free(fixture.positions);
63 }
64
65 /// Triangles scattered as clusters or loose shards, some sharing
66 /// vertices with their neighbour and the last one possibly a copy of the
67 /// first, so ties at equal `t` occur.
68 fn draw(data: *hypothesis.ConjectureData, gpa: Allocator) !Fixture {
69 const count: usize = @intCast(try data.drawInteger(1, 64, 1));
70 const spread: f64 = if (try data.drawBoolean()) 0.5 else 4;
71 const positions = try gpa.alloc(Vec3, count * 3);
72 errdefer gpa.free(positions);
73 const indices = try gpa.alloc(u32, count * 3);
74 errdefer gpa.free(indices);
75 for (0..count) |triangle| {
76 const center = try drawVec3(data, 10);
77 for (0..3) |corner| {
78 const slot = triangle * 3 + corner;
79 positions[slot] = center.add(try drawVec3(data, spread));
80 indices[slot] = @intCast(slot);
81 }
82 if (triangle > 0 and try data.drawBoolean()) indices[triangle * 3] = @intCast(triangle * 3 - 1);
83 }
84 if (count > 1 and try data.drawBoolean()) @memcpy(indices[(count - 1) * 3 ..], indices[0..3]);
85 return build(gpa, positions, indices);
86 }
87
88 fn build(gpa: Allocator, positions: []Vec3, indices: []u32) !Fixture {
89 const mesh_view = Mesh{ .positions = positions, .indices = indices };
90 const storage = try Storage.alloc(gpa, mesh_view.triangleCount());
91 return .{ .positions = positions, .indices = indices, .storage = storage, .bvh = Bvh.build(mesh_view, storage) };
92 }
93
94 /// A point on a drawn triangle, so queries aimed at it tend to hit.
95 fn drawTarget(fixture: Fixture, data: *hypothesis.ConjectureData) !Vec3 {
96 const count = fixture.mesh().triangleCount();
97 const index: usize = @intCast(try data.drawInteger(0, count - 1, 0));
98 const triangle = fixture.mesh().triangle(index);
99 const u: f32 = @floatCast(try data.drawFloat(0, 1));
100 const v: f32 = @floatCast(try data.drawFloat(0, 1 - @as(f64, u)));
101 return triangle.a.add(triangle.b.sub(triangle.a).scale(u)).add(triangle.c.sub(triangle.a).scale(v));
102 }
103 };
104
105 const RaycastAgrees = struct {
106 pub fn property(data: *hypothesis.ConjectureData, gpa: Allocator) !void {
107 const fixture = try Fixture.draw(data, gpa);
108 defer fixture.deinit(gpa);
109 const mesh = fixture.mesh();
110 const origin = try drawVec3(data, 16);
111 const aim = if (try data.drawBoolean()) try fixture.drawTarget(data) else try drawVec3(data, 16);
112 const direction = aim.sub(origin).normalized(1e-3) orelse return;
113 const ray = Ray{ .origin = origin, .direction = direction };
114 const t_min: f32 = @floatCast(try data.drawFloat(0, 8));
115 const t_max: f32 = t_min + @as(f32, @floatCast(try data.drawFloat(0, 64)));
116 var stats = geometry.Stats{};
117 try std.testing.expectEqual(mesh.raycast(ray, t_min, t_max), try fixture.bvh.raycast(ray, t_min, t_max, &stats));
118 try std.testing.expectEqual(mesh.raycastAny(ray, t_min, t_max), try fixture.bvh.raycastAny(ray, t_min, t_max, null));
119 try std.testing.expect(stats.nodes_visited <= fixture.bvh.nodes.len);
120 try std.testing.expect(stats.triangles_tested <= mesh.triangleCount());
121 }
122 };
123
124 const OverlapAgrees = struct {
125 pub fn property(data: *hypothesis.ConjectureData, gpa: Allocator) !void {
126 const fixture = try Fixture.draw(data, gpa);
127 defer fixture.deinit(gpa);
128 const mesh = fixture.mesh();
129 const capacity: usize = @intCast(try data.drawInteger(0, 8, 8));
130 var scan_out: [8]u32 = undefined;
131 var tree_out: [8]u32 = undefined;
132 const center = (try fixture.drawTarget(data)).add(try drawVec3(data, 3));
133 const radius: f32 = @floatCast(try data.drawFloat(0, 4));
134 const sphere = Sphere{ .center = center, .radius = radius };
135 const scan = mesh.overlapSphere(sphere, scan_out[0..capacity]);
136 const tree = try fixture.bvh.overlapSphere(sphere, tree_out[0..capacity], null);
137 try std.testing.expectEqual(scan, tree);
138 try std.testing.expectEqualSlices(u32, scan_out[0..scan.count], tree_out[0..tree.count]);
139
140 const capsule = Capsule{ .a = center, .b = center.add(try drawVec3(data, 4)), .radius = radius };
141 const scan_capsule = mesh.overlapCapsule(capsule, scan_out[0..capacity]);
142 const tree_capsule = try fixture.bvh.overlapCapsule(capsule, tree_out[0..capacity], null);
143 try std.testing.expectEqual(scan_capsule, tree_capsule);
144 try std.testing.expectEqualSlices(u32, scan_out[0..scan_capsule.count], tree_out[0..tree_capsule.count]);
145 }
146 };
147
148 const SweepAgrees = struct {
149 pub fn property(data: *hypothesis.ConjectureData, gpa: Allocator) !void {
150 const fixture = try Fixture.draw(data, gpa);
151 defer fixture.deinit(gpa);
152 const mesh = fixture.mesh();
153 const start = try drawVec3(data, 16);
154 const aim = if (try data.drawBoolean()) try fixture.drawTarget(data) else try drawVec3(data, 16);
155 const reach: f32 = @floatCast(try data.drawFloat(0, 2));
156 const displacement = aim.sub(start).scale(reach);
157 const radius: f32 = @floatCast(try data.drawFloat(0, 2));
158 const sphere = Sphere{ .center = start, .radius = radius };
159 try std.testing.expectEqual(mesh.sweepSphere(sphere, displacement), try fixture.bvh.sweepSphere(sphere, displacement, null));
160 const capsule = Capsule{ .a = start, .b = start.add(try drawVec3(data, 3)), .radius = radius };
161 try std.testing.expectEqual(mesh.sweepCapsule(capsule, displacement), try fixture.bvh.sweepCapsule(capsule, displacement, null));
162 }
163 };
164
165 const BuildIsDeterministic = struct {
166 pub fn property(data: *hypothesis.ConjectureData, gpa: Allocator) !void {
167 const fixture = try Fixture.draw(data, gpa);
168 defer fixture.deinit(gpa);
169 const again = try Storage.alloc(gpa, fixture.mesh().triangleCount());
170 defer again.free(gpa);
171 const rebuilt = Bvh.build(fixture.mesh(), again);
172 try std.testing.expectEqualSlices(u8, std.mem.sliceAsBytes(fixture.bvh.nodes), std.mem.sliceAsBytes(rebuilt.nodes));
173 try std.testing.expectEqualSlices(u32, fixture.bvh.order, rebuilt.order);
174 try std.testing.expectEqual(fixture.bvh.depth, rebuilt.depth);
175 }
176 };
177
178 test "property: tree raycasts answer as the scan does" {
179 try hypothesis.checkNamed(RaycastAgrees, "geometry-raycast-agrees", settings());
180 }
181
182 test "property: tree overlaps answer as the scan does" {
183 try hypothesis.checkNamed(OverlapAgrees, "geometry-overlap-agrees", settings());
184 }
185
186 test "property: tree sweeps answer as the scan does" {
187 try hypothesis.checkNamed(SweepAgrees, "geometry-sweep-agrees", settings());
188 }
189
190 test "property: the same mesh builds the same tree" {
191 try hypothesis.checkNamed(BuildIsDeterministic, "geometry-build-deterministic", settings());
192 }
193
194 const Draw = struct {
195 random: std.Random,
196
197 fn lane(draw: Draw, bound: f32) f32 {
198 return (draw.random.float(f32) * 2 - 1) * bound;
199 }
200
201 fn vec(draw: Draw, bound: f32) Vec3 {
202 return Vec3.init(draw.lane(bound), draw.lane(bound), draw.lane(bound));
203 }
204
205 fn below(draw: Draw, n: usize) usize {
206 return draw.random.uintLessThan(usize, n);
207 }
208 };
209
210 fn round(v: Vec3) Vec3 {
211 return Vec3.init(@round(v.x), @round(v.y), @round(v.z));
212 }
213
214 test "lattice, flat and collapsed meshes at scales to 20000 answer as the scan does" {
215 const gpa = std.testing.allocator;
216 var prng = std.Random.DefaultPrng.init(0x4745_4f4d_4554_0002);
217 const draw = Draw{ .random = prng.random() };
218 for (0..48) |mesh_round| {
219 const scale: f32 = switch (mesh_round % 4) {
220 0 => 1,
221 1 => 30,
222 2 => 3000,
223 else => 20000,
224 };
225 const lattice = mesh_round % 3 == 0;
226 const flat = mesh_round % 5 == 0;
227 const count = 1 + draw.below(400);
228 const positions = try gpa.alloc(Vec3, count * 3);
229 const indices = try gpa.alloc(u32, count * 3);
230 for (0..count) |triangle| {
231 var center = draw.vec(10);
232 if (flat) center.z = 0;
233 for (0..3) |corner| {
234 var p = center.add(draw.vec(2));
235 if (flat) p.z = 0;
236 if (lattice) p = round(p);
237 const slot = triangle * 3 + corner;
238 const shared = lattice and triangle > 0 and draw.random.boolean();
239 positions[slot] = p.scale(scale / 10);
240 indices[slot] = @intCast(if (shared) slot - 3 else slot);
241 }
242 }
243 const fixture = try Fixture.build(gpa, positions, indices);
244 defer fixture.deinit(gpa);
245 const mesh = fixture.mesh();
246 try std.testing.expect(fixture.bvh.depth < geometry.depth_limit);
247 var scan_out: [12]u32 = undefined;
248 var tree_out: [12]u32 = undefined;
249 for (0..64) |_| {
250 const target = mesh.triangle(draw.below(count)).centroid();
251 var origin = draw.vec(scale * 1.5);
252 if (draw.below(4) == 0) origin.z = target.z;
253 if (lattice and draw.random.boolean()) origin = round(origin);
254 const aim = switch (draw.below(6)) {
255 0 => Vec3.init(0, 0, -1),
256 1 => Vec3.init(1, 0, 0),
257 else => target.sub(origin),
258 };
259 const direction = aim.normalized(0) orelse continue;
260 const ray = Ray{ .origin = origin, .direction = direction };
261 const t_max = scale * 10;
262 try std.testing.expectEqual(mesh.raycast(ray, 0, t_max), try fixture.bvh.raycast(ray, 0, t_max, null));
263 try std.testing.expectEqual(mesh.raycastAny(ray, 0, t_max), try fixture.bvh.raycastAny(ray, 0, t_max, null));
264
265 const radius = draw.random.float(f32) * scale * 0.2;
266 const displacement = target.sub(origin).scale(draw.random.float(f32) * 1.5);
267 const ball = Sphere{ .center = origin, .radius = radius };
268 try std.testing.expectEqual(mesh.sweepSphere(ball, displacement), try fixture.bvh.sweepSphere(ball, displacement, null));
269 const rod = Capsule{ .a = origin, .b = origin.add(draw.vec(scale * 0.3)), .radius = radius };
270 try std.testing.expectEqual(mesh.sweepCapsule(rod, displacement), try fixture.bvh.sweepCapsule(rod, displacement, null));
271
272 const near = Sphere{ .center = target, .radius = draw.random.float(f32) * scale * 0.3 };
273 const scan = mesh.overlapSphere(near, &scan_out);
274 try std.testing.expectEqual(scan, try fixture.bvh.overlapSphere(near, &tree_out, null));
275 try std.testing.expectEqualSlices(u32, scan_out[0..scan.count], tree_out[0..scan.count]);
276 const stick = Capsule{ .a = target, .b = target.add(draw.vec(scale * 0.3)), .radius = near.radius };
277 const scan_stick = mesh.overlapCapsule(stick, &scan_out);
278 try std.testing.expectEqual(scan_stick, try fixture.bvh.overlapCapsule(stick, &tree_out, null));
279 try std.testing.expectEqualSlices(u32, scan_out[0..scan_stick.count], tree_out[0..scan_stick.count]);
280 }
281 }
282 }