00001 #ifndef OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_GRAPH_NODE_H 00002 #define OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_GRAPH_NODE_H 00003 // 00004 // OpenTissue Template Library 00005 // - A generic toolbox for physics-based modeling and simulation. 00006 // Copyright (C) 2008 Department of Computer Science, University of Copenhagen. 00007 // 00008 // OTTL is licensed under zlib: http://opensource.org/licenses/zlib-license.php 00009 // 00010 #include <OpenTissue/configuration.h> 00011 00012 #include <OpenTissue/core/math/math_constants.h> 00013 00014 00015 #include <cmath> //Needed for fabs() 00016 #include <list> //Needed for graph data structure: edges, nodes and volumes 00017 #include <iostream> //Needed for debug output. NOTE: we should consider implementing a logging fascility! 00018 00019 namespace OpenTissue 00020 { 00021 namespace bvh 00022 { 00023 00024 template <typename bvh_type> class BVHGraph; 00025 00029 template <typename bvh_type> 00030 class BVHGraphNode 00031 { 00032 public: 00033 00034 friend class BVHGraph<bvh_type>; 00035 00036 public: 00037 00038 typedef typename bvh_type::volume_type volume_type; 00039 typedef typename bvh_type::bv_ptr bv_ptr; 00040 typedef typename bvh_type::bv_ptr_container bv_ptr_container; 00041 typedef typename bvh_type::geometry_container geometry_container; 00042 typedef BVHGraph<bvh_type> graph_type; 00043 typedef typename graph_type::volume_container volume_container; 00044 00045 public: 00046 00047 typedef typename graph_type::edge_ptr_container edge_ptr_container; 00048 typedef typename graph_type::edge_ptr_iterator edge_ptr_iterator; 00049 typedef typename graph_type::const_edge_ptr_iterator const_edge_ptr_iterator; 00050 typedef typename graph_type::edge_iterator edge_iterator; 00051 typedef typename graph_type::const_edge_iterator const_edge_iterator; 00052 00053 edge_iterator edge_begin() { return edge_iterator(m_edges.begin()); } 00054 edge_iterator edge_end() { return edge_iterator(m_edges.end()); } 00055 const_edge_iterator edge_begin() const { return const_edge_iterator(m_edges.begin()); } 00056 const_edge_iterator edge_end() const { return const_edge_iterator(m_edges.end()); } 00057 00058 edge_ptr_iterator edge_ptr_begin() { return m_edges.begin(); } 00059 edge_ptr_iterator edge_ptr_end() { return m_edges.end(); } 00060 const_edge_ptr_iterator edge_ptr_begin() const { return m_edges.begin(); } 00061 const_edge_ptr_iterator edge_ptr_end() const { return m_edges.end(); } 00062 00063 typedef typename graph_type::node_ptr_container node_ptr_container; 00064 typedef typename graph_type::node_ptr_iterator node_ptr_iterator; 00065 typedef typename graph_type::const_node_ptr_iterator const_node_ptr_iterator; 00066 typedef typename graph_type::node_iterator node_iterator; 00067 typedef typename graph_type::const_node_iterator const_node_iterator; 00068 00069 //node_iterator sub_node_begin() { return node_iterator(m_sub_nodes.begin()); } 00070 //node_iterator sub_node_end() { return node_iterator(m_sub_nodes.end()); } 00071 //const_node_iterator sub_node_begin() const { return const_node_iterator(m_sub_nodes.begin()); } 00072 //const_node_iterator sub_node_end() const { return const_node_iterator(m_sub_nodes.end()); } 00073 00074 node_ptr_iterator sub_node_ptr_begin() { return m_sub_nodes.begin(); } 00075 node_ptr_iterator sub_node_ptr_end() { return m_sub_nodes.end(); } 00076 const_node_ptr_iterator sub_node_ptr_begin() const { return m_sub_nodes.begin(); } 00077 const_node_ptr_iterator sub_node_ptr_end() const { return m_sub_nodes.end(); } 00078 00079 protected: 00080 00081 edge_ptr_container m_edges; 00082 node_ptr_container m_sub_nodes; 00083 bv_ptr m_bv; 00084 volume_type m_volume; 00085 unsigned int m_height; 00086 unsigned int m_subtree_size; 00087 geometry_container m_coverage; 00088 00089 public: 00090 00091 unsigned int m_tag; 00092 unsigned int m_tag2; 00093 00094 public: 00095 00096 BVHGraphNode() 00097 : m_bv() 00098 , m_height(0) 00099 , m_subtree_size(0) 00100 {} 00101 00102 public: 00103 00109 void create_bv(bvh_type & bvh,bool const & annotated = false) 00110 { 00111 bv_ptr_container children; 00112 get_sub_node_BVs(children); 00113 m_bv = bvh.insert(children,annotated); 00114 ++m_subtree_size; 00115 m_bv->volume() = m_volume; 00116 if(size_sub_nodes()) 00117 m_height = max_sub_node_height() + 1; 00118 else 00119 m_height = 0; 00120 } 00121 00122 bv_ptr const & bv() const {return m_bv;} 00123 const unsigned int height()const{return m_height; } 00124 00125 const unsigned int size_subtree()const{ return m_subtree_size; } 00126 const unsigned int size_edges()const{ return static_cast<unsigned int>(m_edges.size()); } 00127 const unsigned int size_sub_nodes()const{ return static_cast<unsigned int>(m_sub_nodes.size()); } 00128 00129 geometry_container const & coverage() const { return m_coverage; } 00130 geometry_container & coverage(){ return m_coverage; } 00131 00132 volume_type & volume() 00133 { 00134 if(m_bv) 00135 return m_bv->volume(); 00136 return m_volume; 00137 } 00138 00139 const unsigned int max_sub_node_height() const 00140 { 00141 using std::max; 00142 unsigned int max_height = 0; 00143 const_node_iterator node = m_sub_nodes.begin(); 00144 const_node_iterator end = m_sub_nodes.end(); 00145 for(; node!=end; ++node) 00146 max_height = max(max_height, node->m_height); 00147 return max_height; 00148 } 00149 00150 const unsigned int min_sub_node_height()const 00151 { 00152 using std::min; 00153 00154 if(m_sub_nodes.empty()) 00155 return 0; 00156 unsigned int min_height = math::detail::highest<unsigned int>(); 00157 const_node_iterator node = m_sub_nodes.begin(); 00158 const_node_iterator end = m_sub_nodes.end(); 00159 for(; node!=end; ++node) 00160 min_height = min(min_height, node->m_height); 00161 return min_height; 00162 } 00163 00164 void get_sub_node_BVs(bv_ptr_container & bvs) 00165 { 00166 bvs.clear(); 00167 const_node_iterator node( m_sub_nodes.begin() ); 00168 const_node_iterator end( m_sub_nodes.end() ); 00169 for(; node != end; ++node) 00170 bvs.push_back(node->m_bv); 00171 } 00172 00173 void get_volumes(volume_container & volumes) 00174 { 00175 volumes.clear(); 00176 const_node_iterator node( m_sub_nodes.begin() ); 00177 const_node_iterator end( m_sub_nodes.end() ); 00178 for(; node != end; ++node) 00179 if(node->m_bv) 00180 volumes.push_back((node->volume())); 00181 } 00182 00183 }; 00184 00185 } // namespace bvh 00186 00187 } // namespace OpenTissue 00188 00189 // OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_GRAPH_NODE_H 00190 #endif
1.7.1