WO2003102875A1 - Triangle polygon plotting device and triangle polygon plotting method - Google Patents

Triangle polygon plotting device and triangle polygon plotting method Download PDF

Info

Publication number
WO2003102875A1
WO2003102875A1 PCT/JP2003/007036 JP0307036W WO03102875A1 WO 2003102875 A1 WO2003102875 A1 WO 2003102875A1 JP 0307036 W JP0307036 W JP 0307036W WO 03102875 A1 WO03102875 A1 WO 03102875A1
Authority
WO
WIPO (PCT)
Prior art keywords
pixel
coordinate
triangle
polygon
vertex
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/JP2003/007036
Other languages
English (en)
French (fr)
Inventor
Yoshiyuki Kato
Akira Torii
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.)
Mitsubishi Electric Corp
Original Assignee
Mitsubishi Electric Corp
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 Mitsubishi Electric Corp filed Critical Mitsubishi Electric Corp
Priority to US10/483,492 priority Critical patent/US20040164985A1/en
Priority to EP03730808A priority patent/EP1510971A4/en
Priority to KR1020047000460A priority patent/KR100594555B1/ko
Publication of WO2003102875A1 publication Critical patent/WO2003102875A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three-dimensional [3D] modelling for computer graphics
    • G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—Two-dimensional [2D] image generation
    • G06T11/40—Filling planar surfaces by adding surface attributes, e.g. adding colours or textures

Definitions

  • the present invention relates to a triangular polygon drawing apparatus and a triangular polygon drawing method for decomposing and drawing triangular polygons into pixels in a technical field of displaying a computer graphics image on a display.
  • FIG. 1A is a diagram for explaining a conventional triangle polygon drawing method.
  • This conventional triangular polygon drawing method is disclosed in the following document, for example, and generates a vixel by repeating edge processing and span processing.
  • this triangular polygon drawing method is classified into three processes: a setup process, an edge process, and a span process.
  • the incremental pattern of the left edge, right edge, and span (scan line between right edge and left edge, current span) in Fig. 1A is used.
  • the various components of a pixel are depth value (z), color value (r, g, b, a), texture coordinates (s, t), and the like.
  • the setup process is performed only once for one triangular polygon.
  • the left edge pixel P 1 e f t and the right edge pixel P r i g h t are calculated by interpolation using the incremental parameter of the page obtained in the set up processing.
  • the X coordinate of the left edge can be calculated by adding the incremental parameter ⁇ Xleft to the previous X coordinate Xold as in the following equation (1).
  • pixels in the scan line direction sandwiched by the left edge pixel P 1 e f t and the right edge pixel P r i g h t obtained in the edge processing are sequentially obtained by interpolation processing.
  • a new pixel can be calculated by adding the X-direction increment parameter as in the following equation (2).
  • the sub-pixel collection is a process for correcting the pixel value of the edge to the value of the center point of the pixel, and is expressed by the following equation (3).
  • the present invention has been made to solve the above-described problem, and eliminates the need for sub-pixel collection at the time of updating a scan line, and can efficiently draw a triangular polygon with simple control. It is intended to provide a gon drawing method. Disclosure of the invention
  • the triangle polygon drawing apparatus includes a triangle type discriminating means for classifying a polygonal shape from the vertex coordinates of the triangle polygon according to the direction and inclination of the major edge to determine the moving direction of the pixel. Based on the moving direction determined by the triangle type discriminating means, the pixels are interpolated in the X direction in order from the start pixel closest to the ⁇ coordinate minimum point or ⁇ coordinate maximum point of the shape of the triangular polygon, and the major edge is first determined. Save the surplus pixels, move the pixels from the major edge to one minor edge, draw one scan line of a triangular polygon, and interpolate the retreated pixels in the ⁇ direction to start the next scan line. And a pixel drawing means.
  • the triangular polygon drawing method is characterized in that the shape of the triangular polygon is classified according to the direction and the inclination of the major edge from the vertex coordinates of the triangular polygon, and the moving direction of the pixel is determined. Based on the direction, the pixel is interpolated in the X direction, starting from the start pixel closest to the minimum Y coordinate vertex or the maximum Y coordinate vertex of the triangular polygon, and measured.
  • FIG. 1 is a diagram for explaining a conventional triangle polygon drawing method.
  • FIG. 2 is a diagram showing a configuration of a triangle polygon drawing device according to a first embodiment of the present invention.
  • FIG. 3 is a diagram for explaining the operation of the triangular polygon drawing device according to the first embodiment of the present invention.
  • FIG. 4 is a diagram for explaining the shapes of four types of triangular polygons classified in the type determination step.
  • FIG. 5 is a diagram showing the drawing direction of the pixels and the stored pixels.
  • FIG. 6 is a diagram showing a configuration of a triangular polygon drawing apparatus according to Embodiment 2 of the present invention. BEST MODE FOR CARRYING OUT THE INVENTION
  • FIG. 2 is a diagram showing a configuration of a triangular polygon drawing device according to the first embodiment of the present invention.
  • 1 is a parameter calculating means for calculating an incremental parameter from the vertex data of the triangular polygon
  • 2 is a parameter calculating means for classifying the shape of the triangular polygon into four types from the parameter calculating means 1.
  • 3 is a start pixel calculating means for calculating a start pixel from the parameter calculating means 1
  • 4 is a pixel moving means (pixel drawing means) for moving a pixel in the X direction or the Y direction according to the determination result of the triangle type determining means 2.
  • 5 are pixel interpolating means (pixel drawing means) for interpolating pixel values according to the pixel moving means 4.
  • FIG. 3 is a diagram for explaining the operation (triangle polygon drawing method) of the triangle polygon drawing device according to the first embodiment of the present invention.
  • the parameter calculating means 1 sorts the vertices of the triangle.
  • the vertex having the minimum Y coordinate (the minimum vertex of the Y coordinate) is V 0 (X 0, Y 0)
  • the vertex having the maximum Y coordinate (the maximum vertex of the Y coordinate) is V 1 (XI, Y 1 )
  • the remaining vertices V2 (X2, Y2) (see Fig. 3B).
  • the upper left is the origin 0 of the X-Y coordinate system.
  • the parameter overnight calculation means 1 calculates the incremental parameters in the X and ⁇ ⁇ directions from the vertex data V0, VI, and V2 of the triangular polygon for the various components of the pixel. calculate.
  • the various components of a pixel include depth values ( ⁇ ), color values (R, G, B, A), texture coordinates (U, V), and the like.
  • ⁇ depth values
  • R, G, B, A color values
  • U texture coordinates
  • the Z values of vertices V 0, VI, and V 2 are zl, z 2, and z 3, respectively, the Z-component incremental parameter x Z dx and the Y-component incremental parameter d Z dy
  • the following equations (4) and (5) are used to calculate the equations.
  • the parameter calculation method 1 determines whether the pixel is located on either side of the edge. In order to judge whether or not there is an incremental parameter in the X and ⁇ directions of the page function is also calculated.
  • the edge function is calculated for the major edge, minor page 0, and minor edge 1.
  • the triangle type discriminating means 2 uses the sign of the outer product C calculated in the parameter calculating step S ⁇ 2, as shown in FIG. Classify polygon shapes into four types ⁇
  • Fig. 4 shows four types of triangular polygons classified in the type determination step. It is a figure for explaining a shape.
  • the four types of triangular polygons have the following shapes.
  • triangular polygons are classified and classified into four types based on the direction and inclination of the major edge, and are used to determine the moving direction of the pixel in the X and Y directions as shown below.
  • the correspondence between the type of each triangular polygon and the direction of pixel movement is as follows.
  • the start pixel calculation means 3 calculates the start pixel using the incremental parameters calculated in the parameter calculation step ST 2 (see FIG. 3C).
  • the start pixel computes each component value of the center point of the pixel closest to vertex V0 or vertex V1 (sub-pixel collection).
  • the start pixel of the Z component is calculated by the following equation (7).
  • px 0 and py O are the X and Y coordinates of the start pixel, respectively, and both are integer values.
  • step ST5 and step ST6, until the current pixel crosses one major edge (while N is zero in step ST5).
  • step ST6 Interpolate in the X direction (step ST6, see Fig. 3D).
  • the direction in the X direction is determined by the result obtained in the type determination step ST3.
  • the interpolation processing is performed by adding the parameter in the X-direction increment calculated in step ST2.
  • the interpolation processing of the Z component is calculated by the following equation (8).
  • each component value of the pixel is stored (retracted) in M (step ST7).
  • the stored pixel M is a pixel for moving to the next scan line processing.
  • FIG. 5 is a diagram showing a drawing direction of a pixel and a pixel M to be stored. In FIG. 5, circled pixels represent the pixels M to be stored. The determination as to whether or not a major edge has been exceeded can be easily made by determining the sign of the edge function.
  • step ST 8 step ST 9, and step ST 10
  • steps ST9, Step ST10 see Fig. 3E
  • the direction in the X direction is determined based on the determination result obtained in the type determination step ST3.
  • the interpolation process is performed by adding the X-direction increment parameter calculated in step ST2.
  • step ST 11 When the current pixel crosses the minor age (Y E S in step ST 8), and proceeds to step ST 11, the pixel M stored in step ST 7 is recovered, and the pixel M is set as the current pixel. Then, in step ST12 and step ST13, if the Y coordinate of the current pixel does not exceed Y1, interpolation in the Y direction is performed (see FIG. 3F). The direction in the Y direction is determined based on the determination result obtained in the type determination step ST3. The interpolation process is performed by adding the parameter in the Y-direction increment calculated in step ST2. For example, the interpolation processing of the Z component is calculated by the following equation (9).
  • step ST 1 if the Y coordinate of the current pixel exceeds Y 1 (step ST 1
  • pixels are moved according to the classification of triangular polygons in Fig. 4. Determine the direction and interpolate in the X direction from the start pixel closest to vertex V0 or vertex V1. Pixels that have crossed the major edge for the first time are saved, and pixel interpolation and drawing are performed in the X direction until the minor edge 0 or minor edge 1 is exceeded.
  • the pixel M is recovered and interpolated in the Y direction.
  • the pixel M is interpolated in the X direction from the interpolated pixel M. Therefore, when moving to the next scan line, the interpolated voxel M will always be outside the triangular polygon, and will be interpolated in the X direction toward the major edge. Conversely, if the pixel M is interpolated in the Y direction, it will always be outside the triangular polygon, and will be interpolated in the X direction toward the major edge, so that the classification, start pixel, X, Y The direction of movement is determined.
  • the parameters to be calculated for the incremental parameters in the X and Y directions for the various components of the pixel are included.
  • start pixel calculation means 3 for calculating various components of the start pixel closest to vertex V0 or vertex V1
  • start pixel calculation step -Pixels are interpolated in the X direction in order from the pixel to save the pixel M that has crossed the major edge for the first time.
  • a pixel moving means 4 for interpolating the evacuated pixel M in the Y direction to be the start pixel of the next scan line, and a pixel interpolating means 5 (pixel drawing step). Movement directions of pixels can be determined by classifying polygon shapes into four types, eliminating the need for computationally intensive sub-pixel collections and having the effect of efficiently drawing triangular polygons with simple control. Can be
  • the triangle type discriminating means determines that the major edge is on the left side and the X coordinate of the minimum Y coordinate vertex is smaller than the X coordinate of the maximum Y coordinate vertex.
  • the pixel drawing means draws the voxels in the + X and + Y directions in order from the start pixel closest to the minimum Y-vertex, so that the pixels move according to the shape of the triangular polygon. Since the direction can be determined, there is no need for a sub-pixel collection that requires a large amount of computation, and the effect is obtained that triangular polygons can be drawn efficiently with simple control.
  • the triangle type discriminating unit determines that the major polygon is located on the left side and the X coordinate of the minimum Y coordinate vertex is larger than the X coordinate of the maximum Y coordinate vertex
  • the pixel drawing means draws pixels by moving in the + X direction and one Y direction in order from the start pixel closest to the Y coordinate maximum vertex, so the pixel moving direction depends on the shape of the triangular polygon. This makes it possible to determine the number of subpixels, which eliminates the need for computationally intensive subpixel collection, and has the effect of efficiently drawing triangular polygons with simple control.
  • the triangle type discriminating means determines a triangle polygon in which the major edge is on the right side and the X coordinate of the Y coordinate minimum vertex is smaller than the X coordinate of the Y coordinate maximum vertex
  • the pixel drawing means moves pixels in the X direction and the one Y direction in order from the closest pixel to the Y coordinate maximum vertex, so pixels are moved according to the shape of the triangular polygon.
  • the direction can now be determined, eliminating the need for computationally intensive sub-pixel collection, and has the advantage that triangular polygons can be drawn efficiently with simple control.
  • the triangle type discriminating means determines a triangle polygon in which the major edge is on the right side and the X coordinate of the minimum Y coordinate vertex is larger than the X coordinate of the maximum Y coordinate vertex
  • the pixel drawing means draws pixels starting from the start pixel closest to the minimum Y coordinate vertex in the —X and + Y directions, so that the pixel movement direction can be changed according to the shape of the triangular polygon. This makes it possible to make decisions, eliminate the need for computationally intensive sub-pixel collections, and effectively draw triangular polygons with simple control.
  • FIG. 6 is a diagram showing a configuration of a triangular polygon drawing apparatus according to Embodiment 2 of the present invention.
  • the same reference numerals as those in FIG. 2 denote the same or corresponding components.
  • reference numeral 6 denotes a pixel movement direction advance determination means (pixel drawing means), which determines the movement direction of a pixel in advance by performing determination inside or outside a triangular polygon of a pixel in advance. Confuse. ,
  • the operation of the second embodiment is basically the same as that of the first embodiment.
  • the only difference is that the direction of pixel movement is determined in advance by calculating the value of the edge function in advance.
  • the addition of the edge function is processed in advance (for example, one clock ahead), and whether or not a minor edge has been exceeded is determined. It is possible to make a judgment in advance.
  • the value of the edge function is calculated in advance, the inside or outside of the triangular polygon of the pixel is determined in advance, and the pixel moving direction prior determination for determining the moving direction of the pixel in advance is performed.
  • the provision of the means 6 eliminates the need for unnecessary addition processing of pixels in the X and Y directions (such as pixels exceeding the minor edge), and has the effect of further improving the drawing efficiency.
  • the triangular polygon drawing apparatus and the triangular polygon drawing method according to the present invention are suitable for performing image display for performing drawing efficiently with simple control.

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Graphics (AREA)
  • Geometry (AREA)
  • Software Systems (AREA)
  • Image Generation (AREA)

Description

明 細 三角形ポリゴン描画装置および三角形ポリゴン描画方法 技術分野
この発明は、 コンピュータグラフィ クスの画像をディスプレイ上に表 示する技術分野において、 三角形ポリゴンをピクセルに分解して描画す る三角形ポリ ゴン描画装置および三角形ポリゴン描画方法に係るもので める。 背景技術
第 1図 Aは、 従来の三角形ポリゴン描画方法を説明するための図であ る。 この従来の三角形ポリゴン描画方法は、 例えば以下の文献に開示さ れており、 エッジ処理とスパン処理とを繰り返すことによ りビクセルを 生成する。
<文献 >
"C omp u t e r G r ap h i c s P r i n c i p l e s a n d P r a ct i c e S e c o nd E d i t i o n" p p . 8 8 3 - p p . 8 85
J ame s D . F o l e y, And r i e s v an D am, S t e v e n K . F e i n e r , J o hn F. Hu gh e s共著
次に動作について説明する。
第 1図 Bに示すように、 この三角形ポリゴン描画方法は、 セッ トアツ プ処理、 エツジ処理およびスパン処理の 3つの処理に分類される。
まずセヅ トアツプ処理では、 第 1図 Aの左エッジ， 右エッジ， スパン (右エッジと左エッジ間のスキャンライ ン、 カレン トスパン） の増分パ ラメ一夕をピクセルの各種成分について計算する。 ピクセルの各種成分 とは、 デプス値 （ z ) ， カラ一値 （r, g , b, a) ， テクスチャ座標 ( s , t ) などである。 セッ トァヅプ処理は 1つの三角形ポリゴンにつ いて 1回だけ行われる。
次のェヅジ処理では、 セヅ トアツプ処理で求めたェヅジの.増分パラメ —夕を用いて、 左エッジのピクセル P 1 e f tと右エッジのピクセル P r i g h t とを補間処理によ り算出する。 例えば左エッジの X座標は、 次の式 （ 1 ) のようにして、 前回の X座標 X o l dに増分パラメ一夕 Δ X l e f tを加算することによ り計算できる。
Xn ew = X o l d + AX l e f t · · · ( 1 )
スパン処理は、 エッジ処理で求めた左エッジのピクセル P 1 e f t と 右エッジのビクセル P r i g h tとで挟まれたスキャンライ ン方向のピ セルを補間処理によ り順次求めていく。 エッジ処理のときと同様、 次 の式 （ 2 ) のようにして、 X方向増分パラメ一夕を加算することによ り 新しいピクセルを計算できる。
P i =P i— 1 +Δ Ρ χ · · ■ ( 2 )
上記のエツジ処理とスパン処理とを頂点 V 0から頂点 V 1まで繰り返 すことによ り、 三角形ポリゴンを構成する全ピクセルを生成する。
従来の三角形ポリゴン描画装置および三角形ポリゴン描画方法は以上 のよう に構成されているので、 スキャンライ ン更新時に左エッジのピク セル （ Ρ 1 e f t ) を算出するときに、 ピクセルの中心点におけるピク セル値を再計算 （サブピクセルコレクション） しなければならないとい う課題があつた。
サブピクセルコレクションは、 エッジのピクセル値をピクセルの中心 点の値に補正するための処理で、 以下の式 （ 3 ) で表現される。
P 0 =P l e f t + (Χ Ο -X l e f t ) · Δ Ρχ · - · ( 3 ) ここで、 X 0はピクセルの中心点の X座標、 Δ Ρχは X方向のピクセ ル増分パラメ一夕であり、 例えば Ζの場合であれば Z 0 = Z l e f t + (X O -X l e f t ) · Δ Ζ χとなる。 式 （ 3 ) から、 サブピクセルコ レクションには、 加算回路よ り も回路規模が一般に大きい乗算回路が必 要となることが分かる。 サブビクセルコレクショ ンは比較的計算量が多 いため、 スキャンライ ン更新のオーバ一ヘッ ドが非常に大きく、 HZW 量が増大してしまう。
この発明は上記のような課題を解決するためになされたもので、 スキ ヤンライン更新時のサブピクセルコレクショ ンを不要とし、 しかも単純 な制御で効率良く三角形ポリゴンの描画を行うことが可能な三角形ポリ ゴン描画方法を提供することを目的とする。 発明の開示
この発明に係る三角形ポリゴン描画装置は、 三角形ポリ ゴンの頂点座 標デ一夕からメジャーェッジの向きおよび傾きに応じて、 ≡角形の形状 を分類してピクセルの移動方向を決定する三角形タイプ判別手段と、 三 角形タイプ判別手段が決定した移動方向に基づいて、 三角形ポリゴンの 形状の Υ座標最小点または Υ座標最大点に最も近いスター トピクセルか ら順に、 ピクセルを X方向へ補間してメジャーエッジをはじめて越えた ピクセルを退避する とともに、 メジャーエッジからマイナ一エッジまで ピクセルを移動して三角形ポリゴンの 1スキャンライ ンを描画し、 退避 したピクセルを Υ方向へ補間して次のスキャンライ ンのスタートピクセ ルとするピクセル描画手段とを備えたものである。
このことによって、 三角形ポリゴンの形状を 4種類に分類してピクセ ルの移動方向を決定できるようになり、 演算量の多いサブピクセルコレ クシヨンを不要とし、 簡単な制御で効率よ く三角形ポリゴンを描画でき る効果がある。
この発明に係る三角形ポリゴン描画方法は、 三角形ポリゴンの頂点座 標デ一夕からメジャーエッジの向きおよび傾きに応じて、 三角形ポリゴ ンの形状を分類してピクセルの移動方向を決定し、 決定した移動方向に 基づいて、 三角形ポリゴンの Y座標最小頂点または Y座標最大頂点に最 も近いスタート ピクセルから順に、 ピクセルを X方向へ補間してメジャ
—エッジをはじめて越えたビクセルを退避するとともに、 メジャーェヅ ジからマイナ一エッジまでビクセルを移動して三角形ポリゴンの 1スキ ヤンライ ンを描画し、 退避したピクセルを Y方向へ補間して次のスキヤ ンライ ンのスター トピクセルとするようにしたものである。
このことによって、 三角形ポリゴンの形状を 4種類に分類してピクセ ルの移動方向を決定できるようになり、 演算量の多いサブピクセルコレ クシヨンを不要とし、 簡単な制御で効率よ く三角形ポリゴンを描画でき るという効果が得られる。 図面の簡単な説明
第 1図は、 従来の三角形ポリゴン描画方法を説明するための図である 第 2図は、 この発明の実施の形態 1 による三角形ポリゴン描画装置の 構成を示す図である。
第 3図は、 この発明の実施の形態 1 による三角形ポリゴン描画装置の 動作を説明するための図である。
第 4図は、 タイプ判別ステツプで分類する 4種類の三角形ポリゴンの 形状を説明するための図である。
第 5図は、 ピクセルの描画方向と保存されるピクセルとを示す図であ る 第 6図は、 この発明の実施の形態 2による三角形ポリゴン描画装置の 構成を示す図である。 発明を実施するための最良の形態
以下、 この発明をより詳細に説明するために、 この発明を実施するた めの最良の形態について、 添付の図面にしたがって説明する。
実施の形態 1 .
第 2図は、 この発明の実施の形態 1による三角形ポリゴン描画装置の 構成を示す図である。
第 2図において、 1は三角形ポリゴンの頂点データから増分パラメ一 夕を計算するパラメ一夕計算手段、 2はパラメ一夕計算手段 1から三角 形ポリゴンの形状を 4種類に分類する三角形タイプ判別手段、 3はパラ メータ計算手段 1からスタートピクセルを計算するスタートピクセル計 算手段、 4は三角形タイプ判別手段 2の判別結果に応じてピクセルを X 方向または Y方向へ移動させるピクセル移動手段 （ピクセル描画手段） 、 5はピクセル移動手段 4に応じてピクセル値を補間するピクセル補間 手段 （ピクセル描画手段） である。
次に動作について説明する。
第 3図は、 この発明の実施の形態 1による三角形ポリゴン描画装置の 動作 （三角形ポリゴン描画方法） を説明するための図である。
第 3図 Aにおいて、 まず頂点ソートステップ S T 1では、 パラメ一夕 計算手段 1が三角形の頂点のソーティ ングを行う。 このソーティングで は、 Y座標が最小である頂点 （Y座標最小頂点） を V 0 ( X 0 , Y 0 ) ， Y座標が最大である頂点 （Y座標最大頂点） を V 1 ( X I , Y 1 ) ， 残る頂点を V 2 ( X 2 , Y 2 ) となるようにする （第 3図 B参照） 。 な おここでは、 左上を X— Y座標系の原点 0と仮定している。 次のパラメ一夕計算ステップ S T 2では、 パラメ一夕計算手段 1は、 三角形ポリゴンの頂点デ一夕 V 0 , V I , V 2から X方向および Υ方向 の増分パラメ一夕をビクセルの各種成分について計算する。 ピクセルの 各種成分とは、 デプス値 （Ζ ) , カラ一値 （R， G, B， A) ， テクス チヤ座標 （U， V) などである。 例えば頂点 V 0 , V I， V 2の Z値を それそれ z l， z 2 , z 3とすると、 Z成分の X方向増分パラメ一夕 d Z dxおよび Y方向増分パラメ一夕 d Z d yは平面の方程式を利用して 以下の式 （4) ， 式 （ 5 ) で計算される。
d Z dx = { (y l -y O ) · ( z 2 - z 1 )
- ( z l - z 0 ) - (y 2 - y l ) } /C · ■ · ( 4) d Z d y= { ( z l— ζ θ ) · ( x 2 - x 1 )
- (x 1 -x 0 ) · ( z 2 - z 1 ) } /C · · · ( 5 ) ここで、 式 （ 4 ) , 式 （ 5 ) の記号 Cは三角形 V 0 V 1 V 2の外積で あり、 以下の式 （ 6 ) で表される。
C = ( X 2 - X 0 ) · ( 1 - y 0 )
- (x 1 - X 0 ) · ( y 2 - y 0 ) · ■ · ( 6 ) 同様に、 パラメ一夕計算ステップ S T 2において、 パラメ一夕計算手 段 1は、 ピクセルがエッジのどちら側にあるかの判定を行うために、 ェ ヅジファンクションの X方向および Υ方向の増分パラメ一夕の計算も行 う。 エッジファンクションはメジャ一エッジ、 マイナ一ェヅジ 0， マイ ナ一エッジ 1について計算する。
夕ィプ判別ステツプ S Τ 3へ移行すると、 三角形タイ プ判別手段 2は 、 パラメータ計算ステヅプ S Τ 2で計算された外積 Cの符号などを用い て、 次の第 4図に示すように、 三角形ポリゴンの形状を 4種類に分類す る ο
第 4図は、 タイ プ判別ステップで分類する 4種類の三角形ポリゴンの 形状を説明するための図である。 4種類の三角形ポリゴンは以下のよう な形状になつている。
第 4図 Aの三角形ポリゴン T yp e 1
• メジャーエッジが左側にある
-頂点 V 0の X座標が頂点 V 1の X座標より小さい
第 4図 Bの三角形ポリゴン T yp e 2
• メジャ一ェヅジが左側にある
•頂点 V 0の X座標が頂点 V 1の X座標より大きい
第 4図 Cの三角形ポリゴン T y p e 3
- メジャ一ェヅジが右側にある
•頂点 V 0の X座標が頂点 V 1の X座標より小さい
第 4図 Dの三角形ポリゴン T y p e 4
• メジャ一エッジが右側にある
•頂点 V 0の X座標が頂点 V 1の X座標より大きい
つま り、 メジャ一エツジの向きおよび傾きから三角形ポリゴンを 4種 類に分類 ，判別しており、 次に示すように、 ピクセルの X方向および Y 方向の移動方向を決定するために行っている。 各三角形ポリゴンの種類 とピクセルの移動方向 （第 4図 A〜第 4図 D中の矢印で示す） との対応 は以下の通りである。
第 4図 Aの三角形ポリゴン T yp e 1
頂点 V 0から下右の方向 （+ Y方向および + X方向） へピクセルの移動 を行う
第 4図 Bの三角形ポリゴン T yp e 2
頂点 V Iから上右の方向 （一 Y方向および + X方向） へピクセルの移動 を行う
第 4図 Cの三角形ポリゴン T yp e 3 頂点 V Iから上左の方向 （—Y方向および— X方向） へピクセルの移動 を行う
第 4図 Dの三角形ポリゴン T y p e 4
頂点 V Oから下左の方向 （ + Y方向および— X方向） へピクセルの移動 を行う
スタート ピクセル計算ステップ S T 4では、 パラメ一夕計算ステップ S T 2で計算された増分パラメ一夕を使って、 スター トピクセル計算手 段 3がスター ト ピクセルの計算を行う （第 3図 C参照） 。 スター トビク セルは頂点 V 0または頂点 V 1に最も近いピクセルの中心点の各成分値 を計算する （サブピクセルコレクショ ン） 。 例えば Z成分のスタート ピ クセルは以下の式 （ 7 ) で計算される。 なおここで、 px 0， p y Oは 、 それそれスタートピクセルの X座標および Y座標であり、 共に整数値 である。
Z s t a r t = z O + ( p x 0 - 0 ) · d Z d x
+ (p y O -y O ) - d Z d y ■ · · ( 7 ) 次にステップ S T 5およびステップ S T 6において、 カレン トピクセ ルがメジャ一エッジを越えるまで （ステップ S T 5で N 0となる間は） X方向へ補間していく （ステップ S T 6， 第 3図 D参照） 。 X方向の向 きはタイプ判別ステップ S T 3で求めた結果で決定される。 補間処理は ステップ S T 2で計算した X方向増分パラメ一夕を加算することによ り 行う。 例えば、 Z成分の補間処理は以下の式 （ 8 ) で計算される。
Z n ew= Z c u r r e n t +d Z dx · · · ( 8 )
ピクセルがメジャーェヅジを越えたら （ステップ S T 5で Y E Sとな ると） 、 そのピクセルの各成分値を Mに保存 （退避） しておく （ステツ プ S T 7 ) 。 この保存されたピクセル Mは次のスキャンライ ン処理へ移 動するためのピクセルである。 第 5図は、 ピクセルの描画方向と保存されるピクセル Mとを示す図で ある。 第 5図において、 丸印を付したピクセルが保存されるピクセル M を表している。 なお、 メジャ一エッジを越えたかどうかの判断はエッジ ファンクションの符号判定で簡単に行う ことができる。
ステップ S T 8 , ステップ S T 9 , ステップ S T 1 0では、 カレン ト ビクセルがマイナ一エッジ 0またはマイナーエッジ 1を越えるまで （ス テツプ S T 8で N 0の間） X方向へ補間して生成されたピクセルの描画 を行う （ステップ S T 9 , ステップ S T 1 0 , 第 3図 E参照） 。 X方向 の向きはタイプ判別ステップ S T 3で求めた判別結果で決定される。 補 間処理はステップ S T 2で計算した X方向増分パラメ一夕を加算するこ とによ り行う。 これらのステップによ り 1スキャンライ ン分のピクセル の生成と描画を行う ことができる。
カレン トピクセルがマイナーェヅジを越えて （ステップ S T 8で Y E S ) ステップ S T 1 1へ移行すると、 ステップ S T 7で保存されたピク セル Mをリカバリ し、 ピクセル Mをカレン トピクセルとする。 そしてス テツプ S T 1 2およびステップ S T 1 3でそのカレン トピクセルの Y座 標が Y 1を越えていなければ Y方向の補間を行う （第 3図 F参照） 。 Y 方向の向きはタイプ判別ステツプ S T 3で求めた判別結果で決定される 。 補間処理はステップ S T 2で計算された Y方向増分パラメ一夕を加算 することによ り行う。 例えば、 Z成分の補間処理は以下の式 （ 9 ) で計 算 れる。
Z n e w= Z c u r r e n t + d Z d y · · · ( 9 )
一方、 カレン トピクセルの Y座標が Y 1を越えたら （ステップ S T 1
3で Y E S ) 全てのスキャンライ ンについて描画がすんだことになるの で、 そこで三角形の描画を終了する。
このように、 第 4図の三角形ポリゴンの分類に応じてピクセルの移動 方向を決定し、 頂点 V 0 または頂点 V 1 に最も近いスター トピクセルか ら X方向へ補間する。 メジャ一エッジをはじめて越えたビクセル Mは退 避しておき、 マイナ一エッジ 0 またはマイナーエッジ 1 を越えるまで X 方向にピクセルの補間 · 描画処理を行っている。
そしてスキャンライ ン更新の際には、 ピクセル Mをリカバリ して Y方 向へ補間し、 次のスキャンライ ンでは、 この補間したピクセル Mから X 方向へ補間していく。 したがって、 次のスキャンライ ンに移ると、 補間 したビクセル Mは必ず三角形ポリゴンの外側になり、 メジャーエッジへ 向かって X方向へ補間されていく ようになる。 逆に言えば、 ピクセル M を Y方向へ補間すると必ず三角形ポリゴンの外側になり、 メジャ一エツ ジへ向かって X方向に補間されるように、 第 4図の分類、 スター トピク セル、 X， Y方向の移動方向を決めている。
以下、 メジャーェヅジをはじめて越えてからマイナーエッジを越える まで、 X方向へピクセルの補間 ·描画を繰り返すことで （頂点 V I また は頂点 V 0の Y座標を越えるまで補間 · 描画を繰り返す） 、 スキャンラ ィ ン更新の際には単純な加算計算だけですむようになり、 計算量を抑制 でき、 スキャンライ ン更新のォ一パーへッ ドを小さくすることができる ( H /W量を削減できる） 。
以上のよう に、 実施の形態 1 によれば、 三角形ポリゴンの頂点 V 0 , 頂点 V 1および頂点 V 2から、 ピクセルの各種成分に関する X方向およ び Y方向の増分パラメ一夕について計算するパラメ一夕計算手段 1 と （ パラメ一夕計算ステップ） 、 メジャ一エッジの向きおよび傾きに応じて 、 三角形ポリ ゴンの形状を 4種類に分類してピクセルの移動方向を決定 する三角形タイプ判別手段 2 と （三角形タイプ判別ステップ） 、 頂点 V 0 または頂点 V 1 に最も近いスタートピクセルの各種成分を計算するス タートピクセル計算手段 3 と （スタートピクセル計算ステヅプ） 、 ス夕 —トピクセルから順に、 ビクセルを X方向へ補間してメジャ一エッジを はじめて越えたピクセル Mを退避するとともに、 メジャーエッジからマ イナ一エッジ 0またはマイナーェヅジ 1 までピクセルを補間して三角形 ポリゴンの 1スキャンライ ンを描画し、 退避したピクセル Mを Y方向へ 補間して次のスキャンライ ンのスター トピクセルとするピクセル移動手 段 4およびピクセル補間手段 5 (ピクセル描画ステップ） とを備えるよ うにしたので、 三角形ポリゴンの形状を 4種類に分類してピクセルの移 動方向を決定できるようになり、 演算量の多いサブピクセルコレクショ ンを不要とし、 簡単な制御で効率良く三角形ポリゴンを描画できるとい う効果が得られる。
また、 実施の形態 1 によれば、 メジャ一エッジが左側にあり、 Y座標 最小頂点の X座標が Y座標最大頂点の X座標よ り も小さい三角形ポリ ゴ ンを三角形タイ プ判別手段が判別すると、 ピクセル描画手段は、 Y座標 最小頂点に最も近いスタートピクセルから順に、 + X方向および + Y方 向へビクセルを移動して描画するようにしたので、 三角形ポリゴンの形 状に応じてピクセルの移動方向を決定できるようになり、 演算量の多い サブピクセルコレクションを不要とし、 簡単な制御で効率良く三角形ポ リゴンを描画できるという効果が得られる。
さらに、 実施の形態 1 によれば、 メジャ一エッジが左側にあり、 Y座 標最小頂点の X座標が Y座標最大頂点の X座標よ り も大きい≡角形ポリ ゴンを三角形タイプ判別手段が判別すると、 ピクセル描画手段は、 Y座 標最大頂点に最も近いスター トピクセルから順に、 + X方向および一 Y 方向へピクセルを移動して描画するようにしたので、 三角形ポリゴンの 形状に応じてピクセルの移動方向を決定できるようになり、 演算量の多 いサブピクセルコレクションを不要と し、 簡単な制御で効率良く三角形 ポリゴンを描画できるという効果が得られる。 さらに、 実施の形態 1 によれば、 メジャーエッジが右側にあ り、 Y座 標最小頂点の X座標が Y座標最大頂点の X座標よ り も小さい三角形ポリ ゴンを三角形タイプ判別手段が判別すると、 ピクセル描画手段は、 Y座 標最大頂点に最も近いス夕一 トピクセルから順に、 —X方向および一 Y 方向へピクセルを移動して描画するようにしたので、 三角形ポリゴンの 形状に応じてピクセルの移動方向を決定できるようになり、 演算量の多 いサブピクセルコレクションを不要とし、 簡単な制御で効率良く三角形 ポリゴンを描画できるという効果が得られる。
さらに、 実施の形態 1 によれば、 メジャーエッジが右側にあ り、 Y座 標最小頂点の X座標が Y座標最大頂点の X座標よ り も大きい三角形ポリ ゴンを三角形タイプ判別手段が判別すると、 ピクセル描画手段は、 Y座 標最小頂点に最も近いスター トピクセルから順に、 — X方向および + Y 方向へピクセルを移動して描画するようにしたので、 三角形ポリゴンの 形状に応じてピクセルの移動方向を決定できるようになり、 演算量の多 いサブピクセルコレクションを不要とし、 簡単な制御で効率良く三角形 ポリゴンを描画できるという効果が得られる。 実施の形態 2 .
第 6図は、 この発明の実施の形態 2による三角形ポリゴン描画装置の 構成を示す図である。 第 2図と同一符号は同一または相当する構成であ る。
第 6図において、 6はピクセル移動方向先行判断手段 （ピクセル描画 手段） であり、 ビクセルの三角形ポリゴン内部または外部の判定を前も つて行うことによ り、 ピクセルの移動方向をあらかじめ決定するもので める。 ，
この実施の形態 2の動作は実施の形態 1 と基本的に同じ動作であ り、 エッジファンクションの値を前もって計算しておく ことにより、 ピクセ ルの移動方向をあらかじめ決定しておく点のみが異なっている。 つま り 、 エッジファンクションの加算と、 ピクセル （例えば Z値） の加算とを 同時に行うのではなく、 エッジファンクションの加算を前もって （例え ば 1 クロヅク先） 処理するようにし、 マイナ一エッジを越えたかどうか の判定を予め行う ことができるようにする。
ェッジに沿って補間処理を行わずに 1 ピクセル単位でピクセルの移動 および補間を行うので、 スキャンライン更新毎のサブビクセルコレクシ ヨ ンが不要となる。 これによ り複雑な演算処理が不要とな り、 描画速度 を向上することができるばかりでなく、 H ZW量も削減することができ る。
以上のように、 実施の形態 2によれば、 エッジファンクションの値を 前もって計算してピクセルの三角形ポリゴン内部または外部の判定を前 もって行い、 ピクセルの移動方向をあらかじめ決定するピクセル移動方 向先行判断手段 6 を備えるようにしたので、 X方向および Y方向におけ るピクセルの無駄な加算処理 （マイナーエッジを越えてしまう ピクセル など） が不要となり、 描画効率をさらに向上できるという効果が得られ る。 産業上の利用可能性
以上のように、 この発明に係る三角形ポリゴン描画装置および三角形 ポリゴン描画方法は、 単純な制御で効率良く描画を行う画像表示を実施 するのに適している。

Claims

請 求 の 範 囲
1 . 三角形ポリゴンをピクセルに分解して描画する三角形ポリゴン描 画装置において、
三角形ポリ ゴンの頂点座標データからメジャ一エッジの向きおよび傾 きに応じて、 上記三角形の形状を分類して上記ピクセルの移動方向を決 定する三角形タイプ判別手段と、
上記三角形夕ィプ判別手段が決定した移動方向に基づいて、 上記三角 形ポリゴンの形状の Y座標最小点または上記 Y座標最大点に最も近いス 夕一トピクセルから順に、 上記ピクセルを X方向へ補間してメジャーェ ッジをはじめて越えた上記ピクセルを退避するとともに、 上記メジャー エッジからマイナーエツジまで上記ピクセルを移動して上記三角形ポリ ゴンの 1スキャンライ ンを描画し、 上記退避したピクセルを Y方向へ補 間して次のスキヤンライ ンのスタートビクセルとするピクセル描画手段 とを備えることを特徴とする三角形ポリゴン描画装置。
2 . メジャーエッジが左側にあり、 Y座標最小頂点の X座標が Y座標 最大頂点の X座標よ り も小さい三角形ポリゴンを三角形タイプ判別手段 が判別すると、
ピクセル描画手段は、 Y座標最小頂点に最も近いス夕一トピクセルか ら順に、 + X方向および + Y方向へピクセルを移動して描画することを 特徴とする請求の範囲第 1項記載の三角形ポリゴン描画装置。
3 . メジャーエッジが左側にあり、 Y座標最小頂点の X座標が Y座標 最大頂点の X座標よ りも大きい三角形ポリゴンを三角形タイプ判別手段 が判別すると、 ピクセル描画手段は、 Y座標最大頂点に最も近いス夕一トピクセルか ら順に、 + X方向および一 Y方向へピクセルを移動して描画することを 特徵とする請求の範囲第 1項記載の三角形ポリゴン描画装置。
4 . メジャーエッジが右側にあり、 Y座標最小頂点の X座標が Y座標 最大頂点の X座標よりも小さい三角形ポリゴンを三角形タイプ判別手段 が判別すると、
ピクセル描画手段は、 Y座標最大頂点に最も近いスタートピクセルか ら順に、 一 X方向および一 Y方向へピクセルを移動して描画することを 特徴とする請求の範囲第 1項記載の三角形ポリゴン描画装置。
5 . メジャーエッジが右側にあり、 Y座標最小頂点の X座標が Y座標 最大頂点の X座標よ りも大きい三角形ポリゴンを三角形タイプ判別手段 が判別すると、
ピクセル描画手段は、 Y座標最小頂点に最も近いスタートピクセルか ら順に、 一 X方向および + Y方向へピクセルを移動して描画することを 特徴とする請求の範囲第 1項記載の三角形ポリゴン描画装置。
6 . ピクセル描画手段は、 ピクセルの三角形ポリゴン内部または外部 の判定を前もって行い、 ピクセルの移動方向をあらかじめ決定すること を特徴とする請求の範囲第 1項記載の三角形ポリゴン描画装置。
7 . 三角形ポリゴンをピクセルに分解して描画する三角形ポリゴン描 画方法において、
三角形ポリゴンの頂点座標デ一夕からメジャーエッジの向きおよび傾 きに応じて、 上記三角形ポリゴンの形状を分類して上記ビクセルの移動 方向を決定し、
上記決定した移動方向に基づいて、 上記三角形ポリ ゴンの Y座標最小 頂点または上記 Y座標最大頂点に最も近いスター トピクセルから順に、 上記ピクセルを X方向へ補間してメジャーエッジをはじめて越えた上記 ピクセルを退避するとともに、 上記メジャーエッジからマイナーェヅジ まで上記ピクセルを移動して上記三角形ポリゴンの 1スキャンライ ンを 描画し、 上記退避したピクセルを Y方向へ補間して次のスキャンライ ン のスタートピクセルとすることを特徴とする三角形ポリゴン描画方法。
PCT/JP2003/007036 2002-06-03 2003-06-03 Triangle polygon plotting device and triangle polygon plotting method Ceased WO2003102875A1 (en)

Priority Applications (3)

Application Number Priority Date Filing Date Title
US10/483,492 US20040164985A1 (en) 2002-06-03 2003-06-03 Triangle polygon plotting device and triangle polygon plotting method
EP03730808A EP1510971A4 (en) 2002-06-03 2003-06-03 TRIANGULAR POLYGONIC SUPPORT DEVICE AND TRIANGLE POLYGONIC APPLICATION METHOD
KR1020047000460A KR100594555B1 (ko) 2002-06-03 2003-06-03 삼각형 폴리곤 묘화 장치 및 삼각형 폴리곤 묘화 방법

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2002-161925 2002-06-03
JP2002161925A JP3507057B2 (ja) 2002-06-03 2002-06-03 三角形ポリゴン描画装置および三角形ポリゴン描画方法

Publications (1)

Publication Number Publication Date
WO2003102875A1 true WO2003102875A1 (en) 2003-12-11

Family

ID=29706593

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2003/007036 Ceased WO2003102875A1 (en) 2002-06-03 2003-06-03 Triangle polygon plotting device and triangle polygon plotting method

Country Status (6)

Country Link
US (1) US20040164985A1 (ja)
EP (1) EP1510971A4 (ja)
JP (1) JP3507057B2 (ja)
KR (1) KR100594555B1 (ja)
CN (1) CN1294539C (ja)
WO (1) WO2003102875A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN119888006A (zh) * 2024-12-02 2025-04-25 三峡大学 一种基于水下等深线的自动编绘方法

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7800631B2 (en) * 2003-03-18 2010-09-21 Qualcomm Incorporated Triangle rendering using direct evaluation
JP4684744B2 (ja) * 2005-05-27 2011-05-18 三菱電機株式会社 図形描画装置及びプログラム
JP4664169B2 (ja) * 2005-09-26 2011-04-06 三菱電機株式会社 図形描画装置及び図形描画プログラム
KR100742155B1 (ko) 2005-12-30 2007-07-24 엠텍비젼 주식회사 스캔라인 형성 방법 및 장치
JP4621617B2 (ja) * 2006-03-28 2011-01-26 株式会社東芝 図形描画装置、図形描画方法、及びプログラム
US20080218520A1 (en) * 2007-03-09 2008-09-11 Graham Sellers Acceleration of Triangle Scan Conversion Through Minor Direction Detection
JP4568750B2 (ja) * 2007-11-30 2010-10-27 富士通株式会社 描画装置、描画プログラムおよび描画方法
KR101517465B1 (ko) 2007-12-07 2015-05-04 삼성전자주식회사 폴리곤의 특징에 적응된 순서로 래스터화하는 래스터화엔진 및 3차원 그래픽스 시스템
KR100954638B1 (ko) * 2008-04-03 2010-04-27 재단법인서울대학교산학협력재단 벡터 그래픽스 래스터라이제이션 방법
US9633458B2 (en) * 2012-01-23 2017-04-25 Nvidia Corporation Method and system for reducing a polygon bounding box
US8976188B1 (en) 2012-04-20 2015-03-10 Google Inc. Optimized data communication system and method for an image rendering system
US9721363B2 (en) 2014-05-19 2017-08-01 Google Inc. Encoding polygon data for fast retrieval and rendering
KR102354989B1 (ko) * 2015-04-14 2022-01-24 삼성전자주식회사 경로 렌더링을 위한 타일 비닝을 수행하는 방법 및 장치.
KR102618560B1 (ko) 2016-06-15 2023-12-27 삼성전자주식회사 경로 렌더링을 수행하는 방법 및 장치
JP6942964B2 (ja) * 2017-01-17 2021-09-29 カシオ計算機株式会社 図形描画方法、図形描画装置、及びプログラム

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0262619A2 (en) 1986-09-29 1988-04-06 Kabushiki Kaisha Toshiba Shading circuit for shading a plurality of polygons which constitute a solid model, and method of shading the same
US5343558A (en) 1991-02-19 1994-08-30 Silicon Graphics, Inc. Method for scan converting shaded triangular polygons
JPH07105404A (ja) * 1993-10-04 1995-04-21 Ricoh Co Ltd 立体画像処理装置及びその処理方法
JPH087123A (ja) * 1994-06-21 1996-01-12 Nippon Steel Corp 三次元画像処理方法及び装置
JPH08101921A (ja) * 1994-09-30 1996-04-16 Sony Corp 三角形の頂点の並び換え装置
JPH10261107A (ja) * 1997-01-14 1998-09-29 Fujitsu Ltd 輝度補間方法及び装置
JP2001209369A (ja) * 2000-01-25 2001-08-03 Mitsubishi Electric Corp ３次元グラフィック用データの生成方法及び記録媒体

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5136664A (en) * 1988-02-23 1992-08-04 Bersack Bret B Pixel rendering
JPH0710404A (ja) * 1993-06-24 1995-01-13 Otis Elevator Co エレベーターのかご
US5563995A (en) * 1993-12-28 1996-10-08 Matsushita Electric Industrial Co., Ltd. Method and system for directly drawing a convex polygon having a given number of vertices with high speed
US5815166A (en) * 1995-03-24 1998-09-29 3Dlabs Inc., Ltd. Graphics subsystem with slaveable rasterizer
JPH10188003A (ja) * 1996-12-20 1998-07-21 Sony Corp 描画方法および描画装置
US6034699A (en) * 1997-05-01 2000-03-07 Ati Technologies, Inc. Rendering polygons
US6016151A (en) * 1997-09-12 2000-01-18 Neomagic Corp. 3D triangle rendering by texture hardware and color software using simultaneous triangle-walking and interpolation for parallel operation
US6501474B1 (en) * 1999-11-29 2002-12-31 Ati International Srl Method and system for efficient rendering of image component polygons
JP2001273518A (ja) * 2000-03-28 2001-10-05 Toshiba Corp レンダリング装置
JP4581261B2 (ja) * 2001-02-14 2010-11-17 ソニー株式会社 演算装置、演算処理方法及び画像処理装置
US6975317B2 (en) * 2002-03-12 2005-12-13 Sun Microsystems, Inc. Method for reduction of possible renderable graphics primitive shapes for rasterization

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0262619A2 (en) 1986-09-29 1988-04-06 Kabushiki Kaisha Toshiba Shading circuit for shading a plurality of polygons which constitute a solid model, and method of shading the same
US5343558A (en) 1991-02-19 1994-08-30 Silicon Graphics, Inc. Method for scan converting shaded triangular polygons
JPH07105404A (ja) * 1993-10-04 1995-04-21 Ricoh Co Ltd 立体画像処理装置及びその処理方法
JPH087123A (ja) * 1994-06-21 1996-01-12 Nippon Steel Corp 三次元画像処理方法及び装置
JPH08101921A (ja) * 1994-09-30 1996-04-16 Sony Corp 三角形の頂点の並び換え装置
JPH10261107A (ja) * 1997-01-14 1998-09-29 Fujitsu Ltd 輝度補間方法及び装置
JP2001209369A (ja) * 2000-01-25 2001-08-03 Mitsubishi Electric Corp ３次元グラフィック用データの生成方法及び記録媒体

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP1510971A4 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN119888006A (zh) * 2024-12-02 2025-04-25 三峡大学 一种基于水下等深线的自动编绘方法

Also Published As

Publication number Publication date
CN1294539C (zh) 2007-01-10
KR20040028920A (ko) 2004-04-03
EP1510971A4 (en) 2009-11-11
JP2004029864A (ja) 2004-01-29
JP3507057B2 (ja) 2004-03-15
EP1510971A1 (en) 2005-03-02
US20040164985A1 (en) 2004-08-26
KR100594555B1 (ko) 2006-06-30
CN1543627A (zh) 2004-11-03

Similar Documents

Publication Publication Date Title
WO2003102875A1 (en) Triangle polygon plotting device and triangle polygon plotting method
JP5423231B2 (ja) グラフィックラスタライゼーションにおける三角形トラバース方法及び装置
US8059119B2 (en) Method for detecting border tiles or border pixels of a primitive for tile-based rendering
JP3290954B2 (ja) 高速透視図ボリュームレンダリングのための光線変換方法
JPH07210697A (ja) コンピュータグラフィックシステムのサブピクセルマスク発生方法および装置
US8068122B2 (en) Method of image scaling
JP2009545827A (ja) ピクセルマスクを用いたグラフィックシステム
KR20190023846A (ko) 콘텐츠 기반 이미지 리사이징 방법 및 장치
US8179399B2 (en) Rasterizing method
CN103384897A (zh) 地图描绘装置
CN101739703B (zh) 用于对三角形进行栅格化的方法和系统
CN111145299A (zh) 顾及线宽一致性的矢量地图实线符号拐角绘制方法
CN117556955B (zh) 一种基于变异驱动遗传算法的不规则零件二维排布方法
CN111127297A (zh) 顾及线宽一致性的矢量地图实线符号绘制方法
JP7455546B2 (ja) 画像処理装置、画像処理方法、及びプログラム
CN102646281B (zh) 用于对椭圆弧进行栅格化的方法和系统
CN111127589B (zh) 顾及线宽一致性的矢量地图圆形虚线符号绘制方法
CN108564523B (zh) Gpu中一种任意视口变换的实现方法
JP3408176B2 (ja) フォント処理装置、フォント処理方法及び記憶媒体
CN101764935A (zh) 一种基于像素空间掩码矩阵的形态渐变径向色彩填充方法
JP2005128173A (ja) 図形描画装置
JP2001307115A (ja) 画像処理装置および画像処理方法
CN118849679A (zh) 一种轮胎花纹灰度图生成方法及其在轮胎花纹性能分析中的应用和程序产品
JPH10240952A (ja) 図形処理方法並びにその装置
JP2003203230A (ja) 距離算出装置、距離算出方法、画像処理装置および画像処理方法

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): CN KR US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR

WWE Wipo information: entry into national phase

Ref document number: 10483492

Country of ref document: US

Ref document number: 1020047000460

Country of ref document: KR

WWE Wipo information: entry into national phase

Ref document number: 2003730808

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 20038007762

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWP Wipo information: published in national office

Ref document number: 2003730808

Country of ref document: EP