Parametriske_kurver
Kurvetilpassing
Grafikk
Børre Stenseth
Matematikk>Polynomer

Polynomer

Hva
hermv

Vi vet at vi har kontroll over tegnemuligheter for kurver og flater i planet og rommet ved enkle polygonrutiner. Det betyr at vi kan framstille hvilke former vi vil ved hjelp av en liste med punkter. Denne måten å tenke på har mange ulemper.

  • Vi må operere med svært mange verdier for å oppnå tilstrekkelig presisjon.
  • Det gir ikke en enkel metode for å generere kurver ut fra gitte geometriske føringer.
  • Vi har ikke en konsistent måte å skjøte kurver på, for å oppnå ønsket grad av kontinuitet. Med kontinuitet mener vi både geometrisk glatthet og kontinuitet i matematisk forstand.

Hensikten med dette kapittelet er å finne fram til et begrenset utvalg av fleksible matematiske modeller som bedrer situasjonen på disse områdene. Vi vil gå løs på problemstillingen etter følgende skjema.

  • Å bestemme polynomer ut fra geometriske krav
  • Utledning av Hermit-kurve. Generalisering av form
  • Utledning av Bezier-kurve på grunnlag av Hermit-kurven
  • Noen resonnementer om kontinuitet og glatthet
  • Tegning av Bezier-kurver i OpenGL

Polynomer

La oss først generalisere utledningen for linjer. I modulen Parametrisk form satte vi mer eller mindre intuitivt opp følgende uttrykk for en linje i planet:

      x(t)=(x2-x1)·t+x1
      y(t)=(y2-y1)·t+y1
    

Vi vil generalisere dette og utvide resonnementet til andre kurver enn linjer. Vi holder oss i planet.

Lineært polynom

Utledningen av uttrykket over kan vi generalisere slik:

En linje er beskrevet ved:

    Q(t)=| x(t),y(t) | = | axt+bx,ayt+by |
    

Vi setter som grensebetingelse at linjestykket skal ha endepunkter i P1(x1,y1) og P2(x2,y2).

Vi kan da sette opp:

        x(0)=bx=x1
x(1)=ax+bx=x2
        y(0)=by=y1
y(1)=ay+by=y2

Vi ser at vi har 4 ukjente koeffisienter som må bestemmes. Vi løser de to ligningssystemene og får

bx=x1
by=y1
ax=x2-x1
ay=y2-y1

De parametrisk ligningene for kurven blir:

    Q(t)=| (x2-x1)t+x1,(y2-y1)t+y1 |
    

slik som vi satte opp intuitivt i et avsnitt ovenfor.

Kvadratisk ved eksempel

Vi er imidlertid ikke fornøyd med bare å ha linjer og sirkler. Vi må kunne handtere krumming av mer eller mindre kompleks natur. Når vi tar opp dette, er det to komplikasjoner som melder seg:

  • Vi kan ikke nøye oss med lineære uttrykk for t. Vi vil holde oss til polynomer som redskap. Ut fra det vi vet om polynomer vet vi at et 2-grads uttrykk gir oss en enkel krumming, siden den deriverte er lineær. Et 3-grads uttrykk kan gi oss to krumminger.
  • Vi må spesifisere krummingen. Det er ikke nok å angi endepunktene, slik vi gjør for linjer.

For å få grep på det siste vil vi bruke den deriverte. Vi betrakter et 2.grads polynom.

    Q(t)=| x(t),y(t) | = | axt2+bxt+cx,ayt2+byt+cy |
    

Derivert med hensyn på t:

    Q'(t)=| x'(t),y'(t) | = | 2axt+bx, 2ayt+by|
    

Vi spesifiserer følgende krav til kurven:

  • Den skal gå gjennom punktet P1(0,0)(origo)
  • Den skal gå gjennom punktet P2(6,0)
  • Den deriverte, tangentvektoren, i P1 skal være R1(0,6)

Dette gir oss to ligningssett, hver med tre ligninger:

        x(0)=cx=0
x(1)=ax+bx+cx=6
x'(0)=bx=0
        y(0)=cy=0
y(1)=ay+by+cy=0
y'(0)=by=6

Vi ser at vi har 6 ukjente koeffisienter som må bestemmes. Vi løser de to ligningssystemene og får

      ax=6
bx=0
cx=0
ay=-6
by=6
cy=0

Den parametrisk ligningen for kurven blir

    Q(t)=|6t2,-6t2+6t|
    

og den deriverte

    Q'(t)=|12t,-12t+6|
    

Vi setter inn noen t-verdier:

Q(0) (0,0) som forutsatt
Q(0.25) (0.375,1.125)
Q(0.5) (1.5,1.5)
Q(0.75) (3.375,1.125)
Q(1) (6,0) som forutsatt

t2kurve

Vi ser at når vi har et kvadratisk uttrykk vil vi få en enkel krumming siden den deriverte er lineær. Skal vi ha mer avanserte kurveformer, må vi høyere grad i polynomet.

Kubisk ved eksempel

Vi holder oss fortsatt i planet og vil lage en kubisk form på den parametriske kurven.

    Q(t)=| x(t)=axt3+bxt2+cxt+dx,y(t)=ayt3+byt2+cyt+dy|
    

Når vi har et kubisk uttrykk vil vi kunne få mer komplisert kurve siden den deriverte er av 2. grad. Vi ser videre at vi har 8 ukjente koeffisienter som må bestemmes.

Vi spesifiserer følgende for kurven:

  • Den skal gå gjennom origo, P1(0,0)
  • Den skal gå gjennom punktet P4(6,0)
  • Den deriverte, tangentvektoren, i P1 skal være R1(0,6)
  • Den deriverte, tangentvektoren, i P4 skal være R4(0,-6)

(Vi bruker P1 og P4 for endepunktene for å innarbeide en terminologi som gjør det lettere å sammenligne med andre geometriske spesifikasjoner senere).

Dette gir oss to ligningssett, hver med fire ligninger:

        x(0)=dx=0
x(1)=ax+bx+cx+dx=6
x'(0)=cx=0
x'(1)=3ax+2bx+cx=0
        y(0)=dy=0
y(1)=ay+by+cy+dy=0
y'(0)=cy=6
y'(1)=3ay+2by+cy=-6

Vi løser og får

      ax=-12
bx=18
cx=0
dx=0
ay=0
by=-6
cy=6
dy=0

De parametrisk ligningene for kurven blir

    x(t)=-12t3+18t2
y(t)=-6t2+6t

og

    x'(t)=-36t2+36t
y'(t)=-12t+6

Vi setter inn noen t-verdier:

Q(0) (0,0) som forutsatt
Q(1) (6,0) som forutsatt
Q'(0) (0,6) som forutsatt
Q'(1) (0,-6) som forutsatt

Hermit-kurven

De betingelsene vi satte opp i eksempel 2, med å spesifisere de to endepunktene og den deriverte i begge endepunktene er utgangspunktet for en navngitt type kurver: Hermit-kurver. Vi generaliserer våre resonnementer til 3D og skriver generelt:

    Q(t)=| x(t),y(t),z(t) |
    =| axt3+bxt2+cxt+dx ,
       ayt3+byt2+cyt+dy,
       azt3+bzt2+czt+dz |
	

og

    Q'(t)=| x'(t),y'(t),z'(t) |
    =| 3axt2+2bxt+cx,
    3ayt2+2byt+cy,
    3azt2+2bzt+cz |
    

Vi konsentrerer oss om x(t) og setter opp det aktuelle ligningssettet generelt:

      x(0)= d = P1
      x(1)= a+b+c+d = P4
      x'(0)= c = R1
      x'(1)= 3a + 2b + c = R4
    

der altså P1 står for P1s x-komponent osv.

Vi ser uten videre at d=P1 og c=R1 . Vi substituerer disse verdiene i de to andre ligningene og får følgende som skal løses:

      a+b+R1+P1=P4
      3a+2b+R1=R4
    

Og løsningen blir:

      a=2P1-2P4+R1+R4
      b=-3P1+3P4-2R1-R4
      c=R1
      d=P1
    

Dette gir oss:

    x(t) =t3(2P1-2P4+R1+R4)+t2(-3P1+3P4-2R1-R4)+t(R1)+P1
=P1(2t3-3t2+1) + P4(-2t3+3t2)
+ R1(t3-2t2+t) + R4(t3-t2)

Vi får helt tilsvarende uttrykk for y(t) og z(t). Vi ser at x(0)=P1 og x(1)=P4.

Skrevet på denne formen ser vi at de fire geometriske betingelsene, P1, P4, R1, R4, veies med kubiske t-polynomer.

Blandingsfunksjonene, t-polynomene, er slik i området t [0..1]:

hermv

Vi vil dra nytte av denne betraktningsmåten og vil skille de geometriske betingelsene og de fire vektfunksjonene eller blandingsfunksjonene. Vi forsøker oss med en matriseform der vi skiller de geometriske betingelsene fra vektene.

    Q(t)=| x(t) , y(t) , z(t) |= T·MH·G
    

Der G uttrykker de geometriske føringene og M uttrykker vektfunksjonene.

hermit

[1]

Dette er et svært omfattende tema som behandles ganske forskjellig i ulike lærebøker i grafisk databehandling. Se ellers matematisk litteratur.

Referanser
  1. Computer Graphics: Principles and Practice in C (2nd Edition)James Foley, Andries van Dam, Steven K.Feiner, John F. Hughes1995Addison-Wesley0201848406
Vedlikehold
2003, Børre Stenseth
Matematikk>Polynomer
til toppen