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