Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Speeding up Intersection

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Speeding up Intersection


Chronological Thread 
    < Chronological >      < Thread >
  • From: Andrew Cunningham <>
  • To:
  • Subject: Re: [cgal-discuss] Speeding up Intersection
  • Date: Mon, 3 May 2021 20:34:36 -0700
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=None ; spf=None
  • Ironport-hdrordr: A9a23:k11ahK5RtCCooE9zSwPXwDfXdLJzesId70hD6mlYVQFSNvaFnMSvgekW2HbP5go5cncmhNyGJe28Wnva75F4+s08Or2lUQngtgKTTL1KwIP+z1Tbak/D38NQ0Kd+f7NzBZnMCzFB5/rSzxK/F78bsby62YSJocub8Ht3VwFtbMhbjjtRLgqACEV5SE1nCPMCZfmhz/FKrTahZngbB/7TbhJpY8H4u9bJmJj6CCRoOzcb7mC14Q+V1A==
  • Ironport-phdr: A9a23:n4etFxcCzQICsmy9LQ/qIAJllGM+jdnLVj590bIXzolWe6HmxazJeXLljd1ThVPEFb/W9+hDw7KP9fy5CCpausrK6SpcOLV3FDY9wf0MmAIhBMPXQWbaF9XNKxIAIcJZSVV+9Gu6O0UGUOz3ZlnVv2HgpWVKQka3OgV6PPn6FZDPhMqrye+y54fTYwJVjzahfL9+Nhq7oRjVu8UMn4dvJKk8xhTUrndWeuld2H9lK0+Ukxvg/Mm74YRt8z5Xu/Iv9s5AVbv1cqElRrFGDzooLn446tTzuRbMUQWA6H0cUn4LkhVTGAjK8Av6XpbqvSTksOd2xTSXMtf3TbAwXjSi8rtrRRr1gyoJKzI17GfagdF2galGohyuugZ/zpbbb4GbNvVwfq3Tc9AHS2RfQslcTDBBDp+mYocTE+YNIeRVoo/grFUOtxu+AgysCfvzxz9Om3D2x7M10uo8GgzYwQwgGdQOsHXSrNX6NKcdS+W1x7TPwDrfYPNZwzP95ZPSfRw4vf6MQLRwcczQyUkpGAPFjk+fqYn/MzyJ0eQNtnGW4ux9Xu2gl2ApsRt+oiSzxsgykInJgJoYxk3Z+Ch6z4s7Kt21RU1nbdCrFJZeuTyWOYt2TM4tQ2xlpSg3x7kHtJO6eCUH1Zopyh3BZ/KIbYSF/hDuWeaeLzp+mXlrdrW/hxOo/kihzO3xTsi00FBQripEiNbArH4N1wbV58OaSfV95l+s1SiT2w3X8O1JIkA5mbDFJ5I8wbM8jJUevErFEyTrgkv5lrWWeV8h+uWw6+TofLHmppiEOo9xkA7+M6AultWhDuQ6LwQCRmab9Ouy2bH58k35R7JKjvIykqbHqpzVOcMbpquhDw9U1IYs9Qq/Ai+43NgEmXQLNlFIdRKdg4T3Jl3DI+r0APixjli0lTdk3fHGPrnvApXXKXjDla/scqxg5E5ZyQozy8tS6IhNBr4dPfLzXEnxtN3eDh82Mwy72ePnBM9h2YMZXGKDGrWZP7/KsV+U+uIvJPGBa5MauDnnL/gp/uPhjX4imVABYKmpxoAXZWujHvVmJkWZeWDjjs0AEWcMpAo+TfblhEeMUT5JND6PWbkh7GQ7FJ6+FtWEAZu8haSImia9BJxfIG5cTUudFG/hMISCVfBLYy2bJoptkycPSKO6GLInzgykiALq1+9nMvbM4X9f8ony0cB8oezVjxA7szJuSN+M1nmECGBykGRPTDA/2OVzoFd210yYgpR/1vdXHNgW6/JSWRohLrbdyfZ7Apb8QFHvZNCMHX+gTs+rHnkaU9Q3wtkBY094U4GpgRnH9yPvCKITkb2NC5w99+TX2H2ndJU18GrPyKR01wpuecBIL2Dz3sZXx03oH4fM1n6hueOqeKAbtAbI/WaHiGeM5QRWDFU2XqLCUnQSIEDRqIahjmvyCoS2ALFiCTNvjNaYI8NiY5jikFNARfHsON3bJWm2njXobT64g4iUZY+vQF0zmSDUCUwKiQcWlV6PcAMjACGgpW3eBTkoHlXqMRuEzA==
Hi Anish,
Since your code is a N^2 algorithm , it's not surprising that this is
taking a long time. The first thing that comes to mind is to bound
each triangle with a CGAL AABB (BoundingBox) and use CGAL AABB
algorithms to find the pairs of intersecting bounding boxes(pairs of
potential triangle intersections). That would make a huge difference
in execution time.
And once you have done that, you could loop over the intersecting
pairs and use OpenMP or other threading approaches like TBB to process
the intersecting pairs in parallel. I personally have had great
success with OpenMP tasks and CGAL.

Andrew

On Mon, May 3, 2021 at 1:17 PM Rasal Raj, Anish
<> wrote:
>
> Hello Guys,
>
> I have recently started working with CGAL. I have a doubt.
>
>
> I am using CGAL intersection operation on a list of triangles. currently,
> it takes some time to complete the information. What are the possible ways
> to improve the execution time?
>
>
> Note: the list of triangles contains around 25k triangles. I have attached
> a sample code with this e-mail. I am using
> Exact_predicates_exact_constructions_kernel kernel.
>
>
> --
> 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