Subversion Repositories gelsvn

#ifndef __HMESH_MANIFOLD_H

#ifndef __HMESH_MANIFOLD_H__

#define __HMESH_MANIFOLD_H

#define __HMESH_MANIFOLD_H__

namespace HMesh

namespace Geometry

	class VertexCirculator;

    // forward declaration

	class FaceCirculator;

    class IndexedFaceSet;

	/** \brief A Data structure representing an open or closed manifold.

namespace HMesh

			Manifold keeps lists of the entities making up a halfedge mesh

{

			and provides basic functions for creating new faces, halfedges

    /** The Manifold class represents a halfedge based mesh. Since meshes based on the halfedge

			and vertices. There are also primitive operations for editing 

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

			such as edge collapse. */

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

	class Manifold

     with vertices.*/

		{

			std::list<Vertex> vertex_db;

    class Manifold

			std::list<Face> face_db;

    {

			std::list<HalfEdge> halfedge_db;

    public:

			bool erase_immediately;

        /// Vector type used for positions of vertices.

			std::vector<VertexIter> unused_vertices;

        typedef CGLA::Vec3d Vec;

			std::vector<FaceIter> unused_faces;

			std::vector<HalfEdgeIter> unused_halfedges;

        /// Default constructor

        Manifold();

			/** Remove a face if it contains only two edges.

        /** \brief Build a manifold. 

					This is an auxiliary function called from collapse_halfedge. */

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

			void remove_face_if_degenerate(HalfEdgeIter);

        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. */

			Manifold(const Manifold&) {}

        void build( size_t no_vertices,

			/**< Empty copy constructor.

                    const float* vertvec,

				 Copying a manifold will not work, since faces, vertices, and

                    size_t no_faces,

				 halfedges contain iterators pointing to other faces, vertices,

                    const int* facevec,

				 and halfedges. These pointers would need to be changed if the 

                    const int* indices);

				 mesh were copied. In other words, we would need to walk the

				 entire mesh. This may be required but it should not be an 

        /** \brief Build a manifold.

				 operation that is easily invoked by calling the copy constructor.

         This function is for vertices given in double precision.

				 Hence, this operator is made private.		*/

         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.

			const Manifold& operator=(const Manifold&) {return *this;}

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

			/**< Empty assignment operator.

        void build( size_t no_vertices,

				 The assignment operator is private for the same reason that the

                   const double* vertvec,

				 copy constructor is private. */

                   size_t no_faces,

                   const int* facevec,

		public:

                   const int* indices);

        /// Build a manifold from a TriMesh

			Manifold(): erase_immediately(true) {}

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

			///< Construct an empty manifold.

        /// Add a face to the Manifold

			bool is_valid();

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

			/**< Performs a series of tests to check that this is a valid manifold.

				 This function is not rigorously constructed but seems to catch

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

				 all problems so far. The function returns true if the mesh is 

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

				 valid and false otherwise.	*/

//        bool remove_face(FaceID fid);

//

			void enumerate_vertices();

//        /** Remove an edge from the Manifold.

			/**< Give each vertex a unique id corresponding to its iterator

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

				 position. Value is stored in the touched attribute. */

//        bool remove_edge(HalfEdgeID hid);

//

			void enumerate_halfedges();

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

			/**< Give each halfedge a unique id corresponding to its iterator

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

				 position. Value is stored in the touched attribute. */

//         this resulting face. */

//        bool remove_vertex(VertexID vid);

			void enumerate_faces();

			/**< Give each face a unique id corresponding to its iterator

        /// number of  vertices

				 position. Value is stored in the touched attribute. */

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

        /// number of active faces

			size_t no_faces() const {return face_db.size();}

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

			///< Return the number of faces.

        /// number of active halfedges

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

			size_t no_halfedges() const {return halfedge_db.size();}

			///< Return the number of halfedges.

        /// number of total vertices in kernel

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

			size_t no_vertices() const {return vertex_db.size();}

        /// number of total faces in kernel

			///< Return the number of vertices

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

        /// number of total halfedges in kernel

			VertexIter create_vertex(const CGLA::Vec3f& pos);

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

			///< Create a new vertex.

        /// check if ID of vertex is in use

			FaceIter create_face();

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

			/**< Create a new face.

        /// check if ID of face is in use

				 An iterator to the face is returned. When a face f is initially

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

				 created, is_used(f) will return false. */

        /// check if ID of halfedge is in use

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

			HalfEdgeIter create_halfedge();

			/**< Create a new halfedge. An iterator to the halfedge is returned.

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

				 When h is initially created, is_used(h) returns false. */

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

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

			void clear();

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

			///< Clear the manifold, removing all data.

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

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

			void remove_unused();

			/**< Remove unused vertices, edges and faces from the database.

        /// Iterator to past the end VertexID

				 If delayed_erase mode is enabled, then until this function 

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

				 has been called, erased vertices, edges, and faces are just marked

        /// Iterator topast the end FaceID

				 as unused but not removed from their respective lists. */

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

        /// Iterator to past the end HalfEdgeID

			void delayed_erase();

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

			/**< Delay the actual removal of vertices, faces, and edges that

				 are erased.  In many cases, it is a problem if one cannot

				 test whether a vertex, halfedge, or face indicated by an

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

				 iterator is in use or has been removed from the mesh. One

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

				 solution to this problem is to delay the actual removal of

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

				 the vertex, edge or face. Instead when calling, say,

				 erase_face(f), all the iterators of f are assigned the

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

				 appropriate NULL value to indicate that they are not

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

				 pointing at anything, and f is added to a vector of faces

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

				 that need to be physically removed from the face_db.

		 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.

				 Since f is not erased, all iterators pointing at f remain

				 valid! And, importantly, it is possible to test whether f is

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

				 in use by calling is_used(f).

		 */

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

				 When remove_unused is called, the physical removal takes

				 place. Calling immediate_erase switches Manifold back to the

				 state where entities are removed as soon as the appropriate

        /** \brief Collapse the halfedge h.

				 erase function is called, and at the same time calls

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

				 remove_unused.

        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 immediate_erase();

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

			/**< Immediately remove erased entities.

				 Calling immediate_erase switches Manifold back to the state

        /** \brief Split a face.

				 where entities are removed as soon as the appropriate erase

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

				 function is called.

        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. */

				 See delayed_erase for more details, and note that

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

				 immediate_erase is the default mode.  */

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

			bool is_used(VertexIter v) const;

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

			/**< Test whether the vertex indicated by the argument v is used.

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

				 This function returns true if the vertex appears to have a 

        A handle to the inserted vertex is returned. */

				 valid outgoing halfedge iterator. */

        VertexID split_face_by_vertex(FaceID f);

       // VertexID split_face_by_vertex(HalfEdgeID h);

			bool is_used(FaceIter f) const;

			/**< Test whether the face indicated by the argument f is used.

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

				 This function returns true if the face appears to have a 

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

				 valid halfedge iterator. */

        A handle to the inserted vertex is returned. */

        VertexID split_edge(HalfEdgeID h);

			bool is_used(HalfEdgeIter h) const;

			/**< Test whether the halfedge indicated by the argument h is used.

        /** \brief Stitch two halfedges.

				 This function returns true if the halfedge appears to have a 

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

				 valid vertex iterator. */

         from a bunch of simple faces. */

        bool stitch_boundary_edges(HalfEdgeID h0, HalfEdgeID h1);

			void erase_halfedge(HalfEdgeIter h);			

			/**< Erase halfedge h. 

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

				 In general, you should never call this function but use the 

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

				 collapse_halfedge function instead since blindly erasing geometry

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

				 is most likely to invalidate the Mesh. Quite possibly this function

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

				 will be removed from the public interface. 

        bool merge_faces(FaceID f, HalfEdgeID h);

				 Note that if delayed_erase has been called, this function does

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

				 not immediately remove anything from the mesh. Instead the halfedge

		The vertex is given by v.

				 is reset to its initial state. Thus, iterators are not invalidated,

				 and it is possible to test whether h is used calling:

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

				 is_used(h). when remove_unused is called, the actual removal

		InvalidFaceID is returned if 

				 takes place.

		- 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.

			void erase_vertex(VertexIter v);

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

			/**< Erase vertex v.

		the input vertex is twice adjacent to the same face!

				 In general, you should never call this function but use the 

				 collapse_halfedge function to collapse the vertex away.

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

				 Blindly erasing is extremely likely to invalidate the

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

				 Mesh. Quite possibly this function will be removed from the

		a pair of halfedges bounding the same face. */

				 public interface. 

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

				 Note that if delayed_erase has been called, this function does

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

				 not immediately remove anything from the mesh. Instead the halfedge

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

				 is reset to its initial state. Thus, iterators are not invalidated,

         face was not InvalidFaceID. */

				 and it is possible to test whether v is used calling:

        FaceID close_hole(HalfEdgeID h);

				 is_used(v). when remove_unused is called, the actual removal

				 takes place.

        /// \brief Flip an edge h. 

			*/

        void flip_edge(HalfEdgeID h);

        /// Return reference to position given by VertexID

			void erase_face(FaceIter f);

        Vec& pos(VertexID id);

			/**< Erase face f.

        /// Return const reference to position given by VertexID

				 In general, you should never call this function but use 

        const Vec& pos(VertexID id) const;

				 collapse_halfedge in conjunction with other functions to

				 remove the face through (Euler) operations which preserve

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

				 the mesh in a valid state.

        void clear();

				 Blindly erasing is extremely likely to invalidate the

				 Mesh. Quite possibly this function will be removed from the

        /// Remove unused items from Mesh, map argument is to be used for attribute vector cleanups in order to maintain sync.

				 public interface. 

        void cleanup(IDRemap& map);

        /// Remove unused items from Mesh

				 Note that if delayed_erase has been called, this function does

        void cleanup();

				 not immediately remove anything from the mesh. Instead the face

				 is reset to its initial state. Thus, iterators are not invalidated,

        /// Returns a Walker to the out halfedge of vertex given by VertexID

				 and it is possible to test whether f is used calling:

        Walker walker(VertexID id) const;

				 is_used(f). when remove_unused is called, the actual removal

        /// Returns a Walker to the last halfedge of face given by FaceID

				 takes place.

        Walker walker(FaceID id) const;

			*/

        /// Returns a Walker to the halfedge given by HalfEdgeID

        Walker walker(HalfEdgeID id) const;

			HalfEdgeIter halfedges_begin();

			///< Return iterator pointing to the first halfedge.

    private:

			HalfEdgeIter halfedges_end();

			///< Return iterator pointing to beyond the last halfedge.

        ConnectivityKernel kernel;

			VertexIter vertices_begin();

        VertexAttributeVector<Vec> positions;

			///< Return iterator pointing to the first vertex.

        // private template for building the manifold from various types

			VertexIter vertices_end();

        template<typename size_type, typename float_type, typename int_type>

			///< Return iterator pointing to beyond the last vertex.

        void build_template(size_type no_vertices,

                            const float_type* vertvec,

			FaceIter faces_begin();

                            size_type no_faces,

			///< Return iterator pointing to the first face.

                            const int_type* facevec,

                            const int_type* indices);

			FaceIter faces_end();

			///< Return iterator pointing to beyond the last face.

        /// Set the next and prev indices of the first and second argument respectively.

        void link(HalfEdgeID h0, HalfEdgeID h1);

			bool collapse_precond(HalfEdgeIter h);

			/**< \brief HalfEdge collapse precondition.

        /// Glue halfedges by letting the opp indices point to each other.

        void glue(HalfEdgeID h0, HalfEdgeID h1);

			The argument h is the halfedge we want to collapse. 

        /// Auxiliary function called from collapse

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

        void remove_face_if_degenerate(HalfEdgeID h);

			h. The reason is that the collapse would violate the manifold property

			of the mesh.

        /// Ensure boundary consistency.

        void ensure_boundary_consistency(VertexID v);

			The test is as follows.

    };

			1. For the two vertices adjacent to the edge, we generate

    /** \brief Verify Manifold Integrity

			a list of all their neighbouring vertices. We then generate a 

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

			list of the vertices that occur in both these lists. That is, 

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

			we find all vertices connected by edges to both endpoints

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

			of the edge and store these in a list.

    bool valid(const Manifold& m);

			2. For both faces incident on the edge, check whether they

    /// Calculate the bounding box of the manifold

			are triangular. If this is the case, the face will be removed,

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

			and it is ok that the the third vertex is connected to both 

			endpoints. Thus the third vertex in such a face is removed

    /// Calculate the bounding sphere of the manifold

			from the list generated in 1.

    void bsphere(const Manifold& m, Manifold::Vec& c, float& r);

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

    /** \brief Test for legal edge collapse.

			would be a vertex in the new mesh with two edges connecting

    The argument h is the halfedge we want to collapse. 

			it to the same vertex. Return false.

    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.

			4. TETRAHEDRON TEST:

    The test is as follows:

			If the valency of both vertices is 

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

			three, and the incident faces are triangles, we also disallow

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

			the operation. Reason: It introduces a vertex of valency two

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

			and if the final two polygons incident on the vertices 

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

			that are adjacent to the edge being collapsed are triangles, then

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

			the construction will collapse

    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. 

			5. VALENCY 4 TEST:

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

			If a face adjacent to the edge being collapsed is a triangle,

    4.  TETRAHEDRON TEST:

			it will disappear, and the valency of the final vertex beloning to

    If the valency of both vertices is three, and the incident faces are triangles, we also disallow the operation. 

			this edge will be reduced by one. Hence this valency should be at

    Reason: A vertex valency of two and two triangles incident on the adjacent vertices makes the construction collapse.

			least 4. A valency three vertex will be reduced to a valency two

    5.  VALENCY 4 TEST:

			vertex which is considered illegal.

    If a triangle is adjacent to the edge being collapsed, it disappears.

    This means the valency of the remaining edge vertex is decreased by one.

			6. PREVENT MERGING HOLES:

    A valency two vertex reduced to a valency one vertex is considered illegal.

			We do not want to collapse an edge if its end points are boundary

    6.  PREVENT MERGING HOLES:

			vertices, but its two adjacent faces are not NULL faces, because

    Collapsing an edge with boundary endpoints and valid faces results in the creation where two holes meet.

			in that case we create a vertex where two holes meet. A non manifold

    A non manifold situation. We could relax this...

			situation.	*/

	7. New test: if the same face is in the one-ring of both vertices but not adjacent to the common edge,

	then the result of a collapse would be a one ring where the same face occurs twice. This is disallowed as the resulting

	 face would be non-simple.	*/

			void collapse_halfedge(HalfEdgeIter h, bool=false);

    bool precond_collapse_edge(const Manifold& m, HalfEdgeID h);

			/**< Collapse the halfedge h.

    /** \brief Test fpr legal edge flip. 

			The argument h is the halfedge being removed. The vertex 

    Returns false if flipping cannot be performed. This is due to one of following: 

			v=h->opp->vert is the one being removed while h->vert survives.

    1.  one of the two adjacent faces is not a triangle. 

    2.  Either end point has valency three.

			The final argument is a boolean indicating whether the vertex

    3.  The vertices that will be connected already are. */

			that survives the collapse should have a position which is the

    bool precond_flip_edge(const Manifold& m, HalfEdgeID h);

			average of its own position and the vertex that is removed.

			By default false meaning that the surviving vertex retains it 

    /// Returns true if the halfedge is a boundary halfedge.

			position.

    bool boundary(const Manifold& m, HalfEdgeID h);

			This function is not guaranteed to keep the mesh sane unless,

    /// Return the geometric length of a halfedge.

			collapse_precond has returned true !!

    float length(const Manifold& m, HalfEdgeID h);

			*/

    /// Returns true if the vertex is a boundary vertex.

			FaceIter split_face(FaceIter f, VertexIter v0, VertexIter v1);

    bool boundary(const Manifold& m, VertexID v);

			/**< Split a face.

				 The face, f, is split by connecting two

    /// Compute valency, i.e. number of incident edges.

				 vertices v0 and v1 (the next two arguments). The vertices of

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

				 the old face between v0 and v1 (in counter clockwise order) 

				 continue to belong to f. The vertices between v1 and 

    /// Compute the vertex normal. This function computes the angle weighted sum of incident face normals.

				 v0 belong to the new face. An iterator to the new face is 

    Manifold::Vec normal(const Manifold& m, VertexID v);

				 returned. */

    /// Returns true if the two argument vertices are in each other's one-rings.

			VertexIter split_edge(HalfEdgeIter h);

    bool connected(const Manifold& m, VertexID v0, VertexID v1);

			/**< Insert a new vertex on halfedge h.

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

    /// Compute the number of edges of a face

				 An iterator to the inserted vertex is	returned. */

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

			void triangulate(FaceIter f);

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

			/**< Triangulate a polygonal face by repeatedly calling split_face.

    the normal is not defined, but computed using the first three

				 Triangulate iteratively splits triangles off a polygon. The first 

    vertices of the face. */

				 triangle split off is the one connecting f->last->vert and

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

				 f->last->next->next->vert.

			*/

    /// Compute the area of a face. 

    float area(const Manifold& m, FaceID f);

			VertexIter safe_triangulate(FaceIter f);

			/**< Triangulate a polygon, f, by inserting a vertex at the barycenter.

    /// Compute the perimeter of a face. 

				 All vertices in f are connected to the new vertex.				

    float perimeter(const Manifold& m, FaceID f);

				 The word "safe" means that it is less likely to create flipped

				 triangles than the normal triangulate. On the other hand, it 

    /// Compute the centre of a face

				 introduces more vertices and probably makes the triangles more

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

				 acute. This function simply calls face_insert_point.

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

				 The inserted vertex is returned.

    * Manifold code

			*/

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

			void face_insert_point(FaceIter f, VertexIter v);

    inline Manifold::Manifold(){}

			/**< Insert a new vertex, v, in a face, f.

				 This operation splits an N-gon into N triangles.

    inline Manifold::Vec& Manifold::pos(VertexID id)

				 In the current implementation the original face is erased. 

    { return positions[id]; }

				 This means that the iterator is not valid after the function

    inline const Manifold::Vec& Manifold::pos(VertexID id) const

				 returns. 

    { return positions[id]; }

			*/

			bool merge_faces(FaceIter f, HalfEdgeIter h);

    inline void Manifold::clear()

			/**< 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

        kernel.clear();

				 returns true if the merging was possible and false

        positions.clear();

				 otherwise. Currently merge only fails if the mesh is already

    }

				 illegal. Thus it should, in fact, never fail. */

    inline Walker Manifold::walker(VertexID id) const

			bool flip(HalfEdgeIter h);

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

			/**< Flip an edge h. Returns false if flipping cannot be performed.

    inline Walker Manifold::walker(FaceID id) const

				 This is either because one of the two adjacent faces is not

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

				 a triangle, or because either end point has valency three or

    inline Walker Manifold::walker(HalfEdgeID id) const

				 because the vertices that will be connected already are. */

    { return Walker(kernel, id); }

			void get_bbox(CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);

			/**< Return the bounding box of the manifold. The arguments pmin and pmax

    inline void Manifold::cleanup(IDRemap& map)

				 will contain the extreme corners of the box when the function 

    {   

				 returns.	*/

        kernel.cleanup(map);

        positions.cleanup(map.vmap);

			void get_bsphere(CGLA::Vec3f& c, float& r);

    }

			/**< Get a bounding sphere. When the function returns, c contains the

				 centre and r the radius. */ 

    inline void Manifold::cleanup()

		};

    {

        IDRemap map;

        Manifold::cleanup(map);

	inline HalfEdgeIter Manifold::halfedges_begin() 

    }

		{

}

#endif

#endif