Mesh connectivity in DHART

[mariuszhermansdorfer]

In my Rhino plugin, there is an option to modify a mesh with a closed curve with defined cut/fill slopes. Here it is in action:

https://www.youtube.com/watch?v=ySkuNJ6hWUI&list=PLaDqvGFC61g2Nlr58WhOtjv9C-9U5t5qY&index=11

Key concepts:

1. Shoot rays from the curve to find intersections with the mesh
2. Create individual meshes for cut & fill
3. Identify and delete all faces within the curve projection on the mesh
4. Patch the hole between the old mesh and the curve projection

Currently I'm traversing a Rhino.Mesh and use its connectivity information. Inspired by our exchange so far and experience with the Embree Raytracer I'm considering transitioning towards Embree's BVHs completely.

Is there a way to perform operations from point 3 within a BVH structure? Ideally, I'd like to identify which triangles intersect with a polyline projected to the mesh AND find all triangles which are within the bounds of the polyline. Geometrically, you could imagine a solid extrusion of the line, which deletes all the faces it intersects:

[cadop]

If I understand correctly, I think there are a few things:

Its a geometry problem more than raytracing, but I guess you are thinking of it like the projection of rays being verts/handles of a spline, and then interpolating between them.

I'm not sure the speed you are dealing with in rhino, but the easiest way (as-is) would be to keep track of triangle centerpoints (e.g. hashtable), and pass to embree as the origin direction and the ray as inverse of the projection (same method as shadow rays). add a bvh mesh of your projection curve (as a mesh). select your triangles based on the ones where the hitid is the mesh id you added. (no need for using primid since you track the triangles in c#).

Or.....

you might want to consider using the nanort (double precision) raytracer if you continue down this route. Besides being more accurate, the entire bvh code is exposed and pretty easy to understand. Its not as fast as embree, but its pretty close (especially with multiprocessing).

Alot (all?) of this will need to be written as new methods in C++ with a new c interface.

• With that said, I would first use AABB to cull most of the mesh being evaluated, which is faster than a BVH traversal.
• I think some bounding algorithm like GJK could be used with the projection direction to get the projected triangles within the view
• maybe something else, but for now would take the center of every triangle and cast a ray in the reversed projection (like shadow rays) to check if it collides.

Need to define:

• What happens if a triangle is within and outside the boundry (and what if its large)
• what if the mesh has undercuts? can it guarantee its not?

i'm pretty sure the patching of the mesh isn't possible with embree. So I guess you would do that in rhino? Otherwise, there is a longer topic to be had for adding mesh utilities to dhart, but it is possible. The API was setup to be modular, which is why when you build it there are a bunch of folders like "spatialstructure" and "graphgenerator", each with their own cmake. We could add another component called "mesh" and build it almost separately from the other packages. It would be the c api that users pass a bvh to and the mesh does its thing. There is one thing I did want to add related to mesh operations, so if you could do the heavy lifting I could help out on the structure.

[cadop]

I think something like this might be more robust for you https://spec.oneapi.io/oneart/0.5-rev-1/embree-spec.html#id147

[cadop]

Or this filter method, gives an example for using alpha texture of a leaf https://spec.oneapi.io/oneart/0.5-rev-1/embree-spec.html#id247

[mariuszhermansdorfer]

Consider this case, green - a single triangle of a much bigger mesh, red - the newly created mesh enclosed by a curve projected onto the terrain mesh:

If I cast rays only from the red vertices, I will miss this face. Casting from the green vertices would find the red mesh but there are potentially more than a million vertices to cast from and even with some AABB checking it'd be expensive.

Is there no bounding box search within the BVH?

[cadop]

Sorry I can't come up with a solution here. I think the links I gave you are the most similar to what you are trying to do. And the more labor intensive version I mentioned originally is what I think you would need to do for resolving the issue of reducing green triangles that collide with red.

You can use embrees BVH to write your own and then do whatever you want (so to your answer, you could use embree), but that takes some effort.

If you are doing mesh operations in rhino maybe there is a way to subsample the outline of the red polygon, remove any triangles it intersects, and then use rhino to find the ring of empty space that was created.

I obviously have a backlog, importantly; finalizing the PR from you on array flattening and the new PR, so I want to prioritize those. When I can get through that I can spend some more time thinking about this.

[mariuszhermansdorfer]

Thanks for sharing your ideas. I’ve been thinking about it and it seems that it might be a case of trying to fit a square peg into a round hole. Embree is great at raytracing but mesh structures exist for a reason and shine in other applications.

Ultimately, I need to introduce other geometric operations which rely on understanding the relationship between faces/edges/vertices of my terrain geometry. Flow analysis, cutting holes and adding boundaries are only a few examples of these.

Rhino.Mesh is robust and has some powerful methods which allow for all the above but it’s not the fastest structure to work with. Hence I’m on the lookout for alternatives to create a real-time experience.

The sculpting demo strips a Rhino.Mesh to the bare minimum and works on flat float arrays directly which are ten fed into an OpenGL pipeline for display. I’ll probably end up doing something similar for the remaining operations.

Still, it would be nice to be able to intersect an embree BVH with an extruded curve. It seems like something which should be doable within the scope of the framework.

But I totally understand your priorities and appreciate your openness to exchange of ideas!