INTRODUCTION

I've written this QBasic "hack" to convert Digital Elevation
Model (DEM) files to Flight Sim Toolkit FTD files.  I was
inspired by the information I found on the web by both Forest
Pearson and Daniel Berlin metioning that it could be done (but
with the use of some very expensive software).

The program I created is rather "vertical" in that it was created
to meet a specific need.  I want to build in FST, not spend lots
of time dressing up a program.  However, I have written a rather
detailed description of the code, and anyone with a grasp of
fundamental programming should be able to make modifications if
necessary.  I suppose if I were motivated, I could make this
program into something really cool.  The longer I worked on it,
the greater the potential I could see for creating modeling
software for this kind of thing.  A nice GUI with a command line
interface would be great (also, using something like Borland
Turbo Pascal or C++ would be better).

Anyway, this written explanation should help anyone who's
interested in creating terrain data files for FST.  This write-up
fully explains the problem I wanted to solve, the approach I took
to the problem, assumptions, trade-offs, and the solution.

BACKGROUND: What's a DEM file?

A DEM file (in particular, a 1 degree DEM) is a file that
represents a one degree square area of the earth.  The DEMs I
used sample the area with 1200 south to north profiles, each
marking the elevation at 1200 points.  For more information on
DEM files, visit the USGS web site and then download their DEM
Data Users Guide.

	http://edcwww.cr.usgs.gov/doc/edchome/ndcdb/ndcdb.html

If you just want to salivate at the possibilties for creating
terrain for the contiguous 48 states of the USA, just go to this
site:

      http://edcwww.cr.usgs.gov/glis/hyper/guide/1_dgr_demfig/index1m.html

I recommend you spend some time learning about DEMs before you do
any conversion.  They are simple, but you should be able to
graphically model them in your mind so you can develop some
verification strategies along the way.  (Verification strategies
would be built into a sophisticated program.)

BACKGROUND: The Problem

For my simulation, I wanted to create FTD files for a portion of
the state of Colorado.  I wanted to include the Eastern plains
and some of the Rocky Mountains around the city of Colorado
Springs.  I selected the area between these four points on the
map.

Northeast corner	40N/104W
Southeast corner	38N/104W
Southwest corner	38N/106W
Northwest corner	40N/106W

This area encompasses slightly more than 12 FTD squares of 250
kilometers.

BACKGROUND: The Approach

Looking at the area I chose, I marked off the 12 FTD squares I
would create. The area is represented by 4 DEM files from the
USGS repository:  The southwest portion by Pueblo West, southeast
by Pueblo East, northwest by Denver West, northeast by Denver
East.  I also marked off the areas covered by each of the DEMs.  

        NOTE:  I suggest to anyone doing this, that you mark off
        both your areas of DEM coverage and your FTD squares. 
        You will need to know this to set the program indices in
        a couple of places.

The program, then runs from the southwest, up to the north for
each profile of both the lower (Pueblo) and upper (Denver) DEMs,
processing profiles from west to east.  This is, of course,
taking into account that the FTD file formats are 90 degrees
orthogonal to DEMs.  FTDs run from left to right, from the bottom
to the top.


IMPLEMENTATION: The Assumptions

I selected 1 degree DEMS over the other DEM formats.  The spacing
was small enough to allow me to select elevations that were no
more than about 10% of the distance between FTD points of 500
meters.  I also assumed that the linear (not angular) quality of
the sampling would be easier to work with than the 7.5 minute
DEMs even though the separation between points is closer in the
7.5 minute DEMs.

The DEM files I downloaded were taken as exact.  The first data
record of the DEM contains information describing the accuracy of
the elevation information (horizontal and vertical).  For my
needs, I was not about to quibble over a couple of 10 meters or
so.  I assumed the elevation information was good enough. 
Because of that, I do no filtering for an occasional "bad"
elevation value.  But, I've not found any in the terrain I've
created for Colorado.

IMPLEMENTATION: The Trade-offs

I own a somewhat small (by today's standards) PC.  It's got 4MB
RAM, but usually over 100MB free on the drive.  I wrote a special
set of boot files so I could run a RAM drive to keep I/O to a
minimum.  I just didn't want to beat up on my drive after the
first successful runs to the lower left FTDs. This is due to the
orthogonal perspective between DEMs and FTDs.

Why Qbasic?  Why not?  It's already on my machine.  At work, I've
got access to just about anything imaginable, but I opted for
something I thought I could more readily share.  Qbasic isn't
fast (I could really tell what a dog it is when I direct I/O to
RAM instead of spinning media), but it's EVERYWHERE.  Another
language would have better facilities for creating internal data
structures for optimal processing.  Writing in Qbasic was fun, if
sometimes frustrating.

THE SOLUTION: Code Explanation  

Read the following sections while looking at a print out of the
Qbasic code.  You will see where you might want to make changes
to process your own DEMs.

SUBROUTINE DECLARATIONS:

The top of the program code contains two subroutine declarations. 
One for outputting to the FTD files.  The other building the
variable bigstring$.  Each of these subroutines is described in
more detail later.

SEPARATION CONSTANTS:

These constants are used to calculate the closest profile to a
vertical row of FTD points and for each profile, the closest
points to the horizontal rows of FTD points.

Horizontal Point Separation:  Horizontal separation at the
northernmost edge of the area is not as great as it is at the
southernmost edge.  That's because the separation of meridians
(lines of longitude) grow as you approach the equator from the
North Pole.  I acknowledged this, but didn't program for it.  The
error isn't that great for my purposes.

I found the distance between the lines of longitude in the middle
latitude of my area.  For this, I used the distance calculator
at:

	http://www.indo.com/distance/

The distance is 87 kilometers.

That means the distance between profiles in the DEMS (on average
between the two) is found by dividing 87,000 meters by 1200
samples.  Then, to account for how many samples would have to
passed to meet the 500 meter distance of the FTD, divide 500 by
the distance between samples.  This value is used to tell us
which profile to process.

Vertical Point Separation:  Lines of latitude are separated by
equal distances for our purposes.  Again, I got the distance from
the indo.com web site and it came out to 111,000 kilometers.  The
same calculation applies to vertical point separation, and it is
used to tell us which points along the profile to process.

HARDCODE THE FTD FILES

Daniel Berlin's explanation of FTD files came in handy here, but
I didn't trust myself to do this alone.  I created a 3x4 world
and looked at the file naming FST used.  I didn't feel like
writing an algorithm to convert the x,y coordinates of FTDs to
the 0 and _ encoding of the FTDs.  That is left to you, dear
reader, as an experiment for yourself.  I used good old brute
force to do this.  I did use the array, however, because of its
ease of use when it comes to indexing and calling the proper
places for output.

BUILD THE FTD HEADER

Taken out of Daniel Berlin's explanation.  The FTD file header
contains some ASCII characters describing some FTD file
attributes and 90 null characters (probably for some future use). 
I built strings, assigned them to string variables, then PUT them
into the files.  Because the FTD file points are written at 200
byte offsets for the terrain data, I opted to open the files for
BINARY operation and work to specific byte locations.  This is
what makes this program so I/O bound.

I also opened the first four FTD files along the left side of the
area and initialized two FTD file set tracking variables to "F"
(for false).  The tracking variables are used to open and close
the other two sets of FTD files later in the program execution.

PREPARE TO READ THE DEMs

The profilesample variable is dimensioned as shared because it is
used by the buildbig procedure, and all DEM files are opened.  I
read the first record and do nothing with it.  The DEM Data Users
Guide explains the contents of the Type-A record, but this being
a simple program, I'm not too concerned about its contents.  The
real purpose for reading the Type-A record is to set the file
pointers to the first profile record.  The DEM files are read
sequentially, so keeping track of the file pointers is important.

I initialize the demfileset variable to 1.  This variable is used
later in reading the files.

I dimension the variable bigstring$ as shared, because it, too is
shared with the buildbig subroutine.

GETTING READY TO RUN THE MAIN PROCESS LOOP

There are three variables to initialize:  The profilebase
variable which is used to calculate the profile to process.  The
profiletoprocess variable which tells us which profile to process
next. The number of profiles processed which controls the main
loop.  Because my area is 3 FTD squares wide, each FTD square
containing 100 points, My loop runs out at 300. 

If you wanted to process all the data, index the loop on the end
of file condition for the last file to read.  You might end up
with some portion of an FTD containing real world data, and the
rest ocean.  But, hey! You've gotten this far, and maybe one day
you would like to do the next adjacent DEM.

RUNNING THE MAIN PROCESS LOOP

The main process loop runs for 300 iterations.  That's because
300 vertical profiles are needed to produced the 3 columns of
FTDs.

INSIDE THE MAIN PROCESS LOOP, AT THE TOP
   
The first line inputs a profile sample.  This sample is tested in
the first condition block.  It checks to see the number of the
profile read.  If it's greater than the 1200, we need to shift
the DEM file sets to the eastern sets.  The variable demfileset
is incremented by by 2, and if you look at how they are numbered
to begin with, you'll see that now we're going to process DEM
files 3 and 4.  Also, why do we read from the new DEM file when
we read just before this code block? That's because there are
1201 samples in a DEM.  The 1201st profile on the easternmost
side of a DEM is identical to the westernmost profile. You'll
have to read the DEM Data Users Guide if you really want to
understand this...

TESTING FOR THE PROFILE TO PROCESS

If the Profile to Process Number is Not Equal to the Profile
Number

This condition is inverse logic.  If a profile we just read is
not equal to the profile to process, then we just read through
the logical records of the files to move the file pointers along
to the next profile.  The variable lridx is short hand for
Logical Record InDeX.  This is a result of the record blocking
process done on the UNIX system.

ELSE..

The Profile to Process Number is EQUAL to the Profile Number

Increment the profilesprocessed variable and print out a message.
We make a call to the subroutine that builds the bigstring$. 
This is a string that is 7206 characters long--1201 elvations
samples at 4 characters each, separated by two spaces.  We have
to count each sample as six characters in length.

The set of point variables are reset, ready to climb the profile,
picking off only those that we need to select for the FTD. 
Pointsprocessed reset to 0 (ready to go), pointctr and pointbase
set to 1, because we want to use the first point,  pointtoprocess
is set equal to pointbase, and the pointvalue is the leftmost set
of six characters (remember? 2 spaces and 4 characters).

THE PROCESSING LOOP FOR DEM FILESET

The condition for processing the loop is the set on length of the
string that remains to be processed.  We don't process the last
sample at the end of the profile, because the last sample on the
end of a profile on a DEM is identical to the first profile on
the corresponding DEM to the north.

WHEN THE POINT COUNTER IS EQUAL TO THE POINT TO PROCESS (WE GOT ONE!)

The pointsprocessed variable is incremented by 1 and we call the
output subroutine, passing to it the number of profiles
processed, points processed, and the value of the sample to be
output.  The profiles processed and the points processed are used
to determine the horizontal and vertical locations of the value
in the FTD.


COMING BACK FROM THE OUTPUT SUBROUTINE

When we come back from the output subroutine, we calculate the
next point to process.  This is done by adding the vertical point
separation constant to the point base value.  The vertical point
separation and point base values must be maintained as real
numbers.  The next point to process is then calculated as the
integer value of the sum of the base and separation.

Then we increment the point counter, and pick out the next sample
(6 characters).  This ends the loop for processing the southern
most DEMs.
        
PROCESSING DEM FILESET + 1

The demfileset + 1 DEMs are the northernmost.  I didn't want to
process the entire lenght of the profiles, only just what was
needed to complete the 3rd and build the 4th FTDs in the column. 

Read from demfileset + 1 (that's DEM file 2 or 4), and call
buildbig, the subroutine for building the variable bigstring$.

POINT VARIABLE INITIALIZATION

The pointctr is set to 0 because we are starting a new DEM
profile.  The pointbase and pointtoprocess variables are set back
1200 because we just counted off 1200 points from the southern
DEM and we are starting a new DEM profile.  We DID NOT reset
points processed, because we need that value to locate the proper
points in the FTD and limit the loop for reading northern DEM
profiles.

FORCING THE END OF THE LOOP TO OUR FTD LIMIT

The loop reading the second DEM (northern DEM) is set to end
after we've processed 400 points.  There are 4 FTDs in a column,
each represented by a 100 x 100 point matrix.

The pointctr is incremented, and the next point is picked out of
the variable bigstring$.  

If the point counter is equal to the point to process, then the
program continues as explained before.  Call to the output
subroutine, calculate the next point to process from the base and
separation values.

DONE WITH THE LOOPS THAT PROCESS CONTIGUOUS PROFILES FROM THE DEMS

Now that we've processed a set of profiles from the southermost
edge of the area to the northernmost edge, we have to calculate
our next profile to process.  Calculating the next profile to
process is the same as calculating the next point to process. 
Add the horizontal point separation value to the profile base
value, then find the integer of that.  Next, assign that to the
variable indicating the next profile to process.

SWITCHING FROM WESTERN FTDs TO CENTRAL FTDs

After calculating 100 profiles, it's time to switch FTDs.  The
variable middleftd$ is set to F as an added "switch.  We can come
through here after 100, but not before it's time to switch and
goof up.  The middleftd$ variable keeps us from doing that.  A
simple loop closes the currently opened FTD files (which, by the
way are opened with numbers in the 50s just for clarification). 
Another loop opens the next FTDs.  The FTDs are opened in the
binary mode because we write to specific byte locations as you'll
see later.
  
SWITCHING FROM CENTRAL FTDs to EASTERN FTDs

Same as above.

ENDING THE LOOP AND BYE-BYE

All the above is a description of the "engine" for performing the
conversion.  Careful study of the code, DEM data format, and FTD
format should allow you to use this as it is, or make minor
modifications to process areas of different dimensions.  The
CLOSE statement closes all files.

BUILDING THE BIG STRING

The subroutine buildbig takes a file number as its only
parameter.  The program, having first read a logical record into
the variable profile sample, calls buildbig to first throw away
the first 142 characters.  Then, with a simple loop, reads the
remaining 7 logical records, appending them to the bigstring$
variable and concatenating them with a double space string, the
" " you see.

The variable s bigstring$ and profilesample are both SHARED to
enable this to happen.

THE OUTPUT SUBROUTINE

The program calls this subroutine and passes three values: the
profile number, the point number, and the value of the sample to
be output.

The purpose of this subroutine is to take the three values and
calculate the position in the FTD for the elevation and output
the elevation to the corresponding byte location.  Actually, the
output elevation is two bytes, but you'll see how that's handled.

The first IF loop is prevent the program from "running away". 
When I was testing the program at the beginning, I had to put
these "brakes" on.  I ran several endless loops, requring me to
halt my Qbasic application.

SELECTING ONE FTD OF 4

The filenum variable is set to 51.  The base file number for the
FTD files is 50 plus 1 through 50 plus 12.

We use the profile number to calculate the FTD filenum variable. 
Remember, the FTD file number offset from one column to the next
is 4, and we change FTD columns every 100 profiles.

After figuring out which column of FTD files we're working with,
we use the pointnum to determine which of the 4 FTD files we need
to open.  

CALCULATING THE BYTE LOCATION

At this point, we've used the profile number and point number to
identify the file to which we are writing.  Now, we have to
translate the profile number and point number into FTD
coordinates. 

The location base value starts out equal to the point number
value and is adjusted downward, based on its number relative to a
factor of 100.  (Again, an FTD square is 100 by 100 points).

The location offset value starts out equal to the profile number
value and is adjusted downward, based on its number relative to a
factor of 100.

The location in the FTD file is found by this calculation,
derived from the description of the FTD file format written by
Daniel Berlin.

LET location = 128 + (((locbase - 1) * 200) + (locoffset * 2)) - 1

CALCULATING THE POINT VALUE

Simple, first convert the string to a real number.  Then define
byte one as by using a modulo function on the value.  Define byte
two as the integer of the value divided by 256.

SENDING THE VALUES TO THE FILE

Define a string for output, because the PUT to byte location
wants a string value.  Then put to the FTD file calculated to be
filenum, at the location calculated with the profile number and
point number, the two bytes you concatenated in the previous
step.

End of the subroutine.

HOW IT'S DONE:

Identify the DEM files you need from the USGS, and download them
onto a UNIX machine.  Use the dd command in the UNIX environment
to block the file.  The results of this is that each of the DEM
record types has been blocked, with all type B DEM records in 7
logical records.  

The DEM files will be a bit larger than 8 megabytes apiece when
read to use. Look at the SAMPLE.DEM file in the archive.  It's
the first few records of one of the Pueblo DEMs

Copy the DEM files into a directory on your PC.

Boot your PC with the CONFIG.SYS and AUTOEXEC.BAT files in the
archive.  If you need something special, create your own boot
files, but be sure to boot up with a RAM drive for output.

Open the QBASIC environment and edit the file names for the input
files to match your needs.  Edit the output file directories if
you need to, too.

Run the QBASIC program (debug if necessary--especially if you
change the dimensions and/or the number of DEMs or FTDs you want
to process).

When the program has completed, use DOS to copy the copy the FTDs
from the RAM drive to the hard drive.  Copy them into the FST
project directory.

QUESTIONS....

If this overwhelms you, don't sell yourself short.  Spend some
time learning the DEM file format, it's interesting stuff.  You
should know the FTD file format, too.  By understanding these
you'll be able to make simple modifications to the work I've done
to create this Qbasic code.  Of course, you should have some
understanding of Qbasic.  I learned it on this project. If you
really get stuck, try to understand your dilemma and send me mail
at

		stevemiller@kktv.com

Have fun.

Steve Miller


