Vykreslovanie plochy n-uholníka

Vyplňování plochy spadá pod 2D počítačovou grafiku a existuje řada způsobů, jak to řešit, v závislosti na obecnosti plochy, obecně na to stačí středoškolská matematika.

Není mi moc jasné zadání, třeba jak se dá vykreslit plocha integrálem? :-)

Zkus to upřesnit a být trochu detailnější v tom, na co nemůžeš přijít, třeba dokážu poradit.

Zdravím. Samozrejme že nechcem žiadne integrále.

Chcem nejaký matematický vzťah ako prejsť "ceruzkou" po ploche zadanej ohraničením.

Běžně používaný algoritmus je Scan-line polygon fill.

Ve zkratce:

1. najdu rozsah maximální a minimální hodnoty Y, (y_min, y_max)
2. položím vodorovně pravítko na hodnotu y_min a jedu po něm tužkou
3. pokud narazím na hranu, zvednu tužku (nebo ji naopak položím, pokud byla zvednutá)
4. posunu pravítko o kousek nahoru a opakuju bod (3)

Sám o sobě je to velmi jednoduchý algoritmus, který vykresluje "liché" úseky, ale složité je zpracování okrajových podmínek, jako jsou vodorovné čáry a průniky hran a ploch nebo aliasing.

Detailní popis je třeba tady: https://www.techfak.uni-bielefeld.de/ags/wbski/lehre/digiSA/WS0607…

Tak, ako som nakreslil intuitivný obrázok, objekt sa môže skladať z n-uholníkov a teda prechádzanie cez ohraničenú plochu môže ceruzka naraziť na "n" hran. Pritom hrany sú definované iba jeho koncovými bodmi.

Ešte som nenapísal, že algoritmus bude spracovaný v mikročipu s obmedzenou kapacitou pamäti.

S tím algoritmus počítá, stačí si projít prvních pár stránek dokumentu, na který odkazuju. Spotřeba paměti se odvíjí od trade-offu výpočetní a paměťové složitosti, není problém to naprogramovat v O(n) vzhledem k počtu hran.

Je to užitečný materiál. Ale s výsledkom si nie som istý.

:))) Tenhle algoritmus jsem programoval už na střední škole, kdy jsem neznal lineární algebru a naše počítače měly extrémně pomalé CPU a minimum paměti, ale dnešní GPU kreslí svoje trojúhelníky úplně stejně, jenom to dělají paralelně a rychle výměnou za větší spotřebu paměti. Zkusit si naprogramovat prototyp je práce na chvilku, to je dobrý návod pro ověření.

Keď sa pozriem na nejaký objekt, viem si ho rozložiť a spracovať. Ale v zadaní sú iba súradnice vrcholov hran. Musel by som zrejme najskôr zistiť minimálne a maximálne X/Y, z toho urobiť mapu. A to do pamäti určite nevojde.

Takže problém je v tom, jak spočítat průnik úsečky a přímky?

Usečku zadanou vrcholy (x0,y0) a (x1,y1) můžu vyjádřit jako konvexní obal:

\( (x,y) = t.(x0,y0) + (1-y).(x1,y1) \)

Vodorovná přímka je zadaná jako (x, y2), kde x je proměnná a y2 je konstanta.

Pro jejich průnik najdu hodnotu parametru t:

\( y2 = t.y0 + (1-t).y1 \)

Pokud je 0 <= t <= 1, tak se protínají (jinak ne) a hodnotu x dopočítám snadno.

Když si najdu průnik aktuální řádky (kde běží scan-line) se všemi hranami polygonu, zjistím podle hodnoty t, jestli je mám započítat nebo ne. Ty, které počítám, seřadím podle hodnoty x jejich průniku a dostanu seznam úseček pro vykreslení.

Spotřeba paměti odpovídá počtu hran polygonu, tedy velikosti zadání, odtud O(n).

Spotřeba CPU je horší, a proto se to dál optimalizuje na inkrementální seznam průniků, ale to už je vyšší dívčí.

Ve vzorci úsečky mám překlep: \( (x,y)=t*(x0,y0)+(1-t)*(x1,y1) \)

Ďakujem, pozriem sa na to. Hlavne aby sa riešenie vošlo do 8-bit mikročipu.

To se vejde určitě, ale bez podpory FP operací je to o dost těžší. Na MOS 6510 se používal Bresenhamův algoritmus (pro praktické použití se řada výpočtu se dá zredukovat na celočíselnou aritmetiku) a další triky.

Bude to celočíselná aritmetika. Jej presnosť úplne stačí.

(x,y)=t∗(x0,y0)+(1−t)∗(x1,y1)

Čo je to X0/Y0 a X1/Y1 rozumiem :-) ale čo je to "t"?

To je parametr od 0 do 1, pro t=0 dostavame bod (x1,y1), pro t=1 dostavame bod (x0,y0).

Už chápem, ale to dostanem do výsledku v X/Y reálne číslo. Len ja budem pracovať iba s celými číslami. Moje X0/Y0 a X1/Y1 sú transformované z reálnych čísiel do celých čísel a majú rozsah 0..8000000000. Ale asi by stačilo výslednú hodnotu zaokrúhliť. A priebežná hodnota "t" mi vlastne bude udávať počet krokov po priamke, že?

Ak to dobre chápem, budem musieť pre každú úsečku vypočítať či pretína práve skúmaný bod a podľa toho nechať, alebo zdvihnúť pero. Chápem to tak správně?

Pro mě je trochu těžší odhadnout, kterým směrem poradit. Upřímně, takový algoritmus musí zručnější programátor dát maximálně do hodiny a matematika je nejvýš na úrovni cca druháku střední školy? Takže to vezmu z druhého konce.

Prototyp bych určitě programoval

• v nějakém příjemnějším prostředí, python, java, cokoliv, co je po ruce

• za použití floating-point aritmetiky

• inkrementálně, od nejjednodušší verze a pak bych ho zlepšoval a postupně optimalizoval

• za využití speciálních příkladů a výjimek, abych odchytil okrajové příklady

Až když je hotová tahle verze, která je jednodušší, dává smysl pokračovat konverzí na fixed-point aritmetiku a omezenou instrukční sadu. Třeba test na průnik přímky s úsečkou se dá zjednodušit, místo hledání parametru t a jeho hodnoty mi stačí jen jeho znaménko, když si rovnice chytře upravím. Stejně tak nemusím kontrolovat bod, kam kreslím, protože když si najdu průniky scan-line s hranami, dostanu vodorovné úsečky, které je potřeba vykreslit.

Samotné jádro algoritmu je opravdu tak jednoduché, jak to zní. Kreslím vodorovnou čáru a střídavě přestávám nebo začínám kreslit v momentě, kdy narazím na hranu. A tyhle průniky se dají pro každou řádku předpočítat, takže velmi snadno dostaneme seznam úseček, které je potřeba nakreslit - po seřazení průniků to jsou liché úseky mezi hranami, sudé se naopak nekreslí.

No skúsim sa s tým popasovať. Len je to pre 8-bit mikročip. Ideovo tomu rozumiem. Skúsim si niečo naprogramovať. Vďaka...

Možno vyzerám ako blb, ale pozrime sa na konkrétny príklad s úsečkami:

X0/Y0 -> X1/Y1 0/700 -> 500/1200 500/1200 -> 900/1200 900/1200 -> 1000/700 1000/700 -> 1100/1200 1100/1200 -> 1400/1200 1400/1200 -> 1700/800 1700/800 -> 1300/500 1300/500 -> 1600/300 1600/300 -> 1100/0 1100/0 -> 800/300 800/300 -> 400/0 400/0 -> 0/700

Potreboval by som tento uzatvorený priestor vybodkovať s rastrom 2.

Ako to konkrétne vyriešiť?

Začátky jsou někdy těžké, no :-)

Mám otázku, zjevně máš velké problémy pochopit nebo naprogramovat ten algoritmus. Proč nezačneš nějakou jednodušší úlohou, jako třeba vyplnění trojúhelníku? Zkoušel jsi googlit? Tohle se používá často, určitě existuje spousta materiálu, ať už popis nebo kód.

Bohužel, nevím, jak lépe poradit, než že bych to sám naprogramoval.

Tahle kniha je v češtině a obsahuje popis řady algoritmů včetně vyplňování polygonů, https://www.knihydobrovsky.cz/kniha/moderni-pocitacova…

Jasne že neviem ako na ten algoritmus a v podstate je jedno či ide o trojuholník alebo mnohouholník. U obdĺžnika dá 2x for s krokom 2 a nemám problém. Ale u iného objektu budem musieť dookola prepočítavať body každej úsečky. teraz sa zamýšľam nad vytvorenie bitovej mapy, kde zanesiem body úsečiek a potom na to hodím 2x for. Ale to mi zožerie veľa pamäti. Pre rozmer 35x35cm s rastrom 0,2 to bude skutočne veľa.