Temporal coherency

[mariuszhermansdorfer]

In your fantastic paper, you write:

Booleans are applied naively, meaning that each frame is computed separately, without propagating cached data from one frame to the subsequent. We leave this improvement for future work to obtain additional speedups.

And later in section 7:

.As discussed in Section 6.1, the algorithm is at the moment not designed to exploit temporal coherency and naively computes each Boolean from scratch, which is of course not optimal. Things like acceleration data structures used to detect intersection and perform the ray casting could be created once and minimally updated at each frame, greatly reducing the computational cost. Also adjacency data is now recomputed from scratch each frame, while they can be cache in most cases.

Has there been any progress on this front? My primary interest in this library is for CSG applications. As the below clip illustrates, a typical use-case is to manipulate one (typically smaller) mesh while the other remains unchanged. It would make a lot of sense to update only the relevant parts of the triangle soup or the octree.

https://user-images.githubusercontent.com/49192999/233774474-646083cd-b4f8-4c52-be57-20ab8e2fffd7.mp4

[mariuszhermansdorfer]

For context, on my machine the customArrangementPipeline takes roughly 60-70% of the time

https://github.com/gcherchi/InteractiveAndRobustMeshBooleans/blob/7081647a8cc7cc823015044964cd071767947f66/code/booleans.cpp#L94-L98

Here is the breakdown of individual steps for the 25k bunny model

computeMultiplier: 0.1989 ms
mergeDuplicatedVertices: 0.738 ms
customRemoveDegenerateAndDuplicatedTriangles: 1.5424 ms
TriangleSoup: 3.8809 ms
customDetectIntersections: 13.6066 ms
initFromTriangleSoup: 3.4242 ms
classifyIntersections: 7.4129 ms
triangulation: 0.9453 ms
appendJollyPoints: 0.0001 ms

Inside of customDetectIntersections, building the octree takes approx. 1/3 of the time:

o.build_from_vectors: 4.3272 ms   

Updating rather than recreating the TriangleSoup and the Octree alone could potentially lead to 25% overall speed increase.

[mlivesu]

Thanks, we know that :) When we were preparing the article we did not have time to do that, and we haven't been working on this ever since (at the moment we don't have students to work on that)