Institutionen för teknisk databehandling, Bo Nordin (bosse@cb.uu.se, 018-183470), 970111

Tentamen i Datorgrafik MN1/DV1 970113
Examination, Computer Graphics MN1/DV1 970113

Tid och plats: 09.00-14.00, Polacksbacken

Inga hjälpmedel förutom papper, penna, suddgummi och ordböcker tillåtna. Skriv namn på alla papper du lämnar in. Använd ej rödpenna. Skriv endast på ena sidan av varje papper.

För godkänt krävs 18 p, för väl godkänt 28 poäng (av totalt 40). Resultat meddelas via e-post och anslås på TDB senast 970120.

Time and Place: 09.00-14.00, Polacksbacken

Only paper, pen(cil), erasers, and dictionaries allowed. Enter your name on all papers you hand in. Do not use red ink. Write on only one side of each paper.

18 points are required to pass the exam, 28 points are required to pass with distinction ("väl godkänt"). The total number of points is 40. The result will be sent by e-mail and posted at TDB no later than 970120.

1. Datorgrafik vs. bildanalys / Computer Graphics vs. Image Analysis (2p)

Datorgrafik och datoriserad bildanalys är två närbesläktade områden. Beskriv kortfattat relationen mellan dem.

Computer Graphics and Computerized Image Analysis are two related areas. Briefly describe the relation between the two.

2. Om menyinteraktion / About Menu Interaction (3p)

Aktivering (när användaren trycker på File t.ex.) av en pulldownmeny innebär ju bl.a. att visa möjliga val på skärmen. Beskriv kortfattat vilka steg (programmeringsmässigt för den som skriver menysystemet) som behövs för att genomföra interaktionen (att välja ett alternativ). Du kan anta att programmeraren har tillgång till ett system för rastergrafik på ungefär samma nivå som SRGP.

Activating (when the user presses File, for instance) of a pulldown menu involves among other things showing the selections on the screen. Briefly describe the programming steps (when programming the menu system) necessary in order to perform the interaction (which is the selection of one of several choices). You may assume that a raster graphics system such as SRGP is available.

3. Specialprocessorer vs. generella processorer /
Special-purpose vs. general-purpose processors (2p)

System för rastergrafik måste lösa fem deluppgifter: generering av grafikprimitiver, traversering av dessa, transformationer, rastrering (scan conversion) och visning (display). Vilka av dessa uppgifter är lämpliga att lägga i speciella processorer? Hur förändras detta om man inte behöver ändra i modellen interaktivt?

Raster-graphics systems must solve five tasks: generation of graphics primitives, traversal, transformation, scan conversion, and display. Which of these tasks are suitable candidates for hardware implementations? If interactive manipulations of the model are very infrequent, how does this optimal division between general-purpose and special-purpose processors change?

4. Hårdvara / Hardware (0.5 + 0.5 + 0.5 + 0.5 = 2p)

Förklara följande hårdvarubegrepp:

a) uppdateringshastighet

b) efterlysningstid

c) skuggmask

d) skillnaden i positionsbestämning mellan en mus och en digitizer (data tablet).

Explain the following hardware concepts:

a) refresh rate

b) persistence

c) shadow mask

d) the difference in positioning between a mouse a a digitizer (data tablet)

5. 2D-transformationer / 2D Transformations (1+ 3 = 4p)

a) För att rotera en figur i 2D kring en godtycklig punkt måste tre steg genomföras. Vilka?

b) Visa de tre transformationsmatriserna som behövs för att rotera en figur 90 grader medurs kring punkten (3,4). I vilken ordning skall de skrivas för att beräkna den sammanlagda transformationsmatrisen: Ge uttrycket för att transformera punkten (x,y).

a) In order to rotate a 2D figure about an arbitrary point three steps are required. What are they?

b) Show the three transformation matrices used to rotate a figure 90 degrees clockwise about (3,4). In what order must they be written to produce the correct concatenated transformation matrix: give the expression for transformation of (x,y).

6. Färgmodeller / Colour Models (1 + 1 + 2 = 4p )

a) Hur förhåller sig de två färgmodellerna RGB, CMY till varandra?

b) Vad betyder Y i CIE-modellen och YIQ-modellen?

c) Färg anges ofta i RGB-systemet, oftast med åtta bitar per färg. Eftersom många (de flesta) arbetsstationer bara har åtta bitar per visad pixel innebär detta en del problem. Hur löser man detta? Hur många färger kan man visa samtidigt på att åtta-bitars arbetsstation? Varför kan man ändra en färg dynamiskt på en sådan men oftast inte på 24-bits arbetsstationer?

a) How are the two colour models RGB and CMY related?

b) What does Y in the CIE and YIQ models mean?

c) Colour is often described in the RGB model, usually with eight bits per colour. Because many (most) workstations only have eight bits per pixel, this introduces a few problems. How are these problems solved? How many colours can be displayed simultaneously on an eight-bit workstation? Why is it possible to change a colour dynamically on eight-bit workstations, but usually not on 24-bit workstations?

7. Motif (2p)

Ur applikationsprogrammerarens synpunkt, hur förenklar Motif hanterandet av händelser jämfört med att skriva i X utan användande av något toolkit.

From the application programmer's point of view, how does Motif simplify event handling compared to writing in X without using a toolkit.

8. Borttagning av skymda ytor / Visible Surface Determination (1 + 3 = 4p)

I 3D-grafik är skymda ytor någonting som man helst inte vill se på skärmen. Därför finns det en mängd metoder för att ta bort dessa.

a) Innan man använder någon av de mer avancerade algoritmerna kan man göra en del för att minska på arbetet. Beskriv kortfattat vad som menas med bounding-box testing och back-face culling.

b) Warnock använder en divide-and-conquer-strategi för att identifiera skymda ytor. Beskriv hans algoritm.

Hidden-surface elimination is an essential part of any system for 3D graphics. There are many ingenious methods for this.

a) Before using an elaborate algorithm, one can reduce the amount of data that must be sent to it. Briefly describe two of these methods: bounding-box testing and back-face culling.

b) Warnock uses the divide-and-conquer strategy to identify and eliminate hidden surfaces. Describe his algorithm.

9. Att fylla polygoner / Filling Polygons (4p)

Det finns en väl etablerad rasteralgoritm för att fylla en polygon med valfri färg. Beskriv denna algoritm genom att sätta in följande ord i sitt sammanhang: odd-parity rule, horisontella kanter, ET (kanttabell), AET (aktiv kanttabell), bucket sort, hörn som delas av flera kanter.

There exists a well established scan-line algorithm for polygon filling. Describe that algorithm by putting the following words in context: odd-parity rule, horizontal edges, ET (edge table), AET (active edge table), bucket sort, shared vertices

10. 3D-grafik / 3D viewing (2 + 2 + 1 = 5p)

a) För att specififera en 3D-vy används två koordinatsystem: världskoordinater och VRC-systemet. Hur specificeras VRC utifrån världskoordinatsystemet? Hur, och i vilket system, specificeras fönstret?

b) Hur specificeras betraktarens position? I vilket system? Vilken är skillnaden mellan parallellprojektion och perspektivprojektion när det gäller betraktningsposition?

c) Vad behövs mer för att vi skall erhålla en "vy-volym" (view volume)?

a) In order to specify a 3D view, two coordinate systems are used: the world coordinate system and the VRC system. How is the VRC system specified in the world coordinate system? How, and in which system, is the view window specified?

b) How is the view position specified? In which system? What is the difference between parallel and perspective projection with regard to viewing position?

c) What more is needed to produce a view volume?

11. Om fraktaler / About Fractals (1 + 1 + 1 = 3p)

Naturliga objekt (skogar, moln, berg, etc.) låter sig inte beskrivas med metoder som baseras på euklidisk geometri. I stället används t.ex. fraktaler.

a) Vilken är den principiella skillnaden (rent uträkningsmässigt) mellan modellering med geometriska metoder och fraktaler?

b) Ett viktigt begrepp inom fraktalgeometrin är den fraktala dimensionen. Hur definieras denna? Visa gärna med exempel som t.ex. Kochs snöflinga.

c) Naturen är ju inte fullt så deteriministisk som t.ex. Kochs snöflinga. Hur får man bilder generade med fraktaler att se naturliga ut, t.ex. ett blads vener eller ett bergmassivs toppar att variera?

Natural objects (forests, clouds, mountains, etc.) are not easily described with methods based on Euclidean geometry. Instead one can use fractals, for instance.

a) What is the fundamental difference (computationally) between modelling based on geometric methods and modelling with fractals?

b) An important concept in fractal geometry is the fractal dimension. How is it defined? Use illustrations, if you wish (Koch's snowflake can be used to exemplify).

c) Nature, however, isn't quite that deterministic. How are images that are generated with fractals made to look more natural? How are the veins of a leaf or the tops of a mountain range made to vary, for instance?

12. Skuggning / Shading (1 + 2 = 3p)

Skuggning (shading) är ett viktigt inslag för att åstadkomma realistiska bilder. Man kan använda sig av s.k. constant shading eller interpolated shading.

a) Vilken är skillnaden? Under vilka förutsättningar ger constant shading korrekta bilder?

b) Två metoder för interpolerad skuggning är Gouraud shading och Phong shading. Hur fungerar de? Ange speciellt skillnaden mellan dem och tala om hur denna påverkar resultatet.

Shading is important in order to accomplish realistic images. One can use constant shading or interpolated shading.

a) What is the difference? Under what circumstances does constant shading produce correct images?

b) Gouraud shading and Phong shading are two methods for interpolated shading. How do they work? In particular, what is the difference between the two, and how does this difference affect the end result?

13. Rymduppdelningstekniker / Spatial-Partitioning Techniques (2p)

Ett sätt att representera solida kroppar (solids) är rymduppdelning (spatial partitioning).

a) Vilken är skillnaden mellan voxel och cuberille?

b) Beskriv kortfattat principen för octree-representation. En beskrivning av 2D-förenklingen räcker. Använd gärna en figur.

One way of representing solids is spatial partitioning.

a) What is the difference between a voxel and a cuberille?

b) Briefly describe the principle of an octree. A description of the simplified 2D case is sufficient. Use a figure.