úloha 050: Efektivní ray-tracing trojúhelníkových sítí

Úkolem je implementovat některou urychlovací metodu pro výpočet průsečíku paprsku s trojúhelníkovou sítí. Síť se nahravá z externího OBJ souboru a má kromě souřadnic vrcholů ve 3D definované též normálové vektory.

Základem poslouží projekt 050rtmesh z repository grcis. Je připravena aplikace, která v jednoduchém okně zobrazuje obrázek spočítaný ray-tracingem, scénu lze vybrat z předem připravených (list-box) a navíc předefinovat načítaný soubor ve Wavefront OBJ formátu stiskem tlačítka Default OBJ.
Pro doplnění Vaší implementace byl založen zdrojový soubor RtMesh.cs, do něho budete psát Váš nový kód a nakonec mi ho odevzdáte.

Relevantní interface a třídy:

ISolid - obecný interface pro tělesa, která se umí protnout paprskem.
TriangleMesh - základní implementace tělesa, které používa již dříve vytvořenou povrchovou reprezentaci scény SceneBrep a naivně počítá průsečík tak, že prochází v cyklu všechny trojúhelníky. Tento přístup budete muset změnit a použít některou urychlovací techniku.
SceneBrep - povrchová reprezentace 3D tělesa uložená v paměti (ale umí se přečíst z Wavefront OBJ formátu). Trojúhelníky jsou propojené pomocí datové struktury "corner table".

Co modifikovat: implementaci třídy FastTriangleMesh ve zdrojáku RtMesh.cs. Poznámkami jsou tam vyznačena místa, která zřejmě budete chtít modifikovat - v konstruktoru přidejte stavbu urychlovací datové struktury a dále přepište metody Intersect() a CompleteIntersection().

Podpora pro geometrické výpočty: ve třídě Geometry jsou pro Vás připraveny užitečné metody: RayTriangleIntersection(), RayBoxIntersection() resp. RayBoxIntersectionInv(). Ty používejte k získání průsečíku paprsku s jednotlivým trojúhelníkem nebo obalovým kvádrem (AABB).
Nezapomeňte inkrementovat čítače CSGInnerNode.countBoundingBoxes resp. CSGInnerNode.countTriangles počítající výpočty průseku paprsku s obalovým kvádrem resp. s jednotlivým trojúhelníkem.

Náměty: KD-tree nebo R-tree (BVH), případně Octree (oktantový strom). Varianty stromů s duplicitou jsou KD-tree a Octree, R-tree duplicitní trojúhelníky nesmí obsahovat. Používejte "bucket-tree", tj. listy s maximálně N trojúhelníky, např. 2 <= N <= 8 (nejlepší je deklarovat N jako konstantu a diskutovat její vliv na rychlost výpočtu).

Literatura pro pokročilé: R-tree (Wikipedia entry), Vlastimil Havran: Heuristic Ray Shooting Algorithms (PhD disertační páce), Ingo Wald, Vlastimil Havran: On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)

Testovací data: několik OBJ souborů (např. teapot.obj nebo pitcher.obj) je součástí naší repository. Ručně si je můžete nahrát do našeho programu, i když pro ně není připravena konfigurace scény (lze použít i komprimovaný .obj.gz formát).

TERMÍN: do 15. 7. 2012

BODY: základ 30 bodů

PROJEKT: 050rtmesh

ZDROJOVÝ SOUBOR: RtMesh.cs

[Cvičení NPGR004] [Návody k zápočtům v C#] [Přednášky a semináře] [Odkazy na demonstrace]

Copyright (C) 2011-2012 J.Pelikán, last change: $Date: 2013-11-22 23:48:14 +0100 (Fri, 22 Nov 2013) $
Send comments/requests to pepca.at.cgg.mff.cuni.cz