BRL-CAD
nmg_mod.c
Go to the documentation of this file.
1 /* N M G _ M O D . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1991-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_mod.c
23  *
24  * Routines for modifying n-Manifold Geometry data structures.
25  *
26  */
27 /** @} */
28 
29 #include "common.h"
30 
31 #include <stdlib.h>
32 #include <string.h>
33 #include "bio.h"
34 
35 #include "vmath.h"
36 #include "nmg.h"
37 #include "raytrace.h"
38 #include "nurb.h"
39 
40 
41 void
42 nmg_merge_regions(struct nmgregion *r1, struct nmgregion *r2, const struct bn_tol *tol)
43 {
44  struct model *m;
45 
46  NMG_CK_REGION(r1);
47  NMG_CK_REGION(r2);
48  BN_CK_TOL(tol);
49 
50  m = r1->m_p;
51  NMG_CK_MODEL(m);
52 
53  if (r2->m_p != m)
54  bu_bomb("nmg_merge_regions: Tried to merge regions from different models!!");
55 
56  /* move all of r2's faces into r1 */
57  while (BU_LIST_NON_EMPTY(&r2->s_hd)) {
58  struct shell *s;
59 
60  s = BU_LIST_FIRST(shell, &r2->s_hd);
61  BU_LIST_DEQUEUE(&s->l);
62  s->r_p = r1;
63  BU_LIST_APPEND(&r1->s_hd, &s->l);
64  }
65 
66  (void)nmg_kr(r2);
67  nmg_rebound(m, tol);
68 }
69 
70 
71 /************************************************************************
72  * *
73  * SHELL Routines *
74  * *
75  ************************************************************************/
76 
77 
78 /**
79  * A geometric routine to find all pairs of faces in a shell that have
80  * the same plane equation (to within the given tolerance), and
81  * combine them into a single face.
82  *
83  * Note that this may result in some of the vertices being very
84  * slightly off the plane equation, but the geometry routines need to
85  * be prepared for this in any case. If the "simplify" flag is set,
86  * pairs of loops in the face that touch will be combined into a
87  * single loop where possible.
88  *
89  * XXX Perhaps should be recast as "nmg_shell_shared_face_merge()",
90  * leaving all the geometric calculations to the code in nmg_fuse.c ?
91  */
92 void
93 nmg_shell_coplanar_face_merge(struct shell *s, const struct bn_tol *tol, const int simplify)
94 {
95  char *flags;
96  register struct faceuse *fu1, *fu2;
97  register struct face *f1, *f2;
98  struct faceuse *prev_fu;
99  struct face_g_plane *fg1, *fg2;
100 
101  flags = (char *)bu_calloc((s->r_p->m_p->maxindex) * 2, sizeof(char),
102  "nmg_shell_coplanar_face_merge flags[]");
103 
104  /* Visit each face in the shell */
105  for (BU_LIST_FOR(fu1, faceuse, &s->fu_hd)) {
106  plane_t n1;
107 
108  if (BU_LIST_NEXT_IS_HEAD(fu1, &s->fu_hd)) break;
109  f1 = fu1->f_p;
110 
111  if (NMG_INDEX_TEST(flags, f1)) continue;
112  NMG_INDEX_SET(flags, f1);
113 
114  fg1 = f1->g.plane_p;
115 
116  /* For this face, visit all remaining faces in the shell. */
117  /* Don't revisit any faces already considered. */
118  for (fu2 = BU_LIST_NEXT(faceuse, &fu1->l);
119  BU_LIST_NOT_HEAD(fu2, &s->fu_hd);
120  fu2 = BU_LIST_NEXT(faceuse, &fu2->l)
121  ) {
122  plane_t n2;
123 
124  f2 = fu2->f_p;
125 
126  if (NMG_INDEX_TEST(flags, f2)) continue;
127  NMG_INDEX_SET(flags, f2);
128 
129  fg2 = f2->g.plane_p;
130 
131  if (fu2->fumate_p == fu1 || fu1->fumate_p == fu2)
132  bu_bomb("nmg_shell_coplanar_face_merge() mate confusion\n");
133 
134  /* See if face geometry is shared & same direction */
135  if (fg1 != fg2 || f1->flip != f2->flip) {
136  register fastf_t dist;
137  /* If plane equations are different, done */
138 
139  /* if the face bounding boxes are at least distance
140  * distance tolerance apart, skip them.
141  */
142  if (V3RPP_DISJOINT_TOL(f1->min_pt, f1->max_pt, f2->min_pt, f2->max_pt, tol->dist)) {
143  continue;
144  }
145 
146  NMG_GET_FU_PLANE(n1, fu1);
147  NMG_GET_FU_PLANE(n2, fu2);
148 
149  /* compare the distance between the faceuse planes at their center */
150  dist = n1[W] - n2[W];
151  if (!NEAR_ZERO(dist, tol->dist)) {
152  continue;
153  }
154 
155  /* skip faceuse pairs if normals are not in the same general direction. */
156  if (VDOT(n1, n2) < SMALL_FASTF) {
157  continue;
158  }
159 
160  /* test if the vertices from each faceuse is within tolerance of the
161  * plane from the other faceuse
162  */
163  if (nmg_ck_fu_verts(fu2, f1, tol) || nmg_ck_fu_verts(fu1, f2, tol)) {
164  continue;
165  }
166  }
167 
168  /*
169  * Plane equations are the same, within tolerance, or by
170  * shared fg topology. Move everything into fu1, and kill
171  * now empty faceuse, fumate, and face
172  */
173 
174  prev_fu = BU_LIST_PREV(faceuse, &fu2->l);
175  nmg_jf(fu1, fu2);
176  fu2 = prev_fu;
177 
178  /* There is now the option of simplifying the face, by
179  * removing unnecessary edges.
180  */
181  if (simplify) {
182  struct loopuse *lu;
183  for (BU_LIST_FOR(lu, loopuse, &fu1->lu_hd))
184  nmg_simplify_loop(lu);
185  }
186  }
187  }
188 
189  bu_free((char *)flags, "nmg_shell_coplanar_face_merge flags[]");
190 
191  nmg_shell_a(s, tol);
192 
193  if (RTG.NMG_debug & DEBUG_BASIC) {
194  bu_log("nmg_shell_coplanar_face_merge(s=%p, tol=%p, simplify=%d)\n",
195  (void *)s, (void *)tol, simplify);
196  }
197 }
198 
199 
200 /**
201  * Simplify all the faces in this shell, where possible. Under some
202  * circumstances this may result in an empty shell as a result.
203  *
204  * Returns -
205  * 0 If all was OK
206  * 1 If shell is now empty
207  */
208 int
209 nmg_simplify_shell(struct shell *s)
210 {
211  struct faceuse *fu;
212  int ret_val;
213 
214  NMG_CK_SHELL(s);
215 
216  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
217  if (nmg_simplify_face(fu)) {
218  struct faceuse *kfu = fu;
219  fu = BU_LIST_PREV(faceuse, &fu->l);
220  nmg_kfu(kfu);
221  }
222  }
223 
224  ret_val = nmg_shell_is_empty(s);
225 
226  if (RTG.NMG_debug & DEBUG_BASIC) {
227  bu_log("nmg_simplify_shell(s=%p) returns %d\n", (void *)s, ret_val);
228  }
229 
230  return ret_val;
231 }
232 
233 
234 /**
235  * Remove all redundant parts between the different "levels" of a shell.
236  * Remove wire loops that match face loops.
237  * Remove wire edges that match edges in wire loops or face loops.
238  * Remove lone vertices (stored as wire loops on a single vertex) that
239  * match vertices in a face loop, wire loop, or wire edge.
240  */
241 void
242 nmg_rm_redundancies(struct shell *s, const struct bn_tol *tol)
243 {
244  struct faceuse *fu;
245  struct loopuse *lu;
246  struct edgeuse *eu;
247  struct vertexuse *vu;
248  uint32_t magic1;
249 
250  NMG_CK_SHELL(s);
251  BN_CK_TOL(tol);
252 
253  if (BU_LIST_NON_EMPTY(&s->fu_hd)) {
254  /* Compare wire loops -vs- loops in faces */
255  lu = BU_LIST_FIRST(loopuse, &s->lu_hd);
256  while (BU_LIST_NOT_HEAD(lu, &s->lu_hd)) {
257  register struct loopuse *nextlu;
258  NMG_CK_LOOPUSE(lu);
259  NMG_CK_LOOP(lu->l_p);
260  nextlu = BU_LIST_PNEXT(loopuse, lu);
261  if (nmg_is_loop_in_facelist(lu->l_p, &s->fu_hd)) {
262  /* Dispose of wire loop (and mate)
263  * which match face loop */
264  if (nextlu == lu->lumate_p)
265  nextlu = BU_LIST_PNEXT(loopuse, nextlu);
266  nmg_klu(lu);
267  }
268  lu = nextlu;
269  }
270 
271  /* Compare wire edges -vs- edges in loops in faces */
272  eu = BU_LIST_FIRST(edgeuse, &s->eu_hd);
273  while (BU_LIST_NOT_HEAD(eu, &s->eu_hd)) {
274  register struct edgeuse *nexteu;
275  NMG_CK_EDGEUSE(eu);
276  NMG_CK_EDGE(eu->e_p);
277  nexteu = BU_LIST_PNEXT(edgeuse, eu);
278  if (nmg_is_edge_in_facelist(eu->e_p, &s->fu_hd)) {
279  /* Dispose of wire edge (and mate) */
280  if (nexteu == eu->eumate_p)
281  nexteu = BU_LIST_PNEXT(edgeuse, nexteu);
282  (void)nmg_keu(eu);
283  }
284  eu = nexteu;
285  }
286  }
287 
288  /* Compare wire edges -vs- edges in wire loops */
289  eu = BU_LIST_FIRST(edgeuse, &s->eu_hd);
290  while (BU_LIST_NOT_HEAD(eu, &s->eu_hd)) {
291  register struct edgeuse *nexteu;
292  NMG_CK_EDGEUSE(eu);
293  NMG_CK_EDGE(eu->e_p);
294  nexteu = BU_LIST_PNEXT(edgeuse, eu);
295  if (nmg_is_edge_in_looplist(eu->e_p, &s->lu_hd)) {
296  /* Kill edge use and mate */
297  if (nexteu == eu->eumate_p)
298  nexteu = BU_LIST_PNEXT(edgeuse, nexteu);
299  (void)nmg_keu(eu);
300  }
301  eu = nexteu;
302  }
303 
304  /* Compare lone vertices against everything else */
305  /* Individual vertices are stored as wire loops on a single vertex */
306  lu = BU_LIST_FIRST(loopuse, &s->lu_hd);
307  while (BU_LIST_NOT_HEAD(lu, &s->lu_hd)) {
308  register struct loopuse *nextlu;
309  NMG_CK_LOOPUSE(lu);
310  nextlu = BU_LIST_PNEXT(loopuse, lu);
311  magic1 = BU_LIST_FIRST_MAGIC(&lu->down_hd);
312  if (magic1 != NMG_VERTEXUSE_MAGIC) {
313  lu = nextlu;
314  continue;
315  }
316  vu = BU_LIST_PNEXT(vertexuse, &lu->down_hd);
317  NMG_CK_VERTEXUSE(vu);
318  NMG_CK_VERTEX(vu->v_p);
319  if (nmg_is_vertex_in_facelist(vu->v_p, &s->fu_hd) ||
320  nmg_is_vertex_in_looplist(vu->v_p, &s->lu_hd, 0) ||
321  nmg_is_vertex_in_edgelist(vu->v_p, &s->eu_hd)) {
322  /* Kill lu and mate */
323  if (nextlu == lu->lumate_p)
324  nextlu = BU_LIST_PNEXT(loopuse, nextlu);
325  nmg_klu(lu);
326  lu = nextlu;
327  continue;
328  }
329  lu = nextlu;
330  }
331 
332  /* There really shouldn't be a lone vertex by now */
333  if (s->vu_p) bu_log("nmg_rm_redundancies() lone vertex?\n");
334 
335  /* get rid of matching OT_SAME/OT_OPPOSITE loops in same faceuse */
336  fu = BU_LIST_FIRST(faceuse, &s->fu_hd);
337  while (BU_LIST_NOT_HEAD(&fu->l, &s->fu_hd)) {
338  struct faceuse *next_fu;
339  int lu1_count;
340  int lu_count;
341 
342  NMG_CK_FACEUSE(fu);
343 
344  if (fu->orientation != OT_SAME) {
345  fu = BU_LIST_NEXT(faceuse, &fu->l);
346  continue;
347  }
348 
349  next_fu = BU_LIST_NEXT(faceuse, &fu->l);
350  if (next_fu == fu->fumate_p)
351  next_fu = BU_LIST_NEXT(faceuse, &next_fu->l);
352 
353  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
354  while (BU_LIST_NOT_HEAD(&lu->l, &fu->lu_hd)) {
355  struct loopuse *next_lu;
356  struct loopuse *lu1;
357 
358  NMG_CK_LOOPUSE(lu);
359 
360  next_lu = BU_LIST_NEXT(loopuse, &lu->l);
361 
362  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
363  lu = next_lu;
364  continue;
365  }
366 
367  /* count edges in lu */
368  lu_count = 0;
369  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd))
370  lu_count++;
371 
372  /* look for anther loopuse with opposite orientation */
373  lu1 = BU_LIST_FIRST(loopuse, &fu->lu_hd);
374  while (BU_LIST_NOT_HEAD(&lu1->l, &fu->lu_hd)) {
375  struct loopuse *next_lu1;
376 
377  NMG_CK_LOOPUSE(lu1);
378 
379  next_lu1 = BU_LIST_PNEXT(loopuse, &lu1->l);
380 
381  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) != NMG_EDGEUSE_MAGIC) {
382  lu1 = next_lu1;
383  continue;
384  }
385 
386  if (lu1 == lu) {
387  lu1 = next_lu1;
388  continue;
389  }
390 
391  if (lu1->orientation == lu->orientation) {
392  lu1 = next_lu1;
393  continue;
394  }
395 
396  /* count edges in lu1 */
397  lu1_count = 0;
398  for (BU_LIST_FOR(eu, edgeuse, &lu1->down_hd))
399  lu1_count++;
400 
401  if (lu_count != lu1_count) {
402  lu1 = next_lu1;
403  continue;
404  }
405 
406  if (nmg_classify_lu_lu(lu, lu1, tol) != NMG_CLASS_AonBshared) {
407  lu1 = next_lu1;
408  continue;
409  }
410 
411  /* lu and lu1 are identical, but with opposite orientations
412  * kill them both
413  */
414 
415  if (next_lu1 == lu)
416  next_lu1 = BU_LIST_NEXT(loopuse, &next_lu1->l);
417 
418  if (next_lu == lu1)
419  next_lu = BU_LIST_NEXT(loopuse, &next_lu->l);
420 
421  (void)nmg_klu(lu);
422  if (nmg_klu(lu1)) {
423  /* faceuse is empty, kill it */
424  if (nmg_kfu(fu)) {
425  /* shell is empty, set "nexts" to get out */
426  next_fu = (struct faceuse *)(&s->fu_hd);
427  next_lu = (struct loopuse *)NULL;
428  } else {
429  /* shell not empty, but fu is */
430  next_lu = (struct loopuse *)NULL;
431  }
432  }
433  break;
434  }
435 
436  if (!next_lu)
437  break;
438 
439  lu = next_lu;
440  }
441  fu = next_fu;
442  }
443 
444  /* get rid of redundant loops in same fu (OT_SAME within an OT_SAME), etc. */
445  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
446  NMG_CK_FACEUSE(fu);
447 
448  if (fu->orientation != OT_SAME)
449  continue;
450 
451  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
452  struct loopuse *lu1;
453 
454  NMG_CK_LOOPUSE(lu);
455 
456  /* look for another loop with same orientation */
457  lu1 = BU_LIST_FIRST(loopuse, &fu->lu_hd);
458  while (BU_LIST_NOT_HEAD(&lu1->l, &fu->lu_hd)) {
459  struct loopuse *next_lu;
460  struct loopuse *lu2;
461  int found;
462 
463  NMG_CK_LOOPUSE(lu1);
464 
465  next_lu = BU_LIST_PNEXT(loopuse, &lu1->l);
466 
467  if (lu1 == lu) {
468  lu1 = next_lu;
469  continue;
470  }
471 
472  if (lu1->orientation != lu->orientation) {
473  lu1 = next_lu;
474  continue;
475  }
476 
477  if (nmg_classify_lu_lu(lu1, lu, tol) != NMG_CLASS_AinB) {
478  lu1 = next_lu;
479  continue;
480  }
481 
482  /* lu1 is within lu and has same orientation. Check
483  * if there is a loop with opposite orientation
484  * between them.
485  */
486  found = 0;
487  for (BU_LIST_FOR(lu2, loopuse, &fu->lu_hd)) {
488  int class1, class2;
489 
490  NMG_CK_LOOPUSE(lu2);
491 
492  if (lu2 == lu || lu2 == lu1)
493  continue;
494 
495  if (lu2->orientation == lu->orientation)
496  continue;
497 
498  class1 = nmg_classify_lu_lu(lu2, lu, tol);
499  class2 = nmg_classify_lu_lu(lu1, lu2, tol);
500 
501  if (class1 == NMG_CLASS_AinB &&
502  class2 == NMG_CLASS_AinB) {
503  found = 1;
504  break;
505  }
506  }
507  if (!found) {
508  /* lu1 is a redundant loop */
509  (void) nmg_klu(lu1);
510  }
511  lu1 = next_lu;
512  }
513  }
514  }
515 
516  /* get rid of redundant loops in same fu where there are two
517  * identical loops, but with opposite orientation
518  */
519  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
520  if (fu->orientation != OT_SAME)
521  continue;
522 
523  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
524  struct loopuse *lu1;
525 
526  if (lu->orientation != OT_SAME)
527  continue;
528 
529  lu1 = BU_LIST_FIRST(loopuse, &fu->lu_hd);
530  while (BU_LIST_NOT_HEAD(&lu1->l, &fu->lu_hd)) {
531  int nmg_class;
532  struct loopuse *next_lu;
533 
534  next_lu = BU_LIST_PNEXT(loopuse, &lu1->l);
535 
536  if (lu1 == lu || lu1->orientation != OT_OPPOSITE) {
537  lu1 = next_lu;
538  continue;
539  }
540 
541  nmg_class = nmg_classify_lu_lu(lu, lu1, tol);
542 
543  if (nmg_class == NMG_CLASS_AonBshared) {
544  nmg_klu(lu1); /* lu1 is redundant */
545  }
546 
547  lu1 = next_lu;
548  }
549  }
550  }
551 
552  if (RTG.NMG_debug & DEBUG_BASIC) {
553  bu_log("nmg_rm_redundancies(s=%p)\n", (void *)s);
554  }
555 }
556 
557 
558 /**
559  * Remove those pesky little vertex-only loops of orientation
560  * "orient". Typically these will be OT_BOOLPLACE markers created in
561  * the process of doing intersections for the boolean operations.
562  */
563 void
564 nmg_sanitize_s_lv(struct shell *s, int orient)
565 {
566  struct faceuse *fu;
567  struct loopuse *lu;
568  pointp_t pt;
569 
570  NMG_CK_SHELL(s);
571 
572  /* sanitize the loop lists in the faces of the shell */
573  fu = BU_LIST_FIRST(faceuse, &s->fu_hd);
574  while (BU_LIST_NOT_HEAD(fu, &s->fu_hd)) {
575 
576  /* all of those vertex-only/orient loops get deleted
577  */
578  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
579  while (BU_LIST_NOT_HEAD(lu, &fu->lu_hd)) {
580  if (lu->orientation == orient) {
581  lu = BU_LIST_PNEXT(loopuse, lu);
582  nmg_klu(BU_LIST_PLAST(loopuse, lu));
583  } else if (lu->orientation == OT_UNSPEC &&
584  BU_LIST_FIRST_MAGIC(&lu->down_hd) ==
586  register struct vertexuse *vu;
587  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
588  pt = vu->v_p->vg_p->coord;
589  VPRINT("nmg_sanitize_s_lv() OT_UNSPEC at", pt);
590  lu = BU_LIST_PNEXT(loopuse, lu);
591  } else {
592  lu = BU_LIST_PNEXT(loopuse, lu);
593  }
594  }
595 
596  /* step forward, avoiding re-processing our mate (which would
597  * have had its loops processed with ours)
598  */
599  if (BU_LIST_PNEXT(faceuse, fu) == fu->fumate_p)
600  fu = BU_LIST_PNEXT_PNEXT(faceuse, fu);
601  else
602  fu = BU_LIST_PNEXT(faceuse, fu);
603 
604  /* If previous faceuse has no more loops, kill it */
605  if (BU_LIST_IS_EMPTY(&(BU_LIST_PLAST(faceuse, fu))->lu_hd)) {
606  /* All of the loopuses of the previous face were
607  * BOOLPLACE's so the face will now go away
608  */
609  nmg_kfu(BU_LIST_PLAST(faceuse, fu));
610  }
611  }
612 
613  /* Sanitize any wire/vertex loops in the shell */
614  lu = BU_LIST_FIRST(loopuse, &s->lu_hd);
615  while (BU_LIST_NOT_HEAD(lu, &s->lu_hd)) {
616  if (lu->orientation == orient) {
617  lu = BU_LIST_PNEXT(loopuse, lu);
618  nmg_klu(BU_LIST_PLAST(loopuse, lu));
619  } else if (lu->orientation == OT_UNSPEC &&
620  BU_LIST_FIRST_MAGIC(&lu->down_hd) ==
622  register struct vertexuse *vu;
623  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
624  pt = vu->v_p->vg_p->coord;
625  VPRINT("nmg_sanitize_s_lv() OT_UNSPEC at", pt);
626  lu = BU_LIST_PNEXT(loopuse, lu);
627  } else {
628  lu = BU_LIST_PNEXT(loopuse, lu);
629  }
630  }
631 
632  if (RTG.NMG_debug & DEBUG_BASIC) {
633  bu_log("nmg_sanitize_s_lv(s=%p, orient=%d)\n", (void *)s, orient);
634  }
635 }
636 
637 
638 /**
639  * For every loop in a shell, invoke nmg_split_touchingloops() on it.
640  *
641  * Needed before starting classification, to separate interior
642  * (touching) loop segments into true interior loops, so each can be
643  * processed separately.
644  */
645 void
646 nmg_s_split_touchingloops(struct shell *s, const struct bn_tol *tol)
647 {
648  struct faceuse *fu;
649  struct loopuse *lu;
650 
651  NMG_CK_SHELL(s);
652  BN_CK_TOL(tol);
653 
654  if (RTG.NMG_debug & DEBUG_BASIC) {
655  bu_log("nmg_s_split_touching_loops(s=%p, tol=%p) START\n",
656  (void *)s, (void *)tol);
657  }
658 
659  /* First, handle any splitting */
660  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
661  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
662  (void)nmg_loop_split_at_touching_jaunt(lu, tol);
663  nmg_split_touchingloops(lu, tol);
664  }
665  }
666  for (BU_LIST_FOR(lu, loopuse, &s->lu_hd)) {
667  (void)nmg_loop_split_at_touching_jaunt(lu, tol);
668  nmg_split_touchingloops(lu, tol);
669  }
670 
671  /* Second, reorient any split loop fragments */
672  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
673  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
674  if (lu->orientation != OT_UNSPEC) continue;
675  nmg_lu_reorient(lu);
676  }
677  }
678 
679  if (RTG.NMG_debug & DEBUG_BASIC) {
680  bu_log("nmg_s_split_touching_loops(s=%p, tol=%p) END\n",
681  (void *)s, (void *)tol);
682  }
683 }
684 
685 
686 /**
687  * For every loop in a shell, invoke nmg_join_touchingloops() on it.
688  */
689 void
690 nmg_s_join_touchingloops(struct shell *s, const struct bn_tol *tol)
691 {
692  struct faceuse *fu;
693  struct loopuse *lu;
694 
695  NMG_CK_SHELL(s);
696  BN_CK_TOL(tol);
697 
698  if (RTG.NMG_debug & DEBUG_BASIC) {
699  bu_log("nmg_s_join_touching_loops(s=%p, tol=%p) START\n",
700  (void *)s, (void *)tol);
701  }
702 
703  /* First, handle any joining */
704  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
705  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
707  }
708  }
709  for (BU_LIST_FOR(lu, loopuse, &s->lu_hd)) {
711  }
712 
713  /* Second, reorient any disoriented loop fragments */
714  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
715  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
716  if (lu->orientation != OT_UNSPEC) continue;
717  nmg_lu_reorient(lu);
718  }
719  }
720 
721  if (RTG.NMG_debug & DEBUG_BASIC) {
722  bu_log("nmg_s_join_touching_loops(s=%p, tol=%p) END\n",
723  (void *)s, (void *)tol);
724  }
725 }
726 
727 
728 /**
729  * Join two shells into one.
730  *
731  * This is mostly an up-pointer re-labeling activity, as it is left up
732  * to the caller to ensure that there are no non-explicit
733  * intersections.
734  *
735  * Upon return, s2 will no longer exist.
736  *
737  * The 'tol' arg is used strictly for printing purposes.
738  */
739 void
740 nmg_js(register struct shell *s1, register struct shell *s2, const struct bn_tol *tol)
741 /* destination */
742 /* source */
743 
744 {
745  struct faceuse *fu2;
746  struct faceuse *nextfu;
747  struct loopuse *lu;
748  struct loopuse *nextlu;
749  struct edgeuse *eu;
750  struct edgeuse *nexteu;
751  struct vertexuse *vu;
752 
753  NMG_CK_SHELL(s1);
754  NMG_CK_SHELL(s2);
755  BN_CK_TOL(tol);
756 
757  if (RTG.NMG_debug & DEBUG_BASIC) {
758  bu_log("nmg_js(s1=%p, s2=%p) START\n", (void *)s1, (void *)s2);
759  }
760 
761  if (RTG.NMG_debug & DEBUG_VERIFY)
762  nmg_vshell(&s1->r_p->s_hd, s1->r_p);
763 
764  /*
765  * For each face in the shell, process all the loops in the face,
766  * and then handle the face and all loops as a unit.
767  */
768  fu2 = BU_LIST_FIRST(faceuse, &s2->fu_hd);
769  while (BU_LIST_NOT_HEAD(fu2, &s2->fu_hd)) {
770  struct faceuse *fu1;
771 
772  nextfu = BU_LIST_PNEXT(faceuse, fu2);
773 
774  /* Faceuse mates will be handled at same time as OT_SAME fu */
775  if (fu2->orientation != OT_SAME) {
776  fu2 = nextfu;
777  continue;
778  }
779 
780  /* Consider this face */
781  NMG_CK_FACEUSE(fu2);
782  NMG_CK_FACE(fu2->f_p);
783 
784  if (nextfu == fu2->fumate_p)
785  nextfu = BU_LIST_PNEXT(faceuse, nextfu);
786 
787  /* If there is a face in the destination shell that shares
788  * face geometry with this face, then move all the loops into
789  * the other face, and eliminate this redundant face.
790  */
791  fu1 = nmg_find_fu_with_fg_in_s(s1, fu2);
792  if (fu1 && fu1->orientation == OT_SAME) {
793  if (RTG.NMG_debug & DEBUG_BASIC)
794  bu_log("nmg_js(): shared face_g_plane, doing nmg_jf()\n");
795  nmg_jf(fu1, fu2);
796  /* fu2 pointer is invalid here */
797  fu2 = fu1;
798  } else {
799  nmg_mv_fu_between_shells(s1, s2, fu2);
800  }
801 
802  fu2 = nextfu;
803  }
804 
805  /*
806  * For each loop in the shell, process. Each loop is either a
807  * wire-loop, or a vertex-with-self-loop. Both get the same
808  * treatment.
809  */
810  lu = BU_LIST_FIRST(loopuse, &s2->lu_hd);
811  while (BU_LIST_NOT_HEAD(lu, &s2->lu_hd)) {
812  nextlu = BU_LIST_PNEXT(loopuse, lu);
813 
814  NMG_CK_LOOPUSE(lu);
815  NMG_CK_LOOP(lu->l_p);
816  if (nextlu == lu->lumate_p)
817  nextlu = BU_LIST_PNEXT(loopuse, nextlu);
818 
819  nmg_mv_lu_between_shells(s1, s2, lu);
820  lu = nextlu;
821  }
822 
823  /*
824  * For each wire-edge in the shell, ...
825  */
826  eu = BU_LIST_FIRST(edgeuse, &s2->eu_hd);
827  while (BU_LIST_NOT_HEAD(eu, &s2->eu_hd)) {
828  nexteu = BU_LIST_PNEXT(edgeuse, eu);
829 
830  /* Consider this edge */
831  NMG_CK_EDGEUSE(eu);
832  NMG_CK_EDGE(eu->e_p);
833  if (nexteu == eu->eumate_p)
834  nexteu = BU_LIST_PNEXT(edgeuse, nexteu);
835  nmg_mv_eu_between_shells(s1, s2, eu);
836  eu = nexteu;
837  }
838 
839  /*
840  * Final case: shell of a single vertexuse
841  */
842  vu = s2->vu_p;
843  if (vu) {
844  NMG_CK_VERTEXUSE(vu);
845  NMG_CK_VERTEX(vu->v_p);
846  nmg_mv_vu_between_shells(s1, s2, vu);
847  s2->vu_p = (struct vertexuse *)0; /* sanity */
848  }
849 
850  if (BU_LIST_NON_EMPTY(&s2->fu_hd)) {
851  bu_bomb("nmg_js(): s2 still has faces!\n");
852  }
853  if (BU_LIST_NON_EMPTY(&s2->lu_hd)) {
854  bu_bomb("nmg_js(): s2 still has wire loops!\n");
855  }
856  if (BU_LIST_NON_EMPTY(&s2->eu_hd)) {
857  bu_bomb("nmg_js(): s2 still has wire edges!\n");
858  }
859  if (s2->vu_p) {
860  bu_bomb("nmg_js(): s2 still has verts!\n");
861  }
862 
863  /* s2 is completely empty now, which is an invalid condition */
864  nmg_ks(s2);
865 
866  /* Some edges may need faceuse parity touched up. */
867  nmg_s_radial_harmonize(s1, tol);
868 
869  if (RTG.NMG_debug & DEBUG_VERIFY)
870  nmg_vshell(&s1->r_p->s_hd, s1->r_p);
871 
872  if (RTG.NMG_debug & DEBUG_BASIC) {
873  bu_log("nmg_js(s1=%p, s2=%p) END\n", (void *)s1, (void *)s2);
874  }
875 }
876 
877 
878 /**
879  * Reverse the surface normals, and invert the orientation state of
880  * all faceuses in a shell.
881  *
882  * This turns the shell "inside out", such as might be needed for the
883  * right hand side term of a subtraction operation.
884  *
885  * While this function is operating, the parity of faceuses radially
886  * around edgeuses is disrupted, hence this atomic interface to invert
887  * the shell.
888  */
889 void
890 nmg_invert_shell(struct shell *s)
891 {
892  struct model *m;
893  struct faceuse *fu;
894  char *tags;
895 
896  NMG_CK_SHELL(s);
897  m = s->r_p->m_p;
898  NMG_CK_MODEL(m);
899 
900  if (RTG.NMG_debug & DEBUG_BASIC) {
901  bu_log("nmg_invert_shell(%p)\n", (void *)s);
902  }
903 
904  /* Allocate map of faces visited */
905  tags = (char *)bu_calloc(m->maxindex+1, 1, "nmg_invert_shell() tags[]");
906 
907  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
908  NMG_CK_FACEUSE(fu);
909  /* By tagging on faces, marks fu and fumate together */
910  if (NMG_INDEX_TEST(tags, fu->f_p)) continue;
911  NMG_INDEX_SET(tags, fu->f_p);
912  /* Process fu and fumate together */
913  nmg_reverse_face(fu);
914  }
915  bu_free(tags, "nmg_invert_shell() tags[]");
916 }
917 
918 
919 /************************************************************************
920  * *
921  * FACE Routines *
922  * *
923  ************************************************************************/
924 
925 
926 /**
927  * Create a face with exactly one exterior loop (and no holes), given
928  * an array of pointers to struct vertex pointers. Intended to help
929  * create a "3-manifold" shell, where each edge has only two faces
930  * alongside of it. (Shades of winged edges!)
931  *
932  * "verts" is an array of "n" pointers to pointers to (struct vertex).
933  * "s" is the parent shell for the new face.
934  *
935  * The new face will consist of a single loop made from n edges
936  * between the n vertices. Before an edge is created between a pair
937  * of vertices, we check to see if there is already an edge with
938  * exactly one edgeuse+mate (in this shell) that runs between the two
939  * vertices. If such an edge can be found, the newly created
940  * edgeuses will just use the existing edge. This means that no
941  * special call to nmg_gluefaces() is needed later.
942  *
943  * If a pointer in verts is a pointer to a null vertex pointer, a new
944  * vertex is created. In this way, new vertices can be created
945  * conveniently within a user's list of known vertices
946  *
947  * verts pointers to struct vertex vertex structs
948  *
949  * ------- --------
950  * 0 | +--|-------->| +--|--------------------------> (struct vertex)
951  * ------- -------- ---------
952  * 1 | +--|------------------------>| +---|---------> (struct vertex)
953  * ------- -------- ---------
954  * 2 | +--|-------->| +--|--------------------------> (struct vertex)
955  * ------- --------
956  * ...
957  * ------- ---------
958  * n | +--|------------------------>| +---|---------> (struct vertex)
959  * ------- ---------
960  *
961  *
962  * The vertices *must* be listed in "counter-clockwise" (CCW) order.
963  * This routine makes only topology, without reference to any
964  * geometry.
965  *
966  * Note that this routine inserts new vertices (by edge use splitting)
967  * at the head of the loop, which reverses the order. Therefore, the
968  * caller's vertices are traversed in reverse order to counter this
969  * behavior, and to effect the proper vertex order in the final face
970  * loop.
971  *
972  * Also note that this routine uses one level more of indirection in
973  * the verts[] array than nmg_cface().
974  *
975  * The lu's list of eu's traverses the verts[] array in order
976  * specified by the caller. Imagine that.
977  */
978 struct faceuse *
979 nmg_cmface(struct shell *s, struct vertex ***verts, int n)
980 {
981  struct faceuse *fu;
982  struct edgeuse *eu, *eur, *euold = NULL;
983  struct loopuse *lu;
984  struct vertexuse *vu;
985  int i;
986 
987  NMG_CK_SHELL(s);
988 
989  if (n < 1) {
990  bu_log("nmg_cmface(s=%p, verts=%p, n=%d.)\n",
991  (void *)s, (void *)verts, n);
992  bu_bomb("nmg_cmface() trying to make bogus face\n");
993  }
994 
995  /* make sure verts points to some real storage */
996  if (!verts) {
997  bu_log("nmg_cmface(s=%p, verts=%p, n=%d.) null pointer to array start\n",
998  (void *)s, (void *)verts, n);
999  bu_bomb("nmg_cmface\n");
1000  }
1001 
1002  /* validate each of the pointers in verts */
1003  for (i = 0; i < n; ++i) {
1004  if (verts[i]) {
1005  if (*verts[i]) {
1006  /* validate the vertex pointer */
1007  NMG_CK_VERTEX(*verts[i]);
1008  }
1009  } else {
1010  bu_log("nmg_cmface(s=%p, verts=%p, n=%d.) verts[%d]=NULL\n",
1011  (void *)s, (void *)verts, n, i);
1012  bu_bomb("nmg_cmface\n");
1013  }
1014  }
1015 
1016  lu = nmg_mlv(&s->l.magic, *verts[0], OT_SAME);
1017  fu = nmg_mf(lu);
1018  fu->orientation = OT_SAME;
1019  fu->fumate_p->orientation = OT_OPPOSITE;
1020  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1021  NMG_CK_VERTEXUSE(vu);
1022  eu = nmg_meonvu(vu);
1023  NMG_CK_EDGEUSE(eu);
1024 
1025  if (!(*verts[0])) {
1026  NMG_CK_VERTEXUSE(eu->vu_p);
1027  NMG_CK_VERTEX(eu->vu_p->v_p);
1028  *verts[0] = eu->vu_p->v_p;
1029  }
1030 
1031  for (i = n-1; i > 0; i--) {
1032  /* Get the edgeuse most recently created */
1033  euold = BU_LIST_FIRST(edgeuse, &lu->down_hd);
1034  NMG_CK_EDGEUSE(euold);
1035 
1036  if (RTG.NMG_debug & DEBUG_CMFACE)
1037  bu_log("nmg_cmface() euold: %8p\n", (void *)euold);
1038 
1039  /* look for pre-existing edge between these vertices */
1040  if (*verts[i]) {
1041  /* look for an existing edge to share */
1042  eur = nmg_findeu(*verts[(i+1)%n], *verts[i], s, euold, 1);
1043  eu = nmg_eusplit(*verts[i], euold, 0);
1044  if (eur) {
1045  nmg_je(eur, eu);
1046 
1047  if (RTG.NMG_debug & DEBUG_CMFACE)
1048  bu_log("nmg_cmface() found another edgeuse (%8p) between %8p and %8p\n",
1049  (void *)eur, (void *)*verts[(i+1)%n], (void *)*verts[i]);
1050  } else {
1051  if (RTG.NMG_debug & DEBUG_CMFACE)
1052  bu_log("nmg_cmface() didn't find edge from verts[%d]%8p to verts[%d]%8p\n",
1053  i+1, (void *)*verts[(i+1)%n],
1054  i, (void *)*verts[i]);
1055  }
1056  } else {
1057  eu = nmg_eusplit(*verts[i], euold, 0);
1058  *verts[i] = eu->vu_p->v_p;
1059 
1060  if (RTG.NMG_debug & DEBUG_CMFACE) {
1061  bu_log("nmg_cmface() *verts[%d] was null, is now %8p\n",
1062  i, (void *)*verts[i]);
1063  }
1064  }
1065  }
1066 
1067  if (n > 1) {
1068  eur = nmg_findeu(*verts[0], *verts[1], s, euold, 1);
1069  if (eur) {
1070  nmg_je(eur, euold);
1071  } else {
1072  if (RTG.NMG_debug & DEBUG_CMFACE)
1073  bu_log("nmg_cmface() didn't find edge from verts[%d]%8p to verts[%d]%8p\n",
1074  0, (void *)*verts[0],
1075  1, (void *)*verts[1]);
1076  }
1077  }
1078 
1079  if (RTG.NMG_debug & DEBUG_BASIC) {
1080  /* Sanity check */
1081  euold = BU_LIST_FIRST(edgeuse, &lu->down_hd);
1082  NMG_CK_EDGEUSE(euold);
1083  if (euold->vu_p->v_p != *verts[0]) {
1084  bu_log("ERROR nmg_cmface() lu first vert s/b %p, was %p\n",
1085  (void *)*verts[0], (void *)euold->vu_p->v_p);
1086  for (i = 0; i < n; i++) {
1087  bu_log(" *verts[%2d]=%p, eu->vu_p->v_p=%p\n",
1088  i, (void *)*verts[i], (void *)euold->vu_p->v_p);
1089  euold = BU_LIST_PNEXT_CIRC(edgeuse, &euold->l);
1090  }
1091  bu_bomb("nmg_cmface() bogus eu ordering\n");
1092  }
1093  }
1094 
1095  if (RTG.NMG_debug & DEBUG_BASIC) {
1096  bu_log("nmg_cmface(s=%p, verts[]=%p, n=%d) fu=%p\n",
1097  (void *)s, (void *)verts, n,
1098  (void *)fu);
1099  }
1100  return fu;
1101 }
1102 
1103 
1104 /**
1105  * Create a loop within a face, given a list of vertices.
1106  *
1107  * "verts" is an array of "n" pointers to (struct vertex). "s" is the
1108  * parent shell for the new face. The face will consist of a single
1109  * loop made from edges between the n vertices.
1110  *
1111  * If verts is a null pointer (no vertex list), all vertices of the
1112  * face will be new points. Otherwise, verts is a pointer to a list
1113  * of vertices to use in creating the face/loop. Null entries within
1114  * the list will cause a new vertex to be created for that point.
1115  * Such new vertices will be inserted into the list for return to the
1116  * caller.
1117  *
1118  * The vertices should be listed in "counter-clockwise" (CCW) order if
1119  * this is an ordinary face (loop), and in "clockwise" (CW) order if
1120  * this is an interior ("hole" or "subtracted") face (loop). This
1121  * routine makes only topology, without reference to any geometry.
1122  *
1123  * Note that this routine inserts new vertices (by edge use splitting)
1124  * at the head of the loop, which reverses the order. Therefore, the
1125  * caller's vertices are traversed in reverse order to counter this
1126  * behavior, and to effect the proper vertex order in the final face
1127  * loop.
1128  */
1129 struct faceuse *
1130 nmg_cface(struct shell *s, struct vertex **verts, int n)
1131 {
1132  struct faceuse *fu;
1133  struct edgeuse *eu;
1134  struct loopuse *lu;
1135  struct vertexuse *vu;
1136  int i;
1137 
1138  NMG_CK_SHELL(s);
1139  if (n < 1) {
1140  bu_log("nmg_cface(s=%p, verts=%p, n=%d.)\n",
1141  (void *)s, (void *)verts, n);
1142  bu_bomb("nmg_cface() trying to make bogus face\n");
1143  }
1144 
1145  if (verts) {
1146  for (i = 0; i < n; ++i) {
1147  if (verts[i]) {
1148  NMG_CK_VERTEX(verts[i]);
1149  }
1150  }
1151  lu = nmg_mlv(&s->l.magic, verts[n-1], OT_SAME);
1152  fu = nmg_mf(lu);
1153  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1154  eu = nmg_meonvu(vu);
1155 
1156  if (!verts[n-1])
1157  verts[n-1] = eu->vu_p->v_p;
1158 
1159  for (i = n-2; i >= 0; i--) {
1160  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
1161  eu = nmg_eusplit(verts[i], eu, 0);
1162  if (!verts[i])
1163  verts[i] = eu->vu_p->v_p;
1164  }
1165 
1166  } else {
1167  lu = nmg_mlv(&s->l.magic, (struct vertex *)NULL, OT_SAME);
1168  fu = nmg_mf(lu);
1169  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1170  eu = nmg_meonvu(vu);
1171  while (--n) {
1172  (void)nmg_eusplit((struct vertex *)NULL, eu, 0);
1173  }
1174  }
1175  if (RTG.NMG_debug & DEBUG_BASIC) {
1176  bu_log("nmg_cface(s=%p, verts[]=%p, n=%d) fu=%p\n",
1177  (void *)s, (void *)verts, n,
1178  (void *)fu);
1179  }
1180  return fu;
1181 }
1182 
1183 
1184 /**
1185  * Create a new loop within a face, given a list of vertices.
1186  * Modified version of nmg_cface().
1187  *
1188  * "verts" is an array of "n" pointers to (struct vertex). "s" is the
1189  * parent shell for the new face. The face will consist of a single
1190  * loop made from edges between the n vertices.
1191  *
1192  * If verts is a null pointer (no vertex list), all vertices of the
1193  * face will be new points. Otherwise, verts is a pointer to a list
1194  * of vertices to use in creating the face/loop. Null entries within
1195  * the list will cause a new vertex to be created for that point.
1196  * Such new vertices will be inserted into the list for return to the
1197  * caller.
1198  *
1199  * The vertices should be listed in "counter-clockwise" (CCW) order if
1200  * this is an ordinary face (loop), and in "clockwise" (CW) order if
1201  * this is an interior ("hole" or "subtracted") face (loop). This
1202  * routine makes only topology, without reference to any geometry.
1203  *
1204  * Note that this routine inserts new vertices (by edge use splitting)
1205  * at the head of the loop, which reverses the order. Therefore, the
1206  * caller's vertices are traversed in reverse order to counter this
1207  * behavior, and to effect the proper vertex order in the final face
1208  * loop.
1209  */
1210 struct faceuse *
1211 nmg_add_loop_to_face(struct shell *s, struct faceuse *fu, struct vertex **verts, int n, int dir)
1212 {
1213  int i;
1214  struct edgeuse *eu;
1215  struct loopuse *lu;
1216  struct vertexuse *vu;
1217 
1218  NMG_CK_SHELL(s);
1219  if (n < 1) {
1220  bu_log("nmg_add_loop_to_face(s=%p, verts=%p, n=%d.)\n",
1221  (void *)s, (void *)verts, n);
1222  bu_bomb("nmg_add_loop_to_face: request to make 0 faces\n");
1223  }
1224 
1225  if (verts) {
1226  if (!fu) {
1227  lu = nmg_mlv(&s->l.magic, verts[n-1], dir);
1228  fu = nmg_mf(lu);
1229  } else {
1230  lu = nmg_mlv(&fu->l.magic, verts[n-1], dir);
1231  }
1232  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1233  eu = nmg_meonvu(vu);
1234  if (!verts[n-1])
1235  verts[n-1] = eu->vu_p->v_p;
1236 
1237  for (i = n-2; i >= 0; i--) {
1238  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
1239  eu = nmg_eusplit(verts[i], eu, 0);
1240  if (!verts[i])
1241  verts[i] = eu->vu_p->v_p;
1242  }
1243  } else {
1244  if (!fu) {
1245  lu = nmg_mlv(&s->l.magic, (struct vertex *)NULL, dir);
1246  fu = nmg_mf(lu);
1247  } else {
1248  lu = nmg_mlv(&fu->l.magic, (struct vertex *)NULL, dir);
1249  }
1250  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1251  eu = nmg_meonvu(vu);
1252  while (--n) {
1253  (void)nmg_eusplit((struct vertex *)NULL, eu, 0);
1254  }
1255  }
1256  if (RTG.NMG_debug & DEBUG_BASIC) {
1257  bu_log("nmg_add_loop_to_face(s=%p, fu=%p, verts[]=%p, n=%d, %s) fu=%p\n",
1258  (void *)s, (void *)fu, (void *)verts, n, nmg_orientation(dir),
1259  (void *)fu);
1260  }
1261  return fu;
1262 }
1263 
1264 
1265 /**
1266  * Given a convex face that has been constructed with edges listed in
1267  * counter-clockwise (CCW) order, compute the surface normal and plane
1268  * equation for this face.
1269  *
1270  * D C
1271  * *-------------------*
1272  * | |
1273  * | .<........... |
1274  * ^ N | . ^ | ^
1275  * | \ | . counter- . | |
1276  * | \ | . clock . | |
1277  * |C-B \ | . wise . | |C-B
1278  * | \ | v . | |
1279  * | \ | ...........>. | |
1280  * \| |
1281  * *-------------------*
1282  * A B
1283  * <-----
1284  * A-B
1285  *
1286  * If the vertices in the loop are given in the order A B C D (e.g.,
1287  * counter-clockwise), then the outward pointing surface normal can be
1288  * computed as:
1289  *
1290  * N = (C-B) x (A-B)
1291  *
1292  * This is the "right hand rule".
1293  *
1294  * For reference, note that a vector which points "into" the loop can
1295  * be subsequently found by taking the cross product of the surface
1296  * normal and any edge vector, e.g.:
1297  *
1298  * Left = N x (B-A)
1299  * or Left = N x (C-B)
1300  *
1301  * This routine will skip on past edges that start and end on the same
1302  * vertex, in an attempt to avoid trouble. However, the loop *must*
1303  * be convex for this routine to work. Otherwise, the surface normal
1304  * may be inadvertently reversed.
1305  *
1306  * Returns -
1307  * 0 OK
1308  * -1 failure
1309  */
1310 int
1311 nmg_fu_planeeqn(struct faceuse *fu, const struct bn_tol *tol)
1312 {
1313  struct edgeuse *eu, *eu_final, *eu_next;
1314  struct loopuse *lu;
1315  plane_t plane;
1316  struct vertex *a, *b, *c;
1317  register int both_equal;
1318 
1319  BN_CK_TOL(tol);
1320 
1321  NMG_CK_FACEUSE(fu);
1322  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
1323  NMG_CK_LOOPUSE(lu);
1324 
1325  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
1326  bu_log("nmg_fu_planeeqn(): First loopuse does not contain edges\n");
1327  return -1;
1328  }
1329  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
1330  NMG_CK_EDGEUSE(eu);
1331  NMG_CK_VERTEXUSE(eu->vu_p);
1332  a = eu->vu_p->v_p;
1333  NMG_CK_VERTEX(a);
1334  NMG_CK_VERTEX_G(a->vg_p);
1335 
1336  eu_next = eu;
1337  do {
1338  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, eu_next);
1339  NMG_CK_EDGEUSE(eu_next);
1340  if (eu_next == eu) {
1341  bu_log("nmg_fu_planeeqn(): First loopuse contains only one edgeuse\n");
1342  return -1;
1343  }
1344  NMG_CK_VERTEXUSE(eu_next->vu_p);
1345  b = eu_next->vu_p->v_p;
1346  NMG_CK_VERTEX(b);
1347  NMG_CK_VERTEX_G(b->vg_p);
1348  } while ((b == a
1349  || bn_pt3_pt3_equal(a->vg_p->coord, b->vg_p->coord, tol))
1350  && eu_next->vu_p != eu->vu_p);
1351 
1352  eu_final = eu_next;
1353  do {
1354  eu_final = BU_LIST_PNEXT_CIRC(edgeuse, eu_final);
1355  NMG_CK_EDGEUSE(eu_final);
1356  if (eu_final == eu) {
1357  bu_log("nmg_fu_planeeqn(): Cannot find three distinct vertices\n");
1358  return -1;
1359  }
1360  NMG_CK_VERTEXUSE(eu_final->vu_p);
1361  c = eu_final->vu_p->v_p;
1362  NMG_CK_VERTEX(c);
1363  NMG_CK_VERTEX_G(c->vg_p);
1364  both_equal = (c == b) ||
1365  bn_pt3_pt3_equal(a->vg_p->coord, c->vg_p->coord, tol) ||
1366  bn_pt3_pt3_equal(b->vg_p->coord, c->vg_p->coord, tol);
1367  } while ((both_equal
1368  || bn_3pts_collinear(a->vg_p->coord, b->vg_p->coord,
1369  c->vg_p->coord, tol))
1370  && eu_next->vu_p != eu->vu_p);
1371 
1372  if (bn_mk_plane_3pts(plane,
1373  a->vg_p->coord, b->vg_p->coord, c->vg_p->coord, tol) < 0) {
1374  bu_log("nmg_fu_planeeqn(): bn_mk_plane_3pts failed on (%g, %g, %g) (%g, %g, %g) (%g, %g, %g)\n",
1375  V3ARGS(a->vg_p->coord),
1376  V3ARGS(b->vg_p->coord),
1377  V3ARGS(c->vg_p->coord));
1378  HPRINT("plane", plane);
1379  return -1;
1380  }
1381  if (VNEAR_ZERO(plane, SMALL_FASTF)) {
1382  bu_log("nmg_fu_planeeqn(): Bad plane equation from bn_mk_plane_3pts\n");
1383  HPRINT("plane", plane);
1384  return -1;
1385  }
1386  nmg_face_g(fu, plane);
1387 
1388  /* Check and make sure all verts are within tol->dist of face */
1389  if (nmg_ck_fu_verts(fu, fu->f_p, tol) != 0) {
1390  bu_log("nmg_fu_planeeqn(fu=%p) ERROR, verts are not within tol of face\n", (void *)fu);
1391  return -1;
1392  }
1393 
1394  if (RTG.NMG_debug & DEBUG_BASIC) {
1395  bu_log("nmg_fu_planeeqn(fu=%p, tol=%p)\n", (void *)fu, (void *)tol);
1396  }
1397  return 0;
1398 }
1399 
1400 
1401 /**
1402  * given a shell containing "n" faces whose outward oriented faceuses
1403  * are enumerated in "fulist", glue the edges of the faces together
1404  * Most especially useful after using nmg_cface() several times to
1405  * make faces which share vertex structures.
1406  */
1407 void
1408 nmg_gluefaces(struct faceuse **fulist, int n, const struct bn_tol *tol)
1409 {
1410  register int i;
1411  struct loopuse *lu;
1412  struct edgeuse *eu;
1413  struct bu_ptbl ftab; /* faceuse table */
1414 
1415  bu_ptbl_init(&ftab, 64, "ftab buffer");
1416  for (i = 0; i < n; ++i) {
1417  for (BU_LIST_FOR(lu, loopuse, &fulist[i]->lu_hd)) {
1418  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
1419  continue;
1420  }
1421  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1422  bu_ptbl_ins(&ftab, (long *)eu);
1423  }
1424  }
1425  }
1426 
1427  nmg_edge_fuse((const uint32_t *)&ftab, tol);
1428  bu_ptbl_free(&ftab);
1429 
1430  if (RTG.NMG_debug & DEBUG_BASIC) {
1431  bu_log("nmg_gluefaces(fulist=%p, n=%d)\n", (void *)fulist, n);
1432  }
1433 }
1434 
1435 
1436 /**
1437  * combine adjacent loops within a face which serve no apparent
1438  * purpose by remaining separate and distinct. Kill "wire-snakes" in
1439  * face.
1440  *
1441  * Returns -
1442  * 0 If all was OK
1443  * 1 If faceuse is now empty
1444  */
1445 int
1446 nmg_simplify_face(struct faceuse *fu)
1447 {
1448  struct loopuse *lu;
1449  int ret_val;
1450 
1451  NMG_CK_FACEUSE(fu);
1452 
1453  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1454  nmg_simplify_loop(lu);
1455  }
1456 
1457  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1458  if (nmg_kill_snakes(lu)) {
1459  struct loopuse *klu = lu;
1460  lu = BU_LIST_PREV(loopuse, &lu->l);
1461  nmg_klu(klu);
1462  }
1463  }
1464 
1465  ret_val = BU_LIST_IS_EMPTY(&fu->lu_hd);
1466 
1467  if (RTG.NMG_debug & DEBUG_BASIC) {
1468  bu_log("nmg_simplify_face(fut=%p) return=%d\n", (void *)fu, ret_val);
1469  }
1470 
1471  return ret_val;
1472 }
1473 
1474 
1475 /**
1476  * This routine reverses the direction of the Normal vector which
1477  * defines the plane of the face.
1478  *
1479  * The OT_SAME faceuse becomes the OT_OPPOSITE faceuse, and vice
1480  * versa. This preserves the convention that OT_SAME loopuses in the
1481  * OT_SAME faceuse are counter-clockwise rotating about the surface
1482  * normal.
1483  *
1484  * Before After
1485  *
1486  *
1487  * N OT_SAME OT_OPPOSITE
1488  * \ .<---------. .<---------.
1489  * \ |fu ^ |fu ^
1490  * \ | .------ | ->. | .------ | ->.
1491  * \| ^fumate | | | ^fumate | |
1492  * | | | | | | | |
1493  * | | | | | | | |
1494  * V | | | V | | |\
1495  * .--------->. | .--------->. | \
1496  * | V | V \
1497  * .<----------. .<----------. \
1498  * OT_OPPOSITE OT_SAME \
1499  * N
1500  *
1501  * Also note that this reverses the same:opposite:opposite:same parity
1502  * radially around each edge. This can create parity errors until all
1503  * faces of this shell have been processed.
1504  *
1505  * Applications programmers should use nmg_invert_shell(), which does
1506  * not have this problem.
1507  *
1508  * THIS ROUTINE IS FOR INTERNAL USE ONLY.
1509  */
1510 void
1511 nmg_reverse_face(register struct faceuse *fu)
1512 {
1513  register struct faceuse *fumate;
1514 
1515  NMG_CK_FACEUSE(fu);
1516  fumate = fu->fumate_p;
1517  NMG_CK_FACEUSE(fumate);
1518  NMG_CK_FACE(fu->f_p);
1519  NMG_CK_FACE_G_EITHER(fu->f_p->g.magic_p);
1520 
1521  /* reverse face normal vector */
1522  fu->f_p->flip = !fu->f_p->flip;
1523 
1524  /* switch which face is "outside" face */
1525  if (fu->orientation == OT_SAME) {
1526  if (fumate->orientation != OT_OPPOSITE) {
1527  bu_log("nmg_reverse_face(fu=%p) fu:SAME, fumate:%d\n",
1528  (void *)fu, fumate->orientation);
1529  bu_bomb("nmg_reverse_face() orientation clash\n");
1530  } else {
1531  fu->orientation = OT_OPPOSITE;
1532  fumate->orientation = OT_SAME;
1533  }
1534  } else if (fu->orientation == OT_OPPOSITE) {
1535  if (fumate->orientation != OT_SAME) {
1536  bu_log("nmg_reverse_face(fu=%p) fu:OPPOSITE, fumate:%d\n",
1537  (void *)fu, fumate->orientation);
1538  bu_bomb("nmg_reverse_face() orientation clash\n");
1539  } else {
1540  fu->orientation = OT_SAME;
1541  fumate->orientation = OT_OPPOSITE;
1542  }
1543  } else {
1544  /* Unoriented face? */
1545  bu_log("ERROR nmg_reverse_face(fu=%p), orientation=%d.\n",
1546  (void *)fu, fu->orientation);
1547  }
1548 
1549  if (RTG.NMG_debug & DEBUG_BASIC) {
1550  bu_log("nmg_reverse_face(fu=%p) fumate=%p\n", (void *)fu, (void *)fumate);
1551  }
1552 }
1553 
1554 
1555 /**
1556  * XXX Called in nmg_misc.c / nmg_reverse_face_and_radials()
1557  * Around an edge, consider all the edgeuses that belong to a single
1558  * shell. The faceuses pertaining to those edgeuses must maintain the
1559  * appropriate parity with their radial faceuses, so that OT_SAME is
1560  * always radial to OT_SAME, and OT_OPPOSITE is always radial to
1561  * OT_OPPOSITE.
1562  *
1563  * If a radial edgeuse is encountered that belongs to *this* face,
1564  * then it might not have been processed by this routine yet, and is
1565  * ignored for the purposes of checking parity.
1566  *
1567  * When moving faces between shells, sometimes this parity
1568  * relationship needs to be fixed, which can be easily accomplished by
1569  * exchanging the incorrect edgeuse with its mate in the radial edge
1570  * linkages.
1571  *
1572  * XXX Note that this routine will not work right in the presence of
1573  * XXX dangling faces.
1574  *
1575  * Note that this routine can't be used incrementally, because after
1576  * an odd number (like one) of faceuses have been "fixed", there is an
1577  * inherent parity error, which will cause wrong decisions to be
1578  * made. Therefore, *all* faces have to be moved from one shell to
1579  * another before the radial parity can be "fixed". Even then, this
1580  * isn't going to work right unless we are given a list of all the
1581  * "suspect" faceuses, so the initial parity value can be properly
1582  * established.
1583  *
1584  * XXXX I am of the opinion this routine is neither useful nor correct
1585  * XXXX in its present form, except for limited special cases.
1586  *
1587  * The 'tol' arg is used strictly for printing purposes.
1588  *
1589  * Returns -
1590  * count of number of edges fixed.
1591  */
1592 int
1593 nmg_face_fix_radial_parity(struct faceuse *fu, const struct bn_tol *tol)
1594 {
1595  struct loopuse *lu;
1596  struct edgeuse *eu;
1597  struct faceuse *fu2;
1598  struct shell *s;
1599  long count = 0;
1600 
1601  NMG_CK_FACEUSE(fu);
1602  s = fu->s_p;
1603  NMG_CK_SHELL(s);
1604  BN_CK_TOL(tol);
1605 
1606  /* Make sure we are now dealing with the OT_SAME faceuse */
1607  if (fu->orientation == OT_SAME)
1608  fu2 = fu;
1609  else
1610  fu2 = fu->fumate_p;
1611 
1612  for (BU_LIST_FOR(lu, loopuse, &fu2->lu_hd)) {
1613  NMG_CK_LOOPUSE(lu);
1614 
1615  /* skip loops of a single vertex */
1616  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
1617  continue;
1618 
1619  /*
1620  * Consider every edge of this loop.
1621  * Initial sequencing is:
1622  * before(radial), eu, eumate, after(radial)
1623  */
1624  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1625  struct edgeuse *eumate;
1626  struct edgeuse *before;
1627  struct edgeuse *sbefore; /* searched before */
1628  struct edgeuse *after;
1629 
1630  eumate = eu->eumate_p;
1631  before = eu->radial_p;
1632  after = eumate->radial_p;
1633  NMG_CK_EDGEUSE(eumate);
1634  NMG_CK_EDGEUSE(before);
1635  NMG_CK_EDGEUSE(after);
1636 
1637  /* If no other edgeuses around edge, done. */
1638  if (before == eumate)
1639  continue;
1640 
1641  /*
1642  * Search in 'before' direction, until it's in
1643  * same shell. Also ignore edgeuses from this FACE,
1644  * as they may not have been fixed yet.
1645  */
1646  for (sbefore = before;
1647  sbefore != eu && sbefore != eumate;
1648  sbefore = sbefore->eumate_p->radial_p
1649  ) {
1650  struct faceuse *bfu;
1651  if (nmg_find_s_of_eu(sbefore) != s) continue;
1652 
1653  bfu = nmg_find_fu_of_eu(sbefore);
1654  /* If edgeuse isn't part of a faceuse, skip */
1655  if (!bfu) continue;
1656  if (bfu->f_p == fu->f_p) continue;
1657  /* Found a candidate */
1658  break;
1659  }
1660 
1661  /* If search found no others from this shell, done. */
1662  if (sbefore == eu || sbefore == eumate)
1663  continue;
1664 
1665  /*
1666  * 'eu' is in an OT_SAME faceuse.
1667  * If the first faceuse in the 'before' direction
1668  * from this shell is OT_SAME, no fix is required.
1669  */
1670  if (sbefore->up.lu_p->up.fu_p->orientation == OT_SAME)
1671  continue;
1672 
1673  /*
1674  * Rearrange order to be: before, eumate, eu, after.
1675  * NOTE: do NOT use sbefore here.
1676  */
1677  before->radial_p = eumate;
1678  eumate->radial_p = before;
1679 
1680  after->radial_p = eu;
1681  eu->radial_p = after;
1682  count++;
1683  if (RTG.NMG_debug & DEBUG_BASIC) {
1684  bu_log("nmg_face_fix_radial_parity() exchanging eu=%p & eumate=%p on edge %p\n",
1685  (void *)eu, (void *)eumate, (void *)eu->e_p);
1686  }
1687  }
1688  }
1689 
1690  if (RTG.NMG_debug & DEBUG_BASIC) {
1691  bu_log("nmg_face_fix_radial_parity(fu=%p) returns %ld\n", (void *)fu, count);
1692  }
1693 
1694  return count;
1695 }
1696 
1697 
1698 /**
1699  * Move faceuse from 'src' shell to 'dest' shell.
1700  */
1701 void
1702 nmg_mv_fu_between_shells(struct shell *dest, register struct shell *src, register struct faceuse *fu)
1703 {
1704  register struct faceuse *fumate;
1705 
1706  NMG_CK_FACEUSE(fu);
1707  fumate = fu->fumate_p;
1708  NMG_CK_FACEUSE(fumate);
1709 
1710  if (fu->s_p != src) {
1711  bu_log("nmg_mv_fu_between_shells(dest=%p, src=%p, fu=%p), fu->s_p=%p isn't src shell\n",
1712  (void *)dest, (void *)src, (void *)fu, (void *)fu->s_p);
1713  bu_bomb("fu->s_p isn't source shell\n");
1714  }
1715  if (fumate->s_p != src) {
1716  bu_log("nmg_mv_fu_between_shells(dest=%p, src=%p, fu=%p), fumate->s_p=%p isn't src shell\n",
1717  (void *)dest, (void *)src, (void *)fu, (void *)fumate->s_p);
1718  bu_bomb("fumate->s_p isn't source shell\n");
1719  }
1720 
1721  /* Remove fu from src shell */
1722  BU_LIST_DEQUEUE(&fu->l);
1723  if (BU_LIST_IS_EMPTY(&src->fu_hd)) {
1724  /* This was the last fu in the list, bad news */
1725  bu_log("nmg_mv_fu_between_shells(dest=%p, src=%p, fu=%p), fumate=%p not in src shell\n",
1726  (void *)dest, (void *)src, (void *)fu, (void *)fumate);
1727  bu_bomb("src shell emptied before finding fumate\n");
1728  }
1729 
1730  /* Remove fumate from src shell */
1731  BU_LIST_DEQUEUE(&fumate->l);
1732 
1733  /*
1734  * Add fu and fumate to dest shell, preserving implicit OT_SAME,
1735  * OT_OPPOSITE order
1736  */
1737  if (fu->orientation == OT_SAME) {
1738  BU_LIST_APPEND(&dest->fu_hd, &fu->l);
1739  BU_LIST_APPEND(&fu->l, &fumate->l);
1740  } else {
1741  BU_LIST_APPEND(&dest->fu_hd, &fumate->l);
1742  BU_LIST_APPEND(&fumate->l, &fu->l);
1743  }
1744 
1745  fu->s_p = dest;
1746  fumate->s_p = dest;
1747 
1748  if (RTG.NMG_debug & DEBUG_BASIC) {
1749  bu_log("nmg_mv_fu_between_shells(dest=%p, src=%p, fu=%p)\n",
1750  (void *)dest, (void *)src, (void *)fu);
1751  }
1752 }
1753 
1754 
1755 /**
1756  * Move everything from the source faceuse into the destination
1757  * faceuse. Exists as a support routine for nmg_jf() only.
1758  */
1759 static void
1760 nmg_move_fu_fu(register struct faceuse *dest_fu, register struct faceuse *src_fu)
1761 {
1762  register struct loopuse *lu;
1763 
1764  NMG_CK_FACEUSE(dest_fu);
1765  NMG_CK_FACEUSE(src_fu);
1766 
1767  if (dest_fu->orientation != src_fu->orientation)
1768  bu_bomb("nmg_move_fu_fu: differing orientations\n");
1769 
1770  /* Move all loopuses from src to dest faceuse */
1771  while (BU_LIST_WHILE(lu, loopuse, &src_fu->lu_hd)) {
1772  BU_LIST_DEQUEUE(&(lu->l));
1773  BU_LIST_INSERT(&(dest_fu->lu_hd), &(lu->l));
1774  lu->up.fu_p = dest_fu;
1775  }
1776  /* The src_fu is invalid here, with an empty lu_hd list */
1777 
1778  if (RTG.NMG_debug & DEBUG_BASIC) {
1779  bu_log("nmg_move_fu_fu(dest_fu=%p, src_fu=%p)\n", (void *)dest_fu, (void *)src_fu);
1780  }
1781 }
1782 
1783 
1784 /**
1785  * Join two faces together by moving everything from the source
1786  * faceuse and mate into the destination faceuse and mate, taking into
1787  * account face orientations. The source face is destroyed by this
1788  * operation.
1789  */
1790 void
1791 nmg_jf(register struct faceuse *dest_fu, register struct faceuse *src_fu)
1792 {
1793  NMG_CK_FACEUSE(dest_fu);
1794  NMG_CK_FACEUSE(src_fu);
1795 
1796  if (RTG.NMG_debug & DEBUG_BASIC) {
1797  bu_log("nmg_jf(dest_fu=%p, src_fu=%p)\n", (void *)dest_fu, (void *)src_fu);
1798  }
1799 
1800  if (src_fu->f_p == dest_fu->f_p)
1801  bu_bomb("nmg_jf() src and dest faces are the same\n");
1802 
1803  if (dest_fu->orientation == src_fu->orientation) {
1804  nmg_move_fu_fu(dest_fu, src_fu);
1805  nmg_move_fu_fu(dest_fu->fumate_p, src_fu->fumate_p);
1806  } else {
1807  nmg_move_fu_fu(dest_fu, src_fu->fumate_p);
1808  nmg_move_fu_fu(dest_fu->fumate_p, src_fu);
1809  }
1810  /* The src_fu is invalid here, having an empty lu_hd list */
1811  nmg_kfu(src_fu);
1812 
1813 }
1814 
1815 
1816 /**
1817  * Construct a duplicate of a face into the shell 's'. The vertex
1818  * geometry is copied from the source face into topologically distinct
1819  * (new) vertex and vertex_g structs. They will start out being
1820  * geometrically coincident, but it is anticipated that the caller will
1821  * modify the geometry, e.g. as in an extrude operation.
1822  *
1823  * It is the caller's responsibility to re-bound the new face after
1824  * making any modifications.
1825  */
1826 struct faceuse *
1827 nmg_dup_face(struct faceuse *fu, struct shell *s)
1828 {
1829  struct loopuse *new_lu, *lu;
1830  struct faceuse *new_fu = (struct faceuse *)NULL;
1831  struct model *m;
1832  struct model *m_f;
1833  plane_t pl;
1834  long **trans_tbl;
1835  long tbl_size;
1836 
1837  NMG_CK_FACEUSE(fu);
1838  NMG_CK_FACE(fu->f_p);
1839  NMG_CK_SHELL(s);
1840 
1841  /* allocate the table that holds the translations between existing
1842  * elements and the duplicates we will create.
1843  */
1844  m = nmg_find_model((uint32_t *)s);
1845  tbl_size = m->maxindex;
1846 
1847  m_f = nmg_find_model((uint32_t *)fu);
1848  if (m != m_f)
1849  tbl_size += m_f->maxindex;
1850 
1851  /* Needs double space, because model will grow as dup proceeds */
1852  trans_tbl = (long **)bu_calloc(tbl_size*2, sizeof(long *),
1853  "nmg_dup_face trans_tbl");
1854 
1855  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1856  if (RTG.NMG_debug & DEBUG_BASIC)
1857  bu_log("nmg_dup_face() duping %s loop...",
1858  nmg_orientation(lu->orientation));
1859  if (new_fu) {
1860  new_lu = nmg_dup_loop(lu, &new_fu->l.magic, trans_tbl);
1861  } else {
1862  new_lu = nmg_dup_loop(lu, &s->l.magic, trans_tbl);
1863  new_fu = nmg_mf(new_lu);
1864 
1865  /* since nmg_mf() FORCES the orientation of the initial
1866  * loop to be OT_SAME, we need to re-set the orientation
1867  * of new_lu if lu->orientation is not OT_SAME. In
1868  * general, the first loopuse on a faceuse's linked list
1869  * will be OT_SAME, but in some circumstances (such as
1870  * after booleans) the first loopuse MAY be OT_OPPOSITE
1871  */
1872  if (lu->orientation != OT_SAME) {
1873  new_lu->orientation = lu->orientation;
1874  new_lu->lumate_p->orientation =
1875  lu->lumate_p->orientation;
1876  }
1877  }
1878  if (RTG.NMG_debug & DEBUG_BASIC)
1879  bu_log(". Duped %s loop\n",
1880  nmg_orientation(new_lu->orientation));
1881  }
1882 
1883  /* Create duplicate, independently modifiable face geometry */
1884  switch (*fu->f_p->g.magic_p) {
1886  NMG_GET_FU_PLANE(pl, fu);
1887  nmg_face_g(new_fu, pl);
1888  break;
1889  case NMG_FACE_G_SNURB_MAGIC: {
1890  struct face_g_snurb *old = fu->f_p->g.snurb_p;
1891  struct face_g_snurb *newface;
1892  /* Create a new, duplicate snurb */
1893  nmg_face_g_snurb(new_fu,
1894  old->order[0], old->order[1],
1895  old->u.k_size, old->v.k_size,
1896  NULL, NULL,
1897  old->s_size[0], old->s_size[1],
1898  old->pt_type,
1899  NULL);
1900  newface = new_fu->f_p->g.snurb_p;
1901  /* Copy knots */
1902  memcpy(newface->u.knots, old->u.knots, old->u.k_size*sizeof(fastf_t));
1903  memcpy(newface->v.knots, old->v.knots, old->v.k_size*sizeof(fastf_t));
1904  /* Copy mesh */
1905  memcpy(newface->ctl_points, old->ctl_points,
1906  old->s_size[0] * old->s_size[1] *
1907  RT_NURB_EXTRACT_COORDS(old->pt_type) *
1908  sizeof(fastf_t));
1909  }
1910  }
1911  new_fu->orientation = fu->orientation;
1912  new_fu->fumate_p->orientation = fu->fumate_p->orientation;
1913 
1914  bu_free((char *)trans_tbl, "nmg_dup_face trans_tbl");
1915 
1916  if (RTG.NMG_debug & DEBUG_BASIC) {
1917  bu_log("nmg_dup_face(fu=%p, s=%p) new_fu=%p\n",
1918  (void *)fu, (void *)s, (void *)new_fu);
1919  }
1920 
1921  return new_fu;
1922 }
1923 
1924 
1925 /************************************************************************
1926  * *
1927  * LOOP Routines *
1928  * *
1929  ************************************************************************/
1930 
1931 
1932 /**
1933  * Join two loops together which share a common edge, such that both
1934  * occurrences of the common edge are deleted. This routine always
1935  * leaves "lu" intact, and kills the loop radial to "eu" (after
1936  * stealing all its edges).
1937  *
1938  * Either both loops must be of the same orientation, or then first
1939  * loop must be OT_SAME, and the second loop must be OT_OPPOSITE.
1940  * Joining OT_SAME & OT_OPPOSITE always gives an OT_SAME result.
1941  * Above statement is not true!!!! I have added nmg_lu_reorient() -JRA
1942  * Since "lu" must survive, it must be the OT_SAME one.
1943  */
1944 void
1945 nmg_jl(struct loopuse *lu, struct edgeuse *eu)
1946 {
1947  struct loopuse *lu2;
1948  struct edgeuse *eu_r; /* use of shared edge in lu2 */
1949  struct edgeuse *nexteu;
1950 
1951  NMG_CK_LOOPUSE(lu);
1952 
1953  NMG_CK_EDGEUSE(eu);
1954  NMG_CK_EDGEUSE(eu->eumate_p);
1955  eu_r = eu->radial_p;
1956  NMG_CK_EDGEUSE(eu_r);
1957  NMG_CK_EDGEUSE(eu_r->eumate_p);
1958 
1959  lu2 = eu_r->up.lu_p;
1960  NMG_CK_LOOPUSE(lu2);
1961 
1962  if (RTG.NMG_debug & DEBUG_BASIC) {
1963  bu_log("nmg_jl(lu=%p, eu=%p) lu2=%p\n", (void *)lu, (void *)eu, (void *)lu2);
1964  }
1965 
1966  if (eu->up.lu_p != lu)
1967  bu_bomb("nmg_jl: edgeuse is not child of loopuse?\n");
1968 
1969  if (lu2->l.magic != NMG_LOOPUSE_MAGIC)
1970  bu_bomb("nmg_jl: radial edgeuse not part of loopuse\n");
1971 
1972  if (lu2 == lu)
1973  bu_bomb("nmg_jl: trying to join a loop to itself\n");
1974 
1975  if (lu->up.magic_p != lu2->up.magic_p)
1976  bu_bomb("nmg_jl: loopuses do not share parent\n");
1977 
1978  if (lu2->orientation != lu->orientation) {
1979  if (lu->orientation != OT_SAME || lu2->orientation != OT_OPPOSITE) {
1980  bu_log("nmg_jl: lu2 = %s, lu = %s\n",
1981  nmg_orientation(lu2->orientation),
1982  nmg_orientation(lu->orientation));
1983  bu_bomb("nmg_jl: can't join loops of different orientation!\n");
1984  } else {
1985  /* Consuming an OPPOSITE into a SAME is OK */
1986  }
1987  }
1988 
1989  if (eu->radial_p->eumate_p->radial_p->eumate_p != eu ||
1990  eu->eumate_p->radial_p->eumate_p->radial_p != eu)
1991  bu_bomb("nmg_jl: edgeuses must be sole uses of edge to join loops\n");
1992 
1993  /*
1994  * Remove all the edgeuses "ahead" of our radial and insert them
1995  * "behind" the current edgeuse. Operates on lu and lu's mate
1996  * simultaneously.
1997  */
1998  nexteu = BU_LIST_PNEXT_CIRC(edgeuse, eu_r);
1999  while (nexteu != eu_r) {
2000  BU_LIST_DEQUEUE(&nexteu->l);
2001  BU_LIST_INSERT(&eu->l, &nexteu->l);
2002  nexteu->up.lu_p = eu->up.lu_p;
2003 
2004  BU_LIST_DEQUEUE(&nexteu->eumate_p->l);
2005  BU_LIST_APPEND(&eu->eumate_p->l, &nexteu->eumate_p->l);
2006  nexteu->eumate_p->up.lu_p = eu->eumate_p->up.lu_p;
2007 
2008  nexteu = BU_LIST_PNEXT_CIRC(edgeuse, eu_r);
2009  }
2010 
2011  /*
2012  * The other loop just has the one (shared) edgeuse left in it.
2013  * Delete the other loop (and its mate).
2014  */
2015  nmg_klu(lu2);
2016 
2017  /*
2018  * Kill the one remaining use of the (formerly) "shared" edge in
2019  * lu and voila: one contiguous loop.
2020  */
2021  if (nmg_keu(eu)) bu_bomb("nmg_jl() loop vanished?\n");
2022 
2023  nmg_lu_reorient(lu);
2024 }
2025 
2026 
2027 /**
2028  * Intended to join an interior and exterior loop together, by
2029  * building a bridge between the two indicated vertices.
2030  *
2031  * This routine can be used to join two exterior loops which do not
2032  * overlap, and it can also be used to join an exterior loop with a
2033  * loop of opposite orientation that lies entirely within it. This
2034  * restriction is important, but not checked for.
2035  *
2036  * If the two vertexuses reference distinct vertices, then two new
2037  * edges are built to bridge the loops together. If the two
2038  * vertexuses share the same vertex, then it is even easier.
2039  *
2040  * Returns the replacement for vu2.
2041  */
2042 struct vertexuse *
2043 nmg_join_2loops(struct vertexuse *vu1, struct vertexuse *vu2)
2044 {
2045  struct edgeuse *eu1, *eu2;
2046  struct edgeuse *first_new_eu;
2047  struct edgeuse *second_new_eu;
2048  struct edgeuse *final_eu2;
2049  struct loopuse *lu1, *lu2;
2050 
2051  NMG_CK_VERTEXUSE(vu1);
2052  NMG_CK_VERTEXUSE(vu2);
2053  eu1 = vu1->up.eu_p;
2054  eu2 = vu2->up.eu_p;
2055  NMG_CK_EDGEUSE(eu1);
2056  NMG_CK_EDGEUSE(eu2);
2057  lu1 = eu1->up.lu_p;
2058  lu2 = eu2->up.lu_p;
2059  NMG_CK_LOOPUSE(lu1);
2060  NMG_CK_LOOPUSE(lu2);
2061 
2062  if (RTG.NMG_debug & DEBUG_BASIC) {
2063  bu_log("nmg_join_2loops(vu1=%p, vu2=%p) lu1=%p, lu2=%p\n",
2064  (void *)vu1, (void *)vu2, (void *)lu1, (void *)lu2);
2065  }
2066 
2067  if (lu1 == lu2 || lu1->l_p == lu2->l_p)
2068  bu_bomb("nmg_join_2loops: can't join loop to itself\n");
2069 
2070  if (lu1->up.fu_p != lu2->up.fu_p)
2071  bu_bomb("nmg_join_2loops: can't join loops in different faces\n");
2072 
2073  if (vu1->v_p != vu2->v_p) {
2074  /*
2075  * Start by taking a jaunt from vu1 to vu2 and back.
2076  */
2077 
2078  /* insert 0 length edge, before eu1 */
2079  first_new_eu = nmg_eins(eu1);
2080 
2081  /* split the new edge, and connect it to vertex 2 */
2082  second_new_eu = nmg_eusplit(vu2->v_p, first_new_eu, 0);
2083  first_new_eu = BU_LIST_PPREV_CIRC(edgeuse, second_new_eu);
2084 
2085  /* Make the two new edgeuses share just one edge */
2086  nmg_je(second_new_eu, first_new_eu);
2087 
2088  /* first_new_eu is eu that enters shared vertex */
2089  vu1 = second_new_eu->vu_p;
2090  } else {
2091  second_new_eu = eu1;
2092  first_new_eu = BU_LIST_PPREV_CIRC(edgeuse, second_new_eu);
2093  NMG_CK_EDGEUSE(second_new_eu);
2094  }
2095  /* second_new_eu is eu that departs from shared vertex */
2096  vu2 = second_new_eu->vu_p; /* replacement for original vu2 */
2097  if (vu1->v_p != vu2->v_p) bu_bomb("nmg_join_2loops: jaunt failed\n");
2098 
2099  /*
2100  * Gobble edges off of loop2 (starting with eu2), and insert them
2101  * into loop1, between first_new_eu and second_new_eu. The final
2102  * edge from loop 2 will then be followed by second_new_eu.
2103  */
2104  final_eu2 = BU_LIST_PPREV_CIRC(edgeuse, eu2);
2105  while (BU_LIST_NON_EMPTY(&lu2->down_hd)) {
2106  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, final_eu2);
2107 
2108  BU_LIST_DEQUEUE(&eu2->l);
2109  BU_LIST_INSERT(&second_new_eu->l, &eu2->l);
2110  eu2->up.lu_p = lu1;
2111 
2112  BU_LIST_DEQUEUE(&eu2->eumate_p->l);
2113  BU_LIST_APPEND(&second_new_eu->eumate_p->l, &eu2->eumate_p->l);
2114  eu2->eumate_p->up.lu_p = lu1->lumate_p;
2115  }
2116 
2117  nmg_lu_reorient(lu1);
2118 
2119  /* Kill entire (null) loop associated with lu2 */
2120  nmg_klu(lu2);
2121 
2122  return vu2;
2123 }
2124 
2125 
2126 /* XXX These should be included in nmg_join_2loops, or be called by it */
2127 
2128 
2129 /**
2130  * vu1 is in a regular loop, vu2 is in a loop of a single vertex A
2131  * jaunt is taken from vu1 to vu2 and back to vu1, and the old loop at
2132  * vu2 is destroyed.
2133  *
2134  * Return is the new vu that replaces vu2.
2135  */
2136 struct vertexuse *
2137 nmg_join_singvu_loop(struct vertexuse *vu1, struct vertexuse *vu2)
2138 {
2139  struct edgeuse *eu1;
2140  struct edgeuse *first_new_eu, *second_new_eu;
2141  struct loopuse *lu2;
2142 
2143  NMG_CK_VERTEXUSE(vu1);
2144  NMG_CK_VERTEXUSE(vu2);
2145 
2146  if (RTG.NMG_debug & DEBUG_BASIC) {
2147  bu_log("nmg_join_singvu_loop(vu1=%p, vu2=%p) lu1=%p, lu2=%p\n",
2148  (void *)vu1, (void *)vu2, (void *)vu1->up.lu_p, (void *)vu2->up.lu_p);
2149  }
2150 
2151  if (*vu2->up.magic_p != NMG_LOOPUSE_MAGIC ||
2152  *vu1->up.magic_p != NMG_EDGEUSE_MAGIC) bu_bomb("nmg_join_singvu_loop bad args\n");
2153 
2154  if (vu1->v_p == vu2->v_p) bu_bomb("nmg_join_singvu_loop same vertex\n");
2155 
2156  /* Take jaunt from vu1 to vu2 and back */
2157  eu1 = vu1->up.eu_p;
2158  NMG_CK_EDGEUSE(eu1);
2159 
2160  /* Insert 0 length edge */
2161  first_new_eu = nmg_eins(eu1);
2162  /* split the new edge, and connect it to vertex 2 */
2163  second_new_eu = nmg_eusplit(vu2->v_p, first_new_eu, 0);
2164  first_new_eu = BU_LIST_PPREV_CIRC(edgeuse, second_new_eu);
2165  /* Make the two new edgeuses share just one edge */
2166  nmg_je(second_new_eu, first_new_eu);
2167 
2168  /* Kill loop lu2 associated with vu2 */
2169  lu2 = vu2->up.lu_p;
2170  NMG_CK_LOOPUSE(lu2);
2171  nmg_klu(lu2);
2172 
2173  return second_new_eu->vu_p;
2174 }
2175 
2176 
2177 /**
2178  * Both vertices are part of single vertex loops. Converts loop on
2179  * vu1 into a real loop that connects them together, with a single
2180  * edge (two edgeuses). Loop on vu2 is killed.
2181  *
2182  * Returns replacement vu for vu2.
2183  * Does not change the orientation.
2184  */
2185 struct vertexuse *
2186 nmg_join_2singvu_loops(struct vertexuse *vu1, struct vertexuse *vu2)
2187 {
2188  struct edgeuse *first_new_eu, *second_new_eu;
2189  struct loopuse *lu1, *lu2;
2190 
2191  if (RTG.NMG_debug & DEBUG_BASIC) {
2192  bu_log("nmg_join_2singvu_loops(vu1=%p, vu2=%p) lu1=%p, lu2=%p\n",
2193  (void *)vu1, (void *)vu2, (void *)vu1->up.lu_p, (void *)vu2->up.lu_p);
2194  }
2195 
2196  NMG_CK_VERTEXUSE(vu1);
2197  NMG_CK_VERTEXUSE(vu2);
2198 
2199  if (*vu2->up.magic_p != NMG_LOOPUSE_MAGIC ||
2200  *vu1->up.magic_p != NMG_LOOPUSE_MAGIC) bu_bomb("nmg_join_2singvu_loops bad args\n");
2201 
2202  if (vu1->v_p == vu2->v_p) bu_bomb("nmg_join_2singvu_loops same vertex\n");
2203 
2204  /* Take jaunt from vu1 to vu2 and back */
2205  /* Make a 0 length edge on vu1 */
2206  first_new_eu = nmg_meonvu(vu1);
2207  /* split the new edge, and connect it to vertex 2 */
2208  second_new_eu = nmg_eusplit(vu2->v_p, first_new_eu, 0);
2209  first_new_eu = BU_LIST_PPREV_CIRC(edgeuse, second_new_eu);
2210  /* Make the two new edgeuses share just one edge */
2211  nmg_je(second_new_eu, first_new_eu);
2212 
2213  /* Kill loop lu2 associated with vu2 */
2214  lu2 = vu2->up.lu_p;
2215  NMG_CK_LOOPUSE(lu2);
2216  nmg_klu(lu2);
2217 
2218  lu1 = vu1->up.eu_p->up.lu_p;
2219  NMG_CK_LOOPUSE(lu1);
2220 
2221  return second_new_eu->vu_p;
2222 }
2223 
2224 
2225 /**
2226  * Divide a loop of edges between two vertexuses.
2227  *
2228  * Make a new loop between the two vertexes, and split it and the loop
2229  * of the vertexuses at the same time.
2230  *
2231  * BEFORE AFTER
2232  *
2233  *
2234  * Va eu1 vu1 Vb Va eu1 vu1 Vb
2235  * * <---------* <---------* * <--------* * <--------*
2236  * | | |
2237  * | ^ | ^ | ^
2238  * | Original | | Original | | New |
2239  * | Loopuse | | Loopuse | | Loopuse |
2240  * V | V | V / |
2241  * | | / |
2242  * *----------> *--------> * *--------> * *--------> *
2243  * Vd vu2 eu2 Vc Vd vu2 eu2 Vc
2244  *
2245  * Returns the new loopuse pointer. The new loopuse will contain
2246  * "vu2" and the edgeuse associated with "vu2" as the FIRST edgeuse on
2247  * the list of edgeuses. The edgeuse for the new edge (connecting the
2248  * vertices indicated by vu1 and vu2) will be the LAST edgeuse on the
2249  * new loopuse's list of edgeuses.
2250  *
2251  * It is the caller's responsibility to re-bound the loops.
2252  *
2253  * Both old and new loopuse will have orientation OT_UNSPEC. It is
2254  * the callers responsibility to determine what the orientations
2255  * should be. This can be conveniently done with nmg_lu_reorient().
2256  *
2257  * Here is a simple example of how the new loopuse might have a
2258  * different orientation than the original one:
2259  *
2260  * F<----------------E
2261  * | ^
2262  * | |
2263  * | C--------->D
2264  * | ^ .
2265  * | | .
2266  * | | .
2267  * | B<---------A
2268  * | ^
2269  * v |
2270  * G---------------->H
2271  *
2272  * When nmg_cut_loop(A, D) is called, the new loop ABCD is clockwise,
2273  * even though the original loop was counter-clockwise. There is no
2274  * way to determine this without referring to the face normal and
2275  * vertex geometry, which being a topology routine this routine
2276  * shouldn't do.
2277  *
2278  * Returns -
2279  * NULL on Error
2280  * lu is loopuse of new loop, on success.
2281  */
2282 struct loopuse *
2283 nmg_cut_loop(struct vertexuse *vu1, struct vertexuse *vu2)
2284 {
2285  struct loopuse *lu, *oldlu;
2286  struct edgeuse *eu1, *eu2, *eunext, *neweu, *eu;
2287  struct model *m;
2288  FILE *fd;
2289  char name[32];
2290  static int i = 0;
2291 
2292  NMG_CK_VERTEXUSE(vu1);
2293  NMG_CK_VERTEXUSE(vu2);
2294 
2295  eu1 = vu1->up.eu_p;
2296  eu2 = vu2->up.eu_p;
2297  NMG_CK_EDGEUSE(eu1);
2298  NMG_CK_EDGEUSE(eu2);
2299  oldlu = eu1->up.lu_p;
2300  NMG_CK_LOOPUSE(oldlu);
2301 
2302  if (eu2->up.lu_p != oldlu) {
2303  bu_bomb("nmg_cut_loop() vertices not descendants of same loop\n");
2304  }
2305 
2306  if (vu1->v_p == vu2->v_p) {
2307  /* The loops touch, use a different routine */
2308  /* The 2nd parameter passed into 'nmg_split_lu_at_vu' is added
2309  * to the new loopuse created by 'nmg_split_lu_at_vu'. Because
2310  * of this, the 2nd parameter should be vu2 because when
2311  * 'nmg_cut_loop' is called and returns, it is expected that
2312  * vu1 remain within the same loopuse as when 'nmg_cut_loop'
2313  * was called.
2314  */
2315  lu = nmg_split_lu_at_vu(oldlu, vu2);
2316  goto out;
2317  }
2318 
2319  NMG_CK_FACEUSE(oldlu->up.fu_p);
2320  m = oldlu->up.fu_p->s_p->r_p->m_p;
2321  NMG_CK_MODEL(m);
2322 
2323  if (RTG.NMG_debug & DEBUG_CUTLOOP) {
2324  bu_log("\tnmg_cut_loop\n");
2325  if (RTG.NMG_debug & DEBUG_PLOTEM) {
2326  long *tab;
2327  tab = (long *)bu_calloc(m->maxindex, sizeof(long),
2328  "nmg_cut_loop flag[] 1");
2329 
2330  (void)sprintf(name, "Before_cutloop%d.plot3", ++i);
2331  bu_log("nmg_cut_loop() plotting %s\n", name);
2332  if ((fd = fopen(name, "wb")) == (FILE *)NULL) {
2333  (void)perror(name);
2334  bu_bomb("unable to open file for writing");
2335  }
2336 
2337  nmg_pl_fu(fd, oldlu->up.fu_p, tab, 100, 100, 100);
2338  nmg_pl_fu(fd, oldlu->up.fu_p->fumate_p, tab, 100, 100, 100);
2339  (void)fclose(fd);
2340  bu_free((char *)tab, "nmg_cut_loop flag[] 1");
2341  }
2342  }
2343 
2344  /* make a new loop structure for the new loop & throw away
2345  * the vertexuse we don't need
2346  */
2347  lu = nmg_mlv(oldlu->up.magic_p, (struct vertex *)NULL, OT_UNSPEC);
2348  oldlu->orientation = oldlu->lumate_p->orientation = OT_UNSPEC;
2349 
2350  nmg_kvu(BU_LIST_FIRST(vertexuse, &lu->down_hd));
2351  nmg_kvu(BU_LIST_FIRST(vertexuse, &lu->lumate_p->down_hd));
2352  /* nmg_kvu() does BU_LIST_INIT() on down_hd */
2353  /* The loopuse is considered invalid until it gets some edges */
2354 
2355  /* move the edges into one of the uses of the new loop */
2356  for (eu = eu2; eu != eu1; eu = eunext) {
2357  eunext = BU_LIST_PNEXT_CIRC(edgeuse, &eu->l);
2358 
2359  BU_LIST_DEQUEUE(&eu->l);
2360  BU_LIST_INSERT(&lu->down_hd, &eu->l);
2361  BU_LIST_DEQUEUE(&eu->eumate_p->l);
2362  BU_LIST_APPEND(&lu->lumate_p->down_hd, &eu->eumate_p->l);
2363  eu->up.lu_p = lu;
2364  eu->eumate_p->up.lu_p = lu->lumate_p;
2365  }
2366 
2367  /* make a wire edge in the shell to "cap off" the new loop */
2368  neweu = nmg_me(eu1->vu_p->v_p, eu2->vu_p->v_p, nmg_find_s_of_eu(eu1));
2369 
2370  /* move the new edgeuse into the new loopuse */
2371  BU_LIST_DEQUEUE(&neweu->l);
2372  BU_LIST_INSERT(&lu->down_hd, &neweu->l);
2373  neweu->up.lu_p = lu;
2374 
2375  /* move the new edgeuse mate into the new loopuse mate */
2376  BU_LIST_DEQUEUE(&neweu->eumate_p->l);
2377  BU_LIST_APPEND(&lu->lumate_p->down_hd, &neweu->eumate_p->l);
2378  neweu->eumate_p->up.lu_p = lu->lumate_p;
2379 
2380  /* now we go back and close up the loop we just ripped open */
2381  eunext = nmg_me(eu2->vu_p->v_p, eu1->vu_p->v_p, nmg_find_s_of_eu(eu1));
2382 
2383  BU_LIST_DEQUEUE(&eunext->l);
2384  BU_LIST_INSERT(&eu1->l, &eunext->l);
2385  BU_LIST_DEQUEUE(&eunext->eumate_p->l);
2386  BU_LIST_APPEND(&eu1->eumate_p->l, &eunext->eumate_p->l);
2387  eunext->up.lu_p = eu1->up.lu_p;
2388  eunext->eumate_p->up.lu_p = eu1->eumate_p->up.lu_p;
2389 
2390  /* make new edgeuses radial to each other, sharing the new edge */
2391  nmg_je(neweu, eunext);
2392 
2393  nmg_ck_lueu(oldlu, "oldlu");
2394  nmg_ck_lueu(lu, "lu"); /*LABLABLAB*/
2395 
2396 
2397  if (RTG.NMG_debug & DEBUG_CUTLOOP && RTG.NMG_debug & DEBUG_PLOTEM) {
2398  long *tab;
2399  tab = (long *)bu_calloc(m->maxindex, sizeof(long),
2400  "nmg_cut_loop flag[] 2");
2401 
2402  (void)sprintf(name, "After_cutloop%d.plot3", i);
2403  bu_log("nmg_cut_loop() plotting %s\n", name);
2404  if ((fd = fopen(name, "wb")) == (FILE *)NULL) {
2405  (void)perror(name);
2406  bu_bomb("unable to open file for writing");
2407  }
2408 
2409  nmg_pl_fu(fd, oldlu->up.fu_p, tab, 100, 100, 100);
2410  nmg_pl_fu(fd, oldlu->up.fu_p->fumate_p, tab, 100, 100, 100);
2411  (void)fclose(fd);
2412  bu_free((char *)tab, "nmg_cut_loop flag[] 2");
2413  }
2414 out:
2415  if (RTG.NMG_debug & DEBUG_BASIC) {
2416  bu_log("nmg_cut_loop(vu1=%p, vu2=%p) old_lu=%p, new_lu=%p\n",
2417  (void *)vu1, (void *)vu2, (void *)oldlu, (void *)lu);
2418  }
2419 
2420  return lu;
2421 }
2422 
2423 
2424 /**
2425  * In a loop which has at least two distinct uses of a vertex, split
2426  * off the edges from "split_vu" to the second occurrence of the vertex
2427  * into a new loop. It is the caller's responsibility to re-bound the
2428  * loops.
2429  *
2430  * The old and new loopuses will have orientation OT_UNSPEC. It is
2431  * the callers responsibility to determine what their orientations
2432  * should be. This can be conveniently done with nmg_lu_reorient().
2433  *
2434  * Here is an example:
2435  *
2436  * E<__________B <___________A
2437  * | ^\ ^
2438  * | / \ |
2439  * | / \ |
2440  * | / v |
2441  * | D<_______C |
2442  * v |
2443  * F________________________>G
2444  *
2445  * When nmg_split_lu_at_vu(lu, B) is called, the old loopuse continues
2446  * to be counter clockwise and OT_SAME, but the new loopuse BCD is now
2447  * clockwise. It needs to be marked OT_OPPOSITE. Without referring
2448  * to the geometry, this can't be determined.
2449  *
2450  * Intended primarily for use by nmg_split_touchingloops().
2451  *
2452  * Returns -
2453  * NULL on Error
2454  * lu is loopuse of new loop, on success.
2455  */
2456 struct loopuse *
2457 nmg_split_lu_at_vu(struct loopuse *lu, struct vertexuse *split_vu)
2458 {
2459  struct edgeuse *eu;
2460  struct vertexuse *vu;
2461  struct loopuse *newlu;
2462  struct loopuse *newlumate;
2463  struct vertex *split_v;
2464  int iteration;
2465 
2466  split_v = split_vu->v_p;
2467  NMG_CK_VERTEX(split_v);
2468 
2469  eu = split_vu->up.eu_p;
2470  NMG_CK_EDGEUSE(eu);
2471 
2472  if (eu->up.lu_p != lu) {
2473  /* Could not find indicated vertex */
2474  newlu = (struct loopuse *)0; /* FAIL */
2475  goto out;
2476  }
2477 
2478  /* Make a new loop in the same face */
2479  lu->orientation = lu->lumate_p->orientation = OT_UNSPEC;
2480  newlu = nmg_mlv(lu->up.magic_p, (struct vertex *)NULL, OT_UNSPEC);
2481  NMG_CK_LOOPUSE(newlu);
2482  newlumate = newlu->lumate_p;
2483  NMG_CK_LOOPUSE(newlumate);
2484 
2485  /* Throw away unneeded lone vertexuse */
2486  nmg_kvu(BU_LIST_FIRST(vertexuse, &newlu->down_hd));
2487  nmg_kvu(BU_LIST_FIRST(vertexuse, &newlumate->down_hd));
2488  /* nmg_kvu() does BU_LIST_INIT() on down_hd */
2489 
2490  /* Move edges & mates into new loop until vertex is repeated */
2491  for (iteration = 0; iteration < 10000; iteration++) {
2492  struct edgeuse *eunext;
2493  eunext = BU_LIST_PNEXT_CIRC(edgeuse, &eu->l);
2494 
2495  BU_LIST_DEQUEUE(&eu->l);
2496  BU_LIST_INSERT(&newlu->down_hd, &eu->l);
2497  BU_LIST_DEQUEUE(&eu->eumate_p->l);
2498  BU_LIST_APPEND(&newlumate->down_hd, &eu->eumate_p->l);
2499 
2500  /* Change edgeuse & mate up pointers */
2501  eu->up.lu_p = newlu;
2502  eu->eumate_p->up.lu_p = newlumate;
2503 
2504  /* Advance to next edgeuse */
2505  eu = eunext;
2506 
2507  /* When split_v is encountered, stop */
2508  vu = eu->vu_p;
2509  NMG_CK_VERTEXUSE(vu);
2510  if (vu->v_p == split_v) break;
2511  }
2512  if (iteration >= 10000) bu_bomb("nmg_split_lu_at_vu: infinite loop\n");
2513 out:
2514  if (RTG.NMG_debug & DEBUG_BASIC) {
2515  bu_log("nmg_split_lu_at_vu(lu=%p, split_vu=%p) newlu=%p\n",
2516  (void *)lu, (void *)split_vu, (void *)newlu);
2517  }
2518  return newlu;
2519 }
2520 
2521 
2522 /**
2523  * Given a vertexuse of an edgeuse in a loopuse, see if the vertex is
2524  * used by at least one other vertexuse in that same loopuse.
2525  *
2526  * Returns -
2527  * vu if this vertex appears elsewhere in the loopuse.
2528  * NULL if this is the only occurrence of this vertex in the loopuse.
2529  *
2530  * XXX move to nmg_info.c
2531  */
2532 struct vertexuse *
2533 nmg_find_repeated_v_in_lu(struct vertexuse *vu)
2534 {
2535  struct vertexuse *tvu; /* vu to test */
2536  struct loopuse *lu;
2537  struct vertex *v;
2538 
2539  v = vu->v_p;
2540  NMG_CK_VERTEX(v);
2541 
2542  if (*vu->up.magic_p != NMG_EDGEUSE_MAGIC)
2543  return (struct vertexuse *)0;
2544  if (*vu->up.eu_p->up.magic_p != NMG_LOOPUSE_MAGIC)
2545  return (struct vertexuse *)0;
2546  lu = vu->up.eu_p->up.lu_p;
2547 
2548  /*
2549  * For each vertexuse on vertex list, check to see if it points up
2550  * to the this loop. If so, then there is a duplicated vertex.
2551  * Ordinarily, the vertex list will be *very* short, so this
2552  * strategy is likely to be faster than a table-based approach,
2553  * for most cases.
2554  */
2555  for (BU_LIST_FOR(tvu, vertexuse, &v->vu_hd)) {
2556  struct edgeuse *teu;
2557  struct loopuse *tlu;
2558 
2559  if (tvu == vu) continue;
2560  if (*tvu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
2561  teu = tvu->up.eu_p;
2562  NMG_CK_EDGEUSE(teu);
2563  if (*teu->up.magic_p != NMG_LOOPUSE_MAGIC) continue;
2564  tlu = teu->up.lu_p;
2565  NMG_CK_LOOPUSE(tlu);
2566  if (tlu != lu) continue;
2567  /*
2568  * Repeated vertex exists. Return (one) other use of it.
2569  */
2570  return tvu;
2571  }
2572  return (struct vertexuse *)0;
2573 }
2574 
2575 
2576 /**
2577  * Search through all the vertices in a loop. Whenever there are two
2578  * distinct uses of one vertex in the loop, split off all the edges
2579  * between them into a new loop.
2580  *
2581  * Note that the call to nmg_split_lu_at_vu() will cause the split
2582  * loopuses to be marked OT_UNSPEC.
2583  */
2584 void
2585 nmg_split_touchingloops(struct loopuse *lu, const struct bn_tol *tol)
2586 {
2587  struct edgeuse *eu;
2588  struct vertexuse *vu;
2589  struct loopuse *newlu;
2590  struct vertexuse *vu_save;
2591 
2592  NMG_CK_LOOPUSE(lu);
2593  BN_CK_TOL(tol);
2594  if (RTG.NMG_debug & DEBUG_BASIC) {
2595  bu_log("nmg_split_touchingloops(lu=%p)\n", (void *)lu);
2596  }
2597 top:
2598  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
2599  return;
2600 
2601  vu_save = (struct vertexuse *)NULL;
2602 
2603  /* For each edgeuse, get vertexuse and vertex */
2604  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
2605 
2606  struct edgeuse *other_eu;
2607  struct vertexuse *other_vu;
2608  int vu_is_part_of_crack = 0;
2609 
2610  vu = eu->vu_p;
2611  NMG_CK_VERTEXUSE(vu);
2612 
2613  if (!nmg_find_repeated_v_in_lu(vu)) continue;
2614 
2615  /* avoid splitting a crack if possible */
2616  for (BU_LIST_FOR(other_vu, vertexuse, &vu->v_p->vu_hd)) {
2617  if (nmg_find_lu_of_vu(other_vu) != lu)
2618  continue;
2619  if (*other_vu->up.magic_p != NMG_EDGEUSE_MAGIC)
2620  continue;
2621  other_eu = other_vu->up.eu_p;
2622  if (nmg_eu_is_part_of_crack(other_eu)) {
2623  vu_save = other_vu;
2624  vu_is_part_of_crack = 1;
2625  break;
2626  }
2627  }
2628 
2629  if (vu_is_part_of_crack)
2630  continue;
2631 
2632  /*
2633  * Repeated vertex exists,
2634  * Split loop into two loops
2635  */
2636  newlu = nmg_split_lu_at_vu(lu, vu);
2637  NMG_CK_LOOPUSE(newlu);
2638  NMG_CK_LOOP(newlu->l_p);
2639  nmg_loop_g(newlu->l_p, tol);
2640 
2641  /* Ensure there are no duplications in new loop */
2642  nmg_split_touchingloops(newlu, tol);
2643 
2644  /* There is no telling where we will be in the
2645  * remainder of original loop, check 'em all.
2646  */
2647  goto top;
2648  }
2649 
2650  if (vu_save) {
2651  /* split loop at crack */
2652  newlu = nmg_split_lu_at_vu(lu, vu_save);
2653  NMG_CK_LOOPUSE(newlu);
2654  NMG_CK_LOOP(newlu->l_p);
2655  nmg_loop_g(newlu->l_p, tol);
2656 
2657  /* Ensure there are no duplications in new loop */
2658  nmg_split_touchingloops(newlu, tol);
2659 
2660  /* There is no telling where we will be in the
2661  * remainder of original loop, check 'em all.
2662  */
2663  goto top;
2664  }
2665 }
2666 
2667 
2668 /**
2669  * Search through all the vertices in a loopuse that belongs to a
2670  * faceuse. Whenever another loopuse in the same faceuse refers to
2671  * one of this loop's vertices, the two loops touch at (at least) that
2672  * vertex. Join them together.
2673  *
2674  * Return -
2675  * count of loops joined (eliminated)
2676  */
2677 int
2678 nmg_join_touchingloops(struct loopuse *lu)
2679 {
2680  struct faceuse *fu;
2681  struct edgeuse *eu;
2682  struct vertexuse *vu;
2683  struct vertex *v;
2684  int count = 0;
2685 
2686  if (RTG.NMG_debug & DEBUG_BASIC) {
2687  bu_log("nmg_join_touchingloops(lu=%p)\n", (void *)lu);
2688  }
2689  NMG_CK_LOOPUSE(lu);
2690  fu = lu->up.fu_p;
2691  NMG_CK_FACEUSE(fu);
2692 
2693 top:
2694  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
2695  return count;
2696 
2697  /* For each edgeuse, get vertexuse and vertex */
2698  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
2699  struct vertexuse *tvu;
2700 
2701  vu = eu->vu_p;
2702  NMG_CK_VERTEXUSE(vu);
2703  v = vu->v_p;
2704  NMG_CK_VERTEX(v);
2705 
2706  /*
2707  * For each vertexuse on vertex list, check to see if it
2708  * points up to an edgeuse in a different loopuse in the same
2709  * faceuse. If so, we touch.
2710  */
2711  for (BU_LIST_FOR(tvu, vertexuse, &v->vu_hd)) {
2712  struct edgeuse *teu;
2713  struct loopuse *tlu;
2714 
2715  if (tvu == vu) continue;
2716  if (*tvu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
2717  teu = tvu->up.eu_p;
2718  NMG_CK_EDGEUSE(teu);
2719  if (*teu->up.magic_p != NMG_LOOPUSE_MAGIC) continue;
2720  tlu = teu->up.lu_p;
2721  NMG_CK_LOOPUSE(tlu);
2722  if (tlu == lu) {
2723  /* We touch ourselves at another vu? */
2724  continue;
2725  }
2726  if (*tlu->up.magic_p != NMG_FACEUSE_MAGIC) continue;
2727  if (tlu->up.fu_p != fu) continue; /* wrong faceuse */
2728  /*
2729  * Loop 'lu' touches loop 'tlu' at this vertex,
2730  * join them.
2731  * XXX Is there any advantage to searching for
2732  * XXX a potential shared edge at this point?
2733  * XXX Call nmg_simplify_loop()?
2734  */
2735  if (RTG.NMG_debug & DEBUG_BASIC) {
2736  bu_log("nmg_join_touchingloops(): lu=%p, vu=%p, tvu=%p\n",
2737  (void *)lu, (void *)vu, (void *)tvu);
2738  }
2739  tvu = nmg_join_2loops(vu, tvu);
2740  NMG_CK_VERTEXUSE(tvu);
2741  count++;
2742  goto top;
2743  }
2744  }
2745  return count;
2746 }
2747 
2748 
2749 /* jaunt status flags used in the jaunt_status array */
2750 #define JS_UNKNOWN 0
2751 #define JS_SPLIT 1
2752 #define JS_JAUNT 2
2753 #define JS_TOUCHING_JAUNT 3
2754 
2755 
2756 /**
2757  * Create a table of EU's. Each EU will be the first EU in a touching
2758  * jaunt (edgeuses from vert A->B->A) where vertex B appears elsewhere
2759  * in the loopuse lu.
2760  *
2761  * returns:
2762  * count of touching jaunts found
2763  *
2764  * The passed pointer to an bu_ptbl structure may not be
2765  * initialized. If no touching jaunts are found, it will still not be
2766  * initialized upon return (to avoid bu_malloc/bu_free pairs for loops
2767  * with no touching jaunts. The flag (need_init) lets this routine
2768  * know whether the ptbl structure has been initialized
2769  */
2770 int
2771 nmg_get_touching_jaunts(const struct loopuse *lu, struct bu_ptbl *tbl, int *need_init)
2772 {
2773  struct edgeuse *eu;
2774  int count = 0;
2775 
2776  NMG_CK_LOOPUSE(lu);
2777 
2778  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
2779  return 0;
2780 
2781  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
2782  struct edgeuse *eu2, *eu3;
2783 
2784  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, &eu->l);
2785  eu3 = BU_LIST_PNEXT_CIRC(edgeuse, &eu2->l);
2786 
2787  /* If it's a 2 vertex crack, stop here */
2788  if (eu->vu_p == eu3->vu_p) break;
2789 
2790  /* If not jaunt, move on */
2791  if (eu->vu_p->v_p != eu3->vu_p->v_p) continue;
2792 
2793  /* It's a jaunt, see if tip touches same loop */
2794  if (nmg_find_repeated_v_in_lu(eu2->vu_p) == (struct vertexuse *)NULL)
2795  continue;
2796 
2797  /* This is a touching jaunt, add it to the list */
2798  if (*need_init) {
2799  bu_ptbl_init(tbl, 64, " tbl");
2800  *need_init = 0;
2801  }
2802 
2803  bu_ptbl_ins(tbl, (long *)eu);
2804  count++;
2805  }
2806 
2807  return count;
2808 }
2809 
2810 
2811 /**
2812  * Support routine for nmg_loop_split_at_touching_jaunt().
2813  *
2814  * Follow the edgeuses in a proposed loop (that may later be created
2815  * by nmg_split_lu_at_vu) and predict the status of the jaunts in
2816  * "jaunt_tbl". The jaunt_status array must be initialized before this
2817  * routine is called and this routine should be called twice to
2818  * account for both loops that will result from the application of
2819  * nmg_split_lu_at_vu().
2820  *
2821  * Inputs:
2822  *
2823  * start_eu - edgeuse that will be first in the proposed new loop
2824  *
2825  * jaunt_tbl - list of touching jaunts whose status in the resulting
2826  * loops is desired.
2827  *
2828  * jaunt_no - which entry in the jaunt_tbl is being considered as a
2829  * split location
2830  *
2831  * visit_count - array for counting the number of times a jaunt gets
2832  * visited in the new loop This array just provides working space for
2833  * the routine.
2834  *
2835  * which_loop - Flag:
2836  * 0 -> This is a proposed loop to be created by nmg_split_lu_at_vu()
2837  * 1 -> This is the loop that will be remaining after
2838  * nmg_split_lu_at_vu(). when "which_loop" == 1, (*next_start_eu)
2839  * must be set to the starting EU of the first loop (Used to find end
2840  * of remaining loop).
2841  *
2842  * Output:
2843  * jaunt_status - status of each touching jaunt appearing in jaunt_tbl
2844  * next_start_eu - edgeuse that will be first in the next loop
2845  */
2846 static void
2847 nmg_check_proposed_loop(struct edgeuse *start_eu, struct edgeuse **next_start_eu, int *visit_count, int *jaunt_status, const struct bu_ptbl *jaunt_tbl, const int jaunt_no, const int which_loop)
2848 {
2849  struct edgeuse *loop_eu;
2850  struct edgeuse *last_eu;
2851  int j;
2852  int done = 0;
2853 
2854  NMG_CK_EDGEUSE(start_eu);
2855  BU_CK_PTBL(jaunt_tbl);
2856 
2857  /* Initialize the count */
2858  for (j = 0; j < BU_PTBL_END(jaunt_tbl); j++)
2859  visit_count[j] = 0;
2860 
2861  /* walk through the proposed new loop, updating the visit_count
2862  * and the jaunt status
2863  */
2864  last_eu = NULL;
2865  loop_eu = start_eu;
2866  while (!done) {
2867  for (j = 0; j < BU_PTBL_END(jaunt_tbl); j++) {
2868  struct edgeuse *jaunt_eu;
2869 
2870  /* Don't worry about this jaunt */
2871  if (j == jaunt_no)
2872  continue;
2873 
2874  jaunt_eu = (struct edgeuse *)BU_PTBL_GET(jaunt_tbl, j);
2875  NMG_CK_EDGEUSE(jaunt_eu);
2876 
2877  /* if jaunt number j is included in this loop, update its status */
2878  if (last_eu && last_eu == jaunt_eu)
2879  jaunt_status[j] = JS_JAUNT;
2880 
2881  /* if this loop_eu has its vertex at the apex of one of
2882  * the touching jaunts, increment the appropriate
2883  * visit_count.
2884  */
2885  if (loop_eu->vu_p->v_p == jaunt_eu->eumate_p->vu_p->v_p)
2886  visit_count[j]++;
2887  }
2888  last_eu = loop_eu;
2889  loop_eu = BU_LIST_PNEXT_CIRC(edgeuse, &loop_eu->l);
2890 
2891  /* if "which_loop" is 0, use the nmg_split_lu_at_vu()
2892  * terminate condition, otherwise, continue until we find
2893  * (*next_start_eu)
2894  */
2895  if (!which_loop && loop_eu->vu_p->v_p == start_eu->vu_p->v_p)
2896  done = 1;
2897  else if (which_loop && loop_eu == (*next_start_eu))
2898  done = 1;
2899  }
2900  *next_start_eu = loop_eu;
2901 
2902 
2903  /* check all jaunts to see if they are still touching jaunts in
2904  * the proposed loop
2905  */
2906  for (j = 0; j < BU_PTBL_END(jaunt_tbl); j++) {
2907  if (jaunt_status[j] == JS_JAUNT) {
2908  /* proposed loop contains this jaunt */
2909  if (visit_count[j] > 1) /* it's still a touching jaunt */
2910  jaunt_status[j] = JS_TOUCHING_JAUNT;
2911  }
2912  }
2913 
2914  /* if the first or last eu in the proposed loop is a jaunt eu, the
2915  * proposed loop will split the jaunt, so set its status to
2916  * JS_SPLIT.
2917  */
2918  for (j = 0; j < BU_PTBL_END(jaunt_tbl); j++) {
2919  struct edgeuse *jaunt_eu;
2920  struct edgeuse *jaunt_eu2;
2921 
2922  jaunt_eu = (struct edgeuse *)BU_PTBL_GET(jaunt_tbl, j);
2923  jaunt_eu2 = BU_LIST_PNEXT_CIRC(edgeuse, &jaunt_eu->l);
2924 
2925  if (last_eu == jaunt_eu || start_eu == jaunt_eu2)
2926  jaunt_status[j] = JS_SPLIT;
2927  }
2928 
2929  return;
2930 }
2931 
2932 
2933 void
2934 nmg_kill_accordions(struct loopuse *lu)
2935 {
2936  struct edgeuse *eu_curr, *eu_prev, *eu_next;
2937  int vert_cnt = 0;
2938 
2939  NMG_CK_LOOPUSE(lu);
2940 
2941  eu_curr = eu_prev = eu_next = (struct edgeuse *)NULL;
2942 
2943  if (BU_LIST_IS_EMPTY(&lu->down_hd)) {
2944  return;
2945  }
2946 
2947  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
2948  return;
2949  }
2950 
2951  for (BU_LIST_FOR(eu_curr, edgeuse, &lu->down_hd)) {
2952  vert_cnt++;
2953  }
2954 
2955  eu_curr = BU_LIST_FIRST(edgeuse, &lu->down_hd);
2956  while (BU_LIST_NOT_HEAD(&eu_curr->l, &lu->down_hd) && vert_cnt > 2) {
2957 
2958  eu_prev = BU_LIST_PPREV_CIRC(edgeuse, &eu_curr->l);
2959  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, &eu_curr->l);
2960 
2961  if ((eu_prev->vu_p->v_p == eu_next->vu_p->v_p) && (eu_curr != eu_prev)) {
2962  if (eu_prev != eu_next) {
2963  if ((RTG.NMG_debug & DEBUG_BASIC) || (RTG.NMG_debug & DEBUG_CUTLOOP)) {
2964  bu_log("nmg_kill_accordions(): killing jaunt in accordion eu's %p and %p\n",
2965  (void *)eu_curr, (void *)eu_prev);
2966  }
2967  (void)nmg_keu(eu_curr);
2968  (void)nmg_keu(eu_prev);
2969  vert_cnt -= 2;
2970  } else {
2971  if ((RTG.NMG_debug & DEBUG_BASIC) || (RTG.NMG_debug & DEBUG_CUTLOOP)) {
2972  bu_log("nmg_kill_accordions(): killing jaunt in accordion eu %p\n", (void *)eu_curr);
2973  }
2974  (void)nmg_keu(eu_curr);
2975  vert_cnt--;
2976  }
2977  eu_curr = BU_LIST_FIRST(edgeuse, &lu->down_hd);
2978  } else {
2979  eu_curr = BU_LIST_PNEXT(edgeuse, eu_curr);
2980  }
2981  }
2982 }
2983 
2984 
2985 /**
2986  * If a loop makes a "jaunt" (edgeuses from verts A->B->A), where the
2987  * tip of the jaunt touches the same loop at a different vertexuse,
2988  * cut the loop into two.
2989  *
2990  * This produces a much more reasonable loop split than
2991  * nmg_split_touchingloops(), which tends to peel off 2-edge "cracks"
2992  * as it unravels the loop.
2993  *
2994  * Note that any loops so split will be marked OT_UNSPEC.
2995  */
2996 int
2997 nmg_loop_split_at_touching_jaunt(struct loopuse *lu, const struct bn_tol *tol)
2998 {
2999  struct bu_ptbl jaunt_tbl;
3000  struct loopuse *new_lu;
3001  struct edgeuse *eu;
3002  struct edgeuse *eu2;
3003  int count = 0;
3004  int jaunt_count;
3005  int jaunt_no;
3006  int need_init = 1;
3007  int *visit_count;
3008  int *jaunt_status;
3009  int i;
3010 
3011  NMG_CK_LOOPUSE(lu);
3012  BN_CK_TOL(tol);
3013 
3014  if ((RTG.NMG_debug & DEBUG_BASIC) || (RTG.NMG_debug & DEBUG_CUTLOOP)) {
3015  bu_log("nmg_loop_split_at_touching_jaunt(lu=%p) START\n", (void *)lu);
3016  nmg_pr_lu_briefly(lu, "");
3017  }
3018 
3019  /* first kill any accordion pleats */
3020  nmg_kill_accordions(lu);
3021 
3022  visit_count = (int *)NULL;
3023  jaunt_status = (int *)NULL;
3024 
3025 top:
3026  jaunt_count = nmg_get_touching_jaunts(lu, &jaunt_tbl, &need_init);
3027  if (RTG.NMG_debug & DEBUG_CUTLOOP) {
3028  bu_log("nmg_loop_split_at_touching_jaunt: found %d touching jaunts in lu %p\n",
3029  jaunt_count, (void *)lu);
3030  if (jaunt_count) {
3031  for (i = 0; i < BU_PTBL_END(&jaunt_tbl); i++) {
3032  eu = (struct edgeuse *)BU_PTBL_GET(&jaunt_tbl, i);
3033  bu_log("\t%p\n", (void *)eu);
3034  }
3035  }
3036  }
3037 
3038  if (jaunt_count < 0) {
3039  bu_log("nmg_loop_split_at_touching_jaunt: nmg_get_touching_jaunts() returned %d for lu %p\n",
3040  jaunt_count, (void *)lu);
3041  bu_bomb("nmg_loop_split_at_touching_jaunt: bad jaunt count\n");
3042  }
3043 
3044  if (jaunt_count == 0) {
3045  if (visit_count)
3046  bu_free((char *)visit_count, "nmg_loop_split_at_touching_jaunt: visit_count[]\n");
3047  if (jaunt_status)
3048  bu_free((char *)jaunt_status, "nmg_loop_split_at_touching_jaunt: jaunt_status[]\n");
3049  if (!need_init)
3050  bu_ptbl_free(&jaunt_tbl);
3051 
3052  if ((RTG.NMG_debug & DEBUG_BASIC) || (RTG.NMG_debug & DEBUG_CUTLOOP)) {
3053  bu_log("nmg_loop_split_at_touching_jaunt(lu=%p) END count=%d\n",
3054  (void *)lu, count);
3055  }
3056  return count;
3057  }
3058 
3059  if (jaunt_count == 1) {
3060  /* just one jaunt, split it and return */
3061  BU_CK_PTBL(&jaunt_tbl);
3062 
3063  eu = (struct edgeuse *)BU_PTBL_GET(&jaunt_tbl, 0);
3064  NMG_CK_EDGEUSE(eu);
3065  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, &eu->l);
3066 
3067  new_lu = nmg_split_lu_at_vu(lu, eu2->vu_p);
3068  count++;
3069  NMG_CK_LOOPUSE(new_lu);
3070  NMG_CK_LOOP(new_lu->l_p);
3071  nmg_loop_g(new_lu->l_p, tol);
3072 
3073  bu_ptbl_free(&jaunt_tbl);
3074  if (visit_count)
3075  bu_free((char *)visit_count, "nmg_loop_split_at_touching_jaunt: visit_count[]\n");
3076  if (jaunt_status)
3077  bu_free((char *)jaunt_status, "nmg_loop_split_at_touching_jaunt: jaunt_status[]\n");
3078 
3079  if ((RTG.NMG_debug & DEBUG_BASIC) || (RTG.NMG_debug & DEBUG_CUTLOOP)) {
3080  bu_log("nmg_loop_split_at_touching_jaunt(lu=%p) END count=%d\n",
3081  (void *)lu, count);
3082  }
3083  return count;
3084  }
3085 
3086  /* if we get here, there are at least two touching jaunts in the
3087  * loop. We need to select which order to split them to avoid
3088  * converting the touching jaunt into a crack. To do this, select
3089  * one touching jaunt as the location for splitting the
3090  * loop. Follow the EU's as nmg_split_lu_at_vu() would do and
3091  * predict the status of ALL the touching jaunts (not just the one
3092  * being split). Both the new loop and the remains of the current
3093  * loop must be checked to determine the status of all the
3094  * touching jaunts. The original touching jaunts must either
3095  * remain as touching jaunts in one of the two resulting loops, or
3096  * they must be split between the two resulting loops. If any of
3097  * the touching jaunts are predicted to have a status other than
3098  * split or still touching, then this is a bad choice for
3099  * splitting the loop. For example, a touching jaunt may be
3100  * converted to a non-touching jaunt by applying
3101  * nmg_split_lu_at_vu() at the wrong vu and will later be
3102  * converted to a two edgeuse loop by nmg_split_touching_loops.
3103  */
3104  BU_CK_PTBL(&jaunt_tbl);
3105 
3106  if (visit_count)
3107  bu_free((char *)visit_count, "nmg_loop_split_at_touching_jaunt: visit_count[]\n");
3108  if (jaunt_status)
3109  bu_free((char *)jaunt_status, "nmg_loop_split_at_touching_jaunt: jaunt_status[]\n");
3110 
3111  visit_count = (int *)bu_calloc(BU_PTBL_END(&jaunt_tbl), sizeof(int),
3112  "nmg_loop_split_at_touching_jaunt: visit_count[]");
3113  jaunt_status = (int *)bu_calloc(BU_PTBL_END(&jaunt_tbl), sizeof(int),
3114  "nmg_loop_split_at_touching_jaunt: jaunt_status[]");
3115 
3116  /* consider each jaunt as a possible location for splitting the loop */
3117  for (jaunt_no = 0; jaunt_no < BU_PTBL_END(&jaunt_tbl); jaunt_no++) {
3118  struct edgeuse *start_eu1; /* EU that will start a new loop upon split */
3119  struct edgeuse *start_eu2; /* EU that will start the remaining loop */
3120  int do_split = 1; /* flag: 1 -> this jaunt is a good choice for making the split */
3121 
3122  /* initialize the status of each jaunt to unknown */
3123  for (i = 0; i < BU_PTBL_END(&jaunt_tbl); i++)
3124  jaunt_status[i] = JS_UNKNOWN;
3125 
3126  /* consider splitting lu at this touching jaunt */
3127  eu = (struct edgeuse *)BU_PTBL_GET(&jaunt_tbl, jaunt_no);
3128  NMG_CK_EDGEUSE(eu);
3129 
3130  /* get new loop starting edgeuse */
3131  start_eu1 = BU_LIST_PNEXT_CIRC(edgeuse, &eu->l);
3132 
3133  if (RTG.NMG_debug & DEBUG_CUTLOOP) {
3134  bu_log("\tConsider splitting lu %p at vu=%p\n", (void *)lu, (void *)start_eu1->vu_p);
3135  bu_log("\t\t(jaunt number %d\n", jaunt_no);
3136  }
3137 
3138  /* determine status of jaunts in the proposed new loop */
3139  nmg_check_proposed_loop(start_eu1, &start_eu2, visit_count,
3140  jaunt_status, &jaunt_tbl, jaunt_no, 0);
3141 
3142  /* Still need to check the loop that will be left if we do a split here */
3143  nmg_check_proposed_loop(start_eu2, &start_eu1, visit_count,
3144  jaunt_status, &jaunt_tbl, jaunt_no, 1);
3145 
3146  if (RTG.NMG_debug & DEBUG_CUTLOOP) {
3147  for (i = 0; i < BU_PTBL_END(&jaunt_tbl); i++) {
3148  struct edgeuse *tmp_eu;
3149 
3150  tmp_eu = (struct edgeuse *)BU_PTBL_GET(&jaunt_tbl, i);
3151  bu_log("\t\tpredicted status of jaunt at eu %p is ", (void *)tmp_eu);
3152  switch (jaunt_status[i]) {
3153  case JS_UNKNOWN:
3154  bu_log("unknown\n");
3155  break;
3156  case JS_SPLIT:
3157  bu_log("split\n");
3158  break;
3159  case JS_JAUNT:
3160  bu_log("a jaunt\n");
3161  break;
3162  case JS_TOUCHING_JAUNT:
3163  bu_log("still a touching jaunt\n");
3164  break;
3165  default:
3166  bu_log("unrecognized status\n");
3167  break;
3168  }
3169  }
3170  }
3171 
3172  /* check predicted status of all the touching jaunts, every
3173  * one must be either split or still a touching jaunt. Any
3174  * other status will create loops of two edgeuses!!!
3175  */
3176  for (i = 0; i < BU_PTBL_END(&jaunt_tbl); i++) {
3177  if (jaunt_status[i] != JS_SPLIT && jaunt_status[i] != JS_TOUCHING_JAUNT) {
3178  do_split = 0;
3179  break;
3180  }
3181  }
3182 
3183  /* if splitting lu at this touching jaunt is not desirable, check the next one */
3184  if (!do_split) {
3185  if (RTG.NMG_debug & DEBUG_CUTLOOP) {
3186  bu_log("\t\tCannot split lu %p at proposed vu\n", (void *)lu);
3187  }
3188  continue;
3189  }
3190 
3191  /* This touching jaunt passed all the tests, its reward is to be split */
3192  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, &eu->l);
3193 
3194  new_lu = nmg_split_lu_at_vu(lu, eu2->vu_p);
3195 
3196  if (RTG.NMG_debug & DEBUG_CUTLOOP) {
3197  bu_log("\tnmg_loop_split_at_touching_jaunt: splitting lu %p at vu %p\n", (void *)lu, (void *)eu2->vu_p);
3198  bu_log("\t\tnew_lu is %p\n", (void *)new_lu);
3199  }
3200 
3201  count++;
3202  NMG_CK_LOOPUSE(new_lu);
3203  NMG_CK_LOOP(new_lu->l_p);
3204  nmg_loop_g(new_lu->l_p, tol);
3205  bu_ptbl_reset(&jaunt_tbl);
3206 
3207  /* recurse on the new loop */
3208  count += nmg_loop_split_at_touching_jaunt(new_lu, tol);
3209 
3210  /* continue with the remains of the current loop */
3211  goto top;
3212  }
3213 
3214  /* If we ever get here, we have failed to find a way to split this loop!!!! */
3215  bu_log("nmg_loop_split_at_touching_jaunt: Could not find a way to split lu %p\n", (void *)lu);
3216  nmg_pr_lu_briefly(lu, " ");
3217  nmg_stash_model_to_file("jaunt.g", nmg_find_model(&lu->l.magic), "Can't split lu");
3218  bu_bomb("nmg_loop_split_at_touching_jaunt: Can't split lu\n");
3219 
3220  /* This return will never execute, but the compilers like it */
3221  return count;
3222 }
3223 
3224 
3225 /**
3226  * combine adjacent loops within the same parent that touch along a
3227  * common edge into a single loop, with the edge eliminated.
3228  */
3229 void
3230 nmg_simplify_loop(struct loopuse *lu)
3231 {
3232  struct edgeuse *eu, *eu_r, *tmpeu;
3233 
3234  NMG_CK_LOOPUSE(lu);
3235  if (RTG.NMG_debug & DEBUG_BASIC) {
3236  bu_log("nmg_simplify_loop(lu=%p)\n", (void *)lu);
3237  }
3238 
3239  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
3240  return;
3241 
3242  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
3243  while (BU_LIST_NOT_HEAD(eu, &lu->down_hd)) {
3244 
3245  NMG_CK_EDGEUSE(eu);
3246 
3247  eu_r = eu->radial_p;
3248  NMG_CK_EDGEUSE(eu_r);
3249 
3250  /* if the radial edge is part of a loop, and the loop of the
3251  * other edge is a part of the same object (face) as the loop
3252  * containing the current edge, and my edgeuse mate is radial
3253  * to my radial`s edgeuse mate, and the radial edge is a part
3254  * of a loop other than the one "eu" is a part of then this is
3255  * a "worthless" edge between these two loops.
3256  */
3257  if (*eu_r->up.magic_p == NMG_LOOPUSE_MAGIC &&
3258  eu_r->up.lu_p->up.magic_p == lu->up.magic_p &&
3259  eu->eumate_p->radial_p == eu->radial_p->eumate_p &&
3260  eu_r->up.lu_p != lu) {
3261 
3262  if (eu_r->up.lu_p->orientation != lu->orientation &&
3263  (lu->orientation != OT_SAME ||
3264  eu_r->up.lu_p->orientation != OT_OPPOSITE)) {
3265  /* Does not meet requirements of nmg_jl(), skip it.
3266  */
3267  eu = BU_LIST_PNEXT(edgeuse, eu);
3268  continue;
3269  }
3270 
3271  /* save a pointer to where we've already been so that when
3272  * eu becomes an invalid pointer, we still know where to
3273  * pick up from.
3274  */
3275  tmpeu = BU_LIST_PLAST(edgeuse, eu);
3276 
3277  nmg_jl(lu, eu);
3278 
3279  /* Since all the new edges will have been appended after
3280  * tmpeu, we can pick up processing with the edgeuse
3281  * immediately after tmpeu
3282  */
3283  eu = tmpeu;
3284 
3285  if (RTG.NMG_debug &(DEBUG_PLOTEM|DEBUG_PL_ANIM) && *lu->up.magic_p == NMG_FACEUSE_MAGIC) {
3286  nmg_pl_2fu("After_joinloop%d.plot3", lu->up.fu_p, lu->up.fu_p->fumate_p, 0);
3287  }
3288  }
3289  eu = BU_LIST_PNEXT(edgeuse, eu);
3290  }
3291 }
3292 
3293 
3294 /**
3295  * Removes "snake" or "disconnected crack" edges from loopuse.
3296  *
3297  * Returns -
3298  * 0 If all went well
3299  * 1 If the loopuse is now empty and needs to be killed.
3300  */
3301 int
3302 nmg_kill_snakes(struct loopuse *lu)
3303 {
3304  struct edgeuse *eu, *eu_r;
3305  struct vertexuse *vu;
3306  struct vertex *v;
3307 
3308  NMG_CK_LOOPUSE(lu);
3309  if (RTG.NMG_debug & DEBUG_BASIC) {
3310  bu_log("nmg_kill_snakes(lu=%p)\n", (void *)lu);
3311  }
3312  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
3313  return 0;
3314 
3315  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
3316  while (BU_LIST_NOT_HEAD(eu, &lu->down_hd)) {
3317 
3318  NMG_CK_EDGEUSE(eu);
3319 
3320  eu_r = eu->radial_p;
3321  NMG_CK_EDGEUSE(eu_r);
3322 
3323  /* if the radial edge is a part of the same loop, and this
3324  * edge is not used by anyplace else, and the radial edge is
3325  * also the next edge, this MAY be the tail of a snake!
3326  */
3327 
3328  if (*eu_r->up.magic_p == NMG_LOOPUSE_MAGIC &&
3329  eu_r->up.lu_p == eu->up.lu_p &&
3330  eu->eumate_p->radial_p == eu->radial_p->eumate_p &&
3331  BU_LIST_PNEXT_CIRC(edgeuse, eu) == eu_r) {
3332 
3333  /* if there are no other uses of the vertex
3334  * between these two edgeuses, then this is
3335  * indeed the tail of a snake
3336  */
3337  v = eu->eumate_p->vu_p->v_p;
3338  vu = BU_LIST_FIRST(vertexuse, &v->vu_hd);
3339  while (BU_LIST_NOT_HEAD(vu, &v->vu_hd) &&
3340  (vu->up.eu_p == eu->eumate_p ||
3341  vu->up.eu_p == eu_r))
3342  vu = BU_LIST_PNEXT(vertexuse, vu);
3343 
3344  if (! BU_LIST_NOT_HEAD(vu, &v->vu_hd)) {
3345  /* this is the tail of a snake! */
3346  (void)nmg_keu(eu_r);
3347  if (nmg_keu(eu)) return 1; /* kill lu */
3348  if (BU_LIST_IS_EMPTY(&lu->down_hd))
3349  return 1; /* loopuse is empty */
3350  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
3351 
3352  if (RTG.NMG_debug &(DEBUG_PLOTEM|DEBUG_PL_ANIM) && *lu->up.magic_p == NMG_FACEUSE_MAGIC) {
3353 
3354  nmg_pl_2fu("After_joinloop%d.plot3", lu->up.fu_p, lu->up.fu_p->fumate_p, 0);
3355 
3356  }
3357 
3358 
3359  } else
3360  eu = BU_LIST_PNEXT(edgeuse, eu);
3361  } else
3362  eu = BU_LIST_PNEXT(edgeuse, eu);
3363  }
3364  return 0; /* All is well, loop still has edges */
3365 }
3366 
3367 
3368 /**
3369  * Move a wire-loopuse from one shell to another. Note that this
3370  * routine can not be used on loops in faces.
3371  */
3372 void
3373 nmg_mv_lu_between_shells(struct shell *dest, register struct shell *src, register struct loopuse *lu)
3374 {
3375  register struct loopuse *lumate;
3376 
3377  NMG_CK_LOOPUSE(lu);
3378  lumate = lu->lumate_p;
3379  NMG_CK_LOOPUSE(lumate);
3380 
3381  if (lu->up.s_p != src) {
3382  bu_log("nmg_mv_lu_between_shells(dest=%p, src=%p, lu=%p), lu->up.s_p=%p isn't source shell\n",
3383  (void *)dest, (void *)src, (void *)lu, (void *)lu->up.s_p);
3384  bu_bomb("lu->up.s_p isn't source shell\n");
3385  }
3386  if (lumate->up.s_p != src) {
3387  bu_log("nmg_mv_lu_between_shells(dest=%p, src=%p, lu=%p), lumate->up.s_p=%p isn't source shell\n",
3388  (void *)dest, (void *)src, (void *)lu, (void *)lumate->up.s_p);
3389  bu_bomb("lumate->up.s_p isn't source shell\n");
3390  }
3391 
3392  /* Remove lu from src shell */
3393  BU_LIST_DEQUEUE(&lu->l);
3394  if (BU_LIST_IS_EMPTY(&src->lu_hd)) {
3395  /* This was the last lu in the list */
3396  bu_log("nmg_mv_lu_between_shells(dest=%p, src=%p, lu=%p), lumate=%p not in src shell\n",
3397  (void *)dest, (void *)src, (void *)lu, (void *)lumate);
3398  bu_bomb("src shell emptied before finding lumate\n");
3399  }
3400 
3401  /* Remove lumate from src shell */
3402  BU_LIST_DEQUEUE(&lumate->l);
3403 
3404  /* Add lu and lumate to dest shell */
3405  BU_LIST_APPEND(&dest->lu_hd, &lu->l);
3406  BU_LIST_APPEND(&lu->l, &lumate->l);
3407 
3408  lu->up.s_p = dest;
3409  lumate->up.s_p = dest;
3410 
3411  if (RTG.NMG_debug & DEBUG_BASIC) {
3412  bu_log("nmg_mv_lu_between_shells(dest=%p, src=%p, lu=%p)\n",
3413  (void *)dest, (void *)src, (void *)lu);
3414  }
3415 }
3416 
3417 
3418 /**
3419  * move first pair of shell wire loopuses out to become a genuine loop
3420  * in an existing face.
3421  *
3422  * XXX This routine is not used anywhere, and may not work.
3423  */
3424 void nmg_moveltof(struct faceuse *fu, struct shell *s)
3425 {
3426  struct loopuse *lu1, *lu2;
3427 
3428  NMG_CK_SHELL(s);
3429  NMG_CK_FACEUSE(fu);
3430  if (fu->s_p != s) {
3431  bu_log("nmg_moveltof() in %s at %d. Cannot move loop to face in another shell\n",
3432  __FILE__, __LINE__);
3433  }
3434  lu1 = BU_LIST_FIRST(loopuse, &s->lu_hd);
3435  NMG_CK_LOOPUSE(lu1);
3436  BU_LIST_DEQUEUE(&lu1->l);
3437 
3438  lu2 = BU_LIST_FIRST(loopuse, &s->lu_hd);
3439  NMG_CK_LOOPUSE(lu2);
3440  BU_LIST_DEQUEUE(&lu2->l);
3441 
3442  BU_LIST_APPEND(&fu->lu_hd, &lu1->l);
3443  BU_LIST_APPEND(&fu->fumate_p->lu_hd, &lu2->l);
3444  /* XXX What about loopuse "up" pointers? */
3445 
3446  if (RTG.NMG_debug & DEBUG_BASIC) {
3447  bu_log("nmg_moveltof(fu=%p, s=%p)\n",
3448  (void *)fu, (void *)s);
3449  }
3450 }
3451 
3452 
3453 /**
3454  * A support routine for nmg_dup_face()
3455  *
3456  * trans_tbl may be NULL.
3457  */
3458 struct loopuse *
3459 nmg_dup_loop(struct loopuse *lu, uint32_t *parent, long int **trans_tbl)
3460 
3461 /* fu or shell ptr */
3462 
3463 {
3464  struct loopuse *new_lu = (struct loopuse *)NULL;
3465  struct vertexuse *new_vu = (struct vertexuse *)NULL;
3466  struct vertexuse *old_vu = (struct vertexuse *)NULL;
3467  struct vertex *old_v = (struct vertex *)NULL;
3468  struct vertex *new_v;
3469  struct edgeuse *new_eu = (struct edgeuse *)NULL;
3470  struct edgeuse *tbl_eu = (struct edgeuse *)NULL;
3471  struct edgeuse *eu = (struct edgeuse *)NULL;
3472 
3473  NMG_CK_LOOPUSE(lu);
3474 
3475  /* if loop is just a vertex, that's simple to duplicate */
3476  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
3477  old_vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
3478  old_v = old_vu->v_p;
3479 
3480  /* Obtain new duplicate of old vertex. May be null 1st time. */
3481  if (trans_tbl)
3482  new_v = NMG_INDEX_GETP(vertex, trans_tbl, old_v);
3483  else
3484  new_v = (struct vertex *)NULL;
3485  new_lu = nmg_mlv(parent, new_v, lu->orientation);
3486  if (new_lu->orientation != lu->orientation) {
3487  bu_log("%s %d: I asked for a %s loop not a %s loop.\n",
3488  __FILE__, __LINE__,
3489  nmg_orientation(lu->orientation),
3490  nmg_orientation(new_lu->orientation));
3491  bu_bomb("bombing\n");
3492  }
3493  if (new_v) {
3494  /* the new vertex already exists in the new model */
3495  bu_log("nmg_dup_loop() existing vertex in new model\n");
3496  return (struct loopuse *)NULL;
3497  }
3498  /* nmg_mlv made a new vertex */
3499  bu_log("nmg_dup_loop() new vertex in new model\n");
3500 
3501  new_vu = BU_LIST_FIRST(vertexuse, &new_lu->down_hd);
3502  new_v = new_vu->v_p;
3503  /* Give old_v entry a pointer to new_v */
3504  if (trans_tbl)
3505  NMG_INDEX_ASSIGN(trans_tbl, old_v, (long *)new_v);
3506  if (old_v->vg_p) {
3507  /* Build a different vertex_g with same coordinates */
3508  nmg_vertex_gv(new_v, old_v->vg_p->coord);
3509  }
3510  if (RTG.NMG_debug & DEBUG_BASIC) {
3511  bu_log("nmg_dup_loop(lu=%p, parent=%p, trans_tbl=%p) new_lu=%p\n",
3512  (void *)lu, (void *)parent, (void *)trans_tbl, (void *)new_lu);
3513  }
3514  return new_lu;
3515  }
3516 
3517  /* This loop is an edge-loop. This is a little more work First
3518  * order of business is to duplicate the vertex/edge makeup.
3519  */
3520  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
3521 
3522  NMG_CK_EDGEUSE(eu);
3523  NMG_CK_VERTEXUSE(eu->vu_p);
3524  NMG_CK_VERTEX(eu->vu_p->v_p);
3525  old_v = eu->vu_p->v_p;
3526 
3527  /* Obtain new duplicate of old vertex. May be null 1st time. */
3528  if (trans_tbl)
3529  new_v = NMG_INDEX_GETP(vertex, trans_tbl, old_v);
3530  else
3531  new_v = (struct vertex *)NULL;
3532 
3533  if (new_lu == (struct loopuse *)NULL) {
3534  /* this is the first edge in the new loop */
3535  new_lu = nmg_mlv(parent, new_v, lu->orientation);
3536  if (new_lu->orientation != lu->orientation) {
3537  bu_log("%s %d: I asked for a %s loop not a %s loop.\n",
3538  __FILE__, __LINE__,
3539  nmg_orientation(lu->orientation),
3540  nmg_orientation(new_lu->orientation));
3541  bu_bomb("bombing\n");
3542  }
3543 
3544  new_vu = BU_LIST_FIRST(vertexuse, &new_lu->down_hd);
3545 
3546  NMG_CK_VERTEXUSE(new_vu);
3547  NMG_CK_VERTEX(new_vu->v_p);
3548 
3549  if (!new_v && trans_tbl) {
3550  /* Give old_v entry a pointer to new_v */
3551  NMG_INDEX_ASSIGN(trans_tbl, old_v,
3552  (long *)new_vu->v_p);
3553  }
3554  new_v = new_vu->v_p;
3555 
3556  new_eu = nmg_meonvu(new_vu);
3557  } else {
3558  /* not the first edge in new loop */
3559  new_eu = BU_LIST_LAST(edgeuse, &new_lu->down_hd);
3560  NMG_CK_EDGEUSE(new_eu);
3561 
3562  new_eu = nmg_eusplit(new_v, new_eu, 0);
3563  new_vu = new_eu->vu_p;
3564 
3565  if (!new_v && trans_tbl) {
3566  /* Give old_v entry a pointer to new_v */
3567  NMG_INDEX_ASSIGN(trans_tbl, old_v,
3568  (long *)new_vu->v_p);
3569  }
3570  new_v = new_vu->v_p;
3571  }
3572  /* Build a different vertex_g with same coordinates */
3573  if (old_v->vg_p) {
3574  NMG_CK_VERTEX_G(old_v->vg_p);
3575  nmg_vertex_gv(new_v, old_v->vg_p->coord);
3576  }
3577 
3578  /* Prepare to glue edges */
3579  /* Use old_e as subscript, to get 1st new_eu (for new_e) */
3580  /* Use old_eu to get mapped new_eu */
3581  if (trans_tbl)
3582  tbl_eu = NMG_INDEX_GETP(edgeuse, trans_tbl, eu->e_p);
3583  else
3584  tbl_eu = (struct edgeuse *)NULL;
3585  if (!tbl_eu && trans_tbl) {
3586  /* Establishes map from old edge to new edge(+use) */
3587  NMG_INDEX_ASSIGN(trans_tbl, eu->e_p, (long *)new_eu);
3588  }
3589  if (trans_tbl)
3590  NMG_INDEX_ASSIGN(trans_tbl, eu, (long *)new_eu);
3591  }
3592 
3593  /* Now that we've got all the right topology created and the
3594  * vertex geometries are in place we can create the edge geometries.
3595  * XXX This ought to be optional, as most callers will immediately
3596  * XXX change the vertex geometry anyway (e.g. by extrusion dist).
3597  */
3598  for (BU_LIST_FOR(new_eu, edgeuse, &new_lu->down_hd)) {
3599  NMG_CK_EDGEUSE(new_eu);
3600  NMG_CK_EDGE(new_eu->e_p);
3601  if (new_eu->g.magic_p) continue;
3602  nmg_edge_g(new_eu);
3603  }
3604 
3605  if (RTG.NMG_debug & DEBUG_BASIC) {
3606  bu_log("nmg_dup_loop(lu=%p(%s), parent=%p, trans_tbl=%p) new_lu=%p(%s)\n",
3607  (void *)lu, nmg_orientation(lu->orientation),
3608  (void *)parent, (void *)trans_tbl,
3609  (void *)new_lu, nmg_orientation(new_lu->orientation));
3610  }
3611  return new_lu;
3612 }
3613 
3614 
3615 /**
3616  * Set this loopuse and mate's orientation to be SAME or OPPOSITE from
3617  * the orientation of the faceuse they each reside in.
3618  */
3619 void
3620 nmg_set_lu_orientation(struct loopuse *lu, int is_opposite)
3621 {
3622  NMG_CK_LOOPUSE(lu);
3623  NMG_CK_LOOPUSE(lu->lumate_p);
3624  if (RTG.NMG_debug & DEBUG_BASIC) {
3625  bu_log("nmg_set_lu_orientation(lu=%p, %s)\n",
3626  (void *)lu, is_opposite?"OT_OPPOSITE":"OT_SAME");
3627  }
3628  if (is_opposite) {
3629  /* Interior (crack) loop */
3630  lu->orientation = OT_OPPOSITE;
3631  lu->lumate_p->orientation = OT_OPPOSITE;
3632  } else {
3633  /* Exterior loop */
3634  lu->orientation = OT_SAME;
3635  lu->lumate_p->orientation = OT_SAME;
3636  }
3637 }
3638 
3639 
3640 /**
3641  * Based upon a geometric calculation, reorient a loop and its mate,
3642  * if the stored orientation differs from the geometric one.
3643  *
3644  * Note that the loopuse and its mate have the same orientation; it's
3645  * the faceuses that are normalward and anti-normalward. The loopuses
3646  * either both agree with their faceuse, or both differ.
3647  */
3648 void
3649 nmg_lu_reorient(struct loopuse *lu)
3650 {
3651  struct faceuse *fu;
3652  int geom_orient;
3653  plane_t norm;
3654  plane_t lu_pl;
3655 
3656  NMG_CK_LOOPUSE(lu);
3657 
3658  if (RTG.NMG_debug & DEBUG_BASIC) {
3659  bu_log("nmg_lu_reorient(lu=%p)\n", (void *)lu);
3660  }
3661 
3662  /* Don't harm the OT_BOOLPLACE self-loop marker vertices */
3663  if (lu->orientation == OT_BOOLPLACE &&
3664  BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC)
3665  return;
3666 
3667  fu = lu->up.fu_p;
3668  NMG_CK_FACEUSE(fu);
3669  if (fu->orientation != OT_SAME) {
3670  lu = lu->lumate_p;
3671  NMG_CK_LOOPUSE(lu);
3672  fu = lu->up.fu_p;
3673  NMG_CK_FACEUSE(fu);
3674  if (RTG.NMG_debug & DEBUG_BASIC)
3675  bu_log("nmg_lu_reorient() selecting other fu=%p, lu=%p\n", (void *)fu, (void *)lu);
3676  if (fu->orientation != OT_SAME)
3677  bu_bomb("nmg_lu_reorient() no OT_SAME fu?\n");
3678  }
3679 
3680 
3681  /* Get OT_SAME faceuse's normal */
3682  NMG_GET_FU_PLANE(norm, fu);
3683  if (RTG.NMG_debug & DEBUG_BASIC) {
3684  PLPRINT("\tfu peqn", norm);
3685  }
3686 
3687  nmg_loop_plane_newell(lu, lu_pl);
3688 
3689  if (lu->orientation == OT_OPPOSITE)
3690  HREVERSE(lu_pl, lu_pl);
3691 
3692  if (VDOT(lu_pl, norm) < -SMALL_FASTF)
3693  geom_orient = OT_OPPOSITE;
3694  else
3695  geom_orient = OT_SAME;
3696 
3697  if (lu->orientation == geom_orient) return;
3698  if (RTG.NMG_debug & DEBUG_BASIC) {
3699  bu_log("nmg_lu_reorient(%p): changing orientation: %s to %s\n",
3700  (void *)lu, nmg_orientation(lu->orientation),
3701  nmg_orientation(geom_orient));
3702  }
3703 
3704  lu->orientation = geom_orient;
3705  lu->lumate_p->orientation = geom_orient;
3706 }
3707 
3708 
3709 /************************************************************************
3710  * *
3711  * EDGE Routines *
3712  * *
3713  ************************************************************************/
3714 
3715 
3716 /**
3717  * Split an edgeuse by inserting a vertex into middle of the edgeuse.
3718  *
3719  * Make a new edge, and a vertex. If v is non-null it is taken as a
3720  * pointer to an existing vertex to use as the start of the new edge.
3721  * If v is null, then a new vertex is created for the beginning of the
3722  * new edge.
3723  *
3724  * In either case, the new edge will exist as the "next" edgeuse after
3725  * the edgeuse passed as a parameter.
3726  *
3727  * Upon return, the new edgeuses (eu1 and mate) will not refer to any
3728  * geometry, unless argument "share_geom" was non-zero.
3729  *
3730  * Explicit return -
3731  * edgeuse of new edge "eu1", starting at V and going to B.
3732  *
3733  * List on entry -
3734  *
3735  * oldeu
3736  * .------------->
3737  * /
3738  * A =============== B (edge)
3739  * /
3740  * <-------------.
3741  * oldeumate
3742  *
3743  * List on return -
3744  *
3745  * oldeu(cw) eu1
3746  * .-------> .----->
3747  * / /
3748  * (edge) A ========= V ~~~~~~~ B (new edge)
3749  * / /
3750  * <-------. <-----.
3751  * mate mate
3752  */
3753 struct edgeuse *
3754 nmg_eusplit(struct vertex *v, struct edgeuse *oldeu, int share_geom)
3755 {
3756  struct edgeuse *eu1,
3757  *eu2,
3758  *oldeumate;
3759  struct shell *s = NULL;
3760  struct loopuse *lu;
3761 
3762  NMG_CK_EDGEUSE(oldeu);
3763  if (v) {
3764  NMG_CK_VERTEX(v);
3765  }
3766  oldeumate = oldeu->eumate_p;
3767  NMG_CK_EDGEUSE(oldeumate);
3768 
3769  /* if this edge has uses other than this edge and its mate, we
3770  * must separate these two edgeuses from the existing edge, and
3771  * create a new edge for them. Then we can insert a new vertex in
3772  * this new edge without fear of damaging some other object.
3773  */
3774  if (oldeu->radial_p != oldeumate)
3775  nmg_unglueedge(oldeu);
3776 
3777  if (*oldeu->up.magic_p == NMG_SHELL_MAGIC) {
3778  s = oldeu->up.s_p;
3779  NMG_CK_SHELL(s);
3780 
3781  /*
3782  * Make an edge from the new vertex ("V") to vertex at other
3783  * end of the edge given ("B"). The new vertex "V" may be
3784  * NULL, which will cause the shell's lone vertex to be used,
3785  * or a new one obtained. New edges will be placed at head of
3786  * shell's edge list.
3787  */
3788  eu1 = nmg_me(v, oldeumate->vu_p->v_p, s);
3789  eu2 = eu1->eumate_p;
3790 
3791  /*
3792  * The situation is now:
3793  *
3794  * eu1 oldeu
3795  * .-----------> .------------->
3796  * / /
3797  *V ~~~~~~~~~~~~~ B (new edge) A =============== B (edge)
3798  * / /
3799  * <-----------. <-------------.
3800  * eu2 oldeumate
3801  */
3802 
3803  /* Make oldeumate start at "V", not "B" */
3804  nmg_movevu(oldeumate->vu_p, eu1->vu_p->v_p);
3805 
3806  /*
3807  * Enforce rigid ordering in shell's edge list: oldeu,
3808  * oldeumate, eu1, eu2. This is to keep edges & mates "close
3809  * to each other".
3810  */
3811  if (BU_LIST_PNEXT(edgeuse, oldeu) != oldeumate) {
3812  BU_LIST_DEQUEUE(&oldeumate->l);
3813  BU_LIST_APPEND(&oldeu->l, &oldeumate->l);
3814  }
3815  BU_LIST_DEQUEUE(&eu1->l);
3816  BU_LIST_DEQUEUE(&eu2->l);
3817  BU_LIST_APPEND(&oldeumate->l, &eu1->l);
3818  BU_LIST_APPEND(&eu1->l, &eu2->l);
3819 
3820  /*
3821  * oldeu(cw) eu1
3822  * .-------> .----->
3823  * / /
3824  * (edge) A ========= V ~~~~~~~ B (new edge)
3825  * / /
3826  * <-------. <-----.
3827  * oldeumate eu2
3828  */
3829  if (share_geom) {
3830  /* Make eu1 share geom with oldeu, eu2 with oldeumate */
3831  nmg_use_edge_g(eu1, oldeu->g.magic_p);
3832  nmg_use_edge_g(eu2, oldeumate->g.magic_p);
3833  } else {
3834  /* Make eu2 use same geometry as oldeu */
3835  nmg_use_edge_g(eu2, oldeu->g.magic_p);
3836  /* Now release geometry from oldeumate; new edge has no geom */
3837  BU_LIST_DEQUEUE(&oldeumate->l2);
3838  nmg_keg(oldeumate);
3839  BU_LIST_DEQUEUE(&eu1->l2);
3840  nmg_keg(eu1);
3841  BU_LIST_INIT(&oldeumate->l2);
3842  BU_LIST_INIT(&eu1->l2);
3843  oldeumate->l2.magic = NMG_EDGEUSE2_MAGIC;
3844  eu1->l2.magic = NMG_EDGEUSE2_MAGIC;
3845  }
3846  goto out;
3847  } else if (*oldeu->up.magic_p != NMG_LOOPUSE_MAGIC) {
3848  bu_log("nmg_eusplit() in %s at %d invalid edgeuse parent\n",
3849  __FILE__, __LINE__);
3850  bu_bomb("nmg_eusplit\n");
3851  }
3852 
3853  /* now we know we are in a loop */
3854 
3855  lu = oldeu->up.lu_p;
3856  NMG_CK_LOOPUSE(lu);
3857 
3858  /* get a parent shell pointer so we can make a new edge */
3859  if (*lu->up.magic_p == NMG_SHELL_MAGIC)
3860  s = lu->up.s_p;
3861  else if (*lu->up.magic_p == NMG_FACEUSE_MAGIC)
3862  s = lu->up.fu_p->s_p;
3863  else
3864  bu_bomb("nmg_eusplit() bad lu->up\n");
3865  NMG_CK_SHELL(s);
3866 
3867  /* Make a new wire edge in the shell */
3868  if (v) {
3869  /* An edge on the single vertex "V" */
3870  eu1 = nmg_me(v, v, s);
3871  eu2 = eu1->eumate_p;
3872  } else {
3873  /* Form a wire edge between two new vertices */
3874  eu1 = nmg_me((struct vertex *)NULL, (struct vertex *)NULL, s);
3875  eu2 = eu1->eumate_p;
3876  /* Make both ends of edge use same vertex.
3877  * The second vertex is freed automatically.
3878  */
3879  nmg_movevu(eu2->vu_p, eu1->vu_p->v_p);
3880  }
3881 
3882  /*
3883  * The current situation is now:
3884  *
3885  * eu1 oldeu
3886  * .-------------> .------------->
3887  * / /
3888  * V ~~~~~~~~~~~~~~~ V (new edge) A =============== B (edge)
3889  * / /
3890  * <-------------. <-------------.
3891  * eu2 oldeumate
3892  *
3893  * Goals:
3894  * eu1 will become the mate to oldeumate on the existing edge.
3895  * eu2 will become the mate of oldeu on the new edge.
3896  */
3897  BU_LIST_DEQUEUE(&eu1->l);
3898  BU_LIST_DEQUEUE(&eu2->l);
3899  BU_LIST_APPEND(&oldeu->l, &eu1->l);
3900  BU_LIST_APPEND(&oldeumate->l, &eu2->l);
3901 
3902  /*
3903  * The situation is now:
3904  *
3905  * oldeu eu1 >>>loop>>>
3906  * .-------> .----->
3907  * / /
3908  * (edge) A ========= V ~~~~~~~ B (new edge)
3909  * / /
3910  * <-------. <-----.
3911  * eu2 oldeumate <<<loop<<<
3912  */
3913 
3914  /* Copy parentage (loop affiliation) and orientation */
3915  eu1->up.magic_p = oldeu->up.magic_p;
3916  eu1->orientation = oldeu->orientation;
3917 
3918  eu2->up.magic_p = oldeumate->up.magic_p;
3919  eu2->orientation = oldeumate->orientation;
3920 
3921  /* Build mate relationship */
3922  eu1->eumate_p = oldeumate;
3923  oldeumate->eumate_p = eu1;
3924  eu2->eumate_p = oldeu;
3925  oldeu->eumate_p = eu2;
3926 
3927  /* Build radial relationship.
3928  * Simple only because this edge has no other uses.
3929  */
3930  eu1->radial_p = oldeumate;
3931  oldeumate->radial_p = eu1;
3932  eu2->radial_p = oldeu;
3933  oldeu->radial_p = eu2;
3934 
3935  /* Associate oldeumate with new edge, and eu2 with old edge. */
3936  oldeumate->e_p = eu1->e_p;
3937  eu2->e_p = oldeu->e_p;
3938 
3939  /* Ensure that edge points up to one of the proper edgeuses. */
3940  oldeumate->e_p->eu_p = oldeumate;
3941  eu2->e_p->eu_p = eu2;
3942 
3943  if (share_geom) {
3944  /* Make eu1 share same geometry as oldeu */
3945  nmg_use_edge_g(eu1, oldeu->g.magic_p);
3946  /* Make eu2 share same geometry as oldeumate */
3947  nmg_use_edge_g(eu2, oldeumate->g.magic_p);
3948  } else {
3949  /* Make eu2 use same geometry as oldeu */
3950  nmg_use_edge_g(eu2, oldeu->g.magic_p);
3951  /* Now release geometry from oldeumate; new edge has no geom */
3952  BU_LIST_DEQUEUE(&oldeumate->l2);
3953  nmg_keg(oldeumate);
3954  BU_LIST_DEQUEUE(&eu1->l2);
3955  nmg_keg(eu1);
3956  BU_LIST_INIT(&oldeumate->l2);
3957  BU_LIST_INIT(&eu1->l2);
3958  oldeumate->l2.magic = NMG_EDGEUSE2_MAGIC;
3959  eu1->l2.magic = NMG_EDGEUSE2_MAGIC;
3960  }
3961  if (oldeu->g.magic_p != oldeu->eumate_p->g.magic_p) bu_bomb("nmg_eusplit() unshared geom\n");
3962 
3963 out:
3964  if (RTG.NMG_debug & DEBUG_BASIC) {
3965  bu_log("nmg_eusplit(v=%p, eu=%p, share=%d) new_eu=%p, mate=%p\n",
3966  (void *)v, (void *)oldeu, share_geom,
3967  (void *)eu1, (void *)eu1->eumate_p);
3968  }
3969  return eu1;
3970 }
3971 
3972 
3973 /**
3974  * Split an edge by inserting a vertex into middle of *all* of the
3975  * uses of this edge, and combine the new edgeuses together onto the
3976  * new edge. A more powerful version of nmg_eusplit(), which does
3977  * only one use.
3978  *
3979  * Makes a new edge, and a vertex. If v is non-null it is taken as a
3980  * pointer to an existing vertex to use as the start of the new edge.
3981  * If v is null, then a new vertex is created for the beginning of the
3982  * new edge.
3983  *
3984  * In either case, the new edgeuse will exist as the "next" edgeuse
3985  * after the edgeuse passed as a parameter.
3986  *
3987  * Note that eu->e_p changes value upon return, because the old edge
3988  * is incrementally replaced by two new ones.
3989  *
3990  * Geometry will be preserved on eu and its mates (by nmg_eusplit),
3991  * if any. ret_eu and mates will share that geometry if share_geom is
3992  * set non-zero, otherwise they will have null geom pointers.
3993  *
3994  * Explicit return -
3995  * Pointer to the edgeuse which starts at the newly created
3996  * vertex (V), and runs to B.
3997  *
3998  * Implicit returns -
3999  * ret_eu->vu_p->v_p gives the new vertex ("v", if non-null), and
4000  * ret_eu->e_p is the new edge that runs from V to B.
4001  *
4002  * The new vertex created will also be eu->eumate_p->vu_p->v_p.
4003  *
4004  * Edge on entry -
4005  *
4006  * eu
4007  * .------------->
4008  * /
4009  * A =============== B (edge)
4010  * /
4011  * <-------------.
4012  * eu->eumate_p
4013  *
4014  * Edge on return -
4015  *
4016  * eu ret_eu
4017  * .-------> .--------->
4018  * / /
4019  * (newedge) A ========= V ~~~~~~~~~~~ B (new edge)
4020  * / /
4021  * <-------. <---------.
4022  *
4023  * Note: to replicate the behavior of this routine in BRL-CAD Release
4024  * 4.0, call with share_geom=0.
4025  */
4026 struct edgeuse *
4027 nmg_esplit(struct vertex *v, struct edgeuse *eu, int share_geom)
4028 /* New vertex, to go in middle */
4029 
4030 
4031 {
4032  struct edge *e; /* eu->e_p */
4033  struct edgeuse *teuX, /* radial edgeuse of eu */
4034  *teuY, /* new edgeuse (next of teuX) */
4035  *neu1, *neu2; /* new (split) edgeuses */
4036  int notdone = 1;
4037  struct vertex *vA, *vB; /* start and end of eu */
4038 
4039  neu1 = neu2 = (struct edgeuse *)NULL;
4040 
4041  NMG_CK_EDGEUSE(eu);
4042  e = eu->e_p;
4043  NMG_CK_EDGE(e);
4044 
4045  NMG_CK_VERTEXUSE(eu->vu_p);
4046  vA = eu->vu_p->v_p;
4047  NMG_CK_VERTEX(vA);
4048 
4049  NMG_CK_EDGEUSE(eu->eumate_p);
4050  NMG_CK_VERTEXUSE(eu->eumate_p->vu_p);
4051  vB = eu->eumate_p->vu_p->v_p;
4052  NMG_CK_VERTEX(vB);
4053 
4054  if (v && (v == vA || v == vB)) {
4055  bu_log("WARNING: nmg_esplit(v=%p) vertex is already an edge vertex\n", (void *)v);
4056  bu_bomb("nmg_esplit() new vertex is already an edge vertex\n");
4057  }
4058 
4059  /* one at a time, we peel out & split an edgeuse pair of this
4060  * edge. when we split an edge that didn't need to be peeled out,
4061  * we know we've split the last edge
4062  */
4063  do {
4064  /* Peel two temporary edgeuses off the original edge */
4065  teuX = eu->radial_p;
4066  /* teuX runs from vA to vB */
4067  teuY = nmg_eusplit(v, teuX, share_geom);
4068  /* Now, teuX runs from vA to v, teuY runs from v to vB */
4069  NMG_CK_EDGEUSE(teuX);
4070  NMG_CK_EDGEUSE(teuY);
4071  NMG_TEST_EDGEUSE(teuX);
4072  NMG_TEST_EDGEUSE(teuY);
4073 
4074  if (!v) {
4075  /* If "v" parameter was NULL and this is the first time
4076  * through, take note of "v" where "e" was just split at.
4077  */
4078  v = teuY->vu_p->v_p;
4079  NMG_CK_VERTEX(v);
4080  }
4081 
4082  if (teuY->e_p == e || teuX->e_p == e) notdone = 0;
4083 
4084  /* Are the two edgeuses going in same or opposite directions?
4085  * Join the newly created temporary edge (teuX, teuY) with the
4086  * new permanent edge (neu1, neu2). On first pass, just take
4087  * note of the new edge & edgeuses.
4088  */
4089  NMG_CK_VERTEX(teuX->vu_p->v_p);
4090  if (teuX->vu_p->v_p == vA) {
4091  if (neu1) {
4092  nmg_je(neu1, teuX);
4093  nmg_je(neu2, teuY);
4094  }
4095  neu1 = teuX->eumate_p;
4096  neu2 = teuY->eumate_p;
4097  } else if (teuX->vu_p->v_p == vB) {
4098  if (neu1) {
4099  nmg_je(neu2, teuX);
4100  nmg_je(neu1, teuY);
4101  }
4102  neu2 = teuX->eumate_p;
4103  neu1 = teuY->eumate_p;
4104  } else {
4105  bu_log("nmg_esplit(v=%p, e=%p)\n", (void *)v, (void *)e);
4106  bu_log("nmg_esplit: teuX->vu_p->v_p=%p, vA=%p, vB=%p\n",
4107  (void *)teuX->vu_p->v_p, (void *)vA, (void *)vB);
4108  bu_bomb("nmg_esplit() teuX->vu_p->v_p is neither vA nor vB\n");
4109  }
4110  } while (notdone);
4111  /* Here, "e" pointer is invalid -- it no longer exists */
4112 
4113  /* Find an edgeuse that runs from v to vB */
4114  if (neu2->vu_p->v_p == v && neu2->eumate_p->vu_p->v_p == vB) {
4115  if (RTG.NMG_debug & DEBUG_BASIC) {
4116  bu_log("nmg_esplit(v=%p, eu=%p, share=%d) neu2=%p\n",
4117  (void *)v, (void *)eu, share_geom, (void *)neu2);
4118  }
4119  return neu2;
4120  } else if (neu1->vu_p->v_p == v && neu1->eumate_p->vu_p->v_p == vB) {
4121  if (RTG.NMG_debug & DEBUG_BASIC) {
4122  bu_log("nmg_esplit(v=%p, eu=%p, share=%d) neu1=%p\n",
4123  (void *)v, (void *)eu, share_geom, (void *)neu1);
4124  }
4125  return neu1;
4126  }
4127 
4128  bu_bomb("nmg_esplit() unable to find eu starting at new v\n");
4129  /* NOTREACHED */
4130  return (struct edgeuse *)NULL;
4131 }
4132 
4133 
4134 /**
4135  * Like nmg_esplit(), split an edge into two parts. Ensure that both
4136  * sets of edgeuses share the original edgeuse geometry. If the
4137  * original edge had no edge geometry, then none is created here.
4138  *
4139  * This is a simple compatibility interface to nmg_esplit(). The
4140  * return is the return of nmg_esplit().
4141  */
4142 struct edgeuse *
4143 nmg_ebreak(struct vertex *v, struct edgeuse *eu)
4144 /* May be NULL */
4145 
4146 {
4147  struct edgeuse *new_eu;
4148 
4149  NMG_CK_EDGEUSE(eu);
4150  if (eu->g.magic_p) {
4151  NMG_CK_EDGE_G_LSEG(eu->g.lseg_p);
4152  }
4153 
4154  new_eu = nmg_esplit(v, eu, 1); /* Do the hard work */
4155  NMG_CK_EDGEUSE(eu);
4156  NMG_CK_EDGEUSE(new_eu);
4157 
4158  if (eu->e_p == new_eu->e_p) bu_bomb("nmb_ebreak() same edges?\n");
4159 
4160  if (RTG.NMG_debug & DEBUG_BASIC) {
4161  bu_log("nmg_ebreak(v=%p, eu=%p) new_eu=%p\n",
4162  (void *)v, (void *)eu, (void *)new_eu);
4163  }
4164  return new_eu;
4165 }
4166 
4167 
4168 /*
4169  * Like nmg_ebreak(), but with edge radial sorting when sharing
4170  * occurs.
4171  *
4172  * Use nmg_ebreak() to break an existing edge on a vertex, preserving
4173  * edge geometry on both new edges. If the edge was broken on an
4174  * existing vertex, search both old and new edgeuses to see if they
4175  * need to be joined with an existing edgeuse that shared the same
4176  * vertices.
4177  */
4178 struct edgeuse *
4179 nmg_ebreaker(struct vertex *v, struct edgeuse *eu, const struct bn_tol *tol)
4180 /* May be NULL */
4181 
4182 
4183 {
4184  struct edgeuse *new_eu;
4185  struct edgeuse *oeu;
4186 
4187  NMG_CK_EDGEUSE(eu);
4188  BN_CK_TOL(tol);
4189 
4190  new_eu = nmg_ebreak(v, eu);
4191  if (v) {
4192  /*
4193  * This edge was broken on an existing vertex. Search the
4194  * whole model for other existing edges that match the newly
4195  * created edge fragments.
4196  */
4197  for (;;) {
4198  oeu = nmg_find_e(eu->vu_p->v_p,
4199  eu->eumate_p->vu_p->v_p,
4200  (struct shell *)NULL, eu->e_p);
4201  if (!oeu) break;
4202  if (RTG.NMG_debug & DEBUG_BASIC) {
4203  bu_log("nmg_ebreaker() joining eu=%p to oeu=%p\n",
4204  (void *)eu, (void *)oeu);
4205  }
4206  nmg_radial_join_eu(eu, oeu, tol);
4207  }
4208 
4209  for (;;) {
4210  oeu = nmg_find_e(new_eu->vu_p->v_p,
4211  new_eu->eumate_p->vu_p->v_p,
4212  (struct shell *)NULL, new_eu->e_p);
4213  if (!oeu) break;
4214  if (RTG.NMG_debug & DEBUG_BASIC) {
4215  bu_log("nmg_ebreaker() joining new_eu=%p to oeu=%p\n",
4216  (void *)new_eu, (void *)oeu);
4217  }
4218  nmg_radial_join_eu(new_eu, oeu, tol);
4219  }
4220 
4221  if (nmg_check_radial(eu, tol))
4222  bu_log("ERROR ebreaker eu=%p bad\n", (void *)eu);
4223  if (nmg_check_radial(new_eu, tol))
4224  bu_log("ERROR ebreaker new_eu=%p bad\n", (void *)new_eu);
4225  }
4226  if (RTG.NMG_debug & DEBUG_BASIC) {
4227  bu_log("nmg_ebreaker(v=%p, eu=%p) new_eu=%p\n", (void *)v, (void *)eu, (void *)new_eu);
4228  }
4229  return new_eu;
4230 }
4231 
4232 
4233 /**
4234  * Given two edges that are known to intersect someplace other than at
4235  * any of their endpoints, break both of them and insert a shared
4236  * vertex. Return a pointer to the new vertex.
4237  */
4238 struct vertex *
4239 nmg_e2break(struct edgeuse *eu1, struct edgeuse *eu2)
4240 {
4241  struct vertex *v;
4242  struct edgeuse *new_eu;
4243 
4244  NMG_CK_EDGEUSE(eu1);
4245  NMG_CK_EDGEUSE(eu2);
4246 
4247  new_eu = nmg_ebreak(NULL, eu1);
4248  v = new_eu->vu_p->v_p;
4249  NMG_CK_VERTEX(v);
4250  (void)nmg_ebreak(v, eu2);
4251 
4252  if (RTG.NMG_debug & DEBUG_BASIC) {
4253  bu_log("nmg_e2break(eu1=%p, eu2=%p) v=%p\n", (void *)eu1, (void *)eu2, (void *)v);
4254  }
4255  return v;
4256 }
4257 
4258 
4259 /**
4260  * Undoes the effect of an unwanted nmg_ebreak().
4261  *
4262  * Eliminate the vertex between this edgeuse and the next edge, on all
4263  * edgeuses radial to this edgeuse's edge. The edge geometry must be
4264  * shared, and all uses of the vertex to be disposed of must originate
4265  * from this edge pair. Also, the "non-B" ends of all edgeuses around
4266  * e1 and e2 must terminate at either A or B.
4267  *
4268  * XXX for t-NURBS, this should probably be re-stated as saying that
4269  * all the edgeuses must share the same 2 edges, and that every eu1
4270  * needs to share geom with its corresponding eu2, and similarly for
4271  * the two mates.
4272  *
4273  * eu1 eu2
4274  * *----------->*----------->*
4275  * A.....e1.....B.....e2.....C
4276  * *<-----------*<-----------*
4277  * eu1mate eu2mate
4278  *
4279  * If successful, the vertex B, the edge e2, and all the edgeuses
4280  * radial to eu2 (including eu2) will have all been killed. The
4281  * radial ordering around e1 will not change.
4282  *
4283  * eu1
4284  * *------------------------>*
4285  * A.....e1..................C
4286  * *<------------------------*
4287  * eu1mate
4288  *
4289  *
4290  * No new topology structures are created by this operation.
4291  *
4292  * Returns -
4293  * 0 OK, edge unbroken
4294  * <0 failure, nothing changed
4295  */
4296 int
4297 nmg_unbreak_edge(struct edgeuse *eu1_first)
4298 {
4299  struct edgeuse *eu1;
4300  struct edgeuse *eu2;
4301  struct edgeuse *teu;
4302  struct edge *e1;
4303  struct edge_g_lseg *eg;
4304  struct vertexuse *vu;
4305  struct vertex *vb = 0;
4306  struct vertex *vc;
4307  struct vertex *va;
4308  struct shell *s1;
4309  int ret = 0;
4310 
4311  NMG_CK_EDGEUSE(eu1_first);
4312  e1 = eu1_first->e_p;
4313  NMG_CK_EDGE(e1);
4314 
4315  if (eu1_first->g.magic_p != eu1_first->eumate_p->g.magic_p)
4316  bu_bomb("nmg_unbreak_edge() eu and mate don't share geometry\n");
4317 
4318  eg = eu1_first->g.lseg_p;
4319  if (!eg) {
4320  bu_log("nmg_unbreak_edge: no geometry for edge1 %p\n", (void *)e1);
4321  ret = -1;
4322  goto out;
4323  }
4324  NMG_CK_EDGE_G_LSEG(eg);
4325 
4326  /* If the edge geometry doesn't have at least four edgeuses, this
4327  * is not a candidate for unbreaking */
4328  if (bu_list_len(&eg->eu_hd2) < 2*2) {
4329  ret = -2;
4330  goto out;
4331  }
4332 
4333  s1 = nmg_find_s_of_eu(eu1_first);
4334  NMG_CK_SHELL(s1);
4335 
4336  eu1 = eu1_first;
4337  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, eu1);
4338  if (eu2->g.lseg_p != eg) {
4339  bu_log("nmg_unbreak_edge: second eu geometry %p does not match geometry %p of edge1 %p\n" ,
4340  (void *)eu2->g.magic_p, (void *)eg, (void *)e1);
4341  ret = -3;
4342  goto out;
4343  }
4344 
4345  va = eu1->vu_p->v_p; /* start vertex (A) */
4346  vb = eu2->vu_p->v_p; /* middle vertex (B) */
4347  vc = eu2->eumate_p->vu_p->v_p; /* end vertex (C) */
4348 
4349  /* all uses of this vertex must be for this edge geometry,
4350  * otherwise it is not a candidate for deletion */
4351  for (BU_LIST_FOR(vu, vertexuse, &vb->vu_hd)) {
4352  NMG_CK_VERTEXUSE(vu);
4353  if (*(vu->up.magic_p) != NMG_EDGEUSE_MAGIC) {
4354  /* vertex is referred to by a self-loop */
4355  if (vu->up.lu_p->orientation == OT_BOOLPLACE) {
4356  /* This kind is transient, and safe to ignore */
4357  continue;
4358  }
4359  ret = -4;
4360  goto out;
4361  }
4362  NMG_CK_EDGEUSE(vu->up.eu_p);
4363  if (vu->up.eu_p->g.lseg_p != eg) {
4364  ret = -5;
4365  goto out;
4366  }
4367  }
4368 
4369  /* Visit all edgeuse pairs radial to eu1 (A--B) */
4370  teu = eu1;
4371  for (;;) {
4372  register struct edgeuse *teu2;
4373  NMG_CK_EDGEUSE(teu);
4374  if (teu->vu_p->v_p != va || teu->eumate_p->vu_p->v_p != vb) {
4375  ret = -6;
4376  goto out;
4377  }
4378  /* We *may* encounter a teu2 not around eu2. Seen in BigWedge */
4379  teu2 = BU_LIST_PNEXT_CIRC(edgeuse, teu);
4380  NMG_CK_EDGEUSE(teu2);
4381  if (teu2->vu_p->v_p != vb || teu2->eumate_p->vu_p->v_p != vc) {
4382  ret = -7;
4383  goto out;
4384  }
4385  teu = teu->eumate_p->radial_p;
4386  if (teu == eu1) break;
4387  }
4388 
4389  /* Visit all edgeuse pairs radial to eu2 (B--C) */
4390  teu = eu2;
4391  for (;;) {
4392  NMG_CK_EDGEUSE(teu);
4393  if (teu->vu_p->v_p != vb || teu->eumate_p->vu_p->v_p != vc) {
4394  ret = -8;
4395  goto out;
4396  }
4397  teu = teu->eumate_p->radial_p;
4398  if (teu == eu2) break;
4399  }
4400 
4401  /* All preconditions are met, begin the unbreak operation */
4402  if (RTG.NMG_debug & DEBUG_BASIC) {
4403  bu_log("nmg_unbreak_edge va=%p, vb=%p, vc=%p\n",
4404  (void *)va, (void *)vb, (void *)vc);
4405  bu_log("nmg_unbreak_edge A:(%g, %g, %g), B:(%g, %g, %g), C:(%g, %g, %g)\n",
4406  V3ARGS(va->vg_p->coord),
4407  V3ARGS(vb->vg_p->coord),
4408  V3ARGS(vc->vg_p->coord));
4409  }
4410 
4411  if (va == vc) {
4412  /* bu_log("nmg_unbreak_edge(eu=%p): Trying to break a jaunt, va==vc (%p)\n", (void *)eu1_first, (void *)va); */
4413  ret = -9;
4414  goto out;
4415  }
4416 
4417 
4418  /* visit all the edgeuse pairs radial to eu1 */
4419  for (;;) {
4420  /* Recheck initial conditions */
4421  if (eu1->vu_p->v_p != va || eu1->eumate_p->vu_p->v_p != vb) {
4422  bu_log("nmg_unbreak_edge: eu1 does not got to/from correct vertices, %p, %p\n",
4423  (void *)eu1->vu_p->v_p, (void *)eu1->eumate_p->vu_p->v_p);
4424  nmg_pr_eu_briefly(eu1, " ");
4425  bu_bomb("nmg_unbreak_edge 1\n");
4426  }
4427  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, eu1);
4428  NMG_CK_EDGEUSE(eu2);
4429  if (eu2->g.lseg_p != eg) {
4430  bu_bomb("nmg_unbreak_edge: eu2 geometry is wrong\n");
4431  }
4432  if (eu2->vu_p->v_p != vb || eu2->eumate_p->vu_p->v_p != vc) {
4433  bu_log("nmg_unbreak_edge: about to kill eu2, but does not got to/from correct vertices, %p, %p\n",
4434  (void *)eu2->vu_p->v_p, (void *)eu2->eumate_p->vu_p->v_p);
4435  nmg_pr_eu_briefly(eu2, " ");
4436  bu_bomb("nmg_unbreak_edge 3\n");
4437  }
4438 
4439  /* revector eu1mate's start vertex from B to C */
4440  nmg_movevu(eu1->eumate_p->vu_p, vc);
4441 
4442  if (eu1->vu_p->v_p != va || eu1->eumate_p->vu_p->v_p != vc) {
4443  bu_log("nmg_unbreak_edge: extended eu1 does not got to/from correct vertices, %p, %p\n",
4444  (void *)eu1->vu_p->v_p, (void *)eu1->eumate_p->vu_p->v_p);
4445  nmg_pr_eu_briefly(eu1, " ");
4446  bu_bomb("nmg_unbreak_edge 2\n");
4447  }
4448 
4449  if (eu2 != BU_LIST_PNEXT_CIRC(edgeuse, eu1))
4450  bu_bomb("nmg_unbreak_edge eu2 unexpected altered\n");
4451 
4452  /* Now kill off the unnecessary eu2 associated w/ cur eu1 */
4453  if (nmg_keu(eu2))
4454  bu_bomb("nmg_unbreak_edge: edgeuse parent is now empty!!\n");
4455 
4456  if (eu1->vu_p->v_p != va || eu1->eumate_p->vu_p->v_p != vc) {
4457  bu_log("nmg_unbreak_edge: unbroken eu1 (after eu2 killed) does not got to/from correct vertices, %p, %p\n",
4458  (void *)eu1->vu_p->v_p, (void *)eu1->eumate_p->vu_p->v_p);
4459  nmg_pr_eu_briefly(eu1, " ");
4460  bu_bomb("nmg_unbreak_edge 4\n");
4461  }
4462  eu1 = eu1->eumate_p->radial_p;
4463  if (eu1 == eu1_first) break;
4464  }
4465 out:
4466  if (RTG.NMG_debug & DEBUG_BASIC) {
4467  bu_log("nmg_unbreak_edge(eu=%p, vb=%p) ret = %d\n",
4468  (void *)eu1_first, (void *)vb, ret);
4469  }
4470  return ret;
4471 }
4472 
4473 
4474 /**
4475  * Undoes the effect of an unwanted nmg_ebreak().
4476  *
4477  * NOTE: THIS IS LIKELY TO PRODUCE AN ILLEGAL NMG STRUCTURE!!!! This
4478  * routine is intended for use only when simplifying an NMG prior to
4479  * output in another format (such as polygons). It will unbreak edges
4480  * where nmg_unbreak_edge() will not!!!!!
4481  *
4482  * Eliminate the vertex between this edgeuse and the next edge, on all
4483  * edgeuses radial to this edgeuse's edge. The edge geometry must be
4484  * shared, and all uses of the vertex, in the same shell, to be
4485  * disposed of must originate from this edge pair. Also, the "non-B"
4486  * ends of all edgeuses around e1 and e2 (in this shell) must
4487  * terminate at either A or B.
4488  *
4489  *
4490  * eu1 eu2
4491  * *----------->*----------->*
4492  * A.....e1.....B.....e2.....C
4493  * *<-----------*<-----------*
4494  * eu1mate eu2mate
4495  *
4496  * If successful, the vertex B, the edge e2, and all the edgeuses in
4497  * the same shell radial to eu2 (including eu2) will have all been
4498  * killed. The radial ordering around e1 will not change.
4499  *
4500  * eu1
4501  * *------------------------>*
4502  * A.....e1..................C
4503  * *<------------------------*
4504  * eu1mate
4505  *
4506  *
4507  * No new topology structures are created by this operation.
4508  *
4509  * Returns -
4510  * 0 OK, edge unbroken
4511  * <0 failure, nothing changed
4512  */
4513 int
4514 nmg_unbreak_shell_edge_unsafe(struct edgeuse *eu1_first)
4515 {
4516  struct edgeuse *eu1;
4517  struct edgeuse *eu2;
4518  struct edgeuse *teu;
4519  struct edge *e1;
4520  struct edge_g_lseg *eg;
4521  struct vertexuse *vu;
4522  struct vertex *vb = 0;
4523  struct vertex *vc;
4524  struct vertex *va;
4525  struct shell *s1;
4526  int ret = 0;
4527 
4528  NMG_CK_EDGEUSE(eu1_first);
4529  e1 = eu1_first->e_p;
4530  NMG_CK_EDGE(e1);
4531 
4532  if (eu1_first->g.magic_p != eu1_first->eumate_p->g.magic_p) {
4533  ret = -10;
4534  goto out;
4535  }
4536 
4537  eg = eu1_first->g.lseg_p;
4538  if (!eg) {
4539  ret = -1;
4540  goto out;
4541  }
4542  NMG_CK_EDGE_G_LSEG(eg);
4543 
4544  s1 = nmg_find_s_of_eu(eu1_first);
4545  NMG_CK_SHELL(s1);
4546 
4547  eu1 = eu1_first;
4548  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, eu1);
4549  if (eu2->g.lseg_p != eg) {
4550  bu_log("nmg_unbreak_edge: second eu geometry %p does not match geometry %p of edge1 %p\n" ,
4551  (void *)eu2->g.magic_p, (void *)eg, (void *)e1);
4552  ret = -3;
4553  goto out;
4554  }
4555 
4556  va = eu1->vu_p->v_p; /* start vertex (A) */
4557  vb = eu2->vu_p->v_p; /* middle vertex (B) */
4558  vc = eu2->eumate_p->vu_p->v_p; /* end vertex (C) */
4559 
4560  /* all uses of this vertex (in shell s1) must be for this edge
4561  * geometry, otherwise it is not a candidate for deletion */
4562  for (BU_LIST_FOR(vu, vertexuse, &vb->vu_hd)) {
4563  NMG_CK_VERTEXUSE(vu);
4564  if (*(vu->up.magic_p) != NMG_EDGEUSE_MAGIC) {
4565  /* vertex is referred to by a self-loop */
4566  if (vu->up.lu_p->orientation == OT_BOOLPLACE) {
4567  /* This kind is transient, and safe to ignore */
4568  continue;
4569  }
4570  ret = -4;
4571  goto out;
4572  }
4573  if (nmg_find_s_of_vu(vu) != s1)
4574  continue;
4575  NMG_CK_EDGEUSE(vu->up.eu_p);
4576  if (vu->up.eu_p->g.lseg_p != eg) {
4577  ret = -5;
4578  goto out;
4579  }
4580  }
4581 
4582  /* Visit all edgeuse pairs radial to eu1 (A--B) */
4583  teu = eu1;
4584  for (;;) {
4585  register struct edgeuse *teu2;
4586  NMG_CK_EDGEUSE(teu);
4587  if (teu->vu_p->v_p != va || teu->eumate_p->vu_p->v_p != vb) {
4588  ret = -6;
4589  goto out;
4590  }
4591  /* We *may* encounter a teu2 not around eu2. Seen in BigWedge */
4592  teu2 = BU_LIST_PNEXT_CIRC(edgeuse, teu);
4593  NMG_CK_EDGEUSE(teu2);
4594  if (teu2->vu_p->v_p != vb || teu2->eumate_p->vu_p->v_p != vc) {
4595  ret = -7;
4596  goto out;
4597  }
4598  teu = teu->eumate_p->radial_p;
4599  if (teu == eu1) break;
4600  }
4601 
4602  /* Visit all edgeuse pairs radial to eu2 (B--C) */
4603  teu = eu2;
4604  for (;;) {
4605  NMG_CK_EDGEUSE(teu);
4606  if (teu->vu_p->v_p != vb || teu->eumate_p->vu_p->v_p != vc) {
4607  ret = -8;
4608  goto out;
4609  }
4610  teu = teu->eumate_p->radial_p;
4611  if (teu == eu2) break;
4612  }
4613 
4614  /* All preconditions are met, begin the unbreak operation */
4615  if (RTG.NMG_debug & DEBUG_BASIC) {
4616  bu_log("nmg_unbreak_edge va=%p, vb=%p, vc=%p\n",
4617  (void *)va, (void *)vb, (void *)vc);
4618  bu_log("nmg_unbreak_edge A:(%g, %g, %g), B:(%g, %g, %g), C:(%g, %g, %g)\n",
4619  V3ARGS(va->vg_p->coord),
4620  V3ARGS(vb->vg_p->coord),
4621  V3ARGS(vc->vg_p->coord));
4622  }
4623 
4624  if (va == vc) {
4625  /* bu_log("nmg_unbreak_edge(eu=%p): Trying to break a jaunt, va==vc (%p)\n", (void *)eu1_first, (void *)va); */
4626  ret = -9;
4627  goto out;
4628  }
4629 
4630 
4631  /* visit all the edgeuse pairs radial to eu1 */
4632  for (;;) {
4633  /* Recheck initial conditions */
4634  if (eu1->vu_p->v_p != va || eu1->eumate_p->vu_p->v_p != vb) {
4635  bu_log("nmg_unbreak_edge: eu1 does not got to/from correct vertices, %p, %p\n",
4636  (void *)eu1->vu_p->v_p, (void *)eu1->eumate_p->vu_p->v_p);
4637  nmg_pr_eu_briefly(eu1, " ");
4638  bu_bomb("nmg_unbreak_edge 1\n");
4639  }
4640  eu2 = BU_LIST_PNEXT_CIRC(edgeuse, eu1);
4641  NMG_CK_EDGEUSE(eu2);
4642  if (eu2->g.lseg_p != eg) {
4643  bu_bomb("nmg_unbreak_edge: eu2 geometry is wrong\n");
4644  }
4645  if (eu2->vu_p->v_p != vb || eu2->eumate_p->vu_p->v_p != vc) {
4646  bu_log("nmg_unbreak_edge: about to kill eu2, but does not got to/from correct vertices, %p, %p\n",
4647  (void *)eu2->vu_p->v_p, (void *)eu2->eumate_p->vu_p->v_p);
4648  nmg_pr_eu_briefly(eu2, " ");
4649  bu_bomb("nmg_unbreak_edge 3\n");
4650  }
4651 
4652  /* revector eu1mate's start vertex from B to C */
4653  nmg_movevu(eu1->eumate_p->vu_p, vc);
4654 
4655  if (eu1->vu_p->v_p != va || eu1->eumate_p->vu_p->v_p != vc) {
4656  bu_log("nmg_unbreak_edge: extended eu1 does not got to/from correct vertices, %p, %p\n",
4657  (void *)eu1->vu_p->v_p, (void *)eu1->eumate_p->vu_p->v_p);
4658  nmg_pr_eu_briefly(eu1, " ");
4659  bu_bomb("nmg_unbreak_edge 2\n");
4660  }
4661 
4662  if (eu2 != BU_LIST_PNEXT_CIRC(edgeuse, eu1))
4663  bu_bomb("nmg_unbreak_edge eu2 unexpected altered\n");
4664 
4665  /* Now kill off the unnecessary eu2 associated w/ cur eu1 */
4666  if (nmg_keu(eu2))
4667  bu_bomb("nmg_unbreak_edge: edgeuse parent is now empty!!\n");
4668 
4669  if (eu1->vu_p->v_p != va || eu1->eumate_p->vu_p->v_p != vc) {
4670  bu_log("nmg_unbreak_edge: unbroken eu1 (after eu2 killed) does not got to/from correct vertices, %p, %p\n",
4671  (void *)eu1->vu_p->v_p, (void *)eu1->eumate_p->vu_p->v_p);
4672  nmg_pr_eu_briefly(eu1, " ");
4673  bu_bomb("nmg_unbreak_edge 4\n");
4674  }
4675  eu1 = eu1->eumate_p->radial_p;
4676  if (eu1 == eu1_first) break;
4677  }
4678 out:
4679  if (RTG.NMG_debug & DEBUG_BASIC) {
4680  bu_log("nmg_unbreak_edge(eu=%p, vb=%p) ret = %d\n",
4681  (void *)eu1_first, (void *)vb, ret);
4682  }
4683  return ret;
4684 }
4685 
4686 
4687 /**
4688  * Insert a new (zero length) edge at the beginning of (i.e., before) an
4689  * existing edgeuse. Perhaps this is what nmg_esplit and nmg_eusplit
4690  * should have been like?
4691  *
4692  * Before:
4693  * .--A--> .--eu-->
4694  * \
4695  * >.
4696  * /
4697  * <-A'--. <-eu'-.
4698  *
4699  *
4700  * After:
4701  *
4702  * eu1 eu
4703  * .--A--> .---> .--eu-->
4704  * \ /
4705  * >.<
4706  * / \
4707  * <-A'--. <---. <-eu'--.
4708  * eu2 eumate
4709  */
4710 struct edgeuse *
4711 nmg_eins(struct edgeuse *eu)
4712 {
4713  struct edgeuse *eumate;
4714  struct edgeuse *eu1, *eu2;
4715  struct shell *s;
4716 
4717  NMG_CK_EDGEUSE(eu);
4718  eumate = eu->eumate_p;
4719  NMG_CK_EDGEUSE(eumate);
4720 
4721  if (*eu->up.magic_p == NMG_SHELL_MAGIC) {
4722  s = eu->up.s_p;
4723  NMG_CK_SHELL(s);
4724  } else {
4725  struct loopuse *lu;
4726 
4727  lu = eu->up.lu_p;
4728  NMG_CK_LOOPUSE(lu);
4729  if (*lu->up.magic_p == NMG_SHELL_MAGIC) {
4730  s = lu->up.s_p;
4731  NMG_CK_SHELL(s);
4732  } else {
4733  struct faceuse *fu;
4734  fu = lu->up.fu_p;
4735  NMG_CK_FACEUSE(fu);
4736  s = fu->s_p;
4737  NMG_CK_SHELL(s);
4738  }
4739  }
4740 
4741  eu1 = nmg_me(eu->vu_p->v_p, eu->vu_p->v_p, s);
4742  eu2 = eu1->eumate_p;
4743 
4744  if (*eu->up.magic_p == NMG_LOOPUSE_MAGIC) {
4745  BU_LIST_DEQUEUE(&eu1->l);
4746  BU_LIST_DEQUEUE(&eu2->l);
4747 
4748  BU_LIST_INSERT(&eu->l, &eu1->l);
4749  BU_LIST_APPEND(&eumate->l, &eu2->l);
4750 
4751  eu1->up.lu_p = eu->up.lu_p;
4752  eu2->up.lu_p = eumate->up.lu_p;
4753  } else {
4754  bu_bomb("nmg_eins() Cannot yet insert null edge in shell\n");
4755  }
4756  if (RTG.NMG_debug & DEBUG_BASIC) {
4757  bu_log("nmg_eins(eu=%p) eu1=%p\n", (void *)eu, (void *)eu1);
4758  }
4759  return eu1;
4760 }
4761 
4762 
4763 /**
4764  * Move a wire edgeuse and its mate from one shell to another.
4765  */
4766 void
4767 nmg_mv_eu_between_shells(struct shell *dest, register struct shell *src, register struct edgeuse *eu)
4768 {
4769  register struct edgeuse *eumate;
4770 
4771  NMG_CK_EDGEUSE(eu);
4772  eumate = eu->eumate_p;
4773  NMG_CK_EDGEUSE(eumate);
4774 
4775  if (eu->up.s_p != src) {
4776  bu_log("nmg_mv_eu_between_shells(dest=%p, src=%p, eu=%p), eu->up.s_p=%p isn't src shell\n",
4777  (void *)dest, (void *)src, (void *)eu, (void *)eu->up.s_p);
4778  bu_bomb("eu->up.s_p isn't source shell\n");
4779  }
4780  if (eumate->up.s_p != src) {
4781  bu_log("nmg_mv_eu_between_shells(dest=%p, src=%p, eu=%p), eumate->up.s_p=%p isn't src shell\n",
4782  (void *)dest, (void *)src, (void *)eu, (void *)eumate->up.s_p);
4783  bu_bomb("eumate->up.s_p isn't source shell\n");
4784  }
4785 
4786  /* Remove eu from src shell */
4787  BU_LIST_DEQUEUE(&eu->l);
4788  if (BU_LIST_IS_EMPTY(&src->eu_hd)) {
4789  /* This was the last eu in the list, bad news */
4790  bu_log("nmg_mv_eu_between_shells(dest=%p, src=%p, eu=%p), eumate=%p not in src shell\n",
4791  (void *)dest, (void *)src, (void *)eu, (void *)eumate);
4792  bu_bomb("src shell emptied before finding eumate\n");
4793  }
4794 
4795  /* Remove eumate from src shell */
4796  BU_LIST_DEQUEUE(&eumate->l);
4797 
4798  /* Add eu and eumate to dest shell */
4799  BU_LIST_APPEND(&dest->eu_hd, &eu->l);
4800  BU_LIST_APPEND(&eu->l, &eumate->l);
4801 
4802  eu->up.s_p = dest;
4803  eumate->up.s_p = dest;
4804 
4805  if (RTG.NMG_debug & DEBUG_BASIC) {
4806  bu_log("nmg_mv_eu_between_shells(dest=%p, src=%p, eu=%p) new_eu=%p\n",
4807  (void *)dest, (void *)src, (void *)eu, (void *)eumate);
4808  }
4809 }
4810 
4811 
4812 /************************************************************************
4813  * *
4814  * VERTEX Routines *
4815  * *
4816  ************************************************************************/
4817 
4818 
4819 /**
4820  * If this shell had a single vertexuse in it, move it to the other
4821  * shell, but "promote" it to a "loop of a single vertex" along the
4822  * way.
4823  */
4824 void
4825 nmg_mv_vu_between_shells(struct shell *dest, register struct shell *src, register struct vertexuse *vu)
4826 {
4827  NMG_CK_VERTEXUSE(vu);
4828  NMG_CK_VERTEX(vu->v_p);
4829 
4830  if (RTG.NMG_debug & DEBUG_BASIC) {
4831  bu_log("nmg_mv_vu_between_shells(dest_s=%p, src_s=%p, vu=%p)\n",
4832  (void *)dest, (void *)src, (void *)vu);
4833  }
4834  (void) nmg_mlv(&(dest->l.magic), vu->v_p, OT_SAME);
4835  if (vu->v_p->vg_p) {
4836  NMG_CK_VERTEX_G(vu->v_p->vg_p);
4837  }
4838  nmg_kvu(vu);
4839 }
4840 
4841 
4842 /*
4843  * Local Variables:
4844  * mode: C
4845  * tab-width: 8
4846  * indent-tabs-mode: t
4847  * c-file-style: "stroustrup"
4848  * End:
4849  * ex: shiftwidth=4 tabstop=8
4850  */
#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_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
int nmg_edge_fuse(const uint32_t *magic_p, const struct bn_tol *tol)
Definition: nmg_fuse.c:1062
struct faceuse * nmg_cface(struct shell *s, struct vertex **verts, int n)
Definition: nmg_mod.c:1130
void nmg_stash_model_to_file(const char *filename, const struct model *m, const char *title)
Definition: nmg_misc.c:4500
else if oldeu
Definition: nmg_mod.c:3847
int nmg_fu_planeeqn(struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_mod.c:1311
void nmg_radial_join_eu(struct edgeuse *eu1, struct edgeuse *eu2, const struct bn_tol *tol)
Definition: nmg_mesh.c:197
#define BU_LIST_LAST(structure, hp)
Definition: list.h:306
void nmg_kill_accordions(struct loopuse *lu)
Definition: nmg_mod.c:2934
int nmg_kfu(struct faceuse *fu1)
Definition: nmg_mk.c:1207
#define NMG_SHELL_MAGIC
Definition: magic.h:142
void nmg_reverse_face(register struct faceuse *fu)
Definition: nmg_mod.c:1511
struct vertexuse * nmg_join_singvu_loop(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2137
int nmg_is_vertex_in_looplist(register const struct vertex *v, const struct bu_list *hd, int singletons)
Definition: nmg_info.c:1754
double dist
>= 0
Definition: tol.h:73
void nmg_set_lu_orientation(struct loopuse *lu, int is_opposite)
Definition: nmg_mod.c:3620
#define NMG_FACE_G_SNURB_MAGIC
Definition: magic.h:126
void nmg_je(struct edgeuse *eudst, struct edgeuse *eusrc)
Definition: nmg_mk.c:2765
if lu s
Definition: nmg_mod.c:3860
Definition: clone.c:90
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
int nmg_join_touchingloops(struct loopuse *lu)
Definition: nmg_mod.c:2678
lu
Definition: nmg_mod.c:3855
int nmg_kr(struct nmgregion *r)
Definition: nmg_mk.c:1595
#define BU_LIST_IS_EMPTY(hp)
Definition: list.h:295
void nmg_s_radial_harmonize(struct shell *s, const struct bn_tol *tol)
Definition: nmg_fuse.c:3375
void nmg_vertex_gv(struct vertex *v, const fastf_t *pt)
Definition: nmg_mk.c:1668
struct faceuse * nmg_mf(struct loopuse *lu1)
Definition: nmg_mk.c:470
#define SMALL_FASTF
Definition: defines.h:342
void nmg_face_g(struct faceuse *fu, const fastf_t *p)
Definition: nmg_mk.c:2235
nmg_movevu(eu2->vu_p, eu1->vu_p->v_p)
void nmg_mv_fu_between_shells(struct shell *dest, register struct shell *src, register struct faceuse *fu)
Definition: nmg_mod.c:1702
void nmg_rebound(struct model *m, const struct bn_tol *tol)
Definition: nmg_misc.c:2072
Header file for the BRL-CAD common definitions.
#define BU_CK_PTBL(_p)
Definition: ptbl.h:74
struct faceuse * nmg_dup_face(struct faceuse *fu, struct shell *s)
Definition: nmg_mod.c:1827
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
void nmg_unglueedge(struct edgeuse *eu)
Definition: nmg_mk.c:2866
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
int nmg_shell_is_empty(register const struct shell *s)
Definition: nmg_info.c:203
void nmg_face_g_snurb(struct faceuse *fu, int u_order, int v_order, int n_u_knots, int n_v_knots, fastf_t *ukv, fastf_t *vkv, int n_rows, int n_cols, int pt_type, fastf_t *mesh)
Definition: nmg_mk.c:2347
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
struct loopuse * nmg_cut_loop(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2283
void nmg_s_join_touchingloops(struct shell *s, const struct bn_tol *tol)
Definition: nmg_mod.c:690
int nmg_kvu(struct vertexuse *vu)
Definition: nmg_mk.c:1095
void bu_ptbl_reset(struct bu_ptbl *b)
Definition: ptbl.c:49
#define NMG_LOOPUSE_MAGIC
Definition: magic.h:130
int nmg_is_edge_in_looplist(const struct edge *e, const struct bu_list *hd)
Definition: nmg_info.c:1885
#define JS_UNKNOWN
Definition: nmg_mod.c:2750
void nmg_pr_eu_briefly(const struct edgeuse *eu, char *h)
Definition: nmg_pr.c:586
void nmg_merge_regions(struct nmgregion *r1, struct nmgregion *r2, const struct bn_tol *tol)
Definition: nmg_mod.c:42
NMG_CK_LOOPUSE(lu)
struct f2 f2
void nmg_invert_shell(struct shell *s)
Definition: nmg_mod.c:890
BU_LIST_DEQUEUE & eu1
Definition: nmg_mod.c:3839
struct edgeuse * nmg_findeu(const struct vertex *v1, const struct vertex *v2, const struct shell *s, const struct edgeuse *eup, int dangling_only)
Definition: nmg_info.c:682
int nmg_check_radial(const struct edgeuse *eu, const struct bn_tol *tol)
Definition: nmg_ck.c:1210
Definition: ptbl.h:62
void nmg_edge_g(struct edgeuse *eu)
Definition: nmg_mk.c:1789
int nmg_ks(struct shell *s)
Definition: nmg_mk.c:1546
void nmg_split_touchingloops(struct loopuse *lu, const struct bn_tol *tol)
Definition: nmg_mod.c:2585
void nmg_sanitize_s_lv(struct shell *s, int orient)
Definition: nmg_mod.c:564
#define NMG_EDGEUSE2_MAGIC
Definition: magic.h:119
void nmg_pl_fu(FILE *fp, const struct faceuse *fu, long *b, int red, int green, int blue)
Definition: nmg_plot.c:722
#define BU_LIST_PLAST(structure, p)
Definition: list.h:424
struct loopuse * nmg_split_lu_at_vu(struct loopuse *lu, struct vertexuse *split_vu)
Definition: nmg_mod.c:2457
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
void nmg_shell_coplanar_face_merge(struct shell *s, const struct bn_tol *tol, const int simplify)
Definition: nmg_mod.c:93
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
#define BU_PTBL_GET(ptbl, i)
Definition: ptbl.h:108
void nmg_jl(struct loopuse *lu, struct edgeuse *eu)
Definition: nmg_mod.c:1945
#define V3ARGS(a)
Definition: color.c:56
struct vertexuse * nmg_join_2singvu_loops(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2186
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
struct loopuse * nmg_mlv(uint32_t *magic, struct vertex *v, int orientation)
Definition: nmg_mk.c:571
void nmg_pr_lu_briefly(const struct loopuse *lu, char *h)
Definition: nmg_pr.c:455
static void top()
struct f1 f1
int nmg_is_loop_in_facelist(const struct loop *l, const struct bu_list *fu_hd)
Definition: nmg_info.c:1933
struct faceuse * nmg_add_loop_to_face(struct shell *s, struct faceuse *fu, struct vertex **verts, int n, int dir)
Definition: nmg_mod.c:1211
void nmg_s_split_touchingloops(struct shell *s, const struct bn_tol *tol)
Definition: nmg_mod.c:646
struct edgeuse * nmg_me(struct vertex *v1, struct vertex *v2, struct shell *s)
Definition: nmg_mk.c:698
#define BU_LIST_PNEXT(structure, p)
Definition: list.h:422
#define HPRINT(a, b)
Definition: raytrace.h:1882
struct edgeuse * nmg_find_e(const struct vertex *v1, const struct vertex *v2, const struct shell *s, const struct edge *ep)
Definition: nmg_info.c:882
goto out
Definition: nmg_mod.c:3846
Support for uniform tolerances.
Definition: tol.h:71
struct shell * nmg_find_s_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:235
#define BN_CK_TOL(_p)
Definition: tol.h:82
#define BU_LIST_FIRST_MAGIC(hp)
Definition: list.h:416
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
struct edgeuse * nmg_meonvu(struct vertexuse *vu)
Definition: nmg_mk.c:800
#define BU_LIST_WHILE(p, structure, hp)
Definition: list.h:410
void nmg_vshell(const struct bu_list *hp, const struct nmgregion *r)
Definition: nmg_ck.c:591
void nmg_ck_lueu(const struct loopuse *cklu, const char *s)
Definition: nmg_ck.c:1138
void nmg_rm_redundancies(struct shell *s, const struct bn_tol *tol)
Definition: nmg_mod.c:242
struct loopuse * nmg_dup_loop(struct loopuse *lu, uint32_t *parent, long int **trans_tbl)
Definition: nmg_mod.c:3459
#define NMG_FACE_G_PLANE_MAGIC
Definition: magic.h:125
void bu_ptbl_free(struct bu_ptbl *b)
Definition: ptbl.c:226
#define BU_LIST_PPREV_CIRC(structure, p)
Definition: list.h:450
int nmg_simplify_shell(struct shell *s)
Definition: nmg_mod.c:209
#define BU_LIST_INIT(_hp)
Definition: list.h:148
int nmg_klu(struct loopuse *lu1)
Definition: nmg_mk.c:1277
int nmg_ck_fu_verts(struct faceuse *fu1, struct face *f2, const struct bn_tol *tol)
Definition: nmg_fuse.c:1416
#define BU_PTBL_END(ptbl)
Definition: ptbl.h:106
int bn_3pts_collinear(point_t a, point_t b, point_t c, const struct bn_tol *tol)
Check to see if three points are collinear.
int nmg_face_fix_radial_parity(struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_mod.c:1593
int nmg_kill_snakes(struct loopuse *lu)
Definition: nmg_mod.c:3302
else nmg_use_edge_g(eu2, oldeu->g.magic_p)
struct faceuse * nmg_find_fu_with_fg_in_s(const struct shell *s1, const struct faceuse *fu2)
Definition: nmg_info.c:341
void nmg_simplify_loop(struct loopuse *lu)
Definition: nmg_mod.c:3230
void nmg_js(register struct shell *s1, register struct shell *s2, const struct bn_tol *tol)
Definition: nmg_mod.c:740
struct vertexuse * nmg_join_2loops(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2043
int bu_list_len(const struct bu_list *hd)
int nmg_is_vertex_in_facelist(register const struct vertex *v, const struct bu_list *hd)
Definition: nmg_info.c:1848
int nmg_simplify_face(struct faceuse *fu)
Definition: nmg_mod.c:1446
#define JS_SPLIT
Definition: nmg_mod.c:2751
struct shell * nmg_find_s_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:249
int nmg_keu(register struct edgeuse *eu1)
Definition: nmg_mk.c:1413
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define JS_TOUCHING_JAUNT
Definition: nmg_mod.c:2753
NMG_CK_SHELL(s)
void nmg_gluefaces(struct faceuse **fulist, int n, const struct bn_tol *tol)
Definition: nmg_mod.c:1408
struct faceuse * nmg_cmface(struct shell *s, struct vertex ***verts, int n)
Definition: nmg_mod.c:979
int nmg_eu_is_part_of_crack(const struct edgeuse *eu)
Definition: nmg_pt_fu.c:276
int nmg_loop_split_at_touching_jaunt(struct loopuse *lu, const struct bn_tol *tol)
Definition: nmg_mod.c:2997
void nmg_jf(register struct faceuse *dest_fu, register struct faceuse *src_fu)
Definition: nmg_mod.c:1791
int bn_pt3_pt3_equal(const point_t a, const point_t b, const struct bn_tol *tol)
nmg_keg(oldeumate)
void nmg_moveltof(struct faceuse *fu, struct shell *s)
Definition: nmg_mod.c:3424
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
#define BU_LIST_NEXT_IS_HEAD(p, hp)
Definition: list.h:338
void nmg_shell_a(struct shell *s, const struct bn_tol *tol)
Definition: nmg_mk.c:2474
#define NMG_FACEUSE_MAGIC
Definition: magic.h:124
struct loopuse * nmg_find_lu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:411
struct vertexuse * nmg_find_repeated_v_in_lu(struct vertexuse *vu)
Definition: nmg_mod.c:2533
BU_LIST_DEQUEUE & oldeumate
Definition: nmg_mod.c:3837
double fastf_t
Definition: defines.h:300
#define VPRINT(a, b)
Definition: raytrace.h:1881
eu2
Definition: nmg_mod.c:3875
int bn_mk_plane_3pts(plane_t plane, const point_t a, const point_t b, const point_t c, const struct bn_tol *tol)
void nmg_mv_lu_between_shells(struct shell *dest, register struct shell *src, register struct loopuse *lu)
Definition: nmg_mod.c:3373
char * nmg_orientation(int orientation)
Definition: nmg_pr.c:50
#define BU_LIST_NEXT(structure, hp)
Definition: list.h:316
#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
void nmg_pl_2fu(const char *str, const struct faceuse *fu1, const struct faceuse *fu2, int show_mates)
Definition: nmg_plot.c:1380
void nmg_loop_plane_newell(const struct loopuse *lu, fastf_t *pl)
Definition: nmg_misc.c:1250
int nmg_is_edge_in_facelist(const struct edge *e, const struct bu_list *hd)
Definition: nmg_info.c:1914
#define BU_LIST_PREV(structure, hp)
Definition: list.h:310
#define BU_LIST_PNEXT_PNEXT(structure, p)
Definition: list.h:430
bu_bomb("nmg_eusplit\n")
#define JS_JAUNT
Definition: nmg_mod.c:2752
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
int nmg_get_touching_jaunts(const struct loopuse *lu, struct bu_ptbl *tbl, int *need_init)
Definition: nmg_mod.c:2771
int nmg_is_vertex_in_edgelist(register const struct vertex *v, const struct bu_list *hd)
Definition: nmg_info.c:1735
struct rt_g RTG
Definition: globals.c:39
struct model * nmg_find_model(const uint32_t *magic_p_arg)
Definition: nmg_info.c:57