Bresenham-algoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Illustratie van de Bresenham lijnalgoritme

Het Bresenham-algoritme is een algoritme voor het tekenen van rechte lijnen en cirkels op matrixdisplays.

Dit algoritme werd in 1962 door Jack Bresenham (destijds programmeur bij IBM), ontwikkeld. Al in 1963 werd het gepresenteerd in een voordracht op de ACM National Conference in Denver. Het bijzondere aan dit algoritme is, dat afrondingsfouten die ontstaan door het afronden van continue grootheden geminimaliseerd worden, terwijl het eenvoudig te implementeren is. De moeilijkste berekening die gebruikt wordt is het optellen van gehele getallen, dus vermenigvuldigen, delen en drijvende-komma-notatie zijn niet nodig.

Met een kleine uitbreiding is het oorspronkelijke algoritme, dat was ontwikkeld voor het tekenen van rechte lijnen, ook voor cirkels te gebruiken. Zelfs de kwadratische termen die in de vergelijking van een cirkel voorkomen kunnen recursief zonder vermenigvuldigingen afgeleid worden uit het voorgaande pixel volgens (n+1)^2 = n^2 + 2 \cdot n + 1, waarin de term 2 \cdot n niet voor een vermenigvuldiging telt, omdat die op binair niveau als een schuifoperatie geïmplementeerd kan worden.

Op basis van de bovenstaande eigenschappen is de betekenis van het Bresenham-algoritme tot op heden behouden gebleven. Het wordt onder meer toegepast in plotters en grafische kaarten. Het algoritme is bovendien zo eenvoudig dat de toepassing niet beperkt is gebleven tot firmware, want ook implementatie in hardware is heel goed mogelijk.

Voor de volledigheid dient vermeld te worden, dat de naam „Bresenham“ tegenwoordig gebruikt wordt voor een groot aantal grafische algoritmen, die eigenlijk later door anderen ontwikkeld zijn, maar gebaseerd zijn op het werk van Bresenham en berusten op hetzelfde principe.

Toelichting[bewerken]

Het Bresenham-algoritme digitaliseert een curve. De digitale punten zijn de roosterpunten, en de selectie van de beste roosterpunten, gebeurt met de "midpoint" techniek. Men start met het beste roosterpunt (het startpunt), en omdat men de richting kent, kent men de mogelijke kandidaat-roosterpunten. Het midpoint is het middelpunt van twee kandidaat-punten. Voor een lijn, kiest men het kandidaat-punt dat het dichtst (in Euclidische zin) bij de lijn ligt. Voor een ellips, parabool of hyperbool, kiest men het kandidaat-punt dat het dichtst (in Euclidische zin) bij de poollijn van het midpoint ligt. Het geselecteerd punt is in feite het resultaat van een relatieve meting en men kan bewijzen, (het bewijs is uiterst complex) dat mits de meting niet Out-of-Control (OoC) is, dat het geselecteerd punt ook het dichtst, in Euclidische zin, bij de curve ligt, rekening gehouden met de eventuele meetfout, die kleiner is dan de helft van de afstand tussen de kandidaat-punten. Niet kwadratische kurven worden "deelsgewijze" benaderd door kegelsneden, en de willekeurige curve wordt dus omgezet in kwadratische Bézier splines (ook conic splines of squines genoemd). Tot nu toe kon het algemeen algoritme, niet omgezet worden in harware: als de meting OoC wordt, dan slaat de digitalisatie heel vaak op hol, en in het Engels zegt men dat het algoritme "berserk" wordt. Het midpoint-algoritme of het algemeen Bresenham-algoritme staat dan ook bekend als een niet stabiel algoritme. Recent heeft Valere Huypens een uiterst snelle oplossing gevonden, namelijk het "Berserkless ultra fast 4-connected Midpoint Algorithm" en het "Berserkless ultra fast 8-connected Midpoint Algorithm".