BVH for ray-triangle intersection tests

[paulmelis]

Here's an initial implementation (C++ parts only, and 3 lines of C#) of using a bounding-volume hierarchy for ray-triangle intersection testing. This is based on existing BVH code I had laying around, plus some inspiration from Jacco Bikker's blog series on BVH construction (see bvh.cpp comments). It contains a fair amount of tracing printf()s, as a code such as this is challenging to debug otherwise, so for now those are best to leave in (I'm sure we'll find bugs ;-)).

I also added a small standalone C++ test for checking with different models and rays, but it's mostly for debugging right now. The next step would be to add the C# layer for easier testing, i.e. interactive ray casting in 3D, possibly as part of StereoKitTest.

This has only been tested with a few 3D models, but ranging from small ones to complex ones (up to 500k triangles, and even a 24M triangle model). Construction seems fairly quick, given that it's not very optimized (models of up to 50k triangles in less than 50ms). Construction has had more testing than intersection testing, as the latter can be better done interactively (as mentioned above).

One thing I haven't figured out is why the added model_ray_intersect_bvh() does not return the same results as using mesh_ray_intersect() on each of the submeshes and taking the closest hit. In most models I tested the subparts do not have a non-identity transform, so that should not influence the outcome, yet it does.

[maluoi]

This looks really awesome! I'm very excited about this, and I'm hoping to give this a hands-on spin a little later! :D

Here's a few notes just from reading over the code, hopefully this doesn't come across as picky.

• The SK codebase almost exclusively uses POD (Plain Old Data, no constructors, deconstructors and preferably no methods) for types, and I'd love it if you could match this with your code! A decent reference for this might be the rect_atlas_t.
• For memory allocation, sk_malloc and free rather than new and delete, though I believe the few new/delete calls you do have there are related to non-POD types.
• With boundingbox, did you consider extending bounds_t to work for this scenario? There's a lot of overlap there, but I know bounds_t is center + dimensions, and it looks like boundingbox is min corner + max corner which may have perf implications.
• I'd be quite happy to make this stuff the default! Just go with mesh/model_ray_intersect rather than mesh_ray_intersect_bvh :) I'll work on smoothing out any hitches with future async mesh work.
• I actually rather like the format of your test project, that's a pretty neat way to do it! Feel free to put something interactive into StereoKitCTest too, it'll probably get a bit more traffic and testing there!

[paulmelis]

Here's a few notes just from reading over the code, hopefully this doesn't come across as picky.

Not at all, it's your code base :) I tried to match the style and constructs I saw, but can probably fix most of the things you mention.

The SK codebase almost exclusively uses POD (Plain Old Data, no constructors, deconstructors and preferably no methods) for types, and I'd love it if you could match this with your code! A decent reference for this might be the rect_atlas_t.

Okay, that should be doable. Is the reason for this choice so you can easily interface to C, without having to build another API layer?

For memory allocation, sk_malloc and free rather than new and delete, though I believe the few new/delete calls you do have there are related to non-POD types.

I might need a bit more info on which to use for what, having not looked closely into those memory routines (nor did I see comments ;-)). For example, how would you go about allocating an array of structs where each element would normally get initialized by the default constructor?

With boundingbox, did you consider extending bounds_t to work for this scenario? There's a lot of overlap there, but I know bounds_t is center + dimensions, and it looks like boundingbox is min corner + max corner which may have perf implications.

Yes, I looked at that, and similar for extending vec3 for the indexing by axis stuff. The latter is a bit tricky to do efficiently without changing the underlying data to a 3-array instead of an x,y,z struct. So I would prefer more to further optimize the boundingbox struct specifically for BVH usage, and possibly use a local float3 or something, as that will ensure we can keep up performance. Although, all in all, it's a bit hard to judge any performance impact without testing. I guess there's also a bit of personal bias there as well as I'm mostly interested in using this on large (1M+ triangles) meshes, where performance will matter :)

I'd be quite happy to make this stuff the default! Just go with mesh/model_ray_intersect rather than mesh_ray_intersect_bvh :) I'll work on smoothing out any hitches with future async mesh work.

One reason to keep the current methods around (just for now) is for easy checks on correctness of the BVH stuff. The intersection results should match, as a BVH is purely a method for speeding up the queries.

I actually rather like the format of your test project, that's a pretty neat way to do it! Feel free to put something interactive into StereoKitCTest too, it'll probably get a bit more traffic and testing there!

Right, but for that I need to work on the C# layer and I need to check how easy it is to build SK from source under visual studio. I think I've only done that once so far. Anything specific to watch out for in that process?

[maluoi]

POD

POD types have the advantage of being a lot more clear about what's happening! You can be guaranteed there's no hidden vtable pointers, nothing weird happening on creation or copy, memcpy is a lot safer, stuff like that. The codebase also assumes that types are POD, and so using non-POD may cause issues when playing together with that code.

I also have at the back of my mind that it might be nice to make StereoKit properly just C rather than the C/C++ hybrid that it is, but that may just be wishful thinking.

Memory

If you're sticking to POD, then it's a little easier to avoid new/delete! I generally strive to design structures that work correctly when zero initialized ( memset(data, 0, sizeof(data)) ), but it's not always possible. It just takes a little bit of extra work.

quat* rots = sk_malloc_t(quat, 10);
for (int32_t i=0; i<10; i++)
    rots[i] = quat_identity;
free(rots);

SK's memory functions are basically the same as normal C stuff, just with some macro wrappers to make it a little easier. sk_malloc and sk_realloc are wrappers on malloc and realloc that allow me to do some light memory debugging if I want to. sk_malloc_zero is for convenience, and will memset to 0 after allocation.

The _t versions of these functions are macro wrappers that also handle type conversion, and makes the code a little less messy :) Otherwise the above becomes quat* rots = (quat*)sk_malloc(sizeof(quat) * 10);

StereoKitCTest

So there is actually a C++ equivalent of StereoKitTest, no C# involved! It has a similar sort of structure to it, where you can have a demo_topic.h/cpp per subject. Only difference is no reflection, so you still have to register the demo over in main.cpp manually, which is easy enough :)

It's not a 1:1 match with the C# test project, and the samples there tend to be a lot less polished. I use it a fair bit for testing out APIs before I commit to something and write up the C# side of it, faster to iterate with!

And then it's also already hooked up to the cmake file too.

Misc

I am totally down with a boundingbox specialized for BVH performance :) There are some SK math bits that are tied into DirectXMath now and again, not sure if they fall into these code paths or not, but those often benefit from SIMD implementations.

[paulmelis]

@maluoi I've done some more work on this, including adding an example in StereoKitCTest.

One issue I'm trying to figure out is why I get an incorrect intersection point when intersecting a ray with a transformed model. I use the model pose to compute the inverse transform matrix, in order to transform the world-space ray into model-space. Yet, I get incorrect results, both with the new BVH code, but also when using the existing model_ray_intersect(). Perhaps I'm missing something fundamental in how poses/transforms are handled in SK? Of course, the intersection point is in model-space coordinates, so needs to be transformed back to world-space for correct display.

[maluoi]

Awesome! Suuuuper exciting! :D I'm doing MR Dev Days stuff all day today, but I'll take a good look tomorrow :)

[paulmelis]

Alright, I've added a few more things in the StereoKitCTest example, including highlighting the intersected triangle (needed to add a model_... method to the API for this).

One thing I haven't figured out is that although the intersection point shown always seems correct (indicating the BVH intersection works correctly) the highlighted triangle isn't always correct. For example, in demo_bvh.cpp it currently loads Radio.glb and if you move the ray handles around you can clearly see the green triangle highlight does not match the intersection point along the ray (shown as a small sphere). Yet, if you change the example to load suzanne.obj then both intersection point and triangle do align. Both those models are a single mesh subset, but I suspect the extra transforms on nodes in Radio.glb are causing the issue. As I based the BVH routine on model_ray_intersect I assume that handles those transforms correctly, but I may need to check again.

[maluoi]

Just tried this out on a model with 1.6 million tris, and it really takes it like a champ! That is slick, really excellent work! :)

I'm also noticing that this code does intersect with backfaces, which on further inspection, even my own code did backface intersection as well! That might actually be something we want to either avoid, or make optional.

[maluoi]

While algorithm may not be as expensive as windows.h, it's still up there as one of the more pricey #includes! I'd recommend using sk_math.h for mini and maxi and math.h for fmaxf and fminf. I usually just write out swap, but I also wouldn't mind if a swap ends out in sk_math.h

[paulmelis]

I fixed the use of <algorithm> and related remarks you made.

Regarding the intersection test currently ignoring facing, it depends a bit on the usage if that's preferred, so I'd definitely want to keep the option to always intersect regardless of facing. E.g. my current interest in this code is intersection testing for teleporting, and I'm mostly using photogrammetry models that are not nicely closed surfaces. So I render them without back-face culling and would want to allow intersection testing on both faces. But maybe in the general case having the optimization to ignore back-facing triangles is a good default.

[paulmelis]

By the way, I've been trying to get a VS build to work for this code, but it just keeps erroring on me (seemingly unrelated to my code). In general, I'm a bit confused as to how the SK build system is organized, especially in relation to CMake usage and things like the physics code. I read somewhere that the react library would be cloned and built automatically once, but that's one of the things that keeps going wrong in my builds (and I definitely have cmake installed and on PATH). And are the VS project files supposed to be managed by hand? As I noticed the BVH-related files being listed in the StereoKitC_UWP project, but I definitely did not place them there myself. Or is there some VS project generation done based on the CMake files? Is there a description somewhere of the build system with a bit of detail?

[maluoi]

So I render them without back-face culling and would want to allow intersection testing on both faces. But maybe in the general case having the optimization to ignore back-facing triangles is a good default.

Yeah, this all sounds pretty sensible. Thinking about this a little more specifically, it might be good to have the option be the Cull enum, so people can just pass the relevant Material's Cull value along!

Personally, when I think about photogrammetry, I worry about the user getting stuck outside of the mesh, or getting inside the mesh in the first place! Which is why I kinda prefer ignoring backfaces :D So, definitely a range of valid perspectives here.

With respect to the VS build, there's something funky in there recently that I've been hunting down! I haven't managed to smooth it over, but it's related to reactphysics3d again. Since Visual Studio has no dependency management tools for git repositories, I've kinda had to replicate some of that "clone and build" pipeline with powershell :( In Visual Studio, the powershell invocation happens in the "pre-build events". Normally this works relatively well, but I'm not a build expert and writing all that via powershell has been an issue prone adventure. You could try deleting the /Tools/oxr_current.txt file to force an OpenXR/reactphysics3d rebuild, but I'm not 100% if that'll fix things.

I'm still looking for a better option for doing this. I've been looking a bit at vcpkg, or possibly moving C# and the Windows dev experience over to pure cmake, but nothing is really looking like a silver bullet.

[paulmelis]

Yeah, this all sounds pretty sensible. Thinking about this a little more specifically, it might be good to have the option be the Cull enum, so people can just pass the relevant Material's Cull value along!

I'd like to use cull_back as default for the cull parameter, which leads to either this

bool32_t mesh_ray_intersect (mesh_t mesh, ray_t model_space_ray, ray_t* out_pt, uint32_t* out_start_inds sk_default(nullptr), cull_ cull_mode sk_default(cull_back));

or this

bool32_t mesh_ray_intersect (mesh_t mesh, ray_t model_space_ray, ray_t* out_pt, cull_ cull_mode sk_default(cull_back), uint32_t* out_start_inds sk_default(nullptr));

I prefer the latter, as I assume the culling option to be used more than the output indices one.

But it seems in stereokit.h that cull_ is only defined after the mesh_... routines (with the material stuff) and I need it earlier. Suggestions on how to approach that? I can move the cull_ enum up in the header?

[maluoi]

I'd prefer the first signature for SK, for compatibility reasons! The second one I'd consider to be a breaking change, even if I also do like it a little more. I'd recommend adding a TODO comment mentioning parameter reordering for v0.4 so it gets reconsidered next time we introduce breaking changes :) In C# we can safely add an overload in the second order, which is not a breaking change there!

And yeah, feel free to shift cull_ up, there's a section at the top with a number of initialization and shared enums!

[paulmelis]

I guess the culling is one of the last things I needed to add. Plus I guess the bounding box class still needs to become a POD type.

[paulmelis]

Okay, I managed to finally get StereoKitCTest compiling on the win10 system that has our XR-3 attached. This allowed some more interactive testing of the BVH intersection with larger models. All intersections (including the different cull modes) seem to be correct and indeed quite fast even for large models. So I guess that completes this particular pull request. We can always revisit/optimize stuff later on :)

[maluoi]

Okay perfect! I'll take this for a spin later this evening and get it merged! Thanks a lot for this feature, I'm really excited about using it :D

I guess I'll also noodle around and see about the public C# API. It's pretty likely that I'll replace the _intersect function entirely with your new _intersect_bvh functions. When I do it, may depend a bit on when and how I set up the async pipeline for mesh processing, we'll see!