Some Analytic Geometry - Introduction to 3D Game Programming with DirectX 12 (Computer Science) (2016)

Introduction to 3D Game Programming with DirectX 12 (Computer Science) (2016)

Appendix C

SOME ANALYTIC
G
EOMETRY

In this appendix, we use vectors and points as building blocks for more complicated geometry. These topics are used in the book, but not as frequently as vectors, matrices, and transformations; hence, we have put them in an appendix, rather than the main text.

C.1 RAYS, LINES, AND SEGMENTS

A line can be described by a point p0 on the line and a vector u that aims parallel to the line (see Figure C.1). The vector line equation is:

image

By plugging in different values for t (t can be any real number) we obtain different points on the line.

If we restrict t to nonnegative numbers, then the graph of the vector line equation is a ray with origin p0 and direction u (see Figure C.2).

Now suppose we wish to define a line segment by the endpoints p0 and p1. We first construct the vector u = p1 p0 from p0 to p1; see Figure C.3. Then, for t ∈ [0, 1], the graph of the equation p(t) = p0 + tu = p0 + (p1p0) is the line segment defined by p0 and p1. Note that if you go outside the range t ∈ [0, 1], then you get a point on the line that coincides with the segment, but which is not on the segment.

image

Figure C.1. A line described by a point p0 on the line and a vector u that aims parallel to the line. We can generate points on the line by plugging in any real number t.

image

Figure C.2. A ray described by an origin p0 and direction u. We can generate points on the ray by plugging in scalars for t that are greater than or equal to zero.

image

Figure C.3. We generate points on the line segment by plugging in different values for t in [0, 1]. For example, the midpoint of the line segment is given at t = 0.5. Also note that if t = 0, we get the endpoint p0 and if t = 1, we get the endpoint p1.

C.2 PARALLELOGRAMS

Let q be a point, and u and v be two vectors that are not scalar multiples of one another (i.e., ukv for any scalar k). Then the graph of the following function is a parallelogram (see Figure C.4):

image

image

Figure C.4. Parallelogram. By plugging in different s, t ∈ [0, 1] we generate different points on the parallelogram.

The reason for the “ukv for any scalar k” requirement can be seen as follows: If u = kv then we could write:

image

which is just the equation of a line. In other words, we only have one degree of freedom. To get a 2D shape like a parallelogram, we need two degrees of freedom, so the vectors u and v must not be scalar multiples of each another.

C.3 TRIANGLES

The vector equation of a triangle is similar to that of the parallelogram equation, except that we restrict the domain of the parameters further:

image

Observe from Figure C.5 that if any of the conditions on s and t do not hold, then p(s, t) will be a point “outside” the triangle, but on the plane of the triangle.

We can obtain the above parametric equation of a triangle given three points defining a triangle. Consider a triangle defined by three vertices p0, p1, p2. Then for that s ≥ 0, t ≥ 0, s + t ≤ 1 a point on the triangle can be given by:

image

We can take this further and distribute the scalars:

image

where we have let r = (1 − st). The coordinates (r, s, t) are called barycentric coordinates. Note that r + s + t = 1 and the barycentric combination p(r, s, t) = rp0 + sp1 + tp2 expresses the point p as a weighted average of the vertices of the triangle. There are interesting properties of barycentric coordinates, but we do not need them for this book; the reader may wish to further research barycentric coordinates.

image

Figure C.5. Triangle. By plugging in different s, t such that s ≥ 0, t ≥ 0, s + t ≤ 1, we generate different points on the triangle.

C.4 PLANES

A plane can be viewed as an infinitely thin, infinitely wide, and infinitely long sheet of paper. A plane can be specified with a vector ν and a point p0 on the plane. The vector n, not necessarily unit length, is called the plane’snormal vector and is perpendicular to the plane; see Figure C.6. A plane divides space into a positive half-space and a negative half-space. The positive half space is the space in front of the plane, where the front of the plane is the side the normal vector emanates from. The negative half space is the space behind the plane.

By Figure C.6, we see that the graph of a plane is all the points p that satisfy the plane equation:

image

When describing a particular plane, the normal n and a known point p0 on the plane are fixed, so it is typical to rewrite the plane equation as:

image

where d = −n · p0. If n = (a, b, c) and p = (x, y, z), then the plane equation can be written as:

image

If the plane’s normal vector n is of unit length, then d = −n · p0 gives the shortest signed distance from the origin to the plane (see Figure C.7).

image

Figure C.6. A plane defined by a normal vector n and a point p0 on the plane. If p0 is a point on the plane, then the point p is also on the plane if and only if the vector pp0 is orthogonal to the plane’s normal vector.]

image

Figure C.7. Shortest distance from a plane to the origin.

image

To make the pictures easier to draw, we sometimes draw our figures in 2D and use a line to represent a plane. A line, with a perpendicular normal, can be thought of as a 2D plane since the line divides the 2D space into a positive half space and negative half space.

C.4.1 DirectX Math Planes

When representing a plane in code, it suffices to store only the normal vector n and the constant d. It is useful to think of this as a 4D vector, which we denote as (n, d) = (a, b, c, d). Therefore, because the XMVECTOR type stores a 4-tuple of floating-point values, the DirectX Math library overloads the XMVECTOR type to also represent planes.

C.4.2 Point/Plane Spatial Relation

Given any point p, observe from Figure C.6 and Figure C.8 that

image

These tests are useful for testing the spatial location of points relative to a plane.

This next DirectX Math function evaluates n · p = d for a particular plane and point:

XMVECTOR XMPlaneDotCoord(// Returns n · p = d replicated in each coordinate

XMVECTOR P, // plane

XMVECTOR V); // point with w = 1

// Test the locality of a point relative to a plane.

XMVECTOR p = XMVectorSet(0.0f, 1.0f, 0.0f, 0.0f);

XMVECTOR v = XMVectorSet(3.0f, 5.0f, 2.0f);

float x = XMVectorGetX( XMPlaneDotCoord(p, v) );

if( x approximately equals 0.0f ) // v is coplanar to the plane.

if( x > 0 ) // v is in positive half-space.

if( x < 0 ) // v is in negative half-space.

image

Figure C.8. Point/plane spatial relation.

image

We say approximately equals due to floating point imprecision.

A similar function is:

XMVECTOR XMPlaneDotNormal(XMVECTOR Plane, XMVECTOR Vec);

This returns the dot product of the plane normal vector and the given 3D vector.

C.4.3 Construction

Besides directly specifying the plane coefficients (n, d) = (a, b, c, d), we can calculate these coefficients in two other ways. Given the normal n and a known point on the plane p0 we can solve for the d component:

image

The DirectX Math library provides the following function to construct a plane from a point and normal in this way:

XMVECTOR XMPlaneFromPointNormal(

XMVECTOR Point,

XMVECTOR Normal);

The second way we can construct a plane is by specifying three distinct points on the plane.

Given the points p0, p1, p2, we can form two vectors on the plane:

image

From that we can compute the normal of the plane by taking the cross product of the two vectors on the plane. (Remember the left hand thumb rule.)

image

Then, we compute d = −n · p0.

The DirectX Math library provides the following function to compute a plane given three points on the plane:

XMVECTOR XMPlaneFromPoints(

XMVECTOR Point1,

XMVECTOR Point2,

XMVECTOR Point3);

C.4.4 Normalizing a Plane

Sometimes we might have a plane and would like to normalize the normal vector. At first thought, it would seem that we could just normalize the normal vector as we would any other vector. But recall that the d component also depends on the normal vector: d = −n · p0. Therefore, if we normalize the normal vector, we must also recalculate d. This is done as follows:

image

Thus, we have the following formula to normalize the normal vector of the plane (n, d):

image

We can use the following DirectX Math function to normalize a plane’s normal vector:

XMVECTOR XMPlaneNormalize(XMVECTOR P);

C.4.5 Transforming a Plane

[Lengyel02] shows that we can transform a plane (n, d) by treating it as a 4D vector and multiplying it by the inverse-transpose of the desired transformation matrix. Note that the plane’s normal vector must be normalized first. We use the following DirectX Math function to do this:

XMVECTOR XMPlaneTransform(XMVECTOR P, XMMATRIX M);

Sample Code:

XMMATRIX T(…); // Initialize T to a desired transformation.

XMMATRIX invT = XMMatrixInverse(XMMatrixDeterminant(T), T);

XMMATRIX invTransposeT = XMMatrixTranspose(invT);

XMVECTOR p = (…); // Initialize Plane.

p = XMPlaneNormalize(p); // make sure normal is normalized.

XMVECTOR transformedPlane = XMPlaneTransform(p, &invTransposeT);

C.4.6 Nearest Point on a Plane to a Given Point

Suppose we have a point p in space and we would like to find the point q on the plane (n, d) that is closest to p. From Figure C.9, we see that

image

image

Figure C.9. The nearest point on a plane to a point p. The point p0 is a point on the plane.

Assuming ||n|| = 1 so that image

we can rewrite this as:

image

C.4.7 Ray/Plane Intersection

Given a ray p(t) = p0 + tu and the equation of a plane n · p + d = 0, we would like to know if the ray intersects the plane and also the point of intersection. To do this, we plug the ray into the plane equation and solve for the parameter t that satisfies the plane equation, thereby giving us the parameter that yields the intersection point:

image

If n·u = 0 then the ray is parallel to the plane and there are either no solutions or infinite many solutions (infinite if the ray coincides with the plane). If t is not in the interval [0, ∞), the ray does not intersect the plane, but the line coincident with the ray does. If t is in the interval [0, ∞), then the ray does intersect the plane and the intersection point is found by evaluating the ray equation at image

.

The ray/plane intersection test can be modified to a segment/plane test. Given two points defining a line segment p and q, then we form the ray r(t) = p + t(qp). We use this ray for the intersection test. If t ∈[0, 1], then the segment intersects the plane, otherwise it does not. The DirectX Math library provides the following function:

XMVECTOR XMPlaneIntersectLine(

XMVECTOR P,

XMVECTOR LinePoint1,

XMVECTOR LinePoint2);

C.4.8 Reflecting Vectors

Given a vector I we wish to reflect it about a plane with normal n. Because vectors do not have positions, only the plane normal is involved when reflecting a vector. Figure C.10 shows the geometric situation, from which we conclude the reflection vector is given by:

image

C.4.9 Reflecting Points

Points reflect differently from vectors since points have position. Figure C.11 shows that the reflected point q is given by:

image

C.4.10 Reflection Matrix

Let (n, d) = (nx, ny, nz, d) be the coefficients of a plane, where d = − n · p0. Then, using homogeneous coordinates, we can reflect both points and vectors about this plane using a single 4 × 4 reflection matrix:

image

Figure C.10. Geometry of vector reflection.

image

Figure C.11. Geometry of point reflection.

image

This matrix assumes the plane is normalized so that

image

If we multiply a point by this matrix, we get the point reflection formula:

image

image

We take the transpose to turn row vectors into column vectors. This is just to make the presentation neater—otherwise, we would get very long row vectors.

And similarly, if we multiply a vector by this matrix, we get the vector reflection formula:

image

The following DirectX Math function can be used to construct the above reflection matrix given a plane:

XMMATRIX XMMatrixReflect(XMVECTOR ReflectionPlane);

C.5 EXERCISES

1. Let p(t) = (1, 1) + t(2, 1) be a ray relative to some coordinate system. Plot the points on the ray at t = 0.0, 0.5, 1.0, 2.0, and 5.0.

2. Let p0 and p1 define the endpoints of a line segment. Show that the equation for a line segment can also be written as p(t) = (1 − t)p0 + tp1 for t ∈ [0, 1].

3. For each part, find the vector line equation of the line passing through the two points.

1. p1 = (2, −1), p2 = (4, 1)

2. p1 = (4, −2, 1), p2 = (2, 3, 2)

4. Let L(t) = p + tu define a line in 3-space. Let q be any point in 3-space. Prove that the distance from q to the line can be written as:

image

image

Figure C.12. Distance from q to the line.

5. Let L(t) = (4, 2, 2) + t(1, 1, 1) be a line. Find the distance from the following points to the line:

1. q = (0, 0, 0)

2. q = (4, 2, 0)

3. q = (0, 2, 2)

6. Let p0 = (0, 1, 0), p1 = (-1, 3, 6), and p2 = (8, 5, 3) be three points. Find the plane these points define.

7. Let image

be a plane. Define the locality of the following points relative to the plane: image

.

8. Let image

be a plane. Find the point on the plane nearest to the point (0, 1, 0).

9. Let image

be a plane. Find the reflection of the point (0, 1, 0) about the plane.

10.Let image

be a plane, and let r(t) = (−1, 1, −1) + t(1, 0, 0) be a ray. Find the point at which the ray intersects the plane. Then write a short program using the XMPlaneIntersectLine function to verify your answer.