# Re: Normal generation out of 3d alpha shapes Classic List Threaded 2 messages Reply | Threaded
Open this post in threaded view
|

## Re: Normal generation out of 3d alpha shapes

 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. 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). 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 -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

## Re: Normal generation out of 3d alpha shapes

 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; // 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] = mAlphaShape->triangle(*it).vertex(i).x();       tri[i] = mAlphaShape->triangle(*it).vertex(i).y();       tri[i] = mAlphaShape->triangle(*it).vertex(i).z();     }     for(uint i = 0; i < 3; i++)       VerticesOut.add1Value(tri[i]);     Vec3 v0 = tri - tri;     Vec3 v1 = tri - tri;     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] = 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? [hidden email] 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 CgalVertexBase;   typedef CGAL::Triangulation_hierarchy_vertex_base_3 CgalTriangulationHierarchieVertexBase;   typedef CGAL::Alpha_shape_cell_base_3 CgalAlphaShapeCellBase;   typedef CGAL::Triangulation_data_structure_3 CgalTriangulationDataStructure;   typedef CGAL::Delaunay_triangulation_3   CgalDelaunayTriangulation;   typedef CGAL::Triangulation_hierarchy_3 CgalTriangulationHierarchy;   typedef CGAL::Alpha_shape_3 CgalAlphaShape3;   typedef CgalKernel::Point_3 CgalPoint3;   typedef CgalAlphaShape3::Alpha_iterator CgalAlphaIterator;   typedef CgalAlphaShape3::NT CgalAlphaNT; -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss