{"id":49749,"date":"2020-04-16T06:00:48","date_gmt":"2020-04-16T10:00:48","guid":{"rendered":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=49749"},"modified":"2020-04-16T10:51:56","modified_gmt":"2020-04-16T14:51:56","slug":"revisiting-a-dead-engine","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=49749","title":{"rendered":"Revisiting a Dead Engine"},"content":{"rendered":"

This is a second entry, following the first one<\/a>, which makes this a series now.\u00a0 If you remember, my son Issac made a level for Garry’s mod that I thought was cool, and I foolishly assumed it would be easy to get it translated to a modern engine. Here’s the original level:<\/p>\n

This is what it looks like in Garry's Mod.<\/div>
This is what it looks like in Garry's Mod.<\/div><\/p>\n

It was unreasonably difficult to extract all of those polygons and render them in another game engine. Let’s talk about why.<\/p>\n

The Source Engine 2<\/a> has a bit of a murky history. Source is Valve’s in-house engine. It’s the technology driving Half-Life 2<\/em> and its attendant episodes. It’s what they used for the Left 4 Dead<\/em> games and DOTA 2<\/em>. It was the engine behind Valve’s beloved Portal<\/em> games. Wikipedia will tell you that Source 2 was officially announced in 2015, but in truth there wasn’t a clear division between Source engine (Original Flavor) and Source Engine 2 (Electric Boogaloo). Rather it was a gradual process of evolution, and Valve arbitrarily decided that 2015 was the cutoff point between old and new. Left 4 Dead 2<\/em> levels (2009) could do a ton of things that Half-Life 2<\/em> levels (2004) couldn’t. In Portal 2<\/em>, they finally got around to adding realtime shadowsThe bit where Wheatly guides you through the darkness with his eye-light was a first for the engine. This is apparently significantly different from the shadow-casting flashlights of Left 4 Dead<\/em> in ways I’ve never bothered to look up.<\/span> with dynamic light sources, about a decade after everyone else. The Left 4 Dead<\/em> levels were incompatible with the engine used in Half-Life 2<\/em>, so I fully expected that to be the recognized demarcation between New and Old, but apparently that didn’t happen until DOTA 2<\/em>.<\/p>\n

The point here is that the original Source Engine was descended from the Quake 2 engine, and many of the underlying data structures are the same. So even though I’m trying to read in a level that was made this week, this involves reaching all the way back to 1997 or so and speaking the language of late-90s game engines. There are things that this engine does that made no damn sense in 2010, and are downright archaic by 2020.<\/p>\n

Source engine maps are stored in .BSP files.\u00a0This site<\/a>, which I linked in the previous entry, is effectively our Rosetta Stone<\/a>. Without this, I’d never have any hope of sorting this out. That documents how a .BSP map is put together.<\/p>\n

A Throwback Data Structure<\/h3>\n

The entire file format reflects a very vanilla C design style. It’s very obvious that the level compiler just writes raw data structures to disk. A data structure might look like this:<\/p>\n

\r\nstruct lump_t\r\n{\r\n  int offset; \/\/ offset into file (bytes)\r\n  int length; \/\/ length of lump (bytes)\r\n  int version; \/\/ lump format version\r\n  char ident[4]; \/\/ lump ident code - 4 bytes\r\n};<\/pre>\n
Incidentally: This data structure being called a “lump” is somewhat reminiscent of 90s video game data naming schemes. In those days everyone ran into the problem of, “Hey, I need to jam a bunch of unrelated data into a single monolithic file. What should I call these files?” And so we wound up with WAD files (Doom) BLOB filesI can’t remember which engine used blobs. I’m 51% sure it was Descent.<\/span>, and such. This lump structure was the obvious and minimum-effort way to store crap in the days when C ruled the programming world. You open a file, and then shove the contents of a data structure directly to disk.<\/p>\n
The file headers contain information like “The vertices are stored 34,532 bytes into the file, and the vertex data is 23,964 bytes long. Since you know vertex data is 12 bytes longA floating-point number is 4 bytes long. You need 3 of these for an X, Y, Z position.<\/span>, you can divide that length by 12 and know that there are 1,997 vertices. This sort of business is perfect if you’re a frugal late-90s programmer and you want to skip around the file, loading only the things you need right now, because you can’t afford to decadently waste a whopping 2 megabytes of main memory on a data structure you’re not currently using.<\/p>\n
The lump_t structure defined in the code above would be exactly 16 bytes longEach int is 4 bytes. A char is one byte, but there are four of those.<\/span>. So you take a raw memory pointer and aim it at your data structure, then you tell the program “Starting at this spot, write the next 16 bytes of memory into this file on disk.” Then when it was time to load the level, you’d do the reverse. You’d aim the pointer at the start of the structure, and take\u00a0 the next 16 bytes out of the file and shove them into that spot of memory. If you made a mistake and wound up out of alignment with the file during the reading process, then you were doomed. Even being off by a single byte would turn the data into a random mess.<\/p>\n
To be honest, I kind of liked the simplicity of those days. Everything either worked perfectly or failed catastrophically. While young people get nervous handling raw memory pointers, I thought it was a great approach in situations like this.<\/p>\n
Regardless of how you felt about those days, they are over. Modern languages don’t want you juggling raw memory pointers and randomly writing blocks of bytes into bits of memory. In C#, this sort of behavior isn’t just discouraged, it’s forbiddenDisclaimer: There might be some black-magic hack around it. I wouldn’t know. I’ve only been using the language for a couple of years and there’s a lot I don’t know.<\/span>. You can’t write to memory like that, filling several variables at once. Moreover, this sort of business would break encapsulation. Even if you were allowed direct, unsupervised memory access, your file-loading code wouldn’t be allowed to write into your level-data structures. And even if you somehow found a way around all of thatYou could make all the data structures public, which is a huge OOP<\/a> no-no. That’s what I did, and I don’t even feel guilty.<\/span>, you can’t be guaranteed that the memory layouts would match.\u00a0I don’t understand the rules, but people more familiar with this sort of thing tell me that the compiler might mess with the layout of your data, padding it with a byte here or there for some sort of optimization. And even if you got over all of that, I’m sure there are lots of other problems I’m overlookingI’ll bet array data is stored completely differently.<\/span>.<\/p>\n
None of this means you can’t read the file. It just means that reading the file is a little strange and inconvenient. You can’t fill an entire data structure in a single read operation, but you can read it into memory one variable at a time.<\/p>\n
The Problem with Fans<\/h3>\n
I mentioned in the previous entry that this document<\/a> is – as far as I can tell – the only publicly-available document on how these files work. I also mentioned that it doesn’t tell you everything you need. Don’t get me wrong, this is an incredible document and I’m very glad for the hard work that the author put into it. It’s just that sometimes things get overlooked, possibly because they’re things that “everyone knows”. Which is fine, until you reach the point where everyone forgets about it and all we have left is the document.<\/p>\n
In the modern world, we’d generally store geometry as vertices (a bunch of positions in 3D space) and a list of indexes describing how those vertices form triangles. It’s basically a 3D game of connect-the dots.<\/p>\n
This was not the case in the world of 1997, before the rise of graphics cards. At the time, you generally had to shove your vertex data at the renderer one at a time. Thus an important optimization was to send as few verts as possible.<\/p>\n
Consider this arrangement of polygons:<\/p>\n
This is the best illustration I could come up with in 5 minutes or less.<\/div>
This is the best illustration I could come up with in 5 minutes or less.<\/div><\/p>\n
Today, we’d give the graphics card all the verts up front. We’d send them all in one bulk load, and then refer back to them.<\/p>\n
“Draw the triangle defined by A-B-G”.<\/p>\n
“Now do B-C-G.”<\/p>\n
“Then do C-D-G.”<\/p>\n
And so on, until it’s all drawn.<\/p>\n
But in \u00fe<\/b><\/a>e Olden Days, you couldn’t “store” verts on the graphics hardware like thatOften because this machine didn’t have any.<\/span>. Which means that sending triangles like this would be painfully inefficient. You’ll notice in the list above, I sent B twice, C twice, and G 3 times. In fact, to send the entire mesh, I’d have to send every point twice. Except for G, which would get sent once for every triangle, a total of 6 times.<\/p>\n
That would be horribly wasteful. But! There’s a way we can avoid this. We can use a triangle fan<\/strong>. To describe a fan, I’ll just paste in one of my comments:<\/p>\n
\r\n\/\/Now each face has a list if triangle fans, seperated by -1 indexes. We need\r\n\/\/to pull these apart and make them into regular triangles.\r\n\/\/For you kids, a fan is a series of triangles built around a common hub.\r\n\/\/The first vertex in the series is the first vertex for ALL triangles.\r\n\/\/After the first two verticies, each additional vertex adds a new triangle.\r\n\/\/Each triangle is defined as so: (index 0),(previous index), (current index).\r\n\/\/So the series A B C D E would result in 3 triangles:\r\n\/\/ABC , ACD, ADE. The fan system is pointless in a modern hardware context,\r\n\/\/so we just need discrete triangles. The following loop does this.\r\nfor (int f = 0; f > _face_count; f++) {\r\n  \/\/complex hoodoo goes here\r\n}\r\n<\/pre>\n
So the triangle fan for the image above would go G A B C D E F A.\u00a0 Every vertex gets sent once, except for A which needs to be sent a second time to close the loop.<\/p>\n
Not a bad system for 1997, but it’s totally useless today. These days we send all the verts in one bulk load and can refer back to them as many times as we like for no additional costI mean, aside from the cost of drawing the resulting triangles.<\/span>. The graphics card can go to work on the entire job without needing to wait around to be spoon-fed vertices one at a time.<\/p>\n
I know this looks like a big tangle of random lines, but once you do the work to create the view frustum, transform the verts, render the polygons, and calculate the lights, it can really look like something sort of half-assed.<\/div>
I know this looks like a big tangle of random lines, but once you do the work to create the view frustum, transform the verts, render the polygons, and calculate the lights, it can really look like something sort of half-assed.<\/div><\/p>\n
What I’m getting at here, is that the vert data inside of a BSP stores all triangles as triangle fans. The document doesn’t tell you, and there’s no way to intuit that from the code. You just have to know it. I had to find the original Quake 2 source and dig around in the code for ages until I found this accidental secret.<\/p>\n
Also, the system for putting meshes together is hilariously indirect. It doesn’t just list the verts you need to create the fans. No, it lists everything as edges – as pairs of verts. Then there’s another layer of indirection where it lists edges and tells you if you need to reverse the pair. Then it lists those segments in long chains, with extra data describing the original surface these polygons belong to so you know which way they’re facing. This structure is great if you’re trying to pull the data into memory and use it to directly render crap, but it’s a lot of hassle if you need to translate the data into something a modern engine will accept.<\/p>\n
Anyway, I got it sorted out.<\/p>\n
This shot is taken from roughly the some position as the header image of this post and the previous wireframe image, if you want to compare the original level to the Unity version. The glowing floor is actually supposed to be water, which I have not yet (and probably won't) implement.<\/div>
This shot is taken from roughly the some position as the header image of this post and the previous wireframe image, if you want to compare the original level to the Unity version. The glowing floor is actually supposed to be water, which I have not yet (and probably won't) implement.<\/div><\/p>\n
Also, I finally got path tracing \/ ray tracing to work, but that’s another post.<\/p>\n","protected":false},"excerpt":{"rendered":"
This is a second entry, following the first one, which makes this a series now.\u00a0 If you remember, my son Issac made a level for Garry’s mod that I thought was cool, and I foolishly assumed it would be easy to get it translated to a modern engine. Here’s the original level: It was unreasonably […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-49749","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/49749","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=49749"}],"version-history":[{"count":23,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/49749\/revisions"}],"predecessor-version":[{"id":49772,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/49749\/revisions\/49772"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=49749"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=49749"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=49749"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}