Method and apparatus for rendering cubic curves

Details Method and apparatus for rendering cubic curves Method and apparatus for rendering cubic curves

1998-09-21

2001-09-25

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

C345S625000

Reexamination Certificate

active

06295072

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method and apparatus for rendering cubic curves, and more particularly, to a method and apparatus used to render cubic Bezier curves which are rapidly decomposed into a plurality of small segments piecewise by two independent operation units that process in parallel the input data of four control points of the cubic Bezier curve with the assistance of an arbitrator to display on a monitor or output to a printer.
BACKGROUND OF THE INVENTION
It is usually necessary to render cubic curves in computer aided design or in the field of computer graphics for displaying characters which are an outline font. The approximate approach of the Bezier curve for the cubic curve is one of the methods most widely used.
There are two primary methods for generating Bezier curves in a computer system. The first is the method of Adaptive Subdivision and the second is the method of Forward Difference.
As shown in “A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces” IEEE Transactions on Pattern Analysis and Machine Intelligence, Jan. 1980, the principle of Adaptive Subdivision for Bezier curve is as follows:
B
n
⁡
[
P
;
u
]
=
∑
i
=
0
n
⁢
P
i
⁡
(
n
i
)
⁢
u
i
⁡
(
1
-
u
)
n
-
i
,
we
⁢
 
⁢
can
⁢
 
⁢
infer
 
B
n
⁡
[
P
;
u
]
=
B
n
⁡
[
P
0
0
,
P
1
1
,
…
⁢
 
,
P
n
n
;
2
⁢
u
]
(
I
)
B
n
⁡
[
P
;
u
]
=
B
n
⁡
[
P
n
n
,
P
n
n
-
1
,
…
⁢
 
,
P
n
0
;
2
⁢
u
-
1
]
⁢

⁢
where
,
 
⁢
P
i
k
=
{
(
P
i
-
1
k
-
1
+
P
i
k
-
1
)
/
2
,
k
=
1
,
2
,
…
⁢
 
,
n
P
i
k
=
0
(
II
)
With reference to
FIG. 2
, there are four original control points P
00
, P
01
, P
02
, and P
03
, from which three corresponding middle points P
11
, P
12
, and P
13
are derived. Subsequently, two middle points P
22
and P
23
with respect to the above three middle points are obtained. Finally, the middle point P
33
of the points P
22
and P
23
is the point where the parameter u in the above equations is equal to 0.5. From the set of the control points P
00
, P
11
, P
22
, and P
33
and the set of the control points P
33
, P
23
, P
13
, and P
03
, the first and second half segments of the original curve can be generated, respectively. If the space of the parameter u ranges from 0.0 to 1.0, the first half segment is related to the parameter u from 0.0 to 0.5 and the second half segment is related to the parameter u from 0.5 to 1.0.
If the two new sets of control points continue to be divided, many new control points with equal space can be obtained. According to the absolute convergence of the Bezier curve, the new control points can be further approximate to the original curve as the division segment becomes much smaller.
The binary approximation algorithm is most well illustrated by a binary tree as shown in
FIG. 3. A
primary set of control points C which consists of four control points may generate two subsets of control points LC and RC, which may further generate LLC, RLC, LRC, and RRC as the final output in the binary tree. Thus, the above Adaptive Subdivision is very close to the method of Depth-First Transversal in the conventional binary tree. The data in the right subset of control points are stored in a stack memory and the left subset of control points are used as the source data for the next division when the present division process is finished. If the subset of control points to be divided meets the requirement of convergence, i.e., the four control points of the subset are in the same straight line, the subset is used to render a curve and stops being further divided and the right subset, previously pushed into the stack memory, is used as the source data for the next division process. The above-mentioned process is repeated until there is no available data.
The method of Adaptive Subdivision has four advantages. First, the input and output data are consistent in format, i.e., both the source and output data are control points. If there are multiple Bezier generators, the desired curve can be implemented in parallel by suitable series connection. Second, only a simple operation using an adder and a shifter is needed and can be implemented easily by a hardware circuit or a microprogram. Third, according to the convergence condition for determining which level of division is necessary, good output data can be derived from any curve with rigorous variation. Fourth, if the curve crosses over the visible window, the top-down division process can screen those unnecessary operations out of the visible window.
However, the method of Adaptive Subdivision has some disadvantages. First, it is necessary to have one set of rapid stack memory used to temporarily store the control points and to pull out the stored data. Second, every node in the binary tree has to be processed while using the binary tree to perform track operation. However, only the final node is needed and those operations for the middle points are unnecessary.
With regard to Forward Difference, the principle of difference is used. Define the forward difference as &Dgr;f(t)=f(t+&dgr;)−f(t), where &dgr;>0. When f
n
=f(t
n
) and t
n
=n·&dgr;, f
n+1
=f
n
+&Dgr;f
n
. In addition, &Dgr;f
n+1
=&Dgr;f
n
+&Dgr;
2
f
n
, &Dgr;
2
f
n+1
=&Dgr;
2
f
n
+&Dgr;
3
f
n
. Assuming a polynomial f(t)=a+bt+ct
2
+dt
3
,
 &Dgr;f(t)=3dt
2
&dgr;+t(3d&dgr;
2
+2c&dgr;)+d&dgr;
3
+c&dgr;
2
+b&dgr;.
&Dgr;
2
f(t)=&Dgr;(&Dgr;f(t))=6&dgr;d
2
t+6d&dgr;
3
+2c&dgr;
2
.
&Dgr;
3
f(t)=&Dgr;(&Dgr;
2
f(t))=6d&dgr;
3
.
We can calculate the initial condition: f
0
=a, &Dgr;f
0
=d&dgr;
3
+c&dgr;
2
+b&dgr;, &Dgr;
2
f
0
=6d&dgr;
3
+2c&dgr;
2
, &Dgr;
3
f
0
=6d&dgr;
3
. Subsequent data can be derived as follows:
f
i+1
=f
i
+&Dgr;f
i
, &Dgr;f
i+1
=&Dgr;f
i
+&Dgr;
2
f
i
, &Dgr;
2
f
i+1
=&Dgr;
2
f
i
+&Dgr;
3
f
0
.
The method of Forward Difference has two advantages. First, only one step is required to rapidly generate desired points for rendering a curve by using three adders. Second, not only Bezier curves, but also any type of cubic curves can be rendered.
The method of Forward Difference still has three disadvantages. First, it is necessary to transform the Bezier curve with the geometrical parameter into a cubic polynomial by a pre-process of floating point multiplication. Second, the value of difference has to be fixed and is very difficult to determine, especially where the curvature varies so significantly that good output data are hard to obtain. This is the most serious disadvantage. Third, although the present part of computation is out of the visible window, it is still necessary to perform the computation because the computation has to be accomplished point by point.
To solve the above disadvantages, a paper titled “Adaptive Forward Differencing for Rendering Curves and Surfaces” Computer Graphics, July 1987, provides a modified method of Adaptive Forward Difference (AFD). First, the Bezier curve which takes control points as the parameters is transformed into a polynomial based on AFD as follows:
f(t)=a
0
A
0
(t)+a
1
A
1
(t)+a
2
A
2
(t)+a
3
A
3
(t), where
A
k
(t)=((t−k+1)/k)*A
k−1
and A
0
(t)=1. That is, when t=0, the basis of AFD comprises: A
0
(t)=1, A
1
(t)=t, A
2
(t)=(1/2)(t)(t−1), and A
3
(t)=(1/6)(t)(t−1)(t−2). When t=t+1, the basis of AFD comprises: A
0
(t+1)=1=A
0
(t), A
1
(t+1)=A
0
(t)+A
1
(t), A
2
(t+1)=A
1
(t)+A
2
(t), and A
3
(t+1)=A
2
(t)+A3(t).
The new basis is brought into the polynomial to obtain:
f(t+1)=(a
0
+a
1
)A
0
(t)+(a
1
+a
2
)A
1
(t)+(a
2
+a
3
)A
2
(t)+a
3
A
3
(t),
wh

Affiliated with

Also associated with

Rating

Method and apparatus for rendering cubic curves does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for rendering cubic curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for rendering cubic curves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2471821