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_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.
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_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 t, fastf_t u, const fastf_t p, const fastf_t d, const fastf_t a, const fastf_t c, 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 int 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.

Define Documentation

#define UNIT_SQ_TOL 1.0e-13

Definition at line 57 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 65 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 81 of file plane.c.
References BN_CK_TOL, bn_tol::dist_sq, MAGSQ, and VSUB2.

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 99 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 121 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 187 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 (eg, *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 247 of file plane.c.
References BN_CK_TOL, bu_log(), bn_tol::dist_sq, MAGNITUDE, MAGSQ, SMALL_FASTF, VCROSS, VDOT, VSCALE, and VSUB2.
Here is the call graph for this function:

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.
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 323 of file plane.c.
References NEAR_ZERO, SMALL_FASTF, VCROSS, VDOT, X, Y, and Z.

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 361 of file plane.c.
References BN_CK_TOL, bn_distsq_line3_pt3(), bu_bomb(), bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist_sq, MAGNITUDE, SMALL_FASTF, tail, VDOT, and VJOIN1.
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 425 of file plane.c.
References BN_CK_TOL, bn_tol::dist, bn_tol::perp, SMALL_FASTF, 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 OK, line of intersection stored in `pt' and `dir'.
-1 FAIL, planes are identical (co-planar)
-2 FAIL, planes are parallel and distinct
-3 FAIL, unable to find line of intersection

Parameters:

[out] pt Starting point of line of intersection

[out] dir Direction vector of line of intersection (unit length)

[in] a plane 1

[in] b plane 2

[in] rpp_min minimum poit of model RPP

[in] tol tolerance values

Definition at line 490 of file plane.c.
References bn_coplanar(), bn_mkpoint_3planes(), LOCAL, VCROSS, VREVERSE, VSET, VUNITIZE, X, Y, and Z.
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 602 of file plane.c.
References BN_CK_TOL, bu_debug, BU_DEBUG_MATH, bu_log(), DETERMINANT_TOL, bn_tol::dist, bn_tol::dist_sq, MAGSQ_2D, NEAR_ZERO, bn_tol::para, V2ARGS, VDOT, VJOIN1_2D, VSUB2_2D, VUNITIZE, X, and Y.
Here is the call graph for this function:

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 825 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(), bu_bomb(), bu_debug, BU_DEBUG_MATH, bu_log(), 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., 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). 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 1036 of file plane.c.
References BN_CK_TOL, bn_isect_line2_line2(), bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist, MAGSQ_2D, status, 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:
-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.

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). And either may be -10 if the point is outside the span.

Parameters:

p point 1

pdir direction-1

q point 2

qdir direction-2

tol tolerance values

Definition at line 1138 of file plane.c.
References BN_CK_TOL, bn_isect_line3_line3(), bu_bomb(), bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist, MAGNITUDE, SMALL_FASTF, status, and V2ARGS.
Here is the call graph for this function:

int bn_isect_line3_line3 ( fastf_t * t,

fastf_t * u,

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 3 _ L I N E 3
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:
-2 no intersection, lines are parallel.
-1 no intersection
0 lines are co-linear (t returned for u=0 to give distance to A)
1 intersection found (t and u returned)

Parameters:

[out] t,u line parameter of interseciton When explicit return >= 0, t and u 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 1

d direction 1

a point 2

c direction 2

tol tolerance values

t,u When explicit return >= 0, t and u 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.
XXX It would be sensible to change the t,u pair to dist[2].
Definition at line 1257 of file plane.c.
References BN_CK_TOL, bn_isect_line2_line2(), bn_pt3_pt3_equal(), bn_vec_ortho(), DETERMINANT_TOL, bn_tol::dist, LOCAL, MAGSQ, NEAR_ZERO, SMALL_FASTF, VCROSS, VDOT, VJOIN1, VSUB2, X, Y, and Z.
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 1507 of file plane.c.
References BN_CK_TOL, bn_dist_pt3_along_line3(), bn_distsq_line3_pt3(), bn_isect_line3_line3(), bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist, bn_tol::dist_sq, LOCAL, MAGSQ, and VSUB2.
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 1595 of file plane.c.
References bu_debug, BU_DEBUG_MATH, bu_log(), LOCAL, MAGNITUDE, MAGSQ, SMALL_FASTF, VDOT, and VSUB2.
Here is the call graph for this function:

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 1631 of file plane.c.
References bu_debug, BU_DEBUG_MATH, bu_log(), LOCAL, MAGNITUDE, SMALL_FASTF, VDOT, and VSUB2.
Here is the call graph for this function:

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 1663 of file plane.c.
References MAGNITUDE, SMALL_FASTF, 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 1685 of file plane.c.
References LOCAL, MAGSQ_2D, SMALL_FASTF, 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 1711 of file plane.c.
References LOCAL, MAGSQ_2D, SMALL_FASTF, 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 1732 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 1788 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 1874 of file plane.c.
References BN_CK_TOL, bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist_sq, MAGSQ_2D, V2PRINT, VDOT_2D, VMOVE_2D, VSCALE_2D, and VSUB2_2D.
Here is the call graph for this function:

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 1969 of file plane.c.
References BN_CK_TOL, bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist, bn_tol::dist_sq, MAGSQ, V3ARGS, VDOT, VJOIN1, VMOVE, and VSUB2.
Here is the call graph for this function:

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 2090 of file plane.c.
References BN_CK_TOL, bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist, bn_tol::dist_sq, MAGSQ_2D, V2JOIN1, V2MOVE, V3ARGS, VDOT_2D, and VSUB2_2D.
Here is the call graph for this function:

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 2187 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 2214 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 2248 of file plane.c.
References BN_CK_TOL, bn_tol::dist, NEAR_ZERO, and VDOT.

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 2313 of file plane.c.
References bn_pi, bn_twopi, bu_bomb(), and VDOT.
Here is the call graph for this function:

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 2345 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 2363 of file plane.c.
References bu_debug, BU_DEBUG_MATH, bu_log(), V2ARGS, VDOT_2D, and VSUB2_2D.
Here is the call graph for this function:

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 2386 of file plane.c.
References BN_CK_TOL, bu_debug, BU_DEBUG_MATH, bu_log(), bn_tol::dist, and NEAR_ZERO.
Referenced by bn_isect_line2_lseg2(), nmg_break_eg_on_v(), and nmg_isect_line2_edge2p().
Here is the call graph for this function:

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 2421 of file plane.c.
References NEAR_ZERO, SMALL_FASTF, VCROSS, VDOT, VJOIN1, VSUB2, and VUNITIZE.

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 2589 of file plane.c.
References BN_CLASSIFY_UNIMPLEMENTED, bu_log(), CHECK_PT, V3ARGS, X, Y, and Z.
Here is the call graph for this function:

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 2647 of file plane.c.
References bu_bomb(), MAGNITUDE, MAGSQ, NEAR_ZERO, SMALL_FASTF, VBLEND2, VDOT, VJOIN1, VSCALE, and VSUB2.
Here is the call graph for this function:

int bn_isect_planes ( fastf_t * pt,

const fastf_t * planes[4],

const int 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, and 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 2728 of file plane.c.
References bu_debug, BU_DEBUG_MATH, bu_log(), and V4ARGS.
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 2799 of file plane.c.
References MAX_FASTF, SQRT_SMALL_FASTF, st, and VSUB2.

Generated on Mon Sep 18 01:25:24 2006 for BRL-CAD by

1.4.6

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

Files

Defines

Functions

Define Documentation

Function Documentation

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