# Software polygon rasterization with transparency using raw image data

I have an image with shapes in it (squares and triangles with different colors scattered in the image) and I have an algorithm that matches the image and extracts the geometry vertices from image raw data (unsigned char*) and the extracted vertices are correct and I have checked theme there is no doubt about theme.

Now that I have got the vertices of the squares and triangles from the raw image data. How can I fill the pixels that lies inside the vertices with transparency so they become deleted shapes?

PS: the vertices that i have got are just an array of points and each point has x and y property in it and the raw image data is rgba8888 (32 bit).

• What do you mean by "so they become deleted shapes"? Nov 23 '15 at 21:10

Ok, here is the solution.

First, you need to ensure that your vertices are winded in a correct direction. For this explanation I'm going to use counter-clockwise order. Like this:

    1

2       3


And our coordinate system is:

Y
^
|
|
0------> X


Let's call our 3 points a, b and c.

Let's create some vectors: b - a = A, c - b = B, a - c = C.
Now we need to rotate them 90 degrees clockwise: [A.y,-A.x] = AA, [B.y,-B.x] = BB, [C.y,-C.x] = CC.

Now you need to understand what dot product is: dot(a, b) = a.x*b.x + a.y&b.y. It has useful properties. For example, dot product of a and b is equal to length of a * length of b * cos of angle between a and b.

And now we can test if some point is in this triangle: The point is inside if dot(AA, point - a) < 0 and dot(BB, point - b) < 0 and dot(CC, point - c) < 0.

And now we take a minimal square that contains all 3 points. Like this:

+--a----+
|       |
|       c
|       |
b-------+


And now you just test every point in this square.

You can use same method for quads, you just need to add 4th point.