DGtal: DGtal::RayIntersectionPredicate< TPoint

This class implements various intersection predicates between a ray and a triangle, a quad or a surfel in dimension 3. More...

#include <DGtal/geometry/tools/RayIntersectionPredicates.h>

Public Types
typedef TPoint	Point
	Type of point. More...

typedef TPoint	Vector
	Type of vector. More...

typedef TPoint::Component	Component
	Type of point coordinates. More...

Public Member Functions
	BOOST_STATIC_ASSERT (TPoint::dimension==3)
	Only in dimension 3. More...

	RayIntersectionPredicate (const Point &origin, const Vector &dest)

bool	operator() (const Point &v1, const Point &v2, const Point &v3) const

bool	operator() (const Point &v1, const Point &v2, const Point &v3, const Point &v4) const

template<typename Surfel >
bool	operator() (const Surfel &aSurfel) const

Data Fields
Point	myOrigin

Point	myDest

Detailed Description

template<typename TPoint>
struct DGtal::RayIntersectionPredicate< TPoint >

This class implements various intersection predicates between a ray and a triangle, a quad or a surfel in dimension 3.

Few details:

Ray-Triangle intersection only uses '+', '*' and '<' operators on Point::Coordinate numbers. It implements "Fast, Minimum Storage Ray/Triangle Intersection", Möller & Trumbore. Journal of Graphics Tools, 1997.
Ray-Quad uses two ray-triangle tests (some redundant computations could have been factorized).
Ray-Surfel intersection is performed in KhalimskySpace coordinates for exact computations. For example, a surfel with coordinates (i,j,k) with i being even, is associated to the quad (i,j+/-1,k+/-1).

For the later case, this predicate is useful to get the surfel (an iterator on a surfel) of a digital surface intersected by the ray using for instance:

Surface::ConstIterator it = std::find_if(surface.begin(), surface.end(), rayPredicateInstance);

surface

CountedPtr< SH3::DigitalSurface > surface

Definition: dgtalCalculus-geodesic.cpp:66

ConstIterator

MyDigitalSurface::ConstIterator ConstIterator

Definition: greedy-plane-segmentation-ex2.cpp:93

Template Parameters

TPoint type of points.

Definition at line 81 of file RayIntersectionPredicates.h.

Member Typedef Documentation

◆ Component

template<typename TPoint >

typedef TPoint::Component DGtal::RayIntersectionPredicate< TPoint >::Component

Type of point coordinates.

Definition at line 94 of file RayIntersectionPredicates.h.

◆ Point

template<typename TPoint >

typedef TPoint DGtal::RayIntersectionPredicate< TPoint >::Point

Type of point.

Definition at line 88 of file RayIntersectionPredicates.h.

◆ Vector

template<typename TPoint >

typedef TPoint DGtal::RayIntersectionPredicate< TPoint >::Vector

Type of vector.

Definition at line 91 of file RayIntersectionPredicates.h.

Constructor & Destructor Documentation

◆ RayIntersectionPredicate()

template<typename TPoint >

DGtal::RayIntersectionPredicate< TPoint >::RayIntersectionPredicate	(	const Point &	origin,
		const Vector &	dest
	)

inline

Constructor from a ray

Precondition: dest vector must be not null.

Parameters

origin	Origin of the ray
dest	vector to represent the direction of the ray

Definition at line 105 of file RayIntersectionPredicates.h.

       : myOrigin(origin), myDest(dest) 
     {
       ASSERT_MSG( dest.norm1() != NumberTraits<typename Point::UnsignedComponent>::ZERO, 
                   "Direction must be non-null vector"); 
     }

Member Function Documentation

◆ BOOST_STATIC_ASSERT()

template<typename TPoint >

DGtal::RayIntersectionPredicate< TPoint >::BOOST_STATIC_ASSERT ( TPoint::dimension = =3 )

Only in dimension 3.

◆ operator()() [1/3]

template<typename TPoint >

bool DGtal::RayIntersectionPredicate< TPoint >::operator()	(	const Point &	v1,
		const Point &	v2,
		const Point &	v3
	)		const

inline

Ray-Triangle intersection predicate (no back-face culling test, i.e., the order of vertices does not matter).

Precondition: the triangle must be non-degenerate.

Parameters

v1	first vertex of the triangle
v2	second vertex of the triangle
v3	third vertex of the triangle

Returns: true if the ray intersects the closed triangle (v1,v2,v3)

Definition at line 125 of file RayIntersectionPredicates.h.

     {
       
       ASSERT((v1 != v2 ) && (v1 != v3) && (v2 != v3));
  
       Point e1, e2;  //Edge1, Edge2
       Point P, Q, T;
       Component det, u, v;
  
       //Find vectors for two edges sharing V1
       e1 = v2 - v1;
       e2 = v3 - v1;
  
       //Begin calculating determinant - also used to calculate u parameter
       P = myDest.crossProduct( e2 );
       
       //if determinant is near zero, ray lies in plane of triangle
       det = e1.dot( P );
       if(det == NumberTraits<Component>::ZERO) 
         {
           return false;
         }
       
       //calculate distance from V1 to ray origin
       T =  myOrigin -  v1;
       
       //Calculate u parameter and test bound
       u = T.dot( P );  //* inv_det;
       
       if (det >  NumberTraits<Component>::ZERO)
         {
           if ((u < NumberTraits<Component>::ZERO) ||
               ( u > det))
             {
               return false;
             }
         }
       else
         {
           if ((u > NumberTraits<Component>::ZERO) ||
               ( u < det))
             {
               return false;
             }
         }
  
       //Prepare to test v parameter
       Q = T.crossProduct( e1 );
       
       //Calculate V parameter and test bound
       v = myDest.dot( Q ); 
       
       //The intersection lies outside of the triangle
       if (det >  NumberTraits<Component>::ZERO)
         {
           if ((v < NumberTraits<Component>::ZERO)  ||
               ((u+v) > det)) 
             {
               return false;
             }       
         }
       else
         {
           if ((v > NumberTraits<Component>::ZERO)  ||
               ((u+v) < det)) 
             {
               return false;
             }       
         }
  
       //distance to triangle must be positive
       Component t = e2.dot( Q ) ;
       if (t*det < NumberTraits<Component>::ZERO)
         return false;
        
       return true;
     }

References DGtal::RayIntersectionPredicate< TPoint >::myDest, and DGtal::RayIntersectionPredicate< TPoint >::myOrigin.

Referenced by DGtal::RayIntersectionPredicate< TPoint >::operator()().

◆ operator()() [2/3]

template<typename TPoint >

bool DGtal::RayIntersectionPredicate< TPoint >::operator()	(	const Point &	v1,
		const Point &	v2,
		const Point &	v3,
		const Point &	v4
	)		const

inline

Ray-Quad intersection predicate (calls two ray-triangle intersections).

Parameters

v1	first vertex of the quad
v2	second vertex of the quad
v3	third vertex of the quad
v4	fourth vertex of the quad

Returns: true if the ray intersects the quad (v1,v2,v3,v4)

Definition at line 217 of file RayIntersectionPredicates.h.

     {
       return (this->operator()(v1,v2,v3) ||
               this->operator()(v1,v4,v3) );
     }

◆ operator()() [3/3]

template<typename TPoint >

template<typename Surfel >

bool DGtal::RayIntersectionPredicate< TPoint >::operator() ( const Surfel & aSurfel ) const

inline

Ray-Surfel intersection predicate (calls two ray-triangle intersections).

Warning: Ray intersection is performed in KhalimskySpace coordinate system. The type Point of the RayIntersectionPredicate class must be the same as the Surfel::Point type.

Parameters

aSurfel a Khalimsky surfel

Returns: true if the ray intersects the surfel aSurfel

Definition at line 240 of file RayIntersectionPredicates.h.

     {
       auto const & aPreSurfel = aSurfel.preCell();
  
       Component x1,x2,x3,x4;
       Component y1,y2,y3,y4;
       Component z1,z2,z3,z4;
       Component ONE = NumberTraits<Component>::ONE;
       
       Point baseQuadCenter =  aPreSurfel.coordinates;
       
       bool yodd = ( NumberTraits<Component>::castToInt64_t(aPreSurfel.coordinates[ 1 ]) & 1 );
       bool zodd = ( NumberTraits<Component>::castToInt64_t(aPreSurfel.coordinates[ 2 ]) & 1 ); 
       
       if(!zodd)
         {
           //zsurfel
           x1= baseQuadCenter[0]-ONE; y1= baseQuadCenter[1]-ONE; z1= baseQuadCenter[2];
           x2= baseQuadCenter[0]+ONE; y2= baseQuadCenter[1]-ONE; z2= baseQuadCenter[2];
           x3= baseQuadCenter[0]+ONE; y3= baseQuadCenter[1]+ONE; z3= baseQuadCenter[2];
           x4= baseQuadCenter[0]-ONE; y4= baseQuadCenter[1]+ONE; z4= baseQuadCenter[2];
         }
       else if(!yodd)
         {
           //ysurfel
           x1= baseQuadCenter[0]-ONE; y1= baseQuadCenter[1]; z1= baseQuadCenter[2]-ONE;
           x2= baseQuadCenter[0]-ONE; y2= baseQuadCenter[1]; z2= baseQuadCenter[2]+ONE;
           x3= baseQuadCenter[0]+ONE; y3= baseQuadCenter[1]; z3= baseQuadCenter[2]+ONE;
           x4= baseQuadCenter[0]+ONE; y4= baseQuadCenter[1]; z4= baseQuadCenter[2]-ONE;
         }
       else
         {
           //xsurfel
           x1= baseQuadCenter[0]; y1= baseQuadCenter[1]-ONE; z1= baseQuadCenter[2]-ONE;
           x2= baseQuadCenter[0]; y2= baseQuadCenter[1]+ONE; z2= baseQuadCenter[2]-ONE;
           x3= baseQuadCenter[0]; y3= baseQuadCenter[1]+ONE; z3= baseQuadCenter[2]+ONE;
           x4= baseQuadCenter[0]; y4= baseQuadCenter[1]-ONE; z4= baseQuadCenter[2]+ONE;
         }
       return this->operator()(Point(x1, y1, z1), Point(x2 ,y2, z2),
                               Point(x3, y3, z3), Point(x4, y4, z4)); 
     }