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 45 of file plane.h.

◆ pl_A

#define pl_A pl_points[0]

Synonym for A point

Definition at line 46 of file plane.h.

◆ BG_CLASSIFY_UNIMPLEMENTED

#define BG_CLASSIFY_UNIMPLEMENTED 0x0000

Definition at line 1099 of file plane.h.

◆ BG_CLASSIFY_INSIDE

#define BG_CLASSIFY_INSIDE 0x0001

Definition at line 1100 of file plane.h.

◆ BG_CLASSIFY_OVERLAPPING

#define BG_CLASSIFY_OVERLAPPING 0x0002

Definition at line 1101 of file plane.h.

◆ BG_CLASSIFY_OUTSIDE

#define BG_CLASSIFY_OUTSIDE 0x0003

Definition at line 1102 of file plane.h.

Typedef Documentation

◆ tri_specific_double

typedef struct tri_specific tri_specific_double

Definition at line 76 of file plane.h.

◆ tri_specific_float

typedef struct tri_float_specific tri_specific_float

Definition at line 92 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.