JUNのブログ

JUNのブログ

活動記録や技術メモ

「世界でもっとも強力な9のアルゴリズム」を読んだ

読書感想文

「世界でもっとも強力な9のアルゴリズム」という本を読んだので感想.

世界でもっとも強力な9のアルゴリズム

世界でもっとも強力な9のアルゴリズム

この本はアルゴリズムについての本だが, アルゴリズムやデータ構造についての教科書という感じではなく, 現代のコンピュータ及びインターネット上で頻繁に使われている(ただしその存在は表から感じさせない)アルゴリズムについて非プログラマーでもわかるように説明した本である.

数式やコードは一切でず, 大まかな概念と考え方, 歴史的な経緯が少しというような内容である. 実際, この本を読めば本書に書いてあるアルゴリズムを実装できるというものではなく, この本を入り口とし, そこから興味のあるアルゴリズムを深堀りして実装するというのが良いのでは無いだろうか. また, 非プログラマーの人が読んでもコンピュータの裏側でどのようなことが起きているか, 現代のコンピュータやインターネットがどのようにして成り立っているのかを知れる良い読み物になると思う.

この本の中で説明されていたアルゴリズムは以下のものがある.

以下各トピックについて軽く感想を書く.

検索エンジンのインデクシング, ページランク

検索エンジンのインデクシング及びページランクアルゴリズムでは実際に検索エンジンが検索ワードに対してどのように検索結果を返しているのかというのが知れて面白かった. また章内で紹介されていたGoogle創業者が発表した論文"The Anatomy of a Large-Scale Hypertextual Web Search Engine"の存在は知らなかった. 調べてみると普通に公開されていたので今度読んでみたい.

infolab.stanford.edu

公開鍵暗号, デジタル著名

公開鍵暗号, デジタル著名に関してはセキュアに情報を交換,伝送したり, ソフトウェアやウェブサイトの作成元を保証したりする時に使われるアルゴリズムを学んだ. プログラミングは他の分野の工学(電気工学, 制御工学, etc)に比べて数学が直接的に必要になる場面というのは少ないと思っているが, それは偉大な数学者が数学及び暗号学に基づく素晴らしい暗号化方法などを編み出し, 誰かが実装してくれているからなんだなぁと思った. この当たりの話はある程度の数学の知識が無いと理解できないはずだが, 本書では簡単な例で核となる考え方を説明してくれていて自分のような人間でも簡単に核となる考え方や仕組みを理解することが出来た.

誤り訂正符号

誤り訂正符号についてはTCP/IP関連の勉強でチェックサムなどについて知っていたが, 歴史的にどのようにそのような仕組みが生まれたかなどは知らなかったので面白かった.

データ圧縮

データ圧縮に関してはロスあり/なし圧縮があり, それらの違いと大まかな考え方について知れた. ただ, 詳細は書かれていないのでこの当たりはまた調べたいと思った.

データベース

データベースは一般的には利用者側からは見えないがとても大事な仕組みである. ただ, このあたりの話は前から知っているものであり, 自分にとって特段目新しいということはなかった.

パターン認識

パターン認識についても同様で, 自分は昔この当たりの勉強をしていたので自分にとって新しい情報というのは無かった(昔勉強していたため). ただ, 勉強したことない人にとってはわかりやすい説明だろうなとは思った.

決定不可能性

最後の決定不可能性については, 少しむずかしかった. 昔計算理論の本を読んだのである程度はわかっていたが, この章では背理法を用いて "プログラムの全てのバグを検出プログラム" を作れないというのを証明した. 正直この章だけは なるほどな? という感じで読んだ. 背理法とういうのはそういうものなのだろうが, こう一発で決定するわけではなく, 「真と仮定した時に他の真であるはずの事象が偽になるからこれは真ではないよね 」みたいな感じですこし回り道をして証明しているような感じで証明して自分には少し合わないかな.

C言語でレイトレーシングプログラムを作った

42 C/C++

初めに

C言語で3Dゲームを作ったという記事の中で言及した通り, 42のLv2ではレイキャスティングで3Dゲームを作る cub3D と, レイトレーシングプログラムを作る miniRT という課題の2つがあり, 自分は cub3D を選択した.

jun-networks.hatenablog.com

しかし, レイトレーシングもやってみたくなったので, 課題の提出こそしないが, 自分なりにminiRTをやってみた. この記事はその解説記事です.

なお課題の提出はしてないのでこれで合っているかどうかは保証しかねる. 間違いがあればコメントかTwitter, Discordなどで連絡ください.

ではやっていくぞー.

miniRTの概要

具体的なコードやアルゴリズムの説明の前にまずはminiRTの課題の概要から.

miniRT の課題を一言で表すと「C言語でレイトレーシングプログラムを作りましょう」って感じ.

具体的に満たす必要のある仕様は以下の通りである.

  • .rt 拡張子のファイル(以降 rtファイル と呼ぶ)を受け取り, そのファイルに記載された設定を元にウィンドウに画像をレンダリングして表示する. (rtファイルについては詳しく後ほど説明する)
  • rtファイルの設定が間違っている場合はエラーメッセージを表示し, プログラムを終了させる.
  • --save フラグがコマンドライン引数として与えられた場合はウィンドウを表示する代わりにBMPファイル形式でレンダリング結果の画像をファイル出力する.

このプログラムのレンダリング結果のいくつかの例を貼っておこう.

f:id:JUN_NETWORKS:20210330064448p:plain
今回の課題で描画する全ての図形が含まれている

all.rt

f:id:JUN_NETWORKS:20210330192101p:plain
3Dモデルのファイルから生成したピカチュウ

3Dモデル

f:id:JUN_NETWORKS:20210330192133p:plain
玉乗りピカチュウ

rtファイルについて

今回のレイトレーシングプログラムはrtファイルを元にレンダリングを行うわけだが, そのrtファイルのフォーマットは以下のようになっている.

R  1024      800
A  0.1      255,255,255
c  0,3,-20    0,-0.2,1       60
c  20,3,0    -1,0,0       60
c  -20,3,0    1,0,0       60
c  0,20,0    0,-1,0       60
c  0,-20,0    0,1,0       60
l  15,15,-15  0.9         255,255,255
pl 0,-4,0   0,1,0            255,255,0
sp 5,0,0       3          255,0,0
tr -3,-5,-3 3,-5,-3 0,5,0      255,255,255
cy -5,-1,0   0,1,0   4  2 0,255,0
sq 0,-2,-3   1,1,-1       3          0,176,176
sq 5,-2,-3   1,-1,1       3          100,0,176

1行が1パラメータとなっており, 形式的には先頭にパラメータの識別子(identifier)が来て, その後空白区切りでパラメータのバリューが入る.

{identifier} {param1} {param2} {param3} ...

以下に各パラメータについての説明を載せておく.

R: 解像度(Resolution)

R は解像度(Resolution)を設定するパラメータである.

R {width} {height}
  • width: 画面の幅
  • height: 画面の高さ

A: 自然光(Ambient)

A は自然光(Ambient)のパラメータである.

A {lighting_ratio} {rgb}
  • lighting_ratio: 自然光の光の強さ. 0.0~1.0 の範囲の値.
  • rgb: 自然光の色.

rgb についてはカンマ区切りで 255,255,255 のように指定する. 以降もrgbを受け取るパラメータがあるが, 同じである.

c: カメラ(camera)

c はカメラ(camera)のパラメータである.

c {coordinates_vec} {orientation_vec} {FOV}
  • coordinates_vec: カメラの座標ベクトル.
  • orientation_vec: カメラの向きベクトル. 各x,y,z成分の大きさは -1.0~1.0 の範囲である.
  • FOV: カメラの視野角(Field Of View). 単位はdegree.

今回 coordinates_vec や orientation_vec のように_vecのサフィックスが付いたものはベクトルを表す. 形式としては x,y,z のようにカンマ区切りで各成分を書く. この後の説明でも同じ様に _vec サフィックスのついたパラメータの設定項目が出てくるが, それらは全てベクトルを表している.

l: 光源(light)

l は光源(light)のパラメータである.

l {coordinates_vec} {brightness_ratio} {rgb}
  • coordinates_vec: 光源の座標ベクトル.
  • brightness_ratio: 光源の明るさ. 範囲は 0.0~1.0 .
  • rgb: 光源の色

pl: 平面(plane)

pl は平面(plane)のパラメータである.

pl {coordinates_vec} {orientation_vec} {rgb}
  • coordinates_vec: 平面の座標ベクトル.
  • orientation_vec: 平面の法線ベクトル.
  • rgb: 平面の色

sp: 球(sphere)

sp は球(sphere)のパラメータである.

sp {coordinates_vec} {diameter} {rgb}
  • coordinates_vec: 球の中心座標ベクトル
  • diameter: 球の直径
  • rgb: 球の色

tr: 三角形平面(triangle)

tr は三角形平面(triangle)のパラメータである.

tr {first_coordinates_vec} {second_coordinates_vec} {third_coordinates_vec}
  • first_coordinates_vec: 三角形平面の1つ目の頂点の座標ベクトル
  • second_coordinates_vec: 三角形平面の2つ目の頂点の座標ベクトル
  • third_coordinates_vec: 三角形平面の3つ目の頂点の座標ベクトル

cy: 円筒(cylinder)

cy は円筒(cylinder)のパラメータである.

cy {coordinates_vec} {orientation_vec} {diameter} {height} {rgb}
  • coordinates_vec: 円筒の中心の座標ベクトル
  • orientation_vec: 円筒の向きベクトル
  • diameter: 円筒の直径
  • height: 円筒の高さ
  • rgb: 円筒の色

sq: 四角形平面(sqaure)

sq は四角形平面(sqaure)のパラメータである.

sq {coordinates_vec} {orientation_vec} {side_size} {rgb}
  • coordinates_vec: 四角形平面の中心の座標ベクトル
  • orientation_vec: 四角形平面の法線ベクトル
  • side_size: 四角形平面の1辺の長さ
  • rgb: 四角形平面の色

レイトレーシングについて

実際に実装に入る前にまずはレイトレーシングとはなんぞやというのを軽く説明する.

本来我々が物体を見るときには, 光源(太陽や電球)などから発した光が物体に反射し, それが目の網膜に当たり, 視神経を通じて信号として脳に伝達されて物が見える.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/795316b92fc766b0181f6fef074f03fa.png 出典: The Textbook of RayTracing @TDU

しかし, 光源から発せられる全ての光線を計算するのは計算量が莫大になり不可能です. また, 光源から発せられる光線の中で目に入る光線はごく一部なので, 膨大な量の無駄な計算をすることになってしまいます.

そこで, 光源から発生した光線を計算するのではなく, 逆に視点から光線を飛ばし, 「どのように目から光源まで光線が飛ぶか」をシミュレートする手法を使う. これがレイトレーシングである.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/2b530e80c7d0de90885e285c5d798063-1024x767.png 出典: The Textbook of RayTracing @TDU

詳しくは画像の出典元を見てください.

knzw.tech

また, 以下の動画もわかりやすくて良いです. (レイキャスティングの動画ですが)

youtu.be

ちなみに, レイトレーシングとレイキャスティングという似たような響きですが, この2つは少し違っていて, 簡単に違いを説明すると,

  • レイキャスティング: 視点から放った光線がオブジェクト(壁やスプライトなど)に当たるまでの距離を計算し, その距離を元に描画する. 光の屈折や反射などは考えない.
  • レイトレーシング: 視点から放った光線が光源に達するまで追跡する. その際, オブジェクト(球など)に光線が衝突した場合に発生する反射や屈折なども考慮して追跡し, その結果を元に色を計算し, 描画する. 光線がオブジェクトに衝突しなかった場合には背景色を描画する.

のようになっている.

ちなみに最近のレイトレーシングは本当に凄いので, 一度見てみると良いです.

www.youtube.com

こちらのNvidia公式のRayTracingのの説明動画も良いです.

www.youtube.com

実装

じゃあ実際に実装していくわけだが, 実装しやすい順番というのがなんとなくあるので, それを元に実装していく.

実装順としては

  1. プロジェクトで使う構造体とそれに関連した関数の定義
    • ベクトル構造体
    • 色情報構造体
    • ワールド情報構造体
  2. レイの表し方
  3. 平面や球との交差判定
  4. 位置と向きとFOVが固定されたカメラ
  5. 陰影(shading)
    • 環境光
    • 拡散反射光
    • 鏡面反射光
  6. 影(shadow)
  7. 球(sp)
  8. 平面(pl)
  9. 位置と向きとFOVが可変なカメラ(c)
  10. 三角形平面(tr)
  11. 四角形平面(sq)
  12. 円筒(cy)

というような感じ. 肝となるのは 2~9 でそれ以降のものに関しては 2〜9 で実装したもと共通する部分が多い.

実際のコードは以下のリポジトリにあります.

github.com

また実装の大筋(2~8)は以下のサイトのアルゴリズムを元に実装しました.

knzw.tech

プロジェクトで使う構造体とそれに関連した関数の定義

ベクトル構造体

C言語で実装するということで, まずベクトルの情報などを保持する構造体と, ベクトルの演算に関する関数などを作成します.

vec3.h に以下のようにベクトル構造体とベクトル演算に関する関数のプロトタイプ宣言を書きます.

// Vector3D
typedef struct    s_vec3 {
    double     x;
    double     y;
    double     z;
} t_vec3;

// Vec3 Utils
// 各成分を受け取ってベクトル構造体として返す
t_vec3          vec3_init(double x, double y, double z);
// ベクトルの足し算 a + b
t_vec3          vec3_add(t_vec3 a, t_vec3 b);
// ベクトルの引き算 a - b
t_vec3          vec3_sub(t_vec3 a, t_vec3 b);
// ベクトルの定数倍 a * b
t_vec3          vec3_mult(t_vec3 a, double b);
// ベクトルの内積 a · b
double         vec3_dot(t_vec3 a, t_vec3 b);
// ベクトルの外積 a × b
t_vec3          vec3_cross(t_vec3 a, t_vec3 b);
// ベクトルの大きさ(長さ) |a|
double         vec3_mag(t_vec3 a);
// ベクトルの大きさを1にしたものを返す
t_vec3          vec3_normalize(t_vec3 a);
// "x,y,z" の形式のテキストをパースしてvecポインタに格納して, ステータスを返す(0は成功. -1以外ならエラー)
int                get_vec3_from_str(t_vec3 *vec, char *str);

上記の関数の具体的な実装は以下から見れます.

github.com

色情報構造体

この先, 色の計算などを行う時にrgbを0~255ではなく0.0~1.0で計算するので, 色情報を保持する構造体と計算関係の関数をminirt.hに作ります.

typedef struct s_fcolor {
    double     red;
    double     green;
    double     blue;
}               t_fcolor;

// fcolor
// t_fcolor構造体をuint32_t型に変換する
uint32_t       fcolor2hex(t_fcolor fcolor);
// red, green, blue の値を0.0~1.0に丸める
t_fcolor        fcolor_normalize(t_fcolor fcolor);
// 各成分から構造体の値を返す
t_fcolor        fcolor_init(double red, double green, double blue);
// t_fcolor同士の足し算
t_fcolor        fcolor_add(t_fcolor a, t_fcolor b);
// t_fcolor同士の各要素同士の掛け算
t_fcolor        fcolor_mult(t_fcolor a, t_fcolor b);
// t_fcolor同士の定数倍
t_fcolor        fcolor_mult_scalar(t_fcolor a, double b);
// "r,g,b" の形式の文字列をパースして fcolor の指すアドレスに格納して, ステータスを返す(0: 成功. -1: 失敗)
int                get_fcolor_from_rgbstr(t_fcolor *fcolor, char *rgbstr);

ワールド構造体

プログラム実行中に物体の情報や光源情報などを保持する構造体を作ります.

typedef struct s_world {
    void       *mlx;  // minilibx特有のやつ
    void       *win;  // minilibxのウィンドウを指すポインタ
    int        screen_width;
    int        screen_height;
    t_dlist *cameras;  // カメラのリスト
    t_list      *objects;  // 物体のリスト
    t_fcolor    ambient;  // 環境光の強度
    t_list      *lights;  // 光源のリスト
}               t_world;

とりあえずこれで実装する準備が出来たので実際に実装していきます.

レイの表し方

ここで説明する内容は東京電機大学の資料と全く同じというか, 自分は東京電機大学の資料を見ながら実装したので, この当たりの説明は元資料である東京電機大学の資料を見た方が良いと思う. ただ, 一応ここでも軽く説明しとく.

まず, 今まで光線と言ってきたものだが, この先レイ(ray)と呼ぶことにする.

この記事の最初の方で述べたように, レイトレーシングというのは放ったレイを追跡(シミュレート)して目に入ってくる光の色や強さなどを求めるわけだが, とりあえずここでは光の強さや陰影は気にせず, 「放ったレイが物体にぶつかったかどうか」という単純な仕様を満たすことから始める.

ベクトル方程式について

様々な物体との交点を求めたい場合, 球や曲面はベクトルで表すことができ, その物体とレイとの交点を求める場合にはベクトル方程式を用いると便利である.

ベクトル方程式とは, 等式の中にベクトルが出現する方程式のことである.

もっとも簡単なベクトル方程式は以下のようなものである.

\vec{a} = \vec{b}

この式は \vec{a}と \vec{b}が, 同じ向きと大きさを持つことを意味する.

なお, ベクトル方程式で注意すべきことは, 両辺ともスカラー, もしくはベクトルである式でないと意味を持たないということである.

例えば左辺がベクトル, 右辺がスカラーの以下の式は成立しない.

\left( \begin{array}{c} a_1 \\ a_2 \\ \vdots \\ a_n \end{array} \right) = 42 \verb| は成立しない．|

レイ(半直線) の方程式

https://knzw.tech/raytracing/wp-content/uploads/2012/05/ray.png

出典: The Textbook of RayTracing @TDU

レイ(半直線)は直線と似ているが, 直線と違い終点が無い. つまり, 始点からとある方向に無限に伸びる直線である. レイは始点の位置ベクトル \vec{s} と 方向ベクトル \vec{dir} によって定義される.

レイの方程式は媒介変数 t (t \ge 0)を用いて以下のように表すことが出来る.

\begin{eqnarray} x &=& s_x + t \cdot dir_x \\ y &=& s_y + t \cdot dir_y \\ z &=& s_z + t \cdot dir_z \end{eqnarray}

(添字付きの s, dir はそれぞれ始点の位置ベクトルと方向ベクトルの成分である.)

ベクトルの方程式で表すと以下のようになる.

\vec{p} = \vec{s} + t \cdot \vec{dir}

( \vec{s}は点sの位置ベクトル)

文章で書けば, 半直線上の点 pの位置ベクトルは始点の位置ベクトルに方向ベクトルの実数倍を足したものとして表現できる ということである.

レイのベクトル方程式はこの先頻繁に出てくるので覚えておいてください.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/ray2.png

出典: The Textbook of RayTracing @TDU

平面や球との交差判定

レイがベクトル方程式で表せるようになったので, ここから平面と球との交差判定, つまりレイと物体が衝突するかどうか, また衝突した場合の交点はどこかというのを求める.

察しのいい人は気づいているかも知れないが, 平面や球などといった物体も数式として表すことでき, それによって交点の計算が出来る.

平面

原点を通る平面の方程式とレイとの交点の求め方は東京電機大学の資料に書いてあるので省略.

ここでは任意の座標を通る平面, つまり, 任意の座標と任意の法線ベクトルを持つ平面とレイとの交差判定について説明する.

まず, 任意の座標と任意の法線ベクトルを持つ平面 というのを想像してほしいわけだが, 以下の図の \vec{O} って書いてあるベクトルが任意のベクトルに置き換えた様子を想像して欲しい. また, 法線ベクトルに関しては, この \vec{n}が自由に向きを変えれる(平面が向いている方向を変えれる)ことを認識しておいてもらいたい.

ここから実際に任意の座標と任意の法線ベクトルを持つ平面とレイとの交差判定について説明していく.

まず, 任意の座標 \vec{p_0}を通る平面の方程式というのは以下のような式である.

a(x - x_0) + c(y - y_0) + c(z - z_0) = 0

ここで, a, b, c は法線ベクトル \vec{n}のx,y,z成分を表す. \vec{n} = \left( \begin{array}{c} a \ b \ c \end{array} \right)

また, x_0 のように0の添字が付いているものは \vec{p_0}の成分である.

ここで平面上の任意の点 \vec{p} はと平面の法線ベクトルは以下のような関係を持つことに注目する.

(\vec{p} - \vec{p_0}) \cdot \vec{n} = 0

つまり, 平面上の任意の点と法線ベクトルの内積は必ず0になるということである.

上記の式とレイのベクトル方程式で連立方程式が立てれる.

{\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} \vec{p} = \vec{s} + t \cdot \vec{dir} \\ (\vec{p} - \vec{p_0}) \cdot \vec{n} = 0 \end{array} \right. \end{eqnarray} }

この式を tについて解くと以下の式が出てくる.

t = \frac{(\vec{p_0} - \vec{s}) \cdot \vec{n}}{\vec{dir} \cdot \vec{n}} = \frac{(\vec{s} - \vec{p_0}) \cdot \vec{n}}{-\vec{dir} \cdot \vec{n}}

解いた tをレイの方程式に突っ込めば交点の座標が出てくるわけ.

なお, -\vec{dir} \cdot \vec{n} = 0 の時は交点が無いと判断する.

ちなみに, tの値は3つのパターンがあり,

  • t > 0 : レイは平面との交点を持つ
  • t = 0 : レイの始点は平面上にある
  • t \lt 0 : 平面はレイの方向ベクトルの逆方向, すなわち見ている方向の反対側にある.

球

平面の交差判定の式の導出は完了したので次は球の交差判定の式を導出する.

例によって原点を通る球の方程式とレイとの交点の求め方は東京電機大学の資料に書いてあるので省略.

ここでは任意の原点を中心とした球とレイとの交点の求め方を求める.

まず, 任意の点 \vec{p_0} = (x_0, y_0, z_0)を中心とする半径 rの球は以下の式で表すことが出来る.

(x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2 = r^2 \Leftrightarrow |\vec{p} - \vec{p_0}|^2 = r^2

次に, レイのベクトル方程式と, 上記の式の右辺の式を使って連立方程式を立てて, それを解くとレイの半直線と球との交点を求める式が導ける. (正確には交点までのレイの長さ tを求めて, それをレイのベクトル方程式に当てはめるわけだが)

{\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} \vec{p} = \vec{s} + t \cdot \vec{dir} \\ |\vec{p} - \vec{p_0}|^2 = r^2 \end{array} \right. \end{eqnarray} }

レイのベクトル方程式を球のベクトル方程式に代入する(はてなブログのTex記法で上手く数式に番号付けれん)

|\vec{d}|^2t^2 + 2(\vec{s} \cdot \vec{d} - \vec{p_0} \cdot \vec{d})t - 2 \vec{s} \cdot \vec{p_0} + |\vec{p_0}|^2 - r^2 + |\vec{s}|^2 = 0

これを二次方程式と見做して, 以下のようにする

A = |\vec{d}|^2 \\\\ B = 2(\vec{s} \cdot \vec{d} - \vec{p_0} \cdot \vec{d}) \\\\ C = - 2 \vec{s} \cdot \vec{p_0} + |\vec{p_0}|^2 - r^2 + |\vec{s}|^2 = (\vec{s} - \vec{p_0})^2 - r^2 \\\\ \verb|のようにおくと|\\\\ At^2 + Bt + C = 0 \\\\ \verb|となる. したがってtの値は以下のように求められる|\\\\ t = \frac{-B \pm \sqrt{B^2 - 4AC}}{2A}

また判別式 [tex: D = B2 - 4AC] の値によって解の個数が変わる.

  • D > 0 : レイと球は2つの交点を持つ
  • D = 0 : レイと球は1つの交点を持つ
  • D \lt 0 : レイと球は交点を持たない(レイと球は交差しない)

位置と向きとFOVが固定されたカメラ

ここでは単純化したカメラ. 具体的には位置と向きとFOVが固定されたカメラを定義し, またどのようにして3D空間を2D空間(スクリーン)に投影するかというのを説明しよう....と思った東京電機大学と全く同じなので詳しくは以下のサイトを見てくれ.

knzw.tech

レイの定義

まぁ基本的には以下の2枚の画像がわかってれいればよくて

https://knzw.tech/raytracing/wp-content/uploads/2012/05/coordinate_convertion.png

出典: The Textbook of RayTracing @TDU

この画像はスクリーン座標をワールド空間内で扱いやすいようにx,y座標を[-1.0-1.0]の範囲に正規化するのと, y座標を下向きに定義するという話.

https://knzw.tech/raytracing/wp-content/uploads/2015/03/ray_from_viewer.png 出典: The Textbook of RayTracing @TDU

こっちの画像はレイの半直線をどのように定義するかという話. 今回は視点からスクリーン上の点への向きを向きベクトル \vec{dir} として使うという話.

球とレイの交点の描画

ここではレイと球をコードとして表現し, 球との交差判定を実装する. また, 交点があったら画素を赤色にセットし, そうでなければ背景色(青色)をセットすることによって交差判定が正しく動作することを確認する.

物体とカメラの関係は以下の画像のように設定する.

https://knzw.tech/raytracing/wp-content/uploads/2015/03/ray_from_viewer.png

出典: The Textbook of RayTracing @TDU

int raytracing(t_world *world)
{
    // 視点位置を表すベクトル
    t_vec3 camera_vec;
    camera_vec = vec3_init(0, 0, -5);  // スクリーンの少し手前な感じ

    // 球の中心座標
    t_vec3 sphere_vec;
    sphere_vec = vec3_init(0, 0, 5);  // スクリーンの少し奥な感じ
    double sphere_r = 1;  // 半径

    for (double y = 0; y < world->screen_height; y++){
        for (double x = 0; x < world->screen_width; x++){
            // スクリーン座標からワールド座標への変換
            // x,yは[-1,1]へ変換する
            // スクリーン上の点の三次元空間における位置を計算する
            t_vec3 screen_vec;
            screen_vec = vec3_init(2 * x / world->screen_width - 1.0, 2 * y / world->screen_height - 1.0, 0);

            // 方向ベクトル
            t_vec3 dir_vec;
            dir_vec = vec3_normalize(vec3_sub(screen_vec, camera_vec));

                        // 
            t_vec3 camera2sphere_vec = vec3_sub(camera_vec, sphere_vec);

            // レイが球に当たったか計算する
            double a = vec3_mag(dir_vec) * vec3_mag(dir_vec);
            double b = 2 * vec3_dot(camera2sphere_vec, dir_vec);
            double c = vec3_dot(camera2sphere_vec, camera2sphere_vec) - sphere_r * sphere_r;
            // 判別式
            double d = b * b - 4 * a * c;
            if (d >= 0)
            {
                my_mlx_pixel_put(&world->img, x, y, rgb2hex(255, 0, 0));
            }
            else
            {
                my_mlx_pixel_put(&world->img, x, y, rgb2hex(0, 0, 255));
            }
        }
    }
    return (0);
}

上記コードは今まで説明してきたものをコード化したものである. なお, my_mlx_pixel_put()が謎だと思うが, これは42Tokyoで使うXWindowシステムのラッパーライブラリであるminiilbx用の関数である. この記事を読んでいる人は「x,yを指定して, そこに指定の色をセットする関数」という認識で十分である.

このコードをコンパイルして実行すると以下のような画像を出力する.

f:id:JUN_NETWORKS:20210401073252p:plain
球との交差判定

陰影(shading)

前のセクションで球の交差判定を実装し, 正しく描画出来ました. 次に実装するのは陰影(shading)です.

ちなみにこのセクションの内容は例によって東京電機大学の資料とほぼ同じなので元資料読んだほうがわかりやすいと思います.

まぁそれはそれとして, 陰影とはなんぞやって感じなんですけど, それは以下の画像を見れば大体わかるかなぁと思います.

https://knzw.tech/raytracing/wp-content/uploads/2012/06/shading_and_shadow.png

出典: The Textbook of RayTracing @TDU

光が物体表面に当たることで発生する明暗のコントラストみたいな感じかな?

これを実装するためにPhongの反射モデルと呼ばれる手法を使う.

en.wikipedia.org

Phongの反射モデルはWikipediaの説明と以下の東京電機大学の資料を見ると概要はなんとなくわかると思います.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/difficulty_of_tracing.png

出典: The Textbook of RayTracing @TDU

Phongの反射モデルでは, 2種類の光源の種類がある.

  • 環境光(Ambient): シーン全体を照らすような光源で, 別の物体表面での反射を経て物体表面に届く光のこと. イメージとしては太陽みたいな感じ.
  • 直接光(light): 電球のようなある場所から光を放つような光源. イメージとしては白熱電球みたいなイメージ

この光が当たることによって物体表面に陰影が出来る. 物体に当たった光が反射して目に見えるわけだが, Phongの反射モデルではその反射光を以下の3つの要素の総和で近似する.

  • 環境光の環境反射(Ambient)
  • 直接光の拡散反射(Diffuse)
  • 直接光の鏡面反射(Specular)

https://upload.wikimedia.org/wikipedia/commons/6/6b/Phong_components_version_4.png Brad Smith投稿者自身による作品 CC 表示-継承 3.0リンクによる

ではここからこの3つの反射現象を扱うわけだが, その前に物体の材質を定義することを忘れてはいけない. 材質と言っても鉄とか木材とかの材料の話ではなく, 光の反射係数のことである.

物体は材質として以下のパラメータを持つ.

  • k_s: 鏡面反射係数. 当たった光に対して鏡面反射をどのくらいするか. RGBそれぞれのチャンネルに対して [0.0, 1.0] の値を持つ.
  • k_d: 拡散反射係数. 当たった光に対して拡散反射をどのくらいするか. RGBそれぞれのチャンネルに対して [0.0, 1.0] の値を持つ.
  • k_a: 環境反射係数. 自然光に対して環境反射をどのくらいするか. RGBそれぞれのチャンネルに対して [0.0, 1.0] の値を持つ.
  • \alpha: 材質の光沢度. 光沢のある点から反射する光がどのくらい均等に反射するかを決める. より滑らかな表面ほど大きい. また, この定数が大きければ鏡面ハイライトが小さく強くなる.

自分の実装では以下のような構造体でこれらのパラメータを保持するようにした. (環境光反射係数は1に固定しているので構造体で保持していない)

typedef struct     s_material {
    t_fcolor        kDif;      // 拡散反射係数  // これを物体の色とする
    t_fcolor        kSpe;      // 鏡面反射係数
    float          shininess; // 光沢度
}                   t_material;

環境光

環境光だが, 直接光以外の光を正確に追跡することは極めて困難であるため定数として処理する.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/difficulty_of_tracing.png

出典: The Textbook of RayTracing @TDU

式にすると, 環境光の反射輝度 R_aは以下のように近似する.

R_a = k_a I_a

自分の実装では k_a はRGBの全てのチャンネルにおいて1と定義したので以下のように簡略化出来る.

R_a = I_a

拡散反射光

直接光の拡散反射光は, 光が物体表面で入射点からあらゆる方向に錯乱する現象である(乱反射とも言う). 拡散反射光は全包囲に広がるため, 理想的な拡散反射では反射した光の強さは観測者の視点位置に依らない.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/ideal_diffuse_surface.png

出典: The Textbook of RayTracing @TDU

反射光の光の強さはランベルトの余弦則(Lambert's cosine law)に従うことが知られている.

ランベルトの余弦則: 理想的な拡散反射面や拡散放射体で観測される放射強度あるいは光度が, 入射光と面の法線との間の角度θの余弦(cos)と正比例することを示す法則.

ja.wikipedia.org

https://knzw.tech/raytracing/wp-content/uploads/2012/05/lamberts_cosine_law.png

出典: The Textbook of RayTracing @TDU

この法則に従えば \vec{n} を反射面の法線ベクトル, \vec{l} を光の入射ベクトル, I_iを光源の強度, k_dを拡散反射係数とすると物体上のある点における拡散反射光 R_dの強さは以下のように表現出来る.

R_d = k_dI_i(\vec{n} \cdot \vec{l})

ここで, |\vec{n}| = |\vec{l}| = 1 である必要があることに注意せよ. また, \vec{l} は(呼び名に反して)交点から光源に向かうベクトルであることに留意せよ.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/nl_vectors.png

出典: The Textbook of RayTracing @TDU

ここでなぜ角度が \vec{n} \cdot \vec{l} が角度を表すのかがわからない人は内積の定義を思い出して欲しい.

\vec{a}\cdot\vec{b} = |\vec{a}||\vec{b}|\cos\theta

(まぁこの辺の導出は東京電機大学の資料に詳しい導出とか載ってるのでわからない人はそっち見てください)

また, 法線ベクトルと入射ベクトルのなす各が90°( \frac{\pi}{2})を超える時, すなわち光源が面の裏から当たっているときには反射は起こらない.

実装では (\vec{n} \cdot \vec{l}) \lt 0 の時拡散反射光の反射輝度は0として扱う.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/no_diffuse_reflection.png

出典: The Textbook of RayTracing @TDU

鏡面反射光

次に鏡面反射について説明する.

そもそも鏡面反射とは金属やプラスチックなどのなめらかな表面で起こる反射である. このような表面では光源に近い部分に明るい部分(ハイライト)が見える.

https://www.wdic.org/proc/plug/SCI/specular.jpg

鏡面反射 ‐ 通信用語の基礎知識

理想的な鏡面では, 光は入射角の正反射方向にのみ反射するけど, 現実は正反射方向にを中心とした範囲に反射光は広がる. また, 鏡面反射光は拡散反射光と違い全ての方向に同じ様に反射(乱反射)しないので, 鏡面反射光の強さは視点に依存して変化する.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/highlight_intensity.png

Phongの反射モデルでは鏡面反射光の放射強度 R_sは以下のような式で近似する.

\begin{eqnarray} R_s &=& k_sI_i\cos^\alpha{\phi} \\\\ &=& k_sI_i(\vec{v} \cdot \vec{r})^\alpha \end{eqnarray}

ここで， k_sは鏡面反射係数， I_iは入射光の強度, \vec{v} は視線ベクトルの逆ベクトル, \vec{r} は入射光の正反射ベクトル， \phiは \vec{v} と \vec{r}のなす角， \alphaは光沢度(shininess)といいハイライトの鋭さを決める係数( 1 \le \alpha)である(図10)．また， |\vec{v}| = |\vec{r}| = 1である.

この式では \vec{v} と \vec{r} の成す角 \phi が小さくなるほど大きくなる. つまり, 鏡面反射光が強くなる

また, \alpha が大きい値になるほど \cos^\alpha{\phi} = (\vec{v} \cdot \vec{r})^\alpha の値の変化は急激になる. つまり, \alpha の値が大きいほど環境反射光の範囲が小さくなる.

https://knzw.tech/raytracing/wp-content/uploads/2012/05/phong.png Chapter5. 陰を付ける | The Textbook of RayTracing @TDU

自分の実装で例を見せると \alphaの値が変化することによって以下のように変わる.

f:id:JUN_NETWORKS:20210401192154p:plainf:id:JUN_NETWORKS:20210401192158p:plainf:id:JUN_NETWORKS:20210401192202p:plain
左: \alpha=10, 中央: \alpha=30, 右: \alpha=100

拡散反射光と同じ様に, 法線ベクトルと入射ベクトルの成す角が \frac{\pi}{2}より大きい時, つまり (\vec{n} \cdot \vec{l}) \lt 0 の時は光が当たらないので環境反射光もゼロになる.

また, 視線ベクトルの逆ベクトル \vec{v} = -\vec{d} と正反射ベクトル \vec{r} の成す角 \phiが \frac{\pi}{2}より大きい時, つまりは (\vec{v} \cdot \vec{r}) \lt 0 の時は環境反射光が起こらない(環境反射光がゼロという扱い).

なお正反射ベクトル \vec{r} は以下のように計算することが出来る

\vec{r} = 2(\vec{n} \cdot \vec{l})\vec{n} - \vec{l}

https://knzw.tech/raytracing/wp-content/uploads/2012/05/regular_reflection.png

Chapter5. 陰を付ける | The Textbook of RayTracing @TDU

実装について

ここまでで陰影にを構成する環境反射光, 拡散反射光, 鏡面反射光を見てきたが, 定数として扱う環境反射光を除き, 光の強さを求めるためには光源からの入射光ベクトルとレイのベクトル, そして物体上の点における法線ベクトルの3つの要素が必ず必要なことがわかったと思う.

入射光ベクトルは直接光が保持しているので問題ない. また, レイのベクトルも既に求め方を表した. 残りの物体上の点における法線ベクトルだが, これは各物体の交点ごとに求める必要がある.

つまり, 語弊を恐れずに言えば物体の交点の法線ベクトルを求めればどのような物体でも陰影が求められるということです.

球

球の陰影を求める方法を考えてみます.

レイと球との交点における法線ベクトルを求めれば今まで見せた反射光の式に当てはめるだけで光の強さが出てきます.

なので, ここでは球のある点における法線ベクトル \vec{n} を求めます.

球の法線ベクトルは球の中心ベクトル \vec{p_c}から交点へのベクトル \vec{p_i}を大きさ1にしたものです.

\vec{n} = \frac{\vec{p_i} - \vec{p_0}}{|\vec{p_i} - \vec{p_0}|}

https://knzw.tech/raytracing/wp-content/uploads/2015/03/sphere_normal.png Chapter5. 陰を付ける | The Textbook of RayTracing @TDU

平面

平面は最初から法線ベクトルが定義されているのでそれを使えば陰影が求められます.

ここまでの実装すると以下のような画像が生成出来るようになります.

f:id:JUN_NETWORKS:20210401203406p:plain

コミットにチェックアウトして実行しただけなのでちょっとバグあるけど概ねこんな感じになります. (コミットハッシュ: 9379031)

影(shadow)

陰影は計算出来るようになったので次は影の計算を計算出来るようにします.

影はどのように計算するかというと, 物体とレイの交点 と 光源 の間に別の物体があれば影になります. これだけです.

https://knzw.tech/raytracing/wp-content/uploads/2012/06/shadow_ray.png

交点と光源の間に物体があるかどうかは 交点を始点 \vec{s}とし, 方向ベクトル \vec{dir}を \vec{dir} = \frac{\vec{p_l} - \vec{p_i}}{|\vec{p_l} - \vec{p_i}|} とするレイ(シャドウレイ) \vec{ray'}をと他の物体との交差判定を行えばよい. ここで \vec{p_l} は光源の位置ベクトルであり, \vec{p_i} を交点の位置ベクトルとする.

交点を始点とするシャドウレイ \vec{ray'}とそれぞれの物体と交差判定を行い, 交点から光源までの距離 D_l = \vec{p_l} - \vec{p_i}より短いものがあれば, その交点は影になるという判定になる.

注意

シャドウレイの始点を愚直に実装すると始点が自分自身と交差してしまうので, 微小距離 \epsilon をシャドウレイの始点ベクトルに足して始点をずらす必要がある.

https://knzw.tech/raytracing/wp-content/uploads/2012/06/epsilon.png

従ってシャドウレイは以下のようになる - 始点: \vec{p_i} + \epsilon\vec{dir} - 方向: \vec{dir} = \frac{\vec{p_l} - \vec{p_i}}{|\vec{p_l} - \vec{p_i}|} - 光源までの距離 D_l' = D_l - \epsilon

ここで微小距離 \epsilonは適当に \frac{1}{32} や \frac{1}{128}, \frac{1}{512} などを使う.

ここまで実装すれば以下のような画像が生成出来るようになる. (コミットハッシュ: 8c64c73)

f:id:JUN_NETWORKS:20210401205735p:plain

球(sp)

ここまでの実装で球を描画出来る様になっている.

平面(pl)

ここまでの実装で平面を描画出来る様になっている.

位置と向きとFOVが可変なカメラ(c)

ここから先は東京電機大学の資料には載っていないので手書きの図と共に説明していく.

今までのカメラは以下の図のように位置,向き,FOV(視野角)が固定されたものだった.

https://knzw.tech/raytracing/wp-content/uploads/2015/03/ray_from_viewer.png

Chapter4. 最初の実装 | The Textbook of RayTracing @TDU

現在の実装ではカメラの向きやFOVが変わった際に上手く動作しないので, 位置,向き,FOVが変更可能なカメラについてここでは説明する.

まず実際に詳しい説明に入る前に, 位置,向き,FOVが変更可能なカメラを機能させるために何をする必要があるのか大まかに書く

  1. 任意のFOVのためにカメラとスクリーンの距離 d を計算する
  2. ワールド座標からスクリーン座標へ変換するために, スクリーン座標の正規直交基底ベクトル \vec{e_{sx}}, \vec{e_{sy}} を求める.

ではやっていくぞー.

任意のFOVのためにカメラとスクリーンの距離を計算する

任意のFOVという仕様を満たすために, 与えられたFOVによってスクリーンとカメラを近づけたり離したりして任意のFOVを実現する.

これを行うためにスクリーンとカメラの間の距離 d を求める必要があるが, これは求めるのは簡単である.

与えられたFOVを \thetaとし, 画面幅を wとすると以下の式によってカメラとスクリーン間の距離を求めることが出来る.

\begin{eqnarray} \tan{\frac{\theta}{2}} &=& \frac{\frac{w}{2}}{d} \\\\ \tan{\frac{\theta}{2}} \cdot d &=& \frac{w}{2} \\\\ d &=& \frac{w}{2 \cdot \tan{\frac{\theta}{2}}} \\\\ d &=& \frac{w}{2} \cdot \frac{1}{\tan{\frac{\theta}{2}}} \end{eqnarray}

f:id:JUN_NETWORKS:20210401213010p:plain
イメージとしてはこんな感じ

スクリーン座標の正規直交基底ベクトルを求める

ワールド座標からスクリーン座標へ変換するために, スクリーン座標の正規直交基底ベクトル \vec{e_{sx}} , \vec{e_{sy}} を求める. と言っても訳わからないと思うので説明します.

そもそもスクリーン世界のx,yとワールドのx,yは同じではありません. 正確には基底ベクトルが異なります.

f:id:JUN_NETWORKS:20210402020213p:plain
スクリーン基底ベクトルとワールド基底ベクトル

これはカメラが真っ直ぐ前を向いていない( \vec{d_c} \neq (0, 0, 1)) の時, 顕著に現れます.

f:id:JUN_NETWORKS:20210402020256p:plain
カメラが座標 \vec{p_c} = (-1, 5, -2) から \vec{d_c} = (0.2, -0.7, -0.1) の向きに見下ろしている的な?

こういうわけなので, スクリーン座標とワールド座標を変換する処理が必要になります.

具体的には, レイはカメラの位置からスクリーンに向かってレイを飛ばす \vec{ray} = \vec{p_c} + t\vec{d_c} わけだが, このままではスクリーン世界の座標軸をベースなので, ワールド座標と合致せず正しく描画されません. なので, スクリーン座標軸で作ったレイの式 \vec{ray} = \vec{p_c} + t\vec{d_c} をワールド座標軸に変換するような処理が必要なわけです.

ではどうやって変換するかというと, スクリーン基底ベクトル \vec{e_{sx}}, \vec{e_{sy}}を求めて, その基底ベクトルを使ってレイの式を立てます.

スクリーン座標からワールド座標への変換を含むレイの式は以下のようになります.

f:id:JUN_NETWORKS:20210402020444p:plain
スクリーン座標からワールド座標への変換を含むレイのベクトル方程式

上記の最終的な式を見てわかるかもしれませんが, 基本的にスクリーン基底ベクトル \vec{e_{sx}}, \vec{e_{sy}} 以外は既出の値であり, なのでここでスクリーン基底ベクトル \vec{e_{sx}}, \vec{e_{sy}}を求めてしまえばスクリーン座標からワールド座標への変換を含むレイの方程式を作成することができ, それ即ち位置と向きとFOVが可変なカメラの実装が可能になるのです.

というわけでここからスクリーン基底ベクトル \vec{e_{sx}}, \vec{e_{sy}}の求め方を説明していきます.

まず, 一つ知っておかねばならないのは, 今回の課題においてカメラに与えられるパラメータは 座標, 向き, FOV だけということです.

十分じゃね? って思うかも知れませんが, 注意せねばならないのは, 回転 が無いということです.

回転が与えられていないということはカメラは以下のように長方形に一意に決まらず, 円状になってしまうということです.

f:id:JUN_NETWORKS:20210402014416p:plain
カメラの回転情報が与えられないのでスクリーンが一意に決まらない

じゃあどうするかというと, こちら側で都合の良いように勝手に決めてしまいます.

どういう風に決めれば都合が良いのかというのは人によって色々あるかもしれませんが, 今回自分はワールドのx軸に水平(もしくはy軸に垂直)として勝手に決めました.

f:id:JUN_NETWORKS:20210402020520p:plain
y軸に垂直になるように勝手にスクリーンの回転を一意にして計算出来るようにした

ここから \vec{e_{sx}} を求めていきます. \vec{e_{sy}} はカメラの方向ベクトル \vec{d_c}と \vec{e_{sx}}との外積で求めることができます. \vec{e_{sy}} = \vec{d_{c}} \times \vec{e_{sx}}

\begin{eqnarray} \vec{e_{sx}} \cdot \vec{e_{sx}} &=& 1 \\\\ \left( \begin{array}{c} s_x \\\\ 0 \\\\ s_z \end{array} \right) \cdot \left( \begin{array}{c} s_x \\\\ 0 \\\\ s_z \end{array} \right) &=& 1 \\\\ s_x^2 + 0 + s_z^2 &=& 1 \tag{1} \end{eqnarray}
\begin{eqnarray} \vec{d_c} \cdot \vec{e_{sx}} &=& 0 \\\\ \left( \begin{array}{c} d_x \\\\ d_y \\\\ d_z \end{array} \right) \cdot \left( \begin{array}{c} s_x \\\\ 0 \\\\ s_z \end{array} \right) &=& 0 \\\\ d_x \cdot s_x + 0 + d_z \cdot s_z &=& 0 \\\\ s_x &=& \frac{-d_z \cdot s_z}{d_x} \tag{2} \end{eqnarray}
\begin{eqnarray} \verb|② を ① に代入| \\\\ (\frac{-d_z \cdot s_z}{d_x})^2 + s_z^2 &=& 1 \\\\ (\frac{d_z^2}{d_x^2} + 1)s_z^2 &=& 1 \\\\ s_z^2 &=& \frac{1}{(\frac{d_z^2}{d_x^2} + 1)} \times \frac{d_x^2}{d_x^2} \\\\ &=& \frac{d_x^2}{(d_z^2 + d_x^2)} \\\\ s_z &=& \frac{\pm d_x}{\sqrt{(d_z^2 + d_x^2)}} \tag{3} \end{eqnarray}

これで e_{sx} のz成分である s_z が求められました. また, ここで \pm d_xとなっているところは, カメラは -d_x 側にあるので, s_{z} = \frac{-d_{x}}{\sqrt{(d_{z}^2 + d_{x}^2)}} を使えば良いです.

③のマイナスの式を①の式に代入

\begin{eqnarray} s_x^2 + 0 + s_z^2 &=& 1 \\\\ s_x^2 &=& 1 - \frac{d_x}{d_z^2 + d_x^2} \\\\ &=& \frac{d_z^2 + d_x^2}{d_z^2 + d_x^2} - \frac{d_x^2}{d_z^2 + d_x^2} \\\\ &=& \frac{d_z^2}{d_z^2 + d_x^2} \\\\ s_x = \frac{\pm d_z}{\sqrt{(d_z^2 + d_x^2)}} \end{eqnarray}

これで e_{sx} のx成分である s_x が求められました. また, ここで \pm d_zとなっているところは, ワールド座標のx軸に合わせて +d_z 側の式を使えば良いです.

ようやく e_{sx} の全ての成分が求まりました! e_{sy} の方はカメラの方向ベクトルと外積を取れば出てきます.

\vec{e\_{sy}} = \vec{d\_{c}} \times \vec{e\_{sx}}

これでスクリーン基底ベクトル \vec{e_{sx}}, \vec{e_{sy}}が出てきました.

ここまで実装したら以下の画像のようにカメラの位置を自由に変えれるようになります.

f:id:JUN_NETWORKS:20210402031600p:plainf:id:JUN_NETWORKS:20210402031519p:plainf:id:JUN_NETWORKS:20210402031723p:plainf:id:JUN_NETWORKS:20210402031806p:plain
同じワールドに対して様々な位置,向き,FOVのカメラを設定出来る

三角形平面(tr)

三角形平面は簡単です.

  1. 適当に三角形平面の法線ベクトルを外積を使って求める. \vec{n} = (\vec{p_3} - \vec{p_1}) \times (\vec{p_2} - \vec{p_1})
  2. 三角形の内外判定というものを行う

www.thothchildren.com

f:id:JUN_NETWORKS:20210402033311p:plain
三角形の内外判定

四角形平面(sq)

  1. 四角形平面を2次元で扱えるようにカメラの時と同様にワールド座標から四角形平面座標にするために四角形平面の基底ベクトルを求める
  2. 平面と同じ方法で交点を求める
  3. 求めた交点が四角形内に入っているか判定する

f:id:JUN_NETWORKS:20210402033601p:plain
四角形平面の交差判定(変数とかがブログとは少し違うけど適当に読み替えてください)

円筒(cy)

以下の画像に全て書いてます.

f:id:JUN_NETWORKS:20210402034147p:plain

完走した感想

さて, 完走した感想(激ウマギャグ)ですが... 疲れたーーーーーーーーーーーーーーーーー.

miniRTの課題難しかったのでブログにまとめたいなぁと思ってまとめ始めましたが, くっっっっそ時間かかりました. ここまで書くのに14時間くらいかかりました. 疲れた.

まぁそれはともかく, 課題を完走した感想ですが, 最近流行りのレイトレーシングを自分でフルスクラッチで書くという経験はとても楽しかったです. miniRTという課題名の通り最近のNvidiaとかが出しているレイトレーシングの動画とかを見ると確かにminiなRayTraicingだなぁと思いました.

ここまで読めば解ると思いますが, とにかく数学だらけ(特にベクトル)で大変でした. 久しぶり過ぎてベクトルの外積とか調べ直してなんとか思い出して実装できました. また, 数式をコード化する作業中にバグを踏むと数式が間違っているかコードが間違っているかわからなくなりデバッグがめっちゃ大変でした.

また, 今回多くの実装は東京電機大学の資料を参考にさせて貰いました. また, カメラや円筒の実装は42の学生に教えてもらいながら実装しました. 東京電機大学, 及び42Tokyoの教えてくれた学生の皆さんありがとうございました.

というわけで, miniRTの解説記事でした.

では今日はこのへんで. ではでは〜〜👋👋

参考にしたサイト

knzw.tech

www.dropbox.com

Ubuntu環境でのUnityの開発環境の作り方

Unity Ubuntu

Unityのインストール

とりあえずUnityHub使っとけば良いです.

docs.unity3d.com

Unity プロジェクト設定

エディタは VSCode 推奨.

Unity プロジェクトから起動するエディタは Edit -> Preferences で設定を開いて, Editor って調べたら設定項目が出てくる.

.NET 系

Microsoft 公式から.NET をインストールする. snap を使ったインストールが簡単で良いと思う. どのバージョンが良いかは正直わからん. LTS か 5.0 インストールすれば良い気がする...

Mono 公式から Mono をダウンロードする. Mono は C#で書かれたアプリケーションをクロスプラットフォーム用に簡単にコンパイルするためのやつ.

VSCode 設定

そのままだと Intellisense が効かなくて不便なので, C#の公式拡張機能を入れよう.

で, そのまま Intellisense が効けばいいんだが, 効かなかったので, StackOverflow の回答 を元に設定した.

具体的には以下の項目をsettings.jsonに追加した.

"omnisharp.useGlobalMono": "always",
"omnisharp.path": "latest"

HackDay 2021 Online に参加しました

ハッカソン Unity

2021年3月20日〜21日に開催された HackDay2021Online に参加しました. その振り返り記事です.

HackDayとは

一応知らない人のためにHackDayとはなんぞやというのを簡単に説明すると, Yahooが主催する「24時間で開発を行うハッカソン」です. 24時間で開発とプレゼン資料とかもろもろ作って, そんで発表するという感じです.

作ったもの

今回私のチームは BrailleBeat という点字と音ゲーを組み合わせたゲームをUnityで制作しました.

発表は以下のアーカイブで見れます.

youtu.be

開発時点ではこのゲームはiPadアプリとして作っていたのですが, 開発がある程度完了した時点で時間に余裕があったのでWebGL版も作って公開しました.

junnetworks.github.io

結果

この記事を書いている時点(2021/03/23)ではまだHappyHacking賞(投票によって決まる賞)以外の最優秀賞や企業賞などは決まっていないです.

ちなみに視聴者投票の結果は以下のようになりました.

f:id:JUN_NETWORKS:20210323192609p:plain

なんと!! 私達のチームの作品が2位です!!

感想

今回久しぶりにハッカソンに出ましたが, めちゃくちゃ楽しかったです!!

また, 視聴者投票の結果2位になれたことは大変嬉しい結果でした. ただ, 自分は今回の作品に自信があったので, 2位という結果が嬉しいと同時に少し悔しいです.

開発に関して

開発に関しては今回自分たちは完全オンラインで行いました. チームメンバーは以下のような分担で開発を行いました.

  • Diceさん: ゲームのコア部分とタップエフェクトの実装
  • みさきくん: スタート画面やオーディオビジュアライザーの実装
  • フレキくん: 譜面生成とプレゼン資料作成&発表
  • みずのさん: 全てのデザイン
  • JUN(俺): リザルト画面やWebGLビルド

上記に書いた以外にも色々とみんなやったりしましたが, 大体こんな感じの分担でした.

皆さんとても優秀でとてもスムーズに開発を行うことができ, 結果として完成度の高い作品が開発できました.

今回お互いが皆顔見知りというわけではなく, 私の場合だとDiceさんとみずのさんとは今回のハッカソンで初めましてという感じでしたが, それが逆に新鮮でとても楽しかったです. 新しい人との繋がりはいつでも良いものですね.

開発のスケジュール感としては最終的に以下のような感じになりました. (Discordのログとコミットログを参考に大体こんな感じ)

  • 20日 12:00: 開発開始
  • 20日 13:00: 譜面ファイルの形式を決定
  • 20日 18:00: ゲームとしてコア部分(判定やノーツの配置など)がある程度完成
  • 21日 00:00: 演奏画面のデザインと実装, ひらがな表示
  • 21日 01:00: スコア計算などを実装
  • 21日 05:00: タップエフェクトなどを作成
  • 21日 10:00: WebGL版デプロイ完了

github.com

チームメンバーの皆さんのおかげで余裕を持った開発が出来たと感じています.

アイデアについて

今回は"何を作るか"ということに関してはHackDayが始まる前にDiscordのボイチャにて2回ほどアイデア出しを行い決めました.

アイデア出しは「エンジニアの知的生産性」で学んだKJ法を取り入れてみました.

jun-networks.hatenablog.com

KJ法は本来オフラインで付箋を使って行うのですが, 今回は完全オンラインなので代わりにMiroというコラボレーションツールを使ってKJ法行いました.

miro.com

f:id:JUN_NETWORKS:20210323194046p:plain
Miroを使ったアイデア出し

まず, 各々が思いついたワードやそれに関連するワードやそのワードに対する感情などを15~30分くらいで書きだしてもらい, その後各々が書いたワードについて書いた人がなぜそのワードを書いたかを説明し, それに対してフィードバックを行い, これを全ての人が行います. その後関連するワード, 今回の場合だと"コロナ関連", "食事系" などのように関連性の高そうなワードを集めて大まかにカテゴライズします. そしたらそこから思いついた具体的なアイデアを書き出してもらい, そのアイデアの中から決めるというような流れでKJ法をやってみました.

f:id:JUN_NETWORKS:20210323194618p:plain
私が書いたワード

ちなみに今回の 点字×音ゲー の案はDiceさんが昔思いついたものでしたので, KJ法によって生み出されたアイデアかと問われたら少し違うかもしれませんが, それでも多くの作品のアイデアが生まれたのでやって良かったと個人的には思っています.

f:id:JUN_NETWORKS:20210323195702p:plain
BrailleBeatの付箋たち (この時点では名前が決まっていなかった)

f:id:JUN_NETWORKS:20210323203153p:plain
採用されたデザイン案

完走した感想

オンラインハッカソン, オフラインハッカソンと同じように楽しめたと思いました.

ただ, 他のチームとの交流や新たな出会いなどがやはりオフラインに比べて少ないと感じました. これはオンラインハッカソンに限らず, オンラインで開催されるイベントは概ねこの傾向が強いので仕方ないといえばそうですが... この辺なんとかテクノロジーの力で解消出来ないものか...

あと, 今回初めてデザイナーの方と一緒にハッカソンに出たのですが, デザイナーって凄いですね. この凄さを上手く言語化するのはなかなか難しいのですが, なんというかエンジニアが作った建物を綺麗にインテリアや壁紙などを整えるというか, なんかデザイナーさんがデザインしてくれるとなんか作品が華やかになるんですよね... 自分がデザインすると頑張ったところで2000年代個人サイトくらいが限度なので本当に凄いです.

今回多分1年以上ぶりにハッカソンに出たんですが, なんというか プログラミングの楽しさ というか ものづくりの楽しさ というのを思い出した気がします.

今回, HappyHacking賞を惜しくも逃したわけですが, 他にも賞はあるのでちょっぴり期待して連絡を待とうと思います.

追記: 他の賞は特に何もありませんでした.

というわけで久しぶりのハッカソン楽しかったゾイというお話でした. ではまた次の記事でお会いしましょう. ではでは〜〜👋👋

(ちなみにチーム名の由来はこんな感じです)

f:id:JUN_NETWORKS:20210323205104p:plain
チーム名が「なんでもいいですよ」に決まった瞬間

「Linuxのしくみ ～実験と図解で学ぶOSとハードウェアの基礎知識」を読んだ

読書感想文

「［試して理解］Linuxのしくみ ～実験と図解で学ぶOSとハードウェアの基礎知識」を読んだ.

［試して理解］Linuxのしくみ ～実験と図解で学ぶOSとハードウェアの基礎知識

［試して理解］Linuxのしくみ ～実験と図解で学ぶOSとハードウェアの基礎知識

Linuxを日頃から触っているけど, 中身を全然知らなかったので読んだ.

Linuxの内部の仕組みを大まかに理解出来るよい本だった.

本書は実験プログラムと豊富な図解と丁寧な解説で自分のようなOSやコンピューターアーキテクチャについて殆ど知識が無いような人でも詰まる事無く理解出来た. (Linux触ったこと無い人には難しいかもしれん)

この本を読めばLinuxカーネルを完全に理解したとはならない気がする. どちらかというと, これからLinuxカーネルやOSをがっつり勉強していくという人の初めの第一歩に最適だと思った. (初手ヘネパタ本とか挫折しそうだし)

後はLinuxを日頃から使っているエンジニアなんかも読んでおくと日頃から触っているシステムについて詳しく慣れるので良いと思った.

手を動かしながら楽しく読める本だったのでおすすめです.

第1章 コンピュータシステムの概要

この章ではOSがコンピューターにおいてどのような役割を担っており, それによって何が嬉しいのかが書かれている.

OSが無いと個々のプログラムが各ハードウェアデバイスにアクセスするためにハードウェアデバイスごとにアセンブリなどでコード書かないといけないの大変だよねー. じゃあそれをまとめて共通のインターフェースとして使えるようにすれば楽じゃん. って感じか.

このあたりの内容は前から知っているものだったので, まぁ確かにそうだな って感じ.

第2章 ユーザーモードで実現する機能

ハードウェアの抽象化などの役割がOSにあるのは前から知っていたが, この章ではCPUのユーザーモードとカーネルモードというのが出てきてこれは初めて知ったのでびっくりした.

自分はC言語でwrite, readなどのシステムコールを何度も使ったことがあったが, 実際のところそれらがどのように動いているのかは何も知らなかった. しかし, ここではCPUのモードという概念が登場し, システムコールが呼ばれた際にはCPUがユーザーモードからカーネルモードに移動して, システムコールを処理することがわかった.

システムコールにはプロセスの生成やメモリの確保,解法,プロセス間通信,ネットワーク, ファイルシステム操作, デバイスアクセスなどの色々な種類があり, それらの機能を使いたい時にシステムコールという形でカーネルに依頼する.

システムコールはCPUの特殊な命令を実行することで発行するらしい. プロセスは通常ユーザーモードで動作するが, システムコールが発行されるとCPUはカーネルモードに遷移して, 依頼内容に応じたカーネルの処理が動き, それが完了したらまたユーザーモードに戻る.

そしてユーザープロセスがシステムコールを使わず直接CPUのモードを変更するは無い. (もしあるならカーネルの意味がない)

第3章 プロセス管理

ここではカーネルによるプロセス生成,削除,管理などについて説明してる.

Linuxには fork() と execve() という2つの関数がある.

  • fork(): 同じプログラムの処理を複数のプロセスに分けて処理する という目的で使う(Webサーバーによる複数リクエストの受付). 処理としては,
    1. 子プロセス用にメモリ領域を確保し, 親プロセスのメモリをコピーする.
    2. fork()関数の実行が完了したところからプログラムは再開する. (親プロセスのメモリを丸々コピーしているのでプログラムカウンタもコピーされてるって感じか?)
    3. 親プロセスと子プロセスは一般的に違うコードを実行する. これには fork() 関数の戻り値が親プロセスでは子プロセスのプロセスID, 子プロセスでは0が返ってくることを利用して分岐させる.
  • execve(): 全く別のプログラムを生成する時に使う(bashから各種プログラムの新規作成). 処理としては,
    1. 実行ファイルからプロセスに必要なメモリマップを読み出す.
    2. 現在のプロセスのメモリを新しいプロセスのデータで上書きする.
    3. 新しいプロセスの最初の命令から実行を開始する.

ちなみにメモリマップとは, 「データやコードがメモリ内にどのように配置されるか?」という情報のこと. (で合ってるはず...)

どの命令(のアドレス)から実行すればよいかは実行ファイル内に書かれている.

Linuxにおいては実行ファイルはELF(Executable Linkable Format)という形式になっており, プロセスに必要なメモリマップはELFファイルのプログラムヘッダの部分の情報を元に計算されるのかな?

ja.wikipedia.org

別のプロセスを新規作成する場合は, 親となるプロセスが fork() を読んで, 生成された子プロセスがexecve()を呼ぶ "fork and exec" によるプロセス生成が多いらしい.

github.com

あと, 勝手に勘違いしていたんだけど, 親プロセスが死んでも(終了しても)子プロセスが芋づる式に死ぬわけでは無いっぽい. そもそも親プロセスという言い方をしているが, 正確には 「親となるプロセス」であり, 親となるプロセスからfork()によって生成されたプロセスは別に親のことなんかどうでもいいっぽい.

親プロセスが死んだら, 子プロセスは initプロセス(initはsystemdのシンボリックリンク)の養子になるらしい.

子プロセスを残したまま親プロセスがkillされてしまった場合その子プロセスはどうなるのだろうか？

その場合Linuxでは「initプロセスの養子」となるようになっている。「親プロセスがいなくなったからといって子プロセスが停止するとは限らない」ところに気をつけてほしい。

しかし一般的なデーモンプログラムなどは自分が死ぬときは基本的に子プロセスをkillしてから寿命をまっとうするようになっている場合が多いだろう。

eng-entrance.com

自分はNginxのプロセスとかをイメージして勝手に親プロセスが死んだら子プロセスも死ぬと思っていたけど, これはただ単に多くのプログラムがそのように実装しているだけらしい.

プロセスの親プロセスをpsコマンドで見る方法は以下のリンクを参照.

www.atmarkit.co.jp

第4章 プロセススケジューラ

この章ではプロセススケジューラについて説明してる.

プロセススケジューラによってプロセスは一定時間(タイムスライス)ごとにプロセスが切り替わりながら実行される.

また1つのコアに付き同時に実行できるプロセスは1つなので(ハイパースレッドは無視してもろて...), 昨今のCPUのコア数増加のありがたさがわかった.

で, この章では論理CPU(OSが認識出来るCPUの数)とプロセスを変えると実行時間がどのようになるかという実験をした.

結論としては,

  • プロセス数とコア数が同じ: 1つのプロセスが1つのコアを独占して使えるので最速.
  • プロセス数がコア数より多い時: 1つのコアで複数プロセスを切り替えながら実行する(これをコンテキストスイッチと呼ぶ)ので, 1つのプロセスが1つのコアの時に比べて遅くなる. 単純に, 4プロセスを2コアで動かすと2プロセスを2コアで動かしたときよりも1プロセスにかかる時間が2倍になる.

ちなみにコンテキストスイッチはプロセスの切りの良いところで発生するものではなく, タイムスライスが切れるとそのプロセスが今何を実行していようが容赦なく次の別のプロセスの実行へと切り替わる.

プロセスには状態があり, 状態には以下のようなものがある.

  • 実行状態: 現在論理CPUを使っている
  • 実行待ち状態: CPU時間が割り当てられるのを待っている
  • スリープ状態: 何らかのイベントの発生を待っている. イベント発生まではCPU時間を使わない. イベントが発生したら実行待ち状態に移行する.
  • ゾンビ状態: プロセスが終了した後に親プロセスが終了状態を受け取るのを待っている.

とりあえずこの4つを覚えればいいっぽい.

イベントっていうのは, 所定時間(3秒とか)が経過するの待っていたり, キーボードなどのデバイスの入力待ちだったり, ストレージデバイスI/O待ちだったり, ネットワークの送受信待ちだったりいろいろある.

各プロセスの状態は ps ax のSTATフィールドを見ればわかる.

qiita.com

論理CPUが複数ある場合のプロセススケジューリングはプロセススケジューラの中にあるロードバランサによって複数の論理CPU間で公平にプロセスを分配するようになっている.

例えば論理CPUが2つあって, CPU0にはプロセスが2つあり, CPU1にはプロセスが1つある場合, ここで新しいプロセスを生成したら, そのプロセスはCPU1のほうで実行されることになる.

timeコマンドによって表示される各項目の意味はいかのようなものである.

real 11.12  # 実際の経過時間
user 11.09  # CPUがユーザーモードで動作した時間
sys 0.00    # システムコールを実行していた時間(CPUがカーネルモードで動作した時間)

ちなみにtimeコマンドの user と sys の部分は, 2つの論理CPUで動かした場合は2つのCPUで動作した時間を合計したものになるので, real の項目より user や sys の項目の値のが方が大きくなることがある.

プロセスには優先度(nice値)というものがあり, nice() というシステムコールによって-19から20までの間で変更が可能である. デフォルトは0. -19が一番優先度が高く, 20が一番優先度が低い. 優先度が高いプロセスほどCPU使用時間の割合が他のプロセスに比べて長くなる.

優先度を上げるのはroot権限が必要だが, 優先度を下げるのは誰でも出来る.

第5章 メモリ管理

Linuxは, システムに搭載されている全メモリを, カーネルのメモリ管理システムと呼ばれる機能を使って管理している.

で, 普通にプログラムが直にメモリを触れてしまうと, メモリの確保,解放の積み重ねでメモリの断片化が起きたり, あるプロセスが別のプロセスのメモリ領域にアクセス出来たり, メモリ配置がハードウェアアドレスの番地なのでマルチプロセスの際にいちいち他のプログラムに配慮しなくてはいけなかったりと大変なので, 仮想記憶という仕組みを使う.

仮想記憶とは, カーネルが使うメモリ内にページテーブルを保持し, そのページテーブルに仮想アドレスと物理アドレスの変換を保存しておき, プロセスがメモリにアクセスする際にはそのページテーブルを元に物理アドレスにアクセスするという感じ.

ページテーブルはメモリをページという単位で区切って管理していて, 変換はページ単位で行われる. ページテーブルの中の1つのページに対応するデータをページエントリと呼ぶ. ページサイズはCPUアーキテクチャごとに決まっていて, x86_64の時は4Kバイト.

仮想記憶(ページテーブル)のおかげで, メモリ断片化の問題は, 空きメモリを上手いこと仮想アドレスに紐付ければOK. あるプロセスが別のメモリ領域にアクセス出来る問題は, ページテーブルの仮想アドレスの範囲外にアクセスしようとしたらページフォールトというCPU割り込みが発生し, カーネルがそれを捉え, SIGSEGVというシグナルをプロセスに通知し, プロセスを強制終了させる. 仮想アドレスを使えば各プロセスは自分の好きなようにアドレスを指定出来る(物理アドレスを考えなくてもよい)ので他のプロセスと共存することが可能.

で, 実際のLinuxカーネルはページテーブルを使うだけではなく, デマンドページング と呼ばれる方法を使ってメモリを管理している.

この方法は, メモリ確保のシステムコールが呼ばれた際にはページテーブルに物理アドレスが未定のページエントリを作成し(仮想メモリの確保), その仮想アドレスに初めてアクセスが来た時に初めて実際にその仮想アドレスに物理アドレスを紐付ける(物理メモリの確保)というもの.

この流れとしては,

  1. プログラムが仮想メモリは割当済みだが物理メモリ未割り当ての領域にアクセス
  2. CPUがアクセスしようと試みるが, 未割り当てなのでページフォールトが発生.
  3. カーネルがページフォールトを検知し物理メモリを仮想メモリに割り当てる
  4. ユーザーモードに戻ってプロセスの実行を継続する.

なので, 例えば8GBのメモリ搭載のシステムで100GBのメモリを確保(仮想メモリの確保)は可能であるが, 実際にアクセスしようとした時にエラーになる.

malloc() は実はメモリを毎回確保する処理をしているわけではなく, ある程度mmap()でメモリを確保し, glibcのメモリプールとして確保したメモリ(仮想メモリ)を保持しておき, malloc() が呼ばれた際にバイト単位で切り出してプログラムにかえしている. ちなみにメモリプールが足りなくなるとまた mmap() でメモリを確保する. ちなみに mmap() はページ単位でメモリを獲得するのでそのままだとバイト単位でもメモリ確保は出来ない.

実は fork() も仮想記憶によって高速化されている. fork() 実行時はメモリをまるごとコピーするのではなく, 親プロセスのページテーブルのみコピーしてくる. そして, 親か子プロセスのどちらか変更を加えたらそのページのコピーが作られ, 書き込み側のプロセスのページテーブルの仮想アドレスに対応する物理アドレスが更新され, メモリの共有が解除される. メモリが共有されたらもう一方のプロセスも読み書きを自由に出来るようなる. この仕組みをコピーオンライトという.

メモリが足りねぇーってなったら, 一部メモリ内のデータをスワップメモリに退避させてメモリに空きを作る. スワップメモリとはストレージデバイスを一時的にメモリとして扱うものである. この時退避先の領域のことをスワップメモリという. メモリからスワップ領域に退避させることをスワップアウトという. 退避させたメモリのページエントリの物理メモリにはスワップ領域のアドレスが書かれている.

逆にスワップ領域に退避させていたデータにアクセスしようとした場合には, スワップ領域からメモリ領域に戻す処理(スワップイン)が行われる.

スワップアウト, スワップイン合わせてスワッピングという.

スワップ領域は便利なものだが, ストレージデバイスはメモリに比べて格段に遅いので, スワッピングが多発する場合にはシステムの速度が低下することがある. このようなスワッピングが繰り返されてシステムの速度が低下することをスラッシングと呼ぶ.

ページテーブル自体が肥大化しないように階層型ページテーブルやヒューページとかいう仕組みを使ってうまいことしているらしい.

第6章 記憶階層

CPUからレジスタへのアクセス時間に比べてメモリへのアクセス時間は極端に遅い.

なので, CPU内にはキャッシュメモリと呼ばれるメモリから読み出した情報を貯めておく記憶領域があり, メモリへのアクセスを減らす工夫がなされている. キャッシュメモリはメモリアクセスに比べて数倍から数十倍早い.

一度目の特定のメモリへのアクセスはメモリからキャッシュメモリに読み出して, そんでキャッシュメモリから読み出す. 2回目以降はキャッシュメモリからの読み出しのみで済むので高速になる.

キャッシュメモリのデータを変更した場合には即時にメモリに変更が反映されるのではなく, バックグラウンド処理としてメモリに書き戻される.

キャッシュメモリが足りなくなったら既存のキャッシュライン(キャッシュの1単位)を破棄する. その時, ダーティフラグが立っていたらメモリに書き戻してから破棄する.

キャッシュメモリは階層構造になっていてL1,2,3キャッシュというのがある.

で, キャッシュメモリ内にデータがあれば高速化するけど, 実際に上手く働かくかというのは, 多くの場合YES. 多くのプログラムは参照の局所性と呼ばれる次のような特徴がある.

  • 時間的局所性: ある時点でアクセスされたデータは近い将来再びアクセスする可能性が高い. (ループの処理のコード領域とか)
  • 空間的局所性: ある時点であるデータにアクセスされると, それに近い場所にアクセス可能性が高い. (配列要素の全走査など)

あと, 今のままだとページテーブルの参照が結局物理メモリにアクセスしていて遅いので, Translation Lookaside Bufferというページテーブルをキャッシュメモリと同様に高速アクセス可能な領域があるらしい.

ja.wikipedia.org

で, ストレージデバイスへのアクセスはメモリに比べてもさらに激遅なので, メモリキャッシュのストレージ版であるページキャッシュという機能がある.

これはファイルからデータを読み出す時に, 直接データをプロセスのメモリ空間内にコピーするのではなく, 一度カーネル用メモリ内にページキャッシュとして保存し, それをプロセスのメモリ空間内にコピーするというものである.

書き込みについても同様で, 直接ストレージデバイスを書き換えるのではなく, ページキャッシュを書き換え, 書き換えられた箇所はバックグラウンドでストレージデバイスに反映されるようになっている.

ちなみに, ページキャッシュはカーネル内のメモリにあるので, 別のプロセスが同じファイルを読み出そうとした場合にも効果を発揮する.

ページキャッシュにもダーティフラグ的なものがあり, 考え方はキャッシュメモリのものとほぼ同じ.

ちなみにダーティフラグが立ったページが存在した状態(ストレージデバイスにまだ反映されていないページがある状態)で電源を消すとその書き換わったページの部分のデータは消滅する.

消滅してほしくなかったら同期的な書き込みを有効にするフラグ O_SYNC フラグを open() 時に指定して上げれば良い. こうすると書き込んだ時にページキャッシュだけでなくストレージデバイスにも同時に書き込まれる.

ここまで述べた通り, CPUは常に計算している訳ではなく, CPUの計算速度に比べてメモリアクセスやストレージデバイスはとても時間がかかるのでCPUには割と暇な時間(データ転送待ち)がある. そこで, ハードウェア側で認識できる論理CPUの数を2倍にして, 一定の条件下で2つのCPUがあるかのように動作させるハイパースレッドという機能がある. ただし, 必ずしも性能が向上するわけではなく, 性能が向上したりしなかったりするので, そのへんは注意が必要.

7章 ファイルシステム

ストレージデバイスを直接扱うということは各ファイルがどのメモリ番地から何バイトにあたって存在するかなどを記録しておかねばならないのでめんどくさすぎる.

なのでファイルシステムというものを使う.

ファイルシステムには ext4, XFS, Brtfs など色々種類があるが全て統一的なインターフェースでアクセス出来るようになっており, ユーザープログラム側はファイルシステムの差異を気にしなくても良いように出来ている.

それぞれのファイルシステムの違いとしてはファイルシステムの不整合時の修復方法の違いなど色々あるっぽいので用途に合わせて選ぶのが良さそう. Linuxだとext4がデフォルトっぽい?

ファイルには2つのデータがある

  • データ: 普通にデータ. 動画とかテキストとか写真とか.
  • メタデータ: ファイルの名前やストレージデバイス上での位置, サイズなどの補助的な情報. 情報としては以下のようなものがある.
    • 種類: ファイルかディレクトリかその他か
    • 時刻情報: 作成した時間, 最後にアクセスした時間, 最後に内容を変更した時間
    • 権限情報: どのユーザーがファイルにアクセス出来るか.

で, こっからおもしろくて, ファイルとディレクトリ以外にもデバイスファイルというものがある. Linuxは自分が動作しているハードウェア上のデバイスをほぼ全てファイルとして表現している. (Everything is a file)

unix.stackexchange.com

各デバイスは /dev 以下に存在する.

デバイスファイルには2種類ある

  • キャラクタデバイス: 端末, キーボード, マウスなどの読み書きは出来るがシークは出来ないもの.
  • ブロックデバイス: HDDやSSDなどのストレージデバイス.

例えば端末のデバイスファイルは wirte() システムコールでデータを端末に出力でき, read()システムコールでデータを端末から読み取れる.

$ ps
    PID TTY          TIME CMD
2873558 pts/10   00:00:00 ps
4186478 pts/10   00:00:03 zsh
$ echo "HELLO" > /dev/pts/10 #別端末から実行すると pts/10 に対応する端末に文字が出力される

qiita.com

そして実はファイルシステムを介さずに直接ストレージデバイスの対応する番地のデータを書き換えることも出来る. ただし, これはあくまで実験用であって, 普通に使うとシステムが壊れる可能性があるのでしないほうが良い.

ファイルシステムには他にメモリベースのtmpfsという /tmp や /var/run などの再起動したら消えるディレクトリで使わるものもある.

$ mount | grep tmpfs
udev on /dev type devtmpfs (rw,nosuid,noexec,relatime,size=8048832k,nr_inodes=2012208,mode=755)
tmpfs on /run type tmpfs (rw,nosuid,nodev,noexec,relatime,size=1615600k,mode=755)
tmpfs on /dev/shm type tmpfs (rw,nosuid,nodev)
tmpfs on /run/lock type tmpfs (rw,nosuid,nodev,noexec,relatime,size=5120k)
tmpfs on /sys/fs/cgroup type tmpfs (ro,nosuid,nodev,noexec,mode=755)
tmpfs on /run/snapd/ns type tmpfs (rw,nosuid,nodev,noexec,relatime,size=1615600k,mode=755)
tmpfs on /run/user/1000 type tmpfs (rw,nosuid,nodev,relatime,size=1615596k,mode=700,uid=1000,gid=1000)

他にもネットワークデバイス用とかプロセス管理用(/procで使われる)とか色々種類がある.

第8章 ストレージデバイス

ここではHDDやSSDがセクタという単位で読み出している的な話がされていた.

で, HDDはアクセスの際に機械的な動作であるスイングアームの調整とかでめっちゃ時間がかかると.

なので機械的な動作をなるべく減らすために, 連続したセクタを一度に読み出すようにした方が早い. なので, カーネル側のブロックデバイス層という部分のI/Oスケジューラという機能が連速したセクタにアクセスする場合には一度にまとめて取得するとか読み出す順番をソートするとか色々最適化してくれている.

また, 先読みという機能(これはプログラムの局所性に基づくものである)もある.

以下読んでる時に書いた雑なメモ

p7
プロセスが直接デバイスに触れないようにするためにハードウェアレベルで制限を行う.
具体的にはCPUには カーネルモード と ユーザーモードがあり, カーネルモードの時のみデバイスへアクセス出来る.
プロセスはユーザーモードで動作し, カーネル(デバイスドライバやメモリ管理システムなどのプロセスに触られたくないもの)はカーネルモードで動作する.
プロセスがデバイスアクセスなどのカーネルモードで管理している部分を利用したいときはシステムコールを使ってOSに依頼する.
システムコールはカーネルとプロセスとのインターフェース.

キーワード
- POSIX: UNIX系OSがが備えるべき各種機能を定めた規格

p25
OSが提供するプログラム例の中に ウィンドウシステム: X がある!

プログラム実行時に作成されたメモリマップは /proc/{pid}/maps というファイルによって得られる.

p110
- mmap() という関数でLinuxカーネルに対して新規にメモリを要求するシステムコールを呼ぶ. - mmap() はページ単位(通常は4KB)でメモリ領域を獲得する. - malloc() は内部的にmmap()を呼び出している. - malloc() のバイト単位でのメモリ確保を実現するために, 事前にmmap()システムコールによってカーネルから大きなメモリ領域を確保してプールして貯めておき, プログラムからのmalloc()発行時にその領域から必要な量をバイト単位で切り出してプログラムに返すという処理をしている. - プールしているメモリ領域がなくなればサイドmmap()を発行して新たなメモリ領域を獲得する.

p122: デマンドページング
- やはりmalloc() や mmap() でメモリを獲得しても, 実際に物理メモリが確保されるのはそのメモリアドレスにアクセスした瞬間らしい. - 原理としては, mmap() などでメモリを確保する. (正確には 仮想メモリを確保する と言うらしい) - ページテーブル(仮想アドレスと物理アドレスを紐付けるやつ)にエントリを追加. ただしこの時点では物理アドレスの方は決まっていない. - プログラムが確保した領域にアクセスするとCPUがページフォールトを起こす. それをカーネルが検知して, 物理メモリを確保し, ページテーブルを書き換えて, プログラムの処理を続行する. (これを 物理メモリを確保した と表現する) - この時プログラムはページフォールトが発生したことに気づかない. - ちなみに2回目以降のアクセス時にはページフォールトは発生しない. なぜなら物理メモリが既に確保済みだから.

p132: メモリの枯渇
- メモリの枯渇には2種類ある - 仮想メモリの枯渇 - 仮想アドレス空間がいっぱいの状態でメモリを確保しようとすると失敗する. - これは32bit環境ではアドレス空間(ページングテーブル)のサイズが約4GBしか無かったので昔は大規模ソフトウェアでこの問題が発生していた. - いまは64bit環境で, 128TBくらいのアドレス空間があるので大体大丈夫. - 物理メモリの枯渇 - 物理メモリに空きが無かったら発生する.

スワッピング
- 物理メモリが足りなくなった際に, 一部メモリのデータをスワップ領域に移動させることをスワップアウトという. - スワップ領域に退避させていたデータにプログラムがアクセスした際にはページフォールトが発生し, スワップ領域から物理メモリにデータが移動される. これをスワップインという. - この2つのことを含めてスワッピングと呼ぶ. - スワッピングはページ単位で行われるので, ページングとも呼ばれたりする. その際はページアウト, ページインとなる.

p148 2種類のページフォールト
- メジャーフォールト: スワッピングのようにストレージデバイスへのアクセスが発生するページフォールトのこと - マイナーフォールト: ストレージデバイスへのアクセスが発生しないページフォールトのこと

p229: procfs : システムに存在するプロセスに関する情報を得るためのファイルシステム
- cat /proc/{pid}/maps : プロセスのメモリマップ - cat /proc/{pid}/cmdline : プロセスのコマンドライン引数 - cat /proc/{pid}/stat: プロセスの状態やこれまでに使用したCPU時間, 優先度, 使用メモリ量など - procfsではプロセス以外にも以下のような情報も得られる - /proc/info: システムに搭載しているCPUに関する情報 - /proc/diskstats: システムに搭載しているストレージデバイスに関する情報 - /proc/meminfo: システムに搭載しているメモリに関する情報 - /proc/sys/: カーネルの各種チューニングパラメータに対応するファイルが入っている. sysctl コマンドと/etc/sysctl.conf によって変更するパラメータに1対1で対応 - ps, sar, top, freeなどのOSがが提供する各種情報を表示するコマンドは procfs から情報を取得している. - 各種ファイルやディレクトリの詳細は man proc を参照.

p230: cgroup: 各種リソースの使用量に制限を設けるcgroupという機能があり, cgroupfsを通して操作する.
- CPUやメモリの使用量を制限することが出来る. - この機能はDockerなどのコンテナ管理ソフトウェアや, 複数の仮想マシンが動作するシステムで使われている. - 特に1つのシステム上に複数の顧客のコンテナや仮想マシンが共存するマルチテナント構成のシステムにおいて使われている.

使ったコマンド
- strace: strace ./a.out 呼ばれたシステムコールを表示する. - sar: sar -P ALL 1 1 とすると1秒間のCPUがどのモードになっているか割合が見れる. - sarコマンド自体はCPUやメモリ, ネットワーク, ディスクIOなどの負荷が見れるコマンド - ldd: ldd /bin/echo プログラムがどのようなライブラリをリンクしているかを見れる. - readelf: readelf -h /bin/sleep #エントリポイントアドレスの取得 Linuxの実行ファイルのフォーマットであるELF(Executable Linkable Format)の情報を見る. - readelf -S /bin/sleep # コードとデータのファイル内オフセット, サイズ, 開始アドレスを取得 - taskset: taskset -c 0 ./a.out コマンドライン引数で指定したプログラムを-cオプションで指定した論理CPU上で動作させる - ps ax でプロセスの状態を見る psコマンドまとめ - /proc/cpuinfo にCPUの情報が載っている - ps -eo pid,comm,time,etime: プロセスID, コマンド名, CPU使用時間, 経過時間 を表示する - free システムが搭載するメモリの量と使用中のメモリの量を見る. (出力はkB単位) - sar -r 1 でシステムの状態を1秒毎に表示 - sar -B 1でページングに関する情報を1秒毎に表示 - swapon --show システムのスワップ領域を表示 (free でも確認可能) - sar -W 1 でスワッピング(ページング)に関する情報を1秒毎に表示

関数
- system() でC言語からシェルコマンド実行出来る (man 3 system)

C言語で3Dゲームを作った

42 C/C++

42の課題の1つであるcub3Dを今日クリアしたので感想を書く.

課題について

Lv2 ではCG系の課題があり, cub3Dというレイキャスティングで古典的な3Dを作るか, miniRTというレイトレーシングプログラムを作るかを選ぶのですが, 自分はcub3Dの方を選びました. なぜなら画面動かせた方が楽しそうだったから.

レイキャスティングとはなんぞやって感じだけど, 大雑把に言えば「光をシミュレートして3次元空間を2次元空間に落とし込む」という感じかな? レイキャスティングのコアとなる考え方は, 光源から放たれる全ての光(光線)をシミュレートするのではなく, 逆に目(スクリーン)から光線(のようなにか)を発射してそれを計算することで何を映すかを計算する手法って感じ?

ちょっと言語化が下手くそ過ぎたので以下の動画の冒頭部分にレイキャスティングのわかりやすい概念の説明があるのでそれ見たほうがいいかも.

www.youtube.com

cub3Dがどんな課題かというと, 完成形としては Wolfenstein 3D みたいな3DゲームをC言語で作りましょうという課題.

www.youtube.com

やらなきゃいけないこととしては以下のような感じ

  • ゲームの設定ファイル(.cubファイル)から設定情報などをパースしてそれらの情報を元にゲームを遊べるようにする.
  • レイキャスティングを用いて3Dのような表示をする
  • --save フラグが引数として提供されたら.bmpファイルを出力してプログラムを終了する

って感じ. メインはレイキャスティングのところ.

使用が許可されている関数などは決まっていて, なんでもかんでも使えるわけではない. 一応 <math.h> 内の関数は全て使用しても良いということだったので, 三角関数などは実装しなくても良い.

また, 描画に関しては, 42側からX Window Systemのラッパーライブラリが提供されるのでそれを使う必要がある.

github.com

42では課題は与えられるけど, 授業や教科書は無いので自分は以下のサイトを見ながら作った.

lodev.org

作ったもの

コード

github.com

動いている様子

youtu.be

Wolfenstein 3D のテクスチャを使うとそれっぽくなります.

youtu.be

出力されたBMPをイメージビュワーで開いた様子. (なぜかはてなブログでbmpファイルをうpするとバグったためスクショ)

f:id:JUN_NETWORKS:20210303035915p:plain

仕組み

norm_leave_comment ブランチにコメント付きのコードがあります. (ブランチ名ひどいな...)

github.com

壁の描画

github.com

プレイヤーの座標などの表し方

f:id:JUN_NETWORKS:20210304084150p:plain

プレイヤーの現在地は2次元ベクトル \vec{pos} で表されます. またプレイヤーの現在向いている方向は2次元方向ベクトル \vec{dir} で表され, これは大きさ1の単位ベクトルです.

ここからがポイントで, ここにスクリーンを表すカメラ平面ベクトル \vec{plane} を追加します. -\vec{plane} が画面左側, +\vec{plane} が画面右側を表します. またこの \vec{plane} の長さ(大きさ)によってプレイヤーの視野角が変わります.

視野角30° ( |\vec{plane}| \fallingdotseq 0.2679 )

f:id:JUN_NETWORKS:20210304085825p:plain
視野角30°

視野角66° ( |\vec{plane}| \fallingdotseq 0.6494 )

f:id:JUN_NETWORKS:20210304085928p:plain
視野角66°

視野角90° ( |\vec{plane}| \fallingdotseq 1.0000 )

f:id:JUN_NETWORKS:20210304090021p:plain
視野角90°

planeベクトルの長さの計算方法は tan(deg/2) で計算出来ます.

また, マップのデータは文字列の配列で持ちます. (0: 空白, 1: 壁, 2: スプライト(障害物))

char *MAP[] = {
        "1111111111111111111111111",
        "1000000000110000000000001",
        "1011000001110000002000001",
        "100100000000000000000000111111111",
        "111111111011000001110000000000001",
        "100000000011000001110111110111111",
        "11110111111111011100000010001",
        "11110111111111011101010010001",
        "11000000110101011100000010001",
        "10002000000000001100000010001",
        "10000000000000001101010010001",
        "11000001110101011101011010N0111",
        "11110111 1110101 101111010001",
        "11111111 1111111 111111111111",
};

光線を飛ばす

以下の図のような感じでプレイヤーの現在地から \vec{dir} - \vec{plane} から \vec{dir} + \vec{plane} までの間で光線を飛ばします. 飛ばす間隔はスクリーンの横幅のピクセル数に依存します(画面の横幅と同じ数の光線を飛ばす). (図では光線の一部を省略しています)

f:id:JUN_NETWORKS:20210304085314p:plain

で, 光線を飛ばすといっても適当に飛ばしたのではどの壁にぶつかったかわからないので, DDA(デジタル差分解析)という方法を使って光線を1マスずつ進めていき, 壁にぶつかったかどうかを都度チェックします.

f:id:JUN_NETWORKS:20210304095819p:plain

Raycasting

sideDistX, sideDistY は最初プレイヤーがいる位置がぴったりマスの端にいるとは限らないのでまず最初の1回目だけは別でマップの端に移動するための量.

deltaDistX, deltaDistY はマスの端から次のマスの端までの距離.

これらの値を使って1マスごとに壁かどうかチェックしていき, 壁だったらそこで終了する.

壁までの距離を求める

光線を飛ばして壁にぶつかれば今度は, 壁までの距離を求めることが可能になります.

ただし, プレイヤーから当たった壁までの距離をそのまま使うと魚眼のようになってしまうので, 工夫する必要があります.

具体的にはプレイヤーから壁までの距離ではなく, カメラ平面(を無限に左右に伸ばした直線)に対して垂直になるような距離(以後"垂直距離"と呼ぶ)を取ります.

f:id:JUN_NETWORKS:20210304104932p:plain

Raycasting

上の図でいうところの緑色の線が垂直距離です.

壁までの垂直距離の計算式や図を用いた導出は Raycasting でされているのでここでは割愛します.

壁を描画する

壁までの垂直距離が求まったところで, その値を使って今度は壁の高さ(height_base)を求めます.

これはただ単に 基準となる壁の高さ / 壁までの距離 で求めることが出来ます.

この基準となる壁の高さ は別にスクーン幅そのまま使ってもいいんですが, 実はそのままスクリーン幅を使うと縦横比がスクリーン幅によって変わってしまうので, 変わらないようにするために 2*|\vec{plane}| の逆数を掛けます. 式は スクリーン幅 / (2 * plane_length) です. この式の意味としては, 「視野角が広くなるということは \vec{plane} の大きさが大きくなるよね. 大きくなるということは描画された時に横の長さが一定じゃなくなるってことだから, 2 * |\vec{plane}| の逆数を掛ければ横の長さが元に戻るんじゃね?」 っていう感じ.

これで壁の高さが求められたので, あとは画面中央を基準に壁を描画すればOKです. テクスチャを描画する場合は描画している場所が壁全体の上から何%の位置にいるのかというのを求めて, それをもとにテクスチャ画像から色を取得してスクリーンに描画すればOKです.

スプライトの描画

github.com

そもそもスプライトとはなんぞやって感じなんですが, スプライトは障害物みたいな感じのやつです.

f:id:JUN_NETWORKS:20210304111022p:plain
この樽みたいなやつがスプライト

スプライトは壁の描画とは一味違ってて, よく言われる表現が「スクリーンにシールを貼った感じ」というもの. これは実際に動いている動画とかを見ないと多分わからないと思うのでこの記事の最初の方で貼った動画を見てちょ.

ただ, 正直どのようにスプライトを描画したら正解なのかがしっかりわかっている訳ではないのでもしかしたら間違ってるかもです.

というか壁の描画がプレイヤーから光線を発射し, それが壁にぶつかるまでの距離を元にどのように描画するのかを決めていたのに対し, スプライトの描画はプレイヤーとスプライトの位置関係を元に2D画像をどのような大きさでスクリーンのどこに描画するか計算するので, 壁の描画とは考え方がだいぶ違います.

技術的には 透視投影変換 というものらしいです. (42にいるゲーム開発者の方が教えてくれました)

mem-archive.com

処理の流れとしては

  1. 壁の描画フェーズにてスクリーン幅分の光線放出し, 壁までの垂直距離を求めたので, その各光線の壁までの垂直距離の情報を配列(zBuffer とする)として保持する.
  2. スプライトまでの距離(ユークリッド距離)を求めて, 距離が遠い順になるようにソート.
  3. スプライトの座標をマップ上の座標からプレイヤーからの相対座標に変換する.
  4. カメラ行列の逆行列を掛けてスクリーン上でのx座標と, プレイヤーからスプライトまでの深度(3D空間におけるZ軸)を求める.
  5. スクリーン上のx座標とスプライトまでの深度を元にスプライトを描画する幅や高さを計算する.
  6. スプライトの左端から右端にかけてスクリーンの各xに対して描画処理を行う. その際に zBuffer[x] がスプライトの深度よりも遠い (つまりスプライトが壁よりも手前にある) 場合にスプライトを描画する.

はい. むずいですね.

正直スプライトの計算に関しては元サイトの方でも説明が少なかったので理解するのが大変でした.

スプライトの描画に必要な情報の計算

スプライトの描画に必要な情報は以下の通りです.

  • スプライトの描画座標
  • プレイヤーからスプライトまでの距離

この2つです. 一応他にもスプライトの描画サイズなどもありますが, 他の情報はすべて上記の2つの値から計算されるので, この2つの値がもっとも重要なのです.

この2つの値の計算に 透視投影変換 の手法を使います.

透視投影変換は2つのフェーズに分けることができます.

https://i2.wp.com/mem-archive.com/wp-content/uploads/2018/02/%E3%82%AD%E3%83%A3%E3%83%97%E3%83%81%E3%83%A34.png

透視投影変換とは | NO MORE! 車輪の再発明

つまり以下の2つの処理に分けることが出来ます.

  • 外部パラメータ：世界座標系からカメラ座標系への変換
  • 内部パラメータ：カメラ座標系から画像座標系への変換

ちなみに...

  • カメラ: 今回の場合, プレイヤーの現在座標にあたる.
  • 世界座標系: 絶対的な位置. 今回の場合だとスプライトのMAP上での座標にあたる.
  • 外部パラメータ: カメラ行列の逆行列(後述)を掛けてカメラ座標系に変換する.
  • 内部パラメータ: カメラ座標系から画像座標系(スクリーン上での具体的な座標)に変換する

というように対応します.

世界座標系からカメラ座標系への変換

まず初めに世界座標系からカメラ座標系への変換を行います.

この変換を行うために, スプライトの座標を世界座標系(スプライトのMAP上での座標)からプレイヤーからの相対座標に変換するひつようがあるので変換します.

式は, \vec{sprite} - \vec{pos} です. シンプルですね.

次に相対座標からカメラ座標系への変換を行います.

カメラ座標系への変換には相対座標に対してカメラ行列を掛けるという操作を行います.

カメラ行列ってなんぞや? って感じですが, カメラ行列とは以下のような行列のことです.

\left[ \begin{matrix} planeX & dirX \\ planeY & dirY \end{matrix} \right]

そしてカメラ行列の逆行列は以下のような式になります.

\left[ \begin{matrix} planeX & dirX \\ planeY & dirY \end{matrix} \right]

これを先程求めたスプライトのプレイヤーからの相対座標 ( \vec{pos'} とする) に掛けます.

\frac{1}{(planeX \times dirY - dirX \times planeY)} \times \left[ \begin{matrix} planeX & -dirX \\ -planeY & dirY \end{matrix} \right] \left[ \begin{matrix} sprite'X \\ sprite'Y \end{matrix} \right] = \left[ \begin{matrix} transX \\ transY \end{matrix} \right]

この式によって求められる transX , transY は以下のような意味を持つ.

  • transX : カメラから見て左右のスプライトまでの距離. スケールはマップと同じ.
  • transY : カメラから見て前後(深度)のスプライトまでの距離. スケールはマップと同じ.

図にすると以下のような感じ.

f:id:JUN_NETWORKS:20210304123149p:plain

カメラ座標系から画像座標系へ変換する

ここではスクリーン上に描画する際に必要となる以下の値を計算します.

  • スクリーン上でのx座標
  • スプライトのスクリーン上での高さ
  • スプライトのスクリーン上での幅

まずスクリーン上でのx座標ですが, これは (int)(screenWidth / 2 * (1.0 + transX / transY)) で計算出来ます. 式の意味としては, まず transX / transY が, スプライトが画面左端にある時は -1, 中央の時は 0, 画面右端にいるときは1になります. これに1足して, 画面の横幅の半分を掛ければ具体的なスクリーン上でのスプライトの中心のx座標が求まります.

スプライトの高さと幅については壁の高さのときに使った height_base を使って height_base / transY とするれば求まります.

後はこれを描画すればOKです.

f:id:JUN_NETWORKS:20210304124246p:plain
計算過程(間違ってたら教えてください)

BMP画像の出力

www.umekkii.jp

基本的にこのサイトを見ながらファイルに各種情報を書き込んでいけばOK. Bitmapらくちん!

マップが閉じているかの判定

github.com

設定ファイルにて示されているマップが閉じていない場合はエラーを返さないといけないので, マップが閉じているかどうかの判定を行う必要があります.

"マップが閉じている"というのは具体的には, プレイヤーが歩いてマップ外部に到達不可能. つまり, 壁で覆われているということです.

この判定は floodfill というアルゴリズムを使えば可能です.

en.wikipedia.org

おまけ

アルファブレンディング

処理が重かったので関数を作っただけで使いませんでしたが, アルファブレンディングというものを実装しました.

ja.wikipedia.org

// アルファブレンディング
// dst: 背景, src: 前景
uint32_t   alpha_blend(uint32_t dst, uint32_t src)
{
    double     alpha;
    uint32_t   color;

    // 透明: 0.0, 不透明: 1.0
    alpha = -((double)(src >> 24) / (double)0xff - 1.0);
    color = 0x00000000;
    color |= (int)((src & 0xff) * alpha) + (int)((dst & 0x000000ff) * (1 - alpha));
    color |= ((int)((src >> 8 & 0xff) * alpha) + (int)((dst >> 8 & 0xff) * (1 - alpha))) << 8;
    color |= ((int)((src >> 16 & 0xff) * alpha) + (int)((dst >> 16 & 0xff) * (1 - alpha))) << 16;
    return (color);
}

やってることとしてはWikipediaの記事をそのままコードにした感じ.

f:id:JUN_NETWORKS:20210304124513p:plain
樽の背景が少し透けてる

何かに使おうと思って作ったけど, 結局使わなかったので供養.

完走した感想

完走した感想ですが, 楽しい課題でした. 3Dゲームの描画の計算のやり方(レイキャスティング)や設定ファイルをC言語でパースする方法などを知れてよかったです.

ただ, エラーハンドリングがめんどくさかった... mallocの成否の判定などを書いていると, PythonやJSの例外って便利な機能だなぁと思いました.

あと, 数学を使ったコードを久しぶりに書きましたが楽しいですね. 久しぶりに高専で使ってた線形代数のノート引っ張り出して色々思い出しました.

昨今3DゲームとかはUnityとか使えばある程度のものは簡単に作れるわけですが, 一度こうやってゲームエンジンなどを使わず, 原始的なゲームを作ってみると, かなりゲームエンジンに対する考え方なども変わりますし, ゲームエンジンってすげぇなぁ〜って思いました.

今回も記事を書く前はめんどくさいなぁ〜と思ったのですが, 記事を書く中で適当に理解して放置していた箇所を理解し直す羽目になった(特にスプライトのところ)ので良かったです. やはりアウトプットは大切. はっきりわかんだね.

本当はこの課題の前に, printf自作とかサーバー系の課題とか面白い課題が色々あったのですが, 結局書きたいなーと思って放置してしまっていますね... printfはそのうち書きます.

42, いい場所なので, プログラミングが好きな人間は来ると幸せになれると思います.

では今日はこのへんで. ではでは〜〜👋👋

「エンジニアの知的生産術」を読んだ.

読書感想文

「エンジニアの知的生産術」という本を読みました.

エンジニアの知的生産術 ―効率的に学び、整理し、アウトプットする WEB+DB PRESS plus

エンジニアの知的生産術 ―効率的に学び、整理し、アウトプットする WEB+DB PRESS plus

読んだ目的

知的生産を上げたかったから.

具体的には自分は本を読むのがめちゃくちゃ遅いのでその辺解決出来ないかなぁと思い読んだ.

各章のまとめ/感想

1章 新しいことを学ぶには

この章はこれから先の章で学ぶことを一通り紹介するような感じだった.

時間がない人はこの章だけ読んでもいいかも?

後にいくつかの章で言及されることだが, 基本的に質の良いインプットというのは, 「全体を把握した後, 細部を理解する」という感じらしい.

この章で大事なのは, 学びのサイクルは以下の3つの繰り返しであるということ.

  1. 具体: 情報収集や体験など
  2. 抽象: パターンの発見など. 抽象化.
  3. 応用: 抽象化したものを実際に使う(実践する, 検証する)

2章やる気を出すには

やる気が起きない人の多くはタスクが多すぎるかららしい.

なのでやるタスクを絞る必要がある.

タスクの絞り方としては, タスクや思っていることを全て紙に書き出して, それらを整理しこれから何をするかを決める.

これは Getting Things Done (GTD) と呼ばれる手法らしい.

postd.cc

何を優先するかという点においては「7つの習慣」の第3の習慣を参考にすると良い.

www.recruit-ms.co.jp

またタスクが大きすぎるとゴールが遠く, やる気が出ないので, タスクを細かいタスクに分割するか, 時間で区切るなどの工夫が必要.

所感

わかる...自分も数ヶ月前まで業務で設定するタスクの粒度が大きくやる気が出ないことが多かったが, ここ数ヶ月タスクの粒度を細かくすることによって業務効率が上がったことを実感している.

時間を区切るというのは具体的にはポモドーロテクニックなどだが, この辺は創造的なタスクなのか, 記憶のタスクなのかで向き不向きがあるというのをどっかの本で読んだ. (多分DAIGOの本だと思う) (ちなみにポモドーロテクニックは暗記などの創造性の低いタスクに向いてるって書いてた気がする)

3章 記憶を鍛えるには

記憶とはPCのメモリのようなものではなく, どちらかというと筋肉のように何回も鍛える必要がある.

記憶は使う(思い出す)たびに強くなる.

アウトプットをするのは思い出す行為にあたり, 記憶が強化される.

記憶を鍛えるためには反復学習が適している. 次の学習の時期は忘れた頃くらいが良いらしい.

このあたりの学習の期間の調整などの仕組みやソフトとして, ライトナーシステム や Anki というソフトなどがある.

note.com

所感

つまるところ, いっぱい思い出しそう! アウトプットしよう!

しかし, この学習間隔というのがむずいよな...

"英単語を覚える" とかだったら忘却曲線に基づいた学習間隔で出題するアプリもあるっぽいしそういうのを使ってもいいいかも

4章 効率的に読むには

目的意識を持って本を読むと効果が上がる.

早く読もうとすると入ってくる情報量が理解する速さを上回ってしまい, 結果インプットの量に比べて理解出来た量が減ってしまう.

無理して早く読むよりも自分に適した速度で読むのが良い.

本の読み方としては - まずは本を読む前に本の全体像を把握する - 目次で章や説を見る - 書評などを探して感想を読む.

本を読むための目的はいくつかあり, 具体的には以下のようなものがある

  • 大雑把な地図を得るため: どの情報がどこにあるか把握し, 必要な時に読み返せるようにする
  • 結合を起こす: 既に持っている情報や他の本との間のつながりを見つけ出し, 新たな知識を得る
  • 思考の道具を得る: 具体的な言葉などを知りこれからその分野などでの学習や会話が出来るようにする.

これらの目的も素晴らしいが, 著者は 復習のための教材を作るを目的とすることをおすすめしている.

復習のための教材というは, "例えば人に教える" や "(人に教えるために) ブログやスライド, 資料などを作る" といったことが当てはまる.

ここでのポイントは 人に教える ということである.

人に教えるために作った資料などは後に自分が見返した時にも大いに役立つ.

所感

このブログがまさにそれだね!

また, 復習という意味では読み終わった後に他の人が書いた書評を読むのも自分とは違った意見や視点を知れてとてもおもしろく復習になるし新たな発見があったりしてとても良い.

アウトプットを前提に読むというところでは, 読み終わってから書評を書くのではなく, 各章読み終わるごとにその章の感想を書くのが良いのかなぁと思ったりした. (忘れちゃうので(思い出すことが大事なはずでは?))

このあたりはいくつかやり方を試してみて一番効果が高そうなものを行うようにすれば良いかな.

5章 考えをまとめるには

考えをまとめるにはKJ法というのが良い.

http://www.ritsumei.ac.jp/~yamai/kj.htm

流れとしては

  1. 持っている情報, 思いついたことなどを全て付箋に書き出す.
  2. 主観的に書き出した付箋で近いものを近い場所に置きグループ化する
  3. グループに名前を付ける(名前を付けれない場合はグループ分けが良くない)
  4. グループ間の関係(類似, 対立などなど)を矢印などで書く.
  5. 文章化してアウトプット

人によってやりやすいようにカスタマイズすれば良い.

6章 アイデアを思いつくには

著者によるとアイデアが思いつくまでには以下の3つのフェーズがあるらしい

  1. 耕すフェーズ
  2. 芽生えるフェーズ
  3. 育てるフェーズ

1.耕すフェーズでは情報のインプットや調査, つながりを見つけ出したりなどが含まれる. 第4章で紹介したKJ法なども大いに役立つ.

2.芽生えるフェーズでは耕すフェーズで獲得した知識や情報を脳内で寝かしておきアイデアが芽生えるのを待ちます. この辺は昔読んだ本にお風呂などのリラックスした状態では脳が思考や情報を整理を行う といったことが書かれていた. だから風呂でアイデアが思いつくことが多いらしい.

3.育てるフェーズでは, 芽生えたアイデアというものはそのままでは使えないことが多いのでそれをブラッシュアップしてプロダクトに出来るレベルにするみたいな感じ.

所感

昔ハッカソン(アイデアソン)に出た時に複数人でアイデアやワードを付箋に書いていって, そこからアイデアを生み出し, 実際に開発するということを何回かしたが, 今思えばその当時行ったことはまさにこれではないか.

確かにあの当時, 「何も思いつかん...」というところからアイデアを実際に生み出し, そして開発したことからして KJ法+この章の方法 はアイデアを生み出すことが出来そうだ! と思った.

こうやって自分の過去の経験と結びつくと記憶が強化されるらしい.

7章 何を学ぶか決めるには

1つの分野を極めるのも良いが, 複数分野の掛け合わせが強いぞ! という感じの内容.

他者が持つ知識と差別化を行い, 自分の知識の価値を高めよう. といった感じの内容.

所感

自分なんかは去年くらいにどの分野を極めればわからず悩みまくっており, その際に10人以上のエンジニアや人事の人と話した結果, 1つの分野を極めるだけがエンジニアではなく, 複数分野が出来たり, 他の業界の知識があることが強みになるということがわかった. まさにこの章の内容と同じだなぁと思った.

読んだ感想

有用なテクニックが学術的根拠と実例と共に紹介されており良かったと思う.

ただ, 自分はこういう本を読むだけで満足しちゃって実践しないことが多いのでしっかり実践しようと思った.

ホントはブログに書評を書く予定はなかったのだが, この本の内容を実践してみようということで書評を書いてみた.

KJ法などは実践するのが大変そうだなぁ...と感じた.

ただ, ハッカソンや個人開発において何か作りたいけどアイデアが出てこないときにはとても役に経ちそうだったので最低一回は実践してみる. (実践した感想をもしかしたらブログに書くかも)

書評に関してだが, 今回久しぶりに書いてみてそんなに手間ではない(1hくらいで書ける)のでこれから本を読む度に書こうと思う. またフォーマットはこの記事のフォーマットが自分に合っていてとても書きやすかったので次回以降このフォーマットを使って書くと思う.

この書評を書く前にScrapboxに感想や有用そうなことをまとめようと試みたが, ただ本文を移しただけみたいになってしまい, 労力に対してリターンが少なかったので止めた. この本にも書いてあったが, 人に教えるために書くことが大事ということで, やはりブログに書くのが一番だなと思った.