CGAL users discussion list

[jana jelenki <>]

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

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
>

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

 

 

--
jana jelenki