グラフィックスの基礎

はじめに

グラフィクスライブラリ

グラフィクス，あるいはコンピュータ・グラフィクスという言葉からみなさんは何をイメージするでしょうか？おそらく多くの人はテレビゲームやアニメーション映画に使われている三次元のグラフィックスのことをイメージするのではないかと思います．グラフィクスという言葉は広い意味ではこういった三次元のグラフィクスだけではなく，写真のような二次元画像のことも広く包括しますが，今回の講義では，まさにみなさんのイメージにある三次元のグラフィクスを扱いたいと思います．

ただ，残念なことに，C言語にはグラフィクスを利用するための標準的な関数は用意されていません．それ故，汎用的なＣ言語の教科書を買っても，グラフィクスのことは書かれていません (とはいっても，他の言語，例えば標準的な二次元，三次元グラフィクスのライブラリを持つJavaでもグラフィクスのことに触れている例は少ないとは思います)．

そのため，C言語においてグラフィクスを利用する際には，別途，何らかのグラフィクスライブラリを用意する必要があります．現在，三次元グラフィクスを扱うためのライブラリには，この講義で扱うOpenGLの他にも，Microsoftが開発をしており，Windows上でのみ動作するDirectX，Appleが開発しておりMac上でのみ動作するMetal，そしてOpenGL同様にOSに依存せずに動くことを目指したVulkanなどがあります．

OpenGLはここにあげた3つの中で比較的早期に開発が開始されており，そのため機能は他の三つには劣るものの，比較的プログラミングがしやすく，研究や開発の現場で以前広く使われています．それでは，早速OpenGLについて詳しく見ていきたいと思います．

OpenGL

OpenGL は元々 シリコングラフィクス社（SGI）が開発していた三次元グラフィクスライブラリです．残念ながら，シリコングラフィックス社はすでに倒産しており，現在はKhronos Groupという非営利団体によって管理されています．厳密にはOpenGLはライブラリではなく，三次元グラフィクスをコンピュータ上で動かすための仕様書のようなもの(実はC言語もそれに近い)で，実際の開発はIntel, NVIDIA, AMDといったCPUやグラフィックスカードの開発会社によって行われています．ただ，OpenGLは仕様書であるがゆえに，こういった会社が作っている演算装置上でOSやハードウェアの違いに依存することなく，ほぼ同じ動作をします(ぼぼ，というのは言葉通りの意味で，込み入った機能は違う動作をすることもある)．

現在，最先端のコンピュータグラフィックスはOpenGLから，よりハードウェアの性能を引き出しやすい (その代わりにプログラミングが大変な) ライブラリであるVulkan, DirectX, Metalなどに，その役割を受け継ぎつづありますが，それでもOpenGLを学ぶことは，基本的なコンピュータ・グラフィクスの仕組みを理解する上でとても重要です．

ここまで，OpenGLは三次元グラフィクスのライブラリである，という話をしてきましたが，いきなり三次元の物体を画面に描画するのは，少しハードルが高いため，まずは二次元グラフィクスの描画から徐々にOpenGLの使い方に慣れていきましょう．．

まず初めに，OpenGLの簡単な例を示します．以下の例に示すように，OpenGL の関数は全て glXXXXXX というように関数名の頭に “gl” の２文字がつきます．例えば，OpenGL で直線を描画したければ，プログラムの冒頭で，

#include <GL/gl.h>

のようにOpenGLのヘッダをインクルードした上で，

glBegin(GL_LINES);
glVertex2d( x0, y0 );
glVertex2d( x1, y1 );
glEnd();

のように書くと (x0, y0) と (x1, y1) を結んだ直線が描かれます．

GLUT (OpenGL Utility Toolkit)

さて，OpenGLでは上記のような比較的単純なコードで直線等を描画できますが，この直線はどこに描画されるのでしょうか？

これまでprintfなどを用いて文字を表示する場合には，コマンドプロンプトの中に表示されていました．しかし，コマンドプロンプトは文字しか表示できないので，この上に写真のようなグラフィクスを描画することはできません(アスキーアートのようなものなら可能ですが)．

そのため，OpenGLによって何かを描画するためには，その描画先となるウィンドウを別途用意しなくてはなりません (前回の演習課題を思い出してみてください．プログラムを実行すると，新しいウィンドウが開いたはずです)．このようなウィンドウは例えばWindowsであれば，Windows APIとよばれるライブラリの一種を用いて非常に複雑なコードを書かなければなりません．その上，そこで作成したWindows上のプログラムはMacの上では動かないため，Macでも動かそうと思うと，今度はCocoaというMac用の別のライブラリを使う必要が出てきます．

OpenGLは，特定のOSやウィンドウシステムに依存しないように汎用的に設計されています．そのため，ウィンドウを開いたり，閉じたり，あるいは，マウスからの入力を受け付けたりといった処理がOSに依存していては，せっかくのOpenGLの汎用性（あらゆるOS環境で同様に使えるという汎用性）が台無しです．

そこで，OpenGLには補助的なライブラリとして，ウィンドウやマウスの制御を行うための OpenGL Utility Toolkit (GLUT) というライブラリが用意されています．このGLUTを用いてプログラミングを行うと，OSやウィンドウシステムに全く依存しないプログラムを書くことが可能になります（例えば，この授業で書くプログラムは，Cygwin以外にも，通常のWindowsや Mac，Linuxの上でも，ソースファイルを改変することなしに動作します(ただしMakefileを含むコンパイルやリンクの方法は多少変更が必要)．

ちなみに2020年現在，GLUTはすでに開発が止まっており，その機能の多くは後継のライブラリであるFreeGLUTに受け継がれています．FreeGLUTは例えばGLUTの時代にはなかったマウスホイールを扱う関数など，多くの機能が新しく実装されています．ただ，残念なことに，そのFreeGLUTでさえも，ライブラリの設計はやや古くなってきており，現在はGLFWなどの，よりモダンなライブラリが使われることが多くなってきています．

ただ，これらのモダンなライブラリであっても，考え方は共通しているため，本講義ではやや煩雑な導入手続きが必要ないGLUTを使ってプログラムを作成していきます．

GLUTの簡単な例

GLUT を使った簡単なプログラムを次に示します．GLUT を利用するには，プログラムの冒頭で <GL/glut.h> をインクルードします．OpenGLの関数は頭に”gl”がつきましたが，GLUTの関数は全て頭に “glut” がつきます．


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#ifndef __APPLE__  // OSがMacでない (= WindowsやLinux)
#include <GL/glut.h>  // Windows, Linuxの場合のヘッダ
#else
#include <GLUT/glut.h>  // Macの場合のヘッダ
#endif

int WINDOW_WIDTH = 500;   // ウィンドウの横幅
int WINDOW_HEIGHT = 500;  // ウィンドウの高さ

// OpenGLの描画に使う関数
void display() {    
    // 画面を決まった色で塗りつぶす(詳しくは「背景色を描画」を参照)
    glClearColor(1.0f, 1.0f, 0.0f, 1.0f);
    glClear(GL_COLOR_BUFFER_BIT);

    // 表示内容を更新
    glFlush();    
}

int main(int argc, char **argv) {
    // GLUTの初期化
    glutInit(&argc, argv);
    // ウィンドウのサイズを設定
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    // ウィンドウの作成 (引数はウィンドウのタイトル)
    glutCreateWindow("First GLUT program");
    // 描画に使う関数 (コールバック関数) の登録
    glutDisplayFunc(display);
    // 描画ループの開始
    glutMainLoop();
}

さて，このプログラムを入力し，コンパイルしてみましょう．通常のコンパイル（＆リンク）の仕方は，プログラムファイル名をtest.cとすると，

# Cygwinの場合
gcc test.c -lglut -lglu32 -lopengl32
# MSYS2の場合
gcc test.c -lfreeglut -lglu32 -lopengl32

です．

Macを使っている方は，下記でコンパイルをします．

gcc -framework OpenGL -framework GLUT test.c

注意 Macの場合にはOpenGLをコンパイル時に大量にwarningが発生します．エラー(warningではなく)がなければ問題ありませんが，気になる場合には，以下のように GL_SILENCE_DEPRECATION というマクロを定義してください．

gcc -framework OpenGL -framework GLUT -DGL_SILENCE_DEPRECATION test.c

注意コンパイルオプションの付け方は，設定環境やコンパイラにより異なります．上記は最新のCygwinを使う場合の例ですが，一部の古い環境では

gcc test.c -lglut -lglu -lgl

のようになる可能性もあります．

作成される a.out (あるいは a.exe) ファイルの実行には，これまでの補間や微分方程式の課題で行なったものと同様にX Windowを起動しておく必要があります (MSYS2やMacの場合には特に必要ありません)．

Cygwinのターミナルから startxwin と入力すると，下図のように，画面右下の通知領域トレイに”X”のアイコンが現れます．このアイコンを右クリックして，Applications中にxtermがあるかを確認してください (クリックすると下の図が拡大されます)．

もしxtermが見つかった場合には，それをクリックすることで背景が白いターミナルが出てくるので，そのターミナル上でプログラムを実行します．

./a.out

一方，上記の操作でApplicationsが現れない場合には，少し待つと，下図のような緑色の背景を持つ”X”のアイコンが別に現れます．この場合は，このアイコンを右クリックして「システムツール」→「Cygwin Terminal」を続けてクリックします．すると，今までとは別のCygwinのターミナルが開くので，このターミナル上で上記のように ./a.out を実行します．

うまく動作すると，以下のように画面全体が黄色く塗りつぶされたウィンドウが出てきます．

GLUTによるグラフィックスプログラミング

GLUTのプログラムの流れ

GLUTにおけるプログラムの流れは，

GLUT を初期化する（glutInit）
グラフィクス描画用のウィンドウを開く（glutCreateWindow）
ウィンドウにグラフィクスを描画する関数を決める（glutDisplayFunc）
無限ループに入って，イベントが起こるのを待つ（glutMainLoop）となります．

glutMainLoop() を実行すると，プログラムの処理はGLUTの内部関数に引き渡され，プログラム処理は main 関数には戻ってきません． glutMainLoop()の実行後はGLUT内部で，常にウィンドウ等の状況を監視し，画面を描画するべきイベントが起こるごとに，あらかじめ登録された描画関数（上記の例では display）を呼び出して描画を行わせる仕組みになっています．

さて，上で述べた 画面を描画するべきイベントとは何かというと，例えば，

ウィンドウが新たに開かれた
ウィンドウのサイズが変わった
ウィンドウが他のウィンドウに隠された後，再び表に表れた．

などが該当します．

上記のサンプルでは，display 関数の中身が空っぽなので，これらのイベントが起こっても画面には何も描画されませんが，とりあえず，実際に上記のプログラムを実行して，これらのイベントを起こしてみましょう (単純にprintfで何かを出力するだけでもdisplayが呼ばれていることは分かる)．

直線の描画

では，次に，直線を描画してみましょう．先ほどのプログラムを次のように書き換えてください (コピー&ペーストでも動きますが，最初のうちは自分で書くことを推奨します)．


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#ifndef __APPLE__  // OSがMacでない (= WindowsやLinux)
#include <GL/glut.h>  // Windows, Linuxの場合のヘッダ
#else
#include <GLUT/glut.h>  // Macの場合のヘッダ
#endif

int WINDOW_WIDTH = 500;   // ウィンドウの横幅
int WINDOW_HEIGHT = 500;  // ウィンドウの高さ

void display() {
    // ウィンドウ表示内容のクリア
    glClear(GL_COLOR_BUFFER_BIT);
    
    // 直線の描画 (glFlushを忘れないこと)
    glBegin(GL_LINES);
    glVertex2d(150.0, 150.0);
    glVertex2d(350.0, 350.0);
    glEnd();
    glFlush();
}

void reshape(int width, int height) {
    // OpenGLウィンドウの描画範囲を設定
    // 下記は描画範囲が[0, width] x [0, height]となるように設定している
    glViewport(0, 0, width, height);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, (double)width, 0.0, (double)height);
    WINDOW_WIDTH = width;
    WINDOW_HEIGHT = height;
}

int main(int argc, char **argv) {
    // GLUTの初期化
    glutInit(&argc, argv);
    // ウィンドウのサイズを設定
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    // ウィンドウの作成 (引数はウィンドウのタイトル)
    glutCreateWindow("First GLUT program");
    // 描画に使う関数の登録
    glutDisplayFunc(display);
    // ウィンドウのサイズ変更時に呼ばれる関数の登録
    glutReshapeFunc(reshape);
    // 描画ループの開始
    glutMainLoop();
}

display 関数に触れる前に，簡単にreshape 関数について説明します．この関数はGLUTによってウィンドウが開いた時と，ユーザがウィンドウサイズを変更した時に呼ばれる関数です．display 関数と同様に main 関数の中で glutReshapeFunc を用いて reshape という関数名が指定されています．中身についての説明は煩雑になるので，詳しくは述べませんが，端的には gluOrtho2D 関数を用いてウィンドウに映る座標範囲を $[0, \text{width}] \times [0, \text{height}]$ となるように設定しています (右下が原点)．

上記の reshape 関数の中での座標範囲の設定を受けて display 関数内では，直線の始点と終点の座標を指定しています．ウィンドウ左下を (0, 0) として，ピクセル単位で与えます．ただし，これはあくまで現在のreshape 関数の設定がそのようになっているためで，設定なしにそうなるわけではないことは覚えておいてください．

display 関数の最初に出てくる glClear(GL_COLOR_BUFFER_BIT) というのは，カラーバッファ，すなわち現在画面に描画されている色を何らかの色でクリアする (塗りつぶす) ことを意味しています．これについては，後ほど課題でも少し動作を確認します．

また display 関数の最後に出てくる glFlush() というのは，それまでに実行したOpenGLコマンドの結果を，実際に画面表示に反映させるための関数です．OpenGLは，内部ではいくつかの命令が溜まってから，まとめて実行するようになっているので，描画結果を反映するためにも display 関数の最後では glFlush() を呼ぶのを忘れないようにしてください．

さて，上記プログラムをコンパイルして実行してみると，以下の図のようにウィンドウの中程に白い直線が表れたはずです．ウィンドウを移動したり，一度隠してから表に出したりしてみましょう．毎回，ウィンドウの中程に，白い直線が再描画されるのがわかります．

MacOS Catalinaを使う場合の注意

MacOS 10.15 (Catalina)を使っている場合には，画面の左下にしか物が描画されないようです．その場合には上記のプログラムの中で reshape 関数内にある glViewport(0, 0, width, height); という行を以下のように変更して下さい．

変更前

glViewport(0, 0, width, height);

変更後

glViewport(0, 0, width * 2, height * 2);

背景色を変える

先ほどの説明で glClear(GL_COLOR_BUFFER_BIT) が画面を塗りつぶす処理であることを説明しました．先ほどの例では画面が黒く塗りつぶされて，その上に白い線が描かれていましたが，この塗りつぶしの色を変更することも可能です．

プログラムを以下のように書き換えてみましょう．


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#ifndef __APPLE__  // OSがMacでない (= WindowsやLinux)
#include <GL/glut.h>  // Windows, Linuxの場合のヘッダ
#else
#include <GLUT/glut.h>  // Macの場合のヘッダ
#endif

int WINDOW_WIDTH = 500;   // ウィンドウの横幅
int WINDOW_HEIGHT = 500;  // ウィンドウの高さ

void init() {
    glClearColor(0.0, 0.0, 1.0, 1.0);
}

void display() {
    // ウィンドウ表示内容のクリア
    glClear(GL_COLOR_BUFFER_BIT);
    
    // 直線の描画 (glFlushを忘れないこと)
    glBegin(GL_LINES);
    glVertex2d(150.0, 150.0);
    glVertex2d(350.0, 350.0);
    glEnd();
    glFlush();
}

void reshape(int width, int height) {
    // OpenGLウィンドウの描画範囲を設定
    // 下記は描画範囲が[0, width] x [0, height]となるように設定している
    glViewport(0, 0, width, height);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, (double)width, 0.0, (double)height);
    WINDOW_WIDTH = width;
    WINDOW_HEIGHT = height;
}

int main(int argc, char **argv) {
    // GLUTの初期化
    glutInit(&argc, argv);
    // ウィンドウのサイズを設定
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    // ウィンドウの作成 (引数はウィンドウのタイトル)
    glutCreateWindow("First GLUT program");
    // 描画に使う関数の登録
    glutDisplayFunc(display);
    // ウィンドウのサイズ変更時に呼ばれる関数の登録
    glutReshapeFunc(reshape);
    // OpenGLの初期化処理  (これはコールバック関数ではないので直接呼び出す)
    init();
    // 描画ループの開始
    glutMainLoop();
}

ここでは，諸々の初期設定を行うために，void init() という関数を用意しました．これは，OpenGLやGLUTとは関係なく，見やすさのために初期設定を一つの関数にまとめただけです (つまりコールバック関数ではない)．

この関数の中で呼び出している glClearColor という関数によって glClear する際の色（＝背景色）を設定することができます． glClearColor の1番目，2番目，3番目の引数が，それぞれ，赤，緑，青の3原色に対応しており，それぞれに0から1までの値をセットすることができます．ここでは色の表現法の話について詳しく言及することは避けますが，今回の例では青の成分だけが1になっているので，画面の背景が青色で塗りつぶされています．

なお4番目の引数は色の不透明度(0は透明，1は不透明)を表すものですが，今回の設定では透明度は表現できないので今回1単に1を入れておいてください．正しくプログラムが実行できると，以下のような画面が出力されるはずです．

線の色を変える

次に，線の色を変えてみましょう．先ほどは glClearColor 関数を使って背景を塗りつぶす色を指定しましたが，描画する色を指定する場合には glColor3d 関数を使います． display 関数を次のように書き換えます．

void display(void) {
    // ウィンドウの表示内容のクリア
    glClear(GL_COLOR_BUFFER_BIT);

    // 描画色の指定
    glColor3d(1.0, 0.0, 0.0);

    // 直線の描画 (glFlushを忘れないこと)
    glBegin(GL_LINES);
    glVertex2d( 100, 100 );
    glVertex2d( 200, 200 );
    glEnd();
    glFlush();
}

glColor3d の３つの引数が，赤，緑，青の３原色に対応しているのは，先ほどの glClearColor の場合と同じです．なお glColor3d により描画色をセットすると，それ以降に実施される OpenGL 命令は全てセットした色で実行され，新たに色をセットし直さない限り，描画色は変わりません．

練習課題

glColor3d は glBegin と glEnd の間で呼び出すこともできます．これによって直線の視点と終点を異なる色で指定すると何が起こるでしょうか？

いろいろな図形の描画

では，直線以外にも，いろいろな図形を描いてみましょう．

void display() {
    // ウィンドウ表示内容のクリア
    glClear(GL_COLOR_BUFFER_BIT);

    // 赤い線
    glColor3d(1.0, 0.0, 0.0);
    glBegin(GL_LINES);
    glVertex2d(150, 150);
    glVertex2d(350, 350);
    glEnd();

    // 青い線 (一筆書き)
    glColor3d(0.0, 0.0, 1.0);
    glBegin(GL_LINE_STRIP);
    glVertex2d(40, 400);
    glVertex2d(160, 300);
    glVertex2d(240, 480);
    glVertex2d(80, 460);
    glVertex2d(80, 240);
    glEnd();

    // 白い三角形
    glColor3d(1.0, 1.0, 1.0);
    glBegin(GL_TRIANGLES);
    glVertex2d(40, 240);
    glVertex2d(100, 60);
    glVertex2d(140, 180);
    glEnd();

    // 緑の長方形
    glColor3d(0.0, 1.0, 0.0);
    glRectd(360, 40, 400, 80);

    // 太い線 (太さを戻すのを忘れないこと)
    glColor3d(1.0, 0.0, 0.0);
    glLineWidth(5.0);
    glBegin(GL_LINES);
    glVertex2d(200, 400);
    glVertex2d(400, 200);
    glEnd();
    glLineWidth(1.0);

    glFlush();
}

正しくプログラムが実行されると以下のような画面が表示されます．

それでは，実際に関数の中身をみていきます．

一筆書きのように，複数の点を連結した折れ線を描くには，

glBegin(GL_LINE_STRIP);
glVertex2d(..., ...);  // 頂点1
glVertex2d(..., ...);  // 頂点2
glVertex2d(..., ...);  // 頂点3
// 以下あるだけ並べる
...
glEnd();

のように glBegin に GL_LINES ではなく GL_LINE_STRIP を指定します． GL_LINES では入力された頂点2つごとに間に直線を入れていくのに対し GL_LINE_STRIP は入力された全ての点を順に繋いでくれます．

三角形を描くには，

glBegin(GL_TRIANGLES);  
glVertex2d(..., ...);  // 頂点1
glVertex2d(..., ...);  // 頂点2
glVertex2d(..., ...);  // 頂点3
glEnd();

とします．これにより，３つの頂点を結ぶ三角形が描画されます．

さらに，（上記の例にはありませんが）四角形以上の多角形を描くには，

glBegin(GL_POLYGON);  
glVertex2d(..., ...);  // 頂点1
glVertex2d(..., ...);  // 頂点2
glVertex2d(..., ...);  // 頂点3
// 以下あるだけ並べる
...
glEnd();

というやり方もあります (四角形なら GL_QUADS でも大丈夫)．これにより，指定された頂点を結ぶ多角形（＝ポリゴン）が描画されます．ただし，指定した多角形が凹型の場合，正しく描画が行われません．凹型の多角形を描画したい場合には，複数の凸型多角形に分割して描画することが必要です．

また，四角形は，多角形の一つとして描画することもできますが，各辺が座標軸に垂直・平行な長方形の場合には，次の関数一つで描画できます．

glRectd(x0, y0, x1, y1);

これにより $(x_0, y_0), (x_0, y_1), (x_1, y_0), (x_1, y_1)$ の4点を頂点とする長方形が描かれます．

また，描画する線の太さを変えることもできます．

glLineWidth(5.0);

とすると，それ以降に描画される線の太さが 5ピクセルに設定されます（初期設定では 1ピクセル）．

色の設定の場合と同じく，線の設定についても，新たに線の太さが再設定されるまで，設定内容は有効です．そのため，上記のプログラムでは太くしたい直線を描画したのち glLineWidth(1.0) と書いて，太さを元の1ピクセル幅に戻しています．

その他，点 (正方形) を打ちたければ，

glBegin(GL_POINTS);
glVertex2d(..., ...);  // 頂点1
glVertex2d(..., ...);  // 頂点2
glVertex2d(..., ...);  // 頂点3
// 以下あるだけ並べる
...
glEnd();

とします．点の大きさは，

glPointSize(3.0);

として変更できます (この例は，点の縦横の大きさが3.0ピクセルになる)．

課題1 (配点：4点)

自分の名前のイニシャル文字を，直線・三角形・四角形などを利用して画面にグラフィクスとして描画せよ．

作品例

いろいろなグラフィクス要素を使いこなしてもらうことが目的なので，各自，工夫して面白い絵を描くこと．背景色などにも変化を持たせても良い．最低3種類以上の図形要素を利用すること．

なお，上記の例では，各文字と記号を一つの関数としてまとめて利便性の向上を図っている．全てのdisplay 関数の中に書くのではなく，適宜関数化して，分かりやすいソースコードとなるように努めること．

マウスイベント

GLUT では，マウスから何らかの入力が生じた（＝マウスイベントが発生した）際に呼び出されるべき関数をあらかじめ登録しておくことで，マウスを使ったプログラムを作成することができます．

マウスイベントを取り扱う関数を登録するには，コールバック関数として

void mouse(int button, int state, int x, int y);

のような引数を持つ関数 (名前はmouseでなくても良い)を作成し display などと同様に，

glutMouseFunc(mouse);

として，コールバック関数を登録します．

例として，マウスでクリックしたボタンとその位置をprintfで書き出すようなプログラムは以下のようになります．


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#ifndef __APPLE__  // OSがMacでない (= WindowsやLinux)
#include <GL/glut.h>  // Windows, Linuxの場合のヘッダ
#else
#include <GLUT/glut.h>  // Macの場合のヘッダ
#endif

#include <stdio.h>

int WINDOW_WIDTH = 500;   // ウィンドウの横幅
int WINDOW_HEIGHT = 500;  // ウィンドウの高さ

void init() {
    glClearColor(0.0, 0.0, 0.0, 1.0);
}

void display() {
    // ウィンドウ表示内容のクリア
    glClear(GL_COLOR_BUFFER_BIT);    
    glFlush();
}

void reshape(int width, int height) {
    // OpenGLウィンドウの描画範囲を設定
    // 下記は描画範囲が[0, width] x [0, height]となるように設定している
    glViewport(0, 0, width, height);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, (double)width, 0.0, (double)height);
    WINDOW_WIDTH = width;
    WINDOW_HEIGHT = height;
}

void mouse(int button, int state, int x, int y) {
    switch (button) {
    case GLUT_LEFT_BUTTON:
        printf("Left button was ");
        break;
    case GLUT_MIDDLE_BUTTON:
        printf("Middle button was ");
        break;
    case GLUT_RIGHT_BUTTON:
        printf("Right button was ");
        break;
    }

    switch (state) {
    case GLUT_DOWN:
        printf("pushed at %d %d\n", x, y);
        break;
    case GLUT_UP:
        printf("released at %d %d\n", x, y);
        break;
    }
    fflush(stdout);
}

int main(int argc, char **argv) {
    // GLUTの初期化
    glutInit(&argc, argv);
    // ウィンドウのサイズを設定
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    // ウィンドウの作成 (引数はウィンドウのタイトル)
    glutCreateWindow("First GLUT program");
    // 描画に使う関数の登録
    glutDisplayFunc(display);
    // ウィンドウのサイズ変更時に呼ばれる関数の登録
    glutReshapeFunc(reshape);
    // マウス操作時に呼ばれる関数の登録
    glutMouseFunc(mouse);
    glutReshapeFunc(reshape);
    // OpenGLの初期化処理  (これはコールバック関数ではないので直接呼び出す)
    init();
    // 描画ループの開始
    glutMainLoop();
}

上記のプログラムを実際に実行してみるとわかる通り，マウスのボタンが押されるか，離されると mouse 関数が呼び出されます． mouse 関数の引数には，

引数 button に，押された（あるいは，離された）ボタンの種類
(GL_LEFT_BUTTON, GL_MIDDLE_BUTTON, GL_RIGHT_BUTTON のいずれか)
引数 state に，押された(GLUT_DOWN)のか，あるいは，離された(GLUT_UP)のか
引数 x ，y に押された（あるいは，離された）ときの，マウス座標

がそれぞれ渡されています．

ただし，渡されるマウス座標は，ウィンドウ左上を (0,0)，ウィンドウ右下を (ウィンドウ幅，ウィンドウ高さ) としたピクセル値 であり，しかも glVertex2d で指定した位置が reshape 関数内の指定に依存する一方，こちらのマウス座標は，ウィンドウのサイズだけに依存し reshape 関数内の指定とは関係がありません．

もし，これを描画座標に一致させたければ，描画座標系とマウス座標系の関係を頭に描きつつ，何らかの変換を施す必要があります．具体例を以下に示します．この例では，マウス左ボタンで押下した場所を最大5つまで覚えておいて，その場所に点を打ちます．なお，以下の例では，以後の課題のヒントとなるよう，あえて点の座標を保存するために matrix 型を使っています．


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#ifndef __APPLE__  // OSがMacでない (= WindowsやLinux)
#include <GL/glut.h>  // Windows, Linuxの場合のヘッダ
#else
#include <GLUT/glut.h>  // Macの場合のヘッダ
#endif

#include <stdio.h>
#include "matrix.h"

#define MAX_POINTS 5

int WINDOW_WIDTH = 500;   // ウィンドウの横幅
int WINDOW_HEIGHT = 500;  // ウィンドウの高さ

int n_points;
matrix points;

void init() {
    glClearColor(0.0, 0.0, 0.0, 1.0);
    mat_alloc(&points, MAX_POINTS, 2);
    n_points = 0;
}

void display() {
    // ウィンドウ表示内容のクリア
    glClear(GL_COLOR_BUFFER_BIT);

    // 点をあるだけ描く
    glPointSize(10.0);
    glBegin(GL_POINTS);
    for (int i = 0; i < n_points; i++) {
        const double x = mat_elem(points, i, 0);
        const double y = mat_elem(points, i, 1);
        glVertex2d(x, y);
    }
    glEnd();

    glFlush();
}

void reshape(int width, int height) {
    // OpenGLウィンドウの描画範囲を設定
    // 下記は描画範囲が[0, width] x [0, height]となるように設定している
    glViewport(0, 0, width, height);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, (double)width, 0.0, (double)height);
    WINDOW_WIDTH = width;
    WINDOW_HEIGHT = height;
}

void mouse(int button, int state, int x, int y) {
    if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN) {
        if (n_points < MAX_POINTS) {
            mat_elem(points, n_points, 0) = x;
            mat_elem(points, n_points, 1) = WINDOW_HEIGHT - y - 1;  // Y座標は上下反転する
            n_points++;
        } else {
            printf("点の数は%dを超えられません\n", MAX_POINTS);
        }
        glutPostRedisplay();
    }
}

int main(int argc, char **argv) {
    // GLUTの初期化
    glutInit(&argc, argv);
    // ウィンドウのサイズを設定
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    // ウィンドウの作成 (引数はウィンドウのタイトル)
    glutCreateWindow("First GLUT program");
    // 描画に使う関数の登録
    glutDisplayFunc(display);
    // ウィンドウのサイズ変更時に呼ばれる関数の登録
    glutReshapeFunc(reshape);
    // マウス操作時に呼ばれる関数の登録
    glutMouseFunc(mouse);
    glutReshapeFunc(reshape);
    // OpenGLの初期化処理  (これはコールバック関数ではないので直接呼び出す)
    init();
    // 描画ループの開始
    glutMainLoop();
}

まず，マウス座標については55行目ならびに56行目に書かれています． reshape関数の中の設定では，原点が左下になるようになっていたので，左上の原点とするマウス座標とは上下方向のみが反転しています．そこで56行目ではウィンドウのサイズからY座標を引くことで座標を反転させています．

次に注目してもらいたいのが mouse 関数の内部で新しい点が追加された時に呼ばれる glutPostRedisplay 関数です．上記プログラムでは，新しい点がクリックされるたびに，点の座標を更新して再描画する必要が生じます．しかしGLUTは，再描画イベント(ウィンドウサイズの変更など)が発生しない限り，再描画を行いません．そのため，強制的に再描画を実行させるためにglutPostRedisplay 関数が呼び出されています．

課題2 (配点: 4点)

すぐ上のプログラム (クリックした5点を表示するプログラム) を参考にして，それらをラグランジュ補間した曲線を表示するプログラムを作成せよ．この課題の下に記した「二次元のラグランジュ補間」の説明を参考にして，描かれる曲線がクリックした順に点を結ぶように工夫せよ．

注意

新しい点をクリックするごとに，補間曲線が最新のものに変化していくようなプログラムとすること．
またラグランジュ補間で得られる曲線だけでなく5つの点も同時に描画すること．
頂点を順に結んでいく場合にはGL_LINESではなく，GL_LINE_STRIPを用いる．GL_LINESが与えられた頂点列に対して，0番目と1番目，2番目と3番目，のように2つ区切りで線分を描くのに対して，GL_LINE_STRIPは0番目と1番目，1番目と2番目，2番目と3番目のように，与えられた頂点列を順に線分で結んでいく．

課題の作成方法

課題の作成にあたっては，課題2および課題3で利用するZIPファイルを用いる．
このファイルを展開して得られるディレクトリ(名前はdraw_curveになる)を，matrixライブラリを含む includeならびにlibディレクトリと同じ階層に置く．
その後，draw_curve内に課題2の内部にあるdraw_curve.cに課題2および3のプログラムを作成する．
提出は課題3のプログラムのみで良いが，まず固定の点数で2次元のラグランジュ補間ができることを確認(=課題2)してから，課題3に進むのが良いだろう．

結果の例

二次元のラグランジュ補間

以前学んだラグランジュ補間においてはXY平面上で曲線のx座標が増加するのに応じてy座標がどう変化するのかを求めていました．そのため，ラグランジュの補間関数 $L_i(x)$ は $x$ の関数として，

\[\begin{aligned} L_i(x) &= \prod_{j=1, j \neq i}^{n+1} \frac{x - x_j}{x_i - x_j} \\ &= \frac{(x - x_1) \cdots (x - x_{i-1}) (x - x_{i+1}) \cdots (x - x_{n+1})}{(x_i - x_1) \cdots (x_i - x_{i-1}) (x_i - x_{i+1}) \cdots (x_i - x_{n+1})} \end{aligned}\]

と表し，この補間関数からy座標が以下のように計算されていました．

\[y(x) = \sum_{i=1}^{n+1} L_i(x) y_i\]

もちろん，この関数でも曲線を描くことはできますが，上記の表現は点をクリックした順序には関係のない式になっているので，曲線は常にx座標が小さい順に点を結んできいます．

しかしながら，特にコンピュータグラフィクスを用いて絵を描く場合などを想像すると，点を書いた順とは関係なくx座標の昇順に曲線が描かれるのは不都合です．そこで，上記のラグランジュ補間の式に$x$, $y$座標とは別の媒介変数$t$を導入して，点をクリックした順に曲線を描くように変更します．

最も単純な媒介変数$t$の設定方法はある点が $i$ 番目にクリックされた点であるときに $t_i = i$ と媒介変数を設定することです．これを用いて，ラグランジュ補間の式を書き直すと，補間関数 $L_i$ が $t$ の関数として以下のように書き直されます．

\[\begin{aligned} L_i(t) &= \prod_{j=1, j \neq i}^{n+1} \frac{t - t_j}{t_i - t_j} \\ &= \frac{(t - t_1) \cdots (t - t_{i-1}) (t - t_{i+1}) \cdots (t - t_{n+1})}{(t_i - t_1) \cdots (t_i - t_{i-1}) (t_i - t_{i+1}) \cdots (t_i - t_{n+1})} \end{aligned}\]

そして，この補間関数を用いて$x$, $y$を $t$の関数として以下のように書きます．

\[\begin{aligned} x(t) = \sum_{i=1}^{n+1} L_i(t) x_i \\ y(t) = \sum_{i=1}^{n+1} L_i(t) y_i \end{aligned}\]

このように変更すると，先ほど結果の例に示したように，クリックした順に点が結ばれたような結果が得られるようになります．

この結果を得るために以前作成した lagrange 関数のプロトタイプ宣言を以下のように変更します．

void lagrange(double t, matrix points, double *x, double *y);

この関数ではクリックされた頂点の列が points の中に格納されており，ある媒介変数 $t$ に対応する $x$, $y$ 座標が *x, *y に計算されるように実装してください．

OpenGLの中で実際に曲線を描く場合には，tを細かく分割して，折れ線として近似的に曲線を描画します．例えば以下のような形です．

// 曲線を描く
const double segments = 100;
double x, y;
glBegin(GL_LINE_STRIP);
for (int i = 0; i <= segments; i++) {
    // 以下のtは0から(n_points - 1)までをsegment分割したもの(この場合は100分割)
    const double t = (double)((n_points - 1) * i) / (double)segments;
    lagrange(t, points, &x, &y);
    glVertex2d(x, y);
}
glEnd();

可変長配列と連結リスト

ここまでで作成したプログラムは点の数が最大5個であり，また，点を追加することは可能でも点を削除することができませんでした．そこで，以下では，このプログラムを改良し，点の追加と削除を可能とするように変更します．

これまで点の座標の記録にはmatrix型を用いてきました．ここに十分大きな数の点を保存したいときに，取りうる最も単純な方法は行列のサイズを $10000 \times 2$ のように十分大きくすることでしょう．しかしながら，この場合でも点の数は $10000$ を超えられず，また，点が1つしかなかったとしても10000点分のメモリが必要になってしまいます．また点の削除についても，あまり良いやり方は思いつきません．

そこで用いるのが配列と構造体の動的確保でもご紹介した連結リストというデータ構造です．ここでは，復習を兼ねて，連結リストのプログラムとその使い方についてみていきます．

単方向リストはノードという単位から成っています．各ノードはリストに格納されるべきデータと次のノードへのポインタを備えています．例えばC言語での実装では次のようになります．

typedef struct list_node_ {
    int x, y;
    struct list_node_ *next;
} list_node;

現在は，マウスがクリックした点の座標をリストに保存したいので，データとしては int x, y が用意されています．それとは別に*nextが次のノードへのポインタを格納します．なお，この構造体の定義では，構造体が自分自身のポインタを持つため，これまで struct の直後に省略されていた構造体名を入れて，構造体内部でその名前が使えるようにしています．

ちなみにC++では struct ABC {}; のように書けば型名 ABC をそのまま使うことができますが，C言語の場合には ABC という構造体名と struct を合わせた struct ABC が一つに型名として認識されるため，上記の構造体では*node の型名に list_node_ ではなく struct list_node_ が使われています．

これとは別にリストの先頭のポインタとリストのサイズを管理する linked_list 構造体も用意しています．

typedef struct {
    list_node *root;
    int size;
} linked_list;

これらの構造体定義を下に連結リストの作成，ノードの追加，ノードの削除，ならびに連結リスト全体の削除の4つの関数が用意されています．

// リストの作成
void init_list(linked_list *list) {
    list->root = NULL;
    list->size = 0;
}

// rootを先頭要素とする連結リストの末尾に新しいノードを追加
void add_node(linked_list *list, int x, int y) {
    // 新しいノードの作成
    list_node *node = (list_node*)malloc(sizeof(list_node));
    node->x = x;
    node->y = y;
    node->next = NULL;

    // 末尾要素を探す
    if (list->root == NULL) {
        // まだ要素がなければ，先頭要素を新規ノードにする
        list->root = node;
    } else {
        // あるノードの次のノード (next) がNULLになるものを探す
        list_node *iter = list->root;
        while (iter->next != NULL) {
            iter = iter->next;
        }

        // 見つかったら末尾要素を新規ノードで置き換える
        iter->next = node;
    }

    // リストの要素数を1増やす
    list->size += 1;
}

// nodeで示されるノードをlistから削除する
void remove_node(linked_list *list, list_node *node) {
    // ノードが見つかったかどうか
    bool found = false;

    // ノードを探索する
    if (list->root == node) {
        // 先頭ノードがnodeならrootを置き換える
        list->root = list->root->next;
        found = true;
    } else {
        // 次の要素がnodeとなるノードを探す
        list_node *iter = list->root;
        while (iter != NULL) {
            if (iter->next == node) {
                // もし次のノードがnodeなら，さらにその次のノードとつなぎ直す
                iter->next = iter->next->next;
                found = true;
                break;
            }
            iter = iter->next;
        }
    }

    // もしnode見つかっていたら，メモリを解放してリストの要素数を1減らす
    if (found) {
        free(node);
        list->size -= 1;
    }
}

// リストのデータを全て削除する
void free_list(linked_list *list) {
    // 先頭から順にノードをfreeしていく
    list_node *iter = list->root;
    while (iter != NULL) {
        // 先に次のノードのポインタを別の変数にコピーしてからfreeする
        list_node *next = iter->next;
        free(iter);
        iter = next;
    }

    // 最後にリスト自体をfreeする
    free(list);
}

コードの内容については，細かなコメントを入れてありますので，注意深くコードとコメントを見ることで，一定の理解を得ることは可能だと思います．ここでは，関数の使い方について，簡単なサンプルプログラムを元に説明します．

連結リストを用いたサンプルプログラム


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <stdio.h>
#include "linked_list.h"

int main(int argc, char **argv) {
    // リストの初期化
    linked_list list;
    init_list(&list);

    // リストに頂点を挿入
    add_node(&list, 1, 2);
    add_node(&list, 2, 3);
    add_node(&list, 3, 4);
    add_node(&list, 4, 5);

    // リストの内容を表示
    printf("Size: %d\n", list.size);
    for (list_node *it = list.root; it != NULL; it = it->next) {
        printf("%d, %d\n", it->x, it->y);
    }
    printf("\n");

    // リストから要素を削除 (3番目の要素を削除)
    list_node *remove = list.root;  // 先頭の要素
    remove = remove->next;  // 2番目の要素
    remove = remove->next;  // 3番目の要素
    remove_node(&list, remove);

    // リストの内容を表示
    printf("Size: %d\n", list.size);
    for (list_node *it = list.root; it != NULL; it = it->next) {
        printf("%d, %d\n", it->x, it->y);
    }

    // リストの破棄
    free_list(&list);
}

リストの作成

リストの作成は6-7行目ある通り，単純にlinked_list型の変数を宣言し，init_listに渡してリストを初期化しています．

リストの破棄

リストの破棄についても，35行目にある通り，free_list関数の引数に破棄したいリストを渡せば十分です．前述の通り，remmove_list関数内部では，連結リストに含まれる全てのlist_nodeに対するメモリを解放しています．

要素の追加

要素の追加は10-13行目にある通り，add_node関数により行います．この関数は第1引数に要素を追加するリストのポインタを取り，第2, 第3引数に追加する頂点のx座標, y座標を取ります．今回の例では，4つの頂点を追加しており，その結果として，配列の長さ (list->sizeで取得できる)が正しく4となっていることを確認して下さい．

要素の削除

要素の追加は頂点の座標を指定することで行いましたが，要素を削除する際には，頂点座標ではなく，その内容を記録したlist_node型のポインタを指定することで行います．

例えば，3番目の要素をリストから削除したいとすれば，23-25行目のようにして3番目の要素を指し示すlist_nodeのポインタを取得し，それをremove_node関数の第2引数に渡します．もちろん，より大きな配列の$n$番目の要素や特定の条件を満たす要素を削除したいとすれば，for文などにより，削除したい要素のポインタを取得する必要があります．

リスト内容の列挙

これまでfor文では for (int i = 0; i < 10; i++) {} のように $i$番目の要素を順に処理するというプログラムが一般的でしたが，for文が

for (初期化の処理; 終了条件; 次のループにいく前の処理) {
    // 処理の内容
}

のようなルールで使われることを踏まえると，連結リストを先頭から順にたどるような処理も可能になります．

上記のプログラムではit (it は反復子を表すイテレータ(iterator)の略) にリストの先頭要素を代入し，それを次の要素に進める処理( it = it->next) をループ内の処理が実行されるごとに行なっています．もしitがNULLであれば，リストでそのノードに続く要素がない(=終端要素に達した)ということなので，それを終了条件としています．

実行の結果

上記のプログラムを実行すると，以下のような出力が得られ，正しく要素の追加や削除，ならびに要素の列挙が行われていることが分かります．

Size: 4
1, 2
2, 3
3, 4
4, 5

Size: 3
1, 2
2, 3
4, 5

課題3 (配点: 2点)

上記の連結リストを利用して，マウスの左クリックで点を追加，右クリックで点を削除するように課題2のプログラムを改良せよ．提出に当たっては，以下のように曲線の描画結果と点を削除した後の結果をスクリーンショットに含めること．

曲線の描画結果	点を削除した結果