CGAL users discussion list

[<>]

Hi,
 
I took a look at the incremental builder like you suggested.
 
I was hoping I could build a polyhedron out of just the boundary faces of a delaunay triangulation.
 
Here is what I came up with:
 
My construction code is as follows: first add all vertices, then using a vector of triangles (indices to the vertices, computed earlier) add them as facets to the polyhedron.
 
The data is contained like this:
 
struct triangle {
    int indexA, indexB, indexC;
};
 
std::vector<Point> m_vertices; // all the vertices of the polyhedron/triangulation
std::vector<triangle> m_triangles; // contains references to the vertices in m_vertices
 
I tested this with some debug data: one polyhedron consisting of 4 and another one with 5 vertices. I worked out the triangle vertex order on paper, and this produced correct results.
 
I also fed the output of qhull to this code (9 vertices), and it too produced correct results. So I believe this part of my code is correct.
 
void operator() (HDS& hds)
{
    CGAL::Polyhedron_incremental_builder_3<HDS> B(hds, true);
    B.begin_surface(m_vertices.size(), m_triangles.size());
 
    for(std::vector<Point>::iterator vertexIterator = m_vertices.begin(); vertexIterator != m_vertices.end(); ++vertexIterator)
    {
        B.add_vertex(*vertexIterator);
    }
 
    for(std::vector<triangle>::iterator triangleIterator = m_triangles.begin(); triangleIterator != m_triangles.end(); ++triangleIterator)
    {
        B.begin_facet();
        B.add_vertex_to_facet((*triangleIterator).indexA);
        B.add_vertex_to_facet((*triangleIterator).indexB);
        B.add_vertex_to_facet((*triangleIterator).indexC);
        B.end_facet();
    }
 
    //
    //if ( B.check_unconnected_vertices() )
    //{
    //    B.remove_unconnected_vertices();
    //}
 
    B.end_surface();
}
 
Now then, to convert my CGAL triangulation into the representation of m_vertices and m_triangles...
 
I only want the convex hull, so I only consider the cells connected to the infinite vertex.
 
Then it gets a little sketchy.. from the facet of the exterior cell (incident to the infinite vertex) making up part of the polyhedron surface, I need the counter-clockwise (?) order of the vertices. I based myself on http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/TriangulationDS_3/Chapter_main.html for this. In the first image, the vertices indices are shown.
 
std::vector<Vertex_handle> m_vertexHandles;
 
void fillWithRealData(const Dt& DelaunayTriangulation)
{
    // store the vertex handles

    for(Finite_vertices_iterator DverticesIterator = DelaunayTriangulation.finite_vertices_begin(); DverticesIterator != DelaunayTriangulation.finite_vertices_end(); ++DverticesIterator)

        m_vertexHandles.push_back(DverticesIterator);
 
    for(int i = 0; i < m_vertexHandles.size(); ++i)
        m_vertices.push_back(m_vertexHandles[i]->point());
 
    // get all the cells connected to the infinite vertex (cells that make up the boundary/surface)
    std::vector<cellHandleDh> exteriorCells;
    DelaunayTriangulation.incident_cells(DelaunayTriangulation.infinite_vertex(), std::back_inserter(exteriorCells));
    triangle triangleInstance;
 
    // for these exterior cells, get the triangle vertices that make up the surface of the triangulation and add them to m_triangles
    for(std::vector<cellHandleDh>::iterator triangleIterator = exteriorCells.begin(); triangleIterator != exteriorCells.end(); ++triangleIterator)
    {
        // check which of the vertices are the correct facet, and which order the vertices must appear in
        if((*triangleIterator)->vertex(0) == DelaunayTriangulation.infinite_vertex())
        {
            triangleInstance.indexA = getVertexHandleIndex((*triangleIterator)->vertex(3));
            triangleInstance.indexB = getVertexHandleIndex((*triangleIterator)->vertex(2));
            triangleInstance.indexC = getVertexHandleIndex((*triangleIterator)->vertex(1));
        }
        else if((*triangleIterator)->vertex(1) == DelaunayTriangulation.infinite_vertex())
        {
            triangleInstance.indexA = getVertexHandleIndex((*triangleIterator)->vertex(0));
            triangleInstance.indexB = getVertexHandleIndex((*triangleIterator)->vertex(2));
            triangleInstance.indexC = getVertexHandleIndex((*triangleIterator)->vertex(3));
        }
        else if((*triangleIterator)->vertex(2) == DelaunayTriangulation.infinite_vertex())
        {
            triangleInstance.indexA = getVertexHandleIndex((*triangleIterator)->vertex(0));
            triangleInstance.indexB = getVertexHandleIndex((*triangleIterator)->vertex(3));
            triangleInstance.indexC = getVertexHandleIndex((*triangleIterator)->vertex(1));
        }
        else if((*triangleIterator)->vertex(3) == DelaunayTriangulation.infinite_vertex())
        {
            triangleInstance.indexA = getVertexHandleIndex((*triangleIterator)->vertex(2));
            triangleInstance.indexB = getVertexHandleIndex((*triangleIterator)->vertex(0));
            triangleInstance.indexC = getVertexHandleIndex((*triangleIterator)->vertex(1));
        }
        else
            assert(0);
            m_triangles.push_back(triangleInstance);
        }
 
   

}

 
int getVertexHandleIndex(Vertex_handle vertexHandle)
{
    for(int i = 0; i < m_vertexHandles.size(); ++i)
    {
        if(m_vertexHandles[i] == vertexHandle)
            return i;
    }
 
    assert(0);
    return -1;
}
 
I also tested this with points generated by CGAL in a sphere, but this didn't produce correct results.
Polyhedron::is_closed() and Polyhedron::is_valid() didn't return true and I get:
 
====
summe border halfedges (2*nb) = 0
vertex 0
    halfedge 0
    halfedge 1
    halfedge 2
    halfedge 3
vertex 1
    halfedge pointer in vertex corrupted.
end of CGAL::HalfedgeDS_const_decorator<HDS>::is_valid(): structure is NOT VALID
.
counting halfedges failed.
====
 
 
Does the order in which the triangles are added (B.begin_facet() ...) matter perhaps?
 
I also looked at Polyhedron_3.make_triangle(...), but I assume this doesn't do what I want? It didn't really produce correct results as far as I know.
 
Any help is greatly appreciated.
   

> Date: Wed, 19 Nov 2008 12:09:56 -0800
> From:
> To:
> Subject: Re: [cgal-discuss] Triangulation to Polyhedron
>
> i had the same problem, i solved it by using the incremental builder.
>
> in my program, i need to re-triangulate triangles on a 3D surface. i
> first do the triangulation in 2D. and then use the incremental builder
> to create the same triangulation in 3D in the polyhedron_3 format. and
> finally attach the re-triangulated piece to the original surface.
>
> actually, i didn't use the triangulation feature of the CGAL, i used
> another library. because in my case, the thing that needs to be
> triangulated may be a concave polygon. i don't know how CGAL can do
> the triangulation while preserving the concave border.
>
>
>
> On Wed, Nov 19, 2008 at 11:48 AM, <> wrote:
> > Hi,
> >
> > How do you convert a Delaunay_triangulation_3 object to a Polyhedron_3
> > object?
> >
> > I tried to use CGAL::assign(), but it didn't work.
> >
> >
> > Thank you.
> >
> > ________________________________
> > Alle fun stuff van Messenger nu verzameld op één coole site! Windows Live
> > Messenger
>
>
>
> --
> Dept. of Computer Science
> University of California, Davis
> Homepage:http://wwwcsif.cs.ucdavis.edu/~yans/
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

---

De nieuwe Hotmail maakt je leven nog makkelijker Wees er als eerste bij.