Plane/line/point calculations

Collaboration diagram for Plane/line/point calculations:

Data Structures
struct	plane_specific
struct	tri_specific
struct	tri_float_specific

Macros
#define	MAXPTS   4
#define	pl_A   pl_points[0]
#define	BG_CLASSIFY_UNIMPLEMENTED   0x0000
#define	BG_CLASSIFY_INSIDE   0x0001
#define	BG_CLASSIFY_OVERLAPPING   0x0002
#define	BG_CLASSIFY_OUTSIDE   0x0003

Typedefs
typedef struct tri_specific	tri_specific_double
typedef struct tri_float_specific	tri_specific_float

Functions
int	bg_distsq_line3_line3 (fastf_t dist[3], point_t P, vect_t d, point_t Q, vect_t e, point_t pt1, point_t pt2)
	Calculate the square of the distance of closest approach for two lines. More...
int	bg_dist_pnt3_line3 (fastf_t *dist, point_t pca, const point_t a, const point_t p, const vect_t dir, const struct bn_tol *tol)
int	bg_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	bg_dist_line3_line3 (fastf_t dist[2], const point_t p1, const point_t p2, const vect_t d1, const vect_t d2, const struct bn_tol *tol)
int	bg_dist_pnt3_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, and the point of closest approach (PCA). More...
int	bg_distsq_pnt3_lseg3_v2 (fastf_t *distsq, const fastf_t *a, const fastf_t *b, const fastf_t *p, const struct bn_tol *tol)
int	bg_3pnts_collinear (point_t a, point_t b, point_t c, const struct bn_tol *tol)
	Check to see if three points are collinear. More...
int	bg_pnt3_pnt3_equal (const point_t a, const point_t b, const struct bn_tol *tol)
int	bg_dist_pnt2_lseg2 (fastf_t *dist_sq, fastf_t pca[2], 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, and the point of closest approach (PCA). More...
int	bg_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 unit length. More...
int	bg_lseg3_lseg3_parallel (const point_t sg1pt1, const point_t sg1pt2, const point_t sg2pt1, const point_t sg2pt2, const struct bn_tol *tol)
int	bg_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	bg_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. More...
int	bg_isect_pnt2_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. More...
int	bg_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: More...
int	bg_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 unit length. More...
int	bg_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)
double	bg_dist_pnt3_pnt3 (const point_t a, const point_t b)
	Returns distance between two points. More...
int	bg_3pnts_distinct (const point_t a, const point_t b, const point_t c, const struct bn_tol *tol)
int	bg_npnts_distinct (const int npts, const point_t *pts, const struct bn_tol *tol)
int	bg_make_plane_3pnts (plane_t plane, const point_t a, const point_t b, const point_t c, const struct bn_tol *tol)
int	bg_make_pnt_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 vectors of the planes need not be of unit length. More...
int	bg_isect_line3_plane (fastf_t *dist, const point_t pt, const vect_t dir, const plane_t plane, const struct bn_tol *tol)
int	bg_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 is returned in parametric line (point & direction vector) form. More...
int	bg_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	bg_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: More...
double	bg_dist_line3_pnt3 (const point_t pt, const vect_t dir, const point_t a)
double	bg_distsq_line3_pnt3 (const point_t pt, const vect_t dir, const point_t a)
double	bg_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 origin. More...
double	bg_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 the line and the point. More...
double	bg_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 the line and the point, squared. More...
double	bg_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. More...
int	bg_isect_pnt_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. More...
double	bg_dist_pnt_lseg (point_t pca, const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
void	bg_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. 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. More...
void	bg_rotate_plane (plane_t oplane, const mat_t mat, const plane_t iplane)
	Transform a plane equation by the given 4x4 matrix. More...
int	bg_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. More...
int	bg_coplanar_pts (const point_t *pts, int pt_cnt, const struct bn_tol *tol)
	Test if a set of points are coplanar. Note: if 0 < pt_cnt <=3 the point(s) are trivially coplanar, and 1 will be returned. More...
double	bg_angle_measure (vect_t vec, const vect_t x_dir, const vect_t y_dir)
double	bg_dist_pnt3_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. 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. More...
double	bg_dist_pnt2_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. 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. More...
int	bg_between (double left, double mid, double right, const struct bn_tol *tol)
int	bg_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	bg_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. More...
int	bg_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. If the planes intersect at a single point, that point is the solution. More...
int	bg_plane_pt_nrml (plane_t *p, point_t pt, vect_t nrml)
	Given an origin and a normal, create a plane_t. More...
int	bg_fit_plane (point_t *c, vect_t *n, size_t npnts, point_t *pnts)
	Calculates the best fit plane for a set of points. More...
int	bg_plane_closest_pt (fastf_t *u, fastf_t *v, plane_t *p, point_t *pt)
	Find the closest U,V point on the plane p to 3d point pt. More...
int	bg_plane_pt_at (point_t *pt, plane_t *p, fastf_t u, fastf_t v)
	Return the 3D point on the plane at parametric coordinates u, v. More...

Detailed Description

Plane structures (from src/librt/plane.h) and plane/line/point calculations

Todo:

• this API may need to be simplified. A lot of the closest point calculations, for example, should probably just concern themselves with the calculation itself and leave any tolerance based questions to a separate step.

Macro Definition Documentation

MAXPTS

#define MAXPTS   4

All we need are 4 points

Definition at line 46 of file plane.h.

pl_A

#define pl_A   pl_points[0]

Synonym for A point

Definition at line 47 of file plane.h.

BG_CLASSIFY_UNIMPLEMENTED

#define BG_CLASSIFY_UNIMPLEMENTED   0x0000

Definition at line 1101 of file plane.h.

BG_CLASSIFY_INSIDE

#define BG_CLASSIFY_INSIDE   0x0001

Definition at line 1102 of file plane.h.

BG_CLASSIFY_OVERLAPPING

#define BG_CLASSIFY_OVERLAPPING   0x0002

Definition at line 1103 of file plane.h.

BG_CLASSIFY_OUTSIDE

#define BG_CLASSIFY_OUTSIDE   0x0003

Definition at line 1104 of file plane.h.

Typedef Documentation

tri_specific_double

typedef struct tri_specific tri_specific_double

Definition at line 1 of file plane.h.

tri_specific_float

typedef struct tri_float_specific tri_specific_float

Definition at line 1 of file plane.h.

Function Documentation

bg_distsq_line3_line3()

int bg_distsq_line3_line3	(	fastf_t	dist[3],
		point_t	P,
		vect_t	d,
		point_t	Q,
		vect_t	e,
		point_t	pt1,
		point_t	pt2
	)

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

The lines are specified 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 algorithm is based on expressing the distance squared, taking partials with respect to the two unknown parameters (dist[0] and dist[1]), setting the two partials equal to 0, and solving the two simultaneous equations

bg_dist_pnt3_line3()

int bg_dist_pnt3_line3	(	fastf_t *	dist,
		point_t	pca,
		const point_t	a,
		const point_t	p,
		const vect_t	dir,
		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.

bg_dist_line3_lseg3()

int bg_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 segment.

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.

bg_dist_line3_line3()

int bg_dist_line3_line3	(	fastf_t	dist[2],
		const point_t	p1,
		const point_t	p2,
		const vect_t	d1,
		const vect_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 values 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 bg_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?

bg_dist_pnt3_lseg3()

int bg_dist_pnt3_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, and the point of closest approach (PCA).

*
*                       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_pnt_lseg().

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

bg_distsq_pnt3_lseg3_v2()

int bg_distsq_pnt3_lseg3_v2	(	fastf_t *	distsq,
		const fastf_t *	a,
		const fastf_t *	b,
		const fastf_t *	p,
		const struct bn_tol *	tol
	)

PRIVATE: This is a new API and should be considered unpublished.

Find the square of the distance from a point P to a line segment described by the two endpoints A and B.

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

There are six distinct cases, with these return codes - Return code precedence: 1, 2, 0, 3, 4, 5

 0  P is within tolerance of lseg AB.  *dist =  0.
 1  P is within tolerance of point A.  *dist = 0.
 2  P is within tolerance of point B.  *dist = 0.
 3  PCA is within tolerance of A. *dist = |P-A|**2.
 4  PCA is within tolerance of B. *dist = |P-B|**2.
 5  P is "above/below" lseg AB.   *dist=|PCA-P|**2.

If both P and PCA and not within tolerance of lseg AB use these return codes -

 3  PCA is to the left of A.  *dist = |P-A|**2.
 4  PCA is to the right of B. *dist = |P-B|**2.

This function is a test version of "bn_distsq_pnt3_lseg3".

bg_3pnts_collinear()

int bg_3pnts_collinear	(	point_t	a,
		point_t	b,
		point_t	c,
		const struct bn_tol *	tol
	)

Check to see if three points are collinear.

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

bg_pnt3_pnt3_equal()

int bg_pnt3_pnt3_equal	(	const point_t	a,
		const point_t	b,
		const struct bn_tol *	tol
	)

Returns

1 if the two points are equal, within the tolerance

0 if the two points are not "the same"

bg_dist_pnt2_lseg2()

int bg_dist_pnt2_lseg2	(	fastf_t *	dist_sq,
		fastf_t	pca[2],
		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, and the point of closest approach (PCA).

*                       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 bg_dist_pnt3_lseg3().

bg_isect_lseg3_lseg3()

int bg_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 unit length.

Returns

-3 missed

-2 missed (line segments are parallel)

-1 missed (collinear and non-overlapping)

0 hit (line segments collinear 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 segment (within tol->dist) results in 0.0 and when the intersect is at the end point of the line segment (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

bg_lseg3_lseg3_parallel()

int bg_lseg3_lseg3_parallel	(	const point_t	sg1pt1,
		const point_t	sg1pt2,
		const point_t	sg2pt1,
		const point_t	sg2pt2,
		const struct bn_tol *	tol
	)

bg_isect_line3_line3()

int bg_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
	)

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
	u	direction 1
	q0	point 2
	v	direction 2
	tol	tolerance values
[out]	s	(distances to intersection) (see below)
[out]	t	(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. occurring 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.

bg_2line3_colinear()

int bg_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.

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.

bg_isect_pnt2_lseg2()

int bg_isect_pnt2_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.

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'

bg_isect_line2_lseg2()

int bg_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:

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 segment, < 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

bg_isect_lseg2_lseg2()

int bg_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 unit length.

Returns

-2 missed (line segments are parallel)

-1 missed (collinear and non-overlapping)

0 hit (line segments collinear 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

bg_isect_line2_line2()

int bg_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
	)

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 (i.e., 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)

bg_dist_pnt3_pnt3()

double bg_dist_pnt3_pnt3	(	const point_t	a,
		const point_t	b
	)

Returns distance between two points.

bg_3pnts_distinct()

int bg_3pnts_distinct	(	const point_t	a,
		const point_t	b,
		const point_t	c,
		const struct bn_tol *	tol
	)

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

bg_npnts_distinct()

int bg_npnts_distinct	(	const int	npts,
		const point_t *	pts,
		const struct bn_tol *	tol
	)

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

bg_make_plane_3pnts()

int bg_make_plane_3pnts	(	plane_t	plane,
		const point_t	a,
		const point_t	b,
		const point_t	c,
		const struct bn_tol *	tol
	)

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 collinear.

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 calculation

bg_make_pnt_3planes()

int bg_make_pnt_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 vectors of the planes need not be of unit length.

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

bg_isect_line3_plane()

int bg_isect_line3_plane	(	fastf_t *	dist,
		const point_t	pt,
		const vect_t	dir,
		const plane_t	plane,
		const struct bn_tol *	tol
	)

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 length 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

bg_isect_2planes()

int bg_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 is returned in parametric line (point & direction vector) form.

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 point of model RPP
[in]	tol	tolerance values

bg_isect_2lines()

int bg_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
	)

bg_isect_line_lseg()

int bg_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:

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 bg_isect_line3_lseg3() XXX should probably be changed to return dist[2]

bg_dist_line3_pnt3()

double bg_dist_line3_pnt3	(	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 the line and the point.

'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

bg_distsq_line3_pnt3()

double bg_distsq_line3_pnt3	(	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 square of the closest distance between the line and the point.

'dir' need not have unit length.

Return - Distance squared

bg_dist_line_origin()

double bg_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 origin.

'dir' need not have unit length.

Returns

Distance

bg_dist_line2_point2()

double bg_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 the line and the point.

'dir' need not have unit length.

Returns

Distance

bg_distsq_line2_point2()

double bg_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 the line and the point, squared.

'dir' need not have unit length.

Returns

Distance squared

bg_area_of_triangle()

double bg_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.

bg_isect_pnt_lseg()

int bg_isect_pnt_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.

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)

bg_dist_pnt_lseg()

double bg_dist_pnt_lseg	(	point_t	pca,
		const point_t	a,
		const point_t	b,
		const point_t	p,
		const struct bn_tol *	tol
	)

bg_rotate_bbox()

void bg_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. 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.

bg_rotate_plane()

void bg_rotate_plane	(	plane_t	oplane,
		const mat_t	mat,
		const plane_t	iplane
	)

Transform a plane equation by the given 4x4 matrix.

bg_coplanar()

int bg_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.

Returns

-1 not coplanar, parallel but distinct

0 not coplanar, not parallel. Planes intersect.

1 coplanar, same normal direction

2 coplanar, opposite normal direction

bg_coplanar_pts()

int bg_coplanar_pts	(	const point_t *	pts,
		int	pt_cnt,
		const struct bn_tol *	tol
	)

Test if a set of points are coplanar. Note: if 0 < pt_cnt <=3 the point(s) are trivially coplanar, and 1 will be returned.

Returns

-1 error

0 not coplanar

1 coplanar

bg_angle_measure()

double bg_angle_measure	(	vect_t	vec,
		const vect_t	x_dir,
		const vect_t	y_dir
	)

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 bg_twopi.

bg_dist_pnt3_along_line3()

double bg_dist_pnt3_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. 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.

bg_dist_pnt2_along_line2()

double bg_dist_pnt2_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. 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.

bg_between()

int bg_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.

bg_does_ray_isect_tri()

int bg_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
	)

Returns

0 No intersection

1 Intersection, 'inter' has intersect point.

bg_hlf_class()

int bg_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.

Returns

BG_CLASSIFY_INSIDE

BG_CLASSIFY_OVERLAPPING

BG_CLASSIFY_OUTSIDE

bg_isect_planes()

int bg_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. If the planes intersect at a single point, that point is the solution.

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 bg_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)

bg_plane_pt_nrml()

int bg_plane_pt_nrml	(	plane_t *	p,
		point_t	pt,
		vect_t	nrml
	)

Given an origin and a normal, create a plane_t.

bg_fit_plane()

int bg_fit_plane	(	point_t *	c,
		vect_t *	n,
		size_t	npnts,
		point_t *	pnts
	)

Calculates the best fit plane for a set of points.

Use SVD algorithm from Soderkvist to fit a plane to vertex points https://www.ltu.se/cms_fs/1.51590!/svd-fitting.pdf

Returns a center point and a normal direction for the plane

bg_plane_closest_pt()

int bg_plane_closest_pt	(	fastf_t *	u,
		fastf_t *	v,
		plane_t *	p,
		point_t *	pt
	)

Find the closest U,V point on the plane p to 3d point pt.

bg_plane_pt_at()

int bg_plane_pt_at	(	point_t *	pt,
		plane_t *	p,
		fastf_t	u,
		fastf_t	v
	)

Return the 3D point on the plane at parametric coordinates u, v.