Please help - Cracking elevation data format in data file

I am desperate and need help. Whoever can solve this will be rewarded.
I've been working on this in one way or another for about 6 months.

I'm working on a program to assist me in figuring out the way
elevation data is stored in a small section of a data file for the
game Morrowind. I'm going to be creating a mod for it and need to
create a landscape generation program first. This IS a legal endeavor,
just a difficult one.

The game map is broken down into 1024 64x64 vertex sections, called
cells, and stored sequentially in a data file (*.ESM). Although the
cells' order in the ESM go from left to right, top to bottom, the
elevation/vertex data is stored in each cell left to right, bottom to
top due to the game's coordinate system.

Each vertex height is represented by a 1 byte signed integer. This
value is relative to the height of the vertex before it (-1 means the
vertex is 1 unit lower than the previous vertex, etc.). However, at
the end of each row of vertices this value is not carried over to the
vertex at the beginning of the next row. It resets to something,
presumably 0. Disturbingly, the string of bytes describing a cell's
elevation is 4225 bytes long (65x65 bytes), in contrast to the game's
64x64 vertex cells. There is an extra row and column for an unknown
reason. Each cell has it's own global elevation offset as well, which
is added to each vertex.

I've created several test ESM's using another landscape generation
program. One has a horizontal gradient of elevation, the other a
vertical, and another is simply a circular "hill" that overlaps a 3x3
grid of cells. I included a JPEG for each so you can see what the
results should look like. Each has mixed results in the program.

My program displays the results of my "formula" for interpreting the
data graphically and numerically to assist in cracking the format.
Graphically the elevation is shown as a grayscale. Numerically each
vertex is shown as either its raw ASCII value (from the ESM, 0-254),
its relative elevation, or its absolute (final) elevation.

Please contact me in this newsgroup or via email if you are interested
and I will send you the project and data files (about 1.7 MB). It is
written in VB6 and contains no additional references or API calls.

Thanks.

Kevin Fishburne
kfishburne@_NOSPAM_pinestate.com

"Kevin Fishburne" <Kevin_Edward_Fishburne@hotmail.com> wrote in message
news:3de59d6f.0401160951.7dc7061a@posting.google.c om...
> I'm working on a program to assist me in figuring out the way
> elevation data is stored in a small section of a data file for the
> game Morrowind. I'm going to be creating a mod for it and need to
> create a landscape generation program first. This IS a legal endeavor,
> just a difficult one.

The Morrowind web site mentions editors you can get. Have
you not tried this approach?

> Disturbingly, the string of bytes describing a cell's
> elevation is 4225 bytes long (65x65 bytes), in contrast to the game's
> 64x64 vertex cells. There is an extra row and column for an unknown
> reason. Each cell has it's own global elevation offset as well, which
> is added to each vertex.

The initial development of the game used NetImmerse, although
what you describes indicates the final version of the game uses a
modified terrain system different than what I had originally
implemented. The original version used the algorithm in
Real-time, continuous level of detail rendering of height fields,
P. Lindstrom, D. Koller, W. Ribarsky, L.F. Hodges, N. Faust, G.A. Turner
Proceedings of SIGGRAPH 1996, pp. 109-118
The requirement for tiling the terrain without the CLOD causing
cracking at the tile boundaries is that each tile be of the size
(2^n+1)-by-(2^n+1). In your case, n = 6.

> My program displays the results of my "formula" for interpreting the
> data graphically and numerically to assist in cracking the format.

Has Bethesda Softworks not provided the format at its website?
If legal, why would you need to "crack" the format?

--
Dave Eberly
eberly@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com

Fractal or other height-field data is usually a power-of-two +1 in size. To
make a 64x64 grid out of triangles would need 64*64*2 tris obviously, but
it'd need 65*65 vertices. Just draw a 4x4 grid of dots on paper and see that
it encapsulates 3x3 squares, not the 4x4 you might expect.

Sorry if this is dumb-**** answer, I'm real tired and need to go to bed

--

Regards,
Paul Johnson
www.applewoodhouse.com


"Dave Eberly" <eberly@magic-software.com> wrote in message
news:YeWNb.10008$q4.5904@newsread3.news.atl.earthl ink.net...
> "Kevin Fishburne" <Kevin_Edward_Fishburne@hotmail.com> wrote in message
> news:3de59d6f.0401160951.7dc7061a@posting.google.c om...
> > I'm working on a program to assist me in figuring out the way
> > elevation data is stored in a small section of a data file for the
> > game Morrowind. I'm going to be creating a mod for it and need to
> > create a landscape generation program first. This IS a legal endeavor,
> > just a difficult one.
>
> The Morrowind web site mentions editors you can get. Have
> you not tried this approach?
>
> > Disturbingly, the string of bytes describing a cell's
> > elevation is 4225 bytes long (65x65 bytes), in contrast to the game's
> > 64x64 vertex cells. There is an extra row and column for an unknown
> > reason. Each cell has it's own global elevation offset as well, which
> > is added to each vertex.
>
> The initial development of the game used NetImmerse, although
> what you describes indicates the final version of the game uses a
> modified terrain system different than what I had originally
> implemented. The original version used the algorithm in
> Real-time, continuous level of detail rendering of height fields,
> P. Lindstrom, D. Koller, W. Ribarsky, L.F. Hodges, N. Faust, G.A. Turner
> Proceedings of SIGGRAPH 1996, pp. 109-118
> The requirement for tiling the terrain without the CLOD causing
> cracking at the tile boundaries is that each tile be of the size
> (2^n+1)-by-(2^n+1). In your case, n = 6.
>
> > My program displays the results of my "formula" for interpreting the
> > data graphically and numerically to assist in cracking the format.
>
> Has Bethesda Softworks not provided the format at its website?
> If legal, why would you need to "crack" the format?
>
> --
> Dave Eberly
> eberly@magic-software.com
> http://www.magic-software.com
> http://www.wild-magic.com
>
>

"Paul Johnson" <paul@applewoodhouse.com> wrote in message
news:bua4g1$qhg$1@titan.btinternet.com...
> Fractal or other height-field data is usually a power-of-two +1 in size.
To
> make a 64x64 grid out of triangles would need 64*64*2 tris obviously, but
> it'd need 65*65 vertices. Just draw a 4x4 grid of dots on paper and see
that
> it encapsulates 3x3 squares, not the 4x4 you might expect.
>
> Sorry if this is dumb-**** answer, I'm real tired and need to go to bed

Yes it is, and yes you do. Draw an NxM grid of dots on paper and
see that it encapsulates (N-1)x(M-1) squares. This is true regardless
of N and M. This is not the issue. The continuous level of detail
algorithm I mentioned requires N and M to be powers of two plus one.
The requirement has to do with edge collapses in a quad-tree-like
data structure. I implemented the terrain algorithm in NetImmerse,
which is what Morrowind used as its graphics engine, so I think I am
qualified to post the response I did

--
Dave Eberly
eberly@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com

I'm not getting into willy waving with you. I've been doing commercial
graphics programming for 15 years meself. One thing you never know on here
is how much knowledge the poster has and sometimes he's looking for the easy
answer... He wondered about the +1 and I explained is all - "There is an
extra row and column for an unknown reason."

--

Regards,
Paul Johnson
www.applewoodhouse.com


"Dave Eberly" <eberly@magic-software.com> wrote in message
news:jX0Ob.11412$i4.498@newsread1.news.atl.earthli nk.net...
> "Paul Johnson" <paul@applewoodhouse.com> wrote in message
> news:bua4g1$qhg$1@titan.btinternet.com...
> > Fractal or other height-field data is usually a power-of-two +1 in size.
> To
> > make a 64x64 grid out of triangles would need 64*64*2 tris obviously,
but
> > it'd need 65*65 vertices. Just draw a 4x4 grid of dots on paper and see
> that
> > it encapsulates 3x3 squares, not the 4x4 you might expect.
> >
> > Sorry if this is dumb-**** answer, I'm real tired and need to go to bed

>
> Yes it is, and yes you do. Draw an NxM grid of dots on paper and
> see that it encapsulates (N-1)x(M-1) squares. This is true regardless
> of N and M. This is not the issue. The continuous level of detail
> algorithm I mentioned requires N and M to be powers of two plus one.
> The requirement has to do with edge collapses in a quad-tree-like
> data structure. I implemented the terrain algorithm in NetImmerse,
> which is what Morrowind used as its graphics engine, so I think I am
> qualified to post the response I did
>
> --
> Dave Eberly
> eberly@magic-software.com
> http://www.magic-software.com
> http://www.wild-magic.com
>
>

From real experience 8 bits isnt enough range for whole map, so I would
guess
that the extra byte 64+1 is a magnitude ( 0..255) multipleied by 256
and all
the next 64 numbers are added (offset) foo that value.

why the extra row??? 65x65 64+1 64+1 ????

It might be 2 bytes (0..64k-1) for the starting offset 64*2 + 1 (the 1
being
something else.

or there might be other data in a 'struct' (besides the possible offset
values 64*1)
maybe multipliers for the point offsets (so that terrain withing the cell
can shift by more than
1 step for each value in the byte.

Its possible that the extra values might be a lower Level of Detail (LOD)
mapping to use for
a smaller simpler mesh at long distance (like a 8x8 mesh = 64 values
(maybe 2 bytes each)
that are averages (cant rely on just picking every 8th point to use for
this as you might randomly
get a peak or a dip that will distort it too much...)



Or something Ive done for that extra row+column is to have 64x64 tiles
but include
the points to finish the 64th row/ collumn of tiles (requiring 64+1
points each direction = 65x65)
These point values overlap the next cells on 2 side (like right and
bottom if its a 4th quadrant
coord system) so that all the tiles triangles can be drawn without having
to pull other cell's data
into mem (or just complicate the access code -- a client that get sent
cells would have to be sent the
extra cells to do all the tiles properly...)







Kevin Fishburne wrote:

> I am desperate and need help. Whoever can solve this will be rewarded.
> I've been working on this in one way or another for about 6 months.
>
> I'm working on a program to assist me in figuring out the way
> elevation data is stored in a small section of a data file for the
> game Morrowind. I'm going to be creating a mod for it and need to
> create a landscape generation program first. This IS a legal endeavor,
> just a difficult one.
>
> The game map is broken down into 1024 64x64 vertex sections, called
> cells, and stored sequentially in a data file (*.ESM). Although the
> cells' order in the ESM go from left to right, top to bottom, the
> elevation/vertex data is stored in each cell left to right, bottom to
> top due to the game's coordinate system.
>
> Each vertex height is represented by a 1 byte signed integer. This
> value is relative to the height of the vertex before it (-1 means the
> vertex is 1 unit lower than the previous vertex, etc.). However, at
> the end of each row of vertices this value is not carried over to the
> vertex at the beginning of the next row. It resets to something,
> presumably 0. Disturbingly, the string of bytes describing a cell's
> elevation is 4225 bytes long (65x65 bytes), in contrast to the game's
> 64x64 vertex cells. There is an extra row and column for an unknown
> reason. Each cell has it's own global elevation offset as well, which
> is added to each vertex.
>
> I've created several test ESM's using another landscape generation
> program. One has a horizontal gradient of elevation, the other a
> vertical, and another is simply a circular "hill" that overlaps a 3x3
> grid of cells. I included a JPEG for each so you can see what the
> results should look like. Each has mixed results in the program.
>
> My program displays the results of my "formula" for interpreting the
> data graphically and numerically to assist in cracking the format.
> Graphically the elevation is shown as a grayscale. Numerically each
> vertex is shown as either its raw ASCII value (from the ESM, 0-254),
> its relative elevation, or its absolute (final) elevation.
>
> Please contact me in this newsgroup or via email if you are interested
> and I will send you the project and data files (about 1.7 MB). It is
> written in VB6 and contains no additional references or API calls.
>
> Thanks.
>
> Kevin Fishburne
> kfishburne@_NOSPAM_pinestate.com

"Paul Johnson" <paul@applewoodhouse.com> wrote in message
news:bubd05$o7$1@sparta.btinternet.com...
> I'm not getting into willy waving with you. I've been doing commercial
> graphics programming for 15 years meself.

Your second sentence contradicts the first.

> One thing you never know on here is how much knowledge
> the poster has and sometimes he's looking for the easy
> answer...

There is no "easy" answer, only the correct one, which
I explained.

> He wondered about the +1 and I explained is all

And I pointed out your explanation is not the correct one.

--
Dave Eberly
eberly@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com

Thanks for the response, this is a breath of fresh air for sure.

"Dave Eberly" <eberly@magic-software.com> wrote in message news:<YeWNb.10008$q4.5904@newsread3.news.atl.earth link.net>...

> The Morrowind web site mentions editors you can get. Have
> you not tried this approach?

I have. There is one official construction set with a severely limited
toolset for modifying the terrain and two user-programmed utilities.
One crashes, the other doesn't give me the level of control I need for
my landscape. I couldn't get in touch with either author and their
source code doesn't seem to be available.

> The requirement for tiling the terrain without the CLOD causing
> cracking at the tile boundaries is that each tile be of the size
> (2^n+1)-by-(2^n+1). In your case, n = 6.

Excellent, that makes sense. Now I just need to find what sides the
row and column are on for each cell/tile. I should be able to do that
by comparing adjacent cell sides to see if they contain the same data.

> Has Bethesda Softworks not provided the format at its website?
> If legal, why would you need to "crack" the format?

Sadly not. They seem to get a kick out of letting people crack their
data file format themselves. They've offered some help/clues in the
past but generally try not to get involved in the hard core modders'
projects. Probably because of potential lawsuits since many of the
large-scale mods are based on things like Lord of the Rings, which I
doubt they have permission to do from the copyright holders. They do
their best to encourage modding, such as hosting a modder's forum and
releasing a fairly robust editor with the game.

The main problem I'm having deciphering the elevation data is hard to
pin down. The heights are rendered incorrectly. Much of what it
renders is correct, although vertical changes in elevation aren't
rendered at all. I tried to carry over the accumulative height past
each row's end instead of resetting it to zero, but that didn't work
either. It's bizarre. I'll post my code in a follow up to this.

Kevin Fishburne
kfishburne@_NOSPAM_pinestate.com

Here is a code snippet from the DrawCell() procedure:

' Interpret the cell elevation data in the file and draw it.

' Disable the button and open the ESM for input.
cmdVisualize.Enabled = False
Open txtESM.Text For Binary As #1

' Declare variables.
Dim fp As Long ' File position (current
place/byte in ESM).
Dim CellElevationRaw(4224) As Byte ' Contains raw elevation
data from the ESM.
Dim CellElevationRelative(4224) As Integer ' Contains relative
elevation data converted from CellElevationRaw().
Dim CellElevationAbsolute(4224) As Long ' Contains absolute
elevation data converted from CellElevationRelative().
Dim CellElevationOffset As Single ' Elevation offset (+ or
-) of the entire cell.
Dim ByteData(3) As Byte ' Contains raw elevation
offset data from the ESM (4 bytes). Used to calculate
' CellElevationOffset.
Dim VHGTHeader As String ' Used to grab the VHGT
header where it's -supposed- to be just in case fp is wrong.
Dim CellElevationRange As Long ' Total elevation range
(lowest point to highest point) for the current cell.
Dim LowestElevation As Long ' Lowest elevation for
the current cell.
Dim HighestElevation As Long ' Highest elevation for
the current cell.
Dim Counter1 As Integer ' Generic For...Next loop
counter 1.
Dim Counter2 As Integer ' Generic For...Next loop
counter 2.

' Set the current position in the file to the appropriate cell/offset.
fp = ((30304 * Cell) - 30304) + 288255

' Verify that the current position in the file is correct by
identifying the VHGT header.
VHGTHeader = Space(4)
Get #1, fp - 13, VHGTHeader
If VHGTHeader <> "VHGT" Then
MsgBox ("Cell " & Cell & " not found in usual location.")
GoTo EarlyExit
End If

' Get the current cell's elevation offset.
Get #1, fp - 5, ByteData()
' Convert the 4 bytes to single float.
CellElevationOffset = ByteToSingle(ByteData())

' Load the ESM elevation data into CellElevationRaw().
Get #1, fp, CellElevationRaw()

' Convert CellElevationRaw() from byte data to signed integers and
store in CellElevationRelative().
For Counter1 = 0 To 4224
' Convert the current vertex.
If CellElevationRaw(Counter1) > 127 Then
' Height is negative (-128 - -1).
CellElevationRelative(Counter1) = CellElevationRaw(Counter1) -
256
Else
' Height is positive (0 - 127).
CellElevationRelative(Counter1) = CellElevationRaw(Counter1)
End If
Next Counter1

' Convert CellElevationRelative() from signed integers to absolute
elevation data and store in CellElevationAbsolute().
' ******** This section is incorrect.
Counter2 = 0
For Counter1 = 0 To 4224
' Convert the current vertex.
If Counter1 = 0 Then
' First vertex in the array.
CellElevationAbsolute(Counter1) =
CellElevationRelative(Counter1)
GoTo ExitEarly2
End If
If Counter1 <> 0 And Counter2 <> 0 Then
' Other vertex in the array.
CellElevationAbsolute(Counter1) =
CellElevationAbsolute(Counter1 - 1) + CellElevationRelative(Counter1)
GoTo ExitEarly2
End If
If Counter1 <> 0 And Counter2 = 0 Then
' First vertex in row.
CellElevationAbsolute(Counter1) =
CellElevationRelative(Counter1)
End If
ExitEarly2:
Counter2 = Counter2 + 1
If Counter2 = 65 Then Counter2 = 0
Next Counter1

' Modify CellElevationAbsolute() by CellElevationOffset.
For Counter1 = 0 To 4224
CellElevationAbsolute(Counter1) = CellElevationAbsolute(Counter1)
+ CellElevationOffset
Next Counter1

"Kevin Fishburne" <Kevin_Edward_Fishburne@hotmail.com> wrote in message
news:3de59d6f.0401190636.91a949a@posting.google.co m...

> The main problem I'm having deciphering the elevation data is hard to
> pin down. The heights are rendered incorrectly. Much of what it
> renders is correct, although vertical changes in elevation aren't
> rendered at all. I tried to carry over the accumulative height past
> each row's end instead of resetting it to zero, but that didn't work
> either. It's bizarre. I'll post my code in a follow up to this.

Without knowledge of the format, reverse engineering might
be quite a chore. The algorithm I mentioned used a 16-bit
unsigned integer for the heights. However, some companies
had suggested using the "height field" storage to include other
information (some suggestions requiring increasing to 32-bits
per height field vertex). For example, there might be some
bits used to store compressed normals for lighting so that you
do not have to calculate vertex normals at run-time when a tile
is dynamically loaded. A few bits might even be reserved for
information that the game logic uses. For example, a few bits
could be used as a trigger so that when your character is
located in a specific portion of a tile, some reaction is started
in the game. Perhaps the rendering errors themselves can help
you deduce the number of bits used for height.

--
Dave Eberly
eberly@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com