CGAL users discussion list

[Tony Apicella <>]

I am doing a union of two meshes also, and I see that sometimes only one mesh is included in the union, even though both meshes intersect.  I have tried increasing the facet_distance of mesh_3 create mesh with partial success.  I have placed the code and data in the code base.

First, I create meshes around sub volumes of a gray scale image and write the outer boundary of the resulting C3T3s to the disk.

Later I read back two neighboring meshes, each into a mesh of type SurfaceMesh<K::Point_3> and call the co-refine and compute union method in the PMP namespace.

Union results are sometimes as expected and other times one of the meshes is not included in the union.    

Is the problem that I am writing a C3T3 outer boundary and reading into a Surface Mesh?  Is this causing truncation or other boundary error?

Should I convert the C3T3 to a Surface Mesh first, and then write it?

Thank you.

---

From: <> on behalf of Sebastien Loriot <>
Sent: Wednesday, January 27, 2021 10:34 AM
To: <>
Subject: Re: [cgal-discuss] PMP performance question

 

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.
>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss