JPH06231261A

JPH06231261A - 折線近似によりパラメトリックトリミング曲線を表示する方法およびグラフィック表示システム

Info

Publication number: JPH06231261A
Application number: JP1385593A
Authority: JP
Inventors: Toshiharu Kawasaki; 敏治川崎; Tooru Sakaihara; 徹酒井原; Toshiyuki Kuwana; 利幸桑名
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1993-01-29
Filing date: 1993-01-29
Publication date: 1994-08-19

Abstract

(57)【要約】【目的】トリミング曲線の曲面上での誤差を指定され
た値以下にする、トリミング曲線の折線による近似方法
を備えたグラフィックシステムを提供する。【構成】ファイリング装置６１３に予め格納、または
マウス６０４等により入力されたトリミング曲線は、メ
モリ６０２に格納される。キーボード６０３から指定さ
れた許容誤差値は、メモリ６０２に格納される。装置６
１３には、トリミング曲線を折線により近似する際に、
任意の許容誤差値に基づいて折線の数を決定するプログ
ラムが格納されている。このプログラムはメモリ６０２
に読みだされ、ＣＰＵ６０１で実行されて指定された許
容誤差値に基づき折線の数が決定され、トリミング曲線
の図形データが作成されてメモリ６０２に格納される。
このデータはグラフィックサブシステム６０７に転送さ
れ、ＣＲＴ６１１に表示される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、パラメトリック曲面を
グラフィックディスプレイ等に描画するグラフィックシ
ステムに係り、特にパラメトリック曲面をパラメトリッ
クトリミング曲線によってトリミングするようなグラフ
ィックシステムに係る。

【０００２】

【従来の技術】一般に、グラフィックシステムにおいて
曲線を表示する場合、曲線をドット（点）の列として表
示させようとすると複雑な処理を必要とするため、複数
の連続した線分からなる折線で近似して表示する。線分
を発生するには、例えば、ＤＤＡ（ＤｉｇｉｔａｌＤ
ｉｆｆｅｒｅｎｔｉａｌＡｎａｌｉｚｅｒ）を用いる
方法がある。

【０００３】即ち、曲線の折線近似は、曲線上に適当な
Ｎ（≧１）個の点（これを分割点と称する）を採り、上
記曲線の始点と第１番目の分割点、第１番目の分割点と
第２番目の分割点、……、第Ｎ−１番目の分割点と第Ｎ
番目の分割点、第Ｎ番目の分割点と終点とを線分で結ん
だ折線で近似することによってなされる。

【０００４】同様に、曲面をドットの列により表示させ
ようとすると複雑な処理を必要とするため、複数の連続
した多角形からなる開多面体又は閉多面体で近似して表
示する。上記多角形（正確には、この多角形を塗り潰す
ためのドット列）を発生させるためには、上記のように
線分を表示する場合と同様に、ＤＤＡを用いる方法があ
る（ただし、線分を発生させるＤＤＡを２次元のＤＤＡ
と称し、多角形を発生させるＤＤＡを３次元のＤＤＡと
称する）。

【０００５】即ち、曲面の開多面体又は閉多面体による
近似は、曲面上に適当なＭ×Ｎ個（Ｍ，Ｎ≧１）の分割
点を採り（曲面上の１方向にＭ個の分割点を、この方向
と異なる方向にＮ個の分割点を採り）、この分割点によ
り出来るＭ×Ｎ個の格子の矩形、又は、この矩形を更に
対角線で分割した三角形の集まりにより近似する。

【０００６】曲線及び曲面の上記のような分割点の求め
方としては、曲線及び曲面の各座標がパラメータによる
数式で表現されている場合に、このパラメータの値を始
点から終点までを等分してパラメータの分割点を求め、
各パラメータの分割点に対応する曲線及び曲面上の点を
分割点とする方法がある。この場合に、分割点の個数
（分割数）を求める方法としては、従来“Ｓｕｒｆａｃ
ｅａｌｇｏｒｉｔｈｍｓｕｓｉｎｇｂｏｕｎｄｓ
ｏｎｄｅｒｉｖａｔｉｖｅｓ”（Ｄ．Ｆｉｌｉｐ，
Ｒ．Ｍａｇｅｄｓｏｎ，ａｎｄＲ．Ｍａｒｋｏ
ｔ，１９８６）や“Ｒｅａｌ−ｔｉｍｅｒｅｎｄｅ
ｒｉｎｇｏｆｔｒｉｍｍｅｄｓｕｒｆａｃｅｓ”
（Ａ．Ｒｏｃｋｗｏｏｄ，Ｋ．Ｈｅａｔｏｎ，ａｎ
ｄＴ．Ｄａｖｉｓ，１９８９）等に記載されている
ような方法がある。

【０００７】

【発明が解決しようとする課題】上記従来技術では、パ
ラメトリック（パラメータの関数として与えられる）曲
線及びパラメトリック曲面の分割数の決定法について述
べられている。

【０００８】一方、パラメトリック曲面のパラメータ空
間（これを定義域と称する）をパラメータ空間内に定義
された曲線で制限し、制限された部分のみを描画するよ
うな、いわゆるトリミングの技術がある。トリミング
は、通常パラメータ空間内に定義された一本以上の曲線
（これをトリミング曲線と称す）から構成される閉曲線
（これをトリミングループと称す）で指定され、その閉
曲線の左側（右側）を描画する側として残すように定義
される。

【０００９】一般に、各トリミング曲線もパラメトリッ
クに定義されることが多い。この場合、このパラメトリ
ック曲線（トリミング曲線）も折線近似を行うが、上記
従来技術にもトリミング曲線の分割方法については述べ
られていない。しかし、通常は、グラフィックシステム
固定又はシステムへ受け渡される分割数でパラメトリッ
ク曲面のパラメタ空間内で折線近似を行い、その後トリ
ミング曲線を折線近似した各節点（２本の折線が接続す
る点）におけるパラメトリック曲面上の値、又は、開多
面体近似又は閉多面体近似した開多面体又は閉多面体上
の値を計算し、このようにして計算された曲面上の点を
結んで構成される折線をパラメトリック曲面のエッジ
（端部）としていた。しかし、このようにするとトリミ
ングによって生じたパラメトリック曲面のエッジに誤差
が発生するが、その誤差を評価する手段について考慮さ
れていなかった。トリミングされた二つの曲面をエッジ
で合わせたような図形を表示したい場合には、このよう
な誤差が大きいとエッジ部分が合わなくなり不自然にな
る。

【００１０】本発明は、ユーザにより誤差の許容値を指
定されると、トリミングによって生じるパラメトリック
曲面のエッジの誤差を、前記指定された値以下に抑える
ことを可能とするための、パラメトリックトリミング曲
線の折線近似方法を備えたグラフィックシステムを提供
することを目的とする。

【００１１】

【問題を解決するための手段】上記課題を解決するため
に、本発明によれば、少なくとも、入力装置、記憶装
置、演算装置、および、表示装置を備え、パラメトリッ
ク曲面の定義式または制御点の集合、および、前記曲面
をトリミングするためのパラメトリックなトリミング曲
線の定義式または制御点の集合を記憶装置に保持し、演
算装置において前記パラメトリック曲面を開多面体また
は閉多面体により近似し、演算装置において前記パラメ
トリックなトリミング曲線を折線により近似して、前記
パラメトリック曲面およびパラメトリックなトリミング
曲線を前記表示装置に表示する際に、トリミング曲線の
折線による近似の精度について、外部から指定される任
意の値の許容誤差値を前記入力装置により受付けて記憶
装置に保持し、指定された許容誤差値に基づいて、トリ
ミング曲線を折線により近似する際の折線の数を決定す
るための式を記憶装置に予め備え、演算装置により折線
の数を決定することができる。

【００１２】また、トリミング曲線が、１つの変数ｔを
パラメタとしｃ（ｔ）＝（ｕ（ｔ），ｖ（ｔ））である
写像ｃで与えられ、パラメトリック曲面が、２つの変数
ｕおよびｖをパラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，
ｖ），ｙ（ｕ，ｖ），ｚ（ｕ，ｖ））である写像ｓによ
り与えられ、許容誤差値がＬで指定されるとき、トリミ
ング曲線を折線により近似する際の折線の数を決定する
ための式を、合成写像ｓ・ｃのｔによる一次微分（ｓ・
ｃ）′の大きさの、前記トリミング曲線のパラメタｔの
範囲内での最大値Ｍ１を演算装置により求め、折線の数
をＭ１／Ｌと決定するための式とすることもできる。

【００１３】さらに、トリミング曲線が、１つの変数ｔ
をパラメタとしｃ（ｔ）＝（ｕ（ｔ），ｖ（ｔ））であ
る写像ｃで与えられ、パラメトリック曲面が、２つの変
数ｕおよびｖをパラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，
ｖ），ｙ（ｕ，ｖ），ｚ（ｕ，ｖ））である写像ｓによ
り与えられ、許容誤差値がＴＯＬで指定されるとき、ト
リミング曲線を折線により近似する際の折線の数を決定
するための式を、合成写像ｓ・ｃのｔによる二次微分
（ｓ・ｃ）″の大きさの、前記トリミング曲線のパラメ
タｔの範囲内での最大値Ｍ２を演算装置により求め、折
線の数を√（Ｍ２／（８×ＴＯＬ））と決定するための
式とすることもできる。

【００１４】さらに、パラメトリック曲面が、複数の曲
面（各曲面を区分と称する）の和集合として与えられて
いる場合には、パラメトリックトリミング曲線ｃの写像
ｓによる値域と、前記パラメトリック曲面の各区分との
共通部分が存在するか否かを演算装置により判定し、共
通部分が存在するときに限り、共通部分が存在する範囲
を合成写像ｓ・ｃのパラメタ範囲として、（ｓ・ｃ）′
又は（ｓ・ｃ）″の大きさの最大値を求めることもでき
る。

【００１５】さらに、パラメトリック曲面が、複数の曲
面（各曲面を区分と称する）の和集合として与えられ、
且つ、パラメトリックトリミング曲線が制御点の集合で
定義され且つ凸包性を有する場合には、前記パラメトリ
ックトリミング曲線を定義する制御点の集合の写像ｓに
よる値域と、前記パラメトリック曲面の各区分との共通
部分が存在するか否かを演算装置により判定し、前記パ
ラメトリックトリミング曲線の値域とパラメトリック曲
線の各区分との共通部分が存在するか否かの判定を行う
こともできる。

【００１６】さらに、パラメトリック曲面の定義式また
は制御点の集合、および、前記曲面をトリミングするた
めのパラメトリックなトリミング曲線の定義式または制
御点の集合を記憶装置に保持し、演算装置において前記
パラメトリック曲面を開多面体または閉多面体により近
似し、演算装置において前記パラメトリックなトリミン
グ曲線を折線により近似して、前記パラメトリック曲面
およびパラメトリックなトリミング曲線を表示装置に表
示するグラフィック表示システムにおいて、前記トリミ
ング曲線の折線による近似の精度について、外部から指
定される任意の値の許容誤差値を入力する入力手段と、
入力された許容誤差値を保持する第１の記憶手段と、入
力された許容誤差値に基づいて、前記トリミング曲線を
折線により近似する際の折線の数を決定するための式を
予め保持する第２の記憶手段と、この式に基づき折線の
数を決定する決定手段とを備えるグラフィック表示シス
テムを提供することもできる。

【００１７】さらに、このグラフィック表示システムに
おいて、トリミング曲線が、１つの変数ｔをパラメタと
しｃ（ｔ）＝（ｕ（ｔ），ｖ（ｔ））である写像ｃで与
えられ、パラメトリック曲面が、２つの変数ｕおよびｖ
をパラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，ｖ），ｙ
（ｕ，ｖ），ｚ（ｕ，ｖ））である写像ｓにより与えら
れ、許容誤差値がＬで指定されるとき、トリミング曲線
を折線により近似する際の折線の数を決定するための式
を、合成写像ｓ・ｃのｔによる一次微分（ｓ・ｃ）′の
大きさの、トリミング曲線のパラメタｔの範囲内での最
大値Ｍ１を演算装置により求め、折線の数をＭ１／Ｌと
決定するための式とすることもできる。

【００１８】さらに、グラフィック表示システムにおい
て、トリミング曲線が、１つの変数ｔをパラメタとしｃ
（ｔ）＝（ｕ（ｔ），ｖ（ｔ））である写像ｃで与えら
れ、パラメトリック曲面が、２つの変数ｕおよびｖをパ
ラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，ｖ），ｙ（ｕ，
ｖ），ｚ（ｕ，ｖ））である写像ｓにより与えられ、許
容誤差値がＴＯＬで指定されるとき、前記トリミング曲
線を折線により近似する際の折線の数を決定するための
式を、合成写像ｓ・ｃのｔによる二次微分（ｓ・ｃ）″
の大きさの、前記トリミング曲線のパラメタｔの範囲内
での最大値Ｍ２を演算装置により求め、折線の数を√
（Ｍ２／（８×ＴＯＬ））と決定するための式とするこ
ともできる。

【００１９】さらに、パラメトリック曲面が、複数の曲
面（各曲面を区分と称する）の和集合として与えられて
いる場合に、パラメトリックトリミング曲線ｃの写像ｓ
による値域と、パラメトリック曲面の各区分との共通部
分が存在するか否かを判定する判定手段と、判定手段に
より共通部分が存在すると判定された場合に、共通部分
が存在する範囲を合成写像ｓ・ｃのパラメタ範囲とし
て、（ｓ・ｃ）′又は（ｓ・ｃ）″の大きさの最大値を
求める最大値算出手段とを備えるグラフィック表示シス
テムを提供することもできる。

【００２０】さらに、パラメトリック曲面が、複数の曲
面（各曲面を区分と称する）の和集合として与えられ、
且つ、パラメトリックトリミング曲線が制御点の集合で
定義され且つ凸包性を有する場合に、判定手段として、
パラメトリックトリミング曲線を定義する制御点の集合
の写像ｓによる値域と、パラメトリック曲面の各区分と
の共通部分が存在するか否かを判定する制御点判定手段
とを備えるグラフィック表示システムを提供することも
できる。

【００２１】ここで、凸包性について説明する。区間
［ａ，ｂ］を定義域とするパラメトリック曲線が、制御
点の集合｛Ｐ_i｜ｉ＝１，２，…，ｎ｝から定まってい
るとき、曲線ｃが凸包性を持つとは、曲線上の任意の点
がｃｏ｛Ｐ_i｜ｉ＝１，２，３，…，ｎ｝（すべての点
Ｐ_iを含む、最小の凸集合）に含まれることである。即
ち、任意のｔ∈［ａ，ｂ］に対して、ｃ（ｔ）∈ｃｏ
｛Ｐ_i｜ｉ＝１，２，…，ｎ｝が成り立つことである。
同様に、矩形領域［ａ，ｂ］×［ｃ，ｄ］を定義域とす
るパラメトリック曲面が、制御点の集合｛Ｐ_ij｜ｉ＝
１，２，…，ｍ；ｊ＝１，２，…，ｎ｝から定まってい
るとき、曲面ｓが凸包性を持つとは、曲線上の任意の点
がｃｏ｛Ｐ_ij｜ｉ＝１，２，…，ｍ；ｊ＝１，２，…，
ｎ｝（すべての点Ｐ_ijを含む、最小の凸集合）に含まれ
ることである。即ち、任意の（ｕ，ｖ）∈［ａ，ｂ］×
［ｃ，ｄ］に対して、ｓ（ｕ，ｖ）∈ｃｏ｛Ｐ_ij｜ｉ＝
１，２，…，ｍ；ｊ＝１，２，…，ｎ｝が成り立つこと
である。

【００２２】

【作用】パラメトリックトリミング曲線の折線近似の為
の分割方法をパラメトリック曲面上での誤差が一定値以
下になるように定める為の一例は、与えられたパラメト
リック曲面の定義式又は与えられた制御点の集合より定
まる定義式をｓとし、与えられたパラメトリックトリミ
ング曲線の定義式又は与えられた制御点の集合より定ま
る定義式をｃとするとき、パラメトリックトリミング曲
線の折線近似の各線分の長さを一定値Ｌ以下に抑えるた
めに、合成写像ｓ・ｃのパラメトリックトリミング曲線
のパラメタによる一次微分（ｓ・ｃ）′の大きさのパラ
メタ範囲内での最大値Ｍ１を求め、パラメトリックトリ
ミング曲線の折線近似の為の分割数をＭ１／Ｌとするこ
とである。

【００２３】別の一例は、与えられたパラメトリック曲
面の定義式又は与えられた制御点の集合より定まる定義
式をｓとし、与えられたパラメトリックトリミング曲線
の定義式又は与えられた制御点の集合より定まる定義式
をｃとするとき、パラメトリックトリミング曲線の折線
近似とパラメトリックトリミング曲線の真値からの誤差
を一定値ＴＯＬ以下に抑えるために、合成写像ｓ・ｃの
パラメトリックトリミング曲線のパラメタによる二次微
分（ｓ・ｃ）″の大きさのパラメタ範囲内での最大値Ｍ
２を求め、パラメトリックトリミング曲線の折線近似の
為の分割数を√（Ｍ２／（８×ＴＯＬ））とすることで
ある。

【００２４】更に、パラメトリック曲面が区分的に与え
られている場合において、パラメトリックトリミング曲
線の折線近似の為の分割方法は、各区分毎にパラメトリ
ックトリミング曲線の折線近似方法によって行い、合成
写像ｓ・ｃのパラメタ範囲は、パラメトリックトリミン
グ曲線ｃの値域とパラメトリック曲面の各区分との共通
部分が存在するかを判定し、共通部分が存在するときに
限り共通部分が存在する範囲をパラメタ範囲として（ｓ
・ｃ）′又は（ｓ・ｃ）″の大きさの最大値を求める。

【００２５】更に、パラメトリック曲面が区分的に与え
られ、且つ、パラメトリックトリミング曲線が制御点の
集合で定義され且つ凸包性を有する場合において、パラ
メトリックトリミング曲線の値域とパラメトリック曲線
の各区分との共通部分が存在するかの判定は、パラメト
リックトリミング曲線を定義する制御点の集合の値域と
パラメトリック曲面の各区分との共通部分が存在するか
の判定によって行う。

【００２６】

【実施例】まず、図６に示すブロック図、および、図７
に示す機能ブロック図を用いて、グラフィックシステム
の一例について簡単に説明する。

【００２７】一般に、グラフィックシステムは、図７に
示すように制御部７０１、記憶部７０２、入力部７０
３、画像処理部７０７、表示部７１１、外部記憶装置７
１３等から構成される。これらの図７に示す各部は、具
体的には、たとえば図６に示すブロック図のように構成
される。すなわち、制御部７０１は中央処理装置（ＣＰ
Ｕ）６０１、記憶部７０２はメインメモリ（ＭＭ）６０
２、画像処理部７０７はグラフィックサブシステム６０
７、表示部７１１はＣＲＴ６１１から構成される。入力
部７０３はデータ入力を行うためのキーボード（ＫＢ）
６０３、マウス（ＭＯＵＳＥ）６０４、スタイラスペン
（ＰＥＮ）６０５、ダイアル（ＤＩＡＬ）６１２等から
構成され、外部記憶装置７１３は図形データ等を記憶保
存するファイリング装置（ＦＩＬＥ）６１３等から構成
される。上記制御部７０１（ＣＰＵ６０１）、入力部７
０３（キーボード６０３、マウス６０４、スタイラスペ
ン６０５、ダイアル６１２）、画像処理部７０７（グラ
フィックサブシステム６０７）、外部記憶装置７１３
（ファイリング装置６１３）は、システムバス７０６
（６０６）を介して接続され、データ交換を行う。又、
グラフィックサブシステム６０７は、グラフィックＬＳ
Ｉ６０８及びフレームメモリ（ＦＭ）６１０等から構成
され、フレームバス６０９を介して接続され、データ交
換を行う。

【００２８】図６に示すグラフィックシステムを用い
て、図形をＣＲＴ６１１に表示する過程について簡単に
説明する。

【００２９】先ず、キーボード６０３、マウス６０４、
スタイラスペン６０５、ダイアル６１２等の各種入力装
置によってデータを入力し、システムバス６０６を介し
てメインメモリ６０２に図形データを作成する。また
は、予め作成された図形データをファイリング装置６１
３よりシステムバス６０６を介してメインメモリ６０２
に転送する。ＣＰＵ６０１は、メインメモリ６０２内の
図形データを、必要ならば、キーボード６０３、マウス
６０４、スタイラスペン６０５、ダイアル６１２等の各
種入力装置からシステムバス６０６を介して送られる指
示に従って変更を加える。図形データの変更には、例え
ば、図形の回転、平行移動、視点の変更等の幾何演算や
後述するパラメトリック曲面の多角形による近似のため
の演算、パラメトリックトリミング曲線の折線による近
似のための演算、等を含んでいる。ＣＰＵ６０１は、上
記の様にして作成されたメインメモリ６０２内の図形デ
ータをシステムバス６０６を介して順次グラフィックサ
ブシステム６０７へ転送する。グラフィックサブシステ
ム６０７では、グラフィックＬＳＩ６０８が、送られて
くる図形データをＣＲＴ６１１に表示するために、幾何
的に（即ち、座標データとして）与えられた図形データ
及び図形種類（線分、多角形、等）に従って、ドット
（画素）によるイメージ（画像）を作成する。この処理
は、例えば、線分の座標データからＤＤＡ（Ｄｉｇｉｔ
ａｌＤｉｆｆｅｒｅｎｔｉａｌＡｎａｌｉｚｅｒ）
によってドット列を発生する処理や、多角形の座標デー
タから三次元ＤＤＡによって多角形内部を塗り潰すドッ
ト列を発生する処理等を含む。作成されたドットイメー
ジは、フレームメモリバス６０９を介してフレームメモ
リ６１０に転送され、最後に、グラフィックサブシステ
ム６０７は、フレームメモリ６１０のドットイメージを
赤，緑，青を示す信号であるＲＧＢ信号等に変換し、Ｃ
ＲＴ６１１はそれを表示する。

【００３０】次に、パラメトリック曲面のパラメトリッ
クトリミング曲線によるトリミングについて簡単に説明
する。

【００３１】図３は、２つの変数ＵおよびＶをパラメー
タとする２次元座標空間（ＵＶパラメタ空間）の或る領
域３０１から、３つの変数Ｘ，Ｙ，Ｚで定まる３次元座
標空間（ＸＹＺ空間）への像としてのパラメトリック曲
面３０２を表している。即ち、パラメトリック曲面３０
２は、２次元空間の或る領域（これを定義域と称する）
から３次元空間への写像ｓとして定義されるものであ
る。写像ｓは、通常コンピュータでの扱い易さからｕ及
びｖに関する多項式、又は、一旦４次元ＸＹＺＷ空間へ
の写像として定義しておき、後にこれを同次座標と見て
Ｗ座標で除する有理多項式が用いられる（これにより、
平行移動、拡大縮小、回転移動といった基本的な変換を
組み合わせた変換を、これらの基本的変換を表現する行
列式の乗算として表現することが可能となるというメリ
ットがある）。即ち、写像ｓは

【００３２】

【数１】

【００３３】又は

【００３４】

【数２】

【００３５】の形をしていると考え、以後の説明を行
う。ここで、写像ｘ，ｙ，ｚ，ｗは、ｕ及びｖに関する
多項式である。

【００３６】写像ｓの定義域は、通常、コンピュータで
の扱い易さから矩形が採られる。然しながら、このこと
は表示を行うグラフィックシステムの性能などの理由に
より、写像ｘ，ｙ，ｚ，ｗの次数を制限せざるを得ず、
延いてはパラメトリック曲面の形状に制約を与えること
になる。この制約を解消するために、写像ｓの定義域を
この定義域内に描かれた閉ループを用いて、この閉ルー
プの片側（閉ループの右側または左側）を切り取り、残
った部分のみを定義域とする方法が考案されている。こ
の方法をトリミングと称す。以後、何方でも同様なの
で、閉ループ上で反時計回りの方向を正方向とした場合
に閉ループの右側を切り取る側とし、左側を残す側とす
る。また、この閉ループをトリミングループと称す。

【００３７】図４により、上記のトリミングについて説
明する。トリミングループ４０１は、定義域３０１を制
限し、ループ４０１の左側（内側）を制限された定義域
とする。すると、定義域３０１からの写像ｓによる像で
あるパラメトリック曲面３０２も制限され、パラメトリ
ック曲面３０２の一部（これをトリム曲面と称す）４０
２のみとなる。この方法を用いることで、比較的低次の
多項式又は有理多項式を用いて、比較的自由な形状を作
り出すことが可能となる。

【００３８】通常、コンピュータでの扱い易さからトリ
ミングループもパラメトリックに（変数の関数として）
与えられる。トリミングループは、必ずしも一本の閉ル
ープである必要はなく、複数の互いに始点および終点の
みで連結した曲線の集まりとして定められていても良
い。その一本一本をトリミング曲線と称す。図５は、変
数Ｔの定義域であるＴパラメタ空間の或る領域５０１か
らＵＶパラメタ空間への像としてのパラメトリックトリ
ミング曲線５０２を表した図である。即ち、パラメトリ
ックトリミング曲線５０２とは、１次元空間の或る領域
（定義域）から２次元空間への写像ｃによる像として定
義されるものである。写像ｃは、通常コンピュータでの
扱い易さからｔに関する多項式、又は、一旦三次元ＵＶ
Ｈ空間への写像として定義しておき後にこれを同次座標
と見てＨ座標で除する有理多項式が用いられる（これに
より、平行移動、拡大縮小、回転移動といった基本的な
変換を組み合わせた変換を、これらの基本的変換を表現
する行列式の乗算として表現することが可能となるとい
うメリットがある）。即ち、写像ｃは

【００３９】

【数３】

【００４０】又は

【００４１】

【数４】

【００４２】の形をしていると考える。ここで、写像
ｕ，ｖ，ｈは、ｔに関する多項式である。

【００４３】次に、トリム曲面を描画する場合の処理に
ついての一例を説明する。この説明の為に、ＮＵＲＢ
（ｎｏｎ−ｕｎｉｆｏｒｍｒａｔｉｏｎａｌＢ−ｓ
ｐｌｉｎｅ）曲面のＮＵＲＢ曲線によるトリミングを例
に採るが、本発明はＮＵＲＢに特有の発明という訳では
ない。ＮＵＲＢ曲面及びＮＵＲＢ曲線は、制御点の集合
及びノット列と呼ばれる非減少列及び次数によって定ま
るパラメトリックな曲面及び曲線である。これらの制御
点、および、ノット列に関しては、“ＴｈｅＧｒａｐ
ｈｉｃａｌＰｒｅｃｅｓｓｉｎｇｏｆＢ−Ｓｐｌ
ｉｎｅｓｉｎａＨｉｇｈｌｙＤｙｎａｍｉｃＥ
ｎｖｉｒｏｎｍｅｎｔ”（ＳａｌｉｍＳ．Ａｂｉ−Ｅｚ
ｚｉ，１９８９）等に詳述されている。

【００４４】ＮＵＲＢ曲面ｓは、Ｕ方向の次数をｐ、Ｖ
方向の次数をｑ、制御点の集合をＰ_ij（１≦ｉ≦ｍ，１
≦ｊ≦ｎ）、Ｕ方向のノット列をｕ₁≦ｕ₂≦…≦ｕ
_m+p+1とするとき

【００４５】

【数５】

【００４６】によって定義される写像族｛η_ik｝、及
び、Ｖ方向のノット列をｖ₁≦ｖ₂≦…≦ｖ_n+q+1とする
とき

【００４７】

【数６】

【００４８】によって定義される写像族｛θ_ik｝を用い
て

【００４９】

【数７】

【００５０】の様に定義される区分パラメトリック曲面
である。定義域は、［ｕ_p+1，ｕ_m+1］×［ｖ_q+1，
ｖ_n+1］である。制御点Ｐ_ijが非同次座標（ｘ_ij，
ｙ_ij，ｚ_ij）であるか、又は、同次座標（ｘ_ij，ｙ_ij，
ｚ_ij，ｗ_ij）であるかによって、上記の式は

【００５１】

【数８】

【００５２】又は

【００５３】

【数９】

【００５４】の様に書き換えることが出来る。ｕ_i＜ｕ
_i+1且つｖ_j＜ｖ_j+1のとき、［ｕ_i，ｕ_i ₊₁］×［ｖ_j，ｖ
_j+1］に対して一つの区分が対応する。これを曲面スパ
ンと称す。

【００５５】同様に、ＮＵＲＢ曲線ｃは、次数をｒ、制
御点の集合をＱ_k（１≦ｋ≦ｌ）、ノット列をｔ₁≦ｔ₂
≦…≦ｔ_l+r+1とするとき

【００５６】

【数１０】

【００５７】によって定義される写像族｛ζ_lk｝を用い
て

【００５８】

【数１１】

【００５９】の様に定義される区分パラメトリック曲線
である。定義域は、［ｔ_r+1，ｔ_l+1］である。制御点Ｑ
_kが非同次座標（ｕ_k，ｖ_k）であるか、又は、同次座標
（ｕ_k，ｖ_k，ｈ_k）であるかによって、上記の式は

【００６０】

【数１２】

【００６１】又は

【００６２】

【数１３】

【００６３】の様に書き換えることが出来る。ｔ_k＜ｔ
_k+1のとき、［ｔ_k，ｔ_k+1］に対して一つの区分が対応
する。これを曲線スパンと称す。

【００６４】図１に、本発明の１実施例である、ＮＵＲ
Ｂ曲面のＮＵＲＢ曲線によるトリミングを含むトリム曲
面の表示処理の手順を表すフローチャートを示す。ま
た、図８に、この表示処理を行なうための、処理部の機
能ブロック図を示す（これらの機能ブロックを、図６の
ＣＰＵ６０１に備えればよい）。

【００６５】先ず、手順の全体の流れを概説する。通
常、ＮＵＲＢ曲面や他のプリミティブ（点、直線、多角
形、または文字列等）は、モデリング座標系（Ｍｏｄｅ
ｌｉｎｇＣｏｏｒｄｉｎａｔｅＳｙｓｔｅｍ．Ｍ
Ｃと略す）と呼ばれる個々の空間に定義され、その後総
てのプリミティブは同一のワールド座標系（Ｗｏｒｌｄ
ＣｏｏｒｄｉｎａｔｅＳｙｓｔｅｍ．ＷＣと略す）
へと変換される。次に、視点の指定及び視野の指定（通
常、視野の領域を示すために視野ピラミッドというもの
を指定する）により、例えばＺ座標の正方向から負方向
へ視線が伸び、視野ピラミッドがＸＹＺ空間の単位立方
体（視野領域）となるような正規化投影座標系（Ｎｏｒ
ｍａｌｉｚｅｄＰｒｏｊｅｃｔｉｏｎＣｏｏｒｄｉ
ｎａｔｅＳｙｓｔｅｍ．ＮＰＣと略す）へと変換され
る。次に、表示画面との比を考慮してデバイス座標系
（ＤｅｖｉｃｅＣｏｏｒｄｉｎａｔｅＳｙｓｔｅ
ｍ．ＤＣと略す）へと変換され、属性や変換過程の途中
で計算する輝度等の属性に従って表示される。総ての座
標系はＸＹＺの３次元であるが、制御点が同次座標で与
えられている場合などＸＹＺＷの４次元で考えた方が処
理に都合が良い場合がある。一般に、制御点のみで考え
る場合は同次座標で考え、実際の曲面上の座標を考える
場合は非同次座標で考えると都合が良い。以下も特に断
わらない限りこのように考えるものとする。

【００６６】次に、上記の概説について、図１および図
８を用いて詳細に述べるが、本実施例は一例であり、こ
の通りに実行しなければならないという訳ではない。

【００６７】先ず、変換部８０１により、制御点をワー
ルド座標系へ変換する（ステップ１０１）。次に、変換
部８０２により、制御点をコピーし、そのコピーした制
御点を正規化投影座標系へ変換する（ステップ１０
２）。次に、チェック部８０３により、制御点のコピー
に対し、視野領域に入っているかを判定する（ステップ
１０３）。次に、ステップ１２０に進み、総ての制御点
についてステップ１０１乃至ステップ１０３の処理が終
了したかを判定する。終了していない場合にはステップ
１０１に戻り、ステップ１０１乃至ステップ１０３を繰
り返す。終了している場合にはステップ１２１に進み、
総ての制御点が視野領域に入っているか否かを判定す
る。総ての制御点が入っていない場合には、表示処理を
終了する。視野領域に入っている制御点が有る場合に
は、ステップ１０４に進む。

【００６８】ステップ１０４においては、次に、展開部
８０４により、曲面スパンにおいてＮＵＲＢ曲面をベジ
ェ曲面に展開する。ＮＵＲＢ曲面（又は曲線）をベジェ
曲面（又は曲線）に展開するには、Ｃｏｘ−ｄｅＢｏｏ
ｒアルゴリズムと呼ばれる方法が知られている。ベジェ
曲面に展開するのは、以後の処理を簡単にする為であ
り、必ずしも必要な処理ではない。

【００６９】ベジェ曲面は、Ｕ方向の次数をｐ、Ｖ方向
の次数をｑ、制御点の集合をＰ_ij（１≦ｉ≦ｐ＋１，１
≦ｊ≦ｑ＋１）とするとき

【００７０】

【数１４】

【００７１】によって定義される写像族｛Ｂ_ik｝を用い
て

【００７２】

【数１５】

【００７３】の様に定義されるパラメトリック曲面であ
る。定義域は、通常［０，１］×［０，１］であるが、
パラメータを適当に変換することにより任意の矩形とし
て良い。制御点Ｐ_ijが非同次座標（ｘ_ij，ｙ_ij，ｚ_ij）
であるか、又は、同次座標（ｘ_ij，ｙ_ij，ｚ_ij，ｗ_ij）
であるかによって、上記の式は

【００７４】

【数１６】

【００７５】又は

【００７６】

【数１７】

【００７７】の様に書き換えることが出来る。

【００７８】同様に、ベジェ曲線ｃは、次数をｒ、制御
点の集合をＱ_k（１≦ｋ≦ｌ）とするとき、上記の写像
族｛Ｂ_ik｝を用いて

【００７９】

【数１８】

【００８０】の様に定義されるパラメトリック曲線であ
る。定義域は、通常［０，１］であるが、パラメータを
適当に変換することにより任意の閉区間として良い。制
御点Ｑ_kが非同次座標（ｕ_k，ｖ_k）であるか、又は、同
次座標（ｕ_k，ｖ_k，ｈ_k）であるかによって、上記の式
は

【００８１】

【数１９】

【００８２】又は

【００８３】

【数２０】

【００８４】の様に書き換えることが出来る。

【００８５】次に、変換部８０５により、ベジェ制御点
をコピーし、そのコピーした制御点を正規化投影座標系
へ変換する（ステップ１０５）。この後、チェック部８
０６により、制御点のコピーに対し、視野領域に入って
いるかを判定する（ステップ１０６）。次に、ステップ
１３０に進み、総ての制御点についてステップ１０４乃
至ステップ１０６の処理が終了したかを判定する。終了
していない場合にはステップ１０４に戻り、ステップ１
０４乃至ステップ１０６を繰り返す。終了している場合
にはステップ１３１に進み、総ての制御点が視野領域に
入っているか否かを判定する。総ての制御点が入ってい
ない場合には、ステップ１３２に進む。

【００８６】制御点が一点でも視野領域内に入っている
場合には、計算部８０７により、この曲面スパンの分割
数を計算する（ステップ１０７）。分割数を計算するに
は、例えば、前出の“Ｓｕｒｆａｃｅａｌｇｏｒｉｔ
ｈｍｓｕｓｉｎｇｂｏｕｎｄｓｏｎｄｅｒｉｖ
ａｔｉｖｅｓ”や“Ｒｅａｌ−ｔｉｍｅｒｅｎｄｅｒ
ｉｎｇｏｆｔｒｉｍｍｅｄｓｕｒｆａｃｅｓ”等
に記載されている方法で計算すれば良い。ステップ１３
２においては、総ての曲面スパンに対してステップ１０
４乃至ステップ１０７の処理が行なわれたか否かを調べ
る。処理が行なわれていない曲面スパンがある場合に
は、ステップ１０４へ戻る。総ての曲面スパンに対して
処理が行なわれている場合には、ステップ１０８へ進
む。

【００８７】ステップ１０８においては、トリミング曲
線の分割数を計算し、近似部８０８により、折線により
近似する。ステップ１０８における処理の詳細は、後述
する。次に、ステップ１３３において、ステップ１０８
の処理が総てのトリミング曲線に対して行なわれたか否
かを判定する。処理が行なわれていないトリミング曲線
が有る場合には、ステップ１０８の処理を繰り返す。

【００８８】次に、写像ｓの定義域［ｕ_p+1，ｕ_m+1］×
［ｖ_q+1，ｖ_n+1］を、各曲面スパンの分割数及びトリミ
ング曲線の屈曲点に従って分割する（ステップ１０
９）。分割された小片のそれぞれをセルと称す。セル
は、矩形又は矩形を更に対角線で分割した三角形であ
る。尚、トリミング曲線の屈曲点とは、Ｕ座標の傾きが
正から負へ変化し且つＶ座標の傾きが負のとき、又は、
Ｕ座標の傾きが負から正へ変化し且つＶ座標の傾きが正
のときのＶ座標、及び、Ｖ座標の傾きが正から負へ変化
し且つＵ座標の傾きが正のとき、又は、Ｖ座標の傾きが
負から正へ変化し且つＵ座標の傾きが負のときのＵ座標
のことである。屈曲点での分割を行うのは、トリミング
された後のセルの各辺が単調になるようにするためであ
る。

【００８９】次に、トリミング部８０９により、各トリ
ミング曲線と各セルとの交点計算を行いながら、各セル
をトリミングする（ステップ１１０）。トリミングされ
たセルは、上記に説明したように多角形となる。以後の
処理は、この多角形に対して行う。又は、適当な細分を
行って三角形に分割して行っても良い。

【００９０】次に、クリッピング部８１０により、トリ
ミングされたセルのＸＹＺ空間（正規化投影座標系）へ
の像をクリッピングする（ステップ１１１）。最後に、
変換部８１１により、セルをデバイス座標系へ変換し
（ステップ１１２）、属性及び上記で述べてはいないが
変換過程の途中で計算される輝度等の属性に従って表示
する（ステップ１１３）。ステップ１３４において、総
てのセルに対してステップ１１１乃ステップ１１３の処
理が行なわれたか否かを判定し、処理が行なわれていな
いセルが有る場合には、ステップ１１１へ戻る。総ての
セルに対して処理が行なわれている場合には、表示処理
を終了する。

【００９１】図２に、ステップ１０８の処理を詳しく説
明するためのフローチャートを示す。また、図９に、こ
の処理を実行するための処理部の、機能ブロック図を示
す（この機能ブロックは、図８の近似部８０８内に備え
られる）。以下、図２および図９により、ステップ１０
８の処理を説明する。

【００９２】先ず、展開部９０１により、曲線スパンに
おいてＮＵＲＢ曲線をベジェ曲線に展開する（ステップ
２０１）。矢張、ベジェ曲線に展開するのは、以後の処
理を簡単にする為であり、必ずしも必要な処理ではな
い。次に、判定部９０２により、ベジェ曲線が曲面スパ
ンと交叉するか否かを判定する（ステップ２０２）。交
叉しなければ、以後の処理は行わない。交叉する場合に
は、以下の各ステップの処理を行う。

【００９３】ここで、交叉の判定について、説明する。

【００９４】一般的には（曲線および曲面がベジェでな
い場合には）、交叉の判定を行うには、合成写像ｓ・ｃ
のパラメタ範囲は、パラメトリックトリミング曲線ｃの
値域とパラメトリック曲面の各区分との共通部分が存在
するかを判定する。そして、共通部分が存在するときに
限り共通部分が存在する範囲をパラメタ範囲として（ｓ
・ｃ）′又は（ｓ・ｃ）″の最大値を求める。

【００９５】本実施例のように、曲線および曲面がベジ
ェである場合には、ベジェ曲線の制御点に対し、総ての
制御点が曲面スパンに入っていなければ交叉をしないも
のとして判定する。一つでも入っている場合には、交叉
するものとして以下の処理を行うが、交叉しない場合も
あり得る。然し、交叉しない場合でも以後の処理で上手
く処理されるので、ここでは問題としない。

【００９６】次に、合成部９０３により、曲面スパンに
おけるベジェ曲面にベジェ曲線を代入し合成写像を作成
する（ステップ２０３）。この合成写像の定義域は、曲
線スパンを［ｔ_k，ｔ_k+1］、ベジェ曲線をｃ、曲面スパ
ンを［ｕ_i，ｕ_i+1］×［ｖ_j，ｖ_j+1］とするとき、［ｔ
_k，ｔ_k+1］∩｛ｔ∈［ｔ_k，ｔ_k+1］｜ｃ（ｔ）∈
［ｕ_i，ｕ_i+1］×［ｖ_j，ｖ_j+1］｝である。この定義域
をＴと置く。定義域Ｔを求めるには、ベジェ曲線ｃと曲
面スパン［ｕ_i，ｕ_i+1］×［ｖ_j，ｖ_j+1］の境界での交
点計算によって求めることが出来る。

【００９７】次に、計算部９０４により、定義域Ｔにお
けるベジェ曲線ｃの分割数を計算する（ステップ２０
４）。

【００９８】ここで、分割数の計算方法について、説明
する。その為に、曲線スパンを［ｔ_k，ｔ_k+1］、ベジェ
曲線の次数をｒ、制御点の集合をＱ_k（１≦ｋ≦ｌ）、
ベジェ曲線をｃ、曲面スパンを［ｕ_i，ｕ_i+1］×
［ｖ_j，ｖ_j+1］、ベジェ曲面のＵ方向の次数をｐ、Ｖ方
向の次数をｑ、制御点の集合をＰ_ij（１≦ｉ≦ｐ＋１，
１≦ｊ≦ｑ＋１）ベジェ曲面をｓ、合成写像ｓ・ｃの定
義域をＴとする。

【００９９】第一の分割数の計算方法においては、ベジ
ェ曲線ｃの折線近似の各線分の長さを一定値Ｌ以下に抑
えるために、合成写像ｓ・ｃの一次微分（ｓ・ｃ）′の
大きさのＴでの最大値Ｍ１を求め、ベジェ曲線ｃの折線
近似の為の分割数をＭ１／Ｌとする。このように分割数
を決めると折線近似の各線分の長さを一定値Ｌ以下に抑
えることができることの理論的な根拠は、“Ｔｈｅｇ
ｒａｐｈｉｃａｌｐｒｏｃｅｓｓｉｎｇｏｆＢ−
ｓｐｌｉｎｅｉｎａｈｉｇｈｌｙｄｙｎａｍｉ
ｃｅｎｖｉｒｏｎｍｅｎｔ，Ｓ．Ｓ．Ａｂｉ−Ｅ
ｚｚｉ著，Ｒｅｎｓｓｅｌａｒｐｏｌｙｔｅｃｈｎｉ
ｃｉｎｓｔｉｔｕｔｅ，１９８９年発行”のｐ．１５
４を中心に記載されている。最大値Ｍ１は、ベジェ曲面
ｓ及びベジェ曲線ｃが共に多項式である場合、

【０１００】

【数２１】

【０１０１】であることを用いて

【０１０２】

【数２２】

【０１０３】のように決定しても良い。このとき、合成
写像ｓ・ｃの定義域Ｔは最早関係がなくなる。従って、
このようにして最大値Ｍ１を評価する（決定する）場合
には、ベジェ曲線ｃと曲面スパン［ｕ_i，ｕ_i+1］×［ｖ
_j，ｖ_j+1］の境界での交点計算は必要なくなる。尚、ベ
ジェ曲面ｓ又はベジェ曲線ｃが有理多項式である場合
も、分子と分母に分け、分子は上記の方法で分母は最大
値の代わりに最小値を計算することで同様に計算出来
る。

【０１０４】第二の分割数の計算方法においては、ベジ
ェ曲線の折線近似とベジェ曲線ｃの真値からの誤差を一
定値（これをＴＯＬとする）以下に抑えるために、合成
写像ｓ・ｃの二次微分（ｓ・ｃ）″の大きさのＴでの最
大値Ｍ２を求め、ベジェ曲線ｃの折線近似の為の分割数
を√（Ｍ２／（８×ＴＯＬ））とする。このように分割
数を決めると折線近似の各線分の長さを一定値ＴＯＬ以
下に抑えることができることの理論的な根拠は、“Ｔｈ
ｅｇｒａｐｈｉｃａｌｐｒｏｃｅｓｓｉｎｇｏｆ
Ｂ−ｓｐｌｉｎｅｉｎａｈｉｇｈｌｙｄｙｎ
ａｍｉｃｅｎｖｉｒｏｎｍｅｎｔ”のｐ．１５７を中
心に記載されている。最大値Ｍ２は、ベジェ曲面ｓ及び
ベジェ曲線ｃが共に多項式である場合、

【０１０５】

【数２３】

【０１０６】であることを用いて

【０１０７】

【数２４】

【０１０８】のように決定しても良い。このとき、合成
写像ｓ・ｃの定義域Ｔは最早関係がなくなる。従って、
このようにして最大値Ｍ２を評価する（決定する）場合
には、ベジェ曲線ｃと曲面スパン［ｕ_i，ｕ_i+1］×［ｖ
_j，ｖ_j+1］の境界での交点計算は必要なくなる。尚、ベ
ジェ曲面ｓ又はベジェ曲線ｃが有理多項式である場合
も、分子と分母に分け、分子は上記の方法で計算し、分
母は最大値の代わりに最小値を計算することで同様に計
算出来る。

【０１０９】最後に、処理部９０５により、曲面スパン
におけるベジェ曲線をステップ２０４で求めた分割数に
より折線で近似する（ステップ２０５）。ステップ２１
０において、ステップ２０２乃至ステップ２０５の処理
が総ての曲面スパンに対して行なわれたか否かを判定
し、行なわれていない場合にはステップ２０２へ戻る。
総ての曲面スパンに対して行なわれた場合には、ステッ
プ２１１において、総ての曲線スパンに対して処理が行
なわれたか否かを判定し、行なわれていない場合にはス
テップ２０１へ戻る。総ての曲線スパンに対して行なわ
れた場合には、表示処理を終了する。

【０１１０】上記において、各ベジェ曲線のＸＹＺ空間
への像を考えている訳であるが、ＸＹＺ空間は、ワール
ド座標系でも正規化投影座標系でもデバイス座標系でも
何方でも良い。然し、好ましくは、最終的に表示される
デバイス座標系で考えた方が良い。

【０１１１】又、正規化投影座標系又はデバイス座標系
で考えたとき、Ｚ座標は余り意味を持たない。従って、
（ｓ・ｃ）′又は（ｓ・ｃ）″の大きさを考えるときに
Ｚ座標は無視して考えても良い。

【０１１２】以上で述べた方法によって、曲面及びトリ
ミング曲線の分割数を決定し、トリミングを行った結
果、トリム曲面はセルに分割される。分割されたセル
は、変数変換を受け、図６に示したグラフィックサブシ
ステム６０７に送られる。グラフィックサブシステム６
０７では、グラフィックＬＳＩ６０８が、ドットイメー
ジデータを作成する。このとき、トリミング曲線の真値
とグラフィックＬＳＩ６０８に入力される折線とは、上
記の方法によってある一定値の誤差ＴＯＬで抑えられて
いる。又、グラフィックＬＳＩ６０８に送られる座標デ
ータは、一般に浮動小数であるが、作成されるドットデ
ータは、四捨五入（又は切捨て）等によって整数に丸め
られる。丸めによる誤差は、最大１／√２である。従っ
て、トリミング曲線の真値と表示されるドットイメージ
との最大誤差はＴＯＬ＋１／√２となる。

【０１１３】一方、グラフィックＬＳＩ６０８におい
て、ドットの存在する割合を考慮し、輝度を廻りのドッ
トに分散して表示するアンチエイリアスの技術がある。
通常、アンチエイリアスは、隣接１ドットの廻りに対し
分散を行うので、本発明において、ＴＯＬ＋１／√２＜
１となる様にＴＯＬを選び、アンチエイリアスの手法を
用いることで、表示上誤差のない結果が得られる。

【０１１４】又、本発明を、トリミングされた二つの曲
面をエッジであわせたような図形を表示することに用い
る場合、共にＴＯＬの誤差で評価したとすると、二つの
エッジをそれぞれドットイメージにしたとき、それらの
間の最大誤差は２（ＴＯＬ＋１／√２）である。このと
き、アンチエイリアスを、例えば、隣接する２（＞２
（ＴＯＬ＋１／√２））ドットの廻りに対し分散を行う
ようにすることで、表示上隙間のない結果が得られるよ
うになる。

【０１１５】

【発明の効果】上記のように、本発明によれば、ユーザ
により誤差の許容値を指定されると、トリミングによっ
て生じるパラメトリック曲面のエッジの誤差を、前記指
定された値以下に抑えることを可能とするための、パラ
メトリックトリミング曲線の折線近似方法を備えたグラ
フィックシステムを提供することができる。

【図面の簡単な説明】

【図１】トリム曲面の表示手順の一例を表すフローチャ
ートの図である。

【図２】トリミング曲線の折線近似の手順を表すフロー
チャートの図である。

【図３】パラメトリック曲面を説明するための図であ
る。

【図４】トリミングを説明するための図である。

【図５】パラメトリックトリミング曲線を説明するため
の図である。

【図６】グラフィックシステムの一例を表すブロック図
である。

【図７】グラフィックシステムの一例を表す機能ブロッ
ク図である。

【図８】トリム曲面の表示処理を行なう処理部の機能ブ
ロック図である。

【図９】トリミング曲線の折線近似処理を行なう処理部
の機能ブロック図である。

【符号の説明】

６０１…中央処理装置（ＣＰＵ）、６０２…メインメモ
リ（ＭＭ）、６０３…キーボード（ＫＢ）、６０４…マ
ウス（ＭＯＵＳＥ）、６０５…スタイラスペン（ＰＥ
Ｎ）、６０６…システムバス、６０７…グラフィックサ
ブシステム、６０８…グラフィックＬＳＩ、６０９…フ
レームバス、６１０…フレームメモリ（ＦＭ）、６１１
…ＣＲＴ、６１２…ダイアル（ＤＩＡＬ）、６１３…フ
ァイリング装置（ＦＩＬＥ）。

───────────────────────────────────────────────────── フロントページの続き (72)発明者桑名利幸茨城県日立市大みか町五丁目２番１号株式会社日立製作所大みか工場内

Claims

【特許請求の範囲】

【請求項１】少なくとも、入力装置、記憶装置、演算装
置、および、表示装置を備え、パラメトリック曲面の定
義式または制御点の集合、および、前記曲面をトリミン
グするためのパラメトリックなトリミング曲線の定義式
または制御点の集合を記憶装置に保持し、前記演算装置
において前記パラメトリック曲面を開多面体または閉多
面体により近似し、前記演算装置において前記パラメト
リックなトリミング曲線を折線により近似して、前記パ
ラメトリック曲面およびパラメトリックなトリミング曲
線を前記表示装置に表示する際に、前記トリミング曲線の折線による近似の精度について、
外部から指定される任意の値の許容誤差値を前記入力装
置により受付けて、記憶装置に保持し、前記指定された許容誤差値に基づいて、前記トリミング
曲線を折線により近似する際の折線の数を決定するため
の式を前記記憶装置に予め備え、前記演算装置により前
記折線の数を決定することを特徴とする、折線近似によ
りパラメトリックトリミング曲線を表示する方法。
【請求項２】請求項１記載の折線近似によりパラメトリ
ックトリミング曲線を表示する方法は、前記トリミング曲線が、１つの変数ｔをパラメタとしｃ
（ｔ）＝（ｕ（ｔ），ｖ（ｔ））である写像ｃで与えら
れ、前記パラメトリック曲面が、２つの変数ｕおよびｖをパ
ラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，ｖ），ｙ（ｕ，
ｖ），ｚ（ｕ，ｖ））である写像ｓにより与えられ、前記許容誤差値がＬで指定されるとき、前記トリミング曲線を折線により近似する際の折線の数
を決定するための式は、合成写像ｓ・ｃのｔによる一次微分（ｓ・ｃ）′の大き
さの、前記トリミング曲線のパラメタｔの範囲内での最
大値Ｍ１を前記演算装置により求め、前記折線の数をＭ
１／Ｌと決定するための式であることを特徴とする、折
線近似によりパラメトリックトリミング曲線を表示する
方法。
【請求項３】請求項１記載の折線近似によりパラメトリ
ックトリミング曲線を表示する方法は、前記トリミング曲線が、１つの変数ｔをパラメタとしｃ
（ｔ）＝（ｕ（ｔ），ｖ（ｔ））である写像ｃで与えら
れ、前記パラメトリック曲面が、２つの変数ｕおよびｖをパ
ラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，ｖ），ｙ（ｕ，
ｖ），ｚ（ｕ，ｖ））である写像ｓにより与えられ、前記許容誤差値がＴＯＬで指定されるとき、前記トリミング曲線を折線により近似する際の折線の数
を決定するための式は、合成写像ｓ・ｃのｔによる二次微分（ｓ・ｃ）″の大き
さの、前記トリミング曲線のパラメタｔの範囲内での最
大値Ｍ２を前記演算装置により求め、前記折線の数を√
（Ｍ２／（８×ＴＯＬ））と決定するための式であるこ
とを特徴とする、折線近似によりパラメトリックトリミ
ング曲線を表示する方法。
【請求項４】請求項２または３において、前記パラメトリック曲面が、複数の曲面（各曲面を区分
と称する）の和集合として与えられている場合には、前記パラメトリックトリミング曲線ｃの写像ｓによる値
域と、前記パラメトリック曲面の各区分との共通部分が
存在するか否かを前記演算装置により判定し、共通部分
が存在するときに限り、共通部分が存在する範囲を合成
写像ｓ・ｃのパラメタ範囲として、（ｓ・ｃ）′又は
（ｓ・ｃ）″の大きさの最大値を求めることを特徴とす
る、折線近似によりパラメトリックトリミング曲線を表
示する方法。
【請求項５】請求項４において、前記パラメトリック曲面が、複数の曲面（各曲面を区分
と称する）の和集合として与えられ、且つ、前記パラメ
トリックトリミング曲線が制御点の集合で定義され且つ
凸包性を有する場合には、前記パラメトリックトリミング曲線を定義する制御点の
集合の写像ｓによる値域と、前記パラメトリック曲面の
各区分との共通部分が存在するか否かを前記演算装置に
より判定し、前記パラメトリックトリミング曲線の値域
とパラメトリック曲線の各区分との共通部分が存在する
か否かの判定を行うことを特徴とする、折線近似により
パラメトリックトリミング曲線を表示する方法。
【請求項６】パラメトリック曲面の定義式または制御点
の集合、および、前記曲面をトリミングするためのパラ
メトリックなトリミング曲線の定義式または制御点の集
合を記憶装置に保持し、前記演算装置において前記パラ
メトリック曲面を開多面体または閉多面体により近似
し、前記演算装置において前記パラメトリックなトリミ
ング曲線を折線により近似して、前記パラメトリック曲
面およびパラメトリックなトリミング曲線を前記表示装
置に表示するグラフィック表示システムにおいて、前記トリミング曲線の折線による近似の精度について、
外部から指定される任意の値の許容誤差値を入力する入
力手段と、前記入力された許容誤差値を保持する第１の記憶手段
と、前記入力された許容誤差値に基づいて、前記トリミング
曲線を折線により近似する際の折線の数を決定するため
の式を予め保持する第２の記憶手段と、前記式に基づき前記折線の数を決定する決定手段と、を備えることを特徴とするグラフィック表示システム。
【請求項７】請求項６記載のグラフィック表示システム
において、前記トリミング曲線が、１つの変数ｔをパラメタとしｃ
（ｔ）＝（ｕ（ｔ），ｖ（ｔ））である写像ｃで与えら
れ、前記パラメトリック曲面が、２つの変数ｕおよびｖをパ
ラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，ｖ），ｙ（ｕ，
ｖ），ｚ（ｕ，ｖ））である写像ｓにより与えられ、前記許容誤差値がＬで指定されるとき、前記トリミング曲線を折線により近似する際の折線の数
を決定するための式は、合成写像ｓ・ｃのｔによる一次微分（ｓ・ｃ）′の大き
さの、前記トリミング曲線のパラメタｔの範囲内での最
大値Ｍ１を前記演算装置により求め、前記折線の数をＭ
１／Ｌと決定するための式であることを特徴とするグラ
フィック表示システム。
【請求項８】請求項１記載のグラフィック表示システム
において、前記トリミング曲線が、１つの変数ｔをパラメタとしｃ
（ｔ）＝（ｕ（ｔ），ｖ（ｔ））である写像ｃで与えら
れ、前記パラメトリック曲面が、２つの変数ｕおよびｖをパ
ラメタとしｓ（ｕ，ｖ）＝（ｘ（ｕ，ｖ），ｙ（ｕ，
ｖ），ｚ（ｕ，ｖ））である写像ｓにより与えられ、前記許容誤差値がＴＯＬで指定されるとき、前記トリミング曲線を折線により近似する際の折線の数
を決定するための式は、合成写像ｓ・ｃのｔによる二次微分（ｓ・ｃ）″の大き
さの、前記トリミング曲線のパラメタｔの範囲内での最
大値Ｍ２を前記演算装置により求め、前記折線の数を√
（Ｍ２／（８×ＴＯＬ））と決定するための式であるこ
とを特徴とするグラフィック表示システム。
【請求項９】請求項７または８において、前記パラメトリック曲面が、複数の曲面（各曲面を区分
と称する）の和集合として与えられている場合に、前記パラメトリックトリミング曲線ｃの写像ｓによる値
域と、前記パラメトリック曲面の各区分との共通部分が
存在するか否かを判定する判定手段と、前記判定手段により共通部分が存在すると判定された場
合に、前記共通部分が存在する範囲を合成写像ｓ・ｃの
パラメタ範囲として、（ｓ・ｃ）′又は（ｓ・ｃ）″の
大きさの最大値を求める最大値算出手段と、を備えることを特徴とするグラフィック表示システム。
【請求項１０】請求項９において、前記パラメトリック曲面が、複数の曲面（各曲面を区分
と称する）の和集合として与えられ、且つ、前記パラメ
トリックトリミング曲線が制御点の集合で定義され且つ
凸包性を有する場合に、前記判定手段として、前記パラメトリックトリミング曲線を定義する制御点の
集合の写像ｓによる値域と、前記パラメトリック曲面の
各区分との共通部分が存在するか否かを判定する制御点
判定手段と、を備えることを特徴とするグラフィック表示システム。