WO1992009043A1

WO1992009043A1 - Method and apparatus for rendering a trimmed patch and an equipotential surface

Info

Publication number: WO1992009043A1
Application number: PCT/KR1991/000029
Authority: WO
Inventors: Jae Yong Koh
Original assignee: Individual
Current assignee: Individual
Priority date: 1990-11-16
Filing date: 1991-11-16
Publication date: 1992-05-29
Anticipated expiration: 1993-05-16
Also published as: KR920010418A; KR930004215B1

Abstract

The present invention is a method and apparatus for fast rendering of trimmed patches. It is intended to eliminate high overhead incurred when obtaining the parametric image of the trimming curves defined in the object or screen space, finding minima/maxima, and performing multiple initializations of difference vector. The present invention is designed to perform forward differencing in multiple directions parallel to any of the coordinate axis of the vector space in which the patch is defined so that it can render the trimmed patches without high overhead. It is also shown that the invention is further applicable to numerical calculations and scientific visualizations, for example, tracing equipotential surfaces.

Description

TITLE

Method and Apparatus for Rendering a Trimmed Patch and an Equipotential Surface.

TECHNICAL FIELD

The present invention relates to computer graphics, more particularly, to a method and apparatus for rendering a trimmed patch and an equipotential surface on computer graphics display.

BACKGROUND ART

Bicubic patch is a mapping P defined by P:[0,1]×[0,1]→R³. The mapping distorts unit square [0,1]×[0,1] in the parameter space (s,t) to produce a curved surface in the object space R³. It is then projected to the screen space by viewing transformation V as shown in Fig. 1. Rendering bicubic patches is the process of evaluating position vector V(P(s,t)) and intensity for a number of sampling points

(s,t) in the unit square. Note that it is often desirable to produce only a portion of a bicubic patch. For instance, trimmed-NURBS(non-uniform rational B-splines) have gained popularity for mechanical CAD applications. High-end workstations with interleaved video memory or pixel cache may produce only a portion of a patch inside the processing 'footprint' every moment. In these cases, each trimmed patch or a portion of a patch is produced by sampling the points in the interior region defined by a closed loop of trimming curves. A good algorithm must render not only the full patch, but also the trimmed patch fast.

Forward differencing is an efficient way to render full patches. It exploits polynomial's n-th order forward difference for an incremental step Δs along the parameter s to calculate each coordinate value of the patch if the polynomial P(s) is of degree n. For the cubic polynomial, the initial difference vector ΔՓ₀ is obtained by

where M is the geometric basis matrix and G is the geometric vector. The initial difference vector is used to repeatedly obtain the differences of next step using n-th order digital differential analyzer (DDA) calculations :

Δ0P_i+1 = Δ0P_i + Δ1P_i

Δ1P_{i +1} = Δ1P_i + Δ2P_i

ΔnP_i+1 = ΔnP_i

where the left side is the next step difference value. The DDA uses only n additions per step. Further, the additions can be done all at once as in Algorithm 1 shown below. The hardware implementation(See patent No. US4,760,548) is also shown in Fig. 2 where each accumulator Acci corresponds to fd[i] in Algorithm 1.

1 Initialize vector fd[0..n]; { fd[i]← ΔiP₀ }

2 while rendering a curve P(s) for successive increments

of variable s by Δs do

3 begin

4 output(fd[0]);

for i=0 to n par_do { par_do stands

for 'do in parallel'}

6 fd[i] := fd[i] 4- fd[i +1]; {augment s by Δs}

7 end.

Algorithm 1. Forward differencing of degree n polynomial P(s). Rendering a patch requires evaluations of 2-variable polynomialP(s,t) on m n sampling points (s,t)e[0,1]×[0,1]. Forward differencing regards p(s,t)= ∑∑aij i =0j=0 sⁱ t^j as 1-variable polynomial P(s)=ΣAi(t)sⁱ where A_i(t)=∑aij ^j, i.e., the

1-variable polynomial whose coefficients are again 1-variable polynomials. Rendering P(s,t) proceeds by first applying Algorithm 1 to 1-variable polynomial P(s,0)=ΣAi(0)sⁱ, then to P(s,Δt), P(s,2Δt),···, P(s,1), i.e., in a row-major fashion as shown in Fig. 3. What deserves attention here is the calculation of initial difference vector for each P(s,qΔt) where q=0,1,2,··· . Let us now denote initial difference vector for P(s,qΔt) as ΔՓ₀(qΔt) and each of its i-th component as Δ ⁱP₀(qΔt). Rather than directly calculating each initial vector as in Algorithm 1 which consumes a large amount of time, forward differencing over t is again applied to the calculation of each Δ ⁱP₀(qΔt), i=0,···,m.

Algorithm 2 shown below summarizes these steps. The poly_vector[0..m,0..n] in algorithm 2 is the difference vector for calculating successive ΔՓ₀(0), ΔՓ₀(Δt),··· ,ΔՓ₀(1). Each of the i-th column poly_vector[0..m,i] keeps difference vector for ΔⁱP₀(qΔt) (q=0, 1,2···.). Thus, each poly_vector[0,i] successively latches ΔⁱP₀(0), ΔⁱP₀(Δt),···, ΔⁱP₀(1) for every execution of lines 12-14 once initialized by line 1. These initial vector components are handed down to fd[i] by lines 4-5. Lines 6-11 are DDA calculation for rendering P(s,qΔt). The hardware implementation of the algorithm is shown in Fig. 4. Again Acci corresponds to fd[i] of the algorithm and Acc.j corresponds to poly_vector[i,j]. (For more thorough understanding of prior art methods for evaluating polynomial by DDA calculation, see: Foley, J.D. and Van Dam, A., 1990 Computer Graphics: Principles and Practice, Addison Wesley.)

1 Initialize poly_vector[0..m, 0..n];

2 while rendering a patch P(s,t) do 3 begin

4 for i: = 0 to n par_do

5 fd[i] := poly_vector[0,i];

{ fd[0..n] took over the ΔՓ₀(iΔt) }

6 while rendering a curve P(s,qΔt) do

7 begin

8 output(fd[0]);

9 for i:= 0 to n-1 par_do

10 fd[i] := fd[i] + fd[i+ 1];

{ augment s by Δs }

11 end;

{ Completion of evaluating P(s,iΔs) }

12 for i := 0 to m-1 parjdo

13 for ,j : = 0 to n par_do

14 poly_vector[i,j] := poly_vector[i,j] +

poly_vector [i + 1 ,j];

{ calculate initial difference of polynomial

P(s,(q+ 1)Δt), i.e., calculate ΔՓ₀((q+l)Δt)}

15 end.

Algorithm 2. 2-variable polynomial forward differencing.

Note that the number of additions needed per sampling point is smaller than that of recursive subdivision and all of the additions can be performed concurrently in a single machine cycle. No stack is required. As to the rendering of trimmed patches, however, forward differencing becomes inefficient though there may be differences between situations. It requires non-trivial preparatory steps which can be summarized as follows: i ) If the trimming curves are defined in the ob,ject or parameter space, pro,jections of the curves into the parameter space is obtained, ii) All points on the trimming curves where the tangents are parallel to the s or t axes are discovered, i.e., the minima/maxima along both s and t axes, iii) Using the minima/maxima, the visible region of the patch is subdivided into multiple pieces, iv) For each piece, individual initialization of forward differencing is needed.

Some of the preparatory steps such as finding parametric image and minima/maxima can be precalculated if the trimming curves are fixed in the parameter space. But the trimming curves are likely to deform, especially when they are not defined in the parameter space. For instance, the silhouette of the patch used in back-faced portion culling or the clipping boundary of a viewport change its shape in the parameter space according to every motion/deformation of the patch or viewing point. So the forward differencing suffers from the above overhead per scene per patch. This time-consuming overhead is due to the fact that the forward differencing must proceed in a 'row major' fashion as previously mentioned. Thus, without the overhead, it is not possible to sample the points in the visible region only as shown in Fig. 5 where neither augmenting s nor resetting to the next curve by augmenting t at point P brings the sampling point back to the visible region.

The row-major evaluation sequence also designate the different augmentation schemes for s and t. When s is augmented, t remains unchanged; However, augmentation along t sets s to 0, i.e., it can take a displacement (Δs,0) but not (0,Δt). When the forward differencing is applied to a polynomial defined in the n dimensional vector space (s₁ ,s₂,···,s_n), it can take only a single specific displacement (0,···Δsi ···,0). Thus the conventional method cannot be used in scientific data visualizations such as tracing a equipotential surface.

A more flexible forward differencing which can arbitrarily change its sampling direction as shown in Fig. 6 (which is an object of the present invention) may sample the visible region only using some effective filling method. In this case, neither the calculation of parametric image nor the searches for minima/maxima become necessary; only one initialization of the difference vector will suffice. Further, the method can be utilized in tracing equipotential surfaces in the vector space of 2 or more dimensions.

It is therefore an object of the present invention to provide a method and apparatus for rendering a trimmed patch without the high overhead mentioned previously.

It is also an object of the present invention to provide a method and apparatus for high-speed visualization of equipotential surfaces by DDA calculations.

DISCLOSURE OF INVENTION

In accordance with the present invention, a method for rendering trimmed patches without the high overhead incurred when obtaining the parametric image of the trimming curves, finding an army of minima/maxima, and performing multiple initializations of difference vector is provided, the method comprises the steps of: receiving an initial difference vector for each dimension which reflects the patch P(s,t) to be rendered, initial evaluation position (s,t)=(So,To) and displacement set {(+Δs,0),(-Δs,0),(0, + Δt), (0,-Δt)} of the evaluation position; receiving a set of trimming curves which surround visible regions on the patch;

evaluating the P(s,t) by applying a series of third order multi-directional DDA calculates each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set, wherein the applications of the DDA calculations are controlled so that all the points in the visible region are sampled once and only once without the overhead; and

displaying the computed P(s,t) value and intensity of each evaluation position on graphic display devices. Also in accordance with the present invention, a method for fast rendering of trimmed patches by DDA calculations which eliminates the high overhead incurred when obtaining the parametric image of the trimming curves, finding an army of minima/maxima, and performing multiple initializations of difference vector is provided, the method comprises the steps of:

receiving an initial difference vector for each dimension which reflects the patch P(s,t) to be rendered, initial evaluation position (s,t)=(S₀,T₀) and a set of displacements {(Δs,0),(0,Δt)} of the evaluation position;

receiving a set of trimming curves which surround visible regions on the patch;

evaluating the P(s,t) by applying a series of third order multi-directional DDA calculates each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

inverting a displacement in the set of displacements, i.e., making the difference vector reflect the patch to be rendered, either a displacement set

{(-Δs,0), (0,Δt)} or {(Δs,0), (0,-Δt)}, and current evaluation position.

controlling the applications of the DDA calculations so that all the points in the visible region are sampled once and only once without the overhead;

displaying the computed P(s,t) value and intensity for each evaluation position on graphic display devices.

Also in accordance with the present invention, an apparatus for the fast rendering of trimmed patches without the high overhead incurred when obtaining the parametric image of the trimming curves, finding an army of minima/maxima, and performing multiple initializations of difference vector. This apparatus includes: means for receiving initial difference vector for each dimension which reflects the patch P(s,t) to be rendered, a set of displacements {(±Δs,0), (0,±Δt)}, and initial evaluation position (s,t)=(S₀,T₀);

means for evaluating the P(s,t) by applying a series of third order multi-directional DDA calculates each of which corresponds to a displacement ofthe evaluation position by a displacement from the displacement set;

means for visiting all the sampling points in the interior region enclosed by trimming curves once and only once without the overhead; and

means for displaying the computed P(s,t) value and intensity of each evaluation position on graphic display devices.

Also in accordance with the present invention, apparatus for the fast rendering of trimmed patches is provided, the apparatus includes:

means for receiving initial difference vector for each dimension which reflects the patch P(s,t) to be rendered, displacement set {(Δs,0), (0,Δt)}, and initial evaluation position (s,t)=(S₀,T₀);

means for evaluating the P(s,t) by applying a series of third order multi-directional DDA calculates each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

means for inverting one of the displacements in the set of displacements by making the difference vector reflect the patch to be rendered, either a set of displacements {(-Δs,0), (0,Δt)} or {(Δs,0), (0,-Δt)} to evaluate P(s,t) for one of the displacements of eiflier (-Δs,0) or (0,-Δt);

Also in accordance with the present invention, a method for visualizing equipotential surface by DDA calculations is provided. The method includes the steps of:

receiving the initialized difference vector poly_vector[0..D₁,0..D₁, ···0..D_n,0..D_n] for each dimension which reflects the polynomial potential function P(s₁,···,S_n) to be traced, a set of displacements {(±Δs₁,0,···,0), (0,±Δs₂ ···,0), ··· (0,··· 0,±Δs_n)} of sampling point (s₁ ,···,S_n) and the initial evaluation position (S0₁ ,S0₂,···, S0_n) on the visible region;

evaluating the P(s₁ ,···,s_n) by applying a series of n-th order multi-directional DDA calculates each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

deciding the next displacement to be taken among the set of displacements; and

displaying each computed P(s₁ ,···,s_n) value and intensity of each evaluation position on graphic display devices.

receiving the initialized difference vector for each dimension which reflects the polynomial potential function P(s ₁,···,s_n) to be traced, a displacement set

{(Δs₁ ,0,··· ,0),(0,Δs₂···,0),··· (0,···,0, Δs_n)} of evaluation position (s₁,···,s_n) and the initial evaluation position (S0ι ,S02,···,S0n) on the visible region;

inverting one of the displacements in the set of displacements;

deciding the next displacement to be taken among the set of displacements; and

displaying each computed P(s,t) value and intensity of each evaluation position on graphic display devices.

Also in accordance with the present invention, an apparatus for visualizing equipotential surface by DDA calculations is provided. The method includes the steps of:

means for receiving the initialized difference vector poly_vector[ 0..D₁,0..D₁ ,··· 0..D_n,0..D_n] for each dimenaon which reflects the polynomial potential function P(s₁,··· ,s_n) to be traced, a set of displacements {(±Δs₁,0,···,0), (0,±Δs₂··· ,0),··· (0,··· ,0,±Δs_n)} of sampling point (s₁,··· ,s_n) and the initial evaluation position (S0ι,S02,···,S0n) on the visible region;

means for evaluating the P(s₁,···,s_n) by applying a series of n-th order multi-directional DDA calculates each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

means for deciding the next displacement to be taken among the set of displacements; and

means for displaying each computed P(s,t) value and intensity of each evaluation position on graphic display devices.

means for receiving the initialized difference vector for each dimension which reflects the polynomial potential function P(s₁,··· ,S_n) to be traced, a displacement set {(Δs₁,0,···,0), (0,Δs₂···,0),··· (0,··· ,0,Δs_n)} of sampling point (s₁,··· ,s_n) and the initial evaluation position (S0₁,S0₂,···,S0_n) on the visible region;

DESCRIPTION OF THE DRAWINGS

The invention will be described in greater detail with reference to the drawings in which: FIGURE 1 shows a rendering process of a trimmed bicubic patch.

FIGURE 2 is a hardware implementation of conventional forward differencing for 1-dimensional polynomial.

FIGURE 3 shows the sampling(evaluation) sequence of conventional forward differencing.

FIGURE 4 is a hardware implementation of conventional forward differencing for 2-dimensional polynomial.

FIGURE 5 shows anomaly of conventional forward differencing on rendering trimmed patches.

FIGURE 6 shows the arbitrary directional sampling(evaluation) sequence of the current invention.

FIGURE 7 shows overall structure of the current invention.

FIGURE 8 is a hardware implementation of current invention for 2- dimensional polynomial.

FIGURE 9 is a execution instance of the current invention.

FIGURE 10 shows the process of rendering parametric bicubic patches.

BEST MODE FOR CARRYING OUT THE INVENTION

Fig 7. shows an overall block diagram of an instance of the present invention. Each of the MFD(Multi-Directional Forward Differencing) units successively performs DDA calculations to evaluate a polynomial P(s₁,··· ,s_n) when its evaluation position (s₁ ,···,s_n) displaces by any of displacement vector (Δs₁,0,···,0), (0,Δs₂··· ,0),··· (0,··· 0,Δs_n) once initialized properly. Thus, the units output the values of polynomials which are supplied to the frame buffer as the position vector (x,y,z) and intensity on that position to create an image, for example, a patch V(P(s,t)) as shown in Fig. 1. The DCU(displacement control unit) shown in the figure determines which one of the displacements (Δs₁,0,···,0), (0,Δs₂···,0),··· (0,···,0,Δs_n) to be taken every moment. This unit is needed to trace equipotential surfaces and to sample the points on a visible region of a trimmed patch once and only once. As to the tracing of equipotential surfaces, the DCU successively determines next displacement to be taken on the basis of, say, a gradient of a potential function, which may be calculated again by MFD units. As to the rendering of trimmed patches, DCU keeps information about the trimming curves and checks to see if the computed position vector (x,y,z) is in the interior region defined by the trimming curves. If not, it commands to push or pop the difference vector onto or out of the stack memories, each of which is a part of the MFD unit, and to change the sampling direction so as to bring the sampling position back to the visible region. Some filling methods, such as scan-line seed fills may be adopted to sample each point in the visible region once and only once with only a small stack requirement(For more detailed information about the filling method, see Foley, J.D. and Van Dam, A., Computer Graphics 1990.) The DCU unit can be implemented using conventional circuits such as state machines or general CPU units.

What deserve greater attention here are the MFD units. A MFD unit is designed to evaluate polynomial P(s,t) for a series of displacements each of which are (±Δs,0) or (0,±Δt). Note that the conventional forward differencing can evaluate the polynomial for only a single displacement (Δs,0). In case of the general n-dimensional polynomial P(s₁,S₂,···,s_n), the MFD unit can take any of 2n directional displacements (±Δs₁,0,···),··· ,(0,··· ,±Δs_n) by multi-directional DDA calculation whereas conventional forward differencing adheres to a single specific direction (0,··· Δs_i··· ,0). This makes the fast trimmed patch generation and the equipotential surface tracing possible. For the clarity of the explanation, the 2-dimensional MFD is presented henceforth. Extension to the higher dimensions shall be followed.

As a primary step to the methods used in MFD unit, a method is shown in algorithm 3 below. Let us call it fundamental multi-directional forward differencing or f-mfd in short. The initialization of poly_vector in line 1 of f-mfd is identical to that of Algorithm 2(conventional forward differencing). Lines 10-13 perform

DDA calculations over each column of it to augment t by Δt. They are again identical to lines 12-14 of Algorithm 2, but have a different effect because of the lines 6-9. Actually, s remains unchanged even by these operations, because lines

6-9 perform DDA calculations over all the rows of poly_vector rather than on the top-most row as in Algorithm 2. An instance of primary MFD unit, a hardware implementation of f-mfd, is shown in Fig. 8. It performs the calculations in a fully parallel fashion. The complexity of f-mfd with respect to hardware cost and execution time is about the same as conventional forward differencing, but it is more dynamic than the conventional algorithm. Note that any computing machine can perform the f-mfd by serially executing the parallel instructions in the algorithm.

1 Initialize poly_vector[0..m, 0..n];

{The initialization is identical to that of Algorithm 2}

2 while navigating_in_(s,t) do

3 begin

4 output(poly_vector[0,0]);

5 input(smpl_dir); {sampling direction:

parallel to s or t axis }

7 for i = 0 to m par_do

8 for j = 1 to n-1 par do

9 poly_vector[i,j] := poly_vectof[i,j]

+ poly_vector[i,j+ 1]; + poly_vector[i,,j+1];

{augment s by Δs}

10 if (smpl_dir = t_axis)

11 for i = 1 to m-1 par_do

12 for j = 0 to n par_do

13 poly_vector[i,j] := poly_vector[i,j]

+ poly_vector[i+1,j];

{augment t by Δt}

14 end.

Algorithm 3. Fundamental Multi-directional Forward differencing

(f-mfd).

Fig. 9 shows an instance of the execution trace of algorithm 3. In this instance, we choose the simple polynomial P(s,t)=s³t³ where the initial value (So.To) is (0,0) and the displacement (Δs,Δt)=(1,1). Note that Algorithm 3 can be applied even if initial values are any real numbers other than (0,0). It is formally proven that f-mfd evaluates general 2-dimension polynomial P(s,t) for successive displacement either (Δs,0) or (0,Δt). It should be noted from the results obtained previously that we need at least two more displacements (-Δs,0), (0,-Δt) to navigate freely in 2-dimensional space. The resulting algorithm with displacement set {(±Δs,0), (0,±Δt)} will be called Complete Multi-directional Forward Differencing or c-mfd briefly.

For convenience' sake, we introduce forward differencing operator:

The operator K_s ⁱ(Δs) on P(s,t) is defined to be

Similarly, another operator K_t ⁱ(Δt) is defined to be

⌠ K_t ⁱ(Δt)P(s,t)= K_t ^{i -1}(Δt)P(s,t+ Δt)- K_t ^{i -1}(Δt)P(s,t) (i>0)

Each operator Kⁱ designates an i-th order forward difference explicitly stating the displacements (Δs,Δt) and the dimension it applies to. Each component of initial poly_vector of algorithm 2 and algorithm 3 then can be described in terms of the operator as shown below:

poly_vector[i,j] = K_t ⁱ(Δt)K_s ^j(Δs)P(S₀,T₀).

Extension of f-mfd to c-mfd is achieved straightforward by using an operator per direction per dimension, i.e., by applying K_s ⁱ(Δs), K_s ⁱ(-Δs), K_tj(Δt) and K_t ^j(-Δt) to P(s,t). In this case, the poly_vector becomes 4-dimensional array poly_vector[0..m,0..m, 0..n,0..n] with each dimension per operator. This scheme works properly because the multi-directional forward differencing can be performed on the polynomial of 2 or more dimensions. Note that the amount of hardware resources needed in this scheme can be reduced far less than that required by f-mfd, a square as much by series of simplifications. An obvious way is to make use of the fact that if operator Ks is applied to a dimension s more than (degree of polynomial in s), the difference becomes constant 0, i.e., K_s ⁱ(Δs)K_s ^j(-Δs) P(s) _ 0 iff i+ j > (degree of polynomial in s). We need not have to allocate any resources to these differences as shown in Algorithm 4.

Initialize poly_vector[0..m, 0..m, 0..n, 0..n];

{ Note that we need to initialize poly_vector[s⁺ ,s- ,

r,f] where s⁺ + s-≤ m +1 and t⁺+ t-≤ n+1.}

while navigating_in_(s,t) do

begin

output(poly_vector[0,0,0,0]);

input(smpl_dir); {sampling direction : parallel to s axis or parallel to t axis }

if (smpl_dir = s⁺)

for i⁺ = 0 to m-1 par do

for i- = 0 to m-1-i⁺ par do

for j⁺ = 0 to n-1 par do

for j- = 0 to n-j⁺ par do

poly_vector[i⁺ ,i- ,j⁺,j-]: =poly_vector[ϊ⁺ ,i- ,j⁺ ,j-]

+ poly_vector[i⁺ + 1 ,i- ,j⁺ ,,j- ] ;

else if (smpl_dir = s-)

for i⁺ = 0 to m-1 par do

for i- = 0 to m-1-i⁺ par do

for j⁺ = 0 to n par do

for j- = 0 to n-j⁺ par do

poly_vector[i⁺ ,i- j⁺ ,j-] : =poly_vector[i⁺ ,i- ,j⁺ ,j-]

+ poly_vector[i⁺,i-+ 1,j⁺,j-];

{ Similar process applies to dimension t }

end.

Algorithm 4. The c-mfd using 2 operators per dimension.

Algorithm 4 requires not only the increased number of the poly_vector components but also the increased complexity in initialization of polyjvector. If an algorithm with fewer components and lower initialization cost is desired, Algorithm 5 shown below will be an effective approach. It obtains four displacements by about the same amount of hardware and initialization cost as f-mfd, somewhat sacrificing the speed.

It initially keeps the same poly_vector as f-mfd, i.e., the vector with feasible displacement set {(Δs,0), (0,Δt)}. Then it derives vector with displacement set {(-Δs,0), (0,Δt)} or {(Δs,0), (0,-Δt)} from the current poly_vector: it derives K_s ⁱ(-Δs)P(s-Δs,t) (i=0,1,··· ) from K_s ^j(Δs)P(s,t) 0=0,1,···) according to the following equation,

The Eq. (2) has also been firmly proven though we omit the proof here. The Eq. (2) can be directly implemented into the forward differencing as: p

Let us call this derivation 'displacement inversion'.

For a degree m polynomial, the displacement inversion process requires m-i+ 1 additions to compute each of the new poly_vector[i,j] which cannot be done in parallel fashion. Thus the process is slower than the DDA calculation of

Algorithm 4. Anyway, the inversion does not occur frequently in applications such as trimmed patch rendering.

We instantiate the displacement inversion for bicubic polynomials in algorithm 5. The Eq. (2) in this case becomes;

K⁰(-Δs)P(s-Δs) = K⁰(Δs)P(s) - K¹(Δs)P(s) + K²(Δs)P(s)

- K³(Δs)P(s)

K¹(-Δs)P(s-Δs) - K¹(Δs)P(s) + 2K²(Δs)P(s) - 3K³(Δs)P(s)

K²(-Δs)P(s-Δs) K²(Δs)P(s) - 3K³(Δs)P(s)

K³(-Δs)P(s-Δs) - K³(Δs)P(s)

Initialize poly_vector[0..3,0..3] ;

while navigating_in_(s,t) do begin

output(poly_vector[0,0]);

input(smpl_dir); {get new direction s⁺ or s-, t⁺ or t-}

if (smpl_dir does not changed along s axis){same direction}

for i = 0 to 2 par do

for j = 0 to 3 par do

poly_vector[i,j] : =poly_vector[i,j] +poly_vector[i + 1,j] ; if (smpl_dir is inversed along s axis) {displacement inversion}

for j = 0 to 3 par do

parbegin {begin execution of parallel statements}

poly_vector[0,j]:= poly_vector[0,j]- poly_vector[1,j]

+ poly_vector[2,j]- poly_vector[3,,j];

poly_vector[l ,j] : =-poly_vector[1 ,j] +2*poly_vector[2,j]

- 3*poly_vector[3,j];

poly_vector[2,j]:= poly_vector[2,j]- poly_vector[3,j];

poly_vector[3,j]:= - poly_vector[3,j];

parend; {end of parallel statements}

{Similar process applies to t }

end.

Algorithm 5. The 2-dimensional c-mfd using displacement inversion.

It should be noted that the number of additions needed per rendering a trimmed patch can be greatly reduced by exploiting 1 dimensional difference vector fd[i] as shown in Algorithm 1.

Fig. 10 shows rendering sequence of a trimmed patch viewed in the parameter space. The patch is trimmed by edges of a viewport(E) defined in the screen space. The scan-line seed fill method is used to visit all the points in the visible region once and only once. In Fig. 10a, the span containing the initial seed i has been filled in by evaluating P(s,t) for all the sampling points on the span using multi-directional DDA calculation, and difference vector for the numbered seeds(Point 1) calculated also by multi-directional DDA calculation have been saved on a stack. The numbers indicate order on the stack, i.e., No. 1 indicate the difference vector to be popped first. After filling a span, the difference vector on the stack is popped and the span containing the vector is then filled until the stack becomes empty. Note that a parametric image of the edges of the viewport(E) does not have to be calculated because the region checking can be done in the object space.

Extension of 2-dimensional c-mfd to n-dimensional c-mfd (n>2) can be achieved straightforward using poly_vector of 2n-dimensions, a dimension per each operator K_{s 1}(Δ_s1),K_{s 1}(-Δ_s1), K_s2(Δ_s2),K_s2(-Δ_s2)··· K_sn(Δ_sn) ,K_sn(-Δ_sn) or using poly_vector of n-dimensions, a dimension per each operator K_s1(Δ_s1),

K_s2(-Δ_s2)··· K_sn(Δ_sn) in which case the displacement inversion must be incorporated. Algorithm 6 shows an n-dimensional c-mfd with displacement inversion.

i+1 j l jq-1

Note that the term Σ Σ• • Σ 1 can be precalculated in a table.

j l = l j2=l j_q=j_q. _j

Initialize poly_vector[0..D₀ ,···0..D_n];

while navigating_in_(s₁ , ···sn) do

begin

output(poly_vector [0, ···0]);

input(smpl_dir); {get new direction among

(Δs₁,0,···,0), (0,Δs₂···,0),··· (0,···,0,Δsn) }

if (smpl_dir does not changed along si axis){same direction} for si = 0 to D₁ par do

........

for si = 0 to D_{i -1} par_do

.......

for sn = 0 to D_n par do

poly_vector[s₁··· ,s_i, ··· s_n]: =poly_vector[s₁···,s_i,···s_n]

+poly_vector[s₁···,s_i +1,···s_n];

if (smpl_dir is inversed along si axis) {displacement inversion}

........

for si = 0 to D_i par_do

.......

parbegin {begin execution of parallel statements}

poly_vector[··· ,si,-"] : = pare

nd; {end of parallel statements}

....

{Similar process applies to t }

end.

Algorithm 6. The n-dimensional c-mfd using displacement inversion. The n-dimensional c-mfd is applicable to numerical calculations such as tracing equipotential surfaces or plotting a solution surfaces of a system of nonlinear equations. Conventional forward differencing cannot be applied as a result of its row-ma,jor evaluation sequence. Other conventional methods such as Homer's rule are not sufficiently fast.

Claims

1. A method for rendering trimmed patches without the high overhead incurred when obtaining the parametric image of trimming curves, finding an army of minima/maxima, and perrfαrming multiple initializations of difference vector, said method comprising the steps of:

receiving an initial difference vector poly_vector[0..3,0..3,0..3,0..3] for each dimension which reflects the patch P(s,t) to be rendered, initial evaluation position (s,t)=(S_o,T_o) and a displacement set {(+Δs,0), (-Δs,0),(0,+Δt), (0,-Δt)} of the evaluation position;

receiving a set of trimming curves which surround visible regions on the patch;

evaluating the P(s,t) by applying a series of multi-directicaial DDA(digital differential analyzer) calculations each of which corresponds to a displacement of the evaluation position by a displaoeoent from the displacement set, vdierein the application of the DDA calculations are controlled so that all the points in the visible region are sampled once and only once without the overhead; and displaying the computed P(s,t) value and intensity of each evaluation position on graphic display devices.

2. The method according to claim 1, wherein the step of evaluating the P(s,t) further comprises, respectively, the step of:

poly_vector[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + poly_vector[s⁺+1,s-,t⁺,t-]

( 0 ≤s+< 3, 0≤s-,t⁺,t-≤ 3)

in case the evaluation position displaces by (Δs,0);

poly_vectcar[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + poly_vector[s⁺,s-+1,t⁺,t-]

(0≤s-< 3, 0≤s⁺,t⁺,t-≤ 3)

in case the evaluation position displaces by (-Δs,0); poly_vector[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + poly_vector[s⁺,s-,t⁺+1,t-]

( 0≤t⁺< 3, 0≤s⁺,s-,t-≤ 3)

in case the evaluation position displaces by (0, Δt); and

poly_vector[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + poly_vector[s⁺,s-,t⁺,t-+1]

( 0≤t-< 3, 0≤s⁺,s-,t⁺≤ 3)

in case the evaluation position displaces by (0,-Δt).

3. A method for rendering trimmed patches by DDA calculations which eliminates the high overhead incurred when obtaining the parametric image of the trimming curves, finding an aray of minima/maxima, and performing multiple initializations of difference vector, said method comprising the steps of:

receiving an initial difference vector poly_vector[0..3,0_.3] for each dimension which reflects the patch P(s,t) to be rendered, initial evaluation position (s,t)=(S_o,T_o) and a displacement set {(Δs,0),(0,Δt)} of the evaluation position;

receiving a set of trimming curves which surround visible regions on the patch;

evaluating the P(s,t) by applying a series of multi-directional DDA calculations each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

inverting a displacement in the set of displacements, i.e., making the difference vector reflect the patch to be rendered, either a set of displacements {(-Δs,0), (0,Δt)} or {(Δs,0), (0,-Δt)};

controlling the application of the DDA calculations so that all the points in the visible region are sampled once and only once without the overhead; and displaying the computed P(s,t) value and intensity for each evaluation position on graphic display devices.

4. The method according to claim 3 wherein the step of evaluating the P(s,t) further conprises, respectively, the step of the operations:

poly_vectαr[s,t] := poly_vector[s,t] + poly_vector[s+1,t]

in case the displacement of the evaluation position is (Δs,0); and poly_vector[s,t] := poly_vector[s,t] + poly_vector[s,t+1]

in case the displacement of the evaluation position is (0,Δt);

5. The method according to claim 3 wherein the step of inverting the displacement further comprises, respectively, the step of:

poly_vector[s,t]

in case the displacement to be inverted is (Δs,0)> and

poly_vector[s,t]

in case the displacement to be inverted is (0,Δt).

6. An apparatus for the fast rendering of trimmed patches is provided. It is intended to eliminates the high overhead incurred when obtaining the parametric image of the trimming curves, finding an army of minima/maxima, and performing multiple initializations of difference vector, said apparatus including:

means for receiving initial difference vector poly_vector[0..3,0..3, 0..3.0..3] for each dimension vzhich reflects the patch P(s,t) to be rendered, a set of displacements {(±Δs,0), (0,±Δt)}, and initial evaluation position (s,t)=(S_o,T_o);

means for evaluating the P(s,t) by applying a series of multi-directional DDA calculations each of which corresponds to a displacement of the evaluation position hy a displacement from the displacement set:

means for evaluating all the sampling points in the interior region enclosed by trimming curves once and only once without the overhead, said means comprises logics such as state machines which perform filling operation by successively evaluating P(s,t) for a series of the displacement (±Δs,0), (0,±Δt), occasionally pushing or popping the difference vector onto or out of the stack memory; and

7. The apparatus according to claim 6 wherein the means for evaluating the P(s,t) further comprises means for performing operations:

polyji«xrtcr[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + poly_vector[s⁺+1,s-,t⁺,t-] ( 0≤s⁺< 3, 0≤s-,t⁺,t-≤ 3)

in case the evaluation position displaces by (Δs,0);

poly_vector[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + poly_vector[s⁺,s-+1,t⁺,t-] ( 0≤s-< 3, 0≤s⁺,t⁺,t-≤ 3)

in case the evaluation position displaces by (-Δs,0);

poly_vectcr[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + poly_vector[s⁺,s-,t⁺+1,t-]

( 0≤t⁺< 3, 0≤s⁺,s-,t-≤ 3)

in case the evaluation position displaces by (0,Δt); and

poly_vector[s⁺,s-,t⁺,t-]:=

poly_vector[s⁺,s-,t⁺,t-] + polyjυector[s⁺,s-,t⁺,t-+1]

( 0≤t-< 3, 0≤s⁺,s-,t⁺≤ 3)

in case the evaluation position displaces by (0,-Δt).

8. An apparatus for rendering trimmed patches, including:

means far receiving initial difference vector poly_vector[0..3,0..3] for each dimension which reflects the patch P(s,t) to be rendered, a set of displacements {(Δs,0), (0,Δt)}, and initial evaluation position (s,t) =(S_o,T_o);

means for evaluating the P(s,t) by applying a series of multi-directional DDA calculations each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

means for inverting a displacement in the displacement set by making the difference vector reflect the patch to be rendered, either a set of displacements {(-Δs,0), (0,Δt)} or {(Δs,0), (0,-Δt)} to evaluate P(s,t) for one of the displacements either (-Δs,0) or (0,-Δt);

means for evaluating all the sampling points in the interior region enclosed by trimming curves once and only once without the overhead, said means comprises logics such as state machines which perform filling operation by successively evaluating P(s,t) for a series of the displacements (±Δs,0), (0,±Δt), occasionally pushing or popping the difference vector into or out of stadc memory; and

9. The apparatus aooording to claim 8 wherein the means for evaluating the P(s,t) further comprises means for performing operation:

poly_vector[s,t] := poly_vector[s,t] + poly_vector[s+1,t]

in case the displacement of the evaluation position is (Δs,0); and poly_vector[s,t] := poly_vector[s,t] + poly_vectcr[s,t+1]

in case the displacement of the evaluation position is (Δt,0).

10. The apparatus according to claim 8 wherein the means of inverting the displacement further comprises means far performing operations:

poly_vector[s,t]

in case the displacement to be inverted is (Δs,0); and

poly_vector[s,t]

in case the displacement to be inverted is (0,Δt).

11. A method for visualizing equipotential surface by DDA calculations, said method including the steps of:

receiving the initialized difference vector poly_vector[0..D₁,0..D₁, ··· 0..D_n,0..D_n] for each dimension which reflects the potential function P(s₁, ···,s_n) =∑∑ ···∑_ae1 ···_en s₁ ^e1 ···Sn^en, a polynomial of degree D_i in s_i to be traced, a set of displacements {(±Δs₁,0, ···,0), (0,±Δs₂ ···,0), ··· (0, ···,0,±Δs_n)} of sampling point (s_i,···,s_n) and the initial evaluation position (S0₁,S02, ···, S0_n) on the visible region;

evaluating the P(s₁,···,s_n) by applying a series of multi-directional DDA calculations each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

deciding a next displacement to be taken from the displacement set; and displaying each computed P(s₁, ···,s_n) value and intensity of each evaluation position on graphic display devices.

12. The apparatus according to claim 11 wherein the means for evaluating the P(s₁, ···,S_n) further comprises means for performing operations:

poly_vector[s₁ ⁺,s₁-...s_i ⁺...s_n ⁺,s_n-]:= poly_vector[s₁ ⁺,s_ι-,...,s_i ⁺,...]

⁺poly_vector[s₁ ⁺,s₁-,...,s_i ⁺+1, ···] ( 0≤s_i ⁺< D_i, 0≤s_i-≤ D_i, 0≤s_J ⁺,s_j-≤ D_j)

in case the evaluation position displaces by ( ···,Δs_i,···); and poly_vector[s₁ ⁺,s₁-, ···S_i- ···S_n ⁺,s_n-]:= poly_vector[s_i ⁺,s₁-, ···,si-, ···]

⁺poly_vector[s₁ ⁺,s₁-, ···,s_i-+1, ···]

( 0≤s_i ⁺< D_i, 0≤s_i-≤ D_i, 0≤s_j ⁺,s_j-< D_j)

in case the evaluation position displaces by ( ···,-Δs_i,···).

13. A method for visualizing equipotential surface by DDA calculations, said method including the steps of:

receiving the initialized difference vector poly_vector[0..D₁,··· ,0..D_n] for each dimension which reflects the potential function P(s_i,···,s_n)

=ΣΣ ···∑_ac1···_cn S₁ ^e1···S_n ^en to be traced, a set of displacements {(Δs₁,0,··· ,0),(0,Δs2···,0),··· (0,···,0,Δs_n)} of sampling point (s_i, ···,s_n) and the initial evaluation position (S0₁,S0₂,···,S0_n) on the visible region;

evaluating the P(s_i,···,s_n) by applying a series of multi-directional DDA calculations each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

deciding a next displacement to be taken from the displacement set; and displaying each computed P(s_i, ···,s_n) value and intensity of each evaluation position on graphic display devices.

14. The method according to claim 13 wherein the step of evaluating the P(s_i,···,s_n) further comprises, respectively, the step of:

poly_vector[s_i,···s_i,···s_n]:= poly_vector[s₁,··· s_i,···]

+ poly_vector[s₁,···,s_i+1,···];

( 0≤s_i< D_i, 0≤s_j≤ D_j)

in case the evaluation position displaces by ( ···,Δs_i, ···).

15. The method according to claim 13 wherein the step of inverting the displacement further cαsprises, respectively, the step of:

poly_vector[s₁, ···,s_ι ···S_n]

in case the displacement to be inverted is ( ···,Δsi,···).

16. An apparatus for visualizing equipotential surface by DDA calculations, said method including the steps of:

means for receiving the initialized difference vector poly_vector[0..D₁,0..D₁,··· 0..D_n,0..D_n] for each dimension which reflects the potential function P(s_i,···,s_n) =ΣΣ···∑_ac1···_cn s_i ^e1···s_n ^en to be traced, a set of displacements {(±Δs₁.0,···,0), (0,±Δs₂···,0),··· (0,··· ,0,±Δs_n)} of sampling point (s_i,···,s_n) and the initial evaluation position (S0₁,S0₂,···,S0_n) on the visible region;

means for evaluating the P(s_i,···,s_n) by applying a series of multi-directional DDA calculations each of which corresponds to a displacement of the evaluation position by a displacement from the displacement set;

means for deciding a next displacement to be taken among the set of displacements; and

means for displaying each computed P(s_i,···,s_n) value and intensity of each evaluation position on graphic display devices.

17. The apparatus according to claim 16 wherein the means far evaluating the P(s_i,···,s_n) further comprises the means for performing the operations: poly_vector[sι⁺,sι-,···si⁺···Sπ]:= poly_vector[s₁ ⁺,s₁-,···,s_i ⁺,···]

+ poly_vector[s₁ ⁺,s₁-,···,s_i ⁺+1, ···]

( 0≤s_i ⁺< D_i, 0≤s_i-≤ D_i, 0≤s_J ⁺,s_j-≤ D_j)

in case the evaluation position displaces by (···,Δs_i,···); and

poly_vector[s₁ ⁺,s₁-, ···s_i-···s_n]:= poly_vector[s₁ ⁺,s₁-,··· s_i-,··· ]

+ poly_vector[s₁ ⁺,s₁-,···,s_i-+1,···]

(0≤s_i ⁺< D_i, 0≤s_i-≤ D_i, 0≤s_J ⁺,S_J-≤ D_j)

in case the evaluation position displaces by (···,-Δs_ι,···).

18. An apparatus for visualizing equipotential surface by DDA calculations, said method including the steps of: means for receiving the initialized difference vector poly_vector[ 0..D₁,···,0..D_n] for each dimension which reflects the potential function

P(s₁, ···,S_n) =ΣΣ ···Σ_ac1···_cn s₁ ^e1 ···s_n ^en to be traced, a set of displacements

{(Δs_i,0,···,0), (0,Δs₂ ···,0),··· (0,···,0,Δs_n)} of sampling point (s_i,···,s_n) and the initial evaluation position (S0₁,S0₂,···,S0_n) on the visible region;

means for inverting an displacement in the set of displacements, i.e., making the difference vector reflect the potential function to be displayed, a displacement set {(-Δs₁,0,···,0),(0,Δs₂···,0),···(0,···,0,Δs_n)}, {(Δs₁,0,···,0),( 0,-Δs₂···,0),···(0,···,0, Δs_n)},··· or {(Δs₁,0,···,0) , (0, Δs₂···,0) ,···(0,···,0,

-Δs_n)};

means for deciding a next displacement to be taken from the displacement set; and

means for displaying each computed P(s_i···,s_n) value and intensity of each evaluation position an graphic display devices.

19. The apparatus according to claim 18 wherein the means for evaluating the P(s_i,···,s_n) further comprises the means for computing:

poly_vector[s_i,···s_i,···s_n]:= poly_vector[s₁,···,si,···S_n]

⁺ poly_veσtor[s₁,···,s_i+1,···s_n]

( 0≤s_i< D_i, 0≤s_j≤ D_j)

in case the evaluation position displaces by (···,Δs_i,···).

20. The apparatus according to claim 18 wherein the means far inverting the displacement further comprises the means for computing:

poly_vector[s_i,···,s_i···s_n]

in case the displacement be inverted is (···,Δs_i,···).