1
/*<html><pre> -<a href="qh-merge.htm"
2
>-------------------------------</a><a name="TOP">-</a>
5
header file for merge.c
7
see qh-merge.htm and merge.c
9
copyright (c) 1993-2003, The Geometry Center
16
/*============ -constants- ==============*/
18
/*-<a href="qh-merge.htm#TOC"
19
>--------------------------------</a><a name="qh_ANGLEredundant">-</a>
22
indicates redundant merge in mergeT->angle
24
#define qh_ANGLEredundant 6.0
26
/*-<a href="qh-merge.htm#TOC"
27
>--------------------------------</a><a name="qh_ANGLEdegen">-</a>
30
indicates degenerate facet in mergeT->angle
32
#define qh_ANGLEdegen 5.0
34
/*-<a href="qh-merge.htm#TOC"
35
>--------------------------------</a><a name="qh_ANGLEconcave">-</a>
38
offset to indicate concave facets in mergeT->angle
41
concave facets are assigned the range of [2,4] in mergeT->angle
42
roundoff error may make the angle less than 2
44
#define qh_ANGLEconcave 1.5
46
/*-<a href="qh-merge.htm#TOC"
47
>--------------------------------</a><a name="MRG">-</a>
50
indicates the type of a merge (mergeT->type)
52
typedef enum { /* in sort order for facet_mergeset */
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 */
68
/*-<a href="qh-merge.htm#TOC"
69
>--------------------------------</a><a name="qh_MERGEapex">-</a>
72
flag for qh_mergefacet() to indicate an apex merge
74
#define qh_MERGEapex True
76
/*============ -structures- ====================*/
78
/*-<a href="qh-merge.htm#TOC"
79
>--------------------------------</a><a name="mergeT">-</a>
82
structure used to merge facets
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 */
94
/*=========== -macros- =========================*/
96
/*-<a href="qh-merge.htm#TOC"
97
>--------------------------------</a><a name="FOREACHmerge_">-</a>
99
FOREACHmerge_( merges ) {...}
100
assign 'merge' to each merge in merges
103
uses 'mergeT *merge, **mergep;'
105
restart since qh.facet_mergeset may change
106
see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
108
#define FOREACHmerge_( merges ) FOREACHsetelement_(mergeT, merges, merge)
110
/*============ prototypes in alphabetical order after pre/postmerge =======*/
112
void qh_premerge (vertexT *apex, realT maxcentrum, realT maxangle);
113
void qh_postmerge (char *reason, realT maxcentrum, realT maxangle,
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);
174
#endif /* qhDEFmerge */