Browse Prior Art Database

Hidden Line Elimination for Complex Surfaces

IP.com Disclosure Number: IPCOM000085584D
Original Publication Date: 1976-Apr-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 68K

Publishing Venue

IBM

Related People

Appel, A: AUTHOR

Abstract

This technique is useful in computer graphics for rendering realistic pictures where one or more surfaces are smooth but are topologically convoluted.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Hidden Line Elimination for Complex Surfaces

This technique is useful in computer graphics for rendering realistic pictures where one or more surfaces are smooth but are topologically convoluted.

The basic strategy of hidden line elimination is to find which sections of the curves to be drawn are not hidden by the surface or surfaces to be drawn, and which are represented by the curves. The essential problem is to find which curve segments fall behind surface patches. When the patches are small, a reasonable approximation is a 4-sided polygon. The space curves to be drawn can also be approximated by many small line segments, where each line segment is a side of a polygon. These patches are locally continuous, but on a larger scale can form topologically complex sheets in space such as shown in Figs. 1 and 2, for example.

It will also be assumed that since patches are small, that the distance of the entire patch from the eye (or a reference plane) is the same as any point on the patch. With this assumption the plane equation of any patch need not be calculated.

A point in three-dimensional space is hidden by a patch if the point is further from the eye than any point on the patch, and if the projection of this point falls within the projection of the patch. In Fig. 3, P(1), P(2), P(3) are typical points in three-dimensional space. P(4) is a point on the patch. PP(1) is the piercing point of P(1) in the plane of the patch. PP(3) is the piercing point of P(3) in the plane of the patch. In Fig. 4, P(1) is hidden by the patch since it is further from the eye than P(4) and PP(1) lies inside the patch. P (2)is not hidden by the patch since it is closer to the eye than P(4). P(3) is not hidden since while P(3) is further than P(4), PP(3) does not fall inside the patch.

Whether the piercing point of a line of sight to a point falls inside a patch can also be determined from the picture itself. Only the projection of P falls inside the projection of the patch. Therefore, it is not necessary to actually calculate the line of sight, the patch plane equation or the intersection of the line of sight and the patch plane.

Given a 4-sided polygon and a point, a Quad-Sense Test can be described. This test can detect if a point falls inside a convex 4-sided polygon. Each side of the polygon and the given point forms a triangle.

In Fig. 5, triangles (P(1),P(2),A),(P(2),P(3),A),(P(3),P(4),A), (P(4),P(1),A) are formed. Each triangle has an area matrix: AREA = 1/2 x(1)y(1)1 x(2)y(2)1 x(A)y(A)1 The value of AREA is either +, 0, -.

A point is inside the 4-sided polygon if each of the area matrix values are all + or all -. When the area = 0, point A is probably colinear with a boundary line. The Quad-Sense Test is to calculate the triangle area values, and a point is declared inside the 4-sided polygon if all area matrix values are + or - but not 0.

An effici...