/* brep.h: An edge-based Boundary Representation of solids, similar
 *         to the winged-edge data structure. */

#ifndef _BREP_H_
#define _BREP_H_

#ifdef __cplusplus
extern "C" {
#endif

/* ******************* The Topological Data Structure *********************/
/*
 * References:
 *
 * - Kevin Weiler, "Edge-based Data Structures for Solid Modeling in 
 *   Curved-Surface Environments", IEEE Computer graphics and Applications,
 *   January, 1985.
 * - Martti Mantyla and Reijo Sulonen, "GWB: A Solid Modeler with Euler
 *   Operators", IEEE Computer graphics and Applications, September 1982.
 * - Tony C. Woo, "A Combinatorial Analysis of Boundary Data Structure
 *   Schemata", IEEE Computer graphics and Applications, March 1985.
 * - Andrew S. Glassner, "Maintaining Winged-Edge Models", Graphics Gems II,
 *   James Arvo (editor), Academic Press, 1991
 * - Mark Segal and Carlo H. Sequin, "Partitioning Polyhedral Objects into
 *   Nonintersecting Parts", IEEE Computer graphics and Applications, January,
 *   1988.
 */

/* the boundary of a solid consists of one or more SHELLs.
 * User-supplied geometric and other data for the solid is pointed to 
 * by 'client_data' */
typedef struct BREP_SOLID {
  void *client_data;			/* pointer to whatever data the user 
					 * wants to keep with the solid */
  struct BREP_SHELL *shells;
  struct BREP_VERTEX_OCTREE *vertices;	/* vertices, sorted in an octree 
					 * for fast lookup. */
} BREP_SOLID;

/* A shell is basically a collection of connected faces representing an
 * orientable two-manifold. This means: a two-dimensional surface (in 3D 
 * space here), where each point on the surface has a neighbourhood 
 * topologically equivalent to an open disk. The surface must be orientable
 * and closed. Orientable means that it is two-sided. There must be a clear
 * distinction between its inside and its outside. The data structure
 * here only represent the (adjacency) topology of a surface. It is up
 * to the user of this data structure and library funtions to fill in
 * the geometry information and make sure that it is geometrically 
 * consistent. That means that the assigned shape should be consistent with
 * the topology. */
typedef struct BREP_SHELL {
  void *client_data;
  struct BREP_SHELL *prev, *next;	/* doubly linked ring to make
					 * insertions and removals easy */
  struct BREP_FACE *faces;
  struct BREP_SOLID *solid;		/* backpointer to the containing 
					 * solid */
} BREP_SHELL;

/* A face is a bounded open subset of a plane, bounded by one or more 
 * contours. One contour defines the outside of the face. Other contours
 * describe its cavities. The contours describing cavities are called
 * rings. The orientation of the outer contour must be counterclockwise as
 * seen from the direction of the normal to the containing plane. Rings
 * must be oriented clockwise. The cross product of a contour edge direction
 * and the plane normal is always a vector that points to the outside of
 * a face. Or in other words, the inside of a face is always on the left side
 * of a contour. The geometric data supplied by the user must conform with 
 * this rule. The rings, if any, are pointed to by the outer contour. 
 * When building a face, the first contour being specified must be the 
 * outer contour (at least if your application relies on this 
 * interpretation). */
typedef struct BREP_FACE {
  void *client_data;
  struct BREP_FACE *prev, *next;	/* faces form a doubly linked ring */
  struct BREP_CONTOUR *outer_contour;
  struct BREP_SHELL *shell;		/* backpointer to the containing 
					 * shell */
} BREP_FACE;

/* A contour represents a single closed planar polygonal curve (a loop).
 * Self-intersecting contours are not allowed. Different contours may only
 * intersect at common vertices or edges if at all. Here, we provide pointers
 * to WINGs instead of EDGEs in order to have implicit information about
 * the orientation of an edge as used in a contour. This facilitates 
 * iterating over the edges or vertices in a contour in a consistent manner. 
 * When building a contour, the edges must be specified in the right order:
 * the inside of the face is always to the left of an edge. In a two-manifold,
 * outer contours do not touch inner contours (they don't intersect 
 * and do not share vertices or edges). However, a vertex may be
 * used several times in a contour and two outer or inner contours
 * can share an edge, but only in opposite direction. If you need multiple
 * pairs of contours sharing the same vertex, you probably want 
 * topologically different vertices at the same place in 3D space. Same if
 * you believe you need inner and outer contours sharing a vertex. */
typedef struct BREP_CONTOUR {
  void *client_data;
  struct BREP_CONTOUR *prev, *next;	/* contours form a doubly linked ring 
					 * in order to facilitate the splitting
					 * and merging of contours. There is 
					 * one ring per face, containing the 
					 * outer contour as well as the 
					 * rings. */
  struct BREP_WING *wings;
  struct BREP_FACE *face;		/* backpointer to the containing 
					 * face */
} BREP_CONTOUR;

/* An edge is a unique connection between two vertices. There can be no more
 * than one edge between two given vertices in a valid model. An edge  can be 
 * used in two contours. The use of an edge in a contour is called a 
 * wing. A wing contains the starting vertex of the edge in the contour. The
 * other vertex is the starting vertex in the other wing, since the edge should
 * be used in opposite sense by the other contour sharing the edge. 
 * The invariant is: wing->vertex == OtherWingInEdge(wing->prev)->vertex:
 * the starting point in a wing is the endpoint of the edge specified in 
 * wing->prev. 
 * The data structure contains two more pointers than a winged edge data 
 * structure, but the code to operate on it is significantly simpler, cfr. 
 * [Weiler 1985]. The data structure is more compact than in [Glassner 1991]. */
typedef struct BREP_WING {
  struct BREP_VERTEX *vertex;		/* startvertex */
  struct BREP_WING *prev, *next;	/* ClockWise and CounterClockWise
					 * next wing within outer contours */
  struct BREP_EDGE *edge;		/* pointer to the containing edge */
  struct BREP_CONTOUR *contour;		/* backpointer to the containing 
					 * contour */
} BREP_WING;

typedef struct BREP_EDGE {
  void *client_data;
  struct BREP_WING wing[2];		/* two wings */
} BREP_EDGE;

/* A doubly linked ring of wings indicates in what wings a vertex is being used. 
 * The code becomes a lot simpler and more efficient when explicitely remembering
 * with each vertex what wings leave at the vertex. It also allows to deal
 * easier with partial shells: shells not enclosing a region into space, such
 * as a collection of coplanar faces, which is often used in synthetic
 * environments. */
typedef struct BREP_WING_RING {
  BREP_WING *wing;
  struct BREP_WING_RING *prev, *next;
} BREP_WING_RING;

/* A vertex is basically a point in 3D space. */
typedef struct BREP_VERTEX {
  void *client_data;
  BREP_WING_RING *wing_ring;		 /* ring of wings leaving at the vertex */
} BREP_VERTEX;


/* *********************** Callback Functions ************************** */
/* In order to maintain other than topological data with the entities,
 * e.g. geometrical data such as coordinates of a vertex, plane equation
 * of a face etc ..., three callback functions are associated with
 * each entity:
 *
 * - a Create callback: called when the topological entity is created
 *	this is the moment to duplicate the client data passed with
 *	an entity in order to make a private copy for that entity;
 *
 * - a Close callback: called when the topological entity is
 *	completely specified. A vertex is completely specified when it
 *	is created, an edge is completely specified each time it is
 *	included in a contour. Contours, faces, shells and solids
 *	are considered completely specified only when the user
 *	lets it know to the library by calling BrepCloseSolid().
 *	A Close callback is a good moment to compute plane equations
 *	for faces, to compute bounding boxes, to verify etc...
 *
 * - a Destroy callback: when the topological entity is being destroyed.
 *	A Destroy callback is the place to dispose of the client data
 *	for an entity.
 *
 * argument: a pointer to the topological entity being created,
 *	     closed or destroyed.
 *
 * return value: for a Create or Close callback, a pointer to the new 
 *	     client data to be kept with the topological entity. 
 *	     for a Destroy callback: none 
 *
 * Default callback functions: none. If a callback function is not set,
 *	no action is taken and nothing is changed to the client data
 *	of an entity.
 */

typedef void *(*BREP_CALLBACK_FUNC)(void *);

extern BREP_CALLBACK_FUNC BrepSetCreateSolidCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCreateShellCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCreateFaceCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCreateContourCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCreateEdgeCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCreateVertexCallback(BREP_CALLBACK_FUNC func);

extern BREP_CALLBACK_FUNC BrepSetCloseSolidCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCloseShellCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCloseFaceCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCloseContourCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCloseEdgeCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetCloseVertexCallback(BREP_CALLBACK_FUNC func);

extern BREP_CALLBACK_FUNC BrepSetDestroySolidCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetDestroyShellCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetDestroyFaceCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetDestroyContourCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetDestroyEdgeCallback(BREP_CALLBACK_FUNC func);
extern BREP_CALLBACK_FUNC BrepSetDestroyVertexCallback(BREP_CALLBACK_FUNC func);


/* callback routines for communicating informational, warning, error and
 * fatal error messages. First parameter (if non-null) is a pointer
 * to the client data of the topological entity that caused the 
 * error (use and identification of this info is left to the user of
 * this library). The second argument is the message itself. */
typedef void (*BREP_MSG_CALLBACK_FUNC)(void *client_data, char *message);

/* No error message from the library is longer than this */
#define BREP_MAX_MESSAGE_LENGTH 200

/* The SetCallback functions return the previously set callback function */
extern BREP_MSG_CALLBACK_FUNC BrepSetInfoCallback(BREP_MSG_CALLBACK_FUNC f);
extern BREP_MSG_CALLBACK_FUNC BrepSetWarningCallback(BREP_MSG_CALLBACK_FUNC f);
extern BREP_MSG_CALLBACK_FUNC BrepSetErrorCallback(BREP_MSG_CALLBACK_FUNC f);
extern BREP_MSG_CALLBACK_FUNC BrepSetFatalCallback(BREP_MSG_CALLBACK_FUNC f);


/* *********************** Contructors ***************************** */
/* creates an empty solid, client_data supplied */
extern BREP_SOLID *BrepCreateSolid(void *client_data);

/* creates a new empty shell within the solid if solid is not a NULL
 * pointer. You will need to call BrepCloseShell() yourself to
 * close the shell and/or BrepConnectShellToSolid() to connect it
 * to a solid if you don't specify a solid to contain the shell with
 * this function. */
extern BREP_SHELL *BrepCreateShell(BREP_SOLID *solid, void *client_data);

/* creates a new empty face within the shell if shell is not a NULL
 * pointer. */
extern BREP_FACE *BrepCreateFace(BREP_SHELL *shell, void *client_data);

/* creates a new empty contour within the face. 'face' cannot be a NULL
 * pointer. */
extern BREP_CONTOUR *BrepCreateContour(BREP_FACE *face, void *client_data);

/* creates a new vertex. The new vertex is not installed it in a vertex 
 * octree as vertices do not have to be sorted in an octree, see below. */
extern BREP_VERTEX *BrepCreateVertex(void *client_data);

/* Creates a wing into the contour from vertex1 to vertex2. The 
 * inside of the face bounded by the contour is supposed to be on the 
 * left side. The wing being created is supposed to be the new last
 * one in a contour, i.e. its starting vertex 'vertex1' must be the 
 * endvertex of the most recently created wing in the contour (if 
 * non-empty). It is the responsibility of the user to close the
 * contour, i.e., the last edge in a contour should connect to the 
 * first one. */
extern BREP_WING *BrepCreateWing(BREP_VERTEX *vertex1, BREP_VERTEX *vertex2, BREP_CONTOUR *contour, void *client_data);

/* performs various actions to be done when the boundary representation of
 * the solid has been completely specified. Automatically calls 
 * BrepCloseShell() for its contained shells and so on ... */
extern void BrepCloseSolid(BREP_SOLID *solid);

/* The following functions are only needed when creating "orphan"
 * shells and faces (= without specifying the parent solid/shell
 * when creating them). */

/* same for a shell. Only needed for shells that were created without
 * specifying the enclosing solid. */
extern void BrepCloseShell(BREP_SHELL *shell);

/* same for a face. Note that contours and wings/edges cannot be created
 * without a containing face, ... */
extern void BrepCloseFace(BREP_FACE *face);

/* connects the shell to the solid */
extern void BrepConnectShellToSolid(BREP_SHELL *shell, BREP_SOLID *solid);

/* disconnect the shell from the solid */
extern void BrepDisconnectShellFromSolid(BREP_SHELL *shell);

/* connects the face to the shell */
extern void BrepConnectFaceToShell(BREP_FACE *face, BREP_SHELL *shell);

/* disconnect the face from its containing shell */
extern void BrepDisconnectFaceFromShell(BREP_FACE *face);


/* ************************ Modifiers ******************************* */

/* Splits an edge in two at the specified vertex (at least: 
 * topologically; the new vertex doesn't have to be collinear
 * with the endpoints of the edge to be split, but you should make
 * sure that no contours are created that intersect in other
 * places than at vertices and along edges. The contours
 * to which the edge belongs are assumed to be closed loops. */
extern void BrepSplitEdge(BREP_EDGE *edge, BREP_VERTEX *vertex);

/* Splits only one wing. If a full edge is to be split, also its
 * wing in the other contour (if any) needs to be split at the same vertex.
 * (BrepSplitEdge does this).
 * Returns the wing leaving at the inserted vertex. */
extern BREP_WING *BrepSplitWing(BREP_WING *wing, BREP_VERTEX *vertex);

/* Join two edges at their common endpoint. The edges must be used
 * in the same contours and must share an endpoint. */
extern void BrepJoinEdges(BREP_EDGE *edge1, BREP_EDGE *edge2);

/* Joins two wings at there common endpoint. The wings are supposed to 
 * be consecutive wings, i.e. wing1->next = wing2 (and wing2->prev = wing1)
 * in a closed contour. The common vertex is wing2->vertex,
 * the start vertex of the second wing (which is supposed to be
 * the endpoint of the first wing as well). Returns the newly
 * created wing. */
extern BREP_WING *BrepJoinWings(BREP_WING *wing1, BREP_WING *wing2);

/* wing1 and wing2 should be two wings belonging to the same contour.
 * This routine creates a new edge connecting the start vertex of wing1 
 * and wing2, splitting the contour in two. A pointer to the newly created 
 * wing, connecting the start vertex of wing1 to the start vertex of wing2, 
 * is returned. */
extern BREP_WING *BrepMakeEdgeSplitContour(BREP_WING *wing1, BREP_WING *wing2,
					   void *edge_data, void *contour_data);

/* Wing1 and wing2 are two wings belonging to a different contour. This
 * routine creates a new edge connecting the starting vertices of 
 * wing1 and wing2 and merges to two contours to one. A pointer to
 * the newly created wing, connecting the start vertex of wing1 to the
 * start vertex of wing2, is returned. */
extern BREP_WING *BrepMakeEdgeJoinContours(BREP_WING *wing1, BREP_WING *wing2, 
					   void *edge_data);

/* wing is a wing of an edge that is used in two different contours. This 
 * routine deletes the edge to which the wing belongs, inserting the reaminder
 * of the "other" contour sharing the edge into the contour to which the wing 
 * belongs. The other contour is destroyed and the first is "closed" again 
 * in order to notify that it changed. Returns the wing from the first contour 
 * that comes before the first wing moved from the second to the first, or
 * NULL if the first contour was a selfloop. In that case, the empty contour 
 * is deleted. In case of errors, wing is returned. Warning: if the face to which
 * the other contour belongs, contains holes, these holes should probably be moved
 * to the face to which 'wing' belongs.   */
extern BREP_WING *BrepDeleteEdgeJoinContours(BREP_WING *wing);

/* 'wing' is a wing of an edge that is used two times (in opposite direction) 
 * in the same contour, i.o.w. a seam. This routine deletes this edge.
 * If the wings happen to be consequtive wings, the wings are just deleted.
 * If these are the only two wings in the contour, the contour is deleted as 
 * well and a NULL wing pointer is returned. If they are not consequtive, the 
 * contour is split in two contours. The wing before 'wing' will remain in 
 * the original contour and will be returned. */
extern BREP_WING *BrepDeleteEdgeSplitContour(BREP_WING *wing, void *contour_data);

/* Creates a notch, connecting the start vertex of the wing with
 * the specified vertex, ans inserts it into the contour to
 * which the wing belongs. A pointer to the newly created
 * wing, from the start vertex of the specified wing to the
 * specified vertex, is returned. */
extern BREP_WING *BrepMakeNotch(BREP_WING *wing, BREP_VERTEX *vertex, 
				void *edge_data);

/* Creates a slit, connecting the two specified vertices, 
 * in the given face. A slit is a new contour containing
 * two wings: one from v1 to v2 and the second
 * from v2 back to v1. A pointer to the newly created
 * wing, connecting v1 to v2, is returned. */
extern BREP_WING *BrepMakeSlit(BREP_FACE *face, BREP_VERTEX *v1, BREP_VERTEX *v2,
			       void *edge_data, void *contour_data);

/* Replace the starting vertex of 'wing' by 'newvertex'. Assumes
 * that 'wing' is correctly connected in a contour and it is not
 * the only wing (that means: the contour is not a selfloop).
 * Returns a pointer to the new wing, which is leaving at 'newvertex'. */
extern BREP_WING *BrepWingReplaceVertex(BREP_WING *wing, BREP_VERTEX *newvertex);


/* ******************** Selectors and Iterators ************************* */
/* adding and removing elements in the ring being iterated over is restricted
 * to certain conditions: the first element being iterated over must remain 
 * in the ring and the next element of an element being passed must remain
 * the same as well. */

/* iterate over the shells in the solid: 1A = 1 extra argument, passed after the 
 * BREP_SHELL *, 2A = two extra arguments, passed in order after the BREP_SHELL * */
extern void BrepSolidIterateShells(BREP_SOLID *solid, void (*func)(BREP_SHELL *));
extern void BrepSolidIterateShells1A(BREP_SOLID *solid, void (*func)(BREP_SHELL *, void *), void *parm);
extern void BrepSolidIterateShells2A(BREP_SOLID *solid, void (*func)(BREP_SHELL *, void *, void *), void *parm1, void *parm2);

/* execute func for every face in the shell */
extern void BrepShellIterateFaces(BREP_SHELL *shell, void (*func)(BREP_FACE *));
extern void BrepShellIterateFaces1A(BREP_SHELL *shell, void (*func)(BREP_FACE *, void *), void *parm);
extern void BrepShellIterateFaces2A(BREP_SHELL *shell, void (*func)(BREP_FACE *, void *, void *), void *parm1, void *parm2);

/* iterate over the contours of the face */
extern void BrepFaceIterateContours(BREP_FACE *face, void (*func)(BREP_CONTOUR *));
extern void BrepFaceIterateContours1A(BREP_FACE *face, void (*func)(BREP_CONTOUR *, void *), void *parm);
extern void BrepFaceIterateContours2A(BREP_FACE *face, void (*func)(BREP_CONTOUR *, void *, void *), void *parm1, void *parm2);

/* Iterate over the wings in the contour. When properly built, the inside of 
 * the face containing the contour is always on the left side of an edge. */
extern void BrepContourIterateWings(BREP_CONTOUR *contour, void (*func)(BREP_WING *));
extern void BrepContourIterateWings1A(BREP_CONTOUR *contour, void (*func)(BREP_WING *, void *), void *parm);
extern void BrepContourIterateWings2A(BREP_CONTOUR *contour, void (*func)(BREP_WING *, void *, void *), void *parm1, void *parm2);

/* Iterates over the vertices in a contour. Same order as when iterating 
 * over the edges. */
extern void BrepContourIterateVertices(BREP_CONTOUR *contour, void (*func)(BREP_VERTEX *));
extern void BrepContourIterateVertices1A(BREP_CONTOUR *contour, void (*func)(BREP_VERTEX *, void *), void *parm);

/* Iterate over the wings leaving the vertex, in arbitrary order. */
extern void BrepVertexIterateWings(BREP_VERTEX *vertex, void (*func)(BREP_WING *));
extern void BrepVertexIterateWings1A(BREP_VERTEX *vertex, void (*func)(BREP_WING *, void *), void *parm);

/* Iterator over all wings (included in a contour) connecting the two 
 * given vertices. */
extern void BrepIterateWingsWithVertex(BREP_VERTEX *vertex1, BREP_VERTEX *vertex2, 
				       void (*func)(BREP_WING *));

extern void BrepIterateWingsWithVertex1A(BREP_VERTEX *vertex1, BREP_VERTEX *vertex2, 
					 void (*func)(BREP_WING *, void *parm), 
					 void *parm);

/* You might prefer the following, more flexibale iterators however ... */
#define ForAllInRing(TYPE, elem, first, nextel) \
  TYPE *elem, *nextel; \
  for (elem=(first), nextel=elem->next; elem; elem = nextel==(first) ? (TYPE *)NULL : nextel, nextel=nextel->next)

#define ForAllShellsInSolid(shell, solid) { \
  if ((solid) && (solid)->shells) { \
    ForAllInRing(BREP_SHELL, shell, (solid)->shells, next_shell) {

#define ForAllFacesInShell(face, shell) { \
  if ((shell) && (shell)->faces) { \
    ForAllInRing(BREP_FACE, face, (shell)->faces, next_face) {

#define ForAllContoursInFace(contour, face) { \
  if ((face) && (face)->outer_contour) { \
    ForAllInRing(BREP_CONTOUR, contour, (face)->outer_contour, next_contour) {

#define ForAllWingsInContour(wing, contour) { \
  if ((contour) && (contour)->wings) { \
    ForAllInRing(BREP_WING, wing, (contour)->wings, next_wing) {

#define ForAllWingsLeavingVertex(_wing, vertex) { \
  if ((vertex) && (vertex)->wing_ring) { \
    ForAllInRing(BREP_WING_RING, _r_, (vertex)->wing_ring, next_wingel) { \
      BREP_WING *_wing = _r_->wing;

#ifndef EndForAll
#define EndForAll }}}
#endif

/* returns the other wing in the edge */
extern BREP_WING *BrepEdgeOtherWing(BREP_WING *wing);

/* returns the next wing with same starting vertex as wing. The order is 
 * counterclockwise if the vertex is used in outer contours only and 
 * clockwise if used in inner contours only. Returns a null pointer
 * if the current wing is not properly connected to possible
 * other wings sharing the vertex, or the boundary of a partial
 * shell was reached. */
extern BREP_WING *BrepNextWingLeavingVertex(BREP_WING *wing);

/* looks whether the wing is referenced in the wing ring of its
 * starting vertex. Returns a pointer to the BREP_WING_RING element if
 * it is found and NULL if not */
extern BREP_WING_RING *BrepFindWingLeavingVertex(BREP_WING *wing);

/* Looks whether an edge connecting the two vertices already
 * exists, Returns it if it exists. Returns NULL if not. */
extern BREP_EDGE *BrepFindEdge(BREP_VERTEX *vertex1, BREP_VERTEX *vertex2);


/* ************************ Destructors **************************** */
/* releases all memory associated with the solid, also its vertices if not used
 * in other solids as well. */
extern void BrepDestroySolid(BREP_SOLID *solid);

/* release all memory associated to a shell and its contained faces */
extern void BrepDestroyShell(BREP_SHELL *shell);

/* release all storage associated with a face and its contours, including
 * edges if not used in other faces as well */
extern void BrepDestroyFace(BREP_FACE *face);

/* release all storage associated with a contour and its wing/edges
 * if not used in other contours as well */
extern void BrepDestroyContour(BREP_CONTOUR *contour);

/* remove a wing from a contour, release the storage associated with the
 * edge if it is not used in other contours as well. This routine will 
 * in general create a hole in a contour: the endpoint of a previous edge
 * might not be the starting point of the next one where an edge has been
 * deleted. The vertices are not deleted. */
extern void BrepDestroyWing(BREP_WING *wing);

/* Remove a vertex from a (closed) contour, the wings containing the vertex are
 * removed as well (and their edges if not used in other contours as
 * well). If it is not the only vertex in the contour, a new wing connecting
 * the neighbooring vertices is created, so the contour remains
 * a loop. The vertex is not deleted. */
extern void BrepContourRemoveVertex(BREP_CONTOUR *contour, BREP_VERTEX *vertex);

/* release all storage associated with the vertex if it is not used 
 * anymore in any edge. */
extern void BrepDestroyVertex(BREP_VERTEX *vertex);


/* ********************** vertex octrees *************************** */
/* vertices can also be sorted and stored into an octree in order to make 
 * searching for a vertex significantly faster. */
/* this struct must have the same layout as OCTREE in Octree.h */
typedef struct BREP_VERTEX_OCTREE {
  BREP_VERTEX *vertex;
  struct BREP_VERTEX_OCTREE *child[8];
} BREP_VERTEX_OCTREE;

/* Before trying to store vertices in an octree, first a routine should
 * be speciied to compare the client data of two vertices.
 * The routine specified should return a code with the following meaning:
 *
 * 	0:  x1 <= x2 , y1 <= y2, z1 <= z2 but not all are equal
 * 	1:  x1 >  x2 , y1 <= y2, z1 <= z2 
 * 	2:  x1 <= x2 , y1 >  y2, z1 <= z2 
 * 	3:  x1 >  x2 , y1 >  y2, z1 <= z2 
 * 	4:  x1 <= x2 , y1 <= y2, z1 >  z2 
 * 	5:  x1 >  x2 , y1 <= y2, z1 >  z2 
 * 	6:  x1 <= x2 , y1 >  y2, z1 >  z2 
 * 	7:  x1 >  x2 , y1 >  y2, z1 >  z2 
 * 	8:  x1 == x2 , y1 == y2, z1 == z2 
 *
 * in other words: 
 *
 *	code&1 == 1 if x1 > x2 and 0 otherwise
 *	code&2 == 1 if y1 > y2 and 0 otherwise
 *	code&4 == 1 if z1 > z2 and 0 otherwise
 *	code&8 == 1 if x1 == x2 and y1 == y2 and z1 == z2
 *
 * BrepSetVertexCompareRoutine() returns the previously installed compare 
 * routine so it can be restored when necessary. */
typedef int (*BREP_COMPARE_FUNC)(void *, void *);

extern BREP_COMPARE_FUNC BrepSetVertexCompareRoutine(BREP_COMPARE_FUNC routine);

/* Set a routine to compare only the the location of two BREP_VERTEXes. There
 * may be multiple vertices at the same location, e.g. having a different
 * normal and/or name. These vertices are considered different vertices
 * by the vertex compare routine which is set with BrepSetVertexCompareRoutine(),
 * but they are considered the same vertices by the routine which is set with
 * BrepSetVertexCompareLocationRoutine(). The previously installed compare 
 * routine is returned, so it can be restored when necessary. This compare
 * routine is used by BrepFindVertexAtLocation(), BrepIterateVerticesAtLocation(),
 * BrepIterateWingsBetweenLocations() ... */
extern BREP_COMPARE_FUNC BrepSetVertexCompareLocationRoutine(BREP_COMPARE_FUNC routine);

/* Looks up a vertex in the vertex octree, return NULL if not found */
extern BREP_VERTEX *BrepFindVertex(void *vertex_data, BREP_VERTEX_OCTREE *vertices);

/* attaches a  BREP_VERTEX to the vertex octree */
extern void BrepAttachVertex(BREP_VERTEX *vertex, BREP_VERTEX_OCTREE **vertices);

/* removes a BREP_VERTEX from the vertex octree */
extern void BrepReleaseVertex(BREP_VERTEX *vertex, BREP_VERTEX_OCTREE **vertices);

/* Creates a vertex and installs it in the vertex octree, same as
 * BrepCreateVertex() followed by BrepAttachVertex() */
extern BREP_VERTEX *BrepInstallVertex(void *vertex_data, BREP_VERTEX_OCTREE **vertices);

/* calls func for each BREP_VERTEX in the octree */
extern void BrepIterateVertices(BREP_VERTEX_OCTREE *vertices, void (*func)(BREP_VERTEX *));

/* For convenience, a vertex octree is created with each BREP_SOLID.
 * The vertex octree bound to a BREP_SOLID is also destroyed when
 * destroying the BREP_SOLID. 
 * The routines below allow to create and destroy vertex octrees not
 * bound to a solid. */

/* creates a new vertex octree: currently only returns a NULL pointer */
extern BREP_VERTEX_OCTREE *BrepCreateVertexOctree(void);

/* Destroys a vertex octree, does not destroy the vertices referenced in
 * the octree. */
extern void BrepDestroyVertexOctree(BREP_VERTEX_OCTREE *vertices);

/* destroys all the vertices and the vertex octree, same as
 * BrepIterateVertices(vertices, BrepDestroyVertex) followed by
 * BrepDestroyvertexOctree(). */
extern void BrepDestroyVertices(BREP_VERTEX_OCTREE *vertices);

/* Looks up the first vertex in the vertex octree at the location as specified in the 
 * given vertex data. There may be multiple vertices at the same location (e.g. having 
 * a different normal and/or a different name). These vertices should normally be
 * stored as a suboctree of the octree containing all vertices. A pointer to the
 * top of this suboctree is returned if there are vertices at the given location.
 * NULL is returned if there are no vertices at the given location. */
extern BREP_VERTEX_OCTREE *BrepFindVertexAtLocation(void *vertex_data, BREP_VERTEX_OCTREE *vertices);

/* Iterators over all vertices in the given vertex octree that are at the same
 * location as specified in the vertex data. */
extern void BrepIterateVerticesAtLocation(void *vertex_data, BREP_VERTEX_OCTREE *vertices,
					  void (*routine)(BREP_VERTEX *vertex));

/* 1 extra parameter */
extern void BrepIterateVerticesAtLocation1A(void *vertex_data, BREP_VERTEX_OCTREE *vertices,
					    void (*routine)(BREP_VERTEX *vertex, void *parm), 
					    void *parm);

/* 2 extra parameters */
extern void BrepIterateVerticesAtLocation2A(void *vertex_data, BREP_VERTEX_OCTREE *vertices,
					    void (*routine)(BREP_VERTEX *vertex, void *parm1, void *parm2),
					    void *parm1, void *parm2);

/* Iterator over all edge-wings between vertices at the locations specified by 
 * v1data and v2data. */
extern void BrepIterateWingsBetweenLocations(void *v1data, void *v2data,
					     BREP_VERTEX_OCTREE *vertices,
					     void (*func)(BREP_WING *));

/* Iterator over all edge-wings between vertices at the locations specified by 
 * v1data and v2data. */
extern void BrepIterateWingsBetweenLocations1A(void *v1data, void *v2data,
					       BREP_VERTEX_OCTREE *vertices,
					       void (*func)(BREP_WING *),
					       void *parm);

#ifdef __cplusplus
}
#endif

#endif /* _BREP_H_ */