ötletes vonalrajzoló algoritmus egy régi TP 7.0 (?) könyvben.

Fórumok

Üdv!

Sok évvel ezelőtt egy -emlékeim szerint- kék-fehér borítós Turbó pascal könyvben láttam egy nagyon jópofa vonalrajzoló algoritmust. A könyv szerint -ha jól emléxem- a Sinclair ZX Spectrum használta először azt az algoritmust vonalrajzoláshoz. Ha tudod miről beszélek és van rá módód, kérlek tedd közkinccsé azt az algoritmust itt!
Köszi!

Hozzászólások

Valaki nem tudná digitális formában elküldeni nekem azt az oldalt az assembly könyvből, plusz a forráskód fotóját?
--
unix -- több, mint kód. filozófia.
Life is feudal

Nem is tudom hányszor írtam akkoriban vonalhúzást, mert gyorsabb volt sokkal, mint a Spectrum aztán az Amiga ROM-ban levő. Később Amigán azzal versengtünk, hogy ki tudja - önmagát átíró kóddal - rövidebben megírni a vonalhúzás rutint.

Hi!

Ha minden igaz, akkor ez benne van a Jatekprogramok programozasa Pascal es assembly nyelven es a VGA kartya programozasa Pascal es assembly nyelven c. konyvek valamelyikeben. Amugy az alg. neve Bresenham-fele algoritmus, o egy IBM-es ember volt egyebkent, es van egy hasonloan egyszeru ellipszisrajzolo algoritmusa is.

By(t)e
TBS::Antiemes

Ez a forrás az Agárdi Gábor könyvében:

Vga6 Segment
assume cs:Vga6,ds:Vga6

Start: mov ax,Vga6
mov ds,ax

mov ax,0a000h
mov es,ax

mov ax,13h
int 10h

call Line

xor ax,ax
int 16h

mov ax,3
int 10h

mov ax,4c00h
int 21h

Line Proc

mov bx,word ptr [Xa]
mov ax,word ptr [Xb]

mov dx,1

sub ax,bx

jnc .1_Line

neg ax

mov dx,65535

.1_Line: mov word ptr [DELTA_X],ax
mov word ptr [PONT_X],bx
mov word ptr [SGN_X],dx

mov bx,word ptr [Ya]
mov ax,word ptr [Yb]
mov dx,1
sub ax,bx
jnc .2_Line
neg ax
mov dx,65535

.2_Line mov word ptr [DELTA_Y],ax
mov word ptr [PONT_Y],bx
mov word ptr [SGN_Y],dx

cmp ax,word ptr [DELTA_X]

jc .1_Vizsz

mov dx,ax
shr dx,1

;Fuggoleges

mov cx,ax
inc cx

.1_Fuggo: push dx

call Pont

pop dx
mov ax,word ptr [SGN_Y]
add word ptr [PONT_Y],ax
add dx,word ptr [DELTA_X]
cmp dx,word ptr [DELTA_Y]
jc .2_Fuggo

sub dx,word ptr [DELTA_Y]
mov ax,word ptr [SGN_X]
add word ptr [PONT_X],ax

.2_Fuggo loop .1_Fuggo

ret

;Vizszintes

.1_Vizsz mov cx,word ptr [DELTA_X]
mov dx,cx
inc cx
shr dx,1

.2_Vizsz push dx
call Pont
pop dx
mov ax,word ptr [SGN_X]
add word ptr [PONT_X],ax
add dx,word ptr [DELTA_Y]
cmp dx,word ptr [DELTA_X]
jc .3_Vizsz
sub dx,word ptr [DELTA_X]
mov ax,word ptr [SGN_Y]
add word ptr [PONT_Y],ax

.3_Vizsz loop .2_Vizsz

ret

Line Endp

Pont Proc

mov di,word ptr [PONT_X]
mov ax,word ptr [PONT_Y]
mov bx,320
mul bx
add di,ax
mov al,byte ptr [COLOR]
mov es:[di],al
ret

Pont Endp

PONT_X: dw ?
PONT_Y: dw ?

Xa: dw 50
Ya: dw 50

Xb: dw 200
Yb: dw 100

DELTA_X: dw ?
DELTA_Y: dw ?

SGN_X: dw ?
SGN_Y: dw ?

COLOR: db ?

Vga6 Ends
End Start

; A magyarázatokat kihagytam. Azt el lehet olvasni:
; Agárdi Gábor: Gyakorlati Assembly (ISBN 963 577 117 7)
; 154-160. oldal
; Bár az ottani forráskódban levő magyarázat egy helyen
; mintha hibás lenne... (157. oldalon).

--
unix -- több, mint kód. filozófia.
Life is feudal

Valami hasonló BASH scriptben:


#!/bin/bash

VER=1

X_START=$1; Y_START=$2; X_STOP=$3; Y_STOP=$4
X_PONT=$X_START; Y_PONT=$Y_START

if [ $X_START -gt $X_STOP ]
then
    X_STEP=-1
    X_DELTA=`expr $X_START - $X_STOP`
else
    X_STEP=1
    X_DELTA=`expr $X_STOP - $X_START`
fi

if [ $Y_START -gt $Y_STOP ]
then
    Y_STEP=-1
    Y_DELTA=`expr $Y_START - $Y_STOP`
else
    Y_STEP=1
    Y_DELTA=`expr $Y_STOP - $Y_START`
fi

if [ $VER -eq 1 ]
then
    echo "D X: $X_DELTA     D Y: $Y_DELTA"
fi

if [ $X_DELTA -ge $Y_DELTA ]
then
    SZAMLALO=`expr $X_DELTA / 2`
    HOSSZ=`expr $X_DELTA + 1`
    for pont in `seq 1 $HOSSZ`
    do
        echo -n "$X_PONT    $Y_PONT"
        if [ $VER -eq 1 ]
        then
            echo "       sz: $SZAMLALO"
        else
            echo
        fi
        SZAMLALO=`expr $SZAMLALO + $Y_DELTA`
        if [ $X_DELTA -le $SZAMLALO ]
        then
            SZAMLALO=`expr $SZAMLALO - $X_DELTA`
            Y_PONT=`expr $Y_PONT + $Y_STEP`
        fi
        X_PONT=`expr $X_PONT + $X_STEP`
    done
else
    SZAMLALO=`expr $Y_DELTA / 2`
    HOSSZ=`expr $Y_DELTA + 1`
    for pont in `seq 1 $HOSSZ`
    do
        echo -n "$X_PONT    $Y_PONT"
        if [ $VER -eq 1 ]
        then
            echo "       sz: $SZAMLALO"
        else
            echo
        fi
        SZAMLALO=`expr $SZAMLALO + $X_DELTA`
        if [ $Y_DELTA -le $SZAMLALO ]
        then
            SZAMLALO=`expr $SZAMLALO - $Y_DELTA`
            X_PONT=`expr $X_PONT + $X_STEP`
        fi
        Y_PONT=`expr $Y_PONT + $Y_STEP`
    done
fi

--
unix -- több, mint kód. filozófia.
Life is feudal

Elkészítettem spectrum emulátoron a basic programot, amivel le lehet ellenőrizni, hogy tényleg jó az algoritmus.

10 INPUT "kiindulopont X: ";startx
20 INPUT "kiindulopont Y: ";starty
30 INPUT "vegpont X: ";stopx
40 INPUT "vegpont Y: ";stopy
50 LET deltax = ABS (stopx - startx)
60 LET deltay = ABS (stopy - starty)
70 LET xpont = startx: LET ypont = starty
80 LET stepx = 1
90 IF startx > stopx THEN LET stepx = -1
100 LET stepy = 1
110 IF starty > stopy THEN LET stepy = -1
200 IF deltax >= deltay THEN GO TO 1000
300 LET szamlalo = deltay / 2
310 LET hossz = deltay + 1
320 FOR p = 1 TO hossz
330 PLOT xpont,ypont
340 LET szamlalo = szamlalo + deltax
350 IF deltay <= szamlalo THEN LET szamlalo = szamlalo - deltay: LET xpont = xpont + stepx
360 LET ypont = ypont + stepy
370 NEXT p
900 STOP
1000 LET szamlalo = deltax / 2
1010 LET hossz = deltax + 1
1020 FOR p = 1 TO hossz
1030 PLOT xpont,ypont
1040 LET szamlalo = szamlalo + deltay
1050 IF deltax <= szamlalo THEN LET szamlalo = szamlalo - deltax: LET ypont = ypont + stepy
1060 LET xpont = xpont + stepx
1070 Next p

és az adatkiírós változat:

5 LET ver = 1
10 INPUT "kiindulopont X: ";startx
20 INPUT "kiindulopont Y: ";starty
30 INPUT "vegpont X: ";stopx
40 INPUT "vegpont Y: ";stopy
50 LET deltax = ABS (stopx - startx)
60 LET deltay = ABS (stopy - starty)
65 IF ver = 1 THEN PRINT "Delta X: ";deltax;" Delta Y: ";deltay
70 LET xpont = startx: LET ypont = starty
80 LET stepx = 1
90 IF startx > stopx THEN LET stepx = -1
100 LET stepy = 1
110 IF starty > stopy THEN LET stepy = -1
200 IF deltax >= deltay THEN GO TO 1000
300 LET szamlalo = deltay / 2
310 LET hossz = deltay + 1
320 FOR p = 1 TO hossz
330 IF ver = 0 THEN PRINT xpont;" ";ypont
333 IF ver = 1 THEN PRINT xpont;" ";ypont;" sz: ";szamlalo
340 LET szamlalo = szamlalo + deltax
350 IF deltay <= szamlalo THEN LET szamlalo = szamlalo - deltay: LET xpont = xpont + stepx
360 LET ypont = ypont + stepy
370 NEXT p
900 STOP
1000 LET szamlalo = deltax / 2
1010 LET hossz = deltax + 1
1020 FOR p = 1 TO hossz
1030 IF ver = 0 THEN PRINT xpont;" ";ypont
1033 IF ver = 1 THEN PRINT xpont;" ";ypont;" sz: ";szamlalo
1040 LET szamlalo = szamlalo + deltay
1050 IF deltax <= szamlalo THEN LET szamlalo = szamlalo - deltax: LET ypont = ypont + stepy
1060 LET xpont = xpont + stepx
1070 Next p

--
unix -- több, mint kód. filozófia.
Life is feudal

Elnézést, hogy ennyit idefirkálok, de az archívum számára ugyebár...
C++ fordítóval megetethető változat:

IranyVektor.cpp:


#include <cstdlib>

#ifndef    KISZAMOL_H
#define    KISZAMOL_H
#include "kiszamol.h"
#endif



class IranyVektor
    {
    private:
        int     Step, Delta;

    public:
        int Aktualis;
        IranyVektor(int Start=1, int Stop=4)
            {   
            Delta=(int) abs(Stop - Start);
            if ( Start > Stop )
                {
                Step = -1;
                }
            else
                {
                Step = 1;
                }    
            Aktualis = Start;
            }

        ~IranyVektor()           {}
        int GetDelta()           { return Delta;    }
        int GetStep()            { return Step;     }
    };

kiszamol.cpp:


#include <iostream>
#include <cstdlib>

#ifndef    KISZAMOL_H
#define    KISZAMOL_H
#include "kiszamol.h"
#endif

#ifndef    IRANYVEKTOR_H
#define    IRANYVEKTOR_H
#include "IranyVektor.cpp"
#endif

using std::cout; using std::endl; using std::cin;

int kiszamol(int a, int b, int c, int d, bool MelyikRovidebb, bool Verbose)
    {
    int HOSSZ,SZAMLALO, *Xpont,*Ypont;
    int HosszabbStart = a;
    int HosszabbStop  = b;
    int RovidebbStart = c;
    int RovidebbStop  = d;
    IranyVektor Hosszabb(HosszabbStart,HosszabbStop);
    IranyVektor Rovidebb(RovidebbStart,RovidebbStop);

    if (MelyikRovidebb)
        {
        Xpont = &Hosszabb.Aktualis;
        Ypont = &Rovidebb.Aktualis;
	if (Verbose)
	    {
	    cout << "Delta X: " << Hosszabb.GetDelta() << "       " << "Delta Y: " << Rovidebb.GetDelta() << endl;
	    }
        }
    else
        {
        Ypont = &Hosszabb.Aktualis;
        Xpont = &Rovidebb.Aktualis;
	if (Verbose)
	    {
	    cout << "Delta X: " << Rovidebb.GetDelta() << "       " << "Delta Y: " << Hosszabb.GetDelta() << endl;
	    }
        }

    HOSSZ    = Hosszabb.GetDelta() + 1;
    SZAMLALO = Hosszabb.GetDelta() / 2;

    for (int p=1; p <= HOSSZ; p++)
        {
        cout << *Xpont << "   " << *Ypont;
	if (Verbose)
	    {
	    cout << "     sz: " << SZAMLALO;
	    }
        cout << endl;
        SZAMLALO = SZAMLALO + Rovidebb.GetDelta();
        if ( Hosszabb.GetDelta() <= SZAMLALO )
            {
	    SZAMLALO = SZAMLALO - Hosszabb.GetDelta();
	    Rovidebb.Aktualis = Rovidebb.Aktualis + Rovidebb.GetStep();
	    }
        Hosszabb.Aktualis = Hosszabb.Aktualis + Hosszabb.GetStep();	
        }

    }

kiszamol.h:

int kiszamol(int, int, int, int, bool, bool);

ZXVonal_0_3.cpp:


#include <iostream>
#include <cstdlib>

#ifndef    KISZAMOL_H
#define    KISZAMOL_H
#include "kiszamol.h"
#endif

#ifndef    IRANYVEKTOR_H
#define    IRANYVEKTOR_H
#include "IranyVektor.cpp"
#endif

using std::cout; using std::endl; using std::cin;

int main(int argc,char * argv[])
{
char *strptr[5];
strptr[1]="Kezdopont X iranyvektora: ";
strptr[2]="Vegpont   X iranyvektora: ";
strptr[3]="Kezdopont Y iranyvektora: ";
strptr[4]="Vegpont   Y iranyvektora: ";
int koord[5];
bool VER;
VER=1;

if (argc < 6 || !strcmp(argv[5],"0"))
    {
    VER=0;
    }

for (int i=1;i<=(argc - 1);i++)
    {
    koord[i]=atoi(argv[i]);
    }

for (int i=argc; i<=4;i++)
    {
    cout << strptr[i];
    cin >> koord[i];
    }


if ( abs(koord[3]-koord[1]) >= abs(koord[4]-koord[2]) )
    {
    kiszamol(koord[1],koord[3],koord[2],koord[4],1,VER);
    }
else
    {
    kiszamol(koord[2],koord[4],koord[1],koord[3],0,VER);
    }
}

Makefile:


CC = g++
TARGET = ZX_Vonal_szamolo.e

ZX_Vonalszamolo.e: IranyVektor.o kiszamol.o ZXVonal_0_3.cpp
	$(CC) -o $(TARGET) IranyVektor.o kiszamol.o ZXVonal_0_3.cpp

IranyVektor.o: IranyVektor.cpp
	$(CC) -c IranyVektor.cpp

kiszamol.o: kiszamol.h kiszamol.cpp
	$(CC) -c kiszamol.cpp

clean:
	rm -rf *.o
	rm -rf $(TARGET)

--
unix -- több, mint kód. filozófia.
Life is feudal

Megtaláltam azt a bizonyos régi Turbo Pascal kódot:


Program Vonal;
Uses Graph,Crt;

Type
     TVektor = record
               aktualis_koordinata: integer;
	       kezdopont:           integer;
	       vegpont:             integer;
	       hossz:               integer;
	       leptetes:            integer;
	       koordinata_tengely:     char;
	       end;
	       
Var
    x_vektor, y_vektor:             TVektor;
    nagyobb_vektor, kisebb_vektor:  TVektor;
    segedkonstans, vonal_hossza:    integer;
    pont_x_koord, pont_y_koord:     integer;
    ch:                                char;
    
Procedure GrS;
Var Gd,Gm:                          integer;
Begin
Gd:=Detect;
InitGraph(Gd,Gm,'d:\bp\bgi');
End;

Procedure Pont;
Begin
if nagyobb_vektor.koordinata_tengely='x' then
             begin
	     pont_x_koord:=nagyobb_vektor.aktualis_koordinata;
	     pont_y_koord:=kisebb_vektor.aktualis_koordinata;
	     end
else	     
	     begin
	     pont_y_koord:=nagyobb_vektor.aktualis_koordinata;
	     pont_x_koord:=kisebb_vektor.aktualis_koordinata;
	     end
PutPixel(pont_x_koord,pont_y_koord,black);
end;

Begin
GrS;
SetColor(blue);
Repeat
ClrScr;
x_vektor.kezdopont:=random(600);
y_vektor.kezdopont:=random(350);
x_vektor.vegpont:=random(600);
y_vektor.vegpont:=random(350);
x_vektor.hossz:=x_vektor.vegpont-x_vektor.kezdopont;
y_vektor.hossz:=y_vektor.vegpont-y_vektor.kezdopont;
x_vektor.leptetes:=1;
y_vektor.leptetes:=1;
x_vektor.koordinata_tengely='x';
y_vektor.koordinata_tengely='y';
x_vektor.aktualis_koordinata:=x_vektor.kezdopont;
y_vektor.aktualis_koordinata:=y_vektor.kezdopont;

if x_vektor.vegpont < x_vektor.kezdopont then
       begin
       x_vektor.leptetes:=-1;
       x_vektor.hossz:=x_vektor.hossz*(-1);
       end
if y_vektor.vegpont < y_vektor.kezdopont then
       begin
       y_vektor.leptetes:=-1;
       y_vektor.hossz:=y_vektor.hossz*(-1);
       end

if x_vektor.hossz < y_vektor.hossz then
       begin
       nagyobb_vektor:=y_vektor;
       kisebb_vektor:=x_vektor;
       end
else
       begin
       nagyobb_vektor:=x_vektor;
       kisebb_vektor:=y_vektor;
       end;

segedkonstans:=nagyobb_vektor.hossz div 2;

For vonal_hossza:=1 to nagyobb_vektor.hossz + 1 do
       begin
       Pont;
       nagyobb_vektor.aktualis_koordinata:=nagyobb_vektor.aktualis_koordinata + nagyobb_vektor.leptetes;
       segedkonstans:=segedkonstans + kisebb_vektor.hossz;
       if segedkonstans > nagyobb_vektor.hossz then
             begin
	     segedkonstans:=segedkonstans - nagyobb_vektor.hossz;
	     kisebb_vektor.aktualis_koordinata:=kisebb_vektor.aktualis_koordinata + kisebb_vektor.leptetes;
	     end;
       end;
ch:=ReadKey;
Until (ch=#32);
CloseGraph;
End.
	     

--
unix -- több, mint kód. filozófia.
Life is feudal