Reverted incorrect merge (missing files)
[blender.git] / extern / qhull / include / qhull / poly.h
1 /*<html><pre>  -<a                             href="qh-poly.htm"
2   >-------------------------------</a><a name="TOP">-</a>
3
4    poly.h 
5    header file for poly.c and poly2.c
6
7    see qh-poly.htm, qhull.h and poly.c
8
9    copyright (c) 1993-2002, The Geometry Center
10 */
11
12 #ifndef qhDEFpoly
13 #define qhDEFpoly 1
14
15 /*===============   constants ========================== */
16
17 /*-<a                             href="qh-geom.htm#TOC"
18   >--------------------------------</a><a name="ALGORITHMfault">-</a>
19   
20   ALGORITHMfault   
21     use as argument to checkconvex() to report errors during buildhull
22 */
23 #define qh_ALGORITHMfault 0
24
25 /*-<a                             href="qh-poly.htm#TOC"
26   >--------------------------------</a><a name="DATAfault">-</a>
27   
28   DATAfault        
29     use as argument to checkconvex() to report errors during initialhull
30 */
31 #define qh_DATAfault 1
32
33 /*-<a                             href="qh-poly.htm#TOC"
34   >--------------------------------</a><a name="DUPLICATEridge">-</a>
35   
36   DUPLICATEridge
37     special value for facet->neighbor to indicate a duplicate ridge
38   
39   notes:
40     set by matchneighbor, used by matchmatch and mark_dupridge
41 */
42 #define qh_DUPLICATEridge ( facetT * ) 1L
43
44 /*-<a                             href="qh-poly.htm#TOC"
45   >--------------------------------</a><a name="MERGEridge">-</a>
46   
47   MERGEridge       flag in facet
48     special value for facet->neighbor to indicate a merged ridge
49   
50   notes:
51     set by matchneighbor, used by matchmatch and mark_dupridge
52 */
53 #define qh_MERGEridge ( facetT * ) 2L
54
55
56 /*============ -structures- ====================*/
57
58 /*=========== -macros- =========================*/
59
60 /*-<a                             href="qh-poly.htm#TOC"
61   >--------------------------------</a><a name="FORALLfacet_">-</a>
62   
63   FORALLfacet_( facetlist ) { ... }
64     assign 'facet' to each facet in facetlist
65     
66   notes:
67     uses 'facetT *facet;'
68     assumes last facet is a sentinel
69     
70   see:
71     FORALLfacets
72 */
73 #define FORALLfacet_( facetlist ) if ( facetlist ) for( facet=( facetlist );facet && facet->next;facet=facet->next )
74
75 /*-<a                             href="qh-poly.htm#TOC"
76   >--------------------------------</a><a name="FORALLnew_facets">-</a>
77   
78   FORALLnew_facets { ... } 
79     assign 'newfacet' to each facet in qh.newfacet_list
80     
81   notes:
82     uses 'facetT *newfacet;'
83     at exit, newfacet==NULL
84 */
85 #define FORALLnew_facets for( newfacet=qh newfacet_list;newfacet && newfacet->next;newfacet=newfacet->next )
86
87 /*-<a                             href="qh-poly.htm#TOC"
88   >--------------------------------</a><a name="FORALLvertex_">-</a>
89   
90   FORALLvertex_( vertexlist ) { ... }
91     assign 'vertex' to each vertex in vertexlist
92     
93   notes:
94     uses 'vertexT *vertex;'
95     at exit, vertex==NULL
96 */
97 #define FORALLvertex_( vertexlist ) for ( vertex=( vertexlist );vertex && vertex->next;vertex= vertex->next )
98
99 /*-<a                             href="qh-poly.htm#TOC"
100   >--------------------------------</a><a name="FORALLvisible_facets">-</a>
101   
102   FORALLvisible_facets { ... }
103     assign 'visible' to each visible facet in qh.visible_list
104     
105   notes:
106     uses 'vacetT *visible;'
107     at exit, visible==NULL
108 */
109 #define FORALLvisible_facets for (visible=qh visible_list; visible && visible->visible; visible= visible->next)
110
111 /*-<a                             href="qh-poly.htm#TOC"
112   >--------------------------------</a><a name="FORALLsame_">-</a>
113   
114   FORALLsame_( newfacet ) { ... } 
115     assign 'same' to each facet in newfacet->f.samecycle
116     
117   notes:
118     uses 'facetT *same;'
119     stops when it returns to newfacet
120 */
121 #define FORALLsame_(newfacet) for (same= newfacet->f.samecycle; same != newfacet; same= same->f.samecycle)
122
123 /*-<a                             href="qh-poly.htm#TOC"
124   >--------------------------------</a><a name="FORALLsame_cycle_">-</a>
125   
126   FORALLsame_cycle_( newfacet ) { ... } 
127     assign 'same' to each facet in newfacet->f.samecycle
128     
129   notes:
130     uses 'facetT *same;'
131     at exit, same == NULL
132 */
133 #define FORALLsame_cycle_(newfacet) \
134      for (same= newfacet->f.samecycle; \
135          same; same= (same == newfacet ?  NULL : same->f.samecycle))
136
137 /*-<a                             href="qh-poly.htm#TOC"
138   >--------------------------------</a><a name="FOREACHneighborA_">-</a>
139   
140   FOREACHneighborA_( facet ) { ... }
141     assign 'neighborA' to each neighbor in facet->neighbors
142   
143   FOREACHneighborA_( vertex ) { ... }
144     assign 'neighborA' to each neighbor in vertex->neighbors
145   
146   declare:
147     facetT *neighborA, **neighborAp;
148
149   see:
150     <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
151 */
152 #define FOREACHneighborA_(facet)  FOREACHsetelement_(facetT, facet->neighbors, neighborA)
153
154 /*-<a                             href="qh-poly.htm#TOC"
155   >--------------------------------</a><a name="FOREACHvisible_">-</a>
156   
157   FOREACHvisible_( facets ) { ... } 
158     assign 'visible' to each facet in facets
159     
160   notes:
161     uses 'facetT *facet, *facetp;'
162     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
163 */
164 #define FOREACHvisible_(facets) FOREACHsetelement_(facetT, facets, visible)
165
166 /*-<a                             href="qh-poly.htm#TOC"
167   >--------------------------------</a><a name="FOREACHnewfacet_">-</a>
168   
169   FOREACHnewfacet_( facets ) { ... } 
170     assign 'newfacet' to each facet in facets
171     
172   notes:
173     uses 'facetT *newfacet, *newfacetp;'
174     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
175 */
176 #define FOREACHnewfacet_(facets) FOREACHsetelement_(facetT, facets, newfacet)
177
178 /*-<a                             href="qh-poly.htm#TOC"
179   >--------------------------------</a><a name="FOREACHvertexA_">-</a>
180   
181   FOREACHvertexA_( vertices ) { ... } 
182     assign 'vertexA' to each vertex in vertices
183     
184   notes:
185     uses 'vertexT *vertexA, *vertexAp;'
186     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
187 */
188 #define FOREACHvertexA_(vertices) FOREACHsetelement_(vertexT, vertices, vertexA)
189
190 /*-<a                             href="qh-poly.htm#TOC"
191   >--------------------------------</a><a name="FOREACHvertexreverse12_">-</a>
192   
193   FOREACHvertexreverse12_( vertices ) { ... } 
194     assign 'vertex' to each vertex in vertices
195     reverse order of first two vertices
196     
197   notes:
198     uses 'vertexT *vertex, *vertexp;'
199     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
200 */
201 #define FOREACHvertexreverse12_(vertices) FOREACHsetelementreverse12_(vertexT, vertices, vertex)
202
203
204 /*=============== prototypes poly.c in alphabetical order ================*/
205
206 void    qh_appendfacet(facetT *facet);
207 void    qh_appendvertex(vertexT *vertex);
208 void    qh_attachnewfacets (void);
209 boolT   qh_checkflipped (facetT *facet, realT *dist, boolT allerror);
210 void    qh_delfacet(facetT *facet);
211 void    qh_deletevisible(void /*qh visible_list, qh horizon_list*/);
212 setT   *qh_facetintersect (facetT *facetA, facetT *facetB, int *skipAp,int *skipBp, int extra);
213 unsigned qh_gethash (int hashsize, setT *set, int size, int firstindex, void *skipelem);
214 facetT *qh_makenewfacet(setT *vertices, boolT toporient, facetT *facet);
215 void    qh_makenewplanes ( void /* newfacet_list */);
216 facetT *qh_makenew_nonsimplicial (facetT *visible, vertexT *apex, int *numnew);
217 facetT *qh_makenew_simplicial (facetT *visible, vertexT *apex, int *numnew);
218 void    qh_matchneighbor (facetT *newfacet, int newskip, int hashsize,
219                           int *hashcount);
220 void    qh_matchnewfacets (void);
221 boolT   qh_matchvertices (int firstindex, setT *verticesA, int skipA, 
222                           setT *verticesB, int *skipB, boolT *same);
223 facetT *qh_newfacet(void);
224 ridgeT *qh_newridge(void);
225 int     qh_pointid (pointT *point);
226 void    qh_removefacet(facetT *facet);
227 void    qh_removevertex(vertexT *vertex);
228 void    qh_updatevertices (void);
229
230
231 /*========== -prototypes poly2.c in alphabetical order ===========*/
232
233 void    qh_addhash (void* newelem, setT *hashtable, int hashsize, unsigned hash);
234 void    qh_check_bestdist (void);
235 void    qh_check_maxout (void);
236 void    qh_check_output (void);
237 void    qh_check_point (pointT *point, facetT *facet, realT *maxoutside, realT *maxdist, facetT **errfacet1, facetT **errfacet2);
238 void    qh_check_points(void);
239 void    qh_checkconvex(facetT *facetlist, int fault);
240 void    qh_checkfacet(facetT *facet, boolT newmerge, boolT *waserrorp);
241 void    qh_checkflipped_all (facetT *facetlist);
242 void    qh_checkpolygon(facetT *facetlist);
243 void    qh_checkvertex (vertexT *vertex);
244 void    qh_clearcenters (qh_CENTER type);
245 void    qh_createsimplex(setT *vertices);
246 void    qh_delridge(ridgeT *ridge);
247 void    qh_delvertex (vertexT *vertex);
248 setT   *qh_facet3vertex (facetT *facet);
249 facetT *qh_findbestfacet (pointT *point, boolT bestoutside,
250            realT *bestdist, boolT *isoutside);
251 facetT *qh_findfacet_all (pointT *point, realT *bestdist, boolT *isoutside,
252                           int *numpart);
253 int     qh_findgood (facetT *facetlist, int goodhorizon);
254 void    qh_findgood_all (facetT *facetlist);
255 void    qh_furthestnext (void /* qh facet_list */);
256 void    qh_furthestout (facetT *facet);
257 void    qh_infiniteloop (facetT *facet);
258 void    qh_initbuild(void);
259 void    qh_initialhull(setT *vertices);
260 setT   *qh_initialvertices(int dim, setT *maxpoints, pointT *points, int numpoints);
261 vertexT *qh_isvertex (pointT *point, setT *vertices);
262 vertexT *qh_makenewfacets (pointT *point /*horizon_list, visible_list*/);
263 void    qh_matchduplicates (facetT *atfacet, int atskip, int hashsize, int *hashcount);
264 void    qh_nearcoplanar ( void /* qh.facet_list */);
265 vertexT *qh_nearvertex (facetT *facet, pointT *point, realT *bestdistp);
266 int     qh_newhashtable(int newsize);
267 vertexT *qh_newvertex(pointT *point);
268 ridgeT *qh_nextridge3d (ridgeT *atridge, facetT *facet, vertexT **vertexp);
269 void    qh_outcoplanar (void /* facet_list */);
270 pointT *qh_point (int id);
271 void    qh_point_add (setT *set, pointT *point, void *elem);
272 setT   *qh_pointfacet (void /*qh facet_list*/);
273 setT   *qh_pointvertex (void /*qh facet_list*/);
274 void    qh_prependfacet(facetT *facet, facetT **facetlist);
275 void    qh_printhashtable(FILE *fp);
276 void    qh_printlists (void);
277 void    qh_resetlists (boolT stats, boolT resetVisible /*qh newvertex_list newfacet_list visible_list*/);
278 void    qh_setvoronoi_all (void);
279 void    qh_triangulate (void /*qh facet_list*/);
280 void    qh_triangulate_facet (facetT *facetA, vertexT **first_vertex);
281 void    qh_triangulate_link (facetT *oldfacetA, facetT *facetA, facetT *oldfacetB, facetT *facetB);
282 void    qh_triangulate_mirror (facetT *facetA, facetT *facetB);
283 void    qh_triangulate_null (facetT *facetA);
284 void    qh_vertexintersect(setT **vertexsetA,setT *vertexsetB);
285 setT   *qh_vertexintersect_new(setT *vertexsetA,setT *vertexsetB);
286 void    qh_vertexneighbors (void /*qh facet_list*/);
287 boolT   qh_vertexsubset(setT *vertexsetA, setT *vertexsetB);
288
289
290 #endif /* qhDEFpoly */