BRL-CAD
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 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

Definition at line 76 of file plane.h.

◆ 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]distThe 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
ppoint 1
pdirdirection-1
qpoint 2
qdirdirection-2
toltolerance 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
p0point 1
udirection 1
q0point 2
vdirection 2
toltolerance 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
distWhen 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.
ppoint of first line
ddirection of first line
apoint of second line
cdirection of second line
toltolerance 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
distThe 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
ppoint 1
pdirdirection1
qpoint 2
qdirdirection2
toltolerance 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
distWhen 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.
ppoint of first line
ddirection of first line
apoint of second line
cdirection of second line
toltolerance 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]planeThe plane equation is stored here.
[in]apoint 1
[in]bpoint 2
[in]cpoint 3
[in]tolTolerance 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]ptThe point of intersection is stored here.
aplane 1
bplane 2
cplane 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]distset to the parametric distance of the intercept
[in]ptorigin of ray
[in]dirdirection of ray
[in]planeequation of plane
[in]toltolerance 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]ptStarting point of line of intersection
[out]dirDirection vector of line of intersection (unit length)
[in]aplane 1 (normal must be unit length)
[in]bplane 2 (normal must be unit length)
[in]rpp_minminimum point of model RPP
[in]toltolerance 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
ppoint
astart of lseg
bend of lseg
toltolerance values
[out]distparametric 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.