JPH076232A - ベツィエスプラインを描写するようにハイブリッドフォワード相違プロセスを行うシステム及び方法 - Google Patents

ベツィエスプラインを描写するようにハイブリッドフォワード相違プロセスを行うシステム及び方法

Info

Publication number
JPH076232A
JPH076232A JP5163592A JP16359293A JPH076232A JP H076232 A JPH076232 A JP H076232A JP 5163592 A JP5163592 A JP 5163592A JP 16359293 A JP16359293 A JP 16359293A JP H076232 A JPH076232 A JP H076232A
Authority
JP
Japan
Prior art keywords
magnitude
bezier
function
test
error
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.)
Pending
Application number
JP5163592A
Other languages
English (en)
Inventor
James A Goossen
エイ グーセン ジェームズ
Kirk O Olynyk
オー オリニク カーク
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.)
Microsoft Corp
Original Assignee
Microsoft 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 Microsoft Corp filed Critical Microsoft Corp
Publication of JPH076232A publication Critical patent/JPH076232A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T1/00—General purpose image data processing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—Two-dimensional [2D] image generation
    • G06T11/20—Drawing from basic elements
    • G06T11/23—Drawing from basic elements using straight lines or curves
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/17—Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • Algebra (AREA)
  • Image Generation (AREA)
  • Pharmaceuticals Containing Other Organic And Inorganic Compounds (AREA)
  • Control Of Electric Motors In General (AREA)
  • Complex Calculations (AREA)
  • Image Processing (AREA)
  • Reduction Or Emphasis Of Bandwidth Of Signals (AREA)
  • Feedback Control In General (AREA)

Abstract

(57)【要約】 【目的】 コンピュータグラフィックシステムにおいて
ベツィエスプラインを近似するための計算効率の良いシ
ステム及び方法を提供する。 【構成】 ベツィエ曲線を描写する高速で且つメモリ効
率の高いシステム及び方法であって、ベツィエ制御ポイ
ントによって定められたベツィエ曲線を表すハイブリッ
ドフォワード相違関数を使用し、少数の直線セグメント
で曲線を描写することができ、公知の反復細分化技術を
用いて計算されたものと同じベツィエ制御ポイントを生
じるように曲線を描写し、この反復細分化によって導出
されない線セグメント近似は拒絶し、ベツィエ曲線のい
ずれの端でもスタートできて、同じ近似を描写すること
ができ、しかも、コンピュータで容易に実施できると共
に、いかなる次数のベツィエ曲線にも適用できるシステ
ム及び方法。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、ベツィエスプラインを
描写するシステム及び方法に係る。より詳細には、本発
明は、限定された一連の直線セグメントでベツィエスプ
ラインを近似することによりコンピュータグラフィック
システムにおいて曲線を模擬するシステム、方法及び装
置に係る。
【０００２】
【従来の技術】コンピュータシステムは、多量のデータ
をコンパイルし同化するのに非常に有用である。コンピ
ュータシステムは、曲線を表示することのできるグラフ
ィックディスプレイをしばしば備えている。図１は、典
型的なグラフィックディスプレイシステムに表示するこ
とのできる曲線２を示している。
【０００３】グラフィックディスプレイシステムは、一
般に、表示されるべき曲線のデジタル表示を記憶するた
めのメモリを備えている。初期のシステムでは、表示さ
れるべき曲線を表すデジタル値を記憶する非常に大きな
メモリを含むことがあった。この方法を用いた高解像度
のディスプレイシステムは非常に大きなメモリを必要と
する。このような初期のシステムは、曲線を表すデジタ
ル値を最初に発生するときに著しく低速である上に、曲
線をディスプレイ上で回転したり配置し直したりすると
きのように曲線を操作するときにも低速である。これら
の問題により、ほとんどのコンピュータディスプレイシ
ステムは、曲線モデルを形成するベツィエスプライン方
法を使用している。
【０００４】ベツィエ曲線ともしばしば称するベツィエ
スプラインは、曲線及びカーブした表面に対する数学的
な構造体である。二次元グラフィックシステムに最も頻
繁に使用されているベツィエ曲線は、立方ベツィエ曲線
である。立方ベツィエ曲線は曲線を定義する４つの制御
ポイントを必要とする。４つのポイントが特定される
と、曲線が定義される。しかしながら、当業者に明らか
なように、より高次のベツィエ曲線を使用して、非常に
複雑な曲線を二次元、三次元又はそれより高い次元にお
いて形成することができる。
【０００５】立方ベツィエ曲線を使用して図１の曲線２
のような任意の曲線を構成するために、曲線が多数の個
々の弧に仕切られる。これが図１に示されており、曲線
２は３つの弧に分割されている。ポイント４と６との間
で曲線２は弧８に分割され、ポイント６と８との間で曲
線２は弧１２に分割され、そしてポイント１０と１４と
の間で曲線２は弧１６に分割されている。立方ベツィエ
曲線を用いて弧８を構成するために、弧の端末ポイント
４及び６と、２つの追加ポイント、即ち制御ポイント１
８及び２０とが選択される。これらの制御ポイント１８
及び２０と、端末ポイント４及び６とを適当に選択する
ことにより、公知の反復プロセスを用いて弧８を発生す
ることができる。このプロセスは、弧１２及び１６につ
いても、それらの選択した制御ポイントを使用して繰り
返される。従って、１０個のベツィエ制御ポイントによ
って曲線２を定めることができる。同様に、ベツィエ曲
線技術を用いて１組の選択した制御ポイントからほとん
どの所望の曲線を発生することができる。
【０００６】ベツィエ曲線は、データポイントの小さな
組によって曲線を描くことができるが、ベツィエ曲線自
体をディスプレイスクリーン上に表示すべきときには、
ディスプレイスクリーン上の一連のポイントに対するデ
ータ値、即ち曲線をトレースするピクセルと称するもの
を指定しなければならない。曲線の弧上の各個々のデー
タポイントを決定するのは、計算効率の悪い低速なプロ
セスであるから、ベツィエ曲線を近似するのが非常に有
益であると分かっている。これを行う利点は、直線セグ
メントの限定された組でベツィエ曲線を非常に厳密に近
似できることである。必要な線セグメントの本数は、所
望の曲線の曲率及びディスプレイスクリーンの解像度を
含む多数の要因によって左右される。直線セグメントの
限定された組によって弧を近似するのが特に効果的であ
る。というのは、線セグメントを構成する１組のポイン
トを決定するのは非常に効率的に行えるからである。ベ
ツィエ曲線を、その曲線又は少なくとも曲線の弧を近似
する１組の直線セグメントに変換することを、曲線を
「描写する」と称する。
【０００７】上記の説明は、プリンタ及びディスプレイ
スクリーンに等しく適用できることに注意されたい。典
型的なレーザプリンタのピクセルサイズは、典型的なビ
デオディスプレイスクリーンのピクセルサイズとは異な
る。しかしながら、レーザプリンタや、他の形式のグラ
フィックプリンタ、例えば、ピクセルを使用しないベク
トルプロッタに曲線を描写するときには、ディスプレイ
スクリーン上にベツィエ曲線を描写する際に遭遇する同
じ問題が生じる。
【０００８】ベツィエ曲線を描写する典型的な公知の方
法は、反復細分化として知られている。この方法が図２
に示されており、ここでは、１組の線セグメントによっ
て弧２２が厳密に近似される。弧２２の端末ポイント２
４及び２６と称する２つの制御ポイントと、制御ポイン
ト２８及び３０が、立方ベツィエ曲線を介して弧２２を
定める。これら４つの制御ポイントは良く知られたやり
方で決定される。曲線を描写する最初の段階は、ポイン
ト２４と２６との間に延びる線セグメント３８が弧２２
を「充分に厳密」に近似するものであって、線セグメン
ト３８を弧２２の近似として表示することができるかど
うかを決定することである。線セグメントがディスプレ
イスクリーンの解像度内（即ちスクリーン上に実際の弧
を配置すべきところのピクセル内）にある場合には、そ
れ以上計算しても表示の質的な改善は生じない。実際の
解像度はディスプレイ装置によって左右される。例え
ば、典型的なビデオディスプレイターミナルでは、１イ
ンチあたり７２ピクセルであり、一方、レーザプリンタ
は１インチあたり３００又は６００ピクセルである。従
って、計算精度の程度はディスプレイ装置によって左右
される。
【０００９】反復細分化プロセスにおいてエラーの量を
決定する方法は、ポイント２４と２６との間に延びる線
セグメント３８を形成することである。次いで、線セグ
メント３８に垂直で且つ制御ポイント２８を通って延び
る線セグメント４０の大きさと、同様に線セグメント３
８に垂直であるがポイント３０を通って延びる線セグメ
ント４２の大きさとを決定する。これらの線セグメント
４０及び４２の大きさは、これらの両方が１ピクセルの
大きさのような所定のテスト大きさよりも小さいかどう
かについてチェックされる。線セグメント４０及び４２
の両方がテスト大きさよりも小さい場合には、線セグメ
ント３８は弧２２の充分に厳密な近似であって弧として
表示できると考えられる。
【００１０】しかしながら、いずれかの線セグメント４
０又は４２の大きさがテスト大きさよりも大きい場合に
は、線セグメント３８は弧２２の充分に正確な表示では
なくて、表示のための弧の近似として不適当である。こ
の場合には、弧２２を２つの部分に細分化し、その各々
を４つの制御ポイントで定めるようにする。各部分の４
つの制御ポイントは次のように決定される。先ず、各線
セグメント３２、３４及び３６の中間点、特にポイント
４４、４６及び４８を各々決定する。次いで、ポイント
４４と４６との間及びポイント４６と４８との間に延び
る線セグメントの中間点、特にポイント５０及び５２を
各々決定する。最後に、ポイント５０と５２との間に延
びる線セグメント５４の中間点を決定し、これがポイン
ト５６である。弧２２はこのポイント５６を通過する。
このポイント５６において、弧２２は、ポイント５０と
５２を接続する線セグメント５４に正接する。これで、
弧２２の２つの部分を定めることができる。
【００１１】弧２２の第１部分２２ａは、ベツィエの制
御ポイントとしてポイント２４、４４、５０及び５６を
用いて定められ、そして弧２２の第２部分２２ｂは、ベ
ツィエ制御ポイントとしてポイント５６、５２、４８及
び２６を用いて定められる。弧２２の２つの部分２２ａ
及び２２ｂが見つかった後に、端末ポイント２４と５６
との間及び端末ポイント５６と２６との間に各々引かれ
た線セグメント６０及び６２が上記手順を用いてテスト
され、線セグメント６０及び６２が各弧部分２２ａ及び
２２ｂの充分に正確な近似であってこれらを用いて弧２
２のその部分を表示できるかどうか決定される。１つ以
上の弧部分がその各々の制御ポイント間に引いた線セグ
メントによって充分厳密に定められない場合には、その
弧部分のベツィエ曲線が上記手順を用いて細分化され
る。弧２２の各部分がそれにより得られる１組の線セグ
メントによって表示のために充分に厳密に近似されたと
考えられるまでこの手順が繰り返される。
【００１２】上記プロセスを続けることにより、弧２２
を所望の正確さ程度まで近似することができる。所与の
１組の線セグメントが、それ以上正確な線セグメントの
組が不要であるような充分な精度で弧を近似するときに
は、ベツィエ曲線を描写を停止することが非常に重要で
ある。これは、非常に正確な曲線を描写するには非常に
多数の数学演算が必要であり、ほとんどのコンピュータ
グラフィックシステムはディスプレイスクリーンである
かプリンタであるかに係わりなく一般に解像度の低い装
置であり、得られる線セグメントの組を記憶するに必要
なメモリの量は近似精度の増加と共に甚だしく増大し、
そしてコンピュータグラフィックシステムの速度が限定
されているためである。
【００１３】
【発明が解決しようとする課題】１組の線セグメントが
厳密に近似するときを決定する上記の公知技術は、計算
上非効率的である。公知技術では、線セグメント４０及
び４２の長さを決定することが必要である。又、各々の
反復において、２つのベツィエ制御ポイント間の最も短
い距離の計算、制御ポイント２８及び３０のような線セ
グメント及び線セグメント３８が必要とされる。このた
め、線セグメント４０及び４２の大きさを計算できるよ
うにポイント５７及び５８の位置を決定しなければなら
ない。これらのポイント５７及び５８の計算は計算効率
が悪く、この効率の悪さは、あるコンピュータグラフィ
ックディスプレイで曲線を描写するときに要求される多
大な時間をかけて遂行したときに非常に顕著なものとな
る。
【００１４】ベツィエ曲線を描写する別の公知方法は、
ベツィエ曲線を定義するのに用いられる式を数学的に分
析して、ベツィエの端末ポイント間に引いた直線セグメ
ントが、ユーザがこれを用いてベツィエ曲線を近似する
ための充分に厳密な近似であるかどうかを判断すること
である。
【００１５】ベツィエ曲線は、次の数１によって数学的
に表すことができる。
【００１６】
【数１】 但し、次の数２の通りである。
【００１７】
【数２】 上記式は、ベツィエの次数をｎとすれば、いかなる次数
のベツィエ曲線にも有効である。従って、立方ベツィエ
曲線（ｎ＝３）の式は、次のようになる。 ｆ(t) ＝ｂ0(1-t)3 ＋ｂ13(1-t)2t ＋ｂ23(1-t)t2 ＋ｂ3t3 ここで、ｂ0 ないしｂ3 は、曲線を定めるのに必要な４
つのベツィエ制御ポイントである。上記の式は、いかな
る次元数にも有効である。この式は、各次元において関
数を定義するためにベクトルを使用することによって各
次元に独立して適用される。簡単化のために、１つの式
についてのみ説明する。ｔが０から１に変化するとき
に、ベツィエの制御ポイントによって定められた関数ｆ
(t) は、図３に曲線１００で示すようにトレースされ
る。
【００１８】ベツィエ曲線を描写するためのパラメータ
的な解決策は、図３に示すように、ベツィエの端末ポイ
ント１０２と１０４との間に引いた単一の直線セグメン
ト１０６で曲線１００を描写するように最初に試みる。
この段階は、ｔ＝０における関数ｆ(t) の初期位置であ
るベツィエの端末ポイント１０２からベツィエの端末ポ
イント１０４まで１つの段階をとるものと考えられる。
線セグメント１０６がベツィエ曲線１００の近似として
用いるのに充分なほど正確でないとエラー項が示す場合
には、公知のシステムは、関数ｆ(t) に数学演算子を適
用して、「ステップサイズ」を半分に切断し、ここで関
数が図４に示すようにベツィエ曲線１００の第１の曲線
部分１０８のみを定めるようにする。関数は、ベツィエ
の端末ポイント１０２の現在位置と、ｔ＝１／２におけ
る関数ｆ(t) の曲線１００上のポイントである新たな端
末ポイント１１６との間に曲線部分１０８を定める。こ
のポイント１１６は、線５４が図２の弧２２に正接した
同じポイント５６であることに注意されたい。
【００１９】この技術で良く知られた数学演算子が関数
ｆ(t) に適用されてステップサイズが減少される。この
演算子はしばしば「アジャスト・ダウン演算子」と称す
る。このアジャスト・ダウン演算子を適用する前は、関
数ｆ(t) は、ベツィエの端末ポイント１０２の初期位置
からベツィエの端末ポイント１０４までの全曲線を定義
する。アジャスト・ダウン演算子を関数ｆ(t) に適用し
た後、今度はこの関数は、ベツィエの端末ポイント１０
２における初期位置からｔ＝１／２における関数ｆ(t)
の曲線１００上のポイント１１６までの曲線１００の第
１半部分１０８を定義する。公知のシステムは、この半
分のステップサイズに対して関数ｆ(t)を分析して、端
末ポイント１０２と中点１１６との間に引いた線セグメ
ント１１２が曲線部分１０８の正確な近似であるかどう
かを決定する。この線セグメント１１２が曲線部分１０
８を近似するのに充分正確でない場合には、システム
は、関数ｆ(t) にもう一度アジャスト・ダウン演算子を
適用してステップサイズを再び減少する。今度は関数ｆ
(t) は、図５に示すように、ベツィエの端末ポイント１
０２における初期位置から曲線部分１０８の中点１２２
までの曲線１００の第１の四半分を定める（第２の四半
分は参照番号１２４で示されている）。線セグメントが
曲線部分を適切に近似するに充分なほど正確になるま
で、ステップサイズは半分づつ減少され続ける。
【００２０】この時点で、公知システムは、「ステップ
・フォワード演算子」と一般に称する別の演算子を関数
ｆ(t) に適用する。このステップ・フォワード演算子
は、現在ステップサイズに等しい量だけ関数の現在位置
を効果的に移動する。例えば、端末ポイント１０２とポ
イント１２２との間に引かれた図５の線セグメント１２
０が曲線部分１１８を近似するのに充分な精度であると
決定された場合に、システムは、この曲線部分１１８を
近似するのに線セグメント１２０を使用し、そしてこの
ステップ・フォーワード演算子を関数ｆ(t) に適用し
て、この関数を曲線上のポイント１２２へ移動する。ス
テップ・フォワード演算子を適用する前は、関数ｆ(t)
は、ベツィエの端末ポイント１０２の初期位置から端末
ポイント１２２までの曲線部分１１８を定める。ステッ
プ・フォワード演算子を適用した後には、関数ｆ(t) の
現在位置が端末ポイント１２２まで移動され、今度は関
数は、ポイント１２２の現在位置から端末ポイント１１
６までの曲線部分１２４を定める。ステップ・フォワー
ド演算子を適用することによって関数のステップサイズ
は変更されないことに注意されたい。公知システムは、
曲線部分１２４に対して関数ｆ(t) に同じプロセスを適
用し、即ち、必要に応じてアジャスト・ダウン演算子を
適用するか、又は線セグメント１２６が曲線部分１２４
に充分厳密であって線セグメント１２６を用いて曲線部
分１２４を近似できる場合にはステップ・フォワード演
算子を適用する。
【００２１】線セグメント１２６が曲線部分１２４を近
似するのに充分正確である場合は、システムは、ステッ
プフォワード演算子をその後に適用する際のステップサ
イズを２倍にする「アジャスト・アップ演算子」と一般
に称する第３の演算子を関数ｆ(t) に適用する。このア
ジャスト・アップ演算子によってステップサイズは２倍
になる。アジャスト・アップ演算子を適用する前は、関
数ｆ(t) は、端末ポイント１２２の現在位置から端末ポ
イント１１６までの曲線部分１２４を定める。アジャス
ト・アップ演算子を適用した後は、関数は、端末ポイン
ト１２２の現在位置から図６に示す新たな端末ポイント
１３２までの２倍のサイズの曲線部分１２４及び１２８
を定める。従って、システムは、ポイント１２２とポイ
ント１３２との間に引いた線セグメント１３０が曲線部
分１２４及び１２８を充分正確に近似するかどうかを決
定する。線セグメント１３０が曲線部分１２４及び１２
８を近似するに充分な精度である場合には、システムは
線セグメント１３０を使用し、ステップ・フォワード演
算子を関数ｆ(t) に適用して、この関数の現在位置を線
セグメント１３０の端末であるポイント１３２まで移動
する。関数がベツィエ曲線に沿って移動するにつれてス
テップサイズを半分又は２倍にするこのプロセスは、こ
の分野では、適応フォワード相違(adaptive forward di
fferencing)（ＡＦＤ）として知られている。
【００２２】理想的には、ＡＦＤは、最小数の線セグメ
ントで曲線１００を描写する。以下で詳細に述べるよう
に、関数ｆ(t) のエラー項を評価するのが困難であるた
めにこのようなことは生じない。
【００２３】この分野で良く知られているように、ＡＦ
Ｄについての式は単に一般化したベツィエ式を操作する
ものである。基礎の変更と称するこの操作により、ＡＦ
Ｄの基礎に対し次の式が得られる。 ｆ(t) ＝ａ0 Ａ0(ｔ）＋ａ1 Ａ1(ｔ）．．．＋ａk Ａk （ｔ） 但し、Ａk （ｔ）＝((ｔ−ｋ＋１）／ｋ）＊Ａk-1(ｔ),
Ａ0(ｔ）＝１である。最も一般的に使用される曲線であ
る立方ベツィエ曲線については、係数Ａ0 ないしＡ3 は
次の式で与えられる。
【００２４】Ａ0(ｔ）＝１ Ａ1(ｔ）＝ｔ Ａ2(ｔ）＝１／２（ｔ)(ｔ−１） Ａ3(ｔ）＝１／６（ｔ)(ｔ−１)(ｔ−２） 但し、関数はＡＦＤ係数について表される。時間ｔ＝ｔ
＋１においてこの関数を評価するために、次の式を使用
し、 Ａ0(ｔ＋１）＝１＝Ａ0(ｔ） Ａ1(ｔ＋１）＝Ａ0(ｔ）＋Ａ1(ｔ） Ａ2(ｔ＋１）＝Ａ1(ｔ）＋Ａ2(ｔ） Ａ3(ｔ＋１）＝Ａ2(ｔ）＋Ａ3(ｔ） 関数ｆ（ｔ＋１）を関数ｆ（ｔ）について表すことがで
きる。関数ｆ（ｔ＋１）を関数ｆ（ｔ）について評価す
るために、フォワード・ステップ演算子を適用すること
ができる。次の式は、関数ｆ（ｔ＋１）をＡＦＤベース
で表す。
【００２５】 ｆ（ｔ＋１）＝（ａ0 ＋ａ1)Ａ0(ｔ）＋（ａ1 ＋ａ2)Ａ1(ｔ） ＋（ａ2 ＋ａ3)Ａ2(ｔ）＋（ａ3)Ａ3(ｔ） これにより、次の式が得られる。 ｆ（ｔ＋１）＝（ａ0') Ａ0(ｔ）＋（ａ1') Ａ1(ｔ） ＋（ａ2') Ａ2(ｔ）＋（ａ3') Ａ3(ｔ） 但し、ａ0 ＋ａ1 ＝ａ0'、ａ1 ＋ａ2 ＝ａ1'、ａ2 ＋ａ
3 ＝ａ2'及びａ3 ＝ａ3'である。関数ｆ（ｔ＋１）は、
ベクトル項ａ0'ないしａ3'を用いることにより評価でき
ることに注意されたい。
【００２６】関数ｆ（ｔ）に適用される簡単な演算子を
使用すると、ベツィエ曲線を描写する計算効率が上昇す
る。従って、ベツィエ曲線を描写するためのＡＦＤの数
学的解決策は、上記したグラフ的技術に勝る改善であ
る。しかしながら、このシステムは、ベツィエ曲線の満
足な近似を描写するためにどれほど多くの細分化を必要
とするかを決定するという問題に依然として直面してい
る。ＡＦＤの技術を使用すると、エラー項を計算するこ
とができる。しかし、ＡＦＤ式のエラー項は評価が困難
である。その結果、公知システムは、描写される曲線の
精度を決定する別の方法に依存している。ＡＦＤにおけ
る最も一般的な解決策は、各線セグメントが１ピクセル
長さとしてしばしば選択されるテスト大きさ以下になる
まで繰り返し細分化することである。かくて、曲線は繰
り返し細分化され、式ａ0'−ａ0 により計算される線セ
グメントの長さはピクセル長さ以下となる。
【００２７】ＡＦＤを用いて線セグメントが１ピクセル
長さ以下になるまで細分化するやり方には多数の欠点が
ある。最も明らかな欠点は、特に非常にフラットな曲線
や直線については数ピクセル長さの線セグメントでも適
当な近似を与えるので、ベツィエ曲線の正確な近似を描
写するために実際に必要とされる以上に多数の細分化が
行われることである。
【００２８】ＡＦＤの別の欠点は、ＡＦＤ技術によって
発生されるポイントが上記した公知の反復細分化方法に
よって発生されるポイントと常に同じではないことであ
る。反復細分化では、図６において線セグメント１３０
を用いて曲線部分１２４及び１２８を近似することには
決してならないことに注意されたい。反復細分化は常に
曲線を半分に細分化するので、ポイント１１６が曲線１
００を近似するのに用いる線セグメントの端末ポイント
となる。従って、反復細分化では常にポイント１１６が
ベツィエの制御ポイントとなり、一方、ＡＦＤ技術で
は、関数ｆ（ｔ）の制御ポイントとしてポイント１１６
を使用しない線セグメントを生じる。
【００２９】制御ポイントが異なるので、ＡＦＤ技術は
両方向であることが保証されず、即ちベツィエ曲線の一
端でスタートして発生されるベツィエ制御ポイントは、
曲線の他端からスタートして発生される制御ポイントと
必ずしも同じでない。ＡＦＤを用いてグラフィック像を
消去する場合には、システムは、曲線を形成したのと同
じ曲線端において消去をスタートする必要がある。これ
は、コンピュータディスプレイスクリーンから曲線を消
去するときに欠点となる。というのは、ベツィエ曲線の
他端から消去する方がしばしば効率的だからである。
【００３０】反復細分化方法は、方向に依存しないとい
う利点がある。ベツィエ曲線のいずれの端からスタート
しても同じベツィエ制御ポイントが発生される。反復細
分化方法は、上記のように曲線を描写する際に計算効率
が悪いという欠点がある。
【００３１】それ故、ベツィエ曲線を描写しそしてそれ
により生じる直線セグメントで曲線を近似する精度を決
定するための計算効率の良いシステム及び方法をもつこ
とが有用である。
【００３２】
【課題を解決するための手段】ベツィエ曲線を計算効率
の良いやり方で描写するシステムが提供される。このシ
ステムは、曲線の端末ポイント間の直線セグメントで曲
線を近似する精度の程度を測定する。このシステムはエ
ラーベクトルを計算し、そしてエラーベクトルの大きさ
を、ベツィエ曲線を描写すべき所望程度の精度を表すテ
スト大きさと比較する。エラーベクトル項のいずれかの
大きさがテスト大きさを越える場合は、システムは、描
写されている曲線部分のサイズを減少するための数学演
算子を適用し、精度に対してテストを繰り返す。エラー
ベクトルの大きさが各々テスト大きさより小さい場合に
は、システムは、より大きな曲線部分をテストして、そ
の大きな曲線部分を近似するのに大きな線セグメントを
使用できるかどうか決定する。この線セグメントが反復
細分化によって導出される場合には、システムはその大
きな線セグメントのみを使用する。さもなくば、システ
ムは、より小さい線セグメントを使用して、より小さい
曲線部分を近似する。
【００３３】本発明の他の特徴及び効果は、添付図面を
参照した詳細な説明より明らかとなろう。
【００３４】
【実施例】本発明は、同じエラー測定を用いた一般に使
用されている公知の反復細分化方法によって発生される
ものと同じ１組の線セグメントでベツィエ曲線を描写す
るシステム及び方法に関する。本発明のシステム及び方
法は、ベツィエ曲線を計算効率の良いやり方で描写す
る。関連する公知の方法と同様に、本発明は、以下にテ
スト大きさと称する精度値を決定することを必要とす
る。このテスト大きさは線セグメントでベツィエ曲線を
近似する精度の程度がユーザにとって充分なものである
かどうかを決定する。テスト大きさの実際の値は、通
常、ピクセルのサイズのように使用するグラフィックデ
ィスプレイスクリーン又はプリンタの解像度に関連して
選択されるが、いかなるテスト大きさ値を使用してもよ
い。線セグメントが実際の曲線の１つのピクセル内に入
る場合には、それ以上の計算が意味のある近似を生じな
いので、システムは計算を終わらせることができる。前
記したように、解像度の程度はディスプレイ装置によっ
て左右され、ビデオディスプレイのピクセルは、典型的
なレーザプリンタのピクセルとは物理的なサイズが異な
る。本発明は、いかなる解像度のディスプレイ装置にも
同等に機能する。
【００３５】ハイブリッドフォワード相違（ＨＦＤ）と
称する本発明のシステムは、特定のグラフィックディス
プレイにより要求される精度で曲線を描写するに必要な
頻度でしか細分化を行わないので、ベツィエ曲線を計算
効率の良い仕方で描写することができる。このシステム
は、ＡＦＤの計算効率によってもたらされる幾つかの効
果を使用するが、ピクセルではなくて線を発生する。と
いうのは、本発明は、細分化の回数を最小にするために
使用されるエラーベクトルを計算するからである。又、
このシステムは、公知の反復細分化方法によって発生さ
れたものと厳密に同じベツィエ制御ポイントを再生す
る。これはディスプレイスクリーンから曲線を消去する
ときに非常に効果的である。というのは、曲線を最初に
引いた方向に係わりなくベツィエ曲線のいずれの端から
でも消去プロセスを行えるからである。更に、本発明の
システムは、独特のベクトルエラー手法を用いて、描写
されるベツィエ曲線の精度を分析する。
【００３６】エラーベクトルの使用は、図７のグラフに
最も良く示されている。４つのベツィエ制御ポイント２
０２、２０４、２０６及び２０８によって定められた立
方ベツィエ曲線２００は、２つのベツィエ端末ポイント
２０２と２０８との間に引いた単一の線セグメント２１
０によって近似することができる。この近似の精度を決
定するために、システムは４つのベツィエ制御ポイント
間のベクトル２１２、２１４及び２１６を計算する。こ
のプロセスはいかなる次数のベツィエ曲線にも適用で
き、唯一の相違はシステムによって発生されるエラーベ
クトルの数だけであることに注意されたい。例えば、３
次のベツィエ曲線は、以下に述べるように２つのエラー
ベクトルを生じるが、２次のベツィエ曲線は１つのエラ
ーベクトルを生じる。４次のベツィエ曲線は３つのエラ
ーベクトルを生じる。
【００３７】システムは、ベツィエ曲線２００に対し、
一対のエラーベクトル２１８及び２２０を計算し、これ
らは、図７において４つのベツィエ制御ポイント２０
２、２０４、２０６及び２０８の間に引いたベクトル２
１２、２１４及び２１６を単純に加算及び減算すること
により計算することができる。特に、エラーベクトル２
１８は、ベクトル２１４からベクトル２１２を減算する
ことによって計算され、そしてエラーベクトル２２０
は、ベクトル２１６からベクトル２１４を減算すること
によって計算される。図７において、エラーベクトル２
１８及び２２０は、各々制御ポイント２０４及び２０６
から発せられるように示されている。２つのエラーベク
トル２１８及び２２０の大きさは、テスト大きさと各々
比較される。いずれかのエラーベクトルの大きさがテス
ト大きさを越えた場合には、近似が充分に正確なもので
はなく、曲線を細分化しなければならない。一方、エラ
ーベクトル２１８及び２２０の大きさがどちらもテスト
大きさより小さい場合には、ベツィエ端末ポイント２０
２と２０８との間に引いた線セグメント２１０が充分な
精度であって、これを用いてベツィエ曲線２００を近似
することができる。
【００３８】エラーベクトルの大きさを計算する多数の
方法が当業者に知られていることに注意されたい。エラ
ーベクトルの大きさを計算する１つの方法は、エラーベ
クトルを各Ｘ及びＹ成分に分解し、そしてベクトルのＸ
及びＹ成分の平方の和の平方根を計算することである。
ここに示す好ましい実施例では、システムはエラーベク
トルの実際の大きさを計算しない。そうではなくて、各
エラーベクトルのＸ又はＹ成分の大きい方がそのエラー
ベクトルの近似として使用される。従って、各エラーベ
クトル２１８及び２２０の大きい方のＸ又はＹ成分の大
きさ（又はスカラー成分）がテスト大きさと比較され
る。
【００３９】これらのエラーベクトルは、線セグメント
２１０でベツィエ曲線２００を近似する精度の程度を計
算するのに使用できるが、ベクトル２１２、２１４及び
２１６の計算と、エラーベクトル２１８及び２２０の計
算それ自体は、低速プロセスでよい。本発明のシステム
は、ベツィエの制御ポイント間のベクトルを計算する必
要なく、これらのエラーベクトルを決定する。
【００４０】前記したように、ＡＦＤの基本式は、次の
通りである。 ｆ（ｔ）＝ａ0 Ａ0(ｔ）＋ａ1 Ａ1(ｔ）．．．＋ａk Ａk （ｔ） 但し、ａ0 ないしａk は、空間における方向を表すベク
トルである。立方多項式に対してＨＦＤで大きさ決めさ
れるエラーベースは、次の式で表される。 ｆ（ｔ）＝ｅ0 Ｅ0(ｔ）＋ｅ1 Ｅ1(ｔ）＋ｅ2 Ｅ2(ｔ）＋ｅ3 Ｅ3(ｔ） 但し、 Ｅ0(ｔ）＝Ａ0(ｔ）＝１ Ｅ1(ｔ）＝Ａ1(ｔ）＝ｔ Ｅ2(ｔ）＝Ａ2(ｔ）＋Ａ3(ｔ）＝１／６（ｔ)(ｔ2 −１） Ｅ3(ｔ）＝−Ａ3(ｔ）＝−１／６（ｔ)(ｔ−１)(ｔ−２） これは評価の容易なフォワード・ステップ演算子を生じ
る。エラーベクトルｅ0ないしｅ3 は、次の式によって
ベツィエの制御ポイントに関連付けることができる。
【００４１】ｅ0 ＝ｂ0 ｅ1 ＝ｂ3 −ｂ0 ｅ2 ＝６（ｂ3 −２ｂ2 ＋ｂ1 ） ｅ3 ＝６（ｂ2 −２ｂ1 ＋ｂ0 ） 但し、ｂ0 ないしｂ3 は、ベツィエの制御ポイントであ
る。これらの式は、ベツィエ曲線の線セグメント近似の
精度を評価するのに使用できるベクトルを表している。
特に、ベクトルｅ2 及びｅ3 は、図７の６倍ベクトル２
１８及び２２０である。従って、図７にグラフで導出さ
れたエラーベクトルは、上記の式から導出することがで
きる。上記式の基礎を変更することにより、エラー項を
決定する作業が簡単になる。エラーベクトルｅ2 及びｅ
3 の大きさがテスト大きさと比較される。前記したよう
に、エラーベクトルの大きさは、エラーベクトルのスカ
ラー成分の大きい方で近似することができる。両エラー
ベクトルｅ2 及びｅ3 の大きさがテスト大きさよりも小
さい場合には、２つのベツィエ端末ポイント間に引いた
線セグメントを用いてベツィエ曲線を近似することがで
きる。本発明の原理はいかなる次数のベツィエ曲線にも
等しく適用でき、唯一の相違は形成されるエラーベクト
ルの数だけである。立方ベツィエ曲線の場合には、２つ
のエラーベクトルｅ2 及びｅ3 があるが、４次のベツィ
エ曲線は、３つのエラーベクトルｅ2 、ｅ3 及びｅ4 を
有し、これら全てをテスト大きさと比較する必要があ
る。これに対し、２次のベツィエ曲線は、テスト大きさ
と比較すべき１つのエラーベクトルｅ2 のみを有する。
従って、立方ベツィエ曲線について説明するが、本発明
はいかなる次数のベツィエ曲線にも適用できる。
【００４２】以下の説明は、立方ベツィエ曲線の線セグ
メント近似をテストするための独特のエラーベクトルを
導出するプロセスの一例である。図８ないし１０のフロ
ーチャートと、図１１ないし１５は、本発明により使用
される方法を１段階づつ説明するものである。システム
には、ベツィエ制御ポイントの値が設けられる。これら
のポイントは、グラフィックアプリケーションプログラ
ム等のような種々の手段によってコンピュータに入力さ
れる。立方ベツィエ曲線の場合には、４つの制御ポイン
トｂ0 ないしｂ3 がシステムに入力される。システム
は、これらのベツィエ制御ポイントを用いて、上記のＨ
ＦＤ大きさ決めエラーベースのｅ0 ないしｅ3 の項で定
めた関数ｆ（ｔ）を計算する。例えば、図８のフローチ
ャートでは開始ブロック３００において、システムにベ
ツィエ制御ポイントの値が与えられる。システムは、こ
れらのベツィエ制御ポイントを用いて、上記のＨＦＤ大
きさ決めエラーベースのｅ0 ないしｅ3 の項で定められ
た関数ｆ（ｔ）を計算する。関数ｆ（ｔ）は、図１１に
おいて曲線４００を定めるものである。端末ポイント４
０２及び４０４は、各々、ベツィエ端末ポイントｂ0 及
びｂ3 である。他の２つのベツィエ制御ポイントは明瞭
化のために省略してある。
【００４３】システムは、最初に、ステップ数を表す変
数ｎｓｔｅｐｓを、ブロック３０２に示すように、１に
等しくセットする。この変数は、関数ｆ（ｔ）が現在ス
テップサイズを用いて現在位置からベツィエの端末ポイ
ントに到達するのに必要なステップ数を表している。最
初に、この関数は曲線全体を定める。従って、一方のベ
ツィエ端末ポイント４０２から他方のベツィエ端末ポイ
ント４０４へ初期ステップサイズで到達するのに単一の
ステップを必要とする。ブロック３０４では、システム
は、最初はベツィエ曲線全体である曲線の現在部分に対
するエラーベクトルを計算する。システムは、関数ｆ
（ｔ）のエラーベクトルｅ2 及びｅ3 を使用して、単一
の線セグメント４０６が、４つの入力されたベツィエ制
御ポイントにより定められた曲線４００を充分正確に近
似するかどうかを決定する。前記したように、エラーベ
クトルの大きさは、エラーベクトルのスカラー成分の大
きい方によって近似することができる。エラーベクトル
ｅ2 及びｅ3 の両方がテスト大きさよりも小さい場合に
は、２つのベツィエ端末ポイント４０２と４０４との間
に形成した単一に線セグメント４０６がベツィエ曲線４
００の正確な近似となる。
【００４４】エラーベクトルのいずれかがテスト大きさ
よりも大きい場合には、判断ブロック３０６の結果がイ
エスとなる。この場合には、ステップサイズを半分に切
断するアジャスト・ダウン演算子が関数ｆ（ｔ）に適用
される。この形式の演算子は公知であり、ここでは詳細
に説明しない。ここに示す好ましい実施例では、次の数
３のマトリクスを用いて、関数ｆ（ｔ／２）をｆ（ｔ）
について評価する。
【００４５】
【数３】 但し、ｅ0'ないしｅ3'は関数ｆ（ｔ／２）の項でありそ
してｅ0 ないしｅ3 は関数ｆ（ｔ）の項である。アジャ
スト・ダウン演算子を適用すると、関数ｆ（ｔ）が変更
されて、今度はこの関数が、図１２においてベツィエ端
末ポイント４０２の現在位置から関数ｆ（ｔ／２）で定
められた新たな端末ポイント４１６までの曲線部分４０
８（即ち、ベツィエ曲線４００の最初の半分）のみを定
めるようになる。ここでは、アジャスト・ダウン演算子
の適用によって新たな関数ｆ（ｔ／２）が効果的に形成
されることを示す。項ｅ0'ないしｅ3'は関数ｆ（ｔ／
２）の項である。アジャスト・ダウン演算子を２回目に
適用すると、ｅ0"ないしｅ3"の項で表された関数ｆ（ｔ
／４）が得られる。明瞭化のため、ｅ0 ないしｅ3 の項
で表された関数ｆ（ｔ）として動作関数を以下に定義す
る。これは、ｅ0'、ｅ0"、ｅ0 "'、等々の項をもつ問題
を回避する。当業者には明らかであろうが、明確に述べ
ると、元の関数ｆ（ｔ）は、演算子を適用した後は関数
ｆ（ｔ）と同じではない。同様に、新たな関数ｆ（ｔ）
の項ｅ0 ないしｅ3 も、元の関数の項ｅ0ないしｅ3 と
同じでない。ポイント４１６は、関数ｆ（ｔ）において
ｔ＝１／２の場合の曲線４００のポイントであることに
注意されたい。このポイントは図２のポイント５６に対
応している。ブロック３１０は、ｎｓｔｅｐｓの値を２
倍にし、現在ステップサイズでベツィエ端末ポイント４
０２の現在位置からベツィエ端末ポイント４０４へ到達
するのに２つのステップを要することを示している。シ
ステムは、ブロック３０４に制御を復帰させ、今度はベ
ツィエ曲線の第１曲線部分４０８を表す関数ｆ（ｔ）の
エラーベクトルを決定し、プロセスが繰り返される。シ
ステムは、ポイント４０２と４１６との間に延びる線セ
グメント４１２が曲線部分４０８を近似するのに充分正
確であるかどうかを決定するテストを行う。今度は曲線
部分４０８を表している関数ｆ（ｔ）は、第１のベツィ
エ端末ポイント４０２と曲線４００上の中間点４１６と
の間に延びる線セグメント４１２に対するエラーを表す
新たなエラーベクトルｅ2 及びｅ3 をもつことになる。
【００４６】線セグメント４１２に対するエラーを表す
エラーベクトルｅ2 及びｅ3 が両方ともにテスト大きさ
より小さい場合には、この線セグメント４１２を用いて
曲線部分４０８を近似することができる。しかしなが
ら、いずれかのエラーベクトルｅ2 又はｅ3 がこのテス
ト大きさより大きい場合には、線セグメント４１２を用
いて曲線部分４０８を近似することはできない。この場
合には、システムはアジャスト・ダウン演算子を関数ｆ
（ｔ）に適用してステップサイズを再び半分に分割す
る。これで、関数は、全曲線４００の最初の四半分の部
分４１８のみを定めることになる。アジャスト・ダウン
演算子が適用された後に、関数ｆ（ｔ）のエラーベクト
ルｅ2 及びｅ3 は、ポイント４０２と４２２との間に延
びる線セグメント４２０が曲線部分４１８を近似する精
度を表す。エラーをチェックし、アジャスト・ダウン演
算子を適用し、そしてｎｓｔｅｐｓの値を２倍にする段
階は、曲線の特定部分に対するエラーベクトル全てがテ
スト大きさより小さくなるまで繰り返される。この場合
に、判断ブロック３０６の結果がノーとなる。
【００４７】エラーベクトルｅ2 及びｅ3 の両方がテス
ト大きさより小さいことがシステムによって判断される
と、システムは、図１０に示すようにブロック３１６に
おいてベツィエ曲線の現在部分の２つの端末ポイント４
０２と４２２との間に線セグメント４２０を発生し、次
いで、ブロック３１８においてフォワード・ステップ演
算子を関数ｆ（ｔ）に適用することによってベツィエ曲
線の次の部分に移動する。フォワード・ステップ演算子
の一般式は公知であり、ここでは詳細に説明しない。こ
こに示す好ましい実施例では、次の数４のマトリクスを
用いて、関数ｆ（ｔ＋１）を関数ｆ（ｔ）について評価
する。
【００４８】
【数４】 但し、ｅ0'ないしｅ3'は関数ｆ（ｔ＋１）の項でありそ
してｅ0 ないしｅ3 は関数ｆ（ｔ）の項である。上記し
たように、新たな項ｅ0 ないしｅ3 をもつ新たな関数ｆ
（ｔ）として関数ｆ（ｔ＋１）を再定義する。
【００４９】フォワード・ステップ演算子を適用する前
は、関数ｆ（ｔ）は、ベツィエの端末ポイント４０２の
現在位置から端末ポイント４２２まで延びる曲線部分４
１８を定める。このフォワード・ステップ演算子を関数
ｆ（ｔ）に適用した後は、この関数はポイント４２２に
現在位置を有し、ポイント４２２からポイント４１６ま
での曲線部分４２４を定める。又、システムは、ブロッ
ク３２０においてｎｓｔｅｐｓ値を３に減少する。これ
は、現在ステップサイズで、ポイント４２２の現在位置
からベツィエの端末ポイント４０４に達するまでに３ス
テップを要することを示している。フォワード・ステッ
プ演算子を適用してもステップサイズは不変のままであ
ることに注意されたい。判断ブロック３２２は、丁度描
写されたセグメントがベツィエ曲線の最後のセグメント
であるかどうかチェックを行う。ｎｓｔｅｐｓが０に等
しい場合には、最後の曲線部分が描写されており、判断
ブロック３２２の結果はイエスである。従って、ベツィ
エ曲線全体が描写され、システムはブロック３２４にお
いて描写プロセスを終了する。判断ブロック３２２の結
果がノーの場合には、システムは図８のブロック３０４
に制御を戻し、現在曲線部分に対するエラーベクトルを
再び計算する。
【００５０】曲線部分４２４を描写するために、システ
ムは、エラーベクトルを計算しそしてエラーベクトルの
大きさをテスト大きさと比較するという上記のプロセス
を繰り返す。いずれかのエラーベクトルｅ2 又はｅ3 が
テスト大きさよりも大きい場合には、システムはアジャ
スト・ダウン演算子を適用してステップサイズを半分に
切断する。曲線部分４２４のエラーベクトルがテスト大
きさを越えない場合には、判断ブロック３０６の結果が
ノーとなる。端末ポイント４２２と４１６との間の線セ
グメント４２６を用いてベツィエ曲線を近似することが
できる。曲線部分４２４を近似する線セグメント４２６
を発生する前に、システムは、もっと長い線セグメント
を使用して、より大きな部分を近似できるかどうかをチ
ェックする。
【００５１】上記のアジャスト・ダウン演算子及びフォ
ワード・ステップ演算子に加えて、本発明は、ステップ
サイズを２倍にするように関数ｆ（ｔ）に適用できるア
ジャスト・アップ演算子も使用する。この演算子も当業
者に良く知られており、ここでは詳細に説明しない。こ
こに示す好ましい実施例では、次の数５のマトリクスを
用いて、関数ｆ（２ｔ）を関数ｆ（ｔ）について評価す
る。
【００５２】
【数５】 但し、ｅ0'ないしｅ3'は関数ｆ（２ｔ）の項でありそし
てｅ0 ないしｅ3 は関数ｆ（ｔ）の項である。この場合
も、アジャスト・アップ演算子を適用した後に新たな項
ｅ0 ないしｅ3 をもつ新たな関数ｆ（ｔ）として関数ｆ
（２ｔ）を再定義する。ステップサイズを２倍にするこ
とにより、システムはベツィエ曲線のより大きな部分を
近似する。アジャスト・アップ演算子は、描写されてい
るベツィエ曲線の特定部分に対し、エラーがテスト大き
さより小さい場合に関数に適用される。公知システム及
び本発明のシステムはどちらも、大きさステップサイズ
がテスト大きさを越えるかどうかを判断するテストを行
うことができる。公知システムは、２倍のステップサイ
ズに対するエラーがテスト大きさを越えないことが分か
ると、ステップサイズを２倍にする。公知システムは、
それにより得られるベツィエの制御ポイントが反復細分
化方法から導出されたベツィエ制御ポイントと同じであ
るかどうかに係わりなくステップサイズを増加する。こ
れに対し、本発明のシステムは、たとえ２倍のステップ
サイズのエラーがテスト大きさを越えなくても、得られ
るベツィエ制御ポイントが反復細分化方法から生じるも
のと同じでない限り、ステップサイズを２倍にしない。
【００５３】ベツィエ曲線の現在描写部分のエラーベク
トルｅ2 及びｅ3 の大きさが両方ともにテスト大きさよ
り小さいときには、システムは、その描写される曲線部
分のサイズの２倍の曲線部分をテストして、アジャスト
・アップ演算子を関数に適用すべきかどうかを調べる。
システムは、関数ｆ（ｔ）に適用された最後の演算子が
アジャスト・ダウン演算子であった場合には２倍サイズ
の曲線部分をチェックしない。というのは、アジャスト
・ダウン演算子を手前で使用したことは、単一の直線セ
グメントで２倍サイズの曲線部分を近似できないという
指示だからである。一方、システムがアジャスト・ダウ
ン演算子の介在適用なしにフォワード・ステップ演算子
を手前で適用していた場合には、システムはアジャスト
・アップ演算子を適用できるかどうか判断するようテス
トする。システムは、２倍サイズの曲線部分のエラーベ
クトルがテスト大きさよりも小さく且つ２倍サイズの曲
線部分が公知の反復細分化プロセスを用いて導出される
ものである場合にのみ、アジャスト・アップ演算子を適
用する。システムは、アジャスト・アップ演算子を適用
する必要なく、２倍サイズの曲線部分に対してエラーベ
クトルｅ2 及びｅ3を決定することができる。システム
は、上記のマトリクスからｅ2'及びｅ3'を計算して、２
倍サイズの曲線部分に対するエラーベクトルを決定する
だけでよい。２倍サイズの曲線部分のいずれかのエラー
ベクトルｅ2 又はｅ3 がテスト大きさより大きい場合、
又は線セグメントが反復細分化によって導出されない場
合は、システムはアジャスト・アップ演算子を適用しな
い。線セグメント４２６が曲線部分２４２を近似するた
めに用いるのに充分正確なものであるとシステムが判断
した場合には、図１４に示すように、長い直線セグメン
ト４３０を使用して大きな曲線部分４２４及び４２８を
近似できるかどうかをシステムが再び決定する。この長
い線セグメント４３０に対するいずれかのエラーベクト
ルｅ2 又はｅ3 がテスト大きさを越える場合には、図９
の判断ブロック３１４の結果がイエスとなる。この場合
には、長い線セグメント４３０が使用されず、システム
は、前記したように、図１０のブロック３１６において
２つの端末ポイント４２２と４１６との間に引いた直線
セグメントによって現在曲線部分を近似する。次いで、
システムは、ブロック３１８において関数ｆ（ｔ）にフ
ォワード・ステップ演算子を適用し、端末ポイント４１
６を用いて曲線の次の部分を関数ｆ（ｔ）の現在位置と
して分析する。システムは、ブロック３２０において変
数ｎｓｔｅｐｓの値を減少するが、手前の細分化された
曲線部分４２４からのステップサイズを使用する。これ
で、関数ｆ（ｔ）はベツィエ曲線の次の部分４２８を表
す。
【００５４】一方、線セグメント４２６の両エラーベク
トルｅ2 及びｅ3 がテスト大きさより小さい場合には、
図８の判断ブロック３０６の結果がノーである。次い
で、判断ブロック３１３において、システムは、適用さ
れた最後の演算子がアジャスト・ダウン演算子であるか
どうかチェックする。もしそうであれば、判断ブロック
３１３の結果がイエスであり、システムは、長い線セグ
メントが不正確であると既に決定されているので、長い
線セグメントについてはチェックしない。そうではなく
て、システムはブロック３１６へ進んで、現在曲線部分
に対する線セグメントを発生する。アジャスト・ダウン
演算子が最後に適用された演算子でない場合には、判断
ブロック３１３の結果がノーである。この場合には、シ
ステムは、長い直線セグメント４３０を用いて曲線４０
０の長い部分を近似できるかどうかを更にテストする。
図１４において、アジャスト・ダウン演算子は最後に適
用された演算子ではなく、従って、判断ブロック３１３
の結果はノーである。線セグメント４３０が充分に正確
なものである場合には、曲線部分４２４及び４２８をこ
の線セグメントによって近似することができる。２倍サ
イズの曲線部分に対するエラーベクトルｅ2 及びｅ3 の
大きさが両方ともテスト大きさより小さい場合には、図
９の判断ブロック３１４の結果がノーである。システム
は、線セグメントが反復細分化によって導出されたもの
であるかどうかを判断するようチェックする。
【００５５】本発明は、ベツィエ曲線を描写するために
既にとられているステップ数を追跡することによりこの
チェックを行う。ステップ数が偶数である場合には、そ
れにより得られるベツィエ制御ポイントは、反復細分化
技術によって導出されたものと同じである。しかし、ス
テップ数ｎｓｔｅｐｓの値が奇数である場合には、反復
細分化によって同じ線セグメントは導出されない。図９
において、判断ブロック３２６は、ｎｓｔｅｐｓの値が
偶数であるか奇数であるかをテストする。ｎｓｔｅｐｓ
が奇数である場合には、判断ブロック３２６の結果がノ
ーであり、システムは図１０のブロック３１６へ制御を
移し、２倍サイズの曲線部分ではなくて曲線の現在部分
に対する線セグメントを発生する。図１４では、変数ｎ
ｓｔｅｐｓの値が３である。それ故、システムは、線セ
グメント４３０を用いて曲線部分４２４及び４２８を近
似しない。というのは、反復細分化がこの線セグメント
を使用しないからである。そうではなくて、システム
は、正確さについて既にテストされている線セグメント
４２６を用いて、曲線部分４２４を近似する。フォワー
ド・ステップ演算子が関数ｆ（ｔ）に適用されて現在位
置をポイント４１６に移動し、変数ｎｓｔｅｐｓの値が
２に減少される。ここで、関数ｆ（ｔ）は、図１５に示
すように、曲線部分４２８を定める。
【００５６】システムは、曲線部分４２８のエラーベク
トルｅ2 及びｅ3 に対して上記テストを繰り返す。いず
れかのエラーベクトルｅ2 又はｅ3 がテスト大きさを越
える場合には、システムは上記のようにアジャスト・ダ
ウン演算子を適用する。両方のエラーベクトルｅ2 及び
ｅ3 がテスト大きさより小さい場合には、システムは大
きな線セグメントを用いて大きな曲線部分を近似できる
かどうか判断するテストを行う。図１５に示すように、
エラーベクトルｅ2 及びｅ3 が両方ともテスト大きさよ
り小さく且つ線セグメントが反復細分化を用いて導出さ
れるものである場合には、線セグメント４３８を用いて
曲線部分４２８及び４３６を近似することができる。シ
ステムは上記と同様にエラーを計算する。いずれかのエ
ラーベクトルの大きさがテスト大きさを越える場合に
は、図９の判断ブロック３１４の結果がイエスとなる。
システムは長い線セグメント４３８を用いて曲線部分４
２８及び４３６を近似しない。そうではなくて、システ
ムは線セグメント４３４を用いて曲線部分４２８を近似
する。しかしながら、両エラーベクトルの大きさがテス
ト大きさよりも小さい場合には、判断ブロック３１４の
結果がノーとなる。ｎｓｔｅｐｓが偶数の場合には、判
断ブロック３２６の結果がイエスであり、ブロック３２
８において、アジャスト・アップ演算子を関数に適用す
ることによりステップサイズが２倍にされる。ここで、
関数はベツィエ曲線の２倍サイズの部分を表す。ｎｓｔ
ｅｐｓの値はブロック３３０において半分に分割され、
これは、増加されたステップサイズが、ベツィエ曲線上
の現在位置からベツィエ端末ポイントに到達するに要す
るステップ数を半分にすることを指示する。ここに示す
システムの実施例では、図８のブロック３０４に制御が
復帰され、大きなステップサイズに対するエラーベクト
ルが計算される。システムは、判断ブロック３１４に制
御を戻せることに注意されたい。というのは、判断ブロ
ック３１４において２倍サイズの曲線部分に対するエラ
ーベクトルがテスト大きさを越えないことが既に決定さ
れているからである。従って、システムは、大きな曲線
部分に対するエラーベクトルがテスト大きさを越えるま
で更に大きな曲線部分を探す。図１５では変数ｎｓｔｅ
ｐｓの値が２であるから、線セグメント４３８は反復細
分化によって導出されるものである。それ故、システム
は、両エラーベクトルｅ2 及びｅ3 がテスト大きさより
小さい場合に線セグメント４３８を用いて曲線部分４２
８及び４３６を近似する。
【００５７】本発明の原理によれば、反復細分化によっ
て導出される線セグメントのみを用いてベツィエ曲線が
近似される。ベツィエ曲線を描写する問題に対するこの
解決策は、いずれの方向からでも曲線を描写できるよう
にする。即ち、ベツィエ曲線はいずれも端からでも描写
することができ、同じ線セグメントを用いて曲線が描写
される。公知のシステムは、ベツィエ制御ポイントの順
序を反転した場合に異なる曲線を描写する。この変則性
が曲線形成時に問題を生じる。というのは、公知のシス
テムは曲線を単一方向に描写するように制限されている
からである。既に存在するベツィエ曲線を消去する場合
にも同じことがいえる。公知のシステムは、ベツィエ曲
線を、その曲線が形成されたのと同じ方向にしか消去す
ることができない。この制約も、ベツィエ曲線をいずれ
の方向からでも描写できる本発明の原理を用いて回避さ
れる。
【００５８】ベツィエ曲線にハイブリッドフォワード相
違ベースを適用すると、これまでの技術よりも迅速に曲
線を描写できることに注意されたい。いずれの方向から
でも曲線を描写できる利点を放棄して、ハイブリッドフ
ォワード相違ベースを用いて単一方向からのみ曲線を描
写することができる。又、当業者であれば、Ｎ次のベツ
ィエ曲線のＮ−１個の全てのエラーベクトルが小さくな
った場合及びその場合だけ小さくなるようなエラーベク
トルの関数をエラー基準として使用できることも明らか
であろう。例えば、エラーベクトルの大きさではなく
て、Ｎ−１個のエラーベクトルのＮ−１個のリニアな独
立した組み合わせの大きさを探すこともできる。
【００５９】上記のフローチャートをたどることによ
り、システムは、ベツィエ曲線を近似するのに使用でき
る線セグメントの最も小さい組を計算し、更に、良く知
られた反復細分化方法を用いて導出される同じ線セグメ
ントを使用する。システムは、曲線を描写するに必要な
細分化の数を最小にすることにより計算上効率の良いや
り方で線セグメントを計算する。これは、少ない細分化
でベツィエ曲線の受け入れられる近似が与えられても、
線セグメントの各々が１ピクセル長さになるまでベツィ
エ曲線が常に細分化されるような公知のＡＦＤ技術と対
照的である。
【００６０】本発明のシステムは、図１６に示すコンピ
ュータシステム４８０において実施される。メインコン
ピュータボックス４８２は、典型的に、中央処理ユニッ
ト、システムメモリ、ディスクドライブのような大量記
憶ユニット、及び種々のＩ／Ｏインターフェイスを備え
ている。コンピュータシステムは、データを入力したり
コンピュータの動作を制御したりするためのキーボード
４８４を有している。多くのグラフィックコンピュータ
と同様に、コンピュータシステムは、グラフィックデー
タをコンピュータに入力するためのマウス４８６及びデ
ジタイジングパッド４８８も有している。マウス４８６
及びデジタイジングパッド４８８は、複雑なグラフィッ
クオブジェクトを形成するように種々のアプリケーショ
ンプログラムと共に使用される。本発明のシステムは、
キーボード４８４、マウス４８６及びデジタイジングパ
ッド４８８のような装置によって発生された入力データ
を受け入れる。このデータは、本発明により、ビデオデ
ィスプレイターミナル４９０又はレーザプリンタ４９２
等の種々のグラフィック出力装置にグラフ表示を形成す
るように処理される。出力装置に発生された線セグメン
トは、本発明によって行われたプロセスの結果である。
【００６１】本発明によるシステム５００が図１７に機
能ブロック図で示されている。このシステム５００は中
央処理ユニット（ＣＰＵ）５０２によって制御され、こ
れはバス５０８を経てメモリ５０４に接続されている。
バス５０８は、ＣＰＵ５０２をシステム５００の他の要
素にも接続すると共に、図１７に示すように、これら要
素の幾つかを相互接続する。テスト大きさ５０６は、シ
ステムメインメモリ５０４に記憶されるか、又は他の適
当な記憶位置に記憶される。ハイブリッドフォワード相
違（ＨＦＤ）関数発生器５１０は、上記のハイブリッド
フォワード相違ベースを用いてベツィエ曲線の数学関数
を計算する。この関数は、最初にベツィエ曲線全体を定
め、変数ｎｓｔｅｐｓ５０７の値は、それを表すように
１に初期化される。ｎｓｔｅｐｓの値５０７は、システ
ムメインメモリ５０４又は適当な記憶位置に記憶するこ
とができる。関数が適当な演算子によって動作されると
きに、ステップサイズを変更することができる。ｎｓｔ
ｅｐｓの値５０７は対応的に変更される。ベツィエ曲線
の部分が描写されるときには、ｎｓｔｅｐｓの値５０７
は、この関数が現在ステップサイズでベツィエ曲線の端
末ポイントに到達するのに要するステップ数を表すよう
に変更される。エラーベクトルの計算器５１２は、ＨＦ
Ｄ関数発生器５１０により計算された関数の幾つかの項
を使用する。エラーベクトルは、ベツィエ曲線の線セグ
メント近似におけるエラー量の尺度として使用される。
比較器５１４は、エラーベクトル計算器５１２によって
発生された各エラーベクトル項の大きさをテスト大きさ
５０６と比較する。テスト大きさ５０６の値は、特定の
出力装置の解像度に基づいて異なるが、これもシステム
メインメモリ５０４又は他の適当な記憶位置に記憶する
ことができる。エラーベクトル項のいずれかがテスト大
きさ５０６を越える場合には、演算子マトリクス５１６
を用いてアジャスト・ダウン演算子により関数がステッ
プサイズを半分に分割し、そしてＨＦＤ関数発生器５１
０がその減少されたステップサイズに対して関数を評価
する。又、演算子マトリクス５１６は、上記したよう
に、ベツィエ曲線が分割されるたびに、ｎｓｔｅｐｓ５
０７の値を変更する。こんプロセスはエラーベクトル計
算器５１２によって発生された全てのエラーベクトル項
がテスト大きさ５０６より小さくなるまで続けられる。
【００６２】全てのエラーベクトル項がテスト大きさ５
０６より小さくなったことが比較器５１４により指示さ
れると、２つのベツィエ端末ポイントが線セグメント発
生器５１８に与えられ、これはその２つのベツィエ端末
ポイント間に引いた直線セグメントを発生する。線セグ
メント発生器５１８によって発生されたデータポイント
はディスプレイドライバ５２０に送られ、これはデータ
を特定のディスプレイに適したフォーマットに処理す
る。最終的に、このフォーマット化されたデータが、Ｃ
ＲＴ、レーザプリンタ等のディスプレイ５２２に転送さ
れ、ベツィエ曲線の線セグメント近似５２４を表示す
る。
【００６３】メモリ５０４に記憶されたベツィエ制御ポ
イントは、従来のアプリケーションパッケージ又はデジ
タイジングユニットのような種々様々なソースから得る
ことができる。これら全てのソースが入力５２６によっ
て一般的に表されている。
【００６４】エラーベクトル計算器５１２によって発生
された全てのエラーベクトル項がテスト大きさより小さ
いことが比較器５１４で決定された場合には、演算子マ
トリクス５１６はアジャスト・アップ演算子を適用して
関数がステップサイズを２倍にするようにする。この２
倍サイズのステップに対してエラーベクトル計算器５１
２によって発生されたエラーベクトル項が全てテスト大
きさ５０６よりも小さい場合には、システム５００は、
線セグメントが反復細分化技術によって導出されるもの
である場合だけ、この大きさステップサイズを使用す
る。さもなくば、システム５００は、小さなステップサ
イズを使用し、ベツィエ曲線の次の部分を描写するよう
に進める。
【００６５】本発明のシステム５００は、ＡＦＤに使用
されるものとして述べたものに類似した式を使用する
が、これらの式を操作して、ＨＦＤ大きさ決めエラーベ
ースでこれらを表すようにする。システム５００は、簡
単なフォワード・ステップ演算子を生じる大きさ決めエ
ラーベースを使用し、これは時間ｔ＝０における評価を
容易にし、導出容易なエラーベクトルを生じさせる。Ａ
ＦＤベースではなくてＨＦＤ大きさ決めエラーベースを
用いることにより、エラーベクトルを決定することがで
きる。決定されたエラーベクトルは、直線セグメントで
ベツィエ曲線を近似する正確度を表している。
【００６６】以上、本発明の原理により立方ベツィエ曲
線を描写する技術について詳細に説明した。本発明の原
理は、いかなる次数のベツィエ曲線にも等しく適用でき
る。立方ベツィエ曲線と他の次数のベツィエ曲線との相
違は、発生されるエラーベクトルの数だけである。立方
ベツィエ曲線は２つのエラーベクトルを有し、４次のベ
ツィエ曲線は３つのエラーベクトルを有する。３つのベ
クトル全ての大きさがテスト大きさより小さくなければ
ならないか、或いはシステムが曲線を細分化する。３つ
のエラーベクトル全ての大きさがテスト大きさより小さ
い場合に、システムはベツィエ曲線の端末ポイント間に
直線セグメントを引いて、曲線を近似する。いずれかの
エラーベクトルの大きさがテスト大きさを越える場合に
は、システムはアジャスト・ダウン演算子を適用してス
テップサイズを減少する。エラーベクトルの大きさが全
てテスト大きさより小さいときに、システムは、ベツィ
エ曲線のその部分を近似する線セグメントを発生し、フ
ォワード・ステップ演算子を適用して、関数の現在位置
を移動する。より大きな線セグメントを用いてベツィエ
曲線の大きな部分を近似できる場合には、その大きな線
セグメントが公知の反復細分化によって使用されるもの
である場合にのみアジャスト・アップ演算子を適用す
る。従って、ベツィエ曲線を非常に効率的なやり方で描
写して、公知の反復細分化方法と同じ線セグメントを形
成し、且つこの描写した曲線をいずれの方向からでも消
去することができる。
【００６７】本発明の幾つかの実施例及び効果を以上に
説明したが、これは単に本発明を解説するためのものに
過ぎず、本発明の範囲内で変更がなされ得ることが明ら
かである。故に、本発明は、特許請求の範囲のみによっ
て限定されるものとする。
【図面の簡単な説明】
【図１】任意の曲線を小さな弧のサブセットにいかに細
分化するかを示す図である。
【図２】立方ベツィエ曲線によって定められた図１の曲
線の弧であって、ベツィエ端末ポイントをまたぐ１組の
個々の線セグメントによってこの弧をいかに近似できる
か、そして公知の方法でその近似の正確さをいかにチェ
ックするかを示した図である。
【図３】図２の曲線を示す図で、公知技術を用いた曲線
の第１近似を示す図である。
【図４】公知方法によって半分に細分化された図３の曲
線を示す図である。
【図５】図４の曲線を示す図で、公知技術の原理により
その一部分が更に細分化されたところを示す図である。
【図６】図５の曲線を示す図で、公知技術の原理により
大きな線セグメントを使用するところを示した図であ
る。
【図７】本発明に使用するエラーベクトルのグラフ的計
算を示す図である。
【図８】本発明の原理によるフローチャートである。
【図９】図８のフローチャートの続きである。
【図１０】図９のフローチャートの続きである。
【図１１】図２の曲線を示す図で、本発明による曲線の
第１近似を示す図である。
【図１２】図１１の曲線を半分に細分化した図である。
【図１３】図１２の曲線を示す図で、本発明の原理によ
りその一部分を更に細分化したところを示す図である。
【図１４】図１３の曲線を示す図で、本発明の原理によ
り線セグメントを拒絶するところを示す図である。
【図１５】図１４の曲線を示す図で、本発明の原理によ
り線セグメントを受け入れるとこころを示す図である。
【図１６】本発明を実施する典型的なコンピュータシス
テムを示す図である。
【図１７】本発明を実施する図１６のコンピュータシス
テムの機能図である。
【符号の説明】
２ 曲線 ４、６、１０、１４ ポイント ８、１２、１６ 弧 １８、２０ 制御ポイント ２００ ベツィエ曲線 ２０２、２０４、２０６、２０８ ベツィエ制御ポイン
ト ２１０ 線セグメント ２１２、２１４、２１６ ベクトル ２１８、２２０ エラーベクトル ５００ システム ５０２ 中央処理ユニット ５０４ メモリ ５０６ テスト大きさ ５０７ 変数ｎｓｔｅｐｓ ５０８ バス ５１０ ＨＦＤ関数発生器 ５１２ エラーベクトル計算器 ５１４ 比較器 ５１６ 演算子マトリクス ５１８ 線セグメント発生器 ５２０ ディスプレイドライバ ５２２ ディスプレイ ５２６ 入力
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 庁内整理番号 ＦＩ 技術表示箇所 8420−5Ｌ Ｇ０６Ｆ 15/66 ４１０ (72)発明者 ジェームズ エイ グーセン アメリカ合衆国 ワシントン州 98007 ベルヴュー ワンハンドレッドアンドフォ ーティエイス アベニュー ノース イー スト 4735 アパートメント エイエイ 303 (72)発明者 カーク オー オリニク アメリカ合衆国 ワシントン州 98052 レッドモンド ワンハンドレッドアンドセ ヴンティファースト ノース イースト 8610

Claims (20)

    【特許請求の範囲】
  1. 【請求項１】 （ａ）Ｎ−１度のベツィエ曲線を画成す
    る可変数Ｎ個の一連のベツィエ制御ポイントＰ1 ．．．
    ＰN を入力するための入力手段と、 （ｂ）上記ベツィエ曲線を線セグメントで近似すべき所
    望の正確度を表すテスト大きさを選択する手段と、 （ｃ）上記Ｎ個の一連の入力されたベツィエ制御ポイン
    トに基づいてハイブリッドフォワード相違関数を決定す
    る手段と、 （ｄ）ステップサイズを選択する手段であって、上記ハ
    イブリッドフォワード相違関数は該関数の現在位置から
    このステップサイズで定められた端末ポイントまでの上
    記ベツィエ曲線の部分を画成し、上記ハイブリッドフォ
    ワード相違関数が上記ベツィエ制御ポイントＰ1 から上
    記ベツィエ制御ポイントＰN までの全ベツィエ曲線を最
    初に定めるように初期ステップサイズを選択する手段
    と、 （ｅ）上記選択されたステップサイズに基づいて上記ハ
    イブリッドフォワード相違関数から、１組のＮ−２個の
    エラーベクトルＥ1 ．．．ＥN-2 に基づく１組のＮ−２
    個のエラー関数を決定する手段と、 （ｆ）上記Ｎ−２個のエラー関数の各々の大きさを上記
    テスト大きさと比較しそして上記Ｎ−２個のエラー関数
    のいずれかの大きさが上記テスト大きさを越える場合、
    又は上記Ｎ−２個のエラー関数の各々の大きさが上記テ
    スト大きさより小さい場合に、それを指示するための手
    段と、 （ｇ）指示信号に応答して上記ベツィエ曲線を近似する
    ように上記現在ポイントと上記端末ポイントとの間の直
    線セグメントを発生するための線手段とを具備すること
    を特徴とするコンピュータシステム。
  2. 【請求項２】 ハイブリッドフォワード相違関数を決定
    する上記手段は、Ｎ個の項ｅ0 ないしｅN-1 を有すると
    共に、 ｆ(t) ＝ｅ0 Ｅ0(t)＋ｅ1 Ｅ1(t)＋ｅ2 Ｅ2(t)＋．．．ｅN-1 ＥN-1(t) という一般式を有する請求項１に記載のコンピュータシ
    ステム。
  3. 【請求項３】 （ｈ）上記Ｎ−２個のエラーベクトルの
    いずれかの大きさが上記テスト大きさを越えることが上
    記比較手段によって指示された場合に上記ハイブリッド
    フォワード相違関数により取られる上記ステップサイズ
    を減少するように上記ハイブリッドフォワード相違関数
    を変更するための第１変更手段を更に具備し、この第１
    変更手段は、上記現在位置から上記減少されたステップ
    サイズによって定められる新たな端末ポイントまで延び
    る上記ベツィエ曲線の細分化部分を定める第１の動作関
    数を発生しそしてこの第１の動作関数を上記手段（ｅ）
    により処理するために供給すると共に、上記Ｎ−２のエ
    ラーベクトルの各々の大きさが上記テスト大きさよりも
    小さい場合に上記指示信号を発生する請求項１に記載の
    コンピュータシステム。
  4. 【請求項４】 （ｉ）上記Ｎ−２のエラーベクトルの大
    きさが各々上記テスト大きさよりも小さい場合に、上記
    フォワードステップ手段が上記第１変更手段の介在適用
    なしに上記ハイブリッドフォワード相違関数を変更する
    際に、上記ハイブリッドフォワード相違関数によって取
    られる上記ステップサイズを増加するように上記ハイブ
    リッドフォワード相違関数を変更する第２変更手段を更
    に具備し、この第２変更手段は、上記細分化部分より大
    きな上記ベツィエ曲線の部分であって上記現在位置から
    上記増加されたステップサイズによって定められた増加
    された端末ポイントまで延びる部分を定める第２の動作
    関数を発生し、 （ｊ）上記現在位置と上記増加された端末ポイントとの
    間に延びる増加された直線セグメントが反復細分化によ
    って近似されるかどうか決定する一致手段であって、上
    記第２の動作関数から決定された上記Ｎ−２のエラーベ
    クトルのいずれかが上記テスト大きさを越える場合、又
    は上記増加された直線セグメントが反復細分化によって
    導出されないと上記一致手段が決定した場合には、上記
    指示信号を発生し、そして上記第２の動作関数から決定
    された上記Ｎ−２のエラーベクトルの各々の大きさが上
    記テスト大きさよりも小さく且つ上記増加された直線セ
    グメントが反復細分化によって導出されると上記一致手
    段が決定した場合は、上記線セグメントに上記現在位置
    及び上記増加された端末ポイントを与えると共に、上記
    増加された線セグメントを発生するように上記指示信号
    を発生する一致手段を更に具備する請求項１に記載のコ
    ンピュータシステム。
  5. 【請求項５】 線セグメントで曲線を近似すべき所望の
    正確度を表すテスト大きさを用いてベツィエ曲線を近似
    するように反復細分化発生する同じ直線セグメントを発
    生するためのコンピュータシステムにおいて、 （ａ）Ｎ−１度のベツィエ曲線を画成する可変数Ｎ個の
    一連のベツィエ制御ポイントＰ1 ．．．ＰN を入力する
    ための入力手段を具備し、上記ベツィエ制御ポイントＰ
    1 及びＰN は上記曲線に一致する端末ポイントであり、 （ｂ）上記Ｎ個の一連の入力されたベツィエ制御ポイン
    トに基づいてハイブリッドフォワード相違関数を決定す
    る手段を更に具備し、 （ｃ）ステップサイズを選択する手段を更に具備し、上
    記ハイブリッドフォワード相違関数は該関数の現在位置
    からこのステップサイズにより定められた端末ポイント
    までの上記ベツィエ曲線の部分を画成し、上記ハイブリ
    ッドフォワード相違関数が上記ベツィエ制御ポイントＰ
    1 から上記ベツィエ制御ポイントＰN までの全ベツィエ
    曲線を最初に定めるように初期ステップサイズが選択さ
    れ、 （ｄ）上記選択されたステップサイズに基づいて上記ハ
    イブリッドフォワード相違関数から、１組のＮ−２のエ
    ラーベクトルＥ1 ．．．ＥN-2 を決定する手段を更に具
    備し、 （ｅ）上記Ｎ−２のエラーベクトルのいずれかの大きさ
    が上記テスト大きさを越える場合に上記ハイブリッドフ
    ォワード相違関数によって取られる上記ステップサイズ
    を減少するように上記ハイブリッドフォワード相違関数
    を変更するための第１変更手段を更に具備し、この第１
    変更手段は、上記現在位置から上記減少されたステップ
    サイズによって定められる新たな端末ポイントまで延び
    る上記ベツィエ曲線の細分化部分を定める第１の動作関
    数を発生し、そしてこの第１動作関数を上記手段（ｄ）
    により処理するために供給し、 （ｆ）指示信号に応答して上記ベツィエ曲線を近似する
    ように上記現在ポイントと上記端末ポイントとの間の直
    線セグメントを発生するための線手段を更に具備し、 （ｇ）上記線手段が直線を発生するときに上記ハイブリ
    ッドフォワード相違関数を変更するフォワードステップ
    手段を更に具備し、このフォワードステップ手段は、上
    記ハイブリッドフォワード相違関数の上記現在位置を上
    記ステップサイズによって定められた上記端末ポイント
    へ上記ステップサイズを変更せずに移動することにより
    上記ベツィエ曲線の細分化部分を定めるフォワード動作
    関数を発生しそしてこのフォワード動作関数を上記手段
    （ｄ）により処理するために供給し、 （ｈ）上記Ｎ−２のエラーベクトルの大きさが各々上記
    テスト大きさよりも小さい場合に、上記フォワードステ
    ップ手段が上記第１変更手段の介在適用なしに上記ハイ
    ブリッドフォワード相違関数を変更する際に、該関数に
    より取られる上記ステップサイズを増加するように上記
    ハイブリッドフォワード相違関数を変更する第２変更手
    段を更に具備し、この第２変更手段は、上記細分化部分
    より大きな上記ベツィエ曲線の部分であって上記現在位
    置から上記増加されたステップサイズによって定められ
    た増加された端末ポイントまで延びる部分を定める第２
    の動作関数を発生し、 （ｉ）上記現在位置と上記増加された端末ポイントとの
    間に延びる増加された直線セグメントが反復細分化によ
    って近似されるかどうか決定する一致手段であって、上
    記第２の動作関数から決定された上記Ｎ−２のエラーベ
    クトルの各々の大きさが上記テスト大きさより小さく且
    つ上記増加された直線セグメントが反復細分化により導
    出される場合に上記第２動作関数を上記手段（ｄ）によ
    って処理するように供給し、そして上記第２の動作関数
    から決定された上記Ｎ−２のエラーベクトルのいずれか
    が上記テスト大きさを越えるか又は上記現在位置と上記
    増加された端末ポイントとの間に延びる上記増加された
    直線セグメントが反復細分化によって導出されないと上
    記一致手段が決定した場合は上記指示信号を発生するよ
    うな一致手段を更に具備し、そして （ｊ）上記Ｎ−２のエラーベクトルの各々の大きさを上
    記テスト大きさと比較し、そして上記Ｎ−２のエラーベ
    クトルの各々の大きさが上記テスト大きさより小さく且
    つ上記第１及び第２の変更手段のうちの上記第１の変更
    手段が最も最近に適用された場合に上記指示信号を発生
    するための手段を更に具備することを特徴とするコンピ
    ュータシステム。
  6. 【請求項６】 上記Ｎ−２のエラーベクトルの大きさを
    上記テスト大きさと比較する上記手段は、 上記Ｎ−２のエラーベクトルのベクトル成分を解く手段
    と、 上記Ｎ−２のエラーベクトルの上記解いた成分のうちの
    少なくとも最も大きなものの大きさを上記テスト大きさ
    と比較し、そして上記Ｎ−２のエラーベクトルの上記解
    いたベクトル成分のいずれかの大きさが上記テスト大き
    さを越えるか又は上記Ｎ−２のエラーベクトルの上記解
    いたベクトル成分の各々の大きさが上記テストの成分よ
    り小さい場合にそれを指示するための手段とを備えた請
    求項１又は５のいずれかに記載のシステム。
  7. 【請求項７】 ベツィエ曲線を近似するように直線セグ
    メントを発生するためのコンピュータシステムにおい
    て、 中央プロセッサと、 電気的なデータ及び制御信号を搬送するバスを介して上
    記中央プロセッサに接続されたメモリと、 上記バスを経て上記メモリへＮ−１度のベツィエ曲線を
    定める変数Ｎ個の一連のベツィエ制御ポイント
    Ｐ1 ．．．ＰN を入力するための入力ユニットと、 線セグメントで上記ベツィエ曲線を近似すべき所望の正
    確度を表すテスト大きさと、 上記バスに接続されていて、上記Ｎ個の一連の入力され
    たベツィエ制御ポイントに基づいてハイブリッドフォワ
    ード相違関数を発生するためのハイブリッドフォワード
    相違関数発生器と、 ステップサイズであって、上記ハイブリッドフォワード
    相違関数は該関数の現在位置からこのステップサイズに
    より定められた端末ポイントまでの上記ベツィエ曲線の
    部分を画成し、上記ベツィエ制御ポイントＰ1 から上記
    ベツィエ制御ポイントＰN までの全ベツィエ曲線を定め
    るように初期ステップ値を有しているようなステップサ
    イズと、 上記バスに接続されていて、上記ハイブリッドフォワー
    ド相違関数に基づいて動作し、上記ステップサイズを減
    少して、上記ハイブリッドフォワード相違関数が上記ベ
    ツィエ曲線の小さな部分を表すようにすると共に、上記
    ステップ値を２倍にして上記ハイブリッドフォワード相
    違関数が上記ベツィエ曲線の上記端末ポイントに到達す
    るのに２倍多いステップをとることを表すようにする
    か、上記ステップサイズを増加して、上記ハイブリッド
    フォワード相違関数が上記ベツィエ曲線の大きな部分を
    表すようにすると共に、上記ステップ値を半分にして、
    上記ハイブリッドフォワード相違関数が上記ベツィエ曲
    線の上記端末ポイントに到達するのに半分のステップを
    とることを表すようにするか、又は現在ステップサイズ
    でフォワードステップをとるようにして、上記ハイブリ
    ッドフォワード相違関数の現在位置が上記現在ステップ
    で増加されるようにし、そして上記ステップ値を減少し
    て、上記ハイブリッドフォワード相違関数が現在ステッ
    プサイズで上記ベツィエ曲線の上記端末ポイントに向か
    って１ステップとったことを指示するようにする１組の
    演算子と、 上記バスに接続されていて、上記ハイブリッドフォワー
    ド相違関数から１組のＮ−２のエラーベクトルを決定す
    るエラーベクトル計算器と、 上記テスト大きさの値を各々の上記Ｎ−２のエラーベク
    トルの大きさの値と比較し、そして上記Ｎ−２のエラー
    ベクトルのいずれかの大きさが上記テスト大きさを越え
    る場合、又は上記Ｎ−２のエラーベクトルの大きさが各
    々上記テスト大きさより小さい場合にそれを指示するた
    めの比較器と、 上記現在位置及び上記端末ポイントを受け取り、そして
    指示信号を受け取った際に、上記現在位置と上記端末ポ
    イントとの間に引いた線セグメントを形成するようにピ
    クセルに対応する複数のデータ値を発生するための線セ
    グメント発生器と、 上記複数のデータポイントを受け取り、これらデータポ
    イントを表示フォーマットに変換する表示ドライバと、 上記変換されたデータポイントを受け取り、上記現在位
    置と上記端末ポイントとの間に引いた上記線セグメント
    に対応する像を発生して、上記ベツィエ曲線の少なくと
    も一部分を近似するためのディスプレイとを具備するこ
    とを特徴とするコンピュータシステム。
  8. 【請求項８】 上記１組の演算子は、上記Ｎ−２のエラ
    ーベクトルのいずれかの大きさが上記テスト大きさを越
    えることが上記比較器により指示された場合には、これ
    ら１組の演算子のうちの第１演算子を上記ハイブリッド
    フォワード相違関数に適用して上記ステップサイズを減
    少し、上記ベツィエ曲線の小さな部分を表す動作ハイブ
    リッドフォワード相違関数を形成すると共に、上記動作
    ハイブリッドフォワード相違関数を上記エラーベクトル
    計算器へ供給し、そして上記Ｎ−２のエラーベクトルの
    各々の大きさが上記テスト大きさより小さい場合は上記
    指示信号を発生する請求項７に記載のシステム。
  9. 【請求項９】 上記１組の演算子は、上記線セグメント
    発生器が上記第１演算子の介在適用なしに直線を発生す
    る際に、これら１組の演算子のうちの第２の演算子を上
    記ハイブリッドフォワード相違関数に適用して上記ステ
    ップサイズを増加し、上記現在位置と上記ステップサイ
    ズにより定められた増加された端末ポイントとの間に延
    びる上記ベツィエ曲線の大きな部分を表す第２の動作ハ
    イブリッドフォワード相違関数を形成し、上記上記第２
    の動作関数から決定された上記Ｎ−２のエラーベクトル
    のいずれかの大きさが上記テスト大きさを越える場合又
    は上記ステップ値が奇数である場合には上記指示信号を
    発生し、そして上記動作された関数から決定された上記
    Ｎ−２のエラーベクトルの各々の大きさが上記テスト大
    きさより小さく且つ上記ステップ値が偶数である場合に
    は、上記線セグメント発生器に上記現在位置及び上記増
    加された端末ポイントを供給すると共に、上記現在位置
    と上記増加された端末ポイントとの間に延びる増加され
    た直線セグメントを発生するように上記指示信号を発生
    する請求項８に記載のシステム。
  10. 【請求項１０】 上記比較器は、上記Ｎ−２のエラーベ
    クトルの上記解かれたベクトル成分のうちの少なくとも
    最も大きいものの大きさを上記テスト大きさと比較し、
    そして上記Ｎ−２のエラーベクトルの上記解かれたベク
    トル成分のいずれかの大きさが上記テスト大きさを越え
    る場合、又は上記Ｎ−２のエラーベクトルの上記解かれ
    たベクトル成分の大きさが各々上記テスト大きさより小
    さい場合にそれを指示する請求項７に記載のシステム。
  11. 【請求項１１】 上記ハイブリッドフォワード相違関数
    は、Ｎ個の項ｅ0 ないしｅN-1 を有すると共に、 ｆ(t) ＝ｅ0 Ｅ0(t)＋ｅ1 Ｅ1(t)＋ｅ2 Ｅ2(t)＋．．．ｅN-1 ＥN-1(t) という一般式を有する請求項７に記載のコンピュータシ
    ステム。
  12. 【請求項１２】 上記Ｎの値は４である請求項１、５又
    は７のいずれかに記載のシステム。
  13. 【請求項１３】 ベツィエ曲線を近似するように直線セ
    グメントを発生するための方法において、 （ａ）Ｎ−１度のベツィエ曲線を画成する可変数Ｎ個の
    一連のベツィエ制御ポイントＰ1 ．．．ＰN を入力し、 （ｂ）上記ベツィエ曲線を線セグメントで近似すべき所
    望の正確度を表すテスト大きさを選択し、 （ｃ）上記Ｎ個の一連の入力されたベツィエ制御ポイン
    トに基づいてハイブリッドフォワード相違関数を決定
    し、 （ｄ）ステップサイズを選択し、上記ハイブリッドフォ
    ワード相違関数は該関数の現在位置からこのステップサ
    イズにより定められた端末ポイントまでの上記ベツィエ
    曲線の部分を画成し、上記ハイブリッドフォワード相違
    関数が上記ベツィエ制御ポイントＰ1 から上記ベツィエ
    制御ポイントＰN までの全ベツィエ曲線を最初に定める
    ように初期ステップサイズを選択し、 （ｅ）上記選択されたステップサイズに基づいて上記ハ
    イブリッドフォワード相違関数から、１組のＮ−２のエ
    ラーベクトルＥ1 ．．．ＥN-2 により１組のＮ−２のエ
    ラー関数を決定し、 （ｆ）上記Ｎ−２のエラー関数の各々の大きさを上記テ
    スト大きさと比較し、そして上記Ｎ−２のエラー関数の
    いずれかの大きさが上記テスト大きさを越える場合、又
    は上記Ｎ−２のエラー関数の各々の大きさが上記テスト
    大きさより小さい場合に、それを指示し、そして （ｇ）指示信号を受け取った際に上記ベツィエ曲線の少
    なくとも一部分を近似するように上記現在ポイントと上
    記端末ポイントとの間の直線セグメントを発生する、と
    いう段階を備えたことを特徴とする方法。
  14. 【請求項１４】 上記１組のＮ−２のエラー関数は、上
    記１組のＮ−２のエラーベクトルである請求項１３に記
    載の方法。
  15. 【請求項１５】 （ｈ）上記Ｎ−２のエラーベクトルの
    大きさを上記テスト大きさと比較する上記段階により、
    上記Ｎ−２のエラーベクトルのいずれかの大きさが上記
    テスト大きさを越えることが指示された場合には、上記
    ハイブリッドフォワード相違関数によって取られる上記
    ステップサイズを減少するように上記ハイブリッドフォ
    ワード相違関数を変更し、或いは上記比較段階により上
    記Ｎ−２のエラーベクトルの大きさが上記テスト大きさ
    より小さいことが指示された場合には、上記指示信号を
    発生し、 （ｉ）上記現在位置から上記減少されたステップサイズ
    により定められた新たな端末ポイントまで延びる上記ベ
    ツィエ曲線の細分化部分を定める第１の動作関数を発生
    し、そして （ｊ）上記第１の動作関数を上記段階（ｅ）ないし
    （ｇ）で処理するための与える、という段階を更に備え
    た請求項１４に記載の方法。
  16. 【請求項１６】 （ｋ）上記段階（ｈ）ないし（ｊ）を
    介在適用せずに上記段階（ｇ）で直線を発生したとき
    に、上記比較により上記Ｎ−２のエラーベクトルの大き
    さが上記テスト大きさより各々小さい場合には、上記ハ
    イブリッドフォワード相違関数によって取られる上記ス
    テップサイズを増加するように上記ハイブリッドフォワ
    ード相違関数を変更し、 （ｌ）上記細分化部分より大きく且つ上記現在位置から
    上記増加されたステップサイズにより定められた増加さ
    れた端末ポイントまで延びる上記ベツィエ曲線の部分を
    定める第２の動作関数を発生し、 （ｍ）上記第２の動作関数から決定された上記Ｎ−２の
    エラーベクトルのいずれかの大きさが上記テスト大きさ
    を越える場合には上記の指示信号を発生し、 （ｎ）上記現在位置と上記増加された端末ポイントとの
    間に延びる増加された直線セグメントが反復細分化によ
    って導出されるかどうかを決定し、そして （ｏ）上記増加された線セグメントが反復細分化によっ
    て導出されない場合には上記指示信号を発生し、或いは
    上記第２の動作関数から決定された上記Ｎ−２のエラー
    ベクトルの各々の大きさが上記テスト大きさより小さく
    且つ上記増加された線セグメントが反復細分化によって
    導出される場合には上記現在位置及び上記増加された端
    末ポイントを上記段階（ｇ）で処理するために与えそし
    て上記指示信号を発生する、という段階を更に備えた請
    求項１５に記載の方法。
  17. 【請求項１７】 上記Ｎ−２のエラーベクトルの大きさ
    を上記テスト大きさと比較する上記段階は、 上記Ｎ−２のエラーベクトルの各々に対して最も大きさ
    ベクトル成分を決定しそして選択し、 各々の上記Ｎ−２のエラーベクトルの上記選択されたベ
    クトル成分の大きさを上記テスト大きさと比較し、そし
    て上記Ｎ−２のエラーベクトルのいずれかの上記選択さ
    れたベクトル成分の大きさが上記テスト大きさを越える
    場合又は各々の上記Ｎ−２のエラーベクトルの上記選択
    されたベクトル成分の大きさが上記テスト大きさより小
    さい場合にそれを指示する、という段階を備えた請求項
    １４に記載の方法。
  18. 【請求項１８】 上記ハイブリッドフォワード相違関数
    は、Ｎ個の項ｅ0 ないしｅN-1 を有すると共に、 ｆ(t) ＝ｅ0 Ｅ0(t)＋ｅ1 Ｅ1(t)＋ｅ2 Ｅ2(t)＋．．．ｅN-1 ＥN-1(t) という一般式を有する請求項１３に記載の方法。
  19. 【請求項１９】 上記Ｎの値は４である請求項１３に記
    載の方法。
  20. 【請求項２０】 上記ベツィエの制御ポイントＰ1 及び
    ＰN は、上記ベツィエ曲線に一致する端末ポイントであ
    る請求項１３に記載の方法。
JP5163592A 1992-07-02 1993-07-01 ベツィエスプラインを描写するようにハイブリッドフォワード相違プロセスを行うシステム及び方法 Pending JPH076232A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/909055 1992-07-02
US07/909,055 US5367617A (en) 1992-07-02 1992-07-02 System and method of hybrid forward differencing to render Bezier splines

Publications (1)

Publication Number Publication Date
JPH076232A true JPH076232A (ja) 1995-01-10

Family

ID=25426578

Family Applications (1)

Application Number Title Priority Date Filing Date
JP5163592A Pending JPH076232A (ja) 1992-07-02 1993-07-01 ベツィエスプラインを描写するようにハイブリッドフォワード相違プロセスを行うシステム及び方法

Country Status (7)

Country Link
US (1) US5367617A (ja)
EP (1) EP0577131B1 (ja)
JP (1) JPH076232A (ja)
KR (1) KR940006049A (ja)
AT (1) ATE193951T1 (ja)
CA (1) CA2099719C (ja)
DE (1) DE69328850T2 (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9274520B2 (en) 2012-03-01 2016-03-01 Nuovo Pignone Srl Method and system for condition monitoring of a group of plants
JP2017528812A (ja) * 2014-09-15 2017-09-28 マイクロソフト テクノロジー ライセンシング，エルエルシー デジタルインクの平滑化及びｇｐｕ−対応レンダリング

Families Citing this family (45)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0604685A1 (en) * 1992-12-28 1994-07-06 Océ-Nederland B.V. Method of modifying the fatness of characters
US5553214A (en) * 1993-08-24 1996-09-03 Digital Equipment Corporation System for delineating and annotating areal regions
US5594852A (en) * 1994-08-17 1997-01-14 Laser Products, Inc. Method for operating a curve forming device
US5566288A (en) * 1994-09-02 1996-10-15 Caterpillar Inc. System and method for automatically fitting a B-spline curve to a set of data points
US5694535A (en) * 1995-03-24 1997-12-02 Novell, Inc. Direct interactive, constant-time curve apparatus and method
US5848246A (en) * 1996-07-01 1998-12-08 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture for a client-server session manager in an interprise computing framework system
US6424991B1 (en) 1996-07-01 2002-07-23 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture for a client-server communication framework
US6038590A (en) * 1996-07-01 2000-03-14 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture for a client-server state machine in an interprise computing framework system
US6304893B1 (en) 1996-07-01 2001-10-16 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture for a client-server event driven message framework in an interprise computing framework system
US6266709B1 (en) 1996-07-01 2001-07-24 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture for a client-server failure reporting process
US6434598B1 (en) 1996-07-01 2002-08-13 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture for a client-server graphical user interface (#9) framework in an interprise computing framework system
US5987245A (en) * 1996-07-01 1999-11-16 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture (#12) for a client-server state machine framework
US6272555B1 (en) 1996-07-01 2001-08-07 Sun Microsystems, Inc. Object-oriented system, method and article of manufacture for a client-server-centric interprise computing framework system
US5999972A (en) * 1996-07-01 1999-12-07 Sun Microsystems, Inc. System, method and article of manufacture for a distributed computer system framework
US6111588A (en) * 1996-12-05 2000-08-29 Adobe Systems Incorporated Creating and modifying curves on a computer display
US6906718B1 (en) * 1997-04-25 2005-06-14 Microsoft Corporation Method and system for efficiently evaluating and drawing NURBS surfaces for 3D graphics
US6208355B1 (en) * 1998-04-07 2001-03-27 Adobe Systems Incorporated Sketch-based editing of curves
US6674435B1 (en) * 1998-09-16 2004-01-06 Texas Instruments Incorporated Fast, symmetric, integer bezier curve to polygon conversion
US6903742B1 (en) 1999-12-01 2005-06-07 Microsoft Corporation Method and apparatus for transforming and rendering graphical curves
JP4066585B2 (ja) * 2000-01-24 2008-03-26 株式会社日立製作所 図形作成方法
US7057615B2 (en) * 2001-06-28 2006-06-06 Microsoft Corporation Method and system for representing and displaying digital ink
US7038697B2 (en) * 2003-02-25 2006-05-02 Microsoft Corporation Color gradient paths
WO2005037223A2 (en) * 2003-10-15 2005-04-28 Brigham And Women's Hospital, Inc. Methods and compositions for immunomodulation
US7057616B2 (en) * 2004-04-23 2006-06-06 Microsoft Corporation Using constrained optimization in curve editing
US20090225078A1 (en) * 2008-03-07 2009-09-10 Jaroslaw Roman Rossignac Rendering Curves Through Iterative Refinement
CN101901488B (zh) * 2009-05-25 2015-09-09 富士通株式会社 用于曲线近似的方法和装置以及图形显示控制方法和装置
US8643650B1 (en) 2009-08-13 2014-02-04 Adobe Systems Incorporated System and method for approximating parametric curves using optimal number of segments
TWI476640B (zh) 2012-09-28 2015-03-11 Ind Tech Res Inst 時間資料序列的平滑化方法與裝置
US9070224B1 (en) * 2012-10-11 2015-06-30 Google Inc. Accurate upper bound for bezier arc approximation error
US10347016B2 (en) * 2016-01-12 2019-07-09 Monotype Imaging Inc. Converting font contour curves
US9785146B2 (en) * 2016-01-26 2017-10-10 Northrop Grumman Systems Corporation Maneuver planning with higher order rational Bezier curves
US10269143B2 (en) 2016-03-25 2019-04-23 Microsoft Technology Licensing, Llc Multiple texture variable opacity stroke rendering and blending
US9965928B2 (en) * 2016-04-15 2018-05-08 Emerson Climate Technologies, Inc. System and method for displaying messages in a column-by-column format via an array of LEDs connected to a circuit of a compressor
US10277115B2 (en) 2016-04-15 2019-04-30 Emerson Climate Technologies, Inc. Filtering systems and methods for voltage control
US10075065B2 (en) 2016-04-15 2018-09-11 Emerson Climate Technologies, Inc. Choke and EMI filter circuits for power factor correction circuits
US10305373B2 (en) 2016-04-15 2019-05-28 Emerson Climate Technologies, Inc. Input reference signal generation systems and methods
US10284132B2 (en) 2016-04-15 2019-05-07 Emerson Climate Technologies, Inc. Driver for high-frequency switching voltage converters
US10656026B2 (en) 2016-04-15 2020-05-19 Emerson Climate Technologies, Inc. Temperature sensing circuit for transmitting data across isolation barrier
US9933842B2 (en) 2016-04-15 2018-04-03 Emerson Climate Technologies, Inc. Microcontroller architecture for power factor correction converter
US10763740B2 (en) 2016-04-15 2020-09-01 Emerson Climate Technologies, Inc. Switch off time control systems and methods
US10312798B2 (en) 2016-04-15 2019-06-04 Emerson Electric Co. Power factor correction circuits and methods including partial power factor correction operation for boost and buck power converters
US10936792B2 (en) 2017-12-21 2021-03-02 Monotype Imaging Inc. Harmonizing font contours
CN111383334B (zh) * 2018-12-28 2022-08-19 北京嘀嘀无限科技发展有限公司 用于渲染对象的系统和方法
CN112269965B (zh) * 2020-08-10 2024-04-05 中国北方车辆研究所 一种非完整约束条件下的连续曲率路径优化方法
US11651548B2 (en) * 2021-07-08 2023-05-16 Huawei Technologies Co., Ltd. Method and apparatus for computer model rasterization

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4620287A (en) * 1983-01-20 1986-10-28 Dicomed Corporation Method and apparatus for representation of a curve of uniform width
US4949281A (en) * 1987-04-23 1990-08-14 H. Berthold Ag Method and apparatus for generating and producing two-dimensional graphic object by polynominal parametric curves
GB2204767B (en) * 1987-05-08 1991-11-13 Sun Microsystems Inc Method and apparatus for adaptive forward differencing in the rendering of curves and surfaces
JP2630605B2 (ja) * 1987-07-29 1997-07-16 三菱電機株式会社 曲面創成方法
US4878182A (en) * 1987-10-30 1989-10-31 International Business Machines Corporation Multiple pixel generator
US5297294A (en) * 1993-03-15 1994-03-29 Washick Steven R Shin guard having kneeshield, accordian pleated flexure area, flexure grooves and ventilation apertures

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9274520B2 (en) 2012-03-01 2016-03-01 Nuovo Pignone Srl Method and system for condition monitoring of a group of plants
JP2017528812A (ja) * 2014-09-15 2017-09-28 マイクロソフト テクノロジー ライセンシング，エルエルシー デジタルインクの平滑化及びｇｐｕ−対応レンダリング

Also Published As

Publication number Publication date
CA2099719A1 (en) 1994-01-03
DE69328850D1 (de) 2000-07-20
EP0577131A2 (en) 1994-01-05
EP0577131B1 (en) 2000-06-14
EP0577131A3 (en) 1995-04-12
US5367617A (en) 1994-11-22
CA2099719C (en) 1999-08-31
DE69328850T2 (de) 2000-11-02
KR940006049A (ko) 1994-03-23
ATE193951T1 (de) 2000-06-15

Similar Documents

Publication Publication Date Title
JPH076232A (ja) ベツィエスプラインを描写するようにハイブリッドフォワード相違プロセスを行うシステム及び方法
JP3318914B2 (ja) ベツィエスプラインをレンダリングするためのシステムおよび方法
JP2501580B2 (ja) 曲線イメ−ジの可視表示発生装置
EP0690396A1 (en) Apparatus and method for analyzing circuits
CN1237739A (zh) 绘制三次曲线的方法和设备
Ebrahimi et al. B-spline curve fitting by diagonal approximation BFGS methods
EP0349182B1 (en) Method and apparatus for approximating polygonal line to curve
JP2677273B2 (ja) ３次ベジェ曲線の折線近似装置
CN117755312A (zh) 车道线拟合方法、电子设备及存储介质
US20020130882A1 (en) Approximating gradients with offset midpoints
JP2938909B2 (ja) 曲面生成方法及びその装置
JP2001229407A (ja) 数値解析用モデル作成装置、数値解析用モデル作成方法および記憶媒体
JPH06274613A (ja) 曲線近似装置
JP3464874B2 (ja) ベジェ曲線による点列トレースの方法および装置
JP2538645B2 (ja) 曲線の折線近似装置
JP3039387B2 (ja) ３次元ｃａｄにおけるｂ−スプライン曲線と直線との交点算出装置
JPH08194816A (ja) 線分近似方法および線分近似方式
JP2725607B2 (ja) Ｂ−スプライン曲面のデータ削減方法および装置
JP2684609B2 (ja) 図形データ処理装置における図形表示方法
JP2507812B2 (ja) 平方根計算方法
JPH0660195A (ja) 曲面表示装置
JPH05334431A (ja) 点列形状データの関数近似装置
JP2002117411A (ja) 曲線描画方法、曲線描画装置および曲線描画プログラムを記録した記録媒体
JPH06274308A (ja) ベジェ曲線均等肉付け作成処理方法
JP4089806B2 (ja) 曲線生成装置およびその方法ならびに記憶媒体

Legal Events

Date Code Title Description
A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20020415