Resources for writing a software renderer?

Search for barycentric coordinates, and start in 2D. If you have the three points of a triangle, and a fourth point somewhere, you can calculate that fourth point's three barycentric coordinates relative to the triangle points with a simple formula (http://en.wikipedia.org/wiki/Barycentric_coordinate_system_(mathematics), scroll down to where it lists lamba 1-3 for the formula). You will get three values, and those will directly tell you if that point is inside the triangle, since then they are all > 0 and < 1.
This can be used to fill the triangle by looping over the smallest rectangle that the triangle fits in, and fill any pixel where the barycentric coordinates pass.
Then when you add texture coordinates or colors, the barycentric coordinates are also interpolation weights for each corner, which gives you texture mapping and shading rather easily. Once you convert it to 3D and need perspective correct interpolation it's a bit more complicated, but you'll find quite a few resources for it if you search for barycentric coordinates and triangle rasterization, and perspective correctness in particular when you reach that stage.

Search for barycentric coordinates, and start in 2D. If you have the three points of a triangle, and a fourth point somewhere, you can calculate that fourth point's barycentric coordinates relative to the triangle points with a simple formula (http://en.wikipedia....m_(mathematics), scroll down to where it lists lamba 1-3 for the formula). You will get three values, and those will directly tell you if that point is inside the triangle, since then they are all > 0 and < 1.
This can be used to fill the triangle by looping over the smallest rectangle that the triangle fits in, and fill any pixel where the barycentric coordinates pass.
Then when you add texture coordinates or colors, the barycentric coordinates are also interpolation weights for each corner, which gives you texture mapping and shading rather easily. Once you convert it to 3D and need perspective correct interpolation it's a bit more complicated, but you'll find quite a few resources for it if you search for barycentric coordinates and triangle rasterization, and perspective correctness in particular when you reach that stage.

EDIT: All my text seems extremly small and strangely colored... not sure how that happened. =) Hopefully it's readable. Setting the font seems to have helped.. but it doesn't really look normal. A reset all fonts button would be awesome. I guess I pasted something with formatting.

I use to love the tutorials at 3D coding Blackhole

There's also the devmaster software rendering tutorials: http://www.devmaster.net/articles.php?catID=9

You don't need to use barycentric coordinates for texture mapping. Just calculate gradients for every interpolated parameter. Gradients are constant across the whole triangle and tell you how much the interpolated parameter changes for each step in x or in y.

Chris Hecker wrote an excellent series on texture mapping for Game Developer in the 90's. Read it if you can find it, otherwise just study the code available here: http://www.gamers.or...ker_texmap.html

The article + code is available on chris hecker's site: http://chrishecker.com/Miscellaneous_Technical_Articles

You don't need to use barycentric coordinates for texture mapping. Just calculate gradients for every interpolated parameter. Gradients are constant across the whole triangle and tell you how much the interpolated parameter changes for each step in x or in y.

Of course you don't need to, but it's easier, often gives better results, and most importantly doesn't require any tweaking or complex edge tracing algorithms and point sorting to get right. In other words, a lot less code for immediately perfect results, at a certain running time cost of course. As far as I know it's also more in line with how graphics cards do it.
Once it's time for optimization, adjacent barycentric coordinates are related enough that you can do a cheap addition to get the i+1:th coordinates from the i:th, similar to a traditional scanline approach.

The linked code and PDFs seem to be 15-20 years old, and deal more with fixed point conversion and efficient loops than getting a good result on screen. On a modern CPU, when the desired result is to simulate OpenGL, floating point barycentric coordinates is a much superior alternative, and will probably run at a reasonable framerate. If you want to write something that's actually playable for a real game at modern resolutions that's a different story, but even then the bottlenecks aren't the same on modern CPUs as they 15 years ago.

How does the [color=#1C2837][size=2]barycentric coordinates approach gel with perpective correction? I'd like to support both ortho and perspective projections, which from what I've been told would traditionally require two triangle rasterisers (one with perpective correction, one without).

You get a different formula that is a bit more complicated when you use perspective correction, but you still get your barycentric coordinates and a perspective correction variable that you need to divide with. (With perspective correction the interpolation must be over 1/Z instead of Z). It should be fairly easy to support both perspective correct and affine interpolation, as just the interpolation part of the code needs to be different.
I don't remember the equations in my head, but it shouldn't be too difficult. Google brings up a couple of Gamedev threads for it. http://www.google.com/search?q=perspective+correct+barycentric+coordinates

I seem to have fallen at the first hurdle- how do I calculate the 4th point for barycentric coords? I'm afraid the notation on the wikipedia article is somewhat beyond me right now.

Are you trying to do perspective correction or simple 2D barycentric coordinates?

The 2D coordinates are the formulas on the page that look like this:
l1 = [ (y2 - y3)(x - x3) + (x3 - x2)(y - y3) ] / [ (y2 - y3)(x1 - x3) + (x3 - x2)(y1 - y3) ]
l2 = ...
l3 = 1 - l1 - l2

Triangle points xi,yi, and point in triangle x,y
Then if you have a color ci for each triangle point the color at x,y is l1 * c1 + l2 * c2 + l3 * c3.
Any float value can be interpolated in the same way, so in the color you would do it for R, G and B, if each channel is a float.


Perspective correction isn't mentioned on Wikipedia I think. Almost all resources on this are from before people used barycentric coordinates, so it's a bit hard to find information.


I think perspective correction can simply be constructed as follows (I only fully implemented it in the old scan-line way so I hope I don't think wrong about this):
Calculate 1 / z at the projected triangle points.
Calculate c / z at the triangle points, and same for any other values to be interpolated.
At each point, interpolate both 1 / z and c / z.
Then do (c / z) / (1 / z) for your interpolated 1/z and c/z values at each pixel to arrive at the perspective correctly interpolated c.

I believe there's a not all too complicated simplification that puts all this into a new set of barycentric coordinates to make it all faster and prettier, but it takes some algebra to arrive at and I don't have it in my head.

This is a self-advert but I started this subject http://www.gamedev.net/topic/594485-my-bachelor-thesis-software-renderer-accelerated-by-cuda-technology/ . I wrote a simple software renderer that supports texture mapping, including mip-mapping. Everything explained in my thesis. Homepage http://maxest.gct-game.net/vainmoinen/

Nice renderer maxest.

Just to clarify the point about the barycentric coordinates, the trick that can be done with the perspective interpolation is to reduce the interpolation to exactly the same as in the simple 2D case.
Perspective correction can be done manually by interpolating all values divided by z instead, together with 1/z. This requires some difference at the per-pixel level interpolation.
If you derive the perspective correct barycentric coordinates however, the only difference will be how you calculate the barycentric coordinates, and you don't need to do the divide by Z for every interpolated value, so the majority of the per-pixel code is exactly the same. It's just a different formula for l1 l2 and l3, and there's no need to divide every value to be interpolated by z at the vertices.
maxest seems to list the equations on page 24 in his paper, if I'm not mistaken?

Yup, I do interpolate attribue/z, 1/z, and compute the interpolated coordinates with a simple division and indeed, pages 24-25 in my thesis explain this.

Are you trying to do perspective correction or simple 2D barycentric coordinates?

The 2D coordinates are the formulas on the page that look like this:
l1 = [ (y2 - y3)(x - x3) + (x3 - x2)(y - y3) ] / [ (y2 - y3)(x1 - x3) + (x3 - x2)(y1 - y3) ]
l2 = ...
l3 = 1 - l1 - l2

Triangle points xi,yi, and point in triangle x,y
Then if you have a color ci for each triangle point the color at x,y is l1 * c1 + l2 * c2 + l3 * c3.
Any float value can be interpolated in the same way, so in the color you would do it for R, G and B, if each channel is a float.

(ignoring perspective correction for now)


So if I'm understanding you, I don't need to explicitly calculate the 4th point, I can go directly from the three triangle verts to a barycentric coord via that equation? (although there seems to be several constants that could be extracted from the inner loop).

Then I'd use the barycentric coords to interpolate my colour/uvs and from that calculate my actual pixel colour?

I'm still slightly worried by looping over the screen-space bounding box for a triangle, that seems like i'll be looping over a lot of pixels and doing the costly barycentric coord calculation only to find that the point is actually outside of the triangle.

[color=#1C2837][size=2]maxest: your project (and slides) look interesting. I'll have to have a look over the rest of it when I've got time. Thanks.

So if I'm understanding you, I don't need to explicitly calculate the 4th point, I can go directly from the three triangle verts to a barycentric coord via that equation? (although there seems to be several constants that could be extracted from the inner loop).

Then I'd use the barycentric coords to interpolate my colour/uvs and from that calculate my actual pixel colour?

I'm still slightly worried by looping over the screen-space bounding box for a triangle, that seems like i'll be looping over a lot of pixels and doing the costly barycentric coord calculation only to find that the point is actually outside of the triangle.

Yes, you can just plug your 3 triangle vertices in pixel space and your current pixel into the equations, and they will directly tell you whether you're inside the triangle and give you interpolation weights.

It can be costly, and there are multiple solutions. One way is to still do a scanline or zigzag sweep over the triangle, but use barycentric coordinates to interpolate and better handling of edge pixels. Another approach is to divide the screen into tiles and check what tiles are touched by the triangle, and then loop over the pixels in those tiles. I believe tiling is part of what graphics hardware does, as it is much better for the cache to draw a small tile at a time than following a whole scanline before jumping back to almost the same texture memory location at the beginning of the next scanline.
The barycentric calculations aren't that expensive once optimized however (much can be precalculated per triangle), and you still skip the whole thing of interpolating values and reading textures when you're outside the triangle. Also, if you write out the equations you can solve for b(x) - b(x-1) if b is the barycentric coordinates, which will leave you a much cheaper calculation in your inner loop.
I would get it working the simple way before starting to optimize it. Once you have your triangle on the screen it's rather easy to cut away one expense at a time.

I would get it working the simple way before starting to optimize it. Once you have your triangle on the screen it's rather easy to cut away one expense at a time.
[/quote]
Exactly. Before I started to develop my pixel processing phase I was contemplating various approaches. I decided to use barycentric coordiantes because they are the neatest way (imho) to get pixels on the screen very quickly. I've liked them so much that I even dropped the idea of tryinganother approaches . But perhaps one day I will go back to my project and try some new things.

Thanks guys, I've got a triangle rasterised now with interpolated vertex colours.

I can certainly see the advantage of the barycentric approach, it makes a lot of the preceding steps much more elegant.