следующий фpагмент (2)===================================================
* Area : PASCAL (PASCAL)
* From : Herman Dullink, 2:282/517 (в воскресенье 25 июня 1995 09:00)
* To : Sean Palmer
* Subj : Re: Linedraw?
===================================================
BV>You just explained the fixed point principal. How about making a line r
BV>with it?
SP> Fixed-point lines don't *necessarily* end up ending on the target
SP> pixel.
Depends on how much bits you use for the fraction, I use 16 bit, and even
in 1600x1200 it's using the very same pixels as Bresenham's. The only
difference is that my 16-bit fixed point version is about 10% faster
than your 32-bit version of Bresenham's :-)
Fixed point line drawing routine draws the line 'correct' when the error/
fault multiplied by the number of pixels needed for the line isn't larger
than 1 (or 0.5, not sure). This means I have to take 1 (or 2) bits more for
the fraction than the number of bits needed for the coordinates. Well,
this is (allmost) as much as Bresenham's needs for d, incrX and incrXY
variables.
To be on the save side (2 bits more), I still can draw lines correct
in 16384x16384 modes using 16 bits for the fraction.
My first version was about 80% faster than your 16-bit Bresenham's.
I was very suprised your 32-bit version was 15% faster than mine, as
I believed Bresenham could never be faster than the incremental
line scan-conversion algoritm using fixed point.
Unfolding really kicks butt. Now my second version (still 16-bit) is
again 10% faster than yours (so it's your turn now :-).
As this code is optimized for my 486, can anybody give me some info
about how this code performs on other CPU's (286,386,P5). It's
written in Turbo Pascal 6.0:
[Line.pas]
const N = 100000;
procedure call(x1,y1,x2,y2:word; c:byte); begin end;
procedure line(x1,y1,x2,y2:word; c:byte); assembler;
asm
push ds
{ Video Segment }
mov ax,0A000h; mov ds,ax; mov es,ax
{ Get Vars }
mov al,c; mov dx,y2; mov cx,x2; mov bx,y1; mov di,x1; mov si,320
{ Calc dX }
sub cx,di; jz @vertical; ja @l1
add di,cx; neg cx; xchg dx,bx
@l1:
{ Calc dY }
sub dx,bx; jz @horizontal; ja @l2
neg dx; neg si
@l2:
{ Calc address }
xchg bh,bl; add di,bx; shr bx,2; add di,bx
{ Determine slope }
cmp cx,dx; je @diagonal; mov ax,0; mov bx,8000h; jb @high_slope
@low_slope: { |dX| > |dY| > 0 }
div cx; xchg dx,ax; mov al,c
@ls1:
mov ds:[di],al; add bx,dx; jc @ls3
@ls2:
inc di; dec cx; jz @last
mov ds:[di],al; add bx,dx; jnc @ls2
@ls3:
adc di,si; dec cx; jnz @ls1; jmp @last
@high_slope: { 0 < |dX| < |dY| }
xchg cx,dx; div cx; xchg dx,ax; inc cx; mov al,c
shr cx,1; jnc @hs2
@hs1:
mov ds:[di],al; add bx,dx; adc di,si
@hs2:
mov ds:[di],al; add bx,dx; adc di,si
dec cx; jnz @hs1; jmp @last
@vertical: { |dX| = 0 }
sub dx,bx; jnb @v1
add bx,dx; neg dx
@v1:
xchg bh,bl; add di,bx; shr bx,2; add di,bx; inc dx
@v2:
mov ds:[di],al; add di,si; dec dx; jnz @v2; jmp @end
@horizontal: { |dY| = 0 }
inc cx; xchg bh,bl; add di,bx; shr bx,2; add di,bx
test di,1; jz @h1
stosb; dec cx
@h1:
mov ah,al; shr cx,1; rep stosw; jnc @end; jmp @last
@diagonal: { |dX| = |dY| }
inc si
@d1:
mov ds:[di],al; add di,si; dec cx; jnz @d1
@last:
mov ds:[di],al
@end:
pop ds
end;
var time:longint absolute $0:$46c; cntr, t, t1 : longint;
begin
write('Timing procedure call');
randseed := 0; cntr := N; t1 := time; while t1 = time do;
repeat
call(random(320),random(200),random(320),random(200),random(256));
dec(cntr)
until cntr = 0;
t1 := time - t1;
asm mov ax,13h; int 10h end;
randseed:=0; cntr := N; t := time; while t = time do;
repeat
line(random(320),random(200),random(320),random(200),random(256));
dec(cntr);
until cntr = 0;
t := time - t - t1;
asm mov ax,03h; int 10h end;
write(N,' lines in ',(t/18.2):0:2,' sec. -> ');
write('lines per second: ',(N*18.2/t):0:0);
writeln(' -> perf. index : ',sqrt(sqrt(320*200)*N*18.2/t):0:1)
end.
следующий фpагмент (3)|пpедыдущий фpагмент (1)
*******************************************************************************
*LINE from d0,d1 (x1,y1) to d2,d3 (x2,y2) without blitter. (Raped Bresenham :-)
*Uses only 68000 instructions (almost no gain by using higher CPU intructions)
*Can be converted to work in chunky-mode because it 'walks' through adresses.
*I've included some psuedo-C comments to clearify the sourcecode.
*Made by Patrick van Logchem (v912152@si.hhs.nl) on 7 June 1993.
*******************************************************************************
cnop 0,8
CPUline:
lea screen,a1 ; offset='start adress of bitplane'
move.w #Width>>3,d4
muls d1,d4
add.w d4,a1 ; 'add Y offset to screen-pointer'
move.w d0,d4
lsr.w #3,d4
add.w d4,a1 ; 'add X offset to screen-pointer'
moveq #1,d4
move.w d2,d6
sub.w d0,d6 ; ax = abs(x2 - x1)
bge.s noABSx
neg.w d6
neg.w d4 ; sx = sign(x2 - x1) /* X-step */
noABSx:
move.w #Width>>3,d5
move.w d3,d7
sub.w d1,d7 ; ay = abs(y2 - y1)
bge.s noABSy
neg.w d7
neg.w d5 ; sy = (Width/8)*sign(y2 - y1) /* Y-step */
noABSy:
cmp.w d6,d7
bgt.w ydomi ; if(ax > ay)
;-----------------------------------------
; X dominant part:
xdomi:
move.w d6,d1 ; d1 = counter /* length of line = ax */
move.w d6,d2
asr.w #1,d2 ; D = ax>>1 /* 'D' is digital error */
not.b d0 ; X = bitnr(X)
and.w #7,d0 ; X &= 7
bchg.b d0,(a1) ; 'change bit on [offset]'
dbf d1,xloop
rts
nop
nop
nop ; use nop's to make sure xloop is on a 8 byte boundary (for speed)
xloop:
sub.w d7,d2 ; D -= ay
bgt.s x_no_e ; if(D < 0) {
add.w d6,d2 ; D += ax
add.w d5,a1 ; offset += sy }
x_no_e:
sub.w d4,d0 ; X -= sx /* next bitnr */
btst #3,d0 ; /* bit 3 clear = X between 0 and 7 ? */
beq.s xjump ; if(X & 8) {
and.w #7,d0 ; X &= 7
add.w d4,a1 ; offset += sx }
xjump:
bchg.b d0,(a1) ; 'change bit on [offset]'
dbf d1,xloop
rts
;-----------------------------------------
; Y dominant part:
ydomi:
move.w d7,d1 ; d1 = counter /* length of line = ay */
move.w d7,d2
asr.w #1,d2 ; D = ay>>1 /* 'D' is digital error */
not.b d0 ; X = bitnr(X)
and.w #7,d0 ; X &= 7
bchg.b d0,(a1) ; 'change bit on [offset]'
dbf d1,yloop
rts
nop
nop
nop
yloop:
sub.w d6,d2 ; D -= ax
bgt.s y_no_e ; if(D < 0) {
add.w d7,d2 ; D += ay
sub.w d4,d0 ; X -= sx /* next bitnr */
btst #3,d0 ; /* bit 3 clear = X between 0 and 7 ? */
beq.s y_no_e ; if(X & 8) {
and.w #7,d0 ; X &= 7
add.w d4,a1 ; offset += sx }
; }
y_no_e:
bchg.b d0,(a1) ; 'change bit on [offset]'
dbf d1,yloop
rts
следующий фpагмент (4)|пpедыдущий фpагмент (2)
- [91] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS -
Msg : 30 of 31
From : Minaev Vasil 2:5030/228 30 Nov 94 22:41:00
To : Cyrill Malevanov
Subj : Re: Быстрая линия need.
--------------------------------------------------------------------------------
.TID: FastEcho 1.41/g 228
Hi Cyrill and other!!
Hе знаю поможет ли это тебе но кидаю...
(кстати если кому это интересно поделитесь соображениями)
Для начала приведу простенький алгоритм Брезенхэма
Procedure Line(SX,SY,EX,EY:Integer);
Var t,dist,Xerr,Yerr,DX,DY,INCX,INCY:Integer;
Begin
Xerr:=0; Yerr:=0;
DX:=EX-SX; DY:=EY-SY;
INCX:=1; INCY:=1;
if DX=0 then INCX:=0;
if DX<0 then INCX:=-1;
if DY=0 then INCY:=0;
if DY<0 then INCY:=-1;
DX:=ABS(DX); DY:=ABS(DY);
if DX>DY Then Dist:=DX;
else Dist:=DY;
Xerr:=DX; Yerr:=DY;
for t:=0 to dist do
begin
PutPixel(Sx,Sy,Color);
Xerr:=Xerr+DX; Yerr:=Yerr+DY;
if Xerr>Dist then
begin
Xerr:=Xerr-dist;
Sx:=Sx+INCX; ----¬
end; ¦
if Yerr>Dist then +-----------------------------------------------¬
begin ¦ ¦
Yerr:=Yerr-dist; ¦ ¦
Sy:=Sy+INCY; ----- ¦
end; ¦
end; ¦
End; ¦
¦
Hиже приведу вариант на асме. Этот вариант вырезан из драйвера графики ¦
для режима 640х350х16 (легко переделать в 640х480х16 и другие) ¦
от собственной графической библиотеки. По этой причине все переменные ¦
адресуются от CS: (непринципиально) Суть быстрой реализации в том ¦
что на каждой итерации цикла вывода необходимо получить не следующую ¦
позицию (как в примере на паскале) а расчитать следующее смещение --------
в видео буфере и маску записи. По этому в начале рассчитываем смещение
первой точки и маску записи а дальше сдвигаем маску и изменяем смещение
Совершенно необходимо побеспокоиться чтобы переменные были выровнены на
четные адреса ( сильно увеличивает скорось). а асме это делается
директивой EVEN в сегменте данных( в прмере он не показан).
Пример несколько погрызан из за ограниченности обьема письма,
опущен код работающий в режиме отсечения по краям области вывода,
со стилями линий и т.д.
Hа 30 процентов быстрее BGI borland!!!!!
; построение линии **************************************************
LINE: ; целочисленный алгоритм Брезенхэма
; void Line(u_int X1,u_int Y1,u_int X2,u_int Y2)
PUSH BP ---¬
MOV BP,SP ¦
¦
MOV AX,[BP+6] ;X1 +-----> C последовательность
MOV CX,[BP+10] ;X2 ¦ вызова
MOV DX,[BP+8] ;Y1 ¦ Для Pascal надо
MOV BX,[BP+12] ;Y2 ¦ переписать.
----
CMP AX,CX ;if x1>x2
JNG @L_1
XCHG AX,CX ;установить положительное
XCHG DX,BX ;направление по оси X
;Это позволит считать что X только увеличивается
;и избавиться от лишних инструкций!!!!
@L_2: MOV CS:S_X,AX ;сохранить координаты
MOV CS:E_X,CX
MOV CS:S_Y,DX
MOV CS:E_Y,BX
; настройка контроллера
; используем режим записи 0
MOV AX,CS:WADDR ;стартовый адрес видеостраницы
MOV ES,AX
MOV DX,3CEh; ;порт контроллера
MOV AL,0 ;регистр установки /сброса
MOV AH,CS:FCOLOR ;цвет вывода
OUT DX,AX
MOV AX,0F01h ;регистр разрешения установки /сброса
;0F-игнорировать данные процессора
;Чрезвычайно полезно если линия выводится в одном
;цвете!!!
OUT DX,AX
MOV AH,CS:PUTMODE ;режим вывода
MOV Al,3 ;номер регистра
OUT DX,AX ;установка регистра сдвига - выбора
MOV DX,0050h ;incY=80
MOV BX,CS:E_Y
SUB CX,CS:S_X ;dx=ex-sx
SUB BX,CS:S_Y ;dy=ey-sy
JNS @A2 ;переход если результат > 0
NEG BX ;dy=-dy
MOV DX,-80 ;incY=-80
@A2: JNZ @A3 ;if ey=sy then
MOV DX,0 ;incy=0;
; BX->dy DX->incr
@A3: MOV BP,CX ;dist=dx
CMP BX,CX ;if dy>dx
JNG @A4 ;переход если dx>dx
MOV BP,BX ;dist=dy
;CX->dx BX->dy DX->incr BP->dist
@A4: MOV SI,BX
MOV DI,CX
MOV CS:Bf1,CX
MOV CS:Bf2,BX
MOV CS:Incr,DX
;SI->dy DI->dx
; подготовка цикла
MOV AX,CS:S_Y
MOV BX,CS:S_X
MOV CX,BX
CALL CALCOFS ;рассчет смещения в буфере
AND CL,07h
MOV AH,080h
SHR AH,CL ;исходная маска
MOV DX,3CEh ;порт контроллера
MOV AL,8 ;регистр битовой маски
OUT DX,AX ;установить маску
MOV CX,BP ;счетчик цикла
INC CX
; DX->номер порта
; AX->AH-маска AL-08 -номер регистра
; BX->смещение в буфере
; SI->yerr DI->xerr BP->dist
; цикл построения линии;
@L1: MOV AL,ES:[BX] ;заполнить задвижки
MOV ES:[BX],AL ;запись пиксела
ADD DI,CS:Bf1 ;xerr=xerr+dx
ADD SI,CS:Bf2 ;yerr=yerr+dy
CMP SI,BP ;if yerr>dist
JNG @L2
SUB SI,BP ;yerr=yerr-dist
ADD BX,CS:Incr ;sy=sy+-80(+-1)
@L2: CMP DI,BP ;if xerr>dist
JNG @L3
SUB DI,BP ;xerr=xerr-dist
ROR AH,1 ;сдвинуть маску вправо
ADC BX,0000 ;если перенос увеличить
^^^^^^^^^^^^^ ;смещение в буфере
; классный способ ( содрано из BGI драйвера )
MOV AL,8 ;восстановить номер регистра
OUT DX,AX ;установить маску
@L3: LOOP @L1
MOV AX,0001h ;восстановить регистр разрешения
OUT DX,AX ;установки / сброса
MOV AX,0003h ;регистр выбора функции
OUT DX,AX
POP BP
RETF
CALCOFS PROC NEAR ;рассчет смещения в буфере
;на входе AX->Y BX->X
MUL CS:SCR_WIDTH ;ширина экрана 80 байт
SHR BX,3
ADD BX,AX
RET
;на выходе BX->смещение
CALCOFS ENDP
Вот и все Kyrill , будут вопросы идеи пиши!!!
Best Regards Vasil.
... Catch the Blue Wave!
следующий фpагмент (5)|пpедыдущий фpагмент (3)
- [93] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS -
Msg : 19 of 19
From : Mike Malakhov 2:5030/84.8 12 Nov 94 01:21:00
To : Cyrill Malevanov
Subj : Быстрая линия need.
--------------------------------------------------------------------------------
.MSGID: 2:5030/84.8 2ec41926
.REPLY: 2:5030/31.0 ec295540
.TID: FastEcho 1.41/g 0
Hello Cyrill!
Thursday November 10 1994 16:47, Cyrill Malevanov wrote to All:
CM> Люди, не дайте помереть!!! Дайте, pls, быструю линию для VGA
CM> 640*480*16, с выводом NormalPut & XORPut.
Живи... Кстати, а еще быстрее реализовать брезенхема кому-нибудь удавалось?
Я над этой процедуркой мучался пару дней :)
----------------------------------------------------------------------------
Procedure Line ( X1, Y1, X2, Y2 : Integer;
Color : Byte );
Assembler;
Var
DeltaX, DeltaY,
Denom : Integer;
VertLonger : Word;
Asm
(* mov dx,3CEh
mov al,5
out dx,al
inc dx
in al,dx
and al,11111100b
out dx,al { Write mode = 0 }
dec dx *)
mov dx,3CEh
mov al,0
out dx,al
inc dx
mov al,Color
out dx,al
dec dx { Set/Reset value }
mov al,3
out dx,al
inc dx
mov al,WriteMode
and al,00000011b
shl al,3
out dx,al
dec dx { Set/Reset value }
mov ax,0FF01h
out dx,ax { Enable Set/Reset register }
mov bx,047CCh { inc di + ror ah,1 }
mov cl,0D7h { adc di,0 }
mov ax,X2
sub ax,X1
jge @@Go1
neg ax
mov bx,04FC4h { dec di + rol ah,1 }
mov cl,0DFh { sbb di,0 }
@@Go1:
mov DeltaX,ax
mov byte ptr cs:[@@Xinc1],bh
mov byte ptr cs:[@@Xinc2],bh
mov byte ptr cs:[@@Rot1+1],bl
mov byte ptr cs:[@@Rot2+1],bl
mov byte ptr cs:[@@Rot_+1],bl
mov byte ptr cs:[@@Xinc_+1],cl
mov bl,0C7h { add di,80 }
mov ax,Y2
sub ax,Y1
jge @@Go2
neg ax
mov bl,0EFh { sub di,80 }
@@Go2:
mov DeltaY,ax
mov byte ptr cs:[@@Yinc1+1],bl
mov byte ptr cs:[@@Yinc2+1],bl
mov VertLonger,offset @@HorizLonger
mov ax,DeltaX
cmp ax,DeltaY
jge @@Go3
xchg ax,DeltaY; mov DeltaX,ax
mov VertLonger,offset @@VertLonger
@@Go3:
mov ax,DeltaX
shl ax,1
mov Denom,ax
mov si,DeltaY
shl si,1 { T }
mov bx,DeltaX
neg bx { E }
mov ax,0A000h
mov es,ax
mov di,Y1
shl di,2
add di,Y1
shl di,4 { di = Y1*80 }
mov ax,X1
shr ax,3
add di,ax
mov cx,X1
and cx,00000111b
mov al,80h
ror al,cl
mov ah,al
mov dx,3CEh
mov al,8
out dx,al
inc dx
xor al,al
jmp VertLonger
@@HorizLonger:
mov cx,DeltaX
inc cx
@@Loop1:
or al,ah
add bx,si
jle @@Cont1
out dx,al
xchg es:[di],al
xor al,al
@@Yinc1: add di,80
sub bx,Denom
@@Rot_: ror ah,1
@@Xinc_: adc di,0
jmp @@GoLoop1
@@Cont1:
@@Rot1: ror ah,1
jnc @@GoLoop1
out dx,al
xchg es:[di],al
xor al,al
@@Xinc1: inc di
@@GoLoop1:
loop @@Loop1
out dx,al
xchg es:[di],al
jmp @@Exit
@@VertLonger:
mov cx,DeltaX
inc cx
@@Loop2:
or al,ah
add bx,si
jle @@Cont2
@@Rot2: ror ah,1
jnc @@NoInc2
out dx,al
xchg es:[di],al
xor al,al
@@Xinc2: inc di
sub bx,Denom
jmp @@Yinc2
@@NoInc2:
sub bx,Denom
@@Cont2:
out dx,al
xchg es:[di],al
xor al,al
@@Yinc2: add di,80
loop @@Loop2
out dx,al
xchg es:[di],al
@@Exit:
mov dx,3CEh
mov al,1
out dx,al
inc dx
mov al,0h
out dx,al
dec dx { Disable Set/Reset register }
mov ax,0003h
out dx,ax
End;
Bye,
WindWalker