Schneider P., Eberly D.H. Geometric Tools for Computer Graphics

Подождите немного. Документ загружается.

364 Chapter 9 Geometric Primitives in 3D

9.7.3 NURBS Surfaces

A nonuniform rational B-spline surface or NURBS surface is obtained from a non-

uniform B-spline polynomial surface in four dimensions. The control points are

,1) ∈ R

for 0 ≤ i

≤ n

and 0 ≤ i

≤ n

, with weights w

> 0, and the poly-

nomial surface is

(Y (s, t), w(s, t)) =



(0)

(s)B

(1)

(t) w

,1)

where B

(0)

i,j

(s) and B

(1)

i,j

(s) are the polynomials deﬁned in the previous subsection.

The NURBS surface is obtained by treating (Y (s, t), w(s, t)) as a homogeneous vec-

tor and dividing through by the last component to obtain a projection in three

dimensions

X(s, t) =

Y(s, t)

w(s, t)



(s, t)P

where

(s, t) =

(0)

(s)B

(1)

(t)



(0)

(s)B

(1)

(t)

Chapter

10Distance in 3D

10.1 Introduction

Suppose we have two geometric objects A and B, and we wish to compute the

distance between them. If we consider each object to be represented by parametric

functions A(s) and B(



t) with s ∈ S ⊂ R

and



t ∈ T ⊂ R

, then there is a general

method for computing the distance. This method consists of ﬁnding a point on A

and a point on B whose squared distance is the minimum of all squared distances

between all possible pairs of points on the objects. Expressed as a function, we have

Q(s,



t) =A(s) −B(



t)

, for (s,



t) ∈ S × T ⊂ R

× R

. The solution is the mini-

mum of this function—either it occurs at an interior point of S × T , in which case

∇(Q) =



0, or it occurs at a boundary point of S × T , in which case the solution

consists of minimizing a quadratic function. Besides this general solution, we also

provide solutions for certain speciﬁc cases, often exploiting geometric properties of

the primitives involved in the problem.

10.2

Point to Linear Component

Suppose we have a point Q and a line L(t) = P + t



d, and we wish to ﬁnd the

minimum distance between Q and L, as shown in Figure 10.1. If we look at the point

on L closest to Q and consider the line segment joining those two points, we see that

the line segment is perpendicular to L. This observation suggests the use of a dot

product, and that indeed is the case—the closest point Q



is the projection of Q on

L (see Figure 10.2). The parametric value of Q





d · (Q − P)



d ·



(10.1)

365

366 Chapter 10 Distance in 3D

Figure 10.1 Distance between a line and a point.

and of course



= P +t



The distance from Q to L is then

d =Q − Q





=Q − (P +t



d)

Note that if the direction



d of L is normalized, we have 

d=1, so Equation 10.1

becomes

d ·

(

Q − P

)

and the necessity of a division is eliminated.

The pseudocode is

float PointLineDistanceSquared3D(Point q, Line l, bool normalized, float& t)

{

float distanceSquared;

t = Dot(l.direction, VectorSubtract(q, l.direction));

if (!normalized) {

t /= Dot(l.direction, l.direction);

}

Point3D qPrime;

qPrime = l.origin+t*l.direction;

10.2 Point to Linear Component 367

Q – P

Figure 10.2 The projection of Q on L.

Vector3D vec=Q-qPrime;

distanceSquared = Dot(vec, vec);

return distanceSquared;

}

10.2.1 Point to Ray or Line Segment

If L is a line, then the solution is as described above. If L is a ray, we restrict the

solution to only nonnegative values of t

;ift

< 0, then the distance from Q to L is

Q − P :

d =



Q − P  t

≤ 0

Q − (Q + t



d) t

> 0

If L is a line segment deﬁned by its two end points P

and P

, then the direction

vector is deﬁned by



d = P

− P

Note that this makes P

= L(0) and P

= L(1), and so we have

d =







Q − P

 t

≤ 0

Q − (P

+ t



d) 0 <t

< 1

Q − (P



d) t

≥ 1

(see Figure 10.3).

368 Chapter 10 Distance in 3D

Figure 10.3 Distance between a line segment and a point.

The pseudocode for the case of the ray is

float PointRayDistanceSquared3D(Point q, ray r, bool normalized, float& t)

{

float distanceSquared;

// Get distance to line - may havet<0

distanceSquared = PointLineDistanceSquared3D(q, r, normalized, &t);

if(t<0){

t=0;

// Get distance to ray origin instead

Vector3D vec=q-r.origin;

distanceSquared = Dot(vec, vec);

}

return distanceSquared;

}

The pseudocode for the line segment case is

float PointLineSegDistanceSquared3D(Point3D q, Segment3D s, bool normalized,

float& t)

{

float distanceSquared;

// Get distance to line - may havet<0ort>1

distanceSquared = PointLineDistanceSquared3D(q, s, normalized, &t);

10.2 Point to Linear Component 369

if(t<0){

t=0;

// Get distance to segment origin instead

Vector3D vec=q-s.p0;

distanceSquared = Dot(vec, vec);

} else if (t > 1) {

t=1;

// Get distance to segment terminus instead

Vector3D vec=q-s.p1;

distanceSquared = Dot(vec, vec);

}

return distanceSquared;

}

10.2.2 Point to Polyline

For calculating the distance between a point P and a polyline L with vertices V

through V

and line segments S

,0≤i<n− 1, whose end points are V

and V

i+1

the straightforward algorithm is to calculate the minimum of the distances between

the point and the line segments of the polyline

Distance



P , L



= min

0≤i<n−1

Distance



P , S



(10.2)

Iterating blindly over the line segments can potentially be expensive for polylines with

a large number of segments or for an application with a large number of polylines for

which the distance calculations must be made frequently.

We could instead use a 3D extension of the suggested technique for computing

the distance between a 2D point and a polyline, as described in Section 6.2. The ap-

proach is to iterate over the polyline’s segments and do a relatively cheap rejection on

segments that we know cannot possibly be closer than the current closest segment’s

distance. If the current closest segment S

is at a distance d to the point P , we can

consider a sphere with center P = (a, b, c) and radius d. Any segment that does not

intersect the sphere cannot be closer than d; however, as pointed out in Section 6.2,

computing this distance would entail just the sort of calculation that we wish to avoid.

In the 2D case, the alternative is to instead consider inﬁnite strips bounding the circle

(see Figure 6.4) and reject polyline segments having both vertices contained within

one of the strips. The 3D analog to this is to consider instead the slabs that bound the

sphere, as shown in Figure 10.4.

Let S

=(x

, y

, z

), (x

i+1

, y

i+1

, z

i+1

) be the next segment to be tested. If S

outside the inﬁnite slab |x − a|≤d, then it cannot intersect the circle. The rejection

test is therefore

370 Chapter 10 Distance in 3D

Figure 10.4 Utilizing half-spaces to speed up point/polyline distance tests.

− a|≥d and |x

i+1

− a|≥d and (x

− a)(x

i+1

− a) > 0

The ﬁrst two conditions guarantee each segment end point is outside the slab. The last

condition guarantees that the end points are on the same side of the slab. Similarly,

if S

is outside the inﬁnite slab |y − b|≤d, then it cannot intersect the circle. The

rejection test is

− b|≥d and |y

i+1

− b|≥d and (y

− b)(y

i+1

− b) > 0

Finally, if S

is outside the inﬁnite slab |z −c|≤d, then it cannot intersect the circle.

The rejection test is

− c|≥d and |z

i+1

− c|≥d and (z

− c)(z

i+1

− c) > 0

Figure 10.5 illustrates this. The segment S

generated the current minimum dis-

tance d between the polyline and the point P . The segment S

, although outside the

circle, is not rejected because it partly lies in each inﬁnite slab. However, S

is re-

jected because it is outside the vertical slab (for purposes of clarity in the illustration,

the z-planes are not shown).

Since square roots should be avoided in the intermediate calculations, an imple-

mentation maintains the squared distance d

instead of d. The rejection test must be

restructured accordingly to use d

− a|

≥ d

and |x

i+1

− a|

≥ d

and (x

− a)(x

i+1

− a) > 0

10.2 Point to Linear Component 371

Figure 10.5 Rejection example for point/polyline distance.

− b|

≥ d

and |y

i+1

− b|

≥ d

and (y

− b)(y

i+1

− b) > 0

− c|

≥ d

and |z

i+1

− c|

≥ d

and (z

− c)(z

i+1

− c) > 0

The quantities in the rejection test are also used in the squared-distance calcula-

tion, so these can be temporarily saved in case they are needed later to avoid redun-

dant calculations. Also, the quantities x

i+1

−a, y

i+1

−b, and z

i+1

−c in the current

rejection test become the x

− a, y

− b, and z

− c values in the next rejection test,

so these should be saved in temporary variables and used later when needed, again to

avoid redundant calculations.

The pseudocode is

float PointPolylineDistanceSquared3D(Point p, Point vertices[],

int nSegments)

{

float dSq = INFINITY;

float xMinusA, yMinusB, zMinusC;

float xNextMinusA, yNextMinusB, zNextMinusC;

372 Chapter 10 Distance in 3D

float xMinusASq, yMinusBSq, zMinusCSq;

float xNextMinusASq, yNextMinusBSq, zNextMinusCSq;

xMinusA = vertices[0].x - p.x;

yMinusB = vertices[0].y - p.y;

zMinusC = vertices[0].z - p.z;

xMinusASq = xMinusA * xMinusA;

yMinusBSq = yMinusB * yMinusB;

zMinusCSq = zMinusC * zMinusC;

xNextMinusA = vertices[1].x - p.x;

yNextMinusB = vertices[1].y - p.y;

zNextMinusC = vertices[1].z - p.z;

xNextMinusASq = xNextMinusA * xMNextinusA;

yNextMinusBSq = yNextMinusB * yNextMinusB;

zNextMinusCSq = zNextMinusC * zNextMinusC;

// Compute distance to first segment

Line l = { vertices[i], vertices[i+1] - vertices[i] };

float t;

dSq = PointLineDistanceSquared3D(p, l, FALSE, t)

// If closest point not on segment, check appropriate end point

if(t<0){

dSq = MIN(dsq, xMinusASq + yMinusBSq + zMinusCSq);

} else if (t > 1) {

dSq = MIN(dsq, xNextMinusASq + yNextMinusBSq + zNextMinusCSq);

}

// Go through each successive segment, rejecting if possible,

// and computing the distance squared if not rejected.

for (i = 1; i < nSegments - 1; i++) {

// Rejection test

if (((Abs(xMinusASq) > dSq) && (Abs(xNextMinusASq) <= dSq)

&& (xMinusA * xNextMinusA > 0)) ||

((Abs(yMinusBSq) > dSq) && (Abs(yNextMinusBSq) <= dSq)

&& (yMinusB * yNextMinusB > 0)) ||

((Abs(zMinusCSq) > dSq) && (Abs(zNextMinusCSq) <= dSq)

&& (zMinusC * zNextMinusC > 0))) {

if (i != nSegments - 2) {

10.2 Point to Linear Component 373

xMinusA = xNextMinusA;

yMinusB = yNextMinusB;

zMinusC = zNextMinusC;

xNextMinusA = vertices[i + 2].x - p.x;

yNextMinusB = vertices[i + 2].y - p.y;

zNextMinusC = vertices[i + 2].z - p.z;

}

continue;

}

// Rejection test failed - check distance to line

Line l = { vertices[i], vertices[i+1] - vertices[i] };

float t;

dSq = PointLineDistanceSquared3D(p, l, FALSE, t)

// If closest point not on segment, check appropriate end point

if(t<0){

dSq = MIN(dsq, xMinusASq + yMinusBSq + zMinusCSq);

} else if (t > 1) {

dSq = MIN(dsq, xNextMinusASq + yNextMinusBSq + zNextMinusCSq);

}

if (i != nSegments - 2) {

xMinusA = xNextMinusA;

yMinusB = yNextMinusB;

zMinusC = zNextMinusC;

xNextMinusA = vertices[i + 2].x - p.x;

yNextMinusB = vertices[i + 2].y - p.y;

zNextMinusC = vertices[i + 2].z - p.z;

}

return dSq;

}

A modiﬁcation of the rejection test involves testing for intersection between a seg-

ment and the axis-aligned box that contains the circle of radius d centered at P .We

can use the method of separating axes discussed in Section 11.11. The improvement

is illustrated by Figure 10.5. The segment S

was not rejected by the previous method

because it lies partly in both inﬁnite strips. However, S

is rejected by the current

method because it does not intersect the axis-aligned rectangle.