Vraag 1: Rastering. en wordt de lijn te dun getekend

Vraag 1: Rastering a. Bespreek de verschillende algoritmen voor de rastering van rechte lijnen, zonder in detail in te gaan op multi-step varianten. Vermeld telkens hun voor- en nadelen. (§1.2 & §1.2.1) b. Hoe kunnen de methodes aangepast worden om dikke lijnen voor te stellen ? (§1.5)

A) 1. Midpoint subdivision • Meest eenvoudige algoritme • Veronderstelt dat de pixelcoördinaten van de uiteinden gekend zijn (x1,y1) en (x2,y2) • Het algoritme maakt gebruik van een recursieve procedure die het midden van het segment berekent, die pixel kleurt, en dan de procedure voor de 2 helften van het segement oproept. • Nadelen: i. Bij hellingshoeken van +/- 45°: onregelmatige en dunnere lijnen ii. Werkt met reële getallen 2. Asymmetrische DDA • DDA = Digital Differential Analyzer deze soort algorimes probeert het gebruik van reële getallen te beperken. • De x-waarde van een pixel wordt iteratief met 1 verhoogd, de y-waarde wordt verhoogd met de rico van de rechte. • Indien de hellingshoek > 45° worden de rollen van x en y omgewisseld. • Incrementeel algoritme: in elke stap wordt een pixel berekend en getekend. • Het algoritme tekent L pixels: i. Voor lijnstukken met helling ~0° of ~90° is L een goede benadering voor de lengte ii. Voor hellingen van ~45° is

√

en wordt de lijn te dun getekend

3. Symmetrische DDA • Vermijdt het onderscheid in functie van de hellingshoek door de incrementen in beide richtingen repetitief te halveren tot wanneer deze beide kleiner zijn dan een pixel • Produceert dezelfde resultaten als midpoint subdivision • Tov asymmetrische DDA worden aanvullende pixels getekend bij hellingshoeken van ~45° zijn de lijnen iets voller, maar minder regelmatig • Sommige pixels worden 2 maal berekend snelheid van het algoritme daalt 4. Kwadrant DDA • Verhoogt de incrementen met exact 1 pixel, maar enkel in de x-richting of de y-richting, nooit in beide tegelijk.

1 Computergrafiek reeks 1

Len Buckens

•

De verhouding van het aantal incrementen in de y-richting y richting tov het aantal incrementen in de x-richting x is gelijk aan de rico

•

• • •

• •

Er wordt een variabele ∆ bijgehouden die de afwijking bijhoudt ten opzichte van de ideale lijn i. ∆ > 0 de nieuwe pixels wordt in de x-richting richting getekend en ∆ wordt verminderd met (y2-y1) ii. ∆ < 0 de lijn wordt verder getekend in de y-richting richting en ∆ wordt verhoogd met (x2-x1) Voordeel: gebruikt geen enkel reëel getal Nadeel: slechte resultaten voor vlakke vlakke of zeer steile lijnstukken Oorzaak hiervan is de foutieve initialisatie van ∆. ∆ moet geinitialiseerd geinitial worden op

Om te vermijden dat dan met reële getallen gewerkt wordt, wordt de waarde 2 ∆ bijgehouden. Voordeel: goede weergave voor bijna horizontale/vertikale lijnen Nadeel: te dikke lijnen bij hellingshoek van ~45°

5. Octant DDA • Vermijdt overlappende segmenten (is eigenlijk een verfijning van kwadrant DDA) • Is de hellingshoek <45°: er is enkel een pixel mogelijk in horizontale of diagonale richting • Is de hellingshoek >45°: er is enkel een pixel mogelijk in de vertikale of diagonale le richting

• • •

Produceert nagenoeg dezelfde resultaten als asymmetrische DDA, zonder gebruik te maken van reële getallen Nadeel: bij ~45° is de lijn iets te fijn Voordeel: i. regelmatig patroon ii. geen reële getallen

6. Double-step DDA • Bij elke iteratie worden verschillende pixels tegelijkertijd bepaald • Multi-step step DDA-varianten DDA varianten richten zich vooral op het optimaliseren van de snelheid, en niet van de output • Bij elke stap moet een keuze gemaakt worden uit 4 mogelijke patronen: patronen

•

Voordeel: i. Geen gebruik van reële getallen g

2 Computergrafiek reeks ks 1

Len Buckens

ii. Ongeveer de helft minder bewerkingen dan bij octant DDA

B) 1. Door replicatie: • Eenvoudigste en snelste manier • Bij elke iteratie van het DDA-algoritme worden een aantal pixels boven en onder (of links en rechts als de helligshoek >45°) van de geselecteerde pixel getekend. • Het aantal pixels wordt berekend uit de gewenste breedte van de lijn • Nadelen: i. Bij vrij dikke lijnen zien de gerepliceerde lijnen er niet uit als rechthoeken, maar als parallellogrammen ii. De overgang van 2 even dikke rechte lijnsegmenten is in het gemeenschappelijk punt niet altijd even goed • In de praktijk wordt replicatie enkel toegepast als de lijnen niet zeer dik zijn. 2. Gebruik van een pen: • Deze methode repliceert niet in 1 enkele richting, maar houdt de vorm van een pen bij en tekent die vorm bij elke iteratie van het DDA-algoritme, gecentreerd rond de geselecteerd pixel • Voor lijnen wordt meestal een pen met rechthoekige vorm gekozen • Nadeel: stuk trager dan replicatie omdat sommige pixels meerdere keren getekend worden. 3. Het DDA-algoritme 2x toepassen op lijn-objecten die uit elkaar verschoven zijn en de ruimte tussen deze objecten opvullen met een methode voor het opvullen van rechthoeken • Nadeel: nog meer rekenwerk.


Len Buckens

Vraag 2: Het algoritme van Bresenham a. Bespreek het doel van dit algoritme en geef de volledige uitwerking van het selectieproces. (§1.3) b. Hoe kan deze methode aangepast worden om dikke cirkels voor te stellen ? (§1.5)

A) Dit is een DDA-techniek techniek die gebruikt wordt om cirkels te rasteren. Het algoritme berekent enkel pixels voor de cirkelsector met beginpunt (0,R) en eindpunt

De andere sectoren worden door symmetrie bekomen. Bij elke iteratie i wordt de x-waarde waarde van de pixel verhoogd. verhoogd Men heeft bijgevolg geen zuivere vertikale elementen. elementen. Het aanpassen van de y-waarde y is aan een voorwaarde verbonden: ∆i > 0 Na het tekenen van een pixel Pi-1 = (xi-1,yi-1) moet men beslissen of de ordinaat van de volgende pixel yi, yi-1 -1 1 wordt, of yi-1 blijft. De discriminant ∆i is het verschil van de kwadraten van de afstanden van Si en Ti tot de cirkel.

De discriminant bij een volgende iteratie ∆i+1 kan uit ∆i berekend worden:

De beginwaarde van de discriminant is ∆1 = 3-2R Voordeel: het algoritme vereist enkel gehele getallen.

B) 1. Door replicatie: • Eenvoudigste en snelste manier • Bij elke iteratie van het DDA-algoritme DDA algoritme worden een aantal pixels boven en onder (of links en rechts als de helligshoek >45°) van de geselecteerde pixel getekend.


Len Buckens

• •

Nadeel: de cirkel is dunner in de helften van de kwadranten dan aan de overgangen van de kwadranten. In de praktijk wordt replicatie enkel toegepast als bij niet zo dikke cirkels.

2. Gebruik van een pen: • Deze methode repliceert niet in 1 enkele richting, maar houdt de vorm van een pen bij en tekent die vorm bij elke iteratie van het DDA-algoritme, gecentreerd rond de geselecteerd pixel • Voor cirkels wordt meestal een cirkelvormige pen met gekozen • Nadeel: stuk trager dan replicatie omdat sommige pixels meerdere keren getekend worden. 3. Het DDA-algoritme 2x toepassen op cirkel-objecten die uit elkaar verschoven zijn en de ruimte tussen deze objecten opvullen met een methode voor het opvullen van rechthoeken • Nadeel: nog meer rekenwerk.


Len Buckens

Vraag 3: Rastering van veelhoeken en antialiasing a. Hoe moeten algoritmen voor het rasteren van rechte lijnen gewijzigd worden indien men ze wil toepassen op het opvullen van veelhoeken ? (§1.4) b. Geef het doel van antialiasing, het algemeen principe ervan, en drie algoritmen voor de praktische uitwerking (met voorbeelden). (§1.6)

A) De veelhoek wordt afgetast met (horizontale) scanlijnen. Voor elke scanlijn gaat men op zoek naar de intersecties met de veelhoek (altijd een even aantal, rekening houden met multipliciteit). De intersecties worden gesorteerd volgens de x-waarde. Alle pixels tussen een intersectie met een even index en een intersectie met oneven index worden getekend. Elke intersectie wordt berekend met een incrementeel algoritme voor de rastering van lijnen, op basis van intersecties met de vorige scanlijn. Deze algoritmes moeten wel aangepast worden: alleen inwendige pixels mogen als intersectiepunt gekozen worden, ook al ligt de uitwendige pixel dichter bij de rand. Anders vallen sommige geselecteerde pixels buiten de veelhoek, wat een storend effect heeft op naburige veelhoeken van een ander kleur.

B) Rechten en cirkels zijn continue meetkundige krommen. Rastering technieken vormen deze continue objecten om in een eindige verzameling pixels. Pixels kunnen slechts een discreet aantal posities aannemen, bepaald door de karakteristieken van de hardware. Hierdoor krijgen lijnen en cirkels een gekarteld uitzicht of treden ongewenste interferentieverschijnselen op, hoe groote de resolutie van de pixels ook is. Dit heet aliasing. Doel: Het doel van antialiasing is dit effect proberen te reduceren. Algemeen principe: meestal doet men een beroep op het aanpassen van de kleurcomponenten of van de grijstinten van de geselecteerde pixels. Algoritmes: 1. Supersampling gaat uit van de vaststelling dat aliasing vermindert als de resolutie zou kunnen opgedreven worden. De rasteringstap wordt dan ook uitgevoerd met een raster in het geheugen van de computer dat fijner is dan wat de hardware effectief te beschikking heeft. vb: met elke pixel van het scherm komt een groep van 4 pixels overeen. Na het rastering-proces wordt elke groep geheugenpixels verwerkt door een supersamplingfase: de intensiteit van de hardware-pixel wordt berekend op basis van het aantal geselecteerd pixels in de groep, dmv van een eenvoudige uitmiddeling of door gewogen uitmiddeling.


Len Buckens

a. Voordeel: efficiënt bij het weergeven van gevulde rechthoeken b. Nadeel: el: niet altijd verbeterd effect bij dunnen lijnen 2. Postfiltering gebruikt een geheugenbuffer met dezelfde fde resolutie als de hardware. Na de rastering-fase fase wordt de intensiteit van een pixel herberekend op basis van het al dan niet geseleceerd zijn van naburige pixels.

3. Prefiltering: rastering en antialiasing worden in 1 stap uitgevoerd, in tegenstelling tot supersampling en postfiltering. Hiervoor zijn aangepaste DDA-methodes DDA nodig: a. Pittaway-Watkinson Watkinson algoritme wordt gebruiktvoor het weergeven van gevulde rechthoeken. Dit algoritme maakt het mogelijk niet alleen de selectie van een pixel, maar ook tegelijkertijd tegelijkertijd de intesiteit ervan incrementeel, pixel per pixel, te berekenen. b. Voor rechte lijnen kan gebruik gemaakt worden van een variant van multimulti step DDA: bij elke stap moet eenkeuze gemaakt worden uit verschillende patronen. De patronen verschillen nu echter ook in intensiteit ervan.


Len Buckens

Vraag 4: Transformaties a. Welke families transformaties worden in de computergrafiek gebruikt, en waarom ? b. Geef en bespreek de matrixrepresentaties van de verschillende types transformaties en hun samenstellingen. (§2.1 behalve §2.1.4)

A) 1. Affiene transformaties: rotaties, schaaloperaties en translaties. Ze spelen een belangrijke rol in de computergrafiel omdat ze de collineariteit en parallellisme bewaren: evenwijdige lijnen/vlakken worden door een affiene transformatie afgebeeld op evenwijdige lijnen/vlakken. 2. Projecties zijn een bijzondere soort transformatie: ze maken het mogelijk om een drie dimensionaal object voor te stellen op een 2-dimensionaal uitvoerapparaat. Daarom zijn ze belangrijk in de computergrafiek. B) 1. Rotaties Willekeurige rotaties worden dikwijls opgevat als een samenstelling van meer eenvoudige rotaties. De meest elementaire zijn de rotaties rond de coördinaatassen. De rotatie rond de z-as van een punt (x, y, z) wordt gegeven door:

Willekeurige trasformaties kunnen samengesteld worden tot 1 transformatie met de matrix M=Mn . Mn-1 . … . M2 . M1. Opgelet: de vermenigvuldiging van matrices is meestal niet commutatief: de volgorde waarin de individuele rotaties uitgevoerd worden speelt wel een rol. De transformatiematrix van een willekeurige rotaties Ru,β rond de u-as over een hoek β kan bekomen worden door de rotatie te ontbinden in rotaties telkens rond 1 van de coördinaatassen: een voorbereidende stap voert 2 rotaties uit: Ry,θ en Rz,-φ zodat het beelde van de u-as samenvalt met de x-as. Een 3e rotatie wordt uitgevoerd rond de x-as over een hoek β: Rx,β. In de laatste stap worden de voorbereidende rotaties ongedaan gemaakt: Ru,β = Ry,-θ . Rz,φ . Rx,β . Rz,-φ . Ry,θ Een willekeurige rotatieslatrix heeft de gedaante:


Len Buckens

De kolommen van de matrix kunnen geïnterpreteerd worden als de coördinaten van de eenheidsvectoren van het coördinatenstelsel.

2. Schaaloperaties Een schaaloperatie S0,xyz, gecentreerd rond de oorsprong en gericht volgens de coördinaatassen heeft een zeer eenvoudige matrix representatie:

Wanneer sx=sy=sz dan spreekt men van gelijkvormigheid. Een meer algemene schaaloperatie S0,uvw kan men bekomen door eerst een rotatie Ru->x, v->y, w->z uit te voeren, de schaaloperatie uit te voeren en daarna de inverse rotatie toe te passen. S0,uvw = (Ru->x, v->y, w->z)T . S0,xyz . Ru->x, v->y, w->z Indien 1 van de schaalfactoren -1 is en de rest +1, dan heeft men een spiegeling/reflectie in een coördinatenvlak. Matrices voor spiegelingen in willekeurige vlakken kunnen opnieuw bekomen worden door een rotatie en inverse rotatie toe te passen.

3. Translaties Een willekeurige translatie kunnen we als volgt schrijven:

Deze voorstelling heeft echter het nadeel dat de samenstelling met andere tranformaties complexer wordt. Daarom schrijven we een translatie als volgt:

Deze vorm (x, y, z, 1) is een homogene coördinaatvoorstelling van een willekeurig 3D punt. Om de samenstelling van translaties met affiene transformaties te vereenvoudigen, moeten ook de rekenregels voor rotaties en schaaloperaties in homogene vorm gebracht worden:


Len Buckens

Vraag 5: Projecties en clipping a. Welke soort projectie wordt in de computergrafiek gebruikt, en waarom ? b. Leid de algemene matrixvorm van deze projectie af. (§2.2) c. Wat is de bedoeling van clipping ? Bespreek clippen in twee en in drie dimensies. (§2.3 zonder deelparagrafen)

A) Perspectieve projectiles (behoren tot de lineaire projecties). Ze zijn zeer belangrijk belan in de computergrafiek omdat ze simuleren hoe onze ogen 3D-objecten 3D objecten op het netvlies visualiseren.

B) We leiden eerst de rekenregels af na het toepassen van een affiene transformatie (transformatie en rotatie),, die het coördinatenstelsel in lijn brengt brengt met de kijkrichting en het projectievlak. De coördinaten (xp, yp, 0, 1) van de perspectieve projectie van een willekeurig punt (x, y, z, 1) kunnen onmiddellijk worden afgeleid uit de gelijkvormige driehoeken:

We houden er rekening mee dat alle viertallen (x’ hetzelfde punt (xp, yp, 0, 1) voorstellen: x’

w’.xp = x

en

y’

w’.yp = y

en

w’.xp, y’

w’.yp, 0, w’) en w’ ≠ 0

w’ =

In matrixvorm:

Combineren we nu de voorbereidende affiene transformatie (die het coördinatenstelsel in lijn brengt met de kijkrichting en het projectievlak) met de projectie zelf, dan krijgen we volgende matrix:


Len Buckens

Hierbij stelt (θx, θy, θz) de coördinaat van het snijpunt van de kijrichting met het projectievlak voor (kx,ky,kz) is de richtingsvector van de kijrichting (ix,iy,iz) en (jx,jy,jz) zijn de orthogonale richtingsvectoren.

C) Clipping = de selectie van alle elementen in de perspectieve projectie die binnen de viewport liggen (wat de kijker dus kan zien) 1. In 3 dimensies clipt men 3D-objecten ten opzichte van de piramide met top in het oogpunt vooraleer men ze perspectief projecteert. 2. Bij 2D-clipping worden eerst alle objecten (ook deze die volledig buiten de piramide liggen) geprojecteerd vooraleer men ze clipt tov de viewport.


Len Buckens

Vraag 6: Het algoritme van Cyrus-Beck Cyrus a. Geef het doel, de toepasbaarheid, en de beperkingen van het algoritme, en de volledige uitwerking van het principe. Pas het algoritme stap-voor-stap stap toe op volgende viewport (figuur ( wordt gegeven)) en een lijnstuk met eindpunten ... . (§2.3.2) b. Hoe clipt men meer ingewikkelde krommen en figuren ? A) Doel: Het Cyrus-Beck Beck algoritme werd ontworpen om clipping van lijnen tov om het even welke convexe veelhoek mogelijk te maken.

Toepasbaarheid Het algoritme kan ook toegepast worden op rechthoekige viewports van perspectieve projecties. Mits een aantal triviale aanpassingen kan het ook gebruikt worden voor 3D3D clipping tov convexe veelvlakken. Uitwerking In dit algoritme werkt men met de parametervoorstelling van een lijnstuk [P1,P2]. Een willekeurig punt van de rechte lijn door P1 en P2 wordt gegeven door P(t) = P1 + t(P2 – P1). Als t ≤ 0 ≤ 1 dan ligt P(t) op het lijnstuk [P1, P2]. De kern van het algoritme is het opsporen van de t-waarden t waarden van de intersecties met de verschillende zijden van de viewport en hieruit bepalen of het lijnsegment gedeeltelijk/volledig binnen de viewport ligt. Met et elke zijde van de viewport wordt een inwendige normaal n geassocieerd. Indien f een willekeurig punt van die zijde is, kan met aan de hand van het teken van het scalair product n ● [P(t) – f ] bepalen waar een willekeurig punt P(t) zicht tov die zijde bevindt.

Is n ● [P(t) – f ] > 0 dan ligt P(t) aan dezelfde kant van de inwendige normaal, anders niet. Is n ● [P(t) – f ] = 0 dan is P(t) op de rechte door de zijde gelegen. Enkel als ni ● [P(t) – fi ] ≥ 0 voor alle zijden i, dan bevindt P(t) zich binnen of op rand van de viewport. In een eerste stap berekent het algoritme alle ni ● [P(t) – fi ] functies en de overeenkomstige ti waarden waarvoor deze functies nul worden. Er zijn 3 mogelijkheden:

1. Geven alle ni ● [P(t) – fi ] functies niet-negatieve negatieve waarden voor zowel t=0 als t=1 dan ligt het overeenkomstige lijnstuk volledig binnen de veeloek. 2. Is dit enkel het geval voor t=0 of t=1 dan ligt het lijnstuk zeker partieel binnen de veelhoek en moet men op zoek gaan naar het snijpunt. Men moet dan op zoek gaan


Len Buckens

naar het uniek snijpunt. 3. Wordt niet voldaan aan ni ● [P(t) – fi ] ≥ 0 voor zowel t=0 als t=1 dan kan het lijnstuk zowel partieel binnen als volledig buiten de veelhoek liggen. Hiertoe worden alle tj waarden die voldoen aan 0 ≤ tj ≤ 1 weerhouden en gesorteerd. Voor elk van deze waarden gaat men opnieuw na of ni ● [P(tj) – fi ] ≥ 0 voldaan is. De kleinste en grootste tj waarden waarvoor deze voorwaarde geldt, geven de gezochte snijpunten.

B) Meer ingewikkelde krommen en figuren clipt men in 2 stappen: Eerst berekent men een omhullende rechthoek of veelhoek van de figuur en clipt men alle zijden ervan met de viewport. Op deze manier probeert men te achterhalen of de figuur zich volledig binnen, volledig buiten of slechts partieel binnen de viewport bevindt. Enkel in het laatste geval splitst men vervolgens de kromme in segmenten die hetzij volledig binnen hetzij volledig buiten de viewport liggen.

Voorbeeld oef:

Voor lijnstuk P1P2: bereken de 4 parameterfuncties (in elke richting). Zoek de twaarden waarvoor deze nul worden, dus: -1/6, 7/6, -1/2, 3/2. Al deze functie geven niet negatieve waarden voor t=0 en t=1, deze rechte ligt volledig binnen de rechthoek rechthoek.

Voor lijnstuk P3P4: bereken de 4 parameterfuncties (in elke richting). Zoek de t-waarden waarvoor deze nul worden, dus: 6/5, 14/5, 1/5, 1. Voor t=0 zijn er negatieve functies. func Voor t=1 zijn er ook negatieve functies. Het lijnstuk kan dus gedeeltelijk binnen of volledig buiten de rechthoek liggen. We gaan nu voor alle waarden /5, 14/5, 1/5, 1 na of ze de functies niet-negatief maken. Zowel 1/5 als 1 maken de eerste functie negatief. Het lijnstuk ligt dus niet binnen de viewport.


Len Buckens

We berekenen opnieuw de parameterfuncties en de nulpunten van deze functies: 1/10, 9/10, -1/2, 3/2. Voor zowel t=0 als t=1 zijn er negatieve functies. Dit lijnstuk ligt dus gedeeltelijk binnen of volledig buiten de rechthoek. We vullen nu alle waarden in in alle functies. We krijgen alleen niet-negatieve negatieve oplossingen, het lijnstuk ligt dus gedeeltelijk binnen nnen de rechthoek en de snijpunten zijn onze kleinste en grootste tt waarde: 1/10 en 9/10 Opm: we houden enkel rekening met t-waarden t waarden tussen 0 en 1, andere liggen niet op het lijnstuk (daarom wordt met -1/2 -1/2 geen rekening gehouden in de vorige oef. Die zou anders wel bv de eerste functie negatief maken)


Len Buckens

Vraag 7: Clipping a. Het algoritme van Cohen-Sutherland: geef het doel, de toepasbaarheid, en de beperkingen van het algoritme, en de volledige uitwerking van het principe. Pas het algoritme toe op relevante voorbeelden. Geef eveneens een variant van de techniek. (§2.3.1) b. Het algoritme van Sutherland-Hodgman: geef het doel, de toepasbaarheid, en de beperkingen van het algoritme, en de volledige uitwerking van het principe. Pas het algoritme stap-voor-stap toe op volgend voorbeeld: (figuur wordt gegeven) . (§2.3.3)

A) Doel Het zo vlug mogelijk detecteren of lijnstukken volledig binnen of met zekerheid volledig buiten een rechthoekige viewport liggen. Toepasbaarheid Het algoritme kan ook toegepast worden op individuele punten door deze te beschouwen als lijnstukken waarvan de eindpunten hetzelfde zijn. Het kan ook toegepast worden in drie dimensies, maar men doet liever beroep op het CyrusBeck algoritme of het Sutherland-Hodgman algoritme. Uitwerking


Len Buckens

Stap 1: Eerst wordt bepaald of lijnstukken binnen/buiten of gedeeltelijk binnen de viewport liggen. Lijnstukken ken waarvan beide eindpunten binnen de viewport liggen, liggen volledig binnen de viewport. Lijnstukken waarvan beide eindpunten samen links/rechts/boven/onder de viewport liggen, liggen volledig buiten de viewport. Voor andere is een meer diepgaande analyse nodig. Om deze eerste selectie te vereenvoudigen stelt het Cohen-Sutherland Cohen Sutherland algoritme voor om aan elk eindpunt van een lijnstuk een bitcode b3b2b1b0 te hechten: • • • •

b0 b1 b2 b3

= = = =

1 1 1 1

als als als als

het het het het

punt punt punt punt

zich zich zich zich

links van de viewport bevindt. rechts van de viewport bevindt. onder de viewport bevindt. boven de viewport bevindt.

Lijnstukken die zich volledig binnen de viewport bevinden, hebben een bitcode 0000. Als men een AND-operatie operatie uitvoert op 2 eindpunten van een lijnstuk die verschillend zijn van 0000 dan: • •

ligt het lijnstuk met zekerheide buiten de viewport als het resultaat niet 0000 is. Is het resultaat wel 0000, dan ligt minstens een deel van het segment buiten de d viewport. Bij deze laatste mogelijkheid is een 2e stap nodig.

Stap 2: Men kan aan de individuele bits van de codes van de eindpunten zien met welke zijden van de viewport intersectiepunten berekend moeten worden: enkel zijden waarvoor de overeenkomstige bit van het ene eindpunt 0 is, en in het andere eindpunt 1. Na het berekenen van de intersectie vervangt men het eindpunt met de overeenkomstige 11 bit door het intersectiepunt en past men het algoritme van Cohen-Sutherland Cohen therland opnieuw toe. Voorbeelden We nemen als eerste voorbeeld het lijnstuk [ab]. Voor eindpunt a is de bitcode 0000, voor eindpunt b ook. Het lijnstuk ligt dus volledig binnen de viewport. Als 2e voorbeeld nemen we lijnstuk [gh]. Voor eindpunt g is de bitcode: itcode: 0001, voor eindpunt h: 1000. AND-en en van deze bitcodes geeft 0000: er kan dus een deel binnen de viewport liggen. Voor bit 0 en bit 3 zijn de overeenkomstige bits in beide eindpunten verschillend: b3(g) = 0; b3(h) = 1 b0(g) = 1; b0(h) = 0 We moeten n dus enkel intersecties met de bovenzijde en linkerkant berekenen. We vervangen g door het intersectiepunt met de linkerzijde. Voor g’ is de bitcode nu: 0000. AND-en en met h geeft weer 0000. Nu is b3(g) = 0; b3(h) = 1. We berekenen dus opnieuwe een intersectiepunt, nu met de bovenzijde. bovenzijde. We vervangen het punt h door zijn intersectiepunt h’. Voor h’ is de bitcode 0000, net als g’: het lijnstuk [g’h’] ligt volledig binnen de viewport. voorbeeld 3: we nemen lijnstuk [ij]. Voor i is de bitcode 0100, voor j ook 0100. 0100 AND-en van


Len Buckens

beide bitcodes geeft 0100.. Aangezien dit niet gelijk is aan 0000 ligt het lijnstuk volledig buiten de viewport.

Variant Een variant van deze techniek vermijdt het berekenen van intersectiepunten. Indien de resultaatcode 0000 is, wordt rdt het midden van het lijnstuk berekend en wordt het algorimte recursief op beide helften toegepast. Indien een lijnstuk deels door de viewport gaat, moet men de iteratie doorvoeren tot wanneer men de precisie van een pixel bereikt heeft. Deze variant wordt wordt vooral toegepast wanneer het clipping algoritme in de harwdware geïmplementeerd wordt.

B) Doel: Het clippen van willekeurige (convexe of concave) gesloten en gevulde veelhoeken tov willekeurige convexe viewports. Toepasbaarheid Het algoritme kan zonder probleem veralgemeend worden tot 3D-clipping. 3D clipping. Uitwerking Op het eerste zicht lijkt dit een overbodig algoritme: men kan een gesloten veelhoek immers opvatten als een verzameling lijnen en op elk van deze lijnen een ander algoritme (Cyrus-Beck, (Cyrus CohenSutherland) toepassen. Volgende figuur toont aan dat dit niet zomaar het geval al is: het is voor een programma niet zomaar duidelijk welke punten hij moet verbinden. Dit algoritme omzeilt deze moeilijkheden door de veelhoek achtereenvolgens te clippen tov van de diverse halfvlakken bepaald door de zijden van de viewport en hun inwendige inwe normaal. Het algoritme houdt de veelhoek bij als een circulair gelinkte lijst van hoekpunten en werkt die lijst tijdens de verschillende stappen bij. In elke stap bepaalt het algoritme welke van de hoekpunten deel uitmaken van het beschoudwe halfvlak. Een groep van opeenvolgende punten in de lijst die niet behoren tot het halfvlak worden vervangen door de 2 snijpunten met de grensrechte van het halfvlak. Hierbij kan de circulair gelinkte lijst van hoekpunten uiteenvallen in meerdere componenten, componente die men elk individueel moet behandelen. Nadata alle halfvlakken aan de beurt geweest zijn, bevatten de circulair gelinkte lijsten een correcte representatie van de geclipte veelhoek. De volgorde waarin de diverse halfvlakken aan de beurt komen speelt geen g enkele rol Voorbeeld Deze viewport heeft 4 zijden, er zijn dus 4 stappen nodig. Bij het begin zitten in de ciculair gelinkte lijst 5 punten: A B C D E F


Len Buckens

•

Stap 1: we clippen de veelhoek tov het halfvlak gelegen aan de rechterkant van de linkerzijde. Punt A ligt buiten het halfvlak en wordt B’ B” vervangen door de 2 snijpunten met de grensrechte A” van dat halfvlak. De gelinkte lijst bevat volgende punten: A’ A” B C D E F

•

Stap 2: we clippen de veelhoek tov van het halfvlak ha gelegen aan de onderkant van de bovenzijde van de viewport. Punt B ligt buiten dit halfvlak en wordt vervangen door de 2 snijpunten met de grensrechte van dit halfvlak. De gelinkte lijst bevat volgende punten: A’ A” B’ B” C D E F.

•

A’

E’ E”

Stap 3: we clippen en de veelhoek tov van het halfvlak gelegen aan de linkerkant van de rechterzijde. Punt E ligt buiten dit halfvlak en wordt vervangen door 2 snijpunten met de grensrechte van dit halfvlak. De gelinkte lijst bevat nu volgende punten: A’ A” B’ B” C D E’ E” F Na deze stap hebben we al volgende figuur:

•

Stap 4: we clippen de veelhoek v tov het halfvlak gelegen en aan de bovenkant van de onderzijde van de viewport. De punten F en E” liggen buiten het halfvlak en worden dus vervangen door de snijpunten met de grensrechte van het halfvlak. De gelinkte lijst bevat nu volgende punten: A’ A” B’ B” C D E’ F’ F”.

E”

De veelhoek is nu volledig geclipt.


Len Buckens

Vraag 1: Rastering. en wordt de lijn te dun getekend

Recommend Documents