/* Last edited on 2007-01-24 22:12:41 by stolfi */

/*  
  A 3D map on {X} is a partition of {X} into topological open balls
  of dimension 0 (/vertices/), 1 (/edges/), 2 (/faces/), and 2 (/cells/),
  in such a way that the closure of each element is the union of itself
  and other lower-dimensional elements, and certain /niceness/ conditions
  are satisfied about the way elements incide on each other.
  
  Two maps {M,N} on {X} are said to be /mutually dual/ if (1) a
  {k}-element of {M} intersects a {j}-element of {N} only if {k+j >=
  3}; (2) each cell of {M} contains exactly one vertex of {N}, and
  vice-versa; and (3) each edge of {M} crosses (once and
  transversally) exactly one face of {N}, and vice versa. 
  
  If {e} is any {k]-element of one map, we denote by {e*} the /dual element of
  {e}/, the unique {3-k}-element of the other map that intersects {e}.
  Note that,for any {e,f} of {M} (or of {N}), {e} is incident to {f} 
  iff {f*} is incident to {e*}.
  
  A /barycentric subdivision/ of a dual pair {M,N} is a triangulation
  of {T} of {X} which (1) is a refinement of both maps, (2) has
  exactly one vertex {e#} on each element {e} of {M} or {N}, with {e*#
  = e#} for any {e}. The dimension of {e} (0,1,2, or 3) is called the
  /type/ of {e#}. It follows that each cell {t} of {T} is incident to
  four distinct vertices, one of each type.
  
  The structure represents simultaneously the topology of two mutually
  dual 3D maps on the same 3D manifold. For the comments in this
  interface, we assume that {M,N} are the two maps being represented,
  and {X} is the manifold. If {e} is any element of one map, we denote
  by {dim(e)} its dimension (0,1,2, or 3), and by {e*} its /dual element/,
  the unique element of the other map with dimension {3-dim(e)} that
  intersects {e}.
  
  In the facet-edge data structure, the topology of a dual pair
  {M,N} of maps is represented by decomposing the space {X} into
  /wedges/, and specifying how the wedges are connected.  */
  
/*
  
  We assume that for every element {e} of {M} there is a continuous
  /planting function/ {F[e]} from a closed {k}-ball {KB[k]} to the
  closure {Ke} of {e} that is the union of finitely
  many homeomorphisms whose ranges are elements of {M}.
  
  The wedges are derived from some triangulation {S} of {X} that is a
  barycentric subdivision of {M} and {N}. Let {S[e]} denote the unique
  vertex of {S} that is contained in element {e} of {M} or {N}.
  Conversely, we write {M[s]} (resp. {N[s]} for the unique element {e}
  of {M} (resp. {N}) that contains element {s} of {S}. 
  
  For each vertex {v} of {S}, the dimension of {M[v]} is 
  called the /{M}-type/ of {v}. More generally, the /{M}-type/
  of an element {s} of {S} is the set of the {M}-types of its vertices.
  The /{N}-type/ of an element is similarly defined, and is 
  related to the {M} type by mapping each integer {i} to {3-i}.
  
  Note that each {k}-dimensional element of {S} is incident to {k+1}
  distinct vertices of {S}, all with distinct {M}-types; and two
  distinct {k}-elements of {S} share at most {k} vertices. In
  particular, we say that two cells {s,t} of {S} are /{i}-adjacent
  relative to {M}/ if they share three vertices, and the two vertices
  that are *not* shared by them have {M}-type {i}. */
  
/*
  A wedge of {M,N} is then defined as the union of any set of simplices
  of a barycentric subdivision of {M} that are connected by
  0-adjacency or 3-adjacency (relative to either map), together with
  the triangles of {S} with types {0,1,2} and {1,2,3} and 
  the edges of {S} of type {1,2} that those cells incide to. 
  It turns out that any such group has precisely four 
  {S}-cells
  
  In any barycentric subdivision, {flp[i](s)!=s} for all {i} and {s}.
  Moreover, {flp[0](flp[3](s))=flp[3](flp[0](s))!=s}. It follows that
  any orbit of the set {flp[0],flp[3]} consists of four {s}-cells.
  
  The triangulation {S} defines a fourth map on {X}, the /wedge subdivision/ {W}.
  The cells of {W} are the the wedges. The faces of {W} are the 
  
  a tetrahedral chunk of the underlying 3D manifold
  {X}, that connects some edge {E} of {M} with some edge {F} of {N}
  such that the face {E*} of {N} that is dual to {E} is incident to
  edge {F}, and vice-versa. More precisely, a wedge is 
  
  An /oriented wedge/ is a wedge together with a specific order
  for the two edges and a specific longitudinal orientation for 
  each of them.  The first and second edges of the pair are called
  the /axis/ and the /rim/ of the oriented wedge. The two endpoints
  of the axis (which may be the same point of {X}) are the /origin
  vertex/ and the /destination vertex/. The 
  and the second edge is called the 
  and the 
  is marked as /primal/, and both edges have a
  The facet-edge data structure was described by D.Dobkin and J.Laszlo
  in the paper "Primitives for the Manipulation of Three-Dimensional
  Subdivisions" (/Algorithmica/, 1989)
  
  The structure represents the topology of a 3D map {M} on a 3D
  topological space {X}. In the comments of this interface, we denote
  by {dim(e)} the dimension of any element {e} of {M}. An element is a
  /vertex/, /edge/, /wall/, or /cell/ depending on whether its
  dimension is 0,1,2, or 3.
  
  The structure is defined in terms of a triangulation {S} of {X} that
  is a barycentric sudivision of {M}. (The precise geometry of {S} is
  irrelevant since the data structure depends only on its topology,
  which is determined by that of {M}.) We write {M[s]} for the unique
  element {e} of {M} that contains element {s} of {S}. Conversely, we
  write {S[e]} for the unique vertex of {S} that is contained in
  element {e} of {M}. 
  
  We denote by {V(s)} the set of vertices of an element {s} of {S},
  and by {typ(s)} its /type/, defined as the set of integers
  {{dim(M[v]) : v in V(s)}}. Note that a {k}-element of {S} has {k+1}
  distinct vertices, all with distinct types, and two elements {s,t}
  have {V(s)==V(t)} iff {s==t}. 
  
  If {s} is a cell of {S}, we denote by {flp[i](s)} the cell {t} of
  {S} such that {V(t)} differs from {V(s)} only by the vertex of type
  {i}. Note that {flp[i](flp[i](s)) = s} for any {i} and {s}. 
  It is known that the {flp[]} functions determine completely the 
  topology of {S}, and therefore that of {M} and {M*}. */
  
/*
  
  Now, the {S} cells can be partitioned into groups of four, each
  arranged as a {2×2} matrix, such that {flp[0]} and {flp[3]} merely
  swap rows and columns, respectively, within each block. The
  facet-edge data structure takes advantage of this fact to reduce the
  number of pointers needed to encode the {flp[]} functions. Namely,
  it uses a single data record to represent the four cells of each
  orbit, so that each cell can be encoded as a pointer plus two bits.
  The functions {flp[0]} and {flp[3]} then merely coplement those
  bits, while {flp[1]} and {flp[2]} are stored as eight pointers in
  that record.
  
  Thus, each data record can be seen as representing a /wedge/ of {X},
  defined as the union of those four {S}-cells together with the four
  {S}-faces of types {{0,1,2},{1,2,3}} and the {S}-edge of type
  {{1,2}} that those cells incide on.
  
  The four blocks that comprise a wedge are also incident to 
  two {S}-edges of type {0,1} and an {S}-vertex of type {1}
  whose union is an edge of {M}. They are also incident to 
  two {S}-edges of type {2,3} and an {S}-vertex of type {2},
  which comprise an edge {f*} of {M*} -- that is, the dual
  of a face {f} of {M}. 
  
  The triangulation {S} is also a barycentric subdivision of {M*},
  and the type of an element {s} relative to {M*} is obtained 
  by replcing each vertex type {i} by {3-i}.
  
*/

/*
  The oriented elements associated with {p} are called
  
     {p.el[1]}: the /pike/ of {p} (an oriented edge of {p}'s map).
     {p.el[2]}: the /flap/ of {p} (an oriented wall of {p}'s map).

  Let {a} be the link of type {{0,1}} that bounds the quad {p.s}. 
  The /internal orientation implied by {p}/ on {a}
  is defined so that positive sense of
  travel on {a} goes from {p.s.v[0]} to {p.s.v[1]}. 
  The internal orientations implied by {p} on its
  pike {p.el[1]} agrees, by definition with this
  orientation on {a}. 
  
  let {f} be the The internal orientation on the flap {p.el[2]} is such that
  the flag of type {{0,1,2}}
  
  Their duals are

     {p*.el[1]}: the /dart/ of {p} (an oriented edge of the dual map).
     {p*.el[2]}: the /dish/ of {p} (an oriented wall of the dual map).
  
   along {a} and from {p.s.v.[3]} to {p.s.v[2]}
  along {b} and dart {p.el[2]*}
  
  Let {a} and {b} be the links of type {{0,1}} and {{2,3}}, respectively,
  that bound the quad {p.s}.  The /internal orientation implied by {p}/ on {a} and {b}
  is defined so that positive sense of
  travel goes from {p.s.v[0]} to {p.s.v[1]} along {a} and from {p.s.v.[3]} to {p.s.v[2]}
  along {b}.  The internal orientations implied by {p} on its
  pike {p.el[1]} and dart {p.el[2]*}, by definition, agree
  with these orientation on {a} and {b}.  It follows that 
  {p.el[1] == p*.el[1]} the same orin
  
  the oriented dual edge {p.el[2]*} is the /dart/ of {p}. [!!!] 

  The node {p.el[0]} is the /origin/ of {p.el[1]}, and the cell
  {p.el[3]} is the /hither/ of {p.el[2]}. [!!!]

  Each quad of {S} is therefore identified by a wedge record pointer and
  two bits. The operation {flp[0]} merely complements one bit, while
  {flp[3]} complements the other one. */



*/


  /* Description for computational of bits for Spin and Srot
    If "a == spin^s(srot^r(a0))", where "a0" is the base place
    of "a", "r" in [0..3], and "s" in [0..1], then "PBits(a) == (2r + s)".
    Therefore,

    | a.spin.bits == XOR(PBits(a), 1)
    | If sbit is 0
    |   a.srot.bits == (PBits(a) + 2) MOD 8 
    | otherwise
    |   a.srot.bits == (PBits(a) + 6) MOD 8

 The place {NextF(a)} is given by {PWedge(a)->next[RotBits(a)]},
 provided that {SpinBit(a) == 0}. Otherwise {NextF(a)} is computed by 
 the formula {NextF(a) == Spin(Clock(NextF(Clock(Spin(a)))))}. */
*/