Getting scan lines of arbitrary 2d triangle

3.1k views Asked by At

How would one go about retrieving scan lines for all the lines in a 2D triangle?

I'm attempting to implement the most basic feature of a 2D software renderer, that of texture mapping triangles. I've done this more times than i can count using OpenGL, but i find myself limping when trying to do it myself.

I see a number of articles saying that in order to fill a triangle (whose three vertices each have texture coordinates clamped to [0, 1]), i need to linearly interpolate between the three points. What? I thought interpolation was between two n-dimensional values.

NOTE; This is not for 3D, it's strictly 2D, all the triangles are arbitrary (not axis-aligned in any way). I just need to fill the screen with their textures the way OpenGL would. I cannot use OpenGL as a solution.

2

There are 2 answers

2
Emond On BEST ANSWER

An excellent answer and description can be found here: http://sol.gfxile.net/tri/index.html

You can use the Bresenham algorithm to draw/find the sides.

0
AudioBubble On

One way to handle it is to interpolate in two steps if you use scanline algorithm. First you interpolate the value on the edges of the triangle and when you start drawing the scanline you interpolate between the start and end value of that scanline.

Since you are working in 2d you can also use a matrix transformation to obtain the screen coordinate to texture coordinate. Yesterday I answered a similar question here. The technique is called change of basis in mathematics.