DGtal  1.5.beta
DGtal::RayIntersectionPredicate< TPoint > Struct Template Reference

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);
CountedPtr< SH3::DigitalSurface > surface
MyDigitalSurface::ConstIterator ConstIterator
Template Parameters
TPointtype 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
originOrigin of the ray
destvector to represent the direction of the ray

Definition at line 105 of file RayIntersectionPredicates.h.

107  : myOrigin(origin), myDest(dest)
108  {
109  ASSERT_MSG( dest.norm1() != NumberTraits<typename Point::UnsignedComponent>::ZERO,
110  "Direction must be non-null vector");
111  }
static const std::decay< T >::type ZERO
Constant Zero.
Definition: NumberTraits.h:100

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
v1first vertex of the triangle
v2second vertex of the triangle
v3third vertex of the triangle
Returns
true if the ray intersects the closed triangle (v1,v2,v3)

Definition at line 125 of file RayIntersectionPredicates.h.

128  {
129 
130  ASSERT((v1 != v2 ) && (v1 != v3) && (v2 != v3));
131 
132  Point e1, e2; //Edge1, Edge2
133  Point P, Q, T;
134  Component det, u, v;
135 
136  //Find vectors for two edges sharing V1
137  e1 = v2 - v1;
138  e2 = v3 - v1;
139 
140  //Begin calculating determinant - also used to calculate u parameter
141  P = myDest.crossProduct( e2 );
142 
143  //if determinant is near zero, ray lies in plane of triangle
144  det = e1.dot( P );
146  {
147  return false;
148  }
149 
150  //calculate distance from V1 to ray origin
151  T = myOrigin - v1;
152 
153  //Calculate u parameter and test bound
154  u = T.dot( P ); //* inv_det;
155 
157  {
158  if ((u < NumberTraits<Component>::ZERO) ||
159  ( u > det))
160  {
161  return false;
162  }
163  }
164  else
165  {
166  if ((u > NumberTraits<Component>::ZERO) ||
167  ( u < det))
168  {
169  return false;
170  }
171  }
172 
173  //Prepare to test v parameter
174  Q = T.crossProduct( e1 );
175 
176  //Calculate V parameter and test bound
177  v = myDest.dot( Q );
178 
179  //The intersection lies outside of the triangle
181  {
182  if ((v < NumberTraits<Component>::ZERO) ||
183  ((u+v) > det))
184  {
185  return false;
186  }
187  }
188  else
189  {
190  if ((v > NumberTraits<Component>::ZERO) ||
191  ((u+v) < det))
192  {
193  return false;
194  }
195  }
196 
197  //distance to triangle must be positive
198  Component t = e2.dot( Q ) ;
199  if (t*det < NumberTraits<Component>::ZERO)
200  return false;
201 
202  return true;
203  }
TPoint::Component Component
Type of point coordinates.
MyPointD Point
Definition: testClone2.cpp:383

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
v1first vertex of the quad
v2second vertex of the quad
v3third vertex of the quad
v4fourth vertex of the quad
Returns
true if the ray intersects the quad (v1,v2,v3,v4)

Definition at line 217 of file RayIntersectionPredicates.h.

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

◆ 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
aSurfela Khalimsky surfel
Returns
true if the ray intersects the surfel aSurfel

Definition at line 240 of file RayIntersectionPredicates.h.

241  {
242  auto const & aPreSurfel = aSurfel.preCell();
243 
244  Component x1,x2,x3,x4;
245  Component y1,y2,y3,y4;
246  Component z1,z2,z3,z4;
248 
249  Point baseQuadCenter = aPreSurfel.coordinates;
250 
251  bool yodd = ( NumberTraits<Component>::castToInt64_t(aPreSurfel.coordinates[ 1 ]) & 1 );
252  bool zodd = ( NumberTraits<Component>::castToInt64_t(aPreSurfel.coordinates[ 2 ]) & 1 );
253 
254  if(!zodd)
255  {
256  //zsurfel
257  x1= baseQuadCenter[0]-ONE; y1= baseQuadCenter[1]-ONE; z1= baseQuadCenter[2];
258  x2= baseQuadCenter[0]+ONE; y2= baseQuadCenter[1]-ONE; z2= baseQuadCenter[2];
259  x3= baseQuadCenter[0]+ONE; y3= baseQuadCenter[1]+ONE; z3= baseQuadCenter[2];
260  x4= baseQuadCenter[0]-ONE; y4= baseQuadCenter[1]+ONE; z4= baseQuadCenter[2];
261  }
262  else if(!yodd)
263  {
264  //ysurfel
265  x1= baseQuadCenter[0]-ONE; y1= baseQuadCenter[1]; z1= baseQuadCenter[2]-ONE;
266  x2= baseQuadCenter[0]-ONE; y2= baseQuadCenter[1]; z2= baseQuadCenter[2]+ONE;
267  x3= baseQuadCenter[0]+ONE; y3= baseQuadCenter[1]; z3= baseQuadCenter[2]+ONE;
268  x4= baseQuadCenter[0]+ONE; y4= baseQuadCenter[1]; z4= baseQuadCenter[2]-ONE;
269  }
270  else
271  {
272  //xsurfel
273  x1= baseQuadCenter[0]; y1= baseQuadCenter[1]-ONE; z1= baseQuadCenter[2]-ONE;
274  x2= baseQuadCenter[0]; y2= baseQuadCenter[1]+ONE; z2= baseQuadCenter[2]-ONE;
275  x3= baseQuadCenter[0]; y3= baseQuadCenter[1]+ONE; z3= baseQuadCenter[2]+ONE;
276  x4= baseQuadCenter[0]; y4= baseQuadCenter[1]-ONE; z4= baseQuadCenter[2]+ONE;
277  }
278  return this->operator()(Point(x1, y1, z1), Point(x2 ,y2, z2),
279  Point(x3, y3, z3), Point(x4, y4, z4));
280  }
static DGtal::int64_t castToInt64_t(const std::decay< T >::type &aT)
Cast method to DGtal::int64_t (for I/O or board export uses only).
Definition: NumberTraits.h:145
static const std::decay< T >::type ONE
Constant One.
Definition: NumberTraits.h:103
bool operator()(const Point &v1, const Point &v2, const Point &v3) const

References DGtal::NumberTraitsImpl< std::decay< T >::type >::castToInt64_t(), DGtal::RayIntersectionPredicate< TPoint >::operator()(), and DGtal::SignedKhalimskyCell< dim, TInteger >::preCell().

Field Documentation

◆ myDest

template<typename TPoint >
Point DGtal::RayIntersectionPredicate< TPoint >::myDest

◆ myOrigin

template<typename TPoint >
Point DGtal::RayIntersectionPredicate< TPoint >::myOrigin

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