 |
Description  |
|
|
BACKGROUND AND SUMMARY OF THE INVENTION
Recent years have seen considerable advancement in the use of computers to
form pictures. Somewhat more specifically, the field of computer graphics
involves the generation, representation, manipulation, processing, and
evaluation of graphic objects with computers. Graphic objects created with
the aid of a computer may or may not have an existing physical form. That
is, using the techniques of computer graphics, pictures or graphic objects
may be created without physical models, pictures, or drawings as those
terms apply in a traditional sense. For example, a graphic object may be
defined by a computer in terms of an abstract description (model) that can
be transformed into a corresponding picture on a display surface as the
face of a cathode ray tube.
Using computer graphics, displayed pictures typically are generated by
manipulating or modifying mathematical representations of primitive
geometrical shapes. That is, desired images may be created by processing
primitive shapes such as squares and triangles with operations as those
called "union" or "intersection". For example, a primitive shape of a
house may be created by adding a triangle (representative of a roof) to a
square (representative of walls). More complex images require the use of
shapes with more complex curves and surfaces.
A person interacting with a computer may provide data (either directly or
from the computer's memory) sufficient to specify a primitive image for
display on a screen. That image then may be enhanced to a desired form by
processing the basic data. In that regard, techniques and structures have
been proposed for creating smooth appearing images in graphic displays.
For example, see an article in Scientific American, September 1984,
entitled "Computer Software for Graphics". With continuing work in the
field of computer graphics, a persistent need has been revealed for
structures to expedite and simplify the creation of desired images.
Somewhat recently, mathematical science has recognized the feasibility of
using combinations of parametric patches as curved primitives to create
graphic images. Such combinations of patches may be used to form complex
images, much as a collection of cloth patches are joined to form a quilted
bedspread. Patches provide flexibility and can represent both planar and
curved surfaces. They can be generated by the parameterization of certain
rational polynomial functions. Such techniques have been treated in the
literature. For example, see INTERACTIVE COMPUTER GRAPHICS by Wolfgang K.
Giloi, 1978, Prentice-Hall, Inc., specifically Chapter 4 entitled
"Interpolation and Approximation of Curves and Surfaces"; GEOMETRIC
PRINCIPLES AND PROCEDURES FOR COMPUTER GRAPHIC APPLICATIONS by Sylvan H.
Chasen, 1978, Prentice-Hall, Inc., see Chapter 2, "Creating a Mathematical
Formulation to Match Constraints"; and COMPUTATIONAL GEOMETRY FOR DESIGN
AND MANUFACTURE by I. D. Faux and M. J. Pratt, John Wiley & Son, 1979, see
Chapter 7, "Composite Surfaces".
One approach utilizing parametric patches is based on a method developed by
Bezier and is described in the above texts. A polyhedron, e.g. rectangle,
is used to outline a desired surface. The vertices of the polyhedron thus
control the shape of the generated patch. The vertices are known as
control points. Note that the control points at the corners of the patch
lie on the polyhedron.
Parametric patch techniques are well suited for interactive computer
graphics because a user may control the shape of patches simply by
altering the position or the number of control points. Generally, a rough
approximation of a desired surface can be accomplished by a user defining
some initial control points. By subdividing a patch of a rough
approximation into subpatches the image can be refined. As a technique,
patch subdivision is treated in a book PRINCIPLES OF INTERACTIVE COMPUTER
GRAPHICS by Newman and Sproull, 2nd Edition, 1979, McGraw-Hill, Inc., and
in an article, "An Algorithm and Data Structure for 3D Object Synthesis
Using Surface Patch Intersections", by Wayne E. Carlson appearing in
Computer Graphics, July 1982, Vol. 16, No. 3
(ACMO-89791-076-1/82/007/0255).
Subdivision in this context is any process which exactly converts a
parametric patch to several smaller ones. A number of control points for
an initial patch are employed in well known equations for computing a
similar number of control points for each subpatch. Thus, subdivision of a
patch is accomplished by computing the coordinates of additional control
points to further shape the surface as defined by subpatches. The
motivation for subdivision is that progressive subdivision produces
subpatches with control points that are progressively closer to the
desired surface.
It has been proposed to perform patch subdivision on a general purpose
computer. However, that approach is relatively slow and is not generally
suitable for interactive computer use. Essentially, a need exists for an
economical system to rapidly compute the coordinates for control points in
the subdivision of parametric patches. The related apparatus for providing
working data and for displaying resulting data is complex and voluminous
but well known in the prior art. Accordingly, the system hereof is
described in the form of a component. The place and use of the component
in a composite computer graphics system will be readily apparent to
persons of ordinary skill in the art.
In general, the system of the present invention operates in cooperation
with a host computer. Signals are received from the host computer
representative of initial control points definitive of a parametric patch.
A plurality of parallel processors receive the control points
simultaneously. In accordance with one disclosed embodiment, the signals
representative of the control points are provided in a so-called
"canonical" sequence which indicates the positional relationship of the
control points. In this embodiment, a counter identifies the control
points. In another disclosed embodiment, a name in the form of a single
integer value is assigned to identify each control point.
As disclosed herein, each of the parallel subdivision processors may
receive signals representative of control points to compute the
coordinates of a distinct subpatch control point. However, in an
alternative embodiment as disclosed herein, subdivision processors compute
the coordinates of multiple control points.
Once a level of subdivision is completed, the subpatch control points are
received by the host computer and stored. In that regard, the total
processing time involves the intervals required to output the initial
patch control points to the subdivision processors, during which time the
computation of subpatch control points occurs, plus the intervals to input
and store the subpatch control points into the host computer. The process
is recursive so that further levels of subdivision expeditiously lead to
greater refinement of the generated image.
BRIEF DESCRIPTION OF THE DRAWINGS
In the drawings, which constitute a part of this specification, exemplary
embodiments exhibiting various objectives and features hereof are set
forth, specifically:
FIGS. 1a, 1b, and 2c are graphic representations of a triangular parametric
patch related to a triangle, and illustrated to be subdivided in
accordance with aspects of the present invention;
FIGS. 2a and 2b are diagrammatic representations to illustrate the
subdivision process;
FIG. 3 is a block diagram representative of an embodiment of a system in
accordance with the present invention;
FIG. 4 is a block diagram representative of a component of the system of
FIG. 3;
FIG. 5 is a block diagram representative of an alternative component of the
system of FIG. 3; and
FIG. 6 is a block diagram illustrative of an alternative embodiment of the
present invention.
DESCRIPTION OF THE ILLUSTRATIVE EMBODIMENTS
Detailed illustrative embodiments of the present invention are disclosed
herein; however, they are merely representative, recognizing that a wide
variety of specific embodiments of the disclosed system are possible.
Nevertheless, the illustrative embodiments are deemed to afford the best
embodiments for purposes of disclosure and to provide a basis for the
claims herein which define the scope of the present invention.
Initially, some graphic representations may be helpful with regard to patch
concepts. Referring initially to FIG. 1a, a quadratic, triangular Bezier
patch 20 is represented by solid lines, the shape being somewhat like an
inflated sail. The vertex or corner control points 22, 24, and 26 of the
patch 20 are coincidentally the vertices of a triangle 28 (dashed lines).
In this case, the patch is roughly triangular in shape. That is, it may be
considered to be a "curved" triangle. The other control points, e.g.
points 30, 32, and 34 are neither on the patch 20 nor in the plane of the
triangle 28.
Normally, a triangular patch is mimicked by principal features of an
associated triangle. Essentially, by progressively subdividing a patch
into subpatches, the desired shape can be progressively more nearly
approximated. For example, note the triangles represented in fine lines in
FIG. 1a which are created by connecting the control points 22, 24, 26, 30,
32, and 34 and which convey a convex form approximating the form of the
patch 20. Note that in FIG. 1b the patch 20 has been subdivided into four
subpatches which are represented by solid lines. The control points 200
through 228 (even numbers) have been created by subdivision and define the
four subpatches. Note further the triangles represented in fine lines in
FIG. 1b which are created by connecting the control points 200 through 228
and which convey a convex form more closely approximating the patch 20
than does the convex form shown in FIG. 1a.
FIG. 2 illustrates the subdivision of a quadratic, triangular Bezier patch
V (FIG. 2a) to produce subpatches P, Q, R, and S (FIG. 2b). Note the
naming conventions to describe the control points of the patches. In that
regard, while the numerals are usually in subscript form, in the interest
of convenience and ease of printing, subscripts are not employed. Also
note that certain of the subpatch control points are shared by subpatches,
e.g. the control point P020=Q200=S002. Again, the triangular patches V, P,
Q, R, and S are illustrated for association with quadratic, triangular
Bezier patches; however in that regard, only the vertices of the triangles
will coincide with the vertex control points of the Bezier patches.
As illustrated in FIG. 2b, a patch is specified by a single letter, for
example patch V. Control points are specified by adding three decimal
digits to the designating letter, for example control point V020. Though
convenient for explanation, in the illustrative embodiment, these names
are not formatted in the computer signals representing control points.
Rather, representative single integers are used, or the positions of the
control points are determined in a canonical sequence.
Subdivision is basically a process of computing convex combinations, i.e. a
process whereby a weighted average of patch control points produces a
subpatch control point. The simplest example of subdivision is illustrated
in FIG. 2c wherein a linear, triangular Bezier patch is subdivided
uniformly to create four subpatches. Linear refers to the fact that the
sides of the patch are straight lines and that the patch is actually a
planar triangle. Uniform subdivision refers to the fact that subdivision
of the patch creates subpatches which (in the case of a linear patch) are
all the same size. Thus, uniform subdivision of a linear, triangular
Bezier patch is accomplished through bisection of each edge of that patch.
Bisection of an edge is accomplished by averaging the two endpoints of
that edge. For example, a control point P010 is calculated as follows:
P010=(V100+V010)/2.
A somewhat more complicated example is the case of uniform, one-to-four
subdivision of a quadratic, triangular Bezier patch as illustrated in
FIGS. 2a and b. Quadratic refers to the fact that the sides of the patch
are quadratic curves, for example, parabolae. Uniform subdivision refers
to the fact that subdivision of the patch creates subpatches which are all
roughly equal in size. In the case of uniform, one-to-four subdivision of
a quadratic, triangular Bezier patch, a control point P020 is calculated
as follows:
P020=(V200+2V110+V020)/4.
Generally, algorithms for calculating subpatch control points are well
known. Specifically, such algorithms are disclosed in an article
"Subdivision Algorithms for Bezier Triangles" from the journal
Computer-Aided Design, Ronald N. Goldman, Vol. 15, No. 3, (May 1983), pp.
159-166. Various subdivisions of triangles have been proposed. However, in
the disclosed embodiments, a Bezier triangle is split into four subpatches
as illustrated in FIG. 2.
FIG. 3 shows a system in accordance herewith for performing subdivision.
Specifically, a host computer 50 supplies signals representative of
control points to a plurality of subdivision processors P1 and P2 through
PN. Specifically, the host computer 50 provides signals representative of
individual control points to the subdivision processors P through a
control point output bus 52. As the signals on the bus 52 are applied to
each of the subdivision processors P, it is necessary to identify
individual control point signals. Accordingly, the host computer 50
provides designation signals to a control point name bus 54.
It is also necessary for the host computer to specify the immediate
function of the subdivision processors P, i.e., either to receive signals
representative of control points or provide signals representative of
control points. That function is accomplished by signals supplied to the
processors P through an input/output control line 56. Essentially, the
control line 56 affords binary control. For example, if the line 56
manifests a one bit by the high state of a binary signal, an input to the
host computer from the processors P is commanded. On the contrary, if the
control line 56 is at a low level (manifesting a zero bit), the control
processors P are commanded to receive signals from the host computer 50.
Input signals from the processors P are returned to the host computer
through an input bus 58.
Contrasted to the simple binary format of the control line 56, the buses
52, 54, and 58 carry numerical data naming control points and specifying
values of control points. The signals in the name bus 54 specify the name
of a control point. The control point output bus 52 and input bus 58
specify values for each of the components X, Y, Z and W to define each
control point. Consequently, computing values for a single control point
involves the computation of four components of that control point, e.g. X,
Y, Z, and W. Accordingly, in the processors as illustrated, the multiplier
76 (FIG. 4) actually comprises four individual multipliers which are
coupled to individual adders, registers, dividers, and gates. Thus, the
multiplier 103 (FIG. 5) as represented is a gang multiplier actually
comprising four separate multipliers for the quantities X, Y, Z, and W.
Similarly, the adder 80 comprises four components as does the register 86,
the divider 90, and the gate 94. Such values for designating the control
point are either accepted from the host computer 50 through the output bus
52 or returned to the host computer 50 through the input bus 58. Control
of the choice is accomplished by the host computer 50 utilizing well known
structures of the prior art. In that regard, note that the host computer
50 utilizes a memory 62 which stores control point data in process in a
retrievable format.
Exemplary detailed subdivision processors for use as the processors P1 and
P2 through PN are disclosed below. However, preliminarily consider an
exemplary operation by the system of FIG. 3 to accomplish the exemplary
subdivision as illustrated in FIG. 2.
As indicated above, computing the control point P020 (FIG. 2b, top)
involves the operation: (V200+2V110+V020)/4. Thus, computing the control
point P020 involves the control points: V200, V110, and V020. Computing
other control points, e.g. P110, P101, and so on involves the use of
different control points of the V series as illustrated in FIG. 2.
In the operation of the system of FIG. 3, signals representative of the
control points V are sequentially supplied to the output bus 52 while,
simultaneously, signals representative of the control point names are
supplied to the name bus 54 during a time when the subdivision processors
P are commanded to receive such data. The subdivision processors P accept
signals representative of those control points V necessary for their
computation of the individual control point to be calculated. For example,
assuming the subdivision processor P1 is to compute the control point P020
(FIG. 2b, top), it will accept input signals representative of the control
points V200, V110, and V020. Other of the subdivision processors P, e.g.
P2 through PN , will similarly accept those control points essential for
the calculation each is to perform.
When all of the patch control points V have been supplied to the buses 52
and 54, the processors P will have calculated subpatch control points for
input to the computer 50 through the input bus 58. Note that, in sequence,
the input bus 58 accepts one subpatch control point to be input from one
processor P during one time interval. Accordingly, the host computer 50
receives subpatch control points, one at a time, placing them in memory.
The total processing time for the subdivision process can accordingly be
equal to the number of time intervals required to output the patch control
points to the processors P plus the number of time intervals needed to
input the subpatch control points from the processors P to the host
computer 50.
Pursuing the exemplary computation of the subpatch P200, as assumed for
subdivision processor P1, reference will now be made to FIG. 4
illustrating a detailed form for the processor P1. Note that the buses
previously identified with respect to FIG. 3 for connection to the host
computer 50 bear the same reference numerals in FIG. 4.
The name bus 54 and the control line 56 are coupled to a random access
memory (RAM) 66 which applies signals to a coefficient bus 68, a register
load line 70, a register clear line 72, and a gate enable line 74. These
signals, applied by the RAM 66, control the operation of the subdivision
processor and are applied by the RAM in response to the signals which are
provided to the RAM 66. Specifically, during a given time interval, the
signals from the name bus 54 and control line 56 are merged to form
address signals which select a word in the RAM 66. The word selected
contains the signals which are applied to the coefficient bus 68, the
register load line 70, the register clear line 72, and the gate enable
line 74. Such RAMs are well known in the prior art related to integrated
circuits. The function of such RAMs to provide distributed signals in
response to address signals is also well known.
As stated, the signals provided from the RAM 66 dictate the operation of
the subdivision processor during each specific time interval and are
provided in response to signals provided to the RAM during that same time
interval via the name bus 54 and the control line 56. Thus, the RAM
contains a program for operation of the subdivision processor. This
program consists of a series of words and is loaded into the RAM at some
time prior to actual subdivision computation via a RAM program data bus
96. Note that the program loaded is specific to the control point to be
calculated by the subdivision processor; thus, the particular control
point calculated by a subdivision processor is determined by the program
loaded into the processor's RAM and is in accord with the calculations as
explained above. Note that it is possible to load different programs into
a single subdivision processor's RAM at different times; therefore, a
single subdivision processor may calculate different control points at
different times, dependent only upon the program loaded. An example of a
specific program will be discussed later in conjunction with a discussion
of the operation of a subdivision processor.
The coefficient bus 68 (from the RAM 66) is connected to a divider 90 and
to a multiplier 76. The multiplier 76 also receives control point signals
from the host computer 50 (FIG. 3) through the control point output bus
52. Signals from the multiplier 76 (FIG. 4) are supplied through a product
bus 78 to an adder 80 with a second input 82. The output from the adder 80
is supplied through a sum bus 84 to a register 86 controlled by the lines
70 and 72. The register 86 is also connected to supply signals to the bus
82 (returning to the adder 80) and to a divider 90. The output from the
divider 90 is supplied to a quotient bus 92 for qualified passage through
a gate 94 which may be enabled by a signal in the line 74 to provide
signals to the control point input bus 58. As suggested above, there are
four sets of multipliers 76, adders 80, registers 86, dividers 90, and
gates 94, one set for each of X, Y, Z, and W. However, all four sets are
controlled by a single set of coefficient bus 68, register load line 70,
register clear line 72, and gate enable line 74.
Consider the operation of the processor P1 of FIG. 4 to generate the
subpatch control point P020 in accordance with the formula above. That is,
consider the computation of P020 (FIG. 2) involving the arithmetic
combination of control points (component values) from the patch V (FIG.
2). Specifically:
P020=(V200+2V110+V020)/4.
For convenience, assume that the signals representative of control points
V200, V110, and V020 appear in that order in the control point output bus
52 and the control point name bus 54. Note that while signals in the
control point output bus 52 manifest the value of a control point,
normally in terms of X, Y, Z, and W, signals in the control point name bus
54 designate the specific control point represented.
As was stated previously, the signals in the control point name bus 54 are
designated by single integers; thus, a specific control point is
designated by a specific integer. The integer "zero" is not used to
specify a control point, but rather is used to initialize the subdivision
processor. Accordingly, the RAM is programmed such that when a zero is
applied to the control point name bus 54, the RAM will assert a "one" in
the register clear line 72. The effect of a "one" in the register clear
line 72 is to set the contents of the register 86 to "zero".
The first operation of the subdivision processor P1 is an initialization
operation. This initialization is directed by means of a "zero" applied to
the control point name bus 54.
During a subsequent operation, a signal specifying the value of control
point V200 appears in the bus 52 concurrently with a signal in the name
bus 54 identifying that control point. Relating to the control point V200,
when such signals appear, the RAM 66 provides a signal representative of
unity or "one" in the coefficient bus 68. Consequently, the value
representative of the control point V200 appearing in the bus 52 is
multiplied by unity in the multiplier 76 and accordingly is supplied as
its value through the product bus 78 to the adder 80. Note that the
register 86 was previously cleared at the beginning of the generation
operation (clear line 72) and accordingly the value of V200 is set in the
register 86 under control of a signal in the line 70.
During a subsequent operation, the control point V110 (FIG. 2) is
designated by a signal in the name bus 54 and the value thereof is
manifest by a signal in the output bus 52. Responding to that control
point, the RAM 66 provides a multiplier of two to the coefficient bus 68.
Consequently, the value of the control point V110 is multiplied by two,
the product being supplied through the product bus 78 to the adder 80
which now functions to combine the value of V200 (from the register 86)
with the product of 2V110. Accordingly, the register 86 now registers a
quantity: (V200+2V 110).
In due course, a designation of the control point V020 is received in the
name bus 54 concurrently with the value of the control point being
received in the output bus 52. Again, in response to the designation of
the control point, the RAM 66 provides a unity or "one" coefficient to the
multiplier 76 with the result that the actual value of V020 is supplied
from the multiplier 76 through the product bus 78 to the adder 80. In the
next phase of operation, the quantity V020 (from the multiplier 76) is
added to the quantity V200+2V110 (from the register 86) to produce the
quantity: (V200+2V110+V020) in the register 86.
When all of the patch control points have been received, the operational
phase of output from the host computer to the subdivision processors is
complete. The next operational phase is that of input from the subdivision
processors to the host computer. During this phase, the names of subpatch
control points are applied sequentially to the control point name bus 54
by the host computer. When the name P020 is applied to this bus, the RAM
66 supplies a "four" to the divider 90 by means of the coefficient bus 68
which prompts the division of the quantity (V200+2V110+V020) by four. The
resulting quotient appearing in the quotient bus 92 is a signal
representation of P020. Again under control of the RAM 66, the line 74
passes an enable signal to the gate 94 with the consequence that signals
representative of P020 are supplied through the input bus 58 to the host
computer 50 (FIG. 1).
The operations described above are sequenced in time under control of the
RAM 66 as explained. However, in that regard, an indication of the program
for the RAM 66 is set out below in tabular form and in time sequence. The
first column of the following chart designates sequencing time intervals 1
through 8. The subsequent columns designate signal content provided on
various lines and buses to develop the values indicated at the right side
of the chart during the indicated actions of the final column.
__________________________________________________________________________
OPERATION SUMMARY - FIG. 4
Time Register Comment
1 2 3 4 5 6 7 8 9 10 11
__________________________________________________________________________
1 0 0 1 0 0 Initialize
2 0 V200 V200 1 1 0 0 V200 Accumulate
data
3 0 V110 V110 2 1 0 0 V200+2V110
Accumulate
data
4 0 V101 V101 0 0 0 V200+2V110
Do nothing
data
5 0 V020 V020 1 1 0 0 V200+2V110+V020
Accumulate
data
6 0 V011 V011 0 0 0 V200+2V110+V020
Do nothing
data
7 0 V002 V002 0 0 0 V200+2V110+V020
Do nothing
data
8 1 P020 P020
4 0 0 1 V200+2V110+V020
Put P020 on
data control point
input bus
9-22
1 Other Other 0 0 0 V200+2V110+V020
Do nothing
P,Q,R,S P,Q,R,
S data
__________________________________________________________________________
Column representations in the above chart are as follows:
______________________________________
Column No.
______________________________________
1 Time intervals, e.g. T1-T22.
2 Binary signal on input/output
control line 56.
3 Control point name bus 54.
4 Control point output bus 52.
5 Control point input bus 58.
6 Coefficient bus 68.
7 Binary signal in register load
line 70.
8 Binary signal in register clear
line 72.
9 Binary signal in gate enable
line 74.
10 Accumulated value in register
86.
11 Functional operation.
______________________________________
While only rows 1 through 8 are elaborated in the above chart, the
operation would actually constitute some twenty-two intervals to
accomplish the computation and input to the host computer of each of the
subpatch control points as illustrated in FIG. 2b. That is, in accordance
with the above assumptions, all subpatch control points were generated in
the initial seven time intervals. The following fifteen time intervals
(8-22) are required to input the subpatch control points to the host
computer. In that regard, it is to be noted that the order in which the
control points are provided or received by the host computer 50 is
unimportant because in the system of FIG. 3, each control point is
specified by name in the form of a representative signal.
Further with respect to the system of FIG. 3, it is to be appreciated that
each subdivision processor P (specifically processors P1 and P2 through
Pn) is identical to each other subdivision processor. That is, the
tailoring of an individual subdivision processor for the calculation of a
specific control point is accomplished by means of the program loaded into
the RAM 66. Thus, the RAM 66 of each subdivision processor contains a
different program. While this use of RAM provides a rather general
solution to the subdivision problem, this generality is achieved at the
expense of a somewhat large RAM. The RAM 66 may be replaced with a
significantly more compact programmable logic array (PLA). Such PLAs are
well known in the prior art related to integrated circuits. A PLA differs
from a RAM in that different programs cannot be loaded into it; rather, it
has one program built into it, and this program cannot be changed. Using a
PLA implementation, each subdivision processor P would differ from all
other subdivision processors in two respects. First, the RAM 66 would be
replaced by a PLA unique to each subdivision processor, which PLA would
generate unique signals in response to receiving signals from the host
computer 50 to accomplish the desired manipulations for that subdivision
processor. Thus, each subdivision processor would calculate one control
point only. Second, the divider, as the divider 90, in each processor P
would divide by one divisor only. That is, the calculation of a unique
control point involves division by a unique divisor. Since each
subdivision processor would calculate a unique control point, that
subdivision processor would perform division by the unique divisor
specific to that control point. For example, in the previously discussed
calculation of the control point P200, division by four was required.
However, the processor P for computing:
R101=(V101+V002)/2
would require division by two. For such a computation, the assigned
processor would have a unique program in its PLA replacing the RAM 66.
Also, division would be by two rather than four as described above with
reference to the processor P1.
As indicated above, the individual equations for computing the different
control points of a subpatch vary considerably; however, certain
properties exist between those equations which can be exploited in a
subdivision processor. For example, consider the two equations of the
subdivision illustrated in FIG. 2:
P020=(V200+2V110+V020)/4
R101=(V101+V002)/2.
The two equations are significant in that the control points of the patch V
do not intersect. That is, the subset of control points used to compute
P020 does not intersect with the subset of control points used to compute
R101. Consequently, a single processor can be employed to compute both the
subpatch control points P020 and R101 providing the processor is equipped
with distinct and separate registers and includes a minor amount of
additional operating circuitry. In that regard, the two computation
structures can share a control PLA and a multiplier. Those elements
constitute a major portion of the processor. Accordingly, such a
structural arrangement is advantageous. A form thereof is illustrated in
FIG. 5.
As before, previously identified components are designated by identical
reference numerals. In that regard, FIG. 5 shows an input/output control
line 56 (upper left) above a control point name bus 54. Those signal paths
are coupled to a coefficient and control programmable logic array (PLA)
102 of the type described above.
The PLA 102 provides several binary control signals individually to a set
of control lines. Also, it provides coefficient values to a multiplier 103
through a coefficient bus 104. The multiplier 103 also receives control
point signals through the output bus 52.
Generally, the multiplier 103 accomplishes multiplications in executing
control point formulas, supplying products to separate apparatus for
developing the subpatch control points R101 and P020 separately. That is,
signals from the multiplier 103 are applied to an apparatus channel
generally indicated by the reference numeral 106 for developing the
control point P020. Signals from the multiplier 103 are also supplied to
an apparatus channel generally indicated by the numeral 108 for computing
the subpatch control point R101. Each channel includes separate structures
as treated in detail below. The operation of the system of FIG. 5 involves
the development of the control points P020 and R101 independently in the
channels 106 and 108 somewhat as described with reference to the system of
FIG. 4. Accordingly, in the chart format as explained above, the operation
of the system of FIG. 5 to accomplish signals representative of the
control points P020 and R101 in the control point input bus 58 is
summarized in the following chart:
__________________________________________________________________________
OPERATION SUMMARY - FIG. 5
P020 R101
Time Register Register
1 2 3 4 5 6 7 8 9 10
11
12 13
__________________________________________________________________________
1 0 0 0 1 0 0 0 0
2 0 V200 V200 1 1 0 0 0 0 V200 0
data
3 0 V110 V110 2 1 0 0 0 0 V200+2V110
0
data
4 0 V101 V101 1 0 1 0 0 0 V200+2V110
V101
data
5 0 V020 V020 1 1 0 0 0 0 V200+2V110+V020
V101
data
6 0 V011 V011 0 0 0 0 0 V200+2V110+V020
V101
data
7 0 V002 V002 1 0 1 0 0 0 V200+2V110+V020
V101+V002
data
8 1 P020 P020 0 0 0 1 0 V200+2V110+V020
V101+V002
data
9 1 R101 R101 0 0 0 0 1 V200+2V110+V020
V101+V002
data
10-22
1 Other Other 0 0 0 0 0 V200+2V110+V020
V101+V002
P,Q,R,S P,Q,R,
S data
__________________________________________________________________________
The columns of the above chart designate representations as follow:
Column 1 indicates the time sequences of operation, e.g. T1-T22.
Column 2 indicates the binary signal of the input/output control line 56.
Column 3 shows the contents of the control point name bus 54 at various
times.
Column 4 shows the contents of the control point output bus 52 at different
times.
Column 5 shows the contents of the control point input bus 58 at certain
time intervals.
Column 6 shows the content of the coefficient bus 104 at certain intervals.
Column 7 designates the binary signal in the P020 register load line 110.
Column 8 indicates the binary signal for the R101 register load line 112.
Column 9 indicates the binary signal in the register clear line 114.
Column 10 indicates the contents of the P020 gate enable line 116.
Column 11 indicates the contents of the R101 gate enab1e 1ine 118.
Column 12 indicates the contents of the P020 register 120.
Column 13 indicates the contents of the R101 register 122.
Although the above chart provides a tabular summary of the operating
sequence for the system of FIG. 5, a detailed description will afford a
complete understanding. Accordingly, assume the apparatus of FIG. 5 is
coupled to receive signals as described above from a host computer 50
(FIG. 3). The operation of the system of FIG. 5 to accomplish
representations of the control points P020 and R101 will now be described
somewhat concurrently with the introduction of structural elements not
previously introduced. As in the system of FIG. 4, the subdivision
processor is initialized by providing a "zero" signal in the control point
name bus 54. In response to this signal, the PLA 102 provides a "one"
signal in the register clear line 114. The effect of this "one" is to set
the contents of the P020 register and the contents of the R101 register to
"zero".
As in the system of FIG. 4, assume a predetermined sequence for signals
representative of control points for the patch V. That sequence is set out
in Column 3 of the above chart, specifically the sequence is: V200, V110,
V101, V020, V011, and V002.
With the occurrence of the initial control point signals (representative of
V200, during time interval 2), the PLA 102 is actuated. Specifically, the
control point V200 is recognized for the computation of the subpatch
control point P020. Accordingly, a value of "one" appears on the
coefficient bus 104 actuating the multiplier 103 to multiply the value of
the control point V200 and supply the result to the P020 adder 132. As the
P020 register was previously cleared by the register clear line 114, the
value of V200 is set in the P020 register 120.
On the occurrence of signals representing the control point V110, the
system is again active. Specifically, the PLA 102 supplies a coefficient
value of "two" to the multiplier 103 which also receives the value of the
control point V110. As a result, the product 2V110 is added to the
quantity V200 by the adder 132, the sum being placed in the P020 register
120. The partially computed value for the subpatch control point P020 is
held in the register 120 awaiting the next pertinent signal representative
of a control point of the patch V which is employed in that computation.
Upon the occurrence of the signal representative of the control point V101,
the apparatus 108 (FIG. 5) begins the computation of the subpatch control
point R101. This operation is indicated in the above chart, tabulated at
interval four. Specifically, the PLA 102 provides a coefficient "one"
unity to the multiplier 103 so that the value of the control point V101 is
supplied to a R101 adder 136. Note that the register 122 was previously
cleared with the consequence that the value of control point V101 is set
in the register 122. Note also that the P020 register 120 is inactive
during this interval as it does not receive a load command signal from the
line 110.
The numerators of the control points P020 and R101 are thus developed
stage-by-stage in the registers 120 and 122 as the relevant control points
of patch V are supplied. When so developed, a pair of dividers 140 and 142
perform the requisite divisions to accomplish signals representative of
the control points P020 and R101 respectively. These signals are
respectively gated from the dividers 140 and 142 by control gates 144 and
146 to the control point input bus 58.
From the above consideration of the structure of FIG. 5 it may be seen that
a single processor P (FIG. 3) may compute multiple subpatch control points
without loss of time. To recap such operations, as summarized in the above
chart, during time intervals 2, 3, and 5 the register 122 is inhibited by
"zero" signals (Column 8 of chart). At those times, the host computer
places control point names V200, V110, and V020 respectively on the
control point name bus 54 (Column 3). Since these control points are used
in the computation of control point P020, during each of these time
intervals (times 2, 3, and 5) the PLA 102 places | | |
