Special Octree implemenation that supports to query points close to caste rays. More...

#include <RayCastOctreeObject.h>

Inheritance diagram for icl::geom::RayCastOctreeObject:

Public Member Functions
	RayCastOctreeObject (const float &minX, const float &minY, const float &minZ, const float &width, const float &height, const float &depth)
	creates a QuadTree for the given 2D rectangle
	RayCastOctreeObject (const float &min, const float &len)
	creates a QuadTree for the given 2D rectangle
	~RayCastOctreeObject ()
	destructor
ICLGeom_API std::vector< Vec >	rayCast (const ViewRay &ray, float maxDist=1) const
	casts a ray and returns all points that are closer than given distance to ray
ICLGeom_API std::vector< Vec >	rayCastSort (const ViewRay &ray, float maxDist=1) const
	as ray cast, but sorts the points by distance to the ray-offset
ICLGeom_API Vec	rayCastClosest (const ViewRay &ray, float maxDist=1) const throw (utils::ICLException)
	casts a ray and returns the point closest to the ray-offset
Static Protected Member Functions
static void	ray_cast_sqr_rec (const Super::Node *n, const ViewRay &ray, float maxSqrDist, float maxDist, std::vector< Vec > &result)
	internal worker method for recursive ray cast
Private Types
typedef OctreeObject< float, 16, 1, Vec, 1024 >	Super

Detailed Description

Special Octree implemenation that supports to query points close to caste rays.

The RayCastOctreeObject defines all template parameters of the more general OctreeObject class, while preserving the super classe's interface, it adds the rayCast function, which can be used to query all points, that are close to a given view-ray.

The Segmentation Algorithm

Internally the octree structure is exploited for accelerating ray casts. Each node's AABB (axis aligned bounding box) defines a bounding sphere around it's center. The radius of the bounding sphere is pre-computed and accessible from the Node structure. Whenever the center of node is further away from the view-ray than the pre-computed node radius plus the maximum distance to the ray the node and all it's sub-nodes are not tested any further. As an additional speed-up, internally squared distances are used to avoid expensive square-root calculations.

Speed

On a Core i5 @ 3.4 GHz with 8GB Ram and 64 Bit linux, an orthogonal ray cast into a regular grid 2D point cloud in 3D space (containing a typical number of, 320x240 points) takes about 3.2 micro-secounds - that is 330 ray-casts per millisecond. This is about 250 times faster than a brute force search.

Member Typedef Documentation

typedef OctreeObject<float,16,1,Vec,1024> icl::geom::RayCastOctreeObject::Super [private]

Constructor & Destructor Documentation

icl::geom::RayCastOctreeObject::RayCastOctreeObject	(	const float &	minX,
		const float &	minY,
		const float &	minZ,
		const float &	width,
		const float &	height,
		const float &	depth
	)		`[inline]`

creates a QuadTree for the given 2D rectangle

icl::geom::RayCastOctreeObject::RayCastOctreeObject	(	const float &	min,
		const float &	len
	)		`[inline]`

creates a QuadTree for the given 2D rectangle

icl::geom::RayCastOctreeObject::~RayCastOctreeObject ( ) [inline]

destructor

Deletes the root node only, all other nodes are deleted by the allocator

Member Function Documentation

static void icl::geom::RayCastOctreeObject::ray_cast_sqr_rec	(	const Super::Node *	n,
		const ViewRay &	ray,
		float	maxSqrDist,
		float	maxDist,
		std::vector< Vec > &	result
	)		`[static, protected]`

internal worker method for recursive ray cast

ICLGeom_API std::vector<Vec> icl::geom::RayCastOctreeObject::rayCast	(	const ViewRay &	ray,
		float	maxDist = `1`
	)		const

casts a ray and returns all points that are closer than given distance to ray

ICLGeom_API Vec icl::geom::RayCastOctreeObject::rayCastClosest	(	const ViewRay &	ray,
		float	maxDist = `1`
	)		const throw (utils::ICLException)

casts a ray and returns the point closest to the ray-offset

ICLGeom_API std::vector<Vec> icl::geom::RayCastOctreeObject::rayCastSort	(	const ViewRay &	ray,
		float	maxDist = `1`
	)		const

as ray cast, but sorts the points by distance to the ray-offset

The documentation for this class was generated from the following file:

/home/jenkins/workspace/icl-manual-trunk/icl-manual/ICLGeom/src/ICLGeom/RayCastOctreeObject.h

Public Member Functions