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: Sat, 24 Apr 2021 14:06:57 +0200
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-hdrordr: A9a23:fQ7ys6OhnPGf2cBcTkKjsMiAIKoaSvp033AA0UdtRRtJNvGJjszGpoV46TbYgCscMUtLpfmuI6+FKEmwybdU5s0rMa6mTE3avgKTQr1KyavH73neFzbl9uhbvJ0QEJRWLNHrF1B1gYLbzWCDfOoI+9WM/KC2ieq29R4EJj1CUK1u4xx0DQyWCCRNJTVuP4YzF5aX+6N8xwaIRHUNYsy3QlkDUuTTzue78q7OXB8cCxYrrDSJlDOjgYSKdCSw4xF2aV9y6IZn1WDElgDjj5/T182T+1v7zG/c75NfhdvnxJ9iPaW3+60oFgk=
  • Ironport-phdr: A9a23:x0hVyBZHmdYEbxLIcBBfeJH/LTH014qcDmYuwqpisKpHd+GZx7+nAna3zctkgFKBZ4jH8fUM07OQ7/mxHzZZut3e7jgrS99lb1c9k8IYnggtUoauKHbQC7rUVRE8B9lIT1R//nu2YgB/Ecf6YEDO8DXptWZBUhrwOhBoKevrB4Xck9q41/yo+53Ufg5EmCexbal9IRmrqQjdrNcajZZsJ6o+yBbEo2ZDdvhLy29vOV+dhQv36N2q/J5k/SRQuvYh+NBFXK7nYak2TqFWASo/PWwt68LlqRfMTQ2U5nsBSWoWiQZHAxLE7B7hQJj8tDbxu/dn1ymbOc32Sq00WSin4qx2RhLklDsLOjgk+2zRl8d+jr9UoAi5qhJi3YDUboGbOvlwcKzTctwVR3ZOUMlKWixdAY6xdZcDA/YPMOtaqYT2ulsArQG5BQmpHO7h1yFHiWTs0q0hz+QhEB/J3Ao9FNwIt3TUttT1NKAOUeuoy6TI1jHDb/RM2Tf874jIbgotofSIXb9rfsrRzFMgFwLBjlmKtYPlODaV2/0LvmOG4OVuSfihhHQ7qwFtvDev3MEsh5HIi48X1lzJ6CZ0zokrKdC6SkN2fMKoHIdMuy+aKYZ7XscvTW9otSomzrALpZq2cSoXxZg6xhPSdvKKfomU7h/hUuuaPDl2hHVgeL2lhhay91CtxfHzVsau1FZGtC1FksPDtnwV0Rzc8NOIReB5/ki/wzqAywfT6uRcLUA1k6rbMZ8hzaQqmpodq0TOGDL9lkbujKKOaEko5uyl5/7kb7jmvJOQKpF4hwLkPqkhlcGzGfo0PRISU2SG/OmzyqHv8lf8TblUkvE6j6zUvZ7AKsgFuqK0BgFY3Zot6xu9Cjqr0tcVkH0IIV9AZR2LkovkNEvLLf/iDvqyjFShnTF2zP7cJLLhGI/CLn3bnbfhY7l970lcxRI2zd9F5pJUDqgNIfz2WkPsrdDYABA0PgOuz+boD9V90YweWWaRDaODLKzStlqI6vouI+mKeoAVpC7wJ+Y56/Pql3M0ml8QcbO00ZcJa320BPtrLkqBbXrpmNgBEGMKvgQkTOztjV2PSSVTZ3K1X6Im5zE7D56mAZ3GRoCpm7GB0yK7EYdXZmBCEFyDDXDod4CcV/cWdC2SOtNhkiADVbW5V4Ah2guhtAvjx7V6L+rU4TEXtY/41Nhu/ODTjhEz9TlsD8uHyW2NTmd0nnkJRzAsxqx/r1Z9mR++17NlialYCcBL/KEOFRwrMIbVie18EdH7HAzbOcyYTU6vBdSgDzZ2Rd04x5oCYl12Bs653S3FxDegP7IFi+mLGIAs6fCbmGPgIt50jXfAzqgoyVc8BdBeMHWvwa95+Q+UDIHAlwCVlr2haL8HjxLKoWyMxG7LsEBDWxNrSo3EW2oebw3Yt4fX/ETHGoSjA708LgpMz4amLbFLbcGh2U5CQ+3iP8iYZmaZlGK5BBLOzbSJOtm5M14B1TnQXRBX2zsY+myLYFBWLhfkmHrXCXlVLXyqe1nlmcFxrXq6Sgk/yATYNyVJ5/+O4hcQwMekZbYT07YD0A8kojRwWUm4hpfYV4bGqA1mc6FRJ9g65QUfvUrp8jdlN5nlFJhMw1sXcgB5pUTrvz14D4xBlY4hq3Z4lWJP

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

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>

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>



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

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