BRL-CAD
nmg_info.c
Go to the documentation of this file.
1 /* N M G _ I N F O . 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_info.c
23  *
24  * A companion module to nmg_mod.c which contains routines to
25  * answer questions about n-Manifold Geometry data structures.
26  * None of these routines will modify the NMG structures in any way.
27  *
28  */
29 /** @} */
30 
31 #include "common.h"
32 
33 #include <stdlib.h>
34 #include <stddef.h>
35 #include <string.h>
36 #include <math.h>
37 #include "bio.h"
38 
39 #include "vmath.h"
40 #include "nmg.h"
41 #include "raytrace.h"
42 
43 /************************************************************************
44  * *
45  * MODEL Routines *
46  * *
47  ************************************************************************/
48 
49 /**
50  * Given a pointer to the magic number in any NMG data structure,
51  * return a pointer to the model structure that contains that NMG item.
52  *
53  * The reason for the register variable is to leave the argument variable
54  * unmodified; this may aid debugging in event of a core dump.
55  */
56 struct model *
57 nmg_find_model(const uint32_t *magic_p_arg)
58 {
59  register const uint32_t *magic_p = magic_p_arg;
60 
61 top:
62  if (magic_p == NULL) {
63  bu_log("nmg_find_model(%p) encountered null pointer\n",
64  (void *)magic_p_arg);
65  bu_bomb("nmg_find_model() null pointer\n");
66  /* NOTREACHED */
67  }
68 
69  switch (*magic_p) {
70  case NMG_MODEL_MAGIC:
71  return (struct model *)magic_p;
72  case NMG_REGION_MAGIC:
73  return ((struct nmgregion *)magic_p)->m_p;
74  case NMG_SHELL_MAGIC:
75  return ((struct shell *)magic_p)->r_p->m_p;
76  case NMG_FACEUSE_MAGIC:
77  magic_p = &((struct faceuse *)magic_p)->s_p->l.magic;
78  goto top;
79  case NMG_FACE_MAGIC:
80  magic_p = &((struct face *)magic_p)->fu_p->l.magic;
81  goto top;
82  case NMG_LOOP_MAGIC:
83  magic_p = ((struct loop *)magic_p)->lu_p->up.magic_p;
84  goto top;
85  case NMG_LOOPUSE_MAGIC:
86  magic_p = ((struct loopuse *)magic_p)->up.magic_p;
87  goto top;
88  case NMG_EDGE_MAGIC:
89  magic_p = ((struct edge *)magic_p)->eu_p->up.magic_p;
90  goto top;
91  case NMG_EDGEUSE_MAGIC:
92  magic_p = ((struct edgeuse *)magic_p)->up.magic_p;
93  goto top;
94  case NMG_VERTEX_MAGIC:
95  magic_p = &(BU_LIST_FIRST(vertexuse,
96  &((struct vertex *)magic_p)->vu_hd)->l.magic);
97  goto top;
99  magic_p = ((struct vertexuse *)magic_p)->up.magic_p;
100  goto top;
101 
102  default:
103  bu_log("nmg_find_model() can't get model for magic=%x (%s)\n",
104  *magic_p, bu_identify_magic(*magic_p));
105  bu_bomb("nmg_find_model() failure\n");
106  }
107  return (struct model *)NULL;
108 }
109 
110 
111 /**
112  * Given a pointer to the magic number in any NMG data structure,
113  * return a pointer to the shell structure that contains that NMG item.
114  *
115  * The reason for the register variable is to leave the argument variable
116  * unmodified; this may aid debugging in event of a core dump.
117  */
118 struct shell *
119 nmg_find_shell(const uint32_t *magic_p)
120 {
121 top:
122  if (magic_p == NULL) {
123  bu_log("nmg_find_shell(%p) encountered null pointer\n", (void *)magic_p);
124  bu_bomb("nmg_find_shell() null pointer\n");
125  }
126 
127  switch (*magic_p) {
128  case NMG_SHELL_MAGIC:
129  return (struct shell *)magic_p;
130  case NMG_FACEUSE_MAGIC:
131  magic_p = &((struct faceuse *)magic_p)->s_p->l.magic;
132  goto top;
133  case NMG_FACE_MAGIC:
134  magic_p = &((struct face *)magic_p)->fu_p->l.magic;
135  goto top;
136  case NMG_LOOP_MAGIC:
137  magic_p = ((struct loop *)magic_p)->lu_p->up.magic_p;
138  goto top;
139  case NMG_LOOPUSE_MAGIC:
140  magic_p = ((struct loopuse *)magic_p)->up.magic_p;
141  goto top;
142  case NMG_EDGE_MAGIC:
143  magic_p = ((struct edge *)magic_p)->eu_p->up.magic_p;
144  goto top;
145  case NMG_EDGEUSE_MAGIC:
146  magic_p = ((struct edgeuse *)magic_p)->up.magic_p;
147  goto top;
148  case NMG_VERTEX_MAGIC:
149  magic_p = &(BU_LIST_FIRST(vertexuse,
150  &((struct vertex *)magic_p)->vu_hd)->l.magic);
151  goto top;
152  case NMG_VERTEXUSE_MAGIC:
153  magic_p = ((struct vertexuse *)magic_p)->up.magic_p;
154  goto top;
155 
156  default:
157  bu_log("nmg_find_shell() can't get shell for magic=%x (%s)\n",
158  *magic_p, bu_identify_magic(*magic_p));
159  bu_bomb("nmg_find_shell() failure\n");
160  }
161  return (struct shell *)NULL;
162 }
163 
164 
165 void
166 nmg_model_bb(fastf_t *min_pt, fastf_t *max_pt, const struct model *m)
167 {
168  struct nmgregion *r;
169  register int i;
170 
171  NMG_CK_MODEL(m);
172 
173  min_pt[0] = min_pt[1] = min_pt[2] = MAX_FASTF;
174  max_pt[0] = max_pt[1] = max_pt[2] = -MAX_FASTF;
175 
176  for (BU_LIST_FOR(r, nmgregion, &m->r_hd)) {
177  for (i=0; i < 3; i++) {
178  if (min_pt[i] > r->ra_p->min_pt[i])
179  min_pt[i] = r->ra_p->min_pt[i];
180  if (max_pt[i] < r->ra_p->max_pt[i])
181  max_pt[i] = r->ra_p->max_pt[i];
182  }
183  }
184 }
185 
186 
187 /************************************************************************
188  * *
189  * SHELL Routines *
190  * *
191  ************************************************************************/
192 
193 /**
194  * See if this is an invalid shell
195  * i.e., one that has absolutely nothing in it,
196  * not even a lone vertexuse.
197  *
198  * Returns -
199  * 1 yes, it is completely empty
200  * 0 no, not empty
201  */
202 int
203 nmg_shell_is_empty(register const struct shell *s)
204 {
205  NMG_CK_SHELL(s);
206 
207  if (BU_LIST_NON_EMPTY(&s->fu_hd)) return 0;
208  if (BU_LIST_NON_EMPTY(&s->lu_hd)) return 0;
209  if (BU_LIST_NON_EMPTY(&s->eu_hd)) return 0;
210  if (s->vu_p) return 0;
211  return 1;
212 }
213 
214 
215 /**
216  * return parent shell for loopuse
217  * formerly nmg_lups().
218  */
219 struct shell *
220 nmg_find_s_of_lu(const struct loopuse *lu)
221 {
222  if (*lu->up.magic_p == NMG_SHELL_MAGIC) return lu->up.s_p;
223  else if (*lu->up.magic_p != NMG_FACEUSE_MAGIC)
224  bu_bomb("nmg_find_s_of_lu() bad parent for loopuse\n");
225 
226  return lu->up.fu_p->s_p;
227 }
228 
229 
230 /**
231  * return parent shell of edgeuse
232  * formerly nmg_eups().
233  */
234 struct shell *
235 nmg_find_s_of_eu(const struct edgeuse *eu)
236 {
237  if (*eu->up.magic_p == NMG_SHELL_MAGIC) return eu->up.s_p;
238  else if (*eu->up.magic_p != NMG_LOOPUSE_MAGIC)
239  bu_bomb("nmg_find_s_of_eu() bad parent for edgeuse\n");
240 
241  return nmg_find_s_of_lu(eu->up.lu_p);
242 }
243 
244 
245 /**
246  * Return parent shell of vertexuse
247  */
248 struct shell *
249 nmg_find_s_of_vu(const struct vertexuse *vu)
250 {
251  NMG_CK_VERTEXUSE(vu);
252 
253  if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC)
254  return nmg_find_s_of_lu(vu->up.lu_p);
255  return nmg_find_s_of_eu(vu->up.eu_p);
256 }
257 
258 
259 /************************************************************************
260  * *
261  * FACE Routines *
262  * *
263  ************************************************************************/
264 
265 /**
266  * return a pointer to the faceuse that is the super-parent of this
267  * edgeuse. If edgeuse has no grandparent faceuse, return NULL.
268  */
269 struct faceuse *
270 nmg_find_fu_of_eu(const struct edgeuse *eu)
271 {
272  NMG_CK_EDGEUSE(eu);
273 
274  if (*eu->up.magic_p == NMG_LOOPUSE_MAGIC &&
275  *eu->up.lu_p->up.magic_p == NMG_FACEUSE_MAGIC)
276  return eu->up.lu_p->up.fu_p;
277 
278  return (struct faceuse *)NULL;
279 }
280 
281 
282 struct faceuse *
283 nmg_find_fu_of_lu(const struct loopuse *lu)
284 {
285  switch (*lu->up.magic_p) {
286  case NMG_FACEUSE_MAGIC:
287  return lu->up.fu_p;
288  case NMG_SHELL_MAGIC:
289  return (struct faceuse *)NULL;
290  default:
291  bu_log("Error at %s %d:\nInvalid loopuse parent magic (%x)\n",
292  __FILE__, __LINE__, *lu->up.magic_p);
293  bu_bomb("nmg_find_fu_of_lu() giving up on loopuse");
294  }
295  return (struct faceuse *)NULL;
296 }
297 
298 
299 /**
300  * return a pointer to the parent faceuse of the vertexuse
301  * or a null pointer if vu is not a child of a faceuse.
302  */
303 struct faceuse *
304 nmg_find_fu_of_vu(const struct vertexuse *vu)
305 {
306  NMG_CK_VERTEXUSE(vu);
307 
308  switch (*vu->up.magic_p) {
309  case NMG_LOOPUSE_MAGIC:
310  return nmg_find_fu_of_lu(vu->up.lu_p);
311  case NMG_SHELL_MAGIC:
312  if (RTG.NMG_debug & DEBUG_BASIC)
313  bu_log("nmg_find_fu_of_vu(vu=%p) vertexuse is child of shell, can't find faceuse\n", (void *)vu);
314  return (struct faceuse *)NULL;
315  case NMG_EDGEUSE_MAGIC:
316  switch (*vu->up.eu_p->up.magic_p) {
317  case NMG_LOOPUSE_MAGIC:
318  return nmg_find_fu_of_lu(vu->up.eu_p->up.lu_p);
319  case NMG_SHELL_MAGIC:
320  if (RTG.NMG_debug & DEBUG_BASIC)
321  bu_log("nmg_find_fu_of_vu(vu=%p) vertexuse is child of shell/edgeuse, can't find faceuse\n", (void *)vu);
322  return (struct faceuse *)NULL;
323  }
324  bu_log("Error at %s %d:\nInvalid loopuse parent magic %x\n", __FILE__, __LINE__, *vu->up.lu_p->up.magic_p);
325  break;
326  default:
327  bu_log("Error at %s %d:\nInvalid vertexuse parent magic %x\n", __FILE__, __LINE__, *vu->up.magic_p);
328  break;
329  }
330 
331  return (struct faceuse *)NULL;
332 }
333 /**
334  * Find a faceuse in shell s1 that shares the face_g_plane structure with
335  * fu2 and has the same orientation.
336  * This may be an OT_OPPOSITE faceuse, depending on orientation.
337  * Returns NULL if no such faceuse can be found in s1.
338  * fu2 may be in s1, or in some other shell.
339  */
340 struct faceuse *
341 nmg_find_fu_with_fg_in_s(const struct shell *s1, const struct faceuse *fu2)
342 {
343  struct faceuse *fu1;
344  struct face *f2;
345  register struct face_g_plane *fg2;
346 
347  NMG_CK_SHELL(s1);
348  NMG_CK_FACEUSE(fu2);
349 
350  f2 = fu2->f_p;
351  NMG_CK_FACE(f2);
352  fg2 = f2->g.plane_p;
353  NMG_CK_FACE_G_PLANE(fg2);
354 
355  for (BU_LIST_FOR(fu1, faceuse, &s1->fu_hd)) {
356  register struct face *f1;
357  register struct face_g_plane *fg1;
358  int flip1, flip2;
359 
360  f1 = fu1->f_p;
361  fg1 = fu1->f_p->g.plane_p;
362 
363  if (fg1 != fg2) continue;
364 
365  if (fu1 == fu2 || fu1->fumate_p == fu2) continue;
366 
367  /* Face geometry matches, select fu1 or its mate */
368  flip1 = (fu1->orientation != OT_SAME) != (f1->flip != 0);
369  flip2 = (fu2->orientation != OT_SAME) != (f2->flip != 0);
370  if (flip1 == flip2) return fu1;
371  return fu1->fumate_p;
372  }
373  return (struct faceuse *)NULL;
374 }
375 
376 
377 /**
378  * Return the angle in radians from the interior portion of the faceuse
379  * associated with edgeuse 'eu', measured in the coordinate system
380  * defined by xvec and yvec, which are known to be perpendicular to
381  * each other, and to the edge vector.
382  *
383  * This is done by finding the "left-ward" vector for the edge in the
384  * face, which points into the interior of the face, and measuring
385  * the angle it forms relative to xvec and yvec.
386  *
387  * Wire edges are indicated by always returning angle of -pi.
388  * That will be the only case for negative returns.
389  */
390 double
391 nmg_measure_fu_angle(const struct edgeuse *eu, const fastf_t *xvec, const fastf_t *yvec, const fastf_t *UNUSED(zvec))
392 {
393  vect_t left;
394 
395  NMG_CK_EDGEUSE(eu);
396 
397  if (*eu->up.magic_p != NMG_LOOPUSE_MAGIC) return -M_PI;
398  if (nmg_find_eu_leftvec(left, eu) < 0) return -M_PI;
399 
400  return bn_angle_measure(left, xvec, yvec);
401 }
402 
403 
404 /************************************************************************
405  * *
406  * LOOP Routines *
407  * *
408  ************************************************************************/
409 
410 struct loopuse *
411 nmg_find_lu_of_vu(const struct vertexuse *vu)
412 {
413  NMG_CK_VERTEXUSE(vu);
414 
415  if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC)
416  return vu->up.lu_p;
417 
418  if (*vu->up.magic_p == NMG_SHELL_MAGIC)
419  return (struct loopuse *)NULL;
420 
421  if (*vu->up.eu_p->up.magic_p == NMG_SHELL_MAGIC)
422  return (struct loopuse *)NULL;
423 
424  return vu->up.eu_p->up.lu_p;
425 }
426 
427 
428 /**
429  * A "crack" is defined as a loop which has no area.
430  *
431  * Example of a non-trivial "crack" loop:
432  *
433  * <---- eu4 -----
434  * C ############### D
435  * | # ^ ---- eu3 --->
436  * | # |
437  * eu5 # eu2
438  * | # |
439  * <--- eu6 --V # |
440  * A ############ B
441  * --- eu1 ---->
442  *
443  *
444  * Returns -
445  * 0 Loop is not a "crack"
446  * !0 Loop *is* a "crack"
447  */
448 int
449 nmg_loop_is_a_crack(const struct loopuse *lu)
450 {
451  struct edgeuse *cur_eu;
452  struct edgeuse *cur_eumate;
453  struct vertexuse *cur_vu;
454  struct vertex *cur_v;
455  struct vertexuse *next_vu;
456  struct vertex *next_v;
457  struct faceuse *fu;
458  struct vertexuse *test_vu;
459  struct edgeuse *test_eu;
460  struct loopuse *test_lu;
461  int ret = 0;
462 
463  NMG_CK_LOOPUSE(lu);
464 
465  if (*lu->up.magic_p != NMG_FACEUSE_MAGIC) {
466  if (RTG.NMG_debug & DEBUG_BASIC) bu_log("lu up is not faceuse\n");
467  ret = 0;
468  goto out;
469  }
470  fu = lu->up.fu_p;
471  NMG_CK_FACEUSE(fu);
472 
473  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
474  if (RTG.NMG_debug & DEBUG_BASIC) bu_log("lu down is not edgeuse\n");
475  ret = 0;
476  goto out;
477  }
478 
479  /*
480  * For every edgeuse, see if there is another edgeuse from 'lu',
481  * radial around this edge, which is not this edgeuse's mate.
482  */
483  for (BU_LIST_FOR(cur_eu, edgeuse, &lu->down_hd)) {
484  cur_eumate = cur_eu->eumate_p;
485  cur_vu = cur_eu->vu_p;
486  cur_v = cur_vu->v_p;
487 
488  next_vu = cur_eumate->vu_p;
489  next_v = next_vu->v_p;
490 
491  /* XXX It might be more efficient to walk the radial list */
492  /* See if the next vertex has an edge pointing back to cur_v */
493  for (BU_LIST_FOR(test_vu, vertexuse, &next_v->vu_hd)) {
494  if (*test_vu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
495  test_eu = test_vu->up.eu_p;
496 
497  if (test_eu == cur_eu) continue; /* skip self */
498  if (test_eu == cur_eumate) continue; /* skip mates */
499  if (*test_eu->up.magic_p != NMG_LOOPUSE_MAGIC) continue;
500  test_lu = test_eu->up.lu_p;
501  if (test_lu != lu) continue;
502  /* Check departing edgeuse's NEXT vertex */
503  if (test_eu->eumate_p->vu_p->v_p == cur_v) goto match;
504  }
505  /* No path back, this can't be a crack, abort */
506  ret = 0;
507  goto out;
508 
509  /* One edgeuse matched, all the others have to as well */
510  match: ;
511  }
512  ret = 1;
513 out:
514  if (RTG.NMG_debug & DEBUG_BASIC) {
515  bu_log("nmg_loop_is_a_crack(lu=%p) ret=%d\n", (void *)lu, ret);
516  }
517  return ret;
518 }
519 
520 
521 /**
522  * Determine if loop proceeds counterclockwise (CCW) around the
523  * provided normal vector (which may be either the face normal,
524  * or the anti-normal).
525  *
526  * Returns -
527  * +1 Loop is CCW, should be exterior loop.
528  * -1 Loop is CW, should be interior loop.
529  * 0 Unable to tell, error.
530  *
531  */
532 int
533 nmg_loop_is_ccw(const struct loopuse *lu, const fastf_t *UNUSED(norm), const struct bn_tol *tol)
534 {
535  fastf_t area;
536  plane_t pl;
537  int ret = 1;
538 
539  HSETALL(pl, 0.0); /* sanity */
540  area = nmg_loop_plane_area2(lu, pl, tol);
541 
542  if (NEAR_ZERO(area, tol->dist_sq)) {
543  if (RT_G_DEBUG & DEBUG_MATH) {
544  bu_log("nmg_loop_is_ccw: Loop area (%g) is less than tol->dist_sq (%g)\n", area, tol->dist_sq);
545  nmg_pr_lu_briefly(lu, " ");
546  }
547  ret = 0;
548  goto out;
549  }
550 
551  if (area < -SMALL_FASTF) {
552  ret = -1;
553  goto out;
554  }
555 
556 out:
557  if (UNLIKELY(RTG.NMG_debug & DEBUG_BASIC)) {
558  bu_log("nmg_loop_is_ccw(lu=%p) ret=%d\n", (void *)lu, ret);
559  }
560 
561  return ret;
562 }
563 
564 
565 /**
566  * Search through all the vertices in a loop.
567  * If there are two distinct uses of one vertex in the loop,
568  * return true.
569  * This is useful for detecting "accordian pleats"
570  * unexpectedly showing up in a loop.
571  * Derived from nmg_split_touchingloops().
572  *
573  * Returns -
574  * vu Yes, the loop touches itself at least once, at this vu.
575  * 0 No, the loop does not touch itself.
576  */
577 const struct vertexuse *
578 nmg_loop_touches_self(const struct loopuse *lu)
579 {
580  const struct edgeuse *eu;
581  const struct vertexuse *vu;
582  const struct vertex *v;
583 
584  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
585  return (const struct vertexuse *)0;
586 
587  /* For each edgeuse, get vertexuse and vertex */
588  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
589  const struct vertexuse *tvu;
590 
591  vu = eu->vu_p;
592  v = vu->v_p;
593 
594  /*
595  * For each vertexuse on vertex list,
596  * check to see if it points up to the this loop.
597  * If so, then there is a duplicated vertex.
598  * Ordinarily, the vertex list will be *very* short,
599  * so this strategy is likely to be faster than
600  * a table-based approach, for most cases.
601  */
602  for (BU_LIST_FOR(tvu, vertexuse, &v->vu_hd)) {
603  const struct edgeuse *teu;
604  const struct loopuse *tlu;
605 
606  if (tvu == vu) continue;
607  /*
608  * Inline expansion of:
609  * if (nmg_find_lu_of_vu(tvu) != lu) continue;
610  */
611  if (*tvu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
612  teu = tvu->up.eu_p;
613 
614  if (*teu->up.magic_p != NMG_LOOPUSE_MAGIC) continue;
615  tlu = teu->up.lu_p;
616 
617  if (tlu != lu) continue;
618  /*
619  * Repeated vertex exists.
620  */
621  return vu;
622  }
623  }
624  return (const struct vertexuse *)0;
625 }
626 
627 
628 /************************************************************************
629  * *
630  * EDGE Routines *
631  * *
632  ************************************************************************/
633 
634 /**
635  * If shell s2 has an edge that connects the same vertices as eu1 connects,
636  * return the matching edgeuse in s2.
637  * This routine works properly regardless of whether eu1 is in s2 or not.
638  * A convenient wrapper for nmg_findeu().
639  */
640 struct edgeuse *
641 nmg_find_matching_eu_in_s(const struct edgeuse *eu1, const struct shell *s2)
642 {
643  const struct vertexuse *vu1a, *vu1b;
644  struct edgeuse *eu2;
645 
646  NMG_CK_EDGEUSE(eu1);
647  NMG_CK_SHELL(s2);
648 
649  vu1a = eu1->vu_p;
650  vu1b = BU_LIST_PNEXT_CIRC(edgeuse, eu1)->vu_p;
651 
652  if ((nmg_find_v_in_shell(vu1a->v_p, s2, 1)) == (struct vertexuse *)NULL)
653  return (struct edgeuse *)NULL;
654  if ((nmg_find_v_in_shell(vu1b->v_p, s2, 1)) == (struct vertexuse *)NULL)
655  return (struct edgeuse *)NULL;
656 
657  /* Both vertices have vu's of eu's in s2 */
658 
659  eu2 = nmg_findeu(vu1a->v_p, vu1b->v_p, s2, eu1, 0);
660  return eu2; /* May be NULL if no edgeuse found */
661 }
662 
663 
664 /**
665  * Find an edgeuse in a shell between a given pair of vertex structs.
666  *
667  * If a given shell "s" is specified, then only edgeuses in that shell
668  * will be considered, otherwise all edgeuses in the model are fair game.
669  *
670  * If a particular edgeuse "eup" is specified, then that edgeuse
671  * and its mate will not be returned as a match.
672  *
673  * If "dangling_only" is true, then an edgeuse will be matched only if
674  * there are no other edgeuses on the edge, i.e. the radial edgeuse is
675  * the same as the mate edgeuse.
676  *
677  * Returns -
678  * edgeuse* Edgeuse which matches the criteria
679  * NULL Unable to find matching edgeuse
680  */
681 struct edgeuse *
682 nmg_findeu(const struct vertex *v1, const struct vertex *v2, const struct shell *s, const struct edgeuse *eup, int dangling_only)
683 {
684  register const struct vertexuse *vu;
685  register const struct edgeuse *eu;
686  const struct edgeuse *eup_mate;
687  int eup_orientation;
688 
689  NMG_CK_VERTEX(v1);
690  NMG_CK_VERTEX(v2);
691  if (s) NMG_CK_SHELL(s);
692 
693  if (eup) {
694  struct faceuse *fu;
695  NMG_CK_EDGEUSE(eup);
696  eup_mate = eup->eumate_p;
697  NMG_CK_EDGEUSE(eup_mate);
698  fu = nmg_find_fu_of_eu(eup);
699  if (fu)
700  eup_orientation = fu->orientation;
701  else
702  eup_orientation = OT_SAME;
703  } else {
704  eup_mate = eup; /* NULL */
705  eup_orientation = OT_SAME;
706  }
707 
708  if (RTG.NMG_debug & DEBUG_FINDEU)
709  bu_log("nmg_findeu() seeking eu!=%8p/%8p between (%8p, %8p) %s\n",
710  (void *)eup, (void *)eup_mate, (void *)v1, (void *)v2,
711  dangling_only ? "[dangling]" : "[any]");
712 
713  for (BU_LIST_FOR(vu, vertexuse, &v1->vu_hd)) {
714  if (!vu->up.magic_p)
715  bu_bomb("nmg_findeu() vertexuse in vu_hd list has null parent\n");
716 
717  /* Ignore self-loops and lone shell verts */
718  if (*vu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
719  eu = vu->up.eu_p;
720 
721  /* Ignore edgeuses which don't run between the right verts */
722  if (eu->eumate_p->vu_p->v_p != v2) continue;
723 
724  if (RTG.NMG_debug & DEBUG_FINDEU) {
725  bu_log("nmg_findeu: check eu=%8p vertex=(%8p, %8p)\n",
726  (void *)eu, (void *)eu->vu_p->v_p,
727  (void *)eu->eumate_p->vu_p->v_p);
728  }
729 
730  /* Ignore the edgeuse to be excluded */
731  if (eu == eup || eu->eumate_p == eup) {
732  if (RTG.NMG_debug & DEBUG_FINDEU)
733  bu_log("\tIgnoring -- excluded edgeuse\n");
734  continue;
735  }
736 
737  /* See if this edgeuse is in the proper shell */
738  if (s && nmg_find_s_of_eu(eu) != s) {
739  if (RTG.NMG_debug & DEBUG_FINDEU)
740  bu_log("\tIgnoring %p -- eu in wrong shell s=%p\n",
741  (void *)eu, (void *)eu->up.s_p);
742  continue;
743  }
744 
745  /* If it's not a dangling edge, skip on */
746  if (dangling_only && eu->eumate_p != eu->radial_p) {
747  if (RTG.NMG_debug & DEBUG_FINDEU) {
748  bu_log("\tIgnoring %8p/%8p (radial=%p)\n",
749  (void *)eu, (void *)eu->eumate_p,
750  (void *)eu->radial_p);
751  }
752  continue;
753  }
754 
755  if (RTG.NMG_debug & DEBUG_FINDEU)
756  bu_log("\tFound %8p/%8p\n", (void *)eu, (void *)eu->eumate_p);
757 
758  if (*eu->up.magic_p == NMG_LOOPUSE_MAGIC &&
759  *eu->up.lu_p->up.magic_p == NMG_FACEUSE_MAGIC &&
760  eup_orientation != eu->up.lu_p->up.fu_p->orientation)
761  eu = eu->eumate_p; /* Take other orient */
762  goto out;
763  }
764  eu = (struct edgeuse *)NULL;
765 out:
766  if (RTG.NMG_debug & (DEBUG_BASIC|DEBUG_FINDEU))
767  bu_log("nmg_findeu() returns %p\n", (void *)eu);
768 
769  return (struct edgeuse *)eu;
770 }
771 
772 
773 /**
774  * An analog to nmg_findeu(), only restricted to searching a faceuse,
775  * rather than to a whole shell.
776  */
777 struct edgeuse *
778 nmg_find_eu_in_face(const struct vertex *v1, const struct vertex *v2, const struct faceuse *fu, const struct edgeuse *eup, int dangling_only)
779 {
780  register const struct vertexuse *vu;
781  register const struct edgeuse *eu;
782  const struct edgeuse *eup_mate;
783  int eup_orientation;
784 
785  NMG_CK_VERTEX(v1);
786  NMG_CK_VERTEX(v2);
787  if (fu) NMG_CK_FACEUSE(fu);
788 
789  if (eup) {
790  struct faceuse *fu1;
791  NMG_CK_EDGEUSE(eup);
792  eup_mate = eup->eumate_p;
793  NMG_CK_EDGEUSE(eup_mate);
794  fu1 = nmg_find_fu_of_eu(eup);
795  if (fu1)
796  eup_orientation = fu1->orientation;
797  else
798  eup_orientation = OT_SAME;
799  } else {
800  eup_mate = eup; /* NULL */
801  eup_orientation = OT_SAME;
802  }
803 
804  if (RTG.NMG_debug & DEBUG_FINDEU)
805  bu_log("nmg_find_eu_in_face() seeking eu!=%8p/%8p between (%8p, %8p) %s\n",
806  (void *)eup, (void *)eup_mate, (void *)v1, (void *)v2,
807  dangling_only ? "[dangling]" : "[any]");
808 
809  for (BU_LIST_FOR(vu, vertexuse, &v1->vu_hd)) {
810  if (!vu->up.magic_p)
811  bu_bomb("nmg_find_eu_in_face() vertexuse in vu_hd list has null parent\n");
812 
813  /* Ignore self-loops and lone shell verts */
814  if (*vu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
815  eu = vu->up.eu_p;
816 
817  /* Ignore edgeuses which don't run between the right verts */
818  if (eu->eumate_p->vu_p->v_p != v2) continue;
819 
820  if (RTG.NMG_debug & DEBUG_FINDEU) {
821  bu_log("nmg_find_eu_in_face: check eu=%8p vertex=(%8p, %8p)\n",
822  (void *)eu, (void *)eu->vu_p->v_p,
823  (void *)eu->eumate_p->vu_p->v_p);
824  }
825 
826  /* Ignore the edgeuse to be excluded */
827  if (eu == eup || eu->eumate_p == eup) {
828  if (RTG.NMG_debug & DEBUG_FINDEU)
829  bu_log("\tIgnoring -- excluded edgeuse\n");
830  continue;
831  }
832 
833  /* See if this edgeuse is in the proper faceuse */
834  if (fu && nmg_find_fu_of_eu(eu) != fu) {
835  if (RTG.NMG_debug & DEBUG_FINDEU)
836  bu_log("\tIgnoring %p -- eu not in faceuse\n", (void *)eu);
837  continue;
838  }
839 
840  /* If it's not a dangling edge, skip on */
841  if (dangling_only && eu->eumate_p != eu->radial_p) {
842  if (RTG.NMG_debug & DEBUG_FINDEU) {
843  bu_log("\tIgnoring %8p/%8p (radial=%p)\n",
844  (void *)eu, (void *)eu->eumate_p,
845  (void *)eu->radial_p);
846  }
847  continue;
848  }
849 
850  if (RTG.NMG_debug & DEBUG_FINDEU)
851  bu_log("\tFound %8p/%8p\n", (void *)eu, (void *)eu->eumate_p);
852 
853  if (*eu->up.magic_p == NMG_LOOPUSE_MAGIC &&
854  *eu->up.lu_p->up.magic_p == NMG_FACEUSE_MAGIC &&
855  eup_orientation != eu->up.lu_p->up.fu_p->orientation)
856  eu = eu->eumate_p; /* Take other orient */
857  goto out;
858  }
859  eu = (struct edgeuse *)NULL;
860 out:
861  if (RTG.NMG_debug & (DEBUG_BASIC|DEBUG_FINDEU))
862  bu_log("nmg_find_eu_in_face() returns %p\n", (void *)eu);
863 
864  return (struct edgeuse *)eu;
865 }
866 
867 
868 /**
869  * Find an edge between a given pair of vertices.
870  *
871  * If a given shell "s" is specified, then only edges in that shell
872  * will be considered, otherwise all edges in the model are fair game.
873  *
874  * If a particular edge "ep" is specified, then that edge
875  * will not be returned as a match.
876  *
877  * Returns -
878  * edgeuse* Edgeuse of an edge which matches the criteria
879  * NULL Unable to find matching edge
880  */
881 struct edgeuse *
882 nmg_find_e(const struct vertex *v1, const struct vertex *v2, const struct shell *s, const struct edge *ep)
883 {
884  register const struct vertexuse *vu;
885  register const struct edgeuse *eu;
886 
887  NMG_CK_VERTEX(v1);
888  NMG_CK_VERTEX(v2);
889  if (s) NMG_CK_SHELL(s);
890 
891  if (RTG.NMG_debug & DEBUG_FINDEU) {
892  bu_log("nmg_find_e() seeking e!=%8p between (%8p, %8p)\n",
893  (void *)ep, (void *)v1, (void *)v2);
894  }
895 
896  for (BU_LIST_FOR(vu, vertexuse, &v1->vu_hd)) {
897  if (!vu->up.magic_p)
898  bu_bomb("nmg_find_e() vertexuse in vu_hd list has null parent\n");
899 
900  /* Ignore self-loops and lone shell verts */
901  if (*vu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
902  eu = vu->up.eu_p;
903 
904  /* Ignore edgeuses which don't run between the right verts */
905  /* We know that this eu starts at v1 */
906  if (eu->eumate_p->vu_p->v_p != v2) continue;
907 
908  if (RTG.NMG_debug & DEBUG_FINDEU) {
909  bu_log("nmg_find_e: check eu=%8p vertex=(%8p, %8p)\n",
910  (void *)eu, (void *)eu->vu_p->v_p,
911  (void *)eu->eumate_p->vu_p->v_p);
912  }
913 
914  /* Ignore the edge to be excluded */
915  if (eu->e_p == ep) {
916  if (RTG.NMG_debug & DEBUG_FINDEU)
917  bu_log("\tIgnoring -- excluded edge\n");
918  continue;
919  }
920 
921  /* See if this edgeuse is in the proper shell */
922  if (s && nmg_find_s_of_eu(eu) != s) {
923  if (RTG.NMG_debug & DEBUG_FINDEU)
924  bu_log("\tIgnoring %p -- eu in wrong shell s=%p\n", (void *)eu, (void *)eu->up.s_p);
925  continue;
926  }
927 
928  if (RTG.NMG_debug & DEBUG_FINDEU)
929  bu_log("\tFound %8p/%8p\n", (void *)eu, (void *)eu->eumate_p);
930 
931  if (*eu->up.magic_p == NMG_LOOPUSE_MAGIC &&
932  *eu->up.lu_p->up.magic_p == NMG_FACEUSE_MAGIC &&
933  eu->up.lu_p->up.fu_p->orientation != OT_SAME) {
934  eu = eu->eumate_p; /* Take other orient */
935  }
936  goto out;
937  }
938  eu = (struct edgeuse *)NULL;
939 out:
940  if (RTG.NMG_debug & (DEBUG_BASIC|DEBUG_FINDEU))
941  bu_log("nmg_find_e() returns %p\n", (void *)eu);
942 
943  return (struct edgeuse *)eu;
944 }
945 
946 
947 /**
948  * Return a pointer to the edgeuse which is the parent of this vertexuse.
949  *
950  * A simple helper routine, which replaces the amazingly bad sequence of:
951  * nmg_find_eu_with_vu_in_lu(nmg_find_lu_of_vu(vu), vu)
952  * that was being used in several places.
953  */
954 struct edgeuse *
955 nmg_find_eu_of_vu(const struct vertexuse *vu)
956 {
957  NMG_CK_VERTEXUSE(vu);
958 
959  if (*vu->up.magic_p != NMG_EDGEUSE_MAGIC)
960  return (struct edgeuse *)NULL;
961 
962  return vu->up.eu_p;
963 }
964 
965 
966 /**
967  * Find an edgeuse starting at a given vertexuse within a loopuse.
968  */
969 struct edgeuse *
970 nmg_find_eu_with_vu_in_lu(const struct loopuse *lu, const struct vertexuse *vu)
971 {
972  register struct edgeuse *eu;
973 
974  NMG_CK_LOOPUSE(lu);
975  NMG_CK_VERTEXUSE(vu);
976 
977  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
978  bu_bomb("nmg_find_eu_with_vu_in_lu: loop has no edges!\n");
979  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
980  if (eu->vu_p == vu) return eu;
981  }
982  bu_bomb("nmg_find_eu_with_vu_in_lu: Unable to find vu!\n");
983 
984  /* NOTREACHED */
985 
986  return (struct edgeuse *)NULL;
987 }
988 
989 
990 /**
991  * Looking radially around an edge, find another edge in the same
992  * face as the current edge. (this could be the mate to the current edge)
993  */
994 const struct edgeuse *
995 nmg_faceradial(const struct edgeuse *eu)
996 {
997  const struct faceuse *fu;
998  const struct edgeuse *eur;
999 
1000  NMG_CK_EDGEUSE(eu);
1001 
1002  fu = eu->up.lu_p->up.fu_p;
1003  eur = eu->radial_p;
1004 
1005  while (*eur->up.magic_p != NMG_LOOPUSE_MAGIC
1006  || *eur->up.lu_p->up.magic_p != NMG_FACEUSE_MAGIC
1007  || eur->up.lu_p->up.fu_p->f_p != fu->f_p)
1008  {
1009  eur = eur->eumate_p->radial_p;
1010  }
1011 
1012  return eur;
1013 }
1014 
1015 
1016 /**
1017  * looking radially around an edge, find another edge which is a part
1018  * of a face in the same shell
1019  */
1020 const struct edgeuse *
1021 nmg_radial_face_edge_in_shell(const struct edgeuse *eu)
1022 {
1023  const struct edgeuse *eur;
1024  const struct shell *s;
1025 
1026  NMG_CK_EDGEUSE(eu);
1027 
1028  s = nmg_find_s_of_eu(eu);
1029  eur = eu->radial_p;
1030 
1031  while (eur != eu->eumate_p) {
1032  if (*eur->up.magic_p == NMG_LOOPUSE_MAGIC &&
1033  *eur->up.lu_p->up.magic_p == NMG_FACEUSE_MAGIC &&
1034  eur->up.lu_p->up.fu_p->s_p == s) {
1035  break; /* found another face in shell */
1036  } else {
1037  eur = eur->eumate_p->radial_p;
1038  }
1039  }
1040  return eur;
1041 }
1042 
1043 
1044 /**
1045  * Perform a topology search to determine if two faces (specified by
1046  * their faceuses) share an edge in common. If so, return an edgeuse
1047  * in fu1 of that edge.
1048  *
1049  * If there are multiple edgeuses in common, ensure that they all refer
1050  * to the same edge_g_lseg geometry structure. The intersection of two planes
1051  * (non-coplanar) must be a single line.
1052  *
1053  * Calling this routine when the two faces share face geometry
1054  * and have more than one edge in common gives
1055  * a NULL return, as there is no unique answer.
1056  *
1057  * NULL is also returned if no common edge could be found.
1058  */
1059 const struct edgeuse *
1060 nmg_find_edge_between_2fu(const struct faceuse *fu1, const struct faceuse *fu2, const struct bn_tol *tol)
1061 {
1062  const struct loopuse *lu1;
1063  const struct edgeuse *ret = (const struct edgeuse *)NULL;
1064  int coincident;
1065 
1066  NMG_CK_FACEUSE(fu1);
1067  NMG_CK_FACEUSE(fu2);
1068  BN_CK_TOL(tol);
1069 
1070  for (BU_LIST_FOR(lu1, loopuse, &fu1->lu_hd)) {
1071  const struct edgeuse *eu1;
1072 
1073  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) == NMG_VERTEXUSE_MAGIC)
1074  continue;
1075 
1076  for (BU_LIST_FOR(eu1, edgeuse, &lu1->down_hd)) {
1077  const struct edgeuse *eur;
1078 
1079  /* Walk radially around the edge */
1080  eur = eu1->radial_p;
1081 
1082  while (eur != eu1->eumate_p) {
1083  if (*eur->up.magic_p == NMG_LOOPUSE_MAGIC &&
1084  *eur->up.lu_p->up.magic_p == NMG_FACEUSE_MAGIC &&
1085  eur->up.lu_p->up.fu_p->f_p == fu2->f_p) {
1086  /* Found the other face on this edge! */
1087  if (!ret) {
1088  /* First common edge found */
1089  if (eur->up.lu_p->up.fu_p == fu2) {
1090  ret = eur;
1091  } else {
1092  ret = eur->eumate_p;
1093  }
1094  } else {
1095  /* Previous edge found, check edge_g_lseg */
1096  if (eur->g.lseg_p != ret->g.lseg_p) {
1097  bu_log("eur=%p, eg_p=%p; ret=%p, eg_p=%p\n",
1098  (void *)eur, (void *)eur->g.lseg_p,
1099  (void *)ret, (void *)ret->g.lseg_p);
1100  nmg_pr_eg(eur->g.magic_p, 0);
1101  nmg_pr_eg(ret->g.magic_p, 0);
1102  nmg_pr_eu_endpoints(eur, 0);
1103  nmg_pr_eu_endpoints(ret, 0);
1104 
1105  coincident = nmg_2edgeuse_g_coincident(eur, ret, tol);
1106  if (coincident) {
1107  /* Change eur to use ret's eg */
1108  bu_log("nmg_find_edge_between_2fu() belatedly fusing e1=%p, eg1=%p, e2=%p, eg2=%p\n",
1109  (void *)eur->e_p, (void *)eur->g.lseg_p,
1110  (void *)ret->e_p, (void *)ret->g.lseg_p);
1111  nmg_jeg(ret->g.lseg_p, eur->g.lseg_p);
1112  /* See if there are any others. */
1113  nmg_model_fuse(nmg_find_model(&eur->l.magic), tol);
1114  } else {
1115  bu_bomb("nmg_find_edge_between_2fu() 2 faces intersect with differing edge geometries?\n");
1116  }
1117  }
1118  }
1119  }
1120  /* Advance to next */
1121  eur = eur->eumate_p->radial_p;
1122  }
1123  }
1124  }
1125 
1126  if (RTG.NMG_debug & DEBUG_BASIC)
1127  bu_log("nmg_find_edge_between_2fu(fu1=%p, fu2=%p) edgeuse=%p\n",
1128  (void *)fu1, (void *)fu2, (void *)ret);
1129 
1130  return ret;
1131 
1132 }
1133 
1134 
1135 /**
1136  * Support for nmg_find_e_nearest_pt2().
1137  */
1138 struct fen2d_state {
1139  char *visited; /* array of edges already visited */
1140  fastf_t mindist; /* current min dist */
1141  struct edge *ep; /* closest edge */
1142  mat_t mat;
1143  point_t pt2;
1144  const struct bn_tol *tol;
1145 };
1146 
1147 
1148 static void
1149 nmg_find_e_pt2_handler(uint32_t *lp, void *state, int UNUSED(unused))
1150 {
1151  register struct fen2d_state *sp = (struct fen2d_state *)state;
1152  register struct edge *e = (struct edge *)lp;
1153  fastf_t dist_sq;
1154  point_t a2, b2;
1155  struct vertex *va, *vb;
1156  point_t pca;
1157  int code;
1158 
1159  BN_CK_TOL(sp->tol);
1160  NMG_CK_EDGE(e);
1161 
1162  /* If this edge has been processed before, do nothing more */
1163  if (!NMG_INDEX_FIRST_TIME(sp->visited, e)) return;
1164 
1165  va = e->eu_p->vu_p->v_p;
1166  vb = e->eu_p->eumate_p->vu_p->v_p;
1167 
1168  MAT4X3PNT(a2, sp->mat, va->vg_p->coord);
1169  MAT4X3PNT(b2, sp->mat, vb->vg_p->coord);
1170 
1171  code = bn_dist_pt2_lseg2(&dist_sq, pca, a2, b2, sp->pt2, sp->tol);
1172 
1173  if (code == 0) dist_sq = 0;
1174 
1175  if (dist_sq < sp->mindist) {
1176  sp->mindist = dist_sq;
1177  sp->ep = e;
1178  }
1179 }
1180 
1181 
1182 /**
1183  * A geometric search routine to find the edge that is nearest to
1184  * the given point, when all edges are projected into 2D using
1185  * the matrix 'mat'.
1186  * Useful for finding the edge nearest a mouse click, for example.
1187  */
1188 struct edge *
1189 nmg_find_e_nearest_pt2(uint32_t *magic_p, const fastf_t *pt2, const fastf_t *mat, const struct bn_tol *tol)
1190 
1191 /* 2d point */
1192 /* 3d to 3d xform */
1193 
1194 {
1195  struct model *m;
1196  struct fen2d_state st;
1197  static const struct nmg_visit_handlers htab = {NULL, NULL, NULL, NULL, NULL,
1198  NULL, NULL, NULL, NULL, NULL,
1199  NULL, NULL, NULL, NULL, NULL,
1200  NULL, NULL, NULL, nmg_find_e_pt2_handler, NULL,
1201  NULL, NULL, NULL, NULL, NULL};
1202  /* htab.vis_edge = nmg_find_e_pt2_handler; */
1203 
1204  BN_CK_TOL(tol);
1205  m = nmg_find_model(magic_p);
1206  NMG_CK_MODEL(m);
1207 
1208  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
1209  st.mindist = INFINITY;
1210  VMOVE(st.pt2, pt2);
1211  MAT_COPY(st.mat, mat);
1212  st.ep = (struct edge *)NULL;
1213  st.tol = tol;
1214 
1215  nmg_visit(magic_p, &htab, (void *)&st);
1216 
1217  bu_free((char *)st.visited, "visited[]");
1218 
1219  if (st.ep) {
1220  NMG_CK_EDGE(st.ep);
1221  return st.ep;
1222  }
1223  return (struct edge *)NULL;
1224 }
1225 
1226 
1227 /**
1228  * Given an edgeuse, return two arbitrary unit-length vectors which
1229  * are perpendicular to each other and to the edgeuse, such that
1230  * they can be considered the +X and +Y axis, and the edgeuse is +Z.
1231  * That is, X cross Y = Z.
1232  *
1233  * Useful for erecting a coordinate system around an edge suitable
1234  * for measuring the angles of other edges and faces with.
1235  */
1236 void
1237 nmg_eu_2vecs_perp(fastf_t *xvec, fastf_t *yvec, fastf_t *zvec, const struct edgeuse *eu, const struct bn_tol *tol)
1238 {
1239  const struct vertex *v1, *v2;
1240  fastf_t len;
1241 
1242  NMG_CK_EDGEUSE(eu);
1243  BN_CK_TOL(tol);
1244 
1245  v1 = eu->vu_p->v_p;
1246  v2 = eu->eumate_p->vu_p->v_p;
1247  if (v1 == v2) bu_bomb("nmg_eu_2vecs_perp() start&end vertex of edge are the same!\n");
1248 
1249  VSUB2(zvec, v2->vg_p->coord, v1->vg_p->coord);
1250  len = MAGNITUDE(zvec);
1251  /* See if v1 == v2, within tol */
1252  if (len < tol->dist) bu_bomb("nmg_eu_2vecs_perp(): 0-length edge (geometry)\n");
1253  len = 1 / len;
1254  VSCALE(zvec, zvec, len);
1255 
1256  bn_vec_perp(xvec, zvec);
1257  VCROSS(yvec, zvec, xvec);
1258 }
1259 
1260 
1261 /**
1262  * Given an edgeuse, if it is part of a faceuse, return the inward pointing
1263  * "left" vector which points into the interior of this loop, and
1264  * lies in the plane of the face. The left vector is unitized.
1265  *
1266  * This routine depends on the vertex ordering in an OT_SAME loopuse being
1267  * properly CCW for exterior loops, and CW for interior (hole) loops.
1268  *
1269  * Returns -
1270  * -1 if edgeuse is not part of a faceuse.
1271  * 0 if left vector successfully computed into caller's array.
1272  */
1273 int
1274 nmg_find_eu_leftvec(fastf_t *left, const struct edgeuse *eu)
1275 {
1276  const struct loopuse *lu;
1277  const struct faceuse *fu;
1278  vect_t Norm;
1279  vect_t edgevect;
1280  fastf_t dot;
1281  struct vertex_g *vg1;
1282  struct vertex_g *vg2;
1283  fastf_t edge_len_sq;
1284  fastf_t sin_sq;
1285 
1286  NMG_CK_EDGEUSE(eu);
1287 
1288  if (*eu->up.magic_p != NMG_LOOPUSE_MAGIC) return -1;
1289  lu = eu->up.lu_p;
1290  if (*lu->up.magic_p != NMG_FACEUSE_MAGIC) return -1;
1291  fu = lu->up.fu_p;
1292 
1293  vg1 = eu->vu_p->v_p->vg_p;
1294  vg2 = eu->eumate_p->vu_p->v_p->vg_p;
1295 
1296  /* Get unit length Normal vector for edgeuse's faceuse */
1297  NMG_GET_FU_NORMAL(Norm, fu);
1298 
1299  VSUB2(edgevect, vg2->coord, vg1->coord);
1300  edge_len_sq = MAGSQ(edgevect);
1301 
1302  dot = VDOT(edgevect, Norm);
1303  sin_sq = 1.0 - (dot * dot / edge_len_sq);
1304 
1305  if (NEAR_ZERO(sin_sq, 0.000001)) {
1306  /* we don't have a tol structure available XXX */
1307  const struct edgeuse *eu_next;
1308  const struct edgeuse *eu_prev;
1309  vect_t next_left;
1310  vect_t prev_left;
1311  vect_t other_edge;
1312  int other_edge_is_parallel=1;
1313 
1314  VSETALL(other_edge, 0);
1315 
1316  bu_log("WARNING: eu %p (%f %f %f) parallel to normal (%f %f %f)\n", (void *)eu, V3ARGS(edgevect), V3ARGS(Norm));
1317 
1318  eu_next = eu;
1319  while (other_edge_is_parallel) {
1320  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, &eu_next->l);
1321  if (eu_next == eu)
1322  break;
1323  if (NMG_ARE_EUS_ADJACENT(eu, eu_next))
1324  continue;
1325  VSUB2(other_edge, eu_next->eumate_p->vu_p->v_p->vg_p->coord,
1326  eu_next->vu_p->v_p->vg_p->coord);
1327  VUNITIZE(other_edge);
1328  dot = 1.0 - fabs(VDOT(other_edge, Norm));
1329  if (dot < .5)
1330  other_edge_is_parallel = 0;
1331  }
1332  if (other_edge_is_parallel) {
1333  bu_log("Cannot find edge (starting eu =%p) that is not parallel to face normal!!!\n", (void *)eu);
1334  nmg_pr_fu_briefly(fu, (char *)NULL);
1335  bu_bomb("Cannot find edge that is not parallel to face normal!!!\n");
1336  }
1337 
1338  VCROSS(next_left, Norm, other_edge);
1339  VUNITIZE(next_left);
1340 
1341  eu_prev = eu;
1342  other_edge_is_parallel = 1;
1343  while (other_edge_is_parallel) {
1344  eu_prev = BU_LIST_PPREV_CIRC(edgeuse, &eu_prev->l);
1345  if (eu_prev == eu)
1346  break;
1347  if (NMG_ARE_EUS_ADJACENT(eu, eu_prev))
1348  continue;
1349  VSUB2(other_edge, eu_prev->eumate_p->vu_p->v_p->vg_p->coord,
1350  eu_prev->vu_p->v_p->vg_p->coord);
1351  VUNITIZE(other_edge);
1352  dot = 1.0 - fabs(VDOT(other_edge, Norm));
1353  if (dot < .5)
1354  other_edge_is_parallel = 0;
1355  }
1356  if (other_edge_is_parallel) {
1357  bu_log("Cannot find edge (starting eu =%p) that is not parallel to face normal!!!\n",
1358  (void *)eu);
1359  nmg_pr_fu_briefly(fu, (char *)NULL);
1360  bu_bomb("Cannot find edge that is not parallel to face normal!!!\n");
1361  }
1362 
1363  VCROSS(prev_left, Norm, other_edge);
1364  VUNITIZE(prev_left);
1365 
1366  VBLEND2(left, 0.5, next_left, 0.5, prev_left);
1367  VUNITIZE(left);
1368  return 0;
1369  }
1370 
1371  VCROSS(left, Norm, edgevect);
1372  if (RTG.NMG_debug & DEBUG_MESH_EU) {
1373  vect_t edge_unit;
1374  vect_t norm_x_edge;
1375 
1376  VMOVE(edge_unit, edgevect);
1377  VUNITIZE(edge_unit);
1378  VCROSS(norm_x_edge, Norm, edge_unit);
1379  bu_log("for eu %p from fu %p v1=%p, v2=%p:\n",
1380  (void *)eu, (void *)fu, (void *)eu->vu_p->v_p, (void *)eu->eumate_p->vu_p->v_p);
1381  bu_log("\t(%.10f %.10f %.10f) <-> (%.10f %.10f %.10f)\n", V3ARGS(eu->vu_p->v_p->vg_p->coord), V3ARGS(eu->eumate_p->vu_p->v_p->vg_p->coord));
1382  bu_log("\tedge dot norm = %.10f\n", VDOT(edge_unit, Norm));
1383  bu_log("\tnorm X edge = (%.10f %.10f %.10f)\n", V3ARGS(norm_x_edge));
1384  bu_log("\tnorm=(%.10f %.10f %.10f), edgevect=(%.10f %.10f %.10f), left=(%.10f %.10f %.10f)\n",
1385  V3ARGS(Norm), V3ARGS(edgevect), V3ARGS(left));
1386  }
1387  VUNITIZE(left);
1388  if (RTG.NMG_debug & DEBUG_MESH_EU) {
1389  bu_log("\tUnitized left=(%f %f %f)\n", V3ARGS(left));
1390  }
1391  return 0;
1392 }
1393 
1394 
1395 /**
1396  * Given an edgeuse, if it is part of a faceuse, return the inward pointing
1397  * "left" vector which points into the interior of this loop, and
1398  * lies in the plane of the face. The left vector is not unitized.
1399  *
1400  * This routine depends on the vertex ordering in an OT_SAME loopuse being
1401  * properly CCW for exterior loops, and CW for interior (hole) loops.
1402  *
1403  * Returns -
1404  * -1 if edgeuse is not part of a faceuse.
1405  * 0 if left vector successfully computed into caller's array.
1406  */
1407 int
1408 nmg_find_eu_left_non_unit(fastf_t *left, const struct edgeuse *eu)
1409 {
1410  const struct loopuse *lu;
1411  const struct faceuse *fu;
1412  vect_t Norm;
1413  vect_t edgevect;
1414  pointp_t p1, p2;
1415 
1416  NMG_CK_EDGEUSE(eu);
1417 
1418  if (*eu->up.magic_p != NMG_LOOPUSE_MAGIC) return -1;
1419  lu = eu->up.lu_p;
1420  if (*lu->up.magic_p != NMG_FACEUSE_MAGIC) return -1;
1421  fu = lu->up.fu_p;
1422 
1423  /* Get unit length Normal vector for edgeuse's faceuse */
1424  NMG_GET_FU_NORMAL(Norm, fu);
1425 
1426  /* Get vector in direction of edge */
1427  p1 = eu->vu_p->v_p->vg_p->coord;
1428  p2 = eu->eumate_p->vu_p->v_p->vg_p->coord;
1429  VSUB2(edgevect, p2, p1);
1430 
1431  /* left vector is cross-product of face normal and edge direction */
1432  VCROSS(left, Norm, edgevect);
1433  return 0;
1434 }
1435 /**
1436  * If there is an edgeuse of an OT_SAME faceuse on this edge, return it.
1437  * Only return a wire edgeuse if that is all there is.
1438  * Useful for selecting a "good" edgeuse to pass to nmg_eu_2vecs_perp().
1439  */
1440 struct edgeuse *
1441 nmg_find_ot_same_eu_of_e(const struct edge *e)
1442 {
1443  register struct edgeuse *eu1;
1444  register struct edgeuse *eu;
1445  struct faceuse *fu;
1446 
1447  NMG_CK_EDGE(e);
1448 
1449  eu = eu1 = e->eu_p;
1450  do {
1451  fu = nmg_find_fu_of_eu(eu);
1452  if (fu && fu->orientation == OT_SAME) return eu;
1453 
1454  fu = nmg_find_fu_of_eu(eu->eumate_p);
1455  if (fu && fu->orientation == OT_SAME) return eu->eumate_p;
1456  eu = eu->radial_p->eumate_p;
1457  } while (eu != eu1);
1458 
1459  return eu1; /* All wire */
1460 }
1461 
1462 
1463 /************************************************************************
1464  * *
1465  * VERTEX Routines *
1466  * *
1467  ************************************************************************/
1468 
1469 /**
1470  * Perform a topological search to
1471  * determine if the given vertex is contained in the given faceuse.
1472  * If it is, return a pointer to the vertexuse which was found in the
1473  * faceuse.
1474  *
1475  * Returns NULL if not found.
1476  */
1477 struct vertexuse *
1478 nmg_find_v_in_face(const struct vertex *v, const struct faceuse *fu)
1479 {
1480  struct vertexuse *vu;
1481  struct edgeuse *eu;
1482  struct loopuse *lu;
1483 
1484  NMG_CK_VERTEX(v);
1485 
1486  for (BU_LIST_FOR(vu, vertexuse, &v->vu_hd)) {
1487  if (*vu->up.magic_p == NMG_EDGEUSE_MAGIC) {
1488  eu = vu->up.eu_p;
1489  if (*eu->up.magic_p == NMG_LOOPUSE_MAGIC) {
1490  lu = eu->up.lu_p;
1491  if (*lu->up.magic_p == NMG_FACEUSE_MAGIC && lu->up.fu_p == fu)
1492  return vu;
1493  }
1494 
1495  } else if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
1496  lu = vu->up.lu_p;
1497  if (*lu->up.magic_p == NMG_FACEUSE_MAGIC && lu->up.fu_p == fu)
1498  return vu;
1499  }
1500  }
1501  return (struct vertexuse *)NULL;
1502 }
1503 
1504 
1505 /**
1506  * Search shell "s" for a vertexuse that refers to vertex "v".
1507  * For efficiency, the search is done on the uses of "v".
1508  *
1509  * If "edges_only" is set, only a vertexuse from an edgeuse will
1510  * be returned, otherwise, vu's from self-loops and lone-shell-vu's
1511  * are also candidates.
1512  */
1513 struct vertexuse *
1514 nmg_find_v_in_shell(const struct vertex *v, const struct shell *s, int edges_only)
1515 {
1516  struct vertexuse *vu;
1517 
1518  NMG_CK_VERTEX(v);
1519 
1520  for (BU_LIST_FOR(vu, vertexuse, &v->vu_hd)) {
1521 
1522  if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
1523  if (edges_only) continue;
1524  if (nmg_find_s_of_lu(vu->up.lu_p) == s)
1525  return vu;
1526  continue;
1527  }
1528  if (*vu->up.magic_p == NMG_SHELL_MAGIC) {
1529  if (edges_only) continue;
1530  if (vu->up.s_p == s)
1531  return vu;
1532  continue;
1533  }
1534  if (*vu->up.magic_p != NMG_EDGEUSE_MAGIC)
1535  bu_bomb("nmg_find_v_in_shell(): bad vu up ptr\n");
1536 
1537  /* vu is being used by an edgeuse */
1538  if (nmg_find_s_of_eu(vu->up.eu_p) == s)
1539  return vu;
1540  }
1541  return (struct vertexuse *)NULL;
1542 }
1543 
1544 
1545 /**
1546  * Conduct a geometric search for a vertex in loopuse 'lu' which is
1547  * "identical" to the given point, within the specified tolerance.
1548  * The loopuse may be part of a face, or it may be wires.
1549  *
1550  * Returns -
1551  * NULL No vertex matched
1552  * (struct vertexuse *) A matching vertexuse from that loopuse.
1553  */
1554 struct vertexuse *
1555 nmg_find_pt_in_lu(const struct loopuse *lu, const fastf_t *pt, const struct bn_tol *tol)
1556 {
1557  register struct edgeuse *eu;
1558  register struct vertex_g *vg;
1559  uint32_t magic1;
1560 
1561  magic1 = BU_LIST_FIRST_MAGIC(&lu->down_hd);
1562  if (magic1 == NMG_VERTEXUSE_MAGIC) {
1563  struct vertexuse *vu;
1564  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1565  vg = vu->v_p->vg_p;
1566  if (!vg) {
1567  return (struct vertexuse *)NULL;
1568  }
1569  if (bn_pt3_pt3_equal(vg->coord, pt, tol)) {
1570  return vu;
1571  }
1572  return (struct vertexuse *)NULL;
1573  }
1574  if (magic1 != NMG_EDGEUSE_MAGIC) {
1575  bu_bomb("nmg_find_pt_in_lu() Bogus child of loop\n");
1576  }
1577 
1578  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1579  vg = eu->vu_p->v_p->vg_p;
1580  if (!vg) {
1581  continue;
1582  }
1583  if (bn_pt3_pt3_equal(vg->coord, pt, tol)) {
1584  return eu->vu_p;
1585  }
1586  }
1587 
1588  return (struct vertexuse *)NULL;
1589 }
1590 
1591 
1592 /**
1593  * Conduct a geometric search for a vertex in face 'fu' which is
1594  * "identical" to the given point, within the specified tolerance.
1595  *
1596  * Returns -
1597  * NULL No vertex matched
1598  * (struct vertexuse *) A matching vertexuse from that face.
1599  */
1600 struct vertexuse *
1601 nmg_find_pt_in_face(const struct faceuse *fu, const fastf_t *pt, const struct bn_tol *tol)
1602 {
1603  register struct loopuse *lu;
1604  struct vertexuse *vu;
1605 
1606  NMG_CK_FACEUSE(fu);
1607  BN_CK_TOL(tol);
1608 
1609  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1610  vu = nmg_find_pt_in_lu(lu, pt, tol);
1611  if (vu)
1612  return vu;
1613  }
1614  return (struct vertexuse *)NULL;
1615 }
1616 
1617 
1618 /**
1619  * Given a point in 3-space and a shell pointer, try to find a vertex
1620  * anywhere in the shell which is within sqrt(tol_sq) distance of
1621  * the given point.
1622  *
1623  * The algorithm is a brute force, and should be used sparingly.
1624  * Mike Gigante's NUgrid technique would work well here, if
1625  * searching was going to be needed for more than a few points.
1626  *
1627  * Returns -
1628  * pointer to vertex with matching geometry
1629  * NULL
1630  *
1631  * XXX Why does this return a vertex, while its helpers return a vertexuse?
1632  */
1633 struct vertex *
1634 nmg_find_pt_in_shell(const struct shell *s, const fastf_t *pt, const struct bn_tol *tol)
1635 {
1636  const struct faceuse *fu;
1637  const struct loopuse *lu;
1638  const struct edgeuse *eu;
1639  const struct vertexuse *vu;
1640  struct vertex *v;
1641  const struct vertex_g *vg;
1642 
1643  NMG_CK_SHELL(s);
1644  BN_CK_TOL(tol);
1645 
1646  fu = BU_LIST_FIRST(faceuse, &s->fu_hd);
1647  while (BU_LIST_NOT_HEAD(fu, &s->fu_hd)) {
1648  /* Shell has faces */
1649  vu = nmg_find_pt_in_face(fu, pt, tol);
1650  if (vu)
1651  return vu->v_p;
1652 
1653  if (BU_LIST_PNEXT(faceuse, fu) == fu->fumate_p)
1654  fu = BU_LIST_PNEXT_PNEXT(faceuse, fu);
1655  else
1656  fu = BU_LIST_PNEXT(faceuse, fu);
1657  }
1658 
1659  /* Wire loopuses */
1660  lu = BU_LIST_FIRST(loopuse, &s->lu_hd);
1661  while (BU_LIST_NOT_HEAD(lu, &s->lu_hd)) {
1662  vu = nmg_find_pt_in_lu(lu, pt, tol);
1663  if (vu)
1664  return vu->v_p;
1665 
1666  if (BU_LIST_PNEXT(loopuse, lu) == lu->lumate_p)
1667  lu = BU_LIST_PNEXT_PNEXT(loopuse, lu);
1668  else
1669  lu = BU_LIST_PNEXT(loopuse, lu);
1670  }
1671 
1672  /* Wire edgeuses */
1673  for (BU_LIST_FOR(eu, edgeuse, &s->eu_hd)) {
1674 
1675  v = eu->vu_p->v_p;
1676  vg = v->vg_p;
1677 
1678  if (vg) {
1679  if (bn_pt3_pt3_equal(vg->coord, pt, tol)) {
1680  return v;
1681  }
1682  }
1683  }
1684 
1685  /* Lone vertexuse */
1686  if (s->vu_p) {
1687 
1688  v = s->vu_p->v_p;
1689  vg = v->vg_p;
1690 
1691  if (vg) {
1692  if (bn_pt3_pt3_equal(vg->coord, pt, tol)) {
1693  return v;
1694  }
1695  }
1696  }
1697  return (struct vertex *)0;
1698 }
1699 
1700 
1701 /**
1702  * Brute force search of the entire model to find a vertex that
1703  * matches this point.
1704  * XXX Shouldn't this return the _closest_ match, not just the
1705  * XXX first match within tolerance?
1706  */
1707 struct vertex *
1708 nmg_find_pt_in_model(const struct model *m, const fastf_t *pt, const struct bn_tol *tol)
1709 {
1710  struct nmgregion *r;
1711  struct shell *s;
1712  struct vertex *v;
1713 
1714  NMG_CK_MODEL(m);
1715  BN_CK_TOL(tol);
1716 
1717  for (BU_LIST_FOR(r, nmgregion, &m->r_hd)) {
1718  for (BU_LIST_FOR(s, shell, &r->s_hd)) {
1719  v = nmg_find_pt_in_shell(s, pt, tol);
1720  if (v) {
1721  return v;
1722  }
1723  }
1724  }
1725  return (struct vertex *)NULL;
1726 }
1727 
1728 
1729 /**
1730  * Returns -
1731  * 1 If found
1732  * 0 If not found
1733  */
1734 int
1735 nmg_is_vertex_in_edgelist(register const struct vertex *v, const struct bu_list *hd)
1736 {
1737  register const struct edgeuse *eu;
1738 
1739  NMG_CK_VERTEX(v);
1740 
1741  for (BU_LIST_FOR(eu, edgeuse, hd)) {
1742  if (eu->vu_p->v_p == v) return 1;
1743  }
1744  return 0;
1745 }
1746 
1747 
1748 /**
1749  * Returns -
1750  * 1 If found
1751  * 0 If not found
1752  */
1753 int
1754 nmg_is_vertex_in_looplist(register const struct vertex *v, const struct bu_list *hd, int singletons)
1755 {
1756  register const struct loopuse *lu;
1757  uint32_t magic1;
1758 
1759  NMG_CK_VERTEX(v);
1760 
1761  for (BU_LIST_FOR(lu, loopuse, hd)) {
1762 
1763  magic1 = BU_LIST_FIRST_MAGIC(&lu->down_hd);
1764  if (magic1 == NMG_VERTEXUSE_MAGIC) {
1765  register const struct vertexuse *vu;
1766  if (!singletons) continue;
1767  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1768  if (vu->v_p == v) return 1;
1769  } else if (magic1 == NMG_EDGEUSE_MAGIC) {
1770  if (nmg_is_vertex_in_edgelist(v, &lu->down_hd))
1771  return 1;
1772  } else {
1773  bu_bomb("nmg_is_vertex_in_loopuse() bad magic\n");
1774  }
1775  }
1776  return 0;
1777 }
1778 
1779 
1780 /**
1781  * Returns -
1782  * vu One use of vertex 'v' in face 'f'.
1783  * NULL If there are no uses of 'v' in 'f'.
1784  */
1785 struct vertexuse *
1786 nmg_is_vertex_in_face(const struct vertex *v, const struct face *f)
1787 {
1788  struct vertexuse *vu;
1789 
1790  NMG_CK_VERTEX(v);
1791  NMG_CK_FACE(f);
1792 
1793  for (BU_LIST_FOR(vu, vertexuse, &v->vu_hd)) {
1794  register const struct edgeuse *eu;
1795  register const struct loopuse *lu;
1796  register const struct faceuse *fu;
1797 
1798  if (*vu->up.magic_p != NMG_EDGEUSE_MAGIC) continue;
1799  if (*(eu = vu->up.eu_p)->up.magic_p != NMG_LOOPUSE_MAGIC) continue;
1800  lu = eu->up.lu_p;
1801  if (*lu->up.magic_p != NMG_FACEUSE_MAGIC) continue;
1802  fu = lu->up.fu_p;
1803  if (fu->f_p != f) continue;
1804  return vu;
1805  }
1806  return (struct vertexuse *)NULL;
1807 }
1808 
1809 
1810 /**
1811  * Check to see if a given vertex is used within a shell
1812  * by a wire loopuse which is a loop of a single vertex.
1813  * The search could either be by the shell lu_hd, or the vu_hd.
1814  *
1815  * Returns -
1816  * 0 vertex is not part of that kind of loop in the shell.
1817  * 1 vertex is part of a selfloop in the given shell.
1818  */
1819 int
1820 nmg_is_vertex_a_selfloop_in_shell(const struct vertex *v, const struct shell *s)
1821 {
1822  const struct vertexuse *vu;
1823 
1824  NMG_CK_VERTEX(v);
1825  NMG_CK_SHELL(s);
1826 
1827  /* try to find the vertex in a loopuse of this shell */
1828  for (BU_LIST_FOR(vu, vertexuse, &v->vu_hd)) {
1829  register const struct loopuse *lu;
1830 
1831  if (*vu->up.magic_p != NMG_LOOPUSE_MAGIC) continue;
1832  lu = vu->up.lu_p;
1833  if (*lu->up.magic_p != NMG_SHELL_MAGIC) continue;
1834 
1835  if (lu->up.s_p == s)
1836  return 1;
1837  }
1838  return 0;
1839 }
1840 
1841 
1842 /**
1843  * Returns -
1844  * 1 If found
1845  * 0 If not found
1846  */
1847 int
1848 nmg_is_vertex_in_facelist(register const struct vertex *v, const struct bu_list *hd)
1849 {
1850  register const struct faceuse *fu;
1851 
1852  NMG_CK_VERTEX(v);
1853  for (BU_LIST_FOR(fu, faceuse, hd)) {
1854  if (nmg_is_vertex_in_looplist(v, &fu->lu_hd, 1))
1855  return 1;
1856  }
1857  return 0;
1858 }
1859 
1860 
1861 /**
1862  * Returns -
1863  * 1 If found
1864  * 0 If not found
1865  */
1866 int
1867 nmg_is_edge_in_edgelist(const struct edge *e, const struct bu_list *hd)
1868 {
1869  register const struct edgeuse *eu;
1870 
1871  NMG_CK_EDGE(e);
1872  for (BU_LIST_FOR(eu, edgeuse, hd)) {
1873  if (e == eu->e_p) return 1;
1874  }
1875  return 0;
1876 }
1877 
1878 
1879 /**
1880  * Returns -
1881  * 1 If found
1882  * 0 If not found
1883  */
1884 int
1885 nmg_is_edge_in_looplist(const struct edge *e, const struct bu_list *hd)
1886 {
1887  register const struct loopuse *lu;
1888  uint32_t magic1;
1889 
1890  NMG_CK_EDGE(e);
1891 
1892  for (BU_LIST_FOR(lu, loopuse, hd)) {
1893  magic1 = BU_LIST_FIRST_MAGIC(&lu->down_hd);
1894  if (magic1 == NMG_VERTEXUSE_MAGIC) {
1895  /* Loop of a single vertex does not have an edge */
1896  continue;
1897  } else if (magic1 == NMG_EDGEUSE_MAGIC) {
1898  if (nmg_is_edge_in_edgelist(e, &lu->down_hd))
1899  return 1;
1900  } else {
1901  bu_bomb("nmg_is_edge_in_loopuse() bad magic\n");
1902  }
1903  }
1904  return 0;
1905 }
1906 
1907 
1908 /**
1909  * Returns -
1910  * 1 If found
1911  * 0 If not found
1912  */
1913 int
1914 nmg_is_edge_in_facelist(const struct edge *e, const struct bu_list *hd)
1915 {
1916  register const struct faceuse *fu;
1917 
1918  NMG_CK_EDGE(e);
1919  for (BU_LIST_FOR(fu, faceuse, hd)) {
1920  if (nmg_is_edge_in_looplist(e, &fu->lu_hd))
1921  return 1;
1922  }
1923  return 0;
1924 }
1925 
1926 
1927 /**
1928  * Returns -
1929  * 1 If found
1930  * 0 If not found
1931  */
1932 int
1933 nmg_is_loop_in_facelist(const struct loop *l, const struct bu_list *fu_hd)
1934 {
1935  register const struct faceuse *fu;
1936  register const struct loopuse *lu;
1937 
1938  NMG_CK_LOOP(l);
1939  for (BU_LIST_FOR(fu, faceuse, fu_hd)) {
1940  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1941  if (l == lu->l_p) return 1;
1942  }
1943  }
1944  return 0;
1945 }
1946 
1947 
1948 /************************************************************************
1949  * *
1950  * Tabulation Routines *
1951  * *
1952  ************************************************************************/
1953 
1954 struct vf_state {
1955  char *visited;
1956  struct bu_ptbl *tabl;
1957 };
1958 
1959 
1960 /**
1961  * A private support routine for nmg_vertex_tabulate().
1962  * Having just visited a vertex, if this is the first time,
1963  * add it to the bu_ptbl array.
1964  */
1965 static void
1966 nmg_2rvf_handler(uint32_t *vp, void *state, int UNUSED(unused))
1967 {
1968  register struct vf_state *sp = (struct vf_state *)state;
1969  register struct vertex *v = (struct vertex *)vp;
1970 
1971  NMG_CK_VERTEX(v);
1972  /* If this vertex has been processed before, do nothing more */
1973  if (!NMG_INDEX_FIRST_TIME(sp->visited, v)) return;
1974 
1975  bu_ptbl_ins(sp->tabl, (long *)vp);
1976 }
1977 
1978 
1979 /**
1980  * Given a pointer to any nmg data structure,
1981  * build an bu_ptbl list which has every vertex
1982  * pointer from there on "down" in the model, each one listed exactly once.
1983  */
1984 void
1985 nmg_vertex_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
1986 {
1987  struct model *m;
1988  struct vf_state st;
1989  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
1990  NULL, NULL, NULL, NULL, NULL,
1991  NULL, NULL, NULL, NULL, NULL,
1992  NULL, NULL, NULL, NULL, NULL,
1993  NULL, NULL, NULL, nmg_2rvf_handler, NULL};
1994  /* handlers.vertex = nmg_2rvf_handler; */
1995 
1996  m = nmg_find_model(magic_p);
1997  NMG_CK_MODEL(m);
1998 
1999  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2000  st.tabl = tab;
2001 
2002  (void)bu_ptbl_init(tab, 64, " tab");
2003 
2004  nmg_visit(magic_p, &handlers, (void *)&st);
2005 
2006  bu_free((char *)st.visited, "visited[]");
2007 }
2008 
2009 
2010 /**
2011  * A private support routine for nmg_vertexuse_normal_tabulate().
2012  * Having just visited a vertexuse-a, if this is the first time,
2013  * add it to the bu_ptbl array.
2014  */
2015 static void
2016 nmg_vert_a_handler(uint32_t *vp, void *state, int UNUSED(unused))
2017 {
2018  register struct vf_state *sp = (struct vf_state *)state;
2019  register struct vertexuse_a_plane *va;
2020 
2021  if (*vp != NMG_VERTEXUSE_A_PLANE_MAGIC)
2022  return;
2023 
2024  va = (struct vertexuse_a_plane *)vp;
2025  /* If this vertex normal has been processed before, do nothing more */
2026  if (!NMG_INDEX_FIRST_TIME(sp->visited, va)) return;
2027 
2028  bu_ptbl_ins(sp->tabl, (long *)vp);
2029 }
2030 
2031 
2032 /**
2033  * Given a pointer to any nmg data structure,
2034  * build an bu_ptbl list which has every vertexuse normal
2035  * pointer from there on "down" in the model, each one listed exactly once.
2036  */
2037 void
2038 nmg_vertexuse_normal_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
2039 {
2040  struct model *m;
2041  struct vf_state st;
2042  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
2043  NULL, NULL, NULL, NULL, NULL,
2044  NULL, NULL, NULL, NULL, NULL,
2045  NULL, NULL, NULL, NULL, NULL,
2046  NULL, NULL, nmg_vert_a_handler, NULL, NULL};
2047  /* handlers.vis_vertexuse_a = nmg_vert_a_handler; */
2048 
2049  m = nmg_find_model(magic_p);
2050  NMG_CK_MODEL(m);
2051 
2052  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2053  st.tabl = tab;
2054 
2055  (void)bu_ptbl_init(tab, 64, " tab");
2056 
2057  nmg_visit(magic_p, &handlers, (void *)&st);
2058 
2059  bu_free((char *)st.visited, "visited[]");
2060 }
2061 
2062 
2063 /**
2064  * A private support routine for nmg_edgeuse_tabulate().
2065  * Having just visited a edgeuse, if this is the first time,
2066  * add it to the bu_ptbl array.
2067  */
2068 static void
2069 nmg_2edgeuse_handler(uint32_t *eup, void *state, int UNUSED(unused))
2070 {
2071  register struct vf_state *sp = (struct vf_state *)state;
2072  register struct edgeuse *eu = (struct edgeuse *)eup;
2073 
2074  NMG_CK_EDGEUSE(eu);
2075  /* If this edgeuse has been processed before, do nothing more */
2076  if (!NMG_INDEX_FIRST_TIME(sp->visited, eu)) return;
2077 
2078  bu_ptbl_ins(sp->tabl, (long *)eup);
2079 }
2080 
2081 
2082 /**
2083  * Given a pointer to any nmg data structure,
2084  * build an bu_ptbl list which has every edgeuse
2085  * pointer from there on "down" in the model, each one listed exactly once.
2086  */
2087 void
2088 nmg_edgeuse_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
2089 {
2090  struct model *m;
2091  struct vf_state st;
2092  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
2093  NULL, NULL, NULL, NULL, NULL,
2094  NULL, NULL, NULL, NULL, NULL,
2095  NULL, nmg_2edgeuse_handler, NULL, NULL, NULL,
2096  NULL, NULL, NULL, NULL, NULL};
2097  /* handlers.bef_edgeuse = nmg_2edgeuse_handler; */
2098 
2099  m = nmg_find_model(magic_p);
2100  NMG_CK_MODEL(m);
2101 
2102  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2103  st.tabl = tab;
2104 
2105  (void)bu_ptbl_init(tab, 64, " tab");
2106 
2107  nmg_visit(magic_p, &handlers, (void *)&st);
2108 
2109  bu_free((char *)st.visited, "visited[]");
2110 }
2111 
2112 
2113 /**
2114  * A private support routine for nmg_edge_tabulate().
2115  * Having just visited a edge, if this is the first time,
2116  * add it to the bu_ptbl array.
2117  */
2118 static void
2119 nmg_2edge_handler(uint32_t *ep, void *state, int UNUSED(unused))
2120 {
2121  register struct vf_state *sp = (struct vf_state *)state;
2122  register struct edge *e = (struct edge *)ep;
2123 
2124  NMG_CK_EDGE(e);
2125  /* If this edge has been processed before, do nothing more */
2126  if (!NMG_INDEX_FIRST_TIME(sp->visited, e)) return;
2127 
2128  bu_ptbl_ins(sp->tabl, (long *)ep);
2129 }
2130 
2131 
2132 /**
2133  * Given a pointer to any nmg data structure,
2134  * build an bu_ptbl list which has every edge
2135  * pointer from there on "down" in the model, each one listed exactly once.
2136  */
2137 void
2138 nmg_edge_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
2139 {
2140  struct model *m;
2141  struct vf_state st;
2142  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
2143  NULL, NULL, NULL, NULL, NULL,
2144  NULL, NULL, NULL, NULL, NULL,
2145  NULL, NULL, NULL, nmg_2edge_handler, NULL,
2146  NULL, NULL, NULL, NULL, NULL};
2147  /* handlers.vis_edge = nmg_2edge_handler; */
2148 
2149  m = nmg_find_model(magic_p);
2150  NMG_CK_MODEL(m);
2151 
2152  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2153  st.tabl = tab;
2154 
2155  (void)bu_ptbl_init(tab, 64, " tab");
2156 
2157  nmg_visit(magic_p, &handlers, (void *)&st);
2158 
2159  bu_free((char *)st.visited, "visited[]");
2160 }
2161 
2162 
2163 /**
2164  * A private support routine for nmg_edge_g_tabulate().
2165  * Having just visited an edge_g_lseg, if this is the first time,
2166  * add it to the bu_ptbl array.
2167  */
2168 static void
2169 nmg_edge_g_handler(uint32_t *ep, void *state, int UNUSED(unused))
2170 {
2171  register struct vf_state *sp = (struct vf_state *)state;
2172 
2173  NMG_CK_EDGE_G_EITHER(ep);
2174 
2175  /* If this edge has been processed before, do nothing more */
2176  switch (*ep) {
2177  case NMG_EDGE_G_LSEG_MAGIC:
2178  if (!NMG_INDEX_FIRST_TIME(sp->visited, ((struct edge_g_lseg *)ep)))
2179  return;
2180  break;
2182  if (!NMG_INDEX_FIRST_TIME(sp->visited, ((struct edge_g_cnurb *)ep)))
2183  return;
2184  break;
2185  }
2186 
2187  bu_ptbl_ins(sp->tabl, (long *)ep);
2188 }
2189 
2190 
2191 /**
2192  * Given a pointer to any nmg data structure,
2193  * build an bu_ptbl list which has every edge
2194  * pointer from there on "down" in the model, each one listed exactly once.
2195  */
2196 void
2197 nmg_edge_g_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
2198 {
2199  struct model *m;
2200  struct vf_state st;
2201  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
2202  NULL, NULL, NULL, NULL, NULL,
2203  NULL, NULL, NULL, NULL, NULL,
2204  NULL, NULL, NULL, NULL, nmg_edge_g_handler,
2205  NULL, NULL, NULL, NULL, NULL};
2206  /* handlers.vis_edge_g = nmg_edge_g_handler; */
2207 
2208  m = nmg_find_model(magic_p);
2209  NMG_CK_MODEL(m);
2210 
2211  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2212  st.tabl = tab;
2213 
2214  (void)bu_ptbl_init(tab, 64, " tab");
2215 
2216  nmg_visit(magic_p, &handlers, (void *)&st);
2217 
2218  bu_free((char *)st.visited, "visited[]");
2219 }
2220 
2221 
2222 /**
2223  * A private support routine for nmg_face_tabulate().
2224  * Having just visited a face, if this is the first time,
2225  * add it to the bu_ptbl array.
2226  */
2227 static void
2228 nmg_2face_handler(uint32_t *fp, void *state, int UNUSED(unused))
2229 {
2230  register struct vf_state *sp = (struct vf_state *)state;
2231  register struct face *f = (struct face *)fp;
2232 
2233  NMG_CK_FACE(f);
2234  /* If this face has been processed before, do nothing more */
2235  if (!NMG_INDEX_FIRST_TIME(sp->visited, f)) return;
2236 
2237  bu_ptbl_ins(sp->tabl, (long *)fp);
2238 }
2239 
2240 
2241 /**
2242  * Given a pointer to any nmg data structure,
2243  * build an bu_ptbl list which has every face
2244  * pointer from there on "down" in the model, each one listed exactly once.
2245  */
2246 void
2247 nmg_face_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
2248 {
2249  struct model *m;
2250  struct vf_state st;
2251  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
2252  NULL, NULL, NULL, NULL, NULL,
2253  nmg_2face_handler, NULL, NULL, NULL, NULL,
2254  NULL, NULL, NULL, NULL, NULL,
2255  NULL, NULL, NULL, NULL, NULL};
2256  /* handlers.vis_face = nmg_2face_handler; */
2257 
2258  m = nmg_find_model(magic_p);
2259  NMG_CK_MODEL(m);
2260 
2261  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2262  st.tabl = tab;
2263 
2264  (void)bu_ptbl_init(tab, 64, " tab");
2265 
2266  nmg_visit(magic_p, &handlers, (void *)&st);
2267 
2268  bu_free((char *)st.visited, "visited[]");
2269 }
2270 
2271 
2272 /**
2273  * Build an bu_ptbl list which cites every edgeuse
2274  * pointer that uses edge geometry "eg".
2275  */
2276 void
2277 nmg_edgeuse_with_eg_tabulate(struct bu_ptbl *tab, const struct edge_g_lseg *eg)
2278 
2279 /* can also be edge_g_cnurb */
2280 {
2281  struct bu_list *midway; /* &eu->l2, midway into edgeuse */
2282  struct edgeuse *eu;
2283 
2284  NMG_CK_EDGE_G_EITHER(eg);
2285  (void)bu_ptbl_init(tab, 64, " tab");
2286 
2287  for (BU_LIST_FOR(midway, bu_list, &eg->eu_hd2)) {
2288  eu = BU_LIST_MAIN_PTR(edgeuse, midway, l2);
2289  if (eu->g.lseg_p != eg) bu_bomb("nmg_edgeuse_with_eg_tabulate() eu disavows eg\n");
2290  bu_ptbl_ins_unique(tab, (long *)eu);
2291  }
2292 }
2293 
2294 
2296  char *visited;
2297  struct bu_ptbl *tabl;
2298  point_t pt;
2299  vect_t dir;
2300  struct bn_tol tol;
2301 };
2302 
2303 
2304 /**
2305  * A private support routine for nmg_edgeuse_on_line_tabulate.
2306  * Having just visited an edgeuse, if this is the first time,
2307  * and both vertices of this edgeuse lie within tol of the line,
2308  * add it to the bu_ptbl array.
2309  */
2310 static void
2311 nmg_line_handler(uint32_t *longp, void *state, int UNUSED(unused))
2312 {
2313  register struct edge_line_state *sp = (struct edge_line_state *)state;
2314  register struct edgeuse *eu = (struct edgeuse *)longp;
2315 
2316  NMG_CK_EDGEUSE(eu);
2317  /* If this edgeuse has been processed before, do nothing more */
2318  if (!NMG_INDEX_FIRST_TIME(sp->visited, eu)) return;
2319 
2320  /* If the lines are not generally parallel, don't bother with
2321  * checking the endpoints. This helps reject very short edges
2322  * which are colinear only by virtue of being very small.
2323  */
2324  BN_CK_TOL(&sp->tol);
2325  NMG_CK_EDGE_G_LSEG(eu->g.lseg_p);
2326 
2327  /* sp->tol.para and RT_DOT_TOL are too tight. 0.1 is 5 degrees */
2328  /* These are not unit vectors. */
2329  if (fabs(VDOT(eu->g.lseg_p->e_dir, sp->dir)) <
2330  0.9 * MAGNITUDE(eu->g.lseg_p->e_dir) * MAGNITUDE(sp->dir))
2331  return;
2332 
2333  if (bn_distsq_line3_pt3(sp->pt, sp->dir, eu->vu_p->v_p->vg_p->coord)
2334  > sp->tol.dist_sq)
2335  return;
2336  if (bn_distsq_line3_pt3(sp->pt, sp->dir, eu->eumate_p->vu_p->v_p->vg_p->coord)
2337  > sp->tol.dist_sq)
2338  return;
2339 
2340  /* Both points are within tolerance, add edgeuse to the list */
2341  bu_ptbl_ins(sp->tabl, (long *)longp);
2342 }
2343 
2344 
2345 /**
2346  * Given a pointer to any nmg data structure,
2347  * build an bu_ptbl list which cites every edgeuse
2348  * pointer from there on "down" in the model
2349  * that has both vertices within tolerance of the given line.
2350  *
2351  * XXX This routine is a potential source of major trouble.
2352  * XXX If there are "nearby" edges that "should" be on the list but
2353  * XXX don't make it, then the intersection calculations might
2354  * XXX miss important intersections.
2355  * As an admittedly grubby workaround, use 10X the distance tol here,
2356  * just to get more candidates onto the list.
2357  * The caller will have to wrestle with the added fuzz.
2358  */
2359 void
2360 nmg_edgeuse_on_line_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p, const fastf_t *pt, const fastf_t *dir, const struct bn_tol *tol)
2361 {
2362  struct model *m;
2363  struct edge_line_state st;
2364  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
2365  NULL, NULL, NULL, NULL, NULL,
2366  NULL, NULL, NULL, NULL, NULL,
2367  NULL, nmg_line_handler, NULL, NULL, NULL,
2368  NULL, NULL, NULL, NULL, NULL};
2369  /* handlers.bef_edgeuse = nmg_line_handler; */
2370 
2371  m = nmg_find_model(magic_p);
2372  NMG_CK_MODEL(m);
2373  BN_CK_TOL(tol);
2374 
2375  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2376  st.tabl = tab;
2377  VMOVE(st.pt, pt);
2378  VMOVE(st.dir, dir);
2379 
2380  st.tol = *tol; /* struct copy */
2381 
2382  (void)bu_ptbl_init(tab, 64, " tab");
2383 
2384  nmg_visit(magic_p, &handlers, (void *)&st);
2385 
2386  bu_free((char *)st.visited, "visited[]");
2387 }
2388 
2389 
2391  char *visited;
2392  struct bu_ptbl *edges;
2393  struct bu_ptbl *verts;
2394 };
2395 
2396 
2397 /**
2398  * A private support routine for nmg_e_and_v_tabulate().
2399  *
2400  * Note that an edgeUSE is put on the list, to save one memory dereference
2401  * in the eventual application.
2402  */
2403 static void
2404 nmg_e_handler(uint32_t *longp, void *state, int UNUSED(unused))
2405 {
2406  register struct e_and_v_state *sp = (struct e_and_v_state *)state;
2407  register struct edge *e = (struct edge *)longp;
2408 
2409  NMG_CK_EDGE(e);
2410  /* If this edge has been processed before, do nothing more */
2411  if (!NMG_INDEX_FIRST_TIME(sp->visited, e)) return;
2412 
2413  /* Add to list */
2414  bu_ptbl_ins(sp->edges, (long *)e->eu_p);
2415 }
2416 
2417 
2418 /**
2419  * A private support routine for nmg_e_and_v_tabulate().
2420  */
2421 static void
2422 nmg_v_handler(uint32_t *longp, void *state, int UNUSED(unused))
2423 {
2424  register struct e_and_v_state *sp = (struct e_and_v_state *)state;
2425  register struct vertex *v = (struct vertex *)longp;
2426 
2427  NMG_CK_VERTEX(v);
2428  /* If this vertex has been processed before, do nothing more */
2429  if (!NMG_INDEX_FIRST_TIME(sp->visited, v)) return;
2430 
2431  /* Add to list */
2432  bu_ptbl_ins(sp->verts, (long *)longp);
2433 }
2434 
2435 
2436 /**
2437  * Build lists of all edges (represented by one edgeuse on that edge)
2438  * and all vertices found underneath the
2439  * NMG entity indicated by magic_p.
2440  */
2441 void
2442 nmg_e_and_v_tabulate(struct bu_ptbl *eutab, struct bu_ptbl *vtab, const uint32_t *magic_p)
2443 {
2444  struct model *m;
2445  struct e_and_v_state st;
2446  static const struct nmg_visit_handlers handlers = {NULL, NULL, NULL, NULL, NULL,
2447  NULL, NULL, NULL, NULL, NULL,
2448  NULL, NULL, NULL, NULL, NULL,
2449  NULL, NULL, NULL, nmg_e_handler, NULL,
2450  NULL, NULL, NULL, nmg_v_handler, NULL};
2451  /* handlers.vis_edge = nmg_e_handler; */
2452  /* handlers.vis_vertex = nmg_v_handler; */
2453 
2454  m = nmg_find_model(magic_p);
2455  NMG_CK_MODEL(m);
2456 
2457  st.visited = (char *)bu_calloc(m->maxindex+1, sizeof(char), "visited[]");
2458  st.edges = eutab;
2459  st.verts = vtab;
2460 
2461  (void)bu_ptbl_init(eutab, 64, " eutab");
2462  (void)bu_ptbl_init(vtab, 64, " vtab");
2463 
2464  nmg_visit(magic_p, &handlers, (void *)&st);
2465 
2466  bu_free((char *)st.visited, "visited[]");
2467 }
2468 
2469 
2470 /**
2471  * Given two edgeuses, determine if they share the same edge geometry,
2472  * either topologically, or within tolerance.
2473  *
2474  * Returns -
2475  * 0 two edge geometries are not coincident
2476  * 1 edges geometries are everywhere coincident.
2477  * (For linear edge_g_lseg, the 2 are the same line, within tol.)
2478  */
2479 int
2480 nmg_2edgeuse_g_coincident(const struct edgeuse *eu1, const struct edgeuse *eu2, const struct bn_tol *tol)
2481 {
2482  struct edge_g_lseg *eg1;
2483  struct edge_g_lseg *eg2;
2484 
2485  eg1 = eu1->g.lseg_p;
2486  eg2 = eu2->g.lseg_p;
2487 
2488  if (eg1 == eg2) {
2489  return 1;
2490  }
2491 
2492  /* Ensure that vertices on edge 2 are within tol of e1 */
2493  if (bn_distsq_line3_pt3(eg1->e_pt, eg1->e_dir,
2494  eu2->vu_p->v_p->vg_p->coord) > tol->dist_sq) {
2495  return 0;
2496  }
2497  if (bn_distsq_line3_pt3(eg1->e_pt, eg1->e_dir,
2498  eu2->eumate_p->vu_p->v_p->vg_p->coord) > tol->dist_sq) {
2499  return 0;
2500  }
2501 
2502  return 1;
2503 }
2504 
2505 
2506 /*
2507  * Local Variables:
2508  * mode: C
2509  * tab-width: 8
2510  * indent-tabs-mode: t
2511  * c-file-style: "stroustrup"
2512  * End:
2513  * ex: shiftwidth=4 tabstop=8
2514  */
#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
#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
struct faceuse * nmg_find_fu_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:270
Definition: list.h:118
#define NMG_EDGE_MAGIC
Definition: magic.h:123
#define NMG_SHELL_MAGIC
Definition: magic.h:142
void nmg_edge_g_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2197
int nmg_is_vertex_in_looplist(register const struct vertex *v, const struct bu_list *hd, int singletons)
Definition: nmg_info.c:1754
struct bu_ptbl * tabl
Definition: nmg_info.c:2297
#define NMG_VERTEX_MAGIC
Definition: magic.h:147
int nmg_find_eu_left_non_unit(fastf_t *left, const struct edgeuse *eu)
Definition: nmg_info.c:1408
if lu s
Definition: nmg_mod.c:3860
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 VSETALL(a, s)
Definition: color.c:54
char * visited
Definition: nmg_info.c:2391
struct vertexuse * nmg_find_pt_in_face(const struct faceuse *fu, const fastf_t *pt, const struct bn_tol *tol)
Definition: nmg_info.c:1601
#define M_PI
Definition: fft.h:35
double dist_sq
dist * dist
Definition: tol.h:74
struct edgeuse * nmg_find_eu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:955
#define SMALL_FASTF
Definition: defines.h:342
void nmg_model_bb(fastf_t *min_pt, fastf_t *max_pt, const struct model *m)
Definition: nmg_info.c:166
struct edgeuse * nmg_find_eu_in_face(const struct vertex *v1, const struct vertex *v2, const struct faceuse *fu, const struct edgeuse *eup, int dangling_only)
Definition: nmg_info.c:778
fastf_t mindist
Definition: nmg_info.c:1140
void nmg_edgeuse_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2088
void nmg_pr_eg(const uint32_t *eg_magic_p, char *h)
Definition: nmg_pr.c:488
Header file for the BRL-CAD common definitions.
int bu_ptbl_ins_unique(struct bu_ptbl *b, long *p)
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
int nmg_shell_is_empty(register const struct shell *s)
Definition: nmg_info.c:203
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
#define MAX_FASTF
Definition: defines.h:340
struct edge * nmg_find_e_nearest_pt2(uint32_t *magic_p, const fastf_t *pt2, const fastf_t *mat, const struct bn_tol *tol)
Definition: nmg_info.c:1189
#define NMG_LOOPUSE_MAGIC
Definition: magic.h:130
int nmg_is_edge_in_looplist(const struct edge *e, const struct bu_list *hd)
Definition: nmg_info.c:1885
point_t pt2
Definition: nmg_info.c:1143
struct edgeuse * nmg_find_eu_with_vu_in_lu(const struct loopuse *lu, const struct vertexuse *vu)
Definition: nmg_info.c:970
NMG_CK_LOOPUSE(lu)
struct f2 f2
BU_LIST_DEQUEUE & eu1
Definition: nmg_mod.c:3839
char * visited
Definition: nmg_info.c:2296
struct edgeuse * nmg_findeu(const struct vertex *v1, const struct vertex *v2, const struct shell *s, const struct edgeuse *eup, int dangling_only)
Definition: nmg_info.c:682
Definition: ptbl.h:62
char * visited
Definition: nmg_info.c:1955
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
const struct edgeuse * nmg_find_edge_between_2fu(const struct faceuse *fu1, const struct faceuse *fu2, const struct bn_tol *tol)
Definition: nmg_info.c:1060
struct bn_tol tol
Definition: nmg_info.c:2300
int nmg_loop_is_ccw(const struct loopuse *lu, const fastf_t *norm, const struct bn_tol *tol)
Definition: nmg_info.c:533
struct edge * ep
Definition: nmg_info.c:1141
struct edgeuse * nmg_find_ot_same_eu_of_e(const struct edge *e)
Definition: nmg_info.c:1441
#define RT_G_DEBUG
Definition: raytrace.h:1718
int nmg_loop_is_a_crack(const struct loopuse *lu)
Definition: nmg_info.c:449
#define NMG_LOOP_MAGIC
Definition: magic.h:132
void nmg_edgeuse_on_line_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p, const fastf_t *pt, const fastf_t *dir, const struct bn_tol *tol)
Definition: nmg_info.c:2360
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
#define NMG_FACE_MAGIC
Definition: magic.h:127
struct faceuse * nmg_find_fu_of_lu(const struct loopuse *lu)
Definition: nmg_info.c:283
int bn_dist_pt2_lseg2(fastf_t *dist_sq, fastf_t pca[2], 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...
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
struct shell * nmg_find_s_of_lu(const struct loopuse *lu)
Definition: nmg_info.c:220
struct bu_ptbl * tabl
Definition: nmg_info.c:1956
const struct vertexuse * nmg_loop_touches_self(const struct loopuse *lu)
Definition: nmg_info.c:578
#define V3ARGS(a)
Definition: color.c:56
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
struct vertexuse * nmg_find_v_in_face(const struct vertex *v, const struct faceuse *fu)
Definition: nmg_info.c:1478
void nmg_pr_lu_briefly(const struct loopuse *lu, char *h)
Definition: nmg_pr.c:455
char * visited
Definition: nmg_info.c:1139
static void top()
struct f1 f1
int nmg_is_loop_in_facelist(const struct loop *l, const struct bu_list *fu_hd)
Definition: nmg_info.c:1933
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
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
#define UNUSED(parameter)
Definition: common.h:239
struct edgeuse * nmg_find_e(const struct vertex *v1, const struct vertex *v2, const struct shell *s, const struct edge *ep)
Definition: nmg_info.c:882
goto out
Definition: nmg_mod.c:3846
struct faceuse * nmg_find_fu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:304
#define NMG_REGION_MAGIC
Definition: magic.h:137
Support for uniform tolerances.
Definition: tol.h:71
struct shell * nmg_find_s_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:235
#define BN_CK_TOL(_p)
Definition: tol.h:82
int nmg_is_edge_in_edgelist(const struct edge *e, const struct bu_list *hd)
Definition: nmg_info.c:1867
#define BU_LIST_FIRST_MAGIC(hp)
Definition: list.h:416
int nmg_find_eu_leftvec(fastf_t *left, const struct edgeuse *eu)
Definition: nmg_info.c:1274
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
void nmg_visit(const uint32_t *magicp, const struct nmg_visit_handlers *htab, void *state)
Definition: nmg_visit.c:263
#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
int nmg_is_vertex_a_selfloop_in_shell(const struct vertex *v, const struct shell *s)
Definition: nmg_info.c:1820
mat_t mat
Definition: nmg_info.c:1142
struct vertex * nmg_find_pt_in_model(const struct model *m, const fastf_t *pt, const struct bn_tol *tol)
Definition: nmg_info.c:1708
const struct edgeuse * nmg_faceradial(const struct edgeuse *eu)
Definition: nmg_info.c:995
struct edgeuse * nmg_find_matching_eu_in_s(const struct edgeuse *eu1, const struct shell *s2)
Definition: nmg_info.c:641
struct bu_ptbl * verts
Definition: nmg_info.c:2393
#define BU_LIST_PPREV_CIRC(structure, p)
Definition: list.h:450
#define NMG_EDGE_G_LSEG_MAGIC
Definition: magic.h:122
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
int nmg_2edgeuse_g_coincident(const struct edgeuse *eu1, const struct edgeuse *eu2, const struct bn_tol *tol)
Definition: nmg_info.c:2480
#define NMG_EDGE_G_CNURB_MAGIC
Definition: magic.h:121
struct shell * nmg_find_shell(const uint32_t *magic_p)
Definition: nmg_info.c:119
#define DEBUG_MATH
25 nmg math routines
Definition: raytrace.h:110
struct faceuse * nmg_find_fu_with_fg_in_s(const struct shell *s1, const struct faceuse *fu2)
Definition: nmg_info.c:341
eu1 up magic_p
Definition: nmg_mod.c:3915
#define NMG_VERTEXUSE_A_PLANE_MAGIC
Definition: magic.h:144
void nmg_e_and_v_tabulate(struct bu_ptbl *eutab, struct bu_ptbl *vtab, const uint32_t *magic_p)
Definition: nmg_info.c:2442
int nmg_is_vertex_in_facelist(register const struct vertex *v, const struct bu_list *hd)
Definition: nmg_info.c:1848
double bn_angle_measure(vect_t vec, const vect_t x_dir, const vect_t y_dir)
void bn_vec_perp(vect_t new_vec, const vect_t old_vec)
Definition: mat.c:616
struct vertexuse * nmg_find_v_in_shell(const struct vertex *v, const struct shell *s, int edges_only)
Definition: nmg_info.c:1514
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
struct shell * nmg_find_s_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:249
void nmg_pr_eu_endpoints(const struct edgeuse *eu, char *h)
Definition: nmg_pr.c:600
struct vertex * nmg_find_pt_in_shell(const struct shell *s, const fastf_t *pt, const struct bn_tol *tol)
Definition: nmg_info.c:1634
void nmg_pr_fu_briefly(const struct faceuse *fu, char *h)
Definition: nmg_pr.c:359
NMG_CK_SHELL(s)
void nmg_face_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2247
int bn_pt3_pt3_equal(const point_t a, const point_t b, const struct bn_tol *tol)
const struct edgeuse * nmg_radial_face_edge_in_shell(const struct edgeuse *eu)
Definition: nmg_info.c:1021
const struct bn_tol * tol
Definition: nmg_info.c:1144
#define NMG_FACEUSE_MAGIC
Definition: magic.h:124
struct loopuse * nmg_find_lu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:411
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double fastf_t
Definition: defines.h:300
fastf_t nmg_loop_plane_area2(const struct loopuse *lu, fastf_t *pl, const struct bn_tol *tol)
Definition: nmg_misc.c:1424
const char * bu_identify_magic(uint32_t magic)
eu2
Definition: nmg_mod.c:3875
double bn_distsq_line3_pt3(const point_t pt, const vect_t dir, const point_t a)
#define BU_LIST_NOT_HEAD(p, hp)
Definition: list.h:324
int nmg_is_edge_in_facelist(const struct edge *e, const struct bu_list *hd)
Definition: nmg_info.c:1914
void nmg_edgeuse_with_eg_tabulate(struct bu_ptbl *tab, const struct edge_g_lseg *eg)
Definition: nmg_info.c:2277
struct vertexuse * nmg_find_pt_in_lu(const struct loopuse *lu, const fastf_t *pt, const struct bn_tol *tol)
Definition: nmg_info.c:1555
#define BU_LIST_PNEXT_PNEXT(structure, p)
Definition: list.h:430
struct bu_ptbl * edges
Definition: nmg_info.c:2392
#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
#define UNLIKELY(expression)
Definition: common.h:282
void nmg_vertexuse_normal_tabulate(struct bu_ptbl *tab, const uint32_t *magic_p)
Definition: nmg_info.c:2038
int nmg_is_vertex_in_edgelist(register const struct vertex *v, const struct bu_list *hd)
Definition: nmg_info.c:1735
struct rt_g RTG
Definition: globals.c:39
struct model * nmg_find_model(const uint32_t *magic_p_arg)
Definition: nmg_info.c:57