CGAL users discussion list

[Bruno Manganelli <>]

That indeed is exactly what I needed, thanks!

Without mesh subdivision and shrink_factor of 1, the algorithm takes less than 5s.

However, trying to execute CGAL::subdivide_skin_surface_mesh_3 on the surface generated with the shrink_factor of 1 results in an assertion failure in  in triangulate_mixed_complex_3.h:983

CGAL_assertion(orientation(ch) == POSITIVE);

Is this expected? I couldn't find the requirement that shrink_factor must be < 1 in the documentation.

On Mon, Apr 26, 2021 at 8:26 AM Sebastien Loriot <> wrote:

Andreas mentioned that there is the following package that also might
fit you need (in case you want more that spheres):

https://doc.cgal.org/latest/Skin_surface_3/index.html#Chapter_3D_Skin_Surface_Meshing

Best,

Sebastien.

On 4/25/21 11:42 AM, Sebastien Loriot wrote:
> Did you switch on parallel meshing?
> By default the points on the spheres are computing by bisection.
> It is possible to provide a specific functor for computing points
> on the surface.
>
> Best,
>
> Sebastien.
>
> On 4/25/21 11:12 AM, Bruno Manganelli ( via
> cgal-discuss Mailing List) wrote:
>> Thanks for all your dedication to help :)
>> I have tried your method, and indeed it works. However it is still
>> fairly slow, taking around 70 s to process 761 spheres (on a ryzen 5
>> 3600). Do you think there are any optimizations that I could try or do
>> you think it will be hard to significantly speed  up this approach?
>>
>>
>> On Sat, Apr 24, 2021 at 2:50 PM Sebastien Loriot
>> < <mailto:>> wrote:
>>
>>     With the following code (quick and dirty):
>>     https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5
>>     <https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5>
>>
>>     I could generate a mesh.
>>
>>     Best,
>>
>>     Sebastien.
>>
>>     PS: there might be some initialization issues if you have several
>>     (small) connected components and initial points should be added.
>>     If you need clean intersections then some extra work is also needed.
>>
>>
>>     On 4/24/21 2:06 PM, Sebastien Loriot wrote:
>>      > If you take the maximum radius, you can collect all the closest
>> point
>>      > to the query and stop when you exceed the maximum radius.
>>      > You can associate the radius to each point like in this exemple:
>>      >
>>      >
>>     
>> https://doc.cgal.org/latest/Spatial_searching/Spatial_searching_2searching_with_point_with_info_8cpp-example.html
>>
>>     
>> <https://doc.cgal.org/latest/Spatial_searching/Spatial_searching_2searching_with_point_with_info_8cpp-example.html>
>>
>>
>>      >
>>      >
>>      > HTH,
>>      >
>>      > Sebastien.
>>      >
>>      > On 4/24/21 11:28 AM, Bruno Manganelli (
>>     <mailto:> via
>>      > cgal-discuss Mailing List) wrote:
>>      >> Thanks for the reply Sebastien :)
>>      >> Unfortunately I can't use a kd-tree because the spheres can have
>>      >> different radii, so a point won't necessarily be inside the
>> closest
>>      >> sphere.
>>      >> I have tried adapting an AABB tree to use spheres as primitives,
>>     but
>>      >> it doesn't seem to work when querying for intersections with
>> points.
>>      >> I admittedly don't know how the bounding boxes are created or
>>     whether
>>      >> querying for intersections is a valid thing to do.
>>      >>
>>      >> For reference, this is what I was doing with AABB trees:
>>      >>
>>      >> class AABBSpherePrimitive {
>>      >>   public:
>>      >>     using Point = Point_3;
>>      >>     using Datum = Sphere_3;
>>      >>     using Point_reference = Point;
>>      >>     using Datum_reference = Datum;
>>      >>     using Id = Datum;
>>      >>
>>      >>     AABBSpherePrimitive(Sphere_3 sphere)
>>      >>         : m_sphere_datum(sphere)
>>      >>     {
>>      >>       m_reference_point = sphere.center();
>>      >>       m_reference_point +=
>>      >> K::Vector_3{std::sqrt(sphere.squared_radius()), 0, 0};
>>      >>     }
>>      >>
>>      >>     Datum_reference datum() const { return m_sphere_datum; }
>>      >>     Id id() const { return m_sphere_datum; }
>>      >>     Point_reference reference_point() const { return
>>     m_reference_point; }
>>      >>   private:
>>      >>     Datum m_sphere_datum;
>>      >>     Point m_reference_point;
>>      >> };
>>      >>
>>      >> using SphereTreeTraits = CGAL::AABB_traits<K,
>> AABBSpherePrimitive>;
>>      >> using SphereTree = CGAL::AABB_tree<SphereTreeTraits>;
>>      >>
>>      >>
>>      >> On Sat, Apr 24, 2021 at 7:42 AM Sebastien Loriot
>>      >> < <mailto:>
>>     <mailto: <mailto:>>> wrote:
>>      >>
>>      >>     What I would do is generate a mesh for the union of
>> spheres by
>>      >> adapting
>>      >>     this example:
>>      >>
>>      >>
>>      >>
>>     
>> https://doc.cgal.org/latest/Mesh_3/Mesh_3_2mesh_implicit_sphere_8cpp-example.html
>>
>>     
>> <https://doc.cgal.org/latest/Mesh_3/Mesh_3_2mesh_implicit_sphere_8cpp-example.html>
>>
>>
>>      >>
>>      >>
>>      >>
>>     
>> <https://doc.cgal.org/latest/Mesh_3/Mesh_3_2mesh_implicit_sphere_8cpp-example.html
>>
>>     
>> <https://doc.cgal.org/latest/Mesh_3/Mesh_3_2mesh_implicit_sphere_8cpp-example.html>>
>>
>>
>>      >>
>>      >>
>>      >>     to handle several spheres.
>>      >>
>>      >>     To do that, I think the simplest way to do it is to use a
>>     kd-tree
>>      >> [1] to
>>      >>     get the closest sphere center from the query point and then
>>     use the
>>      >>     existing formula with the selected sphere.
>>      >>
>>      >>     Let us know if you could do it.
>>      >>
>>      >>     Best,
>>      >>
>>      >>     Sebastien.
>>      >>
>>      >>     [1] https://doc.cgal.org/latest/Spatial_searching/index.html
>>     <https://doc.cgal.org/latest/Spatial_searching/index.html>
>>      >>     <https://doc.cgal.org/latest/Spatial_searching/index.html
>>     <https://doc.cgal.org/latest/Spatial_searching/index.html>>
>>      >>
>>      >>
>>      >>
>>      >>     On 4/23/21 11:57 PM, bmanga (
>>     <mailto:>
>>      >>     <mailto:
>>     <mailto:>> via cgal-discuss
>>      >>     Mailing List) wrote:
>>      >>      > I have also tried to use
>>      >>      >
>>     PMP::experimental::autorefine_and_remove_self_intersections, but
>>      >>     it fails
>>      >>      > with the following:
>>      >>      >
>>      >>      > CGAL error: precondition violation!
>>      >>      > _expression_ : vaa != vbb
>>      >>      >
>>      >>      >
>>      >>      >
>>      >>      > --
>>      >>      > Sent from: http://cgal-discuss.949826.n4.nabble.com/
>>     <http://cgal-discuss.949826.n4.nabble.com/>
>>      >>     <http://cgal-discuss.949826.n4.nabble.com/
>>     <http://cgal-discuss.949826.n4.nabble.com/>>
>>      >>      >
>>      >>
>>      >>     --     You are currently subscribed to cgal-discuss.
>>      >>     To unsubscribe or access the archives, go to
>>      >> https://sympa.inria.fr/sympa/info/cgal-discuss
>>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>>      >>     <https://sympa.inria.fr/sympa/info/cgal-discuss
>>     <https://sympa.inria.fr/sympa/info/cgal-discuss>>
>>      >>
>>      >>
>>      >>
>>      >> --
>>      >> You are currently subscribed to cgal-discuss.
>>      >> To unsubscribe or access the archives, go to
>>      >> https://sympa.inria.fr/sympa/info/cgal-discuss
>>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>>      >>
>>
>>     --     You are currently subscribed to cgal-discuss.
>>     To unsubscribe or access the archives, go to
>>     https://sympa.inria.fr/sympa/info/cgal-discuss
>>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>>
>>
>>
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>

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