CGAL users discussion list

[Sebastien Loriot <>]

do_intersect can be safely used with 
CGAL::Exact_predicates_inexact_constructions_kernel (EPICK),
intersection requires EPECK.

I would indeed reduce the number of expensive calls using bboxes
and do_intersect predicates.

But again this depends on your scenario. If you have all triangles
intersecting all triangles then the filter is useless.

Sebastien.

On 5/5/21 3:49 PM, jana jelenki ( via cgal-discuss Mailing 
List) wrote:
> Thank you for you fast reply.
> Are you using the same kernel and datatype as me?
> Am I getting you right, that the black box function «Intersection» 
> itself cannot be sped up. It’s only possible to reduce number of calls, 
> to reduce computational time?
>
>     Среда, 5 мая 2021, 16:43 +03:00 от Sebastien Loriot
>     <>:
>     Of course it depends on your real scenario but I would use something
>     like this example:
>
>     
> https://doc.cgal.org/latest/Box_intersection_d/Box_intersection_d_2triangle_self_intersect_8cpp-example.html
>     
> <https://doc.cgal.org/latest/Box_intersection_d/Box_intersection_d_2triangle_self_intersect_8cpp-example.html>
>
>     with the do_intersect and a fast kernel without exact constructions
>     to collect pairs of triangles intersecting and then I'll use a kernel
>     with exact constructions to compute intersections.
>
>     Best,
>
>     Sebastien.
>
>     On 5/5/21 3:37 PM, jana jelenki ( via cgal-discuss Mailing
>     List) wrote:
>      > Hi Sebastien,
>      > below is an MWE, that sums up my code. I have numbers that span from
>      > 1.0e-7 to 100, therefore the strange looking points.
>      > Result of this intersection is a Segment_3:
>      > P1: 66.666666722222    50.0000001    0
>      > P2: 100.0000001    50.0000001    0
>      > It takes nearly 0.1ms for each intersection. So 10s for 100,000
>      > intersections. Can this be sped up by another kernel or data type? I
>      > tested for example inexact construction but it gave wrong results.
>      > Best
>      >
>      > #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
>     #include
>      > <iostream> #include <chrono>
>      > typedef CGAL::Exact_predicates_exact_constructions_kernelKernel;
>     typedef Kernel::Point_3Point3; typedef Kernel::Triangle_3Triangle3;
>      > int main() {
>      >
>      > std::vector<Point3> APoints(3); std::vector<Point3> BPoints(3);
>      > APoints[0] = Point3(0, 0, 0); APoints[1] = Point3(100.0000001, 0,
>     0); APoints[2] = Point3(100.0000001, 100.0000001, 0);
>      > BPoints[0] = Point3(0, 50.0000001, -100.0000001); BPoints[1] =
>     Point3(200.0000001, 50.0000001, -100.0000001); BPoints[2] =
>     Point3(200.0000001, 50.0000001, 200.0000001);
>      > Triangle3 TriangleA(APoints[0], APoints[1], APoints[2]);
>     Triangle3 TriangleB(BPoints[0], BPoints[1], BPoints[2]);
>      > int end =100000;
>      > auto start =std::chrono::high_resolution_clock::now();
>      > for (int i =0; i < end; i++)
>      > auto result = CGAL::intersection(TriangleA, TriangleB);
>      > auto finish =std::chrono::high_resolution_clock::now();
>     std::chrono::duration<double> elapsed = finish - start; std::cerr<<
>     elapsed.count()<< "\t" << elapsed.count() / end *1000 << std::endl; }
>      >
>      > Среда, 5 мая 2021, 15:30 +03:00 от Sebastien Loriot
>      > < </compose?To=cgal%>>:
>      > Without seeing any code it is hard to tell. Are you using
>     do_intersect
>      > or intersection?
>      >
>      > Best,
>      >
>      > Sebastien.
>      >
>      > On 5/4/21 9:01 AM, jana jelenki ( via cgal-discuss
>     Mailing
>      > List) wrote:
>      > > Hi,
>      > > I find this topic very interesting. I already use spatial
>      > partitioning
>      > > and also OpenMP. For an average Triangle_3 Triangle_3
>     intersection my
>      > > program needs on average 0.1ms in release mode. I also use the
>     exact
>      > > kernel. Is this the limit of the CGLAL implementation, are
>     there any
>      > > numbers or benchmarks?  Or can you squeeze there even further?
>      > > Best
>      > >
>      > > Вторник, 4 мая 2021, 6:35 +03:00 от Andrew Cunningham
>      > > < </compose?To=cgal@a%2dcunningham.com>
>     </compose?To=cgal@a%2dcunningham.com>>:
>      > > 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
>      > > <
>     </compose?To=anish.rasal@rwth%2daachen.de>
>      > </compose?To=anish.rasal@rwth%2daachen.de>
>      > > </compose?To=anish.rasal@rwth%2daachen.de>> 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
>     <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
>     <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>
>      > <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>
>      > <https://sympa.inria.fr/sympa/info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>>>
>      > >
>      > > --
>      > > jana jelenki
>      > >
>      > > --
>      > > 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>
>      > <https://sympa.inria.fr/sympa/info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>>
>      >
>      > --
>      > jana jelenki
>      >
>      > --
>      > 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>
>
> --
> jana jelenki
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss