Triangle drawing

I don't know much about this, but you can try looking at some general references on triangle rasterization (link), just to see if there's a problem with your logic.

At a glance I would agree with your assumption that the bug is likely in your ordering, although that would only be an assumption thus a good point to at least initially focus review. You shouldn't rule out widening the search.

It's interesting to note the difference between the two diagrams you post...

The leftmost vertex appears the same in both.
The middle vertex appears to have the same X that it always did, with Y either correct (as you increase Y), or being set the the same Y as the first vert.
The right most verts X is what it should be, the Y is messed up.

Therefore, the Y's appear to be getting messed up and this could be because of your sorting algorithm.

Have you single stepped through this function at the points where the Y value changed and causes the error? It's this sort of thing you may need to undertake in order to provide more data to help solve the problem.

I might ask, why are you sorting the vertices anyway? Most triangle rasterizations functions merely find the top most and work from there, simple noting from the other two verts which is the left most and which is the right most, which will lead to simpler code in your example. Many rasterization functions also assume a certain clockwise or anti-clockwise winding order in the triangle vertex data for reasons of keeping code simple and understanding which way a triangle might be facing (in absence of a normal).

Incidentally, a little more info (more is coming forward from my time long ago in software rendering).

One of the reasons why people would largely ignore the idea of figuring out the order of the vertices was really to avoid the trap you fell into, which basically leads you to author more complex code than you may need.

Triangle rasterization is really one of those topics where if you keep is simple, when errors occur you'll have code that is much easier to debug.

A good, old method of software triangle rasterization was not only to start from the topmost vert (as you have done) but also split the triangle into two triangles (if necessary*).

The reason for this was one of code simplicity and basically boiled down to code when you drew from one top pixel, spanning to a line part way through the triangle (lets call it halfway for arguments sake, although it isn't actually halfway) and then from that point back down to the single lowest vertex.

Kind of like this triangle (excuse poor ascii art):

1
**
*-*
*--*
2---*
.**--*
...**-*
.....**3

Would be drawn in two halves like this:

a)
1
**
*-*
*--*
2***X

b)

2***Y
.**--*
...**-*
.....**3

The whole point would be to have two triangle rasterizers, one of which draws from a top most point to two lower points (halfway through the trangle, sharing the same Y). One which draws from two topmost points (starting halfway through the triangle, same Y) to a lower point. This is typically how triangle rasterization would be done in the past in a simple, optimized manner.

Now I wouldn't get hung up about the optimized/high performance part if I were you (it seems like this would not be your goal right now, although ask by all means). The reason I explain all this is because clearly you already have the code for drawing the top half of the triangle, and extending you code to draw the bottom half isn't going to be too difficult given what you have done so far.

There are a couple of very easy caveats...

I put a * above with the 'if necessary' comment because sometimes it is only necessary to draw one of these two halves. It really depends on whether or the relevant vertices are on the same line. Your triangle in your first diagram is of this type and it's a very simple test to see if the other two verts share the same Y. If they do, only use the draw top half code to draw the whole triangle.

Another test is important...if there are two top most verts of a triangle, then you're using only the rasterization that draws the lower part of the triangle.

You could argue that you're only drawing a line for the cases where all three verts Y values are the same, but most engines would not bother drawing this anyway - they'd have already considered that the triangle they are drawing isn't facing the camera.

While this might seem complicated, it really isn't, especially given that you a) already have half the rasterization code b) the rest of the rasterization code is pretty much the flip/reverse of what you have now and c) it should allow you the opportunity to throw away that vertex ordering/winding code, which is more complex than what you need. I've never seen a game engine have this and again it's really based around basing development on realistic assumptions and keeping things simple.

Which (incidentally) if you are worried about mathematics not being your thing, the same logic applies. There are many circumstances where you can factor complex math out merely by keeping things simple.

[Edited by - freakchild on June 7, 2010 5:23:33 PM]

Thank you so much for your reply. I had been thinking about it and came to a similar idea of splitting the triangle into two and handling different cases separately but I didn't know if it would be the "right" way.

Right, I'll give it a go now!

I've gotten it working completely now! It can draw any type of triangle I throw at it =D (Albeit slowly!). Thanks again for your help!

Just checked in - very glad this worked out for you.