CGAL users discussion list

[Bruno Manganelli <>]

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

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



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

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