Ok, I have some triangles now, rather than lines. Copying Benryves' idea from last year, I'm using fog instead of properly lighting the scene.

Piccy time:

(Click to enlarge)

I'm rendering the map twice, once in solid view, once in wireframe (Something I can do with one line of code thanks to the way my engine works), which is why it looks weird.
My method of generating triangles isn't really that optimal, and will probably cause artefacts with large polygons with many edges, but it works for now. Currently I just make a fake triangle fan (It's really a triangle list, but it looks like a triangle fan, you can see some in the screenshot), using the first vertex of the edge list as the fan start point, then just working my way around.

I've half got texture code working - It parses the textures and creates them, but I'm at work just now so I don't have a Quake pak file, which means I don't have the Quake palette handy, so I'll hopefully get that done tonight.

The next thing I'm going to run into is a problem with the way Quake uses OpenGL, and I'm using Direct3D. With OpenGL you can specify texture coordinates seperately from vertex positions, with D3D you can't (easily). That means that I'll have to duplicate some of my vertices to account for texture coordinates. And that's going to be a little fiddly with my current setup.
Still it needs done, and shouldn't be that bad.

Anyway, back to work...