vc | Rasterization using Barycentric coordinates

linkRasterization using Barycentric coordinates

Rasterization is the task of transforming a vector graphic image (shapes) and converting it into a raster image (a series of pixels that when displayed together creates the final image). When we want to raterize a triangle this task can be fulfilled using a wonderful mathematical method called barycentric coordinates, which are a way of representing the coordinates inside a triangle with masses on the vertices.

The idea behind the rasterization algorithm using barycentric coordinates is to take each point on the screen and calculate its Barycentric coordinate in order to determine if the point is inside the triangle or if it isn't, if it is inside the triangle we determine which color do we want to apply to the point. In order to calculate the barycentric coordinates we have to think on each point

p = (x,y)

x = \lambda_1x_1 + \lambda_2x_2 + \lambda_3x_3

and

y = \lambda_1y_1 + \lambda_2y_2 + \lambda_3y_3

, where

r_i = (x_i,y_i)

is the ith vertex of the triangle,

\lambda_i

is the ith Barycentric coordinate and

\lambda_1 + \lambda_2 + \lambda_3 = 1

Now if we replace

\lambda_3

with

1 - \lambda_2 - \lambda_1

we have,

\lambda_1(x_1-x_3) + \lambda_2(x_2-x_3) + x_3 - x = 0

\lambda_1(y_1-y_3) + \lambda_2(y_2-y_3) + y_3 - y = 0

which can be represented as a linear transformation

T\cdot\lambda = r - r_3

where

T = \begin{pmatrix} x_1 - x_3 & x_2 - x_3 \\ y_1 - y_3 & y_2 - y_3\end{pmatrix}

, now

T

is an invertible matrix, since

r_1 - r_3

and

r_2 - r_3

are linearly independent. So we can calculate

\lambda_1, \lambda_2

\begin{pmatrix} \lambda_1 \\ \lambda_2 \end{pmatrix} = T^{-1}(r-r_3)

, then we end up with the following formulas.

\lambda_1= \frac{(y_2-y_3)(x-x_3) + (x_3-x_2)(y-y_3)}{(y_2-y_3)(x_1-x_3) + (x_3-x_2)(y_1-y_3)}

\lambda_2= \frac{(y_3-y_1)(x-x_3) + (x_1-x_3)(y-y_3)}{(y_2-y_3)(x_1-x_3) + (x_3-x_2)(y_1-y_3)}

\lambda_3= 1-\lambda_1-\lambda_2

With those barycentric coordinates we can know if a point is inside the triangle if and only if

0 \leq \lambda_1, \lambda_2 \leq 1

. The following sketch shows an implementation using shaders of the rasterization using as colors the three Barycentric coordinates as values for each rgb channel.

barycentric.js1linklet barycentricShader;

2linklet shaderTexture;

3linklet v1 = [0.25, 0.25];

4linklet v2 = [0.5, 0.75];

5linklet v3 = [0.9, 0.5];

6linklet v1y = [0.25, 0.25];

7linklet v2y = [0.5, 0.75];

8linklet v3y = [1.0, 0.5];

9linkfunction preload() {

10link  barycentricShader = loadShader('/vc/docs/sketches/barycentric.vert', '/vc/docs/sketches/barycentric.frag');

11link}

12link

13linkfunction setup() {

14link  createCanvas(512, 512, WEBGL);

15link  shaderTexture = createGraphics(512, 512, WEBGL);

16link  shaderTexture.noStroke();

17link  noStroke();

18link}

19link

20linkfunction matrixMulti(vec, matrix) {

21link  let nVec = [0,0];

22link  for(i = 0; i < 2; i++) {

23link    for (j = 0; j < 2; j++) {

24link      nVec[i] += matrix[i][j]*vec[j]

25link    }

26link  }

27link  return nVec;

28link}

29link

30link

31linkfunction draw() {

32link  let rotationMatrix1 = [[0.9998476951563912391570115588139148516927403105831859396583207145,-0.0174524064372835128194189785163161924722527203071396426836124276],[0.0174524064372835128194189785163161924722527203071396426836124276,0.9998476951563912391570115588139148516927403105831859396583207145]];

33link

34link  v1 = matrixMulti(v1, rotationMatrix1);

35link  v2 = matrixMulti(v2, rotationMatrix1);

36link  v3 = matrixMulti(v3, rotationMatrix1);

37link  v1y[0] -= 0.5;

38link  v2y[0] -= 0.5;

39link  v3y[0] -= 0.5;

40link  v1y[1] -= 0.5;

41link  v2y[1] -= 0.5;

42link  v3y[1] -= 0.5;

43link  v1y = matrixMulti(v1y, rotationMatrix1);

44link  v2y = matrixMulti(v2y, rotationMatrix1);

45link  v3y = matrixMulti(v3y, rotationMatrix1);

46link  v1y[0] += 0.5;

47link  v2y[0] += 0.5;

48link  v3y[0] += 0.5;

49link  v1y[1] += 0.5;

50link  v2y[1] += 0.5;

51link  v3y[1] += 0.5;

52link  shaderTexture.shader(barycentricShader);

53link  barycentricShader.setUniform('A', [min(abs(v1[0]),1.0), min(abs(v1y[1]),1.0)]);

54link  barycentricShader.setUniform('B', [min(abs(v2[0]),1.0), min(abs(v2y[1]),1.0)]);

55link  barycentricShader.setUniform('C', [min(abs(v3[0]),1.0), min(abs(v3y[1]),1.0)]);

56link  texture(shaderTexture);

57link  shaderTexture.rect(0,0,512,512);

58link  rect(-512/2,-512/2.0,512,512)

59link}

60link

61link

barycentric.vert1link#ifdef GL_ES

2linkprecision mediump float;

3link#endif

4link

5linkattribute vec3 aPosition;

6linkattribute vec2 aTexCoord;

7link

8linkvarying vec2 vTexCoord;

9link

10linkvoid main() {

11link  vTexCoord = aTexCoord;

12link

13link  vec4 positionVec4 = vec4(aPosition, 1.0);

14link  positionVec4.xy = positionVec4.xy * 2.0 - 1.0;

15link

16link  gl_Position = positionVec4;

17link}

barycentric.frag1link#ifdef GL_ES

2linkprecision mediump float;

3link#endif

4link

5linkuniform vec2 A;

6linkuniform vec2 B;

7linkuniform vec2 C;

8linkvarying vec2 vTexCoord;

9link

10link

11linkvoid main() {

12link  vec2 uv = vTexCoord;

13link  uv.y = 1.0 - uv.y;

14link  vec2 v0 = C - A;

15link  vec2 v1 = B - A;

16link  vec2 v2 = uv - A;

17link

18link  float dot00 = dot(v0, v0);

19link  float dot01 = dot(v0, v1);

20link  float dot02 = dot(v0, v2);

21link  float dot11 = dot(v1, v1);

22link  float dot12 = dot(v1, v2);

23link

24link  float det = 1.0 / (dot00 * dot11 - dot01 * dot01);

25link  float u = (dot11 * dot02 - dot01 * dot12) * det;

26link  float v = (dot00 * dot12 - dot01 * dot02) * det;

27link

28link  if((u >= 0.0) && (v >= 0.0) && (u + v <= 1.0)) {

29link    gl_FragColor = vec4(u*1.0,v*1.0, (1.0-u-v)*1.0, 1.0);

30link  } else {

31link    gl_FragColor = vec4(0.0,0.0,0.0,1.0);

32link  }

33link}

Software Image & Video Processingchevron_right

Problem Statement and Background Image and Video filters Image Photographic-Mosaic Ascii art

Kernel (Image processing)chevron_right

Kernel (Image processing) Edge detection Sharpen Blur Unsharp Masking Your own filters

Conclusions and References

Hardware Image & Video Processingchevron_right

Problem Statement and Background Image and Video filters Ascii art Photo Mosaic

Kernel (Image processing)chevron_right

Kernel (Image processing) Edge detection Sharpen Blur Unsharp Masking

Conclusions and References

Renderingchevron_right

Problem Statement and Background Radiosity Algorithm Rasterization using Barycentric coordinates Conclusions and References

Computer Graphics HCI