Triangle Drawing: Calculating the Deltas - Part 1
Hello there. I just thought I'd write down some thoughts about calculating the deltas for a gouraud shaded triangle drawer. If you've read Darkblade's excellent triangle tute, you'll know what I'm talking about. if you haven't, go and read it now. I hope this little text will compliment his text well, as a little "post script" to describe a few more neat speedups. Note that there are about 30 zillion more, but anyway...
What I'm going to get to is an efficient way of calculating the increments to the shade values that you need to actually fill the gouraud shaded triangle. with a little bit of thought, the stuff I describe here can be extended to calculating texture increments or truecolour gouraud shaded triangles too, because as everyone should (?) know, each variable that you're interpolating across the triangle (whether it be gouraud shade value, red/green/blue value, or texture coordinates) it's all exactly the same maths (and code).
Before I get down to it, let me just say something about back facing. In most 3d engines (which is what you want these triangles for, isn't it?) people say that triangles are one sided. what does that mean? well make a triangle out of a bit of ripped up paper, and number its corners 1,2,3 in clockwise order. Look at it from the front (labeled) side. The labels are still in clockwise order (doh). now flip the triangle over, so you can see the reverse side. If you could still read the labels, you'd notice they were now in anti-clockwise order. clue number 1. hmm. Now look at a solid object (your table, your girlfriend, whatever....) and imagine it being made of triangles. can you see any of the back sides of those triangles? don't think so (oh please let's not make any sick jokes at this point). that was clue 2 by the way. Put'em together and you get this thought: we don't need to draw any of the triangles which are facing away from us. Nifty. Throw'em right away. But how do we know which is which? Easy: Look to see which ones still have their corners in clockwise order, after you've rotated them into screen coordinates.
Nifty, eh? Well, if you haven't heard of it before, it is.
But why am I talking about this shit? Bear with me. The usual way of working out which way round a triangle is, is using the "cross product". Here it is in sort of weirdo pseudo-code. Imagine you have 3 arrays: X[3], Y[3] and C[3]. X and Y store the coordinates of the 3 corners, and c holds the 3 shades to be gouraud shaded across the triangle. we won't use C for now, but it's a taste of what's to come.
Now do this:
let ax = x[0] - x[1]
let bx = x[2] - x[1]
let ay = y[0] - y[1]
let by = y[2] - y[1]
(They're just to make the next bit easy to write down. and you need them elsewhere later, so keep then around.)
let area = ax * by - ay * bx
Now if this area variable is positive, then the triangle is facing you. If it's 0 or negative, the triangle is facing edge on (0) or away from you (negative) so you can damn well forget about drawing it. (Or maybe I got it my sums the wrong way round, in which case swap "positive" and "negative" in the above.)
Also, area is pretty much the area of the triangle on the screen. but that's not very useful.
But WAIT! This is where we get to deltas. The traditional method is to calculate the longest scanline in the triangle and then interpolate the shade down other edges and lots of other complex stuff. But remember, at this stage in my discussion, we haven't even got round to scanning the edges. We've just worked out the area. Now, this area is useful. First thing to do with it is work out its reciprocal, which you do like this:
let rarea = 1 / area
we're talking floating point here. and here's the first cool thing: that's the ONLY divide you're ever going to have to do, to calculate ALL the deltas you'll ever need. Nifty? You're telling me. There's more. (By the way there's a way of removing all divides in the edge scanning code too, so that REALLY is the only divide in the entire triangle routine, but that's another article.)
GIVE ME THE DELTAS! I hear you say. Righto.
let ac = c[0]-c[1]
let bc = c[2]-c[1]
(Again, those two are just to make the next bit easier to write. remember c[] is the shade values you're compute the increments from.)
let delta_c_x = rarea * ( ay * bc - ac * by )
let delta_c_y = rarea * ( ac * bx - ax * bc )
(Once again, I might have got those minus signs back to front. Sorry. Just suck it and see - what can I say? I'm doing this off the top of my head, ok? And it's pretty messy up there...)
There's a very beautiful mathematical derivation of all this, but I'll spare y'all.
Anyway. THAT'S IT. Count the multiplies. Not many. Count the divides. 1. Not bad? I should just explain about the two deltas. delta_c_x is the one you add on, each pixel in your inner loop. I think of it as moving one pixel to the right - and each time you do that, you add on delta_c_x. It's exactly the same value that comes out right at the end of the traditional method that Darkblade explained, using longest scanlines and wotnot. it's just this one tends to fall out quicker.
Now the delta_c_y. This one is a bit odd. It's the increment when you go VERTICALLY down a pixel. "Normally", people use an increment along the left edge of the triangle - that is, going down and across a bit, depending on the angle of the left edge. That's fine - but that's not the way I do it, mainly because this method of calculating the increments doesn't give you that - it gives you the increment for going STRAIGHT down. So, I hold a "current shade value" just as before, which holds the colour at the left of the current scanline. When I move to the next scanline, rather than just adding a simple increment, I have to add delta_c_y and ALSO a multiple of delta_c_x, depending on how many horizontal pixels I move to follow the left edge. Does that sound like it sucks? Maybe. But it's quite useful when your left edge hits the edge of the screen - the "normal" system goes a bit mental at that stage. This one copes just fine - you just stop adding on any delta_c_x, because you aren't moving to the side any more.
Well, if that last paragraph passed you by, you'll have to read it through again until you get it. it's not complicated, it's just hard to explain, and I'm no teacher.
Right, I'm bored of typing. hope that helps y'all. It certainly gives nice fast triangles if you put it into practice....
Until next time.
http://ban.joh.cam.ac.uk/~alex
For all my demos, the source code for bleam, and graphic design stuff.....