DEMO.DESIGN
Frequently Asked Questions
 
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий ф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

Всего 4 фpагмент(а/ов) |пpедыдущий фpагмент (4)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ, http://www.enlight.ru/demo/faq".