Triangulation

This could be a room in Doom!

Hit the first snag already. While the walls in Doom are ridiculously easy to create - they're just quads - the floors and ceilings of rooms can have many bizarre and arbitrary shapes.

I'm not sure how Doom rendered its floors and ceilings. If you forget a wall the ceiling kind of "spills" out. My guess is they use some scanline tricks.

Anyway, I'm not working on that low a level. All I do is send triangles to the GPU and let it do its magic. So that means I need to triangulate my floors. Which, apparently, is super difficult.

... Chazelle (1991) showed that an arbitrary simple polygon can be triangulated in O(n). However, according to Skiena (1997), "this algorithm is quite hopeless to implement."

Quite hopeless indeed!

So I started at the top of the chain with the hopeless algorithm and then moved my way down to less and less efficient ways until I hit the bottom with the "ear pruning" technique. It basically boils down to "pick a random corner and see if you can cut it off, otherwise pick a new one." One of the online powerpoint presentations I found mockingly called it the "naive solution" before failing to properly explain another method involving trapezoids. :/

Stuff that though! At least it works, check this out:



Oh and one cool thing about the Doom engine: because the floors are all perfectly level it's super easy to map a texture on them!