World's Worst Sector Splitter
Thursday, 16th March 2006
As with many programming problems, a potential solution presents itself at about 2AM when you suddenly awake and hunt paper and pencil before the brilliant idea vanishes into the groggy murk that is forgetfulness.
In this instance, a solution did present itself, but it's far from 'brilliant'.
I was pondering DOOM's floors, and how to split them up. I came up with a simple, optimal solution - optimal, provided that the sector I was splitting into triangles was a rectangle with sides perfectly aligned the the (x,y) axes. Happily, DOOM follows that pattern fairly often.
Here we have the typical sector. It's sector number one from E1M1, the ground that surrounds the acid pool outside the window. As you can see, it's not entirely convex, and has a hole in the middle. I have access to the lines and points that surround the sector.
My technique runs like this:
- Split the sector up into horizontal spans. To do this, I cycle through every single line in the sector, and for every different Y coordinate I split the sector.
- For each individual span, go through each line in the sector. If it's completely outside the span, discard it. If it's partially outside (no line will ever have a point half-way inside the span), clip it to the upper/lower Y bounds.
- Sort these lines from left to right, then group into pairs. Each pair, when combined with the top and bottom Y boundary, forms a trapezium. Split this into two triangles - there's a part of your floor.
This method is fairly simple, and appears to work pretty well:
Note the large magenta shape at the top (maze in E1M2). That's a single sector!
The image is less pretty if I dump out an image showing the triangles generated:
Hopefully that makes my method slightly clearer.
For some areas, it does pretty well. In others (sectors not perfectly aligned to the (x,y) axes) it generates an absolutely horrible mess of triangles.
Grouping walls by texture and generating a new vertex buffer for each texture group worked pretty well, so I've done the same for floors.
The first floor test looked pretty good (minus texture coordinates):
...so I fixed it up a bit, and flipped the vertex order to support ceilings as well.
One problem I had been worried about had reared it's ugly head, however - hairline cracks between triangles, showing the lovely bright blue through the dark and dismal UAC facility. It was trivial to fix, however; replace the floating-point linear interpolation (to clip lines to the single horizontal span in the floor splitting code) with the integer-based method. This got rid of all the rounding errors, and the cracks were gone.
The floor splitting code might inefficient, but it is simple - even then, however, it does fail on certain segments resulting in slightly-larger-than-hairline cracks on certain levels.
I'm not quite sure why that's happening. I have a hunch that in certain cases there is an extra line when breaking up sectors into horizontal spans and you end up with an odd number of dividing lines. In some cases, this extra line is at the end - and it is ignored safely. If it's at the beginning, though, everything is shunted along one and the whole sector span is drawn incorrectly.
Also, (and this can be verifed), some sector floors/ceilings end up being drawn back-to-front, and fall prey to the backface culling. Ducking below the surface of the floor, you can clearly see the missing floor deciding to be a ceiling.
One potential improvement would be to split the floor twice - once in horizontal spans, once in vertical spans - and use the one that produces the least triangles.
The texturing issues from last post were fixed with a variety of code changes - some sector-to-sector wall segments were being drawn upside down (the code now flips the heights around so they're in the correct order); the light level of a sector's wall is calculated by the brightest between it and any adjacent sector; lower texture pegging fixed to align correctly.