Algoritmer

På de følgende sidene vil du finne noen resonnementer og algoritmer for vanlige problemer i planet. Temaene er ikke knyttet opp til OpenGL, og er tatt med for å gi en generell innføring i de aller mest grunnleggende resonnementene, hovedsaklig i planet.

På siden for linjer finner du et par måter å framstille linjer på og du finner en algoritme for å finne skjæring mellom linjer.

Under sirkler finner du noen enkle algoritmer for å tegne sirkler.

Under polygoner finner du en algoritme for å ordne en punktsverm i et polygon og du finner en algoritme for å lage et polygon som omslutter en punktsverm. Dessuten en algoritme for arealberegning.

Utgangspunktet er hele tiden rene geometriske betraktninger. Dersom vi skal gå inn på detaljene i hvordan enkeltpunkter skal velges ut for å framstille linjestykker og sirkler best mulig på skjermen reiser dette to sett med problemstillinger som ikke er dekket her:

• DDA-algoritmer. (Digital Differential Algorithms). Dette er algoritmer som kombinerer to krav til uttegningen: De skal være effktive og de skal velge ut skjermpunkter slik at trappetrinnseffekter blir fordelt best mulig. Slike algoritmer er beskrevet i grafisk litteratur.
• Aliasing. Selv om vi har gode DDA-algoritmer så er det ikke mulig å unngå trappetrinnseffekten i linjer og buer. Det er en rekke teknikker som går ut på å redusere den visuelle effekten av dette, antialiasing. Dette er også beskrevet i grafisk litteratur.

DDA-algoritmene ligger langt inne i systemet og vi må gjøre svært ineffektive kunstgrep for å endre disse. Antialiasing er teknikker som er tilgjengelig i pakker som OpenGL. De er tidkrevende, de realiseres typisk med flere renderinger av scenen, og de skrus bare på når vi har behov.