Bresenham-algoritme
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 de voorgaande pixel volgens , waarin de term 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, en ook implementatie in hardware heel goed mogelijk is.
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
Zie: Relative Squared Distances to a Conic -- Berserkless 8-Connected Midpoint Algorithm, International Journal of Computer Graphics & Animation (ICJGA) Vol. 5, No. 1, January 2015, DOI: 10.5121/ijcga.2015.5102. 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 curven 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 algemene algoritme niet omgezet worden in hardware: als de meting OoC wordt, slaat de digitalisatie heel vaak op hol, en in het Engels zegt men dat het algoritme "berserk" wordt. Het midpoint-algoritme en het algemene Bresenham-algoritme staan dan ook bekend als niet-stabiele algoritmen. 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".
Referenties bewerken
- Relative Squared Distances to a Conic -- Berserkless 8-Connected Midpoint Algorithm, International Journal of Computer Graphics & Animation (ICJGA) Vol. 5, No. 1, January 2015, DOI: 10.5121/ijcga.2015.5102.