#ifndef Triangulation_H #define Triangulation_H /* Last edited on 2025-01-09 23:26:30 by stolfi */ /* 3D triangulations represented with the facet-edge data structure. */ #define Triangulation_H_copyright \ "Copyright © 2001 Universidade Estadual de Campinas (UNICAMP)" #define Triangulation_H_author \ "Created by L. Lozada in 1999-2001???.\n" \ "Based on J. Stolfi and R. Marcone's 2D Triangulation.i3, ca. ????." #define _GNU_SOURCE #include #include #include #include #include #include #include #include /* ELEMENT CREATION */ typedef struct FourNodes_t { Node_t v[4]; } FourNodes_t; FourNodes_t TetraNegNodes(Place_t p); /* The nodes of the tetrahedron {PnegP(a)}. */ FourNodes_t TetraPosNodes(Place_t p); /* The nodes of the tetrahedron {PposP(a)}. */ typedef struct FiveNodes_t { Node_t n[5]; } FiveNodes_t; FiveNodes_t TetraNegPosNodes(Place_t p); /* The nodes of the tetrahedra {PnegP(a)} and {PposP(a)}. */ typedef struct FourWalls_t { Wall_t f[4]; } FourWalls_t; FourWalls_t TetraWalls(Place_t p); /* The four walls of the tetrahedron {PnegP(a)}. */ typedef struct SixEdges_t { Edge_t e[6]; } SixEdges_t; SixEdges_t TetraEdges(Place_t p); /* The six edges of the tetrahedron {PnegP(a)}. */ typedef struct ThreeEdges_t { Edge_t e[3]; } ThreeEdges_t; ThreeEdges_t TriangEdges(Place_t p); /* The three edges of the wall of {p}. */ /* BORDER CHECKING */ bool_t EdgeIsBorder(Place_t p); /* TRUE if the edge of {p} belongs to the manifold's border (i.e. bounds a NULL cell). */ bool_t WallIsBorder(Place_t p); /* TRUE iff the wall of {p} belongs to the manifold's border. Same as {PposP(p) == NULL) || (PnegP(p) == NULL}. */ /* MAP ELEMENT CONSTRUCTION */ void EmphasizeTetrahedron(Place_t a, Place_t b, uint n); /* Emphasizes the original elements of a tetrahedron produced by the MakeTetraTopo(order,order) procedure. */ EightPlaces_t MakeTetraTopo(uint nx, uint ny); /* Builds a topological tetrahedron subdivided radialy. The number of tetrahedra cells is {nx} by {ny}. Returns eight places at the corner wedges. */ Place_t Glue(Place_t a, Place_t b, uint n, bool_t setorg /* DF TRUE */); /* Glues two topological tetrahedra, by identification the {n} triangular walls on the topological boundary of tetrahedra. The places {a} and {b} must have the same {OrientationBit} and {SpinBit}. After teh call we will have {PnegP(a) == PnegP(b)}. The traversal of the topological boundary will be realized by quad-edge functions reduced to functions wedge. The identification of triangular walls will be done by the {Meld} procedure, removing the wedges on the chain {b} and updating the relations between nodes and cells. If {setorg == TRUE} then {SetOrgAll} is executed. */ TwelvePlaces_t GetTetraCorners(Place_t p); /* This procedure builds an array of 12 wedge @places, such all elements on the array have the same handness and the same negative poly. {PnegP}. The {p} in the argument must be a @place that represent one tetrahe- dron of $T$ (in the primal space). */ Place_vec_t *CollectTetrahedra(ElemTableRec_t *top); /* Returns a list {t} with one wedge on each tetrahedron from top in numerical order, with consistent orientations whenever possible. The wedges will be such that PnegP(t[i])->num == i. */ /* LOW-LEVEL ENUMERATION PROCEDURES */ void Collectwedges(Place_t p, Place_vec_t *re, uint *ne); /* Enumerates the @{edge->?}s of wall {a.wall} (with successive {NextE}s) and stores them in {re[0..NE-1]}. Also sets {NE} and (re)allocates {re^} as needed. */ void CollectCellWalls(Place_t p, Place_vec_t *rf, uint *nf); /* Enumerates the walls of cell {PnegP(a)} and stores them in {rf[0..NF-1]}. Also sets {NF} and (re)allocates {rf^} as needed. Assumes that the {xmark} bits of all wall records are FALSE. */ void CollectCellEdges(Place_t p, Place_vec_t *re, uint *NE, Place_vec_t *rf /* Working area */); /* Collects all edges of the cell {PnegP(a)}, returns their representative places in {re[0..NE-1]}. Also sets {NE} and (re)allocates {re^} as needed. Assumes all {xmark} bits are FALSE. The {rf} vector is a working area, expanded as needed; may be NULL initially. */ void CollectCellNodes(Place_t p, Place_vec_t *rv, uint *nv, Place_vec_t *rf /* Working area */); /* Collects all nodes of the cell {PnegP(a)}, returns their {OrgV}-representatives in {re[0..NE-1]}. Also sets {NE} and (re)allocates {re^} as needed. Assumes all {xmark} bits are FALSE. The {rf} vector is a working area, expanded as needed; may be NULL initially. */ /* INPUT/OUTPUT */ typedef struct AdjacencyMatrix_t { int rows; int cols; bool_t **el; } AdjacencyMatrix_t; AdjacencyMatrix_t *MakeAdjacencyMatrix(ElemTableRec_t *top); /* Builds the adjacency matrix for the map element table {top}. */ void GetVariableNodes(ElemTableRec_t *top, bool_vec_t *vr); /* Sets {vr[v] = TRUE} for every node {v} that is not fixed. */ /* GEOMETRIC TOOLS */ typedef r4_vec_t Coords_t; /* Coordinates for all {NodeRec_t}s in the structure. */ void InitCoords(Random_t *coins, Coords_t *c, double radius /* DF 1.0 */); /* Fills c with random coordinates in the range {[-radius __ +radius]}. */ Coords_t GenCoords(Random_t *coins, ElemTableRec_t *top); /* Returns a new {Coords_t} vector {v}, initialized with {InitCoords(&v, 1.0)}. */ void Displace(ElemTableRec_t *top, r4_t *d, Coords_t *c); /* Displaces all existing nodes by {d}. */ void Scale(ElemTableRec_t *top, double s, Coords_t *c); /* Scales the coordinates of all existing nodes by {s}. */ r4_t WallCross(Place_t p, Coords_t *c); /* A vector approximately perpendicular to {wall} field of {p}, this vector is computing by the mean of two perpendicular vectors (with orientation topological consistent) for two tetrahedrons inci- dents in this wall. Returns the unit vector if the wall has atributte {exists==FALSE}. */ r4_t WallNormal(Place_t p, Coords_t *c); /* Normal of {wall} field of {a}; same as {r4_Dir(WallCross(a, c))}. Returns an arbitrary unit vector if the wall has zero area. */ r4_t PolyCross(Place_t p, Coords_t *c); /* A vector approximately perpendicular to PnegP of {p}. Returns the unit vector if the cell has atributte {exists==FALSE}. */ r4_t PolyNormal(Place_t p, Coords_t *c); /* Normal of {PnegP(a)}; same as {r4_Dir(PolyCross(a, c))}. Returns an arbitrary unit vector if the wall has zero area */ r4_t EdgeCross(Place_t p, Coords_t *c); /* A vector approximately perpendicular to component edge of {p}, this vector is computing by the mean of perpendicular vectors (with orientation topological consistent) to all tetrahedrons incidents in this edge. Returns the unit vector if the edge has atributte {exists==FALSE}. */ r4_t EdgeNormal(Place_t p, Coords_t *c); /* Normal of component edge of {a}; same as {r4_Dir(EdgeCross(a, c))}. Returns an arbitrary unit vector if the edge has zero lenght. */ r4_t WallBarycenter(Place_t p, Coords_t *c); /* The barycenter of wall component of {p}. */ r4_t TetraBarycenter(Place_t p, Coords_t *c); /* The barycenter of the negative tetrahedron of {p}. */ r4_t NodeCross(Place_t p, Coords_t *c, ElemTableRec_t *top); /* A vector approximately orthogonal to the OrgV(a), whose length is proportional the volume of the cell defined by the {existing} neighbors of {OrgV(a)}. */ r4_t NodeNormal(Place_t p, Coords_t *c, ElemTableRec_t *top); /* Estimated normal at OrgV(a), considering only neighbors that exist; same as {r4_Dir(NodeCross(a, c))}. Returns an arbitrary unit vector if {NodeCross(a, c)} is zero. */ typedef struct Quadp { Place_t p[4]; } Quadp; typedef struct Quadv { Node_t v[4]; } Quadv; typedef struct Triv { Node_t v[3]; } Triv; typedef struct Trip { Place_t p[3]; } Trip; vec_typedef(Quadv_vec_t,Quadv_vec,Quadv); /* A vector of {Quadv}s. */ Node_vec_t *Neighbors(Place_t p, ElemTableRec_t *top); /* Neighbor nodes of {v}, for any topology. */ Quadv_vec_t *StarOfNode(Place_t p, ElemTableRec_t *top); /* Return the node set that conform every tetrahedron belonging to star of OrgV(a). The node set is sorted such as, the first element is OrgV(a), the second is OrgV(NextE(a)), the third OrgV(PrevE(a)) and the las element is OrgV(PrevE(PrevF(a))). */ uint NumberPolyOfStar(Quadv_vec_t *qv); /* Return the number of cells that belong to star of OrgV(a). */ r4_vec_t *ComputeAllNodeNormals(ElemTableRec_t *top, Coords_t *c); /* Returns a vector with the result of NodeNormal applied to each node of {top}. */ r4_vec_t *ComputeAllEdgeNormals(ElemTableRec_t *top, Coords_t *c); /* Returns a vector with the result of EdgeNormal applied to each @{edge->?} of {top}. */ r4_vec_t *ComputeAllWallNormals(ElemTableRec_t *top, Coords_t *c); /* Returns a vector with the result of Wall Normal applied to each wall of {top}. */ r4_vec_t *ComputeAllCellNormals(ElemTableRec_t *top, Coords_t *c); /* Returns a vector with the result of PolyNormal applied to each polyhe- dron of {top}. */ /* GEOMETRIC AVERAGES */ /* In the following procedures, when {all == TRUE} the quantities are computed over all elements of the appropriate dimension; otherwise they are computed only over those elements with {existing == TRUE}. */ r4_t Barycenter(ElemTableRec_t *top, Coords_t *c, bool_t all); /* Returns the barycenter of all nodes. */ r4_t PartialBarycenter(Node_vec_t *v, Coords_t *c, bool_t all); /* Barycenter of the nodes {v[i]}. Previously called {NeighborBarycenter}. */ double MeanNodeDistance(ElemTableRec_t *top, Coords_t *c, r4_t *ctr, bool_t all); /* The average distance of nodes from {ctr}, in the root-mean-square sense; that is, {sqrt(sum(norm(c[v]-ctr)^2)/N)}. */ double MaxNodeDistance(ElemTableRec_t *top, Coords_t *c, r4_t *ctr, bool_t all); /* The maximum distance of a node from {ctr}. */ double MeanEdgeLength(ElemTableRec_t *top, Coords_t *c, bool_t all); /* The average length of edges, in the root-mean-square sense; that is {sqrt(sum(dist(c[org(e)], c[dst(e)])^2)/N)}. */ r4_t MeanCellNormal(ElemTableRec_t *top, Coords_t *c, bool_t all); /* The average of all tetrahedra normals, normalized to unit length. */ double MeanThickness(ElemTableRec_t *top, Coords_t *c, r4_t *ctr, r4_t *norm, bool_t all); /* Average node deviation from the hyperplane that passes through {ctr} and is orthogonal to {norm}, in the root mean square sense. */ void NormalizeNodeDistances(ElemTableRec_t *top, Coords_t *c, bool_t all); /* Shifts and scales all nodes so that they have barycenter (0,0,0,0) and unit mean square distance from the origin. The {all} parameter is used to compute the barycenter and the mean square distance. */ void NormalizeEdgeLengths(ElemTableRec_t *top, Coords_t *c, bool_t all); /* Shifts and scales all existing nodes so that they have barycenter (0,0,0,0), and the mean square length of existing @{edge->?}s is 1.0. The {all} parameter is used to compute the barycenter and the mean @{edge->?} length. */ /* INPUT/OUTPUT */ void FWriteCoords(FILE *wr, Coords_t *c, char *cmt); /* Writes the vertex coordinates {c} and comment text {cmt} to file {wr}, in a format that can be read back. */ void WriteCoords(char *name, char *tag, int seq, Coords_t *c, char *cmt /* DF "" */); /* Like {FWriteCoords} but writes to a new disk file called "{name}{tag}-{NNNNNN}.st", where {NNNNNN} is the {seq} number, zero-padded to 6 digits. The part "-{NNNNNN}" is supressed if {seq} is negative. */ void FReadCoords(FILE *rd, Coords_t *c, char **cmtP); /* Reads from {rd} a set of vertex coordinates. The file must contain exactly {c.ne} points of {R^4}, which will be stored into {c[0..c.ne-1]}. If {cmtP} is not NULL, also stores into {*cmtP} a pointer to the file's comment text. */ Coords_t ReadCoords(char *name, char *tag, int seq, uint NV); /* Similar to {FReadCoords}, but reads from the disk file called "{name}{tag}-{NNNNNN}.st", where {NNNNNN} is the {seq} number, zero-padded to 6 digits. The part "-{NNNNNN}" is supressed if {seq} is negative. The file must contain exactly {NV} points of {R^4}, which are returned as a newly allocated {Coords_t} vector. The file's comment text is discarded. */ void WriteMaterials(char *name, char *tag, ElemTableRec_t *top, char *cmt /* DF " " */, bool_t ro_te /* DF FALSE */); /* Writes the materials properties to file disk in a format that can be read back. The file will have the given {name} with ".ma" appended. */ void WriteStDe ( FILE *wr, Coords_t *c, /* Node coordinates */ Coords_t *Dc, /* Node coordinates derivates */ uint prec, /* DF 4; Significant figures to use for {c} and {Dc} */ char *cmt /* DF "" */ ); /* Writes the coordinates {c} and derivatives {Dc} to file {wr} in the ".sd" format. */ TopReadData_t ReadToMa(char *name, bool_t ro_te /* DF FALSE */); /* A more general procedure to read two disk files created by {WriteTopology} and {WriteMaterials}. The files must have the given {name} with ".tp" and ".ma". */ Coords_t *ReadState(char *name); /* Reads a disk file created by {WriteState}. The file must have the given {name} with ".st" appended. */ #endif