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 x_i: x_i = x_i−1+1/m, y_i = y_i−1 + m, hvor Δx = x_end − x_start og Δy = y_end − y_start 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:

$m={\frac {y_{end}-y_{start}}{x_{end}-x_{start}}}$

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

$y_{k+1}=y_{k}+m$

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

$x_{k+1}=x_{k}+{\frac {1}{m}}$

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