BRL-CAD
#include "common.h"
#include <stddef.h>
#include <math.h>
#include <string.h>
#include "bio.h"
#include "bu/parallel.h"
#include "vmath.h"
#include "bn.h"
#include "db.h"
#include "raytrace.h"
#include "mater.h"
Include dependency graph for tree.c:

Go to the source code of this file.

Macros

#define ACQUIRE_SEMAPHORE_TREE(_hash)
 
#define RELEASE_SEMAPHORE_TREE(_hash)
 

Functions

HIDDEN void _rt_tree_region_assign (union tree *tp, const struct region *regionp)
 
HIDDEN int _rt_gettree_region_start (struct db_tree_state *tsp, const struct db_full_path *pathp, const struct rt_comb_internal *combp, void *client_data)
 
HIDDEN union tree_rt_gettree_region_end (struct db_tree_state *tsp, const struct db_full_path *pathp, union tree *curtree, void *client_data)
 
HIDDEN struct soltab_rt_find_identical_solid (const matp_t mat, struct directory *dp, struct rt_i *rtip)
 
HIDDEN union tree_rt_gettree_leaf (struct db_tree_state *tsp, const struct db_full_path *pathp, struct rt_db_internal *ip, void *client_data)
 
void rt_free_soltab (struct soltab *stp)
 
void _rt_tree_kill_dead_solid_refs (union tree *tp)
 
int rt_gettrees_muves (struct rt_i *rtip, const char **attrs, int argc, const char **argv, int ncpus)
 
int rt_gettrees_and_attrs (struct rt_i *rtip, const char **attrs, int argc, const char **argv, int ncpus)
 
int rt_gettree (struct rt_i *rtip, const char *node)
 
int rt_gettrees (struct rt_i *rtip, int argc, const char **argv, int ncpus)
 
int rt_tree_elim_nops (union tree *tp, struct resource *resp)
 
struct soltabrt_find_solid (const struct rt_i *rtip, const char *name)
 
void rt_optim_tree (union tree *tp, struct resource *resp)
 

Detailed Description

Ray Tracing library database tree walker.

Collect and prepare regions and solids for subsequent ray-tracing.

Definition in file tree.c.

Macro Definition Documentation

#define ACQUIRE_SEMAPHORE_TREE (   _hash)
Value:
switch ((_hash)&03) { \
case 0: \
break; \
case 1: \
break; \
case 2: \
break; \
default: \
break; \
}
#define RT_SEM_TREE1
Definition: raytrace.h:1727
#define RT_SEM_TREE0
Definition: raytrace.h:1726
void bu_semaphore_acquire(unsigned int i)
Definition: semaphore.c:180
#define RT_SEM_TREE2
Definition: raytrace.h:1728
#define RT_SEM_TREE3
Definition: raytrace.h:1729

Definition at line 38 of file tree.c.

Referenced by _rt_find_identical_solid(), _rt_gettree_leaf(), and rt_free_soltab().

#define RELEASE_SEMAPHORE_TREE (   _hash)
Value:
switch ((_hash)&03) { \
case 0: \
break; \
case 1: \
break; \
case 2: \
break; \
default: \
break; \
}
#define RT_SEM_TREE1
Definition: raytrace.h:1727
#define RT_SEM_TREE0
Definition: raytrace.h:1726
#define RT_SEM_TREE2
Definition: raytrace.h:1728
void bu_semaphore_release(unsigned int i)
Definition: semaphore.c:218
#define RT_SEM_TREE3
Definition: raytrace.h:1729

Definition at line 53 of file tree.c.

Referenced by _rt_find_identical_solid(), _rt_gettree_leaf(), and rt_free_soltab().

Function Documentation

HIDDEN void _rt_tree_region_assign ( union tree tp,
const struct region regionp 
)

Definition at line 70 of file tree.c.

References bu_bomb(), OP_GUARD, OP_INTERSECT, OP_NOP, OP_NOT, OP_SOLID, OP_SUBTRACT, OP_UNION, OP_XNOP, OP_XOR, RT_CK_REGION, RT_CK_TREE, tree::tree_node::tb_left, tree::tree_node::tb_regionp, tree::tree_node::tb_right, tree::tr_a, tree::tr_b, and tree::tree_leaf::tu_regionp.

Referenced by rt_gettrees_muves().

Here is the call graph for this function:

HIDDEN int _rt_gettree_region_start ( struct db_tree_state tsp,
const struct db_full_path pathp,
const struct rt_comb_internal combp,
void *  client_data 
)

This routine must be prepared to run in parallel.

Definition at line 108 of file tree.c.

References RT_CHECK_COMB, RT_CK_FULL_PATH, RT_CK_RESOURCE, RT_CK_RTI, rt_i::rti_air_discards, db_tree_state::ts_aircode, db_tree_state::ts_resp, db_tree_state::ts_rtip, and rt_i::useair.

Referenced by rt_gettrees_muves().

HIDDEN union tree* _rt_gettree_region_end ( struct db_tree_state tsp,
const struct db_full_path pathp,
union tree curtree,
void *  client_data 
)

This routine will be called by db_walk_tree() once all the solids in this region have been visited.

This routine must be prepared to run in parallel. As a result, note that the details of the solids pointed to by the soltab pointers in the tree may not be filled in when this routine is called (due to the way multiple instances of solids are handled). Therefore, everything which referred to the tree has been moved out into the serial section. (_rt_tree_region_assign, rt_bound_tree)

Definition at line 138 of file tree.c.

References region::attr_values, bn_mat_inv(), BU_ALLOC, bu_avs_add(), BU_AVS_FOR, bu_avs_free(), bu_avs_get(), bu_avs_init_empty(), bu_calloc(), BU_LIST_INSERT, bu_log(), bu_semaphore_acquire(), bu_semaphore_release(), bu_strdup, directory::d_uses, db5_get_attributes(), DB_FULL_PATH_CUR_DIR, db_is_tree_all_unions(), db_path_to_string(), DEBUG_REGIONS, DEBUG_TREEWALK, rt_i::HeadRegion, region::l, mater_info::ma_color_valid, mater_info::ma_shader, bu_list::magic, bu_attribute_value_pair::name, rt_i::nregions, OP_NOP, region::reg_aircode, region::reg_all_unions, region::reg_bit, region::reg_gmater, region::reg_instnum, region::reg_is_fastgen, region::reg_los, region::reg_mater, region::reg_mfuncs, region::reg_name, region::reg_regionid, region::reg_treetop, region::reg_udata, RT_CK_DBI, RT_CK_FULL_PATH, RT_CK_RESOURCE, RT_CK_RTI, RT_CK_TREE, RT_G_DEBUG, rt_pr_tree(), rt_region_color_map(), RT_REGION_MAGIC, RT_SEM_RESULTS, TREE_NULL, db_tree_state::ts_aircode, db_tree_state::ts_attrs, db_tree_state::ts_dbip, db_tree_state::ts_gmater, db_tree_state::ts_is_fastgen, db_tree_state::ts_los, db_tree_state::ts_mat, db_tree_state::ts_mater, db_tree_state::ts_regionid, db_tree_state::ts_resp, and db_tree_state::ts_rtip.

Referenced by rt_gettrees_muves().

Here is the call graph for this function:

HIDDEN struct soltab* _rt_find_identical_solid ( const matp_t  mat,
struct directory dp,
struct rt_i rtip 
)

See if solid "dp" as transformed by "mat" already exists in the soltab list. If it does, return the matching stp, otherwise, create a new soltab structure, enroll it in the list, and return a pointer to that.

"mat" will be a null pointer when an identity matrix is signified. This greatly speeds the comparison process.

The two cases can be distinguished by the fact that stp->st_id will be 0 for a new soltab structure, and non-zero for an existing one.

This routine will run in parallel.

In order to avoid a race between searching the soltab list and adding new solids to it, the new solid to be added must be enrolled in the list before exiting the critical section.

To limit the size of the list to be searched, there are many lists. The selection of which list is determined by the hash value computed from the solid's name. This is the same optimization used in searching the directory lists.

This subroutine is the critical bottleneck in parallel tree walking.

It is safe, and much faster, to use several different critical sections when searching different lists.

There are only 4 dedicated semaphores defined, TREE0 through TREE3. This unfortunately limits the code to having only 4 CPUs doing list searching at any one time. Hopefully, this is enough parallelism to keep the rest of the CPUs doing I/O and actual solid prepping.

Since the algorithm has been reduced from an O((nsolid/128)**2) search on the entire rti_solidheads[hash] list to an O(ninstance) search on the dp->d_use_head list for this one solid, the critical section should be relatively short-lived. Having the 3-way split should provide ample opportunity for parallelism through here, while still ensuring that the necessary variables are protected.

There are two critical variables which both need to be protected: the specific rti_solidhead[hash] list head, and the specific dp->d_use_hd list head. Fortunately, since the selection of critical section is based upon db_dirhash(dp->d_namep), any other processor that wants to search this same 'dp' will get the same hash as the current thread, and will thus wait for the appropriate semaphore to be released. Similarly, any other thread that wants to search the same rti_solidhead[hash] list as the current thread will be using the same hash, and will thus wait for the proper semaphore.

Definition at line 306 of file tree.c.

References ACQUIRE_SEMAPHORE_TREE, bn_mat_is_equal(), BU_ALLOC, BU_LIST_FOR, BU_LIST_INSERT, BU_LIST_MAIN_PTR, bu_log(), bu_malloc(), bu_ptbl_init(), bu_semaphore_acquire(), bu_semaphore_release(), directory::d_namep, directory::d_use_hd, directory::d_uses, db_dirhash(), DEBUG_SOLIDS, soltab::l, soltab::l2, bu_list::magic, rt_i::nsolids, RELEASE_SEMAPHORE_TREE, RT_CK_DIR, RT_CK_RTI, RT_CK_SOLTAB, RT_G_DEBUG, RT_SEM_STATS, RT_SOLTAB2_MAGIC, RT_SOLTAB_MAGIC, RT_SOLTAB_NULL, rt_i::rti_dont_instance, rt_i::rti_solidheads, rt_i::rti_tol, soltab::st_aradius, soltab::st_bit, soltab::st_dp, soltab::st_matp, soltab::st_regions, soltab::st_rtip, and soltab::st_uses.

Referenced by _rt_gettree_leaf().

Here is the call graph for this function:

HIDDEN union tree* _rt_gettree_leaf ( struct db_tree_state tsp,
const struct db_full_path pathp,
struct rt_db_internal ip,
void *  client_data 
)
void _rt_tree_kill_dead_solid_refs ( union tree tp)

Convert any references to "dead" solids into NOP nodes.

Definition at line 651 of file tree.c.

References bu_log(), directory::d_namep, DEBUG_TREEWALK, OP_GUARD, OP_INTERSECT, OP_NOP, OP_NOT, OP_SOLID, OP_SUBTRACT, OP_UNION, OP_XNOP, OP_XOR, RT_CK_SOLTAB, RT_CK_TREE, rt_free_soltab(), RT_G_DEBUG, SOLTAB_NULL, soltab::st_aradius, soltab::st_dp, tree::tree_node::tb_left, tree::tree_node::tb_right, tree::tr_a, tree::tr_b, and tree::tree_leaf::tu_stp.

Referenced by rt_gettrees_muves().

Here is the call graph for this function: