JUNのブログ

動いている様子

gyazo.com

シェル全体の構成

全体を超大雑把に分けると以下のようなコンポーネントに分解できます.

入力処理(readline): JUN
Lexer & Parser: torus
CommandExecution: JUN

JUNと書いてあるのが自分が主に担当した部分で, torusと書いてあるのがtorusさんが主に担当した部分です.

大まかな設計は The Architecture of Open Source Applications という本の中にあるbashの章の中のbashのコンポーネントのアーキテクチャ図を参考にしてコンポーネントを分け, その後それぞれに担当を決めました.

ここから先はこれらコンポーネントそれぞれについての説明を書くのですが, 自分が担当した部分に関しては詳細に書けるのですが, 自分が担当していない部分に関しては少し大雑把な説明になるかもしれないです.

入力処理

入力処理はreadlineを使って良いとのことなので, 使いました.

正直 readline が便利すぎてあまり入力処理について説明することは無いです. 強いて言うならシグナルハンドリングは少し気をつける必要がありますが, The GNU Readline Libraryを使ったを見ればなんとかなります.

実はこの入力処理についてはちょっとした小話があるのですが, それはまた後ほど...

Lexer & Parser

Lexer (字句解析)

Lexerとは字句解析機であり, 入力文字列を解釈し, 字句(ひとつの意味のある文字列単位)単位で取り出せるみたいな感じです. 字句はToken, 字句解析機はTokenizerとも呼ぶみたいです.

例えば入力が echo Hello I am "JUN" 'san' | cat なら以下のように取り出せるイメージです.

Token	Type
`echo`	EXPANDABLE
`Hello`	EXPANDABLE
`am`	EXPANDABLE
`JUN`	EXPANDABLE_QUOTED
`san`	NON_EXPANDABLE
`\|`	PIPE
`cat`	EXPANDABLE

Parser (構文解析)

Lexerで字句単位に文字列を取り出せるようになったのでここでは取り出した字句を元に構文解析を行い抽象構文木(AST)を作成します.

シェルが受け付ける文字列の文脈自由文法(課題に必要な部分のみ)はバッカス・ナウア記法(BNF) を用いて以下のように表される.

command_line ::=
      "\n"
    | sequencial_commands delimiter "\n"
    | sequencial_commands "\n"

delimiter ::=
      ";"

sequencial_commands ::=
      piped_commands delimiter sequencial_commands
    | piped_commands

piped_commands ::=
      command "|" piped_commands
    | command

command ::=
      arguments

arguments ::=
      redirection
    | redirection arguments
    | string
    | string arguments

string ::=
      expandable <no_space> string
    | expandable
    | not_expandable <no_space> string
    | not_expandable
    | expandable_quoted <no_space> string
    | expandable_quoted

redirection ::=
      "<" string
    | ">" string
    | ">>" string
    | "<<" string

この文法に基づいて再帰下降構文解析を行いASTを生成する.

f:id:JUN_NETWORKS:20210701232046p:plain — abc def | file < infile ; xyz ; のパース結果

CommandExecution

Lexer, Parser の処理が完了し, ASTが生成できたら今度はそれを元に実際にリダイレクションの処理やコマンドの実行などを行います.

今回は "Lexer & Parser" と "CommandExecution" を完全に分けて実装したので, ASTをそのまま使って実行するのではなくCommandExecution側で受け取りたい構造体(t_command_invocation)というのを予め定義しておき, ASTとt_command_invocationを変換する関数を最終的に作ることによって同時並行でそれぞれの担当箇所を実装できると共に, どちらか一方に変更があっても変換関数を修正すれば良いだけになります.

t_command_invocation は具体的には以下のような構造体です.

typedef struct s_command_invocation
{
    t_cmd_redirection           *output_redirections;
    struct s_command_invocation    *piped_command;
    t_cmd_redirection           *input_redirections;
    const char                    **exec_and_args;
    pid_t                       pid;
}   t_command_invocation;

t_cmd_redirection はリダイレクションに関する情報を持つ片方向連結リストの構造体です. 具体的には以下の情報を持っています.
- ファイルパス (heredocの場合は入力された文字列)
- リダイレクションの種類(追記かどうか, heredocかどうかなど)
- リダイレクションで指定されたファイルディスクリプタ
- 次のリダイレクションへのポインタ
piped_command はパイプの次のコマンドへのポインタです.
exec_and_args は実行するプログラムに渡す文字列配列です. int main(int argc, char **argv) と書いたら受け取れる argv の部分です.
pid はコマンド(プログラム)が子プロセスで実行された時のプロセスIDです. fork() して作成した子プロセスを wait() して終了ステータスを取得するために使います. あと, fork()して作成した子プロセスを正しくwait()してあげないとゾンビプロセスになってしまうのでこれを避けるためにも子プロセスのpidは必要です.

リダイレクションの処理

リダイレクションの処理は基本的には dup2() などを使って標準入出力のfd(2>や3<みたいなfd指定の場合は指定のfd)をファイルのfdに置き換えれば出来ます.

気をつけるべき点としては, bashでは複数リダイレクションが存在する時, そのfdのリダイレクションの中で最後リダイレクションのみが書き込みや読み込みが行われることです.

bash で echo hello > file1 > file2 > file3 と実行するとfile1とfile2はファイルは作成されるが, 何も書き込まれておらず, file3にのみ"hello"が書き込まれています. ちなみにzshの場合だと全てのファイルに"hello" が書き込まれるという違いがあります.

入力の場合も同様で, cat < file1 < file2 の場合, 実際にcatコマンドの標準入力に繋がれるのは file2 のみです.

heredocument

heredocument はbash特有の概念ではなく, いろんな言語に実装されている.

要は複数行文字列リテラルということみたいです. bashにおいては << と区切り文字の組み合わせで始まり, もう一度区切り文字が出現するまでの文字列をコマンドの標準入力に流し込むというものになっています.

f:id:JUN_NETWORKS:20210701040100p:plain — heredocumentの例

f:id:JUN_NETWORKS:20210701040157p:plain — 複数heredocumentの例

f:id:JUN_NETWORKS:20210701040746p:plain — パイプとheredocumentを組み合わせた例

まぁ大体雰囲気はこんな感じです.

で, 実装の方なんですが, heredocumentの入力タイミングはParserの後, ASTをt_command_invocationに変換する関数内で行うようにしました. つまり, cat << EOF はparserが処理して, そこから先入力される文字列はParserではなくCommandExecution側で入力を受け付けて, 入力された文字列を構造体のメンバに保存します.

fd周りについてですが, ファイルのリダイレクションだとopen()すればよいのですが, heredocument はファイルを入力としているわけではないので, リダイレクションとは分けて考えるべきです.

しかし, 最初どういう風に実装されているか全然わからなかったのでbashのソースコードを見に行きました. そうするとどうやら親プロセスから子プロセスに対してheredocument用のpipeを繋いで文字列を渡しているようです.

先程紹介した "パイプとheredocumentを組み合わせた例" を例に図にすると以下のような感じです.

f:id:JUN_NETWORKS:20210701170325p:plain

パイプラインのコマンド間のパイプ以外にも, シェルのプロセスと子プロセス間のheredocument用のパイプを作成し, そのpipeに対してheredocumentで入力された文字列をwrite()することで実現出来ます.

プログラムの実行

今回自分はシェルのパイプラインの実装はループで子プロセスを生成していくやり方にしました. echo hello | wc -l | cat を例として考えると以下の様になります.

f:id:JUN_NETWORKS:20210701171159p:plain

シェルのパイプライン処理の実装方法はいくつかあるのですが, 複数コマンドが同時に動くという点(並列実行)に気をつけましょう.

例えば bash で cat | ls とすると, catの実行が完了する前にlsの出力が先に出現します. これはcatの実行が完了してからlsを実行する逐次的な実行ではなく, cat と ls を並列に実行させているからです.

f:id:JUN_NETWORKS:20210701174911p:plain — `cat` と `ls`が同時に実行され `cat` が入力待ちになっている

ビルトインコマンド

ビルトインコマンドというのはシェル側で実装してシェルに組み込まれているコマンドです.

ビルトインコマンドの実装自体は基本的にはbashのビルトインコマンドのヘルプとかを読みながら関数として実装すれば良いです.

で, 問題となるのはコマンドそのものというよりかはビルトインコマンドの実行方法です. ビルトインコマンドは外部のプログラムを呼び出すわけではないので execvp() などはしません.

ビルトインコマンドは単体で実行される場合とパイプラインとして実行される場合で実行方法が異なります.

ビルトインコマンド単体で実行される場合はfork()せずにシェルのプロセス上で対象の関数を呼び出します.

その際にリダイレクションが含まれている場合は標準入出力をdup() などを使って保存しておき, 後に復元する必要があります. こうしないとその後標準入出力が使えなくなります.

例えば echo hello > output.txtが入力された時, もしechoが外部コマンドならSTDOUT_FILENOをopen("output.txt", O_WRONLY | O_CREAT)で出力先ファイルのfdを使ってdup2(fd, STDOUT_FILENO) のように置き換えれば良いだけです. なぜなら外部コマンドを実行しているプロセスはシェルのプロセスではなく, シェルのプロセスからfork()された子プロセスであり, 子プロセスのfdがどうなろうと親プロセスには影響しないからです.

しかし, シェルのプロセスで実行するビルトインコマンドは話が違います. そのまま愚直にdup2(fd, STDOUT_FILENO)などとしようものなら標準出力はcloseされ, その後シェルが標準出力に書き込む手段が無くなります. なのでこのような悲惨な事態を避けるために dup(STDOUT_FILENO) のようにリダイレクション用のfdとは別に標準入出力のfdを複製して保持しておきます. そしてリダイレクションの処理を行っている時に複製した標準入出力のfdとリダイレクションで指定されたfd(2> みたいなやつ)が被ったらもう一度dup(複製した標準入出力のfd)をしてからファイルのfdに置き換えることで標準入出力のfdを失わないようにしながらリダイレクションを処理する必要があります.

そしてリダイレクションなどの処理が終わり, ビルトインコマンド関数の実行が完了したらリダイレクション用に開けていたfdを閉じて, 標準入出力のfdを元のfdに戻して完了です.

このようにビルトインコマンド単体の場合はシェルと同じプロセスで実行されるためリダイレクション周りなどは注意を払う必要が有ります.

次にパイプラインの中にビルトインコマンドがある場合, 例えば echo hello | cat のような場合です.

この場合, 外部コマンドを実行する時と同じ様にfork()して子プロセスを生成します. 違いはexecvp()で外部のプログラムを読み込んでメモリを別のプログラムに置き換えることはせず, ビルトインコマンドに対応した関数を呼び出して終了する点です.

ここまでの話で説明したとおりビルトインコマンドは単体の場合はシェルのプロセスで, パイプライン内の場合はシェルの子プロセスで実行されます. そして子プロセスの環境変数やfdの変更, メモリの操作, カレントディレクトリの変更は親プロセスに影響しません.つまりどういうことが起きるかというと, 以下のようなことが起きます.

f:id:JUN_NETWORKS:20210701215039p:plain — bashでの実行例

パイプライン内で export した環境変数が反映されていませんね. これは export は環境変数を追加したけれど, コマンドがパイプライン内にあるのでexportは子プロセスで実行され, 親プロセスであるシェルのプロセス内の環境変数には反映されていないのです.

cdでも同様にパイプライン内で実行するとシステムコールchdir()が子プロセス内で実行されるためシェルのcwdは変わりません.

f:id:JUN_NETWORKS:20210702031526p:plain — bashでの実行例

こういうのを知るとなぜ export や unset, cdなどがビルトインコマンドとしてシェルに組み込まれているかがわかりますね.

その他

環境変数の保持方法

初めのころは, 環境変数は文字列配列environをそのまま保持していて, 環境変数を追加する時は文字列配列のメモリ領域を確保し直し(課題の制約でrealloc()は使えないので), environにもともと入っていたデータを新しい配列にコピーしその後最後の要素に新しい環境変数の文字列("key=value"形式)を入れるようにしていました.

しかし, この方法はおすすめできません. なぜなら環境変数の取得や追加, 削除などの操作に多くの手間が必要になりバグの原因になりますし拡張性が低いです. なので良い子は連結リストやハッシュテーブルなどの扱いやすいデータ構造で環境変数を保持しておき, コマンドを実行する時に文字列配列に変換する関数を作りましょう.

今回自分は連結リストで環境変数を保持するようにしました. 速度ガー! って思うかもしれませんが, 環境変数の数なんて大して大きくなることは無いはずなので問題ないと判断しました. (問題が起きそうなら別のデータ構造に変えればいいだけ)

typedef struct s_var {
    const char            *key;
    const char            *value;
    bool               is_shell_var;
    struct s_var       *next;
}                       t_var;

入力処理に関しての小話

入力処理に関してはreadlineを使ったから苦労してない的なことを書きましたが, 実は自分のチームが課題を始めたころはreadlineは使えずTermcapを使って実装する必要がありました. (Termcapの部分はtorusさんがやってくれました)

このtermcapがかなり曲者のようでして, 入力処理の実装はかなり苦労していました. しかし, 自分達が課題を提出直前に課題変更があり, readlineが使えるようになりTermcapを使う必要が無くなったのと, 課題要件にheredocの追加が行われ, 話し合った結果Termcapによる入力処理の実装は破棄し, readlineによる入力処理を実装することにしました.

課題変更前はTermcapによる入力処理と履歴機能と文字列編集の実装のためにロープ木)による文字列編集が実装されていました.

GitHub - torus/42-minishell at termcapありのバージョンからTermcapを使ったバージョンのコードが見れます. (heredocumentは実装されていません)

豆知識

ここではminishellをやる上で役に立つかもしれない豆知識を書いておきます. (自分用の備忘録でもある)

bashのコードリーディング

bashのコードは1996年頃に書かれていて, 現代のC言語のコードとは書き方が一部異なっており, それを知らないととても読みづらいです.

具体的には

インデントのサイズはスペース8
古いC言語の規格では引数の型は関数ヘッダーの次の行に書く必要がある.

この書き方をK&Rスタイルと言うらしいです.

なのでbashのコードを読む時はエディタのインデントサイズを8にして, 古いC言語の書き方を頭の片隅に置いておくとスムーズにコードが読めると思います.

GNUフラグパーサー

echo -n -n hello や echo -nnnn hello と書いた時に echo -n hello と同じ挙動をするのはGNUのフラグパーサーライブラリであるgetoptの仕様によるものである.

www.gnu.org

完走した感想

いやー, 長かった. 4月に課題に取り組み始めてから提出するまで約3ヶ月かかりました. まぁ3ヶ月の間全てminishellやっていたというわけではなく競プロやったりフラクタルの実装したりちょくちょく寄り道したりしてましたが, それでも大変でした.

コミット数も42の課題では初めて1000コミット超えました. まぁPRやrevertなどのコミットがいっぱい入っているので全てのコミットがコードの実装を含んでいるというわけでもないですが.

この課題をするまでシェルというものが自分で実装できるものというイメージは全くありませんでしたが, 今回実装してみてシェルの内部での処理やUNIXプログラミングについて少し詳しくなり, シェルくらい頑張れば実装できるっしょっていう気持ちになりました.

また, 今回シェルを作ったことでこの課題に取り組む前と後でシェルに対する意識が大きく変わったように思えます. 課題に取り組む前は, シェルはブラックボックスって感じで, とりあえずなんか知らんけどコマンドを入力したら実行してくれるって感じでしたが, 今では内部でどのような処理が行われているかがわかっているためシェルを触っている時にシェルの実装側からの視点というものがわかるようになった気がします.

この記事ではあまり深堀りしてませんでしたが, cdを含むいくつかのビルトインコマンドはbashのhelpコマンドでは出てこない挙動などがあり, それを知るためにbashのソースコードを読んだりもしました. コミットが25年前(1996年)とかが普通にあり, 自分より年上のコードを読むのは新鮮でした. 25年前ともなると現在のC言語の文法やインデントスタイルなどが違っていたりして読むのが大変でした.

今回始めてUNIXプログラミングと呼ばれるものを行っったのですが,「詳解UNIXプログラミング」という本がとてもとても役に立ちました.

詳解UNIXプログラミング第3版

作者:W. Richard Stevens,Stephen A. Rago
翔泳社

Amazon

UNIXとはなんぞやという説明からUNIXにおけるファイルの扱い, シグナルやプロセス等々...UNIXプログラミングを行う上で必要な知識がここに書かれています. この本のおかげでminishellなんとかクリア出来たと言っても過言では無いくらいに役に立ちました. (自分の中では勝手に聖書と呼んでいます)

また, 今回一緒にチームを組んだtorusさんはキャリアの長いプログラマーの方で, 多くのことを教えて頂き大変勉強になりました. 豆知識のセクションに書いてある知識はtorusさんから教えてもらったものだったりします.

あと, 提出する直前で課題が大幅に変更されたのは堪えました. 特にtorusさんはその時点で既にTermcapに関わる入出力関係のコードを数週間掛けて千行以上書いていました. しかし, Termcapでの入出力をheredocに対応させる(複数行入力対応)こととreadlineの実装に切り替えるという2つの選択肢を考えた時に, ここまで書いてきた千行以上のコードを破棄し, readlineでの実装に舵を切ったのは凄いなぁと思いました. もし自分だったら惜しくて既存のコードに固執してしまうかもしれません.

f:id:JUN_NETWORKS:20210702013616p:plain — Termcapの削除に関するPR

今回の課題は今までの課題で一番重く, 実装量も多いため記事内で全てを解説しませんでした. 具体的なコードが見たい人はGitHubのリポジトリを見てください.

とても大変でしたが, やりがいと学びのある良い課題でした.

といったところで今日はこのへんで. ではでは〜〜👋👋

参考リンク

bash関係

シェル関係

パーサー関係

readline

Termcap

その他

2021-06-18

AWS Academy Cloud Foundations 修了した

42TokyoでAWSから提供されている学生向けプログラム AWS Academy Cloud Foundations が受講可能だったので受講して修了したので完走した感想.

AWS Academy Cloud Foundations とは

AWS Academy Cloud Foundations とはAWSが学生向けに提供している教育プログラム AWS Academy のうちの1つ.

aws.amazon.com

内容としては Cloud Foundations というくらいなので基礎的な内容が多い. AWSアカウントの登録から初期設定, ネットワークの基礎知識とVPC, EC2やS3, Lambda, オートスケーリング, それらクラウドサービスを使うことによって生じるメリットと従来のオンプレミスとの比較など.

基本的に各章の構成は動画とラボ(後で説明), PDF, 知識確認テストという感じ.

動画は AWS Academy の人が色々解説してくれる. PDFはその動画内で使ってるスライドが見れる. 知識確認テストはAWS認定試験の一部問題を抜粋しているっぽかった

で, ラボなんだけど, これがめっちゃ良かった. このラボというのはAWS側が学生用に一時的なAWSのサンドボックス環境を提供してくれて, そこで試せるって感じ.

個人でAWSを試しに触ってみるってセキュリティ対策やら請求額のモニタリングとアラームとか何も知識が無い初学者には少しハードルが高い気がするので, こういう環境でお金やセキュリティのことを心配せずにAWSのサービスを実際に触れるのはとても良いと思った.

完走した感想

自分は昔バイトでMLOps用にAWS アーキテクチャを設計したことがあり, AWSを全く触ったことがないというわけではなく, このコースの範囲なら割と知っている内容が多かった. でもちょくちょく知らないサービスがあったり, なんとなく使い方までは知っているけど他サービスとの違いとか新しいことを知れたので良かった. あと, 単純にここ1年くらいAWS触ってなかったので復習にもなって良かった.

このコースはAWSを触ったこと無い人にとっては最高の教育プログラムだと思った. ラボの説明のところでも書いたけど, AWSをいきなり一人で触ると請求アラームの設定やIAM垢の設定などが大変だと思うので, 個人で触る前にこういうコースである程度AWSの概要とある程度のベストプラクティスを知ってから触ると安心してAWS触れそうだし, 始めの第一歩としてこのコースはとても良いと感じた.

ただ, ある程度AWSでの設計や運用をしたことある人からしたら知ってることが多くて物足りないかも? (まぁ Cloud Foundations コースなのでそりゃそうですが)

個人的にはAWS アーキテクチャの設計について深く知りたかったなぁと思ったら, AWS Academy Cloud Architecting というコースが Cloud Foundationsコースの次にあるらしく, 恐らくこれがアーキテクチャ設計とかに関してのコースだと思う.

AWS Academy Cloud Architecting

この中級レベルのコースでは、AWS で IT インフラストラクチャを構築するための基礎を学び、学生が AWS 認定ソリューションアーキテクト – アソシエイトの認定を取得するために必要なスキルを習得するのに役立ちます。このコースには、講義やハンズオンラボ、およびプロジェクト作業を通じて配信される約 40 時間のコンテンツが含まれています。

学生には、このコースを受講する前に、AWS Academy Cloud Foundations または同等のコースを受講することをお勧めします。

AWS Academy

まぁ, てな感じでAWSの復習と少し抜けていた知識などが補填出来て満足でした.

後Certificationバッジがもらえてそれがカッコよくて良いです.

という感じで AWS Academy Cloud Foundations を楽しく修了しましたよーというお話でした.

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

2021-06-12

フラクタル((マンデルブロ|ジュリア)集合)生成プログラムを書いた

42 C/C++

42の課題でフラクタル(マンデルブロ集合とジュリア集合)を描画する課題があり, それが完了したので感想とか色々.

フラクタルとはなんぞや

Wikipediaによると

図形の部分と全体が自己相似（再帰）になっているものなどをいう。

フラクタル - Wikipedia

らしいです.

以下のようなやつとかですね.

I, Avenafatua, CC 表示-継承 3.0, リンクによる

まぁ他にもフラクタルはいくつか種類があったり, 数学的な定義とか色々ありますが, まぁズームしていくと終わりが無くどんどん図形が出てくるやつのことです.

So Doge. Much fractal.

imgur.com

マンデルブロ集合

で, マンデルブロ集合 (Mandelbrot set) とはなんぞやという話ですが, マンデルブロ集合とは以下の漸化式が $n \rightarrow {\infty}$ で発散しない集合のことです.

$\begin{cases} {Z_{n+1} = Z_{n}^2 + C}\\ {Z_0 = 0} \end{cases}$

ここで $Z$ と $C$ は複素数の式 $a + bi$ です. また, $C$ は複素数平面上の座標に対応しています.

マンデルブロ集合のわかりやすい説明は以下の動画とサイトがわかりやすいです.

azisava.sakura.ne.jp

で, 実装するときには $n \rightarrow {\infty}$ が発散するかどうかを判定しようとすると永遠に終わらないので, 適当に $n \rightarrow 100$ とかにします. また, 発散するかどうかの判定は $|Z_n|$ が2を超えなければ集合に入っているということにします.

なんで2にしたかというと, マンデルブロ集合が実数, 虚数共に-2から2の範囲にあるからです.

で, これをコードとして書くと以下のような図が出てくるわけです.

f:id:JUN_NETWORKS:20210612144640p:plain

これを拡大していくと再帰的にどんどん色んな形が描画されていくのです.

ジュリア集合

ジュリア集合は基本的なコンセプトはマンデルブロ集合と同じです. 違う点は, $Z$ と $C$ の扱いで, ジュリア集合では $Z$ を複素平面上の座標に対応させ, $C$ が定数となっています.

以下の動画がめっちゃわかりやすいので見ると良いです.

たとえば $C=0.4-0.325i$ とすると以下のような形が出てきます.

f:id:JUN_NETWORKS:20210612145154p:plain — C=0.4-0.325i

$C=-0.8+0.156i$ だと以下のような形が出る.

f:id:JUN_NETWORKS:20210612145752p:plain — C=-0.8+0.156i

こんな感じで $C$ を変えると $C$ の値によって色んな形が出現します.

今回自分はマウスの座標によって $C$ の値を変えれるようにしました.

はい. かっこいい.

バーニングシップ

課題のボーナスで「更にもう一個別のフラクタル作りなはれ」というのがあったのでバーニングシップ(Burning Ship)というのを作りました.

基本的なコンセプトはマンデルブロ集合と同じなのですが, イテレーションごとに行う計算( $Z_{n+1}$ を求める計算)が少し違います.

$\begin{cases} {Z_{n+1} = (|Re(Z_n)| + i|Im(Z_n)|)^2 + C}\\ {Z_0 = 0} \end{cases}$

イテレーションごとに行う計算でそのまま2乗するのではなく, 絶対値を取るのがマンデルブロ集合との違いです.

これを実装して描画すると以下のような図形が出てきます.

f:id:JUN_NETWORKS:20210612154839p:plain

燃えてる船(Burning Ship)っぽいですね.

これを拡大していくと

再帰的にどんどん船の形が出てきますね! かっこいい!

ただ, バーニングシップに関しては深くズームしまくると途中で行き止まりに当たるんで実装が正しくない可能性があるかも.

色付けに付いて

マンデルブロ集合, ジュリア集合, バーニングシップは実装自体は難しくないです. ただ, 美しく描画するとなるとむずいんすよね...

今回の課題でも一応 color range shift を実装するという項目があったので, 単純にイテレーション回数に応じてHSVの色相(Hue)を変えるというので実装していて, 綺麗ではあるんですがYouTubeとかに上がっている動画の方みたいに綺麗なものを実装するのはなかなか難しそうです.

f:id:JUN_NETWORKS:20210612162636p:plain — 自分の実装

By Maxter315 - Own work, CC BY-SA 4.0, Link

Wikipediaにマンデルブロ集合の色付けについての記事があったので見てみたのですが, 色付けって奥が深いですね...

完走した感想

完走した感想ですが, 楽しかったです(小並感).

マンデルブロ集合, ジュリア集合の描画に関しては1日で実装できましが, マウスのカーソルの場所に向かってズームする処理(Google map的なアレ)がくっそむずかったです.

というのも最初はズーム倍率と中心座標を保持してその値を変えることによって実現させようと思ったのですが, まる一日やっても上手くいかず, 結局ggったり他の人のコード読んだりして最終的には描画する左右上下両端の値(min_re, max_re, min_im, max_im)を保持し, それらを使って描画するようにしました. そこにマウスのウィンドウサイズからの相対座標を使って掛けたり割ったりしてうまいことズームしたり平行移動したりするようにしました.

あと, ループ内で変数代入するタイミングをミスってデバッグに1日溶かしました.

とか色々あって大体4日くらいかかりました.

この課題以外にも2Dゲームの課題とかがあったのですが, ジュリア集合のGIFアニメーションがかっこよすぎたのでこの課題にしました.

マウスで $C$ の値を変動させるというのは課題要件に無いので別にやる必要はなかったのですが, かっこいいを求めてやりました. 結果的にはかっこよくなったので大満足です.

この課題はそこまで重くない課題なので最初は記事を書くモチベはさほどなかったのですが, 実は提出するのをやらかしてLinterに引っかかって0点を食らったので供養のために書いていたりしますw

f:id:JUN_NETWORKS:20210612165431p:plain

ちゃんと課題提出前に確認するのと, 眠い時はちゃんと寝ましょう.

それではまた次の記事でお会いしましょう. ではでは〜👋👋

2021-04-30

GitHub PullRequest を簡単にローカルにfetchできる設定

git 備忘録

github の PullRequest を簡単にローカルに落とせる設定を書いたのでメモ.

設定

~/.gitconfig に以下の内容を追加する

[alias]
  pr = "!f() { if [ !${2+x} ]; then git fetch origin pull/${1}/head:pr/${1} ; else git fetch ${2} pull/${1}/head:pr/${1} ; fi }; f"

何をしているかというと,

引数が1つの場合は origin から${1}番プルリクエストを pr/${1} という名前でfetchする.
引数が2つの場合は ${2} からfetchする. それ以外は引数が1つの場合と一緒.

ホントは引数1つの場合, origin ではなくデフォルトのリモートリポジトリにしたかったんだけど, デフォルトのリモートリポジトリ名の取得方法がわからんのでな... (.git/config を解析して情報取り出せばいけると思うけど)

自分の.gitconfig は以下のリンクから見れます.

Winny　天才プログラマー金子勇との7年半 (NextPublishing)

使い方

git pr {PR番号} という風に実行すれば良い. 例: git pr 73

また, origin以外から取得する場合は git pr {リモートリポジトリ名} {PR番号} とすればできる. 例: git pr remote2 73

f:id:JUN_NETWORKS:20210430214029p:plain

参考にしたサイト

qiita.com

参考にしたというか, この記事のコマンドを簡単に使えるようにした感じ.

2021-04-29

「Winny 天才プログラマー金子勇との7年半」を読んだ

読書感想文

「Winny 天才プログラマー金子勇との7年半」という本を読んだので感想.

作者:壇俊光
発売日: 2020/04/24
メディア: Kindle版

金子勇については多くの記事があるので, 気になる人は以下の記事などを読んでみてください.

wired.jp

www.newsweekjapan.jp

感想

この本は2004年から2011年の約7年間に渡って行われたWinny裁判についての本である.

この本の中で金子勇という人物の人物像や経歴, 思想などが垣間見えたが, 本当に優秀なプログラマーだったんだなぁと思うと同時に, こんなに優秀な人間を日本のおかしな司法が潰してしまったのかと悲しくなってしまった.

家宅捜索から事情聴取, 裁判中にいたるまで如何にに京都府警と京都地裁が狡い手を使い, 金子勇を罪人と陥れようとしていたのが見えて胸糞が悪かった. 日本の刑事裁判の起訴後有罪率は99.9%と言われているが, この数字はこのような異常な取り調べによるものなんだなだとしたら日本の司法制度は相当狂っていると感じた.

また, 本書は裁判やその周辺について時系列順で語っているのだが, その中で金子勇が裁判に時間を費やしている中で世間ではiTunesやYouTubeが誕生し, P2PをベースとしたSkypeが誕生し, mixiからTwitterに移行し, と裁判に拘束される彼を余所に時代が流れ, 技術が進歩していくのが残酷だった. もし, 彼がこの7年間を裁判のためではなくコードを書くことに使っていたらどうなっていたかなど誰にもわかりはしないが, 少なくとも今のようなアメリカの後追いをするだけの日本ではなく, ソフトウェアに関するいくつかの分野で最先端をいくような未来があったのかなと思ってみたりした.

このWinny事件もそうだが, この事件にに限らず, 自分が知っている近年の事件でも, 「アラートループ事件」や「Coinhive事件」などがあり, 日本の司法や警察は本当に何も学んでいないんだなと思った.

jun-networks.hatenablog.com

金子勇が後継の技術者のために7年という時間を費やして戦ってくれたのに, 日本の司法行政は何も変わっていなくて悲しい気持ちと同時に正直諦めの気持ちがある.

また, 日本国内で何かしらの成果物を公開する際, 特にそれが最先端の技術を含む場合には Coinhive事件と同じ道を辿る可能性がある(逮捕されるかもしれない)ので, 日本国内でコードを書くなら最低限被疑者となった際の権利や原則, それらに関する法律や憲法などは頭に入れておいた方が良いと思った.

ascii.jp

www.atmarkit.co.jp

日本国内でコードを書いていたらある日突然逮捕されるというのは冗談ではなく本当にありえることだと思うので, 一度上記の記事のどちらかを軽く読んで頭の片隅においておくと実際に逮捕された時に少しは役に立つかも知れません. (逮捕されないのが一番ですが...)

結局「出る杭は打たれる」というのが日本なのだと思った. それと同時に, 本当に優秀な人, 特に新しい技術の研究開発を行っている人は日本ではなく, 人類のために予算が潤沢で新しい技術などに理解がある(と自分は思っている)米国などで研究開発してほしいという自分の個人的な意見がさらに強くなった.

完走した感想

という感じで「Winny 天才プログラマー金子勇との7年半」を読んだ感想でした.

この本はWinny事件の裁判に対する弁護士側からの視点の本でしたが, コードを書く開発者側の人間としてはWinny自体に興味があったりするので, 本書の中でも言及されていた金子勇が裁判のために書いた本「Winnyの技術」というのがあり, こちらはWinnyのプログラムやそれに使われている技術について書かれているようなのでまた今度読んでみようと思う.

Winnyの技術

作者:金子勇
メディア: 単行本

本書及びこのこの裁判は "駄目な司法が天才プログラマーを潰す" という読んでいて気持ちの良いものではないけれど, 日本の情報技術の発展ために戦ってくれた偉大なプログラマーについては少し知っておくべきではないだろうか. 是非興味があったら読んでみてください.

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

2021-04-16

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

読書感想文

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

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

作者:ジョンマコーミック
発売日: 2013/10/10
メディア: Kindle版

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

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

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

検索エンジンのインデクシング
ページランク
公開鍵暗号法
誤り訂正符号
パターン認識
データ圧縮
データベース
デジタル著名
決定不可能性 (これはアルゴリズムではないが, 関連する大事な話だった)

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

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

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

infolab.stanford.edu

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

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

誤り訂正符号

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

データ圧縮

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

データベース

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

パターン認識

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

決定不可能性

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

2021-04-02

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

42 C/C++

初めに

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

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

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

ではやっていくぞー.

初めに
miniRTの概要
- rtファイルについて
レイトレーシングについて
実装
完走した感想
参考にしたサイト

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: 四角形平面の色

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

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

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

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

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

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

knzw.tech

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

youtu.be

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

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

のようになっている.

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

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

実装

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

実装順としては

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

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

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

また実装の大筋(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);

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

色情報構造体

この先, 色の計算などを行う時に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| は成立しない．|$

レイ(半直線) の方程式

レイ(半直線)は直線と似ているが, 直線と違い終点が無い. つまり, 始点からとある方向に無限に伸びる直線である. レイは始点の位置ベクトル $\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$ の位置ベクトルは始点の位置ベクトルに方向ベクトルの実数倍を足したものとして表現できる ということである.

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

平面や球との交差判定

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

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

平面

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

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

まず, 任意の座標と任意の法線ベクトルを持つ平面というのを想像してほしいわけだが, 以下の図の $\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 = B² - 4AC] の値によって解の個数が変わる.

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

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

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

knzw.tech

レイの定義

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

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

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

球とレイの交点の描画

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

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

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)です.

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

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

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

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

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

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

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

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

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

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;

環境光

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

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

$R_a = k_a I_a$

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

$R_a = I_a$

拡散反射光

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

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

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

この法則に従えば $\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}$ は(呼び名に反して)交点から光源に向かうベクトルであることに留意せよ.

ここでなぜ角度が $\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として扱う.