build_bintree.c File Reference

#include <volume_io/internal_volume_io.h>
#include <bicpl/data_structures.h>

Include dependency graph for build_bintree.c:

Go to the source code of this file.

Data Structures
struct	leaf_queue_type
Defines
#define	NODE_VISIT_COST   0.02
#define	NET_CHANGE_THRESHOLD   0.0
#define	FACTOR   1.0e-4
#define	THRESHOLD   30
#define	SWAP(a, b, type)
Functions
typedef	PRIORITY_QUEUE_STRUCT (leaf_queue_type)
private void	subdivide_bintree (bintree_struct_ptr bintree, int max_nodes, int n_objects, range_struct bound_vols[])
private void	get_planes (int axis_index, int n_objects, int list[], range_struct bound_vols[], Real right_plane, Real *left_plane, int *n_left, int *n_overlap, int *n_right)
private Real	find_best_split_node_for_axis (int axis_index, int n_objects, int object_list[], range_struct bound_vols[], range_struct *limits, Real *best_left_plane, Real *best_right_plane)
private void	split_node (range_struct bound_vols[], bintree_node_struct **ptr_to_node, range_struct *limits, int *n_nodes, range_struct *left_limits, Real *left_cost, range_struct *right_limits, Real *right_cost)
private void	create_leaf_queue (leaf_queue_struct *leaf_queue)
private void	delete_leaf_queue (leaf_queue_struct *leaf_queue)
private BOOLEAN	leaf_queue_empty (leaf_queue_struct *leaf_queue)
private void	insert_in_leaf_queue (leaf_queue_struct *leaf_queue, bintree_node_struct **ptr_to_node, Real node_cost, range_struct *limits)
private void	remove_from_leaf_queue (leaf_queue_struct *leaf_queue, bintree_node_struct ***ptr_to_node, range_struct *limits)
private BOOLEAN	node_tightly_bounds_object (range_struct *bound_vol, range_struct *limits)
public void	evaluate_bintree_efficiency (bintree_struct_ptr bintree, Real *avg_nodes_visited, Real *avg_objects_visited)
private void	recursive_efficiency_count (bintree_node_struct *node, range_struct *limits, Real *avg_nodes_visited, Real *avg_objects_visited)
private Real	node_visit_estimation (range_struct *limits)

---

Define Documentation

#define FACTOR   1.0e-4

Referenced by get_prediction_weights_3d(), PRIORITY_QUEUE_STRUCT(), and resample_volume().

#define NET_CHANGE_THRESHOLD   0.0

Definition at line 23 of file build_bintree.c. Referenced by split_node().

#define NODE_VISIT_COST   0.02

Definition at line 22 of file build_bintree.c. Referenced by split_node().

#define SWAP (  a, b, type   )

Value: { \ type _tmp; \ _tmp = (a); \ (a) = (b); \ (b) = _tmp; \ } Definition at line 395 of file build_bintree.c. Referenced by split_node().

#define THRESHOLD   30

Definition at line 309 of file build_bintree.c. Referenced by find_best_split_node_for_axis(), and split_node().

---

Function Documentation

private void create_leaf_queue (  leaf_queue_struct *  leaf_queue  )

Definition at line 606 of file build_bintree.c. References INITIALIZE_PRIORITY_QUEUE. Referenced by subdivide_bintree().

private void delete_leaf_queue (  leaf_queue_struct *  leaf_queue  )

Definition at line 612 of file build_bintree.c. References DELETE_PRIORITY_QUEUE. Referenced by subdivide_bintree().

public void evaluate_bintree_efficiency (  bintree_struct_ptr  bintree, Real *  avg_nodes_visited, Real *  avg_objects_visited )

Definition at line 675 of file build_bintree.c. References node_visit_estimation(), bintree_struct::range, recursive_efficiency_count(), and bintree_struct::root. Referenced by PRIORITY_QUEUE_STRUCT().

private Real find_best_split_node_for_axis (  int  axis_index, int  n_objects, int  object_list[], range_struct  bound_vols[], range_struct *  limits, Real *  best_left_plane, Real *  best_right_plane )

Definition at line 329 of file build_bintree.c. References get_planes(), range_struct::limits, node_visit_estimation(), and THRESHOLD. Referenced by split_node().

private void get_planes (  int  axis_index, int  n_objects, int  list[], range_struct  bound_vols[], Real  right_plane, Real *  left_plane, int *  n_left, int *  n_overlap, int *  n_right )

Definition at line 262 of file build_bintree.c. References FALSE, range_struct::limits, and TRUE. Referenced by find_best_split_node_for_axis().

private void insert_in_leaf_queue (  leaf_queue_struct *  leaf_queue, bintree_node_struct **  ptr_to_node, Real  node_cost, range_struct *  limits )

Definition at line 624 of file build_bintree.c. References INSERT_IN_PRIORITY_QUEUE, leaf_queue_type::limits, and leaf_queue_type::ptr_to_node. Referenced by subdivide_bintree().

private BOOLEAN leaf_queue_empty (  leaf_queue_struct *  leaf_queue  )

Definition at line 618 of file build_bintree.c. References IS_PRIORITY_QUEUE_EMPTY. Referenced by subdivide_bintree().

private BOOLEAN node_tightly_bounds_object (  range_struct *  bound_vol, range_struct *  limits )

Definition at line 655 of file build_bintree.c. References FALSE, range_struct::limits, and TRUE. Referenced by split_node().

private Real node_visit_estimation (  range_struct *  limits  )

Definition at line 750 of file build_bintree.c. References range_surface_area(), and range_volume(). Referenced by evaluate_bintree_efficiency(), find_best_split_node_for_axis(), PRIORITY_QUEUE_STRUCT(), recursive_efficiency_count(), and split_node().

typedef PRIORITY_QUEUE_STRUCT (  leaf_queue_type   )

Definition at line 31 of file build_bintree.c. References evaluate_bintree_efficiency(), FACTOR, initialize_bintree(), node_visit_estimation(), and subdivide_bintree().

private void recursive_efficiency_count (  bintree_node_struct *  node, range_struct *  limits, Real *  avg_nodes_visited, Real *  avg_objects_visited )

Definition at line 697 of file build_bintree.c. References bintree_node_is_leaf(), get_bintree_leaf_objects(), get_bintree_left_child(), get_bintree_right_child(), get_node_split_axis(), get_node_split_position(), range_struct::limits, and node_visit_estimation(). Referenced by evaluate_bintree_efficiency().

private void remove_from_leaf_queue (  leaf_queue_struct *  leaf_queue, bintree_node_struct ***  ptr_to_node, range_struct *  limits )

Definition at line 638 of file build_bintree.c. References leaf_queue_type::limits, leaf_queue_type::ptr_to_node, and REMOVE_FROM_PRIORITY_QUEUE. Referenced by subdivide_bintree().

private void split_node (  range_struct  bound_vols[], bintree_node_struct **  ptr_to_node, range_struct *  limits, int *  n_nodes, range_struct *  left_limits, Real *  left_cost, range_struct *  right_limits, Real *  right_cost )

Definition at line 432 of file build_bintree.c. References create_bintree_internal_node(), create_bintree_leaf(), delete_bintree_node(), FALSE, find_best_split_node_for_axis(), get_bintree_leaf_objects(), get_node_split_position(), range_struct::limits, NET_CHANGE_THRESHOLD, node_tightly_bounds_object(), NODE_VISIT_COST, node_visit_estimation(), SWAP, THRESHOLD, and TRUE. Referenced by subdivide_bintree().

private void subdivide_bintree (  bintree_struct_ptr  bintree, int  max_nodes, int  n_objects, range_struct  bound_vols[] )

Definition at line 180 of file build_bintree.c. References create_bintree_leaf(), create_leaf_queue(), delete_leaf_queue(), FALSE, get_bintree_left_child_ptr(), get_bintree_limits(), get_bintree_right_child_ptr(), insert_in_leaf_queue(), leaf_queue_empty(), remove_from_leaf_queue(), bintree_struct::root, and split_node(). Referenced by PRIORITY_QUEUE_STRUCT().

---