A.D.A. Amiga Demoscene Archive

  Welcome guest! Please register a new account or log in

  

  

  

log in with SceneID

  

Demos Amiga Demoscene Archive Forum / Coding / Triangle fill algorithm, help!!

 

Author Message
BalrogSoft
Member
#1 - Posted: 14 Feb 2007 14:15 - Edited
Reply Quote
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
winden
Member
#2 - Posted: 14 Feb 2007 20:48 - Edited
Reply Quote
Balrog, a simple and nice reference for triangle delta formulas is at kalms' page... texture deltas formulas
Kalms
Member
#3 - Posted: 15 Feb 2007 00:26
Reply Quote
balrogsoft:

DIVS.W d3,d2 will divide d2.l by d3.w and store the result in low/high part of d2 (quotient in low, remainder in high).

Since DIVS expects both operands to be signed, you need to sign-extend the delta value you have in d2.w to fill the entire register. You accomplish that by doing an EXT.L d2 just before the divisison.
BalrogSoft
Member
#4 - Posted: 15 Feb 2007 00:32 - Edited
Reply Quote
Thanks a lot Kalms! it works!

 

  Please register a new account or log in to comment

  

  

  

 

A.D.A. Amiga Demoscene Archive, Version 3.0