{"id":1950,"date":"2014-01-23T16:27:27","date_gmt":"2014-01-23T15:27:27","guid":{"rendered":"http:\/\/www.hinnerup.net\/?p=1950"},"modified":"2014-07-04T10:48:25","modified_gmt":"2014-07-04T09:48:25","slug":"bezier_spline_shader","status":"publish","type":"post","link":"https:\/\/www.hinnerup.net\/en\/permanent\/2014\/01\/23\/bezier_spline_shader\/","title":{"rendered":"B\u00e9zier Spline Distance Glow"},"content":{"rendered":"

I Hinnerup Net har vi, mest bare fordi vi kan, udviklet en WebGL shader<\/a> der k\u00f8rer p\u00e5 computerens GPU (bedre kendt som grafikprocessor). Shaderen beregner konstant afstanden fra et vilk\u00e5rligt punkt til en dynamisk skiftende kvadratisk B\u00e9zier-kurve<\/a>.<\/p>\n

Advarsel:<\/b> Formler f\u00f8lger herefter i stride og voldsomme m\u00e6ngder. Hvis du vil direkte til demoen s\u00e5 hop til bunden af indl\u00e6gget! \ud83d\ude09<\/p>\n

Indenfor computer-graphic omr\u00e5det er B\u00e9zier-kurver ikke til at komme udenom. Oprindeligt blev Bernsteins polynomie<\/a> introduceret som en del af teoretisk matematik i 1800-tallet af Charles Hermite<\/a> og Sergei Bernstein<\/a>. B\u00e9zier-kurven, der er en udvidelse heraf, blev en realitet i 1900 tallet, da Pierre B\u00e9zier<\/a> og Paul de Casteljau<\/a>, fandt p\u00e5 at bruge del-summene i Bernsteins polynomie til at skalerere et array af vektorer (ogs\u00e5 kaldet kontrolpunkter).<\/p>\n

Ligningen for en B\u00e9zier-kurve af nte<\/sup>-grad er som f\u00f8lger:<\/p>\n

\"AnyBezierSpline\"
<\/a>P(t)<\/b> er et punkt P, som \u00e6ndrer sig som en funktion af t.
t<\/b> er en floating point v\u00e6rdi, som bruges i intervallet 0.0 til 1.0.
n<\/b> er en integer, som har v\u00e6rdien antal kontrol punkter minus 1.
i<\/b> er en integer, som bev\u00e6ger sig fra 0 til n.
P <\/b>er et array af vektorer eller kontrol punkter, som indekseres af integeren i.
!<\/b> er fakultet tegnet, som er produktet af en talr\u00e6kke af de positive hele tal fra 1 til og med tallet selv. Fakultet-funktionen n! kan dermed udtrykkes som:<\/p>\n

\"Fakultet\"
<\/a>En B\u00e9zier-kurve af nte<\/sup>-grad har n+1 kontrolpunkter. I dette tilf\u00e6lde \u00f8nsker vi at have 3 kontrolpunkter. Derfor skal ligningen blot l\u00f8ses for n = 2, hvilket giver f\u00f8lgende:<\/p>\n

\u00a0\"QuadraticBezier\"
<\/a>Herunder er koden til at beregne et punkt p\u00e5 B\u00e9zier-kurven.<\/p>\n

vec2 getPositionOnBezierCurve(float t, vec2 p0, vec2 p1, vec2 p2) \r\n{\r\n\tfloat fOneMinusT = 1.0-t;\r\n\tvec2 pos = fOneMinusT*fOneMinusT*p0+2.0*fOneMinusT*t*p1+t*t*p2;\r\n\treturn pos;\r\n}<\/pre>\n
\u00a0Hvis det undlades at gange kontrolpunkterne p\u00e5 hver af del-summene i Bernsteins polynomial, kommer de 3 kurver af t til at se s\u00e5ledes ud:<\/p>\n
\"QuadraticBernstein\"
<\/a>Hvis de 3 kontrolpunkter bliver ganget p\u00e5 de 3 kurver af t, s\u00e5 bliver resultatet en kvadratisk B\u00e9zier-kurve.<\/p>\n
\"GraphOfQuadraticBezier\"
<\/a>At finde afstanden imellem et vilk\u00e5rligt punkt Q og denne kvadratiske B\u00e9zier-kurve er overkommeligt hvis t er 0.0 eller 1.0, da P(t) jo her vil give henholdvis det f\u00f8rste eller sidste iforvejen kendte kontrolpunkt. Men da shaderen skal virke med et vilk\u00e5rligt punkt Q og en vilk\u00e5rlig kvadratisk B\u00e9zier  kurve skal der lidt mere formel-galop til.\u00a0For at kunne beregne den korteste afstand imellem et vilk\u00e5rligt punkt Q og et punkt p\u00e5 B\u00e9zier-kurven P(t) skal tangenten til P(t) anvendes. Tangenten beregnes ved at finde den afledte af funktionen P(t).<\/p>\n
\"DerivativeQuadraticBezierSpline\"<\/a><\/p>\n

Ligningen for tangenten til P(t) kan omskrives til:<\/span><\/p>\n
\"DerivativeQuadraticBezierSpline1\"
<\/a>Dette kan reduceres yderligere til:<\/span><\/p>\n
\"DerivativeQuadraticBezierSpline2\"<\/a> 
\"A_Equal\"
<\/a> \"B_Equal\"
<\/a>Den korteste afstand imellem et vilk\u00e5rligt punkt Q og et punkt p\u00e5 B\u00e9zier-kurve P(t) vil v\u00e6re, der hvor skalarproduktet imellem vektoren Q-P(t) og tangenten til punktet P(t) er lig med 0.<\/span><\/p>\n
\u00a0\"DistanceEquation\"
<\/a>. Skalarproduktet giver som bekendt cosinus til vinkelen imellem vektorene. Cosinus giver nul ved 90 grader, s\u00e5 med andre ord finder ligningen den v\u00e6rdi af t hvor vektoren Q-P(t) er ortogonal med tangenten til punktet P(t). Det er netop dette punkt, som vil have den korteste afstand til B\u00e9zier-kurven fra punktet Q.<\/p>\n
N\u00e5r ligningen bliver l\u00f8st for t bliver det til en trediegradsligning:<\/p>\n
\"CubicEquation\"<\/a>\u00a0
<\/a>
Udtrykt i kode, ser overst\u00e5ende s\u00e5dan ud:
<\/span><\/p>\n
vec2 dP0Q = p0-q;\r\nvec2 A = p1-p0;\r\nvec2 B = p0+p2-p1*2.0;\r\nfloat a = dot(B,B);\r\nfloat b = dot(A,B)*3.0;\r\nfloat c = dot(A,A)*2.0+dot(dP0Q, B);\r\nfloat d = dot(dP0Q,A);\r\n<\/pre>\n

<\/a>Der findes forskellige m\u00e5der til at l\u00f8se en trediegradsligning p\u00e5. Vi valgte at bruge Cardano’s metode<\/a>.<\/p>\n
<\/a>Udtrykt i kode bliver Cardano’s metode til f\u00f8lgende:<\/p>\n
#define EPSILON 0.000000001\r\n#define PI 3.14159265358979\r\nint findRoots(float a, float b, float c, float d, out float r[3]) {\r\n\tif (abs(a) > EPSILON) {\r\n\t\tfloat z = 1.0/a;\r\n\t\tfloat d3 = 1.0/3.0;\r\n\t\tfloat d27 = 1.0/27.0;\r\n\t\ta = b*z;\r\n\t\tb = c*z;\r\n\t\tc = d*z;\r\n\t\tfloat p = b-a*a*d3;\r\n\t\tfloat q = a*(2.0*a*a-9.0*b)*d27+c;\r\n\t\tfloat ppp = p*p*p;\r\n\t\tfloat D = q*q+4.0*ppp*d27;\r\n\t\tfloat delta = -a*d3;\r\n\t\tif (D > EPSILON) {\r\n\t\t\tz = sqrt(D);\r\n\t\t\tfloat u = (-q+z)*0.5;\r\n\t\t\tfloat v = (-q-z)*0.5;\r\n\t\t\tu = sign(u)*pow(abs(u),d3);\r\n\t\t\tv = sign(v)*pow(abs(v),d3);\r\n\t\t\tr[0] = u+v+delta;\r\n\t\t\treturn 1;\r\n\t\t}\r\n\t\telse if (D < -EPSILON) {\r\n\t\t\tfloat u = sqrt(-p*d3)*2.0;\r\n\t\t\tfloat v = acos(-sqrt(-27.0/ppp)*q*0.5)*d3;\r\n\t\t\tr[0] = u*cos(v)+delta;\r\n\t\t\tr[1] = u*cos(v+2.0*PI*d3)+delta;\r\n\t\t\tr[2] = u*cos(v+4.0*PI*d3)+delta;\r\n\t\t\treturn 3;\r\n\t\t}\t\t\r\n\t\telse {\r\n\t\t\tq = sign(q)*pow(abs(q)*0.5,d3);\r\n\t\t\tr[0] = 2.0*-q+delta;\r\n\t\t\tr[1] = q+delta;\r\n\t\t\treturn 2;\r\n\t\t}\r\n\t}\r\n\telse {\r\n\t\tif (abs(b) <= EPSILON && abs(c) > EPSILON) {\r\n\t\t\tr[0] = -d/c;\r\n\t\t\treturn 1;\r\n\t\t}\r\n\t\telse {\r\n\t\t\tfloat D = c*c-4.0*b*d;\r\n\t\t\tfloat z = 1.0/(2.0*b);\r\n\t\t\tif (D > EPSILON) {\r\n\t\t\t\tD = sqrt(D);\r\n\t\t\t\tr[0] = (-c-D)*z;\r\n\t\t\t\tr[1] = (-c+D)*z;\r\n\t\t\t\treturn 2;\r\n\t\t\t}\r\n\t\t\telse if (D > -EPSILON) {\r\n\t\t\t\tr[0] = -c*z;\r\n\t\t\t\treturn 1;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\treturn 0;\r\n}\r\n<\/pre>\n
L\u00f8sningen af trediegrads ligningen vil give et sted imellem 0 og 3 l\u00f8sninger. I tilf\u00e6lde af mere end 1 l\u00f8sning, s\u00e5 bruges kun den l\u00f8sning hvor t er indenfor intervallet 0.0 til 1.0.\u00a0N\u00e5r den rigtige v\u00e6rdi af t s\u00e5ledes er fundet, skal denne s\u00e6ttes ind i den oprindelige ligning for en kvadratisk B\u00e9zier-kurve for at beregne punktet K, som vil v\u00e6re punktet p\u00e5 kurven der er t\u00e6ttest p\u00e5 Q.\u00a0Til sidst beregnes selve afstanden g imellem K og Q med Pythagoras.<\/p>\n
\u00a0\"DistanceToPointOnBezierCurve\"<\/a><\/p>\n
Koden til henholdvis at beregne K og sikre at t er i intervallet 0.0 til 1.0 og samt beregne afstanden imellem K og Q ser s\u00e5dan ud:<\/p>\n
float g = distance(q,getPositionOnBezierCurve(clamp(r[0],0.0,1.0),p0,p1,p2));\r\ng = min(g, distance(q,getPositionOnBezierCurve(clamp(r[1],0.0,1.0),p0,p1,p2)));\r\ng = min(g, distance(q,getPositionOnBezierCurve(clamp(r[2],0.0,1.0),p0,p1,p2)));\r\n<\/pre>\n
Afstandsv\u00e6rdien g bruges til at indeksere hele farvespektret og hermed oversat til en enkelt farve for hver pixel p\u00e5 sk\u00e6rmen.\u00a0Koden til at g\u00f8re dette er:<\/p>\n
float white = max(5.0-pow(d,2.0),0.0);\r\nfloat red = max(-0.0007*pow(d-40.0,2.0)+1.0,0.0);\r\nfloat yellow = max(-0.0007*pow(d-75.0,2.0)+1.0,0.0);\r\nfloat green = max(-0.0007*pow(d-110.0,2.0)+1.0,0.0);\r\nfloat cyan = max(-0.0007*pow(d-145.0,2.0)+1.0,0.0);\r\nfloat blue = max(-0.0007*pow(d-180.0,2.0)+1.0,0.0);\r\nvec4 c = vec4(white,white,white,0);\r\nc += vec4(red,0,0,0);\r\nc += vec4(yellow,yellow,0,0);\r\nc += vec4(0,green,0,0);\r\nc += vec4(0,cyan,cyan,0);\r\nc += vec4(0,0,blue,0);\r\n<\/pre>\n
Hvis din browser underst\u00f8tter WebGL kan du se en realtime version herunder<\/a>.
\"BezierDistanceGlowShader\"<\/a><\/p>\n
\n
<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
I Hinnerup Net har vi, mest bare fordi vi kan, udviklet en WebGL shader der k\u00f8rer p\u00e5 computerens GPU (bedre kendt som grafikprocessor). Shaderen beregner konstant afstanden fra et vilk\u00e5rligt punkt til en dynamisk skiftende kvadratisk B\u00e9zier-kurve. Advarsel: Formler f\u00f8lger herefter i stride og voldsomme m\u00e6ngder. Hvis du vil direkte til demoen s\u00e5 hop til […]<\/p>\n","protected":false},"author":13,"featured_media":2040,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10,1,8,4],"tags":[107,105,106],"class_list":["post-1950","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithms","category-misc","category-javascript","category-programming","tag-bezier","tag-shader","tag-webgl"],"_links":{"self":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/posts\/1950","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/comments?post=1950"}],"version-history":[{"count":110,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/posts\/1950\/revisions"}],"predecessor-version":[{"id":2127,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/posts\/1950\/revisions\/2127"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/media\/2040"}],"wp:attachment":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/media?parent=1950"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/categories?post=1950"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/tags?post=1950"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}