CGAL users discussion list

[Sebastien Loriot <>]

When doing a union operation, the first step of the operation is
to filter the intersection between the bounding boxes of the input
triangles. This is done in a clever way using this package:
https://doc.cgal.org/latest/Box_intersection_d/

The rest of the runtime then depend on the size of the intersection of
triangles.

I don't know why the second step if slower, because in both cases the 
size of at least one mesh increases so maybe it depends on the order of 
the cubes.

I guess, the fastest sequential option would be to used the experimental
non-documented function
CGAL::Polygon_mesh_processing::experimental::autorefine_and_remove_self_intersections(m);

Build the mesh m by appending all your meshes inside and call that
function. It will build only on hierarchy of bboxes for all the
triangles and will resolve the intersection. It is still experimental
and will throw an exception in case they are more than 2 input meshes 
sharing an edge. The exception type is
CGAL::Polygon_mesh_processing::corefinement::Triple_intersection_exception

For the multithreaded version, I've create a simple example doing the
union in parallel:
https://github.com/CGAL/cgal/pull/5403
It is a basic version that might need extra step depending on how
complex is the input.

Best regards,

Sebastien.

On 1/22/21 5:05 AM, Giles Puckett wrote:
> Hello,
>
> I have an application that builds 3D volumes by combining simple shapes 
> (cubes, cylinders) using corefine_and_compute_union. There may be 
> 100-400 simple shapes.
>
> I tried two ways of doing the unions:
>
> 1. Build up the result by unioning in one cube at a time, or
>
> 2. Union the simple shapes in pairs, then union their results (in a 
> binary tree fashion) until you get one object left.
>
> I noticed that method 2 is a lot slower than method 1 - I assumed it was 
> because there are many more faces to be split when corefining. Is this a 
> reasonable assumption? I am interested in method 2 again as it lends 
> itself to doing unions in parallel, potentially reducing operations from 
> O(N) to O(log2 N) if there are enough cores/threads.
>
> What determines the performance if corefine_and_compute_union? Is it the 
> complexity of the meshes, the complexity of the intersection path, or 
> something else?
>
> And is PMP able to be multithreaded?
>
> Giles.