[go: up one dir, main page]

WO1992009043A1 - Procede et appareil de representation d'une connexion ajustee et d'une surface equipotentielle - Google Patents

Procede et appareil de representation d'une connexion ajustee et d'une surface equipotentielle Download PDF

Info

Publication number
WO1992009043A1
WO1992009043A1 PCT/KR1991/000029 KR9100029W WO9209043A1 WO 1992009043 A1 WO1992009043 A1 WO 1992009043A1 KR 9100029 W KR9100029 W KR 9100029W WO 9209043 A1 WO9209043 A1 WO 9209043A1
Authority
WO
WIPO (PCT)
Prior art keywords
vector
poly
displacement
evaluation position
case
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/KR1991/000029
Other languages
English (en)
Inventor
Jae Yong Koh
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Publication of WO1992009043A1 publication Critical patent/WO1992009043A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation

Definitions

  • 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.
  • Bicubic patch is a mapping P defined by P:[0,1] ⁇ [0,1] ⁇ R 3 .
  • 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 3 . 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
  • trimmed-NURBS non-uniform rational B-splines
  • High-end workstations with interleaved video memory or pixel cache may produce only a portion of a patch inside the processing 'footprint' every moment.
  • 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.
  • the initial difference vector ⁇ 0 is obtained by
  • the poly_vector[0..m,0..n] in algorithm 2 is the difference vector for calculating successive ⁇ 0 (0), ⁇ 0 ( ⁇ t), ⁇ , ⁇ 0 (1).
  • each poly_vector[0,i] successively latches ⁇ i P 0 (0), ⁇ i P 0 ( ⁇ t), ⁇ , ⁇ i P 0 (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.)
  • 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.
  • s 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).
  • s When the forward differencing is applied to a polynomial defined in the n dimensional vector space (s 1 ,s 2 , ⁇ ,s n ), it can take only a single specific displacement (0, ⁇ si ⁇ ,0).
  • 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.
  • 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:
  • initial evaluation position (s,t) (S 0 ,T 0 ) and a set of displacements ⁇ ( ⁇ s,0),(0, ⁇ t) ⁇ of the evaluation position;
  • apparatus for the fast rendering of trimmed patches includes:
  • a method for visualizing equipotential surface by DDA calculations includes the steps of:
  • a method for visualizing equipotential surface by DDA calculations includes the steps of:
  • an apparatus for visualizing equipotential surface by DDA calculations includes the steps of:
  • an apparatus for visualizing equipotential surface by DDA calculations includes the steps of:
  • 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.
  • 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 1 , ⁇ ,s n ) when its evaluation position (s 1 , ⁇ ,s n ) displaces by any of displacement vector ( ⁇ s 1 ,0, ⁇ ,0), (0, ⁇ s 2 ⁇ ,0), ⁇ (0, ⁇ 0, ⁇ s n ) once initialized properly.
  • 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 1 ,0, ⁇ ,0), (0, ⁇ s 2 ⁇ ,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.
  • 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.
  • 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).
  • the MFD unit can take any of 2n directional displacements ( ⁇ s 1 ,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.
  • the 2-dimensional MFD is presented henceforth. Extension to the higher dimensions shall be followed.
  • Fig. 9 shows an instance of the execution trace of algorithm 3.
  • Algorithm 3 can be applied even if initial values are any real numbers other than (0,0).
  • 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.
  • K t i ( ⁇ 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 i 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 i ( ⁇ t)K s j ( ⁇ s)P(S 0 ,T 0 ).
  • Extension of f-mfd to c-mfd is achieved straightforward by using an operator per direction per dimension, i.e., by applying K s i ( ⁇ s), K s i (- ⁇ s), K t j( ⁇ t) and K t j (- ⁇ t) to P(s,t).
  • 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.
  • poly_vector[i + ,i- ,j + ,j-]: poly_vector[ ⁇ + ,i- ,j + ,j-]
  • poly_vector[i + ,i- j + ,j-] : poly_vector[i + ,i- ,j + ,j-]
  • 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.
  • 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.
  • the process is slower than the DDA calculation of
  • K 0 (- ⁇ s)P(s- ⁇ s) K 0 ( ⁇ s)P(s) - K 1 ( ⁇ s)P(s) + K 2 ( ⁇ s)P(s)
  • poly_vector[i,j] poly_vector[i,j] +poly_vector[i + 1,j] ; if (smpl_dir is inversed along s axis) ⁇ displacement inversion ⁇
  • poly_vector[0,j]: poly_vector[0,j]- poly_vector[1,j]
  • poly_vector[l ,j] : -poly_vector[1 ,j] +2*poly_vector[2,j]
  • poly_vector[2,j]: poly_vector[2,j]- poly_vector[3,j];
  • poly_vector[3,j]: - poly_vector[3,j];
  • 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.
  • 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.
  • 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 ),
  • Algorithm 6 shows an n-dimensional c-mfd with displacement inversion.
  • poly_vector[s 1 ⁇ ,s i , ⁇ s n ]: poly_vector[s 1 ⁇ ,s i , ⁇ s n ]
  • 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.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Graphics (AREA)
  • Geometry (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Complex Calculations (AREA)
  • Controls And Circuits For Display Device (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

Procédé et appareil de représentation rapide des connexions ajustées. On vise à éliminer le temps système important qu'il faut pour obtenir l'image paramétrique des courbes d'ajustage définies dans l'espace objet ou écran, pour trouver des minimums/maximums, et pour effectuer de multiples initialisations du vecteur de différence. Cette invention est conçue pour effectuer une différentiation directe dans plusieurs sens parallèles à l'un quelconque des axes de coordonnées de l'espace vecteur dans lequel est définie la connexion, de sorte qu'elle puisse représenter les connexions ajustées avec un temps système peu élevé. Elle s'applique également aux calculs numériques et aux visualisations scientifiques telles que le traçage des surfaces équipotentielles.
PCT/KR1991/000029 1990-11-16 1991-11-16 Procede et appareil de representation d'une connexion ajustee et d'une surface equipotentielle Ceased WO1992009043A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR1019900018608A KR930004215B1 (ko) 1990-11-16 1990-11-16 디지탈하드웨어장치 및 디지탈데이터처리 방법
KR1990/18608 1990-11-16

Publications (1)

Publication Number Publication Date
WO1992009043A1 true WO1992009043A1 (fr) 1992-05-29

Family

ID=19306147

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/KR1991/000029 Ceased WO1992009043A1 (fr) 1990-11-16 1991-11-16 Procede et appareil de representation d'une connexion ajustee et d'une surface equipotentielle

Country Status (2)

Country Link
KR (1) KR930004215B1 (fr)
WO (1) WO1992009043A1 (fr)

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1987002157A1 (fr) * 1985-10-02 1987-04-09 American Telephone & Telegraph Company Reseau de commutation maille
DE3815390A1 (de) * 1987-05-08 1988-11-24 Sun Microsystems Inc Anordnung und verfahren zur adaptiven vorwaertsdifferenzbildung bei der erzeugung von kurven und flaechen
US4999789A (en) * 1987-02-05 1991-03-12 Hewlett-Packard Co. Method and apparatus for trimming B-spline descriptions of patches in a high performance three dimensional graphics system

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1987002157A1 (fr) * 1985-10-02 1987-04-09 American Telephone & Telegraph Company Reseau de commutation maille
US4999789A (en) * 1987-02-05 1991-03-12 Hewlett-Packard Co. Method and apparatus for trimming B-spline descriptions of patches in a high performance three dimensional graphics system
DE3815390A1 (de) * 1987-05-08 1988-11-24 Sun Microsystems Inc Anordnung und verfahren zur adaptiven vorwaertsdifferenzbildung bei der erzeugung von kurven und flaechen

Also Published As

Publication number Publication date
KR920010418A (ko) 1992-06-26
KR930004215B1 (ko) 1993-05-21

Similar Documents

Publication Publication Date Title
US6925210B2 (en) Method for blurring images in real-time
Swanson et al. A fast shaded-polygon renderer
US4667236A (en) Television perspective effects system
US5977994A (en) Data resampler for data processing system for logically adjacent data samples
EP0396311B1 (fr) Méthode et appareil de traitement d'image
US3639736A (en) Display windowing by clipping
JPH0628485A (ja) テクスチャーアドレス生成器、テクスチャーパターン生成器、テクスチャー描画装置及びテクスチャーアドレス生成方法
US5136660A (en) Apparatus and method for computing the radon transform of digital images
US5402337A (en) Method and apparatus for constructing three-dimensional surface shading image display
JPS61136177A (ja) 像データを計算する為に使う装置
US5483627A (en) Preprocessing pipeline for real-time object based graphics systems
EP0986906B1 (fr) Procede et systeme permettant de generer des trames d'affichage a partir d'une sequence de trames source en synthetisant une ou plusieurs trames intermediaires uniquement a partir d'une trame source qui les precede immediatement
WO1992009043A1 (fr) Procede et appareil de representation d'une connexion ajustee et d'une surface equipotentielle
US4945497A (en) Method and apparatus for translating rectilinear information into scan line information for display by a computer system
JP2634126B2 (ja) グラフィックス表示方法および装置
Kanus et al. Implementations of Cube-4 on the teramac custom computing machine
JP2588257B2 (ja) 輪郭近似方式
US5745123A (en) Method for resizing an image by a factor of two
EP1032883B1 (fr) Reechantilloneur de donnees pour systeme de traitement de donnees
JPS6125278A (ja) 実時間三次元画像処理装置
CN118736023B (zh) 一种集成点云加速模块的线结构光相机和方法
JP3055024B2 (ja) 画像デ―タの転送装置
JP2610825B2 (ja) 図形処理装置
KR100261075B1 (ko) 트라이리니어 텍스쳐 매핑 가속화 장치
JPH0251789A (ja) 立体表現画像の陰影付加装置

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IT LU NL SE

122 Ep: pct application non-entry in european phase