• Create Account

World's Worst Sector Splitter

Posted by benryves, 15 March 2006 · 311 views

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:
1. 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.
2. 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.
3. 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.

What about creating a very small BSP in order to create convex areas on the floor and then tesselate these areas to create triangles?

Of course, tesselation of a concave polygon with holes can be fun too ;)
DOOM does have a BSP tree and supposedly splits sectors into convex polygons for you, but my tests came back with results like the following:

There are big holes in places. My experiments with doing my own BSP partitioning failed quite horribly, which is why I wanted to try a more basic approach.

Of course, I'm still getting >60FPS (it's locking to my refresh rate, so I haven't got a more accurate figure) so performance is no issue. [smile]
An interesting problem, and quite a cool solution! It does generate quite an ugly resultant mesh at times though [sad] Perhaps if you knew that they were all convex, or subtractions of convex shapes from convex shapes, it would be easier to split up. But most sectors aren't.

I'm assuming lines that where edges of sectors meet, the lines are shared? Which is why extra vertices are sometimes generated? (see pictar for an example)

You might be able to save a few triangles and make the resulting output nicer by merging all the lines on the right-hand edge of the inside sector, since they all go in the same direction... But I guess it wouldn't really be worth the effort [smile]

One of the problems here is that I'm using the plain line definitions from the WAD file. For example, a single straight section of wall might be made up of several line definitions with different textures or types (for example, the area around a window).

I could cut down (quite significantly!) the number of triangles produced by optimising the lines first - working out which lines connect to the same vertex and travel in the same direction, then joining them together. This would reduce the number of different Y coordinates, and therefore the number of splits. Most of the worst patches appear in areas where there are an excessive number of splits.
That's awesome! When can we expect DoomMDX
Chex Quest!
PARTNERS