InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Cellular Automata for Hidden Line Elimination

IP.com Disclosure Number: IPCOM000081713D
Original Publication Date: 1974-Jul-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 4 page(s) / 112K

Publishing Venue


Related People

Appel, A: AUTHOR [+2]


There is described herein a simple hidden-line elimination technique which avoids the need for treating exponential time growth.

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 54% of the total text.

Page 1 of 4

Cellular Automata for Hidden Line Elimination

There is described herein a simple hidden-line elimination technique which avoids the need for treating exponential time growth.

In the known hidden-line programs for use in the generation of three-dimensional depictions in the computer graphic arts, the following elements are usually included: 1. The forming of the wire-frame image on the picture plane

of the surfaces.

2. The breaking of each line (or curve) into small segments.

3. The testing of a point on each segment to sense whether a

segment falls within the projected region of a closer


4. The drawing only of those segments which do not lie within

regions that are closer to the observer than they are.

Thus, as shown in Figs. 1 and 2 wherein there are illustrated a typical hidden-line technique, the wire-frame picture shown in Fig. 1 is converted to the hidden-line picture shown in Fig. 2. It is readily appreciated that the hidden-line problem is essentially one of the sorting type that has the characteristic shown in Fig. 3, wherein there is illustrated the characteristics of most known hidden-line programs.

Generally, most hidden-line elimination programs have the characteristic performance Time (CPU) = f(N/2/). With sophisticated sorting techniques, the optimum limiting characteristic is T(CPU) approx.= N1n(N). Thus, different known programs implement algorithms with characteristic behavior T = AN/2/, T = A + BN/1.3/ or T = A + BN/1.1/1n(N).

Almost all hidden-line suppression programs entail great costs, because of the necessity for accurate surface and line equations and complex list structures. In the technique described herein, there is utilized the cellular automata approach.

A cellular automaton generally is played on an infinite (or finite) checker board where cells are given a definite state, the variety of states being finite. Considering the loading of a cellular automaton with the projection of an object, reference is made to Figs. 4 and 5 wherein there is shown the loading of a raster with depth. Each cell is loaded with the depth of the point in three-dimensional space. If two lines cross at a cell, the depth which is loaded is the minimum. The cells so loaded are termed "line cells", and these cells are turned on or lighted to draw the object.

The object of this hidden-line technique is to turn off line cells or to "kill" line cells. In the technique, there is associated with each line cell one or two directions which point in...