Advanced graphics for avionics displays

Thesis: Advanced graphics for avionics displays

2006-2007

Academiejaar 2006 - 2007 Dep. Toegepaste Ingenieurswetenschappen BME - CTL Schoonmeersstraat 52 - 9000 Gent

Advanced graphics for avionics displays

Eindwerk voorgedragen tot het behalen van het diploma van INDUSTRIEEL INGENIEUR INFORMATICA Philippe VANDEWALLE

Promotoren: Wim Van Den Breen Brecht Baert (Barco Belgium, Kennedypark, 8000 KORTRIJK)

Philippe Vandewalle

pagina - 1 -


2006-2007

Woord Vooraf Als laatstejaarsstudent Industrieel Ingenieur Informatica aan de Hogeschool Gent werd van mij verwacht dat ik een vakoverschrijdend eindwerk leverde, om mijn capaciteiten te bewijzen als informaticus. Ik ging op zoek naar een bedrijf dat voor mij een gepast werk had. Ik streefde ernaar iets te vinden die nauw aansluit met algoritmen in het grafische gebied, omdat dit mij interesseert en een sterke voldoening geeft bij het bereiken van het doel. Ik vond het gepaste eindwerk bij Barco Avionics, Kortrijk. Het werken bij deze groep was een aangename en leerrijke ervaring, die ik in mijn latere carriere zeker zal kunnen gebruiken. Ik zou graag mijn externe begeleider, Brecht Baert, en mijn interne begeleider, Wim Van den Breen, bedanken voor de uitstekende hulp en ondersteuning die ik van hen heb gekregen. Hun ervaring heeft mij geholpen om deze thesis tot een goed einde te brengen.

Philippe Vandewalle

pagina - 2 -


2006-2007

Inhoudsopgave HOOFDSTUK 1: 1.1 1.2

INLEIDING ............................................................................................................... 6

DOELSTELLING ............................................................................................................................... 7 FASERING VAN HET PROJECT........................................................................................................... 8

HOOFDSTUK 2:

CADRG .................................................................................................................... 10

2.1 INLEIDING ..................................................................................................................................... 10 2.2 OMSCHRIJVING ............................................................................................................................. 10 2.3 STRUCTUUR VAN CADRG............................................................................................................ 11 2.3.1 Logische structuur................................................................................................................ 11 2.3.2 Fysische structuur ................................................................................................................ 15 2.4 CADRG INFORMATIE OP HET WEB ............................................................................................... 23 HOOFDSTUK 3:

CADRGREADER.................................................................................................... 24

3.1 DOELSTELLING ............................................................................................................................. 24 3.1.1 Vereisten............................................................................................................................... 24 3.2 ANALYSE ...................................................................................................................................... 26 3.2.1 Skelet van de CadrgReader .................................................................................................. 26 3.2.2 Analyse van de te gebruiken datastructuren bij het initialisatie proces............................... 28 3.2.3 Analyse van de te gebruiken datastructuren bij het verwerken van de aanvragen van een rasterafbeelding. .................................................................................................................................. 31 3.3 REALISATIE ................................................................................................................................... 37 3.3.1 Globale applicatie structuur ................................................................................................ 37 3.3.2 Overzicht van de procedures bij het initialisatieproces. ...................................................... 38 3.3.3 Overzicht van de procedures van objecten bij het verwerken van een aanvraag................. 40 3.3.4 Het opruimen van de gebruikte datastructuren.................................................................... 42 3.4 C-CODE ........................................................................................................................................ 43 3.5 RESULTAAT .................................................................................................................................. 43 HOOFDSTUK 4:

OPENGL .................................................................................................................. 44

4.1 WAT IS OPENGL? ......................................................................................................................... 44 4.2 ARCHITECTUUR ............................................................................................................................ 44 4.2.1 OpenGL implementeert volgende zaken:.............................................................................. 45 4.3 GLUT ........................................................................................................................................... 46 4.3.1 Initialisatie ........................................................................................................................... 46 4.3.2 Callback functies declareren............................................................................................ 47 4.3.3 OpenGL instructies .............................................................................................................. 49 4.4 OPENGL OMGEVING OPZETTEN .................................................................................................... 50 4.5 LINKS ............................................................................................................................................ 51 HOOFDSTUK 5:

CADRGVIEWER.................................................................................................... 52

5.1 DOELSTELLING ............................................................................................................................. 52 5.1.1 Inleiding ............................................................................................................................... 52 5.1.2 Vakjargon en definities......................................................................................................... 52 5.1.3 vereisten ............................................................................................................................... 53 5.2 ANALYSE ...................................................................................................................................... 55 5.2.1 Analyse van een datastructuur voor het bijhouden van de onderlinge positie van de cadrgtiles en de opbouw van het cadrg-field................................................................................................. 55 5.2.2 Analyse van een datastructuur die bijhoud welke tiles reeds zijn geladen........................... 60 Philippe Vandewalle

pagina - 3 -


2006-2007

5.3 REALISATIE ................................................................................................................................... 64 5.3.1 Renderen van het CadrgField. ............................................................................................. 65 5.3.2 Updaten van het CadrgField................................................................................................ 66 5.4 RESULTAAT ................................................................................................................................... 71 HOOFDSTUK 6:

DTED ........................................................................................................................ 72

6.1 INLEIDING ..................................................................................................................................... 72 6.2 OMSCHRIJVING ............................................................................................................................. 72 6.3 STRUCTUUR VAN DTED ................................................................................................................. 73 6.3.1 Logische structuur................................................................................................................ 73 6.3.2 Fysische structuur ................................................................................................................ 74 6.4 LINKS ............................................................................................................................................ 76 HOOFDSTUK 7:

DTEDREADER ....................................................................................................... 77

7.1 DOELSTELLING ............................................................................................................................. 77 7.1.1 Inleiding ............................................................................................................................... 77 7.1.2 Vereisten............................................................................................................................... 77 7.2 ANALYSE ...................................................................................................................................... 78 7.2.1 Skelet van de DtedReader .................................................................................................... 78 7.2.2 Analyse van de te gebruiken datastructuren bij het initialisatie proces............................... 80 7.2.3 Analyse van de te gebruiken datastructuren bij het verwerken van de aanvragen van een dted-tile. 85 7.2.4 het beëindigen ...................................................................................................................... 86 7.3 REALISATIE ................................................................................................................................... 87 7.3.1 DTEDreader object .............................................................................................................. 87 7.3.2 DTED_List object................................................................................................................. 87 7.3.3 het DTED_TOC object. ........................................................................................................ 88 7.3.4 Het DTEDtile object............................................................................................................. 88 7.3.5 BMP.H.................................................................................................................................. 88 7.4 RESULTAAT .................................................................................................................................. 89 HOOFDSTUK 8:

DIGIMAP................................................................................................................. 90

8.1 DOELSTELLING ............................................................................................................................. 90 8.1.1 Inleiding ............................................................................................................................... 90 8.1.2 vereisten ............................................................................................................................... 90 8.2 ANALYSE ...................................................................................................................................... 91 8.2.1 Gelaagd ontwerp.................................................................................................................. 91 8.2.2 Digimap onafhankelijk van gebruikte dataset...................................................................... 92 8.2.3 een algemeen Tile-object...................................................................................................... 92 8.2.4 het digimap object ................................................................................................................ 93 8.3 REALISATIE ................................................................................................................................... 94 8.3.1 Renderen van het textureField. ............................................................................................ 95 8.4 RESULTAAT ................................................................................................................................... 97

Philippe Vandewalle

pagina - 4 -


2006-2007

Verklarende Woordenlijst Display

Het scherm van de piloot die de digital map toont

CADRG

Compressed ARC Digitised Raster Graphics. Rasterbeelden met bijhorende informatie. Voor grote schalen zijn dit in gescande kaarten. Voor kleine schalen kunnen dit satellietfoto’s zijn.

DTED

Digital Terrain Elevation Data: hoogteinformatie per geografische locatie. De hoogte is gegeven in meter ten opzichte van zeeniveau

View

Het zichtbare gedeelte van het landschap.

Range

De breedte van het landschap dat zichtbaar moet zijn in de applicatie

Tile

Een entiteit waaruit het geheel beeld is opgebouwd

Zone

Een gebied waarbij het interval per pixel of waarde gelijk is. Door verschillende zones in te voeren, kan men de bolvorm van de aarde op een raster voorstellen.

Coverage

Een verzameling van parameters die de geografische locatie en bedekking van een gebied bepalen.

MSL

Afkorting voor Mean Sea Level. Dit is het uitgemiddelde zeeniveau over de getijden (eb en vloed) heen.

Elevatie

Een waarde in meter die de hoogte van een bepaald punt bepaald tegenover MSL

CadrgField

Geografisch: het gebied dat kan bedekt worden door de geladen CadrgTiles logisch: De boomstructuur van geladen CadrgTiles die wordt geladen om het beeld te renderen.

CadrgField- De diagonaal van een cirkel die een gebied omschrijft waarbinnen radius we elk gebied proberen te bedekken door extra Tiles te laden.

Philippe Vandewalle

pagina - 5 -


Hoofdstuk 1:

2006-2007

Inleiding

Avionics displays spelen een belangrijke rol in de veiligheid van een vliegtuig. Zij verstrekken informatie aan de piloot omtrent het vliegtuig en de omgeving. Deze thesis zal zich concentreren op het definiëren en ontwerpen van de functies voor dergelijke Avionic displays, meer bepaald voor de mapping display. De mapping display houd zich bezig met het samenstellen van een synthetic ground map van de omgeving die zich onder het vliegtuig bevindt. Een synthetic ground map is een kunstmatig beeld gecreëerd met behulp van kaarten, plannen, plattegrond-afbeeldingsdatabank, hoogte-informatie per locatie om 3D-beeld te genereren (bergen, valleien,…),… De synthetic ground map bevat informatie over het oppervlak onder het vliegtuig, met informatie zoals: • • • •

de hoogte van het oppervlak(ten opzichte van het zeeniveau) aard van het oppervlak (water, land, bos, rotsen) militaire zones, verboden zones,… vliegtorens, hoogspanningsleidingen, luchthavens

Onderstaande afbeelding toont een synthetic ground map, op een mapping display, samengesteld uit 4 verschillende datasets.

Dergelijke systemen bestaan reeds, vaak in 2D of in 3D. Echter met een schokkend (haperend) beeld bij het vernieuwen van het scherm. Dit vooral wanneer er wordt verder gevlogen, en een nieuwe sectie dient te worden geladen. De permanente gegevensopslag gebeurt op flashgeheugen omdat dit schokvast is. Maar de bus die toegang biedt hiertoe vormt een bottle-neck. Om deze zo weinig mogelijk te belasten, zouden atomaire rasterafbeeldingen efficiënter moeten worden geladen en hergebruikt. Door ze in een gepaste gegevensstructuur in het geheugen te bewaren zouden ze dan geen tweede keer moeten worden gelezen, bij het genereren van een volgende view. Philippe Vandewalle

pagina - 6 -


2006-2007

1.1 DOELSTELLING De bedoeling van deze thesis is om de algoritmen te ontwikkelen die het mogelijk moeten maken om de synthetic groundmap te construeren ( Advanced graphics for avionics displays). Deze algoritmen zullen aspecten omvatten zoals: •

Het bepalen van de te laden atomaire afbeeldingen (afhankelijk van de locatie)

•

Decomprimeren en laden van de atomaire afbeeldingen.

•

Het gestructureerd bijhouden van deze afbeeldingen om ze later te kunnen hergebruiken bij het samenstellen van de verschillende views.

•

Het laden van de oppervlakte informatie van een locatie.

•

De verschillende layers samenvoegen tot een passende view.

Het ophalen, inlezen en decomprimeren van de data gebeurt in de programeer taal C, omdat deze later gemakkelijk overdraagbaar zijn naar het embedded systeem van het vliegtuig. Het genereren van de textures en later mappen van deze textures op een 3D-beeld zal gebeuren met behulp van de OpenGL standard graphics librairy. Uiteindelijk is het de bedoeling om aan de hand van terreinbeschrijvende datasets zoals CADRG en DTED een synthetisch beeld te kunnen genereren. CADRG1 (Compressed ARC Digitized Raster Graphics) is een zelfbeschrijvende directorystructuur die rasterafbeeldingen bijhoudt. Deze directorystructuur wordt in de root directory beschreven door een “Table Of Contents” file. Deze is ingedeeld in zones, breedtegraden, schaalbibliotheken en beschrijft waar welke file te vinden is in de subdirectories. Na decompressie (vectorcompressie) bekomt men dan een bitmap voor de gegeven locatie. Deze zal dan dienen als texture om de synthetic groundmap te genereren. DTED2 (Digital Terrain Elevation Data) is ook een zelfbeschrijvende directorystructuur zoals hierboven. Maar deze houd voor elk gebied bij wat de gemiddelde elevatie is tegenover zee niveau, het hoogste punt, en het laagste punt. De grootte van een geschreven gebied is afhankelijk van de schaal bibliotheek Omdat de te gebruiken datasets CADRG en DTED essentieel zijn in deze thesis, wordt aan elk van hen een apart hoofdstuk besteedt. “Hoofdstuk 2: CADRG” voor CADRG en “Hoofdstuk 6: DTED” voor DTED.

1

Amerikaans Militaire standaard: MIL-STD-2411

2

Amerikaans Militaire standaard: MIL-STD-2525

Philippe Vandewalle

pagina - 7 -


2006-2007

1.2 FASERING VAN HET PROJECT. We moeten dus een synthetic groundmap kunnen weergeven gebaseerd op CADRG en DTED. We zullen daarom eerst een groundmap proberen te construeren enkel op basis van CADRG. Wanneer deze klaar is, zullen we pas daarna het DTED gedeelte eraan toevoegen. De thesis zal bijgevolg uit volgende fases bestaan: • Fase 1: ontwerpen van een CadrgReader. • Fase 2: ontwerpen van een CadrgViewer. • Fase 3: ontwerpen van een DtedReader. • Fase 4: ontwerpen van een DtedViewer. • Fase 5: de CADRG~ en DTED layer assembleren. De eerste fase zal dus bestaan uit het maken van een CadrgReader. Wat CADRG is en hoe deze is geordend, vindt men terug in “Hoofdstuk 2: CADRG”. De CadrgReader zal dan voor een gegeven locatie een atomaire afbeelding lokaliseren in de CADRG database, deze decomprimeren en laden. Om te kunnen testen of de geladen afbeelding overeen komt met de aangevraagde locatie en er zich geen onregelmatigheden voordoen in de rasterafbeelding, zullen we de bekomen RGB-data opslaan in een bitmap bestand. Voor deze bestanden zijn trouwens voldoende viewers beschikbaar. De analyse en het ontwerp van de CadrgReader is terug te vinden in “Hoofdstuk 3: CadrgReader”. CADRG

CadrgReader

testBitmap

In een volgende fase zullen we een CadrgViewer maken. De CadrgViewer is een soort browser om door een CADRG database te bladeren. De CadrgViewer delegeert het laden van de atomaire afbeeldingen aan de CadrgReader. De CadrgViewer voorziet in het beheer van de atomaire afbeeldingen en bepaald voor welke geografische locaties er afbeeldingen moeten worden geladen. De CadrgViewer zorgt er voor dat er voldoende atomaire afbeeldingen geladen zijn zodat er een geheel beeld kan worden geconstrueerd. Bij een flight-over, zal de View periodiek moeten heropgebouwd worden, maar het nieuwe beeld zal grotendeels hetzelfde zijn als het vorige. Bijgevolg zullen dezelfde atomaire afbeeldingen vaak hergebruikt kunnen worden. De CadrgViewer zal daarom ook een structuur moeten bijhouden die deze atomaire afbeeldingen bijhoud. Het uiteindelijke resultaat, de groundmap enkel op basis van CADRG, zal dan op het scherm worden gevisualiseerd met behulp van OpenGL. “Hoofdstuk 4 OpenGL”, geeft een omschrijving van OpenGL en verteld hoe men de omgeving moet instellen om met OpenGL-applicaties te kunnen werken en/of ze te ontwikkelen. De analyse en het ontwerp van de CadrgViewer is terug te vinden in “Hoofdstuk 5: CadrgViewer”. CadrgViewer View CadrgReader

CADRG

Philippe Vandewalle

pagina - 8 -


2006-2007

In de derde fase zullen we een DtedReader ontwerpen. “Hoofdstuk 6: DTED”, geeft uitleg over de Data Terrain Elevation Data. En naar analogie met de CadrgReader, zal “Hoofdstuk 7: DtedReader”, terug de analyse en het ontwerp van de DtedReader bevatten. De DtedReader zal voor de gevraagde geografische locaties de hoogte-informatie voor een bepaald gebied laden. Om dit te kunnen testen, zullen we terug de bekomen data in een bitmap bestand opslaan. Hierbij zullen we ervoor zorgen dat elke pixel een kleur krijgt afhankelijk van de hoogte. Rood staat voor het hoogste gebied. Groen voor het laagste.

DTED

DtedReader

testBitmap

In de vierde fase zullen we de Digimap ontwerpen. Deze zal naar analogie met de CadrgVieuwer ervoor zorgen dat er genoeg locaties geladen zijn zodat de volledig vieuw kan worden bedekt. Met deze informatie zal dan een 3Dbeeld worden gegenereerd met behulp van OpenGL. Het beeld zal bestaan uit een mesh met de DTED elevatie’s als bron. De triangulatie-driehoeken worden dan gevuld met de CADRG-textures om een realistischer beeld te krijgen. Het ontwerp en de realisatie van de Digimap zijn terug te vinden in “Hoofdstuk 8: Digimap”. DIGIMAP CADRG

CadrgReader Vieuw

DTED

Philippe Vandewalle

DtedReader

pagina - 9 -


Hoofdstuk 2:

2006-2007

CADRG

2.1 INLEIDING Bij dit eindwerk zal een groot deel van de inputdata bestaan uit CADRG data. Om de werking en structuur van de CadrgReader (zie volgend hoofdstuk) te kunnen begrijpen, volgt eerst een toelichting over CADRG.

2.2 OMSCHRIJVING CADRG1 (Compressed ARC Digitized Raster Graphics) is een militair data formaat voor het bewaren van digitale kaarten en foto’s. Het is een verzameling van digitale rasterafbeeldingen afkomstig van ingescande kaarten. Na het inscannen worden de afbeeldingen gefilterd op storingen in het originele formaat. Ook vindt herformattering plaats volgens het RPF2 formaat. RPF of Raster Product Format is eveneens een militaire standaard, waar CADRG deel van uitmaakt. RPF is een Voorbeeld van een CADRG afbeelding standaard voor geografische databases. Deze standaard beschrijft hoe de tabellen van pixels van afbeeldingen en geografische referenties worden geordend en gegroepeerd, om zo de uitwisseling van raster data tussen producenten en gebruikers te standaardiseren. Om de CADRG data compact te maken, wordt deze ook gecomprimeerd. De compressiemethode is vectorcompressie. Deze methode is traag bij het comprimeren. Het opmaken van CADRG databases vergt veel werk, en worden dan ook door gespecialiseerde firma’s gedaan. Het decomprimeren gaat dan weer zeer snel (ongeveer 10 keren sneller dan JPEG!). De data wordt immers zeer vaak geraadpleegd(= decompressie ), terwijl ze maar 1 keer moet worden aangemaakt (= compressie ). CADRG werd ook ontworpen op een manier om aan databasepaginering te kunnen doen. Het is dus niet nodig om de gehele database te laden wanneer men enkel kaartgegevens nodig heeft van een bepaald gebied. Wanneer men

1

http://www.nima.mil/ast/fm/acq/MIL-PRF-89038%20CADRG.pdf

2

http://earth-info.nga.mil/publications/specs/printed/2411/2411_RPF.pdf

Philippe Vandewalle

pagina - 10 -


2006-2007

over een gebied vliegt, worden de desbetreffende “pagina’s” geladen en wordt de kaart afgebeeld, gebaseerd op de positie waar men zich bevindt.

2.3 STRUCTUUR VAN CADRG 2.3.1 LOGISCHE STRUCTUUR De CADRG database bevat rasterafbeeldingen voor een bepaald gebied. Bijvoorbeeld voor Europa, Noord Amerika of Azië,… Het is niet gebruikelijk om data die geheel de wereld omvat in één CADRG database te omvatten omdat deze te groot zou zijn. Wil men dus geheel de wereld kunnen tonen, dan zal men over meerdere databases moeten beschikken. Hierbij dient hun bedekking elkaar aan te vullen. In dit eindwerk zullen de functies trouwens met meerder CADRG databases dienen te kunnen werken. Zo zal men bij het opvragen van een afbeelding voor een bepaalde locatie eerst moeten bepalen in welke database deze is gelegen.

CADRG database:

TOC bestand

Scale librairy 1:1M

Scale librairy 1:500K

Zone 4 (56°N 64°N)

Zone 3 (48°N 56°N)

Zone 3 (48°N 56°N)

Zone 2 (32°N 48°N)

Zone 2 (32°N 48°N)

Zone 1 (00°N 32°N)

Zone 1 (00°N 32°N)

Zone A (00°Z 32°Z)

…

…

De CADRG database kan men hiërarchisch indelen. Waarbij op elk niveau volgens een ander criterium wordt ingedeeld. Onderstaande figuur toont de indeling per niveau. Volgorde van de niveaus: Database | Schaal | Zone | Frame | Subframe(of tile)

RPF(CADRG)

Database 1:500K

Schaal Zone

1

…

2

…

3

…

… 4

…

5

…

1:1M

… A

…

1

…

2

…

3

4

…

Frame Subframes of tiles genaamd

Philippe Vandewalle

…

…

pagina - 11 -

…


2006-2007

Het TOC bestand verschaft informatie over de inhoud van de database. 2.3.1.1 SCHAAL Binnen één voorkomen. • ARC1 • ARC2

CADRG database kunnen meerdere schalen (scale librairies) Volgende schalen zijn relevant voor avionics: 1:1 000 000 Operational Navigational Chart (1:1M) 1: 500 000 Tactical Pilotage Chart (1:500K)

Een eerste indeling kan dus gebeuren op niveau van schaal. 2.3.1.2 ZONES (ARC SYSTEEM) Binnen iedere schaal bibliotheek verdeelt het ARC1 systeem de aardellipsoïde in 18 zones volgens breedtegraad. Dit is nodig om de vervorming door projectie van een ronde wereldbol op een 2D-vlak weg te werken. Indien dit niet zou gebeuren, dan zou de horizontale geografische resolutie (graden per pixel), continu variëren van de evenaar tot de polen. Zie onderstaande figuur.

Zone 3 Zone 2 Zone 1 ARC systeem

Het ARC systeem maakt het dus mogelijk om de rasterafbeeldingen als rechthoeken af te beelden zonder bolvervorming. Bij de aanmaak van de CADRG database is het dus nodig om een lijn bovenaan in een bepaalde zone over meer pixels te interpoleren dan een lijn onderaan in die zone. Binnen iedere zone is de horizontale geografische resolutie dan constant. De Breedtegraden die de zones begrenzen zijn terug te vinden in onderstaande tabel Noordelijke hemisfeer

1

Zuidelijke hemisfeer

Zone

Breedtegraad

Zone

Breedtegraad

9 8

80° - 90° 76° - 80°

A B

0° - 32° 32° - 48°

7 6

72° – 76° 68° – 72°

C D

48° – 56° 56° – 64°

5 4

64° – 68° 56° – 64°

E F

64° – 68° 68° – 72°

3 2

48° – 56° 32° - 48°

G H

72° – 76° 76° - 80°

1

0° - 32°

I

80° - 90°

ARC (equal Arc second Raster Chart)

Philippe Vandewalle

pagina - 12 -


2006-2007

2.3.1.3 FRAMES Elke zone bestaat op zijn beurt uit een rechthoekig rooster van frames (zie onderstaand figuur). Binnen een zone zijn de frames aaneengesloten. De frames kunnen de grenzen van de zone overschrijden, om zo een volledig frame te bekomen. Zone 4

Zone 3

Rooster van frames. Ieder vierkant vertegenwoordigt een framefile die op zijn beurt bestaat uit 36 subframes of tiles

Zone 2 Een frame bestaat uit: • een coverage • 6 x 6 imagedata • een decompressietabellen • een kleurentabel Coverage Dit is een verzameling geografische coördinaten, die de corresponderende plaats van de rasterafbeelding op de aarde eenduidig specificeert. Deze bevat volgende gegevens: •

NW lengte~/breedtegraad van linker bovenhoek

•

NO lengte~/breedtegraad van rechter bovenhoek

•

ZW lengte~/breedtegraad van linker onderhoek

•

ZO lengte~/breedtegraad van rechter onderhoek

•

horizontale resolutie

•

verticale resolutie

•

Schaal

•

Zone

Philippe Vandewalle

pagina - 13 -


2006-2007

6 x 6 imagedata Een frame bestaat op zijn beurt uit 36 tiles. Dit zijn elementaire stukjes rasterafbeelding van 256 x 256 pixels. De tiles zijn geordend in een 6*6 matrix. 0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

256 pixels

1536 pixels 18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

Iedere tile kan apart gedecomprimeerd worden. Hierdoor kan men sneller een relevant beeld weergeven zonder veel overhead te moeten verwerken. De tile data bestaat uit een 64 x 64 matrix van 12bits die dan wordt gedecomprimeerd tot een 256 x 256 rasterafbeelding. decompressietabellen Deze zijn voor ieder frame anders en bevatten een soort vector code boek. Voor iedere groep van 12 pixels uit de imagedata bestaat dan een ingang die verdere decompressie mogelijk maakt. (Uitwerking van de decompressietechniek volgt in volgend hoofdstuk: CadrgReader) Kleurentabel Net zoals dit bij een bitmap mogelijk is, wordt het kleur bijgehouden in een tabel met kleurindexen. Voor CADRG kunnen kleurentabellen bestaan met een grootte van 16, 32 of 216 ingangen (meestal 216). Kleurentabellen met 24(16) of 25(32) ingangen, worden meestal gebruikt voor zwart-wit of monochrome kaarten.

Philippe Vandewalle

pagina - 14 -


2006-2007

2.3.2 FYSISCHE STRUCTUUR Voor de verwerking van de CADRG data is vooral de fysische structuur van belang. Een CADRG database gedraagt zich niet als één bestand die een speciale interne structuur bevat, maar als een hiërarchische directory structuur. Binnen deze directory structuur bevinden zich dan bepaalde bestanden die een belangrijke sleutelrol spelen in de beschrijving en ordening van de database. 2.3.2.1 DIRECTORY STRUCTUUR Omdat CADRG deel uitmaakt van de RPF (Raster Product Format) familie, is de naam van de root directory van de CADRG database, de RPF directory Onderstaande figuur toont een voorbeeld van de directory structuur van een CADRG database

…

… Binnen de root directory is het A.TOC bestand, het belangrijkste bestand. Dit bestand is een soort inhoudsopgave van de gehele CADRG database. De extensie *.TOC, is trouwens een afkorting voor “Table Of Contents”. Het A.TOC bestand bevat voor iedere geografische locatie die de database omvat, een verwijzing naar de corresponderende framefile dieper in de structuur. Indien aanwezig bevat dit bestand ook een verwijzing naar een “overview” bestand. Dit is een bestand met een rasterafbeelding van een kaart van het gebied die de database omvat. In deze database (zie bovenstaande figuur) is 000ONC05.OVR zo een bestand. Overview bestanden zullen minder relevant zijn in deze thesis omdat we voor een gegeven locatie data willen ophalen. Indien deze locatie niet wordt bedekt in de database zal dit wel gemerkt worden in het A.TOC bestand indien er geen verwijzing naar een bestand bestaat voor deze locatie. De directory indeling gebeurt op basis van de logische structuur (zie 2.3.1 Logische structuur) Eerst wordt een indeling gemaakt op basis van de schaal. Indien de database data bevat voor verschillende schalen, dan worden hiervoor aparte directories gemaakt. Door inlezen van het A.TOC bestand kunnen we weten dat de database de schalen 1:1M en 1:500K bevat. De directory naam Philippe Vandewalle

pagina - 15 -


2006-2007

“CTPC”, afgeleid van “Collection Tactical Pilotage Charts”, zal de beelden bevatten met de 1:500K schaal (zie puntje “2.3.1.1 Schaal”). CONC (Collection Operational Navigational Charts) zal de schaalbibliotheek 1:1M bevatten. Binnen elk van deze directories wordt verder opgesplitst per zone. (zie 2.3.1.2 Zones, ARC systeem). Voor iedere zone wordt een aparte sub directory aangemaakt. De zone kan men trouwens afleiden uit de laatste 2 karakters van de directory naam. Zie figuur links. Deze database bevat dus 5 zones voor dit gebied met een bepaalde schaal. Binnen elke zone directory bevinden zich dan de framefiles voor deze zone. Zie onderstaande figuur. De extensie van de framefiles is telkens de tweede en derde letter van de bovenliggende directories met als laatste karakter de zone. Dit ter controle. Verder heeft de bestandsnaam niets te maken met de geografische locatie. Het mappen van de geografische locatie en de bestandsnaam gebeurt trouwens in het A.TOC bestand. Al deze framefiles kunnen samen dan een aanéén gesloten rasterafbeelding …

… vormen voor deze zone. Elk van deze framefiles bevatten terug 6 x 6 tiles van elk 256 x 256 pixels. Deze tiles kunnen afzonderlijk worden gedecomprimeerd. Een framefile kan dus een afbeelding bevatten van 1536 x 1536 pixels. Toch varieert de bestandgrootte maar tussen de 287kb en 290kb! Indien we snel een rekensom maken van 1536 pixels x 1536 pixels met 216 mogelijke verschillende kleuren per pixel (=8bits of 1 byte nodig per pixel). Dan komen we op 2 359 296 byte of 2,3 Mbyte nodig per framefile. Dit terwijl een framefile slecht 290 kbyte groot is. We zien hier dat de vectorcompressie (zie volgend hoofdstuk) zeer efficiënt is.

Philippe Vandewalle

pagina - 16 -


2006-2007

2.3.2.2 BESTANDSSTRUCTUUR VAN EEN *.TOC BESTAND Om de CADRG data te kunnen benutten moeten we eerst weten hoe die is samengesteld en wat ze bevat. Daarom moeten we eerst het “Table of Contents” bestand inlezen en interpreteren. De algemene structuur van een table of contents bestand is de volgende: • Een header sectie: Deze sectie zal het bestand identificeren. • Een locatie sectie: Deze sectie toont de begin byte locatie van de verschillende secties. De eigenlijk byte offset van de verschillende secties ten opzichte van het begin van het bestand. Hierdoor kan de programmeur de verschillende secties inlezen en interpreteren. • Een grens rechthoek sectie: Deze sectie zal de grenzen van één of meerdere grensrechthoeken bevatten. Dit zijn rechthoeken waarvoor een verzameling van aan één sluitende frames bestaat. Hiervan wordt hun geografische locatie, zone, schaal, aantal frames horizontaal, aantal frames verticaal en resolutie bijgehouden. • Een framefile index sectie: In deze sectie vindt de eigenlijke mapping van de framefiles met hun geografische coördinaten en hun bestandsnaam plaats. Dit zijn de eigenlijke records van het bestand. Bestandsindeling en grootte in bytes Veld Header sectie Little/big endian indicator(ff=little~/00=big endian) Header sectie length File name Update indicator Governing standard number Governing standard date Security classification Security country code Security release marking Location section location Locatie sectie Location section length Component location table offset Number of component location records Component location record length Component aggregate length [component location record] minimum 2 Component id Component length Component location

Philippe Vandewalle

Type

Aantal bytes

Bool Uint Asci Byte Asci Asci Asci Asci Asci Uint

1 2 12 1 15 8 1 2 2 4

48

14 + nrec x 10 Uint Uint Uint Uint Uint Uint Uint Uint

2 4 2 2 4 10 2 4 4

pagina - 17 -


Veld Grens rechthoek sectie [Grens rechthoek sectie subheader] Grens rechthoek table offset Number of grensrechthoek records Grens rechthoek record length [Grens rechthoek subsectie] [Grens rechthoek record] Product data type Compression ratio Scale Zone Producer Northwest latitude Northwest longitude Southwest latitude Southwest longitude Norhteast latitude Norhteast longitude Southeast latitude Southeast longitude Vertical resolution Horizontal resolution Vertical interval Horizontal interval Number of vertical frames Number of horizontal frames Framefile index sectie [Framefile index section subheader] Highest security classification Framefile index table offset Number of framefile index records Number of pathname records Framefile index record length [Framefile index subsection] [Framefile index table] [index record] Grensrechthoek record number Frame location row number Frame location column number Pathname record offset Framefile name Geographic location Framefile security classification Framefile security country Framefile security release [Pathnametable] [pathname record] Pathname length Pathname

Philippe Vandewalle

2006-2007

Type

Aantal bytes 8

Uint Uint Uint

4 2 2

Asci Asci Asci Asci Asci Real Real Real Real Real Real Real Real Real Real Real Real Uint Uint

132 5 5 12 1 5 8 8 8 8 8 8 8 8 8 8 8 8 4 4

Asci Uint Uint Uint Uint

1 4 4 2 2

Uint Uint Uint Uint Asci Asci Asci Asci Asci

2 2 2 4 12 6 1 2 2

nrec x 132

13

33

var Uint Asci

2 var

pagina - 18 -


2006-2007

2.3.2.3 BESTANDSSTRUCTUUR VAN EEN FRAMEFILE. Om een rasterafbeelding voor een gegeven locatie uit een framefile te halen en te decomprimeren, moeten we eerst deze framefile parsen. Kennis van de bestandsindeling van dit bestand is dan ook vereist. De structuur van een framefile kan zoals bij een table of contents bestand worden onderverdeeld in secties. • Header sectie: identificeert terug het bestand. •

Location sectie: bevat de byte offset van de verschillende secties zodat bij het programmeren naar de verschillende secties kan worden gesprongen.

•

Coverage sectie : Deze sectie definieert de geografische omvang van de framefile.

•

Compression sectie: voorziet in tabellen met pixel vector codeboeken die nodig zijn om de gecomprimeerde rasterafbeeldingen te decoderen.

•

Color/grayscale sectie: De color/grayscale sectie bevat de 216 RGB waarden voor de kleurentabel.

•

Image sectie: deze bevat de gecomprimeerde data van de 36 tiles. Dit zijn eigenlijk pointers naar vector codeboeken.

Bestandsindeling en grootte in bytes Veld Header sectie Little/big endian indicator(ff=little~/00=big endian) Header sectie length File name Update indicator Governing standard number Governing standard date Security classification Security country code Security release marking Location section location Location sectie Location section length Component location table offset Number of component location records Component location record length Component aggregate length [component location record] minimum 2 Component id Component length Component location

Philippe Vandewalle

Type

Aantal bytes 48

Bool Uint Asci Byte Asci Asci Asci Asci Asci Uint

Uint Uint Uint Uint Uint Uint Uint Uint

1 2 12 1 15 8 1 2 2 4 14 + nrec x 10 2 4 2 2 4 10 2 4 4

pagina - 19 -


Veld Coverage sectie [Coverage sectie subheader] Northwest latitude Northwest longitude Southwest latitude Southwest longitude Norhteast latitude Norhteast longitude Southeast latitude Southeast longitude Vertical resolution Horizontal resolution Vertical interval Horizontal interval Compression sectie [Compression sectie subheader] Compression algorithm id Number of compression lookup offset recs Number of compression param offset recs [Compression lookup subsection] Compression lookup offset table offset Compression lookup table record length [Compression lookup offset table] [Compression lookup offset record] Compression lookup table id Number of compression lookup records Number of values per compr. lookup rec Compression lookup value bit Compression lookup table offset [Compression lookup table] [Comprssion lookup record] Compression lookup value [Compression parameter subsection] Compression param. offset table offset Compression param. Offset record length [Compression param. Offset table] [Compression param. Offset record] Compression param. Id Compression param. Record [Compression param. Record] Compression parameter value

Philippe Vandewalle

2006-2007

Type

Aantal bytes 96

Real Real Real Real Real Real Real Real Real Real Real Real

8 8 8 8 8 8 8 8 8 8 8 8

Uint Uint Uint

2 2 2

Uint Uint

4 2

Uint Uint Uint Uint Uint

2 4 2 2 4

Bits

var

Uint Uint

4 2

Uint Uint

2 4

Byte

var

6

14

var

6

pagina - 20 -


Veld Color/grayscale sectie [color/grayscale sectie subheader] Number of color/grayscale offset records Number of color converter offset record External color/grayscale file name [Colormap subsection] Colormap offset table offset color/grayscale offset record length [colormap offset table] [color/grayscale offset record] color/grayscale table id Number of color/grayscale record color/grayscale element length Histogram record length color/grayscale table offset Histogram table offset [color/grayscale element group] [color/grayscale table] [color/grayscale record] color/grayscale element [histogram element group] [histogram table] [histogram record] Histogram element [Color converter subsection] Color converter offset table offset Color converter offset record length Color converter record length [Color converter offset table] [color converter offset record] Color converter table id Number of color converter records Color converter table offset Source color/grayscale offset table Target color/grayscale table entry num [color converter table] [color converter record] Target color/grayscale table entry num

Philippe Vandewalle

2006-2007

Type

Aantal bytes 14

Uint Uint Asci

1 1 12

Uint Uint

4 2 17

Uint Uint Uint Uint Uint Uint

2 4 1 2 4 4

Byte

Var

Uint

4

Uint Uint Uint

4 2 2

Uint Uint Uint Uint Uint

2 4 4 4 4

Uint

4

18

4

pagina - 21 -


Veld Image sectie [image description subheader] Number of spectral groups Number of subframe tables Number of spectral band tables Number of spec. band lines per image row Number of subframes in left-right dir Number of subframes in up-down dir Number of output cols per subframe Number of output rows per subframe Subframe mask table offset Transparancy mask table offset [Mask subsection] [mask subheader] Subframe sequence record length Transparancy sequence record length Transparancy output pixel code lenth Transparancy output pixel code value [Subframe mask table] [Subframe mask spectral group] [Subframe mask row] [Subframe sequence record] Subframe offset [Transparency mask table] [Transparency mask spectral group] [Transparency mask row] [Transparency sequence record Subframe offset [image display parameters subheader] Number of image rows Number of image codes per row Image code bit length [Spatial data subheader] [spectral group] [subframe table] [Spectral band table] [Image row] [Spectral band line] Image code

Philippe Vandewalle

2006-2007

Type

Aantal bytes

Uint Uint Uint Uint Uint Uint Uint Uint Uint Uint

2 2 2 2 2 2 4 4 4 4

Uint Uint Uint Bits

2 2 2 Var

Uint

4

Uint

4

Uint Uint Uint

4 4 1

Bits

var

pagina - 22 -


2006-2007

2.4 CADRG INFORMATIE OP HET WEB http://cadrg.com Homepagina van CADRG. Hoofdzakelijk informatie over de productie van CADRG databases en de technieken die daarvoor worden gebruikt.

http://www.aeroplanner.com/cadrg Site waar men CADRG data kan downloaden in beperkte mate.

http://www.nga.mil/ast/fm/acq/MIL-PRF-89038%20CADRG.pdf Document met de militaire specificaties over CADRG.

http://earth-info.nga.mil/publications/specs/printed/2411/2411_RPF.pdf Document met de militaire specificaties van RPF, waar CADRG deel van uitmaakt.

Philippe Vandewalle

pagina - 23 -


Hoofdstuk 3:

2006-2007

CadrgReader

3.1 DOELSTELLING Zoals de naam het zegt, dient deze module te lezen uit de beschikbare CADRG data. De input voor de CadrgReader zal bestaan uit een aanvraag, die een bepaalde locatie en schaal omvat. Hiervoor zal dan een rasterafbeelding moeten worden geladen. Om snel op deze aanvraag te kunnen antwoorden zal bij het initialiseren van de CadrgReader een structuur moeten worden opgesteld, die kan nagaan of die data aanwezig is en waar ze moet worden opgehaald.

3.1.1 VEREISTEN 3.1.1.1 BASISVEREISTE Het hoofddoel van de CadrgReader is om voor een gevraagde locatie (lengtegraad, breedtegraad) en een bepaalde schaal, de corresponderende rasterafbeelding te zoeken en te decomprimeren uit de CADRG database. Locatie - Lengtegraad - breedtegraad Schaal

CadrgReader

A.TOC

Wanneer er voor een bepaalde locatie geen rasterafbeeldingen aanwezig zijn in de gewenste schaal, dan dient het systeem automatisch op zoek te gaan in andere schaalbibliotheken om te kijken of de locatie aanwezig is. 3.1.1.2 TABLE OF CONTENTS LIST OPSTELLEN. Om een rasterafbeelding voor een bepaalde locatie op te halen, moeten we weten of er rasterafbeeldingen aanwezig zijn voor die bepaalde locatie en waar ze dan te vinden zijn. Daarom zal er bij het opstarten van de CADRG-reader, eerst moeten gezocht worden naar de aanwezige CADRG databases1 en hun coverage. Hiervan dient dan een snel te raadplegen datastructuur te worden gemaakt. Het zoeken naar de aanwezige CADRG databases gebeurt vanaf een

1

Zie vorig hoofdstuk “CADRG”. Om over rasterafbeeldingen te beschikken voor een grotere oppervlakte, zijn er meestal meerdere CADRG databases aanwezig. Philippe Vandewalle

pagina - 24 -


2006-2007

opgegeven start directory, die de CADRG databases groepeert. Daarna worden subdirectories recursief doorzocht naar *.TOC-bestanden. 3.1.1.3 ZO WEINIG MOGELIJK BESTANDSTOEGANG. In het huidig systeem vindt ook veel bestandstoegang plaats. Aangezien veelvuldige interactie met het secundaire geheugen (voor een avionics systeem is dit flashgeheugen) een bottle-neck is voor de performantie, dient het aantal bestandstoegangen tot een minimum te worden herleid bij het ophalen van rasterafbeelding. Lezen van een bestand is trouwens een dure operatie in vergelijking met een processor operatie of bij het lezen van het primaire geheugen. 3.1.1.4 TILES OF FRAMEFILES? Bij het opgeven van een bepaalde locatie dient een rasterafbeelding te worden geladen. Maar hoe groot is deze afbeelding? Door de opbouw van de CADRG database kunnen we kiezen. Ofwel laden we een gehele framefile, ofwel één enkele tile. Indien we een gehele framefile laden, dan lezen we het framefile bestand in één keer in het geheugen (= zo weinig mogelijk bestandstoegang). We decomprimeren de 6 x 6 tiles tot 1 afbeelding van 1536 x 1536 pixels. En kunnen daarna het geheugen van het ingelezen bestand terug vrijgeven. Een nadeel hiervan is dat we mogelijk veel te veel data decomprimeren en bijhouden. Wanneer we er voor kiezen om als elementaire afbeelding een tile te laden, dan lezen we ook de gehele framefile in het geheugen. Niet enkel en alleen om bestandstoegang te reduceren, maar ook omdat de framefile moet geinterpreteerd worden om de decompressietabellen te bekomen en om te weten waar de te decomprimeren data zich bevindt. Daarna decomprimeren we de tile van 256 x 256 pixels en kunnen we de geheugenruimte van de ingelezen framefile vrijgeven. Om continuiteitsredenen1 en om niet onnodig veel data te moeten decomprimeren, zullen we ervoor kiezen om de grootteorde van een rasterafbeelding klein te houden en gelijk te stellen aan een tile. Aangezien het de bedoeling is om de CadrgReader later te integreren in de CadrgViewer, zullen we er rekening mee moeten houden dat iedere keer als we een tile willen laden, we de gehele framefile ook zouden moeten laden. Wanneer we dan bij de Vieuwer bijvoorbeeld een beeld zouden willen die meerdere tiles van éénzelfde framefile omvat, dan zouden we meerdere malen diezelfde framefile moeten inlezen. Wat zeer inefficient is. Daarom zullen we er voor moeten zorgen dat er een structuur wordt bijgehouden met de geladen, herbruikbare framefiles van de tiles die worden gebruikt in de view. Zo kunnen we de grootte van een elementaire afbeelding klein houden èn moeten we de framefile maar één keer inlezen. Zelfs wanneer we daarna meerdere tiles van dezelfde framefile willen laden. 1 We zorgen ervoor dat het laden van rasterafbeeldingen snel en continu kan gebeuren door de elementaire afbeeldingen klein te houden. Dit in de plaats van grote afbeeldingen die een haperend effect veroorzaken wanneer een grote blok data moet worden geladen. Philippe Vandewalle

pagina - 25 -


2006-2007

3.2 ANALYSE 3.2.1 SKELET VAN DE CADRGREADER Als we kijken naar de opbouw van de CadrgReader, dan dient die eigenlijk uit 3 grote blokken te bestaan: • De initialisatie. • Het verwerken van één of meerdere aanvragen. • Het opruimen van de gebruikte datastructuren. 3.2.1.1 DE INITIALISATIE: Bij de initialisatie van de CadrgReader worden de aanwezige TOC bestanden gezocht en geparst. Hierbij wordt een snel te doorzoeken datastructuur opgezet die de bedekkingen van de databases bevat. Deze moet de TOCobjecten verzamelen. Procesflow: Initialisatie

Geheugen

Recursief de sub directories van de start directory doorzoeken op zoek naar *.toc bestanden Gevonden bestand is *.toc bestand

Het gevonden bestand inlezen en parsen in een TOC-Object. A.TOC

Het nieuwe TOC-Object aan een TOC-verzameling toevoegen.

TOC

TOC

TOC

…

3.2.1.2 VERWERKEN VAN AANVRAGEN: De aangevraagde locatie wordt in de bovenbeschreven datastructuur opgezocht en indien aanwezig wordt de betreffende framefile geladen. De framefile wordt dan ook in een gegevensstructuur in het geheugen geladen om zo de rasterafbeelding te kunnen decomprimeren. De bekomen rasterafbeelding zal voorlopig, door het nog afwezig zijn van de viewer, worden opgeslagen als een bitmap in het filesysteem. Dit om te kunnen testen. Wanneer de CadrgReader dan zal worden geïntegreerd in de CadrgViewer dient dan enkel een pointer te worden doorgegeven die verwijst naar de rasterdata. De flow-layout van dit proces is te vinden op volgend bladzijde Philippe Vandewalle

pagina - 26 -


2006-2007

inputlocatie: vb (51°NB;3°OL) Geheugen

Procesflow: verwerken van aanvragen

Bepalen van de zone waarin de breedtegraad valt. getzone(51°NB)=3 Zoeken in de TOC verzameling in welke database de locatie/zone voorkomt en lokaliseert de corresponderende framefile.

TOC

TOC

…

NEE

Locatie en framefile gevonden? JA Framefile in datastructuur

geheugen

laden

en

parsen

in

Framefile

Framefile

Offsets in de framefile bepalen van gecomprimeerde afbeelding en decomprimeren.

de

Tile

Aanmaken van een Tile object (+ save as bitmap)

3.2.1.3 HET BEËINDIGEN: Bij het beëindigen dienen de destructors van de bovenbeschreven datastructuren te worden aangeroepen om het geheugen terug vrij te geven. Onderstaande afbeelding toont de flow-layout. Procesflow: CadrgReader opruimen

Geheugen

Geheugen van aanwezige tiles vrijgeven.

Tile

Geheugen van geladen framefiles vrijgeven.

Het TOC verzameling object opruimen met voor ieder TOC Object in de verzameling ook het corresponderende geheugen vrijgeven.

Philippe Vandewalle

Framefile

TOC

TOC

pagina - 27 -

…


3.2.2 ANALYSE

2006-2007

VAN DE TE GEBRUIKEN DATASTRUCTUREN BIJ HET

INITIALISATIE PROCES Bij de initialisatie wordt in het filesysteem vanaf een bepaalde start directory naar *.TOC bestanden gezocht. Deze bestanden dienen te worden ingelezen en geïnterpreteerd, om een inhoudstafel te bekomen in het geheugen met voor welke geografische locaties er rasterafbeeldingen beschikbaar zijn. 3.2.2.1 DATASTRUCTUREN OM EEN TOC BESTAND IN TE PARSEN. We moeten dus een datastructuur ontwerpen om een *.TOC bestand in het geheugen te parsen. We zullen hierbij rekening houden met de logische structuur van CADRG (zie het vorige hoofdstuk). Het TOC bestand bevat een verzameling verwijzingen (= sub directory en bestandsnaam) naar framefiles die de rasterafbeeldingen bevatten voor bepaalde locaties. Zo een verwijzing zullen we een Frame_entry noemen en bijhouden in een apart object. Deze Frame_entry objecten worden volgens bepaalde criteria gegroepeerd (zie hoofdstuk CADRG). Frame_entry objecten met een zelfde combinatie zone/schaal, worden gegroepeerd in een TOC_entry object in een 2 dimensionale tabel. Dit object beschrijft eigenlijk een grensrechthoek voor een bepaalde zone waarvoor rasterafbeeldingen aanwezig zijn. Een grensrechthoek wordt afgebakend door de geografische coördinaten van de 4 hoeken. Het gebruik van TOC_entry objecten heeft het voordeel dat we snel de betreffende Frame_entry zullen kunnen terug vinden. De Frame_entry objecten zullen een rij~ en kolom nummer hebben binnen de TOC_entry. We hebben gezien in het hoofdstuk “CADRG” dat de frames binnen een grensrechthoek in een zone, aan één gesloten zijn. Als we van een grensrechthoek het aantal rijen en kolommen frames weten (= bijgehouden in een TOC_entry object) en de geografisch coördinaten van de hoeken van de grensrechthoek, dan kunnen we dus snel dx en dy bepalen. Zie onderstaande figuur die een grensrechthoek voorstelt. NW lente~/ breedtegraad

NO lente~/ breedtegraad

Gezochte Frame_entry object dy ZW lente~/ breedtegraad

ZO lente~/ breedtegraad dx

Binnen een TOC_entry object kunnen we dus in O(1) een Frame_entry terug vinden. We moeten nu enkel nog de juiste TOC_entry snel kunnen bepalen. Al de TOC_entry objecten van een bepaalde database of *.TOC bestand zullen we verzamelen in een TOC object. Dit object zal bijkomende informatie over de Philippe Vandewalle

pagina - 28 -


2006-2007

database bevatten (raster product type, release datum, aantal grensrechthoeken,…) en ook een snel te raadplegen structuur met verwijzingen naar de TOC_entry objecten. Aangezien we van een te zoeken locatie snel de zone1 kunnen bepalen en een TOC_entry geheel binnen één zone valt, kunnen we TOC_entry objecten in een hashtabel organiseren in het geheugen. Een “getZone(locatie)” functie kan dan dienen als hashfunctie die de zone van een bepaalde locatie bepaald en waarbij de zone uiteraard als hashsleutel dient. Aangezien er in de CADRG database meerdere schaal bibliotheken kunnen voorkomen, kunnen er ook meerdere TOC_entry objecten binnen een bepaalde zone vallen. Er kunnen dus meerdere hashelementen voorkomen voor één sleutel. Aangezien het aantal TOC_entry objecten per zone variabel is, en hun aantal eerder laag is (er zal meestal maar 1 schaalbibliotheek aanwezig zijn, en uitzonderlijk 2 à 3 ), zullen we per hashelement een gelinkte lijst voorzien. De hashtabel zou er dan uitzien zoals onderstaande figuur. Hashtabel: entry lookup 1 2 Hashfunctie: GetZone(gezochte locatie.breedtegraad)

3 4 5 6 7 8 …

Het bepalen van het juiste hashelement gebeurt in O(1). Binnen het hashelement moeten we dan nog de gelinkte lijst overlopen die in deze implementatie maximaal 3 lang zal zijn. We kunnen nu binnen één database snel op zoek gaan naar een framefile voor een bepaalde locatie. Aangezien er meerdere CADRG databases aanwezig kunnen zijn, om een grotere bedekking te bekomen, zullen we een verzamelobject moeten voorzien die deze databases groepeert. De databases kunnen we niet gerangschikt bijhouden volgens een bepaalde zoeksleutel die relevant is bij het opzoeken van een bepaalde locatie. En aangezien het aantal databases ook niet groot zal zijn (van 5 tot 10), kunnen we de databases gerust bijhouden in een gelinkte lijst zoals onderstaande figuur. Database1info+ Database2info+ Database3info+ 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 1

zones zijn begrensd door discrete waarden die niet veranderen. Zie hoofdstuk ”CADRG: 3.3.1.2 Zones”.

Philippe Vandewalle

pagina - 29 -


2006-2007

Besluit: Stellen we het aantal databases voor door “d”, het aantal schaalbibliotheken door “s” en het aantal framefiles door n. Dan is de totale performantie voor het zoeken naar de juiste framefile gelijk aan O(d.s). Op het eerst zicht lijkt dit niet zo goed. Maar als we weten dat d en s klein zijn, en de enige parameter die groot kan uitvallen, namelijk n (=aantal framefiles), geen rol speelt in de totale performantie omdat de locatie van een framefile kan berekend worden, dan is dit zeer performant. 3.2.2.2 UML KLASSENDIAGRAM VOOR HET INITIALISATIEPROCES Als we de hierboven omschreven klassen in een UML schema gieten met elk hun benodigde attributen, dan bekomen we onderstaand schema. De klassen Frame_entry en TOC_entry hebben geen methodes omdat deze geen functionaliteit bezitten, ze dienen enkel om te groeperen om sneller te kunnen zoeken. Hun nieuwe instanties worden aangemaakt door het TOC object. * + + + + + + +

Frame_entry exists: long frame_row: unsigned short frame_col: unsigned short *directory: char filename[16]: char georef[7]: char version: char

1 TOC + + + + + + + + + + + + + + +

endian: unsigned char hdr_sec_len: unsigned short ascii filename[12]; new: unsigned char standard_num[15]: char standard_date[8]: char classification: char country[2]: char release[2]: char loc_sec_phys_loc: uint loc_sec_log_loc: uint rpf_type: int NITF_hdr_len: long entrie_lookup[18]: Link_list* num_boundaries: unsigned int

+

newTOC (RPF_path: char*, filename: char*) Toc* + deleteTOC(_toc: TOC*) + getEntry(_toc: Toc*, imp_ctl: Import_controls *) Toc_entry* + TOCprintinfo(_toc: TOC*)

Philippe Vandewalle

1

0..* + + + + + + + + + + + + + + + + + + + + + + +

TOC_entry nw_lat: double nw_long: double sw_lat: double sw_long: double ne_lat: double ne_long: double se_lat: double se_long: double vert_interval: double horiz_interval: double vert_resolution: double horiz_resolution: double horiz_frames: long vert_frames: long invalid_geographics: long boundary_id: unsigned short type[8]: char compression[6]: char scale[18]: char zone[2]: char producer[6]: char version: char *title: char

1

0..1 TOC_List

+ newTOC_list (RPF_path: char*) TOC_list* + deleteTOC_list(_toc_list: TOC_list*) + printTOC_list(_toc_list: TOC_list*)

pagina - 30 -


3.2.3 ANALYSE

2006-2007


VERWERKEN VAN DE AANVRAGEN VAN EEN RASTERAFBEELDING. Nu we beschikken over een snel te doorzoeken inhoudsopgave van de bedekking van de databases, zullen we onderzoeken welke structuren we nog nodig hebben om een aanvraag te verwerken, voor het laden van een rasterafbeelding voor een bepaalde locatie. Aangezien het de bedoeling is om de CadrgReader later te gebruiken om aanvragen van de CadrgViewer te verwerken, zullen we de structuren ontwerpen met het oog op het laden van meerdere tiles na elkaar. We zullen dus de structuur zo opstellen dat we voordeel kunnen halen uit de reeds geladen resources (bijvoorbeeld geladen framefiles hergebruiken). 3.2.3.1 IMPORTCONTROLS Om het zoeken naar de juiste framefile binnen de TOC_List te vergemakkelijken zullen we gebruik maken van een kleine hulpstructuur die de aanvraagparameters bevat. Zo moeten we maar één parameter meegeven aan de functies die de juiste framefile proberen te lokaliseren. We kunnen deze structuur als het aanvraag object zien, en zal de sleutels bevatten voor de te importeren rasterafbeelding. Namelijk de lengtegraad, breedtegraad en de schaal. Dit object zullen we een Import_controls object noemen. Van dit object zal er gedurende geheel de applicatie maar één instantie aanwezig zijn waarbij de attributen zullen gewijzigd worden bij eventuele volgende aanvragen. Import_controls + lat: double + lon: double + scale: char*

3.2.3.2 FRAMEFILE Wanneer we de betreffende framefile gelokaliseerd hebben, dan moeten we deze laden en parsen in een datastructuur. Hiervoor zullen we een Frame_file object voorzien. Om het aantal bestandstoegangen te reduceren, zullen we geheel de framefile in één blok in het geheugen lezen. In het object voorzien we hiervoor een pointer naar dit datablok en een attribuut die de grootte in bytes bijhoud. Hiervoor zullen we de grootte van de betreffende framefile moeten opvragen aan het bestandssysteem. Na het interpreteren van de data, mag het gebruikte geheugen hiervoor terug vrijgegeven worden. We parsen eerst de header van de framefile waarvoor we een apart object voorzien. Voor de attributen1 van de header verwijs ik door naar het klassendiagram met betrekking tot het parsen van een framefile. Daarna volgen de geografische coördinaten van het gebied die door de framefile wordt bedekt. Deze worden gegroepeerd in een Coverage object. De framefile omvat ook een paar compressieobjecten. Namelijk het Compression object.

1

De attributen van de header zijn ook terug te vinden in het hoofdstuk “CADRG” bij de bestandsbeschrijving van een framefile.

Philippe Vandewalle

pagina - 31 -


2006-2007

Dit object bevat informatie over het type compressie, het aantal decompressietabellen en hun offsets. De decompressietabellen worden elk bijgehouden in een CompessionLookupTable object. Elk CompressionLookupTable object heeft z’n eigen id die de volgorde van de tabel bepaald in de vectordecompressie. Het CompressionLookupTable object bevat ook informatie over het aantal records die het bevat en de lengte van de records (in bits). Deze records worden elk voorgesteld door een CompressionParameter object. Dit is het eigenlijk record voor decompressie. Dit bestaat uit een sleutel en een waarde. De framefile bevat ook informatie over de gecomprimeerde data. Deze informatie bevat het aantal subframes die het horizontaal en verticaal bevat, hoe deze zijn geordend in het gecomprimeerd datablok (aantal subframe tabellen, het aantal lijnen en kolommen met bits die één zo een tabel vertegenwoordigd). Dit is nodig voor een partiële decompressie om zo één subframe uit een het gecomprimeerde datablok te halen. Deze informatie wordt gegroepeerd in een RPF_Image object (afgeleid van Raster Product Format). FrameFile + data: unsigned char* + datasize: long + entry: Frame_entry* + indices[6][6]: unsigned int + loc_data: unsigned int + all_subframes: unsigned char + NITF_hdr_len: long + chummed[6][6]: unsigned int + compressed: long + newFrameFile(entry* Toc_entry, imp_ctl* Import_controls) Frame_file * + deleteFrameFile(ffile* Frame_file) - parse_framefile(ffile* Frame_file) int

4

* + + + + + + + + + + + +

Coverage nw_lat: double nw_long: double sw_lat: double sw_long: double ne_lat: double ne_long: double se_lat: double se_long: double vert_resolution: double horiz_resolution: double vert_interval: double horiz_interval: double

Philippe Vandewalle

+ + + + + + + +

RPF_image spectral_groups: unsigned short subframe_tables: unsigned short spectral_tables: unsigned short spectral_lines: unsigned short horiz_subframes: unsigned short vert_subframes: unsigned short output_cols: unsigned int output_rows: unsigned int

+ + + + +

CompressionLookupTable id: unsigned short records: unsigned int values: unsigned short bit_length: unsigned short phys_offset: unsigned int

CompressionParameter + id: unsigned short + rec_off: unsigned int

+ + + + + + +

Compression algorithm: unsigned short noff_recs: unsigned short nparm_off_recs: unsigned short tables: unsigned short table_length: unsigned short parameters: unsigned short para_length: unsigned short

pagina - 32 -


2006-2007

Uit het UML schema op de vorige pagina blijkt dat alle functionaliteit, voor het laden en parsen, door het FrameFile object wordt vervult. De overige objecten dienen enkel voor groeperen, structureren en hergebruik. Zo zal bijvoorbeeld het Coverage object later kunnen hergebruikt worden bij het maken van een Tile object. Instanties van structuurobjecten worden gecreëerd door het FrameFile object zelf. 3.2.3.3 HET LADEN VAN EEN TILE We beschikken nu over een FrameFile object in het geheugen waarmee we een tile kunnen laden(decomprimeren). De tile dient de opgegeven geografische locatie van het Import_Controls object te omvatten. Het laden van een Tile gebeurt volgens volgend stramien: • Bepalen van de subframe binnen de framefile. • Offset van subframe binnen het gecomprimeerde data blok bepalen. • Decomprimeren van de data. • Tile Object aanmaken. BEPALEN VAN SUBFRAME BINNEN DE FRAMEFILE. Een tile is een subframe in een framefile. Een framefile bevat standaard, volgens de militaire specificatie van CADRG, 6 x 6 subframes (=tiles). Maar om compatibiliteit met mogelijke veranderingen in de toekomst te voorzien, zullen we er altijd voor zorgen dat we het aantal subframes per framefile lezen uit het RPF_Image object. Elk FrameFile object bevat trouwens een RPF_Image object. Samen met het Coverage1 object en het RPF object van de FrameFile kunnen we volgens de regel van drie het kolom~ en rij nummer van de te decomprimeren subframe bepalen.

NW lente~/breedtegraad Framefile: FrameFile.Coverage.North-West

Gevraagde lengtegraad: ImportControls.longitude NO lente~/breedtegraad Framefile: FrameFile.Coverage.North-East

Te decomprimeren subframe

Gevraagde breedtegraad: ImportControls.latitude

dy

ZW lente~/breedtegraad Framefile: FrameFile.Coverage.South-West

dx

ZO lente~/breedtegraad Framefile: FrameFile.Coverage.South-East

1

De Coverage van een FrameFile bevat de geografsiche coördinaten van de vier hoeken van de Framefile. Philippe Vandewalle

pagina - 33 -


2006-2007

OFFSET VAN EEN SUBFRAME BINNEN HET GECOMPRIMEERDE DATA BLOK BEPALEN. We kennen nu dx en dy, respectievelijk kolom en rij van de subframe binnen de FrameFile. Het FramFile object bevat ook een attribuut “indices[6][6]”, die een 2 dimensionale tabel bevat van offsets van de subframes binnen de framefile. Voor de gegeven dx en dy, bevat FrameFile.indices[dx][dy], dan de offset van de te decomprimeren data. DECOMPRIMEREN VAN DE DATA. Om de data te kunnen decomprimeren, moeten we eerst weten hoe de decompressie bij CADRG werkt. De vector compressie bij CADRG werkt met codewoorden van 12 bits. Elk mogelijk codewoord heeft een ingang in een CompressieLookupTable. 12 bits, zorgen voor 212 of 4096 mogelijkheden. Een CompressieLookupTable bestaat bijgevolg uit 4096 records waarbij het codewoord van 12 bits als sleutel of index dient. Ieder codewoord wordt gedecomprimeerd tot 16 pixels, of beter gezegd tot 16 ingangen in de kleurentabel met maximaal 215 mogelijke kleuren. Om dit mogelijk te maken zijn er 4 CompressieLookupTables nodig. Iedere CompressieLookupTable vertaald het 12 bit codewoord in 4 pixels op een rij. Door het codewoord in 4 verschillend, opeenvolgende CompressieLookupTables op te zoeken, bekomt men dus 4 rijen van 4 kolommen kleurwaarden. Deze kleuren moeten later dan nog worden opgezocht in de ColorLookupTable. (Zie onderstaande figuur voor de werking van de CompressionLookupTables.) 256 x kleurenindex

64 x 12 bits codewoord CompressionLookupTable 1 64

0000 0000 0000 0000 0000 0001 … … … ………… 1111 1111 1111 CompressionLookupTable 2

Één 12 bits codewoord 100110010101

0000 0000 0000 0000 0000 0001 … … … ………… 1111 1111 1111

256

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...................... . . . Één . . . . . . . . . . codewoord ......... . . . gedecomprimeerd . . . . . . . . . . . . . . . . tot ... ...................... 4x4 kleurindexen ...................... ...................... ...................... ...................... ......................

CompressionLookupTable 3 0000 0000 0000 0000 0000 0001 … … … ………… 1111 1111 1111 CompressionLookupTable 4 0000 0000 0000 0000 0000 0001 … … … ………… 1111 1111 1111

Één compressietabel bevat 4096 records.

Om een tile met grootte 256 x 256 pixels te kunnen decomprimeren, bevat het gecomprimeerde datablok dus 64 x 64 codewoorden van 12 bits. Philippe Vandewalle

pagina - 34 -


2006-2007

Om een subframe op kolom x en rij y in de framefile te decomprimeren tot een tile van 256 x 256 pixels, lezen we vanaf offset FrameFile.indices[x][y] het gecomprimeerde datablok in. Dit datablok heeft een grootte van 64 x 64 x12 bits (=6144 bytes, zie afbeelding op vorige bladzijde.) Door met een pointer door dit datablok te lopen, en te shiften om de 12 bits afzonderlijk in één integer te krijgen, kunnen we deze waarden dan opzoeken in de CompressionLookupTable. Het resultaat is dan een structuur van 256 x 256 bytes kleurenindexen. TILE OBJECT AANMAKEN. Met het oog op het later integreren van de CadrgReader in een CadrgViewer, slaan we deze data op in een CadrgTile object. Het Tile object zal een pointer bevatten naar de data (256 x 256 kleurindexen) en de grootte van het datablok, zodat we niet buiten dit blok lezen bij het raadplegen met een pointer. Ook zullen we bijhouden welke kolom en rij deze CadrgTile vertegenwoordigd in de FrameFile. Om de geografische locatie te kunnen bepalen van de tile, zal de CadrgTile ook nog een Coverage object omvatten. Om van de ingelezen FrameFile hergebruik te kunnen maken bij het eventueel laden van een volgende tile, zullen we gebruik maken van een hulpstructuur, die we een CadrgImage zullen noemen. Een CadrgImage zal de geladen Tiles die bij één FrameFile horen groeperen. Een CadrgImage zal bijgevolg een 2 dimensionale tabel met pointers bevatten naar de geladen CadrgTiles (zie onderstaande figuur). Pointers naar CadrgTiles die nog niet geladen zijn blijven NULL. Een CadrgImage bevat ook een pointer naar de corresponderende FrameFile om zo snel een volgende tile te kunnen laden, alsook een poiner naar de CompressionLookupTable en ColorLookupTable van de FrameFile, die gemeenschappelijk zijn voor al de CadrgTiles. Een CadrgImage bevat vervolgens ook nog het aantal tiles horizontaal en verticaal, en een teller die bijhoud hoeveel CadrgTiles er reeds zijn geladen. CadrgImage CompressionLookupTable* ColorLookupTable* FrameFile* Nhorizontal_tiles Nvertical_tiles references

CadrgTile Data* CadrgTile NbytesData Data* CadrgTile X_index NbytesData Data* Y_index CadrgTile X_index NbytesData Image* Data* Y_index CadrgTile X_index NbytesData Image* Data* Y_index CadrgTile X_index NbytesData Image* Data* Y_index CadrgTile X_index NbytesData Image* Data* Y_index CadrgTile X_index NbytesData Image* Data* Y_index X_index NbytesData Image* Y_index X_index Image* Y_index Image*

Voor de volledigheid bevat een CadrgTile object ook nog een pointer naar z’n CadrgImage object (een soort ouder pointer) om via het CadrgImage object naar eventuele buur CadrgTiles te kunnen verwijzen in de CadrgViewer. Philippe Vandewalle

pagina - 35 -


2006-2007

Om de CadrgReader te testen zullen we dan van het Tile object lezen om een bitmap bestand (*.bmp) te maken die we gemakkelijk kunnen raadplegen op onregelmatigheden. 3.2.3.4 UML SCHEMA VAN DE OBJECTEN DIE EEN AANVRAAG AFHANDELEN 0.* CadrgTile + data: unsigned char* + nbytesdata: unsigned int + x_index: int + y_index: int +newCadrgTile(image* CadrgImage, x int, y int, comp_lut* unsigned char) CadrgTile * + deleteCadrgTile(tile* CadrgTile) -get_rpf_image_tile(file Frame_file*, tno long, table unsigned char* ,tile unsigned char*) short

FrameFile data: unsigned char* datasize: long entry: Frame_entry* indices[6][6]: unsigned int loc_data: unsigned int all_subframes: unsigned char NITF_hdr_len: long chummed[6][6]: unsigned int compressed: long newFrameFile(entry* Toc_entry, imp_ctl* Import_controls) Frame_file * + deleteFrameFile(ffile* Frame_file) - parse_framefile(ffile* Frame_file) int + + + + + + + + + +

1 CadrgImage color_lut: byte[3]* compression_lut: unsigned char* references: int nw_lat: double nw_long: double sw_lat: double sw_long: double ne_lat: double ne_long: double se_lat: double se_long: double vert_interval: double horiz_interval: double zone: long scale_library: char* num_hor_tiles: int num_ver_tiles: int newCadrgImage(toc Toc_file*, impctl Import_controls*) CadrgImage* + deleteCadrgImage(image CadrgImage*) + + + + + + + + + + + + + + + + + +

+ + + + + + + + + + + +

Coverage nw_lat: double nw_long: double sw_lat: double sw_long: double ne_lat: double ne_long: double se_lat: double se_long: double vert_resolution: double horiz_resolution: double vert_interval: double horiz_interval: double

De onderste twee objecten (FrameFile en Coverage) zijn reeds eerder behandeld en dienen enkel om de relatie ermee aan te tonen.

Philippe Vandewalle

pagina - 36 -


2006-2007

3.3 REALISATIE 3.3.1 GLOBALE APPLICATIE STRUCTUUR De uitwerking van de algoritmen zal gebeuren in C. Niet tegenstaande de programmeertaal C niet object georiënteerd is, zullen we deze manier van werken toch proberen te benaderen. Zo krijgt ieder basisobject een eigen header~ en code bestand met de naam van het object. Bijvoorbeeld: Met het TOC object correspondeert het TOC.h bestand, die de interface van het object definieerd en een TOC.c bestand die de functionaliteit bevat. Zo zal ook ieder object een procedure hebben van de vorm newObjectnaam en deleteObjectnaam, een soort constructor en destructor. Onderstaande afbeelding illustreert deze manier van werken.

TOC.h

TOC OBJECT TOC.c

- Definitie van de struct van het object - Definitie van de publieke procedures: • newTOC(…) • deleteTOC(…)

- Uitwerking van de functionaliteit van de publieke procedures. - De private procedures: • parse_Toc(…) • hashEntryLookup(…)

Voor de realisatie van de applicatie maken we vervolgens gebruik van nog één extra object, namelijk het “Application” object. Van dit object wordt maar één instantie aangemaakt. Dit object vormt een soort rootobject van waaruit alle objecten in de applicatie kunnen worden bereikt. Het “Application” object bevat ook nog attributen die de status van de applicatie bijhouden. Onderstaande code toont de attributen die van belang zijn voor de CadrgReader. typedef struct{ Link_list Import_controls Link_list void double double }Application;

*cadrg_toc_list;// list of TOC’s imp_ctl; // application import control *loaded_cadrg_image_list;//LL of CadrgImages *centertile;//needs to be casted to CadrgTile x;// x position tile y;// y position tile

Het “Application” object wordt geïmplementeerd als struct in het global.h bestand. Het global.h bestand bevat declaraties van structs en procedures die globaal zijn voor de applicatie en niet specifiek aan één objectklasse kunnen worden toegeschreven. Het global.c bestand bevat dan de uitwerking van de procedures die in global.h werden gedeclareerd. We zullen de realisatie, net als de analyse, ook in 3 onderdelen opsplitsen: • De initialisatie • Afhandelen van de aanvragen • Het opruimen van de gebruikte datastructuren Philippe Vandewalle

pagina - 37 -


2006-2007

3.3.2 OVERZICHT VAN DE PROCEDURES BIJ HET INITIALISATIEPROCES. Bij de initialisatie moeten alle CADRG *-toc bestanden worden gezocht en geïnterpreteerd. Hiervan worden dan TOC objecten gemaakt en samengevoegd in een TOC-List. Bij de start maken we dus een nieuw TOC_List object aan. Dit object is een member van het globale application object. 3.3.2.1 PROCEDURES VAN HET TOC OBJECT (TOC.C EN TOC.H). Public (TOC.h)

Toc*newTOC (char* RPF_path);

Public (TOC.h)

void deleteTOC(Toc* _toc);

Public (TOC.h)

Constructor voor het TOC object. De parameter RPF_path bevat het pad naar het *.toc bestand. De constructor zorgt er voor dat er geheugen gereserveerd wordt en er andere nodige procedures worden aangroepen om het *.toc bestand te converteren in een bruikbaar TOC object. Indien er geen TOC object kan worden aangemaakt is de returnwaarde een lege pointer.

Geeft het gebruikte geheugen terug vrij bij het opruimen van het TOC object. Dit is de destructor. De “_toc” parameter is de pointer naar het op te ruimen object. Toc_entry *imp_ctl);

*getEntry(_Toc

*toc,

Import_controls

Geeft een TOC_entry object terug. Deze procedure probeert een TOC_entry te vinden in een TOC object(attribuut “_Toc”) die voldoet aan de attributen van een import_control object (attribuut “imp_ctl”) zoals bepaalde lengtegraad, breedtegraad, schaal, … Indien deze niet kan worden gevonden, wordt een lege pointer terug gegeven. Public (TOC.h)

Private (TOC.c)

Private (TOC.c)

void TOCprintinfo(Toc_file*); Dit is een soort “tostring” procedure. Om te weten welke geografische gebieden een bepaald TOC object omvat, kan men deze procedure aanroepen. Deze procedure schrijft de informatie rechtstreeks naar de console. unsigned int hash(char c); Dit is de hash functie die wordt gebruikt binnen en TOC object om snel een entry terug te vinden afhankelijk van de zone van de te zoeken locatie. De returnwaarde is de index van de hashtabel. Toc_entry *parse_toc *);

(char *, char *, Header *, uint

Deze procedure wordt aangeroepen door de constructor om de Toc_entries te parsen in het TOC object.

Philippe Vandewalle

pagina - 38 -


2006-2007

3.3.2.2 PROCEDURES VAN HET TOC_LIST OBJECT Public Link_list *newTOC_list (char* RPF_path); (TOC_List.h) Dit is de constructor die een nieuw TOC_list object zal aanmaken. De “RPF_path” parameter bevat het pad naar de startdirectory waar de CADRG databases zich bevinden. Met behulp van de “rec_search_for_toc_files()”-procedure (zie hieronder), wordt dan vanaf deze startdirectory, het filesysteem afgezocht naar *.toc bestanden. Deze procedure zal voor ieder gevonden *.toc bestand een nieuw TOC object door de “newTOC()” constructor aanroepen. Het TOC object wordt dan aan de TOC_List toegevoegd. Wanneer al de TOC bestanden tot TOC objecten zijn omgevormd, is de TOC_list compleet en wordt een pointer ernaar terug gegeven. De TOC_List is van het type “Link_list”. Public Void deleteTOC_list(Link_list* TOC_list); (TOC_List.h) De destructor. Deze procedure ruimt de TOC objecten in de TOC_list op. Dit gebeurt door voor ieder TOC object, één voor één, de “deleteTOC()” procedure aan te roepen. Public Void printTOC_list(Link_list* TOC_list); (TOC_List.h) Deze procedure roept voor ieder object in de TOC_list de “printTOC()” procedure aan. Zo bekomt men een lijst van de geografische locaties die worden bedekt door de aanwezige databases in het systeem. Private Link_list* rec_search_for_toc_files(Link_list* (TOC_List.c) char* startpoint, char* TOCpattern)

TOC_List,

Deze procedure zoekt recursief vanaf een bepaalde startdirectory (=startpoint parameter)in het bestandssysteem naar *.toc bestanden (= TOCpattern parameter). Wanneer het betreffende bestand een *.toc bestand is wordt hiervoor de “newTOC()” constructor aangeroepen. Wanneer het gaat om een directory, wordt deze procedure recursief aangeroepen vanaf dit punt. 3.3.2.3 PROCEDURES VAN HET TOC_ENTRY EN FRAME_ENTRY OBJECT Het TOC_entry object bevat geen functionaliteit en dient enkel als groeperingobject om sneller te kunnen zoeken binnen een TOC. Het wordt dan ook geïmplementeerd als struct in het TOC.h bestand zelf. Het zoeken doorheen de TOC_entries, wordt volledig beheerd door het TOC object. Een Frame_entry object biedt ook geen functionaliteit. Het bevat gewoon informatie over een verwijzing naar een FrameFile. Aangezien Frame_entries ook nog worden gebruikt in andere standaarden dan CADRG binnen de RPF familie, wordt een Frame_entry geïmplementeerd als een struct in een RPF.h bestand. In het RPF.h en RPF.c bestand zullen we structs en procedures declareren die globaal gebruikt worden binnen de RPF familie en niet specifiek voor CADRG. Hieronder vindt je de procedures die in het RPF.c bestand worden beschreven.

Philippe Vandewalle

pagina - 39 -

Thesis: Advanced graphics for avionics displays Public (RPF.h)

Public (RPF.h)

2006-2007

Char get_zone_from_latitude (double lat); Deze procedure bepaald voor een gegeven breedtegraad de zone waarin men een framefile moet zoeken. De zone wordt teruggegeven als karakter. Zie hoofdstuk “CADRG” voor meer uitleg over zones. Void skipNITFHeader(FILE *infp); Bij het parsen van een bestand in de RPF familie, zet deze procedure de leespointer juist na de NITF header.

Public (RPF.h)

Long getNITFHeaderLEN(Frame_file *file);

Public (RPF.h)

Long parse_locations_from_framefile(Frame_file Location *locs, long count, long offset);

Geeft de lengte van de NITF header terug. file,

Bij het parsen van een framefile bestand leest deze procedure de byte offset locatie’s in van de verschillende secties in het bestand. De Location struct wordt gedeclareerd in RPF.h Public (RPF.h)

Long parse_locations(FILE count);

*fin,

Location

*locs,

long

In tegenstelling tot vorige procedure leest deze procedure de byteoffsets van de verschillende secties in van een TOC bestand.

3.3.3 OVERZICHT

VAN

DE

PROCEDURES

VAN

OBJECTEN

BIJ

HET

VERWERKEN VAN EEN AANVRAAG. Bij het behandelen van een aanvraag, probeert men een tile te laden voor de geografische locatie die het import_controls object bevat. Dit gebeurt door eerst te kijken in de application.loaded_cadrg_image_list1, als er reeds een framefile geladen is die deze locatie omvat. Indien dit niet het geval zoekt men in applicaiton.cadrg_toc_list naar een verwijzing van een framefile die deze locatie omvat. Daarna wordt de betreffende framefile geladen, wordt er een CadrgImage aangemaakt, en gecomprimeerd men de tile waarin de geografische locatie zich bevindt. Voor het testen van de CadrgReader zullen we de rasterdata van de tile dan opslaan in een *.bmp bestand.

1

Zie hoofdstuk ”3.3.1 Globale applicatie structuur”, over het application object.

Philippe Vandewalle

globale

pagina - 40 -


2006-2007

3.3.3.1 PROCEDURES VAN HET FRAMEFILE OBJECT Public Frame_file *newFrameFile(Toc_entry (FrameFile.h) Import_controls *imp_ctl);

*entry,

De constructor van een framefile. Deze laadt via de gevonden Toc_entry de framefile die de geografische locatie van de Imort_controls omvat. Daarna wordt het framefile bestand geparst en wordt een Frame_file object teruggegeven. Public void deleteFrameFile(Frame_file*); (FrameFile.h) Destructor voor een Frame_file object. Public void parse_clut(Frame_entry *frame, Rgb *rgb, long (FrameFile.h) ReducedColorTable, uint *cct, long *n_cols, long Nitf_hdr_len, uchar *blackpixel); Deze procedure parst de color lookup table in de gepaste datastructuur. Public short get_comp_lut(Frame_file *file, HDATA_PTR table, (FrameFile.h) uint *cct, long ReducedColorTable); Deze procedure leest de compression lookup tables van de framefile in. Privat int parse_framefile(Frame_file *file); (FrameFile.c) Deze procedure wordt aangeroepen door de constructor om de gehele framefile te parsen.

3.3.3.2 PROCEDURES VAN HET CADRGIMAGE OBJECT Public CadrgImage *newCadrgImage(Toc_file (CadrgImage.h) Import_controls *impctl);

*toc,

De constructor van een CadrgImage object. Deze probeert voor een gegeven geografische locatie, een entry te vinden. Daarna wordt geprobeerd de framefile te laden, en wordt er een CadrgImage object gemaakt. Wanneer dit niet lukt, wordt een lege pointer terug gegeven. Public void deleteCadrgImage(CadrgImage *image); (CadrgImage.h) De destructor van een CadrgImage object. Public void printCadrgImageInfo(CadrgImage *image); (CadrgImage.h) Print informatie over het CadrgImage object naar de console.

Philippe Vandewalle

pagina - 41 -


2006-2007

3.3.3.3 PROCEDURES VAN HET CADRGTILE OBJECT Public (CadrgTile.h)

CadrgTile *newCadrgTile(void *image, int x, int y, unsigned char *comp_lut, unsigned char blackpixel); De constructor van een CadrgTile object. Van een gegeven image object probeert men een CadrgTile object te laden op rij x en kolom y. Een pointer naar het object wordt terug gegeven. Wanneer dit niet lukt wordt een lege pointer teruggegeven.

Public void deleteCadrgTile(CadrgTile * tile); (CadrgTile.h) De destructor van een CadrgTile object. Public void printCadrgTileInfo(CadrgTile* tile); (CadrgTile.h) Print informatie over de CadrgTile naar de console. Private short get_rpf_image_tile(Frame_file file, (CadrgTile.c) unsigned char* table, unsigned char* decompress, uchar blackpixel);

long tile,

tno, long

Decomprimeert de data van een CadrgTile. Uit de gegeven Frame_file wordt vanaf offset “tno” een tile gedecomprimeerd met behulp van de decompressietabel “table”. De rasterdata wordt opgeslagen in tile.

3.3.3.4 DE RASTERAFBEELDING VAN DE CADRGTILE OPSLAAN ALS *.BMP BESTAND. Om te kunnen testen of een de CadrgTile juist werd geladen, slaan we de rasterdata op in een bitmapbestand zodat we deze kunnen raadplegen. Public (BMP.h)

void SaveIMGasBMP(unsigned char* d, Rgb* c_lut, char* outputfile, int x, int y, int dimension ); Deze procedure slaat de data “d” van de CadrgTile op in een bitmapbestand met naam “outputfile”. “x” en “y” zijn de posities van CadrgTile binnen de CadrgImage om te kunnen testen of de juiste tile werd gedecomprimeerd. “c_clut” is een pointer naar de color lookup table.

Public (BMP.h)

void encode_bmp_hdr (BITMAP_FILEHEADER *bf,BITMAP_INFO *bmi,FILE *fp); Deze procedure zorgt dat een standaardheader voor het bitmapbestand wordt gemaakt en weggeschreven.

3.3.4 HET OPRUIMEN VAN DE GEBRUIKTE DATASTRUCTUREN Voor het opruimen van de gebruikte datastructuren wordt een beroep gedaan op de destructors van de betreffende objecten. De destructors van verzamelobjecten, zoals een TOC_list, zijn zo ontworpen dat het voldoende is om de destructor van het verzamelobject aan te roepen. Zo zal “deleteTOC_list(applicaiton.cadrg_toc_list)” de destructor van alle TOC

Philippe Vandewalle

pagina - 42 -


2006-2007

objecten aanroepen die het bevat om daarna het eigen gebruikte geheugen vrij te geven. We moeten dus enkel maar de destructor van alle verzamelobjecten aan roepen. En de verzamelobjecten zijn bereikbaar via het globale application object.

3.4 C-CODE Voor de geschreven C-code, verwijs ik naar de bijgeleverde cd. De CadrgReader is terug te vinden in de directory “CADRG READER”. De applicatie vangt aan in de main(int argc, char** argv) van het “main.c” bestand.

3.5 RESULTAAT Onderstaande afbeelding is dan het resultaat van het laden van een CadrgTile met de CadrgReader.

Philippe Vandewalle

pagina - 43 -


Hoofdstuk 4:

2006-2007

OpenGL

Omdat we de textures op het beeld zullen brengen met behulp van OpenGL en in een latere fase ook de 3D beelden genereren met OpenGL, geven we eerst een kleine uitzetting over OpenGL.

4.1 WAT IS OPENGL? OpenGL is een interface voor grafische kaarten waarmee programmeurs op een 'gemakkelijke' manier mooie driedimensionale beelden kunnen programmeren. De programmeurs praten tegen de OpenGL-interface aan, waarna die OpenGl-interface de beelden opbouwt en deze naar de grafische kaart stuurt om te worden afgebeeld op het beeldscherm. Men kan OpenGL zien als DirectX, zij het dat OpenGL zelf geen versneller is maar een intermediair tussen de applicatie en de grafische kaart. OpenGL kan op diverse niveaus worden uitgevoerd: compleet in software (= langzaam), maar ook slim gebruik makend van de hardware-versnellers die op de grafische kaart zitten (= snel). Meer recentere grafische kaarten laten dan ook enorm veel “OpenGL-rekenwerk” door de grafische chips verzorgen, waardoor de software wordt ontlast. Men moet er dus voor zorgen dat de applicatie op de een of andere manier tegen OpenGL kan 'aan praten'. Indien de grafische kaart niet zou compatibel zijn met OpenGL, dient men dus de website van de fabrikant van de grafische kaart te raadplegen, om te kijken of er misschien een passende OpenGL-driver beschikbaar is.

4.2 ARCHITECTUUR Om OpenGL hardwareonafhankelijk te kunnen maken, werden commando's voor vensteropdrachten en voor het verkrijgen van gebruikersinvoer buiten beschouwing gelaten. Op het eerste zicht lijkt dit een serieus nadeel van OpenGL, maar zoals we later zullen zien (zie volgende puntje over GLUT), is het mogelijk om OpenGL te combineren met andere flexibele programmeerbibliotheken die wel vensteropdrachten en gebruikersinvoer afhandelen. Wat meer is, OpenGL voorziet ook geen opdrachten om complexe modellen te beschrijven (moleculen, vliegtuigen, huizen, vogels, enz...). In OpenGL vind je enkel de meest eenvoudige geometrische objecten (punten, lijnen en polygonen). De ontwikkelaar moet zijn/haar eigen model opbouwen gebruik makende van deze eenvoudige basis. Er bestaan wel OpenGLgerelateerde bibliotheken die meer complexe modellen voorzien, en elke gebruiker kan deze bibliotheken gebruiken om zelf bibliotheken te maken. De OpenGL interface kan aangesproken worden in verschillende talen waaronder:C/C++, Java, FORTRAN en Ada. In dit eindwerk zullen we de C interface gebruiken. Dit is immers ook de meest gebruikte.

Philippe Vandewalle

pagina - 44 -


2006-2007

4.2.1 OPENGL IMPLEMENTEERT VOLGENDE ZAKEN: 4.2.1.1 FEATUES VAN OPENGL GEBRUIKT IN DIT EINDWERK. Geometrische primitieven : laten toe om mathematische beschrijvingen van objecten te gebruiken. De primitieven die er tot nu toe zijn, zijn : • Punten • Lijnen • Polygonen • tekeningen en bitmaps. Kleuren codering in RGBA (Rood-Groen-Blauw-Alpha) of in kleurenindexmodus. Bekijken en Modelleren (Viewing and Modeling) laten toe om objecten in een 3dimensionele wereld te plaatsen, onze camera rond te bewegen in deze 3d wereld en het gunstigste punt te bepalen van waaruit we de scène die gerenderd moet worden willen bekijken. Texture Mapping:dit is een onmisbaar deel voor het CADRG gedeelte van deze thesis. Hiermee worden de bekomen rasterafbeeldingen getoond. Dubbele buffering helpt om flikker te voorkomen tijdens het “verder vliegen” boven de kaart. Elke opeenvolgende frame van een animatie wordt opgebouwd in een aparte geheugenbuffer en wordt enkel getoond op het scherm indien de rendering van het frame volledig uitgevoerd is. Anti-aliasing vermindert het blokkerige effect dat je krijgt als je een lijn op een computer scherm tekent. Dit gebeurt vooral bij lagere resoluties. Z-buffering houdt de Z-coordinaat van een 3D object bij. De Z-buffer wordt gebruikt om de nabijheid van objecten tot de kijker te bepalen. De Z-buffer is ook noodzakelijk bij het bepalen welke delen van objecten zichtbaar zijn en welke niet (hidden surface removal). Transformaties : rotaties, schaleringen, translaties, perspectieven in 3D, enz... 4.2.1.2 OPENGL BIEDT ECHTER NOG MEER MOGELIJKHEDEN ZOALS: Atmosferische effecten zoals mist, rook en nevel. Een algoritme beschrijft dat nevel, mist, rook, vervuiling van de lucht of eender welk luchteffect, hierdoor kan men diepte aan de tekening toevoegen. Display lijsten staan toe tekencommando's in een lijst op te slaan, zodat ze pas later gerenderd worden. Wanneer ze juist gebruikt worden, kunnen display lijsten de prestaties sterk verbeteren. Polynoom evaluatoren dienen om niet-uniforme rationele B-splines te ondersteunen.Deze helpen om mooi gelijkmatige krommen te tekenen, door slechts een paar referentiepunten te gebruiken, i.p.v. zeer veel punten tussenin. Feedback, selectie en kiezen ('Picking') laten je applicaties maken die de gebruikers toestaan om een deel van het scherm te selecteren of een object te selecteren dat op het scherm getekend is. In de feedback modus kan de ontwikkelaar de resultaten van de renderingberekeningen opvragen.

Philippe Vandewalle

pagina - 45 -


2006-2007

4.3 GLUT Zoals we reeds vermeldden, om OpenGL overdraagbaar en platformonafhankelijk te maken, was het noodzakelijk om alle commando's die iets te maken hebben met het venstersysteem overboord te gooien, bijvoorbeeld het openen van een venster, het sluiten van een venster, het schalen van een venster, een venster van vorm doen veranderen, het inlezen van de cursor positie, hetzelfde geldt voor alle commando's die te maken hebben met invoerapparaten zoals bijvoorbeeld het inlezen van toetsenbordinvoer enz... Deze acties zijn immers allemaal zeer besturingssysteemafhankelijk. In windows zou men eerst vensters moeten maken met WIN32 de inhoud, in OpenGL termen “renderingcontext genaamd, aan OpenGL koppelen en dan renderen. Ook alle programma interactie zou via WIN32 moeten gebeuren. Om dit te vermijden en het programmeerwerk vlotter te laten verlopen werd hiervoor een specifieke librairy geschreven, nl GLUT (=GL Utility Toolkit) De OpenGL Utility Toolkit is een programmeer-interface met ANSI C en FORTRAN bindingen voor het schrijven van OpenGL programma's. Het is geschreven door Mark J. Kilgard en vult een groot gat dat was opengelaten door de OpenGL specificatie. Dankzij de GLUT ontwikkelaars kunnen we een algemene window system interface gebruiken, onafhankelijk van het doelsysteem. OpenGL applicaties die GLUT gebruiken kunnen eenvoudig worden overgedragen tussen platforms zonder veel veranderingen aan de broncode. GLUT vereenvoudigd zeker de productie van OpenGL code en vult de OpenGL library aan. De GLUT API is een status machine, net als OpenGL. Dit betekend dat GLUT een aantal status variabelen heeft die 'leven' tijdens het uitvoeren van de applicatie. De initiële staten van de GLUT machine zijn redelijk gekozen om aan te sluiten bij de meeste applicaties. Het programma kan de waarden van de status (state) variabelen aanpassen wanneer dat nodig is. Als een GLUT functie wordt aangeroepen, wordt zijn actie aangepast aan de hand van de waarden van de status variabelen.

4.3.1 INITIALISATIE Ieder OpenGL programma dat gebruik maakt van GLUT moet beginnen met het initialiseren van de GLUT status machine. De glut initialisatie functies beginnen met glutInit***. De hoofd initialisatie functie is glutInit(int **argcp, char **argv)1. GlutInit zorgt voor het initialiseren van de GLUT status variabelen. Deze overige initialisatie routines kunnen gebruikt worden om de default venster initialisatie status te zetten. Bijvoorbeeld:

glutInitWindowPosition(int x, int **y); // vensterpositie van linker bovenhoek

1

argcp en argv gewoon overnemen van de main

Philippe Vandewalle

pagina - 46 -


2006-2007

glutInitWindowSize(int breedte, int **hoogte); //hoogte en breedte van het venster glutInitDisplayMode(unsigned int mode); //om statusvariabelen te plaatsen.

De

mode is de Display (weergave) mode, een bitsgewijze OR of GLUT display mode bit masker. Courant gebruikte bitmasker waarden zijn: GLUT_RGBA GLUT_RGB GLUT_INDEX GLUT_SINGLE GLUT_DOUBLE

Selecteer een RGBA mode venster. Dit is de standaard als geen GLUT_RGBA noch GLUT_INDEX is opgegeven. Het zelfde als GLUT_RGBA. Selecteer kleur index venster mode. Dit overschrijft GLUT_RGBA. Selecteer een enkel gebufferd venster. Dit is de standaard Selecteer een dubbel gebuffered venster. Dit overschrijft GLUT_SINGLE.

We illustreren deze functies aan de hand van een voorbeeld: #include //nodig im glut te kunnen gebruiken // zie volgend hoofdstuk over het opzetten van de omgeving void main(int argcp, char **argv){ /* Geef venster grootte en locatie */ glutInitWindowSize(640, 480); glutInitWindowPosition(0, 0); /* Selecteer Display mode type: Dubbele buffer & RGBA kleur */ glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE); /* Initialiseer GLUT status */ glutInit(&argcp, argv); // hier volgt dan de code die de render functies specificeren. };

4.3.2 CALLBACK FUNCTIES DECLAREREN Om de eigen functies, die de objecten tekenen en bepalen wat er moet gebeuren bij een bepaalde gebeurtenis te integreren met OPENGL/GLUT wordt beroep gedaan op callback functies. Bij deze functies dient men een pointer mee te geven naar de uit te voeren functie. Dit is de functie die men zelf geschreven heeft. 4.3.2.1 GEBEURTENIS AFHANDELING Zoals eerder genoemd is GLUT een status machine. Nu zullen we zien dat het ook ontworpen is als een gebeurtenis-gestuurde machine. Dit betekend dat er een "timer" of continue lus is die gestart wordt na de juiste initialisatie en die, een voor een, alle gebeurtenissen afhandelt die gedeclareerd zijn aan GLUT tijdens de initialisatie. Gebeurtenissen zijn: een muisklik, het sluiten van een venster, vergroten/verkleinen van een venster, verplaatsing van de cursor, indrukken van toetsen op het toetsenbord, en vooral bijzonder de "idle" gebeurtenis, oftewel als er niets gebeurd! Elk van de mogelijke gebeurtenissen Philippe Vandewalle

pagina - 47 -


2006-2007

moet geregistreerd worden in een van de GLUT status variabelen voor de "timer" of gebeurtenis-verwerkings lus van GLUT om periodiek te controleren of die gebeurtenis is gestart door de gebruiker. Zo zouden we bijvoorbeeld een "druk op toets pijl naar boven" als een gebeurtenis kunnen registeren waarbij GLUT een stap vooruit dient te lopen over de CADRG map. Gebeurtenissen worden geregistreerd via callback registration routines. Deze hebben de syntax glut[eenGebeurtenis]Func, in ons geval zou dit glutKeyFunc zijn. Een callback registratie verteld de GLUT engine welke gebruiker-gedefinieerde functie aangeroepen moet worden als de bijbehorende gebeurtenis wordt "getriggerd". In de CadrgViewer zullen we dus een functie KeyPress schrijven die nagaat welke toets werd ingedrukt, zodat we de positie kunnen verplaatsen, roteren, inzoomen,… Daarna moet de functie “KeyPress worden

geregistreerd na de glutInit() in

main() met het statement "glutKeyFunc(KeyPress);". Welke callback functies en gebeurtenissen zijn toegestaan in GLUT, kan men terug vinden in de GLUT API1. Het belangrijkste nu is dat nadat alle belangrijke gebeurtenissen in onze applicatie zijn geregistreerd, we de gebeurtenis-afhandelings routine van GLUT moeten starten, dit is de glutMainLoop(). De functie komt niet meer terug, ons programma gaat in feite een oneindige lus in. Het zal callbacks die eerder zijn geregistreerd aanroepen wanneer nodig. Iedere main() voor een OpenGL applicatie dient te eindigen in een glutMainLoop() statement. Onderstaand voorbeeld illustreer dit. #include void main(int argcp, char **argv){ /* Initialiseer GLUT status */ glutInit(&argcp, argv); glutInitWindowSize(640, 480); glutInitWindowPosition(0, 0); /* Open een venster */ glutCreateWindow("CADRG VIEWER"); /* Selecteer Display mode type:Double buffer & RGBA color */ glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE); /* Registreer Callback Functies */ glutKeyFunc(KeyPress); /* Start Gebeurtenis Afhandeling Engine */ glutMainLoop(); }; keyPress(GLKEY key){ if (key == ARROWUP) //de map verder verplaatsen… elseif (key == ‘Q’ // destructors aanroepen en applicatie beëindigen }

1

GLUT API: http://www.opengl.org/resources/libraries/glut/spec3/spec3.html

Philippe Vandewalle

pagina - 48 -


2006-2007

4.3.2.2 POINTER NAAR TEKENFUCTIE EN NAAR IDLE FUNCTIE De glutDisplayFunc zet de display functie voor het huidige venster en

glutIdleFunc, zet de idle functie. Beide registratie routines verwachten een functie van het type void *(void). We zullen dus een functie DrawMap() maken die door het aanroepen van OpenGL instructies, de CADRG textures op het scherm zet. Deze functie zet de eigenlijke scene op scherm En deze functie dan registreren via glutDisplayFunc(DrawMap); In de MyIdle(void), registreren we dan een functie die wordt aangroepen als er geen invoer van de gebruiker is, dit is iedere keer als het gebeurtenis afhandelings machine van GLUT de oneindige lus (=glutMainLoop()) doorloop, en geen nieuwe gebeurtenis optreedt. Hier registreren we dus een functie die het “CADRG landschap” update. Hier worden dus indien nodig nieuwe afbeeldingen geladen en oudere, niet meer nodige, worden vrijgegeven.

4.3.3

OPENGL INSTRUCTIES

4.3.3.1 PRIMITIEVEN TEKEN Het tekenen van primitieven zoals punten en lijnen gebeurt tussen 2 specifieke functies nl glBegin(GL_QUADS); //tekeninstructies //GL_QUADS specificeert gegroepeerd als vierhoek glEnd();

dat

de

punten

per

4

worden

Voor iedere vertex dienen 3 coördinaten te worden opgegeven. Wanneer de vertex tekeninstructie wordt voorafgegaan door een texture referentiefunctie, correspondeert de vertex met een bepaalde positie van de vertex. glBegin(GL_QUADS); for(i=0;i
coördinaat links onder vertex op pos x,y,z coördinaat rechts onder vertex op pos x,y,z coördinaat rechts boven vertex op pos x,y,z coördinaat links boven vertex op pos x,y,z

glEnd();

Philippe Vandewalle

pagina - 49 -


2006-2007

4.3.3.2 TEXTURES OpenGL maakt het mogelijk om textures te laden en deze data naar het geheugen op de grafische kaart te zenden waardoor er sneller kan gerenderd worden. Dit is het laden van de texture. Wanneer men de texture laadt krijgt men van OpenGL een texture-id terug. Dit is een integer die dient om de texture te identificeren. Wanneer men bij het renderen dan wil gebruik maken van deze texture, kan men naar deze texture verwijzen door middel van dit texture-id. Hiervoor worden volgende functies gebruikt. glGenTextures( 1, &textureid);// genereert een uniek texture-id die nog vrij is glBindTexture(GL_TEXTURE_2D, textureid); // bind een textureid aan een texture instantie glTexImage2D(GL_TEXTURE_2D, 0, 3, 256, 256, 0, GL_RGB, GL_UNSIGNED_BYTE, data); //zend de data naar de grafische kaart en spicifieerd de breedte, hoogte en pixelformaat (RGB, RGBA,…)

4.4 OPENGL OMGEVING OPZETTEN Om te kunnen programmeren in OpenGL en Glut is het nodig om de OpenGL en GLUT librairies te linken. Sedert Visual Studio 2003 is OpenGL standaard voorzien. GLUT dient men te downloaden van de volgende website: http://www.xmission.com/~nate/glut.html Download daar het “glut-3.7.6-bin.zip (117 KB)” bestand. (Dit bestand staat tevens ook op de bijgeleverde cd in de directory “OPENGL”) Bij het unzippen zijn er 3 bestanden van belang voor ons. bestanden: glut.h, glut32.lib en glut32.dll.

Dit zijn de

Bij het ontwikkelen met Visual Studio, dient het bestand glut.h in de include directory te komen en glut32.lib in de lib directory. Wie een andere ontwikkelingstool gebruikt, kan de readme.txt raadplegen over hoe men z’n omgeving opzet. Wanneer Visual studio geïnstalleerd is in c:\Program Files, dan dienen de bestanden glut.h en glut32.lib dus respectievelijk te komen in: Voor Visual Studio2003: C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\PlatformSDK\\include\gl\glut.h C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\PlatformSDK\\lib\glut32.lib Voor Visual Studio2005: C:\Program Files\Microsoft Visual Studio 8\VC\PlatformSDK\Include\gl\glut.h C:\Program Files\Microsoft Visual Studio 8\VC\PlatformSDK\lib\glut32.libl

Het glut32.dll bestand is nodig wanneer men de gecompileerde GLUT code wil uitvoeren. Dit bestand dient in dezelfde directory als de applicatie te komen. Een gemakkelijker manier is om dit bestand in je c:\windows\system32 directory te plaatsen. Dit voorkomt dat je een glut32.dll exemplaar in ieder directory van een gemaakte GLUT-applicatie dient te plaatsen. Het probleem hierbij is dat wanneer je de applicatie op een andere machine wilt runnen, je niet mag vergeten om de glut32.dll mee te kopiëren.

Philippe Vandewalle

pagina - 50 -


2006-2007

Om gebruik te kunnen maken van de GLUT functies, Dient men eerst <windows.h> te includen zodat glut kan communiceren met het onderliggende window systeem. Het is niet nodig om te include’en aangezien glut dit reeds doet. Wil men dus gebruik kunnen maken van opengl en glut, dan dient men volgend code bovenaan ieder bestand te include’en:

#include<windows.h> #include

4.5 LINKS

De OpenGL website, met tal van voorbeelden, API en een forum www.opengl.org De GLUT website, met de te downloaden librairy + broncode. Hier is ook documentatie over glut te vinden. www.xmission.com/~nate/glut.html Voorbeelden van OpenGL applicaties + broncode www.keesmoerman.nl/opengl.html Tutorials met OpenGl en GLUT nehe.gamedev.net

Philippe Vandewalle

pagina - 51 -


Hoofdstuk 5:

2006-2007

CadrgViewer

5.1 DOELSTELLING 5.1.1 INLEIDING De CadrgViewer dient te fungeren als een soort beheersmodule voor de geladen CADRG-tiles waarmee het CADRG-beeld wordt gegenereerd. De CadrgViewer moet bepalen welke tiles er moeten worden geladen om het beeld op te bouwen tijdens een flight-over. Het laden van de tiles wordt dan over gelaten aan de CadrgReader.

5.1.2 VAKJARGON EN DEFINITIES Range

Onderliggende CADRG-tiles

View

VIEW: De view is voor de piloot het zichtbare beeld in de cockpit met de CADRG-beelden. De breedte van de view kan door de piloot worden ingesteld door de range. RANGE: De range bepaald de uitgestrektheid van het gebied, weer gegeven in de view, in de breedte. Deze wordt uitgedrukt in “nautical mile”. Een nautical mile1 is een lengte eenheid die over de gehele wereld wordt gebruikt voor maritieme of luchtvaartdoeleinden. POSITION: De plaats waar men zich bevindt boven het aardoppervlak. Bepaald door lengte~ en breedtegraad (longitude and latitude). Deze wordt periodiek verkregen. DIRECTION: de richting naar waar de punt van het vliegtuig wijst. De eigenlijke richting naar waar men aan het vliegen is. Deze wordt periodiek verkregen. SCALE LIBRARY: De CADRG databank kan gegevens bevatten met verschillende schalen. Hoe kleiner de schaal, hoe gedetailleerder uiteraard, maar deze stelt dan ook hogere eisen aan het systeem (meer geheugen en processortijd) De gebruiker kan hierbij een voorkeursschaal opgeven, zodat eerst aan de CADRGreader een aanvraag wordt gedaan voor deze schaal. Indien geen data gevonden in de databank voor deze schaal, wordt automatisch naar corresponderende data gezocht in een andere aanwezige schaal.

1

Eén nautical mile = 1,852km = 1,150779 mile = 1 arc minute

Philippe Vandewalle

pagina - 52 -


2006-2007

CADRG-TILE: Dit is een elementaire afbeelding waaruit de view wordt opgebouwd. Een CADRG-tile is een afbeelding van 256 x 256 pixels met bijhorende schaal en positie.

5.1.3

VEREISTEN

Het hoofddoel van de CADRG-viewer is om afhankelijk van: • de positie • direction • de range van de view • en de gewenste scale librairy een corresponderend beeld te genereren. Daarbij moeten de nodige tiles worden opgehaald via de CADRG-reader. De CADRG-viewer moet dan verder instaan voor het beheer van deze geladen tiles. Wanneer de viewer dan over de benodigde tiles beschikt, dient deze de afzonderlijke tiles te assembleren tot een geheel beeld met behulp van OpenGL. Zie onderstaande figuur voor een schematische voorstelling. Position Direction Range v/d view Gewenste scale librairy

• • • •

CadrgViewer VIEW

CadrgReader

CADRG-data

Een bijkomende vereiste is om zo weinig mogelijk te moeten lezen van het secundaire geheugen (=flashgeheugen). Omdat veelvuldig lezen/schrijven van de databus naar het flashgeheugen de performantie van het systeem naar beneden haalt. Daarom dient men er voor te zorgen dat de tiles slechts éénmaal dienen te worden gelezen. Indien men in de toekomst dus nog beelden zal moeten genereren met een dergelijke tile als component, dient men deze in het geheugen te houden voor later gebruik. Pas wanneer men de tile niet meer nodig zal hebben om volgende beelden te genereren, mag men ze uit het geheugen verwijderen. De tiles dienen daarom in een gepaste gegevensstructuur te worden bewaard (zie hoofdstuk “Analyse” voor de uitwerking). Deze gegevensstructuur moet het mogelijk maken om de tiles snel terug te vinden op basis van lengte en breedtegraad, maar ook op basis van hun onderlinge positie. •

Zoeken via onderlinge positie: om bij het renderen van het beeld met OpenGL, snel de map te kunnen overlopen

Philippe Vandewalle

pagina - 53 -

Thesis: Advanced graphics for avionics displays •

2006-2007

Zoeken via lengte~ en breedtegraad, om snel te weten of een tile reeds is geladen of niet. Indien nog niet geladen, wordt deze dan aangevraagd aan de CadrgReader.

Ook wanneer een tile overbodig wordt, omdat het vliegtuig reeds verder is gevlogen, is het de taak van de CadrgViewer om deze uit de structuur met geladen tiles te verwijderen. Door de piloot wordt een “range” ingesteld (zie “Vakjargon en definities”, hiervoor). Er moeten dus steeds voldoende CADRG-tiles geladen worden om het gebied te kunnen bedekken, bepaald door de range. Het bepalen van het aantal tiles die in het geheugen dient te worden gehouden behoort ook tot de taken van de CadrgViewer omdat het vliegtuig ook een bepaalde richting heeft (draaihoek), moeten er ook steeds voldoende tiles geladen zijn om de view te kunnen construeren bij iedere draaihoek. Het bedekte gebied moet dus een bepaalde cirkel omschrijven die bepaald wordt door de Range en hoogte/breedte verhouding van de view. Telkens wanneer de CadrgViewer input krijgt van een nieuwe lengte~ en/of breedtegraad van het vliegtuig, dient te worden bepaald of het beeld een pixel is opgeschoven. Dit dient te gebeuren aan de hand van de schaal en CADRGresolutie. Indien het beeld dient te worden opgeschoven, wordt eerst de structuur met tiles overlopen om te kijken of deze nog in staat is om de view te bedekken. De CadrgViewer dient daarbij te bepalen of er tiles moeten worden bij geladen. Of indien tiles overbodig zijn geworden moeten deze worden verwijderd. Ook is het nodig dat de CadrgViewer tiles kan assembleren die afkomstig zijn van verschillende scale-librairies. Dit kan nodig zijn wanneer de dekking van bijvoorbeeld de huidig gebruikte database ten einde strekt. Er dient dan te worden overgeschakeld naar een andere CADRG-bron om zo de piloot nog te voorzien van een relevant beeld. Dit wil dus zeggen dat de het geen garantie is dat de tiles zich gaan gedragen als een “nette” matrix van rijen en kolommen.

Tiles uit kleine scale librairy VIEW Tiles uit grotere scale librairy

Het is dus mogelijk dat een tile-structuur zoals op bovenstaande figuur zich voordoet. Bij het onderzoeken van een gegevensstructuur om de onderlinge positie van de tiles bij te houden, zal hiermee rekening moeten worden gehouden.

Philippe Vandewalle

pagina - 54 -


2006-2007

5.2 ANALYSE 5.2.1 ANALYSE VAN EEN DATASTRUCTUUR VOOR HET BIJHOUDEN VAN DE ONDERLINGE POSITIE VAN DE CADRG-TILES EN DE OPBOUW VAN HET CADRG-FIELD De CadrgViewer dient dus te voorzien in een administratie waaruit men kan afleiden welke tiles dienen te worden geladen om een volledig beeld te kunnen weergeven. (bepaald door positie, richting en range). Om te weten welke tiles men moet laden, zijn er 2 zaken van belang: 1. Welk gebied moet er kunnen bedekt worden met de tiles om zo een volledig gedekt beeld te kunnen construeren? 2. Welke tiles bevinden zich reeds in het geheugen, zodat we weten welke niet meer moeten geladen worden. We moeten dit ook weten om deze tiles eventueel vrij te geven wanneer er wordt verder gevlogen en ze dus overbodig zijn. Het voorzien van antwoord op deze vorige 2 vragen is de core-business van de tile-administratie van de CadrgViewer. Als antwoord op de eerste vraag dienen we dus een gebied af te bakenen. Dit gebied zullen we verder in deze thesis het CADRG-field noemen. 5.2.1.1 BEPALEN CADRG-FIELD Om te voldoen aan de vereisten, beschreven in het vorige hoofdstuk, dient de view te kunnen roteren op het CADRG-field, terwijl het beeld steeds volledig blijft. Daarom zal het CADRG-field een cirkel beschrijven. (zie onderstaande figuur)

CADRG-field

Range

View.height VIEW

View.length

Philippe Vandewalle

pagina - 55 -


2006-2007

De straal zal dan bij gevolg gelijk zijn aan de halve diagonaal van de view, en bekomt men met volgende formule: Radius

[meter]=

sqrt((View.length[pixels])²+(View.height[pixels])²) x 2

Range[meters] . View.length[pixels]

5.2.1.2 DATASTRUCTUUR VAN HET CADRG-FIELD De datastructuur van het CADRG-field zou het moeten mogelijk maken dat, wanneer het CADRG-field is opgesteld:

We snel de view kunnen renderen.

We snel een CADRG-field kunnen opstellen voor een nieuwe locatie, met behulp van de gegevens uit het CADRG-field van de vorige locatie

Aan de hand van de voorlopige opbouw van het CADRG-field gemakkelijk kunnen bepalen welke tiles moeten worden bijgeladen om tot een volledig beeld te komen.

Om de datastructuur op te stellen voor het CADRG-field, moeten we ons eerst afvragen welke data deze bevat. Het CADRG-field is een verzameling van CADRG-tiles. Om deze tiles te kunnen assembleren tot één view, moeten we hun onderlinge posities kennen. Aangezien we een beeld moeten kunnen vormen met tiles uit mogelijk verschillende schaal bibliotheken, is het mogelijk dat een tile meerdere directe buren heeft aan één zijde. (Zie onderstaande figuur)

Tiles uit kleine scale librairy VIEW Tiles uit grotere scale librairy

Het zou dus zeker niet mogelijk zijn om een 2-dimensionale tabel te gebruiken hiervoor. Trouwens, ook het totaal aantal tiles varieert dynamisch. Het 2-dimensionaal gerangschikt bijhouden van de tiles in een Kd-Tree, lijkt hier een goede oplossing. Maar omdat we toch nooit gaan opzoeken in het CADRG-field, is deze implementatie te duur. Aangezien we het CADRG-field enkel snel moeten kunnen overlopen, is een datastructuur met het karakter van een gelinkte lijst hier de beste oplossing.

Philippe Vandewalle

pagina - 56 -


2006-2007

Deze voorstelling lijkt echter iets te simpel, want de oplossing moet ook rekening kunnen houden met volgende zaken: •

Continuïteit geschied in 2 dimensies.

•

Er heerst geen regelmaat in de locatie en voorkomen van de nodes.

Continuïteit geschied in 2 dimensies. Omdat de view zal opgebouwd worden uit meerdere rijen en kolommen tiles, zal het hier minstens moeten gaan om een gelinke lijst met pointers in meerdere dimensies ( een boom structuur). Er heerst geen regelmaat in de locatie en voorkomen van de nodes. Doordat het beeld kan bestaan uit tiles van verschillende CADRG-bronnen, kan het zijn dat de ene tile groter moet worden afgebeeld dan de andere om een uniform beeld te krijgen. Hierdoor kan het aantal buren van een tile variëren. Hierin onderscheiden we 3 gevallen: Bovenbuur is dezelfde als de bovenbuur van een linker/rechterbuur: Dit is het gevolg van een beeld bestaande uit verschillende schaalbibliotheken, waarbij tile1 (zie figuur) groter moet worden afgebeeld dan tile2 en tile3.

Tile1

Hierbij moet men dus rekening houden dat er meerdere verwijzingen zullen zijn naar tile1 Tile2

Tile3

Tussen de bovenbuur en de bovenbuur van een linker/rechterbuur bevinden zich meerdere nodes: Tile3

Tile1

…

Tile4

Tile2

Dit is terug een gevolg van een beeld bestaande uit verschillende schaalbibliotheken. Hierbij moet men rekening houden dat de tiles tussen tile3 en tile4 ook buren zijn van tile1 en tile2, maar er geen directe verwijzing naar bestaat.

Tussen de bovenbuur en de bovenbuur van de linker/rechterbuur bevinden zich geen nodes: Tile4

Tile1

Tile3

Tile2

Philippe Vandewalle

Dit is het gevolg van het mogelijk ontbreken van data in de CADRG-database of het voorkomen van een corrupt bestand Uit dit laatste geval volgt dat bij de opbouw van het CADRG-field men in elke richting zal moeten zoeken naar een volgende tile.

pagina - 57 -


2006-2007

5.2.1.3 BEELD VAN DE DATASTRUCTUUR. Wanneer we kijken naar de benodigde datastructuur om de onderlinge locatie van de tiles bij te houden, lijkt het alsof we een soort web van tiles nodig hebben. Hierbij heeft iedere tile maximum 4 pointers. Eén in elke richting die de uitbreiding van het Cadrgfield mogelijk maakt. CADRG-field

We moeten dus zolang tiles laden, totdat de rand van het CADRG-field bereikt is. 5.2.1.4 ABSTRACTIE VAN DE DATASTRUCTUUR. Wanneer we het vorig abstraheren, dan zien we dat dit eigenlijk een graaf is. En dus kan worden opgeslagen in een boom met volgende specifieke vereisten: •

Iedere node heeft 4 pointers, één in elke richting. Waarbij deze pointers eventueel leeg mogen blijven (om geen lussen te hebben bij het overlopen van de structuur bij het renderen)

•

De wortel van de boom, die we in dit geval de center-tile noemen, is de tile die het geografisch centrum van het Cadrgfield omvat

•

Een blad van de boom bevat de rand van het Cadrgfield

•

Er kunnen zich zijdelingse verbindingen voordoen in de boom. Een node kan een pointer bevatten naar een node die reeds aan de boom hangt. Dit komt omdat tiles kunnen verschillen in grootte, en dus kunnen buur zijn van meerdere tiles. In onderstaande figuur zijn 3 niveaus uitgewerkt op basis van de figuur bij 1.2.1.3) Center-tile

North-tile

Philippe Vandewalle

East-tile

South-tile

West-tile

pagina - 58 -


2006-2007

5.2.1.5 ATTRIBUTEN VAN EEN NODE We kunnen de tiles gemakkelijk als node gebruiken door extra velden bij te voegen. Om het CADRG-field te kunnen opbouwen en renderen, moet per node volgende zaken worden bijgehouden: •

*Data: Een pointer naar de data (de afbeelding, in bitmap formaat)

•

Nbytesdata: de omvang van de data in bytes

•

TextureId: de identificatie van de texture op de grafische kaart. (iedere texture krijgt van opengl een ID)

•

Fieldmembervalue: de versie van het Cadrgfield. Om een nieuw CADRG-field op te bouwen uit een vorig. Aan de hand van Fieldmembervalue weet men of de node reeds in het nieuwe CADRGfield is opgenomen.

•

*Direction[4]: een tabel van 4 pointers naar de buren. Om de boom te kunnen construeren (0=north, 1=east, 2=south, 3=west).

•

dist[4]: (distance) een tabel die de 4 afstanden (north, east, south, west) bijhoud van de tile tot de locatie van het vliegtuig. Dit is nodig om te kunnen berekenen waar tiles exact moeten worden afgebeeld bij het renderen.

In UML wordt dit:

0…4

Tile + + + + + +

data: void* nbytesdata: Int textureid: Int fieldmembervalue: Int direction: Tile*[4] dist : Int[4]

Philippe Vandewalle

1

pagina - 59 -


2006-2007

5.2.2 ANALYSE VAN EEN DATASTRUCTUUR DIE BIJHOUD WELKE TILES REEDS ZIJN GELADEN. Met behulp van de structuur uit vorig hoofdstuk weet de CADRG-viewer nu welke tiles hij nodig heeft om het beeld te construeren. Maar omdat een volgend beeld snel uit het vorige moet kunnen vloeien, is het een vereiste dat tiles maar één keer worden geladen. We hebben dus nog nood aan een structuur die bijhoudt welke tiles reeds zijn geladen. Om te weten of een tile reeds is geladen, moeten we die snel kunnen opzoeken in deze datastructuur. Omdat we tiles voor een bepaalde locatie willen raadplegen, moeten we dus geografisch kunnen zoeken. Een kd-boom zou hier terug een oplossing kunnen bieden. Toch brengt dit problemen met zich mee: Welk punt van de tile als sleutel kiezen? Om de tiles te kunnen rangschikken, hebben we een unieke geografische sleutel nodig voor de tile. We zouden bijvoorbeeld de linker~/rechter boven/~onderhoek of het middelpunt kunnen nemen. Maar als we zoeken naar een tile, dan kennen we de coördinaten van de hoeken van een tile niet. Het CADRG-field evolueert voortdurend. Omdat het CADRG-field voortdurend evolueert, door het verder vliegen van het vliegtuig, moet de kd-boom voortdurend worden aangepast. En om snel zoeken mogelijk te maken, dient de boom optimaal te zijn (= zo laag mogelijk) Omdat het optimaliseren van een kd-boom een dure operatie is, is de kd-boom hier dus geen verstandige keuze. 5.2.2.1 CADRG STRUCTUUR VOLGEN De CADRG structuur groepeert de tiles in CADRG-images. Een image bevat 36 (6x6) tiles. Een CADRG-image bevat ook nog metadata zoals “de coverage”. Dit zijn de NW, NO, ZW, ZO coördinaten van het gebied dat de image bedekt. Als we nu dergelijke structuur bijhouden, en voor elke tile in de image, een pointer naar de image, dan hoeven we enkel te controleren of de pointer bestaat om te weten of de tile reeds is geladen. 5.2.2.2 ZOEKEN NAAR DE IMAGE WAARIN DE TILE TUISHOORT Uiteraard moeten we er rekening mee houden dat er meerdere CADRG-images zullen zijn die we moeten doorzoeken. We zouden deze images terug kunnen ordenen in een kd-boom om snel te kunnen opzoeken, maar dan hebben we terug dezelfde problemen zoals hierboven beschreven. Aangezien het aantal images continu varieert en eerder laag is (1 image is reeds 1536 x 1536 pixels), kunnen we ze gewoon bijhouden in een gelinkte lijst. Zoeken gebeurt dan in O(n/36), met n gelijk aan het aantal tiles. Deze performantie lijkt op het eerste zicht niet zo goed. Maar omdat we door de aarde van de opbouw van het CADRG-field steeds de buur van een CADRG-tile kennen, kunnen we de performantie verhogen door de buur mee te geven die we laatst zochten. De kans dat een tile in dezelfde image valt als zijn buur is immers zeer groot.

Philippe Vandewalle

pagina - 60 -


2006-2007

Kansberekening veronderstel hieronder de 36 tiles die gegroepeerd zijn in een image. Er zijn 3 groepen tiles met elke een bepaalde kans dat hun buur in dezelfde image valt:

Verzameling tiles in de image.

: 4 kansen op 4 : 3 kansen op 4 : 2 kansen op 4 Sommatie van de kans dat een tile in dezelfde image valt als zijn buur is dus: 16 tiles x 4/4 + 16 tiles x 3/4 + 4 tiles x 2/4 = 30 kansen op 36 tiles = 30/36 = 83,33% De kans dat een image dus in O(1) wordt gevonden ipv O(n/36) is dus 83,33%, wat de gemiddelde performantie sterkt verhoogt. 5.2.2.3 ZOEKEN NAAR DE TILE IN DE IMAGE. Nu we weten in welke Image een tile zich kan bevinden, hoeven we enkel nog te zoeken in de CADRG-image. Aangezien de image een “coverage” bijhoudt, kunnen we de plaats van de tile in de image berekenen. De coverage bevat de lengte en breedtegraad van de 4 hoeken van de oppervlakte die wordt bedekt door de image. Door interpolatie van de gezochte locatie tussen deze hoeken, kennen we dus de rij en de kolom van de tile waarin deze locatie zich moet bevinden. Wanneer een pointer dan verwijst naar een tile, weten we dat deze geladen is, of wanneer de pointer leeg is, dienen we hem te laden. De performantie voor het zoeken van de tile binnen de image is dus O(1).

Philippe Vandewalle

pagina - 61 -


2006-2007

5.2.2.4 BEELD VAN DE DATASTRUCTUUR OM GELADEN TILES BIJ TE HOUDEN. De 2 dimensionale tabel met pointers zullen we integreren in een image, omdat deze behoort tot een bepaald CADRG-image. De enkele geladen images worden bijgehouden in een gelinkte lijst (= ImageList), zoals hiervoor omschreven. Onderstaande figuur toont een beeld van de datastructuur. ImageList IMAGE

IMAGE

Image meta data: colorlut, scale...

coverage,

Frame file bestand

Image meta data: colorlut, scale...

coverage,

Frame file bestand

...

geladen / gedecomprimeerde tiles Lege pointers voor eventuele nog te laden tiles 5.2.2.5 OVERBODIGE TILES TERUG VRIJGEVEN. Wanneer bij een “flight-over” het beeld opnieuw moet worden gerenderd, dient het CadrgField te worden geüpdate. Hiervoor wordt een beroep gedaan op reeds geladen tiles, en indien er nieuw een gebied moet worden bedekt, dan zullen we een nieuwe tile laten laden door de CadrgReader. Wanneer we echter ver genoeg zijn zodat we een bepaalde tile niet meer nodig hebben, dan zullen we zijn betreffende destructor moeten aanroepen. Het probleem hierbij is dat we in de verzameling geladen tiles niet weten welke nog worden gebruikt bij het renderen van het CadrgField. Daarom zullen we een extra veld per tile bijhouden, namelijk “fieldmembervalue”, (zie UML van CADRGTile hierna). Dit veld bevat een waarde die gelijk is aan de fieldmembervalue van het huidige CadrgField. Bij het herconstrueren van het CadrgField wordt de fieldmembervalue van het CadrgField aangepast om ervoor te zorgen dat de waarde verschilt met de vorige. Wanneer we dan een reeds geladen tile opnemen in het CadrgField, dan stellen we de waarde van het fieldmembervalue attribuut van deze tile gelijk aan het fieldmembervalue attribuut van het CadrgField. Wanneer het CadrgField dan compleet is, voeren we een “cleanCadrgField()” methode uit, die alle tiles waarvoor de fieldmembervalue niet gelijk is aan deze van het huidige CadrgField verwijderd. Philippe Vandewalle

pagina - 62 -


2006-2007

5.2.2.6 UML-SCHEMA VAN DE OBJECTEN DIE DE STATUS VAN HET CADRG-FIELD BIJHOUDEN.

0.* CadrgTile + data: unsigned char* + nbytesdata: unsigned int + x_index: int + y_index: int + textureid: int + fieldmembervalue: int + direction: CADRGTile*[4] + dist: int[4] +newCadrgTile(image* CadrgImage, x int, y int, comp_lut* unsigned char) CadrgTile * +deleteCadrgTile(tile* CadrgTile) -get_rpf_image_tile(file Frame_file*, tno long, table unsigned char* ,tile unsigned char*) short

0.1 ImageList

1 CadrgImage + color_lut: byte[3]* + compression_lut: unsigned char* + references: int + nw_lat: double + nw_long: double + sw_lat: double + sw_long: double + ne_lat: double + ne_long: double + se_lat: double + se_long: double + vert_interval: double + horiz_interval: double + zone: long + scale_library: char* + num_hor_tiles: int + num_ver_tiles: int + references: int +newCadrgImage(toc Toc_file*, impctl Import_controls*) CadrgImage* +deleteCadrgImage(image CadrgImage*)

1

Philippe Vandewalle

pagina - 63 -


2006-2007

5.3 REALISATIE De realisatie van de CadrgViewer zal erin bestaan door het implementeren van een soort flight simulator. De simulator zal over een bepaald gebied vliegen, waarbij voor een nieuwe locatie het CadrgField wordt geupdate en daarna wordt gerenderd. Als gebruiker zullen we volgende zaken kunnen: • sneller en trager over een gebied vliegen (eventueel ook stil hangen) • Naar links of rechts uitwijken. • Hoger of lager vliegen. • De “angle” van het vliegtuig wijzigen. Deze zaken kunnen we implementeren met OpenGL: • Door bij het renderen van het CadrgField te spelen met parameters zoals: rotate(), translate(),… • En door een locatie en snelheid bij te houden. Hierbij wordt de snelheid aangepast waneer men op de pijltoetsen drukt. Vooruit is versnellen, en achteruit is vertragen. Daarna wordt de volgende locatie berekend afhanelijk van de snelheid en het uitwijken (pijl naar links/rechts). Voor de implementatie verwijs ik naar de bestanden CADRGviewer.h en CADRGvieuwer.c. Hierin wordt een OpenGL venster aangemaakt en een rendercontext. Ook het definieren van functies die moeten worden uitgevoerd bij het opvangen van een event, zoals drukken op een bepaalde toets, wordt hier gedaan. Hieronder vindt U een lijst met toetsen die een bepaalde functionaliteit bezitten. Deze lijst wordt ook getoond in het consolevenster bij het opstarten van de applicatie. Usage: U or u: D or d: arrow-up: arrow-down: arrow-right: arrow-left: numpad-8: numpad-2: numpad-6: numpad-4: End: Q or q:

Philippe Vandewalle

UP: increase altitude\n"); DOWN: decrease altitude\n"); increase speed\n"); decrease speed\n"); rotate right\n"); rotate left\n"); rotate arrond Y-axis\n"); rotate arrond Y-axis\n"); rotate right\n"); rotate left\n"); stop, speed=0\n"); Quit application\n\n");

pagina - 64 -


2006-2007

5.3.1 RENDEREN VAN HET CADRGFIELD. Het tekenen van de CADRG-beelden op scherm wordt gedaan in de “drawCadrgField(tile)” procedure. Dit gebeurt door het doorlopen van de CadrgField boomstructuur. Dit wordt gedaan door de “drawCadrgField(tile)” procedure recursief op te roepen voor elke aanwezige buur van een tile. Per tile wordt dan een vierkant getekend (geen omtreklijn) waarbij het oppervlak wordt opgevuld met de corresponderende texture van de tile. Iedere hoek van de vierkant wordt getekend op een bepaalde afstand van het centerpunt (= waar het vliegtuig zich bevindt). Deze afstanden worden bijgehouden in het “dist[ ]” attribuut van het CADRGTile-object. • Dist[0]= noordelijke afstand van de tile tot centerpunt. • Dist[1]= oostelijke afstand van de tile tot centerpunt. • Dist[3]= zuidelijke afstand van de tile tot centerpunt. • Dist[4]= westelijke afstand van de tile tot centerpunt. Ook dienen de texturecoördinaten te worden gelinkt aan de corresponderende hoeken (zie hieronder: glTexCoord2f( X,Y)). Onderstaande code illustreert de “drawCadrgField()”-procedure. void drawCadrgField(CadrgTile* tile){ int i; //bind texture for this quad glBindTexture(GL_TEXTURE_2D, tile->textureid); glBegin(GL_QUADS); //vertex: down-left glTexCoord2f( 0.0,1.0); // Texture coordinates glVertex3f( tile->dist[3],tile->dist[2],0.0) //(x,y,z) //vertex: down-right glTexCoord2f( 1.0,1.0); // Texture coordinates glVertex3f( tile->dist[1],tile->dist[2],0.0); //(x,y,z) //vertex: up-right glTexCoord2f(1.0,0.0); // Texture coordinates glVertex3f( tile->dist[1],tile->dist[0],0.0); //(x,y,z) //vertex: up-left glTexCoord2f( 0.0,0.0); // Texture coordinates glVertex3f( tile->dist[3],tile->dist[0],0.0); //(x,y,z) glEnd(); //check the pointers if cadrgfield extends... for(i=0;i<4;i++){ if (tile->direction[i]!=(CadrgTile*)NULL) drawCadrgField(tile->direction[i]); //rec-call } return; } Philippe Vandewalle

pagina - 65 -


2006-2007

5.3.2 UPDATEN VAN HET CADRGFIELD Bij verder vliegen moet het beeld iedere keer worden aangepast aan de plaats waar men zicht bevindt. De verzameling tiles die deel uitmaken van dit beeld, het CadrgField genaamd, moet dus iedere keer worden geüpdate. We zullen dit doen door telkens een nieuw CadrgField aan te maken op basis van het vorige. Door de vorige structuur te hergebruiken kunnen we trouwens heel wat voordeel halen uit vorig reken~ en zoekwerk. Het CadrgField is eigenlijk niets anders dan een boomstructuur met speciale vereisten zoals beschreven in puntje Fout! Verwijzingsbron niet gevonden.. De implementatie van deze boom wordt daarom door de CADRGTile struct gedaan. Het opstellen van deze boom daarentegen is heel wat ingewikkelder en wordt geïmplementeerd in de bestanden CadrgFactory.h en CadrgFactory.c. Hierin worden de losse CADRGTiles geassembleerd tot een CadrgField. Hieronder volgt een bespreking van de belangrijkste procedures van de CadrgFactory 5.3.2.1 NEWCADRGFIELD() We beginnen met het aanroepen van “newCadrgField(importcontrols)”. Hierin wordt de “CadrgFieldmembervalue” aangepast zodat deze verschilt van de vorige om nadien overbodige tiles te kunnen vrijgeven. Daarna wordt de tile gezocht waar de locatie in valt. Deze tile zal trouwens dienst doen als centertile (=root van de CadrgField-boom). Voor deze tile worden de noord~, oost~, zuid~ en west afstanden tot het centerpunt bepaald. En uiteindelijk probeert men de tile in iedere richting uit te breiden. Wanneer het CadrgField is geconstrueerd, worden de tiles die niet tot het actieve CadrgField behoren, uit het geheugen verwijdert met “cleanCadrgField()”. Code-extract: CadrgTile*

newCadrgField(Import_controls *impctl){

CadrgTile *roottile; double dx, dy; if (CadrgField_MemberValue == 1) CadrgField_MemberValue = 0; else CadrgField_MemberValue = 1; //get roottile for this location impctl->respect_scale=1; roottile = getTileForLocation(impctl, NULL); if(roottile==(CadrgTile*)NULL){ iError("CADRG-HOLE!, couldn't load roottile:\n”) return (CadrgTile*)NULL; } Philippe Vandewalle

pagina - 66 -


2006-2007

//calculate the position in frame and distance to N,E,S,Wborders dy=(application.imp_ctl.lat-roottile->coverage.sw_lat)/roottile>coverage.vert_interval; dx=(application.imp_ctl.lon-roottile->coverage.sw_long)/roottile>coverage.horiz_interval; roottile->dist[North] = (CADRG_TILE_PIXEL_WIDTH-dy)*roottile>coverage.vert_resolution; roottile->dist[East] = (CADRG_TILE_PIXEL_WIDTH-dx)*roottile>coverage.horiz_resolution; roottile->dist[South] = dy*roottile->coverage.vert_resolution*1.0; roottile->dist[West] = dx*roottile->coverage.horiz_resolution*1.0; roottile->fieldmembervalue = CadrgField_MemberValue; //try to expand in al directions expandCadrgField(roottile,North); expandCadrgField(roottile,East); expandCadrgField(roottile,South); expandCadrgField(roottile,West); cleanCadrgField(); return roottile; } 5.3.2.2 UITBREIDEN VAN HET CADRGFIELD: EXPANDCADRGFIELD() De “expandCadrgField()” procedure is de meest kritische procedure voor de CadrgViewer omdat hierin de CadrgTiles tot een CadrgField worden geassembleerd. De “expandCadrgField()” procedure probeert het CadrgField in een bepaalde richting vanaf een bepaalde tile uit te breiden. Hierbij moet worden getest of men nog mag uitbreiden in deze richting zonder de CadrgField-cirkel te overschrijden. Dit wordt gedaan door te testen of de afstanden van de hoeken van de huidige tile niet groter zijn dan de CadrgFieldRadius. void expandCadrgField(CadrgTile *ptile, Direction dir){ double radius1, radius2; double dy, dx; Import_controls impctl; CadrgTile *tile;

//calculate if we need to expand the map (if view limits not reached) radius1=sqrt(ptile->dist[dir]*ptile->dist[dir] + ptile>dist[(dir+1)%4]*ptile->dist[(dir+1)%4]); radius2=sqrt(ptile->dist[dir]*ptile->dist[dir] + ptile>dist[(dir+3)%4]*ptile->dist[(dir+3)%4]); if (radius1dist[(dir+1)%4]*ptile->dist[(dir+3)%4]<0 && Philippe Vandewalle

pagina - 67 -


2006-2007

abs(ptile->dist[dir])
A

Dir=west

B

Tile

D

Dir=east

C

Dir=south

CadrgfieldRangeradius

tabel Direction Radius1 Radius2 North A B East B C South C D west D A Om radius1 en radius2 te berekenen maken we gebruik van de stelling van Pythagoras. We zien hier dat we enkel nog mogen uitbreiden in de richtingen: east, south en west. Wanneer we het CadrgField verder mogen uitbreiden in de richting “dir”, dan controleren we eerst of deze tile reeds een buur heeft in deze richting. Indien nog geen buur, dan moeten we er één zoeken voor de eerst volgende locatie buiten de tile. Dit om een aaneengesloten beeld te krijgen. Zoeken naar een tile gebeurt in verschillende bronnen, waarbij de bron waarbij men snelst kan laden voorrang krijgt1.

1

Naar analogie met memoriemanagement. Waar men eerst het cache geheugen op de processor zal raadplegen en daarna het Ram geheugen en indien niet aanwezig uiteindelijk laden van het secundaire geheugen.

Philippe Vandewalle

pagina - 68 -


2006-2007

We zoeken eerst in dezelfde image als de huidige tile. We hebben hierbij trouwens 83.33% kans om reeds de tile te vinden. Daarna doorzoeken we de gehele verzameling geladen tiles naar de tile die deze locatie dekt. En wanneer we de tile dan nog niet vinden proberen we er één te laden van het secundair geheugen door gebruikt te maken van de CadrgReader. Wanneer de “fieldmembervalue” van de geladen tile dan verschillend is van deze van het CadrgField, dan weten we dat het gaat om een nieuwe tile die we moeten opnemen in de structuur en kunnen we de pointers aanpassen. Wanneer de “fieldmembervalue” echter gelijk is aan deze van de “CadrgFieldmembervalue”, dan weten we dat deze tile reeds eerder door een andere tile werd gelinkt en we hem niet mogen opnemen in het CadrgField. Anders zouden we immers lussen in het CadrgField genereren, waarbij er zich fouten zouden voordoen bij het renderen van de boom. Daarna moeten we enkel nog de afstanden tot de centerpositie aanpassen van de nieuwe tile en deze nieuwe tile ook proberen uit te breiden in elke richting. Dit doen we door opnieuw recursief de “expandCadrgField” procedure op te roepen. Vereenvoudigd code-extract: if (ptile->direction[dir]==(CadrgTile*)NULL){ //calculate the next point we need to load impctl = application.imp_ctl; //nieuwe locatie berekenen om aaneengesloten beeld te bekomen } impctl.respect_scale=1; //try loading in same scale tile = getTileForLocation(&impctl, ptile); if(tile==(CadrgTile*)NULL){ iError("CADRG-HOLE!, couldn't load tile); return; } if(tile->fieldmembervalue == CadrgField_MemberValue){ //tile is allready member of cadrgfield return; } else{//attach the new tile to the field ptile->direction[dir]=tile; ((CadrgTile*)ptile->direction[dir])-> fieldmembervalue = CadrgField_MemberValue; } } else{//use tile from previous times if(((CadrgTile*)ptile->direction[dir])-> fieldmembervalue==CadrgField_MemberValue){ //tile allready member of cadrgfield: break this connection to avoid loops ptile->direction[dir]=(CadrgTile*)NULL; return; } else{ tile = ptile->direction[dir]; Philippe Vandewalle

pagina - 69 -


2006-2007

((CadrgTile*)ptile->direction[dir])-> fieldmembervalue = CadrgField_MemberValue; } } //calculate new distances adjustDistances(ptile, ((CadrgTile*)ptile-> direction[dir]), dir); //try to expand in al directions expandCadrgField(tile,North); expandCadrgField(tile,East); expandCadrgField(tile,South); expandCadrgField(tile,West); } else{//the cadrg field must end here // cut cadrgfield ptile->direction[dir]=(CadrgTile*)NULL; //make sure it stops } return; }

Philippe Vandewalle

pagina - 70 -


2006-2007

5.4 RESULTAAT Dit is kort de werking van de CadrgViewer. Voor meer gedetailleerde implementatieaspecten verwijs ik naar de code op de CD in de directory “CADRGVIEWER”. Wanneer U de CadrgViewer wil testen, is het aan te raden het Readme.txt te lezen. De CadrgViewer moet immers beschikken over een CADRG-database. In het readme-bestand staat vermeld hoe men de omgeving moet opzetten en waar de databanken met de CADRG-data op de pc moeten worden gekopieerd. Onderstaande afbeelding toont een momentopname van de CadrgViewer in werking. Hierbij werd CADRG-data gebruikt afkomstig van ingescande aeronautical maps.

Philippe Vandewalle

pagina - 71 -


Hoofdstuk 6:

2006-2007

DTED

6.1 INLEIDING De hoogte-informatie om een 3D synthetic ground map te maken voor deze thesis zal bestaan uit DTED data. DTED staat voor Digital Terrain Elevation Data. Om de werking en structuur van de DTED-reader (zie volgend hoofdstuk) te kunnen begrijpen, volgt eerst een toelichting over DTED.

6.2 OMSCHRIJVING DTED is gegroeid uit een militaire standaard die is ontworpen om hoogte-informatie per locatie te kunnen opslaan. Deze hoogte-informatie wordt opgeslagen als een uniforme matrix van hoogtewaarden tegenover MSL (Mean Sea Level) uitgedrukt in meter. DTED bestaat in verschillende niveau’s van detail (=de samplefrequentie van het aardoppervlak). DTED level1 specificeert een samplefrequentie van 3.0 seconden. Met 60 seconden per minuut en 60 minuten per graad, wil dit zeggen dat er 60 x 60 =1200 samplewaarden zijn 3.0 per breedtegraad. Voor DTED level2 is de samplefrequentie 1.0 seconde. 3600 samplewaarden per breedtegraad.

Er zijn dus 60x60 =

DTED is georganiseerd in losse bestanden. Tot en met DTED level2, wordt de hoogte-informatie van een vierkante graad bijgehouden in één bestand. Onderstaande tabel toont de karakteristieken van de verschillende DTEDlevels: level

samplefrequentie

afstand op grond

rij x kolom

bestand

0

30.000 sec

~1000 m

120x120

1x1 graad

1

3.0000 sec

~100m

1200x1200

1x1 graad

2

1.0000 sec

~30m

3600x3600

1X1graad

3

0.3333 sec

~10m

900x900

5x5min

4

0.1111 sec

~3m

540x540

1x1min

Philippe Vandewalle

pagina - 72 -


2006-2007

DTED level0 is afkomstig van DTED level1 men neemt hiervoor de gemiddelde waarde van 10x10 elevaties van level1. DTED level0 is gratis te downloaden van de website van NIMA: http://geoengine.nga.mil/geospatial/SW_TOOLS/NIMAMUSE/webinter/rast_roa m.html Voor deze thesis zullen we DTED level0 data gebruiken, gedownload van bovenstaande website.

6.3 STRUCTUUR VAN DTED 6.3.1 LOGISCHE STRUCTUUR Een DTED database bestaat uit een verzameling van losse bestanden. Deze bestanden bedekken afhankelijk van hun detail level een bepaald gebied. En een database bestaat enkel uit bestanden van één bepaald detaillevel. Per detaillevel kan door de bolvorm van de aarde, de sampelfrequentie langs de lengtelijn variëren. Een vierkante graad aan de noordpool zal immer minder oppervlakte bevatten dan een vierkante graad aan de evenaar. Hierdoor is DTED, net zoals CADRG, ingedeeld in zones. Let wel, de zones van DTED en CADRG lopen niet gelijk. Onderstaande tabellen geeft hiervan een overzicht voor DTED level0, level1 en level2 TABEL I: level 0 Zone breedtegraad breedtegraad interval I II III IV V

0° - 50° 50° - 70° 70° - 75° 75° - 80° 80° - 90°

30 30 30 30 30

seconds seconds seconds seconds seconds

TABEL II: level 1 Zone breedtegraad breedtegraad interval I II III IV V

0° - 50° 50° - 70° 70° - 75° 75° - 80° 80° - 90°

3 3 3 3 3


TABEL III: level 2 Zone breedtegraad breedtegraad interval I II III IV V

0° - 50° 50° - 70° 70° - 75° 75° - 80° 80° - 90°

Philippe Vandewalle

1 1 1 1 1


lengtegraadinterval 30 seconds 60 seconds 90 seconds 120 seconds 180 seconds

lengtegraadinterval 3 seconds 6 seconds 9 seconds 12 seconds 18 seconds

lengtegraadinterval 1 2 3 4 6

seconds seconds seconds seconds seconds pagina - 73 -


2006-2007

DTED kan men dus eerst logisch indelen in detaillevels, daarna de detaillevels in verschillende zones, om dan uiteindelijk bij een essentieel elevation matrix bestand te komen. Onderstaande figuur geeft hiervan een schematisch voorstelling. DTED

Database Level

0

1

Tile

Een DTED tile-bestand bevat ook een header die zowel het gebied beschrijft waarvoor het data bevat, als sample informatie. Hierover meer in de fysische indeling van DTED

6.3.2 FYSISCHE STRUCTUUR 6.3.2.1 DIRECTORIESTRUCTUUR Om DTED tiles te kunnen inlezen is vooral de fysische structuur van belang. Een DTED database (of directory) heeft volgende structuur

De database bestaat uit 2 hoofd subdirectories. “dted” die de data bevat en “text” die het “onc.dir” bestand bevat. De “dted” directory bevat de databestanden, georganiseerd volgens lengtegraad. De naam van de subdirectory beschrijft de lengtegraad. W staat voor westerlengte en E staat voor oosterlengte. Voor iedere lengtegraad waarvoor de database bestanden bevat is dus een subdirectory voorzien. In zo een subdirectory bevindt zich dan de data, met voor iedere breedtegraad een bestand. De bestandsnaam is van de vorm [hemisfeer:N/S][graden].dt[level]. Bovenstaande afbeelding is van een DTED level 0 database. Omdat een level 0 database is gedownsampeld van een level 1, bevat de level 0 database nog 3 extra bestanden per tile. Één voor de gemiddelde elevatie, de maximum~ en de minimum elevatie. Deze kan men gemakkelijk herkennen aan de extensie. Philippe Vandewalle

pagina - 74 -


2006-2007

De “text” directory bevat het “onc.dir” bestand. Dit is een ASCI bestand die voor elke databestand een entry bevat. Deze entries zijn op dezelfde manier gegroepeerd als de directoriestructuur. 6.3.2.2 BESTANDSSTRUCTUUR VAN EEN ELEVATIEBESTAND. Een elevatie bestand bestaat uit een set van verschillende headers die de locatie, de grootte en de samplefrequentie specificeren. De User Header Label (UHL) bevat een sentinal, een soort sequentie van bits waaraan we kunnen herkennen dat het om een dted bestand gaat en geen één of ander corrupt bestand waarvan de naam werd veranderd. Dan hebben we de lengtegraad en breedtegraad van het meest zuid-westelijke punt van de elevatiematrix. Gevolgd door de gebruikte intervallen van sampeling. Zowel langs de breedtegraad als langs de lengtegraad. Voor de volledigheid wordt ook meegegeven van de elevatiematrix.

nog

het

aantal

lijnen

en

kolommen

De Data Set Identification Header (DSI) bevat informatie over de producent de data (jaartal, producent code, land…). Deze header houd ook het dted level bij en de soort classificatie (=secret/confidential/unclassified) Het Accuracy Description Record nauwkeurigheid van de gegevens.

(ACC)

bevat

informatie

over

de

Data records bevatten de eigenlijke elevatie data. Één datarecord bevat de elevaties voor een gehele breedtegraad. De datarecords bevatten de data van west naar oost en de volgorde van de datarecords is van zuid naar noord. Voor een DTED level0 bestand met sampelfrequentie van 30 seconden zijn er 120 rijen x 120 kolommen. Zo dat er 121 records zijn met 121 waarden. Dit komt omdat de grenselevaties van een cel ook worden bijgehouden. 6.3.2.3 ELEVATIEWAARDEN De elevatiewaarden bestaan uit 2 bytes. En zijn opgeslagen in big endian unsigned notatie. We zullen dus de notie van de machine moeten controleren waarop de applicatie werkt, en afhankelijk daarvan de bytes swappen. Theoretisch is het dus mogelijk om een maximum elevatie van 216 =65 535 meter te hebben. Aangezien dit niet voorkomt op de aarde, behoud men de eerste bit (meest beduidende) voor het teken, zodat ook negatieve elevaties mogelijk zijn. Komt men bij het inlezen van het bestand dus een elevatie tegen van 32 768m of meer, dan weet men dat het gaat om een negatieve elevatie. Negatieve elevaties zijn opgeslagen in “signed magnitude” bitvolgorde. (= het eerste bit bepaald het teken).

Philippe Vandewalle

pagina - 75 -


2006-2007

6.4 LINKS http://www.nga.mil/ast/fm/acq/89020B.pdf Document met de militaire specificaties over DTED

http://www.vterrain.org/Elevation/dted.html korte uitleg over DTED.

http://www.fas.org/irp/program/core/dted.htm documentatie over samplefrequentie.

de

verschillende

DTED

detail

levels

met

hun

http://geoengine.nga.mil/muse-cgi-bin/rast_roam.cgi website waar men DTED level0 data gratis kan downloaden.

Philippe Vandewalle

pagina - 76 -


Hoofdstuk 7:

2006-2007

DtedReader

7.1 DOELSTELLING 7.1.1 INLEIDING De DtedReader zal er voor zorgen dat er voor een gegeven geografische locatie DTED hoogte data wordt geladen. Omdat de DtedReader later zal worden gebruikt om hoogte informatie in te lezen voor het genereren van de synthetic ground map, zal hij zo worden ontworpen zodat er meerdere aanvragen na elkaar kunnen worden gedaan. Om op deze aanvragen te kunnen antwoorden zal er terug een snel te doorzoeken structuur moeten worden opgezet om de aanwezige data te doorzoeken.

7.1.2 VEREISTEN 7.1.2.1 BASISVEREISTE De basisvereiste van de DtedReader is om voor een gegeven locatie (=lengtegraad en breedtegraad) en een DTEDlevel (= zie vorig hoofdstuk “DTED”), hoogteinformatie in te lezen.

Locatie - Lengtegraad - breedtegraad DTEDlevel

DtedReader

DTED database

De hoogteinformatie wordt ingelezen in een hoogtematrix van een DTEDtile object. Dit DTEDtile object zal dan in een latere fase worden doorgegeven aan de MapViewer om zo een 3D beeld te genereren. Bij de DtedReader zullen we deze DTEDtile voorlopig gebruiken om er een bitmap van te maken. We zullen dit doen door iedere elevatie een kleurwaarde te geven. De werking van de DtedReader kan dan gemakkelijk worden getest door het bitmap bestand te raadplegen.

Philippe Vandewalle

pagina - 77 -


2006-2007

7.1.2.2 DTED TABLE OF CONTENTS LIST OPSTELLEN. Om hoogteinformatie voor een bepaalde locatie op te halen, moeten we weten of die aanwezig is voor die bepaalde locatie en waar ze dan te vinden is. Daarom zal er bij het opstarten van de DtedReader, eerst moeten worden gezocht naar de aanwezige DTED bestanden. Vanaf een opgegeven startdirectory, die we het “dted path” zullen noemen, zal het filesteem worden doorzocht naar bestanden van de vorm “????.dt?”. van deze bestanden wordt hun path en geografische locatie dan in een snel te doorzoeken datastructuur gegoten. 7.1.2.3 DTEDTILES Bij een aanvraag, dient het bestand dan te worden gezocht die de corresponderende geografische locatie bevat. Indien er zo een bestand aanwezig is wordt het ingelezen. Het inlezen dient in één readinstructie te gebeuren om zo weinig mogelijk bestandstoegang te hebben1. Wanneer het bestand zich in het geheugen bevindt, dienen de verschillende velden dan in een DTEDtile structuur te worden geparst. Een DTEDtile dient minstens de elevatiematrix te bevatten, de geografische locatie die het omvat, en het aantal rijen en kolommen van de matrix. 7.1.2.4 TESTEN DOOR MIDDEL VAN BITMAPS. Wanneer de DTEDtile is geparst, moeten we nog kunnen testen of de data wel correct werd ingelezen. We zullen daarom een soort “saveDTEDasBitmap()” procedure moeten voorzien. Deze procedure zal de elevatiematrix omzetten naar kleurcodes en als een bitmap naar het bestandsysteem schrijven.

7.2 ANALYSE 7.2.1 SKELET VAN DE DTEDREADER De opbouw van de DtedReader bestaat net zoals de CadrgReader terug uit 3 grote blokken, namelijk: • De initialisatie. • Het verwerken van één of meerdere aanvragen. • Het opruimen van de gebruikte datastructuren. 7.2.1.1 DE INITIALISATIE: Bij de initialisatie van de DtedReader wordt de DTED TOC (table of contents) structuur opgesteld. Hierbij wordt het filesysteem vanaf het “dtedpath” doorzocht op zoek naar bestanden van de vorm “????.dt?”.

1

Wanneer we de velden van het bestand één voor één zouden inlezen, zou er veel te veel synchronisatietijd nodig zijn tussen het secundaire geheugen en de applicatie. Philippe Vandewalle

pagina - 78 -


2006-2007

bij het opstellen van de zoekstructuur wordt een hulpstructuur gebruikt waarin we bij het doorlopen van het bestandssysteem de verwijzingen naar de Procesflow: Initialisatie

Geheugen

Recursief de subdirectories vanaf het dtedpath doorzoeken naar dted bestanden. Gevonden bestand is ????.dt? bestand

Van het gevonden bestand wordt het relatieve pad vanaf het dtedpath opgeslagen. Daarna wordt de bestandsnaam geanalyseerd om zo de geografische locatie te weten te komen.

Wanneer we al de bestanden hebben gevonden, wordt de opzoek datastructuur aangemaakt

DtedToclevel 0…

DtedToclevel 1

DtedToclevel n

gevonden bestanden voorlopig in opslaan. Pas wanneer alle bestanden zijn gevonden wordt de definitieve structuur opgesteld. Dit stelt ons in staat om efficiënt geheugen te reserveren en waarbij we de gegevens bij benadering haast kunnen zoeken door indirecte adressering. 7.2.1.2 VERWERKEN VAN AANVRAGEN VOOR ELEVATIEDATA: inputlocatie: vb (50°NB;1°OL) Procesflow: verwerken van dted aanvragen

De gevraagde geografische locatie opzoeken in de DTED TOC list. Hiervoor zoeken we eerst de gepaste level TOC en daarna zoeken we de locatie.

Locatie gevonden?

NEE

Geheugen

DTED TOC 0

DTED TOC 1

JA Het gevonden bestand laden en parsen in een DTEDtile object N050.dt0

DTEDtile

De aangevraagde locatie wordt in de bovenbeschreven datastructuur opgezocht en indien aanwezig wordt het betreffende bestand geladen.Het Philippe Vandewalle

pagina - 79 -


2006-2007

DTED bestand wordt in één read instructie ingelezen. Via een lopende pointer en de gekende byte-offsets, kan men dan de velden in een DTEDtile parsen. 7.2.1.3 HET BEËINDIGEN: Bij het beëindigen worden de bovenbeschreven datastructuren opgeruimd door hun destructors aan te roepen.Onderstaande afbeelding toont de flowlayout. Procesflow: CadrgReader opruimen Geheugen van aanwezige DTED tiles vrijgeven.

Geheugen van de DTED TOC lijst vrijgeven

7.2.2 ANALYSE

Geheugen DTEDTile

DTED TOC lijst


INITIALISATIE PROCES Bij de initialisatie moeten we een lijst opstellen die de bedekking van de DTED database bevat. Het is belangrijk dat we deze snel kunnen doorzoeken. En aangezien het opstellen van deze structuur maar éénmalig is, mag het opstellen van deze structuur gerust iets meer tijd in beslag nemen. 7.2.2.1 TIJDELIJKE DTED TOC HULPSTRUCTUUR. Voor het opstellen van deze structuur zullen we gebruik maken van een tijdelijke hulpstructuur. In de code op de cd is deze geïmplementeerd in het bestand “DTED_TOC.h” als “DTED_world”. De applicatie zal DTED data kunnen laden tot en met level 2. Ieder bestand heeft dan juist een bedekking van één vierkante graad. De tijdelijke hulpstructuur zal bestaan uit een 2 dimensionale tabel, van 360 kolommen en 90 rijen. Dit is voldoende om de gehele aarde te bedekken. (Één vierkante graad per cel.) Een cel zal een mogelijke pointer naar een string bevatten. De string is het relatieve pad, vanaf het dted_path naar het betreffende bestand die de hoogte informatie bevat voor de locatie. Hierbij is de rij index de breedtegraad, en is de kolom index de lengtegraad. Omdat er meerdere DTED levels bestaan zullen we meerdere van deze hulpstructuren voorzien. Deze worden dynamisch aangemaakt en in een gelinkte lijst gestopt. Dit omdat het aantal databases met verschillende detail level eerder laag is. Eigenlijk meestal maar 1. We zijn nu klaar om het bestandssysteem te doorlopen. Wanneer we een bestand tegen komen van de vorm ???.dt?, dan weten we dat het om een DTED bestand gaat. Het laatste karakter van de extensie bepaald het detaillevel. Hierdoor weten we in welke hulpstructuur we moeten toevoegen. Het eerste karakter van de bestandsnaam bepaald de hemisfeer (North of South). Het tweede en derde karakter bepalen dan het aantal graden. Zo weten we in welke rij van de hulpstructuur we het pad moeten opslaan

Philippe Vandewalle

pagina - 80 -


2006-2007

De lengtegraad van het bestand kan men afleiden uit de naam van de bovenliggende directory. Hierdoor weten we nu ook de kolom waarin we moeten toevoegen. Na het doorlopen van het bestandssysteem beschikken we dan over een 2 dimensionale tabel met hier en daar ingevulde pointers. Zie onderstaande schematische voorstelling van de hulpstructuur. Dtedlevel 0 hulpstructuur 0

1

2

3

Dtedlevel 1 hulpstructuur

… … … … … 360

1

0

1

2

3

… … … … … 360

1

2

p

p

p

…

p

p

p

p

180

2 …

p

p

180

p

p

Wanneer we beschikken over de hulpstructuur kunnen we dan de DTED TOC list opstellen. Deze moet voor verschillende detail levels snel een verwijzing kunnen bieden naar het betreffende bestand. Omdat we reeds beschikken over de hulpstructuur weten we over hoeveel detaillevels we beschikken, zodat we een tabel met directe adressering kunnen voorzien naar de verschillende DTED TOC objecten. 7.2.2.2 HET DTED TOC OBJECT Het DTED TOC object van een bepaald DTED level, moet een pad kunnen bieden naar een bestand voor een gegeven geografische locatie. We zullen hiervoor de hulpstructuur transformeren naar een structuur die meer efficiënter het geheugen gebruikt. Tijdens het opstellen van de hulpstructuur zullen we een extra 1 dimensionale hulp tabel voorzien, met evenveel cellen als er rijen zijn in de hulpstructuur. Deze hulptabel zal het aantal cellen bijhouden die zijn ingevuld in een bepaalde rij. We initiëren deze hulptabel op 0 en telkens als we een pad toevoegen aan de hulpstructuur, verhogen we de corresponderende teller in de hulptabel met 1. Door het aantal cellen te tellen in de hulptabel waarvan de teller meer dan 0 bedraagt, weten we hoeveel rijen er een waarde bevatten. Met andere woorden weten we dus hoeveel verschillen breedtegraden we hebben. We voorzien hiervoor een 1 Dimensionale tabel waarbij we de verschillende breedtegraden in oplopende volgorde bijhouden. Dit stelt ons in staat om later geïnterpoleerd – binair te zoeken. (zie hierna). We slaan deze tabel, samen met het aantal breedtegraden op in een DTED_TOC object. En door het aantal ingevulde pointers te tellen per breedtegraad, weten we ook hoeveel geheugen we moeten reserveren per breedtegraad om de lengtegraden bij te houden. We zullen de lengtegraden ook in gesorteerde volgorde bijhouden. Per DTED_TOC object houden we dus een 1 dimensionale gesorteerde tabel bij, voor de verschillende lengtegraden samen met het aantal. Deze worden opgeslagen in een DTED_LAT_TOC object (LAT = latitude) Philippe Vandewalle

pagina - 81 -


2006-2007

Een pad naar een bestand wordt opgeslagen in een DTED_entry object. Dit bestaat uit 3 velden: een latitude, een longitude en een pointer naar een pad. De resulterende structuur ziet er dan uit zoals op onderstaande figuur. DTED_TOC_List: Maxlevel Dtedtoc[p]

=

p

DTED_TOC Level = 1

DTED_LAT_TOC: DTED … entry 1

Count = j … …


Count = k … …


Count = l … …


Count = n … …

DTED entry j

Count = m Tabel met pointers naar de DTED_LAT_TOC objecten

DTED entry k

DTED entry l

DTED entry n

Vereenvoudigd stelt deze structuur een 2 dimensionale tabel voor met onregelmatige vorm zoals hiernaast afgebeeld. Om te zoeken moeten we dan eerst de gepaste latitude zoeken op de eerste kolom, en dan de gepaste longitude in de rij ernaast.

7.2.2.3 ZOEKEN NAAR DE GEVRAAGDE ENTRY Als we naar een bepaalde entry (= pad naar een dted bestand) willen zoeken, dan moeten we 3 dingen weten: - het detaillevel - de breedtegraad (latitude) - de lengtegraad (longitude) in de DTED_TOC_List kunnen we dan de DTED_TOC selecteren door in de tabel het element te kiezen met index = detaillevel. (zoeken is hier O(1)) Daarna moeten we in de DTED_TOC de juiste breedtegraad zoeken. Aangezien deze in een gesorteerde tabel voorkomen waarbij we het aantal elementen kennen, kunnen we hier binair gaan zoeken. (zoeken is dan O(log(n)). We kunnen de performantie nog opdrijven door geïnterpoleerd te gaan zoeken. En wel als volgt: Philippe Vandewalle

pagina - 82 -


2006-2007

We kennen de kleinste waarde = dted_lat_toctab[0]. En we kennen de grootste waarde = dted_lat_toctab[count-1]. Door de gezochte waarde nu te interpoleren tussen de grootste en de kleinste waarde kunnen we een snelle schatting maken van de te kiezen index. Wanneer we het gevonden element met de berekende index, dan vergelijken met de te zoeken waarde, kan het zijn dat deze nog niet overeenkomt. We herhalen dan de vorige stappen, zoals bij binair zoeken, tot we de juiste waarde vinden. of tot de beginindex = eindindex-1. Deze manier van zoeken is dus veel sneller dan binair zoeken. We moeten er wel rekening mee houden dat de waarden niet mooi aaneensluitend zijn. Zo is het mogelijk dat een extreme waarde aan het begin of het einde van de tabel de zoekopdracht aanzienlijk vertraagd omdat de berekende index dan geheel niet overeenkomt met de werkelijke index van de te zoeken waarde. Daarom zullen we voor het zoeken naar de gepaste breedtegraad een combinatie van binair zoeken en geïnterpoleerd zoeken gebruiken. We berekenen eerst de binaire zoekindex “bindex” en den de geïnterpoleerde index “iindex” en nemen van beiden het gemiddelde. Deze implementatie is veel sneller dan gewoon binair zoeken (of binaire boom zoeken O(log(n))), en is minder gevoelig voor een onregelmatige stijging van de sleutelwaarden. Om de juiste lengtegraad te zoeken kunnen we op juist dezelfde manier werken als om de breedtegraad te zoeken. De totale performantie om een entry te zoeken met het aantal detail levels=l het aantal breedtegraden=m en het aantal lengtegraden per breedtegraad=n, wordt dan: Het juiste detail level bepalen: O(1) De juiste breedtegraad bepalen: beter dan O(log(m)) door interpolatie De juiste lengtegraad bepalen: beter dan O(log(n)) door interpolatie Totaal: O(1) +

beter

O(log(m)) +

beter

O(log(n))

Indien we de TOC hadden geïmplementeerd met een kd-tree om geografisch te zoeken, dan was de performantie voor het zoeken gemiddeld = O(1) + O(log(n*m) = O(1) + O(log(m)) + O(log(n)). Indien we kijken naar onze implementatie met een onregelmatige 2 dimensionale tabel, dan zien we dat de performantie beter is door het interpoleren. Hierdoor is deze implementatie dan gerechtvaardigd.

Philippe Vandewalle

pagina - 83 -


2006-2007

7.2.2.4 UML KLASSENDIAGRAM VOOR HET INITIALISATIEPROCES Als we de hierboven omschreven klassen in een UML schema gieten met elk hun benodigde attributen, dan bekomen we onderstaand schema.

1

DTED_List + maxlevel: int +newDTED_list (char* dted_path); DTED_list *

0..*

DTED_entry + lat: int + lon: int + path: char*

1

+deleteDTED_list(DTED_list* dted_list);

0..* +getEntryFromDTEDlist(DTED_list* list,int level, int lat, int lon);

DTED_LAT_TOC + count: int

1 +printDTED_list(DTED_list* dted_list);

0..*

DTED_LEVEL_TOC + count: int + level: int

* DTED_TOC + count: int + level: int + newDTED_TOC (DTED_world* dtedworld); DTED_TOC *

1

+deleteDTED_TOC(DTED_TOC* toc); +getEntryFromDTEDtoc(DTED_TOC * toc, int lat, int lon); DTED_entry* +printDTED_TOC(DTED_TOC* toc); + printDTED_entry(DTED_entry* entry);

Philippe Vandewalle

pagina - 84 -


7.2.3 ANALYSE

2006-2007


VERWERKEN VAN DE AANVRAGEN VAN EEN DTED-TILE. Nu we beschikken over een snel te doorzoeken inhoudsopgave van de bedekking van de databases, zullen we onderzoeken hoe we een DTED-bestand kunnen laden en welke structuren we hiervoor nodig hebben. 7.2.3.1 DTED-READER We zullen een DTED-Reader object voorzien waarbij we het laden van een DTED-bestand en het maken van een DTED-tile door de DTED-Reader laten verzorgen. Verder zal de DTED-reader enkel over 2 attributen beschikken. Namelijk het “dted_path”, die de start directory van de DTED-database bevat. Wanneer we dan een bestand wensen te laden moeten we het relatieve pad laten voorgaan door het “dted_path”. Het tweede attribuut is de bekomen DTED_list uit vorig hoofdstuk. Wanneer we trouwens een DTEDreader object aanmaken (newDTEDreader()), zal deze ervoor zorgen dat de zoekstructuur wordt opgesteld. Een nieuwe tile laden gebeurt dan door een methode aan te roepen van de DTEDreader. UML schema van den DTED-reader attributen en methodes:

+ + + + + +

DTEDreader dtedpath: char* dtedlist: DTED_List* newDTEDreader(char* dted_path); DTEDreader* deleteDTEDreader(DTEDreader* reader); loadDTEDtile(DTEDreader* reader, int level, int lat, int lon); printDTED(DTEDreader* reader);

DTEDtile*

7.2.3.2 DTED-TILES De bestandsstructuur van een DTED-bestand is eerder simpel in vergelijking met dat van een CADRG-bestand. Daarom hebben we maar 1 structuur nodig om een DTED-bestand te laden, namelijk een DTEDtile. De geografische locatie van een DTED-bestand bevat enkel discrete waarden en bevat altijd een volledige vierkante graad. Daarom is het voldoende om voor een DTEDtile enkel de geografische locatie van de zuidwestelijke hoek te bewaren. De overige coördinaten kunnen worden afgeleidt door er 1° bij te tellen. De data bestaan uit een matrix van 2byte elevatiewaarden. Omdat de breedte en de hoogte van de matrix afhankelijk is van het DTED detailniveau en van de breedtegraad (zie zones in DTED), zullen we het aantal rijen en kolommen in het DTEDtile object bijhouden. De data bestaat dan uit een pointer naar een geheugenruimte die dynamisch wordt gereserveerd, waarvan de grootte afhankelijk is van het aantal rijen en kolommen.

Philippe Vandewalle

pagina - 85 -


2006-2007

Een DTEDtile kan wordt bekomen door de “loadDTEDtile(DTEDreader, level, lat, lon)” methode van de DTEDreader aan te roepen. Hier kan het DTEDdetaillevel, de breedtegraad (=lat) en de lengtegraad (=lon) worden opgegeven waarvoor men een tile wenst te laden. De DTEDreader roept op zijn beurt de constuctor “newDTEDtile(dtedpath,dtedentry)” van het DTEDtile object aan. Het “dtedpath” bevat het absolute pad naar de DTED-data en “dtedentry” bevat een pointer naar de betreffende entry met informatie over het te laden bestand. De entry werd bekomen door de “getEntryFromDTEDList()” methode van het DTEDlist-object. We weten nu waar het bestand zich bevindt en het in één read instructie in het geheugen lezen. Dit om synchronisatietijd met het secundair geheugen te reduceren. Het DTED-bestand bevat een paar headers (ter controle) en ook de indicatie over het aantal rijen en kolommen van de elevatiematrix. Daarna kunnen we met een lopende pointer de elevatiedata in de matrix parsen. Hierbij moeten we er rekening mee houden dat de elevatiedata in big-endian werd bewaard. We moeten dus nog de notatie op de machine testen en eventueel swappen. Het UML schema van een DTEDtile object ziet er dan uit zoals op onderstaande figuur: DTEDtile + sw_lat; int + sw_lon; int + nrows; int + ncols; int + data; short* +newDTEDtile(char* dted_path, DTED_entry* entry); DTEDtile* +deleteDTEDtile(DTEDtile* tile); +printDTEDtile(DTEDtile* tile);

Voor testdoeleinden zal de elevatiematrix worden weggeschreven naar een bitmap bestand. Hierbij wordt elke hoogtewaarde geconverteerd naar een kleurwaarde.

7.2.4

HET BEËINDIGEN

Bij het beëindigen dient men enkel de destructor op de roepen van de geladen DTEDtiles en destructor van het DTEDreader object. De destructor van de DTEDreader zal ervoor zorgen de DTEDList wordt opgeruimd.

Philippe Vandewalle

pagina - 86 -


2006-2007

7.3 REALISATIE Bij de DtedReader proberen we terug de object georiënteerde manier te benaderen door voor ieder functioneel object een constructor en destructor te voorzien in een apart bestand.

7.3.1 DTEDREADER OBJECT

7.3.1.1 PROCEDURES VAN HET TOC OBJECT (TOC.C EN TOC.H). Public DTEDreader* newDTEDreader(char* dted_path); (dtedreader.h) Het dted_path bevat het absolute pad naar de DTED-data. De constructor zorgt ervoor dat een nieuwe DTED_list wordt aangemaakt (dit door ook de constructor “newDTED_list()” aan te roepen zie later ), en dat het dted_path wordt opgeslagen. Daarna wordt een pointer naar het DTEDreader object teruggegeven. Public void deleteDTEDreader(DTEDreader* reader); (dtedreader.h) De destructor zorgt ervoor dat de gebruikte gegevensstructuren worden opgeruimd, waarna het geheugen van de DTEDreader zelf wordt vrijgegeven. Public DTEDtile* loadDTEDtile(DTEDreader* reader, int level, (dtedreader.h) int lat, int lon); Probeert een tile te laden voor detailniveau level op locatie lat breedtegraad en lon lengtegraad. Indien dit niet lukt, wordt een lege pointer terug gegeven. Public void printDTED(DTEDreader* reader); (dtedreader.h) Schrijft informatie naar de console over de inhoud van de DTED_List.

7.3.2 DTED_LIST OBJECT Public DTED_list *newDTED_list (char* dted_path); (DTED_List.h) De constructor van de DTED_list doorzoekt het filesysteem recusief vanaf het dted_path naar bestanden van de vorm “*.dt?” en plaatst deze in een hulpstructuur. Daarna worden de DTEDTOC objecten aangemaakt door hun constructor op te roepen. Public void deleteDTED_list(DTED_list* dted_list); (DTED_List.h) geeft het geheugen vrij van de DTED_list en de onderliggende structuren.

Philippe Vandewalle

pagina - 87 -


2006-2007

Public DTED_entry* getEntryFromDTEDlist(DTED_list* (DTED_List.h) list,int level, int lat, int lon); Zoekt in de DTED_list naar bestanden met een bepaald detaillevel level, die de locatie lat, lon bevatten Public void printDTED_list(DTED_list* dted_list); (DTED_List.c) Schrijft informatie over het de DTED_list naar de console.

7.3.3

HET DTED_TOC OBJECT.

DTED_TOC *newDTED_TOC (DTED_world* dtedworld); Public (DTED_TOC.h) Maakt een nieuw DTED_TOC object aan op basis van de “dtedworld” hulpstructuur. void deleteDTED_TOC(DTED_TOC* toc); Public (DTED_TOC.h) Geeft het geheugen vrij van het DTED_TOC object en van onderliggende TOC_entries. DTED_entry* getEntryFromDTEDtoc(DTED_TOC* toc, int Public (DTED_TOC.h) lat, int lon); Zoekt de entry voor een bepaalde locatie. Indien ze niet kan worden gevonden wordt een lege pointer terug gegeven. void printDTED_TOC(DTED_TOC* toc); Public (DTED_TOC.h) Print informatie over DTED_TOC object naar console. void printDTED_entry(DTED_entry* entry); Public (DTED_TOC.h) Print informatie over DTED_entry object naar console.

7.3.4 HET DTEDTILE OBJECT. Public (DTEDtile.h)

DTEDtile* newDTEDtile(char* dted_path, DTED_entry* entry); Maakt een nieuw DTEDtile object aan door het bestand waarnaar de DTED_entry verwijst te laden en te parsen. Indien het bestand niet kan worden geladen, wordt een lege pointer terug gegeven.

Public (DTEDtile.h)

void

deleteDTEDtile(DTEDtile* tile);

Geeft het geheugen vrij van de DTEDtile

7.3.5 BMP.H Public (bmp.h)

saveDTEDtile_asBMP(unsigned short*d, heigth, char* filepath,char* filename); Slaat de elevatiedata testdoeleinden.

Philippe Vandewalle

op

in

een

int

bitmap

width,

bestand

int voor

pagina - 88 -


2006-2007

7.4 RESULTAAT De DTEDreader kunnen we dan testen in het main.c bestand zoals in onderstaande code: int main (int argc, char **argv){ DTEDreader* reader; DTEDtile* tile; reader = newDTEDreader("c:\\MAPS\\DTED"); printDTED(reader); //info over de bedekking van de dted-database getch(); // hier kan men meerder tiles proberen te laden tile = loadDTEDtile(reader,0, 51.0, 3.0); saveDTEDtile_asBMP(tile->data, tile->ncols , tile->nrows, "c:\\MAPS", “dtedtesttile.bmp”); deleteDTEDtile(tile); // na het laden van de nodige tiles, geven we de reader terug vrij deleteDTEDreader(reader); printf("\n\nhit key to terminate..."); getch(); return 0; } Voor de overige code verwijs ik naar de bijgeleverde CD in de directory DTEDREADER. Onderstaande afbeelding werd gemaakt met de DTEDreader. De afbeelding representeerd de DTED level0 elevaties voor 1 cell van 1 vierkante graad.

We kunnen mooi de rivierbeddingen zien die door de tijd heen zijn uitgesleten door erosie. Bovenaan links is tevens een stukje van de zee te zien.

Philippe Vandewalle

pagina - 89 -


Hoofdstuk 8:

2006-2007

DigiMap

8.1 DOELSTELLING 8.1.1 INLEIDING De DigiMap zal een synthetisch beeld op basis van CADRG-data én DTED-data tonen. Met de DTED-data wordt een terrein gemaakt waarbij gebergtes en valleien ontstaan door driehoeken te tekenen. Door het vlak van deze driehoeken te vullen met corresponderende CADRG-data bekomt men een realistisch beeld. De Digimap is gebaseerd op de CADRG-vieuwer als het gaat over het beheer van tiles en het samenstellen van een CadrgField. We zullen dit dan ook niet meer herhalen. Nieuwe aspecten van de Digimap zijn zaken zoals het “mappen” van de elevatie data op de CADRG-data. Dit zorgt voor problemen want de grenzen van de CadrgTiles komen immers niet overeen met deze van de DtedTiles. Ook zal de Digimap een meer algemenere methode voor het samenstellen van een synthetic ground map hanteren.

8.1.2

VEREISTEN

Het hoofddoel van de Digimap is om afhankelijk van: • de positie • direction • de range van de view • de gewenste Cadrg scale librairy • en het gewenste DTED detaillevel een corresponderend 3D-beeld te genereren. Daarbij wordt een beroep gedaan op de reeds ontwikkelde CadrgReader en de DtedReader om de corresponderende CadrgTiles en DtedTiles te laden. position, direction, range v/d view, scale lib, detaillevel

DIGIMAP CadrgViewer

CadrgReader

CADRG-data

DTED-data

Philippe Vandewalle

VIEW

pagina - 90 -


2006-2007

Omdat we nu een 3D beeld genereren, zijn er veel meer vlakken die moeten worden gerenderd. Hierdoor zal de belasting op het systeem toenemen. Het is dan ook van belang dat we het renderings werk zo snel mogelijk kunnen laten uitvoeren. Hiervoor zullen we er voor zorgen dat posities van elevaties en texture offsets van vlakken kunnen worden bewaard in een structuur. We moeten, bij het renderen, dan enkel deze data maar inlezen in plaats van iedere keer opnieuw te berekenen.

8.2 ANALYSE 8.2.1 GELAAGD ONTWERP. We hebben tot nu toe enkel gebruik gemaakt van 1 type dataset om een beeld te contstrueren. Bij de DigiMap zullen we nu 2 datasets aanspreken. Een synthetic groundmap kan uit verschillende layers bestaan: • De object-layer • De texture-layer • De heightfield-layer De object-layer is de laag waarbij er objecten op een oppervlak worden getekend. Wanneer we bij de texture-layer satelietfoto’s gebruiken en een groen vlak hebben, kunnen we in de object-layer bijvoorbeeld 3D-boom objecten tekenen. Of wanneer we een rood gebied hebben omdat er zich daar huizen bevinden, kunnen we kleine 3D-huisjes tekenen. Anders kunnen we de object layer ook bevolken door datasets die bijvoorbeeld informatie bevatten over waar er zich vliegtorens bevinden of luchthavens. Op deze plaatsen kunnen we dan werkelijke objecten tekenen. De texture layer is de laag die de rasterafbeeldingen levert voor de synthetic ground map. Deze kunnen afkomstig zijn van satellietfoto’s of van ingescande kaarten. Voorbeelden van datasets die als bron kunnen dienen hiervoor zijn CADRG en GeoTIFF. De heightfield-layer zorgt ervoor dat we een terrein kunnen maken die de hoogte weerspiegelt. Voorbeelden van datasets die hiervoor kunnen worden gebruikt zijn DTED en DEM. Object layer

Texture layer

Heightfield layer

Philippe Vandewalle

pagina - 91 -


2006-2007

De DigiMap in dit eindwerk zal enkel de onderste 2 layers implementeren. Maar door de algemene manier waarop we de DigiMap zullen implementeren, zou de object layer zonder al te veel aanpassingen kunnen worden er aan toegevoegd.

8.2.2 DIGIMAP ONAFHANKELIJK VAN GEBRUIKTE DATASET We zullen er ook voor zorgen dat de digimap in de toekomst ook gemakkelijk met andere datasets dan CADRG of DTED zal kunnen werken. Een vereiste hiervoor is dat er wel een reader wordt gemaakt voor deze dataset. Deze readers dienen dan enkele methodes te implementeren zodat de DigiMap tegen deze reader kan aanspreken. Een zogenaamde interface. CadrgReader DIGIMAP GeoTiffReader Texturefield

Textureinterface …

+ DtedReader Heightfield

Heightfieldinterface

DemReader

…

Op deze manier zou het mogelijk zijn dan de piloot realtime kan overschakelen van de ene dataset naar de andere. Men zou kunnen kiezen voor een CADRGtexturelayer en wanneer het zicht van de piloot slecht is door bijvoorbeeld slecht weer, zou men kunnen overschakelen naar een GeoTiff-texturelayer, die foto’s van de omgeving bevat.

8.2.3

EEN ALGEMEEN TILE-OBJECT

Om dit te implementeren zullen we gebruik maken van een algemeen Tileobject. Het is dit Tile-object die wordt gebruikt om een textureField op te stellen (zie CadrgField van de CadrgViewer). We zullen de “dist[4]” en “direction[4]” attributen dan ook in het Tile object bewaren. Verder bevat dit Tile object ook nog een link naar de corresponderende layertiles. De heightfield layer wordt geïmplementeerd door een Heightfield-object, en de texture layer wordt geïmplementeerd door een texturemap. Wanneer we dan een aanvraag doen aan een TextureReader(=CadrgReader of GeoTiffReader), dan dient deze het “texturemap” gedeelte van de Tile in te vullen. En wanneer we een aanvraag doen aan een HeightfieldReader(=DtedReader of DemReader), dan dient deze het “heightfield” gedeelte van de Tile in te vullen. Philippe Vandewalle

pagina - 92 -


2006-2007

Het UML schema van een algemene Tile: Tile +coverage; Coverage +textureid; unsigned int +direction[4]; struct Tile* +dist[4]; double +fieldmembervalue; int

TextureMap +width: int +height: int data: char* subtype: void*

Heightfield +coverage; Coverage +width; int +height; int +*data; short +*x_tex_co; float +*y_tex_co; float +*x_offset; float +*y_offset; float +*subtype; void

Een Tile • • • •

wordt volledig beheerd door de Digimap zelf: het aanmaken ervan het laden van de texture(=aanvraag aan de CadrgReader) het laden van de hoogteinformatie (= aanvraag aan DtedReader) het construeren van het texturefield ( = Tiles aan elkaar linken)

8.2.4

HET DIGIMAP OBJECT

Om vorige zaken te kunnen verwezenlijken zullen we een digimap object maken die een CadrgReader attribuut heeft. Om texture aanvragen naar te richten. Evenens ook een DtedReader attribuut om een heightfield te laden en een ImportControls attribuut die locatie van het vleigtuig bevat. Verder bevat de DigiMap nog enkele attributen die van belang zijn voor de administratie voor het opstellen van een textureField (cfr CadrgField bij de CadrgViewer). Voor het opstellen van het textureField bezit de DigiMap dezelfde functies (licht gewijzigt) als de CadrgViewer. 8.2.4.1 MAPPEN VAN DE HEIGHTFIELDDATA OP DE TEXTUREDATA Doordat de grenzen van de cadrgtiles niet gelijk lopen met de grenzen van de dtedtiles zullen we de ene tile op de andere moeten mappen. Omdat we voor de breedte van de View een range specificeren, moeten de tiles informatie bezitten over hun lengte en breedte op de grond in meters of nautical miles. Omdat enkel texturetiles deze informatie bezitten, zullen we dus de texturetiles als basis kiezen om de andere op te mappen. De digimap zal dus eventueel meerdere dtedtiles moeten mappen op 1 algemene tile met de texturetile als referentie. Zie onderstaande afbeelding.

Philippe Vandewalle

pagina - 93 -

Thesis: Advanced graphics for avionics displays DTEDtile

2006-2007

DTEDtile

Algemene Tile, met de Texture Tile als referentie. De Digimap zal elevatiedata uit 4 verschillende dtedtiles moeten assembleren in de Algemene tile. DTEDtile DTEDtile

8.3 REALISATIE De realisatie van de DigiMap zal erin bestaan door het veralgemenen van de CADRGViewer en het verfijnen van de viewer functies. De DigiMap zal zo ontworpen worden om met meerdere datasets te kunnen werken. Het moet nu ook moelijk zijn om 3D oppervlakken te renderen. De Digimap zal de CadrgReader en de DtedReader omvatten. Bij de aanmaak van het project in Visual Studio werden de 2 directories dan ook gekopieerd binnen de DigiMap folder, en de relevante bestanden werden in het project geïnclude. Het Algemeen Tile object wordt geimplementeerd in de bestanden Tile.h en Tile.c maar bevat verder geen functionaliteit De digimap zorgt ervoor dat de gepaste gegevens geladen worden (door oproepen aan de CadrgReader en DtedReader. Wanneer deze gegevens geladen zijn zorgt de Digimap ervoor dat ze op een gepaste manier worden getransformeerd om ze snel te kunnen renderen. Dit wordt gedaan door gebruik te maken van volgende functies, geimplementeerd in DigMap.h en Digimap.c Public (DigiMap.h)

Public (DigiMap.h)

DigiMap* DigiMap* newDigiMap(); Deze procedure is gelijkaardig aan de newCadrgField() procedure van de CadrgViewer. Hierbij wordt voor de gegeven locatie de gepaste cadrgtile geladen gecombineerd wanneer de texturedata is geladen, wordt de hoogte-informatie ingevuld door de Digimap. void

updateDigiMap(DigiMap* map);

deze procedure past de centertile van de digimap aan en bouwt het Texturefield opnieuw op.

Philippe Vandewalle

pagina - 94 -

Thesis: Advanced graphics for avionics displays Private (DigiMap.c)

2006-2007

void expandDigiMap(DigiMap* map,Tile *ptile, Direction dir); is gelijkaardig aan expandcadrgfield() in de CadrgViewer en werkt op een analoge manier.

Private (DigiMap.c)

Private (DigiMap.c)

Private (DigiMap.c)

Private (DigiMap.c)

void adjustDistances(Tile *ptile, Tile *tile, Direction dir); Om de tiles op de juiste plaats te kunnen tekenen bij het renderen, wordt de afstand (in meters) aangepast van de tiles tot het centerpunt. void upgradeTile(DigiMap* map, Tile* tile); na het laden van de texture voor een tile, wordt deze procedure aangeroepen om de tile in de grafische kaart te laden en om hoogte informatie voor de tile te laden en te berekenen. void interpolateBordersOfHeightmap(Tile* tile); Omdat de geografsiche posities het raster van de elevatiematrix niet overeenkomt met de grenzen van een texturetile, moeten we de randen van de heightfield interpoleren. Dit gebeurt in deze procedure. void setRenderInfo(Tile* tile); Om snel te kunnen renderen berekenen we één maal de textureoffsets van de verschillende diehoeken en slaan deze op in het x_tex_co en y_tex_co attribuut van de heightfield.

8.3.1 RENDEREN VAN HET TEXTUREFIELD. Bij het renderen van het TextureField, dienen we net zoals bij de CadrgViewer ook de boom te overlopen, maar in plaats van per tile 4 vertexes te tekenen met daarin “net” passende texturecoordinaten, zullen we de elevatiematrix overlopen en per 4 elevatiewaarden zullen we 2 driehoeken tekenen. Onderstaande figuur toont 8 elevatiewaarden, waarmee we 4 groepen van 4 kunnen vormen en dus 8 driehoeken tekenen.

Het tekenen van het oppervlak gebeurt dan door, met de z-component van de vertex, de hoogtewaarde mee te geven. Code-extract: void drawMapWithHeightField(Tile* tile){ Coverage *tilecov; Heightfield *hmap; int i,x,y; double double int Philippe Vandewalle

tilewidth; tileheight; vp; pagina - 95 -

Thesis: Advanced graphics for avionics displays double

2006-2007

nd, wd;

tilecov=&(tile->coverage); hmap=&(tile->heightfield); glBindTexture(GL_TEXTURE_2D, tilewidth = tile->dist[1] - tile->dist[3]; tileheight = tile->dist[0] - tile->dist[2]; tilewidth=tilewidth/254*256; tileheight=tileheight/254*256; nd=tile->dist[0]; wd=tile->dist[3]; //testprintmap(hmap); for(y=1;yheight;y++){ glBegin(GL_TRIANGLE_STRIP); for(x=1;xwidth;x++){ //vertex0 vp=y*hmap->width +(x-1); glTexCoord2f(hmap->x_offset[vp]/tilewidth,hmap-> y_offset[vp]/tileheight ); glVertex3f(wd+hmap->x_offset[vp],nd-hmap-> y_offset[vp], hmap->data[vp]*elev_multi); //vertex1 vp=y*hmap->width+x; glTexCoord2f(hmap->x_offset[vp]/tilewidth,hmap-> y_offset[vp]/tileheight ); glVertex3f(wd+hmap->x_offset[vp],nd-hmap-> y_offset[vp], hmap->data[vp]*elev_multi); //vertex2 vp=(y-1)*hmap->width+(x-1); glTexCoord2f(hmap->x_offset[vp]/tilewidth,hmap-> y_offset[vp]/tileheight ); glVertex3f(wd+hmap->x_offset[vp],nd-hmap-> y_offset[vp], hmap->data[vp]*elev_multi); //vertex3 vp=(y-1)*hmap->width+x; glTexCoord2f(hmap->x_offset[vp]/tilewidth,hmap-> y_offset[vp]/tileheight ); glVertex3f(wd+hmap->x_offset[vp],nd-hmap-> y_offset[vp], hmap->data[vp]*elev_multi); } glEnd(); }

for(i=0;i<4;i++){ if (tile->direction[i]!=(Tile*)NULL) drawMap(tile->direction[i]); } return;

//rec-call

}

Philippe Vandewalle

pagina - 96 -


2006-2007

8.4 RESULTAAT De implementatie van de DigiMap is terug te vinden op de bijgeleverde cd in de directorie DIGIMAP. Wanneer we de Digimap dan starten, dan lijkt er bij het opstarten niets veranderd. Maar wanneer we de “angle” van de view veranderen, door een hoek te maken met de camera (numpad 2 of numpad 8), dan zien we het relief van het oppervlak. Onderstaande afbeelding toont een momentopname van de DigiMap in werking. We kunnen mooi de vallei van de rivier waarnemen.

Philippe Vandewalle

pagina - 97 -


2006-2007

Hieronder zien we een schermafdruk van een kustlijn. We moeten opmerken dat de zee ook elevatiedata bevat, maar dat deze = 0.

Onderstaande afbeelding is een schermafdruk van de Digimap in ruiger gebergte.

Philippe Vandewalle

pagina - 98 -


2006-2007

Eigen beoordeling Bij de aanvang van dit eindwerk moest ik eerst een hele boterham specificaties en standaarden bestuderen om te begrijpen hoe de inputdata geordend was. Vooral bij het ontwerpen van de CadrgReader ging heel wat bestudeerwerk van de Cadrg standaard aan vooraf. Wanneer de CadrgReader klaar was, kon ik mij ten volle geven om een vernieuwend algoritme te ontwerpen voor het laden van tiles voor de Viewer. Hierbij heb ik verschillende modellen afgewogen en zitten sleutelen aan een algoritme die niet voor de hand ligt, maar toch vrij efficient blijkt te zijn. Bij het op zoek gaan naar efficiente datastructuren heb ik me soms met gewaagde implementaties bezig gehouden, zonder efficiente uit het oog te verliezen. Na vele forums en enkele tutorials te doorlopen over OpenGL was de vreugde dan ook groot wanneer ik zonder haperingen aan een hoog tempo door de CadrgData kon scrollen met de CadrgViewer. Bij de demonstratie van de CadrgViewer bij Barco had men dan ook oog naar de alternatieve manier waarop de view werd geconstrueerd. Om het geheel realistischer te maken heb ik dan nog een DTED reader gemaakt om deze te implementeren in de Viewer. Het reliëf en de mooie resultaten die hiermee kunnen gecreëerd worden, zorgen ervoor dat ik zo stilletjes aan verslaafd geraakt ben aan de mogelijkheden van OpenGL. Wat het resultaat betreft ben ik fier op de DIGIMAP en ken met een gerust hart zeggen dat het doel bereikt is. Het implementeren van de DIGIMAP op een manier waarbij men onafhankelijk is van de gebruikte dataset, nodigt dan ook uit om de DIGIMAP verder uit te bouwen met een waaier van andere datasets.

Philippe Vandewalle

pagina - 99 -

Advanced graphics for avionics displays

Recommend Documents