[alg] Basic 3D engine vraagje

[Bozozo]

Ik wil een eigen, zeer basic 3D engine in flash maken. Tot nu toe is het aardig gelukt, zie deze test.

De engine werkt heel eenvoudig: iedere vertex wordt via standaard transformatiematrices geprojecteerd op het platte vlak. Nu loop ik tegen het volgende probleem aan: als je voorbij het object loopt (er "doorheen") dan zie je op een gegeven moment de negatieve projectie. Het object bevindt zich dan recht achter je. Natuurlijk moet het object dan onzichtbaar zijn.

Ik zou gewoon alle vertices met afstand_tot_camera <= 0 kunnen weglaten, maar dan zou je objecten die gedeeltelijk achter de camera liggen niet meer zien.

Wat is hiervoor de beste oplossing? Ik neem aan dat iedere 3D engine dit 'probleem' moet oplossen, dus er zal wel een trucje bekend zijn. Heeft iemand hier ervaring mee?

[Marcks]

Bozozo schreef op zaterdag 19 april 2008 @ 20:09:
Ik wil een eigen, zeer basic 3D engine in flash maken. Tot nu toe is het aardig gelukt, zie deze test.

Ik zou gewoon alle vertices met afstand_tot_camera <= 0 kunnen weglaten, maar dan zou je objecten die gedeeltelijk achter de camera liggen niet meer zien.

Je zou in ieder geval alle vertices kunnen weglaten die noch in de field of view liggen, noch aan andere vertices grenzen die er wel in liggen. Daarvoor moeten wel alle faces worden opgebroken in driehoeken. Alle renderers doen dat overigens.

Je kunt dan wellicht problemen krijgen met faces die gedeeltelijk in de FOV liggen. Een mogelijke oplossing is om de problematische vertices te vervangen door pseudo-vertices op het snijpunt van de edge en de FOV.

[Bozozo]

Het opbreken in driehoeken wil ik proberen te vermijden. Het tekenen in Flash werkt met Shapes, dwz objecten bestaande uit een contour en een Fill. Als ik mijn faces (in het voorbeeld vierkanten, maar elke vorm is in principe mogelijk) ga opbreken dan neemt het aantal Shapes snel toe en dat is erg slecht voor de prestaties van Flash.

Het introduceren van nepvertices is een optie (misschien onvermijdelijk?), maar voegt ook nogal wat rekenwerk toe. Een object kan dan bijvoorbeeld worden opgesplitst in "gewone" faces en "aangepaste" faces, waarna ik weer aan de vlakken-tekenen-adhv-vertices functie moet uitleggen dat er andere vertices zijn bijgekomen die alleen door bepaalde vlakken worden gebruikt.

[.oisyn]

Je moet de snijpunten met het nearplane berekenen en het stuk van de polygoon dat erachter ligt eraf hakken, er zit niets anders op.

[Eddy Dean]

Doet backface culling dat niet ook?

Bereken dotproduct van twee vectoren op polygon, als die vector naar camera wijst moet je hem tekenen, anders niet. Dit werkt helaas niet met de transparantie die je gebruikt...

[PrisonerOfPain]

Eddy Dean schreef op zondag 20 april 2008 @ 09:42:
Doet backface culling dat niet ook?

Nee, backface culling verwijderd alleen polygonen met een normal die van de camera af wijst. Clipping tegen z-near heeft een ander doelt; het houd de perspective berekening correct door deling door een heel klein of negatief getal te voorkomen. Let wel dat je tijdens dit process (en nog wel meer) je polygon wel op moet delen.

Bereken dotproduct van twee vectoren op polygon, als die vector naar camera wijst moet je hem tekenen, anders niet. Dit werkt helaas niet met de transparantie die je gebruikt...

Je gebruikt het crossproduct tussen twee edges om de normal te krijgen als je die niet apart opslaat, vervolgens dot je de normal met de direction vector van je camera (meestal view - position) om te kijken of de vector naar je toe wijst.

[Bozozo]

Ik denk dat ik te veel performance moet inleveren voor het implementeren van polygoonafsnijding. Het 'door de camera heen gaan' van een object is in een eenvoudig spelletje m.i. toch al geen waarschijnlijke situatie.

Backface culling is trouwens een leuk idee. Ik wilde de normalen toch al gaan vastleggen (ivm basic shading) en met een eenvoudige check kun je dan meteen een hoop polygonen afstrepen.

Bedankt voor de reacties!

[PrisonerOfPain]

Bozozo schreef op zondag 20 april 2008 @ 11:09:
Ik denk dat ik te veel performance moet inleveren voor het implementeren van polygoonafsnijding. Het 'door de camera heen gaan' van een object is in een eenvoudig spelletje m.i. toch al geen waarschijnlijke situatie.

Je moet het ook alleen doen als de performance voor het snijden beter is als de performance voor het renderen; enkel bij z-near kan het nogal vreemde artifacts opleveren. Polygonen die 'willekeurig' op het scherm lijken te verschijnen als je te dicht bij objecten in de buurt komen zijn het kenmerk. Daarbij zijn er nog mogelijkheden om het proces te versnellen; algemene culling technieken zoals frustum culling helpen een hoop en als je tegen de viewport zelf gaat clippen zou je kunnen overwegen om een guardband te implementeren. Dat houd in dat je een extra ruimte om je viewport creëert waar je gewoon op rendered maar dat niet tot je uiteindelijke resultaat behoord. In dat geval hoef je in minder gevallen te clippen.

Backface culling is trouwens een leuk idee. Ik wilde de normalen toch al gaan vastleggen (ivm basic shading) en met een eenvoudige check kun je dan meteen een hoop polygonen afstrepen.

In het optimale geval kun je de helft van de polygonen in je viewport afschaffen, maar meestal zullen het er iets minder zijn.

[.oisyn]

Bozozo schreef op zondag 20 april 2008 @ 11:09:
Ik denk dat ik te veel performance moet inleveren voor het implementeren van polygoonafsnijding. Het 'door de camera heen gaan' van een object is in een eenvoudig spelletje m.i. toch al geen waarschijnlijke situatie.

Vrijwel alle software renderers implementeren near plane clipping. Het is ook helemaal niet zo'n dure operatie. Je clipt op een constante z (zeg z=1) in camera space. Het enige dat je dus hoeft te doen is het vinden van de x en y coordinaten als een polygoon een aantal verts heeft met z>1 en een aantal verts met z<1. Je moet gewoon over de edges heen lopen, waarbij je een nieuwe lijst van vertices opbouwt. Als een edge het vlak kruist, dan bereken je het snijpunt en voeg je die aan de lijst toe. En als een edge een eindvertex (met de looprichting mee) heeft met z>1, dan voeg je die ook toe aan de lijst. Je nieuwe lijst met vertices is dan je geclipte polygoon.

Je kunt dit evt. optimaliseren door eerst op object-niveau te kijken of er überhaupt geclipt moet worden. Dus als je object een bounding volume heeft (zoals een box of sphere), dan kijk je of dat volume het vlak snijdt. Zo ja, dan moeten de polygonen in dat object geclipt worden.

[PrisonerOfPain]

.oisyn schreef op zondag 20 april 2008 @ 15:39:
Als een edge het vlak kruist, dan bereken je het snijpunt en voeg je die aan de lijst toe.

De rest van de eigenschappen van je vertex moet je op dat moment niet vergeten te interpoleren want het kan tot een behoorlijk lelijk, en fout, resultaat leiden. Verder dien je uit te kijken met het creëren van hele lange en dunne triangles; maar dat is eigenlijk niet relevant in een software rasterizer.

[.oisyn]

PrisonerOfPain schreef op zondag 20 april 2008 @ 15:59:
Verder dien je uit te kijken met het creëren van hele lange en dunne triangles

Waarom?

[PrisonerOfPain]

.oisyn schreef op zondag 20 april 2008 @ 16:11:
[...]

Waarom?

Ik heb altijd geleerd dat sliver polygons traag zijn om te renderen op een GPU; vandaar dat ik ook zei dat 't er verder niet toe deed in een software rasterizer. En ear clipping staat er bekend om juist veel slivers te creëren; echter is het meestal maar de vraag of het het waard is om een ingewikkelder clipping algorithme te implementeren enkel voor deze edge cases.

[.oisyn]

Ik heb altijd geleerd dat sliver polygons traag zijn om te renderen op een GPU

Dat klopt idd, omdat pixels in groepjes tegelijk worden getekend. Bij lange dunne triangles heb je dus het probleem dat er minder gebruik wordt gemaakt van die parallellisatie (omdat heel veel pixels in zo'n blok niet binnen het polygoon vallen), en de effectieve fillrate dus omlaag gaat. Maar goed, dat geldt voor relatief moderne GPUs, en die doen al jaren hun eigen clipping .

En ear clipping staat er bekend om juist veel slivers te creëren

Het is geen resultaat van je clipping; dat levert gewoon een polygoon op. Het hangt af van de manier waarop je je resulterende polygoon opnieuw gaat trianguliseren. Maar goed, als je geclipte polygoon gewoon lang en dun is doe je er verder weinig aan.

[PrisonerOfPain]

.oisyn schreef op zondag 20 april 2008 @ 18:17:
Maar goed, dat geldt voor relatief moderne GPUs, en die doen al jaren hun eigen clipping .

Kijk, dat hebben ze me er nooit bij verteld , kan ook zijn omdat ze ons hier op proberen te leiden voor een modernere generatie maar bedankt voor de info .

Het is geen resultaat van je clipping; dat levert gewoon een polygoon op. Het hangt af van de manier waarop je je resulterende polygoon opnieuw gaat trianguliseren. Maar goed, als je geclipte polygoon gewoon lang en dun is doe je er verder weinig aan.

Met ingewikkeldere triangulization algorithmes zoals Delaunay of Voronoi tessellation is het in principe mogelijk om betere resultaaten te krijgen, maar dat werkt inderdaad niet als het resultaat van je clipping al bagger is. De reden dat ik triangulazation en clipping door elkaar haalde was omdat het resultaat van het clippen in m'n software rasterizer al meteen getriangulate was.

[.oisyn]

Alleen Delaunay trouwens, een Voronoi diagram is de duaal van de Delaunay triangulatie van dezelfde set punten en bestaat niet louter uit diehoeken (waarbij de punten sowieso geen vertices zijn binnen het diagram)