In 1963 L. G. Roberts wrotes the first algorithm at M.I.T. Lincoln Lab, to eliminate hidden or obscured surfaces from a perspective picture. Later in 1965 Roberts create homogenous coordinate systems to represent 3D transformations, which is still the used mathematical code of all graphics today.
  |
|
After a list of three-dimensional objects has been obtained in some manner, it should be possible to display them from any point of view. The sections of objects behind other objects should not be seen, nor should the back lines and construction lines of individual objects. The 3-D display program will do all this and more. It allows macro-like instances of objects so that a single object construction can be used many times with different transformations. It allows structures of models to be built up by the Use of the knobs, push buttons, and light pen. Any object can be duplicated, deleted, or transformed. These extras make possible the construction of test cases for the 2-D to 3-D program to process. However, the most significant feature of this program is the mathematical technique which makes possible the hidden line removal. |
|
| Early photography of Larry Roberts at MIT. |
A good method of storing three-dimensional data is extremely important. The structure used is the basis for both the display program and the 3-D construction process. Therefore, the data necessary for hidden line removal must be quickly available and at the same time the topological structure must be suitable for model matching. The list structure used is a list of tied blocks connected in rings. Ring list structures were developed for the TX-2 computer by Sutherland for his Sketchpad system. Sketchpad allows a user to draw two-dimensional line drawings on the computer display with the aid of the light pen, knobs, and push buttons. An extension of this work to three dimensions is currently being completed by Johnson.
| Hidden Line Elimination - Three steps are required to prepare a line for display. First, it is trimmed off at the edges of the display. Next, the back lines of each model are deleted. Third, the sections of each line which are hidden by other models are removed. It is the third part which is difficult and time consuming. As far as I know, no one has ever devised a procedure for determining hidden line segments. One can imagine brute force methods such as calculating all the line intersections on the focal plane and then computing which lines were in which polygons and tracing out the frontal lines. But procedures such as this are hard to make complete for all cases, and the processing time could be fantastic. Therefore, a new mathematical method was conceived which utilizes volume inequality matrices to find out whether a point is inside or outside a volume. |
|
 |
|
| Two stereo pairs of Roberts hidden line removal object (1964). |
This test can then be extended by linear inequality solutions to tell which segment of a line is behind a volume. This is why the inverse transformations, plane vectors, and volume matrices are needed. Since they are available, they can be used to advantage in the first two steps.
 |
|
Display Construction - Besides being able to display the list structure, the display program has provisions for modifying the list. The picture transformation in the first instance can always be changed by a rotation about each of three axes, a translation in three directions, or a size change. All transformation changes are obtained through the use of four shaft encoder knobs on the computer console. The function of these knobs is selected by means of push buttons. In addition to modifying the picture transformation, the light pen can be used to point out any instance transformation for modification. The pen is pointed at the object to be modified and a level register indicates which instance level of the object to modify. This method is somewhat crude but does allow any instance to be modified. The transformation changes allowable for objects include rotation, translation, three size components, three skew components, and an overall size factor. |
|
| Table, Array made with instances, Compound object, and Rotated view of object. |
Beyond these transformation controls, any object can be deleted or duplicated. New instances of models can be generated and instances made of present pictures. These controls allow the construction of any list structure possible or the modification of any existing structure. Thus test pictures may be generated to facilitate the testing of this program and the 3-D construction program.
After receiving his PhD, Roberts continued to work at the MIT Lincoln Laboratory. Having read the seminal 1961 paper of the "Intergalactic Computer Network" by J. C. R. Licklider, Roberts developed the first computer-to-computer network that could communicate via data packets. In 1966, he became the chief scientist in the ARPA Information Processing Techniques Office, where he led the development of the ARPANet. As of July 2008, Dr. Roberts has recongized that the Internet lack sufficient capacity to fully support the bandwidth requirements of all applications. As such, some applications must receive different grades of service which his new company, Anagram, is now supporting.
Roberts, L G., "Machine Perception of Three Dimensional Solids," MIT Lincoln Lab. Rep., TR 315, May 1963.
|
|
)
)
)
){kind=link}
){kind=link}
){kind=link}
){kind=link}