Point/Line/Plane Geometry Math
[libbn (numerical functions)]

Collaboration diagram for Point/Line/Plane Geometry Math:

Files

file  plane.c
 

Some useful routines for dealing with planes and lines.


Defines

#define UNIT_SQ_TOL   1.0e-13

Functions

double bn_dist_pt3_pt3 (const fastf_t *a, const fastf_t *b)
 Returns distance between two points.
int bn_pt3_pt3_equal (const fastf_t *a, const fastf_t *b, const struct bn_tol *tol)
int bn_pt2_pt2_equal (const fastf_t *a, const fastf_t *b, const struct bn_tol *tol)
int bn_3pts_collinear (fastf_t *a, fastf_t *b, fastf_t *c, const struct bn_tol *tol)
 Check to see if three points are collinear.
int bn_3pts_distinct (const fastf_t *a, const fastf_t *b, const fastf_t *c, const struct bn_tol *tol)
int bn_npts_distinct (const int npt, const point_t *pts, const struct bn_tol *tol)
int bn_mk_plane_3pts (fastf_t *plane, const fastf_t *a, const fastf_t *b, const fastf_t *c, const struct bn_tol *tol)
int bn_mkpoint_3planes (fastf_t *pt, const fastf_t *a, const fastf_t *b, const fastf_t *c)
 Given the description of three planes, compute the point of intersection, if any. The direction vectors of the planes need not be of unit length.
int bn_2line3_colinear (const fastf_t *p1, const fastf_t *d1, const fastf_t *p2, const fastf_t *d2, double range, const struct bn_tol *tol)
 Returns non-zero if the 3 lines are colinear to within tol->dist over the given distance range.
int bn_dist_pt3_line3 (fastf_t *dist, fastf_t *pca, const fastf_t *a, const fastf_t *dir, const fastf_t *p, const struct bn_tol *tol)
int bn_dist_line3_line3 (fastf_t *dist, const fastf_t *p1, const fastf_t *d1, const fastf_t *p2, const fastf_t *d2, const struct bn_tol *tol)
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)
int bn_isect_line3_plane (fastf_t *dist, const fastf_t *pt, const fastf_t *dir, const fastf_t *plane, const struct bn_tol *tol)
int bn_isect_2planes (fastf_t *pt, fastf_t *dir, const fastf_t *a, const fastf_t *b, const fastf_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 is returned in parametric line (point & direction vector) form.
int bn_isect_line2_line2 (fastf_t *dist, const fastf_t *p, const fastf_t *d, const fastf_t *a, const fastf_t *c, const struct bn_tol *tol)
int bn_isect_line2_lseg2 (fastf_t *dist, const fastf_t *p, const fastf_t *d, const fastf_t *a, const fastf_t *c, const struct bn_tol *tol)
 Intersect a line in parametric form:
int bn_isect_lseg2_lseg2 (fastf_t *dist, const fastf_t *p, const fastf_t *pdir, const fastf_t *q, const fastf_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 unit length.
int bn_isect_lseg3_lseg3 (fastf_t *dist, const fastf_t *p, const fastf_t *pdir, const fastf_t *q, const fastf_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 unit length.
int bn_isect_line3_line3 (fastf_t *pdist, fastf_t *qdist, const fastf_t *p0, const fastf_t *pdir_i, const fastf_t *q0, const fastf_t *qdir_i, const struct bn_tol *tol)
int bn_isect_line_lseg (fastf_t *t, const fastf_t *p, const fastf_t *d, const fastf_t *a, const fastf_t *b, const struct bn_tol *tol)
 Intersect a line in parametric form:
double bn_dist_line3_pt3 (const fastf_t *pt, const fastf_t *dir, const fastf_t *a)
 Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between the line and the point.
double bn_distsq_line3_pt3 (const fastf_t *pt, const fastf_t *dir, const fastf_t *a)
double bn_dist_line_origin (const fastf_t *pt, const fastf_t *dir)
 Given a parametric line defined by PT + t * DIR, return the closest distance between the line and the origin.
double bn_dist_line2_point2 (const fastf_t *pt, const fastf_t *dir, const fastf_t *a)
 Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between the line and the point.
double bn_distsq_line2_point2 (const fastf_t *pt, const fastf_t *dir, const fastf_t *a)
 Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between the line and the point, squared.
double bn_area_of_triangle (register const fastf_t *a, register const fastf_t *b, register const fastf_t *c)
 Returns the area of a triangle. Algorithm by Jon Leech 3/24/89.
int bn_isect_pt_lseg (fastf_t *dist, const fastf_t *a, const fastf_t *b, const fastf_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_isect_pt2_lseg2 (fastf_t *dist, const fastf_t *a, const fastf_t *b, const fastf_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_dist_pt3_lseg3 (fastf_t *dist, fastf_t *pca, const fastf_t *a, const fastf_t *b, const fastf_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, and the point of closest approach (PCA).
int bn_dist_pt2_lseg2 (fastf_t *dist_sq, fastf_t *pca, const fastf_t *a, const fastf_t *b, const fastf_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, and the point of closest approach (PCA).
void bn_rotate_bbox (fastf_t *omin, fastf_t *omax, const fastf_t *mat, const fastf_t *imin, const fastf_t *imax)
 Transform a bounding box (RPP) by the given 4x4 matrix. There are 8 corners to the bounding RPP. Each one needs to be transformed and min/max'ed. This is not minimal, but does fully contain any internal object, using an axis-aligned RPP.
void bn_rotate_plane (fastf_t *oplane, const fastf_t *mat, const fastf_t *iplane)
 Transform a plane equation by the given 4x4 matrix.
int bn_coplanar (const fastf_t *a, const fastf_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.
double bn_angle_measure (fastf_t *vec, const fastf_t *x_dir, const fastf_t *y_dir)
double bn_dist_pt3_along_line3 (const fastf_t *p, const fastf_t *d, const fastf_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. If the point X does not lie on the line, then t is the distance of the perpendicular projection of point X onto the line.
double bn_dist_pt2_along_line2 (const fastf_t *p, const fastf_t *d, const fastf_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. If the point X does not lie on the line, then t is the distance of the perpendicular projection of point X onto the line.
int bn_between (double left, double mid, double right, 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)
int bn_hlf_class (const fastf_t *half_eqn, const fastf_t *min, const fastf_t *max, const struct bn_tol *tol)
 Classify a halfspace, specified by its plane equation, against a bounding RPP.
int bn_distsq_line3_line3 (fastf_t *dist, fastf_t *P, fastf_t *d_in, fastf_t *Q, fastf_t *e_in, fastf_t *pt1, fastf_t *pt2)
 Calculate the square of the distance of closest approach for two lines.
int bn_isect_planes (fastf_t *pt, const fastf_t(*planes)[4], const size_t pl_count)
 Calculates the point that is the minimum distance from all the planes in the "planes" array. If the planes intersect at a single point, that point is the solution.
int bn_isect_lseg_rpp (fastf_t *a, fastf_t *b, register fastf_t *min, register fastf_t *max)
 Intersect a line segment with a rectangular parallelpiped (RPP) that has faces parallel to the coordinate planes (a clipping RPP). The RPP is defined by a minimum point and a maximum point. This is a very close relative to rt_in_rpp() from librt/shoot.c.

Detailed Description


Define Documentation

#define UNIT_SQ_TOL   1.0e-13

Definition at line 39 of file plane.c.


Function Documentation

double bn_dist_pt3_pt3 ( const fastf_t *  a,
const fastf_t *  b 
)

Returns distance between two points.

B N _ D I S T _ P T 3 _ P T 3

Definition at line 47 of file plane.c.

References MAGNITUDE, and VSUB2.

int bn_pt3_pt3_equal ( const fastf_t *  a,
const fastf_t *  b,
const struct bn_tol tol 
)

B N _ P T 3 _ P T 3 _ E Q U A L

Returns:
1 if the two points are equal, within the tolerance
0 if the two points are not "the same"

Definition at line 63 of file plane.c.

References bn_tol::dist_sq, X, Y, and Z.

int bn_pt2_pt2_equal ( const fastf_t *  a,
const fastf_t *  b,
const struct bn_tol tol 
)

B N _ P T 2 _ P T 2 _ E Q U A L

Returns:
1 if the two points are equal, within the tolerance
0 if the two points are not "the same"

Definition at line 95 of file plane.c.

References BN_CK_TOL, bn_tol::dist_sq, MAGSQ_2D, and VSUB2_2D.

Referenced by bn_isect_line2_lseg2().

int bn_3pts_collinear ( fastf_t *  a,
fastf_t *  b,
fastf_t *  c,
const struct bn_tol tol 
)

Check to see if three points are collinear.

B N _ 3 P T S _ C O L L I N E A R The algorithm is designed to work properly regardless of the order in which the points are provided.

Returns:
1 If 3 points are collinear
0 If they are not

Definition at line 118 of file plane.c.

References MAGNITUDE, VDOT, and VSUB2.

int bn_3pts_distinct ( const fastf_t *  a,
const fastf_t *  b,
const fastf_t *  c,
const struct bn_tol tol 
)

B N _ 3 P T S _ D I S T I N C T

Check to see if three points are all distinct, i.e., ensure that there is at least sqrt(dist_tol_sq) distance between every pair of points.

Returns:
1 If all three points are distinct
0 If two or more points are closer together than dist_tol_sq

Definition at line 180 of file plane.c.

References BN_CK_TOL, bn_tol::dist_sq, MAGSQ, and VSUB2.

int bn_npts_distinct ( const int  npt,
const point_t pts,
const struct bn_tol tol 
)

B N _ N P T S _ D I S T I N C T

Check to see if the points are all distinct, i.e., ensure that there is at least sqrt(dist_tol_sq) distance between every pair of points.

Returns:
1 If all the points are distinct
0 If two or more points are closer together than dist_tol_sq

Definition at line 208 of file plane.c.

References BN_CK_TOL, bn_tol::dist_sq, MAGSQ, and VSUB2.

int bn_mk_plane_3pts ( fastf_t *  plane,
const fastf_t *  a,
const fastf_t *  b,
const fastf_t *  c,
const struct bn_tol tol 
)

B N _ M K _ P L A N E _ 3 P T S

Find the equation of a plane that contains three points. Note that normal vector created is expected to point out (see vmath.h), so the vector from A to C had better be counter-clockwise (about the point A) from the vector from A to B. This follows the BRL-CAD outward-pointing normal convention, and the right-hand rule for cross products.

 *
 *			C
 *	                *
 *	                |\
 *	                | \
 *	   ^     N      |  \
 *	   |      \     |   \
 *	   |       \    |    \
 *	   |C-A     \   |     \
 *	   |         \  |      \
 *	   |          \ |       \
 *	               \|        \
 *	                *---------*
 *	                A         B
 *			   ----->
 *		            B-A
 

If the points are given in the order A B C (e.g., *counter*-clockwise), then the outward pointing surface normal:

N = (B-A) x (C-A).

Returns:
0 OK
-1 Failure. At least two of the points were not distinct, or all three were colinear.
Parameters:
[out] plane The plane equation is stored here.
[in] a point 1
[in] b point 2
[in] c point 3
[in] tol Tolerance values for doing calcualtion

Definition at line 270 of file plane.c.

References BN_CK_TOL, bn_tol::dist_sq, MAGNITUDE, MAGSQ, VCROSS, VDOT, VSCALE, and VSUB2.

int bn_mkpoint_3planes ( fastf_t *  pt,
const fastf_t *  a,
const fastf_t *  b,
const fastf_t *  c 
)

Given the description of three planes, compute the point of intersection, if any. The direction vectors of the planes need not be of unit length.

B N _ M K P O I N T _ 3 P L A N E S Find the solution to a system of three equations in three unknowns:

 * Px * Ax + Py * Ay + Pz * Az = -A3;
 * Px * Bx + Py * By + Pz * Bz = -B3;
 * Px * Cx + Py * Cy + Pz * Cz = -C3;
 *
 * OR
 *
 * [ Ax  Ay  Az ]   [ Px ]   [ -A3 ]
 * [ Bx  By  Bz ] * [ Py ] = [ -B3 ]
 * [ Cx  Cy  Cz ]   [ Pz ]   [ -C3 ]
 *
 
Returns:
0 OK
-1 Failure. Intersection is a line or plane.
Parameters:
[out] pt The point of intersection is stored here.
a plane 1
b plane 2
c plane 3

Definition at line 335 of file plane.c.

References H, MAGNITUDE, VCROSS, VDOT, X, Y, Z, and ZERO.

int bn_2line3_colinear ( const fastf_t *  p1,
const fastf_t *  d1,
const fastf_t *  p2,
const fastf_t *  d2,
double  range,
const struct bn_tol tol 
)

Returns non-zero if the 3 lines are colinear to within tol->dist over the given distance range.

B N _ 2 L I N E 3 _ C O L I N E A R Range should be at least one model diameter for most applications. 1e5 might be OK for a default for "vehicle sized" models.

The direction vectors do not need to be unit length.

Definition at line 399 of file plane.c.

References BN_CK_TOL, bn_distsq_line3_pt3(), bn_tol::dist_sq, MAGNITUDE, VDOT, and VJOIN1.

Here is the call graph for this function:

int bn_dist_pt3_line3 ( fastf_t *  dist,
fastf_t *  pca,
const fastf_t *  a,
const fastf_t *  dir,
const fastf_t *  p,
const struct bn_tol tol 
)

Find the distance from a point P to a line described by the endpoint A and direction dir, and the point of closest approach (PCA).

                        P

                      /.
                     / .
                    /  .
                   /   . (dist)
                  /    .
                 /     .
                *------*-------->
                A      PCA    dir

There are three distinct cases, with these return codes - 0 => P is within tolerance of point A. *dist = 0, pca=A. 1 => P is within tolerance of line. *dist = 0, pca=computed. 2 => P is "above/below" line. *dist=|PCA-P|, pca=computed.

TODO: For efficiency, a version of this routine that provides the distance squared would be faster.

Definition at line 471 of file plane.c.

References BN_CK_TOL, MAGSQ, UNLIKELY, V3ARGS, VDOT, VJOIN1, VMOVE, VSUB2, and VUNITIZE.

int bn_dist_line3_line3 ( fastf_t *  dist,
const fastf_t *  p1,
const fastf_t *  d1,
const fastf_t *  p2,
const fastf_t *  d2,
const struct bn_tol tol 
)

Calculate closest approach of two lines

returns: -2 -> lines are parallel and do not intersect -1 -> lines are parallel and collinear 0 -> lines intersect 1 -> lines do not intersect

For return values less than zero, dist is not set. For return valuse of 0 or 1, dist[0] is the distance from p1 in the d1 direction to the point of closest approach for that line. Similar for the second line. d1 and d2 must be unit direction vectors.

XXX How is this different from bn_isect_line3_line3() ? XXX Why are the calling sequences just slightly different? XXX Can we pick the better one, and get rid of the other one? XXX If not, can we document how they differ?

Definition at line 537 of file plane.c.

References BN_CK_TOL, bn_dist_line3_pt3(), BN_VECT_ARE_PARALLEL, bn_tol::dist, bn_tol::dist_sq, MAGNITUDE, MAGSQ, NEAR_EQUAL, V3ARGS, VDOT, VJOIN1, and VSUB2.

Here is the call graph for this function:

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 
)

calculate intersection or closest approach of a line and a line segement.

returns: -2 -> line and line segment are parallel and collinear. -1 -> line and line segment are parallel, not collinear. 0 -> intersection between points a and b. 1 -> intersection outside a and b. 2 -> closest approach is between a and b. 3 -> closest approach is outside a and b.

dist[0] is actual distance from p in d direction to closest portion of segment. dist[1] is ratio of distance from a to b (0.0 at a, and 1.0 at b), dist[1] may be less than 0 or greater than 1. For return values less than 0, closest approach is defined as closest to point p. Direction vector, d, must be unit length.

Definition at line 616 of file plane.c.

References BN_CK_TOL, bn_dist_line3_line3(), bn_tol::dist, MAGNITUDE, VDOT, VSCALE, and VSUB2.

Here is the call graph for this function:

int bn_isect_line3_plane ( fastf_t *  dist,
const fastf_t *  pt,
const fastf_t *  dir,
const fastf_t *  plane,
const struct bn_tol tol 
)

B N _ I S E C T _ L I N E 3 _ P L A N E

Intersect an infinite line (specified in point and direction vector form) with a plane that has an outward pointing normal. The direction vector need not have unit length. The first three elements of the plane equation must form a unit lengh vector.

Returns:
-2 missed (ray is outside halfspace)
-1 missed (ray is inside)
0 line lies on plane
1 hit (ray is entering halfspace)
2 hit (ray is leaving)
Parameters:
[out] dist set to the parametric distance of the intercept
[in] pt origin of ray
[in] dir direction of ray
[in] plane equation of plane
[in] tol tolerance values

Definition at line 689 of file plane.c.

References BN_CK_TOL, bn_tol::dist, bn_tol::perp, VDOT, VMOVE, and VUNITIZE.

int bn_isect_2planes ( fastf_t *  pt,
fastf_t *  dir,
const fastf_t *  a,
const fastf_t *  b,
const fastf_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 is returned in parametric line (point & direction vector) form.

B N _ I S E C T _ 2 P L A N E S In order that all the geometry under consideration be in "front" of the ray, it is necessary to pass the minimum point of the model RPP. If this convention is unnecessary, just pass (0, 0, 0) as rpp_min.

Returns:
0 success, line of intersection stored in 'pt' and 'dir'
-1 planes are coplanar
-2 planes are parallel but not coplanar
-3 error, should be intersection but unable to find
Parameters:
[out] pt Starting point of line of intersection
[out] dir Direction vector of line of intersection (unit length)
[in] a plane 1 (normal must be unit length)
[in] b plane 2 (normal must be unit length)
[in] rpp_min minimum poit of model RPP
[in] tol tolerance values

Definition at line 753 of file plane.c.

References bn_coplanar(), bn_mkpoint_3planes(), VCROSS, VREVERSE, VSET, VSETALL, W, X, Y, Z, and ZERO.

Here is the call graph for this function:

int bn_isect_line2_line2 ( fastf_t *  dist,
const fastf_t *  p,
const fastf_t *  d,
const fastf_t *  a,
const fastf_t *  c,
const struct bn_tol tol 
)

B N _ I S E C T _ L I N E 2 _ L I N E 2

Intersect two lines, each in given in parametric form:


 X = P + t * D
 and
 X = A + u * C

 

While the parametric form is usually used to denote a ray (ie, positive values of the parameter only), in this case the full line is considered.

The direction vectors C and D need not have unit length.

Returns:
-1 no intersection, lines are parallel.
0 lines are co-linear
dist[0] gives distance from P to A,
dist[1] gives distance from P to (A+C) [not same as below]
1 intersection found (t and u returned)
dist[0] gives distance from P to isect,
dist[1] gives distance from A to isect.
Parameters:
dist When explicit return > 0, dist[0] and dist[1] are the line parameters of the intersection point on the 2 rays. The actual intersection coordinates can be found by substituting either of these into the original ray equations.
p point of first line
d direction of first line
a point of second line
c direction of second line
tol tolerance values

Note that for lines which are very nearly parallel, but not quite parallel enough to have the determinant go to "zero", the intersection can turn up in surprising places. (e.g. when det=1e-15 and det1=5.5e-17, t=0.5)

Definition at line 882 of file plane.c.

References BN_CK_TOL, DETERMINANT_TOL, NEAR_ZERO, bn_tol::para, V2ARGS, VDOT, VUNITIZE, X, and Y.

int bn_isect_line2_lseg2 ( fastf_t *  dist,
const fastf_t *  p,
const fastf_t *  d,
const fastf_t *  a,
const fastf_t *  c,
const struct bn_tol tol 
)

Intersect a line in parametric form:

B N _ I S E C T _ L I N E 2 _ L S E G 2 X = P + t * D

with a line segment defined by two distinct points A and B=(A+C).

XXX probably should take point B, not vector C. Sigh.

Returns:
-4 A and B are not distinct points
-3 Lines do not intersect
-2 Intersection exists, but outside segemnt, < A
-1 Intersection exists, but outside segment, > B
0 Lines are co-linear (special meaning of dist[1])
1 Intersection at vertex A
2 Intersection at vertex B (A+C)
3 Intersection between A and B

Implicit Returns -

Parameters:
dist When explicit return >= 0, t is the parameter that describes the intersection of the line and the line segment. The actual intersection coordinates can be found by solving P + t * D. However, note that for return codes 1 and 2 (intersection exactly at a vertex), it is strongly recommended that the original values passed in A or B are used instead of solving P + t * D, to prevent numeric error from creeping into the position of the endpoints.
p point of first line
d direction of first line
a point of second line
c direction of second line
tol tolerance values

Definition at line 1073 of file plane.c.

References bn_between(), BN_CK_TOL, bn_dist_pt2_along_line2(), bn_distsq_line2_point2(), bn_isect_line2_line2(), bn_isect_pt2_lseg2(), bn_pt2_pt2_equal(), bn_tol::dist, bn_tol::dist_sq, MAGSQ_2D, V2ARGS, V2PRINT, VADD2_2D, VJOIN1_2D, X, and Y.

Here is the call graph for this function:

int bn_isect_lseg2_lseg2 ( fastf_t *  dist,
const fastf_t *  p,
const fastf_t *  pdir,
const fastf_t *  q,
const fastf_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 unit length.

B N _ I S E C T _ L S E G 2 _ L S E G 2

Returns:
-2 missed (line segments are parallel)
-1 missed (colinear and non-overlapping)
0 hit (line segments colinear and overlapping)
1 hit (normal intersection)
Parameters:
dist The value at dist[] is set to the parametric distance of the intercept.
dist[0] is parameter along p, range 0 to 1, to intercept.
dist[1] is parameter along q, range 0 to 1, to intercept.
If within distance tolerance of the endpoints, these will be exactly 0.0 or 1.0, to ease the job of caller.

Special note: when return code is "0" for co-linearity, dist[1] has an alternate interpretation: it's the parameter along p (not q) which takes you from point p to the point (q + qdir), i.e., its the endpoint of the q linesegment, since in this case there may be *two* intersections, if q is contained within span p to (p + pdir). And either may be -10 if the point is outside the span.

Parameters:
p point 1
pdir direction1
q point 2
qdir direction2
tol tolerance values

Definition at line 1277 of file plane.c.

References BN_CK_TOL, bn_isect_line2_line2(), bn_tol::dist, MAGSQ_2D, and V2ARGS.

Here is the call graph for this function:

int bn_isect_lseg3_lseg3 ( fastf_t *  dist,
const fastf_t *  p,
const fastf_t *  pdir,
const fastf_t *  q,
const fastf_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 unit length.

B N _ I S E C T _ L S E G 3 _ L S E G 3

Returns:
-3 missed
-2 missed (line segments are parallel)
-1 missed (colinear and non-overlapping)
0 hit (line segments colinear and overlapping)
1 hit (normal intersection)
Parameters:
[out] dist The value at dist[] is set to the parametric distance of the intercept dist[0] is parameter along p, range 0 to 1, to intercept. dist[1] is parameter along q, range 0 to 1, to intercept. If within distance tolerance of the endpoints, these will be exactly 0.0 or 1.0, to ease the job of caller.

CLARIFICATION: This function 'bn_isect_lseg3_lseg3' returns distance values scaled where an intersect at the start point of the line segement (within tol->dist) results in 0.0 and when the intersect is at the end point of the line segement (within tol->dist), the result is 1.0. Intersects before the start point return a negative distance. Intersects after the end point result in a return value > 1.0.

Special note: when return code is "0" for co-linearity, dist[1] has an alternate interpretation: it's the parameter along p (not q) which takes you from point p to the point (q + qdir), i.e., it's the endpoint of the q linesegment, since in this case there may be *two* intersections, if q is contained within span p to (p + pdir).

Parameters:
p point 1
pdir direction-1
q point 2
qdir direction-2
tol tolerance values

Definition at line 1388 of file plane.c.

References BN_CK_TOL, bn_isect_line3_line3(), bn_tol::dist, MAGNITUDE, UNLIKELY, and V3ARGS.

Here is the call graph for this function:

int bn_isect_line3_line3 ( fastf_t *  pdist,
fastf_t *  qdist,
const fastf_t *  p0,
const fastf_t *  pdir_i,
const fastf_t *  q0,
const fastf_t *  qdir_i,
const struct bn_tol tol 
)

B N _ I S E C T _ L I N E 3 _ L I N E 3

Intersect two line segments, each in given in parametric form:

X = p0 + pdist * pdir_i (i.e. line p0->p1) and X = q0 + qdist * qdir_i (i.e. line q0->q1)

The input vectors 'pdir_i' and 'qdir_i' must NOT be unit vectors for this function to work correctly. The magnitude of the direction vectors indicates line segment length.

The 'pdist' and 'qdist' values returned from this function are the actual distance to the intersect (i.e. not scaled). Distances may be negative, see below.

Returns:
-2 no intersection, lines are parallel.
-1 no intersection
0 lines are co-linear (pdist and qdist returned) (see below)
1 intersection found (pdist and qdist returned) (see below)
Parameters:
p0 point 1
pdir_i direction 1
q0 point 2
qdir_i direction 2
tol tolerance values
[out] pdist,qdist (distances to intersection) (see below)

When return = 1, pdist is the distance along line p0->p1 to the intersect with line q0->q1. If the intersect is along p0->p1 but in the opposite direction of vector pdir_i (i.e. occuring before p0 on line p0->p1) then the distance will be negative. The value if qdist is the same as pdist except it is the distance along line q0->q1 to the intersect with line p0->p1.

When return code = 0 for co-linearity, pdist and qdist have a different meaning. pdist is the distance from point p0 to point q0 and qdist is the distance from point p0 to point q1. If point q0 occurs before point p0 on line segment p0->p1 then pdist will be negative. The same occurs for the distance to point q1.

Parameters:
pdist see above
qdist see above
p0 line p start point
pdir_i line p direction, must not be unit vector
q0 line q start point
qdir_i line q direction, must not be unit vector

Definition at line 1574 of file plane.c.

References bn_distsq_line3_pt3(), bn_tol::dist_sq, MAGNITUDE, MAGSQ, NEAR_EQUAL, NEAR_ZERO, UNLIKELY, V3ARGS, VADD2, VDOT, VMOVE, VSCALE, and VSUB2.

Here is the call graph for this function:

int bn_isect_line_lseg ( fastf_t *  t,
const fastf_t *  p,
const fastf_t *  d,
const fastf_t *  a,
const fastf_t *  b,
const struct bn_tol tol 
)

Intersect a line in parametric form:

B N _ I S E C T _ L I N E _ L S E G X = P + t * D

with a line segment defined by two distinct points A and B.

Returns:
-4 A and B are not distinct points
-3 Intersection exists, < A (t is returned)
-2 Intersection exists, > B (t is returned)
-1 Lines do not intersect
0 Lines are co-linear (t for A is returned)
1 Intersection at vertex A
2 Intersection at vertex B
3 Intersection between A and B
Implicit Returns -

t When explicit return >= 0, t is the parameter that describes the intersection of the line and the line segment. The actual intersection coordinates can be found by solving P + t * D. However, note that for return codes 1 and 2 (intersection exactly at a vertex), it is strongly recommended that the original values passed in A or B are used instead of solving P + t * D, to prevent numeric error from creeping into the position of the endpoints.

XXX should probably be called bn_isect_line3_lseg3() XXX should probably be changed to return dist[2]

Definition at line 1738 of file plane.c.

References BN_CK_TOL, bn_distsq_line3_pt3(), bn_isect_line3_line3(), bn_tol::dist, bn_tol::dist_sq, MAGNITUDE, MAGSQ, NEAR_ZERO, UNLIKELY, VDOT, VMOVE, VSCALE, VSUB2, and VUNITIZE.

Here is the call graph for this function:

double bn_dist_line3_pt3 ( const fastf_t *  pt,
const fastf_t *  dir,
const fastf_t *  a 
)

Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between the line and the point.

B N _ D I S T _ L I N E 3_ P T 3 'dir' need not have unit length.

Find parameter for PCA along line with unitized DIR: d = VDOT(f, dir) / MAGNITUDE(dir); Find distance g from PCA to A using Pythagoras: g = sqrt(MAGSQ(f) - d**2)

Return - Distance

Definition at line 1946 of file plane.c.

References MAGNITUDE, MAGSQ, VDOT, and VSUB2.

double bn_distsq_line3_pt3 ( const fastf_t *  pt,
const fastf_t *  dir,
const fastf_t *  a 
)

B N _ D I S T S Q _ L I N E 3 _ P T 3

Given a parametric line defined by PT + t * DIR and a point A, return the square of the closest distance between the line and the point.

'dir' need not have unit length.

Return - Distance squared

Definition at line 1984 of file plane.c.

References MAGNITUDE, UNLIKELY, VDOT, VSUB2, and ZERO.

double bn_dist_line_origin ( const fastf_t *  pt,
const fastf_t *  dir 
)

Given a parametric line defined by PT + t * DIR, return the closest distance between the line and the origin.

B N _ D I S T _ L I N E _ O R I G I N 'dir' need not have unit length.

Returns:
Distance

Definition at line 2019 of file plane.c.

References MAGNITUDE, and VDOT.

double bn_dist_line2_point2 ( const fastf_t *  pt,
const fastf_t *  dir,
const fastf_t *  a 
)

Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between the line and the point.

B N _ D I S T _ L I N E 2 _ P O I N T 2 'dir' need not have unit length.

Returns:
Distance

Definition at line 2043 of file plane.c.

References MAGSQ_2D, VDOT_2D, and VSUB2_2D.

double bn_distsq_line2_point2 ( const fastf_t *  pt,
const fastf_t *  dir,
const fastf_t *  a 
)

Given a parametric line defined by PT + t * DIR and a point A, return the closest distance between the line and the point, squared.

B N _ D I S T S Q _ L I N E 2 _ P O I N T 2 'dir' need not have unit length.

Returns:
Distance squared

Definition at line 2071 of file plane.c.

References MAGSQ_2D, VDOT_2D, and VSUB2_2D.

double bn_area_of_triangle ( register const fastf_t *  a,
register const fastf_t *  b,
register const fastf_t *  c 
)

Returns the area of a triangle. Algorithm by Jon Leech 3/24/89.

B N _ A R E A _ O F _ T R I A N G L E

Definition at line 2092 of file plane.c.

References X, Y, and Z.

int bn_isect_pt_lseg ( fastf_t *  dist,
const fastf_t *  a,
const fastf_t *  b,
const fastf_t *  p,
const struct bn_tol tol 
)

Intersect a point P with the line segment defined by two distinct points A and B.

B N _ I S E C T _ P T _ L S E G

Returns:
-2 P on line AB but outside range of AB, dist = distance from A to P on line.
-1 P not on line of AB within tolerance
1 P is at A
2 P is at B
3 P is on AB, dist = distance from A to P on line.
 B *
 |
 P'*-tol-*P
 |    /   _
 dist  /   /|
 |  /   /
 | /   / AtoP
 |/   /
 A *   /

 tol = distance limit from line to pt P;
 dist = parametric distance from A to P' (in terms of A to B)
 
Parameters:
p point
a start of lseg
b end of lseg
tol tolerance values
[out] dist parametric distance from A to P' (in terms of A to B)

Definition at line 2147 of file plane.c.

References BN_CK_TOL, bn_tol::dist_sq, MAGSQ, VDOT, VMOVE, VSCALE, and VSUB2.

int bn_isect_pt2_lseg2 ( fastf_t *  dist,
const fastf_t *  a,
const fastf_t *  b,
const fastf_t *  p,
const struct bn_tol tol 
)

Intersect a point P with the line segment defined by two distinct points A and B.

B N _ I S E C T _ P T 2 _ L S E G 2

Returns:
-2 P on line AB but outside range of AB, dist = distance from A to P on line.
-1 P not on line of AB within tolerance
1 P is at A
2 P is at B
3 P is on AB, dist = distance from A to P on line.
 B *
 |
 P'*-tol-*P
 |    /  _
 dist  /   /|
 |  /   /
 | /   / AtoP
 |/   /
 A *   /

 tol = distance limit from line to pt P;
 dist = distance from A to P'
 

Definition at line 2231 of file plane.c.

References BN_CK_TOL, bn_tol::dist_sq, MAGSQ_2D, V2PRINT, VDOT_2D, VMOVE_2D, VSCALE_2D, and VSUB2_2D.

int bn_dist_pt3_lseg3 ( fastf_t *  dist,
fastf_t *  pca,
const fastf_t *  a,
const fastf_t *  b,
const fastf_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, and the point of closest approach (PCA).

B N _ D I S T _ P T 3 _ L S E G 3

 *
 *			P
 *		       *
 *		      /.
 *		     / .
 *		    /  .
 *		   /   . (dist)
 *		  /    .
 *		 /     .
 *		*------*--------*
 *		A      PCA	B
 
Returns:
0 P is within tolerance of lseg AB. *dist isn't 0: (SPECIAL!!!) *dist = parametric dist = |PCA-A| / |B-A|. pca=computed.
1 P is within tolerance of point A. *dist = 0, pca=A.
2 P is within tolerance of point B. *dist = 0, pca=B.
3 P is to the "left" of point A. *dist=|P-A|, pca=A.
4 P is to the "right" of point B. *dist=|P-B|, pca=B.
5 P is "above/below" lseg AB. *dist=|PCA-P|, pca=computed.

This routine was formerly called bn_dist_pt_lseg().

XXX For efficiency, a version of this routine that provides the XXX distance squared would be faster.

Definition at line 2327 of file plane.c.

References BN_CK_TOL, bn_tol::dist, bn_tol::dist_sq, MAGSQ, UNLIKELY, V3ARGS, VDOT, VJOIN1, VMOVE, and VSUB2.

int bn_dist_pt2_lseg2 ( fastf_t *  dist_sq,
fastf_t *  pca,
const fastf_t *  a,
const fastf_t *  b,
const fastf_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, and the point of closest approach (PCA).

B N _ D I S T _ P T 2 _ L S E G 2

 *			P
 *		       *
 *		      /.
 *		     / .
 *		    /  .
 *		   /   . (dist)
 *		  /    .
 *		 /     .
 *		*------*--------*
 *		A      PCA	B
 

There are six distinct cases, with these return codes -

Returns:
0 P is within tolerance of lseg AB. *dist isn't 0: (SPECIAL!!!) *dist = parametric dist = |PCA-A| / |B-A|. pca=computed.
1 P is within tolerance of point A. *dist = 0, pca=A.
2 P is within tolerance of point B. *dist = 0, pca=B.
3 P is to the "left" of point A. *dist=|P-A|**2, pca=A.
4 P is to the "right" of point B. *dist=|P-B|**2, pca=B.
5 P is "above/below" lseg AB. *dist=|PCA-P|**2, pca=computed.

Patterned after bn_dist_pt3_lseg3().

Definition at line 2449 of file plane.c.

References BN_CK_TOL, bn_tol::dist, bn_tol::dist_sq, MAGSQ_2D, V2JOIN1, V2MOVE, V3ARGS, VDOT_2D, and VSUB2_2D.

void bn_rotate_bbox ( fastf_t *  omin,
fastf_t *  omax,
const fastf_t *  mat,
const fastf_t *  imin,
const fastf_t *  imax 
)

Transform a bounding box (RPP) by the given 4x4 matrix. There are 8 corners to the bounding RPP. Each one needs to be transformed and min/max'ed. This is not minimal, but does fully contain any internal object, using an axis-aligned RPP.

B N _ R O T A T E _ B B O X

Definition at line 2546 of file plane.c.

References ROT_VERT.

void bn_rotate_plane ( fastf_t *  oplane,
const fastf_t *  mat,
const fastf_t *  iplane 
)

Transform a plane equation by the given 4x4 matrix.

B N _ R O T A T E _ P L A N E

Definition at line 2575 of file plane.c.

References MAT4X3PNT, MAT4X3VEC, VDOT, and VSCALE.

int bn_coplanar ( const fastf_t *  a,
const fastf_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.

B N _ C O P L A N A R

Returns:
-1 not coplanar, parallel but distinct
0 not coplanar, not parallel. Planes intersect.
1 coplanar, same normal direction
2 coplanar, opposite normal direction

Definition at line 2610 of file plane.c.

References BN_CK_TOL, bn_pt3_pt3_equal(), MAGSQ, NEAR_EQUAL, NEAR_ZERO, bn_tol::perp, VDOT, VSCALE, VUNITIZE_TOL, and W.

Here is the call graph for this function:

double bn_angle_measure ( fastf_t *  vec,
const fastf_t *  x_dir,
const fastf_t *  y_dir 
)

B N _ A N G L E _ M E A S U R E

Using two perpendicular vectors (x_dir and y_dir) which lie in the same plane as 'vec', return the angle (in radians) of 'vec' from x_dir, going CCW around the perpendicular x_dir CROSS y_dir.

Trig note -

theta = atan2(x, y) returns an angle in the range -pi to +pi. Here, we need an angle in the range of 0 to 2pi. This could be implemented by adding 2pi to theta when theta is negative, but this could have nasty numeric ambiguity right in the vicinity of theta = +pi, which is a very critical angle for the applications using this routine.

So, an alternative formulation is to compute gamma = atan2(-x, -y), and then theta = gamma + pi. Now, any error will occur in the vicinity of theta = 0, which can be handled much more readily.

If theta is negative, or greater than two pi, wrap it around. These conditions only occur if there are problems in atan2().

Returns:
vec == x_dir returns 0,
vec == y_dir returns pi/2,
vec == -x_dir returns pi,
vec == -y_dir returns 3*pi/2.

In all cases, the returned value is between 0 and bn_twopi.

Definition at line 2678 of file plane.c.

References bn_pi, bn_twopi, UNLIKELY, and VDOT.

double bn_dist_pt3_along_line3 ( const fastf_t *  p,
const fastf_t *  d,
const fastf_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. If the point X does not lie on the line, then t is the distance of the perpendicular projection of point X onto the line.

B N _ D I S T _ P T 3 _ A L O N G _ L I N E 3

Definition at line 2713 of file plane.c.

References VDOT, and VSUB2.

double bn_dist_pt2_along_line2 ( const fastf_t *  p,
const fastf_t *  d,
const fastf_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. If the point X does not lie on the line, then t is the distance of the perpendicular projection of point X onto the line.

B N _ D I S T _ P T 2 _ A L O N G _ L I N E 2

Definition at line 2731 of file plane.c.

References V2ARGS, VDOT_2D, and VSUB2_2D.

int bn_between ( double  left,
double  mid,
double  right,
const struct bn_tol tol 
)
Returns:
1 if left <= mid <= right
0 if mid is not in the range.

Definition at line 2755 of file plane.c.

References BN_CK_TOL, bn_tol::dist, and NEAR_EQUAL.

Referenced by bn_isect_line2_lseg2().

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 
)

B N _ D O E S _ R A Y _ I S E C T _ T R I

Returns:
0 No intersection
1 Intersection, 'inter' has intersect point.

Definition at line 2790 of file plane.c.

References N, VCROSS, VDOT, VJOIN1, VSUB2, VUNITIZE, W, and ZERO.

int bn_hlf_class ( const fastf_t *  half_eqn,
const fastf_t *  min,
const fastf_t *  max,
const struct bn_tol tol 
)

Classify a halfspace, specified by its plane equation, against a bounding RPP.

B N _ H L F _ C L A S S

Returns:
BN_CLASSIFY_INSIDE
BN_CLASSIFY_OVERLAPPING
BN_CLASSIFY_OUTSIDE

Definition at line 2958 of file plane.c.

References BN_CLASSIFY_UNIMPLEMENTED, CHECK_PT, V3ARGS, X, Y, and Z.

int bn_distsq_line3_line3 ( fastf_t *  dist,
fastf_t *  P,
fastf_t *  d_in,
fastf_t *  Q,
fastf_t *  e_in,
fastf_t *  pt1,
fastf_t *  pt2 
)

Calculate the square of the distance of closest approach for two lines.

B N _ D I S T S Q _ L I N E 3 _ L I N E 3 The lines are specifed as a point and a vector each. The vectors need not be unit length. P and d define one line; Q and e define the other.

Returns:
0 - normal return
1 - lines are parallel, dist[0] is set to 0.0

Output values: dist[0] is the parametric distance along the first line P + dist[0] * d of the PCA dist[1] is the parametric distance along the second line Q + dist[1] * e of the PCA dist[3] is the square of the distance between the points of closest approach pt1 is the point of closest approach on the first line pt2 is the point of closest approach on the second line

This algoritm is based on expressing the distance sqaured, taking partials with respect to the two unknown parameters (dist[0] and dist[1]), seeting the two partails equal to 0, and solving the two simutaneous equations

Definition at line 3018 of file plane.c.

References MAGNITUDE, MAGSQ, VBLEND2, VDOT, VJOIN1, VSCALE, VSUB2, and ZERO.

int bn_isect_planes ( fastf_t *  pt,
const fastf_t(*)  planes[4],
const size_t  pl_count 
)

Calculates the point that is the minimum distance from all the planes in the "planes" array. If the planes intersect at a single point, that point is the solution.

B N _ I S E C T _ P L A N E S The method used here is based on:

An expression for the distance from a point to a plane is: VDOT(pt, plane)-plane[H]. Square that distance and sum for all planes to get the "total" distance. For minimum total distance, the partial derivatives of this expression (with respect to x, y, and z) must all be zero. This produces a set of three equations in three unknowns (x, y, z).

This routine sets up the three equations as [matrix][pt] = [hpq] and solves by inverting "matrix" into "inverse" and [pt] = [inverse][hpq].

There is likely a more economical solution rather than matrix inversion, but bn_mat_inv was handy at the time.

Checks if these planes form a singular matrix and returns.

Returns:
0 - all is well
1 - planes form a singular matrix (no solution)

Definition at line 3098 of file plane.c.

References bn_mat_determinant(), bn_mat_inv(), H, MAT4X3PNT, MAT_ZERO, V4ARGS, VSET, X, Y, Z, and ZERO.

Here is the call graph for this function:

int bn_isect_lseg_rpp ( fastf_t *  a,
fastf_t *  b,
register fastf_t *  min,
register fastf_t *  max 
)

Intersect a line segment with a rectangular parallelpiped (RPP) that has faces parallel to the coordinate planes (a clipping RPP). The RPP is defined by a minimum point and a maximum point. This is a very close relative to rt_in_rpp() from librt/shoot.c.

B N _ I S E C T _ L S E G _ R P P

Returns:
0 if ray does not hit RPP,
!0 if ray hits RPP.
Parameters:
[in,out] a Start point of lseg
[in,out] b End point of lseg
[in] min min point of RPP
[in] max amx point of RPP

if !0 was returned, "a" and "b" have been clipped to the RPP.

Definition at line 3166 of file plane.c.

References VJOIN1, and VSUB2.

Generated on Tue Dec 11 13:14:29 2012 for LIBBN by  doxygen 1.6.3