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]

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 :).

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

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!

^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.

^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!

^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.

Yeah :D 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 :D

^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 :)

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 :p

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 :p

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.

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, 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.

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 :p

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.

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 :D

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 ;)

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.

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.....

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.

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

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).

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?

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.

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

And that is what magnusll is trying to? To create a compiling tool to compile the walkmeshes?

I have completed the rebuilding functions for the AABB trees (based on the above notes i.e. zeroing the "MostSignificantPlane" field... hopefully the game engine won't miss it too much; it shouldn't be needed for the tree traversal algorithm anyway), the adjacency matrixes and the perimeters. I just need to add in the code for the PerimetersCount structure, which is trivial since the perimeters are already done, and then I can start preliminary testing on imported walkmeshes.

On the "bad news" side, I've just discovered that the "m18ab_02a" walkmesh has no less than 195 faces adjacent to another room.... this is the piece of info which I mentioned must be set manually as it's not included in the walkmesh itself. I guess this rules out scratchbuilt walkmeshes with an half-mile long adjacency line, unless you have way too much free time on your hands....

And that is what magnusll is trying to? To create a compiling tool to compile the walkmeshes?
Yup, and this is another step closer to custom area creation!
On the "bad news" side, I've just discovered that the "m18ab_02a" walkmesh has no less than 195 faces adjacent to another room.... this is the piece of info which I mentioned must be set manually as it's not included in the walkmesh itself. I guess this rules out scratchbuilt walkmeshes with an half-mile long adjacency line, unless you have way too much free time on your hands....Looks like walkmeshes will still be hard to make though...

Looks like walkmeshes will still be hard to make though...
I see it this way... A little bit of extra work to make an area is a small price to pay considering that if we don't want to do all of that work we will never create a new area. Personally, I don't care how walkmeshes get done as long as they CAN be gotten done.;)

Why not do it the same way as BioWare did it? They made it someway. Why cant we do the same?

Why not do it the same way as BioWare did it? They made it someway. Why cant we do the same?

Errr, because we don't know what they did, i assume they have a special importer/exporter plugin for 3DSMax, but that isn't certain, and they may even have their own 3D tool for all their modeling needs which seems more likely.

But they dont want to share that with us and we have to respect that... if we know whats good for us.

Why not do it the same way as BioWare did it? They made it someway. Why cant we do the same?

The adjacency info was probably set using some kind of tool which linked together all the various maps/walkmeshes/etc. belonging to the same area. We don't have any such tool. The one I'm working on uses a single walkmesh at a time - and the info about which other rooms are adjacent to the mesh cannot be found in it since, technically, that info pertains to the layout of the area as a whole rather than the walkmesh itself.

It is reasonable to try and come up with an add-on to the import/export utility which makes editing this info easier - for example, a simple 3-d window which visualizes a wireframe rendition of the walkmesh and lets you select the edges to be linked by clicking directly on them, maybe with an additional option to load the rooms from an .are file and show the possible values as a dropdown list using the room names instead of a zero-based index. But honestly, I'd much rather release a functional (if somewhat clunky) utility as soon as possible, than delay it for weeks while I try to learn Direct3D programming to implement a spiffy visualization window.

Instead of learning Direct3D, maybe you could create an exporter from 3ds max/gmax by learning MaxScript? I tryed once and its pretty simple, Autodesk have documentation on it included with 3ds max.

Instead of learning Direct3D, maybe you could create an exporter from 3ds max/gmax by learning MaxScript? I tryed once and its pretty simple, Autodesk have documentation on it included with 3ds max.


Don't forget the Win32 stuff you'll need for those nice "windows" .

Anyway I'm just glad you people are trying to crack this hard big nut .
Can't help ; sadly I suck at scripting and programming .

Hope you can make a good tool that doesn't ask to much of weird file handleling magic .

Another quick update... I completed the code for rebuilding the binary format and started the preliminary tests. I chose to use the Valley of the Dark Lords' walkmesh as a testbed, as it's a relatively complex one.

The first three tests ended in swift crashes :p, but that was due to a stupid mistake I made in the code which rebuilds the header. After fixing that bug, I was able to successfully load a savegame using the recompiled walkmesh.
I first tried by simply modifying the faces which represent the fallen column in the middle column row, making them walkables. I could walk in the valley and everything was apparently normal, but going near the fallen column, I was still unable to walk on it.
Unsure if that was a problem of the imported walkmesh, I further modified it, this time changing a few faces into "unwalkableness". Reloaded the savegame and... I got stuck. I couldn't move, as apparently the whole valley (or most of it anyway) was suddenly unwalkable. Also tried to teleport away and reenter it, but couldn't manage as the engine wouldn't let me walk in.

I was puzzled by this, and thought at first about a bug in the rebuilding of the walkable adjacency matrix or the perimeters. Then I noticed how inserting a few unwalkable faces messed up the whole valley; an idea struck me, I made a check, and sure enough.... the faces are sorted :evil3: . All the walkable faces come first, and then the unwalkable ones are stored in the last positions of the faces' array. I completely missed this little bit of info until now :doh:

I've added the relevant code in, but will have to wait until tomorrow before being able to do a few more tests. I'll let you know as soon as I can finally make these $%&/ walkmeshes work...

With every error found is a step closer to success.

Well i thought that line needed to be said here, :)

Keep up the good work.

I've done the tests with the new code. I put the newly-edited .wok in the override folder, I loaded the save game aaaaaaand.....

... it works :cool:

I can finally walk where I'm supposed to be able to and not walk where I'm not supposed to. The pathfinding algorithms do not seem to have any problem either, as your companions (and/or enemies) are still able to find their way around.

I've also tried with another walkmesh: the room in the Taris sewers with the Rancor in it. I made unwalkable the faces where the Rancor is, while making walkable the lateral ones near the room exit (where there's the lightly depressed floor with a gap before the central corridor).
The first attempt made the whole room unreachable, but that was because I forgot to manually put back in the room adjacencies. Once that was corrected, I could waltz in the room and pelt the Rancor to my leisure, as it couldn't move. Who's the boss now, hu, stupid Rancor :D

Give me a few days to put everything in an usable form, and I'll start looking for a place to upload the utility. I'll also include some simple window which will let you manually edit the room adjacencies (as the walkmesh is useless without them), along with a small tutorial on how to edit them. As soon as I can get everything uploaded, I'll post the link in the "T3-M4's Astromech Droid Center" forum.

I can finally walk where I'm supposed to be able to and not walk where I'm not supposed to. The pathfinding algorithms do not seem to have any problem either, as your companions (and/or enemies) are still able to find their way around.


Very nice. :)

As for the path finding, the path nodes seem to be specified in the areaname.PTH file within the area's module, which is a standard GFF format file. So if you make major changes to where you can and cannot walk in an area you may need to make changes to this file as well and move the nodes around.

This is great news, looks like we can make Sleheyron from scratch after all! :D

I think, all that remains now is lightmaps?

Amazing news, great work magnusll :thumbsup: now all we need to solve is lightmaps, huh, thats gonna be a little tricky.

I've done the tests with the new code. I put the newly-edited .wok in the override folder, I loaded the save game aaaaaaand.....

... it works :cool:

Great work magnusll, this thread is being watched with anticipation...

Very nice, indeed :).

Just as an addendum to what stoffe said: The path nodes in the .pth files are to do with waypoints; more specifically, how to get from one of them to the other. You could just have two waypoints in a module and have an elaborate pathway file to direct the NPC walking that path to various locations - which is completely pointless when one considers the fact that it's much easier to place a waypoint than it is to edit the .pth for a module. The movement of NPCs without waypoints (such as party members following the player) seem to be independent of this file :).

If you do want need to edit the pathways - because you've created a massive "unwalkable" area where a path would normally lead a creature through - then beware. One error can lead to glitches in waypoint walking - large glitches.

Anyway, nice to see some progress on this :).

Awesome work Magnusll, I can't wait to see it when it comes out!:D

Give me a few days to put everything in an usable form, and I'll start looking for a place to upload the utility. I'll also include some simple window which will let you manually edit the room adjacencies (as the walkmesh is useless without them), along with a small tutorial on how to edit them. As soon as I can get everything uploaded, I'll post the link in the "T3-M4's Astromech Droid Center" forum.
If you need a place to upload, or at least an alternative, just let us know. We'd be happy to host the utility at SWK (starwarsknights.com) along with all of the other modding tools, I'm sure the community would welcome this one to the Family :D

Just an heads-up for those who may be tracking this thread: I've created another thread in the modding tools forum with a link to the first release of the editor. You can find it here:

thread (http://www.lucasforums.com/showthread.php?t=180034)

Further discussion of the utility will take place in the dedicated thread.