[2d/c++] Polygon tekenen

[MisterData]

Goed, ik ben nu al twee uur aan het zoeken (google, flipcode, gamedev enzo) naar een oplossing voor mijn 'probleem'. Het zal ongetwijfeld heel simpel op te lossen zijn, maar ik ben er nog niet opgekomen.

Het gaat om het volgende: ik heb een polygoon (een veelhoek dus) en die bestaat uit een lijst van 2d-punten. Nu wil ik dat ding gaan tekenen. Daar kun je natuurlijk een mooie functie voor aanroeken (DrawPolygon, ik gebruik wxWindows). Maar daar heb ik niks aan, want ik wil dat ding vullen met een gradient (kleurverloop). Ik moet dus per pixel gaan tekenen, alleen heb ik echt geen idee hoe ik nou zo'n polygoon pixeltje voor pixeltje (en dan liefst nog snel ook) op het scherm kan krijgen. Kan iemand mij misschien een duwtje (of een schop ) in de goeie richting geven?

[.oisyn]

hier staat wel wat info in: [rml][ 3d] Zelf een Z-Buffer bakken (?)[/rml]

het idee is gewoon de scanlines afgaan van boven naar beneden, en de x- en rgb-waarden interpoleren

.edit: hier zijn overigens superveel tutorials over te vinden Kijk eens bij www.flipcode.com en www.gamedev.net

[ Voor 22% gewijzigd door .oisyn op 15-12-2002 18:24 ]

[MisterData]

.oisyn schreef op 15 December 2002 @ 18:18:
hier staat wel wat info in: [rml][ 3d] Zelf een Z-Buffer bakken (?)[/rml]

het idee is gewoon de scanlines afgaan van boven naar beneden, en de x- en rgb-waarden interpoleren

.edit: hier zijn overigens superveel tutorials over te vinden Kijk eens bij www.flipcode.com en www.gamedev.net

Als ik wist hoe het heet (een term ofzo) dan gaat het zoeken ook wat makkelijker Ik heb op bovengenoemde sites echter niks kunnen vinden helaas Bedankt voor je link naar dat andere topic iig

edit://

Ik zie hier wel een brok code staan:

code:

void fillTriangle (Vertex v0, Vertex v1, Vertex v2)
{
    if (v0.y > v1.y)
        swap (v0, v1);
    if (v1.y > v2.y)
        swap (v1, v2);
    if (v0.y > v1.y)
        swap (v0, v1);

    x0 = x1 = v0.x;
    dx0 = (v2.x - v0.x) / (v2.y - v0.y);
    dx1 = (v1.x - v0.x) / (v1.y - v0.y);

    for (y is v0.y to v1.y)
    {
        drawSpan (x0, x1);
        x0 += dx0;
        x1 += dx1;
    }

    x1 = v1.x;
    dx1 = (v2.x - v1.x) / (v2.y - v1.y);

    for (y is v1.y to v2.y)
    {
        drawSpan (x0, x1);
        x0 += dx0;
        x1 += dx1;
    }
}

om een triangle in te kleuren, maar hoe moet ik dat met een polygon doen?

[ Voor 37% gewijzigd door MisterData op 15-12-2002 18:29 ]

[Verwijderd]

MisterData schreef op 15 December 2002 @ 18:25:
om een triangle in te kleuren, maar hoe moet ik dat met een polygon doen?

Deel je veelhoek op in driehoekjes?

[.oisyn]

MisterData schreef op 15 december 2002 @ 18:25:
[...]


Als ik wist hoe het heet (een term ofzo) dan gaat het zoeken ook wat makkelijker Ik heb op bovengenoemde sites echter niks kunnen vinden helaas Bedankt voor je link naar dat andere topic iig

polyfiller, polygon drawing routine, polygon renderer...
dat soort termen

Ik zie hier wel een brok code staan:
[knip]
om een triangle in te kleuren, maar hoe moet ik dat met een polygon doen?

Zorg dat je een cyclische lijst hebt van de punten in de polygoon (door bijvoorbeeld een doubly linked list te gebruiken, maar gewoon een array systeem waarbij je wrapping toepast werkt ook).
Zoek voordat je gaat tekenen het bovenste en het onderste punt, dit zijn je start en eindpunten

Je begint bij het bovenste punt, en je gaat nu langs de linker- en rechteredge naar beneden. Je houdt dus steeds 2 sets aan coordinaten bij, 1 voor de linkerkant en een voor de rechterkant. Je beweegt telkens 1 pixelrij naar beneden, en dan bereken je de nieuwe x en kleurwaarden aan de linkerkant en aan de rechterkant. Als je aan het eind van een edge komt ga je door met de edge die daarop volgt. Tot je uiteindelijk bij het onderste punt uitkomt

Ik zal er even een tekeningetje bij maken, dan is het misschien wat makkelijker te begrijpen (mijn uitleg is niet altijd je-van-het namelijk )
.edit:

Verwijderd schreef op 15 december 2002 @ 18:41:

Deel je veelhoek op in driehoekjes?

dat is wel een optie, maar niet helemaal correct. De gradienten kloppen dan alleen binnen de driehoeken, en dan kun je dus mogelijk de opdeling zien door een verkeerd verloop van kleuren van driehoeken die naast elkaar liggen

[Janoz]

.oisyn schreef op 15 december 2002 @ 19:48:
Je begint bij het bovenste punt, en je gaat nu langs de linker- en rechteredge naar beneden. Je houdt dus steeds 2 sets aan coordinaten bij, 1 voor de linkerkant en een voor de rechterkant. Je beweegt telkens 1 pixelrij naar beneden, en dan bereken je de nieuwe x en kleurwaarden aan de linkerkant en aan de rechterkant. Als je aan het eind van een edge komt ga je door met de edge die daarop volgt. Tot je uiteindelijk bij het onderste punt uitkomt

Dit werkt alleen waneer het een convex polygon is (dat wil zeggen dat waneer je twee punten in een polygon kiest en hier een lijn tussen trekt, dat deze lijn dan ook in zijn geheel binnen het polygoon valt)

Dit valt te omzeilen door met een soort scanline algoritme te gebruiken waarop je de snijpunten van de edges met deze snijlijn bijhoud. Dit lijkt heel erg op .oisyn's algoritme, met het verschil dat je op sommige momenten meer dan 2 punten bij zult moeten houden.

[...]


dat is wel een optie, maar niet helemaal correct. De gradienten kloppen dan alleen binnen de driehoeken, en dan kun je dus mogelijk de opdeling zien door een verkeerd verloop van kleuren van driehoeken die naast elkaar liggen

Waneer het gradient verloop op de juiste manier wordt geinterpoleerd hoeft dit niet te gebeuren. Stel dat je eerst je de waarden van je vertices hebt geinterpoleerd, dan wordt de kleur van de grens van het ene triangle geinterpoleerd volgens de zelfde vertex waardes als de andere triangle dus in principe zou je geen grens moeten kunnen zien.

[ Voor 6% gewijzigd door Janoz op 15-12-2002 20:00 ]

[.oisyn]

Janoz schreef op 15 December 2002 @ 19:58:

Dit werkt alleen waneer het een convex polygon is (dat wil zeggen dat waneer je twee punten in een polygon kiest en hier een lijn tussen trekt, dat deze lijn dan ook in zijn geheel binnen het polygoon valt)

jah, daar ging ik eerlijk gezegd ook vanuit

Dit valt te omzeilen door met een soort scanline algoritme te gebruiken waarop je de snijpunten van de edges met deze snijlijn bijhoud. Dit lijkt heel erg op .oisyn's algoritme, met het verschil dat je op sommige momenten meer dan 2 punten bij zult moeten houden.

idd, het enige wat je ook nog moet doen is van tevoren alle startpunten opzoeken (je kunt immers niet terug omhoog gaan langs een edge)

Waneer het gradient verloop op de juiste manier wordt geinterpoleerd hoeft dit niet te gebeuren. Stel dat je eerst je de waarden van je vertices hebt geinterpoleerd, dan wordt de kleur van de grens van het ene triangle geinterpoleerd volgens de zelfde vertex waardes als de andere triangle dus in principe zou je geen grens moeten kunnen zien.
[/nohtml]

Stel je hebt een quad waarop een volledige texture zit geplakt. Deze quad bestaat uit 2 driehoeken. Als je nu bij een hoekpunt dat niet wordt gedeeld de texturecoordinaat veranderd, dan zal de texture alleen anders gemapped worden op die triangle van de quad; aan de andere helft zal niets veranderen (terwijl dat wel de bedoeling is)

[Zoijar]

Kan je niet gewoon openGL gebruiken? Dat is een stuk makkelijker en sneller.

[.oisyn]

Zoijar schreef op 15 December 2002 @ 20:47:
Kan je niet gewoon openGL gebruiken? Dat is een stuk makkelijker en sneller.

De reference rasterizer van OpenGL is allesbehalve snel
Bijkomend nadeel is dat je verder de hele setup erbij hebt (gl rendercontext, je window moet aan bepaalde eisen voldoen, etc.)

[Zoijar]

Het zal toch waarschijnlijk niet echt langzamer zijn dat wat je zelf maakt. En als het dat wel is zal het wel een stuk "correcter" zijn. En met een beetje mazzel heb je gewoon hardware ondersteuning, daar kan je zelf dan nooit tegen op.
En als je Glut gebruikt is die setup zo simpel...komt neer op iets als dit:

code:

    glutInit(argc, argv);
    glutInitWindowSize(256, 256);
    glutInitWindowPosition(100,100);
    glutInitDisplayMode(GLUT_RGBA | GLUT_DEPTH | GLUT_DOUBLE);
    g_window = glutCreateWindow("GLUT Window");

Maar ok, was maar een idee :-)

[.oisyn]

[nohtml]

Zoijar schreef op 15 december 2002 @ 21:13:
Het zal toch waarschijnlijk niet echt langzamer zijn dat wat je zelf maakt.

Zeker wel
De reference rasterizer van OpenGL is gericht op correctheid, niet op snelheid. Dat komt vooral neer op pixel en texel correctheid, dus hoe alles wordt gerasterized. Meestal zijn dat dingen die echt totaal niet boeien (alsof het iemand uitmaakt dat die ene pixel linksboven er officieel niet in hoort maar wel wordt getekend). Verder is OpenGL nogal een abstract iets, met ondersteuning voor allerlei pixelformaten en renderstates. Daar heeft MisterData niet echt last van, en dus is het niet zo moeilijk om een triangle filler te maken die sneller is dan de software opengl variant

En als je Glut gebruikt is die setup zo simpel...komt neer op iets als dit:

code:

    glutInit(argc, argv);
    glutInitWindowSize(256, 256);
    glutInitWindowPosition(100,100);
    glutInitDisplayMode(GLUT_RGBA | GLUT_DEPTH | GLUT_DOUBLE);
    g_window = glutCreateWindow("GLUT Window");

mja, nu maak je dus een hele nieuwe window, je rendert niet in een device context van een een of ander child windootje. Wereld van verschil

Maar idd, een voordeel is wel weer dat je van hardware acceleration gebruik maakt als dat mogelijk is, iets wat tegenwoordig overigens zo goed als standaard is. Neemt niet weg dat het nog steeds interessant is om eens te kijken hoe zo'n polyfiller nou in elkaar zit

[MisterData]

OpenGL heb ik liever niet, maar had er inderdaad ook al aan gedacht For now zal ik me wel behelpen met je zgn. 'convexe' polygonen. Ik zal het algoritme van .oisyn es proberen. Als er iemand nog wat ideeen heeft, dan hoor ik het graag

[RickN]

Wat je wilt doen lijkt erg veel op gouraud-shading, alleen interpoleer je daarbij tussen een aantal kleuren dat gelijk is aan het aantal vertices in je poly. Over gouraud shading is zeker wel veel info te vinden en als je dat kunt kun je ook zeker wat jij wilt.

[hobbit_be]

je kun ook proberen de Flash 4 player code te pakken te krijgen - die hebben ze ooit eens gereleased. Das tamelijk duidelijk want die code was geschreven voor clarity en niet voor speed.

Om concave polys te vullen is nooit eenvoudig (voor zover ik weet doet OpenGL (hardware) dit niet altijd correct). Best dat je alles opdeelt in TRIS. en dan natuurlijk gebruik maken de beste methode om dat te doen (ie: minimum van TRI). en wat bedoel je met gradient? heeft elk punt een andere kleur op is't 'gewoon' een flash gedoe... in dat geval zeker met spans werken (wat eigenlijk neerkomt op een fask mask)... Als je concave will omzeilen gebruik je best het geillustreerde example hoger int forum - heel efficient en dead easy.

[JayTaph]

Denthor van Asphyxia heeft hier hele mooie tutorials voor (oa poly filling, gouraud/texture filling etc).

http://www.hornet.org/code/tutors/denthor/

[MisterData]

RickN schreef op 16 December 2002 @ 10:13:
Wat je wilt doen lijkt erg veel op gouraud-shading, alleen interpoleer je daarbij tussen een aantal kleuren dat gelijk is aan het aantal vertices in je poly. Over gouraud shading is zeker wel veel info te vinden en als je dat kunt kun je ook zeker wat jij wilt.

Gouraud shading

[Zoijar]

Goeie ouwe tijd Cycles afschaven van tri filler innerloops. Heb nog een texture mapped tri filler liggen in assembler, 6 tick innerloop, regel of 1000 totaal...dat waren nog is tijden hehe...registers op je FPU bijhouden, en instructies overlappen, alles omgooien om het een paar tikken sneller te krijgen.

Gouraud shading is als je de licht intensiteit per vertex bepaald, en die dan linear interpoleert over de polygon. (de inverse linear voor perspectieve correctheid)

[ Voor 22% gewijzigd door Zoijar op 16-12-2002 14:16 ]

[.oisyn]

MisterData schreef op 16 December 2002 @ 14:12:
Gouraud shading

Flat shading is het tekenen van een polygoon in 1 vaste kleur, terwijl gouraud shading betekent dat de kleurwaarden geinterpoleerd worden

addendum:
Dit is overigens niet helemaal correct, gouraud shading is een belichtingstechniek die wordt bereikt door de hoekpunten van de polygoon te belichten, en daartussen te interpoleren. Dus gewoon random kleurtjes toekennen en dat interpoleren is in feite geen gouraud shading, hoewel dat wel vaak zo genoemd wordt

[.oisyn]

hobbit_be schreef op 16 December 2002 @ 12:38:
Om concave polys te vullen is nooit eenvoudig (voor zover ik weet doet OpenGL (hardware) dit niet altijd correct).

opengl kan ook helemaal geen polygonen tekenen, alleen triangles en quadilaterals (quads)

Een mogelijkheid om een convex polygon te tekenen is gebruik maken van triangle fans, maar uiteraard kunnen concave polygonen hier niet altijd mee gerealizeerd worden (en daar is het ook niet voor gemaakt)

[hobbit_be]

.iosyn - niet dat het iets uitmaakt maar toch effe puntjes op de i zetten:

glBegin(GL_POLYGON);

dit can wel degelijk meer dan 3/4 (1-N) vertices aan zolang ze convex zijn (in sommige
gevallen en met wat 'chance' kan ie ook concave aan - uit ervaring).

rechtstreeks uit de reference manual...

[.oisyn]

En moet jij eens kijken hoe dat in hardware wordt geimplementeerd... juist, een triangle fan
Maar je hebt idd gelijk dat die optie er is, die was ik helemaal vergeten (ik werk tegenwoordig alleen nog maar met directx 8.1, die zowel geen quads als geen polygonen kan tekenen (wel triangle strips though))

[hobbit_be]

idd vandaar dat ik in mijn original ook zei dat ie op hardware niet goed word uitgevoerd. Maar das eigenlijk de schuld van de drivers en niet de hardware. Maar ik heb ook moeten opzoeken hoor twas inderdaad ook al een tijdje geleden dat ik het heb gebruikt