|
moab
|
00001 00006 #ifndef MOAB_ADAPTIVE_KD_TREE_HPP 00007 #define MOAB_ADAPTIVE_KD_TREE_HPP 00008 00009 #include "moab/Types.hpp" 00010 #include "moab/Tree.hpp" 00011 00012 #include <string> 00013 #include <vector> 00014 #include <math.h> 00015 00016 namespace moab { 00017 00018 class AdaptiveKDTreeIter; 00019 class Interface; 00020 class Range; 00021 00022 class AdaptiveKDTree : public Tree 00023 { 00024 public: 00025 00026 AdaptiveKDTree( Interface* iface); 00027 00036 AdaptiveKDTree(Interface* iface, const Range &entities, 00037 EntityHandle *tree_root_set = NULL, FileOptions *opts = NULL); 00038 00039 ~AdaptiveKDTree(); 00040 00046 ErrorCode parse_options(FileOptions &options); 00047 00061 virtual ErrorCode build_tree(const Range& entities, 00062 EntityHandle *tree_root_set = NULL, 00063 FileOptions *options = NULL); 00064 00066 virtual ErrorCode reset_tree(); 00067 00086 virtual ErrorCode point_search(const double *point, 00087 EntityHandle& leaf_out, 00088 const double iter_tol = 1.0e-10, 00089 const double inside_tol = 1.0e-6, 00090 bool *multiple_leaves = NULL, 00091 EntityHandle *start_node = NULL, 00092 CartVect *params = NULL); 00093 00112 ErrorCode point_search(const double *point, 00113 AdaptiveKDTreeIter& leaf_it, 00114 const double iter_tol = 1.0e-10, 00115 const double inside_tol = 1.0e-6, 00116 bool *multiple_leaves = NULL, 00117 EntityHandle *start_node = NULL); 00118 00134 virtual ErrorCode distance_search(const double *point, 00135 const double distance, 00136 std::vector<EntityHandle>& leaves_out, 00137 const double iter_tol = 1.0e-10, 00138 const double inside_tol = 1.0e-6, 00139 std::vector<double> *dists_out = NULL, 00140 std::vector<CartVect> *params_out = NULL, 00141 EntityHandle *start_node = NULL); 00142 00143 ErrorCode get_info(EntityHandle root, 00144 double min[3], double max[3], 00145 unsigned int &dep); 00146 00148 enum Axis { X = 0, Y = 1, Z = 2 }; 00149 00151 struct Plane { 00152 double coord; 00153 int norm; 00154 00156 bool left_side( const double point[3] ) { 00157 return point[norm] < coord; 00158 } 00160 bool right_side( const double point[3] ) { 00161 return point[norm] > coord; 00162 } 00164 double distance( const double point[3] ) const { 00165 return fabs(point[norm] - coord); 00166 } 00167 }; 00168 00170 ErrorCode get_split_plane( EntityHandle node, Plane& plane ); 00171 00173 ErrorCode set_split_plane( EntityHandle node, const Plane& plane ); 00174 00176 ErrorCode get_tree_iterator( EntityHandle tree_root, 00177 AdaptiveKDTreeIter& result ); 00178 00180 ErrorCode get_last_iterator( EntityHandle tree_root, 00181 AdaptiveKDTreeIter& result ); 00182 00184 ErrorCode get_sub_tree_iterator( EntityHandle tree_root, 00185 const double box_min[3], 00186 const double box_max[3], 00187 AdaptiveKDTreeIter& result ); 00188 00191 ErrorCode split_leaf( AdaptiveKDTreeIter& leaf, Plane plane ); 00192 00195 ErrorCode split_leaf( AdaptiveKDTreeIter& leaf, 00196 Plane plane, 00197 EntityHandle& left_child, 00198 EntityHandle& right_child ); 00201 ErrorCode split_leaf( AdaptiveKDTreeIter& leaf, 00202 Plane plane, 00203 const Range& left_entities, 00204 const Range& right_entities ); 00205 00208 ErrorCode split_leaf( AdaptiveKDTreeIter& leaf, 00209 Plane plane, 00210 const std::vector<EntityHandle>& left_entities, 00211 const std::vector<EntityHandle>& right_entities ); 00212 00216 ErrorCode merge_leaf( AdaptiveKDTreeIter& iter ); 00217 00222 ErrorCode closest_triangle( EntityHandle tree_root, 00223 const double from_coords[3], 00224 double closest_point_out[3], 00225 EntityHandle& triangle_out ); 00226 00227 ErrorCode sphere_intersect_triangles( EntityHandle tree_root, 00228 const double center[3], 00229 double radius, 00230 std::vector<EntityHandle>& triangles ); 00231 00232 ErrorCode ray_intersect_triangles( EntityHandle tree_root, 00233 const double tolerance, 00234 const double ray_unit_dir[3], 00235 const double ray_base_pt[3], 00236 std::vector<EntityHandle>& triangles_out, 00237 std::vector<double>& distance_out, 00238 int result_count_limit = 0, 00239 double distance_limit = -1.0); 00240 00241 ErrorCode compute_depth( EntityHandle root, 00242 unsigned int& min_depth, 00243 unsigned int& max_depth ); 00244 00246 enum CandidatePlaneSet { 00248 SUBDIVISION=0, 00250 SUBDIVISION_SNAP, // = 1 00252 VERTEX_MEDIAN, // = 2 00254 VERTEX_SAMPLE // = 3 00255 }; 00256 00258 virtual ErrorCode print(); 00259 00260 private: 00261 friend class AdaptiveKDTreeIter; 00262 00263 ErrorCode init(); 00264 00266 ErrorCode find_close_triangle( EntityHandle root, 00267 const double from_point[3], 00268 double pt[3], 00269 EntityHandle& triangle ); 00270 00271 ErrorCode make_tag( Interface* iface, std::string name, TagType storage, 00272 DataType type, int count, void* default_val, Tag& tag_handle, 00273 std::vector<Tag>& created_tags ); 00274 00275 ErrorCode intersect_children_with_elems( 00276 const Range& elems, 00277 AdaptiveKDTree::Plane plane, 00278 double eps, 00279 CartVect box_min, 00280 CartVect box_max, 00281 Range& left_tris, 00282 Range& right_tris, 00283 Range& both_tris, 00284 double& metric_value ); 00285 00286 ErrorCode best_subdivision_snap_plane( int num_planes, 00287 const AdaptiveKDTreeIter& iter, 00288 Range& best_left, 00289 Range& best_right, 00290 Range& best_both, 00291 AdaptiveKDTree::Plane& best_plane, 00292 std::vector<double>& tmp_data, 00293 double eps ); 00294 00295 ErrorCode best_subdivision_plane( int num_planes, 00296 const AdaptiveKDTreeIter& iter, 00297 Range& best_left, 00298 Range& best_right, 00299 Range& best_both, 00300 AdaptiveKDTree::Plane& best_plane, 00301 double eps ); 00302 00303 ErrorCode best_vertex_median_plane( int num_planes, 00304 const AdaptiveKDTreeIter& iter, 00305 Range& best_left, 00306 Range& best_right, 00307 Range& best_both, 00308 AdaptiveKDTree::Plane& best_plane, 00309 std::vector<double>& coords, 00310 double eps); 00311 00312 ErrorCode best_vertex_sample_plane( int num_planes, 00313 const AdaptiveKDTreeIter& iter, 00314 Range& best_left, 00315 Range& best_right, 00316 Range& best_both, 00317 AdaptiveKDTree::Plane& best_plane, 00318 std::vector<double>& coords, 00319 std::vector<EntityHandle>& indices, 00320 double eps ); 00321 00322 static const char *treeName; 00323 00324 Tag planeTag, axisTag; 00325 00326 unsigned splitsPerDir; 00327 00328 CandidatePlaneSet planeSet; 00329 }; 00330 00331 00333 class AdaptiveKDTreeIter 00334 { 00335 public: 00336 00337 enum Direction { LEFT = 0, RIGHT = 1 }; 00338 00339 private: 00340 00341 struct StackObj { 00342 StackObj( EntityHandle e, double c ) : entity(e), coord(c) {} 00343 StackObj() {} 00344 EntityHandle entity; 00345 double coord; 00346 }; 00347 00348 enum { BMIN = 0, BMAX = 1 }; 00349 00350 CartVect mBox[2]; 00351 AdaptiveKDTree* treeTool; 00352 std::vector<StackObj> mStack; 00353 mutable std::vector<EntityHandle> childVect; 00354 00357 ErrorCode step_to_first_leaf( Direction direction ); 00358 00359 friend class AdaptiveKDTree; 00360 public: 00361 00362 AdaptiveKDTreeIter() : treeTool(0), childVect(2) {} 00363 00364 ErrorCode initialize( AdaptiveKDTree* tool, 00365 EntityHandle root, 00366 const double box_min[3], 00367 const double box_max[3], 00368 Direction direction ); 00369 00370 AdaptiveKDTree* tool() const 00371 { return treeTool; } 00372 00374 EntityHandle handle() const 00375 { return mStack.back().entity; } 00376 00378 const double* box_min() const 00379 { return mBox[BMIN].array(); } 00380 00382 const double* box_max() const 00383 { return mBox[BMAX].array(); } 00384 00385 double volume() const 00386 { return (mBox[BMAX][0] - mBox[BMIN][0]) * 00387 (mBox[BMAX][1] - mBox[BMIN][1]) * 00388 (mBox[BMAX][2] - mBox[BMIN][2]); } 00389 00391 bool intersects( const AdaptiveKDTree::Plane& plane ) const 00392 { return mBox[BMIN][plane.norm] <= plane.coord && 00393 mBox[BMAX][plane.norm] >= plane.coord; } 00394 00396 unsigned depth() const 00397 { return mStack.size(); } 00398 00403 ErrorCode step( Direction direction ); 00404 00409 ErrorCode step() { return step(RIGHT); } 00410 00415 ErrorCode back() { return step(LEFT); } 00416 00417 00430 ErrorCode sibling_side( AdaptiveKDTree::Axis& axis_out, bool& neg_out ) const; 00431 00455 ErrorCode get_neighbors( AdaptiveKDTree::Axis norm, bool neg, 00456 std::vector<AdaptiveKDTreeIter>& results, 00457 double epsilon = 0.0 ) const; 00458 00460 ErrorCode get_parent_split_plane( AdaptiveKDTree::Plane& plane ) const; 00461 00464 bool is_sibling( const AdaptiveKDTreeIter& other_leaf ) const; 00465 00468 bool is_sibling( EntityHandle other_leaf ) const; 00469 00474 bool sibling_is_forward( ) const; 00475 00491 bool intersect_ray( const double ray_point[3], 00492 const double ray_vect[3], 00493 double& t_enter, double& t_exit ) const; 00494 }; 00495 00496 inline ErrorCode AdaptiveKDTree::reset_tree() 00497 { 00498 return delete_tree_sets(); 00499 } 00500 00501 } // namespace moab 00502 00503 #endif
1.7.6.1 
