Schildersalgoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In computergraphics is het schildersalgoritme een van de simpelste manieren om te bepalen welke delen van een object zichtbaar zijn, als meerdere objecten elkaar overlappen.

Bij dit algoritme wordt elk object in principe volledig getekend, maar de objecten moeten wel van achter naar voor getekend worden. Hierdoor worden de verderweg liggende objecten later overtekend door de dichterbij liggende objecten die het object overlappen.

De bergen liggen het verste weg, dus deze worden als eerste getekend. Daarna de grasvelden en als laatste de bomen. Waar objecten elkaar overlappen is het object dat als laatste getekend is zichtbaar.

Bij eenvoudig gelaagde beelden, zoals het scherm van Microsoft Windows, is het niet moeilijk om objecten te sorteren. Het is meestal niet meer dan een gesorteerde lijst, waar af en toe een object aan toegevoegd of uit weggehaald wordt.

Een situatie die niet van achter naar voor gesorteerd kan worden.

Bij geprojecteerde 3D-beelden kan het complexer worden. Ten eerste verandert de volgorde van de 3D objecten in bijna elk frame, waardoor de lijst ook voor elk frame opnieuw moet worden gesorteerd. Verder zijn er ook situaties die helemaal niet te sorteren vallen, tenminste zolang je per polygoon blijft sorteren. Om perfect te sorteren zul je eigenlijk polygonen moeten gaan splitsen, maar dat is vaak veel te intensief om realtime te gaan doen.

Dit valt op te lossen met een bsp-tree. Een bsp-tree splitst polygonen die problematisch zouden kunnen zijn tijdens het preprocessen van een 3D scène. Tijdens het renderen van de scène kan dan door middel van de bsp-tree alles juist gesorteerd worden. Een nadeel van een bsp-tree is dat het alleen voor statische (niet bewegende) objecten gebruikt kan worden.

Omdat het schildersalgoritme voor 3D scènes zoveel problemen met zich meebrengt, wordt er vaak vanaf gezien en gebruikt men een dieptebuffer, die het sorteren overbodig maakt.