BRL-CAD
cut.c
Go to the documentation of this file.
1 /* C U T . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1990-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/cut.c
23  *
24  * Cut space into lots of small boxes (RPPs actually).
25  *
26  * Call tree for default path through the code:
27  * rt_cut_it()
28  * rt_cut_extend() for all solids in model
29  * rt_ct_optim()
30  * rt_ct_old_assess()
31  * rt_ct_box()
32  * rt_ct_populate_box()
33  * rt_ck_overlap()
34  *
35  */
36 /** @} */
37 
38 #include "common.h"
39 
40 #include <stdlib.h>
41 #include <math.h>
42 #include <string.h>
43 #include "bio.h"
44 
45 #include "bu/parallel.h"
46 #include "bu/sort.h"
47 #include "vmath.h"
48 #include "raytrace.h"
49 #include "plot3.h"
50 
51 
52 HIDDEN int rt_ck_overlap(const vect_t min, const vect_t max, const struct soltab *stp, const struct rt_i *rtip);
53 HIDDEN int rt_ct_box(struct rt_i *rtip, union cutter *cutp, int axis, double where, int force);
54 HIDDEN void rt_ct_optim(struct rt_i *rtip, union cutter *cutp, size_t depth);
55 HIDDEN void rt_ct_free(struct rt_i *rtip, union cutter *cutp);
56 HIDDEN void rt_ct_release_storage(union cutter *cutp);
57 
58 HIDDEN void rt_ct_measure(struct rt_i *rtip, union cutter *cutp, int depth);
59 HIDDEN union cutter *rt_ct_get(struct rt_i *rtip);
60 HIDDEN void rt_plot_cut(FILE *fp, struct rt_i *rtip, union cutter *cutp, int lvl);
61 
62 extern void rt_pr_cut_info(const struct rt_i *rtip, const char *str);
63 HIDDEN int rt_ct_old_assess(register union cutter *, register int, double *, double *);
64 
65 #define AXIS(depth) ((depth)%3) /* cuts: X, Y, Z, repeat */
66 
67 
68 /**
69  * As a temporary aid until NUgrid is working, use NUgrid histogram to
70  * perform a preliminary partitioning of space, along a single axis.
71  * The tree built here is expected to be further refined. The bu_ptbl
72  * "boxes" contains a list of the boxnodes, for convenience.
73  *
74  * Each span runs from [min].nu_spos to [max].nu_epos.
75  */
76 union cutter *
77 rt_cut_one_axis(struct bu_ptbl *boxes, struct rt_i *rtip, int axis, int min, int max, struct nugridnode *nuginfop)
78 {
79  register struct soltab *stp;
80  union cutter *box;
81  int cur;
82  int slice;
83 
84  BU_CK_PTBL(boxes);
85  RT_CK_RTI(rtip);
86 
87  if (min == max) {
88  /* Down to one cell, generate a boxnode */
89  slice = min;
90  BU_ALLOC(box, union cutter);
91 
92  box->bn.bn_type = CUT_BOXNODE;
93  box->bn.bn_len = 0;
94  box->bn.bn_maxlen = rtip->nsolids;
95  box->bn.bn_list = (struct soltab **)bu_calloc(box->bn.bn_maxlen, sizeof(struct soltab *), "xbox boxnode []");
96  VMOVE(box->bn.bn_min, rtip->mdl_min);
97  VMOVE(box->bn.bn_max, rtip->mdl_max);
98  box->bn.bn_min[axis] = nuginfop->nu_axis[axis][slice].nu_spos;
99  box->bn.bn_max[axis] = nuginfop->nu_axis[axis][slice].nu_epos;
100  box->bn.bn_len = 0;
101 
102  /* Search all solids for those in this slice */
103  RT_VISIT_ALL_SOLTABS_START(stp, rtip) {
104  RT_CHECK_SOLTAB(stp);
105  if (!rt_ck_overlap(box->bn.bn_min, box->bn.bn_max,
106  stp, rtip))
107  continue;
108  box->bn.bn_list[box->bn.bn_len++] = stp;
110 
111  bu_ptbl_ins(boxes, (long *)box);
112  return box;
113  }
114 
115  cur = (min + max + 1) / 2;
116  /* Recurse on both sides, then build a cutnode */
117  BU_ALLOC(box, union cutter);
118 
119  box->cn.cn_type = CUT_CUTNODE;
120  box->cn.cn_axis = axis;
121  box->cn.cn_point = nuginfop->nu_axis[axis][cur].nu_spos;
122  box->cn.cn_l = rt_cut_one_axis(boxes, rtip, axis, min, cur-1, nuginfop);
123  box->cn.cn_r = rt_cut_one_axis(boxes, rtip, axis, cur, max, nuginfop);
124  return box;
125 }
126 
127 
128 /**
129  * Process all the nodes in the global array rtip->rti_cuts_waiting,
130  * until none remain. This routine is run in parallel.
131  */
132 void
133 rt_cut_optimize_parallel(int cpu, void *arg)
134 {
135  struct rt_i *rtip = (struct rt_i *)arg;
136  union cutter *cp;
137  int i;
138 
139  if (!arg && RT_G_DEBUG&DEBUG_CUT)
140  bu_log("rt_cut_optimized_parallel(%d): NULL rtip\n", cpu);
141 
142  RT_CK_RTI(rtip);
143  for (;;) {
144 
146  i = rtip->rti_cuts_waiting.end--; /* get first free index */
148  i -= 1; /* change to last used index */
149 
150  if (i < 0) break;
151 
152  cp = (union cutter *)BU_PTBL_GET(&rtip->rti_cuts_waiting, i);
153 
154  rt_ct_optim(rtip, cp, Z);
155  }
156 }
157 
158 
159 #define CMP(_p1, _p2, _memb, _ind) \
160  (*(const struct soltab **)(_p1))->_memb[_ind] < \
161  (*(const struct soltab **)(_p2))->_memb[_ind] ? -1 : \
162  (*(const struct soltab **)(_p1))->_memb[_ind] > \
163  (*(const struct soltab **)(_p2))->_memb[_ind] ? 1 : 0
164 
165 /* Functions for use with bu_sort */
166 HIDDEN int rt_projXmin_comp(const void * p1, const void * p2, void *UNUSED(arg));
167 HIDDEN int rt_projXmax_comp(const void * p1, const void * p2, void *UNUSED(arg));
168 HIDDEN int rt_projYmin_comp(const void * p1, const void * p2, void *UNUSED(arg));
169 HIDDEN int rt_projYmax_comp(const void * p1, const void * p2, void *UNUSED(arg));
170 HIDDEN int rt_projZmin_comp(const void * p1, const void * p2, void *UNUSED(arg));
171 HIDDEN int rt_projZmax_comp(const void * p1, const void * p2, void *UNUSED(arg));
172 
173 HIDDEN int
174 rt_projXmin_comp(const void *p1, const void *p2, void *UNUSED(arg))
175 {
176  return CMP(p1, p2, st_min, X);
177 }
178 
179 
180 HIDDEN int
181 rt_projXmax_comp(const void *p1, const void *p2, void *UNUSED(arg))
182 {
183  return CMP(p1, p2, st_max, X);
184 }
185 
186 
187 HIDDEN int
188 rt_projYmin_comp(const void *p1, const void *p2, void *UNUSED(arg))
189 {
190  return CMP(p1, p2, st_min, Y);
191 }
192 
193 
194 HIDDEN int
195 rt_projYmax_comp(const void *p1, const void *p2, void *UNUSED(arg))
196 {
197  return CMP(p1, p2, st_max, Y);
198 }
199 
200 
201 HIDDEN int
202 rt_projZmin_comp(const void *p1, const void *p2, void *UNUSED(arg))
203 {
204  return CMP(p1, p2, st_min, Z);
205 }
206 
207 
208 HIDDEN int
209 rt_projZmax_comp(const void *p1, const void *p2, void *UNUSED(arg))
210 {
211  return CMP(p1, p2, st_max, Z);
212 }
213 
214 
215 HIDDEN struct cmp_pair {
216  int (*cmp_min)(const void *, const void *, void *);
217  int (*cmp_max)(const void *, const void *, void *);
218 } pairs[] = {
222 };
223 
224 
225 /**
226  * Makes a NUGrid node (CUT_NUGRIDNODE), filling the cells with solids
227  * from the given list.
228  */
229 void
230 rt_nugrid_cut(register struct nugridnode *nugnp, register struct boxnode *fromp, struct rt_i *rtip, int just_collect_info, int depth)
231 {
232 #define USE_HIST 0
233 #if USE_HIST
234  struct bu_hist start_hist[3]; /* where solid RPPs start */
235  struct bu_hist end_hist[3]; /* where solid RPPs end */
236 #endif
237  register struct soltab **stpp;
238 
239  int nu_ncells; /* # cells along one axis */
240  int nu_sol_per_cell; /* avg # solids per cell */
241  int nu_max_ncells; /* hard limit on nu_ncells */
242  size_t pseudo_depth; /* "fake" depth to tell rt_ct_optim */
243  register size_t i;
244  int xp, yp, zp;
245  vect_t xmin, xmax, ymin, ymax, zmin, zmax;
246  struct boxnode nu_xbox, nu_ybox, nu_zbox;
247 
248  if (nugnp->nu_type != CUT_NUGRIDNODE)
249  bu_bomb("rt_nugrid_cut: passed non-nugridnode");
250 
251  /*
252  * Build histograms of solid RPP extent distribution when
253  * projected onto X, Y, and Z axes. First stage in implementing
254  * the Gigante NUgrid algorithm. (Proc. Ausgraph 1990, pg 157)
255  *
256  * XXX For databases where the model diameter (diagonal through
257  * XXX the model RPP) is small or huge, a histogram with
258  * XXX floating-point ranges will be needed.
259  * XXX Integers should suffice for now.
260  *
261  * Goal is to keep the average number of solids per cell constant.
262  * Assuming a uniform distribution, the number of cells along each
263  * axis will need to be (nsol / desired_avg)**(1/3). This is
264  * increased by two to err on the generous side, resulting in a
265  * 3*3*3 grid even for small numbers of solids.
266  *
267  * Presumably the caller will have set rtip->rti_nu_gfactor to
268  * RT_NU_GFACTOR_DEFAULT (although it may change it depending on
269  * the user's wishes or what it feels will be optimal for this
270  * model.) The default value was computed in the following
271  * fashion: Suppose the ratio of the running times of ft_shot and
272  * rt_advance_to_next_cell is K, i.e.,
273  *
274  * avg_running_time(ft_shot)
275  * K := ---------------------------------
276  * avg_running_time(rt_advance)
277  *
278  * Now suppose we divide each axis into G*n^R segments, yielding
279  * G^3 n^(3R) cells. We expect each cell to contain G^(-3)
280  * n^(1-3R) solids, and hence the running time of firing a single
281  * ray through the model will be proportional to
282  *
283  * G*n^R * [ 1 + K G^(-3) n^(1-3R) ] = G*n^R + KG^(-2) n^(1-2R).
284  *
285  * Since we wish for the running time of this algorithm to be low,
286  * we wish to minimize the degree of this polynomial. The optimal
287  * choice for R is 1/3. So the above equation becomes
288  *
289  * G*n^(1/3) + KG^(-2) n^(1/3) = [ G + KG^(-2) ] n^(1/3).
290  *
291  * We now wish to find an optimal value of G in terms of K. Using
292  * basic calculus we see that
293  *
294  * G := (2K)^(1/3).
295  *
296  * It has been experimentally observed that K ~ 5/3 when the model
297  * is mostly arb8s. Hence RT_NU_GFACTOR_DEFAULT := 1.5.
298  *
299  * XXX More tests should be done for this.
300  */
301 
302  if (rtip->rti_nu_gfactor < 0.01 ||
305  bu_log(
306  "rt_nugrid_cut: warning: rtip->rti_nu_gfactor not set, setting to %g\n",
308  }
309 
310  nu_ncells = lrint(ceil(2.0 + rtip->rti_nu_gfactor *
311  pow((double)fromp->bn_len, 1.0/3.0)));
312  if (rtip->rti_nugrid_dimlimit > 0 &&
313  nu_ncells > rtip->rti_nugrid_dimlimit)
314  nu_ncells = rtip->rti_nugrid_dimlimit;
315  nu_sol_per_cell = (fromp->bn_len + nu_ncells - 1) / nu_ncells;
316  nu_max_ncells = 2*nu_ncells + 8;
317 
318  /* pseudo_depth = depth+(int)log((double)(nu_ncells*nu_ncells*nu_ncells)); */
319  pseudo_depth = depth;
320 
321  if (RT_G_DEBUG&DEBUG_CUT)
322  bu_log(
323  "\nnu_ncells=%d, nu_sol_per_cell=%d, nu_max_ncells=%d\n",
324  nu_ncells, nu_sol_per_cell, nu_max_ncells);
325 
326 #if USE_HIST
327  for (i=0; i<3; i++) {
328  bu_hist_init(&start_hist[i],
329  fromp->bn_min[i],
330  fromp->bn_max[i],
331  nu_ncells*100);
332  bu_hist_init(&end_hist[i],
333  fromp->bn_min[i],
334  fromp->bn_max[i],
335  nu_ncells*100);
336  }
337 
338 
339  for (i = 0, stpp = fromp->bn_list;
340  i < fromp->bn_len;
341  i++, stpp++) {
342  register struct soltab *stp = *stpp;
343  RT_CK_SOLTAB(stp);
344  if (stp->st_aradius <= 0) continue;
345  if (stp->st_aradius >= INFINITY) continue;
346  for (j=0; j<3; j++) {
347  BU_HIST_TALLY(&start_hist[j], stp->st_min[j]);
348  BU_HIST_TALLY(&end_hist[j], stp->st_max[j]);
349  }
350  }
351 #endif
352 
353  /* Allocate memory for nugrid axis partition. */
354 
355  for (i=0; i<3; i++)
356  nugnp->nu_axis[i] = (struct nu_axis *)bu_calloc(nu_max_ncells, sizeof(struct nu_axis), "NUgrid axis");
357 
358 #if USE_HIST
359  /*
360  * Next part of NUgrid algorithm: Decide where cell boundaries
361  * should be, along each axis. Each cell will be an interval
362  * across the histogram. For each interval, track the number of
363  * new solids that have *started* in the interval, and the number
364  * of existing solids that have *ended* in the interval. Continue
365  * widening the interval another histogram element in width, until
366  * either the number of starts or endings exceeds the goal for the
367  * average number of solids per cell, nu_sol_per_cell = (nsolids /
368  * nu_ncells).
369  */
370 
371  for (i=0; i<3; i++) {
372  fastf_t pos; /* Current interval start pos */
373  int nstart = 0;
374  int nend = 0;
375  struct bu_hist *shp = &start_hist[i];
376  struct bu_hist *ehp = &end_hist[i];
377  int hindex = 0;
378  int axi = 0;
379 
380  if (shp->hg_min != ehp->hg_min)
381  bu_bomb("cut_it: hg_min error\n");
382  pos = shp->hg_min;
383  nugnp->nu_axis[i][axi].nu_spos = pos;
384  for (hindex = 0; hindex < shp->hg_nbins; hindex++) {
385  if (pos > shp->hg_max) break;
386  /* Advance interval one more histogram entry */
387  /* NOTE: Peeks into histogram structures! */
388  nstart += shp->hg_bins[hindex];
389  nend += ehp->hg_bins[hindex];
390  pos += shp->hg_clumpsize;
391 
392  if (nstart < nu_sol_per_cell && nend < nu_sol_per_cell)
393  continue;
394 
395  /* End current interval, start new one */
396  nugnp->nu_axis[i][axi].nu_epos = pos;
397  nugnp->nu_axis[i][axi].nu_width =
398  pos - nugnp->nu_axis[i][axi].nu_spos;
399  if (axi >= nu_max_ncells-1) {
400  bu_log("NUgrid ran off end, axis=%d, axi=%d\n",
401  i, axi);
402  pos = shp->hg_max+1;
403  break;
404  }
405  nugnp->nu_axis[i][++axi].nu_spos = pos;
406  nstart = 0;
407  nend = 0;
408  }
409  /* End final interval */
410  nugnp->nu_axis[i][axi].nu_epos = pos;
411  nugnp->nu_axis[i][axi].nu_width =
412  pos - nugnp->nu_axis[i][axi].nu_spos;
413  nugnp->nu_cells_per_axis[i] = axi+1;
414  }
415 
416  /* Finished with temporary data structures */
417  for (i=0; i<3; i++) {
418  bu_hist_free(&start_hist[i]);
419  bu_hist_free(&end_hist[i]);
420  }
421 #else
422  {
423  struct soltab **list_min, **list_max;
424  register struct soltab **l1, **l2;
425  register int nstart, nend, axi, len = fromp->bn_len;
426  register fastf_t pos;
427 
428  list_min = (struct soltab **)bu_calloc(len,
429  sizeof(struct soltab *),
430  "min solid list");
431  list_max = (struct soltab **)bu_calloc(len,
432  sizeof(struct soltab *),
433  "max solid list");
434  memcpy(list_min, fromp->bn_list, len*sizeof(struct soltab *));
435  memcpy(list_max, fromp->bn_list, len*sizeof(struct soltab *));
436  for (i=0; i<3; i++) {
437  bu_sort((void *)list_min, len,
438  sizeof(struct soltab *), pairs[i].cmp_min, NULL);
439  bu_sort((void *)list_max, len,
440  sizeof(struct soltab *), pairs[i].cmp_max, NULL);
441  nstart = nend = axi = 0;
442  l1 = list_min;
443  l2 = list_max;
444 
445  pos = fromp->bn_min[i];
446  nugnp->nu_axis[i][axi].nu_spos = pos;
447 
448  while (l1-list_min < len ||
449  l2-list_max < len) {
450  if (l2-list_max >= len ||
451  (l1-list_min < len &&
452  (*l1)->st_min[i] < (*l2)->st_max[i])) {
453  pos = (*l1++)->st_min[i];
454  ++nstart;
455  } else {
456  pos = (*l2++)->st_max[i];
457  ++nend;
458  }
459 
460  if (nstart < nu_sol_per_cell && nend < nu_sol_per_cell)
461  continue;
462 
463  /* Don't make really teeny intervals. */
464  if (pos <= nugnp->nu_axis[i][axi].nu_spos
465  + 1.0
466  + rtip->rti_tol.dist)
467  continue;
468 
469  /* don't make any more cuts if we've gone
470  past the end. */
471  if (pos >= fromp->bn_max[i]
472  - 1.0
473  - rtip->rti_tol.dist)
474  continue;
475 
476  /* End current interval, start new one */
477  nugnp->nu_axis[i][axi].nu_epos = pos;
478  nugnp->nu_axis[i][axi].nu_width =
479  pos - nugnp->nu_axis[i][axi].nu_spos;
480  if (axi >= nu_max_ncells-1) {
481  bu_log(
482  "NUgrid ran off end, axis=%zu, axi=%d\n",
483  i, axi);
484  bu_bomb("rt_nugrid_cut: NUgrid ran off end");
485  }
486  nugnp->nu_axis[i][++axi].nu_spos = pos;
487  nstart = 0;
488  nend = 0;
489  }
490  /* End final interval */
491  if (pos < fromp->bn_max[i]) pos = fromp->bn_max[i];
492  nugnp->nu_axis[i][axi].nu_epos = pos;
493  nugnp->nu_axis[i][axi].nu_width =
494  pos - nugnp->nu_axis[i][axi].nu_spos;
495  nugnp->nu_cells_per_axis[i] = axi+1;
496  }
497  bu_free((void *)list_min, "solid list min sort");
498  bu_free((void *)list_max, "solid list max sort");
499  }
500 
501 #endif
502 
503  nugnp->nu_stepsize[X] = 1;
504  nugnp->nu_stepsize[Y] = nugnp->nu_cells_per_axis[X] *
505  nugnp->nu_stepsize[X];
506  nugnp->nu_stepsize[Z] = nugnp->nu_cells_per_axis[Y] *
507  nugnp->nu_stepsize[Y];
508 
509  /* For debugging */
510  if (RT_G_DEBUG&DEBUG_CUT) for (i=0; i<3; i++) {
511  register int j;
512  bu_log("NUgrid %c axis: %d cells\n", "XYZ*"[i],
513  nugnp->nu_cells_per_axis[i]);
514  for (j=0; j<nugnp->nu_cells_per_axis[i]; j++) {
515  bu_log(" %g .. %g, w=%g\n",
516  nugnp->nu_axis[i][j].nu_spos,
517  nugnp->nu_axis[i][j].nu_epos,
518  nugnp->nu_axis[i][j].nu_width);
519  }
520  }
521 
522  /* If we were just asked to collect info, we are done. The binary
523  * space partitioning algorithm (sometimes) needs just this.
524  */
525 
526  if (just_collect_info) return;
527 
528  /* For the moment, re-use "union cutter" */
529  nugnp->nu_grid = (union cutter *)bu_calloc(nugnp->nu_cells_per_axis[X] *
530  nugnp->nu_cells_per_axis[Y] *
531  nugnp->nu_cells_per_axis[Z], sizeof(union cutter),
532  "3-D NUgrid union cutter []");
533  nu_xbox.bn_len = 0;
534  nu_xbox.bn_maxlen = fromp->bn_len;
535  nu_xbox.bn_list = (struct soltab **)bu_calloc(nu_xbox.bn_maxlen, sizeof(struct soltab *), "xbox boxnode []");
536  nu_ybox.bn_len = 0;
537  nu_ybox.bn_maxlen = fromp->bn_len;
538  nu_ybox.bn_list = (struct soltab **)bu_calloc(nu_ybox.bn_maxlen, sizeof(struct soltab *), "ybox boxnode []");
539  nu_zbox.bn_len = 0;
540  nu_zbox.bn_maxlen = fromp->bn_len;
541  nu_zbox.bn_list = (struct soltab **)bu_calloc(nu_zbox.bn_maxlen, sizeof(struct soltab *), "zbox boxnode []");
542  /* Build each of the X slices */
543  for (xp = 0; xp < nugnp->nu_cells_per_axis[X]; xp++) {
544  VMOVE(xmin, fromp->bn_min);
545  VMOVE(xmax, fromp->bn_max);
546  xmin[X] = nugnp->nu_axis[X][xp].nu_spos;
547  xmax[X] = nugnp->nu_axis[X][xp].nu_epos;
548  VMOVE(nu_xbox.bn_min, xmin);
549  VMOVE(nu_xbox.bn_max, xmax);
550  nu_xbox.bn_len = 0;
551 
552  /* Search all solids for those in this X slice */
553  for (i = 0, stpp = fromp->bn_list;
554  i < fromp->bn_len;
555  i++, stpp++) {
556  if (!rt_ck_overlap(xmin, xmax, *stpp, rtip))
557  continue;
558  nu_xbox.bn_list[nu_xbox.bn_len++] = *stpp;
559  }
560 
561  /* Build each of the Y slices in this X slice */
562  for (yp = 0; yp < nugnp->nu_cells_per_axis[Y]; yp++) {
563  VMOVE(ymin, xmin);
564  VMOVE(ymax, xmax);
565  ymin[Y] = nugnp->nu_axis[Y][yp].nu_spos;
566  ymax[Y] = nugnp->nu_axis[Y][yp].nu_epos;
567  VMOVE(nu_ybox.bn_min, ymin);
568  VMOVE(nu_ybox.bn_max, ymax);
569  nu_ybox.bn_len = 0;
570  /* Search X slice for membs of this Y slice */
571  for (i=0; i<nu_xbox.bn_len; i++) {
572  if (!rt_ck_overlap(ymin, ymax,
573  nu_xbox.bn_list[i],
574  rtip))
575  continue;
576  nu_ybox.bn_list[nu_ybox.bn_len++] =
577  nu_xbox.bn_list[i];
578  }
579  /* Build each of the Z slices in this Y slice*/
580  /* Each of these will be a final cell */
581  for (zp = 0; zp < nugnp->nu_cells_per_axis[Z]; zp++) {
582  register union cutter *cutp =
583  &nugnp->nu_grid[
584  zp*nugnp->nu_stepsize[Z] +
585  yp*nugnp->nu_stepsize[Y] +
586  xp*nugnp->nu_stepsize[X]];
587 
588  VMOVE(zmin, ymin);
589  VMOVE(zmax, ymax);
590  zmin[Z] = nugnp->nu_axis[Z][zp].nu_spos;
591  zmax[Z] = nugnp->nu_axis[Z][zp].nu_epos;
592  cutp->cut_type = CUT_BOXNODE;
593  VMOVE(cutp->bn.bn_min, zmin);
594  VMOVE(cutp->bn.bn_max, zmax);
595  /* Build up a temporary list in nu_zbox first,
596  * then copy list over to cutp->bn */
597  nu_zbox.bn_len = 0;
598  /* Search Y slice for members of this Z slice*/
599  for (i=0; i<nu_ybox.bn_len; i++) {
600  if (!rt_ck_overlap(zmin, zmax,
601  nu_ybox.bn_list[i],
602  rtip))
603  continue;
604  nu_zbox.bn_list[nu_zbox.bn_len++] =
605  nu_ybox.bn_list[i];
606  }
607 
608  if (nu_zbox.bn_len <= 0) {
609  /* Empty cell */
610  cutp->bn.bn_list = (struct soltab **)0;
611  cutp->bn.bn_len = 0;
612  cutp->bn.bn_maxlen = 0;
613  continue;
614  }
615  /* Allocate just enough space for list,
616  * and copy it in */
617 
618  cutp->bn.bn_list =
619  (struct soltab **)bu_calloc(
620  nu_zbox.bn_len,
621  sizeof(struct soltab *),
622  "NUgrid cell bn_list[]");
623  cutp->bn.bn_len = cutp->bn.bn_maxlen =
624  nu_zbox.bn_len;
625 
626  memcpy((char *)cutp->bn.bn_list,
627  (char *)nu_zbox.bn_list,
628  nu_zbox.bn_len *
629  sizeof(struct soltab *));
630 
631  if (rtip->rti_nugrid_dimlimit > 0) {
632  rt_ct_optim(rtip, cutp, pseudo_depth);
633  }
634  }
635  }
636  }
637 
638  bu_free((void *)nu_zbox.bn_list, "nu_zbox bn_list[]");
639  bu_free((void *)nu_ybox.bn_list, "nu_ybox bn_list[]");
640  bu_free((void *)nu_xbox.bn_list, "nu_xbox bn_list[]");
641 }
642 
643 
644 int
645 rt_split_mostly_empty_cells(struct rt_i *rtip, union cutter *cutp)
646 {
647  point_t max, min;
648  struct soltab *stp;
649  struct rt_piecelist pl;
650  fastf_t range[3], empty[3], tmp;
651  int upper_or_lower[3];
652  fastf_t max_empty;
653  int max_empty_dir;
654  size_t i;
655  int num_splits=0;
656 
657  switch (cutp->cut_type) {
658  case CUT_CUTNODE:
659  num_splits += rt_split_mostly_empty_cells(rtip, cutp->cn.cn_l);
660  num_splits += rt_split_mostly_empty_cells(rtip, cutp->cn.cn_r);
661  break;
662  case CUT_BOXNODE:
663  /* find the actual bounds of stuff in this cell */
664  if (cutp->bn.bn_len == 0 && cutp->bn.bn_piecelen == 0) {
665  break;
666  }
667  VSETALL(min, MAX_FASTF);
668  VREVERSE(max, min);
669 
670  for (i=0; i<cutp->bn.bn_len; i++) {
671  stp = cutp->bn.bn_list[i];
672  VMIN(min, stp->st_min);
673  VMAX(max, stp->st_max);
674  }
675 
676  for (i=0; i<cutp->bn.bn_piecelen; i++) {
677  size_t j;
678 
679  pl = cutp->bn.bn_piecelist[i];
680  for (j=0; j<pl.npieces; j++) {
681  int piecenum;
682 
683  piecenum = pl.pieces[j];
684  VMIN(min, pl.stp->st_piece_rpps[piecenum].min);
685  VMAX(max, pl.stp->st_piece_rpps[piecenum].max);
686  }
687  }
688 
689  /* clip min and max to the bounds of this cell */
690  for (i=X; i<=Z; i++) {
691  if (min[i] < cutp->bn.bn_min[i]) {
692  min[i] = cutp->bn.bn_min[i];
693  }
694  if (max[i] > cutp->bn.bn_max[i]) {
695  max[i] = cutp->bn.bn_max[i];
696  }
697  }
698 
699  /* min and max now have the real bounds of data in this cell */
700  VSUB2(range, cutp->bn.bn_max, cutp->bn.bn_min);
701  for (i=X; i<=Z; i++) {
702  empty[i] = cutp->bn.bn_max[i] - max[i];
703  upper_or_lower[i] = 1; /* upper section is empty */
704  tmp = min[i] - cutp->bn.bn_min[i];
705  if (tmp > empty[i]) {
706  empty[i] = tmp;
707  upper_or_lower[i] = 0; /* lower section is empty */
708  }
709  }
710  max_empty = empty[X];
711  max_empty_dir = X;
712  if (empty[Y] > max_empty) {
713  max_empty = empty[Y];
714  max_empty_dir = Y;
715  }
716  if (empty[Z] > max_empty) {
717  max_empty = empty[Z];
718  max_empty_dir = Z;
719  }
720  if (max_empty / range[max_empty_dir] > 0.5) {
721  /* this cell is over 50% empty in this direction, split it */
722 
723  fastf_t where;
724 
725  /* select cutting plane, but move it slightly off any geometry */
726  if (upper_or_lower[max_empty_dir]) {
727  where = max[max_empty_dir] + rtip->rti_tol.dist;
728  if (where >= cutp->bn.bn_max[max_empty_dir]) {
729  return num_splits;
730  }
731  } else {
732  where = min[max_empty_dir] - rtip->rti_tol.dist;
733  if (where <= cutp->bn.bn_min[max_empty_dir]) {
734  return num_splits;
735  }
736  }
737  if (where - cutp->bn.bn_min[max_empty_dir] < 2.0 ||
738  cutp->bn.bn_max[max_empty_dir] - where < 2.0) {
739  /* will make a box too small */
740  return num_splits;
741  }
742  if (rt_ct_box(rtip, cutp, max_empty_dir, where, 1)) {
743  num_splits++;
744  num_splits += rt_split_mostly_empty_cells(rtip, cutp->cn.cn_l);
745  num_splits += rt_split_mostly_empty_cells(rtip, cutp->cn.cn_r);
746  }
747  }
748  break;
749  }
750 
751  return num_splits;
752 }
753 
754 
755 void
756 rt_cut_it(register struct rt_i *rtip, int ncpu)
757 {
758  register struct soltab *stp;
759  union cutter *finp; /* holds the finite solids */
760  FILE *plotfp;
761  int num_splits=0;
762 
763  if (ncpu < 1) ncpu = 1; /* sanity */
764 
765  /* Make a list of all solids into one special boxnode, then refine. */
766  BU_ALLOC(finp, union cutter);
767  finp->cut_type = CUT_BOXNODE;
768  VMOVE(finp->bn.bn_min, rtip->mdl_min);
769  VMOVE(finp->bn.bn_max, rtip->mdl_max);
770  finp->bn.bn_len = 0;
771  finp->bn.bn_maxlen = rtip->nsolids+1;
772  finp->bn.bn_list = (struct soltab **)bu_calloc(
773  finp->bn.bn_maxlen, sizeof(struct soltab *),
774  "rt_cut_it: initial list alloc");
775 
777 
778  RT_VISIT_ALL_SOLTABS_START(stp, rtip) {
779  /* Ignore "dead" solids in the list. (They failed prep) */
780  if (stp->st_aradius <= 0) continue;
781 
782  /* Infinite and finite solids all get lumped together */
783  rt_cut_extend(finp, stp, rtip);
784 
785  if (stp->st_aradius >= INFINITY) {
786  /* Also add infinite solids to a special BOXNODE */
787  rt_cut_extend(&rtip->rti_inf_box, stp, rtip);
788  }
790 
791  /* Dynamic decisions on tree limits. Note that there will be
792  * (2**rtip->rti_cutdepth)*rtip->rti_cutlen potential leaf slots.
793  * Also note that solids will typically span several leaves.
794  */
795  rtip->rti_cutlen = lrint(floor(log((double)(rtip->nsolids+1)))); /* ln ~= log2, nsolids+1 to avoid log(0) */
796  rtip->rti_cutdepth = 2 * rtip->rti_cutlen;
797  if (rtip->rti_cutlen < 3) rtip->rti_cutlen = 3;
798  if (rtip->rti_cutdepth < 12) rtip->rti_cutdepth = 12;
799  if (rtip->rti_cutdepth > 24) rtip->rti_cutdepth = 24; /* !! */
800  if (RT_G_DEBUG&DEBUG_CUT)
801  bu_log("Before Space Partitioning: Max Tree Depth=%zu, Cutoff primitive count=%zu\n",
802  rtip->rti_cutdepth, rtip->rti_cutlen);
803 
804  bu_ptbl_init(&rtip->rti_cuts_waiting, rtip->nsolids,
805  "rti_cuts_waiting ptbl");
806 
807  if (rtip->rti_hasty_prep) {
809  rtip->rti_cutdepth = 6;
810  }
811 
812  switch (rtip->rti_space_partition) {
813  case RT_PART_NUGRID:
815  rt_nugrid_cut(&rtip->rti_CutHead.nugn, &finp->bn, rtip, 0, 0);
816  rt_fr_cut(rtip, finp); /* done with finite solids box */
817  break;
818  case RT_PART_NUBSPT: {
819 #ifdef NEW_WAY
820  struct nugridnode nuginfo;
821 
822  /* Collect statistics to assist binary space partition
823  * tree construction
824  */
825  nuginfo.nu_type = CUT_NUGRIDNODE;
826  rt_nugrid_cut(&nuginfo, &fin_box, rtip, 1, 0);
827 #endif
828  rtip->rti_CutHead = *finp; /* union copy */
829 #ifdef NEW_WAY
830  if (rtip->nsolids < 50000) {
831 #endif
832  /* Old way, non-parallel */
833  /* For some reason, this algorithm produces a
834  * substantial performance improvement over the
835  * parallel way, below. The benchmark tests seem to
836  * be very sensitive to how the space partitioning is
837  * laid out. Until we go to full NUgrid, this will
838  * have to do. */
839  rt_ct_optim(rtip, &rtip->rti_CutHead, 0);
840 #ifdef NEW_WAY
841  } else {
842 
843  /* XXX This hasn't been tested since massive
844  * NUgrid changes were made
845  */
846 
847  /* New way, mostly parallel */
848  union cutter *head;
849  int i;
850 
851  head = rt_cut_one_axis(&rtip->rti_cuts_waiting, rtip,
852  Y, 0, nuginfo.nu_cells_per_axis[Y]-1, &nuginfo);
853  rtip->rti_CutHead = *head; /* struct copy */
854  bu_free((char *)head, "union cutter");
855 
857  for (i=0; i<3; i++) {
858  bu_log("\nNUgrid %c axis: %d cells\n",
859  "XYZ*"[i], nuginfo.nu_cells_per_axis[i]);
860  }
861  rt_pr_cut(&rtip->rti_CutHead, 0);
862  }
863 
864  if (ncpu <= 1) {
865  rt_cut_optimize_parallel(0, rtip);
866  } else {
868  }
869  }
870 #endif
871  /* one more pass to find cells that are mostly empty */
872  num_splits = rt_split_mostly_empty_cells(rtip, &rtip->rti_CutHead);
873 
874  if (RT_G_DEBUG&DEBUG_CUT) {
875  bu_log("rt_split_mostly_empty_cells(): split %d cells\n", num_splits);
876  }
877 
878  break; }
879  default:
880  bu_bomb("rt_cut_it: unknown space partitioning method\n");
881  }
882 
883  bu_free(finp, "union cutter");
884 
885  /* Measure the depth of tree, find max # of RPPs in a cut node */
886 
887  bu_hist_init(&rtip->rti_hist_cellsize, 0.0, 400.0, 400);
888  bu_hist_init(&rtip->rti_hist_cell_pieces, 0.0, 400.0, 400);
889  bu_hist_init(&rtip->rti_hist_cutdepth, 0.0,
890  (fastf_t)rtip->rti_cutdepth+1, rtip->rti_cutdepth+1);
891  memset(rtip->rti_ncut_by_type, 0, sizeof(rtip->rti_ncut_by_type));
892  rt_ct_measure(rtip, &rtip->rti_CutHead, 0);
893  if (RT_G_DEBUG&DEBUG_CUT) {
894  rt_pr_cut_info(rtip, "Cut");
895  }
896 
898  /* Produce a voluminous listing of the cut tree */
899  rt_pr_cut(&rtip->rti_CutHead, 0);
900  }
901 
902  if (RT_G_DEBUG&DEBUG_PL_BOX) {
903  /* Debugging code to plot cuts */
904  if ((plotfp=fopen("rtcut.plot3", "wb"))!=NULL) {
905  pdv_3space(plotfp, rtip->rti_pmin, rtip->rti_pmax);
906  /* Plot all the cutting boxes */
907  rt_plot_cut(plotfp, rtip, &rtip->rti_CutHead, 0);
908  (void)fclose(plotfp);
909  }
910  }
911 }
912 
913 
914 void
915 rt_cut_extend(register union cutter *cutp, struct soltab *stp, const struct rt_i *rtip)
916 {
917  RT_CK_SOLTAB(stp);
918  RT_CK_RTI(rtip);
919 
920  BU_ASSERT(cutp->cut_type == CUT_BOXNODE);
921 
923  bu_log("rt_cut_extend(cutp=%p) %s npieces=%ld\n",
924  (void *)cutp, stp->st_name, stp->st_npieces);
925  }
926 
927  if (stp->st_npieces > 0) {
928  struct rt_piecelist *plp;
929  register int i;
930 
931  if (cutp->bn.bn_piecelist == NULL) {
932  /* Allocate enough piecelist's to hold all solids */
933  BU_ASSERT(rtip->nsolids > 0);
934  cutp->bn.bn_piecelist = (struct rt_piecelist *) bu_calloc(
935  sizeof(struct rt_piecelist), (rtip->nsolids + 2),
936  "rt_ct_box bn_piecelist (root node)");
937  cutp->bn.bn_piecelen = 0; /* sanity */
938  cutp->bn.bn_maxpiecelen = rtip->nsolids + 2;
939  }
940  plp = &cutp->bn.bn_piecelist[cutp->bn.bn_piecelen++];
941  plp->magic = RT_PIECELIST_MAGIC;
942  plp->stp = stp;
943 
944  /* List every index that this solid has */
945  plp->npieces = stp->st_npieces;
946  plp->pieces = (long *)bu_calloc(plp->npieces, sizeof(long), "pieces[]");
947  for (i = stp->st_npieces-1; i >= 0; i--)
948  plp->pieces[i] = i;
949 
950  return;
951  }
952 
953  /* No pieces, list the entire solid on bn_list */
954  if (cutp->bn.bn_len >= cutp->bn.bn_maxlen) {
955  /* Need to get more space in list. */
956  if (cutp->bn.bn_maxlen <= 0) {
957  /* Initial allocation */
958  if (rtip->rti_cutlen > rtip->nsolids)
959  cutp->bn.bn_maxlen = rtip->rti_cutlen;
960  else
961  cutp->bn.bn_maxlen = rtip->nsolids + 2;
962  cutp->bn.bn_list = (struct soltab **)bu_calloc(
963  cutp->bn.bn_maxlen, sizeof(struct soltab *),
964  "rt_cut_extend: initial list alloc");
965  } else {
966  cutp->bn.bn_maxlen *= 8;
967  cutp->bn.bn_list = (struct soltab **) bu_realloc(
968  (void *)cutp->bn.bn_list,
969  sizeof(struct soltab *) * cutp->bn.bn_maxlen,
970  "rt_cut_extend: list extend");
971  }
972  }
973  cutp->bn.bn_list[cutp->bn.bn_len++] = stp;
974 }
975 
976 
977 #ifdef NEW_WAY
978 /**
979  * Attempt to make an "optimal" cut of the given boxnode. Consider
980  * cuts along all three axis planes, and choose the one with the
981  * smallest "offcenter" metric.
982  *
983  * Returns -
984  * -1 No cut is possible
985  * 0 Node has been cut
986  */
987 HIDDEN int
988 rt_ct_plan(struct rt_i *rtip, union cutter *cutp)
989 {
990  int axis;
991  int status[3];
992  double where[3];
993  double offcenter[3];
994  int best;
995  double bestoff;
996 
997  RT_CK_RTI(rtip);
998  for (axis = X; axis <= Z; axis++) {
999 #ifdef NEW_WAY
1000  /* New way */
1001  status[axis] = rt_ct_assess(
1002  cutp, axis, &where[axis], &offcenter[axis]);
1003 #else
1004  /* Old way */
1005  status[axis] = rt_ct_old_assess(
1006  cutp, axis, &where[axis], &offcenter[axis]);
1007 #endif
1008  }
1009 
1010  for (;;) {
1011  best = -1;
1012  bestoff = INFINITY;
1013  for (axis = X; axis <= Z; axis++) {
1014  if (status[axis] <= 0) continue;
1015  if (offcenter[axis] >= bestoff) continue;
1016  /* This one is better than previous ones */
1017  best = axis;
1018  bestoff = offcenter[axis];
1019  }
1020 
1021  if (best < 0) return -1; /* No cut is possible */
1022 
1023  if (rt_ct_box(rtip, cutp, best, where[best], 0) > 0)
1024  return 0; /* OK */
1025 
1026  /*
1027  * This cut failed to reduce complexity on either side. Mark
1028  * this status as bad, and try the next-best opportunity, if
1029  * any.
1030  */
1031  status[best] = 0;
1032  }
1033 }
1034 
1035 
1036 /**
1037  * Assess the possibility of making a cut along the indicated axis.
1038  *
1039  * Returns -
1040  * 0 if a cut along this axis is not possible
1041  * 1 if a cut along this axis *is* possible, plus:
1042  * 'where' is proposed cut point, and
1043  * 'offcenter' is distance from "optimum" cut location.
1044  */
1045 HIDDEN int
1046 rt_ct_assess(register union cutter *cutp, register int axis, double *where_p, double *offcenter_p)
1047 {
1048  register int i;
1049  register double val;
1050  register double where;
1051  register double offcenter; /* Closest distance from midpoint */
1052  register double middle; /* midpoint */
1053  register double left, right;
1054 
1055  if (cutp->bn.bn_len <= 1) return 0; /* Forget it */
1056 
1057  /*
1058  * In absolute terms, each box must be at least 1mm wide after
1059  * cut, so there is no need subdividing anything smaller than
1060  * twice that.
1061  */
1062  if ((right=cutp->bn.bn_max[axis])-(left=cutp->bn.bn_min[axis]) <= 2.0)
1063  return 0;
1064 
1065  /*
1066  * Split distance between min and max in half. Find the closest
1067  * edge of a solid's bounding RPP to the mid-point, and split
1068  * there. This should ordinarily guarantee that at least one side
1069  * of the cut has one less item in it.
1070  *
1071  * XXX This should be much more sophisticated.
1072  * XXX Consider making a list of candidate cut points (max and min
1073  * of each bn_list[] element) with the subscript stored.
1074  *
1075  * Eliminate candidates outside the current range. Sort the
1076  * list. Eliminate duplicate candidates. The the element in the
1077  * middle of the candidate list. Compute offcenter from middle of
1078  * range as now.
1079  */
1080  middle = (left + right) * 0.5;
1081  where = offcenter = INFINITY;
1082  for (i=0; i < cutp->bn.bn_len; i++) {
1083  /* left (min) edge */
1084  val = cutp->bn.bn_list[i]->st_min[axis];
1085  if (val > left && val < right) {
1086  register double d;
1087  if ((d = val - middle) < 0) d = (-d);
1088  if (d < offcenter) {
1089  offcenter = d;
1090  where = val;
1091  }
1092  }
1093  /* right (max) edge */
1094  val = cutp->bn.bn_list[i]->st_max[axis];
1095  if (val > left && val < right) {
1096  register double d;
1097  if ((d = val - middle) < 0) d = (-d);
1098  if (d < offcenter) {
1099  offcenter = d;
1100  where = val;
1101  }
1102  }
1103  }
1104  if (offcenter >= INFINITY)
1105  return 0; /* no candidates? */
1106  if (where <= left || where >= right)
1107  return 0; /* not reasonable */
1108 
1109  if (where - left <= 1.0 || right - where <= 1.0)
1110  return 0; /* cut will be too small */
1111 
1112  *where_p = where;
1113  *offcenter_p = offcenter;
1114  return 1; /* OK */
1115 }
1116 #endif
1117 
1118 #define PIECE_BLOCK 512
1119 
1120 
1121 /**
1122  * Given that 'outp' has been given a bounding box smaller than that
1123  * of 'inp', copy over everything which still fits in the smaller box.
1124  *
1125  * Returns -
1126  * 0 if outp has the same number of items as inp
1127  * 1 if outp has fewer items than inp
1128  */
1129 HIDDEN int
1130 rt_ct_populate_box(union cutter *outp, const union cutter *inp, struct rt_i *rtip)
1131 {
1132  register int i;
1133  int success = 0;
1134  const struct bn_tol *tol = &rtip->rti_tol;
1135 
1136  /* Examine the solids */
1137  outp->bn.bn_len = 0;
1138  outp->bn.bn_maxlen = inp->bn.bn_len;
1139  if (outp->bn.bn_maxlen > 0) {
1140  outp->bn.bn_list = (struct soltab **) bu_calloc(
1141  outp->bn.bn_maxlen, sizeof(struct soltab *),
1142  "bn_list");
1143  for (i = inp->bn.bn_len-1; i >= 0; i--) {
1144  struct soltab *stp = inp->bn.bn_list[i];
1145  if (!rt_ck_overlap(outp->bn.bn_min, outp->bn.bn_max,
1146  stp, rtip))
1147  continue;
1148  outp->bn.bn_list[outp->bn.bn_len++] = stp;
1149  }
1150  if (outp->bn.bn_len < inp->bn.bn_len) success = 1;
1151  } else {
1152  outp->bn.bn_list = (struct soltab **)NULL;
1153  }
1154 
1155  /* Examine the solid pieces */
1156  outp->bn.bn_piecelen = 0;
1157  if (inp->bn.bn_piecelen <= 0) {
1158  outp->bn.bn_piecelist = (struct rt_piecelist *)NULL;
1159  outp->bn.bn_maxpiecelen = 0;
1160  return success;
1161  }
1162 
1163  outp->bn.bn_piecelist = (struct rt_piecelist *) bu_calloc(inp->bn.bn_piecelen, sizeof(struct rt_piecelist), "rt_piecelist");
1164  outp->bn.bn_maxpiecelen = inp->bn.bn_piecelen;
1165 
1166  for (i = inp->bn.bn_piecelen-1; i >= 0; i--) {
1167  struct rt_piecelist *plp = &inp->bn.bn_piecelist[i]; /* input */
1168  struct soltab *stp = plp->stp;
1169  struct rt_piecelist *olp = &outp->bn.bn_piecelist[outp->bn.bn_piecelen]; /* output */
1170  int j, k;
1171  long piece_list[PIECE_BLOCK]; /* array of pieces */
1172  long piece_count=0; /* count of used slots in above array */
1173  long *more_pieces=NULL; /* dynamically allocated array for overflow of above array */
1174  long more_piece_count=0; /* number of slots used in dynamic array */
1175  long more_piece_len=0; /* allocated length of dynamic array */
1176 
1177  RT_CK_PIECELIST(plp);
1178  RT_CK_SOLTAB(stp);
1179 
1180  /* Loop for every piece of this solid */
1181  for (j = plp->npieces-1; j >= 0; j--) {
1182  long indx = plp->pieces[j];
1183  struct bound_rpp *rpp = &stp->st_piece_rpps[indx];
1184  if (!V3RPP_OVERLAP_TOL(outp->bn.bn_min, outp->bn.bn_max, rpp->min, rpp->max, tol->dist))
1185  continue;
1186  if (piece_count < PIECE_BLOCK) {
1187  piece_list[piece_count++] = indx;
1188  } else if (more_piece_count >= more_piece_len) {
1189  /* this should be an extremely rare occurrence */
1190  more_piece_len += PIECE_BLOCK;
1191  more_pieces = (long *)bu_realloc(more_pieces, more_piece_len * sizeof(long),
1192  "more_pieces");
1193  more_pieces[more_piece_count++] = indx;
1194  } else {
1195  more_pieces[more_piece_count++] = indx;
1196  }
1197  }
1198  olp->npieces = piece_count + more_piece_count;
1199  if (olp->npieces > 0) {
1200  /* This solid contributed pieces to the output box */
1201  olp->magic = RT_PIECELIST_MAGIC;
1202  olp->stp = stp;
1203  outp->bn.bn_piecelen++;
1204  olp->pieces = (long *)bu_calloc(olp->npieces, sizeof(long), "olp->pieces[]");
1205  for (j=0; j<piece_count; j++) {
1206  olp->pieces[j] = piece_list[j];
1207  }
1208  k = piece_count;
1209  for (j=0; j<more_piece_count; j++) {
1210  olp->pieces[k++] = more_pieces[j];
1211  }
1212  if (more_pieces) {
1213  bu_free((char *)more_pieces, "more_pieces");
1214  }
1215  if (olp->npieces < plp->npieces) success = 1;
1216  } else {
1217  olp->pieces = NULL;
1218  /* if (plp->npieces > 0) success = 1; */
1219  }
1220  }
1221 
1222  return success;
1223 }
1224 
1225 
1226 /**
1227  * Cut the given box node with a plane along the given axis, at the
1228  * specified distance "where". Convert the caller's box node into a
1229  * cut node, allocating two additional box nodes for the new leaves.
1230  *
1231  * If, according to the classifier, both sides have the same number of
1232  * solids, then nothing is changed, and an error is returned.
1233  *
1234  * The storage strategy used is to make the maximum length of each of
1235  * the two child boxnodes be the current length of the source node.
1236  *
1237  * Returns -
1238  * 0 failure
1239  * 1 success
1240  */
1241 HIDDEN int
1242 rt_ct_box(struct rt_i *rtip, register union cutter *cutp, register int axis, double where, int force)
1243 {
1244  register union cutter *rhs, *lhs;
1245  int success = 0;
1246 
1247  RT_CK_RTI(rtip);
1249  bu_log("rt_ct_box(%p, %c) %g .. %g .. %g\n",
1250  (void *)cutp, "XYZ345"[axis],
1251  cutp->bn.bn_min[axis],
1252  where,
1253  cutp->bn.bn_max[axis]);
1254  }
1255 
1256  /* LEFT side */
1257  lhs = rt_ct_get(rtip);
1258  lhs->bn.bn_type = CUT_BOXNODE;
1259  VMOVE(lhs->bn.bn_min, cutp->bn.bn_min);
1260  VMOVE(lhs->bn.bn_max, cutp->bn.bn_max);
1261  lhs->bn.bn_max[axis] = where;
1262 
1263  success = rt_ct_populate_box(lhs, cutp, rtip);
1264 
1265  /* RIGHT side */
1266  rhs = rt_ct_get(rtip);
1267  rhs->bn.bn_type = CUT_BOXNODE;
1268  VMOVE(rhs->bn.bn_min, cutp->bn.bn_min);
1269  VMOVE(rhs->bn.bn_max, cutp->bn.bn_max);
1270  rhs->bn.bn_min[axis] = where;
1271 
1272  success += rt_ct_populate_box(rhs, cutp, rtip);
1273 
1274  /* Check to see if complexity didn't decrease */
1275  if (success == 0 && !force) {
1276  /*
1277  * This cut operation did no good, release storage,
1278  * and let caller attempt something else.
1279  */
1280  if (RT_G_DEBUG&DEBUG_CUTDETAIL) {
1281  static char axis_str[] = "XYZw";
1282  bu_log("rt_ct_box: no luck, len=%zu, axis=%c\n",
1283  cutp->bn.bn_len, axis_str[axis]);
1284  }
1285  rt_ct_free(rtip, rhs);
1286  rt_ct_free(rtip, lhs);
1287  return 0; /* fail */
1288  }
1289 
1290  /* Success, convert callers box node into a cut node */
1291  rt_ct_release_storage(cutp);
1292 
1293  cutp->cut_type = CUT_CUTNODE;
1294  cutp->cn.cn_axis = axis;
1295  cutp->cn.cn_point = where;
1296  cutp->cn.cn_l = lhs;
1297  cutp->cn.cn_r = rhs;
1298  return 1; /* success */
1299 }
1300 
1301 
1302 /**
1303  * See if any part of the solid is contained within the bounding box
1304  * (RPP).
1305  *
1306  * If the solid RPP at least partly overlaps the bounding RPP, invoke
1307  * the per-solid "classifier" method to perform a more rigorous check.
1308  *
1309  * Returns -
1310  * !0 if object overlaps box.
1311  * 0 if no overlap.
1312  */
1313 HIDDEN int
1314 rt_ck_overlap(register const fastf_t *min, register const fastf_t *max, register const struct soltab *stp, register const struct rt_i *rtip)
1315 {
1316  RT_CHECK_SOLTAB(stp);
1317  if (RT_G_DEBUG&DEBUG_BOXING) {
1318  bu_log("rt_ck_overlap(%s)\n", stp->st_name);
1319  VPRINT(" box min", min);
1320  VPRINT(" sol min", stp->st_min);
1321  VPRINT(" box max", max);
1322  VPRINT(" sol max", stp->st_max);
1323  }
1324  /* Ignore "dead" solids in the list. (They failed prep) */
1325  if (stp->st_aradius <= 0) return 0;
1326 
1327  /* Only check RPP on finite solids */
1328  if (stp->st_aradius < INFINITY) {
1329  if (V3RPP_DISJOINT(stp->st_min, stp->st_max, min, max))
1330  goto fail;
1331  }
1332 
1333  if (!OBJ[stp->st_id].ft_classify)
1334  goto fail;
1335 
1336  /* RPP overlaps, invoke per-solid method for detailed check */
1337  if (OBJ[stp->st_id].ft_classify(stp, min, max, &rtip->rti_tol) == BN_CLASSIFY_OUTSIDE)
1338  goto fail;
1339 
1340  if (RT_G_DEBUG&DEBUG_BOXING)
1341  bu_log("rt_ck_overlap: TRUE\n");
1342 
1343  return 1;
1344 
1345 fail:
1346  if (RT_G_DEBUG&DEBUG_BOXING)
1347  bu_log("rt_ck_overlap: FALSE\n");
1348 
1349  return 0;
1350 }
1351 
1352 
1353 /**
1354  * Returns the total number of solids and solid "pieces" in a boxnode.
1355  */
1356 HIDDEN size_t
1357 rt_ct_piececount(const union cutter *cutp)
1358 {
1359  long i;
1360  size_t count;
1361 
1362  BU_ASSERT(cutp->cut_type == CUT_BOXNODE);
1363 
1364  count = cutp->bn.bn_len;
1365 
1366  if (cutp->bn.bn_piecelen <= 0 || !cutp->bn.bn_piecelist)
1367  return count;
1368 
1369  for (i = cutp->bn.bn_piecelen-1; i >= 0; i--) {
1370  count += cutp->bn.bn_piecelist[i].npieces;
1371  }
1372  return count;
1373 }
1374 
1375 
1376 /*
1377  * Optimize a cut tree. Work on nodes which are over the pre-set
1378  * limits, subdividing until either the limit on tree depth runs out,
1379  * or until subdivision no longer gives different results, which could
1380  * easily be the case when several solids involved in a CSG operation
1381  * overlap in space.
1382  */
1383 HIDDEN void
1384 rt_ct_optim(struct rt_i *rtip, register union cutter *cutp, size_t depth)
1385 {
1386  size_t oldlen;
1387 
1388  if (cutp->cut_type == CUT_CUTNODE) {
1389  rt_ct_optim(rtip, cutp->cn.cn_l, depth+1);
1390  rt_ct_optim(rtip, cutp->cn.cn_r, depth+1);
1391  return;
1392  }
1393  if (cutp->cut_type != CUT_BOXNODE) {
1394  bu_log("rt_ct_optim: bad node [%d]\n", cutp->cut_type);
1395  return;
1396  }
1397 
1398  oldlen = rt_ct_piececount(cutp); /* save before rt_ct_box() */
1400  bu_log("rt_ct_optim(cutp=%p, depth=%zu) piececount=%zu\n", (void *)cutp, depth, oldlen);
1401 
1402  /*
1403  * BOXNODE (leaf)
1404  */
1405  if (oldlen <= 1)
1406  return; /* this box is already optimal */
1407  if (depth > rtip->rti_cutdepth) return; /* too deep */
1408 
1409  /* Attempt to subdivide finer than rtip->rti_cutlen near treetop */
1410  /**** XXX This test can be improved ****/
1411  if (depth >= 6 && oldlen <= rtip->rti_cutlen)
1412  return; /* Fine enough */
1413 #ifdef NEW_WAY
1414  /* New way */
1415  /*
1416  * Attempt to make an optimal cut
1417  */
1418  if (rt_ct_plan(rtip, cutp) < 0) {
1419  /* Unable to further subdivide this box node */
1420  return;
1421  }
1422 #else
1423  /* Old (Release 3.7) way */
1424  {
1425  int did_a_cut;
1426  int i;
1427  int axis;
1428  double where, offcenter;
1429  /*
1430  * In general, keep subdividing until things don't get any
1431  * better. Really we might want to proceed for 2-3 levels.
1432  *
1433  * First, make certain this is a worthwhile cut. In absolute
1434  * terms, each box must be at least 1mm wide after cut.
1435  */
1436  axis = AXIS(depth);
1437  did_a_cut = 0;
1438  for (i=0; i<3; i++, axis += 1) {
1439  if (axis > Z) {
1440  axis = X;
1441  }
1442  if (cutp->bn.bn_max[axis]-cutp->bn.bn_min[axis] < 2.0) {
1443  continue;
1444  }
1445  if (rt_ct_old_assess(cutp, axis, &where, &offcenter) <= 0) {
1446  continue;
1447  }
1448  if (rt_ct_box(rtip, cutp, axis, where, 0) == 0) {
1449  continue;
1450  } else {
1451  did_a_cut = 1;
1452  break;
1453  }
1454  }
1455 
1456  if (!did_a_cut) {
1457  return;
1458  }
1459  if (rt_ct_piececount(cutp->cn.cn_l) >= oldlen &&
1460  rt_ct_piececount(cutp->cn.cn_r) >= oldlen) {
1461  if (RT_G_DEBUG&DEBUG_CUTDETAIL)
1462  bu_log("rt_ct_optim(cutp=%p, depth=%zu) oldlen=%zu, lhs=%zu, rhs=%zu, hopeless\n",
1463  (void *)cutp, depth, oldlen,
1464  rt_ct_piececount(cutp->cn.cn_l),
1465  rt_ct_piececount(cutp->cn.cn_r));
1466  return; /* hopeless */
1467  }
1468  }
1469 #endif
1470  /* Box node is now a cut node, recurse */
1471  rt_ct_optim(rtip, cutp->cn.cn_l, depth+1);
1472  rt_ct_optim(rtip, cutp->cn.cn_r, depth+1);
1473 }
1474 
1475 
1476 /**
1477  * NOTE: Changing from rt_ct_assess() to this seems to result in a
1478  * *massive* change in cut tree size.
1479  *
1480  * This version results in nbins=22, maxlen=3, avg=1.09, while new
1481  * version results in nbins=42, maxlen=3, avg=1.667 (on moss.g).
1482  */
1483 HIDDEN int
1484 rt_ct_old_assess(register union cutter *cutp, register int axis, double *where_p, double *offcenter_p)
1485 {
1486  double val;
1487  double offcenter; /* Closest distance from midpoint */
1488  double where; /* Point closest to midpoint */
1489  double middle; /* midpoint */
1490  double d;
1491  fastf_t max, min;
1492  register size_t i;
1493  long il;
1494  register double left, right;
1495 
1497  bu_log("rt_ct_old_assess(%p, %c)\n", (void *)cutp, "XYZ345"[axis]);
1498 
1499  /* In absolute terms, each box must be at least 1mm wide after cut. */
1500  if ((right=cutp->bn.bn_max[axis])-(left=cutp->bn.bn_min[axis]) < 2.0)
1501  return 0;
1502 
1503  /*
1504  * Split distance between min and max in half. Find the closest
1505  * edge of a solid's bounding RPP to the mid-point, and split
1506  * there. This should ordinarily guarantee that at least one side
1507  * of the cut has one less item in it.
1508  */
1509  min = MAX_FASTF;
1510  max = -min;
1511  where = left;
1512  middle = (left + right) * 0.5;
1513  offcenter = middle - where; /* how far off 'middle', 'where' is */
1514  for (i=0; i < cutp->bn.bn_len; i++) {
1515  val = cutp->bn.bn_list[i]->st_min[axis];
1516  if (val < min) min = val;
1517  if (val > max) max = val;
1518  d = val - middle;
1519  if (d < 0) d = (-d);
1520  if (d < offcenter) {
1521  offcenter = d;
1522  where = val-0.1;
1523  }
1524  val = cutp->bn.bn_list[i]->st_max[axis];
1525  if (val < min) min = val;
1526  if (val > max) max = val;
1527  d = val - middle;
1528  if (d < 0) d = (-d);
1529  if (d < offcenter) {
1530  offcenter = d;
1531  where = val+0.1;
1532  }
1533  }
1534 
1535  /* Loop over all the solid pieces */
1536  for (il = cutp->bn.bn_piecelen-1; il >= 0; il--) {
1537  struct rt_piecelist *plp = &cutp->bn.bn_piecelist[il];
1538  struct soltab *stp = plp->stp;
1539  int j;
1540 
1541  RT_CK_PIECELIST(plp);
1542  for (j = plp->npieces-1; j >= 0; j--) {
1543  int indx = plp->pieces[j];
1544  struct bound_rpp *rpp = &stp->st_piece_rpps[indx];
1545 
1546  val = rpp->min[axis];
1547  if (val < min) min = val;
1548  if (val > max) max = val;
1549  d = val - middle;
1550  if (d < 0) d = (-d);
1551  if (d < offcenter) {
1552  offcenter = d;
1553  where = val-0.1;
1554  }
1555  val = rpp->max[axis];
1556  if (val < min) min = val;
1557  if (val > max) max = val;
1558  d = val - middle;
1559  if (d < 0) d = (-d);
1560  if (d < offcenter) {
1561  offcenter = d;
1562  where = val+0.1;
1563  }
1564  }
1565  }
1566 
1567  if (RT_G_DEBUG&DEBUG_CUTDETAIL)bu_log("rt_ct_old_assess() left=%g, where=%g, right=%g, offcenter=%g\n",
1568 
1569  left, where, right, offcenter);
1570 
1571  if (where < min || where > max) {
1572  /* this will make an empty cell. try splitting the range
1573  * instead
1574  */
1575  where = (max + min) / 2.0;
1576  offcenter = where - middle;
1577  if (offcenter < 0) {
1578  offcenter = -offcenter;
1579  }
1580  }
1581 
1582  if (where <= left || where >= right)
1583  return 0; /* not reasonable */
1584 
1585  if (where - left <= 1.0 || right - where <= 1.0)
1586  return 0; /* cut will be too small */
1587 
1588  /* We are going to cut */
1589  *where_p = where;
1590  *offcenter_p = offcenter;
1591  return 1;
1592 }
1593 
1594 
1595 /*
1596  * This routine must run in parallel
1597  */
1598 HIDDEN union cutter *
1599 rt_ct_get(struct rt_i *rtip)
1600 {
1601  register union cutter *cutp;
1602 
1603  RT_CK_RTI(rtip);
1605  if (!rtip->rti_busy_cutter_nodes.l.magic)
1606  bu_ptbl_init(&rtip->rti_busy_cutter_nodes, 128, "rti_busy_cutter_nodes");
1607 
1608  if (rtip->rti_CutFree == CUTTER_NULL) {
1609  size_t bytes;
1610 
1611  bytes = (size_t)bu_malloc_len_roundup(64*sizeof(union cutter));
1612  cutp = (union cutter *)bu_calloc(1, bytes, " rt_ct_get");
1613  /* Remember this allocation for later */
1614  bu_ptbl_ins(&rtip->rti_busy_cutter_nodes, (long *)cutp);
1615  /* Now, dice it up */
1616  while (bytes >= sizeof(union cutter)) {
1617  cutp->cut_forw = rtip->rti_CutFree;
1618  rtip->rti_CutFree = cutp++;
1619  bytes -= sizeof(union cutter);
1620  }
1621  }
1622  cutp = rtip->rti_CutFree;
1623  rtip->rti_CutFree = cutp->cut_forw;
1625 
1626  cutp->cut_forw = CUTTER_NULL;
1627  return cutp;
1628 }
1629 
1630 
1631 /*
1632  * Release subordinate storage
1633  */
1634 HIDDEN void
1635 rt_ct_release_storage(register union cutter *cutp)
1636 {
1637  size_t i;
1638 
1639  switch (cutp->cut_type) {
1640 
1641  case CUT_CUTNODE:
1642  break;
1643 
1644  case CUT_BOXNODE:
1645  if (cutp->bn.bn_list) {
1646  bu_free((char *)cutp->bn.bn_list, "bn_list[]");
1647  cutp->bn.bn_list = (struct soltab **)NULL;
1648  }
1649  cutp->bn.bn_len = 0;
1650  cutp->bn.bn_maxlen = 0;
1651 
1652  if (cutp->bn.bn_piecelist) {
1653  for (i=0; i<cutp->bn.bn_piecelen; i++) {
1654  struct rt_piecelist *olp = &cutp->bn.bn_piecelist[i];
1655  if (olp->pieces) {
1656  bu_free((char *)olp->pieces, "olp->pieces");
1657  }
1658  }
1659  bu_free((char *)cutp->bn.bn_piecelist, "bn_piecelist[]");
1660  cutp->bn.bn_piecelist = (struct rt_piecelist *)NULL;
1661  }
1662  cutp->bn.bn_piecelen = 0;
1663  cutp->bn.bn_maxpiecelen = 0;
1664  break;
1665 
1666  case CUT_NUGRIDNODE:
1667  bu_free((void *)cutp->nugn.nu_grid, "NUGrid children");
1668  cutp->nugn.nu_grid = NULL; /* sanity */
1669 
1670  for (i=0; i<3; i++) {
1671  bu_free((void *)cutp->nugn.nu_axis[i],
1672  "NUGrid axis");
1673  cutp->nugn.nu_axis[i] = NULL; /* sanity */
1674  }
1675  break;
1676 
1677  default:
1678  bu_log("rt_ct_release_storage: Unknown type [%d]\n", cutp->cut_type);
1679  break;
1680  }
1681 }
1682 
1683 
1684 /*
1685  * This routine must run in parallel
1686  */
1687 HIDDEN void
1688 rt_ct_free(struct rt_i *rtip, register union cutter *cutp)
1689 {
1690  RT_CK_RTI(rtip);
1691 
1692  rt_ct_release_storage(cutp);
1693 
1694  /* Put on global free list */
1696  cutp->cut_forw = rtip->rti_CutFree;
1697  rtip->rti_CutFree = cutp;
1699 }
1700 
1701 
1702 void
1703 rt_pr_cut(const union cutter *cutp, int lvl)
1704 {
1705  size_t i, j;
1706 
1707  bu_log("%p ", (void *)cutp);
1708  for (i=lvl; i>0; i--)
1709  bu_log(" ");
1710 
1711  if (cutp == CUTTER_NULL) {
1712  bu_log("Null???\n");
1713  return;
1714  }
1715 
1716  switch (cutp->cut_type) {
1717 
1718  case CUT_CUTNODE:
1719  bu_log("CUT L %c < %f\n",
1720  "XYZ?"[cutp->cn.cn_axis],
1721  cutp->cn.cn_point);
1722  rt_pr_cut(cutp->cn.cn_l, lvl+1);
1723 
1724  bu_log("%p ", (void *)cutp);
1725  for (i=lvl; i>0; i--)
1726  bu_log(" ");
1727  bu_log("CUT R %c >= %f\n",
1728  "XYZ?"[cutp->cn.cn_axis],
1729  cutp->cn.cn_point);
1730  rt_pr_cut(cutp->cn.cn_r, lvl+1);
1731  return;
1732 
1733  case CUT_BOXNODE:
1734  bu_log("BOX Contains %zu primitives (%zu alloc), %zu primitives with pieces:\n",
1735  cutp->bn.bn_len, cutp->bn.bn_maxlen,
1736  cutp->bn.bn_piecelen);
1737  bu_log(" ");
1738  for (i=lvl; i>0; i--)
1739  bu_log(" ");
1740  VPRINT(" min", cutp->bn.bn_min);
1741  bu_log(" ");
1742  for (i=lvl; i>0; i--)
1743  bu_log(" ");
1744  VPRINT(" max", cutp->bn.bn_max);
1745 
1746  /* Print names of regular solids */
1747  for (i=0; i < cutp->bn.bn_len; i++) {
1748  bu_log(" ");
1749  for (j=lvl; j>0; j--)
1750  bu_log(" ");
1751  bu_log(" %s\n",
1752  cutp->bn.bn_list[i]->st_name);
1753  }
1754 
1755  /* Print names and piece lists of solids with pieces */
1756  for (i=0; i < cutp->bn.bn_piecelen; i++) {
1757  struct rt_piecelist *plp = &(cutp->bn.bn_piecelist[i]);
1758  struct soltab *stp;
1759 
1760  RT_CK_PIECELIST(plp);
1761  stp = plp->stp;
1762  RT_CK_SOLTAB(stp);
1763 
1764  bu_log(" ");
1765  for (j=lvl; j>0; j--)
1766  bu_log(" ");
1767  bu_log(" %s, %ld pieces: ",
1768  stp->st_name, plp->npieces);
1769 
1770  /* Loop for every piece of this solid */
1771  for (j=0; j < plp->npieces; j++) {
1772  long indx = plp->pieces[j];
1773  bu_log("%ld, ", indx);
1774  }
1775  bu_log("\n");
1776  }
1777  return;
1778 
1779  case CUT_NUGRIDNODE:
1780  /* not implemented yet */
1781  default:
1782  bu_log("Unknown type [%d]\n", cutp->cut_type);
1783  break;
1784  }
1785  return;
1786 }
1787 
1788 
1789 void
1790 rt_fr_cut(struct rt_i *rtip, register union cutter *cutp)
1791 {
1792  RT_CK_RTI(rtip);
1793  if (cutp == CUTTER_NULL) {
1794  bu_log("rt_fr_cut NULL\n");
1795  return;
1796  }
1797 
1798  switch (cutp->cut_type) {
1799 
1800  case CUT_CUTNODE:
1801  rt_fr_cut(rtip, cutp->cn.cn_l);
1802  rt_ct_free(rtip, cutp->cn.cn_l);
1803  cutp->cn.cn_l = CUTTER_NULL;
1804 
1805  rt_fr_cut(rtip, cutp->cn.cn_r);
1806  rt_ct_free(rtip, cutp->cn.cn_r);
1807  cutp->cn.cn_r = CUTTER_NULL;
1808  return;
1809 
1810  case CUT_BOXNODE:
1811  rt_ct_release_storage(cutp);
1812  return;
1813 
1814  case CUT_NUGRIDNODE: {
1815  register int i;
1816  int len = cutp->nugn.nu_cells_per_axis[X] *
1817  cutp->nugn.nu_cells_per_axis[Y] *
1818  cutp->nugn.nu_cells_per_axis[Z];
1819  register union cutter *bp = cutp->nugn.nu_grid;
1820 
1821  for (i = len-1; i >= 0; i--) {
1822  rt_fr_cut(rtip, bp);
1823  bp->cut_type = 7; /* sanity */
1824  bp++;
1825  }
1826 
1827  rt_ct_release_storage(cutp);
1828  return; }
1829 
1830  default:
1831  bu_log("rt_fr_cut: Unknown type [%d]\n", cutp->cut_type);
1832  break;
1833  }
1834  return;
1835 }
1836 
1837 
1838 HIDDEN void
1839 rt_plot_cut(FILE *fp, struct rt_i *rtip, register union cutter *cutp, int lvl)
1840 {
1841  RT_CK_RTI(rtip);
1842  switch (cutp->cut_type) {
1843  case CUT_NUGRIDNODE: {
1844  union cutter *bp;
1845  int i, x, y, z;
1846  int xmax = cutp->nugn.nu_cells_per_axis[X],
1847  ymax = cutp->nugn.nu_cells_per_axis[Y],
1848  zmax = cutp->nugn.nu_cells_per_axis[Z];
1849  if (!cutp->nugn.nu_grid) return;
1850  /* Don't draw the boxnodes since that produces far too
1851  * many segments. Optimize the output a little by drawing
1852  * whole line segments (below).
1853  */
1854  for (i=0, bp=cutp->nugn.nu_grid; i < xmax*ymax*zmax; i++, bp++) {
1855  if (bp->cut_type != CUT_BOXNODE)
1856  rt_plot_cut(fp, rtip, bp, lvl);
1857  }
1858  pl_color(fp, 180, 180, 220);
1859  --xmax; --ymax; --zmax;
1860 
1861  /* XY plane */
1862  pd_3line(fp,
1863  cutp->nugn.nu_axis[X][0].nu_spos,
1864  cutp->nugn.nu_axis[Y][0].nu_spos,
1865  cutp->nugn.nu_axis[Z][0].nu_spos,
1866  cutp->nugn.nu_axis[X][0].nu_spos,
1867  cutp->nugn.nu_axis[Y][0].nu_spos,
1868  cutp->nugn.nu_axis[Z][zmax].nu_epos);
1869  for (y=0; y<=ymax; y++) {
1870  pd_3line(fp,
1871  cutp->nugn.nu_axis[X][0].nu_spos,
1872  cutp->nugn.nu_axis[Y][y].nu_epos,
1873  cutp->nugn.nu_axis[Z][0].nu_spos,
1874  cutp->nugn.nu_axis[X][0].nu_spos,
1875  cutp->nugn.nu_axis[Y][y].nu_epos,
1876  cutp->nugn.nu_axis[Z][zmax].nu_epos);
1877  }
1878  for (x=0; x<=xmax; x++) {
1879  pd_3line(fp,
1880  cutp->nugn.nu_axis[X][x].nu_epos,
1881  cutp->nugn.nu_axis[Y][0].nu_spos,
1882  cutp->nugn.nu_axis[Z][0].nu_spos,
1883  cutp->nugn.nu_axis[X][x].nu_epos,
1884  cutp->nugn.nu_axis[Y][0].nu_spos,
1885  cutp->nugn.nu_axis[Z][zmax].nu_epos);
1886  for (y=0; y<=ymax; y++) {
1887  pd_3line(fp,
1888  cutp->nugn.nu_axis[X][x].nu_epos,
1889  cutp->nugn.nu_axis[Y][y].nu_epos,
1890  cutp->nugn.nu_axis[Z][0].nu_spos,
1891  cutp->nugn.nu_axis[X][x].nu_epos,
1892  cutp->nugn.nu_axis[Y][y].nu_epos,
1893  cutp->nugn.nu_axis[Z][zmax].nu_epos);
1894  }
1895  }
1896 
1897  /* YZ plane */
1898  pd_3line(fp,
1899  cutp->nugn.nu_axis[X][0].nu_spos,
1900  cutp->nugn.nu_axis[Y][0].nu_spos,
1901  cutp->nugn.nu_axis[Z][0].nu_spos,
1902  cutp->nugn.nu_axis[X][xmax].nu_epos,
1903  cutp->nugn.nu_axis[Y][0].nu_spos,
1904  cutp->nugn.nu_axis[Z][0].nu_spos);
1905  for (z=0; z<=zmax; z++) {
1906  pd_3line(fp,
1907  cutp->nugn.nu_axis[X][0].nu_spos,
1908  cutp->nugn.nu_axis[Y][0].nu_spos,
1909  cutp->nugn.nu_axis[Z][z].nu_epos,
1910  cutp->nugn.nu_axis[X][zmax].nu_epos,
1911  cutp->nugn.nu_axis[Y][0].nu_spos,
1912  cutp->nugn.nu_axis[Z][z].nu_epos);
1913  }
1914  for (y=0; y<=ymax; y++) {
1915  pd_3line(fp,
1916  cutp->nugn.nu_axis[X][0].nu_spos,
1917  cutp->nugn.nu_axis[Y][y].nu_epos,
1918  cutp->nugn.nu_axis[Z][0].nu_spos,
1919  cutp->nugn.nu_axis[X][xmax].nu_epos,
1920  cutp->nugn.nu_axis[Y][y].nu_epos,
1921  cutp->nugn.nu_axis[Z][0].nu_spos);
1922  for (z=0; z<=zmax; z++) {
1923  pd_3line(fp,
1924  cutp->nugn.nu_axis[X][0].nu_spos,
1925  cutp->nugn.nu_axis[Y][y].nu_epos,
1926  cutp->nugn.nu_axis[Z][z].nu_epos,
1927  cutp->nugn.nu_axis[X][zmax].nu_epos,
1928  cutp->nugn.nu_axis[Y][y].nu_epos,
1929  cutp->nugn.nu_axis[Z][z].nu_epos);
1930  }
1931  }
1932 
1933  /* XZ plane */
1934  pd_3line(fp,
1935  cutp->nugn.nu_axis[X][0].nu_spos,
1936  cutp->nugn.nu_axis[Y][0].nu_spos,
1937  cutp->nugn.nu_axis[Z][0].nu_spos,
1938  cutp->nugn.nu_axis[X][0].nu_spos,
1939  cutp->nugn.nu_axis[Y][ymax].nu_epos,
1940  cutp->nugn.nu_axis[Z][0].nu_spos);
1941  for (z=0; z<=zmax; z++) {
1942  pd_3line(fp,
1943  cutp->nugn.nu_axis[X][0].nu_spos,
1944  cutp->nugn.nu_axis[Y][0].nu_spos,
1945  cutp->nugn.nu_axis[Z][z].nu_epos,
1946  cutp->nugn.nu_axis[X][0].nu_spos,
1947  cutp->nugn.nu_axis[Y][ymax].nu_epos,
1948  cutp->nugn.nu_axis[Z][z].nu_epos);
1949  }
1950  for (x=0; x<=xmax; x++) {
1951  pd_3line(fp,
1952  cutp->nugn.nu_axis[X][x].nu_epos,
1953  cutp->nugn.nu_axis[Y][0].nu_spos,
1954  cutp->nugn.nu_axis[Z][0].nu_spos,
1955  cutp->nugn.nu_axis[X][x].nu_epos,
1956  cutp->nugn.nu_axis[Y][ymax].nu_epos,
1957  cutp->nugn.nu_axis[Z][0].nu_spos);
1958  for (z=0; z<=zmax; z++) {
1959  pd_3line(fp,
1960  cutp->nugn.nu_axis[X][x].nu_epos,
1961  cutp->nugn.nu_axis[Y][0].nu_spos,
1962  cutp->nugn.nu_axis[Z][z].nu_epos,
1963  cutp->nugn.nu_axis[X][x].nu_epos,
1964  cutp->nugn.nu_axis[Y][ymax].nu_epos,
1965  cutp->nugn.nu_axis[Z][z].nu_epos);
1966  }
1967  }
1968 
1969  return; }
1970  case CUT_CUTNODE:
1971  rt_plot_cut(fp, rtip, cutp->cn.cn_l, lvl+1);
1972  rt_plot_cut(fp, rtip, cutp->cn.cn_r, lvl+1);
1973  return;
1974  case CUT_BOXNODE:
1975  /* Should choose color based on lvl, need a table */
1976  pl_color(fp,
1977  (AXIS(lvl)==0)?255:0,
1978  (AXIS(lvl)==1)?255:0,
1979  (AXIS(lvl)==2)?255:0);
1980  pdv_3box(fp, cutp->bn.bn_min, cutp->bn.bn_max);
1981  return;
1982  }
1983  return;
1984 }
1985 
1986 
1987 /*
1988  * Find the maximum number of solids in a leaf node, and other
1989  * interesting statistics.
1990  */
1991 HIDDEN void
1992 rt_ct_measure(register struct rt_i *rtip, register union cutter *cutp, int depth)
1993 {
1994  register int len;
1995 
1996  RT_CK_RTI(rtip);
1997  switch (cutp->cut_type) {
1998  case CUT_NUGRIDNODE: {
1999  register int i;
2000  register union cutter *bp;
2001  len = cutp->nugn.nu_cells_per_axis[X] *
2002  cutp->nugn.nu_cells_per_axis[Y] *
2003  cutp->nugn.nu_cells_per_axis[Z];
2005  for (i=0, bp=cutp->nugn.nu_grid; i<len; i++, bp++)
2006  rt_ct_measure(rtip, bp, depth+1);
2007  return; }
2008  case CUT_CUTNODE:
2009  rtip->rti_ncut_by_type[CUT_CUTNODE]++;
2010  rt_ct_measure(rtip, cutp->cn.cn_l, len = (depth+1));
2011  rt_ct_measure(rtip, cutp->cn.cn_r, len);
2012  return;
2013  case CUT_BOXNODE:
2014  rtip->rti_ncut_by_type[CUT_BOXNODE]++;
2015  rtip->rti_cut_totobj += (len = cutp->bn.bn_len);
2016  if (rtip->rti_cut_maxlen < len)
2017  rtip->rti_cut_maxlen = len;
2018  if (rtip->rti_cut_maxdepth < depth)
2019  rtip->rti_cut_maxdepth = depth;
2020  BU_HIST_TALLY(&rtip->rti_hist_cellsize, len);
2021  len = rt_ct_piececount(cutp) - len;
2022  BU_HIST_TALLY(&rtip->rti_hist_cell_pieces, len);
2023  BU_HIST_TALLY(&rtip->rti_hist_cutdepth, depth);
2024  if (len == 0) {
2025  rtip->nempty_cells++;
2026  }
2027  return;
2028  default:
2029  bu_log("rt_ct_measure: bad node [%d]\n", cutp->cut_type);
2030  return;
2031  }
2032 }
2033 
2034 
2035 void
2036 rt_cut_clean(struct rt_i *rtip)
2037 {
2038  void **p;
2039 
2040  RT_CK_RTI(rtip);
2041 
2042  if (rtip->rti_cuts_waiting.l.magic)
2044 
2045  /* Abandon the linked list of diced-up structures */
2046  rtip->rti_CutFree = CUTTER_NULL;
2047 
2049  return;
2050 
2051  /* Release the blocks we got from bu_calloc() */
2052  for (BU_PTBL_FOR(p, (void **), &rtip->rti_busy_cutter_nodes)) {
2053  bu_free(*p, "rt_ct_get");
2054  }
2056 }
2057 
2058 
2059 void
2060 rt_pr_cut_info(const struct rt_i *rtip, const char *str)
2061 {
2062  const struct nugridnode *nugnp;
2063  int i;
2064 
2065  RT_CK_RTI(rtip);
2066 
2067  bu_log("%s %s: %d nu, %d cut, %d box (%ld empty)\n",
2068  str,
2070  "NUGrid" : "NUBSP",
2074  rtip->nempty_cells);
2075  bu_log("Cut: maxdepth=%d, nbins=%d, maxlen=%d, avg=%g\n",
2076  rtip->rti_cut_maxdepth,
2078  rtip->rti_cut_maxlen,
2079  ((double)rtip->rti_cut_totobj) /
2080  rtip->rti_ncut_by_type[CUT_BOXNODE]);
2082  "cut_tree: Number of primitives per leaf cell");
2084  "cut_tree: Number of primitive pieces per leaf cell");
2086  "cut_tree: Depth (height)");
2087 
2088  switch (rtip->rti_space_partition) {
2089  case RT_PART_NUGRID:
2090  nugnp = (const struct nugridnode *)&rtip->rti_CutHead.nugn;
2091  if (nugnp->nu_type != CUT_NUGRIDNODE)
2092  bu_bomb("rt_pr_cut_info: passed non-nugridnode");
2093 
2094  for (i=0; i<3; i++) {
2095  register int j;
2096  bu_log("NUgrid %c axis: %d cells\n", "XYZ*"[i],
2097  nugnp->nu_cells_per_axis[i]);
2098  for (j=0; j<nugnp->nu_cells_per_axis[i]; j++) {
2099  bu_log(" %g .. %g, w=%g\n",
2100  nugnp->nu_axis[i][j].nu_spos,
2101  nugnp->nu_axis[i][j].nu_epos,
2102  nugnp->nu_axis[i][j].nu_width);
2103  }
2104  }
2105  break;
2106  case RT_PART_NUBSPT:
2107  /* Anything good to print here? */
2108  break;
2109  default:
2110  bu_bomb("rt_pr_cut_info() bad rti_space_partition\n");
2111  }
2112 }
2113 
2114 
2115 void
2116 remove_from_bsp(struct soltab *stp, union cutter *cutp, struct bn_tol *tol)
2117 {
2118  size_t idx;
2119  size_t i;
2120 
2121  switch (cutp->cut_type) {
2122  case CUT_BOXNODE:
2123  if (stp->st_npieces) {
2124  int remove_count, new_count;
2125  struct rt_piecelist *new_piece_list;
2126 
2127  idx = 0;
2128  remove_count = 0;
2129  for (idx=0; idx<cutp->bn.bn_piecelen; idx++) {
2130  if (cutp->bn.bn_piecelist[idx].stp == stp) {
2131  remove_count++;
2132  }
2133  }
2134 
2135  if (remove_count) {
2136  new_count = cutp->bn.bn_piecelen - remove_count;
2137  if (new_count > 0) {
2138  new_piece_list = (struct rt_piecelist *)bu_calloc(
2139  new_count,
2140  sizeof(struct rt_piecelist),
2141  "bn_piecelist");
2142 
2143  i = 0;
2144  for (idx=0; idx<cutp->bn.bn_piecelen; idx++) {
2145  if (cutp->bn.bn_piecelist[idx].stp != stp) {
2146  new_piece_list[i] = cutp->bn.bn_piecelist[idx];
2147  i++;
2148  }
2149  }
2150  } else {
2151  new_count = 0;
2152  new_piece_list = NULL;
2153  }
2154 
2155  for (idx=0; idx<cutp->bn.bn_piecelen; idx++) {
2156  if (cutp->bn.bn_piecelist[idx].stp == stp) {
2157  bu_free(cutp->bn.bn_piecelist[idx].pieces, "pieces");
2158  }
2159  }
2160  bu_free(cutp->bn.bn_piecelist, "piecelist");
2161  cutp->bn.bn_piecelist = new_piece_list;
2162  cutp->bn.bn_piecelen = new_count;
2163  cutp->bn.bn_maxpiecelen = new_count;
2164  }
2165  } else {
2166  for (idx=0; idx < cutp->bn.bn_len; idx++) {
2167  if (cutp->bn.bn_list[idx] == stp) {
2168  /* found it, now remove it */
2169  cutp->bn.bn_len--;
2170  for (i=idx; i < cutp->bn.bn_len; i++) {
2171  cutp->bn.bn_list[i] = cutp->bn.bn_list[i+1];
2172  }
2173  return;
2174  }
2175  }
2176  }
2177  break;
2178  case CUT_CUTNODE:
2179  if (stp->st_min[cutp->cn.cn_axis] > cutp->cn.cn_point + tol->dist) {
2180  remove_from_bsp(stp, cutp->cn.cn_r, tol);
2181  } else if (stp->st_max[cutp->cn.cn_axis] < cutp->cn.cn_point - tol->dist) {
2182  remove_from_bsp(stp, cutp->cn.cn_l, tol);
2183  } else {
2184  remove_from_bsp(stp, cutp->cn.cn_r, tol);
2185  remove_from_bsp(stp, cutp->cn.cn_l, tol);
2186  }
2187  break;
2188  default:
2189  bu_log("remove_from_bsp(): unrecognized cut type (%d) in BSP!\n", cutp->cut_type);
2190  bu_bomb("remove_from_bsp(): unrecognized cut type in BSP!\n");
2191  }
2192 }
2193 
2194 
2195 #define PIECE_BLOCK 512
2196 
2197 void
2198 insert_in_bsp(struct soltab *stp, union cutter *cutp)
2199 {
2200  int i, j;
2201 
2202  switch (cutp->cut_type) {
2203  case CUT_BOXNODE:
2204  if (stp->st_npieces == 0) {
2205  /* add the solid in this box */
2206  if (cutp->bn.bn_len >= cutp->bn.bn_maxlen) {
2207  /* need more space */
2208  if (cutp->bn.bn_maxlen <= 0) {
2209  /* Initial allocation */
2210  cutp->bn.bn_maxlen = 5;
2211  cutp->bn.bn_list = (struct soltab **)bu_calloc(
2212  cutp->bn.bn_maxlen, sizeof(struct soltab *),
2213  "insert_in_bsp: initial list alloc");
2214  } else {
2215  cutp->bn.bn_maxlen += 5;
2216  cutp->bn.bn_list = (struct soltab **) bu_realloc(
2217  (void *)cutp->bn.bn_list,
2218  sizeof(struct soltab *) * cutp->bn.bn_maxlen,
2219  "insert_in_bsp: list extend");
2220  }
2221  }
2222  cutp->bn.bn_list[cutp->bn.bn_len++] = stp;
2223 
2224  } else {
2225  /* this solid uses pieces, add the appropriate pieces to this box */
2226  long pieces[PIECE_BLOCK];
2227  long *more_pieces=NULL;
2228  long more_pieces_alloced=0;
2229  long more_pieces_count=0;
2230  long piece_count=0;
2231  struct rt_piecelist *plp;
2232 
2233  for (i=0; i<stp->st_npieces; i++) {
2234  struct bound_rpp *piece_rpp=&stp->st_piece_rpps[i];
2235  if (V3RPP_OVERLAP(piece_rpp->min, piece_rpp->max, cutp->bn.bn_min, cutp->bn.bn_max)) {
2236  if (piece_count < PIECE_BLOCK) {
2237  pieces[piece_count++] = i;
2238  } else if (more_pieces_alloced == 0) {
2239  more_pieces_alloced = stp->st_npieces - PIECE_BLOCK;
2240  more_pieces = (long *)bu_calloc(more_pieces_alloced, sizeof(long),
2241  "more_pieces");
2242  more_pieces[more_pieces_count++] = i;
2243  } else {
2244  more_pieces[more_pieces_count++] = i;
2245  }
2246  }
2247  }
2248 
2249  if (cutp->bn.bn_piecelen >= cutp->bn.bn_maxpiecelen) {
2250  cutp->bn.bn_piecelist = (struct rt_piecelist *)bu_realloc(cutp->bn.bn_piecelist,
2251  sizeof(struct rt_piecelist) * (++cutp->bn.bn_maxpiecelen),
2252  "cutp->bn.bn_piecelist");
2253  }
2254 
2255  if (!piece_count) {
2256  return;
2257  }
2258 
2259  plp = &cutp->bn.bn_piecelist[cutp->bn.bn_piecelen++];
2260  plp->magic = RT_PIECELIST_MAGIC;
2261  plp->stp = stp;
2262  plp->npieces = piece_count + more_pieces_count;
2263  plp->pieces = (long *)bu_calloc(plp->npieces, sizeof(long), "plp->pieces");
2264  for (i=0; i<piece_count; i++) {
2265  plp->pieces[i] = pieces[i];
2266  }
2267  j = piece_count;
2268  for (i=0; i<more_pieces_count; i++) {
2269  plp->pieces[j++] = more_pieces[i];
2270  }
2271 
2272  if (more_pieces) {
2273  bu_free((char *)more_pieces, "more_pieces");
2274  }
2275  }
2276  break;
2277  case CUT_CUTNODE:
2278  if (stp->st_min[cutp->cn.cn_axis] >= cutp->cn.cn_point) {
2279  insert_in_bsp(stp, cutp->cn.cn_r);
2280  } else if (stp->st_max[cutp->cn.cn_axis] < cutp->cn.cn_point) {
2281  insert_in_bsp(stp, cutp->cn.cn_l);
2282  } else {
2283  insert_in_bsp(stp, cutp->cn.cn_r);
2284  insert_in_bsp(stp, cutp->cn.cn_l);
2285  }
2286  break;
2287  default:
2288  bu_log("insert_in_bsp(): unrecognized cut type (%d) in BSP!\n", cutp->cut_type);
2289  bu_bomb("insert_in_bsp(): unrecognized cut type in BSP!\n");
2290  }
2291 
2292 }
2293 
2294 
2295 void
2296 fill_out_bsp(struct rt_i *rtip, union cutter *cutp, struct resource *resp, fastf_t bb[6])
2297 {
2298  fastf_t bb2[6];
2299  int i, j;
2300 
2301  switch (cutp->cut_type) {
2302  case CUT_BOXNODE:
2303  j = 3;
2304  for (i=0; i<3; i++) {
2305  if (bb[i] >= INFINITY) {
2306  /* this node is at the edge of the model BB, make it fill the BB */
2307  cutp->bn.bn_min[i] = rtip->mdl_min[i];
2308  }
2309  if (bb[j] <= -INFINITY) {
2310  /* this node is at the edge of the model BB, make it fill the BB */
2311  cutp->bn.bn_max[i] = rtip->mdl_max[i];
2312  }
2313  j++;
2314  }
2315  break;
2316  case CUT_CUTNODE:
2317  VMOVE(bb2, bb);
2318  VMOVE(&bb2[3], &bb[3]);
2319  bb[cutp->cn.cn_axis] = cutp->cn.cn_point;
2320  fill_out_bsp(rtip, cutp->cn.cn_r, resp, bb);
2321  bb2[cutp->cn.cn_axis + 3] = cutp->cn.cn_point;
2322  fill_out_bsp(rtip, cutp->cn.cn_l, resp, bb2);
2323  break;
2324  default:
2325  bu_log("fill_out_bsp(): unrecognized cut type (%d) in BSP!\n", cutp->cut_type);
2326  bu_bomb("fill_out_bsp(): unrecognized cut type in BSP!\n");
2327  }
2328 
2329 }
2330 
2331 
2332 /*
2333  * Local Variables:
2334  * mode: C
2335  * tab-width: 8
2336  * indent-tabs-mode: t
2337  * c-file-style: "stroustrup"
2338  * End:
2339  * ex: shiftwidth=4 tabstop=8
2340  */
Definition: db_flip.c:35
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define CMP(_p1, _p2, _memb, _ind)
Definition: cut.c:159
void bu_hist_pr(const struct bu_hist *histp, const char *title)
fastf_t bn_min[3]
Definition: raytrace.h:694
struct bu_hist rti_hist_cellsize
occupancy of cut cells
Definition: raytrace.h:1806
fastf_t hg_min
Definition: hist.h:55
HIDDEN int rt_projXmin_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:174
point_t mdl_min
min corner of model bounding RPP
Definition: raytrace.h:1769
struct soltab ** bn_list
bn_list[bn_len]
Definition: raytrace.h:696
HIDDEN int rt_projYmax_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:195
size_t rti_cutdepth
goal for depth of NUBSPT cut tree
Definition: raytrace.h:1814
#define RT_CK_PIECELIST(_p)
Definition: raytrace.h:1410
#define BN_CLASSIFY_OUTSIDE
Definition: plane_calc.h:1031
#define RT_CK_RTI(_p)
Definition: raytrace.h:1833
double dist
>= 0
Definition: tol.h:73
#define DEBUG_BOXING
16 Object/box checking details
Definition: raytrace.h:101
#define BU_PTBL_FOR(ip, cast, ptbl)
Definition: ptbl.h:125
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
#define CUT_CUTNODE
Definition: raytrace.h:718
struct bu_hist rti_hist_cutdepth
depth of cut tree
Definition: raytrace.h:1808
#define VSETALL(a, s)
Definition: color.c:54
void bu_semaphore_acquire(unsigned int i)
Definition: semaphore.c:180
point_t rti_pmin
for plotting, min RPP
Definition: raytrace.h:1771
Definition: hist.h:53
#define BU_LIST_IS_INITIALIZED(_hp)
Definition: list.h:175
fastf_t bn_max[3]
Definition: raytrace.h:695
HIDDEN void rt_ct_optim(struct rt_i *rtip, union cutter *cutp, size_t depth)
size_t bn_maxlen
of ptrs allocated to list
Definition: raytrace.h:698
#define DEBUG_PL_BOX
32 Plot(3) bounding boxes and cuts
Definition: raytrace.h:122
void bu_hist_init(struct bu_hist *histp, fastf_t min, fastf_t max, size_t nbins)
Definition: hist.c:51
fastf_t st_aradius
Radius of APPROXIMATING sphere.
Definition: raytrace.h:433
void insert_in_bsp(struct soltab *stp, union cutter *cutp)
Definition: cut.c:2198
size_t hg_nbins
Definition: hist.h:59
union cutter * rt_cut_one_axis(struct bu_ptbl *boxes, struct rt_i *rtip, int axis, int min, int max, struct nugridnode *nuginfop)
Definition: cut.c:77
Header file for the BRL-CAD common definitions.
union cutter * cut_forw
Freelist forward link.
Definition: raytrace.h:724
#define BU_CK_PTBL(_p)
Definition: ptbl.h:74
struct nu_axis * nu_axis[3]
Definition: raytrace.h:712
HIDDEN size_t rt_ct_piececount(const union cutter *cutp)
Definition: cut.c:1357
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
HIDDEN int rt_ck_overlap(const vect_t min, const vect_t max, const struct soltab *stp, const struct rt_i *rtip)
#define BU_ASSERT(_equation)
Definition: defines.h:216
int rti_nugrid_dimlimit
limit on nugrid dimensions
Definition: raytrace.h:1764
#define RT_CHECK_SOLTAB(_p)
Definition: raytrace.h:452
#define MAX_FASTF
Definition: defines.h:340
union cutter rti_inf_box
List of infinite solids.
Definition: raytrace.h:1794
point_t min
Definition: raytrace.h:415
fastf_t nu_spos
cell start position
Definition: raytrace.h:705
int rti_space_partition
space partitioning method
Definition: raytrace.h:1763
#define HIDDEN
Definition: common.h:86
HIDDEN union cutter * rt_ct_get(struct rt_i *rtip)
Definition: cut.c:1599
size_t nempty_cells
number of empty NUgrid cells
Definition: raytrace.h:1792
Definition: ptbl.h:62
void fill_out_bsp(struct rt_i *rtip, union cutter *cutp, struct resource *resp, fastf_t bb[6])
Definition: cut.c:2296
Definition: cut.c:215
if(share_geom)
Definition: nmg_mod.c:3829
Definition: color.c:49
#define DEBUG_CUTDETAIL
21 Print space cutting details
Definition: raytrace.h:106
long * pieces
pieces[npieces], piece indices
Definition: raytrace.h:1407
void * memset(void *s, int c, size_t n)
#define RT_G_DEBUG
Definition: raytrace.h:1718
#define RT_PART_NUBSPT
Definition: raytrace.h:1835
size_t bn_len
of solids in list
Definition: raytrace.h:697
#define BU_HIST_TALLY(_hp, _val)
Definition: hist.h:92
double rti_nu_gfactor
constant in numcells computation
Definition: raytrace.h:1812
struct bound_rpp * st_piece_rpps
bounding RPP of each piece of this solid
Definition: raytrace.h:446
HIDDEN int rt_projZmin_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:202
#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
#define CUT_NUGRIDNODE
Definition: raytrace.h:720
union cutter rti_CutHead
Head of cut tree.
Definition: raytrace.h:1793
int nu_stepsize[3]
number of cells to jump for one step in each axis
Definition: raytrace.h:714
#define BU_PTBL_GET(ptbl, i)
Definition: ptbl.h:108
void pdv_3space(register FILE *plotfp, const fastf_t *min, const fastf_t *max)
Definition: plot3.c:560
unsigned char * bp
Definition: rot.c:56
int cn_type
Definition: raytrace.h:685
void rt_cut_clean(struct rt_i *rtip)
Definition: cut.c:2036
void remove_from_bsp(struct soltab *stp, union cutter *cutp, struct bn_tol *tol)
Definition: cut.c:2116
point_t st_max
max X, Y, Z of bounding RPP
Definition: raytrace.h:438
struct rt_piecelist * bn_piecelist
[] solids with pieces
Definition: raytrace.h:699
void bu_sort(void *array, size_t nummemb, size_t sizememb, int(*compare)(const void *, const void *, void *), void *context)
Definition: sort.c:110
HIDDEN int rt_projYmin_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:188
int(* ft_classify)(const struct soltab *, const vect_t, const vect_t, const struct bn_tol *)
Definition: raytrace.h:2090
HIDDEN void rt_ct_release_storage(union cutter *cutp)
HIDDEN int rt_ct_old_assess(register union cutter *, register int, double *, double *)
Definition: cut.c:1484
struct bu_list l
Definition: ptbl.h:63
void rt_fr_cut(struct rt_i *rtip, register union cutter *cutp)
Definition: cut.c:1790
void * bu_realloc(void *ptr, size_t siz, const char *str)
fastf_t hg_clumpsize
Definition: hist.h:57
struct bu_ptbl rti_cuts_waiting
Definition: raytrace.h:1797
#define UNUSED(parameter)
Definition: common.h:239
int(* cmp_max)(const void *, const void *, void *)
Definition: cut.c:217
int rti_cut_maxlen
max len RPP list in 1 cut bin
Definition: raytrace.h:1798
Support for uniform tolerances.
Definition: tol.h:71
void rt_nugrid_cut(register struct nugridnode *nugnp, register struct boxnode *fromp, struct rt_i *rtip, int just_collect_info, int depth)
Definition: cut.c:230
HIDDEN void rt_ct_measure(struct rt_i *rtip, union cutter *cutp, int depth)
struct bu_hist rti_hist_cell_pieces
solid pieces per cell
Definition: raytrace.h:1807
fastf_t nu_epos
cell end position
Definition: raytrace.h:706
uint32_t magic
Magic # for mem id/check.
Definition: list.h:119
#define PIECE_BLOCK
Definition: cut.c:2195
void bu_semaphore_release(unsigned int i)
Definition: semaphore.c:218
size_t bn_piecelen
of piecelists used
Definition: raytrace.h:700
void pl_color(register FILE *plotfp, int r, int g, int b)
Definition: plot3.c:325
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
void bu_parallel(void(*func)(int func_ncpu, void *func_data), int ncpu, void *data)
int rti_hasty_prep
1=hasty prep, slower ray-trace
Definition: raytrace.h:1759
size_t bn_maxpiecelen
of piecelists allocated
Definition: raytrace.h:701
#define RT_SEM_WORKER
Definition: raytrace.h:1730
point_t max
Definition: raytrace.h:416
struct cutnode cn
Definition: raytrace.h:725
#define DEBUG_CUT
15 Print space cutting statistics
Definition: raytrace.h:100
#define RT_VISIT_ALL_SOLTABS_END
Definition: raytrace.h:1850
#define RT_PART_NUGRID
Definition: raytrace.h:1836
point_t st_min
min X, Y, Z of bounding RPP
Definition: raytrace.h:437
size_t npieces
number of pieces in pieces[] array
Definition: raytrace.h:1406
int rti_ncut_by_type[CUT_MAXIMUM+1]
number of cuts by type
Definition: raytrace.h:1799
union cutter * cn_r
val >= point
Definition: raytrace.h:689
void rt_pr_cut_info(const struct rt_i *rtip, const char *str)
Definition: cut.c:2060
const struct rt_functab OBJ[]
Definition: table.c:159
HIDDEN int rt_projXmax_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:181
#define RT_VISIT_ALL_SOLTABS_START(_s, _rti)
Definition: raytrace.h:1845
axis
Definition: color.c:48
int rti_cut_maxdepth
max depth of cut tree
Definition: raytrace.h:1801
int rt_split_mostly_empty_cells(struct rt_i *rtip, union cutter *cutp)
Definition: cut.c:645
size_t nsolids
total # of solids participating
Definition: raytrace.h:1783
point_t mdl_max
max corner of model bounding RPP
Definition: raytrace.h:1770
struct bu_list l2
links, headed by st_dp->d_use_hd
Definition: raytrace.h:427
size_t rti_cutlen
goal for # solids per boxnode
Definition: raytrace.h:1813
#define RT_CK_SOLTAB(_p)
Definition: raytrace.h:453
#define RT_NU_GFACTOR_DEFAULT
see rt_cut_it() for a description of this
Definition: raytrace.h:1826
void rt_cut_optimize_parallel(int cpu, void *arg)
Definition: cut.c:133
void rt_cut_it(register struct rt_i *rtip, int ncpu)
Definition: cut.c:756
fastf_t hg_max
Definition: hist.h:56
int cut_type
Definition: raytrace.h:723
int bn_type
Definition: raytrace.h:693
struct bu_ptbl rti_busy_cutter_nodes
List of "cutter" mallocs.
Definition: raytrace.h:1796
union cutter * cn_l
val < point
Definition: raytrace.h:688
void bu_hist_free(struct bu_hist *histp)
Definition: hist.c:32
void rt_cut_extend(register union cutter *cutp, struct soltab *stp, const struct rt_i *rtip)
Definition: cut.c:915
HIDDEN void rt_ct_free(struct rt_i *rtip, union cutter *cutp)
int bu_malloc_len_roundup(int nbytes)
Definition: color.c:51
int rti_cut_totobj
objs in all bins, total
Definition: raytrace.h:1800
struct boxnode bn
Definition: raytrace.h:726
#define RT_PIECELIST_MAGIC
Definition: magic.h:163
struct nugridnode nugn
Definition: raytrace.h:727
#define RT_SEM_MODEL
Definition: raytrace.h:1733
HIDDEN int rt_ct_populate_box(union cutter *outp, const union cutter *inp, struct rt_i *rtip)
Definition: cut.c:1130
#define CUTTER_NULL
Definition: raytrace.h:731
fastf_t nu_width
voxel size (end - start)
Definition: raytrace.h:707
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
int cn_axis
0, 1, 2 = cut along X, Y, Z
Definition: raytrace.h:686
off_t end
Definition: ptbl.h:64
union cutter * rti_CutFree
cut Freelist
Definition: raytrace.h:1795
#define AXIS(depth)
Definition: cut.c:65
int nu_type
Definition: raytrace.h:711
void rt_pr_cut(const union cutter *cutp, int lvl)
Definition: cut.c:1703
struct soltab * stp
ref back to solid
Definition: raytrace.h:1408
int nu_cells_per_axis[3]
number of slabs
Definition: raytrace.h:713
int st_id
Solid ident.
Definition: raytrace.h:431
void pdv_3box(register FILE *plotfp, const fastf_t *a, const fastf_t *b)
Definition: plot3.c:688
HIDDEN struct cmp_pair pairs[]
uint32_t magic
Definition: raytrace.h:1405
long * hg_bins
Definition: hist.h:60
#define CUT_BOXNODE
Definition: raytrace.h:719
HIDDEN void rt_plot_cut(FILE *fp, struct rt_i *rtip, union cutter *cutp, int lvl)
HIDDEN int rt_projZmax_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:209
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
HIDDEN int rt_ct_box(struct rt_i *rtip, union cutter *cutp, int axis, double where, int force)
union cutter * nu_grid
3-D array of boxnodes
Definition: raytrace.h:715
void pd_3line(register FILE *plotfp, double px1, double py1, double pz1, double px2, double py2, double pz2)
Definition: plot3.c:662
point_t rti_pmax
for plotting, max RPP
Definition: raytrace.h:1772
Definition: color.c:50
fastf_t cn_point
cut through axis==point
Definition: raytrace.h:687
long st_npieces
pieces used by this solid
Definition: raytrace.h:444
int(* cmp_min)(const void *, const void *, void *)
Definition: cut.c:216