コンテンツ・メディアコンテンツ メディアプログラミング実習Ⅰ

コンピュータグラフィックス編②ベジ 曲線とフラクタルベジェ曲線とフラクタル

橋本

1

今日大事なのは…今日大事なのは…

数式が出てもひるまないこと。

数式を頭で理解するのは⼤変だが それ数式を頭で理解するのは⼤変だが、それをプログラムに打ち込んで実⾏するほうが実は簡単が実は簡単。

「式」や「構造」を落ち着いて観察し、それをプログラムに落とし込もう。

2

1 ベジェ曲線1. ベジェ曲線

3

滑らかな曲線を描くアルゴリズム滑らかな曲線を描くアルゴリズムな曲線いろいろな曲線

◦ ベジェ曲線◦ ベジェ曲線◦ ファーガソン曲線◦ Bスプライン曲線◦ 有理ベジェ曲線有理ベジェ曲線◦ NURBS曲線

CADソフトやドローソフトには⼤抵なんらかCADソフトやドロ ソフトには⼤抵なんらかの曲線アルゴリズムが入っている。

Illustrator Photoshop PowerPoint ペイント etc◦ Illustrator、Photoshop、PowerPoint、ペイント、etc…4

例: Inkscapeの曲線機能例: Inkscapeの曲線機能

IllustratorやInkscapeに搭載されている曲線機能を実際に使ってみよう実際に使ってみよう。

5

ベジェ曲線とはベジェ曲線とは「制御点」と呼ばれる複数の点に基づいて定義される多項式曲線定義される多項式曲線。

フランスの⾃動⾞メーカー、ルノー社のエンジニアだったピエール・ベジェが考案ピエール・ベジェが考案。

Pierre Bézier(1910-1999)

CADの開発を⾏っていた。

6Image from http://luc.devroye.org/fonts-36362.html

(1910 1999)

ベジェ曲線はこんな線ベジェ曲線はこんな線

P1 P2

P3P0

点 P P P P を制御点と呼ぶ点 P0, P1, P2, P3 を制御点と呼ぶ。n次のベジェ曲線にはn+1個の制御点があるn次のベジェ曲線にはn+1個の制御点がある◦ 3次のベジェ曲線 ⇒ 4個の制御点

2次のベジェ曲線 ⇒ 3個の制御点7

◦ 2次のベジェ曲線 ⇒ 3個の制御点

３次ベジェ曲線の例３次ベジェ曲線の例制御点の位置を変えることによって曲げ方を制御点の位置を変えることによって曲げ方を変えることができる。

8

ベジェ曲線の数式表現ベジェ曲線の数式表現制御点 P0 P1 P2 P3 があるとき ３次の制御点 P0, P1, P2, P3 があるとき、３次のベジェ曲線は次式で表わされる。

)()()()()( 333

322

311

300 tBPtBPtBPtBPtP +++=

ここで、 は3次のバーンスタイン基底関数)(3 tBi

330 )1()( ttB −=

)(i

231

0

)1(3)(

)()(

tttB −= この関数は、制御点の位置情報をどのようにブレンドするかの

232 )1(3)( tttB −=

をどのようにブレンドするかの配合比を表わす。

9

333 )( ttB =

ベジェ曲線の性質① 端点一致性ベジェ曲線の性質① 端点一致性

P1 P2 P0 P2

P0 P3P P3P1 P3

曲線の両端は制御点P0、Pnに一致する。また P P と P P が曲線の接ベクトルとなるまた、P0 P1 と Pn-1 Pn が曲線の接ベクトルとなる。

10

ベジェ曲線の性質② 凸包性ベジェ曲線の性質② 凸包性P P2P1

P2

P3P0

P2

P3P3 P3

P0 P1

ベジェ曲線は制御点によって定義される凸包の中に完全に内包される。

凸包（とつほう）凸包（とつほう）◦ 与えられた点群を含む最小の凸形状のこと。◦ ピン群に輪ゴムをかけたときにできる図形。 11

数式を読む①数式を読む①PはそれぞれP ( )で表わされる座標値だとPiはそれぞれPi=(xi, yi)で表わされる座標値だということを踏まえると、このように書きなおせる

)()()()()( 3333 tBPtBPtBPtBPtP +++ )()()()()( 33221100 tBPtBPtBPtBPtP +++=

3333 )()()()()( 333

322

311

300 tBxtBxtBxtBxtx +++=

)()()()()( 3333 BBBB )()()()()( 333

322

311

300 tBytBytBytByty +++=

12

数式を読む②数式を読む②)()()()()( 3

333

223

113

00 tBxtBxtBxtBxtx +++=)()()()()( 3333 BBBB )()()()()( 3

333

223

113

00 tBytBytBytByty +++=

(t)って何だ？( ) て何だ◦ 媒介変数表示。パラメータ表示とも呼ぶ。t は ろ ろな値をとる ここでは t 0 1◦ t はいろいろな値をとる。ここでは t = 0〜1◦ この式に t=0, t=0.1, t=0.2, … t=1.0 と代入式 , , , と代入していくと、曲線を構成する点群になる。⇒ for文でやればいい！

13

⇒ for文でやればいい！

実装をイメージしようf (fl t t 0 t 1 0 t 0 01) {

実装をイメージしようfor (float t=0; t<1.0; t+=0.01) {

330 )1()( ttB −=

231

0

)1(3)(

)1()(

tttB

ttB

−=

33

232

)(

)1(3)( tttB −=

)()()()()( 3333 tBxtBxtBxtBxtx +++=

333 )( ttB =

)()()()()( 33221100 tBxtBxtBxtBxtx +++=)()()()()( 3

333

223

113

00 tBytBytBytByty +++=point( , );

})(tx )(ty

}14

実装をイメージしよう2f (fl t t 0 t 1 0 t 0 01) {

実装をイメージしよう2for (float t=0; t<1.0; t+=0.01) {

330 )1( tB −=

231

0

)1(3

)1(

ttB

tB

−=

33

232 )1(3 ttB −=

3333 BxBxBxBxx +++=

333 tB =

33221100 BxBxBxBxx +++=3

333

223

113

00 ByByByByy +++=point( , );

}x y

}15

課題① bezierCurve1課題① bezierCurve1前述 数式をもと 次 曲線前述の数式をもとに、３次ベジェ曲線を描くプログラムを作成せよ。を描くプログラムを作成せよ。

制御点の例P0 : (75 260)◦ P0 : (75, 260)◦ P1 : (170, 120)◦ P2 : (350, 90)P3 : (500 200)◦ P3 : (500, 200)

16

課題② bezierCurve2課題② bezierCurve2各制御点をマウスカ ソルでひ ぱ て移動で各制御点をマウスカーソルでひっぱって移動できるように改良し、制御点の配置によってベジェ曲線がどうなるか確認せよ。

点の近くでマウスボタンを押して、そのままドラッグすると点が移動。

17

点の近くで ウスボタンを押して、そのままドラッグすると点が移動。好きな場所でマウスボタンを離すと、そこで点が留まる。

課題② ヒント課題② ヒント点を移動させるには？

「点の近くにカ ソルがあって マウスボタ◦ 「点の近くにカーソルがあって、マウスボタンが押されている」状態を判定しよう。

◦ その状態のときに カーソルに点がついてい◦ その状態のときに、カ ソルに点がついていくようにすれば良い。

◦ マウスボタン押下状態は mousePressed とマウスボタン押下状態は mousePressed という論理型変数（true/false）で判定できる。

18

2 フラクタル2. フラクタル

19

フラクタルとはフラクタルとはフラクタル（Fractal）

⾃己相似性を持つ図形のこと◦ ⾃己相似性を持つ図形のこと

自己相似性縮尺を変え も全体と部分の形状が相似◦ 縮尺を変えても全体と部分の形状が相似の関係にあること。◦ 「⾃分の中に⾃分がいて、さらにその中にも⾃分が…」という構造にも⾃分が 」という構造

20

有名なフラクタル図形有名なフラクタル図形

マンデルブロ集合 シェルピンスキー角形の三角形

コ ホ曲線コッホ曲線

21Image from http://ja.wikipedia.org/wiki/マンデルブロ集合

自然界に潜むフラクタル自然界に潜むフラクタル海岸線（リアス式海岸）海岸線（リアス式海岸）毛細血管毛細血管植物の葉や茎

ロマネスコシダ植物

22（カリフラワーの一種）

Image from http://ja.wikipedia.org/wiki/シダ植物, http://ja.wikipedia.org/wiki/ロマネスコ

フラクタルの応⽤例フラクタルの応⽤例F t l C dFractal Codes◦ ⾃己相似性を持つ２次元コード⾃己相似性を持つ２次元コ ド◦ カメラで撮るときに一部分が欠けていても、内部に同じパタ ン構造があるので認識できる部に同じパターン構造があるので認識できる。

23綾塚 祐二, “Fractal Codes: ⾃己相似的に配置される二次元コード”, WISS2006, pp.101-106

フラクタルな木を描くフラクタルな木を描く図 よ な木を描く方法を考 よ図のような木を描く方法を考えてみよう。

24

考えるポイント考えるポイント繰り返 な ブ クがど繰り返しになっているブロックがどの部分かを⾒抜く。部分かを⾒抜く。

これが最小単位

25

木を描くアルゴリズム木を描くアルゴリズム

①原点から上方向に⻑さLの線を描く。

②原点から上方向にLだけ平⾏移動する。②原点から上方向にLだけ平⾏移動する。+40°-40°

③その位置で ＋40度回転した後、そこを起点に⻑さL/2の線を描く

③④そこを起点に⻑さL/2の線を描く。

②④その位置で －40度回転した後、

そこを起点に⻑さL/2の線を描く。 ①そこを起点に⻑さL/2の線を描く。26

①

木を描くプログラム木を描くプログラムvoid setup() {size(400,400);t k W i ht(2)

void drawTree(float length) {if ( length < 1 ) {

tstrokeWeight(2);}

return;}

void draw() {translate( width/2, height );drawTree(200);

line( 0, 0, 0, -length );translate(0, -length);

drawTree(200);} pushMatrix();

rotate(radians(40));drawTree( length/2 );drawTree( length/2 );

popMatrix();

pushMatrix();pushMatrix();rotate(radians(-40));drawTree( length/2 );

i ()(!) プログラムをよく読んでどのよう

27

popMatrix(); }

( ) プ グラムをよく読んでどのように動作しているか考えてみよう。

再帰的アルゴリズム再帰的アルゴリズム関数 中 ⾃分⾃身を呼び出す構造関数の中で⾃分⾃身を呼び出す構造

void drawTree(…) {( ) {

……

drawTree(…); drawTree()の中でdrawTree()が呼ばれ、さらにその中でまたdrawTree()が呼ばれ と延々} drawTree()が呼ばれ…と延々繰り返される

28

再帰的アルゴリズムでの注意再帰的アルゴリズムでの注意再帰において重要なのはル プの「脱出条件」再帰において重要なのはループの「脱出条件」◦ これがきちんと仕掛けられてないと無限ループに陥って

しまうしまう。

void drawTree(float length) {

if ( length < 1 ) { これがループの脱出条件 枝のif ( length < 1 ) {return; // 脱出！

}

これがル プの脱出条件。枝の長さが１未満になったら、そのタイミングで関数を脱出する。

……d T ( l th/2 )drawTree( length/2 );……

29

drawTree( length/2 ); }

課題③ KochCurve課題③ KochCurveホ曲線を描くプ グ を作成 よコッホ曲線を描くプログラムを作成せよ。

30

課題③ ヒント課題③ ヒント

④⑥⑤ ⑦

①

④⑩

⑦

①

② ③⑧

③

⑨L/3 ⑨

L31

フラクタルのプログラムを作るコツ手順① 基本要素だけを描く関数を作るまずは再帰構造のことは意識せずに「基本要素だけを描く関数」まずは再帰構造のことは意識せずに「基本要素だけを描く関数」を作ってみる。この時、引数で要素の⼤きさを指定できるようにしておく。

void drawTree(float length) {

しておく。

line( 0, 0, 0, -length );translate(0, -length);

pushMatrix();rotate(radians(40));line( 0 0 0 -length/2 );line( 0, 0, 0, length/2 );

popMatrix();

pushMatrix();pushMatrix();rotate(radians(-40));line( 0, 0, 0, -length/2 );

popMatrix();

32

p p ();}

フラクタルのプログラムを作るコツ

先ほど作 た関数内で⾏われている描画処理のうち 再帰的

手順② 再帰構造にする

先ほど作った関数内で⾏われている描画処理のうち、再帰的な分割処理が発⽣する部分を再帰呼び出し（⾃分⾃身を呼び出す）に置き換える

void drawTree(float length) {

出す）に置き換える。

void drawTree(float length) {( g ) {

line( 0, 0, 0, -length );translate(0, -length);

( g ) {

line( 0, 0, 0, -length );translate(0, -length);

pushMatrix();rotate(radians(40));li ( 0 0 0 l h/2 )

pushMatrix();rotate(radians(40));d T ( l h/2 )line( 0, 0, 0, -length/2 );

popMatrix();

p shMat i ()

drawTree( length/2 );popMatrix();

p shMat i ()pushMatrix();rotate(radians(-40));line( 0, 0, 0, -length/2 );

popMatrix();

pushMatrix();rotate(radians(-40));drawTree( length/2 );

popMatrix();

33

popMatrix(); }

popMatrix(); }

フラクタルのプログラムを作るコツ手順③ 再帰の脱出条件を設定する

このままでは再帰処理が無限に⾏われてしまうので、それを防ぐために「要素の⼤きさが 定

void drawTree(float length) {

ぐために「要素の⼤きさが一定値以下になったら処理をしない」という仕組みを１⾏目に書

if ( length < 1 ) {return;

}い」という仕組みを１⾏目に書き加える。 line( 0, 0, 0, -length );

translate(0, -length);

これで完成！ pushMatrix();rotate(radians(40));d T ( l th/2 )drawTree( length/2 );

popMatrix();

pushMatrix();pushMatrix();rotate(radians(-40));drawTree( length/2 );

popMatrix();

34

popMatrix(); }