BRL-CAD
bool.c
Go to the documentation of this file.
1 /* B O O L . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1985-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 ray */
21 /** @{ */
22 /** @file librt/bool.c
23  *
24  * Ray Tracing program, Boolean region evaluator.
25  *
26  * Note to developers -
27  * Do not use the hit_point field in these routines, as for some solid
28  * types it has been filled in by the g_xxx_shot() routine, and for
29  * other solid types it may not have been. In particular, copying a
30  * garbage hit_point from a structure which has not yet been filled
31  * in, into a structure which won't be filled in again, gives wrong
32  * results. Thanks to Keith Bowman for finding this obscure bug.
33  *
34  */
35 /** @} */
36 
37 #include "common.h"
38 
39 #include <string.h>
40 #include "bio.h"
41 
42 #include "bu/parallel.h"
43 #include "vmath.h"
44 #include "raytrace.h"
45 
46 
47 
48 /* Boolean values. Not easy to change, but defined symbolically */
49 #define BOOL_FALSE 0
50 #define BOOL_TRUE 1
51 
52 
53 /**
54  * If a zero thickness segment abuts another partition, it will be
55  * fused in, later.
56  *
57  * If it is free standing, then it will remain as a zero thickness
58  * partition, which probably signals going through some solid an odd
59  * number of times, or hitting an NMG wire edge or NMG lone vertex.
60  */
61 void
62 rt_weave0seg(struct seg *segp, struct partition *PartHdp, struct application *ap)
63 {
64  register struct partition *pp;
65  struct resource *res = ap->a_resource;
66  struct rt_i *rtip = ap->a_rt_i;
67  register fastf_t tol_dist;
68 
69  tol_dist = rtip->rti_tol.dist;
70 
71  RT_CK_PT_HD(PartHdp);
72  RT_CK_RTI(ap->a_rt_i);
73  RT_CK_RESOURCE(res);
74  RT_CK_RTI(rtip);
75 
77  bu_log(
78  "rt_weave0seg: Zero thickness seg: %s (%.18e, %.18e) %d, %d\n",
79  segp->seg_stp->st_name,
80  segp->seg_in.hit_dist,
81  segp->seg_out.hit_dist,
82  segp->seg_in.hit_surfno,
83  segp->seg_out.hit_surfno);
84  }
85 
86  if (PartHdp->pt_forw == PartHdp) bu_bomb("rt_weave0seg() with empty partition list\n");
87 
88  /* See if this segment ends before start of first partition */
89  if (segp->seg_out.hit_dist < PartHdp->pt_forw->pt_inhit->hit_dist) {
90  GET_PT_INIT(rtip, pp, res);
91  bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
92  pp->pt_inseg = segp;
93  pp->pt_inhit = &segp->seg_in;
94  pp->pt_outseg = segp;
95  pp->pt_outhit = &segp->seg_out;
96  APPEND_PT(pp, PartHdp);
97  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("0-len segment ends before start of first partition.\n");
98  return;
99  }
100 
101  /*
102  * Cases: seg at start of pt, in middle of pt, at end of pt, or
103  * past end of pt but before start of next pt.
104  *
105  * XXX For the first 3 cases, we might want to make a new 0-len pt,
106  * XXX especially as the NMG ray-tracer starts reporting wire hits.
107  */
108  for (pp=PartHdp->pt_forw; pp != PartHdp; pp=pp->pt_forw) {
109  if (NEAR_EQUAL(segp->seg_in.hit_dist, pp->pt_inhit->hit_dist, tol_dist) ||
110  NEAR_EQUAL(segp->seg_out.hit_dist, pp->pt_inhit->hit_dist, tol_dist)
111  ) {
112  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("0-len segment ends right at start of existing partition.\n");
113  return;
114  }
115  if (NEAR_EQUAL(segp->seg_in.hit_dist, pp->pt_outhit->hit_dist, tol_dist) ||
116  NEAR_EQUAL(segp->seg_out.hit_dist, pp->pt_outhit->hit_dist, tol_dist)
117  ) {
118  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("0-len segment ends right at end of existing partition.\n");
119  return;
120  }
121  if (segp->seg_out.hit_dist <= pp->pt_outhit->hit_dist &&
122  segp->seg_in.hit_dist >= pp->pt_inhit->hit_dist) {
123  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("0-len segment in the middle of existing partition.\n");
124  return;
125  }
126  if (pp->pt_forw == PartHdp ||
127  segp->seg_out.hit_dist < pp->pt_forw->pt_inhit->hit_dist) {
128  struct partition *npp;
129  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("0-len segment after existing partition, but before next partition.\n");
130  GET_PT_INIT(rtip, npp, res);
131  bu_ptbl_ins_unique(&npp->pt_seglist, (long *)segp);
132  npp->pt_inseg = segp;
133  npp->pt_inhit = &segp->seg_in;
134  npp->pt_outseg = segp;
135  npp->pt_outhit = &segp->seg_out;
136  APPEND_PT(npp, pp);
137  return;
138  }
139  }
140  bu_bomb("rt_weave0seg() fell out of partition loop?\n");
141 }
142 
143 
144 void
145 rt_boolweave(struct seg *out_hd, struct seg *in_hd, struct partition *PartHdp, struct application *ap)
146 {
147  register struct seg *segp;
148  register struct partition *pp;
149  struct resource *res = ap->a_resource;
150  struct rt_i *rtip = ap->a_rt_i;
151 
152  register fastf_t diff, diff_se;
153  register fastf_t tol_dist;
154 
155  RT_CK_PT_HD(PartHdp);
156 
157  tol_dist = rtip->rti_tol.dist;
158 
159  RT_CK_RTI(ap->a_rt_i);
160  RT_CK_RESOURCE(res);
161  RT_CK_RTI(rtip);
162 
164  bu_log("In rt_boolweave, tol_dist = %g\n", tol_dist);
165  rt_pr_partitions(rtip, PartHdp, "-----------------BOOL_WEAVE");
166  }
167 
168  while (BU_LIST_NON_EMPTY(&(in_hd->l))) {
169  register struct partition *newpp = PT_NULL;
170  register struct seg *lastseg = RT_SEG_NULL;
171  register struct hit *lasthit = HIT_NULL;
172  int lastflip = 0;
173 
174  segp = BU_LIST_FIRST(seg, &(in_hd->l));
175  RT_CHECK_SEG(segp);
176  RT_CK_HIT(&(segp->seg_in));
177  RT_CK_RAY(segp->seg_in.hit_rayp);
178  RT_CK_HIT(&(segp->seg_out));
179  RT_CK_RAY(segp->seg_out.hit_rayp);
180  if (RT_G_DEBUG&DEBUG_PARTITION) {
181  point_t pt;
182 
183  bu_log("************ Input segment:\n");
184  rt_pr_seg(segp);
185  rt_pr_hit(" In", &segp->seg_in);
186  VJOIN1(pt, ap->a_ray.r_pt, segp->seg_in.hit_dist, ap->a_ray.r_dir);
187  /* XXX needs indentation added here */
188  VPRINT(" IPoint", pt);
189 
190  rt_pr_hit("Out", &segp->seg_out);
191  VJOIN1(pt, ap->a_ray.r_pt, segp->seg_out.hit_dist, ap->a_ray.r_dir);
192  /* XXX needs indentation added here */
193  VPRINT(" OPoint", pt);
194  bu_log("***********\n");
195  }
196  if ((size_t)segp->seg_stp->st_bit >= rtip->nsolids)
197  bu_bomb("rt_boolweave: st_bit");
198 
199  BU_LIST_DEQUEUE(&(segp->l));
200  BU_LIST_INSERT(&(out_hd->l), &(segp->l));
201 
202  /* Make nearly zero be exactly zero */
203  if (NEAR_ZERO(segp->seg_in.hit_dist, tol_dist))
204  segp->seg_in.hit_dist = 0;
205  if (NEAR_ZERO(segp->seg_out.hit_dist, tol_dist))
206  segp->seg_out.hit_dist = 0;
207 
208  /* Totally ignore things behind the start position */
209  if (segp->seg_out.hit_dist < -10.0)
210  continue;
211 
212  if (segp->seg_stp->st_aradius < INFINITY &&
213  !(segp->seg_in.hit_dist >= -INFINITY &&
214  segp->seg_out.hit_dist <= INFINITY)) {
215  bu_log("rt_boolweave: Defective %s segment %s (%.18e, %.18e) %d, %d\n",
216  OBJ[segp->seg_stp->st_id].ft_name,
217  segp->seg_stp->st_name,
218  segp->seg_in.hit_dist,
219  segp->seg_out.hit_dist,
220  segp->seg_in.hit_surfno,
221  segp->seg_out.hit_surfno);
222  continue;
223  }
224  if (segp->seg_in.hit_dist > segp->seg_out.hit_dist) {
225  bu_log("rt_boolweave: Inside-out %s segment %s (%.18e, %.18e) %d, %d\n",
226  OBJ[segp->seg_stp->st_id].ft_name,
227  segp->seg_stp->st_name,
228  segp->seg_in.hit_dist,
229  segp->seg_out.hit_dist,
230  segp->seg_in.hit_surfno,
231  segp->seg_out.hit_surfno);
232  continue;
233  }
234 
235  /*
236  * Weave this segment into the existing partitions, creating
237  * new partitions as necessary.
238  */
239  if (PartHdp->pt_forw == PartHdp) {
240  /* No partitions yet, simple! */
241  GET_PT_INIT(rtip, pp, res);
242  bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
243  pp->pt_inseg = segp;
244  pp->pt_inhit = &segp->seg_in;
245  pp->pt_outseg = segp;
246  pp->pt_outhit = &segp->seg_out;
247  APPEND_PT(pp, PartHdp);
248  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("No partitions yet, segment forms first partition\n");
249  goto done_weave;
250  }
251 
252  if (ap->a_no_booleans) {
253  lastseg = segp;
254  lasthit = &segp->seg_in;
255  lastflip = 0;
256  /* Just sort in ascending in-dist order */
257  for (pp=PartHdp->pt_forw; pp != PartHdp; pp=pp->pt_forw) {
258  if (lasthit->hit_dist < pp->pt_inhit->hit_dist) {
259  if (RT_G_DEBUG&DEBUG_PARTITION) {
260  bu_log("Insert nobool seg before next pt\n");
261  }
262  GET_PT_INIT(rtip, newpp, res);
263  bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
264  newpp->pt_inseg = segp;
265  newpp->pt_inhit = &segp->seg_in;
266  newpp->pt_outseg = segp;
267  newpp->pt_outhit = &segp->seg_out;
268  INSERT_PT(newpp, pp);
269  goto done_weave;
270  }
271  }
272  if (RT_G_DEBUG&DEBUG_PARTITION) {
273  bu_log("Append nobool seg at end of list\n");
274  }
275  GET_PT_INIT(rtip, newpp, res);
276  bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
277  newpp->pt_inseg = segp;
278  newpp->pt_inhit = &segp->seg_in;
279  newpp->pt_outseg = segp;
280  newpp->pt_outhit = &segp->seg_out;
281  INSERT_PT(newpp, PartHdp);
282  goto done_weave;
283  }
284 
285  /* Check for zero-thickness segment, within tol */
286  diff = segp->seg_in.hit_dist - segp->seg_out.hit_dist;
287  if (NEAR_ZERO(diff, tol_dist)) {
288  rt_weave0seg(segp, PartHdp, ap);
289  goto done_weave;
290  }
291 
292  if (segp->seg_in.hit_dist >= PartHdp->pt_back->pt_outhit->hit_dist) {
293  /*
294  * Segment starts exactly at last partition's end, or
295  * beyond last partitions end. Make new partition.
296  */
297  if (RT_G_DEBUG&DEBUG_PARTITION) {
298  bu_log("seg starts beyond last partition end. (%g, %g) Appending new partition\n",
299  PartHdp->pt_back->pt_inhit->hit_dist,
300  PartHdp->pt_back->pt_outhit->hit_dist);
301  }
302  GET_PT_INIT(rtip, pp, res);
303  bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
304  pp->pt_inseg = segp;
305  pp->pt_inhit = &segp->seg_in;
306  pp->pt_outseg = segp;
307  pp->pt_outhit = &segp->seg_out;
308  APPEND_PT(pp, PartHdp->pt_back);
309  goto done_weave;
310  }
311 
312  /* Loop through current partition list weaving the current
313  * input segment into the list. The following three variables
314  * keep track of the current starting point of the input
315  * segment. The starting point of the segment moves to higher
316  * hit_dist values (as it is woven in) until it is entirely
317  * consumed.
318  */
319  lastseg = segp;
320  lasthit = &segp->seg_in;
321  lastflip = 0;
322  for (pp=PartHdp->pt_forw; pp != PartHdp; pp=pp->pt_forw) {
323 
324  if (RT_G_DEBUG&DEBUG_PARTITION) {
325  bu_log("At start of loop:\n");
326  bu_log(" remaining input segment: (%.12e - %.12e)\n",
327  lasthit->hit_dist, segp->seg_out.hit_dist);
328  bu_log(" current partition: (%.12e - %.12e)\n",
329  pp->pt_inhit->hit_dist, pp->pt_outhit->hit_dist);
330  rt_pr_partitions(rtip, PartHdp, "At start of loop");
331  }
332 
333  diff_se = lasthit->hit_dist - pp->pt_outhit->hit_dist;
334  if (diff_se > tol_dist) {
335  /* Seg starts beyond the END of the
336  * current partition.
337  * PPPP
338  * SSSS
339  * Advance to next partition.
340  */
341  if (RT_G_DEBUG&DEBUG_PARTITION) {
342  bu_log("seg start beyond partition end, skipping. (%g, %g)\n",
343  pp->pt_inhit->hit_dist,
344  pp->pt_outhit->hit_dist);
345  }
346  continue;
347  }
348  if (RT_G_DEBUG&DEBUG_PARTITION) rt_pr_pt(rtip, pp);
349  diff = lasthit->hit_dist - pp->pt_inhit->hit_dist;
350  if (diff_se > -(tol_dist) && diff > tol_dist) {
351  /*
352  * Seg starts almost "precisely" at the
353  * end of the current partition.
354  * PPPP
355  * SSSS
356  * FUSE an exact match of the endpoints,
357  * advance to next partition.
358  */
359  lasthit->hit_dist = pp->pt_outhit->hit_dist;
360  if (RT_G_DEBUG&DEBUG_PARTITION) {
361  bu_log("seg start fused to partition end, diff=%g\n", diff);
362  }
363  continue;
364  }
365 
366  /*
367  * diff < ~~0
368  * Seg starts before current partition ends
369  * PPPPPPPPPPP
370  * SSSS...
371  */
372  if (diff > tol_dist) {
373  /*
374  * lasthit->hit_dist > pp->pt_inhit->hit_dist
375  * pp->pt_inhit->hit_dist < lasthit->hit_dist
376  *
377  * Segment starts after partition starts,
378  * but before the end of the partition.
379  * Note: pt_seglist will be updated in equal_start.
380  * PPPPPPPPPPPP
381  * SSSS...
382  * newpp|pp
383  */
384  RT_DUP_PT(rtip, newpp, pp, res);
385  /* new partition is the span before seg joins partition */
386  pp->pt_inseg = segp;
387  pp->pt_inhit = &segp->seg_in;
388  pp->pt_inflip = 0;
389  newpp->pt_outseg = segp;
390  newpp->pt_outhit = &segp->seg_in;
391  newpp->pt_outflip = 1;
392  INSERT_PT(newpp, pp);
393  if (RT_G_DEBUG&DEBUG_PARTITION) {
394  bu_log("seg starts within p. Split p at seg start, advance. (diff = %g)\n", diff);
395  bu_log("newpp starts at %.12e, pp starts at %.12e\n",
396  newpp->pt_inhit->hit_dist,
397  pp->pt_inhit->hit_dist);
398  bu_log("newpp = %p, pp = %p\n", (void *)newpp, (void *)pp);
399  }
400  goto equal_start;
401  }
402  if (diff > -(tol_dist)) {
403  /*
404  * Make a subtle but important distinction here. Even
405  * though the two distances are "equal" within
406  * tolerance, they are not exactly the same. If the
407  * new segment is slightly closer to the ray origin,
408  * then use its IN point.
409  *
410  * This is an attempt to reduce the deflected normals
411  * sometimes seen along the edges of e.g. a cylinder
412  * unioned with an ARB8, where the ray hits the top of
413  * the cylinder and the *side* face of the ARB8 rather
414  * than the top face of the ARB8.
415  */
416  diff = segp->seg_in.hit_dist - pp->pt_inhit->hit_dist;
417  if (!pp->pt_back ||
418  pp->pt_back == PartHdp ||
419  pp->pt_back->pt_outhit->hit_dist <=
420  segp->seg_in.hit_dist) {
421  if (NEAR_ZERO(diff, tol_dist) &&
422  diff < 0) {
423  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("changing partition start point to segment start point\n");
424  pp->pt_inseg = segp;
425  pp->pt_inhit = &segp->seg_in;
426  pp->pt_inflip = 0;
427  }
428  }
429  equal_start:
430  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("equal_start\n");
431  /*
432  * Segment and partition start at (roughly) the same
433  * point. When fusing 2 points together i.e., when
434  * NEAR_ZERO(diff, tol) is true, the two points MUST
435  * be forced to become exactly equal!
436  */
437  diff = segp->seg_out.hit_dist - pp->pt_outhit->hit_dist;
438  if (diff > tol_dist) {
439  /*
440  * Seg & partition start at roughly
441  * the same spot,
442  * seg extends beyond partition end.
443  * PPPP
444  * SSSSSSSS
445  * pp | newpp
446  */
447  bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
448  lasthit = pp->pt_outhit;
449  lastseg = pp->pt_outseg;
450  lastflip = 1;
451  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("seg spans partition and extends beyond it\n");
452  continue;
453  }
454  if (diff > -(tol_dist)) {
455  /*
456  * diff ~= 0
457  * Segment and partition start & end
458  * (nearly) together.
459  * PPPP
460  * SSSS
461  */
462  bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
463  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("same start&end\n");
464  goto done_weave;
465  } else {
466  /*
467  * diff < ~0
468  *
469  * Segment + Partition start together,
470  * segment ends before partition ends.
471  * PPPPPPPPPP
472  * SSSSSS
473  * newpp| pp
474  */
475  RT_DUP_PT(rtip, newpp, pp, res);
476  /* new partition contains segment */
477  bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
478  newpp->pt_outseg = segp;
479  newpp->pt_outhit = &segp->seg_out;
480  newpp->pt_outflip = 0;
481  pp->pt_inseg = segp;
482  pp->pt_inhit = &segp->seg_out;
483  pp->pt_inflip = 1;
484  INSERT_PT(newpp, pp);
485  if (RT_G_DEBUG&DEBUG_PARTITION) {
486  bu_log("start together, seg shorter than partition\n");
487  bu_log("newpp starts at %.12e, pp starts at %.12e\n",
488  newpp->pt_inhit->hit_dist,
489  pp->pt_inhit->hit_dist);
490  bu_log("newpp = %p, pp = %p\n", (void *)newpp, (void *)pp);
491  }
492  goto done_weave;
493  }
494  /* NOTREACHED */
495  } else {
496  /*
497  * diff < ~~0
498  *
499  * Seg starts before current partition starts,
500  * but after the previous partition ends.
501  * SSSSSSSS...
502  * PPPPP...
503  * newpp|pp
504  */
505  GET_PT_INIT(rtip, newpp, res);
506  bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
507  newpp->pt_inseg = lastseg;
508  newpp->pt_inhit = lasthit;
509  newpp->pt_inflip = lastflip;
510  diff = segp->seg_out.hit_dist - pp->pt_inhit->hit_dist;
511  if (diff < -(tol_dist)) {
512  /*
513  * diff < ~0
514  * Seg starts and ends before current
515  * partition, but after previous
516  * partition ends (diff < 0).
517  * SSSS
518  * pppp PPPPP...
519  * newpp pp
520  */
521  newpp->pt_outseg = segp;
522  newpp->pt_outhit = &segp->seg_out;
523  newpp->pt_outflip = 0;
524  INSERT_PT(newpp, pp);
525  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("seg between 2 partitions\n");
526  goto done_weave;
527  }
528  if (diff < tol_dist) {
529  /*
530  * diff ~= 0
531  *
532  * Seg starts before current
533  * partition starts, and ends at or
534  * near the start of the partition.
535  * (diff == 0). FUSE the points.
536  * SSSSSS
537  * PPPPP
538  * newpp|pp
539  * NOTE: only copy hit point, not
540  * normals or norm private stuff.
541  */
542  newpp->pt_outseg = segp;
543  newpp->pt_outhit = &segp->seg_out;
544  newpp->pt_outhit->hit_dist = pp->pt_inhit->hit_dist;
545  newpp->pt_outflip = 0;
546  INSERT_PT(newpp, pp);
547  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("seg ends at partition start, fuse\n");
548  goto done_weave;
549  }
550  /*
551  * Seg starts before current partition
552  * starts, and ends after the start of the
553  * partition. (diff > 0).
554  * SSSSSSSSSS
555  * PPPPPPP
556  * newpp| pp | ...
557  */
558  newpp->pt_outseg = pp->pt_inseg;
559  newpp->pt_outhit = pp->pt_inhit;
560  newpp->pt_outflip = 1;
561  lastseg = pp->pt_inseg;
562  lasthit = pp->pt_inhit;
563  lastflip = newpp->pt_outflip;
564  INSERT_PT(newpp, pp);
565  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("insert seg before p start, ends after p ends. Making new partition for initial portion.\n");
566  goto equal_start;
567  }
568  /* NOTREACHED */
569  }
570 
571  /*
572  * Segment has portion which extends beyond the end
573  * of the last partition. Tack on the remainder.
574  * PPPPP
575  * SSSSS
576  */
577  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("seg extends beyond partition end\n");
578  GET_PT_INIT(rtip, newpp, res);
579  bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
580  newpp->pt_inseg = lastseg;
581  newpp->pt_inhit = lasthit;
582  newpp->pt_inflip = lastflip;
583  newpp->pt_outseg = segp;
584  newpp->pt_outhit = &segp->seg_out;
585  APPEND_PT(newpp, PartHdp->pt_back);
586 
587  done_weave: ; /* Sorry about the goto's, but they give clarity */
588  if (RT_G_DEBUG&DEBUG_PARTITION)
589  rt_pr_partitions(rtip, PartHdp, "After weave");
590  }
591  if (RT_G_DEBUG&DEBUG_PARTITION)
592  bu_log("--------------------Leaving Booleweave\n");
593 }
594 
595 
596 int
597 rt_defoverlap (register struct application *ap, register struct partition *pp, struct region *reg1, struct region *reg2, struct partition *pheadp)
598 {
599  RT_CK_AP(ap);
600  RT_CK_PT(pp);
601  RT_CK_REGION(reg1);
602  RT_CK_REGION(reg2);
603 
604  /*
605  * Apply heuristics as to which region should claim partition.
606  */
607  if (reg1->reg_aircode != 0) {
608  /* reg1 was air, replace with reg2 */
609  return 2;
610  }
611  if (pp->pt_back != pheadp) {
612  /* Repeat a prev region, if that is a choice */
613  if (pp->pt_back->pt_regionp == reg1)
614  return 1;
615  if (pp->pt_back->pt_regionp == reg2)
616  return 2;
617  }
618 
619  /* To provide some consistency from ray to ray, use lowest bit # */
620  if (reg1->reg_bit < reg2->reg_bit)
621  return 1;
622  return 2;
623 }
624 
625 
626 /**
627  * Given one of the regions that is involved in a given partition
628  * (whether the boolean formula for this region is BOOL_TRUE in this
629  * part or not), return a bu_ptbl list containing all the segments in
630  * this partition which came from solids that appear as terms in the
631  * boolean formula for the given region.
632  *
633  * The bu_ptbl is initialized here, and must be freed by the caller.
634  * It will contain a pointer to at least one segment.
635  */
636 void
637 rt_get_region_seglist_for_partition(struct bu_ptbl *sl, const struct partition *pp, const struct region *regp)
638 {
639  const struct seg **segpp;
640 
641  bu_ptbl_init(sl, 8, "region seglist for partition");
642 
643  /* Walk the partitions segment list */
644  for (BU_PTBL_FOR(segpp, (const struct seg **), &pp->pt_seglist)) {
645  const struct region **srpp;
646 
647  RT_CK_SEG(*segpp);
648  /* For every segment in part, walk the solid's region list */
649  for (BU_PTBL_FOR(srpp, (const struct region **), &(*segpp)->seg_stp->st_regions)) {
650  RT_CK_REGION(*srpp);
651 
652  if (*srpp != regp) continue;
653  /* This segment is part of a solid in this region */
654  bu_ptbl_ins_unique(sl, (long *)(*segpp));
655  }
656  }
657 
658  if (BU_PTBL_LEN(sl) <= 0) bu_bomb("rt_get_region_seglist_for_partition() didn't find any segments\n");
659 }
660 
661 
662 /**
663  * Find the maximum value of the raynum (seg_rayp->index) encountered
664  * in the segments contributing to this region.
665  *
666  * Returns -
667  * # Maximum ray index
668  * -1 If no rays are contributing segs for this region.
669  */
670 int
671 rt_tree_max_raynum(register const union tree *tp, register const struct partition *pp)
672 {
673  RT_CK_TREE(tp);
674  RT_CK_PARTITION(pp);
675 
676  switch (tp->tr_op) {
677  case OP_NOP:
678  return -1;
679 
680  case OP_SOLID:
681  {
682  register struct soltab *seek_stp = tp->tr_a.tu_stp;
683  register struct seg **segpp;
684  for (BU_PTBL_FOR(segpp, (struct seg **), &pp->pt_seglist)) {
685  if ((*segpp)->seg_stp != seek_stp) continue;
686  return (*segpp)->seg_in.hit_rayp->index;
687  }
688  }
689  /* Maybe it hasn't been shot yet, or ray missed */
690  return -1;
691 
692  case OP_NOT:
693  return rt_tree_max_raynum(tp->tr_b.tb_left, pp);
694 
695  case OP_UNION:
696  case OP_INTERSECT:
697  case OP_SUBTRACT:
698  case OP_XOR:
699  {
700  int a = rt_tree_max_raynum(tp->tr_b.tb_left, pp);
701  int b = rt_tree_max_raynum(tp->tr_b.tb_right, pp);
702  if (a > b) return a;
703  return b;
704  }
705  default:
706  bu_bomb("rt_tree_max_raynum: bad op\n");
707  }
708  return 0;
709 }
710 
711 
712 /**
713  * Handle FASTGEN volume/volume overlap. Look at underlying segs. If
714  * one is less than 1/4", take the longer. Otherwise take the
715  * shorter.
716  *
717  * Required to null out one of the two regions.
718  */
719 void
720 rt_fastgen_vol_vol_overlap(struct region **fr1, struct region **fr2, const struct partition *pp)
721 {
722  struct bu_ptbl sl1 = BU_PTBL_INIT_ZERO;
723  struct bu_ptbl sl2 = BU_PTBL_INIT_ZERO;
724  const struct seg *s1 = (const struct seg *)NULL;
725  const struct seg *s2 = (const struct seg *)NULL;
726  fastf_t s1_in_dist;
727  fastf_t s2_in_dist;
728  fastf_t depth;
729  struct seg **segpp;
730 
731  RT_CK_REGION(*fr1);
732  RT_CK_REGION(*fr2);
733 
734  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("Resolving FASTGEN volume/volume overlap: %s %s\n", (*fr1)->reg_name, (*fr2)->reg_name);
735 
736  rt_get_region_seglist_for_partition(&sl1, pp, *fr1);
737  rt_get_region_seglist_for_partition(&sl2, pp, *fr2);
738 
739  s1_in_dist = MAX_FASTF;
740  s2_in_dist = MAX_FASTF;
741  for (BU_PTBL_FOR(segpp, (struct seg **), &sl1))
742  {
743  if ((*segpp)->seg_in.hit_dist < s1_in_dist)
744  {
745  s1 = (*segpp);
746  s1_in_dist = s1->seg_in.hit_dist;
747  }
748  }
749  for (BU_PTBL_FOR(segpp, (struct seg **), &sl2))
750  {
751  if ((*segpp)->seg_in.hit_dist < s2_in_dist)
752  {
753  s2 = (*segpp);
754  s2_in_dist = s2->seg_in.hit_dist;
755  }
756  }
757  RT_CK_SEG(s1);
758  RT_CK_SEG(s2);
759 
760  depth = pp->pt_outhit->hit_dist - pp->pt_inhit->hit_dist;
761 
762  /* 6.35mm = 1/4 inch */
763  if (depth < 6.35) {
764  /* take region with lowest inhit */
765  if (s1->seg_in.hit_dist < s2->seg_in.hit_dist) {
766  /* keep fr1, delete fr2 */
767  *fr2 = REGION_NULL;
768  } else {
769  /* keep fr2, delete fr1 */
770  *fr1 = REGION_NULL;
771  }
772  } else {
773  /*
774  * take the region with largest inhit
775  */
776  if (s1->seg_in.hit_dist >= s2->seg_in.hit_dist) {
777  /* keep fr1, delete fr2 */
778  *fr2 = REGION_NULL;
779  } else {
780  *fr1 = REGION_NULL;
781  }
782  }
783 
784  bu_ptbl_free(&sl1);
785  bu_ptbl_free(&sl2);
786 }
787 
788 int
789 rt_fdiff(double a, double b)
790 {
791  register double diff;
792  register double d;
793  register int ret;
794 
795  /* d = Max(Abs(a), Abs(b)) */
796  d = (a >= 0.0) ? a : -a;
797  if (b >= 0.0) {
798  if (b > d) d = b;
799  } else {
800  if ((-b) > d) d = (-b);
801  }
802  if (d <= 1.0e-6) {
803  ret = 0; /* both nearly zero */
804  goto out;
805  }
806  if (d >= INFINITY) {
807  if (ZERO(a - b)) {
808  ret = 0;
809  goto out;
810  }
811  if (a < b) {
812  ret = -1;
813  goto out;
814  }
815  ret = 1;
816  goto out;
817  }
818  if ((diff = a - b) < 0.0) diff = -diff;
819  if (diff < 0.001) {
820  ret = 0; /* absolute difference is small, < 1/1000mm */
821  goto out;
822  }
823  if (diff < 0.000001 * d) {
824  ret = 0; /* relative difference is small, < 1ppm */
825  goto out;
826  }
827  if (a < b) {
828  ret = -1;
829  goto out;
830  }
831  ret = 1;
832 out:
833  if (RT_G_DEBUG&DEBUG_FDIFF) bu_log("rt_fdiff(%.18e, %.18e)=%d\n", a, b, ret);
834  return ret;
835 }
836 
837 
838 /**
839  * Handle FASTGEN plate/volume overlap.
840  *
841  * Measure width of _preceding_ partition, which must have been
842  * claimed by the volume mode region fr2.
843  *
844  * If less than 1/4", delete preceding partition, and plate wins this
845  * part. If less than 1/4", plate wins this part, previous partition
846  * untouched. If previous partition is claimed by plate mode region
847  * fr1, then overlap is left in output???
848  *
849  * Required to null out one of the two regions.
850  */
851 void
852 rt_fastgen_plate_vol_overlap(struct region **fr1, struct region **fr2, struct partition *pp, struct application *ap)
853 {
854  struct partition *prev;
855  fastf_t depth;
856 
857  RT_CK_REGION(*fr1);
858  RT_CK_REGION(*fr2);
859  RT_CK_PT(pp);
860  RT_CK_AP(ap);
861 
862  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("Resolving FASTGEN plate/volume overlap: %s %s\n", (*fr1)->reg_name, (*fr2)->reg_name);
863 
864  prev = pp->pt_back;
865  if (prev->pt_magic == PT_HD_MAGIC) {
866  /* No prev partition, this is the first. d=0, plate wins */
867  *fr2 = REGION_NULL;
868  return;
869  }
870 
871  /* arbitrary tolerance is the dominant absolute tolerance from the
872  * now-deprecated rt_fdiff(). need to test sensitivity before
873  * changing to the distance tolerance.
874  */
875  if (!NEAR_EQUAL(prev->pt_outhit->hit_dist, pp->pt_inhit->hit_dist, 0.001)) {
876  /* There is a gap between previous partition and this one. So
877  * both plate and vol start at same place, d=0, plate wins.
878  */
879  *fr2 = REGION_NULL;
880  return;
881  }
882 
883  if (prev->pt_regionp == *fr2) {
884  /* previous part is volume mode, ends at start of pp */
885  depth = prev->pt_outhit->hit_dist - prev->pt_inhit->hit_dist;
886  /* 6.35mm = 1/4 inch */
887  if (depth < 6.35) {
888  /* Delete previous partition from list */
889  DEQUEUE_PT(prev);
890  FREE_PT(prev, ap->a_resource);
891 
892  /* plate mode fr1 wins this partition */
893  *fr2 = REGION_NULL;
894  } else {
895  /* Leave previous partition alone */
896  /* plate mode fr1 wins this partition */
897  *fr2 = REGION_NULL;
898  }
899  } else if (prev->pt_regionp == *fr1) {
900  /* previous part is plate mode, ends at start of pp */
901  /* d < 0, leave overlap in output??? */
902  /* For now, volume mode region just loses. */
903  *fr2 = REGION_NULL;
904  } else {
905  /* Some other region precedes this partition */
906  /* So both plate and vol start at same place, d=0, plate wins */
907  *fr2 = REGION_NULL;
908  }
909 }
910 
911 
912 void
913 rt_default_multioverlap(struct application *ap, struct partition *pp, struct bu_ptbl *regiontable, struct partition *InputHdp)
914 {
915  struct region *lastregion = (struct region *)NULL;
916  int n_regions;
917  int n_fastgen = 0;
918  int code;
919  size_t i;
920  int counter;
921 
922  RT_CK_AP(ap);
923  RT_CK_PARTITION(pp);
924  BU_CK_PTBL(regiontable);
925  RT_CK_PT_HD(InputHdp);
926 
927  if (ap->a_overlap == RT_AFN_NULL)
928  ap->a_overlap = rt_defoverlap;
929 
930  /* Count number of FASTGEN regions */
931  n_regions = BU_PTBL_LEN(regiontable);
932  for (counter = n_regions-1; counter >= 0; counter--) {
933  struct region *regp = (struct region *)BU_PTBL_GET(regiontable, counter);
934  RT_CK_REGION(regp);
935  if (regp->reg_is_fastgen != REGION_NON_FASTGEN) n_fastgen++;
936  }
937 
938  /*
939  * Resolve all FASTGEN overlaps before considering BRL-CAD
940  * overlaps, because FASTGEN overlaps have strict rules.
941  */
942  if (n_fastgen >= 2) {
943  struct region **fr1;
944  struct region **fr2;
945 
947  bu_log("I see %d FASTGEN overlaps in this partition\n", n_fastgen);
948  for (BU_PTBL_FOR(fr1, (struct region **), regiontable)) {
949  if (*fr1 == REGION_NULL) continue;
950  rt_pr_region(*fr1);
951  }
952  }
953 
954  /*
955  * First, resolve volume_mode/volume_mode overlaps because
956  * they are a simple choice. The searches run from high to
957  * low in the ptbl array.
958  */
959  for (BU_PTBL_FOR(fr1, (struct region **), regiontable)) {
960  if (*fr1 == REGION_NULL) continue;
961  RT_CK_REGION(*fr1);
962  if ((*fr1)->reg_is_fastgen != REGION_FASTGEN_VOLUME)
963  continue;
964  for (fr2 = fr1-1; fr2 >= (struct region **)BU_PTBL_BASEADDR(regiontable); fr2--) {
965  if (*fr2 == REGION_NULL) continue;
966  RT_CK_REGION(*fr2);
967  if ((*fr2)->reg_is_fastgen != REGION_FASTGEN_VOLUME)
968  continue;
969  rt_fastgen_vol_vol_overlap(fr1, fr2, pp);
970  if (*fr1 == REGION_NULL) break;
971  }
972  }
973 
974  /* Second, resolve plate_mode/volume_mode overlaps */
975  for (BU_PTBL_FOR(fr1, (struct region **), regiontable)) {
976  if (*fr1 == REGION_NULL) continue;
977  RT_CK_REGION(*fr1);
978  if ((*fr1)->reg_is_fastgen != REGION_FASTGEN_PLATE)
979  continue;
980  for (BU_PTBL_FOR(fr2, (struct region **), regiontable)) {
981  if (*fr2 == REGION_NULL) continue;
982  RT_CK_REGION(*fr2);
983  if ((*fr2)->reg_is_fastgen != REGION_FASTGEN_VOLUME)
984  continue;
985  rt_fastgen_plate_vol_overlap(fr1, fr2, pp, ap);
986  if (*fr1 == REGION_NULL) break;
987  }
988  }
989 
990 
991  /* Finally, think up a way to pass plate/plate overlaps on */
992  n_fastgen = 0;
993  for (counter = n_regions-1; counter >= 0; counter--) {
994  struct region *regp = (struct region *)BU_PTBL_GET(regiontable, counter);
995  if (regp == REGION_NULL) continue; /* empty slot in table */
996  RT_CK_REGION(regp);
997  if (regp->reg_is_fastgen != REGION_NON_FASTGEN) n_fastgen++;
998  }
999 
1000  /* Compress out any null pointers in the table */
1001  bu_ptbl_rm(regiontable, (long *)NULL);
1002  }
1003 
1004  lastregion = (struct region *)BU_PTBL_GET(regiontable, 0);
1005  RT_CK_REGION(lastregion);
1006 
1007  if (BU_PTBL_LEN(regiontable) > 1 && ap->a_rt_i->rti_save_overlaps != 0) {
1008  /*
1009  * Snapshot current state of overlap list, so that downstream
1010  * application code can resolve any FASTGEN plate/plate
1011  * overlaps. The snapshot is not taken at the top of the
1012  * routine because nobody is interested in FASTGEN vol/plate
1013  * or vol/vol overlaps. The list is terminated with a NULL
1014  * pointer, placed courtesy of bu_calloc().
1015  */
1016  pp->pt_overlap_reg = (struct region **)bu_calloc(
1017  BU_PTBL_LEN(regiontable)+1, sizeof(struct region *),
1018  "pt_overlap_reg");
1019  memcpy((char *)pp->pt_overlap_reg,
1020  (char *)BU_PTBL_BASEADDR(regiontable),
1021  BU_PTBL_LEN(regiontable) * sizeof(struct region *));
1022  }
1023 
1024  /* Examine the overlapping regions, pairwise */
1025  for (i=1; i < BU_PTBL_LEN(regiontable); i++) {
1026  struct region *regp = (struct region *)BU_PTBL_GET(regiontable, i);
1027  if (regp == REGION_NULL) continue; /* empty slot in table */
1028  RT_CK_REGION(regp);
1029 
1030  code = -1; /* For debug out in policy */
1031 
1032  /*
1033  * Two or more regions claim this partition
1034  */
1035  if (lastregion->reg_aircode != 0 && regp->reg_aircode == 0) {
1036  /* last region is air, replace with solid regp */
1037  goto code2;
1038  } else if (lastregion->reg_aircode == 0 && regp->reg_aircode != 0) {
1039  /* last region solid, regp is air, keep last */
1040  goto code1;
1041  } else if (lastregion->reg_aircode != 0 &&
1042  regp->reg_aircode != 0 &&
1043  regp->reg_aircode == lastregion->reg_aircode) {
1044  /* both are same air, keep last */
1045  goto code1;
1046  }
1047 
1048  /*
1049  * If a FASTGEN region overlaps a non-FASTGEN region, the
1050  * non-FASTGEN ("traditional BRL-CAD") region wins. No
1051  * mixed-mode geometry like this will be built by the
1052  * fastgen-to-BRL-CAD converters, only by human editors.
1053  */
1054  if (lastregion->reg_is_fastgen != regp->reg_is_fastgen) {
1055  if (lastregion->reg_is_fastgen)
1056  goto code2; /* keep regp */
1057  if (regp->reg_is_fastgen)
1058  goto code1; /* keep lastregion */
1059  }
1060 
1061  /*
1062  * To support ray bundles, find partition with the lower
1063  * contributing ray number (closer to center of bundle), and
1064  * retain that one.
1065  */
1066  {
1067  int r1 = rt_tree_max_raynum(lastregion->reg_treetop, pp);
1068  int r2 = rt_tree_max_raynum(regp->reg_treetop, pp);
1069 
1070  /* Only use this algorithm if one is not the main ray */
1071  if (r1 > 0 || r2 > 0) {
1073  bu_log("Potential overlay along ray bundle: r1=%d, r2=%d, resolved to %s\n", r1, r2,
1074  (r1<r2)?lastregion->reg_name:regp->reg_name);
1075  }
1076  if (r1 < r2) {
1077  goto code1; /* keep lastregion */
1078  }
1079  goto code2; /* keep regp */
1080  }
1081  }
1082 
1083  /*
1084  * Hand overlap to old-style application-specific
1085  * overlap handler, or default.
1086  * 0 = destroy partition,
1087  * 1 = keep part, claiming region=lastregion
1088  * 2 = keep part, claiming region=regp
1089  */
1090  code = ap->a_overlap(ap, pp, lastregion, regp, InputHdp);
1091 
1092  /* Implement the policy in "code" */
1093  if (code == 0) {
1094  /*
1095  * Destroy the whole partition.
1096  */
1098  bu_log("rt_default_multioverlap: overlap code=0, partition=%p deleted\n", (void *)pp);
1099  bu_ptbl_reset(regiontable);
1100  return;
1101  } else if (code == 1) {
1102  code1:
1103  /* Keep partition, claiming region = lastregion */
1105  bu_log("rt_default_multioverlap: overlap policy=1, code=%d, p retained in region=%s\n",
1106  code, lastregion->reg_name);
1107  BU_PTBL_CLEAR_I(regiontable, i);
1108  } else {
1109  code2:
1110  /* Keep partition, claiming region = regp */
1111  bu_ptbl_zero(regiontable, (long *)lastregion);
1112  lastregion = regp;
1114  bu_log("rt_default_multioverlap: overlap policy!=(0, 1) code=%d, p retained in region=%s\n",
1115  code, lastregion->reg_name);
1116  }
1117  }
1118 }
1119 
1120 
1121 void
1122 rt_silent_logoverlap(struct application *ap, const struct partition *pp, const struct bu_ptbl *regiontable, const struct partition *UNUSED(InputHdp))
1123 {
1124  RT_CK_AP(ap);
1125  RT_CK_PT(pp);
1126  BU_CK_PTBL(regiontable);
1127  return;
1128 }
1129 
1130 
1131 void
1132 rt_default_logoverlap(struct application *ap, const struct partition *pp, const struct bu_ptbl *regiontable, const struct partition *UNUSED(InputHdp))
1133 {
1134  point_t pt;
1135  static long count = 0; /* Not PARALLEL, shouldn't hurt */
1136  register fastf_t depth;
1137  size_t i;
1138  struct bu_vls str = BU_VLS_INIT_ZERO;
1139 
1140  RT_CK_AP(ap);
1141  RT_CK_PT(pp);
1142  BU_CK_PTBL(regiontable);
1143 
1144  /* Attempt to control tremendous error outputs */
1145  if (++count > 100) {
1146  if ((count%100) != 3) return;
1147  bu_log("(overlaps omitted)\n");
1148  }
1149 
1150  /*
1151  * Print all verbiage in one call to bu_log(),
1152  * so that messages will be grouped together in parallel runs.
1153  */
1154  bu_vls_extend(&str, 80*8);
1155  bu_vls_putc(&str, '\n');
1156 
1157  /* List all the regions which evaluated to BOOL_TRUE in this partition */
1158  for (i=0; i < BU_PTBL_LEN(regiontable); i++) {
1159  struct region *regp = (struct region *)BU_PTBL_GET(regiontable, i);
1160 
1161  if (regp == REGION_NULL) continue;
1162  RT_CK_REGION(regp);
1163 
1164  bu_vls_printf(&str, "OVERLAP%zu: %s\n", i+1, regp->reg_name);
1165  }
1166 
1167  /* List all the information common to this whole partition */
1168  bu_vls_printf(&str, "OVERLAPa: dist=(%g, %g) isol=%s osol=%s\n",
1169  pp->pt_inhit->hit_dist, pp->pt_outhit->hit_dist,
1170  pp->pt_inseg->seg_stp->st_name,
1171  pp->pt_outseg->seg_stp->st_name);
1172 
1173  depth = pp->pt_outhit->hit_dist - pp->pt_inhit->hit_dist;
1174  VJOIN1(pt, ap->a_ray.r_pt, pp->pt_inhit->hit_dist,
1175  ap->a_ray.r_dir);
1176 
1177  bu_vls_printf(&str, "OVERLAPb: depth %.5fmm at (%g, %g, %g) x%d y%d lvl%d\n",
1178  depth, pt[X], pt[Y], pt[Z],
1179  ap->a_x, ap->a_y, ap->a_level);
1180 
1181  bu_log("%s", bu_vls_addr(&str));
1182  bu_vls_free(&str);
1183 }
1184 
1185 
1186 /**
1187  * Overlap tables are NULL terminated arrays of region pointers. The
1188  * order of entries may be different between the two.
1189  *
1190  * Returns -
1191  * 1 The tables match
1192  * 0 The tables do not match
1193  */
1194 int
1195 rt_overlap_tables_equal(struct region *const*a, struct region *const*b)
1196 {
1197  int alen=0, blen=0;
1198  register struct region *const*app;
1199  register struct region *const*bpp;
1200 
1201  if (a == NULL && b == NULL)
1202  return 1;
1203 
1204  if (a == NULL || b == NULL)
1205  return 0;
1206 
1207  /* First step, compare lengths */
1208  for (app = a; *app != NULL; app++) alen++;
1209  for (bpp = b; *bpp != NULL; bpp++) blen++;
1210  if (alen != blen) return 0;
1211 
1212  /* Second step, compare contents */
1213  for (app = a; *app != NULL; app++) {
1214  register const struct region *t = *app;
1215  for (bpp = b; *bpp != NULL; bpp++) {
1216  if (*bpp == t) goto b_ok;
1217  }
1218  /* 't' not found in b table, no match */
1219  return 0;
1220  b_ok: ;
1221  }
1222  /* Everything matches */
1223  return 1;
1224 }
1225 
1226 
1227 /**
1228  * Test to see if a region is ready to be evaluated over a given
1229  * partition, i.e. if all the prerequisites have been satisfied.
1230  *
1231  * Returns -
1232  * !0 Region is ready for (correct) evaluation.
1233  * 0 Region is not ready
1234  */
1235 int
1236 rt_tree_test_ready(register const union tree *tp, register const struct bu_bitv *solidbits, register const struct region *regionp, register const struct partition *pp)
1237 {
1238  RT_CK_TREE(tp);
1239  BU_CK_BITV(solidbits);
1240  RT_CK_REGION(regionp);
1241  RT_CK_PT(pp);
1242 
1243  switch (tp->tr_op) {
1244  case OP_NOP:
1245  return 1;
1246 
1247  case OP_SOLID:
1248  if (BU_BITTEST(solidbits, tp->tr_a.tu_stp->st_bit)) {
1249  /* This solid's been shot, segs are valid. */
1250  return 1;
1251  }
1252 
1253  /*
1254  * This solid has not been shot yet.
1255  */
1256  return 0;
1257 
1258  case OP_NOT:
1259  return !rt_tree_test_ready(tp->tr_b.tb_left, solidbits, regionp, pp);
1260 
1261  case OP_UNION:
1262  case OP_INTERSECT:
1263  case OP_SUBTRACT:
1264  case OP_XOR:
1265  if (!rt_tree_test_ready(tp->tr_b.tb_left, solidbits, regionp, pp))
1266  return 0;
1267  return rt_tree_test_ready(tp->tr_b.tb_right, solidbits, regionp, pp);
1268 
1269  default:
1270  bu_bomb("rt_tree_test_ready: bad op\n");
1271  }
1272  return 0;
1273 }
1274 
1275 
1276 /**
1277  * If every solid in every region participating in this ray-partition
1278  * has already been intersected with the ray, then this partition can
1279  * be safely evaluated.
1280  *
1281  * Returns -
1282  * !0 Partition is ready for (correct) evaluation.
1283  * 0 Partition is not ready
1284  */
1285 int
1286 rt_bool_partition_eligible(register const struct bu_ptbl *regiontable, register const struct bu_bitv *solidbits, register const struct partition *pp)
1287 {
1288  struct region **regpp;
1289 
1290  BU_CK_PTBL(regiontable);
1291  BU_CK_BITV(solidbits);
1292  RT_CK_PT(pp);
1293 
1294  for (BU_PTBL_FOR(regpp, (struct region **), regiontable)) {
1295  register struct region *regp;
1296 
1297  regp = *regpp;
1298  RT_CK_REGION(regp);
1299 
1300  /* Check region prerequisites */
1301  if (!rt_tree_test_ready(regp->reg_treetop, solidbits, regp, pp)) {
1302  return 0;
1303  }
1304  }
1305  return 1;
1306 }
1307 
1308 
1309 void
1310 rt_grow_boolstack(register struct resource *resp)
1311 {
1312  if (resp->re_boolstack == (union tree **)0 || resp->re_boolslen <= 0) {
1313  resp->re_boolslen = 128; /* default len */
1314  resp->re_boolstack = (union tree **)bu_malloc(sizeof(union tree *) * resp->re_boolslen, "initial boolstack");
1315  } else {
1316  resp->re_boolslen <<= 1;
1317  resp->re_boolstack = (union tree **)bu_realloc((char *)resp->re_boolstack, sizeof(union tree *) * resp->re_boolslen, "extend boolstack");
1318  }
1319 }
1320 
1321 
1322 /**
1323  * Using a stack to recall state, evaluate a boolean expression
1324  * without recursion.
1325  *
1326  * For use with XOR, a pointer to the "first valid subtree" would
1327  * be a useful addition, for rt_boolregions().
1328  *
1329  * Returns -
1330  * !0 tree is BOOL_TRUE
1331  * 0 tree is BOOL_FALSE
1332  * -1 tree is in error (GUARD)
1333  */
1334 int
1335 rt_booleval(register union tree *treep, struct partition *partp, struct region **trueregp, struct resource *resp)
1336 /* Tree to evaluate */
1337 /* Partition to evaluate */
1338 /* XOR true (and overlap) return */
1339 /* resource pointer for this CPU */
1340 {
1341  static union tree tree_not[MAX_PSW]; /* for OP_NOT nodes */
1342  static union tree tree_guard[MAX_PSW]; /* for OP_GUARD nodes */
1343  static union tree tree_xnop[MAX_PSW]; /* for OP_XNOP nodes */
1344  register union tree **sp;
1345  register int ret;
1346  register union tree **stackend;
1347 
1348  RT_CK_TREE(treep);
1349  RT_CK_PT(partp);
1350  RT_CK_RESOURCE(resp);
1351  if (treep->tr_op != OP_XOR)
1352  trueregp[0] = treep->tr_regionp;
1353  else
1354  trueregp[0] = trueregp[1] = REGION_NULL;
1355  while ((sp = resp->re_boolstack) == (union tree **)0)
1356  rt_grow_boolstack(resp);
1357  stackend = &(resp->re_boolstack[resp->re_boolslen]);
1358  *sp++ = TREE_NULL;
1359 stack:
1360  switch (treep->tr_op) {
1361  case OP_NOP:
1362  ret = 0;
1363  goto pop;
1364  case OP_SOLID:
1365  {
1366  register struct soltab *seek_stp = treep->tr_a.tu_stp;
1367  register struct seg **segpp;
1368  for (BU_PTBL_FOR(segpp, (struct seg **), &partp->pt_seglist)) {
1369  if ((*segpp)->seg_stp == seek_stp) {
1370  ret = 1;
1371  goto pop;
1372  }
1373  }
1374  ret = 0;
1375  }
1376  goto pop;
1377  case OP_UNION:
1378  case OP_INTERSECT:
1379  case OP_SUBTRACT:
1380  case OP_XOR:
1381  *sp++ = treep;
1382  if (sp >= stackend) {
1383  register int off = sp - resp->re_boolstack;
1384  rt_grow_boolstack(resp);
1385  sp = &(resp->re_boolstack[off]);
1386  stackend = &(resp->re_boolstack[resp->re_boolslen]);
1387  }
1388  treep = treep->tr_b.tb_left;
1389  goto stack;
1390  default:
1391  bu_log("rt_booleval: bad stack op [%d]\n", treep->tr_op);
1392  return BOOL_TRUE; /* screw up output */
1393  }
1394 pop:
1395  if ((treep = *--sp) == TREE_NULL)
1396  return ret; /* top of tree again */
1397  /*
1398  * Here, each operation will look at the operation just completed
1399  * (the left branch of the tree generally), and rewrite the top of
1400  * the stack and/or branch accordingly.
1401  */
1402  switch (treep->tr_op) {
1403  case OP_SOLID:
1404  bu_log("rt_booleval: pop SOLID?\n");
1405  return BOOL_TRUE; /* screw up output */
1406  case OP_UNION:
1407  if (ret) goto pop; /* BOOL_TRUE, we are done */
1408  /* lhs was false, rewrite as rhs tree */
1409  treep = treep->tr_b.tb_right;
1410  goto stack;
1411  case OP_INTERSECT:
1412  if (!ret) {
1413  ret = BOOL_FALSE;
1414  goto pop;
1415  }
1416  /* lhs was true, rewrite as rhs tree */
1417  treep = treep->tr_b.tb_right;
1418  goto stack;
1419  case OP_SUBTRACT:
1420  if (!ret) goto pop; /* BOOL_FALSE, we are done */
1421  /* lhs was true, rewrite as NOT of rhs tree */
1422  /* We introduce the special NOT operator here */
1423  tree_not[resp->re_cpu].tr_op = OP_NOT;
1424  *sp++ = &tree_not[resp->re_cpu];
1425  treep = treep->tr_b.tb_right;
1426  goto stack;
1427  case OP_NOT:
1428  /* Special operation for subtraction */
1429  ret = !ret;
1430  goto pop;
1431  case OP_XOR:
1432  if (ret) {
1433  /* lhs was true, rhs better not be, or we have an
1434  * overlap condition. Rewrite as guard node followed
1435  * by rhs.
1436  */
1437  if (treep->tr_b.tb_left->tr_regionp)
1438  trueregp[0] = treep->tr_b.tb_left->tr_regionp;
1439  tree_guard[resp->re_cpu].tr_op = OP_GUARD;
1440  treep = treep->tr_b.tb_right;
1441  *sp++ = treep; /* temp val for guard node */
1442  *sp++ = &tree_guard[resp->re_cpu];
1443  } else {
1444  /* lhs was false, rewrite as xnop node and result of
1445  * rhs.
1446  */
1447  tree_xnop[resp->re_cpu].tr_op = OP_XNOP;
1448  treep = treep->tr_b.tb_right;
1449  *sp++ = treep; /* temp val for xnop */
1450  *sp++ = &tree_xnop[resp->re_cpu];
1451  }
1452  goto stack;
1453  case OP_GUARD:
1454  /*
1455  * Special operation for XOR. lhs was true. If rhs
1456  * subtree was true, an overlap condition exists (both
1457  * sides of the XOR are BOOL_TRUE). Return error
1458  * condition. If subtree is false, then return BOOL_TRUE
1459  * (from lhs).
1460  */
1461  if (ret) {
1462  /* stacked temp val: rhs */
1463  if (sp[-1]->tr_regionp)
1464  trueregp[1] = sp[-1]->tr_regionp;
1465  return -1; /* GUARD error */
1466  }
1467  ret = BOOL_TRUE;
1468  sp--; /* pop temp val */
1469  goto pop;
1470  case OP_XNOP:
1471  /*
1472  * Special NOP for XOR. lhs was false. If rhs is true,
1473  * take note of its regionp.
1474  */
1475  sp--; /* pop temp val */
1476  if (ret) {
1477  if ((*sp)->tr_regionp)
1478  trueregp[0] = (*sp)->tr_regionp;
1479  }
1480  goto pop;
1481  default:
1482  bu_log("rt_booleval: bad pop op [%d]\n", treep->tr_op);
1483  return BOOL_TRUE; /* screw up output */
1484  }
1485  /* NOTREACHED */
1486 }
1487 
1488 
1489 int
1490 rt_boolfinal(struct partition *InputHdp, struct partition *FinalHdp, fastf_t startdist, fastf_t enddist, struct bu_ptbl *regiontable, struct application *ap, const struct bu_bitv *solidbits)
1491 {
1492  struct region *lastregion = (struct region *)NULL;
1493  struct region *TrueRg[2];
1494  register struct partition *pp;
1495  register int claiming_regions;
1496  int hits_avail = 0;
1497  int hits_needed;
1498  int ret = 0;
1499  int indefinite_outpt = 0;
1500  char *reason = (char *)NULL;
1501  fastf_t diff;
1502 
1503 #define HITS_TODO (hits_needed - hits_avail)
1504 
1505  RT_CK_PT_HD(InputHdp);
1506  RT_CK_PT_HD(FinalHdp);
1507  BU_CK_PTBL(regiontable);
1508  RT_CK_RTI(ap->a_rt_i);
1509  BU_CK_BITV(solidbits);
1510 
1512  bu_log("\nrt_boolfinal(%g, %g) x%d y%d lvl%d START\n",
1513  startdist, enddist,
1514  ap->a_x, ap->a_y, ap->a_level);
1515  }
1516 
1517  if (!ap->a_multioverlap)
1519 
1520  if (!ap->a_logoverlap)
1522 
1523  if (enddist <= 0) {
1524  reason = "not done, behind start point";
1525  ret = 0;
1526  goto out;
1527  }
1528 
1529  if (ap->a_onehit < 0)
1530  hits_needed = -ap->a_onehit;
1531  else
1532  hits_needed = ap->a_onehit;
1533 
1534  if (ap->a_onehit != 0) {
1535  register struct partition *npp = FinalHdp->pt_forw;
1536 
1537  for (; npp != FinalHdp; npp = npp->pt_forw) {
1538  if (npp->pt_inhit->hit_dist < 0.0)
1539  continue;
1540  if (ap->a_onehit < 0 && npp->pt_regionp->reg_aircode != 0)
1541  continue; /* skip air hits */
1542  hits_avail += 2; /* both in and out listed */
1543  }
1544  if (hits_avail >= hits_needed) {
1545  reason = "a_onehit request satisfied at outset";
1546  ret = 1;
1547  goto out;
1548  }
1549  }
1550 
1551  if (ap->a_no_booleans) {
1552  while ((pp = InputHdp->pt_forw) != InputHdp) {
1553  RT_CK_PT(pp);
1554  DEQUEUE_PT(pp);
1555  pp->pt_regionp = (struct region *)
1557  RT_CK_REGION(pp->pt_regionp);
1558  if (RT_G_DEBUG&DEBUG_PARTITION) {
1559  rt_pr_pt(ap->a_rt_i, pp);
1560  }
1561  INSERT_PT(pp, FinalHdp);
1562  }
1563  ret = 0;
1564  reason = "No a_onehit processing in a_no_booleans mode";
1565  goto out;
1566  }
1567 
1568  pp = InputHdp->pt_forw;
1569  while (pp != InputHdp) {
1570  RT_CK_PT(pp);
1571  claiming_regions = 0;
1572  if (RT_G_DEBUG&DEBUG_PARTITION) {
1573  bu_log("\nrt_boolfinal(%g, %g) x%d y%d lvl%d, next input pp\n",
1574  startdist, enddist,
1575  ap->a_x, ap->a_y, ap->a_level);
1576  rt_pr_pt(ap->a_rt_i, pp);
1577  }
1578  RT_CHECK_SEG(pp->pt_inseg);
1579  RT_CHECK_SEG(pp->pt_outseg);
1580 
1581  /* Force "very thin" partitions to have exactly zero thickness. */
1582  if (NEAR_EQUAL(pp->pt_inhit->hit_dist, pp->pt_outhit->hit_dist, ap->a_rt_i->rti_tol.dist)) {
1583  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log(
1584  "rt_boolfinal: Zero thickness partition, prims %s %s (%.18e, %.18e) x%d y%d lvl%d\n",
1585  pp->pt_inseg->seg_stp->st_name,
1586  pp->pt_outseg->seg_stp->st_name,
1587  pp->pt_inhit->hit_dist,
1588  pp->pt_outhit->hit_dist,
1589  ap->a_x, ap->a_y, ap->a_level);
1590  pp->pt_outhit->hit_dist = pp->pt_inhit->hit_dist;
1591  }
1592 
1593 
1594  /* Sanity checks on sorting. */
1595  if (pp->pt_inhit->hit_dist > pp->pt_outhit->hit_dist) {
1596  bu_log("rt_boolfinal: inverted partition %p x%d y%d lvl%d\n",
1597  (void *)pp,
1598  ap->a_x, ap->a_y, ap->a_level);
1599  rt_pr_partitions(ap->a_rt_i, InputHdp, "With problem");
1600  }
1601  if (pp->pt_forw != InputHdp) {
1602  diff = pp->pt_outhit->hit_dist - pp->pt_forw->pt_inhit->hit_dist;
1603  if (!ZERO(diff)) {
1604  if (NEAR_ZERO(diff, ap->a_rt_i->rti_tol.dist)) {
1605  if (RT_G_DEBUG&DEBUG_PARTITION) bu_log("rt_boolfinal: fusing 2 partitions %p %p\n",
1606  (void *)pp, (void *)pp->pt_forw);
1608  } else if (diff > 0) {
1609  bu_log("rt_boolfinal: sorting defect %e > %e! x%d y%d lvl%d, diff = %g\n",
1610  pp->pt_outhit->hit_dist,
1611  pp->pt_forw->pt_inhit->hit_dist,
1612  ap->a_x, ap->a_y, ap->a_level, diff);
1613  bu_log("sort defect is between parts %p and %p\n",
1614  (void *)pp, (void *)pp->pt_forw);
1615  if (!(RT_G_DEBUG & DEBUG_PARTITION))
1616  rt_pr_partitions(ap->a_rt_i, InputHdp, "With DEFECT");
1617  ret = 0;
1618  reason = "ERROR, sorting defect, give up";
1619  goto out;
1620  }
1621  }
1622  }
1623 
1624  /*
1625  * If partition is behind ray start point, discard it.
1626  *
1627  * Partition may start before current box starts, because it's
1628  * still waiting for all its solids to be shot.
1629  */
1630  if (pp->pt_outhit->hit_dist < ap->a_rt_i->rti_tol.dist) {
1631  register struct partition *zap_pp;
1632  if (RT_G_DEBUG&DEBUG_PARTITION)
1633  bu_log("discarding partition %p behind ray start, out dist=%g\n",
1634  (void *)pp, pp->pt_outhit->hit_dist);
1635  zap_pp = pp;
1636  pp = pp->pt_forw;
1637  DEQUEUE_PT(zap_pp);
1638  FREE_PT(zap_pp, ap->a_resource);
1639  continue;
1640  }
1641 
1642  /*
1643  * If partition begins beyond current box end, the state of
1644  * the partition is not fully known yet, and new partitions
1645  * might be added in front of this one, so stop now.
1646  */
1647  diff = pp->pt_inhit->hit_dist - enddist;
1648  if (diff > ap->a_rt_i->rti_tol.dist) {
1649  if (RT_G_DEBUG&DEBUG_PARTITION)
1650  bu_log("partition begins %g beyond current box end, returning\n", diff);
1651  reason = "partition begins beyond current box end";
1652  ret = 0;
1653  goto out;
1654  }
1655 
1656  /*
1657  * If partition ends somewhere beyond the end of the current
1658  * box, the condition of the outhit information is not fully
1659  * known yet. The partition might be broken or shortened by
1660  * subsequent segments, not discovered until entering future
1661  * boxes.
1662  */
1663  diff = pp->pt_outhit->hit_dist - enddist;
1664  if (diff > ap->a_rt_i->rti_tol.dist) {
1665  if (RT_G_DEBUG&DEBUG_PARTITION)
1666  bu_log("partition ends beyond current box end\n");
1667  if (ap->a_onehit != 1) {
1668  ret = 0;
1669  reason = "a_onehit != 1, trace remaining boxes";
1670  goto out;
1671  }
1672  /* pt_outhit may not be correct */
1673  indefinite_outpt = 1;
1674  } else {
1675  indefinite_outpt = 0;
1676  }
1677 
1678  /* XXX a_ray_length checking should be done here, not in
1679  * rt_shootray()
1680  */
1681 
1682  /* Start with a clean slate when evaluating this partition */
1683  bu_ptbl_reset(regiontable);
1684 
1685  /*
1686  * For each segment's solid that lies in this partition, add
1687  * the list of regions that refer to that solid into the
1688  * "regiontable" array.
1689  */
1690  {
1691  struct seg **segpp;
1692 
1693  if (RT_G_DEBUG&DEBUG_PARTITION)
1694  bu_log("Building region table:\n");
1695  for (BU_PTBL_FOR(segpp, (struct seg **), &pp->pt_seglist)) {
1696  struct soltab *stp = (*segpp)->seg_stp;
1697  RT_CK_SOLTAB(stp);
1698  bu_ptbl_cat_uniq(regiontable, &stp->st_regions);
1699  }
1700  }
1701 
1702  if (RT_G_DEBUG&DEBUG_PARTITION) {
1703  struct region **regpp;
1704  bu_log("Region table for this partition:\n");
1705  for (BU_PTBL_FOR(regpp, (struct region **), regiontable)) {
1706  register struct region *regp;
1707 
1708  regp = *regpp;
1709  RT_CK_REGION(regp);
1710  bu_log("%p %s\n", (void *)regp, regp->reg_name);
1711  }
1712  }
1713 
1714  if (indefinite_outpt) {
1715  if (RT_G_DEBUG&DEBUG_PARTITION)
1716  bu_log("indefinite out point, checking partition eligibility for early evaluation.\n");
1717  /*
1718  * More hits still needed. HITS_TODO > 0. If every solid
1719  * in every region participating in this partition has
1720  * been intersected, then it is OK to evaluate it now.
1721  */
1722  if (!rt_bool_partition_eligible(regiontable, solidbits, pp)) {
1723  ret = 0;
1724  reason = "Partition not yet eligible for evaluation";
1725  goto out;
1726  }
1727  if (RT_G_DEBUG&DEBUG_PARTITION)
1728  bu_log("Partition is eligible for evaluation.\n");
1729  }
1730 
1731  /* Evaluate the boolean trees of any regions involved */
1732  {
1733  struct region **regpp;
1734  for (BU_PTBL_FOR(regpp, (struct region **), regiontable)) {
1735  register struct region *regp;
1736 
1737  regp = *regpp;
1738  RT_CK_REGION(regp);
1739  if (RT_G_DEBUG&DEBUG_PARTITION) {
1740  rt_pr_tree_val(regp->reg_treetop, pp, 2, 0);
1741  rt_pr_tree_val(regp->reg_treetop, pp, 1, 0);
1742  rt_pr_tree_val(regp->reg_treetop, pp, 0, 0);
1743  bu_log("%p=bit%d, %s: ", (void *)regp, regp->reg_bit, regp->reg_name);
1744  }
1745  if (regp->reg_all_unions) {
1746  if (RT_G_DEBUG&DEBUG_PARTITION)
1747  bu_log("BOOL_TRUE (all union)\n");
1748  claiming_regions++;
1749  lastregion = regp;
1750  continue;
1751  }
1752  if (rt_booleval(regp->reg_treetop, pp, TrueRg,
1753  ap->a_resource) == BOOL_FALSE) {
1754  if (RT_G_DEBUG&DEBUG_PARTITION)
1755  bu_log("BOOL_FALSE\n");
1756  /* Null out non-claiming region's pointer */
1757  *regpp = REGION_NULL;
1758  continue;
1759  }
1760  /* This region claims partition */
1761  if (RT_G_DEBUG&DEBUG_PARTITION)
1762  bu_log("BOOL_TRUE (eval)\n");
1763  claiming_regions++;
1764  lastregion = regp;
1765  }
1766  }
1767  if (RT_G_DEBUG&DEBUG_PARTITION)
1768  bu_log("rt_boolfinal: claiming_regions=%d (%g <-> %g)\n",
1769  claiming_regions, pp->pt_inhit->hit_dist, pp->pt_outhit->hit_dist);
1770  if (claiming_regions == 0) {
1771  if (RT_G_DEBUG&DEBUG_PARTITION)
1772  bu_log("rt_boolfinal moving past partition %p\n", (void *)pp);
1773  pp = pp->pt_forw; /* onwards! */
1774  continue;
1775  }
1776 
1777  if (claiming_regions > 1) {
1778  /*
1779  * There is an overlap between two or more regions, invoke
1780  * multi-overlap handler.
1781  */
1782  if (RT_G_DEBUG&DEBUG_PARTITION)
1783  bu_log("rt_boolfinal: invoking a_multioverlap() pp=%p\n", (void *)pp);
1784  bu_ptbl_rm(regiontable, (long *)NULL);
1785  ap->a_logoverlap(ap, pp, regiontable, InputHdp);
1786  ap->a_multioverlap(ap, pp, regiontable, InputHdp);
1787 
1788  /* Count number of remaining regions, s/b 0 or 1 */
1789  claiming_regions = 0;
1790  {
1791  register struct region **regpp;
1792  for (BU_PTBL_FOR(regpp, (struct region **), regiontable)) {
1793  if (*regpp != REGION_NULL) {
1794  claiming_regions++;
1795  lastregion = *regpp;
1796  }
1797  }
1798  }
1799 
1800  /*
1801  * If claiming_regions == 0, discard partition.
1802  * If claiming_regions > 1, signal error and discard.
1803  * There is nothing further we can do to fix it.
1804  */
1805  if (claiming_regions > 1) {
1806  bu_log("rt_boolfinal() a_multioverlap() failed to resolve overlap, discarding bad partition:\n");
1807  rt_pr_pt(ap->a_rt_i, pp);
1808  }
1809 
1810  if (claiming_regions != 1) {
1811  register struct partition *zap_pp;
1812 
1813  if (RT_G_DEBUG&DEBUG_PARTITION)
1814  bu_log("rt_boolfinal discarding overlap partition %p\n", (void *)pp);
1815  zap_pp = pp;
1816  pp = pp->pt_forw; /* onwards! */
1817  DEQUEUE_PT(zap_pp);
1818  FREE_PT(zap_pp, ap->a_resource);
1819  continue;
1820  }
1821  }
1822 
1823  /*
1824  * claiming_regions == 1
1825  *
1826  * Remove this partition from the input queue, and append it
1827  * to the result queue.
1828  */
1829  {
1830  register struct partition *newpp;
1831  register struct partition *lastpp;
1832  if (RT_G_DEBUG&DEBUG_PARTITION)
1833  bu_log("Appending partition to result queue: %g, %g\n",
1834  pp->pt_inhit->hit_dist, pp->pt_outhit->hit_dist);
1835  newpp = pp;
1836  pp=pp->pt_forw; /* onwards! */
1837  DEQUEUE_PT(newpp);
1838  RT_CHECK_SEG(newpp->pt_inseg); /* sanity */
1839  RT_CHECK_SEG(newpp->pt_outseg); /* sanity */
1840  /* Record the "owning" region. pt_regionp = NULL before here. */
1841  newpp->pt_regionp = lastregion;
1842 
1843  /* See if this new partition extends the previous last
1844  * partition, "exactly" matching.
1845  */
1846  lastpp = FinalHdp->pt_back;
1847  if (lastpp != FinalHdp &&
1848  lastregion == lastpp->pt_regionp &&
1849  NEAR_EQUAL(newpp->pt_inhit->hit_dist,
1850  lastpp->pt_outhit->hit_dist,
1851  ap->a_rt_i->rti_tol.dist) &&
1852  (ap->a_rt_i->rti_save_overlaps == 0 ||
1854  lastpp->pt_overlap_reg,
1855  newpp->pt_overlap_reg))
1856  ) {
1857  /* same region, merge by extending last final partition */
1858  if (RT_G_DEBUG&DEBUG_PARTITION)
1859  bu_log("rt_boolfinal 'exact match', extending last partition, discarding %p\n", (void *)newpp);
1860  RT_CK_PT(lastpp);
1861  RT_CHECK_SEG(lastpp->pt_inseg); /* sanity */
1862  RT_CHECK_SEG(lastpp->pt_outseg);/* sanity */
1863  if (RT_G_DEBUG&DEBUG_PARTITION)
1864  bu_log("rt_boolfinal collapsing %p %p\n", (void *)lastpp, (void *)newpp);
1865  lastpp->pt_outhit = newpp->pt_outhit;
1866  lastpp->pt_outflip = newpp->pt_outflip;
1867  lastpp->pt_outseg = newpp->pt_outseg;
1868 
1869  /* Don't lose the fact that the two solids of this
1870  * partition contributed.
1871  */
1872  bu_ptbl_ins_unique(&lastpp->pt_seglist, (long *)newpp->pt_inseg);
1873  bu_ptbl_ins_unique(&lastpp->pt_seglist, (long *)newpp->pt_outseg);
1874 
1875  FREE_PT(newpp, ap->a_resource);
1876  newpp = lastpp;
1877  } else {
1878  APPEND_PT(newpp, lastpp);
1879  if (!(ap->a_onehit < 0 && newpp->pt_regionp->reg_aircode != 0))
1880  hits_avail += 2;
1881  }
1882 
1883  RT_CHECK_SEG(newpp->pt_inseg); /* sanity */
1884  RT_CHECK_SEG(newpp->pt_outseg); /* sanity */
1885  }
1886 
1887  /* See if it's worthwhile breaking out of partition loop early */
1888  if (ap->a_onehit != 0 && HITS_TODO <= 0) {
1889  ret = 1;
1890  if (pp == InputHdp)
1891  reason = "a_onehit satisfied at bottom";
1892  else
1893  reason = "a_onehit satisfied early";
1894  goto out;
1895  }
1896  }
1897  if (ap->a_onehit != 0 && HITS_TODO <= 0) {
1898  ret = 1;
1899  reason = "a_onehit satisfied at end";
1900  } else {
1901  ret = 0;
1902  reason = "more partitions needed";
1903  }
1904 out:
1905  if (RT_G_DEBUG&DEBUG_PARTITION) {
1906  bu_log("rt_boolfinal() ret=%d, %s\n", ret, reason);
1907  rt_pr_partitions(ap->a_rt_i, FinalHdp, "rt_boolfinal: Final partition list at return:");
1908  rt_pr_partitions(ap->a_rt_i, InputHdp, "rt_boolfinal: Input/pending partition list at return:");
1909  bu_log("rt_boolfinal() ret=%d, %s\n", ret, reason);
1910  }
1911  return ret;
1912 }
1913 
1914 
1915 double
1916 rt_reldiff(double a, double b)
1917 {
1918  register fastf_t d;
1919  register fastf_t diff;
1920 
1921  /* d = Max(Abs(a), Abs(b)) */
1922  d = (a >= 0.0) ? a : -a;
1923  if (b >= 0.0) {
1924  if (b > d) d = b;
1925  } else {
1926  if ((-b) > d) d = (-b);
1927  }
1928  if (ZERO(d))
1929  return 0.0;
1930  if ((diff = a - b) < 0.0) diff = -diff;
1931  return diff / d;
1932 }
1933 
1934 
1935 int
1936 rt_partition_len(const struct partition *partheadp)
1937 {
1938  register struct partition *pp;
1939  register long count = 0;
1940 
1941  pp = partheadp->pt_forw;
1942  if (pp == PT_NULL)
1943  return 0; /* Header not initialized yet */
1944  for (; pp != partheadp; pp = pp->pt_forw) {
1945  if (pp->pt_magic != 0) {
1946  /* Partitions on the free queue have pt_magic = 0 */
1947  RT_CK_PT(pp);
1948  }
1949  if (++count > 1000000) bu_bomb("partition length > 10000000 elements\n");
1950  }
1951  return (int)count;
1952 }
1953 
1954 
1955 void
1956 rt_rebuild_overlaps(struct partition *PartHdp, struct application *ap, int rebuild_fastgen_plates_only)
1957 {
1958  struct partition *pp, *next, *curr;
1959  struct region *pp_reg;
1960  struct partition *pp_open;
1961  struct bu_ptbl open_parts;
1962  int i, j;
1963 
1964  RT_CK_PT_HD(PartHdp);
1965  RT_CK_AP(ap);
1966 
1967  bu_ptbl_init(&open_parts, 0, "Open partitions");
1968 
1969  pp = PartHdp->pt_forw;
1970  while (pp != PartHdp) {
1971  RT_CK_PARTITION(pp);
1972  next = pp->pt_forw;
1973 
1974  if (rebuild_fastgen_plates_only && pp->pt_regionp->reg_is_fastgen != REGION_FASTGEN_PLATE) {
1975  bu_ptbl_trunc(&open_parts, 0);
1976  pp = next;
1977  continue;
1978  }
1979 
1980  for (i=0; i<BU_PTBL_END(&open_parts); i++) {
1981  int keep_open=0;
1982 
1983  if (!pp)
1984  break;
1985 
1986  pp_open = (struct partition *)BU_PTBL_GET(&open_parts, i);
1987  if (!pp_open)
1988  continue;
1989  RT_CK_PARTITION(pp_open);
1990 
1991  if (pp->pt_overlap_reg) {
1992  j = -1;
1993  while ((pp_reg = pp->pt_overlap_reg[++j])) {
1994  if (pp_reg == (struct region *)(-1))
1995  continue;
1996  RT_CK_REGION(pp_reg);
1997 
1998  if (pp_reg == pp_open->pt_regionp) {
1999  /* add this partition to pp_open */
2000  pp_open->pt_outseg = pp->pt_outseg;
2001  pp_open->pt_outhit = pp->pt_outhit;
2002  pp_open->pt_outflip = pp->pt_outflip;
2003  bu_ptbl_cat_uniq(&pp_open->pt_seglist, &pp->pt_seglist);
2004 
2005  /* mark it as used */
2006  pp->pt_overlap_reg[j] = (struct region *)(-1);
2007  if (pp_reg == pp->pt_regionp)
2008  pp->pt_regionp = (struct region *)NULL;
2009 
2010  /* keep pp_open open */
2011  keep_open = 1;
2012  }
2013  }
2014  } else {
2015  if (pp->pt_regionp == pp_open->pt_regionp && pp->pt_inhit->hit_dist <= pp_open->pt_outhit->hit_dist) {
2016  /* add this partition to pp_open */
2017  pp_open->pt_outseg = pp->pt_outseg;
2018  pp_open->pt_outhit = pp->pt_outhit;
2019  pp_open->pt_outflip = pp->pt_outflip;
2020  bu_ptbl_cat_uniq(&pp_open->pt_seglist, &pp->pt_seglist);
2021 
2022  /* eliminate this partition */
2023  BU_LIST_DEQUEUE((struct bu_list *)pp)
2024  pp->pt_overlap_reg = NULL; /* sanity */
2025  pp = (struct partition *)NULL;
2026 
2027  /* keep pp_open open */
2028  keep_open = 1;
2029  }
2030  }
2031 
2032  if (!keep_open) {
2033  BU_PTBL_CLEAR_I(&open_parts, i);
2034  }
2035  }
2036 
2037  /* if all region claims have been removed, eliminate the partition */
2038  if (pp && pp->pt_overlap_reg) {
2039  int reg_count=0;
2040 
2041  /* count remaining region claims */
2042  j = -1;
2043  while ((pp_reg = pp->pt_overlap_reg[++j]))
2044  if (pp_reg != (struct region *)(-1)) {
2045  RT_CK_REGION(pp_reg);
2046  reg_count++;
2047  }
2048 
2049  if (!reg_count) {
2050  BU_LIST_DEQUEUE((struct bu_list *)pp)
2051  bu_free((char *)pp->pt_overlap_reg, "overlap list");
2052  pp->pt_overlap_reg = NULL; /* sanity */
2053  pp = (struct partition *)NULL;
2054  }
2055  }
2056 
2057  /* any remaining region claims must produce new partitions */
2058  if (pp) {
2059  if (pp->pt_overlap_reg) {
2060  j = -1;
2061  curr = pp;
2062  while ((pp_reg = pp->pt_overlap_reg[++j])) {
2063  struct partition *new_pp;
2064 
2065  if (pp_reg == (struct region *)(-1))
2066  continue;
2067  RT_CK_REGION(pp_reg);
2068 
2069  if (rebuild_fastgen_plates_only &&
2071  continue;
2072 
2073  /* if the original partition is available, just use it */
2074  if (!pp->pt_regionp || pp->pt_regionp == pp_reg) {
2075  pp->pt_regionp = pp_reg;
2076  bu_ptbl_ins(&open_parts, (long *)pp);
2077  } else {
2078  /* create a new partition, link it to the end of the current pp,
2079  * and add it to the open list */
2080  RT_DUP_PT(ap->a_rt_i, new_pp, pp, ap->a_resource)
2081  new_pp->pt_regionp = pp_reg;
2082  new_pp->pt_overlap_reg = (struct region **)NULL;
2083  BU_LIST_APPEND((struct bu_list *)curr, (struct bu_list *)new_pp)
2084  bu_ptbl_ins(&open_parts, (long *)new_pp);
2085  curr = new_pp;
2086  }
2087  }
2088  } else {
2089  if (rebuild_fastgen_plates_only) {
2091  bu_ptbl_ins(&open_parts, (long *)pp);
2092  }
2093  } else {
2094  bu_ptbl_ins(&open_parts, (long *)pp);
2095  }
2096  }
2097  if (pp->pt_overlap_reg) {
2098  bu_free((char *)pp->pt_overlap_reg, "overlap list");
2099  pp->pt_overlap_reg = (struct region **)NULL;
2100  }
2101  }
2102  pp = next;
2103  }
2104 
2105  bu_ptbl_free(&open_parts);
2106 }
2107 
2108 
2109 /*
2110  * Local Variables:
2111  * mode: C
2112  * tab-width: 8
2113  * indent-tabs-mode: t
2114  * c-file-style: "stroustrup"
2115  * End:
2116  * ex: shiftwidth=4 tabstop=8
2117  */
struct xray a_ray
Actual ray to be shot.
Definition: raytrace.h:1583
int reg_bit
constant index into Regions[]
Definition: raytrace.h:541
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_LIST_INSERT(old, new)
Definition: list.h:183
struct region * pt_regionp
ptr to containing region
Definition: raytrace.h:580
struct hit * pt_outhit
OUT hit ptr.
Definition: raytrace.h:579
struct hit seg_in
IN information.
Definition: raytrace.h:370
void rt_fastgen_plate_vol_overlap(struct region **fr1, struct region **fr2, struct partition *pp, struct application *ap)
Definition: bool.c:852
uint32_t pt_magic
sanity check
Definition: raytrace.h:573
Definition: list.h:118
#define REGION_FASTGEN_PLATE
Definition: raytrace.h:554
int rt_tree_test_ready(register const union tree *tp, register const struct bu_bitv *solidbits, register const struct region *regionp, register const struct partition *pp)
Definition: bool.c:1236
#define BU_PTBL_INIT_ZERO
Definition: ptbl.h:92
int rt_bool_partition_eligible(register const struct bu_ptbl *regiontable, register const struct bu_bitv *solidbits, register const struct partition *pp)
Definition: bool.c:1286
#define RT_CK_RTI(_p)
Definition: raytrace.h:1833
#define OP_NOP
Leaf with no effect.
Definition: raytrace.h:1132
void rt_silent_logoverlap(struct application *ap, const struct partition *pp, const struct bu_ptbl *regiontable, const struct partition *InputHdp)
Definition: bool.c:1122
struct region ** pt_overlap_reg
NULL-terminated array of overlapping regions. NULL if no overlap.
Definition: raytrace.h:583
double dist
>= 0
Definition: tol.h:73
#define BU_PTBL_FOR(ip, cast, ptbl)
Definition: ptbl.h:125
union tree ** re_boolstack
Stack for rt_booleval()
Definition: raytrace.h:1455
struct soltab * seg_stp
pointer back to soltab
Definition: raytrace.h:372
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
#define OP_XOR
Binary: L xor R, not both.
Definition: raytrace.h:1130
#define RT_CK_SEG(_p)
Definition: raytrace.h:377
short reg_all_unions
1=boolean tree is all unions
Definition: raytrace.h:551
Definition: raytrace.h:368
Definition: raytrace.h:248
void(* a_multioverlap)(struct application *, struct partition *, struct bu_ptbl *, struct partition *)
called to resolve overlaps
Definition: raytrace.h:1593
int bu_ptbl_rm(struct bu_ptbl *b, const long *p)
#define RT_SEG_NULL
Definition: raytrace.h:374
fastf_t st_aradius
Radius of APPROXIMATING sphere.
Definition: raytrace.h:433
char pt_inflip
flip inhit->hit_normal
Definition: raytrace.h:581
Header file for the BRL-CAD common definitions.
#define HITS_TODO
int bu_ptbl_ins_unique(struct bu_ptbl *b, long *p)
#define BU_CK_PTBL(_p)
Definition: ptbl.h:74
#define OP_XNOP
Unary: L, mark region.
Definition: raytrace.h:1136
#define RT_CK_RAY(_p)
Definition: raytrace.h:224
struct seg * pt_outseg
OUT seg pointer.
Definition: raytrace.h:578
const char * reg_name
Identifying string.
Definition: raytrace.h:539
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
struct resource * a_resource
dynamic memory resources
Definition: raytrace.h:1591
char pt_outflip
flip outhit->hit_normal
Definition: raytrace.h:582
int index
Which ray of a bundle.
Definition: raytrace.h:217
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
int a_onehit
flag to stop on first hit
Definition: raytrace.h:1586
#define MAX_FASTF
Definition: defines.h:340
#define RT_CK_REGION(_p)
Definition: raytrace.h:559
int rt_overlap_tables_equal(struct region *const *a, struct region *const *b)
Definition: bool.c:1195
void bu_ptbl_reset(struct bu_ptbl *b)
Definition: ptbl.c:49
#define HIT_NULL
Definition: raytrace.h:258
struct hit * pt_inhit
IN hit pointer.
Definition: raytrace.h:577
#define RT_DUP_PT(ip, new, old, res)
Definition: raytrace.h:599
union tree * tb_left
Definition: raytrace.h:1149
struct bu_list l
Definition: raytrace.h:369
struct soltab * tu_stp
Definition: raytrace.h:1156
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
Definition: ptbl.h:62
size_t counter[MAX_PSW]
Definition: bu_parallel.c:42
long st_bit
solids bit vector index (const)
Definition: raytrace.h:439
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
#define OP_SUBTRACT
Binary: L subtract R.
Definition: raytrace.h:1129
Definition: color.c:49
struct bu_ptbl pt_seglist
all segs in this partition
Definition: raytrace.h:584
struct rt_i * a_rt_i
this librt instance
Definition: raytrace.h:1588
int rt_booleval(register union tree *treep, struct partition *partp, struct region **trueregp, struct resource *resp)
Definition: bool.c:1335
short reg_is_fastgen
FASTGEN-compatibility mode?
Definition: raytrace.h:552
#define RT_CHECK_SEG(_p)
Definition: raytrace.h:376
#define DEBUG_PARTITION
14 Info about bool_weave()
Definition: raytrace.h:99
#define OP_INTERSECT
Binary: L intersect R.
Definition: raytrace.h:1128
#define RT_G_DEBUG
Definition: raytrace.h:1718
#define BU_BITTEST(_bv, bit)
Definition: bitv.h:168
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
#define RT_CK_HIT(_p)
Definition: raytrace.h:259
#define BU_PTBL_GET(ptbl, i)
Definition: ptbl.h:108
#define GET_PT_INIT(ip, p, res)
Definition: raytrace.h:606
void rt_pr_region(const struct region *rp)
#define RT_CK_AP(_p)
Definition: raytrace.h:1674
#define TREE_NULL
Definition: raytrace.h:1181
int a_x
Screen X of ray, if applicable.
Definition: raytrace.h:1596
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
void bu_ptbl_cat_uniq(struct bu_ptbl *dest, const struct bu_ptbl *src)
Definition: ptbl.c:203
struct seg * pt_inseg
IN seg ptr (gives stp)
Definition: raytrace.h:576
void rt_default_multioverlap(struct application *ap, struct partition *pp, struct bu_ptbl *regiontable, struct partition *InputHdp)
Definition: bool.c:913
struct hit seg_out
OUT information.
Definition: raytrace.h:371
void bu_ptbl_trunc(struct bu_ptbl *tbl, int end)
Definition: ptbl.c:267
struct xray * hit_rayp
pointer to defining ray
Definition: raytrace.h:256
#define PT_NULL
Definition: raytrace.h:586
#define BOOL_TRUE
Definition: bool.c:50
#define REGION_FASTGEN_VOLUME
Definition: raytrace.h:555
int a_level
recursion level (for printing)
Definition: raytrace.h:1595
struct tree::tree_node tr_b
char ft_name[17]
Definition: raytrace.h:2043
void * bu_realloc(void *ptr, size_t siz, const char *str)
#define UNUSED(parameter)
Definition: common.h:239
#define OP_GUARD
Unary: not L, or else!
Definition: raytrace.h:1135
void rt_pr_partitions(const struct rt_i *rtip, const struct partition *phead, const char *title)
void rt_rebuild_overlaps(struct partition *PartHdp, struct application *ap, int rebuild_fastgen_plates_only)
Definition: bool.c:1956
#define PT_HD_MAGIC
Definition: magic.h:208
goto out
Definition: nmg_mod.c:3846
void rt_pr_seg(const struct seg *segp)
struct partition * pt_back
backwards link
Definition: raytrace.h:575
int(* a_overlap)(struct application *, struct partition *, struct region *, struct region *, struct partition *)
DEPRECATED.
Definition: raytrace.h:1592
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
void rt_pr_hit(const char *str, const struct hit *hitp)
struct bu_ptbl st_regions
ptrs to regions using this solid (const)
Definition: raytrace.h:440
#define RT_AFN_NULL
Definition: raytrace.h:1673
vect_t r_dir
Direction of ray (UNIT Length)
Definition: raytrace.h:219
#define BU_PTBL_CLEAR_I(_ptbl, _i)
Definition: ptbl.h:111
void rt_get_region_seglist_for_partition(struct bu_ptbl *sl, const struct partition *pp, const struct region *regp)
Definition: bool.c:637
#define BU_PTBL_LEN(ptbl)
Definition: ptbl.h:107
void bu_ptbl_free(struct bu_ptbl *b)
Definition: ptbl.c:226
struct bn_tol rti_tol
Math tolerances for this model.
Definition: raytrace.h:1765
#define DEQUEUE_PT(_cur)
Definition: raytrace.h:648
void rt_pr_tree_val(const union tree *tp, const struct partition *partp, int pr_name, int lvl)
int rti_save_overlaps
1=fill in pt_overlap_reg, change boolweave behavior
Definition: raytrace.h:1757
union tree * tb_right
Definition: raytrace.h:1150
#define ZERO(val)
Definition: units.c:38
HIDDEN int code(fastf_t x, fastf_t y)
Definition: clip.c:43
void(* a_logoverlap)(struct application *, const struct partition *, const struct bu_ptbl *, const struct partition *)
called to log overlaps
Definition: raytrace.h:1594
point_t r_pt
Point at which ray starts.
Definition: raytrace.h:218
void rt_default_logoverlap(struct application *ap, const struct partition *pp, const struct bu_ptbl *regiontable, const struct partition *InputHdp)
Definition: bool.c:1132
#define REGION_NON_FASTGEN
Definition: raytrace.h:553
int rt_defoverlap(register struct application *ap, register struct partition *pp, struct region *reg1, struct region *reg2, struct partition *pheadp)
Definition: bool.c:597
void bu_ptbl_zero(struct bu_ptbl *b, const long *p)
void rt_boolweave(struct seg *out_hd, struct seg *in_hd, struct partition *PartHdp, struct application *ap)
Definition: bool.c:145
int reg_aircode
Region ID AIR code.
Definition: raytrace.h:543
void rt_fastgen_vol_vol_overlap(struct region **fr1, struct region **fr2, const struct partition *pp)
Definition: bool.c:720
const struct rt_functab OBJ[]
Definition: table.c:159
#define RT_CK_RESOURCE(_p)
Definition: raytrace.h:1490
#define BU_PTBL_END(ptbl)
Definition: ptbl.h:106
size_t nsolids
total # of solids participating
Definition: raytrace.h:1783
#define RT_CK_PT(_p)
Definition: raytrace.h:589
int a_y
Screen Y of ray, if applicable.
Definition: raytrace.h:1597
#define RT_CK_PT_HD(_p)
Definition: raytrace.h:591
#define RT_CK_SOLTAB(_p)
Definition: raytrace.h:453
int a_no_booleans
1= partitions==segs, no booleans
Definition: raytrace.h:1602
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
#define REGION_NULL
Definition: raytrace.h:558
void bu_vls_extend(struct bu_vls *vp, size_t extra)
Definition: vls.c:136
long re_boolslen
elements in re_boolstack[]
Definition: raytrace.h:1456
#define BU_PTBL_BASEADDR(ptbl)
Definition: ptbl.h:104
void rt_grow_boolstack(register struct resource *resp)
Definition: bool.c:1310
union tree * reg_treetop
Pointer to boolean tree.
Definition: raytrace.h:540
int rt_fdiff(double a, double b)
Definition: bool.c:789
#define DEBUG_FDIFF
19 bool/fdiff debugging
Definition: raytrace.h:104
Definition: color.c:51
#define RT_CK_PARTITION(_p)
Definition: raytrace.h:590
int hit_surfno
solid-specific surface indicator
Definition: raytrace.h:255
#define APPEND_PT(_new, _old)
Definition: raytrace.h:645
int re_cpu
processor number, for ID
Definition: raytrace.h:1442
#define INSERT_PT(_new, _old)
Definition: raytrace.h:642
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define RT_CK_TREE(_p)
Definition: raytrace.h:1182
#define OP_SOLID
Leaf: tr_stp -> solid.
Definition: raytrace.h:1126
int rt_boolfinal(struct partition *InputHdp, struct partition *FinalHdp, fastf_t startdist, fastf_t enddist, struct bu_ptbl *regiontable, struct application *ap, const struct bu_bitv *solidbits)
Definition: bool.c:1490
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
#define FREE_PT(p, res)
Definition: raytrace.h:622
int st_id
Solid ident.
Definition: raytrace.h:431
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
Definition: bitv.h:105
struct partition * pt_forw
forwards link
Definition: raytrace.h:574
fastf_t hit_dist
dist from r_pt to hit_point
Definition: raytrace.h:250
Definition: vls.h:56
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
int rt_partition_len(const struct partition *partheadp)
Definition: bool.c:1936
#define BOOL_FALSE
Definition: bool.c:49
double fastf_t
Definition: defines.h:300
#define OP_UNION
Binary: L union R.
Definition: raytrace.h:1127
#define BU_CK_BITV(_bp)
Definition: bitv.h:116
#define VPRINT(a, b)
Definition: raytrace.h:1881
void bu_vls_putc(struct bu_vls *vp, int c)
Definition: vls.c:666
#define OP_NOT
Unary: not L.
Definition: raytrace.h:1134
struct tree::tree_leaf tr_a
void rt_pr_pt(const struct rt_i *rtip, const struct partition *pp)
void rt_weave0seg(struct seg *segp, struct partition *PartHdp, struct application *ap)
Definition: bool.c:62
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
int rt_tree_max_raynum(register const union tree *tp, register const struct partition *pp)
Definition: bool.c:671
double rt_reldiff(double a, double b)
Definition: bool.c:1916
#define tr_regionp
Definition: raytrace.h:1179