CGAL users discussion list

[Andreas Fabri <>]

Jonas Schild wrote:
> Hi all,
>
> I have the following problem:
>
> I'm constructing a 3d alpha shape from a set of points using CGAL. After 
> creation of the alpha shape, I'm iterating over all facets to extract 
> the triangles. But:
> The orientation of the normal (either by using cross product or using 
> CGAL's ortho_vector(point, point, point) of which results are the same) 
> is partially wrong. I've read that the orientation of the triangle is 
> based on orientation of the cell (i.e. pointing into the cell). However, 
> I'm not able to retrieve the normals pointing outside the alpha shape. 
> Part of the problem is, that for certain alpha values, the constructed 
> shape is no solid object. Is it possible to iterate only over alphas 
> where the shape is solid, not necessarily convex?
>
> Furthermore, I don't understand how ccw(int) on the triangulation 
> structure is supposed to work regarding finding the correct orientation 
> thus the normals are pointing outside the volume.

Hi Jonas,

Here comes a partial answer.

With ccw(int) you refer probably to the base class of all 3D traingulations:
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/TriangulationDS_3_ref/Class_Triangulation_utils_3.html#Cross_link_anchor_994


As the manual says ccw(int) only makes sense when it is 2D.

What you should use is the undocumented funcyion:

static int Triangulation_utils_3<..>::vertex_triple_index(const int i, const 
int j)
  {
    // indexes of the  jth vertex  of the facet of a cell
    // opposite to vertx i
      CGAL_triangulation_precondition( ( i >= 0 && i < 4 ) &&
                                     ( j >= 0 && j < 3 ) );
    return tab_vertex_triple_index[i][j];
  }

The fact that it is undocumented is a bug.

Hope this helps,

andreas

> Hopefully someone could give me a hint or two ;)
>
> Thanks in advance
> Jonas