Skip to navigation

⌂ ∞ ▽ The Sentinel on the BBC Micro

Drawing polygons: TracePolygonEdge (Part 1 of 8)

       Name: TracePolygonEdge (Part 1 of 8)                          [Show more]
       Type: Subroutine
   Category: Drawing polygons
    Summary: Trace a polygon edge, populating xPolygonRight or xPolygonLeft
             with the x-coordinate of the edge for each y-coordinate

    Context: See this subroutine in context in the source code
 References: This subroutine is called as follows:
             * GetPolygonLines (Part 5 of 6) calls TracePolygonEdge
             * GetPolygonLines (Part 6 of 6) calls TracePolygonEdge




 This routine traces a polygon edge.

 For this to work the start point must have a bigger y-coordinate than the end
 point, so the edge is either horizontal or slopes downwards when tracing the
 edge from start to end.



 Arguments:

   xEdgeStart(Hi Lo)    The x-coordinate of the start of the edge to trace

   yEdgeStart(Hi Lo)    The y-coordinate of the start of the edge to trace

   xEdgeEnd(Hi Lo)      The x-coordinate of the end of the edge to trace

   yEdgeEnd(Hi Lo)      The y-coordinate of the start of the edge to trace

   yEdgeDeltaLo         The y-axis delta along the edge

   yPolygonTop          The y-coordinate of the top of the polygon (where higher
                        y-coordinates are up the screen)

   yPolygonBottom       The y-coordinate of the bottom of the polygon (where
                        higher y-coordinates are up the screen)

   xPolygonAddrHi       The high byte of either xPolygonLeft or xPolygonRight
                        to determine which of the resulting tables is written to



 Returns:

   xPolygonLeft         The pixel x-coordinates of the left edges of each pixel
                        line in the polygon (when xPolygonAddrHi is the high
                        byte of xPolygonLeft)

   xPolygonRight        The pixel x-coordinates of the right edges of each pixel
                        line in the polygon (when xPolygonAddrHi is the high
                        byte of xPolygonRight)



.tred1

 JMP tred35             \ Jump to part 6 to trace an edge with two-byte start or
                        \ end point x-coordinates

.tred2

 RTS                    \ Return from the subroutine

.TracePolygonEdge

                        \ We start by updating yPolygonBottom so it covers the
                        \ y-coordinate of the end point of the edge, as the end
                        \ point has the lower y-coordinate

 LDA yEdgeEndHi         \ If yEdgeEnd(Hi Lo) is negative then the end point is
 BMI tred3              \ in the lower half of the screen, so jump to tred3 to
                        \ set yPolygonBottom to the lowest point in the screen
                        \ buffer, i.e. minPitchAngle

 BNE tred2              \ If yEdgeEndHi > 0 then the end point is off the top of
                        \ the screen, so jump to tred2 to return from the
                        \ subroutine

                        \ If we get here then yEdgeEndHi = 0, so now we analyse
                        \ the low byte of yEdgeEnd(Hi Lo)

 LDA yEdgeEndLo         \ If yEdgeEndLo >= maxPitchAngle then the edge ends
 CMP maxPitchAngle      \ beyond the top of the screen buffer, so jump to tred2
 BCS tred2              \ to return from the subroutine

 CMP yPolygonBottom     \ If yEdgeEndLo >= yPolygonBottom then yPolygonBottom
 BCS tred5              \ already covers the y-coordinate, so jump to tred5 to
                        \ move on to the next calculation

                        \ If we get here then yEdgeEndLo < yPolygonBottom, so we
                        \ need to reduce yPolygonBottom to cater for this new
                        \ y-coordinate

 CMP minPitchAngle      \ If yEdgeEndLo >= minPitchAngle, then the y-coordinate
 BCS tred4              \ in yEdgeEndLo is inside the screen buffer, so jump
                        \ to tred4 to store this as the new value of
                        \ yPolygonBottom

                        \ Otherwise yEdgeEndLo is below the bottom of the screen
                        \ buffer, so we need to clip yPolygonBottom to the
                        \ y-coordinate of the bottom of the screen buffer

.tred3

 LDA minPitchAngle      \ Set A = minPitchAngle, so A is clipped to the bottom
                        \ of the screen buffer

.tred4

 STA yPolygonBottom     \ Set yPolygonBottom to the clipped value of yEdgeEndLo
                        \ as this is the lowest y-coordinate we have found yet

.tred5

                        \ Next we update yPolygonTop so it covers the
                        \ y-coordinate of the start point of the edge

 LDA yEdgeStartHi       \ If yEdgeStart(Hi Lo) is negative then the start point
 BMI tred2              \ is off the bottom of the screen, so jump to tred2 to
                        \ return from the subroutine

 BNE tred6              \ If 0 < yEdgeStartHi < 128 then the start point is
                        \ beyond the top of the screen, so jump to tred6 to set
                        \ yPolygonTop to the highest point in the screen buffer,
                        \ i.e. maxPitchAngle

                        \ If we get here then yEdgeStartHi = 0, so now we
                        \ analyse the low byte of yEdgeStart(Hi Lo)

 LDA yEdgeStartLo       \ If yEdgeStartLo < minPitchAngle then the edge starts
 CMP minPitchAngle      \ below the bottom of the screen buffer, so jump to
 BCC tred2              \ tred2 to return from the subroutine

 CMP yPolygonTop        \ If yEdgeStartLo < yPolygonTop then yPolygonTop already
 BCC tred8              \ caters for the y-coordinate, so jump to tred8 to move
                        \ on to the next calculation

                        \ If we get here then yEdgeStartLo >= yPolygonTop, so we
                        \ need to bump up yPolygonTop to cater for this new
                        \ y-coordinate

 CMP maxPitchAngle      \ If yEdgeStartLo < maxPitchAngle, then the y-coordinate
 BCC tred7              \ in yEdgeStartLo is inside the screen buffer, so jump
                        \ to tred7 to store this as the new value of yPolygonTop

                        \ Otherwise yEdgeStartLo is beyond the top of the screen
                        \ buffer, so we need to clip yPolygonTop to the
                        \ y-coordinate of the top of the screen buffer

.tred6

 LDA maxPitchAngle      \ Set A = maxPitchAngle - 1, so A is clipped to the top
 SEC                    \ of the screen buffer
 SBC #1

.tred7

 STA yPolygonTop        \ Set yPolygonTop to the clipped value of yEdgeStartLo
                        \ as this is the highest y-coordinate we have found yet

.tred8

 LDA xEdgeStartHi       \ If either of the start or end points have a non-zero
 ORA xEdgeEndHi         \ high byte in their x-coordinates, jump to part 4 via
 BNE tred1              \ tred1 to trace the polygon edge accordingly

                        \ If we get here then both xEdgeStartHi and xEdgeEndHi
                        \ are zero, so the x-coordinates for the polygon edge
                        \ are all in the range 0 to 255

 LDA xEdgeStartLo       \ Set A = xEdgeStartLo - xEdgeEndLo
 SEC                    \
 SBC xEdgeEndLo         \ So A contains the x-axis delta along the edge we are
                        \ tracing

 BCS tred9              \ If the subtraction didn't underflow, jump to tred9 to
                        \ store the result in xEdgeDelta, as it is already the
                        \ correct sign for the absolute value

 EOR #&FF               \ Negate A using two's complement, so that A is now
 CLC                    \ positive and contains the absolute value of the
 ADC #1                 \ distance in the x-axis between the two points

 STA xEdgeDelta         \ Store the result in xEdgeDelta, so xEdgeDelta is the
                        \ positive absolute of the x-axis delta, as follows:
                        \
                        \   xEdgeDelta = |xEdgeStartLo - xEdgeEndLo|

 LDX #&E8               \ Set A to the opcode for the INX instruction, so we
                        \ trace along the edge by incrementing X

 BNE tred10             \ Jump to tred10 to keep going (this BNE is effectively
                        \ a JMP as X is never zero)

.tred9

 STA xEdgeDelta         \ Set xEdgeDelta to the positive x-axis delta, so this
                        \ is the case:
                        \
                        \   xEdgeDelta = |xEdgeStartLo - xEdgeEndLo|

 LDX #&CA               \ Set A to the opcode for the DEX instruction, so we
                        \ trace along the edge by decrementing X

.tred10

                        \ By this point we have the following:
                        \
                        \   * xEdgeDelta = |xEdgeStartLo - xEdgeEndLo|
                        \
                        \   * X is the correct opcode for tred12 (DEX or INX)

 LDY xEdgeDelta         \ Set the status flags on the comparison of xEdgeDelta
 CPY yEdgeDeltaLo       \ and yEdgeDeltaLo, so we can decide which axis has the
                        \ longer side along the polygon edge (and therefore
                        \ which axis we should step along when tracing the edge)

 LDY yEdgeStartLo       \ Set (A Y) = (xPolygonAddrHi yEdgeStartLo) to use as
 LDA xPolygonAddrHi     \ the storage address in the modification below

 BCS tred18             \ If xEdgeDelta >= yEdgeDeltaLo then the x-axis delta is
                        \ the biggest and the edge has a shallow gradient, so
                        \ jump to part 3 to trace the edge by stepping along the
                        \ x-axis

                        \ Otherwise the edge has a steep gradient, so fall
                        \ through into part 2 to trace the edge by stepping
                        \ along the y-axis