Wall clipping [was 3D floors]

[Scet]

So far the only successful method of creating floor/polygons in Doom.Net has been making .GWA files with glBSP. However this is far too slow to actually be playable so I'm wondering how other 3D ports do it. Since most ports are C or C++ do they just include glBSP in the code, or is there some technique I'm missing? If they do just incorporate glBSP, I could always wrap it into a DLL, but then that causes a bunch of licensing issues.

Any ideas?

[kristus]

Legacy don't use GL nodes at all.

[andrewj]

glBSP is not that slow, less than 10 seconds for a largish level on my 500MHz machine, and it only has to be done once.

You can avoid licensing issues by simply running glBSP as a separate program. In Unix you have the system() function, I don't know what the equivalent is in Windows.

Another way is to use the GLU tesselate function.

Or you could write your own sector tesselation function. It's tricky because you need to handle sectors that are not contiguous (have separate areas on the map). In fact the BSP algorithm is one of the simplest ways to do it.

Edit: glBSP builds DOOM2.GWA (32 levels) in 17 seconds on my 500Mhz machine.

Edit 2: Legacy was considering using GL Nodes, I believe SmiteMeister was working on it, don't know if he finished it.

[kristus]

I'm not saying that it shouldn't use GL nodes, because it sure as hell would be a good addition. But it is doing 3d floors w/o them, and AFAIK they are pretty damn fast in comparision.

[Quasar]

CreateProcess is the equivalent under Windows. It is not a pretty function.

[andrewj]

Quasar said:

CreateProcess is the equivalent under Windows. It is not a pretty function.

Ah good to know.

Not much of the Windows API could be called pretty (I've just had the joy of learning the GetSaveFileName function :-).

[Graf Zahl]

kristus said:

I'm not saying that it shouldn't use GL nodes, because it sure as hell would be a good addition. But it is doing 3d floors w/o them, and AFAIK they are pretty damn fast in comparision.

Of course it is possible to create polygons without GL nodes. PrBoom can do it as well. But I think we all know the precision issues involved in that...

But regarding GL nodes, I noticed one potential problem: There are lots of maps which depend on the used nodebuilder's quirks and won't work anymore when the nodes are rebuilt. So even with GL nodes you might need to load the original nodes as well so that the engine can use them for collision detection.

[rpeter]

Oops. An example? My pet engine uses only the nodes created by a built-in version of glbsp. I'd like to test such maps.

[Graf Zahl]

Try the crane in Phobos:Anomaly Reborn. I haven't found a single node builder which was able to build working nodes for that. With all there were holes the player could fall into.

[rpeter]

Thanks, I'll check it out, hope it's requirements are not beyond Boom compatibility.

[andrewj]

The crane relies heavily on the self-referencing sector trick. Doom will ignore these lines when rendering flats, but the nodes builder has to create subsectors for those areas, and it's not obvious which seg should be the "main" seg. Ports usually use the first seg to decide what sector the subsector belongs to.

I think ports have to bear some responsibility to handle these tricks, like checking whether segs are on a self-referencing sector and taking some action (doing some analysis of its own). glBSP 2.20 improved the handling of this case, but there's a limit to what a nodes builder can do.

[TheDarkArchon]

rpeter said:

Thanks, I'll check it out, hope it's requirements are not beyond Boom compatibility.

It's an MBF map.

[rpeter]

Bummer. Graf, are there any other wad (Boom compatible) I can test?

[kristus]

That specific map isn't MBF, it's only E1M4 of that wad that is MBF iirc. And even so, it should work great with Eternity.

[Scet]

Thanks guys.

As for glBSP being slow, I meant creating a .GWA for a whole megawad, which can take several minutes on my 2Ghz machine. Plus it hogs the whole CPU.

"CreateProcess is the equivalent under Windows. It is not a pretty function."

Yes the Win32 is ugly. Good thing I'm using C# and .NET, where everything is pretty.

[Graf Zahl]

Ajapted said:

I think ports have to bear some responsibility to handle these tricks, like checking whether segs are on a self-referencing sector and taking some action (doing some analysis of its own). glBSP 2.20 improved the handling of this case, but there's a limit to what a nodes builder can do.

The problem is, you can't do much. It's not that easy to second-guess a mapper's intent and it might as easily backfire as it would help. That's why in GZDoom I preserve the original nodes and use them for all in-game checks. The GL nodes that have to be generated are only used for rendering then.

[Hobbs]

TheDarkArchon said:

It's an MBF map.

Who cares? Most ports considered Boom compat are also MBF compat

[Khojan]

I don't know if it will help, but if you're only interested in creating the polygons for your floors and ceilings I can send you my code which does this. It builds a triangle list for an entire sector. With my rewrite I don't actually use the segs, ssectors, or nodes at all. So it might not be what you want.

When I'm parsing the linedefs and sidedefs I build a collection of lines that make up the edges of the sector. From there my code can build the list of triangles necessary. It works on all the weird sector shapes I've tried so far.

[Quasar]

Yeah; EE and PrBoom both have most if not all MBF features between the two of them.

[Scet]

Khojan said:

I don't know if it will help, but if you're only interested in creating the polygons for your floors and ceilings I can send you my code which does this. It builds a triangle list for an entire sector. With my rewrite I don't actually use the segs, ssectors, or nodes at all. So it might not be what you want.

That's exactly what I'm looking for, please send it to me. Thank you, Khojan.

[Khojan]

No problem. I'll email it to you soon.

[Scet]

Sorry, another question, how are you handling rendering if only working with sectors? I know for the smallish offical doom maps a decent FPS is possible even when rendering the whole level, but for larger PWADs it's not(at least not on my crappy card).

I guess it would be possible to use the blocklist as a quadtree and the lines for clipping. I'm having a lot of problems implementing the BSP and wonder if there's a less complex way.

[Khojan]

I haven't gotten to that part yet. But I'll be doing that completely in my own way too. Each of my sectors has a bounding box I'll use to immediately cull sectors that aren't in the view angle. I'll not draw sectors that are more than a certain distance away, and for other sectors in front of me I'll work on my own alrogithm to determine if they should be visible or not based on where I am. That will all come later. I have lots of other stuff that has to be done first.

[andrewj]

Scet said:

I guess it would be possible to use the blocklist as a quadtree and the lines for clipping. I'm having a lot of problems implementing the BSP and wonder if there's a less complex way.

Well a BSP is very similar to a quadtree, if you understand quadtrees then you can understand BSP trees.

What exactly are you having trouble with?

[Scet]

Well it seems I'm not walking the tree correctly. The subsectors render out-of-order. I usually only get a few sub-sectors out, so the level "appears" as I walk through it. Here's my technique:

1) I start at the players sub-sectors parent node.

2) If the camera position is on the right side, process the right child then the left child. The opposite happens for the left side.

3) If the parent of this node is not null(the root node) the "climb up" into that node.

4) Repeat

There are two functions. The main recursive function called FindNode and the other called Process which checks if a child is a sub-sector or node. If it's a subsector it adds it to the renderer, otherwise it goes down the child node using FindNode.

There are also checks in place to make sure it doesn't process the same node twice.

[andrewj]

You're right, you are not handling the bsp correctly.
The correct algorithm is this:

(a) start at the root node of the bsp tree

(b) check which side of the node the camera is on

(c) first process the child-node which is on the camera side, then process the child-node which is on the other (far) side

(d) when you get to a leaf (a subsector), render it

That's it.

In other words, you always go down the bsp tree. Note the recursion in step (c), it means that you reach subsectors in correct order (e.g. closest first, furthest last).

[Quasar]

Note however that is only the correct order IF you are using a screenspace clipping algorithm like DOOM uses. If you are not, and you are simply going to draw everything to the screen and let it overdraw (which I warn you will be slow), then you should draw back-to-front instead of front-to-back. This means you render the backspaces first, then the frontspaces. Same algorithm, just a different traversal order.

I'm not aware of any modern game engine that uses back-to-front drawing, however, simply because it's really slow.

[Scet]

Thanks Ajapted, I think I have it right now since I can walk through the level with the Z-buffer disabled.

Now the problem is as Quasar said, that rendering every sub-sector is too slow. I do occulsion testing on each sub-sector while going through the BSP, but this process is slow too. Am I supposed to check node or sub-sector visibility while traversing the tree, and what do I do if a node/ssect isn't visible?

[Graf Zahl]

Scet said:

Am I supposed to check node or sub-sector visibility while traversing the tree, and what do I do if a node/ssect isn't visible?

You should do a visibility check for the node's back space. Since the viewpoint is in the front space you can always assume it's visible by default.

And if you are using GL nodes which means that each subsector is closed you can also add a visibility check for each subsector. With normal (incomplete) subsectors this won't work properly though.

[Scet]

That's what I don't understand though, how to do the frustum test on each node/ssect. I'm doing occulsion testing on the GPU right now, which works, but is slow when processing ever sub-sector.



In the end it renders the correct amount, but there's too many ssects being tested. I need a faster way then using the GPU.

Edit: Forgot to mention that I am using GL Nodes.