CGAL users discussion list

[Jonas Schild <>]

Hi Monique, hi Andreas,

thank you for your kind replies. I've tried to figure it out myself but 
stumble over the complexity of the data structures. Perhaps you or so 
else could help me by looking on the code.

This is how I currently extract the vertices from the alpha shape:

vec3 tri[3];
// my two output lists
VerticesOut.clear();
NormalsOut.clear();

CgalAlphaShape3::Alpha_shape_facets_iterator it = 
mAlphaShape->alpha_shape_facets_begin();
CgalAlphaShape3::Alpha_shape_facets_iterator itEnd = 
mAlphaShape->alpha_shape_facets_end();

for ( ; it != itEnd ; ++it )
{
   for(uint i = 0; i < 3; i++)
   {
     tri[i][0] = mAlphaShape->triangle(*it).vertex(i).x();
     tri[i][1] = mAlphaShape->triangle(*it).vertex(i).y();
     tri[i][2] = mAlphaShape->triangle(*it).vertex(i).z();
   }

   for(uint i = 0; i < 3; i++)
     VerticesOut.add1Value(tri[i]);

   Vec3 v0 = tri[1] - tri[0];
   Vec3 v1 = tri[2] - tri[0];

   Vec3 normal = v0 ^ v1;
   normal.normalize();
   NormalsOut.add1Value(normal);
}

It works but the Normals arbitrarily point towards the inside or outside 
of the shape, where I want them all to point outwards.

I changed the it iterator to CgalAlphaShape3::Alpha_shape_cells_iterator 
it = mAlphaShape->alpha_shape_cells_begin() to get the cells, but then 
using the triangle function (tri[i][0] = 
mAlphaShape->triangle(*it,j).vertex(i).x();) for all j=0..3 triangles of 
the cell, gives me a type mismatch error. It expects a cell_handle, so 
is the cell_iterator not compatible?
Even if this worked, I still wonder how then to create the correct 
normals as the triangle DS doesn't provide a normal by itself.
Thinking about the function that Adreas proposed (static int 
Triangulation_utils_3<..>::vertex_triple_index(const int i, const int j) 
), I'm not sure what to do. Am I to check for each vertex i of a cell 
the j=0..2 opposing vertices to construct the 4 triangles of a cell? I 
assume that some cells might include the infinite vertex, so is this 
really helpful?



 wrote:
> Jonas Schild wrote:
>
> > 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
>
> There is no ccw function in 3D.
sorry ;-)
> You can look at the beginning of the User manual of 3D Triangulation 
> Data Structure, you will find the explanation of the orientation of 
> cells.
> You can see there how to get vertices of the facet opposite to vertex 
> i in a cell in an ordered way (be careful, it depends on the parity of 
> i).
what is meant by the parity? I'm not sure what could help me the to be 
honest...
> Also, in case it may help, in the reference manual of 
> CGAL::Triangulation_3 you can find
>
> Triangle        t.triangle ( const Cell_handle c, int i)
>         Returns the triangle formed by the three vertices of facet 
> (c,i). The triangle is oriented so that its normal points to the 
> inside of cell c.
> The typedef at the top of the page tells you that the type returned is 
> in fact a CGAL::Triangle_3, if you are using the CGAL Kernel as traits 
> class.
>
> Best regards
>     Monique Teillaud

Thanks so far for the prompt and nice replies. I hope to improve on 
understanding :)
Best,
Jonas

PS: I forgot to include the construction of CGAL i'm using:
struct CgalKernel : CGAL::Exact_predicates_inexact_constructions_kernel {};
 typedef CGAL::Alpha_shape_vertex_base_3<CgalKernel> CgalVertexBase;
 typedef CGAL::Triangulation_hierarchy_vertex_base_3<CgalVertexBase> 
CgalTriangulationHierarchieVertexBase;
 typedef CGAL::Alpha_shape_cell_base_3<CgalKernel> CgalAlphaShapeCellBase;
 typedef 
CGAL::Triangulation_data_structure_3<CgalTriangulationHierarchieVertexBase,CgalAlphaShapeCellBase> 
CgalTriangulationDataStructure;
 typedef 
CGAL::Delaunay_triangulation_3<CgalKernel,CgalTriangulationDataStructure>  
CgalDelaunayTriangulation;
 typedef CGAL::Triangulation_hierarchy_3<CgalDelaunayTriangulation> 
CgalTriangulationHierarchy;
 typedef CGAL::Alpha_shape_3<CgalTriangulationHierarchy> CgalAlphaShape3;
 typedef CgalKernel::Point_3 CgalPoint3;
 typedef CgalAlphaShape3::Alpha_iterator CgalAlphaIterator;
 typedef CgalAlphaShape3::NT CgalAlphaNT;