 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computer graphics display systems, and more
particularly relates to such a graphics computer system that employs
parallel processors in a display processor portion thereof.
2. Background Art
Besides Lines, Markers and Polygons, Computer Graphics Displays today
support more general geometric primitives, such as Spline Curves and
Spline Surfaces.
In the Computer Aided Design/Computer Aided Manufacture ("CAD/CAM") area,
most of the geometric data can be covered by using Non-Uniform Rational
B-Spline of degree less than or equal to three-linear, quadratic or cubic
(see the sections below). For Non-Uniform Rational B-Spline Surfaces,
there exist techniques to break up the surface into simpler Rational
Bezier Surface Patches.
A system is described herein which uses Parallel Processors to implement
the display function of Rational Bezier Surface patches for both wireframe
model and solid/shaded model. The use of Parallel Processors to implement
display functions in computer graphics system has been described generally
in an article by James Clark of Stamford University, "A VLSI Geometry
Processor for Graphics," Clark, James, COMPUTER, Jul. 1980, pp. 59-68.
U.S. Pat. No. 4,187,539 to Eaton describes a pipelined data processing
system with centralized microprogram control.
However, absent in the prior art is a processing system that permits
efficient parallel and pipelined processing for generating surface
information for a graphics display system. Prior art arrangements require
complicated and extensive external control logic, where attempts have been
made to combine a number of processors together in graphics processing. As
a result, progress heretofore in the area of more efficient processing in
workstations of graphics computer systems has been limited.
For example, conventionally CAD/CAM applications use graphics workstations
by sending down the polygons which make up the objects stored in the host
computer data base, rather than the Spline surface form data stored in the
data base. According to this procedure, the host computer decomposes the
Spline surface into flat polygons, and then sends the polygons to the
graphics workstation. The graphics workstation then processes the polygons
for display.
The drawbacks of this approach are several. First, the host processor takes
more time to do the Spline surface decomposition than would be desired.
Second, by requiring the host processor to generate the data corresponding
to the polygons, more data must be sent between the host processor and the
graphics workstation. This ties up the transmission link which may be
sharing with other applications and graphics workstations. Thirdly, when
local zooming is applied to the polygonal data, the display of the model
loses its smoothness. As a result, the program in the graphics workstation
must notify the host computer to decompose the surface data and send the
polygon again, to restore the smoothness of the object being zoomed.
Accordingly, it is an object of the present invention to provide a
processing system that generates surface information for a graphics
display system.
It is a further object of the invention to provide a processing system
wherein the processing to generate surface information is performed in
parallel, pipelined fashion.
It is a still further object of the present invention to provide a
processing system in which surface information is generated according to
rational B Spline computation in an efficient manner.
It is a still further object of the present invention to provide a
processing system in which Spline surface computation of polygons can be
performed in a graphics workstation, rather than in a host processor.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for generating
surface information for a graphics display system. Data that represents
the surface to be processed is provided from storage to a transformation
processor that further comprises a plurality of floating point processors
connected in parallel. The data is processed in parallel in the
transformation processor, such that the surface is tesselated into a
plurality of patches. A floating point processor is provided for further
processing to generate the normals at the vertices of the patches, the
further floating point processor being connected to the outputs of the
parallel processors.
This novel arrangement of floating point processors in parallel and
pipeline configuration represents an advance in the art that permits the
generation of surface data in an efficient manner, as compared with prior
art arrangements. By doing the processing to tesselate a surface into
patches by way of processors connected in parallel, and then providing
that data to a further processor and pipeline to generate the normals at
the vertices of the patches, greatly enhanced processing efficiency is
provided as compared with the prior art.
The foregoing and other objects, features and advantages of the invention
will be apparent from the more particular description of the preferred
embodiments of the invention, as illustrated in the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a raster graphics system embodying the present
invention.
FIG. 2 is a block diagram of a transformation processor embodying the
present invention.
FIG. 3 is a flow chart of a functional partition for surface patch
processing according to the present invention.
FIG. 4 is a block diagram of a system for generating rational bezier
surfaces according to the present invention.
FIG. 5 is an input/output of the system components.
FIG. 6 is a surface patch orientation.
FIG. 7 is a flow chart of a X-component processor according to the present
invention.
FIG. 8 is a flow chart of a Y-component processor according to the present
invention.
FIG. 9 is a flow chart of a Z-component processor according to the present
invention.
FIG. 10 is a flow chart of a W-component processor according to the present
invention.
FIG. 11 is a procedures for generating points.
FIG. 12, which includes FIGS. 12, 13 and 14 together is a flow chart of
patch processing in accordance with the present invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT OF THE INVENTION
A Graphics system for raster display in accordance with the preferred
embodiment of the present invention is described in this section and shown
in block diagram form in FIG. 1. The display has 24-bit planes, and the
resolution is 1024 by 1024.
Raster Graphics Display System 10 is shown in FIG. 1. It comprises System
Memory 12, a Display Processor 14, and Video Pixel Memory 16 which is read
to drive a Monitor (not shown). Memories 12, 16 are of conventional
design, and are not explained in detail herein.
The Display Processor 14 comprises:
1. a Graphics Control Processor (GCP) 20,
2. a Transformation Processor (TrP) 30,
3. a Drawing Processor (DRP) 40, and
4. a Shading Processor (ShP) 50.
DRP 40 and ShP 50 operate in pipeline and/or parallel. They are special
purpose processors that execute programs residing in system memory 12,
using a set of prestored microcoded programs residing in their own
writable control store. They use their own working memory, to store
constants and parameters, used by the program.
There are two types of geometric data processed by the Graphics Display
System 10:
1. Wireframe Data
This data includes the basic geometric primitives --lines (vectors),
markers, and polygons (the edges of the polygons), the segments
representing spline curves, and the segments representing the boundaries
of a spline surface patch (wireframe model).
2. Solid and Shaded Surface Data
The data flow through System 10 shown in FIG. 1 is from the System Memory
12, through the GCP-TrP-DrP pipeline of Display Processor 14 to the Video
Pixel Memory 16, then to the monitor (not shown) for display.
For the processing of the geometric primitives, the Functional Partition of
the graphics system is as follows:
GCP-20
fetches and processes instructions from the System Memory 12;
decomposes the non-uniform Rational B-spline into Rational Bezier Patches;
passes the geometric data to the TrP 30 for transformation and clipping;
passes the command (e.g. frame control orders) to the DrP 40.
TrP-30
receives the geometric data (e.g. end points of lines) from GCP 20;
transforms and clips the coordinates of the data in the floating point
format;
generates the segments for the spline curve;
generates the boundary data for the surface patch;
passes the data to the DrP 40 for the drawing of wireframe model;
passes the data to the ShP 50 for the drawing of solid/shaded model.
DrP-40
receives the geometric data-lines, characters markers, polygons from the
TrP 30; and rasterizes the data to the Video Pixel Memory 16 for display
receives the commands from GCP 20 and interfaces with
a Vector-to-Raster Converter;
Video Pixel Memory Frame Buffers;
a Video Look-Up Table;
all of conventional design.
ShP-50
receives the geometric data--boundary information about the surface
patches, the coordinates of the corners, and the normals from the TrP
30--shades the patches by calculating the color/intensity for each pixel,
and then rasterizes the data to the Video Pixel Memory 16 for display.
A major building block of the Display Processor 14, used repeatedly
throughout as described below, is a Graphics Floating Point Processor, a
VLSI processor with 32-bit floating point capability.
It includes:
1. a floating point multiplier;
2. a floating point adder, also used as an accumulator for the multiplier;
3. a simple sequencer;
4. RAM for microcode;
5. FIFO for input and output for interface;
6. Sixty-four registers for storing data.
Floating point processors are known generally in the art. U.S. patent
application Ser. No. 07/115,150, filed Oct. 30, 1987, commonly assigned,
discloses an invention which provides special input and output FIFOs for
advantageous parallel and/or pipelined interconnection in the manner
herein described, and is hereby incorporated herein by reference. The
Graphics Floating Point Processor can be used in a number of different
configurations as will become apparent from the description below.
GCP 20 includes a CPU, an interface to the Transformation Processor 30, a
bus interface, and a floating point processor, e.g. a Graphics Floating
Point Processor.
TrP 30, shown in FIG. 2, comprises ten Graphics Floating Point Processors
(hereinafter "GFPP"), in serial and parallel as shown to handle
transformation, clipping, and mapping.
The GCP 20-TrP 30 data interface is the 32-bit IEEE floating point format.
The output 32 of the TrP 30 is sent to the DRP 40 and to a register (not
shown) which can be read by the GCP 20.
The TrP 30 consists of ten GFPP chips, which are arranged in the following
four stages:
1. Transformation Module 300
four GFPPs 310, 320, 330, 340, in parallel for transformation, generating
spline curves, and generating spline surface patches.
2. Surface Patch Module 350
one GFPP for generating the boundary data for surface patches--vertices
coordinates and normals (tesselation).
3. Clipping Module 301
three GFPPs 360, 370, 380, in series for line and polygon clipping.
4. Mapping Module 302
two GFPPs 390, 400, in series for perspective projection and mapping to the
viewport on the screen.
The TrP 30 supports Rational Bezier Surfaces. The definition of the Cubic
Rational Bezier Surface Patches are covered here; the case of Quadratic is
similar.
The Rational Bezier Surface Patch is defined by:
1. Coordinates of sixteen control points, together with their associated
weights w's (which are all positive)
for i=1 to 4, and j=1 to 4:
P{i,j}=(x{i,j},y{i,j},z{i,j}, w{i,j})
2. Blending functions (for Cubic Bezier) B1(t), B2(t), B3(t), B4(t):
B1(t)=(1-t).sup.3
B2(t)=3t(1-t).sup.2
B3(t)=3(1-t)t.sup.2
B4(t)=t.sup.3
3. The parametric equations for the patch in (s,t) for 0.ltoreq.s.ltoreq.1
and 0.ltoreq.t.ltoreq.1:
X(s,t)=sum(w{i,j}x{i,j}Bi(s)Bj(t))/sum(w{i,j}Bi(s)Bj(t))
Y(s,t)=sum(w{i,j}y{i,j}Bi(s)Bj(t))/sum(w{i,j}Bi(s)Bj(t))
Z(s,t)=sum(w{i,j}x{i,j}Bi(s)Bj(t))/sum(w{i,j}Bi(s)Bj(t))
where the sum is over the index 1.ltoreq.i.ltoreq.4, and
1.ltoreq.j.ltoreq.4.
Using the notation of Homogeneous Coordinate, the above three parametric
equations can be rewritten as follows:
x(s,t)=sum(w{i,j}x{i,j}Bi(s)Bj(t))
y(s,t)=sum(w{i,j}y{i,j}Bi(s)Bj(t))
z(s,t)=sum(w{i,j}z{i,j}Bi(s)Bj(t))
w(s,t)=sum(w{i,j}Bi(s)Bj(t))
and
X(s,t)=x(s,t)/w(s,t)
Y(s,t)=y(s,t)/w(s,t)
Z(s,t)=z(s,t)/w(s,t)
Each of x(s,t), y(s,t), z(s,t), and w(s,t) is a polynomial of two
variables; and each has sixteen terms.
##EQU1##
There is another way to generate the functions x(t), Y(t), z(t), w(t); of
the sixteen coefficients of each polynomials by using matrix
multiplication:
Let S be the 1.times.4 matrix
S=(s.sup.3, s.sup.2, s,1); and (1)
T the 4.times.1 matrix
##EQU2##
The Cubic splines can be represented as a 4.times.4 matrix
##EQU3##
By selecting the elements in the matrix V, different splines can be
generated.
e.g. The Bezier spline is given by
##EQU4##
Let Vt be the Transpose Matrix of V
##EQU5##
for the Bezier spline, Vt is given by
##EQU6##
which is the same as V.
Let WX denote the 4.times.4 matrix
##EQU7##
In the notation above, the five matrices are multiplied in the following
order:
##EQU8##
The product S.V.WX.Vt.T is x(s,t).
Since V=V.sub.t for Rational Bezier Surfaces, this is the same as the
product S.V.WX.V.T.
The product V.WX.V is a 4.times.4 matrix
##EQU9##
which are the coefficients of x(s,t).
Matrices WY, WZ, and W can be defined in the same way to yield y(s,t),
z(s,t), and w(s,t);
and matrices V.WY.V., V.WZ.V, and V.W.V will yield the coefficients
matrices B, C, and D for y(s,t), z(s,t) and w(s,t).
for y(s,t)
##EQU10##
for z(s,t);
##EQU11##
for w(s,t);
##EQU12##
The spline equation is invariant under an affine transformation:
If M is an affine transformation represented by the 4.times.4 matrix:
##EQU13##
then the Rational Bezier Surfaces after the transformation is the same as
the Rational Bezier Surfaces defined by the same matrix V, same weights
but with the transformed control points.
There are two different types of graphics displays associated with Rational
Bezier Surfaces:
1. the Wireframe Model, in which the surface patch is displayed as
wireframe meshes; and
2. the Filled or Shaded Model, in which the surface patch is displayed
either in solid color, or as a shaded model with given light sources which
yield different color and intensity for each pixel on the patch.
The four stages in generating the spline curves for wireframe display are
as follows:
1. Transform the sixteen control points;
2. Construct four polynomials:
x(s,t), y(s,t), z(s,t), w(s,t);
3. Compute the three equations for P(s,t):
X(s,t)=x(s,t)/w(s,t)
Y(s,t)=y(s,t)/w(s,t)
Z(s,t)=z(s,t)/w(s,t)
for each of the x, y, z coordinates; and
4. Generate line segments from the three equations for display:
Using two parameters s,t to generate two families of parametric curves by
two numbers ds and dt
for n=0 to 1/dt; generate line segments for the curve
F(s)=P(s,n*dt)
for m=0 to 1/ds; generate line segments for the curve
F(t)=P(m*ds,t).
In Filled or Shaded Model processing, TrP 30 generates small patches for
Shading. The parameters of each output patch are
the coordinates of the four corners of the patch, and
the normal vector (to the surface) at the corner.
The four stages in generating the Rational Bezier Surface patches for
display are as follows:
1. Transform the sixteen control points;
2. Construct for polynomials
x(s,t), y(s,t), z(s,t), w(s,t);
3. Compute the three equations for P(s,t):
X(s,t)=x(s,t)/w(s,t)
Y(s,t)=Y(s,t)/w(s,t)
Z(s,t)=z(s,t)/w(s,t)
for each of the x, y, z coordinates; and
4. Generate patches from the three equations for display:
Using two parameters s,t to generate two families of parametric curves by
two numbers ds and dt
generate the coordinates of the four vertices of a patch: for n=0 to 1/dt;
and for m=0 to 1/ds;
F(m,n+1)=P(m*ds,(n+1)*dt)
F(m,n)=P(m*ds,n*dt)
F(m+1,n)=P((m+1)*ds,n*dt)
F(m+1,n+1)=P((m+1)*ds,(n+1)*dt)
generate normals (to the patch) at the vertices
output the data, and generate next patch.
The Rational Bezier Surfaces can be considered as a special case of the
more general Non-Uniform Rational B-Spline Surfaces.
A pre-processing program can be implemented in the GCP 20 to decompose
Non-Uniform Rational B-Spline Surfaces into patches of Rational Bezier
Surfaces according to known mathematical procedures.
Now follows a brief description of the Rational Bezier Spline Curves, which
can be viewed as special case of Rational Bezier Spline Surfaces.
The input of a Cubic Rational Bezier Spline Consists of the coordinates of
four control points: P1, P2, P3, P4; and four positive numbers w1, w2, w3,
w4, called weights.
P1=(x1,y1,z1),w1
P2=(x2,y2,z2),w2
P3=(x3,y3,z3),w3
P4=(x4,y4,z4),w4
The formula for the cubic is as follows:
R(t)=B1(t)w1 P1+B2(t)w2 P2 +B3(t)w3 P3+B4(t)w4 P4
w(t)=B1(t)w1+B2(t)w2 +B3(t)w3+B4(t)w4
P(t)=R(t)/w(t)
where t ranges form 0 to 1.
P(t) represents three equations X(t), Y(t), Z(t)
R(t)=(x(t),y(t),z(t))
X(t)=x(t)/w(t)
Y(t)=y(t)/w(t)
Z(t)=z(t)/w(t)
B1(t), B2(t), B3(t), B4(t) are called the blending functions for cubic
spline:
B1(t)=(1-t)**3
B2(t)=3t(1-t)**2
B3(t)=3(1-t)t**2
B4(t)-t**3
There are three stages in generating the cubic spline curves for display:
1. transform control points;
2. construct four polynomials x(t), y(t), z(t), and w(t) from the control
points, weights, and blending functions;
3. the three equations are:
X(t)=x(t)/w(t)
Y(t)=y(t)/w(t)
Z(t)=z(t)/w(t)
for each of the x, y, z coordinate
4. generate the line segment from the three equations for display.
The matrix expression for splines curves is covered above.
To generate segments approximating the spline, we choose a sequence of
t-values between 0 and 1 in the increasing order 0=t0, t1, . . ., tm=1;
and evaluate the corresponding x, y, z value.
For simplicity, the t-value is chosen in such a way that the differences
between two adjacent t-values are the same.
Because the weights are positive the curve is inside the convex hull
generated by the four control points.
Let
xdiameter=max(x1,x2,x3,x4)-min(x1,x2,x3,x4)
ydiameter=max(y1,y2,y3,y4)-min(y1,y2,y3,y4)
zdiameter=max(z1,z2,z3,z4)-min(z1,z2,z3,z4)
diameter=max(xdiameter,ydiameter,zdiameter)
The number m is then given by:
2 * diameter * window-to-viewport ratio.
Assume f(t)=a t**3+b t**2+c t+d is a polynomial function over the interval
(0,1), and e=1/m is the increment.
To evaluation the polynomial values:
Assume f(t)=a t**3+b t**2+c t+d is a polynomial. It can be expressed into
the following form ((a t+b) t+c) t+d.
For each t-value, we use three multiplication and three addition to
evaluation the function.
The operation and microprogramming of the Pipeline sub-system which is
comprised of the TrP 30 sets and Surface Patch Module 350 will now be
described. See FIG. 3. Also see FIG. 4 for the system configuration.
The output of GCP 20 is sent to the four Graphics Floating Point
Processors, 310, 320, 330, 340, (see FIG. 2) in parallel simultaneously-to
their FIFOs.
The outputs of the four GFPPs 310, 320, 330, 340, to the Surface Patch
Module GFPP 350 are stored in the output FIFO of the four GFPPs, and are,
in turn, read out by the Surface Patch Module GFPP 350 synchronized by
microcode inside the GFPP.
The following is a description of the programming of the TrP 30, which
comprises the TrP 30 and a Surface Patch Module 350.
The Inputs and Outputs of these components are shown in FIG. 5.
Three commands, Load Spline Curve Matrix-LSCM, start Spline Surface
Processing-STPS, and End Spline Surface Processing-ENPS, are used in the
system processing. They will now be described.
A. Load Spline Curve Matrix-LSCM
The LSCM command loads the Spline Curve Matrix or Surface Matrices to TrP
30. The command indicates whether the data words are matrix elements for
one matrix for a Spline Curve, or elements for two matrices for a Spline
Surface.
In Spline curve processing, the LSCM control word is followed by 16 words
of data-the matrix elements defining the spline: LSCM, s11, s12, s13, s14,
s21, s22, s23, s24, s31, s32, s34, s41, s42, s43, s44.
The Spline matrix is given by
##EQU14##
The above 4.times.4 matrix is for Cubic Splines.
For Quadratic Splines, the 4th row and the 4th column contain 0's.
##EQU15##
In Spline surface processing, the LSCM control word is followed by 32 words
of data-the matrix element defining the spline surface: LSCM, s11, s12,
s13, s14, s21, s22, s23, s24, s31, s32, s33, s34, s41, s42, s43, s44, t11,
t12, t13, t14, t21, t22, t23, t24, t31, t32, t33, t23, t41, t42, t43, t44.
There are two matrices: S and T.
The Spline matrix S is given by:
##EQU16##
The above 4.times.4 matrix is for Cubic Splines.
For Quadratic Splines, the 4th row and the 4th column contain 0's.
##EQU17##
The Spline matrix T is given by
##EQU18##
The above 4.times.4 matrix is for Cubic Splines.
For Quadratic Splines, the 4th row and the 4th column contain 0's.
##EQU19##
B. Start Spline Surface Processing-STPS
This command is followed by coordinates of control points and weights
defining the spline surface.
The control points defining the surface are given by a two dimensional
array, associated with the S and T matrices.
The command denotes the degree of the spline curves associated with the S
matrix, either a cubic spline or a quadratic spline.
The command also denotes the degree of the spline curves associated with
the T matrix, again, either a cubic spline or a quadratic spline.
The control points are given in a matrix format,
number of row=order of S curve,
number of column=order of T curve, and
order of S=degree of S+1.
For example, if the command indicates S matrix cubic spline, T matrix
quadratic spline, then the control points are given by the following
matrix
##EQU20##
where each pij=(xij, yij, zij) is a control point.
Thus, the data flow is as follows: STPS, tag, x11, y11, z11, w11, x12, y12,
z12, w12; x1j, y1j, z1j, w1j, x21, y21, z21, w21, x22, y22, z22, w22; x2j,
y2j, z2j, w2j; xi1, ti1, zi1, wi1, xi2, yi2, zi2, wi2; xij, yij, zij,
ENPS,
where
i=b'ss'+b'01' and
j=b'tt'+b'01'.
C. End Spline Surface Processing-ENPS
This command signals the end of data list for a spline surface.
The following is a procedure to generate Rational Bezier Surface Patches.
Although only cubic splines are covered here, the quadratic ones can be
handled in the same way.
The generation of Rational Bezier Surfaces is done in the TrP 30 and the
Surface Patch Module GFPP 350 (see FIG. 4).
The input parameters for a cubic spline to the TrP 30 are as follows:
First, however, note that the following is the matrix generating the cubic
Bezier splines:
##EQU21##
Explicity, the cubic Bezier spline is given by the following matrix:
##EQU22##
The data list consists of the coordinates of 16 points and 16 weights.
x11, y11, z11, w11;
x12, y12, z12, w12;
x13, y13, z13, w13;
x14, y14, z14, w14;
x21, y21, z21, w21;
z22, y22, z22, w22;
x23, y23, z23, w23;
x24, y24, z24, w24;
x31, y31, z31, w31;
x32, y32, z32, w32;
x33, y33, z33, w33;
x34, y34, z34, w34;
x41, y41, z41, w41;
x42, y42, z42, w42;
x43, y43, z43, w43;
x44, y44, z44, w44.
The generation of the Cubic Bezier Spline by using Transformation Module
GFPPs 310-340 will now be described.
The procedure for generating x-coordinate data (GFPP 310) follows. See FIG.
7.
First, the input is as follows.
x11, y11, z11, w11; (coordinates of sixteen points and sixteen weights)
x12, y12, z12, w12;
x13, y13, z13, w13;
x14, y14, z14, w14;
x21, y21, z21, w21;
x22, y22, z22, w22;
x23, y23, z23, w23;
x24, y24, z24, w24;
x31, y31, z31, w31;
x32, y32, z32, w32;
x33, y33, z33, w33;
x24, y34, z34, w34;
x41, y41, z41, w41;
x42, y42, z42, w42;
x43, y43, z43, w43;
x44, y44, z44, w44.
The output is the four x-coordinates for four corners of patch.
Constants involved are: m11,m21,m31,m41 (first column of the transformation
matrix Spline matrix)
##EQU23##
The Bezier spline is given by the following matrix.
##EQU24##
Variables involved are:
##EQU25##
The procedure is as follows.
1. Transform the vertex, and multiply the coordinates by weights
all .rarw.m11*x11+m21*y11+m31*z11+m41
all .rarw.all*w11
a12 .rarw.m11*x12+m21*y12+m31*z12+m41
a12 .rarw.a12*w12
a13 .rarw.m11*x13+m21*y13+m31*z13+m41
a13 .rarw.a13*w13
a14 .rarw.m11*x14+m21*y14+m31*z14+m41
a14 .rarw.a14*w14
a21 .rarw.m11*x21+m21*y21+m31*z21+m41
a21 .rarw.a21*w11
a22 .rarw.m11*x22+m21*y22+m31*z22+m41
a22 .rarw.a22*w12
a23 .rarw.m11*x23+m21*y23+m31*z23+m41
a23 .rarw.x23*w13
a24 .rarw.m11*x24+m21*y24+m31*z24+m41
a24 .rarw.x24*w14
a31 .rarw.m11*x31+m21*y31+m31*z31+m41
a31 .rarw.x31*w11
a32 .rarw.m11*x32+m21*y32+m31*z32+m41
a32 .rarw.x32*w12
a33 .rarw.m11*x33+m21*y33+m31*z33+m41
a33 .rarw.a33*w13
a34 .rarw.m11*x34+m21*y34+m32*z34+m41
a34 .rarw.a34*w14
a41 .rarw.m11*x41+m21*y41+m31*z41+m41
a41 .rarw.a41*w11
a42 .rarw.m11*x42+m21*y42+m31*z42+m41
a42 .rarw.a42*w12
a43 .rarw.m11*x43+m21*y43+m31*z43+m41
a43 .rarw.a43*w13
a44 .rarw.m11*x44+m21*y44+m31*z44+m41
a44 .rarw.a44*w14
2. Generate the coefficients for the polynomial equation.
Concatenate three matrices, V.WX.Vt, for Bezier Spline; V is equal to Vt.
Ten terms of V are non-zero for cubic Bezier.
a. Concatenate WX.Vt, where Vt=V, and v24=v33=v34=v42=v43=v44=0.
tempa1 .rarw.a11*v11+a12*v21+a13*v31+a14*v41
tempa2 .rarw.a11*v12+a12*v22+a13*v32
tempa3 .rarw.a11*v13+a12*v23
a14 .rarw.a11*v14
a11 .rarw.tempa1
a12 .rarw.tempa2
a13 .rarw.tempa3
tempa1 .rarw.a21*v11+a22*v21+a23*v31+a24*v41
tempa2 .rarw.a21*v12+a22*v22+a23*v32
tempa3 .rarw.a21*v13+a22*v23
a24 .rarw.a21*v14
a21 .rarw.tempa1
a22 .rarw.tempa2
a23 .rarw.tempa3
tempa1 .rarw.a31*v11+a32*v21+a33*v31+a34*v41
tempa2 .rarw.a31*v12+a32*v22+a33*v32
tempa3 .rarw.a31*v13+a32*v23
a34 .rarw.a31*v14
a31 .rarw.tempa1
a32 .rarw.tempa2
a33 .rarw.tempa3
tempa1 .rarw.a41*v11+a42*v21+a43*v31+a44*v41
tempa2 .rarw.a41*v12+a42*v22+a43*v32
tempa4 .rarw.a41*v13+a42*v23
a44 .rarw.a41*v14
a41 .rarw.tempa1
a42 .rarw.tempa2
a43 .rarw.tempa3
b. Concatenate V.(WX.Vt). Only ten terms of V, the matrix for cubic Bezier,
are non-zero, and v24=v33=v34=v42=v43=v44=0.
tempa1 .rarw.v11*a11+v12*a21+v13*a31+v14*a41
tempa2 .rarw.v21*a11+v22*a21+v23*a31
tempa3 .rarw.v31*a11+v32*a21
a41 .rarw.v41*a11
a11 .rarw.tempa1
a21 .rarw.tempa2
a31 .rarw.tempa3
tempa1 .rarw.v11*a12+v12*a22+v13*a32+v14*a42
tempa2 .rarw.v21*a12+v22*a22+v23*a32
tempa3 .rarw.v31*a12+v32*a22
a42 .rarw.v41*a12
a12 .rarw.tempa1
a22 .rarw.tempa2
a32 .rarw.tempa3
tempa1 .rarw.v11*a13+v12*a23+v13*a33+v14*a43
tempa2 .rarw.v21*a13+v22*a23+v23*a33
tempa3 .rarw.v31*a13+v32*a23
a43 .rarw.v41*a13
a13 .rarw.tempa1
a23 .rarw.tempa2
a33 .rarw.tempa3
tempa1 .rarw.v11*a14+v12*a24+v13*a34+v14*a44
tempa2 .rarw.v21*a14+v22*a24+v23*a34
tempa3 .rarw.v31*a14+v32*a24
a44 .rarw.v41*a14
a14 .rarw.tempa1
a24 .rarw.tempa2
a34 .rarw.tempa3
End of Generating Equation.
3. The procedure for generating points is as follows.
The following variables are involved:
##EQU26##
This procedure generates the x-coordinates of the four corners of a patch
by using the incremental s-values and t-values dt and ds calculated by the
GCP 20.
The equation is:
##EQU27##
The output is two points for each increment of svar
The output is
##EQU28##
The procedure is as follows.
a. Wait for GCP 20 to finish calculating the incremental s-value and
t-value
ds, dt
b. Use ds, dt to generate the line segment of the curve.
tvar=0
tvar1=dt
svar=0
for tvar<1; Do
for svar<1; Do
tempa1=((a11*svar+a21)*svar+a31)*svar+a41
tempa2=((a12*svar+a22)*svar+a32)*svar+a42
tempa3=((a13*svar+a23)*svar+a33)*svar+a43
tempa4=((a14*svar+a24)*svar+a34)*svar+a44
x1st=((tempa1*tvar+tempa2)*tvar+tempa3)*tvar+temp4 output x1st
x2nd=((tempa1*tvar1+tempa2)*tvar1+tempa3)*tvar1+temp4 output x2nd
svar .rarw.svar+ds
end;
tvar .rarw.tvar+dt
tvar1 .rarw.tvar1+dt
end.
The procedure for generating y-coordinate data (GFPP 320) now follows. See
FIG. 8.
First, the input is as follows.
##EQU29##
The output is the four y-coordinates for four corners of the patch.
Constants involved are: m12,m22,m32,m42 (second column of the
transformation matrix)
##EQU30##
The bezier spline is given by the following matrix.
##EQU31##
Variables involved are:
##EQU32##
The procedure is as follows.
1. Transform the vertex, and multiply the coordinate by weight
b11 .rarw.m12*x11+m22*y11+m32*z11+m42
b11 .rarw.b11*w11
b12 .rarw.m12*x12+M22*y12+m32*z12+m42
b12 .rarw.b12*w12
b13 .rarw.m12*x13+m22*y13+m32*z13+m42
b13 .rarw.b13*w13
b14 .rarw.m12*x14+m22*y14+m32*z14+m42
b14 .rarw.b14*w14
b21 .rarw.m12*x21+m22*y21+m32*z21+m42
b21 .rarw.b21*w11
b22 .rarw.m12*x22+m22*y22+m32*z22+m42
b22 .rarw.b22*w12
b23 .rarw.m12*x23+m22*y23+m32*y23+m42
b23 .rarw.x23*w13
b24 .rarw.m12*x24+m22*y24+m32*z24+m42
b24 .rarw.x24*w14
b31 .rarw.m12*x31+m22*y31+m32*z31+m42
b31 .rarw.x31*w11
b32 .rarw.m12*x32+m32*y32+m32*z32+m42
b32 .rarw.x32*w12
b33 .rarw.m12*x33+m22*y33+m32*z33+m42
b33 .rarw.b33*w13
b34 .rarw.m12*x34+m22*y34+m32*z34+m42
b34 .rarw.b34*w14
b41 .rarw.m12*x41+m22*y41+m32*z41+m42
b41 .rarw.b41*w11
b42 .rarw.m12*x42+m22*y42+m32*z42+m42
b42 .rarw.b42*w12
b43 .rarw.m12*x43+m22*y43+m32*z43+m42
b43 .rarw.b43*w13
b44 .rarw.m12*x44+m22*y44+m32*z44+m42
b44 .rarw.b44*w14
2. Generate the coefficients for the polynomial equation.
Concatenate the three matrices V.WX.Vt. For Bezier Spline, V is equal to
Vt. Ten terms of V are non-zero for cubic Bezier.
a. Concatenate WX.Vt, where Vt=V, and v24=v33=v34=v42=v43=v44=0.
tempb1 .rarw.b11*v11+b12*v21+b13*v31+b14*v41
tempb2 .rarw.b11*v12+b12*v22+b13*v32
tempb3 .rarw.b11*v13+b12*v23
b14 .rarw.b11*v14
b11 .rarw.tempb1
b12 .rarw.tempb2
b13 .rarw.tempb3
tempb1 .rarw.b21*v11+b22*v21+b23*v31+b24*v41
tempb2 .rarw.b11*v12+b12*v22+b13*v32
tempb3 .rarw.b11*v13+b12*v23
b14 .rarw.b11*v14
b11 .rarw.tempb1
b12 .rarw.tempb2
b13 .rarw.tempb3
tempb1 .rarw.b21*v11+b22*v21+b23*v31+b24*v41
tempb2 .rarw.b21*v12+b22*v22+b23*v32
tempb3 .rarw.b21*v13+b22*v23
b24 .rarw.b21*v14
b21 .rarw.tempb1
b22 .rarw.tempb2
b23 .rarw.tempb3
tempb1 .rarw.b31*v11+b32*v21+b33*v31+b34*v41
tempb2 .rarw.b31*v12+b32*v22+b33*v32
tempb3 .rarw.b31*v13+b32*v23
b34 .rarw.b31*v14
b31 .rarw.tempb1
b32 .rarw.tempb2
b33 .rarw.tempb3
tempb1 .rarw.b41*v11+b42*v21+b43*v31+b44*v41
tempb2 .rarw.b41*v12+b42*v22+b43*v32
tempb4 .rarw.b41*v13+b42*v23
b44 .rarw.b41*v14
b41 .rarw.tempb1
b42 .rarw.tempb2
b43 .rarw.tempb3
b. Concatenate V.(WX.Vt).
Only ten terms of V, the matrix for cubic Bezier are non-zero.
v24=v33=v34=v42=v43=v44=0
tempb1 .rarw.v11*b11+v12*b21+v13*b31+v14*b41
tempb2 .rarw.v21*b11+v22*b21+v23*b31
tempb3 .rarw.v31*b11+v32*b21
b41 .rarw.v41*b11
b11 .rarw.tempb1
b21 .rarw.tempb2
b31 .rarw.tempb3
tempb1 .rarw.v11*b12+v12*b22+v13*b32+v14*b42
tempb2 .rarw.v21*b12+v22*b22+v23*b32
tempb3 .rarw.v31*b12+v32*b22
b42 .rarw.v41*b12
b12 .rarw.tempb1
b22 .rarw.tempb2
b32 .rarw.tempb3
tempb1 .rarw.v11*b13+v12*b23+v13*b33+v14*b43
tempb2 .rarw.v21*b13+v22*b23+v23*b33
tempb3 .rarw.v31*b13+v32*b23
b43 .rarw.v41*b13
b13 .rarw.tempb1
b23 .rarw.tempb2
b33 .rarw.tempb3
tempb1 .rarw.v11*b14+v12*b24+v13*b34+v14*b44
tempb2 .rarw.v21*b14+v22*b24+v23*b34
tempb3 .rarw.v31*b14+v32*b24
b44 .rarw.v41*b14
b14 .rarw.tempb1
b24 .rarw.tempb2
b34 .rarw.tempb3
End of Generating Equation.
3. The procedure for generating points is as follows:
Variables involved are:
##EQU33##
This generates the y-coordinates of the four corners of a patch by using
the incremental s-value and t-value, dt and ds calculated by the GCP 20.
The equation is
##EQU34##
The output is two points for each increment of svar. In code,
The output is
##EQU35##
The procedure is:
a. Wait for Graphics Control Processor to finish calculating the
incremental s-value and t-value.
ds, dt
b. Use ds, dt to generate the line segment of the curve.
tvar=0
tvar1=dt
svar=0
for tvar<1; Do
for svar<1; Do
tempb1=((b11*svar+b21)*svar+b31)*svar+b41
tempb2=((b12*svar+b22)*svar+b32)*svar+b42
tempb3=((b13*svar+b23)*svar+b33)*svar+b43
tempb4=((b14*svar+b24)*svar+b34)*svar+b44
y1st=((tempb1*tvar+tempb2)*tvar+tempb3)*tvar+temp4
outpu | | |
