JPH11345344A - ３次曲線を与える方法及び装置 - Google Patents
３次曲線を与える方法及び装置Info
- Publication number
- JPH11345344A JPH11345344A JP10151104A JP15110498A JPH11345344A JP H11345344 A JPH11345344 A JP H11345344A JP 10151104 A JP10151104 A JP 10151104A JP 15110498 A JP15110498 A JP 15110498A JP H11345344 A JPH11345344 A JP H11345344A
- Authority
- JP
- Japan
- Prior art keywords
- control point
- curve
- control points
- points
- control
- 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
Links
Classifications
-
- 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
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Image Generation (AREA)
- Processing Or Creating Images (AREA)
Abstract
(57)【要約】
【課題】 従来の３次ベジエ関数を与える方法と装置
の、コスト、効率の改善をめざす。 【解決手段】 ４制御点の入力データから、２つの独立
した演算装置を並行して利用し、制御点の４つの集合を
パラレルに作成する。アービトレータは、これら４つの
制御点集合から２つの判定を行う。先ず、曲線を与える
条件を満たす制御点集合があれば、これらの集合は線分
作成部に転送され、曲線を与える点が作成される。第二
に、アービトレータは、制御点のどの集合が、パラレル
な水平展開演算のための次のフィードバック入力データ
であるかを判定する。さらに、アービトレータはまた、
曲線を与えるプロセスの停止を制御する。複数の小線分
に区分的に素早く分解されて作成された出力データは、
モニタに表示されるかプリンタに出力される。本方法と
装置とは、ベジエ曲線の幾何学的性質に従い高速で能率
よく曲線を与えるパラレル処理に向いている。
の、コスト、効率の改善をめざす。 【解決手段】 ４制御点の入力データから、２つの独立
した演算装置を並行して利用し、制御点の４つの集合を
パラレルに作成する。アービトレータは、これら４つの
制御点集合から２つの判定を行う。先ず、曲線を与える
条件を満たす制御点集合があれば、これらの集合は線分
作成部に転送され、曲線を与える点が作成される。第二
に、アービトレータは、制御点のどの集合が、パラレル
な水平展開演算のための次のフィードバック入力データ
であるかを判定する。さらに、アービトレータはまた、
曲線を与えるプロセスの停止を制御する。複数の小線分
に区分的に素早く分解されて作成された出力データは、
モニタに表示されるかプリンタに出力される。本方法と
装置とは、ベジエ曲線の幾何学的性質に従い高速で能率
よく曲線を与えるパラレル処理に向いている。
Description
【０００１】
【発明の属する技術分野】本発明は３次曲線を与える方
法及び装置に関するもので、特に、アービトレータの援
助の下で、３次ベジエ曲線（Ｂｅｚｉｅｒ ｃｕｒｖ
ｅ）の４つの制御点の入力データを平行して処理し、モ
ニタに表示するか又はプリンタに出力する、２つの独立
した演算装置によって、素早く複数の小線分に区分的に
分解されたベジエ曲線を与えるために用いられる、方法
及び装置に関する。
法及び装置に関するもので、特に、アービトレータの援
助の下で、３次ベジエ曲線（Ｂｅｚｉｅｒ ｃｕｒｖ
ｅ）の４つの制御点の入力データを平行して処理し、モ
ニタに表示するか又はプリンタに出力する、２つの独立
した演算装置によって、素早く複数の小線分に区分的に
分解されたベジエ曲線を与えるために用いられる、方法
及び装置に関する。
【０００２】
【発明の背景】計算機を用いた設計、又はコンピュータ
・グラフィックスにおいて、アウトライン・フォントで
ある活字を表示するには、３次曲線が通常必要である。
３次曲線に関するベジエ曲線の近似法が、この場合最も
広く用いられている方法である。
・グラフィックスにおいて、アウトライン・フォントで
ある活字を表示するには、３次曲線が通常必要である。
３次曲線に関するベジエ曲線の近似法が、この場合最も
広く用いられている方法である。
【０００３】計算機システムにおいてベジエ曲線を作成
するためには、本来２つの方法がある。その第一は適応
的部分分割法であり、第二は前進差分法である。
するためには、本来２つの方法がある。その第一は適応
的部分分割法であり、第二は前進差分法である。
【０００４】“Ａ ｔｈｅｏｒｅｔｉｃａｌ Ｄｅｖｅ
ｌｏｐｍｅｎｔ ｆｏｒｔｈｅ Ｃｏｍｕｔｅｒ Ｇｅ
ｎｅｒａｔｉｏｎ ａｎｄ Ｄｉｓｐｌａｙｏｆ Ｐｉ
ｅｃｅｗｉｓｅ Ｐｏｌｙｎｏｍｉａｌ Ｓｕｒｆａｃ
ｅｓ”ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐ
ａｔｔｅｒｎＡｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎ
ｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｊａｎ．１９８０、に
よれば、ベジエ曲線に関する適応的部分分割法の原理は
次のように記述される。
ｌｏｐｍｅｎｔ ｆｏｒｔｈｅ Ｃｏｍｕｔｅｒ Ｇｅ
ｎｅｒａｔｉｏｎ ａｎｄ Ｄｉｓｐｌａｙｏｆ Ｐｉ
ｅｃｅｗｉｓｅ Ｐｏｌｙｎｏｍｉａｌ Ｓｕｒｆａｃ
ｅｓ”ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐ
ａｔｔｅｒｎＡｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎ
ｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｊａｎ．１９８０、に
よれば、ベジエ曲線に関する適応的部分分割法の原理は
次のように記述される。
【数１】 と仮定すると、以下のように推論される。
【数２】 但し、ここで、
【数３】 である。
【０００５】図２に示されているように、最初に４つの
制御点Ｐ００、Ｐ０１、Ｐ０２、Ｐ０３が与えられ、対
応する３つの中点Ｐ１１、Ｐ１２、Ｐ１３が導かれる。
次いで、これら３点に関する２つの中点Ｐ２２、Ｐ２３
が得られる。最後に、Ｐ２２とＰ２３間の中点Ｐ３３
が、上式におけるパラメータｕが０．５であるときの点
である。制御点Ｐ００、Ｐ１１、Ｐ２２、Ｐ３３の集合
と制御点Ｐ３３、Ｐ２３、Ｐ１３、Ｐ０３の集合から、
元の曲線の第一半分と第二半分をそれぞれ作成すること
ができる。もしパラメータｕの空間が０．０から１．０
にまたがれば、第一半分はパラメータｕの値０．０から
０．５に関連し、第二半分は０．５から１．０に関連す
る。
制御点Ｐ００、Ｐ０１、Ｐ０２、Ｐ０３が与えられ、対
応する３つの中点Ｐ１１、Ｐ１２、Ｐ１３が導かれる。
次いで、これら３点に関する２つの中点Ｐ２２、Ｐ２３
が得られる。最後に、Ｐ２２とＰ２３間の中点Ｐ３３
が、上式におけるパラメータｕが０．５であるときの点
である。制御点Ｐ００、Ｐ１１、Ｐ２２、Ｐ３３の集合
と制御点Ｐ３３、Ｐ２３、Ｐ１３、Ｐ０３の集合から、
元の曲線の第一半分と第二半分をそれぞれ作成すること
ができる。もしパラメータｕの空間が０．０から１．０
にまたがれば、第一半分はパラメータｕの値０．０から
０．５に関連し、第二半分は０．５から１．０に関連す
る。
【０００６】もしこれら２つの新しい制御点の集合をが
さらに分割し続ければ、多くの新しい制御点が等間隔で
得られる。ベジエ曲線の絶対収束性に従って、分割部分
が遥かに小さくなるにつれて、これらの新しい制御点
は、原型たる曲線を一層近似することができる。
さらに分割し続ければ、多くの新しい制御点が等間隔で
得られる。ベジエ曲線の絶対収束性に従って、分割部分
が遥かに小さくなるにつれて、これらの新しい制御点
は、原型たる曲線を一層近似することができる。
【０００７】バイナリ近似アルゴリズムは、図３に示さ
れているバイナリーツリーによって、適切に図示するこ
とができる。４点からなる制御点の最初の集合Ｃは、制
御点の２つの部分集合ＬＣとＲＣを作成する。そしてこ
れらの部分集合は、さらにこのバイナリーツリーの最終
の出力として、ＬＬＣ，ＲＬＣ、ＬＲＣ，ＲＲＣを作成
する。従って上記適応的部分分割法は、従来のバイナリ
ーツリーにおける、深度第一横断法に極めて似ている。
制御点の右部分集合に属するデータは、スタックメモリ
に格納され、制御点の左部分集合に属するデータは、現
在の分割が終了すれば、次の分割プロセスのためのソー
スデータとして使われる。分割されるべき制御点の部分
集合が収束条件を満たせば、すなわち、この部分集合の
４つの制御点が同一直線上にあれば、この部分集合は曲
線を与えるために使われ、さらに分割されることをやめ
る。そしてスタックメモリに押し込まれていた右部分集
合が、次の分割プロセスのためのソースデータとして使
われる。このようなプロセスを、利用できるデータがな
くなるまで、繰り返す。
れているバイナリーツリーによって、適切に図示するこ
とができる。４点からなる制御点の最初の集合Ｃは、制
御点の２つの部分集合ＬＣとＲＣを作成する。そしてこ
れらの部分集合は、さらにこのバイナリーツリーの最終
の出力として、ＬＬＣ，ＲＬＣ、ＬＲＣ，ＲＲＣを作成
する。従って上記適応的部分分割法は、従来のバイナリ
ーツリーにおける、深度第一横断法に極めて似ている。
制御点の右部分集合に属するデータは、スタックメモリ
に格納され、制御点の左部分集合に属するデータは、現
在の分割が終了すれば、次の分割プロセスのためのソー
スデータとして使われる。分割されるべき制御点の部分
集合が収束条件を満たせば、すなわち、この部分集合の
４つの制御点が同一直線上にあれば、この部分集合は曲
線を与えるために使われ、さらに分割されることをやめ
る。そしてスタックメモリに押し込まれていた右部分集
合が、次の分割プロセスのためのソースデータとして使
われる。このようなプロセスを、利用できるデータがな
くなるまで、繰り返す。
【０００８】適応的部分分割法には４つの利点がある。
先ず第一に、入力及び出力データはフォーマットにおい
て一致しているということである。すなわち、ソースデ
ータも出力データもともに制御点である。もし並列のベ
ジエ作成部があれば、求める曲線は、適当な直列結合に
よって、パラレルに実現することができる。第二に、加
算器とシフト器を用いる簡単な演算だけが必要であり、
容易にハードウェア回路またはマイクロプログラムによ
って実現できる。第三に、どのレベルまでの分割が必要
であるのかを決定する収束条件に従えば、良い出力デー
タが、厳密な変動を持った任意の曲線からでも導かれ
る。第四に、もし曲線が、可視ウインドウをはみ出せ
ば、上記トップダウン分割プロセスが、この可視ウイン
ドウ外の不必要な演算を締め出すことができる。
先ず第一に、入力及び出力データはフォーマットにおい
て一致しているということである。すなわち、ソースデ
ータも出力データもともに制御点である。もし並列のベ
ジエ作成部があれば、求める曲線は、適当な直列結合に
よって、パラレルに実現することができる。第二に、加
算器とシフト器を用いる簡単な演算だけが必要であり、
容易にハードウェア回路またはマイクロプログラムによ
って実現できる。第三に、どのレベルまでの分割が必要
であるのかを決定する収束条件に従えば、良い出力デー
タが、厳密な変動を持った任意の曲線からでも導かれ
る。第四に、もし曲線が、可視ウインドウをはみ出せ
ば、上記トップダウン分割プロセスが、この可視ウイン
ドウ外の不必要な演算を締め出すことができる。
【０００９】しかしながら、適応的部分分割法には、い
くつかの不利な点がある。先ず、制御点を一時的に格納
しその格納されたデータを引き出すために使われる、高
速のスタックメモリを１セット備えることが必要であ
る。第二に、追跡動作を行うためにバイナリーツリーを
用いるに当たって、バイナリーツリーのあらゆるノード
を処理しなければならない。しかし、最終ノードだけが
必要であり、中点群を求める演算は必要でない。
くつかの不利な点がある。先ず、制御点を一時的に格納
しその格納されたデータを引き出すために使われる、高
速のスタックメモリを１セット備えることが必要であ
る。第二に、追跡動作を行うためにバイナリーツリーを
用いるに当たって、バイナリーツリーのあらゆるノード
を処理しなければならない。しかし、最終ノードだけが
必要であり、中点群を求める演算は必要でない。
【００１０】前進差分法においては、差分法の原理が用
いられる。前進差分は△ｆ（ｔ）＝ｆ（ｔ＋δ）−ｆ
（ｔ）と定義される。ここにδ＞０である。ｔn＝ｎ
δ、ｆn＝ｆ（ｔn）のとき、ｆn+1＝ｆn＋△ｆnであ
る。さらに、△ｆn+1＝△ｆn＋△2ｆn、△2ｆn+1＝△2
ｆn＋△3ｆnである。多項式ｆ（ｔ）＝ａ＋ｂｔ＋ｃｔ2
＋ｄｔ3を仮定すれば、
いられる。前進差分は△ｆ（ｔ）＝ｆ（ｔ＋δ）−ｆ
（ｔ）と定義される。ここにδ＞０である。ｔn＝ｎ
δ、ｆn＝ｆ（ｔn）のとき、ｆn+1＝ｆn＋△ｆnであ
る。さらに、△ｆn+1＝△ｆn＋△2ｆn、△2ｆn+1＝△2
ｆn＋△3ｆnである。多項式ｆ（ｔ）＝ａ＋ｂｔ＋ｃｔ2
＋ｄｔ3を仮定すれば、
【数４】 となる。初期条件を計算すれば、
【数５】 である。引き続くデータは次式で与えられる。
【数６】
【００１１】前進差分法には２つの利点がある。第一
に、曲線を与えるための求める点を、３つの加算器を使
って素早く作成するのに必要なのは、ただ一つのステッ
プであることである。第二に、ベジエ曲線に限らず、任
意のタイプの３次曲線を与えることができる。
に、曲線を与えるための求める点を、３つの加算器を使
って素早く作成するのに必要なのは、ただ一つのステッ
プであることである。第二に、ベジエ曲線に限らず、任
意のタイプの３次曲線を与えることができる。
【００１２】前進差分法には、尚３つの不利な点があ
る。第一に、幾何学的パラメータを持ったベジエ曲線
を、浮動小数点掛算の前処理によって、３次多項式に変
換することが必要である。第二に、差分値は固定されな
ければならないし、決定するのが非常に難しい。特に、
曲率が極めて有意的に変動し、良い出力データを得るこ
とが難しい場合に、このことが当てはまる。これは、最
も重大な不利な点である。第三に、たとえ計算の現在の
部分が可視ウインドウ外にあっても、それでも、この計
算を行うことが必要である。なぜなら、計算は１点ずつ
順番に完了されなければならないからである。
る。第一に、幾何学的パラメータを持ったベジエ曲線
を、浮動小数点掛算の前処理によって、３次多項式に変
換することが必要である。第二に、差分値は固定されな
ければならないし、決定するのが非常に難しい。特に、
曲率が極めて有意的に変動し、良い出力データを得るこ
とが難しい場合に、このことが当てはまる。これは、最
も重大な不利な点である。第三に、たとえ計算の現在の
部分が可視ウインドウ外にあっても、それでも、この計
算を行うことが必要である。なぜなら、計算は１点ずつ
順番に完了されなければならないからである。
【００１３】上記の不利な点を克服するために、”Ａｄ
ａｐｔｉｖｅ Ｆｏｒｗａｒｄ Ｄｉｆｆｅｒｅｎｃｉ
ｎｇ ｆｏｒ Ｒｅｎｄｅｒｉｎｇ Ｃｕｒｖｅｓ ａ
ｎｄＳｕｒｆａｃｅｓ” Ｃｏｍｐｕｔｅｒ Ｇｒａｐ
ｈｉｃｓ，Ｊｕｌｙ １９８７ は、適応的前進差分
（ＡＦＤ）という修正方法を提供している。先ず、パラ
メータとして制御点を取るベジエ曲線は、ＡＦＤに基づ
く多項式に、次のようにして変換される。
ａｐｔｉｖｅ Ｆｏｒｗａｒｄ Ｄｉｆｆｅｒｅｎｃｉ
ｎｇ ｆｏｒ Ｒｅｎｄｅｒｉｎｇ Ｃｕｒｖｅｓ ａ
ｎｄＳｕｒｆａｃｅｓ” Ｃｏｍｐｕｔｅｒ Ｇｒａｐ
ｈｉｃｓ，Ｊｕｌｙ １９８７ は、適応的前進差分
（ＡＦＤ）という修正方法を提供している。先ず、パラ
メータとして制御点を取るベジエ曲線は、ＡＦＤに基づ
く多項式に、次のようにして変換される。
【数７】 ただし、Ａk（ｔ）＝（（ｔ−ｋ＋１）／ｋ）＊Ａ
k-1（ｔ）、Ａ0（ｔ）＝１である。すなわち、ｔ＝０の
とき、ＡＦＤの基底は以下のようになる。
k-1（ｔ）、Ａ0（ｔ）＝１である。すなわち、ｔ＝０の
とき、ＡＦＤの基底は以下のようになる。
【数８】 ｔ＝ｔ＋１のときには、ＡＦＤの基底は以下のようにな
る。
る。
【数９】
【００１４】この新しい基底は元の多項式に持ち込まれ
て、以下の式が得られる。
て、以下の式が得られる。
【数１０】 この式は元の基底との関係を説明する。従って、ｆ
（ｔ）からｆ（ｔ＋１）への一次変換は
（ｔ）からｆ（ｔ＋１）への一次変換は
【数１１】 をＡＦＤの基底として、演算行列
【数１２】 で表現される。同様に、ｆ（ｔ）からｆ（ｔ／２）、ｆ
（ｔ／２＋１）、ｆ（２ｔ）への一次変換は、Ａを基底
として、それぞれ次の演算行列Ｌ、Ｒ、Ｐで表現され
る。
（ｔ／２＋１）、ｆ（２ｔ）への一次変換は、Ａを基底
として、それぞれ次の演算行列Ｌ、Ｒ、Ｐで表現され
る。
【数１３】
【数１４】
【数１５】
【００１５】理論的には、適応的前進差分法は、前進差
分における高速演算という利点を持っているし、各ステ
ップにおいて、その分割レベルに適合させることもでき
る。一例として、図４に示されているように、適応的前
進差分は、適応的部分分割におけるように、Ｌ演算とＲ
演算を備えているだけでなく、あるいは、前進差分のよ
うに、Ｅ演算のみを備えているだけでなく、Ｌ、Ｒ、
Ｅ、Ｐという４つの演算を備えている。
分における高速演算という利点を持っているし、各ステ
ップにおいて、その分割レベルに適合させることもでき
る。一例として、図４に示されているように、適応的前
進差分は、適応的部分分割におけるように、Ｌ演算とＲ
演算を備えているだけでなく、あるいは、前進差分のよ
うに、Ｅ演算のみを備えているだけでなく、Ｌ、Ｒ、
Ｅ、Ｐという４つの演算を備えている。
【００１６】しかしながら、分割レベルを決定する方法
に対しては議論の余地がある。なぜならば、現在の点と
以前の点との間の距離から、収束性を判定することは、
充分には厳密ではないからである。図５において、最初
の点Ｐ０と最後の点Ｐ３との間の距離はゼロであるが、
その曲線は収束していない。従って、曲線を与えるスピ
ードは、収束条件がゆるやかであれば速いが、収束条件
が厳密すぎると、スピードが遅くなり、その収束条件が
ボトルネックとなる。
に対しては議論の余地がある。なぜならば、現在の点と
以前の点との間の距離から、収束性を判定することは、
充分には厳密ではないからである。図５において、最初
の点Ｐ０と最後の点Ｐ３との間の距離はゼロであるが、
その曲線は収束していない。従って、曲線を与えるスピ
ードは、収束条件がゆるやかであれば速いが、収束条件
が厳密すぎると、スピードが遅くなり、その収束条件が
ボトルネックとなる。
【００１７】要約すれば、従来技術における適応的部分
分割法と適応的前進差分法には次のような不利な点があ
る。 （１）適応的部分分割はスタックメモリ装置を必要と
し、スタックアクセスでの過重な処理によって、システ
ム動作の能率が大きく減退し、分割性能も衰える。 （２）適応的前進差分は、ベジエ曲線のパラメータ表式
を、ＡＦＤ基底表式に変換することを必要とし、そのた
め浮動小数点演算を行うところ、多くの時間がかかる。 （３）適応的前進差分の出力は、制御点の集合の代わり
に、ベジエ曲線の多くの性質を利用できないような、点
フォーマットで表されている。例えば、ベジエ曲線の凸
包に関する性質は、可視ウインドウからこの曲線がはみ
出しているかどうかを判定し、不必要な計算をスキップ
するために使われる。さらに、ベジエ曲線の接線は、制
御点によって決定される。光源と対象物との間の角度を
計算するに際しては、接線は、陰影処理にとっては大い
に求められる情報である。
分割法と適応的前進差分法には次のような不利な点があ
る。 （１）適応的部分分割はスタックメモリ装置を必要と
し、スタックアクセスでの過重な処理によって、システ
ム動作の能率が大きく減退し、分割性能も衰える。 （２）適応的前進差分は、ベジエ曲線のパラメータ表式
を、ＡＦＤ基底表式に変換することを必要とし、そのた
め浮動小数点演算を行うところ、多くの時間がかかる。 （３）適応的前進差分の出力は、制御点の集合の代わり
に、ベジエ曲線の多くの性質を利用できないような、点
フォーマットで表されている。例えば、ベジエ曲線の凸
包に関する性質は、可視ウインドウからこの曲線がはみ
出しているかどうかを判定し、不必要な計算をスキップ
するために使われる。さらに、ベジエ曲線の接線は、制
御点によって決定される。光源と対象物との間の角度を
計算するに際しては、接線は、陰影処理にとっては大い
に求められる情報である。
【００１８】
【発明の概要】本発明の目的は、上記の問題を克服する
ために、メモリ装置、表示装置、そしてキーボードまた
はマウスのような入力装置を備えた計算機システムにお
いて、３次曲線を与えるための方法を提供することであ
る。この方法は次のようなステップを備えている。 ステップ１（入力）：ベジエ曲線における４つの制御点
からなる制御点集合が、ユーザによって入力される。 ステップ２（垂直分割）：この制御点集合が、制御点の
２つの集合、すなわち制御点の左子供集合と右子供集合
に、分割される。 ステップ３（水平分割）：この制御点集合の隣接集合及
び親集合は、適当なアルゴリズムによって、これら４つ
の制御点から導かれる。 ステップ４（出力）：制御点の集合が直線収束条件を満
たせば、最初と最後の点が端点として用いられ、モニタ
に表示されるかプリンタに出力される。 ステップ５（パス選択）：基本的には、隣接集合が次の
プロセスのソースデータとして使われる。もし制御点集
合が収束すれば、親集合が次のプロセスのソースデータ
として選択される。もし子供集合の一つが収束すれば、
この子供集合が次のプロセスのソースデータとして選択
される。 ステップ６（停止）：求める曲線が完成されたかどうか
をチェックし、もし完成されていなければステップ２に
戻る。
ために、メモリ装置、表示装置、そしてキーボードまた
はマウスのような入力装置を備えた計算機システムにお
いて、３次曲線を与えるための方法を提供することであ
る。この方法は次のようなステップを備えている。 ステップ１（入力）：ベジエ曲線における４つの制御点
からなる制御点集合が、ユーザによって入力される。 ステップ２（垂直分割）：この制御点集合が、制御点の
２つの集合、すなわち制御点の左子供集合と右子供集合
に、分割される。 ステップ３（水平分割）：この制御点集合の隣接集合及
び親集合は、適当なアルゴリズムによって、これら４つ
の制御点から導かれる。 ステップ４（出力）：制御点の集合が直線収束条件を満
たせば、最初と最後の点が端点として用いられ、モニタ
に表示されるかプリンタに出力される。 ステップ５（パス選択）：基本的には、隣接集合が次の
プロセスのソースデータとして使われる。もし制御点集
合が収束すれば、親集合が次のプロセスのソースデータ
として選択される。もし子供集合の一つが収束すれば、
この子供集合が次のプロセスのソースデータとして選択
される。 ステップ６（停止）：求める曲線が完成されたかどうか
をチェックし、もし完成されていなければステップ２に
戻る。
【００１９】本発明のもう一つの目的は、メモリ装置、
表示装置、そしてキーボードまたはマウスのような入力
装置を備えた計算機システムにおいて、３次曲線を与え
るための装置を提供することである。この装置は次のよ
うな構成部分を備えている。可視ウインドウ座標レジス
タ：これは、上記曲線が可視域にあるかどうかを判定す
るための基準となる、可視ウインドウの左上端と右下端
の位置座標を、格納するために用いられる。 入力制御点レジスタ：これは入力される制御点を格納す
る。 出力制御点レジスタ：これは出力される制御点を格納す
る。 ＬＲ演算部：これは加算とシフト演算という簡単な演算
を用いた、３層の演算によって、制御点の左子供集合と
右子供集合をパラレルに作成する。 ＥＰ演算部：これは加算とシフト演算という簡単な演算
を用いた、３層の演算によって、制御点の隣接集合と親
集合をパラレルに作成する。 パス選択部：これは収束解析部、可視性判定装置、停止
カウンタを含み、ＬＲおよびＥＰ演算部から導かれる制
御点から、フィードバック入出力を決定する、 線分作成部：これは、表示装置のドライバに従って、一
つのベジエ曲線の最初と最後の制御点を端点として使う
求める直線における、点データを作成する。
表示装置、そしてキーボードまたはマウスのような入力
装置を備えた計算機システムにおいて、３次曲線を与え
るための装置を提供することである。この装置は次のよ
うな構成部分を備えている。可視ウインドウ座標レジス
タ：これは、上記曲線が可視域にあるかどうかを判定す
るための基準となる、可視ウインドウの左上端と右下端
の位置座標を、格納するために用いられる。 入力制御点レジスタ：これは入力される制御点を格納す
る。 出力制御点レジスタ：これは出力される制御点を格納す
る。 ＬＲ演算部：これは加算とシフト演算という簡単な演算
を用いた、３層の演算によって、制御点の左子供集合と
右子供集合をパラレルに作成する。 ＥＰ演算部：これは加算とシフト演算という簡単な演算
を用いた、３層の演算によって、制御点の隣接集合と親
集合をパラレルに作成する。 パス選択部：これは収束解析部、可視性判定装置、停止
カウンタを含み、ＬＲおよびＥＰ演算部から導かれる制
御点から、フィードバック入出力を決定する、 線分作成部：これは、表示装置のドライバに従って、一
つのベジエ曲線の最初と最後の制御点を端点として使う
求める直線における、点データを作成する。
【００２０】ユーザは、ベジエ曲線の制御点データを、
入力制御点レジスタと可視ウインドウ座標レジスタに入
力し、本発明の他の構成部の動作開始を促すことができ
る。右子供、左子供、隣接、および親集合の制御点は、
ＬＲ演算とＥＰ演算によって、制御点の任意の集合から
得ることができる。パス選択部は４点の収束と可視ウイ
ンドウとの関係ををチェックし、次の演算のための、フ
ィードバック入力を決定する。最適条件下においては、
親制御点は収束していなくて、左制御点と右制御点が収
束する。そこで、これら左右の制御点が出力制御点レジ
スタに直接転送される。出力制御点レジスタが有効な制
御点を受け取った後、これらのデータは線分作成部に転
送され、線分作成部は従来のデジタル差分解析部（ＤＤ
Ａ）によって、それらの最初と最後の点をそれぞれ始点
と終点として、求める線分の点データを作成する。従来
の適応的部分分割は、スタックが空になれば、曲線付与
演算を中止する。しかし、本発明は、次のような停止カ
ウンタのセットを設計しなければならない。すなわちこ
のカウンタの値はパス選択部に関連して順応し、カウン
タの値が０より小さくなれば、曲線付与演算が中止され
る。
入力制御点レジスタと可視ウインドウ座標レジスタに入
力し、本発明の他の構成部の動作開始を促すことができ
る。右子供、左子供、隣接、および親集合の制御点は、
ＬＲ演算とＥＰ演算によって、制御点の任意の集合から
得ることができる。パス選択部は４点の収束と可視ウイ
ンドウとの関係ををチェックし、次の演算のための、フ
ィードバック入力を決定する。最適条件下においては、
親制御点は収束していなくて、左制御点と右制御点が収
束する。そこで、これら左右の制御点が出力制御点レジ
スタに直接転送される。出力制御点レジスタが有効な制
御点を受け取った後、これらのデータは線分作成部に転
送され、線分作成部は従来のデジタル差分解析部（ＤＤ
Ａ）によって、それらの最初と最後の点をそれぞれ始点
と終点として、求める線分の点データを作成する。従来
の適応的部分分割は、スタックが空になれば、曲線付与
演算を中止する。しかし、本発明は、次のような停止カ
ウンタのセットを設計しなければならない。すなわちこ
のカウンタの値はパス選択部に関連して順応し、カウン
タの値が０より小さくなれば、曲線付与演算が中止され
る。
【００２１】本発明の他の特徴及び利点は、添付の図面
に関する以下の説明によって明らかとなる。
に関する以下の説明によって明らかとなる。
【００２２】
【発明の実施の形態】図１に関して、このシステムブロ
ック図は、ユーザが曲線の制御点データを入力するため
の入力装置として、キーボード１０とマウス１２を、ま
た入力装置から得られる座標データを格納するために、
メモリ装置１５を含んでいる。さらにＣＰＵ（中央演算
装置）１３が、可視ウインドウの座標データと、メモリ
装置に格納された制御点データを、データバス３０に転
送するために用いられる。可視ウインドウ座標レジスタ
５５と入力制御点レジスタ５０は、上記座標データと制
御点データをそれぞれ受け取る。一度制御点データが入
力制御点レジスタ５０に格納されると、ベジエ曲線の作
成プロセスが起動される。ＬＲ演算部８０は、入力制御
点データの集合を、内部構成を図示する図６に示されて
いるように、制御点の左右の子供集合にパラレルに変換
するために使われる。ＥＰ演算部８５は、入力制御点デ
ータの集合を、内部構成を図示する図７に示されている
ように、制御点の隣接及び親集合にパラレルに変換する
ために使われる。制御プロセスのフローチャートを図示
する図８及び図９に示されているように、出力データを
作成すべきかどうか、フィードバックをどうするか、そ
して最後の停止を、決定するために、パス選択部９０は
ＬＲ及びＥＰ演算部からの制御点を解析する。マルチプ
レクサ７０は、上記２つの演算部の入力源を制御し、こ
れらＬＲおよびＥＰ演算部が、最初の入力データは入力
制御点レジスタ５０からであることを除いて、フィード
バックデータを、パス選択部９０からのみ受け取るよう
にする。出力制御点レジスタ６０は曲線の出力データを
格納する。線分作成部４０は出力データをさらに扱い、
分割され直線に収束するベジエ曲線を、直線的にシミュ
レートする。デイスプレイドライバ２０とデイスプレイ
装置２５は、線分作成部４０に従って、最終結果を表示
するために使われる。
ック図は、ユーザが曲線の制御点データを入力するため
の入力装置として、キーボード１０とマウス１２を、ま
た入力装置から得られる座標データを格納するために、
メモリ装置１５を含んでいる。さらにＣＰＵ（中央演算
装置）１３が、可視ウインドウの座標データと、メモリ
装置に格納された制御点データを、データバス３０に転
送するために用いられる。可視ウインドウ座標レジスタ
５５と入力制御点レジスタ５０は、上記座標データと制
御点データをそれぞれ受け取る。一度制御点データが入
力制御点レジスタ５０に格納されると、ベジエ曲線の作
成プロセスが起動される。ＬＲ演算部８０は、入力制御
点データの集合を、内部構成を図示する図６に示されて
いるように、制御点の左右の子供集合にパラレルに変換
するために使われる。ＥＰ演算部８５は、入力制御点デ
ータの集合を、内部構成を図示する図７に示されている
ように、制御点の隣接及び親集合にパラレルに変換する
ために使われる。制御プロセスのフローチャートを図示
する図８及び図９に示されているように、出力データを
作成すべきかどうか、フィードバックをどうするか、そ
して最後の停止を、決定するために、パス選択部９０は
ＬＲ及びＥＰ演算部からの制御点を解析する。マルチプ
レクサ７０は、上記２つの演算部の入力源を制御し、こ
れらＬＲおよびＥＰ演算部が、最初の入力データは入力
制御点レジスタ５０からであることを除いて、フィード
バックデータを、パス選択部９０からのみ受け取るよう
にする。出力制御点レジスタ６０は曲線の出力データを
格納する。線分作成部４０は出力データをさらに扱い、
分割され直線に収束するベジエ曲線を、直線的にシミュ
レートする。デイスプレイドライバ２０とデイスプレイ
装置２５は、線分作成部４０に従って、最終結果を表示
するために使われる。
【００２３】パス選択部のフローチャートは図８及び図
９に示されている。停止カウンタはステップＳ８０１に
おいてゼロにリセットされる。ステップＳ８０２は、入
力制御点レジスタに格納されているデータに従って、演
算のための入力データの最初の集合を獲得する。ステッ
プＳ８０５において、入力ＣはＬＲおよびＥＰ演算部に
転送され、４つの集合Ｌ、Ｒ、Ｅ、Ｐが得られる。これ
らの集合はＰ、Ｌ、Ｒ、Ｅの優先順位で次のフィードバ
ック入力データとして選ばれる制御データである。この
時、ステップＳ８０６は、入力Ｃが可視ウインドウから
完全にはみ出しているかどうかを判定し、もしそうなら
ば、ステップＳ８０７は、停止条件（すなわち停止カウ
ンターの値がゼロであること）をチェックし、もし停止
条件が満たされているならば、進行中のすべての動作を
停止する。もし入力Ｃが可視ウインドウの完全な外部に
あるが、停止条件が満たされないときは、まだ処理され
ていないバイナリーツリーの構成を維持するための２つ
の答がある。ここで、制御点の親集合が、処理の制御点
としてすでに使われたことを、仮定する。先ず、現在の
制御点集合がこの親集合の左子供集合であり、この親集
合の集合Ｐもまた可視ウインドウの外にあるとすれば、
ステップＳ８１０において、現在の制御点データＣは、
この親集合の集合Ｐで置き換えられ、続いてステップＳ
８１１において、停止カウンタの値は２で割られる。第
二に、もしステップＳ８０９が、現在の制御点集合は制
御点の親集合の右子供集合であるか、上記集合Ｐが可視
ウインドウの完全な外部には存在しないということを獲
得するならば、ステップＳ８１３において、制御点の隣
接集合ＥがＣに取って代わり、ステップＳ８１４は、停
止カウンターの値を１だけ減じる。それから、次の動作
は、ステップＳ８１２を経て、ステップＳ８０３に戻る
ことによって続行される。
９に示されている。停止カウンタはステップＳ８０１に
おいてゼロにリセットされる。ステップＳ８０２は、入
力制御点レジスタに格納されているデータに従って、演
算のための入力データの最初の集合を獲得する。ステッ
プＳ８０５において、入力ＣはＬＲおよびＥＰ演算部に
転送され、４つの集合Ｌ、Ｒ、Ｅ、Ｐが得られる。これ
らの集合はＰ、Ｌ、Ｒ、Ｅの優先順位で次のフィードバ
ック入力データとして選ばれる制御データである。この
時、ステップＳ８０６は、入力Ｃが可視ウインドウから
完全にはみ出しているかどうかを判定し、もしそうなら
ば、ステップＳ８０７は、停止条件（すなわち停止カウ
ンターの値がゼロであること）をチェックし、もし停止
条件が満たされているならば、進行中のすべての動作を
停止する。もし入力Ｃが可視ウインドウの完全な外部に
あるが、停止条件が満たされないときは、まだ処理され
ていないバイナリーツリーの構成を維持するための２つ
の答がある。ここで、制御点の親集合が、処理の制御点
としてすでに使われたことを、仮定する。先ず、現在の
制御点集合がこの親集合の左子供集合であり、この親集
合の集合Ｐもまた可視ウインドウの外にあるとすれば、
ステップＳ８１０において、現在の制御点データＣは、
この親集合の集合Ｐで置き換えられ、続いてステップＳ
８１１において、停止カウンタの値は２で割られる。第
二に、もしステップＳ８０９が、現在の制御点集合は制
御点の親集合の右子供集合であるか、上記集合Ｐが可視
ウインドウの完全な外部には存在しないということを獲
得するならば、ステップＳ８１３において、制御点の隣
接集合ＥがＣに取って代わり、ステップＳ８１４は、停
止カウンターの値を１だけ減じる。それから、次の動作
は、ステップＳ８１２を経て、ステップＳ８０３に戻る
ことによって続行される。
【００２４】もし制御点の集合Ｃの少なくとも一部が可
視ウインドウ内にあれば、ステップＳ８１５は、集合Ｃ
が収束していてかつ親集合の左部分集合かどうかをチェ
ックし、もしそうなら、動作は親集合に向かう。ステッ
プＳ８１８とＳ８１９は、既に述べたステップＳ８１
０、Ｓ８１１と同様である。もし集合Ｃが最後であれ
ば、ステップＳ８２０は、集合Ｃを出力し、進行中のす
べての動作を中止する。
視ウインドウ内にあれば、ステップＳ８１５は、集合Ｃ
が収束していてかつ親集合の左部分集合かどうかをチェ
ックし、もしそうなら、動作は親集合に向かう。ステッ
プＳ８１８とＳ８１９は、既に述べたステップＳ８１
０、Ｓ８１１と同様である。もし集合Ｃが最後であれ
ば、ステップＳ８２０は、集合Ｃを出力し、進行中のす
べての動作を中止する。
【００２５】ステップＳ８５０の後、ステップＳ８５１
が、ＬおよびＲをチェックするために使われる。このと
き、３つの場合がある。先ず、もし集合ＬとＲが収束し
ているならば、ステップＳ８５９において、制御点の隣
接集合Ｅが制御点の現在集合Ｃに取って代わり、ステッ
プＳ８６０において、停止カウンタの値は１だけ減じら
れる。そしてステップＳ８６１は、集合ＬとＲをパラレ
ルに出力する。第二に、もし集合Ｌが収束しているが、
集合Ｒは収束していなければ、ステップＳ８５３におい
て、制御点の集合Ｒが制御点の現在集合Ｃに取って代わ
り、ステップＳ８５４は集合Ｌを出力し、ステップＳ８
５５は停止カウンタの値を２倍する。第３に、もし集合
Ｌが収束していなければ、ステップＳ８５７において、
集合Ｌが現在集合Ｃに取って代わり、ステップＳ８５８
は、停止カウンタの値を２倍し、それから１を加える。
が、ＬおよびＲをチェックするために使われる。このと
き、３つの場合がある。先ず、もし集合ＬとＲが収束し
ているならば、ステップＳ８５９において、制御点の隣
接集合Ｅが制御点の現在集合Ｃに取って代わり、ステッ
プＳ８６０において、停止カウンタの値は１だけ減じら
れる。そしてステップＳ８６１は、集合ＬとＲをパラレ
ルに出力する。第二に、もし集合Ｌが収束しているが、
集合Ｒは収束していなければ、ステップＳ８５３におい
て、制御点の集合Ｒが制御点の現在集合Ｃに取って代わ
り、ステップＳ８５４は集合Ｌを出力し、ステップＳ８
５５は停止カウンタの値を２倍する。第３に、もし集合
Ｌが収束していなければ、ステップＳ８５７において、
集合Ｌが現在集合Ｃに取って代わり、ステップＳ８５８
は、停止カウンタの値を２倍し、それから１を加える。
【００２６】図１０はパス選択のシミュレーションを例
示するために使われる。ここで、曲線を与える各プロセ
スはバイナリーツリーの構造に対応する。図１０におい
て、ＬＲ演算部に対する分割動作の順序は、ノード９０
０、ノード９１０、ノード９２０の順である。このシス
テムはノード９２１と９２２のデータを出力し、ノード
９３０に向かう。というのは、ノード９２０から導かれ
る、ノード９２１と９２２に関する制御点が収束するた
めである。このシステムはノード９３１と９３２のデー
タを出力し、ノード９４０に向かう。というのは、ノー
ド９３０から導かれるノード９３１と９３２に関する制
御点が収束するためである。しかしながら、ノード９４
０のための制御点が収束し、システムはさらにノード９
５０に向かう。ノード９５０の観点からは、ノード９４
０の制御点が収束し、システムはノード９４０のための
制御点を出力するが、ノード９６０が収束していないの
で、システムはさらにノード９６０に向かう。ノード９
６１とノード９６２は収束しているので、システムはノ
ード９６１と９６２の制御点データを閉め出す。
示するために使われる。ここで、曲線を与える各プロセ
スはバイナリーツリーの構造に対応する。図１０におい
て、ＬＲ演算部に対する分割動作の順序は、ノード９０
０、ノード９１０、ノード９２０の順である。このシス
テムはノード９２１と９２２のデータを出力し、ノード
９３０に向かう。というのは、ノード９２０から導かれ
る、ノード９２１と９２２に関する制御点が収束するた
めである。このシステムはノード９３１と９３２のデー
タを出力し、ノード９４０に向かう。というのは、ノー
ド９３０から導かれるノード９３１と９３２に関する制
御点が収束するためである。しかしながら、ノード９４
０のための制御点が収束し、システムはさらにノード９
５０に向かう。ノード９５０の観点からは、ノード９４
０の制御点が収束し、システムはノード９４０のための
制御点を出力するが、ノード９６０が収束していないの
で、システムはさらにノード９６０に向かう。ノード９
６１とノード９６２は収束しているので、システムはノ
ード９６１と９６２の制御点データを閉め出す。
【００２７】上記で述べたことは、シミュレーションの
フローチャートとその結果である。４つの点を以下詳述
する。その第一は、ＬＲ演算部とＥＰ演算部のための内
部構成と動作である。第二は制御点の収束をどのように
判定するかである。第三は、曲線が可視ウインドウの内
部にあるかどうかをどう判定するかである。第四は、３
次曲線を与えるための、本発明の装置の効率性である。
フローチャートとその結果である。４つの点を以下詳述
する。その第一は、ＬＲ演算部とＥＰ演算部のための内
部構成と動作である。第二は制御点の収束をどのように
判定するかである。第三は、曲線が可視ウインドウの内
部にあるかどうかをどう判定するかである。第四は、３
次曲線を与えるための、本発明の装置の効率性である。
【００２８】１．ＬＲ演算部とＥＰ演算部のための内部
構成と動作： ＬＲ演算部は図６に示されているような
従来の適応的部分分割の設計を用いる。各々の小円は
（Ａ＋Ｂ）／２を作成する演算単位を表す。ここで、Ａ
とＢは２つの入力データである。３つの演算の後、元の
制御点（Ｐ００，Ｐ０１，Ｐ０２，Ｐ０３）は左子供集
合（Ｐ００，Ｐ１１，Ｐ２２，Ｐ３３）と右子供集合
（Ｐ３３、Ｐ２３、Ｐ１３、Ｐ０３）に分割される。
構成と動作： ＬＲ演算部は図６に示されているような
従来の適応的部分分割の設計を用いる。各々の小円は
（Ａ＋Ｂ）／２を作成する演算単位を表す。ここで、Ａ
とＢは２つの入力データである。３つの演算の後、元の
制御点（Ｐ００，Ｐ０１，Ｐ０２，Ｐ０３）は左子供集
合（Ｐ００，Ｐ１１，Ｐ２２，Ｐ３３）と右子供集合
（Ｐ３３、Ｐ２３、Ｐ１３、Ｐ０３）に分割される。
【００２９】ＥＰ演算部は本発明において提供される。
これはＬＲ演算部に類似の演算部で、図７に例示されて
いる。各々の小円は２Ｂ−Ａを作成する演算単位を表
す。ここで、ＡとＢは２つの入力データである。３つの
演算の後、元の制御点（Ｐ００，Ｐ０１，Ｐ０２，Ｐ０
３）は親集合（Ｐ００，Ｐ１１，Ｐ２２，Ｐ３３）と隣
接集合（Ｐ０３、Ｐ１３、Ｐ２３、Ｐ３３）に分割され
る。
これはＬＲ演算部に類似の演算部で、図７に例示されて
いる。各々の小円は２Ｂ−Ａを作成する演算単位を表
す。ここで、ＡとＢは２つの入力データである。３つの
演算の後、元の制御点（Ｐ００，Ｐ０１，Ｐ０２，Ｐ０
３）は親集合（Ｐ００，Ｐ１１，Ｐ２２，Ｐ３３）と隣
接集合（Ｐ０３、Ｐ１３、Ｐ２３、Ｐ３３）に分割され
る。
【００３０】よく知られているように、ベジエ曲線のた
めのＬＲ演算部の分割プロセスは次のようである。
めのＬＲ演算部の分割プロセスは次のようである。
【数１６】 と仮定すると、以下のように推論される。
【数１７】 但し、ここで、
【数１８】 である。
【００３１】本発明はＥＰ演算部のために次のアルゴリ
ズムを提供する（これは帰納法によって証明することが
できる。）。
ズムを提供する（これは帰納法によって証明することが
できる。）。
【数１９】 と仮定すると、以下のように推論される。
【数２０】 但し、ここで、
【数２１】 である。
【００３２】本発明は３次曲線だけでなく２次曲線また
はより高次の曲線を作成することができる。さらに、本
発明をより明瞭に説明すると、図６及び図７は共に６つ
の演算部を用いる。これらの演算部をハードウエアー回
路で実現することを望むならば、適当なフィードバック
回路を付け加えることによって、演算部の数を３つに減
らすことができる。
はより高次の曲線を作成することができる。さらに、本
発明をより明瞭に説明すると、図６及び図７は共に６つ
の演算部を用いる。これらの演算部をハードウエアー回
路で実現することを望むならば、適当なフィードバック
回路を付け加えることによって、演算部の数を３つに減
らすことができる。
【００３３】２．制御点の収束を判定する方法： 図１
１に示されているように、集合Ｃ（Ｐ１００、ｐ２０
０、Ｐ３００、Ｐ４００）によって定義されるベジエ曲
線が、直線に収束しているかどうかを判定するために、
従来の方法はＰ２００とＰ３００から、Ｐ１００とＰ４
００間の線分にそれぞれ垂線を引く。もし得られる２つ
の線分の長さが、あるしきい値よりも小さいならば、こ
れらの制御点は収束していると判定される。
１に示されているように、集合Ｃ（Ｐ１００、ｐ２０
０、Ｐ３００、Ｐ４００）によって定義されるベジエ曲
線が、直線に収束しているかどうかを判定するために、
従来の方法はＰ２００とＰ３００から、Ｐ１００とＰ４
００間の線分にそれぞれ垂線を引く。もし得られる２つ
の線分の長さが、あるしきい値よりも小さいならば、こ
れらの制御点は収束していると判定される。
【００３４】もっと簡単な次の方法が、計算時間を節約
するために、またはハードウエア回路で実現するのに都
合がよいように、たいていは用いられる。図１１におい
て、２つのベクトルＶ２５０（＝Ｖ２００−Ｖ１００）
とＶ３５０（＝Ｖ２００−Ｖ１００）のみを計算する。
そして、これら２つのベクトルのＸ成分またはＹ成分
が、しきい値よりも小さいならば、これらの制御点は収
束していると判定される。
するために、またはハードウエア回路で実現するのに都
合がよいように、たいていは用いられる。図１１におい
て、２つのベクトルＶ２５０（＝Ｖ２００−Ｖ１００）
とＶ３５０（＝Ｖ２００−Ｖ１００）のみを計算する。
そして、これら２つのベクトルのＸ成分またはＹ成分
が、しきい値よりも小さいならば、これらの制御点は収
束していると判定される。
【００３５】３．曲線が可視ウインドウの内部にあるか
どうかを判定する方法：本発明が前進差分に比べて有利
な点は、現在の制御点が可視ウインドウの外部にあるこ
とを判定し、分割のレベルを動的な方法で適合させるの
がはるかに容易であることである。
どうかを判定する方法：本発明が前進差分に比べて有利
な点は、現在の制御点が可視ウインドウの外部にあるこ
とを判定し、分割のレベルを動的な方法で適合させるの
がはるかに容易であることである。
【００３６】図１２において、制御点（Ｐ００、Ｐ０
１、Ｐ０２、Ｐ０３）によって定義されるベジエ曲線
は、完全に、（Ｂ３００、Ｂ４００）によって定義され
る可視ウインドウの外部にある。これら４つの制御点の
座標の最大最小値が得られれば、この曲線が可視ウイン
ドウの外部にあることを判定するのは容易である。
１、Ｐ０２、Ｐ０３）によって定義されるベジエ曲線
は、完全に、（Ｂ３００、Ｂ４００）によって定義され
る可視ウインドウの外部にある。これら４つの制御点の
座標の最大最小値が得られれば、この曲線が可視ウイン
ドウの外部にあることを判定するのは容易である。
【００３７】４．３次曲線を与えるための、本発明の装
置の効率性：従来の適応的部分分割法より有利な点は、
第一に、メモリスタックが必要でなく、そのためアクセ
ス時間を節約する点である。第二に、適応的部分分割法
にあっては、バイナリーツリーのすべてのノードが処理
されなければならないが、本発明によれば、２端点ノー
ドが処理されればよいことである。未処理のバイナリー
ツリーに関しては、端点ノードの数がＮであれば、全部
で２Ｎ−１のノードがある。
置の効率性：従来の適応的部分分割法より有利な点は、
第一に、メモリスタックが必要でなく、そのためアクセ
ス時間を節約する点である。第二に、適応的部分分割法
にあっては、バイナリーツリーのすべてのノードが処理
されなければならないが、本発明によれば、２端点ノー
ドが処理されればよいことである。未処理のバイナリー
ツリーに関しては、端点ノードの数がＮであれば、全部
で２Ｎ−１のノードがある。
【００３８】適応的前進差分法に比べて有利な点は３つ
ある。第一に、適応的前進差分は、制御点に基づくベジ
エ曲線をＡＦＤに基づくものに変換するため、掛算と割
算のような浮動小数点演算を必要とすることである。第
二に、適応的前進差分は、曲線が可視ウインドウの外部
にあっても、不必要な計算を省略することができないこ
とである。第三に、本発明は、Ｌ、Ｒ、Ｅ、Ｐ演算を、
インテル８０８６プロセッサにおいて実現するには、た
だ１２個の足し算と引き算のプロセス、すなわち３６ク
ロックタイムと、１２個のシフト演算プロセス、すなわ
ち４２クロックタイムを必要とするのに対して、適応的
前進差分は、１４個の足し算と引き算のプロセス、すな
わち４２クロックタイムと、４１個のシフト演算プロセ
ス、すなわち８２クロックタイムを必要とする。
ある。第一に、適応的前進差分は、制御点に基づくベジ
エ曲線をＡＦＤに基づくものに変換するため、掛算と割
算のような浮動小数点演算を必要とすることである。第
二に、適応的前進差分は、曲線が可視ウインドウの外部
にあっても、不必要な計算を省略することができないこ
とである。第三に、本発明は、Ｌ、Ｒ、Ｅ、Ｐ演算を、
インテル８０８６プロセッサにおいて実現するには、た
だ１２個の足し算と引き算のプロセス、すなわち３６ク
ロックタイムと、１２個のシフト演算プロセス、すなわ
ち４２クロックタイムを必要とするのに対して、適応的
前進差分は、１４個の足し算と引き算のプロセス、すな
わち４２クロックタイムと、４１個のシフト演算プロセ
ス、すなわち８２クロックタイムを必要とする。
【００３９】
【発明の効果】本発明には３つの根本的利点がある。 （１）本発明においては、メモリスタック装置は必要で
なく、コストをハードウエアとマイクロプログラミング
によって低下することができる。 （２）制御点は入力データとして直接使われ、浮動小数
点演算は前処理において必要でない。４つの演算Ｌ、
Ｒ、Ｅ、Ｐを求める平均的な効率は、適応的前進差分法
のそれに勝る。 （３）本発明における中間データは、制御点であって、
検出中の曲線が可視ウインドウの外にあることを判定
し、分割と展開のレベルを動的に適応させ、不必要な演
算を閉め出すような場合にベジエ関数の性質を用いるこ
とができる。
なく、コストをハードウエアとマイクロプログラミング
によって低下することができる。 （２）制御点は入力データとして直接使われ、浮動小数
点演算は前処理において必要でない。４つの演算Ｌ、
Ｒ、Ｅ、Ｐを求める平均的な効率は、適応的前進差分法
のそれに勝る。 （３）本発明における中間データは、制御点であって、
検出中の曲線が可視ウインドウの外にあることを判定
し、分割と展開のレベルを動的に適応させ、不必要な演
算を閉め出すような場合にベジエ関数の性質を用いるこ
とができる。
【００４０】上記において、好ましい実施例のみが示さ
れ説明されたが、この発明の範囲にある変形と組み合わ
せは保護されることを、求めるものである。
れ説明されたが、この発明の範囲にある変形と組み合わ
せは保護されることを、求めるものである。
【図１】 本発明における好ましい実施例のシステムブ
ロック図を示す。
ロック図を示す。
【図２】 ベジエ曲線の分割原理を例示する概略図を示
す。
す。
【図３】 繰り返し分割のＬＲ演算を例示するバイナリ
ーツリーの構造を示す。
ーツリーの構造を示す。
【図４】 適応的前進差分のＬ、Ｒ、Ｅ，Ｐ演算を、バ
イナリーツリー構造によって示す。
イナリーツリー構造によって示す。
【図５】 ベジエ曲線の特殊な場合を示す。
【図６】 本発明における好ましい実施例の、ＬＲ演算
部の内部構造を示す。
部の内部構造を示す。
【図７】 本発明における好ましい実施例の、ＥＰ演算
部の内部構造を示す。
部の内部構造を示す。
【図８】 本発明における好ましい実施例の、パス選択
部のフローチャートを示す。
部のフローチャートを示す。
【図９】 本発明における好ましい実施例の、パス選択
部のフローチャート（但し、図８におけるＳ８１６・B
からの延長部）を示す。
部のフローチャート（但し、図８におけるＳ８１６・B
からの延長部）を示す。
【図１０】 本発明における好ましい実施例の、パス選
択部のシミュレーションを図示する。
択部のシミュレーションを図示する。
【図１１】 本発明における好ましい実施例の、制御点
の収束を判定するプロセスを図示する。
の収束を判定するプロセスを図示する。
【図１２】 本発明における好ましい実施例の、可視ウ
インドウにおける捕捉プロセスを図示する。
インドウにおける捕捉プロセスを図示する。
１０…キーボード、１２…マウス、１３…ＣＰＵ（中央
演算装置）、１５…メモリ装置、２０…デイスプレイド
ライバ、２５…デイスプレイ又はプリンタ、３０…デー
タバス、４０…線分作成部、５０…入力制御点レジス
タ、５５…可視ウインドウ座標レジスタ、６０…出力制
御点レジスタ、７０…マルチプレックサ、８０…ＬＲ演
算部、８５…ＥＰ演算部、９０…パス選択部
演算装置）、１５…メモリ装置、２０…デイスプレイド
ライバ、２５…デイスプレイ又はプリンタ、３０…デー
タバス、４０…線分作成部、５０…入力制御点レジス
タ、５５…可視ウインドウ座標レジスタ、６０…出力制
御点レジスタ、７０…マルチプレックサ、８０…ＬＲ演
算部、８５…ＥＰ演算部、９０…パス選択部
Claims (2)
- 【請求項１】 メモリ装置、表示装置、及びキーボード
またはマウスのような入力装置を備えた計算機システム
において、３次曲線を与える方法であって、 ａ．上記３次曲線のベジエ曲線における４つの制御点か
らなる制御点集合を入力するステップと、 ｂ．上記制御点集合から、ＬＲ演算部を用いて、それぞ
れ４つの制御点を持つ左子供集合と右子供集合を作成す
るステップと、 ｃ．上記制御点集合から、適切なアルゴリズムを伴うＥ
Ｐ演算部を用いて、それぞれ４つの制御点を持つ隣接集
合と親集合を作成するステップと、 ｄ．上記制御点集合の４点が直線上にあるという所定の
収束条件を満たすならば、上記制御点集合の最初と最後
の点を用いて、線分を表示又は出力するステップと、 ｅ．上記ベジエ曲線が完成されるならば、上記ベジエ曲
線を与えることを停止するが、さもなくば、ステップｆ
を実行するステップと、 ｆ．上記親集合、上記隣接集合、上記右子供集合、上記
左子供集合を用いて、上記制御点集合を置き換えること
によって、次の繰り返しを続けるためにステップｂに帰
るステップと、 を備え、上記隣接集合が次の繰り返しのための制御点集
合として用いられ、もし上記制御点集合が収束している
ならば、上記親集合が次の繰り返しのための制御点集合
として用いられ、もし上記右子供集合または左子供集合
が収束しているならば、それが次の繰り返しのための制
御点集合として用いられる方法。 - 【請求項２】 メモリ装置、表示装置、そしてキーボー
ドまたはマウスのような入力装置を備えた計算機システ
ムにおいて、３次曲線を与えるための装置であって、上
記曲線が可視域にあるかどうかを判定するための基準と
なる可視ウインドウの左上端と右下端の位置座標を、格
納するために用いられる可視ウインドウ座標レジスタ
と、入力制御点を格納する入力制御点レジスタと、出力
制御点を格納する出力制御点レジスタと、加算とシフト
演算という簡単な演算を用いた３層の演算によって、上
記入力制御点の左子供集合と右子供集合をパラレルに作
成するＬＲ演算部と、加算とシフト演算という簡単な演
算を用いた３層の演算によって、制御点の隣接集合と親
集合をパラレルに作成するＥＰ演算部と、収束解析部、
可視性判定装置、停止カウンタを含み、上記ＬＲおよび
ＥＰ演算部によって作成される、上記左子供集合、右子
供集合、および上記隣接集合、親集合から、フィードバ
ック入出力を決定するパス選択部と、上記表示装置のド
ライバに従って、一つのベジエ曲線の最初と最後の制御
点を端点として使う求める直線における点データを作成
する線分作成部と、を備えている装置。
Priority Applications (6)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10151104A JPH11345344A (ja) | 1998-06-01 | 1998-06-01 | ３次曲線を与える方法及び装置 |
| US09/157,422 US6295072B1 (en) | 1998-06-01 | 1998-09-21 | Method and apparatus for rendering cubic curves |
| SG1998003804A SG71156A1 (en) | 1998-06-01 | 1998-09-22 | Method and apparatus for rendering cubic curves |
| TW087115833A TW376489B (en) | 1998-06-01 | 1998-09-23 | Method and apparatus for rendering cubic curves |
| MYPI98004425A MY116776A (en) | 1998-06-01 | 1998-09-25 | Method and apparatus for rendering cubic curves |
| CN98122411.3A CN1106621C (zh) | 1998-06-01 | 1998-11-18 | 绘制三次曲线的方法和设备 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10151104A JPH11345344A (ja) | 1998-06-01 | 1998-06-01 | ３次曲線を与える方法及び装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11345344A true JPH11345344A (ja) | 1999-12-14 |
Family
ID=15511443
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10151104A Pending JPH11345344A (ja) | 1998-06-01 | 1998-06-01 | ３次曲線を与える方法及び装置 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US6295072B1 (ja) |
| JP (1) | JPH11345344A (ja) |
| CN (1) | CN1106621C (ja) |
| MY (1) | MY116776A (ja) |
| SG (1) | SG71156A1 (ja) |
| TW (1) | TW376489B (ja) |
Families Citing this family (25)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE19901934C2 (de) * | 1999-01-19 | 2001-07-19 | Heidelberger Druckmasch Ag | Verfahren zur Erzeugung eines Rahmens für grafische Objekte, die durch Bezier-Kurven beschrieben sind |
| US20050156930A1 (en) * | 2004-01-20 | 2005-07-21 | Matsushita Electric Industrial Co., Ltd. | Rendering device and rendering method |
| US8068103B2 (en) * | 2004-06-24 | 2011-11-29 | Apple Inc. | User-interface design |
| US7116327B2 (en) * | 2004-08-31 | 2006-10-03 | A{grave over (g)}fa Corporation | Methods for generating control points for cubic bezier curves |
| US20070239696A1 (en) * | 2006-03-28 | 2007-10-11 | Microsoft Corporation | Interactive relational graphic solutions |
| US7930902B2 (en) * | 2006-06-26 | 2011-04-26 | Emhart Glass S.A. | Mechanism for conveying an article |
| US7952580B1 (en) | 2007-08-31 | 2011-05-31 | Adobe Systems Incorporated | Classification of exterior and interior triangles for artwork rendering |
| US7928984B1 (en) | 2007-08-31 | 2011-04-19 | Adobe Systems Incorporated | Efficient data packaging for rendering bézier curves on a GPU |
| US8044955B1 (en) | 2007-08-31 | 2011-10-25 | Adobe Systems Incorporated | Dynamic tessellation spreading for resolution-independent GPU anti-aliasing and rendering |
| US8068106B1 (en) | 2007-08-31 | 2011-11-29 | Adobe Systems Incorporated | Rendering cubic Bézier curves as quadratic curves using a GPU |
| US7868887B1 (en) | 2007-10-18 | 2011-01-11 | Adobe Systems Incorporated | Rendering rational quadratic Bézier curves on a GPU |
| US8350853B2 (en) * | 2007-10-30 | 2013-01-08 | National University Corporation Yokohama National University | Interpolation processing method and interpolation processor |
| US8248419B2 (en) * | 2009-04-21 | 2012-08-21 | Sony Corporation Entertainment Inc. | Generation of cubic Bezier control points in computer graphics systems |
| US20110285718A1 (en) | 2010-05-21 | 2011-11-24 | Kilgard Mark J | Point containment for quadratic bèzier strokes |
| US9092905B2 (en) | 2011-04-15 | 2015-07-28 | Panasonic Intellectual Property Management Co., Ltd. | Curve rendering device, curve rendering method, curve rendering program, and integrated circuit |
| US20130018636A1 (en) * | 2011-07-14 | 2013-01-17 | Microsoft Corporation | Quadratic approximate offset curves for quadratic curve segments |
| CN102999930B (zh) * | 2011-09-15 | 2015-11-25 | 汉王科技股份有限公司 | 一种电子笔迹线条描绘方法及装置 |
| CN103390283B (zh) * | 2012-05-09 | 2017-10-31 | 腾讯科技（深圳）有限公司 | 绘制平行曲线的方法和设备 |
| KR101980200B1 (ko) | 2012-07-12 | 2019-05-20 | 삼성전자주식회사 | 베이지어 커브에 대한 타일 비닝을 수행하는 그래픽 처리 장치 및 방법 |
| CN102903134B (zh) * | 2012-09-13 | 2016-05-04 | 烽火通信科技股份有限公司 | 快速绘制多次曲线的方法 |
| US9965446B1 (en) * | 2013-07-19 | 2018-05-08 | Amazon Technologies, Inc. | Formatting a content item having a scalable object |
| US10347016B2 (en) * | 2016-01-12 | 2019-07-09 | Monotype Imaging Inc. | Converting font contour curves |
| US10936792B2 (en) | 2017-12-21 | 2021-03-02 | Monotype Imaging Inc. | Harmonizing font contours |
| CN110347357B (zh) * | 2019-07-15 | 2020-12-04 | 北大方正集团有限公司 | 打印处理方法和装置 |
| CN113379873B (zh) * | 2021-08-11 | 2021-11-09 | 北京赛目科技有限公司 | 一种道路曲线确定方法、装置、电子设备 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| NL8300872A (nl) * | 1983-03-10 | 1984-10-01 | Philips Nv | Multiprocessor-rekenmachinesysteem voor het tot een gekleurde afbeelding verwerken van in een hierarchische datastruktuur gedefinieerde objekt-elementen. |
| JPH0458378A (ja) | 1990-06-28 | 1992-02-25 | Mitsubishi Heavy Ind Ltd | ベジエ曲線を分割して展開する方法 |
| US5422990A (en) | 1992-04-29 | 1995-06-06 | Canon Kabushiki Kaisha | Bezier spline to quadratic polynomial fragment conversion |
| US5363479A (en) | 1992-07-02 | 1994-11-08 | Microsoft Corporation | System and method for rendering bezier splines |
| JP3287685B2 (ja) | 1994-02-02 | 2002-06-04 | キヤノン株式会社 | データ変換装置及び方法 |
| US5638503A (en) | 1994-07-07 | 1997-06-10 | Adobe Systems, Inc. | Method and apparatus for generating bitmaps from outlines containing bezier curves |
| US5995109A (en) * | 1997-04-08 | 1999-11-30 | Lsi Logic Corporation | Method for rendering high order rational surface patches |
-
1998
- 1998-06-01 JP JP10151104A patent/JPH11345344A/ja active Pending
- 1998-09-21 US US09/157,422 patent/US6295072B1/en not_active Expired - Fee Related
- 1998-09-22 SG SG1998003804A patent/SG71156A1/en unknown
- 1998-09-23 TW TW087115833A patent/TW376489B/zh active
- 1998-09-25 MY MYPI98004425A patent/MY116776A/en unknown
- 1998-11-18 CN CN98122411.3A patent/CN1106621C/zh not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN1106621C (zh) | 2003-04-23 |
| MY116776A (en) | 2004-03-31 |
| TW376489B (en) | 1999-12-11 |
| US6295072B1 (en) | 2001-09-25 |
| CN1237739A (zh) | 1999-12-08 |
| SG71156A1 (en) | 2000-03-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH11345344A (ja) | ３次曲線を与える方法及び装置 | |
| CN115066589A (zh) | 基于动态排序分割的分布式张量网络收缩方案 | |
| Liu et al. | A combined approach to cartographic displacement for buildings based on skeleton and improved elastic beam algorithm | |
| US20180293486A1 (en) | Conditional graph execution based on prior simplified graph execution | |
| CN112767230A (zh) | Gpu图神经网络优化方法及装置 | |
| US12166878B2 (en) | System and method to improve efficiency in multiplication_ladder-based cryptographic operations | |
| CN110232665B (zh) | 最大池化方法、装置、计算机设备及存储介质 | |
| US5107452A (en) | Computation optimizer | |
| Tran-Dinh et al. | Fast inexact decomposition algorithms for large-scale separable convex optimization | |
| EP0314289B1 (en) | Multiple pixel generator | |
| Baranwal et al. | ReLAccS: A multilevel approach to accelerator design for reinforcement learning on FPGA-based systems | |
| KR20230099190A (ko) | 다차원 텐서의 주소 생성 장치 및 방법 | |
| US20200311545A1 (en) | Information processor, information processing method, and storage medium | |
| CN113823385B (zh) | 一种修改dicom图像的方法、装置、设备及介质 | |
| US11704277B2 (en) | Variation-aware qubit movement scheme for noise intermediate scale quantum era computers | |
| KR970004093B1 (ko) | 멤버쉽 함수 데이타 작성 방법 및 장치 그리고 적합도 연산 방법 및 장치 | |
| Amat et al. | Arabic fonts representation using sine cosine algorithm | |
| US20030195912A1 (en) | Arithmetic processing unit and semiconductor device | |
| US5202962A (en) | Graphic processor suitable for graphic data transfer and conversion processes | |
| Gao et al. | Geometric constraint solving with geometric transformation | |
| Yilmaz | A new smoothing function technique for solving minimax problems | |
| JP2000251081A (ja) | 内点判定方法、グラフィック描画装置およびプログラム記憶媒体 | |
| Frishman et al. | Uncluttering graph layouts using anisotropic diffusion and mass transport | |
| US6256656B1 (en) | Apparatus and method for extending computational precision of a computer system having a modular arithmetic processing unit | |
| US20070180010A1 (en) | System and method for iteratively eliminating common subexpressions in an arithmetic system |