Bresenhamin algoritmilla toteutettu Line funktio.

Oletko tehnyt jotain, mistä muut voisivat hyötyä. Postita vinkit tänne.
Post Reply
MaGetzUb
Guru
Posts: 1715
Joined: Sun Sep 09, 2007 12:35 pm
Location: Alavus

Bresenhamin algoritmilla toteutettu Line funktio.

Post by MaGetzUb »

Eksyin wikipediassa surffaillessani artikkeliin linjan toteutuksesta nopeasti, sitten löytyi Bresenhamin algoritmi. Sillä saikin nättiä tasaista linjaa ilman jakolaskuja/trigonometriaa. :)
Ja sitten väännin sen pohjalta funktion. :P

Code: Select all


'Made by MaGetzUb

SCREEN 400, 300, 32, 2

Repeat 



    Color 0, 255, 255
    DSG_Line(200, 150, MouseX(), MouseY())
    Color 255, 255, 255
    Text 0, 0, FPS()

DrawScreen
Forever




Function DSG_Line(AloitusX, AloitusY, LopetusX, LopetusY, Buffer = 0)
    If Not Buffer Then Buffer = SCREEN()
    rgb = getRGB(3) + getRGB(2) Shl 8 + getRGB(1) Shl 16
    
    Hyppy = False
    
    ErotusX = LopetusX - AloitusX 
    
    If ErotusX > 0 Then
        HyppyX = 1
    Else
        HyppyX = -1
    EndIf
    
    ErotusY = LopetusY - AloitusY
    
    If ErotusY > 0 Then
        HyppyY = 1
    Else
        HyppyY = -1
    EndIf
    
    ErotusX = Abs(ErotusX)
    ErotusY = Abs(ErotusY)
    
    If ErotusY > ErotusX Then
        Hyppy = True
        RdX = AloitusX
        AloitusX = AloitusY
        AloitusY = RdX
        RdX = ErotusX
        ErotusX = ErotusY
        ErotusY = RdX 
        RdX = HyppyX
        HyppyX = HyppyY
        HyppyY = RdX
    EndIf
    
    Erotus = (ErotusY * 2) - ErotusX
    Lock Buffer 
        For i = 0 To ErotusX
            If Hyppy Then
                PutPixel2 AloitusY, AloitusX, rgb, Buffer
            Else
                PutPixel2 AloitusX, AloitusY, rgb, Buffer
            EndIf
            While Erotus => 0
                AloitusY = AloitusY + HyppyY
                Erotus = Erotus - (ErotusX * 2)
            Wend
            AloitusX = AloitusX + HyppyX
            Erotus = Erotus + (ErotusY * 2)
        Next i
    
    
        PutPixel2 LopetusX, LopetusY, rgb, Buffer
    Unlock Buffer 
EndFunction  
Jos vain foorumilaisilla on halua, niin optioimoikaa kaavaa ja sendatkaa tähän ketjuun. :)
Last edited by MaGetzUb on Sun Jul 04, 2010 1:34 pm, edited 1 time in total.
Solar Eclipse
Meneillä olevat Projektit:
We're in a simulation, and God is trying to debug us.
User avatar
Jonez
Devoted Member
Posts: 575
Joined: Mon Aug 27, 2007 8:37 pm

Re: Bresenhamin algoritmilla toteutettu Line funktio.

Post by Jonez »

Aika näppärä, mutta vaikuttaisi olevan turhan hidas pikselitasolla. Perinteisillä kosinilla ja sinillä saa nopeamman systeemin:

Code: Select all

kulma# = GetAngle( AloitusX, AloitusY, LopetusX, LopetusY )
Lock Buffer
For i = 1 To Distance( AloitusX, AloitusY, LopetusX, LopetusY )
    PutPixel2 AloitusX + Cos( kulma ) * i, AloitusY - Sin( kulma ) * i, rgb, Buffer
Next i
Unlock Buffer
Ymmärrän kyllä että tässä haettiin juuri erilaista toteutusta kuin trigonometrinen vastaava.

Mutta oikeastaan kirjoitin tämän vastauksen ilmoittaakseni, että koodissasi on virhe. Vaikka puskurin voi funktioon syöttää, siellä silti lukitaan vain näyttöpuskuri, eli kuvilla säätäminen heittää mavia.

Edit. oikeastaan tuo trigonometrinen tapa on yhtä nopea, ellei jopa hitaampi :).
-Vuoden 2008 aloittelijan ystävä -palkinnon voittaja-
Image <- protestipelikilpailun voittaja.
Space War
Koodiapina
Forum Veteran
Posts: 2396
Joined: Tue Aug 28, 2007 4:20 pm

Re: Bresenhamin algoritmilla toteutettu Line funktio.

Post by Koodiapina »

Trigonometrialla toteutettu viiva ei kuitenkaan kulje kovin tarkasti. Bresenhamin algoritmihan perustuu juuri siihen, että pisteet olisivat juuri oikeilla paikoilla.
MaGetzUb
Guru
Posts: 1715
Joined: Sun Sep 09, 2007 12:35 pm
Location: Alavus

Re: Bresenhamin algoritmilla toteutettu Line funktio.

Post by MaGetzUb »

Jonez wrote:Aika näppärä, mutta vaikuttaisi olevan turhan hidas pikselitasolla. Perinteisillä kosinilla ja sinillä saa nopeamman systeemin:

Code: Select all

kulma# = GetAngle( AloitusX, AloitusY, LopetusX, LopetusY )
Lock Buffer
For i = 1 To Distance( AloitusX, AloitusY, LopetusX, LopetusY )
    PutPixel2 AloitusX + Cos( kulma ) * i, AloitusY - Sin( kulma ) * i, rgb, Buffer
Next i
Unlock Buffer
Ymmärrän kyllä että tässä haettiin juuri erilaista toteutusta kuin trigonometrinen vastaava.

Mutta oikeastaan kirjoitin tämän vastauksen ilmoittaakseni, että koodissasi on virhe. Vaikka puskurin voi funktioon syöttää, siellä silti lukitaan vain näyttöpuskuri, eli kuvilla säätäminen heittää mavia.

Edit. oikeastaan tuo trigonometrinen tapa on yhtä nopea, ellei jopa hitaampi :).
Ohoh, kappas korjasin puskuri virheen. Tein tuon koodin yöllä, joten siinä voi olla joitain virheitä. (Ja minulla tapana on korjailla sitä vaivihkaa jälkikäteen täälä foorumilla.)
Tässä oma tyylini tehä linja:

Code: Select all


Repeat 
    
    Color 128, 255, 0
    Line2(200, 150, MouseX(), MouseY(), SCREEN())

    Text 0, 0, FPS()

    DrawScreen 
Forever 


Function Line2(x, y, x2, y2, buffer = 0)
    
    rgb = getRGB(3) + getRGB(2) Shl 8 + getRGB(1) Shl 16
    If Not buffer Then buffer = Screen()

    dist# = ((x2 - x)^2 + (y2 - y)^2)^0.5
    
    Lock buffer
        For i = 0 To dist#
            PutPixel2 x + (x2 - x) / dist * i, y + (y2 - y) / dist * i, rgb ,buffer
        Next i
    Unlock buffer

EndFunction
Solar Eclipse
Meneillä olevat Projektit:
We're in a simulation, and God is trying to debug us.
User avatar
Kille
Active Member
Posts: 249
Joined: Wed Aug 26, 2009 3:50 pm
Location: Juankoski

Re: Bresenhamin algoritmilla toteutettu Line funktio.

Post by Kille »

en tuota voinut testata kun kännykällä selailen, mutta eikö nuo (x2-x)-jutut olisi nopeampia ihan pelkkänä x:nä? Sehän on ihan sama juttu ilman ylimääräisiä laskuja?
Koodiapina
Forum Veteran
Posts: 2396
Joined: Tue Aug 28, 2007 4:20 pm

Re: Bresenhamin algoritmilla toteutettu Line funktio.

Post by Koodiapina »

Kille wrote:en tuota voinut testata kun kännykällä selailen, mutta eikö nuo (x2-x)-jutut olisi nopeampia ihan pelkkänä x:nä? Sehän on ihan sama juttu ilman ylimääräisiä laskuja?

Code: Select all

x = 5
x2 = 20

x2-x = 15
5 != 15
x2 on erillinen muuttuja, ei tarkoita samaa kuin matematiikan 2x eli 2*x.
MaGetzUb
Guru
Posts: 1715
Joined: Sun Sep 09, 2007 12:35 pm
Location: Alavus

Re: Bresenhamin algoritmilla toteutettu Line funktio.

Post by MaGetzUb »

Eli pelkkä x tuossa alemmassa koodissani on viivan ensimmäinen vaaka-akselin parametri, ja x2 on viimmeinen vaaka-akselin koordinaatti. ;)
Sama pätee y ja y2 parametreissa.
Solar Eclipse
Meneillä olevat Projektit:
We're in a simulation, and God is trying to debug us.
Post Reply