Loading and Rendering WMOs

Well that was easy!  Turns out the WMO files are super easy to get rendering.  Thanks to Blizzard, the WMOs contain all the index and normal data so I made quick work of simply popping the data into some buffers and threw ‘em up on screen with some really simple lighting.  Still no textures yet, but I’m going to work on it next I think cause I’m getting sick of looking at flat white objects.  I know there’s an OpenGL BLP loader out there somewhere, just gotta find it and rewrite it to my liking.

Below are a couple quick renders of the top half of the Tuskarr boat.  I noticed some strange z-fighting on some other WMOs like the Goblin laboratory seen in Ratchet.  I still don’t know the cause of it but I think it might have something to do with the render batching that I haven’t yet implemented.

Wireframe

Fill

Stay tuned for some textures on these things!

World of Warcraft World Viewer

I’ve started work on a project with my friend Aaron for a World of Warcraft World Viewer.  It’s essentially for my own enjoyment and experience but it could also be used to supplement a World of Warcraft bot that he intends to work on.

I’ve decided to start with the terrain to begin with.I’ve been using the material from the MPQNav blog and WowDev to guide me along in the process just to understand how the file formats are all laid out for the terrain.

ADT rendering.

Right now I have it loading in the terrain from ADT files and rendering them all in one draw call using OpenGL’s vertex and index buffers.  This would be fast and efficient if it wasn’t drawing the entirety of the ADT at the highest level of detail!  Right now, my program is running rendering 65,536 triangles one go.  Worst of all, I have to render it using a triangle list.  So I’m passing a list of 196,608 indices to the graphics card and saying “have fun!”  I’ll no doubt have to employ some level of detail algorithm to ensure I’m not killing the graphics card.

Since I’ve gotten the terrain loading working, I think I’ll move on and do some of the WMO loading.  Just so happens there’s a BSP component to the WMOs too!  Likely for the huge WMOs like Orgrimmar, Stormwind, Dalaran etc.

I’m going to actually update this blog somewhat regularly now just for a journal of what I’m doing nowadays.

Deciphering the Node Tree

The BSP node tree is a bit tricky.  More specifically, the coordinate system for the node tree is tricky.

A BSP file breaks down the world into a binary tree consisting of nodes.  A node has a bounding box, face count, face pool index and two child indices into the node pool.  To efficiently find out what leaf we are in, we search the tree recursively by checking if the camera’s current position is inside the bounding box of the current node we are searching.  If it is, we check both its children recursively until we determine what node we are in.  This is exponentially more efficient than checking all of the leaves for camera containment.  Initial tests show the search depth to be, on average, about 20 nodes until it reaches a leaf.

Node Bounding Box Oddity

However, there are some anomalies I have experienced.  Most of the time, the algorithm works as I expect but other times I am surprised to find that the program thinks I am in a node that is considerably far away.  I am not sure if this will persist when I am finding what leaf we are in instead of the leaf’s node.

For the most part, though, I am pleased with my progress so far.  It is not without it’s serious setbacks, though.

I did tests earlier to see if I could stripify a face.  To my surprise, it seems like some edges faces don’t even close, as though there is an edge missing.  I still have yet to look into this in any depth though.

Drawing The BSP

Since I had all the neccesary data to render the world, I figured I’d give it a shot.

Anzio Beach

I was pleasantly surprised to find that to the best of my knowledge everything was working just fine.  My initial draw test was to just render all the vertices but it turned out to be a disaster because only small detailed objects were recognizable, if they can even be called that.  At this point, the program merely renders all the edges in the world.  The method is basically just used to check that everything is in tact and I haven’t read in anything incorrectly.

The next step is to render all the faces (hopefully) correctly.  Each face in a BSP is defined by a collection of no less than three edges which point to two vertices in the world’s vertex pool.  I was initially worried about how I was going to triangulate the vertices but as luck would have it every surface is convex and as such I can use a Triangle Fan to render the face since it’s my assumption that the edges are stored in a clockwise or counter-clockwise order and choosing a base point is arbitrary.

Brush Entities Misbehaving

I also learned that some brush entities need to be translated and rotated by their defined origin and rotation in order to be placed correctly in the world otherwise you end up with landing crafts in the sky.

So everything is going well for now.  There are a couple of things I am worried about.  Firstly, if I want the program to render efficiently I’m going to need to perform a lot of culling.  Camera frustum culling is not a problem but I may have to replicate the way that the engine does it’s visibility culling.  This is not a problem, however, as long as the visibility lump can be deciphered.

Secondly is the textures and their alignment.  I still need to do some research into how to first load them into the program for use, and then align them properly on the faces.

BSP Version 30 File Format

The BSP file format is at first glance rather confusing.  Compared to it’s successor it’s very minimalistic as well.  Instead of storing the  brush data it originally belonged to it merely stores the compiled surfaces that are visible or are special like clip or trigger faces.  This is of course the problem from the get go and why previous attempts to recreate any meaningful brush work are merely demonstrational and overall useless for a faithful reconstruction of the map.

The Half-Life engine renders its worlds using a kd-tree algorithm.  A kd-tree is a binary space partitioning (BSP) algorithm that splits up space along various planes.  The planes in this case come from the various surfaces of walls, ground and so on.  When you compile a map, the compiler generates this tree so that it can render the game optimally.  I could write an entire article on how this works but that’s not my intention.  You are free to look into these concepts elsewhere.

There is a very good document outlining the BSP version 30 file format that I am basing my work off of.  You can find it here.

BSP Model Structure

Though very helpful,  it is not complete.  For example, it does not list how the visibility information is stored which is vital to the program running efficiently and coherently.  However, all is not lost as I know it has been done before with other third-party programs.  I also feel strongly that it’s likely the visibility information is identical to a previous or later version of the file format.  Take for example the Quake 2 BSP file format, using version 38.  The data is arranged in a very similar way to version 30 of the file format so I will experiment with reading it in those known ways to see if I can extract the visibility data.

I’m going to be writing the reconstruction tool using C# and Microsoft’s XNA Framework simply because it is what I am most comfortable with.  Though rudimentary, I have written a couple XNA engines before so I am not too worried about how to set up the rendering engine using space partitioning trees.

As it is, I have the file format deciphered to a point where I could render the map, however it would likely be very slow to draw due to the lack of visibility information.

I may post my BSP loading DLL and source code when I feel it is as accurate as it can be.

Half-Life BSP Decompiler

I’ve begun work (a while ago actually) on a program that I had hoped would be able to with a click of a button convert Half-Life BSP files into their original RMF or VMF file with all the solid object data intact.  As I progressed however, I realised that this is quite an impossible task. Unlike Source engine BSP files, Half-Life BSP files do not store their original brush data and makes simple decompilation not an option for this task.

Now, the reason I am so interested in doing this is primarily to convert the old Day of Defeat v1.3 maps into maps that can be played on the Source engine which has a significant online gaming community unlike it’s predecessor which has slid into an endless pit of empty servers and bots fighting bots.  There’s something almost magical about these maps that drives me to complete this program.

Day of Defeat

I first played Day of Defeat some seven years ago (I feel old now) and the map I remember seeing was dod_overlord. At the time, I experienced many hours of enjoyment storming the beaches or alternatively holding the beachhead with all my might.  The graphics were top notch at the time…sort of.  Looking back, it was extremely blocky. But then again this was a free Half-Life modification.  Better looking games were kicking around in 2002 but this one held my interest.

Enough reminiscing though, back on track!  With my dreams crushed of a quick click of a button ‘conversion’ from one engine to the other, I had to dream up another way to port over the maps.

My options are very limited. I’m basically left with either writing a  ‘staight port’ program that somehow takes in the already compiled surface and visibility data from Half-Life and compiles it on the Source engine or I can devise a visual tool to aid me in manually reconstructing the brushes one by one.  So in the spirit of adventure and learning I have gone with option number two.

dod_overlord

I envision the tool to be rather similar to Valve Hammer Editor or even Nem’s Crafty program.  The basic concept is to select faces that will comprise a given brush.  Take for example, a box sitting on the ground.  What the tool will do is allow you to select the surfaces to comprise a new brush.  If surfaces are missing I will write algorithms to fill in missing surfaces.  If surfaces are fragmented due to VIS slicing I will implement a way to combine the surfaces.

This is merely a rough draft and a jot down of my plans for this tool.  I will go into more detail as problems arise so I may document how I plan to solve them.

I will probably write a draft of the Half-Life BSP file format as I understand it as my next entry and detail some of the problems I anticipate I will run into.