HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ImathLineAlgo.h
Go to the documentation of this file.
1 //
2 // SPDX-License-Identifier: BSD-3-Clause
3 // Copyright Contributors to the OpenEXR Project.
4 //
5 
6 //
7 // Algorithms applied to or in conjunction with Imath::Line class
8 //
9 
10 #ifndef INCLUDED_IMATHLINEALGO_H
11 #define INCLUDED_IMATHLINEALGO_H
12 
13 #include "ImathFun.h"
14 #include "ImathLine.h"
15 #include "ImathNamespace.h"
16 #include "ImathVecAlgo.h"
17 
18 IMATH_INTERNAL_NAMESPACE_HEADER_ENTER
19 
20 ///
21 /// Compute point1 and point2 such that point1 is on line1, point2
22 /// is on line2 and the distance between point1 and point2 is minimal.
23 ///
24 /// This function returns true if point1 and point2 can be computed,
25 /// or false if line1 and line2 are parallel or nearly parallel.
26 /// This function assumes that line1.dir and line2.dir are normalized.
27 ///
28 
29 template <class T>
30 IMATH_CONSTEXPR14 bool
31 closestPoints (const Line3<T>& line1, const Line3<T>& line2, Vec3<T>& point1, Vec3<T>& point2) IMATH_NOEXCEPT
32 {
33  Vec3<T> w = line1.pos - line2.pos;
34  T d1w = line1.dir ^ w;
35  T d2w = line2.dir ^ w;
36  T d1d2 = line1.dir ^ line2.dir;
37  T n1 = d1d2 * d2w - d1w;
38  T n2 = d2w - d1d2 * d1w;
39  T d = 1 - d1d2 * d1d2;
40  T absD = abs (d);
41 
42  if ((absD > 1) || (abs (n1) < std::numeric_limits<T>::max() * absD && abs (n2) < std::numeric_limits<T>::max() * absD))
43  {
44  point1 = line1 (n1 / d);
45  point2 = line2 (n2 / d);
46  return true;
47  }
48  else
49  {
50  return false;
51  }
52 }
53 
54 ///
55 /// Given a line and a triangle (v0, v1, v2), the intersect() function
56 /// finds the intersection of the line and the plane that contains the
57 /// triangle.
58 ///
59 /// If the intersection point cannot be computed, either because the
60 /// line and the triangle's plane are nearly parallel or because the
61 /// triangle's area is very small, intersect() returns false.
62 ///
63 /// If the intersection point is outside the triangle, intersect
64 /// returns false.
65 ///
66 /// If the intersection point, pt, is inside the triangle, intersect()
67 /// computes a front-facing flag and the barycentric coordinates of
68 /// the intersection point, and returns true.
69 ///
70 /// The front-facing flag is true if the dot product of the triangle's
71 /// normal, (v2-v1)%(v1-v0), and the line's direction is negative.
72 ///
73 /// The barycentric coordinates have the following property:
74 ///
75 /// pt = v0 * barycentric.x + v1 * barycentric.y + v2 * barycentric.z
76 ///
77 
78 template <class T>
79 IMATH_CONSTEXPR14 bool
80 intersect (const Line3<T>& line,
81  const Vec3<T>& v0,
82  const Vec3<T>& v1,
83  const Vec3<T>& v2,
84  Vec3<T>& pt,
85  Vec3<T>& barycentric,
86  bool& front) IMATH_NOEXCEPT
87 {
88  Vec3<T> edge0 = v1 - v0;
89  Vec3<T> edge1 = v2 - v1;
90  Vec3<T> normal = edge1 % edge0;
91 
92  T l = normal.length();
93 
94  if (l != 0)
95  normal /= l;
96  else
97  return false; // zero-area triangle
98 
99  //
100  // d is the distance of line.pos from the plane that contains the triangle.
101  // The intersection point is at line.pos + (d/nd) * line.dir.
102  //
103 
104  T d = normal ^ (v0 - line.pos);
105  T nd = normal ^ line.dir;
106 
107  if (abs (nd) > 1 || abs (d) < std::numeric_limits<T>::max() * abs (nd))
108  pt = line (d / nd);
109  else
110  return false; // line and plane are nearly parallel
111 
112  //
113  // Compute the barycentric coordinates of the intersection point.
114  // The intersection is inside the triangle if all three barycentric
115  // coordinates are between zero and one.
116  //
117 
118  {
119  Vec3<T> en = edge0.normalized();
120  Vec3<T> a = pt - v0;
121  Vec3<T> b = v2 - v0;
122  Vec3<T> c = (a - en * (en ^ a));
123  Vec3<T> d = (b - en * (en ^ b));
124  T e = c ^ d;
125  T f = d ^ d;
126 
127  if (e >= 0 && e <= f)
128  barycentric.z = e / f;
129  else
130  return false; // outside
131  }
132 
133  {
134  Vec3<T> en = edge1.normalized();
135  Vec3<T> a = pt - v1;
136  Vec3<T> b = v0 - v1;
137  Vec3<T> c = (a - en * (en ^ a));
138  Vec3<T> d = (b - en * (en ^ b));
139  T e = c ^ d;
140  T f = d ^ d;
141 
142  if (e >= 0 && e <= f)
143  barycentric.x = e / f;
144  else
145  return false; // outside
146  }
147 
148  barycentric.y = 1 - barycentric.x - barycentric.z;
149 
150  if (barycentric.y < 0)
151  return false; // outside
152 
153  front = ((line.dir ^ normal) < 0);
154  return true;
155 }
156 
157 ///
158 /// Return the vertex that is closest to the given line. The returned
159 /// point is either v0, v1, or v2.
160 ///
161 
162 template <class T>
163 IMATH_CONSTEXPR14 Vec3<T>
165 {
166  Vec3<T> nearest = v0;
167  T neardot = (v0 - l.closestPointTo (v0)).length2();
168 
169  T tmp = (v1 - l.closestPointTo (v1)).length2();
170 
171  if (tmp < neardot)
172  {
173  neardot = tmp;
174  nearest = v1;
175  }
176 
177  tmp = (v2 - l.closestPointTo (v2)).length2();
178  if (tmp < neardot)
179  {
180  neardot = tmp;
181  nearest = v2;
182  }
183 
184  return nearest;
185 }
186 
187 ///
188 /// Rotate the point p around the line l by the given angle.
189 ///
190 
191 template <class T>
192 IMATH_CONSTEXPR14 Vec3<T>
194 {
195  //
196  // Form a coordinate frame with <x,y,a>. The rotation is the in xy
197  // plane.
198  //
199 
200  Vec3<T> q = l.closestPointTo (p);
201  Vec3<T> x = p - q;
202  T radius = x.length();
203 
204  x.normalize();
205  Vec3<T> y = (x % l.dir).normalize();
206 
207  T cosangle = std::cos (angle);
208  T sinangle = std::sin (angle);
209 
210  Vec3<T> r = q + x * radius * cosangle + y * radius * sinangle;
211 
212  return r;
213 }
214 
215 IMATH_INTERNAL_NAMESPACE_HEADER_EXIT
216 
217 #endif // INCLUDED_IMATHLINEALGO_H
SYS_API double cos(double x)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
#define IMATH_NOEXCEPT
Definition: ImathConfig.h:72
Definition: ImathVec.h:32
IMATH_HOSTDEVICE T length() const IMATH_NOEXCEPT
Return the Euclidean norm.
Definition: ImathVec.h:1734
IMATH_CONSTEXPR14 Vec3< T > closestVertex(const Vec3< T > &v0, const Vec3< T > &v1, const Vec3< T > &v2, const Line3< T > &l) IMATH_NOEXCEPT
const GLfloat * c
Definition: glew.h:16631
IMATH_HOSTDEVICE Vec3< T > normalized() const IMATH_NOEXCEPT
Return a normalized vector. Does not modify *this.
Definition: ImathVec.h:1801
GLdouble l
Definition: glew.h:9164
GLint GLenum GLint x
Definition: glcorearb.h:409
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:857
GLdouble GLdouble GLdouble GLdouble q
Definition: glew.h:1419
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER IMATH_CONSTEXPR14 bool closestPoints(const Line3< T > &line1, const Line3< T > &line2, Vec3< T > &point1, Vec3< T > &point2) IMATH_NOEXCEPT
Definition: ImathLineAlgo.h:31
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:818
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
GLfloat GLfloat p
Definition: glew.h:16656
GLfloat v0
Definition: glcorearb.h:816
IMATH_CONSTEXPR14 Vec3< T > rotatePoint(const Vec3< T > p, Line3< T > l, T angle) IMATH_NOEXCEPT
IMATH_CONSTEXPR14 bool intersect(const Line3< T > &line, const Vec3< T > &v0, const Vec3< T > &v1, const Vec3< T > &v2, Vec3< T > &pt, Vec3< T > &barycentric, bool &front) IMATH_NOEXCEPT
Definition: ImathLineAlgo.h:80
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GLfloat f
Definition: glcorearb.h:1926
GLdouble angle
Definition: glew.h:9177
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER IMATH_HOSTDEVICE constexpr T abs(T a) IMATH_NOEXCEPT
Definition: ImathFun.h:26
GLfloat GLfloat v1
Definition: glcorearb.h:817
GLboolean r
Definition: glcorearb.h:1222
IMATH_HOSTDEVICE const Vec3 & normalize() IMATH_NOEXCEPT
Normalize in place. If length()==0, return a null vector.
Definition: ImathVec.h:1753
GLint y
Definition: glcorearb.h:103
SYS_API double sin(double x)
constexpr T normalize(UT_FixedVector< T, D > &a) noexcept