00001 #ifndef OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_BINARY_MATCHING_BOTTOM_UP_POLICY_H 00002 #define OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_BINARY_MATCHING_BOTTOM_UP_POLICY_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 00013 #include <OpenTissue/collision/bvh/bottom_up_constructor/bvh_graph.h> 00014 #include <list> 00015 00016 namespace OpenTissue 00017 { 00018 namespace bvh 00019 { 00020 00025 template<typename bvh_type> 00026 class BinaryMatchBottomUpPolicy 00027 { 00028 public: 00029 00030 00031 typedef BVHGraph<bvh_type> graph_type; 00032 typedef typename graph_type::node_ptr_type node_ptr_type; 00033 typedef typename graph_type::edge_ptr_type edge_ptr_type; 00034 typedef typename graph_type::edge_iterator edge_iterator; 00035 typedef typename graph_type::edge_ptr_iterator edge_ptr_iterator; 00036 typedef typename graph_type::node_iterator node_iterator; 00037 typedef typename graph_type::edge_ptr_container edge_ptr_container; 00038 typedef typename graph_type::real_type real_type; 00039 typedef typename bvh_type::volume_type volume_type; 00040 typedef typename bvh_type::geometry_type geometry_type; 00041 00042 protected: 00043 00044 graph_type * m_graph; 00045 edge_ptr_container m_matched; 00046 00047 public: 00048 00057 void init(graph_type & graph) 00058 { 00059 m_graph = &graph; 00060 match_edges(); 00061 } 00062 00071 void update(node_ptr_type /*node*/) 00072 { 00073 if(m_matched.empty()) 00074 match_edges(); 00075 } 00076 00082 edge_ptr_type get_next_edge() 00083 { 00084 edge_ptr_type edge( m_matched.front() ); 00085 m_matched.pop_front(); 00086 return edge; 00087 } 00088 00095 const bool has_more_edges()const { return (m_graph->size_edges()>0); } 00096 00110 bool should_create_bv(node_ptr_type node) 00111 { 00112 bool possible_legal_collapse_exist = false; 00113 00114 edge_iterator edge = node->edge_begin(); 00115 edge_iterator end = node->edge_end(); 00116 for(;edge!=end;++edge) 00117 { 00118 node_ptr_type other = (edge->A() == node)?edge->B():edge->A(); 00119 00120 if(node->size_sub_nodes()+other->size_sub_nodes()<degree()) 00121 possible_legal_collapse_exist = true; 00122 } 00123 if(!possible_legal_collapse_exist) 00124 { 00125 return true; 00126 } 00127 if(node->size_sub_nodes() >= degree()) 00128 return true; 00129 if( (m_graph->size_edges()+1)< degree() ) 00130 return true; 00131 return false; 00132 } 00133 00148 template<typename geometry_iterator,typename volume_iterator> 00149 volume_type fit(geometry_iterator g0,geometry_iterator g1,volume_iterator v0,volume_iterator v1){ return volume_type(); } 00150 00151 protected: 00152 00153 void match_edges() 00154 { 00155 if(m_graph->size_edges()==0) 00156 return; 00157 m_matched.clear(); 00158 00159 { 00160 edge_iterator edge = m_graph->edge_begin(); 00161 edge_iterator end = m_graph->edge_end(); 00162 for(;edge != end; ++edge) 00163 edge->m_tag = 0; 00164 } 00165 { 00166 node_iterator node = m_graph->node_begin(); 00167 node_iterator end = m_graph->node_end(); 00168 for(;node != end; ++node) 00169 node->m_tag2 = node->m_tag = 0; 00170 } 00171 00172 std::list<node_ptr_type> Q; 00173 node_ptr_type first( m_graph->edge_begin()->A() ); 00174 Q.push_back( first ); 00175 00176 while(!Q.empty()) 00177 { 00178 node_ptr_type node( Q.front() ); 00179 Q.pop_front(); 00180 node->m_tag = 1; 00181 00182 edge_ptr_iterator e = node->edge_ptr_begin(); 00183 edge_ptr_iterator end = node->edge_ptr_end(); 00184 for(;e!=end;++e) 00185 { 00186 if( (*e)->m_tag) 00187 continue; 00188 (*e)->m_tag = 1; 00189 node_ptr_type other = ( (*e)->A() == node)? (*e)->B(): (*e)->A(); 00190 if(!other->m_tag) 00191 { 00192 Q.push_back(other); 00193 } 00194 //--- should we match node and other? 00195 if(!node->m_tag2 && !other->m_tag2) 00196 { 00197 node->m_tag2 = 1; 00198 other->m_tag2 = 1; 00199 edge_ptr_type match( *e ); 00200 m_matched.push_back( match ); 00201 } 00202 } 00203 } 00204 } 00205 00218 const unsigned int degree() const { return 2; } 00219 }; 00220 00221 } // namespace bvh 00222 00223 } // namespace OpenTissue 00224 00225 // OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_BINARY_MATCHING_BOTTOM_UP_POLICY_H 00226 #endif
1.7.1