#ifndef OctfRep_H #define OctfRep_H /* Internal representation of the facet-edge data structure. */ /* Last edited on 2007-02-04 01:35:12 by stolfi */ #include #include #include #define _GNU_SOURCE #include /* FACET-EDGE DATA RECORDS In a barycentric subdivision of a map on a (borderless) manifold, one always has {p.flp[0] != p}, {p.flp[0].flp[0] == p}, {p.flp[3] != p}, {p.flp[3].flp[3] == p}, {p.flp[0].flp[3] == p.flp[3].flp[0] != p}. It follows that the places in a map {M} are connected by {flp[0]} and {flp[3]} into discrete components (orbits) of size four, each comprising four /sibling chips/ {s00,s01,s10,s11}; where {flp[0]} (in {M}) swaps {s00<->s10} and {s01<->s11}, while {flp[3]} swaps {s00<->s01} and {s10<->s11}. The same holds for the places in the dual map {M*}. The the dual operator {*} establishes an isomorphism between each orbit on {M} and an orbit of {M*}, both based on the same four chips, except that the isomorphism exchanges the effects of {flp[0]} and {flp[3]}. The facet-edge data structure takes advantage of this fact to optimize the encoding of the {flp} operators. It uses a single data record to represent each of these four-chip groups and the eight places based on those chips. In this way, the operations {flp[0]} and {fpl[3]} stay on the same record. Only the operations {flp[1]} and [flp[2]} need to be encoded explicitly, by pointers between those records records. WEDGES Each data record can be viewed as representing a /wedge/ of the map {M}, the subset of {X} that comprises the four chips of such a group, plus every flag with {M}-type {{0,1,2}} or {{1,2,3}} that bounds two of those chips, and the link with {M}-type {{1,2}} {m} that bounds all four chips. A wedge {w} is therefore incident to exactly one edge {e = w.edge} of {M}, which is the union of two links with {M}-type {{0,1}} and one knot with {M}-type {{1}} that bound it. The wedge is also incident to exactly one edge {f*} of the dual map {M*}, comprising two links with {M}-type {{2,3}} and one knot with {M}-type {{3}}. The wall {f = w.wall} of {M} whose dual is {f*} is incident to {e} and bisects {w} and {f*}. Dually, the wall {e*} of {M*} is incident to the edge {f*} and also bisects {w} and {e}. The link {m} lies on the wall {f} and connects the centroids {e!} and {f!}; in fact, it is the intersection of the walls {e*} of {M*} and {f} of {M}. The wedge also incides on the two endpoints of its edge {e} (which may be the same node of {M}) and extends into the two cells separated by its wall {f} (which may be the same cell of {M}). */ typedef struct WedgeRec_t *Wedge_t; /* A {Wedge_t} is a pointer to record that represents a wedge of the two maps. */ vec_typedef(Wedge_vec_t,Wedge_vec,Wedge_t); /* A vector of pointers to wedge records. */ void WedgeInit(Wedge_t w); /* Initializes the contents of {*}. The {ca} pointers are set so that {w} is the single wedge of a new connected component {N} of the map, on a new connected component {Y} of {X}. The new subspace {Y} is homeomorphic to a three-sphere. The new map {N} will have one vertex, one loop edge, one wall and one cell. [!!! The comments said "two vertices"-- check!!!] */ Wedge_t MakeWedge(void); /* Allocates a new WedgeRec_t} record, initialize it with {WedgeInit}. */ /* FROM WEDGES TO PLACES In order to identify a unique place in {M} or {M*}, the the facet-edge structure uses a pointer to a wedge record {w}, plus two /orientation bits/ that identify one chip {s} among the four chips contained in the wedge {w}, plus a /duality bit that selects between {M} and {M*}. The two orientation bits can be interpreted as specifying longitudinal orientations for the two edges of {M} and {M*} associated with {w}, namely {w.edge} and {w.wall*}. The duality bit specifies which of the two is *the* edge of {w}. */ #define MaxWedgeNum (UINT_MAX/8); /* The maximum wedge number allowed. */ typedef uint WedgeNum_t; /* Must be in [0..MaxWedgeNum]. */ /* ORIENTATION BITS */ typedef unsigned char SRBits_t; /* [0..7] Spin and Rotations bits */ typedef unsigned char RBits_t; /* [0..3] Rotations bits of */ typedef unsigned char OBit_t; /* [0..1] Orientation bit */ typedef unsigned char SBit_t; /* [0..1] Spin bit */ typedef unsigned char DBit_t; /* [0..1] Dual/Primal bit */ /* The meaning of these bits is relative, not absolute. (More on that below). */ Wedge_t PWedge(Place_t p); /* The record {w} that represents the wedge containing chip {p.s} (together with the other three sibling chips). */ SRBits_t PBits(Place_t p); /* The bits that identify the place {p} among the eight chips with the same wedge record as {p}. */ Place_t PlaceInWedge(Wedge_t w, SRBits_t srb); /* The place {p} on the wedge {w} with {SRBits(p) = srb}. */ Place_t WedgeBase(Wedge_t w); /* The `base' place on the wedge {w}, i.e. {PlaceInWedge(w,0)}. */ /* An {SRBits_t} value identifies a particular place within a wedge {w}, according to the following table (where {a == WedgeBase(w)}): | SRBits place OBit DBit SBit RBits | ----------------------------------------------- | 000 0 a 0 0 0 0 | 001 1 a.spin 0 0 1 0 | 010 2 a.srot 0 1 0 1 | 011 3 a.srot.spin 0 1 1 1 | 100 4 a.clock 1 0 0 2 | 101 5 a.clock.spin 1 0 1 2 | 110 6 a.tors 1 1 0 3 | 111 7 a.tors.spin 1 1 1 3 In general, the place {p = a.Srot^r.Spin^s}, for "r" in [0..3] and "s" in [0..1], has {SRBits(p) = 2r + s}. */ OBit_t OrientationBit(Place_t p); /* Orientation bit == "SRBits DIV 4". Reversed by "Clock", unchanged by "Spin", may be changed by "Srot". */ SBit_t SpinBit(Place_t p); /* Spin bit == "SRBits MOD 2". Reversed by "Spin". */ DBit_t DualBit(Place_t p); /* Dual bit == "SRBits DIV 2 MOD 2". Unchanged by "Spin" and "Clock", reversed by "Srot". */ RBits_t SrotBits(Place_t p); /* Rot bits == "SRBits DIV 2". Unchanged by "Spin", incremented twice by "Clock", either incremented or decremented by "Srot". */ /* CREATING AND RECLAIMING WEDGE RECORDS */ void DeleteWedge(Place_t p); /* Delete the wedge record of {p}. */ /* TOPOLOGY MODIFICATION */ void SpliceWalls(Place_t a, Place_t b); /* Merges or splits the wall-rings {F_a} and {F_b} of places {a} and {b}. */ void SpliceEdges(Place_t a, Place_t b); /* Merges or splits the edge-rings {E_a} and {E_b} of places {a} and {b}. */ void SetNextF(Place_t p, Place_t b); /* If {NextF(a) != b}, performs {SpliceWalls(a, PrevF(b))}. After this call {NextF(a)} will be equal to {b}. Valid whenever {SpliceWalls(a,PrevE(b))} is valid. */ void SetNextE(Place_t p, Place_t b); /* If {NextE(a) != b}, performs {SpliceEdges(a,PrevE(b))}. After this call, {NextE(a)} will be equal to {b}. Valid whenever {SpliceEdges(a,PrevE(b))} is valid. */ /* MELDING FACET-EDGE @PLACES */ void Meld(Place_t p, Place_t b); /* Meld {F_a} with {F_b} */ #define MaxPlaceNum ((MaxWedgeNum*8)-1) /* Maximum pair number */ typedef uint PlaceNum_t; /* [0..MaxPlaceNum] */ PlaceNum_t GetPlaceNum_t(Place_t p); /* == {PWedge(a).num * 8 + PBits(a)} */ /* ENUMERATING WEDGES */ Wedge_vec_t EnumWedges(Place_vec_t root, VisitFunc_t visit); /* Enumerates all wedges that can be reached from the places {root.e[0..root.ne-1]}. Calls {visit(p)} excatly once for each wedge, where {p} is the wedge's paseplace. Returns a list {W} of all the visited wedges. As a side effect, assigns sequential numbers to the {num} field of all visited wedges, so that {W[i]->num == i} for all {i} in {0..W.ne-1}. */ /* PRINTOUT */ void PrintPlace(FILE *wr, Place_t p, uint feWidth /* DF 1 */, bool_t nl /* DF FALSE */); /* Prints @place {a} as "m:r:s", where {m} is the serial wedge number, and {r,s} are such that {a == Spin^s(Srot^r(a0))}, where {a0} is the base @place of the wedge. The wedge number will be left-padded with spaces to {feWidth} bytes. if ((nl == TRUE the procedure adds the newline character in the end, else it not add the character. */ Place_t ReadPlace(FILE *rd, Wedge_vec_t *map); /* Reads from {rd} an @place in the {m:r:s} format used by {PrintPlace}. The {map} table is used to convert the wedge number {m} into a {Wedge_t} pointer.*/ void PrintWedge(FILE *wr, Wedge_t w, uint feWidth /* DF 1 */); /* Prints on {wr} the four places {NextF(Srot^r(b))}, where {b} is the base place of {w} and {r} ranges in {0..3}. Places are separated by one space. Each place is printed using {PrintPlace}, with wedge numbers left-padded to {feWidth} bytes. */ void ReadWedge(FILE *rd, Wedge_t w, Wedge_vec_t *map); /* Reads from {rd} four places {a[0..3]}, using {ReadPlace(rd, map)}. Then performs {SetNextF(Srot^r(b), a[r])}, where {b} is the base place of {w} and {r} ranges in {0..3}. */ /* WEDGE RECORD CONTENTS */ typedef struct NodeOrCellRec_t *NodeOrCell_t; typedef struct EdgeOrWallRec_t *EdgeOrWall_t; typedef struct NodeRec_t *Node_t; typedef struct EdgeRec_t *Edge_t; typedef struct WallRec_t *Wall_t; typedef struct CellRec_t *Cell_t; /* Pointer to records that describes elements of one of the maps, the /primal map/. [!!! Should be unified via duality !!!]. */ vec_typedef(Node_vec_t,Node_vec,Node_t); vec_typedef(Edge_vec_t,Edge_vec,Edge_t); vec_typedef(Wall_vec_t,Wall_vec,Wall_t); vec_typedef(Cell_vec_t,Cell_vec,Cell_t); /* Vectors of pointers to map element records. */ struct WedgeRec_t { WedgeNum_t num; /* ID number of this wedge. */ Edge_t edge; /* Edge of the primal map that bounds this wedge. */ Wall_t wall; /* Wall of the primal map that bisects this wedge. */ Place_t next[4]; /* {w.next[RBits(p)] = NextF(p)}, if {p} is primal. */ /* Field ued for enumeration: */ uint pstack; /* Index into `seen' table. */ /* Fields used for barycentric subdivision: */ uint order; /* used for barycentric subdivision. */ uint order1, order2; /* used for barycentric subdivision. */ EightPlaces_t ca; /* Handles to the terahedron of barycentric subd map. */ /* Fields from {TriangulationWedgeRec_t}: */ NodeOrCell_t org[4]; /* Origin nodes (or containing cells) of the chips in wedge. */ bool_t mark3; /* Mark the wedge, used by TriangulationRefineT.*/ Node_t *vh; /* Medial node associated to wedge.*/ uint old; /* [???]. */ /* Fields from {JSTriWedgeRec_t}: */ bool_t refine; /* Mark bit used by RefineT. */ } WedgeRec_t; /* A {WedgeRec_t} record is associated to a wedge {w} of the two maps repesented by the facet-edge structure. The fields of the {WedgeRec_t} are defined with respect to a specific place on that wedge, the /base place/ -- one of the eight places whose chips are contained in {w}. If {p} is the base place of {w}, then {w.edge} represents the oriented edge {p.e[1]}, and {w.wall} represents the oriented wall {p.e[2]}. The topology of a map {M} is described by connecting {WedgeRec_t} records. In the current implementation, the base places of all wedges belong to the same map, the /primal map/. [!!! Change as follows: The base place of each record may belong to {M} or to {M*}. Hence each connection must specify the other wedge record and a specific place in it, among the 8 possible. !!!] */ /* #default WedgeRec_t.num 0 */ /* #default WedgeRec_t.mark3 FALSE */ /* DATA POINTERS [!!! verify this code -- implemented ? !!!] For each place {p}, the data structure maintains four variables, the /element slots/, {p.data[0..3]}, which can be set by the user and are conceptually associated to the four vertices of the chip {p.s.knt[0..3]}. pointer/. /wall info/, which can be set by the client to arbitray pointers. The two records are shared between the places {p}, {p.flp[0]}, {p.flp[3]}, and {p.flp[0].flp[3]}, but may be different for two places on the same edge or wall. The edge info of {p} is the wall info of {p*}, and vice-versa. */ typedef void *EdgeWallInfo_t; void SetEdgeInfo(Place_t p, EdgeWallInfo_t n); /* Set the {edge} field of {p} to {n}. */ void SetWallInfo(Place_t p, EdgeWallInfo_t n); /* Set the {wall} field of {p} to {n}. */ void SetRingEdgeInfo(Place_t p, EdgeWallInfo_t n); /* Does {SetEdgeInfo(q,n)} for all places {q} in the edge ring of {p}. */ void SetRingWallInfo(Place_t p, EdgeWallInfo_t n); /* Does {SetWallInfo(q,n)} for all places {q} in the wall ring of {p}. */ /* SPACES AND MAPS WITH VIRTUAL BORDERS A /pseudo-manifold with border/ is a compact space {X} where almost every point has a neighborhood that is either homeomorphic to {R^3} or to the closed half of {R^3} with a positive first coordinate. The /border/ of {X} is the closure in {X} of the set of points that have only neighborhoods of the second type. A /map with border/ is a map {M} on a pseudo-manifold with border. The border of {X} must necessarily be the union of nodes, walls and edegs of {M}. Moreover every element of {M} must bound some cell of {M}. If one must work with a map {M} with border, it is best to consider a borderless space {X'} that contains {|M|} as a subspace, and a map {M'} on {X'} that contains {M} as a submap; and then mark the elements of {M'} as /concrete/ (in {M}) or /virtual/ (not in {M}). That way, the stepping operators always yield a valid place and satisfy the usual identities. Note that any element of {M'} that is concrete must bound a cell of {M'} that is also concrete. The border of {|M|} is the union of all elements that are concrete but bound a virtual cell. */ /* SPACES AND MAPS WITH HARD BORDERS In theory the implementation allows {s.flp[i] == s}, which can be interpreted as the presence of a border in {X}. In that case, the flag {0..3}\{i} of {s} is contained in the border of {X}. However, this implementation is such that the chip {t = s.flp[i]} is always distict from {s} when {i} is 0 or 3. If {s.flp[1] == s}, then the border cuts across the cell {s.e[3]}. Ditto if {s.flp[2] == s}. The chips {s} and {t = s.flp[i]} specify the same sequence of elements of {M} except possibly for the element of dimension {i}; that is, {t.e[j] == s.e[j]} for all {j != i}. On the other hand, one may have {t.e[i] == s.e[i]} even when {t != s} (e.g. if {i == 0} and the edge {s.e[1]} is a loop. It is important to note that, when {t = s.flp[i]} is distinct from {s} --- in particular, when{X} is a (borderless) manifold --- the the local orientations of {X} implied by {s} and {t} *always disagree* when compared across the shared wall of type {0..3}\{i}. The facet-edge structure is implemented in such a way that that each {flp[i]} operation takes constant time. */ /* SELF-DUAL MAPS In a properly contructed facet-edge structure, the maps {M} and {M*} are completely distinct: each is a complete partition of {X}, and no element of one map is an element of the other map. In that case, the {flp[i]} operations always stay on the same map. However, the facet-edge structure can be modified in such a way that one can go from a place in {M} to a place in {M*} by a sequence of {flp} operations, without ever using the dual operator `*'. In that case the two maps merge into a single `pseudo-map' {M~}, that is no longer a partition of {X}, and all the theory above becomes invalid. If you feel the need to work with such structures, you should forget about the Facet-Edge struture, and use the Gem structure instead. */ #define OctfRep_H_AUTH \ " L. A. P. Lozada and J. Stolfi, UNICAMP." #define OctfRep_H_MODS \ " 1999 Modula-3 version {Octf.i3} created by L. Lozada,\n" \ " based on Modula-3 quad-edge module by R. M. Rosi\n" \ " and J. Stolfi.\n" \ " 2007-01-24 Converted to C and split off from {Octf.h} by J. Stolfi\n" #endif