Skip to navigation


Drawing triangles: DrawTriangle (Part 8 of 11)

Name: DrawTriangle (Part 8 of 11) [Show more] Type: Subroutine Category: Drawing triangles Summary: Draw the bottom part of a clipped triangle Deep dive: Drawing triangles
Context: See this subroutine in context in the source code References: No direct references to this subroutine in this source file
\ By this point we have the following: \ \ (R0, R1) = (x1, y1) \ \ (R2, R3) = (x2, y2) \ \ (x3, y3) is on the stack \ \ R6 = (y1 - y2) / (x2 - x1) \ = slope of (x1, y1) to (x2, y2) \ \ R7 = (y1 - y3) / (x3 - x1) \ = slope of (x1, y1) to (x3, y3) \ \ R12 = screen address of the start of the \ pixel row containing (x1, y1) \ \ (x1, y1) is the point lowest down the \ screen and (x3, y3) is the highest up the \ screen, with (x2, y2) the point in the \ middle (in terms of y-coordinate) \ \ We now draw the triangle in two parts, \ effectively slicing the triangle in half \ with a horizontal line at y-coordinate y2, \ leaving two triangles to draw: \ \ 1. The triangle from (x1, y1) at the \ bottom up to the horizontal line with \ (x2, y2) at one end \ \ 2. The triangle from the horizontal line \ with (x2, y2) at one end, up to \ (x3, y3) at the top \ \ We start at the bottom of the triangle, at \ (x1, y1), and step upwards by one pixel \ row at a time, drawing a horizontal line \ between the two sides, until we reach the \ level of (x2, y2) \ \ As we step up each pixel row, we calculate \ the x-coordinates of each row we draw by \ adding the slopes in R6 and R7 \ \ We store the x-coordinates of the current \ horizontal line in R4 and R5, so these are \ the registers we update with the slope \ values SUBS R9, R1, R3 \ Set R9 = R1 - R3 \ = y1 - y2 \ \ So this is the vertical distance between \ (x1, y1) and (x2, y2), i.e. the delta \ y-coordinate between the two points \ \ We know this is positive because y1 >= y2, \ so we can use this as a loop counter for \ drawing horizontal lines in the triangle \ between y-coordinates y1 and y2 MOV R4, R0, LSL #16 \ Set R4 = R0 << 16 \ = x1 << 16 \ \ We scale up R4 so that it can contain a \ fractional result - we will treat the \ bottom 16 bits as the fraction, so \ R4 >> 16 gives us the integral part \ \ We use R4 as the x-coordinate of the left \ end of the horizontal line to draw ORR R4, R4, #&8000 \ Set R5 to x1, with the top bit of its MOV R5, R4 \ fractional part set (so that's 0.5) \ \ We use R5 as the x-coordinate of the right \ end of the horizontal line to draw CMP R6, R7 \ If R6 > R7, swap R6 and R7, so we know MOVGT R14, R6 \ that R6 <= R7, i.e. R6 contains the side MOVGT R6, R7 \ with the lesser slope, which will be the MOVGT R7, R14 \ slope along the left edge of the triangle BL trin45 \ Call the subroutine in part 11 to draw the \ bottom part of the triangle, clipping it \ to the screen as we go LDMFD R13!, {R0-R1} \ Fetch the coordinates for the third point \ (x3, y3) from the stack and into (R0, R1) SUBS R9, R3, R1 \ Set R9 = R3 - R1 \ = y2 - y3 \ \ So this is the vertical distance between \ (x2, y2) and (x3, y3), i.e. the delta \ y-coordinate between the two points \ \ We know this is positive because y2 >= y3, \ so we can use this as a loop counter for \ drawing horizontal lines in the triangle \ between y-coordinates y2 and y3 LDMEQIA R13!, {PC} \ If R9 is zero then (x2, y2) and (x3, y3) \ are at the same y-coordinate, so there is \ nothing to draw in the top part of the \ triangle, so return from the subroutine as \ we are done \ We now calculate the slope for the third \ side of the triangle, from (x2, y2) to \ (x3, y3), as follows: \ \ R14 = (y2 - y3) / (x2 - x1) SUBS R14, R0, R2 \ Set R14 = R0 - R2 \ = x3 - x2 RSBMI R14, R0, R2 \ If R14 is negative, set R4 = x2 - x3, so \ we have the following: \ \ R14 = |x3 - x2| CMP R14, #64 \ If either R14 >= 64 or R9 >= 64, then at CMPLO R9, #64 \ least one of these is true: BHS trin33 \ \ R14 = |x3 - x2| >= 64 \ \ R9 = (y2 - y3) >= 64 \ \ so jump to trin33 to calculate the slope \ using the shift-and-subtract algorithm LDR R10, divisionTableAddr \ Set R10 to the address of the division \ tables ADD R10, R10, R14, LSL #8 \ Set R10 to the address of the division \ table containing n / R14, for n = 0 to 63 \ \ This works because each division table \ contains 64 words, or 256 bytes, so the \ address of table n / d is: \ \ divisionTable + d * 256 LDR R12, [R10, R9, LSL #2] \ Set R12 to the R9-th word in the division \ table containing n / R14, so this \ calculates the following: \ \ R12 = R9 / R14 \ \ = (y2 - y3) / |x3 - x2| B trin35 \ Jump to trin35 to skip the following and \ keep going .trin33 \ If we get here then at least one of these \ is true: \ \ R14 = |x3 - x2| >= 64 \ \ R9 = (y2 - y3) >= 64 \ \ We now calculate R12 = R9 / R14 using the \ shift-and-subtract division algorithm MOV R9, R9, LSL #16 \ First we scale R9 up as far as we can, to \ make the result as accurate as possible MOV R12, #0 \ Set R12 = 0 to contain the result MOV R10, #&80000000 \ Set bit 31 of R10 so we can shift it to \ the right in each iteration, using it as a \ counter .trin34 MOVS R14, R14, LSL #1 \ Shift R14 left, moving the top bit into \ the C flag CMPCC R14, R9 \ If we shifted a 0 out of the top of R14, \ test for a possible subtraction SUBCS R14, R14, R9 \ If we shifted a 1 out of the top of R14 or ORRCS R12, R12, R10 \ R14 >= R9, then do the subtraction: \ \ R14 = R14 - R9 \ \ and set the relevant bit in the result \ (i.e. apply the set bit in R10 to the \ result in R12) MOVS R10, R10, LSR #1 \ Shift R10 to the right, moving bit 0 into \ the C flag BCC trin34 \ Loop back until we shift the 1 out of the \ right end of R10 (after 32 shifts) \ So we now have the following result: \ \ R12 = R9 / R14 \ \ = (y2 - y3) / |x3 - x2| .trin35 CMP R0, R2 \ If R0 - R2 < 0 then: RSBMI R12, R12, #0 \ \ x3 - x2 < 0 \ \ so negate R12 to give R12 the correct sign \ for the following calculation: \ \ R12 = (y2 - y3) / (x3 - x2) \ \ So R12 contains the slope of the third \ side of the triangle, from (x2, y2) to \ (x3, y3)