5.1 Line Intersecting a Rectangular Plane

Figure 5-1 shows a line intersecting a rectangular plane . You will develop the algorithm and a program to find the point of intersection, called the hit point. Here you are stipulating that the plane is finite, but it doesn’t have to be. After going through the analysis, you will see there is nothing here that requires the plane be finite. You also start off by assuming the plane is rectangular. It doesn’t have to be rectangular but, for now, it is easier to keep it finite and rectangular.

The plane has corners at 0, 1, 2, and 3. These have local coordinates of (x0,y0,z0) - (x3,y3,z3) relative to the center of rotation at (xc,yc,zc). The line starts at x[4],y[4],z[4] and ends at x[5],y[5],z[5]. It intersects the plane at the hit point.

There are three unit vectors at corner 0; û,, and . Unit vector points from corner 0 to 1; û from 0 to 3. is normal to the plane. is a unit vector pointing along the line from 4 to 5. Q₄₅ is the distance from 4 to 5. Q _h is the distance from 4 to the hit point. Q _n is the perpendicular distance from 4 to the plane. Your quest is to determine the location of the hit point (xh,yh,zh). Using vector geometry, you can write the following relations:

Distance 4 → 5:

(5-1)

(5-2)

(5-3)

(5-4)

Unit vector 4 → 5:

(5-5)

(5-6)

(5-7)

(5-8)

Distance 0 → 3:

(5-9)

(5-10)

(5-11)

(5-12)

Unit vector 0 → 3:

(5-13)

(5-14)

(5-15)

(5-16)

Distance 0 → 1:

(5-17)

(5-18)

(5-19)

(5-20)

Unit vector 0 → 1:

(5-21)

(5-22)

(5-23)

(5-24)

Unit vector :

(5-25)

(5-26)

(5-27)

(5-28)

(5-29)

(5-30)

(5-31)

Vector 0 → 4:

(5-32)

(5-33)

(5-34)

(5-35)

Perpendicular distance 4 to plane:

(5-36)

Hit point:

(5-37)

(5-38)

(5-39)

(5-40)

(5-41)

(5-42)

(5-43)

You can test to see if the hit point lies within the boundaries of the plane. Figure 5-2 shows the geometry. Vector V0h runs from corner 0 to the hit point h. up and vp are the projections of V0h on the 03 and 01 directions, respectively. To test for an in-bound or out-of-bound hit,

if up < 0 or up > Q03    hit is out of bounds

if vp < 0 or vp > Q01     hit is out of bounds

With xh,yh, and zh being the coordinates of the hit point h, you can calculate up and vp as follows:

(5-44)

(5-45)

(5-46)

(5-47)

To find up, you project V0h onto the 03 direction. To do that, you take the dot product of V0h with û:

(5-48)

To find vp, you take the dot product of V0h with :

(5-49)

If you regard the line from 4 to 5 as being finite, you can test to see if it is long enough to reach the plane. From Figure 5-1,

(5-50)

(5-51)

(5-52)

(5-53)

if Q45 < Qh    LINE TOO SHORT, NO HIT

All of this has been incorporated in Listing 5-1, which has the same structure as Listing 3-5 in Chapter 3, although some of the functions and operations have been altered. As in that program, rotation directions and amounts are entered through the keyboard. Rotations are additive; for example, if the system is rotated first by Rx=40 degrees, followed by Rx=10, the total angle will be 50 degrees. Ry and Rz operate similarly.

Some data is hard-wired in Listing 5-1, such as definitions of the rectangular plane and the line intersecting it. They are shown in the lists in lines 18–20. There are six elements in each list numbered [0]-[5]: [0]-[3] are the four corners of the plane while [4] and [5] are the beginning and end of the line. They are coordinated with the diagrams in Figures 5-1 and 5-2. To modify the plane and line, just put new numbers in the lists. For example, item [5] is the end of the line. To drop it down in the +y direction, increase y[5]. The numbers in the lists are in local coordinates relative to the center of rotation (xc,yc,zc), which is at the center of the plane. The values are shown in Lines 14-16.

It takes only three points to define a plane. Here you have a four-corner rectangular plane. If you alter the plane’s corner coordinates, be sure they lie in the same plane. The easiest way to do so is to start off with a plane that lies in or is parallel to one of the coordinate planes. It can be rotated out of that coordinate plane later. In line 19, the first four elements of the y list are all zero. That describes a flat plane parallel to the x,z plane at y=0. Also, if altering the [x] or [z] lists, be sure the plane remains rectangular since the calculations of the hit point in this analysis assume that is the case.

Rotation functions rotx, roty, and rotz, which rotate coordinates around the coordinate directions, are included in lines 28-35. They are the same as used in prior programs so they have not been listed.

Line 45 plots a dot at the hit point (xhg,yhg) where the line intersects the plane. If the hit point lies within the plane’s boundaries, the color of the dot is red; if it’s outside, it is blue. If the line from [4] to [5] is too short and never reaches the plane, the color is changed to green and a dot is placed at [5], the end of the line. This is illustrated in Figure 5-5. The calculation of the hit point is carried out by function hitpoint(x,y,z), which begins in line 53. The program follows the analysis above in Equations 5-1 through 5-49 and should be self-explanatory.

Data input takes place in lines 154-166. This is similar to Listing 3-5. Samples of the output are shown in Figures 5-3, 5-4, and 5-5. Parameters are included in the captions.

5.2 Line Intersecting a Triangular Plane

Almost any flat surface can be formed by an array of triangular planes and a curved surface can be approximated by triangles, hence our interest in triangular planes .

Figure 5-6 shows the geometry for a line intersecting a triangular plane. The algorithms used in Listing 5-3 are mostly the same as in Listing 5-1. One difference is that the lengths of the list are, of course, shorter since the triangle has one less corner. Another is that the check on whether the hit point lies within the triangle or is out of bounds is different.

Before going on to Listing 5-3, you will develop a simple way to determine if a hit point lies within a triangle or outside of it. Figure 5-7 shows the geometry used for the out-of-bounds calculation. Listing 5-2 produces the output shown in Figure 5-8 and, with modification to the lists defining the coordinates of point 3, in Figure 5-9. In Figure 5-8, the hit is out of bounds; in Figure 5-9, it is within the triangle.

Figure 5-7 shows three triangles: the black one, defined by points 0, 1, and 2, is the base triangle, the one you are concerned with. It has area A. The triangle defined by points 0, 1, and 3 (the hit point) has area A1. The third triangle between point 0, 3, and 2 has area A2. It is easy to see that if A1+A2>A, the hit point is out of bounds; if A1+A2<A, it is in bounds. If you can calculate the areas of the three triangles, you will have an easy way to determine if the hit point is within or outside of the base triangle. To do so, you rely on a simple expression for determining the area of a triangle:

(5-54)

(5-55)

where a, b, and c are the lengths of the three sides of the triangle and A is its area. This is known as Heron’s formula, named after Hero of Alexandria, a Greek engineer and mathematician circa 10 AD - 70 AD.

This relation is put to use in Listing 5-2 and later in Listing 5-3. In Listing 5-2, most of the program is concerned with evaluating the lengths of the lines shown in Figure 5-7. Heron’s formula is then used to calculate the three areas: A, A1, and A2. The decision whether the hit point is inside or outside of the base triangle is made in lines 114-117 of Listing 5-2. It produces Figure 5-8. Program THT2 (not shown) is the same as THT1 (Listing 5-2) but has the lists adjusted to put the hit point within the triangle. It produces Figure 5-9. The adjusted lists are

x=[40,30,80,55]

y=[60,10,60,45]

z=[0,0,0,0]

As you can see from these lists, the hit point has been moved to (55,45,0).

Listing 5-3 plots the hit point between a line and a triangle. It is similar to Listing 5-1 except it uses the inside or outside test developed above. Examples of output are shown in Figures 5-10, 5-11, and 5-12. One difference worth noting is in the calculation of the unit vector , which is perpendicular to the plane of the triangle. In Listing 5-1, this was found by taking the cross product of û with vˆ. Since the angle between û and was 90 ^° , this produced a unit vector that was normal to both of them, which implies normal to the plane, and of magnitude 1. This is because where α is the angle between û and . When α equals 90 ^° , .

However, with a general non-right triangle, the angle is not 90 ^° so the vector resulting from the cross product, while normal to the plane, does not have a value of 1; in other words, it is not a unit vector. The algorithm between lines 88 and 91 makes the correction by normalizing ’s components. It does this by dividing each of them by the magnitude of . In line 88, magn is the magnitude of before normalization of the vector’s components. Depending on the angle α, its value will be somewhere between 0 and 1. Dividing each component of by magn makes a unit vector.

5.3 Line Intersecting a Circle

The determination of whether the hit point of a line intersecting the plane of a circle is within the circle is trivial. As shown in Figure 5-13, if the distance from the circle’s center to the hit point is greater than the circle’s radius, it lies outside the circle:

if rh > r    NO HIT

We won’t bother writing a separate program to demonstrate this. You should be able to do that yourself by modifying Listing 5-1 or Listing 5-3. Simply fill the x[ ],y[ ], and z[ ] lists with the points defining the circle’s perimeter and the line coordinates and modify the functions plotsystem and hitpoint.

5.4 Line Intersecting a Circular Sector

In this section, you develop a procedure to determine if the hit point of a line intersecting the plane of a sector of a circle is inside or outside the sector. Figure 5-14 shows the sector. It has a center at point 0 and a radius r. The hit point is at 3. rh is the distance from 0 to the hit point. Your goal is to determine if the hit point lies inside or outside the sector. (We will not be developing a full three-dimensional program here; you’ll just see how the inside or outside algorithm works.) It could be easily incorporated into any of the preceding programs, such as Listing 5-3.

There are five unit vectors at point 0: û points from 0 to 2; points from 0 to 1; and ĥ from 0 to the hit point at 3. is a unit vector normal to the plane of the sector. It is not shown since it points up and out of the plane. is the result of the cross product of û with ; is from the cross product of with .

Your strategy is to first determine if Rh>r, in which case the hit point is outside the sector in the radial direction. Then you take the dot product of ĥ with . If the result is positive, the hit point is outside the sector on the 0-2 side. Then you take the dot product of ĥ with . If it is positive, the hit point is out of bounds on the 0-1 side.

In Listing 5-4, the local coordinates (relative to point 0) are defined in the lists in lines 14-16. The last element in the lists defines the coordinates of the hit point, point 3. xc,yc, and zc in lines 18-20 are the global coordinates of point 0. The hit test algorithm begins in line 23. Most of it should be self-explanatory based on the previous discussion. Attention is called to lines 52-58. This is where the normal vector is evaluated by taking the cross product of û with . As explained earlier, this produces a unit vector (magnitude 1) only if û and are perpendicular to one another. Since the angle between them in a general sector will not necessarily be 90 degrees, the vector must be normalized. That takes place in lines 55-58. The dot product of with ĥ takes place in line 64, with ĥ in line 70. Line 72 assumes the hit color is red, which means the hit is within the sector. If A is positive, it lies outside the sector, in which case the hit color is changed to blue in line 74. Lines 76 and 77 perform the same test for the other side of the sector. Lines 79 and 80 check for the hit point lying outside the sector in the radial direction. Figures 5-15 and 5-16 show two sample runs. You can move the hit point around yourself by changing the coordinates of point 3 in the lists in lines 14-15. You change only the x and y coordinates of the hit point since it is assumed to lie in the z=0 plane, as does the sector.

5.5 Line Intersecting a Sphere

Figure 5-17, output from Listing 5-5, shows a line intersecting a sphere . The entrance and exit points are shown in red. Figure 5-18 shows the model used by Listing 5-5. The line begins at B and ends at E.

To find the entrance hit point, you start at B and move a point p incrementally along the line toward E. At each step, you calculate Qpc, the distance between p and c. If it is less than or equal to the sphere’s radius rs, you have made contact with the sphere and a red dot is plotted. You continue moving p along the line inside the sphere without plotting anything (you could plot a dotted line), calculating Qpc as you go, until Qpc becomes equal to or greater than rs. At that point, p leaves the sphere and another red dot is plotted. p continues moving along the line to E, plotting black dots along the way. Instead of plotting the line with dots, you could have used short line segments as was done in prior programs.

To move p along the line, you use parameter t, which is the distance from B to p. To get the coordinates of p, you construct unit vector û, which points along the line

(5-56)

(5-57)

(5-58)

(5-59)

(5-60)

(5-61)

(5-62)

where Qbe is the distance along the line from B to E and ux,uy, and uz are the components of û. The coordinates of p are thus

(5-63)

(5-64)

(5-65)

Qpc is easy to determine:

(5-66)

(5-67)

(5-68)

(5-69)

In Listing 5-5, the sphere’s center coordinates are set in lines 18-20. The sphere is composed of longitude (vertical) lines and latitude (horizontal) lines. The lists in lines 10-16 contain the local and global coordinates of the longitudes. The initial filling of these lists takes place in lines 25-38, which create a half circle in the z=0 plane. As shown in Figure 5-19, point p lies on the circumference at coordinates xp,yp,zp where

(5-70)

(5-71)

(5-72)

They are set in lines 30-32. ϕ is the angle around the z direction. It runs from -90 ^° to +90 ^° . You don’t need the back half of the longitudes so they are not plotted. This half circle will be rotated around the y direction to create the oval longitudes. They are 10 ^° apart as set in line 74. Since they are rotated around the y direction only, the program contains just the rotation function roty: rotx and rotz are not needed in this model. Plotting of the longitudes takes place in lines 72-77.

The latitudes are plotted in lines 80-97. Figure 5-21 shows a front view of the sphere looking into the x,y plane. Each latitude is essentially a circle having radius rl where

(5-73)

This is calculated in line 89 of the program. When viewed from the front, the latitude appears as a straight line since you are not rotating the sphere in this program.

The ϕ loop beginning at line 88 ranges ϕ from -90 ^° to + 90 ^° in 10 ^° increments. At each increment a new latitude is plotted. It will have a radius given by Equation 5-73 above. The α loop beginning at line 92 sweeps across the front of the circular latitude from α=0 ^° to 180 ^° in 10 ^° increments. This is illustrated in Figure 5-22, which shows the top view looking down on the x,z plane.

5.6 Plane Intersecting a Sphere

In this section, you will work out a technique for plotting a flat rectangular plane intersecting a sphere. Figure 5-23 shows the output of Listing 5-6; Figure 5-24 shows the model used by that listing.

The strategy here is to use the algorithms developed in the previous section for a line intersecting a sphere as your basic element. By representing the plane as a series of parallel lines, you can easily find the intersection of a plane with a sphere. Figure 5-23 shows unit vector û at corner 1. As before, this points from the beginning to end of the first line. There is also unit vector at corner 1. This points to corner 3. By advancing along the line from 1 to 3 in small steps, you can construct lines running parallel to the first one from 1 to 2. Advancing down each of these lines in small increments of t, you can find the coordinates of points across the plane. To advance in the direction, you introduce parameter s, which is the distance from corner 1 to the beginning of the new line. To get the coordinates of the end of that line, you perform the same operation starting at point 2 using vˆ and s, as in

(5-74)

(5-75)

(5-76)

where xe, ye, and ze are the coordinates of the end of the line; x2,y2, and z2 are the coordinates of point 2; and vx,vy, and vz are the components of unit vector .

Incrementing down and across the plane with parameters t and s allows you to sweep across the surface of the plane. At each point p you calculate the distance from p to the center of the sphere. If it is equal to or less than the sphere’s radius, you have a hit.

I won’t list the entire program that produced Figure 5-23 since it is mostly similar to Listing 5-5, except for the addition of an s loop that sweeps in the direction. Control of the program begins at line 27. Lines 27-37 define the coordinates of plane corners 1, 2, and 3. The unit vectors û and are established in lines 39-53. Lines 55 and 56 set the scan increments in dt and ds. The loop 57-64 scans in the direction, establishing the beginning and end coordinates of each line. Function plane, which begins at line 1, determines if there is a hit with each line and the sphere. For each s, the loop beginning at line 3 advances down the line in the û direction, calculating the coordinates xp,yp,zp of each point p along the line. Line 10 calculates the distance of p from the sphere’s center. Line 11 says, if the distance is greater than the sphere’s radius, plot a black dot. If it is less than or equal to the radius, line 18 plots a colorless dot. The rest of the logic up to line 24 determines if the line has emerged from the sphere, in which case plotting of black dots resumes. Results are shown in Figure 5-23.

5.7 Summary

In this chapter, you learned how to predict whether a three-dimensional line or plane will intersect a three-dimensional surface or solid object. Why bother with this? Because it is fundamental to removing hidden lines, you will see in Chapter 6. When plotting surface A, which may be behind another surface or object B, you do so in small steps, plotting a scatter dot (or a short line segment) at each step. If the point on A is hidden by B, you do not plot it. To determine if it is hidden from view by an observer, you draw an imaginary line from the point on A to the observer (i.e. in the -z direction). If you can determine if that line from A intersects a surface or object B in front of it, then you will know whether or not it is hidden. While you cannot develop hidden line algorithms for every conceivable situation (you did rectangular planes, triangular planes, circular sectors, circles, and spheres here), by understanding how it is done for these objects you should, with a bit of creativity, be able to develop your own hidden line algorithms for other surfaces and objects. Perhaps the line-triangular plane is most useful since complex surfaces and objects can often by approximated by an assembly of triangles. You will see more about this in Chapter 6.