HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
ImathLineAlgo.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2002-2012, Industrial Light & Magic, a division of Lucas
4 // Digital Ltd. LLC
5 //
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions are
10 // met:
11 // * Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // * Redistributions in binary form must reproduce the above
14 // copyright notice, this list of conditions and the following disclaimer
15 // in the documentation and/or other materials provided with the
16 // distribution.
17 // * Neither the name of Industrial Light & Magic nor the names of
18 // its contributors may be used to endorse or promote products derived
19 // from this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 //
33 ///////////////////////////////////////////////////////////////////////////
34 
35 
36 
37 #ifndef INCLUDED_IMATHLINEALGO_H
38 #define INCLUDED_IMATHLINEALGO_H
39 
40 //------------------------------------------------------------------
41 //
42 // This file contains algorithms applied to or in conjunction
43 // with lines (Imath::Line). These algorithms may require
44 // more headers to compile. The assumption made is that these
45 // functions are called much less often than the basic line
46 // functions or these functions require more support classes
47 //
48 // Contains:
49 //
50 // bool closestPoints(const Line<T>& line1,
51 // const Line<T>& line2,
52 // Vec3<T>& point1,
53 // Vec3<T>& point2)
54 //
55 // bool intersect( const Line3<T> &line,
56 // const Vec3<T> &v0,
57 // const Vec3<T> &v1,
58 // const Vec3<T> &v2,
59 // Vec3<T> &pt,
60 // Vec3<T> &barycentric,
61 // bool &front)
62 //
63 // V3f
64 // closestVertex(const Vec3<T> &v0,
65 // const Vec3<T> &v1,
66 // const Vec3<T> &v2,
67 // const Line3<T> &l)
68 //
69 // V3f
70 // rotatePoint(const Vec3<T> p, Line3<T> l, float angle)
71 //
72 //------------------------------------------------------------------
73 
74 #include "ImathLine.h"
75 #include "ImathVecAlgo.h"
76 #include "ImathFun.h"
77 #include "ImathNamespace.h"
78 
80 
81 
82 template <class T>
83 bool
85  (const Line3<T>& line1,
86  const Line3<T>& line2,
87  Vec3<T>& point1,
88  Vec3<T>& point2)
89 {
90  //
91  // Compute point1 and point2 such that point1 is on line1, point2
92  // is on line2 and the distance between point1 and point2 is minimal.
93  // This function returns true if point1 and point2 can be computed,
94  // or false if line1 and line2 are parallel or nearly parallel.
95  // This function assumes that line1.dir and line2.dir are normalized.
96  //
97 
98  Vec3<T> w = line1.pos - line2.pos;
99  T d1w = line1.dir ^ w;
100  T d2w = line2.dir ^ w;
101  T d1d2 = line1.dir ^ line2.dir;
102  T n1 = d1d2 * d2w - d1w;
103  T n2 = d2w - d1d2 * d1w;
104  T d = 1 - d1d2 * d1d2;
105  T absD = abs (d);
106 
107  if ((absD > 1) ||
108  (abs (n1) < limits<T>::max() * absD &&
109  abs (n2) < limits<T>::max() * absD))
110  {
111  point1 = line1 (n1 / d);
112  point2 = line2 (n2 / d);
113  return true;
114  }
115  else
116  {
117  return false;
118  }
119 }
120 
121 
122 template <class T>
123 bool
124 intersect
125  (const Line3<T> &line,
126  const Vec3<T> &v0,
127  const Vec3<T> &v1,
128  const Vec3<T> &v2,
129  Vec3<T> &pt,
130  Vec3<T> &barycentric,
131  bool &front)
132 {
133  //
134  // Given a line and a triangle (v0, v1, v2), the intersect() function
135  // finds the intersection of the line and the plane that contains the
136  // triangle.
137  //
138  // If the intersection point cannot be computed, either because the
139  // line and the triangle's plane are nearly parallel or because the
140  // triangle's area is very small, intersect() returns false.
141  //
142  // If the intersection point is outside the triangle, intersect
143  // returns false.
144  //
145  // If the intersection point, pt, is inside the triangle, intersect()
146  // computes a front-facing flag and the barycentric coordinates of
147  // the intersection point, and returns true.
148  //
149  // The front-facing flag is true if the dot product of the triangle's
150  // normal, (v2-v1)%(v1-v0), and the line's direction is negative.
151  //
152  // The barycentric coordinates have the following property:
153  //
154  // pt = v0 * barycentric.x + v1 * barycentric.y + v2 * barycentric.z
155  //
156 
157  Vec3<T> edge0 = v1 - v0;
158  Vec3<T> edge1 = v2 - v1;
159  Vec3<T> normal = edge1 % edge0;
160 
161  T l = normal.length();
162 
163  if (l != 0)
164  normal /= l;
165  else
166  return false; // zero-area triangle
167 
168  //
169  // d is the distance of line.pos from the plane that contains the triangle.
170  // The intersection point is at line.pos + (d/nd) * line.dir.
171  //
172 
173  T d = normal ^ (v0 - line.pos);
174  T nd = normal ^ line.dir;
175 
176  if (abs (nd) > 1 || abs (d) < limits<T>::max() * abs (nd))
177  pt = line (d / nd);
178  else
179  return false; // line and plane are nearly parallel
180 
181  //
182  // Compute the barycentric coordinates of the intersection point.
183  // The intersection is inside the triangle if all three barycentric
184  // coordinates are between zero and one.
185  //
186 
187  {
188  Vec3<T> en = edge0.normalized();
189  Vec3<T> a = pt - v0;
190  Vec3<T> b = v2 - v0;
191  Vec3<T> c = (a - en * (en ^ a));
192  Vec3<T> d = (b - en * (en ^ b));
193  T e = c ^ d;
194  T f = d ^ d;
195 
196  if (e >= 0 && e <= f)
197  barycentric.z = e / f;
198  else
199  return false; // outside
200  }
201 
202  {
203  Vec3<T> en = edge1.normalized();
204  Vec3<T> a = pt - v1;
205  Vec3<T> b = v0 - v1;
206  Vec3<T> c = (a - en * (en ^ a));
207  Vec3<T> d = (b - en * (en ^ b));
208  T e = c ^ d;
209  T f = d ^ d;
210 
211  if (e >= 0 && e <= f)
212  barycentric.x = e / f;
213  else
214  return false; // outside
215  }
216 
217  barycentric.y = 1 - barycentric.x - barycentric.z;
218 
219  if (barycentric.y < 0)
220  return false; // outside
221 
222  front = ((line.dir ^ normal) < 0);
223  return true;
224 }
225 
226 
227 template <class T>
228 Vec3<T>
230  (const Vec3<T> &v0,
231  const Vec3<T> &v1,
232  const Vec3<T> &v2,
233  const Line3<T> &l)
234 {
235  Vec3<T> nearest = v0;
236  T neardot = (v0 - l.closestPointTo(v0)).length2();
237 
238  T tmp = (v1 - l.closestPointTo(v1)).length2();
239 
240  if (tmp < neardot)
241  {
242  neardot = tmp;
243  nearest = v1;
244  }
245 
246  tmp = (v2 - l.closestPointTo(v2)).length2();
247  if (tmp < neardot)
248  {
249  neardot = tmp;
250  nearest = v2;
251  }
252 
253  return nearest;
254 }
255 
256 
257 template <class T>
258 Vec3<T>
260 {
261  //
262  // Rotate the point p around the line l by the given angle.
263  //
264 
265  //
266  // Form a coordinate frame with <x,y,a>. The rotation is the in xy
267  // plane.
268  //
269 
270  Vec3<T> q = l.closestPointTo(p);
271  Vec3<T> x = p - q;
272  T radius = x.length();
273 
274  x.normalize();
275  Vec3<T> y = (x % l.dir).normalize();
276 
277  T cosangle = Math<T>::cos(angle);
278  T sinangle = Math<T>::sin(angle);
279 
280  Vec3<T> r = q + x * radius * cosangle + y * radius * sinangle;
281 
282  return r;
283 }
284 
285 
287 
288 #endif // INCLUDED_IMATHLINEALGO_H
#define IMATH_INTERNAL_NAMESPACE_HEADER_EXIT
T z
Definition: ImathVec.h:275
static T sin(T x)
Definition: ImathMath.h:99
Vec3< T > pos
Definition: ImathLine.h:59
#define IMATH_INTERNAL_NAMESPACE_HEADER_ENTER
Vec3< T > closestVertex(const Vec3< T > &v0, const Vec3< T > &v1, const Vec3< T > &v2, const Line3< T > &l)
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
GLint y
Definition: glcorearb.h:102
Vec3< T > rotatePoint(const Vec3< T > p, Line3< T > l, T angle)
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
static T max()
static T cos(T x)
Definition: ImathMath.h:98
GLfloat f
Definition: glcorearb.h:1925
T x
Definition: ImathVec.h:275
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_INTERNAL_NAMESPACE_HEADER_ENTER T abs(T a)
Definition: ImathFun.h:55
Vec3< T > normalized() const
Definition: ImathVec.h:1731
T angle(const Vec2< T > &v1, const Vec2< T > &v2)
Definition: Vec2.h:480
Vec3< T > dir
Definition: ImathLine.h:60
T length() const
Definition: ImathVec.h:1663
Vec3< T > closestPointTo(const Vec3< T > &point) const
Definition: ImathLine.h:131
const Vec3 & normalize()
Definition: ImathVec.h:1682
GridType::Ptr normalize(const GridType &grid, bool threaded, InterruptT *interrupt)
Normalize the vectors of the given vector-valued grid.
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
GLfloat v0
Definition: glcorearb.h:815
GLint GLenum GLint x
Definition: glcorearb.h:408
GLfloat GLfloat v1
Definition: glcorearb.h:816
T y
Definition: ImathVec.h:275
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
GLboolean r
Definition: glcorearb.h:1221
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER bool closestPoints(const Line3< T > &line1, const Line3< T > &line2, Vec3< T > &point1, Vec3< T > &point2)
Definition: ImathLineAlgo.h:85