The Kotor walkmesh format

[magnusll]

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]

[Pavlos]

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.

 

This is indeed good news and I'm glad someone's picked up the torch .

[Master Zionosis]

This is very good news, I'm going to watching this thread very closely to see the progress.

[Gargoyle King]

This looks very promising - does this mean that we are closer to actual custom module building, i'm sure the guys at Team Jawa are going to love this!

[Darth InSidious]

^No. No lightmaps yet.

 

Aside from the fact that even if we had, it's virtually impossible to do, given that you have to model each room individually, and then will have to go through a probably quite complex method of creating walkmeshes and then lightmaps for it. So not really.

[Gargoyle King]

^No. No lightmaps yet.

 

Aside from the fact that even if we had, it's virtually impossible to do, given that you have to model each room individually, and then will have to go through a probably quite complex method of creating walkmeshes and then lightmaps for it. So not really.

 

Tshh, quite a shame really (but one can only hope).

 

P.S. Have you got any updates on your Rhen Var mod for TSL InSidious, it's looking very good by the screenshots and i'll definately download!

[magnusll]

^No. No lightmaps yet.

 

Aside from the fact that even if we had, it's virtually impossible to do, given that you have to model each room individually, and then will have to go through a probably quite complex method of creating walkmeshes and then lightmaps for it. So not really.

 

I can't speak for lightmaps yet, but as for walkmeshes, the smart thing to do would be to select the mesh you've used while creating the room, copy it, assign it the walkmesh modifier, add whatever other meshes you might need (likely a few additional vertical walls), then simply assign the proper material to the various faces.

I'm quite far from being an expert in Gmax, but I didn't have any problem manipulating the walkmeshes I imported with my tool using the NWMax menus. As soon as I've completed the importer side, the walkmesh you created would be auto-imported and ready to go, with the only exception being setting the room adjacency manually. But I've cycled through all the walkmeshes in models.bif for Kotor I, and not one of those had more than two room adjacencies; so it shouldn't be too big of a task to add in a couple of values.

 

Creating the room in the first place, on the other hand... now that is another matter. But this maybe my abject incompetence at anything graphic which is speaking, so I'll let better 3d artists than me (i.e. everybody on the planet) speak on this.

[Quanon]

Yeah great news !!! A bit sad of the lightmap stuff , but this would mean we could make platform or other stuff you can walk on .... yeah.

 

But without the lightmap I guess any room or map you make would be black ?

 

Anywayz , it's always good the hear this kind of news

[Darth InSidious]

^The room would indeed be black

 

@magnusll: Possibly. Nonetheless, the modelling of new rooms themselves that are more than boxes would be tough going. And then there's the job of finding a use for the room

[Quanon]

Just a quick question : Is it possible to use just the walkmesh and lighmap of say Manaan ; but to build a new décor around it ?

 

Cause this looks promising ; but I guess you would still need to program some sort of renderer who would translate the light-info from your moddeling program to a file Kotor could use .

 

This would be something like the .VIS files like they use in JA maps , right ?

 

Anyway , keep up the good work

[magnusll]

Just a quick question : Is it possible to use just the walkmesh and lighmap of say Manaan ; but to build a new décor around it ?

 

Cause this looks promising ; but I guess you would still need to program some sort of renderer who would translate the light-info from your moddeling program to a file Kotor could use .

 

This would be something like the .VIS files like they use in JA maps , right ?

 

Anyway , keep up the good work

 

Well, if you use the original walkmesh and lightmap, you don't really need to import anything except the new room itself... as you would just rebuild the mod with the original binary files. But, why would you start from the walkmesh instead of starting from the room itself? I was under the impression that room models could already be imported in gmax?

 

As for lightmaps, I'll try my hand at it as soon as I get the walkmesh import to an usable state. Shouldn't take too long now that I know how to build the data.

[Pavlos]

As for lightmaps, I'll try my hand at it as soon as I get the walkmesh import to an usable state. Shouldn't take too long now that I know how to build the data.

 

magnusll, is there any chance of releasing your source code once you're done? I'd be interested to see how you've gone about doing things .

[magnusll]

magnusll, is there any chance of releasing your source code once you're done? I'd be interested to see how you've gone about doing things .

 

Sure. As I said in the thread about my utility tool, everything will be released under some sort of public license, most likely some GPL variant.

 

Keep in mind that I know nothing about 3d graphics; the algorithms I'll be using will be simple and utilize a brute force approach. I'm pretty sure there has to be some very efficient way of computing perimeters... but I don't know it and have no intention of finding it out.

 

On the plus side, this will make the code more readable. As a matter of fact, I'm purposefully avoiding any sort of C tricks (like direct array loading, which would certainly be faster) and making it a point of trying to approach everything in an almost didascalic manner. I figure that this will make the code more useful for anyone else as a starting point; and you can always add optimizations later. Besides, considering modern CPU speeds and the fact that file format conversions don't need real time, it's a moot point anyway.

[Quanon]

Well I've already imported a few modules-parts into 3D-max before ; I know this works ; I think its possible to import any model into MAX but it's a real hassle to get it back into Kotor .

 

I've seen an older thread where they talked about re-using walkmeshes .

 

But I'll wait for your ToolKit ; I'm no wizzked in programming ( had C++ this year in college but failed misserbly :s )

 

But thanks for the quick reply's

[Darth InSidious]

The problem is exporting the models. They become distorted.

 

Also, if you try and put one module's lightmapping with another, even slightly different module, it doesn't work. I've tried it before and got nowhere.

[glovemaster]

When i started this i got the ASCII stage sorted and worked out a way to export them from 3ds max. I hope you get a compiler/decompiler sorted soon Im not much of a programmer and got stuck here.. :'(

Well done so far

[magnusll]

A quick update on the importer: I'm stuck on rebuilding the AABB tree. The AABBs as built by the NWscripts are different from the original ones found in the binary files. Kotor uses a different algorithm, and despite having spent a ludicrous amount of hours trying to decipher it (and learning much more than I could ever want or need on AABB trees, K-Dops, BVHs and the like), I haven't been able to completely crack it... yet.

 

What I found out so far is that Kotor AABB trees are perfectly balanced, so once the splitting axis is chosen, the splitting point is the median of the faces' centroid coordinate on the chosen axis. What I still can't figure out is the algorithm they use to pick the best axis. The weird thing is that you can normally pick between three choices (i.e. X, Y or Z) but in Kotor's trees, the hypothetical Best Axis value can actually assume one of six values (1, 2, 4, 8, 16 or 32).

I *think* (based on some preliminary checks) that the first three values (1, 2 and 4) correspond to the X, Y and Z axis chosen on the basis of the "split on the longest axis" heuristic. I have yet to figure out the meaning of the last three values, and how they choose between the two triplets. I've tried using the 20 diagonal halfspaces that cut the corners and edges of the bounding boxes, but none of them seems to replicate the original splits.

The use of different heuristics can't help, either, as all of them would simply result in the choice of an axis in the (X,Y,Z) set; I need to figure out *how* they sort the faces when using those last three values, before I can work on how they choose between the three options.

 

I'll keep trying to solve the puzzle; in the meantime, if anyone here is an expert in 3-d collision detection algorithms, I could certainly use the help

[glovemaster]

Yeah, I noticed that the AABB nodes had 5 values rather than 3 aswell, i have noticed the exact same pattern in the MDL format. Maybe you could ask JDNoa how it works for MDL files? Not how to compile it maybe but you might be able to find out how it works.

[magnusll]

Yeah, I noticed that the AABB nodes had 5 values rather than 3 aswell, i have noticed the exact same pattern in the MDL format. Maybe you could ask JDNoa how it works for MDL files? Not how to compile it maybe but you might be able to find out how it works.

 

Ehrm. As far as I can tell, mdlops imports the aabb nodes as they're done by NWMax? I don't know Perl though, and I only gave a cursory glance at the source code.

 

But, what you pointed out made me realize that I'm an idiot. I've just tried to run a check on all the walkmeshes in Kotor I (except one which I think is bugged), and simply using the "split along the longest size" and "choose the median" I got a match on over 86.9% of all the nodes. I'm willing to attribute the remaining 13% discordance to rounding problems, so this should explain the AABB tree building algorithm. So the only significant change is choosing the median instead of the mean, which I found out almost immediately, and I wasted over a week (sigh).

And Torlack was probably right in naming that damn field as "Most Significant Plane". It certainly doesn't look like a "BestAxis" now, at any rate.

 

Maybe it's time to go on with rebuilding the rest of the data and just try to see if anything horrible happens by zeroing that data and reimporting the model.....

[glovemaster]

NWmax will not export walkmeshes. I have found a way though,

You need to create the walkmesh as you would normally (well you wouldn't normally but i mean in general) and export as MDL. Then look through the ASCII MDL file and you can extract the data for the walkmesh manually.

[Mindtwistah]

Stupid question probably but what does walkmeshes do? And what is it?

[magnusll]

NWmax will not export walkmeshes. I have found a way though,

You need to create the walkmesh as you would normally (well you wouldn't normally but i mean in general) and export as MDL. Then look through the ASCII MDL file and you can extract the data for the walkmesh manually.

 

? My NWMax exports them all right? All you need to do is to create an AuroraBase, then an Editable Mesh, then apply the Walkmesh modifier to the mesh.... select both the AuroraBase and the mesh and export everything, and you'll find the AABB node info in the exported file. I'm using NWmax 0.7 with Gmax. If you want to build a walkmesh for a surface you already modeled, what I'd do is to clone the surface and create the walkmesh by itself, then change whatever you need to...

 

But this is a moot point anyway, as if the importer is going to rebuild the tree all that it will need is the vertices and the faces (the faces' material is the info used by the game to distinguish between walkable/non walkable surfaces).

[glovemaster]

hmm, thats strange.. it doesnt work for me with NWmax 0.8 and 3ds max 9. maybe its version 8.0 doesn't work properly?

[sekan]

Stupid question probably but what does walkmeshes do? And what is it?

 

Walkmeshes is the thing in the game that does that you can walk on ground.

I haven't tried to make a walkmesh but i think they are extremly hard to make.

[glovemaster]

Actually, walkmeshes are very easy to make, the problem we have is compiling them into a format the game can read.