Antwoorden tentamen 1 juli 2014.

Tentamen DDM, 1 juli 2014 (eerste vel)
Naam:
Studentnummer:
Lever alleen deze twee vellen in! Andere verkregen blaadjes zijn kladpapier.
Maak de opgaven eerst op kladpapier en zet dan het antwoord op deze vellen.
Formuleer je antwoord altijd zorgvuldig en precies.
Opg. 1
Punten
2
3
4
5
6
7
8
Tot
1
1. (1 punt) Als een curve is opgebouwd uit twee delen en het eerste deel, met parameter
0 tot 1, is kwadratisch, en het tweede deel, met parameter 1 tot 2, is kubisch, wat is
de maximale mate van continu¨ıteit die we kunnen krijgen in het punt met parameterwaarde 1? Leg het antwoord uit.
Als het tweede deel werkelijk kubisch is, en dus een term heeft met u3 , dan zal de
derde afgeleide nooit 0 zijn, maar een vaste, constante waarde hebben onafhankelijk
van u. De tweedegraads functie van het eerste deel zal altijd een derde afgeleide
hebben die 0 is. Het is wel mogelijk dat de functie overeenstemt in functiewaarde,
in afgeleide en in tweede afgeleide bij de overgang met parameterwaarde 1. Dus
maximaal C 2 of G2 .
2. (1 punt) Gegeven een uniforme kwadratische curve f (u) = a0 + a1 · u + a2 · u2 met
co¨effici¨enten a0 = (1, 1), a1 = (2, 4) en a2 = (4, 0). Bepaal drie punten p0 , p1 en p2 die
deze kwadratische curve defini¨eren met f 0 (0) = p0 , f (0.5) = p1 en f (1) = p2 .
p0 = (2, 4), p1 = (3, 3) en p2 = (7, 5).
3. (1.5 punt) Gegeven de volgende vier punten in 2D: (−2, −2), (0, 0), (1, 0), en (1, 2).
Gebruik principale componentenanalyse om de normaal van een lijn ` te vinden die de
goed fit met deze punten. Geef de covariantiematrix, het karakteristieke polynoom, de
eigenwaarden en bijbehorende eigenvectoren, en geef aan welke vector de normaalvector
van de lijn ` is. Je mag eigenwaarden en vectoren afronden op 1 decimaal.
Covariantiematrix:
1
4
6 6
6 8
!
Karakteristiek polynoom: 41 (λ2 − 14λ + 12)
N.B. 41 weglaten (2x) wordt niet fout gerekend.
√
Eigenwaarden en eigenvectoren: 7+/− 37 ≈ 7+/−6.1 = 13.1 of 0.9, met (6 , 7.1)T
en (7.1 , − 6)T als bijbehorende eigenvectoren
Normaalvector van lijn `: Gelijk aan de tweede eigenvector (7.1 , − 6)T .
1
4. (1 punt) Leg het RANSAC algoritme uit als het gebruikt wordt om een vlak te vinden
dat veel punten dichtbij heeft in 3D.
Het RANSAC algoritme kiest vele malen drie punten, construeert dan een vlak van
die drie punten, en test voor all andere punten of ze dicht bij het vlak liggen (typisch
5 centimeter). Het vlak waar het meeste punten bij liggen wordt gerapporteerd.
5. (1 punt) Een kd-boom die een verzameling P met punten in het vlak opslaat kan gebruikt
worden om voor een willekeurig zoekpunt q te bepalen wat het meest dichtbije punt van
P is. Leg duidelijk uit hoe een effici¨ent algoritme hiervoor werkt.
Eerst wordt het blad van de kd-boom gezocht dat een gebied representeert waarin q
ligt. Het punt p van P dat in dat blad is opgeslagen is een kandidaat antwoord, maar
er kan nog een punt dichterbij liggen. Daarom wordt een cirkel zoekactie uitgevoerd
met q als midden en pq als straal. Zodra een punt wordt gevonden dat dichterbij
q ligt kan de straal verkleind worden tot deze nieuwe kleinste afstand, in dezelfde
zoekactie. Het meest dichtbije punt wordt gerapporteerd.
6. (1 punt) Teken een BSP subdivisie voor de driehoeken in de onderstaande figuur en
teken de bijbehorende BSP boom. Er zijn al diverse hulplijnen gestippeld getekend.
Geef de lijnen die je tekent in de figuur een label (A, B, C, ...) en gebruik deze labels
ook in de overeenkomstige knopen in de BSP boom (reserve op achterblad).
verder op tweede vel
2
Tentamen DDM, 1 juli 2014 (tweede vel)
Naam:
Studentnummer:
7. (1.5 punt) De implicit surface reconstruction methode, ofwel de voxel-based method van
Hoppe en collega’s heeft drie fasen waarin een surface (manifold, boundary) uit een
verzameling punten in 3D wordt gereconstrueerd. Geef aan wat deze fasen zijn en wat
het resultaat (het berekende) is na elke fase.
In de eerste fase wordt de normaal van elk punt afgeschat; elk punt heeft dan een
normaalvector.
In de tweede fase worden alle normaalvectoren naar buiten gericht; alle normaalvectoren zijn dan consistent met elkaar.
In de derde fase wordt het surface geconstrueerd met marching cubes, waarbij het
surface gedefinieerd is als de nul-set van de functie die per Voronoi cel de afstand
tot het raakvlak aan het punt in die Voronoi cel is. Het resultaat is een surface.
8. (1 punt) Gegeven het volgende L-systeem:
Symbolen: A, B, S
Start: S
Regels: S → A [+ A S] [− A] B S , A → S
Geef de eerste en tweede generatie behorend bij dit L-systeem in een formule (string
symbolen), en teken deze twee generaties waarbij [ en ] op de gebruikelijke manier een
zijtak aangeven, + rotatie tegen de klok in met 45◦ en − rotatie met de klok mee met
45◦ . De symbolen A, B en S worden hetzelfde getekend namelijk met een lijnstuk van
ongeveer 1 cm. Begin onderaan en teken vertikaal omhoog.
Generatie 1: A [+ A S] [− A] B S
Generatie 2: S [+ S A [+ A S] [− A] B S] [− S] B A [+ A S] [− A] B S
Lever alleen deze twee vellen in (met je naam en studentnummer)!
3
Van vraag 6, reserve figuur voor BSP subdivisie en bijbehorende boom.
4

Download Report