plane_calc.h
Go to the documentation of this file.
1 /* P L A N E _ C A L C . H
3  *
4  * Copyright (c) 2004-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20
21 /*----------------------------------------------------------------------*/
22 /* @file plane_calc.h */
24 /** @{ */
25
26 /**
27  * @brief Plane/line/point calculations
28  */
29
30 #ifndef BN_PLANE_CALC_H
31 #define BN_PLANE_CALC_H
32
33 #include "common.h"
34 #include "vmath.h"
35 #include "bn/defines.h"
36 #include "bn/plane_struct.h"
37 #include "bn/tol.h"
38
40
41 /**
42  *@brief
43  * Calculate the square of the distance of closest approach for two
44  * lines.
45  *
46  * The lines are specified as a point and a vector each. The vectors
47  * need not be unit length. P and d define one line; Q and e define
48  * the other.
49  *
50  * @return 0 - normal return
51  * @return 1 - lines are parallel, dist is set to 0.0
52  *
53  * Output values:
54  * dist is the parametric distance along the first line P + dist * d of the PCA
55  * dist is the parametric distance along the second line Q + dist * e of the PCA
56  * dist is the square of the distance between the points of closest approach
57  * pt1 is the point of closest approach on the first line
58  * pt2 is the point of closest approach on the second line
59  *
60  * This algorithm is based on expressing the distance squared, taking
61  * partials with respect to the two unknown parameters (dist and
62  * dist), setting the two partials equal to 0, and solving the two
63  * simultaneous equations
64  */
65 BN_EXPORT extern int bn_distsq_line3_line3(fastf_t dist,
66  point_t P,
67  vect_t d,
68  point_t Q,
69  vect_t e,
70  point_t pt1,
71  point_t pt2);
72
73 /**
74  * Find the distance from a point P to a line described by the
75  * endpoint A and direction dir, and the point of closest approach
76  * (PCA).
77  *
78  @code
79  P
80  *
81  /.
82  / .
83  / .
84  / . (dist)
85  / .
86  / .
87  *------*-------->
88  A PCA dir
89  @endcode
90  * There are three distinct cases, with these return codes -
91  * 0 => P is within tolerance of point A. *dist = 0, pca=A.
92  * 1 => P is within tolerance of line. *dist = 0, pca=computed.
93  * 2 => P is "above/below" line. *dist=|PCA-P|, pca=computed.
94  *
95  * TODO: For efficiency, a version of this routine that provides the
96  * distance squared would be faster.
97  */
98 BN_EXPORT extern int bn_dist_pt3_line3(fastf_t *dist,
99  point_t pca,
100  const point_t a,
101  const point_t p,
102  const vect_t dir,
103  const struct bn_tol *tol);
104
105 /**
106  * calculate intersection or closest approach of a line and a line
107  * segment.
108  *
109  * returns:
110  * -2 -> line and line segment are parallel and collinear.
111  * -1 -> line and line segment are parallel, not collinear.
112  * 0 -> intersection between points a and b.
113  * 1 -> intersection outside a and b.
114  * 2 -> closest approach is between a and b.
115  * 3 -> closest approach is outside a and b.
116  *
117  * dist is actual distance from p in d direction to
118  * closest portion of segment.
119  * dist is ratio of distance from a to b (0.0 at a, and 1.0 at b),
120  * dist may be less than 0 or greater than 1.
121  * For return values less than 0, closest approach is defined as
122  * closest to point p.
123  * Direction vector, d, must be unit length.
124  *
125  */
126 BN_EXPORT extern int bn_dist_line3_lseg3(fastf_t *dist,
127  const fastf_t *p,
128  const fastf_t *d,
129  const fastf_t *a,
130  const fastf_t *b,
131  const struct bn_tol *tol);
132
133 /**
134  * Calculate closest approach of two lines
135  *
136  * returns:
137  * -2 -> lines are parallel and do not intersect
138  * -1 -> lines are parallel and collinear
139  * 0 -> lines intersect
140  * 1 -> lines do not intersect
141  *
142  * For return values less than zero, dist is not set. For return
143  * values of 0 or 1, dist is the distance from p1 in the d1
144  * direction to the point of closest approach for that line. Similar
145  * for the second line. d1 and d2 must be unit direction vectors.
146  *
147  * XXX How is this different from bn_isect_line3_line3() ?
148  * XXX Why are the calling sequences just slightly different?
149  * XXX Can we pick the better one, and get rid of the other one?
150  * XXX If not, can we document how they differ?
151  */
152 BN_EXPORT extern int bn_dist_line3_line3(fastf_t dist,
153  const point_t p1,
154  const point_t p2,
155  const vect_t d1,
156  const vect_t d2,
157  const struct bn_tol *tol);
158
159 /**
160  *@brief
161  * Find the distance from a point P to a line segment described by the
162  * two endpoints A and B, and the point of closest approach (PCA).
163  @verbatim
164  *
165  * P
166  * *
167  * /.
168  * / .
169  * / .
170  * / . (dist)
171  * / .
172  * / .
173  * *------*--------*
174  * A PCA B
175  @endverbatim
176  *
177  * @return 0 P is within tolerance of lseg AB. *dist isn't 0: (SPECIAL!!!)
178  * *dist = parametric dist = |PCA-A| / |B-A|. pca=computed.
179  * @return 1 P is within tolerance of point A. *dist = 0, pca=A.
180  * @return 2 P is within tolerance of point B. *dist = 0, pca=B.
181  * @return 3 P is to the "left" of point A. *dist=|P-A|, pca=A.
182  * @return 4 P is to the "right" of point B. *dist=|P-B|, pca=B.
183  * @return 5 P is "above/below" lseg AB. *dist=|PCA-P|, pca=computed.
184  *
185  * This routine was formerly called bn_dist_pt_lseg().
186  *
187  * XXX For efficiency, a version of this routine that provides the
188  * XXX distance squared would be faster.
189  */
190 BN_EXPORT extern int bn_dist_pt3_lseg3(fastf_t *dist,
191  point_t pca,
192  const point_t a,
193  const point_t b,
194  const point_t p,
195  const struct bn_tol *tol);
196
197 /**
198  * PRIVATE: This is a new API and should be considered unpublished.
199  *
200  * Find the square of the distance from a point P to a line segment described
201  * by the two endpoints A and B.
202  *
203  * P
204  * *
205  * /.
206  * / .
207  * / .
208  * / . (dist)
209  * / .
210  * / .
211  * *------*--------*
212  * A PCA B
213  *
214  * There are six distinct cases, with these return codes -
215  * Return code precedence: 1, 2, 0, 3, 4, 5
216  *
217  * 0 P is within tolerance of lseg AB. *dist = 0.
218  * 1 P is within tolerance of point A. *dist = 0.
219  * 2 P is within tolerance of point B. *dist = 0.
220  * 3 PCA is within tolerance of A. *dist = |P-A|**2.
221  * 4 PCA is within tolerance of B. *dist = |P-B|**2.
222  * 5 P is "above/below" lseg AB. *dist=|PCA-P|**2.
223  *
224  * If both P and PCA and not within tolerance of lseg AB use
225  * these return codes -
226  *
227  * 3 PCA is to the left of A. *dist = |P-A|**2.
228  * 4 PCA is to the right of B. *dist = |P-B|**2.
229  *
230  * This function is a test version of "bn_distsq_pt3_lseg3".
231  *
232  */
233 BN_EXPORT extern int bn_distsq_pt3_lseg3_v2(fastf_t *distsq,
234  const fastf_t *a,
235  const fastf_t *b,
236  const fastf_t *p,
237  const struct bn_tol *tol);
238
239 /**
240  * @brief
241  * Check to see if three points are collinear.
242  *
243  * The algorithm is designed to work properly regardless of the order
244  * in which the points are provided.
245  *
246  * @return 1 If 3 points are collinear
247  * @return 0 If they are not
248  */
249 BN_EXPORT extern int bn_3pts_collinear(point_t a,
250  point_t b,
251  point_t c,
252  const struct bn_tol *tol);
253
254 /**
255  * @return 1 if the two points are equal, within the tolerance
256  * @return 0 if the two points are not "the same"
257  */
258 BN_EXPORT extern int bn_pt3_pt3_equal(const point_t a,
259  const point_t b,
260  const struct bn_tol *tol);
261
262 /**
263  *@brief
264  * Find the distance from a point P to a line segment described by the
265  * two endpoints A and B, and the point of closest approach (PCA).
266  @verbatim
267  * P
268  * *
269  * /.
270  * / .
271  * / .
272  * / . (dist)
273  * / .
274  * / .
275  * *------*--------*
276  * A PCA B
277  @endverbatim
278  * There are six distinct cases, with these return codes -
279  * @return 0 P is within tolerance of lseg AB. *dist isn't 0: (SPECIAL!!!)
280  * *dist = parametric dist = |PCA-A| / |B-A|. pca=computed.
281  * @return 1 P is within tolerance of point A. *dist = 0, pca=A.
282  * @return 2 P is within tolerance of point B. *dist = 0, pca=B.
283  * @return 3 P is to the "left" of point A. *dist=|P-A|**2, pca=A.
284  * @return 4 P is to the "right" of point B. *dist=|P-B|**2, pca=B.
285  * @return 5 P is "above/below" lseg AB. *dist=|PCA-P|**2, pca=computed.
286  *
287  *
288  * Patterned after bn_dist_pt3_lseg3().
289  */
290 BN_EXPORT extern int bn_dist_pt2_lseg2(fastf_t *dist_sq,
291  fastf_t pca,
292  const point_t a,
293  const point_t b,
294  const point_t p,
295  const struct bn_tol *tol);
296
297 /**
298  *@brief
299  * Intersect two 3D line segments, defined by two points and two
300  * vectors. The vectors are unlikely to be unit length.
301  *
302  *
303  * @return -3 missed
304  * @return -2 missed (line segments are parallel)
305  * @return -1 missed (collinear and non-overlapping)
306  * @return 0 hit (line segments collinear and overlapping)
307  * @return 1 hit (normal intersection)
308  *
309  * @param[out] dist
310  * The value at dist[] is set to the parametric distance of the
311  * intercept dist is parameter along p, range 0 to 1, to
312  * intercept. dist is parameter along q, range 0 to 1, to
313  * intercept. If within distance tolerance of the endpoints,
314  * these will be exactly 0.0 or 1.0, to ease the job of caller.
315  *
316  * CLARIFICATION: This function 'bn_isect_lseg3_lseg3'
317  * returns distance values scaled where an intersect at the start
318  * point of the line segment (within tol->dist) results in 0.0
319  * and when the intersect is at the end point of the line
320  * segment (within tol->dist), the result is 1.0. Intersects
321  * before the start point return a negative distance. Intersects
322  * after the end point result in a return value > 1.0.
323  *
324  * Special note: when return code is "0" for co-linearity, dist has
325  * an alternate interpretation: it's the parameter along p (not q)
326  * which takes you from point p to the point (q + qdir), i.e., it's
327  * the endpoint of the q linesegment, since in this case there may be
328  * *two* intersections, if q is contained within span p to (p + pdir).
329  *
330  * @param p point 1
331  * @param pdir direction-1
332  * @param q point 2
333  * @param qdir direction-2
334  * @param tol tolerance values
335  */
336 BN_EXPORT extern int bn_isect_lseg3_lseg3(fastf_t *dist,
337  const point_t p, const vect_t pdir,
338  const point_t q, const vect_t qdir,
339  const struct bn_tol *tol);
340
341 BN_EXPORT extern int bn_lseg3_lseg3_parallel(const point_t sg1pt1, const point_t sg1pt2,
342  const point_t sg2pt1, const point_t sg2pt2,
343  const struct bn_tol *tol);
344
345 /**
346  * Intersect two line segments, each in given in parametric form:
347  *
348  * X = p0 + pdist * pdir_i (i.e. line p0->p1)
349  * and
350  * X = q0 + qdist * qdir_i (i.e. line q0->q1)
351  *
352  * The input vectors 'pdir_i' and 'qdir_i' must NOT be unit vectors
353  * for this function to work correctly. The magnitude of the direction
354  * vectors indicates line segment length.
355  *
356  * The 'pdist' and 'qdist' values returned from this function are the
357  * actual distance to the intersect (i.e. not scaled). Distances may
358  * be negative, see below.
359  *
360  * @return -2 no intersection, lines are parallel.
361  * @return -1 no intersection
362  * @return 0 lines are co-linear (pdist and qdist returned) (see below)
363  * @return 1 intersection found (pdist and qdist returned) (see below)
364  *
365  * @param p0 point 1
366  * @param pdir_i direction 1
367  * @param q0 point 2
368  * @param qdir_i direction 2
369  * @param tol tolerance values
370  * @param[out] pdist, qdist (distances to intersection) (see below)
371  *
372  * When return = 1, pdist is the distance along line p0->p1 to the
373  * intersect with line q0->q1. If the intersect is along p0->p1 but
374  * in the opposite direction of vector pdir_i (i.e. occurring before
375  * p0 on line p0->p1) then the distance will be negative. The value
376  * if qdist is the same as pdist except it is the distance along line
377  * q0->q1 to the intersect with line p0->p1.
378  *
379  * When return code = 0 for co-linearity, pdist and qdist have a
380  * different meaning. pdist is the distance from point p0 to point q0
381  * and qdist is the distance from point p0 to point q1. If point q0
382  * occurs before point p0 on line segment p0->p1 then pdist will be
383  * negative. The same occurs for the distance to point q1.
384  */
385 BN_EXPORT extern int bn_isect_line3_line3(fastf_t *s, fastf_t *t,
386  const point_t p0,
387  const vect_t u,
388  const point_t q0,
389  const vect_t v,
390  const struct bn_tol *tol);
391
392 /**
393  * @brief
394  * Returns non-zero if the 3 lines are collinear to within tol->dist
395  * over the given distance range.
396  *
397  * Range should be at least one model diameter for most applications.
398  * 1e5 might be OK for a default for "vehicle sized" models.
399  *
400  * The direction vectors do not need to be unit length.
401  */
402 BN_EXPORT extern int bn_2line3_colinear(const point_t p1,
403  const vect_t d1,
404  const point_t p2,
405  const vect_t d2,
406  double range,
407  const struct bn_tol *tol);
408
409 /**
410  * @brief
411  * Intersect a point P with the line segment defined by two distinct
412  * points A and B.
413  *
414  * @return -2 P on line AB but outside range of AB,
415  * dist = distance from A to P on line.
416  * @return -1 P not on line of AB within tolerance
417  * @return 1 P is at A
418  * @return 2 P is at B
419  * @return 3 P is on AB, dist = distance from A to P on line.
420  @verbatim
421  B *
422  |
423  P'*-tol-*P
424  | / _
425  dist / /|
426  | / /
427  | / / AtoP
428  |/ /
429  A * /
430
431  tol = distance limit from line to pt P;
432  dist = distance from A to P'
433  @endverbatim
434 */
435 BN_EXPORT extern int bn_isect_pt2_lseg2(fastf_t *dist,
436  const point_t a,
437  const point_t b,
438  const point_t p,
439  const struct bn_tol *tol);
440
441 /**
442  *@brief
443  * Intersect a line in parametric form:
444  *
445  * X = P + t * D
446  *
447  * with a line segment defined by two distinct points A and B=(A+C).
448  *
449  * XXX probably should take point B, not vector C. Sigh.
450  *
451  * @return -4 A and B are not distinct points
452  * @return -3 Lines do not intersect
453  * @return -2 Intersection exists, but outside segment, < A
454  * @return -1 Intersection exists, but outside segment, > B
455  * @return 0 Lines are co-linear (special meaning of dist)
456  * @return 1 Intersection at vertex A
457  * @return 2 Intersection at vertex B (A+C)
458  * @return 3 Intersection between A and B
459  *
460  * Implicit Returns -
461  * @param dist When explicit return >= 0, t is the parameter that describes
462  * the intersection of the line and the line segment.
463  * The actual intersection coordinates can be found by
464  * solving P + t * D. However, note that for return codes
465  * 1 and 2 (intersection exactly at a vertex), it is
466  * strongly recommended that the original values passed in
467  * A or B are used instead of solving P + t * D, to prevent
468  * numeric error from creeping into the position of
469  * the endpoints.
470  *
471  * @param p point of first line
472  * @param d direction of first line
473  * @param a point of second line
474  * @param c direction of second line
475  * @param tol tolerance values
476  */
477 BN_EXPORT extern int bn_isect_line2_lseg2(fastf_t *dist,
478  const point_t p,
479  const vect_t d,
480  const point_t a,
481  const vect_t c,
482  const struct bn_tol *tol);
483
484 /**
485  *@brief
486  * Intersect two 2D line segments, defined by two points and two
487  * vectors. The vectors are unlikely to be unit length.
488  *
489  * @return -2 missed (line segments are parallel)
490  * @return -1 missed (collinear and non-overlapping)
491  * @return 0 hit (line segments collinear and overlapping)
492  * @return 1 hit (normal intersection)
493  *
494  * @param dist The value at dist[] is set to the parametric distance of the
495  * intercept.
496  *@n dist is parameter along p, range 0 to 1, to intercept.
497  *@n dist is parameter along q, range 0 to 1, to intercept.
498  *@n If within distance tolerance of the endpoints, these will be
499  * exactly 0.0 or 1.0, to ease the job of caller.
500  *
501  * Special note: when return code is "0" for co-linearity, dist has
502  * an alternate interpretation: it's the parameter along p (not q)
503  * which takes you from point p to the point (q + qdir), i.e., its
504  * the endpoint of the q linesegment, since in this case there may be
505  * *two* intersections, if q is contained within span p to (p + pdir).
506  * And either may be -10 if the point is outside the span.
507  *
508  * @param p point 1
509  * @param pdir direction1
510  * @param q point 2
511  * @param qdir direction2
512  * @param tol tolerance values
513  */
514 BN_EXPORT extern int bn_isect_lseg2_lseg2(fastf_t *dist,
515  const point_t p,
516  const vect_t pdir,
517  const point_t q,
518  const vect_t qdir,
519  const struct bn_tol *tol);
520
521 /**
522  * Intersect two lines, each in given in parametric form:
523  @verbatim
524
525  X = P + t * D
526  and
527  X = A + u * C
528
529  @endverbatim
530  *
531  * While the parametric form is usually used to denote a ray (i.e.,
532  * positive values of the parameter only), in this case the full line
533  * is considered.
534  *
535  * The direction vectors C and D need not have unit length.
536  *
537  * @return -1 no intersection, lines are parallel.
538  * @return 0 lines are co-linear
539  *@n dist gives distance from P to A,
540  *@n dist gives distance from P to (A+C) [not same as below]
541  * @return 1 intersection found (t and u returned)
542  *@n dist gives distance from P to isect,
543  *@n dist gives distance from A to isect.
544  *
545  * @param dist When explicit return > 0, dist and dist are the
546  * line parameters of the intersection point on the 2 rays. The
547  * actual intersection coordinates can be found by substituting either
548  * of these into the original ray equations.
549  *
550  * @param p point of first line
551  * @param d direction of first line
552  * @param a point of second line
553  * @param c direction of second line
554  * @param tol tolerance values
555  *
556  * Note that for lines which are very nearly parallel, but not quite
557  * parallel enough to have the determinant go to "zero", the
558  * intersection can turn up in surprising places. (e.g. when
559  * det=1e-15 and det1=5.5e-17, t=0.5)
560  */
561 BN_EXPORT extern int bn_isect_line2_line2(fastf_t *dist,
562  const point_t p,
563  const vect_t d,
564  const point_t a,
565  const vect_t c,
566  const struct bn_tol *tol);
567
568 /**
569  * @brief
570  * Returns distance between two points.
571  */
572 BN_EXPORT extern double bn_dist_pt3_pt3(const point_t a,
573  const point_t b);
574
575 /**
576  * Check to see if three points are all distinct, i.e., ensure that
577  * there is at least sqrt(dist_tol_sq) distance between every pair of
578  * points.
579  *
580  * @return 1 If all three points are distinct
581  * @return 0 If two or more points are closer together than dist_tol_sq
582  */
583 BN_EXPORT extern int bn_3pts_distinct(const point_t a,
584  const point_t b,
585  const point_t c,
586  const struct bn_tol *tol);
587
588 /**
589  * Check to see if the points are all distinct, i.e., ensure that
590  * there is at least sqrt(dist_tol_sq) distance between every pair of
591  * points.
592  *
593  * @return 1 If all the points are distinct
594  * @return 0 If two or more points are closer together than dist_tol_sq
595  */
596 BN_EXPORT extern int bn_npts_distinct(const int npts,
597  const point_t *pts,
598  const struct bn_tol *tol);
599
600 /**
601  * Find the equation of a plane that contains three points. Note that
602  * normal vector created is expected to point out (see vmath.h), so
603  * the vector from A to C had better be counter-clockwise (about the
604  * point A) from the vector from A to B. This follows the BRL-CAD
605  * outward-pointing normal convention, and the right-hand rule for
606  * cross products.
607  *
608  @verbatim
609  *
610  * C
611  * *
612  * |\
613  * | \
614  * ^ N | \
615  * | \ | \
616  * | \ | \
617  * |C-A \ | \
618  * | \ | \
619  * | \ | \
620  * \| \
621  * *---------*
622  * A B
623  * ----->
624  * B-A
625  @endverbatim
626  *
627  * If the points are given in the order A B C (e.g.,
628  * *counter*-clockwise), then the outward pointing surface normal:
629  *
630  * N = (B-A) x (C-A).
631  *
632  * @return 0 OK
633  * @return -1 Failure. At least two of the points were not distinct,
634  * or all three were collinear.
635  *
636  * @param[out] plane The plane equation is stored here.
637  * @param[in] a point 1
638  * @param[in] b point 2
639  * @param[in] c point 3
640  * @param[in] tol Tolerance values for doing calculation
641  */
642 BN_EXPORT extern int bn_mk_plane_3pts(plane_t plane,
643  const point_t a,
644  const point_t b,
645  const point_t c,
646  const struct bn_tol *tol);
647
648 /**
649  *@brief
650  * Given the description of three planes, compute the point of intersection, if
651  * any. The direction vectors of the planes need not be of unit length.
652  *
653  * Find the solution to a system of three equations in three unknowns:
654  @verbatim
655  * Px * Ax + Py * Ay + Pz * Az = -A3;
656  * Px * Bx + Py * By + Pz * Bz = -B3;
657  * Px * Cx + Py * Cy + Pz * Cz = -C3;
658  *
659  * OR
660  *
661  * [ Ax Ay Az ] [ Px ] [ -A3 ]
662  * [ Bx By Bz ] * [ Py ] = [ -B3 ]
663  * [ Cx Cy Cz ] [ Pz ] [ -C3 ]
664  *
665  @endverbatim
666  *
667  * @return 0 OK
668  * @return -1 Failure. Intersection is a line or plane.
669  *
670  * @param[out] pt The point of intersection is stored here.
671  * @param a plane 1
672  * @param b plane 2
673  * @param c plane 3
674  */
675
676 BN_EXPORT extern int bn_mkpoint_3planes(point_t pt,
677  const plane_t a,
678  const plane_t b,
679  const plane_t c);
680
681 /**
682  * Intersect an infinite line (specified in point and direction vector
683  * form) with a plane that has an outward pointing normal. The
684  * direction vector need not have unit length. The first three
685  * elements of the plane equation must form a unit length vector.
686  *
687  * @return -2 missed (ray is outside halfspace)
688  * @return -1 missed (ray is inside)
689  * @return 0 line lies on plane
690  * @return 1 hit (ray is entering halfspace)
691  * @return 2 hit (ray is leaving)
692  *
693  * @param[out] dist set to the parametric distance of the intercept
694  * @param[in] pt origin of ray
695  * @param[in] dir direction of ray
696  * @param[in] plane equation of plane
697  * @param[in] tol tolerance values
698  */
699 BN_EXPORT extern int bn_isect_line3_plane(fastf_t *dist,
700  const point_t pt,
701  const vect_t dir,
702  const plane_t plane,
703  const struct bn_tol *tol);
704
705 /**
706  *@brief
707  * Given two planes, find the line of intersection between them, if
708  * one exists. The line of intersection is returned in parametric
709  * line (point & direction vector) form.
710  *
711  * In order that all the geometry under consideration be in "front" of
712  * the ray, it is necessary to pass the minimum point of the model
713  * RPP. If this convention is unnecessary, just pass (0, 0, 0) as
714  * rpp_min.
715  *
716  * @return 0 success, line of intersection stored in 'pt' and 'dir'
717  * @return -1 planes are coplanar
718  * @return -2 planes are parallel but not coplanar
719  * @return -3 error, should be intersection but unable to find
720  *
721  * @param[out] pt Starting point of line of intersection
722  * @param[out] dir Direction vector of line of intersection (unit length)
723  * @param[in] a plane 1 (normal must be unit length)
724  * @param[in] b plane 2 (normal must be unit length)
725  * @param[in] rpp_min minimum point of model RPP
726  * @param[in] tol tolerance values
727  */
728 BN_EXPORT extern int bn_isect_2planes(point_t pt,
729  vect_t dir,
730  const plane_t a,
731  const plane_t b,
732  const vect_t rpp_min,
733  const struct bn_tol *tol);
734 BN_EXPORT extern int bn_isect_2lines(fastf_t *t,
735  fastf_t *u,
736  const point_t p,
737  const vect_t d,
738  const point_t a,
739  const vect_t c,
740  const struct bn_tol *tol);
741
742 /**
743  *@brief
744  * Intersect a line in parametric form:
745  *
746  * X = P + t * D
747  *
748  * with a line segment defined by two distinct points A and B.
749  *
750  *
751  * @return -4 A and B are not distinct points
752  * @return -3 Intersection exists, < A (t is returned)
753  * @return -2 Intersection exists, > B (t is returned)
754  * @return -1 Lines do not intersect
755  * @return 0 Lines are co-linear (t for A is returned)
756  * @return 1 Intersection at vertex A
757  * @return 2 Intersection at vertex B
758  * @return 3 Intersection between A and B
759  *
760  * @par Implicit Returns -
761  *
762  * t When explicit return >= 0, t is the parameter that describes the
763  * intersection of the line and the line segment. The actual
764  * intersection coordinates can be found by solving P + t * D.
765  * However, note that for return codes 1 and 2 (intersection exactly
766  * at a vertex), it is strongly recommended that the original values
767  * passed in A or B are used instead of solving P + t * D, to prevent
768  * numeric error from creeping into the position of the endpoints.
769  *
770  * XXX should probably be called bn_isect_line3_lseg3()
771  * XXX should probably be changed to return dist
772  */
773 BN_EXPORT extern int bn_isect_line_lseg(fastf_t *t, const point_t p,
774  const vect_t d,
775  const point_t a,
776  const point_t b,
777  const struct bn_tol *tol);
778
779 /**
780  * Given a parametric line defined by PT + t * DIR and a point A,
781  * return the closest distance between the line and the point.
782  *
783  * 'dir' need not have unit length.
784  *
785  * Find parameter for PCA along line with unitized DIR:
786  * d = VDOT(f, dir) / MAGNITUDE(dir);
787  * Find distance g from PCA to A using Pythagoras:
788  * g = sqrt(MAGSQ(f) - d**2)
789  *
790  * Return -
791  * Distance
792  */
793 BN_EXPORT extern double bn_dist_line3_pt3(const point_t pt,
794  const vect_t dir,
795  const point_t a);
796
797 /**
798  * Given a parametric line defined by PT + t * DIR and a point A,
799  * return the square of the closest distance between the line and the
800  * point.
801  *
802  * 'dir' need not have unit length.
803  *
804  * Return -
805  * Distance squared
806  */
807 BN_EXPORT extern double bn_distsq_line3_pt3(const point_t pt,
808  const vect_t dir,
809  const point_t a);
810
811 /**
812  *@brief
813  * Given a parametric line defined by PT + t * DIR, return the closest
814  * distance between the line and the origin.
815  *
816  * 'dir' need not have unit length.
817  *
818  * @return Distance
819  */
820 BN_EXPORT extern double bn_dist_line_origin(const point_t pt,
821  const vect_t dir);
822
823 /**
824  *@brief
825  * Given a parametric line defined by PT + t * DIR and a point A,
826  * return the closest distance between the line and the point.
827  *
828  * 'dir' need not have unit length.
829  *
830  * @return Distance
831  */
832 BN_EXPORT extern double bn_dist_line2_point2(const point_t pt,
833  const vect_t dir,
834  const point_t a);
835
836 /**
837  *@brief
838  * Given a parametric line defined by PT + t * DIR and a point A,
839  * return the closest distance between the line and the point,
840  * squared.
841  *
842  * 'dir' need not have unit length.
843  *
844  * @return
845  * Distance squared
846  */
847 BN_EXPORT extern double bn_distsq_line2_point2(const point_t pt,
848  const vect_t dir,
849  const point_t a);
850
851 /**
852  *@brief
853  * Returns the area of a triangle. Algorithm by Jon Leech 3/24/89.
854  */
855 BN_EXPORT extern double bn_area_of_triangle(const point_t a,
856  const point_t b,
857  const point_t c);
858
859 /**
860  *@brief
861  * Intersect a point P with the line segment defined by two distinct
862  * points A and B.
863  *
864  * @return -2 P on line AB but outside range of AB,
865  * dist = distance from A to P on line.
866  * @return -1 P not on line of AB within tolerance
867  * @return 1 P is at A
868  * @return 2 P is at B
869  * @return 3 P is on AB, dist = distance from A to P on line.
870  @verbatim
871  B *
872  |
873  P'*-tol-*P
874  | / _
875  dist / /|
876  | / /
877  | / / AtoP
878  |/ /
879  A * /
880
881  tol = distance limit from line to pt P;
882  dist = parametric distance from A to P' (in terms of A to B)
883  @endverbatim
884  *
885  * @param p point
886  * @param a start of lseg
887  * @param b end of lseg
888  * @param tol tolerance values
889  * @param[out] dist parametric distance from A to P' (in terms of A to B)
890  */
891 BN_EXPORT extern int bn_isect_pt_lseg(fastf_t *dist,
892  const point_t a,
893  const point_t b,
894  const point_t p,
895  const struct bn_tol *tol);
896
897 BN_EXPORT extern double bn_dist_pt_lseg(point_t pca,
898  const point_t a,
899  const point_t b,
900  const point_t p,
901  const struct bn_tol *tol);
902
903 /**
904  *@brief
905  * Transform a bounding box (RPP) by the given 4x4 matrix. There are
906  * 8 corners to the bounding RPP. Each one needs to be transformed
907  * and min/max'ed. This is not minimal, but does fully contain any
908  * internal object, using an axis-aligned RPP.
909  */
910 BN_EXPORT extern void bn_rotate_bbox(point_t omin,
911  point_t omax,
912  const mat_t mat,
913  const point_t imin,
914  const point_t imax);
915
916 /**
917  *@brief
918  * Transform a plane equation by the given 4x4 matrix.
919  */
920 BN_EXPORT extern void bn_rotate_plane(plane_t oplane,
921  const mat_t mat,
922  const plane_t iplane);
923
924 /**
925  *@brief
926  * Test if two planes are identical. If so, their dot products will
927  * be either +1 or -1, with the distance from the origin equal in
928  * magnitude.
929  *
930  * @return -1 not coplanar, parallel but distinct
931  * @return 0 not coplanar, not parallel. Planes intersect.
932  * @return 1 coplanar, same normal direction
933  * @return 2 coplanar, opposite normal direction
934  */
935 BN_EXPORT extern int bn_coplanar(const plane_t a,
936  const plane_t b,
937  const struct bn_tol *tol);
938
939 /**
940  * Using two perpendicular vectors (x_dir and y_dir) which lie in the
941  * same plane as 'vec', return the angle (in radians) of 'vec' from
942  * x_dir, going CCW around the perpendicular x_dir CROSS y_dir.
943  *
944  * Trig note -
945  *
946  * theta = atan2(x, y) returns an angle in the range -pi to +pi.
947  * Here, we need an angle in the range of 0 to 2pi. This could be
948  * implemented by adding 2pi to theta when theta is negative, but this
949  * could have nasty numeric ambiguity right in the vicinity of theta =
950  * +pi, which is a very critical angle for the applications using this
951  * routine.
952  *
953  * So, an alternative formulation is to compute gamma = atan2(-x, -y),
954  * and then theta = gamma + pi. Now, any error will occur in the
955  * vicinity of theta = 0, which can be handled much more readily.
956  *
957  * If theta is negative, or greater than two pi, wrap it around.
958  * These conditions only occur if there are problems in atan2().
959  *
960  * @return vec == x_dir returns 0,
961  * @return vec == y_dir returns pi/2,
962  * @return vec == -x_dir returns pi,
963  * @return vec == -y_dir returns 3*pi/2.
964  *
965  * In all cases, the returned value is between 0 and bn_twopi.
966  */
967 BN_EXPORT extern double bn_angle_measure(vect_t vec,
968  const vect_t x_dir,
969  const vect_t y_dir);
970
971 /**
972  *@brief
973  * Return the parametric distance t of a point X along a line defined
974  * as a ray, i.e. solve X = P + t * D. If the point X does not lie on
975  * the line, then t is the distance of the perpendicular projection of
976  * point X onto the line.
977  */
978 BN_EXPORT extern double bn_dist_pt3_along_line3(const point_t p,
979  const vect_t d,
980  const point_t x);
981
982 /**
983  *@brief
984  * Return the parametric distance t of a point X along a line defined
985  * as a ray, i.e. solve X = P + t * D. If the point X does not lie on
986  * the line, then t is the distance of the perpendicular projection of
987  * point X onto the line.
988  */
989 BN_EXPORT extern double bn_dist_pt2_along_line2(const point_t p,
990  const vect_t d,
991  const point_t x);
992
993 /**
994  *
995  * @return 1 if left <= mid <= right
996  * @return 0 if mid is not in the range.
997  */
998 BN_EXPORT extern int bn_between(double left,
999  double mid,
1000  double right,
1001  const struct bn_tol *tol);
1002
1003 /**
1004  * @return 0 No intersection
1005  * @return 1 Intersection, 'inter' has intersect point.
1006  */
1007 BN_EXPORT extern int bn_does_ray_isect_tri(const point_t pt,
1008  const vect_t dir,
1009  const point_t V,
1010  const point_t A,
1011  const point_t B,
1012  point_t inter);
1013
1014 /**
1015  *@brief
1016  * Classify a halfspace, specified by its plane equation, against a
1017  * bounding RPP.
1018  *
1019  * @return BN_CLASSIFY_INSIDE
1020  * @return BN_CLASSIFY_OVERLAPPING
1021  * @return BN_CLASSIFY_OUTSIDE
1022  */
1023 BN_EXPORT extern int bn_hlf_class(const plane_t half_eqn,
1024  const vect_t min, const vect_t max,
1025  const struct bn_tol *tol);
1026
1027
1028 #define BN_CLASSIFY_UNIMPLEMENTED 0x0000
1029 #define BN_CLASSIFY_INSIDE 0x0001
1030 #define BN_CLASSIFY_OVERLAPPING 0x0002
1031 #define BN_CLASSIFY_OUTSIDE 0x0003
1032
1033
1034 /**
1035  *@brief
1036  * Calculates the point that is the minimum distance from all the
1037  * planes in the "planes" array. If the planes intersect at a single
1038  * point, that point is the solution.
1039  *
1040  * The method used here is based on:
1041
1042  * An expression for the distance from a point to a plane is:
1043  * VDOT(pt, plane)-plane[H].
1044  * Square that distance and sum for all planes to get the "total"
1045  * distance.
1046  * For minimum total distance, the partial derivatives of this
1047  * expression (with respect to x, y, and z) must all be zero.
1048  * This produces a set of three equations in three unknowns (x, y, z).
1049
1050  * This routine sets up the three equations as [matrix][pt] = [hpq]
1051  * and solves by inverting "matrix" into "inverse" and
1052  * [pt] = [inverse][hpq].
1053  *
1054  * There is likely a more economical solution rather than matrix
1055  * inversion, but bn_mat_inv was handy at the time.
1056  *
1057  * Checks if these planes form a singular matrix and returns.
1058  *
1059  * @return 0 - all is well
1060  * @return 1 - planes form a singular matrix (no solution)
1061  */
1062 BN_EXPORT extern int bn_isect_planes(point_t pt,
1063  const plane_t planes[],
1064  const size_t pl_count);
1065
1067
1068 #endif /* BN_PLANE_CALC_H */
1069 /** @} */
1070 /*
1071  * Local Variables:
1072  * mode: C
1073  * tab-width: 8
1074  * indent-tabs-mode: t
1075  * c-file-style: "stroustrup"
1076  * End:
1077  * ex: shiftwidth=4 tabstop=8
1078  */
double bn_area_of_triangle(const point_t a, const point_t b, const point_t c)
Returns the area of a triangle. Algorithm by Jon Leech 3/24/89.
int bn_isect_line3_plane(fastf_t *dist, const point_t pt, const vect_t dir, const plane_t plane, const struct bn_tol *tol)
int bn_isect_line_lseg(fastf_t *t, const point_t p, const vect_t d, const point_t a, const point_t b, const struct bn_tol *tol)
Intersect a line in parametric form:
int bn_isect_pt_lseg(fastf_t *dist, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Intersect a point P with the line segment defined by two distinct points A and B. ...
int bn_coplanar(const plane_t a, const plane_t b, const struct bn_tol *tol)
Test if two planes are identical. If so, their dot products will be either +1 or -1, with the distance from the origin equal in magnitude.
if lu s
Definition: nmg_mod.c:3860
void bn_rotate_bbox(point_t omin, point_t omax, const mat_t mat, const point_t imin, const point_t imax)
Transform a bounding box (RPP) by the given 4x4 matrix. There are 8 corners to the bounding RPP...
int bn_isect_pt2_lseg2(fastf_t *dist, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Intersect a point P with the line segment defined by two distinct points A and B. ...
int bn_between(double left, double mid, double right, const struct bn_tol *tol)
Definition: plane.c:2234
double bn_distsq_line2_point2(const point_t pt, const vect_t dir, const point_t a)
Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between th...
int bn_mkpoint_3planes(point_t pt, const plane_t a, const plane_t b, const plane_t c)
Given the description of three planes, compute the point of intersection, if any. The direction vecto...
int bn_dist_line3_lseg3(fastf_t *dist, const fastf_t *p, const fastf_t *d, const fastf_t *a, const fastf_t *b, const struct bn_tol *tol)
Definition: plane.c:433
double bn_dist_pt3_along_line3(const point_t p, const vect_t d, const point_t x)
Return the parametric distance t of a point X along a line defined as a ray, i.e. solve X = P + t * D...
int bn_hlf_class(const plane_t half_eqn, const vect_t min, const vect_t max, const struct bn_tol *tol)
Classify a halfspace, specified by its plane equation, against a bounding RPP.
double bn_dist_line2_point2(const point_t pt, const vect_t dir, const point_t a)
Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between th...
int bn_isect_lseg2_lseg2(fastf_t *dist, const point_t p, const vect_t pdir, const point_t q, const vect_t qdir, const struct bn_tol *tol)
Intersect two 2D line segments, defined by two points and two vectors. The vectors are unlikely to be...
int bn_isect_line2_lseg2(fastf_t *dist, const point_t p, const vect_t d, const point_t a, const vect_t c, const struct bn_tol *tol)
Intersect a line in parametric form:
int bn_dist_pt2_lseg2(fastf_t *dist_sq, fastf_t pca, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Find the distance from a point P to a line segment described by the two endpoints A and B...
#define __BEGIN_DECLS
Definition: common.h:73
double bn_dist_line3_pt3(const point_t pt, const vect_t dir, const point_t a)
int bn_2line3_colinear(const point_t p1, const vect_t d1, const point_t p2, const vect_t d2, double range, const struct bn_tol *tol)
Returns non-zero if the 3 lines are collinear to within tol->dist over the given distance range...
int bn_lseg3_lseg3_parallel(const point_t sg1pt1, const point_t sg1pt2, const point_t sg2pt1, const point_t sg2pt2, const struct bn_tol *tol)
Definition: plane.c:2532
Support for uniform tolerances.
Definition: tol.h:71
void bn_rotate_plane(plane_t oplane, const mat_t mat, const plane_t iplane)
Transform a plane equation by the given 4x4 matrix.
int bn_isect_planes(point_t pt, const plane_t planes[], const size_t pl_count)
Calculates the point that is the minimum distance from all the planes in the "planes" array...
int bn_distsq_pt3_lseg3_v2(fastf_t *distsq, const fastf_t *a, const fastf_t *b, const fastf_t *p, const struct bn_tol *tol)
Definition: plane.c:1793
int bn_dist_line3_line3(fastf_t dist, const point_t p1, const point_t p2, const vect_t d1, const vect_t d2, const struct bn_tol *tol)
int bn_distsq_line3_line3(fastf_t dist, point_t P, vect_t d, point_t Q, vect_t e, point_t pt1, point_t pt2)
Plane/line/point calculations.
int bn_dist_pt3_line3(fastf_t *dist, point_t pca, const point_t a, const point_t p, const vect_t dir, const struct bn_tol *tol)
double bn_dist_pt3_pt3(const point_t a, const point_t b)
Returns distance between two points.
double bn_dist_pt_lseg(point_t pca, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
int bn_isect_lseg3_lseg3(fastf_t *dist, const point_t p, const vect_t pdir, const point_t q, const vect_t qdir, const struct bn_tol *tol)
Intersect two 3D line segments, defined by two points and two vectors. The vectors are unlikely to be...
int bn_3pts_collinear(point_t a, point_t b, point_t c, const struct bn_tol *tol)
Check to see if three points are collinear.
int bn_npts_distinct(const int npts, const point_t *pts, const struct bn_tol *tol)
Definition: plane.c:173
int bn_isect_line3_line3(fastf_t *s, fastf_t *t, const point_t p0, const vect_t u, const point_t q0, const vect_t v, const struct bn_tol *tol)
int bn_3pts_distinct(const point_t a, const point_t b, const point_t c, const struct bn_tol *tol)
#define A
Definition: msr.c:51
int bn_dist_pt3_lseg3(fastf_t *dist, point_t pca, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Find the distance from a point P to a line segment described by the two endpoints A and B...
double bn_angle_measure(vect_t vec, const vect_t x_dir, const vect_t y_dir)
#define __END_DECLS
Definition: common.h:74
#define Q
Definition: msr.c:54
int bn_isect_line2_line2(fastf_t *dist, const point_t p, const vect_t d, const point_t a, const vect_t c, const struct bn_tol *tol)
int bn_pt3_pt3_equal(const point_t a, const point_t b, const struct bn_tol *tol)
int bn_does_ray_isect_tri(const point_t pt, const vect_t dir, const point_t V, const point_t A, const point_t B, point_t inter)
Definition: plane.c:2263
double bn_dist_pt2_along_line2(const point_t p, const vect_t d, const point_t x)
Return the parametric distance t of a point X along a line defined as a ray, i.e. solve X = P + t * D...
int bn_isect_2planes(point_t pt, vect_t dir, const plane_t a, const plane_t b, const vect_t rpp_min, const struct bn_tol *tol)
Given two planes, find the line of intersection between them, if one exists. The line of intersection...
double bn_dist_line_origin(const point_t pt, const vect_t dir)
Given a parametric line defined by PT + t * DIR, return the closest distance between the line and the...
double fastf_t
Definition: defines.h:300
int bn_isect_2lines(fastf_t *t, fastf_t *u, const point_t p, const vect_t d, const point_t a, const vect_t c, const struct bn_tol *tol)
int bn_mk_plane_3pts(plane_t plane, const point_t a, const point_t b, const point_t c, const struct bn_tol *tol)
double bn_distsq_line3_pt3(const point_t pt, const vect_t dir, const point_t a)