The two-dimensional 'hidden-line'' problem is the problem of determining, by means of a computer algorithm, which edges or parts of edges of an arbitrary, non-intersecting polygon are visible from a specified vantage point in the plane of the polygon. The problem is an important one in the field of computer graphics, and is encountered, for example, in using a computer to determine the portion of an island's coastline visible from a ship offshore. Some propositions are introduced that facilitate the solution of this problem. A general algorithm for the solution is described, and illustrative examples are given of hidden-line problems solved with a digital computer.
A problem of particular current interest in the area of computer graphics is the so-called "hidden-line" problem. In its general, three-dimensional form, this problem is concerned with determining by a digital computer which edges of one or more opaque objects are visible and which are invisible when the objects are viewed from an arbitrary exterior point. The same problem is faced by a draftsman in making a technical drawing of an object in which the visible edges of the object are represented by solid lines and the invisible edges, that is, those hidden from view by parts of the object, are shown by dashed lines. Although every draftsman develops a skill for mentally solving this problem for himself, no satisfactory algorithms exist as yet for solving it rapidly and efficiently on a digital computer. A simple, fast algorithm is essential because there are today many applications for which it is desired to view a moving object on a cathode-ray oscilloscope, with the visible and invisible edges of the object continually redetermined for different orientations of the object relative to the observer. To the surprise of most investigators, the problem has proved to be unusually complex.
This paper is concerned only with the two-dimensional version of the general hidden-line problem, specifically with irregular polygons. The two-dimensional problem occurs, for example, in viewing an island in the ocean from on board a ship, it being of interest to know which parts of the shore are visible for different locations of the ship. Even this apparently simple problem requires a fairly complex algorithm.
Various other investigators have concerned themselves with the hidden-line problem, though, in general, they have limited their work to special cases, such as only quadric surfaces [1] or simple assemblies of planar-surfaced objects [2] [3]. To the authors' knowledge, none has developed an algorithm for the efficient solution for arbitrary two-dimensional polygonal figures.
Given an arbitrary, non-intersecting polygon P having n vertices Vi, i=1,2,...,n, numbered consecutively in a negative sense (ie such that the inside always lies to the right) around the polygon, the coordinates (xi,yi) of the vertices V, in a Cartesian coordinate system, and a vantage point E with coordinates (x0, y0) which may lie either inside or outside P, find which edges of the polyhedron are visible, partially visible, or invisible for an observer located at the vantage point.
The restriction to polygons is a reasonable one, since the computer description of an arbitrary, closed, two-dimensional figure is most easily given in terms of a succession of straight-line segments. The problem permits the vantage point to be either outside or inside. If the vantage point is outside, the problem is that of an island viewed from offshore, as already mentioned; if inside, the problem is that of a lake with a boat from which the lake shore, represented by the polygon, is viewed.
The possible configurations of a vantage point relative to a polygon may be classified into three distinct types. The vantage point may lie in the free exterior of the polygon (the most common type), it may be seemingly encircled by the polygon, the blocked exterior type, or it may lie in the interior of the polygon. The three types of configurations are illustrated in Fig. 1. The distinction between the free exterior and the blocked exterior configurations is that in the latter it is not possible to draw a straight line beginning at E and extending infinitely outward without intersecting the polygon. Each type of configuration requires a slightly different approach to its solution.
To determine the configuration type, one proceeds as follows. With the vantage point E as the origin and the positive x direction as the reference axis of a polar coordinate system, one computes the angles φi and the distances ρi to each vertex Vi, i = 1, 2,..., n. (See Fig. 2.)
φi =arctan( (yi-y0)/(xi-x0) ), 0 ≤ φi < 2π radians (1) ρi = (xi-x0) sqrt(1 + ((yi-y0)/(xi-x0) )2 ) (2)
Now suppose that the polygon P is traced out in a negative sense by a vector r from the point E. At each vertex, the angle φi gives the angular location of r in the range 0 to 2π radians but does not indicate the number of complete rotations about E, if any, that may have been required to reach this vertex. To obtain a complete description of the angular position of r at each vertex, a new set of angles, Φi, i = 1,2,...,n, is introduced. These angles, referred to as total angles, give the total angular position of r at the vertices Vi as measured from the reference axis, and are not limited to the range 0 to 2π radians. Their values can be determined from the values of the corresponding modulo-2π angles, φi, and the knowledge that as r moves from one vertex to an adjacent vertex, the change in angle must always be less than π radians. The latter follows from the proposition that the angle subtended by a line segment at a point not collinear with the line segment is always less than π radians.
It is convenient to express the total angles Φ in terms of rotational units (rtu), where 1 rtu = 2π radians. To find the Φi, it is necessary to know when the vector r crosses the reference axis. Whenever r crosses in a clockwise sense, the integer part of its angle (expressed in rotational units) decreases by unity, and whenever r crosses in a counterclockwise sense, it increases by unity. There is no change in the integer part of the angle if the reference axis is not crossed. The following rule is easily deduced:
If |φi+1 - φi| < 0.5 rtu then Φi+1 = Φi + Φi+1 - φi If φi+1 - φi > 0.5 rtu then Φi+1 = Φi + Φi+1 - φi - 1 If φi+1 - φi < -0.5 rtu then Φi+1 = Φi + Φi+1 - φi + 1 (3)
To determine all the Φi, i = 1, 2,...,n, one begins with vertex V1 and arbitrarily lets Φ1 = φ1. The other Φi, are then determined in succession by substituting the known values of φi; in (3). It is desirable (for reasons to be seen shortly) also to determine Φn+1, where φn+1=φ1.
Once all the Φi have been determined, it is a simple matter to establish the type of configuration represented by the polygon and the vantage point E. If Φi =Φn+1 then E is exterior to P because r has then not made a net rotation about E in tracing out P exactly once. However, if Φi =Φn+1 +1, a net clockwise rotation about E has taken place, and E lies in the interior of P.
If E is exterior to P and max Φi- min Φi < 1, then the configuration is free, and if max Φi - min Φi≥1, it is blocked, since in that case the point E is fully encircled.
The edges of a polygon P may be visible, partially visible (i.e., partially invisible), or invisible from a vantage point E. A particular edge may be invisible for one of two causes: either because the edge is facing away from E, or, although facing E, it is blocked from view at E by another part of P. If an edge is facing away from E, it will be entirely invisible; however, if it faces E but is blocked by another portion of P, then it may be either partially or entirely invisible, depending on the degree to which it is blocked.
If a polygon P is traced out in a negative sense by a vector r from an exterior point E, and r describes a negative angle about E as it moves along an edge of P, then this entire edge will be invisible from E.
Proof: Let the edge lie between the vertices Vj and Vj+1. Then a triangle Vj E Vj+1 can be constructed. Since r in moving along the side Vj Vj+1 of the triangle describes a negative angle, the vertex Vj+1 lies clockwise from Vj, as seen from E. Further, since P is traced out in a negative sense, its interior lies to the right of the edge Vj Vj+1, and, therefore, inside the triangle Vj E Vj+1. Hence the entire edge is invisible from E. Q.E.D.
If a polygon P is traced out in a negative sense by a vector r from an exterior point E, and r describes a positive angle about E as it moves along the edge between two adjacent vertices that are both visible from E, then the entire edge will be visible from E.
Proof: Let the edge lie between vertices Vj and Vj+1. Then a triangle Vj+1 E Vj can be constructed, of which the side Vj Vj+1 is the edge. Since Vj and Vj+1 are both visible, no portion of P may cross the sides E Vj and E Vj+1. Also since r describes a positive angle in going along Vj Vj+1 and while tracing out P in a negative sense, the interior of P lies outside the triangle Vj+1 E Vj. Hence no part of P lies inside the triangle, and, therefore, the entire edge Vj Vj+1 is visible from E. Q.E.D.
Corollary: If any two points on an edge of a polygon are visible from an exterior point E and at least one of the points is not a vertex, then the portion of the edge between these points is visible from E.
If a polygon P is traced out in a negative sense from an exterior point E, then all edges encountered after the most counterclockwise vertex and before the most clockwise vertex of P are invisible from E.
(Throughout this paper, if two or more vertices tie for most clockwise or most counterclockwise, the one lying closest to E is to be selected. )
Proof: Let the most clockwise vertex of P, relative to E, be Vp. Now consider the most counterclockwise vertex. Suppose this vertex has the label Vq. Then if a vector r from E traces out P in a negative sense, beginning with Vp, its angle with some reference line will change from a minimum value, Φmin, at Vp, to a maximum value, Φmax, at Vq, and then back again to the minimum value. The difference Φmax-Φmin may be less than, equal to, or greater than 1 rtu, but will, of course, always be positive. By hypothesis, P lies exactly in the angular region [Φmin, Φmax] and since P is a single closed figure, there is no angular region within [Φmin, Φmax] that does not contain a part of P. Hence as r traces out P in a negative sense from V, (at Φmax) to V, (at Φmin), some part of the interior of P will always lie between E and the edges traced out, and, therefore, all such edges will be invisible from E. Q.E.D.
With Proposition 3 one can at once establish that on the average roughly half the edges of a polygon are entirely invisible, and these edges need then not be considered further. All the remaining edges will either lie in full unobstructed view of E and will, therefore, be visible or will lie partially or wholly in what can be considered to be a bay, and will, therefore, be either partially or wholly invisible from E. This is illustrated in Fig. 3 for both a free exterior and a blocked exterior configuration. A bay is referred to as either a backward or a forward bay, depending on whether it lies, respectively, clockwise or counter clockwise of the vector r as this vector passes through the visible vertex that marks the entrance to the bay.
The entire hidden-line problem thus reduces to determining which edges of the polygon can be eliminated by Proposition 3 and which edges can be shown to lie in a bay. All remaining edges will be visible.
It can be seen from Fig. 3(b) that there is only a trivial distinction between an interior configuration and a blocked exterior configuration. In both the vantage point E is fully blocked from viewing the exterior of the polygon. The passage to the exterior in the blocked exterior configuration of Fig. 3(b) will be treated simply as a bay, a backward bay in this instance. The only difference is that for an interior configuration the vertices appear to be labeled in the positive rather than the negative sense about P as seen from E. Hence it is necessary merely to reverse the order of labeling the vertices to make an interior configuration indistinguishable-for purposes of the hidden-line problem-from a blocked exterior configuration.
The following is a description of the algorithm in outline form:
Step 1: Compute φi and ρi for each vertex.
Step 2: Compute the total angles Φi.
Step 3: Determine whether configuration is of the free exterior, blocked exterior, or interior type. If interior, reverse the order of labeling.
Step 4: Relabel all vertices Ai, such that A1 is the most clockwise vertex and i advances in a clockwise sense. Label the edges ai, where i is the index of the preceding vertex as the polygon is traced out in a negative sense.
Step 5: Rotate polar coordinate system (ρi,φi) so that reference axis passes through A1. New coordinates are labeled (ri, Ωi).
Step 6: If Am is the most counterclockwise vertex (Φm= maxiΦi) then all edges ai, i > m, will be invisible from Proposition 3.
One next searches for a point on P that is definitely visible. If the configuration is of the free-exterior type, the vertex A is used since it is always visible, and one continues with Step 12. Otherwise continue with Step 7.
Step 7: Find all edges aj for which the integer part of the terminal angle, Ωj+1, is greater by unity than that of the initial angle, Ωi.
Step 8: Determine the intersections between the reference axis and all edges aj of Step 7. This is done by first rotating the x, y coordinates of the initial and terminal vertices of each edge about the point (x0, Y0) by the same amount by which the reference axis was rotated in Step 5. Using the rotated coordinates (xi', yi') of the vertices, the intersection will lie on the reference axis at a point xq,j given by
xq,j' = xj' - yj' ((xj+1' - xj')/(yj+1' - yj'))
Step 9: Find the distances from E to the vertices Ai that lie on the reference axis. Label these distances rq,t, where q=1,2,...,Q, and Q is the total number of vertices and intersections on the axis.
Step 10: Determine min(rq,t, Xq,j') from Steps 8 and 9.
Step 11: The desired visible point is the one for which the minimum distance is obtained in Step 10.
Step 12: Commence with the known visible point on P and proceed along P in a negative sense to the next vertex. Let Tj denote the total angle of the present visible point. If the point is the vertex Aj, then Tj=Ωj.
Step 13: If Ωj+1=Tj, aj is entirely invisible. Return to Step 12 and take Aj+1 as the next visible vertex.
Step 14: If Ωj+1<Tj, Aj+1 lies in a backward bay, as shown in Fig. 4(a). The next visible point will lie on the line EAj and will be either a vertex or an intersection between this line and an edge of P. To determine this visible point, the polar coordinate system is rotated to place the reference line on the line EAj. All vertices lying on this line are then found, as well as all edges that cross this line. The procedure is identical with that of Steps 7 through 11.
If this next visible point lies on the edge ak, it will be labeled Bk, If k>j, all edges ai for j ≤i<k will be invisible; if k<j, all edges ai for j≤i≤n and i<k will be invisible. Also, the edge a will be invisible from Ak to Bk.
The next test will be to compare Ωk+l with Tk, the angle at Bk. Note that here Tk =Ωj.
Step 15: If Ωj+1>Tj, Aj+1 may be either visible or may lie in a forward bay. Consider Fig. 4(b). Let the last visible point on aj be Bj. Examine all vertices of P, except those already considered or eliminated by means of Proposition 3, to determine which, if any, lie in the angular region between Ωj+1 and Tj. For this purpose consider only the fractional parts of the angles, expressed in rotational units. If no vertices are found in the angular region, proceed to Step 18.
Step 16: If vertices are found in the angular region, retain only those for which ri<max(rj,rj+1). If none remain, go to Step 18.
Step 17: From the remaining vertices, select the one that lies most clockwise from the line Aj+1E. Suppose this is the vertex Ak. Evaluate the expression
α= (xk-xj+1)(yj-yj+1) - (xj-xj+1)(yk-yj+1)
If α>0 a forward bay exists for which Ak is the vertex that marks the entrance to the bay. Proceed to Step 19.
If α <0 return to Step 1 7 and use the vertex with the next most clockwise angle. If none remain, go to Step 18.
Step 18: The vertex Aj+1 is visible and, from Proposition 2 the segment BjAj+1 is visible. (See Fig. 4(b).) Return to Step 12 and next consider Aj+2.
Step 19: The edge aj is invisible from the intersection, Cj, with the line EAk to the vertex Aj+1. If k>j+1, all edges ai, for which j+1≤i<k are invisible; if K<j, all edges ai for which j+1≤i≤n and i<k are invisible. The first visible vertex following Aj is Ak. Return to Step 12 and next consider Ak+1.
Step 20: For a free exterior configuration, the foregoing scheme of testing vertices while moving in a counterclockwise sense about E terminates when the most counterclockwise vertex, Am, is reached.
For a blocked exterior configuration, the process continues until one full rotation has been made about E and the initial visible point encountered once more.
An example of a blocked exterior configuration is shown in Fig. 5. The figure has already been relabeled to make A1 the most clockwise vertex. From Proposition 3, edges a12 through a20 are invisible and the vertices A13 through A20 need not be considered any further. The point Q on a11 is found as the initial visible point. Then A12 is found to be visible, thereby indicating that the segment QA12 is visible. At A12 a backward bay is encountered making a12 through a20 invisible, a fact that is already known from Proposition 3.
In general, the use of Proposition 3, although not necessary, is nevertheless helpful since it eliminates a large number of vertices at an early stage of the problem. It thereby reduces the number of vertices that may have to be examined during the testing for forward bays.
Edge a1 is invisible from A1 to B1 and visible from B1 to A2. Edges a2, a2 and a4 are found to be visible. A backward bay is found at A5, making 5a and a6 invisible. Edge a7 is then visible only from B7 to A8.
In going from A8 to A9, a forward bay is encountered, marked by the vertex A11. This makes a0 and a10 invisible, and a8 is visible only from A8 to C8. From A11 the edge a11 is considered only to Q, the initial visible vertex. The segment A11Q is found to be visible and the solution is complete.
In Figs. 6 and 7 results are shown of two problems solved on a digital computer. The drawings are the actual computer output, drawn on line by a digital plotter.
(1) J. Y. S. Luh and R. J. Krolak, A mathematical model for mechanical part description, CACM, vol. 8 125-129, February 1965.
(2) A. F. Smith, Method for computer visualization, Electronic Systems Lab, MIT Rept. 8436-TM-2, September 1960.
(3) L. G. Roberts, Machine perception of three-dimensional solids, MIT Lincoln Lab Tech. Rept. 315, May 1963.