Schildersalgoritme

Van Wikipedia

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 princiepe volledig getekend, maar de objecten moeten wel van achter naar voor getekend worden. Hierdoor worden de verderweg liggende objecten later overtekent door 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 simpele gelaagde beelden, zoals het scherm van Microsoft Windows, is het vaak erg simpel om objecten te sorteren. Het is dan vaak 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 echter verschrikkelijk moeilijk worden. Ten eerste verandert de volgorde van de 3D objecten zogoed als elk frame, waardoor je de lijst ook elk frame opnieuw moet sorteren. 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 split polygonen die problematisch zouden kunnen zijn tijdens het preprocessen van een 3D scène. Tijdens het renderen van de scène kun je dan doormiddel van die bsp-tree alles altijd perfect sorteren. 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.