» »

[C++] Krivulje - fillanje

[C++] Krivulje - fillanje

Mmm'Aah ::

Evo ga, pa sem jih še zafilal (zgoraj Spline, spodaj Bezier, pod sliko pa koda). Algoritem je tak, da iz točk krivulje sparsa ven horizontalne linije točk, ki so znotraj krivulje. Potem se te linije enostavno nariše z risanjem črt, kar je potem zelo hitro. Tudi v navadnem načinu, brez OpenGL pospeševanja dobim gladko animacijo pri premikanju kontrolnih točk z miško. Časovno pa tega nisem še meril.

Kar nekaj problemov mi je delalo to, da ima krivulja velikokrat že v sami liniji zaporedne točke z isto koordinato Y in to, da krivulja ko spremeni smer (odvod iz + v - ali obratno) lahko ima na konici tudi po le eno točko, kar se zlahka zamenja za običajno naraščanje/padanje krivulje. Zaradi tega, se ne da vsega skupaj enostavno razdelit po Y koordinatah in soritrat po X ter narisat. Stvar sem izpeljal tako, da sproti preverja kako krivulja zavija, ter tudi izloča zaporedne piksle in vzema samo robove.

Še bolj bi se dalo stvar optimizirat za risanje, če bi nekako dobil ven največjega in morda še kaj manjših kvadratov, ki jih lahko komot zafilam, ampak nisem še ugotovil, kako bi do tega učinkovito prišel (brez preverjanja vseh možnosti). Če ima kdo kakšno idejo ali pa referenco, prosim ;)

slikca

void InsertIntoScanline(LinkedList<Point> *scanline, Point &pt)
{
	for (Iterator<Point> *p=scanline->First(); !scanline->End(p); p=scanline->Next(p))
	{
		if (pt.x < scanline->ElementAt(p).x)
		{
			scanline->InsertAt(p, pt);
			return;
		}
	}
	
	scanline->Add(pt);
}

void RemoveFromScanline(LinkedList<Point> *scanline, Point &pt)
{
	for (Iterator<Point> *p=scanline->First(); !scanline->End(p); p=scanline->Next(p))
	{
		if (pt.x == scanline->ElementAt(p).x)
		{
			scanline->RemoveAt(p);
			return;
		}
	}
}

void FillPoints(Point points[], int size, Graphics *gfx)
{
	//Find the necessary list size
	int minY=999999, maxY=-999999, height, i;
	
	for (i=0; i<size; i++)
	{
		if (points[i].y < minY) minY = points[i].y;
		if (points[i].y > maxY) maxY = points[i].y;
	}
	
	height = maxY-minY+1;
	LinkedList<Point> *scanlines = new LinkedList<Point>[height];
	
	//Parse scanlines
	Point pt, ptPrev;
	bool multiple = false;
	int change=0, changePrev=0, changeFirst=0;
	
	for (i=0; i<size; i++, ptPrev=pt)
	{
		pt = points[i%size];
		change = pt.y-ptPrev.y;
		
		if (i>0 && change!=0 && changeFirst==0)
			changeFirst = change;

		if (i>0 && change==0)
		{
			multiple = true;
			continue;
		}
		
		if (changePrev == -change)
			InsertIntoScanline(&scanlines[ptPrev.y - minY], ptPrev);
						
		InsertIntoScanline(&scanlines[pt.y - minY], pt);
		multiple = false;
		changePrev = change;
	}
	
	if (points[size-1].y == points[0].y)
	{
		if (changePrev == changeFirst)
			RemoveFromScanline(&scanlines[points[0].y - minY], points[0]);
	}
	else
	{
		if (changePrev != changeFirst)
			InsertIntoScanline(&scanlines[points[0].y - minY], points[0]);
	}

	//Draw scanlines
	for (i=0; i<height; i++)
	{
		bool parity=false;
		foreach (Point, p, scanlines[i])
		{
			if (parity){
				pt = scanlines[i].ElementAt(p);			
				gfx->DrawLine(ptPrev, pt);
			}
			else
				ptPrev = scanlines[i].ElementAt(p);
			
			parity = !parity;
		}
	}
	
	delete[] scanlines;
}
  • zavarovalo slike: OwcA ()

Jebiveter ::

Zadeva zgleda mega! Edino kar mogoce manjka je Antialiasing, ker trenutno so robovi bolj tocke kot povezana krivulja. In ce ti je cilj vektorski gui... potem to nujno rabis.

I like :)
Certainty of death. Small chance of success. What are we waiting for?

Mmm'Aah ::

Mi jemlješ besede "izpod prstov" še preden uspem skodirat :) Here it is. All nice and shiny :D Antialiasing ni niti supesampling niti multisampling ampak je neka moja pogruntavščina ki da hell-of-a več odtenkov sivin kot prej omenjena algoritma in to v 3x krajšem času. Ne bi vedu za implementacijo tega na grafični ampak to kar sem js spisal dela vse na CPUju. Kljub temu gladka animacija ob premikanju kontrolnih točk, tudi če z miško noriš po zaslonu. >:D Še vedno je nekaj pomanjkljivosti pri antialiasanju filanih krivulj (glej podrobno pa sigurno opaziš), ampak se bom potrudil to čimprej uredit.

So...dve slikci, z filo in brez:

slikca1
slikca1

Zgodovina sprememb…

  • zavarovalo slike: OwcA ()

Gundolf ::

Hehe ampak navadne črte imaš pa še vedno aliasane. Drugače pa, si ti siguren da nočeš da bi OpenGL delal to namesto tebe in GPU namesto CPUja?

Mmm'Aah ::

hmmm...temu bi js rekel ljubezen do programiranja. Sej bi komot lahko nardil da rišem use s črtami in uporabu en glLineWidth al kaj je že za debelino in vklopu multisampling itd... ampak zakaj bi blo tako izi, če lahko to probam sprogramirat sam, se ob tem marsikaj naučim in kar je najvažnejše neizmerno vživam ob vsaki vrstici kode ki jo napišem? OK, vsak ima svoje cilje, lahko je to praktičnost, lahko je to razvoj osebnega znanja, lahko je to užitek. Js poslušam vse nekako združit.

In konec koncev........ta stvar fura čisto vredu tudi BREZ OpenGL in brez hude grafične kartice. That's my point!

Gundolf ::

Vsekakor dober point.

Drugače pa v interesu hitrosti je, da rišeš z OpenGLom. 1.2 podpira po moje že vsaka nekaj let stara integrirana kartica. Tudi če ga ne, imaš zanj softwaresko emulacijo. In si nazaj pri tem, da ti riše CPU. Le da se tokrat računalnik sam odloči ali bo obremenil CPU ali GPU.

Zdaj pa daj da vidim da se krivulji prekrivata ;)

Mmm'Aah ::

Tuki je prekrivanje. Kaj si mislil da mogoče shade-am robne pixle na belo (oz. barvo ozadja)?:) Ne,ne, js spreminjam alpha level, tako da se levo "compozitira" z ozadjem. Edino še kakšnem gamma correction bi mogu nardit, ker včasih pridejo robni pixli malo bolj temni, ko se dve močni barvi mešata (poglej robove ki se prekrivajo).

slikca

Gundolf ::

Mal sem se šel phishing za bugi :) Kakšen gamma correction sanjaš? Zdaj imaš verjetno prejšnja barva + (nova barva * alfa). Poskusi z (prejšnja barva * (1 - alfa)) + (nova barva * alfa).

Ampak navadne črte pa še vedno nisi antialiasal.

Mmm'Aah ::

Barve že mešam točno tako kot si ti reku. Fora je, da kljub temu včasih rezultat pride vizualno "pretemen". Vsaj tako pravijo "profiji" v raznih člankih po netu, mogoče je pa to stvar okusa. No, saj to so takši detajli, ki skoraj niso opazni.

Senitel ::

Gamma? A delaš kakšno filtriranje (antialiasing) oziroma interpolacije, da bi potreboval gamma correction?

Jebiveter ::

Sentinel, ce pogledas zgornje screenshote vidis, da dela antialiasing robov samih krivulj.
Certainty of death. Small chance of success. What are we waiting for?


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Izračun normale v C++ in povezava z Excelom

Oddelek: Programiranje
141514 (1164) primoz4p
»

Ati radeon, Xorg in Xv

Oddelek: Operacijski sistemi
101357 (1229) MasterMind
»

Gentoo setup problem

Oddelek: Operacijski sistemi
251653 (1477) G2
»

Linux / ATI Radeon / problem z driverji

Oddelek: Operacijski sistemi
131660 (1477) ahac
»

Vtis Gentoo Linux 1.4

Oddelek: Operacijski sistemi
211281 (1045) Brane2

Več podobnih tem