[AVR] Rita vektorbilder

[Korken]

Godagens!

För ganska länge sedan skrev jag en kod för att rita massa olika saker på en KS0108 display (punkter, linjer, text, cirklar osv), och jag fick en idé jag vill testa.
Rita vektorbilder. Alltså ange några koordinater (som blir outlines) och sedan fylla i området.

Att gör outlines och så var inga problem, men hur ska jag fylla i allt? Alltså, hur vet man vad som är innanför och utanför min figur?
Jag har googlat runt lite på mitt problem, men har inte hittat något.

Några idéer på hur man ska koda det?

Mvh
Emil

[blueint]

För en cirkel eller ellips så ta den vänstra delen och för varje punkt i denna, dra en linje till motsvarande på den högra delen. Ineffektivt men fungerar.

[Korken]

Det har har redan funktioner för, vad jag menade var en mängd av sammankopplade raka sträck.
Typ om jag drar outlines av en pil så vill jag få den automatiskt ifylld.

Jag definierar varje hör i en array för att få outlines, men jag vill fylla i den automatiskt också.
Typ som denna bild, jag har funktionen för outlines, men vill fylla i den också.

pil.png

[victor_passe]

Du kan ju börja högst upp på vänster av skärmen.
Gå pixel för pixel åt höger och när du stöter på en pixel som redan är svart(En av dina linjer) så sätter du flaggan inside=1.
Nu fortsätter du till höger men färglägger varje punkt. När du träffar på en punkt som redan var svart(En annan av dina linjer) så sätter du inside=0 och slutar att färglägga.
Fortsätt med detta för hela raden och sedan varje rad.

Inte effektivt men är lätt iaf.

Edit:
Du kan ju optimera lite genom att hitta den högsta/lägsta x och y punkten bland dina linjer så slipper du gå över hela skärmen, bara din figur.

[johano]

Googla på "flood fill" så får du en del intressanta träffar.

/johan

[bit96]

Det var ett tag sen jag gjorde en sådan rutin.
Förutsätt att polygonen inte korsar sig själv, det är då lite lättare.
Det är dock en hel del kod att skriva.

Men i princip letar du upp polygonens översta hörn.
Och sedan drar du horisontella streck mellan vänster och högerkant.
Det fungerar även med flera horisontella streck om polygonen så att säga går upp och ner flera gånger.

Kort beskrivning av metod. (Tagen ur minnet då det var ett tag sedan, men det ger väl en liten hjälp på traven)
Bygg upp en tabell med hörn genom att skanna polygonen nedåt efter dess hörn.
Linjer får alltså klippas så att han får minst två hörn på samma rad.
Kolla vinklarna på linjen före och efter varje hörn.
Utifrån vinklarna tas logiska beslut om det skall ritas eller inte.
Lägg in dessa beslut i tabellen.

När tabellen är klar går man igenom den och ritar horisontella linjer utifrån de villkor man la in.
Man bör känna till Bresenhams linjerutin.

Denna metod är alltså inte en "flood fill" utan en "vektor fill" som är mycket effektivare, men kräver lite mer kod och tankearbete.

[Icecap]

Jag gjorde en flood-fill i sin tid (i BASIC) och den fungerade ganska bra. Har såklart inte källkoden kvar men jag minns att man behöver en rimlig stor stack i någon form för att komma ihåg avgreningar.

[blueint]

Kanske det går att peta in polygonkoordinaterna i en matris och göra en elegant matrisoperation för att få floodfill med ren matematik?

[Korken]

Jag ska testa å implementera "flood fill" och se om minnet räcker, annars så ska jag se om jag inte lyckas fundera ut något.

[victor_passe]

Men det behövs ju inget minne, om du gör som jag och till viss del bit96 skrev.
Du behöver bara några byte minne.

[blueint]

Förutsätter att man kan läsa bildminnet vilket inte alltid är fallet. Och då kan man behöva räkna fram gränserna. Vilket kan kräva en del beräkning istället för dataskyfflande.

[victor_passe]

Ingen beräkning direkt, TS hade väll alla punkter i någon form av tabell, bara att hitta min/max.
Och KS0108 kan man väll läsa data från? Om man har dragit R/W tråden till en I/O iaf.

[sodjan]

> Och KS0108 kan man väll läsa data från?

Jo, *controllern* har en R/W signal i och för sig, men jag
har sett ett par kompletta KS0108 LCD-moduler där
R/W är lagd fast till GND (write-läge) och inte dragen ut
till kontakten alls.

[Swech]

En nackdel kanske.. med din rutin Viktor är att den
inte funkar om 2 figurer överlappar varandra. Då blir det XOR ritande...
Nu kanske det aldrig är fallet som TS tänkt sig

Swech

[victor_passe]

Jo, det ligger något i det.
Om man inte skippar att läsa från grafik-minnet och istället kollar om ens tabell med punkter/linjer kommer att skära pixeln man är på.
Allså, för varje pixel, kolla varje linje och varje punkt i linjen, skär den min pixel?


VÄLDIGT inoptimalt men då kommer man runt problemet iaf.