 |
Claims  |
|
|
We claim:
1. A computer system for approximating a Bezier curve with at least a line
segment, comprising:
(a) input means for inputting first, second, third, and fourth sequential
Bezier control points defining a cubic Bezier curve;
(b) means for selecting a test magnitude indicative of a desired degree of
accuracy with which the line segment should approximate said Bezier curve;
(c) means for determining a hybrid forward differencing function based on
said first, second, third, and fourth sequential inputted Bezier control
points;
(d) size means for selecting a step size, where said hybrid forward
differencing function defines a portion of said Bezier curve from a
present position of said hybrid forward differencing function to an end
point defined by said step size, said size means selecting an initial
value for said selected step size so that said hybrid forward differencing
function initially defines the entire Bezier curve from said first
inputted Bezier control point to said fourth inputted Bezier control
point;
(e) error means for determining a first error vector and a second error
vector from said hybrid forward differencing function based on said
selected step size;
(f) means for comparing the magnitude of said first error vector and said
second error vector with said test magnitude, and indicating if the
magnitude of either said first error vector or said second error vector
exceeds said test magnitude or if the magnitudes of both said first and
said second error vector are less than said test magnitude; and
(g) line means for generating a straight line segment between said present
position and said end point to approximate said Bezier curve in response
to an indicator signal.
2. The system of claim 1, further including:
(h) first alteration means for altering said hybrid forward differencing
function to decrease said step size taken by said hybrid forward
differencing function if said comparing means indicates that the magnitude
of either said first or said second error vector exceeds said test
magnitude, said first alteration means generating a first operated
function defining a subdivided portion of said Bezier curve extending from
said present position to a new end point defined by said decreased step
size, and providing said first operated function for processing by said
error means, and generating said indicator signal if the magnitudes of
said first and said second error vectors are both less than said test
magnitude.
3. The system of claim 2, further including:
(i) second alteration means for altering said hybrid forward differencing
function to increase said step size taken by said hybrid forward
differencing function, upon said line step generating a straight line
without the intervening application of said first alteration means, if the
magnitudes of said first and said second error vectors are both less than
said test magnitude, said second alteration means generating a second
operated function defining a portion of said Bezier curve larger than said
subdivided portion and extending from said present position to an
increased end point defined by said increased step size; and
(j) matching means for determining if an increased straight line segment
extending between said present position and said increased end point would
be approximated by recursive subdivision, generating said indicator signal
if the magnitude of either said first or said second error vector
determined from said second operated function exceeds said test magnitude
or if said matching means determines that said increased straight line
segment would not be derived by said recursive subdivision, and providing
said line means with said present position and said increased end point
and generating said indicator signal to generate said increased straight
line segment if the magnitudes of said first and said second error vectors
determined from said second operated function are both less than said test
magnitude and said matching means determines that said increased straight
line segment would be derived by said recursive subdivision.
4. The system according to claim 1 wherein said means for comparing the
magnitudes of said first and second error vectors with said test magnitude
includes:
means for determining and selecting the vector components with the largest
magnitude for said first and said second error vectors; and
means for comparing the magnitudes of said selected vector component of
said first and second error vectors with said test magnitude, and
indicating if the magnitude of said selected vector component of either
said first or said second error vector exceeds said test magnitude or if
the magnitudes of both of said selected vector components are less than
said test magnitude.
5. A computer system for approximating a Bezier curve with at least a line
segment, comprising:
(a) input means for inputting first, second, third, and fourth sequential
Bezier control points defining a cubic Bezier curve;
(b) means for selecting a test magnitude indicative of a desired degree of
accuracy with which the line segment should approximate said Bezier curve;
(c) means for determining a hybrid forward differencing function based on
said first, second, third, and fourth sequential inputted Bezier control
points, said function having four terms, e.sub.0 through e.sub.3, and
having the following general form:
f(t)=e.sub.0 E.sub.0 (t)+e.sub.1 E.sub.1 (t)+e.sub.2 E.sub.2 (t)+e.sub.3
E.sub.3 (t);
(d) size means for selecting a step size, where said hybrid forward
differencing function defines a portion of said Bezier curve from a
present position of said hybrid forward differencing function to an end
point defined by said step size, said size means selecting an initial
value for said selected step size so that said hybrid forward differencing
function initially defines the entire Bezier curve from said first
inputted Bezier control point to said fourth inputted Bezier control
point;
(e) error means for determining a first error vector and a second error
vector from said hybrid forward differencing function based on said
selected step size, said first and second error vectors being e.sub.2 and
e.sub.3, respectively;
(f) means for comparing the magnitude of said first error vector and said
second error vector with said test magnitude, and indicating if the
magnitude of either said first error vector or said second error vector
exceeds said test magnitude or if the magnitudes of both said first and
said second error vector are less than said test magnitude; and
(g) line means for generating a straight line segment between said present
position and said end point to approximate said Bezier curve in response
to an indicator signal.
6. The system of claim 5, further including:
(h) first alteration means for altering said hybrid forward differencing
function to decrease said step size taken by said hybrid forward
differencing function if said comparing means indicates that the magnitude
of either said first or said second error vector exceeds said test
magnitude, said first alteration means generating a first operated
function defining a subdivided portion of said Bezier curve extending from
said present position to a new end point defined by said decreased step
size, and providing said first operated function for processing by said
error meats, and generating said indicator signal if the magnitudes of
said first and said second error vectors are both less than said test
magnitude.
7. The system of claim 6, further including:
(i) second alteration means for altering said hybrid forward differencing
function to increase said step size taken by said hybrid forward
differencing function, upon said forward step means altering said hybrid
forward differencing function without the intervening application of said
first alteration means, if the magnitudes of said first and said second
error vectors are both less than said test magnitude, said second
alteration means generating a second operated function defining a portion
of said Bezier curve larger than said subdivided portion and extending
from said present position to an increased end point defined by said
increased step size; and
(j) matching means for determining if an increased straight line segment
extending between said present position and said increased end point would
be approximated by recursive subdivision, generating said indicator signal
if the magnitude of either said first or said second error vector
determined from said second operated function exceeds said test magnitude
or if said matching means determines that said increased straight line
segment would not be derived by said recursive subdivision, and providing
said line means with said present position and said increased end point
and generating said indicator signal to generate said increased straight
line segment if the magnitudes of said first and said second error vectors
determined from said second operated function are both less than said test
magnitude and said matching means determines that said increased straight
line segment would be derived by said recursive subdivision.
8. The system according to claim 5 wherein said means for comparing the
magnitudes of said first and second error vectors with said test magnitude
includes:
means for determining and selecting the vector components with the largest
magnitude for said first and said second error vectors; and
means for comparing the magnitudes of said selected vector component of
said first and second error vectors with said test magnitude, and
indicating if the magnitude of said selected vector component of either
said first or said second error vector exceeds said test magnitude or if
the magnitudes of both of said selected vector components are less than
said test magnitude.
9. A computer system for approximating a Bezier curve with at least a line
segment, comprised of:
(a) input means for inputting a variable number, N, of sequential Bezier
control points, P.sub.1 . . . P.sub.N, defining a Bezier curve of degree
N-1;
(b) means for selecting a test magnitude indicative of a desired degree of
accuracy with which the line segment should approximate said Bezier curve;
(c) means for determining a hybrid forward differencing function based on
said N sequential inputted Bezier control points;
(d) size means for selecting a step size, where said hybrid forward
differencing function defines a portion of said Bezier curve from a
present position of said hybrid forward differencing function to an end
point defined by said step size, said size means selecting an initial
value for said selected step size so that said hybrid forward differencing
function initially defines the entire Bezier curve from said Bezier
control point P.sub.1 to said Bezier control point P.sub.N ;
(e) error means for determining a set of N-2 error vectors, E.sub.1 . . .
E.sub.N-2, from said hybrid forward differencing function based on said
selected step size;
(f) means for comparing the magnitudes of each of said N-2 error vectors
with said test magnitude, and indicating if the magnitude of any of said
N-2 error vectors exceeds said test magnitude or if the magnitude of each
of said N-2 error vectors is less than said test magnitude; and
(g) line means for generating a straight line segment between said present
position and said end point to approximate said Bezier curve in response
to an indicator signal.
10. The system of claim 9, further including:
(h) first alteration means for altering said hybrid forward differencing
function to decrease said step size taken by said hybrid forward
differencing function if said comparing means indicates that the magnitude
of any of said N-2 error vectors exceeds said test magnitude, said first
alteration means generating a first operated function defining a
subdivided portion of said Bezier curve extending from said present
position to a new end point defined by said decreased step size, and
providing said first operated function for processing by said error means,
and generating said indicator signal if the magnitude of each of said N-2
error vectors is less than said test magnitude.
11. The system of claim 10, further including:
(i) second alteration means for altering said hybrid forward differencing
function to increase said step size taken by said hybrid forward
differencing function, upon said forward step means altering said hybrid
forward differencing function without the intervening application of said
first alteration means, if the magnitudes of said N-2 error vectors are
each less than said test magnitude, said second alteration means
generating a second operated function defining a portion of said Bezier
curve larger than said subdivided portion and extending from said present
position to an increased end point defined by said increased step size;
and
(j) matching means for determining if an increased straight line segment
extending between said present position and said increased end point would
be approximated by recursive subdivision, generating said indicator signal
if any of said N-2 error vectors determined from said second operated
function exceeds said test magnitude or if said matching means determines
that said increased straight line segment would not be derived by said
recursive subdivision, and providing said line means with said present
position and said increased end point and generating said indicator signal
to generate said increased straight line segment if the magnitudes of each
of said N-2 error vectors determined from said second operated function
are less than said test magnitude and said matching means determines that
said increased straight line segment would be derived by said recursive
subdivision.
12. The system according to claim 9 wherein said means for comparing the
magnitudes of said N-2 error vectors with said test magnitude includes:
means for resolving the vector components of said N-2 error vectors; and
means for comparing the magnitudes of said resolved components of said N-2
error vectors with said test magnitude, and indicating if the magnitude of
any of said resolved vector components of said N-2 error vectors exceeds
said test magnitude or if the magnitude of each of said resolved vector
components of said N-2 error vectors is less than said test magnitude.
13. A computer system for approximating a Bezier curve with at least a line
segment, comprised of:
(a) input means for inputting a variable number, N, of sequential Bezier
control points, P.sub.1 . . . P.sub.N, defining a Bezier curve of degree
N-1;
(b) means for selecting a test magnitude indicative of a desired degree of
accuracy with which the line segment should approximate said Bezier curve;
(c) means for determining a hybrid forward differencing function based on
said N sequential inputted Bezier control points;
(d) size means for selecting a step size, where said hybrid forward
differencing function defines a portion of said Bezier curve from a
present position of said hybrid forward differencing function to an end
point defined by said step size, said size means selecting an initial
value for said selected step size so that said hybrid forward differencing
function initially defines the entire Bezier curve from said Bezier
control point P.sub.1 to said Bezier control point P.sub.N ;
(e) error means for determining a set of N-2 error functions based on a set
of N-2 error vectors, E.sub.1 . . . E.sub.N-2, from said hybrid forward
differencing function based on said selected step size;
(f) means for comparing the magnitudes of each of said N-2 error functions
with said test magnitude, and indicating if the magnitude of any of said
N-2 error functions exceeds said test magnitude or if the magnitude of
each of said N-2 error functions is less than said test magnitude; and
(g) line means for generating a straight line segment between said present
position and said end point to approximate said Bezier curve in response
to an indicator signal.
14. A computer system for approximating a Bezier curve with at least a line
segment, comprised of:
(a) input means for inputting a variable number, N, of sequential Bezier
control points, P.sub.1 . . . P.sub.N, defining a Bezier curve of degree
N-1;
(b) means for selecting a test magnitude indicative of a desired degree of
accuracy with which the line segment should approximate said Bezier curve:
(c) means for determining a hybrid forward differencing function based on
said N sequential inputted Bezier control points, said function having N
terms, e.sub.0 through e.sub.N-1, and having the following general form:
f(t)=e.sub.0 E.sub.0 (t)+e.sub.1 E.sub.1 (t)+e.sub.2 E.sub.2 (t)+. . .
e.sub.N-1 E.sub.N-1 (t);
(d) size means for selecting a step size, where said hybrid forward
differencing function defines a portion of said Bezier curve from a
present position of said hybrid forward differencing function to an end
point defined by said step size, said size means selecting an initial
value for said selected step size so that said hybrid forward differencing
function initially defines the entire Bezier curve from said Bezier
control point P.sub.1 to said Bezier control point P.sub.N ;
(e) error means for determining a set of N-2 error vectors, E.sub.l . . .
E.sub.N-2, from said hybrid forward differencing function based on based
on said selected step size, said N-2 error vectors being e.sub.2 through
e.sub.N-1, respectively;
(f) means for comparing the magnitudes of each of said N-2 error vectors
with said test magnitude, and indicating if the magnitude of any of said
N-2 error vectors exceeds said test magnitude or if the magnitude of each
of said N-2 error vectors is less than said test magnitude; and
(g) line means for generating a straight line segment between said present
position and said end point to approximate said Bezier curve in response
to an indicator signal.
15. The system of claim 14, further including:
(h) first alteration means for altering said hybrid forward differencing
function to decrease said step size taken by said hybrid forward
differencing function if said comparing means indicates that the magnitude
of any of said N-2 error vectors exceeds said test magnitude, said first
alteration means generating a first operated function defining a
subdivided portion of said Bezier curve extending from said present
position to a new end point defined by said decreased step size, and
providing said first operated function for processing by element e, and
generating said indicator signal if the magnitude of each of said N-2
error vectors is less than said test magnitude.
16. The system of claim 15, further including:
(i) second alteration means for altering said hybrid forward differencing
function to increase said step size taken by said hybrid forward
differencing function, upon said forward step means altering said hybrid
forward differencing function without the intervening application of said
first alteration means, if the magnitudes of said N-2 error vectors are
each less than said test magnitude, said second alteration means
generating a second operated function defining a portion of said Bezier
curve larger than said subdivided portion and extending from said present
position to an increased end point defined by said increased step size;
and
(j) matching means for determining if an increased straight line segment
extending between said present position and said increased end point would
be approximated by recursive subdivision, generating said indicator signal
if any of said N-2 error vectors determined from said second operated
function exceeds said test magnitude or if said matching means determines
that said increased straight line segment would not be derived by said
recursive subdivision, and providing said line means with said present
position and said increased end point and generating said indicator signal
to generate said increased straight line segment if the magnitudes of each
of said N-2 error vectors determined from said second operated function
are less than said test magnitude and said matching means determines that
said increased straight line segment would be derived by said recursive
subdivision.
17. The system according to claim 14 wherein said means for comparing the
magnitudes of said N-2 error vectors with said test magnitude includes:
means for resolving the vector components of said N-2 error vectors; and
means for comparing the magnitude of at least the largest of said resolved
components of said N-2 error vectors with said test magnitude, and
indicating if the magnitude of any of said resolved vector components of
said N-2 error vectors exceeds said test magnitude or if the magnitude of
each of said resolved vector components of said N-2 error vectors is less
than said test magnitude.
18. A computer system for generating the same straight line segments that
recursive subdivision generate to approximate a Bezier curve using a test
magnitude indicative of a desired degree to accuracy with which the line
segments should approximate the curve, the system comprised of:
(a) input means for inputting a variable number, N, of sequential Bezier
control points, P.sub.1 . . . P.sub.N, defining a Bezier curve of degree
N-1, with Bezier control points P.sub.1 and P.sub.N being end points that
coincide with the curve;
(b) means for determining a hybrid forward differencing function based on
said N sequential inputted Bezier control points;
(c) error means for selecting a step size, where said hybrid forward
differencing function defines a portion of said Bezier curve from a
present position of said hybrid forward differencing function to an end
point defined by said step size, said size means selecting an initial
value for said selected step size so that said hybrid forward differencing
function initially defines the entire Bezier curve from said Bezier
control point P.sub.1 to said Bezier control point P.sub.N ;
(d) error means for determining a set of N-2 error vectors, E.sub.1 . . .
E.sub.N-2, from said hybrid forward differencing function, based on said
selected step size:
(e) first alteration means for altering said hybrid forward differencing
function to decrease said step size taken by said hybrid forward
differencing function if the magnitude of any of said N-2 error vectors
exceeds the test magnitude, said first alteration means generating a first
operated function defining a subdivided portion of said Bezier curve
extending from said present position to a new end point defined by said
decreased step size, and providing said first operated function for
processing by said error means;
(f) line means for generating a straight line segment between said present
position and said end point to approximate said Bezier curve in response
to an indicator signal;
(g) forward step means for altering said hybrid forward differencing
function upon said line means generating a straight line, said forward
step means generating a forward operated function defining a subdivided
portion of said Bezier curve by moving said present position of said
hybrid forward differencing function to said end point defined by said
step size without altering said step size and providing said forward
operated function for processing by element d;
(h) second alteration means for altering said hybrid forward differencing
function to increase said step size taken by said hybrid forward
differencing function, upon said forward step means altering said hybrid
forward differencing function without the intervening application of said
first alteration means, if the magnitudes of said N-2 error vectors are
each less than said test magnitude, said second alteration means
generating a second operated function defining a portion of said Bezier
curve larger than said subdivided portion and extending from said present
position to an increased end point defined by said increased step size;
(i) matching means for determining if an increased straight line segment
extending between said present position and said increased end point would
be approximated by the recursive subdivision, and providing said second
operated function for processing by element d if the magnitudes of each of
said N-2 error vectors determined from said second operated function are
each less than the test magnitude and if said increased straight line
segment would be derived by the recursive subdivision, and generating said
indicator signal if any of said N-2 error vectors determined from said
second operated function exceeds the test magnitude or if said matching
means determines that said increased straight line segment extending
between said present position and said increased end point would not be
derived by the recursive subdivision; and
(j) comparing means for comparing the magnitudes of each of said N-2 error
vectors with the test magnitude, and generating said indicator signal if
the magnitude of each of said N-2 error vectors is less than the test
magnitude and said first alteration means was the most recently applied of
said first and second alteration means.
19. The system according to claim 18 wherein said comparing means includes:
means for resolving the vector components of said N-2 error vectors; and
means for comparing the magnitude of at least the largest of said resolved
components of said N-2 error vectors with said test magnitude, and
generating said indicator signal if the magnitude of each of said resolved
vector components of said N-2 error vectors is less than said test
magnitudes and said first alteration was the most recently applied of said
first and second alteration means.
20. A computer system for generating a straight line segment to approximate
a Bezier curve, the system comprised of:
a central processor:
a memory, connected to said central processor via a bus carrying electrical
data and control signals;
an input unit by which a first, second, third, and fourth sequential Bezier
control points defining a cubic Bezier curve may be entered into said
memory via said bus;
a test magnitude indicative of a desired degree of accuracy with which the
line segment should approximate said Bezier curve:
a hybrid forward differencing generator connected to said bus generating a
hybrid forward differencing function based on said first, second, third,
and fourth sequential inputted Bezier control points;
size means for selecting a step size where said hybrid forward differencing
function defines a portion of said Bezier curve from a present position of
said hybrid forward differencing function to an end point defined by said
step size, said size means selecting an initial value for said selected
step size, said step size having an initial step value so that said hybrid
forward differencing function initially defines the entire Bezier curve
from said first Bezier control point to said fourth Bezier control point;
a set of operators connected to said bus operating on said hybrid forward
differencing function to decrease said step size so that said hybrid
forward differencing function represents a smaller portion of said Bezier
curve and doubling said step value indicating that it takes twice as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, to increase said step size so that said hybrid
forward differencing function represents a larger portion of said Bezier
curve and halving said step value indicating that it takes half as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, or take a forward step at the present step
size so that the current position of said hybrid forward differencing
function is incremented by said present step size and decrementing said
step value indicating that said hybrid forward differencing function has
taken one step, at the present step size toward said end point of said
Bezier curve;
an error vector calculator connected to said bus determining a first and
second error vectors from said hybrid forward differencing function;
a comparator comparing the value of said test magnitude with the value of
the magnitude of said first and said second error vectors and indicating
if the magnitude of either said first or said second error vector exceeds
said test magnitude or if the magnitudes of both said first and said
second error vectors are less than said test magnitude;
a line segment generator receiving said present position and said end point
and, upon receiving an indicator signal, generating a plurality of data
values corresponding to pixels to create a line segment drawn between said
present position and said end point;
a display driver receiving said plurality of data points and converting
said data points into a display format; and
a display receiving said converted data points and generating an image
corresponding to said line segment drawn between said present position and
said end point to approximate at least a portion of said Bezier curve.
21. The system of claim 20 wherein said set of operators applies a first of
said set of operators to said hybrid forward differencing function to
decrease said step size creating an operated hybrid forward differencing
function that represents a smaller portion of said Bezier curve and
providing said operated hybrid forward differencing function to said error
vector calculator if said comparator indicates that the magnitude of
either said first or said second error vectors exceeds said test magnitude
and generating said indicator signal if the magnitudes of said first and
said second error vectors are both less than said test magnitude.
22. The system of claim 21 wherein said set of operators, upon said line
segment generator generating a straight line without an intervening
application of said first operator, applies a second of said set of
operators to said hybrid forward differencing function to increase said
step size creating a second operated hybrid forward differencing function
that represents a larger portion of said Bezier curve extending between
said present position and an increased end point defined by said step
size, generating said indicator signal if the magnitude of either said
first or said second error vectors determined from said second operated
function exceeds said test magnitude or if said step value is odd, and
providing said line segment generator with said present position and said
increased end point and generating said indicator signal to generate an
increased straight line segment extending between said present position
and said increased end point if the magnitudes of said first and said
second error vectors determined from said second operated function are
both less than said test magnitude and said step value is even.
23. The system according to claim 20 wherein said comparator compares the
magnitude of at least the largest of the resolved vector components of
said first and said second error vectors with said test magnitude and
indicates if the magnitude of any of the resolved vector components of
said first and said second error vectors exceeds said test magnitude or if
the magnitudes of the resolved vector components of both said first and
said second error vectors are less than said test magnitude.
24. A computer system for generating a straight line segment to approximate
a Bezier curve, the system comprised of:
a central processor:
a memory, connected to said central processor via a bus carrying electrical
data and control signals;
an input unit by which a first, second, third, and fourth sequential Bezier
control points defining a cubic Bezier curve may be entered into said
memory via said bus;
a test magnitude indicative of a desired degree of accuracy with which the
line segment should approximate said Bezier curve;
a hybrid forward differencing generator connected to said bus generating a
hybrid forward differencing function based on said first, second, third,
and fourth sequential inputted Bezier control points, said function having
four terms, e.sub.0 through e.sub.3, and having the following general
form:
f(t)=e.sub.0 E.sub.0 (t)+e.sub.1 E.sub.1 (t)+e.sub.2 E.sub.2 (t)+e.sub.3
E.sub.3 (t);
size means for selecting a step size where said hybrid forward differencing
function defines a portion of said Bezier curve from a present position of
said hybrid forward differencing function to an end point defined by said
step size, said size means selecting an initial value for said selected
step size, so that said hybrid forward differencing function initially
defines the entire Bezier curve from said first Bezier control point to
said fourth Bezier control point;
a set of operators connected to said bus operating on said hybrid forward
differencing function to decrease said step size so that said hybrid
forward differencing function represents a smaller portion of said Bezier
curve and doubling said step value indicating that it takes twice as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, to increase said step size so that said hybrid
forward differencing function represents a larger portion of said Bezier
curve and halving said step value indicating that it takes half as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, or take a forward step at the present step
size so that the current position of said hybrid forward differencing
function is incremented by said present step size and decrementing said
step value indicating that said hybrid forward differencing function has
taken one step, at the present step size toward said end point of said
Bezier curve:
an error vector calculator connected to said bus determining a first error
vector and a second error vector from said hybrid forward differencing
function based on said selected step size, said first and second error
vectors being e.sub.2 and e.sub.3, respectively;
a comparator comparing the value of said test magnitude with the value of
the magnitude of said first and said second error vectors and indicating
if the magnitude of either said first or said second error vector exceeds
said test magnitude or if the magnitudes of both said first and said
second error vectors are less than said test magnitude;
a line segment generator receiving said present position and said end point
and, upon receiving an indicator signal, generating a plurality of data
values corresponding to pixels to create a line segment drawn between said
present position and said end point;
a display driver receiving said plurality of data points and converting
said data points into a display format; and
a display receiving said converted data points and generating an image
corresponding to said line segment drawn between said present position and
said end point to approximate at least a portion of said Bezier curve.
25. The system of claim 24 wherein said set of operators applies a first of
said set of operators to said hybrid forward differencing function to
decrease said step size creating an operated hybrid forward differencing
function that represents a smaller portion of said Bezier curve and
providing said operated hybrid forward differencing function to said error
vector calculator if said comparator indicates that the magnitude of
either said first or said second error vectors exceeds said test magnitude
and generating said indicator signal if the magnitudes of said first and
said second error vectors are both less than said test magnitude.
26. The system of claim 25 wherein said set of operators, upon said line
segment generator generating a straight line without an intervening
application of said first operator, applies a second of said set of
operators to said hybrid forward differencing function to increase said
step size creating a second operated hybrid forward differencing function
that represents a larger portion of said Bezier curve extending between
said present position and an increased end point defined by said step
size, generating said indicator signal if the magnitude of either said
first or said second error vectors determined from said second operated
function exceeds said test magnitude or if said step value is odd, and
providing said line segment generator with said present position and said
increased end point and generating said indicator signal to generate an
increased straight line segment extending between said present position
and said increased end point if the magnitudes of said first and said
second error vectors determined from said second operated function are
both less than said test magnitude and said step value is even.
27. The system according to claim 24 wherein said comparator compares the
magnitude of at least the largest of the resolved vector components of
said first and said second error vectors with said test magnitude and
indicates if the magnitude of any of the resolved vector components of
said first and said second error vectors exceeds said test magnitude or if
the magnitudes of the resolved vector components of both said first and
said second error vectors are less than said test magnitude.
28. A computer system for generating a straight line segment to approximate
a Bezier curve, the system comprised of:
a central processor:
a memory, connected to said central processor via a bus carrying electrical
data and control signals;
an input unit by which a variable number, N, of sequential Bezier control
points, P.sub.1 . . . P.sub.N, defining a Bezier curve of degree N-1 may
be entered into said memory via said bus;
a test magnitude indicative of a desired degree of accuracy with which the
line segment should approximate said Bezier curve;
a hybrid forward differencing generator connected to said bus generating a
hybrid forward differencing function based on said N sequential inputted
Bezier control points;
size means for selecting a step size where said hybrid forward differencing
function defines a portion of said Bezier curve from a present position of
said hybrid forward differencing function to an end point defined by said
step size, said size means selecting an initial value for said selected
step size so that said hybrid forward differencing function initially
defines the entire Bezier curve from said Bezier control point P.sub.1 to
said Bezier control point P.sub.N ;
a set of operators connected to said bus operating on said hybrid forward
differencing function to decrease said step size so that said hybrid
forward differencing function represents a smaller portion of said Bezier
curve and doubling said step value indicating that it takes twice as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, to increase said step size so that said hybrid
forward differencing function represents a larger portion of said Bezier
curve and halving said step value indicating that it takes half as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, or take a forward step at the present step
size so that the current position of said hybrid forward differencing
function is incremented by said present step size and decrementing said
step value indicating that said hybrid forward differencing function has
taken one step, at the present step size toward said end point of said
Bezier curve;
an error vector calculator connected to said bus and determining a set of
N-2 error vectors from said hybrid forward differencing function;
a comparator comparing the value of said test magnitude with the value of
the magnitude of each of said N-2 error vectors and indicating if the
magnitude of any of said N-2 error vectors exceeds said test magnitude or
if the magnitudes of said N-2 error vectors are each less than said test
magnitude;
a line segment generator receiving said present position and said end point
and, upon receiving an indicator signal, generating a plurality of data
values corresponding to pixels to create a line segment drawn between said
present position and said end point;
a display driver receiving said plurality of data points and converting
said data points into a display format; and
a display receiving said converted data points mad generating an image
corresponding to said line segment drawn between said present position and
said end point to approximate at least a portion of said Bezier curve.
29. The system of claim 28 wherein said set of operators applies a first of
said set of operators to said hybrid forward differencing function to
decrease said step size creating an operated hybrid forward differencing
function that represents a smaller portion of said Bezier curve and
providing said operated hybrid forward differencing function to said error
vector calculator if said comparator indicates that the magnitude of any
of said N-2 error vectors exceeds said test magnitude and generating said
indicator signal if the magnitude of each of said N-2 error vectors is
less than said test magnitude.
30. The system of claim 29 wherein said set of operators, upon said line
segment generator generating a straight line without an intervening
application of said first operator, applies a second of said set of
operators to said hybrid forward differencing function to increase said
step size creating a second operated hybrid forward differencing function
that represents a larger portion of said Bezier curve extending between
said present position and an increased end point defined by said step
size, generating said indicator signal if the magnitude of any of said N-2
error vectors determined from said second operated function exceeds said
test magnitude or if said step value is odd, and providing said line
segment generator with said present position and said increased end point
and generating said indicator signal to generate an increased straight
line segment extending between said present position and said increased
end point if the magnitudes of each of said N-2 error vectors determined
from said operated function are less than said test magnitude and said
step value is even.
31. The system according to claim 28 wherein said comparator compares the
magnitude of at least the largest of the resolved vector components of
said N-2 error vectors with said test magnitude and indicates if the
magnitude of any of the resolved vector components of said N-2 error
vectors exceeds said test magnitude or if the magnitudes of the resolved
vector components of said N-2 error vectors are each less than said test
magnitude.
32. A computer system for generating a straight line segment to approximate
a Bezier curve, the system comprised of:
a central processor;
a memory, connected to said central processor via a bus carrying electrical
data and control signals;
an input unit by which a variable number, N, of sequential Bezier control
points. P.sub.1 . . . P.sub.N, defining a Bezier curve of degree N-1 may
be entered into said memory via said bus;
a test magnitude indicative of a desired degree of accuracy with which the
line segment should approximate said Bezier curve:
a hybrid forward differencing generator connected to said bus generating a
hybrid forward differencing function based on said based on said N
sequential inputted Bezier control points, said function having N terms,
e.sub.0 through e.sub.N-1, and having the following general form:
f(t)=e.sub.0 E.sub.0 (t)+e.sub.1 E.sub.1 (t)+e.sub.2 E.sub.2 (t)+. . .
e.sub.N-1 E.sub.N-1 (t);
size means for selecting a step size where said hybrid forward differencing
function defines a portion of said Bezier curve from a present position of
said hybrid forward differencing function to an end point defined by said
step size, so that said hybrid forward differencing function initially
defines the entire Bezier curve from said Bezier control point P.sub.1 to
said Bezier control point P.sub.N ;
a set of operators connected to said bus operating on said hybrid forward
differencing function to decrease said step size so that said hybrid
forward differencing function represents a smaller portion of said Bezier
curve and doubling said step value indicating that it takes twice as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, to increase said step size so that said hybrid
forward differencing function represents a larger portion of said Bezier
curve and halving said step value indicating that it takes half as many
steps for said hybrid forward differencing function to reach said end
point of said Bezier curve, or take a forward step at the present step
size so that the current position of said hybrid forward differencing
function is incremented by said present step size and decrementing said
step value indicating that said hybrid forward differencing function has
taken one step, at the present step size toward said end point of said
Bezier curve;
an error vector calculator connected to said bus and determining a set of
N-2 error vectors from said hybrid forward differencing function based on
said selected step size, said N-2 error vectors being e.sub.2 through
e.sub.N-1, respectively from said hybrid forward differencing function;
a comparator comparing the value of said test magnitude with the value of
the magnitude of each of said N-2 error vectors and indicating if the
magnitude of any of said N-2 error vectors exceeds said test magnitude or
if the magnitudes of said N-2 error vectors are each less than said test
magnitude;
a line segment generator receiving said present po | | |
