BRL-CAD
Loading...
Searching...
No Matches
tree.h
Go to the documentation of this file.
1/* T R E E . H
2 * BRL-CAD
3 *
4 * Copyright (c) 1993-2025 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/** @file rt/tree.h
21 *
22 */
23
24#ifndef RT_TREE_H
25#define RT_TREE_H
26
27#include "common.h"
28#include "vmath.h"
29#include "bu/avs.h"
30#include "bu/magic.h"
31#include "bu/malloc.h"
32#include "bn/tol.h"
33#include "rt/geom.h"
34#include "rt/defines.h"
35#include "rt/db_instance.h"
36#include "rt/directory.h"
37#include "rt/mater.h"
38#include "rt/op.h"
39#include "rt/region.h"
40#include "rt/soltab.h"
41#include "rt/tol.h"
42#include "nmg.h"
43
45
46union tree; /* forward declaration */
47struct resource; /* forward declaration */
48struct rt_i; /* forward declaration */
49struct rt_comb_internal; /* forward declaration */
50struct rt_db_internal; /* forward declaration */
51
52/**
53 * State for database tree walker db_walk_tree() and related
54 * user-provided handler routines.
55 */
58 struct db_i * ts_dbip;
59 int ts_sofar; /**< @brief Flag bits */
60
61 int ts_regionid; /**< @brief GIFT compat region ID code*/
62 int ts_aircode; /**< @brief GIFT compat air code */
63 int ts_gmater; /**< @brief GIFT compat material code */
64 int ts_los; /**< @brief equivalent LOS estimate */
65 struct mater_info ts_mater; /**< @brief material properties */
66
67 /* FIXME: ts_mat should be a matrix pointer, not a matrix */
68 mat_t ts_mat; /**< @brief transform matrix */
69 int ts_is_fastgen; /**< @brief REGION_NON_FASTGEN/_PLATE/_VOLUME */
70 struct bu_attribute_value_set ts_attrs; /**< @brief attribute/value structure */
72 int ts_stop_at_regions; /**< @brief else stop at solids */
74 const struct db_full_path *pathp,
75 const struct rt_comb_internal *comb,
76 void *client_data
77 ); /**< @brief callback during DAG downward traversal called on region nodes */
78 union tree * (*ts_region_end_func)(struct db_tree_state *tsp,
79 const struct db_full_path *pathp,
80 union tree *curtree,
81 void *client_data
82 ); /**< @brief callback during DAG upward traversal called on region nodes */
83 union tree * (*ts_leaf_func)(struct db_tree_state *tsp,
84 const struct db_full_path *pathp,
85 struct rt_db_internal *ip,
86 void *client_data
87 ); /**< @brief callback during DAG traversal called on leaf primitive nodes */
88 const struct bg_tess_tol * ts_ttol; /**< @brief Tessellation tolerance */
89 const struct bn_tol * ts_tol; /**< @brief Math tolerance */
90 struct model ** ts_m; /**< @brief ptr to ptr to NMG "model" */
91 struct rt_i * ts_rtip; /**< @brief Helper for rt_gettrees() */
92 struct resource * ts_resp; /**< @brief Per-CPU data */
93};
94#define RT_DBTS_INIT_ZERO { RT_DBTS_MAGIC, NULL, 0, 0, 0, 0, 0, RT_MATER_INFO_INIT_ZERO, MAT_INIT_ZERO, 0, BU_AVS_INIT_ZERO, 0, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL }
95/* from mged_initial_tree_state */
96#define RT_DBTS_INIT_IDN { RT_DBTS_MAGIC, NULL, 0, 0, 0, 0, 100, RT_MATER_INFO_INIT_IDN, MAT_INIT_IDN, 0, BU_AVS_INIT_ZERO, 0, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL }
98/* Used to replace old rt_initial_tree_state global */
99#define RT_DBTS_INIT(_p) do { \
100 (_p)->magic = RT_DBTS_MAGIC; \
101 (_p)->ts_dbip = NULL; \
102 (_p)->ts_sofar = 0; \
103 (_p)->ts_regionid = 0; \
104 (_p)->ts_aircode = 0; \
105 (_p)->ts_gmater = 0; \
106 (_p)->ts_los = 0; \
107 VSETALL((_p)->ts_mater.ma_color, 1.0); \
108 (_p)->ts_mater.ma_temperature = -1.0; \
109 (_p)->ts_mater.ma_color_valid = 0; \
110 (_p)->ts_mater.ma_cinherit = DB_INH_LOWER; \
111 (_p)->ts_mater.ma_minherit = DB_INH_LOWER; \
112 (_p)->ts_mater.ma_shader = NULL; \
113 MAT_IDN((_p)->ts_mat); \
114 (_p)->ts_is_fastgen = 0; \
115 BU_AVS_INIT(&(_p)->ts_attrs); \
116 (_p)->ts_stop_at_regions = 0; \
117 (_p)->ts_region_start_func = NULL; \
118 (_p)->ts_region_end_func = NULL; \
119 (_p)->ts_leaf_func = NULL; \
120 (_p)->ts_ttol = NULL; \
121 (_p)->ts_tol = NULL; \
122 (_p)->ts_m = NULL; \
123 (_p)->ts_rtip = NULL; \
124 (_p)->ts_resp = NULL; \
125} while (0)
126
127#define TS_SOFAR_MINUS 1 /**< @brief Subtraction encountered above */
128#define TS_SOFAR_INTER 2 /**< @brief Intersection encountered above */
129#define TS_SOFAR_REGION 4 /**< @brief Region encountered above */
131#define RT_CK_DBTS(_p) BU_CKMAG(_p, RT_DBTS_MAGIC, "db_tree_state")
133/**
134 * State for database traversal functions.
135 */
136struct db_traverse
139 struct db_i *dbip;
141 struct db_i *,
142 struct directory *,
143 void *);
145 struct db_i *,
146 struct directory *,
147 void *);
148 void (*leaf_func) (
149 struct db_i *,
150 struct directory *,
151 void *);
152 struct resource *resp;
155#define RT_DB_TRAVERSE_INIT(_p) {(_p)->magic = RT_DB_TRAVERSE_MAGIC; \
156 (_p)->dbip = ((void *)0); (_p)->comb_enter_func = ((void *)0); \
157 (_p)->comb_exit_func = ((void *)0); (_p)->leaf_func = ((void *)0); \
158 (_p)->resp = ((void *)0); (_p)->client_data = ((void *)0);}
159#define RT_CK_DB_TRAVERSE(_p) BU_CKMAG(_p, RT_DB_TRAVERSE_MAGIC, "db_traverse")
161struct combined_tree_state {
166#define RT_CK_CTS(_p) BU_CKMAG(_p, RT_CTS_MAGIC, "combined_tree_state")
168union tree {
169 uint32_t magic; /**< @brief First word: magic number */
170 /* Second word is always OP code */
171 struct tree_node {
173 int tb_op; /**< @brief non-leaf */
174 struct region *tb_regionp; /**< @brief ptr to containing region */
175 union tree *tb_left;
178 struct tree_leaf {
180 int tu_op; /**< @brief leaf, OP_SOLID */
181 struct region *tu_regionp; /**< @brief ptr to containing region */
182 struct soltab *tu_stp;
184 struct tree_cts {
186 int tc_op; /**< @brief leaf, OP_REGION */
187 struct region *tc_pad; /**< @brief unused */
192 int td_op; /**< @brief leaf, OP_TESS */
193 const char *td_name; /**< @brief If non-null, dynamic string describing heritage of this region */
194 struct nmgregion *td_r; /**< @brief ptr to NMG region */
195 void *td_d; /**< @brief tessellation related data */
196 struct rt_db_internal *td_i; /**< @brief For special cases like half spaces */
200 int tl_op; /**< @brief leaf, OP_DB_LEAF */
201 matp_t tl_mat; /**< @brief xform matp, NULL ==> identity */
202 char *tl_name; /**< @brief Name of this leaf (bu_strdup'ed) */
205/* Things which are in the same place in both A & B structures */
206#define tr_op tr_a.tu_op
207#define tr_regionp tr_a.tu_regionp
209#define TREE_NULL ((union tree *)0)
210#define RT_CK_TREE(_p) BU_CKMAG(_p, RT_TREE_MAGIC, "union tree")
212/**
213 * initialize a union tree to zero without a node operation set. Use
214 * the largest union so all values are effectively zero except for the
215 * magic number.
216 */
217#define RT_TREE_INIT(_p) { \
218 (_p)->magic = RT_TREE_MAGIC; \
219 (_p)->tr_b.tb_op = 0; \
220 (_p)->tr_b.tb_regionp = NULL; \
221 (_p)->tr_b.tb_left = NULL; \
222 (_p)->tr_b.tb_right = NULL; \
223 }
224
225/**
226 * flattened version of the union tree
227 */
228struct rt_tree_array
230 union tree *tl_tree;
231 int tl_op;
233
234#define TREE_LIST_NULL ((struct tree_list *)0)
236#ifdef USE_OPENCL
237/**
238 * Flattened version of the infix union tree.
239 */
240#define UOP_UNION 1 /**< @brief Binary: L union R */
241#define UOP_INTERSECT 2 /**< @brief Binary: L intersect R */
242#define UOP_SUBTRACT 3 /**< @brief Binary: L subtract R */
243#define UOP_XOR 4 /**< @brief Binary: L xor R, not both*/
244#define UOP_NOT 5 /**< @brief Unary: not L */
245#define UOP_GUARD 6 /**< @brief Unary: not L, or else! */
246#define UOP_XNOP 7 /**< @brief Unary: L, mark region */
247
248#define UOP_SOLID 0 /**< @brief Leaf: tr_stp -> solid */
249
250/**
251 * bit expr tree representation
252 *
253 * node:
254 * uint uop : 3
255 * uint right_child : 29
256 *
257 * leaf:
258 * uint uop : 3
259 * uint st_bit : 29
260 */
261struct bit_tree {
262 unsigned val;
263};
264
265struct cl_tree_bit {
266 cl_uint val;
267};
268
269/* Print a bit expr tree */
270RT_EXPORT extern void rt_pr_bit_tree(const struct bit_tree *btp,
271 int idx,
272 int lvl);
273
274RT_EXPORT extern void rt_bit_tree(struct bit_tree *btp,
275 const union tree *tp,
276 size_t *len);
277#endif
278
279/* Print an expr tree */
280RT_EXPORT extern void rt_pr_tree(const union tree *tp,
281 int lvl);
282RT_EXPORT extern void rt_pr_tree_vls(struct bu_vls *vls,
283 const union tree *tp);
284RT_EXPORT extern char *rt_pr_tree_str(const union tree *tree);
286struct partition; /* forward declaration */
287RT_EXPORT extern void rt_pr_tree_val(const union tree *tp,
288 const struct partition *partp,
289 int pr_name,
290 int lvl);
291
292/**
293 * Duplicate the contents of a db_tree_state structure, including a
294 * private copy of the ts_mater field(s) and the attribute/value set.
295 */
297 const struct db_tree_state *itsp);
298
299/**
300 * Release dynamic fields inside the structure, but not the structure
301 * itself.
302 */
303RT_EXPORT extern void db_free_db_tree_state(struct db_tree_state *tsp);
305/**
306 * In most cases, you don't want to use this routine, you want to
307 * struct copy mged_initial_tree_state or use RT_DBTS_INIT, and
308 * then set ts_dbip in your copy.
309 */
310RT_EXPORT extern void db_init_db_tree_state(struct db_tree_state *tsp,
311 struct db_i *dbip,
312 struct resource *resp);
314 const struct db_full_path *pathp);
317RT_EXPORT extern void db_pr_tree_state(const struct db_tree_state *tsp);
320/**
321 * Handle inheritance of material property found in combination
322 * record. Color and the material property have separate inheritance
323 * interlocks.
324 *
325 * Returns -
326 * -1 failure
327 * 0 success
328 * 1 success, this is the top of a new region.
329 */
331 const struct db_full_path *pathp,
332 const struct rt_comb_internal *comb);
333
334/**
335 * The search stops on the first match.
336 *
337 * Returns -
338 * tp if found
339 * TREE_NULL if not found in this tree
340 */
341RT_EXPORT extern union tree *db_find_named_leaf(union tree *tp, const char *cp);
343/**
344 * The search stops on the first match.
345 *
346 * Returns -
347 * TREE_NULL if not found in this tree
348 * tp if found
349 * *side == 1 if leaf is on lhs.
350 * *side == 2 if leaf is on rhs.
351 *
352 */
354 union tree *tp,
355 const char *cp);
356RT_EXPORT extern void db_tree_del_lhs(union tree *tp,
357 struct resource *resp);
358RT_EXPORT extern void db_tree_del_rhs(union tree *tp,
359 struct resource *resp);
360
361/**
362 * Given a name presumably referenced in a OP_DB_LEAF node, delete
363 * that node, and the operation node that references it. Not that
364 * this may not produce an equivalent tree, for example when rewriting
365 * (A - subtree) as (subtree), but that will be up to the caller/user
366 * to adjust. This routine gets rid of exactly two nodes in the tree:
367 * leaf, and op. Use some other routine if you wish to kill the
368 * entire rhs below "-" and "intersect" nodes.
369 *
370 * The two nodes deleted will have their memory freed.
371 *
372 * If the tree is a single OP_DB_LEAF node, the leaf is freed and *tp
373 * is set to NULL.
374 *
375 * Returns -
376 * -3 Internal error
377 * -2 Tree is empty
378 * -1 Unable to find OP_DB_LEAF node specified by 'cp'.
379 * 0 OK
380 */
381RT_EXPORT extern int db_tree_del_dbleaf(union tree **tp,
382 const char *cp,
383 struct resource *resp,
384 int nflag);
385
386/**
387 * Multiply on the left every matrix found in a DB_LEAF node in a
388 * tree.
389 */
390RT_EXPORT extern void db_tree_mul_dbleaf(union tree *tp,
391 const mat_t mat);
392
393/**
394 * This routine traverses a combination (union tree) in LNR order and
395 * calls the provided function for each OP_DB_LEAF node. Note that
396 * this routine does not go outside this one combination!!!!
397 *
398 * was previously named comb_functree()
399 */
400RT_EXPORT extern void db_tree_funcleaf(struct db_i *dbip,
402 union tree *comb_tree,
403 void (*leaf_func)(struct db_i *, struct rt_comb_internal *, union tree *,
404 void *, void *, void *, void *),
405 void * user_ptr1,
406 void * user_ptr2,
407 void * user_ptr3,
408 void * user_ptr4);
409
410/**
411 * Starting with possible prior partial path and corresponding
412 * accumulated state, follow the path given by "new_path", updating
413 * *tsp and *total_path with full state information along the way. In
414 * a better world, there would have been a "combined_tree_state" arg.
415 *
416 * Parameter 'depth' controls how much of 'new_path' is used:
417 *
418 * 0 use all of new_path
419 * >0 use only this many of the first elements of the path
420 * <0 use all but this many path elements.
421 *
422 * A much more complete version of rt_plookup() and pathHmat(). There
423 * is also a TCL interface.
424 *
425 * Returns -
426 * 0 success (plus *tsp is updated)
427 * -1 error (*tsp values are not useful)
428 */
429RT_EXPORT extern int db_follow_path(struct db_tree_state *tsp,
431 const struct db_full_path *new_path,
432 int noisy,
433 long pdepth);
434
435/**
436 * Follow the slash-separated path given by "cp", and update *tsp and
437 * *total_path with full state information along the way.
438 *
439 * A much more complete version of rt_plookup().
440 *
441 * TODO - need to extend this to support specifiers orig_str to
442 * call out particular instances of combs in a tree...
443 *
444 * Returns -
445 * 0 success (plus *tsp is updated)
446 * -1 error (*tsp values are not useful)
447 */
449 struct db_full_path *pathp,
450 const char *orig_str, int noisy);
451
452RT_EXPORT extern union tree *db_dup_subtree(const union tree *tp,
453 struct resource *resp);
454RT_EXPORT extern void db_ck_tree(const union tree *tp);
455
457/**
458 * Release all storage associated with node 'tp', including children
459 * nodes.
460 */
461RT_EXPORT extern void db_free_tree(union tree *tp,
462 struct resource *resp);
464
465/**
466 * Re-balance this node to make it left heavy. Union operators will
467 * be moved to left side. when finished "tp" MUST still point to top
468 * node of this subtree.
469 */
470RT_EXPORT extern void db_left_hvy_node(union tree *tp);
471
473/**
474 * If there are non-union operations in the tree, above the region
475 * nodes, then rewrite the tree so that the entire tree top is nothing
476 * but union operations, and any non-union operations are clustered
477 * down near the region nodes.
478 */
479RT_EXPORT extern void db_non_union_push(union tree *tp,
480 struct resource *resp);
482/**
483 * Return a count of the number of "union tree" nodes below "tp",
484 * including tp.
485 */
486RT_EXPORT extern int db_count_tree_nodes(const union tree *tp,
487 int count);
489
490/**
491 * Returns -
492 * 1 if this tree contains nothing but union operations.
493 * 0 if at least one subtraction or intersection op exists.
494 */
495RT_EXPORT extern int db_is_tree_all_unions(const union tree *tp);
496RT_EXPORT extern int db_count_subtree_regions(const union tree *tp);
499 int cur,
500 int lim,
501 struct resource *resp);
502
503/**
504 * This is the top interface to the "tree walker."
505 *
506 * Parameters:
507 * rtip rt_i structure to database (open with rt_dirbuild())
508 * argc # of tree-tops named
509 * argv names of tree-tops to process
510 * init_state Input parameter: initial state of the tree.
511 * For example: rt_initial_tree_state,
512 * and mged_initial_tree_state.
513 *
514 * These parameters are pointers to callback routines. If NULL, they
515 * won't be called.
516 *
517 * reg_start_func Called at beginning of each region, before
518 * visiting any nodes within the region. Return
519 * 0 if region should be skipped without
520 * recursing, otherwise non-zero. DO NOT USE FOR
521 * OTHER PURPOSES! For example, can be used to
522 * quickly skip air regions.
523 *
524 * reg_end_func Called after all nodes within a region have been
525 * recursively processed by leaf_func. If it
526 * wants to retain 'curtree' then it may steal
527 * that pointer and return TREE_NULL. If it
528 * wants us to clean up some or all of that tree,
529 * then it returns a non-null (union tree *)
530 * pointer, and that tree is safely freed in a
531 * non-parallel section before we return.
532 *
533 * leaf_func Function to process a leaf node. It is actually
534 * invoked from db_recurse() from
535 * _db_walk_subtree(). Returns (union tree *)
536 * representing the leaf, or TREE_NULL if leaf
537 * does not exist or has an error.
538 *
539 *
540 * This routine will employ multiple CPUs if asked, but is not
541 * multiply-parallel-recursive. Call this routine with ncpu > 1 from
542 * serial code only. When called from within an existing thread, ncpu
543 * must be 1.
544 *
545 * If ncpu > 1, the caller is responsible for making sure that
546 * RTG.rtg_parallel is non-zero.
547 *
548 * Plucks per-cpu resources out of rtip->rti_resources[]. They need
549 * to have been initialized first.
550 *
551 * Returns -
552 * -1 Failure to prepare even a single sub-tree
553 * 0 OK
554 */
555RT_EXPORT extern int db_walk_tree(struct db_i *dbip,
556 int argc,
557 const char **argv,
558 int ncpu,
559 const struct db_tree_state *init_state,
560 int (*reg_start_func) (struct db_tree_state * /*tsp*/,
561 const struct db_full_path * /*pathp*/,
562 const struct rt_comb_internal * /* combp */,
563 void *client_data),
564 union tree *(*reg_end_func) (struct db_tree_state * /*tsp*/,
565 const struct db_full_path * /*pathp*/,
566 union tree * /*curtree*/,
567 void *client_data),
568 union tree *(*leaf_func) (struct db_tree_state * /*tsp*/,
569 const struct db_full_path * /*pathp*/,
570 struct rt_db_internal * /*ip*/,
571 void *client_data),
572 void *client_data);
573
574/**
575 * Fills a bu_vls with a representation of the given tree appropriate
576 * for processing by Tcl scripts.
577 *
578 * A tree 't' is represented in the following manner:
579 *
580 * t := { l dbobjname { mat } }
581 * | { l dbobjname }
582 * | { u t1 t2 }
583 * | { n t1 t2 }
584 * | { - t1 t2 }
585 * | { ^ t1 t2 }
586 * | { ! t1 }
587 * | { G t1 }
588 * | { X t1 }
589 * | { N }
590 * | {}
591 *
592 * where 'dbobjname' is a string containing the name of a database object,
593 * 'mat' is the matrix preceding a leaf,
594 * 't1', 't2' are trees (recursively defined).
595 *
596 * Notice that in most cases, this tree will be grossly unbalanced.
597 */
598RT_EXPORT extern int db_tree_list(struct bu_vls *vls, const union tree *tp);
599
600/**
601 * Take a TCL-style string description of a binary tree, as produced
602 * by db_tree_list(), and reconstruct the in-memory form of that tree.
603 */
604RT_EXPORT extern union tree *db_tree_parse(struct bu_vls *vls, const char *str, struct resource *resp);
605
606/**
607 * This subroutine is called for a no-frills tree-walk, with the
608 * provided subroutines being called at every combination and leaf
609 * (solid) node, respectively.
610 *
611 * This routine is recursive, so no variables may be declared static.
612 */
613RT_EXPORT extern void db_functree(struct db_i *dbip,
614 struct directory *dp,
615 void (*comb_func)(struct db_i *,
616 struct directory *,
617 void *),
618 void (*leaf_func)(struct db_i *,
619 struct directory *,
620 void *),
621 struct resource *resp,
622 void *client_data);
623/**
624 * Ray Tracing library database tree walker.
625 *
626 * Collect and prepare regions and solids for subsequent ray-tracing.
627 *
628 */
629
630
631/**
632 * Calculate the bounding RPP of the region whose boolean tree is
633 * 'tp'. The bounding RPP is returned in tree_min and tree_max, which
634 * need not have been initialized first.
635 *
636 * Returns -
637 * 0 success
638 * -1 failure (tree_min and tree_max may have been altered)
639 */
640RT_EXPORT extern int rt_bound_tree(const union tree *tp,
643
644/**
645 * Eliminate any references to NOP nodes from the tree. It is safe to
646 * use db_free_tree() here, because there will not be any dead solids.
647 * They will all have been converted to OP_NOP nodes by
648 * _rt_tree_kill_dead_solid_refs(), previously, so there is no need to
649 * worry about multiple db_free_tree()'s repeatedly trying to free one
650 * solid that has been instanced multiple times.
651 *
652 * Returns -
653 * 0 this node is OK.
654 * -1 request caller to kill this node
655 */
656RT_EXPORT extern int rt_tree_elim_nops(union tree *,
657 struct resource *resp);
659/**
660 * Return count of number of leaf nodes in this tree.
661 */
662RT_EXPORT extern size_t db_tree_nleaves(const union tree *tp);
663
664/**
665 * Take a binary tree in "V4-ready" layout (non-unions pushed below
666 * unions, left-heavy), and flatten it into an array layout, ready for
667 * conversion back to the GIFT-inspired V4 database format.
668 *
669 * This is done using the db_non_union_push() routine.
670 *
671 * If argument 'free' is non-zero, then the non-leaf nodes are freed
672 * along the way, to prevent memory leaks. In this case, the caller's
673 * copy of 'tp' will be invalid upon return.
674 *
675 * When invoked at the very top of the tree, the op argument must be
676 * OP_UNION.
677 */
678RT_EXPORT extern struct rt_tree_array *db_flatten_tree(struct rt_tree_array *rt_tree_array, union tree *tp, int op, int avail, struct resource *resp);
679
681/**
682 * Produce a GIFT-compatible listing, one "member" per line,
683 * regardless of the structure of the tree we've been given.
684 */
685RT_EXPORT extern void db_tree_flatten_describe(struct bu_vls *vls,
686 const union tree *tp,
688 int lvl,
689 double mm2local,
690 struct resource *resp);
691
692RT_EXPORT extern void db_tree_describe(struct bu_vls *vls,
693 const union tree *tp,
695 int lvl,
696 double mm2local);
697
698/**
699 * Support routine for db_ck_v4gift_tree().
700 * Ensure that the tree below 'tp' is left-heavy, i.e. that there are
701 * nothing but solids on the right side of any binary operations.
702 *
703 * Returns -
704 * -1 ERROR
705 * 0 OK
706 */
707RT_EXPORT extern int db_ck_left_heavy_tree(const union tree *tp,
708 int no_unions);
709/**
710 * Look a gift-tree in the mouth.
711 *
712 * Ensure that this boolean tree conforms to the GIFT convention that
713 * union operations must bind the loosest.
714 *
715 * There are two stages to this check:
716 * 1) Ensure that if unions are present they are all at the root of tree,
717 * 2) Ensure non-union children of union nodes are all left-heavy
718 * (nothing but solid nodes permitted on rhs of binary operators).
719 *
720 * Returns -
721 * -1 ERROR
722 * 0 OK
723 */
724RT_EXPORT extern int db_ck_v4gift_tree(const union tree *tp);
725
726/**
727 * Given a rt_tree_array array, build a tree of "union tree" nodes
728 * appropriately connected together. Every element of the
729 * rt_tree_array array used is replaced with a TREE_NULL. Elements
730 * which are already TREE_NULL are ignored. Returns a pointer to the
731 * top of the tree.
732 */
734 size_t howfar,
735 struct resource *resp);
736
737RT_EXPORT extern union tree *db_mkgift_tree(struct rt_tree_array *trees,
738 size_t subtreecount,
739 struct resource *resp);
740
741
742RT_EXPORT extern void rt_optim_tree(union tree *tp,
743 struct resource *resp);
745
746
747
748
749/*************************************************************************
750 * Deprecated
751 *************************************************************************/
752
753
754/**
755 * Updates state via *tsp, pushes member's directory entry on *pathp.
756 * (Caller is responsible for popping it).
757 *
758 * Returns -
759 * -1 failure
760 * 0 success, member pushed on path
761 *
762 * DEPRECATED, internal implementation function
763 */
765 struct db_full_path *pathp,
766 const union tree *tp);
767
768/**
769 * Returns -
770 * -1 found member, failed to apply state
771 * 0 unable to find member 'cp'
772 * 1 state applied OK
773 *
774 * DEPRECATED, internal implementation function
775 */
777 struct db_full_path *pathp,
778 const char *cp,
779 int sofar,
780 const union tree *tp);
781
782/**
783 * Recurse down the tree, finding all the leaves (or finding just all
784 * the regions).
785 *
786 * ts_region_start_func() is called to permit regions to be skipped.
787 * It is not intended to be used for collecting state.
788 *
789 * DEPRECATED, internal implementation function
790 */
791RT_EXPORT extern union tree *db_recurse(struct db_tree_state *tsp,
792 struct db_full_path *pathp,
794 void *client_data);
795
796
797
799
800#endif /* RT_TREE_H */
801
802/*
803 * Local Variables:
804 * tab-width: 8
805 * mode: C
806 * indent-tabs-mode: t
807 * c-file-style: "stroustrup"
808 * End:
809 * ex: shiftwidth=4 tabstop=8
810 */
Definition dvec.h:74
Header file for the BRL-CAD common definitions.
fastf_t vect_t[ELEMENTS_PER_VECT]
3-tuple vector
Definition vmath.h:349
fastf_t mat_t[ELEMENTS_PER_MAT]
4x4 matrix
Definition vmath.h:370
Global registry of recognized magic numbers.
Definition tol.h:72
Definition vls.h:53
struct db_full_path cts_p
Definition tree.h:165
struct db_tree_state cts_s
Definition tree.h:164
uint32_t magic
Definition tree.h:163
void(* comb_exit_func)(struct db_i *, struct directory *, void *)
Definition tree.h:145
void * client_data
Definition tree.h:154
void(* leaf_func)(struct db_i *, struct directory *, void *)
Definition tree.h:149
uint32_t magic
Definition tree.h:139
struct db_i * dbip
Definition tree.h:140
struct resource * resp
Definition tree.h:153
void(* comb_enter_func)(struct db_i *, struct directory *, void *)
Definition tree.h:141
int ts_los
equivalent LOS estimate
Definition tree.h:64
struct mater_info ts_mater
material properties
Definition tree.h:65
const struct bg_tess_tol * ts_ttol
Tessellation tolerance.
Definition tree.h:89
int ts_is_fastgen
REGION_NON_FASTGEN/_PLATE/_VOLUME.
Definition tree.h:70
struct resource * ts_resp
Per-CPU data.
Definition tree.h:93
struct rt_i * ts_rtip
Helper for rt_gettrees()
Definition tree.h:92
int ts_sofar
Flag bits.
Definition tree.h:59
uint32_t magic
Definition tree.h:57
int ts_regionid
GIFT compat region ID code.
Definition tree.h:61
struct bu_attribute_value_set ts_attrs
attribute/value structure
Definition tree.h:71
const struct bn_tol * ts_tol
Math tolerance.
Definition tree.h:90
struct db_i * ts_dbip
Definition tree.h:58
struct model ** ts_m
ptr to ptr to NMG "model"
Definition tree.h:91
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 tree.h:74
int ts_aircode
GIFT compat air code.
Definition tree.h:62
mat_t ts_mat
transform matrix
Definition tree.h:69
int ts_stop_at_regions
else stop at solids
Definition tree.h:73
int ts_gmater
GIFT compat material code.
Definition tree.h:63
NMG topological model.
Definition topology.h:289
NMG topological region.
Definition topology.h:277
int tl_op
Definition tree.h:232
union tree * tl_tree
Definition tree.h:231
int tc_op
leaf, OP_REGION
Definition tree.h:187
struct region * tc_pad
unused
Definition tree.h:188
uint32_t magic
Definition tree.h:186
struct combined_tree_state * tc_ctsp
Definition tree.h:189
int tl_op
leaf, OP_DB_LEAF
Definition tree.h:201
uint32_t magic
Definition tree.h:200
char * tl_name
Name of this leaf (bu_strdup'ed)
Definition tree.h:203
matp_t tl_mat
xform matp, NULL ==> identity
Definition tree.h:202
uint32_t magic
Definition tree.h:180
struct soltab * tu_stp
Definition tree.h:183
int tu_op
leaf, OP_SOLID
Definition tree.h:181
struct region * tu_regionp
ptr to containing region
Definition tree.h:182
union tree * tb_left
Definition tree.h:176
uint32_t magic
Definition tree.h:173
int tb_op
non-leaf
Definition tree.h:174
union tree * tb_right
Definition tree.h:177
struct region * tb_regionp
ptr to containing region
Definition tree.h:175
struct rt_db_internal * td_i
For special cases like half spaces.
Definition tree.h:197
const char * td_name
If non-null, dynamic string describing heritage of this region.
Definition tree.h:194
void * td_d
tessellation related data
Definition tree.h:196
struct nmgregion * td_r
ptr to NMG region
Definition tree.h:195
int td_op
leaf, OP_TESS
Definition tree.h:193
void db_tree_del_lhs(union tree *tp, struct resource *resp)
union tree * db_find_named_leaf(union tree *tp, const char *cp)
int db_follow_path_for_state(struct db_tree_state *tsp, struct db_full_path *pathp, const char *orig_str, int noisy)
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 *client_data), union tree *(*reg_end_func)(struct db_tree_state *, const struct db_full_path *, union tree *, void *client_data), union tree *(*leaf_func)(struct db_tree_state *, const struct db_full_path *, struct rt_db_internal *, void *client_data), void *client_data)
void db_pr_tree_state(const struct db_tree_state *tsp)
int db_apply_state_from_memb(struct db_tree_state *tsp, struct db_full_path *pathp, const union tree *tp)
struct combined_tree_state * db_dup_combined_tree_state(const struct combined_tree_state *old)
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 pdepth)
void rt_pr_tree_val(const union tree *tp, const struct partition *partp, int pr_name, int lvl)
int db_tally_subtree_regions(union tree *tp, union tree **reg_trees, int cur, int lim, struct resource *resp)
void db_pr_combined_tree_state(const struct combined_tree_state *ctsp)
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)
union tree * db_mkbool_tree(struct rt_tree_array *rt_tree_array, size_t howfar, struct resource *resp)
void db_free_combined_tree_state(struct combined_tree_state *ctsp)
union tree * db_dup_subtree(const union tree *tp, struct resource *resp)
int db_ck_v4gift_tree(const union tree *tp)
struct combined_tree_state * db_new_combined_tree_state(const struct db_tree_state *tsp, const struct db_full_path *pathp)
struct rt_tree_array * db_flatten_tree(struct rt_tree_array *rt_tree_array, union tree *tp, int op, int avail, struct resource *resp)
union tree * db_recurse(struct db_tree_state *tsp, struct db_full_path *pathp, struct combined_tree_state **region_start_statepp, void *client_data)
void db_non_union_push(union tree *tp, struct resource *resp)
int db_is_tree_all_unions(const union tree *tp)
void db_tree_flatten_describe(struct bu_vls *vls, const union tree *tp, int indented, int lvl, double mm2local, struct resource *resp)
void db_init_db_tree_state(struct db_tree_state *tsp, struct db_i *dbip, struct resource *resp)
void db_ck_tree(const union tree *tp)
void rt_pr_tree_vls(struct bu_vls *vls, const union tree *tp)
void db_tree_del_rhs(union tree *tp, struct resource *resp)
int rt_tree_elim_nops(union tree *, struct resource *resp)
void db_functree(struct db_i *dbip, struct directory *dp, void(*comb_func)(struct db_i *, struct directory *, void *), void(*leaf_func)(struct db_i *, struct directory *, void *), struct resource *resp, void *client_data)
void rt_optim_tree(union tree *tp, struct resource *resp)
void db_free_db_tree_state(struct db_tree_state *tsp)
char * rt_pr_tree_str(const union tree *tree)
void db_left_hvy_node(union tree *tp)
int db_tree_del_dbleaf(union tree **tp, const char *cp, struct resource *resp, int nflag)
void db_dup_db_tree_state(struct db_tree_state *otsp, const struct db_tree_state *itsp)
union tree * db_tree_parse(struct bu_vls *vls, const char *str, struct resource *resp)
int db_count_tree_nodes(const union tree *tp, int count)
int db_apply_state_from_comb(struct db_tree_state *tsp, const struct db_full_path *pathp, const struct rt_comb_internal *comb)
void db_tree_mul_dbleaf(union tree *tp, const mat_t mat)
int rt_bound_tree(const union tree *tp, vect_t tree_min, vect_t tree_max)
union tree * db_find_named_leafs_parent(int *side, union tree *tp, const char *cp)
size_t db_tree_nleaves(const union tree *tp)
void rt_pr_tree(const union tree *tp, int lvl)
union tree * db_mkgift_tree(struct rt_tree_array *trees, size_t subtreecount, struct resource *resp)
int db_tree_list(struct bu_vls *vls, const union tree *tp)
int db_ck_left_heavy_tree(const union tree *tp, int no_unions)
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)
void db_free_tree(union tree *tp, struct resource *resp)
int db_count_subtree_regions(const union tree *tp)
void db_tree_describe(struct bu_vls *vls, const union tree *tp, int indented, int lvl, double mm2local)
Definition tree.h:169
struct tree::tree_cts tr_c
struct tree::tree_node tr_b
uint32_t magic
First word: magic number.
Definition tree.h:170
struct tree::tree_leaf tr_a
struct tree::tree_tessellation tr_d
struct tree::tree_db_leaf tr_l
fundamental vector, matrix, quaternion math macros