反復関数系を用いたベジエ曲線の生成
6
0
0
全文
(2) 体のモデリングとテクスチャリングの両方を１つの IFS に. 化させていくことによって求められる点列を直線で結ん. よって実現することを目的とする。. でいく方法の他に、ド・カステリョのアルゴリズムが知ら. 本論文では、その経過報告として、IFS によるベジエ曲線. れている。これは、 n = 2 または 3 の時に用いることがで. の生成について扱う。また、本手法のベジエ曲面への適用. きるアルゴリズムで、図２のように、. を示す。. Pi 0 = Pi. Pi r = (1 − t ) ⋅ Pi r −1 + t ⋅ Pi +r1−1. ２．ベジエ曲線 ベジエ曲線はパラメトリック曲線の一つである。 n 次ベ ジエ曲線は、 n + 1 個の制御点で記述される。本研究では 主に３次ベジエ曲線を扱った。 P0 , P1 , P2 , P3 をそれぞれ制. 御点の位置ベクトルとすると、３次ベジエ曲線 P(t ) は、. いる。t を変化させて求められる点 P0n を結んでいくことで ベジエ曲線を描くことができる。. 3. P(t ) = ∑ B (t )Pi i =0. とした時、 P0n はベジエ曲線上の点になることを利用して. 3 i. なお、ベジエ曲線は、 P0n によって、２つの新たなベジエ. と定義される。ただし、 t は媒介変数で、 0 ≤ t ≤ 1. 曲線に分割される事が知られている。 n = 3 の場合、制御. また、 Bin (t ) は Bernstein 関数と言い、. 点 P00 , P10 , P20 , P30 で定義されるベジエ曲線は、 点 P03 によ. Bin (t )= n Ci (1 − t ) ⋅ t i. って、それぞれ P00 , P01 , P02 , P03 、 P03 , P12 , P21 , P30 を制. と定義される。特に n = 3 の時は、. 御点とするベジエ曲線に分割される。. n −i. {. }. {. } {. }. B03 (t ) = (1 − t ). 3. B13 (t ) = 3(1 − t ) ⋅ t 2. P20. B23 (t ) = 3(1 − t ) ⋅ t 2. P11 P10. B33 (t ) = t 3. P12. 2 0. となる。図１に、３次ベジエ曲線の例を示す。. P. P03. P21. 1 0. P. P00 図 2 ド・カステリョのアルゴリズム( t = 1. 図 1. ３次ベジエ曲線. ベジエ曲線の描画には、 Bernstein 関数の媒介変数 t を変. 2 −34−. P30. 2. ).
(3) の方法で容易に IFS コードを求めることができる。 これは、. ３．Iterated Function System (IFS). ２次ベジエ曲線の制御点が３点であることに起因する。つ. （確率付き）IFS は、完備な距離空間 X 、 n 個の縮小写. まり、平面を決定するために必要十分な数の点になってい. 像ωi : X → X 、確率 pi によって、. るのである。IFS コードを求めるためには、もとの制御点. {X ;ω1 ,L,ω n ; p1 ,L, pn }. {P. , P10 , P20 を 新 た な 制 御 点 P00 , P01 , P02 及 び. と定義される。距離空間 X によるハウスドルフ空間を. {P. , P11 , P20 に移すようなアフィン変換を計算すればよ. 0 0. H ( X ) 、 B ∈ H ( X ) とすると、. 2 0. }. }. }. い。. n. W (B ) = U {ω i (b ) : b ∈ B}. P10 (1.1,2.1). i =1. と定義される写像W : H ( X ) → H ( X ) は縮小写像になる。. {. {. }. よって、点列 W o n (B ) n=1 はある収束点 A を持ち、この点 ∞. P01. をアトラクタと言う。すなわち、. P02. lim W o n (B ) = A. P11. n→∞. IFS のアトラクタを描画するアルゴリズムには、 Deterministic Algorithm と Chaos Game Algorithm の２つ がある。このうち、Deterministic Algorithm は、ある基 本図形 S を、決められた回数 s 回アフィン変換したものを、. P00. (0.1,0.7 ). 全ての変換の組み合わせに対して描画するアルゴリズム. P20. である。. (2.1,0.1). また、Chaos Game Algorithm は、ある点 xn ∈ X に、IFS. コード内の確率に従って変換を選択し、xn+1 = ω i ( xn ) とす. 図 3 IFS による２次ベジエ曲線. るアルゴリズムである。得られた点列をプロットしていく ことで、アトラクタを近似的に描くことができる。この時、 点の密度が不変測度（invariant measure）になる。. 例として、図３の２次ベジエ曲線から求めたアフィン変換. 本論文では、直線を基本図形とする Deterministic Algorithm を用いた。これは、ステップ数 s を小さくする ことで、どのような写像が行われているかが確認できるた めと、ベジエ曲面に拡張した際、法線ベクトルを与える時 に、点よりも線（面）の方が都合がよいと考えたためであ る。. を以下に示す。. ⎛ x⎞. ⎛ 0.5. ⎛ x⎞. ⎛ 0.5. 0 ⎞⎛ x ⎞ ⎛ 0.05 ⎞. ⎟⎟⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ ω1 ⎜⎜ ⎟⎟ = ⎜⎜ ⎝ y ⎠ ⎝ 0.35 0.25 ⎠⎝ y ⎠ ⎝ 0.49 ⎠ 0 ⎞⎛ x ⎞ ⎛ 1.05 ⎞. ⎟⎟⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ ω 2 ⎜⎜ ⎟⎟ = ⎜⎜ ⎝ y ⎠ ⎝ − 0.5 0.25 ⎠⎝ y ⎠ ⎝1.125 ⎠. なお、IFS の写像としては、アフィン変換を用いるのが一 般的である。本研究でもアフィン変換のみを扱っている。 次に、３次ベジエ曲線の IFS への変換について述べる。. ４．ベジエ曲線から IFS への変換. ３次ベジエ曲線の場合、２次元平面上に描きたい時のよう. それでは、実際にベジエ曲線から IFS コードを求める。. に、制御点が同一平面上にあると、４点からは平面を決定. まず、２次ベジエ曲線の IFS への変換について述べる。ア. することができないので、２次ベジエ曲線と同じ方法でア. イデアとしては、ド・カステリョのアルゴリズムによるベ. フィン変換を見つけることができない。そこで本論文では、. ジエ曲線の分割を用いた。２次ベジエ曲線においては、こ. Bernstein 関数による４次元曲線を IFS 化し、それによっ. 3 −35−.
(4) て得られた点列を、描画したい空間に写像する方法を取っ た。本手法の基本概念を図４に示す。. ⎛1 ⎛ x0 ⎞ ⎜ 2 ⎜ ⎟ ⎜ 0 ⎜x ⎟ ω1 ⎜ 1 ⎟ = ⎜ ⎜ x ⎜ 2⎟ ⎜ 0 ⎜x ⎟ ⎝ 3⎠ ⎜ 0 ⎝ ⎛ 1 ⎛ x0 ⎞ ⎜ 8 ⎜ ⎟ ⎜ 3 ⎜x ⎟ ω1 ⎜ 1 ⎟ = ⎜ 8 x ⎜ 3 ⎜ 2⎟ ⎜ 8 ⎜x ⎟ ⎝ 3 ⎠ ⎜− 3 ⎝ 8. 0 −1 − 3 ⎞⎟⎛ x ⎞ ⎛ 1 ⎞ 4 8 0 ⎜ ⎟ 3 ⎟⎜ x ⎟ ⎜ 2 ⎟ 1 1 ⎟ ⎜ 2 2 8 ⎟ 1 + 0 3 ⎟⎜ x2 ⎟ ⎜ 0 ⎟ 1 0 4 8 ⎟⎜⎜ ⎟⎟ ⎜ ⎟ 1 ⎟⎝ x3 ⎠ ⎜⎝ 0 ⎟⎠ 0 0 8 ⎠ 0 0 0 ⎞⎟⎛ x ⎞ ⎛ 0 ⎞ ⎜ 0⎟ ⎜ ⎟ ⎟ 1 0 0 ⎜ x1 ⎟ ⎜ 0 ⎟ 4 ⎟ +⎜ ⎟ 1 1 0 ⎟⎜⎜ x2 ⎟⎟ ⎜ 0 ⎟ 2 2 ⎟⎜ ⎟ ⎜ 1 ⎟ 1 0 1 ⎟⎝ x3 ⎠ ⎝ 2 ⎠ − 4 2⎠. ここで一つ注意しなければならないのが、ω1 の１行１列. 図 4 本手法の基本概念. の値、及びω 2 の４行４列の値である。これらはベクトル. B1 , B2 の取り方によってはどんな値も取ることができる が、アフィン変換が縮小的でなければならないので、絶対 値が１以上になってはならない。. ５．Bernstein 関数曲線 まず、４次元実数空間を考える。この空間上で、曲線 B(t ) を、. (. ). {. これにより、Bernstein 関数曲線を、R 4 ;ω1 , ω 2 ; 1 , 1. 2. 2. }. B(t ) = B03 (t ), B13 (t ), B23 (t ), B33 (t ). という IFS によって表すことができた。実際に点をプロッ. と定義する。ただし、 t は媒介変数で、 0 ≤ t ≤ 1. た点 b = (b0 , b1 , b2 , b3 ) ∈ R 4 を、. トする時は、制御点のベクトル Pi により、IFS から出てき. 以後、この曲線 B(t ) を、Bernstein 関数曲線と呼ぶ。 次に、縮小写像を計算する。縮小写像が存在すると仮定 した時、仮に Bernstein 関数曲線を t = 1 で２つに分割. 3. F (b ) = ∑ bi ⋅ Pi i =0. 2. と変換して得た点 F (b ) をプロットすればよい。. すると、. ( ) (. ω1 (B(t )) = B 1 2 t ω 2 (B(t )) = B 1 2 t + 1 2. 本手法を用いて描いたベジエ曲線を図５に示す。図１のベ. ). ジエ曲線と同じ制御点を用いているため、図１と全く同じ 曲線を描いていることが見て取れる。 なお、本論文では t = 1 で２つに分割したが、これは分. 2. となるはずである。ただし、. ωi ( x ) = Ai x + Bi. 割の１例である。本手法では、任意の t で、任意の数に分. Ai は４×４の行列、 Bi は４次元列ベクトルである。. される曲線が変化することはない。. 割することが可能である。分割の位置や個数により、描画. 後はそれぞれの項の係数が合うようにアフィン変換の パラメータを決めればよい。実際に求めたアフィン変換を 次に示す。. −36− 4.
(5) となるようなアフィン変換ω1 , L, ω 4 を求めた。IFS によ って得られた双３次ベジエ曲面を図６に示す。. 図 5 IFS によるベジエ曲線 描画する時とは逆に、ベジエ曲線上の点から Bernstein 関数曲線の点への写像 F −1 ( x ) を求めることができる場合、 こ れ ら を 用 い て 、 Bernstein 関 数 曲 線 を 用 い な い. {X ; F. −1. }. o ω1 o F , F −1 o ω 2 o F , 1 , 1 を見つけること 2 2. 図 6 IFS による双３次ベジエ曲面. ができる。しかし、 F は R 4 から R 2 もしくは R 3 への 1 次. 変換であるため、その逆写像 F −1 ( x ) を一意に求めること. は困難である。. ７．おわりに 本研究は、ベジエ曲面を用いてモデリングした物体を反復. ６．ベジエ曲面への適用. 関数系(Iterated Function System : IFS)に変換し、その. 本論文で用いた手法を、双３次ベジエ曲面に適用した。. 不変測度をテクスチャとして用いることにより、物体のモ. 双３次ベジエ曲面 P(u, v ) は、１６個の制御点 Pij 、媒介変. デリングとテクスチャリングの両方を１つの IFS によって. 数 u 、 v を用いて、. IFS によるベジエ曲線の生成について扱った。. 3. 変換の方法として、４次元空間上の Bernstein 関数曲線. 3. P(u , v ) = ∑∑ B (u ) ⋅ B (v ) ⋅ Pij i =0 j =0. 3 i. 実現することを目的とした。本論文では、そのうち、主に. 3 j. を考え、 これを IFS 化し、 出てきた点を変換して描画した。 この方法は、ベジエ曲線の IFS を直接求めることができな. と定義される。ただし、 0 ≤ u, v ≤ 1. いために取られた物だが、本手法を拡張することにより、. これを、本手法に基づいて、１６次元実数空間上の曲面. 有理ベジエ曲線や他のパラメトリック曲線を IFS 化するこ. (. ). B(u , v ) = B03 (u )B03 (v ),L, B33 (u )B33 (v ). とも可能であると考えられる。. とし、. タ、及び不変測度を生成可能であることが保証されている. ( ) ω (B(u , v )) = B (1 2 u + 1 2 , 1 2 v ) ω (B(u, v )) = B (1 2 u, 1 2 v + 1 2 ) ω (B(u , v )) = B (1 2 u + 1 2 , 1 2 v + 1 2 ). ω1 (B(u , v )) = B 1 2 u, 1 2 v. また、IFS は、Collage の定理により、任意のアトラク が、そのためにいくつの縮小写像が必要なのかは明記され ていない。しかし、本手法を用いれば、任意の点で任意の 個数に分割できるため、任意の不変測度を生成することが. 2. 3. 可能であると考えられる。 今後の課題としては、 Bernstein 関数曲線を用いない IFS の導出が挙げられる。これは、前述の関数 F −1 ( x ) を何ら. 4. 5 −37−.
(6) かの方法で導出することで実現が可能である。 また、本論文の IFS によるベジエ曲線は、既存のベジエ 曲線の描画アルゴリズムよりも描画速度が遅い。これは、. 参考文献 [1]. Ebert, D., Musgrave, F., Peachey, P., Perlin, K., and. IFS のアルゴリズムに Deterministic Algorithm を用いて. Worley, S., "Texturing and Modeling: A Procedural. いるためである。一般には Chaos Game Algorithm の方が. Approach, Third Edition", with contributions from W.. 高速であるが、前述の法線ベクトルの問題により、本論文. Mark and J. Hart, Morgan Kaufmann, November 2002. では Deterministic Algorithm を使用している。しかし、. [2]. 技術編 CG 標準テキストブック , 画像情報教育振興協会. これは、Point Rendering の概念を用いることで、Chaos. [3]. M．F．Barnsley, "Fractals Everywhere"，Academic Press，. Game Algorithm を使用し、高速に描画することが可能にな ると思われる。. 1988． [4]. 本手法で導出した確率付き IFS において、Chaos Game. Restricted. Algorithm を用いる事により、テクスチャに似た効果を出 すことが可能になる。特に本手法は、任意の点で任意の個. Przemyslaw Prusinkiewicz and Mark Hammel, Iterated. Function. Systems,. Constructions, and L-systems , SIGGRAPH [5]. Language-. Przemyslaw Prusinkiewicz and Mark Hammel,. Koch. 94 Escape-time. 数の縮小写像に分割可能という特長を持つため、任意の不. Visualization Method for Language-restricted Iterated. 変測度を設計することが可能であり、柔軟なテクスチャリ. Function. Systems ,. ングができると考えられるが、具体的なテクスチャ設計方. Interface. 92, pp.213-223, 1992. 法が確立されているわけではない。そのため、不変測度の 設計手法に関する研究が必要である。 本手法では、求めた IFS コードのアフィン変換部分を変 更することにより、既存の手法では困難な、形状モデルに おける微細構造の表現が可能になると予想される。アフィ ン変換の変更によるアトラクタの変化の連続性は、 Blowing Theorem [3]によって保証されている。しかし、具 体的に、アフィン変換をどのように変更すればどのような 形状が得られるのかは、よく知られていない。 IFS は、フラクタル形状を生成する際に有効な手法であ るが、欠点として、決定論的フラクタルしか生成できず、 統計的フラクタルを生成することはできない、ということ が挙げられる。一方で、山や木など、自然物の多くは、統 計的フラクタル形状である。そのため、本手法で求めた IFS をどのように変更しても、自然物のような統計的フラクタ ル形状を生成することができない。しかし、これは、IFS に用いる変換をアフィン変換以外のものにすることで規 則性を感じにくくしたり、IFS を拡張した LRIFS[4,5]を用 いて統計的フラクタル性を持たせたりすることによって 改善することができると考えられる。. 6 」 −38−. Proceeding. of. Graphics.
(7)
図
関連したドキュメント
Furuta, Log majorization via an order preserving operator inequality, Linear Algebra Appl.. Furuta, Operator functions on chaotic order involving order preserving operator
[14.] It must, however, be remembered, as a part of such development, that although, when this condition (232) or (235) or (236) is satisfied, the three auxiliary problems above
As explained above, the main step is to reduce the problem of estimating the prob- ability of δ − layers to estimating the probability of wasted δ − excursions. It is easy to see
A monotone iteration scheme for traveling waves based on ordered upper and lower solutions is derived for a class of nonlocal dispersal system with delay.. Such system can be used
In order to be able to apply the Cartan–K¨ ahler theorem to prove existence of solutions in the real-analytic category, one needs a stronger result than Proposition 2.3; one needs
Classical Sturm oscillation theory states that the number of oscillations of the fundamental solutions of a regular Sturm-Liouville equation at energy E and over a (possibly
We study the classical invariant theory of the B´ ezoutiant R(A, B) of a pair of binary forms A, B.. We also describe a ‘generic reduc- tion formula’ which recovers B from R(A, B)
When dealing with both SDEs and RDEs, the main goals are to compute, exact or numerically, the solution stochastic process, say x(t), and its main statistical functions (mostly mean,
