Wall clipping [was 3D floors]

[Graf Zahl]

Scet said:

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.

Don't use the GPU for it. This is something that's much easier to do with regular C-Code.
Basically it means that for each seg you render you add it to a clipping list that keeps track of all parts of the viewing frustum that are obstructed by geometry that has already been drawn. When rendering something you check whether the the subsector/node/seg or whatever is being obstructed by something lying in front of it. If that is the case such an object should be skipped entirely.
The GPU's occlusion test is really not suitable for geometry clipping in such an early stage. The basic rule should be to pass as little data as possible to the GPU.
Of course the best way to understand how this is supposed to work is to look at an actual implementation (i.e. one of the existing GL ports.)

[andrewj]

For each node there is a bounding box for everything inside the node (all the subsectors). In DOOM it's stored in the parent node.

You get the true benefit of using the BSP by testing the node bounding box for visibility (so you don't need to process the whole sub-tree). You compute the angle range that the bounding box covers, and test that against an "occlusion map".

The occlusion map is initially all clear. Every time you draw a one-sided seg, you set the angle range of the seg in the map. Closed doors also count.

For EDGE I use a 4096 element bit-map for this (each bit represents an angle). Other methods are possible too, e.g. using a list of angles. which gives better accuracy but is more complicated to do it efficiently.

[Graf Zahl]

Ajapted said:

For EDGE I use a 4096 element bit-map for this (each bit represents an angle). Other methods are possible too, e.g. using a list of angles. which gives better accuracy but is more complicated to do it efficiently.

When I was doing precision tests I found that anything that loses precision can create visual artifacts. I think the best approach is to use a linked list of clipping ranges with full angle precision.

[andrewj]

Graf Zahl said:

When I was doing precision tests I found that anything that loses precision can create visual artifacts. I think the best approach is to use a linked list of clipping ranges with full angle precision.

EDGE has a small problem of very thin segs (on the screen) disappearing, which is usually not very noticeable. I think using the bit-map to simply clip subsector bboxes (and not individual segs) would work better and artifacts would be much rarer.

The linked list of ranges seems like it would get "clogged" on complex maps (like AV). The number of entries could reach into hundreds, and then every test and set operation becomes a hundred times slower. Do you optimise this in any way?

[Graf Zahl]

Ajapted said:

EDGE has a small problem of very thin segs (on the screen) disappearing, which is usually not very noticeable.

I had the same problem. Actually there are two things that can be responsible:

1) a clipper with insufficient precision
2) Use of Doom's original R_PointToAngle function which is horrendously imprecise.

The linked list of ranges seems like it would get "clogged" on complex maps (like AV). The number of entries could reach into hundreds, and then every test and set operation becomes a hundred times slower. Do you optimise this in any way?

Overlapping entries in the clipper get merged but aside from that, no. I haven't experienced noticable slowdowns from this code. For example, the code that has to check two-sided lines whether they obstruct the view needs a lot more time. The time for the clipper itself is completely irrelevant compared to what is needed to process a seg.

I think checking a bit map as you do is far slower. If I understand it correctly you have to check all bits in the affected range. I only have to check each seg against the already existing entries - and due to the merging there are very rarely more than 10-20. You'd need some rather exreme geometry to push it to 100.

[DaniJ]

I just thought I'd chime in to say that the method Graf mentions is pretty similar to how Doomsday's clipper works.

[andrewj]

Graf Zahl said:

For example, the code that has to check two-sided lines whether they obstruct the view needs a lot more time.

I never bothered checking two-sided lines. Apart from being at the bottom of a cliff, is there much benefit it doing that?

I think checking a bit map as you do is far slower. If I understand it correctly you have to check all bits in the affected range. I only have to check each seg against the already existing entries - and due to the merging there are very rarely more than 10-20. You'd need some rather exreme geometry to push it to 100.

With the bitmap you can check 32 bits at a time, so it should be comparable in speed to the linked list.

But the linked list sounds like the way to go.

[rpeter]

I'm not familiar with current GZDoom but the very first release borrowed the clipper class from ZDoomGL 0.7x by Timmy and it was based on Doomsday's code.

As for visibily checking bounding boxes are super, they are also pretty good for dynlight checking. I even build bounding boxes for walls for that (well, one unit thick walls, that is).

[andrewj]

rpeter said:

they are also pretty good for dynlight checking. I even build bounding boxes for walls for that (well, one unit thick walls, that is).

Do you mean finding the dynamic light objects, or are you talking about shadowing (limiting the geometry that each dynamic light is applied to) ?

[Graf Zahl]

rpeter said:
I'm not familiar with current GZDoom but the very first release borrowed the clipper class from ZDoomGL 0.7x by Timmy and it was based on Doomsday's code.

Yes, I am still using Timmie's code. Although I had written my own clipper working with the same principle it had some design problems that made using it a little awkward so I switched it.

As for visibily checking bounding boxes are super, they are also pretty good for dynlight checking. I even build bounding boxes for walls for that (well, one unit thick walls, that is).

For walls distance calculations are normally more efficient. Remember, if you compare the square of the distance to the wall you don't even need a square root for that. The time spent here is mostly irrelevant anyway.

[Graf Zahl]

Ajapted said:
I never bothered checking two-sided lines. Apart from being at the bottom of a cliff, is there much benefit it doing that?

What about closed doors? I don't mean cliffs or stuff like that but sector boundaries you can't see through.

[andrewj]

Graf Zahl said:

What about closed doors?

Of course you can treat closed doors like one-sided lines for the purposes of visibility culling (seemed so obvious that I didn't need to say it explicity).

[Graf Zahl]

... and the code to test this along with other cases (closed lifts) requires more processing time than the clipper itself - but it only becomes noticable on large open levels.

[entryway]

How can I turn on the fps counter in edge?

[andrewj]

entryway said:

How can I turn on the fps counter in edge?

Use the IDINFO cheat.

Graf Zahl said:

and the code to test this along with other cases (closed lifts) requires more processing time than the clipper itself - but it only becomes noticable on large open levels

Unless you mark linedefs as vis-blocking in the physics code.

[Graf Zahl]

Ajapted said:

Unless you mark linedefs as vis-blocking in the physics code.

Which isn't that easy with Boom's sector transfer special.

[andrewj]

Graf Zahl said:

Which isn't that easy with Boom's sector transfer special.

Now you've lost me.... type 242??

BTW, how do you go with polyobjects and visibility checking?

[Graf Zahl]

Ajapted said:
Now you've lost me.... type 242??

Yes. When you can change the camera object at any time precalculated information can become worthless rather quickly.

BTW, how do you go with polyobjects and visibility checking?

Polyobject segs are passed to the clipper as part of the subsector they are in so there isn't any special treatment for them.

[rpeter]

Ajapted said:

Do you mean finding the dynamic light objects, or are you talking about shadowing (limiting the geometry that each dynamic light is applied to) ?

I'm using the bounding boxes to test whether a light corona touches a given wall or flat.

Graf Zahl said:

For walls distance calculations are normally more efficient. Remember, if you compare the square of the distance to the wall you don't even need a square root for that. The time spent here is mostly irrelevant anyway.

I do the bounding box check after the standard projectpointonplane check, which works with infinit planes, so it gives close distances even when the actual wall is miles away from the light source, but its plane is not. Bounding box check shaves off these cases. With walls the gain is not too much, but with flats I found it a must.

Legacy also uses bounding box checks for dynlights, but I found it faulty, lights just simply disappear from certain angles.

[Scet]

Thanks guys, I understand how it all works I just have to come up with a working implementation. I can get over 100 FPS though in the normal Doom WADs though, so I'm going to focus more on gameplay for now. Hopefully I'll have deathmatch in by January.

[DaniJ]

I'm using the bounding boxes to test whether a light corona touches a given wall or flat.

Given the nature of coronas, what use is there in checking for intersection with world geometry? How are you rendering them?

[rpeter]

My bad english. I meant the dynamic light radius of light sources.
I render coronas (halos) and dynamic lights on walls and flats as other ports do. I don't use models, sprites are unaffected by lights of other lightsources. I don't think I could realistically light an imp with a baron's projectile passing in front of it.