Subversion Repositories gelsvn

/* ----------------------------------------------------------------------- *

 * This file is part of GEL, http://www.imm.dtu.dk/GEL

 * Copyright (C) the authors and DTU Informatics

 * For license and list of authors, see ../../doc/intro.pdf

 * ----------------------------------------------------------------------- */

/**

 * @file Manifold.h

 * @brief The Manifold class is the main data structure of HMesh - the actual mesh.

 */

#include <algorithm>

#include <CGLA/Vec3d.h>

#include "ConnectivityKernel.h"

#include "Iterators.h"

#include "Walker.h"

#include "AttributeVector.h"

}

     representation must be manifold (although exceptions could be made) the class is thus named.

     Manifold contains many functions for mesh manipulation and associated the position attribute

        /// Vector type used for positions of vertices.

        typedef CGLA::Vec3d Vec;

        /// Default constructor

        Manifold();

        /** \brief Build a manifold. 

        The arguments are the number of vertices, no_vertices, the vector of vertices, vertvec, the number of faces, no_faces. 

        facevecis an array where each entry indicates the number of vertices in that face. 

        The array indices contains all the corresponding vertex indices in one concatenated list. */

        void build( size_t no_vertices,

                    const float* vertvec,

                    size_t no_faces,

                    const int* facevec,

                    const int* indices);

        /** \brief Build a manifold.

         This function is for vertices given in double precision.

         The arguments are the number of vertices, no_vertices, the vector of vertices, vertvec, the number of faces, no_faces.

         facevecis an array where each entry indicates the number of vertices in that face.

         The array indices contains all the corresponding vertex indices in one concatenated list. */

        void build( size_t no_vertices,

                   const double* vertvec,

                   size_t no_faces,

                   const int* facevec,

                   const int* indices);

        /// Build a manifold from a TriMesh

        void build(const Geometry::TriMesh& mesh);

        /// Add a face to the Manifold

        FaceID add_face(std::vector<Manifold::Vec> points);

//        /** Removes a face from the Manifold. If it is an interior face it is simply replaces

//         by an InvalidFaceID. If the face contains boundary edges, these go away. */

//

//         This function will remove the faces on either side and the edge itself in the process. */

//        bool remove_edge(HalfEdgeID hid);

//

//        /** Remove a vertex from the Manifold.

//         This function merges all faces around the vertex into one and then removes 

//         this resulting face. */

//        bool remove_vertex(VertexID vid);

        /// number of  vertices

        size_t no_vertices() const { return kernel.no_vertices();}

        /// number of active faces

        size_t no_faces() const { return kernel.no_faces();}

        /// number of active halfedges

        size_t no_halfedges() const { return kernel.no_halfedges();}

        /// number of total vertices in kernel

        size_t allocated_vertices() const { return kernel.allocated_vertices();}

        /// number of total faces in kernel

        size_t allocated_faces() const { return kernel.allocated_faces();}

        /// number of total halfedges in kernel

        size_t allocated_halfedges() const { return kernel.allocated_halfedges();}

        /// check if ID of vertex is in use

        bool in_use(VertexID id) const { return kernel.in_use(id);}

        /// check if ID of face is in use

        bool in_use(FaceID id) const { return kernel.in_use(id);}

        /// check if ID of halfedge is in use

        bool in_use(HalfEdgeID id) const { return kernel.in_use(id);}

        /// Iterator to first VertexID, optional argument defines if unused items should be skipped

        VertexIDIterator vertices_begin(bool skip = true) const { return kernel.vertices_begin();}

        /// Iterator to first FaceID, optional argument defines if unused items should be skipped

        FaceIDIterator faces_begin(bool skip = true) const { return kernel.faces_begin();}

        /// Iterator to first HalfEdgeID, optional argument defines if unused items should be skipped

        HalfEdgeIDIterator halfedges_begin(bool skip = true) const { return kernel.halfedges_begin();}

        /// Iterator to past the end VertexID

        VertexIDIterator vertices_end() const { return kernel.vertices_end();}

        /// Iterator topast the end FaceID

        FaceIDIterator faces_end() const { return kernel.faces_end();}

        /// Iterator to past the end HalfEdgeID

        HalfEdgeIDIterator halfedges_end() const {return kernel.halfedges_end(); }  

		/** \brief Bridge f0 and f1 by connecting the vertex pairs given in pairs.

		 This function creates a cylindrical connection between f0 and f1. f0 and f1 are removed and the vertices 

		 given in pairs are connected by edges. The result is a cylindrical connection that changes the genus of the object.

		 This function leaves all error chethising in the hands of the user (for now). The faces clearly should not have any 

		 vertices or edges in common as this will create a non-manifold situation. Also the faces should face towards or away 

		 from each other and be in a position where it is reasonable to make the bridge. The connections should also make sense 

		 from a geometric point of view and should be in a counter clothiswise loop on f0 and a clothiswise loop on f1. No need to 

		 connect all vertices.

		 The function returns a vector of HalfEdgeIDs. Those are, of course, the connecting halfedges - also the opposite edges.

		 */

		std::vector<HalfEdgeID> bridge_faces(FaceID f0, FaceID f1, const std::vector<std::pair<VertexID, VertexID> >& pairs);

        /** \brief Collapse the halfedge h.

        The argument h is the halfedge being removed. The vertex v=h->opp->vert is the one being removed while h->vert survives.

        The final argument indicates whether the surviving vertex should have the average position of the former vertices.

        By default false meaning that the surviving vertex retains it position.

        This function is not guaranteed to keep the mesh sane unless, precond_collapse_edge has returned true !! */

        void collapse_edge(HalfEdgeID h, bool avg_vertices = false);

        /** \brief Split a face.

        The face, f, is split by creating an edge with endpoints v0 and v1 (the next two arguments). 

        The vertices of the old face between v0 and v1 (in counter clothiswise order) continue to belong to f. 

        The vertices between v1 and v0 belong to the new face. A handle to the new face is returned. */

        FaceID split_face_by_edge(FaceID f, VertexID v0, VertexID v1);

        /** \brief Split a polygon, f, by inserting a vertex at the barycenter.			

        This function is less likely to create flipped triangles than the split_face_triangulate function. 

        On the other hand, it introduces more vertices and probably makes the triangles more acute.

        A handle to the inserted vertex is returned. */

        VertexID split_face_by_vertex(FaceID f);

       // VertexID split_face_by_vertex(HalfEdgeID h);

        /** \brief Insert a new vertex on halfedge h.

        The new halfedge is insterted as the previous edge to h.

        A handle to the inserted vertex is returned. */

        VertexID split_edge(HalfEdgeID h);

        /** \brief Stitch two halfedges.

         Two boundary halfedges can be stitched together. This can be used to build a complex mesh

         from a bunch of simple faces. */

        bool stitch_boundary_edges(HalfEdgeID h0, HalfEdgeID h1);

        /** \brief Merges two faces into a single polygon. 

        The first face is f. The second face is adjacent to f along the halfedge h. 

        This function returns true if the merging was possible and false otherwise. 

        Currently merge only fails if the mesh is already illegal. Thus it should, in fact, never fail. */

        bool merge_faces(FaceID f, HalfEdgeID h);

		/** \brief Merge all faces in the one ring of a vertex into a single polygon.

		The vertex is given by v.

		The return value is the FaceID of the resulting polygonal face. 

		InvalidFaceID is returned if 

		- the input vertex is not in use or 

		- the input vertex has valence less than two which is a degenerate case.

		- the input vertex is a boundary vertex of valence two - i.e. adjacent to just one face.

		- the same halfedge appears in two faces of the one ring of the input vertex: I.e.

		the input vertex is twice adjacent to the same face!

		Note that this function can create some unusual and arguably degenerate meshes. For instance, 

		two triangles which share all vertices is collapsed to a single pair of vertices connected by 

		a pair of halfedges bounding the same face. */

		FaceID merge_one_ring(VertexID v, float max_loop_length = FLT_MAX);

        /** \brief Close hole given by the invalid face of halfedgehandle h.

         returns FaceID of the created face or the face that is already there if the 

         face was not InvalidFaceID. */

        FaceID close_hole(HalfEdgeID h);

        /// \brief Flip an edge h. 

        void flip_edge(HalfEdgeID h);

        /// Return reference to position given by VertexID

        Vec& pos(VertexID id);

        /// Return const reference to position given by VertexID

        const Vec& pos(VertexID id) const;

        /// Clear the mesh. Remove all faces, halfedges, and vertices.

    private:

        // private template for building the manifold from various types

        template<typename size_type, typename float_type, typename int_type>

                            const float_type* vertvec,

                            size_type no_faces,

                            const int_type* indices);

    };

    Performs a series of tests to chethis that this is a valid manifold.

    This function is not rigorously constructed but seems to catch all problems so far. 

    The function returns true if the mesh is valid and false otherwise. */

    void bbox(const Manifold& m, Manifold::Vec& pmin, Manifold::Vec& pmax);

    /** \brief Test for legal edge collapse.

    The argument h is the halfedge we want to collapse. 

    If this function does not return true, it is illegal to collapse h. 

    The reason is that the collapse would violate the manifold property of the mesh.

    The test is as follows:

    1.  For the two vertices adjacent to the edge, we generate a list of all their neighbouring vertices. 

    We then generate a  list of the vertices that occur in both these lists. 

    That is, we find all vertices connected by edges to both endpoints of the edge and store these in a list.

    2.  For both faces incident on the edge, chethis whether they are triangular. 

    If this is the case, the face will be removed, and it is ok that the the third vertex is connected to both endpoints. 

    Thus the third vertex in such a face is removed from the list generated in 1.

    3.  If the list is now empty, all is well. 

    Otherwise, there would be a vertex in the new mesh with two edges connecting it to the same vertex. Return false.

    int valency(const Manifold& m, VertexID v);

    /// Compute the number of edges of a face

    int no_edges(const Manifold& m, FaceID f);

    /** Compute the normal of a face. If the face is not a triangle,

    Manifold::Vec normal(const Manifold& m, FaceID f);

    *******************************************************************/

    inline Walker Manifold::walker(VertexID id) const

    { return Walker(kernel, kernel.out(id)); }

    { return Walker(kernel, kernel.last(id)); }

    inline Walker Manifold::walker(HalfEdgeID id) const