BRL-CAD
nmg_rt_isect.c
Go to the documentation of this file.
1 /* N M G _ R T _ I S E C T . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1994-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @addtogroup nmg */
21 /** @{ */
22 /** @file primitives/nmg/nmg_rt_isect.c
23  *
24  * Support routines for raytracing an NMG.
25  *
26  */
27 /** @} */
28 
29 #include "common.h"
30 
31 #include <stdlib.h>
32 #include <string.h>
33 #include <math.h>
34 #include "bio.h"
35 
36 #include "vmath.h"
37 #include "nmg.h"
38 #include "raytrace.h"
39 #include "nurb.h"
40 #include "plot3.h"
41 
42 
43 /* Plot a faceuse and a line between pt and plane_pt */
44 static int plot_file_number=0;
45 
46 
47 const char *
49 {
50  switch (code) {
51  case HMG_HIT_IN_IN:
52  return "IN_IN";
53  case HMG_HIT_IN_OUT:
54  return "IN_OUT";
55  case HMG_HIT_OUT_IN:
56  return "OUT_IN";
57  case HMG_HIT_OUT_OUT:
58  return "OUT_OUT";
59  case HMG_HIT_IN_ON:
60  return "IN_ON";
61  case HMG_HIT_ON_IN:
62  return "ON_IN";
63  case HMG_HIT_OUT_ON:
64  return "OUT_ON";
65  case HMG_HIT_ON_OUT:
66  return "ON_OUT";
67  case HMG_HIT_ANY_ANY:
68  return "ANY_ANY";
69  }
70  return "?_?\n";
71 }
72 
73 
74 const char *
76 {
77  switch (code) {
79  return "RS_INSIDE";
80  case NMG_RAY_STATE_ON:
81  return "RS_ON";
83  return "RS_OUTSIDE";
84  case NMG_RAY_STATE_ANY:
85  return "RS_ANY";
86  }
87  return "RS_UNKNOWN";
88 }
89 
90 
91 /**
92  * Ensure that the ray makes a valid set of state transitions.
93  */
94 void
95 nmg_ck_hitmiss_list(const struct bu_list *hd)
96 {
97  struct hitmiss *hmp;
98  int state = NMG_RAY_STATE_OUTSIDE;
99  int istate;
100  int ostate;
101 
102  for (BU_LIST_FOR(hmp, hitmiss, hd)) {
103  NMG_CK_HITMISS(hmp);
104 
105  /* Skip hits on non-3-manifolds */
106  if (hmp->in_out == HMG_HIT_ANY_ANY) continue;
107 
108  istate = HMG_INBOUND_STATE(hmp);
109  ostate = HMG_OUTBOUND_STATE(hmp);
110  if (state != istate) {
111  bu_log("ray state was=%s, transition=%s (istate=%s)\n",
112  nmg_rt_state_str(state),
113  nmg_rt_inout_str(hmp->in_out),
114  nmg_rt_state_str(istate));
115  bu_bomb("nmg_ck_hitmiss_list() NMG ray-tracer bad in/out state transition\n");
116  }
117  state = ostate;
118  }
119  if (state != NMG_RAY_STATE_OUTSIDE) {
120  bu_log("ray ending state was %s, should have been RS_OUT\n", nmg_rt_state_str(state));
121  bu_bomb("nmg_ck_hitmiss_list() NMG ray-tracer bad ending state\n");
122  }
123 }
124 
125 
126 HIDDEN void
127 nmg_rt_isect_plfu(struct faceuse *fu, fastf_t *pt, fastf_t *plane_pt)
128 {
129  FILE *fp;
130  char name[25];
131  long *b;
132 
133  NMG_CK_FACEUSE(fu);
134 
135  sprintf(name, "ray%02d.plot3", plot_file_number++);
136  fp=fopen(name, "wb");
137  if (fp == (FILE *)NULL) {
138  perror(name);
139  bu_bomb("unable to open file for writing");
140  }
141 
142  bu_log("overlay %s\n", name);
143  b = (long *)bu_calloc(fu->s_p->r_p->m_p->maxindex,
144  sizeof(long), "bit vec"),
145 
146  pl_erase(fp);
147  pd_3space(fp,
148  fu->f_p->min_pt[0]-1.0,
149  fu->f_p->min_pt[1]-1.0,
150  fu->f_p->min_pt[2]-1.0,
151  fu->f_p->max_pt[0]+1.0,
152  fu->f_p->max_pt[1]+1.0,
153  fu->f_p->max_pt[2]+1.0);
154 
155  nmg_pl_fu(fp, fu, b, 255, 255, 255);
156 
157  pl_color(fp, 255, 50, 50);
158  pdv_3line(fp, pt, plane_pt);
159 
160  bu_free((char *)b, "bit vec");
161  fclose(fp);
162 }
163 
164 
165 HIDDEN void
166 pleu(struct edgeuse *eu, fastf_t *pt, fastf_t *plane_pt)
167 {
168  FILE *fp;
169  char name[25];
170  long *b;
171  point_t min_pt, max_pt;
172  int i;
173  struct model *m;
174 
175  sprintf(name, "ray%02d.plot3", plot_file_number++);
176  fp=fopen(name, "wb");
177  if (fp == (FILE *)NULL) {
178  perror(name);
179  bu_bomb("unable to open file for writing");
180  }
181 
182  bu_log("overlay %s\n", name);
183  m = nmg_find_model(eu->up.magic_p);
184  b = (long *)bu_calloc(m->maxindex, sizeof(long), "bit vec");
185 
186  pl_erase(fp);
187 
188  VMOVE(min_pt, eu->vu_p->v_p->vg_p->coord);
189 
190  for (i=0; i < 3; i++) {
191  if (eu->eumate_p->vu_p->v_p->vg_p->coord[i] < min_pt[i]) {
192  max_pt[i] = min_pt[i];
193  min_pt[i] = eu->eumate_p->vu_p->v_p->vg_p->coord[i];
194  } else {
195  max_pt[i] = eu->eumate_p->vu_p->v_p->vg_p->coord[i];
196  }
197  }
198  pd_3space(fp,
199  min_pt[0]-1.0, min_pt[1]-1.0, min_pt[2]-1.0,
200  max_pt[0]+1.0, max_pt[1]+1.0, max_pt[2]+1.0);
201 
202  nmg_pl_eu(fp, eu, b, 255, 255, 255);
203  pl_color(fp, 255, 50, 50);
204  pdv_3line(fp, pt, plane_pt);
205  bu_free((char *)b, "bit vec");
206  fclose(fp);
207 }
208 
209 
210 void
212 {
213  NMG_CK_HITMISS(a_hit);
214 
215  bu_log(" dist:%12g pt=(%f %f %f) %s=%p\n",
216  a_hit->hit.hit_dist,
217  a_hit->hit.hit_point[0],
218  a_hit->hit.hit_point[1],
219  a_hit->hit.hit_point[2],
220  bu_identify_magic(*(uint32_t *)a_hit->hit.hit_private),
221  (void *)a_hit->hit.hit_private
222  );
223  bu_log("\tstate:%s", nmg_rt_inout_str(a_hit->in_out));
224 
225  switch (a_hit->start_stop) {
226  case NMG_HITMISS_SEG_IN: bu_log(" SEG_START"); break;
227  case NMG_HITMISS_SEG_OUT: bu_log(" SEG_STOP"); break;
228  }
229 
230  VPRINT("\n\tin_normal", a_hit->inbound_norm);
231  VPRINT("\tout_normal", a_hit->outbound_norm);
232 }
233 void
235 {
236  struct hitmiss *a_hit;
237 
238  bu_log("nmg/ray hit list:\n");
239 
240  for (BU_LIST_FOR(a_hit, hitmiss, hd)) {
241  nmg_rt_print_hitmiss(a_hit);
242  }
243 }
244 
245 
246 /**
247  * insert the new hit point in the correct place in the list of hits
248  * so that the list is always in sorted order
249  */
250 HIDDEN void
251 hit_ins(struct ray_data *rd, struct hitmiss *newhit)
252 {
253  struct hitmiss *a_hit;
254 
256  newhit->hit.hit_magic = RT_HIT_MAGIC;
257 
258  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
259  bu_log("hit_ins()\n inserting:");
260  nmg_rt_print_hitmiss(newhit);
261  }
262 
263  for (BU_LIST_FOR(a_hit, hitmiss, &rd->rd_hit)) {
264  if (newhit->hit.hit_dist < a_hit->hit.hit_dist)
265  break;
266  }
267 
268  /* a_hit now points to the item before which we should insert this
269  * hit in the hit list.
270  */
271 
272  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
273  if (BU_LIST_NOT_HEAD(a_hit, &rd->rd_hit)) {
274  bu_log(" prior to:");
275  nmg_rt_print_hitmiss(a_hit);
276  } else {
277  bu_log("\tat end of list\n");
278  }
279  }
280 
281  BU_LIST_INSERT(&a_hit->l, &newhit->l);
282 
283  if (RTG.NMG_debug & DEBUG_RT_ISECT)
285 
286 }
287 
288 
289 /**
290  * The ray missed this vertex. Build the appropriate miss structure.
291  */
292 HIDDEN struct hitmiss *
293 ray_miss_vertex(struct ray_data *rd, struct vertexuse *vu_p)
294 {
295  struct hitmiss *myhit;
296 
297  NMG_CK_VERTEXUSE(vu_p);
298  NMG_CK_VERTEX(vu_p->v_p);
299  NMG_CK_VERTEX_G(vu_p->v_p->vg_p);
300 
301  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
302  bu_log("ray_miss_vertex(%g %g %g)\n",
303  vu_p->v_p->vg_p->coord[0],
304  vu_p->v_p->vg_p->coord[1],
305  vu_p->v_p->vg_p->coord[2]);
306  }
307 
308  myhit=NMG_INDEX_GET(rd->hitmiss, vu_p->v_p);
309  if (myhit) {
310  /* vertex previously processed */
311  if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit, NMG_RT_HIT_MAGIC)) {
312  if (RTG.NMG_debug & DEBUG_RT_ISECT)
313  bu_log("ray_miss_vertex(vertex previously HIT!!!!)\n");
314  } else if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit, NMG_RT_HIT_SUB_MAGIC)) {
315  if (RTG.NMG_debug & DEBUG_RT_ISECT)
316  bu_log("ray_miss_vertex(vertex previously HIT_SUB!?!?)\n");
317  }
318  return myhit;
319  }
320  myhit=NMG_INDEX_GET(rd->hitmiss, vu_p->v_p);
321  if (myhit) {
322  if (RTG.NMG_debug & DEBUG_RT_ISECT)
323  bu_log("ray_miss_vertex(vertex previously missed)\n");
324  return myhit;
325  }
326 
327  NMG_GET_HITMISS(myhit, rd->ap);
328  NMG_INDEX_ASSIGN(rd->hitmiss, vu_p->v_p, myhit);
329  myhit->outbound_use = (long *)vu_p;
330  myhit->inbound_use = (long *)vu_p;
331  myhit->hit.hit_private = (void *)vu_p->v_p;
332 
333  /* get build_vertex_miss() to compute this */
334  myhit->dist_in_plane = -1.0;
335 
336  /* add myhit to the list of misses */
338  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
339 
340  return myhit;
341 }
342 
343 
344 /**
345  * Support routine for vertex_neighborhood()
346  */
347 HIDDEN void
348 get_pole_dist_to_face(struct ray_data *rd, struct vertexuse *vu, fastf_t *Pole, fastf_t *Pole_prj_pt, double *Pole_dist, fastf_t *Pole_pca, fastf_t *pointA, fastf_t *leftA, fastf_t *pointB, fastf_t *leftB, fastf_t *polar_height_vect, char *Pole_name)
349 {
350  vect_t pca_to_pole_vect;
351  vect_t VtoPole_prj;
352  point_t pcaA, pcaB;
353  fastf_t distA, distB;
354  int code, status;
355 
356  VSETALL(pca_to_pole_vect, 0);
357 
358  /* find the points of closest approach
359  * There are six distinct return values from bn_dist_pt3_lseg3():
360  *
361  * Value Condition
362  * -----------------------------------------------------------------
363  * 0 P is within tolerance of lseg AB. *dist isn't 0: (SPECIAL!!!)
364  * *dist = parametric dist = |PCA-A| / |B-A|. pca=computed.
365  * 1 P is within tolerance of point A. *dist = 0, pca=A.
366  * 2 P is within tolerance of point B. *dist = 0, pca=B.
367  *
368  * 3 P is to the "left" of point A. *dist=|P-A|, pca=A.
369  * 4 P is to the "right" of point B. *dist=|P-B|, pca=B.
370  * 5 P is "above/below" lseg AB. *dist=|PCA-P|, pca=computed.
371  */
372  code = bn_dist_pt3_lseg3(&distA, pcaA, vu->v_p->vg_p->coord, pointA,
373  Pole_prj_pt, rd->tol);
374  if (code < 3) {
375  /* Point is on line */
376  *Pole_dist = MAGNITUDE(polar_height_vect);
377  VMOVE(Pole_pca, Pole_prj_pt);
378  return;
379  }
380 
381  status = code << 4;
382  code = bn_dist_pt3_lseg3(&distB, pcaB, vu->v_p->vg_p->coord, pointB,
383  Pole_prj_pt, rd->tol);
384  if (code < 3) {
385  /* Point is on line */
386  *Pole_dist = MAGNITUDE(polar_height_vect);
387  VMOVE(Pole_pca, Pole_prj_pt);
388  return;
389  }
390 
391  status |= code;
392 
393  /* Status
394  * codeA CodeB
395  * 3 3 Do the Tanenbaum patch thing
396  * 3 4 This should not happen.
397  * 3 5 compute dist from pole to pcaB
398  * 4 3 This should not happen.
399  * 4 4 This should not happen.
400  * 4 5 This should not happen.
401  * 5 3 compute dist from pole to pcaA
402  * 5 4 This should not happen.
403  * 5 5 pick the edge with smallest "dist"
404  * and compute pole-pca distance.
405  */
406  if (RTG.NMG_debug & DEBUG_RT_ISECT)
407  bu_log("get_pole_dist_to_face(%s) status from dist_pt_lseg == 0x%02x\n", Pole_name, status);
408 
409  switch (status) {
410  case 0x35: /* compute dist from pole to pcaB */
411 
412  /* if plane point is "inside" edge B, plane point is PCA */
413  VSUB2(VtoPole_prj, Pole_prj_pt, vu->v_p->vg_p->coord);
414  if (VDOT(leftB, VtoPole_prj) > -SMALL_FASTF) {
415  /* plane point is "inside" edge B */
416  if (RTG.NMG_debug & DEBUG_RT_ISECT)
417  bu_log("\tplane point inside face\n");
418  VMOVE(Pole_pca, Pole_prj_pt);
419  VSUB2(pca_to_pole_vect, Pole_prj_pt, Pole);
420  *Pole_dist = MAGNITUDE(pca_to_pole_vect);
421  return;
422  }
423 
424  if (RTG.NMG_debug & DEBUG_RT_ISECT)
425  bu_log("\tplane point outside face\n");
426  VSUB2(pca_to_pole_vect, pcaB, Pole);
427  VMOVE(Pole_pca, pcaB);
428  break;
429  case 0x53: /* compute dist from pole to pcaA */
430 
431  /* if plane point is "inside" edge A, plane point is PCA */
432  VSUB2(VtoPole_prj, Pole_prj_pt, vu->v_p->vg_p->coord);
433  if (VDOT(leftA, VtoPole_prj) > -SMALL_FASTF) {
434  /* plane point is "inside" edge A */
435  if (RTG.NMG_debug & DEBUG_RT_ISECT)
436  bu_log("\tplane point inside face\n");
437  VMOVE(Pole_pca, Pole_prj_pt);
438  VSUB2(pca_to_pole_vect, Pole_prj_pt, Pole);
439  *Pole_dist = MAGNITUDE(pca_to_pole_vect);
440  return;
441  }
442 
443  if (RTG.NMG_debug & DEBUG_RT_ISECT)
444  bu_log("\tplane point outside face\n");
445  VSUB2(pca_to_pole_vect, pcaA, Pole);
446  VMOVE(Pole_pca, pcaA);
447  break;
448  case 0x55:/* pick the edge with smallest "dist"
449  * and compute pole-pca distance.
450  */
451  VSUB2(VtoPole_prj, Pole_prj_pt, vu->v_p->vg_p->coord);
452 
453  if (distA < distB) {
454  VUNITIZE(VtoPole_prj);
455  VUNITIZE(leftA);
456  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
457  VPRINT("LeftA", leftA);
458  VPRINT("VtoPole_prj", VtoPole_prj);
459  }
460 
461  if (VDOT(leftA, VtoPole_prj) > -SMALL_FASTF) {
462  /* plane point is "inside" edge A */
463  if (RTG.NMG_debug & DEBUG_RT_ISECT)
464  bu_log("\tplane point inside face\n");
465  VSUB2(pca_to_pole_vect, Pole_prj_pt, Pole);
466  *Pole_dist = MAGNITUDE(pca_to_pole_vect);
467  VMOVE(Pole_pca, Pole_prj_pt);
468  return;
469  }
470  if (RTG.NMG_debug & DEBUG_RT_ISECT)
471  bu_log("\tplane point outside face\n");
472  VSUB2(pca_to_pole_vect, pcaA, Pole);
473  VMOVE(Pole_pca, pcaA);
474  } else {
475  VUNITIZE(VtoPole_prj);
476  VUNITIZE(leftB);
477  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
478  VPRINT("LeftB", leftB);
479  VPRINT("VtoPole_prj", VtoPole_prj);
480  }
481  if (VDOT(leftB, VtoPole_prj) > -SMALL_FASTF) {
482  /* plane point is "inside" edge B */
483  if (RTG.NMG_debug & DEBUG_RT_ISECT)
484  bu_log("\tplane point inside face\n");
485  VMOVE(Pole_pca, Pole_prj_pt);
486  VSUB2(pca_to_pole_vect, Pole_prj_pt, Pole);
487  *Pole_dist = MAGNITUDE(pca_to_pole_vect);
488  return;
489  }
490  if (RTG.NMG_debug & DEBUG_RT_ISECT)
491  bu_log("\tplane point outside face\n");
492  VSUB2(pca_to_pole_vect, pcaB, Pole);
493  VMOVE(Pole_pca, pcaB);
494  }
495  break;
496  case 0x33: {
497  /* The point is over the vertex shared by the points, and
498  * not over one edge or the other. We now need to figure
499  * out which edge to classify this point against.
500  *
501  * Time to do the Tanenbaum algorithm.
502  */
503  double dotA;
504  double dotB;
505 
506  if (RTG.NMG_debug & DEBUG_RT_ISECT)
507  bu_log("\tplane point beyond both edges.... Doing the Tanenbaum algorithm.\n");
508 
509  VSUB2(VtoPole_prj, Pole_prj_pt, vu->v_p->vg_p->coord);
510 
511  dotA = VDOT(leftA, VtoPole_prj);
512  dotB = VDOT(leftB, VtoPole_prj);
513 
514  if (dotA < dotB) {
515  if (dotA > -SMALL_FASTF) {
516  /* Point is "inside" face,
517  * PCA is plane projection point.
518  */
519  if (RTG.NMG_debug & DEBUG_RT_ISECT)
520  bu_log("\tpoint inside face\n");
521  VMOVE(Pole_pca, Pole_prj_pt);
522  VSUB2(pca_to_pole_vect, Pole, Pole_prj_pt);
523  } else {
524  /* Point is "outside" face, PCA is at vertex. */
525  if (RTG.NMG_debug & DEBUG_RT_ISECT)
526  bu_log("\tpoint outside face, PCA is vertex\n");
527 
528  VSUB2(pca_to_pole_vect, pcaA, Pole);
529  VMOVE(Pole_pca, pcaA);
530  }
531  } else {
532  if (dotB > -SMALL_FASTF) {
533  /* Point is "inside" face,
534  * PCA is plane projection point
535  */
536  if (RTG.NMG_debug & DEBUG_RT_ISECT)
537  bu_log("\tpoint is inside face\n");
538  VMOVE(Pole_pca, Pole_prj_pt);
539  VSUB2(pca_to_pole_vect, Pole, Pole_prj_pt);
540  } else {
541 
542  /* Point is "outside" face, PCA is at vertex. */
543  if (RTG.NMG_debug & DEBUG_RT_ISECT)
544  bu_log("\tpoint is outside face, PCA is vertex\n");
545  VSUB2(pca_to_pole_vect, pcaB, Pole);
546  VMOVE(Pole_pca, pcaB);
547  }
548  }
549  if (RTG.NMG_debug & DEBUG_RT_ISECT)
550  VPRINT("\tpca_to_pole_vect", pca_to_pole_vect);
551  *Pole_dist = MAGNITUDE(pca_to_pole_vect);
552  return;
553  }
554  case 0x34: /* fallthrough */
555  case 0x54: /* fallthrough */
556  case 0x43: /* fallthrough */
557  case 0x44: /* fallthrough */
558  case 0x45: /* fallthrough */
559  default:
560  bu_log("%s %d: So-called 'Impossible' status codes\n",
561  __FILE__, __LINE__);
562  bu_bomb("get_pole_dist_to_face() Pretending NOT to bomb\n");
563  break;
564  }
565 
566  *Pole_dist = MAGNITUDE(pca_to_pole_vect);
567 
568  return;
569 }
570 
571 
572 HIDDEN void
573 plot_neighborhood(fastf_t *North_Pole, fastf_t *North_pl_pt, fastf_t *North_pca, fastf_t *South_Pole, fastf_t *South_pl_pt, fastf_t *South_pca, fastf_t *pointA, fastf_t *pointB, fastf_t *norm, fastf_t *pt, fastf_t *leftA, fastf_t *leftB)
574 {
575  static int plotnum=0;
576  FILE *pfp;
577  char name[64];
578  point_t my_pt;
579  vect_t ray;
580 
581  sprintf(name, "vert%03d.plot3", plotnum++);
582  pfp=fopen(name, "wb");
583  if (pfp == (FILE *)NULL) {
584  bu_log("Error opening %s\n", name);
585  return;
586  } else
587  bu_log("overlay %s\n", name);
588 
589 
590  /* draw the ray */
591  pl_color(pfp, 255, 55, 55);
592  pdv_3line(pfp, North_Pole, South_Pole);
593 
594  /* draw the area of the face */
595  pl_color(pfp, 55, 255, 55);
596  pdv_3move(pfp, pt);
597  pdv_3cont(pfp, pointA);
598  pdv_3cont(pfp, pointB);
599  pdv_3cont(pfp, pt);
600 
601  /* draw the projections of the pole points */
602  pl_color(pfp, 255, 255, 55);
603  pdv_3line(pfp, North_Pole, North_pl_pt);
604  if (! VEQUAL(North_pca, North_pl_pt)) {
605  pdv_3line(pfp, North_Pole, North_pca);
606  pdv_3line(pfp, North_pl_pt, North_pca);
607  }
608  VSUB2(ray, South_Pole, North_Pole);
609  VSCALE(ray, ray, -0.125);
610  VADD2(my_pt, North_Pole, ray);
611  pdv_3move(pfp, my_pt);
612  pl_label(pfp, "N");
613 
614  pl_color(pfp, 55, 255, 255);
615  pdv_3line(pfp, South_Pole, South_pl_pt);
616  if (! VEQUAL(South_pca, South_pl_pt)) {
617  pdv_3line(pfp, South_Pole, South_pca);
618  pdv_3line(pfp, South_pl_pt, South_pca);
619  }
620  VREVERSE(ray, ray);
621  VADD2(my_pt, South_Pole, ray);
622  pdv_3move(pfp, my_pt);
623  pl_label(pfp, "S");
624 
625  pl_color(pfp, 128, 128, 128);
626  VADD2(my_pt, pt, norm);
627  pdv_3line(pfp, pt, my_pt);
628 
629  pl_color(pfp, 192, 192, 192);
630  VADD2(my_pt, pointA, leftA);
631  pdv_3line(pfp, pointA, my_pt);
632 
633  VADD2(my_pt, pointB, leftB);
634  pdv_3line(pfp, pointB, my_pt);
635 
636  fclose(pfp);
637 }
638 
639 
640 /**
641  * Examine the vertex neighborhood to classify the ray as IN/ON/OUT of
642  * the NMG both before and after hitting the vertex.
643  *
644  *
645  * There is a conceptual sphere about the vertex. For reasons
646  * associated with tolerancing, the sphere has a radius equal to the
647  * magnitude of the maximum dimension of the NMG bounding RPP.
648  *
649  * The point where the ray enters this sphere is called the "North
650  * Pole" and the point where it exits the sphere is called the "South
651  * Pole"
652  *
653  * For each face which uses this vertex we compute 2 "distance"
654  * metrics:
655  *
656  * project the "north pole" and "south pole" down onto the plane of
657  * the face:
658  *
659  *
660  *
661  * /
662  * /
663  * /North Pole
664  * / |
665  * Face Normal ^ / |
666  * | / | Projection of North Pole
667  * Plane of face |/ V to plane
668  * ---------------------------------*-------------------------------
669  * Projection of ^ / Vertex
670  * South Pole | /
671  * to plane | /
672  * |/
673  * /South Pole
674  * /
675  * /
676  * /
677  * /
678  * /
679  * /
680  * |/_
681  * Ray
682  *
683  * If the projected polar point is inside the two edgeuses at this
684  * vertexuse, then
685  * the distance to the face is the projection distance.
686  *
687  * else
688  * Each of the two edgeuses at this vertexuse
689  * implies an infinite ray originating at the vertex.
690  * Find the point of closest approach (PCA) of each ray
691  * to the projection point. For whichever ray passes
692  * closer to the projection point, find the distance
693  * from the original pole point to the PCA. This is
694  * the "distance to the face" metric for this face from
695  * the given pole point.
696  *
697  * We compute this metric for the North and South poles for all faces
698  * at the vertex. The face with the smallest distance to the north
699  * (south) pole is used to determine the state of the ray before
700  * (after) it hits the vertex.
701  *
702  * If the north (south) pole is "outside" the plane of the closest
703  * face, then the ray state is "outside" before (after) the ray hits
704  * the vertex.
705  */
706 HIDDEN void
707 vertex_neighborhood(struct ray_data *rd, struct vertexuse *vu_p, struct hitmiss *myhit)
708 {
709  struct vertexuse *vu;
710  struct faceuse *fu;
711  point_t South_Pole, North_Pole;
712  struct faceuse *North_fu = (struct faceuse *)NULL;
713  struct faceuse *South_fu = (struct faceuse *)NULL;
714  struct vertexuse *North_vu = (struct vertexuse *)NULL;
715  struct vertexuse *South_vu = (struct vertexuse *)NULL;
716  point_t North_pl_pt, South_pl_pt;
717  point_t North_pca, South_pca;
718  double North_dist, South_dist;
719  double North_min, South_min;
720  double cos_angle;
721  vect_t VtoPole;
722  double scalar_dist;
723  double dimen, t;
724  point_t min_pt, max_pt;
725  int i;
726  vect_t norm, anti_norm;
727  vect_t polar_height_vect;
728  vect_t leftA, leftB;
729  point_t pointA, pointB;
730  struct edgeuse *eu;
731  vect_t edge_vect;
732  int found_faces;
733  vect_t r_dir_unit;
734 
735  NMG_CK_VERTEXUSE(vu_p);
736  NMG_CK_VERTEX(vu_p->v_p);
737  NMG_CK_VERTEX_G(vu_p->v_p->vg_p);
738 
739  if (RTG.NMG_debug & DEBUG_RT_ISECT)
740  bu_log("vertex_neighborhood\n");
741 
742  nmg_model_bb(min_pt, max_pt, nmg_find_model(vu_p->up.magic_p));
743  for (dimen= -MAX_FASTF, i=3; i--;) {
744  t = max_pt[i]-min_pt[i];
745  if (t > dimen) dimen = t;
746  }
747 
748  VMOVE(r_dir_unit, rd->rp->r_dir);
749  VUNITIZE(r_dir_unit);
750  VJOIN1(North_Pole, vu_p->v_p->vg_p->coord, -dimen, r_dir_unit);
751  VJOIN1(South_Pole, vu_p->v_p->vg_p->coord, dimen, r_dir_unit);
752 
753  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
754  VPRINT("\tNorth Pole", North_Pole);
755  VPRINT("\tSouth Pole", South_Pole);
756  }
757 
758  /* There is a conceptual sphere around the vertex. The max
759  * dimension of the bounding box for the NMG defines the size.
760  * The point where the ray enters this sphere is called the North
761  * Pole, and the point where it exits is called the South Pole.
762  */
763 
764  South_min = North_min = MAX_FASTF;
765  found_faces = 0;
766  myhit->in_out = 0;
767 
768  /* for every use of this vertex */
769  for (BU_LIST_FOR(vu, vertexuse, &vu_p->v_p->vu_hd)) {
770  /* if the parent use is an (edge/loop)use of an OT_SAME
771  * faceuse that we haven't already processed...
772  */
773  NMG_CK_VERTEXUSE(vu);
774  NMG_CK_VERTEX(vu->v_p);
775  NMG_CK_VERTEX_G(vu->v_p->vg_p);
776 
777  fu = nmg_find_fu_of_vu(vu);
778  if (fu) {
779  found_faces = 1;
780  if (*vu->up.magic_p == NMG_EDGEUSE_MAGIC &&
781  fu->orientation == OT_SAME) {
782 
783  /* The distance from each "Pole Point" to the faceuse
784  * is the commodity in which we are interested.
785  *
786  * A pole point is projected. This is either the
787  * distance to the plane (if the projection of the
788  * point into the plane lies within the angle of the
789  * two edgeuses at this vertex) or we take the
790  * distance from the pole to the PCA of the closest
791  * edge.
792  */
793  NMG_GET_FU_NORMAL(norm, fu);
794  VREVERSE(anti_norm, norm);
795 
796  if (RTG.NMG_debug & DEBUG_RT_ISECT)
797  VPRINT("\tchecking face", norm);
798 
799  /* project the north pole onto the plane */
800  VSUB2(polar_height_vect, vu->v_p->vg_p->coord, North_Pole);
801  scalar_dist = VDOT(norm, polar_height_vect);
802 
803  /* project the poles down onto the plane */
804  VJOIN1(North_pl_pt, North_Pole, scalar_dist, norm);
805  VJOIN1(South_pl_pt, South_Pole, scalar_dist, anti_norm);
806  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
807  VPRINT("\tNorth Plane Point", North_pl_pt);
808  VPRINT("\tSouth Plane Point", South_pl_pt);
809  }
810  /* Find points on sphere in direction of edges
811  * (away from vertex along edge)
812  */
813  eu = vu->up.eu_p;
814  do {
815  eu = BU_LIST_PNEXT_CIRC(edgeuse, eu);
816  } while ((eu->vu_p->v_p == vu->v_p) && (eu != vu->up.eu_p));
817  nmg_find_eu_leftvec(leftA, vu->up.eu_p);
818  VSUB2(edge_vect, eu->vu_p->v_p->vg_p->coord, vu->v_p->vg_p->coord);
819  VUNITIZE(edge_vect);
820  VJOIN1(pointA, vu->v_p->vg_p->coord, dimen, edge_vect);
821 
822  eu = vu->up.eu_p;
823  do {
824  eu = BU_LIST_PPREV_CIRC(edgeuse, eu);
825  } while ((eu->vu_p->v_p == vu->v_p) && (eu != vu->up.eu_p));
826 
827  nmg_find_eu_leftvec(leftB, eu);
828  VSUB2(edge_vect, eu->vu_p->v_p->vg_p->coord, vu->v_p->vg_p->coord);
829  VUNITIZE(edge_vect);
830  VJOIN1(pointB, vu->v_p->vg_p->coord, dimen, edge_vect);
831 
832 
833  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
834  VPRINT("\tLeftA", leftA);
835  VPRINT("\tLeftB", leftB);
836  }
837  /* find distance of face to North Pole */
838  get_pole_dist_to_face(rd, vu,
839  North_Pole, North_pl_pt, &North_dist, North_pca,
840  pointA, leftA, pointB, leftB,
841  polar_height_vect, "North");
842 
843  if (RTG.NMG_debug & DEBUG_RT_ISECT)
844  bu_log("\tDist north pole<=>face %g\n", North_dist);
845 
846  if (North_min > North_dist) {
847  North_min = North_dist;
848  North_fu = fu;
849  North_vu = vu;
850  if (RTG.NMG_debug & DEBUG_RT_ISECT)
851  bu_log("New North Pole Min: %g\n", North_min);
852  }
853 
854 
855  /* find distance of face to South Pole */
856  get_pole_dist_to_face(rd, vu,
857  South_Pole, South_pl_pt, &South_dist, South_pca,
858  pointA, leftA, pointB, leftB,
859  polar_height_vect, "South");
860 
861  if (RTG.NMG_debug & DEBUG_RT_ISECT)
862  bu_log("\tDist south pole<=>face %g\n", South_dist);
863 
864  if (South_min > South_dist) {
865  South_min = South_dist;
866  South_fu = fu;
867  South_vu = vu;
868  if (RTG.NMG_debug & DEBUG_RT_ISECT)
869  bu_log("New South Pole Min: %g\n", South_min);
870  }
871 
872 
873  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
874  plot_neighborhood(North_Pole, North_pl_pt, North_pca,
875  South_Pole, South_pl_pt, South_pca,
876  pointA, pointB, norm,
877  vu_p->v_p->vg_p->coord,
878  leftA, leftB);
879  }
880  }
881  } else {
882  if (!found_faces)
883  South_vu = North_vu = vu;
884  }
885  }
886 
887  if (!found_faces) {
888  /* we've found a vertex floating in space */
889  myhit->outbound_use = myhit->inbound_use = (long *)North_vu;
890  myhit->in_out = HMG_HIT_ANY_ANY;
891  VREVERSE(myhit->hit.hit_normal, r_dir_unit);
892  return;
893  }
894 
895 
896  NMG_GET_FU_NORMAL(norm, North_fu);
897  VMOVE(myhit->inbound_norm, norm);
898  if (RTG.NMG_debug & DEBUG_RT_ISECT)
899  bu_log("North Pole Min: %g to %g %g %g\n", North_min,
900  norm[0], norm[1], norm[2]);
901 
902  /* compute status of ray as it is in-bound on the vertex */
903  VSUB2(VtoPole, North_Pole, vu_p->v_p->vg_p->coord);
904  cos_angle = VDOT(norm, VtoPole);
905  if (BN_VECT_ARE_PERP(cos_angle, rd->tol))
906  myhit->in_out |= NMG_RAY_STATE_ON << 4;
907  else if (cos_angle > SMALL_FASTF)
908  myhit->in_out |= NMG_RAY_STATE_OUTSIDE << 4;
909  else
910  myhit->in_out |= NMG_RAY_STATE_INSIDE << 4;
911 
912 
913  /* compute status of ray as it is out-bound from the vertex */
914  NMG_GET_FU_NORMAL(norm, South_fu);
915  VMOVE(myhit->outbound_norm, norm);
916  VSUB2(VtoPole, South_Pole, vu_p->v_p->vg_p->coord);
917  cos_angle = VDOT(norm, VtoPole);
918  if (BN_VECT_ARE_PERP(cos_angle, rd->tol))
919  myhit->in_out |= NMG_RAY_STATE_ON;
920  else if (cos_angle > SMALL_FASTF)
921  myhit->in_out |= NMG_RAY_STATE_OUTSIDE;
922  else
923  myhit->in_out |= NMG_RAY_STATE_INSIDE;
924 
925 
926  myhit->inbound_use = (long *)North_vu;
927  myhit->outbound_use = (long *)South_vu;
928 
929  switch (myhit->in_out) {
930  case HMG_HIT_ON_ON: /* fallthrough??? -MJM??? */
931  case HMG_HIT_IN_IN: /* fallthrough */
932  case HMG_HIT_OUT_OUT: /* fallthrough */
933  case HMG_HIT_IN_ON: /* fallthrough */
934  case HMG_HIT_ON_IN: /* two hits */
935  myhit->hit.hit_private = (void *)North_vu;
936  break;
937  case HMG_HIT_IN_OUT: /* one hit - outbound */
938  case HMG_HIT_ON_OUT: /* one hit - outbound */
939  myhit->hit.hit_private = (void *)South_vu;
940  break;
941  case HMG_HIT_OUT_IN: /* one hit - inbound */
942  case HMG_HIT_OUT_ON: /* one hit - inbound */
943  myhit->hit.hit_private = (void *)North_vu;
944  break;
945  default:
946  bu_log("%s %d: vertex_neighborhood() Bad vertex in_out state = %d\n",
947  __FILE__, __LINE__, myhit->in_out);
948  bu_bomb("vertex_neighborhood() bad vertex in_out state\n");
949  break;
950 
951  }
952 }
953 
954 
955 /**
956  * Once it has been decided that the ray hits the vertex, this routine
957  * takes care of recording that fact.
958  */
959 HIDDEN void
960 ray_hit_vertex(struct ray_data *rd, struct vertexuse *vu_p, int status)
961 {
962  struct hitmiss *myhit;
963  vect_t v;
964  vect_t r_dir_unit;
965 
966  VMOVE(r_dir_unit, rd->rp->r_dir);
967  VUNITIZE(r_dir_unit);
968 
969  if (RTG.NMG_debug & DEBUG_RT_ISECT)
970  bu_log("ray_hit_vertex %p (%g %g %g) status=%d\n",
971  (void *)vu_p->v_p, V3ARGS(vu_p->v_p->vg_p->coord), status);
972 
973  myhit = NMG_INDEX_GET(rd->hitmiss, vu_p->v_p);
974  if (myhit) {
975  if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit, NMG_RT_HIT_MAGIC))
976  return;
977  /* oops, we have to change a MISS into a HIT */
978  BU_LIST_DEQUEUE(&myhit->l);
979  } else {
980  NMG_GET_HITMISS(myhit, rd->ap);
981  NMG_INDEX_ASSIGN(rd->hitmiss, vu_p->v_p, myhit);
982  myhit->outbound_use = (long *)vu_p;
983  myhit->inbound_use = (long *)vu_p;
984  }
985 
986  /* v = vector from ray point to hit vertex */
987  VSUB2(v, vu_p->v_p->vg_p->coord, rd->rp->r_pt);
988  /* using the unit vector for ray direction */
989  myhit->hit.hit_dist = VDOT(v, r_dir_unit); /* distance along ray */
990  VMOVE(myhit->hit.hit_point, vu_p->v_p->vg_p->coord);
991  myhit->hit.hit_private = (void *) vu_p->v_p;
992 
993  if (RTG.NMG_debug & DEBUG_RT_ISECT)
994  bu_log("\tray = (%g %g %g), dir=(%g %g %g), dist=%g\n",
995  V3ARGS(rd->rp->r_pt), V3ARGS(rd->rp->r_dir), myhit->hit.hit_dist);
996 
998 
999  /* XXX need to compute neighborhood of vertex so that ray can be
1000  * classified as in/on/out before and after the vertex.
1001  */
1002  vertex_neighborhood(rd, vu_p, myhit);
1003 
1004  /* XXX we re really should temper the results of vertex_neighborhood()
1005  * with the knowledge of "status"
1006  */
1007 
1008  hit_ins(rd, myhit);
1009 
1010  /* sanity check */
1011  NMG_CK_HITMISS(myhit);
1012 }
1013 
1014 
1015 /**
1016  * Called in one of the following situations:
1017  * 1) Zero length edge
1018  * 2) Vertexuse child of Loopuse
1019  * 3) Vertexuse child of Shell
1020  *
1021  * return:
1022  * 1 vertex was hit
1023  * 0 vertex was missed
1024  */
1025 HIDDEN int
1026 isect_ray_vertexuse(struct ray_data *rd, struct vertexuse *vu_p)
1027 {
1028  struct hitmiss *myhit;
1029  double ray_vu_dist;
1030 
1031  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1032  bu_log("isect_ray_vertexuse\n");
1033 
1034  NMG_CK_VERTEXUSE(vu_p);
1035  NMG_CK_VERTEX(vu_p->v_p);
1036  NMG_CK_VERTEX_G(vu_p->v_p->vg_p);
1037 
1038  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1039  bu_log("nmg_isect_ray_vertexuse %g %g %g",
1040  vu_p->v_p->vg_p->coord[0],
1041  vu_p->v_p->vg_p->coord[1],
1042  vu_p->v_p->vg_p->coord[2]);
1043 
1044  myhit = NMG_INDEX_GET(rd->hitmiss, vu_p->v_p);
1045  if (myhit) {
1046  if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit, NMG_RT_HIT_MAGIC)) {
1047  /* we've previously hit this vertex */
1048  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1049  bu_log(" previously hit\n");
1050  return 1;
1051  } else {
1052  /* we've previously missed this vertex */
1053  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1054  bu_log(" previously missed\n");
1055  return 0;
1056  }
1057  }
1058 
1059  /* intersect ray with vertex */
1060  ray_vu_dist = bn_dist_line3_pt3(rd->rp->r_pt, rd->rp->r_dir,
1061  vu_p->v_p->vg_p->coord);
1062 
1063  if (ray_vu_dist > rd->tol->dist) {
1064  /* ray misses vertex */
1065  ray_miss_vertex(rd, vu_p);
1066  return 0;
1067  }
1068 
1069  /* ray hits vertex */
1070  ray_hit_vertex(rd, vu_p, NMG_VERT_UNKNOWN);
1071 
1072  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
1074  }
1075 
1076  return 1;
1077 }
1078 
1079 
1080 /**
1081  * As the name implies, this routine is called when the ray and an
1082  * edge are colinear. It handles marking the vertices as hit,
1083  * remembering that this is a seg_in/seg_out pair, and builds the hit
1084  * on the edge.
1085  */
1086 HIDDEN void
1087 colinear_edge_ray(struct ray_data *rd, struct edgeuse *eu_p)
1088 {
1089  struct hitmiss *vhit1, *vhit2, *myhit;
1090 
1091 
1092  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1093  bu_log("\t - colinear_edge_ray\n");
1094 
1095  vhit1 = NMG_INDEX_GET(rd->hitmiss, eu_p->vu_p->v_p);
1096  vhit2 = NMG_INDEX_GET(rd->hitmiss, eu_p->eumate_p->vu_p->v_p);
1097 
1098  /* record the hit on each vertex, and remember that these two hits
1099  * should be kept together.
1100  */
1101  if (vhit1->hit.hit_dist > vhit2->hit.hit_dist) {
1102  ray_hit_vertex(rd, eu_p->vu_p, NMG_VERT_ENTER);
1104 
1105  ray_hit_vertex(rd, eu_p->eumate_p->vu_p, NMG_VERT_LEAVE);
1106  vhit2->start_stop = NMG_HITMISS_SEG_IN;
1107  } else {
1108  ray_hit_vertex(rd, eu_p->vu_p, NMG_VERT_LEAVE);
1109  vhit1->start_stop = NMG_HITMISS_SEG_IN;
1110 
1111  ray_hit_vertex(rd, eu_p->eumate_p->vu_p, NMG_VERT_ENTER);
1113  }
1114  vhit1->other = vhit2;
1115  vhit2->other = vhit1;
1116 
1117  NMG_GET_HITMISS(myhit, rd->ap);
1118  NMG_INDEX_ASSIGN(rd->hitmiss, eu_p->e_p, myhit);
1119  myhit->hit.hit_private = (void *)eu_p->e_p;
1120 
1122  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
1123 
1124  return;
1125 }
1126 
1127 
1128 /**
1129  * When a vertex at an end of an edge gets hit by the ray, this macro
1130  * is used to build the hit structures for the vertex and the edge.
1131  */
1132 #define HIT_EDGE_VERTEX(rd, eu_p, vu_p) \
1133  { \
1134  if (RTG.NMG_debug & DEBUG_RT_ISECT) bu_log("hit_edge_vertex\n"); \
1135  if (*eu_p->up.magic_p == NMG_SHELL_MAGIC || \
1136  (*eu_p->up.magic_p == NMG_LOOPUSE_MAGIC && \
1137  *eu_p->up.lu_p->up.magic_p == NMG_SHELL_MAGIC)) \
1138  ray_hit_vertex(rd, vu_p, NMG_VERT_ENTER_LEAVE); \
1139  else \
1140  ray_hit_vertex(rd, vu_p, NMG_VERT_UNKNOWN); \
1141  NMG_GET_HITMISS(myhit, rd->ap); \
1142  NMG_INDEX_ASSIGN(rd->hitmiss, eu_p->e_p, myhit); \
1143  myhit->hit.hit_private = (void *)eu_p->e_p; \
1144  \
1145  BU_LIST_MAGIC_SET(&myhit->l, NMG_RT_HIT_SUB_MAGIC); \
1146  BU_LIST_INSERT(&rd->rd_miss, &myhit->l); \
1147  }
1148 
1149 
1150 /**
1151  * Compute the "ray state" before and after the ray encounters a
1152  * hit-point on an edge.
1153  */
1154 HIDDEN void
1155 edge_hit_ray_state(struct ray_data *rd, struct edgeuse *eu, struct hitmiss *myhit)
1156 {
1157  double cos_angle;
1158  double inb_cos_angle = 2.0;
1159  double outb_cos_angle = -1.0;
1160  struct shell *s;
1161  struct faceuse *fu;
1162  struct faceuse *inb_fu = (struct faceuse *)NULL;
1163  struct faceuse *outb_fu = (struct faceuse *)NULL;
1164  struct edgeuse *inb_eu = (struct edgeuse *)NULL;
1165  struct edgeuse *outb_eu = (struct edgeuse *)NULL;
1166  struct edgeuse *eu_p;
1167  struct edgeuse *fu_eu;
1168  vect_t edge_left;
1169  vect_t norm;
1170  vect_t r_dir_unit;
1171 
1172  VMOVE(r_dir_unit, rd->rp->r_dir);
1173  VUNITIZE(r_dir_unit);
1174 
1175  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT)) {
1176  eu_p = BU_LIST_PNEXT_CIRC(edgeuse, eu);
1177  bu_log("edge_hit_ray_state(%g %g %g -> %g %g %g _vs_ %g %g %g)\n",
1178  eu->vu_p->v_p->vg_p->coord[0],
1179  eu->vu_p->v_p->vg_p->coord[1],
1180  eu->vu_p->v_p->vg_p->coord[2],
1181  eu_p->vu_p->v_p->vg_p->coord[0],
1182  eu_p->vu_p->v_p->vg_p->coord[1],
1183  eu_p->vu_p->v_p->vg_p->coord[2],
1184  rd->rp->r_dir[0],
1185  rd->rp->r_dir[1],
1186  rd->rp->r_dir[2]);
1187  }
1188 
1189  myhit->in_out = 0;
1190 
1191  s = nmg_find_s_of_eu(eu);
1192 
1193  eu_p = eu->e_p->eu_p;
1194  do {
1195  fu=nmg_find_fu_of_eu(eu_p);
1196  if (fu) {
1197  fu_eu = eu_p;
1198  if (fu->orientation == OT_OPPOSITE &&
1199  fu->fumate_p->orientation == OT_SAME) {
1200  fu = fu->fumate_p;
1201  fu_eu = eu_p->eumate_p;
1202  }
1203  if (UNLIKELY(fu->orientation != OT_SAME)) {
1204  bu_log("%s[%d]: I can't seem to find an OT_SAME faceuse\nThis must be a `dangling' face. I'll skip it\n", __FILE__, __LINE__);
1205  continue;
1206  }
1207 
1208  if (fu->s_p != s)
1209  continue;
1210 
1211  if (UNLIKELY(nmg_find_eu_leftvec(edge_left, eu_p))) {
1212  bu_log("edgeuse not part of faceuse");
1213  continue;
1214  }
1215 
1216  if (UNLIKELY(!(NMG_3MANIFOLD &
1217  NMG_MANIFOLDS(rd->manifolds, fu->f_p)))) {
1218  bu_log("This is not a 3-Manifold face. I'll skip it\n");
1219  continue;
1220  }
1221 
1222  cos_angle = VDOT(edge_left, r_dir_unit);
1223 
1224  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT)) {
1225  bu_log("left_vect:(%g %g %g) cos_angle:%g\n",
1226  edge_left[0], edge_left[1],
1227  edge_left[2], cos_angle);
1228  }
1229 
1230  if (cos_angle < inb_cos_angle) {
1231  inb_cos_angle = cos_angle;
1232  inb_fu = fu;
1233  inb_eu = fu_eu;
1234  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT))
1235  bu_log("New inb cos_angle %g\n", inb_cos_angle);
1236  }
1237  if (cos_angle > outb_cos_angle) {
1238  outb_cos_angle = cos_angle;
1239  outb_fu = fu;
1240  outb_eu = fu_eu;
1241  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT))
1242  bu_log("New outb cos_angle %g\n", outb_cos_angle);
1243  }
1244  }
1245  } while ((eu_p = eu_p->eumate_p->radial_p) != eu->e_p->eu_p);
1246 
1247  if (!inb_fu || !outb_fu) {
1248  /* we hit a wire edge */
1249  myhit->in_out = HMG_HIT_ANY_ANY;
1250  myhit->hit.hit_private = (void *)eu;
1251  myhit->inbound_use = myhit->outbound_use = (long *)eu;
1252  return;
1253  }
1254 
1255  /* inb_fu is closest to ray on outbound side.
1256  * outb_fu is closest to ray on inbound side.
1257  */
1258 
1259  /* Compute the ray state on the inbound side */
1260  NMG_GET_FU_NORMAL(norm, inb_fu);
1261  VMOVE(myhit->inbound_norm, norm);
1262  if (UNLIKELY(MAGSQ(norm) < VDIVIDE_TOL))
1263  bu_bomb("edge_hit_ray_state() null normal!\n");
1264 
1265  cos_angle = VDOT(norm, r_dir_unit);
1266 
1267  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT)) {
1268  VPRINT("\ninb face normal", norm);
1269  bu_log("cos_angle wrt ray direction: %g\n", cos_angle);
1270  }
1271 
1272  if (BN_VECT_ARE_PERP(cos_angle, rd->tol))
1273  myhit->in_out |= NMG_RAY_STATE_ON << 4;
1274  else if (cos_angle < -SMALL_FASTF)
1275  myhit->in_out |= NMG_RAY_STATE_OUTSIDE << 4;
1276  else /* (cos_angle > 0.0) */
1277  myhit->in_out |= NMG_RAY_STATE_INSIDE << 4;
1278 
1279 
1280  /* Compute the ray state on the outbound side */
1281  NMG_GET_FU_NORMAL(norm, outb_fu);
1282  VMOVE(myhit->outbound_norm, norm);
1283  cos_angle = VDOT(norm, r_dir_unit);
1284 
1285  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT)) {
1286  VPRINT("\noutb face normal", norm);
1287  bu_log("cos_angle wrt ray direction: %g\n", cos_angle);
1288  }
1289 
1290  if (BN_VECT_ARE_PERP(cos_angle, rd->tol))
1291  myhit->in_out |= NMG_RAY_STATE_ON;
1292  else if (cos_angle > SMALL_FASTF)
1293  myhit->in_out |= NMG_RAY_STATE_OUTSIDE;
1294  else /* (cos_angle < 0.0) */
1295  myhit->in_out |= NMG_RAY_STATE_INSIDE;
1296 
1297 
1298  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT)) {
1299  bu_log("myhit->in_out: 0x%02x/", myhit->in_out);
1300  switch (myhit->in_out) {
1301  case HMG_HIT_IN_IN:
1302  bu_log("IN_IN\n"); break;
1303  case HMG_HIT_IN_OUT:
1304  bu_log("IN_OUT\n"); break;
1305  case HMG_HIT_OUT_IN:
1306  bu_log("OUT_IN\n"); break;
1307  case HMG_HIT_OUT_OUT:
1308  bu_log("OUT_OUT\n"); break;
1309  case HMG_HIT_IN_ON:
1310  bu_log("IN_ON\n"); break;
1311  case HMG_HIT_ON_IN:
1312  bu_log("ON_IN\n"); break;
1313  case HMG_HIT_OUT_ON:
1314  bu_log("OUT_ON\n"); break;
1315  case HMG_HIT_ON_OUT:
1316  bu_log("ON_OUT\n"); break;
1317  case HMG_HIT_ON_ON:
1318  bu_log("ON_ON\n"); break;
1319  default:
1320  bu_log("?_?\n"); break;
1321  }
1322  }
1323 
1324 
1325  switch (myhit->in_out) {
1326  case HMG_HIT_ON_ON: /* Another fall through?? JRA */
1327  case HMG_HIT_IN_IN: /* fallthrough */
1328  case HMG_HIT_OUT_OUT: /* fallthrough */
1329  case HMG_HIT_IN_ON: /* fallthrough */
1330  case HMG_HIT_ON_IN: /* two hits */
1331  myhit->inbound_use = (long *)inb_eu;
1332  myhit->outbound_use = (long *)outb_eu;
1333  myhit->hit.hit_private = (void *)inb_eu;
1334  break;
1335  case HMG_HIT_IN_OUT: /* one hit - outbound */
1336  case HMG_HIT_ON_OUT: /* one hit - outbound */
1337  myhit->inbound_use = (long *)outb_eu;
1338  myhit->outbound_use = (long *)outb_eu;
1339  myhit->hit.hit_private = (void *)outb_eu;
1340  break;
1341  case HMG_HIT_OUT_IN: /* one hit - inbound */
1342  case HMG_HIT_OUT_ON: /* one hit - inbound */
1343  myhit->inbound_use = (long *)inb_eu;
1344  myhit->outbound_use = (long *)inb_eu;
1345  myhit->hit.hit_private = (void *)inb_eu;
1346  break;
1347  default:
1348  bu_log("%s %d: Bad edge in/out state = %d\n",
1349  __FILE__, __LINE__, myhit->in_out);
1350  bu_bomb("edge_hit_ray_state() bad edge in_out state\n");
1351  break;
1352  }
1353 }
1354 
1355 
1356 /**
1357  * record a hit on an edge.
1358  */
1359 HIDDEN void
1360 ray_hit_edge(struct ray_data *rd, struct edgeuse *eu_p, double dist_along_ray, fastf_t *pt)
1361 {
1362  struct hitmiss *myhit;
1363  ray_miss_vertex(rd, eu_p->vu_p);
1364  ray_miss_vertex(rd, eu_p->eumate_p->vu_p);
1365 
1366  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1367  bu_log("\t - HIT edge %p (edgeuse=%p)\n", (void *)eu_p->e_p, (void *)eu_p);
1368 
1369  myhit = NMG_INDEX_GET(rd->hitmiss, eu_p->e_p);
1370  if (myhit) {
1371  switch (((struct bu_list *)myhit)->magic) {
1372  case NMG_RT_MISS_MAGIC:
1373  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1374  bu_log("\tedge previously missed, changing to hit\n");
1375  BU_LIST_DEQUEUE(&myhit->l);
1376  break;
1377  case NMG_RT_HIT_SUB_MAGIC:
1378  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1379  bu_log("\tedge vertex previously hit\n");
1380  return;
1381  case NMG_RT_HIT_MAGIC:
1382  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1383  bu_log("\tedge previously hit\n");
1384  return;
1385  default:
1386  break;
1387  }
1388  } else {
1389  NMG_GET_HITMISS(myhit, rd->ap);
1390  }
1391 
1392  /* create hit structure for this edge */
1393  NMG_INDEX_ASSIGN(rd->hitmiss, eu_p->e_p, myhit);
1394  myhit->outbound_use = (long *)eu_p;
1395  myhit->inbound_use = (long *)eu_p;
1396 
1397  /* build the hit structure */
1398  myhit->hit.hit_dist = dist_along_ray;
1399  VMOVE(myhit->hit.hit_point, pt);
1400  myhit->hit.hit_private = (void *) eu_p->e_p;
1401 
1402  edge_hit_ray_state(rd, eu_p, myhit);
1403 
1404  hit_ins(rd, myhit);
1405 
1406  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
1407  struct faceuse *fu=nmg_find_fu_of_eu(eu_p);
1408 
1409  if (fu)
1410  nmg_rt_isect_plfu(fu, rd->rp->r_pt, myhit->hit.hit_point);
1411  else
1412  pleu(eu_p, rd->rp->r_pt, myhit->hit.hit_point);
1413  }
1414 }
1415 
1416 
1417 void
1418 isect_ray_lseg(struct ray_data *rd, struct edgeuse *eu_p)
1419 {
1420  int status;
1421  struct hitmiss *myhit;
1422  int vhit1, vhit2;
1423  fastf_t dist_along_ray;
1424  vect_t r_dir_unit;
1425 
1426  VMOVE(r_dir_unit, rd->rp->r_dir);
1427  VUNITIZE(r_dir_unit);
1428 
1429  status = bn_isect_line_lseg(&dist_along_ray,
1430  rd->rp->r_pt, rd->rp->r_dir,
1431  eu_p->vu_p->v_p->vg_p->coord,
1432  eu_p->eumate_p->vu_p->v_p->vg_p->coord,
1433  rd->tol);
1434 
1435  switch (status) {
1436  case -4 :
1437  /* Zero length edge. The routine bn_isect_line_lseg()
1438  * can't help us. Intersect the ray with each vertex. If
1439  * either vertex is hit, then record that the edge has
1440  * sub-elements which where hit. Otherwise, record the
1441  * edge as being missed.
1442  */
1443 
1444  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1445  bu_log("\t - Zero length edge\n");
1446 
1447  vhit1 = isect_ray_vertexuse(rd, eu_p->vu_p);
1448  vhit2 = isect_ray_vertexuse(rd, eu_p->eumate_p->vu_p);
1449 
1450  NMG_GET_HITMISS(myhit, rd->ap);
1451  NMG_INDEX_ASSIGN(rd->hitmiss, eu_p->e_p, myhit);
1452 
1453  myhit->hit.hit_private = (void *)eu_p->e_p;
1454 
1455  if (vhit1 || vhit2) {
1456  /* we hit the vertex */
1458  } else {
1459  /* both vertices were missed, so edge is missed */
1461  }
1462  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
1463 
1464  break;
1465  case -3 : /* fallthrough */
1466  case -2 :
1467  /* The ray misses the edge segment, but hits the infinite
1468  * line of the edge to one end of the edge segment. This
1469  * is an exercise in tabulating the nature of the miss.
1470  */
1471 
1472  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1473  bu_log("\t - Miss edge, \"hit\" line\n");
1474  /* record the fact that we missed each vertex */
1475  (void)ray_miss_vertex(rd, eu_p->vu_p);
1476  (void)ray_miss_vertex(rd, eu_p->eumate_p->vu_p);
1477 
1478  /* record the fact that we missed the edge */
1479  NMG_GET_HITMISS(myhit, rd->ap);
1480  NMG_INDEX_ASSIGN(rd->hitmiss, eu_p->e_p, myhit);
1481  myhit->hit.hit_private = (void *)eu_p->e_p;
1482 
1484  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
1485 
1486  break;
1487  case -1 : /* just plain missed the edge/line */
1488  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1489  bu_log("\t - Miss edge/line\n");
1490 
1491  ray_miss_vertex(rd, eu_p->vu_p);
1492  ray_miss_vertex(rd, eu_p->eumate_p->vu_p);
1493 
1494  NMG_GET_HITMISS(myhit, rd->ap);
1495  NMG_INDEX_ASSIGN(rd->hitmiss, eu_p->e_p, myhit);
1496  myhit->hit.hit_private = (void *)eu_p->e_p;
1497 
1499  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
1500 
1501  break;
1502  case 0 : /* oh joy. Lines are co-linear */
1503  HIT_EDGE_VERTEX(rd, eu_p, eu_p->vu_p);
1504  HIT_EDGE_VERTEX(rd, eu_p, eu_p->eumate_p->vu_p);
1505  colinear_edge_ray(rd, eu_p);
1506  break;
1507  case 1 :
1508  HIT_EDGE_VERTEX(rd, eu_p, eu_p->vu_p);
1509  break;
1510  case 2 :
1511  HIT_EDGE_VERTEX(rd, eu_p, eu_p->eumate_p->vu_p);
1512  break;
1513  case 3 : {
1514  /* a hit on an edge */
1515  point_t pt;
1516 
1517  VJOIN1(pt, rd->rp->r_pt, dist_along_ray, r_dir_unit);
1518  ray_hit_edge(rd, eu_p, dist_along_ray, pt);
1519 
1520  break;
1521  }
1522  }
1523 }
1524 
1525 
1526 /**
1527  * Intersect ray with edgeuse. If they pass within tolerance, a hit
1528  * is generated.
1529  */
1530 HIDDEN void
1531 isect_ray_edgeuse(struct ray_data *rd, struct edgeuse *eu_p)
1532 {
1533  struct hitmiss *myhit;
1534 
1535  NMG_CK_EDGEUSE(eu_p);
1536  NMG_CK_EDGEUSE(eu_p->eumate_p);
1537  NMG_CK_EDGE(eu_p->e_p);
1538  NMG_CK_VERTEXUSE(eu_p->vu_p);
1539  NMG_CK_VERTEXUSE(eu_p->eumate_p->vu_p);
1540  NMG_CK_VERTEX(eu_p->vu_p->v_p);
1541  NMG_CK_VERTEX(eu_p->eumate_p->vu_p->v_p);
1542 
1543  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
1544  bu_log("isect_ray_edgeuse (%g %g %g) -> (%g %g %g)",
1545  eu_p->vu_p->v_p->vg_p->coord[0],
1546  eu_p->vu_p->v_p->vg_p->coord[1],
1547  eu_p->vu_p->v_p->vg_p->coord[2],
1548  eu_p->eumate_p->vu_p->v_p->vg_p->coord[0],
1549  eu_p->eumate_p->vu_p->v_p->vg_p->coord[1],
1550  eu_p->eumate_p->vu_p->v_p->vg_p->coord[2]);
1551  }
1552 
1553  if (eu_p->e_p != eu_p->eumate_p->e_p)
1554  bu_bomb("isect_ray_edgeuse() edgeuse mate has step-father\n");
1555 
1556  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1557  bu_log("\n\tLooking for previous hit on edge %p ...\n",
1558  (void *)eu_p->e_p);
1559 
1560  myhit = NMG_INDEX_GET(rd->hitmiss, eu_p->e_p);
1561  if (myhit) {
1562  if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit, NMG_RT_HIT_MAGIC)) {
1563  /* previously hit vertex or edge */
1564  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1565  bu_log("\tedge previously hit\n");
1566  return;
1567  } else if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit, NMG_RT_HIT_SUB_MAGIC)) {
1568  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1569  bu_log("\tvertex of edge previously hit\n");
1570  return;
1571  } else if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit, NMG_RT_MISS_MAGIC)) {
1572  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1573  bu_log("\tedge previously missed\n");
1574  return;
1575  } else {
1576  nmg_bu_bomb(rd, "what happened?\n");
1577  }
1578  }
1579 
1580  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1581  bu_log("\t No previous hit\n");
1582 
1583  if (!eu_p->g.magic_p)
1584  isect_ray_lseg(rd, eu_p);
1585  else {
1586  switch (*eu_p->g.magic_p) {
1587  case NMG_EDGE_G_LSEG_MAGIC:
1588  isect_ray_lseg(rd, eu_p);
1589  break;
1591  /* not implemented */
1592  break;
1593  }
1594  }
1595 }
1596 
1597 
1598 HIDDEN void
1599 isect_ray_loopuse(struct ray_data *rd, struct loopuse *lu_p)
1600 {
1601  struct edgeuse *eu_p;
1602 
1603  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1604  bu_log("isect_ray_loopuse(%p, loop:%p)\n", (void *)rd, (void *)lu_p->l_p);
1605 
1606  NMG_CK_LOOPUSE(lu_p);
1607  NMG_CK_LOOP(lu_p->l_p);
1608  NMG_CK_LOOP_G(lu_p->l_p->lg_p);
1609 
1610  if (BU_LIST_FIRST_MAGIC(&lu_p->down_hd) == NMG_EDGEUSE_MAGIC) {
1611  for (BU_LIST_FOR(eu_p, edgeuse, &lu_p->down_hd)) {
1612  isect_ray_edgeuse(rd, eu_p);
1613  }
1614  return;
1615 
1616  } else if (BU_LIST_FIRST_MAGIC(&lu_p->down_hd)!=NMG_VERTEXUSE_MAGIC) {
1617  bu_log("in %s at %d", __FILE__, __LINE__);
1618  nmg_bu_bomb(rd, " bad loopuse child magic");
1619  }
1620 
1621  /* loopuse child is vertexuse */
1622 
1623  (void) isect_ray_vertexuse(rd, BU_LIST_FIRST(vertexuse, &lu_p->down_hd));
1624 }
1625 
1626 
1627 HIDDEN void
1628 eu_touch_func(struct edgeuse *eu, fastf_t *pt, char *priv)
1629 {
1630  struct edgeuse *eu_next;
1631  struct ray_data *rd;
1632 
1633  NMG_CK_EDGEUSE(eu);
1634  NMG_CK_EDGEUSE(eu->eumate_p);
1635  NMG_CK_EDGE(eu->e_p);
1636  NMG_CK_VERTEXUSE(eu->vu_p);
1637  NMG_CK_VERTEXUSE(eu->eumate_p->vu_p);
1638  NMG_CK_VERTEX(eu->vu_p->v_p);
1639  NMG_CK_VERTEX(eu->eumate_p->vu_p->v_p);
1640 
1641  eu_next = BU_LIST_PNEXT_CIRC(edgeuse, eu);
1642 
1643  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1644  bu_log("eu_touch(%g %g %g -> %g %g %g\n",
1645  eu->vu_p->v_p->vg_p->coord[0],
1646  eu->vu_p->v_p->vg_p->coord[1],
1647  eu->vu_p->v_p->vg_p->coord[2],
1648  eu_next->vu_p->v_p->vg_p->coord[0],
1649  eu_next->vu_p->v_p->vg_p->coord[1],
1650  eu_next->vu_p->v_p->vg_p->coord[2]);
1651 
1652  rd = (struct ray_data *)priv;
1653  rd->face_subhit = 1;
1654 
1655  ray_hit_edge(rd, eu, rd->ray_dist_to_plane, pt);
1656 }
1657 
1658 
1659 HIDDEN void
1660 vu_touch_func(struct vertexuse *vu, fastf_t *UNUSED(pt), char *priv)
1661 {
1662  struct ray_data *rd;
1663 
1664  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1665  bu_log("vu_touch(%g %g %g)\n",
1666  vu->v_p->vg_p->coord[0],
1667  vu->v_p->vg_p->coord[1],
1668  vu->v_p->vg_p->coord[2]);
1669 
1670  rd = (struct ray_data *)priv;
1671 
1672  rd->face_subhit = 1;
1674 }
1675 
1676 
1677 HIDDEN void
1678 record_face_hit(struct ray_data *rd, struct hitmiss *myhit, fastf_t *plane_pt, double dist, struct faceuse *fu_p, fastf_t *norm)
1679 {
1680  double cos_angle;
1681  vect_t r_dir_unit;
1682 
1684  myhit->outbound_use = (long *)fu_p;
1685  myhit->inbound_use = (long *)fu_p;
1686 
1687 
1688  VMOVE(myhit->hit.hit_point, plane_pt);
1689 
1690  /* also rd->ray_dist_to_plane */
1691  myhit->hit.hit_dist = dist;
1692  myhit->hit.hit_private = (void *)fu_p->f_p;
1693 
1694 
1695  /* compute what the ray-state is before and after this
1696  * encountering this hit point.
1697  */
1698  VMOVE(r_dir_unit, rd->rp->r_dir);
1699  VUNITIZE(r_dir_unit);
1700  cos_angle = VDOT(norm, r_dir_unit);
1701  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
1702  VPRINT("face Normal", norm);
1703  bu_log("cos_angle wrt ray direction: %g\n", cos_angle);
1704  bu_log("fu %p manifoldness = %d\n",
1705  (void *)fu_p, NMG_MANIFOLDS(rd->manifolds, fu_p));
1706  }
1707 
1708 
1709  if (! (NMG_MANIFOLDS(rd->manifolds, fu_p) & NMG_3MANIFOLD)) {
1710  myhit->in_out = HMG_HIT_ANY_ANY;
1711 
1712  if (cos_angle < rd->tol->perp) {
1713  VMOVE(myhit->inbound_norm, norm);
1714  VREVERSE(myhit->outbound_norm, norm);
1715  myhit->inbound_use = (long *)fu_p;
1716  myhit->outbound_use = (long *)fu_p->fumate_p;
1717  } else {
1718  VREVERSE(myhit->inbound_norm, norm);
1719  VMOVE(myhit->outbound_norm, norm);
1720  myhit->inbound_use = (long *)fu_p->fumate_p;
1721  myhit->outbound_use = (long *)fu_p;
1722  }
1723 
1724  return;
1725  }
1726 
1727 
1728  switch (fu_p->orientation) {
1729  case OT_SAME:
1730  if (BN_VECT_ARE_PERP(cos_angle, rd->tol)) {
1731  /* perpendicular? */
1732  bu_log("%s[%d]: Ray is in plane of face?\n",
1733  __FILE__, __LINE__);
1734  bu_bomb("record_face_hit() I quit\n");
1735  } else if (cos_angle > SMALL_FASTF) {
1736  myhit->in_out = HMG_HIT_IN_OUT;
1737  VREVERSE(myhit->outbound_norm, norm);
1738  myhit->outbound_use = (long *)fu_p;
1739  myhit->inbound_use = (long *)fu_p;
1740  } else {
1741  myhit->in_out = HMG_HIT_OUT_IN;
1742  VMOVE(myhit->inbound_norm, norm);
1743  myhit->inbound_use = (long *)fu_p;
1744  myhit->outbound_use = (long *)fu_p;
1745  }
1746  break;
1747  case OT_OPPOSITE:
1748  if (BN_VECT_ARE_PERP(cos_angle, rd->tol)) {
1749  /* perpendicular? */
1750  bu_log("%s[%d]: Ray is in plane of face?\n",
1751  __FILE__, __LINE__);
1752  bu_bomb("record_face_hit() I quit\n");
1753  } else if (cos_angle > SMALL_FASTF) {
1754  myhit->in_out = HMG_HIT_OUT_IN;
1755  VREVERSE(myhit->inbound_norm, norm);
1756  myhit->inbound_use = (long *)fu_p;
1757  myhit->outbound_use = (long *)fu_p;
1758  } else {
1759  myhit->in_out = HMG_HIT_IN_OUT;
1760  VMOVE(myhit->outbound_norm, norm);
1761  myhit->inbound_use = (long *)fu_p;
1762  myhit->outbound_use = (long *)fu_p;
1763  }
1764  break;
1765  default:
1766  bu_log("%s %d:face orientation not SAME/OPPOSITE\n",
1767  __FILE__, __LINE__);
1768  bu_bomb("record_face_hit() Crash and burn\n");
1769  }
1770 
1771  hit_ins(rd, myhit);
1772  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1773  nmg_rt_isect_plfu(fu_p, rd->rp->r_pt, myhit->hit.hit_point);
1774 
1775  /* sanity check */
1776  NMG_CK_HITMISS(myhit);
1777 }
1778 
1779 
1780 /**
1781  * this is the UV-space tolerance for the NURB intersector, a larger
1782  * number will improve speed, but too large will produce errors.
1783  * Perhaps a routine to calculate an appropriate UV_TOL could be
1784  * constructed.
1785  */
1786 #define UV_TOL 1.0e-6
1787 
1788 void
1789 isect_ray_snurb_face(struct ray_data *rd, struct faceuse *fu, struct face_g_snurb *fg)
1790 {
1791  plane_t pl, pl1, pl2;
1792  struct rt_nurb_uv_hit *hp;
1793  struct bu_list bezier;
1794  struct bu_list hit_list;
1795  struct face_g_snurb *srf;
1796  struct face *f;
1797 
1798  NMG_CK_RD(rd);
1799  NMG_CK_FACE_G_SNURB(fg);
1800  NMG_CK_FACEUSE(fu);
1801 
1802  f = fu->f_p;
1803 
1804  /* calculate two orthogonal planes that intersect along ray */
1805  bn_vec_ortho(pl2, rd->rp->r_dir);
1806  VCROSS(pl1, pl2, rd->rp->r_dir);
1807  pl1[W] = VDOT(rd->rp->r_pt, pl1);
1808  pl2[W] = VDOT(rd->rp->r_pt, pl2);
1809 
1810  BU_LIST_INIT(&bezier);
1811  BU_LIST_INIT(&hit_list);
1812 
1813  rt_nurb_bezier(&bezier, fg, rd->ap->a_resource);
1814 
1815  while (BU_LIST_NON_EMPTY(&bezier)) {
1816  point_t srf_min, srf_max;
1817  int planar;
1818  point_t hit;
1819  fastf_t dist = (fastf_t)0.0;
1820 
1821  VSETALL(hit, 0);
1822 
1823  srf = BU_LIST_FIRST(face_g_snurb, &bezier);
1824  BU_LIST_DEQUEUE(&srf->l);
1825 
1826  /* calculate intersection points on NURB surface (in uv space) */
1827  /* check if NURB surface is a simple planar surface */
1828  if (srf->order[0] == 2 && srf->order[1] ==2 && srf->s_size[0] ==2 && srf->s_size[1] == 2)
1829  planar = 1;
1830  else
1831  planar = 0;
1832 
1833  if (planar) {
1834  vect_t u_dir, v_dir;
1835  point_t ctl_pt[4];
1836  vect_t hit_dir;
1837  int i, j;
1838  int rational;
1839  int coords;
1840  fastf_t *pt;
1841  fastf_t u, v;
1842 
1843  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1844  bu_log("isect_ray_snurb_face: face is planar\n");
1845 
1846  rational = RT_NURB_IS_PT_RATIONAL(srf->pt_type);
1847  coords = RT_NURB_EXTRACT_COORDS(srf->pt_type);
1848  if (coords < 1)
1849  continue; /* "pointless" */
1850 
1851  if (coords > ELEMENTS_PER_POINT) {
1852  bu_log("isect_ray_snurb_face: invalid coordinates value %d\n",
1853  coords);
1854  continue;
1855  }
1856 
1857  pt = srf->ctl_points;
1858  for (i = 0; i < 4; i++) {
1859  for (j = 0; j < coords; j++) {
1860  ctl_pt[i][j] = *pt;
1861  pt++;
1862  }
1863  for (j = 0; rational && j < coords-1; j++) {
1864  ctl_pt[i][j] = ctl_pt[i][j]/ctl_pt[i][coords-1];
1865  }
1866  }
1867  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
1868  for (i = 0; i < 4; i++)
1869  bu_log("\tctl_point[%d] = (%g %g %g)\n", i, V3ARGS(ctl_pt[i]));
1870  bu_log("uv range (%g %g) <-> (%g %g)\n", srf->u.knots[0], srf->v.knots[0], srf->u.knots[srf->u.k_size-1], srf->v.knots[srf->v.k_size-1]);
1871  }
1872 
1873  VSUB2(u_dir, ctl_pt[1], ctl_pt[0]);
1874  VSUB2(v_dir, ctl_pt[2], ctl_pt[0]);
1875  VCROSS(pl, u_dir, v_dir);
1876  VUNITIZE(pl);
1877  pl[W] = VDOT(pl, ctl_pt[0]);
1878  hp = (struct rt_nurb_uv_hit *)NULL;
1879  if (bn_isect_line3_plane(&dist, rd->rp->r_pt, rd->rp->r_dir, pl, rd->tol) <= 0) {
1880  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1881  bu_log("\tNo intersection\n");
1882 
1883  rt_nurb_free_snurb(srf, rd->ap->a_resource);
1884  continue;
1885  }
1886 
1887  VJOIN1(hit, rd->rp->r_pt, dist, rd->rp->r_dir);
1888  VSUB2(hit_dir, hit, ctl_pt[0]);
1889  u = srf->u.knots[0] + (srf->u.knots[srf->u.k_size-1] - srf->u.knots[0]) * VDOT(hit_dir, u_dir) / MAGSQ(u_dir);
1890  v = srf->v.knots[0] + (srf->v.knots[srf->v.k_size-1] - srf->v.knots[0]) * VDOT(hit_dir, v_dir) / MAGSQ(v_dir);
1891 
1892  if (u >= srf->u.knots[0] && u <= srf->u.knots[srf->u.k_size-1] &&
1893  v >= srf->v.knots[0] && v <= srf->v.knots[srf->v.k_size-1])
1894  {
1895  BU_ALLOC(hp, struct rt_nurb_uv_hit);
1896  hp->next = (struct rt_nurb_uv_hit *)NULL;
1897  hp->sub = 0;
1898  hp->u = u;
1899  hp->v = v;
1900 
1901  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1902  bu_log("\thit at uv=(%g %g), xyz=(%g %g %g)\n", hp->u, hp->v, V3ARGS(hit));
1903  }
1904  } else {
1905  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1906  bu_log("isect_ray_snurb_face: using planes (%g %g %g %g) (%g %g %g %g)\n",
1907  V4ARGS(pl1), V4ARGS(pl2));
1908  (void)rt_nurb_s_bound(srf, srf_min, srf_max);
1909  if (!rt_in_rpp(rd->rp, rd->rd_invdir, srf_min, srf_max)) {
1910  rt_nurb_free_snurb(srf, rd->ap->a_resource);
1911  continue;
1912  }
1913  hp = rt_nurb_intersect(srf, pl1, pl2, UV_TOL, rd->ap->a_resource, NULL);
1914  }
1915 
1916  /* process each hit point */
1917  while (hp != (struct rt_nurb_uv_hit *)NULL) {
1918  struct rt_nurb_uv_hit *next;
1919  struct hitmiss *myhit;
1920  vect_t to_hit;
1921  fastf_t dot;
1922  fastf_t homo_hit[4];
1923  int ot_sames, ot_opps;
1924  struct loopuse *lu;
1925 
1926  next = hp->next;
1927 
1928  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1929  bu_log("\tintersect snurb surface at uv=(%g %g)\n", hp->u, hp->v);
1930 
1931  /* check if point is in face (trimming curves) */
1932  ot_sames = 0;
1933  ot_opps = 0;
1934 
1935  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
1936  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
1937  continue;
1938 
1939  if (lu->orientation == OT_SAME)
1940  ot_sames += nmg_uv_in_lu(hp->u, hp->v, lu);
1941  else if (lu->orientation == OT_OPPOSITE)
1942  ot_opps += nmg_uv_in_lu(hp->u, hp->v, lu);
1943  else {
1944  bu_log("isect_ray_snurb_face: lu orientation = %s!!\n",
1945  nmg_orientation(lu->orientation));
1946  bu_bomb("isect_ray_snurb_face: bad lu orientation\n");
1947  }
1948  }
1949 
1950  if (ot_sames == 0 || ot_opps == ot_sames) {
1951  /* not a hit */
1952 
1953  if (RTG.NMG_debug & DEBUG_RT_ISECT)
1954  bu_log("\tNot a hit\n");
1955 
1956  bu_free((char *)hp, "hit");
1957  hp = next;
1958  continue;
1959  }
1960 
1961  NMG_GET_HITMISS(myhit, rd->ap);
1962  NMG_INDEX_ASSIGN(rd->hitmiss, fu->f_p, myhit);
1963  myhit->hit.hit_private = (void *)fu->f_p;
1964  myhit->inbound_use = myhit->outbound_use = (long *)&fu->l.magic;
1965 
1966  /* calculate actual hit point (x y z) */
1967  if (planar) {
1968  VMOVE(myhit->hit.hit_point, hit);
1969  myhit->hit.hit_dist = dist;
1970  VMOVE(myhit->hit.hit_normal, pl);
1971  } else {
1972  rt_nurb_s_eval(srf, hp->u, hp->v, homo_hit);
1973  if (RT_NURB_IS_PT_RATIONAL(srf->pt_type)) {
1974  fastf_t inv_homo;
1975 
1976  inv_homo = 1.0/homo_hit[W];
1977  VSCALE(myhit->hit.hit_point, homo_hit, inv_homo);
1978  } else
1979  VMOVE(myhit->hit.hit_point, homo_hit);
1980 
1981  VSUB2(to_hit, myhit->hit.hit_point, rd->rp->r_pt);
1982  myhit->hit.hit_dist = VDOT(to_hit, rd->rp->r_dir);
1983 
1984  /* get surface normal */
1985  rt_nurb_s_norm(srf, hp->u, hp->v, myhit->hit.hit_normal);
1986  }
1987 
1988  /* may need to reverse it */
1989  if (f->flip)
1990  VREVERSE(myhit->hit.hit_normal, myhit->hit.hit_normal);
1991 
1992  dot = VDOT(myhit->hit.hit_normal, rd->rp->r_dir);
1993 
1994  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
1995  bu_log("\thit at dist = %g (%g %g %g), norm = (%g %g %g)\n",
1996  myhit->hit.hit_dist,
1997  V3ARGS(myhit->hit.hit_point),
1998  V3ARGS(myhit->hit.hit_normal));
1999  if (dot > SMALL_FASTF)
2000  bu_log("\t\tdot = %g (exit point)\n", dot);
2001  else
2002  bu_log("\t\tdot = %g (entrance point)\n", dot);
2003  }
2004 
2005  switch (fu->orientation) {
2006  case OT_SAME:
2007  if (BN_VECT_ARE_PERP(dot, rd->tol)) {
2008  /* perpendicular? */
2009  bu_log("%s[%d]: Ray is in plane of face?\n",
2010  __FILE__, __LINE__);
2011  bu_bomb("record_face_hit() I quit\n");
2012  } else if (dot > SMALL_FASTF) {
2013  myhit->in_out = HMG_HIT_IN_OUT;
2014  VMOVE(myhit->outbound_norm, myhit->hit.hit_normal);
2015  myhit->outbound_use = (long *)fu;
2016  myhit->inbound_use = (long *)fu;
2017  } else {
2018  myhit->in_out = HMG_HIT_OUT_IN;
2019  VMOVE(myhit->inbound_norm, myhit->hit.hit_normal);
2020  myhit->inbound_use = (long *)fu;
2021  myhit->outbound_use = (long *)fu;
2022  }
2023  break;
2024  case OT_OPPOSITE:
2025  if (BN_VECT_ARE_PERP(dot, rd->tol)) {
2026  /* perpendicular? */
2027  bu_log("%s[%d]: Ray is in plane of face?\n",
2028  __FILE__, __LINE__);
2029  bu_bomb("record_face_hit() I quit\n");
2030  } else if (dot > SMALL_FASTF) {
2031  myhit->in_out = HMG_HIT_OUT_IN;
2032  VREVERSE(myhit->inbound_norm, myhit->hit.hit_normal);
2033  myhit->inbound_use = (long *)fu;
2034  myhit->outbound_use = (long *)fu;
2035  } else {
2036  myhit->in_out = HMG_HIT_IN_OUT;
2037  VREVERSE(myhit->outbound_norm, myhit->hit.hit_normal);
2038  myhit->inbound_use = (long *)fu;
2039  myhit->outbound_use = (long *)fu;
2040  }
2041  break;
2042  default:
2043  bu_log("%s %d:face orientation not SAME/OPPOSITE\n",
2044  __FILE__, __LINE__);
2045  bu_bomb("record_face_hit() Crash and burn\n");
2046  }
2047 
2048  hit_ins(rd, myhit);
2049 
2050  bu_free((char *)hp, "hit");
2051  hp = next;
2052  }
2053  rt_nurb_free_snurb(srf, rd->ap->a_resource);
2054  }
2055 }
2056 
2057 
2058 HIDDEN void
2059 isect_ray_planar_face(struct ray_data *rd, struct faceuse *fu_p)
2060 {
2061  plane_t norm;
2062  fastf_t dist;
2063  struct hitmiss *myhit;
2064  point_t plane_pt;
2065  struct loopuse *lu_p;
2066  int pt_class;
2067 
2068  /* the geometric intersection of the ray with the plane of the
2069  * face has already been done by isect_ray_faceuse().
2070  */
2071  NMG_GET_FU_PLANE(norm, fu_p);
2072 
2073  /* ray hits plane:
2074  *
2075  * Get the ray/plane intersection point. Then compute whether
2076  * this point lies within the area of the face.
2077  */
2078 
2079  VMOVE(plane_pt, rd->plane_pt);
2080  dist = rd->ray_dist_to_plane;
2081 
2082  if (UNLIKELY(fabs(DIST_PT_PLANE(plane_pt, norm)) > rd->tol->dist)) {
2083  bu_log("%s:%d plane_pt (%g %g %g) @ dist (%g)out of tolerance\n",
2084  __FILE__, __LINE__, V3ARGS(plane_pt), dist);
2085  bu_bomb("isect_ray_planar_face() dist out of tol\n");
2086  }
2087 
2088  if (UNLIKELY(RTG.NMG_debug & DEBUG_RT_ISECT)) {
2089  fastf_t new_dist;
2090  bu_log("\tray (%16.10e %16.10e %16.10e) (-> %16.10e %16.10e %16.10e)\n",
2091  rd->rp->r_pt[0],
2092  rd->rp->r_pt[1],
2093  rd->rp->r_pt[2],
2094  rd->rp->r_dir[0],
2095  rd->rp->r_dir[1],
2096  rd->rp->r_dir[2]);
2097  bu_log("\tplane/ray intersection point (%16.10e %16.10e %16.10e)\n",
2098  V3ARGS(plane_pt));
2099  bu_log("\tdistance along ray to intersection point %16.10e\n", dist);
2100 
2101  new_dist=DIST_PT_PLANE(plane_pt, norm);
2102 
2103  bu_log("\tDIST_PT_PLANE(%16.10e) %p %p\n",
2104  new_dist, (void *)plane_pt, (void *)norm);
2105 
2106  bn_isect_line3_plane(&new_dist, plane_pt, rd->rp->r_dir,
2107  norm, rd->tol);
2108 
2109  bu_log("Normal %16.10e %16.10e %16.10e %16.10e)\n",
2110  V4ARGS(norm));
2111  bu_log("recalculated plane/pt dist as %16.10e %p %p\n",
2112  new_dist, (void *)plane_pt, (void *)norm);
2113  bu_log("distance tol = %16.10e\n", rd->tol->dist);
2114  }
2115 
2116 
2117  /* determine if the plane point is in or out of the face, and if
2118  * it is within tolerance of any of the elements of the faceuse.
2119  *
2120  * The value of "rd->face_subhit" will be set non-zero if either
2121  * eu_touch_func or vu_touch_func is called. They will be called
2122  * when an edge/vertex of the face is within tolerance of
2123  * plane_pt.
2124  */
2125  rd->face_subhit = 0;
2126  rd->ray_dist_to_plane = dist;
2127  if (rd->classifying_ray)
2128  pt_class = nmg_class_pt_fu_except(plane_pt, fu_p, (struct loopuse *)NULL,
2129  0, 0, (char *)rd, NMG_FPI_PERGEOM, 1,
2130  rd->tol);
2131  else
2132  pt_class = nmg_class_pt_fu_except(plane_pt, fu_p,
2133  (struct loopuse *)NULL,
2134  (void (*)(struct edgeuse *, point_t, const char *))eu_touch_func,
2135  (void (*)(struct vertexuse *, point_t, const char *))vu_touch_func,
2136  (char *)rd,
2137  NMG_FPI_PERGEOM,
2138  0,
2139  rd->tol);
2140 
2141 
2142  NMG_GET_HITMISS(myhit, rd->ap);
2143  NMG_INDEX_ASSIGN(rd->hitmiss, fu_p->f_p, myhit);
2144  myhit->hit.hit_private = (void *)fu_p->f_p;
2145  myhit->hit.hit_surfno = fu_p->f_p->index;
2146  myhit->inbound_use = myhit->outbound_use = (long *)&fu_p->l.magic;
2147 
2148 
2149  switch (pt_class) {
2150  case NMG_CLASS_Unknown :
2151  bu_log("%s[line:%d] ray/plane intercept point cannot be classified wrt face\n",
2152  __FILE__, __LINE__);
2153  bu_bomb("isect_ray_planar_face() class unknown\n");
2154  break;
2155  case NMG_CLASS_AinB :
2156  case NMG_CLASS_AonBshared :
2157  /* if a sub-element of the face was within tolerance of
2158  * the plane intercept, then a hit has already been
2159  * recorded for that element, and we do NOT need to
2160  * generate one for the face.
2161  */
2162  if (rd->face_subhit) {
2164  VMOVE(myhit->hit.hit_point, plane_pt);
2165  /* also rd->ray_dist_to_plane */
2166  myhit->hit.hit_dist = dist;
2167 
2168  myhit->hit.hit_private = (void *)fu_p->f_p;
2169  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
2170  NMG_CK_HITMISS(myhit);
2171  } else {
2172  /* The plane_pt was NOT within tolerance of a
2173  * sub-element, but it WAS within the area of the
2174  * face. We need to record a hit on the face
2175  */
2176  record_face_hit(rd, myhit, plane_pt, dist, fu_p, norm);
2177  }
2178  break;
2179  case NMG_CLASS_AoutB :
2181  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
2182 
2183  break;
2184  default :
2185  bu_log("%s[line:%d] BIZARRE ray/plane intercept point classification\n",
2186  __FILE__, __LINE__);
2187  bu_bomb("isect_ray_planar_face() Bizz\n");
2188  }
2189 
2190  /* intersect the ray with the edges/vertices of the face */
2191  for (BU_LIST_FOR(lu_p, loopuse, &fu_p->lu_hd))
2192  isect_ray_loopuse(rd, lu_p);
2193 }
2194 
2195 
2196 /**
2197  * check to see if ray hits face.
2198  */
2199 HIDDEN void
2200 isect_ray_faceuse(struct ray_data *rd, struct faceuse *fu_p)
2201 {
2202 
2203  struct hitmiss *myhit;
2204  struct face *fp;
2205  struct face_g_plane *fgp;
2206  vect_t r_dir_unit;
2207 
2208  VMOVE(r_dir_unit, rd->rp->r_dir);
2209  VUNITIZE(r_dir_unit);
2210 
2211  if (fu_p->orientation == OT_OPPOSITE) return;
2212 
2213  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2214  bu_log("isect_ray_faceuse(%p, faceuse:%p/face:%p)\n",
2215  (void *)rd, (void *)fu_p, (void *)fu_p->f_p);
2216 
2217  NMG_CK_FACEUSE(fu_p);
2218  NMG_CK_FACEUSE(fu_p->fumate_p);
2219  fp = fu_p->f_p;
2220  NMG_CK_FACE(fp);
2221 
2222 
2223  /* if this face already processed, we are done. */
2224  myhit = NMG_INDEX_GET(rd->hitmiss, fp);
2225  if (myhit) {
2226  if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit,
2227  NMG_RT_HIT_MAGIC)) {
2228  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2229  bu_log(" previously hit\n");
2230  } else if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit,
2232  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2233  bu_log(" previously hit sub-element\n");
2234  } else if (BU_LIST_MAGIC_EQUAL((struct bu_list *)myhit,
2235  NMG_RT_MISS_MAGIC)) {
2236  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2237  bu_log(" previously missed\n");
2238  } else {
2239  bu_log("%s %d:\n\tBad magic %u (%08x) for hitmiss struct for faceuse %p\n",
2240  __FILE__, __LINE__,
2241  myhit->l.magic, myhit->l.magic, (void *)fu_p);
2242  nmg_bu_bomb(rd, "Was I hit or not?\n");
2243  }
2244  return;
2245  }
2246 
2247 
2248  /* bounding box intersection */
2249  if (*fp->g.magic_p == NMG_FACE_G_PLANE_MAGIC) {
2250  int code;
2251  fastf_t dist;
2252  point_t hit_pt;
2253 
2254  fgp = fu_p->f_p->g.plane_p;
2255  NMG_CK_FACE_G_PLANE(fgp);
2256 
2257  code = bn_isect_line3_plane(&dist, rd->rp->r_pt, rd->rp->r_dir, fgp->N, rd->tol);
2258  if (code < 1) {
2259  NMG_GET_HITMISS(myhit, rd->ap);
2260  NMG_INDEX_ASSIGN(rd->hitmiss, fu_p->f_p, myhit);
2261  myhit->hit.hit_private = (void *)fu_p->f_p;
2262  myhit->hit.hit_surfno = fu_p->f_p->index;
2264  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
2265 
2266  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2267  bu_log("missed bounding box\n");
2268  return;
2269  }
2270  dist *= MAGNITUDE(rd->rp->r_dir);
2271  VJOIN1(hit_pt, rd->rp->r_pt, dist, r_dir_unit);
2272  if (V3PT_OUT_RPP_TOL(hit_pt, fp->min_pt, fp->max_pt, rd->tol->dist)) {
2273  NMG_GET_HITMISS(myhit, rd->ap);
2274  NMG_INDEX_ASSIGN(rd->hitmiss, fu_p->f_p, myhit);
2275  myhit->hit.hit_private = (void *)fu_p->f_p;
2276  myhit->hit.hit_surfno = fu_p->f_p->index;
2278  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
2279 
2280  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2281  bu_log("hit point not within face bounding box\n");
2282  return;
2283  }
2284 
2285  VMOVE(rd->plane_pt, hit_pt);
2286  rd->ray_dist_to_plane = dist;
2287  } else if (!rt_in_rpp(rd->rp, rd->rd_invdir,
2288  fu_p->f_p->min_pt, fu_p->f_p->max_pt)) {
2289  NMG_GET_HITMISS(myhit, rd->ap);
2290  NMG_INDEX_ASSIGN(rd->hitmiss, fu_p->f_p, myhit);
2291  myhit->hit.hit_private = (void *)fu_p->f_p;
2292  myhit->hit.hit_surfno = fu_p->f_p->index;
2294  BU_LIST_INSERT(&rd->rd_miss, &myhit->l);
2295 
2296  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2297  bu_log("missed bounding box\n");
2298  return;
2299  }
2300 
2301  if (RTG.NMG_debug & DEBUG_RT_ISECT) bu_log(" hit bounding box \n");
2302 
2303  switch (*fu_p->f_p->g.magic_p) {
2305  isect_ray_planar_face(rd, fu_p);
2306  break;
2308  isect_ray_snurb_face(rd, fu_p, fu_p->f_p->g.snurb_p);
2309  break;
2310  }
2311 }
2312 
2313 
2314 /**
2315  * Implicit return: adds hit points to the hit-list "hl"
2316  */
2317 HIDDEN void
2318 nmg_isect_ray_shell(struct ray_data *rd, const struct shell *s_p)
2319 {
2320  struct faceuse *fu_p;
2321  struct loopuse *lu_p;
2322  struct edgeuse *eu_p;
2323 
2324  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2325  bu_log("nmg_isect_ray_shell(%p, %p)\n", (void *)rd, (void *)s_p);
2326 
2327  NMG_CK_SHELL(s_p);
2328  NMG_CK_SHELL_A(s_p->sa_p);
2329 
2330  /* does ray isect shell rpp ? if not, we can just return. there
2331  * is no need to record the miss for the shell, as there is only
2332  * one "use" of a shell.
2333  */
2334  if (!rt_in_rpp(rd->rp, rd->rd_invdir,
2335  s_p->sa_p->min_pt, s_p->sa_p->max_pt)) {
2336  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2337  bu_log("nmg_isect_ray_shell(no RPP overlap) %p, %p\n", (void *)rd, (void *)s_p);
2338  return;
2339  }
2340 
2341  /* ray intersects shell, check sub-objects */
2342 
2343  for (BU_LIST_FOR(fu_p, faceuse, &(s_p->fu_hd)))
2344  isect_ray_faceuse(rd, fu_p);
2345 
2346  for (BU_LIST_FOR(lu_p, loopuse, &(s_p->lu_hd)))
2347  isect_ray_loopuse(rd, lu_p);
2348 
2349  for (BU_LIST_FOR(eu_p, edgeuse, &(s_p->eu_hd)))
2350  isect_ray_edgeuse(rd, eu_p);
2351 
2352  if (s_p->vu_p)
2353  (void)isect_ray_vertexuse(rd, s_p->vu_p);
2354 
2355  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2356  bu_log("nmg_isect_ray_shell(done) %p, %p\n", (void *)rd, (void *)s_p);
2357 }
2358 
2359 
2360 void
2362 {
2363  struct nmgregion *r_p;
2364  struct shell *s_p;
2365 
2366  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2367  bu_log("isect_ray_nmg: Pnt(%g %g %g) Dir(%g %g %g)\n",
2368  rd->rp->r_pt[0],
2369  rd->rp->r_pt[1],
2370  rd->rp->r_pt[2],
2371  rd->rp->r_dir[0],
2372  rd->rp->r_dir[1],
2373  rd->rp->r_dir[2]);
2374 
2375  NMG_CK_MODEL(rd->rd_m);
2377 
2378  /* Caller has assured us that the ray intersects the nmg model,
2379  * check ray for intersection with rpp's of nmgregion's
2380  */
2381  for (BU_LIST_FOR(r_p, nmgregion, &rd->rd_m->r_hd)) {
2382  NMG_CK_REGION(r_p);
2383  NMG_CK_REGION_A(r_p->ra_p);
2384 
2385  /* does ray intersect nmgregion rpp? */
2386  if (! rt_in_rpp(rd->rp, rd->rd_invdir,
2387  r_p->ra_p->min_pt, r_p->ra_p->max_pt))
2388  continue;
2389 
2390  /* ray intersects region, check shell intersection */
2391  for (BU_LIST_FOR(s_p, shell, &r_p->s_hd)) {
2392  nmg_isect_ray_shell(rd, s_p);
2393  }
2394  }
2395 
2396  if (RTG.NMG_debug & DEBUG_RT_ISECT) {
2397  if (BU_LIST_IS_EMPTY(&rd->rd_hit)) {
2398  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2399  bu_log("ray missed NMG\n");
2400  } else {
2401  if (RTG.NMG_debug & DEBUG_RT_ISECT)
2403  }
2404  }
2405 
2406  /* sanity check */
2408 }
2409 
2410 
2411 void
2412 nmg_pl_hitmiss_list(const char *str, int num, const struct bu_list *hd, const struct xray *rp)
2413 {
2414  FILE *fp;
2415  char buf[128];
2416  struct hitmiss *hmp;
2417  int count = 0;
2418 
2419  snprintf(buf, 128, "%s%d.plot3", str, num);
2420 
2421  if (bu_list_len(hd) <= 0) {
2422  bu_log("nmg_pl_hitmiss_list(): empty list, no %s written\n", buf);
2423  return;
2424  }
2425 
2426  fp = fopen(buf, "wb");
2427  if (fp == (FILE *)NULL) {
2428  perror(buf);
2429  return;
2430  }
2431 
2432  pl_color(fp, 210, 210, 210); /* grey ray */
2433 
2434  for (BU_LIST_FOR(hmp, hitmiss, hd)) {
2435  point_t pt;
2436 
2437  NMG_CK_HITMISS(hmp);
2438 
2439  VJOIN1(pt, rp->r_pt, hmp->hit.hit_dist, rp->r_dir);
2440  if (count++)
2441  pdv_3cont(fp, pt);
2442  else
2443  pdv_3move(fp, pt);
2444  }
2445  fclose(fp);
2446  bu_log("overlay %s\n", buf);
2447 }
2448 
2449 
2450 HIDDEN int
2451 guess_class_from_hitlist_max(struct ray_data *rd, int *hari_kari, int in_or_out_only)
2452 {
2453  struct hitmiss *a_hit;
2454  struct hitmiss *plus_hit = (struct hitmiss *)NULL;
2455  int pt_class;
2456 
2457  *hari_kari = 0;
2458 
2459  NMG_CK_RD(rd);
2460  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2461  bu_log("plus guessing\n");
2462 
2463  for (BU_LIST_FOR(a_hit, hitmiss, &rd->rd_hit)) {
2464  NMG_CK_HITMISS(a_hit);
2465 
2466  if (!in_or_out_only) {
2467  /* if we've got a zero distance hit, that clinches it */
2468  if (NEAR_ZERO(a_hit->hit.hit_dist, rd->tol->dist)) {
2469  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2470  bu_log("guess_class_from_hitlist_min() returns NMG_CLASS_AonBshared for 0 dist hit\n");
2471  return NMG_CLASS_AonBanti;
2472  }
2473 
2474  if (a_hit->hit.hit_dist < -rd->tol->dist)
2475  continue;
2476  } else if (a_hit->hit.hit_dist < rd->tol->dist)
2477  continue;
2478 
2479  if (a_hit->in_out == HMG_HIT_ANY_ANY)
2480  continue;
2481 
2482  if (plus_hit == (struct hitmiss *)NULL) {
2483  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2484  bu_log("plus hit = %g (%s)\n", a_hit->hit.hit_dist,
2485  nmg_rt_inout_str(a_hit->in_out));
2486  plus_hit = a_hit;
2487  *hari_kari = 0;
2488  } else if (a_hit->hit.hit_dist < plus_hit->hit.hit_dist) {
2489  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2490  bu_log("plus hit = %g (%s)\n", a_hit->hit.hit_dist,
2491  nmg_rt_inout_str(a_hit->in_out));
2492  plus_hit = a_hit;
2493  *hari_kari = 0;
2494  } else if (ZERO(a_hit->hit.hit_dist - plus_hit->hit.hit_dist)) {
2495  *hari_kari = 1;
2496  }
2497  }
2498 
2499  /* XXX This needs to be resolved with parity */
2500  if (*hari_kari) {
2501  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2502  bu_log("Contemplating Hari Kari\n");
2503  return NMG_CLASS_Unknown;
2504  }
2505  /* figure out what the status is from plus_hit */
2506  if (plus_hit) {
2507  switch (plus_hit->in_out) {
2508  case HMG_HIT_IN_IN:
2509  case HMG_HIT_IN_OUT:
2510  case HMG_HIT_IN_ON:
2511  pt_class = NMG_CLASS_AinB;
2512  break;
2513  case HMG_HIT_OUT_IN:
2514  case HMG_HIT_OUT_OUT:
2515  case HMG_HIT_OUT_ON:
2516  pt_class = NMG_CLASS_AoutB;
2517  break;
2518  case HMG_HIT_ON_IN:
2519  case HMG_HIT_ON_ON:
2520  case HMG_HIT_ON_OUT:
2521  pt_class = NMG_CLASS_AonBanti;
2522  break;
2523  default:
2524  pt_class = NMG_CLASS_Unknown;
2525  break;
2526  }
2527  } else {
2528  /* since we didn't hit anything in the positive direction,
2529  * we've got to be outside, since we don't allow infinite
2530  * NMG's
2531  */
2532  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2533  bu_log("Nothing in the plus direction\n");
2534  pt_class = NMG_CLASS_AoutB;
2535  }
2536 
2537  return pt_class;
2538 }
2539 
2540 
2541 HIDDEN int
2542 guess_class_from_hitlist_min(struct ray_data *rd, int *hari_kari, int in_or_out_only)
2543 {
2544  struct hitmiss *a_hit;
2545  struct hitmiss *minus_hit = (struct hitmiss *)NULL;
2546  int pt_class;
2547 
2548  *hari_kari = 0;
2549 
2550  NMG_CK_RD(rd);
2551  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2552  bu_log("minus guessing\n");
2553 
2554  for (BU_LIST_FOR(a_hit, hitmiss, &rd->rd_hit)) {
2555  NMG_CK_HITMISS(a_hit);
2556 
2557  if (!in_or_out_only) {
2558  /* if we've got a zero distance hit, that clinches it */
2559  if (NEAR_ZERO(a_hit->hit.hit_dist, rd->tol->dist)) {
2560  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2561  bu_log("guess_class_from_hitlist_min() returns NMG_CLASS_AonBshared for 0 dist hit\n");
2562  return NMG_CLASS_AonBanti;
2563  }
2564 
2565  if (a_hit->hit.hit_dist > rd->tol->dist)
2566  continue;
2567  } else if (a_hit->hit.hit_dist > -(rd->tol->dist))
2568  continue;
2569 
2570  if (a_hit->in_out == HMG_HIT_ANY_ANY)
2571  continue;
2572 
2573  if (minus_hit == (struct hitmiss *)NULL) {
2574  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2575  bu_log("minus hit = %g (%s)\n", a_hit->hit.hit_dist,
2576  nmg_rt_inout_str(a_hit->in_out));
2577  minus_hit = a_hit;
2578  *hari_kari = 0;
2579  } else if (a_hit->hit.hit_dist > minus_hit->hit.hit_dist) {
2580  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2581  bu_log("minus hit = %g (%s)\n", a_hit->hit.hit_dist,
2582  nmg_rt_inout_str(a_hit->in_out));
2583  minus_hit = a_hit;
2584  *hari_kari = 0;
2585  } else if (ZERO(a_hit->hit.hit_dist - minus_hit->hit.hit_dist)) {
2586  *hari_kari = 1;
2587  }
2588  }
2589 
2590  /* XXX This needs to be resolved with parity */
2591  if (*hari_kari) {
2592  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2593  bu_log("Contemplating Hari Kari\n");
2594  return NMG_CLASS_Unknown;
2595  }
2596 
2597  /* figure out what the status is from plus_hit */
2598  if (minus_hit) {
2599  switch (minus_hit->in_out) {
2600  case HMG_HIT_IN_IN:
2601  case HMG_HIT_OUT_IN:
2602  case HMG_HIT_ON_IN:
2603  pt_class = NMG_CLASS_AinB;
2604  break;
2605  case HMG_HIT_OUT_OUT:
2606  case HMG_HIT_IN_OUT:
2607  case HMG_HIT_ON_OUT:
2608  pt_class = NMG_CLASS_AoutB;
2609  break;
2610  case HMG_HIT_ON_ON:
2611  case HMG_HIT_OUT_ON:
2612  case HMG_HIT_IN_ON:
2613  pt_class = NMG_CLASS_AonBanti;
2614  break;
2615  default:
2616  pt_class = NMG_CLASS_Unknown;
2617  break;
2618  }
2619  } else {
2620  /* since we didn't hit anything in this direction,
2621  * we've got to be outside, since we don't allow infinite
2622  * NMG's
2623  */
2624  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2625  bu_log("Nothing in the minus direction\n");
2626  pt_class = NMG_CLASS_AoutB;
2627  }
2628 
2629  return pt_class;
2630 }
2631 
2632 
2633 /**
2634  * Intended as a support routine for nmg_class_pt_s() in nmg_class.c
2635  *
2636  * Intersect a ray with a shell, and return whether the ray start
2637  * point is inside or outside or ON the shell. Count the number of
2638  * crossings (hit points) along the ray, both in the negative and
2639  * positive directions. If an even number, point is outside, if an
2640  * odd number point is inside. If the negative-going and
2641  * positive-going assessments don't agree, this is a problem.
2642  *
2643  * If "in_or_out_only" is non-zero, then we will not look for a
2644  * classification of "ON" the shell.
2645  *
2646  * The caller must be prepared for a return of NMG_CLASS_Unknown, in
2647  * which case it should pick a less difficult ray direction to fire
2648  * and try again.
2649  *
2650  * Returns NMG_CLASS_Unknown if we can't tell or NMG_CLASS_xxx for the
2651  * classification of the pt w.r.t. the shell.
2652  */
2653 int
2654 nmg_class_ray_vs_shell(struct xray *rp, const struct shell *s, const int in_or_out_only, const struct bn_tol *tol)
2655 {
2656  struct ray_data rd;
2657  struct application ap;
2658  struct hitmiss *a_hit;
2659  int minus_class, plus_class;
2660  int hari_kari_minus, hari_kari_plus;
2661 
2662  NMG_CK_SHELL(s);
2663  BN_CK_TOL(tol);
2664 
2665  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT)) {
2666  bu_log("nmg_class_ray_vs_shell(pt(%g %g %g), dir(%g %g %g))\n",
2667  V3ARGS(rp->r_pt), V3ARGS(rp->r_dir));
2668  }
2669 
2670  RT_APPLICATION_INIT(&ap);
2671  ap.a_resource = &rt_uniresource;
2672 
2675 
2676  rd.rd_m = nmg_find_model(&s->l.magic);
2677 
2678  /* If there is a manifolds list attached to the model structure
2679  * then use it, otherwise create a manifolds list to be used once
2680  * in this function and then freed in this function.
2681  */
2682  if (rd.rd_m->manifolds) {
2683  rd.manifolds = rd.rd_m->manifolds;
2684  } else {
2685  rd.manifolds = nmg_manifolds(rd.rd_m);
2686  }
2687 
2688  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT)) {
2689  struct faceuse *fu;
2690 
2691  bu_log("Manifoldness for shell FU's\n");
2692  for (BU_LIST_FOR(fu, faceuse, &s->fu_hd)) {
2693  if (fu->orientation != OT_SAME)
2694  continue;
2695 
2696  bu_log("fu %p: %d\n", (void *)fu, NMG_MANIFOLDS(rd.manifolds, fu));
2697  }
2698  }
2699 
2700  /* Compute the inverse of the direction cosines */
2701  if (!ZERO(rp->r_dir[X])) {
2702  rd.rd_invdir[X]=1.0/rp->r_dir[X];
2703  } else {
2704  rd.rd_invdir[X] = INFINITY;
2705  rp->r_dir[X] = 0.0;
2706  }
2707  if (!ZERO(rp->r_dir[Y])) {
2708  rd.rd_invdir[Y]=1.0/rp->r_dir[Y];
2709  } else {
2710  rd.rd_invdir[Y] = INFINITY;
2711  rp->r_dir[Y] = 0.0;
2712  }
2713  if (!ZERO(rp->r_dir[Z])) {
2714  rd.rd_invdir[Z]=1.0/rp->r_dir[Z];
2715  } else {
2716  rd.rd_invdir[Z] = INFINITY;
2717  rp->r_dir[Z] = 0.0;
2718  }
2719 
2720  rd.rp = rp;
2721  rd.tol = tol;
2722  rd.ap = &ap;
2723  rd.stp = (struct soltab *)NULL;
2724  rd.seghead = (struct seg *)NULL;
2726  rd.hitmiss = (struct hitmiss **)bu_calloc(rd.rd_m->maxindex,
2727  sizeof(struct hitmiss *), "nmg geom hit list");
2728  rd.classifying_ray = 1;
2729 
2730  /* initialize the lists of things that have been hit/missed */
2731  BU_LIST_INIT(&rd.rd_hit);
2732  BU_LIST_INIT(&rd.rd_miss);
2733 
2734  nmg_isect_ray_shell(&rd, s);
2735  NMG_FREE_HITLIST(&rd.rd_miss, &ap);
2736 
2737  /* count the number of hits */
2738  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT)) {
2739  bu_log("%s[%d]: shell Hits:\n", __FILE__, __LINE__);
2740  for (BU_LIST_FOR(a_hit, hitmiss, &rd.rd_hit)) {
2741  if (a_hit->hit.hit_dist > -SMALL_FASTF)
2742  bu_log("Positive dist hit\n");
2743  else
2744  bu_log("Negative dist hit\n");
2745  nmg_rt_print_hitmiss(a_hit);
2746  }
2747  }
2748 
2749  if ((RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT)) &&
2750  (RTG.NMG_debug & (DEBUG_PLOTEM))) {
2751  static int num=0;
2752  nmg_pl_hitmiss_list("shell-ray", num++, &rd.rd_hit, rp);
2753  }
2754 
2755  minus_class = guess_class_from_hitlist_min(&rd, &hari_kari_minus, in_or_out_only);
2756  plus_class = guess_class_from_hitlist_max(&rd, &hari_kari_plus, in_or_out_only);
2757 
2758  if (minus_class != plus_class) {
2759  bu_log("minus_class = (%s)\n", nmg_class_name(minus_class));
2760  bu_log("plus_class = (%s)\n", nmg_class_name(plus_class));
2761  }
2762 
2763  /*
2764  * Rather than blowing up, or guessing, just report that it didn't
2765  * work, and let caller try another direction.
2766  */
2767  if (hari_kari_minus || hari_kari_plus) {
2768  if (RTG.NMG_debug)
2769  bu_log("hari_kari = %d, %d\n", hari_kari_minus, hari_kari_plus);
2770  plus_class = NMG_CLASS_Unknown;
2771  } else if (plus_class != minus_class || minus_class == NMG_CLASS_Unknown) {
2772  plus_class = NMG_CLASS_Unknown;
2773  }
2774 
2775  NMG_FREE_HITLIST(&rd.rd_hit, &ap);
2776 
2777  /* free the hitmiss freelist, filled during NMG_FREE_HITLIST */
2779  struct hitmiss *hitp;
2780  while (BU_LIST_WHILE(hitp, hitmiss, &rt_uniresource.re_nmgfree)) {
2781  NMG_CK_HITMISS(hitp);
2782  BU_LIST_DEQUEUE((struct bu_list *)hitp);
2783  bu_free((void *)hitp, "struct hitmiss");
2784  }
2785  }
2786 
2787  /* free the hitmiss table */
2788  bu_free((char *)rd.hitmiss, "free nmg geom hit list");
2789 
2790  if (!rd.rd_m->manifolds) {
2791  /* If there is no manifolds list attached to the model
2792  * structure then the list was created here (within
2793  * nmg_class_ray_vs_shell) and should be freed here.
2794  * If there is a manifold list attached to the model
2795  * structure then it was created in the nmg_bool
2796  * function and should be freed in the nmg_bool
2797  * function.
2798  */
2799  bu_free((char *)rd.manifolds, "free local manifolds table");
2800  rd.manifolds = NULL; /* sanity */
2801  }
2802 
2803  if (RTG.NMG_debug & (DEBUG_CLASSIFY|DEBUG_RT_ISECT))
2804  bu_log("nmg_class_ray_vs_shell() returns %s(%d)\n",
2805  nmg_class_name(plus_class), plus_class);
2806 
2807 
2808  return plus_class;
2809 }
2810 
2811 
2812 /*
2813  * Local Variables:
2814  * mode: C
2815  * tab-width: 8
2816  * indent-tabs-mode: t
2817  * c-file-style: "stroustrup"
2818  * End:
2819  * ex: shiftwidth=4 tabstop=8
2820  */
void isect_ray_lseg(struct ray_data *rd, struct edgeuse *eu_p)
#define HMG_HIT_OUT_OUT
edge/vertex graze
Definition: raytrace.h:2318
#define BU_LIST_PNEXT_CIRC(structure, p)
Definition: list.h:442
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
int face_subhit
Definition: raytrace.h:2448
uint32_t hit_magic
Definition: raytrace.h:249
const struct bn_tol * tol
Definition: raytrace.h:2421
#define NMG_EDGEUSE_MAGIC
Definition: magic.h:120
HIDDEN void pleu(struct edgeuse *eu, fastf_t *pt, fastf_t *plane_pt)
Definition: nmg_rt_isect.c:166
void rt_nurb_free_snurb(struct face_g_snurb *srf, struct resource *res)
Definition: nurb_util.c:127
void nmg_pl_hitmiss_list(const char *str, int num, const struct bu_list *hd, const struct xray *rp)
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_LIST_INSERT(old, new)
Definition: list.h:183
struct faceuse * nmg_find_fu_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:270
#define NMG_VERT_LEAVE
Definition: raytrace.h:2328
#define NMG_RT_HIT_MAGIC
Definition: magic.h:138
point_t plane_pt
ray/plane(face) intercept point
Definition: raytrace.h:2432
int bn_isect_line3_plane(fastf_t *dist, const point_t pt, const vect_t dir, const plane_t plane, const struct bn_tol *tol)
fastf_t ray_dist_to_plane
ray parametric dist to plane
Definition: raytrace.h:2438
int bn_isect_line_lseg(fastf_t *t, const point_t p, const vect_t d, const point_t a, const point_t b, const struct bn_tol *tol)
Intersect a line in parametric form:
Definition: list.h:118
void * hit_private
PRIVATE handle for xxx_shot()
Definition: raytrace.h:254
#define NMG_CK_RD(_rd)
Definition: raytrace.h:2462
#define HMG_HIT_OUT_IN
breaking in
Definition: raytrace.h:2317
void pdv_3move(register FILE *plotfp, const fastf_t *pt)
Definition: plot3.c:618
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
HIDDEN void record_face_hit(struct ray_data *rd, struct hitmiss *myhit, fastf_t *plane_pt, double dist, struct faceuse *fu_p, fastf_t *norm)
#define HMG_HIT_OUT_ON
Definition: raytrace.h:2322
#define NMG_FACE_G_SNURB_MAGIC
Definition: magic.h:126
if lu s
Definition: nmg_mod.c:3860
long * outbound_use
Definition: raytrace.h:2343
Definition: clone.c:90
struct soltab * stp
Definition: raytrace.h:2420
#define HMG_HIT_IN_IN
hit internal structure
Definition: raytrace.h:2315
lu
Definition: nmg_mod.c:3855
#define VSETALL(a, s)
Definition: color.c:54
Definition: raytrace.h:215
#define BU_LIST_IS_EMPTY(hp)
Definition: list.h:295
#define HIT_EDGE_VERTEX(rd, eu_p, vu_p)
Definition: raytrace.h:368
int rt_nurb_bezier(struct bu_list *bezier_hd, const struct face_g_snurb *orig_surf, struct resource *res)
Definition: nurb_bezier.c:53
#define BU_LIST_IS_INITIALIZED(_hp)
Definition: list.h:175
#define NMG_HITMISS_SEG_OUT
"out"
Definition: raytrace.h:2332
#define BU_LIST_MAGIC_SET(_l, _magic)
Definition: list.h:129
HIDDEN void nmg_isect_ray_shell(struct ray_data *rd, const struct shell *s_p)
#define SMALL_FASTF
Definition: defines.h:342
void nmg_isect_ray_model(struct ray_data *rd)
void nmg_model_bb(fastf_t *min_pt, fastf_t *max_pt, const struct model *m)
Definition: nmg_info.c:166
uint32_t magic
Definition: raytrace.h:2413
long * inbound_use
Definition: raytrace.h:2341
#define nmg_bu_bomb(rd, str)
Definition: raytrace.h:2487
struct bu_list rd_hit
list of hit elements
Definition: raytrace.h:2423
struct bu_list re_nmgfree
head of NMG hitmiss freelist
Definition: raytrace.h:1454
vect_t inbound_norm
Definition: raytrace.h:2342
Header file for the BRL-CAD common definitions.
struct resource * a_resource
dynamic memory resources
Definition: raytrace.h:1591
void isect_ray_snurb_face(struct ray_data *rd, struct faceuse *fu, struct face_g_snurb *fg)
int rt_in_rpp(struct xray *rp, const fastf_t *invdir, const fastf_t *min, const fastf_t *max)
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
#define MAX_FASTF
Definition: defines.h:340
#define HMG_INBOUND_STATE(_hm)
Definition: raytrace.h:2306
char * manifolds
structure 1-3manifold table
Definition: raytrace.h:2415
void pl_erase(register FILE *plotfp)
Definition: plot3.c:271
#define HIDDEN
Definition: common.h:86
NMG_CK_LOOPUSE(lu)
#define NMG_VERT_ENTER
Definition: raytrace.h:2326
#define NMG_RAY_STATE_ANY
Definition: raytrace.h:2313
HIDDEN void isect_ray_planar_face(struct ray_data *rd, struct faceuse *fu_p)
if(share_geom)
Definition: nmg_mod.c:3829
struct bu_list l
Definition: raytrace.h:2335
char * nmg_manifolds(struct model *m)
Definition: nmg_manif.c:413
HIDDEN int guess_class_from_hitlist_min(struct ray_data *rd, int *hari_kari, int in_or_out_only)
Definition: color.c:49
HIDDEN void nmg_rt_isect_plfu(struct faceuse *fu, fastf_t *pt, fastf_t *plane_pt)
Definition: nmg_rt_isect.c:127
struct resource rt_uniresource
default. Defined in librt/globals.c
Definition: globals.c:41
void nmg_pl_fu(FILE *fp, const struct faceuse *fu, long *b, int red, int green, int blue)
Definition: nmg_plot.c:722
void pd_3space(register FILE *plotfp, double px1, double py1, double pz1, double px2, double py2, double pz2)
Definition: plot3.c:580
#define NMG_RAY_STATE_ON
Definition: raytrace.h:2311
struct hitmiss ** hitmiss
1 struct hitmiss ptr per elem.
Definition: raytrace.h:2422
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
#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_pl_eu(FILE *fp, const struct edgeuse *eu, long *b, int red, int green, int blue)
Definition: nmg_plot.c:658
#define NMG_RAY_STATE_OUTSIDE
Definition: raytrace.h:2312
struct model * rd_m
Definition: raytrace.h:2414
void rt_nurb_s_norm(struct face_g_snurb *srf, fastf_t u, fastf_t v, fastf_t *norm)
Definition: nurb_norm.c:44
const char * nmg_rt_inout_str(int code)
Definition: nmg_rt_isect.c:48
HIDDEN void edge_hit_ray_state(struct ray_data *rd, struct edgeuse *eu, struct hitmiss *myhit)
#define NMG_RAY_DATA_MAGIC
Definition: magic.h:135
double bn_dist_line3_pt3(const point_t pt, const vect_t dir, const point_t a)
#define V3ARGS(a)
Definition: color.c:56
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
HIDDEN void isect_ray_faceuse(struct ray_data *rd, struct faceuse *fu_p)
point_t hit_point
DEPRECATED: Intersection point, use VJOIN1 hit_dist.
Definition: raytrace.h:251
void nmg_rt_print_hitmiss(struct hitmiss *a_hit)
Definition: nmg_rt_isect.c:211
vect_t rd_invdir
Definition: raytrace.h:2416
void nmg_rt_print_hitlist(struct bu_list *hd)
Definition: nmg_rt_isect.c:234
#define NMG_RT_HIT_SUB_MAGIC
Definition: magic.h:139
void pdv_3cont(register FILE *plotfp, const fastf_t *pt)
Definition: plot3.c:630
void pl_label(register FILE *plotfp, const char *s)
Definition: plot3.c:244
oldeumate l2 magic
Definition: nmg_mod.c:3843
HIDDEN void isect_ray_loopuse(struct ray_data *rd, struct loopuse *lu_p)
HIDDEN void isect_ray_edgeuse(struct ray_data *rd, struct edgeuse *eu_p)
#define UNUSED(parameter)
Definition: common.h:239
#define NMG_HIT_LIST
Definition: raytrace.h:2299
vect_t outbound_norm
Definition: raytrace.h:2344
#define NMG_CK_HITMISS(hm)
Definition: raytrace.h:2356
struct faceuse * nmg_find_fu_of_vu(const struct vertexuse *vu)
Definition: nmg_info.c:304
Support for uniform tolerances.
Definition: tol.h:71
struct shell * nmg_find_s_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:235
#define BN_CK_TOL(_p)
Definition: tol.h:82
#define BU_LIST_FIRST_MAGIC(hp)
Definition: list.h:416
int nmg_find_eu_leftvec(fastf_t *left, const struct edgeuse *eu)
Definition: nmg_info.c:1274
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
uint32_t magic
Magic # for mem id/check.
Definition: list.h:119
#define BU_LIST_WHILE(p, structure, hp)
Definition: list.h:410
void pl_color(register FILE *plotfp, int r, int g, int b)
Definition: plot3.c:325
#define NMG_FACE_G_PLANE_MAGIC
Definition: magic.h:125
vect_t r_dir
Direction of ray (UNIT Length)
Definition: raytrace.h:219
void pdv_3line(register FILE *plotfp, const fastf_t *a, const fastf_t *b)
Definition: plot3.c:642
#define HMG_HIT_IN_ON
Definition: raytrace.h:2319
int in_out
status of ray as it transitions this hit point.
Definition: raytrace.h:2338
int classifying_ray
Definition: raytrace.h:2455
HIDDEN int guess_class_from_hitlist_max(struct ray_data *rd, int *hari_kari, int in_or_out_only)
oldeumate e_p eu_p
Definition: nmg_mod.c:3940
int nmg_uv_in_lu(const fastf_t u, const fastf_t v, const struct loopuse *lu)
Definition: nurb_trim.c:497
#define BU_LIST_PPREV_CIRC(structure, p)
Definition: list.h:450
#define BN_VECT_ARE_PERP(_dot, _tol)
Definition: tol.h:122
#define HMG_HIT_IN_OUT
breaking out
Definition: raytrace.h:2316
HIDDEN void eu_touch_func(struct edgeuse *eu, fastf_t *pt, char *priv)
double perp
nearly 0
Definition: tol.h:75
HIDDEN void get_pole_dist_to_face(struct ray_data *rd, struct vertexuse *vu, fastf_t *Pole, fastf_t *Pole_prj_pt, double *Pole_dist, fastf_t *Pole_pca, fastf_t *pointA, fastf_t *leftA, fastf_t *pointB, fastf_t *leftB, fastf_t *polar_height_vect, char *Pole_name)
Definition: nmg_rt_isect.c:348
#define NMG_VERT_UNKNOWN
Definition: raytrace.h:2329
#define NMG_EDGE_G_LSEG_MAGIC
Definition: magic.h:122
#define ZERO(val)
Definition: units.c:38
#define BU_LIST_INIT(_hp)
Definition: list.h:148
HIDDEN int code(fastf_t x, fastf_t y)
Definition: clip.c:43
point_t r_pt
Point at which ray starts.
Definition: raytrace.h:218
#define NMG_RAY_STATE_INSIDE
Definition: raytrace.h:2310
#define UV_TOL
int hit(struct application *ap, struct partition *PartHeadp, struct seg *segs)
Definition: gqa.c:963
#define NMG_EDGE_G_CNURB_MAGIC
Definition: magic.h:121
#define HMG_HIT_ON_ON
Definition: raytrace.h:2321
HIDDEN void ray_hit_vertex(struct ray_data *rd, struct vertexuse *vu_p, int status)
Definition: nmg_rt_isect.c:960
void bn_vec_ortho(vect_t out, const vect_t in)
HIDDEN void ray_hit_edge(struct ray_data *rd, struct edgeuse *eu_p, double dist_along_ray, fastf_t *pt)
#define HMG_HIT_ON_OUT
Definition: raytrace.h:2323
int nmg_class_ray_vs_shell(struct xray *rp, const struct shell *s, const int in_or_out_only, const struct bn_tol *tol)
#define NMG_RT_MISS_MAGIC
Definition: magic.h:140
void rt_nurb_s_eval(const struct face_g_snurb *srf, fastf_t u, fastf_t v, fastf_t *final_value)
Definition: nurb_eval.c:49
struct hitmiss * other
for keeping track of the other end of the segment when we know it
Definition: raytrace.h:2346
int bu_list_len(const struct bu_list *hd)
#define NMG_GET_HITMISS(_p, _ap)
Definition: raytrace.h:2465
struct hit hit
Definition: raytrace.h:2336
int bn_dist_pt3_lseg3(fastf_t *dist, point_t pca, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Find the distance from a point P to a line segment described by the two endpoints A and B...
Definition: color.c:51
void nmg_ck_hitmiss_list(const struct bu_list *hd)
Definition: nmg_rt_isect.c:95
HIDDEN void vu_touch_func(struct vertexuse *vu, fastf_t *pt, char *priv)
int hit_surfno
solid-specific surface indicator
Definition: raytrace.h:255
#define NMG_HITMISS_SEG_IN
"in"
Definition: raytrace.h:2331
#define NMG_CK_HITMISS_LISTS(rd)
Definition: raytrace.h:2384
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
vect_t hit_normal
DEPRECATED: Surface Normal at hit_point, use RT_HIT_NORMAL.
Definition: raytrace.h:252
struct xray * rp
Definition: raytrace.h:2417
struct application * ap
Definition: raytrace.h:2418
const char * nmg_class_name(int nmg_class)
Definition: nmg_eval.c:122
HIDDEN void vertex_neighborhood(struct ray_data *rd, struct vertexuse *vu_p, struct hitmiss *myhit)
Definition: nmg_rt_isect.c:707
NMG_CK_SHELL(s)
#define NMG_FREE_HITLIST(_p, _ap)
Definition: raytrace.h:2474
struct bu_list rd_miss
list of missed/sub-hit elements
Definition: raytrace.h:2424
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
HIDDEN void hit_ins(struct ray_data *rd, struct hitmiss *newhit)
Definition: nmg_rt_isect.c:251
#define BU_LIST_MAGIC_EQUAL(_l, _magic)
Definition: list.h:135
int start_stop
is this a seg_in or seg_out
Definition: raytrace.h:2345
HIDDEN int isect_ray_vertexuse(struct ray_data *rd, struct vertexuse *vu_p)
struct rt_nurb_uv_hit * rt_nurb_intersect(const struct face_g_snurb *srf, fastf_t *plane1, fastf_t *plane2, double uv_tol, struct resource *res, struct bu_list *plist)
Definition: nurb_ray.c:322
#define RT_APPLICATION_INIT(_p)
Definition: raytrace.h:1676
fastf_t hit_dist
dist from r_pt to hit_point
Definition: raytrace.h:250
#define HMG_HIT_ON_IN
Definition: raytrace.h:2320
const char * nmg_rt_state_str(int code)
Definition: nmg_rt_isect.c:75
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
fastf_t dist_in_plane
distance from plane intersect
Definition: raytrace.h:2337
const char * bu_identify_magic(uint32_t magic)
char * nmg_orientation(int orientation)
Definition: nmg_pr.c:50
HIDDEN struct hitmiss * ray_miss_vertex(struct ray_data *rd, struct vertexuse *vu_p)
Definition: nmg_rt_isect.c:293
struct seg * seghead
Definition: raytrace.h:2419
#define BU_LIST_NOT_HEAD(p, hp)
Definition: list.h:324
HIDDEN void colinear_edge_ray(struct ray_data *rd, struct edgeuse *eu_p)
#define HMG_OUTBOUND_STATE(_hm)
Definition: raytrace.h:2307
#define HMG_HIT_ANY_ANY
hit on non-3-manifold
Definition: raytrace.h:2324
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
int rt_nurb_s_bound(struct face_g_snurb *srf, fastf_t *bmin, fastf_t *bmax)
Definition: nurb_bound.c:48
#define RT_HIT_MAGIC
Definition: magic.h:161
HIDDEN void plot_neighborhood(fastf_t *North_Pole, fastf_t *North_pl_pt, fastf_t *North_pca, fastf_t *South_Pole, fastf_t *South_pl_pt, fastf_t *South_pca, fastf_t *pointA, fastf_t *pointB, fastf_t *norm, fastf_t *pt, fastf_t *leftA, fastf_t *leftB)
Definition: nmg_rt_isect.c:573
#define UNLIKELY(expression)
Definition: common.h:282
struct rt_g RTG
Definition: globals.c:39
struct model * nmg_find_model(const uint32_t *magic_p_arg)
Definition: nmg_info.c:57