File: | chull.c |
Warning: | line 749, column 9 Access to field 'next' results in a dereference of a null pointer (loaded from variable 'vertices') |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* | |||
2 | This code is described in "Computational Geometry in C" (Second Edition), | |||
3 | Chapter 4. It is not written to be comprehensible without the | |||
4 | explanation in that book. | |||
5 | ||||
6 | Input: 3n integer coordinates for the points. | |||
7 | Output: the 3D convex hull, in postscript with embedded comments | |||
8 | showing the vertices and faces. | |||
9 | ||||
10 | Compile: gcc -o chull chull.c | |||
11 | ||||
12 | Written by Joseph O'Rourke, with contributions by | |||
13 | Kristy Anderson, John Kutcher, Catherine Schevon, Susan Weller. | |||
14 | Last modified: March 1998 | |||
15 | Questions to orourke@cs.smith.edu. | |||
16 | -------------------------------------------------------------------- | |||
17 | This code is Copyright 1998 by Joseph O'Rourke. It may be freely | |||
18 | redistributed in its entirety provided that this copyright notice is | |||
19 | not removed. | |||
20 | -------------------------------------------------------------------- | |||
21 | */ | |||
22 | #include <stdio.h> | |||
23 | #include <stdlib.h> | |||
24 | #include <math.h> | |||
25 | ||||
26 | #include <grass/gis.h> | |||
27 | #include <grass/vector.h> | |||
28 | #include <grass/glocale.h> | |||
29 | ||||
30 | #include "globals.h" | |||
31 | ||||
32 | /* Define vertex indices. */ | |||
33 | #define X0 0 | |||
34 | #define Y1 1 | |||
35 | #define Z2 2 | |||
36 | ||||
37 | /* Define structures for vertices, edges and faces */ | |||
38 | typedef struct tVertexStructure tsVertex; | |||
39 | typedef tsVertex *tVertex; | |||
40 | ||||
41 | typedef struct tEdgeStructure tsEdge; | |||
42 | typedef tsEdge *tEdge; | |||
43 | ||||
44 | typedef struct tFaceStructure tsFace; | |||
45 | typedef tsFace *tFace; | |||
46 | ||||
47 | struct tVertexStructure { | |||
48 | double v[3]; | |||
49 | int vnum; | |||
50 | tEdge duplicate; /* pointer to incident cone edge (or NULL) */ | |||
51 | bool_Bool onhull; /* T iff point on hull. */ | |||
52 | bool_Bool mark; /* T iff point already processed. */ | |||
53 | tVertex next, prev; | |||
54 | }; | |||
55 | ||||
56 | struct tEdgeStructure { | |||
57 | tFace adjface[2]; | |||
58 | tVertex endpts[2]; | |||
59 | tFace newface; /* pointer to incident cone face. */ | |||
60 | bool_Bool delete; /* T iff edge should be delete. */ | |||
61 | tEdge next, prev; | |||
62 | }; | |||
63 | ||||
64 | struct tFaceStructure { | |||
65 | tEdge edge[3]; | |||
66 | tVertex vertex[3]; | |||
67 | bool_Bool visible; /* T iff face visible from new point. */ | |||
68 | tFace next, prev; | |||
69 | }; | |||
70 | ||||
71 | /* Define flags */ | |||
72 | #define ONHULL1 true1 | |||
73 | #define REMOVED1 true1 | |||
74 | #define VISIBLE1 true1 | |||
75 | #define PROCESSED1 true1 | |||
76 | ||||
77 | /* Global variable definitions */ | |||
78 | tVertex vertices = NULL((void*)0); | |||
79 | tEdge edges = NULL((void*)0); | |||
80 | tFace faces = NULL((void*)0); | |||
81 | ||||
82 | /* Function declarations */ | |||
83 | tVertex MakeNullVertex(void); | |||
84 | void ReadVertices(double *px, double *py, double *pz, int num_points); | |||
85 | void writeVertices(struct Map_info *Map); | |||
86 | int DoubleTriangle(void); | |||
87 | void ConstructHull(void); | |||
88 | bool_Bool AddOne(tVertex p); | |||
89 | int VolumeSign(tFace f, tVertex p); | |||
90 | tFace MakeConeFace(tEdge e, tVertex p); | |||
91 | void MakeCcw(tFace f, tEdge e, tVertex p); | |||
92 | tEdge MakeNullEdge(void); | |||
93 | tFace MakeNullFace(void); | |||
94 | tFace MakeFace(tVertex v0, tVertex v1, tVertex v2, tFace f); | |||
95 | void CleanUp(void); | |||
96 | void CleanEdges(void); | |||
97 | void CleanFaces(void); | |||
98 | void CleanVertices(void); | |||
99 | bool_Bool Collinear(tVertex a, tVertex b, tVertex c); | |||
100 | ||||
101 | #include "macros.h" | |||
102 | ||||
103 | /* | |||
104 | ||||
105 | Release all memory allocated for edges, faces and vertices | |||
106 | ||||
107 | */ | |||
108 | void freeMem(void) | |||
109 | { | |||
110 | tEdge e; /* Primary index into edge list. */ | |||
111 | tFace f; /* Primary pointer into face list. */ | |||
112 | tVertex v; | |||
113 | tEdge te; /* Temporary edge pointer. */ | |||
114 | tFace tf; /* Temporary face pointer. */ | |||
115 | tVertex tv; /* Temporary vertex pointer. */ | |||
116 | ||||
117 | e = edges; | |||
118 | do { | |||
119 | te = e; | |||
120 | e = e->next; | |||
121 | DELETE(edges, te)if (edges) { if (edges == edges->next) edges = ((void*)0); else if (te == edges) edges = edges->next; te->next-> prev = te->prev; te->prev->next = te->next; if (te ) { free((char *)te); te = ((void*)0); }; }; | |||
122 | } while (e != edges); | |||
123 | ||||
124 | f = faces; | |||
125 | do { | |||
126 | tf = f; | |||
127 | f = f->next; | |||
128 | DELETE(faces, tf)if (faces) { if (faces == faces->next) faces = ((void*)0); else if (tf == faces) faces = faces->next; tf->next-> prev = tf->prev; tf->prev->next = tf->next; if (tf ) { free((char *)tf); tf = ((void*)0); }; }; | |||
129 | } while (f != faces); | |||
130 | ||||
131 | v = vertices; | |||
132 | do { | |||
133 | tv = v; | |||
134 | v = v->next; | |||
135 | DELETE(vertices, tv)if (vertices) { if (vertices == vertices->next) vertices = ((void*)0); else if (tv == vertices) vertices = vertices-> next; tv->next->prev = tv->prev; tv->prev->next = tv->next; if (tv) { free((char *)tv); tv = ((void*)0); } ; }; | |||
136 | } while (v != vertices); | |||
137 | ||||
138 | FREE(te)if (te) { free((char *)te); te = ((void*)0); }; | |||
139 | FREE(tf)if (tf) { free((char *)tf); tf = ((void*)0); }; | |||
140 | FREE(tv)if (tv) { free((char *)tv); tv = ((void*)0); }; | |||
141 | ||||
142 | DELETE(edges, e)if (edges) { if (edges == edges->next) edges = ((void*)0); else if (e == edges) edges = edges->next; e->next-> prev = e->prev; e->prev->next = e->next; if (e) { free((char *)e); e = ((void*)0); }; }; | |||
143 | DELETE(faces, f)if (faces) { if (faces == faces->next) faces = ((void*)0); else if (f == faces) faces = faces->next; f->next-> prev = f->prev; f->prev->next = f->next; if (f) { free((char *)f); f = ((void*)0); }; }; | |||
144 | DELETE(vertices, v)if (vertices) { if (vertices == vertices->next) vertices = ((void*)0); else if (v == vertices) vertices = vertices-> next; v->next->prev = v->prev; v->prev->next = v->next; if (v) { free((char *)v); v = ((void*)0); }; }; | |||
145 | ||||
146 | FREE(edges)if (edges) { free((char *)edges); edges = ((void*)0); }; | |||
147 | FREE(faces)if (faces) { free((char *)faces); faces = ((void*)0); }; | |||
148 | FREE(vertices)if (vertices) { free((char *)vertices); vertices = ((void*)0) ; }; | |||
149 | } | |||
150 | ||||
151 | /*-------------------------------------------------------------------*/ | |||
152 | int make3DHull(double *px, double *py, double *pz, int num_points, | |||
153 | struct Map_info *Map) | |||
154 | { | |||
155 | int error; | |||
156 | ||||
157 | ReadVertices(px, py, pz, num_points); | |||
158 | ||||
159 | error = DoubleTriangle(); | |||
160 | if (error
| |||
| ||||
161 | G_fatal_error("All points of 3D input map are in the same plane.\n " | |||
162 | "Cannot create a 3D hull."); | |||
163 | } | |||
164 | ||||
165 | ConstructHull(); | |||
166 | ||||
167 | writeVertices(Map); | |||
168 | ||||
169 | freeMem(); | |||
170 | ||||
171 | return (0); | |||
172 | } | |||
173 | ||||
174 | /*--------------------------------------------------------------------- | |||
175 | MakeNullVertex: Makes a vertex, nulls out fields. | |||
176 | ---------------------------------------------------------------------*/ | |||
177 | tVertex MakeNullVertex(void) | |||
178 | { | |||
179 | tVertex v; | |||
180 | ||||
181 | NEW(v, tsVertex)if ((v = (tsVertex *)malloc(sizeof(tsVertex))) == ((void*)0)) { printf("Out of Memory!\n"); exit(0); }; | |||
182 | v->duplicate = NULL((void*)0); | |||
183 | v->onhull = !ONHULL1; | |||
184 | v->mark = !PROCESSED1; | |||
185 | ADD(vertices, v)if (vertices) { v->next = vertices; v->prev = vertices-> prev; vertices->prev = v; v->prev->next = v; } else { vertices = v; vertices->next = vertices->prev = v; }; | |||
186 | ||||
187 | return v; | |||
188 | } | |||
189 | ||||
190 | /*--------------------------------------------------------------------- | |||
191 | ReadVertices: Reads in the vertices, and links them into a circular | |||
192 | list with MakeNullVertex. There is no need for the # of vertices to be | |||
193 | the first line: the function looks for EOF instead. Sets the global | |||
194 | variable vertices via the ADD macro. | |||
195 | ---------------------------------------------------------------------*/ | |||
196 | void ReadVertices(double *px, double *py, double *pz, int num_points) | |||
197 | { | |||
198 | tVertex v; | |||
199 | int vnum = 0; | |||
200 | int i; | |||
201 | ||||
202 | G_important_message(_("Reading 3D vertices...")G_gettext("grassmods", ("Reading 3D vertices..."))); | |||
203 | for (i = 0; i < num_points; i++) { | |||
204 | v = MakeNullVertex(); | |||
205 | v->v[X0] = px[i]; | |||
206 | v->v[Y1] = py[i]; | |||
207 | v->v[Z2] = pz[i]; | |||
208 | v->vnum = vnum++; | |||
209 | G_percent(i, (num_points - 1), 1); | |||
210 | } | |||
211 | fflush(stdout__stdoutp); | |||
212 | } | |||
213 | ||||
214 | /*--------------------------------------------------------------------- | |||
215 | Outputs the 3D triangles to a GRASS 3d vector map. | |||
216 | ---------------------------------------------------------------------*/ | |||
217 | void writeVertices(struct Map_info *Map) | |||
218 | { | |||
219 | /* Pointers to vertices, edges, faces. */ | |||
220 | tFace f; | |||
221 | double *px, *py, *pz; | |||
222 | double fx, fy, fz; | |||
223 | double kx, ky, kz; | |||
224 | ||||
225 | long int cat, num_faces; | |||
226 | ||||
227 | struct line_pnts *Points; | |||
228 | struct line_cats *Cats; | |||
229 | ||||
230 | Points = Vect_new_line_struct(); | |||
231 | Cats = Vect_new_cats_struct(); | |||
232 | ||||
233 | px = G_malloc(sizeof(double) * 4)G__malloc("vector/v.hull" "/" "chull.c", 233, (sizeof(double) * 4)); | |||
234 | py = G_malloc(sizeof(double) * 4)G__malloc("vector/v.hull" "/" "chull.c", 234, (sizeof(double) * 4)); | |||
235 | pz = G_malloc(sizeof(double) * 4)G__malloc("vector/v.hull" "/" "chull.c", 235, (sizeof(double) * 4)); | |||
236 | ||||
237 | f = faces; | |||
238 | num_faces = 0; | |||
239 | cat = 0; | |||
240 | kx = 0.0; | |||
241 | ky = 0.0; | |||
242 | kz = 0.0; | |||
243 | ||||
244 | G_message("Writing faces and kernel to output map ..."); | |||
245 | ||||
246 | do { | |||
247 | ||||
248 | num_faces++; | |||
249 | ||||
250 | /* write one triangular face */ | |||
251 | px[0] = ((double)(f->vertex[0]->v[X0])); | |||
252 | py[0] = ((double)(f->vertex[0]->v[Y1])); | |||
253 | pz[0] = ((double)(f->vertex[0]->v[Z2])); | |||
254 | ||||
255 | px[1] = ((double)(f->vertex[1]->v[X0])); | |||
256 | py[1] = ((double)(f->vertex[1]->v[Y1])); | |||
257 | pz[1] = ((double)(f->vertex[1]->v[Z2])); | |||
258 | ||||
259 | px[2] = ((double)(f->vertex[2]->v[X0])); | |||
260 | py[2] = ((double)(f->vertex[2]->v[Y1])); | |||
261 | pz[2] = ((double)(f->vertex[2]->v[Z2])); | |||
262 | ||||
263 | px[3] = ((double)(f->vertex[0]->v[X0])); | |||
264 | py[3] = ((double)(f->vertex[0]->v[Y1])); | |||
265 | pz[3] = ((double)(f->vertex[0]->v[Z2])); | |||
266 | ||||
267 | /* kernel position: 1st get 3D center of this face */ | |||
268 | fx = (px[0] + px[1] + px[2]) / 3.0; | |||
269 | fy = (py[0] + py[1] + py[2]) / 3.0; | |||
270 | fz = (pz[0] + pz[1] + pz[2]) / 3.0; | |||
271 | ||||
272 | /* kernel position: now add this to kernel coordinates */ | |||
273 | kx = kx + fx; | |||
274 | ky = ky + fy; | |||
275 | kz = kz + fz; | |||
276 | ||||
277 | /* write out face */ | |||
278 | Vect_copy_xyz_to_pnts(Points, px, py, pz, 4); | |||
279 | cat++; | |||
280 | Vect_cat_set(Cats, 1, cat); | |||
281 | Vect_write_line(Map, GV_FACE0x10, Points, Cats); | |||
282 | ||||
283 | f = f->next; | |||
284 | ||||
285 | } while (f != faces); | |||
286 | ||||
287 | /* write kernel for the center of the whole hull */ | |||
288 | kx = kx / num_faces; | |||
289 | ky = ky / num_faces; | |||
290 | kz = kz / num_faces; | |||
291 | Vect_cat_set(Cats, 1, cat + 1); | |||
292 | Vect_copy_xyz_to_pnts(Points, &kx, &ky, &kz, 1); | |||
293 | Vect_write_line(Map, GV_KERNEL0x20, Points, Cats); | |||
294 | ||||
295 | Vect_destroy_line_struct(Points); | |||
296 | ||||
297 | fflush(stdout__stdoutp); | |||
298 | ||||
299 | G_free(px); | |||
300 | G_free(py); | |||
301 | G_free(pz); | |||
302 | } | |||
303 | ||||
304 | /*--------------------------------------------------------------------- | |||
305 | DoubleTriangle builds the initial double triangle. It first finds 3 | |||
306 | noncollinear points and makes two faces out of them, in opposite order. | |||
307 | It then finds a fourth point that is not coplanar with that face. The | |||
308 | vertices are stored in the face structure in counterclockwise order so | |||
309 | that the volume between the face and the point is negative. Lastly, the | |||
310 | 3 newfaces to the fourth point are constructed and the data structures | |||
311 | are cleaned up. | |||
312 | ---------------------------------------------------------------------*/ | |||
313 | ||||
314 | /* RETURN: 0 if OK */ | |||
315 | /* -1 if all points collinear */ | |||
316 | /* -2 if all points coplanar */ | |||
317 | ||||
318 | int DoubleTriangle(void) | |||
319 | { | |||
320 | tVertex v0, v1, v2, v3; | |||
321 | tFace f0, f1 = NULL((void*)0); | |||
322 | long int vol; | |||
323 | ||||
324 | /* Find 3 noncollinear points. */ | |||
325 | v0 = vertices; | |||
326 | while (Collinear(v0, v0->next, v0->next->next)) { | |||
327 | if ((v0 = v0->next) == vertices) { | |||
328 | G_warning("DoubleTriangle: All points are collinear!\n"); | |||
329 | return (-1); | |||
330 | } | |||
331 | } | |||
332 | v1 = v0->next; | |||
333 | v2 = v1->next; | |||
334 | ||||
335 | /* Mark the vertices as processed. */ | |||
336 | v0->mark = PROCESSED1; | |||
337 | v1->mark = PROCESSED1; | |||
338 | v2->mark = PROCESSED1; | |||
339 | ||||
340 | /* Create the two "twin" faces. */ | |||
341 | f0 = MakeFace(v0, v1, v2, f1); | |||
342 | f1 = MakeFace(v2, v1, v0, f0); | |||
343 | ||||
344 | /* Link adjacent face fields. */ | |||
345 | f0->edge[0]->adjface[1] = f1; | |||
346 | f0->edge[1]->adjface[1] = f1; | |||
347 | f0->edge[2]->adjface[1] = f1; | |||
348 | f1->edge[0]->adjface[1] = f0; | |||
349 | f1->edge[1]->adjface[1] = f0; | |||
350 | f1->edge[2]->adjface[1] = f0; | |||
351 | ||||
352 | /* Find a fourth, noncoplanar point to form tetrahedron. */ | |||
353 | v3 = v2->next; | |||
354 | vol = VolumeSign(f0, v3); | |||
355 | while (!vol) { | |||
356 | if ((v3 = v3->next) == v0) { | |||
357 | G_warning("DoubleTriangle: All points are coplanar!\n"); | |||
358 | return (-2); | |||
359 | } | |||
360 | vol = VolumeSign(f0, v3); | |||
361 | } | |||
362 | ||||
363 | /* Insure that v3 will be the first added. */ | |||
364 | vertices = v3; | |||
365 | ||||
366 | return (0); | |||
367 | } | |||
368 | ||||
369 | /*--------------------------------------------------------------------- | |||
370 | ConstructHull adds the vertices to the hull one at a time. The hull | |||
371 | vertices are those in the list marked as onhull. | |||
372 | ---------------------------------------------------------------------*/ | |||
373 | void ConstructHull(void) | |||
374 | { | |||
375 | tVertex v, vnext; | |||
376 | ||||
377 | /* bool changed; */ /* T if addition changes hull; not used. */ | |||
378 | int i; | |||
379 | int numVertices; | |||
380 | ||||
381 | G_important_message(_("Constructing 3D hull...")G_gettext("grassmods", ("Constructing 3D hull..."))); | |||
382 | ||||
383 | v = vertices; | |||
384 | i = 0; | |||
385 | do { | |||
386 | vnext = v->next; | |||
387 | v = vnext; | |||
388 | i++; | |||
389 | } while (v != vertices); | |||
390 | numVertices = i; | |||
391 | ||||
392 | v = vertices; | |||
393 | i = 0; | |||
394 | do { | |||
395 | vnext = v->next; | |||
396 | if (!v->mark) { | |||
397 | v->mark = PROCESSED1; | |||
398 | /* changed = */ AddOne(v); | |||
399 | CleanUp(); | |||
400 | } | |||
401 | v = vnext; | |||
402 | i++; | |||
403 | ||||
404 | G_percent(i, numVertices, 1); | |||
405 | ||||
406 | } while (v != vertices); | |||
407 | ||||
408 | fflush(stdout__stdoutp); | |||
409 | } | |||
410 | ||||
411 | /*--------------------------------------------------------------------- | |||
412 | AddOne is passed a vertex. It first determines all faces visible from | |||
413 | that point. If none are visible then the point is marked as not | |||
414 | onhull. Next is a loop over edges. If both faces adjacent to an edge | |||
415 | are visible, then the edge is marked for deletion. If just one of the | |||
416 | adjacent faces is visible then a new face is constructed. | |||
417 | ---------------------------------------------------------------------*/ | |||
418 | bool_Bool AddOne(tVertex p) | |||
419 | { | |||
420 | tFace f; | |||
421 | tEdge e, temp; | |||
422 | long int vol; | |||
423 | bool_Bool vis = false0; | |||
424 | ||||
425 | /* Mark faces visible from p. */ | |||
426 | f = faces; | |||
427 | do { | |||
428 | vol = VolumeSign(f, p); | |||
429 | ||||
430 | if (vol < 0) { | |||
431 | f->visible = VISIBLE1; | |||
432 | vis = true1; | |||
433 | } | |||
434 | f = f->next; | |||
435 | } while (f != faces); | |||
436 | ||||
437 | /* If no faces are visible from p, then p is inside the hull. */ | |||
438 | if (!vis) { | |||
439 | p->onhull = !ONHULL1; | |||
440 | return false0; | |||
441 | } | |||
442 | ||||
443 | /* Mark edges in interior of visible region for deletion. | |||
444 | Erect a newface based on each border edge. */ | |||
445 | e = edges; | |||
446 | do { | |||
447 | temp = e->next; | |||
448 | if (e->adjface[0]->visible && e->adjface[1]->visible) | |||
449 | /* e interior: mark for deletion. */ | |||
450 | e->delete = REMOVED1; | |||
451 | else if (e->adjface[0]->visible || e->adjface[1]->visible) | |||
452 | /* e border: make a new face. */ | |||
453 | e->newface = MakeConeFace(e, p); | |||
454 | e = temp; | |||
455 | } while (e != edges); | |||
456 | return true1; | |||
457 | } | |||
458 | ||||
459 | /*--------------------------------------------------------------------- | |||
460 | VolumeSign returns the sign of the volume of the tetrahedron determined by f | |||
461 | and p. VolumeSign is +1 iff p is on the negative side of f, | |||
462 | where the positive side is determined by the rh-rule. So the volume | |||
463 | is positive if the ccw normal to f points outside the tetrahedron. | |||
464 | The final fewer-multiplications form is due to Bob Williamson. | |||
465 | ---------------------------------------------------------------------*/ | |||
466 | int VolumeSign(tFace f, tVertex p) | |||
467 | { | |||
468 | double vol; | |||
469 | double ax, ay, az, bx, by, bz, cx, cy, cz; | |||
470 | ||||
471 | ax = f->vertex[0]->v[X0] - p->v[X0]; | |||
472 | ay = f->vertex[0]->v[Y1] - p->v[Y1]; | |||
473 | az = f->vertex[0]->v[Z2] - p->v[Z2]; | |||
474 | bx = f->vertex[1]->v[X0] - p->v[X0]; | |||
475 | by = f->vertex[1]->v[Y1] - p->v[Y1]; | |||
476 | bz = f->vertex[1]->v[Z2] - p->v[Z2]; | |||
477 | cx = f->vertex[2]->v[X0] - p->v[X0]; | |||
478 | cy = f->vertex[2]->v[Y1] - p->v[Y1]; | |||
479 | cz = f->vertex[2]->v[Z2] - p->v[Z2]; | |||
480 | ||||
481 | vol = ax * (by * cz - bz * cy) + ay * (bz * cx - bx * cz) + | |||
482 | az * (bx * cy - by * cx); | |||
483 | ||||
484 | /* The volume should be an integer. */ | |||
485 | if (vol > 0.0) | |||
486 | return 1; | |||
487 | else if (vol < -0.0) | |||
488 | return -1; | |||
489 | else | |||
490 | return 0; | |||
491 | } | |||
492 | ||||
493 | /*--------------------------------------------------------------------- | |||
494 | MakeConeFace makes a new face and two new edges between the | |||
495 | edge and the point that are passed to it. It returns a pointer to | |||
496 | the new face. | |||
497 | ---------------------------------------------------------------------*/ | |||
498 | tFace MakeConeFace(tEdge e, tVertex p) | |||
499 | { | |||
500 | tEdge new_edge[2]; | |||
501 | tFace new_face; | |||
502 | int i, j; | |||
503 | ||||
504 | /* Make two new edges (if don't already exist). */ | |||
505 | for (i = 0; i < 2; ++i) | |||
506 | /* If the edge exists, copy it into new_edge. */ | |||
507 | if (!(new_edge[i] = e->endpts[i]->duplicate)) { | |||
508 | /* Otherwise (duplicate is NULL), MakeNullEdge. */ | |||
509 | new_edge[i] = MakeNullEdge(); | |||
510 | new_edge[i]->endpts[0] = e->endpts[i]; | |||
511 | new_edge[i]->endpts[1] = p; | |||
512 | e->endpts[i]->duplicate = new_edge[i]; | |||
513 | } | |||
514 | ||||
515 | /* Make the new face. */ | |||
516 | new_face = MakeNullFace(); | |||
517 | new_face->edge[0] = e; | |||
518 | new_face->edge[1] = new_edge[0]; | |||
519 | new_face->edge[2] = new_edge[1]; | |||
520 | MakeCcw(new_face, e, p); | |||
521 | ||||
522 | /* Set the adjacent face pointers. */ | |||
523 | for (i = 0; i < 2; ++i) | |||
524 | for (j = 0; j < 2; ++j) | |||
525 | /* Only one NULL link should be set to new_face. */ | |||
526 | if (!new_edge[i]->adjface[j]) { | |||
527 | new_edge[i]->adjface[j] = new_face; | |||
528 | break; | |||
529 | } | |||
530 | ||||
531 | return new_face; | |||
532 | } | |||
533 | ||||
534 | /*--------------------------------------------------------------------- | |||
535 | MakeCcw puts the vertices in the face structure in counterclock wise | |||
536 | order. We want to store the vertices in the same | |||
537 | order as in the visible face. The third vertex is always p. | |||
538 | ---------------------------------------------------------------------*/ | |||
539 | void MakeCcw(tFace f, tEdge e, tVertex p) | |||
540 | { | |||
541 | tFace fv; /* The visible face adjacent to e */ | |||
542 | int i; /* Index of e->endpoint[0] in fv. */ | |||
543 | tEdge s; /* Temporary, for swapping */ | |||
544 | ||||
545 | if (e->adjface[0]->visible) | |||
546 | fv = e->adjface[0]; | |||
547 | else | |||
548 | fv = e->adjface[1]; | |||
549 | ||||
550 | /* Set vertex[0] & [1] of f to have the same orientation | |||
551 | as do the corresponding vertices of fv. */ | |||
552 | for (i = 0; fv->vertex[i] != e->endpts[0]; ++i) | |||
553 | ; | |||
554 | /* Orient f the same as fv. */ | |||
555 | if (fv->vertex[(i + 1) % 3] != e->endpts[1]) { | |||
556 | f->vertex[0] = e->endpts[1]; | |||
557 | f->vertex[1] = e->endpts[0]; | |||
558 | } | |||
559 | else { | |||
560 | f->vertex[0] = e->endpts[0]; | |||
561 | f->vertex[1] = e->endpts[1]; | |||
562 | SWAP(s, f->edge[1], f->edge[2]){ s = f->edge[1]; f->edge[1] = f->edge[2]; f->edge [2] = s; }; | |||
563 | } | |||
564 | /* This swap is tricky. e is edge[0]. edge[1] is based on endpt[0], | |||
565 | edge[2] on endpt[1]. So if e is oriented "forwards," we | |||
566 | need to move edge[1] to follow [0], because it precedes. */ | |||
567 | ||||
568 | f->vertex[2] = p; | |||
569 | } | |||
570 | ||||
571 | /*--------------------------------------------------------------------- | |||
572 | MakeNullEdge creates a new cell and initializes all pointers to NULL | |||
573 | and sets all flags to off. It returns a pointer to the empty cell. | |||
574 | ---------------------------------------------------------------------*/ | |||
575 | tEdge MakeNullEdge(void) | |||
576 | { | |||
577 | tEdge e; | |||
578 | ||||
579 | NEW(e, tsEdge)if ((e = (tsEdge *)malloc(sizeof(tsEdge))) == ((void*)0)) { printf ("Out of Memory!\n"); exit(0); }; | |||
580 | e->adjface[0] = e->adjface[1] = e->newface = NULL((void*)0); | |||
581 | e->endpts[0] = e->endpts[1] = NULL((void*)0); | |||
582 | e->delete = !REMOVED1; | |||
583 | ADD(edges, e)if (edges) { e->next = edges; e->prev = edges->prev; edges->prev = e; e->prev->next = e; } else { edges = e; edges->next = edges->prev = e; }; | |||
584 | return e; | |||
585 | } | |||
586 | ||||
587 | /*-------------------------------------------------------------------- | |||
588 | MakeNullFace creates a new face structure and initializes all of its | |||
589 | flags to NULL and sets all the flags to off. It returns a pointer | |||
590 | to the empty cell. | |||
591 | ---------------------------------------------------------------------*/ | |||
592 | tFace MakeNullFace(void) | |||
593 | { | |||
594 | tFace f; | |||
595 | int i; | |||
596 | ||||
597 | NEW(f, tsFace)if ((f = (tsFace *)malloc(sizeof(tsFace))) == ((void*)0)) { printf ("Out of Memory!\n"); exit(0); }; | |||
598 | for (i = 0; i < 3; ++i) { | |||
599 | f->edge[i] = NULL((void*)0); | |||
600 | f->vertex[i] = NULL((void*)0); | |||
601 | } | |||
602 | f->visible = !VISIBLE1; | |||
603 | ADD(faces, f)if (faces) { f->next = faces; f->prev = faces->prev; faces->prev = f; f->prev->next = f; } else { faces = f; faces->next = faces->prev = f; }; | |||
604 | return f; | |||
605 | } | |||
606 | ||||
607 | /*--------------------------------------------------------------------- | |||
608 | MakeFace creates a new face structure from three vertices (in ccw | |||
609 | order). It returns a pointer to the face. | |||
610 | ---------------------------------------------------------------------*/ | |||
611 | tFace MakeFace(tVertex v0, tVertex v1, tVertex v2, tFace fold) | |||
612 | { | |||
613 | tFace f; | |||
614 | tEdge e0, e1, e2; | |||
615 | ||||
616 | /* Create edges of the initial triangle. */ | |||
617 | if (!fold) { | |||
618 | e0 = MakeNullEdge(); | |||
619 | e1 = MakeNullEdge(); | |||
620 | e2 = MakeNullEdge(); | |||
621 | } | |||
622 | else { /* Copy from fold, in reverse order. */ | |||
623 | e0 = fold->edge[2]; | |||
624 | e1 = fold->edge[1]; | |||
625 | e2 = fold->edge[0]; | |||
626 | } | |||
627 | e0->endpts[0] = v0; | |||
628 | e0->endpts[1] = v1; | |||
629 | e1->endpts[0] = v1; | |||
630 | e1->endpts[1] = v2; | |||
631 | e2->endpts[0] = v2; | |||
632 | e2->endpts[1] = v0; | |||
633 | ||||
634 | /* Create face for triangle. */ | |||
635 | f = MakeNullFace(); | |||
636 | f->edge[0] = e0; | |||
637 | f->edge[1] = e1; | |||
638 | f->edge[2] = e2; | |||
639 | f->vertex[0] = v0; | |||
640 | f->vertex[1] = v1; | |||
641 | f->vertex[2] = v2; | |||
642 | ||||
643 | /* Link edges to face. */ | |||
644 | e0->adjface[0] = e1->adjface[0] = e2->adjface[0] = f; | |||
645 | ||||
646 | return f; | |||
647 | } | |||
648 | ||||
649 | /*--------------------------------------------------------------------- | |||
650 | CleanUp goes through each data structure list and clears all | |||
651 | flags and NULLs out some pointers. The order of processing | |||
652 | (edges, faces, vertices) is important. | |||
653 | ---------------------------------------------------------------------*/ | |||
654 | void CleanUp(void) | |||
655 | { | |||
656 | CleanEdges(); | |||
657 | CleanFaces(); | |||
658 | CleanVertices(); | |||
659 | } | |||
660 | ||||
661 | /*--------------------------------------------------------------------- | |||
662 | CleanEdges runs through the edge list and cleans up the structure. | |||
663 | If there is a newface then it will put that face in place of the | |||
664 | visible face and NULL out newface. It also deletes so marked edges. | |||
665 | ---------------------------------------------------------------------*/ | |||
666 | void CleanEdges(void) | |||
667 | { | |||
668 | tEdge e; /* Primary index into edge list. */ | |||
669 | tEdge t; /* Temporary edge pointer. */ | |||
670 | ||||
671 | /* Integrate the newface's into the data structure. */ | |||
672 | /* Check every edge. */ | |||
673 | e = edges; | |||
674 | do { | |||
675 | if (e->newface) { | |||
676 | if (e->adjface[0]->visible) | |||
677 | e->adjface[0] = e->newface; | |||
678 | else | |||
679 | e->adjface[1] = e->newface; | |||
680 | e->newface = NULL((void*)0); | |||
681 | } | |||
682 | e = e->next; | |||
683 | } while (e != edges); | |||
684 | ||||
685 | /* Delete any edges marked for deletion. */ | |||
686 | while (edges && edges->delete) { | |||
687 | e = edges; | |||
688 | DELETE(edges, e)if (edges) { if (edges == edges->next) edges = ((void*)0); else if (e == edges) edges = edges->next; e->next-> prev = e->prev; e->prev->next = e->next; if (e) { free((char *)e); e = ((void*)0); }; }; | |||
689 | } | |||
690 | e = edges->next; | |||
691 | do { | |||
692 | if (e->delete) { | |||
693 | t = e; | |||
694 | e = e->next; | |||
695 | DELETE(edges, t)if (edges) { if (edges == edges->next) edges = ((void*)0); else if (t == edges) edges = edges->next; t->next-> prev = t->prev; t->prev->next = t->next; if (t) { free((char *)t); t = ((void*)0); }; }; | |||
696 | } | |||
697 | else | |||
698 | e = e->next; | |||
699 | } while (e != edges); | |||
700 | } | |||
701 | ||||
702 | /*--------------------------------------------------------------------- | |||
703 | CleanFaces runs through the face list and deletes any face marked visible. | |||
704 | ---------------------------------------------------------------------*/ | |||
705 | void CleanFaces(void) | |||
706 | { | |||
707 | tFace f; /* Primary pointer into face list. */ | |||
708 | tFace t; /* Temporary pointer, for deleting. */ | |||
709 | ||||
710 | while (faces && faces->visible) { | |||
711 | f = faces; | |||
712 | DELETE(faces, f)if (faces) { if (faces == faces->next) faces = ((void*)0); else if (f == faces) faces = faces->next; f->next-> prev = f->prev; f->prev->next = f->next; if (f) { free((char *)f); f = ((void*)0); }; }; | |||
713 | } | |||
714 | f = faces->next; | |||
715 | do { | |||
716 | if (f->visible) { | |||
717 | t = f; | |||
718 | f = f->next; | |||
719 | DELETE(faces, t)if (faces) { if (faces == faces->next) faces = ((void*)0); else if (t == faces) faces = faces->next; t->next-> prev = t->prev; t->prev->next = t->next; if (t) { free((char *)t); t = ((void*)0); }; }; | |||
720 | } | |||
721 | else | |||
722 | f = f->next; | |||
723 | } while (f != faces); | |||
724 | } | |||
725 | ||||
726 | /*--------------------------------------------------------------------- | |||
727 | CleanVertices runs through the vertex list and deletes the | |||
728 | vertices that are marked as processed but are not incident to any | |||
729 | undeleted edges. | |||
730 | ---------------------------------------------------------------------*/ | |||
731 | void CleanVertices(void) | |||
732 | { | |||
733 | tEdge e; | |||
734 | tVertex v, t; | |||
735 | ||||
736 | /* Mark all vertices incident to some undeleted edge as on the hull. */ | |||
737 | e = edges; | |||
738 | do { | |||
739 | e->endpts[0]->onhull = e->endpts[1]->onhull = ONHULL1; | |||
740 | e = e->next; | |||
741 | } while (e != edges); | |||
742 | ||||
743 | /* Delete all vertices that have been processed but | |||
744 | are not on the hull. */ | |||
745 | while (vertices && vertices->mark && !vertices->onhull) { | |||
746 | v = vertices; | |||
747 | DELETE(vertices, v)if (vertices) { if (vertices == vertices->next) vertices = ((void*)0); else if (v == vertices) vertices = vertices-> next; v->next->prev = v->prev; v->prev->next = v->next; if (v) { free((char *)v); v = ((void*)0); }; }; | |||
748 | } | |||
749 | v = vertices->next; | |||
| ||||
750 | do { | |||
751 | if (v->mark && !v->onhull) { | |||
752 | t = v; | |||
753 | v = v->next; | |||
754 | DELETE(vertices, t)if (vertices) { if (vertices == vertices->next) vertices = ((void*)0); else if (t == vertices) vertices = vertices-> next; t->next->prev = t->prev; t->prev->next = t->next; if (t) { free((char *)t); t = ((void*)0); }; } | |||
755 | } | |||
756 | else | |||
757 | v = v->next; | |||
758 | } while (v != vertices); | |||
759 | ||||
760 | /* Reset flags. */ | |||
761 | v = vertices; | |||
762 | do { | |||
763 | v->duplicate = NULL((void*)0); | |||
764 | v->onhull = !ONHULL1; | |||
765 | v = v->next; | |||
766 | } while (v != vertices); | |||
767 | } | |||
768 | ||||
769 | /*--------------------------------------------------------------------- | |||
770 | Collinear checks to see if the three points given are collinear, | |||
771 | by checking to see if each element of the cross product is zero. | |||
772 | ---------------------------------------------------------------------*/ | |||
773 | bool_Bool Collinear(tVertex a, tVertex b, tVertex c) | |||
774 | { | |||
775 | return (c->v[Z2] - a->v[Z2]) * (b->v[Y1] - a->v[Y1]) - | |||
776 | (b->v[Z2] - a->v[Z2]) * (c->v[Y1] - a->v[Y1]) == | |||
777 | 0 && | |||
778 | (b->v[Z2] - a->v[Z2]) * (c->v[X0] - a->v[X0]) - | |||
779 | (b->v[X0] - a->v[X0]) * (c->v[Z2] - a->v[Z2]) == | |||
780 | 0 && | |||
781 | (b->v[X0] - a->v[X0]) * (c->v[Y1] - a->v[Y1]) - | |||
782 | (b->v[Y1] - a->v[Y1]) * (c->v[X0] - a->v[X0]) == | |||
783 | 0; | |||
784 | } |