# Re: Normal generation out of 3d alpha shapes

6 messages
Open this post in threaded view
|

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

 Andreas Fabri wrote: > 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. really? I would say it is more like a matter of taste...         Monique -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

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

 This is how I got the correct normals for all the boundary facets. The relevant code. Alpha_shape_3 *as; list facets; list vertices; ostringstream facetStream; as->get_alpha_shape_facets(back_inserter(facets), Alpha_shape_3::REGULAR); as->get_alpha_shape_vertices(back_inserter(vertices), Alpha_shape_3::REGULAR); cout<<"\n Number of boundary facets = "<
Open this post in threaded view
|

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

 Santosh Tiwari wrote: > This is how I got the correct normals for all the boundary facets. > >   Hi Santosh, I tried using your code, but failed with correctly setting up the Facet and Vertex data types, so I was not able to create the lists correctly. I then only used your normals to my vertices but they don't seem to be correct. My vertices seem to be in a different order. Could you help me out with your typedefs? Thanks for kindly providing your code! Jonas > The relevant code. > > > Alpha_shape_3 *as; > list facets; > list vertices; > ostringstream facetStream; > > as->get_alpha_shape_facets(back_inserter(facets), Alpha_shape_3::REGULAR); > as->get_alpha_shape_vertices(back_inserter(vertices), > Alpha_shape_3::REGULAR); > > cout<<"\n Number of boundary facets = "< cout<<"\n Number of vertices = "< > facetStream< facetStream< facetStream<<*as; > > > //You can now read the facetStream. Here is some code to read it. > > string facetString(facetstream.str()); > istringstream in; > in.str(facetString); > in>>numVertices; > in>>numFacets; > > vertices = new double*[numVertices]; > for (i=0; i vertices[i] = new double[3]; > in>>x>>y>>z; > vertices[i][0] = x; > vertices[i][1] = y; > vertices[i][2] = z; > } > > facets = new unsigned long int*[numFacets]; > for (i=0; i facets[i] = new unsigned long int[3]; > in>>v1>>v2>>v3; > facets[i][0] = v1; > facets[i][1] = v2; > facets[i][2] = v3; > } > > for(i=0; i x1 = vertices[facets[i][0]][0]; > y1 = vertices[facets[i][0]][1]; > z1 = vertices[facets[i][0]][2]; > > x2 = vertices[facets[i][1]][0]; > y2 = vertices[facets[i][1]][1]; > z2 = vertices[facets[i][1]][2]; > > x3 = vertices[facets[i][2]][0]; > y3 = vertices[facets[i][2]][1]; > z3 = vertices[facets[i][2]][2]; > } > > //You now have all the facets. You can write them to a STL file. > //You can compute the normals for every facet now. > //Here is some code to compute the normals. > > a1 = x3 - x2; > a2 = y3 - y2; > a3 = z3 - z2; > b1 = x2 - x1; > b2 = y2 - y1; > b3 = z2 - z1; > n1 = a2*b3 - a3*b2; > n2 = a1*b3 - a3*b1; > n3 = a1*b2 - a2*b1; > res = sqrt(n1*n1 + n2*n2 + n3*n3); > n1 /= res; > n2 /= res; > n3 /= res; > > I personally do not prefer accessing the internal data structure of a > library even if it permits that. It is very difficult to debug unless you > know the data structure really well. > > __ > Santosh Tiwari > EIB-326 Clemson University > http://www.clemson.edu/~stiwari/> > > > -----Original Message----- > From: [hidden email] > [mailto:[hidden email]] > Sent: Sunday, May 18, 2008 10:54 AM > To: [hidden email] > Subject: Re: [cgal-discuss] Normal generation out of 3d alpha shapes > > Andreas Fabri wrote: >   >> 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/Cl> ass_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. >>     > > really? I would say it is more like a matter of taste... > > Monique >   -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|