00001 #ifndef OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_DEFAULT_PRIORITY_BOTTOM_UP_POLICY_H 00002 #define OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_DEFAULT_PRIORITY_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 #include <OpenTissue/utility/utility_less_ptr.h> 00013 #include <OpenTissue/collision/bvh/bottom_up_constructor/bvh_graph.h> 00014 #include <OpenTissue/core/math/math_constants.h> 00015 00016 00017 #include <cmath> //Needed for fabs() 00018 00019 namespace OpenTissue 00020 { 00021 namespace bvh 00022 { 00023 00032 template<typename bvh_type> 00033 class DefaultPriorityBottomUpPolicy 00034 { 00035 public: 00036 00037 typedef BVHGraph<bvh_type> graph_type; 00038 typedef typename graph_type::node_ptr_type node_ptr_type; 00039 typedef typename graph_type::edge_ptr_type edge_ptr_type; 00040 typedef typename graph_type::edge_iterator edge_iterator; 00041 typedef typename graph_type::edge_ptr_iterator edge_ptr_iterator; 00042 typedef typename graph_type::real_type real_type; 00043 typedef typename bvh_type::volume_type volume_type; 00044 typedef typename bvh_type::geometry_type geometry_type; 00045 00046 protected: 00047 00048 graph_type * m_graph; 00049 00050 public: 00051 00052 virtual ~DefaultPriorityBottomUpPolicy(){}; 00053 00054 public: 00055 00064 void init(graph_type & graph) 00065 { 00066 m_graph = &graph; 00067 edge_ptr_iterator edge = m_graph->edge_ptr_begin(); 00068 edge_ptr_iterator end = m_graph->edge_ptr_end(); 00069 for(;edge != end; ++edge) 00070 { 00071 edge_ptr_type ptr( *edge ); 00072 ptr->priority() = priority(ptr); 00073 } 00074 update_heap(); 00075 } 00076 00085 void update(node_ptr_type node) 00086 { 00087 edge_ptr_iterator edge = node->edge_ptr_begin(); 00088 edge_ptr_iterator end = node->edge_ptr_end(); 00089 for(; edge!=end; ++edge) 00090 { 00091 edge_ptr_type ptr( *edge ); 00092 ptr->priority() = priority(ptr); 00093 } 00094 update_heap(); 00095 } 00096 00102 edge_ptr_type get_next_edge() const{ return edge_ptr_type( *(m_graph->edge_ptr_begin()) ); } 00103 00110 const bool has_more_edges() const { return (m_graph->size_edges()>0); } 00111 00125 bool should_create_bv(node_ptr_type node){ return ( node->size_sub_nodes() >= degree() || (m_graph->size_edges()+1)< degree() ); } 00126 00141 template<typename geometry_iterator,typename volume_iterator> 00142 volume_type fit(geometry_iterator g0,geometry_iterator g1,volume_iterator v0,volume_iterator v1){ return volume_type(); } 00143 00144 protected: 00145 00153 void update_heap() 00154 { 00155 //--- KE 12-10-2004: STL heap stuff does not work on list-types, unfortuantely 00156 //--- graph edges are stored in a list:-( 00157 //--- 00158 //--- std::make_heap(m_graph->m_edges.begin(),m_graph->m_edges.end(),OpenTissue::utility::less_ptr<edge_type *>()); 00159 //--- std::sort_heap(m_graph->m_edges.begin(),m_graph->m_edges.end(),OpenTissue::utility::less_ptr<edge_type *>()); 00160 //--- 00161 //--- Our solution is simply to apply a brute force sorting, it is 00162 //--- not very efficient, but it will get the job done. 00163 00164 //std::sort(m_graph->edge_ptr_begin(), m_graph->edge_ptr_end(), OpenTissue::utility::less_ptr<edge_ptr_type>()); // TODO can not determine difference_type on iterator???? 00165 m_graph->m_edges.sort(OpenTissue::utility::less_ptr<edge_ptr_type>()); 00166 00167 } 00168 00184 virtual real_type priority(edge_ptr_type edge) 00185 { 00186 using std::fabs; 00187 00188 real_type a = edge->A()->size_subtree(); 00189 real_type b = edge->B()->size_subtree(); 00190 if((edge->A()->size_edges() + edge->B()->size_edges()) == degree()) 00191 { 00192 return 0; 00193 } 00194 if((edge->A()->size_edges() + edge->B()->size_edges()) > degree()) 00195 { 00196 return math::detail::highest<real_type>(); 00197 } 00198 return (a + b + fabs(a - b )); 00199 } 00200 00213 virtual const unsigned int degree() const { return 2; } 00214 00215 }; 00216 00217 } // namespace bvh 00218 00219 } // namespace OpenTissue 00220 00221 // OPENTISSUE_COLLISION_BVH_BOTTOM_UP_CONSTRUCTOR_BVH_DEFAULT_PRIORITY_BOTTOM_UP_POLICY_H 00222 #endif
1.7.1