meirbon / rtbvh Goto Github PK

Hey, I think this is a very interesting project! I maintain the bvh crate and I think it'd be super interesting to see a benchmark between this. I suppose yours will be many times faster but I'm very interested to see just how fast.

Issue:

In the environment depicted below, intersection checks (from every origin, in every direction) fail for the two large triangles using the standard BVH implementation. When stepping through the BVH iterator sequentially, the primitives which contain these two triangles are (sometimes) not reached.

I've set up an MRE which constructs a BVH of the 4 triangles in the environment below and then performs intersection checks downwards from positions above the triangles' centers. These intersections should in theory never fail, but they do. The problem occurs non-deterministically, which leads me to believe there is a small bug in the BVH construction step or in the BVH iterator.

Notes:

• 3 triangles have two axis-aligned edges and 1 triangle has one axis-aligned edge.
• All triangles are sufficiently large enough to the point where floating point inaccuracies should not matter.
• I have not tested this environment in the MBVH implementation, since it has been unstable for us in larger environments. For more information refer to @stijn-ucrowds's issue.

How to reproduce:

1. Download the MRE: rtbvh-mre.zip.
2. Run the included test using cargo test -- --nocapture. The test will run for 10 iterations.
3. Observe the intersection assertion failing at a random iteration of the test.

During MBVH construction the algorithm panics.

let bvh = (Builder {
    aabbs: None,
    primitives: triangles.as_slice(),
    primitives_per_leaf: None,
})
    .construct_binned_sah()
    .unwrap_or_default();

let bvh = Mbvh::from(bvh);

thread 'main' panicked at 'Leaf nodes should not be attempted to be split!', C:\Users\User\.cargo\registry\src\github.com-1ecc6299db9ec823\rtbvh-0.5.3\src\mbvh_node.rs:307:13
stack backtrace:
   0: std::panicking::begin_panic<str>
             at C:\Users\User\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:519
   1: rtbvh::mbvh_node::MbvhNode::merge_nodes
             at C:\Users\User\.cargo\registry\src\github.com-1ecc6299db9ec823\rtbvh-0.5.3\src\mbvh_node.rs:307
   2: rtbvh::bvh::Mbvh::construct
             at C:\Users\User\.cargo\registry\src\github.com-1ecc6299db9ec823\rtbvh-0.5.3\src\bvh.rs:373
   3: rtbvh::bvh::{{impl}}::from
             at C:\Users\User\.cargo\registry\src\github.com-1ecc6299db9ec823\rtbvh-0.5.3\src\bvh.rs:419

With the following input triangles.

128.79
-1422.82
0.16
128.5
-1426.88
0.16
128.79
-1426.9067
0.16
129.8
-1422.8629
0.16
128.79
-1422.82
0.16
128.79
-1426.9067
0.16
129.8
-1422.8629
0.16
128.79
-1426.9067
0.16
129.8
-1427
0.16
130.2
-1422.88
0.16
129.8
-1422.8629
0.16
129.8
-1427
0.16
130.2
-1422.88
0.16
129.8
-1427
0.16
130.2
-1423.13
0.16

This being 5 triangles composed of 3 points each composed of 3 components, so:

p0.x
p0.y
p0.z
p1.x
p1.y
p1.z
p2.x
p2.y
p2.z

And then repeat