BRL-CAD
nmg_fcut.c
Go to the documentation of this file.
1 /* N M G _ F C U T . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2007-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_fcut.c
23  *
24  * After two faces have been intersected, cut or join loops crossed
25  * by the line of intersection. (Formerly nmg_comb.c)
26  *
27  * The main external routine here is nmg_face_cutjoin().
28  *
29  * The line of intersection ("ray") will divide the face into two sets
30  * of loops.
31  * No one loop may cross the ray after this routine is finished.
32  * (Current optimization may remove this property).
33  *
34  * Intersection points of significance to the other face but not yet
35  * part of the current face's geometry are denoted by a vu on the ray
36  * list, which points to a loop of a single vertex. These points
37  * need to be incorporated into the final face.
38  *
39  */
40 /** @} */
41 
42 #include "common.h"
43 
44 #include <stdlib.h>
45 #include <string.h>
46 #include <math.h>
47 #include "bio.h"
48 
49 #include "bu/sort.h"
50 #include "vmath.h"
51 #include "nmg.h"
52 #include "raytrace.h"
53 
54 
55 #define PLOT_BOTH_FACES 1
56 
57 
58 /* States of the state machine */
59 #define NMG_STATE_ERROR 0
60 #define NMG_STATE_OUT 1
61 #define NMG_STATE_ON_L 2
62 #define NMG_STATE_ON_R 3
63 #define NMG_STATE_ON_B 4
64 #define NMG_STATE_ON_N 5
65 #define NMG_STATE_IN 6
66 static const char *nmg_state_names[] = {
67  "*ERROR*",
68  "out",
69  "on_L",
70  "on_R",
71  "on_both", /* "hole" crack */
72  "on_neither", /* "non-hole" crack */
73  "in",
74  "TOOBIG"
75 };
76 
77 
78 #define NMG_E_ASSESSMENT_LEFT 0
79 #define NMG_E_ASSESSMENT_RIGHT 1
80 #define NMG_E_ASSESSMENT_ON_FORW 2
81 #define NMG_E_ASSESSMENT_ON_REV 3
82 #define NMG_E_ASSESSMENT_ERROR 4 /* risky */
83 
84 #define NMG_V_ASSESSMENT_LONE 16
85 #define NMG_V_ASSESSMENT_ERROR 17
86 #define NMG_V_COMB(_p, _n) (((_p)<<2)|(_n))
87 
88 /* Extract previous and next assessments from combined version */
89 #define NMG_V_ASSESSMENT_PREV(_a) (((_a)>>2)&3)
90 #define NMG_V_ASSESSMENT_NEXT(_a) ((_a)&3)
91 
92 static const char *nmg_v_assessment_names[32] = {
93  "Left, Left",
94  "Left, Right",
95  "Left, On_Forw",
96  "Left, On_Rev",
97  "Right, Left",
98  "Right, Right",
99  "Right, On_Forw",
100  "Right, On_Rev",
101  "On_Forw, Left",
102  "On_Forw, Right",
103  "On_Forw, On_Forw",
104  "On_Forw, On_Rev",
105  "On_Rev, Left",
106  "On_Rev, Right",
107  "On_Rev, On_Forw",
108  "On_Rev, On_Rev",
109  "LONE_V", /* 16 */
110  "V_ERROR", /* 17 */
111  "?18",
112  "?19",
113  "?20",
114  "?21",
115  "?22",
116  "?23",
117  "?24",
118  "?25",
119  "?26",
120  "?27",
121  "?28",
122  "?29",
123  "?30",
124  "?31"
125 };
126 #define NMG_LEFT_LEFT NMG_V_COMB(NMG_E_ASSESSMENT_LEFT, NMG_E_ASSESSMENT_LEFT)
127 #define NMG_LEFT_RIGHT NMG_V_COMB(NMG_E_ASSESSMENT_LEFT, NMG_E_ASSESSMENT_RIGHT)
128 #define NMG_LEFT_ON_FORW NMG_V_COMB(NMG_E_ASSESSMENT_LEFT, NMG_E_ASSESSMENT_ON_FORW)
129 #define NMG_LEFT_ON_REV NMG_V_COMB(NMG_E_ASSESSMENT_LEFT, NMG_E_ASSESSMENT_ON_REV)
130 #define NMG_RIGHT_LEFT NMG_V_COMB(NMG_E_ASSESSMENT_RIGHT, NMG_E_ASSESSMENT_LEFT)
131 #define NMG_RIGHT_RIGHT NMG_V_COMB(NMG_E_ASSESSMENT_RIGHT, NMG_E_ASSESSMENT_RIGHT)
132 #define NMG_RIGHT_ON_FORW NMG_V_COMB(NMG_E_ASSESSMENT_RIGHT, NMG_E_ASSESSMENT_ON_FORW)
133 #define NMG_RIGHT_ON_REV NMG_V_COMB(NMG_E_ASSESSMENT_RIGHT, NMG_E_ASSESSMENT_ON_REV)
134 #define NMG_ON_FORW_LEFT NMG_V_COMB(NMG_E_ASSESSMENT_ON_FORW, NMG_E_ASSESSMENT_LEFT)
135 #define NMG_ON_FORW_RIGHT NMG_V_COMB(NMG_E_ASSESSMENT_ON_FORW, NMG_E_ASSESSMENT_RIGHT)
136 #define NMG_ON_FORW_ON_FORW NMG_V_COMB(NMG_E_ASSESSMENT_ON_FORW, NMG_E_ASSESSMENT_ON_FORW)
137 #define NMG_ON_FORW_ON_REV NMG_V_COMB(NMG_E_ASSESSMENT_ON_FORW, NMG_E_ASSESSMENT_ON_REV)
138 #define NMG_ON_REV_LEFT NMG_V_COMB(NMG_E_ASSESSMENT_ON_REV, NMG_E_ASSESSMENT_LEFT)
139 #define NMG_ON_REV_RIGHT NMG_V_COMB(NMG_E_ASSESSMENT_ON_REV, NMG_E_ASSESSMENT_RIGHT)
140 #define NMG_ON_REV_ON_FORW NMG_V_COMB(NMG_E_ASSESSMENT_ON_REV, NMG_E_ASSESSMENT_ON_FORW)
141 #define NMG_ON_REV_ON_REV NMG_V_COMB(NMG_E_ASSESSMENT_ON_REV, NMG_E_ASSESSMENT_ON_REV)
142 #define NMG_LONE NMG_V_ASSESSMENT_LONE
143 
144 static const char *nmg_e_assessment_names[6] = {
145  "LEFT",
146  "RIGHT",
147  "ON_FORW",
148  "ON_REV",
149  "E_ERROR",
150  "E_5?"
151 };
152 
153 
154 /*
155  * Action entries for the state transition tables
156  */
157 #define NMG_ACTION_ERROR 0
158 #define NMG_ACTION_NONE 1
159 #define NMG_ACTION_NONE_OPTIM 2
160 #define NMG_ACTION_VFY_EXT 3
161 #define NMG_ACTION_VFY_MULTI 4
162 #define NMG_ACTION_LONE_V_ESPLIT 5
163 #define NMG_ACTION_LONE_V_JAUNT 6
164 #define NMG_ACTION_CUTJOIN 7
165 static const char *action_names[] = {
166  "*ERROR*",
167  "NONE",
168  "NONE_OPTIM",
169  "VFY_EXT",
170  "VFY_MULTI",
171  "LONE_V_ESPLIT",
172  "LONE_V_JAUNT",
173  "CUTJOIN",
174  "*TOOBIG*"
175 };
176 
177 
178 /* The "ray" here is the intersection line between two faces */
180  uint32_t magic;
181  struct vertexuse **vu; /* ptr to vu array */
182  int nvu; /* len of vu[] */
183  point_t pt; /* The ray */
184  vect_t dir;
185  struct edge_g_lseg *eg_p; /* Edge geom of the ray */
186  struct shell *sA;
187  struct shell *sB;
188  struct faceuse *fu1;
189  struct faceuse *fu2;
190  vect_t left; /* points left of ray, on face */
191  int state; /* current (old) state */
192  int last_action; /* last action taken */
193  vect_t ang_x_dir; /* x axis for angle measure */
194  vect_t ang_y_dir; /* y axis for angle measure */
195  const struct bn_tol *tol;
196 };
197 #define NMG_RAYSTATE_MAGIC 0x54322345
198 #define NMG_CK_RAYSTATE(_p) NMG_CKMAG(_p, NMG_RAYSTATE_MAGIC, "nmg_ray_state")
199 
200 struct loop_cuts {
201  struct loopuse *lu;
202  struct vertexuse *vu1;
203  struct vertexuse *vu2;
204 };
205 int
207  int pos,
208  int multi,
209  int other_rs_state);
210 
211 /**
212  * Sort list of hit points (vertexuse's) in fu1 (bu_ptbl 'b') on plane
213  * of fu2 (defined by pt+dir), by increasing distance, vertex ptr, and
214  * vu ptr. Eliminate duplications of vu at same distance. (Actually,
215  * a given vu should show up at exactly 1 distance!) The line of
216  * intersection is pt + t * dir.
217  *
218  * For now, a bubble-sort is used, because the list should not have more
219  * than a few hundred entries on it.
220  */
221 HIDDEN void
222 ptbl_vsort(struct bu_ptbl *b, fastf_t *pt, fastf_t *dir, fastf_t *mag, fastf_t dist_tol)
223 /* table of vertexuses on intercept line */
224 /* unused? */
225 /* unused? */
226 
227 
228 {
229  register struct vertexuse **vu;
230  register int i, j;
231 
232  vu = (struct vertexuse **)b->buffer;
233 
234  if (RTG.NMG_debug) {
235  /* Ensure that distance from points to ray is reasonable */
236  for (i = 0; i < b->end; ++i) {
237  fastf_t dist;
238 
239  NMG_CK_VERTEXUSE(vu[i]);
240  dist = bn_dist_line3_pt3(pt, dir, vu[i]->v_p->vg_p->coord);
241  if (dist > dist_tol) {
242  bu_log("WARNING ptbl_vsort() vu=%p point off line by %e %g*tol, tol=%e\n",
243  (void *)vu[i], dist,
244  dist/dist_tol, dist_tol);
245  if (RTG.NMG_debug&DEBUG_VU_SORT) {
246  VPRINT(" vu", vu[i]->v_p->vg_p->coord);
247  VPRINT(" pt", pt);
248  VPRINT(" dir", dir);
249  }
250  }
251  if (dist > 100*dist_tol) {
252  bu_log("ERROR ptbl_vsort() vu=%p point off line by %g > 100*dist_tol\n",
253  (void *)vu[i], dist);
254  bu_bomb("ptbl_vsort()\n");
255  }
256  }
257  }
258 
259  /* check vertexuses and compute distance from start of line */
260  for (i = 0; i < b->end; ++i) {
261  vect_t vect;
262  NMG_CK_VERTEXUSE(vu[i]);
263 
264  if (mag[i] > MAX_FASTF - SMALL_FASTF) {
265  VSUB2(vect, vu[i]->v_p->vg_p->coord, pt);
266  mag[i] = VDOT(vect, dir);
267  }
268 
269  /* Find previous vu's at "same" distance, within dist_tol */
270  for (j = 0; j < i; j++) {
271  register fastf_t tmag;
272 
273  tmag = mag[i] - mag[j];
274  if (tmag < -dist_tol) continue;
275  if (tmag > dist_tol) continue;
276  /* Nearly equal at same vertex */
277  if (!ZERO(mag[i] - mag[j])
278  && vu[i]->v_p == vu[j]->v_p)
279  {
280  bu_log("ptbl_vsort: forcing vu=%p & vu=%p mag equal\n", (void *)vu[i], (void *)vu[j]);
281  mag[j] = mag[i]; /* force equal */
282  }
283  }
284  }
285 
286  for (i = 0; i < b->end - 1; ++i) {
287  for (j = i+1; j < b->end; ++j) {
288 
289  if (mag[i] < mag[j]) continue;
290  if (ZERO(mag[i] - mag[j])) {
291  if (vu[i]->v_p < vu[j]->v_p) continue;
292  if (vu[i]->v_p == vu[j]->v_p) {
293  if (vu[i] < vu[j]) continue;
294  if (vu[i] == vu[j]) {
295  int last = b->end - 1;
296  /* vu duplication, eliminate! */
297  bu_log("ptbl_vsort: vu duplication eliminated\n");
298  if (j >= last) {
299  /* j is last element */
300  b->end--;
301  break;
302  }
303  /* rewrite j with last element */
304  vu[j] = vu[last];
305  mag[j] = mag[last];
306  b->end--;
307  /* Repeat this index */
308  j--;
309  continue;
310  }
311  /* vu[i] > vu[j], fall through */
312  }
313  /* vu[i]->v_p > vu[j]->v_p, fall through */
314  }
315  /* mag[i] > mag[j] */
316 
317  /* exchange [i] and [j] */
318  {
319  register struct vertexuse *tvu;
320  tvu = vu[i];
321  vu[i] = vu[j];
322  vu[j] = tvu;
323  }
324 
325  {
326  register fastf_t tmag;
327  tmag = mag[i];
328  mag[i] = mag[j];
329  mag[j] = tmag;
330  }
331  }
332  }
333 }
334 
335 
336 /**
337  * As an automatic check for the intersector failing to find
338  * all intersections, check all the vertices on the intersection line.
339  * For each one, find all the other uses in this faceuse, and
340  * if they are not also listed on the line, they were overlooked.
341  *
342  * This does not catch _all_ possible mistakes, but does catch some.
343  */
344 int
345 nmg_ck_vu_ptbl(struct bu_ptbl *p, struct faceuse *fu)
346 {
347  struct vertex *v;
348  struct vertexuse *vu;
349  struct vertexuse *tvu;
350  struct faceuse *tfu;
351  int i;
352  int ret = 0;
353 
354  BU_CK_PTBL(p);
355  NMG_CK_FACEUSE(fu);
356 
357 top:
358  for (i = 0; i < BU_PTBL_END(p); i++) {
359  vu = (struct vertexuse *)BU_PTBL_GET(p, i);
360  NMG_CK_VERTEXUSE(vu);
361  v = vu->v_p;
362  NMG_CK_VERTEX(v);
363  tfu = nmg_find_fu_of_vu(vu);
364  if (tfu != fu) {
365  bu_log("ERROR: vu=%p v=%p up_fu=%p != arg_fu=%p\n",
366  (void *)vu, (void *)v, (void *)tfu, (void *)fu);
367  bu_bomb("nmg_ck_vu_ptbl() intersect list is confused about which face it belongs to.\n");
368  }
369  for (BU_LIST_FOR(tvu, vertexuse, &v->vu_hd)) {
370  NMG_CK_VERTEXUSE(tvu);
371  if (tvu == vu) continue;
372  if ((tfu = nmg_find_fu_of_vu(tvu)) == (struct faceuse *)NULL)
373  continue;
374  if (tfu != fu) continue;
375  /* tvu is in fu. Is tvu on the line? */
376  if (bu_ptbl_locate(p, (long *)&tvu->l.magic) >= 0) continue;
377  /* No, not on list */
378  bu_log("ERROR: vu=%p v=%p %s=%p is on isect line, tvu=%p %s=%p isn't.\n",
379  (void *)vu, (void *)v,
380  bu_identify_magic(*vu->up.magic_p),
381  (void *)vu->up.magic_p,
382  (void *)tvu,
383  bu_identify_magic(*tvu->up.magic_p),
384  (void *)tvu->up.magic_p);
385  /* XXX bomb here? */
386  nmg_pr_ptbl("intersect line vu table", p, 1);
387  bu_bomb("nmg_ck_vu_ptbl() missing vertexuse\n");
388 /* XXXXXXXXXXXXXXXXXXXXXXXX Horrible temporizing measure */
389  /* Another strategy: add it in! */
390  (void)bu_ptbl_ins(p, (long *)&tvu->l.magic);
391  ret++;
392  goto top;
393  }
394  }
395  if (ret)bu_log("nmg_ck_vu_ptbl() ret=%d\n", ret);
396  return ret;
397 }
398 
399 
400 /**
401  * Given a vertexuse from a loop which lies in a plane,
402  * compute the vector 'vec' from the previous vertex to this one.
403  * Using two perpendicular vectors (x_dir and y_dir) which both lie
404  * in the plane of the loop, return the angle (in radians) of 'vec'
405  * from x_dir, going CCW around the perpendicular x_dir CROSS y_dir.
406  *
407  * x_dir is -ray_dir
408  * y_dir points right.
409  *
410  * Returns -
411  * vec == x_dir returns 0,
412  * vec == y_dir returns pi/2,
413  * vec == -x_dir returns pi,
414  * vec == -y_dir returns 3*pi/2.
415  * 0.0 if unable to compute 'vec'
416  */
417 double
418 nmg_vu_angle_measure(struct vertexuse *vu, fastf_t *x_dir, fastf_t *y_dir, int assessment, int in)
419 
420 
421 /* 1 = inbound edge, 0 = outbound edge */
422 {
423  struct loopuse *lu;
424  struct edgeuse *this_eu;
425  struct edgeuse *prev_eu;
426  vect_t vec;
427  fastf_t ang;
428  int this_ass;
429 
430  NMG_CK_VERTEXUSE(vu);
431  if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
432  return 0; /* Unable to compute 'vec' */
433  }
434 
435  /*
436  * For consistency, if entry edge is ON the ray,
437  * force the angles to be exact, don't compute them.
438  */
439  if (in)
440  this_ass = NMG_V_ASSESSMENT_PREV(assessment);
441  else
442  this_ass = NMG_V_ASSESSMENT_NEXT(assessment);
443  if (this_ass == NMG_E_ASSESSMENT_ON_FORW) {
444  if (in) ang = 0.0; /* zero angle */
445  else ang = M_PI; /* 180 degrees */
446  if (RTG.NMG_debug&DEBUG_VU_SORT)
447  bu_log("nmg_vu_angle_measure: NMG_E_ASSESSMENT_ON_FORW, ang=%g\n", ang);
448  return ang;
449  }
450  if (this_ass == NMG_E_ASSESSMENT_ON_REV) {
451  if (in) ang = M_PI; /* 180 degrees */
452  else ang = 0.0; /* zero angle */
453  if (RTG.NMG_debug&DEBUG_VU_SORT)
454  bu_log("nmg_vu_angle_measure: NMG_E_ASSESSMENT_ON_REV, ang=%g\n", ang);
455  return ang;
456  }
457 
458  /*
459  * Compute the angle
460  */
461  lu = nmg_find_lu_of_vu(vu);
462  NMG_CK_LOOPUSE(lu);
463  this_eu = nmg_find_eu_with_vu_in_lu(lu, vu);
464  prev_eu = this_eu;
465  do {
466  prev_eu = in ? BU_LIST_PPREV_CIRC(edgeuse, prev_eu) :
467  BU_LIST_PNEXT_CIRC(edgeuse, prev_eu);
468  if (prev_eu == this_eu) {
469  if (RTG.NMG_debug&DEBUG_VU_SORT)
470  bu_log("nmg_vu_angle_measure: prev eu is this eu, ang=0\n");
471  return 0; /* Unable to compute 'vec' */
472  }
473  /* Skip any edges that stay on this vertex */
474  } while (prev_eu->vu_p->v_p == this_eu->vu_p->v_p);
475 
476  /* in==1 Get vec for inbound edge, but pointing away from vert. */
477  /* in==0 "prev" is really next, so this is departing vec */
478  VSUB2(vec, prev_eu->vu_p->v_p->vg_p->coord, vu->v_p->vg_p->coord);
479 
480  ang = bn_angle_measure(vec, x_dir, y_dir);
481  if (RTG.NMG_debug&DEBUG_VU_SORT)
482  bu_log("nmg_vu_angle_measure: measured angle=%e\n", ang*RAD2DEG);
483 
484  /*
485  * Since the entry edge is not on the ray, ensure the
486  * angles are not exactly 0 or pi.
487  */
488 #define RADIAN_TWEEK 1.0e-14 /* low bits of double prec., re: 6.28... */
489  if (ZERO(ang)) {
490  if (this_ass == NMG_E_ASSESSMENT_RIGHT) {
491  ang = RADIAN_TWEEK;
492  } else {
493  /* Assuming NMG_E_ASSESSMENT_LEFT */
494  ang = M_2PI - RADIAN_TWEEK;
495  }
496  } else if (ZERO(ang - M_PI)) {
497  if (this_ass == NMG_E_ASSESSMENT_RIGHT) {
498  ang = M_PI - RADIAN_TWEEK;
499  } else {
500  ang = M_PI + RADIAN_TWEEK;
501  }
502  }
503 
504  /*
505  * Also, ensure computed angle and topological assessment agree
506  * about which side of the ray this edge is on.
507  */
508  if (ang > M_PI) {
509  if (this_ass != NMG_E_ASSESSMENT_LEFT) {
510  bu_log("*** ERROR topology/geometry conflict, ang=%e, ass=%s\n",
511  ang*RAD2DEG,
512  nmg_e_assessment_names[this_ass]);
513  }
514  } else if (ang < M_PI) {
515  if (this_ass != NMG_E_ASSESSMENT_RIGHT) {
516  bu_log("*** ERROR topology/geometry conflict, ang=%e, ass=%s\n",
517  ang*RAD2DEG,
518  nmg_e_assessment_names[this_ass]);
519  }
520  }
521  if (RTG.NMG_debug&DEBUG_VU_SORT)
522  bu_log(" final ang=%g (%e), vec=(%g, %g, %g)\n", ang*RAD2DEG, ang*RAD2DEG, V3ARGS(vec));
523  return ang;
524 }
525 
526 
527 int
528 nmg_is_v_on_rs_list(const struct nmg_ray_state *rs, const struct vertex *v)
529 {
530  register int i;
531 
532  NMG_CK_VERTEX(v);
533  for (i=rs->nvu-1; i >= 0; i--) {
534  if (!rs->vu[i]) continue;
535  if (rs->vu[i]->v_p == v) return i;
536  }
537  return -1;
538 }
539 
540 
541 /**
542  * The current vertex (eu->vu_p) is on the line of intersection.
543  * Assess the indicated edge, to see if it lies on the line of
544  * intersection, or departs towards the left or right.
545  *
546  * There is no need to look more than one edge forward or backward.
547  * Even if there are edges which loop around to the same vertex
548  * (with a different vertexuse), that (0-length) edge is ON the ray.
549  */
550 int
551 nmg_assess_eu(struct edgeuse *eu, int forw, struct nmg_ray_state *rs, int pos)
552 {
553  struct vertex *v;
554  struct vertex *otherv = (struct vertex *)0;
555  struct edgeuse *othereu;
556  vect_t heading;
557  int ret;
558  register int i;
559 
560  VSETALL(heading, 0);
561 
562  NMG_CK_EDGEUSE(eu);
563  NMG_CK_RAYSTATE(rs);
564  BN_CK_TOL(rs->tol);
565  v = eu->vu_p->v_p;
566  NMG_CK_VERTEX(v);
567  othereu = eu;
568  if (forw) {
569  othereu = BU_LIST_PNEXT_CIRC(edgeuse, othereu);
570  } else {
571  othereu = BU_LIST_PPREV_CIRC(edgeuse, othereu);
572  }
573  if (othereu == eu) {
574  /* Back to where search started */
575  if (RTG.NMG_debug) nmg_pr_eu(eu, NULL);
576  bu_bomb("nmg_assess_eu() no edges leave the vertex!\n");
577  }
578  otherv = othereu->vu_p->v_p;
579  if (otherv == v) {
580  /* Edge stays on this vertex -- can't tell if forw or rev! */
581  if (RTG.NMG_debug) nmg_pr_eu(eu, NULL);
582  bu_bomb("nmg_assess_eu() edge runs from&to same vertex!\n");
583  }
584 
585  /* If the other vertex is mentioned anywhere on the ray's vu list,
586  * then the edge is "on" the ray.
587  * Match against vertex (rather than vertexuse) because cut/join
588  * operations may have changed the particular vertexuse pointer.
589  */
590  if ((i = nmg_is_v_on_rs_list(rs, otherv)) > -1) {
591  struct vertex *farv;
592  struct edgeuse *fareu;
593  int start, end;
594 
595  fareu = othereu;
596  again:
597  /* Edge's far end is ON the ray. Which way does it go? */
598  if (RTG.NMG_debug&DEBUG_FCUT)
599  bu_log("eu ON ray: vu[%d]=%p, other:vu[%d]=%p\n",
600  pos, (void *)rs->vu[pos], i, (void *)otherv);
601 
602  /*
603  * As an attempt at fixing the ON/ON vertexuse problem,
604  * look further forw/back along the edgeuse list,
605  * as long as it shares the same edge geometry.
606  * If not on list, use *that* vertex to assess left/right.
607  */
608  if (forw) {
609  fareu = BU_LIST_PNEXT_CIRC(edgeuse, fareu);
610  } else {
611  fareu = BU_LIST_PPREV_CIRC(edgeuse, fareu);
612  }
613  if (fareu == eu) goto really_on; /* All eu's are ON! */
614  if (fareu->g.lseg_p != eu->g.lseg_p) goto really_on;
615  farv = fareu->vu_p->v_p;
616  if (RTG.NMG_debug&DEBUG_FCUT)
617  bu_log("nmg_assess_eu() farv = %p, on_index=%d\n", (void *)farv, nmg_is_v_on_rs_list(rs, farv));
618  if (nmg_is_v_on_rs_list(rs, farv) > -1) {
619  /* farv is ON list, try going further back */
620  goto again;
621  }
622  /* farv is not ON list, assess _it_ */
623  /* XXX Need to remove othervu from the list! */
624  otherv = farv;
625  if (RTG.NMG_debug&DEBUG_FCUT)
626  bu_log("nmg_assess_eu() assessing farv\n");
627  goto left_right;
628 
629  /* Compute edge vector, for purposes of orienting answer */
630  really_on:
631  /*
632  * There are 2 ways of determining the assessment:
633  * edge direction DOT ray direction, above, and
634  * comparing the subscripts of the two vertexuses
635  * (which translates to comparing dists along ray).
636  */
637  if (i > pos) {
638  if (forw)
640  else
642  start = pos+1;
643  end = i;
644  } else {
645  /* i < pos (They can't be equal) */
646  if (forw)
648  else
650  start = i+1;
651  end = pos;
652  }
653 
654  /*
655  * Verify that any other vertexuses on the intersect line
656  * along the ON edge are uses of one of the two edge
657  * endpoints. Otherwise, something awful has happened.
658  */
659  for (i=start; i<end; i++) {
660  int j;
661  if (!rs->vu[i]) continue;
662  if (rs->vu[i]->v_p == v ||
663  rs->vu[i]->v_p == otherv)
664  continue;
665  if (RTG.NMG_debug&DEBUG_FCUT) {
666  bu_log("In edge interval (%d, %d), ON vertexuse [%d] = %p appears?\n",
667  start-1, end, i, (void *)rs->vu[i]);
668  for (j=start-1; j<=end; j++) {
669  if (!rs->vu[i]) continue;
670  bu_log(" %d ", j);
671  nmg_pr_vu_briefly(rs->vu[j], (char *)0);
672  }
673  bu_log("nmg_assess_eu(): ON vertexuse in middle of edge?\n");
674  }
675  /* Leave it for nmg_onon_fix() to fix */
677  return -i; /* Special flag to nmg_onon_fix() */
678  }
679  goto out;
680  }
681 
682  /*
683  * Since other vertex does not lie anywhere on line of intersection,
684  * the edge must lie to one side or the other of the ray.
685  * Check vector from v to otherv against "left" vector.
686  */
687 left_right:
688  VSUB2(heading, otherv->vg_p->coord, v->vg_p->coord);
689  if (MAGSQ(heading) <= SMALL_FASTF) bu_bomb("nmg_assess_eu() null heading 2\n");
690  if (VDOT(heading, rs->left) < 0) {
692  } else {
693  ret = NMG_E_ASSESSMENT_LEFT;
694  }
695 out:
696  if (RTG.NMG_debug&DEBUG_FCUT) {
697  bu_log("nmg_assess_eu(%p, fw=%d, pos=%d) v=%p otherv=%p: %s\n",
698  (void *)eu, forw, pos, (void *)v, (void *)otherv,
699  nmg_e_assessment_names[ret]);
700  bu_log(" v(%g, %g, %g) other(%g, %g, %g)\n",
701  V3ARGS(v->vg_p->coord), V3ARGS(otherv->vg_p->coord));
702  bu_log(" rs->left(%g, %g, %g) heading(%g, %g, %g)\n",
703  V3ARGS(rs->left), V3ARGS(heading));
704  }
705  return ret;
706 }
707 
708 
709 int
710 nmg_assess_vu(struct nmg_ray_state *rs, int pos)
711 {
712  struct vertexuse *vu;
713  struct loopuse *lu;
714  struct edgeuse *this_eu;
715  int next_ass;
716  int prev_ass;
717  int ass;
718 
719  NMG_CK_RAYSTATE(rs);
720  vu = rs->vu[pos];
721  NMG_CK_VERTEXUSE(vu);
722  if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
723  return NMG_V_ASSESSMENT_LONE;
724  }
725  if ((lu = nmg_find_lu_of_vu(vu)) == (struct loopuse *)0)
726  bu_bomb("nmg_assess_vu: no lu\n");
727  this_eu = nmg_find_eu_with_vu_in_lu(lu, vu);
728  /* Couldn't this have been this_eu = vu->up.eu_p ? */
729  if (this_eu != vu->up.eu_p)
730  bu_log("nmg_assess_vu() eu mis-match? %p %p\n", (void *)this_eu, (void *)vu->up.eu_p);
731  prev_ass = nmg_assess_eu(this_eu, 0, rs, pos);
732  next_ass = nmg_assess_eu(this_eu, 1, rs, pos);
733  if (prev_ass < 0 || next_ass < 0) {
735  } else {
736  ass = NMG_V_COMB(prev_ass, next_ass);
737  }
738 
739  /*
740  * If the vu assessment is
741  * NMG_ON_REV_ON_FORW or NMG_ON_FORW_ON_REV,
742  * ensure that other end of both eu's is same vertex.
743  * If not, it's an intersector error, and will confuse our caller.
744  */
745  if (ass==NMG_ON_REV_ON_FORW || ass==NMG_ON_FORW_ON_REV) {
746  struct edgeuse *prev;
747  struct edgeuse *next;
748  prev = BU_LIST_PPREV_CIRC(edgeuse, this_eu);
749  next = BU_LIST_PNEXT_CIRC(edgeuse, this_eu);
750  if (prev->vu_p->v_p != next->vu_p->v_p) {
751  bu_log("nmg_assess_vu() %s, v=%p, prev_v=%p, next_v=%p\n",
752  nmg_v_assessment_names[ass],
753  (void *)this_eu->vu_p->v_p,
754  (void *)prev->vu_p->v_p, (void *)next->vu_p->v_p);
755  bu_log("nmg_assess_vu() ON/ON edgeuse ends on different vertices.\n");
756  VPRINT("vu ", this_eu->vu_p->v_p->vg_p->coord);
757  VPRINT("prev", prev->vu_p->v_p->vg_p->coord);
758  VPRINT("next", next->vu_p->v_p->vg_p->coord);
759 
760  /* See how far off the line they are */
761  bu_log("vu dist=%e, next dist=%e, tol=%e\n",
762  bn_dist_line3_pt3(rs->pt, rs->dir, this_eu->vu_p->v_p->vg_p->coord),
763  bn_dist_line3_pt3(rs->pt, rs->dir, prev->vu_p->v_p->vg_p->coord),
764  rs->tol->dist);
765  bu_bomb("nmg_assess_vu() ON/ON edgeuse ends on different vertices.\n");
766  }
767  }
768  if (RTG.NMG_debug&DEBUG_FCUT) {
769  bu_log("nmg_assess_vu() vu[%d]=%p, v=%p: %s\n",
770  pos, (void *)vu, (void *)vu->v_p, nmg_v_assessment_names[ass]);
771  }
772  return ass;
773 }
774 
775 
776 struct nmg_vu_stuff {
777  struct vertexuse *vu;
783  fastf_t lo_ang; /* small if RIGHT, large if LEFT */
785  int seq; /* seq # after lsp->min_vu */
786  int wedge_class; /* WEDGE_LEFT, etc. */
787 };
789  struct loopuse *lu;
791  struct vertexuse *min_vu;
792  int n_vu_in_loop; /* # ray vu's in this loop */
793 };
794 
795 
796 #define WEDGE_LEFT 0
797 #define WEDGE_CROSS 1
798 #define WEDGE_RIGHT 2
799 #define WEDGE_ON 3
800 #define WEDGECLASS2STR(_cl) nmg_wedgeclass_string[(_cl)]
801 static const char *nmg_wedgeclass_string[] = {
802  "LEFT",
803  "CROSS",
804  "RIGHT",
805  "ON",
806  "???"
807 };
808 
809 
810 void
811 nmg_pr_vu_stuff(const struct nmg_vu_stuff *vs)
812 {
813  bu_log("nmg_pr_vu_stuff(%p) vu=%p, loop_index=%d, lsp=%p\n",
814  (void *)vs, (void *)vs->vu, vs->loop_index, (void *)vs->lsp);
815  bu_log(" in_vu_angle=%g, out_vu_angle=%g, min_vu_dot=%g\n",
816  vs->in_vu_angle, vs->out_vu_angle, vs->min_vu_dot);
817  bu_log(" lo_ang=%g, hi_ang=%g, seq=%d, wedge_class=%s\n",
818  vs->lo_ang, vs->hi_ang, vs->seq,
820 }
821 
822 
823 /**
824  * 0 degrees is to the rear (ON_REV), 90 degrees is to the RIGHT,
825  * 180 is ON_FORW, 270 is to the LEFT.
826  * Determine if the given wedge is entirely to the left or right of
827  * the ray, or if it crosses.
828  *
829  * "halfway X" (ha, hb) have these properties:
830  * < 0 (==> X < 180) RIGHT
831  * > 0 (==> X > 180) LEFT
832  * ==0 (==> X == 180) ON_FORW
833  *
834  * Returns -
835  * WEDGE_LEFT
836  * WEDGE_CROSSING
837  * WEDGE_RIGHT
838  * WEDGE_ON
839  */
840 int
841 nmg_wedge_class(int ass, double a, double b)
842 /* assessment of two edges forming wedge */
843 
844 
845 {
846  double ha, hb;
847  register int ret;
848 
849  ha = a - 180;
850  hb = b - 180;
851 
853  ret = WEDGE_ON;
854  goto out;
855  }
857  ret = WEDGE_ON;
858  goto out;
859  }
860 
861  if (NEAR_ZERO(ha, .01)) {
862  /* A is on the ray, within tol */
863  if (NEAR_ZERO(hb, .01)) {
864  /* B is on the ray, within tol */
865  /* This is a 0-angle wedge entering & leaving.
866  * This is not WEDGE_ON
867  * Call it WEDGE_CROSS.
868  */
869  if (RTG.NMG_debug&DEBUG_VU_SORT)
870  bu_log("nmg_wedge_class() 0-angle wedge\n");
871  ret = WEDGE_CROSS;
872  goto out;
873  }
874  if (hb < 0) {
875  ret = WEDGE_RIGHT;
876  goto out;
877  }
878  ret = WEDGE_LEFT;
879  goto out;
880  }
881  if (ha < 0) {
882  /* A is to the right */
883  if (hb <= 0) {
884  ret = WEDGE_RIGHT;
885  goto out;
886  }
887  ret = WEDGE_CROSS;
888  goto out;
889  }
890  /* ha is > 0, A is to the left */
891  if (NEAR_ZERO(hb, .01)) {
892  /* A is left, B is ON_FORW (180) */
893  ret = WEDGE_LEFT;
894  goto out;
895  }
896  if (hb >= 0) {
897  /* A is left, B is LEFT */
898  ret = WEDGE_LEFT;
899  goto out;
900  }
901  /* A is left, B is RIGHT */
902  ret = WEDGE_CROSS;
903 out:
904  if (RTG.NMG_debug&DEBUG_VU_SORT) {
905  bu_log("nmg_wedge_class(%g, %g) = %s\n",
906  a, b, WEDGECLASS2STR(ret));
907  }
908  return ret;
909 }
910 
911 
912 static const char *nmg_wedge2_string[] = {
913  "WEDGE2_OVERLAP",
914  "WEDGE2_NO_OVERLAP",
915  "WEDGE2_AB_IN_CD",
916  "WEDGE2_CD_IN_AB",
917  "WEDGE2_IDENTICAL",
918  "WEDGE2_TOUCH_AT_BC",
919  "WEDGE2_TOUCH_AT_DA",
920  "WEDGE2_???"
921 };
922 #define WEDGE2_TO_STRING(_class2) (nmg_wedge2_string[(_class2)+2])
923 
924 #define WEDGE2_OVERLAP -2
925 #define WEDGE2_NO_OVERLAP -1
926 #define WEDGE2_AB_IN_CD 0
927 #define WEDGE2_CD_IN_AB 1
928 #define WEDGE2_IDENTICAL 2
929 #define WEDGE2_TOUCH_AT_BC 3
930 #define WEDGE2_TOUCH_AT_DA 4
931 
932 /**
933  * Returns -
934  * WEDGE2_OVERLAP AB partially overlaps CD (error)
935  * WEDGE2_NO_OVERLAP AB does not overlap CD
936  * WEDGE2_AB_IN_CD AB is inside CD
937  * WEDGE2_CD_IN_AB CD is inside AB
938  * WEDGE2_IDENTICAL AB == CD
939  * WEDGE2_TOUCH_AT_BC AB touches CD at BC, but does not overlap
940  * WEDGE2_TOUCH_AT_DA CD touches AB at DA, but does not overlap
941  */
942 static int
943 nmg_compare_2_wedges(double a, double b, double c, double d)
944 {
945  double t;
946  int a_in_cd = 0;
947  int b_in_cd = 0;
948  int c_in_ab = 0;
949  int d_in_ab = 0;
950  int a_eq_b = 0;
951  int a_eq_c = 0;
952  int a_eq_d = 0;
953  int b_eq_c = 0;
954  int b_eq_d = 0;
955  int c_eq_d = 0;
956  int ret;
957 
958 #define WEDGE_ANG_TOL 0.001 /* XXX Angular tolerance, in degrees */
959 #define ANG_SMASH(_a) {\
960  if (_a <= WEDGE_ANG_TOL) _a = 0; \
961  else if (NEAR_EQUAL(_a, 180, WEDGE_ANG_TOL)) _a = 180; \
962  else if (_a >= 360 - WEDGE_ANG_TOL) _a = 360; }
963 
964  ANG_SMASH(a);
965  ANG_SMASH(b);
966  ANG_SMASH(c);
967  ANG_SMASH(d);
968 
969  /* Ensure A < B */
970  if (a > b) {
971  t = a;
972  a = b;
973  b = t;
974  }
975  /* Ensure that C < D */
976  if (c > d) {
977  t = c;
978  c = d;
979  d = t;
980  }
981 
982  if (NEAR_EQUAL(a, b, WEDGE_ANG_TOL)) a_eq_b = 1;
983  if (NEAR_EQUAL(a, c, WEDGE_ANG_TOL)) a_eq_c = 1;
984  if (NEAR_EQUAL(a, d, WEDGE_ANG_TOL)) a_eq_d = 1;
985  if (NEAR_EQUAL(b, c, WEDGE_ANG_TOL)) b_eq_c = 1;
986  if (NEAR_EQUAL(b, d, WEDGE_ANG_TOL)) b_eq_d = 1;
987  if (NEAR_EQUAL(c, d, WEDGE_ANG_TOL)) c_eq_d = 1;
988 
989  /*
990  * Test for TOUCHing wedges must come before INside test,
991  * so that zero-angle wedges that touch a non-zero angle wedge,
992  * will be properly recognized. e.g. AB=(0, 0) CD=(0, 180).
993  */
994  if (b_eq_c) {
995  /* Wedges touch along B-C junction */
996  if (a_eq_d)
997  ret = WEDGE2_IDENTICAL; /* two zero-angle wedges */
998  else
999  ret = WEDGE2_TOUCH_AT_BC;
1000  goto out;
1001  }
1002 
1003  if (a_eq_d) {
1004  /* We know c <= d, d==a, a <= b */
1005  if (a_eq_b) {
1006  ret = WEDGE2_AB_IN_CD;
1007  } else if (c_eq_d) {
1008  ret = WEDGE2_CD_IN_AB;
1009  } else {
1010  ret = WEDGE2_TOUCH_AT_DA;
1011  }
1012  goto out;
1013  }
1014 
1015  if (a_eq_c) {
1016  if (b_eq_d) {
1017  ret = WEDGE2_IDENTICAL;
1018  goto out;
1019  }
1020  /* We already know that A <= B, from sort above */
1021  if (b < d) ret = WEDGE2_AB_IN_CD;
1022  else ret = WEDGE2_CD_IN_AB;
1023  goto out;
1024  }
1025 
1026  if (b_eq_d) {
1027  /* a != c, because of previous IF statement */
1028  if (a < c) ret = WEDGE2_CD_IN_AB;
1029  else ret = WEDGE2_AB_IN_CD;
1030  goto out;
1031  }
1032 
1033  /* See if c < a, b < d */
1034  if (c <= a && a <= d) a_in_cd = 1;
1035  if (c <= b && b <= d) b_in_cd = 1;
1036  /* See if a < c, d < b */
1037  if (a < c && c < b) c_in_ab = 1;
1038  if (a < d && d < b) d_in_ab = 1;
1039 
1040  if (a_in_cd && b_in_cd) {
1041  if (c_in_ab || d_in_ab) {
1042  ret = WEDGE2_OVERLAP; /* ERROR */
1043  goto out;
1044  }
1045  ret = WEDGE2_AB_IN_CD;
1046  goto out;
1047  }
1048  if (c_in_ab && d_in_ab) {
1049  if (a_in_cd || b_in_cd) {
1050  ret = WEDGE2_OVERLAP; /* ERROR */
1051  goto out;
1052  }
1053  ret = WEDGE2_CD_IN_AB;
1054  goto out;
1055  }
1056  if (a_in_cd + b_in_cd + c_in_ab + d_in_ab <= 0) {
1057  ret = WEDGE2_NO_OVERLAP;
1058  goto out;
1059  }
1060  ret = WEDGE2_OVERLAP; /* ERROR */
1061 out:
1062  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1063  bu_log(" a_in_cd=%d, b_in_cd=%d, c_in_ab=%d, d_in_ab=%d\n",
1064  a_in_cd, b_in_cd, c_in_ab, d_in_ab);
1065  bu_log("nmg_compare_2_wedges(%g, %g, %g, %g) = %d %s\n",
1066  a, b, c, d, ret, WEDGE2_TO_STRING(ret));
1067  }
1068  if (ret <= WEDGE2_OVERLAP) {
1069  bu_log("nmg_compare_2_wedges(%g, %g, %g, %g) ERROR!\n", a, b, c, d);
1070  bu_bomb("nmg_compare_2_wedges() ERROR\n");
1071  }
1072  return ret;
1073 }
1074 
1075 
1076 /**
1077  * Find the VU which is inside (or on) the given wedge,
1078  * fitting as tightly to the given wedge as possible,
1079  * and with the lowest value of lo_ang possible.
1080  * XXX how to do tie-breaking for the two coincident ones where
1081  * XXX two loops come together.
1082  *
1083  * lo_ang < hi_ang on RIGHT side of intersection line
1084  * lo_ang > hi_ang on LEFT side of intersection line
1085  *
1086  * There are three wedges involved here:
1087  * the original one, from lo to hi,
1088  * the current best "candidate" so far,
1089  * and "this", the current one being considered.
1090  */
1091 static int
1092 nmg_find_vu_in_wedge(struct nmg_vu_stuff *vs, int start, int end, double lo_ang, double hi_ang, int wclass, int *skip_array)
1093 
1094 /* vu index of coincident range */
1095 
1096 
1097 {
1098  register int i;
1099  double cand_lo;
1100  double cand_hi;
1101  int candidate;
1102 
1103  if (RTG.NMG_debug&DEBUG_VU_SORT)
1104  bu_log("nmg_find_vu_in_wedge(start=%d, end=%d, lo=%g, hi=%g) START\n",
1105  start, end, lo_ang, hi_ang);
1106 
1107  candidate = -1;
1108  cand_lo = lo_ang;
1109  cand_hi = hi_ang;
1110 
1111  /* Consider all the candidates */
1112  for (i=start; i < end; i++) {
1113  int this_wrt_orig;
1114  int this_wrt_cand;
1115 
1116  NMG_CK_VERTEXUSE(vs[i].vu);
1117  if (skip_array[i]) {
1118  if (RTG.NMG_debug&DEBUG_VU_SORT)
1119  bu_log("Skipping index %d\n", i);
1120  continue;
1121  }
1122 
1123  /* Ignore wedges crossing, or on other side of line */
1124  if (vs[i].wedge_class != wclass && vs[i].wedge_class != WEDGE_ON) {
1125  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1126  bu_log("Seeking wedge_class=%s, [%d] has wedge_class %s\n",
1127  WEDGECLASS2STR(wclass), i, WEDGECLASS2STR(vs[i].wedge_class));
1128  }
1129  continue;
1130  }
1131 
1132  if (vs[i].wedge_class == WEDGE_ON) {
1133  /* Ensure that comparisons will work */
1134  if (wclass == WEDGE_RIGHT) {
1135  vs[i].lo_ang = 0;
1136  vs[i].hi_ang = 180;
1137  } else {
1138  vs[i].lo_ang = 360;
1139  vs[i].hi_ang = 180;
1140  }
1141  }
1142 
1143  this_wrt_orig = nmg_compare_2_wedges(
1144  vs[i].lo_ang, vs[i].hi_ang,
1145  lo_ang, hi_ang);
1146  switch (this_wrt_orig) {
1147  case WEDGE2_AB_IN_CD:
1148  break;
1149  case WEDGE2_IDENTICAL:
1150  candidate = i;
1151  goto out;
1152  default:
1153  continue; /* not inside wedge */
1154  }
1155 
1156  if (candidate < 0) {
1157  /* This wedge AB is inside original wedge.
1158  * If candidate is -1, use AB as candidate.
1159  */
1160  if (RTG.NMG_debug&DEBUG_VU_SORT)
1161  bu_log("Initial candidate %d selected\n", i);
1162  candidate = i;
1163  cand_lo = vs[i].lo_ang;
1164  cand_hi = vs[i].hi_ang;
1165  continue;
1166  }
1167 
1168  this_wrt_cand = nmg_compare_2_wedges(
1169  vs[i].lo_ang, vs[i].hi_ang,
1170  cand_lo, cand_hi);
1171  switch (this_wrt_cand) {
1172  case WEDGE2_CD_IN_AB:
1173  /* This wedge AB contains candidate wedge CD, therefore
1174  * this wedge is closer to original wedge */
1175  if (RTG.NMG_debug&DEBUG_VU_SORT)
1176  bu_log("This candidate %d is closer\n", i);
1177  candidate = i;
1178  cand_lo = vs[i].lo_ang;
1179  cand_hi = vs[i].hi_ang;
1180  break;
1181  case WEDGE2_NO_OVERLAP:
1182  /* No overlap, but both are inside. Take lower angle */
1183  if (vs[i].lo_ang < cand_lo) {
1184  if (RTG.NMG_debug&DEBUG_VU_SORT)
1185  bu_log("Taking lower angle %d\n", i);
1186  candidate = i;
1187  cand_lo = vs[i].lo_ang;
1188  cand_hi = vs[i].hi_ang;
1189  }
1190  break;
1191  default:
1192  if (RTG.NMG_debug&DEBUG_VU_SORT)
1193  bu_log("Continuing with search\n");
1194  continue;
1195  }
1196  }
1197 out:
1198  if (RTG.NMG_debug&DEBUG_VU_SORT)
1199  bu_log("nmg_find_vu_in_wedge(start=%d, end=%d, lo=%g, hi=%g) END candidate=%d\n",
1200  start, end, lo_ang, hi_ang,
1201  candidate);
1202  return candidate; /* is -1 if none found */
1203 }
1204 
1205 
1206 /**
1207  * Determine if the 'wedge' vu, which is either a LEFT or RIGHT wedge,
1208  * should be processed before or after the 'cross' vu, which is a
1209  * CROSS wedge.
1210  *
1211  * Returns -
1212  * 1 if wedge should be processed before cross
1213  * 0 if cross should be processed before wedge
1214  */
1215 static int
1216 nmg_is_wedge_before_cross(const struct nmg_vu_stuff *wedge, const struct nmg_vu_stuff *cross)
1217 {
1218  int class2;
1219  int ret = -1;
1220 
1221  if (cross->wedge_class != WEDGE_CROSS || wedge->wedge_class == WEDGE_CROSS)
1222  bu_bomb("nmg_is_wedge_before_cross() bad input\n");
1223 
1224  /* LEFT/RIGHT Wedge is (AB), CROSS wedge is (CD) */
1225  class2 = nmg_compare_2_wedges(wedge->lo_ang, wedge->hi_ang,
1226  cross->lo_ang, cross->hi_ang);
1227 
1228  switch (class2) {
1229  default:
1230  bu_log("nmg_is_wedge_before_cross() class2=%s\n",
1231  WEDGE2_TO_STRING(class2));
1232  bu_bomb("nmg_is_wedge_before_cross(): bad wedge comparison\n");
1233  case WEDGE2_NO_OVERLAP:
1234  /* wedge is not inside cross, cross is not inside wedge. */
1235  /* Do wedge first */
1236  ret = 1;
1237  break;
1238  case WEDGE2_TOUCH_AT_BC:
1239  /* Should only happen when wedge is WEDGE_RIGHT */
1240  if (wedge->wedge_class != WEDGE_RIGHT)
1241  bu_bomb("WEDGE not RIGHT with WEDGE2_TOUCH_AT_BC?\n");
1242  ret = 1;
1243  break;
1244  case WEDGE2_TOUCH_AT_DA:
1245  /* Should only happen when wedge is WEDGE_LEFT */
1246  if (wedge->wedge_class != WEDGE_LEFT)
1247  bu_bomb("WEDGE not LEFT with WEDGE2_TOUCH_AT_DA?\n");
1248  ret = 1;
1249  break;
1250  case WEDGE2_AB_IN_CD:
1251  /* 'wedge' is inside the 'cross' wedge, do it second. */
1252  ret = 0;
1253  break;
1254  }
1255  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1256  bu_log("nmg_is_wedge_before_cross() class2=%s, ret=%d\n",
1257  WEDGE2_TO_STRING(class2), ret);
1258  }
1259  return ret;
1260 }
1261 
1262 
1263 /**
1264  * Support routine for nmg_face_coincident_vu_sort(), via bu_sort().
1265  *
1266  * It is important to note that an edge on the LEFT side of the ray
1267  * will have a "lo" angle which is numerically LARGER than the "hi" angle.
1268  * However, all are measured in the usual units:
1269  * 0 = ON_REV, 90 = RIGHT, 180 = ON_FORW, 270 = LEFT.
1270  *
1271  * Returns -
1272  * -1 when A < B
1273  * 0 when A == B
1274  * +1 when A > B
1275  */
1276 #define A_LT_B {ret = -1; goto out;}
1277 #define AB_EQUAL {ret = 0; goto out;}
1278 #define A_GT_B {ret = 1; goto out;}
1279 static int
1280 nmg_face_vu_compare(const void *aa, const void *bb, void *UNUSED(arg))
1281 {
1282  register const struct nmg_vu_stuff *a = (const struct nmg_vu_stuff *)aa;
1283  register const struct nmg_vu_stuff *b = (const struct nmg_vu_stuff *)bb;
1284  register double diff;
1285  int lo_equal = 0;
1286  int hi_equal = 0;
1287  register int ret = 0;
1288 
1289  lo_equal = NEAR_EQUAL(a->lo_ang, b->lo_ang, WEDGE_ANG_TOL);
1290  hi_equal = NEAR_EQUAL(a->hi_ang, b->hi_ang, WEDGE_ANG_TOL);
1291  /* If both have the same assessment & angles match, => tie */
1292  if (a->wedge_class == b->wedge_class && lo_equal && hi_equal) {
1293  /* Break the tie */
1294  tie_break:
1295  if (a->loop_index == b->loop_index) {
1296  /* Within a loop, sort by vu sequence number */
1297  if (a->seq < b->seq) A_LT_B;
1298  if (a->seq == b->seq) AB_EQUAL;
1299  A_GT_B;
1300  }
1301  /* Select smallest inbound angle */
1302  diff = a->in_vu_angle - b->in_vu_angle;
1303  if (NEAR_ZERO(diff, WEDGE_ANG_TOL)) {
1304  /* Gak, this really means trouble! */
1305  bu_log("nmg_face_vu_compare(): two loops (single vertex) have same in_vu_angle%g?\n",
1306  a->in_vu_angle);
1307  nmg_pr_vu_stuff(a);
1308  nmg_pr_vu_stuff(b);
1309  bu_bomb("nmg_face_vu_compare(): can't decide\n");
1310  AB_EQUAL;
1311  }
1312  if (diff < 0) A_LT_B;
1313  A_GT_B;
1314  }
1315  switch (a->wedge_class) {
1316  case WEDGE_ON:
1317  switch (b->wedge_class) {
1318  case WEDGE_ON:
1319  goto tie_break;
1320  default:
1321  nmg_pr_vu_stuff(a);
1322  nmg_pr_vu_stuff(b);
1323  bu_bomb("nmg_face_vu_compare() WEDGE_ON 1?\n");
1324  }
1325  break;
1326 
1327  case WEDGE_LEFT:
1328  switch (b->wedge_class) {
1329  case WEDGE_LEFT:
1330  if (lo_equal) {
1331  /* hi_equal case handled above */
1332  if (a->hi_ang < b->hi_ang) A_LT_B;
1333  A_GT_B;
1334  }
1335  if (a->lo_ang > b->lo_ang) A_LT_B;
1336  A_GT_B;
1337  case WEDGE_CROSS:
1338  /* A is LEFT, B is CROSS */
1339  if (nmg_is_wedge_before_cross(a, b)) A_LT_B;
1340  A_GT_B;
1341  case WEDGE_RIGHT:
1342  diff = 360 - a->lo_ang;/* CW version of left angle */
1343  if (b->lo_ang <= diff) A_GT_B;
1344  A_LT_B;
1345  case WEDGE_ON:
1346  nmg_pr_vu_stuff(a);
1347  nmg_pr_vu_stuff(b);
1348  bu_bomb("nmg_face_vu_compare() WEDGE_ON 2?\n");
1349  }
1350  bu_log("nmg_face_vu_compare: Unhandled wedge class: %d\n", b->wedge_class);
1351  break;
1352 
1353  case WEDGE_CROSS:
1354  switch (b->wedge_class) {
1355  case WEDGE_LEFT:
1356  /* A (AB) is CROSS, (CD) is LEFT */
1357  if (nmg_is_wedge_before_cross(b, a)) A_GT_B;
1358  A_LT_B;
1359  case WEDGE_CROSS:
1360  if (lo_equal) {
1361  if (a->hi_ang > b->hi_ang) A_LT_B;
1362  A_GT_B;
1363  }
1364  if (a->lo_ang < b->lo_ang) A_LT_B;
1365  A_GT_B;
1366  case WEDGE_RIGHT:
1367  /* A is CROSS, B is RIGHT */
1368  if (nmg_is_wedge_before_cross(b, a)) A_GT_B;
1369  A_LT_B;
1370  case WEDGE_ON:
1371  nmg_pr_vu_stuff(a);
1372  nmg_pr_vu_stuff(b);
1373  bu_bomb("nmg_face_vu_compare() WEDGE_ON 3?\n");
1374  }
1375  bu_log("nmg_face_vu_compare: Unhandled wedge class: %d\n", b->wedge_class);
1376  break;
1377 
1378  case WEDGE_RIGHT:
1379  switch (b->wedge_class) {
1380  case WEDGE_LEFT:
1381  diff = 360 - b->lo_ang;/* CW version of left angle */
1382  if (a->lo_ang <= diff) A_LT_B;
1383  A_GT_B;
1384  case WEDGE_CROSS:
1385  /* A is RIGHT, B is CROSS */
1386  if (nmg_is_wedge_before_cross(a, b)) A_LT_B;
1387  A_GT_B;
1388  case WEDGE_RIGHT:
1389  if (lo_equal) {
1390  if (a->hi_ang < b->hi_ang) A_GT_B;
1391  A_LT_B;
1392  }
1393  if (a->lo_ang < b->lo_ang) A_LT_B;
1394  A_GT_B;
1395  case WEDGE_ON:
1396  nmg_pr_vu_stuff(a);
1397  nmg_pr_vu_stuff(b);
1398  bu_bomb("nmg_face_vu_compare() WEDGE_ON 4?\n");
1399  }
1400  bu_log("nmg_face_vu_compare: Unhandled wedge class: %d\n", b->wedge_class);
1401  break;
1402  }
1403 out:
1404  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1405  bu_log("nmg_face_vu_compare(vu=%p, vu=%p) %s %s, %s\n",
1406  (void *)a->vu, (void *)b->vu,
1409  ret == (-1) ? "A<B" : (ret == 0 ? "A==B" : "A>B"));
1410  }
1411  return ret;
1412 }
1413 
1414 
1415 /**
1416  * For the purpose of computing the dot product of the edges around
1417  * this vertexuse and the ray direction vector, the edge vectors should
1418  * both be pointing inwards to the vertex,
1419  * rather than in the edge direction, so that it is possible to sort
1420  * the vertexuse's into sequence by "angle" along the ray direction,
1421  * starting with the vertexuse that the ray first encounters.
1422  */
1423 static void
1424 nmg_face_vu_dot(struct nmg_vu_stuff *vsp, struct loopuse *lu, const struct nmg_ray_state *rs, int ass)
1425 {
1426  struct edgeuse *this_eu;
1427  struct edgeuse *othereu;
1428  vect_t vec;
1429  fastf_t dot;
1430  struct vertexuse *vu;
1431  int this_vertex;
1432 
1433  NMG_CK_RAYSTATE(rs);
1434  vu = vsp->vu;
1435  NMG_CK_VERTEXUSE(vu);
1436  NMG_CK_LOOPUSE(lu);
1437  this_eu = nmg_find_eu_with_vu_in_lu(lu, vu);
1438 
1439  /* First, consider the edge inbound into this vertex */
1440  this_vertex = NMG_V_ASSESSMENT_PREV(ass);
1441  if (this_vertex == NMG_E_ASSESSMENT_ON_REV) {
1442  vsp->min_vu_dot = -1; /* straight back */
1443  } else if (this_vertex == NMG_E_ASSESSMENT_ON_FORW) {
1444  vsp->min_vu_dot = 1; /* straight forw */
1445  } else {
1446  othereu = BU_LIST_PPREV_CIRC(edgeuse, this_eu);
1447  if (vu->v_p != othereu->vu_p->v_p) {
1448  /* Vector from othereu to this_eu */
1449  VSUB2(vec, vu->v_p->vg_p->coord,
1450  othereu->vu_p->v_p->vg_p->coord);
1451  VUNITIZE(vec);
1452  vsp->min_vu_dot = VDOT(vec, rs->dir);
1453  } else {
1454  vsp->min_vu_dot = 99; /* larger than +1 */
1455  }
1456  }
1457 
1458  /* Second, consider the edge outbound from this vertex (forw) */
1459  this_vertex = NMG_V_ASSESSMENT_NEXT(ass);
1460  if (this_vertex == NMG_E_ASSESSMENT_ON_REV) {
1461  dot = -1; /* straight back */
1462  if (dot < vsp->min_vu_dot) vsp->min_vu_dot = dot;
1463  } else if (this_vertex == NMG_E_ASSESSMENT_ON_FORW) {
1464  dot = 1; /* straight forw */
1465  if (dot < vsp->min_vu_dot) vsp->min_vu_dot = dot;
1466  } else {
1467  othereu = BU_LIST_PNEXT_CIRC(edgeuse, this_eu);
1468  if (vu->v_p != othereu->vu_p->v_p) {
1469  /* Vector from othereu to this_eu */
1470  VSUB2(vec, vu->v_p->vg_p->coord,
1471  othereu->vu_p->v_p->vg_p->coord);
1472  VUNITIZE(vec);
1473  dot = VDOT(vec, rs->dir);
1474  if (dot < vsp->min_vu_dot) {
1475  vsp->min_vu_dot = dot;
1476  }
1477  }
1478  }
1479 }
1480 
1481 
1482 /**
1483  * If one loop gets cut, then unwind the whole call stack, and reassess
1484  * where things stand. (The caller needs to re-call in that case).
1485  *
1486  * The goal here is to get rid of nested wedges.
1487  * To do that, join loops wherever possible, cut them sparingly.
1488  *
1489  * Returns -
1490  * 0 Nothing needed changing, OK to proceed with vertex sorting.
1491  * 1 Loops were cut or joined, need to reclassify everything
1492  * at this vertexuse.
1493  */
1494 static int
1495 nmg_special_wedge_processing(struct nmg_vu_stuff *vs, int start, int end, double lo_ang, double hi_ang, int wclass, int *exclude, const struct bn_tol *tol)
1496 
1497 /* vu index of coincident range */
1498 
1499 
1500 {
1501  register int i;
1502  int outer_wedge;
1503  int inner_wedge;
1504  int class2;
1505  struct loopuse *outer_lu;
1506  struct loopuse *inner_lu;
1507  int not_these[128];
1508 
1509  BN_CK_TOL(tol);
1510 
1511  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1512  char buf[128];
1513  FILE *fp;
1514  struct model *m;
1515  long *b;
1516  struct bn_vlblock *vbp;
1517  static int num = 0;
1518 
1519  bu_log("nmg_special_wedge_processing(start=%d, end=%d, lo=%g, hi=%g, wclass=%s)\n",
1520  start, end, lo_ang, hi_ang,
1521  WEDGECLASS2STR(wclass));
1522  VPRINT("\tvertex", vs[start].vu->v_p->vg_p->coord);
1523 
1524  /* Plot all the loops that touch here. */
1525  m = nmg_find_model((uint32_t *)vs[start].vu);
1526  b = (long *)bu_calloc(m->maxindex, sizeof(long), "nmg_special_wedge_processing flag[]");
1527  vbp = rt_vlblock_init();
1528  for (i=start; i < end; i++) {
1529  struct loopuse *lu;
1530  lu = nmg_find_lu_of_vu(vs[i].vu);
1531  bu_log("\tvu[%d]=%p, lu=%p\n", i, (void *)vs[i].vu, (void *)lu);
1532  nmg_vlblock_lu(vbp, lu, b, 255, 0, 0, 0);
1533  }
1534  for (i=start; i < end; i++) {
1535  struct loopuse *lu;
1536  lu = nmg_find_lu_of_vu(vs[i].vu);
1537  nmg_pr_lu_briefly(lu, 0);
1538  }
1539  sprintf(buf, "wedge%d.plot3", num++);
1540  fp = fopen(buf, "wb");
1541  rt_plot_vlblock(fp, vbp);
1542  fclose(fp);
1543  bu_log("wrote %s\n", buf);
1544  bu_free((char *)b, "nmg_special_wedge_processing flag[]");
1545  rt_vlblock_free(vbp);
1546  }
1547 
1548  if (end-start >= 128) bu_bomb("nmg_special_wedge_processing: array overflow\n");
1549  if (!exclude) {
1550  memset((char *)not_these, 0, sizeof(not_these));
1551  exclude = not_these;
1552  }
1553 
1554 again:
1555  /* May be many "outer" wedges to iterate over this side of line */
1556  outer_wedge = nmg_find_vu_in_wedge(vs, start, end,
1557  lo_ang, hi_ang, wclass, exclude);
1558  if (outer_wedge <= -1) return 0; /* No wedges to process */
1559 
1560  exclude[outer_wedge] = 1; /* Don't return this wedge again */
1561 
1562  /* There is at least one wedge on this side of the line */
1563  outer_lu = nmg_find_lu_of_vu(vs[outer_wedge].vu);
1564  NMG_CK_LOOPUSE(outer_lu);
1565 
1566 again_inner:
1567  inner_wedge = nmg_find_vu_in_wedge(vs, start, end,
1568  vs[outer_wedge].lo_ang, vs[outer_wedge].hi_ang,
1569  wclass, exclude);
1570  if (inner_wedge <= -1) {
1571  /*
1572  * See if there is another outer wedge that starts where
1573  * outer_wedge left off.
1574  * exclude[outer_wedge] is already set.
1575  */
1576  goto again;
1577  }
1578  if (inner_wedge == outer_wedge) bu_bomb("nmg_special_wedge_processing() identical vu selections?\n");
1579 
1580  class2 = nmg_compare_2_wedges(vs[outer_wedge].lo_ang, vs[outer_wedge].hi_ang,
1581  vs[inner_wedge].lo_ang, vs[inner_wedge].hi_ang);
1582  if (RTG.NMG_debug&DEBUG_VU_SORT)
1583  bu_log("+++nmg_special_wedge_processing() outer=%d, inner=%d, class2=%s\n", outer_wedge, inner_wedge, WEDGE2_TO_STRING(class2));
1584 
1585  inner_lu = nmg_find_lu_of_vu(vs[inner_wedge].vu);
1586  NMG_CK_LOOPUSE(inner_lu);
1587 
1588  if (outer_lu == inner_lu) {
1589  struct loopuse *new_lu;
1590  if (class2 == WEDGE2_IDENTICAL &&
1591  NEAR_EQUAL(vs[inner_wedge].hi_ang, vs[inner_wedge].lo_ang, WEDGE_ANG_TOL)
1592  ) {
1593  if (RTG.NMG_debug&DEBUG_VU_SORT)
1594  bu_log("nmg_special_wedge_processing: inner and outer wedges from same loop, WEDGE2_IDENTICAL & 0deg spread, already in final form.\n");
1595  exclude[inner_wedge] = 1; /* Don't return this wedge again */
1596  /* Don't need to recurse only because this is a crack */
1597  goto again_inner;
1598  }
1599  if (RTG.NMG_debug&DEBUG_VU_SORT)
1600  bu_log("nmg_special_wedge_processing: inner and outer wedges from same loop, cutting loop\n");
1601  new_lu = nmg_cut_loop(vs[outer_wedge].vu, vs[inner_wedge].vu);
1602  NMG_CK_LOOPUSE(new_lu);
1603  NMG_CK_LOOPUSE(inner_lu);
1604  nmg_loop_g(inner_lu->l_p, tol);
1605  nmg_loop_g(new_lu->l_p, tol);
1606  nmg_lu_reorient(inner_lu);
1607  nmg_lu_reorient(new_lu);
1608  return 1; /* cutjoin was done */
1609  }
1610 
1611  /* XXX Or they could be WEDGE2_IDENTICAL */
1612  /* XXX If WEDGE2_IDENTICAL, could we join and then simplify? */
1613  if (RTG.NMG_debug&DEBUG_VU_SORT)
1614  bu_log("wedge at vu[%d] is inside wedge at vu[%d]\n", inner_wedge, outer_wedge);
1615 
1616  if (outer_lu->orientation == inner_lu->orientation) {
1617  /*
1618  * Two loops meet at this vu. Joining them will impose
1619  * a natural edgeuse ordering onto the vu's.
1620  */
1621  if (RTG.NMG_debug&DEBUG_VU_SORT)
1622  bu_log("joining loops\n");
1623  vs[inner_wedge].vu = nmg_join_2loops(vs[outer_wedge].vu,
1624  vs[inner_wedge].vu);
1625  nmg_loop_g(outer_lu->l_p, tol);
1626  return 1; /* cutjoin was done */
1627  }
1628 
1629  /* Recurse on inner wedge */
1630  if (nmg_special_wedge_processing(vs, start, end,
1631  vs[inner_wedge].lo_ang, vs[inner_wedge].hi_ang, wclass, exclude, tol))
1632  return 1; /* An inner wedge was cut */
1633 
1634  /*
1635  * Inner and outer are different loopuses,
1636  * have different orientations,
1637  * and have nothing complex inside the wedge of the inner loop.
1638  * Join inner and outer loops here, to impose a proper vu ordering.
1639  */
1640  if (RTG.NMG_debug&DEBUG_VU_SORT)
1641  bu_log("Inner wedge is simple, join inner and outer loops.\n");
1642 
1643  vs[inner_wedge].vu = nmg_join_2loops(vs[outer_wedge].vu,
1644  vs[inner_wedge].vu);
1645  nmg_loop_g(outer_lu->l_p, tol);
1646  return 1; /* cutjoin was done */
1647 }
1648 
1649 
1650 /**
1651  * Given co-incident vertexuses (same distance along the ray),
1652  * sort them into the "proper" order for driving the state machine.
1653  */
1654 int
1655 nmg_face_coincident_vu_sort(struct nmg_ray_state *rs, int start, int end)
1656 
1657 /* first index */
1658 /* last index + 1 */
1659 {
1660  int num;
1661  struct nmg_vu_stuff *vs;
1662  struct nmg_loop_stuff *ls;
1663  int nloop;
1664  unsigned nvu;
1665  unsigned i;
1666  struct loopuse *lu;
1667  int ass;
1668  int l;
1669  int retries = 0;
1670 
1671  if (RTG.NMG_debug&DEBUG_VU_SORT)
1672  bu_log("nmg_face_coincident_vu_sort(, %d, %d) START\n", start, end);
1673 
1674  NMG_CK_RAYSTATE(rs);
1675 
1676  num = end - start;
1677  vs = (struct nmg_vu_stuff *)bu_malloc(sizeof(struct nmg_vu_stuff)*num,
1678  "nmg_vu_stuff");
1679  ls = (struct nmg_loop_stuff *)bu_malloc(sizeof(struct nmg_loop_stuff)*num,
1680  "nmg_loop_stuff");
1681 
1682 top:
1683  if (retries++ > 24) bu_bomb("nmg_face_coincident_vu_sort() infinite loop\n");
1684  /* Assess each vu, create list of loopuses, find max angles */
1685  nloop = 0;
1686  nvu = 0;
1687  if (start < 0 || end < 0)
1688  bu_log("%s:%d Internal Error\n", __FILE__, __LINE__);
1689  for (i = (unsigned)end-1; i >= (unsigned)start; i--) {
1690  lu = nmg_find_lu_of_vu(rs->vu[i]);
1691  NMG_CK_LOOPUSE(lu);
1692  ass = nmg_assess_vu(rs, i);
1693  if (RTG.NMG_debug&DEBUG_VU_SORT)
1694  bu_log("vu[%d]=%p v=%p assessment=%s\n",
1695  i, (void *)rs->vu[i], (void *)rs->vu[i]->v_p, nmg_v_assessment_names[ass]);
1696  /* Ignore lone vertices, unless that is all that there is,
1697  * in which case, let just one through. (return 'start+1');
1698  */
1699  if (*(rs->vu[i]->up.magic_p) == NMG_LOOPUSE_MAGIC) {
1700  if (start < 0)
1701  bu_log("%s:%d Internal Error\n", __FILE__, __LINE__);
1702 
1703  if (nvu > 0 || i > (unsigned)start) {
1704  /* Drop this loop of a single vertex in sanitize() */
1705  lu->orientation =
1706  lu->lumate_p->orientation = OT_BOOLPLACE;
1707  /* "continue" keeps vu from being added to vs[] */
1708  continue;
1709  }
1710  }
1711 
1712  vs[nvu].vu = rs->vu[i];
1713  vs[nvu].seq = -1; /* Not assigned yet */
1714 
1715  /* x_dir is -dir, y_dir is -left */
1716  vs[nvu].in_vu_angle = nmg_vu_angle_measure(rs->vu[i],
1717  rs->ang_x_dir, rs->ang_y_dir, ass, 1) * RAD2DEG;
1718  vs[nvu].out_vu_angle = nmg_vu_angle_measure(rs->vu[i],
1719  rs->ang_x_dir, rs->ang_y_dir, ass, 0) * RAD2DEG;
1720 
1721  /* Special case for LEFT & ON combos */
1723  vs[nvu].in_vu_angle = 360;
1725  vs[nvu].out_vu_angle = 360;
1726 
1727  vs[nvu].wedge_class = nmg_wedge_class(ass, vs[nvu].in_vu_angle, vs[nvu].out_vu_angle);
1728  if (RTG.NMG_debug&DEBUG_VU_SORT) bu_log("nmg_wedge_class = %d %s\n", vs[nvu].wedge_class, WEDGECLASS2STR(vs[nvu].wedge_class));
1729  /* Sort the angles (Don't forget to sort for CROSS case too) */
1730  if ((vs[nvu].wedge_class == WEDGE_LEFT && vs[nvu].in_vu_angle > vs[nvu].out_vu_angle) ||
1731  (vs[nvu].wedge_class != WEDGE_LEFT && vs[nvu].in_vu_angle < vs[nvu].out_vu_angle)) {
1732  vs[nvu].lo_ang = vs[nvu].in_vu_angle;
1733  vs[nvu].hi_ang = vs[nvu].out_vu_angle;
1734  } else {
1735  vs[nvu].lo_ang = vs[nvu].out_vu_angle;
1736  vs[nvu].hi_ang = vs[nvu].in_vu_angle;
1737  }
1738 
1739  /* Check entering and departing edgeuse angle w.r.t. ray */
1740  /* This is already done once in nmg_assess_vu(); reuse? */
1741  /* Computes vs[nvu].min_vu_dot */
1742  nmg_face_vu_dot(&vs[nvu], lu, rs, ass);
1743 
1744  /* Search for loopuse table entry */
1745  for (l = 0; l < nloop; l++) {
1746  if (ls[l].lu == lu) goto got_loop;
1747  }
1748  /* didn't find loopuse in table, add to table */
1749  l = nloop++;
1750  ls[l].lu = lu;
1751  ls[l].n_vu_in_loop = 0;
1752  ls[l].min_dot = 99; /* > +1 */
1753  got_loop:
1754  ls[l].n_vu_in_loop++;
1755  vs[nvu].loop_index = l;
1756  vs[nvu].lsp = &ls[l];
1757  if (vs[nvu].min_vu_dot < ls[l].min_dot) {
1758  ls[l].min_dot = vs[nvu].min_vu_dot;
1759  ls[l].min_vu = vs[nvu].vu;
1760  }
1761  nvu++;
1762  }
1763 
1764  /*
1765  * For each loop which has more than one vertexuse present on the
1766  * ray, start at the vu which has the smallest angle off the ray,
1767  * and walk the edges of the loop, marking off the vu sequence for
1768  * those vu's on the ray (those vu's found in vs[].vu).
1769  */
1770  for (l = 0; l < nloop; l++) {
1771  register struct edgeuse *eu;
1772  struct edgeuse *first_eu;
1773  int seq = 0;
1774 
1775  if (ls[l].n_vu_in_loop <= 1) continue;
1776 
1777  first_eu = nmg_find_eu_with_vu_in_lu(ls[l].lu, ls[l].min_vu);
1778  eu = first_eu;
1779  do {
1780  register struct vertexuse *vu = eu->vu_p;
1781  NMG_CK_VERTEXUSE(vu);
1782  for (i = 0; i < nvu; i++) {
1783  if (vs[i].vu == vu) {
1784  vs[i].seq = seq++;
1785  break;
1786  }
1787  }
1788  eu = BU_LIST_PNEXT_CIRC(edgeuse, eu);
1789  } while (eu != first_eu);
1790  }
1791 
1792  /* For loops with >1 crossings here, determine proper VU ordering on that loop */
1793  /* XXX */
1794 
1795  /* Here is where the special wedge-breaking code goes */
1796  if (nmg_special_wedge_processing(vs, 0, nvu, 0.0, 180.0, WEDGE_RIGHT, (int *)0, rs->tol)) {
1797  if (RTG.NMG_debug&DEBUG_VU_SORT)
1798  bu_log("*** nmg_face_coincident_vu_sort(, %d, %d) restarting after 0--180 wedge\n", start, end);
1799  goto top;
1800  }
1801  /* XXX reclass on/on edges from WEDGE_RIGHT to WEDGE_LEFT here? */
1802  if (nmg_special_wedge_processing(vs, 0, nvu, 360.0, 180.0, WEDGE_LEFT, (int *)0, rs->tol)) {
1803  if (RTG.NMG_debug&DEBUG_VU_SORT)
1804  bu_log("*** nmg_face_coincident_vu_sort(, %d, %d) restarting after 180-360 wedge\n", start, end);
1805  goto top;
1806  }
1807 
1808  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1809  bu_log("Loop table (before sort):\n");
1810  for (l = 0; l < nloop; l++) {
1811  bu_log(" index=%d, lu=%p, min_dot=%g, #vu=%d\n",
1812  l, (void *)ls[l].lu, ls[l].min_dot,
1813  ls[l].n_vu_in_loop);
1814  }
1815  }
1816 
1817  /* Sort the vertexuse table into appropriate order */
1818  bu_sort((void *)vs, (unsigned)nvu, (unsigned)sizeof(*vs),
1819  nmg_face_vu_compare, NULL);
1820 
1821  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1822  bu_log("Vertexuse table (after sort):\n");
1823  for (i = 0; i < nvu; i++) {
1824  bu_log(" %p, l=%d, in/o=(%g, %g), lo/hi=(%g, %g), %s, sq=%d\n",
1825  (void *)vs[i].vu, vs[i].loop_index,
1826  vs[i].in_vu_angle, vs[i].out_vu_angle,
1827  vs[i].lo_ang, vs[i].hi_ang,
1828  WEDGECLASS2STR(vs[i].wedge_class),
1829  vs[i].seq);
1830  }
1831  }
1832 
1833  /* Copy new vu's back to main array */
1834  {
1835  for (i = 0; i < nvu; i++) {
1836  rs->vu[start+i] = vs[i].vu;
1837  }
1838  }
1839  if (RTG.NMG_debug&DEBUG_VU_SORT) {
1840  for (i = 0; i < nvu; i++) {
1841  bu_log(" vu[%d]=%p, v=%p\n",
1842  start+i, (void *)rs->vu[start+i], (void *)rs->vu[start+i]->v_p);
1843  }
1844  }
1845 
1846  bu_free((char *)vs, "nmg_vu_stuff");
1847  bu_free((char *)ls, "nmg_loop_stuff");
1848 
1849  if (RTG.NMG_debug&DEBUG_VU_SORT)
1850  bu_log("nmg_face_coincident_vu_sort(, %d, %d) END, ret=%d\n", start, end, start+nvu);
1851 
1852  return start+nvu;
1853 }
1854 
1855 
1856 /**
1857  * Eliminate any OT_BOOLPLACE self-loops that remain behind in this face.
1858  */
1859 void
1860 nmg_sanitize_fu(struct faceuse *fu)
1861 {
1862  struct loopuse *lu;
1863  struct loopuse *lunext;
1864 
1865  NMG_CK_FACEUSE(fu);
1866 
1867  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
1868  while (BU_LIST_NOT_HEAD(lu, &fu->lu_hd)) {
1869  NMG_CK_LOOPUSE(lu);
1870  lunext = BU_LIST_PNEXT(loopuse, lu);
1871  if (lu->orientation == OT_BOOLPLACE) {
1872  /* XXX What to do with return code? */
1873  if (nmg_klu(lu)) bu_bomb("nmg_sanitize_fu() nmg_klu() emptied face?\n");
1874  }
1875  lu = lunext;
1876  }
1877 }
1878 
1879 
1880 /**
1881  * Set up nmg_ray_state structure.
1882  * "left" is a vector that lies in the plane of the face
1883  * which contains the loops being operated on.
1884  * It points in the direction "left" of the ray, such that the first
1885  * OT_SAME loop in the first OT_SAME fact that it crosses will cross
1886  * the ray in a left-to-right manner consistent with the CCW loop rule.
1887  * There are some special conditions placed on the "dir" argument to
1888  * make this happen; see the comments in nmg_inter.c for details, or
1889  * Mike's notes "The 'Left' Vector Choice" dated 27-Aug-93, page 1.
1890  */
1891 void
1892 nmg_face_rs_init(struct nmg_ray_state *rs, struct bu_ptbl *b, struct faceuse *fu1, struct faceuse *fu2, fastf_t *pt, fastf_t *dir, struct edge_g_lseg *eg, const struct bn_tol *tol)
1893 
1894 /* table of vertexuses in fu1 on intercept line */
1895 /* face being worked */
1896 /* for plane equation */
1897 
1898 
1899 /* may be null. Geom of isect line. */
1900 
1901 {
1902  plane_t n1;
1903 
1904  BN_CK_TOL(tol);
1905  BU_CK_PTBL(b);
1906  NMG_CK_FACEUSE(fu1);
1907  NMG_CK_FACEUSE(fu2);
1908  if (eg) NMG_CK_EDGE_G_LSEG(eg);
1909 
1910  memset((char *)rs, 0, sizeof(rs));
1911 
1912  rs->magic = NMG_RAYSTATE_MAGIC;
1913  rs->tol = tol;
1914  rs->vu = (struct vertexuse **)b->buffer;
1915  rs->nvu = b->end;
1916  rs->eg_p = eg;
1917  rs->sA = fu1->s_p;
1918  rs->sB = fu2->s_p;
1919  rs->fu1 = fu1;
1920  rs->fu2 = fu2;
1921  VMOVE(rs->pt, pt);
1922  VMOVE(rs->dir, dir);
1923  NMG_GET_FU_PLANE(n1, fu1);
1924  VCROSS(rs->left, n1, dir);
1925  VUNITIZE(rs->left);
1926  switch (fu1->orientation) {
1927  case OT_SAME:
1928  break;
1929  case OT_OPPOSITE:
1930  VREVERSE(rs->left, rs->left);
1931  break;
1932  default:
1933  bu_bomb("nmg_face_rs_init: bad orientation\n");
1934  }
1935  if (RTG.NMG_debug&DEBUG_FCUT) {
1936  struct loopuse *lu;
1937  struct edgeuse *eu;
1938  struct vertexuse *vu;
1939  int i;
1940 
1941  bu_log("\tfu->orientation=%s\n", nmg_orientation(fu1->orientation));
1942  HPRINT("\tfg N", n1);
1943  VPRINT("\t pt", pt);
1944  VPRINT("\t dir", dir);
1945  VPRINT("\tleft", rs->left);
1946  bu_log("\tvertexuses in fu that are on lintersect line:\n");
1947  for (i = 0; i < BU_PTBL_END(b); i++) {
1948  vu = (struct vertexuse *)BU_PTBL_GET(b, i);
1949  nmg_pr_vu_briefly(vu, "\t ");
1950  }
1951  bu_log("\tLoopuse in fu (%p):\n", (void *)fu1);
1952  for (BU_LIST_FOR(lu, loopuse, &fu1->lu_hd)) {
1953  bu_log("\tLOOPUSE %p:\n", (void *)lu);
1954  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
1955  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
1956  nmg_pr_vu_briefly(vu, "\tVertex Loop: ");
1957  } else {
1958  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
1959  struct edgeuse *eu_next;
1960  vect_t eu_dir;
1961  fastf_t eu_len;
1962  double inv_len;
1963 
1964  nmg_pr_eu_briefly(eu, "\t\t");
1965  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, eu);
1966  VSUB2(eu_dir, eu_next->vu_p->v_p->vg_p->coord, eu->vu_p->v_p->vg_p->coord);
1967  eu_len = MAGNITUDE(eu_dir);
1968  if (eu_len < VDIVIDE_TOL)
1969  inv_len = 0.0;
1970  else
1971  inv_len = 1.0/eu_len;
1972  for (i = 0; i < 3; i++)
1973  eu_dir[i] = eu_dir[i] * inv_len;
1974  bu_log("\t\t\teu_dir = (%g, %g, %g), length = %g\n", V3ARGS(eu_dir), eu_len);
1975  }
1976  }
1977  }
1978  }
1979  rs->state = NMG_STATE_OUT;
1980 
1981  /* For measuring angle CCW around plane from -dir */
1982  VREVERSE(rs->ang_x_dir, dir);
1983  VREVERSE(rs->ang_y_dir, rs->left);
1984 }
1985 
1986 
1987 #define VAVERAGE(a, b, c) { \
1988  (a)[X] = ((b)[X] + (c)[X]) * 0.5;\
1989  (a)[Y] = ((b)[Y] + (c)[Y]) * 0.5;\
1990  (a)[Z] = ((b)[Z] + (c)[Z]) * 0.5;\
1991  }
1992 /**
1993  * Force the geometry structure for a given edge to be that of
1994  * the intersection line between the two faces.
1995  *
1996  * Note that sometimes a vertex can appear to lie on more than one
1997  * line. It is important to refer to geometry here, to make sure
1998  * that the edgeuse is not mistakenly fused to the wrong edge geometry.
1999  *
2000  * XXX This has the byproduct that not all edgeuses "on" the line
2001  * XXX of intersection will share rs->eg_p.
2002  *
2003  * See the comments in nmg_radial_join_eu() for the rationale.
2004  */
2005 void
2006 nmg_edge_geom_isect_line(struct edgeuse *eu, struct nmg_ray_state *rs, const char *reason)
2007 {
2008  register struct edge_g_lseg *eg;
2009 
2010  NMG_CK_EDGEUSE(eu);
2011  NMG_CK_RAYSTATE(rs);
2012  if (eu->g.lseg_p) NMG_CK_EDGE_G_LSEG(eu->g.lseg_p);
2013  if (rs->eg_p) NMG_CK_EDGE_G_LSEG(rs->eg_p);
2014 
2015  if (RTG.NMG_debug&DEBUG_FCUT) {
2016  bu_log("nmg_edge_geom_isect_line(eu=%p, %s)\n eu->g=%p, rs->eg=%p at START\n",
2017  (void *)eu, reason,
2018  (void *)eu->g.magic_p, (void *)rs->eg_p);
2019  }
2020  if (!eu->g.magic_p) {
2021  /* This edgeuse has No edge geometry so far.
2022  * It may be a new edge formed by a CUTJOIN operation.
2023  */
2024  if (!rs->eg_p) {
2025  nmg_edge_g(eu);
2026  eg = eu->g.lseg_p;
2027  NMG_CK_EDGE_G_LSEG(eg);
2028  VMOVE(eg->e_pt, rs->pt);
2029  VMOVE(eg->e_dir, rs->dir);
2030  rs->eg_p = eg;
2031  } else {
2032  NMG_CK_EDGE_G_LSEG(rs->eg_p);
2033  nmg_use_edge_g(eu, (uint32_t *)rs->eg_p);
2034  }
2035  goto out;
2036  }
2037  /* Edge has edge geometry */
2038  if (eu->g.lseg_p == rs->eg_p) return; /* nothing changes */
2039  if (!rs->eg_p) {
2040  /* This is first edge_g found on isect line, remember it */
2041  eg = eu->g.lseg_p;
2042  NMG_CK_EDGE_G_LSEG(eg);
2043  rs->eg_p = eg;
2044  goto out;
2045  }
2046 
2047  /*
2048  * Edge has an edge geometry struct, different from that of isect line.
2049  * Force all uses of this edge geom to take on isect line's geometry.
2050  * Everywhere eu->g.lseg_p is seen, replace with rs->eg_p.
2051  *
2052  * XXX This is DUBIOUS, as the angle might be very different.
2053  */
2054  nmg_jeg(rs->eg_p, eu->g.lseg_p);
2055 out:
2056  NMG_CK_EDGE_G_LSEG(rs->eg_p);
2057  if (RTG.NMG_debug&DEBUG_FCUT) {
2058  bu_log("nmg_edge_geom_isect_line(eu=%p) g=%p, rs->eg=%p at END\n",
2059  (void *)eu, (void *)eu->g.magic_p, (void *)rs->eg_p);
2060  }
2061 }
2062 
2063 
2064 static struct bu_ptbl *
2065 find_loop_to_cut(int *index1, int *index2, int prior_start, int prior_end, int next_start, int next_end, fastf_t *mid_pt, struct nmg_ray_state *rs)
2066 {
2067  struct loopuse *lu1, *lu2;
2068  struct vertexuse *vu1 = (struct vertexuse *)NULL;
2069  struct vertexuse *vu2 = (struct vertexuse *)NULL;
2070  struct loopuse *match_lu=(struct loopuse *)NULL;
2071  struct loopuse *prior_lu, *next_lu;
2072  struct bu_ptbl *cuts=(struct bu_ptbl *)NULL;
2073  struct loop_cuts *lcut;
2074  int count = 0;
2075  int i, j, k;
2076  int done = 0;
2077 
2078  if (RTG.NMG_debug&DEBUG_FCUT)
2079  bu_log("find_loop_to_cut: prior_start=%d, prior_end=%d, next_start=%d, next_end=%d, rs=%p\n",
2080  prior_start, prior_end, next_start, next_end, (void *)rs);
2081 
2082  NMG_CK_RAYSTATE(rs);
2083 
2084  /* check if any coincident VU's can give us a loop to cut */
2085  while (!done) {
2086  done = 1;
2087  count++;
2088  if (count > 100) {
2089  bu_log("find_loop_to_cut: infinite loop\n");
2090  bu_log("prior_start = %d, prior_end = %d, next_start = %d next_nd = %d\n",
2091  prior_start, prior_end, next_start, next_end);
2092  bu_log("mid_point = (%f %f %f)\n", V3ARGS(mid_pt));
2093  for (i = 0; i < rs->nvu; i++)
2094  bu_log("\t%d %p\n", i, (void *)rs->vu[i]);
2095  bu_bomb("find_loop_to_cut: infinite loop");
2096  }
2097  for (i=prior_start; i < prior_end; i++) {
2098  int class_pt;
2099 
2100  prior_lu = nmg_find_lu_of_vu(rs->vu[i]);
2101  class_pt = NMG_CLASS_Unknown;
2102  for (j=next_start; j < next_end; j++) {
2103  next_lu = nmg_find_lu_of_vu(rs->vu[j]);
2104  if (prior_lu == next_lu) {
2105  int class_lu;
2106 
2107  if (!match_lu) {
2108  match_lu = next_lu;
2109  BU_ALLOC(cuts, struct bu_ptbl);
2110  bu_ptbl_init(cuts, 64, " cuts");
2111  BU_ALLOC(lcut, struct loop_cuts);
2112  lcut->lu = match_lu;
2113  bu_ptbl_ins(cuts, (long *)lcut);
2114  continue;
2115  }
2116 
2117  if (match_lu == next_lu)
2118  continue;
2119 
2120  if (class_pt == NMG_CLASS_Unknown) {
2121  class_pt = nmg_class_pt_lu_except(mid_pt,
2122  match_lu, (struct edge *)NULL, rs->tol);
2123  if (match_lu->orientation == OT_OPPOSITE) {
2124  if (class_pt == NMG_CLASS_AinB)
2125  class_pt = NMG_CLASS_AoutB;
2126  else if (class_pt == NMG_CLASS_AoutB)
2127  class_pt = NMG_CLASS_AinB;
2128  }
2129  }
2130  class_lu = nmg_classify_lu_lu(next_lu, match_lu, rs->tol);
2131 
2132  if (class_lu == class_pt ||
2133  class_lu == NMG_CLASS_AonBshared) {
2134  int found = 0;
2135 
2136  match_lu = next_lu;
2137  for (k = 0; k < BU_PTBL_END(cuts); k++) {
2138  lcut = (struct loop_cuts *)BU_PTBL_GET(cuts, k);
2139  if (lcut->lu == match_lu) {
2140  found = 1;
2141  break;
2142  }
2143  }
2144  if (!found) {
2145  done = 0;
2146  BU_ALLOC(lcut, struct loop_cuts);
2147  lcut->lu = match_lu;
2148  bu_ptbl_ins(cuts, (long *)lcut);
2149  }
2150  }
2151  }
2152  }
2153  }
2154  }
2155 
2156  if (cuts) {
2157  for (k = 0; k < BU_PTBL_END(cuts); k++) {
2158  lcut = (struct loop_cuts *)BU_PTBL_GET(cuts, k);
2159  match_lu = lcut->lu;
2160 
2161  if (RTG.NMG_debug&DEBUG_FCUT)
2162  bu_log("\tfind_loop_to_cut: matching lu's = %p\n", (void *)match_lu);
2163  lu1 = match_lu;
2164  for (i=prior_start; i < prior_end; i++) {
2165  if (nmg_find_lu_of_vu(rs->vu[i]) == lu1) {
2166  *index1 = i;
2167  vu1 = rs->vu[i];
2168  lcut->vu1 = vu1;
2169  break;
2170  }
2171  }
2172  lu2 = match_lu;
2173  for (i=next_start; i < next_end; i++) {
2174  if (nmg_find_lu_of_vu(rs->vu[i]) == lu2) {
2175  *index2 = i;
2176  vu2 = rs->vu[i];
2177  lcut->vu2 = vu2;
2178  break;
2179  }
2180  }
2181  }
2182  } else {
2183  if (RTG.NMG_debug&DEBUG_FCUT)
2184  bu_log("\tfind_loop_to_cut returning 0\n");
2185  return (struct bu_ptbl *)NULL;
2186  }
2187 
2188  for (k = 0; k < BU_PTBL_END(cuts); k++) {
2189  lcut = (struct loop_cuts *)BU_PTBL_GET(cuts, k);
2190  lu1 = lcut->lu;
2191  lu2 = lu1;
2192 
2193  /* Check if there is more than one VU from lu2 */
2194  count = 0;
2195  for (i=next_start; i<next_end; i++) {
2196  if (nmg_find_lu_of_vu(rs->vu[i]) == lu2)
2197  count++;
2198  }
2199 
2200  if (count > 1) {
2201  struct vertexuse *vu_best;
2202  fastf_t vu_angle;
2203  vect_t x_dir, y_dir;
2204  vect_t norm;
2205 
2206  if (RTG.NMG_debug&DEBUG_FCUT)
2207  bu_log("\tfind_loop_to_cut: %d VU's from lu %p\n", count, (void *)lu2);
2208 
2209  /* need to select correct VU */
2210  vu_angle = (-M_PI);
2211  vu_best = (struct vertexuse *)NULL;
2212 
2213  VSUB2(x_dir, vu2->v_p->vg_p->coord, vu1->v_p->vg_p->coord);
2214  VUNITIZE(x_dir);
2215  NMG_GET_FU_NORMAL(norm, rs->fu1);
2216 
2217  VCROSS(y_dir, norm, x_dir);
2218  VUNITIZE(y_dir);
2219 
2220  if (RTG.NMG_debug&DEBUG_FCUT)
2221  bu_log("\tx_dir=(%g %g %g), y_dir=(%g %g %g)\n",
2222  V3ARGS(x_dir), V3ARGS(y_dir));
2223 
2224  for (i=next_start; i<next_end; i++) {
2225  struct edgeuse *eu;
2226  fastf_t angle;
2227  vect_t eu_dir;
2228 
2229 
2230  if (nmg_find_lu_of_vu(rs->vu[i]) != lu2)
2231  continue;
2232 
2233  if (*(rs->vu[i]->up.magic_p) != NMG_EDGEUSE_MAGIC) {
2234  bu_log("nmg_fcut_face: VU (%p) is not from an EU\n", (void *)rs->vu[i]);
2235  bu_bomb("nmg_fcut_face: VU is not from an EU");
2236  }
2237 
2238  /* calculate angle this EU will make with edgeuse
2239  * that will be created by the cut/join
2240  */
2241  eu = rs->vu[i]->up.eu_p;
2242  VSUB2(eu_dir, eu->eumate_p->vu_p->v_p->vg_p->coord, eu->vu_p->v_p->vg_p->coord);
2243  angle = atan2(VDOT(y_dir, eu_dir), VDOT(x_dir, eu_dir));
2244 
2245  if (RTG.NMG_debug&DEBUG_FCUT)
2246  bu_log("\tangle for eu %p (vu=%p, #%d) is %g\n",
2247  (void *)eu, (void *)rs->vu[i], i, angle);
2248 
2249  /* select max angle */
2250  if (angle > vu_angle) {
2251  if (RTG.NMG_debug&DEBUG_FCUT)
2252  bu_log("\t\tabove is the new best VU\n");
2253  vu_angle = angle;
2254  vu_best = rs->vu[i];
2255  *index2 = i;
2256  }
2257  }
2258 
2259  if (vu_best) {
2260  vu2 = vu_best;
2261  lcut->vu2 = vu2;
2262  }
2263 
2264  if (RTG.NMG_debug&DEBUG_FCUT)
2265  bu_log("\tfind_loop_to_cut: selecting VU2 %p\n", (void *)vu2);
2266  }
2267 
2268  /* Check for duplicate cuts (cutting two different loops across same two vertices) */
2269  if (BU_PTBL_END(cuts) > 1) {
2270  for (i = 0; i < BU_PTBL_END(cuts); i++) {
2271  struct loop_cuts *lcut1, *lcut2;
2272  int class1, class2;
2273 
2274  lcut1 = (struct loop_cuts *)BU_PTBL_GET(cuts, i);
2275  for (j=i+1; j<BU_PTBL_END(cuts); j++) {
2276  lcut2 = (struct loop_cuts *)BU_PTBL_GET(cuts, j);
2277 
2278  if (lcut1->vu1->v_p != lcut2->vu1->v_p ||
2279  lcut1->vu2->v_p != lcut2->vu2->v_p)
2280  continue;
2281 
2282  /* lcut1 and lcut2 are the same cut, choose one loop to cut */
2283  if (lcut1->lu->orientation == OT_OPPOSITE &&
2284  lcut2->lu->orientation == OT_OPPOSITE)
2285  {
2286  bu_log("find_loop_to_cut: Two OT_OPPOSITE loops to be cut?? %p and %p\n",
2287  (void *)lcut1->lu, (void *)lcut2->lu);
2288  bu_bomb("find_loop_to_cut: Two OT_OPPOSITE loops to be cut??\n");
2289  }
2290  if (lcut1->lu->orientation == OT_OPPOSITE) {
2291  /* don't cut an OT_OPPOSITE loop */
2292  bu_ptbl_rm(cuts, (long *)lcut1);
2293  break;
2294  }
2295  if (lcut2->lu->orientation == OT_OPPOSITE) {
2296  /* don't cut an OT_OPPOSITE loop */
2297  bu_ptbl_rm(cuts, (long *)lcut2);
2298  break;
2299  }
2300  class1 = nmg_class_pt_lu_except(mid_pt, lcut1->lu,
2301  (struct edge *)NULL, rs->tol);
2302  class2 = nmg_class_pt_lu_except(mid_pt, lcut2->lu,
2303  (struct edge *)NULL, rs->tol);
2304 
2305  if (class1 == NMG_CLASS_AoutB && class2 == NMG_CLASS_AoutB) {
2306  bu_log("find_loop_to_cut: mid point is outside both loops??? %p and %p pt=(%g %g %g)\n",
2307  (void *)lcut1->lu, (void *)lcut2->lu, V3ARGS(mid_pt));
2308  bu_bomb("find_loop_to_cut: mid point is outside both loops???\n");
2309  }
2310 
2311  if (class1 == NMG_CLASS_AoutB) {
2312  /* Don't cut this loop (cut is outside loop) */
2313  bu_ptbl_rm(cuts, (long *)lcut1);
2314  break;
2315  }
2316  if (class2 == NMG_CLASS_AoutB) {
2317  /* Don't cut this loop (cut is outside loop) */
2318  bu_ptbl_rm(cuts, (long *)lcut2);
2319  break;
2320  }
2321  }
2322  }
2323  }
2324 
2325  /* Check if there is more than one VU from lu1 */
2326  count = 0;
2327  for (i = prior_start; i < prior_end; i++) {
2328  if (nmg_find_lu_of_vu(rs->vu[i]) == lu1)
2329  count++;
2330  }
2331 
2332  if (count > 1) {
2333  struct vertexuse *vu_best;
2334 
2335  fastf_t vu_angle;
2336  vect_t x_dir, y_dir;
2337  vect_t norm;
2338 
2339  if (RTG.NMG_debug&DEBUG_FCUT)
2340  bu_log("\tfind_loop_to_cut: %d VU's from lu %p\n", count, (void *)lu1);
2341 
2342  /* need to select correct VU */
2343  vu_angle = (-M_PI);
2344  vu_best = (struct vertexuse *)NULL;
2345 
2346  VSUB2(x_dir, vu1->v_p->vg_p->coord, vu2->v_p->vg_p->coord);
2347  VUNITIZE(x_dir);
2348  NMG_GET_FU_NORMAL(norm, rs->fu1);
2349 
2350  VCROSS(y_dir, norm, x_dir);
2351  VUNITIZE(y_dir);
2352 
2353  if (RTG.NMG_debug&DEBUG_FCUT)
2354  bu_log("\tx_dir=(%g %g %g), y_dir=(%g %g %g)\n",
2355  V3ARGS(x_dir), V3ARGS(y_dir));
2356 
2357  for (i = prior_start; i < prior_end; i++) {
2358  struct edgeuse *eu;
2359  fastf_t angle;
2360  vect_t eu_dir;
2361 
2362  if (nmg_find_lu_of_vu(rs->vu[i]) != lu1)
2363  continue;
2364 
2365  if (*(rs->vu[i]->up.magic_p) != NMG_EDGEUSE_MAGIC) {
2366  bu_log("nmg_fcut_face: VU (%p) is not from an EU\n", (void *)rs->vu[i]);
2367  bu_bomb("nmg_fcut_face: VU is not from an EU");
2368  }
2369 
2370  /* calculate angle this EU will make with edgeuse
2371  * that will be created by the cut/join
2372  */
2373  eu = rs->vu[i]->up.eu_p;
2374  VSUB2(eu_dir, eu->eumate_p->vu_p->v_p->vg_p->coord, eu->vu_p->v_p->vg_p->coord);
2375  angle = atan2(VDOT(y_dir, eu_dir), VDOT(x_dir, eu_dir));
2376 
2377  if (RTG.NMG_debug&DEBUG_FCUT)
2378  bu_log("\tangle for eu %p (vu=%p, #%d) is %g\n",
2379  (void *)eu, (void *)rs->vu[i], i, angle);
2380 
2381  /* select max angle */
2382  if (angle > vu_angle) {
2383  if (RTG.NMG_debug&DEBUG_FCUT)
2384  bu_log("\t\tabove is the new best VU\n");
2385  vu_angle = angle;
2386 
2387  vu_best = rs->vu[i];
2388  *index1 = i;
2389  }
2390  }
2391 
2392  if (vu_best) {
2393  vu1 = vu_best;
2394  lcut->vu1 = vu1;
2395  }
2396 
2397  if (RTG.NMG_debug&DEBUG_FCUT)
2398  bu_log("\tfind_loop_to_cut: selecting VU1 %p\n", (void *)vu1);
2399  }
2400  }
2401 
2402  if (RTG.NMG_debug&DEBUG_FCUT)
2403  bu_log("\tfind_loop_to_cut: returning %ld cuts (index1=%d, index2=%d)\n",
2404  BU_PTBL_END(cuts), *index1, *index2);
2405 
2406  return cuts;
2407 }
2408 
2409 
2410 static fastf_t
2411 nmg_eu_angle(struct edgeuse *eu, struct vertex *vp)
2412 {
2413  struct faceuse *fu;
2414  struct vertex_g *vg1, *vg2;
2415  vect_t norm;
2416  vect_t x_dir;
2417  vect_t y_dir;
2418  vect_t eu_dir;
2419  fastf_t angle;
2420 
2421  NMG_CK_EDGEUSE(eu);
2422  NMG_CK_VERTEX(vp);
2423 
2424  fu = nmg_find_fu_of_eu(eu);
2425  NMG_CK_FACEUSE(fu);
2426  NMG_GET_FU_NORMAL(norm, fu);
2427 
2428  vg1 = eu->vu_p->v_p->vg_p;
2429  vg2 = eu->eumate_p->vu_p->v_p->vg_p;
2430 
2431  VSUB2(x_dir, vg1->coord, vp->vg_p->coord);
2432  VUNITIZE(x_dir);
2433  VCROSS(y_dir, norm, x_dir);
2434  VUNITIZE(y_dir);
2435 
2436  VSUB2(eu_dir, vg2->coord, vg1->coord);
2437  angle = atan2(VDOT(eu_dir, y_dir), VDOT(eu_dir, x_dir));
2438 
2439  return angle;
2440 }
2441 
2442 
2443 static int
2444 find_best_vu(int start, int end, struct vertex *other_vp, struct nmg_ray_state *rs)
2445 {
2446  struct edgeuse *eu;
2447  struct vertexuse *best_vu;
2448  struct loopuse *best_lu;
2449  fastf_t best_angle;
2450  int best_index;
2451  int other_is_in_best = -42;
2452  int nmg_class;
2453  int i;
2454 
2455  if (RTG.NMG_debug&DEBUG_FCUT)
2456  bu_log("find_best_vu: start=%d, end=%d, other_vp=%p, rs=%p\n",
2457  start, end, (void *)other_vp, (void *)rs);
2458 
2459  NMG_CK_VERTEX(other_vp);
2460  NMG_CK_RAYSTATE(rs);
2461 
2462  if (start == end-1) {
2463  if (RTG.NMG_debug&DEBUG_FCUT)
2464  bu_log("\tfind_best_vu returning %d\n", start);
2465 
2466  return start;
2467  }
2468 
2469  best_vu = rs->vu[start];
2470  best_lu = nmg_find_lu_of_vu(best_vu);
2471  best_index = start;
2472  eu = best_vu->up.eu_p;
2473  best_angle = nmg_eu_angle(eu, other_vp);
2474 
2475  if (BU_LIST_FIRST_MAGIC(&best_lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
2476  other_is_in_best = 0;
2477  } else if (nmg_loop_is_a_crack(best_lu)) {
2478  other_is_in_best = 0;
2479  } else {
2480  nmg_class = nmg_class_pt_lu_except(other_vp->vg_p->coord, best_lu, (struct edge *)NULL, rs->tol);
2481 
2482  if ((nmg_class == NMG_CLASS_AinB && best_lu->orientation == OT_SAME) ||
2483  (nmg_class == NMG_CLASS_AoutB && best_lu->orientation == OT_OPPOSITE))
2484  other_is_in_best = 1;
2485  else if (nmg_class == NMG_CLASS_AonBshared) {
2486  bu_log("find_best_vu: There is a loop to cut, lu=%p\n", (void *)best_lu);
2487  bu_bomb("find_best_vu: There is a loop to cut");
2488  } else
2489  other_is_in_best = 0;
2490  }
2491 
2492  if (RTG.NMG_debug&DEBUG_FCUT)
2493  bu_log("\tfind_best_vu: first choice is index=%d, vu=%p, lu=%p, other_is_in_best=%d\n",
2494  best_index, (void *)best_vu, (void *)best_lu, other_is_in_best);
2495 
2496  for (i=start+1; i<end; i++) {
2497  struct loopuse *lu;
2498 
2499  lu = nmg_find_lu_of_vu(rs->vu[i]);
2500  if (lu != best_lu) {
2501  nmg_class = nmg_classify_lu_lu(lu, best_lu, rs->tol);
2502  if (RTG.NMG_debug&DEBUG_FCUT) {
2503  bu_log("lu %p is %s\n", (void *)lu, nmg_orientation(lu->orientation));
2504  bu_log("best_lu %p is %s\n", (void *)best_lu, nmg_orientation(best_lu->orientation));
2505  bu_log("lu %p is %s w.r.t lu %p\n",
2506  (void *)lu, nmg_class_name(nmg_class), (void *)best_lu);
2507  }
2508 
2509  if (other_is_in_best) {
2510  if (nmg_class == NMG_CLASS_AinB || (nmg_class == NMG_CLASS_AonBshared && lu->orientation == OT_SAME)) {
2511 
2512  best_vu = rs->vu[i];
2513  best_lu = lu;
2514  best_index = i;
2515 
2516  if (RTG.NMG_debug&DEBUG_FCUT)
2517  bu_log("\tfind_best_vu: better choice (inside) - index=%d, vu=%p, lu=%p, other_is_in_best=%d\n",
2518  best_index, (void *)best_vu, (void *)best_lu, other_is_in_best);
2519  /* other_is_in_best can't change */
2520  }
2521  } else {
2522  if (nmg_class == NMG_CLASS_AoutB || (nmg_class == NMG_CLASS_AonBshared && lu->orientation == OT_OPPOSITE)) {
2523  best_vu = rs->vu[i];
2524  best_lu = lu;
2525  best_index = i;
2526 
2527  /* other_is_in_best may change */
2528  if (BU_LIST_FIRST_MAGIC(&best_lu->down_hd) == NMG_VERTEXUSE_MAGIC) {
2529  other_is_in_best = 0;
2530  } else if (nmg_loop_is_a_crack(best_lu)) {
2531  other_is_in_best = 0;
2532  } else {
2533  nmg_class = nmg_class_pt_lu_except(other_vp->vg_p->coord,
2534  best_lu, (struct edge *)NULL, rs->tol);
2535 
2536  if ((nmg_class == NMG_CLASS_AinB && best_lu->orientation == OT_SAME) ||
2537  (nmg_class == NMG_CLASS_AoutB && best_lu->orientation == OT_OPPOSITE))
2538  other_is_in_best = 1;
2539  else if (nmg_class == NMG_CLASS_AonBshared) {
2540  bu_log("find_best_vu: There is a loop to cut, lu=%p\n",
2541  (void *)best_lu);
2542  bu_bomb("find_best_vu: There is a loop to cut");
2543  } else
2544  other_is_in_best = 0;
2545  }
2546  if (RTG.NMG_debug&DEBUG_FCUT)
2547  bu_log("\tfind_best_vu: better choice (outside) - index=%d, vu=%p, lu=%p, other_is_in_best=%d\n",
2548  best_index, (void *)best_vu, (void *)best_lu, other_is_in_best);
2549  }
2550  }
2551  } else {
2552  fastf_t angle;
2553  /* need to choose based on eu directions */
2554 
2555  eu = rs->vu[i]->up.eu_p;
2556  NMG_CK_EDGEUSE(eu);
2557  angle = nmg_eu_angle(eu, other_vp);
2558 
2559  if (RTG.NMG_debug&DEBUG_FCUT)
2560  bu_log("best_angle = %f, eu=%p, eu_angle=%f\n",
2561  best_angle, (void *)eu, angle);
2562  if (angle > best_angle) {
2563  best_angle = angle;
2564  best_vu = rs->vu[i];
2565  best_lu = nmg_find_lu_of_vu(best_vu);
2566  best_index = i;
2567  }
2568  }
2569  }
2570 
2571  return best_index;
2572 }
2573 
2574 
2575 HIDDEN void
2577 {
2578  register int cur;
2579  struct vertexuse *vu1, *vu2;
2580  struct loopuse *new_lu;
2581  struct edgeuse *new_eu1;
2582  struct edgeuse *old_eu;
2583  struct vertex *prev_v;
2584  struct bu_ptbl *cuts;
2585  int prior_start;
2586  int cut_no;
2587 
2588  NMG_CK_RAYSTATE(rs);
2589  BN_CK_TOL(rs->tol);
2590 
2591  if (RTG.NMG_debug&DEBUG_FCUT)
2592  bu_log("nmg_face_combine()\n");
2593 
2594  if (rs->eg_p) NMG_CK_EDGE_G_LSEG(rs->eg_p);
2595 
2596 #if PLOT_BOTH_FACES
2597  nmg_2face_plot(rs->fu1, rs->fu2);
2598 #else
2599  nmg_face_plot(rs->fu1);
2600  nmg_face_plot(rs->fu2);
2601 #endif
2602 
2603  if (RTG.NMG_debug&DEBUG_FCUT) {
2604  bu_log("rs->fu1 = %p\n", (void *)rs->fu1);
2605  bu_log("rs->fu2 = %p\n", (void *)rs->fu2);
2606  nmg_pr_fu_briefly(rs->fu1, "");
2607  bu_log("%d vertices on intersect line\n", rs->nvu);
2608  for (cur = 0; cur < rs->nvu; cur++)
2609  bu_log("\tvu=%p, v=%p, lu=%p\n",
2610  (void *)rs->vu[cur], (void *)rs->vu[cur]->v_p, (void *)nmg_find_lu_of_vu(rs->vu[cur]));
2611  }
2612 
2613 
2614  if (rs->nvu < 2)
2615  return;
2616 
2617  prev_v = (struct vertex *)NULL;
2618  prior_start = 0;
2619  while (1) {
2620  struct edgeuse *eu_tmp;
2621  struct loopuse *lu1 = (struct loopuse *)NULL;
2622  struct loopuse *lu2 = (struct loopuse *)NULL;
2623  point_t mid_pt;
2624  int nmg_class;
2625  int orient1 = 0;
2626  int orient2 = 0;
2627  int prior_end;
2628  int next_start, next_end;
2629  int i;
2630  int index1 = 0, index2 = 0;
2631 
2632  while (rs->vu[prior_start]->v_p == prev_v)
2633  prior_start++;
2634 
2635  vu1 = rs->vu[prior_start];
2636  prior_end = prior_start;
2637 
2638  prev_v = vu1->v_p;
2639 
2640  while (++prior_end < rs->nvu && rs->vu[prior_end]->v_p == vu1->v_p);
2641 
2642  next_start = prior_end;
2643 
2644  if (next_start >= rs->nvu)
2645  break; /* all done */
2646 
2647  vu2 = rs->vu[next_start];
2648  next_end = next_start;
2649  while (++next_end < rs->nvu && rs->vu[next_end]->v_p == vu2->v_p);
2650 
2651  if (RTG.NMG_debug&DEBUG_FCUT) {
2652  bu_log("rs->fu1 = %p\n", (void *)rs->fu1);
2653  bu_log("rs->fu2 = %p\n", (void *)rs->fu2);
2654  bu_log("prior_start=%d. prior_end=%d, next_start=%d, next_end=%d\n",
2655  prior_start, prior_end, next_start, next_end);
2656  bu_log("%d vertices on intersect line\n", rs->nvu);
2657  for (cur = 0; cur < rs->nvu; cur++)
2658  bu_log("\tvu=%p, v=%p, lu=%p\n",
2659  (void *)rs->vu[cur], (void *)rs->vu[cur]->v_p, (void *)nmg_find_lu_of_vu(rs->vu[cur]));
2660  }
2661 
2662  /* look for an EU in this face that connects vu1 and vu2 */
2663  if (nmg_find_eu_in_face(vu1->v_p, vu2->v_p, rs->fu1,
2664  (struct edgeuse *)NULL, 0))
2665  {
2666  if (RTG.NMG_debug&DEBUG_FCUT)
2667  bu_log("Already an edge here\n");
2668  continue;
2669  }
2670 
2671  if (nmg_find_eu_in_face(vu1->v_p, vu2->v_p, rs->fu1->fumate_p,
2672  (struct edgeuse *)NULL, 0))
2673  {
2674  if (RTG.NMG_debug&DEBUG_FCUT)
2675  bu_log("Already an edge here\n");
2676  continue;
2677  }
2678 
2679  /* we know that fu1 does not contain an edge connecting vu1 and vu2,
2680  * Now check if the midpoint is inside or outside fu1.
2681  * Note that ON fu1 is not an option at this point
2682  */
2683  VAVERAGE(mid_pt, vu1->v_p->vg_p->coord, vu2->v_p->vg_p->coord)
2684  nmg_class = nmg_class_pt_fu_except(mid_pt, rs->fu1, (struct loopuse *)NULL,
2685  (void (*)(struct edgeuse *, point_t, const char *))NULL,
2686  (void (*)(struct vertexuse *, point_t, const char *))NULL,
2687  (const char *)NULL, 0, 1, rs->tol);
2688 
2689  if (RTG.NMG_debug&DEBUG_FCUT) {
2690  bu_log("vu1=%p (%g %g %g), vu2=%p (%g %g %g)\n",
2691  (void *)vu1, V3ARGS(vu1->v_p->vg_p->coord),
2692  (void *)vu2, V3ARGS(vu2->v_p->vg_p->coord));
2693  bu_log("\tmid_pt = (%g %g %g)\n", V3ARGS(mid_pt));
2694  bu_log("class for mid point is %s\n", nmg_class_name(nmg_class));
2695  }
2696 
2697  if (nmg_class == NMG_CLASS_AoutB)
2698  continue;
2699 
2700  /* Check if mid-point is in fu2. If fu2 is disjoint loops, this point
2701  * may be outside fu2, and we don't want to cut fu1 here.
2702  */
2703  nmg_class = nmg_class_pt_fu_except(mid_pt, rs->fu2, (struct loopuse *)NULL,
2704  (void (*)(struct edgeuse *, point_t, const char *))NULL,
2705  (void (*)(struct vertexuse *, point_t, const char *))NULL,
2706  (char *)NULL, 0, 0, rs->tol);
2707 
2708  if (nmg_class == NMG_CLASS_AoutB)
2709  continue;
2710 
2711  /* See if there is an edge joining the 2 vertices already, this
2712  * will be used for radial join later */
2713  old_eu = nmg_findeu(vu1->v_p, vu2->v_p, (struct shell *)NULL,
2714  (struct edgeuse *)NULL, 0);
2715 
2716 
2717  cuts = find_loop_to_cut(&index1, &index2, prior_start, prior_end,
2718  next_start, next_end, mid_pt, rs);
2719  if (cuts == (struct bu_ptbl *)NULL) {
2720  index1 = find_best_vu(prior_start, prior_end, vu2->v_p, rs);
2721  index2 = find_best_vu(next_start, next_end, vu1->v_p, rs);
2722  vu1 = rs->vu[index1];
2723  vu2 = rs->vu[index2];
2724  lu1 = nmg_find_lu_of_vu(vu1);
2725  lu2 = nmg_find_lu_of_vu(vu2);
2726  orient1 = lu1->orientation;
2727  orient2 = lu2->orientation;
2728  }
2729 
2730  if (cuts) {
2731  for (cut_no = 0; cut_no < BU_PTBL_END(cuts); cut_no++) {
2732  struct loop_cuts *lcut;
2733 
2734  if (RTG.NMG_debug&DEBUG_FCUT)
2735  bu_log("\tcut loop (#%d of %ld)\n", cut_no, BU_PTBL_END(cuts));
2736 
2737  lcut = (struct loop_cuts *)BU_PTBL_GET(cuts, cut_no);
2738 
2739  vu1 = lcut->vu1;
2740  vu2 = lcut->vu2;
2741  lu1 = lcut->lu;
2742 
2743  new_lu = nmg_cut_loop(vu1, vu2);
2744  new_eu1 = BU_LIST_LAST(edgeuse, &new_lu->down_hd);
2745 
2746  NMG_CK_EDGEUSE(new_eu1);
2747 
2748  /* make intersection edges real */
2749  new_eu1->e_p->is_real = 1;
2750 
2751  nmg_loop_g(lu1->l_p, rs->tol);
2752  nmg_loop_g(new_lu->l_p, rs->tol);
2753 
2754  nmg_lu_reorient(lu1);
2755  nmg_lu_reorient(new_lu);
2756 
2757  if (RTG.NMG_debug&DEBUG_FCUT) {
2758  bu_log("\t\t new_eu = %p\n", (void *)new_eu1);
2759  nmg_pr_fu_briefly(rs->fu1, "");
2760  }
2761  if (old_eu) nmg_radial_join_eu(old_eu, new_eu1, rs->tol);
2762 
2763  /* A new VU has been added to vu2->v_p, add it to the rs->vu[]
2764  * array by overwriting the last use of vu1->v_p
2765  */
2766 
2767  eu_tmp = vu1->up.eu_p;
2768  eu_tmp = BU_LIST_PPREV_CIRC(edgeuse, &eu_tmp->l);
2769  if (eu_tmp->vu_p->v_p != vu2->v_p) {
2770  bu_log("nmg_fcut_face: eu (%p) has wrong vertex (%p) should be (%p)\n",
2771  (void *)eu_tmp, (void *)eu_tmp->vu_p->v_p, (void *)vu2->v_p);
2772  bu_bomb("nmg_fcut_face: eu has wrong vertex");
2773  }
2774 
2775  rs->vu[prior_end-1-cut_no] = eu_tmp->vu_p;
2776  }
2777  bu_ptbl_free(cuts);
2778  bu_free((char *)cuts, "cuts");
2779 
2780  continue;
2781  }
2782 
2783  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) == NMG_VERTEXUSE_MAGIC &&
2784  BU_LIST_FIRST_MAGIC(&lu2->down_hd) == NMG_VERTEXUSE_MAGIC)
2785 
2786  {
2787  struct vertexuse *new_vu2;
2788 
2789  new_vu2 = nmg_join_2singvu_loops(vu1, vu2);
2790  new_eu1 = new_vu2->up.eu_p;
2791  NMG_CK_EDGEUSE(new_eu1);
2792 
2793  /* make intersection edges real */
2794  new_eu1->e_p->is_real = 1;
2795 
2796  nmg_loop_g(lu1->l_p, rs->tol);
2797  lu1->orientation = OT_SAME;
2798  lu1->lumate_p->orientation = OT_SAME;
2799 
2800  if (RTG.NMG_debug&DEBUG_FCUT) {
2801  bu_log("\tjoin 2 singvu loops\n");
2802  nmg_pr_fu_briefly(rs->fu1, "");
2803  }
2804  if (old_eu) nmg_radial_join_eu(old_eu, new_eu1, rs->tol);
2805 
2806  /* vu2 has been killed, replace it in rs->vu[] */
2807 
2808  for (i=next_start; i<next_end; i++) {
2809  if (rs->vu[i] == vu2) {
2810  rs->vu[i] = new_vu2;
2811  break;
2812  }
2813  }
2814 
2815  continue;
2816  }
2817 
2818  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) == NMG_VERTEXUSE_MAGIC &&
2819  BU_LIST_FIRST_MAGIC(&lu2->down_hd) == NMG_EDGEUSE_MAGIC)
2820  {
2821  struct vertexuse *new_vu1;
2822 
2823  new_vu1 = nmg_join_singvu_loop(vu2, vu1);
2824  new_eu1 = new_vu1->up.eu_p;
2825  NMG_CK_EDGEUSE(new_eu1);
2826 
2827  /* make intersection edges real */
2828  new_eu1->e_p->is_real = 1;
2829 
2830  nmg_loop_g(lu2->l_p, rs->tol);
2831  lu2->orientation = orient2;
2832  lu2->lumate_p->orientation = orient2;
2833 
2834  if (RTG.NMG_debug&DEBUG_FCUT) {
2835  bu_log("\tjoin loops vu1 (%p) is sing vu loop\n", (void *)vu1);
2836  nmg_pr_fu_briefly(rs->fu1, "");
2837  }
2838  if (old_eu) nmg_radial_join_eu(old_eu, new_eu1, rs->tol);
2839 
2840  /* A new VU has been added to vu2->v_p, add it to the rs->vu[]
2841  * array by overwriting the last use of vu1->v_p
2842  */
2843 
2844  eu_tmp = new_vu1->up.eu_p;
2845  eu_tmp = BU_LIST_PPREV_CIRC(edgeuse, &eu_tmp->l);
2846  if (eu_tmp->vu_p->v_p != vu2->v_p) {
2847  bu_log("nmg_fcut_face: eu (%p) has wrong vertex (%p) should be (%p)\n",
2848  (void *)eu_tmp, (void *)eu_tmp->vu_p->v_p, (void *)vu2->v_p);
2849  bu_bomb("nmg_fcut_face: eu has wrong vertex");
2850  }
2851 
2852  rs->vu[prior_end-1] = eu_tmp->vu_p;
2853  continue;
2854  }
2855 
2856  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) == NMG_EDGEUSE_MAGIC &&
2857  BU_LIST_FIRST_MAGIC(&lu2->down_hd) == NMG_VERTEXUSE_MAGIC)
2858  {
2859  struct vertexuse *new_vu2;
2860 
2861  new_vu2 = nmg_join_singvu_loop(vu1, vu2);
2862  new_eu1 = new_vu2->up.eu_p;
2863  NMG_CK_EDGEUSE(new_eu1);
2864 
2865  /* make intersection edges real */
2866  new_eu1->e_p->is_real = 1;
2867 
2868  nmg_loop_g(lu1->l_p, rs->tol);
2869  lu1->orientation = orient1;
2870  lu1->lumate_p->orientation = orient1;
2871 
2872  if (RTG.NMG_debug&DEBUG_FCUT) {
2873  bu_log("\tjoin loops vu2 (%p) is sing vu loop\n", (void *)vu2);
2874  nmg_pr_fu_briefly(rs->fu1, "");
2875  }
2876 
2877  if (old_eu) nmg_radial_join_eu(old_eu, new_eu1, rs->tol);
2878 
2879  /* vu2 has been killed, replace it in rs->vu[] */
2880 
2881  for (i=next_start; i<next_end; i++) {
2882  if (rs->vu[i] == vu2) {
2883  rs->vu[i] = new_vu2;
2884  break;
2885  }
2886  }
2887 
2888  continue;
2889  }
2890 
2891  if (lu1 != lu2) {
2892  struct vertexuse *new_vu2;
2893 
2894  new_vu2 = nmg_join_2loops(vu1, vu2);
2895  new_eu1 = new_vu2->up.eu_p;
2896  NMG_CK_EDGEUSE(new_eu1);
2897 
2898  /* make intersection edges real */
2899  new_eu1->e_p->is_real = 1;
2900 
2901  nmg_loop_g(lu1->l_p, rs->tol);
2902 
2903  if (RTG.NMG_debug&DEBUG_FCUT) {
2904  bu_log("\t join 2 loops\n");
2905  bu_log("\t\tvu2 (%p) replaced with new_vu2 %p\n", (void *)vu2, (void *)new_vu2);
2906  nmg_pr_fu_briefly(rs->fu1, "");
2907  }
2908 
2909  if (old_eu) nmg_radial_join_eu(old_eu, new_eu1, rs->tol);
2910 
2911  /* a new use of vu2->v_p has been created add it to the list by
2912  * overwriting a use of the previous vertex
2913  */
2914  rs->vu[prior_end - 1] = new_vu2;
2915 
2916  continue;
2917  }
2918 
2919  bu_log("ERROR in face cutter: something should have been cut!!\n");
2920  bu_log("vu1=%p, vu2=%p\n", (void *)vu1, (void *)vu2);
2921  nmg_pr_fu_briefly(rs->fu1, "");
2922  bu_bomb("ERROR: face cutter didn't cut anything");
2923  }
2924 
2925  if (RTG.NMG_debug&DEBUG_FCUT)
2926  nmg_pr_fu_briefly(rs->fu1, "");
2927 }
2928 
2929 
2930 void
2931 nmg_unlist_v(struct bu_ptbl *b, fastf_t *mag, struct vertex *v)
2932 {
2933  register int i;
2934  struct vertexuse *vu;
2935 
2936  BU_CK_PTBL(b);
2937  NMG_CK_VERTEX(v);
2938  for (i = 0; i < BU_PTBL_END(b); i++) {
2939  vu = (struct vertexuse *)BU_PTBL_GET(b, i);
2940  if (!vu) continue;
2941  if (vu->v_p == v) {
2942  BU_PTBL_GET(b, i) = (long *)0;
2943  mag[i] = MAX_FASTF;
2944  }
2945  }
2946 }
2947 
2948 
2949 /**
2950  * An attempt to fix the condition:
2951  * nmg_assess_eu(): ON vertexuse in middle of edge?
2952  *
2953  * Note that the vertexuse being zapped may have a lower subscript.
2954  *
2955  * Must be called after vu list has been sorted.
2956  */
2957 int
2958 nmg_onon_fix(struct nmg_ray_state *rs, struct bu_ptbl *b, struct bu_ptbl *ob, fastf_t *mag, fastf_t *omag)
2959 
2960 
2961 /* other rs's vu list */
2962 /* list of distances from intersect ray start point */
2963 /* list of distances from intersect ray start point */
2964 {
2965  int i;
2966  int zapped;
2967  struct vertexuse *vu;
2968  struct vertex *v;
2969  int zot;
2970 
2971  NMG_CK_RAYSTATE(rs);
2972  BU_CK_PTBL(b);
2973  BU_CK_PTBL(ob);
2974 
2975  zapped = 0;
2976  for (i = 0; i < BU_PTBL_END(b); i++) {
2977  again:
2978  vu = (struct vertexuse *)BU_PTBL_GET(b, i);
2979  if (!vu) continue;
2980  NMG_CK_VERTEXUSE(vu);
2981  if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC) continue;
2982  v = vu->v_p;
2983  NMG_CK_VERTEX(v);
2984  if ((zot = nmg_assess_eu(vu->up.eu_p, 0, rs, i)) < 0) {
2985  if (RTG.NMG_debug&DEBUG_FCUT) {
2986  bu_log("nmg_onon_fix(): vu[%d] zapped (rev)\n", -zot);
2987  }
2988  doit:
2989  vu = (struct vertexuse *)BU_PTBL_GET(b, -zot);
2990  NMG_CK_VERTEXUSE(vu);
2991  v = vu->v_p;
2992  /* Need to null out all uses of this vertex from both lists */
2993  nmg_unlist_v(b, mag, v);
2994  nmg_unlist_v(ob, omag, v);
2995  zapped++;
2996  goto again;
2997  }
2998 
2999  if ((zot = nmg_assess_eu(vu->up.eu_p, 1, rs, i)) < 0) {
3000  if (RTG.NMG_debug&DEBUG_FCUT) {
3001  bu_log("nmg_onon_fix(): vu[%d] zapped (forw)\n", -zot);
3002  }
3003  goto doit;
3004  }
3005  }
3006  if (zapped) {
3007  int removed;
3008 
3009  /* If any vertexuses got zapped, their pointer was set to NULL.
3010  * They can all be removed from the list in one easy operation.
3011  */
3012  bu_log("nmg_onon_fix(): removing %d dead vertexuses\n", zapped);
3013  /* remove entries from distance list first */
3014  removed = 0;
3015  for (i= BU_PTBL_END(b); i >= 0; i--) {
3016  int count=0;
3017  int j, k;
3018 
3019  j = i;
3020  while (j >= 0 && !BU_PTBL_GET(b, j))
3021  --j;
3022  count = i-j;
3023  removed += count;
3024  for (k = j + 1; k < BU_PTBL_END(b)-removed; k++)
3025  mag[k] = mag[k+count];
3026  }
3027  bu_ptbl_rm(b, 0);
3028  removed = 0;
3029  for (i = BU_PTBL_END(ob); i >= 0; i--) {
3030  int count=0;
3031  int j, k;
3032 
3033  j = i;
3034  while (j>=0 && !BU_PTBL_GET(ob, j)) --j;
3035  count = i-j;
3036  removed += count;
3037  for (k = j + 1; k < BU_PTBL_END(ob)-removed; k++)
3038  omag[k] = omag[k+count];
3039  }
3040  bu_ptbl_rm(ob, 0);
3041  return 1;
3042  }
3043 
3044  return 0;
3045 }
3046 
3047 
3048 /**
3049  * The main face cut handler.
3050  * Called from nmg_inter.c by nmg_isect_2faces().
3051  *
3052  * A wrapper for nmg_face_combine, for now.
3053  *
3054  * The two vertexuse lists may be of different lengths, because
3055  * one may have multiple uses of a vertex, while the other has only
3056  * a single use of that same vertex.
3057  */
3058 struct edge_g_lseg *
3059 nmg_face_cutjoin(struct bu_ptbl *b1, struct bu_ptbl *b2, fastf_t *mag1, fastf_t *mag2, struct faceuse *fu1, struct faceuse *fu2, fastf_t *pt, fastf_t *dir, struct edge_g_lseg *eg, const struct bn_tol *tol)
3060 /* table of vertexuses in fu1 on intercept line */
3061 /* table of vertexuses in fu2 on intercept line */
3062 /* table of distances to vertexuses from is->pt */
3063 /* table of distances to vertexuses from is->pt */
3064 /* face being worked */
3065 /* for plane equation */
3066 
3067 
3068 /* may be null. geometry of isect line */
3069 
3070 {
3071  struct vertexuse **vu1, **vu2;
3072  int i;
3073  struct nmg_ray_state rs1;
3074  struct nmg_ray_state rs2;
3075 
3076  if (RTG.NMG_debug&DEBUG_FCUT) {
3077  bu_log("\nnmg_face_cutjoin(fu1=%p, fu2=%p) eg=%p START\n", (void *)fu1, (void *)fu2, (void *)eg);
3078  }
3079 
3080  BN_CK_TOL(tol);
3081  NMG_CK_FACEUSE(fu1);
3082  NMG_CK_FACEUSE(fu2);
3083 
3084  /* Perhaps this should only happen when debugging is on? */
3085  if (RTG.NMG_debug&DEBUG_FCUT && (b1->end <= 0 || b2->end <= 0)) {
3086  bu_log("nmg_face_cutjoin(fu1=%p, fu2=%p): WARNING empty list %ld %ld\n",
3087  (void *)fu1, (void *)fu2, b1->end, b2->end);
3088  }
3089 
3090 top:
3091  /*
3092  * Sort hit points by increasing distance, vertex ptr, vu ptr,
3093  * and eliminate any duplicate vu's.
3094  */
3095  ptbl_vsort(b1, pt, dir, mag1, tol->dist);
3096  ptbl_vsort(b2, pt, dir, mag2, tol->dist);
3097 
3098  vu1 = (struct vertexuse **)b1->buffer;
3099  vu2 = (struct vertexuse **)b2->buffer;
3100 
3101  /* Print list of intersections */
3102  if (RTG.NMG_debug&DEBUG_FCUT) {
3103  bu_log("Ray vu intersection list:\n");
3104  for (i = 0; i < b1->end; i++) {
3105  bu_log(" %d %e ", i, mag1[i]);
3106  nmg_pr_vu_briefly(vu1[i], (char *)0);
3107  }
3108  for (i = 0; i < b2->end; i++) {
3109  bu_log(" %d %e ", i, mag2[i]);
3110  nmg_pr_vu_briefly(vu2[i], (char *)0);
3111  }
3112  }
3113 
3114  /* Check to make sure that intersector didn't miss anything */
3115  if (nmg_ck_vu_ptbl(b1, fu1) || nmg_ck_vu_ptbl(b2, fu2)) goto top;
3116 
3117 
3118  /* this block of code checks if the two lists of intersection vertexuses
3119  * contain vertexuses from the appropriate faceuse */
3120  if (RTG.NMG_debug&DEBUG_FCUT) {
3121  int found1=(-1), found2=(-1); /* -1 => not set, 0 => no vertexuses from faceuse found */
3122  int tmp_found;
3123  struct faceuse *fu;
3124  struct vertexuse *vu;
3125 
3126  /* list b1 should contain vertexuses from faceuse fu1 */
3127  for (i = 0; i < BU_PTBL_END(b1); i++) {
3128  tmp_found = 0;
3129  vu = (struct vertexuse *)BU_PTBL_GET(b1, i);
3130  fu = nmg_find_fu_of_vu(vu);
3131  if (fu == fu1)
3132  tmp_found = 1;
3133  if (found1 == (-1))
3134  found1 = tmp_found;
3135  else if (tmp_found != found1) {
3136  /* some found, some not found!!!!! */
3137  bu_log ("nmg_face_cutjoin: Intersection list is screwy for face 1\n");
3138  break;
3139  }
3140  }
3141 
3142  /* and list b2 should contain vertexuses from faceuse fu2 */
3143  for (i = 0; i < BU_PTBL_END(b2); i++) {
3144  tmp_found = 0;
3145  vu = (struct vertexuse *)BU_PTBL_GET(b2, i);
3146  fu = nmg_find_fu_of_vu(vu);
3147  if (fu == fu2)
3148  tmp_found = 1;
3149  if (found2 == (-1))
3150  found2 = tmp_found;
3151  else if (tmp_found != found2) {
3152  /* some found, some not found!!!!! */
3153  bu_log ("nmg_face_cutjoin: Intersection list is screwy for face 2\n");
3154  break;
3155  }
3156  }
3157  if (!found1)
3158  bu_log("nmg_face_cutjoin: intersection list for face 1 doesn't contain vertexuses from face 1!!!\n");
3159  if (!found2)
3160  bu_log("nmg_face_cutjoin: intersection list for face 2 doesn't contain vertexuses from face 2!!!\n");
3161  }
3162 
3163  nmg_face_rs_init(&rs1, b1, fu1, fu2, pt, dir, eg, tol);
3164  nmg_face_rs_init(&rs2, b2, fu2, fu1, pt, dir, eg, tol);
3165  nmg_fcut_face(&rs1);
3166  nmg_fcut_face(&rs2);
3167 
3168  /* Can't do simplifications here,
3169  * because the caller's linked lists & pointers might get disrupted.
3170  */
3171 
3172  /* Merging uses of common edges is OK, though, and quite necessary. */
3173  i = nmg_mesh_two_faces(fu1, fu2, tol);
3174  if (i) {
3175  if (RTG.NMG_debug&DEBUG_FCUT)
3176  bu_log("nmg_face_cutjoin() meshed %d edges\n", i);
3177  }
3178  if (RTG.NMG_debug&DEBUG_FCUT) {
3179  bu_log("nmg_face_cutjoin(fu1=%p, fu2=%p) eg=%p END\n", (void *)fu1, (void *)fu2, (void *)rs1.eg_p);
3180  }
3181  if (eg && !rs1.eg_p)
3182  bu_bomb("nmg_face_cutjoin() lost edge_g_lseg?\n");
3183  if (eg && eg != rs1.eg_p)
3184  bu_log("nmg_face_cutjoin() changed from eg=%p to rs1.eg_p=%p\n", (void *)eg, (void *)rs1.eg_p);
3185  return rs1.eg_p;
3186 }
3187 
3188 
3189 void
3190 nmg_fcut_face_2d(struct bu_ptbl *vu_list, fastf_t *UNUSED(mag), struct faceuse *fu1, struct faceuse *fu2, struct bn_tol *tol)
3191 {
3192  struct nmg_ray_state rs;
3193  point_t pt;
3194  vect_t dir;
3195  struct edge_g_lseg *eg;
3196 
3197  NMG_CK_FACEUSE(fu1);
3198  NMG_CK_FACEUSE(fu2);
3199  BN_CK_TOL(tol);
3200  BU_CK_PTBL(vu_list);
3201 
3202  VSETALL(pt, 0.0);
3203  VSET(dir, 1.0, 0.0 , 0.0);
3204  eg = (struct edge_g_lseg *)NULL;
3205 
3206  nmg_face_rs_init(&rs, vu_list, fu1, fu2, pt, dir, eg, tol);
3207 
3208  nmg_fcut_face(&rs);
3209 }
3210 
3211 
3212 /*
3213  * State machine transition tables
3214  * Indexed by MNG_V_ASSESSMENT values.
3215  */
3216 
3220  int action;
3221 };
3222 
3223 
3224 static const struct state_transitions nmg_state_is_out[17] = {
3242 };
3243 
3244 
3245 static const struct state_transitions nmg_state_is_on_L[17] = {
3263 };
3264 
3265 
3266 static const struct state_transitions nmg_state_is_on_R[17] = {
3284 };
3285 
3286 
3287 static const struct state_transitions nmg_state_is_on_B[17] = {
3305 };
3306 
3307 
3308 static const struct state_transitions nmg_state_is_on_N[17] = {
3326 };
3327 
3328 
3329 static const struct state_transitions nmg_state_is_in[17] = {
3347 };
3348 
3349 
3350 /**
3351  * Given current (old) state, assess the current vertexuse, and
3352  * pull the appropriate action and new state from the tables.
3353  * Then perform the indicated action.
3354  *
3355  * The real work happens in the nmg_assess_vu() and in the tables.
3356  *
3357  * Explicit Returns -
3358  * Nothing useful yet.
3359  *
3360  * Implicit Returns -
3361  * Modifications to the NMG shell being operated on.
3362  * Updated state etc. in nmg_ray_state structure.
3363  */
3364 int
3365 nmg_face_state_transition(struct nmg_ray_state *rs, int pos, int multi, int other_rs_state)
3366 {
3367  int assessment;
3368  int old_state;
3369  int new_state;
3370  const struct state_transitions *stp;
3371  struct vertexuse *vu;
3372  struct vertexuse *prev_vu = (struct vertexuse *)NULL;
3373  struct loopuse *lu;
3374  struct loopuse *prev_lu;
3375  struct faceuse *fu;
3376  struct edgeuse *eu;
3377  struct edgeuse *first_new_eu;
3378  struct edgeuse *second_new_eu;
3379  struct edgeuse *old_eu;
3380  int e_assessment;
3381  int action;
3382  int e_pos;
3383 
3384  NMG_CK_RAYSTATE(rs);
3385  vu = rs->vu[pos];
3386  NMG_CK_VERTEXUSE(vu);
3387  BN_CK_TOL(rs->tol);
3388  if (rs->eg_p) NMG_CK_EDGE_G_LSEG(rs->eg_p);
3389 
3390  if (RTG.NMG_debug&DEBUG_FCUT) {
3391  bu_log("nmg_face_state_transition(vu %p, pos=%d) START\n",
3392  (void *)vu, pos);
3393  bu_log("Plotting this loopuse, before action:\n");
3394  nmg_pr_lu_briefly(nmg_find_lu_of_vu(vu), (char *)0);
3396  rs->vu[0], rs->vu[rs->nvu-1], rs->left);
3397  }
3398 
3399  if (RTG.NMG_debug & DEBUG_VERIFY) {
3400  nmg_vfu(&rs->fu1->s_p->fu_hd, rs->fu1->s_p);
3401  nmg_vfu(&rs->fu2->s_p->fu_hd, rs->fu2->s_p);
3404  }
3405 
3406  assessment = nmg_assess_vu(rs, pos);
3407  old_state = rs->state;
3408  switch (old_state) {
3409  default:
3410  case NMG_STATE_ERROR:
3411  bu_bomb("nmg_face_state_transition: was in ERROR state\n");
3412  case NMG_STATE_OUT:
3413  stp = &nmg_state_is_out[assessment];
3414  break;
3415  case NMG_STATE_ON_L:
3416  stp = &nmg_state_is_on_L[assessment];
3417  break;
3418  case NMG_STATE_ON_R:
3419  stp = &nmg_state_is_on_R[assessment];
3420  break;
3421  case NMG_STATE_ON_B:
3422  stp = &nmg_state_is_on_B[assessment];
3423  break;
3424  case NMG_STATE_ON_N:
3425  stp = &nmg_state_is_on_N[assessment];
3426  break;
3427  case NMG_STATE_IN:
3428  stp = &nmg_state_is_in[assessment];
3429  break;
3430  }
3431 
3432  if (assessment != stp->assessment) {
3433  bu_log("assessment=%d, stp->assessment=%d, error\n", assessment, stp->assessment);
3434  bu_bomb("nmg_face_state_transition() bad table\n");
3435  }
3436  action = stp->action;
3437  new_state = stp->new_state;
3438  rs->last_action = action;
3439 
3440  /*
3441  * Major optimization here.
3442  * If the state machine for the other face is still in OUT state,
3443  * then take no actions in this face,
3444  * because any cutting or joining done here will have no effect
3445  * on the final result of the boolean, it's just extra work.
3446  * This can reduce the amount of unnecessary topology by 75% or more.
3447  */
3448  if (other_rs_state == NMG_STATE_OUT && action != NMG_ACTION_ERROR &&
3449  action != NMG_ACTION_NONE) {
3450  action = NMG_ACTION_NONE_OPTIM;
3451  }
3452 
3453  if (RTG.NMG_debug&DEBUG_FCUT) {
3454  bu_log("nmg_face_state_transition(vu %p, pos=%d)\n\told=%s, assessed=%s, new=%s, action=%s\n",
3455  (void *)vu, pos,
3456  nmg_state_names[old_state], nmg_v_assessment_names[assessment],
3457  nmg_state_names[new_state], action_names[action]);
3458  }
3459 
3460  /*
3461  * Force edge geometry that lies on the intersection line
3462  * to use the edge_g_lseg structure of the intersection line (ray).
3463  */
3464  if (NMG_V_ASSESSMENT_PREV(assessment) == NMG_E_ASSESSMENT_ON_REV) {
3465  eu = nmg_find_eu_of_vu(vu);
3466  eu = BU_LIST_PPREV_CIRC(edgeuse, eu);
3467  NMG_CK_EDGEUSE(eu);
3468  if (!rs->eg_p || eu->g.lseg_p != rs->eg_p) {
3469  if (rs->eg_p) {
3470  NMG_CK_EDGE_G_LSEG(rs->eg_p);
3471  }
3472  nmg_edge_geom_isect_line(eu, rs, "force ON_REV to line");
3473  }
3474  }
3475  if (NMG_V_ASSESSMENT_NEXT(assessment) == NMG_E_ASSESSMENT_ON_FORW) {
3476  eu = nmg_find_eu_of_vu(vu);
3477  NMG_CK_EDGEUSE(eu);
3478  if (!rs->eg_p || eu->g.lseg_p != rs->eg_p) {
3479  if (rs->eg_p) {
3480  NMG_CK_EDGE_G_LSEG(rs->eg_p);
3481  }
3482  nmg_edge_geom_isect_line(eu, rs, "force ON_FORW to line");
3483  }
3484  }
3485 
3486  switch (action) {
3487  default:
3488  case NMG_ACTION_ERROR:
3489  bomb:
3490  {
3491  struct bu_vls str = BU_VLS_INIT_ZERO;
3492 
3493  bu_log("nmg_face_state_transition: got action=ERROR\n");
3494 
3495  bu_vls_printf(&str, "nmg_face_state_transition(vu %p, pos=%d)\n\told=%s, assessed=%s, new=%s, action=%s\n",
3496  (void *)vu, pos,
3497  nmg_state_names[old_state], nmg_v_assessment_names[assessment],
3498  nmg_state_names[new_state], action_names[action]);
3499  if (RT_G_DEBUG || RTG.NMG_debug) {
3500  /* First, print this faceuse */
3501  lu = nmg_find_lu_of_vu(vu);
3502  NMG_CK_LOOPUSE(lu);
3503  /* Print the faceuse for later analysis */
3504  bu_log("Loop with the offending vertex\n");
3505  nmg_pr_lu_briefly(lu, (char *)0);
3506  }
3507  /* Explode */
3508  bu_bomb(bu_vls_addr(&str));
3509  }
3510  case NMG_ACTION_NONE:
3511  case NMG_ACTION_NONE_OPTIM:
3512  if (*(vu->up.magic_p) != NMG_LOOPUSE_MAGIC) break;
3513  lu = vu->up.lu_p;
3514  if (old_state != NMG_STATE_OUT && lu->orientation == OT_BOOLPLACE) {
3515  /* If something connects to the surface of our face,
3516  * hang on to this vertexuse.
3517  */
3518  lu->orientation = lu->lumate_p->orientation = OT_UNSPEC;
3519  }
3520  break;
3521  case NMG_ACTION_VFY_EXT:
3522  /* Verify loop containing this vertex has external orientation */
3523  lu = nmg_find_lu_of_vu(vu);
3524  NMG_CK_LOOPUSE(lu);
3525  switch (lu->orientation) {
3526  case OT_SAME:
3527  break;
3528  default:
3529  bu_log("nmg_face_state_transition: VFY_EXT got orientation=%s\n",
3530  nmg_orientation(lu->orientation));
3531  break;
3532  }
3533  break;
3534  case NMG_ACTION_VFY_MULTI:
3535  /* Ensure that there are multiple vertexuse's at this
3536  * vertex along the ray.
3537  * If not, the table entry is illegal.
3538  */
3539  if (multi) break;
3540  bu_log("nmg_face_state_transition: VFY_MULTI had only 1 vertex\n");
3541  goto bomb;
3543  /*
3544  * Split edge to include vertex from this lone vert loop.
3545  * This only happens in an "ON" state, so split the edge that
3546  * starts (or ends) with the previously seen vertex.
3547  * Note that the forward going edge may point the wrong way,
3548  * i.e., not lie on the ray at all.
3549  * Also note that the previous member(s) of vu[] may be
3550  * lone vert loops that were not processed due to optimization,
3551  * so it may be necessary to look back a ways to find
3552  * the vertexuse which started this ON edge.
3553  */
3554  lu = nmg_find_lu_of_vu(vu);
3555  NMG_CK_LOOPUSE(lu);
3556  for (e_pos = pos-1; e_pos >= 0; e_pos--) {
3557  prev_vu = rs->vu[e_pos];
3558  NMG_CK_VERTEXUSE(prev_vu);
3559  /* lu is lone vert loop; l_p is distinct from prev_lu->l_p */
3560  if (*prev_vu->up.magic_p == NMG_EDGEUSE_MAGIC)
3561  break;
3562  /* Not an edgeuse, prob. a loopuse, continue backwards */
3563  }
3564  if (e_pos < 0) bu_bomb("nmg_face_state_transition: LONE_V_ESPLIT can't find start of edge!\n");
3565  eu = prev_vu->up.eu_p;
3566  NMG_CK_EDGEUSE(eu);
3567  e_assessment = nmg_assess_eu(eu, 1, rs, e_pos); /* forw */
3568  if (e_assessment == NMG_E_ASSESSMENT_ON_FORW) {
3569  /* "eu" (forw) is the right edge to split */
3570  } else {
3571  e_assessment = nmg_assess_eu(eu, 0, rs, e_pos); /*rev*/
3572  if (e_assessment == NMG_E_ASSESSMENT_ON_REV) {
3573  /* (reverse) "eu" is the right one */
3574  eu = BU_LIST_PPREV_CIRC(edgeuse, eu);
3575  } else {
3576  /* What went wrong? */
3577  bu_log("LONE_V_ESPLIT: rev e_assessment = %s\n", nmg_e_assessment_names[e_assessment]);
3578  bu_bomb("nmg_face_state_transition: LONE_V_ESPLIT could not find ON edge to split\n");
3579  }
3580  }
3581  /* Break edge, update vu table with new value */
3582  if (vu->v_p == eu->vu_p->v_p) {
3583  /* Edge already starts at same vertex */
3584  rs->vu[pos] = eu->vu_p;
3585  } else if (vu->v_p == eu->eumate_p->vu_p->v_p) {
3586  /* Edge already ends at same vertex */
3587  rs->vu[pos] = BU_LIST_PNEXT_CIRC(edgeuse, eu)->vu_p;
3588  } else {
3589  /* Break edge, force onto isect line */
3590  nmg_edge_geom_isect_line(eu, rs, "LONE_V_ESPLIT, before edge split");
3591  rs->vu[pos] = nmg_ebreaker(vu->v_p, eu, rs->tol)->vu_p;
3592  }
3593  /* Kill lone vertex loop (and vertexuse) */
3594  nmg_klu(lu);
3595  if (RTG.NMG_debug&DEBUG_FCUT) {
3596  bu_log("After LONE_V_ESPLIT, the final loop:\n");
3597  lu = nmg_find_lu_of_vu(rs->vu[pos]);
3598  NMG_CK_LOOPUSE(lu);
3599  nmg_pr_lu(lu, " ");
3600  nmg_plot_lu_ray(lu, rs->vu[0], rs->vu[rs->nvu-1], rs->left);
3601  }
3602  break;
3604  /*
3605  * Take current loop on a jaunt from current (prev_vu) edge
3606  * up to the vertex (vu) of this lone vertex loop,
3607  * and back again.
3608  * This only happens in "IN" state.
3609  */
3610  prev_vu = rs->vu[pos-1];
3611  NMG_CK_VERTEXUSE(prev_vu);
3612 
3613  if (*prev_vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
3614  /* Both prev and current are lone vertex loops */
3615  rs->vu[pos] = nmg_join_2singvu_loops(prev_vu, vu);
3616  /* Set orientation */
3617  lu = nmg_find_lu_of_vu(rs->vu[pos]);
3618  NMG_CK_LOOPUSE(lu);
3619  /* If state is IN, this is a "crack" loop */
3620  nmg_set_lu_orientation(lu, old_state==NMG_STATE_IN);
3621  } else {
3622  rs->vu[pos] = nmg_join_singvu_loop(prev_vu, vu);
3623  }
3624 
3625  /* We know edge geom is null, make it be the isect line */
3626  first_new_eu = BU_LIST_PPREV_CIRC(edgeuse, rs->vu[pos]->up.eu_p);
3627  nmg_edge_geom_isect_line(first_new_eu, rs, "LONE_V_JAUNT, new edge");
3628 
3629  /* Fusing to this new edge will happen in nmg_face_cutjoin() */
3630 
3631  /* Recompute loop geometry. Bounding box may have expanded */
3632  nmg_loop_g(nmg_find_lu_of_vu(rs->vu[pos])->l_p, rs->tol);
3633 
3634  if (RTG.NMG_debug&DEBUG_FCUT) {
3635  bu_log("After LONE_V_JAUNT, the final loop:\n");
3636  nmg_pr_lu_briefly(nmg_find_lu_of_vu(rs->vu[pos]), (char *)0);
3638  rs->vu[0], rs->vu[rs->nvu-1], rs->left);
3639  }
3640  break;
3641  case NMG_ACTION_CUTJOIN:
3642  /*
3643  * Cut loop into two, or join two into one.
3644  * The operation happens between the previous vu
3645  * and the current one.
3646  * If the two vu's are part of the same loop,
3647  * then cut the loop into two, otherwise
3648  * join the two loops into one.
3649  */
3650  lu = nmg_find_lu_of_vu(vu);
3651  NMG_CK_LOOPUSE(lu);
3652  fu = lu->up.fu_p;
3653  NMG_CK_FACEUSE(fu);
3654  prev_vu = rs->vu[pos-1];
3655  NMG_CK_VERTEXUSE(prev_vu);
3656  prev_lu = nmg_find_lu_of_vu(prev_vu);
3657  NMG_CK_LOOPUSE(prev_lu);
3658 
3659  /* See if there is an edge joining the 2 vertices already */
3660  old_eu = nmg_findeu(prev_vu->v_p, vu->v_p, (struct shell *)NULL,
3661  (struct edgeuse *)NULL, 0);
3662 
3663  if (lu->l_p == prev_lu->l_p) {
3664  int is_crack;
3665 
3666  /* Same loop, cut into two */
3667  is_crack = nmg_loop_is_a_crack(lu);
3668  if (RTG.NMG_debug&DEBUG_FCUT)
3669  bu_log("Calling nmg_cut_loop(prev_vu=%p, vu=%p) is_crack=%d, old_eu=%p\n",
3670  (void *)prev_vu, (void *)vu, is_crack, (void *)old_eu);
3671  if (prev_vu->v_p == vu->v_p) {
3672  /* The loop touches itself already */
3673  lu = nmg_split_lu_at_vu(prev_lu, prev_vu);
3674  } else {
3675  lu = nmg_cut_loop(prev_vu, vu);
3676 
3677  /* New edge has been created between 2 verts, fuse */
3678  /* first_new_eu starts at vu, ends at prev_vu */
3679  /* second_new_eu starts at prev_vu, ends at vu */
3680  first_new_eu = BU_LIST_PPREV_CIRC(edgeuse, &prev_vu->up.eu_p->l);
3681  second_new_eu = BU_LIST_PPREV_CIRC(edgeuse, &vu->up.eu_p->l);
3682  NMG_CK_EDGEUSE(first_new_eu);
3683  NMG_CK_EDGEUSE(second_new_eu);
3684  if (first_new_eu->vu_p->v_p != vu->v_p || first_new_eu->eumate_p->vu_p->v_p != prev_vu->v_p) {
3685  nmg_pr_vu_briefly(prev_vu, 0);
3686  nmg_pr_vu_briefly(vu, 0);
3687  nmg_pr_eu_endpoints(first_new_eu, 0);
3688  nmg_pr_eu_endpoints(second_new_eu, 0);
3689  if (old_eu) nmg_pr_eu_endpoints(old_eu, 0);
3690  bu_bomb("nmg_face_state_transition() cut loop bafflement\n");
3691  }
3692  /* Fuse new edge to intersect line, old edge */
3693  nmg_edge_geom_isect_line(first_new_eu, rs, "CUTJOIN, new edge after loop cut");
3694  if (old_eu) nmg_radial_join_eu(old_eu, first_new_eu, rs->tol);
3695  }
3696 
3697  nmg_loop_g(lu->l_p, rs->tol);
3698  nmg_loop_g(prev_lu->l_p, rs->tol);
3699 
3700  nmg_lu_reorient(lu);
3701  nmg_lu_reorient(prev_lu);
3702 
3703  if (RTG.NMG_debug&DEBUG_FCUT) {
3704  bu_log("After CUT, the final loop:\n");
3705  nmg_pr_lu_briefly(nmg_find_lu_of_vu(rs->vu[pos]), (char *)0);
3707  rs->vu[0], rs->vu[rs->nvu-1], rs->left);
3708  }
3709  break;
3710  }
3711  /*
3712  * prev_vu and vu are in different loops,
3713  * join the two loops into one loop.
3714  * No edgeuses are deleted at this stage,
3715  * so some "snakes" may appear in the process.
3716  */
3717  if (RTG.NMG_debug&DEBUG_FCUT) {
3718  bu_log("nmg_face_state_transition() joining 2 loops, prev_vu=%p, vu=%p, old_eu=%p\n",
3719  (void *)prev_vu, (void *)vu, (void *)old_eu);
3720  }
3721 
3722  if (*prev_vu->up.magic_p == NMG_LOOPUSE_MAGIC ||
3723  *vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
3724  /* One (or both) is a loop of a single vertex */
3725  /* This is the special boolean vertex marker */
3726 
3727  /* See if there is an existing edge between
3728  * the two vertices.
3729  */
3730 
3731  if (*prev_vu->up.magic_p == NMG_LOOPUSE_MAGIC &&
3732  *vu->up.magic_p != NMG_LOOPUSE_MAGIC) {
3733  if (RTG.NMG_debug&DEBUG_FCUT)
3734  bu_log("\tprev_vu is a vertex loop\n");
3735  /* if prev_vu is geometrically on an edge that goes through vu,
3736  * then split that edge at prev_vu */
3737  rs->vu[pos-1] = nmg_join_singvu_loop(vu, prev_vu);
3738  } else if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC &&
3739  *prev_vu->up.magic_p != NMG_LOOPUSE_MAGIC) {
3740  if (RTG.NMG_debug&DEBUG_FCUT)
3741  bu_log("\tvu is a vertex loop\n");
3742  /* if vu is geometrically on an edge that goes through prev_vu,
3743  * then split that edge at vu */
3744  rs->vu[pos] = nmg_join_singvu_loop(prev_vu, vu);
3745  } else {
3746  /* Both are loops of single vertex */
3747  if (RTG.NMG_debug&DEBUG_FCUT)
3748  bu_log("\tprev_vu and vu are vertex loops\n");
3749  vu = rs->vu[pos] = nmg_join_2singvu_loops(prev_vu, vu);
3750  /* Set orientation */
3751  lu = nmg_find_lu_of_vu(vu);
3752  NMG_CK_LOOPUSE(lu);
3753  nmg_set_lu_orientation(lu, old_state==NMG_STATE_IN);
3754  }
3755  } else {
3756  rs->vu[pos] = nmg_join_2loops(prev_vu, vu);
3757  }
3758 
3759  /* XXX If an edge has been built between prev_vu and vu,
3760  * force its geometry to lie on the ray.
3761  */
3762  vu = rs->vu[pos];
3763  lu = nmg_find_lu_of_vu(vu);
3764  NMG_CK_LOOPUSE(lu);
3765  prev_vu = rs->vu[pos-1];
3766  eu = prev_vu->up.eu_p;
3767  NMG_CK_EDGEUSE(eu);
3768  first_new_eu = BU_LIST_PPREV_CIRC(edgeuse, rs->vu[pos]->up.eu_p);
3769  NMG_CK_EDGEUSE(first_new_eu);
3770  if (eu == first_new_eu) {
3771  nmg_edge_geom_isect_line(first_new_eu, rs, "CUTJOIN new edge");
3772  if (old_eu) nmg_radial_join_eu(old_eu, eu, rs->tol);
3773  }
3774 
3775  /* Recompute loop geometry. Bounding box may have expanded */
3776  nmg_loop_g(lu->l_p, rs->tol);
3777 
3778  if (RTG.NMG_debug&DEBUG_FCUT) {
3779  bu_log("After JOIN, the final loop:\n");
3780  nmg_pr_lu_briefly(lu, (char *)0);
3781  nmg_plot_lu_ray(lu, rs->vu[0], rs->vu[rs->nvu-1], rs->left);
3782  }
3783  break;
3784  }
3785 
3786  rs->state = new_state;
3787 
3788  if (RTG.NMG_debug & DEBUG_VERIFY) {
3789  /* Verify both faces are still OK */
3790  nmg_vfu(&rs->fu1->s_p->fu_hd, rs->fu1->s_p);
3791  nmg_vfu(&rs->fu2->s_p->fu_hd, rs->fu2->s_p);
3794  }
3795 
3796  if (RTG.NMG_debug&DEBUG_FCUT) {
3797  bu_log("nmg_face_state_transition(vu %p, pos=%d) END\n",
3798  (void *)rs->vu[pos], pos);
3799  }
3800  if (rs->eg_p) NMG_CK_EDGE_G_LSEG(rs->eg_p);
3801  return 0;
3802 }
3803 
3804 
3805 /*
3806  * Local Variables:
3807  * mode: C
3808  * tab-width: 8
3809  * indent-tabs-mode: t
3810  * c-file-style: "stroustrup"
3811  * End:
3812  * ex: shiftwidth=4 tabstop=8
3813  */
vect_t ang_x_dir
Definition: nmg_fcut.c:193
int n_vu_in_loop
Definition: nmg_fcut.c:792
void nmg_pr_vu_briefly(const struct vertexuse *vu, char *h)
Definition: nmg_pr.c:702
#define BU_LIST_PNEXT_CIRC(structure, p)
Definition: list.h:442
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
void nmg_lu_reorient(struct loopuse *lu)
Definition: nmg_mod.c:3649
long ** buffer
Definition: ptbl.h:66
#define NMG_EDGEUSE_MAGIC
Definition: magic.h:120
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define NMG_LEFT_LEFT
Definition: nmg_fcut.c:126
struct faceuse * nmg_find_fu_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:270
#define NMG_LEFT_RIGHT
Definition: nmg_fcut.c:127
void rt_vlblock_free(struct bn_vlblock *vbp)
Definition: vlist.c:78
#define NMG_ON_FORW_LEFT
Definition: nmg_fcut.c:134
#define WEDGE2_CD_IN_AB
Definition: nmg_fcut.c:927
#define NMG_STATE_OUT
Definition: nmg_fcut.c:60
#define NMG_ON_REV_ON_REV
Definition: nmg_fcut.c:141
fastf_t hi_ang
Definition: nmg_fcut.c:784
void nmg_radial_join_eu(struct edgeuse *eu1, struct edgeuse *eu2, const struct bn_tol *tol)
Definition: nmg_mesh.c:197
int nmg_assess_vu(struct nmg_ray_state *rs, int pos)
Definition: nmg_fcut.c:710
int nmg_wedge_class(int ass, double a, double b)
Definition: nmg_fcut.c:841
#define BU_LIST_LAST(structure, hp)
Definition: list.h:306
#define NMG_ON_FORW_ON_REV
Definition: nmg_fcut.c:137
struct edge_g_lseg * eg_p
Definition: nmg_fcut.c:185
HIDDEN void ptbl_vsort(struct bu_ptbl *b, fastf_t *pt, fastf_t *dir, fastf_t *mag, fastf_t dist_tol)
Definition: nmg_fcut.c:222
struct loopuse * lu
Definition: nmg_fcut.c:789
struct vertexuse * nmg_join_singvu_loop(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2137
int nmg_class_pt_fu_except(const point_t pt, const struct faceuse *fu, const struct loopuse *ignore_lu, void(*eu_func)(struct edgeuse *, point_t, const char *), void(*vu_func)(struct vertexuse *, point_t, const char *), const char *priv, const int call_on_hits, const int in_or_out_only, const struct bn_tol *tol)
double dist
>= 0
Definition: tol.h:73
#define NMG_RAYSTATE_MAGIC
Definition: nmg_fcut.c:197
void nmg_set_lu_orientation(struct loopuse *lu, int is_opposite)
Definition: nmg_mod.c:3620
int nmg_onon_fix(struct nmg_ray_state *rs, struct bu_ptbl *b, struct bu_ptbl *ob, fastf_t *mag, fastf_t *omag)
Definition: nmg_fcut.c:2958
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
vect_t ang_y_dir
Definition: nmg_fcut.c:194
lu
Definition: nmg_mod.c:3855
#define VSET(a, b, c, d)
Definition: color.c:53
#define VSETALL(a, s)
Definition: color.c:54
#define NMG_ON_FORW_RIGHT
Definition: nmg_fcut.c:135
point_t pt
Definition: nmg_fcut.c:183
#define NMG_STATE_ON_R
Definition: nmg_fcut.c:62
#define M_PI
Definition: fft.h:35
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
#define NMG_CK_RAYSTATE(_p)
Definition: nmg_fcut.c:198
void nmg_face_rs_init(struct nmg_ray_state *rs, struct bu_ptbl *b, struct faceuse *fu1, struct faceuse *fu2, fastf_t *pt, fastf_t *dir, struct edge_g_lseg *eg, const struct bn_tol *tol)
Definition: nmg_fcut.c:1892
#define A_GT_B
Definition: nmg_fcut.c:1278
#define WEDGE2_OVERLAP
Definition: nmg_fcut.c:924
int bu_ptbl_rm(struct bu_ptbl *b, const long *p)
struct edgeuse * nmg_find_eu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:955
#define SMALL_FASTF
Definition: defines.h:342
int nmg_face_coincident_vu_sort(struct nmg_ray_state *rs, int start, int end)
Definition: nmg_fcut.c:1655
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
struct vertexuse * vu2
Definition: nmg_fcut.c:203
#define NMG_ACTION_VFY_EXT
Definition: nmg_fcut.c:160
#define NMG_E_ASSESSMENT_RIGHT
Definition: nmg_fcut.c:79
#define NMG_STATE_ON_N
Definition: nmg_fcut.c:64
Header file for the BRL-CAD common definitions.
fastf_t out_vu_angle
Definition: nmg_fcut.c:781
struct faceuse * fu2
Definition: nmg_fcut.c:189
#define BU_CK_PTBL(_p)
Definition: ptbl.h:74
void nmg_face_plot(const struct faceuse *fu)
Definition: nmg_plot.c:1862
int nmg_classify_lu_lu(const struct loopuse *lu1, const struct loopuse *lu2, const struct bn_tol *tol)
Definition: nmg_class.c:2205
#define WEDGE_LEFT
Definition: nmg_fcut.c:796
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
int loop_index
Definition: nmg_fcut.c:778
struct bn_vlblock * rt_vlblock_init(void)
Definition: vlist.c:71
struct loopuse * nmg_cut_loop(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2283
#define MAX_FASTF
Definition: defines.h:340
#define NMG_LOOPUSE_MAGIC
Definition: magic.h:130
#define HIDDEN
Definition: common.h:86
struct shell * sA
Definition: nmg_fcut.c:186
void nmg_pr_eu_briefly(const struct edgeuse *eu, char *h)
Definition: nmg_pr.c:586
#define WEDGE2_IDENTICAL
Definition: nmg_fcut.c:928
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)
fastf_t min_dot
Definition: nmg_fcut.c:790
#define NMG_E_ASSESSMENT_ON_REV
Definition: nmg_fcut.c:81
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
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
#define NMG_V_ASSESSMENT_ERROR
Definition: nmg_fcut.c:85
struct vertexuse * vu1
Definition: nmg_fcut.c:202
#define NMG_ON_REV_LEFT
Definition: nmg_fcut.c:138
void nmg_edge_g(struct edgeuse *eu)
Definition: nmg_mk.c:1789
if(share_geom)
Definition: nmg_mod.c:3829
#define NMG_ACTION_NONE_OPTIM
Definition: nmg_fcut.c:159
int nmg_use_edge_g(struct edgeuse *eu, uint32_t *magic_p)
Definition: nmg_mk.c:2087
int nmg_assess_eu(struct edgeuse *eu, int forw, struct nmg_ray_state *rs, int pos)
Definition: nmg_fcut.c:551
void nmg_2face_plot(const struct faceuse *fu1, const struct faceuse *fu2)
Definition: nmg_plot.c:1924
int wedge_class
Definition: nmg_fcut.c:786
struct loopuse * lu
Definition: nmg_fcut.c:201
struct shell * sB
Definition: nmg_fcut.c:187
#define A_LT_B
Definition: nmg_fcut.c:1276
#define WEDGE2_NO_OVERLAP
Definition: nmg_fcut.c:925
void * memset(void *s, int c, size_t n)
#define NMG_STATE_IN
Definition: nmg_fcut.c:65
#define RT_G_DEBUG
Definition: raytrace.h:1718
int nmg_loop_is_a_crack(const struct loopuse *lu)
Definition: nmg_info.c:449
void nmg_pr_vu_stuff(const struct nmg_vu_stuff *vs)
Definition: nmg_fcut.c:811
struct loopuse * nmg_split_lu_at_vu(struct loopuse *lu, struct vertexuse *split_vu)
Definition: nmg_mod.c:2457
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
vect_t dir
Definition: nmg_fcut.c:184
#define NMG_STATE_ON_B
Definition: nmg_fcut.c:63
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
void nmg_fcut_face_2d(struct bu_ptbl *vu_list, fastf_t *mag, struct faceuse *fu1, struct faceuse *fu2, struct bn_tol *tol)
Definition: nmg_fcut.c:3190
#define BU_PTBL_GET(ptbl, i)
Definition: ptbl.h:108
struct vertexuse * vu
Definition: nmg_fcut.c:777
struct faceuse * fu1
Definition: nmg_fcut.c:188
double bn_dist_line3_pt3(const point_t pt, const vect_t dir, const point_t a)
#define NMG_ON_REV_ON_FORW
Definition: nmg_fcut.c:140
#define V3ARGS(a)
Definition: color.c:56
#define NMG_RIGHT_ON_REV
Definition: nmg_fcut.c:133
struct vertexuse * nmg_join_2singvu_loops(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2186
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
void nmg_pr_lu_briefly(const struct loopuse *lu, char *h)
Definition: nmg_pr.c:455
static void top()
void bu_sort(void *array, size_t nummemb, size_t sizememb, int(*compare)(const void *, const void *, void *), void *context)
Definition: sort.c:110
int last_action
Definition: nmg_fcut.c:192
struct vertexuse ** vu
Definition: nmg_fcut.c:181
fastf_t min_vu_dot
Definition: nmg_fcut.c:782
#define BU_LIST_PNEXT(structure, p)
Definition: list.h:422
struct bu_list l
Definition: ptbl.h:63
#define UNUSED(parameter)
Definition: common.h:239
#define NMG_V_ASSESSMENT_LONE
Definition: nmg_fcut.c:84
#define HPRINT(a, b)
Definition: raytrace.h:1882
void nmg_plot_lu_ray(const struct loopuse *lu, const struct vertexuse *vu1, const struct vertexuse *vu2, const fastf_t *left)
Definition: nmg_plot.c:2020
void nmg_vlblock_lu(struct bn_vlblock *vbp, const struct loopuse *lu, long *tab, int red, int green, int blue, int fancy)
Definition: nmg_plot.c:1088
goto out
Definition: nmg_mod.c:3846
#define WEDGE2_TO_STRING(_class2)
Definition: nmg_fcut.c:922
struct faceuse * nmg_find_fu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:304
#define NMG_E_ASSESSMENT_ON_FORW
Definition: nmg_fcut.c:80
Support for uniform tolerances.
Definition: tol.h:71
#define BN_CK_TOL(_p)
Definition: tol.h:82
#define BU_LIST_FIRST_MAGIC(hp)
Definition: list.h:416
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
#define NMG_V_ASSESSMENT_PREV(_a)
Definition: nmg_fcut.c:89
fastf_t in_vu_angle
Definition: nmg_fcut.c:780
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
uint32_t magic
Magic # for mem id/check.
Definition: list.h:119
#define ANG_SMASH(_a)
#define NMG_LONE
Definition: nmg_fcut.c:142
int nmg_mesh_two_faces(register struct faceuse *fu1, register struct faceuse *fu2, const struct bn_tol *tol)
Definition: nmg_mesh.c:479
#define NMG_ON_FORW_ON_FORW
Definition: nmg_fcut.c:136
double nmg_vu_angle_measure(struct vertexuse *vu, fastf_t *x_dir, fastf_t *y_dir, int assessment, int in)
Definition: nmg_fcut.c:418
int bu_ptbl_locate(const struct bu_ptbl *b, const long *p)
#define VAVERAGE(a, b, c)
Definition: nmg_fcut.c:1987
void bu_ptbl_free(struct bu_ptbl *b)
Definition: ptbl.c:226
#define WEDGE_CROSS
Definition: nmg_fcut.c:797
fastf_t lo_ang
Definition: nmg_fcut.c:783
#define BU_LIST_PPREV_CIRC(structure, p)
Definition: list.h:450
void nmg_edge_geom_isect_line(struct edgeuse *eu, struct nmg_ray_state *rs, const char *reason)
Definition: nmg_fcut.c:2006
int nmg_is_v_on_rs_list(const struct nmg_ray_state *rs, const struct vertex *v)
Definition: nmg_fcut.c:528
struct nmg_loop_stuff * lsp
Definition: nmg_fcut.c:779
void nmg_unlist_v(struct bu_ptbl *b, fastf_t *mag, struct vertex *v)
Definition: nmg_fcut.c:2931
#define ZERO(val)
Definition: units.c:38
void nmg_jeg(struct edge_g_lseg *dest_eg, struct edge_g_lseg *src_eg)
Definition: nmg_mk.c:3047
int nmg_klu(struct loopuse *lu1)
Definition: nmg_mk.c:1277
#define NMG_ON_REV_RIGHT
Definition: nmg_fcut.c:139
#define WEDGECLASS2STR(_cl)
Definition: nmg_fcut.c:800
#define WEDGE_ON
Definition: nmg_fcut.c:799
#define WEDGE2_TOUCH_AT_BC
Definition: nmg_fcut.c:929
#define BU_PTBL_END(ptbl)
Definition: ptbl.h:106
void nmg_pr_lu(const struct loopuse *lu, char *h)
Definition: nmg_pr.c:405
#define NMG_ACTION_NONE
Definition: nmg_fcut.c:158
int nmg_fu_touchingloops(const struct faceuse *fu)
Definition: nmg_inter.c:6500
#define NMG_V_ASSESSMENT_NEXT(_a)
Definition: nmg_fcut.c:90
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
#define NMG_STATE_ERROR
Definition: nmg_fcut.c:59
struct vertexuse * nmg_join_2loops(struct vertexuse *vu1, struct vertexuse *vu2)
Definition: nmg_mod.c:2043
#define NMG_LEFT_ON_FORW
Definition: nmg_fcut.c:128
#define NMG_ACTION_CUTJOIN
Definition: nmg_fcut.c:164
#define NMG_ACTION_LONE_V_JAUNT
Definition: nmg_fcut.c:163
#define WEDGE2_AB_IN_CD
Definition: nmg_fcut.c:926
#define NMG_E_ASSESSMENT_LEFT
Definition: nmg_fcut.c:78
double bn_angle_measure(vect_t vec, const vect_t x_dir, const vect_t y_dir)
int nmg_ck_vu_ptbl(struct bu_ptbl *p, struct faceuse *fu)
Definition: nmg_fcut.c:345
void nmg_pr_ptbl(const char *title, const struct bu_ptbl *tbl, int verbose)
Definition: nmg_pr.c:776
#define RADIAN_TWEEK
#define NMG_RIGHT_RIGHT
Definition: nmg_fcut.c:131
int nmg_face_state_transition(struct nmg_ray_state *rs, int pos, int multi, int other_rs_state)
Definition: nmg_fcut.c:3365
void nmg_pr_eu(const struct edgeuse *eu, char *h)
Definition: nmg_pr.c:552
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define WEDGE2_TOUCH_AT_DA
Definition: nmg_fcut.c:930
#define NMG_LEFT_ON_REV
Definition: nmg_fcut.c:129
const char * nmg_class_name(int nmg_class)
Definition: nmg_eval.c:122
void nmg_pr_eu_endpoints(const struct edgeuse *eu, char *h)
Definition: nmg_pr.c:600
#define NMG_STATE_ON_L
Definition: nmg_fcut.c:61
void nmg_pr_fu_briefly(const struct faceuse *fu, char *h)
Definition: nmg_pr.c:359
off_t end
Definition: ptbl.h:64
#define NMG_RIGHT_ON_FORW
Definition: nmg_fcut.c:132
#define NMG_ACTION_LONE_V_ESPLIT
Definition: nmg_fcut.c:162
#define WEDGE_RIGHT
Definition: nmg_fcut.c:798
#define NMG_E_ASSESSMENT_ERROR
Definition: nmg_fcut.c:82
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
#define AB_EQUAL
Definition: nmg_fcut.c:1277
#define WEDGE_ANG_TOL
const struct bn_tol * tol
Definition: nmg_fcut.c:195
#define NMG_RIGHT_LEFT
Definition: nmg_fcut.c:130
vect_t left
Definition: nmg_fcut.c:190
struct loopuse * nmg_find_lu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:411
#define NMG_ACTION_ERROR
Definition: nmg_fcut.c:157
Definition: vls.h:56
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double fastf_t
Definition: defines.h:300
#define VPRINT(a, b)
Definition: raytrace.h:1881
const char * bu_identify_magic(uint32_t magic)
char * nmg_orientation(int orientation)
Definition: nmg_pr.c:50
void nmg_vfu(const struct bu_list *hp, const struct shell *s)
Definition: nmg_ck.c:488
#define BU_LIST_NOT_HEAD(p, hp)
Definition: list.h:324
uint32_t magic
Definition: nmg_fcut.c:180
void nmg_loop_g(struct loop *l, const struct bn_tol *tol)
Definition: nmg_mk.c:2152
void rt_plot_vlblock(FILE *fp, const struct bn_vlblock *vbp)
Definition: vlist.c:427
HIDDEN void nmg_fcut_face(struct nmg_ray_state *rs)
Definition: nmg_fcut.c:2576
#define NMG_V_COMB(_p, _n)
Definition: nmg_fcut.c:86
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
struct vertexuse * min_vu
Definition: nmg_fcut.c:791
struct edge_g_lseg * nmg_face_cutjoin(struct bu_ptbl *b1, struct bu_ptbl *b2, fastf_t *mag1, fastf_t *mag2, struct faceuse *fu1, struct faceuse *fu2, fastf_t *pt, fastf_t *dir, struct edge_g_lseg *eg, const struct bn_tol *tol)
Definition: nmg_fcut.c:3059
void nmg_sanitize_fu(struct faceuse *fu)
Definition: nmg_fcut.c:1860
#define NMG_ACTION_VFY_MULTI
Definition: nmg_fcut.c:161
struct rt_g RTG
Definition: globals.c:39
struct model * nmg_find_model(const uint32_t *magic_p_arg)
Definition: nmg_info.c:57