INTERFACE Octf; (* Facet-Edge data structure. Created on 1998 by Luis Arturo Perez Lozada, (see notice of copyright at the end of this file), inspired in the im- plementation of Quad-Edge data structure (by J. Stolfi and R. Marcone). See : "Primitives for the Manipulation of Three-Dimensional Subdivisions" by D. Dobkin and J. Laszlo, Algorithmica 1989. Last Modification: 03-08-00 by stolfi: - The attribute "pa" for edges and faces is now a pair and not a pointer. *) (* A 'FacetEdge data structure' is a pair of dual subdvisions of a connec- ted 3-Cellular Complexes. An 'facetedge' (n) is an facetedge of the primal or dual subdivision. A 'pair' (a) is an oriented and spined facetedge. A 'quad' is a group of four pairs, consisting of two mutually dual facetedges. An 'octet' is a group of eight pairs, consisting of two mutually dual facetedges in all their spins and orientations. *) IMPORT Wr, Rd, R3; TYPE T = Pair; (* A subdivision is usually handled by one of its pairs. *) Pair = RECORD facetedge: FacetEdge; bits: SRBits END; (*ori+spin facetedge *) SRBits = [0..7]; (* Spin and Rotations bits of base pair *) OBit = [0..1]; (* Orientation bit *) SBit = [0..1]; (* Spin bit *) RBits = [0..3]; (* Rotation bits *) DBit = [0..1]; (* Dual/Primal bit *) PairNum = [0..MaxPairNum]; FacetEdgeNum = [0..MaxFacetEdgeNum]; TYPE Node <: PublicNode; PublicNode = OBJECT num: CARDINAL; END; Edge <: PublicEdge; PublicEdge = OBJECT pa : Pair; (* pair associated *) num : CARDINAL; (* Number of edge component *) dg : CARDINAL; (* For computing degree of vertex *) exists: BOOLEAN := TRUE; (* FALSE for immaterial edges *) xmark: BOOLEAN; (* Mark used by MakePolyhedronTopology *) color: R3.T := R3.T{0.0,0.0,0.0}; (* Color for drawing *) transp: R3.T := R3.T{0.0,..}; (* Transp. coeffs for painting *) radius: REAL := 0.004; (* radius for drawing *) root: INTEGER := -1; (* Parent edge in original map, -1 = none. *) (* degenerate: BOOLEAN := FALSE; (* to mark as an element degenerate *) *) (* vertex: ARRAY [0..1] OF Node; (* endpoints vertices *) *) METHODS init(): Edge; END; Face <: PublicFace; PublicFace = OBJECT pa : Pair; (* pair associated *) num : CARDINAL; (* Number of face component *) exists: BOOLEAN := TRUE; (* FALSE for ghost faces *) xmark: BOOLEAN; (* Mark used by MakePolyhedronTopology *) color: R3.T := R3.T{1.0,1.0,0.20}; (* Color for painting *) transp: R3.T := R3.T{0.7,0.7,0.7}; (* Transp. coeffs for painting *) root: INTEGER := -1; (* Parent face of original map, -1 = none. *) (* vertex: REF ARRAY OF Node; (* endpoints vertices *) *) (* degenerate:BOOLEAN := FALSE; (* to mark an element as degenerate *) *) METHODS init(): Face; END; FacetEdge <: PublicFacetEdge; PublicFacetEdge = OBJECT num: FacetEdgeNum := 0; (* Number of facetedge *) edge: Edge; (* Component edge *) face: Face; (* Component face *) order: CARDINAL; (* used for barycenter subdivision *) ca : ARRAY [0..7] OF Pair; marks: BOOLEAN := FALSE; METHODS init(): FacetEdge; (* Initializes the pointers of "self" so that it describes an isolated facetedge with distinct endpoints. The endpoints of facetedge to corrrespond exactly to endpoints of edge component. *) END; (* ====== Pairs ====== *) (* A "SRBits" value identifies a particular pair within any facetedge, according to the following table (where 'a' is the reference pair of the facetedge): | SRBits pair SBit OBit DBit RBits | -------------------------------------------------- | 000 0 a 0 0 0 0 | 001 1 a.spin 1 0 0 0 | 010 2 a.srot 0 0 1 1 | 011 3 a.srot.spin 1 0 1 1 | 100 4 a.clock 0 1 0 2 | 101 5 a.clock.spin 1 1 0 2 | 110 6 a.tors 0 1 1 3 | 111 7 a.tors.spin 1 1 1 3 In general, the pair "Spin^s(Srot^r(a))", for "r" in [0..3] and "s" in [0..1], has "SRBits" equal to "2r + s". *) (* ====== Facet-Edge dual function ====== *) PROCEDURE Sdual(a: Pair): Pair; (* dual pair facetedge *) (* ====== Facet-Edge senses of rotations functions ====== *) PROCEDURE Spin(a: Pair): Pair; (* reverses spin *) PROCEDURE Srot(a: Pair): Pair; (* rotated vers. of a, "aSrot=aSdualSpin" *) PROCEDURE Clock(a: Pair): Pair; (* "aClock = aSrotSrot" *) PROCEDURE Tors(a: Pair): Pair; (* Inverse of "Srot, "aTors=aSrotSrotSrot" *) (* ====== Facet-Edge traversal functions ====== *) PROCEDURE Fnext(a: Pair): Pair; (* next pair in spin sense with same edge *) PROCEDURE Enext(a: Pair): Pair; (* next pair in orientation sense with same face *) PROCEDURE Fnext_1(a: Pair): Pair; (* n. pair in c. spin sense w. same edge *) PROCEDURE Enext_1(a: Pair): Pair; (* n. pair in c. ori. sense w. same face *) (* ====== Computing Bits ====== *) PROCEDURE OrientationBit(a: Pair): OBit; (* Orientation bit = "SRBits DIV 4". Reversed by "Clock", unchanged by "Spin", may be changed by "Srot". *) PROCEDURE SpinBit(a: Pair): SBit; (* Spin bit = "SRBits MOD 2". Reversed by "Spin". *) PROCEDURE DualBit(a: Pair): DBit; (* Dual bit = "SRBits DIV 2 MOD 2". Unchanged by "Spin" and "Clock", reversed by "Srot". *) PROCEDURE SrotBits(a: Pair): RBits; (* Rot bits = "SRBits DIV 2". Unchanged by "Spin", incremented twice by "Clo- ck", either incremented or decremented by "Srot". *) (* ====== Counting ====== *) PROCEDURE DegreeFaceRing(a: Pair): CARDINAL; (* Number of "Pairs" facetedge with same edege component as "a". *) PROCEDURE DegreeEdgeRing(a: Pair): CARDINAL; (* Number of "Pairs" facetedge with same face component as "a". *) (* ====== Creation ====== *) PROCEDURE MakeFacetEdge(): Pair; (* Creates a new pair facetedge. Equivalent to | Pair{facetedge := NEW(FacetEdge).init(), bits := 0} *) PROCEDURE MakeEdge(): Edge; (* Creates a new component edge. *) PROCEDURE MakeFace(): Face; (* Creates a new component face. *) (* ======= updating ====== *) PROCEDURE SetFace(a: Pair; n: Face); (* Set the component face of pair facetedge "a.facetedge" equal to "n". *) PROCEDURE SetEdge(a: Pair; n: Edge); (* Set the component edge of pair facetedge "a.facetedge" equal to "n". *) PROCEDURE SetFaceAll(a: Pair; n: Face); (* Set the component face of all pairs adjacents to same component face that "a.facetedge" equal to "n". *) PROCEDURE SetEdgeAll(a: Pair; n: Edge); (* Set the component edge of all pairs adjacents to same component edge that "a.facetedge" equal to "n". *) (* ====== Destruction ====== *) PROCEDURE DeleteFacetEdge(a: Pair); (* Delete a pair facetedge "a" with the 7 another pairs associated. *) (* ====== Splicing ====== *) PROCEDURE SpliceFacets(a,b: Pair); (* Merges or splits the facet-rings F_{a} e F_{b} of pairs a and b. *) PROCEDURE SpliceEdges(a,b: Pair); (* Merges or splits the edge-rings E_{a} e E_{b} of pairs a and b. *) PROCEDURE SetFnext(a,b: Pair); (* If "Fnext(a) # b", performs "SpliceFacets(a, Fnext_1(b))". After this call "Fnext(a)" will be equal to "b". Valid whenever "SpliceFacets(a,b)" is va- lid. *) PROCEDURE SetEnext(a,b: Pair); (* If "Enext(a) # b", performs "SpliceEdges(a, Enext_1(b))". After this call, "Enext(a)" will be equal to "b". Valid whenever "SpliceEdges(a,b)" is valid. *) (* ================= Functions of QuadEdge ========= *) PROCEDURE Onext(s: Pair): Pair; (* If DualBit(s) = 0, then return Clock(Fnext(Enext_1(s))) else return Enext_1(s) *) PROCEDURE Onext_1(s: Pair): Pair; (* If DualBit(s) = 0, then return Clock(Fnext_1(Enext_1(s))) else return Enext_1(s) *) (* ====== Meld ========== *) PROCEDURE Meld(a,b : Pair); (* Meld F_{a} com F_{b} *) (* ====== Traversal ====== *) TYPE VisitProc = PROCEDURE(a: Pair); (* A client-provided pair visitation procedure. *) PROCEDURE EnumFacetEdges(a: Pair; visit: VisitProc; facetedges: BOOLEAN := FALSE); (* Enumerates all pairs that can be reached from a by some combination of Enext_1's and Fnext's. If "facetedges" is "FALSE" (default), the pairs "a" and "Srot(a)" is passed to the VisitProc exactly once. If "facetedges" is "TRUE", only the pair "a" is passed to the VisitProc exactly once. If the algebra is well-formed, only pairs of same primduality as "a" will ever be enumerated; that is, the procedure will never visit "Srot(a)" "Spin(Srot(a))", "Tors(a)" or "Spin(Tors(a))" if it visits the pair "a". *) PROCEDURE NumberEdges(READONLY a: ARRAY OF Pair): REF ARRAY OF Edge; (* Enumerates all (primal) edges reachable from "a" by chains of "Enext_1's" and "Fnext's". *) PROCEDURE NumberEdgesForDegree(READONLY a: ARRAY OF Pair): REF ARRAY OF Pair; (* Enumerates all (primal) edges with the same origin that of Pair "a" by chains of "Onext's" and "Fnext's". *) PROCEDURE NumberFacets(READONLY a: ARRAY OF Pair): REF ARRAY OF Face; (* Enumerates all (primal) facets reachable from "a" by chains of "Enext_1's" and "Fnext's". *) (* ====== Numbering ====== *) CONST MaxPairNum = LAST(CARDINAL); (* Maximum pair number *) MaxFacetEdgeNum = MaxPairNum DIV 8; (* Maximum facetedge number *) PROCEDURE NumberFacetEdges(READONLY a: ARRAY OF Pair): REF ARRAY OF Pair; (* Assigns distinct numbers serial to all facetedges reachable from "a" by Enext_1/Fnext chains. Returns a vector with one reachable pair from each facetedge. *) PROCEDURE GetPairNum (a: Pair): PairNum; (* = "a.facetedge.num * 8 + a.bits" *) (* ====== Printout ====== *) PROCEDURE PrintPair( wr: Wr.T; a: Pair; feWidth: CARDINAL := 1; nl : BOOLEAN := FALSE; ); (* Prints pair "a" as "m:r:s", where "m" is the serial facetedge number, and "r,s" are such that "a = Spin^s(Srot^r(a0))", where "a0" is the base pair of the facetedge. The facetedge 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. *) PROCEDURE ReadPair(rd: Rd.T; READONLY map: ARRAY OF FacetEdge): Pair; (* Reads from "rd" an pair in the "m:r:s" format used by "PrintPair". The "map" table is used to convert the facetedge number "m" into an "Facet- Edge" pointer. *) PROCEDURE PrintFacetEdge(wr: Wr.T; n: FacetEdge; feWidth: CARDINAL := 1); (* Prints on "wr" the four pairs Fnext(Srot^i(s)), where "s = Pair{n, 0}" and "i = 0..3". Pairs are separated by one space. Each pair is printed using "PrintPair", with facetedge numbers left-padded to "feWidth" bytes. *) PROCEDURE ReadFacetEdge(rd: Rd.T; n: FacetEdge; READONLY map: ARRAY OF FacetEdge); (* Reads from "rd" four pairs "a[0..3]", using "ReadPair(rd, map)". Then performs "SetFnext(Srot^i(s), a[i])", where "s = Pair{n,0}" and "i = 0..3". *) END Octf. (**************************************************************************) (* *) (* Copyright (C) 1998 Universidade Estadual de Campinas (UNICAMP) *) (* *) (* Authors: *) (* L. P. Lozada & J. Stolfi - UNICAMP *) (* *) (* This file can be freely used, distributed, and modified, provided that *) (* this copyright and authorship notice is included in every copy or *) (* derived version. *) (* *) (* DISCLAIMER: This software is offered ``as is'', without any guarantee *) (* as to fitness for any particular purpose. Neither the copyright *) (* holder nor the authors or their employers can be held responsible *) (* for any damages that may result from its use. *) (* *) (* Last edited on 2001-05-21 02:02:23 by stolfi *) (**************************************************************************)