Re: Normal generation out of 3d alpha shapes

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Normal generation out of 3d alpha shapes

Monique Teillaud
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

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?


[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<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;


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss