この記事では、私自身のアプローチと結果を共有したいと思います。
レイトレーシングに関するいくつかの言葉
カメラを持っていると想像してください（簡単にするために、カメラは重要なポイントであると仮定します）。 また、ピクセルのセットであるデザインプレーンもあります。 次に、カメラから、投影面の各ピクセルにベクトル（ プライマリ光線 ）を描画し、 光線ごとに、交差する最も近いシーンオブジェクトを見つけます。 交点に対応する色を使用して、デザインプレーン上の対応するピクセルを塗りつぶすことができます。 デザインプレーンのすべてのポイントに対してこの手順を繰り返すと、3次元シーンの画像が得られます。 これらの操作のみに制限する場合、結果のアルゴリズムはレイキャスティングと呼ばれます。
再帰的レイキャスティング==レイトレーシング
- プライマリレイとシーンオブジェクトの交点から、セカンダリレイを放すことができます—光源に向けられます。 シーン内のオブジェクトと交差する場合、オブジェクトの特定のポイントは影になります。 このテクニックにより、 幾何学的に正しい影を得ることができます。
- オブジェクトに鏡面がある場合、幾何光学の法則に従って、反射光線を計算し、そのルーティング手順を（再帰的に）開始できます。 次に、鏡面反射から得られた色と表面の固有の色を混ぜます。 この手法により、 ミラーサーフェスをシミュレートできます（同様に、 透明なサーフェスをシミュレートできます ）。
- カメラからビームとシーンオブジェクトとの交点までの距離を計算できます。 距離の値を使用してフォグをモデリングできます。オブジェクトがカメラから遠いほど、色の強度が低くなります（計算では、強度を減少させる指数関数などを使用できます）。
上記の手法を組み合わせることで、非常にリアルな画像を取得できます。 また、アルゴリズムの次の機能にも注目します。
- 各ピクセルの色は、他のピクセルとは独立して計算できます（カメラから放出された光線は互いに影響を与えないため、並行して処理できるため）
- アルゴリズムには、オブジェクトのジオメトリに対する制限が含まれていません（プレーン、球、円柱などの豊富なプリミティブセットを使用できます）。
レンダリングアーキテクチャ
すべてのオブジェクトはヒープに格納されます。 レンダリングは、3Dオブジェクトへのポインターの配列で動作します（実際、すべてのオブジェクトはまだkdツリーにパッケージ化されていますが、現時点では、ツリーが存在しないと想定しています）。 現時点では、三角形と球の2種類のプリミティブがあります。
さまざまなプリミティブで動作するようにレンダーを教える方法は？
レイトレーシングアルゴリズムはオブジェクトのジオメトリに依存しません。オブジェクトの構造はレンダラーにとって重要ではありません。実際には、図形と光線の交点を計算するために必要なのは関数のみです。
OOPの観点では、これはインターフェイスの概念を使用して実装できます 。各オブジェクトは対応するメソッドの実装を提供し、さまざまなプリミティブを統一的な方法で処理できます。
Cプログラミング言語には、OOPパラダイムでプログラミングするための構文構造はありませんが、この場合、構造と関数ポインターが助けになります。
レンダリングは、3Dオブジェクトの実際のパラメーターが格納されているデータ領域へのポインターと、このデータ領域を正しく処理できる関数へのポインターを含む一般化された構造（Object3d）で動作します。
レンダリングソースからのObject3d構造の説明
typedef struct { // , // : , ( ), // : , , .. void * data; // , , // data Boolean (*intersect)(const void * data, const Point3d ray_start_point, const Vector3d ray, // Point3d * const intersection_point); // // // // :) Color (*get_color)(const void * data, const Point3d intersection_point); // ( ) // - // , - Vector3d (*get_normal_vector)(const void * data, const Point3d intersection_point); // Object3d // , // , void (*release_data)(void * data); } Object3d;
このアプローチにより、各3Dプリミティブに関連するコードを個別のファイルにローカライズできます。 したがって、3Dオブジェクトの構造を変更する（たとえば、テクスチャや法線マップのサポートを追加する）ことも、新しい3Dプリミティブを追加することも非常に簡単です。 この場合-レンダリングコードを変更する必要はありません。 カプセル化のようなものになりました。
例：レンダリングソースからの球体コード
sphere.c
// ... typedef struct { Point3d center; Float radius; Color color; } Sphere; // ... // "" Object3d * new_sphere(const Point3d center, const Float radius, const Color color) { Sphere * sphere = malloc(sizeof(Sphere)); sphere->center = center; sphere->radius = radius; sphere->color = color; // 3D Object3d * obj = malloc(sizeof(Object3d)); obj->data = sphere; // , Sphere obj->get_color = get_sphere_color; obj->get_normal_vector = get_sphere_normal_vector; obj->intersect = intersect_sphere; obj->release_data = release_sphere_data; return obj; } // // static Color get_sphere_color(const void * data, const Point3d intersection_point) { const Sphere * sphere = data; return sphere->color; } // // Bump Mapping static Vector3d get_sphere_normal_vector(const void * data, const Point3d intersection_point) { const Sphere * sphere = data; // vector3dp - , Vector3d n = vector3dp(sphere->center, intersection_point); normalize_vector(&n); return n; } // static Boolean intersect_sphere(const void * data, const Point3d ray_start_point, const Vector3d ray, Point3d * const intersection_point) { const Sphere * sphere = data; // - // GitHub } // "" void release_sphere_data(void * data) { Sphere * sphere = data; // - free(sphere); }
実装に関係なく、さまざまなプリミティブを操作する方法の例
void example(void) { Object3d * objects[2]; // , (10, 20, 30) 100 objects[0] = new_sphere(point3d(10, 20, 30), 100, rgb(255, 0, 0)); // (0, 0, 0), (100, 0, 0) (0, 100, 0) objects[1] = new_triangle(point3d(0, 0, 0), point3d(100, 0, 0), point3d(0, 100, 0), rgb(0, 255, 0)); Point3d camera = point3d(0, 0, -100); Vector3d ray = vector3df(0, -1, 0); int i; for(i = 0; i < 2; i++) { Object3d * obj = objects[i]; Point3d intersection_point; if(obj->intersect(obj->data, camera, ray, &intersection_point)) { // Color c = obj->get_color(obj->data, intersection_point); // - :-) // , // , objects! } } }
正義のために、そのようなアーキテクチャはポインタとの多くのジャグリングを伴うことに注意する価値があります。
レンダリング速度
テストの例として、シェルピンスキーピラミッドフラクタル、鏡球、テクスチャスタンドでシーンを視覚化することにしました。 シェルピンスキーのピラミッドは、レンダリング速度のテストに非常に便利です。 異なるレベルの再帰を設定することにより、異なる数の三角形を生成できます。
当初、レンダリング速度は1000ポリゴン未満のシーンでのみ満足のいくものでした。 4コアプロセッサを使用しているため、並列化によるレンダリングの高速化が決定されました。
POSIXスレッド
第一印象：Javaスレッドのセマンティクスはpthreadに非常に近いです。 したがって、POSIXスレッドモデルの理解に特別な問題はありませんでした。 スレッドプールをファイルすることが決定されました:-)
スレッドプールにはタスクのキューが含まれていました。 各タスクは、実行される関数へのリンクと引数のリストへのリンクを含む構造体でした。 タスクキューへのアクセスは、ミューテックスと条件変数によって規制されていました。 便宜上、レンダリング全体が別の関数にカプセル化されます。引数の1つはスレッドの数です：
カプセル化関数シグネチャのレンダリング
void render_scene(const Scene * const scene, const Camera * const camera, Canvas * canvas, const int num_threads); // Scene 3D , , // Camera , // Canvas 2 -
この関数には、レンダリングサイクルとスレッドプールを接続するコードが含まれていました。
- キャンバスをいくつかの部分に分割します
- キャンバスの各部分に対して、レンダリングのための個別のタスクを形成します
- すべてのタスクをプールに送信し、完了を待つ
しかし、残念ながら、2コアのラップトップでは、レンダリングが定期的にクラッシュするか、Abort trap 6エラーでクラッシュしました（4コアのラップトップでは決して起こりませんでした）。 この悲しいバグを修正しようとしましたが、すぐにもっと魅力的な解決策を見つけました。
Openmp
OpenMPは、タスクの作成と配布を処理し、レンダリングの完了を待機する障壁も編成します。 シングルスレッドのコードを並列化するディレクティブをいくつか追加するだけで十分です。ホバリングのバグはなくなりました:-)
ソースレンダリング機能
void render_scene(const Scene * const scene, const Camera * const camera, Canvas * canvas, const int num_threads) { const int width = canvas->width; const int height = canvas->height; const Float focus = camera->focus; // omp_set_num_threads(num_threads); int x; int y; // , :-) #pragma omp parallel private(x, y) #pragma omp for collapse(2) schedule(dynamic, CHUNK) for(x = 0; x < width; x++) { for(y = 0; y < height; y++) { const Vector3d ray = vector3df(x, y, focus); const Color col = trace(scene, camera, ray); set_pixel(i, j, col, canvas); } } }
レンダリングは少し加速しましたが、残念ながら、1000を超えるプリミティブを含むシーンは依然として非常にゆっくりとレンダリングされていました。
光線とプリミティブの交差の誤計算は、比較的リソースを消費する手順です。 問題は、シーンのすべてのプリミティブとの各光線の交差点がチェックされることです（光線が交差する最も近いプリミティブが検索されます）。 光線が正確に交差しないオブジェクトを何らかの方法で除外することは可能ですか？
Kdツリー
オブジェクトのあるシーンを「左」と「右」の2つの部分に分割しましょう（それぞれLとRとして示します）。
シーンを座標軸に平行な部分に分割するため、レイが交差するシーンの部分を比較的迅速に計算できます。 次のオプションが可能です。
- ビームはシーンLの一部のみを通過します
パートRに含まれるオブジェクトは表示できません
（写真のビーム1）
- ビームはシーンRの一部のみを横切る
パートLに含まれるオブジェクトは表示できません
（写真のビーム3）
- ビームは最初にシーンLの一部を通過し、次にシーンRの一部を通過します
まず、シーンLの一部に属するオブジェクトを調べます。交差点が見つかった場合、シーンRの一部に属するオブジェクトは表示できません。 レイがパートLのオブジェクトと交差しない場合、パートRのオブジェクトを表示する必要があります
（写真のビーム2）
- 光線は最初にシーンRの一部を通過し、次にシーンLの一部を通過します
前バージョンと同じ交差点検索ロジック（最初にシーンRの一部を検討する場合のみ）
ただし、まったく同じ方法で、表示されるポリゴンの数を減らすために、シーンを再帰的に小さなセクションに分割し続けることができます。 シーンセグメントを含み、プリミティブがアタッチされた結果の階層構造は、 kdツリーと呼ばれます 。
たとえば、 ビーム2をトレースするプロセスを見てみましょう。
- 光線は最初にシーンの左セグメント（L）を通過し、次に右-R
- パートLから-光線はLLセグメントのみを通過します
- LLセグメントにはオブジェクトが含まれていません
- シーンの右半分に移動-R
- シーンの右半分では、ビームは最初にRLセグメントを通過し、次にRRセグメントを通過します
- RLシーンの一部で、ビームとオブジェクトの交差点が見つかりました
- トレース完了
ツリーのようなデータ構造の編成により、ビームと明らかに交差しないオブジェクトを除外しました。 しかし、まだ非常に重要なニュアンスがあります-kdツリーの有効性は、シーンをどのようにパーツに分割するかに依存します。 シーンを分割する場所を選択する方法は？
表面積ヒューリスティック
レイがシーンのセグメントに入る確率は、そのセグメントの面積に比例します。 シーンのセクションに含まれるプリミティブが多いほど、レイがこのセグメントに到達するときに、より多くの交差点を計算する必要があります。 したがって、分割の基準を定式化できます。プリミティブの数と、それらが含まれるセグメントの面積の積を最小化する必要があります。 この基準は、 表面積ヒューリスティック （SAH）と呼ばれます。
簡単な例を使用して、実行中のヒューリスティックを見てみましょう。
したがって、SAHを使用すると、空のスペースと3Dオブジェクトを効果的に分離できます。これは、レンダリングパフォーマンスに非常に良い影響を与えます。
観察
レンダリングでは、画像の1ピクセルあたりの平均交差数を計算する機能が実装されています：光線とオブジェクトの交差が計算されるたびに、カウンター値が増加し、レンダリングの終了時に、カウンター値が画像のピクセル数で除算されます。
得られる結果はシーンによって異なります（kdツリーの構築はプリミティブの相対位置に依存するため）。 グラフは、プリミティブの数に対する画像の1ピクセルあたりの平均交差数の依存性を示しています。
この値は、シーンに含まれるプリミティブの数よりもはるかに少ないことに気付くことができます（kdツリーがない場合、各レイについてN個すべてのプリミティブとの交差点を探す必要があるため、線形依存性があります）。 実際、kdツリーを使用して、レイトレーシングのアルゴリズムの複雑さをO（N）からO（log（N））に減らしました。
正義のために、このソリューションの欠点の1つはkdツリーの構築のリソース消費であることに注意する価値があります。 しかし、静的なシーンの場合-これは重要ではありません：シーンをロードし、ツリーが構築されるのを待ちます-そして、シーンの周りをカメラで移動できます:-)
16386の三角形を含むシーン：
モデルをダウンロードする
多数のプリミティブをレンダリングすることを学んだ後、3Dモデルをロードすることが望まれました。 かなりシンプルで広範囲の形式が選択されました-OBJ ：モデルは、頂点のリストとポリゴンのリストを含むテキストファイルに格納されます（各ポリゴンは、頂点のリストのポイントによって定義されます）。
非常に単純なモデルの例：tetrahedron.obj
＃四面体
＃頂点：
v 1.00 1.00 1.00
v 2.00 1.00 1.00
v 1.00 2.00 1.00
v 1.00 1.00 2.00
＃三角形：
f 1 3 2
f 1 4 3
f 1 2 4
f 2 3 4
＃頂点：
v 1.00 1.00 1.00
v 2.00 1.00 1.00
v 1.00 2.00 1.00
v 1.00 1.00 2.00
＃三角形：
f 1 3 2
f 1 4 3
f 1 2 4
f 2 3 4
OBJ形式のパーサーを作成する過程で、多くのモデルにはポリゴンの各頂点への法線のリストも含まれていることがわかりました。 頂点の法線ベクトルを補間して、ポリゴンの任意の点で法線ベクトルを取得できます-この手法により、滑らかな表面をシミュレートできます（ フォンシェーディングを参照）。 この機能は、現在のレンダーアーキテクチャのフレームワーク内で非常に簡単に実装できました（Triangle3d構造に法線ベクトルを追加し、ポリゴンの任意のポイントに対してそれらを補間する関数を記述する必要がありました）。
レンダリングソースからのTriangle3d構造
typedef struct { // Point3d p1; Point3d p2; Point3d p3; // , // - Vector3d norm; Color color; Material material; // - , color Canvas * texture; // // , Point2d t1; Point2d t2; Point2d t3; // // Vector3d n1; Vector3d n2; Vector3d n3; // // } Triangle3d;
約19,000個のポリゴンを含むレンダリングシーンの例：
約22,000のポリゴンを含むレンダリングされたシーンの例：
楽しみのために、 スカイボックスを追加して車のモデルをロードすることにしました。
シーンには約100,000個のポリゴンが含まれています（kdツリーは数分で構築されました） 
おわりに
Cの学習中にこのタスクを選択したことは嬉しいです。言語のエコシステムのさまざまな側面を学び、美しい結果を得ることができたからです。
Githubレンダリングソース： github.com/lagodiuk/raytracing-render （プロジェクトの説明-デモの開始方法）。
勉強の過程で、2冊の本が私を大いに助けてくれました。
- ブライアン・カーニガン、デニス・リッチー-Cプログラミング言語 -は当初、この本を読むのに多少の困難がありました。 しかし、Head First Cを読んだ後、私は再びこの本に戻りました。 この本には、研究に役立った多くの例とタスクがあります。
- Dawn Griffiths、Dawn Griffiths-Head First C -Cエコシステムの一般的なビジョン（メモリの配置方法、OSレベルでの動作、make、valgrind、POSIXストリーム、ユニットテストが一般的な用語で説明されているため） 、Arduinoについては数ページもあります）
また、Cのニュアンスのいくつかについてのアドバイス、および（GLUTを使用した）レンダリング用の記述されたフロントエンドについて、ウィンドウにシーンを表示し、キーボードを使用してカメラを移動および回転させるdmytrishに感謝します。
また、非常に便利なリソースをお勧めします： ray - tracing.ru-ここでは、アクセス可能な形式で、フォトリアリスティックレンダリングに使用されるさまざまなアルゴリズムが使用されます（特にkdツリーとSAH）。
PS
レンダリングの開発中に作成されたいくつかのビデオ：
霧の中のシェルピンスキーのピラミッド
キューブ、男、ランタン、ティーポット、シェルピンスキーピラミッド:-)
UPD：
ツリーの構築を加速することが判明しました。 コメントスレッドの詳細： habrahabr.ru/post/187720/#comment_6580722
UPD 2：
このコメントスレッドで議論した後： habrahabr.ru/post/187720/#comment_6579384-アンチエイリアスが実装されました。 アイデアをありがとう。 レンダリングされた画像はきれいになりました:)
