JPH03105579A

JPH03105579A - 曲線生成装置

Info

Publication number: JPH03105579A
Application number: JP24364589A
Authority: JP
Inventors: Noriko Kudo; 工藤　法子; Satoshi Naoi; 聡直井; Toshiya Mima; 美間　俊哉
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1989-09-20
Filing date: 1989-09-20
Publication date: 1991-05-02
Anticipated expiration: 2014-02-03
Also published as: JP2854035B2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】［目次］概要産業上の利用分野従来の技術発明が解決しようとする課題課題を解決するための手段作用実施例発明の効果［概要］差分マトリクス法の利用で曲線を生成する方法に間し、高品質な曲線を高速に生成できる方法の提供を目的とし
、曲線を形成する各点のいずれかと対応したマトリクスを
微分演算して該マトリクスから所定の時間間隔だけ離れ
た次のマトリクスまでの増分量を算出し、算出ざれた増
分量と算出基準のマトリクスとの加算で次のマトリクス
を求める処理が前記曲線の始点と対応したマトリクスを
初期値として該曲線の終点と対応したマトリクスの得ら
れるまで繰り返される曲線生成方法において、前記初期
値のマトリクスに含まれた誤差が前記加算の繰り返しに
より前記終点までに累積する量を示し曲線形成点の総数
が変数となる関数を定め、該間数の値が許容値以下で最
大となる曲線形成点の総数を算出し、曲線の始点から終
点までの時間的な長さと選択された総数とから前記時間
間隔を求める、ことを特徴とする。

［産業上の利用分野］本発明は、差分マトリクス法の利用で曲線を生成する方
法に間する。

ＣＧ，ＣＡＤの分野においては品質の高い曲線を生成す
ることが必要とされる。

そして、高品質な曲線をソフトウェアで生成する場合に
はその生成速度が低いので、ハートウエアで曲線を生成
する方式がＣＧ装置やＣＡＤｌ！置で採用される。

［従来の技術］中点分割法を適用したハードウェアで曲線が生成される
場合には、全ての曲線をＢｅｚｉｅｒ曲線に変換するこ
とが必要となり、また、その変換を行うハードウエアの
構成が著しく複雑化し、さらに、中点座標を繰り返して
記憶するスタックの容量が膨大となる。

そこで、マトリクスの微分演算で算出された増分量をそ
のマトリクスに加算する処理が繰り返されることにより
曲線形成点を逐次求める差分マトノクス法が曲線生成用
のハードウエアに適用される。

この差分マトリクス法によれば、前記の変換を行うこと
なく一般多項式，Ｂｅｚｉｅｒ曲線，Ｓｐｌｉｎｅ曲線
などを高速に生成でき、しかも、スタック量が膨大とな
ることはない。

［発明が解決しようとする課題］しかしながら差分マトリクス法によれば、増分量の逐次
加算で曲線生成点のマトリクスが順に求められるので、
その加算の繰り返しにより誤差が次第に累積する。

本発明は上記の従来の事情に鑑みてなされたものであり
、その目的は、高品質な曲線を高速に生成できる方法を
提供することにある。

［課題を解決するための手段］上記目的を達成するために、本発明では第１図の方法が
とられている。

同図において、曲線１００を形成する各点ＰＯ・・・Ｐ
　ｉ、Ｐｉ　ｉｌｌ・・・ＰｎのいずれかＰｉと対応し
たマトリクスＭ　（　ｔ　ｉ　）を微分演算してこのマ
トリクスＭ（ｔｉ）から所定の時間間隔δだけ離れた次
のマトリクスＭ（ｔｒ＋１）までの増分１ｔａを算出し
、算出ざれた増分量ａと算出基準のマトリクスＭ　（　
ｔ　ｉ　）との加算で次の曲線形成点Ｐ　ｉ＋１と対応
したマトリクスＭ（ｔＩ＋１）を求める処理が曲線１０
０の始点ＰＯと対応したマトリクスＭ（ｔｏ）を初期値
として曲線１００の終点Ｐｎと対応したマトリクスＭ（
ｔｎ）の得られるまで繰り返される（差分マトリクス法
による曲線生成）．また、前記初期値のマトリクスＭ（ｔ０）に含まれた誤
差εが前記加算の繰り返しにより曲線１００の終点Ｐｎ
までに累積する量Ｅを示し曲線形成点Ｐ０・・・Ｐ　ｉ
、Ｐｉ　ｉ＋）・・・Ｐｎの総数ｎを変数とする間数ｆ
がステップ１１０て求められる。

そして、間数ｆの値Ｅが許容値Ｅ　ｍａｘ以下で最大と
なる曲線形成点ＰＯ・・・Ｐ　ｉ．Ｐ　ｉ＋！・・・Ｐ
ｎの総Ｆ［　ｎ　ｍａｘがステップ１２０で選択される
。

さらに、曲線１００の始点ＰＯから終点Ｐｎまでの時間
的な長さｔｎ−ｔｏと選択されｋ総数ｎ　ｍａｙとから
前記の時間間隔δｍｉｎがステップ１３０で求められる
。

［作用コ本発明では、各曲線生成点ＰＯ・・・Ｐｉ、Ｐｉｉｌ１
・・・Ｐｎを各々示すマトリクスＭ（ｔｏ）・・・Ｍ（
ｔｉ）．　　Ｍ（ｔｉ＋１）・・・Ｍ（ｔ．ｎ）が差分
マトリクス法で順に求められる。

その差分マトリクス演算で使用される時間間隔δＩＩＩ
ｉｎは曲線１００の始点ＰＯから終点Ｐｎまでの時間的
な長さｔ　ｎ　−　ｔ　Ｏと曲線形成点ＰＯ・・・Ｐ＋
、Ｐｉ書＋１・・・Ｐｎの総数ｎ　ｗａｘから求められ
る（ステップ１３０）。

さらに、時間間隔δｍｉｎを求めるために使用される曲
線形成点ＰＯ・・・Ｐ　ｉ、Ｐｉ　ｉ＋１・・・Ｐｎの
総数ｎ　ｍａｘは閏数ｆの解を選択することにより得ら
れる（ステップ１２０）。

この閏数ｆは曲線形成点ＰＯ・・・Ｐｉ、Ｐｉｉ＋１・
・・Ｐｎの総数ｎを変数としており、初朋誤差εが与え
られることで最終的な累積誤差Ｅが得られ、関数値Ｅが
許容誤差Ｅ　ｍａｘ以下となる条件下で変数ｎが最大と
なる解として総数ｎ　＋＋＋ａｘが選択される。

そして、間数ｆはマトリクスＭ（　ｔ　０）．　　Ｍ（
ｔｉ），Ｍ（ｔｉ＋Ｉ）・・・Ｍ（ｔｎ）と同様な形で
表現できる。

したがって、最大総数ｎ　ｏ＋ａｘを差分マトリクス法
の利用で選択でき、このため、曲線形成点ＰＯ・・・Ｐ
　ｉ、Ｐｉ　ｉｌｌ・・・Ｐｎとともに時間間隔δｍｉ
ｎをハートウエアで高速に求めることが可能となる。

さらに、最終的な累積誤差Ｅが許容１ａＥｍａｘ以下と
なる最小の時間間隔δｗｉｎが求められるので、曲線１
００を正確に表現することも可能となる。

［実施例］以下、図面に基づいて本発明に係る方法の好適な実施例
を説明する。

第２図では本発明が適用された曲線発生器の構成が説明
ざれており、この曲線発生器はデータ入力部２０，累積
誤差算出部２２，差分マトリクス算出部２４，間隔決定
部２６．増分値加算部２８，曲線出力部３０で構成され
ている。

本実施例では三次元曲線１００（例えば、ユニフォーム
Ｂスプライン関数）が生成の対象とされており、一定の
時間的な長さｔＯ〜ｔｎの区間における曲線制御点Ｑ　
ＩＩ　　Ｑ　Ｉ＋ｌ，　　Ｑ　＋　”２＋　　Ｑ　＋　
＋３のデータがデータ人力部２０から取り込まれる。

それら制御点Ｑｉ．　　Ｑ　ｉ＋Ｉ．　　Ｑ　ｉ＋２，
　　Ｑ　ｉ＋３及び時間間隔δて初間値のマトリクスＭ
　（　ｔｏ）　＝　［Ａ．Ｂ，　Ｃ．　ＤＩをＡ　　　＝　　　（１／６）Ｑｉ＋（２／３）Ｑｉ＋１
＋（１／６）Ｑｉ＋２Ｂ　　　＝　　　｛（−１／６）　　δ２＋　（１／２
）δ一１／２｝　　Ｑｉ＋｛（１／２）　　δ２−６｝Ｑｉ＋１＋｛（−１／２
）　　δ２＋　（１／２）８十１／２）Ｑ督＋２＋（１／６）　　δ２Ｑｉ＋３Ｃ＝（一δ＋１）Ｑ＋　（３δ−２）Ｑｉ＋１＋　（一３８＋１）Ｑｉ＋２＋δＱ１＋３Ｄ　　＝　　−Ｑｉ＋３Ｑｉ＋Ｉ−３Ｑｉ＋２＋Ｑｉ＋
３・・・第（１）式により表現でき、このマトリクスＭ　（　１０）　＝　
［Ａ，Ｂ．　　Ｃ，　　Ｄ］の算出は差分マトリクス算
出部２４で行われる。

第３図では差分マトリクス算出部２４と増分値加算部２
日の作用が説明されており、マトリクスＭ　（　ｔｏ）
　＝　［Ａ．　　Ｂ，　　Ｃ．　　Ｄ］　＋．ｉ曲線１
０（１）始点ｐｏと対応している。

そして、初期値のマトリクスＭ　（ｔ０）　＝　［Ａ．
Ｂ．　　Ｃ，　　Ｄ］は増分値加算部２日に与えられ、
始点ＰＯを示すその第１要素Ａ＝Ｓ（ｔ０）は増分値加
算部２８から曲線出力部３０に与えられて外部へ出力さ
れる。

また、増分加算部２８では現在のマトリクスＭ（ｔ０）
の第２要素Ｂ＝△Ｓ　（　ｔ　０）が一次微分され、第
３要素Ｃ＝Δ２ｓ（ｔｏ）が二次微分され、さらに第４
要素Ｄ＝Δ３Ｓ（ｔｏ）が三次微分される。

その微分演算で増分１ｔａを示すマトリクス［Ｂ．Ｃ．
Ｄ．Ｏ］＝［ΔＳ　（　ｔ　０），　　Δ２　Ｓ　（　
ｔ　０），　　Δ３Ｓ（　ｔ　０）］が算出され、増分
値加算部２８では増分量ａのマトリクス［Ｂ，　　Ｃ，
　　Ｄ，　　Ｏ］がそれまでのマトリクスＭ　（１０）
　＝　［Ａ．　　Ｂ．　　Ｃ．　　Ｄ］に加算ざれる。

これにより得られたマトリクスＭ　（ｔ１）　＝　［Ａ
＋Ｂ．　　Ｂ＋Ｃ．　　Ｃ＋Ｄ，　　Ｄ］の第１要素Ａ
＋Ｂが次の曲線形成点Ｐ１を示すデータとして曲線出力
部３０へ送出される。

さらに、新たなマトリクスＭ　（　ｔ　Ｉ）　＝　［Ａ
＋Ｂ，Ｂ＋Ｃ，Ｃ＋Ｄ，ＤコへそれまでのマトリクスＭ
（ｔｏ）　＝　［Ａ，　　Ｂ．　　Ｃ．　　Ｄ］が更新
される。

以上の処理は同様にして繰り返され、その結果、曲線形
成点ＰＯ，　　ＰＩ，　　Ｐ２・・・Ｐｎを各々示すデ
ータＡ，Ａ＋Ｂ，Ａ＋２Ｂ＋Ｃ・・・Ａ＋ｎＢ＋ｎ　（
ｎ−１）　Ｃ／２＋ｎ　（ｎ−１）　　（ｎ−２）　Ｄ
／６が外部へ順に出力される。

このときに求められるマトリクスＭ（ｔ０）＝［Ａ．　
　Ｂ．　　Ｃ．　　Ｄコ．　　Ｍ　　（ｔ１）＝　　［
Ａ＋Ｂ，　　Ｂ＋Ｃ，Ｃ＋Ｄ．Ｄｌ．Ｍ　（ｔ２）＝　
［Ａ＋２Ｂ＋Ｃ．Ｂ＋２Ｃ＋Ｄ，Ｃ＋２Ｄ，Ｄ］　・・
・Ｍ（ｔｎ）＝［Ａ＋ｎＢ＋ｎ　（ｎ−１）Ｃ／２＋ｎ
　（ｎ−１）（ｎ−２）Ｄ／６．Ｂ＋ｎＣ十ｎ　（ｎ−
１）Ｄ／２，Ｃ＋ｎＤ．Ｄ］の各要素Ｓ　（　ｔ　ｉ＋
１）．　　ΔＳ　（　ｔ　ｉ＋１）＋Δ２Ｓ　（　ｔ　
ＩＨ），　　Δ３Ｓ（ｔｉ＋１）は、次の第（２）式で
表現される。

Ｓ（ｔ　ｉ＋１）＝Ｓ　　（　ｔ　ｉ）　　＋ΔＳ（ｔ
ｉ）ΔＳ（ｔｉ＋１）＝ΔＳ（ｔｉ）　　＋Δ２Ｓ（ｔ
ｉ）Δ２Ｓ　（　ｔ　ｉ＋１）＝Δ２Ｓ（ｔｉ）　　＋
Δ３Ｓ（ｔｉ）Δ３Ｓ　（　ｔ　ｉ＋１）＝Δ３Ｓ（ｔ
ｉ）・・・第（２）式それらのマトリクスＭ（ｔ０），Ｍ（ｔ１），Ｍ（ｔ２
）・・・Ｍ（ｕｎ）が求められる時間間隔δは δ＝　　ｔ　ｉ＋ｌ　−　　ｔ　ｉ・・・第（３）式て示され、微分演算及び増分量加算の回数ｎは夕人力部
２０から予め取り込まれる。

曲線１００の終点Ｐｎで最終的に累積する誤差Ｅは、第
３図におけるマトリクスＭ（ｔｎ）の第１要素Ｓ（ｔｎ
）から理解されるように、Ｅ＝ｎ　　（ｎ−１）　　（ｎ−２）　　Ｅ／６・・・
第（５）式て示される。

その第（５）式は、曲線形成点Ｐ　ｉ＋１の間隔δが最
も密となる最大の形成点総数ｎ　ｍａｘを用いてｎ＝（
ｔｎ〜ｔ０）／δ ・・・第（４）式て示される。

ここで、差分マトリクスの演算に際し、３次微分増分量
Δ３Ｓ（ｔｉ）の初朋値Ｄに含まれる誤差εと最終的に
累積する誤差Ｅの許容値ＥｒｎａｘがデーＥ＝ｎｍａｘ
（ｎｍａｘ−１）　　（ｎｍａｘ−２）　　ｃ／６・・・第（６）式と表現でき、また、このときの時間間隔δｍｉｎは δｍｉｎ＝　　（　ｔ　ｎ−　ｔ　０）／　ｎ　ｍａｘ
・・・第（７）式て示される。

その累積誤差Ｅが許容値Ｅ　ｍａｘ以上となる条件は、
ｎｍａｘ（ｎｉａｘ−１）　　（ｎｍａｘ−２）＞　６
　Ｅ　ＩＩＩａｘ／　ｔ・・・第（８）式て示され、この第（８）式は累積算出部２２て生成され
る。

そして、差分マトリクス算出部２４及び増分加算部２８
により第（８）式における左辺の値が差分マトリクス法
で求められ、第（８）式を満たす最大の形成点総数ｎ　
ｍａｘが選択ざれる。

すなわち、最大の形成点総数ｎ　ｗａｘが０以上の整数
であるので、その総数ｎ　ｍａｘにＯ．　　１．　　２
・・・を第（８）式に代入して左辺の値を求める処理が
繰り返される。

それら左辺の値は累！１誤差算出部２２に増分値加算部
２８から逐次与えられ、第（８）式を満たす総数ｎ　ｍ
ａｙが選択ざれる。

さらに、累積誤差算出部２２からこの総数ｎｍａＸが間
隔決定部２Ｇに与えられ、間隔決定部２６ではｎ　ｍａｘ＝　ｎ　ｎａｘ−　　１・・・第（９）式に従って最大の形成点総数ｎ　ｍａＸが定められる。

以上のように本実施例においては、第（８）式の左辺が
曲線１００と同様な３次曲線式でこの式を満たす解がＯ
以上の整数であることに着目して最大総数ｎ　ｍａｘが
差分マトリクス法を用いてハートウエアで求められる。

したがって、ニュートン法なとのように解の収束性や算
出所要時間の点て問題が生ずることはなく、第（８）式
の解が高速に算出される。

しかも、差分マトリクス法による演算が整数演算である
ので、誤差が皆無となり、このｋめ、正確な解を求める
ことが可能となる。

なお、増分値加算部２日ではＳ（ｎｍａｘ）＝ｎｍａｘ（ｎｍａｘ−１）　　Ｃｎｍａｘ−２）・・
・第（】０）式が対象の曲線式として取り扱われる。

また、その際に第３図の値Ａ．．　　Ｂ，　　Ｃ，　　
Ｄで示されるマトリクス要素は、Ｓ　　（ｎｍａｘｉ＋Ｉ）　　＝Ｓ　　（ｎｍａｘｉ）
・・・第（１１）式 △Ｓ　　（　ｎ　ｍａχｉ＋Ｉ）＝ΔＳ　（ｎｍａｘｉ）十Δ２Ｓ　（ｎｍａｘｉ）・・
・第（】２）式 Δ２Ｓ　　（　ｎ　ｍａｘｉ＋Ｉ）＝Δ２Ｓ　（ｎｍａｙｉ）＋Δ３Ｓ　（ｎｍａＸｉ）・
・・第（１３）式 Δ’Ｓ　（ｎｍａｘｉ＋１）　＝Δ３Ｓ　（ｎｍａｘｉ
）・・・第（１４）式で各々示され、第（１ｏ）式から値Ａ．　　Ｂ，　　Ｃ
，Ｄの相当ｔｌＩＩＡｎ，　　Ｂｎ，　　Ｃｎ．　　Ｄ
ｎが次の第（ｌ５）式から求められる。

Ａｎ　＝Ｂ　ｎ　＝Ｃ　ｎ　＝０Ｄｎ＝６・・・第（１５）式このようにして間隔決定部２６で叢小の時間間隔δｍｉ
ｎが求められると、第３図の値Ａ．　　Ｂ，　　Ｃ，Ｄ
が完全に定まり、以下は第（２）式に１だって差分マト
リクスの演算がｎ　ｍａｘ回繰り返えされる。

ただし、実際にはシフト数γを用いて次の第（】６）式
で示される演算が行われ、これにより演算精度が高めら
れろ。

Ｓ（ｔｒ＋１）＝Ｓ　（ｔｉ）　十ｒ木（１／ｒ）　Δｓ　（ｔｉ）（
１／γ）ΔＳ　　（　ｔ　ｉ＋１）＝　（１／γ）ΔＳ（ｔｉ）　　＋γ本　（ｌ／γ２）
Δ２Ｓ（ｔｉ）（１／γ２）Δ２Ｓ　　（　ｔ　ｉ＋Ｉ）＝（ｌ／γ２
）Δ２Ｓ（ｔｉ）＋γ本（１／γ３）△３Ｓ（ｔｉ）（１／γ３）Δ３Ｓ　　（　ｔ　ｉ＋１）＝　（１／γ
３）Δ３Ｓ（ｔｉ）・・・第（１６）式て求められるので、高品質な曲線１００を高速に生成で
きる。

このため、ＣＧ．ＣＡＤの処理が行われる装置を著しく
高性能化することが可能となる。

なお、初期誤差ε，誤差許容値ＥＩＩｌａｘが大きな場
合には、時間間隔δｍａｘもこれに応じて拡大するので
、曲線１００の生成速度が極めて高くなる。

したがって、初期誤差ε及び誤差許容値Ｅ　ｗａｘの指
定により、曲線１００の生成速度と生成精度のいずれを
優先すべきかを用途に応じて選択できる。

また、曲線形成点Ｐ１の間隔が１ドットとなる場合には
、それらの間を結ぶ直線は直線発生器で生成できる。

以上説明したように本実施例によれば、初期誤差εと誤
差許容値Ｅ　ｍａｘが与えられることにより最終的な累
積誤差Ｅが誤差許容値Ｅ　ｍａｘ以下となるので、差分
マトリクス法で高品質な曲線１００を生成できる。

また、最小の時間間隔δＩｌｉｎも差分マトリクス法［
発明の効果］以上説明したように本発明によれば、最終的な累狽該差
が誤差許容値以下となる時間間隔を用いて差分マトリク
スの演算が行われ、その時間間隔も差分マトリクス法で
算出できるので、高品質な曲線を高速に生成するハード
ウェアを構成することが可能となる。

【図面の簡単な説明】

第１図は発明の原理説明図、第２図は実施例の構成説明図、第３図は差分マトリクス算出部及び増分値加算部の作用
説明図、てある。２　０　◆ ２２　◆ ２４　・２６　・２　８　● ３　０　● データ人力部累積誤差算出部差分マトリクス算出部間隔決定部増分値加算部曲線出力部実施例の構成説明図第２図

Claims

【特許請求の範囲】曲線（１００）を形成する各点（Ｐ０・・・Ｐｉ、Ｐｉ
＋１・・・Ｐｎ）のいずれか（Ｐｉ）と対応したマトリ
クス（Ｍ（ｔｉ））を微分演算して該マトリクス（Ｍ（
ｔｉ））から所定の時間間隔（δ）だけ離れた次のマト
リクス（Ｍ（ｔｉ））までの増分量（ａ）を算出し、算
出された増分量（ａ）と算出基準のマトリクス（Ｍ（ｔ
＋ｉ））との加算で次の曲線形成点（Ｐｉ＋１）と対応
したマトリクス（Ｍ（ｔｉ＋１））を求める処理が前記
曲線（１００）の始点（Ｐ０）と対応したマトリクス（
Ｍ（ｔ０））を初期値として該曲線（１００）の終点（
Ｐｎ）と対応したマトリクス（Ｍ（ｔｎ））の得られる
まで繰り返される曲線生成方法において、前記初期値のマトリクス（Ｍ（ｔ０））に含まれた誤差
（ε）が前記加算の繰り返しにより前記終点（Ｐｎ）ま
でに蓄積する量（Ｅ）を示し曲線形成点（Ｐ０・・・Ｐ
ｉ、Ｐｉ＋１・・・Ｐｎ）の総数（ｎ）が変数となる関
数（ｆ）を定め（ステップ１１０）、該関数（ｆ）の値
（Ｅ）が許容値（Ｅ＿ｍ＿ａ＿ｘ）以下のときに最大と
なる曲線形成点（Ｐ０・・・Ｐｉ、Ｐｉ＋１・・・Ｐｎ
）の総数（ｎ＿ｍ＿ａ＿ｘ）を選択し（ステップ１２０
）、曲線（１００）の始点（Ｐ０）から終点（Ｐｎ）までの
時間的な長さ（ｔｎ〜ｔ０）と選択された総数（ｎ＿ｍ
＿ａ＿ｘ）とから前記時間間隔（δ＿ｍ＿ｉ＿ｎ）を求
める（ステップ１３０）、ことを特徴とする曲線生成方法。