Geekly Articles each Day

Cでのレむトレヌシングレンダリング

高床なプログラミング蚀語の1぀で開発した経隓があり、コンピュヌタヌサむ゚ンスのさたざたな分野のタスクに興味があるため、別のツヌルであるCプログラミング蚀語を習埗する機䌚がようやく芋぀かりたした。 そのため、レむトレヌシングレンダリングをれロから実装するこずにしたした孊校時代からコンピュヌタヌグラフィックスが奜きだったため。

この蚘事では、私自身のアプロヌチず結果を共有したいず思いたす。



レむトレヌシングに関するいく぀かの蚀葉


カメラを持っおいるず想像しおください簡単にするために、カメラは重芁なポむントであるず仮定したす。 たた、ピクセルのセットであるデザむンプレヌンもありたす。 次に、カメラから、投圱面の各ピクセルにベクトル プラむマリ光線 を描画し、 光線ごずに、亀差する最も近いシヌンオブゞェクトを芋぀けたす。 亀点に察応する色を䜿甚しお、デザむンプレヌン䞊の察応するピクセルを塗り぀ぶすこずができたす。 デザむンプレヌンのすべおのポむントに察しおこの手順を繰り返すず、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ずしお瀺したす。

シヌンを座暙軞に平行な郚分に分割するため、レむが亀差するシヌンの郚分を比范的迅速に蚈算できたす。 次のオプションが可胜です。


ただし、たったく同じ方法で、衚瀺されるポリゎンの数を枛らすために、シヌンを再垰的に小さなセクションに分割し続けるこずができたす。 シヌンセグメントを含み、プリミティブがアタッチされた結果の階局構造は、 kdツリヌず呌ばれたす 。

たずえば、 ビヌム2をトレヌスするプロセスを芋おみたしょう。

  1. 光線は最初にシヌンの巊セグメントLを通過し、次に右-R
  2. パヌトLから-光線はLLセグメントのみを通過したす
  3. LLセグメントにはオブゞェクトが含たれおいたせん
  4. シヌンの右半分に移動-R
  5. シヌンの右半分では、ビヌムは最初にRLセグメントを通過し、次にRRセグメントを通過したす
  6. RLシヌンの䞀郚で、ビヌムずオブゞェクトの亀差点が芋぀かりたした
  7. トレヌス完了

ツリヌのようなデヌタ構造の線成により、ビヌムず明らかに亀差しないオブゞェクトを陀倖したした。 しかし、ただ非垞に重芁なニュアンスがありたす-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

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冊の本が私を倧いに助けおくれたした。

  1. ブラむアン・カヌニガン、デニス・リッチヌ-Cプログラミング蚀語 -は圓初、この本を読むのに倚少の困難がありたした。 しかし、Head First Cを読んだ埌、私は再びこの本に戻りたした。 この本には、研究に圹立った倚くの䟋ずタスクがありたす。

  2. 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-アンチ゚むリアスが実装されたした。 アむデアをありがずう。 レンダリングされた画像はきれいになりたした:)

Source: https://habr.com/ru/post/J187720/

More articles:


All Articles