BRL-CAD
db_tree.c
Go to the documentation of this file.
1 /* D B _ T R E E . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1988-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 dbio */
21 /** @{ */
22 /** @file librt/db_tree.c
23  *
24  * Includes parallel tree walker routine. Also includes routines to
25  * return a matrix given a name or path.
26  *
27  */
28 
29 #include "common.h"
30 
31 #include <math.h>
32 #include <string.h>
33 #include <ctype.h>
34 #include "bio.h"
35 
36 
37 #include "bu/parallel.h"
38 #include "vmath.h"
39 #include "bn.h"
40 #include "nmg.h"
41 #include "raytrace.h"
42 #include "./librt_private.h"
43 
44 
45 void
46 db_dup_db_tree_state(struct db_tree_state *otsp, const struct db_tree_state *itsp)
47 {
48  size_t shader_len = 0;
49  size_t i;
50 
51  RT_CK_DBTS(itsp);
52  RT_CK_DBI(itsp->ts_dbip);
53 
54  *otsp = *itsp; /* struct copy */
55 
56  if (itsp->ts_mater.ma_shader)
57  shader_len = strlen(itsp->ts_mater.ma_shader);
58  if (shader_len) {
59  otsp->ts_mater.ma_shader = (char *)bu_malloc(shader_len+1, "db_new_combined_tree_state: ma_shader");
60  bu_strlcpy(otsp->ts_mater.ma_shader, itsp->ts_mater.ma_shader, shader_len+1);
61  } else
62  otsp->ts_mater.ma_shader = (char *)NULL;
63 
64  if (itsp->ts_attrs.count > 0) {
65  bu_avs_init(&otsp->ts_attrs, itsp->ts_attrs.count, "otsp->ts_attrs");
66  for (i = 0; i<(size_t)itsp->ts_attrs.count; i++)
67  bu_avs_add(&otsp->ts_attrs, itsp->ts_attrs.avp[i].name,
68  itsp->ts_attrs.avp[i].value);
69  } else {
71  }
72 }
73 
74 
75 void
77 {
78  RT_CK_DBTS(tsp);
79  RT_CK_DBI(tsp->ts_dbip);
80  if (tsp->ts_mater.ma_shader) {
81  bu_free(tsp->ts_mater.ma_shader, "db_free_combined_tree_state: ma_shader");
82  tsp->ts_mater.ma_shader = (char *)NULL; /* sanity */
83  }
84  if (tsp->ts_attrs.max > 0) {
85  bu_avs_free(&tsp->ts_attrs);
86  tsp->ts_attrs.avp = (struct bu_attribute_value_pair *)NULL;
87  }
88  tsp->ts_dbip = (struct db_i *)NULL; /* sanity */
89 }
90 
91 
92 void
93 db_init_db_tree_state(struct db_tree_state *tsp, struct db_i *dbip, struct resource *resp)
94 {
95  RT_CK_DBI(dbip);
96  if (!resp) {
97  resp = &rt_uniresource;
98  }
99  RT_CK_RESOURCE(resp);
100 
101  memset((char *)tsp, 0, sizeof(*tsp));
102  tsp->magic = RT_DBTS_MAGIC;
103  tsp->ts_dbip = dbip;
104  tsp->ts_resp = resp;
106  MAT_IDN(tsp->ts_mat); /* XXX should use null pointer convention! */
107 }
108 
109 
110 struct combined_tree_state *
111 db_new_combined_tree_state(const struct db_tree_state *tsp, const struct db_full_path *pathp)
112 {
113  struct combined_tree_state *new_ctsp;
114 
115  RT_CK_DBTS(tsp);
116  RT_CK_FULL_PATH(pathp);
117  RT_CK_DBI(tsp->ts_dbip);
118 
119  BU_ALLOC(new_ctsp, struct combined_tree_state);
120  new_ctsp->magic = RT_CTS_MAGIC;
121  db_dup_db_tree_state(&(new_ctsp->cts_s), tsp);
122  db_full_path_init(&(new_ctsp->cts_p));
123  db_dup_full_path(&(new_ctsp->cts_p), pathp);
124  return new_ctsp;
125 }
126 
127 
128 struct combined_tree_state *
130 {
131  struct combined_tree_state *new_ctsp;
132 
133  RT_CK_CTS(old_ctsp);
134  BU_ALLOC(new_ctsp, struct combined_tree_state);
135  new_ctsp->magic = RT_CTS_MAGIC;
136  db_dup_db_tree_state(&(new_ctsp->cts_s), &(old_ctsp->cts_s));
137  db_full_path_init(&(new_ctsp->cts_p));
138  db_dup_full_path(&(new_ctsp->cts_p), &(old_ctsp->cts_p));
139  return new_ctsp;
140 }
141 
142 
143 void
145 {
146  RT_CK_CTS(ctsp);
147  db_free_full_path(&(ctsp->cts_p));
148  db_free_db_tree_state(&(ctsp->cts_s));
149  memset((char *)ctsp, 0, sizeof(*ctsp)); /* sanity */
150  bu_free((char *)ctsp, "combined_tree_state");
151 }
152 
153 
154 void
155 db_pr_tree_state(const struct db_tree_state *tsp)
156 {
157  size_t i;
158 
159  RT_CK_DBTS(tsp);
160 
161  bu_log("db_pr_tree_state(%p):\n", (void *)tsp);
162  bu_log(" ts_dbip=%p\n", (void *)tsp->ts_dbip);
163  bu_printb(" ts_sofar", tsp->ts_sofar, "\020\3REGION\2INTER\1MINUS");
164  bu_log("\n");
165  bu_log(" ts_regionid=%d\n", tsp->ts_regionid);
166  bu_log(" ts_aircode=%d\n", tsp->ts_aircode);
167  bu_log(" ts_gmater=%d\n", tsp->ts_gmater);
168  bu_log(" ts_los=%d\n", tsp->ts_los);
169  if (tsp->ts_mater.ma_color_valid) {
170  bu_log(" ts_mater.ma_color=%g, %g, %g\n",
171  tsp->ts_mater.ma_color[0],
172  tsp->ts_mater.ma_color[1],
173  tsp->ts_mater.ma_color[2]);
174  }
175  bu_log(" ts_mater.ma_temperature=%g K\n", tsp->ts_mater.ma_temperature);
176  bu_log(" ts_mater.ma_shader=%s\n", tsp->ts_mater.ma_shader ? tsp->ts_mater.ma_shader : "");
177  for (i = 0; i < (size_t)tsp->ts_attrs.count; i++) {
178  bu_log("\t%s = %s\n", tsp->ts_attrs.avp[i].name, tsp->ts_attrs.avp[i].value);
179  }
180  bn_mat_print("ts_mat", tsp->ts_mat);
181  bu_log(" ts_resp=%p\n", (void *)tsp->ts_resp);
182 }
183 
184 
185 void
187 {
188  char *str;
189 
190  RT_CK_CTS(ctsp);
191  bu_log("db_pr_combined_tree_state(%p):\n", (void *)ctsp);
192  db_pr_tree_state(&(ctsp->cts_s));
193  str = db_path_to_string(&(ctsp->cts_p));
194  bu_log(" path='%s'\n", str);
195  bu_free(str, "path string");
196 }
197 
198 
199 int
200 db_apply_state_from_comb(struct db_tree_state *tsp, const struct db_full_path *pathp, const struct rt_comb_internal *comb)
201 {
202  RT_CK_DBTS(tsp);
203  RT_CK_COMB(comb);
204 
205  if (comb->rgb_valid == 1) {
206  if (tsp->ts_sofar & TS_SOFAR_REGION) {
207  if ((tsp->ts_sofar&(TS_SOFAR_MINUS|TS_SOFAR_INTER)) == 0) {
208  /* This combination is within a region */
209  char *sofar = db_path_to_string(pathp);
210 
211  bu_log("db_apply_state_from_comb(): WARNING: color override in combination within region '%s', ignored\n",
212  sofar);
213  bu_free(sofar, "path string");
214  }
215  /* Just quietly ignore it -- it's being subtracted off */
216  } else if (tsp->ts_mater.ma_cinherit == 0) {
217  /* DB_INH_LOWER was set -- lower nodes in tree override */
218  tsp->ts_mater.ma_color_valid = 1;
219  tsp->ts_mater.ma_color[0] =
220  (((float)(comb->rgb[0])) / 255.0);
221  tsp->ts_mater.ma_color[1] =
222  (((float)(comb->rgb[1])) / 255.0);
223  tsp->ts_mater.ma_color[2] =
224  (((float)(comb->rgb[2])) / 255.0);
225  /* Track further inheritance as specified by this combination */
226  tsp->ts_mater.ma_cinherit = comb->inherit;
227  }
228  }
229  if (comb->temperature > 0) {
230  if (tsp->ts_sofar & TS_SOFAR_REGION) {
231  if ((tsp->ts_sofar&(TS_SOFAR_MINUS|TS_SOFAR_INTER)) == 0) {
232  /* This combination is within a region */
233  char *sofar = db_path_to_string(pathp);
234 
235  bu_log("db_apply_state_from_comb(): WARNING: temperature in combination below region '%s', ignored\n",
236  sofar);
237  bu_free(sofar, "path string");
238  }
239  /* Just quietly ignore it -- it's being subtracted off */
240  } else if (tsp->ts_mater.ma_minherit == 0) {
241  /* DB_INH_LOWER -- lower nodes in tree override */
242  tsp->ts_mater.ma_temperature = comb->temperature;
243  }
244  }
245  if (bu_vls_strlen(&comb->shader) > 0) {
246  if (tsp->ts_sofar & TS_SOFAR_REGION) {
247  if ((tsp->ts_sofar&(TS_SOFAR_MINUS|TS_SOFAR_INTER)) == 0) {
248  /* This combination is within a region */
249  char *sofar = db_path_to_string(pathp);
250 
251  bu_log("db_apply_state_from_comb(): WARNING: material property spec in combination below region '%s', ignored\n",
252  sofar);
253  bu_free(sofar, "path string");
254  }
255  /* Just quietly ignore it -- it's being subtracted off */
256  } else if (tsp->ts_mater.ma_minherit == 0) {
257  struct bu_vls tmp_vls = BU_VLS_INIT_ZERO;
258 
259  /* DB_INH_LOWER -- lower nodes in tree override */
260  if (tsp->ts_mater.ma_shader)
261  bu_free((void *)tsp->ts_mater.ma_shader, "ma_shader");
262 
263  if (bu_shader_to_key_eq(bu_vls_addr(&comb->shader), &tmp_vls)) {
264  char *sofar = db_path_to_string(pathp);
265 
266  bu_log("db_apply_state_from_comb: Warning: bad shader in %s (ignored):\n", sofar);
267  bu_vls_free(&tmp_vls);
268  bu_free(sofar, "path string");
269  tsp->ts_mater.ma_shader = (char *)NULL;
270  } else {
271  tsp->ts_mater.ma_shader = bu_vls_strdup(&tmp_vls);
272  bu_vls_free(&tmp_vls);
273  }
274  tsp->ts_mater.ma_minherit = comb->inherit;
275  }
276  }
277 
278  /* Handle combinations which are the top of a "region" */
279  if (comb->region_flag) {
280  if (tsp->ts_sofar & TS_SOFAR_REGION) {
281  if ((tsp->ts_sofar&(TS_SOFAR_MINUS|TS_SOFAR_INTER)) == 0) {
282  char *sofar = db_path_to_string(pathp);
283  bu_log("Warning: region unioned into region at '%s', lower region info ignored\n",
284  sofar);
285  bu_free(sofar, "path string");
286  }
287  /* Go on as if it was not a region */
288  } else {
289  /* This starts a new region */
290  tsp->ts_sofar |= TS_SOFAR_REGION;
291  tsp->ts_regionid = comb->region_id;
292  tsp->ts_is_fastgen = comb->is_fastgen;
293  tsp->ts_aircode = comb->aircode;
294  tsp->ts_gmater = comb->GIFTmater;
295  tsp->ts_los = comb->los;
296  return 1; /* Success, this starts new region */
297  }
298  }
299  return 0; /* Success */
300 }
301 
302 
303 int
304 db_apply_state_from_memb(struct db_tree_state *tsp, struct db_full_path *pathp, const union tree *tp)
305 {
306  struct directory *mdp;
307  mat_t xmat;
308  mat_t old_xlate;
309 
310  RT_CK_DBTS(tsp);
311  RT_CK_FULL_PATH(pathp);
312  RT_CK_TREE(tp);
313 
314  if ((mdp = db_lookup(tsp->ts_dbip, tp->tr_l.tl_name, LOOKUP_QUIET)) == RT_DIR_NULL) {
315  char *sofar = db_path_to_string(pathp);
316  bu_log("db_lookup(%s) failed in %s\n", tp->tr_l.tl_name, sofar);
317  bu_free(sofar, "path string");
318  return -1;
319  }
320 
321  db_add_node_to_full_path(pathp, mdp);
322 
323  MAT_COPY(old_xlate, tsp->ts_mat);
324  if (tp->tr_l.tl_mat) {
325  MAT_COPY(xmat, tp->tr_l.tl_mat);
326  } else {
327  MAT_IDN(xmat);
328  }
329 
330  /* If the owning region it above this node in the tree, it is not
331  * possible to animation region-material properties lower down in
332  * the arc. So note by sending a NULL pointer.
333  */
334  db_apply_anims(pathp, mdp, old_xlate, xmat,
335  (tsp->ts_sofar & TS_SOFAR_REGION) ?
336  (struct mater_info *)NULL :
337  &tsp->ts_mater);
338 
339  bn_mat_mul(tsp->ts_mat, old_xlate, xmat);
340 
341  return 0; /* Success */
342 }
343 
344 
345 int
347  struct db_tree_state *tsp,
348  struct db_full_path *pathp,
349  const char *cp,
350  int sofar,
351  const union tree *tp)
352 {
353  int ret;
354 
355  RT_CK_DBTS(tsp);
356  RT_CHECK_DBI(tsp->ts_dbip);
357  RT_CK_FULL_PATH(pathp);
358  RT_CK_TREE(tp);
359 
360  switch (tp->tr_op) {
361 
362  case OP_DB_LEAF:
363  if (!BU_STR_EQUAL(cp, tp->tr_l.tl_name))
364  return 0; /* NO-OP */
365  tsp->ts_sofar |= sofar;
366  if (db_apply_state_from_memb(tsp, pathp, tp) < 0)
367  return -1; /* FAIL */
368  return 1; /* success */
369 
370  case OP_UNION:
371  case OP_INTERSECT:
372  case OP_SUBTRACT:
373  case OP_XOR:
374  ret = db_apply_state_from_one_member(tsp, pathp, cp, sofar,
375  tp->tr_b.tb_left);
376  if (ret != 0) return ret;
377  if (tp->tr_op == OP_SUBTRACT)
378  sofar |= TS_SOFAR_MINUS;
379  else if (tp->tr_op == OP_INTERSECT)
380  sofar |= TS_SOFAR_INTER;
381  return db_apply_state_from_one_member(tsp, pathp, cp, sofar,
382  tp->tr_b.tb_right);
383 
384  default:
385  bu_log("db_apply_state_from_one_member: bad op %d\n", tp->tr_op);
386  bu_bomb("db_apply_state_from_one_member\n");
387  }
388  return -1;
389 }
390 
391 
392 union tree *
393 db_find_named_leaf(union tree *tp, const char *cp)
394 {
395  union tree *ret;
396 
397  RT_CK_TREE(tp);
398 
399  switch (tp->tr_op) {
400 
401  case OP_DB_LEAF:
402  if (!BU_STR_EQUAL(cp, tp->tr_l.tl_name))
403  return TREE_NULL;
404  return tp;
405 
406  case OP_UNION:
407  case OP_INTERSECT:
408  case OP_SUBTRACT:
409  case OP_XOR:
410  ret = db_find_named_leaf(tp->tr_b.tb_left, cp);
411  if (ret != TREE_NULL) return ret;
412  return db_find_named_leaf(tp->tr_b.tb_right, cp);
413 
414  default:
415  bu_log("db_find_named_leaf: bad op %d\n", tp->tr_op);
416  bu_bomb("db_find_named_leaf\n");
417  }
418  return TREE_NULL;
419 }
420 
421 
422 union tree *
423 db_find_named_leafs_parent(int *side, union tree *tp, const char *cp)
424 {
425  union tree *ret;
426 
427  RT_CK_TREE(tp);
428 
429  switch (tp->tr_op) {
430 
431  case OP_DB_LEAF:
432  /* Always return NULL -- we are seeking parent, not leaf */
433  return TREE_NULL;
434 
435  case OP_UNION:
436  case OP_INTERSECT:
437  case OP_SUBTRACT:
438  case OP_XOR:
439  if (tp->tr_b.tb_left->tr_op == OP_DB_LEAF) {
440  if (BU_STR_EQUAL(cp, tp->tr_b.tb_left->tr_l.tl_name)) {
441  *side = 1;
442  return tp;
443  }
444  }
445  if (tp->tr_b.tb_right->tr_op == OP_DB_LEAF) {
446  if (BU_STR_EQUAL(cp, tp->tr_b.tb_right->tr_l.tl_name)) {
447  *side = 2;
448  return tp;
449  }
450  }
451 
452  /* If target not on immediate children, descend down. */
453  ret = db_find_named_leafs_parent(side, tp->tr_b.tb_left, cp);
454  if (ret != TREE_NULL) return ret;
455  return db_find_named_leafs_parent(side, tp->tr_b.tb_right, cp);
456 
457  default:
458  bu_log("db_find_named_leafs_parent: bad op %d\n", tp->tr_op);
459  bu_bomb("db_find_named_leafs_parent\n");
460  }
461  return TREE_NULL;
462 }
463 
464 
465 void
466 db_tree_del_lhs(union tree *tp, struct resource *resp)
467 {
468  union tree *subtree;
469 
470  RT_CK_TREE(tp);
471  if (!resp) {
472  resp = &rt_uniresource;
473  }
474  RT_CK_RESOURCE(resp);
475 
476  switch (tp->tr_op) {
477 
478  default:
479  bu_bomb("db_tree_del_lhs() called with leaf node as parameter\n");
480 
481  case OP_UNION:
482  case OP_INTERSECT:
483  case OP_SUBTRACT:
484  case OP_XOR:
485  switch (tp->tr_b.tb_left->tr_op) {
486  case OP_NOP:
487  case OP_SOLID:
488  case OP_REGION:
489  case OP_NMG_TESS:
490  case OP_DB_LEAF:
491  /* lhs is indeed a leaf node */
492  db_free_tree(tp->tr_b.tb_left, resp);
493  tp->tr_b.tb_left = TREE_NULL; /* sanity */
494  subtree = tp->tr_b.tb_right;
495  /*
496  * Since we don't know what node has the
497  * downpointer to 'tp', replicate 'subtree' data
498  * in 'tp' node, then release memory of 'subtree'
499  * node (but not the actual subtree).
500  */
501  *tp = *subtree; /* struct copy */
502  RT_FREE_TREE(subtree, resp);
503  return;
504  default:
505  bu_bomb("db_tree_del_lhs() lhs is not a leaf node\n");
506  }
507  }
508 }
509 
510 
511 void
512 db_tree_del_rhs(union tree *tp, struct resource *resp)
513 {
514  union tree *subtree;
515 
516  RT_CK_TREE(tp);
517  if (!resp) {
518  resp = &rt_uniresource;
519  }
520  RT_CK_RESOURCE(resp);
521 
522  switch (tp->tr_op) {
523 
524  default:
525  bu_bomb("db_tree_del_rhs() called with leaf node as parameter\n");
526 
527  case OP_UNION:
528  case OP_INTERSECT:
529  case OP_SUBTRACT:
530  case OP_XOR:
531  switch (tp->tr_b.tb_right->tr_op) {
532  case OP_NOP:
533  case OP_SOLID:
534  case OP_REGION:
535  case OP_NMG_TESS:
536  case OP_DB_LEAF:
537  /* rhs is indeed a leaf node */
538  db_free_tree(tp->tr_b.tb_right, resp);
539  tp->tr_b.tb_right = TREE_NULL; /* sanity */
540  subtree = tp->tr_b.tb_left;
541  /*
542  * Since we don't know what node has the
543  * downpointer to 'tp', replicate 'subtree' data
544  * in 'tp' node, then release memory of 'subtree'
545  * node (but not the actual subtree).
546  */
547  *tp = *subtree; /* struct copy */
548  RT_FREE_TREE(subtree, resp);
549  return;
550  default:
551  bu_bomb("db_tree_del_rhs() rhs is not a leaf node\n");
552  }
553  }
554 }
555 
556 
557 int
558 db_tree_del_dbleaf(union tree **tp, const char *cp, struct resource *resp, int nflag)
559 {
560  union tree *parent;
561  int side = 0;
562 
563  if (*tp == TREE_NULL) return -1;
564 
565  RT_CK_TREE(*tp);
566  if (!resp) {
567  resp = &rt_uniresource;
568  }
569  RT_CK_RESOURCE(resp);
570 
571  if ((parent = db_find_named_leafs_parent(&side, *tp, cp)) == TREE_NULL) {
572  /* Perhaps the root of the tree is the named leaf? */
573  if ((*tp)->tr_op == OP_DB_LEAF &&
574  BU_STR_EQUAL(cp, (*tp)->tr_l.tl_name)) {
575  if (nflag)
576  return 0;
577 
578  db_free_tree(*tp, resp);
579  *tp = TREE_NULL;
580  return 0;
581  }
582  return -2;
583  }
584 
585  switch (side) {
586  case 1:
587  if (nflag)
588  return 0;
589 
590  db_tree_del_lhs(parent, resp);
591  (void)db_tree_del_dbleaf(tp, cp, resp, nflag); /* recurse for extras */
592  return 0;
593  case 2:
594  if (nflag)
595  return 0;
596 
597  db_tree_del_rhs(parent, resp);
598  (void)db_tree_del_dbleaf(tp, cp, resp, nflag); /* recurse for extras */
599  return 0;
600  }
601  bu_log("db_tree_del_dbleaf() unknown side=%d?\n", side);
602  return -3;
603 }
604 
605 
606 void
607 db_tree_mul_dbleaf(union tree *tp, const mat_t mat)
608 {
609  mat_t temp;
610 
611  RT_CK_TREE(tp);
612 
613  switch (tp->tr_op) {
614 
615  case OP_DB_LEAF:
616  if (tp->tr_l.tl_mat == NULL) {
617  tp->tr_l.tl_mat = bn_mat_dup(mat);
618  return;
619  }
620  bn_mat_mul(temp, mat, tp->tr_l.tl_mat);
621  MAT_COPY(tp->tr_l.tl_mat, temp);
622  break;
623 
624  case OP_UNION:
625  case OP_INTERSECT:
626  case OP_SUBTRACT:
627  case OP_XOR:
628  db_tree_mul_dbleaf(tp->tr_b.tb_left, mat);
629  db_tree_mul_dbleaf(tp->tr_b.tb_right, mat);
630  break;
631 
632  default:
633  bu_log("db_tree_mul_dbleaf: bad op %d\n", tp->tr_op);
634  bu_bomb("db_tree_mul_dbleaf\n");
635  }
636 }
637 
638 
639 void
641  struct db_i *dbip,
642  struct rt_comb_internal *comb,
643  union tree *comb_tree,
644  void (*leaf_func)(struct db_i *, struct rt_comb_internal *, union tree *,
645  void *, void *, void *, void *),
646  void *user_ptr1,
647  void *user_ptr2,
648  void *user_ptr3,
649  void *user_ptr4)
650 {
651  void (*lfunc)(struct db_i *, struct rt_comb_internal *, union tree *,
652  void *, void *, void *, void *);
653 
654  RT_CK_DBI(dbip);
655 
656  if (!comb_tree)
657  return;
658 
659  RT_CK_TREE(comb_tree);
660 
661  lfunc = (void (*)(struct db_i *, struct rt_comb_internal *, union tree *, void *, void *, void *, void *))leaf_func;
662  switch (comb_tree->tr_op) {
663  case OP_DB_LEAF:
664  lfunc(dbip, comb, comb_tree, user_ptr1, user_ptr2, user_ptr3, user_ptr4);
665  break;
666  case OP_UNION:
667  case OP_INTERSECT:
668  case OP_SUBTRACT:
669  case OP_XOR:
670  db_tree_funcleaf(dbip, comb, comb_tree->tr_b.tb_left, leaf_func, user_ptr1, user_ptr2, user_ptr3, user_ptr4);
671  db_tree_funcleaf(dbip, comb, comb_tree->tr_b.tb_right, leaf_func, user_ptr1, user_ptr2, user_ptr3, user_ptr4);
672  break;
673  default:
674  bu_log("db_tree_funcleaf: bad op %d\n", comb_tree->tr_op);
675  bu_bomb("db_tree_funcleaf: bad op\n");
676  break;
677  }
678 }
679 
680 
681 int
683  struct db_tree_state *tsp,
684  struct db_full_path *total_path,
685  const struct db_full_path *new_path,
686  int noisy,
687  long depth) /* # arcs in new_path to use */
688 {
689  struct rt_db_internal intern;
690  struct rt_comb_internal *comb;
691  struct directory *comb_dp; /* combination's dp */
692  struct directory *dp; /* element's dp */
693  size_t j;
694 
695  RT_CK_DBTS(tsp);
696  RT_CHECK_DBI(tsp->ts_dbip);
697  RT_CK_FULL_PATH(total_path);
698  RT_CK_FULL_PATH(new_path);
699  RT_CK_RESOURCE(tsp->ts_resp);
700 
702  char *sofar = db_path_to_string(total_path);
703  char *toofar = db_path_to_string(new_path);
704  bu_log("db_follow_path() total_path='%s', tsp=%p, new_path='%s', noisy=%d, depth=%ld\n",
705  sofar, (void *)tsp, toofar, noisy, depth);
706  bu_free(sofar, "path string");
707  bu_free(toofar, "path string");
708  }
709 
710  if (depth < 0) {
711  depth = new_path->fp_len-1 + depth;
712  if (depth < 0) bu_bomb("db_follow_path() depth exceeded provided path\n");
713  } else if ((size_t)depth >= new_path->fp_len) {
714  depth = new_path->fp_len-1;
715  } else if (depth == 0) {
716  /* depth of zero means "do it all". */
717  depth = new_path->fp_len-1;
718  }
719 
720  j = 0;
721 
722  /* Get the first combination */
723  if (total_path->fp_len > 0) {
724  /* Some path has already been processed */
725  comb_dp = DB_FULL_PATH_CUR_DIR(total_path);
726  } else {
727  /* No prior path. Process any animations located at the
728  * root.
729  */
730  comb_dp = RT_DIR_NULL;
731  dp = new_path->fp_names[0];
732  RT_CK_DIR(dp);
733 
734  if (tsp->ts_dbip->dbi_anroot) {
735  struct animate *anp;
736  mat_t old_xlate, xmat;
737 
738  for (anp=tsp->ts_dbip->dbi_anroot; anp != ANIM_NULL; anp = anp->an_forw) {
739  RT_CK_ANIMATE(anp);
740  if (dp != anp->an_path.fp_names[0])
741  continue;
742  MAT_COPY(old_xlate, tsp->ts_mat);
743  MAT_IDN(xmat);
744  db_do_anim(anp, old_xlate, xmat, &(tsp->ts_mater));
745  bn_mat_mul(tsp->ts_mat, old_xlate, xmat);
746  }
747  }
748 
749  /* Put first element on output path, either way */
750  db_add_node_to_full_path(total_path, dp);
751 
752  if ((dp->d_flags & RT_DIR_COMB) == 0) goto is_leaf;
753 
754  /* Advance to next path element */
755  j = 1;
756  comb_dp = dp;
757  }
758  /*
759  * Process two things at once: the combination at [j], and its
760  * member at [j+1].
761  */
762  do {
763  /* j == depth is the last one, presumably a leaf */
764  if (j > (size_t)depth) break;
765  dp = new_path->fp_names[j];
766  RT_CK_DIR(dp);
767 
768  if (!comb_dp) {
769  goto fail;
770  }
771 
772  if ((comb_dp->d_flags & RT_DIR_COMB) == 0) {
773  bu_log("db_follow_path() %s isn't combination\n", comb_dp->d_namep);
774  goto fail;
775  }
776 
777  /* At this point, comb_db is the comb, dp is the member */
778  if (RT_G_DEBUG&DEBUG_TREEWALK) {
779  bu_log("db_follow_path() at %s/%s\n", comb_dp->d_namep, dp->d_namep);
780  }
781 
782  /* Load the combination object into memory */
783  if (rt_db_get_internal(&intern, comb_dp, tsp->ts_dbip, NULL, tsp->ts_resp) < 0)
784  goto fail;
785  comb = (struct rt_comb_internal *)intern.idb_ptr;
786  RT_CK_COMB(comb);
787  if (db_apply_state_from_comb(tsp, total_path, comb) < 0)
788  goto fail;
789 
790  /* Crawl tree searching for specified leaf */
791  if (db_apply_state_from_one_member(tsp, total_path, dp->d_namep, 0, comb->tree) <= 0) {
792  bu_log("db_follow_path() ERROR: unable to apply member %s state\n", dp->d_namep);
793  goto fail;
794  }
795  /* Found it, state has been applied, sofar applied, member's
796  * directory entry pushed onto total_path
797  */
798  rt_db_free_internal(&intern);
799 
800  /* If member is a leaf, handle leaf processing too. */
801  if ((dp->d_flags & RT_DIR_COMB) == 0) {
802  is_leaf:
803  /* Object is a leaf */
804  if (j == new_path->fp_len-1) {
805  /* No more path was given, all is well */
806  goto out;
807  }
808  /* Additional path was given, this is wrong */
809  if (noisy) {
810  char *sofar = db_path_to_string(total_path);
811  char *toofar = db_path_to_string(new_path);
812  bu_log("db_follow_path() ERROR: path ended in leaf at '%s', additional path specified '%s'\n",
813  sofar, toofar);
814  bu_free(sofar, "path string");
815  bu_free(toofar, "path string");
816  }
817  goto fail;
818  }
819 
820  /* Advance to next path element */
821  j++;
822  comb_dp = dp;
823  } while (j <= (size_t)depth);
824 
825 out:
826  if (RT_G_DEBUG&DEBUG_TREEWALK) {
827  char *sofar = db_path_to_string(total_path);
828  bu_log("db_follow_path() returns total_path='%s'\n",
829  sofar);
830  bu_free(sofar, "path string");
831  }
832  return 0; /* SUCCESS */
833 fail:
834  return -1; /* FAIL */
835 }
836 
837 
838 int
839 db_follow_path_for_state(struct db_tree_state *tsp, struct db_full_path *total_path, const char *orig_str, int noisy)
840 {
841  struct db_full_path new_path;
842  int ret;
843 
844  RT_CK_DBTS(tsp);
845 
846  if (*orig_str == '\0') {
847  return 0; /* Null string */
848  }
849 
850  db_full_path_init(&new_path);
851 
852  if (db_string_to_path(&new_path, tsp->ts_dbip, orig_str) < 0) {
853  db_free_full_path(&new_path);
854  return -1;
855  }
856 
857  if (new_path.fp_len <= 0) {
858  db_free_full_path(&new_path);
859  return 0; /* Null string */
860  }
861 
862  ret = db_follow_path(tsp, total_path, &new_path, noisy, 0);
863  db_free_full_path(&new_path);
864 
865  return ret;
866 }
867 
868 
869 /**
870  * Helper routine for db_recurse()
871  */
872 HIDDEN void
873 _db_recurse_subtree(union tree *tp, struct db_tree_state *msp, struct db_full_path *pathp, struct combined_tree_state **region_start_statepp, void *client_data)
874 {
875  struct db_tree_state memb_state;
876  union tree *subtree;
877 
878  RT_CK_TREE(tp);
879  RT_CK_DBTS(msp);
880  RT_CK_RESOURCE(msp->ts_resp);
881  db_dup_db_tree_state(&memb_state, msp);
882 
883  switch (tp->tr_op) {
884 
885  case OP_DB_LEAF:
886  if (db_apply_state_from_memb(&memb_state, pathp, tp) < 0) {
887  /* Lookup of this leaf failed, NOP it out. */
888  if (tp->tr_l.tl_mat) {
889  bu_free((char *)tp->tr_l.tl_mat, "tl_mat");
890  tp->tr_l.tl_mat = NULL;
891  }
892  bu_free(tp->tr_l.tl_name, "tl_name");
893  tp->tr_l.tl_name = NULL;
894  tp->tr_op = OP_NOP;
895  goto out;
896  }
897 
898  /* protect against cyclic geometry */
899  if (cyclic_path(pathp, tp->tr_l.tl_name)) {
900  int depth = pathp->fp_len;
901 
902  bu_log("Detected cyclic reference of %s\nPath stack is:\n", tp->tr_l.tl_name);
903  while (--depth >=0) {
904  bu_log("\tPath depth %d is %s\n", depth, pathp->fp_names[depth]->d_namep);
905  }
906  bu_log("WARNING: skipping the cyclic reference lookup\n");
907 
908  /* Lookup of this leaf resulted in a cyclic reference,
909  * NOP it out.
910  */
911  if (tp->tr_l.tl_mat) {
912  bu_free((char *)tp->tr_l.tl_mat, "tl_mat");
913  tp->tr_l.tl_mat = NULL;
914  }
915  bu_free(tp->tr_l.tl_name, "tl_name");
916  tp->tr_l.tl_name = NULL;
917  tp->tr_op = OP_NOP;
918  goto out;
919  }
920 
921  /* Recursive call */
922  if ((subtree = db_recurse(&memb_state, pathp, region_start_statepp, client_data)) != TREE_NULL) {
923  union tree *tmp;
924 
925  /* graft subtree on in place of 'tp' leaf node */
926  /* exchange what subtree and tp point at */
927  RT_GET_TREE(tmp, msp->ts_resp);
928  RT_CK_TREE(subtree);
929  *tmp = *tp; /* struct copy */
930  *tp = *subtree; /* struct copy */
931  RT_FREE_TREE(subtree, msp->ts_resp);
932 
933  db_free_tree(tmp, msp->ts_resp);
934  RT_CK_TREE(tp);
935  } else {
936  /* Processing of this leaf failed, NOP it out. */
937  if (tp->tr_l.tl_mat) {
938  bu_free((char *)tp->tr_l.tl_mat, "tl_mat");
939  tp->tr_l.tl_mat = NULL;
940  }
941  bu_free(tp->tr_l.tl_name, "tl_name");
942  tp->tr_l.tl_name = NULL;
943  tp->tr_op = OP_NOP;
944  }
945  DB_FULL_PATH_POP(pathp);
946  break;
947 
948  case OP_UNION:
949  case OP_INTERSECT:
950  case OP_SUBTRACT:
951  case OP_XOR:
952  _db_recurse_subtree(tp->tr_b.tb_left, &memb_state, pathp, region_start_statepp, client_data);
953  if (tp->tr_op == OP_SUBTRACT)
954  memb_state.ts_sofar |= TS_SOFAR_MINUS;
955  else if (tp->tr_op == OP_INTERSECT)
956  memb_state.ts_sofar |= TS_SOFAR_INTER;
957  _db_recurse_subtree(tp->tr_b.tb_right, &memb_state, pathp, region_start_statepp, client_data);
958  break;
959 
960  default:
961  bu_log("_db_recurse_subtree: bad op %d\n", tp->tr_op);
962  bu_bomb("_db_recurse_subtree\n");
963  }
964 out:
965  db_free_db_tree_state(&memb_state);
966  RT_CK_TREE(tp);
967  return;
968 }
969 
970 
971 union tree *
972 db_recurse(struct db_tree_state *tsp, struct db_full_path *pathp, struct combined_tree_state **region_start_statepp, void *client_data)
973 {
974  struct directory *dp;
975  struct rt_db_internal intern;
976  union tree *curtree = TREE_NULL;
977 
978  RT_CK_DBTS(tsp);
979  RT_CHECK_DBI(tsp->ts_dbip);
980  RT_CK_RESOURCE(tsp->ts_resp);
981  RT_CK_FULL_PATH(pathp);
982  RT_DB_INTERNAL_INIT(&intern);
983 
984  if (pathp->fp_len <= 0) {
985  bu_log("db_recurse() null path?\n");
986  return TREE_NULL;
987  }
988  dp = DB_FULL_PATH_CUR_DIR(pathp);
989 
991  char *sofar = db_path_to_string(pathp);
992  bu_log("db_recurse() pathp='%s', tsp=%p, *statepp=%p, tsp->ts_sofar=%d\n",
993  sofar, (void *)tsp,
994  (void *)*region_start_statepp, tsp->ts_sofar);
995  bu_free(sofar, "path string");
996  if (bn_mat_ck("db_recurse() tsp->ts_mat at start", tsp->ts_mat) < 0) {
997  bu_log("db_recurse(%s): matrix does not preserve axis perpendicularity.\n", dp->d_namep);
998  }
999  }
1000 
1001  /*
1002  * Load the entire object into contiguous memory. Note that this
1003  * code depends on the d_flags being set properly.
1004  */
1005  if (!dp || dp->d_addr == RT_DIR_PHONY_ADDR) return TREE_NULL;
1006 
1007  if (dp->d_flags & RT_DIR_COMB) {
1008  struct rt_comb_internal *comb;
1009  struct db_tree_state nts;
1010  int is_region;
1011 
1012  if (rt_db_get_internal(&intern, dp, tsp->ts_dbip, NULL, tsp->ts_resp) < 0) {
1013  bu_log("db_recurse() rt_db_get_internal(%s) FAIL\n", dp->d_namep);
1014  curtree = TREE_NULL; /* FAIL */
1015  goto out;
1016  }
1017 
1018  /* Handle inheritance of material property. */
1019  db_dup_db_tree_state(&nts, tsp);
1020 
1021  comb = (struct rt_comb_internal *)intern.idb_ptr;
1022  RT_CK_COMB(comb);
1023  db5_sync_attr_to_comb(comb, &intern.idb_avs, dp);
1024  if ((is_region = db_apply_state_from_comb(&nts, pathp, comb)) < 0) {
1025  db_free_db_tree_state(&nts);
1026  curtree = TREE_NULL; /* FAIL */
1027  goto out;
1028  }
1029 
1030  if (is_region > 0) {
1031  struct combined_tree_state *ctsp;
1032 
1033  /* get attribute/value structure */
1034  bu_avs_merge(&nts.ts_attrs, &intern.idb_avs);
1035 
1036  /*
1037  * This is the start of a new region. If handler rejects
1038  * this region, skip on. This might be used for ignoring
1039  * air regions.
1040  */
1041  if (tsp->ts_region_start_func &&
1042  tsp->ts_region_start_func(&nts, pathp, comb, client_data) < 0) {
1043  if (RT_G_DEBUG&DEBUG_TREEWALK) {
1044  char *sofar = db_path_to_string(pathp);
1045  bu_log("db_recurse() ts_region_start_func deletes %s\n",
1046  sofar);
1047  bu_free(sofar, "path string");
1048  }
1049  db_free_db_tree_state(&nts);
1050  curtree = TREE_NULL; /* FAIL */
1051  goto out;
1052  }
1053 
1054  if (tsp->ts_stop_at_regions) {
1055  goto region_end;
1056  }
1057 
1058  /* Take note of full state here at region start */
1059  if (*region_start_statepp != (struct combined_tree_state *)0) {
1060  bu_log("db_recurse() ERROR at start of a region, *region_start_statepp = %p\n",
1061  (void *)*region_start_statepp);
1062  db_free_db_tree_state(&nts);
1063  curtree = TREE_NULL; /* FAIL */
1064  goto out;
1065  }
1066  ctsp = db_new_combined_tree_state(&nts, pathp);
1067  *region_start_statepp = ctsp;
1068  if (RT_G_DEBUG&DEBUG_TREEWALK) {
1069  bu_log("setting *region_start_statepp to %p\n", (void *)ctsp);
1071  }
1072  }
1073 
1074  if (comb->tree) {
1075  /* Steal tree from combination, so it won't be freed */
1076  curtree = comb->tree;
1077  comb->tree = TREE_NULL;
1078  if (curtree) RT_CK_TREE(curtree);
1079 
1080  /* Release most of internal form before recursing */
1081  rt_db_free_internal(&intern);
1082  comb = NULL;
1083 
1084  _db_recurse_subtree(curtree, &nts, pathp, region_start_statepp, client_data);
1085  if (curtree) RT_CK_TREE(curtree);
1086  } else {
1087  /* No subtrees in this combination, invent a NOP */
1088  RT_GET_TREE(curtree, tsp->ts_resp);
1089  curtree->tr_op = OP_NOP;
1090  if (curtree) RT_CK_TREE(curtree);
1091  }
1092 
1093  region_end:
1094  if (is_region > 0) {
1095  /*
1096  * This is the end of processing for a region.
1097  */
1098  if (tsp->ts_region_end_func) {
1099  curtree = tsp->ts_region_end_func(
1100  &nts, pathp, curtree, client_data);
1101  if (curtree) RT_CK_TREE(curtree);
1102  }
1103  }
1104  db_free_db_tree_state(&nts);
1105  if (curtree) RT_CK_TREE(curtree);
1106  } else if (dp->d_flags & RT_DIR_SOLID) {
1107 
1108  if (bn_mat_ck(dp->d_namep, tsp->ts_mat) < 0) {
1109  bu_log("db_recurse(%s): matrix does not preserve axis perpendicularity.\n",
1110  dp->d_namep);
1111  bn_mat_print("bad matrix", tsp->ts_mat);
1112  curtree = TREE_NULL; /* FAIL */
1113  goto out;
1114  }
1115 
1116  if (RT_G_DEBUG&DEBUG_TREEWALK)
1117  bu_log("db_recurse() rt_db_get_internal(%s) solid\n", dp->d_namep);
1118 
1119  RT_DB_INTERNAL_INIT(&intern);
1120  if (rt_db_get_internal(&intern, dp, tsp->ts_dbip, tsp->ts_mat, tsp->ts_resp) < 0) {
1121  bu_log("db_recurse() rt_db_get_internal(%s) FAIL\n", dp->d_namep);
1122  curtree = TREE_NULL; /* FAIL */
1123  goto out;
1124  }
1125 
1126  if ((tsp->ts_sofar & TS_SOFAR_REGION) == 0 &&
1127  tsp->ts_stop_at_regions == 0) {
1128  struct combined_tree_state *ctsp;
1129  char *sofar = db_path_to_string(pathp);
1130  /*
1131  * Solid is not contained in a region.
1132  * "Invent" region info.
1133  * Take note of full state here at "region start".
1134  */
1135  if (*region_start_statepp != (struct combined_tree_state *)0) {
1136  bu_log("db_recurse(%s) ERROR at start of a region (bare solid), *region_start_statepp = %p\n",
1137  sofar, (void *)*region_start_statepp);
1138  curtree = TREE_NULL; /* FAIL */
1139  goto out;
1140  }
1141  if (RT_G_DEBUG & DEBUG_REGIONS) {
1142  bu_log("NOTICE: db_recurse(): solid '%s' not contained in a region, creating a region for it of the same name.\n",
1143  sofar);
1144  }
1145 
1146  ctsp = db_new_combined_tree_state(tsp, pathp);
1147  ctsp->cts_s.ts_sofar |= TS_SOFAR_REGION;
1148  *region_start_statepp = ctsp;
1149  if (RT_G_DEBUG&DEBUG_TREEWALK) {
1150  bu_log("db_recurse(%s): setting *region_start_statepp to %p (bare solid)\n",
1151  sofar, (void *)ctsp);
1153  }
1154  bu_free(sofar, "path string");
1155  }
1156 
1157  /* Hand the solid off for leaf processing */
1158  if (!tsp->ts_leaf_func) {
1159  curtree = TREE_NULL; /* FAIL */
1160  goto out;
1161  }
1162  curtree = tsp->ts_leaf_func(tsp, pathp, &intern, client_data);
1163  if (curtree) RT_CK_TREE(curtree);
1164  } else {
1165  bu_log("%s is not a drawable database object\n",
1166  dp->d_namep);
1167  curtree = TREE_NULL;
1168  return curtree;
1169  }
1170 out:
1171  /* rt_db_get_internal() may not have been called yet, so do not
1172  * try to free intern unless we know there is something to free
1173  */
1174  if (intern.idb_ptr != NULL) {
1175  rt_db_free_internal(&intern);
1176  }
1177  if (RT_G_DEBUG&DEBUG_TREEWALK) {
1178  char *sofar = db_path_to_string(pathp);
1179  bu_log("db_recurse() return curtree=%p, pathp='%s', *statepp=%p\n",
1180  (void *)curtree, sofar,
1181  (void *)*region_start_statepp);
1182  bu_free(sofar, "path string");
1183  }
1184  if (curtree) RT_CK_TREE(curtree);
1185  return curtree;
1186 }
1187 
1188 
1189 union tree *
1190 db_dup_subtree(const union tree *tp, struct resource *resp)
1191 {
1192  union tree *new_tp;
1193 
1194  if (!tp)
1195  return TREE_NULL;
1196 
1197  RT_CK_TREE(tp);
1198  if (!resp) {
1199  resp = &rt_uniresource;
1200  }
1201  RT_CK_RESOURCE(resp);
1202 
1203  RT_GET_TREE(new_tp, resp);
1204  *new_tp = *tp; /* struct copy */
1205 
1206  switch (tp->tr_op) {
1207  case OP_NOP:
1208  case OP_SOLID:
1209  /* If this is a simple leaf, done */
1210  return new_tp;
1211 
1212  case OP_DB_LEAF:
1213  if (tp->tr_l.tl_mat)
1214  new_tp->tr_l.tl_mat = bn_mat_dup(tp->tr_l.tl_mat);
1215  new_tp->tr_l.tl_name = bu_strdup(tp->tr_l.tl_name);
1216  return new_tp;
1217 
1218  case OP_REGION:
1219  /* If this is a REGION leaf, dup combined_tree_state & path */
1221  tp->tr_c.tc_ctsp);
1222  return new_tp;
1223 
1224  case OP_NOT:
1225  case OP_GUARD:
1226  case OP_XNOP:
1227  new_tp->tr_b.tb_left = db_dup_subtree(tp->tr_b.tb_left, resp);
1228  return new_tp;
1229 
1230  case OP_UNION:
1231  case OP_INTERSECT:
1232  case OP_SUBTRACT:
1233  case OP_XOR:
1234  /* This node is known to be a binary op */
1235  new_tp->tr_b.tb_left = db_dup_subtree(tp->tr_b.tb_left, resp);
1236  new_tp->tr_b.tb_right = db_dup_subtree(tp->tr_b.tb_right, resp);
1237  return new_tp;
1238 
1239  case OP_NMG_TESS: {
1240  /* FIXME: fake "copy" .. lie!!! */
1241  new_tp->tr_d.td_r = tp->tr_d.td_r;
1242  new_tp->tr_d.td_name = bu_strdup(tp->tr_d.td_name);
1243  return new_tp;
1244  }
1245 
1246  default:
1247  bu_log("db_dup_subtree: bad op %d\n", tp->tr_op);
1248  bu_bomb("db_dup_subtree\n");
1249  }
1250  return TREE_NULL;
1251 }
1252 
1253 
1254 void
1255 db_ck_tree(const union tree *tp)
1256 {
1257  RT_CK_TREE(tp);
1258 
1259  switch (tp->tr_op) {
1260  case OP_NOP:
1261  break;
1262  case OP_DB_LEAF:
1263  BU_ASSERT_PTR(tp->tr_l.tl_name, !=, NULL);
1264  break;
1265  case OP_SOLID:
1266  if (tp->tr_a.tu_stp)
1267  RT_CK_SOLTAB(tp->tr_a.tu_stp);
1268  break;
1269  case OP_REGION:
1270  RT_CK_CTS(tp->tr_c.tc_ctsp);
1271  break;
1272 
1273  case OP_NOT:
1274  case OP_GUARD:
1275  case OP_XNOP:
1276  db_ck_tree(tp->tr_b.tb_left);
1277  break;
1278 
1279  case OP_UNION:
1280  case OP_INTERSECT:
1281  case OP_SUBTRACT:
1282  case OP_XOR:
1283  /* This node is known to be a binary op */
1284  db_ck_tree(tp->tr_b.tb_left);
1285  db_ck_tree(tp->tr_b.tb_right);
1286  break;
1287 
1288  default:
1289  bu_log("db_ck_tree: bad op %d\n", tp->tr_op);
1290  bu_bomb("db_ck_tree\n");
1291  }
1292 }
1293 
1294 
1295 void
1296 db_free_tree(union tree *tp, struct resource *resp)
1297 {
1298  if (!tp)
1299  return;
1300 
1301  RT_CK_TREE(tp);
1302  if (!resp) {
1303  resp = &rt_uniresource;
1304  }
1305  RT_CK_RESOURCE(resp);
1306 
1307  /*
1308  * Before recursion, smash the magic number, so that if another
1309  * thread tries to free this same tree, they will fail.
1310  */
1311  tp->magic = (uint32_t)-3; /* special bad flag */
1312 
1313  switch (tp->tr_op) {
1314  case OP_FREE :
1315  tp->tr_op = 0; /* sanity */
1316  return;
1317  case OP_NOP:
1318  break;
1319 
1320  case OP_SOLID:
1321  if (tp->tr_a.tu_stp) {
1322  struct soltab *stp = tp->tr_a.tu_stp;
1323  RT_CK_SOLTAB(stp);
1324  tp->tr_a.tu_stp = RT_SOLTAB_NULL;
1325  rt_free_soltab(stp);
1326  }
1327  break;
1328  case OP_REGION:
1329  /* REGION leaf, free combined_tree_state & path */
1331  tp->tr_c.tc_ctsp = (struct combined_tree_state *)0;
1332  break;
1333 
1334  case OP_NMG_TESS:
1335  {
1336  struct nmgregion *r = tp->tr_d.td_r;
1337  if (tp->tr_d.td_name) {
1338  bu_free((char *)tp->tr_d.td_name, "region name");
1339  tp->tr_d.td_name = (const char *)NULL;
1340  }
1341  if (r == (struct nmgregion *)NULL) {
1342  break;
1343  }
1344  /* Disposing of the nmg model structure is
1345  * left to someone else.
1346  * It would be rude to zap all the other regions here.
1347  */
1348  if (r->l.magic == NMG_REGION_MAGIC) {
1349  NMG_CK_REGION(r);
1350  nmg_kr(r);
1351  }
1352  tp->tr_d.td_r = (struct nmgregion *)NULL;
1353  }
1354  break;
1355 
1356  case OP_DB_LEAF:
1357  if (tp->tr_l.tl_mat) {
1358  bu_free((char *)tp->tr_l.tl_mat, "tl_mat");
1359  tp->tr_l.tl_mat = NULL;
1360  }
1361  bu_free(tp->tr_l.tl_name, "tl_name");
1362  tp->tr_l.tl_name = NULL;
1363  break;
1364 
1365  case OP_NOT:
1366  case OP_GUARD:
1367  case OP_XNOP:
1368  if (tp->tr_b.tb_left->magic == RT_TREE_MAGIC)
1369  db_free_tree(tp->tr_b.tb_left, resp);
1370  tp->tr_b.tb_left = TREE_NULL;
1371  break;
1372 
1373  case OP_UNION:
1374  case OP_INTERSECT:
1375  case OP_SUBTRACT:
1376  case OP_XOR:
1377  {
1378  union tree *fp;
1379 
1380  /* This node is known to be a binary op */
1381  fp = tp->tr_b.tb_left;
1382  tp->tr_b.tb_left = TREE_NULL;
1383  RT_CK_TREE(fp);
1384  db_free_tree(fp, resp);
1385 
1386  fp = tp->tr_b.tb_right;
1387  tp->tr_b.tb_right = TREE_NULL;
1388  RT_CK_TREE(fp);
1389  db_free_tree(fp, resp);
1390  }
1391  break;
1392 
1393  default:
1394  bu_log("db_free_tree: bad op %d\n", tp->tr_op);
1395  bu_bomb("db_free_tree\n");
1396  }
1397  tp->tr_op = 0; /* sanity */
1398 
1399  RT_FREE_TREE(tp, resp);
1400 }
1401 
1402 
1403 void
1405 {
1406  union tree *lhs, *rhs;
1407 
1408  RT_CK_TREE(tp);
1409 
1410  if (tp->tr_op != OP_UNION)
1411  return;
1412 
1413  while (tp->tr_b.tb_right->tr_op == OP_UNION) {
1414  lhs = tp->tr_b.tb_left;
1415  rhs = tp->tr_b.tb_right;
1416 
1417  tp->tr_b.tb_left = rhs;
1418  tp->tr_b.tb_right = rhs->tr_b.tb_right;
1419  rhs->tr_b.tb_right = rhs->tr_b.tb_left;
1420  rhs->tr_b.tb_left = lhs;
1421  }
1422 }
1423 
1424 
1425 void
1426 db_non_union_push(union tree *tp, struct resource *resp)
1427 {
1428  union tree *A, *B, *C;
1429  union tree *tmp;
1430  int repush_child=0;
1431 
1432  RT_CK_TREE(tp);
1433  if (!resp) {
1434  resp = &rt_uniresource;
1435  }
1436  RT_CK_RESOURCE(resp);
1437 
1438  switch (tp->tr_op) {
1439  case OP_REGION:
1440  case OP_SOLID:
1441  case OP_DB_LEAF:
1442  /* If this is a leaf, done */
1443  return;
1444 
1445  case OP_NOP:
1446  /* This tree has nothing in it, done */
1447  return;
1448 
1449  default:
1450  db_non_union_push(tp->tr_b.tb_left, resp);
1451  db_non_union_push(tp->tr_b.tb_right, resp);
1452  break;
1453  }
1454  if ((tp->tr_op == OP_INTERSECT || tp->tr_op == OP_SUBTRACT)
1455  && tp->tr_b.tb_left->tr_op == OP_UNION)
1456  {
1457  union tree *lhs = tp->tr_b.tb_left;
1458  union tree *rhs;
1459 
1460  A = lhs->tr_b.tb_left;
1461  B = lhs->tr_b.tb_right;
1462 
1463  if (A->tr_op == OP_NOP && B->tr_op == OP_NOP) {
1464  /* nothing here, eliminate entire subtree */
1465  db_free_tree(tp->tr_b.tb_left, resp);
1466  db_free_tree(tp->tr_b.tb_right, resp);
1467  tp->tr_op = OP_NOP;
1468  tp->tr_b.tb_left = NULL;
1469  tp->tr_b.tb_right = NULL;
1470 
1471  } else if (A->tr_op == OP_NOP) {
1472  db_tree_del_lhs(lhs, resp);
1473 
1474  /* recurse */
1475  db_non_union_push(tp, resp);
1476  } else if (B->tr_op == OP_NOP) {
1477  db_tree_del_rhs(lhs, resp);
1478 
1479  /* recurse */
1480  db_non_union_push(tp, resp);
1481  } else {
1482 
1483  repush_child = 1;
1484 
1485  /* Rewrite intersect and subtraction nodes, such that
1486  * (A u B) - C becomes (A - C) u (B - C)
1487  *
1488  * tp-> -
1489  * / \
1490  * lhs-> u C
1491  * / \
1492  * A B
1493  */
1494  RT_GET_TREE(rhs, resp);
1495 
1496  /* duplicate top node into rhs */
1497  *rhs = *tp; /* struct copy */
1498  tp->tr_b.tb_right = rhs;
1499  /* rhs->tr_b.tb_right remains unchanged:
1500  *
1501  * tp-> -
1502  * / \
1503  * lhs-> u - <-rhs
1504  * / \ / \
1505  * A B ? C
1506  */
1507 
1508  rhs->tr_b.tb_left = lhs->tr_b.tb_right;
1509  /*
1510  * tp-> -
1511  * / \
1512  * lhs-> u - <-rhs
1513  * / \ / \
1514  * A B B C
1515  */
1516 
1517  /* exchange left and top operators */
1518  tp->tr_op = lhs->tr_op;
1519  lhs->tr_op = rhs->tr_op;
1520  /*
1521  * tp-> u
1522  * / \
1523  * lhs-> - - <-rhs
1524  * / \ / \
1525  * A B B C
1526  */
1527 
1528  /* Make a duplicate of rhs->tr_b.tb_right */
1529  lhs->tr_b.tb_right = db_dup_subtree(rhs->tr_b.tb_right, resp);
1530  /*
1531  * tp-> u
1532  * / \
1533  * lhs-> - - <-rhs
1534  * / \ / \
1535  * A C' B C
1536  */
1537  }
1538 
1539  } else if (tp->tr_op == OP_INTERSECT && tp->tr_b.tb_right->tr_op == OP_UNION) {
1540  /* C + (A u B) -> (C + A) u (C + B) */
1541  union tree *rhs = tp->tr_b.tb_right;
1542 
1543  C = tp->tr_b.tb_left;
1544  A = tp->tr_b.tb_right->tr_b.tb_left;
1545  B = tp->tr_b.tb_right->tr_b.tb_right;
1546 
1547  if (A->tr_op == OP_NOP && B->tr_op == OP_NOP) {
1548  /* nothing here, eliminate entire subtree */
1549  tp->tr_op = OP_NOP;
1550  db_free_tree(tp->tr_b.tb_left, resp);
1551  db_free_tree(tp->tr_b.tb_right, resp);
1552  tp->tr_b.tb_left = NULL;
1553  tp->tr_b.tb_right = NULL;
1554  } else if (A->tr_op == OP_NOP) {
1555  db_tree_del_lhs(rhs, resp);
1556 
1557  /* recurse */
1558  db_non_union_push(tp, resp);
1559  } else if (B->tr_op == OP_NOP) {
1560  db_tree_del_rhs(rhs, resp);
1561 
1562  /* recurse */
1563  db_non_union_push(tp, resp);
1564  } else {
1565  repush_child = 1;
1566 
1567  tp->tr_op = OP_UNION;
1568  RT_GET_TREE(tmp, resp);
1569  tmp->tr_regionp = tp->tr_regionp;
1570  tmp->tr_op = OP_INTERSECT;
1571  tmp->tr_b.tb_left = C;
1572  tmp->tr_b.tb_right = A;
1573  tp->tr_b.tb_left = tmp;
1574  tp->tr_b.tb_right->tr_op = OP_INTERSECT;
1575  tp->tr_b.tb_right->tr_b.tb_left = db_dup_subtree(C, resp);
1576  }
1577  } else if (tp->tr_op == OP_SUBTRACT && tp->tr_b.tb_right->tr_op == OP_UNION) {
1578  /* C - (A u B) -> C - A - B */
1579  union tree *rhs = tp->tr_b.tb_right;
1580 
1581 
1582  C = tp->tr_b.tb_left;
1583  A = tp->tr_b.tb_right->tr_b.tb_left;
1584  B = tp->tr_b.tb_right->tr_b.tb_right;
1585 
1586  if (C->tr_op == OP_NOP) {
1587  /* nothing here, eliminate entire subtree */
1588  tp->tr_op = OP_NOP;
1589  db_free_tree(tp->tr_b.tb_left, resp);
1590  db_free_tree(tp->tr_b.tb_right, resp);
1591  tp->tr_b.tb_left = NULL;
1592  tp->tr_b.tb_right = NULL;
1593  } else if (A->tr_op == OP_NOP && B->tr_op == OP_NOP) {
1594  db_tree_del_rhs(tp, resp);
1595 
1596  /* recurse */
1597  db_non_union_push(tp, resp);
1598  } else if (A->tr_op == OP_NOP) {
1599  db_tree_del_lhs(rhs, resp);
1600 
1601  /* recurse */
1602  db_non_union_push(tp, resp);
1603  } else if (B->tr_op == OP_NOP) {
1604  db_tree_del_rhs(rhs, resp);
1605 
1606  /* recurse */
1607  db_non_union_push(tp, resp);
1608  } else {
1609  repush_child = 1;
1610 
1611  tp->tr_b.tb_left = tp->tr_b.tb_right;
1612  tp->tr_b.tb_left->tr_op = OP_SUBTRACT;
1613  tp->tr_b.tb_right = B;
1614  tmp = tp->tr_b.tb_left;
1615  tmp->tr_b.tb_left = C;
1616  tmp->tr_b.tb_right = A;
1617  }
1618  }
1619 
1620  /* if this operation has moved a UNION operator towards the leaves
1621  * then the children must be processed again
1622  */
1623  if (repush_child) {
1624  db_non_union_push(tp->tr_b.tb_left, resp);
1625  db_non_union_push(tp->tr_b.tb_right, resp);
1626  }
1627 
1628  /* rebalance this node (moves UNIONs to left side) */
1629  db_left_hvy_node(tp);
1630 }
1631 
1632 
1633 int
1634 db_count_tree_nodes(const union tree *tp, int count)
1635 {
1636  RT_CK_TREE(tp);
1637  switch (tp->tr_op) {
1638  case OP_NOP:
1639  case OP_SOLID:
1640  case OP_REGION:
1641  case OP_DB_LEAF:
1642  /* A leaf node */
1643  return count+1;
1644 
1645  case OP_UNION:
1646  case OP_INTERSECT:
1647  case OP_SUBTRACT:
1648  case OP_XOR:
1649  /* This node is known to be a binary op */
1650  count = db_count_tree_nodes(tp->tr_b.tb_left, count);
1651  count = db_count_tree_nodes(tp->tr_b.tb_right, count);
1652  return count+1;
1653 
1654  case OP_NOT:
1655  case OP_GUARD:
1656  case OP_XNOP:
1657  /* This node is known to be a unary op */
1658  count = db_count_tree_nodes(tp->tr_b.tb_left, count);
1659  return count+1;
1660 
1661  default:
1662  bu_log("db_count_tree_nodes: bad op %d\n", tp->tr_op);
1663  bu_bomb("db_count_tree_nodes\n");
1664  }
1665  return 0;
1666 }
1667 
1668 
1669 int
1670 db_is_tree_all_unions(const union tree *tp)
1671 {
1672  RT_CK_TREE(tp);
1673  switch (tp->tr_op) {
1674  case OP_NOP:
1675  case OP_SOLID:
1676  case OP_REGION:
1677  case OP_DB_LEAF:
1678  /* A leaf node */
1679  return 1; /* yep */
1680 
1681  case OP_UNION:
1682  if (db_is_tree_all_unions(tp->tr_b.tb_left) == 0)
1683  return 0;
1684  return db_is_tree_all_unions(tp->tr_b.tb_right);
1685 
1686  case OP_INTERSECT:
1687  case OP_SUBTRACT:
1688  return 0; /* nope */
1689 
1690  case OP_XOR:
1691  case OP_NOT:
1692  case OP_GUARD:
1693  case OP_XNOP:
1694  return 0; /* nope */
1695 
1696  default:
1697  bu_log("db_is_tree_all_unions: bad op %d\n", tp->tr_op);
1698  bu_bomb("db_is_tree_all_unions\n");
1699  }
1700  return 0;
1701 }
1702 
1703 
1704 int
1706 {
1707  int cnt;
1708 
1709  RT_CK_TREE(tp);
1710  switch (tp->tr_op) {
1711  case OP_SOLID:
1712  case OP_REGION:
1713  case OP_DB_LEAF:
1714  return 1;
1715 
1716  case OP_UNION:
1717  /* This node is known to be a binary op */
1720  return cnt;
1721 
1722  case OP_INTERSECT:
1723  case OP_SUBTRACT:
1724  case OP_XOR:
1725  case OP_NOT:
1726  case OP_GUARD:
1727  case OP_XNOP:
1728  case OP_NOP:
1729  /* This is as far down as we go -- this is a region top */
1730  return 1;
1731 
1732  default:
1733  bu_log("db_count_subtree_regions: bad op %d\n", tp->tr_op);
1734  bu_bomb("db_count_subtree_regions\n");
1735  }
1736  return 0;
1737 }
1738 
1739 
1740 int
1742  union tree *tp,
1743  union tree **reg_trees,
1744  int cur,
1745  int lim,
1746  struct resource *resp)
1747 {
1748  union tree *new_tp;
1749 
1750  RT_CK_TREE(tp);
1751  if (!resp) {
1752  resp = &rt_uniresource;
1753  }
1754  RT_CK_RESOURCE(resp);
1755  if (cur >= lim) bu_bomb("db_tally_subtree_regions: array overflow\n");
1756 
1757  switch (tp->tr_op) {
1758  case OP_NOP:
1759  return cur;
1760 
1761  case OP_SOLID:
1762  case OP_REGION:
1763  case OP_DB_LEAF:
1764  RT_GET_TREE(new_tp, resp);
1765  *new_tp = *tp; /* struct copy */
1766  tp->tr_op = OP_NOP; /* Zap original */
1767  reg_trees[cur++] = new_tp;
1768  return cur;
1769 
1770  case OP_UNION:
1771  /* This node is known to be a binary op */
1772  cur = db_tally_subtree_regions(tp->tr_b.tb_left, reg_trees, cur, lim, resp);
1773  cur = db_tally_subtree_regions(tp->tr_b.tb_right, reg_trees, cur, lim, resp);
1774  return cur;
1775 
1776  case OP_INTERSECT:
1777  case OP_SUBTRACT:
1778  case OP_XOR:
1779  case OP_NOT:
1780  case OP_GUARD:
1781  case OP_XNOP:
1782  /* This is as far down as we go -- this is a region top */
1783  RT_GET_TREE(new_tp, resp);
1784  *new_tp = *tp; /* struct copy */
1785  tp->tr_op = OP_NOP; /* Zap original */
1786  reg_trees[cur++] = new_tp;
1787  return cur;
1788 
1789  default:
1790  bu_log("db_tally_subtree_regions: bad op %d\n", tp->tr_op);
1791  bu_bomb("db_tally_subtree_regions\n");
1792  }
1793  return cur;
1794 }
1795 
1796 
1797 /* ============================== */
1798 
1799 HIDDEN union tree *
1800 _db_gettree_region_end(struct db_tree_state *tsp, const struct db_full_path *pathp, union tree *curtree, void *UNUSED(client_data))
1801 {
1802 
1803  RT_CK_DBTS(tsp);
1804  RT_CK_DBI(tsp->ts_dbip);
1805  RT_CK_FULL_PATH(pathp);
1806  RT_CK_RESOURCE(tsp->ts_resp);
1807 
1808  RT_GET_TREE(curtree, tsp->ts_resp);
1809  curtree->tr_op = OP_REGION;
1810  curtree->tr_c.tc_ctsp = db_new_combined_tree_state(tsp, pathp);
1811 
1812  return curtree;
1813 }
1814 
1815 
1816 HIDDEN union tree *
1817 _db_gettree_leaf(struct db_tree_state *tsp, const struct db_full_path *pathp, struct rt_db_internal *ip, void *UNUSED(client_data))
1818 {
1819  union tree *curtree;
1820 
1821  RT_CK_DBTS(tsp);
1822  RT_CK_DBI(tsp->ts_dbip);
1823  RT_CK_FULL_PATH(pathp);
1824  RT_CK_DB_INTERNAL(ip);
1825  RT_CK_RESOURCE(tsp->ts_resp);
1826 
1827  RT_GET_TREE(curtree, tsp->ts_resp);
1828  curtree->tr_op = OP_REGION;
1829  curtree->tr_c.tc_ctsp = db_new_combined_tree_state(tsp, pathp);
1830 
1831  return curtree;
1832 }
1833 
1834 
1836  uint32_t magic;
1837  union tree **reg_trees;
1839  int reg_current; /* semaphored when parallel */
1840  union tree * (*reg_end_func)(struct db_tree_state *, const struct db_full_path *, union tree *, void *);
1841  union tree * (*reg_leaf_func)(struct db_tree_state *, const struct db_full_path *, struct rt_db_internal *, void *);
1842  struct rt_i *rtip;
1844 };
1845 #define DB_WALK_PARALLEL_STATE_MAGIC 0x64777073 /* dwps */
1846 #define DB_CK_WPS(_p) BU_CKMAG(_p, DB_WALK_PARALLEL_STATE_MAGIC, "db_walk_parallel_state")
1847 
1848 
1849 HIDDEN void
1851  union tree *tp,
1852  struct combined_tree_state **region_start_statepp,
1853  union tree *(*leaf_func)(struct db_tree_state *, const struct db_full_path *, struct rt_db_internal *, void *),
1854  void *client_data,
1855  struct resource *resp)
1856 {
1857  struct combined_tree_state *ctsp;
1858  union tree *curtree;
1859 
1860  RT_CK_TREE(tp);
1861  RT_CK_RESOURCE(resp);
1862 
1863  switch (tp->tr_op) {
1864  case OP_NOP:
1865  return;
1866 
1867  /* case OP_SOLID:*/
1868  case OP_REGION:
1869  /* Flesh out remainder of subtree */
1870  ctsp = tp->tr_c.tc_ctsp;
1871  RT_CK_CTS(ctsp);
1872  if (ctsp->cts_p.fp_len <= 0) {
1873  bu_log("_db_walk_subtree() REGION with null path?\n");
1875  /* Result is an empty tree */
1876  tp->tr_op = OP_NOP;
1877  tp->tr_a.tu_stp = 0;
1878  return;
1879  }
1880  RT_CK_DBI(ctsp->cts_s.ts_dbip);
1881  ctsp->cts_s.ts_stop_at_regions = 0;
1882  /* All regions will be accepted, in this 2nd pass */
1883  ctsp->cts_s.ts_region_start_func = 0;
1884  /* ts_region_end_func() will be called in _db_walk_dispatcher() */
1885  ctsp->cts_s.ts_region_end_func = 0;
1886  /* Use user's leaf function */
1887  ctsp->cts_s.ts_leaf_func = leaf_func;
1888  ctsp->cts_s.ts_resp = resp;
1889 
1890  /* If region already seen, force flag */
1891  if (*region_start_statepp)
1892  ctsp->cts_s.ts_sofar |= TS_SOFAR_REGION;
1893  else
1894  ctsp->cts_s.ts_sofar &= ~TS_SOFAR_REGION;
1895 
1896  curtree = db_recurse(&ctsp->cts_s, &ctsp->cts_p, region_start_statepp, client_data);
1897  if (curtree == TREE_NULL) {
1898  char *str;
1899  str = db_path_to_string(&(ctsp->cts_p));
1900  bu_log("_db_walk_subtree() FAIL on '%s'\n", str);
1901  bu_free(str, "path string");
1902 
1904  /* Result is an empty tree */
1905  tp->tr_op = OP_NOP;
1906  tp->tr_a.tu_stp = 0;
1907  return;
1908  }
1909  /* replace *tp with new subtree */
1910  *tp = *curtree; /* struct copy */
1912  RT_FREE_TREE(curtree, resp);
1913  return;
1914 
1915  case OP_NOT:
1916  case OP_GUARD:
1917  case OP_XNOP:
1918  _db_walk_subtree(tp->tr_b.tb_left, region_start_statepp, leaf_func, client_data, resp);
1919  return;
1920 
1921  case OP_UNION:
1922  case OP_INTERSECT:
1923  case OP_SUBTRACT:
1924  case OP_XOR:
1925  /* This node is known to be a binary op */
1926  _db_walk_subtree(tp->tr_b.tb_left, region_start_statepp, leaf_func, client_data, resp);
1927  _db_walk_subtree(tp->tr_b.tb_right, region_start_statepp, leaf_func, client_data, resp);
1928  return;
1929 
1930  case OP_DB_LEAF:
1931  rt_pr_tree(tp, 1);
1932  bu_bomb("_db_walk_subtree() unexpected DB_LEAF\n");
1933 
1934  default:
1935  bu_log("_db_walk_subtree: bad op %d\n", tp->tr_op);
1936  bu_bomb("_db_walk_subtree() bad op\n");
1937  }
1938 }
1939 
1940 
1941 /**
1942  * This routine handles the PARALLEL portion of db_walk_tree(). There
1943  * will be at least one, and possibly more, instances of this routine
1944  * running simultaneously.
1945  *
1946  * Uses the self-dispatcher pattern: Pick off the next region's tree,
1947  * and walk it.
1948  */
1949 HIDDEN void
1950 _db_walk_dispatcher(int cpu, void *arg)
1951 {
1952  struct combined_tree_state *region_start_statep;
1953  int mine;
1954  union tree *curtree;
1955  struct db_walk_parallel_state *wps = (struct db_walk_parallel_state *)arg;
1956  struct resource *resp;
1957 
1958  DB_CK_WPS(wps);
1959 
1960  if (wps->rtip == NULL || cpu == 0) {
1961  resp = &rt_uniresource;
1962  } else {
1963  RT_CK_RTI(wps->rtip);
1964 
1965  resp = (struct resource *)BU_PTBL_GET(&wps->rtip->rti_resources, cpu);
1966  if (resp == NULL)
1967  resp = &rt_uniresource;
1968  }
1969  RT_CK_RESOURCE(resp);
1970 
1971  while (1) {
1973  mine = wps->reg_current++;
1975 
1976  if (mine >= wps->reg_count)
1977  break;
1978 
1980  bu_log("\n\n***** _db_walk_dispatcher() on item %d\n\n", mine);
1981 
1982  if ((curtree = wps->reg_trees[mine]) == TREE_NULL)
1983  continue;
1984  RT_CK_TREE(curtree);
1985 
1986  /* Walk the full subtree now */
1987  region_start_statep = (struct combined_tree_state *)0;
1988  _db_walk_subtree(curtree, &region_start_statep, wps->reg_leaf_func, wps->client_data, resp);
1989 
1990  /* curtree->tr_op may be OP_NOP here.
1991  * It is up to db_reg_end_func() to deal with this,
1992  * either by discarding it, or making a null region.
1993  */
1994  RT_CK_TREE(curtree);
1995  if (!region_start_statep) {
1996  bu_log("ERROR: _db_walk_dispatcher() region %d started with no state\n", mine);
1997  if (RT_G_DEBUG&DEBUG_TREEWALK)
1998  rt_pr_tree(curtree, 0);
1999  continue;
2000  }
2001  RT_CK_CTS(region_start_statep);
2002 
2003  /* This is a new region */
2004  if (RT_G_DEBUG&DEBUG_TREEWALK)
2005  db_pr_combined_tree_state(region_start_statep);
2006 
2007  /*
2008  * reg_end_func() returns a pointer to any unused
2009  * subtree for freeing.
2010  */
2011  if (wps->reg_end_func) {
2012  wps->reg_trees[mine] = (*(wps->reg_end_func))(
2013  &(region_start_statep->cts_s),
2014  &(region_start_statep->cts_p),
2015  curtree, wps->client_data);
2016  }
2017 
2018  db_free_combined_tree_state(region_start_statep);
2019  }
2020 }
2021 
2022 
2023 int
2024 db_walk_tree(struct db_i *dbip,
2025  int argc,
2026  const char **argv,
2027  int ncpu,
2028  const struct db_tree_state *init_state,
2029  int (*reg_start_func) (struct db_tree_state *, const struct db_full_path *, const struct rt_comb_internal *, void *),
2030  union tree *(*reg_end_func) (struct db_tree_state *, const struct db_full_path *, union tree *, void *),
2031  union tree *(*leaf_func) (struct db_tree_state *, const struct db_full_path *, struct rt_db_internal *, void *),
2032  void *client_data)
2033 {
2034  union tree *whole_tree = TREE_NULL;
2035  int new_reg_count;
2036  int i;
2037  int something_not_found = 0;
2038  union tree **reg_trees; /* (*reg_trees)[] */
2039  struct db_walk_parallel_state wps;
2040  struct resource *resp;
2041 
2042  RT_CK_DBTS(init_state);
2043  RT_CHECK_DBI(dbip);
2044 
2045  if (init_state->ts_rtip == NULL || ncpu == 1) {
2046  resp = &rt_uniresource;
2047  } else {
2048  RT_CK_RTI(init_state->ts_rtip);
2049  resp = (struct resource *)BU_PTBL_GET(&init_state->ts_rtip->rti_resources, 0);
2050  if (resp == NULL) {
2051  resp = &rt_uniresource;
2052  }
2053  }
2054  RT_CK_RESOURCE(resp);
2055 
2056  /* Walk each of the given path strings */
2057  for (i = 0; i < argc; i++) {
2058  union tree *curtree;
2059  struct db_tree_state ts;
2060  struct db_full_path path;
2061  struct combined_tree_state *region_start_statep;
2062 
2063  ts = *init_state; /* struct copy */
2064  ts.ts_dbip = dbip;
2065  ts.ts_resp = resp;
2066  db_full_path_init(&path);
2067 
2068  /* First, establish context from given path */
2069  if (db_follow_path_for_state(&ts, &path, argv[i],
2070  LOOKUP_NOISY) < 0) {
2071  bu_log ("db_walk_tree: warning - %s not found.\n",
2072  argv[i]);
2073  ++ something_not_found;
2074  continue; /* ERROR */
2075  }
2076  if (path.fp_len <= 0) {
2077  continue; /* e.g., null combination */
2078  }
2079 
2080  /*
2081  * Second, walk tree from root to start of all regions. Build
2082  * a boolean tree of all regions. Use user function to
2083  * accept/reject each region here. Use internal functions to
2084  * process regions & leaves.
2085  */
2086  ts.ts_stop_at_regions = 1;
2087  ts.ts_region_start_func = reg_start_func;
2090 
2091  region_start_statep = (struct combined_tree_state *)0;
2092  curtree = db_recurse(&ts, &path, &region_start_statep, client_data);
2093  if (region_start_statep)
2094  db_free_combined_tree_state(region_start_statep);
2095  db_free_full_path(&path);
2096  if (curtree == TREE_NULL)
2097  continue; /* ERROR */
2098 
2099  RT_CK_TREE(curtree);
2100  if (RT_G_DEBUG&DEBUG_TREEWALK) {
2101  bu_log("tree after db_recurse():\n");
2102  rt_pr_tree(curtree, 0);
2103  }
2104 
2105  if (whole_tree == TREE_NULL) {
2106  whole_tree = curtree;
2107  } else {
2108  union tree *new_tp;
2109 
2110  RT_GET_TREE(new_tp, ts.ts_resp);
2111  new_tp->tr_op = OP_UNION;
2112  new_tp->tr_b.tb_left = whole_tree;
2113  new_tp->tr_b.tb_right = curtree;
2114  whole_tree = new_tp;
2115  }
2116  }
2117 
2118  if (whole_tree == TREE_NULL)
2119  return -1; /* ERROR, nothing worked */
2120 
2121 
2122  /*
2123  * Third, push all non-union booleans down.
2124  */
2125  db_non_union_push(whole_tree, resp);
2126  if (RT_G_DEBUG&DEBUG_TREEWALK) {
2127  char *str;
2128 
2129  bu_log("tree after db_non_union_push():\n");
2130  rt_pr_tree(whole_tree, 0);
2131  bu_log("Same tree in another form:\n");
2132  str = (char *)rt_pr_tree_str(whole_tree);
2133  bu_log("%s\n", str);
2134  bu_free(str, "return from rt_pr_tree_str");
2135  }
2136 
2137  /* Build array of sub-tree pointers, one per region, for parallel
2138  * processing below.
2139  */
2140  new_reg_count = db_count_subtree_regions(whole_tree);
2141  reg_trees = (union tree **)bu_calloc(sizeof(union tree *),
2142  (new_reg_count+1), "*reg_trees[]");
2143  new_reg_count = db_tally_subtree_regions(whole_tree, reg_trees, 0,
2144  new_reg_count, resp);
2145 
2146  /* Release storage for tree from whole_tree to leaves.
2147  * db_tally_subtree_regions() duplicated and OP_NOP'ed the
2148  * original top of any sub-trees that it wanted to keep, so
2149  * whole_tree is just the left-over part now.
2150  */
2151  db_free_tree(whole_tree, resp);
2152 
2153  /* As a debugging aid, print out the waiting region names */
2154  if (RT_G_DEBUG&DEBUG_TREEWALK) {
2155  bu_log("%d waiting regions:\n", new_reg_count);
2156  for (i = 0; i < new_reg_count; i++) {
2157  union tree *treep;
2158  struct combined_tree_state *ctsp;
2159  char *str;
2160 
2161  if ((treep = reg_trees[i]) == TREE_NULL) {
2162  bu_log("%d: NULL\n", i);
2163  continue;
2164  }
2165  RT_CK_TREE(treep);
2166  if (treep->tr_op != OP_REGION) {
2167  bu_log("%d: op=%d\n", i, treep->tr_op);
2168  rt_pr_tree(treep, 2);
2169  continue;
2170  }
2171  ctsp = treep->tr_c.tc_ctsp;
2172  RT_CK_CTS(ctsp);
2173  str = db_path_to_string(&(ctsp->cts_p));
2174  bu_log("%d '%s'\n", i, str);
2175  bu_free(str, "path string");
2176  }
2177  bu_log("end of waiting regions\n");
2178  }
2179 
2180  /* Make state available to the threads */
2182  wps.reg_trees = reg_trees;
2183  wps.reg_count = new_reg_count;
2184  wps.reg_current = 0; /* Semaphored */
2185  wps.reg_end_func = reg_end_func;
2186  wps.reg_leaf_func = leaf_func;
2187  wps.client_data = client_data;
2188  wps.rtip = init_state->ts_rtip;
2189 
2190  bu_parallel(_db_walk_dispatcher, ncpu, (void *)&wps);
2191 
2192  /* Clean up any remaining sub-trees still in reg_trees[] */
2193  for (i = 0; i < new_reg_count; i++) {
2194  db_free_tree(reg_trees[i], resp);
2195  }
2196  bu_free((char *)reg_trees, "*reg_trees[]");
2197 
2198  if (something_not_found) {
2199  bu_log ("db_walk_tree: %d %s not found.\n",
2200  something_not_found,
2201  (something_not_found > 1) ? "items" : "item");
2202  return -2;
2203  } else {
2204  return 0; /* OK */
2205  }
2206 }
2207 
2208 
2209 void
2210 db_apply_anims(struct db_full_path *pathp, struct directory *dp, mat_t stack, mat_t arc, struct mater_info *materp)
2211 {
2212  struct animate *anp;
2213  int i, j;
2214 
2215  /* Check here for animation to apply */
2216 
2217  if ((dp->d_animate != ANIM_NULL) && (RT_G_DEBUG & DEBUG_ANIM)) {
2218  char *sofar = db_path_to_string(pathp);
2219  bu_log("Animate %s with...\n", sofar);
2220  bu_free(sofar, "path string");
2221  }
2222 
2223  /*
2224  * For each of the animations attached to the mentioned object,
2225  * see if the current accumulated path matches the path specified
2226  * in the animation. Comparison is performed right-to-left (from
2227  * leafward to rootward).
2228  */
2229  for (anp = dp->d_animate; anp != ANIM_NULL; anp = anp->an_forw) {
2230  int anim_flag;
2231 
2232  j = pathp->fp_len-1;
2233 
2234  RT_CK_ANIMATE(anp);
2235  i = anp->an_path.fp_len-1;
2236  anim_flag = 1;
2237 
2238  if (RT_G_DEBUG & DEBUG_ANIM) {
2239  char *str;
2240 
2241  str = db_path_to_string(&(anp->an_path));
2242  bu_log("\t%s\t", str);
2243  bu_free(str, "path string");
2244  bu_log("an_path.fp_len-1:%d pathp->fp_len-1:%d\n",
2245  i, j);
2246  }
2247 
2248  for (; i >= 0 && j >= 0; i--, j--) {
2249  if (anp->an_path.fp_names[i] != pathp->fp_names[j]) {
2250  if (RT_G_DEBUG & DEBUG_ANIM) {
2251  bu_log("%s != %s\n",
2252  anp->an_path.fp_names[i]->d_namep,
2253  pathp->fp_names[j]->d_namep);
2254  }
2255  anim_flag = 0;
2256  break;
2257  }
2258  }
2259 
2260  /* anim, stack, arc, mater */
2261  if (anim_flag)
2262  db_do_anim(anp, stack, arc, materp);
2263  }
2264  return;
2265 }
2266 
2267 
2268 int
2270  mat_t m, /* result */
2271  struct db_i *dbip,
2272  const char *name,
2273  struct resource *resp)
2274 {
2275  struct db_full_path full_path;
2276  mat_t region_to_model;
2277 
2278  /* get transformation between world and "region" coordinates */
2279  if (db_string_to_path(&full_path, dbip, name)) {
2280  /* bad thing */
2281  bu_log("db_region_mat: db_string_to_path(%s) error\n", name);
2282  return -1;
2283  }
2284  if (!db_path_to_mat(dbip, &full_path, region_to_model, 0, resp)) {
2285  /* bad thing */
2286  bu_log("db_region_mat: db_path_to_mat(%s) error", name);
2287  return -2;
2288  }
2289 
2290  /* get matrix to map points from model (world) space
2291  * to "region" space
2292  */
2293  bn_mat_inv(m, region_to_model);
2294  db_free_full_path(&full_path);
2295  return 0;
2296 }
2297 
2298 
2299 int
2301  mat_t model_to_shader, /* result */
2302  const struct rt_i *rtip,
2303  const struct region *rp,
2304  point_t p_min, /* input/output: shader/region min point */
2305  point_t p_max, /* input/output: shader/region max point */
2306  struct resource *resp)
2307 {
2308  mat_t model_to_region;
2309  mat_t m_xlate;
2310  mat_t m_scale;
2311  mat_t m_tmp;
2312  vect_t v_tmp;
2313  struct rt_i *my_rtip;
2314  char *reg_name;
2315 
2316  RT_CK_RTI(rtip);
2317  RT_CK_RESOURCE(resp);
2318 
2319  reg_name = (char *)bu_calloc(strlen(rp->reg_name), sizeof(char), "rt_shader_mat reg_name");
2320  bu_basename(reg_name, rp->reg_name);
2321  /* get model-to-region space mapping */
2322  if (db_region_mat(model_to_region, rtip->rti_dbip, rp->reg_name, resp) < 0) {
2323  bu_free(reg_name, "reg_name free");
2324  return -1;
2325  }
2326 
2327  if (VEQUAL(p_min, p_max)) {
2328  /* User/shader did not specify bounding box, obtain bounding
2329  * box for un-transformed region
2330  */
2331 
2332  /* XXX This should really be handled by a special set of tree
2333  * walker routines which just build up the RPP of the region.
2334  * For now we just re-use rt_rpp_region() with a scratch rtip.
2335  */
2336  my_rtip = rt_new_rti(rtip->rti_dbip);
2337  my_rtip->useair = rtip->useair;
2338 
2339  /* XXX Should have our own semaphore here */
2341  if (rt_gettree(my_rtip, reg_name)) bu_bomb(rp->reg_name);
2343  rt_rpp_region(my_rtip, reg_name, p_min, p_max);
2344  rt_clean(my_rtip);
2345  }
2346 
2347  /*
2348  * Translate bounding box to origin
2349  */
2350  MAT_IDN(m_xlate);
2351  VSCALE(v_tmp, p_min, -1);
2352  MAT_DELTAS_VEC(m_xlate, v_tmp);
2353  bn_mat_mul(m_tmp, m_xlate, model_to_region);
2354 
2355  /*
2356  * Scale the bounding box to unit cube
2357  */
2358  VSUB2(v_tmp, p_max, p_min);
2359  VINVDIR(v_tmp, v_tmp);
2360  MAT_IDN(m_scale);
2361  MAT_SCALE_VEC(m_scale, v_tmp);
2362  bn_mat_mul(model_to_shader, m_scale, m_tmp);
2363 
2364  bu_free(reg_name, "reg_name free");
2365 
2366  return 0;
2367 }
2368 
2369 
2370 HIDDEN int
2372 {
2373  int len = 0;
2374  const char *str = NULL;
2375  const char *end = NULL;
2376 
2377  if (!vls) return 0;
2378 
2379  /* don't need a space if the string is empty */
2380  len = bu_vls_strlen(vls);
2381  if (len == 0)
2382  return 0;
2383 
2384  /* don't need a space at the start of a (potentially nested) new
2385  * list. backtrack until we're out.
2386  */
2387  str = bu_vls_addr(vls);
2388  end = str + len - 1;
2389  while (end && *end == '{') {
2390  if (end == str) {
2391  return 0;
2392  }
2393  end--;
2394  }
2395 
2396  /* sanity, shouldn't happen */
2397  if (!end) {
2398  return 0;
2399  }
2400 
2401  /* don't need a space if there is already whitespace separation,
2402  * unless it has been escaped.
2403  */
2404  if (isspace((int)*end) && ((end == str) || (*(end-1) != '\\'))) {
2405  return 0;
2406  }
2407 
2408  /* yep, we need space */
2409  return 1;
2410 }
2411 
2412 
2413 HIDDEN void
2415 {
2416  if (!vls) return;
2417 
2418  if (tree_list_needspace(vls)) {
2419  bu_vls_strcat(vls, " {");
2420  } else {
2421  bu_vls_putc(vls, '{');
2422  }
2423 }
2424 
2425 
2426 HIDDEN void
2428 {
2429  if (!vls) return;
2430  bu_vls_putc(vls, '}');
2431 }
2432 
2433 
2434 /* implements a large portion of what Tcl does when appending elements
2435  * to DStrings.
2436  */
2437 HIDDEN void
2438 tree_list_append(struct bu_vls *vls, const char *str)
2439 {
2440  const char *p;
2441  int quoteit = 0;
2442 
2443  if (!vls) return;
2444 
2445  if (!str || strlen(str) == 0) {
2446  str = "{}";
2447  }
2448 
2449  if (tree_list_needspace(vls)) {
2450  bu_vls_putc(vls, ' ');
2451  }
2452 
2453  /* see if we need to quote the string */
2454  for (p = str; *p != '\0'; p++) {
2455  switch (*p) {
2456  case '[':
2457  case '$':
2458  case ';':
2459  case ' ':
2460  case '\f':
2461  case '\n':
2462  case '\r':
2463  case '\t':
2464  case '\v':
2465  quoteit = 1;
2466  break;
2467  }
2468  if (quoteit)
2469  break;
2470  }
2471 
2472  /* already quoted? assumes cleanly balanced braces */
2473  p = str;
2474  if (*p == '{' || *p == '"') {
2475  quoteit = 0;
2476  }
2477 
2478  if (quoteit) {
2480  bu_vls_strcat(vls, str);
2481  tree_list_sublist_end(vls);
2482  } else {
2483  bu_vls_strcat(vls, str);
2484  }
2485 }
2486 
2487 
2488 int
2489 db_tree_list(struct bu_vls *vls, const union tree *tp)
2490 {
2491  int count = 0;
2492 
2493  if (!tp || !vls)
2494  return 0;
2495 
2496  RT_CK_TREE(tp);
2497  switch (tp->tr_op) {
2498  case OP_DB_LEAF:
2499  tree_list_append(vls, "l");
2500  tree_list_append(vls, tp->tr_l.tl_name);
2501  if (tp->tr_l.tl_mat) {
2503  bn_encode_mat(vls, tp->tr_l.tl_mat);
2504  tree_list_sublist_end(vls);
2505  }
2506  count++;
2507  break;
2508 
2509  /* This node is known to be a binary op */
2510  case OP_UNION:
2511  tree_list_append(vls, "u");
2512  goto bin;
2513  case OP_INTERSECT:
2514  tree_list_append(vls, "n");
2515  goto bin;
2516  case OP_SUBTRACT:
2517  tree_list_append(vls, "-");
2518  goto bin;
2519  case OP_XOR:
2520  tree_list_append(vls, "^");
2521  bin:
2523  count += db_tree_list(vls, tp->tr_b.tb_left);
2524  tree_list_sublist_end(vls);
2525 
2527  count += db_tree_list(vls, tp->tr_b.tb_right);
2528  tree_list_sublist_end(vls);
2529  break;
2530 
2531  /* This node is known to be a unary op */
2532  case OP_NOT:
2533  tree_list_append(vls, "!");
2534  goto unary;
2535  case OP_GUARD:
2536  tree_list_append(vls, "G");
2537  goto unary;
2538  case OP_XNOP:
2539  tree_list_append(vls, "X");
2540  unary:
2542  count += db_tree_list(vls, tp->tr_b.tb_left);
2543  tree_list_sublist_end(vls);
2544  break;
2545 
2546  case OP_NOP:
2547  tree_list_append(vls, "N");
2548  break;
2549 
2550  default:
2551  bu_log("db_tree_list: bad op %d\n", tp->tr_op);
2552  bu_bomb("db_tree_list\n");
2553  }
2554 
2555  return count;
2556 }
2557 
2558 
2559 union tree *
2560 db_tree_parse(struct bu_vls *vls, const char *str, struct resource *resp)
2561 {
2562  int argc;
2563  char **argv;
2564  union tree *tp = TREE_NULL;
2565  db_op_t op;
2566 
2567  if (!resp) {
2568  resp = &rt_uniresource;
2569  }
2570  RT_CK_RESOURCE(resp);
2571 
2572  /* Skip over leading spaces in input */
2573  while (*str && isspace((int)*str)) str++;
2574 
2575  /*XXX Temporarily use brlcad_interp until a replacement for Tcl_SplitList is created */
2576  if (Tcl_SplitList(brlcad_interp, str, &argc, (const char ***)&argv) != TCL_OK)
2577  return TREE_NULL;
2578 
2579  if (argc <= 0 || argc > 3) {
2580  bu_vls_printf(vls,
2581  "db_tree_parse: tree node does not have 1, 2 or 3 elements: %s\n",
2582  str);
2583  Tcl_Free((char *)argv); /* not bu_free(), not free() */
2584  return TREE_NULL;
2585  }
2586 
2587  if (argv[0][1] != '\0') {
2588  bu_vls_printf(vls, "db_tree_parse() operator is not single character: %s", argv[0]);
2589  Tcl_Free((char *)argv); /* not bu_free(), not free() */
2590  return TREE_NULL;
2591  }
2592 
2593  op = db_str2op(argv[0]);
2594 
2595  if (op == DB_OP_NULL) {
2596 
2597  /* didn't find a csg operator, so see what other tree element it is */
2598 
2599  switch (argv[0][0]) {
2600  case 'l':
2601  /* Leaf node: {l name {mat}} */
2602  RT_GET_TREE(tp, resp);
2603  tp->tr_op = OP_DB_LEAF;
2604  tp->tr_l.tl_name = bu_strdup(argv[1]);
2605  /* If matrix not specified, NULL pointer ==> identity matrix */
2606  tp->tr_l.tl_mat = NULL;
2607  if (argc == 3) {
2608  mat_t m;
2609  /* decode also recognizes "I" notation for identity */
2610  if (bn_decode_mat(m, argv[2]) != 16) {
2611  bu_vls_printf(vls,
2612  "db_tree_parse: unable to parse matrix '%s' using identity",
2613  argv[2]);
2614  break;
2615  }
2616  if (bn_mat_is_identity(m))
2617  break;
2618  if (bn_mat_ck("db_tree_parse", m)) {
2619  bu_vls_printf(vls,
2620  "db_tree_parse: matrix '%s', does not preserve axis perpendicularity, using identity", argv[2]);
2621  break;
2622  }
2623  /* Finally, a good non-identity matrix, dup & save it */
2624  tp->tr_l.tl_mat = bn_mat_dup(m);
2625  }
2626  break;
2627 
2628  case '!':
2629  /* Unary: not {! {lhs}} */
2630  RT_GET_TREE(tp, resp);
2631  tp->tr_b.tb_op = OP_NOT;
2632  goto unary;
2633  case 'G':
2634  /* Unary: GUARD {G {lhs}} */
2635  RT_GET_TREE(tp, resp);
2636  tp->tr_b.tb_op = OP_GUARD;
2637  goto unary;
2638  case 'X':
2639  /* Unary: XNOP {X {lhs}} */
2640  RT_GET_TREE(tp, resp);
2641  tp->tr_b.tb_op = OP_XNOP;
2642  goto unary;
2643  unary:
2644  if (argv[1] == (char *)NULL) {
2645  bu_vls_printf(vls,
2646  "db_tree_parse: unary operator %s has insufficient operands in %s\n",
2647  argv[0], str);
2648  bu_free((char *)tp, "union tree");
2649  tp = TREE_NULL;
2650  }
2651  tp->tr_b.tb_left = db_tree_parse(vls, argv[1], resp);
2652  if (tp->tr_b.tb_left == TREE_NULL) {
2653  bu_free((char *)tp, "union tree");
2654  tp = TREE_NULL;
2655  }
2656  break;
2657 
2658  case 'N':
2659  /* NOP: no args. {N} */
2660  RT_GET_TREE(tp, resp);
2661  tp->tr_b.tb_op = OP_XNOP;
2662  break;
2663 
2664  default:
2665  bu_vls_printf(vls, "db_tree_parse: unable to interpret operator '%s'\n", argv[1]);
2666  break;
2667  }
2668 
2669  } else {
2670 
2671  /* found a csg operator */
2672 
2673  switch (op) {
2674  default:
2675  case DB_OP_UNION:
2676  /* Binary: Union: {u {lhs} {rhs}} */
2677  RT_GET_TREE(tp, resp);
2678  tp->tr_b.tb_op = OP_UNION;
2679  break;
2680  case DB_OP_INTERSECT:
2681  /* Binary: Intersection */
2682  RT_GET_TREE(tp, resp);
2683  tp->tr_b.tb_op = OP_INTERSECT;
2684  break;
2685  case DB_OP_SUBTRACT:
2686  /* Binary: Union */
2687  RT_GET_TREE(tp, resp);
2688  tp->tr_b.tb_op = OP_SUBTRACT;
2689  break;
2690  }
2691 
2692  if (argv[1] == (char *)NULL || argv[2] == (char *)NULL) {
2693  bu_vls_printf(vls,
2694  "db_tree_parse: binary operator %s has insufficient operands in %s",
2695  argv[0], str);
2696  RT_FREE_TREE(tp, resp);
2697  tp = TREE_NULL;
2698  }
2699  tp->tr_b.tb_left = db_tree_parse(vls, argv[1], resp);
2700  if (tp->tr_b.tb_left == TREE_NULL) {
2701  RT_FREE_TREE(tp, resp);
2702  tp = TREE_NULL;
2703  }
2704  tp->tr_b.tb_right = db_tree_parse(vls, argv[2], resp);
2705  if (tp->tr_b.tb_right == TREE_NULL) {
2706  /* free the left we just tree parsed */
2707  db_free_tree(tp->tr_b.tb_left, resp);
2708  RT_FREE_TREE(tp, resp);
2709  tp = TREE_NULL;
2710  }
2711  }
2712 
2713  /*XXX Temporarily using tcl for its Tcl_SplitList */
2714  Tcl_Free((char *)argv); /* not bu_free(), not free() */
2715  return tp;
2716 }
2717 
2718 
2719 /** @} */
2720 /*
2721  * Local Variables:
2722  * mode: C
2723  * tab-width: 8
2724  * indent-tabs-mode: t
2725  * c-file-style: "stroustrup"
2726  * End:
2727  * ex: shiftwidth=4 tabstop=8
2728  */
union tree *(* ts_leaf_func)(struct db_tree_state *tsp, const struct db_full_path *pathp, struct rt_db_internal *ip, void *client_data)
callback during DAG traversal called on leaf primitive nodes
Definition: raytrace.h:1065
void db_pr_combined_tree_state(const struct combined_tree_state *ctsp)
Definition: db_tree.c:186
int db_count_subtree_regions(const union tree *tp)
Definition: db_tree.c:1705
struct combined_tree_state * db_new_combined_tree_state(const struct db_tree_state *tsp, const struct db_full_path *pathp)
Definition: db_tree.c:111
char * d_namep
pointer to name string
Definition: raytrace.h:859
#define RT_CTS_MAGIC
Definition: magic.h:155
#define DEBUG_REGIONS
7 Print regions & boolean trees
Definition: raytrace.h:90
Definition: raytrace.h:800
int ts_stop_at_regions
else stop at solids
Definition: raytrace.h:1054
void db_add_node_to_full_path(struct db_full_path *pp, struct directory *dp)
Definition: db_fullpath.c:54
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define RT_CHECK_DBI(_p)
Definition: raytrace.h:828
int rt_db_get_internal(struct rt_db_internal *ip, const struct directory *dp, const struct db_i *dbip, const mat_t mat, struct resource *resp)
Definition: dir.c:76
int db_region_mat(mat_t m, struct db_i *dbip, const char *name, struct resource *resp)
Definition: db_tree.c:2269
void db_ck_tree(const union tree *tp)
Definition: db_tree.c:1255
int bn_mat_is_identity(const mat_t m)
Definition: mat.c:980
union tree *(* reg_leaf_func)(struct db_tree_state *, const struct db_full_path *, struct rt_db_internal *, void *)
Definition: db_tree.c:1841
int(* ts_region_start_func)(struct db_tree_state *tsp, const struct db_full_path *pathp, const struct rt_comb_internal *comb, void *client_data)
callback during DAG downward traversal called on region nodes
Definition: raytrace.h:1055
fastf_t C[2 *MAX_CNT+1][2 *MAX_CNT+1]
Definition: dsp_brep.cpp:38
void bu_avs_init_empty(struct bu_attribute_value_set *avp)
Definition: avs.c:36
struct mater_info ts_mater
material properties
Definition: raytrace.h:1047
struct tree::tree_cts tr_c
char region_flag
!0 ==> this COMB is a REGION
Definition: raytrace.h:939
void db_pr_tree_state(const struct db_tree_state *tsp)
Definition: db_tree.c:155
struct nmgregion * td_r
ptr to NMG region
Definition: raytrace.h:1168
void rt_clean(struct rt_i *rtip)
int db_follow_path_for_state(struct db_tree_state *tsp, struct db_full_path *total_path, const char *orig_str, int noisy)
Definition: db_tree.c:839
size_t fp_len
Definition: db_fullpath.h:44
int tb_op
non-leaf
Definition: raytrace.h:1147
void db_dup_full_path(struct db_full_path *newp, const struct db_full_path *oldp)
Definition: db_fullpath.c:87
#define RT_CK_RTI(_p)
Definition: raytrace.h:1833
#define RT_SOLTAB_NULL
Definition: raytrace.h:449
int ts_gmater
GIFT compat material code.
Definition: raytrace.h:1045
#define OP_NOP
Leaf with no effect.
Definition: raytrace.h:1132
float ma_temperature
positive ==> degrees Kelvin
Definition: raytrace.h:523
struct db_tree_state cts_s
Definition: raytrace.h:1116
Definition: clone.c:90
int useair
1="air" regions are retained while prepping
Definition: raytrace.h:1756
void bu_vls_strcat(struct bu_vls *vp, const char *s)
Definition: vls.c:368
#define OP_NMG_TESS
Leaf: tr_stp -> nmgregion.
Definition: raytrace.h:1137
#define OP_XOR
Binary: L xor R, not both.
Definition: raytrace.h:1130
int bu_avs_add(struct bu_attribute_value_set *avp, const char *attribute, const char *value)
Definition: avs.c:78
void db_tree_del_lhs(union tree *tp, struct resource *resp)
Definition: db_tree.c:466
int nmg_kr(struct nmgregion *r)
Definition: nmg_mk.c:1595
void bu_semaphore_acquire(unsigned int i)
Definition: semaphore.c:180
int db_is_tree_all_unions(const union tree *tp)
Definition: db_tree.c:1670
void bu_avs_merge(struct bu_attribute_value_set *dest, const struct bu_attribute_value_set *src)
Definition: avs.c:154
#define ANIM_NULL
Definition: raytrace.h:1354
struct directory * db_lookup(const struct db_i *, const char *name, int noisy)
Definition: db_lookup.c:153
int db_follow_path(struct db_tree_state *tsp, struct db_full_path *total_path, const struct db_full_path *new_path, int noisy, long depth)
Definition: db_tree.c:682
#define RT_CK_COMB(_p)
Definition: raytrace.h:955
struct combined_tree_state * tc_ctsp
Definition: raytrace.h:1162
HIDDEN void tree_list_sublist_begin(struct bu_vls *vls)
Definition: db_tree.c:2414
int db_tally_subtree_regions(union tree *tp, union tree **reg_trees, int cur, int lim, struct resource *resp)
Definition: db_tree.c:1741
Header file for the BRL-CAD common definitions.
#define OP_XNOP
Unary: L, mark region.
Definition: raytrace.h:1136
int ts_los
equivalent LOS estimate
Definition: raytrace.h:1046
#define DB_FULL_PATH_CUR_DIR(_pp)
Definition: db_fullpath.h:51
db_op_t db_str2op(const char *str)
Definition: op.c:31
const char * value
Definition: avs.h:62
const char * reg_name
Identifying string.
Definition: raytrace.h:539
void db_free_db_tree_state(struct db_tree_state *tsp)
Definition: db_tree.c:76
unsigned char rgb[3]
Definition: raytrace.h:948
char ma_color_valid
non-0 ==> ma_color is non-default
Definition: raytrace.h:524
struct db_full_path cts_p
Definition: raytrace.h:1117
uint32_t magic
First word: magic number.
Definition: raytrace.h:1143
HIDDEN union tree * _db_gettree_region_end(struct db_tree_state *tsp, const struct db_full_path *pathp, union tree *curtree, void *client_data)
Definition: db_tree.c:1800
int rt_shader_mat(mat_t model_to_shader, const struct rt_i *rtip, const struct region *rp, point_t p_min, point_t p_max, struct resource *resp)
Definition: db_tree.c:2300
void db_full_path_init(struct db_full_path *pathp)
Definition: db_fullpath.c:40
void rt_pr_tree(const union tree *tp, int lvl)
int db_tree_list(struct bu_vls *vls, const union tree *tp)
Definition: db_tree.c:2489
void rt_free_soltab(struct soltab *stp)
Definition: tree.c:605
int ts_aircode
GIFT compat air code.
Definition: raytrace.h:1044
int db_count_tree_nodes(const union tree *tp, int count)
Definition: db_tree.c:1634
#define HIDDEN
Definition: common.h:86
union tree * tb_left
Definition: raytrace.h:1149
union tree * db_find_named_leaf(union tree *tp, const char *cp)
Definition: db_tree.c:393
struct soltab * tu_stp
Definition: raytrace.h:1156
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
#define OP_FREE
Unary: L has free chain.
Definition: raytrace.h:1140
void db_left_hvy_node(union tree *tp)
Definition: db_tree.c:1404
union tree *(* reg_end_func)(struct db_tree_state *, const struct db_full_path *, union tree *, void *)
Definition: db_tree.c:1840
void db_dup_db_tree_state(struct db_tree_state *otsp, const struct db_tree_state *itsp)
Definition: db_tree.c:46
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
#define OP_SUBTRACT
Binary: L subtract R.
Definition: raytrace.h:1129
struct combined_tree_state * db_dup_combined_tree_state(const struct combined_tree_state *old_ctsp)
Definition: db_tree.c:129
struct bu_attribute_value_set ts_attrs
attribute/value structure
Definition: raytrace.h:1052
void * memset(void *s, int c, size_t n)
void db5_sync_attr_to_comb(struct rt_comb_internal *comb, const struct bu_attribute_value_set *avs, struct directory *dp)
Definition: db5_attr.c:303
#define RT_FREE_TREE(_tp, _res)
Definition: raytrace.h:1232
#define OP_INTERSECT
Binary: L intersect R.
Definition: raytrace.h:1128
struct resource rt_uniresource
default. Defined in librt/globals.c
Definition: globals.c:41
char ma_cinherit
color: DB_INH_LOWER / DB_INH_HIGHER
Definition: raytrace.h:525
HIDDEN int tree_list_needspace(struct bu_vls *vls)
Definition: db_tree.c:2371
#define RT_G_DEBUG
Definition: raytrace.h:1718
db_op_t
Definition: op.h:33
#define OP_DB_LEAF
Leaf of combination, db fmt.
Definition: raytrace.h:1139
void db_init_db_tree_state(struct db_tree_state *tsp, struct db_i *dbip, struct resource *resp)
Definition: db_tree.c:93
union tree * db_tree_parse(struct bu_vls *vls, const char *str, struct resource *resp)
Definition: db_tree.c:2560
void bn_mat_print(const char *title, const mat_t m)
Definition: mat.c:81
struct animate * an_forw
forward link
Definition: raytrace.h:1338
#define RT_CK_DB_INTERNAL(_p)
Definition: raytrace.h:207
struct bu_attribute_value_pair * avp
Definition: avs.h:89
union tree *(* ts_region_end_func)(struct db_tree_state *tsp, const struct db_full_path *pathp, union tree *curtree, void *client_data)
callback during DAG upward traversal called on region nodes
Definition: raytrace.h:1060
#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 RT_CK_DIR(_dp)
Definition: raytrace.h:876
#define RT_DIR_SOLID
this name is a solid
Definition: raytrace.h:883
int db_string_to_path(struct db_full_path *pp, const struct db_i *dbip, const char *str)
Definition: db_fullpath.c:361
struct db_i * ts_dbip
Definition: raytrace.h:1040
#define BU_PTBL_GET(ptbl, i)
Definition: ptbl.h:108
#define RT_DBTS_MAGIC
Definition: magic.h:157
#define RT_DB_INTERNAL_INIT(_p)
Definition: raytrace.h:199
#define TS_SOFAR_INTER
Intersection encountered above.
Definition: raytrace.h:1081
int db_apply_state_from_one_member(struct db_tree_state *tsp, struct db_full_path *pathp, const char *cp, int sofar, const union tree *tp)
Definition: db_tree.c:346
#define LOOKUP_QUIET
Definition: raytrace.h:893
#define bu_strlcpy(dst, src, size)
Definition: str.h:60
void bn_mat_inv(mat_t output, const mat_t input)
#define TREE_NULL
Definition: raytrace.h:1181
void db_free_full_path(struct db_full_path *pp)
Definition: db_fullpath.c:473
mat_t ts_mat
transform matrix
Definition: raytrace.h:1050
void db_tree_del_rhs(union tree *tp, struct resource *resp)
Definition: db_tree.c:512
matp_t tl_mat
xform matp, NULL ==> identity
Definition: raytrace.h:1173
int db_apply_state_from_comb(struct db_tree_state *tsp, const struct db_full_path *pathp, const struct rt_comb_internal *comb)
Definition: db_tree.c:200
#define RT_DIR_PHONY_ADDR
Special marker for d_addr field.
Definition: raytrace.h:879
struct bu_vls shader
Definition: raytrace.h:950
char * ma_shader
shader name & parms
Definition: raytrace.h:527
HIDDEN void _db_walk_subtree(union tree *tp, struct combined_tree_state **region_start_statepp, union tree *(*leaf_func)(struct db_tree_state *, const struct db_full_path *, struct rt_db_internal *, void *), void *client_data, struct resource *resp)
Definition: db_tree.c:1850
#define RT_CK_CTS(_p)
Definition: raytrace.h:1119
struct bu_attribute_value_set idb_avs
Definition: raytrace.h:196
size_t bu_vls_strlen(const struct bu_vls *vp)
Definition: vls.c:189
char * tl_name
Name of this leaf (bu_strdup'ed)
Definition: raytrace.h:1174
#define OP_REGION
Leaf: tr_stp -> combined_tree_state.
Definition: raytrace.h:1131
struct tree::tree_node tr_b
matp_t bn_mat_dup(const mat_t in)
Definition: mat.c:1046
void bu_printb(const char *s, unsigned long v, const char *bits)
#define UNUSED(parameter)
Definition: common.h:239
char * bu_vls_strdup(const struct bu_vls *vp)
Definition: vls.c:274
#define OP_GUARD
Unary: not L, or else!
Definition: raytrace.h:1135
char ma_minherit
mater: DB_INH_LOWER / DB_INH_HIGHER
Definition: raytrace.h:526
int bn_mat_ck(const char *title, const mat_t m)
Definition: mat.c:1058
Definition: joint.h:84
goto out
Definition: nmg_mod.c:3846
void bn_mat_mul(mat_t o, const mat_t a, const mat_t b)
#define NMG_REGION_MAGIC
Definition: magic.h:137
void bu_avs_init(struct bu_attribute_value_set *avp, size_t len, const char *str)
Definition: avs.c:47
struct directory ** fp_names
array of dir pointers
Definition: db_fullpath.h:46
char * db_path_to_string(const struct db_full_path *pp)
Definition: db_fullpath.c:191
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
struct tree::tree_nmgregion tr_d
struct resource * ts_resp
Per-CPU data.
Definition: raytrace.h:1074
void db_non_union_push(union tree *tp, struct resource *resp)
Definition: db_tree.c:1426
void bu_semaphore_release(unsigned int i)
Definition: semaphore.c:218
int db_do_anim(struct animate *anp, mat_t stack, mat_t arc, struct mater_info *materp)
#define DEBUG_ANIM
10 Animation
Definition: raytrace.h:93
#define TS_SOFAR_REGION
Region encountered above.
Definition: raytrace.h:1082
int db_tree_del_dbleaf(union tree **tp, const char *cp, struct resource *resp, int nflag)
Definition: db_tree.c:558
void bu_parallel(void(*func)(int func_ncpu, void *func_data), int ncpu, void *data)
float ma_color[3]
explicit color: 0..1
Definition: raytrace.h:522
struct rt_i * rt_new_rti(struct db_i *dbip)
Definition: prep.c:58
int bn_decode_mat(mat_t m, const char *str)
Support routines for the math functions.
struct db_full_path an_path
(sub)-path pattern
Definition: raytrace.h:1339
int rt_gettree(struct rt_i *rtip, const char *node)
Definition: tree.c:869
#define RT_CK_DBI(_p)
Definition: raytrace.h:829
int rt_rpp_region(struct rt_i *rtip, const char *reg_name, fastf_t *min_rpp, fastf_t *max_rpp)
Definition: bbox.c:148
#define RT_CK_FULL_PATH(_p)
Definition: db_fullpath.h:59
#define DB_CK_WPS(_p)
Definition: db_tree.c:1846
void bu_basename(char *basename, const char *path)
Definition: basename.c:30
#define RT_TREE_MAGIC
Definition: magic.h:171
#define RT_SEM_WORKER
Definition: raytrace.h:1730
int db_apply_state_from_memb(struct db_tree_state *tsp, struct db_full_path *pathp, const union tree *tp)
Definition: db_tree.c:304
struct tree::tree_db_leaf tr_l
union tree * tb_right
Definition: raytrace.h:1150
void * idb_ptr
Definition: raytrace.h:195
#define RT_DIR_COMB
combination
Definition: raytrace.h:884
#define RT_CK_RESOURCE(_p)
Definition: raytrace.h:1490
Definition: op.h:35
#define BU_ASSERT_PTR(_lhs, _relation, _rhs)
Definition: defines.h:227
HIDDEN union tree * _db_gettree_leaf(struct db_tree_state *tsp, const struct db_full_path *pathp, struct rt_db_internal *ip, void *client_data)
Definition: db_tree.c:1817
#define RT_CK_DBTS(_p)
Definition: raytrace.h:1084
struct db_i * rti_dbip
prt to Database instance struct
Definition: raytrace.h:1774
HIDDEN fastf_t bin(fastf_t val, fastf_t step)
Definition: nmg_tri_mc.c:461
#define RT_GET_TREE(_tp, _res)
Definition: raytrace.h:1210
void db_free_tree(union tree *tp, struct resource *resp)
Definition: db_tree.c:1296
union tree * tree
Leading to tree_db_leaf leaves.
Definition: raytrace.h:938
#define RT_CK_SOLTAB(_p)
Definition: raytrace.h:453
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
#define RT_DIR_NULL
Definition: raytrace.h:875
#define LOOKUP_NOISY
Definition: raytrace.h:892
#define DB_WALK_PARALLEL_STATE_MAGIC
Definition: db_tree.c:1845
HIDDEN void tree_list_append(struct bu_vls *vls, const char *str)
Definition: db_tree.c:2438
int ts_is_fastgen
REGION_NON_FASTGEN/_PLATE/_VOLUME.
Definition: raytrace.h:1051
struct rt_i * rtip
Definition: db_tree.c:1842
char * rt_pr_tree_str(const union tree *tree)
Definition: pr.c:460
int db_walk_tree(struct db_i *dbip, int argc, const char **argv, int ncpu, const struct db_tree_state *init_state, int(*reg_start_func)(struct db_tree_state *, const struct db_full_path *, const struct rt_comb_internal *, void *), union tree *(*reg_end_func)(struct db_tree_state *, const struct db_full_path *, union tree *, void *), union tree *(*leaf_func)(struct db_tree_state *, const struct db_full_path *, struct rt_db_internal *, void *), void *client_data)
Definition: db_tree.c:2024
void db_tree_funcleaf(struct db_i *dbip, struct rt_comb_internal *comb, union tree *comb_tree, void(*leaf_func)(struct db_i *, struct rt_comb_internal *, union tree *, void *, void *, void *, void *), void *user_ptr1, void *user_ptr2, void *user_ptr3, void *user_ptr4)
Definition: db_tree.c:640
int cyclic_path(const struct db_full_path *fp, const char *name)
Definition: db_fullpath.c:598
int bu_shader_to_key_eq(const char *in, struct bu_vls *vls)
Definition: parse.c:2279
union tree * db_dup_subtree(const union tree *tp, struct resource *resp)
Definition: db_tree.c:1190
Definition: op.h:34
struct rt_i * ts_rtip
Helper for rt_gettrees()
Definition: raytrace.h:1073
HIDDEN void _db_recurse_subtree(union tree *tp, struct db_tree_state *msp, struct db_full_path *pathp, struct combined_tree_state **region_start_statepp, void *client_data)
Definition: db_tree.c:873
#define RT_CK_ANIMATE(_p)
Definition: raytrace.h:1355
char is_fastgen
REGION_NON_FASTGEN/_PLATE/_VOLUME.
Definition: raytrace.h:940
HIDDEN void tree_list_sublist_end(struct bu_vls *vls)
Definition: db_tree.c:2427
struct animate * d_animate
link to animation
Definition: raytrace.h:865
#define A
Definition: msr.c:51
const char * td_name
If non-null, dynamic string describing heritage of this region.
Definition: raytrace.h:1167
const char * name
Definition: avs.h:61
#define RT_SEM_MODEL
Definition: raytrace.h:1733
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define RT_CK_TREE(_p)
Definition: raytrace.h:1182
#define TS_SOFAR_MINUS
Subtraction encountered above.
Definition: raytrace.h:1080
char rgb_valid
!0 ==> rgb[] has valid color
Definition: raytrace.h:947
int ts_regionid
GIFT compat region ID code.
Definition: raytrace.h:1043
void db_tree_mul_dbleaf(union tree *tp, const mat_t mat)
Definition: db_tree.c:607
#define OP_SOLID
Leaf: tr_stp -> solid.
Definition: raytrace.h:1126
struct bu_ptbl rti_resources
list of 'struct resource's encountered
Definition: raytrace.h:1811
union tree * db_recurse(struct db_tree_state *tsp, struct db_full_path *pathp, struct combined_tree_state **region_start_statepp, void *client_data)
Definition: db_tree.c:972
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
union tree ** reg_trees
Definition: db_tree.c:1837
#define DEBUG_TREEWALK
22 Database tree traversal
Definition: raytrace.h:107
void db_apply_anims(struct db_full_path *pathp, struct directory *dp, mat_t stack, mat_t arc, struct mater_info *materp)
Definition: db_tree.c:2210
int d_flags
flags
Definition: raytrace.h:869
Definition: vls.h:56
int ts_sofar
Flag bits.
Definition: raytrace.h:1041
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
float temperature
0 ==> region temperature
Definition: raytrace.h:949
#define OP_UNION
Binary: L union R.
Definition: raytrace.h:1127
void bu_vls_putc(struct bu_vls *vp, int c)
Definition: vls.c:666
struct animate * dbi_anroot
PRIVATE: heads list of anim at root lvl.
Definition: raytrace.h:821
void bu_avs_free(struct bu_attribute_value_set *avp)
Definition: avs.c:235
#define OP_NOT
Unary: not L.
Definition: raytrace.h:1134
Tcl_Interp * brlcad_interp
Definition: tcl.c:41
HIDDEN void _db_walk_dispatcher(int cpu, void *arg)
Definition: db_tree.c:1950
struct tree::tree_leaf tr_a
void db_free_combined_tree_state(struct combined_tree_state *ctsp)
Definition: db_tree.c:144
void rt_db_free_internal(struct rt_db_internal *ip)
Definition: dir.c:216
#define DB_FULL_PATH_POP(_pp)
Definition: db_fullpath.h:49
int db_path_to_mat(struct db_i *dbip, struct db_full_path *pathp, mat_t mat, int depth, struct resource *resp)
Definition: db_fullpath.c:630
#define bu_strdup(s)
Definition: str.h:71
void bn_encode_mat(struct bu_vls *vp, const mat_t m)
Definition: tcl.c:108
union tree * db_find_named_leafs_parent(int *side, union tree *tp, const char *cp)
Definition: db_tree.c:423
uint32_t magic
Definition: raytrace.h:1039
#define BU_STR_EQUAL(s1, s2)
Definition: str.h:126