幾何的 Newton 法の同次化に関する研究 A study of homogenized geometric Newton-Raphson method

全文

(1)幾何的 Newton 法の同次化に関する研究 A study of homogenized geometric Newton-Raphson method. 2006 年 2 月早稲田大学大学院理工学研究科機械工学専攻 CAD 工学専攻木村雅紀. -. i. -.

(2) 目. 1. 序 1.1.. 次. 章_______________________________________________________________ 1 研究背景 ______________________________________________________________ 1. 1.2. 干渉計算の方法と問題点 _________________________________________________ 1.2.1. 代数的解法________________________________________________________ 1.2.2. Bezier 分割法 ______________________________________________________ 1.2.3. 区間分割法________________________________________________________ 1.2.4. Sturm の定理_______________________________________________________ 1.2.5. 幾何的 Newton 法___________________________________________________. 1 2 2 2 3 3. 1.3.. 頑健性と局所一意性_____________________________________________________ 5. 1.4.. 研究目的 ______________________________________________________________ 5. 1.5.. 論文の構成 ____________________________________________________________ 5. 2. 問題提起 __________________________________________________________ 9 2.1.. はじめに ______________________________________________________________ 9. 2.2. 有理曲線 ______________________________________________________________ 9 2.2.1. 有理曲線の定義 ____________________________________________________ 9 2.2.2. 有理 Bezier 曲線 ____________________________________________________ 9 2.3.. 有理曲線の特徴________________________________________________________ 10. 2.4.. 有理曲線の問題点______________________________________________________ 11. 2.5.. ユークリッド幾何的 Newton 法（CE法）___________________________________ 12. 2.6.. 実行例 _____________________________________________________________ 13. 2.7.. まとめ _____________________________________________________________ 15. 3. 発散問題への対応 __________________________________________________ 16 3.1.. はじめに _____________________________________________________________ 16. 3.2. 同次曲線 _____________________________________________________________ 16 3.2.1. 同次曲線の定義 ___________________________________________________ 16 3.2.2. 同次 Bezier 曲線 ___________________________________________________ 17 3.3.. 同次曲線の利点________________________________________________________ 17. 3.4.. 同次幾何的 Newton法（SH法） __________________________________________ 18. 3.5.. 実行例 _____________________________________________________________ 19. 3.6. 考 3.6.1. 3.6.2. 3.6.3. 3.7.. 察 _____________________________________________________________ CE 法の等価関数 __________________________________________________ SH 法の等価関数 __________________________________________________ 頑健性と等価関数 _________________________________________________. 21 21 21 23. まとめ _____________________________________________________________ 24. 4. 局所一意性問題への対応 _________________________________________ 25 4.1.. はじめに _____________________________________________________________ 25. 4.2.. 同次パラメータ________________________________________________________ 25. 4.3.. 同次パラメータ同次曲線 ________________________________________________ 26. -. ii. -.

(3) 4.3.1. 4.3.2. 4.3.3.. 同次パラメータ同次曲線の定義 ______________________________________ 26 同次パラメータ同次 Bezier 曲線 ______________________________________ 26 同次パラメータ同次 Bezier 曲線の偏微分導関数 _________________________ 26. 4.4. 同次パラメータ同次幾何的 Newton法（DH法）_____________________________ 27 4.4.1. DH 法の等価関数__________________________________________________ 27 4.4.2. 同次パラメータ制御 _______________________________________________ 29 4.5.. 実行例 _____________________________________________________________ 30. 4.6. 考 4.6.1. 4.6.2. 4.6.3. 4.6.4. 4.6.5. 4.6.6. 4.6.7. 4.7.. 察 _____________________________________________________________ 局所一意性の向上 _________________________________________________ 高次の問題に対する実行例__________________________________________ 適切な同次パラメータ制御__________________________________________ 増分値の大きさ ___________________________________________________ 同次パラメータ空間における制御式の比較_____________________________ 頑健性について ___________________________________________________ 演算回数の比較 ___________________________________________________. 32 32 32 37 37 39 40 40. まとめ _____________________________________________________________ 42. 5. 振動問題への対応 __________________________________________________ 43 5.1.. はじめに _____________________________________________________________ 43. 5.2.. 振動現象の発見________________________________________________________ 43. 5.3.. 振動現象と複素解______________________________________________________ 45. 5.4. 複素同次パラメータ同次曲線_____________________________________________ 5.4.1. 複素同次パラメータ _______________________________________________ 5.4.2. 複素同次パラメータ同次曲線の定義___________________________________ 5.4.3. 複素同次パラメータ同次 Bezier 曲線の定義_____________________________. 46 46 46 47. 5.5. 複素同次パラメータ同次幾何的 Newton法（DHC 法）________________________ 47 5.5.1. 同次パラメータ制御 _______________________________________________ 48 5.6.. 実行例 _____________________________________________________________ 49. 5.7. 考 5.7.1. 5.7.2. 5.7.3. 5.7.4. 5.7.5. 5.7.6. 5.8.. 察 _____________________________________________________________ 非有理式化による頑健性の向上 ______________________________________ 初期点の虚数部の与え方____________________________________________ 他の実行例_______________________________________________________ 同次化による利点 _________________________________________________ 増分値の大きさ ___________________________________________________ 演算回数の比較 ___________________________________________________. 50 50 50 52 55 57 58. まとめ _____________________________________________________________ 61. 6. 有理曲面を対象とする幾何的 Newton法の頑健性 __________ 62 6.1.. はじめに _____________________________________________________________ 62. 6.2. 従来の幾何的 Newton 法（CE法） ________________________________________ 6.2.1. 有理曲面_________________________________________________________ 6.2.2. CE 法 ___________________________________________________________ 6.2.3. CE 法の等価関数 __________________________________________________. 62 62 63 63. 6.3. 同次幾何的 Newton法（SH法） __________________________________________ 6.3.1. 同次曲面_________________________________________________________ 6.3.2. SH 法 ___________________________________________________________ 6.3.3. SH 法の等価関数 __________________________________________________. 64 64 64 65. - iii -.

(4) 6.4.. 実行例 _____________________________________________________________ 65. 6.5. 考 6.5.1. 6.5.2. 6.5.3. 6.5.4. 6.6.. 察 _____________________________________________________________ CE 法における等価関数の断面_______________________________________ SH 法における等価関数の断面_______________________________________ 等価関数の断面形状 _______________________________________________ 条件を変えた実験 _________________________________________________. 67 67 68 68 70. まとめ _______________________________________________________________ 76. 7. 結. 論______________________________________________________________ 77. 7.1.. 総. 括 _____________________________________________________________ 77. 7.2.. 本論文の新規性________________________________________________________ 78. 7.3.. 今後の課題 ___________________________________________________________ 78. - iv -.

(5) 1. 序. 章. 1.1. 研究背景 CAD/CAM システムは設計・生産活動などの分野で広く普及し，一般的なものとなった．CAD の効率的な利用は製品開発の能率を高めている．CAD で用いた 3 次元データを設計から生産，さらには解析にまで利用するという傾向が広がっており，品質の高い製品を短期間で生産することを可能にしている．しかし，CAD にはまだ改善すべき問題が多く残されている．それらの問題の重要な要因の 1 つに除算の問題がある．分母が 0 または非常に小さな値となる場合の除算は危険な処理であり，アルゴリズムが破綻するなど，システム全体を不安定にしてしまう．従来の方法では例外処理を行ってこの問題を回避している．しかし，例外処理を多く含む処理体系はプログラムが煩雑になり，統一性がない上にサイズが大きくなるため，構築・修正が困難となる．また，コンピュータの演算では有効桁数が有限であるため除算の厳密な解を得ることができない．有効桁数を増加することによって誤差は縮小するが，厳密な解を要求する場面では決定的な解決法ではない．これに対し，除算を用いない処理方法として同次処理が提案されている [Yamaguchi1996][Yamaguchi2002]．同次処理の演算では除算を行う必要がない．分母が 0 または非常に小さな値となる場合も，演算は常に頑健である．また，同次処理では除算による誤差の蓄積も起こらない．さらに，同次処理の重要な性質として双対性があり，幾つかの処理が同一のアルゴリズムによって記述でき，アルゴリズムの共用が可能となるため，同次処理はシステムのスリム化・統一化に有効である．このように，同次処理を導入することによって，頑健で統一的な CAD システムを実現することができる．本論文が論じるのは有理曲線・曲面を対象とした干渉処理についての研究である．本論文は，頑健ではない従来の方法に同次化の手法を施し，演算を頑健化する方法について述べる． 1.2. 干渉計算の方法と問題点形状処理工学において干渉処理は重要な問題である．干渉処理演算の方法としては，代数的に解を求める方法，幾何的な性質を利用して解を求める方法，幾何的 Newton(-Raphson)法を用いる方法などがある[Toriya1991]．それぞれの方法は得意とする分野があるため，対象となる曲線・曲面の性質によってこれらを使い分ける必要がある．例えば，代数的に求められる解は厳密な値となるが，対象とできる次数には限度がある．幾何的 Newton 法では次数に関係なく，精度を指定して近似解を求めることができる．. -. 1. -.

(6) 以下に Bezier 曲線を対象とした干渉処理の方法を幾つか挙げる．曲面の干渉処理は曲線を対象とした方法を応用すればよい． 1.2.1. 代数的解法パラメトリック表現された曲線・曲面を陰関数表現された式に代入することによって，交点のパラメータを求める方法である．例えば，直線と曲線の交点の場合，x，y の陰関数表現の直線式に，パラメトリック表現された曲線式を代入し，パラメータについて解けばよい． 5 次以上の代数方程式は解くことができないため，高次の曲線を扱った干渉処理には適用できない． 1.2.2. Bezier 分割法 Bezier分割法は de Casteljauの分割アルゴリズムを用いて Bezier 曲線を分割して交点を求める方法である．図1は de Casteljau のアルゴリズムによって 3 次 Bezier 曲線が t において分割される様子を表す．凸包領域の干渉する部分を調べ，直線に近似できるまで曲線を逐次２分割していき，交点を求める．Bezier 分割法は収束が遅い．. Fig. 1 De Casteljau’s algorism.. 1.2.3. 区間分割法区間分割法[Sederberg1994]は接線の方向が x 軸，y 軸と平行になる点で Bezier 曲線を分割する．図2に示すように，凸包は曲線を含む x 軸，y 軸と平行な辺で構成される長方形であり，分割された各部分曲線はどこで分割しても凸包が長方形で得られる．この性質を利用し，凸包が干渉する部分についてさらに分割を行い，曲線が直線近似できるまで繰り返して交点を求める．区間分割法は Bezier 分割法より速いが能率的ではない．. -. 2. -.

(7) Fig. 2 The interval subdivision method.. 1.2.4. Sturm の定理 Sturm の定理を用いると，代数方程式の区間内に存在する解の個数を正確に判定することができる[Togawa1971]．これを，交点算出演算に応用すれば，Bezier 分割法などとの組み合わせで解の存在する微小区間を求めることができる．組み合わせる収束法に依存するが，一般に収束は遅い． 1.2.5. 幾何的 Newton 法図3に示すように，Taylor 展開による 1 次近似を行い，曲線を直線に近似して交点の近似解を求めるという操作を繰り返し，真の解に収束させる方法である．一般的な方程式の解法である Newton(-Raphson)法の収束プロセスによく似ている．幾何的 Newton 法は，対象とする曲線・曲面の次数や種類に依存せず，高速に解を求めることができる，一般的な交点算出方法である．本論文は幾何的 Newton 法の同次化について述べる．. Fig. 3 Geometric Newton-Raphson method.. 従来の幾何的 Newton 法を有理曲線・曲面を対象とした交点算出に適用すると，演算途中でアルゴリズムが破綻する場合が多い．また，予想不可能な解に収束してしまうという問題もある． Newton 法の改良に関する研究は過去に行われており，それらを幾何的 Newton法に適用するのは簡単である．以下に Newton 法や幾何的 Newton 法の改良に関する研究を幾つか挙げる．. -. 3. -.

(8) (A) 増分値の制御 Newton 法によって f (t ) = 0 となる t を求める場合の反復計算式は， f (t i ) t i+1 = t i − (i = 0,1,2,L) f ′(ti ). (1). である．Newton法では，増分値− f (t i ) f ′(t i ) の分母 f ′(t i ) が微小値をとる場合に増分値が非常に大きな値となる．そのまま演算を続けると発散を起こす危険がある．また，予想不可能な解に収束する場合があるため問題である．これを避けるために，増分値に適切な数値を乗じて（例えば，1/2 倍するなど）増分値の大きさを制御し，演算を頑健化させる方法がある．また，ある値より大きい場合に増分値を小さくするというように，条件によって場合分けする方法もある．これらの方法では，乗じる数値を適切に選択する事が必要である．しかし，そのための合理的な決定法が与えられているわけではない．また，場合によっては増分値が小さくなりすぎて収束が遅くなってしまう． (B) 擬似 Newton 法従来のNewton法の変形である2つの擬似Newton法を扱った研究もある[Ozban2004]．擬似 Newton 法の反復計算式はそれぞれ， (1) Arithmetic Mean Newton’s Method (AN 法) f (t i ) f (t i ) t i+1 = t i − ただし， z i+1 = t i − (2)  f ′(t i ) + f ′( z i+1 )  f ′(t i )   2   (2) Midpoint Newton’s Method (MN 法) f (t i ) f (t i ) ただし， z i+1 = t i − t i+1 = t i −  t + zi +1  f ′(t i ) f ′ i   2 . (3). である．これらの疑似 Newton法を，有理曲線と直線との交点算出を行う幾何的 Newton法に適用すると，どちらの方法もアルゴリズムが途中で破綻する場合が多い．また，予想しない解に収束する場合もある． (C) 接触円を用いた幾何的 Newton 法初期点において，接線による近似の代わりに接触円による近似を行うという方法も提案されている[Kallay2001]．この方法は接触円を求めるときに 2 次導関数を要求するため，Taylor 展開の 2 次近似式を用いる Bailey 法に似ている．2 次導関数を求める計算量はとても多いため，簡潔性のためには 1 次近似までにしておく方がよい．また，有理曲線・曲面を対象とした干渉処理において，アルゴリズムが途中で破綻. -. 4. -.

(9) する問題を解決していない．このように，Newton 法や幾何的 Newton法に関する過去の研究には，収束性に関するものが多く，有理曲線･曲面を対象とした場合にアルゴリズムが途中で破綻する問題や，予想不可能な解に収束するという問題に対して解決策を与えるものではない．有理曲線･曲面を対象とした場合の有理式特有の頑健性問題に言及した論文は著者の知る限り見当たらない． 1.3. 頑健性と局所一意性本論文においては，幾何的 Newton 法の破綻問題と収束問題を議論するにあたり，以下の用語を定義し，用いる． l 頑健性（robustness）とは，演算が途中で破綻することなく終了する性質である． l 局所一意性とは初期点と収束解との間に連続的な関係が得られる性質であり，初期点から離れた予想外の解に収束せず，予測されうる解に収束することを意味する． 1.4. 研究目的有理曲線・曲面を対象とする幾何的 Newton 法のアルゴリズムには，頑健性と局所一意性に問題がある．より具体的に，有理曲線・曲面を対象とした幾何的 Newton 法の問題を以下に整理する． 1. 多くの初期パラメータから発散現象を生じるという発散問題． 2. 収束解と初期パラメータとの関係が不連続的であり，局所一意性が悪いという問題． 3. 複素解が存在する場合に振動現象が起こるという振動問題．本論文は幾何的 Newton 法に同次処理を導入することによって，これらの問題を解決または改善する手法を提案することを研究目的とする． 1.5. 論文の構成本論文は7章より成る．各章の概要は以下の通りである．第１章研究背景・研究目的幾何的 Newton 法には，頑健性と局所一意性が要求される．頑健性とは，演算が途中で破綻することなく終了する性質である．また局所一意性とは初期パラメータと収束解との関係が連続的となる性質であり，予測され得る解に収束するために必要な性質である．有理曲線・曲面を対象とする幾何的 Newton 法のアルゴリズムには，頑健性と局所一意性に問題がある．幾何的 Newton 法に関連する過去の研究は収束性の改善につい. -. 5. -.

(10) て述べており，有理曲線･曲面を対象とした場合の有理式特有の頑健性に対する問題に言及したものは見当たらない．本論文は幾何的 Newton 法に同次処理を導入することによって，発散問題，振動問題，局所一意性問題を解決または改善する手法を提案する．第２章問題提起従来法であるユークリッド幾何的 Newton法（CE 法）は，ユークリッド空間において定義される有理曲線を直接的に対象とする幾何的 Newton法である．CE 法は発散現象を生じやすい．実際に CE 法を用いて，有理曲線と直線との交点算出を行うと，多くの初期パラメータにおいてパラメータ値が発散する．有理曲線を対象とした演算処理は，有理式表現に起因する問題を持つからである．また，CE 法は初期パラメータと収束解との関係が不連続的であり，局所一意性にも問題がある．第３章発散問題への対応 CE 法の発散問題を解決するため，座標を同次化した同次幾何的 Newton法（SH 法）を提案する．SH 法は同次ベクトル空間において定義される同次曲線を対象とする， CE 法と等価な幾何的 Newton法である．同次曲線は有理曲線の分母をもう 1 つのベクトル成分とすることにより非有理式表現された曲線であり，有理式表現に起因する問題が同次曲線には存在しない．同次曲線を対象とする SH 法は有理式表現に起因する発散現象が起きず，頑健である．SH 法では，すべての初期パラメータに対し演算を破綻なく行うことができる．交点を求める幾何的処理と等価な関数を等価関数という．発散問題は，幾何的 Newton 法の等価関数の形状に依存しており，等価関数が横方向の漸近線を持つ場合に発散現象が現れる．有理曲線を対象とする場合，その CE 法等価関数には必ず漸近線が存在する．いったんパラメータが漸近線近傍の値をとると，以後は微分値が一方的に減小し，増分値は加速度的に増大し，遂には発散現象を生じる．これに対し，SH 法では非有理曲線を対象とすることになるので，SH 法の等価関数には漸近線が存在せず，演算は頑健である．第４章局所一意性問題への対応 SH 法では頑健性は向上したが，局所一意性は不十分である．局所一意性を向上させるために同次パラメータ同次幾何的 Newton 法（DH 法）を提案する． DH 法では，座標だけでなくパラメータも同次化することにより，幾何的 Newton 法のパラメータ増分値を制御できる新しい自由度が得られる．本論文では，同次パラ. -. 6. -.

(11) メータ成分の二乗和を最小化する制御法を提案した．この制御法では，演算回数を従来法と変えることなく増分値を従来法より小さく制御することができる．DH 法では，発散現象が現れないだけでなく，初期パラメータと収束解との関係が連続的となり，局所一意性が飛躍的に向上する．第５章振動問題への対応複素解の存在する交点算出問題においては，振動現象が発生する場合がある．この問題を解決するために，同次パラメータを複素数化した複素同次パラメータ同次幾何的 Newton 法（DHC 法）を提案する． DHC 法では，座標が同次化されているので発散性はなく，演算は頑健である．また，パラメータも同次化され，複素同次パラメータ成分の二乗和を最小に制御する．これにより，DHC 法は優れた局所一意性も実現している．さらに，初期パラメータ近傍に複素解が存在する場合には，振動現象なしに複素解に収束させることができる． DHC 法は発散的および振動問題の双方を解決するとともに，優れた局所一意性を有している．第６章有理曲面に対する幾何的 Newton 法の頑健性曲面／曲面相互の交線を交線追跡法により求める際の，交線上の 1 点を幾何的 Newton 法により決定する場合の頑健化について論じる．曲線／直線の幾何的 Newton 法に対する同次化の手法を，有理曲面間相互干渉処理に応用する．従来法である CE 法は，有理曲面を対象としており，有理式表現に起因する問題により，発散現象を生じやすい．これに対し，同次曲面を対象とした SH 法は頑健である．同次曲面が非有理式で定義される曲面だからである．発散問題は，幾何的 Newton 法の等価関数の形状に依存しており，等価関数が横方向の漸近線を持つ場合に演算は発散する．曲面間相互干渉処理では等価関数が多変数を持つ複雑な形状であるため，変数の幾つかを固定し，等価関数の断面によって頑健化が説明される．有理曲面を対象とする場合，CE 法の等価関数は有理式となり，その曲面の断面は必ず横方向の漸近線を持つ．いったんパラメータが漸近線近傍の値をとると，以後は微分値が一方的に減小し，増分値は加速度的に増大する．したがって CE 法は頑健性がない．同次座標を用いて有理曲面を同次曲面として扱うのが，曲面に対する SH 法である．同次曲面は非有理式であるから，同次曲面を対象とする SH 法の等価関数には漸近線が存在せず，SH 法では演算を破綻なく行うことができる．. -. 7. -.

(12) 第７章結論本論文では，従来の幾何的 Newton 法の持つ発散問題，振動問題，局所一意性問題に対して解決方法を提案した．有理曲線／直線の交点算出に対する幾何的 Newton 法における研究成果は以下の通りである． 1. 発散問題への対応として，座標を同次化することにより演算の頑健性を向上させた．また，考察において頑健性と等価関数の漸近線との関係を明確にした． 2. 局所一意性問題への対応として，パラメータを同次化し，かつ，同次座標成分の二乗和を最小に制御することにより，局所一意性を格段に向上させた． 3. 振動問題への対応として，パラメータの複素数化を行い，複素解に収束させることにより振動現象を回避した．複素数化と同次化を併用することにより頑健性と局所一意性を両立した DHC 法を提案した．有理曲面を対象とする幾何的 Newton 法における研究成果は以下の通りである． 4. 曲面の干渉処理においても，座標の同次化によって演算の頑健性を向上させる方法を提案した．また，有理曲面を対象とした幾何的 Newton 法の頑健性と等価関数の漸近線との関係を明確にした．. -. 8. -.

(13) 2. 問題提起 2.1. はじめに自由曲線の中でも有理式表現を用いた有理曲線は，非有理式表現の通常の曲線と比べて，より高い表現自由度を持っている．有理曲線は weight を用いた形状制御が可能で，円錐曲線を厳密に表現できるなど，豊かな表現能力を備えている．しかし，有理曲線を対象とする演算処理では有理式表現に起因する問題点が多く，本来有している優れた特性が十分に利用されていない．有理曲線を対象とする従来の幾何的 Newton法（Conventional Euclidian Method 以降 CE 法とする）すなわち，ユークリッド幾何的 Newton法では，アルゴリズムが途中で破綻するなど頑健性がない．有理曲線を対象とするため，有理式表現に起因する発散問題を持つのである．実際に CE 法を用いて有理曲線と直線との交点算出を行い，初期パラメータと演算結果との関係を調べると，多くの初期パラメータに対して発散現象が起こっている．高い表現能力を持つ有理曲線であるが，これを対象とした演算処理は頑健性がない．本章では，従来の幾何的 Newton法である CE 法が頑健性を欠いた演算処理であることを示し，有理曲線を対象とした演算処理の抱える問題を提示する． 2.2. 有理曲線非有理式曲線は，円や放物線といった円錐曲線を厳密に表現することができない．しかし，有理曲線では制御点に適当な重み係数を与えることにより，厳密に正確に円錐曲線を表現できる． 2.2.1. 有理曲線の定義有理曲線はユークリッド空間で定義される有理式表現された曲線である．2 次元ユークリッド空間における有理パラメトリック曲線は以下のように定義される． p(t ) = [ x(t ) y (t )] = [ X (t ) w(t ) Y (t ) w(t )]∈ E 2 (4). n 次の有理曲線は，次のように表される． n. p(t ) =. ∑α (t ) w q j =0 n. j. j. j. (5). ∑α (t ) w i. i. i =0. ここに，q j は制御ベクトル，w j は weight（重み係数），α j (t ) はスカラー関数である．ただし，すべての j についてα j (t ) ≥ 0 またはα j (t ) ≤ 0 であり，また，すべての j について w j > 0 または w j < 0 である． 2.2.2. 有理 Bezier 曲線 j 番目の制御点をq j とし，その制御点における weight を w j とするとき， n 次の有理 Bezier 曲線は次の式で表される． -. 9. -.

(14) n. p(t ) =. ∑ B (t )w q j= 0. j ,n. j. j. n. ∑ B (t )w j ,n. [. qj = xj. ]. yj ∈ E2. (6). j. j =0. B j ,n (t ) は Bernstein 基底関数であり，以下のように記述される． n! B j ,n (t ) = (1 − t )n− j t j (n − j) ! j!. (7). 2.3. 有理曲線の特徴 (1) 円錐曲線の厳密な表現通常の Bezier 曲線や B-spline 曲線のような非有理式曲線では，円や楕円など円錐曲線の正確な表現は不可能である．しかし，有理 Bezier 曲線や NURBS などの有理曲線では，適切な weight と制御ベクトルを与えることにより，厳密に正確な円錐曲線を表現することができる． (2) Weight による形状制御有理曲線は，制御ベクトルq j の weight w j を変化させることにより，曲線形状を変化させることができる．Weight w j の値が大きいほど曲線は制御ベクトル q j に引き寄せられ，小さいほど制御ベクトルから離れるという性質を持っている． (3) 条件付凸包性曲線が凸包領域の内部に収まっていることを凸包性という．凸包領域とは制御ベクトルで作られる多角形である．曲線が凸包性を持っていると，干渉処理を行う際，凸包領域が干渉していなければ曲線も干渉しないと判断できるので，処理が容易になる．図4に示すように，有理曲線では，weight が正負混在である場合に，曲線が凸包領域の外に出てしまい，凸包性を失う．有理曲線に凸包性を持たせるためには，制御ベクトルの weight w j がすべて同符号でなければならない．. (a) w0 , w1 , w2 > 0 のとき凸包性が成り立っている. (b) w1 だけを負にとると凸包性が成り立たない Fig. 4 Convex hull.. - 10 -.

(15) (4) 無条件アフィン不変性アフィン写像は，恒等写像，平行移動，拡大，縮小，回転移動，せん断などがあり， CAD ではよく使われる．アフィン写像に関して表現式が不変となる性質をアフィン不変性という． A を線形マトリクス， x ， v をベクトルとすると，アフィン写像は， Φ x = Ax + v （ x, v ∈ R 2 , R 3 ） (8) と表される．制御ベクトル q j と混ぜ合わせ関数 α j (t ) から，曲線 p(t ) が， n. p(t ) = ∑ α j (t ) q j. (9). j= 0. と表されるとき，アフィン不変性は， n. Φ p(t ) = ∑ α j (t ) Φq j. (10). j =0. と表すことができる．つまり，曲線上の点にアフィン変換を施して得られる曲線と，制御ベクトルにアフィン変換を施してから得られる曲線が等しいということである．式(10)が成立するためには，通常の曲線では n. ∑ α (t ) = 1 j= 0. (11). j. という条件を満たさねばならない．しかし，有理曲線は， n. p(t ) =. ∑ α (t ) w q j. j. j. j= 0. (12). n. ∑ α (t ) w j =0. j. j. であるから，常に式(11)が満たされ，無条件でアフィン不変性が成り立つ．したがって，係数関数に制約がない． (5) 係数の整数化有理式表現を利用して係数を整数化できるので，有理曲線は厳密に正確な表現式で表すことができる． 2.4. 有理曲線の問題点 (1) Weight の制約凸包性を持たせるために制御ベクトルのweight をすべて同符号にしなければならない．このことが有理曲線の weight による形状制御の表現自由度に制約を与えている． (2) 厳密ではない座標表現有理曲線は厳密に正確な表現式で表される．しかし，座標を評価する際に除算を行わねばならず，座標の厳密な評価ができない． (3) 頑健性のない幾何的 Newton 法. - 11 -.

(16) 後に詳しく述べるが，有理曲線を対象とした幾何的 Newton 法は発散現象が起こりやすい． 2.5. ユークリッド幾何的 Newton 法（CE 法） CE 法（ユークリッド幾何的 Newton法）は，ユークリッド空間において有理曲線を対象とした幾何的 Newton 法である．2 つのベクトルv A ， v B によって決定される線分 v (s ) と有理曲線 p(t ) があり，交点が存在すると仮定する．有理曲線 p(t ) と線分 v (s ) を以下のように与える． (13) p(t ) = [ x(t ) y (t )] = [ X (t ) w(t ) Y (t ) w(t )]. v (s ) = s v A + (1 − s )v B. (14). v A = [x A. y A ] = [ X A wA YA w A ]. (15). v B = [xB. y B ] = [ X B wB YB wB ]. (16). 有理曲線 p(t ) と線分 v (s ) の交点では次式が成り立つ．. p(t ) = v (s ). (17). 有理曲線と線分の交点近傍に，初期点 p(t 0 ) , v (s 0 ) を与える．この初期点よりパラメータ値がそれぞれ微小量δ s , δ t だけ変化した点が交点であるとすれば，次式が成り立つ． p(t 0 + δ t ) = v (s 0 + δ s ). (18). 変数δ t を求めたいが，非線形方程式であるから，直接求めることはできない．そこで，この式の両辺を Taylor 展開して 1 次近似式を得る． p(t 0 ) + δ s p′(t 0 ) = v (s 0 ) + δ sv ′(s 0 ) = (1 − s 0 − δ s )v A + (s 0 + δ s )v B. (19). これは 2 元連立方程式である．この方程式をパラメータ増分値δ t について解くと，. x(t 0 ) − x A x − xA δt = − B x ′(t 0 ) xB − x A. y (t 0 ) − y A y B − yA y ′(t 0 ) yB − y A. (20). となる．この式を同次座標を用いた表現にすることで，同次処理との比較が簡単になる．上式を 3×3 行列式の表現に変形し，さらに分子と分母に wA ，wB をかけても，δ t の値は変わらないから，. - 12 -.

(17) x(t 0 ) xA w A x B wB δt = − x′(t 0 ) xA w A x B wB. y(t 0 ) 1 y A wA w A y B wB wB y ′(t 0 ) 0 y A wA w A y B wB wB X (t 0 ) Y (t 0 ) 1 w(t 0 ) w(t 0 ) XA YA wA XB YB wB. =−. X ′(t 0 )w(t 0 ) − X (t 0 )w′(t 0 ) Y ′(t 0 )w(t 0 ) − Y (t 0 )w′(t 0 ) 0 w 2 (t 0 ) w2 (t 0 ) XA YA wA XB YB wB. (21). と表現することができる．このようにして求められた増分値δ t を用いて，新たな初期パラメータ t は t i +1 = t i + δ t. (i = 0 ,1,L). (22). として求められる． 2.6. 実行例. Fig. 5 Relation between a Bezier curve and a line.. 3 次有理曲線と直線との交点を幾何的 Newton法を用いて求める実験を行う．曲線と. - 13 -.

(18) 直線の関係を図5に示す．有理曲線の 4 つの制御点q 0 , q1 , q 2 , q3 の座標と各制御点における weight は， q 0 = (0, 40) ， weight = 1 q1 = (20, 0) ， weight = 3 q 2 = (40 , 40 ) ， weight = 9 q 3 = (60, 0 ) ， weight = 1 とする．直線は y = 22 であり，次の 2 点 v A , v B から決定される． v A = (0, 22) v B = (100, 22 ) このときの交点はv a , v b , v c の 3 点であり，それぞれの交点における通常パラメータを t a , t b , t c とする．初期パラメータの範囲を− 0.5 ≤ t ≤ 1.5 とし，0.001 単位で値を変化させた初期パラメータを与えて幾何的 Newton法を行った．初期パラメータと CE 法による演算結果のパラメータ値との関係を図6に示す．ただし，図中の赤色の点は発散を表している．. Fig. 6 Result of CE method.. 図6より，演算結果を整理すると次のようになる． (a) 解 t a = 0.11978443 に収束． (b) 解 t b = 0.21712988 に収束． (c) 解 t c = 0.95590338 に収束． (d) 発散により，解が求められない．このとき，初期パラメータと CE 法による演算結果との関係を図7に示す． - 14 -.

(19) CE 法による演算結果をみると，発散が起きる領域(d)が多く，初期パラメータと収束した解との関係が不連続的である．従来法である CE 法は頑健性がないことがわかる．. Fig. 7 Result of CE method.. 2.7. まとめ有理曲線は weight による形状制御が可能であり，非有理式曲線と比較して高い表現能力を持った曲線である．しかし，有理曲線を対象とした演算処理では，有理式表現に起因する問題から発散が生じやすい．従来からの幾何的Newton法であるCE法による有理曲線と直線との交点算出の結果をみると，多くの初期パラメータからの演算で発散している．この発散現象は有理式表現に起因する問題である．また，初期パラメータと収束解との関係も不連続的であり，局所一意性の乱れが見られる．本論文では幾何的 Newton 法に同次処理を導入し，頑健性，局所一意性を向上させる方法を提案する．. - 15 -.

(20) 3. 発散問題への対応 3.1. はじめに 2章で述べたように，有理曲線を対象とする従来の幾何的Newton法は頑健性がない．従来法では，反復計算の途中で発散する場合が多い．この発散現象は有理式に起因する問題である．発散問題を解決するために，座標を同次化した幾何的 Newton 法である通常パラメータ同次幾何的 Newton法（Singly homogenized method以降 SH法とする）が提案された．SH 法は山田ら[Yamada1995]によって方法が提案され，幾つかの例題によって頑健性が示された．しかし，演算の頑健化に対する考察がなされていない．本論文では頑健性の向上について等価関数という観点から考察を述べる． SH 法は同次曲線を対象とした幾何的 Newton法である．同次曲線は有理曲線の座標を同次化し，ユークリッド空間より 1 次元高い同次ベクトル空間で扱われる非有理式表現された曲線である．同次曲線は有理曲線と同様の性質を持つが，有理曲線が抱えている有理式表現に起因する問題点や制約が存在せず，有理曲線より更に高い表現自由度を持っている．従来法の CE 法は有理曲線を対象とするため，有理式に起因する発散現象が起こりやすい．座標を同次化した SH 法では，非有理式表現の同次曲線を対象とし，有理式表現による問題は生じないため，発散は起きず，演算は頑健である．座標の同次化による演算の頑健性向上について説明するには，交点を求める幾何的処理と等価な関数をみればよい．これを等価関数という．幾何的 Newton 法の頑健性はこの等価関数の形状に大きく依存している．対象とする曲線が有理式か非有理式かという違いは，等価関数の形状に影響を与える．従来の CE 法では有理曲線を対象とするため，等価関数も有理式表現となり，必ず横方向の漸近線を持つ．いったんパラメータが漸近線近傍の値をとると，以後は微分値が一方的に減小し，増分値は加速度的に増大する．これに対し，SH 法では同次曲線を対象とし，同次曲線は非有理式表現であるから， SH 法の等価関数は非有理の通常多項式となり，横方向の漸近線が発生しない．したがって，SH 法は頑健である． 3.2. 同次曲線 3.2.1. 同次曲線の定義同次曲線は射影空間に付随する同次ベクトル空間で定義される曲線であり，次式のように表現される． P (t ) = [X (t ) Y (t ) w(t )] = [ x(t )w(t ) y(t )w(t ) w(t )] ∈ R 3. (23). ただし，オーバーラインは同値類を表している．同値類とは，同値関係，つまり，任意のスカラー k ≠ 0 について ( X , Y , w) = (kX , kY , kw) の関係を満たす点の集合である． n 次の同次曲線は，同次座標を成分とするベクトルQ j ( j = 0,1,L ,n ) の凸結合で表さ - 16 -.

(21) れる． n. P (t ) = ∑α j (t )Q j. (24). j =0. ここに， α j (t ) ( j = 0,1,L ,n ) は同一符号のスカラー関数（正負ともに可）である． 3.2.2. 同次 Bezier 曲線 j 番目の制御ベクトルを，同次座標を成分として Q j とすると， n 次の同次 Bezier 曲線は次の式で表される． n. P (t ) = ∑ B j ,n (t )Q j j= 0. [. Qj = X j. Yj. ]. w j ∈ R3. B j ,n (t ) は Bernstein 基底関数であり，以下のように記述される． n! B j ,n (t ) = (1 − t )n− j t j (n − j) ! j!. (25). (26). 同次曲線では，有理曲線の分母であったものを曲線ベクトルの 1 つの成分として扱う．これにより，有理曲線の処理が非有理な通常多項式曲線の処理と等価になり，有理曲線に付随する様々な問題が解決される． 3.3. 同次曲線の利点 (1) 厳密な座標表現有理曲線は有理式表現であり，座標を得るために除算を行う．これに対し，同次曲線はすべての成分が非有理化された同次座標を扱うため，同次曲線では厳密に正確な座標評価を行うことが可能である． (2) 無条件凸包性有理曲線は weight の符号がすべて等しくなければ，ユークリッド平面上で凸包性が成立しない．これに対し，同次曲線は，同次ベクトル空間で定義される制御ベクトルの凸結合として定義されており，同次ベクトル空間において原点を通る錐面として表される．この錐面は常に制御ベクトルと原点で作られる多角錐の内部にあるので，同次ベクトル空間において無条件で凸包性が成り立つ． (3) 無条件射影不変性有理曲線は無条件アフィン不変性を持つが，同次曲線は無条件射影不変性を持っている．同次曲線の扱われる同次ベクトル空間では，アフィン変換を含む射影変換を線形変換として表すことができる． A を線形マトリクス，X を同次ベクトルとすると，射影写像は， Φ X = AX. （ X ∈ R3 , R 4 ）. (27). と表される．制御ベクトル Q j と混ぜ合わせ関数 α j (t ) から，同次曲線 P (t ) が， - 17 -.

(22) n. P (t ) = ∑ α j (t ) Q j. (28). j =0. と表されるとき，同次曲線に対する射影不変性は， n. Φ P (t ) = ∑ α j (t )ΦQ j. (29). j =0. と表すことができる．したがって，同次曲線では射影不変性が無条件で成り立つ．同次ベクトル空間ではすべての射影変換が線型変換となるため，統一的な処理が可能である． (4) 頑健な幾何的 Newton 法有理曲線を対象とする幾何的 Newton 法はしばしば発散する．これに対し，同次曲線を対象とする幾何的 Newton 法は非常に頑健である．詳細は後に述べる． 3.4. 同次幾何的 Newton 法（SH 法）上記の有理曲線 p(t ) に対応する通常パラメータ同次曲線 P (t ) は P (t ) = [ X (t ) Y (t ) w(t )]. (30). となる．また，線分 v (s ) に対応する同次線分 V (s ) は V (s ) = sV A + (1 − s )V B. (31). V A = [X A. YA. wA ]. (32). VB = [X B. YB. wB ]. (33). となる．同次曲線 P (t ) と同次線分V (s ) の交点では，同値関係により，0 ではない定数α について次式が成り立つ．. P (t ) = αV ( s ). α ≠0. (34). 同次曲線と同次線分の交点近傍に，初期点 P (t 0 ) , V (s 0 ) を与える．この初期点よりパラメータ値がそれぞれ微小量δ s , δ t だけ変化した点が交点であるとすれば，次式が成り立つ． P (t 0 + δ t ) = αV (s 0 + δ s ). α ≠0. (35). 変数δ t を求めたいのだが，非線形方程式であるため直接求めることができない．そこで，(35)式の両辺を Taylor 展開して 1 次近似式を得る． P (t 0 ) + δ tP ′(t 0 ) = α {V ( s 0 ) + δ sV ′( s 0 )} = α {(1 − s 0 − δ s )V A + (s 0 + δ s )V B } この連立方程式をパラメータ増分値 δ t について解くと. - 18 -. (36).

(23) X (t 0 ) Y (t 0 ) w(t 0 ) XA YA wA XB YB wB δt = − X ′(t 0 ) Y ′(t 0 ) w′(t 0 ) XA YA wA XB YB wB. (37). このようにして求められた δ t を用いて，新たな初期点のパラメータ t は t i +1 = t i + δ t. (i = 0,1,L). (38). として求められる．このように SH 法とは，同次ベクトル空間における通常パラメータの同次曲線を対象とした幾何的 Newton 法である． 3.5. 実行例 3 次有理曲線と直線とが図8に示すように 3 つの点で交差している．交点をv a , v b , v c の 3 点とし，それぞれの交点におけるパラメータをt a , t b , t c とする．これは図5と同じ問題である．. Fig. 8 Relation between a Bezier curve and a line.. 初期パラメータの範囲を− 0.5 ≤ t ≤ 1.5 とし，0.001 単位で値を変えた初期点を与え，幾何的 Newton法を行う．初期パラメータと，SH 法による演算結果のパラメータ値との関係を図9に示す．図9では発散は生じないが，発散を含め，演算結果を整理すると次のようになる． (a) 解 t a = 0.11978443 に収束． (b) 解 t b = 0.21712988 に収束． (c) 解 t c = 0.95590338 に収束． (d) 発散により，解が求まらない．. - 19 -.

(24) このとき，CE 法，SH 法による演算結果と初期パラメータとの関係をそれぞれ図10，図11に示す． CE 法の演算結果を示す図10では発散を示す結果(d)となる初期パラメータが多いが， SH 法の演算結果を示す図11では(d)は存在せず頑健である．. Fig. 9 Result of SH method.. Fig. 10 Result of CE method.. Fig. 11 Result of SH method.. - 20 -.

(25) 3.6. 考察図10より，CE 法には発散する初期点領域が多く存在する．一方，図11より，SH 法には発散する初期点領域はまったく存在しない．交点を求める幾何的処理と等価な関数を等価関数という．演算の頑健性は等価関数の形状に依存している． 3.6.1. CE 法の等価関数初期パラメータ t における CE 法の増分値は，式(21)より， X (t ) Y (t ) 1 w(t ) w(t ) XA YA w A XB YB w B. δt = −. X ′(t )w(t ) − X (t )w′(t ) Y ′(t )w(t ) − Y (t )w′(t ) 0 w 2 (t ) w 2 (t ) XA YA wA XB YB wB. である．式(39)の分子の式を X (t ) Y (t ) 1 w(t ) w(t ) f (t ) = X A YA wA XB YB wB. (39). (40). のように t についての関数 f (t ) とすると，増分値は次のように表される． δ t = − f (t ) f ′(t ) (41) 上式より，方程式 f (t ) = 0 を解くことと，交点のパラメータt を求めることは同等であることがわかるので，関数 f (t ) を CE 法の等価関数という．図8の問題における CE 法の等価関数 f (t ) を図12に示す． 3.6.2. SH 法の等価関数初期パラメータ t における SH 法の増分値は，式(37)より，. X (t ) Y (t ) X A YA X B YB δt = − X ′(t ) Y ′(t ) XA YA XB YB. w(t ) wA wB w′(t ). (42). wA wB. - 21 -.

(26) である．式(42)の分子の式を. X (t ) Y (t ) w(t ). F (t ) = X A XB. YA YB. wA wB. (43). のように t についての関数 F (t ) とすると，増分値は次のように表される． δ t = − F (t ) F ′(t ) (44) 上式より，方程式 F (t ) = 0 を解くことと，交点のパラメータt を求めることは同等であるので，関数 F (t ) をSH法の等価関数という．図8の問題におけるSH法の等価関数 F (t ) を図13に示す．. Fig. 12 The equivalence functions of CE method.. Fig. 13 The equivalence functions of SH method.. - 22 -.

(27) 3.6.3. 頑健性と等価関数 SH 法は CE 法と比べて非常に頑健である．頑健性の向上は，等価関数における横方向の漸近線の有無により，以下のように説明できる． CE 法では有理曲線を対象とするため等価関数は有理式であるが，SH 法では同次曲線を対象とするため等価関数は非有理式である． CE法の等価関数 f (t ) は有理関数であるから，次数の等しい2つの関数 F (t ) と w(t ) を分子と分母にもつ．パラメータ t について極限をとると F (t ) t→ ±∞ f (t ) = → α (45) w(t ) となる．α は定数である．パラメータ t についての極限が定数に収束するため，等価関数 f (t ) には必ず横方向の漸近線が存在する．漸近線付近を模式的に表したものが図14である．パラメータがいったん漸近線付近の値をとると，等価関数がより漸近線に近付く方向に次のパラメータが求められ，増分値の絶対値が加速度的に増大する．これが繰り返されるため，演算はパラメータを無限大にする方向へ進み，最終的には発散してしまう．このため，等価関数が有理式となる CE 法は頑健性がない．これに対し，同次曲線を対象とする交線算出では，等価関数は非有理の通常多項式となるため，横方向の漸近線は発生せず，増分値の増加による発散が生じない．したがって，等価関数が非有理式となる SH 法は頑健である．. Fig. 14 Behavior of f(t) near an asymptote.. - 23 -.

(28) 3.7. まとめ本章では，発散問題への対応として，座標を同次化した SH 法を提案した．発散問題は，等価関数が有理式で表現される場合に横方向の漸近線を持つことが原因である．従来の CE 法では有理曲線を対象とするため，等価関数も有理式となり，横方向の漸近線を持つ形状となっている．幾何的 Newton 法の初期パラメータが漸近線付近の値をとると発散してしまう． SH 法は同次曲線を対象とするため，等価関数は非有理式となり，漸近線が発生しない．同次座標を用いた同次曲線を対象とすることにより，発散問題を解決した頑健な幾何的 Newton 法を提案することができた．. - 24 -.

(29) 4. 局所一意性問題への対応 4.1. はじめに SH 法は座標を同次化することにより，従来の CE 法の有理式表現に起因する発散問題を解決した．しかし，SH 法では初期パラメータと演算結果との関係が不連続的であり，局所一意性に問題がある．局所一意性が成立しないと，初期パラメータと演算結果との関係が予測できず，予想外の解に収束する可能性がある．局所一意性を向上させるために，パラメータを同次化した幾何的 Newton 法である同次パラメータ同次幾何的 Newton法（Doubly Homogenized method 以降 DH 法とする）が提案された[Yamada1995a]．DH 法はパラメータも同次化された同次パラメータ同次曲線を対象とする幾何的 Newton法である．座標が同次化されているため，SH 法と同様に演算は頑健であり，発散現象は発生しない．さらに DH 法ではパラメータを同次化することにより，同次パラメータ制御という新しい自由度を持ち，幾何的 Newton 法の通常パラメータ増分値（以後は，単にパラメータ増分値とし，同次パラメータ増分値と区別する）の大きさを制御することができる．パラメータ増分値を適切に制御することにより，局所一意性を向上させることが可能となる．従来の同次パラメータ制御では，得られるパラメータ増分値が異常に大きくなる場合があり，その結果として局所一意性が必ずしも十分ではなかった．本論文では，同次パラメータ増分値の二乗和が最小となる関係を同次パラメータ制御とした．これにより，パラメータ増分値は適切に制御され，局所一意性が飛躍的に向上する．本章では，DH 法における局所一意性の向上を幾つかの実験結果により示す．局所一意性の向上に関する考察では，パラメータ増分値の大きさを従来法と比較し， DH 法が適切にパラメータ増分値を制御していることを示す．また，同次パラメータ空間において同次パラメータ制御を幾何的にとらえ，従来法ではパラメータ増分値が極端に大きな値をとるような場合も，DH 法では適切な大きさに制御されることを示す．また，演算回数を比較し，DH 法は局所的な演算を可能にしているにも関わらず，演算回数は従来法と同程度であることを示す． 4.2. 同次パラメータパラメータの同次化には幾つかの方法が考えられるが，ここでは 2 つの方法を示す． 1 つ目は Type1 と呼ばれる方法であり，単純に分子と分母を 2 成分として同次化する．このとき，同次パラメータ (S , h ) と通常パラメータ t との間の関係は， S t= (46) h である． 2 つ目は Type2 と呼ばれる方法で，同次パラメータ(σ ,η ) と通常パラメータt との間の関係は，. - 25 -.

(30) t=. σ σ +η. (47). である．これを用いると Bernstein 基底関数が簡単に表現でき，Bezier 曲線の表現が簡単になる．以降は同次パラメータとして，単純な同次化を行っている Type1 を扱うことにする． 4.3. 同次パラメータ同次曲線 4.3.1. 同次パラメータ同次曲線の定義同次パラメータ同次曲線は同次ベクトル空間で定義される，パラメータが同次化された曲線である．同次パラメータ Type1 を用いた同次パラメータ同次曲線は次のように定義される． HP (S , h ) = [X (S , h ) Y (S , h ) w(S , h )]∈ R 3. (48). 4.3.2. 同次パラメータ同次 Bezier 曲線 j 番目の制御ベクトルをQ j とすると，n 次の同次パラメータ同次 Bezier 曲線は次の式で表される． n. HP (S , h ) = ∑ HB j ,n (S , h)Q j j =0. [. Q j = X j Yj. ]. wj ∈ R3. (49). ここで HB j ,n (S , h ) は同次 Bernstein 基底関数であり，次のように記述される． HB j, n (S , h) =. n! n− j S j (h − S ) (n − j ) ! j!. (50). 4.3.3. 同次パラメータ同次 Bezier 曲線の偏微分導関数同次 Bernstein 基底関数の偏微分導関数は ∂ HB j ,n (S , h) = n ⋅ HB j −1,n −1 (S , h) − n ⋅ HB j ,n−1 (S , h ) ∂S ∂ HB j ,n ( S , h) = n ⋅ HB j ,n −1 (S , h ) ∂h. (51) (52). であり，同次パラメータ同次 Bezier 曲線の１階偏微分導関数は. HPS (S , h ) =. HPh (S , h) =. n  n  ∂ HP ( S , h ) = n∑ HB j−1,n−1 ( S , h) − n ∑ HB j ,n −1 (S , h ) ⋅ Q j ∂S j =0  j =0 . (53). n ∂ HP ( S , h ) = n∑ HB j, n−1 (S , h) ⋅ Q j ∂h j= 0. (54). となる．n 次の同次パラメータ同次 Bezier 曲線 HP (S , h ) と通常パラメータ同次 Bezier 曲線 P (t ) の関係は次のようになる． HP (S , h) = h n P (t ) ． (55). - 26 -.

(31) 上式の１階偏微分導関数は， HP S (S , h ) = h n−1 ⋅ P ′(t ). (56). HP h ( S , h ) = n ⋅ h n−1 ⋅ P (t ) − S ⋅ h n− 2 ⋅ P ′(t ). (57). となる． 4.4. 同次パラメータ同次幾何的 Newton 法（DH 法） DH 法（同次パラメータ同次幾何的 Newton法）は，同次ベクトル空間において，パラメータが同次化された同次パラメータ同次曲線 HP ( S ,h ) を対象として，交点算出演算を行う．上記の有理曲線 p(t ) に対応する同次パラメータ同次曲線 HP ( S ,h ) は HP (S ,h ) = [ X ( S ,h ) Y (S , h) w(S , h )]. (58). となる．同次パラメータ同次曲線 HP ( S ,h ) と同次線分V (s ) の交点では，同値関係により， 0 でない定数 α に対して次の式が成り立つ．. HP (S ,h ) = αV (s ). α ≠0. (59). 同次曲線と同次線分の交点近傍に，初期点 HP (S 0 ,h0 ) ，V (s 0 ) を与える．この初期点よりパラメータ値がそれぞれ微小量δS ，δh ，δ s だけ変化した点が交点であるとすれば，次式が成り立つ． HP (S 0 + δ S ,h0 + δ h) = αV ( s0 + δ s ). α ≠0. (60). 変数δS ，δh を求めたいのだが，式は非線形連立方程式であるため，直接求めることはできない．式(60)の両辺を Taylor 展開して１次近似式を得る． HP (S 0 ,h0 ) + δ SHPS (S 0 ,h0 ) + δ hHPh (S 0 ,h0 ) = α {(1 − s 0 − δ s )VA + (s 0 + δ s )VB }. (61). 4 変数に対して 3 つの方程式であるから，式が足りない．パラメータ増分値δS , δh を求めるためには変数間に何らかの関係式がもうひとつ必要である．変数δS , δh の間に関係式を与えることを同次パラメータ制御という．DH 法の増分値は，同次パラメータ制御の与え方によって変化する．同次パラメータを導入することにより，幾何的 Newton 法は新しい自由度を得たのである． 4.4.1. DH 法の等価関数式(61)は，ベクトル HP (S 0 ,h0 ) + δ SHPS (S 0 ,h0 ) + δ hHPh (S 0 ,h0 ) が，2 つのベクトル VA , VB と線形従属であることを意味する．行列式を用いてこれを表現すると，. - 27 -.

(32) X ( S0 ,h0 ) + δSX S (S 0 ,h0 ) + δhX h (S 0 , h0 ) XA XB. Y (S 0 ,h0 ) + δSYS (S 0 ,h0 ) + δhYh (S 0 ,h0 ) YA YB w( S0 ,h0 ) + δSwS (S 0 , h0 ) + δhwh (S 0 ,h0 ) wA wB. =0. (62). =0. (63). となる．これを δS , δh に関してまとめると，. X ( S0 ,h0 ) Y ( S0 ,h0 ) w(S 0 , h0 ) XA XB. YA XB. wA wB. X S (S 0 ,h0 ) YS ( S0 ,h0 ) wS ( S0 ,h0 ) + δS. XA XB. YA XB. wA wB. X η (S 0 , h0 ) Yh (S 0 , h0 ) wh (S 0 , h0 ) + δh. XA XB. YA XB. wA wB. となる．ここで，. HF (S , h ) =. X ( S ,h ) Y ( S , h) w(S , h ) XA XB. YA XB. wA wB. (64). とおくと，(63)式は次のように表すことができる． HF (S 0 , h0 ) + δSHFS (S 0 ,h0 ) + δhHF h (S 0 ,h0 ) = 0. (65). 方程式 HF (S ,h ) = 0 を解くことと，交点における同次パラメータ S，h を求めることは同等であるから，関数 HF (S ,h ) は DH 法の等価関数である．次数が n のとき，同次パラメータ同次 Bezier 曲線 HP ( S ,h ) と通常パラメータ同次 Bezier 曲線 P (t ) の間には式(55)のような関係があるので. - 28 -.

(33) X (S , h) Y (S ,h ) w(S ,h ). HF (S , h) =. XA XB. YA XB. wA wB. h X (t ) h Y (t ) h w(t ) n. =. XA XB. n. n. YA XB. wA wB. X (t ) Y (t ) w(t ) = h XA XB n. YA XB. wA = h n F (t ) wB. (66). となる．つまり，DH 法は，SH 法の等価関数 F (t ) を h n 倍にしたものを解いていることになる． 4.4.2. 同次パラメータ制御同次パラメータ増分値δS ，δh を求めるためには同次パラメータ制御が必要である．図15に示すように，同次パラメータ制御として，δS -δh 空間において原点を通り，式 (65)と直交するような関係式 − δS HFh ( S0 ,h0 ) + δh HFS (S 0 , h0 ) = 0 (67) を与える．直交する 2 つの直線は必ず１つの交点を持つから，あらゆる初期点に対し，一意的に同次パラメータ増分値δS , δh を求めることができる．式(65)と式(67)を連立させて解くと， − HF (S 0 , h0 ) ⋅ HFS (S 0 ,h0 )  δ S =  HFS2 (S 0 ,h0 ) + HFh2 ( S0 ,h0 ) (68)  − HF (S 0 ,h0 ) ⋅ HFh (S 0 ,h0 ) δh =  HFS2 (S 0 , h0 ) + HFh2 (S 0 ,h0 ) となる．このようにして求められたδS , δh を使って，新たな初期点の同次パラメータ S ,h は Si +1 = S i + δS (i = 0,1,L) (69) hi+1 = hi + δh つまり， Si +1 = S i −. HF (S i , hi )⋅ HFS (S i , hi ) HFS2 (S i ,hi ) + HFh2 ( Si ,hi ). (70). HF ( Si ,hi ) ⋅ HFh (S i ,hi ) hi+1 = hi − HFS2 (S i ,hi ) + HFh2 ( Si ,hi ). となる．同次パラメータ S ，h には同値関係があるので，分母 HFS2 (S i ,hi ) + HFh2 (S i , hi ) を S i+1 ，hi+1 両方にかけても同じ通常パラメータを表す．したがって，あらためて S i+1 ， hi+1 を次のように定めると，. - 29 -.

(34) { } = {HF (S , h ) + HF (S , h )}h − HF (S , h ) ⋅ HF ( S ,h ). Si +1 = HFS2 ( Si ,hi ) + HFh2 ( Si ,hi ) S i − HF (S i , hi ) ⋅ HFS (S i ,hi ) hi+1. 2 S. i. 2 h. i. i. i. i. i. i. h. i. (71). i. のように，非有理式表現となる．この操作を繰り返すことにより有理曲線と線分の交点におけるパラメータを求めることができる．. Fig. 15. 4.5.. Homogeneous parameter, homogeneous Newton method in homogeneous parameter space.. 実行例. Fig. 16. Relation between a Bezier curve and a line.. 3 次有理曲線と直線とが図16に示すように3つの点で交差している．交点をv a , v b , v c の 3 点とし，それぞれの交点におけるパラメータをt a , t b , t c とする．これは図5，図8 に示す問題と同じ問題である．初期パラメータの範囲を− 0.5 ≤ t ≤ 1.5 とし，0.001 単位で値を変えた初期点を与え，. - 30 -.

(35) 幾何的 Newton法を行う．初期パラメータと，SH 法による演算結果のパラメータ値との関係を図17に示す．図17では発散は生じないが，発散を含め，演算結果を整理すると次のようになる． (a) 解 t a = 0.11978443 に収束． (b) 解 t b = 0.21712988 に収束． (c) 解 t c = 0.95590338 に収束． (d) 発散により，解が求められない．図20は，初期パラメータと DH 法による演算結果との関係を表している．比較のために，図18に CE 法，図19に SH 法による演算結果を示す．図18の CE 法による演算結果では，発散を起こす初期点領域(d)が多く，初期パラメータと収束解との関係が不連続的である．図19の SH 法による演算結果では，演算は頑健だが，初期パラメータと収束解との関係は不連続的である．図20の DH 法による演算結果では，演算が頑健で，初期パラメータと収束解との関係も連続的である．. Fig. 17. Relation between a bezier curve and a line.. - 31 -.

(36) Fig. 18 Result of CE method.. Fig. 19 Result of SH method.. Fig. 20 Result of DH method.. 4.6. 考察 4.6.1. 局所一意性の向上図20の DH 法による演算結果では，それぞれの解に収束する初期パラメータが連続する領域となっている．このように，初期パラメータと収束解との間に連続的な関係が得られることを局所一意性という． SH 法では等価関数の形状が単純になるため，CE 法と比べて局所一意性の向上がみられるが，DH 法では同次パラメータを導入することにより局所一意性は飛躍的に改善される．これはパラメータの増分値が同次パラメータ制御によって適切に制御されるためである． 4.6.2. 高次の問題に対する実行例 6 次有理曲線と直線との交点を幾何的 Newton法を用いて求める．曲線と直線の関係を図21に示す．有理曲線の 7 つの制御点q 0 , q1 , q 2 , q3 , q 4 , q 5 , q 6 の座標と各制御点における weight は， q 0 = (0, 0 ) , weight = 1 q1 = (20, 100 ) ， weight = 3 q 2 = (40, 0) , weight = 18 q3 = (60, 70 ) ， weight = 16 q 4 = (80, 0 ) , weight = 18 q5 = (100, 100) , weight = 3 q 6 = (120, 0 ) , weight = 1. - 32 -.

(37) Fig. 21 Relation between a bezier curve and a line.. とする．直線は y = 28 であり，次の 2 点 v A , v B から決定される． v A = (0, 28) v B = (200, 28) このとき，交点はv a , v b , v c , v d , v e , v f の 6 点であり，それぞれの交点における通常パラメータを t a , t b , t c t d , t e t f とする．初期パラメータの範囲を − 0.5 ≤ t ≤ 1.5 とし， 0.001 単位で値を変化させた初期パラメータを与えて幾何的 Newton法を行った．幾何的 Newton法を用いた交点算出により得られる結果は次の 7 つのうちのどれかである． (a) 解 t a = 0.02450941 に収束 (b) 解 t b = 0.20804395 に収束 (c) 解 t c = 0.35087360 に収束 (d) 解 t d = 0.64912640 に収束 (e) 解 t e = 0.79195605 に収束 (f) 解 t f = 0.97549059 に収束 (g) 発散により，解が求められない初期パラメータと演算結果との関係を，CE法について図22に，SH法について図23に， DH 法について図24にそれぞれ示す．. - 33 -.

(38) Fig. 22 Result of CE method.. Fig. 23 Result of SH method.. Fig. 24 Result of DH method.. 図22の CE 法による演算結果では，発散を起こす初期点領域(g)が多く，初期パラメータと収束解との関係が不連続的である．図23の SH 法による演算結果では，演算は頑健だが，初期パラメータと収束解との関係は不連続的である．図24の DH 法による演算結果では，演算が頑健であり，初期パラメータと収束解との関係も連続的である．このように，高次の有理曲線を対象とする場合にも，DH 法では局所一意性が向上している．次に，8 次有理曲線と直線との交点を幾何的 Newton法を用いて求める．曲線と直線の関係を図25に示す．有理曲線の 9 つの制御点q 0 , q1 , q 2 , q3 , q 4 , q 5 , q 6 , q 7 , q 8 の座標と - 34 -.

(39) 各制御点における weight は， q 0 = (0, 0 ) , weight = 1 q1 = (20, 100 ) ， weight = 5 q 2 = (40, 0) , weight = 13 q 3 = (60, 100) ， weight = 20 q 4 = (80, 0 ) , weight = 24 q5 = (100, 100) , weight = 20 q 6 = (120, 0 ) , weight = 13 q 7 = (140, 100 ) , weight = 5 q8 = (160, 0) , weight = 1 とする．直線は y = 49.048625792812 であり，次の 2 点 v A , v B から決定される． v A = (0, 49.048625792812) v B = (200, 49.048625792812 ). Fig. 25 Relation between a bezier curve and a line.. このとき，曲線と直線とは t = 0.5 において重解を持つ．交点はv a , v b , v c , v d , v e , v f , v g の 7 点であり，それぞれの交点における通常パラメータをt a , t b , t c t d , t e t f , t g とする．初期パラメータの範囲を− 3.0 ≤ t ≤ 3.0 とし， 0.001 単位で値を変化させた初期パラメータを与えて幾何的 Newton法を行った．幾何的 Newton法を用いた交点算出により得られる結果は次の 8 つのうちのどれかである． (a) 解 t a = 0.03129892 に収束 (b) 解 t b = 0.14631360 に収束 (c) 解 t c = 0.32431412 に収束 (d) 解 t d = 0.50 に収束 (e) 解 t e = 0.67568587 に収束 (f) 解 t f = 0.85368639 に収束. - 35 -.

(40) (g) 解 t g = 0.96870107 に収束 (h) 発散により，解が求められない初期パラメータと演算結果との関係を，CE法について図26に，SH法について図27に， DH 法について図28にそれぞれ示す．. Fig. 26 Result of CE method.. Fig. 27 Result of SH method.. Fig. 28 Result of DH method.. - 36 -.

(41) 図26の CE 法による演算結果では，発散を起こす初期点領域(h)が多く，初期パラメータと収束解との関係が不連続的である．図27の SH 法による演算結果では，演算は頑健だが，初期パラメータと収束解との関係は不連続的である．図28の DH 法による演算結果では，演算が頑健であり，初期パラメータと収束解との関係も連続的である．このように，高次の有理曲線を対象とし，かつ重解が含まれるような場合にも，DH 法では局所一意性が向上している． 4.6.3. 適切な同次パラメータ制御本論文では，図15に示すように同次パラメータ増分値の二乗和δS 2 + δh 2 が最小になるような同次パラメータ制御を提案している．同次パラメータ制御は，この方法以外にも考えることができる．例えば， S ⋅ δS + h ⋅ δh = 0 (72) という関係式による同次パラメータ制御がある．この同次パラメータ制御を用いて図16の問題を解いた場合の結果を図29に示す．この場合は局所一意性の向上は見られない．このように，パラメータの同次化だけでは局所一意性は向上せず，適切な制御法が必要である．本論文が提案した同次パラメータ制御が局所一意性に有効に作用していることがわかる．. Fig. 29 Result of DH method with a conventional control of homogeneous parameters.. 4.6.4. 増分値の大きさそれぞれの幾何的 Newton 法におけるパラメータ増分値を比較する．図30，図31，図32はそれぞれ CE 法，SH 法，今回提案する DH 法における，パラメータとパラメータ増分値との関係を表している．図30，図31に示す CE 法，SH 法では，漸近線を伴ってパラメータ増分値が非常に大きな値をとることがあるのに対し，図32に示す DH 法では，パラメータ増分値の値は小さく抑えられていることがわかる．DH 法では，同次パラメータ制御によりパラメータ増分値 δ t が適切に制御されている．. - 37 -.

(42) Fig. 30 Parameter increments of CE method.. Fig. 31 Parameter increments of SH method.. Fig. 32 Parameter increments of DH method.. - 38 -.

(43) 4.6.5. 同次パラメータ空間における制御式の比較 DH 法における局所一意性の向上を代数的に説明することは困難であるため，同次パラメータ空間において幾何的な説明を試みる． DH 法の同次パラメータ制御は式(67)である．このとき，SH 法を同次パラメータで表現すると， δh = 0 (73) と表すことができる．これが SH 法の同次パラメータ制御を表す式である． S−h 空間において， SH 法，従来の同次パラメータ制御による DH 法，本論文で提案する同次パラメータ制御による DH 法によって次の初期パラメータが求められる様子をそれぞれ図33，図34，図35に示す．ユークリッド空間におけるパラメータt は， S−h 空間において，原点を通る直線の勾配として表される． SH 法では，テイラー展開の一次近似式である式(65)と式(73)との交点として次の初期パラメータが求められる．式(65)と式(73)が平行に近付くにつれて，現在の初期パラメータ t i を表す勾配と次の初期パラメータt i+1 を表す勾配との差が大きくなる．つまり，パラメータ増分値δ t が大きな値になる．大きすぎるパラメータ増分値をとると，初期パラメータから遠く離れたパラメータに演算が進行し，近傍の解に収束しない可能性が高くなる．したがって，SH 法は局所一意性に問題がある．従来の同次パラメータ制御による DH 法では，式(65)と式(72)との交点として次の初期パラメータが求められる．この場合も，式(65)と式(72)が平行に近付くにつれて，現在の初期パラメータ t i を表す勾配と次の初期パラメータ t i+1 を表す勾配との差が大きくなり，パラメータ増分値δ t が大きな値になる．したがって，従来の同次パラメータ制御では局所一意性に問題がある．これに対し，本論文で提案する同次パラメータ制御では，式(65)とこれに直交する式(67)との交点として次の初期パラメータが求められる．図15，図35に示すように，式(65)は常に初期パラメータ( Si , hi )の近傍に存在する．DH 法では同次パラメータ増分値の二乗和δS 2 + δh 2 が常に最小化されるため，次の初期パラメータt i+1 が現在の初期パラメータt i から遠く離れることがなく，パラメータ増分値δ t が極端に大きな値とはならない．したがって，DH 法では，局所的な演算処理が保証され，初期点近傍の解に収束するため局所一意性が向上するのである．. - 39 -.

(44) Fig. 33 SH method in S−h space.. Fig. 34 DH method in S−h space.. Fig. 35 DH method in S−h space.. 4.6.6. 頑健性について同次パラメータ Type1 を通常パラメータに換算する場合，式(46)の関係より， h =1 (74) という関係を用いる．この条件を与えれば，式(66)より，DH 法の等価関数は SH 法の等価関数と等しい．したがって，DH 法の等価関数は SH 法と同様，横方向の漸近線を持たないので演算処理に対して頑健である．これは DH 法も SH 法と同様に座標を同次化しており，等価関数が非有理式となるからである． 4.6.7. 演算回数の比較初期パラメータと演算回数との関係をそれぞれ CE 法は図36，SH 法は図37，DH 法は図38に示す．演算回数とは収束または発散までに要した繰り返し演算の回数とする． DH 法では増分値の大きさを制御して局所一意性を向上させているが，演算回数は他の方法と比較して差はない．. - 40 -.

(45) Fig. 36 Numbers of iterations in CE method.. Fig. 37 Numbers of iterations in SH method.. Fig. 38 Numbers of iterations in DH method.. - 41 -.