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

A KD-Tree for mesh faces. More...

#include <imesh/imesh_mesh.h>
#include <vgl/vgl_box_3d.h>
#include <vgl/vgl_point_3d.h>

Go to the source code of this file.

Classes
struct	imesh_kd_tree_node
	A node in the KD-Tree. More...
class	imesh_kd_tree_queue_entry
	A class used for sorting a queue of tree nodes by an assigned value. More...
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 (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.
vcl_auto_ptr< imesh_kd_tree_node >	imesh_build_kd_tree (const imesh_mesh &mesh)
	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=0)
	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 > &internal, vcl_vector< imesh_kd_tree_queue_entry > &leaf)
	Traverse the tree looking for leaf nodes that contain the query.

---

Detailed Description

A KD-Tree for mesh faces.

Author:

Matt Leotta (mleotta@lems.brown.edu)

Date:

June 2, 2008

Definition in file imesh_kd_tree.h.

---

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

(

const imesh_mesh &

mesh

)

[inline]

construct a kd-tree of mesh faces.

Definition at line 82 of file imesh_kd_tree.h.

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

Parameters:

dists

(if specified) returns a vector of all explored nodes and the closest square distance found so far

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.