Digital differential analyzer

Digital differential analyzer (DDA) er innen datagrafikk et stykke maskinvare eller programvare for å lineær-interpolere variabler over et interval mellom et start- og sluttpunkt. DDA brukes for å rasterisere linjer, triangler og polygoner. I sin enkleste form vil DDA-algoritmen virke ved å interpolere verdier i intervallet ved å regne ut for følgende ligninger for hver xi: xi =  xi−1+1/m, yi =  yi−1 + m, hvor Δx = xend − xstart og  Δy = yend − ystart og m = Δy/Δx.

 Ytelse 
DDA-algoritmen kan implementeres ved bruk av enten flyttalls- eller heltallsaritmetikk. Flyttallsmetoden krever en addisjon- og en avrundingsoperasjon per interpolerte verdi (for eksempel koordinatene x og y, dybde, fargekomponent og så videre) og resultat. Denne metoden er bare effektiv når en FPU med raske addisjons- og avrundingsoperasjoner er tilgjengelig.

Ved bruk av heltallsaritmetikk og et fast antall siffer etter komma, kreves to addisjoner per syklus. Hvis tallet bak komma blir mer enn én, kreves en ekstra addisjon og subtraksjon. Sannsynligheten for at dette skjer er proporsjonal med raten til m i de interpolerte start- og sluttverdiene.

DDA passer bra for å bli implementert i maskinvaren, og kan benytte seg av parallellutførelse (pipelining) for å maksimere ytelsen.

Helningen til linja m kan beskrives på følgende måte:


 Algoritmen 
DDA starter med å regne ut dy og dx, og velger den minste av disse til fortsettelsen. Linja blir så regnet ut for hver heltallsverdi mellom start- og sluttpunktet langs enten x- eller y-aksen. Den utregnede verdien i hvert punkt blir så rundet til nærmeste heltall for den andre koordinaten.

Gitt en linje med positiv helning på mindre enn en, vil man regne ut y-verdier for hver x (dx=1) slik som

Hvor k er en heltallsverdi som starter fra 0, for det første punktet, og øker med én til sluttpunktet er nådd. y-verdien rundes så av til nærmeste heltall for å få en nøyaktig pixelverdi på skjermen.

For linjer med helning høyere enn én, bytter man om på x og y, det vil si at man regner ut x-verdier og bruker dy=1

Liknende kalkulasjoner gjøres for å regne ut pikselverdier langs en linje med negativ helning.

 Se også 
 Bresenhams linjealgoritme som er en algoritme for å tegne linjer.
 Xiaolin Wus linjealgoritme som er en algoritme for anti-aliasing

 Kilder 
 Alan Watt: 3D Computer Graphics, 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9

Kategori:Datagrafikk
Kategori:Algoritmer