cgal-discuss - Re: [cgal-discuss] Subtracting spheres from a mesh

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Subtracting spheres from a mesh

From: Sebastien Loriot <>
To:
Subject: Re: [cgal-discuss] Subtracting spheres from a mesh
Date: Mon, 26 Apr 2021 11:32:32 +0200
Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
Ironport-hdrordr: A9a23:rLyJba2Z9ZKu08eHYTQk6AqjBaVyeYIsi2QD101hICF9WMqeisyogbAnxQb54Qx8ZFgMu/ClfJOBT3TV6IJv7eAqVouKcQH6tAKTQ71KwofvzjbpES+71sM178ldWodkDtmYNzlHpOP7+hT9M9tI+rm62YWpn/qb83B2UQpxYbph5AsRMHf5LmRSRBNaQaY/DoaW/MBdpzGtPU0QdNnTPAhmY8Hmh/nm0K3regQHARlP0njqsRqN5KThGxaVmjcSOgk/pYsKyHPImQD16qKov5iAu3jh/lTe5ZhXh9fto+ErbPCkscQNLyWptwDAXvUGZ5S5oDs3rOuzgWxGrPDwpX4bVfhb2jf6ZGnwix3owgzp0DEy8RbZuCalqEqmhcT4QT4gYvAx/b5xQ1/840okvNY5+qpOxmqYuZ0/N2K6oA3No/zBVxRrkQ6fpHovlvN7tQ0kbaIuLKVQpsge8SpuYeo9IB4=
Ironport-phdr: A9a23:RWL6zBcnDV0Zw1OpTU/aV3a6lGM+AtnLVj590bIXzolWe6HmxazJeXLljd1ThVPEFb/W9+hDw7KP9fy5CCpauMnK4C5KWacPfidNsd8RkQ0kDZzNImzAB9muURYHGt9fXkRu5XCxPBsdMs//Y1rPvi/6tmZKSV3wOgVvO+v6BJPZgdip2OCu4Z3TZBhDiCagbb9oIxi6sAHcutMIjYd/KKs9xRjEr3pVcOlK2G1kIk6ekQzh7cmq5p5j9CpQu/Ml98FeVKjxYro1Q79FAjk4Km45/MLkuwXNQguJ/XscT34ZkgFUDAjf7RH1RYn+vy3nvedgwiaaPMn2TbcpWTS+6qpgVRHlhDsbOzM/7WrajNF7gqBGrxK7vxFx3pDaYI+VOvR9cK3Sc9wVSmhdUcheTCFBHoCxYpETA+YdM+tVrY/wrEYOoxukAgmsAfvixCJWiXDtx6I6yPghEQDY0wwmAtkAtnPUrM/0NKcVTeC+0a7FzS7Hb/NRwzf96Y/Icgw7rfGJWbJ9asXRyUw1GAPEilWcs5DqPzSQ1ukUtWWQ8uVvW/61hWE9twFxviagxt0qioTRmo8Y103J+Th6zYopIdC0VVB3bN66HJZOuCyUOIt4T8c+T2xopCo3yaMLt56mcCUO1Jgq2RDSZuGDfoSV4hzuVuCcKip2inJifbKwnRey8U64x+3zV8m0zFZKrjdendXWqn8N0BnT5tCbRfty5Eih3SyD1wfJ6uFLOUw0k7DUJIU6zb40iJUfq1jMHijzmEnuja+WcF8k+umy5Oj9bLXmvJmRPJJ3hAHmKqkihNCzDOAiPgUNX2WX4/qw2KP+8UHjT7hHgOU6nrfDv5zGOMgWo7C2DxNP3Ysm9RqzEyqq3dEWkHYdMl5JZBeKgofnNlzOPv/1COmwj0isnThwwv3KI7LsDonXIXXGjrjscrdw51NaxQEu195Q/YhUBasEIP/rWk/+qtjYDhghPgyx2ennCdF92poQWGKVH6OVKa3SvFCG6+41LOmMY4gVuDn5K/c7/fLhkXg5mVoFcamo25sYdmy4E+x4L0mFZXfgmNQMHGcQsgYgUuDmlUeOXDFdanqqWqIz/DA7CIaoDYfZQYCthaSM3Dy/Hp1RfGBGC1eMEWvye4WBX/cBcy2SIsp7nTwFUbitUZMu1RartAPi0bpoMvLU+jEEtZLkzNV6++LTmgs29TBtEsud0nqNQH1pnmMTXD87x7t/oEx4yleby6d0mf1YFdpJ5/NISAg2L5Dcz/YpQ+30QR/LK9eVVE69EJLhGiA0Vtt3wtkUYk87Fc/llQHGxyPtArkbkPuAC5Uwt67dxHPsPN0u9nDdyaMdgkk6F8tTKXW91Ok47BnWH4ePkkODlq/se75bxz/I7G7EzGyAuwZTXwd0FKnERnsCfVCFkdOs7UzLS/qiCK8sLxBa4c+EMKpDLNPz3ntcQ/K2A9nUanmtmmq2TTKP3LKLcMK+YGEaxiTaFA4Blygc+H+HMU41ASL38DGWNyBnCV+6OxCkyuJ5sn7uFicc/0Sxd0RkkoGN1FsViPibI9sW17MA/Tg78nB6QA370NXRBN6N4QFmefcECfsNpWxf3GecjDRTe5mpLqRsnFkbGyx4ukrv01N8DYASyKACnDYR1AN3bJmg/hZZbTrw9Z/1M7zTbGL1+UL3A5M=

I just created the fix PR:

https://github.com/CGAL/cgal/pull/5642

Thanks,

Sebastien.

On 4/26/21 11:26 AM, Bruno Manganelli ( via cgal-discuss Mailing List) wrote:

I think there is a missing return statement in make_skin_suface_mesh_3.h after line 37.
Adding that fixed my issue.

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

Do you have a minimal example we could use to reproduce the issue?

Did you also try this example:

https://doc.cgal.org/latest/Skin_surface_3/Skin_surface_3_2union_of_balls_simple_8cpp-example.html

<https://doc.cgal.org/latest/Skin_surface_3/Skin_surface_3_2union_of_balls_simple_8cpp-example.html>

Best,

Sebastien.

On 4/26/21 11:09 AM, Bruno Manganelli (
<> via
cgal-discuss Mailing List) wrote:
> 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

<https://doc.cgal.org/latest/Skin_surface_3/index.html#Chapter_3D_Skin_Surface_Meshing>
> <https://doc.cgal.org/latest/Skin_surface_3/index.html#Chapter_3D_Skin_Surface_Meshing <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
> >> < <>
< <>>
> < <>
< <>>>> wrote:
> >>
> >>     With the following code (quick and dirty):
> >>
https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5
<https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5>
> <https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5
<https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5>>
> >>
> <https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5
<https://gist.github.com/sloriot/d563b5ce27d28fcfd73beb1b628d72b5>
> <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>
> <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>>
>
> >>
> >>
> >>
> <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>
> <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
> ( <>
< <>>
> >>     <
<>
> <
<>>> 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
> >>      >> <
<> <
<>>
> < <>
< <>>>
> >>     <
<> <
<>>
> < <>
< <>>>>> 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>>
>
> >>
> >>
> >>
> <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>>>
>
> >>
> >>
> >>      >>
> >>      >>
> >>      >>
> >>
> >>
> <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>>
>
> >>
> >>
> >>
> <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>>
> >> <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>>>
> >>      >>
> <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>>
> >> <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
( <>
> < <>>
> >>     <
<>
> <
<>>>
> >>      >>     <
<>
> < <>>
> >>     <
<>
> <
<>>>> 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/>>
> >>     <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/>>>
> >>      >>     <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/>>
> >>     <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>>
> >>     <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>>>
> >>      >> <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>>
> >>     <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>
> <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>
> <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>
> <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>
> <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>
> <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>
> <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

Re: [cgal-discuss] Subtracting spheres from a mesh, (continued)

List archive

Re: [cgal-discuss] Subtracting spheres from a mesh