CGAL users discussion list

[jana jelenki <>]

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_kernel Kernel;
typedef Kernel::Point_3 Point3;
typedef Kernel::Triangle_3 Triangle3;

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