Cascaded Booleans - intermediate mesh repair possible?

[starseeker]

Hi! In your paper, you mention that Diazzi and Attene'a approach solved the robustness problem for cascaded booleans by "implicitly repairing the input during the process" but doing so introduced a performance penalty. Is such an approach possible with your pipeline for applications that can afford to be non-interactive? Or, if possible in theory, would the difficulty of doing so be comparable to that of solving the cascading for indirect predicates problem?

For context - the potential application I'm interested in is evaluation of complex CSG boolean trees used to define complex models in the BRL-CAD computer aided design software package - we convert implicit primitives to meshes (when the primitives aren't already meshes) and then attempt to evaluate the booleans on the meshes. Each intermediate mesh is then used as an input for parent CSG operations - which, unless I'm mistaken, constitutes a classic example of cascading booleans. As expected, our current implementation encounters robustness issues, and I'm very interested in whether your research can be used to improve the outcomes of our use case. Since this evaluation is normally done during a conversion step we can afford (within reason) non-interactivity for the sake of robustness. Before doing a deep dive into the reference code, I thought it might be worth asking if a) the elements to do a repair step are already present in cinolib or one of the other supporting codes b) if not, what approach you would recommend, and c) if you have any sense of how difficult such a repair step would be to implement.

Thanks for your time and for making a very interesting effort available!

[mlivesu]

hi! thanks for the interest in our research. Indeed, the scenario that you described is a case of cascaded boolean, because the output of the boolean operation at time t becomes the input for the subsequent boolean operation at time t+1.

I feel there is some confusion between being robust in the computation of booleans and being robust against possibly defective input meshes passed to the boolean operator. These are two different things. Specifically:

• the code in this repository computes booleans robustly, but it assumes that the input meshes are always well formed (manifold watertight meshes with a coherent surface orientation and no self intersections). If these assumptions do not hold, the algorithm may not work as expected

• Diazzi and Attene's work is robust against possibly ill-defined input meshes. For example, if the input meshes are not watertight or they contain self intersections, the program would still perform as expected. The price to pay for this feature is using an explicit volume mesh, with consequent slowdown

Cascading is another beast. The issue with cascading has to do with the fact that the output of a boolean operator contains intersection points that are only implicitly represented, because their coordinates cannot be represented exactly into the floating point system of your computer. Both algorithms mentioned above use the Attene's Indirect Predicates to represent such points "indirectly", that is, memorizing what input elements generated the intersection, and then using only this information during computation. Unfortunately, the Indirect Predicates do not permit to construct a new implicit point as the intersection of mesh elements that already contain some other implicit point (this is exactly what would happen if you cascade), making robust cascading not currently possible.

Note that Diazzi and Attene's work can, to some extent, support cascaded booleans. The idea here would be to take the output of each boolean and cast all points to floats. This is a lossy cast (and may create all sort of troubles!) but these defects can be compensated by the "mesh repairing feature" of the algorithm. In the paper they show some example, but we are talking about very shallow CSG trees. Since the process is inexact, cascading many booleans may accumulate significative error and spoil the result. If you could try on your complex use case and see what happens it would interesting for us to know!

Regarding truly robust cascading: in the final part of the paper we observe that the result of a boolean operation (also cascaded) is always a subset of all input meshes that participated in the boolean. Therefore, it should always be possible to express all intersection points as the intersection of input primitives natively expressed with floating points. What we miss right now is the ability to do a backtracking, in order to retrieve the correct input mesh elements for constructing implicit point at any point during cascading.

So, long story short, one may try Diazzi and Attene's heuristic cascading and see what happens. Truly robust cascading is not currently supported but it will be eventually supported. The time necessary to realize it will mostly depend on our ability to get funding and hire somebody to do the missing part. If you are an academic and want to collaborate on it, or if you are a company and want to somehow contribute to it, just let us know :)

[starseeker]

Given this premise, the reason why cascading is currently not possible is because Indirect Predicates do not permit to construct a new implicit point as the intersection of mesh elements that already contain some other implicit point (this is exactly what would happen if you cascade).

I see. So if the result of one computation is "stepped down" to an approximation using all floating point numbers (as must be done if the boolean result is going to be exported to something like an OBJ), that mesh may (if it satisfies the necessary properties) in turn be used as the input for a new boolean operation - however, in doing so, that approximation will lose the correctness guarantees that properly propagating the original IP intersections from the original boolean operation would provide?

The idea here would be to take the output of each boolean and cast all points to floats. This is a lossy cast (and may create all sort of troubles!) but these defects can be compensated by the "mesh repairing feature" of the algorithm.

So the write_OBJ output mesh from main.cpp in your example will, in principle, need PolyMender or some similar repair steps to ensure a manifold watertight, non-self-intersecting output? Eventually, we'd want to produce a final mesh that was "clean".

So, long story short, one may try Diazzi and Attene's heuristic cascading and see what happens. Truly robust cascading is not currently supported but it will be eventually supported. The time necessary to realize it will mostly depend on our ability to get funding and hire somebody to do the missing part. If you are an academic and want to collaborate on it, or if you are a company and want to somehow contribute to it, just let us know :)

Unfortunately I'm neither - I'm just a software developer on the BRL-CAD project :). I'll start by working with the reference implementation code and see what's involved with hooking it into our facetization pipeline - that'll be the first step regardless. If I rework it to provide a shared library, would that be of interest as a pull request?

[mlivesu]

I see. So if the result of one computation is "stepped down" to an approximation using all floating point numbers (as must be done if the boolean result is going to be exported to something like an OBJ), that mesh may (if it satisfies the necessary properties) in turn be used as the input for a new boolean operation - however, in doing so, that approximation will lose the correctness guarantees that properly propagating the original IP intersections from the original boolean operation would provide?

correct

So the write_OBJ output mesh from main.cpp in your example will, in principle, need PolyMender or some similar repair steps to ensure a manifold watertight, non-self-intersecting output? Eventually, we'd want to produce a final mesh that was "clean".

No. Keep in mind that the approximation error affects only the vertex coordinates and not the mesh connectivity. Robust booleans would still guarantee the correct topology. Precisely, if the two shapes are not tangent, the output mesh will be guaranteed to be manifold watertight. But, because of the approximated float coordinates, you may introduce zero area triangles, intersections, and points that move far away from where they should be (because of errors in the rounding). For the record, Diazzi and Attene's work would remedy zero area elements and intersections, but may "fail" because of badly rounded coordinates that create sort of artificial spikes and stuff like that

Unfortunately I'm neither - I'm just a software developer on the BRL-CAD project :). I'll start by working with the reference implementation code and see what's involved with hooking it into our facetization pipeline - that'll be the first step regardless. If I rework it to provide a shared library, would that be of interest as a pull request?

The code is shaped in a way that, to my understanding, making a library out of our tool would be as easy as saying to cmake "make a library" and not "make an executable". But of course, if you massage the code and create anything that looks like useful for the community, please let us know, we'll be happy to include it in the repo!