CGAL users discussion list

[Mariette Yvinec <>]

You are probably encountering a numerical problem
when computing the alpha_shape data structure....
Although the Delaunay triangulation is CGAL is granted not
to include tet with 0 volume, it may include tet with very small
(but non zero ) volume.
Everything works fine for the triangulation
because the kernel you are using provides exact predicates.
However, when you build an alpha-shapes, the critical alpha
values, which are squared_radius of minimum circumspheres
are computed. the EPIC kernel use floating point arithmetic
for that and may encounter numerical pb as a null denominator...
(The denominators in such computation are the volume of the tets).

A solution might be to use an exact kernel but
thiswill slow down your code.

cbamber85 wrote:
> Hi all,
>
> I'm creating a Delaunay alpha shape surface from a point cloud input.  The
> point cloud is generated from the surface of an existing mesh in another
> program, so all the points lie on a surface in a very regular pattern with no
> duplicate points (I clean the point cloud of them manually just in case).  I
> also make sure that there is at least 4 points to work with.
>
> Here is the useful info:
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel    K;
> typedef CGAL::Alpha_shape_vertex_base_3<K>    Vb;
> typedef CGAL::Triangulation_hierarchy_vertex_base_3<Vb>    Vbh;
> typedef CGAL::Alpha_shape_cell_base_3<K>    Fb;
> typedef CGAL::Triangulation_data_structure_3<Vbh,Fb>      Tds;
> typedef CGAL::Delaunay_triangulation_3<K,Tds>      Delaunay;
> typedef CGAL::Triangulation_hierarchy_3<Delaunay>    Delaunay_hierarchy;
> typedef CGAL::Alpha_shape_3<Delaunay_hierarchy>    Alpha_shape_3;
>
> Delaunay_hierarchy dTet;
> for (unsigned int i = 0; i < mPoints.length(); ++i){
>         dTet.insert(Point_3(mPoints[i].x, mPoints[i].y, mPoints[i].z));}
>
> //  At this line all is well, and I use the Delaunay hierarchy to instantiate
> an
> //  Alpha_shape_3 object.
> Alpha_shape_3 mesh(dTet);
>
> //  Which errors with this:
> CGAL error: assertion violation!
> Expression : ! CGAL_NTS is_zero(den)
> File       : C:\Program 
> Files\CGAL-3.4\include\CGAL/constructions/kernel_ftC3.h
> Line	  : 
>
> No line number is given, but there is only one occurence of CGAL_NTS
> is_zero(den) in the file and that is for calculating the determinant of a
> matrix for the squared_radiusC3 function.  However, for the alpha number I've
> been supplying (what I think) is decent range of real numbers, all with the
> same error.  And I have also tried using the find_optimal_alpha function with 
> a
> few low solid component numbers, again the same error.
>
> I have seen others get this error in 2D for collinear points, but as I am
> building my triangulation incrementally using Delaunay rules, I can't see how
> the above is a possible outcome.
>
> Does anybody have any suggestions?
>   

--
Mariette Yvinec
Geometrica project team
INRIA  Sophia-Antipolis