CGAL users discussion list

[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

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