magnusll

06-10-2007, 08:34 AM

Ok, so I was wondering about what to do with my stupid little extract utility, and thought it would be nice to add a feature which nothing else has, just to make it useful. And the two things which sprang to mind were, of course, walkmeshes and lightmaps.

I started to collect the available knowledge on walkmeshes, and found some incredibly useful information around which allowed me to read most of the info (notably the vertices, faces and AABB nodes) straight out of the bat. Despite that, it took me nearly one more week to decode the rest of the format, and I got stumped by really basic linear transformations that I should've been able to recognize in an instant. My mind is slipping as I'm getting old :(

But enough of the pitiful self-commiseration. You're here, I guess, to have a look at the .WOK file format info. Before delving into the details, though, obligatory thanks go to:

Fred Tetra

Torlack

Joco

without whom I'd still be wallowing in said self-commiseration, blankly staring to a bunch of uncomprehensible hex values.

And now, to the format: the Kotor .WOK structure is made of an header providing a few actual data and a bunch of pointers to further structures. It goes like this:

BWM Header structure:

char[4] FileType -- always "BWM "

char[4] Version -- always "V1.0"

UInt32 WalkmeshType -- always 1 for .wok, 0 for .pwk and .dwk

byte[48] Reserved -- always 0

Uint32 Position.X

Uint32 Position.Y

Uint32 Position.Z

UInt32 VerticesCount -- pointer to an array of BWM Vertices

UInt32 OffsetToVertices

UInt32 FacesCount -- pointer to an array of BWM Faces

UInt32 OffsetToFaces

UInt32 OffsetToWalkTypes -- pointer to an array of Int32

UInt32 OffsetToNormalizedInvertedNormals -- pointer to an array of Vertices

UInt32 OffsetToFacePlanesCoefficient -- pointer to an array of floats

UInt32 AABBCount

UInt32 OffsetToAABBs -- pointer to an array of AABB nodes

UInt32 UnknownEntry -- always 0 if FacesCount != 0

UInt32 WalkableFacesEdgesAdjacencyMatrixCount

UInt32 OffsetToWalkableFacesEdgesAdjacencyMatrix -- pointer to an array of BWM EdgesAdjacencies

UInt32 PerimetricEdgesCount

UInt32 OffsetToPerimetricEdges -- pointer to an array of BWM PerimetricEdges

UInt32 PerimetersCount

UInt32 OffsetToPerimeters -- pointer to an array of Int32

The structures are as follows:

BWM Vertex Structure:

float X

float Y

float Z

BWM Face Structure:

int V1_Index -- 0-based indexes into the Vertex structure

int V2_Index

int V3_Index

BWM Walktype Structure:

Int32 walktype -- same values as the NWMAX materials for walkmeshes

BWM AABB Node Structure (this is a tree structure):

BWM Vertex BoxMin

BWM Vertex BoxMax

Int32 LeafFaceIndex -- 0-based index of the face contained in this leaf; -1 for non-leaf

Int32 MostSignificantPlane -- tentative, to be verified; 0 for leaves, one of 1-2-4-8-16-32 otherwise

Int32 UnknownFixedAt4 -- = 4 in each node of each .wok in models.bif for Kotor I

Int32 LeftNodeArrayIndex -- -1 if this is a leaf, otherwise 0-based index of left child AABB node

Int32 RightNodeArrayIndex -- -1 if this is a leaf, otherwise 0-based index of right child AABB node

BWM EdgesAdjacency Structure (see below):

Int32 Face1_Adjacency -- all 0-based and -1 if perimetric

Int32 Face2_Adjacency

Int32 Face3_Adjacency

BWM PerimetricEdges Structure (see below):

Int32 Edge_Index -- 0-based

Int32 RoomAdjacency -- -1 if no adjacent room

Further details:

the number of Walktypes, normalized inverted normals and planes coefficients is the same as the number of faces.

The normalized inverted normals for each face are computed as follows: calculate the vector which is normal to the face (according to vector order 1-2-3), normalize it, and invert it.

The planes coefficients (or distances, or whatever you want to call them) are computed with a scalar multiplication of the normalized inverted normal with V1.

The EdgesAdjacency structure is an array of offsets into itself. It is built this way:

- build an array of faces which contains only the walkable faces of the walkmesh

- each of this faces will obviously have 3 edges: V1-V2, V2-V3 and V3-V1

- all those edges will constitute the AdjacencyMatrix. For each one of those:

- if the edge is not adjacent to any other edge (i.e. it is in a perimeter), write -1

- if the edge is adjacent to another edge, write the offset of that other edge into this matrix (remember, 0-based, so the first edge is at index 0). For each edge, there can be only one adjacent edge; it basically means the two edges are the same, and are shared between two faces. These are all the "internal" (not perimetric) edges, and probably precomputed to speed up the pathfinding algorithm.

The PerimetricEdges structure is built this way:

- build a list of edges from all the edges in the EdgesAdjacency structure which are perimetric (thus having a -1 in the matrix), pick the first one and write its 0-based index here in the Edge_Index field (the 0-based index is relative to the offset into the EdgesAdjacency structure; it is simply what would be the walkmesh edge number into Gmax, minus 1 as Gmax starts counting from 1 instead of 0)

- if the edge is adjacent to a room (i.e. if it is basically the threshold between two rooms), write in the RoomAdjacency field the 0-based index of the room to which it is adjacent (the room structure is in the relative .are file)

- if it is not adjacent to a room, write -1 in the RoomAdjacency

- delete the edge from the list of edges still to be processed

- now try to pick another edge which is in contact with the previous one (i.e. they share a vertex); if you find one, that one will be the next entry in the structure. Otherwise, pick the first edge still to be processed and proceed from there.

This basically builds a list of perimeters present in the walkmesh; you start from the first perimetric edge and "follow the line", so to speak, until you close it. After that, you find the next perimetric edge which you still have not processed and start the second perimeter, and so on.

If you're asking yourself while you need more than one perimeter: think about a square room with a pillar in the middle. Perimeter A = the room perimeter; perimeter B = the pillar perimeter. The Valley of the Dark Lords has 39 perimeters: the external one and 38 internal ones.

The perimeters structure is simply an offset into the PerimetricEdges structure detailing the end of each single perimeter. Note that this is NOT 0-based. This is effectively the sum of the edges of all perimeters computed up to the current entry. I.e. if you have two perimeters, the first one composed of 8 edges and the second of 4, you'd have two values in here: a "8" and a "12".

Now for the question that probably many of you are asking yourselves: no, I've not yet built a complete exporter-importer. I've the export part done (and in fact, I extensively used the exported walkmeshes while decoding the format). But I've yet to write the import part. Moreover, there is at least one info (the room adjacency field) which cannot be found in the walkmesh itself, and thus I'll have to write some kind of manual edit window which lets you link an edge to a room.

I'll let you know as soon as I've something done.

[Edited June 19, change in AABB node structure]

I started to collect the available knowledge on walkmeshes, and found some incredibly useful information around which allowed me to read most of the info (notably the vertices, faces and AABB nodes) straight out of the bat. Despite that, it took me nearly one more week to decode the rest of the format, and I got stumped by really basic linear transformations that I should've been able to recognize in an instant. My mind is slipping as I'm getting old :(

But enough of the pitiful self-commiseration. You're here, I guess, to have a look at the .WOK file format info. Before delving into the details, though, obligatory thanks go to:

Fred Tetra

Torlack

Joco

without whom I'd still be wallowing in said self-commiseration, blankly staring to a bunch of uncomprehensible hex values.

And now, to the format: the Kotor .WOK structure is made of an header providing a few actual data and a bunch of pointers to further structures. It goes like this:

BWM Header structure:

char[4] FileType -- always "BWM "

char[4] Version -- always "V1.0"

UInt32 WalkmeshType -- always 1 for .wok, 0 for .pwk and .dwk

byte[48] Reserved -- always 0

Uint32 Position.X

Uint32 Position.Y

Uint32 Position.Z

UInt32 VerticesCount -- pointer to an array of BWM Vertices

UInt32 OffsetToVertices

UInt32 FacesCount -- pointer to an array of BWM Faces

UInt32 OffsetToFaces

UInt32 OffsetToWalkTypes -- pointer to an array of Int32

UInt32 OffsetToNormalizedInvertedNormals -- pointer to an array of Vertices

UInt32 OffsetToFacePlanesCoefficient -- pointer to an array of floats

UInt32 AABBCount

UInt32 OffsetToAABBs -- pointer to an array of AABB nodes

UInt32 UnknownEntry -- always 0 if FacesCount != 0

UInt32 WalkableFacesEdgesAdjacencyMatrixCount

UInt32 OffsetToWalkableFacesEdgesAdjacencyMatrix -- pointer to an array of BWM EdgesAdjacencies

UInt32 PerimetricEdgesCount

UInt32 OffsetToPerimetricEdges -- pointer to an array of BWM PerimetricEdges

UInt32 PerimetersCount

UInt32 OffsetToPerimeters -- pointer to an array of Int32

The structures are as follows:

BWM Vertex Structure:

float X

float Y

float Z

BWM Face Structure:

int V1_Index -- 0-based indexes into the Vertex structure

int V2_Index

int V3_Index

BWM Walktype Structure:

Int32 walktype -- same values as the NWMAX materials for walkmeshes

BWM AABB Node Structure (this is a tree structure):

BWM Vertex BoxMin

BWM Vertex BoxMax

Int32 LeafFaceIndex -- 0-based index of the face contained in this leaf; -1 for non-leaf

Int32 MostSignificantPlane -- tentative, to be verified; 0 for leaves, one of 1-2-4-8-16-32 otherwise

Int32 UnknownFixedAt4 -- = 4 in each node of each .wok in models.bif for Kotor I

Int32 LeftNodeArrayIndex -- -1 if this is a leaf, otherwise 0-based index of left child AABB node

Int32 RightNodeArrayIndex -- -1 if this is a leaf, otherwise 0-based index of right child AABB node

BWM EdgesAdjacency Structure (see below):

Int32 Face1_Adjacency -- all 0-based and -1 if perimetric

Int32 Face2_Adjacency

Int32 Face3_Adjacency

BWM PerimetricEdges Structure (see below):

Int32 Edge_Index -- 0-based

Int32 RoomAdjacency -- -1 if no adjacent room

Further details:

the number of Walktypes, normalized inverted normals and planes coefficients is the same as the number of faces.

The normalized inverted normals for each face are computed as follows: calculate the vector which is normal to the face (according to vector order 1-2-3), normalize it, and invert it.

The planes coefficients (or distances, or whatever you want to call them) are computed with a scalar multiplication of the normalized inverted normal with V1.

The EdgesAdjacency structure is an array of offsets into itself. It is built this way:

- build an array of faces which contains only the walkable faces of the walkmesh

- each of this faces will obviously have 3 edges: V1-V2, V2-V3 and V3-V1

- all those edges will constitute the AdjacencyMatrix. For each one of those:

- if the edge is not adjacent to any other edge (i.e. it is in a perimeter), write -1

- if the edge is adjacent to another edge, write the offset of that other edge into this matrix (remember, 0-based, so the first edge is at index 0). For each edge, there can be only one adjacent edge; it basically means the two edges are the same, and are shared between two faces. These are all the "internal" (not perimetric) edges, and probably precomputed to speed up the pathfinding algorithm.

The PerimetricEdges structure is built this way:

- build a list of edges from all the edges in the EdgesAdjacency structure which are perimetric (thus having a -1 in the matrix), pick the first one and write its 0-based index here in the Edge_Index field (the 0-based index is relative to the offset into the EdgesAdjacency structure; it is simply what would be the walkmesh edge number into Gmax, minus 1 as Gmax starts counting from 1 instead of 0)

- if the edge is adjacent to a room (i.e. if it is basically the threshold between two rooms), write in the RoomAdjacency field the 0-based index of the room to which it is adjacent (the room structure is in the relative .are file)

- if it is not adjacent to a room, write -1 in the RoomAdjacency

- delete the edge from the list of edges still to be processed

- now try to pick another edge which is in contact with the previous one (i.e. they share a vertex); if you find one, that one will be the next entry in the structure. Otherwise, pick the first edge still to be processed and proceed from there.

This basically builds a list of perimeters present in the walkmesh; you start from the first perimetric edge and "follow the line", so to speak, until you close it. After that, you find the next perimetric edge which you still have not processed and start the second perimeter, and so on.

If you're asking yourself while you need more than one perimeter: think about a square room with a pillar in the middle. Perimeter A = the room perimeter; perimeter B = the pillar perimeter. The Valley of the Dark Lords has 39 perimeters: the external one and 38 internal ones.

The perimeters structure is simply an offset into the PerimetricEdges structure detailing the end of each single perimeter. Note that this is NOT 0-based. This is effectively the sum of the edges of all perimeters computed up to the current entry. I.e. if you have two perimeters, the first one composed of 8 edges and the second of 4, you'd have two values in here: a "8" and a "12".

Now for the question that probably many of you are asking yourselves: no, I've not yet built a complete exporter-importer. I've the export part done (and in fact, I extensively used the exported walkmeshes while decoding the format). But I've yet to write the import part. Moreover, there is at least one info (the room adjacency field) which cannot be found in the walkmesh itself, and thus I'll have to write some kind of manual edit window which lets you link an edge to a room.

I'll let you know as soon as I've something done.

[Edited June 19, change in AABB node structure]