BRL-CAD
nmg_tri.c
Go to the documentation of this file.
1 /* N M G _ T R I . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1994-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @addtogroup nmg */
21 /** @{ */
22 /** @file primitives/nmg/nmg_tri.c
23  *
24  * Triangulate the faces of a polygonal NMG.
25  *
26  */
27 /** @} */
28 
29 #include "common.h"
30 
31 #include <stdlib.h>
32 #include <math.h>
33 #include "bio.h"
34 
35 #include "bu/parallel.h"
36 #include "vmath.h"
37 #include "nmg.h"
38 #include "raytrace.h"
39 #include "plot3.h"
40 
41 
42 /* macros for comparing 2D points in scanline order */
43 /* XXX maybe should use near zero tolerance instead */
44 #define TOL_2D 1.0e-10
45 #define P_GT_V(_p, _v) \
46  (((_p)->coord[Y] - (_v)->coord[Y]) > TOL_2D || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] < (_v)->coord[X]))
47 #define P_LT_V(_p, _v) \
48  (((_p)->coord[Y] - (_v)->coord[Y]) < (-TOL_2D) || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] > (_v)->coord[X]))
49 #define P_GE_V(_p, _v) \
50  (((_p)->coord[Y] - (_v)->coord[Y]) > TOL_2D || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] <= (_v)->coord[X]))
51 #define P_LE_V(_p, _v) \
52  (((_p)->coord[Y] - (_v)->coord[Y]) < (-TOL_2D) || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] >= (_v)->coord[X]))
53 
54 #define NMG_PT2D_MAGIC 0x2d2d2d2d
55 #define NMG_TRAP_MAGIC 0x1ab1ab
56 #define NMG_CK_PT2D(_p) NMG_CKMAG(_p, NMG_PT2D_MAGIC, "pt2d")
57 #define NMG_CK_TRAP(_p) {NMG_CKMAG(_p, NMG_TRAP_MAGIC, "trap");\
58  if (! BU_LIST_PREV(bu_list, &(_p)->l)) {\
59  bu_log("%s %d bad prev pointer of trapezoid %p\n", \
60  __FILE__, __LINE__, (void *)&(_p)->l); \
61  bu_bomb("NMG_CK_TRAP: aborting");\
62  } else if (! BU_LIST_NEXT(bu_list, &(_p)->l)) {\
63  bu_log("%s %d bad next pointer of trapezoid %p\n", \
64  __FILE__, __LINE__, (void *)&(_p)->l); \
65  bu_bomb("NMG_CL_TRAP: aborting");\
66  }}
67 
68 #define NMG_TBL2D_MAGIC 0x3e3e3e3e
69 #define NMG_CK_TBL2D(_p) NMG_CKMAG(_p, NMG_TBL2D_MAGIC, "tbl2d")
70 
71 /* macros to retrieve the next/previous 2D point about loop */
72 #define PT2D_NEXT(tbl, pt) pt2d_pn(tbl, pt, 1)
73 #define PT2D_PREV(tbl, pt) pt2d_pn(tbl, pt, -1)
74 
75 struct pt2d {
76  struct bu_list l; /* scanline ordered list of points */
77  fastf_t coord[3]; /* point coordinates in 2-D space */
78  struct vertexuse *vu_p; /* associated vertexuse */
79 };
80 
81 
82 struct trap {
83  struct bu_list l;
84  struct pt2d *top; /* point at top of trapezoid */
85  struct pt2d *bot; /* point at bottom of trapezoid */
86  struct edgeuse *e_left;
87  struct edgeuse *e_right;
88 };
89 
91  struct bu_list l;
92  struct loopuse *lu;
95 };
96 
97 /* if there is an edge in this face which connects the points
98  * return 1
99  * else
100  * return 0
101  */
102 
103 
104 /* subroutine version to pass to the rt_tree functions */
105 int PvsV(struct trap *p, struct trap *v)
106 {
107  NMG_CK_TRAP(p);
108  NMG_CK_TRAP(v);
109 
110  if (p->top->coord[Y] > v->top->coord[Y]) return 1;
111  else if (p->top->coord[Y] < v->top->coord[Y]) return -1;
112  else if (p->top->coord[X] < v->top->coord[X]) return 1;
113  else if (p->top->coord[X] > v->top->coord[X]) return -1;
114  else return 0;
115 }
116 
117 
118 static struct pt2d *find_pt2d(struct bu_list *tbl2d, struct vertexuse *vu);
119 static FILE *plot_fp;
120 static int flatten_debug=1;
121 
122 static struct pt2d *
123 find_pt2d(struct bu_list *tbl2d, struct vertexuse *vu)
124 {
125  struct pt2d *p;
126  NMG_CK_TBL2D(tbl2d);
127 
128  if (vu) {
129  NMG_CK_VERTEXUSE(vu);
130  }
131 
132  for (BU_LIST_FOR(p, pt2d, tbl2d)) {
133  if (p->vu_p == vu) {
134  return p;
135  }
136  }
137  return (struct pt2d *)NULL;
138 }
139 
140 
141 static void
142 nmg_tri_plfu(struct faceuse *fu, struct bu_list *tbl2d)
143 {
144  static int file_number=0;
145  FILE *fp;
146  char name[25];
147  char buf[80];
148  long *b;
149  struct loopuse *lu;
150  struct edgeuse *eu;
151  struct vertexuse *vu;
152  struct pt2d *p;
153 
154  NMG_CK_TBL2D(tbl2d);
155  NMG_CK_FACEUSE(fu);
156 
157  sprintf(name, "tri%02d.plot3", file_number++);
158  fp=fopen(name, "wb");
159  if (fp == (FILE *)NULL) {
160  perror(name);
161  return;
162  }
163 
164  bu_log("\tplotting %s\n", name);
165  b = (long *)bu_calloc(fu->s_p->r_p->m_p->maxindex,
166  sizeof(long), "bit vec"),
167 
168  pl_erase(fp);
169  pd_3space(fp,
170  fu->f_p->min_pt[0]-1.0,
171  fu->f_p->min_pt[1]-1.0,
172  fu->f_p->min_pt[2]-1.0,
173  fu->f_p->max_pt[0]+1.0,
174  fu->f_p->max_pt[1]+1.0,
175  fu->f_p->max_pt[2]+1.0);
176 
177  nmg_pl_fu(fp, fu, b, 255, 255, 255);
178 
179  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
180  NMG_CK_LOOPUSE(lu);
181  if (BU_LIST_IS_EMPTY(&lu->down_hd)) {
182  bu_log("Empty child list for loopuse %s %d\n", __FILE__, __LINE__);
183  } else if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
184  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
185  pdv_3move(fp, vu->v_p->vg_p->coord);
186  p=find_pt2d(tbl2d, vu);
187  if (p) {
188  sprintf(buf, "%g, %g",
189  p->coord[0], p->coord[1]);
190  pl_label(fp, buf);
191  } else
192  pl_label(fp, "X, Y (no 2D coords)");
193 
194  } else {
195  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
196  NMG_CK_EDGEUSE(eu);
197 
198  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
199  p=find_pt2d(tbl2d, eu->vu_p);
200  if (p) {
201  pdv_3move(fp, eu->vu_p->v_p->vg_p->coord);
202 
203  sprintf(buf, "%g, %g",
204  p->coord[0], p->coord[1]);
205  pl_label(fp, buf);
206  } else
207  pl_label(fp, "X, Y (no 2D coords)");
208  }
209  }
210  }
211 
212 
213  bu_free((char *)b, "plot table");
214  fclose(fp);
215 }
216 
217 
218 /**
219  * Return Prev/Next 2D pt about loop from given 2D pt.
220  * if vertex is child of loopuse, return parameter 2D pt.
221  */
222 static struct pt2d *
223 pt2d_pn(struct bu_list *tbl, struct pt2d *pt, int dir)
224 {
225  struct edgeuse *eu, *eu_other;
226  struct pt2d *new_pt;
227 
228  NMG_CK_TBL2D(tbl);
229  NMG_CK_PT2D(pt);
230  NMG_CK_VERTEXUSE((pt)->vu_p);
231 
232  if (*(pt)->vu_p->up.magic_p == NMG_EDGEUSE_MAGIC) {
233  eu = (pt)->vu_p->up.eu_p;
234  NMG_CK_EDGEUSE(eu);
235  if (dir < 0)
236  eu_other = BU_LIST_PPREV_CIRC(edgeuse, eu);
237  else
238  eu_other = BU_LIST_PNEXT_CIRC(edgeuse, eu);
239 
240  new_pt = find_pt2d(tbl, eu_other->vu_p);
241  if (new_pt == (struct pt2d *)NULL) {
242  if (dir < 0)
243  bu_log("can't find prev of %g %g\n",
244  pt->coord[X],
245  pt->coord[Y]);
246  else
247  bu_log("can't find next of %g %g\n",
248  pt->coord[X],
249  pt->coord[Y]);
250  bu_bomb("goodbye\n");
251  }
252  NMG_CK_PT2D(new_pt);
253  return new_pt;
254  }
255 
256  if (*(pt)->vu_p->up.magic_p != NMG_LOOPUSE_MAGIC) {
257  bu_log("%s %d Bad vertexuse parent (%g %g %g)\n",
258  __FILE__, __LINE__,
259  V3ARGS((pt)->vu_p->v_p->vg_p->coord));
260  bu_bomb("goodbye\n");
261  }
262 
263  return pt;
264 }
265 
266 
267 /**
268  * Add a vertex to the 2D table if it isn't already there.
269  */
270 static void
271 map_vu_to_2d(struct vertexuse *vu, struct bu_list *tbl2d, fastf_t *mat, struct faceuse *fu)
272 {
273  struct vertex_g *vg;
274  struct vertexuse *vu_p;
275  struct vertex *vp;
276  struct pt2d *p, *np;
277 
278  NMG_CK_TBL2D(tbl2d);
279  NMG_CK_VERTEXUSE(vu);
280  NMG_CK_FACEUSE(fu);
281 
282  /* if this vertexuse has already been transformed, we're done */
283  if (find_pt2d(tbl2d, vu)) return;
284 
285  BU_ALLOC(np, struct pt2d);
286  np->coord[2] = 0.0;
287  np->vu_p = vu;
289 
290  /* if one of the other vertexuses has been mapped, use that data */
291  for (BU_LIST_FOR(vu_p, vertexuse, &vu->v_p->vu_hd)) {
292  p = find_pt2d(tbl2d, vu_p);
293  if (p) {
294  VMOVE(np->coord, p->coord);
295  return;
296  }
297  }
298 
299  /* transform the 3-D vertex into a 2-D vertex */
300  vg = vu->v_p->vg_p;
301  MAT4X3PNT(np->coord, mat, vg->coord);
302 
303 
304  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug) bu_log(
305  "Transforming %p 3D(%g, %g, %g) to 2D(%g, %g, %g)\n",
306  (void *)vu, V3ARGS(vg->coord), V3ARGS(np->coord));
307 
308  /* find location in scanline ordered list for vertex */
309  for (BU_LIST_FOR(p, pt2d, tbl2d)) {
310  if (P_GT_V(p, np)) continue;
311  break;
312  }
313  BU_LIST_INSERT(&p->l, &np->l);
314 
315  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
316  bu_log("transforming other vertexuses...\n");
317 
318  /* for all other uses of this vertex in this face, store the
319  * transformed 2D vertex
320  */
321  vp = vu->v_p;
322 
323  for (BU_LIST_FOR(vu_p, vertexuse, &vp->vu_hd)) {
324  register struct faceuse *fu_of_vu;
325  NMG_CK_VERTEXUSE(vu_p);
326 
327  if (vu_p == vu) continue;
328 
329  fu_of_vu = nmg_find_fu_of_vu(vu_p);
330  if (!fu_of_vu) continue; /* skip vu's of wire edges */
331  NMG_CK_FACEUSE(fu_of_vu);
332  if (fu_of_vu != fu) continue;
333 
334  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
335  bu_log("transform %p... ", (void *)vu_p);
336 
337  /* if vertexuse already transformed, skip it */
338  if (find_pt2d(tbl2d, vu_p)) {
339  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug) {
340  bu_log("%p vertexuse already transformed\n", (void *)vu);
341  nmg_pr_vu(vu, NULL);
342  }
343  continue;
344  }
345 
346  /* add vertexuse to list */
347  BU_ALLOC(p, struct pt2d);
348  p->vu_p = vu_p;
349  VMOVE(p->coord, np->coord);
351 
352  BU_LIST_APPEND(&np->l, &p->l);
353 
354  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
355  bu_log("vertexuse transformed\n");
356  }
357  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
358  bu_log("Done.\n");
359 }
360 
361 
362 /**
363  * Create the 2D coordinate table for the vertexuses of a face.
364  *
365  * --------- -----------------------------------
366  * |pt2d --+-----> | struct pt2d.{magic, coord[3]} |
367  * --------- -----------------------------------
368  * | struct pt2d.{magic, coord[3]} |
369  * -----------------------------------
370  * | struct pt2d.{magic, coord[3]} |
371  * -----------------------------------
372  *
373  * When the caller is done, nmg_free_2d_map() should be called to dispose
374  * of the map
375  */
376 struct bu_list *
377 nmg_flatten_face(struct faceuse *fu, fastf_t *TformMat, const struct bn_tol *tol)
378 {
379  static const vect_t twoDspace = { 0.0, 0.0, 1.0 };
380  struct bu_list *tbl2d;
381  struct vertexuse *vu;
382  struct loopuse *lu;
383  struct edgeuse *eu;
384  vect_t Normal;
385 
386  NMG_CK_FACEUSE(fu);
387 
388  BU_ALLOC(tbl2d, struct bu_list);
389 
390  /* we use the 0 index entry in the table as the head of the sorted
391  * list of vertices. This is safe since the 0 index is always for
392  * the model structure
393  */
394 
395  BU_LIST_INIT(tbl2d);
397 
398  /* construct the matrix that maps the 3D coordinates into 2D space */
399  NMG_GET_FU_NORMAL(Normal, fu);
400  bn_mat_fromto(TformMat, Normal, twoDspace, tol);
401 
402  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
403  bn_mat_print("TformMat", TformMat);
404 
405 
406  /* convert each vertex in the face to its 2-D equivalent */
407  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
408  if (RTG.NMG_debug & DEBUG_TRI) {
409  switch (lu->orientation) {
410  case OT_NONE: bu_log("flattening OT_NONE loop\n"); break;
411  case OT_SAME: bu_log("flattening OT_SAME loop\n"); break;
412  case OT_OPPOSITE:bu_log("flattening OT_OPPOSITE loop\n"); break;
413  case OT_UNSPEC: bu_log("flattening OT_UNSPEC loop\n"); break;
414  case OT_BOOLPLACE:bu_log("flattening OT_BOOLPLACE loop\n"); break;
415  default: bu_log("flattening bad orientation loop\n"); break;
416  }
417  }
418  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
419  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
420  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
421  bu_log("vertex loop\n");
422  map_vu_to_2d(vu, tbl2d, TformMat, fu);
423 
424  } else if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_EDGEUSE_MAGIC) {
425  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
426  bu_log("edge loop\n");
427  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
428  vu = eu->vu_p;
429  if (RTG.NMG_debug & DEBUG_TRI && flatten_debug)
430  bu_log("(%g %g %g) -> (%g %g %g)\n",
431  V3ARGS(vu->v_p->vg_p->coord),
432  V3ARGS(eu->eumate_p->vu_p->v_p->vg_p->coord));
433  map_vu_to_2d(vu, tbl2d, TformMat, fu);
434  }
435  } else bu_bomb("bad magic of loopuse child\n");
436  }
437 
438  return tbl2d;
439 }
440 
441 
442 static int
443 is_convex(struct pt2d *a, struct pt2d *b, struct pt2d *c, const struct bn_tol *tol)
444 {
445  vect_t ab, bc, pv, N;
446  double angle;
447 
448  NMG_CK_PT2D(a);
449  NMG_CK_PT2D(b);
450  NMG_CK_PT2D(c);
451 
452  /* invent surface normal */
453  VSET(N, 0.0, 0.0, 1.0);
454 
455  /* form vector from a->b */
456  VSUB2(ab, b->coord, a->coord);
457 
458  /* Form "left" vector */
459  VCROSS(pv, N, ab);
460 
461  /* form vector from b->c */
462  VSUB2(bc, c->coord, b->coord);
463 
464  /* find angle about normal in "pv" direction from a->b to b->c */
465  angle = bn_angle_measure(bc, ab, pv);
466 
467  if (RTG.NMG_debug & DEBUG_TRI)
468  bu_log("\tangle == %g tol angle: %g\n", angle, tol->perp);
469 
470  /* Since during loopuse triangulation, sometimes it is necessary
471  * to allow degenerate triangles (i.e. zero area). Because of
472  * this, we need to allow the definition of convex to include 0
473  * and 180 degree angles.
474  */
475  return (angle >= -SMALL_FASTF) && (angle <= (M_PI + SMALL_FASTF));
476 }
477 
478 
479 static void
480 map_new_vertexuse(struct bu_list *tbl2d, struct vertexuse *vu_p)
481 {
482  struct vertexuse *vu;
483  struct pt2d *p, *new_pt2d;
484 
485  NMG_CK_TBL2D(tbl2d);
486  NMG_CK_VERTEXUSE(vu_p);
487 
488  /* if it's already mapped we're outta here! */
489  p = find_pt2d(tbl2d, vu_p);
490  if (p) {
491  if (RTG.NMG_debug & DEBUG_TRI)
492  bu_log("%s %d map_new_vertexuse() vertexuse already mapped!\n",
493  __FILE__, __LINE__);
494  return;
495  }
496  /* allocate memory for new 2D point */
497  BU_ALLOC(new_pt2d, struct pt2d);
498 
499  /* find another use of the same vertex that is already mapped */
500  for (BU_LIST_FOR(vu, vertexuse, &vu_p->v_p->vu_hd)) {
501  NMG_CK_VERTEXUSE(vu);
502  p=find_pt2d(tbl2d, vu);
503  if (!p)
504  continue;
505 
506  /* map parameter vertexuse */
507  new_pt2d->vu_p = vu_p;
508  VMOVE(new_pt2d->coord, p->coord);
509  BU_LIST_MAGIC_SET(&new_pt2d->l, NMG_PT2D_MAGIC);
510  BU_LIST_APPEND(&p->l, &new_pt2d->l);
511  return;
512  }
513 
514  bu_bomb("Couldn't find mapped vertexuse of vertex!\n");
515 }
516 
517 
518 /**
519  * Support routine for
520  * nmg_find_first_last_use_of_v_in_fu
521  *
522  * The object of the game here is to find uses of the given vertex whose
523  * departing edges have the min/max dot product with the direction vector.
524  *
525  */
526 HIDDEN void
527 pick_edges(struct vertex *v, struct vertexuse **vu_first, int *min_dir, struct vertexuse **vu_last, int *max_dir, struct faceuse *fu, fastf_t *dir)
528 
529 
530 /* 1: forward -1 reverse */
531 
532 
533 {
534  struct vertexuse *vu;
535  struct edgeuse *eu_next, *eu_last;
536  struct vertexuse *vu_next, *vu_prev;
537  double dot_max = -2.0;
538  double dot_min = 2.0;
539  double vu_dot;
540  double eu_length_sq;
541  vect_t eu_dir;
542  if (RTG.NMG_debug & DEBUG_TRI)
543  bu_log("\t pick_edges(v:(%g %g %g) dir:(%g %g %g))\n",
544  V3ARGS(v->vg_p->coord), V3ARGS(dir));
545 
546  /* Look at all the uses of this vertex, and find the uses
547  * associated with an edgeuse in this faceuse.
548  *
549  * Compute the dot product of the direction vector with the vector
550  * of the edgeuse, and the PRIOR edgeuse in the loopuse.
551  *
552  * We're looking for the vertexuses with the min/max edgeuse
553  * vector dot product.
554  */
555  *vu_last = *vu_first = (struct vertexuse *)NULL;
556  for (BU_LIST_FOR(vu, vertexuse, &v->vu_hd)) {
557  NMG_CK_VERTEXUSE(vu);
558  NMG_CK_VERTEX(vu->v_p);
559  NMG_CK_VERTEX_G(vu->v_p->vg_p);
560 
561  if (vu->v_p != v)
562  bu_bomb("vertexuse does not acknowledge parents\n");
563 
564  if (nmg_find_fu_of_vu(vu) != fu ||
565  *vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
566  if (RTG.NMG_debug & DEBUG_TRI)
567  bu_log("\t\tskipping irrelevant vertexuse\n");
568  continue;
569  }
570 
571  NMG_CK_EDGEUSE(vu->up.eu_p);
572 
573  /* compute/compare vu/eu vector w/ ray vector */
574  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, vu->up.eu_p);
575  NMG_CK_EDGEUSE(eu_next);
576  vu_next = eu_next->vu_p;
577  NMG_CK_VERTEXUSE(vu_next);
578  NMG_CK_VERTEX(vu_next->v_p);
579  NMG_CK_VERTEX_G(vu_next->v_p->vg_p);
580  VSUB2(eu_dir, vu_next->v_p->vg_p->coord, vu->v_p->vg_p->coord);
581  eu_length_sq = MAGSQ(eu_dir);
582  VUNITIZE(eu_dir);
583 
584  if (RTG.NMG_debug & DEBUG_TRI)
585  bu_log("\t\tchecking forward edgeuse to %g %g %g\n",
586  V3ARGS(vu_next->v_p->vg_p->coord));
587 
588  if (eu_length_sq > SMALL_FASTF) {
589  if ((vu_dot = VDOT(eu_dir, dir)) > dot_max) {
590  if (RTG.NMG_debug & DEBUG_TRI) {
591  bu_log("\t\t\teu_dir %g %g %g\n",
592  V3ARGS(eu_dir));
593 
594  bu_log("\t\t\tnew_last/max %p %g %g %g -> %g %g %g vdot %g\n",
595  (void *)vu,
596  V3ARGS(vu->v_p->vg_p->coord),
597  V3ARGS(vu_next->v_p->vg_p->coord),
598  vu_dot);
599  }
600  dot_max = vu_dot;
601  *vu_last = vu;
602  *max_dir = 1;
603  }
604  if (vu_dot < dot_min) {
605  if (RTG.NMG_debug & DEBUG_TRI) {
606  bu_log("\t\t\teu_dir %g %g %g\n", V3ARGS(eu_dir));
607  bu_log("\t\t\tnew_first/min %p %g %g %g -> %g %g %g vdot %g\n",
608  (void *)vu,
609  V3ARGS(vu->v_p->vg_p->coord),
610  V3ARGS(vu_next->v_p->vg_p->coord),
611  vu_dot);
612  }
613 
614  dot_min = vu_dot;
615  *vu_first = vu;
616  *min_dir = 1;
617  }
618  }
619 
620 
621  /* compute/compare vu/prev_eu vector w/ ray vector */
622  eu_last = BU_LIST_PPREV_CIRC(edgeuse, vu->up.eu_p);
623  NMG_CK_EDGEUSE(eu_last);
624  vu_prev = eu_last->vu_p;
625  NMG_CK_VERTEXUSE(vu_prev);
626  NMG_CK_VERTEX(vu_prev->v_p);
627  NMG_CK_VERTEX_G(vu_prev->v_p->vg_p);
628  /* form vector in reverse direction so that all vectors
629  * "point out" from the vertex in question.
630  */
631  VSUB2(eu_dir, vu_prev->v_p->vg_p->coord, vu->v_p->vg_p->coord);
632  eu_length_sq = MAGSQ(eu_dir);
633  VUNITIZE(eu_dir);
634 
635  if (RTG.NMG_debug & DEBUG_TRI)
636  bu_log("\t\tchecking reverse edgeuse to %g %g %g\n",
637  V3ARGS(vu_prev->v_p->vg_p->coord));
638 
639  if (eu_length_sq > SMALL_FASTF) {
640  if ((vu_dot = VDOT(eu_dir, dir)) > dot_max) {
641  if (RTG.NMG_debug & DEBUG_TRI) {
642  bu_log("\t\t\t-eu_dir %g %g %g\n",
643  V3ARGS(eu_dir));
644  bu_log("\t\t\tnew_last/max %p %g %g %g <- %g %g %g vdot %g\n",
645  (void *)vu,
646  V3ARGS(vu->v_p->vg_p->coord),
647  V3ARGS(vu_prev->v_p->vg_p->coord),
648  vu_dot);
649  }
650  dot_max = vu_dot;
651  *vu_last = vu;
652  *max_dir = -1;
653  }
654  if (vu_dot < dot_min) {
655  if (RTG.NMG_debug & DEBUG_TRI) {
656  bu_log("\t\t\teu_dir %g %g %g\n", V3ARGS(eu_dir));
657  bu_log("\t\t\tnew_first/min %p %g %g %g <- %g %g %g vdot %g\n",
658  (void *)vu,
659  V3ARGS(vu->v_p->vg_p->coord),
660  V3ARGS(vu_prev->v_p->vg_p->coord),
661  vu_dot);
662  }
663  dot_min = vu_dot;
664  *vu_first = vu;
665  *min_dir = -1;
666  }
667  }
668  }
669 
670 }
671 
672 
673 /**
674  * Support routine for
675  * nmg_find_first_last_use_of_v_in_fu
676  *
677  * Given and edgeuse and a faceuse, pick the use of the edge in the faceuse
678  * whose left vector has the largest/smallest dot product with the given
679  * direction vector. The parameter "find_max" determines whether we
680  * return the edgeuse with the largest (find_max != 0) or the smallest
681  * (find_max == 0) left-dot-product.
682  */
683 struct edgeuse *
684 pick_eu(struct edgeuse *eu_p, struct faceuse *fu, fastf_t *dir, int find_max)
685 {
686  struct edgeuse *eu, *keep_eu=NULL, *eu_next;
687  int go_radial_not_mate = 0;
688  double dot_limit;
689  double euleft_dot;
690  vect_t left, eu_vect;
691 
692  if (RTG.NMG_debug & DEBUG_TRI)
693  bu_log("\t pick_eu(%g %g %g <-> %g %g %g, dir:%g %g %g, %s)\n",
694  V3ARGS(eu_p->vu_p->v_p->vg_p->coord),
695  V3ARGS(eu_p->eumate_p->vu_p->v_p->vg_p->coord),
696  V3ARGS(dir), (find_max==0?"find min":"find max"));
697 
698  if (find_max) dot_limit = -2.0;
699  else dot_limit = 2.0;
700 
701  /* walk around the edge looking for uses in this face */
702  eu = eu_p;
703  do {
704  if (nmg_find_fu_of_eu(eu) == fu) {
705  /* compute the vector for this edgeuse */
706  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, eu);
707  VSUB2(eu_vect, eu_next->vu_p->v_p->vg_p->coord,
708  eu->vu_p->v_p->vg_p->coord);
709  VUNITIZE(eu_vect);
710 
711  /* compute the "left" vector for this edgeuse */
712  if (nmg_find_eu_leftvec(left, eu)) {
713  bu_log("%s %d: edgeuse no longer in faceuse?\n", __FILE__, __LINE__);
714  bu_bomb("bombing");
715  }
716 
717  euleft_dot = VDOT(left, dir);
718 
719  if (RTG.NMG_debug & DEBUG_TRI)
720  bu_log("\t\tchecking: %g %g %g -> %g %g %g left vdot:%g\n",
721  V3ARGS(eu->vu_p->v_p->vg_p->coord),
722  V3ARGS(eu_next->vu_p->v_p->vg_p->coord),
723  euleft_dot);
724 
725 
726  /* if this is and edgeuse we need to remember, keep
727  * track of it while we go onward
728  */
729  if (find_max) {
730  if (euleft_dot > dot_limit) {
731  dot_limit = euleft_dot;
732  keep_eu = eu;
733  if (RTG.NMG_debug & DEBUG_TRI)
734  bu_log("\t\tnew max\n");
735  }
736  } else {
737  if (euleft_dot < dot_limit) {
738  dot_limit = euleft_dot;
739  keep_eu = eu;
740  if (RTG.NMG_debug & DEBUG_TRI)
741  bu_log("\t\tnew min\n");
742  }
743  }
744  }
745 
746  if (go_radial_not_mate) eu = eu->eumate_p;
747  else eu = eu->radial_p;
748  go_radial_not_mate = ! go_radial_not_mate;
749 
750  } while (eu != eu_p);
751 
752  if (RTG.NMG_debug & DEBUG_TRI) {
753  if (keep_eu) {
754  bu_log("\t\tpick_eu() returns %g %g %g -> %g %g %g\n\t\t\tbecause vdot(left) = %g\n",
755  V3ARGS(keep_eu->vu_p->v_p->vg_p->coord),
756  V3ARGS(keep_eu->eumate_p->vu_p->v_p->vg_p->coord),
757  dot_limit);
758  } else {
759  bu_log("pick_eu() returns NULL");
760  }
761  }
762 
763  return keep_eu;
764 }
765 
766 
767 /**
768  * Given a pointer to a vertexuse in a face and a ray, find the
769  * "first" and "last" uses of the vertex along the ray in the face.
770  * Consider the diagram below where 4 OT_SAME loopuses meet at a single
771  * vertex. The ray enters from the upper left and proceeds to the lower
772  * right. The ray encounters vertexuse (represented by "o" below)
773  * number 1 first and vertexuse 3 last.
774  *
775  *
776  * edge A
777  * |
778  * \ ^||
779  * \ |||
780  * 1||V2
781  * ------->o|o------->
782  * edge D --------------.-------------edge B
783  * <-------o|o<------
784  * 4^||3
785  * ||| \
786  * ||| \
787  * ||V \|
788  * | -
789  * edge C
790  *
791  * The primary purpose of this routine is to find the vertexuses
792  * that should be the parameters to nmg_cut_loop() and nmg_join_loop().
793  */
794 void
795 nmg_find_first_last_use_of_v_in_fu(struct vertex *v, struct vertexuse **first_vu, struct vertexuse **last_vu, fastf_t *dir, struct faceuse *fu, const struct bn_tol *UNUSED(tol))
796 {
797  struct vertexuse *vu_first, *vu_last;
798  int max_dir=0, min_dir=0; /* 1: forward -1 reverse */
799  struct edgeuse *eu_first, *eu_last, *eu_p=NULL;
800 
801  NMG_CK_VERTEX(v);
802  NMG_CK_FACEUSE(fu);
803  if (first_vu == (struct vertexuse **)(NULL)) {
804  bu_log("%s: %d first_vu is null ptr\n", __FILE__, __LINE__);
805  bu_bomb("terminating\n");
806  }
807  if (last_vu == (struct vertexuse **)(NULL)) {
808  bu_log("%s: %d last_vu is null ptr\n", __FILE__, __LINE__);
809  bu_bomb("terminating\n");
810  }
811 
812  VUNITIZE(dir);
813 
814  if (RTG.NMG_debug & DEBUG_TRI)
815  bu_log("\t nmg_find_first(v:(%g %g %g) dir:(%g %g %g))\n",
816  V3ARGS(v->vg_p->coord), V3ARGS(dir));
817 
818  /* go find the edges which are "closest" to the direction vector */
819  pick_edges(v, &vu_first, &min_dir, &vu_last, &max_dir, fu, dir);
820 
821 
822  /* Now we know which 2 edges are most important to look at.
823  * The question now is which vertexuse on this edge to pick.
824  * For example, in the diagram above we will choose a use of edge C
825  * for our "max". Either vu3 OR vu4 could be chosen.
826  *
827  * For our max/last point, we choose the use for which:
828  * vdot(ray, eu_left_vector)
829  * is largest.
830  *
831  * For our min/first point, we choose the use for which:
832  * vdot(ray, eu_left_vector)
833  * is smallest.
834  */
835 
836  /* get an edgeuse of the proper edge */
837  NMG_CK_VERTEXUSE(vu_first);
838  switch (min_dir) {
839  case -1:
840  eu_p = BU_LIST_PPREV_CIRC(edgeuse, vu_first->up.eu_p);
841  break;
842  case 1:
843  eu_p = vu_first->up.eu_p;
844  break;
845  default:
846  bu_bomb("bad max_dir\n");
847  break;
848  }
849 
850  NMG_CK_EDGEUSE(eu_p);
851  NMG_CK_VERTEXUSE(eu_p->vu_p);
852 
853  eu_first = pick_eu(eu_p, fu, dir, 0);
854  NMG_CK_EDGEUSE(eu_first);
855  NMG_CK_VERTEXUSE(eu_first->vu_p);
856  NMG_CK_VERTEX(eu_first->vu_p->v_p);
857  NMG_CK_VERTEX_G(eu_first->vu_p->v_p->vg_p);
858 
859  if (RTG.NMG_debug & DEBUG_TRI)
860  bu_log("\t first_eu: %g %g %g -> %g %g %g\n",
861  V3ARGS(eu_first->vu_p->v_p->vg_p->coord),
862  V3ARGS(eu_first->eumate_p->vu_p->v_p->vg_p->coord));
863 
864 
865  if (eu_first->vu_p->v_p == v)
866  /* if we wound up with and edgeuse whose vertexuse is
867  * actually on the vertex "v" we're in business, we
868  * simply record the vertexuse with this edgeuse.
869  */
870  *first_vu = eu_first->vu_p;
871  else {
872  /* It looks like we wound up choosing an edgeuse which is
873  * "before" the vertex "v" (an edgeuse that points at "v")
874  * so we need to pick the vertexuse of the NEXT edgeuse
875  */
876  NMG_CK_EDGEUSE(eu_first->eumate_p);
877  NMG_CK_VERTEXUSE(eu_first->eumate_p->vu_p);
878  NMG_CK_VERTEX(eu_first->eumate_p->vu_p->v_p);
879 
880  if (eu_first->eumate_p->vu_p->v_p == v) {
881  eu_p = BU_LIST_PNEXT_CIRC(edgeuse, eu_first);
882  NMG_CK_EDGEUSE(eu_p);
883  NMG_CK_VERTEXUSE(eu_p->vu_p);
884  *first_vu = eu_p->vu_p;
885  } else {
886  bu_log("I got eu_first: %g %g %g -> %g %g %g but...\n",
887  V3ARGS(eu_first->vu_p->v_p->vg_p->coord),
888  V3ARGS(eu_first->eumate_p->vu_p->v_p->vg_p->coord));
889  bu_bomb("I can't find the right vertex\n");
890  }
891  }
892 
893 
894  NMG_CK_VERTEXUSE(vu_last);
895  switch (max_dir) {
896  case -1:
897  eu_p = BU_LIST_PPREV_CIRC(edgeuse, vu_last->up.eu_p);
898  break;
899  case 1:
900  eu_p = vu_last->up.eu_p;
901  break;
902  default:
903  bu_bomb("bad min_dir\n");
904  break;
905  }
906 
907  NMG_CK_EDGEUSE(eu_p);
908  NMG_CK_VERTEXUSE(eu_p->vu_p);
909 
910  eu_last = pick_eu(eu_p, fu, dir, 1);
911 
912  NMG_CK_EDGEUSE(eu_last);
913  NMG_CK_VERTEXUSE(eu_last->vu_p);
914  NMG_CK_VERTEX(eu_last->vu_p->v_p);
915  if (RTG.NMG_debug & DEBUG_TRI)
916  bu_log("\t last_eu: %g %g %g -> %g %g %g\n",
917  V3ARGS(eu_last->vu_p->v_p->vg_p->coord),
918  V3ARGS(eu_last->eumate_p->vu_p->v_p->vg_p->coord));
919 
920 
921  if (eu_last->vu_p->v_p == v)
922  /* if we wound up with and edgeuse whose vertexuse is
923  * actually on the vertex "v" we're in business, we
924  * simply record the vertexuse with this edgeuse.
925  */
926  *last_vu = eu_last->vu_p;
927  else {
928  /* It looks like we wound up choosing an edgeuse which is
929  * "before" the vertex "v" (an edgeuse that points at "v")
930  * so we need to pick the vertexuse of the NEXT edgeuse
931  */
932  NMG_CK_EDGEUSE(eu_last->eumate_p);
933  NMG_CK_VERTEXUSE(eu_last->eumate_p->vu_p);
934  NMG_CK_VERTEX(eu_last->eumate_p->vu_p->v_p);
935 
936  if (eu_last->eumate_p->vu_p->v_p == v) {
937  eu_p = BU_LIST_PNEXT_CIRC(edgeuse, eu_last);
938  NMG_CK_EDGEUSE(eu_p);
939  NMG_CK_VERTEXUSE(eu_p->vu_p);
940  *last_vu = eu_p->vu_p;
941  } else {
942  bu_log("I got eu_last: %g %g %g -> %g %g %g but...\n",
943  V3ARGS(eu_last->vu_p->v_p->vg_p->coord),
944  V3ARGS(eu_last->eumate_p->vu_p->v_p->vg_p->coord));
945  bu_bomb("I can't find the right vertex\n");
946  }
947  }
948 
949 
950  NMG_CK_VERTEXUSE(*first_vu);
951  NMG_CK_VERTEXUSE(*last_vu);
952 }
953 
954 
955 static void
956 pick_pt2d_for_cutjoin(struct bu_list *tbl2d, struct pt2d **p1, struct pt2d **p2, const struct bn_tol *tol)
957 {
958  struct vertexuse *cut_vu1, *cut_vu2, *junk_vu;
959  struct faceuse *fu;
960  vect_t dir;
961 
962  NMG_CK_TBL2D(tbl2d);
963 
964  if (RTG.NMG_debug & DEBUG_TRI)
965  bu_log("\tpick_pt2d_for_cutjoin()\n");
966 
967  BN_CK_TOL(tol);
968  NMG_CK_PT2D(*p1);
969  NMG_CK_PT2D(*p2);
970  NMG_CK_VERTEXUSE((*p1)->vu_p);
971  NMG_CK_VERTEXUSE((*p2)->vu_p);
972 
973  cut_vu1 = (*p1)->vu_p;
974  cut_vu2 = (*p2)->vu_p;
975 
976  NMG_CK_VERTEX(cut_vu1->v_p);
977  NMG_CK_VERTEX_G(cut_vu1->v_p->vg_p);
978  NMG_CK_VERTEX(cut_vu2->v_p);
979  NMG_CK_VERTEX_G(cut_vu2->v_p->vg_p);
980 
981  /* If the 'from' and 'to' cut vertexuse are in the same loopuse,
982  * it should be safe to assume the current pt2d records for these
983  * vertexuse are correct for the cut. Therefore, do not search for
984  * other pt2d vertexuse records, just exit this function using the
985  * vertexuse pt2d records passed into this function. If we allow
986  * this function to continue and search for alternate vertexuse,
987  * sometimes, depending on the number of vertexuse at the cut
988  * points, and the complexity of the angles between the edges at
989  * the cuts, an incorrect vertexuse is often chosen. This change
990  * avoids the error prone logic when we can assume the vertexuse
991  * passed into this function are the correct vertexuse for the
992  * cut, i.e. when the two vertexuse are in the same loopuse.
993  */
994  if ((*p1)->vu_p->up.eu_p->up.lu_p == (*p2)->vu_p->up.eu_p->up.lu_p) {
995  return;
996  }
997 
998  /* form direction vector for the cut we want to make */
999  VSUB2(dir, cut_vu2->v_p->vg_p->coord,
1000  cut_vu1->v_p->vg_p->coord);
1001 
1002  if (RTG.NMG_debug & DEBUG_TRI)
1003  VPRINT("\t\tdir", dir);
1004 
1005  fu = nmg_find_fu_of_vu(cut_vu1);
1006  if (!fu) {
1007  bu_log("%s: %d no faceuse parent of vu\n", __FILE__, __LINE__);
1008  bu_bomb("Bye now\n");
1009  }
1010 
1011  nmg_find_first_last_use_of_v_in_fu((*p1)->vu_p->v_p,
1012  &junk_vu, &cut_vu1, dir, fu, tol);
1013 
1014  NMG_CK_VERTEXUSE(junk_vu);
1015  NMG_CK_VERTEXUSE(cut_vu1);
1016  *p1 = find_pt2d(tbl2d, cut_vu1);
1017 
1018  if (RTG.NMG_debug & DEBUG_TRI) {
1019  struct pt2d *pj, *pj_n, *p1_n;
1020 
1021  pj = find_pt2d(tbl2d, junk_vu);
1022  pj_n = PT2D_NEXT(tbl2d, pj);
1023 
1024  p1_n = PT2D_NEXT(tbl2d, (*p1));
1025 
1026  bu_log("\tp1 pick %g %g -> %g %g (first)\n\t\t%g %g -> %g %g (last)\n",
1027  pj->coord[0], pj->coord[1],
1028  pj_n->coord[0], pj_n->coord[1],
1029  (*p1)->coord[0], (*p1)->coord[1],
1030  p1_n->coord[0], p1_n->coord[1]);
1031  }
1032 
1033 
1034  nmg_find_first_last_use_of_v_in_fu((*p2)->vu_p->v_p,
1035  &cut_vu2, &junk_vu, dir, fu, tol);
1036 
1037 
1038  *p2 = find_pt2d(tbl2d, cut_vu2);
1039  if (RTG.NMG_debug & DEBUG_TRI) {
1040  struct pt2d *pj, *pj_n, *p2_n;
1041 
1042  pj = find_pt2d(tbl2d, junk_vu);
1043  pj_n = PT2D_NEXT(tbl2d, pj);
1044 
1045  p2_n = PT2D_NEXT(tbl2d, (*p2));
1046  bu_log("\tp2 pick %g %g -> %g %g (first)\n\t\t%g %g -> %g %g (last)\n",
1047  (*p2)->coord[0], (*p2)->coord[1],
1048  p2_n->coord[0], p2_n->coord[1],
1049  pj->coord[0], pj->coord[1],
1050  pj_n->coord[0], pj_n->coord[1]);
1051  }
1052 
1053 }
1054 
1055 
1056 static void join_mapped_loops(struct bu_list *tbl2d, struct pt2d *p1, struct pt2d *p2, const int *color, const struct bn_tol *tol);
1057 
1058 /**
1059  *
1060  * Cut a loop which has a 2D mapping. Since this entails the creation
1061  * of new vertexuses, it is necessary to add a 2D mapping for the new
1062  * vertexuses.
1063  *
1064  */
1065 static struct pt2d *
1066 cut_mapped_loop(struct bu_list *tbl2d, struct pt2d *p1, struct pt2d *p2, const int *color, const struct bn_tol *tol, int void_ok)
1067 {
1068  struct loopuse *new_lu;
1069  struct loopuse *old_lu;
1070  struct edgeuse *eu;
1071 
1072  NMG_CK_TBL2D(tbl2d);
1073  BN_CK_TOL(tol);
1074  NMG_CK_PT2D(p1);
1075  NMG_CK_PT2D(p2);
1076  NMG_CK_VERTEXUSE(p1->vu_p);
1077  NMG_CK_VERTEXUSE(p2->vu_p);
1078 
1079  if (RTG.NMG_debug & DEBUG_TRI)
1080  bu_log("\tcutting loop @ %g %g -> %g %g\n",
1081  p1->coord[X], p1->coord[Y],
1082  p2->coord[X], p2->coord[Y]);
1083 
1084  if (p1->vu_p->up.eu_p->up.lu_p != p2->vu_p->up.eu_p->up.lu_p) {
1085  bu_log("parent loops are not the same %s %d\n", __FILE__, __LINE__);
1086  bu_bomb("cut_mapped_loop() goodnight 1\n");
1087  }
1088 
1089  pick_pt2d_for_cutjoin(tbl2d, &p1, &p2, tol);
1090 
1091  if (p1->vu_p->up.eu_p->up.lu_p != p2->vu_p->up.eu_p->up.lu_p) {
1092  if (void_ok) {
1093  if (RTG.NMG_debug)
1094  bu_log("cut_mapped_loop() parent loops are not the same %s %d, trying join\n", __FILE__, __LINE__);
1095  join_mapped_loops(tbl2d, p1, p2, color, tol);
1096  return (struct pt2d *)NULL;
1097  } else {
1098  char buf[80];
1099  char name[32];
1100  static int iter=0;
1101  vect_t cut_vect, cut_start, cut_end;
1102  FILE *fp;
1103 
1104  bu_log("parent loops are not the same %s %d\n",
1105  __FILE__, __LINE__);
1106 
1107 
1108  sprintf(buf, "cut %g %g %g -> %g %g %g\n",
1109  V3ARGS(p1->vu_p->v_p->vg_p->coord),
1110  V3ARGS(p2->vu_p->v_p->vg_p->coord));
1111 
1112  sprintf(name, "bad_tri_cut%d.g", iter++);
1113  fp=fopen("bad_tri_cut.plot3", "wb");
1114  if (fp == (FILE *)NULL)
1115  bu_bomb("cut_mapped_loop() goodnight 2\n");
1116 
1117  VSUB2(cut_vect, p2->vu_p->v_p->vg_p->coord, p1->vu_p->v_p->vg_p->coord);
1118  /* vector goes past end point by 50% */
1119  VJOIN1(cut_end, p2->vu_p->v_p->vg_p->coord, 0.5, cut_vect);
1120  /* vector starts before start point by 25% */
1121  VJOIN1(cut_start, p1->vu_p->v_p->vg_p->coord, -0.25, cut_vect);
1122 
1123  pl_color(fp, 100, 100, 100);
1124  pdv_3line(fp, cut_start, p1->vu_p->v_p->vg_p->coord);
1125  pl_color(fp, 255, 255, 255);
1126  pdv_3line(fp, p1->vu_p->v_p->vg_p->coord, p2->vu_p->v_p->vg_p->coord);
1127  pl_color(fp, 100, 100, 100);
1128  pdv_3line(fp, p2->vu_p->v_p->vg_p->coord, cut_end);
1129 
1130  (void)fclose(fp);
1131  nmg_stash_model_to_file("bad_tri_cut.g",
1132  nmg_find_model(&p1->vu_p->l.magic), buf);
1133 
1134  bu_bomb("cut_mapped_loop() goodnight 3\n");
1135  }
1136  }
1137 
1138  if (plot_fp) {
1139  pl_color(plot_fp, V3ARGS(color));
1140  pdv_3line(plot_fp, p1->coord, p2->coord);
1141  }
1142 
1143  old_lu = p1->vu_p->up.eu_p->up.lu_p;
1144  NMG_CK_LOOPUSE(old_lu);
1145  new_lu = nmg_cut_loop(p1->vu_p, p2->vu_p);
1146  NMG_CK_LOOPUSE(new_lu);
1147  NMG_CK_LOOP(new_lu->l_p);
1148  nmg_loop_g(new_lu->l_p, tol);
1149 
1150  /* XXX Does anyone care about loopuse orientations at this stage?
1151  nmg_lu_reorient(old_lu);
1152  nmg_lu_reorient(new_lu);
1153  */
1154 
1155  /* get the edgeuse of the new vertexuse we just created */
1156  eu = BU_LIST_PPREV_CIRC(edgeuse, &new_lu->down_hd);
1157  NMG_CK_EDGEUSE(eu);
1158 
1159  /* if the original vertexuses had normals,
1160  * copy them to the new vertexuses.
1161  */
1162  if (p1->vu_p->a.magic_p && *p1->vu_p->a.magic_p == NMG_VERTEXUSE_A_PLANE_MAGIC) {
1163  struct vertexuse *vu;
1164  struct faceuse *fu;
1165  struct loopuse *lu;
1166  vect_t ot_same_normal;
1167  vect_t ot_opposite_normal;
1168 
1169  /* get vertexuse normal */
1170  VMOVE(ot_same_normal, p1->vu_p->a.plane_p->N);
1171  fu = nmg_find_fu_of_vu(p1->vu_p);
1172  NMG_CK_FACEUSE(fu);
1173  if (fu->orientation == OT_OPPOSITE)
1174  VREVERSE(ot_same_normal, ot_same_normal);
1175 
1176  VREVERSE(ot_opposite_normal, ot_same_normal);
1177 
1178  /* look for new vertexuses in new_lu and old_lu */
1179  for (BU_LIST_FOR(vu, vertexuse, &p1->vu_p->v_p->vu_hd)) {
1180  if (vu->a.magic_p)
1181  continue;
1182 
1183  lu = nmg_find_lu_of_vu(vu);
1184  if (lu != old_lu && lu != old_lu->lumate_p &&
1185  lu != new_lu && lu != new_lu->lumate_p)
1186  continue;
1187 
1188  /* assign appropriate normal */
1189  fu = nmg_find_fu_of_vu(vu);
1190  if (fu->orientation == OT_SAME)
1191  nmg_vertexuse_nv(vu, ot_same_normal);
1192  else if (fu->orientation == OT_OPPOSITE)
1193  nmg_vertexuse_nv(vu, ot_opposite_normal);
1194  }
1195  }
1196  if (p2->vu_p->a.magic_p && *p2->vu_p->a.magic_p == NMG_VERTEXUSE_A_PLANE_MAGIC) {
1197  struct vertexuse *vu;
1198  struct faceuse *fu;
1199  struct loopuse *lu;
1200  vect_t ot_same_normal;
1201  vect_t ot_opposite_normal;
1202 
1203  /* get vertexuse normal */
1204  VMOVE(ot_same_normal, p2->vu_p->a.plane_p->N);
1205  fu = nmg_find_fu_of_vu(p2->vu_p);
1206  NMG_CK_FACEUSE(fu);
1207  if (fu->orientation == OT_OPPOSITE)
1208  VREVERSE(ot_same_normal, ot_same_normal);
1209 
1210  VREVERSE(ot_opposite_normal, ot_same_normal);
1211 
1212  /* look for new vertexuses in new_lu and old_lu */
1213  for (BU_LIST_FOR(vu, vertexuse, &p2->vu_p->v_p->vu_hd)) {
1214  if (vu->a.magic_p)
1215  continue;
1216 
1217  lu = nmg_find_lu_of_vu(vu);
1218  if (lu != old_lu && lu != old_lu->lumate_p &&
1219  lu != new_lu && lu != new_lu->lumate_p)
1220  continue;
1221 
1222  /* assign appropriate normal */
1223  fu = nmg_find_fu_of_vu(vu);
1224  if (fu->orientation == OT_SAME)
1225  nmg_vertexuse_nv(vu, ot_same_normal);
1226  else if (fu->orientation == OT_OPPOSITE)
1227  nmg_vertexuse_nv(vu, ot_opposite_normal);
1228  }
1229  }
1230 
1231  /* map it to the 2D plane */
1232  map_new_vertexuse(tbl2d, eu->vu_p);
1233 
1234  /* now map the vertexuse on the radially-adjacent edgeuse */
1235  NMG_CK_EDGEUSE(eu->radial_p);
1236  map_new_vertexuse(tbl2d, eu->radial_p->vu_p);
1237 
1238  eu = BU_LIST_PPREV_CIRC(edgeuse, &(p1->vu_p->up.eu_p->l));
1239  return find_pt2d(tbl2d, eu->vu_p);
1240 }
1241 
1242 
1243 /**
1244  *
1245  * Join 2 loops (one forms a hole in the other usually)
1246  *
1247  */
1248 static void
1249 join_mapped_loops(struct bu_list *tbl2d, struct pt2d *p1, struct pt2d *p2, const int *color, const struct bn_tol *tol)
1250 {
1251  struct vertexuse *vu, *vu1, *vu2;
1252  struct edgeuse *eu = (struct edgeuse *)NULL;
1253  struct loopuse *lu = (struct loopuse *)NULL;
1254 
1255  NMG_CK_TBL2D(tbl2d);
1256  NMG_CK_PT2D(p1);
1257  NMG_CK_PT2D(p2);
1258  BN_CK_TOL(tol);
1259 
1260  vu = (struct vertexuse *)NULL;
1261  vu1 = p1->vu_p;
1262  vu2 = p2->vu_p;
1263 
1264  NMG_CK_VERTEXUSE(vu1);
1265  NMG_CK_VERTEXUSE(vu2);
1266 
1267  if (RTG.NMG_debug & DEBUG_TRI)
1268  bu_log("join_mapped_loops()\n");
1269 
1270  if (((p1->vu_p->up.eu_p->up.lu_p->orientation != OT_OPPOSITE) &&
1271  (p1->vu_p->up.eu_p->up.lu_p->orientation != OT_SAME)) ||
1272  ((p2->vu_p->up.eu_p->up.lu_p->orientation != OT_OPPOSITE) &&
1273  (p2->vu_p->up.eu_p->up.lu_p->orientation != OT_SAME))) {
1274  bu_bomb("join_mapped_loops(): loopuse orientation is not OT_SAME or OT_OPPOSITE\n");
1275  }
1276 
1277  if ((p1->vu_p->up.eu_p->up.lu_p->orientation == OT_OPPOSITE) &&
1278  (p2->vu_p->up.eu_p->up.lu_p->orientation == OT_OPPOSITE)) {
1279  bu_bomb("join_mapped_loops(): both loopuse can not have orientation OT_OPPOSITE (1)\n");
1280  }
1281 
1282  if (p1 == p2) {
1283  bu_log("join_mapped_loops(): %s %d Attempting to join loop to itself at (%g %g %g)?\n",
1284  __FILE__, __LINE__,
1285  V3ARGS(p1->vu_p->v_p->vg_p->coord));
1286  bu_bomb("join_mapped_loops(): bombing\n");
1287  } else if (p1->vu_p->up.eu_p->up.lu_p == p2->vu_p->up.eu_p->up.lu_p) {
1288  bu_log("join_mapped_loops(): parent loops are the same %s %d\n", __FILE__, __LINE__);
1289  bu_bomb("join_mapped_loops(): bombing\n");
1290  }
1291  /* check to see if we're joining two loops that share a vertex */
1292  if (p1->vu_p->v_p == p2->vu_p->v_p) {
1293  if (RTG.NMG_debug & DEBUG_TRI) {
1294  bu_log("join_mapped_loops(): Joining two loops that share a vertex at (%g %g %g)\n",
1295  V3ARGS(p1->vu_p->v_p->vg_p->coord));
1296  }
1297  vu = nmg_join_2loops(p1->vu_p, p2->vu_p);
1298  goto out;
1299  }
1300 
1301  pick_pt2d_for_cutjoin(tbl2d, &p1, &p2, tol);
1302 
1303  if (p1->vu_p->up.eu_p->up.lu_p == p2->vu_p->up.eu_p->up.lu_p) {
1304  bu_bomb("join_mapped_loops(): attempting to join a loopuse to itself\n");
1305  }
1306  if (p1->vu_p == p2->vu_p) {
1307  bu_bomb("join_mapped_loops(): attempting to join a vertexuse to itself\n");
1308  }
1309 
1310  vu1 = p1->vu_p;
1311  vu2 = p2->vu_p;
1312  NMG_CK_VERTEXUSE(vu1);
1313  NMG_CK_VERTEXUSE(vu2);
1314 
1315  if (p1 == p2) {
1316  bu_log("join_mapped_loops(): %s %d trying to join a vertexuse (%g %g %g) to itself\n",
1317  __FILE__, __LINE__,
1318  V3ARGS(p1->vu_p->v_p->vg_p->coord));
1319  } else if (p1->vu_p->up.eu_p->up.lu_p == p2->vu_p->up.eu_p->up.lu_p) {
1320  if (RTG.NMG_debug & DEBUG_TRI) {
1321  bu_log("join_mapped_loops(): parent loops are the same %s %d\n",
1322  __FILE__, __LINE__);
1323  }
1324  (void)cut_mapped_loop(tbl2d, p1, p2, color, tol, 1);
1325  return;
1326  }
1327 
1328  if ((vu1->up.eu_p->up.lu_p->orientation == OT_OPPOSITE) &&
1329  (vu2->up.eu_p->up.lu_p->orientation == OT_OPPOSITE)) {
1330  bu_bomb("join_mapped_loops(): both loopuse can not have orientation OT_OPPOSITE (2)\n");
1331  }
1332 
1333  if (*vu2->up.magic_p != NMG_EDGEUSE_MAGIC) {
1334  bu_bomb("join_mapped_loops(): vertexuse vu2 must belong to an edgeuse\n");
1335  }
1336 
1337  NMG_CK_EDGEUSE(vu2->up.eu_p);
1338 
1339  /* need to save this so we can use it later to get
1340  * the new "next" edge/vertexuse
1341  */
1342  eu = BU_LIST_PPREV_CIRC(edgeuse, vu2->up.eu_p);
1343 
1344 
1345  if (RTG.NMG_debug & DEBUG_TRI) {
1346  struct edgeuse *pr1_eu;
1347  struct edgeuse *pr2_eu;
1348 
1349  pr1_eu = BU_LIST_PNEXT_CIRC(edgeuse, vu1->up.eu_p);
1350  pr2_eu = BU_LIST_PNEXT_CIRC(edgeuse, vu2->up.eu_p);
1351 
1352  bu_log("join_mapped_loops(): joining loops between:\n\t%g %g %g -> (%g %g %g)\n\tand%g %g %g -> (%g %g %g)\n",
1353  V3ARGS(vu1->v_p->vg_p->coord),
1354  V3ARGS(pr1_eu->vu_p->v_p->vg_p->coord),
1355  V3ARGS(vu2->v_p->vg_p->coord),
1356  V3ARGS(pr2_eu->vu_p->v_p->vg_p->coord));
1357  }
1358 
1359  vu = nmg_join_2loops(vu1, vu2);
1360  if (plot_fp) {
1361  pl_color(plot_fp, V3ARGS(color));
1362  pdv_3line(plot_fp, p1->coord, p2->coord);
1363  }
1364 
1365 
1366  NMG_CK_VERTEXUSE(vu);
1367 
1368  if (vu == vu2) {
1369  bu_bomb("join_mapped_loops(): vu == vu2\n");
1370  }
1371  /* since we've just made some new vertexuses
1372  * we need to map them to the 2D plane.
1373  *
1374  * XXX This should be made more direct and efficient. For now we
1375  * just go looking for vertexuses without a mapping.
1376  */
1377 out:
1378  NMG_CK_EDGEUSE(vu->up.eu_p);
1379  NMG_CK_LOOPUSE(vu->up.eu_p->up.lu_p);
1380  lu = vu->up.eu_p->up.lu_p;
1381  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1382  if (!find_pt2d(tbl2d, eu->vu_p)) {
1383  map_new_vertexuse(tbl2d, eu->vu_p);
1384  }
1385  }
1386 }
1387 
1388 
1389 void
1390 nmg_plot_fu(const char *prefix, const struct faceuse *fu, const struct bn_tol *UNUSED(tol))
1391 {
1392  struct loopuse *lu;
1393  struct edgeuse *eu;
1394  int edgeuse_vert_count = 0;
1395  int non_consec_edgeuse_vert_count = 0;
1396  int faceuse_loopuse_count = 0;
1397  struct vertex *prev_v_p = (struct vertex *)NULL;
1398  struct vertex *curr_v_p = (struct vertex *)NULL;
1399  struct vertex *first_v_p = (struct vertex *)NULL;
1400  struct edgeuse *curr_eu = (struct edgeuse *)NULL;
1401  struct edgeuse *prev_eu = (struct edgeuse *)NULL;
1402  struct edgeuse *first_eu = (struct edgeuse *)NULL;
1403  FILE *plotfp;
1404  struct bu_vls plot_file_name = BU_VLS_INIT_ZERO;
1405 
1406  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1407 
1408  /* skip loops which do not contain edges */
1409  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
1410  continue;
1411  }
1412  non_consec_edgeuse_vert_count = 0;
1413  edgeuse_vert_count = 0;
1414  prev_v_p = (struct vertex *)NULL;
1415  curr_v_p = (struct vertex *)NULL;
1416  first_v_p = (struct vertex *)NULL;
1417  curr_eu = (struct edgeuse *)NULL;
1418  prev_eu = (struct edgeuse *)NULL;
1419  first_eu = (struct edgeuse *)NULL;
1420 
1421  faceuse_loopuse_count++;
1422 
1423  bu_vls_sprintf(&plot_file_name, "%s_faceuse_%p_loopuse_%p.pl",
1424  prefix, (void *)fu, (void *)lu);
1425  plotfp = fopen(bu_vls_addr(&plot_file_name), "wb");
1426 
1427  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1428  curr_v_p = eu->vu_p->v_p;
1429  curr_eu = eu;
1430  if (edgeuse_vert_count == 0) {
1431  first_v_p = curr_v_p;
1432  first_eu = eu;
1433  }
1434  if (edgeuse_vert_count <= 1) {
1435  if (first_eu->e_p->is_real) {
1436  /* if 1st edgeuse is real set start edge plot color to hot pink */
1437  pl_color(plotfp, 255,105,180);
1438  } else {
1439  /* set first segment red */
1440  pl_color(plotfp, 255,0,0);
1441  }
1442  } else {
1443  if (prev_eu->e_p->is_real) {
1444  /* set middle segments shades of yellow */
1445  pl_color(plotfp, ((edgeuse_vert_count * 30) % 155) + 100,
1446  ((edgeuse_vert_count * 30) % 155) + 100, 0);
1447  } else {
1448  /* set middle segments shades of green */
1449  pl_color(plotfp, 0, ((edgeuse_vert_count * 30) % 155) + 100, 0);
1450  }
1451  }
1452  edgeuse_vert_count++;
1453  if (curr_v_p != prev_v_p) {
1454  non_consec_edgeuse_vert_count++;
1455  }
1456  if (edgeuse_vert_count > 1) {
1457  bn_dist_pt3_pt3(prev_v_p->vg_p->coord,curr_v_p->vg_p->coord);
1458  pdv_3line(plotfp, prev_v_p->vg_p->coord, curr_v_p->vg_p->coord);
1459  }
1460  prev_v_p = curr_v_p;
1461  prev_eu = curr_eu;
1462  }
1463 
1464  if (curr_v_p && first_v_p) {
1465  bn_dist_pt3_pt3(first_v_p->vg_p->coord,curr_v_p->vg_p->coord);
1466  if (curr_eu->e_p->is_real) {
1467  /* set last segment if is_real to cyan */
1468  pl_color(plotfp, 0, 255, 255);
1469  } else {
1470  /* set last segment blue */
1471  pl_color(plotfp, 0,0,255);
1472  }
1473  pdv_3line(plotfp, curr_v_p->vg_p->coord, first_v_p->vg_p->coord);
1474  }
1475  (void)fclose(plotfp);
1476  bu_vls_free(&plot_file_name);
1477  }
1478 }
1479 
1480 /*
1481  * 0 = no isect (out)
1482  * 1 = isect edge, but not vertex (on)
1483  * 2 = isect vertex (shared, vertex fused)
1484  * 3 = isect vertex (non-shared, vertex not fused)
1485  * 4 = inside (on)
1486  */
1487 
1488 int
1489 nmg_isect_pt_facet(struct vertex *v, struct vertex *v0, struct vertex *v1, struct vertex *v2, const struct bn_tol *tol)
1490 {
1491  fastf_t *p, *p0, *p1, *p2;
1492  fastf_t dp0p1, dp0p2, dp1p2; /* dist p0->p1, p0->p2, p1->p2 */
1493  fastf_t dpp0, dpp1, dpp2; /* dist p->p0, p->p1, p->p2 */
1494  point_t bb_min, bb_max;
1495  vect_t p0_p2, p0_p1, p0_p;
1496  fastf_t p0_p2_magsq, p0_p1_magsq;
1497  fastf_t p0_p2__p0_p1, p0_p2__p0_p, p0_p1__p0_p;
1498  fastf_t u, v00, u_numerator, v_numerator, denom;
1499  int degen_p0p1, degen_p0p2, degen_p1p2;
1500  int para_p0_p1__p0_p;
1501  int para_p0_p2__p0_p;
1502  int para_p1_p2__p1_p;
1503 
1504  NMG_CK_VERTEX(v);
1505  NMG_CK_VERTEX(v0);
1506  NMG_CK_VERTEX(v1);
1507  NMG_CK_VERTEX(v2);
1508  NMG_CK_VERTEX_G(v->vg_p);
1509  NMG_CK_VERTEX_G(v0->vg_p);
1510  NMG_CK_VERTEX_G(v1->vg_p);
1511  NMG_CK_VERTEX_G(v2->vg_p);
1512 
1513  p = v->vg_p->coord;
1514  p0 = v0->vg_p->coord;
1515  p1 = v1->vg_p->coord;
1516  p2 = v2->vg_p->coord;
1517 
1518  degen_p0p1 = degen_p0p2 = degen_p1p2 = 0;
1519  if (v0 == v1) {
1520  degen_p0p1 = 1;
1521  }
1522  if (v0 == v2) {
1523  degen_p0p2 = 1;
1524  }
1525  if (v1 == v2) {
1526  degen_p1p2 = 1;
1527  }
1528 
1529  if (v == v0 || v == v1 || v == v2) {
1530  return 2; /* isect vertex (shared, vertex fused) */
1531  }
1532 
1533  /* find facet bounding box */
1534  VSETALL(bb_min, INFINITY);
1535  VSETALL(bb_max, -INFINITY);
1536  VMINMAX(bb_min, bb_max, p0);
1537  VMINMAX(bb_min, bb_max, p1);
1538  VMINMAX(bb_min, bb_max, p2);
1539 
1540  if (V3PT_OUT_RPP_TOL(p, bb_min, bb_max, tol->dist)) {
1541  return 0; /* no isect */
1542  }
1543 
1544  dp0p1 = bn_dist_pt3_pt3(p0, p1);
1545  dp0p2 = bn_dist_pt3_pt3(p0, p2);
1546  dp1p2 = bn_dist_pt3_pt3(p1, p2);
1547 
1548  if (!degen_p0p1 && (dp0p1 < tol->dist)) {
1549  degen_p0p1 = 2;
1550  }
1551  if (!degen_p0p2 && (dp0p2 < tol->dist)) {
1552  degen_p0p2 = 2;
1553  }
1554  if (!degen_p1p2 && (dp1p2 < tol->dist)) {
1555  degen_p1p2 = 2;
1556  }
1557 
1558  dpp0 = bn_dist_pt3_pt3(p, p0);
1559  dpp1 = bn_dist_pt3_pt3(p, p1);
1560  dpp2 = bn_dist_pt3_pt3(p, p2);
1561 
1562  if (dpp0 < tol->dist || dpp1 < tol->dist || dpp2 < tol->dist) {
1563  return 3; /* isect vertex (non-shared, vertex not fused) */
1564  }
1565 
1566  para_p0_p1__p0_p = para_p0_p2__p0_p = para_p1_p2__p1_p = 0;
1567  /* test p against edge p0->p1 */
1568  if (!degen_p0p1 && bn_lseg3_lseg3_parallel(p0, p1, p0, p, tol)) {
1569  /* p might be on edge p0->p1 */
1570  para_p0_p1__p0_p = 1;
1571  if (NEAR_EQUAL(dpp0 + dpp1, dp0p1, tol->dist)) {
1572  /* p on edge p0->p1 */
1573  return 1; /* isect edge, but not vertex (on) */
1574  }
1575  }
1576  /* test p against edge p0->p2 */
1577  if (!degen_p0p2 && bn_lseg3_lseg3_parallel(p0, p2, p0, p, tol)) {
1578  /* p might be on edge p0->p2 */
1579  para_p0_p2__p0_p = 1;
1580  if (NEAR_EQUAL(dpp0 + dpp2, dp0p2, tol->dist)) {
1581  /* p on edge p0->p2 */
1582  return 1; /* isect edge, but not vertex (on) */
1583  }
1584  }
1585  /* test p against edge p1->p2 */
1586  if (!degen_p1p2 && bn_lseg3_lseg3_parallel(p1, p2, p1, p, tol)) {
1587  /* p might be on edge p1->p2 */
1588  para_p1_p2__p1_p = 1;
1589  if (NEAR_EQUAL(dpp1 + dpp2, dp1p2, tol->dist)) {
1590  /* p on edge p1->p2 */
1591  return 1; /* isect edge, but not vertex (on) */
1592  }
1593  }
1594 
1595  if (degen_p0p1 || degen_p0p2 || degen_p1p2) {
1596  return 0; /* no isect (out) */
1597  }
1598  if (para_p0_p1__p0_p || para_p0_p2__p0_p || para_p1_p2__p1_p) {
1599  return 0; /* no isect (out) */
1600  }
1601 
1602  VSUB2(p0_p2, p2, p0);
1603  VSUB2(p0_p1, p1, p0);
1604  VSUB2(p0_p, p, p0);
1605 
1606  p0_p2_magsq = MAGSQ(p0_p2);
1607  p0_p1_magsq = MAGSQ(p0_p1);
1608  p0_p2__p0_p1 = VDOT(p0_p2, p0_p1);
1609  p0_p2__p0_p = VDOT(p0_p2, p0_p);
1610  p0_p1__p0_p = VDOT(p0_p1, p0_p);
1611 
1612  u_numerator = ( p0_p1_magsq * p0_p2__p0_p - p0_p2__p0_p1 * p0_p1__p0_p );
1613  v_numerator = ( p0_p2_magsq * p0_p1__p0_p - p0_p2__p0_p1 * p0_p2__p0_p );
1614  denom = ( p0_p2_magsq * p0_p1_magsq - p0_p2__p0_p1 * p0_p2__p0_p1 );
1615 
1616  if (ZERO(denom)) {
1617  denom = 1.0;
1618  }
1619 
1620  if (NEAR_ZERO(u_numerator, tol->dist)) {
1621  u_numerator = 0.0;
1622  u = 0.0;
1623  } else {
1624  u = u_numerator / denom;
1625  }
1626 
1627  if (NEAR_ZERO(v_numerator, tol->dist)) {
1628  v_numerator = 0.0;
1629  v00 = 0.0;
1630  } else {
1631  v00 = v_numerator / denom;
1632  }
1633 
1634  if ((u > SMALL_FASTF) && (v00 > SMALL_FASTF) && ((u + v00) < (1.0 - SMALL_FASTF))) {
1635  return 4; /* inside (on) */
1636  }
1637 
1638  return 0; /* no isect (out) */
1639 }
1640 
1641 
1642 /**
1643  * Given the faceuse 'fu' test if the potential cut, defined by an
1644  * edgeuse from 'eu1->vu_p' to 'eu2->vu_p', intersects any edgeuse of
1645  * the faceuse.
1646  *
1647  * Return 1 if intersect found otherwise return 0.
1648  */
1649 int
1650 nmg_isect_potcut_fu(struct edgeuse *eu1, struct edgeuse *eu2, struct faceuse *fu, const struct bn_tol *tol)
1651 {
1652  point_t p1, p2, q1, q2;
1653  vect_t pdir, qdir;
1654  fastf_t dist[2];
1655  int status;
1656  int hit = 0;
1657  struct loopuse *lu;
1658  struct edgeuse *eu;
1659  struct vertexuse *vu1b, *vu2b;
1660  struct vertexuse *vu1, *vu2;
1661 
1662  vu1 = eu1->vu_p;
1663  vu1b = (BU_LIST_PNEXT_CIRC(edgeuse, &eu1->eumate_p->l))->vu_p;
1664  vu2 = eu2->vu_p;
1665  vu2b = (BU_LIST_PNEXT_CIRC(edgeuse, &eu2->eumate_p->l))->vu_p;
1666 
1667  /* vu1b and vu2b are the vertexuse of the faceuse mate that shares
1668  * the same vertex as vu1 and vu2, respectively.
1669  */
1670 
1671  BN_CK_TOL(tol);
1672  NMG_CK_FACEUSE(fu);
1673 
1674  /* Loop thru all loopuse, looking for intersections */
1675  hit = 0;
1676  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1677  NMG_CK_LOOPUSE(lu);
1678 
1679  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1680 
1681  /* skip testing eu1 and eu2 */
1682  if (eu->vu_p == vu1 || eu->vu_p == vu1b || eu->vu_p == vu2 || eu->vu_p == vu2b) {
1683  continue;
1684  }
1685 
1686  NMG_CK_EDGEUSE(eu);
1687 
1688  NMG_CK_VERTEXUSE(vu2);
1689  NMG_CK_VERTEXUSE(vu1);
1690  NMG_CK_VERTEXUSE(eu->vu_p);
1691  NMG_CK_VERTEXUSE(eu->eumate_p->vu_p);
1692 
1693  NMG_CK_VERTEX(vu2->v_p);
1694  NMG_CK_VERTEX(vu1->v_p);
1695  NMG_CK_VERTEX(eu->vu_p->v_p);
1696  NMG_CK_VERTEX(eu->eumate_p->vu_p->v_p);
1697 
1698  NMG_CK_VERTEX_G(vu2->v_p->vg_p);
1699  NMG_CK_VERTEX_G(vu1->v_p->vg_p);
1700  NMG_CK_VERTEX_G(eu->vu_p->v_p->vg_p);
1701  NMG_CK_VERTEX_G(eu->eumate_p->vu_p->v_p->vg_p);
1702 
1703  /* Test if edge is zero length, if so bomb since this
1704  * should not happen.
1705  */
1706  if (eu->vu_p->v_p->vg_p->coord == eu->eumate_p->vu_p->v_p->vg_p->coord) {
1707  bu_bomb("nmg_isect_lseg3_eu(): found zero length edge\n");
1708  }
1709 
1710  VMOVE(p1, vu2->v_p->vg_p->coord);
1711  VMOVE(p2, vu1->v_p->vg_p->coord);
1712  VSUB2(pdir, p2, p1);
1713  VMOVE(q1, eu->vu_p->v_p->vg_p->coord);
1714  VMOVE(q2, eu->eumate_p->vu_p->v_p->vg_p->coord);
1715  VSUB2(qdir, q2, q1);
1716 
1717  status = bn_isect_lseg3_lseg3(dist, p1, pdir, q1, qdir, tol);
1718 
1719  if (status == 0) { /* colinear and overlapping */
1720  /* Hit because, can only skip if hit on end point only
1721  * and overlapping indicates more than an end point
1722  * was hit.
1723  */
1724  hit = 1;
1725  } else if (status == 1) { /* normal intersection */
1726 
1727  /* When either (p1 = q1) or (p2 = q1) meaning either
1728  * the start or end vertex of pot-cut (potential cut
1729  * between hole-loopuse and non-hole-loopuse) is the
1730  * same as the 1st vertex of the current edgeuse being
1731  * tested then the corresponding vertex pointers
1732  * should also be equal, verify this is true, if not,
1733  * bomb so problem can be investigated.
1734  */
1735 
1736  if (((NEAR_ZERO(dist[0], SMALL_FASTF) && NEAR_ZERO(dist[1], SMALL_FASTF))
1737  != (vu2->v_p == eu->vu_p->v_p)) ||
1738  ((NEAR_EQUAL(dist[0], 1.0, SMALL_FASTF) && NEAR_ZERO(dist[1], SMALL_FASTF))
1739  != (vu1->v_p == eu->vu_p->v_p))) {
1740  bu_bomb("nmg_isect_lseg3_eu(): logic error possibly in 'bn_isect_lseg3_lseg3'\n");
1741  }
1742 
1743  /* True when either (p1 = q1) or (p2 = q1) or
1744  * (p1 = q2) or (p2 = q2) meaning either the start or
1745  * end vertex of pot-cut (potential cut between
1746  * hole-loopuse and non-hole-loopuse) is the same as
1747  * the 1st vertex of the current edgeuse being tested.
1748  * When this is true this is ok because we already
1749  * know of these intersections, we are testing
1750  * everywhere else for intersections.
1751  */
1752  if ((NEAR_ZERO(dist[0], SMALL_FASTF) && NEAR_ZERO(dist[1], SMALL_FASTF)) ||
1753  (NEAR_EQUAL(dist[0], 1.0, SMALL_FASTF) && NEAR_ZERO(dist[1], SMALL_FASTF)) ||
1754  (NEAR_ZERO(dist[0], SMALL_FASTF) && NEAR_EQUAL(dist[1], 1.0, SMALL_FASTF)) ||
1755  (NEAR_EQUAL(dist[0], 1.0, SMALL_FASTF) && NEAR_EQUAL(dist[1], 1.0, SMALL_FASTF))) {
1756  } else {
1757  /* Set hit true so elsewhere logic can skip this
1758  * pot-cut and try the next one.
1759  */
1760  hit = 1;
1761  }
1762  }
1763 
1764  if (hit) {
1765  /* Break from eu for-loop since a hit was found and
1766  * we need to stop testing the current pot-cut and
1767  * start testing the next.
1768  */
1769  break; /* Break from eu for-loop */
1770  }
1771  } /* End of eu for-loop */
1772 
1773  if (hit) {
1774  /* Break from lu for-loop since a hit was found and we
1775  * need to stop testing the current pot-cut and start
1776  * testing the next.
1777  */
1778  break; /* Break from lu for-loop */
1779  }
1780 
1781  } /* End of lu for-loop */
1782 
1783  return hit;
1784 }
1785 
1786 
1787 void
1788 nmg_triangulate_rm_holes(struct faceuse *fu, struct bu_list *tbl2d, const struct bn_tol *tol)
1789 {
1790  vect_t N;
1791  int hit;
1792  struct loopuse *lu1 = 0, *lu2, *lu_tmp;
1793  struct edgeuse *eu1, *eu2, *eu_tmp;
1794  struct vertexuse *vu1;
1795  struct pt2d *pt2d_cut_to = (struct pt2d *)NULL;
1796  struct pt2d *pt2d_cut_from = (struct pt2d *)NULL;
1797  static const int cut_color[3] = { 90, 255, 90};
1798  int fast_exit = 0;
1799  int holes = 0;
1800 
1801  VSETALL(N, 0);
1802 
1803  BN_CK_TOL(tol);
1804  NMG_CK_FACEUSE(fu);
1805 
1806  fast_exit = 0;
1807  holes = 0;
1808 
1809  for (BU_LIST_FOR(lu_tmp, loopuse, &fu->lu_hd)) {
1810  if (lu_tmp->orientation == OT_OPPOSITE) {
1811  holes = 1;
1812  lu1 = BU_LIST_FIRST(loopuse, &fu->lu_hd);
1813  break;
1814  }
1815  }
1816 
1817  while (holes) {
1818  NMG_CK_LOOPUSE(lu1);
1819  fast_exit = 0;
1820  if (lu1->orientation == OT_OPPOSITE) {
1821 
1822  /* Test lu1 to determine if any of the vertex is shared
1823  * with a outer loopuse.
1824  */
1825 
1826  /* Loop thru each eu of lu1 hole loopuse. */
1827  for (BU_LIST_FOR(eu1, edgeuse, &lu1->down_hd)) {
1828  for (BU_LIST_FOR(vu1, vertexuse, &eu1->vu_p->v_p->vu_hd)) {
1829  /* Ensure same faceuse */
1830  if (lu1->up.fu_p == vu1->up.eu_p->up.lu_p->up.fu_p) {
1831  if (vu1->up.eu_p->up.lu_p->orientation == OT_SAME) {
1832  /* Non-hole edgeuse */
1833  pt2d_cut_from = find_pt2d(tbl2d, vu1);
1834  /* Hole edgeuse */
1835  pt2d_cut_to = find_pt2d(tbl2d, eu1->vu_p);
1836 
1837  if ( !pt2d_cut_from || !pt2d_cut_to ) {
1838  bu_bomb("nmg_triangulate_rm_holes(): failed to find vu in tbl2d table\n");
1839  }
1840 
1841  NMG_CK_PT2D(pt2d_cut_from);
1842  NMG_CK_PT2D(pt2d_cut_to);
1843  join_mapped_loops(tbl2d, pt2d_cut_from, pt2d_cut_to, cut_color, tol);
1844  fast_exit = 1;
1845  break;
1846  }
1847  }
1848  }
1849  if (fast_exit) {
1850  break;
1851  }
1852  }
1853 
1854  if (!fast_exit) {
1855  /* Loop thru each eu of hole loopuse */
1856  for (BU_LIST_FOR(eu1, edgeuse, &lu1->down_hd)) {
1857 
1858  /* Loop thru each non-hole loopuse to create pot-cut. */
1859  for (BU_LIST_FOR(lu2, loopuse, &fu->lu_hd)) {
1860  NMG_CK_LOOPUSE(lu2);
1861  if (lu2->orientation != OT_OPPOSITE) {
1862 
1863  NMG_CK_EDGEUSE(eu1);
1864  /* Loop thru each eu of non-hole loopuse,
1865  * vu1 of pot-cut.
1866  */
1867  for (BU_LIST_FOR(eu2, edgeuse, &lu2->down_hd)) {
1868  NMG_CK_EDGEUSE(eu2);
1869  /* The pot-cut should be from non-hole
1870  * loopuse to a hole-loopuse it is
1871  * assumed that vertices are fused.
1872  */
1873 
1874  /* Test if edge is zero length, if so
1875  * skip this edge.
1876  */
1877  if (eu2->vu_p->v_p->vg_p->coord == eu1->vu_p->v_p->vg_p->coord) {
1878  continue;
1879  }
1880 
1881  /* eu1 part of hole lu */
1882  /* eu2 part of non-hole lu */
1883  hit = nmg_isect_potcut_fu(eu1, eu2, fu, tol);
1884 
1885  if (!hit) {
1886  /* perform cut */
1887  fast_exit = 1;
1888 
1889  /* p1, non-hole edgeuse */
1890  pt2d_cut_from = find_pt2d(tbl2d, eu2->vu_p);
1891  /* p2, hole edgeuse */
1892  pt2d_cut_to = find_pt2d(tbl2d, eu1->vu_p);
1893 
1894  if ( !pt2d_cut_from || !pt2d_cut_to ) {
1895  bu_bomb("nmg_triangulate_rm_holes(): failed to find vu in tbl2d table\n");
1896  }
1897 
1898  NMG_CK_PT2D(pt2d_cut_from);
1899  NMG_CK_PT2D(pt2d_cut_to);
1900  join_mapped_loops(tbl2d, pt2d_cut_from, pt2d_cut_to, cut_color, tol);
1901 
1902  if (fast_exit) {
1903  break; /* Break from eu2 */
1904  }
1905  }
1906 
1907  } /* End of for-loop eu2 traversing all
1908  * possible pot-cut v1 of current
1909  * non-hole-loopuse.
1910  */
1911 
1912  } /* End of if-statement making sure lu2 is
1913  * NOT a hole-loopuse, makes sure the start vertex
1914  * of pot-cut is on a non-hole-loopuse.
1915  */
1916 
1917  if (fast_exit) break;
1918 
1919  } /* End of lu2 for-loop. */
1920 
1921  if (fast_exit) {
1922  break;
1923  }
1924 
1925  } /* End of eu1 for-loop. */
1926  }
1927  }
1928 
1929  if (fast_exit) {
1930  lu1 = BU_LIST_FIRST(loopuse, &fu->lu_hd);
1931  } else {
1932  lu1 = BU_LIST_PNEXT_CIRC(loopuse, lu1);
1933  }
1934 
1935  holes = 0;
1936  for (BU_LIST_FOR(lu_tmp, loopuse, &fu->lu_hd)) {
1937  if (lu_tmp->orientation == OT_OPPOSITE) {
1938  holes = 1;
1939  break;
1940  }
1941  }
1942  }
1943 
1944  /* When we get to this point, all hole-loopuse should be removed
1945  * by joining them with a non-hole-loopuse, which converts them to
1946  * a non-hole-loopuse.
1947  */
1948 
1949  /* This is at the end of processing of the current hole-loopuse,
1950  * if a cut was not made for this hole-loopuse then bomb. Maybe
1951  * enhance process to create a vertex to cut into since could not
1952  * find an existing vertex.
1953  */
1954  if (0) {
1955  bu_log("nmg_triangulate_rm_holes(): hole-loopuse lu1 0x%lx no cut found\n", (unsigned long)lu1);
1956  for (BU_LIST_FOR(lu_tmp, loopuse, &fu->lu_hd)) {
1957  for (BU_LIST_FOR(eu_tmp, edgeuse, &lu_tmp->down_hd)) {
1958  bu_log("nmg_triangulate_rm_holes(): lu_p = 0x%lx lu_orient = %d fu_p = 0x%lx vu_p = 0x%lx eu_p = 0x%lx v_p = 0x%lx vg_p = 0x%lx 3D coord = %g %g %g\n",
1959  (unsigned long)lu_tmp, lu_tmp->orientation, (unsigned long)lu_tmp->up.fu_p,
1960  (unsigned long)eu_tmp->vu_p, (unsigned long)eu_tmp, (unsigned long)eu_tmp->vu_p->v_p,
1961  (unsigned long)eu_tmp->vu_p->v_p->vg_p, V3ARGS(eu_tmp->vu_p->v_p->vg_p->coord));
1962 
1963  }
1964  }
1965  bu_bomb("nmg_triangulate_rm_holes(): could not find cut for current hole-loopuse\n");
1966  }
1967 
1968 #ifdef DEBUG_TRI_P
1969  {
1970  struct model *my_m2;
1971  struct edgeuse *myeu2;
1972  lu_tmp = BU_LIST_FIRST(loopuse, &fu->lu_hd);
1973  myeu2 = BU_LIST_FIRST(edgeuse, &(lu_tmp->down_hd));
1974  nmg_plot_lu_around_eu("holes_removed", myeu2, tol);
1975 
1976  my_m2 = nmg_find_model(lu_tmp->up.magic_p);
1977  NMG_CK_MODEL(my_m2);
1978  nmg_stash_model_to_file("holes_removed.g", my_m2, "holes_removed");
1979  }
1980 #endif
1981 
1982  return;
1983 }
1984 
1985 /*
1986  * return 1 when faceuse is empty, otherwise return 0
1987  *
1988  */
1989 int
1990 nmg_triangulate_rm_degen_loopuse(struct faceuse *fu, const struct bn_tol *tol)
1991 {
1992  struct loopuse *lu;
1993  struct edgeuse *eu;
1994  int loopuse_count_tmp = 0;
1995  int edgeuse_vert_count = 0;
1996  struct loopuse *lu1, *lu_tmp;
1997  int lu_done = 0;
1998 
1999  size_t *book_keeping_array, *book_keeping_array_tmp;
2000  int book_keeping_array_alloc_cnt = 40; /* initial allocated record count */
2001  int unique_vertex_cnt = 0;
2002  int idx = 0;
2003  int done = 0;
2004  int match = 0;
2005  int killed_lu = 0;
2006  int ret = 0;
2007 
2008  BN_CK_TOL(tol);
2009  NMG_CK_FACEUSE(fu);
2010 
2011  book_keeping_array = (size_t *)bu_calloc(book_keeping_array_alloc_cnt, sizeof(size_t),
2012  "book_keeping_array");
2013 
2014  /* remove loopuse with < 3 vertices */
2015  lu_done = 0;
2016  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
2017  while (!lu_done) {
2018 
2019  if (BU_LIST_IS_HEAD(lu, &fu->lu_hd)) {
2020  lu_done = 1;
2021  } else {
2022  NMG_CK_LOOPUSE(lu);
2023  lu_tmp = lu;
2024  killed_lu = 0;
2025  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_EDGEUSE_MAGIC) {
2026  edgeuse_vert_count = 0;
2027  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
2028  NMG_CK_EDGEUSE(eu);
2029  edgeuse_vert_count++;
2030  }
2031  if (edgeuse_vert_count < 3) {
2032  nmg_klu(lu);
2033  killed_lu = 1;
2034  if (RTG.NMG_debug & DEBUG_TRI) {
2035  bu_log("nmg_triangulate_rm_degen_loopuse(): faceuse 0x%lx -- killed loopuse 0x%lx with %d vertices\n",
2036  (unsigned long)fu, (unsigned long)lu_tmp, edgeuse_vert_count);
2037  }
2038  }
2039  } else if ((BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC) &&
2040  (BU_LIST_FIRST_MAGIC(&lu->lumate_p->down_hd) == NMG_VERTEXUSE_MAGIC)) {
2041  nmg_kvu(BU_LIST_FIRST(vertexuse, &lu->down_hd));
2042  nmg_kvu(BU_LIST_FIRST(vertexuse, &lu->lumate_p->down_hd));
2043  nmg_klu(lu);
2044  killed_lu = 1;
2045  if (RTG.NMG_debug & DEBUG_TRI) {
2046  bu_log("nmg_triangulate_rm_degen_loopuse(): faceuse 0x%lx -- killed single vertex loopuse 0x%lx\n",
2047  (unsigned long)fu, (unsigned long)lu_tmp);
2048  }
2049  } else {
2050  bu_log("nmg_triangulate_rm_degen_loopuse(): faceuse 0x%lx -- unknown loopuse content\n",
2051  (unsigned long)fu);
2052  bu_bomb("nmg_triangulate_rm_degen_loopuse(): unknown loopuse content\n");
2053  }
2054 
2055  if (killed_lu) {
2056  loopuse_count_tmp = 0;
2057  for (BU_LIST_FOR(lu1, loopuse, &fu->lu_hd)) {
2058  loopuse_count_tmp++;
2059  }
2060 
2061  if (RTG.NMG_debug & DEBUG_TRI) {
2062  bu_log("nmg_triangulate_rm_degen_loopuse(): faceuse 0x%lx -- %d loopuse remain in faceuse after killing loopuse 0x%lx\n",
2063  (unsigned long)fu, loopuse_count_tmp, (unsigned long)lu_tmp);
2064  }
2065  if (loopuse_count_tmp < 1) {
2066  if (RTG.NMG_debug & DEBUG_TRI) {
2067  bu_log("nmg_triangulate_rm_degen_loopuse(): faceuse 0x%lx -- contains no loopuse\n",
2068  (unsigned long)fu);
2069  }
2070  ret = 1;
2071  goto out;
2072  }
2073 
2074  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
2075  } else {
2076  /* test for at least 3 unique vertices */
2077  unique_vertex_cnt = 0;
2078  done = 0;
2079  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
2080  while (!done) {
2081  if (BU_LIST_IS_HEAD(eu, &lu->down_hd)) {
2082  done = 1;
2083  if (unique_vertex_cnt == 0) {
2084  bu_bomb("nmg_triangulate_rm_degen_loopuse(): empty loopuse\n");
2085  }
2086  } else {
2087  NMG_CK_EDGEUSE(eu);
2088  if (unique_vertex_cnt == 0) {
2089  /* insert first record */
2090  book_keeping_array[unique_vertex_cnt] = (size_t)eu->vu_p->v_p->vg_p;
2091  unique_vertex_cnt++;
2092  } else {
2093  match = 0;
2094  for (idx = 0 ; idx < unique_vertex_cnt ; idx++) {
2095  if (book_keeping_array[idx] == (size_t)eu->vu_p->v_p->vg_p) {
2096  match = 1;
2097  {
2098  struct edgeuse *eu1;
2099  int cnt = 0;
2100  for (BU_LIST_FOR(eu1, edgeuse, &lu->down_hd)) {
2101  cnt++;
2102  bu_log("%d -- vu_p = %p vg_p = %p dup_vu_p = %p dup_vg_p = %p\n",
2103  cnt,
2104  (void *)eu1->vu_p, (void *)eu1->vu_p->v_p->vg_p,
2105  (void *)eu->vu_p, (void *)eu->vu_p->v_p->vg_p);
2106  }
2107  }
2108  bu_bomb("nmg_triangulate_rm_degen_loopuse(): found duplicate vertex\n");
2109  break;
2110  }
2111  }
2112  if (!match) {
2113  book_keeping_array[unique_vertex_cnt] = (size_t)eu->vu_p->v_p->vg_p;
2114  unique_vertex_cnt++;
2115  if (unique_vertex_cnt >= book_keeping_array_alloc_cnt) {
2116  book_keeping_array_alloc_cnt = unique_vertex_cnt;
2117  book_keeping_array_alloc_cnt += 10;
2118  book_keeping_array_tmp = (size_t *)bu_realloc((void *)book_keeping_array,
2119  book_keeping_array_alloc_cnt * sizeof(size_t),
2120  "book_keeping_array realloc");
2121  book_keeping_array = book_keeping_array_tmp;
2122  }
2123  }
2124  }
2125  }
2126  eu = BU_LIST_PNEXT(edgeuse, eu);
2127  } /* end of while-not-done loop */
2128 
2129  if (unique_vertex_cnt < 3) {
2130  nmg_klu(lu);
2131  if (RTG.NMG_debug & DEBUG_TRI) {
2132  bu_log("killed loopuse 0x%lx with %d vertices (i.e. < 3 unique vertices)\n",
2133  (unsigned long)lu_tmp, edgeuse_vert_count);
2134 
2135  }
2136  loopuse_count_tmp = 0;
2137  for (BU_LIST_FOR(lu1, loopuse, &fu->lu_hd)) {
2138  loopuse_count_tmp++;
2139  }
2140 
2141  if (RTG.NMG_debug & DEBUG_TRI) {
2142  bu_log("nmg_triangulate_rm_degen_loopuse(): %d remaining loopuse in faceuse after killing loopuse 0x%lx\n", loopuse_count_tmp, (unsigned long)lu_tmp);
2143  }
2144  if (loopuse_count_tmp < 1) {
2145  if (RTG.NMG_debug & DEBUG_TRI) {
2146  bu_log("nmg_triangulate_rm_degen_loopuse(): faceuse contains no loopuse\n");
2147  }
2148  ret = 1;
2149  goto out;
2150  }
2151 
2152  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
2153 
2154  } else {
2155  lu = BU_LIST_PNEXT(loopuse, lu);
2156  }
2157  }
2158  }
2159  }
2160 
2161 out:
2162  bu_free(book_keeping_array, "book_keeping_array");
2163  return ret;
2164 }
2165 
2166 
2167 void
2168 nmg_dump_model(struct model *m)
2169 {
2170  struct nmgregion *r;
2171  struct shell *s;
2172  struct faceuse *fu;
2173  struct loopuse *lu;
2174  struct edgeuse *eu;
2175  struct vertex_g *vg;
2176  FILE *fp;
2177  size_t r_cnt = 0;
2178  size_t s_cnt = 0;
2179  size_t fu_cnt = 0;
2180  size_t lu_cnt = 0;
2181  size_t eu_cnt = 0;
2182 
2183  if ((fp = fopen("nmg_vertex_dump.txt", "a")) == NULL) {
2184  bu_bomb("nmg_vertex_dump, open failed\n");
2185  }
2186 
2187  r_cnt = 0;
2188  for (BU_LIST_FOR(r, nmgregion, &m->r_hd)) {
2189  r_cnt++;
2190  NMG_CK_REGION(r);
2191  s_cnt = 0;
2192  for (BU_LIST_FOR(s, shell, &r->s_hd)) {
2193  s_cnt++;
2194  NMG_CK_SHELL(s);
2195  fu_cnt = 0;
2196  for (BU_LIST_FOR (fu, faceuse, &s->fu_hd)) {
2197  fu_cnt++;
2198  NMG_CK_FACEUSE(fu);
2199  lu_cnt = 0;
2200  for (BU_LIST_FOR (lu, loopuse, &fu->lu_hd)) {
2201  lu_cnt++;
2202  NMG_CK_LOOPUSE(lu);
2203  eu_cnt = 0;
2204  for (BU_LIST_FOR (eu, edgeuse, &lu->down_hd)) {
2205  eu_cnt++;
2206  NMG_CK_EDGEUSE(eu);
2207  NMG_CK_VERTEXUSE(eu->vu_p);
2208  NMG_CK_VERTEX(eu->vu_p->v_p);
2209  NMG_CK_VERTEX_G(eu->vu_p->v_p->vg_p);
2210  vg = eu->vu_p->v_p->vg_p;
2211  fprintf(fp, "%ld %ld %ld %ld %ld %g %g %g\n",
2212  (unsigned long)r_cnt,
2213  (unsigned long)s_cnt,
2214  (unsigned long)fu_cnt,
2215  (unsigned long)lu_cnt,
2216  (unsigned long)eu_cnt,
2217  V3ARGS(vg->coord));
2218  }
2219  }
2220  }
2221  }
2222  }
2223 
2224  fclose(fp);
2225  return;
2226 }
2227 
2228 
2229 HIDDEN void
2230 nmg_tri_kill_accordions(struct loopuse *lu, struct bu_list *tbl2d)
2231 {
2232  struct edgeuse *eu_curr, *eu_prev, *eu_next;
2233  struct pt2d *tmp = (struct pt2d *)NULL;
2234  int vert_cnt = 0;
2235 
2236  NMG_CK_LOOPUSE(lu);
2237 
2238  eu_curr = eu_prev = eu_next = (struct edgeuse *)NULL;
2239 
2240  if (tbl2d) {
2241  NMG_CK_TBL2D(tbl2d);
2242  }
2243 
2244  if (BU_LIST_IS_EMPTY(&lu->down_hd)) {
2245  return;
2246  }
2247 
2248  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
2249  return;
2250  }
2251 
2252  for (BU_LIST_FOR(eu_curr, edgeuse, &lu->down_hd)) {
2253  vert_cnt++;
2254  }
2255 
2256  eu_curr = BU_LIST_FIRST(edgeuse, &lu->down_hd);
2257  while (BU_LIST_NOT_HEAD(&eu_curr->l, &lu->down_hd) && vert_cnt > 2) {
2258 
2259  eu_prev = BU_LIST_PPREV_CIRC(edgeuse, &eu_curr->l);
2260  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, &eu_curr->l);
2261 
2262  if ((eu_prev->vu_p->v_p == eu_next->vu_p->v_p) && (eu_curr != eu_prev)) {
2263  if (eu_prev != eu_next) {
2264  if ((RTG.NMG_debug & DEBUG_BASIC) || (RTG.NMG_debug & DEBUG_CUTLOOP)) {
2265  bu_log("nmg_tri_kill_accordions(): killing jaunt in accordion eu's %p and %p\n",
2266  (void *)eu_curr, (void *)eu_prev);
2267  }
2268  if (tbl2d) {
2269  if ((tmp = find_pt2d(tbl2d, eu_curr->vu_p))) {
2270  tmp->vu_p = (struct vertexuse *)NULL;
2271  } else {
2272  bu_bomb("nmg_tri_kill_accordions(): could not find eu_curr->vu_p in tbl2d table (1)\n");
2273  }
2274  if ((tmp = find_pt2d(tbl2d, eu_prev->vu_p))) {
2275  tmp->vu_p = (struct vertexuse *)NULL;
2276  } else {
2277  bu_bomb("nmg_tri_kill_accordions(): could not find eu_prev->vu_p in tbl2d table\n");
2278  }
2279  }
2280  (void)nmg_keu(eu_curr);
2281  (void)nmg_keu(eu_prev);
2282  vert_cnt -= 2;
2283  } else {
2284  if ((RTG.NMG_debug & DEBUG_BASIC) || (RTG.NMG_debug & DEBUG_CUTLOOP)) {
2285  bu_log("nmg_tri_kill_accordions(): killing jaunt in accordion eu %p\n", (void *)eu_curr);
2286  }
2287  if (tbl2d) {
2288  if ((tmp = find_pt2d(tbl2d, eu_curr->vu_p))) {
2289  tmp->vu_p = (struct vertexuse *)NULL;
2290  } else {
2291  bu_bomb("nmg_tri_kill_accordions(): could not find eu_curr->vu_p in tbl2d table (2)\n");
2292  }
2293  }
2294  (void)nmg_keu(eu_curr);
2295  vert_cnt--;
2296  }
2297  eu_curr = BU_LIST_FIRST(edgeuse, &lu->down_hd);
2298  } else {
2299  eu_curr = BU_LIST_PNEXT(edgeuse, eu_curr);
2300  }
2301  }
2302 }
2303 
2304 
2305 HIDDEN void
2306 validate_tbl2d(const char *str, struct bu_list *tbl2d, struct faceuse *fu)
2307 {
2308  struct loopuse *lu = (struct loopuse *)NULL;
2309  struct edgeuse *eu = (struct edgeuse *)NULL;
2310  struct pt2d *pt = (struct pt2d *)NULL;
2311  int error_cnt = 0;
2312 
2313  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
2314  NMG_CK_LOOPUSE(lu);
2315 
2316  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
2317  continue;
2318  }
2319 
2320  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
2321  NMG_CK_EDGEUSE(eu);
2322  if (!(pt = find_pt2d(tbl2d, eu->vu_p))) {
2323  error_cnt++;
2324  bu_log("validate_tbl2d(): %d: fu = %p fu_orient = %d lu = %p lu_orient = %d missing vu = %p coord = %f %f %f \n",
2325  error_cnt,
2326  (void *)fu, fu->orientation,
2327  (void *)lu, lu->orientation,
2328  (void *)eu->vu_p, V3ARGS(eu->vu_p->v_p->vg_p->coord));
2329  } else {
2330  NMG_CK_VERTEXUSE(pt->vu_p);
2331  NMG_CK_VERTEX(pt->vu_p->v_p);
2332  NMG_CK_VERTEX_G(pt->vu_p->v_p->vg_p);
2333  NMG_CK_EDGEUSE(pt->vu_p->up.eu_p);
2334  NMG_CK_LOOPUSE(pt->vu_p->up.eu_p->up.lu_p);
2335  NMG_CK_FACEUSE(pt->vu_p->up.eu_p->up.lu_p->up.fu_p);
2336  }
2337  }
2338  }
2339  if (error_cnt != 0) {
2340  bu_log("validate_tbl2d(): %s\n", str);
2341  bu_bomb("validate_tbl2d(): missing entries in tbl2d table\n");
2342  }
2343 }
2344 
2345 
2346 /**
2347  * Given a unimonotone loopuse, triangulate it into multiple loopuses
2348  */
2349 HIDDEN void
2350 cut_unimonotone(struct bu_list *tbl2d, struct loopuse *lu, const struct bn_tol *tol)
2351 {
2352  int verts = 0;
2353  int excess_loop_count = 0;
2354  int loop_count = 0;
2355  int status;
2356  int ccw_result;
2357  int tmp_vert_cnt = 0;
2358 
2359  /* boolean variables */
2360  int inside_triangle = 0;
2361  int isect_vertex = 0;
2362 
2363  vect_t fu_normal;
2364  vect_t v0, v1, v2;
2365  fastf_t dot00, dot01, dot02, dot11, dot12;
2366  fastf_t invDenom, u, v;
2367  fastf_t dist;
2368 
2369  struct pt2d *min, *max, *newpt, *first, *prev, *next, *current, *tmp;
2370  struct pt2d *prev_orig, *next_orig, *pt, *t;
2371 
2372  struct model *m;
2373  struct faceuse *fu;
2374  struct loopuse *lu2, *orig_lu_p;
2375  struct edgeuse *eu;
2376  struct vertex_g *prev_vg_p = NULL;
2377 
2378  static const int cut_color[3] = { 90, 255, 90};
2379 
2380  if (RTG.NMG_debug & DEBUG_TRI) {
2381  bu_log("cutting unimonotone:\n");
2382  }
2383 
2384  NMG_CK_TBL2D(tbl2d);
2385  BN_CK_TOL(tol);
2386  NMG_CK_LOOPUSE(lu);
2387 
2388  min = max = newpt = first = prev = next = current = (struct pt2d *)NULL;
2389  prev_orig = next_orig = pt = t = tmp = (struct pt2d *)NULL;
2390 
2391  orig_lu_p = lu;
2392 
2393  if (RTG.NMG_debug & DEBUG_TRI) {
2394  validate_tbl2d("start of function cut_unimonotone()", tbl2d, lu->up.fu_p);
2395  }
2396 
2397  /* find min/max points & count vertex points */
2398  verts = 0;
2399  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
2400  NMG_CK_EDGEUSE(eu);
2401  newpt = find_pt2d(tbl2d, eu->vu_p);
2402  if (!newpt) {
2403  bu_log("cut_unimonotone(): can not find a 2D point for %g %g %g\n",
2404  V3ARGS(eu->vu_p->v_p->vg_p->coord));
2405  bu_bomb("cut_unimonotone(): can not find a 2D point\n");
2406  }
2407 
2408  if (RTG.NMG_debug & DEBUG_TRI) {
2409  bu_log("%g %g\n", newpt->coord[X], newpt->coord[Y]);
2410  }
2411 
2412  if (!min || P_LT_V(newpt, min)) {
2413  min = newpt;
2414  }
2415  if (!max || P_GT_V(newpt, max)) {
2416  max = newpt;
2417  }
2418  verts++;
2419  }
2420 
2421  first = max;
2422 
2423  if (RTG.NMG_debug & DEBUG_TRI) {
2424  bu_log("cut_unimonotone(): %d verts, min: %g %g max: %g %g first:%g %g %p\n", verts,
2425  min->coord[X], min->coord[Y], max->coord[X], max->coord[Y],
2426  first->coord[X], first->coord[Y], (void *)first);
2427  }
2428 
2429  excess_loop_count = verts * verts;
2430  current = PT2D_NEXT(tbl2d, first);
2431  while (verts > 3) {
2432  loop_count++;
2433  if (loop_count > excess_loop_count) {
2434  if (RTG.NMG_debug & DEBUG_TRI) {
2435  eu = BU_LIST_FIRST(edgeuse, &(current->vu_p->up.eu_p->up.lu_p->down_hd));
2436  nmg_plot_lu_around_eu("cut_unimonotone_infinite_loopuse", eu, tol);
2437  m = nmg_find_model(current->vu_p->up.eu_p->up.lu_p->up.magic_p);
2438  nmg_stash_model_to_file("cut_unimonotone_infinite_model.g", m, "cut_unimonotone_infinite_model");
2439  nmg_pr_lu(current->vu_p->up.eu_p->up.lu_p, "cut_unimonotone_loopuse");
2440  nmg_plot_fu("cut_unimonotone_infinite_loopuse", current->vu_p->up.eu_p->up.lu_p->up.fu_p, tol);
2441  }
2442  bu_log("cut_unimonotone(): infinite loop %p\n", (void *)current->vu_p->up.eu_p->up.lu_p);
2443  bu_bomb("cut_unimonotone(): infinite loop\n");
2444  }
2445 
2446  prev = PT2D_PREV(tbl2d, current);
2447  next = PT2D_NEXT(tbl2d, current);
2448 
2449  VSETALL(v0, 0.0);
2450  VSETALL(v1, 0.0);
2451  VSETALL(v2, 0.0);
2452  dot00 = dot01 = dot02 = dot11 = dot12 = 0.0;
2453  invDenom = u = v = 0.0;
2454  prev_vg_p = (struct vertex_g *)NULL;
2455 
2456  /* test if any of the loopuse vertices are within the triangle
2457  * to be created. it is assumed none of the loopuse within the
2458  * faceuse intersects any of the other loopuse with the exception
2459  * of having a common edge or vertex
2460  */
2461  inside_triangle = 0;
2462  for (BU_LIST_FOR(pt, pt2d, tbl2d)) {
2463 
2464  if (inside_triangle) {
2465  break;
2466  }
2467 
2468  if (pt->vu_p == (struct vertexuse *)NULL) {
2469  /* skip tbl2d entries with a null vertexuse */
2470  continue;
2471  }
2472 
2473  if (pt->vu_p->up.eu_p == (struct edgeuse *)NULL) {
2474  /* skip tbl2d entries with a null edgeuse */
2475  continue;
2476  }
2477 
2478  NMG_CK_EDGEUSE(pt->vu_p->up.eu_p);
2479  NMG_CK_LOOPUSE(pt->vu_p->up.eu_p->up.lu_p);
2480 
2481  if (pt->vu_p->up.eu_p->up.lu_p == current->vu_p->up.eu_p->up.lu_p) {
2482  /* true when the vertexuse to be tested is in the
2483  * same loopuse as the potential cut
2484  */
2485 
2486  /* skips processing the same vertex */
2487  if (prev_vg_p != pt->vu_p->v_p->vg_p) {
2488  VSUB2(v0, next->coord, prev->coord);
2489  VSUB2(v1, current->coord, prev->coord);
2490  VSUB2(v2, pt->coord, prev->coord);
2491  dot00 = VDOT(v0, v0);
2492  dot01 = VDOT(v0, v1);
2493  dot02 = VDOT(v0, v2);
2494  dot11 = VDOT(v1, v1);
2495  dot12 = VDOT(v1, v2);
2496  invDenom = 1.0 / (dot00 * dot11 - dot01 * dot01);
2497  u = (dot11 * dot02 - dot01 * dot12) * invDenom;
2498  v = (dot00 * dot12 - dot01 * dot02) * invDenom;
2499 
2500  if ((u > SMALL_FASTF) && (v > SMALL_FASTF) && ((u + v) < (1.0 - SMALL_FASTF))) {
2501  /* true if point inside triangle */
2502  if (RTG.NMG_debug & DEBUG_TRI) {
2503  bu_log("cut_unimonotone(): point inside triangle, lu_p = %p, point = %g %g %g\n",
2504  (void *)lu, V3ARGS(pt->vu_p->v_p->vg_p->coord));
2505  }
2506  inside_triangle = 1;
2507  } else {
2508  if (RTG.NMG_debug & DEBUG_TRI) {
2509  bu_log("cut_unimonotone(): outside triangle, lu_p = %p, 3Dprev = %g %g %g 3Dcurr = %g %g %g 3Dnext = %g %g %g 3Dpoint = %g %g %g is_convex = %d\n",
2510  (void *)lu, V3ARGS(prev->vu_p->v_p->vg_p->coord),
2511  V3ARGS(current->vu_p->v_p->vg_p->coord),
2512  V3ARGS(next->vu_p->v_p->vg_p->coord),
2513  V3ARGS(pt->vu_p->v_p->vg_p->coord),
2514  is_convex(prev, current, next, tol));
2515  }
2516  }
2517  }
2518  prev_vg_p = pt->vu_p->v_p->vg_p;
2519  } /* end of if-statement to skip testing vertices not in the current loopuse */
2520  }
2521 
2522  /* test if the potential cut would intersect a vertex which
2523  * would not belong to the resulting triangle to be created
2524  * by the cut
2525  */
2526  isect_vertex = 0;
2527  for (BU_LIST_FOR(eu, edgeuse, &next->vu_p->up.eu_p->up.lu_p->down_hd)) {
2528 
2529  if (isect_vertex) {
2530  break;
2531  }
2532 
2533  if ((prev->vu_p->v_p != eu->vu_p->v_p) &&
2534  (current->vu_p->v_p != eu->vu_p->v_p) &&
2535  (next->vu_p->v_p != eu->vu_p->v_p)) {
2536  /* true when the vertex tested would not belong to
2537  * the resulting triangle
2538  */
2539  status = bn_isect_pt_lseg(&dist, prev->vu_p->v_p->vg_p->coord,
2540  next->vu_p->v_p->vg_p->coord,
2541  eu->vu_p->v_p->vg_p->coord, tol);
2542  if (status == 3) {
2543  /* true when the potential cut intersects a vertex */
2544  isect_vertex = 1;
2545  if (RTG.NMG_debug & DEBUG_TRI) {
2546  bu_log("cut_unimonotone(): cut prev %g %g %g -> next %g %g %g point = %g %g %g\n",
2547  V3ARGS(prev->vu_p->v_p->vg_p->coord),
2548  V3ARGS(next->vu_p->v_p->vg_p->coord),
2549  V3ARGS(eu->vu_p->v_p->vg_p->coord));
2550  bu_log("cut_unimonotone(): cut and vertex intersect\n");
2551  }
2552  }
2553  }
2554  }
2555 
2556  if (is_convex(prev, current, next, tol) && !inside_triangle && !isect_vertex) {
2557  /* true if the angle is convex and there are no vertices
2558  * from this loopuse within the triangle to be created
2559  * and the potential cut does not intersect any vertices,
2560  * from this loopuse, which are not part of the triangle
2561  * to be created. convex here is between 0 and 180 degrees
2562  * including 0 and 180.
2563  */
2564  if (RTG.NMG_debug & DEBUG_TRI) {
2565  bu_log("cut_unimonotone(): before cut loop:\n");
2566  nmg_pr_fu_briefly(lu->up.fu_p, "");
2567  }
2568 
2569  if (RTG.NMG_debug & DEBUG_TRI) {
2570  bu_log("cut_unimonotone(): before cut orig_lu_p = %p prev lu_p = %p 3D %g %g %g curr lu_p = %p 3D %g %g %g next lu_p = %p 3D %g %g %g\n",
2571  (void *)orig_lu_p, (void *)prev->vu_p->up.eu_p->up.lu_p,
2572  V3ARGS(prev->vu_p->v_p->vg_p->coord),
2573  (void *)current->vu_p->up.eu_p->up.lu_p,
2574  V3ARGS(current->vu_p->v_p->vg_p->coord),
2575  (void *)next->vu_p->up.eu_p->up.lu_p,
2576  V3ARGS(next->vu_p->v_p->vg_p->coord));
2577  }
2578 
2579 
2580  if (next->vu_p == prev->vu_p) {
2581  bu_bomb("cut_unimonotone(): trying to cut to/from same vertexuse\n");
2582  }
2583 
2584  if (RTG.NMG_debug & DEBUG_TRI) {
2585  validate_tbl2d("before cut_unimonotone -- cut_mapped_loop",
2586  tbl2d, current->vu_p->up.eu_p->up.lu_p->up.fu_p);
2587  }
2588 
2589  prev_orig = prev;
2590  next_orig = next;
2591 
2592  /* cut a triangular piece off of the loop to create a new loop */
2593  current = cut_mapped_loop(tbl2d, next, prev, cut_color, tol, 0);
2594 
2595  prev = prev_orig;
2596  next = next_orig;
2597 
2598  if (!current) {
2599  bu_bomb("cut_unimonotone(): function cut_mapped_loop returned null\n");
2600  }
2601  if (current == next) {
2602  bu_bomb("cut_unimonotone(): current == next\n");
2603  }
2604 
2605  if (RTG.NMG_debug & DEBUG_TRI) {
2606  validate_tbl2d("after cut_unimonotone -- cut_mapped_loop",
2607  tbl2d, current->vu_p->up.eu_p->up.lu_p->up.fu_p);
2608  }
2609 
2610  if (BU_LIST_FIRST_MAGIC(&next->vu_p->up.eu_p->up.lu_p->down_hd) != NMG_EDGEUSE_MAGIC) {
2611  bu_bomb("cut_unimonotone(): next loopuse contains no edgeuse\n");
2612  }
2613 
2614  /* check direction (cw/ccw) of loopuse after cut */
2615  NMG_GET_FU_NORMAL(fu_normal, next->vu_p->up.eu_p->up.lu_p->up.fu_p);
2616  ccw_result = nmg_loop_is_ccw(next->vu_p->up.eu_p->up.lu_p, fu_normal, tol);
2617 
2618  if (ccw_result == 0) {
2619  /* true if could not determine direction */
2620 
2621  /* need to save the lu pointer since the vu pointer
2622  * may become invalid after nmg_tri_kill_accordions
2623  * removes the accordions
2624  */
2625  lu2 = next->vu_p->up.eu_p->up.lu_p;
2626 
2627  if (RTG.NMG_debug & DEBUG_TRI) {
2628  validate_tbl2d("cut_unimonotone() before nmg_tri_kill_accordions",
2629  tbl2d, lu2->up.fu_p);
2630  }
2631 
2632  nmg_tri_kill_accordions(lu2, tbl2d);
2633 
2634  if (BU_LIST_FIRST_MAGIC(&lu2->down_hd) != NMG_EDGEUSE_MAGIC) {
2635  bu_bomb("cut_unimonotone(): after nmg_tri_kill_accordions, loopuse has no edgeuse\n");
2636  }
2637 
2638  if (RTG.NMG_debug & DEBUG_TRI) {
2639  validate_tbl2d("cut_unimonotone() after nmg_tri_kill_accordions",
2640  tbl2d, lu2->up.fu_p);
2641  }
2642 
2643  NMG_CK_LOOPUSE(lu2);
2644  /* find the pt2d table entry for the first vu within
2645  * the resulting lu
2646  */
2647  eu = BU_LIST_FIRST(edgeuse, &lu2->down_hd);
2648  if (!(next = find_pt2d(tbl2d, eu->vu_p))) {
2649  bu_bomb("cut_unimonotone(): unable to find next vertexuse\n");
2650  }
2651 
2652  /* count the number of vertexuse in the 'next' loopuse */
2653  for (BU_LIST_FOR(eu, edgeuse, &next->vu_p->up.eu_p->up.lu_p->down_hd)) {
2654  tmp_vert_cnt++;
2655  }
2656 
2657  /* set the vertexuse counter (i.e. verts) to the current
2658  * number of vertexuse in the loopuse. this is needed
2659  * since nmg_tri_kill_accordions, if it kills any
2660  * accordions in the loopuse, will reduce the number of
2661  * vertexuse in the loopuse
2662  */
2663  verts = tmp_vert_cnt;
2664 
2665  if (verts > 3) {
2666  bu_bomb("cut_unimonotone(): can not determine loopuse cw/ccw and loopuse contains > 3 vertices\n");
2667  }
2668 
2669  } else if (ccw_result == -1) {
2670  /* true if the loopuse has a cw rotation */
2671  bu_log("cut_unimonotone(): after cut_mapped_loop, next loopuse was cw.\n");
2672 
2673  if (RTG.NMG_debug & DEBUG_TRI) {
2674  validate_tbl2d("cut_unimonotone() before flip direction",
2675  tbl2d, next->vu_p->up.eu_p->up.lu_p->up.fu_p);
2676  }
2677  fu = next->vu_p->up.eu_p->up.lu_p->up.fu_p;
2678  lu2 = next->vu_p->up.eu_p->up.lu_p;
2679 
2680  NMG_CK_LOOPUSE(lu2);
2681  NMG_CK_FACEUSE(fu);
2682  if (*lu2->up.magic_p == NMG_FACEUSE_MAGIC) {
2683  /* loop is in wrong direction, exchange lu and lu_mate */
2684  BU_LIST_DEQUEUE(&lu2->l);
2685  BU_LIST_DEQUEUE(&lu2->lumate_p->l);
2686  BU_LIST_APPEND(&fu->lu_hd, &lu2->lumate_p->l);
2687  lu2->lumate_p->up.fu_p = fu;
2688  BU_LIST_APPEND(&fu->fumate_p->lu_hd, &lu2->l);
2689  lu2->up.fu_p = fu->fumate_p;
2690  } else if (*lu2->up.magic_p == NMG_SHELL_MAGIC) {
2691  bu_bomb("cut_unimonotone(): loopuse parent is shell\n");
2692  } else {
2693  bu_bomb("cut_unimonotone(): loopuse parent is unknown\n");
2694  }
2695 
2696  /* add the new vertexuse to the pt2d table. these new
2697  * vertexuse are from loopuse-mate before the switch.
2698  */
2699  lu2 = BU_LIST_FIRST(loopuse, &fu->lu_hd);
2700 
2701  for (BU_LIST_FOR(eu, edgeuse, &lu2->down_hd)) {
2702  NMG_CK_EDGEUSE(eu);
2703  map_new_vertexuse(tbl2d, eu->vu_p);
2704  if (RTG.NMG_debug & DEBUG_TRI) {
2705  tmp = find_pt2d(tbl2d, eu->vu_p);
2706  if (!(tmp)) {
2707  bu_bomb("cut_unimonotone(): vertexuse not added to tbl2d table\n");
2708  }
2709  }
2710  }
2711 
2712  eu = BU_LIST_FIRST(edgeuse, &lu2->down_hd);
2713  if (!(next = find_pt2d(tbl2d, eu->vu_p))) {
2714  bu_bomb("cut_unimonotone(): unable to find next vertexuse in tbl2d table\n");
2715  }
2716 
2717  /* make sure loopuse orientation is marked OT_SAME */
2718  nmg_set_lu_orientation(lu2, 0);
2719 
2720  current = PT2D_PREV(tbl2d, next);
2721  prev = PT2D_PREV(tbl2d, current);
2722 
2723  orig_lu_p = next->vu_p->up.eu_p->up.lu_p;
2724 
2725  if (RTG.NMG_debug & DEBUG_TRI) {
2726  validate_tbl2d("cut_unimonotone() after flip direction",
2727  tbl2d, next->vu_p->up.eu_p->up.lu_p->up.fu_p);
2728  }
2729  } else if (ccw_result == 1) {
2730  /* make sure loopuse orientation is marked OT_SAME */
2731  nmg_set_lu_orientation(next->vu_p->up.eu_p->up.lu_p, 0);
2732  } else {
2733  bu_bomb("cut_unimonotone(): function 'nmg_loop_is_ccw' returned an invalid result\n");
2734  }
2735 
2736  if (RTG.NMG_debug & DEBUG_TRI) {
2737  bu_log("cut_unimonotone(): after cut orig_lu_p = %p lu_p = %p 3D %g %g %g --> lu_p = %p 3D %g %g %g\n",
2738  (void *)orig_lu_p, (void *)prev->vu_p->up.eu_p->up.lu_p,
2739  V3ARGS(prev->vu_p->v_p->vg_p->coord),
2740  (void *)next->vu_p->up.eu_p->up.lu_p,
2741  V3ARGS(next->vu_p->v_p->vg_p->coord));
2742  }
2743 
2744  if (orig_lu_p != next->vu_p->up.eu_p->up.lu_p) {
2745  bu_bomb("cut_unimonotone(): next loopuse to cut is not the original loopuse\n");
2746  }
2747 
2748  if (RTG.NMG_debug & DEBUG_TRI) {
2749  bu_log("cut_unimonotone(): after cut loop:\n");
2750  nmg_pr_fu_briefly(lu->up.fu_p, "");
2751  }
2752  if (next->vu_p->v_p == prev->vu_p->v_p) {
2753  /* the vert count must be decremented 2 when
2754  * the cut was between the same vertex
2755  */
2756  verts -= 2;
2757  } else {
2758  verts--;
2759  }
2760 
2761  NMG_CK_LOOPUSE(lu);
2762 
2763  if (RTG.NMG_debug & DEBUG_TRI) {
2764  nmg_tri_plfu(lu->up.fu_p, tbl2d);
2765  }
2766 
2767  if (current->vu_p == first->vu_p) {
2768  t = PT2D_NEXT(tbl2d, first);
2769  if (RTG.NMG_debug & DEBUG_TRI) {
2770  bu_log("cut_unimonotone(): first(%p -> %g %g\n",
2771  (void *)first, t->coord[X], t->coord[Y]);
2772  }
2773 
2774  t = PT2D_NEXT(tbl2d, current);
2775  if (RTG.NMG_debug & DEBUG_TRI) {
2776  bu_log("cut_unimonotone(): current(%p) -> %g %g\n",
2777  (void *)current, t->coord[X], t->coord[Y]);
2778  }
2779 
2780  current = PT2D_NEXT(tbl2d, current);
2781  if (RTG.NMG_debug & DEBUG_TRI) {
2782  bu_log("cut_unimonotone(): current(%p) -> %g %g\n",
2783  (void *)current, t->coord[X], t->coord[Y]);
2784  }
2785  }
2786  } else {
2787  if (RTG.NMG_debug & DEBUG_TRI) {
2788  bu_log("cut_unimonotone(): not-cut orig_lu_p = %p lu_p = %p 3D %g %g %g --> lu_p = %p 3D %g %g %g\n",
2789  (void *)orig_lu_p, (void *)prev->vu_p->up.eu_p->up.lu_p,
2790  V3ARGS(prev->vu_p->v_p->vg_p->coord),
2791  (void *)next->vu_p->up.eu_p->up.lu_p,
2792  V3ARGS(next->vu_p->v_p->vg_p->coord));
2793  }
2794 
2795  if (RTG.NMG_debug & DEBUG_TRI) {
2796  bu_log("cut_unimonotone(): cut not performed, moving to next potential cut\n");
2797  }
2798  current = next;
2799  }
2800  }
2801 }
2802 
2803 
2804 void
2805 print_loopuse_tree(struct bu_list *head, struct loopuse_tree_node *parent, const struct bn_tol *tol)
2806 {
2807  struct loopuse_tree_node *node, *node_first;
2808  struct bu_vls plot_file_desc = BU_VLS_INIT_ZERO;
2809 
2810  if (head->magic != BU_LIST_HEAD_MAGIC) {
2811  bu_bomb("print_loopuse_tree(): head not bu_list head\n");
2812  }
2813 
2814  if (BU_LIST_IS_EMPTY(head)) {
2815  bu_bomb("print_loopuse_tree(): empty bu_list\n");
2816  }
2817 
2818  node_first = BU_LIST_FIRST(loopuse_tree_node, head);
2819  NMG_CK_LOOPUSE(node_first->lu);
2820 
2821  bu_vls_sprintf(&plot_file_desc, "parent_%p_", (void *)parent);
2822  nmg_plot_fu(bu_vls_addr(&plot_file_desc), node_first->lu->up.fu_p, tol);
2823  bu_vls_free(&plot_file_desc);
2824 
2825  for (BU_LIST_FOR(node, loopuse_tree_node, head)) {
2826  bu_log("print_loopuse_tree() parent ptr %p head ptr = %p siblings node %p lu %p %d child_hd ptr %p\n",
2827  (void *)parent, (void *)head, (void *)node, (void *)node->lu, node->lu->orientation,
2828  (void *)&(node->children_hd));
2829  if (BU_LIST_NON_EMPTY(&(node->children_hd))) {
2830  print_loopuse_tree(&(node->children_hd), node, tol);
2831  }
2832  }
2833 }
2834 
2835 int
2836 nmg_classify_pt_loop_new(const struct vertex *line1_pt1_v_ptr, const struct loopuse *lu, const struct bn_tol *tol)
2837 {
2838  struct edgeuse *eu1, *eu2;
2839  int status;
2840  int hit_cnt = 0;
2841  int in_cnt = 0;
2842  int out_cnt = 0;
2843  int on_cnt = 0;
2844  int done = 0;
2845  double angle1 = 0;
2846  plane_t N = HINIT_ZERO;
2847  vect_t x_dir = VINIT_ZERO;
2848  vect_t y_dir = VINIT_ZERO;
2849  vect_t vec1 = VINIT_ZERO;
2850  vect_t vec2 = VINIT_ZERO;
2851  vect_t line1_dir = VINIT_ZERO;
2852  vect_t line2_dir = VINIT_ZERO;
2853  fastf_t *line1_pt1, *line1_pt2, *line2_pt1, *line2_pt2;
2854  fastf_t line1_dist = 0.0;
2855  fastf_t line2_dist = 0.0;
2856  fastf_t vec2_mag = 0.0;
2857 
2858  vect_t min_pt = {MAX_FASTF, MAX_FASTF, MAX_FASTF};
2859  vect_t max_pt = {-MAX_FASTF, -MAX_FASTF, -MAX_FASTF};
2860 
2861  bu_log("\nnmg_classify_pt_loop_new(): START ==========================================\n\n");
2862 
2863  line1_pt1 = line1_pt1_v_ptr->vg_p->coord;
2864  NMG_CK_LOOPUSE(lu);
2865 
2866  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
2867  bu_bomb("nmg_classify_pt_loop_new(): loopuse contains no edgeuse\n");
2868  }
2869 
2870 
2871  for (BU_LIST_FOR(eu1, edgeuse, &lu->down_hd)) {
2872  NMG_CK_EDGEUSE(eu1);
2873  if (eu1->vu_p->v_p->vg_p->coord[X] > max_pt[X]) {
2874  max_pt[X] = eu1->vu_p->v_p->vg_p->coord[X];
2875  }
2876  if (eu1->vu_p->v_p->vg_p->coord[Y] > max_pt[Y]) {
2877  max_pt[Y] = eu1->vu_p->v_p->vg_p->coord[Y];
2878  }
2879  if (eu1->vu_p->v_p->vg_p->coord[Z] > max_pt[Z]) {
2880  max_pt[Z] = eu1->vu_p->v_p->vg_p->coord[Z];
2881  }
2882  if (eu1->vu_p->v_p->vg_p->coord[X] < min_pt[X]) {
2883  min_pt[X] = eu1->vu_p->v_p->vg_p->coord[X];
2884  }
2885  if (eu1->vu_p->v_p->vg_p->coord[Y] < min_pt[Y]) {
2886  min_pt[Y] = eu1->vu_p->v_p->vg_p->coord[Y];
2887  }
2888  if (eu1->vu_p->v_p->vg_p->coord[Z] < min_pt[Z]) {
2889  min_pt[Z] = eu1->vu_p->v_p->vg_p->coord[Z];
2890  }
2891  }
2892 
2893  if (V3PT_OUT_RPP_TOL(line1_pt1, min_pt, max_pt, tol->dist)) {
2894  /* True when the point is outside the loopuse bounding box.
2895  * Considering distance tolerance, the point is also not on
2896  * the bounding box and therefore the point can not be on the
2897  * loopuse.
2898  */
2899  bu_log("pt = %g %g %g min_pt = %g %g %g max_pt = %g %g %g\n",
2900  V3ARGS(line1_pt1), V3ARGS(min_pt), V3ARGS(max_pt));
2901  bu_log("nmg_classify_pt_loop_new(): pt outside loopuse bb\n");
2902  bu_log("\nnmg_classify_pt_loop_new(): END ==========================================\n\n");
2903  return NMG_CLASS_AoutB;
2904  }
2905 
2906  for (BU_LIST_FOR(eu1, edgeuse, &lu->down_hd)) {
2907  NMG_CK_EDGEUSE(eu1);
2908  if (eu1->vu_p->v_p == line1_pt1_v_ptr) {
2909  bu_log("nmg_classify_pt_loop_new(): pt %g %g %g is same as a loopuse vertex\n",
2910  V3ARGS(eu1->vu_p->v_p->vg_p->coord));
2911  bu_log("\nnmg_classify_pt_loop_new(): END ==========================================\n\n");
2912  return NMG_CLASS_AonBshared;
2913  } else {
2914  if (bn_pt3_pt3_equal(eu1->vu_p->v_p->vg_p->coord, line1_pt1_v_ptr->vg_p->coord, tol)) {
2915  bu_bomb("nmg_classify_pt_loop_new(): found unfused vertex\n");
2916  }
2917  }
2918  }
2919 
2920  NMG_GET_FU_NORMAL(N, lu->up.fu_p);
2921 
2922  for (BU_LIST_FOR(eu1, edgeuse, &lu->down_hd)) {
2923  NMG_CK_EDGEUSE(eu1);
2924  if (eu1->eumate_p->vu_p->v_p->vg_p == eu1->vu_p->v_p->vg_p) {
2925  bu_bomb("nmg_classify_pt_loop_new(): zero length edge\n");
2926  } else if (bn_pt3_pt3_equal(eu1->eumate_p->vu_p->v_p->vg_p->coord, eu1->vu_p->v_p->vg_p->coord, tol)) {
2927  bu_bomb("nmg_classify_pt_loop_new(): found unfused vertex, zero length edge\n");
2928  }
2929 
2930  line1_pt2 = eu1->vu_p->v_p->vg_p->coord;
2931  VSUB2(line1_dir, line1_pt2, line1_pt1);
2932 
2933  hit_cnt = 0;
2934  done = 0;
2935  eu2 = BU_LIST_FIRST(edgeuse, &lu->down_hd);
2936  while (!done) {
2937  if (BU_LIST_IS_HEAD(eu2, &lu->down_hd)) {
2938  done = 1;
2939  } else {
2940  line2_pt1 = eu2->vu_p->v_p->vg_p->coord;
2941  line2_pt2 = eu2->eumate_p->vu_p->v_p->vg_p->coord;
2942  VSUB2(line2_dir, line2_pt2, line2_pt1);
2943 
2944  status = bn_isect_line3_line3(&line1_dist, &line2_dist,
2945  line1_pt1, line1_dir, line2_pt1, line2_dir, tol);
2946 
2947  if ( status == 1 ) {
2948  int on_vertex = 0;
2949  VSUB2(vec2, line2_pt2, line2_pt1);
2950  vec2_mag = MAGNITUDE(vec2);
2951  if ((line1_dist > -(tol->dist)) && (line2_dist > -(tol->dist)) &&
2952  (line2_dist < (vec2_mag + tol->dist))) {
2953  /* true when intercept is on the ray and on the edgeuse */
2954 
2955  if (NEAR_ZERO(line1_dist, tol->dist)) {
2956  /* true when start point of ray is within distance tolerance of edgeuse */
2957  bu_log("normal intercept, pt on loopuse but not vertexuse, lu_ptr = %p pt = %g %g %g line1_dist = %g line2_dist = %g edgeuse pt1 %g %g %g pt2 %g %g %g\n",
2958  (void *)lu, V3ARGS(line1_pt1), line1_dist, line2_dist, V3ARGS(line2_pt1), V3ARGS(line2_pt2));
2959  bu_bomb("normal intercept, pt on loopuse but not vertexuse\n");
2960  return NMG_CLASS_AonBshared;
2961  }
2962 
2963  if (NEAR_ZERO(line2_dist, tol->dist)) {
2964  /* true when hit is on 1st vertex of edgeuse */
2965  VSUB2(x_dir, line2_pt1, line1_pt1);
2966  VCROSS(y_dir, N, x_dir);
2967  VSUB2(vec1, line2_pt2, line1_pt1);
2968  angle1 = bn_angle_measure(vec1, x_dir, y_dir);
2969  on_vertex = 1;
2970  }
2971 
2972  if (NEAR_ZERO(line2_dist - vec2_mag, tol->dist)) {
2973  /* true when hit is on 2st vertex of edgeuse */
2974  VSUB2(x_dir, line2_pt2, line1_pt1);
2975  VCROSS(y_dir, N, x_dir);
2976  VSUB2(vec1, line2_pt1, line1_pt1);
2977  angle1 = bn_angle_measure(vec1, x_dir, y_dir);
2978  on_vertex = 1;
2979  }
2980 
2981  if (on_vertex) {
2982  if (angle1 > M_PI) {
2983  /* count hit only when non-hit vertex of edgeuse lies below ray */
2984  bu_log("hit-on-edgeuse-vertex ... ray = %g %g %g -> %g %g %g edge = %g %g %g -> %g %g %g edge lu_ptr = %p ang1 = %g vec1 = %g %g %g N = %g %g %g %g, x_dir = %g %g %g y_dir = %g %g %g\n",
2985  V3ARGS(line1_pt1), V3ARGS(line1_pt2), V3ARGS(line2_pt1),
2986  V3ARGS(line2_pt2), (void *)lu, angle1, V3ARGS(vec1), V4ARGS(N),
2987  V3ARGS(x_dir), V3ARGS(y_dir));
2988  hit_cnt++;
2989  }
2990  } else {
2991  bu_log("hit-on-edgeuse-non-vertex ray = %g %g %g -> %g %g %g edge = %g %g %g -> %g %g %g edge lu_ptr = %p N = %g %g %g %g\n",
2992  V3ARGS(line1_pt1), V3ARGS(line1_pt2), V3ARGS(line2_pt1),
2993  V3ARGS(line2_pt2), (void *)lu, V4ARGS(N));
2994  hit_cnt++;
2995  }
2996  }
2997  eu2 = BU_LIST_PNEXT(edgeuse, eu2);
2998  }
2999 
3000  if (status == 0) {
3001  bu_log("nmg_classify_pt_loop_new(): co-linear, ray = %g %g %g -> %g %g %g edge = %g %g %g -> %g %g %g lu_ptr = %p line1_dist = %g line2_dist = %g\n",
3002  V3ARGS(line1_pt1), V3ARGS(line1_pt2), V3ARGS(line2_pt1),
3003  V3ARGS(line2_pt2), (void *)lu, line1_dist, line2_dist);
3004  VSUB2(line1_dir, line1_pt2, line1_pt1);
3005  VSUB2(line2_dir, line2_pt2, line2_pt1);
3006 
3007  /* test if ray start point is on edgeuse */
3008  if (((line1_dist > SMALL_FASTF) && (line2_dist < -SMALL_FASTF)) ||
3009  ((line1_dist < -SMALL_FASTF) && (line2_dist > SMALL_FASTF))) {
3010  /* true when the sign of the two distances are opposite */
3011  /* if the point was on one of the loopuse vertices, it would
3012  * have been determined in the earlier logic. no need to
3013  * consider any of the in/out results because they are
3014  * inconclusive if the point is on the edgeuse.
3015  */
3016 
3017  bu_log("co-linear, pt on loopuse but not vertexuse, lu_ptr = %p pt = %g %g %g line1_dist = %g line2_dist = %g edgeuse pt1 %g %g %g pt2 %g %g %g\n",
3018  (void *)lu, V3ARGS(line1_pt1), line1_dist, line2_dist,
3019  V3ARGS(line2_pt1), V3ARGS(line2_pt2));
3020  bu_bomb("co-linear, pt on loopuse but not vertexuse\n");
3021  return NMG_CLASS_AonBshared;
3022 
3023  } else if ((line1_dist > SMALL_FASTF) && (line2_dist > SMALL_FASTF)) {
3024  /* true when both intercepts are on the ray
3025  * this is not a hit but we need to keep track of these
3026  * future hits on these vertices are inconclusive
3027  */
3028  bu_log("nmg_classify_pt_loop_new(): co-linear ON RAY, ray = %g %g %g -> %g %g %g edge = %g %g %g -> %g %g %g lu_ptr = %p line1_dist = %g line2_dist = %g\n",
3029  V3ARGS(line1_pt1), V3ARGS(line1_pt2), V3ARGS(line2_pt1),
3030  V3ARGS(line2_pt2), (void *)lu, line1_dist, line2_dist);
3031  eu2 = BU_LIST_PNEXT(edgeuse, eu2);
3032  } else {
3033  eu2 = BU_LIST_PNEXT(edgeuse, eu2);
3034  }
3035  } /* end of status = 0 if statement */
3036 
3037  if (status != 1 && status != 0) {
3038  eu2 = BU_LIST_PNEXT(edgeuse, eu2);
3039  }
3040  }
3041  } /* end of while-loop */
3042 
3043  if (hit_cnt != 0) {
3044  if (NEAR_ZERO((hit_cnt/2.0) - floor(hit_cnt/2.0), SMALL_FASTF)) {
3045  /* true when hit_cnt is even */
3046  bu_log("nmg_classify_pt_loop_new(): hit_cnt = %d %f %f EVEN\n",
3047  hit_cnt, (hit_cnt/2.0), floor(hit_cnt/2.0));
3048  out_cnt++;
3049  } else {
3050  bu_log("nmg_classify_pt_loop_new(): hit_cnt = %d %f %f ODD\n",
3051  hit_cnt, (hit_cnt/2.0), floor(hit_cnt/2.0));
3052  in_cnt++;
3053  }
3054  }
3055  }
3056 
3057  if (((out_cnt > 0) && (in_cnt != 0)) || ((in_cnt > 0) && (out_cnt != 0))) {
3058  bu_log("lu ptr = %p pt = %g %g %g in_cnt = %d out_cnt = %d on_cnt = %d\n",
3059  (void *)lu, V3ARGS(line1_pt1), in_cnt, out_cnt, on_cnt);
3060  bu_log("nmg_classify_pt_loop_new(): inconsistent result, point both inside and outside loopuse\n");
3061  }
3062 
3063  if (out_cnt > 0) {
3064  bu_log("\nnmg_classify_pt_loop_new(): END ==========================================\n\n");
3065  return NMG_CLASS_AoutB;
3066  }
3067  if (in_cnt > 0) {
3068  bu_log("\nnmg_classify_pt_loop_new(): END ==========================================\n\n");
3069  return NMG_CLASS_AinB;
3070  }
3071 
3072  bu_log("in_cnt = %d out_cnt = %d on_cnt = %d\n", in_cnt, out_cnt, on_cnt);
3073  bu_bomb("nmg_classify_pt_loop_new(): should not be here\n");
3074 
3075  return NMG_CLASS_Unknown; /* error */
3076 }
3077 
3078 
3079 int
3080 nmg_classify_lu_lu_new(const struct loopuse *lu1, const struct loopuse *lu2, const struct bn_tol *tol)
3081 {
3082  struct edgeuse *eu;
3083  int status;
3084  int in_cnt = 0;
3085  int out_cnt = 0;
3086  int on_cnt = 0;
3087 
3088  NMG_CK_LOOPUSE(lu1);
3089  NMG_CK_LOOPUSE(lu2);
3090 
3091  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) != NMG_EDGEUSE_MAGIC) {
3092  bu_bomb("nmg_classify_lu_lu_new(): loopuse lu1 contains no edgeuse\n");
3093  }
3094 
3095  for (BU_LIST_FOR(eu, edgeuse, &lu1->down_hd)) {
3096 
3097  status = nmg_classify_pt_loop_new(eu->vu_p->v_p, lu2, tol);
3098 
3099  if (status == NMG_CLASS_AoutB) {
3100  out_cnt++;
3101  }
3102  if (status == NMG_CLASS_AinB) {
3103  in_cnt++;
3104  }
3105  if (status == NMG_CLASS_AonBshared) {
3106  on_cnt++;
3107  }
3108  }
3109 
3110  if (((out_cnt > 0) && (in_cnt != 0)) || ((in_cnt > 0) && (out_cnt != 0))) {
3111  bu_log("in_cnt = %d out_cnt = %d on_cnt = %d\n", in_cnt, out_cnt, on_cnt);
3112  bu_log("nmg_classify_lu_lu_new(): inconsistent result, point both inside and outside loopuse\n");
3113  }
3114 
3115  if (out_cnt > 0) {
3116  return NMG_CLASS_AoutB;
3117  }
3118  if (in_cnt > 0) {
3119  return NMG_CLASS_AinB;
3120  }
3121 
3122  bu_log("lu1_ptr = %p lu2_ptr = %p in_cnt = %d out_cnt = %d on_cnt = %d\n",
3123  (void *)lu1, (void *)lu2, in_cnt, out_cnt, on_cnt);
3124  bu_bomb("nmg_classify_lu_lu_new(): should not be here\n");
3125 
3126  return NMG_CLASS_Unknown; /* error */
3127 }
3128 
3129 
3130 void
3131 insert_above(struct loopuse *lu, struct loopuse_tree_node *node, const struct bn_tol *tol)
3132 {
3133  struct loopuse_tree_node *new_node, *node_tmp, *node_idx;
3134  int done = 0;
3135  int result;
3136 
3137  if (node->l.magic == BU_LIST_HEAD_MAGIC) {
3138  bu_bomb("insert_above(): was passed bu_list head, should have received bu_list node\n");
3139  }
3140 
3141  NMG_CK_LOOPUSE(lu);
3142  /* XXX - where is this released? */
3143  BU_ALLOC(new_node, struct loopuse_tree_node);
3144  BU_LIST_INIT(&(new_node->l));
3145  new_node->l.magic = 0;
3146  new_node->lu = lu;
3147  new_node->parent = node->parent;
3148  BU_LIST_INIT(&(new_node->children_hd));
3149  new_node->children_hd.magic = BU_LIST_HEAD_MAGIC;
3150  node_idx = BU_LIST_PNEXT(loopuse_tree_node, &(node->l));
3151  BU_LIST_DEQUEUE(&(node->l));
3152  node->parent = new_node;
3153  BU_LIST_APPEND(&(new_node->children_hd), &(node->l));
3154 
3155 
3156  bu_log("insert_above(): lu_p = %p node ptr = %p new_node ptr = %p\n",
3157  (void *)lu, (void *)node, (void *)new_node);
3158 
3159  if (node_idx->l.magic == BU_LIST_HEAD_MAGIC) {
3160  return;
3161  }
3162 
3163  while (!done) {
3164  if (node_idx->l.magic == BU_LIST_HEAD_MAGIC) {
3165  done = 1;
3166  } else {
3167  NMG_CK_LOOPUSE(node_idx->lu);
3168  result = nmg_classify_lu_lu(node_idx->lu, lu, tol);
3169 
3170  if (result == NMG_CLASS_AinB) {
3171  node_tmp = BU_LIST_PNEXT(loopuse_tree_node, node_idx);
3172  BU_LIST_DEQUEUE(&(node_idx->l));
3173  node_idx->parent = new_node;
3174  BU_LIST_APPEND(&(new_node->children_hd), &(node_idx->l));
3175  bu_log("insert_above(): adjust lu_p = %p node ptr = %p new_node ptr = %p\n",
3176  (void *)lu, (void *)node_idx, (void *)new_node);
3177  node_idx = node_tmp;
3178  } else {
3179  node_idx = BU_LIST_PNEXT(loopuse_tree_node, node_idx);
3180  }
3181  }
3182  }
3183  BU_LIST_APPEND(&(new_node->parent->children_hd), &(new_node->l));
3184 
3185  return;
3186 }
3187 
3188 void
3189 insert_node(struct loopuse *lu, struct bu_list *head,
3190  struct loopuse_tree_node *parent, const struct bn_tol *tol)
3191 {
3192  /* when 'insert_node' is first called, the level must be '0' */
3193  int found = 0;
3194  int result1 = 0; /* AinB */
3195  int result2 = 0; /* BinA */
3196  int result_tmp = 0;
3197  struct loopuse_tree_node *node = 0;
3198  struct loopuse_tree_node *new_node = 0;
3199  int orientation_tmp_a, orientation_tmp_b;
3200 
3201  NMG_CK_LOOPUSE(lu);
3202 
3203  if (BU_LIST_NON_EMPTY(head)) {
3204  for (BU_LIST_FOR(node, loopuse_tree_node, head)) {
3205  NMG_CK_LOOPUSE(node->lu);
3206 
3207  orientation_tmp_a = lu->orientation;
3208  orientation_tmp_b = node->lu->orientation;
3209  lu->orientation = 1;
3210  node->lu->orientation = 1;
3211  result1 = nmg_classify_lu_lu(lu, node->lu, tol);
3212  lu->orientation = orientation_tmp_a;
3213  node->lu->orientation = orientation_tmp_b;
3214  bu_log("---- lu %p %d vs lu %p %d result1 = %d\n",
3215  (void *)lu, lu->orientation,
3216  (void *)node->lu, node->lu->orientation, result1);
3217 
3218  orientation_tmp_a = node->lu->orientation;
3219  orientation_tmp_b = lu->orientation;
3220  node->lu->orientation = 1;
3221  lu->orientation = 1;
3222  result_tmp = nmg_classify_lu_lu_new(node->lu, lu, tol);
3223  bu_log("NEW FUNCTION ---- lu %p lu-orient = %d vs lu %p lu-orient = %d result_tmp = %d\n",
3224  (void *)node->lu, node->lu->orientation,
3225  (void *)lu, lu->orientation, result_tmp);
3226  result2 = nmg_classify_lu_lu(node->lu, lu, tol);
3227 
3228  node->lu->orientation = orientation_tmp_a;
3229  lu->orientation = orientation_tmp_b;
3230  bu_log("OLD FUNCTION ---- lu %p lu-orient = %d vs lu %p lu-orient = %d ...result2 = %d\n",
3231  (void *)node->lu, node->lu->orientation,
3232  (void *)lu, lu->orientation, result2);
3233 
3234  if (result_tmp != result2) {
3235  bu_log("nmg_classify_lu_lu_new != nmg_classify_lu_lu\n");
3236  }
3237 
3238  if (result1 == NMG_CLASS_AinB) {
3239  /* insert new node below current node */
3240  found = 1;
3241  bu_log("lu %p in lu %p\n", (void *)lu, (void *)node->lu);
3242  insert_node(lu, &(node->children_hd), parent, tol);
3243  break;
3244  }
3245  if (result2 == NMG_CLASS_AinB) {
3246  /* insert new node above current node */
3247  found = 1;
3248  bu_log("lu %p in lu %p\n", (void *)node->lu, (void *)lu);
3249  break;
3250  }
3251  }
3252  }
3253 
3254  if (!found) {
3255  bu_log("lu %p in lu %p\n", (void *)lu, (void *)parent->lu);
3256  }
3257 
3258  if (!found || (result2 == NMG_CLASS_AinB)) {
3259  /* XXX - where is this released? */
3260  BU_ALLOC(new_node, struct loopuse_tree_node);
3261  BU_LIST_INIT(&(new_node->l));
3262  /* unset magic from BU_LIST_HEAD_MAGIC to zero since this node
3263  * is not going to be a head
3264  */
3265  new_node->l.magic = 1;
3266  new_node->lu = lu;
3267  new_node->parent = parent;
3268  BU_LIST_INIT(&(new_node->children_hd)); /* also sets magic to BU_LIST_HEAD_MAGIC */
3269  BU_LIST_APPEND(head, &(new_node->l));
3270  bu_log("insert-node, insert-node ptr = %p, lu_p = %p parent ptr = %p\n",
3271  (void *)&(new_node->l), (void *)new_node->lu, (void *)new_node->parent);
3272  }
3273 
3274  if (found) {
3275  if (result2 == NMG_CLASS_AinB) {
3276  BU_LIST_DEQUEUE(&(node->l));
3277  BU_LIST_APPEND(&(new_node->children_hd), &(node->l));
3278  }
3279  }
3280 
3281  return;
3282 }
3283 
3284 
3285 void
3286 nmg_build_loopuse_tree(struct faceuse *fu, struct loopuse_tree_node **root, const struct bn_tol *tol)
3287 {
3288 
3289  struct loopuse *lu;
3290  int loopuse_cnt = 0;
3291  NMG_CK_FACEUSE(fu);
3292 
3293  /* create initial head node */
3294  /* XXX - where is this released? */
3295  BU_ALLOC(*root, struct loopuse_tree_node);
3296  BU_LIST_INIT(&((*root)->l));
3297  BU_LIST_INIT(&((*root)->children_hd));
3298  (*root)->parent = (struct loopuse_tree_node *)NULL;
3299  (*root)->lu = (struct loopuse *)NULL;
3300  bu_log("root node addr = %p\n", (void *)&((*root)->l));
3301 
3302  loopuse_cnt = 0;
3303  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3304  NMG_CK_LOOPUSE(lu);
3305  loopuse_cnt++;
3306  bu_log("nmg_build_loopuse_tree(): %d fu_p = %p lu_p = %p\n",
3307  loopuse_cnt, (void *)fu, (void *)lu);
3308  }
3309 
3310  loopuse_cnt = 0;
3311  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3312  NMG_CK_LOOPUSE(lu);
3313  loopuse_cnt++;
3314  bu_log("nmg_build_loopuse_tree(): %d fu_p = %p lu_p = %p\n",
3315  loopuse_cnt, (void *)fu, (void *)lu);
3316  bu_log("nmg_build_loopuse_tree(): root child ptr = %p root ptr = %p\n",
3317  (void *)&((*root)->children_hd), (void *)*root);
3318  insert_node(lu, &((*root)->children_hd), *root, tol);
3319  }
3320 }
3321 
3322 /*
3323  * return 1 when faceuse is empty, otherwise return 0.
3324  *
3325  */
3326 int
3327 nmg_triangulate_fu(struct faceuse *fu, const struct bn_tol *tol)
3328 {
3329  int ccw_result;
3330  int vert_count = 0;
3331  int ret = 0;
3332 
3333  /* boolean variables */
3334  int cut = 0;
3335  int need_triangulation = 0;
3336 
3337  struct bu_list *tbl2d;
3338  struct loopuse *lu;
3339  struct edgeuse *eu;
3340  struct pt2d *pt;
3341 
3342  vect_t fu_normal;
3343  mat_t TformMat;
3344 
3345  BN_CK_TOL(tol);
3346  NMG_CK_FACEUSE(fu);
3347 
3348  NMG_GET_FU_NORMAL(fu_normal, fu);
3349 
3350  if (RTG.NMG_debug & DEBUG_TRI) {
3351  bu_log("---------------- Triangulate face fu_p = 0x%lx fu Normal = %g %g %g\n",
3352  (unsigned long)fu, V3ARGS(fu_normal));
3353  }
3354 
3355  if (RTG.NMG_debug & DEBUG_TRI) {
3356  nmg_plot_fu("nmg_triangulate_fu_unprocessed_faceuse", fu, tol);
3357  }
3358 
3359  /* test if this faceuse needs triangulation. this for-loop is
3360  * to prevent extra processing on simple faceuse. after
3361  * initial processing of more complex faceuse we will need to
3362  * test the faceuse again if it needs to be triangulated
3363  */
3364  need_triangulation = 0;
3365  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3366  NMG_CK_LOOPUSE(lu);
3367  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
3368  continue;
3369  }
3370  if (!((lu->orientation == OT_SAME) || (lu->orientation == OT_OPPOSITE))) {
3371  bu_bomb("nmg_triangulate_fu(): loopuse orientation must be OT_SAME or OT_OPPOSITE\n");
3372  }
3373  if (lu->orientation == OT_OPPOSITE) {
3374  /* the faceuse must contain only exterior loopuse
3375  * to possibly skip triangulation
3376  */
3377  need_triangulation++;
3378  } else {
3379  vert_count = 0;
3380  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
3381  NMG_CK_EDGEUSE(eu);
3382  vert_count++;
3383  }
3384  if (vert_count != 3) {
3385  /* we want to process the loopuse if any have more
3386  * or less than 3 vertices. if less than 3, we want
3387  * to remove these loopuse, if greater than 3 we
3388  * want to triangulate them
3389  */
3390  need_triangulation++;
3391  }
3392  }
3393  }
3394  if (!need_triangulation) {
3395  goto out2;
3396  }
3397 
3398  /* do some cleanup before anything else */
3399  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3400  (void)nmg_loop_split_at_touching_jaunt(lu, tol);
3401  }
3402  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3403  nmg_split_touchingloops(lu, tol);
3404  }
3405  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3406  nmg_lu_reorient(lu);
3407  }
3408 
3409  /* remove loopuse with < 3 vertices i.e. degenerate loopuse */
3410  if (nmg_triangulate_rm_degen_loopuse(fu, tol)) {
3411  /* true when faceuse is empty */
3412  ret = 1;
3413  goto out2;
3414  }
3415 
3416  if (RTG.NMG_debug & DEBUG_TRI) {
3417  nmg_plot_fu("nmg_triangulate_fu_after_cleanup_after_degen_loopuse_killed", fu, tol);
3418  }
3419 
3420  if (RTG.NMG_debug & DEBUG_TRI) {
3421  bu_log("nmg_triangulate_fu(): proceeding to triangulate face %g %g %g\n", V3ARGS(fu_normal));
3422  }
3423 
3424  /* convert 3D face to face in the X-Y plane */
3425  tbl2d = nmg_flatten_face(fu, TformMat, tol);
3426 
3427  if (RTG.NMG_debug & DEBUG_TRI) {
3428  validate_tbl2d("before nmg_triangulate_rm_holes", tbl2d, fu);
3429  }
3430 
3431  /* remove holes from faceuse. this is done by converting inner
3432  * loopuse (i.e. holes, loopuse with cw rotation, loopuse with
3433  * OT_OPPOSITE orientation) by joining/connecting these inner
3434  * loopuse with outer loopuse so the inner loopuse becomes part
3435  * of the outer loopuse
3436  */
3437  nmg_triangulate_rm_holes(fu, tbl2d, tol);
3438 
3439  if (RTG.NMG_debug & DEBUG_TRI) {
3440  validate_tbl2d("after nmg_triangulate_rm_holes", tbl2d, fu);
3441  }
3442 
3443  /* this 'while loop' goes through each loopuse within the faceuse
3444  * and performs ear-clipping (i.e. triangulation). the 'while loop'
3445  * ends when we can go through all the loopuse within the faceuse
3446  * and no cuts need to be performed. each time a cut is performed
3447  * we restart at the beginning of the list of loopuse. the reason
3448  * for this is we can not be sure of the ordering of the loopuse
3449  * within the faceuse after loopuse are cut.
3450  */
3451  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
3452  vert_count = 0;
3453  while (BU_LIST_NOT_HEAD(lu, &fu->lu_hd)) {
3454  NMG_CK_LOOPUSE(lu);
3455  cut = 0;
3456  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_EDGEUSE_MAGIC) {
3457  /* true when loopuse contains edgeuse */
3458  vert_count = 0;
3459  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
3460  NMG_CK_EDGEUSE(eu);
3461  vert_count++;
3462  }
3463  /* only ear-clip loopuse with > 3 vertices */
3464  if (vert_count > 3) {
3465  /* test loopuse rotation */
3466  ccw_result = nmg_loop_is_ccw(lu, fu_normal, tol);
3467  if (ccw_result == 1 || ccw_result == 0) {
3468  /* true when loopuse rotation is ccw */
3469  if (lu->orientation != OT_SAME) {
3470  /* set loopuse orientation to OT_SAME */
3471  nmg_set_lu_orientation(lu, 0);
3472  }
3473  /* ear clip loopuse */
3474  cut_unimonotone(tbl2d, lu, tol);
3475  cut = 1;
3476  } else if (ccw_result == -1) {
3477  /* true when loopuse rotation is cw or unknown */
3478  bu_log("nmg_triangulate_fu(): lu = 0x%lx ccw_result = %d\n",
3479  (unsigned long)lu, ccw_result);
3480  vert_count = 0;
3481  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
3482  vert_count++;
3483  bu_log("nmg_triangulate_fu(): %d ccw_result = %d lu = %p coord = %g %g %g\n",
3484  vert_count, ccw_result,
3485  (void *)lu, V3ARGS(eu->vu_p->v_p->vg_p->coord));
3486  }
3487  bu_bomb("nmg_triangulate_fu(): attempted to cut problem loopuse\n");
3488  } else {
3489  bu_bomb("nmg_triangulate_fu(): function nmg_loop_is_ccw returned invalid result\n");
3490  }
3491  }
3492  }
3493  if (cut) {
3494  /* since a cut was made, continue with the first
3495  * loopuse in the faceuse
3496  */
3497  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
3498  } else {
3499  /* since no cut was made, continue with the next
3500  * loopuse in the faceuse
3501  */
3502  lu = BU_LIST_PNEXT(loopuse, lu);
3503  }
3504  } /* close of 'loopuse while loop' */
3505 
3506  if (1 || RTG.NMG_debug & DEBUG_TRI) {
3507  /* sanity check */
3508  /* after triangulation, verify all loopuse contains <= 3 vertices
3509  * and those loopuse with 3 vertices do not have a cw rotation
3510  */
3511  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3512  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_EDGEUSE_MAGIC) {
3513  vert_count = 0;
3514  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
3515  vert_count++;
3516  if (vert_count > 3) {
3517  bu_bomb("nmg_triangulate_fu(): after ear-clipping found loopuse with > 3 vertices\n");
3518  } else if (vert_count == 3) {
3519  ccw_result = nmg_loop_is_ccw(lu, fu_normal, tol);
3520  if (ccw_result == -1) {
3521  bu_bomb("nmg_triangulate_fu(): after ear-clipping found loopuse with cw rotation\n");
3522  }
3523  }
3524  }
3525  }
3526  }
3527  }
3528 
3529  if (RTG.NMG_debug & DEBUG_TRI) {
3530  validate_tbl2d("nmg_triangulate_fu() after triangulation, before lu_reorient", tbl2d, fu);
3531  }
3532 
3533  /* removes loopuse with < 3 vertices i.e. degenerate loopuse */
3534  if (nmg_triangulate_rm_degen_loopuse(fu, tol)) {
3535  /* true when faceuse is empty */
3536  ret = 1;
3537  goto out1;
3538  }
3539 
3540  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3541  /* set the loopuse orientation to OT_SAME */
3542  nmg_set_lu_orientation(lu, 0);
3543  }
3544 
3545  if (RTG.NMG_debug & DEBUG_TRI) {
3546  validate_tbl2d("nmg_triangulate_fu() after triangulation, after lu_reorient", tbl2d, fu);
3547  }
3548 
3549 out1:
3550  while (BU_LIST_WHILE(pt, pt2d, tbl2d)) {
3551  BU_LIST_DEQUEUE(&pt->l);
3552  bu_free((char *)pt, "pt2d free");
3553  }
3554 
3555  bu_free((char *)tbl2d, "discard tbl2d");
3556 
3557 out2:
3558  return ret;
3559 }
3560 
3561 
3562 /* Disable the old version of function nmg_triangulate_fu */
3563 #if 0
3564 void
3565 nmg_triangulate_fu(struct faceuse *fu, const struct bn_tol *tol)
3566 {
3567  mat_t TformMat;
3568  struct bu_list *tbl2d;
3569  struct loopuse *lu;
3570  struct edgeuse *eu;
3571  struct vertexuse *vu;
3572  struct bu_list tlist;
3573  struct trap *tp;
3574  struct pt2d *pt;
3575  int vert_count;
3576  static int iter=0;
3577  static int monotone=0;
3578  vect_t N;
3579 
3580  char db_name[32];
3581 
3582  VSETALL(N, 0);
3583 
3584  BN_CK_TOL(tol);
3585  NMG_CK_FACEUSE(fu);
3586 
3587  if (RTG.NMG_debug & DEBUG_TRI) {
3588  NMG_GET_FU_NORMAL(N, fu);
3589  bu_log("---------------- Triangulate face %g %g %g\n",
3590  V3ARGS(N));
3591  }
3592 
3593 
3594  /* make a quick check to see if we need to bother or not */
3595  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3596  if (lu->orientation != OT_SAME) {
3597  if (RTG.NMG_debug & DEBUG_TRI)
3598  bu_log("faceuse has non-OT_SAME orientation loop\n");
3599  goto triangulate;
3600  }
3601  vert_count = 0;
3602  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd))
3603  if (++vert_count > 3) {
3604  if (RTG.NMG_debug & DEBUG_TRI)
3605  bu_log("loop has more than 3 vertices\n");
3606  goto triangulate;
3607  }
3608  }
3609 
3610  if (RTG.NMG_debug & DEBUG_TRI) {
3611  bu_log("---------------- face %g %g %g already triangular\n",
3612  V3ARGS(N));
3613 
3614  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd))
3615  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd))
3616  VPRINT("pt", eu->vu_p->v_p->vg_p->coord);
3617 
3618  }
3619  return;
3620 
3621 triangulate:
3622  if (RTG.NMG_debug & DEBUG_TRI) {
3623  vect_t normal;
3624  NMG_GET_FU_NORMAL(normal, fu);
3625  bu_log("---------------- proceeding to triangulate face %g %g %g\n", V3ARGS(normal));
3626  }
3627 
3628 
3629  /* convert 3D face to face in the X-Y plane */
3630  tbl2d = nmg_flatten_face(fu, TformMat);
3631 
3632  /* avoid having a hole start as the first point */
3633  {
3634  struct pt2d *pt1, *pt2;
3635 
3636  pt1 = BU_LIST_FIRST(pt2d, tbl2d);
3637  pt2 = BU_LIST_PNEXT(pt2d, &pt1->l);
3638 
3639  if (vtype2d(pt1, tbl2d, tol) == HOLE_START
3640  && pt1->vu_p->v_p == pt2->vu_p->v_p)
3641  {
3642  /* swap first and second points */
3643  if (RTG.NMG_debug & DEBUG_TRI)
3644  bu_log("Swapping first two points on vertex list (first one was a HOLE_START)\n");
3645 
3646  BU_LIST_DEQUEUE(&pt1->l);
3647  BU_LIST_APPEND(&pt2->l, &pt1->l);
3648  }
3649  }
3650 
3651  if (RTG.NMG_debug & DEBUG_TRI) {
3652  struct pt2d *point;
3653  bu_log("Face Flattened\n");
3654  bu_log("Vertex list:\n");
3655  for (BU_LIST_FOR(point, pt2d, tbl2d)) {
3656  bu_log("\tpt2d %26.20e %26.20e\n", point->coord[0], point->coord[1]);
3657  }
3658 
3659  nmg_tri_plfu(fu, tbl2d);
3660  nmg_plot_flat_face(fu, tbl2d);
3661  bu_log("Face plotted\n\tmaking trapezoids...\n");
3662  }
3663 
3664 
3665  BU_LIST_INIT(&tlist);
3666  nmg_trap_face(tbl2d, &tlist, tol);
3667 
3668  if (RTG.NMG_debug & DEBUG_TRI) {
3669  print_tlist(tbl2d, &tlist);
3670 
3671  bu_log("Cutting diagonals ----------\n");
3672  }
3673  cut_diagonals(tbl2d, &tlist, fu, tol);
3674  if (RTG.NMG_debug & DEBUG_TRI)
3675  bu_log("Diagonals are cut ----------\n");
3676 
3677  if (RTG.NMG_debug & DEBUG_TRI) {
3678  sprintf(db_name, "uni%d.g", iter);
3679  nmg_stash_model_to_file(db_name,
3680  nmg_find_model(&fu->s_p->l.magic),
3681  "triangles and unimonotones");
3682  }
3683 
3684  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd))
3685  (void)nmg_loop_split_at_touching_jaunt(lu, tol);
3686 
3687  if (RTG.NMG_debug & DEBUG_TRI) {
3688  sprintf(db_name, "uni_sj%d.g", iter);
3689  nmg_stash_model_to_file(db_name,
3690  nmg_find_model(&fu->s_p->l.magic),
3691  "after split_at_touching_jaunt");
3692  }
3693 
3694  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd))
3695  nmg_split_touchingloops(lu, tol);
3696 
3697  if (RTG.NMG_debug & DEBUG_TRI) {
3698  sprintf(db_name, "uni_split%d.g", iter++);
3699  nmg_stash_model_to_file(db_name,
3700  nmg_find_model(&fu->s_p->l.magic),
3701  "split triangles and unimonotones");
3702  }
3703 
3704  /* now we're left with a face that has some triangle loops and some
3705  * uni-monotone loops. Find the uni-monotone loops and triangulate.
3706  */
3707  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
3708 
3709  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
3710  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
3711 
3712  bu_log("How did I miss this vertex loop %g %g %g?\n%s\n",
3713  V3ARGS(vu->v_p->vg_p->coord),
3714  "I'm supposed to be dealing with unimonotone loops now");
3715  bu_bomb("aborting\n");
3716 
3717  } else if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_EDGEUSE_MAGIC) {
3718  vert_count = 0;
3719  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
3720  if (++vert_count > 3) {
3721  cut_unimonotone(tbl2d, lu, tol);
3722 
3723  if (RTG.NMG_debug & DEBUG_TRI) {
3724  sprintf(db_name, "uni_mono%d.g", monotone++);
3725  nmg_stash_model_to_file(db_name,
3726  nmg_find_model(&fu->s_p->l.magic),
3727  "newly cut unimonotone");
3728  }
3729 
3730  break;
3731  }
3732  }
3733  }
3734  }
3735 
3736 
3737  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd))
3738  nmg_lu_reorient(lu);
3739 
3740  if (RTG.NMG_debug & DEBUG_TRI)
3741  nmg_tri_plfu(fu, tbl2d);
3742 
3743  while (BU_LIST_WHILE(tp, trap, &tlist)) {
3744  BU_LIST_DEQUEUE(&tp->l);
3745  bu_free((char *)tp, "trapezoid free");
3746  }
3747 
3748  while (BU_LIST_WHILE(pt, pt2d, tbl2d)) {
3749  BU_LIST_DEQUEUE(&pt->l);
3750  bu_free((char *)pt, "pt2d free");
3751  }
3752  bu_free((char *)tbl2d, "discard tbl2d");
3753 
3754  return;
3755 }
3756 #endif
3757 /* This is the endif to disable the old version of function
3758  * nmg_triangulate_fu.
3759  */
3760 
3761 
3762 void
3763 nmg_triangulate_shell(struct shell *s, const struct bn_tol *tol)
3764 {
3765  struct faceuse *fu, *fu_next;
3766 
3767  BN_CK_TOL(tol);
3768  NMG_CK_SHELL(s);
3769 
3770  if (UNLIKELY(RTG.NMG_debug & DEBUG_TRI)) {
3771  bu_log("nmg_triangulate_shell(): Triangulating NMG shell.\n");
3772  }
3773 
3774  (void)nmg_edge_g_fuse(&s->l.magic, tol);
3775  (void)nmg_unbreak_region_edges(&s->l.magic);
3776 
3777  fu = BU_LIST_FIRST(faceuse, &s->fu_hd);
3778  while (BU_LIST_NOT_HEAD(fu, &s->fu_hd)) {
3779  NMG_CK_FACEUSE(fu);
3780  fu_next = BU_LIST_PNEXT(faceuse, &fu->l);
3781 
3782  if (UNLIKELY(fu->orientation != OT_SAME && fu->orientation != OT_OPPOSITE)) {
3783  /* sanity check */
3784  bu_bomb("nmg_triangulate_shell(): Invalid faceuse orientation. (1)\n");
3785  }
3786 
3787  if (fu->orientation == OT_SAME) {
3788  if (fu_next == fu->fumate_p) {
3789  /* Make sure that fu_next is not the mate of fu
3790  * because if fu is killed so will its mate
3791  * resulting in an invalid fu_next.
3792  */
3793  fu_next = BU_LIST_PNEXT(faceuse, &fu_next->l);
3794  }
3795  if (UNLIKELY(fu->fumate_p->orientation != OT_OPPOSITE)) {
3796  /* sanity check */
3797  bu_bomb("nmg_triangulate_shell(): Invalid faceuse orientation. (2)\n");
3798  }
3799  if (nmg_triangulate_fu(fu, tol)) {
3800  /* true when faceuse is empty */
3801  if (nmg_kfu(fu)) {
3802  bu_bomb("nmg_triangulate_shell(): Shell contains no faceuse.\n");
3803  }
3804  }
3805  }
3806  fu = fu_next;
3807  }
3808 
3809  nmg_vsshell(s, s->r_p);
3810 
3811  if (UNLIKELY(RTG.NMG_debug & DEBUG_TRI)) {
3812  bu_log("nmg_triangulate_shell(): Triangulating NMG shell completed.\n");
3813  }
3814 }
3815 
3816 
3817 void
3818 nmg_triangulate_model(struct model *m, const struct bn_tol *tol)
3819 {
3820  struct nmgregion *r;
3821  struct shell *s;
3822 
3823  BN_CK_TOL(tol);
3824  NMG_CK_MODEL(m);
3825 
3826  if (RTG.NMG_debug & DEBUG_TRI) {
3827  bu_log("nmg_triangulate_model(): Triangulating NMG model.\n");
3828  }
3829 
3830  for (BU_LIST_FOR(r, nmgregion, &m->r_hd)) {
3831  NMG_CK_REGION(r);
3832  for (BU_LIST_FOR(s, shell, &r->s_hd)) {
3833  nmg_triangulate_shell(s, tol);
3834  }
3835  }
3836 
3837  if (RTG.NMG_debug & DEBUG_TRI) {
3838  bu_log("nmg_triangulate_model(): Triangulating NMG model completed.\n");
3839  }
3840 }
3841 
3842 
3843 /*
3844  * Local Variables:
3845  * mode: C
3846  * tab-width: 8
3847  * indent-tabs-mode: t
3848  * c-file-style: "stroustrup"
3849  * End:
3850  * ex: shiftwidth=4 tabstop=8
3851  */
#define BU_LIST_PNEXT_CIRC(structure, p)
Definition: list.h:442
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
void nmg_lu_reorient(struct loopuse *lu)
Definition: nmg_mod.c:3649
#define NMG_CK_TRAP(_p)
Definition: nmg_tri.c:57
#define NMG_EDGEUSE_MAGIC
Definition: magic.h:120
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_LIST_INSERT(old, new)
Definition: list.h:183
struct faceuse * nmg_find_fu_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:270
void nmg_stash_model_to_file(const char *filename, const struct model *m, const char *title)
Definition: nmg_misc.c:4500
int nmg_unbreak_region_edges(uint32_t *magic_p)
Definition: nmg_misc.c:4650
Definition: list.h:118
int nmg_kfu(struct faceuse *fu1)
Definition: nmg_mk.c:1207
int bn_isect_pt_lseg(fastf_t *dist, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Intersect a point P with the line segment defined by two distinct points A and B. ...
#define NMG_SHELL_MAGIC
Definition: magic.h:142
void nmg_find_first_last_use_of_v_in_fu(struct vertex *v, struct vertexuse **first_vu, struct vertexuse **last_vu, fastf_t *dir, struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_tri.c:795
int nmg_isect_potcut_fu(struct edgeuse *eu1, struct edgeuse *eu2, struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_tri.c:1650
void pdv_3move(register FILE *plotfp, const fastf_t *pt)
Definition: plot3.c:618
struct edgeuse * pick_eu(struct edgeuse *eu_p, struct faceuse *fu, fastf_t *dir, int find_max)
Definition: nmg_tri.c:684
double dist
>= 0
Definition: tol.h:73
void nmg_set_lu_orientation(struct loopuse *lu, int is_opposite)
Definition: nmg_mod.c:3620
#define P_GT_V(_p, _v)
Definition: nmg_tri.c:45
struct bu_list l
Definition: nmg_tri.c:91
if lu s
Definition: nmg_mod.c:3860
Definition: clone.c:90
int nmg_classify_lu_lu_new(const struct loopuse *lu1, const struct loopuse *lu2, const struct bn_tol *tol)
Definition: nmg_tri.c:3080
lu
Definition: nmg_mod.c:3855
#define VSET(a, b, c, d)
Definition: color.c:53
#define VSETALL(a, s)
Definition: color.c:54
#define N
Definition: randmt.c:39
Definition: nmg_tri.c:75
#define NMG_TBL2D_MAGIC
Definition: nmg_tri.c:68
#define BU_LIST_IS_EMPTY(hp)
Definition: list.h:295
struct pt2d * top
Definition: nmg_tri.c:84
#define M_PI
Definition: fft.h:35
#define PT2D_PREV(tbl, pt)
Definition: nmg_tri.c:73
#define BU_LIST_MAGIC_SET(_l, _magic)
Definition: list.h:129
Definition: raytrace.h:248
#define SMALL_FASTF
Definition: defines.h:342
struct loopuse_tree_node * parent
Definition: nmg_tri.c:93
Header file for the BRL-CAD common definitions.
struct bu_list children_hd
Definition: nmg_tri.c:94
void nmg_vertexuse_nv(struct vertexuse *vu, const fastf_t *norm)
Definition: nmg_mk.c:1719
HIDDEN void pick_edges(struct vertex *v, struct vertexuse **vu_first, int *min_dir, struct vertexuse **vu_last, int *max_dir, struct faceuse *fu, fastf_t *dir)
Definition: nmg_tri.c:527
int nmg_classify_lu_lu(const struct loopuse *lu1, const struct loopuse *lu2, const struct bn_tol *tol)
Definition: nmg_class.c:2205
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
void insert_above(struct loopuse *lu, struct loopuse_tree_node *node, const struct bn_tol *tol)
Definition: nmg_tri.c:3131
struct loopuse * nmg_cut_loop(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2283
#define MAX_FASTF
Definition: defines.h:340
int nmg_kvu(struct vertexuse *vu)
Definition: nmg_mk.c:1095
#define NMG_LOOPUSE_MAGIC
Definition: magic.h:130
void pl_erase(register FILE *plotfp)
Definition: plot3.c:271
#define HIDDEN
Definition: common.h:86
struct bu_list * nmg_flatten_face(struct faceuse *fu, fastf_t *TformMat, const struct bn_tol *tol)
Definition: nmg_tri.c:377
NMG_CK_LOOPUSE(lu)
BU_LIST_DEQUEUE & eu1
Definition: nmg_mod.c:3839
struct vertexuse * vu_p
Definition: nmg_tri.c:78
void nmg_triangulate_shell(struct shell *s, const struct bn_tol *tol)
Definition: nmg_tri.c:3763
if(share_geom)
Definition: nmg_mod.c:3829
void nmg_split_touchingloops(struct loopuse *lu, const struct bn_tol *tol)
Definition: nmg_mod.c:2585
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
Definition: color.c:49
int nmg_loop_is_ccw(const struct loopuse *lu, const fastf_t *norm, const struct bn_tol *tol)
Definition: nmg_info.c:533
#define BU_LIST_IS_HEAD(p, hp)
Definition: list.h:322
void nmg_pl_fu(FILE *fp, const struct faceuse *fu, long *b, int red, int green, int blue)
Definition: nmg_plot.c:722
void pd_3space(register FILE *plotfp, double px1, double py1, double pz1, double px2, double py2, double pz2)
Definition: plot3.c:580
void bn_mat_print(const char *title, const mat_t m)
Definition: mat.c:81
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
struct loopuse * lu
Definition: nmg_tri.c:92
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
void bu_vls_sprintf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:707
HIDDEN void nmg_tri_kill_accordions(struct loopuse *lu, struct bu_list *tbl2d)
Definition: nmg_tri.c:2230
#define V3ARGS(a)
Definition: color.c:56
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
int nmg_triangulate_fu(struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_tri.c:3327
void bn_mat_fromto(mat_t m, const fastf_t *from, const fastf_t *to, const struct bn_tol *tol)
Definition: mat.c:639
Coord * point
Definition: chull3d.cpp:52
#define BU_LIST_PNEXT(structure, p)
Definition: list.h:422
void pl_label(register FILE *plotfp, const char *s)
Definition: plot3.c:244
struct edgeuse * e_right
Definition: nmg_tri.c:87
void * bu_realloc(void *ptr, size_t siz, const char *str)
int nmg_classify_pt_loop_new(const struct vertex *line1_pt1_v_ptr, const struct loopuse *lu, const struct bn_tol *tol)
Definition: nmg_tri.c:2836
#define UNUSED(parameter)
Definition: common.h:239
void nmg_triangulate_model(struct model *m, const struct bn_tol *tol)
Definition: nmg_tri.c:3818
int bn_lseg3_lseg3_parallel(const point_t sg1pt1, const point_t sg1pt2, const point_t sg2pt1, const point_t sg2pt2, const struct bn_tol *tol)
Definition: plane.c:2532
goto out
Definition: nmg_mod.c:3846
struct faceuse * nmg_find_fu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:304
Support for uniform tolerances.
Definition: tol.h:71
void nmg_build_loopuse_tree(struct faceuse *fu, struct loopuse_tree_node **root, const struct bn_tol *tol)
Definition: nmg_tri.c:3286
#define BN_CK_TOL(_p)
Definition: tol.h:82
#define BU_LIST_FIRST_MAGIC(hp)
Definition: list.h:416
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
int nmg_find_eu_leftvec(fastf_t *left, const struct edgeuse *eu)
Definition: nmg_info.c:1274
int nmg_isect_pt_facet(struct vertex *v, struct vertex *v0, struct vertex *v1, struct vertex *v2, const struct bn_tol *tol)
Definition: nmg_tri.c:1489
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
uint32_t magic
Magic # for mem id/check.
Definition: list.h:119
#define BU_LIST_WHILE(p, structure, hp)
Definition: list.h:410
struct bu_list l
Definition: nmg_tri.c:83
void pl_color(register FILE *plotfp, int r, int g, int b)
Definition: plot3.c:325
void pdv_3line(register FILE *plotfp, const fastf_t *a, const fastf_t *b)
Definition: plot3.c:642
#define P_LT_V(_p, _v)
Definition: nmg_tri.c:47
#define NMG_CK_TBL2D(_p)
Definition: nmg_tri.c:69
oldeumate e_p eu_p
Definition: nmg_mod.c:3940
#define BU_LIST_PPREV_CIRC(structure, p)
Definition: list.h:450
HIDDEN void cut_unimonotone(struct bu_list *tbl2d, struct loopuse *lu, const struct bn_tol *tol)
Definition: nmg_tri.c:2350
double perp
nearly 0
Definition: tol.h:75
struct edgeuse * e_left
Definition: nmg_tri.c:86
#define ZERO(val)
Definition: units.c:38
#define BU_LIST_INIT(_hp)
Definition: list.h:148
double bn_dist_pt3_pt3(const point_t a, const point_t b)
Returns distance between two points.
int nmg_klu(struct loopuse *lu1)
Definition: nmg_mk.c:1277
int bn_isect_lseg3_lseg3(fastf_t *dist, const point_t p, const vect_t pdir, const point_t q, const vect_t qdir, const struct bn_tol *tol)
Intersect two 3D line segments, defined by two points and two vectors. The vectors are unlikely to be...
void nmg_plot_lu_around_eu(const char *prefix, const struct edgeuse *eu, const struct bn_tol *tol)
Definition: nmg_plot.c:2111
int hit(struct application *ap, struct partition *PartHeadp, struct seg *segs)
Definition: gqa.c:963
Definition: nmg_tri.c:82
void nmg_pr_lu(const struct loopuse *lu, char *h)
Definition: nmg_pr.c:405
int bn_isect_line3_line3(fastf_t *s, fastf_t *t, const point_t p0, const vect_t u, const point_t q0, const vect_t v, const struct bn_tol *tol)
struct vertexuse * nmg_join_2loops(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2043
#define NMG_VERTEXUSE_A_PLANE_MAGIC
Definition: magic.h:144
struct bu_list l
Definition: nmg_tri.c:76
void nmg_pr_vu(const struct vertexuse *vu, char *h)
Definition: nmg_pr.c:664
Definition: color.c:51
void print_loopuse_tree(struct bu_list *head, struct loopuse_tree_node *parent, const struct bn_tol *tol)
Definition: nmg_tri.c:2805
void nmg_vsshell(const struct shell *s, const struct nmgregion *r)
Definition: nmg_ck.c:541
#define PT2D_NEXT(tbl, pt)
Definition: nmg_tri.c:72
double bn_angle_measure(vect_t vec, const vect_t x_dir, const vect_t y_dir)
int nmg_keu(register struct edgeuse *eu1)
Definition: nmg_mk.c:1413
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
void insert_node(struct loopuse *lu, struct bu_list *head, struct loopuse_tree_node *parent, const struct bn_tol *tol)
Definition: nmg_tri.c:3189
void nmg_pr_fu_briefly(const struct faceuse *fu, char *h)
Definition: nmg_pr.c:359
void nmg_dump_model(struct model *m)
Definition: nmg_tri.c:2168
NMG_CK_SHELL(s)
HIDDEN void validate_tbl2d(const char *str, struct bu_list *tbl2d, struct faceuse *fu)
Definition: nmg_tri.c:2306
struct pt2d * bot
Definition: nmg_tri.c:85
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
int nmg_loop_split_at_touching_jaunt(struct loopuse *lu, const struct bn_tol *tol)
Definition: nmg_mod.c:2997
int bn_pt3_pt3_equal(const point_t a, const point_t b, const struct bn_tol *tol)
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
void nmg_plot_fu(const char *prefix, const struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_tri.c:1390
#define BU_LIST_HEAD_MAGIC
Definition: magic.h:56
#define NMG_FACEUSE_MAGIC
Definition: magic.h:124
struct loopuse * nmg_find_lu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:411
Definition: vls.h:56
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
int PvsV(struct trap *p, struct trap *v)
Definition: nmg_tri.c:105
double fastf_t
Definition: defines.h:300
#define VPRINT(a, b)
Definition: raytrace.h:1881
eu2
Definition: nmg_mod.c:3875
#define BU_LIST_NOT_HEAD(p, hp)
Definition: list.h:324
void nmg_loop_g(struct loop *l, const struct bn_tol *tol)
Definition: nmg_mk.c:2152
int nmg_edge_g_fuse(const uint32_t *magic_p, const struct bn_tol *tol)
Definition: nmg_fuse.c:1199
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
int nmg_triangulate_rm_degen_loopuse(struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_tri.c:1990
#define NMG_CK_PT2D(_p)
Definition: nmg_tri.c:56
void nmg_triangulate_rm_holes(struct faceuse *fu, struct bu_list *tbl2d, const struct bn_tol *tol)
Definition: nmg_tri.c:1788
fastf_t coord[3]
Definition: nmg_tri.c:77
#define UNLIKELY(expression)
Definition: common.h:282
struct rt_g RTG
Definition: globals.c:39
#define NMG_PT2D_MAGIC
Definition: nmg_tri.c:54
struct model * nmg_find_model(const uint32_t *magic_p_arg)
Definition: nmg_info.c:57