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.

typedef TPoint	Vector
	Type of vector.

typedef TPoint::Component	Component
	Type of point coordinates.

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

	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);

DGtal::DigitalSurface::ConstIterator

DigitalSurfaceContainer::SurfelConstIterator ConstIterator

Definition DigitalSurface.h:163

surface

CountedPtr< SH3::DigitalSurface > surface

Definition dgtalCalculus-geodesic.cpp:66

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)); 
    }