1 /*<html><pre> -<a href="qh-merge.htm" 2 >-------------------------------</a><a name="TOP">-</a> 3 4 merge.h 5 header file for merge.c 6 7 see qh-merge.htm and merge.c 8 9 copyright (c) 1993-2003, The Geometry Center 10 */ 11 12 #ifndef qhDEFmerge 13 #define qhDEFmerge 1 14 15 16 /*============ -constants- ==============*/ 17 18 /*-<a href="qh-merge.htm#TOC" 19 >--------------------------------</a><a name="qh_ANGLEredundant">-</a> 20 21 qh_ANGLEredundant 22 indicates redundant merge in mergeT->angle 23 */ 24 #define qh_ANGLEredundant 6.0 25 26 /*-<a href="qh-merge.htm#TOC" 27 >--------------------------------</a><a name="qh_ANGLEdegen">-</a> 28 29 qh_ANGLEdegen 30 indicates degenerate facet in mergeT->angle 31 */ 32 #define qh_ANGLEdegen 5.0 33 34 /*-<a href="qh-merge.htm#TOC" 35 >--------------------------------</a><a name="qh_ANGLEconcave">-</a> 36 37 qh_ANGLEconcave 38 offset to indicate concave facets in mergeT->angle 39 40 notes: 41 concave facets are assigned the range of [2,4] in mergeT->angle 42 roundoff error may make the angle less than 2 43 */ 44 #define qh_ANGLEconcave 1.5 45 46 /*-<a href="qh-merge.htm#TOC" 47 >--------------------------------</a><a name="MRG">-</a> 48 49 MRG... (mergeType) 50 indicates the type of a merge (mergeT->type) 51 */ 52 typedef enum { /* in sort order for facet_mergeset */ 53 MRGnone= 0, 54 MRGcoplanar, /* centrum coplanar */ 55 MRGanglecoplanar, /* angle coplanar */ 56 /* could detect half concave ridges */ 57 MRGconcave, /* concave ridge */ 58 MRGflip, /* flipped facet. facet1 == facet2 */ 59 MRGridge, /* duplicate ridge (qh_MERGEridge) */ 60 /* degen and redundant go onto degen_mergeset */ 61 MRGdegen, /* degenerate facet (not enough neighbors) facet1 == facet2 */ 62 MRGredundant, /* redundant facet (vertex subset) */ 63 /* merge_degenredundant assumes degen < redundant */ 64 MRGmirror, /* mirror facet from qh_triangulate */ 65 ENDmrg 66 } mergeType; 67 68 /*-<a href="qh-merge.htm#TOC" 69 >--------------------------------</a><a name="qh_MERGEapex">-</a> 70 71 qh_MERGEapex 72 flag for qh_mergefacet() to indicate an apex merge 73 */ 74 #define qh_MERGEapex True 75 76 /*============ -structures- ====================*/ 77 78 /*-<a href="qh-merge.htm#TOC" 79 >--------------------------------</a><a name="mergeT">-</a> 80 81 mergeT 82 structure used to merge facets 83 */ 84 85 typedef struct mergeT mergeT; 86 struct mergeT { /* initialize in qh_appendmergeset */ 87 realT angle; /* angle between normals of facet1 and facet2 */ 88 facetT *facet1; /* will merge facet1 into facet2 */ 89 facetT *facet2; 90 mergeType type; 91 }; 92 93 94 /*=========== -macros- =========================*/ 95 96 /*-<a href="qh-merge.htm#TOC" 97 >--------------------------------</a><a name="FOREACHmerge_">-</a> 98 99 FOREACHmerge_( merges ) {...} 100 assign 'merge' to each merge in merges 101 102 notes: 103 uses 'mergeT *merge, **mergep;' 104 if qh_mergefacet(), 105 restart since qh.facet_mergeset may change 106 see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> 107 */ 108 #define FOREACHmerge_( merges ) FOREACHsetelement_(mergeT, merges, merge) 109 110 /*============ prototypes in alphabetical order after pre/postmerge =======*/ 111 112 void qh_premerge (vertexT *apex, realT maxcentrum, realT maxangle); 113 void qh_postmerge (char *reason, realT maxcentrum, realT maxangle, 114 boolT vneighbors); 115 void qh_all_merges (boolT othermerge, boolT vneighbors); 116 void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle); 117 setT *qh_basevertices( facetT *samecycle); 118 void qh_checkconnect (void /* qh new_facets */); 119 boolT qh_checkzero (boolT testall); 120 int qh_compareangle(const void *p1, const void *p2); 121 int qh_comparemerge(const void *p1, const void *p2); 122 int qh_comparevisit (const void *p1, const void *p2); 123 void qh_copynonconvex (ridgeT *atridge); 124 void qh_degen_redundant_facet (facetT *facet); 125 void qh_degen_redundant_neighbors (facetT *facet, facetT *delfacet); 126 vertexT *qh_find_newvertex (vertexT *oldvertex, setT *vertices, setT *ridges); 127 void qh_findbest_test (boolT testcentrum, facetT *facet, facetT *neighbor, 128 facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp); 129 facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp); 130 void qh_flippedmerges(facetT *facetlist, boolT *wasmerge); 131 void qh_forcedmerges( boolT *wasmerge); 132 void qh_getmergeset(facetT *facetlist); 133 void qh_getmergeset_initial (facetT *facetlist); 134 void qh_hashridge (setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex); 135 ridgeT *qh_hashridge_find (setT *hashtable, int hashsize, ridgeT *ridge, 136 vertexT *vertex, vertexT *oldvertex, int *hashslot); 137 void qh_makeridges(facetT *facet); 138 void qh_mark_dupridges(facetT *facetlist); 139 void qh_maydropneighbor (facetT *facet); 140 int qh_merge_degenredundant (void); 141 void qh_merge_nonconvex( facetT *facet1, facetT *facet2, mergeType mergetype); 142 void qh_mergecycle (facetT *samecycle, facetT *newfacet); 143 void qh_mergecycle_all (facetT *facetlist, boolT *wasmerge); 144 void qh_mergecycle_facets( facetT *samecycle, facetT *newfacet); 145 void qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet); 146 void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet); 147 void qh_mergecycle_vneighbors( facetT *samecycle, facetT *newfacet); 148 void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex); 149 void qh_mergefacet2d (facetT *facet1, facetT *facet2); 150 void qh_mergeneighbors(facetT *facet1, facetT *facet2); 151 void qh_mergeridges(facetT *facet1, facetT *facet2); 152 void qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex); 153 void qh_mergevertex_del (vertexT *vertex, facetT *facet1, facetT *facet2); 154 void qh_mergevertex_neighbors(facetT *facet1, facetT *facet2); 155 void qh_mergevertices(setT *vertices1, setT **vertices); 156 setT *qh_neighbor_intersections (vertexT *vertex); 157 void qh_newvertices (setT *vertices); 158 boolT qh_reducevertices (void); 159 vertexT *qh_redundant_vertex (vertexT *vertex); 160 boolT qh_remove_extravertices (facetT *facet); 161 vertexT *qh_rename_sharedvertex (vertexT *vertex, facetT *facet); 162 void qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex); 163 void qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges, 164 facetT *oldfacet, facetT *neighborA); 165 boolT qh_test_appendmerge (facetT *facet, facetT *neighbor); 166 boolT qh_test_vneighbors (void /* qh newfacet_list */); 167 void qh_tracemerge (facetT *facet1, facetT *facet2); 168 void qh_tracemerging (void); 169 void qh_updatetested( facetT *facet1, facetT *facet2); 170 setT *qh_vertexridges (vertexT *vertex); 171 void qh_vertexridges_facet (vertexT *vertex, facetT *facet, setT **ridges); 172 void qh_willdelete (facetT *facet, facetT *replace); 173 174 #endif /* qhDEFmerge */ 175