remesh 0.0.5

Isotropic remeshing library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316

// SPDX-License-Identifier: MIT OR Apache-2.0
// Copyright (c) 2025 lacklustr@protonmail.com https://github.com/eadf

use super::*;
use crate::common::sealed::ScalarType;
use std::f32;
use vector_traits::glam::{Vec3, Vec3A};

fn make_triangle<S: ScalarType>(v0: S::Vec3, v1: S::Vec3, v2: S::Vec3) -> Triangle<S> {
    let edge0 = v1 - v0;
    let edge1 = v2 - v0;
    let normal = edge0.cross(edge1).normalize();

    Triangle { v0, v1, v2, normal }
}

#[test]
fn test_empty_bvh() {
    let bvh = StaticBVH::<f32>::new(&[], &[]);
    let result = bvh.closest_point(Vec3::ZERO, Vec3A::ZERO, -1.0);
    assert!(result.is_none());
}

#[test]
fn test_single_triangle() {
    // Triangle in XY plane at z=0
    let tri = make_triangle(
        Vec3::new(0.0, 0.0, 0.0),
        Vec3::new(1.0, 0.0, 0.0),
        Vec3::new(0.0, 1.0, 0.0),
    );

    let bvh = StaticBVH::<f32>::new_from_triangles(vec![tri.clone()]);

    // Point above the triangle should project down to it
    let query = Vec3::new(0.25, 0.25, 1.0);
    let result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Should be close to (0.25, 0.25, 0.0)
    assert!(
        (result.z).abs() < 0.001,
        "result: {:?} distance a:{}, distance b:{}, distance c:{}",
        result,
        query.distance(tri.v0),
        query.distance(tri.v1),
        query.distance(tri.v2)
    ); // this passes (but should not)
    assert!(
        (result.x - 0.25).abs() < 0.001,
        "result: {:?} distance a:{}, distance b:{}, distance c:{}",
        result,
        query.distance(tri.v0),
        query.distance(tri.v1),
        query.distance(tri.v2)
    ); // this fails with result: Vec3(0.0, 0.0, 0.0)
    assert!(
        (result.y - 0.25).abs() < 0.001,
        "result: {:?} distance a:{}, distance b:{}, distance c:{}",
        result,
        query.distance(tri.v0),
        query.distance(tri.v1),
        query.distance(tri.v2)
    );
}

#[test]
fn test_project_to_triangle_center() {
    let tri = make_triangle(
        Vec3::new(-1.0, -1.0, 0.0),
        Vec3::new(1.0, -1.0, 0.0),
        Vec3::new(0.0, 1.0, 0.0),
    );

    let bvh = StaticBVH::<f32>::new_from_triangles(vec![tri]);

    // Point directly above center
    let query = Vec3::new(0.0, 0.0, 5.0);
    let result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Should project to z=0
    assert!((result.z).abs() < 0.001);
}

#[test]
fn test_project_to_triangle_vertex() {
    let tri = make_triangle(
        Vec3::new(0.0, 0.0, 0.0),
        Vec3::new(1.0, 0.0, 0.0),
        Vec3::new(0.0, 1.0, 0.0),
    );

    let bvh = StaticBVH::<f32>::new_from_triangles(vec![tri]);

    // Point near a vertex
    let query = Vec3::new(-1.0, -1.0, 0.0);
    let result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Should snap to origin vertex
    assert!(result.distance(Vec3::ZERO) < 0.001);
}

#[test]
fn test_project_to_triangle_edge() {
    let tri = make_triangle(
        Vec3::new(0.0, 0.0, 0.0),
        Vec3::new(1.0, 0.0, 0.0),
        Vec3::new(0.0, 1.0, 0.0),
    );

    let bvh = StaticBVH::<f32>::new_from_triangles(vec![tri]);

    // Point outside triangle, nearest to an edge
    let query = Vec3::new(0.5, -1.0, 0.0);
    let result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Should project to the edge between (0,0,0) and (1,0,0)
    assert!((result.y).abs() < 0.001);
    assert!((result.z).abs() < 0.001);
    assert!(result.x >= 0.0 && result.x <= 1.0);
}

#[test]
fn test_multiple_triangles_closest() {
    // Two triangles at different Z heights
    let tri1 = make_triangle(
        Vec3::new(0.0, 0.0, 0.0),
        Vec3::new(1.0, 0.0, 0.0),
        Vec3::new(0.0, 1.0, 0.0),
    );

    let tri2 = make_triangle(
        Vec3::new(0.0, 0.0, 5.0),
        Vec3::new(1.0, 0.0, 5.0),
        Vec3::new(0.0, 1.0, 5.0),
    );

    let bvh = StaticBVH::<f32>::new_from_triangles(vec![tri1, tri2]);

    // Point closer to first triangle
    let query = Vec3::new(0.25, 0.25, 0.5);
    let result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Should project to tri1 at z=0
    assert!((result.z).abs() < 0.001);

    // Point closer to second triangle
    let query2 = Vec3::new(0.25, 0.25, 4.5);
    let result2 = bvh.closest_point(query2, Vec3A::ZERO, -1.0).unwrap().0;

    // Should project to tri2 at z=5
    assert!((result2.z - 5.0).abs() < 0.001);
}

#[test]
fn test_separated_triangles() {
    // Two triangles far apart
    let tri1 = make_triangle(
        Vec3::new(-10.0, 0.0, 0.0),
        Vec3::new(-9.0, 0.0, 0.0),
        Vec3::new(-10.0, 1.0, 0.0),
    );

    let tri2 = make_triangle(
        Vec3::new(10.0, 0.0, 0.0),
        Vec3::new(11.0, 0.0, 0.0),
        Vec3::new(10.0, 1.0, 0.0),
    );

    let bvh = StaticBVH::<f32>::new_from_triangles(vec![tri1, tri2]);

    // Point near first triangle
    let query = Vec3::new(-10.0, 0.0, 0.0);
    let result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Should be very close to first triangle
    let dist_to_tri1 = result.distance(Vec3::new(-10.0, 0.0, 0.0));
    assert!(dist_to_tri1 < 0.001);
}

#[test]
fn test_many_triangles() {
    // Create a grid of triangles
    let mut triangles = Vec::new();

    for i in 0..10 {
        for j in 0..10 {
            let x = i as f32;
            let y = j as f32;

            // Two triangles per grid cell
            triangles.push(make_triangle(
                Vec3::new(x, y, 0.0),
                Vec3::new(x + 1.0, y, 0.0),
                Vec3::new(x, y + 1.0, 0.0),
            ));

            triangles.push(make_triangle(
                Vec3::new(x + 1.0, y, 0.0),
                Vec3::new(x + 1.0, y + 1.0, 0.0),
                Vec3::new(x, y + 1.0, 0.0),
            ));
        }
    }

    let bvh = StaticBVH::<f32>::new_from_triangles(triangles);

    // Query point above the grid
    let query = Vec3::new(5.5, 5.5, 10.0);
    let result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Should project down to z=0
    assert!((result.z).abs() < 0.001);
    assert!((result.x - 5.5).abs() < 0.001);
    assert!((result.y - 5.5).abs() < 0.001);
}

#[test]
fn test_aabb_union() {
    let aabb1 = Aabb::<f32>::new(Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 1.0, 1.0));

    let aabb2 = Aabb::<f32>::new(Vec3::new(0.5, 0.5, 0.5), Vec3::new(2.0, 2.0, 2.0));

    let union = aabb1.union(&aabb2);

    assert_eq!(union.min, Vec3::new(0.0, 0.0, 0.0));
    assert_eq!(union.max, Vec3::new(2.0, 2.0, 2.0));
}

#[test]
fn test_aabb_distance_inside() {
    let aabb = Aabb::<f32>::new(Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 1.0, 1.0));

    // Point inside the Aabb
    let point = Vec3::new(0.5, 0.5, 0.5);
    let dist = aabb.distance_sq(point);

    // Distance should be 0
    assert_eq!(dist, 0.0);
}

#[test]
fn test_aabb_distance_outside() {
    let aabb = Aabb::<f32>::new(Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 1.0, 1.0));

    // Point outside the Aabb
    let point = Vec3::new(2.0, 0.5, 0.5);
    let dist = aabb.distance_sq(point);

    // Distance should be 1.0 (squared distance to closest face)
    assert!((dist - 1.0).abs() < 0.001);
}

#[test]
fn test_projection_preserves_distance_to_plane() {
    // Create a simple triangle in XY plane
    let tri = make_triangle::<f32>(
        Vec3::new(-5.0, -5.0, 0.0),
        Vec3::new(5.0, -5.0, 0.0),
        Vec3::new(0.0, 5.0, 0.0),
    );

    // Test the raw projection function
    let point = Vec3::new(0.0, 0.0, 3.0);
    let projected = project_point_to_triangle::<f32>(point, &tri);

    // Should project straight down to z=0
    assert!((projected.z).abs() < 0.001);
    assert!((projected.x).abs() < 0.001);
    assert!((projected.y).abs() < 0.001);
}

#[test]
fn test_bvh_matches_brute_force() {
    // Create some random triangles
    let triangles = vec![
        make_triangle(
            Vec3::new(0.0, 0.0, 0.0),
            Vec3::new(1.0, 0.0, 0.0),
            Vec3::new(0.0, 1.0, 0.0),
        ),
        make_triangle(
            Vec3::new(2.0, 2.0, 0.0),
            Vec3::new(3.0, 2.0, 0.0),
            Vec3::new(2.0, 3.0, 0.0),
        ),
        make_triangle(
            Vec3::new(-2.0, -2.0, 1.0),
            Vec3::new(-1.0, -2.0, 1.0),
            Vec3::new(-2.0, -1.0, 1.0),
        ),
    ];

    let bvh = StaticBVH::<f32>::new_from_triangles(triangles.clone());

    // Test query point
    let query = Vec3::new(1.0, 1.0, 5.0);

    // BVH result
    let bvh_result = bvh.closest_point(query, Vec3A::ZERO, -1.0).unwrap().0;

    // Brute force result
    let mut brute_force_result = Vec3::ZERO;
    let mut min_dist = f32::MAX;

    for tri in &triangles {
        let proj = project_point_to_triangle(query, tri);
        let dist = query.distance_squared(proj);
        if dist < min_dist {
            min_dist = dist;
            brute_force_result = proj;
        }
    }

    // Results should match
    assert!(bvh_result.distance(brute_force_result) < 0.001);
}