Oefening1: constructie van de controlepunten van de uniforme Lagrange representatie van een Lagrange geïnterpoleerde kromme met niet-uniforme knopenvector



Dovnload 59.2 Kb.
Datum27.08.2016
Grootte59.2 Kb.
Oefening1: constructie van de controlepunten van de uniforme Lagrange representatie van een Lagrange geïnterpoleerde kromme met niet-uniforme knopenvector; schematisch aantonen hoe de berekening van de Bézier representatie van deze kromme zou kunnen uitgevoerd worden (ondermeer opstellen van de inverse van de Bézier basismatrix).

Deel 1
Overgang van niet-uniforme naar uniforme knopenvector: zorg gewoon dat de knopen in de knopenvector een rekenkundige rij vormen. Vb: niet-uniform: {0,3,6,12}  uniform {0,4,8,12}.

Constructie van de nieuwe datapunten op de figuur. De datapunten P0 en P12 blijven in dit voorbeeld dezelfde. We berekenen de nieuwe dat apunten P4 en P8 door 2 maal de constructie te maken, 1 keer voor t=4 en 1 keer voor t=8, zo bekomen we de nieuwe datapunten.

Vb: voor P03 en t=4 ligt 4 niet tussen 0 en 3. Het punt zal dus voorbij P3 liggen. Je beschouwt dan de rechte door P0 en P3 en beschouwt punt P0 als abscis 0 en P3 als abcis 3, je moet P03 tekenen op abscis 4. Ofwel: het punt ligt op 1/3 keer de afstand tussen P0 en P3 voorbij P3.


Voor P6 12 ligt 4 niet tussen 6 en 12. Het punt zal dus voor P6 liggen. Je beschouwt opnieuw de rechte door P6 en P12 met P6 abscis 6 en P12 abscis 12. Je tekent nu het nieuwe punt met abscis 4. Ofwel: het punt ligt op 2/6 keer de afstand tussen P6 en P12 voor P6.


Berekening via piramidaal schema kan als controle, zo kan je de coördinaten van de hulppunten achterhalen.. Piramide 2 keer berekenen, 1 keer voor t=4 en 1 keer voor t=8. Gebruik telkens de oorspronkelijke punten als basis.


Deel 2
De eerste matrix is de matrixrepresentatie van een Bézier kromme van graad 3.

Berekenen van de inversie Bézier matrix geeft:



Om de inverse te berekenen zetten we naast de oorspronkelijke matrix een eenheidsmatrix en vegen we de matrix naar de normaalvorm. De oorspronkelijke eenheidsmatrix is dan onze inverse matrix.

Het berekenen van de Lagrange matrixpresentatie moet hier niet, maar is te bekomen door alle pijlen in het schema van Neville om te draaien. In de top de constante 1 te plaatsen. Je bekomt dan voor ieder basispunt een mengfunctie door voor alle alternatieve paden van de top naar het punt de factoren langs dat pad te vermenigvuldigen en dan de uitkomsten voor de verschillende paden naar een punt op te tellen. Je krijgt dan voor ieder basispunt een functie in t van de derde graad. De coefficienten van de functie van het meest linkse punt vul je in op de bovenste rij. Coefficienten van het 2de punt op de 2e rij enz.






Oefening 2: constructie van een triangulair schema met behulp van het veralgemeend algoritme van Neville (voor een specifieke configuratie van inputgegevens), en berekening hieruit van de gewichtsfuncties en de matrixrepresentatie.




  • stel het schema van Neville om, de gewichtsfacten blijven dezelfde.

  • draai alle pijlen om

  • zet in de top de constante 1

  • de mengfunctie in een bepaald basispunt bereken je door:

    • op zoek te gaan naar de alternatieve paden van de top naar dit basispunt (voor punt 1 is dit bv 1 pad, voor punt 2 zijn dit 2 paden)

    • de gewichtsfactoren lang een bepaald pad te vermenigvuldigen (voor punt 1 is dit bv )

    • tel de bijdragen van de verschillende bijdragen bij elkaar op (voor punt 2 is dit bv: 

  • Je bekomt voor elk basispunt van het schema in dit geval een functie van de 3e graad in t. vb: L0,3(t) = at3 +bt2 +ct +d ; L1,3(t) = et3 +ft2 +gt +h ;… Dit zijn de gewichtsfuncties.

  • Plaats de coefficenten van het meest linkse basispunt op de eerste rij in de matrix, de coefficienten van het 2e basispunt op de 2e rij enz.







Voorbeeld van een matrixrepresentatie:

Indien er voor een bepaald (hulp)punt slechts 1 index i voorkomt dan moet gebruikt gemaakt worden van de Talor reeksontwikkeling







Oefening 3: segmentering (subdivisie) van Bézier krommen (eventueel meerdere segmenten in één enkele stap)

We maken hier gebruik van het algoritme van de Casteljau. We gebruiken hier telkens de gewichtsfactoren 1-t (links) en t (rechts). Met dit schema segmenteren we in 2 stukken. Willen we bv in 1 keer in 2 segmenten segmenteren, dan moeten we ook een 2e schema opstellen (en hier dan bv s gebruiken ipv t).

Constructie op de figuur:


  • Segmenteren in 2 segmenten:

    • P
      t
      as telkens t af tussen de bestaande punten.

    • Verbind de bekomen punten

    • P
      t
      as op deze ook telkens t af

    • Verbind…


  • Segmenteren in 3 segmenten

    • P
      t
      as telkens t en s af tussen de bestaande punten

    • Verbind de bekomen punten

    • Pas op deze ook telkens t en s af

    • Verbind…



t

s


Oefening 4: verhoging van de graad van Bézier splines (stapsgewijs: één graad verhogen per stap)

Een parametervoorstelling van een kromme van graad n kan ook voorgesteld worden als een uitdrukking van graad m>n waarbij de m-n coëfficiënten van de hoogste graad (m dus) 0 zijn.

De datapunten van de kromme blijven dezelfde. Er wordt 1 nieuw controlepunt ingevoerd.
Wanneer we slechts 1 graad verhogen is

Passen we dit toe op een kromme van graad 3 om deze te verhogen naar graad 4, dan is:


n=3. Een kromme van graad 3 heeft 4 punten: P000, P001, P011, P111.
We zoeken dus 5 punten van de kromme met graad 4: Q0000, Q0001, Q0011, Q0111, Q1111











Om dit op de figuur te construeren doen we het volgende:

We tekenen Q0001 op ¼ afstand van P001 en op ¾ afstand van P000. Zo tekenen we Q0011 of ½ afstand van P011 en ½ afstand van P001. En zo tekenen we Q0111 op1/4 afstand van P001 en ¾ afstand van P111

Oefening 5: verhoging van de graad van Bézier splines (in één enkele stap); voorafgaand moet het verband tussen de oude en de nieuwe controlepunten opgesteld worden (vermenigvuldiging met een specifieke matrix, cfr. theorieles)

Om in 1 stap meerdere graden te verhogen maken we gebruik van de formule :

Simpeler uitgelegd:


  • Je berekent eerst het aantal mogelijke combinaties van n indexen uit m (met n hier gelijk aan de vorige graad, en m gelijk aan de nieuwe graad). Verhogen we bv van graad 3 naar graad 6, dan is dit 20. We gebruiken dit getal straks om door te delen. 


  • We tellen nu alle mogelijke punten met als blossomnotatie een deelverzameling van n elementen uit de argumentenlijst van m elementen. Vb 001  00, 01 en 01

Voorbeeld: oude graad is 2 (n), nieuwe graad is 4 (m). We hebben als ‘oude’ punten P00, P01 en P11. De nieuwe punten zullen Q0000,Q0001,Q0011,Q0111 en Q1111.
De factor waardoor we zullen delen is (4.3.2.1)/((2.1).(2.1)) = 6










Matrix:




Op tekening:



  • voor Q0001 passen we ½ af tussen P00 en P01

  • voor Q0011 vormen we de gelijkheid om naar
    
    We tekenen dus de lijn door P00 en P01 op 1/5 van het punt P01 een hulppunt, bv R. Op de lijn door R en P11 tekenen we op 1/6 van P01 het punt Q0011

  • voor Q0111 passen we ½ af tussen P01 en P11

Oefening 6: de Casteljau constructie (van een punt met specifieke parameterwaarde) van een Bézier kromme.

We maken gebruik van een piramidaal schema. Op de basis zetten we de inputgegevens in volgende van het aantal b-elementen in de blossomnotatie (0000<0001<0011…). Uitwerking zie figuur.

aangezien altijd 

en altijd 

kunnen we het schema vereenvoudigen.

Constructie op figuur: (hier uitgewerkt voor graad 4)



  • Neem punt P0000 en P0001 en teken op t*afstand tussen de 2 punten het punt P000t

  • Neem punt P0001 en P0011 en teken op t*afstand tussen de 2 punten het punt P00t1

  • Neem punt P000t en P00t1 en teken op t*afstand tussen de 2 punten het punt P00tt

  • Enz


t

t


t

t


Oefening 7: constructie van de hodograaf van een Bézier kromme of spline

We contrueren het schema van de Casteljau. Op het laagste niveau voeren we nu echter de 1e afgeleide type basisblokken in. Let op de P’(t)/3 in de top. Het getal waardoor men deelt is altijd gelijk aan n (de graad van de kromme) omdat P(t)P[t,t,…,t]  P’(t) = nP[t,t,…t, μ]


Daarom moeten we hieronder alles vermenigvuldigen met n.

Voorbeeld voor een kromme van de 3e graad:


P00μ = 3(P001-P000)
P01μ = 3(P011-P001)
P11μ = 3(P111-P011)

Constructie op tekening:



  • we passen volgens de rechte door P000 en P001 een afstand af dat 3 keer de afstand is tussen P000 en P001 vertrekkend uit punt P000


  • idem voor P001 en P011

  • idem voor P011 en P111

We verschuiven deze lijnstukken met hun beginpunt naar de oorsprong van het assenstelsel.
We weten dat de afgeleide van een Bézier kromme zelf een Bézier kromme is van een graad minder. In dit voorbeeld heeft de afgeleide kromme dus ook 2 datapunten, maar slechts 1 controlepunt. De hodograaf is bijgevolg de kromme die door deze 2 datapunten gaat en bepaald wordt door het controlepunt.



Oefening 8: vaststellen van de continuïteit in de knooppunten van Bézier splines (stelling van Stärk)

We hebben 2 krommen van graad n: { P[a,…a], P[a,…,a,b], …, P[a,b,…,b], P[b,…,b]} en


{ Q[b,…,b], Q[b,…,b,c], … Q[b,c,…,c],Q[c,…c] } met gemeenschappelijk punt P[b,…,b]=Q[b,…b]

Passen we dit toe op een voorbeeld bestaande uit 2 segmenten en data- en controlepunten voor het linkersegment P[a,a,a], P[a,a,b], P[a,b,b] en P[b,b,b] en voor het rechtersegment Q[b,b,b], Q[b,b,c], Q[b,c,c] en Q[c,c,c]



  • aangezien we een gemeenschappelijk contactpunt hebben, hebben we minimaal C0 continuïteit; P[b,b,b]Q[b,b,b]

  • Om C1 continuïteit te bereiken moet volgens de stelling van Stärk indien men de argumenten van controlepunt P[a,b,b] evalueert in de blossom van het rechtersegment, dit een punt Q[a,b,b] opleveren dat samenvalt met P[a,b,b]



Voorbeeldje voor graad 3

Om het punt Q[a,b,b] te construeren gebruiken we de lijn door P[b,b,b] en Q[b,b,c] en tekenen we daar het punt Q[a,b,b] volgens de bijhorende gewichten (2 rode pijlen bovenaan)

Voor Q[b,b,c] idem

Valt P[a,b,b] samen met Q[a,b,b] dan is het C1 continu.

Is op een volgend niveau deze voorwaarde ook voldaan, dan is het C2 continu enz
Oefening 9: constructie van de Bézier representatie van een (polynomiale) NURBS

De knooppunten van de B-spline worden datapunten van de Bézier-representatie. We hebben dus evenveel datapunten in de Bézier representatie als er knooppunten zijn in de B-spline.

In dit voorbeeld hebben we knopenvector {-1,0,1 ; 2,3,4,5 ; 6,7,8 }. We hebben hier 4 reële knopen. De Bézier representatie zal dus 4 datapunten hebben en zal bijgevold uit 3 segmenten bestaan.

Constructie:



  • Tussen punt 012 en 123 heb je 2 punten: 112 en 122. Deze bekom je door het punt 012 de waarde 0 te geven en 123 de waarde 3 te geven. Het punt 112 ligt dan op de ‘waarde’ 1 tussen de 2 punten en het punt 122 ligt op de ‘waarde’ 2 tussen die 2 punten.


  • Op het lijnstuk met de punten 234 en 345 liggen ook 2 punten: 334 en 344. Deze punten bekomen we door het punt 234 de waarde 2 te geven en het punt 345 de waarde 5 te geven. Het punt 334 ligt dan op waarde 3 tussen de 2 punten en het punt 344 ligt op de waarde 4 tussen de 2 punten.


  • Enz…


  • Daarna verbindt je alle punten die 2 indices gemeenschappelijk hebben: vb: punt 122 en punt 223. Tussen deze punten ligt punt 222. We bekomen dit punt door aan het punt 122 de waarde 1 toe te kennen en aan het punt 223 de waarde 3 toe te kennen. Het punt 222 ligt dan op waarde 2 tussen de 2 punten.



  • Indien we bv een B-spline hebben van orde 5 (graad 4) dan moeten we ook nog eens alle punten die 3 indexen gemeenschappelijk hebben verbinden en het tussenliggend punt tekenen:


In principe komt het neer op het volgende: teken alle tussenliggende punten. De punten waarvan alle index gelijk zijn (vb: 22, 444, 7777) zijn de datapunten van de Bézier kromme.



Oefening 10: de Boor constructie (van een punt met specifieke parameterwaarde) van een (polynomiale) NURBS

Hierbij gebruiken we een piramidaal schema dat bijna identiek is aan het schema van de Casteljau.





Oefening 11: constructie van controlepunten na toevoeging van één of meerdere reële knopen in de knopenvector van een (polynomiale) NURBS (zonder over te gaan op de Bézier representatie)

We voegen de knoop gewoon tussen in de knopenvector (heeft het multipliciteit 2, dan voegen we het 2 keer tussen, enz).

Vb: oorspronkelijke knopenvector: {0,1,2 ; 3,5,6,8,9,11 ; 14,15,16}
We voegen de knoop t=7 toe: {0,1,2 ; 3,5,6,7,8,9,11 ; 14,15,16}

We berekenen de nieuwe controlepunten met het de Boor schema. We moeten voor een knooppunt met multicpliciteit 1 slechts 1 iteratie uitvoeren (algoritme van Böhm)



We contrueren daarna de nieuwe punten Q1 Q2 en Q3 op de figuur.


Wanneer we een knoop toevoegen met multipliciteit 2, dan moeten we 2 iteraties uitvoeren:




4 punten worden dan vervangen door 6 punten.
We voegen de knoop t=7 toe: {0,1,2 ; 3,5,6,7,7,8,9,11 ; 14,15,16}
Voor multipliciteit 3 moeten we dan 3 iteraties uitvoeren.

Vraag 12: constructie van controlepunten na toevoeging van één of meerdere virtuele knopen in de knopenvector van een (polynomiale) NURBS (zonder over te gaan op de Bézier representatie)

  1. Is de virtuele knoop die we moeten toevoegen de meest extreme virtuele knoop, dan vervangen we deze gewoon door de nieuwe en dan blijven alle andere controlepunten ongewijzigd (geen enkele van deze controlepunten is immers afhankelijk van de meest extreme virtuele knoop)

    ( t0 , t1 , t2 , ... , tk-2 ; tk-1 , tk , tk+1 , ... )


    ® ( tx , t1 , t2 , ... , tk-2 ; tk-1 , tk , tk+1 , ... )

  2. Is de nieuwe virtuele knoop niet de meest extreme, dan moeten we nieuwe controlepunten bereken. We moeten daarvoor een piramidaal schema opstellen met de omliggende punten. We hebben evenveel ‘oude’ nodig op de basis van de piramide als de graad n.


Vraag 13: constructie van een benadering door lijnstukken van een uniforme NURBS door toepassing van het algoritme van Lane & Riesenfeld

Op de figuur telkens de helft afpassen tussen 2 punten. Deze punten verbinden. Opnieuw de helft afpassen en verbinden.


Vraag 14: berekening en constructie van de controlepunten van de open-uniforme representatie van een (polynomiale) NURBS met een uniforme knopenvector

Bij een uniforme vormen alle knopen (virtuele en reële) een rekenkundige rij. Bij een open-uniforme vormen enkel de reële knopen een rekenkundige rij. De meeste extreme reële knopen worden dus k maal herhaald. Een open-uniforme gaat door het eerste en het laatste controlepunt, een uniforme niet.

Vb: uniform: {-1,0,1 ; 2,3,4,5 ; 6,7,8}  open-uniform {2,2,2 ; 2,3,4,5 ; 5,5,5}



Vraag 15: berekening en constructie van de controlepunten van de uniforme representatie van een (polynomiale) NURBS met een open-uniforme knopenvector

Bij een uniforme vormen alle knopen (virtuele en reële) een rekenkundige rij. Bij een open-uniforme vormen enkel de reële knopen een rekenkundige rij. De meeste extreme reële knopen worden dus k maal herhaald. Een open-uniforme gaat door het eerste en het laatste controlepunt, een uniforme niet.

Vb: open-uniform {2,2,2 ; 2,3,4,5 ; 5,5,5}  uniform {-1,0,1 ; 2,3,4,5 ; 6,7,8}



Oefenigen computergrafiek Len Buckens 2008






De database wordt beschermd door het auteursrecht ©opleid.info 2017
stuur bericht

    Hoofdpagina