contrib/brl/bbas/imesh/algo/imesh_kd_tree.cxx File Reference

#include "imesh_kd_tree.h"
#include "imesh_kd_tree.txx"
#include <vgl/vgl_box_3d.h>
#include <vgl/vgl_point_3d.h>
#include <imesh/algo/imesh_intersect.h>
#include <vcl_algorithm.h>
#include <vcl_limits.h>
#include <vcl_cmath.h>

Go to the source code of this file.

Functions
double	imesh_min_sq_dist (const vgl_point_3d< double > &p, const vgl_box_3d< double > &b)
	The minimum square distance between p and any point in b.
double	imesh_max_sq_dist (const vgl_point_3d< double > &p, const vgl_box_3d< double > &b)
	The maximum square distance between p and any point in b.
vcl_auto_ptr< imesh_kd_tree_node >	imesh_build_kd_tree_rec (const vcl_vector< vgl_box_3d< double > > &boxes, const vgl_box_3d< double > &outer_box, const vgl_box_3d< double > &inner_box, const vcl_vector< unsigned int > &indices)
	recursively construct a kd-tree of mesh triangles.
vcl_auto_ptr< imesh_kd_tree_node >	imesh_build_kd_tree (const vcl_vector< vgl_box_3d< double > > &boxes)
	Construct a kd-tree (in 3d) of axis aligned boxes.
vcl_auto_ptr< imesh_kd_tree_node >	imesh_build_kd_tree (const imesh_vertex_array< 3 > &verts, const imesh_face_array_base &faces)
	construct a kd-tree of mesh faces.
unsigned int	imesh_kd_tree_closest_point (const vgl_point_3d< double > &query, const imesh_mesh &mesh, const vcl_auto_ptr< imesh_kd_tree_node > &root, vgl_point_3d< double > &cp, vcl_vector< imesh_kd_tree_queue_entry > *dists)
	compute the closest point on the mesh using the kd-tree.
void	imesh_kd_tree_traverse (const vgl_point_3d< double > &query, const vcl_auto_ptr< imesh_kd_tree_node > &root, vcl_vector< imesh_kd_tree_queue_entry > &leaf, vcl_vector< imesh_kd_tree_queue_entry > &internal_node)
	Traverse the tree looking for leaf nodes that contain the query.

---

Detailed Description

Definition in file imesh_kd_tree.cxx.

---

Function Documentation

vcl_auto_ptr<imesh_kd_tree_node> imesh_build_kd_tree

(

const vcl_vector< vgl_box_3d< double > > &

boxes

)

Construct a kd-tree (in 3d) of axis aligned boxes.

Definition at line 229 of file imesh_kd_tree.cxx.

vcl_auto_ptr<imesh_kd_tree_node> imesh_build_kd_tree	(	const imesh_vertex_array< 3 > &	verts,
		const imesh_face_array_base &	faces
	)

construct a kd-tree of mesh faces.

Definition at line 271 of file imesh_kd_tree.cxx.

vcl_auto_ptr<imesh_kd_tree_node> imesh_build_kd_tree_rec	(	const vcl_vector< vgl_box_3d< double > > &	boxes,
		const vgl_box_3d< double > &	outer_box,
		const vgl_box_3d< double > &	inner_box,
		const vcl_vector< unsigned int > &	indices
	)

recursively construct a kd-tree of mesh triangles.

Definition at line 140 of file imesh_kd_tree.cxx.

unsigned int imesh_kd_tree_closest_point	(	const vgl_point_3d< double > &	query,
		const imesh_mesh &	mesh,
		const vcl_auto_ptr< imesh_kd_tree_node > &	root,
		vgl_point_3d< double > &	cp,
		vcl_vector< imesh_kd_tree_queue_entry > *	dists
	)

compute the closest point on the mesh using the kd-tree.

Returns:

the index of the closest triangle

Definition at line 338 of file imesh_kd_tree.cxx.

void imesh_kd_tree_traverse	(	const vgl_point_3d< double > &	query,
		const vcl_auto_ptr< imesh_kd_tree_node > &	root,
		vcl_vector< imesh_kd_tree_queue_entry > &	leaf,
		vcl_vector< imesh_kd_tree_queue_entry > &	internal_node
	)

Traverse the tree looking for leaf nodes that contain the query.

Returns a vector of leaf nodes paired with min square distance to the inner box Also returns a vector of the unexplored internal node-distance^2 pairs Resulting vectors are unsorted

Definition at line 357 of file imesh_kd_tree.cxx.

double imesh_max_sq_dist	(	const vgl_point_3d< double > &	p,
		const vgl_box_3d< double > &	b
	)

The maximum square distance between p and any point in b.

Definition at line 53 of file imesh_kd_tree.cxx.

double imesh_min_sq_dist	(	const vgl_point_3d< double > &	p,
		const vgl_box_3d< double > &	b
	)

The minimum square distance between p and any point in b.

Definition at line 16 of file imesh_kd_tree.cxx.