| 1 |
chuckv |
1138 |
/*<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 */ |
