Amiga.org
Operating System Specific Discussions => Amiga OS => Amiga OS -- Development => Topic started by: balrogsoft on February 14, 2007, 01:33:43 PM
-
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.
NOTE: Kalms found the problem on ADA forums, it was necessary a ext.l d2 instruction before divs. Here is the corrected code:
;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
ext.l d2
divs.w d3,d2 ; ((x2 - x1) << 6) / (y2 - y1)
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
ext.l d2
divs.w d3,d2 ; ((x3 - x1) << 6) / (y3 - y1)
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
ext.l d2
divs.w d3,d2 ; ((x3 - x2) << 6) / (y3 - y2)
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 (not corrected). I hope that someone can help me.
http://www.balrogsoftware.com/download/c2p_triangle.zip
-
Fixed before I even got a chance to read it and find out what was wrong :-D
Without the extend operation, your sign will definately get trashed, since all you end up with is the same pattern of bits in the least significant half of your target register, turning a negative 16-bit 2's complement word value like -1 into the positive longword value 65535.
-
Incidentally, there are versions of the DDA line drawing algorithm you can use to determine the start and end points of each horizontal rasterline fragment of your triangle. The fastest of these algorithms don't use any multiplication or division at all.