linjär algebra

Nedan kommer följa förklaringar till enklare uträkningar som kan ske inom linjär algebra och hur de kan användas inom programmering och hur de på ett teoretiskt sätt kan användas för att skapa animationer. Vi kommer även gå in djupare vad vektorer är och hur de fungerar, vad deras relation till matriser är och hur matriser kan hjälpa oss räkna ut avancerade funktioner inom programmering för att skapa rörelse.

Lite kort först om vad en vektor är för något, En vektor kan enkelt beskrivas som en matematisk storhet som har både en riktning och en magnitud. En vektors startpunkt är alltid origo vilket resulterar i att de värde en vektor har som beskrivs med koordinater alltid kommer ha en riktning. Magnituden är längden på den pil som kan dras från origo till vektorns position. En vektors värden kan skrivas oftast som följande; A=(a1,a2,a3) denna vektorn är tredimensionell, Det finns inte riktigt någon begränsning på hur många värden en vektor kan ha men i vårt fall när vi jobbar med animation så är det tredimensionella och tvådimensionella vektorer som är viktiga. Vektorer kan även skrivas i matriser för att utföra avancerade uträkningar på dem detta ser ut på följande vis:

\mathbf{a} = \begin{bmatrix}  a_1\\  a_2\\  a_3\\ \end{bmatrix}

Addison och subtraktion inom vektorer är väldigt simpelt både om vi vore att räkna ut de och om vi vore att illustrera det på ett papper. När vi pratar om addition och subtraktion av vektorer kallar vi resultatet för en resultant. formeln för att addera eller subtrahera vektorer ser ut på följande vis:
u=(u1,u2)

v=(v1,v2)

summan av vektorerna ser ut på följande vis: (v1 + u1) , (u2 + v2)

differensen av vektorerna ser ut på följande vis: (v1 – u1) , (u2 – v2)

Om vi vore att illustrerar detta grafiskt med kommer det se ut på följande vis:

En annan bra bild som illustrerar hur vektor addition och subtraktion fungerar är denna, Bilden visar att vi kan använda oss av triangel metoden för att utföra uträkningen visuellt. vilket går ut på att vi lägger ut vektorerna grafiskt och resultanten är den vektor som är mellan start och slutpositionen av våra utlagda vektorer.

__https://i2.wp.com/www.physicsclassroom.com/mmedia/vectors/ao.gif

Jaha? hur kan vi använda oss av detta inom programmering då?

Jo om vi vore att utföra en linjär interpelation mellan två punkter krävs det att vi har följande; en vektor som startposition en vektor som slutposition som vi sedan kan använda oss av och multiplicera differensen mellan slut och start punkten med en skalar variabel, alltså en variabel som har ett värde mellan 0 och 1(0% – 100%) för att får ut ett mellan värde av vektorerna. värdet som vi sedan får ut ska adderas med våra startpunkt. värdet som skalaren har kommer ge oss vår animation varje gång den ändras får vi ett nytt värde som ligger i linje mellan vår slut och start vektorer.

funktionen för detta kan se ut på följande vis om vi skulle programmera den:

Vector3 Lerp(Vector3 start, Vector3 end, float percent)
{
     return (start + percent*(end - start));
}

https://i2.wp.com/upload.wikimedia.org/wikipedia/commons/4/47/Kuantil_kalkulurako_diagrama_hutsa.png
animationens rörelse i bild.

Om våra vektorer i detta exemplet är start=(3,3) end=(5,5) och låt oss säga att vår skalar variabel(procent) är 0.5  så är det detta som sker

i höger sidan tar vi end – start vilket ger oss ett värde på 2,2 om vi vore att addera detta med vår start punkt skulle vi ha ett värde på 5,5 vilket är vårt slut. men detta sker endast om vår skalar variabel är 1 då skulle (end – start) * 1 resultera i 2,2 som sedan adderas ihop med start för att ge oss vårt slut. Men om nu skalaren är 0.5 så är (end-start) * 0.5 = 1,1 som sedan adderas ihop med start för att ge oss 4,4 vilket är en vektor som är i mitten av 3,3 och 5,5.

Om vi vore att implementera detta i ett spel skulle vi få en rak animation, detta är alltså en av de enklaste animationerna vi kan göra. Men detta lägger grunden åt oss för mer avancerade formler. Även om det går att argumentera att det går mycket snabbare att göra detta direkt i ett animations program såsom matenee i UDK så går det inte argumentera emot att återanvändnings möjligheterna om vi gör det i kod både koden i sig och kunskaperna är otroligt mycket större än om vi vore att göra detta via ett program.

Det behövs även utmärkas här att detta inte är det ända sättet att skriva en linjär interpelation på. Det finns alltid många lösningar på problem, ett annat exempel att skriva samma sak som ovanstående funktion är:

Vector3 Lerp(Vector3 start, Vector3 end, float percent)
(
 return(start*(1-percent)+end*percent);
}

Men som sagt detta är allt linjär interpellation vilket inte är särskilt verklighets troget om vi går tillbaka och kollar på de grundläggande animations principerna så är det inte så här saker och ting rör sig i vår värld om det inte är maskiner. För att lyckas med något mer verklighetstroget som följer principen “Slow in and slow out” som vi kollade på tidigare behöver vi funktioner som kan ha ett värde som inte är linjärt. Här kommer funktioner som Cosine interpelation, Cubic interpelation eller Hermite interpellationin i bilden. Om vi börjar med att undersöka Cosine interpelation så kommer vi att få en kurva som liknar detta:

https://i2.wp.com/codeplea.com/wp-content/uploads/splines_1d_cosine.png

Detta är mycket mer verklighets troget om vi vore att ha rörelser som just behöver ha mjukare övergångar som till exempel en dörr som glider upp eller en arm som svingar i luften. En nackdel med Cosine interpelation är att det är matematiskt mycket mer complext än vissa andra konkurrenter. Då det använder sig av just Cosine funktionen då vi delar vilket ser ut på följande vis:

grader( hypotenusa / ajdecent)

Alltså tar vi o stoppar in hur många grader det är i bågen mellan adjecenten och hypotenusan i en rät rektangel för att sedan ta o räkna hypotenusans längd delat med accentens längd. om graderna är 0 så får vi ett värde av 1 då båda sidorna är lika långa, men är graderna 90 får vi ut 0 då accenten kommer vara ha en längd av 0. Funktionen för att programmera en Cosine Interpelation ser ut på följande vis:

double CosineInterpolate
(
   vector1 start,vector2 end,
   double procent)
{
   double procent2;

   procent2 = (1-cos(procent*PI))/2;
   return(start*(1-procent2)+end*procent2);
}

Detta är lite svårare att hänga med i vad som händer, men om vi börjar med att säga att det behövs då procent värden i denna uträkningen, dock kommer det fortfarande endast finnas en som du själv styr värdet på för att få ut ett slutgiltigt värde på animationen och detta är som tidigare variabeln “procent” som definieras som “double procent” double innebär att det är en variabel som har decimaler medan det som följer är namnet på variabeln i detta fallet procent.

Första delen av uträkningen går ut på att skaffa oss det andra procent värdet “procent2” formeln ser altså ut såhär:(1-cos(procent*PI))/2 , vi tar alltså bort 1 från cos utav procent * PI för att sedan dela det på två. Om vi antar att får första procent har ett värde som tidigare 0.5 så ser alltså formeln ut så här: (1 –  cos(1.57) )/2 , resultatet av cos(1.57) är

0.000796327
detta räknas inte ut som vi i vanliga fall via Sohcahtoa som vi skulle göra det utan en mer optimerad avancerad sökande algoritm som heter “CORDIC algorithm” vilket du kan finna längst ner på detta inlägg.
har vi ett och tar bort detta värdet får vi sedan ut:

0.999204…

detta i sin tur delat med två är vår”procent 2″ vilket är:

0.499602

Nu har vi altså fått ut procent2.

 return(start*(1-procent2)+end*procent2);

Nu är det bara sista delen som återstår vilket ser väldigt enkelt jämfört med den fösta. Vilket är för att du antagligen känner igen den lite, Detta beror på att nu gör vi en samma funktion som i den linjära interpellationen fast med percent2 istället för percent.

Denna formlen kan verka enkel och smidig fast börjar vi kolla hur mycket prestanda krävande det är, Så kan vi kolla vad som egentligen händer under CORDIC Algorithm som en dator använder sig för att räkna ut Sin() och Cos() så behöves det många integrationer av en ekvation lösas för att få ett dugligt resultat.  Det finns det mycket mer optimerade lösningar som t.ex. Cubic interpelation som ser ut på följande vis:

double CubicInterpolate(
   vector y0,vector y1,
   vector y2,vector y3,
   double mu)
{
   double a0,a1,a2,a3,mu2;

   mu2 = mu*mu;
   a0 = y3 - y2 - y0 + y1;
   a1 = y0 - y1 - a0;
   a2 = y2 - y0;
   a3 = y1;

   return(a0*mu*mu2+a1*mu2+a2*mu+a3);
}

Formeln är mycket längre i kod med i data kostnad är den mycket billigare då det endast är vanlig multiplikation addition och subtraktion som gäller genom hela formeln. Ett problem med Cubic är dock att kurvans böjningar baseras på föregående vektors värde så om vi har en start behövs en låsas start position före starten för att ge en smooth kurva från början, samma gäller vid slutet.

Oj vad mycket matte det blev nu, Men vi märker redan att vi kommer kunna ha mycket nytta av det vi gått igenom när det kommer till optimering av animationer vilket är en av de anledningarna till att vi vill använda oss av kod från början. Om vi vore att koda helt utan att förstå oss på matten kan någon funktion som bara har några rader kod och verka enkel och snabb vara långsam och prestanda krävande om vi inte förstår hur matten egentligen fungerar.

ett bra exempel på detta är när vi ska räkna ut magnituden av en vektor vilket som vi tidigare vet ser ut så här:

||A||=  sqr(v1^2 + v2 ^2)

uscript: Vszice(v1,v2);

detta är ganska kostsamt på grund av att vi använder oss av roten ur. Ett bra alternativ till detta om vi endast vill göra en distans check mellan två punkter är att skippa roten ur och bara multiplicera upp resultatet av funktionen tills vi får ett värde som är tillfredsställande.

alltså:

v1^2 + v2 ^ 2 * X

uscript: VSizeSq(v1,v2);

CORDIC algorithm
Implementaion av CORDIC alogrithm i MathLab

function [x, y, z] = cordic_rotation_kernel(x, y, z, inpLUT, n)
% Perform CORDIC rotation kernel algorithm for N iterations.
xtmp = x;
ytmp = y;
for idx = 1:n
    if z < 0
        z(:) = accumpos(z, inpLUT(idx));
        x(:) = accumpos(x, ytmp);
        y(:) = accumneg(y, xtmp);
    else
        z(:) = accumneg(z, inpLUT(idx));
        x(:) = accumneg(x, ytmp);
        y(:) = accumpos(y, xtmp);
    end
    xtmp = bitsra(x, idx); % bit-shift-right for multiply by 2^(-idx)
    ytmp = bitsra(y, idx); % bit-shift-right for multiply by 2^(-idx)
end

________________________________________________________________________________

Referens lista:

hotmath, Adding and Subtracting Vectors: http://hotmath.com/hotmath_help/topics/adding-and-subtracting-vectors.html

Keith M, Febuary 15, 2011, Math Magician – Lerp, Slerp, and Nlerp   http://keithmaggio.wordpress.com/2011/02/15/math-magician-lerp-slerp-and-nlerp/

Paul Bourke, December 1999, Interpolation methods: http://paulbourke.net/miscellaneous/interpolation/

Bryan Dorner, November 19-22, 1998 ,The Magic Calculator and The Sine Addition Formula :http://archives.math.utk.edu/ICTCM/EP-11/C26/paper.pdf

University of Osclo, 2012, CORDIC Algorithm: http://www.uio.no/studier/emner/matnat/ifi/INF5430/v12/undervisningsmateriale/dirk/Lecture_cordic.pdf

MathWorks: Compute Sine and Cosine Using CORDIC Rotation Kernel: http://www.mathworks.se/help/fixedpoint/ug/compute-sine-and-cosine-using-cordic-rotation-kernel.html

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s