Ympyrän piirto (10p)¶
Kurssin harjoitustyö 2017 on tietokonegrafiikassa tunnettu ympyrän piirtämisalgoritmin Midpoint circle algorithm (aka Bresenham's circle algorithm) toteuttaminen y86-assembly-kielellä. Harjoitustyö tehdään harjoitustehtävissä kuvatulla y86 assembly-kääntäjällä ja simulaattorilla.
Yleinen piirtoalgoritmi perustuu liukulukulaskentaan, mutta siitä on kehitetty kokonaislukulaskentaan perustuvia versiota, joista työssä toteutamme seuraavan. Algoritmi on laskennallisesti nopea toteuttaa, koska se vaatii vain yhteen- ja vähennyslaskuja sekä yhden bitin bittishiftauksen. Ideana on, että ympyrän 360 astetta voidaan jakaa kahdeksaan 45 asteen sektoriin. Nyt ympyrän kehän pisteet tarvitsee laskea vain yhdelle sektorille ja peilata keskipisteen kautta muihin sektoreihin.
Menemättä sen syvemmin algoritmin matemaattiseen esitykseen, joka löytyy Wikipedian sivuilta, esitämme sivulta alla C-kielisen version. Muuttujat
x0
ja y0
kuvaavat ympyrän keskipistettä ja sade
sen sädettä. Ympyrän kehän pikselit x
ja y
lasketaan joka iteraatiolla. void ympyra(int64_t x0, int64_t y0, int64_t sade) {
// Alustus
int64_t x = sade-1;
int64_t y = 0;
int64_t dx = 1;
int64_t dy = 1;
int64_t err = dx - (sade << 1);
// Piirtosilmukka
while (x >= y) {
putpixel(x0 + x, y0 + y);
putpixel(x0 + y, y0 + x);
putpixel(x0 - y, y0 + x);
putpixel(x0 - x, y0 + y);
putpixel(x0 - x, y0 - y);
putpixel(x0 - y, y0 - x);
putpixel(x0 + y, y0 - x);
putpixel(x0 + x, y0 - y);
// Uudet parametrit
if (err <= 0) {
y++;
err += dy;
dy += 2;
}
if (err > 0) {
x--;
dx += 2;
err += dx - (sade << 1);
}
}
}
Työssä siis tulisi toteuttaa ylläoleva C-koodi y86-assemblyllä.
Toteutus¶
Työn tulee toteuttaa seuraavat ominaisuudet:
- Kuten harjoitustehtävien koodissa, ohjelmaa alkaa
main:
-kohkosta eikä sitä ennen ole mitään alustuksia - Parametrit ohjelmalle annetaan seuraavasti
- Rekisteri
r8
koordinaatti x0 - Rekisteri
r9
koordinaatti y0 - Rekisteri
r10
säde, maksimi 10 - Ympyrän kehän pisteet
x0+x
jay0+y
tallennetaan pinoon - x-koordinaatti tulee 64-bittisen muistipaikan ylempään 32 bittiin ja y-koordinaatti alempaan 32 bittiin
- Esimerkki
x0+x=0x3B, y0+y=0x32
tallentuu pinoon 64-bittisenä lukuna0x0000003B00000032
- Pino alkaa osoitteesta
0x800
- Ohjelmassa suorituksessa tulisi olla alle 10.000 käskyä, jotta tarkistin voi sen suorittaa
Alla testidataa lähtöarvoilla
x=0x32,y=0x32,sade=0xa
..Alustus: x0=0x32 y0=0x32 x=0x9 y=0x0 dx=0x1 dy=0x1 err=0xFFFFFFF3 1. Iteraatio: x0+x=0x3b y0+y=0x32 x0+y=0x32 y0+x=0x3b x0-y=0x32 y0+x=0x3b x0-x=0x29 y0+y=0x32 x0-x=0x29 y0-y=0x32 x0-y=0x32 y0-x=0x29 x0+y=0x32 y0-x=0x29 x0+x=0x3b y0-y=0x32 Uudet parametrit: err <= 0x0 ? true y=0x1 err=-0x12 dy=0x3 err > 0x0 ? false
Yleisiä ohjeita¶
- Harjoitustyö tehdään yksin
- Työstä saa toki keskustella muiden kanssa, mutta oma koodi on kirjoitettava itse
- Plagiointia koskevat samat säännöt kuin Johdatus-kurssin harjoitustyötä
- Koodin kommenteissa listatkaa muut, joiden kanssa olette keskustelleet tehtävästä, ettei tule plagiointiepäilyksiä samankaltaisten ratkaisujen johdosta
- Toisen opiskelijan koodia ei saa palauttaa omanaan
Ohjeita työhön¶
Assembly-kielellä koodaaminen on astetta vaativampaa kuin korkean tason kielillä joten muutama yleisohje on paikallaan. Harjoitustyön tekemiseksi on kaksi tapaa: OIKEA ja väärä.
Väärä tapa tehdä harjoitustyö on käyttää Lovelacen tarkistinta debuggaukseen. Lovelacen tarkistin ei oikeastaan auta koska se antaa aika niukasti infoa. Sen sijaan y86-kääntäjä ja simulaattori tuottavat paljonkin hyödyllistä tietoa. Eikä tälläinen try and error-tapa koodata enää assembly-kielellä yksinkertaisesti toimi..
Se OIKEA tapa toteuttaa harjoitustyö:
- Suunnittele ohjelma aluksi
- Tämähän on itsestäänselvää tässä vaiheessa kurssia..
- Rakenteellisen ohjelmoinnin menetelmistä on tässäkin hyötyä. Jaa ohjelma toiminnallisuuden mukaan osiksi, jotka voit toteuttaa erikseen ja lopuksi yhdistää toimivaksi ohjelmaksi.
- Mitä aliohjelmia tarvitaan? Miten ne sijoitetaan muistissa hyppykäskyjen / ehtolauseiden minimoiseksi?
- Onko harjoitustehtävien koodista apua?
- Rekistereille kannattaa valita johdonmukaisesti käyttötarkoitus etukäteen (eikä siitä pidä poiketa)
- Tietyt rekisterit ovat vain globaaleille muuttujille
- Tietyt rekisterit ovat vain apumuuttujille
- Tietyt rekisterit ovat vain aliohjelmakutsujen parametreille (toki voi käyttää pinoa)
- Varmista ettei pino mene koodin päälle
- Koodin tulee olla erittäin hyvin kommentoitua
- Tätä voi itse testata unohtamalla koodin muutamaksi päiväksi ja palaamalla siihen sitten..
- Algoritmiä voi laskea paperilla tai toteuttaa C-kielellä ja selvittää siitä mitä välituloksia koodin pitäisi saada
- Omaa koodia kannattaa (lue: pitää) testata simulaattorissa
- Aliohjelmien testaus erillisinä pieninä ohjelmina
- Ehtolauseet samoin ohjelmina. Testaa kaikilla erityyppisillä tuloksen arvoilla
<0, =0, >0
- Hyppykäskyissä riittää usein pelkästään
ZF
-tilabitin tarkastelu, siis onko operaation tulos nolla tai erisuuri kuin nolla
Työn palautus¶
Takaraja tehtävälle on 22. Joulukuuta. Myöhässä palautetusta työstä sakotamme tämän kurssiosion arvosanasta -1, ellei ole henkilökunnan kanssa etukäteen sovittu myöhäisestä palautuksesta. Huom! Ohjatut harjoitukset loppuvat jo 14.12.
Palautettavan ohjelman tulee olla hyvin kommentoitu ja koodin tulee toimia, mutta siinä saa olla pieniä bugeja. Sakotamme niistä pisteen per bugi / puuttuva ominaisuus.
Lovelaceen voi siis palauttaa harjoitustyön koodia, joka ei mene 100% tarkistimesta läpi. Kuitenkaan koodia, joka on alkutekijöissään ei kannata palauttaa suorituksena. Palautetusta koodista tulisi näkyä, että ratkaisua on oikeasti yritetty!
Arvostelu¶
Maksimi 10 pistettä koostuu seuraavasti:
- Toimiva ohjelma, jossa on noudatettu ohjeita: max 8p
- Tarkastuksessa löydetyt bugit / puuttuva ominaisuus: vähennetään 1-2p per bugi/ominaisuus
- Koodin kommentointi: 0-2p
Kurssiarvosana¶
Seuraava koskee tätä 3op:n osuutta.
- Harjoitustehtävistä saa max 20p
- Harjoitustyöstä saa max 10p
- Hyväksyttyyn kurssisuoritukseen pisteitä vaaditaan 50% harjoitustehtävien ja harjoitustyön yhteenlasketusta maksimista eli 15 / 30p
- Suorituksia tulee olla molemmista: sekä harjoitustehtäviä että lopputyö.
Koko kurssin Tietokonejärjestelmät (8op) arvosana tulee etusivulla kerrotun mukaisesti, molemmista osioista 50% arvosanaan.
Kurssipalaute¶
Pyydämme palautetta tästä kurssiosuudesta joko allaolevaan boksiin tai yliopiston virallisille palautesivuille palaute.oulu.fi.
Anna palautetta
Kommentteja tehtävästä?