BSPs voor VSD?

[Shapeshifter]

Ik zit hier met een ray tracer die geschreven is door een paar collega's in MATLAB en de vraag of deze sneller kan. Sowieso gaat er een deel in C++ geschreven worden waarbij er qua implementatie al een en ander geoptimaliseerd kan worden, maar ik zit nu ook naar het algoritme zelf te kijken om erachter te komen of daar wat te halen valt.

Normaalgesproken wordt hij gebruikt om te kijken hoe licht door een object heen loopt. Het object wordt uit een STL bestand geladen en omgezet in een mesh van driehoekjes. Vervolgens wordt er vanuit een bron een ray naar het object geschoten en resulteert dit in een transmissie en een reflectie onder een bepaalde hoek afhankelijk van de materiaaleigenschappen die toegekend zijn aan het driehoekje wat als eerste geraakt wordt. Die transmissie en reflectie vormen weer nieuwe rays die allemaal vanuit het midden van het geraakte driehoekje gepropageerd worden tot ze het object uitvliegen of een bepaalde hoeveelheid interacties hebben bereikt.

Het lijkt erop dat een groot deel van de processortijd zit in het bepalen of een ray een driehoekje raakt of niet. In eerste instantie werden alle driehoekjes getest op een intersect met de ray, maar ergens heeft iemand bedacht om alle driehoekjes in cellen te verdelen en eerst te testen of een ray een bepaalde cel raakt (om vervolgens alleen de driehoekjes in die cel te testen). Daarna heeft weer iemand anders bedacht om cellen van cellen te maken om hier nog meer uit te slepen.

Dit opdelen van de mesh in een datastructuur die visible-surface determination makkelijker maakt kan misschien nog wel verder verbeterd worden. Ik heb geen achtergrond in 3D rendering of gaming engines, maar de techniek die nu gebruikt wordt heeft wat weg van octrees. Dit zette me aan het denken, ik had iets gelezen over hoe Doom binary space partitioning gebruikt om levels efficient te kunnen renderen en hoe je met zo'n BSP tree een statisch model onafhankelijk van gekozen cameraperspectief back to front kan renderen. Wij gebruiken een statisch model, ray tracen is soort van steeds vanuit een ander perspectief ergens naar kijken en visible-surface determination is soort van het dichtsbijzijnde vlakje (recht voor de camera) vinden. Zou het niet mogelijk zijn om van ons model een BSP tree te maken (dat eenmalig wat meer rekenkracht kost) om vervolgens tijdens het ray tracen het eerste vlakje dat potentieel geraakt wordt te vinden door deze BSP tree te doorlopen?

Alleen houdt mijn voorstellingsvermogen hier wel een beetje op. Vind het sowieso al redelijk magisch hoe je na het maken van een BSP tree kennelijk vanuit een willekeurig perspectief back to front kan renderen, dus vind het lastig om te beredeneren of je daarmee ook het eerste driehoekje wat mijn ray zou moeten raken op die manier kan vinden, iets zegt me dat het dichtstbijzijnde driehoekje (dat dus als laatste gerendert wordt in back to front) niet per se recht voor de camera hoeft te zitten (en in dat geval dus niet geraakt wordt door een ray die je precies door het midden schiet). Bovendien weet ik daarmee ook nog niet of het potentieel sneller gaat zijn.

Zijn er hier toevallig mensen die meteen al iets kunnen roepen in de trant van: "dat gaat nooit werken omdat" of "dat wordt al gedaan en hier kun je vinden hoe"? Of het anderzijds leuk / interessant vinden om hierover te filosoferen?

Oh PS: in de toekomst willen we misschien GPUs gaan gebruiken hiervoor (we hebben een manier om de bijdragen van alle individele rays naderhand op te tellen, dus parallelizatie zou ook voor een flinke snelheidswinst kunnen zorgen). Hebben moderne videokaarten tegenwoordig ingebouwde instructies om bijvoorbeeld makkelijk te ray tracen / visibility determination te doen / intersections met driehoekjes te bepalen e.d.?

[DaFeliX]

Ja, interessant

Maar ik heb zelf geen hands-on ervaring. Wel e.e.a. gelezen, dus ik kan je iig aanraden om te kijken naar GPU ipv CPU omdat grafische kaarten juist gemaakt zijn voor dingen zoals jij wil.

Ik heb Game Engine Black Book: Doom gelezen; hierin staat wel een hoofdstuk hoe Doom het destijds deed op een CPU van een 386. De beschrijving is echter best wel 'hoog over', maar wellicht is het icm met de broncode van Doom zelf een aardige uitgangspositie; aannemende dat je het niet erg vind zelf wat dingen te moeten uitpluizen.

[Shapeshifter]

Schaamteloze kick, wie weet toch niet iemand die een idee heeft?

[Knutselsmurf]

Hoewel ik geen uitgebreide kennis heb van raytracers, heb ik wel een beetje kennis van de achterliggende principes. Met die achtergrond kan ik een aantal opmerkingen plaatsen:

- Allereerst geef je aan dat bij een hit tussen de ray en het driehoekje, vanaf het midden van het driehoekje nieuwe rays afgeschoten worden.Dat lijkt mij niet correct. Beter is uiteraard om deze nieuwe rays vanaf het contactpunt te laten vertrekken.
- Nadeel van triangulation (het opdelen in driehoekjes) is dat je zichtbare sprongen kunt krijgen op de naden.
- Het berekenen van het contactpunt tussen een ray en een driehoekje is een simpele matrix-berekening en daar is een GPU zo ongeveer voor ontworpen.
- De originele Doom is in feite nog steeds 2D. Er wordt per kolom pixels slechts 1 ray weggestuurd om te bepalen welke muur er geraakt wordt op welke afstand. Aan de hand daarvan wordt de hele kolom getekend. Deze ene ray wordt in een 2D-omgeving weggestuurd. Hierdoor kan Doom met een BSP uit de voeten om snel de juiste muren te vinden die geraakt worden. Een Octree is, voor zover ik weet, de 3D-variant van een BSP. Op dat punt valt er dus niet veel te verbeteren.

Is er al eens gemeten waar de meeste tijd besteedt wordt? Wat gebeurt er met de rekentijd als het aantal driehoeken 10 /100 / 1000 maal hoger wordt? Als de rekentijd 10 / 100 / 1000 langer wordt, dan is duidelijk dat het zoeken in de octree-variant niet (goed) werkt, maar dat er effectief nog steeds lineair gezocht wordt.

Daarnaast valt natuurlijk te kijken of het mogelijk is om de hit-test tussen een ray en een driehoekje te optimaliseren. Omdat deze functie met afstand het meest wordt aangeroepen, heeft het zin om die functie tot de laatste druppel uit te knijpen qua tijd.

Qua hit-test zou het ongeveer als volgt moeten werken:

Stel we hebben een driehoek ABC in de 3D-ruimte. Deze driehoek, als onderdeel van een oneindig vlak, kun je dan schrijven als au+bv. De vectoren a en b en de scalars u en v worden zodanig gekozen, dat in punt A: u=0 en v=0, in punt B: u=1 en v=0 en in punt C: u=0 en v=1.

Deze transformatie kan vooraf eenmalig gebeuren voor je hele model. Als je vervolgens het snijpunt berekent met het oneindige vlak uv, dat door de punten A, B en C gaat (Dit kan met 1 matrix-operatie berekend worden), dan komen daar de coördinaten van het snijpunt uit, u₁ en v₁.

Het snijpunt ligt binnen de driehoek als 0<=u₁<=1, 0<=v₁<=1 en 0<=u₁+v₁<=1.

Tot zover reikt mijn kennis op dit vlak op dit moment. Het is bijna 20 jaar geleden dat ik hier voor het laatst mee bezig ben geweest, dus het is allemaal wat weggezakt. Ik hoop dat je er desondanks toch iets aan hebt.

[Kobus Post]

Niet mijn ding, maar heb je hier niks aan? http://in1weekend.blogspo...acing-in-one-weekend.html

en nVidia heeft er ook voorbeeld code van voor op de GPU https://developer.nvidia....lerated-ray-tracing-cuda/

Waar word het voor gebruikt? Als het voor plaatjes ofzo is, dan zou je het ook in een game engine kunnen bouwen. Unreal Engine heeft Real time Ray-tracing ingebouwd.

[Comp-Freak]

Ik heb verder geen praktische ervaring met ray tracing, maar afhankelijk van de grootte van je dataset is data locality ook nog iets om in je algoritme rekening mee te houden. Zodra je buiten je cache loopt, zal je geheugenbandbreedte en latency je performance gigantisch beperken. Je algoritme zal daar in dat geval dus zoveel mogelijk rekening mee moeten houden.

[Shapeshifter]

Knutselsmurf schreef op donderdag 17 september 2020 @ 18:33:
Hoewel ik geen uitgebreide kennis heb van raytracers, heb ik wel een beetje kennis van de achterliggende principes. Met die achtergrond kan ik een aantal opmerkingen plaatsen:

- Allereerst geef je aan dat bij een hit tussen de ray en het driehoekje, vanaf het midden van het driehoekje nieuwe rays afgeschoten worden.Dat lijkt mij niet correct. Beter is uiteraard om deze nieuwe rays vanaf het contactpunt te laten vertrekken.

Correct, dat is inderdaad niet helemaal correct, maar wel makkelijker om te implementeren en de fout die we er mee introduceren zorgt voor de toepassing niet voor significante verschillen in resultaat.

- Nadeel van triangulation (het opdelen in driehoekjes) is dat je zichtbare sprongen kunt krijgen op de naden.

Hoe bedoel je dat? als ze onder een gekke hoek staan ofzo? Dat zou je voor een deel op kunnen vangen met een fijnere mesh. We hebben voor driehoekjes gekozen omdat hiervoor veel standaardmethoden zijn om bepaalde operaties te doen. Zijn er alternatieven die veel toegepast worden?

- Het berekenen van het contactpunt tussen een ray en een driehoekje is een simpele matrix-berekening en daar is een GPU zo ongeveer voor ontworpen.

Juist, ik vroeg me dus ook af of daar dan speciale instructies voor zijn die op een laag niveau in de GPU gebruikt kunnen worden, of dat je nog steeds zelf een test moet schrijven, maar dat die gewoon heel efficient gemapped kan worden op de GPU hardware.

- De originele Doom is in feite nog steeds 2D. Er wordt per kolom pixels slechts 1 ray weggestuurd om te bepalen welke muur er geraakt wordt op welke afstand. Aan de hand daarvan wordt de hele kolom getekend. Deze ene ray wordt in een 2D-omgeving weggestuurd. Hierdoor kan Doom met een BSP uit de voeten om snel de juiste muren te vinden die geraakt worden. Een Octree is, voor zover ik weet, de 3D-variant van een BSP. Op dat punt valt er dus niet veel te verbeteren.

Niet helemaal toch? Een octree deelt de ruimte op in blokken waar een BSP de ruimte opdeelt over bepaalde vlakken, maar beide kunnen ze driedimensionaal. Dat ze in Doom niet per se zo toegepast worden zou kunnen. Het is me ook nog niet helemaal duidelijk of het in Doom nou gebruikt wordt om te kijken welke muur geraakt wordt, of om het level te kunnen tekenen vanuit een bepaald cameraperspectief.

Is er al eens gemeten waar de meeste tijd besteedt wordt? Wat gebeurt er met de rekentijd als het aantal driehoeken 10 /100 / 1000 maal hoger wordt? Als de rekentijd 10 / 100 / 1000 langer wordt, dan is duidelijk dat het zoeken in de octree-variant niet (goed) werkt, maar dat er effectief nog steeds lineair gezocht wordt.

Ja, er is wel naar gekeken, maar ik zou even terug moeten zoeken hoe systematisch dat was. We werken op dit moment volgens mij ook niet met een octree, maar meer een soort benadering daarvan.

Daarnaast valt natuurlijk te kijken of het mogelijk is om de hit-test tussen een ray en een driehoekje te optimaliseren. Omdat deze functie met afstand het meest wordt aangeroepen, heeft het zin om die functie tot de laatste druppel uit te knijpen qua tijd.

Qua hit-test zou het ongeveer als volgt moeten werken:

Stel we hebben een driehoek ABC in de 3D-ruimte. Deze driehoek, als onderdeel van een oneindig vlak, kun je dan schrijven als au+bv. De vectoren a en b en de scalars u en v worden zodanig gekozen, dat in punt A: u=0 en v=0, in punt B: u=1 en v=0 en in punt C: u=0 en v=1.

Deze transformatie kan vooraf eenmalig gebeuren voor je hele model. Als je vervolgens het snijpunt berekent met het oneindige vlak uv, dat door de punten A, B en C gaat (Dit kan met 1 matrix-operatie berekend worden), dan komen daar de coördinaten van het snijpunt uit, u₁ en v₁.

Het snijpunt ligt binnen de driehoek als 0<=u₁<=1, 0<=v₁<=1 en 0<=u₁+v₁<=1.

Tot zover reikt mijn kennis op dit vlak op dit moment. Het is bijna 20 jaar geleden dat ik hier voor het laatst mee bezig ben geweest, dus het is allemaal wat weggezakt. Ik hoop dat je er desondanks toch iets aan hebt.

Ben er nog wat dieper ingedoken en volgens mij gebruiken we dit: Wikipedia: Möller–Trumbore intersection algorithm maar een hoop van die methoden komen volgens mij op hetzelfde neer.

Kobus Post schreef op donderdag 17 september 2020 @ 21:56:
Niet mijn ding, maar heb je hier niks aan? http://in1weekend.blogspo...acing-in-one-weekend.html

en nVidia heeft er ook voorbeeld code van voor op de GPU https://developer.nvidia....lerated-ray-tracing-cuda/

Waar word het voor gebruikt? Als het voor plaatjes ofzo is, dan zou je het ook in een game engine kunnen bouwen. Unreal Engine heeft Real time Ray-tracing ingebouwd.

Cool, eens zien of daar nog iets nuttigs tussen staat. Weekenden hebben is een beetje over als je eenmaal kinderen hebt maar ik zie dat er een hoofdstuk is over BVH, interessant.

Nee het is niet om mooie plaatjes te maken, maar om de invloed van een object op een omgeving door te rekenen. Het idee is dat er verschillende objecten zijn en met de tool kan worden bepaald welke van de objecten de meest gunstige invloed op de omgeving heeft, maar alles is statisch.

Comp-Freak schreef op vrijdag 18 september 2020 @ 09:55:
Ik heb verder geen praktische ervaring met ray tracing, maar afhankelijk van de grootte van je dataset is data locality ook nog iets om in je algoritme rekening mee te houden. Zodra je buiten je cache loopt, zal je geheugenbandbreedte en latency je performance gigantisch beperken. Je algoritme zal daar in dat geval dus zoveel mogelijk rekening mee moeten houden.

Exact, maar tot dusverre lukt het goed om de grootte van het object (of de mesh daarvan) zo te bepalen dat hij in het geheugen past.