INTERFACE Map3D; (* A data structure for encoding the topology of a three-dimensional map (a subdivision of a three-dimensional variety into cells, faces, edges, and vertices, with certain topological constraints). Created on 1998 by Luis Arturo Perez Lozada (as Octf.i3), with modifications by J. Stolfi. (See notice of copyright at the end of this file.) This is a variant of the Faced-Edge data structure described in "Primitives for the Manipulation of Three-Dimensional Subdivisions" by D. Dobkin and J. Laszlo (Algorithmica, 1989). Some details are inspired on the implementation of the Quad-Edge data structure by J. Stolfi and R. Marcone Rosi. *) IMPORT Wr, Rd; TYPE T = Handle; (* A handle into a 3D map. *) (* ====== FaceEdge records ====== *) (* The data structure consists of "FaceEdge" nodes. Each FaceEdge record represents an instance of incindence between a face and an edge of the map, together with the corresponding instance of incidence between the corresponding elements in the dual map. *) TYPE FaceEdge <: PublicFaceEdge; PublicFaceEdge = OBJECT num: FaceEdgeNum := 0; (* Serial number of face-edge incidence. *) END; FaceEdgeNum = [0..MaxFaceEdges-1]; (* ====== Handles into the data structure ====== *) (* A "Handle" is a "FaceEdge" together with three bits that specify a `view' of it (one of the two dual maps), plus two orientation bits, `flow' (sense of motion along the edge), and `spin' (sense of motion through the face). There are thus eight handles corresponding to each face-edge incidence, four each for the two dual maps. The "Handle" is the basic data type accepted and returned by most functions in this interface. The flow and spin bits make it possible to distinguish the origin vertex from the destination, the positive cell from the negative, and the next "Handle" along the same face or around the same edge. The view bit makes it possible to obtain and manipulate the dual of a map at essentially zero cost. *) TYPE Handle = RECORD fe: FaceEdge; bits: VFEBits END; VFEBits = [0..7]; (* View and orientation bits. *) HandleNum = [0..MaxHandles-1]; TYPE T = Handle; (* A subdivision is usually handled by one of its handles. *) (* ====== Face-Edge orientation functions ====== *) PROCEDURE RevF(a: Handle): Handle; (* Reverses face orientation (spin) only. *) PROCEDURE RevE(a: Handle): Handle; (* Reverses edge orientation (flow) only. *) PROCEDURE Flip(a: Handle): Handle; (* Flips both edge and face orientations. *) (* ====== Face-Edge traversal functions ====== *) PROCEDURE NextF(a: Handle): Handle; (* Next face around same edge. *) PROCEDURE PrevF(a: Handle): Handle; (* Previous face around same edge. *) PROCEDURE NextE(a: Handle): Handle; (* Next edge around same face. *) PROCEDURE PrevE(a: Handle): Handle; (* Previous edge around same face. *) (* ====== The GEM interpretation ====== *) (* The orientation and traversal functions always obey the following axioms: for any handle "a", and any integer "k", | `Gem' axioms for RevE, RevF: | G1e. RevE(RevE(a)) = a. | G1f. RevF(RevF(a)) = a. | G2e. RevE(a) # a. | G2f. RevF(a) # a. | `Foursome' axiom: | F1. RevE(RevF(a)) = RevF(RevE(a)). | `Gem' axioms for NextE,NextF: | G3e. RevE(NextE(RevE(NextE(a)))) = a. | G3f. RevF(NextF(RevF(NextF(a)))) = a. | G4e. RevE(NextE(a)) # a. | G4f. RevF(NextF(a)) # a. | `Inversion' axioms (definition of PrevE and PrevF): | I1e. PrevE(a) = RevE(NextE(RevE(a))). | I1f. PrevF(a) = RevF(NextF(RevF(a))). | `Bipolar' axioms: | B1e. NextE(RevF(a)) = RevF(NextE(a)). | B1f. NextF(RevE(a)) = RevE(NextF(a)). | B2e. NextE^k(a) # RevF(a). | B2f. NextF^k(a) # RevE(a). The `Gem' axioms G1-G4 are sufficient to provide an unambiguous interpretation of the data structure as a triangulation of a three-dimensional topological manifold, the so-called GEM interpretation (Graph-Encoded Manifold; S. Lins and A. Mandel, ~1985). In this view, each handle is modeled as a geometrical tetrahedron with corners labeled {0,1,2,3}. For each tetrahedron "a" and each label "k", the triangular face opposite to the "k"-labeled corner of "a" is glued to the corresponding face of tetrahedron "sk(a)", where | s0(a) = RevE(a) | s1(a) = RevE(NextE(a)) | s2(a) = RevF(NextF(a)) | s3(a) = RevF(a) Specifically, the two faces are glued by identifying the corners with matching labels, and extending that identification to the rest of the triangles, by affine interpolation. The `Gem' axioms G1--G4 say simply that the functions "s0--s3" are proper involutions, and hence the gluing described above identifies each face of each tetrahedron "a" with exactly one other face in some tetrahedron "b" distinct from "a". The `Gem' axioms ensure that, except for tetrahedral corners, each point of the resulting space has a neighborhood homeomorphic to a 3-ball. Threfore, if we remove the corners, the resulting space is a 3-manifold. The neighborhood of a corner "p" with label "k" consists of two or more tetrahedra, all with "p" as a corner, glued according to the functions "sj" with "j # k". The resulting space is a ball only if its free border (the union of all "k"-labeled faces of those tetrahedra) has the topology of a sphere S^2. This is a global condition that is NOT enforced by the data structure, and is left for the client to worry about. The remaining axioms allow the data structure to be interpreted as a `three-dimensional map:' a decomposition of the space into three-dimensional cells, disk-like faces, segment-like edges, and point-like vertices. In this view, specifically, each 0-labeled corner of the gem model is a vertex of the map. Each 1-labeled corner, together with the (open) gem segments connecting it to adjacent 1-labeled corneres, is an edge of the map. Each 2-labeled corner, together with the (open) gem segments and triangles connecting it to 0- and 1-labeled corners, it a face of the map. Finally, each 3-labeled corner, together with the open segments, triangles, and tetrahedra incident to it, is a cell of the map. The role of the extra axioms is to guarantee that edges and faces have the proper topology. To begin with, the `Foursome' axiom F1, together with the `Gem' axioms G1 and G2, implies that the orbit of a handle through "{RevE,RevF}" has precisely four elements. Moreover, axioms G3 and G4 imply that "NextE" and "NextF" have functional inverses, which are named "PrevE" and "PrevF" by the `Inversion' axioms. Therefore "NextE" and "NextF" are permutations of handles (but not, usually, involutions). Finally, the `Bipolar' axioms state that the orbits of "NextE" come in disjoint pairs of same cardinality, with corresponding handles in each pair connected by "RevF"; and analogously for "NextF" and "RevE". These orbit pairs correspond to the faces and edges of the map, respectively. Thus, with axiom F1, axioms B1e and B1f guarantee that such edges have at most two endpoints, and faces have at most two sides; while B2e and B2f forbid one-ended edges and one-sided faces. As a corollary, these axioms also guarantee that the neighborhoods of gem corners labeled 1 and 2 (which are the centers of map edges and faces) are indeed 3-balls. On the other hand, these neighborhoods of 0- and 3-labeled corners may not be 3-balls. *) (* ====== Dual views of the map ====== *) PROCEDURE Dual(a: Handle): Handle; (* Changes to dual view, keeps orientations. *) (* The face-edge structure actually represents a pair of mutually dual maps, where the "k"-dimensional elements of one map correspond to "(3-k)"-dimensional elements of the other. The "Dual" function takes any handle "a" on one map to a corresponding handle "a*" of the other, with dualized components and consistent orientations. The "Dual" function satisfies the following additional `Duality' axioms: for any handle "a", | D1. Dual(Dual(a)) = a. | D2. Dual(a) # a. | D3e. RevF(Dual(a)) = Dual(RevE(a)). | D3f. RevE(Dual(a)) = Dual(RevF(a)). | D4e. NextE(Dual(a)) = Dual(NextF(a)). | D4f. NextF(Dual(a)) = Dual(NextE(a)). In the gem interprettion, these axioms ensure that "Dual" is a proper involution that swaps each gluing involution "sk" with the one of complementary label: "s0(Dual(u)) = Dual(s3(u))", "s1(Dual(u)) = Dual(s2(u))". It follows from D1--D3 that the orbit of a handle "a" through "{RevF,RevE,Dual}" has exactly eight elements. These elements are the `octet' of handle "a". Note that axiom D2 ensures separation of the primal and dual views only at the local level (within each octet). It is possible to have a data structure with a handle "a" for which "Dual(a) = g(a)" where "g" is some combination of "{NextE,NextF,RevE,RevF}". ??? Is this possible ??? Such `amphotheric' data structures cannot be interpreted as maps. | `View Separation' axiom: | V1. g(a) # Dual(a) For any combination g of {NextE,NextF,RevE,RevF} Finally, the `Separate Views' axiom says that the set of all handles can be partitioned in at least two non-empty subsets, such that "{NextE,NextF,RevE,RevF}" are confined wholly to each subset, whereas "Dual" always maps to a different subset. *) (* ====== QuadEdge emulation ========= *) (* These procedures can be used to traverse the boundary of the cell NegC(s), as if it were a quad-edge data structure. *) PROCEDURE Onext(s: Handle): Handle; (* Next edge around the origin of "s". Same as Flip(PrevF(PrevE(s))). *) PROCEDURE Oprev(s: Handle): Handle; (* Previous edge around the origin of "s". Same as Flip(PrevE(PrevF(s))). *) PROCEDURE Lnext(s: Handle): Handle; (* Same as NextE(s) *) PROCEDURE Lprev(s: Handle): Handle; (* Same as PrevE(s) *) PROCEDURE Sym(s: Handle): Handle; (* Same as Flip(PrevF(s)). *) (* ====== Safe splicing ====== *) PROCEDURE MeldFaces(a, b: Handle); (* Splices two maps (or two parts of the same map) across the faces Fce(a) and Fce(b), which must have the same degree. For any integer "k", let "ak = NextE^k(a)", "bk = NextE^k(b)". if, before the operation, we have PrevF(ak) = ak-, NextF(ak) = ak+ PrevF(bk) = bk-, NextF(bk) = bk+ then after the operation we have NextF(ak-) = bk, NextF(bk) = bk+ NextF(bk-) = ak+, NextF(ak) = ak As a result, the face Fce(a) is removed from the melded map. Note that the VPNode and EFNode fields are not touched. This procedure preserves all axioms, including the `Bipolar' ones. It may however create non-ball cells, or vertices with non-ball neighborhoods. *) (* ====== Computing Bits ====== *) PROCEDURE BaseHandle(fe: FaceEdge): Handle; (* Returns the base handle for the given face-edge incidence record. The various view and orientation bits below are relative to the base handle (0 = same, 1 = opposite). *) TYPE EBit = [0..1]; (* Edge orientation bit (`flow'). *) FBit = [0..1]; (* Face orientation bit (`spin'). *) VBit = [0..1]; (* View bit (primal/dual). *) FEBits = [0..3]; (* Orientation bits. *) PROCEDURE FaceOrientation(a: Handle): FBit; (* Face orientation bit of "a", relatve to the base handle. *) PROCEDURE EdgeOrientation(a: Handle): EBit; (* Edge orientation of "a" relative to the base handle. *) PROCEDURE DualBit(a: Handle): VBit; (* View (primal/dual) bit, relative to the base handle. *) PROCEDURE FaceEdgeOrientation(a: Handle): FEBits; (* Face and edge orientations of "a", relative to the base handle. Same as . *) (* Axioms: | FaceOrientation(RevE(a)) = FaceOrientation(a) | FaceOrientation(RevF(a)) = 1 - FaceOrientation(a) | EdgeOrientation(RevF(a)) = EdgeOrientation(a) | EdgeOrientation(RevE(a)) = 1 - EdgeOrientation(a) | EdgeOrientation(Dual(a)) = FaceOrientation(a) | FaceEdgeOrientation(a) = 2*FaceOrientation(a) + EdgeOrientation(a) *) (* ====== Counting ====== *) PROCEDURE FaceDegree(a: Handle): CARDINAL; (* Number of sides of Fce(a), i.e. the least positive k such that NextE^k(a) = a. *) PROCEDURE EdgeDegree(a: Handle): CARDINAL; (* Number of face incidences on "Edg(a)", i.e. the least positive k such that NextF^k(a) = a. *) (* ====== Creation ====== *) PROCEDURE MakeRawFaceEdge(): Handle; (* Creates a new fe record and returns its base handle. The result r has NextF(RevE(Dual^k(r)) = RevE(Dual^k(r) for all k. Does not create any vertex, edge, face, or polyedron records --- the client must create them and call SetXXXAll as needed. *) (* ======= Element data records ======= *) TYPE ElemNode <: PublicElemNode; PublicElemNode = OBJECT num: CARDINAL; (* Serial number of element within its class. *) END; ElemDimension = [0..3]; (* ======= Edge/face data records ======= *) TYPE EFNode <: PublicEFNode; (* Data record for edge or face *) PublicEFNode = ElemNode OBJECT END; EFHandle = RECORD fe: ElemNode; bits: VEFBits END; (* Handle to an oriented edge of the primal or dual subdivision. *) PROCEDURE Edg(a: Handle): EFHandle; (* The edge record of Handle "a". *) PROCEDURE SetEdgAll(a: Handle; n: EFNode); (* Sets to "n" the edge record of all handles with same edge as "a". *) PROCEDURE Fce(a: Handle): EFHandle; (* The face record of handle "a". *) PROCEDURE SetFceAll(a: Handle; n: EFNode); (* Sets to "n" the face record of all handles with same face as "a". *) (* ======= Vertex/cell data records ======= *) TYPE VPNode <: PublicVPNode; (* Data record for vertex or cell *) PublicVPNode = ElemNode OBJECT END; PROCEDURE Org(a: Handle): VPNode; (* The origin vertex record of handle "a". *) PROCEDURE SetOrgAll(a: Handle; n: VPNode); (* Sets to "n" the origin vertex record for all handles "t" with the same origin as "a". *) PROCEDURE Dst(a: Handle): VPNode; (* The destination vertex record of handle "a". *) PROCEDURE SetDstAll(a: Handle; n: VPNode); (* Sets to "n" the destination vertex record for all handles "t" with the same destination as "a". Same as "SetOrgAll(Flip(t),n)". *) PROCEDURE PosC(a: Handle): VPNode; (* The positive cell record of handle "a". *) PROCEDURE SetPosCAll(a: Handle; n: VPNode); (* Sets to "n" the positive cell record for all handles "t" with same positive cell as "a". Same as SetOrgAll(RevE(Dual(a), n) *) PROCEDURE (a: Handle): VPNode; (* The negative cell record of handle "a". *) PROCEDURE SetNegCAll(a: Handle; n: VPNode); (* Sets to "n" the negative cell record for all handles "t" with same negative cell as "a". Same as SetOrgAll(RevE(Dual(a), n) *) (* ======= Low-level data record updating (use with care!) ====== *) PROCEDURE SetEdgSingle(a: Handle; n: EFNode); (* Set the component edge of handle fe "a.fe" equal to "n". *) PROCEDURE SetFceSingle(a: Handle; n: EFNode); (* Set the component face of handle fe "a.fe" equal to "n". *) PROCEDURE SetOrgSingle(a: Handle; n: VPNode); (* Set the origin of handle "a" to be "n". *) PROCEDURE SetDstSingle(a: Handle; n: VPNode); (* Set the destination of handle "a" to be "n". Same as "SetOrgSingle(Flip(a),n)". *) PROCEDURE SetPosCSingle(a: Handle; n: VPNode); (* Sets the cell positive of "a" to "n". Same as "SetOrgSingle(RevE(Dual(a),n)". *) PROCEDURE SetNegCSingle(a: Handle; n: VPNode); (* Set the cell negative of "a" to "n". Same as "SetOrgSingle(RevE(Dual(a),n)". *) (* ====== Traversal ====== *) TYPE VisitProc = PROCEDURE(a: Handle); (* A client-provided handle visitation procedure. *) PROCEDURE EnumHandles(READONLY a: ARRAY OF Handle; visit: VisitProc; fes: BOOLEAN := FALSE); (* Enumerates all handles "t" that can be reached from some "a[i]" by nextE/NextF chains, and calls "visit(t)" for each of them. If "fes" is "FALSE" (default), each of the handles "t" and "Flip(t)" is passed to the VisitProc exactly once. If "fes" is "TRUE", only the handle "t" is passed to the VisitProc exactly once. If the algebra is well-formed, only handles of same primduality as "a[i]" will ever be enumerated; that is, the procedure will never visit "Dual(t)" "RevE(Dual(t))", "RevF(Dual(t)" or "Flip(Dual(t))" if it visits the handle "t". *) (* ====== Enumeration ====== *) PROCEDURE OutgoingEdges(a: Handle): REF ARRAY OF Handle; (* Returns a list of handles, with one representative handle for every edge with the same origin as the handle "a". *) PROCEDURE BoundingFaces(a: Handle): REF ARRAY OF Handle; (* Returns a list of handles, with one representative handle for every face with the same negative cell as the handle "a". *) PROCEDURE FaceSides(a: Handle): REF ARRAY OF Handle; (* Returns a list of handles on the facet Fce(a), with one handle along each side of that facet. *) PROCEDURE EdgeWings(a: Handle): REF ARRAY OF Handle; (* Returns a list of handles on the edge Edg(a), with one handle on each wing of that edge. *) (* ====== Handle numbering ====== *) CONST MaxHandles = LAST(CARDINAL) DIV 2; (* Maximum number of handles in a map *) MaxFaceEdges = MaxHandleNum DIV 8; (* Maximum number of face-edge incidences. *) PROCEDURE GetHandleNum (a: Handle): HandleNum; (* = "a.fe.num * 8 + a.bits" *) (* ====== Printout ====== *) PROCEDURE FmtHandle(a: Handle; feWidth: CARDINAL := 1): TEXT; (* Formats a handle "a" as "m:dfe", where "m" is the serial face-edge number, and "d,f,e" are bits such that "a = h.Dual^d.RevE^e.RevF^f", where "h" is the base handle of the face-edge. The face-edge number will be left-padded with spaces to "feWidth" bytes. *) PROCEDURE ReadHandle(rd: Rd.T; READONLY map: ARRAY OF FaceEdge): Handle; (* Reads from "rd" an handle in the "m:dfe" format used by "PrintHandle". The "map" table is used to convert the fe number "m" into a FaceEdge pointer. *) PROCEDURE PrintFaceEdge(wr: Wr.T; fe: FaceEdge; feWidth: CARDINAL := 1); (* Prints on "wr" the topological data of the face-edge "fe", namely the four handles BaseHandle(fe). four handles NextF(RevE(Dual^i(s)), where "s = Handle{n, 0}" and "i = 0..3". Handles are separated by one space. Each handle is printed using "PrintHandle", with fe numbers left-padded to "feWidth" bytes. *) PROCEDURE ReadFaceEdge(rd: Rd.T; n: FaceEdge; READONLY map: ARRAY OF FaceEdge); (* Reads from "rd" four handles "a[0..3]", using "ReadHandle(rd, map)". Then performs "SetNextF(RevE(Dual^i(s), a[i])", where "s = Handle{n,0}" and "i = 0..3". *) END Map3D. (**************************************************************************) (* *) (* 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-07 08:04:07 by stolfi *) (**************************************************************************)