Skip to Content.
Sympa Menu

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


Chronological Thread 
  • From: Sebastien Loriot <>
  • To:
  • Subject: Re: [cgal-discuss] Subtracting spheres from a mesh
  • Date: Mon, 26 Apr 2021 08:26:20 +0200
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-hdrordr: A9a23:JqY1qKn9q4JJJ/KgVAmhdbJ9R9zpDfIk3DAbvn1ZSRFFG/GwusiykJ0guSPcpy0WXBgb9OyoHKWbW3vT+dpU7OAqU4uKZwXttGu2IIwK1+KLqAHIITH09eJWyM5bHJRWNduYNzJHsfo=
  • Ironport-phdr: A9a23:AUSWTxRIc+rVes3bF3a8Kt37dNpsogyYAWYlgqEPu/d1aq2muq7aFwnh351FslbFUM3h5u5ejKKO6ua8AD1Gu8/e+yBcOLV3FDY9wf0MmAIhBMPXQWbaF9XNKxIAIcJZSVV+9Gu6O0UGUOz3ZlnVv2HgpWVKQka3OgV6PPn6FZDPhMqrye+y54fTYwJVjzahfL9+Nhq7oRjVu8UMn4duN6Q8xhTKr3ZJZu9b2X5mKVWPkhjm+8y+5oRj8yNeu/Ig885PT6D3dLkmQLJbETorLXk76NXkuhffQwSP4GAcUngNnRpTHwfF9hD6UYzvvSb8q+FwxTOVPczyTbAzRDSi86JmQwLmhSsbKzI09nzch8pth6xZvR2hvQRyzZPUbo+LOvpwfa3Tct0VSmVDQslfWDdMAp+/YoYVE+YNIehVoov7qlATrRW+Hw6sBOb3xzFVmHD5xrc10/89EQHHwgMgGc8FvnLTrNXvNacSVvy1x7TPwDXYa/NW3i396InPchA9u/2MWLZwfNHeyUkqDQzFj1GQpZb5MDOS0+QAqm6W5PdvWuyzkWAosR1xoiSxycc2jInEnp8Zx1DL+Ch9z4g4JtK1RkFlbNO4EpZduT2WOYt0T84mX2xkpCQ3x7katJKnciUG1JsqyhDdZvGHb4WE/x3tWumXLDxlinxlf7e/iAyz8Uim0uDzSsa030xOriZfldnMrH8N2wTc6siGVvt9/lqh1i2V2w/P7eFEJFg4lazBJJE62bEwkoQcvV7fES/xnUX6lK6WdkM++uip8evreLvmpoWaOoRpiQ/+KrwjltKjDek8KAQDXGiW9f6h2LH9/kD1WrpHg/wunqXHqp/WOdkXq6unDANJyIku7gizAyu73Nkdk3QINkxJdA6CgoXmNVzDIO73APKhjFiwkDpk3PXLMqDuD5nRNHfOlanucLl85kJBzgc40MpR6IhOCr4bJfL+Qk/xu8LcDh8+KwG0xvzoCNR51o8HV2OPB7KVPLrcsVKH5+8jOeaMZIgSuDbyL/gq+eTigmM+mV8YZaWp3J0XZ26kHvl+PUmVfX7hjs0CHGoKpAYyUfLmhV6YXTNcZnu+R6c86Ss6CIKiA4fDXIetgLmZ0SegGp1WYXpGClGLEXf0bYmEXvMMZTmdIs9kiDMEVLyhR5U92hGpsQ/206BnIfbM+i0EqZLj08B46PHclR4o8Tx4FtmS02CWT25og2MIXCQ20btkoU19z1eDybJ3j+ZZFdxV/fNJUx01OYTSz+xgWJjPXBncdIKJVEq+WYfhRiogS8o4hd4IeUd0Xdu4yQvS2jKjRL4TmbvMD5M99ufQ3mP6Ot1mmEvAz7Qrs1Q2Xp5PKXG+nfw4sBPCApbA1USfjaejM6oGmzXc8X+KimuIskYfWwF5VeDJXGsUe1DN/uj+s0jNRrvrBbU8ORZa0uaDLLFLY5vnlwZoXvDmbe/TaWuqh2a9A16swamNa5aiL34Z2z/cD1RClgQ78nOPNAx4DSCk9TGNRAdyHE7iNhu/udJ1r2m2Gxdc5zHPVFVo0v+OwjBQgPWdT/0J2bdskCgkojRwWl262oCPY/Kw4jF5daAZWusTpU9d3ArxuAl0P5jmJKdn1AZ2WzQyhFvn0lBMMqsFkcUuqxsCyQNzLeeH1QoEeW/Gm5/3PbLTJy/5+xX9M8br

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

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




Archive powered by MHonArc 2.6.19+.

Top of Page