BRL-CAD
nmg_fuse.c
Go to the documentation of this file.
1 /* N M G _ F U S E . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1993-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_fuse.c
23  *
24  * Routines to "fuse" entities together that are geometrically
25  * identical (within tolerance) into entities that share underlying
26  * geometry structures, so that the relationship is explicit.
27  *
28  */
29 /** @} */
30 
31 #include "common.h"
32 
33 #include <stddef.h>
34 #include <string.h>
35 #include <math.h>
36 #include "bio.h"
37 
38 #include "bu/sort.h"
39 #include "vmath.h"
40 #include "nmg.h"
41 #include "raytrace.h"
42 #include "nurb.h"
43 
44 
45 extern int debug_file_count;
46 
47 struct pt_list
48 {
49  struct bu_list l;
50  point_t xyz;
52 };
53 
54 
55 extern void nmg_split_trim(const struct edge_g_cnurb *cnrb,
56  const struct face_g_snurb *snrb,
57  fastf_t t,
58  struct pt_list *pt0, struct pt_list *pt1,
59  const struct bn_tol *tol);
60 
61 /**
62  * Do two faces share by topology at least one loop of 3 or more vertices?
63  *
64  * Require that at least three distinct edge geometries be involved.
65  *
66  * XXX Won't catch sharing of faces with only self-loops and no edge loops.
67  */
68 int
69 nmg_is_common_bigloop(const struct face *f1, const struct face *f2)
70 {
71  const struct faceuse *fu1;
72  const struct loopuse *lu1;
73  const struct edgeuse *eu1;
74  const uint32_t *magic1 = NULL;
75  const uint32_t *magic2 = NULL;
76  int nverts;
77  int nbadv;
78  int got_three;
79 
80  NMG_CK_FACE(f1);
81  NMG_CK_FACE(f2);
82 
83  fu1 = f1->fu_p;
84  NMG_CK_FACEUSE(fu1);
85 
86  /* For all loopuses in fu1 */
87  for (BU_LIST_FOR(lu1, loopuse, &fu1->lu_hd)) {
88  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) == NMG_VERTEXUSE_MAGIC)
89  continue;
90  nverts = 0;
91  nbadv = 0;
92  magic1 = NULL;
93  magic2 = NULL;
94  got_three = 0;
95  for (BU_LIST_FOR(eu1, edgeuse, &lu1->down_hd)) {
96  nverts++;
97  NMG_CK_EDGE_G_LSEG(eu1->g.lseg_p);
98  if (!magic1) {
99  magic1 = eu1->g.magic_p;
100  } else if (!magic2) {
101  if (eu1->g.magic_p != magic1) {
102  magic2 = eu1->g.magic_p;
103  }
104  } else {
105  if (eu1->g.magic_p != magic1 &&
106  eu1->g.magic_p != magic2) {
107  got_three = 1;
108  }
109  }
110  if (nmg_is_vertex_in_face(eu1->vu_p->v_p, f2))
111  continue;
112  nbadv++;
113  break;
114  }
115  if (nbadv <= 0 && nverts >= 3 && got_three) return 1;
116  }
117  return 0;
118 }
119 
120 
121 /**
122  * Ensure that all the vertices in r1 are still geometrically unique.
123  * This will be true after nmg_region_both_vfuse() has been called,
124  * and should remain true throughout the intersection process.
125  */
126 void
127 nmg_region_v_unique(struct nmgregion *r1, const struct bn_tol *tol)
128 {
129  int i;
130  int j;
131  struct bu_ptbl t;
132 
133  NMG_CK_REGION(r1);
134  BN_CK_TOL(tol);
135 
136  nmg_vertex_tabulate(&t, &r1->l.magic);
137 
138  for (i = BU_PTBL_END(&t)-1; i >= 0; i--) {
139  register struct vertex *vi;
140  vi = (struct vertex *)BU_PTBL_GET(&t, i);
141  NMG_CK_VERTEX(vi);
142  if (!vi->vg_p) continue;
143 
144  for (j = i-1; j >= 0; j--) {
145  register struct vertex *vj;
146  vj = (struct vertex *)BU_PTBL_GET(&t, j);
147  NMG_CK_VERTEX(vj);
148  if (!vj->vg_p) continue;
149  if (!bn_pt3_pt3_equal(vi->vg_p->coord, vj->vg_p->coord, tol))
150  continue;
151  /* They are the same */
152  bu_log("nmg_region_v_unique(): 2 verts are the same, within tolerance\n");
153  nmg_pr_v(vi, 0);
154  nmg_pr_v(vj, 0);
155  bu_bomb("nmg_region_v_unique()\n");
156  }
157  }
158  bu_ptbl_free(&t);
159 }
160 
161 
162 /* compare function for bu_sort within function nmg_ptbl_vfuse */
163 static int
164 x_comp(const void *p1, const void *p2, void *UNUSED(arg))
165 {
166  fastf_t i, j;
167 
168  i = (*((struct vertex **)p1))->vg_p->coord[X];
169  j = (*((struct vertex **)p2))->vg_p->coord[X];
170 
171  if (EQUAL(i, j))
172  return 0;
173  else if (i > j)
174  return 1;
175  return -1;
176 }
177 
178 
179 /**
180  * Working from the end to the front, scan for geometric duplications
181  * within a single list of vertex structures.
182  *
183  * Exists primarily as a support routine for nmg_vertex_fuse().
184  */
185 int
186 nmg_ptbl_vfuse(struct bu_ptbl *t, const struct bn_tol *tol)
187 {
188  int count, fuse;
189  register int i, j;
190  register fastf_t tmp = tol->dist_sq;
191  register fastf_t ab, abx, aby, abz;
192 
193  /* sort the vertices in the 't' list by the 'x' coordinate */
194  bu_sort(BU_PTBL_BASEADDR(t), BU_PTBL_LEN(t), sizeof(long *), x_comp, NULL);
195 
196  count = 0;
197  for (i = 0 ; i < BU_PTBL_END(t) ; i++) {
198  register struct vertex *vi;
199  vi = (struct vertex *)BU_PTBL_GET(t, i);
200  if (!vi) continue;
201  NMG_CK_VERTEX(vi);
202  if (!vi->vg_p) continue;
203 
204  for (j = i+1 ; j < BU_PTBL_END(t) ; j++) {
205  register struct vertex *vj;
206  vj = (struct vertex *)BU_PTBL_GET(t, j);
207  if (!vj) continue;
208  NMG_CK_VERTEX(vj);
209  if (!vj->vg_p) continue;
210 
211  if (vi->vg_p == vj->vg_p) {
212  /* They are the same, fuse vj into vi */
213  nmg_jv(vi, vj); /* vj gets destroyed */
214  BU_PTBL_SET(t, j, NULL);
215  count++;
216  continue;
217  }
218 
219  fuse = 1;
220  abx = vi->vg_p->coord[X] - vj->vg_p->coord[X];
221  ab = abx * abx;
222  if (ab > tmp) {
223  break; /* no more to test */
224  }
225 
226  aby = vi->vg_p->coord[Y] - vj->vg_p->coord[Y];
227  ab += (aby * aby);
228  if (ab > tmp) {
229  fuse = 0;
230  } else {
231  abz = vi->vg_p->coord[Z] - vj->vg_p->coord[Z];
232  ab += (abz * abz);
233  if (ab > tmp) {
234  fuse = 0;
235  }
236  }
237 
238  if (fuse) {
239  /* They are the same, fuse vj into vi */
240  nmg_jv(vi, vj); /* vj gets destroyed */
241  BU_PTBL_SET(t, j, NULL);
242  count++;
243  }
244  }
245  }
246 
247  return count;
248 }
249 
250 
251 /**
252  * For every element in t1, scan t2 for geometric duplications.
253  *
254  * Deleted elements in t2 are marked by a null vertex pointer,
255  * rather than bothering to do a BU_PTBL_RM, which will re-copy the
256  * list to compress it.
257  *
258  * Exists as a support routine for nmg_two_region_vertex_fuse()
259  */
260 int
261 nmg_region_both_vfuse(struct bu_ptbl *t1, struct bu_ptbl *t2, const struct bn_tol *tol)
262 {
263  int count = 0;
264  int i;
265  int j;
266 
267  /* Verify t2 is good to start with */
268  for (j = BU_PTBL_END(t2)-1; j >= 0; j--) {
269  register struct vertex *vj;
270  vj = (struct vertex *)BU_PTBL_GET(t2, j);
271  NMG_CK_VERTEX(vj);
272  }
273 
274  for (i = BU_PTBL_END(t1)-1; i >= 0; i--) {
275  register struct vertex *vi;
276  vi = (struct vertex *)BU_PTBL_GET(t1, i);
277  NMG_CK_VERTEX(vi);
278  if (!vi->vg_p) continue;
279 
280  for (j = BU_PTBL_END(t2)-1; j >= 0; j--) {
281  register struct vertex *vj;
282  vj = (struct vertex *)BU_PTBL_GET(t2, j);
283  if (!vj) continue;
284  NMG_CK_VERTEX(vj);
285  if (!vj->vg_p) continue;
286  if (!bn_pt3_pt3_equal(vi->vg_p->coord, vj->vg_p->coord, tol))
287  continue;
288  /* They are the same, fuse vj into vi */
289  nmg_jv(vi, vj);
290  BU_PTBL_GET(t2, j) = 0;
291  count++;
292  }
293  }
294  return count;
295 }
296 
297 
298 /**
299  * Fuse together any vertices that are geometrically identical, within
300  * distance tolerance. This function may be passed a pointer to an NMG
301  * object or a pointer to a bu_ptbl structure containing a list of
302  * pointers to NMG vertex structures. If a bu_ptbl structure was passed
303  * into this function, the calling function must free this structure.
304  */
305 int
306 nmg_vertex_fuse(const uint32_t *magic_p, const struct bn_tol *tol)
307 {
308  struct bu_ptbl *t1;
309  struct bu_ptbl tmp;
310  size_t t1_len;
311  int total = 0;
312  const uint32_t *tmp_magic_p;
313 
314  BN_CK_TOL(tol);
315 
316  if (!magic_p) {
317  bu_bomb("nmg_vertex_fuse(): passed null pointer");
318  }
319 
320  if (*magic_p == BU_PTBL_MAGIC) {
321  t1 = (struct bu_ptbl *)magic_p;
322  t1_len = BU_PTBL_LEN(t1);
323  if (t1_len) {
324  tmp_magic_p = (const uint32_t *)BU_PTBL_GET((struct bu_ptbl *)magic_p, 0);
325  if (*tmp_magic_p != NMG_VERTEX_MAGIC) {
326  bu_bomb("nmg_vertex_fuse(): passed bu_ptbl structure not containing vertex");
327  }
328  }
329  } else {
330  t1 = &tmp;
331  nmg_vertex_tabulate(t1, magic_p);
332  t1_len = BU_PTBL_LEN(t1);
333  }
334 
335  /* if there are no vertex, do nothing */
336  if (!t1_len) {
337  return 0;
338  }
339 
340  total = nmg_ptbl_vfuse(t1, tol);
341 
342  /* if bu_ptbl was passed into this function don't free it here */
343  if (*magic_p != BU_PTBL_MAGIC) {
344  bu_ptbl_free(t1);
345  }
346 
347  if (RTG.NMG_debug & DEBUG_BASIC && total > 0)
348  bu_log("nmg_vertex_fuse() %d\n", total);
349 
350  return total;
351 }
352 
353 
354 /**
355  * Checks if cnurb is linear
356  *
357  * Returns:
358  * 1 - cnurb is linear
359  * 0 - either cnurb is not linear, or it's not obvious
360  */
361 
362 int
363 nmg_cnurb_is_linear(const struct edge_g_cnurb *cnrb)
364 {
365  int i;
366  int coords;
367  int last_index;
368  int linear=0;
369 
370  NMG_CK_EDGE_G_CNURB(cnrb);
371 
372  if (RTG.NMG_debug & DEBUG_MESH) {
373  bu_log("nmg_cnurb_is_linear(%p)\n", (void *)cnrb);
374  rt_nurb_c_print(cnrb);
375  }
376 
377  if (cnrb->order <= 0) {
378  linear = 1;
379  goto out;
380  }
381 
382  if (cnrb->order == 2) {
383  if (cnrb->c_size == 2) {
384  linear = 1;
385  goto out;
386  }
387  }
388 
389  coords = RT_NURB_EXTRACT_COORDS(cnrb->pt_type);
390  last_index = (cnrb->c_size - 1)*coords;
391 
392  /* Check if all control points are either the start point or end point */
393  for (i=1; i<cnrb->c_size-2; i++) {
394  if (VEQUAL(&cnrb->ctl_points[0], &cnrb->ctl_points[i]))
395  continue;
396  if (VEQUAL(&cnrb->ctl_points[last_index], &cnrb->ctl_points[i]))
397  continue;
398 
399  goto out;
400  }
401 
402  linear = 1;
403 
404 out:
405  if (RTG.NMG_debug & DEBUG_MESH)
406  bu_log("nmg_cnurb_is_linear(%p) returning %d\n", (void *)cnrb, linear);
407 
408  return linear;
409 }
410 
411 
412 /**
413  * Checks if snurb surface is planar
414  *
415  * Returns:
416  * 0 - surface is not planar
417  * 1 - surface is planar (within tolerance)
418  */
419 
420 int
421 nmg_snurb_is_planar(const struct face_g_snurb *srf, const struct bn_tol *tol)
422 {
423  plane_t pl = {(fastf_t)0.0};
424  int i;
425  int coords;
426  mat_t matrix;
427  mat_t inverse;
428  vect_t vsum;
429  double det;
430  double one_over_vertex_count;
431  int planar=0;
432 
433  NMG_CK_FACE_G_SNURB(srf);
434  BN_CK_TOL(tol);
435 
436  if (RTG.NMG_debug & DEBUG_MESH) {
437  bu_log("nmg_snurb_is_planar(%p)\n", (void *)srf);
438  rt_nurb_s_print("", srf);
439  }
440 
441  if (srf->order[0] == 2 && srf->order[1] == 2) {
442  if (srf->s_size[0] == 2 && srf->s_size[1] == 2) {
443  planar = 1;
444  goto out;
445  }
446  }
447 
448  /* build matrix */
449  MAT_ZERO(matrix);
450  VSET(vsum, 0.0, 0.0, 0.0);
451 
452  one_over_vertex_count = 1.0/(double)(srf->s_size[0]*srf->s_size[1]);
453  coords = RT_NURB_EXTRACT_COORDS(srf->pt_type);
454 
455  /* calculate an average plane for all control points */
456  for (i=0; i<srf->s_size[0]*srf->s_size[1]; i++) {
457  fastf_t *pt;
458 
459  pt = &srf->ctl_points[ i*coords ];
460 
461  matrix[0] += pt[X] * pt[X];
462  matrix[1] += pt[X] * pt[Y];
463  matrix[2] += pt[X] * pt[Z];
464  matrix[5] += pt[Y] * pt[Y];
465  matrix[6] += pt[Y] * pt[Z];
466  matrix[10] += pt[Z] * pt[Z];
467 
468  vsum[X] += pt[X];
469  vsum[Y] += pt[Y];
470  vsum[Z] += pt[Z];
471  }
472  matrix[4] = matrix[1];
473  matrix[8] = matrix[2];
474  matrix[9] = matrix[6];
475  matrix[15] = 1.0;
476 
477  /* Check that we don't have a singular matrix */
478  det = bn_mat_determinant(matrix);
479 
480  if (!ZERO(det)) {
481  fastf_t inv_len_pl;
482 
483  /* invert matrix */
484  bn_mat_inv(inverse, matrix);
485 
486  /* get normal vector */
487  MAT4X3PNT(pl, inverse, vsum);
488 
489  /* unitize direction vector */
490  inv_len_pl = 1.0/(MAGNITUDE(pl));
491  HSCALE(pl, pl, inv_len_pl);
492 
493  /* get average vertex coordinates */
494  VSCALE(vsum, vsum, one_over_vertex_count);
495 
496  /* get distance from plane to origin */
497  pl[H] = VDOT(pl, vsum);
498 
499  } else {
500  int x_same=1;
501  int y_same=1;
502  int z_same=1;
503 
504  /* singular matrix, may occur if all vertices have the same zero
505  * component.
506  */
507  for (i=1; i<srf->s_size[0]*srf->s_size[1]; i++) {
508  if (!ZERO(srf->ctl_points[i*coords+X] - srf->ctl_points[X]))
509  x_same = 0;
510  if (!ZERO(srf->ctl_points[i*coords+Y] - srf->ctl_points[Y]))
511  y_same = 0;
512  if (!ZERO(srf->ctl_points[i*coords+Z] - srf->ctl_points[Z]))
513  z_same = 0;
514 
515  if (!x_same && !y_same && !z_same)
516  break;
517  }
518 
519  if (x_same) {
520  VSET(pl, 1.0, 0.0, 0.0);
521  } else if (y_same) {
522  VSET(pl, 0.0, 1.0, 0.0);
523  } else if (z_same) {
524  VSET(pl, 0.0, 0.0, 1.0);
525  }
526 
527  if (x_same || y_same || z_same) {
528  /* get average vertex coordinates */
529  VSCALE(vsum, vsum, one_over_vertex_count);
530 
531  /* get distance from plane to origin */
532  pl[H] = VDOT(pl, vsum);
533 
534  } else {
535  bu_log("nmg_snurb_is_plana: Cannot calculate plane for snurb %p\n", (void *)srf);
536  rt_nurb_s_print("", srf);
537  bu_bomb("nmg_snurb_is_plana: Cannot calculate plane for snurb\n");
538  }
539  }
540 
541  /* Now verify that every control point is on this plane */
542  for (i=0; i<srf->s_size[0]*srf->s_size[1]; i++) {
543  fastf_t *pt;
544  fastf_t dist;
545 
546  pt = &srf->ctl_points[ i*coords ];
547 
548  dist = DIST_PT_PLANE(pt, pl);
549  if (dist > tol->dist)
550  goto out;
551  }
552 
553  planar = 1;
554 out:
555  if (RTG.NMG_debug & DEBUG_MESH)
556  bu_log("nmg_snurb_is_planar(%p) returning %d\n", (void *)srf, planar);
557 
558  return planar;
559 
560 }
561 
562 
563 void
564 nmg_eval_linear_trim_curve(const struct face_g_snurb *snrb, const fastf_t *uvw, fastf_t *xyz)
565 {
566  int coords;
567  hpoint_t xyz1;
568 
569  if (snrb) {
570  NMG_CK_FACE_G_SNURB(snrb);
571  rt_nurb_s_eval(snrb, uvw[0], uvw[1], xyz1);
572  if (RT_NURB_IS_PT_RATIONAL(snrb->pt_type)) {
573  fastf_t inverse_weight;
574 
575  coords = RT_NURB_EXTRACT_COORDS(snrb->pt_type);
576  inverse_weight = 1.0/xyz1[coords-1];
577 
578  VSCALE(xyz, xyz1, inverse_weight);
579  } else {
580  VMOVE(xyz, xyz1);
581  }
582  } else {
583  VMOVE(xyz, uvw);
584  }
585 
586 }
587 
588 
589 void
590 nmg_eval_trim_curve(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t t, fastf_t *xyz)
591 {
592  hpoint_t uvw;
593  hpoint_t xyz1;
594  int coords;
595 
596  NMG_CK_EDGE_G_CNURB(cnrb);
597  if (snrb) {
598  NMG_CK_FACE_G_SNURB(snrb);
599  }
600 
601  rt_nurb_c_eval(cnrb, t, uvw);
602 
603  if (RT_NURB_IS_PT_RATIONAL(cnrb->pt_type)) {
604  fastf_t inverse_weight;
605 
606  coords = RT_NURB_EXTRACT_COORDS(cnrb->pt_type);
607  inverse_weight = 1.0/uvw[coords-1];
608 
609  VSCALE(uvw, uvw, inverse_weight);
610  }
611 
612  if (snrb) {
613  rt_nurb_s_eval(snrb, uvw[0], uvw[1], xyz1);
614  if (RT_NURB_IS_PT_RATIONAL(snrb->pt_type)) {
615  fastf_t inverse_weight;
616 
617  coords = RT_NURB_EXTRACT_COORDS(snrb->pt_type);
618  inverse_weight = 1.0/xyz1[coords-1];
619 
620  VSCALE(xyz, xyz1, inverse_weight);
621  } else {
622  VMOVE(xyz, xyz1);
623  }
624  } else {
625  VMOVE(xyz, uvw);
626  }
627 
628 }
629 
630 
631 void
632 nmg_split_trim(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, fastf_t t, struct pt_list *pt0, struct pt_list *pt1, const struct bn_tol *tol)
633 {
634  struct pt_list *pt_new;
635  fastf_t t_sub;
636  vect_t seg;
637 
638  NMG_CK_EDGE_G_CNURB(cnrb);
639  NMG_CK_FACE_G_SNURB(snrb);
640  BN_CK_TOL(tol);
641 
642  BU_ALLOC(pt_new, struct pt_list);
643  pt_new->t = t;
644 
645  if (pt_new->t < pt0->t || pt_new->t > pt1->t) {
646  bu_log("nmg_split_trim: split parameter (%g) is not between ends (%g and %g)\n",
647  t, pt0->t, pt1->t);
648  bu_bomb("nmg_split_trim: split parameters not between ends\n");
649  }
650 
651  nmg_eval_trim_curve(cnrb, snrb, pt_new->t, pt_new->xyz);
652 
653  BU_LIST_INSERT(&pt1->l, &pt_new->l);
654 
655  VSUB2(seg, pt0->xyz, pt_new->xyz);
656  if (MAGSQ(seg) > tol->dist_sq) {
657  t_sub = (pt0->t + pt_new->t)/2.0;
658  nmg_split_trim(cnrb, snrb, t_sub, pt0, pt_new, tol);
659  }
660 
661  VSUB2(seg, pt_new->xyz, pt1->xyz);
662  if (MAGSQ(seg) > tol->dist_sq) {
663  t_sub = (pt_new->t + pt1->t)/2.0;
664  nmg_split_trim(cnrb, snrb, t_sub, pt_new, pt1, tol);
665  }
666 }
667 
668 
669 void
670 nmg_eval_trim_to_tol(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t t0, const fastf_t t1, struct bu_list *head, const struct bn_tol *tol)
671 {
672  fastf_t t;
673  struct pt_list *pt0, *pt1;
674 
675  NMG_CK_EDGE_G_CNURB(cnrb);
676  NMG_CK_FACE_G_SNURB(snrb);
677  BN_CK_TOL(tol);
678 
679  if (RTG.NMG_debug & DEBUG_MESH)
680  bu_log("nmg_eval_trim_to_tol(cnrb=%p, snrb=%p, t0=%g, t1=%g) START\n",
681  (void *)cnrb, (void *)snrb, t0, t1);
682 
683  BU_ALLOC(pt0, struct pt_list);
684  pt0->t = t0;
685  nmg_eval_trim_curve(cnrb, snrb, pt0->t, pt0->xyz);
686  BU_LIST_INSERT(head, &pt0->l);
687 
688  BU_ALLOC(pt1, struct pt_list);
689  pt1->t = t1;
690  nmg_eval_trim_curve(cnrb, snrb, pt1->t, pt1->xyz);
691  BU_LIST_INSERT(head, &pt1->l);
692 
693  t = (t0 + t1)/2.0;
694  nmg_split_trim(cnrb, snrb, t, pt0, pt1, tol);
695 
696  if (RTG.NMG_debug & DEBUG_MESH)
697  bu_log("nmg_eval_trim_to_tol(cnrb=%p, snrb=%p, t0=%g, t1=%g) END\n",
698  (void *)cnrb, (void *)snrb, t0, t1);
699 }
700 
701 
702 void
703 nmg_split_linear_trim(const struct face_g_snurb *snrb, const fastf_t *uvw1, const fastf_t *uvw2, struct pt_list *pt0, struct pt_list *pt1, const struct bn_tol *tol)
704 {
705  struct pt_list *pt_new;
706  fastf_t t_sub;
707  fastf_t uvw_sub[3];
708  vect_t seg;
709 
710  if (snrb)
711  NMG_CK_FACE_G_SNURB(snrb);
712  BN_CK_TOL(tol);
713  BU_ALLOC(pt_new, struct pt_list);
714  pt_new->t = 0.5*(pt0->t + pt1->t);
715 
716  VBLEND2(uvw_sub, 1.0 - pt_new->t, uvw1, pt_new->t, uvw2);
717  nmg_eval_linear_trim_curve(snrb, uvw_sub, pt_new->xyz);
718 
719  BU_LIST_INSERT(&pt1->l, &pt_new->l);
720 
721  VSUB2(seg, pt0->xyz, pt_new->xyz);
722  if (MAGSQ(seg) > tol->dist_sq) {
723  t_sub = (pt0->t + pt_new->t)/2.0;
724  VBLEND2(uvw_sub, 1.0 - t_sub, uvw1, t_sub, uvw2);
725  nmg_split_linear_trim(snrb, uvw1, uvw2, pt0, pt_new, tol);
726  }
727 
728  VSUB2(seg, pt_new->xyz, pt1->xyz);
729  if (MAGSQ(seg) > tol->dist_sq) {
730  t_sub = (pt_new->t + pt1->t)/2.0;
731  VBLEND2(uvw_sub, 1.0 - t_sub, uvw1, t_sub, uvw2);
732  nmg_split_linear_trim(snrb, uvw1, uvw2, pt0, pt_new, tol);
733  }
734 }
735 
736 
737 void
738 nmg_eval_linear_trim_to_tol(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t *uvw1, const fastf_t *uvw2, struct bu_list *head, const struct bn_tol *tol)
739 {
740  struct pt_list *pt0, *pt1;
741 
742  NMG_CK_EDGE_G_CNURB(cnrb);
743  NMG_CK_FACE_G_SNURB(snrb);
744  BN_CK_TOL(tol);
745 
746  NMG_CK_EDGE_G_CNURB(cnrb);
747  NMG_CK_FACE_G_SNURB(snrb);
748  BN_CK_TOL(tol);
749 
750  if (RTG.NMG_debug & DEBUG_MESH)
751  bu_log("nmg_eval_linear_trim_to_tol(cnrb=%p, snrb=%p, uvw1=(%g %g %g), uvw2=(%g %g %g)) START\n",
752  (void *)cnrb, (void *)snrb, V3ARGS(uvw1), V3ARGS(uvw2));
753 
754  BU_ALLOC(pt0, struct pt_list);
755  pt0->t = 0.0;
756  nmg_eval_linear_trim_curve(snrb, uvw1, pt0->xyz);
757  BU_LIST_INSERT(head, &pt0->l);
758 
759  BU_ALLOC(pt1, struct pt_list);
760  pt1->t = 1.0;
761  nmg_eval_linear_trim_curve(snrb, uvw2, pt1->xyz);
762  BU_LIST_INSERT(head, &pt1->l);
763 
764  nmg_split_linear_trim(snrb, uvw1, uvw2, pt0, pt1, tol);
765 
766  if (RTG.NMG_debug & DEBUG_MESH)
767  bu_log("nmg_eval_linear_trim_to_tol(cnrb=%p, snrb=%p) END\n",
768  (void *)cnrb, (void *)snrb);
769 }
770 
771 
772 /* check for coincidence at twenty interior points along a cnurb */
773 #define CHECK_NUMBER 20
774 
775 /**
776  * Checks if CNURB is coincident with line segment from pt1 to pt2
777  * by calculating a number of points along the CNURB and checking
778  * if they lie on the line between pt1 and pt2 (within tolerance).
779  * NOTE: eu1 must be the EU referencing cnrb!!!!
780  *
781  * Returns:
782  * 0 - not coincident
783  * 1 - coincident
784  */
785 int
786 nmg_cnurb_lseg_coincident(const struct edgeuse *eu1, const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t *pt1, const fastf_t *pt2, const struct bn_tol *tol)
787 {
788  fastf_t t0, t1, t;
789  fastf_t delt;
790  int coincident=0;
791  int i;
792 
793 
794  NMG_CK_EDGEUSE(eu1);
795  NMG_CK_EDGE_G_CNURB(cnrb);
796 
797  if (RTG.NMG_debug & DEBUG_MESH)
798  bu_log("nmg_cnurb_lseg_coincident(eu1=%p, cnrb=%p, snrb=%p, pt1=(%g %g %g), pt2=(%g %g %g)\n",
799  (void *)eu1, (void *)cnrb, (void *)snrb, V3ARGS(pt1), V3ARGS(pt2));
800 
801  if (eu1->g.cnurb_p != cnrb) {
802  bu_log("nmg_cnurb_lseg_coincident: cnrb %p isn't from eu %p\n",
803  (void *)cnrb, (void *)eu1);
804  bu_bomb("nmg_cnurb_lseg_coincident: cnrb and eu1 disagree\n");
805  }
806 
807  if (snrb)
808  NMG_CK_FACE_G_SNURB(snrb);
809 
810  BN_CK_TOL(tol);
811 
812  if (cnrb->order <= 0) {
813  /* cnrb is linear in parameter space */
814  struct vertexuse *vu1;
815  struct vertexuse *vu2;
816  struct vertexuse_a_cnurb *vua1;
817  struct vertexuse_a_cnurb *vua2;
818 
819  if (!snrb)
820  bu_bomb("nmg_cnurb_lseg_coincident: No CNURB nor SNURB!!\n");
821 
822  vu1 = eu1->vu_p;
823  NMG_CK_VERTEXUSE(vu1);
824  if (!vu1->a.magic_p) {
825  bu_log("nmg_cnurb_lseg_coincident: vu (%p) has no attributes\n",
826  (void *)vu1);
827  bu_bomb("nmg_cnurb_lseg_coincident: vu has no attributes\n");
828  }
829 
830  if (*vu1->a.magic_p != NMG_VERTEXUSE_A_CNURB_MAGIC) {
831  bu_log("nmg_cnurb_lseg_coincident: vu (%p) from CNURB EU (%p) is not CNURB\n",
832  (void *)vu1, (void *)eu1);
833  bu_bomb("nmg_cnurb_lseg_coincident: vu from CNURB EU is not CNURB\n");
834  }
835 
836  vua1 = vu1->a.cnurb_p;
837  NMG_CK_VERTEXUSE_A_CNURB(vua1);
838 
839  vu2 = eu1->eumate_p->vu_p;
840  NMG_CK_VERTEXUSE(vu2);
841  if (!vu2->a.magic_p) {
842  bu_log("nmg_cnurb_lseg_coincident: vu (%p) has no attributes\n",
843  (void *)vu2);
844  bu_bomb("nmg_cnurb_lseg_coincident: vu has no attributes\n");
845  }
846 
847  if (*vu2->a.magic_p != NMG_VERTEXUSE_A_CNURB_MAGIC) {
848  bu_log("nmg_cnurb_lseg_coincident: vu (%p) from CNURB EU (%p) is not CNURB\n",
849  (void *)vu2, (void *)eu1);
850  bu_bomb("nmg_cnurb_lseg_coincident: vu from CNURB EU is not CNURB\n");
851  }
852 
853  vua2 = vu2->a.cnurb_p;
854  NMG_CK_VERTEXUSE_A_CNURB(vua2);
855 
856  coincident = 1;
857  for (i=0; i<CHECK_NUMBER; i++) {
858  point_t uvw;
859  point_t xyz;
860  fastf_t blend;
861  fastf_t dist;
862  point_t pca;
863 
864  blend = (double)(i+1)/(double)(CHECK_NUMBER+1);
865  VBLEND2(uvw, blend, vua1->param, (1.0-blend), vua2->param);
866 
867  nmg_eval_linear_trim_curve(snrb, uvw, xyz);
868 
869  if (bn_dist_pt3_lseg3(&dist, pca, pt1, pt2, xyz, tol) > 2) {
870  coincident = 0;
871  break;
872  }
873  }
874  if (RTG.NMG_debug & DEBUG_MESH)
875  bu_log("nmg_cnurb_lseg_coincident returning %d\n", coincident);
876  return coincident;
877  }
878 
879  t0 = cnrb->k.knots[0];
880  t1 = cnrb->k.knots[cnrb->k.k_size-1];
881  delt = (t1 - t0)/(double)(CHECK_NUMBER+1);
882 
883  coincident = 1;
884  for (i=0; i<CHECK_NUMBER; i++) {
885  point_t xyz;
886  fastf_t dist;
887  point_t pca;
888 
889  t = t0 + (double)(i+1)*delt;
890 
891  nmg_eval_trim_curve(cnrb, snrb, t, xyz);
892 
893  if (bn_dist_pt3_lseg3(&dist, pca, pt1, pt2, xyz, tol) > 2) {
894  coincident = 0;
895  break;
896  }
897  }
898  if (RTG.NMG_debug & DEBUG_MESH)
899  bu_log("nmg_cnurb_lseg_coincident returning %d\n", coincident);
900  return coincident;
901 }
902 
903 
904 /**
905  * Checks if CNURB eu lies on curve contained in list headed at "head"
906  * "Head" must contain a list of points (struct pt_list) each within
907  * tolerance of the next. (Just checks at "CHECK_NUMBER" points for now).
908  *
909  * Returns:
910  * 0 - cnurb is not on curve;
911  * 1 - cnurb is on curve
912  */
913 int
914 nmg_cnurb_is_on_crv(const struct edgeuse *eu, const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const struct bu_list *head, const struct bn_tol *tol)
915 {
916  int i;
917  int coincident;
918  fastf_t t, t0, t1;
919  fastf_t delt;
920 
921  NMG_CK_EDGEUSE(eu);
922  NMG_CK_EDGE_G_CNURB(cnrb);
923  if (snrb)
924  NMG_CK_FACE_G_SNURB(snrb);
925  BU_CK_LIST_HEAD(head);
926  BN_CK_TOL(tol);
927 
928  if (RTG.NMG_debug & DEBUG_MESH)
929  bu_log("nmg_cnurb_is_on_crv(eu=%p, cnrb=%p, snrb=%p, head=%p)\n",
930  (void *)eu, (void *)cnrb, (void *)snrb, (void *)head);
931  if (cnrb->order <= 0) {
932  struct vertexuse *vu1, *vu2;
933  struct vertexuse_a_cnurb *vu1a, *vu2a;
934  fastf_t blend;
935  point_t uvw;
936  point_t xyz;
937 
938  /* cnurb is linear in parameter space */
939 
940  vu1 = eu->vu_p;
941  NMG_CK_VERTEXUSE(vu1);
942  vu2 = eu->eumate_p->vu_p;
943  NMG_CK_VERTEXUSE(vu2);
944 
945  if (!vu1->a.magic_p) {
946  bu_log("nmg_cnurb_is_on_crv(): vu (%p) on CNURB EU (%p) has no attributes\n",
947  (void *)vu1, (void *)eu);
948  bu_bomb("nmg_cnurb_is_on_crv(): vu on CNURB EU has no attributes\n");
949  }
950  if (*vu1->a.magic_p != NMG_VERTEXUSE_A_CNURB_MAGIC) {
951  bu_log("nmg_cnurb_is_on_crv(): vu (%p) on CNURB EU (%p) is not CNURB\n",
952  (void *)vu1, (void *)eu);
953  bu_bomb("nmg_cnurb_is_on_crv(): vu on CNURB EU is not CNURB\n");
954  }
955  vu1a = vu1->a.cnurb_p;
956  NMG_CK_VERTEXUSE_A_CNURB(vu1a);
957 
958  if (!vu2->a.magic_p) {
959  bu_log("nmg_cnurb_is_on_crv(): vu (%p) on CNURB EU (%p) has no attributes\n",
960  (void *)vu2, (void *)eu->eumate_p);
961  bu_bomb("nmg_cnurb_is_on_crv(): vu on CNURB EU has no attributes\n");
962  }
963  if (*vu2->a.magic_p != NMG_VERTEXUSE_A_CNURB_MAGIC) {
964  bu_log("nmg_cnurb_is_on_crv(): vu (%p) on CNURB EU (%p) is not CNURB\n",
965  (void *)vu2, (void *)eu->eumate_p);
966  bu_bomb("nmg_cnurb_is_on_crv(): vu on CNURB EU is not CNURB\n");
967  }
968  vu2a = vu2->a.cnurb_p;
969  NMG_CK_VERTEXUSE_A_CNURB(vu2a);
970 
971  coincident = 1;
972  for (i=0; i<CHECK_NUMBER; i++) {
973  struct pt_list *pt;
974  int found=0;
975 
976  blend = (double)(i+1)/(double)(CHECK_NUMBER+1);
977 
978  VBLEND2(uvw, blend, vu1a->param, (1.0-blend), vu2a->param);
979 
980  nmg_eval_linear_trim_curve(snrb, uvw, xyz);
981 
982  for (BU_LIST_FOR(pt, pt_list, head)) {
983  vect_t diff;
984 
985  VSUB2(diff, xyz, pt->xyz);
986  if (MAGSQ(diff) <= tol->dist_sq) {
987  found = 1;
988  break;
989  }
990  }
991  if (!found) {
992  coincident = 0;
993  break;
994  }
995  }
996  if (RTG.NMG_debug & DEBUG_MESH)
997  bu_log("nmg_cnurb_is_on_crv() returning %d\n", coincident);
998  return coincident;
999  }
1000 
1001  coincident = 1;
1002  t0 = cnrb->k.knots[0];
1003  t1 = cnrb->k.knots[cnrb->k.k_size-1];
1004  delt = (t1 - t0)/(double)(CHECK_NUMBER+1);
1005  for (i=0; i<CHECK_NUMBER; i++) {
1006  point_t xyz;
1007  struct pt_list *pt;
1008  int found;
1009 
1010  t = t0 + (double)(i+1)*delt;
1011 
1012  nmg_eval_trim_curve(cnrb, snrb, t, xyz);
1013 
1014  found = 0;
1015  for (BU_LIST_FOR(pt, pt_list, head)) {
1016  vect_t diff;
1017 
1018  VSUB2(diff, xyz, pt->xyz);
1019  if (MAGSQ(diff) <= tol->dist_sq) {
1020  found = 1;
1021  break;
1022  }
1023  }
1024  if (!found) {
1025  coincident = 0;
1026  break;
1027  }
1028  }
1029 
1030  if (RTG.NMG_debug & DEBUG_MESH)
1031  bu_log("nmg_cnurb_is_on_crv returning %d\n", coincident);
1032  return coincident;
1033 }
1034 
1035 /* compare function for bu_sort within function nmg_edge_fuse */
1036 static int
1037 v_ptr_comp(const void *p1, const void *p2, void *UNUSED(arg))
1038 {
1039  size_t i, j;
1040 
1041  i = ((size_t *)p1)[1];
1042  j = ((size_t *)p2)[1];
1043 
1044  if (i == j)
1045  return 0;
1046  else if (i > j)
1047  return 1;
1048  return -1;
1049 }
1050 
1051 
1052 /**
1053  * Note: If a bu_ptbl structure is passed into this function, the
1054  * structure must contain edgeuse. Vertices will then be fused
1055  * at the shell level. If an NMG structure is passed into this
1056  * function, if the structure is an NMG region or model, vertices
1057  * will be fused at the model level. If the NMG structure passed
1058  * in is a shell or anything lower, vertices will be fused at the
1059  * shell level.
1060  */
1061 int
1062 nmg_edge_fuse(const uint32_t *magic_p, const struct bn_tol *tol)
1063 {
1064  typedef size_t (*edgeuse_vert_list_t)[2];
1065  edgeuse_vert_list_t edgeuse_vert_list;
1066  int count=0;
1067  size_t nelem;
1068  struct bu_ptbl *eu_list;
1069  struct bu_ptbl tmp;
1070  struct edge *e1;
1071  struct edgeuse *eu, *eu1;
1072  struct vertex *v1;
1073  register size_t i, j;
1074  register struct edge *e2;
1075  register struct edgeuse *eu2;
1076  register struct vertex *v2;
1077  struct shell *s;
1078  struct model *m;
1079  const uint32_t *tmp_magic_p;
1080 
1081  if (*magic_p == BU_PTBL_MAGIC) {
1082  tmp_magic_p = (const uint32_t *)BU_PTBL_GET((struct bu_ptbl *)magic_p, 0);
1083  if (*tmp_magic_p != NMG_EDGEUSE_MAGIC) {
1084  bu_bomb("nmg_edge_fuse(): passed bu_ptbl structure not containing edgeuse");
1085  }
1086  } else {
1087  tmp_magic_p = magic_p;
1088  }
1089  if (*tmp_magic_p == NMG_REGION_MAGIC || *tmp_magic_p == NMG_MODEL_MAGIC) {
1090  if (*tmp_magic_p == NMG_MODEL_MAGIC) {
1091  m = (struct model *)tmp_magic_p;
1092  } else {
1093  m = ((struct nmgregion *)tmp_magic_p)->m_p;
1094  }
1095  (void)nmg_vertex_fuse(&m->magic, tol);
1096  } else {
1097  s = nmg_find_shell(tmp_magic_p);
1098  (void)nmg_vertex_fuse(&s->l.magic, tol);
1099  }
1100  if (*magic_p == BU_PTBL_MAGIC) {
1101  eu_list = (struct bu_ptbl *)magic_p;
1102  } else {
1103  bu_ptbl_init(&tmp, 64, "eu_list buffer");
1104  nmg_edgeuse_tabulate(&tmp, magic_p);
1105  eu_list = &tmp;
1106  }
1107 
1108  nelem = BU_PTBL_END(eu_list) * 2;
1109  if (nelem == 0)
1110  return 0;
1111 
1112  edgeuse_vert_list = (edgeuse_vert_list_t)bu_calloc(nelem, 2 * sizeof(size_t), "edgeuse_vert_list");
1113 
1114  j = 0;
1115  for (i = 0; i < (size_t)BU_PTBL_END(eu_list) ; i++) {
1116  eu = (struct edgeuse *)BU_PTBL_GET(eu_list, i);
1117  edgeuse_vert_list[j][0] = (size_t)eu;
1118  edgeuse_vert_list[j][1] = (size_t)eu->vu_p->v_p;
1119  j++;
1120  edgeuse_vert_list[j][0] = (size_t)eu;
1121  edgeuse_vert_list[j][1] = (size_t)eu->eumate_p->vu_p->v_p;
1122  j++;
1123  }
1124 
1125  bu_sort(&edgeuse_vert_list[0][0], nelem, 2 * sizeof(size_t), v_ptr_comp, NULL);
1126 
1127  for (i = 0; i < nelem ; i++) {
1128 
1129  eu1 = (struct edgeuse *)edgeuse_vert_list[i][0];
1130 
1131  if (!eu1) {
1132  continue;
1133  }
1134 
1135  v1 = (struct vertex *)edgeuse_vert_list[i][1];
1136  e1 = eu1->e_p;
1137 
1138  for (j = i+1; j < nelem ; j++) {
1139 
1140  eu2 = (struct edgeuse *)edgeuse_vert_list[j][0];
1141 
1142  if (!eu2) {
1143  continue;
1144  }
1145 
1146  v2 = (struct vertex *)edgeuse_vert_list[j][1];
1147  e2 = eu2->e_p;
1148 
1149  if (v1 != v2) {
1150  break; /* no more to test */
1151  }
1152 
1153  if (e1 == e2) {
1154  /* we found ourselves, or already fused, mark as fused and continue */
1155  edgeuse_vert_list[j][0] = (size_t)NULL;
1156  continue;
1157  }
1158 
1159  if (NMG_ARE_EUS_ADJACENT(eu1, eu2)) {
1160  count++;
1161  nmg_radial_join_eu(eu1, eu2, tol);
1162  edgeuse_vert_list[j][0] = (size_t)NULL; /* mark as fused */
1163  }
1164  }
1165  }
1166 
1167  bu_free((char *)edgeuse_vert_list, "edgeuse_vert_list");
1168 
1169  /* if bu_ptbl was passed into this function don't free it here */
1170  if (*magic_p != BU_PTBL_MAGIC) {
1171  bu_ptbl_free(eu_list);
1172  }
1173 
1174  return count;
1175 }
1176 
1177 
1178 /* compare function for bu_sort within function nmg_edge_g_fuse */
1179 static int
1180 e_rr_xyp_comp(const void *p1, const void *p2, void *arg)
1181 {
1182  fastf_t i, j;
1183  fastf_t *edge_rr_xyp = (fastf_t *)arg;
1184  i = edge_rr_xyp[((*((size_t *)p1)))];
1185  j = edge_rr_xyp[(*((size_t *)p2))];
1186 
1187  if (EQUAL(i, j))
1188  return 0;
1189  else if (i > j)
1190  return 1;
1191  return -1;
1192 }
1193 
1194 
1195 /**
1196  * Fuse edge_g structs.
1197  */
1198 int
1199 nmg_edge_g_fuse(const uint32_t *magic_p, const struct bn_tol *tol)
1200 {
1201  register size_t i, j;
1202  register struct edge_g_lseg *eg1, *eg2;
1203  register struct edgeuse *eu1, *eu2;
1204  register struct vertex *eu1v1, *eu1v2, *eu2v1, *eu2v2;
1205  struct bu_ptbl etab; /* edge table */
1206  size_t etab_cnt; /* edge count */
1207  int total;
1208  fastf_t tmp;
1209 
1210  /* rise over run arrays for the xz and yz planes */
1211  fastf_t *edge_rr, *edge_rr_xzp, *edge_rr_yzp, *edge_rr_xyp;
1212 
1213  /* index into all arrays sorted by the contents of array edge_rr_xyp */
1214  size_t *sort_idx_xyp;
1215 
1216  /* arrays containing special case flags for each edge in the xy, xz and yz planes */
1217  /* 0 = no special case, 1 = infinite ratio, 2 = zero ratio, 3 = point in plane (no ratio) */
1218  char *edge_sc, *edge_sc_xyp, *edge_sc_xzp, *edge_sc_yzp;
1219 
1220  /* Make a list of all the edge geometry structs in the model */
1221  nmg_edge_g_tabulate(&etab, magic_p);
1222 
1223  /* number of edges in table etab */
1224  etab_cnt = BU_PTBL_LEN(&etab);
1225 
1226  if (etab_cnt == 0) {
1227  return 0;
1228  }
1229 
1230  sort_idx_xyp = (size_t *)bu_calloc(etab_cnt, sizeof(size_t), "sort_idx_xyp");
1231 
1232  edge_rr = (fastf_t *)bu_calloc(etab_cnt * 3, sizeof(fastf_t), "edge_rr_xyp");
1233  /* rise over run in xy plane */
1234  edge_rr_xyp = edge_rr;
1235  /* rise over run in xz plane */
1236  edge_rr_xzp = edge_rr + etab_cnt;
1237  /* rise over run in yz plane */
1238  edge_rr_yzp = edge_rr + (etab_cnt * 2);
1239 
1240  edge_sc = (char *)bu_calloc(etab_cnt * 3, sizeof(char), "edge_sc_xyp");
1241  /* special cases in xy plane */
1242  edge_sc_xyp = edge_sc;
1243  /* special cases in xz plane */
1244  edge_sc_xzp = edge_sc + etab_cnt;
1245  /* special cases in yz plane */
1246  edge_sc_yzp = edge_sc + (etab_cnt * 2);
1247 
1248  /* load arrays */
1249  for (i = 0 ; i < etab_cnt ; i++) {
1250  point_t pt1, pt2;
1251  register fastf_t xdif, ydif, zdif;
1252  register fastf_t dist = tol->dist;
1253 
1254  eg1 = (struct edge_g_lseg *)BU_PTBL_GET(&etab, i);
1255  eu1 = BU_LIST_MAIN_PTR(edgeuse, BU_LIST_FIRST(bu_list, &eg1->eu_hd2), l2);
1256 
1257  VMOVE(pt1, eu1->vu_p->v_p->vg_p->coord);
1258  VMOVE(pt2, eu1->eumate_p->vu_p->v_p->vg_p->coord);
1259 
1260  xdif = fabs(pt2[X] - pt1[X]);
1261  ydif = fabs(pt2[Y] - pt1[Y]);
1262  zdif = fabs(pt2[Z] - pt1[Z]);
1263  sort_idx_xyp[i] = i;
1264 
1265  if ((xdif < dist) && (ydif > dist)) {
1266  edge_rr_xyp[i] = MAX_FASTF;
1267  edge_sc_xyp[i] = 1; /* no angle in xy plane, vertical line (along y-axis) */
1268  } else if ((xdif > dist) && (ydif < dist)) {
1269  edge_sc_xyp[i] = 2; /* no angle in xy plane, horz line (along x-axis) */
1270  } else if ((xdif < dist) && (ydif < dist)) {
1271  edge_sc_xyp[i] = 3; /* only a point in the xy plane */
1272  edge_rr_xyp[i] = -MAX_FASTF;
1273  } else {
1274  edge_rr_xyp[i] = (pt2[Y] - pt1[Y]) / (pt2[X] - pt1[X]); /* rise over run */
1275  }
1276 
1277  if ((xdif < dist) && (zdif > dist)) {
1278  edge_sc_xzp[i] = 1; /* no angle in xz plane, vertical line (along z-axis) */
1279  } else if ((xdif > dist) && (zdif < dist)) {
1280  edge_sc_xzp[i] = 2; /* no angle in xz plane, horz line (along x-axis) */
1281  } else if ((xdif < dist) && (zdif < dist)) {
1282  edge_sc_xzp[i] = 3; /* only a point in the xz plane */
1283  } else {
1284  edge_rr_xzp[i] = (pt2[Z] - pt1[Z]) / (pt2[X] - pt1[X]); /* rise over run */
1285  }
1286 
1287  if ((ydif < dist) && (zdif > dist)) {
1288  edge_sc_yzp[i] = 1; /* no angle in yz plane, vertical line (along z-axis) */
1289  } else if ((ydif > dist) && (zdif < dist)) {
1290  edge_sc_yzp[i] = 2; /* no angle in yz plane, horz line (along y-axis) */
1291  } else if ((ydif < dist) && (zdif < dist)) {
1292  edge_sc_yzp[i] = 3; /* only a point in the yz plane */
1293  } else {
1294  edge_rr_yzp[i] = (pt2[Z] - pt1[Z]) / (pt2[Y] - pt1[Y]); /* rise over run */
1295  }
1296  }
1297 
1298  /* create sort index based on array edge_rr_xyp */
1299  bu_sort(sort_idx_xyp, etab_cnt, sizeof(size_t), e_rr_xyp_comp, edge_rr_xyp);
1300 
1301  /* main loop */
1302  total = 0;
1303  for (i = 0 ; i < etab_cnt ; i++) {
1304 
1305  eg1 = (struct edge_g_lseg *)BU_PTBL_GET(&etab, sort_idx_xyp[i]);
1306 
1307  if (!eg1) {
1308  continue;
1309  }
1310 
1311  if (UNLIKELY(eg1->l.magic == NMG_EDGE_G_CNURB_MAGIC)) {
1312  continue;
1313  }
1314 
1315  eu1 = BU_LIST_MAIN_PTR(edgeuse, BU_LIST_FIRST(bu_list, &eg1->eu_hd2), l2);
1316  eu1v1 = eu1->vu_p->v_p;
1317  eu1v2 = eu1->eumate_p->vu_p->v_p;
1318 
1319  for (j = i+1; j < etab_cnt ; j++) {
1320 
1321  eg2 = (struct edge_g_lseg *)BU_PTBL_GET(&etab, sort_idx_xyp[j]);
1322 
1323  if (!eg2) {
1324  continue;
1325  }
1326 
1327  if (UNLIKELY(eg2->l.magic == NMG_EDGE_G_CNURB_MAGIC)) {
1328  continue;
1329  }
1330 
1331  if (UNLIKELY(eg1 == eg2)) {
1332  BU_PTBL_SET(&etab, sort_idx_xyp[j], NULL);
1333  continue;
1334  }
1335 
1336  eu2 = BU_LIST_MAIN_PTR(edgeuse, BU_LIST_FIRST(bu_list, &eg2->eu_hd2), l2);
1337  eu2v1 = eu2->vu_p->v_p;
1338  eu2v2 = eu2->eumate_p->vu_p->v_p;
1339 
1340  if (!(((eu1v1 == eu2v2) && (eu1v2 == eu2v1)) || ((eu1v1 == eu2v1) && (eu1v2 == eu2v2)))) {
1341  /* true when vertices are not fused */
1342 
1343  /* xy plane tests */
1344  if (edge_sc_xyp[sort_idx_xyp[i]] != edge_sc_xyp[sort_idx_xyp[j]]) {
1345  /* not parallel in xy plane */
1346  break;
1347  } else if (edge_sc_xyp[sort_idx_xyp[i]] == 0) {
1348  tmp = edge_rr_xyp[sort_idx_xyp[i]] - edge_rr_xyp[sort_idx_xyp[j]];
1349  if (fabs(tmp) > tol->dist) {
1350  /* not parallel in xy plane */
1351  break;
1352  }
1353  }
1354 
1355  /* xz plane tests */
1356  if (edge_sc_xzp[sort_idx_xyp[i]] != edge_sc_xzp[sort_idx_xyp[j]]) {
1357  /* not parallel in xz plane */
1358  continue;
1359  } else if (edge_sc_xzp[sort_idx_xyp[i]] == 0) {
1360  tmp = edge_rr_xzp[sort_idx_xyp[i]] - edge_rr_xzp[sort_idx_xyp[j]];
1361  if (fabs(tmp) > tol->dist) {
1362  /* not parallel in xz plane */
1363  continue;
1364  }
1365  }
1366 
1367  /* yz plane tests */
1368  if (edge_sc_yzp[sort_idx_xyp[i]] != edge_sc_yzp[sort_idx_xyp[j]]) {
1369  /* not parallel in xz plane */
1370  continue;
1371  } else if (edge_sc_yzp[sort_idx_xyp[i]] == 0) {
1372  tmp = edge_rr_yzp[sort_idx_xyp[i]] - edge_rr_yzp[sort_idx_xyp[j]];
1373  if (fabs(tmp) > tol->dist) {
1374  /* not parallel in yz plane */
1375  continue;
1376  }
1377  }
1378 
1379  if (!nmg_2edgeuse_g_coincident(eu1, eu2, tol)) {
1380  continue;
1381  }
1382  }
1383 
1384  total++;
1385  nmg_jeg(eg1, eg2);
1386 
1387  BU_PTBL_SET(&etab, sort_idx_xyp[j], NULL);
1388  }
1389  }
1390 
1391  bu_ptbl_free(&etab);
1392  bu_free(edge_rr, "edge_rr,");
1393  bu_free(edge_sc, "edge_sc");
1394 
1395  if (UNLIKELY(RTG.NMG_debug & DEBUG_BASIC && total > 0))
1396  bu_log("nmg_edge_g_fuse(): %d edge_g_lseg's fused\n", total);
1397 
1398  return total;
1399 }
1400 
1401 
1402 #define TOL_MULTIPLES 1.0
1403 /**
1404  * Check that all the vertices in fu1 are within tol->dist of fu2's surface.
1405  * fu1 and fu2 may be the same face, or different.
1406  *
1407  * This is intended to be a geometric check only, not a topology check.
1408  * Topology may have become inappropriately shared.
1409  *
1410  * Returns -
1411  * 0 All is well, or all verts are within TOL_MULTIPLES*tol->dist of fu2
1412  * count Number of verts *not* on fu2's surface when at least one is
1413  * more than TOL_MULTIPLES*tol->dist from fu2.
1414  */
1415 int
1416 nmg_ck_fu_verts(struct faceuse *fu1, struct face *f2, const struct bn_tol *tol)
1417 {
1418  fastf_t dist = 0.0;
1419  fastf_t worst = 0.0;
1420  int count = 0;
1421  struct loopuse *lu;
1422  struct edgeuse *eu;
1423  struct vertexuse *vu;
1424  struct vertex *v;
1425  struct vertex_g *vg;
1426  plane_t pl2;
1427 
1428  NMG_CK_FACEUSE(fu1);
1429  NMG_CK_FACE(f2);
1430  BN_CK_TOL(tol);
1431 
1432  NMG_CK_FACE_G_PLANE(f2->g.plane_p);
1433 
1434  HMOVE(pl2, f2->g.plane_p->N);
1435 
1436  for (BU_LIST_FOR(lu, loopuse, &fu1->lu_hd)) {
1437  NMG_CK_LOOPUSE(lu);
1438 
1439  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
1440  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1441  NMG_CK_VERTEXUSE(vu);
1442  NMG_CK_VERTEX(vu->v_p);
1443 
1444  v = vu->v_p;
1445  vg = v->vg_p;
1446 
1447  if (!vg) {
1448  bu_bomb("nmg_ck_fu_verts(): vertex with no geometry?\n");
1449  }
1450  NMG_CK_VERTEX_G(vg);
1451 
1452  /* Geometry check */
1453  dist = DIST_PT_PLANE(vg->coord, pl2);
1454  if (!NEAR_ZERO(dist, tol->dist)) {
1455  if (RTG.NMG_debug & DEBUG_MESH) {
1456  bu_log("nmg_ck_fu_verts(%p, %p) v %p off face by %e\n",
1457  (void *)fu1, (void *)f2, (void *)v, dist);
1458  VPRINT(" pt", vg->coord);
1459  PLPRINT(" fg2", pl2);
1460  }
1461  count++;
1462 
1463  dist = fabs(dist);
1464  if (dist > worst) {
1465  worst = dist;
1466  }
1467  }
1468  } else if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_EDGEUSE_MAGIC) {
1469  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1470  NMG_CK_EDGEUSE(eu);
1471  NMG_CK_VERTEXUSE(eu->vu_p);
1472  NMG_CK_VERTEX(eu->vu_p->v_p);
1473 
1474  v = eu->vu_p->v_p;
1475  vg = v->vg_p;
1476 
1477  if (!vg) {
1478  bu_bomb("nmg_ck_fu_verts(): vertex with no geometry?\n");
1479  }
1480  NMG_CK_VERTEX_G(vg);
1481 
1482  /* Geometry check */
1483  dist = DIST_PT_PLANE(vg->coord, pl2);
1484  if (!NEAR_ZERO(dist, tol->dist)) {
1485  if (RTG.NMG_debug & DEBUG_MESH) {
1486  bu_log("nmg_ck_fu_verts(%p, %p) v %p off face by %e\n",
1487  (void *)fu1, (void *)f2, (void *)v, dist);
1488  VPRINT(" pt", vg->coord);
1489  PLPRINT(" fg2", pl2);
1490  }
1491  count++;
1492 
1493  dist = fabs(dist);
1494  if (dist > worst) {
1495  worst = dist;
1496  }
1497  }
1498  }
1499  } else {
1500  bu_bomb("nmg_ck_fu_verts(): unknown loopuse child\n");
1501  }
1502  }
1503 
1504  if (worst > TOL_MULTIPLES*tol->dist) {
1505  return count;
1506  } else {
1507  return 0;
1508  }
1509 }
1510 
1511 
1512 /**
1513  * Similar to nmg_ck_fu_verts, but checks all vertices that use the same
1514  * face geometry as fu1
1515  * fu1 and f2 may be the same face, or different.
1516  *
1517  * This is intended to be a geometric check only, not a topology check.
1518  * Topology may have become inappropriately shared.
1519  *
1520  * Returns -
1521  * 0 All is well.
1522  * count Number of verts *not* on fu2's surface.
1523  *
1524  */
1525 int
1526 nmg_ck_fg_verts(struct faceuse *fu1, struct face *f2, const struct bn_tol *tol)
1527 {
1528  struct face_g_plane *fg1;
1529  struct faceuse *fu;
1530  struct face *f;
1531  int count=0;
1532 
1533  NMG_CK_FACEUSE(fu1);
1534  NMG_CK_FACE(f2);
1535  BN_CK_TOL(tol);
1536 
1537  NMG_CK_FACE(fu1->f_p);
1538  fg1 = fu1->f_p->g.plane_p;
1539  NMG_CK_FACE_G_PLANE(fg1);
1540 
1541  for (BU_LIST_FOR(f, face, &fg1->f_hd)) {
1542  NMG_CK_FACE(f);
1543 
1544  fu = f->fu_p;
1545  NMG_CK_FACEUSE(fu);
1546 
1547  count += nmg_ck_fu_verts(fu, f2, tol);
1548  }
1549 
1550  return count;
1551 }
1552 
1553 
1554 /**
1555  * XXX A better algorithm would be to compare loop by loop.
1556  * If the two faces share all the verts of at least one loop of 3 or more
1557  * vertices, then they should be shared. Otherwise it will be awkward
1558  * having shared loop(s) on non-shared faces!!
1559  *
1560  * Compare the geometry of two faces, and fuse them if they are the
1561  * same within tolerance.
1562  * First compare the plane equations. If they are "similar" (within tol),
1563  * then check all verts in f2 to make sure that they are within tol->dist
1564  * of f1's geometry. If they are, then fuse the face geometry.
1565  *
1566  * Returns -
1567  * 0 Faces were not fused.
1568  * >0 Faces were successfully fused.
1569  */
1570 int
1571 nmg_two_face_fuse(struct face *f1, struct face *f2, const struct bn_tol *tol)
1572 {
1573  register struct face_g_plane *fg1;
1574  register struct face_g_plane *fg2;
1575  int flip2 = 0;
1576  fastf_t dist;
1577 
1578  fg1 = f1->g.plane_p;
1579  fg2 = f2->g.plane_p;
1580 
1581  if (!fg1 || !fg2) {
1582  if (RTG.NMG_debug & DEBUG_MESH) {
1583  bu_log("nmg_two_face_fuse(%p, %p) null fg fg1=%p, fg2=%p\n",
1584  (void *)f1, (void *)f2, (void *)fg1, (void *)fg2);
1585  }
1586  return 0;
1587  }
1588 
1589  /* test if the face geometry (i.e. face plane) is already fused */
1590  if (fg1 == fg2) {
1591  if (RTG.NMG_debug & DEBUG_MESH) {
1592  bu_log("nmg_two_face_fuse(%p, %p) fg already shared\n", (void *)f1, (void *)f2);
1593  }
1594  return 0;
1595  }
1596 
1597  /* if the bounding box of each faceuse is not within distance
1598  * tolerance of each other, then skip fusing
1599  */
1600  if (V3RPP_DISJOINT_TOL(f1->min_pt, f1->max_pt, f2->min_pt, f2->max_pt, tol->dist)) {
1601  return 0;
1602  }
1603 
1604  /* check the distance between the planes at their center */
1605  dist = fabs(fg1->N[W] - fg2->N[W]);
1606  if (!NEAR_ZERO(dist, tol->dist)) {
1607  return 0;
1608  }
1609 
1610  /* check that each vertex of each faceuse is within tolerance of
1611  * the plane of the other faceuse
1612  */
1613  if (nmg_ck_fg_verts(f1->fu_p, f2, tol) || nmg_ck_fg_verts(f2->fu_p, f1, tol)) {
1614  if (RTG.NMG_debug & DEBUG_MESH) {
1615  bu_log("nmg_two_face_fuse: verts not within tol of surface, can't fuse\n");
1616  }
1617  return 0;
1618  }
1619 
1620  if (RTG.NMG_debug & DEBUG_MESH) {
1621  bu_log("nmg_two_face_fuse(%p, %p) coplanar faces, flip2=%d\n",
1622  (void *)f1, (void *)f2, flip2);
1623  }
1624 
1625  /* check if normals are pointing in the same direction */
1626  if (VDOT(fg1->N, fg2->N) >= SMALL_FASTF) {
1627  /* same direction */
1628  flip2 = 0;
1629  } else {
1630  /* opposite direction */
1631  flip2 = 1;
1632  }
1633 
1634  if (flip2 == 0) {
1635  if (RTG.NMG_debug & DEBUG_MESH) {
1636  bu_log("joining face geometry (same dir) f1=%p, f2=%p\n", (void *)f1, (void *)f2);
1637  PLPRINT(" fg1", fg1->N);
1638  PLPRINT(" fg2", fg2->N);
1639  }
1640  nmg_jfg(f1, f2);
1641  } else {
1642  register struct face *fn;
1643  if (RTG.NMG_debug & DEBUG_MESH) {
1644  bu_log("joining face geometry (opposite dirs)\n");
1645 
1646  bu_log(" f1=%p, flip=%d", (void *)f1, f1->flip);
1647  PLPRINT(" fg1", fg1->N);
1648 
1649  bu_log(" f2=%p, flip=%d", (void *)f2, f2->flip);
1650  PLPRINT(" fg2", fg2->N);
1651  }
1652  /* Flip flags of faces using fg2, first! */
1653  for (BU_LIST_FOR(fn, face, &fg2->f_hd)) {
1654  fn->flip = !fn->flip;
1655  if (RTG.NMG_debug & DEBUG_MESH) {
1656  bu_log("f=%p, new flip=%d\n", (void *)fn, fn->flip);
1657  }
1658  }
1659  nmg_jfg(f1, f2);
1660  }
1661  return 1;
1662 }
1663 
1664 
1665 /**
1666  * A routine to find all face geometry structures in an nmg model that
1667  * have the same plane equation, and have them share face geometry.
1668  * (See also nmg_shell_coplanar_face_merge(), which actually moves
1669  * the loops into one face).
1670  *
1671  * The criteria for two face geometry structs being the "same" are:
1672  * 1) The plane equations must be the same, within tolerance.
1673  * 2) All the vertices on the 2nd face must lie within the
1674  * distance tolerance of the 1st face's plane equation.
1675  */
1676 int
1677 nmg_model_face_fuse(struct model *m, const struct bn_tol *tol)
1678 {
1679  struct bu_ptbl ftab;
1680  int total = 0;
1681  register int i, j;
1682 
1683  /* Make a list of all the face structs in the model */
1684  nmg_face_tabulate(&ftab, &m->magic);
1685 
1686  for (i = BU_PTBL_END(&ftab)-1; i >= 0; i--) {
1687  register struct face *f1;
1688  register struct face_g_plane *fg1;
1689  f1 = (struct face *)BU_PTBL_GET(&ftab, i);
1690 
1691  if (*f1->g.magic_p == NMG_FACE_G_SNURB_MAGIC) {
1692  /* XXX Need routine to compare 2 snurbs for equality here */
1693  continue;
1694  }
1695 
1696  fg1 = f1->g.plane_p;
1697 
1698  for (j = i-1; j >= 0; j--) {
1699  register struct face *f2;
1700  register struct face_g_plane *fg2;
1701 
1702  f2 = (struct face *)BU_PTBL_GET(&ftab, j);
1703  fg2 = f2->g.plane_p;
1704  if (!fg2) continue;
1705 
1706  if (fg1 == fg2) continue; /* Already shared */
1707 
1708  if (nmg_two_face_fuse(f1, f2, tol) > 0)
1709  total++;
1710  }
1711  }
1712  bu_ptbl_free(&ftab);
1713  if (RTG.NMG_debug & DEBUG_BASIC && total > 0)
1714  bu_log("nmg_model_face_fuse: %d faces fused\n", total);
1715  return total;
1716 }
1717 
1718 
1719 int
1720 nmg_break_all_es_on_v(uint32_t *magic_p, struct vertex *v, const struct bn_tol *tol)
1721 {
1722  struct bu_ptbl eus;
1723  int i;
1724  int count=0;
1725  const char *magic_type;
1726 
1727  if (UNLIKELY(RTG.NMG_debug & DEBUG_BOOL)) {
1728  bu_log("nmg_break_all_es_on_v(magic=%p, v=%p)\n", (void *)magic_p, (void *)v);
1729  }
1730 
1731  magic_type = bu_identify_magic(*magic_p);
1732  if (UNLIKELY(BU_STR_EQUAL(magic_type, "NULL") ||
1733  BU_STR_EQUAL(magic_type, "Unknown_Magic"))) {
1734  bu_log("Bad magic pointer passed to nmg_break_all_es_on_v (%s)\n", magic_type);
1735  bu_bomb("Bad magic pointer passed to nmg_break_all_es_on_v()\n");
1736  }
1737 
1738  nmg_edgeuse_tabulate(&eus, magic_p);
1739 
1740  for (i = 0; i < BU_PTBL_END(&eus); i++) {
1741  struct edgeuse *eu;
1742  struct vertex *va;
1743  struct vertex *vb;
1744  fastf_t dist;
1745  int code;
1746 
1747  eu = (struct edgeuse *)BU_PTBL_GET(&eus, i);
1748 
1749  if (eu->g.magic_p && *eu->g.magic_p == NMG_EDGE_G_CNURB_MAGIC) {
1750  continue;
1751  }
1752  va = eu->vu_p->v_p;
1753  vb = eu->eumate_p->vu_p->v_p;
1754 
1755  if (va == v || bn_pt3_pt3_equal(va->vg_p->coord, v->vg_p->coord, tol)) {
1756  continue;
1757  }
1758  if (vb == v || bn_pt3_pt3_equal(vb->vg_p->coord, v->vg_p->coord, tol)) {
1759  continue;
1760  }
1761  if (UNLIKELY(va == vb || bn_pt3_pt3_equal(va->vg_p->coord, vb->vg_p->coord, tol))) {
1762  bu_bomb("nmg_break_all_es_on_v(): found zero length edgeuse");
1763  }
1764 
1765  code = bn_isect_pt_lseg(&dist, va->vg_p->coord, vb->vg_p->coord,
1766  v->vg_p->coord, tol);
1767 
1768  if (code < 1) continue; /* missed */
1769 
1770  if (UNLIKELY(code == 1 || code == 2)) {
1771  bu_bomb("nmg_break_all_es_on_v(): internal error");
1772  }
1773  /* Break edge on vertex, but don't fuse yet. */
1774 
1775  if (UNLIKELY(RTG.NMG_debug & DEBUG_BOOL)) {
1776  bu_log("\tnmg_break_all_es_on_v: breaking eu %p on v %p\n", (void *)eu, (void *)v);
1777  }
1778  (void)nmg_ebreak(v, eu);
1779  count++;
1780  }
1781  bu_ptbl_free(&eus);
1782  return count;
1783 }
1784 
1785 
1786 /**
1787  * As the first step in evaluating a boolean formula,
1788  * before starting to do face/face intersections, compare every
1789  * edge in the model with every vertex in the model.
1790  * If the vertex is within tolerance of the edge, break the edge,
1791  * and enroll the new edge on a list of edges still to be processed.
1792  *
1793  * A list of edges and a list of vertices are built, and then processed.
1794  *
1795  * Space partitioning could improve the performance of this algorithm.
1796  * For the moment, a brute-force approach is used.
1797  *
1798  * Returns -
1799  * Number of edges broken.
1800  */
1801 int
1802 nmg_break_e_on_v(const uint32_t *magic_p, const struct bn_tol *tol)
1803 {
1804  int count = 0;
1805  struct bu_ptbl verts;
1806  struct bu_ptbl edgeuses;
1807  struct bu_ptbl new_edgeuses;
1808  register struct edgeuse **eup;
1809  vect_t e_min_pt, e_max_pt;
1810 
1811  BN_CK_TOL(tol);
1812 
1813  nmg_e_and_v_tabulate(&edgeuses, &verts, magic_p);
1814 
1815  /* Repeat the process until no new edgeuses are created */
1816  while (BU_PTBL_LEN(&edgeuses) > 0) {
1817  (void)bu_ptbl_init(&new_edgeuses, 64, " &new_edgeuses");
1818 
1819  for (eup = (struct edgeuse **)BU_PTBL_LASTADDR(&edgeuses);
1820  eup >= (struct edgeuse **)BU_PTBL_BASEADDR(&edgeuses);
1821  eup--
1822  ) {
1823  register struct edgeuse *eu;
1824  register struct vertex *va;
1825  register struct vertex *vb;
1826  register struct vertex **vp;
1827 
1828  eu = *eup;
1829  if (eu->g.magic_p && *eu->g.magic_p == NMG_EDGE_G_CNURB_MAGIC)
1830  continue;
1831  va = eu->vu_p->v_p;
1832  vb = eu->eumate_p->vu_p->v_p;
1833 
1834  /* find edge bounding box */
1835  VMOVE(e_min_pt, va->vg_p->coord);
1836  VMIN(e_min_pt, vb->vg_p->coord);
1837  VMOVE(e_max_pt, va->vg_p->coord);
1838  VMAX(e_max_pt, vb->vg_p->coord);
1839 
1840  for (vp = (struct vertex **)BU_PTBL_LASTADDR(&verts);
1841  vp >= (struct vertex **)BU_PTBL_BASEADDR(&verts);
1842  vp--
1843  ) {
1844  register struct vertex *v;
1845  fastf_t dist;
1846  int code;
1847  struct edgeuse *new_eu;
1848 
1849  v = *vp;
1850  if (va == v) continue;
1851  if (vb == v) continue;
1852 
1853  if (V3PT_OUT_RPP_TOL(v->vg_p->coord, e_min_pt, e_max_pt, tol->dist)) {
1854  continue;
1855  }
1856 
1857  code = bn_isect_pt_lseg(&dist,
1858  va->vg_p->coord,
1859  vb->vg_p->coord,
1860  v->vg_p->coord, tol);
1861 
1862  if (code < 1) continue; /* missed */
1863  if (code == 1 || code == 2) {
1864  bu_log("nmg_break_e_on_v() code=%d, why wasn't this vertex fused?\n", code);
1865  continue;
1866  }
1867 
1868  if (RTG.NMG_debug & (DEBUG_BOOL|DEBUG_BASIC))
1869  bu_log("nmg_break_e_on_v(): breaking eu %p (e=%p) at vertex %p\n",
1870  (void *)eu, (void *)eu->e_p, (void *)v);
1871 
1872  /* Break edge on vertex, but don't fuse yet. */
1873  new_eu = nmg_ebreak(v, eu);
1874  /* Put new edges into follow-on list */
1875  bu_ptbl_ins(&new_edgeuses, (long *)&new_eu->l.magic);
1876 
1877  /* reset vertex vb */
1878  vb = eu->eumate_p->vu_p->v_p;
1879  count++;
1880  }
1881  }
1882  bu_ptbl_free(&edgeuses);
1883  edgeuses = new_edgeuses; /* struct copy */
1884  }
1885  bu_ptbl_free(&edgeuses);
1886  bu_ptbl_free(&verts);
1887  if (RTG.NMG_debug & (DEBUG_BOOL|DEBUG_BASIC))
1888  bu_log("nmg_break_e_on_v() broke %d edges\n", count);
1889  return count;
1890 }
1891 
1892 
1893 /* DEPRECATED: use nmg_break_e_on_v() */
1894 int
1895 nmg_model_break_e_on_v(const uint32_t *magic_p, const struct bn_tol *tol)
1896 {
1897  return nmg_break_e_on_v(magic_p, tol);
1898 }
1899 
1900 /**
1901  * This is the primary application interface to the geometry fusing support.
1902  * Fuse together all data structures that are equal to each other,
1903  * within tolerance.
1904  *
1905  * The algorithm is three part:
1906  * 1) Fuse together all vertices.
1907  * 2) Fuse together all face geometry, where appropriate.
1908  * 3) Fuse together all edges.
1909  *
1910  * Edge fusing is handled last, because the difficult part there is
1911  * sorting faces radially around the edge.
1912  * It is important to know whether faces are shared or not
1913  * at that point.
1914  *
1915  * XXX It would be more efficient to build all the ptbl's at once,
1916  * XXX with a single traversal of the model.
1917  */
1918 int
1919 nmg_model_fuse(struct model *m, const struct bn_tol *tol)
1920 {
1921  int total = 0;
1922 
1923  NMG_CK_MODEL(m);
1924  BN_CK_TOL(tol);
1925 
1926  /* XXXX vertex fusing and edge breaking can produce vertices that are
1927  * not within tolerance of their face. Edge breaking needs to be moved
1928  * to step 1.5, then a routine to make sure all vertices are within
1929  * tolerance of owning face must be called if "total" is greater than zero.
1930  * This routine may have to triangulate the face if an appropriate plane
1931  * cannot be calculated.
1932  */
1933 
1934  /* Step 1 -- the vertices. */
1935  if (RTG.NMG_debug & DEBUG_BASIC)
1936  bu_log("nmg_model_fuse: vertices\n");
1937  total += nmg_vertex_fuse(&m->magic, tol);
1938 
1939  /* Step 1.5 -- break edges on vertices, before fusing edges */
1940  if (RTG.NMG_debug & DEBUG_BASIC)
1941  bu_log("nmg_model_fuse: break edges\n");
1942  total += nmg_break_e_on_v(&m->magic, tol);
1943 
1944  if (total) {
1945  struct nmgregion *r;
1946  struct shell *s;
1947 
1948  /* vertices and/or edges have been moved,
1949  * may have created out-of-tolerance faces
1950  */
1951 
1952  for (BU_LIST_FOR(r, nmgregion, &m->r_hd)) {
1953  for (BU_LIST_FOR(s, shell, &r->s_hd))
1954  nmg_make_faces_within_tol(s, tol);
1955  }
1956  }
1957 
1958  /* Step 2 -- the face geometry */
1959  if (RTG.NMG_debug & DEBUG_BASIC)
1960  bu_log("nmg_model_fuse: faces\n");
1961  total += nmg_model_face_fuse(m, tol);
1962 
1963  /* Step 3 -- edges */
1964  if (RTG.NMG_debug & DEBUG_BASIC)
1965  bu_log("nmg_model_fuse: edges\n");
1966  total += nmg_edge_fuse(&m->magic, tol);
1967 
1968  /* Step 4 -- edge geometry */
1969  if (RTG.NMG_debug & DEBUG_BASIC)
1970  bu_log("nmg_model_fuse: edge geometries\n");
1971  total += nmg_edge_g_fuse(&m->magic, tol);
1972 
1973  if (RTG.NMG_debug & DEBUG_BASIC && total > 0)
1974  bu_log("nmg_model_fuse(): %d entities fused\n", total);
1975  return total;
1976 }
1977 
1978 
1979 /* -------------------- RADIAL -------------------- */
1980 
1981 /**
1982  * Build sorted list, with 'ang' running from zero to 2*pi.
1983  * New edgeuses with same angle as an edgeuse already on the list
1984  * are added AFTER the last existing one, for lack of any better way
1985  * to break the tie.
1986  */
1987 void
1989 {
1990  struct nmg_radial *cur;
1991  register fastf_t rad_ang;
1992 
1993  BU_CK_LIST_HEAD(hd);
1994  NMG_CK_RADIAL(rad);
1995 
1996  if (BU_LIST_IS_EMPTY(hd)) {
1997  BU_LIST_APPEND(hd, &rad->l);
1998  return;
1999  }
2000 
2001  /* Put wires at the front */
2002  if (rad->fu == (struct faceuse *)NULL) {
2003  /* Add before first element */
2004  BU_LIST_APPEND(hd, &rad->l);
2005  return;
2006  }
2007 
2008  rad_ang = rad->ang;
2009 
2010  /* Check for trivial append at end of list.
2011  * This is a very common case, when input list is sorted.
2012  */
2013  cur = BU_LIST_PREV(nmg_radial, hd);
2014  if (cur->fu && rad_ang >= cur->ang) {
2015  BU_LIST_INSERT(hd, &rad->l);
2016  return;
2017  }
2018 
2019  /* Brute force search through hd's list, going backwards */
2020  for (BU_LIST_FOR_BACKWARDS(cur, nmg_radial, hd)) {
2021  if (cur->fu == (struct faceuse *)NULL) continue;
2022  if (rad_ang >= cur->ang) {
2023  BU_LIST_APPEND(&cur->l, &rad->l);
2024  return;
2025  }
2026  }
2027 
2028  /* Add before first element */
2029  BU_LIST_APPEND(hd, &rad->l);
2030 }
2031 
2032 
2033 /**
2034  * Not only verity that list is monotone increasing, but that
2035  * pointer integrity still exists.
2036  */
2037 void
2038 nmg_radial_verify_pointers(const struct bu_list *hd, const struct bn_tol *tol)
2039 {
2040  register struct nmg_radial *rad;
2041  register fastf_t amin = -64;
2042  register struct nmg_radial *prev;
2043  register struct nmg_radial *next;
2044 
2045  BU_CK_LIST_HEAD(hd);
2046  BN_CK_TOL(tol);
2047 
2048  /* Verify pointers increasing */
2049  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2050  /* Verify pointer integrity */
2051  prev = BU_LIST_PPREV_CIRC(nmg_radial, rad);
2052  next = BU_LIST_PNEXT_CIRC(nmg_radial, rad);
2053  if (rad->eu != prev->eu->radial_p->eumate_p)
2054  bu_bomb("nmg_radial_verify_pointers() eu not radial+mate forw from prev\n");
2055  if (rad->eu->eumate_p != prev->eu->radial_p)
2056  bu_bomb("nmg_radial_verify_pointers() eumate not radial from prev\n");
2057  if (rad->eu != next->eu->eumate_p->radial_p)
2058  bu_bomb("nmg_radial_verify_pointers() eu not mate+radial back from next\n");
2059  if (rad->eu->eumate_p != next->eu->eumate_p->radial_p->eumate_p)
2060  bu_bomb("nmg_radial_verify_pointers() eumate not mate+radial+mate back from next\n");
2061 
2062  if (rad->fu == (struct faceuse *)NULL) continue;
2063  if (rad->ang < amin) {
2064  nmg_pr_radial_list(hd, tol);
2065  bu_log(" previous angle=%g > current=%g\n",
2066  amin*RAD2DEG, rad->ang*RAD2DEG);
2067  bu_bomb("nmg_radial_verify_pointers() not monotone increasing\n");
2068  }
2069  amin = rad->ang;
2070  }
2071 }
2072 
2073 
2074 /**
2075  *
2076  * Verify that the angles are monotone increasing.
2077  * Wire edgeuses are ignored.
2078  */
2079 void
2080 nmg_radial_verify_monotone(const struct bu_list *hd, const struct bn_tol *tol)
2081 {
2082  register struct nmg_radial *rad;
2083  register fastf_t amin = -64;
2084 
2085  BU_CK_LIST_HEAD(hd);
2086  BN_CK_TOL(tol);
2087 
2088  /* Verify monotone increasing */
2089  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2090  if (rad->fu == (struct faceuse *)NULL) continue;
2091  if (rad->ang < amin) {
2092  nmg_pr_radial_list(hd, tol);
2093  bu_log(" previous angle=%g > current=%g\n",
2094  amin*RAD2DEG, rad->ang*RAD2DEG);
2095  bu_bomb("nmg_radial_verify_monotone() not monotone increasing\n");
2096  }
2097  amin = rad->ang;
2098  }
2099 }
2100 
2101 
2102 /**
2103  * Check if the passed bu_list is in increasing order. If not,
2104  * reverse the order of the list.
2105  * XXX Isn't the word "ensure"?
2106  */
2107 void
2109 {
2110  struct nmg_radial *rad;
2111  fastf_t cur_value=(-MAX_FASTF);
2112  int increasing=1;
2113 
2114  BU_CK_LIST_HEAD(hd);
2115 
2116  /* if we don't have more than 3 entries, it doesn't matter */
2117 
2118  if (bu_list_len(hd) < 3)
2119  return;
2120 
2121  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2122  /* skip wire edges */
2123  if (rad->fu == (struct faceuse *)NULL)
2124  continue;
2125 
2126  /* if increasing, just keep checking */
2127  if (rad->ang >= cur_value) {
2128  cur_value = rad->ang;
2129  continue;
2130  }
2131 
2132  /* angle decreases, is it going from max to min?? */
2133  if (ZERO(rad->ang - amin) && ZERO(cur_value - amax)) {
2134  /* O.K., just went from max to min */
2135  cur_value = rad->ang;
2136  continue;
2137  }
2138 
2139  /* if we get here, this list is not increasing!!! */
2140  increasing = 0;
2141  break;
2142  }
2143 
2144  if (increasing) /* all is well */
2145  return;
2146 
2147  /* reverse order of the list */
2148  bu_list_reverse(hd);
2149 
2150  /* Need to exchange eu with eu->eumate_p for each eu on the list */
2151  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2152  rad->eu = rad->eu->eumate_p;
2153  rad->fu = nmg_find_fu_of_eu(rad->eu);
2154  }
2155 }
2156 
2157 
2158 /**
2159  * The coordinate system is expected to have been chosen in such a
2160  * way that the radial list of faces around this edge are circularly
2161  * increasing (CCW) in their angle. Put them in the list in exactly
2162  * the order they occur around the edge. Then, at the end, move the
2163  * list head to lie between the maximum and minimum angles, so that the
2164  * list head is crossed as the angle goes around through zero.
2165  * Now the list is monotone increasing.
2166  *
2167  * The edgeuse's radial pointer takes us in the CCW direction.
2168  *
2169  * If the list contains nmg_radial structures r1, r2, r3, r4,
2170  * then going CCW around the edge we will encounter:
2171  *
2172  * (from i-1) (from i+1)
2173  * r1->eu->eumate_p r4->eu->radial_p r2->eu->eumate_p->radial_p->eumate_p
2174  * r1->eu r4->eu->radial_p->eumate_p r2->eu->eumate_p->radial_p
2175  * r2->eu->eumate_p r1->eu->radial_p r3->eu->eumate_p->radial_p->eumate_p
2176  * r2->eu r1->eu->radial_p->eumate_p r3->eu->eumate_p->radial_p
2177  * r3->eu->eumate_p r2->eu->radial_p r4->eu->eumate_p->radial_p->eumate_p
2178  * r3->eu r2->eu->radial_p->eumate_p r4->eu->eumate_p->radial_p
2179  * r4->eu->eumate_p r3->eu->radial_p r1->eu->eumate_p->radial_p->eumate_p
2180  * r4->eu r3->eu->radial_p->eumate_p r1->eu->eumate_p->radial_p
2181  */
2182 void
2183 nmg_radial_build_list(struct bu_list *hd, struct bu_ptbl *shell_tbl, int existing, struct edgeuse *eu, const fastf_t *xvec, const fastf_t *yvec, const fastf_t *zvec, const struct bn_tol *tol)
2184 
2185 /* may be null */
2186 
2187 
2188 /* for printing */
2189 {
2190  struct edgeuse *teu;
2191  struct nmg_radial *rad;
2192  fastf_t amin;
2193  fastf_t amax;
2194  int non_wire_edges=0;
2195  struct nmg_radial *rmin = (struct nmg_radial *)NULL;
2196  struct nmg_radial *rmax = (struct nmg_radial *)NULL;
2197  struct nmg_radial *first;
2198 
2199  BU_CK_LIST_HEAD(hd);
2200  if (shell_tbl) BU_CK_PTBL(shell_tbl);
2201  NMG_CK_EDGEUSE(eu);
2202  BN_CK_TOL(tol);
2203 
2204  if (RTG.NMG_debug & DEBUG_BASIC || RTG.NMG_debug & DEBUG_MESH_EU)
2205  bu_log("nmg_radial_build_list(existing=%d, eu=%p)\n", existing, (void *)eu);
2206 
2207  if (ZERO(MAGSQ(xvec)) || ZERO(MAGSQ(yvec)) || ZERO(MAGSQ(zvec))) {
2208  bu_log("nmg_radial_build_list(): one or more input vector(s) 'xvec', 'yvec', 'zvec' is zero magnitude.\n");
2209  }
2210 
2211  amin = 64;
2212  amax = -64;
2213 
2214  teu = eu;
2215  for (;;) {
2216  BU_GET(rad, struct nmg_radial);
2217  rad->l.magic = NMG_RADIAL_MAGIC;
2218  rad->eu = teu;
2219  rad->fu = nmg_find_fu_of_eu(teu);
2220  if (rad->fu) {
2221  /* We depend on ang being strictly in the range 0..2pi */
2222  rad->ang = nmg_measure_fu_angle(teu, xvec, yvec, zvec);
2223 
2224  if (rad->ang < -SMALL_FASTF) {
2225  bu_bomb("nmg_radial_build_list(): fu_angle should not be negative\n");
2226  }
2227  if (rad->ang > (M_2PI + SMALL_FASTF)) {
2228  bu_bomb("nmg_radial_build_list(): fu_angle should not be > 2pi\n");
2229  }
2230 
2231  non_wire_edges++;
2232 
2233  if ((rad->ang < amin) || (ZERO(rad->ang - amin))) {
2234  amin = rad->ang;
2235  rmin = rad;
2236  }
2237 
2238  if ((rad->ang > amax) || (ZERO(rad->ang - amax))) {
2239  amax = rad->ang;
2240  rmax = rad;
2241  }
2242  } else {
2243  /* Wire edge. Set a preposterous angle */
2244  rad->ang = -M_PI; /* -180 */
2245  }
2246  rad->s = nmg_find_s_of_eu(teu);
2247  rad->existing_flag = existing;
2248  rad->needs_flip = 0; /* not yet determined */
2249  rad->is_crack = 0; /* not yet determined */
2250  rad->is_outie = 0; /* not yet determined */
2251 
2252  if (RTG.NMG_debug & DEBUG_MESH_EU)
2253  bu_log("\trad->eu = %p, rad->ang = %g\n", (void *)rad->eu, rad->ang);
2254 
2255  /* the radial list is not always sorted */
2257 
2258  /* Add to list of all shells involved at this edge */
2259  if (shell_tbl) bu_ptbl_ins_unique(shell_tbl, (long *)&(rad->s->l.magic));
2260 
2261  /* Advance to next edgeuse pair */
2262  teu = teu->radial_p->eumate_p;
2263  if (teu == eu) break;
2264  }
2265 
2266  /* Increasing, with min or max value possibly repeated */
2267  if (!rmin) {
2268  /* Nothing but wire edgeuses, done. */
2269  return;
2270  }
2271 
2272  /* At least one non-wire edgeuse was found */
2273  if (non_wire_edges < 2) {
2274  /* only one non wire entry in list */
2275  return;
2276  }
2277 
2278  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2279  struct nmg_radial *next;
2280 
2281  bu_log("amin=%g min_eu=%p, amax=%g max_eu=%p\n",
2282  rmin->ang * RAD2DEG, (void *)rmin->eu,
2283  rmax->ang * RAD2DEG, (void *)rmax->eu);
2284 
2285  for (BU_LIST_FOR(next, nmg_radial, hd))
2286  bu_log("%p: eu=%p, fu=%p, ang=%g\n", (void *)next, (void *)next->eu, (void *)next->fu, next->ang);
2287  }
2288 
2289  /* Skip to extremal repeated max&min. Ignore wires */
2290  first = rmax;
2291  for (;;) {
2292  struct nmg_radial *next;
2293  next = rmax;
2294  do {
2295  next = BU_LIST_PNEXT_CIRC(nmg_radial, next);
2296  } while (next->fu == (struct faceuse *)NULL);
2297 
2298  if ((next->ang > amax) || (ZERO(next->ang - amax))) {
2299  rmax = next; /* a repeated max */
2300  if (rmax == first) /* we have gone all the way around (All angles are same) */
2301  break;
2302  } else
2303  break;
2304  }
2305  /* wires before min establish new rmin */
2306  first = rmin;
2307  for (;;) {
2308  struct nmg_radial *next;
2309 
2310  while ((next = BU_LIST_PPREV_CIRC(nmg_radial, rmin))->fu == (struct faceuse *)NULL)
2311  rmin = next;
2312  next = BU_LIST_PPREV_CIRC(nmg_radial, rmin);
2313  if ((next->ang < amin) || (ZERO(next->ang - amin))) {
2314  rmin = next; /* a repeated min */
2315  if (rmin == first) {
2316  /* all the way round again (All angles are same) */
2317  /* set rmin to next entry after rmax */
2318  rmin = BU_LIST_PNEXT_CIRC(nmg_radial, rmax);
2319  break;
2320  }
2321  } else
2322  break;
2323  }
2324 
2325  /* Move list head so that it is in between min and max entries. */
2326  if (BU_LIST_PNEXT_CIRC(nmg_radial, rmax) == rmin) {
2327  /* Maximum entry is followed by minimum. Ascending --> CCW */
2328  BU_LIST_DEQUEUE(hd);
2329  /* Append head after maximum, before minimum */
2330  BU_LIST_APPEND(&(rmax->l), hd);
2331  } else {
2332  bu_log(" %f %f %f --- %f %f %f\n",
2333  V3ARGS(eu->vu_p->v_p->vg_p->coord),
2334  V3ARGS(eu->eumate_p->vu_p->v_p->vg_p->coord));
2335  bu_log("amin=%g min_eu=%p, amax=%g max_eu=%p B\n",
2336  rmin->ang * RAD2DEG, (void *)rmin->eu,
2337  rmax->ang * RAD2DEG, (void *)rmax->eu);
2338  nmg_pr_radial_list(hd, tol);
2339  nmg_pr_fu_around_eu_vecs(eu, xvec, yvec, zvec, tol);
2340  bu_bomb("nmg_radial_build_list() min and max angle not adjacent in list (or list not monotone increasing)\n");
2341  }
2342 }
2343 
2344 
2345 /**
2346  * Merge all of the src list into the dest list, sorting by angles.
2347  */
2348 void
2349 nmg_radial_merge_lists(struct bu_list *dest, struct bu_list *src, const struct bn_tol *tol)
2350 {
2351  struct nmg_radial *rad;
2352 
2353  BU_CK_LIST_HEAD(dest);
2354  BU_CK_LIST_HEAD(src);
2355  BN_CK_TOL(tol);
2356 
2357  while (BU_LIST_WHILE(rad, nmg_radial, src)) {
2358  BU_LIST_DEQUEUE(&rad->l);
2359  nmg_radial_sorted_list_insert(dest, rad);
2360  }
2361 }
2362 
2363 
2364 /**
2365  * If there is more than one edgeuse of a loopuse along an edge, then
2366  * it is a "topological crack". There are two kinds, an "innie",
2367  * where the crack is a null-area incursion into the interior of the
2368  * loop, and an "outie", where the crack is a null-area protrusion
2369  * outside of the interior of the loop.
2370  *
2371  * "Outie" "Innie"
2372  * *-------* *-------*
2373  * | ^ | ^
2374  * v | v |
2375  * *<------* | *--->* |
2376  * *---M-->* | *<-M-* |
2377  * | | | |
2378  * v | v |
2379  * *------>* *------>*
2380  *
2381  * The algorithm used is to compute the geometric midpoint of the
2382  * crack edge, "delete" that edge from the loop, and then classify the
2383  * midpoint ("M") against the remainder of the loop. If the edge
2384  * midpoint is inside the remains of the loop, then the crack is an
2385  * "innie", otherwise it is an "outie".
2386  *
2387  * When there are an odd number of edgeuses along the crack, then the
2388  * situation is "nasty":
2389  *
2390  * "Nasty"
2391  * *-------*
2392  * | ^
2393  * v |
2394  * *<------* |
2395  * *------>* |
2396  * *<------* |
2397  * *------>* |
2398  * *<------* |
2399  * | |
2400  * | |
2401  * v |
2402  * *------------->*
2403  *
2404  * The caller is responsible for making sure that the edgeuse is not a
2405  * wire edgeuse (i.e. that the edgeuse is part of a loop).
2406  *
2407  * In the "Nasty" case, all the edgeuse pairs are "outies" except for
2408  * the last lone edgeuse, which should be handled as a "non-crack".
2409  * Walk the loopuse's edgeuses list in edgeuse order to see which one
2410  * is the last (non-crack) repeated edgeuse. For efficiency,
2411  * detecting and dealing with this condition is left up to the caller,
2412  * and is not checked for here.
2413  */
2414 int
2415 nmg_is_crack_outie(const struct edgeuse *eu, const struct bn_tol *tol)
2416 {
2417  const struct loopuse *lu;
2418  const struct edge *e;
2419  point_t midpt;
2420  const fastf_t *a, *b;
2421  int nmg_class;
2422 
2423  NMG_CK_EDGEUSE(eu);
2424  BN_CK_TOL(tol);
2425 
2426  lu = eu->up.lu_p;
2427  NMG_CK_LOOPUSE(lu);
2428  e = eu->e_p;
2429  NMG_CK_EDGE(e);
2430 
2431  /* If ENTIRE loop is a crack, there is no surface area, it's an outie */
2432  if (nmg_loop_is_a_crack(lu)) return 1;
2433 
2434  a = eu->vu_p->v_p->vg_p->coord;
2435  b = eu->eumate_p->vu_p->v_p->vg_p->coord;
2436  VADD2SCALE(midpt, a, b, 0.5);
2437 
2438  /* Ensure edge is long enough so midpoint is not within tol of verts */
2439  {
2440  /* all we want here is a classification of the midpoint,
2441  * so let's create a temporary tolerance that will work!!! */
2442 
2443  struct bn_tol tmp_tol;
2444  struct faceuse *fu;
2445  plane_t pl;
2446  fastf_t dist;
2447 
2448  tmp_tol = (*tol);
2449  if (*lu->up.magic_p != NMG_FACEUSE_MAGIC)
2450  bu_bomb("Nmg_is_crack_outie called with non-face loop");
2451 
2452  fu = lu->up.fu_p;
2453  NMG_CK_FACEUSE(fu);
2454  NMG_GET_FU_PLANE(pl, fu);
2455  dist = DIST_PT_PLANE(midpt, pl);
2456  VJOIN1(midpt, midpt, -dist, pl);
2457  dist = fabs(DIST_PT_PLANE(midpt, pl));
2458  if (dist > SMALL_FASTF) {
2459  tmp_tol.dist = dist*2.0;
2460  tmp_tol.dist_sq = tmp_tol.dist * tmp_tol.dist;
2461  } else {
2462  tmp_tol.dist = SMALL_FASTF;
2463  tmp_tol.dist_sq = SMALL_FASTF * SMALL_FASTF;
2464  }
2465  nmg_class = nmg_class_pt_lu_except(midpt, lu, e, &tmp_tol);
2466  }
2467  if (RTG.NMG_debug & DEBUG_BASIC) {
2468  bu_log("nmg_is_crack_outie(eu=%p) lu=%p, e=%p, nmg_class=%s\n",
2469  (void *)eu, (void *)lu, (void *)e, nmg_class_name(nmg_class));
2470  }
2471 
2472  if (lu->orientation == OT_SAME) {
2473  if (nmg_class == NMG_CLASS_AinB || nmg_class == NMG_CLASS_AonBshared)
2474  return 0; /* an "innie" */
2475  if (nmg_class == NMG_CLASS_AoutB)
2476  return 1; /* an "outie" */
2477  } else {
2478  /* It's a hole loop, things work backwards. */
2479  if (nmg_class == NMG_CLASS_AinB || nmg_class == NMG_CLASS_AonBshared)
2480  return 1; /* an "outie" */
2481  if (nmg_class == NMG_CLASS_AoutB)
2482  return 0; /* an "innie" */
2483  }
2484 
2485  /* Other classifications "shouldn't happen". */
2486  bu_log("nmg_is_crack_outie(eu=%p), lu=%p(%s)\n midpt_class=%s, midpt=(%g, %g, %g)\n",
2487  (void *)eu,
2488  (void *)lu, nmg_orientation(lu->orientation),
2489  nmg_class_name(nmg_class),
2490  V3ARGS(midpt));
2491  nmg_pr_lu_briefly(lu, 0);
2492  bu_bomb("nmg_is_crack_outie() got unexpected midpt classification from nmg_class_pt_lu_except()\n");
2493 
2494  return -1; /* make the compiler happy */
2495 }
2496 
2497 
2498 struct nmg_radial *
2499 nmg_find_radial_eu(const struct bu_list *hd, const struct edgeuse *eu)
2500 {
2501  register struct nmg_radial *rad;
2502 
2503  BU_CK_LIST_HEAD(hd);
2504  NMG_CK_EDGEUSE(eu);
2505 
2506  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2507  if (rad->eu == eu) return rad;
2508  if (rad->eu->eumate_p == eu) return rad;
2509  }
2510  bu_log("nmg_find_radial_eu() eu=%p\n", (void *)eu);
2511  bu_bomb("nmg_find_radial_eu() given edgeuse not found on list\n");
2512 
2513  return (struct nmg_radial *)NULL;
2514 }
2515 
2516 
2517 /**
2518  * Find the next use of either of two edges in the loopuse.
2519  * The second edge pointer may be NULL.
2520  */
2521 const struct edgeuse *
2522 nmg_find_next_use_of_2e_in_lu(const struct edgeuse *eu, const struct edge *e1, const struct edge *e2)
2523 
2524 
2525 /* may be NULL */
2526 {
2527  register const struct edgeuse *neu;
2528 
2529  NMG_CK_EDGEUSE(eu);
2530  NMG_CK_LOOPUSE(eu->up.lu_p); /* sanity */
2531  NMG_CK_EDGE(e1);
2532  if (e2) NMG_CK_EDGE(e2);
2533 
2534  neu = eu;
2535  do {
2536  neu = BU_LIST_PNEXT_CIRC(edgeuse, &neu->l);
2537  } while (neu->e_p != e1 && neu->e_p != e2);
2538  return neu;
2539 
2540 }
2541 
2542 
2543 /**
2544  * For every edgeuse, if there are other edgeuses around this edge
2545  * from the same face, then mark them all as part of a "crack".
2546  *
2547  * To be a crack the two edgeuses must be from the same loopuse.
2548  *
2549  * If the count of repeated ("crack") edgeuses is even, then
2550  * classify the entire crack as an "innie" or an "outie".
2551  * If the count is odd, this is a "Nasty" --
2552  * all but one edgeuse are marked as "outies",
2553  * and the remaining one is marked as a non-crack.
2554  * The "outie" edgeuses are marked off in pairs,
2555  * in the loopuse's edgeuse order.
2556  */
2557 void
2558 nmg_radial_mark_cracks(struct bu_list *hd, const struct edge *e1, const struct edge *e2, const struct bn_tol *tol)
2559 
2560 
2561 /* may be NULL */
2562 
2563 {
2564  struct nmg_radial *rad;
2565  struct nmg_radial *other;
2566  const struct loopuse *lu;
2567  const struct edgeuse *eu;
2568  register int uses;
2569  int outie = -1;
2570 
2571  BU_CK_LIST_HEAD(hd);
2572  NMG_CK_EDGE(e1);
2573  if (e2) NMG_CK_EDGE(e2);
2574  BN_CK_TOL(tol);
2575 
2576  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2577  NMG_CK_RADIAL(rad);
2578  if (rad->is_crack) continue;
2579  if (!rad->fu) continue; /* skip wire edges */
2580  lu = rad->eu->up.lu_p;
2581  uses = 0;
2582 
2583  /* Search the remainder of the list for other uses */
2584  for (other = BU_LIST_PNEXT(nmg_radial, rad);
2585  BU_LIST_NOT_HEAD(other, hd);
2586  other = BU_LIST_PNEXT(nmg_radial, other)
2587  ) {
2588  if (!other->fu) continue; /* skip wire edges */
2589  /* Only consider edgeuses from the same loopuse */
2590  if (other->eu->up.lu_p != lu &&
2591  other->eu->eumate_p->up.lu_p != lu)
2592  continue;
2593  uses++;
2594  }
2595  if (uses <= 0) {
2596  /* The main search continues to end of list */
2597  continue; /* not a crack */
2598  }
2599  uses++; /* account for first use too */
2600 
2601  /* OK, we have a crack. Which kind? */
2602  if ((uses & 1) == 0) {
2603  /* Even number of edgeuses. */
2604  outie = nmg_is_crack_outie(rad->eu, tol);
2605  rad->is_crack = 1;
2606  rad->is_outie = outie;
2607  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2608  bu_log("nmg_radial_mark_cracks() EVEN crack eu=%p, uses=%d, outie=%d\n",
2609  (void *)rad->eu, uses, outie);
2610  }
2611  /* Mark all the rest of them the same way */
2612  for (other = BU_LIST_PNEXT(nmg_radial, rad);
2613  BU_LIST_NOT_HEAD(other, hd);
2614  other = BU_LIST_PNEXT(nmg_radial, other)
2615  ) {
2616  if (!other->fu) continue; /* skip wire edges */
2617  /* Only consider edgeuses from the same loopuse */
2618  if (other->eu->up.lu_p != lu &&
2619  other->eu->eumate_p->up.lu_p != lu)
2620  continue;
2621  other->is_crack = 1;
2622  other->is_outie = outie;
2623  }
2624  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2625  bu_log("Printing loopuse and resulting radial list:\n");
2626  nmg_pr_lu_briefly(lu, 0);
2627  nmg_pr_radial_list(hd, tol);
2628  }
2629  continue;
2630  }
2631  /*
2632  * Odd number of edgeuses. Traverse in loopuse order.
2633  * All but the last one are "outies", last one is "innie"
2634  */
2635  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2636  bu_log("nmg_radial_mark_cracks() ODD crack eu=%p, uses=%d, outie=%d\n",
2637  (void *)rad->eu, uses, outie);
2638  }
2639  /* Mark off pairs of edgeuses, one per trip through loop. */
2640  eu = rad->eu;
2641  for (; uses >= 2; uses--) {
2642  eu = nmg_find_next_use_of_2e_in_lu(eu, e1, e2);
2643  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2644  bu_log("rad->eu=%p, eu=%p, uses=%d\n",
2645  (void *)rad->eu, (void *)eu, uses);
2646  }
2647  if (eu == rad->eu) {
2648  nmg_pr_lu_briefly(lu, 0);
2649  nmg_pr_radial_list(hd, tol);
2650  bu_bomb("nmg_radial_mark_cracks() loop too short!\n");
2651  }
2652 
2653  other = nmg_find_radial_eu(hd, eu);
2654  /* Mark 'em as "outies" */
2655  other->is_crack = 1;
2656  other->is_outie = 1;
2657  }
2658 
2659  /* Should only be one left, this one is an "innie": it borders surface area */
2660  eu = nmg_find_next_use_of_2e_in_lu(eu, e1, e2);
2661  if (eu != rad->eu) {
2662  nmg_pr_lu_briefly(lu, 0);
2663  nmg_pr_radial_list(hd, tol);
2664  bu_bomb("nmg_radial_mark_cracks() loop didn't return to start\n");
2665  }
2666 
2667  rad->is_crack = 1;
2668  rad->is_outie = 0; /* "innie" */
2669  }
2670 }
2671 
2672 
2673 /**
2674  * Returns -
2675  * NULL No edgeuses from indicated shell on this list
2676  * nmg_radial* An original, else first newbie, else a newbie crack.
2677  */
2678 struct nmg_radial *
2679 nmg_radial_find_an_original(const struct bu_list *hd, const struct shell *s, const struct bn_tol *tol)
2680 {
2681  register struct nmg_radial *rad;
2682  struct nmg_radial *fallback = (struct nmg_radial *)NULL;
2683  int seen_shell = 0;
2684 
2685  BU_CK_LIST_HEAD(hd);
2686  NMG_CK_SHELL(s);
2687 
2688  /* First choice: find an original, non-crack, non-wire */
2689  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2690  NMG_CK_RADIAL(rad);
2691  if (rad->s != s) continue;
2692  seen_shell++;
2693  if (rad->is_outie) {
2694  fallback = rad;
2695  continue; /* skip "outie" cracks */
2696  }
2697  if (!rad->fu) continue; /* skip wires */
2698  if (rad->existing_flag) return rad;
2699  }
2700  if (!seen_shell) return (struct nmg_radial *)NULL; /* No edgeuses from that shell, at all! */
2701 
2702  /* Next, an original crack would be OK */
2703  if (fallback) return fallback;
2704 
2705  /* If there were no originals, find first newbie */
2706  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2707  if (rad->s != s) continue;
2708  if (rad->is_outie) {
2709  fallback = rad;
2710  continue; /* skip "outie" cracks */
2711  }
2712  if (!rad->fu) {
2713  continue; /* skip wires */
2714  }
2715  return rad;
2716  }
2717  /* If no ordinary newbies, provide a newbie crack */
2718  if (fallback) return fallback;
2719 
2720  /* No ordinary newbiew or newbie cracks, any wires? */
2721  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2722  if (rad->s != s) continue;
2723  if (rad->is_outie) {
2724  continue; /* skip "outie" cracks */
2725  }
2726  if (!rad->fu) {
2727  fallback = rad;
2728  continue; /* skip wires */
2729  }
2730  return rad;
2731  }
2732  if (fallback) return fallback;
2733 
2734  bu_log("nmg_radial_find_an_original() shell=%p\n", (void *)s);
2735  nmg_pr_radial_list(hd, tol);
2736  bu_bomb("nmg_radial_find_an_original() No entries from indicated shell\n");
2737 
2738  return (struct nmg_radial *)NULL;
2739 }
2740 
2741 
2742 /**
2743  * For a given shell, find an original edgeuse from that shell,
2744  * and then mark parity violators with a "flip" flag.
2745  */
2746 int
2747 nmg_radial_mark_flips(struct bu_list *hd, const struct shell *s, const struct bn_tol *tol)
2748 {
2749  struct nmg_radial *rad;
2750  struct nmg_radial *orig;
2751  register int expected_ot;
2752  int count = 0;
2753  int nflip = 0;
2754 
2755  BU_CK_LIST_HEAD(hd);
2756  NMG_CK_SHELL(s);
2757  BN_CK_TOL(tol);
2758 
2759  orig = nmg_radial_find_an_original(hd, s, tol);
2760  NMG_CK_RADIAL(orig);
2761  if (orig->is_outie) {
2762  /* Only originals were "outie" cracks. No flipping */
2763  return 0;
2764  }
2765 
2766  if (!orig->fu) {
2767  /* nothing but wires */
2768  return 0;
2769  }
2770  if (!orig->existing_flag) {
2771  /* There were no originals. Do something sensible to check the newbies */
2772  if (!orig->fu) {
2773  /* Nothing but wires */
2774  return 0;
2775  }
2776  }
2777 
2778  expected_ot = !(orig->fu->orientation == OT_SAME);
2779  if (!orig->is_outie) count++; /* Don't count orig if "outie" crack */
2780 
2781  for (BU_LIST_FOR_CIRC(rad, nmg_radial, orig)) {
2782  if (rad->s != s) continue;
2783  if (!rad->fu) continue; /* skip wires */
2784  if (rad->is_outie) continue; /* skip "outie" cracks */
2785  count++;
2786  if (expected_ot == (rad->fu->orientation == OT_SAME)) {
2787  expected_ot = !expected_ot;
2788  continue;
2789  }
2790  /* Mis-match detected */
2791  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2792  bu_log("nmg_radial_mark_flips() Mis-match detected, setting flip flag eu=%p\n", (void *)rad->eu);
2793  }
2794  rad->needs_flip = !rad->needs_flip;
2795  nflip++;
2796  /* With this one flipped, set expectation for next */
2797  expected_ot = !expected_ot;
2798  }
2799 
2800  if (count & 1) {
2801  return count;
2802  }
2803 
2804  if (expected_ot == (orig->fu->orientation == OT_SAME))
2805  return nflip;
2806 
2807  bu_log("nmg_radial_mark_flips() unable to establish proper orientation parity.\n eu count=%d, shell=%p, expectation=%d\n",
2808  count, (void *)s, expected_ot);
2809  nmg_pr_radial_list(hd, tol);
2810  bu_bomb("nmg_radial_mark_flips() unable to establish proper orientation parity.\n");
2811 
2812  return 0; /* for compiler */
2813 }
2814 
2815 
2816 /**
2817  * For each shell, check orientation parity of edgeuses within that shell.
2818  */
2819 int
2820 nmg_radial_check_parity(const struct bu_list *hd, const struct bu_ptbl *shells, const struct bn_tol *tol)
2821 {
2822  struct nmg_radial *rad;
2823  struct shell **sp;
2824  struct nmg_radial *orig;
2825  register int expected_ot;
2826  int count = 0;
2827 
2828  BU_CK_LIST_HEAD(hd);
2829  BU_CK_PTBL(shells);
2830  BN_CK_TOL(tol);
2831 
2832  for (sp = (struct shell **)BU_PTBL_LASTADDR(shells);
2833  sp >= (struct shell **)BU_PTBL_BASEADDR(shells); sp--
2834  ) {
2835 
2836  NMG_CK_SHELL(*sp);
2837  orig = nmg_radial_find_an_original(hd, *sp, tol);
2838  if (!orig) continue;
2839  NMG_CK_RADIAL(orig);
2840  if (!orig->existing_flag) {
2841  /* There were no originals. Do something sensible to check the newbies */
2842  if (!orig->fu) continue; /* Nothing but wires */
2843  }
2844  if (orig->is_outie) continue; /* Loop was nothing but outies */
2845  expected_ot = !(orig->fu->orientation == OT_SAME);
2846 
2847  for (BU_LIST_FOR_CIRC(rad, nmg_radial, orig)) {
2848  if (rad->s != *sp) continue;
2849  if (!rad->fu) continue; /* skip wires */
2850  if (rad->is_outie) continue; /* skip "outie" cracks */
2851  if (expected_ot == (rad->fu->orientation == OT_SAME)) {
2852  expected_ot = !expected_ot;
2853  continue;
2854  }
2855  /* Mis-match detected */
2856  bu_log("nmg_radial_check_parity() bad parity eu=%p, s=%p\n",
2857  (void *)rad->eu, (void *)*sp);
2858  count++;
2859  /* Set expectation for next */
2860  expected_ot = !expected_ot;
2861  }
2862  if (expected_ot == (orig->fu->orientation == OT_SAME))
2863  continue;
2864  bu_log("nmg_radial_check_parity() bad parity at END eu=%p, s=%p\n",
2865  (void *)rad->eu, (void *)*sp);
2866  count++;
2867  }
2868  return count;
2869 }
2870 
2871 
2872 /**
2873  * For all non-original edgeuses in the list, place them in the proper
2874  * place around the destination edge.
2875  */
2876 void
2877 nmg_radial_implement_decisions(struct bu_list *hd, const struct bn_tol *tol, struct edgeuse *eu1, fastf_t *xvec, fastf_t *yvec, fastf_t *zvec)
2878 
2879 /* for printing */
2880 /* temp */
2881 /*** temp ***/
2882 {
2883  struct nmg_radial *rad;
2884  struct nmg_radial *prev;
2885  int skipped;
2886 
2887  BU_CK_LIST_HEAD(hd);
2888  BN_CK_TOL(tol);
2889 
2890  if (RTG.NMG_debug & DEBUG_BASIC)
2891  bu_log("nmg_radial_implement_decisions() BEGIN\n");
2892 
2893 again:
2894  skipped = 0;
2895  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2896  struct edgeuse *dest;
2897 
2898  if (rad->existing_flag) continue;
2899  prev = BU_LIST_PPREV_CIRC(nmg_radial, rad);
2900  if (!prev->existing_flag) {
2901  /* Previous eu isn't in place yet, can't do this one until next pass. */
2902  skipped++;
2903  continue;
2904  }
2905 
2906  /*
2907  * Insert "rad" CCW radial from "prev".
2908  *
2909  */
2910  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2911  bu_log("Before -- ");
2912  nmg_pr_fu_around_eu_vecs(eu1, xvec, yvec, zvec, tol);
2913  nmg_pr_radial("prev:", (const struct nmg_radial *)prev);
2914  nmg_pr_radial(" rad:", (const struct nmg_radial *)rad);
2915  }
2916  dest = prev->eu;
2917  if (rad->needs_flip) {
2918  struct edgeuse *other_eu = rad->eu->eumate_p;
2919 
2920  nmg_je(dest, rad->eu);
2921  rad->eu = other_eu;
2922  rad->fu = nmg_find_fu_of_eu(other_eu);
2923  rad->needs_flip = 0;
2924  } else {
2925  nmg_je(dest, rad->eu->eumate_p);
2926  }
2927  rad->existing_flag = 1;
2928  if (RTG.NMG_debug & DEBUG_MESH_EU) {
2929  bu_log("After -- ");
2930  nmg_pr_fu_around_eu_vecs(eu1, xvec, yvec, zvec, tol);
2931  }
2932  }
2933  if (skipped) {
2934  if (RTG.NMG_debug & DEBUG_BASIC)
2935  bu_log("nmg_radial_implement_decisions() %d remaining, go again\n", skipped);
2936  goto again;
2937  }
2938 
2939  if (RTG.NMG_debug & DEBUG_BASIC)
2940  bu_log("nmg_radial_implement_decisions() END\n");
2941 }
2942 
2943 
2944 void
2945 nmg_pr_radial(const char *title, const struct nmg_radial *rad)
2946 {
2947  struct face *f;
2948  int orient;
2949 
2950  NMG_CK_RADIAL(rad);
2951  if (!rad->fu) {
2952  f = (struct face *)NULL;
2953  orient = 'W';
2954  } else {
2955  f = rad->fu->f_p;
2956  orient = nmg_orientation(rad->fu->orientation)[3];
2957  }
2958  bu_log("%s%p, mate of \\/\n",
2959  title,
2960  (void *)rad->eu->eumate_p
2961  );
2962  bu_log("%s%p, f=%p, fu=%p=%c, s=%p %s %c%c%c %g deg\n",
2963  title,
2964  (void *)rad->eu,
2965  (void *)f, (void *)rad->fu, orient,
2966  (void *)rad->s,
2967  rad->existing_flag ? "old" : "new",
2968  rad->needs_flip ? 'F' : '/',
2969  rad->is_crack ? 'C' : '/',
2970  rad->is_outie ? 'O' : (rad->is_crack ? 'I' : '/'),
2971  rad->ang * RAD2DEG
2972  );
2973 }
2974 
2975 
2976 /**
2977  * Patterned after nmg_pr_fu_around_eu_vecs(), with similar format.
2978  */
2979 void
2980 nmg_pr_radial_list(const struct bu_list *hd, const struct bn_tol *tol)
2981 
2982 /* for printing */
2983 {
2984  struct nmg_radial *rad;
2985 
2986  BU_CK_LIST_HEAD(hd);
2987  BN_CK_TOL(tol);
2988 
2989  bu_log("nmg_pr_radial_list(hd=%p)\n", (void *)hd);
2990 
2991  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
2992  NMG_CK_RADIAL(rad);
2993  nmg_pr_radial(" ", rad);
2994  }
2995 }
2996 
2997 
2998 /**
2999  * This routine looks for nmg_radial structures with the same angle,
3000  * and sorts them to match the order of nmg_radial structures that
3001  * are not at that same angle
3002  */
3003 void
3005 {
3006  struct nmg_radial *start_same;
3007  struct bn_tol tol;
3008 
3009  tol.magic = BN_TOL_MAGIC;
3010  tol.dist = 0.0005;
3011  tol.dist_sq = tol.dist * tol.dist;
3012  tol.perp = 1e-6;
3013  tol.para = 1 - tol.perp;
3014 
3015  BU_CK_LIST_HEAD(hd);
3016 
3017  start_same = BU_LIST_FIRST(nmg_radial, hd);
3018  while (BU_LIST_NOT_HEAD(&start_same->l, hd)) {
3019  struct nmg_radial *next_after_same;
3020  struct nmg_radial *end_same;
3021  struct nmg_radial *same;
3022  struct nmg_radial *check;
3023 
3024  if (!start_same->fu) {
3025  start_same = BU_LIST_PNEXT(nmg_radial, &start_same->l);
3026  continue;
3027  }
3028 
3029  end_same = BU_LIST_PNEXT_CIRC(nmg_radial, &start_same->l);
3030  while ((ZERO(end_same->ang - start_same->ang) && !ZERO(end_same - start_same))
3031  || !end_same->fu)
3032  end_same = BU_LIST_PNEXT_CIRC(nmg_radial, &end_same->l);
3033  end_same = BU_LIST_PPREV_CIRC(nmg_radial, &end_same->l);
3034 
3035  if (start_same == end_same) {
3036  start_same = BU_LIST_PNEXT(nmg_radial, &start_same->l);
3037  continue;
3038  }
3039 
3040  /* more than one eu at same angle, sort them according to shell */
3041  next_after_same = BU_LIST_PNEXT_CIRC(nmg_radial, &end_same->l);
3042  while (!next_after_same->fu && next_after_same != start_same)
3043  next_after_same = BU_LIST_PNEXT_CIRC(nmg_radial, &next_after_same->l);
3044 
3045  if (next_after_same == start_same) {
3046  /* no other radials with faces */
3047  return;
3048  }
3049 
3050  check = next_after_same;
3051  while (start_same != end_same && check != start_same) {
3052  same = end_same;
3053  while (same->s != check->s && same != start_same)
3054  same = BU_LIST_PPREV_CIRC(nmg_radial, &same->l);
3055 
3056  if (same->s != check->s) {
3057  /* couldn't find any other radial from shell "same->s"
3058  * so put look at next radial
3059  */
3060 
3061  check = BU_LIST_PNEXT_CIRC(nmg_radial, &check->l);
3062  continue;
3063  }
3064 
3065  /* same->s matches check->s, so move "same" to right after end_same */
3066  if (same == start_same) {
3067  /* starting radial matches, need to move it and
3068  * set pointer to new start_same
3069  */
3070  start_same = BU_LIST_PNEXT_CIRC(nmg_radial, &start_same->l);
3071  BU_LIST_DEQUEUE(&same->l);
3072  BU_LIST_APPEND(&end_same->l, &same->l);
3073  } else if (same == end_same) {
3074  /* already in correct place, just move end_same */
3075  end_same = BU_LIST_PPREV_CIRC(nmg_radial, &end_same->l);
3076  } else {
3077  BU_LIST_DEQUEUE(&same->l);
3078  BU_LIST_APPEND(&end_same->l, &same->l);
3079  }
3080 
3081  check = BU_LIST_PNEXT_CIRC(nmg_radial, &check->l);
3082  }
3083 
3084  start_same = BU_LIST_PNEXT(nmg_radial, &end_same->l);
3085  }
3086 }
3087 
3088 
3089 /**
3090  * Perform radial join of edges in list "hd" based on direction with respect
3091  * to "eu1ref"
3092  */
3093 
3094 void
3095 nmg_do_radial_join(struct bu_list *hd, struct edgeuse *eu1ref, fastf_t *xvec, fastf_t *yvec, fastf_t *zvec, const struct bn_tol *tol)
3096 {
3097  struct nmg_radial *rad;
3098  struct nmg_radial *prev;
3099  vect_t ref_dir;
3100  int skipped;
3101 
3102  BU_CK_LIST_HEAD(hd);
3103  NMG_CK_EDGEUSE(eu1ref);
3104  BN_CK_TOL(tol);
3105 
3106  if (RTG.NMG_debug & DEBUG_MESH_EU)
3107  bu_log("nmg_do_radial_join() START\n");
3108 
3109  nmg_do_radial_flips(hd);
3110 
3111  VSUB2(ref_dir, eu1ref->eumate_p->vu_p->v_p->vg_p->coord, eu1ref->vu_p->v_p->vg_p->coord);
3112 
3113  if (RTG.NMG_debug & DEBUG_MESH_EU)
3114  bu_log("ref_dir = (%g %g %g)\n", V3ARGS(ref_dir));
3115 
3116 top:
3117 
3118  if (RTG.NMG_debug & DEBUG_MESH_EU) {
3119  bu_log("At top of nmg_do_radial_join:\n");
3120  nmg_pr_radial_list(hd, tol);
3121  }
3122 
3123  skipped = 0;
3124  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
3125  struct edgeuse *dest;
3126  struct edgeuse *src;
3127  vect_t src_dir;
3128  vect_t dest_dir;
3129 
3130  if (rad->existing_flag)
3131  continue;
3132 
3133  prev = BU_LIST_PPREV_CIRC(nmg_radial, rad);
3134  if (!prev->existing_flag) {
3135  skipped++;
3136  continue;
3137  }
3138 
3139  VSUB2(dest_dir, prev->eu->eumate_p->vu_p->v_p->vg_p->coord, prev->eu->vu_p->v_p->vg_p->coord);
3140  VSUB2(src_dir, rad->eu->eumate_p->vu_p->v_p->vg_p->coord, rad->eu->vu_p->v_p->vg_p->coord);
3141 
3142  if (!prev->fu || !rad->fu) {
3143  nmg_je(prev->eu, rad->eu);
3144  continue;
3145  }
3146 
3147  if (VDOT(dest_dir, ref_dir) < -SMALL_FASTF)
3148  dest = prev->eu->eumate_p;
3149  else
3150  dest = prev->eu;
3151 
3152  if (VDOT(src_dir, ref_dir) > SMALL_FASTF)
3153  src = rad->eu->eumate_p;
3154  else
3155  src = rad->eu;
3156 
3157  if (RTG.NMG_debug & DEBUG_MESH_EU) {
3158  bu_log("Before -- ");
3159  nmg_pr_fu_around_eu_vecs(eu1ref, xvec, yvec, zvec, tol);
3160  nmg_pr_radial("prev:", prev);
3161  nmg_pr_radial(" rad:", rad);
3162 
3163  if (VDOT(dest_dir, ref_dir) < -SMALL_FASTF)
3164  bu_log("dest_dir disagrees with eu1ref\n");
3165  else
3166  bu_log("dest_dir agrees with eu1ref\n");
3167 
3168  if (VDOT(src_dir, ref_dir) < -SMALL_FASTF)
3169  bu_log("src_dir disagrees with eu1ref\n");
3170  else
3171  bu_log("src_dir agrees with eu1ref\n");
3172 
3173  bu_log("Joining dest_eu=%p to src_eu=%p\n", (void *)dest, (void *)src);
3174  }
3175 
3176  nmg_je(dest, src);
3177  rad->existing_flag = 1;
3178  if (RTG.NMG_debug & DEBUG_MESH_EU) {
3179  bu_log("After -- ");
3180  nmg_pr_fu_around_eu_vecs(eu1ref, xvec, yvec, zvec, tol);
3181  }
3182  }
3183 
3184  if (skipped)
3185  goto top;
3186 
3187  if (RTG.NMG_debug & DEBUG_MESH_EU)
3188  bu_log("nmg_do_radial_join() DONE\n\n");
3189 }
3190 
3191 
3192 /**
3193  * A new routine, that uses "global information" about the edge
3194  * to plan the operations to be performed.
3195  */
3196 void
3197 nmg_radial_join_eu_NEW(struct edgeuse *eu1, struct edgeuse *eu2, const struct bn_tol *tol)
3198 {
3199  struct edgeuse *eu1ref; /* reference eu for eu1 */
3200  struct edgeuse *eu2ref;
3201  struct faceuse *fu1;
3202  struct faceuse *fu2;
3203  struct nmg_radial *rad;
3204  vect_t xvec, yvec, zvec;
3205  struct bu_list list1;
3206  struct bu_list list2;
3207  struct bu_ptbl shell_tbl;
3208 
3209  NMG_CK_EDGEUSE(eu1);
3210  NMG_CK_EDGEUSE(eu2);
3211  BN_CK_TOL(tol);
3212 
3213  if (eu1->e_p == eu2->e_p) return;
3214 
3215  if (!NMG_ARE_EUS_ADJACENT(eu1, eu2))
3216  bu_bomb("nmg_radial_join_eu_NEW() edgeuses don't share vertices.\n");
3217 
3218  if (eu1->vu_p->v_p == eu1->eumate_p->vu_p->v_p) bu_bomb("nmg_radial_join_eu_NEW(): 0 length edge (topology)\n");
3219 
3220  if (bn_pt3_pt3_equal(eu1->vu_p->v_p->vg_p->coord,
3221  eu1->eumate_p->vu_p->v_p->vg_p->coord, tol))
3222  bu_bomb("nmg_radial_join_eu_NEW(): 0 length edge (geometry)\n");
3223 
3224  /* Ensure faces are of same orientation, if both eu's have faces */
3225  fu1 = nmg_find_fu_of_eu(eu1);
3226  fu2 = nmg_find_fu_of_eu(eu2);
3227  if (fu1 && fu2) {
3228  if (fu1->orientation != fu2->orientation) {
3229  eu2 = eu2->eumate_p;
3230  fu2 = nmg_find_fu_of_eu(eu2);
3231  if (fu1->orientation != fu2->orientation)
3232  bu_bomb("nmg_radial_join_eu_NEW(): Cannot find matching orientations for faceuses\n");
3233  }
3234  }
3235 
3236  if (eu1->eumate_p->radial_p == eu1 && eu2->eumate_p->radial_p == eu2 &&
3237  nmg_find_s_of_eu(eu1) == nmg_find_s_of_eu(eu2))
3238  {
3239  /* Only joining two edges, let's keep it simple */
3240  nmg_je(eu1, eu2);
3241  if (eu1->g.magic_p && eu2->g.magic_p) {
3242  if (eu1->g.magic_p != eu2->g.magic_p)
3243  nmg_jeg(eu1->g.lseg_p, eu2->g.lseg_p);
3244  } else if (eu1->g.magic_p && !eu2->g.magic_p)
3245  (void)nmg_use_edge_g(eu2, eu1->g.magic_p);
3246  else if (!eu1->g.magic_p && eu2->g.magic_p)
3247  (void)nmg_use_edge_g(eu1, eu2->g.magic_p);
3248  else {
3249  nmg_edge_g(eu1);
3250  nmg_use_edge_g(eu2, eu1->g.magic_p);
3251  }
3252  return;
3253  }
3254 
3255  /* XXX This angle-based algorithm can't yet handle snurb faces! */
3256  if (fu1 && fu1->f_p->g.magic_p && *fu1->f_p->g.magic_p == NMG_FACE_G_SNURB_MAGIC) return;
3257  if (fu2 && fu2->f_p->g.magic_p && *fu2->f_p->g.magic_p == NMG_FACE_G_SNURB_MAGIC) return;
3258 
3259  /* Construct local coordinate system for this edge,
3260  * so all angles can be measured relative to a common reference.
3261  */
3262  if (fu1) {
3263  if (fu1->orientation == OT_SAME)
3264  eu1ref = eu1;
3265  else
3266  eu1ref = eu1->eumate_p;
3267  } else {
3268  /* eu1 is a wire, find a non-wire, if there are any */
3269  eu1ref = nmg_find_ot_same_eu_of_e(eu1->e_p);
3270  }
3271  if (eu1ref->vu_p->v_p == eu2->vu_p->v_p) {
3272  eu2ref = eu2;
3273  } else {
3274  eu2ref = eu2->eumate_p;
3275  }
3276  nmg_eu_2vecs_perp(xvec, yvec, zvec, eu1ref, tol);
3277 
3278  /* Build the primary lists that describe the situation */
3279  BU_LIST_INIT(&list1);
3280  BU_LIST_INIT(&list2);
3281  bu_ptbl_init(&shell_tbl, 64, " &shell_tbl");
3282 
3283  nmg_radial_build_list(&list1, &shell_tbl, 1, eu1ref, xvec, yvec, zvec, tol);
3284  nmg_radial_build_list(&list2, &shell_tbl, 0, eu2ref, xvec, yvec, zvec, tol);
3285 
3286  if (RTG.NMG_debug & DEBUG_MESH_EU) {
3287  bu_log("nmg_radial_join_eu_NEW(eu1=%p, eu2=%p) e1=%p, e2=%p\n",
3288  (void *)eu1, (void *)eu2,
3289  (void *)eu1->e_p, (void *)eu2->e_p);
3290  nmg_euprint("\tJoining", eu1);
3291  bu_log("Faces around eu1:\n");
3292  nmg_pr_fu_around_eu_vecs(eu1ref, xvec, yvec, zvec, tol);
3293  nmg_pr_radial_list(&list1, tol);
3294 
3295  bu_log("Faces around eu2:\n");
3296  nmg_pr_fu_around_eu_vecs(eu2ref, xvec, yvec, zvec, tol);
3297  nmg_pr_radial_list(&list2, tol);
3298  nmg_pr_ptbl("Participating shells", &shell_tbl, 1);
3299  }
3300 
3301  /* Merge the two lists, sorting by angles */
3302  nmg_radial_merge_lists(&list1, &list2, tol);
3303  nmg_radial_verify_monotone(&list1, tol);
3304 
3305  if (RTG.NMG_debug & DEBUG_MESH_EU) {
3306  bu_log("Before nmg_do_radial_join():\n");
3307  bu_log("xvec=(%g %g %g), yvec=(%g %g %g), zvec=(%g %g %g)\n", V3ARGS(xvec), V3ARGS(yvec), V3ARGS(zvec));
3308  nmg_pr_fu_around_eu_vecs(eu2ref, xvec, yvec, zvec, tol);
3309  }
3310  nmg_do_radial_join(&list1, eu1ref, xvec, yvec, zvec, tol);
3311 
3312  /* Clean up */
3313  bu_ptbl_free(&shell_tbl);
3314  while (BU_LIST_WHILE(rad, nmg_radial, &list1)) {
3315  BU_LIST_DEQUEUE(&rad->l);
3316  BU_PUT(rad, struct nmg_radial);
3317  }
3318  return;
3319 }
3320 
3321 
3322 /**
3323  * Exchange eu and eu->eumate_p on the radial list, where marked.
3324  */
3325 void
3326 nmg_radial_exchange_marked(struct bu_list *hd, const struct bn_tol *tol)
3327 
3328 /* for printing */
3329 {
3330  struct nmg_radial *rad;
3331 
3332  BU_CK_LIST_HEAD(hd);
3333  BN_CK_TOL(tol);
3334 
3335  for (BU_LIST_FOR(rad, nmg_radial, hd)) {
3336  struct edgeuse *eu;
3337  struct edgeuse *eumate;
3338  struct edgeuse *before;
3339  struct edgeuse *after;
3340 
3341  if (!rad->needs_flip) continue;
3342 
3343  /*
3344  * Initial sequencing is:
3345  * before(radial), eu, eumate, after(radial)
3346  */
3347  eu = rad->eu;
3348  eumate = eu->eumate_p;
3349  before = eu->radial_p;
3350  after = eumate->radial_p;
3351 
3352  /*
3353  * Rearrange order to be:
3354  * before, eumate, eu, after.
3355  */
3356  before->radial_p = eumate;
3357  eumate->radial_p = before;
3358 
3359  after->radial_p = eu;
3360  eu->radial_p = after;
3361 
3362  rad->eu = eumate;
3363  rad->fu = nmg_find_fu_of_eu(rad->eu);
3364  rad->needs_flip = 0;
3365  }
3366 }
3367 
3368 
3369 /**
3370  * Visit each edge in this shell exactly once.
3371  * Where the radial edgeuse parity has become disrupted
3372  * due to a boolean operation or whatever, fix it.
3373  */
3374 void
3375 nmg_s_radial_harmonize(struct shell *s, const struct bn_tol *tol)
3376 {
3377  struct bu_ptbl edges;
3378  struct edgeuse *eu;
3379  struct bu_list list;
3380  vect_t xvec, yvec, zvec;
3381  struct edge **ep;
3382 
3383  NMG_CK_SHELL(s);
3384  BN_CK_TOL(tol);
3385 
3386  if (RTG.NMG_debug & DEBUG_BASIC)
3387  bu_log("nmg_s_radial_harmonize(s=%p) BEGIN\n", (void *)s);
3388 
3389  nmg_edge_tabulate(&edges, &s->l.magic);
3390  for (ep = (struct edge **)BU_PTBL_LASTADDR(&edges);
3391  ep >= (struct edge **)BU_PTBL_BASEADDR(&edges); ep--
3392  ) {
3393  struct nmg_radial *rad;
3394  int nflip;
3395 
3396  NMG_CK_EDGE(*ep);
3397  eu = nmg_find_ot_same_eu_of_e(*ep);
3398  nmg_eu_2vecs_perp(xvec, yvec, zvec, eu, tol);
3399 
3400  BU_LIST_INIT(&list);
3401 
3402  nmg_radial_build_list(&list, (struct bu_ptbl *)NULL, 1, eu, xvec, yvec, zvec, tol);
3403  nflip = nmg_radial_mark_flips(&list, s, tol);
3404  if (nflip) {
3405  if (RTG.NMG_debug & DEBUG_MESH_EU) {
3406  bu_log("Flips needed:\n");
3407  nmg_pr_radial_list(&list, tol);
3408  }
3409  /* Now, do the flips */
3410  nmg_radial_exchange_marked(&list, tol);
3411  if (RTG.NMG_debug & DEBUG_MESH_EU) {
3412  nmg_pr_fu_around_eu_vecs(eu, xvec, yvec, zvec, tol);
3413  }
3414  }
3415  /* Release the storage */
3416  while (BU_LIST_WHILE(rad, nmg_radial, &list)) {
3417  BU_LIST_DEQUEUE(&rad->l);
3418  BU_PUT(rad, struct nmg_radial);
3419  }
3420  }
3421 
3422  bu_ptbl_free(&edges);
3423 
3424  if (RTG.NMG_debug & DEBUG_BASIC)
3425  bu_log("nmg_s_radial_harmonize(s=%p) END\n", (void *)s);
3426 }
3427 
3428 
3429 /**
3430  * Visit each edge in this shell exactly once, and check it.
3431  */
3432 void
3433 nmg_s_radial_check(struct shell *s, const struct bn_tol *tol)
3434 {
3435  struct bu_ptbl edges;
3436  struct edge **ep;
3437 
3438  NMG_CK_SHELL(s);
3439  BN_CK_TOL(tol);
3440 
3441  if (RTG.NMG_debug & DEBUG_BASIC)
3442  bu_log("nmg_s_radial_check(s=%p) BEGIN\n", (void *)s);
3443 
3444  nmg_edge_tabulate(&edges, &s->l.magic);
3445  for (ep = (struct edge **)BU_PTBL_LASTADDR(&edges); ep >= (struct edge **)BU_PTBL_BASEADDR(&edges); ep--) {
3446  NMG_CK_EDGE(*ep);
3447  }
3448 
3449  bu_ptbl_free(&edges);
3450 
3451  if (RTG.NMG_debug & DEBUG_BASIC)
3452  bu_log("nmg_s_radial_check(s=%p) END\n", (void *)s);
3453 }
3454 
3455 
3456 void
3457 nmg_r_radial_check(const struct nmgregion *r, const struct bn_tol *tol)
3458 {
3459  struct shell *s;
3460 
3461  NMG_CK_REGION(r);
3462  BN_CK_TOL(tol);
3463 
3464  if (RTG.NMG_debug & DEBUG_BASIC)
3465  bu_log("nmg_r_radial_check(r=%p)\n", (void *)r);
3466 
3467  for (BU_LIST_FOR(s, shell, &r->s_hd)) {
3468  NMG_CK_SHELL(s);
3469  nmg_s_radial_check(s, tol);
3470  }
3471 }
3472 
3473 
3474 /*
3475  * Local Variables:
3476  * mode: C
3477  * tab-width: 8
3478  * indent-tabs-mode: t
3479  * c-file-style: "stroustrup"
3480  * End:
3481  * ex: shiftwidth=4 tabstop=8
3482  */
#define NMG_MODEL_MAGIC
Definition: magic.h:133
#define BU_LIST_PNEXT_CIRC(structure, p)
Definition: list.h:442
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
int nmg_radial_mark_flips(struct bu_list *hd, const struct shell *s, const struct bn_tol *tol)
Definition: nmg_fuse.c:2747
#define NMG_EDGEUSE_MAGIC
Definition: magic.h:120
int nmg_model_fuse(struct model *m, const struct bn_tol *tol)
Definition: nmg_fuse.c:1919
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
int nmg_model_face_fuse(struct model *m, const struct bn_tol *tol)
Definition: nmg_fuse.c:1677
Definition: list.h:118
fastf_t bn_mat_determinant(const mat_t m)
Definition: mat.c:1117
void nmg_radial_join_eu(struct edgeuse *eu1, struct edgeuse *eu2, const struct bn_tol *tol)
Definition: nmg_mesh.c:197
int bn_isect_pt_lseg(fastf_t *dist, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Intersect a point P with the line segment defined by two distinct points A and B. ...
void nmg_edge_g_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2197
double dist
>= 0
Definition: tol.h:73
void nmg_make_faces_within_tol(struct shell *s, const struct bn_tol *tol)
Definition: nmg_misc.c:8463
void nmg_euprint(const char *str, const struct edgeuse *eu)
Definition: nmg_pr.c:751
#define NMG_VERTEX_MAGIC
Definition: magic.h:147
#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
#define BU_LIST_FOR_CIRC(p, structure, hp)
Definition: list.h:379
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
lu
Definition: nmg_mod.c:3855
#define VSET(a, b, c, d)
Definition: color.c:53
#define BU_PTBL_SET(ptbl, i, val)
Definition: ptbl.h:109
#define BU_LIST_IS_EMPTY(hp)
Definition: list.h:295
#define M_PI
Definition: fft.h:35
double dist_sq
dist * dist
Definition: tol.h:74
Definition: raytrace.h:368
void nmg_eval_linear_trim_curve(const struct face_g_snurb *snrb, const fastf_t *uvw, fastf_t *xyz)
Definition: nmg_fuse.c:564
int nmg_class_pt_lu_except(fastf_t *pt, const struct loopuse *lu, const struct edge *e_p, const struct bn_tol *tol)
Definition: nmg_pt_fu.c:1386
int nmg_snurb_is_planar(const struct face_g_snurb *srf, const struct bn_tol *tol)
Definition: nmg_fuse.c:421
void nmg_s_radial_harmonize(struct shell *s, const struct bn_tol *tol)
Definition: nmg_fuse.c:3375
int nmg_region_both_vfuse(struct bu_ptbl *t1, struct bu_ptbl *t2, const struct bn_tol *tol)
Definition: nmg_fuse.c:261
void nmg_jv(register struct vertex *v1, register struct vertex *v2)
Definition: nmg_mk.c:2917
struct bu_list l
Definition: nmg_fuse.c:49
int nmg_cnurb_is_linear(const struct edge_g_cnurb *cnrb)
Definition: nmg_fuse.c:363
#define BN_TOL_MAGIC
Definition: magic.h:74
#define SMALL_FASTF
Definition: defines.h:342
void nmg_pr_radial_list(const struct bu_list *hd, const struct bn_tol *tol)
Definition: nmg_fuse.c:2980
int is_outie
This crack is an "outie".
Definition: raytrace.h:2507
void nmg_jfg(struct face *f1, struct face *f2)
Definition: nmg_mk.c:2968
void nmg_edgeuse_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2088
void nmg_do_radial_join(struct bu_list *hd, struct edgeuse *eu1ref, fastf_t *xvec, fastf_t *yvec, fastf_t *zvec, const struct bn_tol *tol)
Definition: nmg_fuse.c:3095
Header file for the BRL-CAD common definitions.
int bu_ptbl_ins_unique(struct bu_ptbl *b, long *p)
#define BU_CK_PTBL(_p)
Definition: ptbl.h:74
int nmg_break_all_es_on_v(uint32_t *magic_p, struct vertex *v, const struct bn_tol *tol)
Definition: nmg_fuse.c:1720
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
void nmg_eval_linear_trim_to_tol(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t *uvw1, const fastf_t *uvw2, struct bu_list *head, const struct bn_tol *tol)
Definition: nmg_fuse.c:738
#define NMG_RADIAL_MAGIC
Definition: magic.h:134
#define MAX_FASTF
Definition: defines.h:340
NMG_CK_LOOPUSE(lu)
struct f2 f2
#define TOL_MULTIPLES
Definition: nmg_fuse.c:1402
BU_LIST_DEQUEUE & eu1
Definition: nmg_mod.c:3839
void nmg_split_trim(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, fastf_t t, struct pt_list *pt0, struct pt_list *pt1, const struct bn_tol *tol)
Definition: nmg_fuse.c:632
Definition: ptbl.h:62
int nmg_is_crack_outie(const struct edgeuse *eu, const struct bn_tol *tol)
Definition: nmg_fuse.c:2415
void nmg_eu_2vecs_perp(fastf_t *xvec, fastf_t *yvec, fastf_t *zvec, const struct edgeuse *eu, const struct bn_tol *tol)
Definition: nmg_info.c:1237
void nmg_edge_g(struct edgeuse *eu)
Definition: nmg_mk.c:1789
int nmg_cnurb_lseg_coincident(const struct edgeuse *eu1, const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t *pt1, const fastf_t *pt2, const struct bn_tol *tol)
Definition: nmg_fuse.c:786
int needs_flip
Insert eumate, not eu.
Definition: raytrace.h:2508
void nmg_insure_radial_list_is_increasing(struct bu_list *hd, fastf_t amin, fastf_t amax)
Definition: nmg_fuse.c:2108
int nmg_use_edge_g(struct edgeuse *eu, uint32_t *magic_p)
Definition: nmg_mk.c:2087
Definition: color.c:49
void nmg_eval_trim_to_tol(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t t0, const fastf_t t1, struct bu_list *head, const struct bn_tol *tol)
Definition: nmg_fuse.c:670
struct edgeuse * nmg_find_ot_same_eu_of_e(const struct edge *e)
Definition: nmg_info.c:1441
int nmg_two_face_fuse(struct face *f1, struct face *f2, const struct bn_tol *tol)
Definition: nmg_fuse.c:1571
int nmg_loop_is_a_crack(const struct loopuse *lu)
Definition: nmg_info.c:449
void nmg_pr_v(const struct vertex *v, char *h)
Definition: nmg_pr.c:639
int nmg_cnurb_is_on_crv(const struct edgeuse *eu, const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const struct bu_list *head, const struct bn_tol *tol)
Definition: nmg_fuse.c:914
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
void nmg_radial_exchange_marked(struct bu_list *hd, const struct bn_tol *tol)
Definition: nmg_fuse.c:3326
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
int debug_file_count
Definition: nmg_bool.c:57
#define BU_LIST_FOR_BACKWARDS(p, structure, hp)
Definition: list.h:370
#define BU_PTBL_GET(ptbl, i)
Definition: ptbl.h:108
#define BU_PTBL_LASTADDR(ptbl)
Definition: ptbl.h:105
int nmg_vertex_fuse(const uint32_t *magic_p, const struct bn_tol *tol)
Definition: nmg_fuse.c:306
void bn_mat_inv(mat_t output, const mat_t input)
void nmg_r_radial_check(const struct nmgregion *r, const struct bn_tol *tol)
Definition: nmg_fuse.c:3457
#define V3ARGS(a)
Definition: color.c:56
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
void nmg_pr_lu_briefly(const struct loopuse *lu, char *h)
Definition: nmg_pr.c:455
static void top()
#define BU_GET(_ptr, _type)
Definition: malloc.h:201
struct f1 f1
void nmg_do_radial_flips(struct bu_list *hd)
Definition: nmg_fuse.c:3004
void bu_sort(void *array, size_t nummemb, size_t sizememb, int(*compare)(const void *, const void *, void *), void *context)
Definition: sort.c:110
void nmg_pr_fu_around_eu_vecs(const struct edgeuse *eu, const fastf_t *xvec, const fastf_t *yvec, const fastf_t *zvec, const struct bn_tol *tol)
Definition: nmg_pr.c:918
#define CHECK_NUMBER
Definition: nmg_fuse.c:773
void nmg_edge_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2138
#define BU_LIST_PNEXT(structure, p)
Definition: list.h:422
struct bu_list l
Definition: ptbl.h:63
struct shell * s
Derived from eu.
Definition: raytrace.h:2504
fastf_t t
Definition: nmg_fuse.c:51
double nmg_measure_fu_angle(const struct edgeuse *eu, const fastf_t *xvec, const fastf_t *yvec, const fastf_t *zvec)
Definition: nmg_info.c:391
void nmg_radial_verify_monotone(const struct bu_list *hd, const struct bn_tol *tol)
Definition: nmg_fuse.c:2080
Definition: human.c:197
#define UNUSED(parameter)
Definition: common.h:239
#define BU_PUT(_ptr, _type)
Definition: malloc.h:215
#define BU_PTBL_MAGIC
Definition: magic.h:59
goto out
Definition: nmg_mod.c:3846
#define NMG_REGION_MAGIC
Definition: magic.h:137
Support for uniform tolerances.
Definition: tol.h:71
void rt_nurb_s_print(char *c, const struct face_g_snurb *srf)
Definition: nurb_util.c:214
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
struct faceuse * fu
Derived from eu.
Definition: raytrace.h:2503
void nmg_radial_build_list(struct bu_list *hd, struct bu_ptbl *shell_tbl, int existing, struct edgeuse *eu, const fastf_t *xvec, const fastf_t *yvec, const fastf_t *zvec, const struct bn_tol *tol)
Definition: nmg_fuse.c:2183
#define NMG_CK_RADIAL(_p)
Definition: raytrace.h:2511
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
uint32_t magic
Magic # for mem id/check.
Definition: list.h:119
#define BU_LIST_WHILE(p, structure, hp)
Definition: list.h:410
#define NMG_VERTEXUSE_A_CNURB_MAGIC
Definition: magic.h:143
int existing_flag
!0 if this eu exists on dest edge
Definition: raytrace.h:2505
#define BU_LIST_MAIN_PTR(_type, _ptr2, _name2)
Definition: list.h:470
struct vertexuse * nmg_is_vertex_in_face(const struct vertex *v, const struct face *f)
Definition: nmg_info.c:1786
void nmg_radial_implement_decisions(struct bu_list *hd, const struct bn_tol *tol, struct edgeuse *eu1, fastf_t *xvec, fastf_t *yvec, fastf_t *zvec)
Definition: nmg_fuse.c:2877
#define BU_PTBL_LEN(ptbl)
Definition: ptbl.h:107
const struct edgeuse * nmg_find_next_use_of_2e_in_lu(const struct edgeuse *eu, const struct edge *e1, const struct edge *e2)
Definition: nmg_fuse.c:2522
void bu_ptbl_free(struct bu_ptbl *b)
Definition: ptbl.c:226
struct nmg_radial * nmg_find_radial_eu(const struct bu_list *hd, const struct edgeuse *eu)
Definition: nmg_fuse.c:2499
struct edgeuse * eu
Definition: raytrace.h:2502
#define BU_LIST_PPREV_CIRC(structure, p)
Definition: list.h:450
double perp
nearly 0
Definition: tol.h:75
#define ZERO(val)
Definition: units.c:38
#define BU_LIST_INIT(_hp)
Definition: list.h:148
HIDDEN int code(fastf_t x, fastf_t y)
Definition: clip.c:43
void nmg_jeg(struct edge_g_lseg *dest_eg, struct edge_g_lseg *src_eg)
Definition: nmg_mk.c:3047
uint32_t magic
Definition: tol.h:72
int nmg_ck_fu_verts(struct faceuse *fu1, struct face *f2, const struct bn_tol *tol)
Definition: nmg_fuse.c:1416
void nmg_region_v_unique(struct nmgregion *r1, const struct bn_tol *tol)
Definition: nmg_fuse.c:127
int nmg_2edgeuse_g_coincident(const struct edgeuse *eu1, const struct edgeuse *eu2, const struct bn_tol *tol)
Definition: nmg_info.c:2480
#define BU_PTBL_END(ptbl)
Definition: ptbl.h:106
#define NMG_EDGE_G_CNURB_MAGIC
Definition: magic.h:121
int nmg_model_break_e_on_v(const uint32_t *magic_p, const struct bn_tol *tol)
Definition: nmg_fuse.c:1895
struct shell * nmg_find_shell(const uint32_t *magic_p)
Definition: nmg_info.c:119
void nmg_radial_sorted_list_insert(struct bu_list *hd, struct nmg_radial *rad)
Definition: nmg_fuse.c:1988
fastf_t ang
angle, in radians. 0 to 2pi
Definition: raytrace.h:2509
eu1 up magic_p
Definition: nmg_mod.c:3915
void bu_list_reverse(struct bu_list *hd)
void rt_nurb_s_eval(const struct face_g_snurb *srf, fastf_t u, fastf_t v, fastf_t *final_value)
Definition: nurb_eval.c:49
#define BU_PTBL_BASEADDR(ptbl)
Definition: ptbl.h:104
int bu_list_len(const struct bu_list *hd)
void nmg_e_and_v_tabulate(struct bu_ptbl *eutab, struct bu_ptbl *vtab, const uint32_t *magic_p)
Definition: nmg_info.c:2442
void nmg_radial_join_eu_NEW(struct edgeuse *eu1, struct edgeuse *eu2, const struct bn_tol *tol)
Definition: nmg_fuse.c:3197
int bn_dist_pt3_lseg3(fastf_t *dist, point_t pca, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Find the distance from a point P to a line segment described by the two endpoints A and B...
Definition: color.c:51
void nmg_pr_ptbl(const char *title, const struct bu_ptbl *tbl, int verbose)
Definition: nmg_pr.c:776
void nmg_s_radial_check(struct shell *s, const struct bn_tol *tol)
Definition: nmg_fuse.c:3433
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define BU_CK_LIST_HEAD(_p)
Definition: list.h:142
int nmg_is_common_bigloop(const struct face *f1, const struct face *f2)
Definition: nmg_fuse.c:69
const char * nmg_class_name(int nmg_class)
Definition: nmg_eval.c:122
struct nmg_radial * nmg_radial_find_an_original(const struct bu_list *hd, const struct shell *s, const struct bn_tol *tol)
Definition: nmg_fuse.c:2679
void rt_nurb_c_eval(const struct edge_g_cnurb *crv, fastf_t param, fastf_t *final_value)
Definition: nurb_eval.c:125
ustring linear
int is_crack
This eu is part of a crack.
Definition: raytrace.h:2506
NMG_CK_SHELL(s)
void nmg_face_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2247
void nmg_radial_verify_pointers(const struct bu_list *hd, const struct bn_tol *tol)
Definition: nmg_fuse.c:2038
void rt_nurb_c_print(const struct edge_g_cnurb *crv)
Definition: nurb_util.c:181
int nmg_ptbl_vfuse(struct bu_ptbl *t, const struct bn_tol *tol)
Definition: nmg_fuse.c:186
int nmg_ck_fg_verts(struct faceuse *fu1, struct face *f2, const struct bn_tol *tol)
Definition: nmg_fuse.c:1526
void nmg_radial_mark_cracks(struct bu_list *hd, const struct edge *e1, const struct edge *e2, const struct bn_tol *tol)
Definition: nmg_fuse.c:2558
int bn_pt3_pt3_equal(const point_t a, const point_t b, const struct bn_tol *tol)
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
void nmg_pr_radial(const char *title, const struct nmg_radial *rad)
Definition: nmg_fuse.c:2945
int nmg_radial_check_parity(const struct bu_list *hd, const struct bu_ptbl *shells, const struct bn_tol *tol)
Definition: nmg_fuse.c:2820
#define NMG_FACEUSE_MAGIC
Definition: magic.h:124
int nmg_break_e_on_v(const uint32_t *magic_p, const struct bn_tol *tol)
Definition: nmg_fuse.c:1802
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
struct bu_list l
Definition: raytrace.h:2501
double fastf_t
Definition: defines.h:300
void nmg_split_linear_trim(const struct face_g_snurb *snrb, const fastf_t *uvw1, const fastf_t *uvw2, struct pt_list *pt0, struct pt_list *pt1, const struct bn_tol *tol)
Definition: nmg_fuse.c:703
#define VPRINT(a, b)
Definition: raytrace.h:1881
const char * bu_identify_magic(uint32_t magic)
eu2
Definition: nmg_mod.c:3875
char * nmg_orientation(int orientation)
Definition: nmg_pr.c:50
void nmg_eval_trim_curve(const struct edge_g_cnurb *cnrb, const struct face_g_snurb *snrb, const fastf_t t, fastf_t *xyz)
Definition: nmg_fuse.c:590
point_t xyz
Definition: nmg_fuse.c:50
#define BU_LIST_NOT_HEAD(p, hp)
Definition: list.h:324
double para
nearly 1
Definition: tol.h:76
int nmg_edge_g_fuse(const uint32_t *magic_p, const struct bn_tol *tol)
Definition: nmg_fuse.c:1199
#define BU_LIST_PREV(structure, hp)
Definition: list.h:310
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
void nmg_vertex_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:1985
void nmg_radial_merge_lists(struct bu_list *dest, struct bu_list *src, const struct bn_tol *tol)
Definition: nmg_fuse.c:2349
#define UNLIKELY(expression)
Definition: common.h:282
#define BU_STR_EQUAL(s1, s2)
Definition: str.h:126
struct rt_g RTG
Definition: globals.c:39