CGAL users discussion list

[Bruno Manganelli <>]

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

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