Hi, i'm trying to implement a triangle fill algorithm, but it seem that i have some problems calculating deltas for the interpolation. I tried the algorithm on a pc with Purebasic and works perfectly. After a lot of tests, i found the problem on delta values, because with hardcode values for a triangle the algorithm works. I think that the problem is found on the sign of deltas, i think that i lose sign bit. But with some tests i found that with positive deltas some triangles fails also.
This is the code in PureBasic, is basic code, i think that is enough clear to understand it:
Procedure filltriangle(x1,y1,x2,y2,x3,y3,color)
Define.w x, y, x0,y0, dx1, dx2, dx3, scanleftx, scanrightx, leftadd, rightadd, beginx, endx
Define.b bucle
; Sort algorithm using swap method, two iterations is enough to sort an array with 3 items
For bucle = 0 To 1
If y1>y2 : x0=x2 : x2=x1 : x1=x0 : y0=y2 : y2=y1 : y1=y0 : EndIf
If y2>y3 : x0=x3 : x3=x2: x2=x0 : y0=y3 : y3=y2 : y2=y0 : EndIf
Next bucle
If y2 <> y1
dx1=(((x2-x1)<<#FP)/(y2-y1))&$ffff
EndIf
If y3 <> y1
dx2=(((x3-x1)<<#FP)/(y3-y1))&$ffff
EndIf
If y3<> y2
dx3=(((x3-x2)<<#FP)/(y3-y2))&$ffff
EndIf
scanleftx = x1 << #FP
scanrightx = x1 << #FP
If dx1 < dx2
leftadd=dx1
rightadd=dx2
Else
leftadd=dx2
rightadd=dx1
EndIf
For y = y1 To y2 - 1
beginx = scanleftx >> #FP
endx = scanrightx >> #FP
LineXY(beginx, y, endx, y, color)
scanleftx + leftadd
scanrightx + rightadd
Next y
If dx2 > dx3
leftadd = dx2
rightadd = dx3
Else
leftadd = dx3
rightadd = dx2
EndIf
For y = y2 To y3
beginx = scanleftx >> #FP
endx = scanrightx >> #FP
LineXY(beginx, y, endx, y, color)
scanleftx + leftadd
scanrightx + rightadd
Next y
EndProcedure
And this is the asm code (Change and.l #$7fff,d2 for and.l #$ffff,d2, i made a test, but the original value should be $ffff):
;a0 - chunky buffer
;a1 - triangle points
FP EQU 6
DrawTriangle:
movem.l d0-d5/a0-a2,-(sp)
lea deltaX,a2
moveq.w #1,d3
.sort ; Sort triangle points before draw it
move.w 2(a1),d0
move.w 6(a1),d1
cmp.w d0,d1
bpl.b .noSwap1
move.l 0(a1),d0
move.l 4(a1),d1
move.l d0,4(a1)
move.l d1,0(a1)
.noSwap1
move.w 6(a1),d0
move.w 10(a1),d1
cmp.w d0,d1
bpl.b .noSwap2
move.l 4(a1),d0
move.l 8(a1),d1
move.l d0,8(a1)
move.l d1,4(a1)
.noSwap2
dbf d3,.sort
move.w #0,0(a2) ; Clear dx1
move.w 2(a1),d0 ; Compare y1 with y2, if equal jump to avoid a 0 div
move.w 6(a1),d1
cmp.w d0,d1
beq.b .div0_avoid1
move.w 4(a1),d2
move.w 0(a1),d3
sub.w d3,d2 ; (x2 - x1) << 6
lsl.w #FP,d2
move.w d1,d3 ; (y2 - y1)
sub.w d0,d3
divs.w d3,d2 ; ((x2 - x1) << 6) / (y2 - y1)
and.l #$7fff,d2
move.w d2,0(a2) ; Store new dx1
.div0_avoid1
move.w #0,2(a2) ; Clear dx2
move.w 2(a1),d0 ; Compare y1 with y3, if equal jump to avoid a 0 div
move.w 10(a1),d1
cmp.w d0,d1
beq.b .div0_avoid2
move.w 8(a1),d2
move.w 0(a1),d3
sub.w d3,d2 ; (x3 - x1) << 6
lsl.w #FP,d2
move.w d1,d3 ; (y3 - y1)
sub.w d0,d3
divs.w d3,d2 ; ((x3 - x1) << 6) / (y3 - y1)
and.l #$7fff,d2
move.w d2,2(a2) ; Store new dx2
.div0_avoid2
move.w #0,4(a2) ; Clear dx3
move.w 6(a1),d0 ; Compare y2 with y3, if equal jump to avoid a 0 div
move.w 10(a1),d1
cmp.w d0,d1
beq.b .div0_avoid3
move.w 8(a1),d2
move.w 4(a1),d3
sub.w d3,d2 ; (x3 - x2) << 6
lsl.w #FP,d2
move.w d1,d3 ; (y3 - y2)
sub.w d0,d3
divs.w d3,d2 ; ((x3 - x2) << 6) / (y3 - y2)
and.l #$7fff,d2
move.w d2,4(a2) ; Store new dx3
.div0_avoid3
move.w 0(a1),d0 ; scanleft = x1 << 6
lsl.w #FP,d0
move.w d0,d1 ; scanright = x1 << 6
move.w 0(a2),d2 ; leftadd = dx1
move.w 2(a2),d3 ; rightadd = dx2
cmp.w d2,d3 ; if dx1 < dx2 then jump .dx1dx2
bpl.b .dx1dx2
move.w d3,d2 ; leftadd = dx2
move.w 0(a2),d3 ; rightadd = dx1
.dx1dx2
move.w 2(a1),d4
muls.w #160,d4
add.l d4,a0
move.l a0,a2 ; a2 = Start line y pointer
move.w 6(a1),d4
move.w 2(a1),d5
sub.w d5,d4
.top
clr.l d5
move.w d0,d5
lsr.w #FP,d5
add.l d5,a2
clr.l d5
move.w d1,d5
sub.w d0,d5
lsr.w #FP,d5
.linetop
move.b #29,(a2)+
dbf d5,.linetop
add.w #72,d0 ; scanleft + 72 (hardcode)
; add.w d2,d0 ; scanleft + leftadd
add.w #160,d1 ; scanright + 160 (hardcode)
; add.w d3,d1 ; scanright + rightadd
add.l #160,a0
move.l a0,a2
dbf d4,.top
lea deltaX,a2
move.w 2(a2),d2 ; leftadd = dx2
move.w 4(a2),d3 ; rightadd = dx3
cmp.w d2,d3 ; if dx2 < dx3 then jump .dx2dx3
bpl.b .dx2dx3
move.w d3,d2 ; leftadd = dx3
move.w 2(a2),d3 ; rightadd = dx2
.dx2dx3
move.l a0,a2 ; a2 = Start line y pointer
move.w 10(a1),d4
move.w 6(a1),d5
sub.w d5,d4
.bottom
move.w d0,d5
lsr.w #FP,d5
add.l d5,a2
move.w d1,d5
sub.w d0,d5
lsr.w #FP,d5
.linebottom
move.b #29,(a2)+
dbf d5,.linebottom
add.w #72,d0 ; scanleft + 72 (hardcode)
; add.w d2,d0 ; scanleft + leftadd
add.w #-53,d1 ; scanright + 53 (hardcode)
; add.w d3,d1 ; scanright + rightadd
add.l #160,a0
move.l a0,a2
dbf d4,.bottom
.exitdr
movem.l (sp)+,d0-d5/a0-a2
rts
CNOP 0,4
deltaX: ds.w 3
And here is a pack with startup, c2p, rotozoom, and triangle fill to test directly. I hope that someone can help me.
http://www.balrogsoftware.com/download/c2p_triangl e.zip 