GrafikaGyakorlo2DKepszintezis
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.
Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót
Mintakérdések a Számítógépes grafika és képfeldolgozás tárgy vizsgájára való felkészüléshez
2D képszintézis
36. Írjon erősen emelkedő szakaszt rajzoló programot, a Bresenham algoritmus alapján.
- Az algoritmus számon tartja, mennyivel kellene az x-nek nőnie, ha y eggyel nő ((x1-x0)/(y1-y0)), és hogy a rajzoláshoz használt (egész) x mennyivel tér el ettől (error). Mikor y-t növeljük, error-t is növeljük deltával, és ha túlléptük a 0.5-öt (vagyis az eggyel nagyobb x már közelebb van az egyeneshez), akkor x-et eggyel möveljük, error-t pedig eggyel csökkentjük.
- Ahhoz, hogy kikerüljük a lebegőpontos számok használatát, error helyett a 2*(y1-y0)-szorosát tartjuk nyilván (ami mindig egész lesz), értelemszerűen ekkor mindig 2*(y1-y0)*delta=2*(x1-x0)-lal nő (incr), 2*(y1-y0)*0.5=(y1-y0)-lal (threshold) kell összehasonlítani, és ha nagyobb, 2*(y1-y0)-lal (decr) csökkenteni.
- A program feltételezi, hogy a végpont mindkét koordinátája nagyobb, mint a kezdőponté (mert emelkedő szakasz), és az y koordináták különbsége nagyobb vagy egyenlő, mint az x koordinátáké (mert erősen emelkedő). A többi eset nagyon hasonló kóddal lenne kezelhető.
void draw(int x0, int y0, int x1, int y1) {
int x=x0, y=y0;
int error=0, incr=2*(x1-x0), threshold=y1-y0, decr=2*(y1-y0);
for (y=y0; y<=y1; y++) {
pixel(x, y);
error+=incr;
if (error>threshold) {
x++;
error-=decr;
}
}
}
37. Írjon DDA szakaszrajzoló függvényt: DDADraw(int x1, int y1, int x2, int y2, int R, int G, int B), amely bármilyen pozitív meredekségű szakaszt képes felrajzolni. Használhat lebegőpontos aritmetikát. Egy rasztertárbeli pixel színét a PutPixel(int x, int y, int R, int G, int B) függvénnyel változtathatja meg.
- A DDA algoritmus a Bresenham-mel ellentétben lebegőpontos számokat használ a koordináták számítására. Mivel itt nem csak erősen emelkedő szakaszt kell rajzolni, ezért a függvény elején két esetre (erősen és lankásan emelkedő) bontunk.
void DDADraw(int x1, int y1, int x2, int y2, int R, int G, int B) {
float slope=(float)(y2-y1)/(float)(x2-x1);
float xf, yf;
int x, y;
if (slope>=1) {
x=x1;
yf=y;
for ( ; x<x2; x++) {
PutPixel(x, (int)(y+0.5), R, G, B);
y+=slope;
}
} else {
slope=1/slope;
y=y1;
xf=x;
for ( ; y<y2; y++) {
PutPixel((int)(x+0.5), y, R, G, B);
x+=slope;
}
}
}
38. Írjon programot, amely egy szakaszt egy konvex sokszögre vág.
- Egy szakasznak kell tehát a sokszög belsejébe eső részét visszaadni. Egyszerűbb dolgozni, ha tudjuk, hogy pozitív körüljárású a sokszög, ezért (az előjeles területének segítségével) megnézzük, így van-e, és ha nem, megfordítjuk a csúcsainak a sorrendjét. Végiglépkedünk a sokszög oldalain, és mindig levágjuk a szakaszból, ami az oldalon kívülre esik. Ha mindkét végpont kívül van, hamissal visszatérünk (az egész szakasz a sokszögön kívül van), ha mindkettő belül, akkor békén hagyjuk, ha az egyik kívül, akkor azt kicseréljük a vágáshoz használt oldal és a szakasz metszéspontjára.
bool checkOrientation(Array<Vector> polygon) {
float signedArea=0;
for (int i=polygon.size(); i++) {
signedArea+=polygon[i].x*polygon[(i+1)%polygon.size()].y;
signedArea-=polygon[i].y*polygon[(i+1)%polygon.size()].x;
}
return (signedArea<0);
}
void reverse(Array<Vector>& polygon) {
for (int i=0; i<polygon.size()/2; i++) {
temp=polygon[i];
polygon[i]=polygon[polygon.size()-i-1];
polygon[polygon.size()-i-1]=temp;
}
}
Vector intersect(Vector start1, Vector end1, Vector start2, Vector end2) {
float a11=start2.y-end2.y, a12=end2.x-start2.x, a21=end1.y-start1.y, a22=start1.x-end1.x;
float b1=start2.y*end2.x-start2.x*end2.y, b2=end1.y*start1.x-end1.x*start1.y;
float det=a11*a22-a12*a21;
return Vector((a22*b1-a12*b2)/det, (a11*b2-a21*b1)/det);
}
bool inside(Vector clip1, Vector clip2, Vector point) {
return (point.x*(clip2.x-clip1.x)+point.y*(clip1.x-clip2.x)>clip1.x*clip2.y-clip1.y*clip2.x);
}
bool clip(Vector& start, Vector& end, Array<Vector> polygon) {
Vector clip1, clip2; /* az éppen vágáshoz használt oldal */
bool inside1, inside2;
if (checkOrientation(polygon)) reverse(polygon);
for (int i=0; i<polygon.size(); i++) {
clip1=polygon[i];
clip2=polygon[(i+1)%polygon.size()];
inside1=inside(clip1, clip2, start);
inside2=inside(clip1, clip2, end);
if (!inside1 && !inside2) {
return false;
} else if (!inside1 && inside2) {
start=intersect(clip1, clip2, start, end);
} else if (inside1 && !inside2) {
end=intersect(clip1, clip2, start, end);
}
}
return true;
}
39. Írjon programot, amely egy tetszőleges sokszöget egy konvex sokszögre vág.
40. Írjon háromszög kitöltő programot, amely háromszögenként 3 osztást és fixpontos összeadásokat tartalmazhat.
41. Írjon C++ programot, amely eldönti, hogy egy p1, p2, p3 és egy v1, v2, v3 síkbeli háromszögnek van-e közös része. Feltételezheti, hogy a vektor összeadás (+), kivonás (-), skaláris szorzás (
*
), és 90 fokkal való elforgatás ([x,y] -> [-y,x], .Rot90) műveletek a vektorokra (Vec) rendelkezésre állnak. Bónusz: általánosítsa a programot két konvex sokszögre.
- A program elég primitív módszerrel dolgozik: megnézi, benne van-e valamelyik sokszög a másikban, vagy létezik-e olyan oldaluk, ami metszi egymást (ha egyik sem, nincs közös pontjuk). Az inside függvény eldönti v összes csúcsáról és p összes oldaláról, hogy a csúcs az oldal "jó" oldalán van-e (ehhez előzör pozitív körüljárásúra állítja be p-t). intersect két szakaszról nézi meg, hogy metszik-e egymást: ha az egyik csúcsai a másik szakasz különböző oldalán vannak és viszont, akkor igen.
bool checkOrientation(Array<Vector> polygon) {
float signedArea=0;
for (int i=polygon.size(); i++) {
signedArea+=polygon[i].x*polygon[(i+1)%polygon.size()].y;
signedArea-=polygon[i].y*polygon[(i+1)%polygon.size()].x;
}
return (signedArea<0);
}
void reverse(Array<Vector>& polygon) {
for (int i=0; i<polygon.size()/2; i++) {
temp=polygon[i];
polygon[i]=polygon[polygon.size()-i-1];
polygon[polygon.size()-i-1]=temp;
}
}
bool inside(Array<Vector> p, Array<Vector> v) {
if (checkOrientation(p)) reverse(p);
for (int i=0; i<p.size(); i++) {
for (int j=0; j<v.size(); j++) {
Vector a1=p[i], a2=p[(i+1)%p.size()], b=v[j];
if ((b-a1)*((a2-a1).Rot90())<0) return false;
}
}
return true;
}
bool intersect(Vector a1, Vector a2, Vector b1, Vector b2) {
bool inside1=(((b1-a1)*((a2-a1).Rot90())<0)^^((b2-a1)*((a2-a1).Rot90())<0));
bool inside2=(((a1-b1)*((b2-b1).Rot90())<0)^^((a2-b1)*((b2-b1).Rot90())<0));
return (inside1 && inside2);
}
bool intersectPolygons(Array<Vector> p, Array<Vector> v) {
if (inside(p, v) || inside(v, p)) return true;
for (int i=0; i<p.size(); i++) {
for (int j=0; j<v.size(); j++) {
if (intersect(p[i], p[(i+1)%p.size()], v[j], v[(j+1)%v.size()])) {
return true;
}
}
}
return false;
}
bool intersectTriangles(Vector p1, Vector p2, Vector p3, \
Vector v1, Vector v2, Vector v3) {
Array<Vector> p, v;
p.add(p1); p.add(p2); p.add(p3);
v.add(v1); v.add(v2); v.add(v3);
return (intersectPolygons(p, v));
}
42. Írjon NURBS görbe megjelenítőt, amelyben felhasználhatja a NUBS bázisfüggvényeket.
43. Írjon háromszögvágó programot, amely a csúcsaival definiált háromszögből eltávolítja azokat a pontokat, amelyek a paraméterként kapott ymin érték alatt vannak, és visszatérési értékében jelzi, hogy maradt-e egyáltalán valami a vágás után. Az eredményt a háromszögek csúcsait tartalmazó tömbben adja vissza. A megoldás során feltételezheti, hogy rendelkezésre áll egy Intersect eljárás, ami két egyenes metszéspontját kiszámítja.
44. Írjon programot, amely egy paraméterként kapott, vezérlő pontjaival (x[], y[], npoint) definiált Bézier görbét felrajzol. A vezérlőpontok koordinátái képernyőkoordinátákban (pixel egység) értendők. A rajzoláshoz a glBegin(GL_LINE_STRIP), glVertex2d(xi, yi) és glEnd( ) utasításokat használja! A képszintézis gyorsítása érdekében ne rajzoljon, ha a Bézier görbe befoglaló téglalapjának és az XRES, YRES méretű nézetablaknak nincs közös része. Feltételezheti, hogy az adott programozási nyelven az "n alatt az i" és a hatványozás beépített műveletek.
45. Írjon 2D aláosztott görbe (Catmull-Clark subdivision curve) rajzoló rutint C++ nyelven. A függvény bemeneti változói: int n a csomópontok száma, Vector2 points[] a 2D Vector2 típusú csomópontok tömbje, int level az aláosztás szintje (0 az aláosztatlan görbét jelenti). Feltételezheti, hogy a Vector2-ben a szokásos vektorműveletek operátor overloaddal már megvalósítottak. A megjelenítést GL_LINE_STRIP segítségével OpenGL-lel valósítsa meg, a felhasználható függvények (glBegin, glVertex2d, glEnd).
46. Írja fel azt az időfüggő homogén lineáris transzformációs mátrixot, amely egy [2, 0] sebességű autó 2 egység sugarú kerekét mozgatja és forgatja. Az animáció kezdetén a kerék transzformációs mátrixa az egységmátrix.
- A kerék középpontja kezdetben az origóban van, t idő elteltével pedig a (2t, 0) pontban. Mivel 2t-t haladt az autó, ezért a kör kerültének 2t hosszú része érintette a talajt, ez pedig 2t/2 (radián) szögelfordulásnak felel meg (óramutató járásával megegyező irányban, feltéve, hogy az y=-2 egyenesen gördült). Tehát először elforgatjuk a kereket 2t-vel negatív (óramutató járásával megegyező) irányba, majd eltoljuk (2t, 0)-val. [math] \left[ \begin{array}{ccc} \cos(t) & \sin(t) & 0 \\ -\sin(t) & \cos(t) & 0 \\ 2t & 0 & 1 \end{array} \right] [/math]
47. Írjon szakaszvágó programot, amely a szakaszból eltávolítja azokat a pontokat, amelyek a paraméterként kapott ymin érték alatt vannak és visszatérési értékében jelzi, hogy maradt-e egyáltalán valami a vágás után.
48. Rajzolja fel annak a hardvernek a vázlatos kapcsolási rajzát, amely minden órajelciklusra egy erősen emelkedő (x2 > x1, y2 > y1, y2-y1 > x2-x1) egyenes szakasz újabb pixelének x, y címét előállítja. Milyen értékekkel kell inicializálni a tárolókat?
49. Területkitöltés geometriai reprezentáció alapján (belső pont azonosítása, naív algoritmus, gyorsítási lehetőségek, inkrementális elv, aktív él tábla, él tábla).
50. Területek vágása ablakra (algoritmus, több részre eső területek kezelése).
51. Írja fel egy 2D autókerék transzformációs mátrixát az idő függvényében, ha az autó az x tengely irányába halad v sebességgel, a talaj y koordinátája zérus, a kerék sugara r. A lokális modellezési-koordinátarendszerben a kerék tengelye az origóban van, és t=0-ban az x koordináta ugyancsak zérus. A kerék a talajon gördül.
52. 2D grafikus rendszerek felépítése (bemeneti és kimeneti csővezeték felépítése és működése, OpenGL és a GLUT hol jelenik meg).
53. Adott egy zárt töröttvonal a síkban. A csúcsok koordinátái a px[n], py[n] tömbökben vannak, a csúcsok száma az n változóban. Írjon C++ függvényt, amely egy (x, y) pontról eldönti, hogy a töröttvonal által definiált sokszög belsejében van-e.
54. Kedves barátnője (barátja) radiológusként dolgozik a kórházban, és naponta nagyon sok röntgen képről kell eldöntenie, hogy a képen látható csont törött-e vagy sem. Milyen szerencse, hogy tanulta a számítógépes grafika területelárasztó kitöltő algoritmusát (floodfill), így tud segíteni neki! Készítsen karácsonyi ajándékként egy C++ függvényt, amely a kép alapján eldönti, hogy azon egyetlen csont található, vagy több különálló csontdarab (azaz törött-e a csont vagy sem)! Az N x M felbontású szürkeárnyalatos kép az unsigned char image[N][M] tömbben van. Tudjuk, hogy a levegő a 0..10 tartományban, a lágyszövet 10-100 tartományban, a csont pedig a 100-200 tartományban lévő szürkeségi szinteknek felel meg. A 200-256 tartományban nincs érték. Két csontdarabról akkor mondjuk, hogy különállóak, ha közöttük legalább egy pixelnyi nem csont anyag található (azaz a két tartomány csontszínű pixelei még sarkaikban sem érintkeznek). A függvény megkapja az image[N][M] tömböt és az int N,M felbontási értékeket és egy int értékkel tér vissza, ami akkor 1, ha több különálló csont is látható a képen, egyébként 0.
55. Az erdészetnél vállalt munkát, ahol tölgyfaerdőt telepítettek egy szabályos rács szerint N sorban és M oszlopban. Sajnos távvezeték építés miatt az erdőből fákat kell kivágni a távvezeték egyenes vonala alatt. Tudjuk, hogy a távvezeték melyik sorban/oszlopban lép be az erdőbe és melyikben távozik. Valamilyen szakaszrajzoló algoritmus adaptálásával írjon C++ programot, amely a sztandard outputra kiírja, hogy mely sorban és oszlopban lévő fákat kell kivágni. Természetesen, csak minimális számú fát szeretnénk kivágni, ezért egy kivágott fának legfeljebb két, ugyancsak kivágott szomszédja lehet (két fa szomszéd, ha sor és oszlopszámuk külön-külön legfeljebb eggyel térnek el egymástól!
56. Tőzsdeügynöknek csapott fel, és a részvényekről egy nagyon nagy méretű adatbázissal rendelkezik. Egy részvényt a sorszámával, a hozammal (0..1000) és a törzstőkével (0..1000) jellemezhetünk. A kuncsaftok azt a kérdést tehetik fel, hogy melyek azon részvények sorszámai, amelyek hozama az általuk megadott hozamtól legfeljebb 10-zel tér el, ÉS az általuk megadott törzstőkétől ugyancsak legfeljebb 10-zel tér el. Szerencsére még emlékszik a sugárkövetés szabályos rács felosztó eljárására, így tőzsdeügynökként is megállja a helyét. Írjon olyan programot, amely egy előfeldolgozási lépésből és egy lekérdező lépésből áll C++ nyelven. Az előfeldolgozási fázis időbonyolultsága nem érdekes, úgyis csak egyszer kell végrehajtani. Viszont a nagy piaci verseny miatt csak olyan lekérdező lépés engedhető meg, amelynek válaszideje nem nő a részvények számával abban az esetben, ha a részvényadatok valószínűségi eloszlása egyenletes (olyan megoldások, ahol a lekérdezési idő a részvények számával nő, különösen, ha azzal egyenesen arányos, nem értékelhetők ezen a ZH-n sem). A bemeneti adatok a részvények tömbje és száma. A lekérdezési fázis bemenete a kívánt hozam és tőke, a kimenete pedig a kívánalomnak eleget tevő részvények sorszámainak tömbje. A megoldás során a tömbök allokálásával nem kell foglalkozni.
57. A katasztrófa elhárításnál kapott munkát, és éppen a Tisza vízállásjelentését (érték a tengerszinthez képest méterben) hallgatja, ahol gátszakadás történt. Nagyon gyorsan meg kell mondania, hogy milyen területeket fog elönteni a víz. Rendelkezésére áll a körzet digitalizált magasságtérképe (float height[N][M]), ahol minden pixelben a pont tengerszint feletti magassága található. Milyen szerencse, hogy tanulta a számítógépes grafika területelárasztó kitöltő algoritmusát (floodfill), amivel meg tudja oldani a feladatot, és ezért nem kell januártól új állást keresnie! Írjon C++ függvényt, amely a sztenderd kimenetre kiírja azon térkép pixelek koordinátáit, amelyeknek megfelelő pont víz alá fog kerülni. A függvény bemenete a gátszakadás helye ugyanabban a koordinátarendszerben, amelyben a magasságtérképet is kapjuk, és a Tisza vízállása. Feltételezhetjük, hogy a térkép határain biztosan nem terjed tovább az ár, és hogy a Tisza vízszintje állandó.
- 58. Pistike egy labirintusban szeretné megtalálni a kijáratot. Segítsen neki! Tételezze fel, hogy a labirintus térképét Pistike már beszkennelte, és a kapott képet a számítógép memóriájába az unsigned char * terkep címre betöltötte. A kép bináris, egy pixelt egy unsigned char reprezentál, a kép felbontása 400x400, a fekete pixelek (szín = 0) a folyosókat, a fehérek (szín = 1) a falakat jelzik. A bejárat a kép [10,10], a kijárat pedig a [390,390] ponton van. Írjon C programot, amely eldönti, hogy el lehet-e a jutni a bejárattól a kijáratig (a tényleges utat nem kell meghatározni, csak azt, hogy lehetséges-e eljutni a célig) (Ha nincs ötlete, akkor gondoljon a területkitöltő algoritmusokra).*
59. Írjon C++ függvényt, amely egy paraméterként kapott x, y középpontú ellipszist felrajzol. Az ellipszis főtengelyeinek hossza a, illetve b. Az a hosszúságú főtengely a koordinátatengelyekkel alpha szöget zár be. A középpont és a tengelyhossz képernyő koordinátákban (pixel egység) értendők. A rajzoláshoz a glBegin(GL_LINE_STRIP), glVertex2f(xi,yi) és glEnd( ) utasításokat használja! Az ellipszis töredezettségét elkerülendő, egy rajzolt szakasz maximális vízszintes és függőleges mérete a 10 pixelt nem haladhatja meg. A színbeállítással és az ablak megnyitásával nem kell foglalkozni.
60. Írjon görbesimító programot C++-ban OpenGL és GLUT felhasználásával. Az windows ablak háttérszíne kék, felbontását szabadon megválaszthatják. A program egy "pontok.txt" nevű ascii fájlt olvas be, amelynek első sorában egy int van (a pontok száma), amit ennyi sor követ, minden sorban két float számmal, amelyek a pontok x,y világkoordinátáit tartalmazzák. A program ezen csúcspontokra egy zárt töröttvonalat illeszt és egy (0,0),(100,100) sarokpontokkal definiált ablakú kamerával lefényképezi, az eredményt a képernyő windows ablakában megjeleníti. A zárt töröttvonalat fehér színnel kell felrajzolni. Ha a felhasználó a bal egér gombbal ráklikkel a töröttvonalra, a program Catmull-Clark algoritmussal simít egyet a töröttvonalon. Jobb egérklikk pedig csökkenti a simítás mértékét.
61. Írjon görbesimító programot C++-ban OpenGL és GLUT felhasználásával. Az windows ablak háttérszíne kék, felbontását szabadon megválaszthatják. A program egy "pontok.txt" nevű ascii fájlt olvas be, amelynek első sorában egy int van (a pontok száma), amit ennyi sor követ, minden sorban két float számmal, amelyek a pontok x,y világkoordinátáit tartalmazzák. A program ezen csúcspontokra egy zárt töröttvonalat illeszt és egy (0,0),(100,100) sarokpontokkal definiált ablakú kamerával lefényképezi, az eredményt a képernyő windows ablakában megjeleníti. A zárt töröttvonalat fehér színnel kell felrajzolni. Ha a felhasználó a bal egér gombbal ráklikkel a zárt töröttvonal által határolt területre, a program Catmull-Clark algoritmussal simít egyet a töröttvonalon. Jobb egérklikk pedig csökkenti a simítás mértékét. A maximális simítás mértéke legalább 3, azon túl korlátozható. A zárt töröttvonal által határolt terület pontjai azok, amelyekhez a végtelenből érkezve páratlanször lépjük át a töröttvonalat.
62. Írja meg a glutility csomag gluOrtho2D(double Left, double Right, double Bottom, double Top) függvényét. Az implementációban a void glMultMatrixd(const double m[4][4]) függvényt használhatja fel.
- Ezt a függvényt a projekciómátrix beállítására szokták használni, hogy a projekció a [math] Left \leq x \leq Right,\; Bottom \leq y \leq Top,\; -1 \leq z \leq 1 [/math] tartományt transzformálja a [math] -1 \leq x \leq 1,\; -1 \leq y \leq 1,\; -1 \leq z \leq 1 [/math] kockába (megfordítva a koordinátarendszer körüljárását, vagyis pl. a z=1 sík képe a z=-1 lesz). Ezt az alábbi mátrixszal lehet megtenni: [math] \left[\begin{array}{cccc} \frac{2}{Right-Left} & 0 & 0 & 0 \\ 0 & \frac{2}{Top-Bottom} & 0 & 0 \\ 0 & 0 & -1 & 0 \\ -\frac{Right+Left}{Right-Left} & -\frac{Top+Bottom}{Top-Bottom} & 0 & 1 \end{array}\right] [/math] tehát a függvény:
void gluOrtho2D(double Left, double Right, double Bottom, double Top) {
double matrix[16]={2/(Right-Left), 0, 0, 0, \
0, 2/(Top-Bottom), 0, 0, \
0, 0, -1, 0, \
-(Right+Left)/(Right-Left), -(Top+Bottom)/(Top-Bottom), 0, 1};
glMultMatrixd(matrix);
}
63. Írjon C++ függvényt, amely egy zárt sokszögre eldönti, hogy rámutatással kijelöltük-e. Akkor tekintjük a sokszöget kijelöltnek, ha a (x,y) kijelölési pont középpontű, 10 egység oldalhosszúságú téglalap tartalmazza a sokszögből egy részt (ez a rész bármilyen kicsiny lehet, a vizsgálatot tehát nem elég egész koordinátákra elvégezni). A függvény deklarációja:
struct Vertex { float x, y; };
bool Talalat(float x, float y, int n, Vertex * p);
ahol n a csúcspontok száma, p pedig a csúcspontok tömbje.
64. Írjon C++ függvényt, amely egy többszörösen összefüggő sokszöget kitölt (akkor nevezünk egy sokszöget többszörösen összefüggőnek, ha a határát több zárt töröttvonallal lehet megadni). A függvény bemenete az egyes töröttvonalak csúcsszáma, illetve a töröttvonalak csúcspontjai (2 dimenziós tömb). Felételezheti, hogy a művelet előtt az ablakra vágtunk. Az ablak sarokpontjai (0,0), (1000,1000). Egyetlen pixelt a SetPixel(x,y) függvénnyel színezhet át a sokszög színére. Példák kitöltött, többszörösen összefüggő sokszögekre:
-- G - 2008.12.25.
