JPH08106521A - Graphic data processing method and graphic data processing device - Google Patents
Graphic data processing method and graphic data processing deviceInfo
- Publication number
- JPH08106521A JPH08106521A JP6241460A JP24146094A JPH08106521A JP H08106521 A JPH08106521 A JP H08106521A JP 6241460 A JP6241460 A JP 6241460A JP 24146094 A JP24146094 A JP 24146094A JP H08106521 A JPH08106521 A JP H08106521A
- Authority
- JP
- Japan
- Prior art keywords
- vertex
- vertices
- peripheral line
- outer peripheral
- predetermined number
- 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.)
- Withdrawn
Links
Landscapes
- Image Generation (AREA)
- Processing Or Creating Images (AREA)
Abstract
(57)【要約】
【目的】 三角形スター構造の図形データを三角形スト
リップ構造の図形データに変換して処理する方法及び装
置を提供することを目的とする。
【構成】 所定番号から１ずつ増加すると共に、“ｎ”
を１以上の整数として場合に、所定番号、（所定番号＋
ｎ）番及び（所定番号＋ｎ＋１）番の頂点からなる三角
形により、図形の内部が重なることなく、かつ過不足な
く分割されるように割り当てられた第一の番号列を、
“ｍ”を整数とした場合に、（ｍ−２）番、（ｍ−１）
番及びｍ番の頂点から形成される三角形と（ｍ−１）
番、ｍ番及び（ｍ＋１）番の頂点からなる三角形とを合
成して形成される四角形により、図形の内部が重なるこ
となく、かつ過不足なく分割されるように割り当てられ
た第二の番号列に変換する。
(57) [Summary] [Object] An object of the present invention is to provide a method and apparatus for converting graphic data having a triangular star structure into graphic data having a triangular strip structure and processing it. [Structure] The number is incremented by 1 from the predetermined number and "n"
Is a predetermined number, (predetermined number +
The first number sequence assigned so that the interiors of the figures are not overlapped and are exactly divided by the triangles having the vertices of (n) th and (predetermined number + n + 1) th,
When "m" is an integer, (m-2) number, (m-1)
Triangle formed from the vertices of the number n and m and (m-1)
A second number sequence allocated so that the insides of the figures do not overlap and are exactly divided by a quadrangle formed by synthesizing a triangle composed of the vertices of the number m, the number m, and the number (m + 1) Convert to.
Description
【０００１】[0001]
【産業上の利用分野】本発明は、独立した三角形に別の
三角形が三角形スターと呼ばれる構造で接続して形成さ
れた図形のデータを、三角形ストリップと呼ばれる構造
で形成された図形のデータに変換する方法と装置に関す
る。BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention converts data of a figure formed by connecting another triangle to an independent triangle in a structure called a triangle star to data of a figure formed in a structure called a triangle strip. Method and apparatus.
【０００２】[0002]
【従来の技術】従来、グラフィック表示装置等では、多
角形図形として扱われる三次元表示物体の座標変換、輝
度計算、クリッピング等の処理を高速に行うため、図５
に示すような三角形ストリップを用いて扱うデータの数
を少なくする方法が採用されている。2. Description of the Related Art Conventionally, in a graphic display device or the like, processing such as coordinate conversion, brightness calculation, and clipping of a three-dimensional display object treated as a polygonal figure is performed at high speed.
A method of reducing the number of data handled by using a triangular strip as shown in FIG.
【０００３】即ち、図５に示す三角形ストリップでは、
頂点２〜７が隣接する２つの三角形に共有され、また頂
点３〜６が隣接する３つの三角形に共有されることによ
りデータの数を少なくしている。That is, in the triangular strip shown in FIG.
The vertices 2 to 7 are shared by two adjacent triangles, and the vertices 3 to 6 are shared by three adjacent triangles, thereby reducing the number of data.
【０００４】このような三角形ストリップからなる図形
は、例えば複数のＣＴ画像から立体像を再構成する場合
に、ＣＴ画像間を補間する図形として利用される。な
お、三角形ストリップとは、図形の頂点に付された頂点
列をＶ0、Ｖ1、Ｖ2、・・・、Ｖnとするときに、
Ｖn-2、Ｖn-1、Ｖnより三角形を構成する図形をいう。A figure consisting of such triangular strips is used as a figure for interpolating between CT images when a stereoscopic image is reconstructed from a plurality of CT images, for example. A triangle strip means that when a vertex row attached to the vertices of a figure is V 0 , V 1 , V 2 , ..., V n ,
A figure that forms a triangle from V n-2 , V n-1 , and V n .
【０００５】[0005]
【発明が解決しようとする課題】ところで、前述の従来
のグラフィック表示装置では、三角形ストリップは高速
に処理されるが、三角形スターと呼ばれる構造の図形
は、高速に処理されない。By the way, in the above-mentioned conventional graphic display device, the triangular strip is processed at high speed, but the graphic of the structure called triangular star is not processed at high speed.
【０００６】ここで、三角形スターとは、図６に示すよ
うに、図形の頂点に付された頂点列をＶ0、Ｖ1、Ｖ2、
・・・、Ｖnとするときに、Ｖ0、Ｖn-1、Ｖnより三角形
を構成する図形をいうが、この三角形スターでは、連続
する一つの三角形を構築するのに、三角形ストリップの
場合と同様、一頂点ずつしかデータが増えない点で三角
形ストリップと共通する。Here, the triangular star means, as shown in FIG. 6, a series of vertices attached to the vertices of a figure by V 0 , V 1 , V 2 ,
.., V n , a figure that forms a triangle from V 0 , V n-1 , and V n . In this triangle star, a triangle strip is used to construct one continuous triangle. Similar to the case, it is common with the triangle strip in that the data increases only one vertex at a time.
【０００７】しかし、従来は、図４に示すように、個々
に独立した三角形（図６の例では、、、、の４
つの三角形）として処理されていたため、高速に描画で
きなかった。However, conventionally, as shown in FIG. 4, individually independent triangles (in the example of FIG. 6, 4 of
It was processed as two triangles), so it could not be drawn at high speed.
【０００８】本発明は、このような事情に鑑みてなされ
たもので、三角形スター構造の図形データを三角形スト
リップ構造の図形データに変換して処理する方法及び装
置を提供することを課題とする。The present invention has been made in view of the above circumstances, and an object of the present invention is to provide a method and apparatus for converting graphic data having a triangular star structure into graphic data having a triangular strip structure for processing.
【０００９】[0009]
＜本発明の第１の図形データ処理方法＞本発明の第１の
図形データ処理方法は、前述した課題を解決するため下
記の如く構成されている。図１は、本発明の原理図であ
る。<First Graphic Data Processing Method of the Present Invention> The first graphic data processing method of the present invention is configured as follows in order to solve the above-mentioned problems. FIG. 1 is a principle diagram of the present invention.
【００１０】即ち、所定番号から図形の各頂点に１つづ
つ増加する番号を割り当ててなる頂点列であり、“ｎ”
を１以上の整数とした場合に、所定番号、（所定番号＋
ｎ）番及び（所定番号＋ｎ＋１）番の頂点から形成され
る三角形により、前記図形の内部を過不足なく分割する
第一の頂点列を、前記図形の各頂点に割り当ててなる別
の頂点列であり、“ｍ”を整数とした場合に、（ｍ−
２）番、（ｍ−１）番及びｍ番の頂点から形成される三
角形と（ｍ−１）番、ｍ番及び（ｍ＋１）番の頂点から
形成される三角形とを合成して形成される四角形によ
り、前記図形の内部を過不足なく分割する第二の頂点列
に変換して処理することを含むことを特徴とする（請求
項１に対応）。 ＜本発明の第２の図形データ処理方法＞本発明の第２の
図形データ処理方法は、前述した課題を解決するため下
記の如く構成されている。That is, it is a vertex string in which a number which is incremented by one from each of the predetermined numbers is assigned to each vertex of the figure.
Is a predetermined number, (predetermined number +
A first vertex row that divides the inside of the figure without excess or deficiency by a triangle formed by the nth and (predetermined number + n + 1) vertices is a different vertex row that is assigned to each vertex of the figure. Yes, when "m" is an integer, (m-
2), triangles formed from (m-1) th and mth vertices and triangles formed from (m-1) th, mth and (m + 1) th vertices are formed by combining It is characterized by including processing by converting the inside of the figure into a second vertex row that divides the inside of the figure by just a quadrangle without excess or shortage (corresponding to claim 1). <Second Graphic Data Processing Method of the Present Invention> A second graphic data processing method of the present invention is configured as follows in order to solve the above-mentioned problems.
【００１１】即ち、前記第一の頂点列が付された頂点間
の各辺に割り当てられたフラグである第一の外周線フラ
グを、前記第二の頂点列が付された頂点間の各辺に割り
当てられたフラグである第二の外周線フラグに変換して
処理することを特徴とする（請求項２に対応）。 ＜本発明の第３の図形データ処理方法＞本発明の第３の
図形データ処理方法は、前述した課題を解決するため下
記の如く構成されている。図２は、本発明の原理図であ
る。That is, the first peripheral line flag, which is a flag assigned to each side between the vertices to which the first vertex row is attached, is set to the each edge between the vertices to which the second vertex row is attached. It is characterized in that it is converted into a second outer peripheral line flag which is a flag assigned to (1) and processed (corresponding to claim 2). <Third Graphic Data Processing Method of the Present Invention> A third graphic data processing method of the present invention is configured as follows in order to solve the above-mentioned problems. FIG. 2 is a principle diagram of the present invention.
【００１２】即ち、所定番号から図形の各頂点に１つづ
つ増加する番号を割り当ててなる頂点列であり、“ｎ”
を１以上の整数とした場合に、所定番号、（所定番号＋
ｎ）番及び（所定番号＋ｎ＋１）番の頂点から形成され
る三角形により、前記図形の内部を過不足なく分割する
ように割り当てられた第一の頂点列を、前記図形の各頂
点に割り当ててなる別の頂点列であり、“ｍ”を整数と
した場合に、（ｍ−２）番、（ｍ−１）番及びｍ番の頂
点から形成される三角形により、前記図形の内部を過不
足なく分割する第二の頂点列に変換して処理することを
特徴とする（請求項３に対応）。 ＜本発明の第４の図形データ処理方法＞本発明の第４の
図形データ処理方法は、前述した課題を解決するため下
記の如く構成されている。That is, it is a vertex sequence in which a number that is incremented by one is assigned to each vertex of the figure from a predetermined number, and "n"
Is a predetermined number, (predetermined number +
A first vertex row allocated so as to divide the inside of the figure without excess or deficiency by a triangle formed from the nth and (predetermined number + n + 1) vertices is assigned to each vertex of the figure. It is another vertex sequence, and when "m" is an integer, the triangle formed from the vertices of (m-2) th, (m-1) th and mth is used to ensure that the inside of the figure is not excessive or deficient. It is characterized in that it is converted into a second vertex sequence to be divided and processed (corresponding to claim 3). <Fourth Graphic Data Processing Method of the Present Invention> A fourth graphic data processing method of the present invention is configured as follows in order to solve the above-mentioned problems.
【００１３】即ち、第３の図形データ処理方法におい
て、前記第一の頂点列が付された頂点間の各辺に割り当
てられたフラグである第一の外周線フラグを、前記第二
の頂点列が付された頂点間の各辺に割り当てられたフラ
グである第二の外周線フラグに変換して処理することを
特徴とする（請求項４に対応）。 ＜本発明の第１の図形データ処理装置＞本発明の第１の
図形データ処理装置は、前述した課題を解決するため下
記の如く構成されている。図３は、本発明の原理図であ
る。That is, in the third graphic data processing method, the first peripheral line flag, which is a flag assigned to each side between the vertices to which the first vertex line is added, is set to the second vertex line. It is characterized by converting into a second outer peripheral line flag which is a flag assigned to each side between vertices marked with and processing (corresponding to claim 4). <First Graphic Data Processing Device of the Present Invention> A first graphic data processing device of the present invention is configured as follows in order to solve the problems described above. FIG. 3 is a principle diagram of the present invention.
【００１４】即ち、所定番号から図形の各頂点に１つづ
つ増加する割り当ててなる頂点列であり、“ｎ”を１以
上の整数とした場合に、所定番号、（所定番号＋ｎ）番
及び（所定番号＋ｎ＋１）番の頂点から形成される三角
形により、前記図形の内部を過不足なく分割する第一の
頂点列を、図形データ格納部１０から入力し、前記図形
の各頂点に割り当ててなる別の頂点列であり、“ｍ”を
整数とした場合に、（ｍ−２）番、（ｍ−１）番及びｍ
番の頂点から形成される三角形と（ｍ−１）番、ｍ番及
び（ｍ＋１）番の頂点から形成される三角形とを合成し
て形成される四角形により、前記図形の内部を過不足な
く分割する第二の頂点列に変換する頂点データ変換部２
１と、この頂点データ変換部２１により変換された第二
の頂点列を、三角形ストリップを描画する機能を有する
図形描画部３０に出力する変換データ出力部２２とを備
えたことを特徴とする（請求項５に対応）。That is, it is a row of vertices that is assigned by incrementing from the predetermined number to each vertex of the figure by one. When "n" is an integer of 1 or more, the predetermined number, (predetermined number + n) number and (predetermined number) A first vertex row that divides the inside of the figure without excess or deficiency by a triangle formed from the predetermined number + n + 1) vertices is input from the figure data storage unit 10 and assigned to each vertex of the figure. (M-2) number, (m-1) number, and m when "m" is an integer.
The inside of the figure is exactly divided by a quadrangle formed by synthesizing a triangle formed from the vertices of No. and a triangle formed from the vertices of (m−1) th, mth and (m + 1) th Vertex data conversion unit 2 for converting into a second vertex sequence
1 and a conversion data output unit 22 for outputting the second vertex array converted by the vertex data conversion unit 21 to a graphic drawing unit 30 having a function of drawing a triangle strip ( (Corresponding to claim 5).
【００１５】ここで、図形データ格納部１０は、例え
ば、ＲＯＭ（Read Only Memory；読み出し専用記憶装
置）、半導体記憶装置、磁気ディスク記憶装置、フレキ
シィブル装置、磁気テープ装置、ＣＤ−ＲＯＭ（Compac
t Disc ROM；光学的記憶装置）、Ｍ／Ｏ（Magnet Optic
al；光磁気ディスク装置）等を利用することができる。The graphic data storage unit 10 is, for example, a ROM (Read Only Memory), a semiconductor storage device, a magnetic disk storage device, a flexible device, a magnetic tape device, a CD-ROM (Compac).
t Disc ROM: Optical storage device, M / O (Magnet Optic
al; magneto-optical disk device) or the like can be used.
【００１６】また、頂点データ変換部２１は、ＣＰＵ
（Central Processing Unit ；中央演算処理装置）で実
行されるソフトウェアによって実現することができる。 ＜本発明の第２の図形データ処理装置＞本発明の第２の
図形データ処理装置は、前述した課題を解決するため下
記の如く構成されている。図３は、本発明の原理図であ
る。The vertex data conversion unit 21 is a CPU
It can be realized by software executed by (Central Processing Unit). <Second Graphic Data Processing Device of the Present Invention> A second graphic data processing device of the present invention is configured as follows in order to solve the above-mentioned problems. FIG. 3 is a principle diagram of the present invention.
【００１７】即ち、所定番号から図形の各頂点に１つづ
つ増加する番号を割り当ててなる頂点列であり、“ｎ”
を１以上の整数とした場合に、所定番号、（所定番号＋
ｎ）番及び（所定番号＋ｎ＋１）番の頂点から形成され
る三角形により、前記図形の内部を過不足なく分割する
ように割り当てられた第一の頂点列を、図形データ格納
部１０から入力し、前記図形の各頂点に割り当ててなる
別の頂点列であり、“ｍ”を整数とした場合に、（ｍ−
２）番、（ｍ−１）番及びｍ番の頂点から形成される三
角形により、前記図形の内部を過不足なく分割する第二
の頂点列に変換する頂点データ変換部２１と、この頂点
データ変換部２１により変換された第二の頂点列を、三
角形ストリップを描画する機能を有する図形描画部３０
に出力する変換データ出力部２２とを備えたことを特徴
とする（請求項６に対応）。That is, it is a vertex sequence in which a number that is incremented by one is assigned to each vertex of the figure from a predetermined number, and "n"
Is a predetermined number, (predetermined number +
From the figure data storage unit 10, a first vertex row allocated so as to divide the inside of the figure without excess or deficiency by a triangle formed from the n) th and (predetermined number + n + 1) th vertices, It is another vertex string assigned to each vertex of the figure, and when "m" is an integer, (m-
A vertex data conversion unit 21 for converting the inside of the figure into a second vertex sequence that divides the inside of the figure without excess or deficiency by a triangle formed from the 2) th, (m-1) th and the mth vertices, and this vertex data. The graphic drawing unit 30 having a function of drawing a triangular strip from the second vertex array converted by the converting unit 21.
And a converted data output unit 22 for outputting the data (corresponding to claim 6).
【００１８】ここで、図形データ格納部１０は、例え
ば、ＲＯＭ、半導体記憶装置、磁気ディスク記憶装置、
フレキシィブル装置、磁気テープ装置、ＣＤ−ＲＯＭ、
Ｍ／Ｏ等を利用することができる。Here, the graphic data storage unit 10 is, for example, a ROM, a semiconductor memory device, a magnetic disk memory device,
Flexible device, magnetic tape device, CD-ROM,
M / O or the like can be used.
【００１９】また、頂点データ変換部２１は、ＣＰＵで
実行されるソフトウェアによって実現することができ
る。Further, the vertex data conversion unit 21 can be realized by software executed by the CPU.
【００２０】[0020]
【作用】本発明の第１及び第２の図形データ処理方法に
よれば、第一の頂点列が、第二の頂点列に変換して処理
される。変換された第二の頂点列は、三角形ストリップ
構造をなすため高速に描画可能である。つまり、三角形
スター構造をなす第一の頂点列の図形が高速に描画され
るようになる。According to the first and second graphic data processing methods of the present invention, the first vertex row is converted into the second vertex row and processed. The converted second vertex array has a triangular strip structure, and thus can be drawn at high speed. That is, the figure of the first vertex row forming the triangular star structure can be drawn at high speed.
【００２１】また、本発明の第３及び第４の図形データ
処理方法によれば、三角形スター構造をなす図形の外周
線フラグが、三角形ストリップ構造をなす図形の外周線
フラグに変換して処理される。Further, according to the third and fourth graphic data processing methods of the present invention, the peripheral line flag of the graphic having the triangular star structure is converted into the peripheral line flag of the graphic having the triangular strip structure and processed. It
【００２２】そして、本発明の第１及び第２の図形デー
タ処理装置によれば、頂点データ変換部２１により、第
一の頂点列が第二の頂点列に変換される。次に、変換デ
ータ出力部２２により、図形描画部３０に出力される。
つまり、第１及び第２の図形データ処理方法と同様に、
三角形スター構造をなす第一の頂点列の図形が高速に描
画されるようになる。Then, according to the first and second graphic data processing devices of the present invention, the vertex data conversion unit 21 converts the first vertex row into the second vertex row. Next, the converted data output unit 22 outputs the converted data to the graphic drawing unit 30.
That is, like the first and second graphic data processing methods,
The figure of the first vertex row forming the triangular star structure can be drawn at high speed.
【００２３】[0023]
【実施例】以下、本発明の実施例を図面を参照して説明
する。Embodiments of the present invention will be described below with reference to the drawings.
【００２４】[0024]
【第１実施例】 ＜構成＞図９は、本発明の第１実施例の構成ブロック図
である。First Embodiment <Structure> FIG. 9 is a structural block diagram of a first embodiment of the present invention.
【００２５】図９では、三角形リスト構造で表現された
図形データを格納した図形データ格納部１０と、この図
形データ格納部１０から入力した図形データが三角形ス
ター形式である場合に、三角形ストリップ形式に変換す
る三角形リスト処理部２０と、独立三角形及び三角形ス
トリップ形式の図形を描画する図形描画部３０とが備え
られている。In FIG. 9, when the graphic data storage unit 10 storing the graphic data represented by the triangle list structure and the graphic data input from the graphic data storage unit 10 is in the triangular star format, the triangular strip format is used. A triangle list processing unit 20 for converting and a graphic drawing unit 30 for drawing a graphic in the independent triangle and triangle strip formats are provided.
【００２６】以下、各構成要素について詳細に説明す
る。 〔図形データ格納部１０〕図形データ格納部１０には、
三角形リストで表現された図形データが、図１０に示す
形式で格納されている。即ち、三角形リスト要素のヘッ
ダと、頂点数と、頂点１からＮの各々のデータとを格納
している。なお、頂点１から３のデータは、常に独立三
角形となるように選ばれている。ここで、図形データの
具体例を、図６を参照して説明する。まず、頂点数には
“６”が、頂点１から６のデータには、番号“１”から
“６”が付された頂点のデータが格納される。Hereinafter, each component will be described in detail. [Graphic Data Storage Unit 10] The graphic data storage unit 10 includes
The graphic data represented by the triangle list is stored in the format shown in FIG. That is, the header of the triangle list element, the number of vertices, and each data of vertices 1 to N are stored. The data of the vertices 1 to 3 are selected so that they are always independent triangles. Here, a specific example of the graphic data will be described with reference to FIG. First, "6" is stored in the number of vertices, and the data of the vertices 1 to 6 stores the data of the vertices numbered "1" to "6".
【００２７】そして、各頂点のデータは、座標と、頂点
色と、頂点法線と、頂点フラグとで構成されている。こ
のうち、頂点色、頂点法線、頂点フラグは、必ずしもデ
ータが用意されている訳ではなく、必要に応じ値が設定
されている。また、頂点フラグは、ダミーエリアと、
（ａ）（ｎ−２）頂点間の外周線フラグ（１ビット）
と、（ｂ）（ｎ−１）頂点間の外周線フラグ（１ビッ
ト）と、（ｃ）三角形形状フラグ（２ビット）とで構成
されている。The data of each vertex is composed of coordinates, vertex colors, vertex normals, and vertex flags. Of these, data is not necessarily prepared for the vertex color, the vertex normal, and the vertex flag, and values are set as necessary. Also, the vertex flag is a dummy area,
(A) (n-2) Perimeter line flag between vertices (1 bit)
And (b) (n-1) outer peripheral line flag between vertices (1 bit) and (c) triangular shape flag (2 bits).
【００２８】（ａ）（ｎ−２）頂点間の外周線フラグと
は、“（ｎ−２）”番の頂点と“ｎ”番の頂点間の外周
線が有るか無いかを示すフラグである（有る場合は
“１”で、無い場合は“０”）。図７の（ａ）で説明す
ると、例えば“１”番の頂点と“３”番の頂点間には外
周線があるから“１”となるが、“３”番の頂点と
“５”番の頂点間には外周線がないから“０”となる。The (a) (n-2) outer peripheral line flag between vertices is a flag indicating whether or not there is an outer peripheral line between the "(n-2)" vertex and the "n" vertex. Yes (“1” if yes, “0” if no). Explaining with reference to FIG. 7A, for example, since there is an outer peripheral line between the "1" vertex and the "3" vertex, it becomes "1", but the "3" vertex and the "5" vertex Since there is no peripheral line between the vertices of, the value is "0".
【００２９】（ｂ）（ｎ−１）頂点間の外周線フラグと
は、“（ｎ−１）”番の頂点と“ｎ”番の頂点間の外周
線が有るか無いかを示すフラグである（有る場合は
“１”で、無い場合は“０”）。図７の（ａ）で説明す
ると、例えば“２”番の頂点と“３”番の頂点間には外
周線があるから“１”となる。(B) The outer peripheral line flag between (n-1) vertices is a flag indicating whether or not there is an outer peripheral line between the "(n-1)" vertex and the "n" vertex. Yes (“1” if yes, “0” if no). Explaining with reference to FIG. 7A, for example, since there is an outer peripheral line between the "2" vertex and the "3" vertex, it becomes "1".
【００３０】（ｃ）三角形形状フラグとは、図形の種別
によって下記の（イ）から（ハ）のいずれかを示すフラ
グである。ただし、頂点列は、“０”番から１づつ増加
する番号が割り当てられているものとする。 （イ）“ｎ”番の頂点と“（ｎ＋１）”番の頂点と
“（ｎ＋２）”番の頂点より三角形が構成される場合、
独立三角形を示す値“００”をとる。 （ロ）“（ｎ−２）”番の頂点と“（ｎ−１）”番の頂
点と“ｎ”番の頂点より三角形が構成される場合、三角
形ストリップを示す値“０１”をとる。 （ハ）“０”番の頂点と“（ｎ−１）”番の頂点と
“ｎ”番の頂点より三角形が構成される場合、三角形ス
トリップを示す値“１０”をとる。(C) The triangular shape flag is a flag indicating any one of the following (a) to (c) depending on the type of figure. However, it is assumed that the vertex row is assigned a number that is incremented by 1 from "0". (A) In the case where a triangle is composed of the “n” vertex, the “(n + 1)” vertex and the “(n + 2)” vertex,
The value "00" indicating an independent triangle is taken. (B) When a triangle is composed of "(n-2)" vertices, "(n-1)" vertices, and "n" vertices, the value "01" indicating a triangle strip is taken. (C) When a triangle is composed of the "0" vertex, the "(n-1)" vertex and the "n" vertex, the value "10" indicating the triangle strip is taken.
【００３１】〔三角形リスト処理部２０〕三角形リスト
処理部２０の内部は、下記の（１）〜（３）からなる。 （１−ａ）頂点列を含む頂点データの変換を行う頂点デ
ータ変換部２１。 （１−ｂ）頂点データ変換部２１より入力した三角形ス
ターの頂点データを２つの三角形よりなる三角形ストリ
ップ群の頂点データに変換する第１のストリップ頂点デ
ータ変換処理部２５ａ。 （１−ｃ）現在何番目のストリップを処理しているかと
いう情報を格納するストリップ分割番号テーブル２３。 （１−ｄ）頂点データの変換方法に関する情報を格納す
る第１の頂点データ変換テーブル２６ａ。 （２−ａ）外周線データの付け替えを行う外周線変換部
２７。 （２−ｂ）外周線変換部２７より外周線データを入力し
て、三角形ストリップ用の外周線データを変換する第１
のストリップ用外周線変換部２８ａ。 （２−ｃ）外周線データの変換方法に関する情報を格納
する第１の外周線変換テーブル２９ａ。 （３−ａ）第１のストリップ頂点データ変換処理部２５
ａ及び第１のストリップ用外周線変換部２８ａが変換し
た情報を格納するストリップデータ格納部２４。 （３−ｂ）ストリップデータ格納部２４に格納された情
報を図形描画部３０に送出するストリップデータ送出部
２２。[Triangle List Processing Unit 20] The inside of the triangle list processing unit 20 is composed of the following (1) to (3). (1-a) A vertex data conversion unit 21 that converts vertex data including a vertex row. (1-b) A first strip vertex data conversion processing unit 25a for converting the vertex data of the triangular star input from the vertex data conversion unit 21 into the vertex data of the triangle strip group consisting of two triangles. (1-c) A strip division number table 23 that stores information on which strip is currently processed. (1-d) A first vertex data conversion table 26a that stores information regarding a method of converting vertex data. (2-a) An outer peripheral line conversion unit 27 that replaces outer peripheral line data. (2-b) First, inputting outer peripheral line data from the outer peripheral line converting unit 27 to convert the outer peripheral line data for the triangle strip.
Outer peripheral line converting portion 28a for strip. (2-c) A first outer peripheral line conversion table 29a that stores information regarding a method of converting outer peripheral line data. (3-a) First strip vertex data conversion processing unit 25
a and the strip data storage unit 24 that stores the information converted by the first strip outer peripheral line conversion unit 28a. (3-b) The strip data transmission unit 22 that transmits the information stored in the strip data storage unit 24 to the graphic drawing unit 30.
【００３２】以下、各構成要素を説明する。 （頂点データ変換部２１、第１のストリップ頂点データ
変換処理部２５ａ）第１のストリップ頂点データ変換処
理部２５ａは、ストリップ分割番号テーブル２３と第１
の頂点データ変換テーブル２６ａを変換時に参照する。Each component will be described below. (Vertex data conversion unit 21, first strip vertex data conversion processing unit 25a) The first strip vertex data conversion processing unit 25a includes the strip division number table 23 and the first
The vertex data conversion table 26a of is referred to at the time of conversion.
【００３３】第１の頂点データ変換テーブル２６ａは、
具体的には、表１のように構成されている。この表１を
参照して、図１（ａ）に示す三角形スターの頂点列を図
１（ｂ）（ｃ）に示す三角形ストリップの頂点列に変換
する方法を説明する。The first vertex data conversion table 26a is
Specifically, it is configured as shown in Table 1. A method for converting the vertex array of the triangular star shown in FIG. 1A into the vertex array of the triangular strip shown in FIGS. 1B and 1C will be described with reference to Table 1.
【００３４】[0034]
【表１】 まず、図１（ｂ）に示す三角形ストリップ群の４つの頂
点“１”、“２”、“３”及び“４”は、１番目にでき
る三角形ストリップであるから、それぞれ図１（ａ）の
“２”番、“３”番、“１”番及び“４”番の頂点から
構成される。[Table 1] First, the four vertices “1”, “2”, “3” and “4” of the triangle strip group shown in FIG. 1B are the first triangle strips. It is composed of "2", "3", "1" and "4" vertices.
【００３５】次に、図１（ｃ）に示す三角形ストリップ
群の４つの頂点“５”、“６”、“７”及び“８”は、
２番目にできる三角形ストリップであるから、それぞれ
図１（ａ）の“４”番、“５”番、“１”番及び“６”
番の頂点から構成される。Next, the four vertices "5", "6", "7" and "8" of the triangular strip group shown in FIG.
Since it is the second triangular strip, it is the "4", "5", "1" and "6" in FIG. 1 (a), respectively.
It consists of the top of the number.
【００３６】（外周線変換部２７、第１のストリップ用
外周線変換部２８ａ）第１のストリップ用外周線変換部
２８ａは、第１の外周線変換テーブル２９ａを変換時に
参照する。(Outer peripheral line conversion unit 27, first outer peripheral line conversion unit 28a) The first strip outer peripheral line conversion unit 28a refers to the first outer peripheral line conversion table 29a during conversion.
【００３７】第１の外周線変換テーブル２９ａは、具体
的には、表２及び表３のように構成されている。表２及
び表３を参照して、図７（ａ）に示す三角形スターの外
周線を図７（ｂ）に示す三角形ストリップの外周線に変
換する方法を説明する。The first outer peripheral line conversion table 29a is specifically constructed as shown in Tables 2 and 3. A method of converting the outer peripheral line of the triangular star shown in FIG. 7A into the outer peripheral line of the triangular strip shown in FIG. 7B will be described with reference to Tables 2 and 3.
【００３８】[0038]
【表２】 まず、図７（ｂ）に示す三角形ストリップ群は、１番目
にできる三角形ストリップであるから、表２に従って、
次のように変換される。[Table 2] First, since the triangle strip group shown in FIG. 7B is the first triangle strip, according to Table 2,
It is converted as follows.
【００３９】“１”番の頂点については、この番号より
若い番号との間に外周線が引けないため、変換を考慮し
なくて良い。“２”番の頂点については、“１”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの３頂点目の（ｎ−１）頂点間外周線（３-1）（図
７（ａ）参照）となる。Regarding the apex of "1", the outer peripheral line cannot be drawn between the number and a number smaller than this number, so it is not necessary to consider the conversion. A peripheral line can be drawn between the "2" apex and the "1" apex, but this peripheral line is the (n-1) inter-apex outer peripheral line (3 -1 ) of the third apex of the triangular star. ) (See FIG. 7A).
【００４０】“３”番の頂点については、“２”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの３頂点目の（ｎ−２）頂点間外周線（３-2）（図
７（ａ）参照）となる。また、“１”番の頂点との間に
外周線が引けるが、この外周線は、三角形スターの２頂
点目の（ｎ−１）頂点間外周線（２-1）（図７（ａ）参
照）となる。An outer peripheral line can be drawn between the "3" apex and the "2" apex, and this outer peripheral line is the outer peripheral line between the (n-2) apexes of the third apex of the triangular star ( 3 -2 ) (see FIG. 7A). Also, an outer peripheral line can be drawn between the apex of "1", but this outer peripheral line is the outer peripheral line (2 -1 ) between the (n-1) apexes of the second apex of the triangular star (Fig. 7 (a)). (See).
【００４１】“４”番の頂点については、“３”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの４頂点目の（ｎ−２）頂点間外周線（４ー2）（図
７（ａ）参照）となる。また、“２”番の頂点との間に
外周線が引けるが、この外周線は、三角形スターの４頂
点目の（ｎ−１）頂点間外周線（４ー1）（図７（ａ）参
照）となる。A peripheral line can be drawn between the "4" vertex and the "3" vertex, but this peripheral line is the (n-2) inter-vertical peripheral line (n-2) at the fourth vertex of the triangular star. 4-2 ) (see FIG. 7A). Further, "2" number but can be subtracted peripheral line between the apex of the outer peripheral line of the triangle Stars 4 vertices th (n-1) vertices between peripheral line (4-1) (FIGS. 7 (a) (See).
【００４２】[0042]
【表３】 まず、図７（ｃ）に示す三角形ストリップ群は、２番目
にできる三角形ストリップであるから、表３に従って、
次のように変換される。[Table 3] First, since the triangular strip group shown in FIG. 7C is the second triangular strip group, according to Table 3,
It is converted as follows.
【００４３】“５”番の頂点については、この番号より
若い番号との間に外周線が引けないため、変換を考慮し
なくて良い。“６”番の頂点については、“５”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの５頂点目の（ｎ−１）頂点間外周線（５-1）（図
７（ａ）参照）となる。Regarding the apex of "5", since an outer peripheral line cannot be drawn between the number and a number smaller than this number, the conversion need not be considered. The apex of the "6" th, "5" th but can be subtracted peripheral line between the apex of the outer peripheral line of the triangle Stars 5 vertices th (n-1) vertices between peripheral line (5 -1 ) (See FIG. 7A).
【００４４】“７”番の頂点については、“６”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの５頂点目の（ｎ−２）頂点間外周線（５ー2）（図
７（ａ）参照）となる。また、“５”番の頂点との間に
外周線が引けるが、この外周線は、三角形スターの４頂
点目の（ｎ−２）頂点間外周線（４ー2）（図７（ａ）参
照）となる。An outer peripheral line can be drawn between the apex of "7" and the apex of "6", but this outer peripheral line is the outer peripheral line between the (n-2) apexes of the fifth apex of the triangular star ( 5-2 ) (see FIG. 7 (a)). Further, "5" th but can be subtracted peripheral line between the apex of the outer peripheral line of the triangle star 4 vertices th (n-2) between vertices peripheral line (4-2) (FIGS. 7 (a) (See).
【００４５】“８”番の頂点については、“７”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの６頂点目の（ｎ−２）頂点間外周線（６ー2）（図
７（ａ）参照）となる。また、“６”番の頂点との間に
外周線が引けるが、この外周線は、三角形スターの６頂
点目と（ｎ−１）頂点間外周線（６ー1）（図７（ａ）参
照）となる。An outer peripheral line can be drawn between the apex of "8" and the apex of "7", and this outer peripheral line is the outer peripheral line between the (n-2) apexes of the sixth vertex of the triangular star ( 6-2 ) (see FIG. 7 (a)). Further, "6" number but can be subtracted peripheral line between the apex of the outer peripheral line, 6 vertices th triangle star and (n-1) vertices between peripheral line (6-1) (FIGS. 7 (a) (See).
【００４６】＜三角形リスト処理部２０の動作＞次に、
図１１を参照して三角形リスト処理部２０の動作を説明
する。まず、図形データ格納部１０から図形データが入
力されると、「三角形スター」、「三角形ストリッ
プ」、及び「独立三角形」のいずれに該当するかが形状
判定される（ステップ１１０１）。<Operation of Triangle List Processing Unit 20> Next,
The operation of the triangle list processing unit 20 will be described with reference to FIG. First, when the graphic data is input from the graphic data storage unit 10, the shape of the “triangle star”, the “triangle strip”, or the “independent triangle” is determined (step 1101).
【００４７】ステップ１１０１で、「三角形ストリッ
プ」と判定された場合は、図示していない三角形ストリ
ップ処理部に処理が移る（ステップ１１０３）。また、
ステップ１１０１で「独立三角形」と判定された場合
は、図示していない独立三角形処理部に処理が移る（ス
テップ１１０４）。If it is determined in step 1101 that the "triangle strip" is present, the process proceeds to a triangle strip processing unit (not shown) (step 1103). Also,
If it is determined as "independent triangle" in step 1101, the process moves to an independent triangle processing unit (not shown) (step 1104).
【００４８】そして、ステップ１１０１で「三角形スタ
ー」と判定された場合は、２つのストリップ分のデータ
を読み込む（ステップ１１０２）。そして、１番目のス
トリップか否かを判断する（ステップ１１０５）。Then, if it is determined in step 1101 that it is a "triangle star", data for two strips is read (step 1102). Then, it is determined whether or not it is the first strip (step 1105).
【００４９】ステップ１１０５で、ＹＥＳ（＝１番目の
ストリップ）と判断された場合、更に、外周線データ付
きか否かを判断する（ステップ１１０６）。ステップ１
１０６で、ＹＥＳ（＝外周線データ付き）と判断された
場合、第１の外周線変換テーブル２９ａの１番目にでき
るストリップの表により、外周線データを付け替える
（ステップ１１０７）。When it is judged YES (= 1st strip) in step 1105, it is further judged whether or not outer peripheral line data is included (step 1106). Step 1
When it is determined to be YES (= with outer peripheral line data) in 106, the outer peripheral line data is replaced according to the first strip table in the first outer peripheral line conversion table 29a (step 1107).
【００５０】ステップ１１０６で、ＮＯ（＝外周線デー
タが付いていない）と判断された場合及びステップ１１
０７の後に、第１の頂点データ変換テーブル２６ａの１
番目にできるストリップ表の順番で４頂点をストリップ
として送出する（ステップ１１０８）。When it is judged as NO (= the outer peripheral line data is not attached) in step 1106, and step 11
After 07, 1 in the first vertex data conversion table 26a
The four vertices are sent out as strips in the order of the second strip table (step 1108).
【００５１】一方、ステップ１１０５で、ＮＯ（＝１番
目のストリップではない）と判断された場合、更に、外
周線データ付きか否かを判断する（ステップ１１０
９）。ステップ１１０９で、ＹＥＳ（＝外周線データ付
き）と判断された場合、第１の外周線変換テーブル２９
ａのＮ番目にできるストリップの表により、外周線デー
タを付け替える（ステップ１１１０）。On the other hand, if NO (= 1st strip) is judged in step 1105, it is further judged whether or not outer peripheral line data is attached (step 110).
9). If YES (= with outer peripheral line data) is determined in step 1109, the first outer peripheral line conversion table 29
The outer peripheral line data is rearranged according to the table of the Nth strip of a (step 1110).
【００５２】ステップ１１１０で、ＮＯ（＝外周線デー
タが付いていない）と判断された場合及びステップ１１
１０の後に、第１の頂点データ変換テーブル２６ａのＮ
番目にできるストリップ表の順番で４頂点をストリップ
として送出する（ステップ１１１１）。When it is judged as NO (= no outer peripheral line data is attached) in step 1110, and in step 11
10 after the first vertex data conversion table 26a N
The four vertices are sent out as strips in the order of the second strip table (step 1111).
【００５３】ステップ１１０８及びステップ１１１１の
後に、全てのストリップデータを送ったか否かを判断す
る（ステップ１１１２）。ステップ１１１２で、ＮＯ
（＝送っていない）と判断された場合、ステップ１１０
２に戻る。After steps 1108 and 1111, it is determined whether all strip data has been sent (step 1112). NO in step 1112
If it is determined that (= not sent), step 110
Return to 2.
【００５４】[0054]
【第２実施例】 ＜構成＞図１２は、本発明の第２実施例の構成ブロック
図である。[Second Embodiment] <Structure> FIG. 12 is a block diagram showing the structure of a second embodiment of the present invention.
【００５５】第２実施例は、第１実施例と同様に構成さ
れているので、同一部分には同一符号を付して説明を省
略し、以下、相違する部分についてのみ説明する。 〔三角形リスト処理部２０〕三角形リスト処理部２０の
内部は、下記の（１）〜（３）からなる。 （１−ａ）頂点列を含む頂点データの変換を行う頂点デ
ータ変換部２１。 （１−ｂ）頂点データ変換部２１より入力した三角形ス
ターの頂点データを三角形ストリップ群の頂点データに
変換する第２のストリップ頂点データ変換処理部２５
ｂ。 （１−ｃ）現在何番目のストリップを処理しているかと
いう情報を格納するストリップ分割番号テーブル２３。 （１−ｄ）頂点データの変換方法に関する情報を格納す
る第２の頂点データ変換テーブル２６ｂ。 （２−ａ）外周線データの付け替えを行う外周線変換部
２７。 （２−ｂ）外周線変換部２７より外周線データを入力し
て、三角形ストリップ用の外周線データを変換する第２
のストリップ用外周線変換部２８ｂ。 （２−ｃ）外周線データの変換方法に関する情報を格納
する第２の外周線変換テーブル２９ｂ。 （３−ａ）第２のストリップ頂点データ変換処理部２５
ｂ及び第２のストリップ用外周線変換部２８ｂが変換し
た情報を格納するストリップデータ格納部２４。 （３−ｂ）ストリップデータ格納部２４に格納された情
報を図形描画部３０に送出するストリップデータ送出部
２２。Since the second embodiment has the same structure as the first embodiment, the same parts are designated by the same reference numerals and the description thereof will be omitted. Only the different parts will be described below. [Triangle list processing unit 20] The inside of the triangle list processing unit 20 is composed of the following (1) to (3). (1-a) A vertex data conversion unit 21 that converts vertex data including a vertex row. (1-b) Second strip vertex data conversion processing unit 25 for converting the vertex data of the triangle star input from the vertex data conversion unit 21 into the vertex data of the triangle strip group.
b. (1-c) A strip division number table 23 that stores information on which strip is currently processed. (1-d) A second vertex data conversion table 26b that stores information regarding the conversion method of vertex data. (2-a) An outer peripheral line conversion unit 27 that replaces outer peripheral line data. (2-b) Inputting outer peripheral line data from the outer peripheral line converting unit 27 to convert the outer peripheral line data for the triangular strip.
Outer peripheral line conversion unit 28b for strip. (2-c) A second outer peripheral line conversion table 29b that stores information about a method of converting outer peripheral line data. (3-a) Second strip vertex data conversion processing unit 25
b and the strip data storage unit 24 that stores the information converted by the second strip outer peripheral line conversion unit 28b. (3-b) The strip data transmission unit 22 that transmits the information stored in the strip data storage unit 24 to the graphic drawing unit 30.
【００５６】以下、各構成要素を説明する。 （頂点データ変換部２１、第２のストリップ頂点データ
変換処理部２５ｂ）第２のストリップ頂点データ変換処
理部２５ｂは、ストリップ分割番号テーブル２３と第２
の頂点データ変換テーブル２６ｂを変換時に参照する。Each component will be described below. (Vertex data conversion unit 21, second strip vertex data conversion processing unit 25b) The second strip vertex data conversion processing unit 25b includes the strip division number table 23 and the second
The vertex data conversion table 26b of is referred to at the time of conversion.
【００５７】第２の頂点データ変換テーブル２６ａは、
具体的には、表４のように構成されている。この表４を
参照して、図２（ａ）に示す三角形スターの頂点列を図
２（ｂ）に示す三角形ストリップの頂点列に変換する方
法を説明する。The second vertex data conversion table 26a is
Specifically, it is configured as shown in Table 4. A method for converting the vertex array of the triangular star shown in FIG. 2A into the vertex array of the triangular strip shown in FIG. 2B will be described with reference to Table 4.
【００５８】[0058]
【表４】 まず、図２（ｂ）に示す三角形ストリップの“１”番目
の頂点は、図２（ａ）に示す三角形スターの“２”番目
の頂点から変換される。[Table 4] First, the "1" th vertex of the triangular strip shown in FIG. 2B is converted from the "2" th vertex of the triangular star shown in FIG. 2A.
【００５９】以下、図２（ｂ）に示す三角形ストリップ
の“２”番目、“３”番目、“４”番目、“５”番目、
“６”番目、“７”番目及び“８”番目の頂点は、それ
ぞれ図２（ａ）の示す三角形スターの“３”番目、
“１”番目、“４”番目、“１”番目、“１”番目及び
“６”番目の頂点から変換される。Hereinafter, the "2" th, "3" th, "4" th, "5" th, and 3rd of the triangular strip shown in FIG.
The "6" th, "7" th, and "8" th vertices are the "3" th and the 3rd of the triangular star shown in FIG. 2 (a), respectively.
The "1" -th, "4" -th, "1" -th, "1" -th, and "6" -th vertices are converted.
【００６０】第２のストリップ用外周線変換部２８ｂ
は、第２の外周線変換テーブル２９ｂを変換時に参照す
る。第２の外周線変換テーブル２９ｂは、具体的には、
表５及び表６のように構成されている。Second outer peripheral line converting portion 28b for strip
Refers to the second outer peripheral line conversion table 29b during conversion. The second outer peripheral line conversion table 29b is, specifically,
It is configured as shown in Table 5 and Table 6.
【００６１】表５及び表６を参照して、図８（ａ）に示
す三角形スターの外周線を図８（ｂ）に示す三角形スト
リップの外周線に変換する方法を説明する。A method of converting the outer peripheral line of the triangular star shown in FIG. 8A into the outer peripheral line of the triangular strip shown in FIG. 8B will be described with reference to Tables 5 and 6.
【００６２】[0062]
【表５】 [Table 5]
【００６３】[0063]
【表６】 まず、“１”番の頂点については、この番号より若い番
号との間に外周線が引けないため、変換を考慮しなくて
良い。[Table 6] First, since the outer peripheral line cannot be drawn between the number "1" and a number smaller than this number, the conversion need not be considered.
【００６４】“２”番の頂点については、“１”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの３頂点目の（ｎ−１）頂点間外周線（３-1）（図
８（ａ）参照）となる。An outer peripheral line can be drawn between the "2" apex and the "1" apex. This outer peripheral line is the outer peripheral line between the (n-1) apexes of the third apex of the triangular star ( 3 −1 ) (see FIG. 8A).
【００６５】“３”番の頂点については、“２”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの３頂点目の（ｎ−２）頂点間外周線（３-2）（図
８（ａ）参照）となる。また、“１”番の頂点との間に
外周線が引けるが、この外周線は、三角形スターの２頂
点目の（ｎ−１）頂点間外周線（２-1）（図８（ａ）参
照）となる。An outer peripheral line can be drawn between the "3" apex and the "2" apex, and this outer peripheral line is the outer peripheral line between the (n-2) apexes of the third apex of the triangular star ( 3 -2 ) (see FIG. 8A). Also, an outer peripheral line can be drawn between the apex of "1", but this outer peripheral line is the outer peripheral line (2 -1 ) between the (n-1) apexes of the second apex of the triangular star (Fig. 8 (a)). (See).
【００６６】“４”番の頂点については、“３”番の頂
点との間に外周線が引けるが、この外周線は、三角形ス
ターの４頂点目の（ｎ−２）頂点間外周線（４ー2）（図
８（ａ）参照）となる。また、“２”番の頂点との間に
外周線が引けるが、この外周線は、三角形スターの４頂
点目の（ｎ−１）頂点間外周線（４ー1）（図８（ａ）参
照）となる。An outer peripheral line can be drawn between the "4" apex and the "3" apex. This outer peripheral line is the outer peripheral line between the (n-2) apexes of the fourth apex of the triangular star ( 4-2 ) (see FIG. 8A). A peripheral line can be drawn between the "2" vertex and this peripheral line is the (n-1) inter-vertical peripheral line ( 4-1 ) at the 4th vertex of the triangular star (Fig. 8 (a)). (See).
【００６７】“５”番の頂点については、表６より考慮
しなくてもよい。“６”番の頂点については、“５”番
の頂点との間に外周線が引けるが、この外周線は、三角
形スターの５頂点目の（ｎ−２）頂点間外周線（５ー2）
（図８（ａ）参照）となる。また、“４”番の頂点との
間に外周線が引けるが、この外周線は、三角形スターの
５頂点目の（ｎ−１）頂点間外周線（５ー1）（図８
（ａ）参照）となる。It is not necessary to consider from Table 6 the vertex "5". The apex of the "6" th, "5" th but can be subtracted peripheral line between the apex of the outer peripheral line of the triangle Stars 5 vertices th (n-2) between vertices peripheral line (5-2 )
(See FIG. 8A). Also, an outer peripheral line can be drawn between the "4" vertex and this outer peripheral line is the outer peripheral line ( 5-1 ) between the (n-1) apexes of the fifth vertex of the triangular star (Fig. 8).
(See (a)).
【００６８】“７”番の頂点については、表６より考慮
しなくてもよい。“８”番の頂点については、“７”番
の頂点との間に外周線が引けるが、この外周線は、三角
形スターの６頂点目の（ｎ−２）頂点間外周線（６ー2）
（図８（ａ）参照）となる。また、“６”番の頂点との
間に外周線が引けるが、この外周線は、三角形スターの
５頂点目の（ｎ−１）頂点間外周線（６ー1）（図８
（ａ）参照）となる。It is not necessary to consider from Table 6 the "7" vertex. A peripheral line can be drawn between the apex of "8" and the apex of "7", but this peripheral line is the outer peripheral line between the (n-2) apexes of the sixth vertex of the triangular star ( 6-2 )
(See FIG. 8A). A peripheral line can be drawn between the "6" vertex and this peripheral line is the (n-1) inter-vertical peripheral line ( 6-1 ) at the 5th vertex of the triangular star (Fig. 8).
(See (a)).
【００６９】＜三角形リスト処理部２０の動作＞次に、
図１３を参照して三角形リスト処理部２０の動作を説明
する。まず、図形データ格納部１０から図形データが入
力されると、「三角形スター」、「三角形ストリッ
プ」、及び「独立三角形」のいずれに該当するかが形状
判定される（ステップ１３０１）。<Operation of Triangle List Processing Unit 20> Next,
The operation of the triangle list processing unit 20 will be described with reference to FIG. First, when the graphic data is input from the graphic data storage unit 10, the shape of the “triangle star”, the “triangle strip”, or the “independent triangle” is determined (step 1301).
【００７０】ステップ１３０１で、「三角形ストリッ
プ」と判定された場合は、図示していない三角形ストリ
ップ処理部に処理が移る（ステップ１３０３）。また、
ステップ１３０１で「独立三角形」と判定された場合
は、図示していない独立三角形処理部に処理が移る（ス
テップ１３０４）。If it is determined in step 1301 that the "triangle strip" is present, the process moves to a triangle strip processing unit (not shown) (step 1303). Also,
If it is determined as "independent triangle" in step 1301, the process moves to an independent triangle processing unit (not shown) (step 1304).
【００７１】そして、ステップ１３０１で「三角形スタ
ー」と判定された場合は、２つのストリップ分のデータ
を読み込む（ステップ１３０２）。そして、１番目のス
トリップか否かを判断する（ステップ１３０５）。Then, when it is judged as "triangle star" in step 1301, the data for two strips is read (step 1302). Then, it is judged whether or not it is the first strip (step 1305).
【００７２】ステップ１３０５で、ＹＥＳ（＝１番目の
ストリップ）と判断された場合、更に、外周線データ付
きか否かを判断する（ステップ１３０６）。ステップ１
３０６で、ＹＥＳ（＝外周線データ付き）と判断された
場合、第２の外周線変換テーブル２９ｂの１番目にでき
るストリップの表により、外周線データを付け替える
（ステップ１３０７）。When it is determined YES (= 1st strip) in step 1305, it is further determined whether or not outer peripheral line data is included (step 1306). Step 1
When it is determined YES in 306 (= with outer peripheral line data), the outer peripheral line data is replaced according to the first strip table in the second outer peripheral line conversion table 29b (step 1307).
【００７３】ステップ１３０６で、ＮＯ（＝外周線デー
タが付いていない）と判断された場合及びステップ１３
０７の後に、３頂点を第２の頂点データ変換テーブル２
６ｂより変換して送出する（ステップ１３０８）。When it is determined as NO (= the outer peripheral line data is not attached) in step 1306, and step 13
After 07, 3 vertices are converted to the second vertex data conversion table 2
6b is converted and transmitted (step 1308).
【００７４】一方、ステップ１３０５で、ＮＯ（＝１番
目のストリップではない）と判断された場合、更に、外
周線データ付きか否かを判断する（ステップ１３０
９）。ステップ１３０９で、ＹＥＳ（＝外周線データ付
き）と判断された場合、第２の外周線変換テーブル２９
ｂのＮ番目にできるストリップの表により、外周線デー
タを付け替える（ステップ１３１０）。On the other hand, when it is judged NO in step 1305 (= not the first strip), it is further judged whether or not outer peripheral line data is attached (step 130).
9). If it is determined as YES (= with outer peripheral line data) in step 1309, the second outer peripheral line conversion table 29
The outer peripheral line data is rearranged according to the table of the Nth strip formed in b (step 1310).
【００７５】ステップ１３１０で、ＮＯ（＝外周線デー
タが付いていない）と判断された場合及びステップ１３
１０の後に、２頂点を第２の頂点データ変換テーブル２
６ｂより変換して送出する（ステップ１３１１）。When it is judged as NO (= the outer peripheral line data is not attached) in Step 1310, and Step 13
After 10, the second vertex is converted into the second vertex data conversion table 2
6b is converted and transmitted (step 1311).
【００７６】ステップ１３０８及びステップ１３１１の
後に、全てのストリップデータを送ったか否かを判断す
る（ステップ１３１２）。ステップ１３１２で、ＮＯ
（＝送っていない）と判断された場合、ステップ１３０
２に戻る。After steps 1308 and 1311, it is determined whether all strip data has been sent (step 1312). NO in step 1312
If it is determined (= not sent), step 130
Return to 2.
【００７７】[0077]
【発明の効果】本発明の図形データ処理方法及び図形デ
ータ処理装置によれば、三角形スター構造の図形データ
を三角形ストリップ構造の図形データに変換して処理す
ることで、三角形ストリップを高速に描画する装置が利
用可能となり、従来、高速描画が困難であった三角形ス
ターを高速に描画することが可能になる。According to the graphic data processing method and the graphic data processing apparatus of the present invention, the graphic data of the triangle star structure is converted into the graphic data of the triangle strip structure and processed, thereby drawing the triangle strip at high speed. The device can be used, and it becomes possible to draw a triangular star at high speed, which was difficult to draw at high speed in the past.
【図１】本発明の図形データ処理方法の第１原理図であ
る。FIG. 1 is a first principle diagram of a graphic data processing method of the present invention.
【図２】本発明の図形データ処理方法の第２原理図であ
る。FIG. 2 is a second principle diagram of the graphic data processing method of the present invention.
【図３】本発明の図形データ処理装置の原理図である。FIG. 3 is a principle diagram of a graphic data processing device of the present invention.
【図４】独立三角形の説明図である。FIG. 4 is an explanatory diagram of an independent triangle.
【図５】三角形ストリップの説明図である。FIG. 5 is an explanatory diagram of a triangular strip.
【図６】三角形スターの説明図である。FIG. 6 is an explanatory diagram of a triangular star.
【図７】三角形スターの外周線フラグと三角形ストリッ
プの外周線フラグとの関係図である。FIG. 7 is a diagram showing a relationship between an outer peripheral line flag of a triangular star and an outer peripheral line flag of a triangular strip.
【図８】三角形スターの外周線フラグと三角形ストリッ
プの外周線フラグとの関係図である。FIG. 8 is a diagram showing a relationship between an outer peripheral line flag of a triangular star and an outer peripheral line flag of a triangular strip.
【図９】第１実施例の構成ブロック図である。FIG. 9 is a configuration block diagram of the first embodiment.
【図１０】実施例の三角形リスト要素テーブルを示す図
である。FIG. 10 is a diagram showing a triangle list element table according to the embodiment.
【図１１】第１実施例の三角形リスト処理部のフローチ
ャートである。FIG. 11 is a flowchart of a triangle list processing unit according to the first embodiment.
【図１２】第２実施例の構成ブロック図である。FIG. 12 is a configuration block diagram of a second embodiment.
【図１３】第２実施例の三角形リスト処理部のフローチ
ャートである。FIG. 13 is a flowchart of a triangle list processing unit according to the second embodiment.
１０・・・・図形データ格納部 ２０・・・・三角形リスト処理部 ２１・・・・頂点データ変換部 ２２・・・・ストリップデータ送出部 ２３・・・・ストリップ分割番号テーブル ２４・・・・ストリップデータ格納部 ２５ａ・・・第１のストリップ頂点データ変換処理部 ２５ｂ・・・第２のストリップ頂点データ変換処理部 ２６ａ・・・第１の頂点データ変換テーブル ２６ｂ・・・第２の頂点データ変換テーブル ２７・・・・外周線変換部 ２８ａ・・・第１のストリップ用外周線変換部 ２８ｂ・・・第２のストリップ用外周線変換部 ２９ａ・・・第１の外周線変換テーブル ２９ｂ・・・第２の外周線変換テーブル ３０・・・・図形描画部 10 ... Graphic data storage unit 20 ... Triangle list processing unit 21 ... Vertex data conversion unit 22 ... Strip data transmission unit 23 ... Strip division number table 24 ... Strip data storage unit 25a ... First strip vertex data conversion processing unit 25b ... Second strip vertex data conversion processing unit 26a ... First vertex data conversion table 26b ... Second vertex data Conversion table 27 ... Outer peripheral line conversion unit 28a ... First strip outer peripheral line conversion unit 28b ... Second strip outer peripheral line conversion unit 29a ... First outer peripheral line conversion table 29b. .... Second outer peripheral line conversion table 30 ... Graphic drawing unit
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 庁内整理番号 ＦＩ 技術表示箇所 9365−5Ｈ Ｇ０６Ｆ 15/72 ３５５ Ｋ ─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. 6 Identification code Internal reference number FI technical display location 9365-5H G06F 15/72 355 K
Claims (6)
する番号を割り当ててなる頂点列であり、“ｎ”を１以
上の整数とした場合に、所定番号、（所定番号＋ｎ）番
及び（所定番号＋ｎ＋１）番の頂点から形成される三角
形により、前記図形の内部を過不足なく分割する第一の
頂点列を、 前記図形の各頂点に割り当ててなる別の頂点列であり、
“ｍ”を整数とした場合に、（ｍ−２）番、（ｍ−１）
番及びｍ番の頂点から形成される三角形と（ｍ−１）
番、ｍ番及び（ｍ＋１）番の頂点から形成される三角形
とを合成して形成される四角形により、前記図形の内部
を過不足なく分割する第二の頂点列に変換して処理する
ことを含むことを特徴とする図形データ処理方法。1. A vertex sequence in which a number that is incremented by one is assigned to each vertex of a figure from a predetermined number. When "n" is an integer of 1 or more, a predetermined number, (predetermined number + n) number And a first vertex row which divides the inside of the figure without excess or deficiency by a triangle formed from the (predetermined number + n + 1) number of vertices is another vertex row which is assigned to each vertex of the figure,
When "m" is an integer, (m-2) number, (m-1)
Triangle formed from the vertices of the number n and m and (m-1)
By converting a quadrangle formed by synthesizing a triangle formed from the # 1, m-th, and (m + 1) -th vertices into a second vertex row that divides the inside of the figure without excess or deficiency, processing is performed. A graphic data processing method comprising:
れたフラグである第一の外周線フラグを、 前記第二の頂点列が付された頂点間の各辺に割り当てら
れたフラグである第二の外周線フラグに変換して処理す
ることを特徴とする図形データ処理方法。2. The first peripheral line flag according to claim 1, wherein the first peripheral line flag is a flag assigned to each side between the vertices to which the first vertex line is attached, and the second vertex line is attached. A graphic data processing method characterized by converting to a second outer peripheral line flag which is a flag assigned to each side between vertices and processing.
する番号を割り当ててなる頂点列であり、“ｎ”を１以
上の整数とした場合に、所定番号、（所定番号＋ｎ）番
及び（所定番号＋ｎ＋１）番の頂点から形成される三角
形により、前記図形の内部を過不足なく分割するように
割り当てられた第一の頂点列を、 前記図形の各頂点に割り当ててなる別の頂点列であり、
“ｍ”を整数とした場合に、（ｍ−２）番、（ｍ−１）
番及びｍ番の頂点から形成される三角形により、前記図
形の内部を過不足なく分割する第二の頂点列に変換して
処理することを特徴とする図形データ処理方法。3. A vertex sequence in which a number that is incremented by one from a predetermined number is assigned to each vertex of a figure. When "n" is an integer of 1 or more, a predetermined number, (predetermined number + n) number And another vertex formed by allocating to the vertices of the figure a first row of vertices that is assigned to divide the inside of the figure without excess or deficiency by a triangle formed by the vertices of (predetermined number + n + 1) Columns,
When "m" is an integer, (m-2) number, (m-1)
A graphic data processing method characterized by converting the inside of the graphic into a second apex sequence that divides the interior of the graphic with just the right and left corners by using a triangle formed from the # 1 and m-th vertices.
れたフラグである第一の外周線フラグを、 前記第二の頂点列が付された頂点間の各辺に割り当てら
れたフラグである第二の外周線フラグに変換して処理す
ることを特徴とする図形データ処理方法。4. The third peripheral line flag according to claim 3, wherein the first peripheral line flag is a flag assigned to each side between the vertices to which the first vertex line is attached. A graphic data processing method characterized by converting to a second outer peripheral line flag which is a flag assigned to each side between vertices and processing.
する番号を割り当ててなる頂点列であり、“ｎ”を１以
上の整数とした場合に、所定番号、（所定番号＋ｎ）番
及び（所定番号＋ｎ＋１）番の頂点から形成される三角
形により、前記図形の内部を過不足なく分割する第一の
頂点列を、図形データ格納部から入力し、前記図形の各
頂点に割り当ててなる別の頂点列であり、“ｍ”を整数
とした場合に、（ｍ−２）番、（ｍ−１）番及びｍ番の
頂点から形成される三角形と（ｍ−１）番、ｍ番及び
（ｍ＋１）番の頂点から形成される三角形とを合成して
形成される四角形により、前記図形の内部を過不足なく
分割する第二の頂点列に変換する頂点データ変換部と、 この頂点データ変換部により変換された第二の頂点列
を、三角形ストリップを描画する機能を有する図形描画
部に出力する変換データ出力部とを備えたことを特徴と
する図形データ処理装置。5. A vertex sequence in which a number that is incremented by one is assigned to each vertex of a figure from a predetermined number. When "n" is an integer of 1 or more, a predetermined number, (predetermined number + n) number And a first vertex row that divides the inside of the figure without excess or deficiency by the triangle formed by the (predetermined number + n + 1) vertices is input from the figure data storage unit and assigned to each vertex of the figure. It is another vertex sequence, and when "m" is an integer, a triangle formed from vertices of (m-2) th, (m-1) th and mth and (m-1) th and mth And a vertex formed by combining the triangles formed by the (m + 1) th vertices into a second vertex sequence that divides the inside of the figure without excess or deficiency, and this vertex data. The second vertex row converted by the converter is a triangle strip. And a conversion data output unit that outputs the converted data to a graphic drawing unit having a function of drawing.
する番号を割り当ててなる頂点列であり、“ｎ”を１以
上の整数とした場合に、所定番号、（所定番号＋ｎ）番
及び（所定番号＋ｎ＋１）番の頂点から形成される三角
形により、前記図形の内部を過不足なく分割するように
割り当てられた第一の頂点列を、図形データ格納部から
入力し、前記図形の各頂点に割り当ててなる別の頂点列
であり、“ｍ”を整数とした場合に、（ｍ−２）番、
（ｍ−１）番及びｍ番の頂点から形成される三角形によ
り、前記図形の内部を過不足なく分割する第二の頂点列
に変換する頂点データ変換部と、 この頂点データ変換部により変換された第二の頂点列
を、三角形ストリップを描画する機能を有する図形描画
部に出力する変換データ出力部とを備えたことを特徴と
する図形データ処理装置。6. A vertex sequence in which a number that is incremented by one is assigned to each vertex of a figure from a predetermined number. When "n" is an integer of 1 or more, a predetermined number, (predetermined number + n) number And a triangle formed by the (predetermined number + n + 1) number of vertices, the first vertex row allocated so as to divide the inside of the figure without excess or deficiency is input from the figure data storage unit, and each of the figures It is another vertex sequence assigned to the vertices, and when "m" is an integer, the number (m-2),
A vertex data conversion unit that converts the inside of the figure into a second vertex sequence that divides the inside of the figure without excess or deficiency by a triangle formed from (m-1) th and mth vertices, and is converted by this vertex data conversion unit. And a converted data output unit for outputting the second vertex row to a graphic drawing unit having a function of drawing a triangular strip.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6241460A JPH08106521A (en) | 1994-10-05 | 1994-10-05 | Graphic data processing method and graphic data processing device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6241460A JPH08106521A (en) | 1994-10-05 | 1994-10-05 | Graphic data processing method and graphic data processing device |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH08106521A true JPH08106521A (en) | 1996-04-23 |
Family
ID=17074653
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP6241460A Withdrawn JPH08106521A (en) | 1994-10-05 | 1994-10-05 | Graphic data processing method and graphic data processing device |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH08106521A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011175656A (en) * | 2006-05-11 | 2011-09-08 | Panasonic Corp | Processing device |
-
1994
- 1994-10-05 JP JP6241460A patent/JPH08106521A/en not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011175656A (en) * | 2006-05-11 | 2011-09-08 | Panasonic Corp | Processing device |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| RU2134447C1 (en) | Data transfer device and video game using it | |
| CA1181881A (en) | Method and apparatus for compiling digital image information | |
| US4533910A (en) | Graphics display system with viewports of arbitrary location and content | |
| EP0235456A2 (en) | Image processing apparatus | |
| JPH0916144A (en) | System and method for triangle raster with two-dimensionallyinterleaved frame buffer | |
| EP0076082B1 (en) | Display processing apparatus | |
| EP0279693A2 (en) | Multi-plane video ram | |
| US5724560A (en) | Display graphics adapter for processing different pixel sizes in a windowing system | |
| US5719598A (en) | Graphics processor for parallel processing a plurality of fields of view for multiple video displays | |
| JPS60191293A (en) | High-speed linear interpolation circuit for CRT display devices | |
| JPH08106521A (en) | Graphic data processing method and graphic data processing device | |
| JPH06223099A (en) | Signal processing system provided with reduced memory space | |
| US5535315A (en) | Graphic coloring system in a graphic-display system having separately stored shape/positional data and color data selectively combinable to form desired images of differing shapes and colors | |
| US6563507B1 (en) | Storage circuit control device and graphic computation device | |
| US6476818B1 (en) | Storage circuit control device and graphic computation device | |
| JP2677954B2 (en) | Memory system | |
| US4291306A (en) | Figure displaying device | |
| JPS6292070A (en) | Memory system for picture data | |
| JPS5967587A (en) | Color overlapped graphic generator | |
| US6054994A (en) | Process for depicting objects using an image reproduction device | |
| JPH0752468B2 (en) | Multiprocessor for line drawing display | |
| JPS6069756A (en) | Data storage device | |
| JPS63168749A (en) | Three-dimensional data storage device | |
| JPS63318682A (en) | Vertical/horizontal converting method for image data | |
| JPH06168323A (en) | Image data reducing display device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20020115 |