Speeding up 3D Alpha Calculation

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Speeding up 3D Alpha Calculation

ak4733
Hi all,

Disclaimer: I am new to CGAL. I've been working with CGAL for less than a
week, so apologies if this is a silly question.

I'm attempting to speed up my application utilizing alpha shapes. To my
understanding, Alpha_shapes_3 generates a family of alpha shapes across
different alphas. Fixed_alpha_shape_3 generates a single alpha shape for a
given alpha (I just need a single alpha shape). The documentation says that
this approach should be faster, but I'm finding that it takes just as long,
if not even longer, than Alpha_shapes_3 !!! I'm not too sure as to why this
is occurring; unfortunately it may be because of some type / kernel
mismatch, and I don't have enough understanding of CGAL to debug that
effectively given the limited examples on alpha shapes. I use the same point
models for both alpha generations.

Here is my simplified setup:

typedef CGAL::Exact_predicates_inexact_constructions_kernel Gt;

typedef CGAL::Fixed_alpha_shape_vertex_base_3<Gt> Vb;
typedef CGAL::Fixed_alpha_shape_cell_base_3<Gt> Fb;
typedef CGAL::Triangulation_data_structure_3<Vb, Fb> Tds;
typedef CGAL::Delaunay_triangulation_3<Gt, Tds> Triangulation_3;
typedef CGAL::Fixed_alpha_shape_3<Triangulation_3> Alpha_shape_3;

typedef Gt::Point_3 Point;

std::list<Point> points; //I generate some points for this list in my code

Alpha_shape_3 as(points.begin(), points.end(), 1); //note I defined
alpha_shape_3 for fix_alpha

Any help / tips are appreciated!






--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

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


Reply | Threaded
Open this post in threaded view
|

Re: Speeding up 3D Alpha Calculation

Sebastien Loriot (GeometryFactory)
Could you share your benchmark?

I've just gave it a try with a bench program [1]
with 351750 weighted points and I got:

Building regular triangulation: 2.03785
Build Fixed weighted alpha complex
Fixed 4.41835
Build family weighted alpha complex
Family 13.0819
Build family filtered weighted alpha complex
Family filtered 25.4051
Building exact regular triangulation: 4.34791
Build exact family weighted alpha complex
Family exact 23.192


so ~4s vs 13s.

Sebastien.

[1]
https://github.com/CGAL/cgal/blob/master/Alpha_shapes_3/test/Alpha_shapes_3/bench_walpha.cpp


On 06/19/2018 05:26 PM, ak4733 wrote:

> Hi all,
>
> Disclaimer: I am new to CGAL. I've been working with CGAL for less than a
> week, so apologies if this is a silly question.
>
> I'm attempting to speed up my application utilizing alpha shapes. To my
> understanding, Alpha_shapes_3 generates a family of alpha shapes across
> different alphas. Fixed_alpha_shape_3 generates a single alpha shape for a
> given alpha (I just need a single alpha shape). The documentation says that
> this approach should be faster, but I'm finding that it takes just as long,
> if not even longer, than Alpha_shapes_3 !!! I'm not too sure as to why this
> is occurring; unfortunately it may be because of some type / kernel
> mismatch, and I don't have enough understanding of CGAL to debug that
> effectively given the limited examples on alpha shapes. I use the same point
> models for both alpha generations.
>
> Here is my simplified setup:
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel Gt;
>
> typedef CGAL::Fixed_alpha_shape_vertex_base_3<Gt> Vb;
> typedef CGAL::Fixed_alpha_shape_cell_base_3<Gt> Fb;
> typedef CGAL::Triangulation_data_structure_3<Vb, Fb> Tds;
> typedef CGAL::Delaunay_triangulation_3<Gt, Tds> Triangulation_3;
> typedef CGAL::Fixed_alpha_shape_3<Triangulation_3> Alpha_shape_3;
>
> typedef Gt::Point_3 Point;
>
> std::list<Point> points; //I generate some points for this list in my code
>
> Alpha_shape_3 as(points.begin(), points.end(), 1); //note I defined
> alpha_shape_3 for fix_alpha
>
> Any help / tips are appreciated!
>
>
>
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.nabble.com/
>

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