Subsectors

I have realized that theoretically, a subsector should be able to intersect 2 different sectors, as long as it remains a convex shape and contains exactly 2 segs located on opposite sides of the same linedef, which would be like "splitting" the subsector in half (if the subsector's shape could be visualized). This shouldn't cause any unwanted view occlusion and Doom's renderer should be able to properly render a map with these subsectors. I haven't seen this "trick" mentioned on the wiki, which made me think that I invented something new that could possibly help to generate more balanced BSP trees and/or with less subsectors, while being vanilla compatible.

So my question is: Do subsectors need to correspond to sectors for some implementation-dependent reason other than to pre-emptively ensure proper functioning of the basic BSP-traversing algorithm described on the wiki?

My simple test map, with SEGS/SSECTORS/NODES I manually created via Hex-editing (!), bombed out all ports I've tested the map with. PrBoom-plus once gave me an error message along the lines of "Subsector N doesn't correspond to any sector!". This is what led me to putting this question here.

I have found in the meantime that there were other problems with the BSP lumps I've created - I was also testing how the renderer would handle if multiple nodes referenced the same subsector, and came to a conclusion that not well at all. In other words, the map/tree I made is useless, don't even bother with wanting to see it.

I'd like to help (since I have some experience with hex editing level structures, ahem) but I really need more information, preferably with pictures, to get an idea of what you are suggesting.

I'll try to answer your questions though.

scifista42 said:

Do subsectors need to correspond to sectors for some implementation-dependent reason

Every subsector needs to end up corresponding to a sector, yes, but it's not as straightforward as that (it never is...). Remember that in the WAD file, each subsector is just a list of segs. In the engine, however, when the level is being loaded, there is a function P_GroupLines() where it assigns to each subsector a corresponding sector, based on the first seg in the list.

for (i=0 ; i<numsubsectors ; i++, ss++)
    {
	seg = &segs[ss->firstline];
	ss->sector = seg->sidedef->sector;
    }

(Remember that each seg references a linedef, and the linedef references a sidedef, and the sidedef references a sector). This means that if you're willing to hack the segs, you can almost arbitrarily make any subsector correspond to any sector, by inserting a fake 0-length seg at the start of the list of segs for that subsector, or what have you. I actually did this in the linguortal WADs, because Things are rendered based on what sector they are in, not what subsector; so by making a fake first seg in a linguortal'd subsector I could fool the engine into thinking that the Things in that sector still ought to be visible.

scifista42 said:

I was also testing how the renderer would handle if multiple nodes referenced the same subsector

This is also fine, so long as you don't accidentally set up a loop. Again, this was something I did in my linguortal tests. If multiple nodes point to the same subsector, then the first one reached will draw the subsector's segs as normal, and when the other nodes are reached, they will try and draw the same subsector's segs but instantly give up and move on because that part of the screen was already drawn.

Imagine that this is a part of a Doom map, and these 5 lines are 5 double-sided linedefs on the boundary of 2 different sectors (each with a different floor/ceiling height, brightness, etc):



Now imagine that this is the visualization of subsectors in this part of the map:



You may be thinking: "WTF, how could subsectors cross those linedefs, that can't work!"

I'm telling you it can work - as long as each such subsector contains exactly one such linedef, and its respective 2 segs on each side of the linedef - and no other segs at all.

When the engine will traverse the tree, it will only draw the one seg which is oriented towards the player, anyway. So there shouldn't be problems. Right?

I hope the basic idea is clear now.

I can't say for sure that something like that couldn't work, but I don't think it would.

Each subsector has exactly one sector associated with it, with one floor plane and one ceiling plane. It draws any visible segs and in the right circumstances marks the area extending above / below them as belonging to that plane. In your suggestion, the subsector would need to have *two* possible floor and ceiling planes, depending on which side of it was being drawn, and there's no way the engine would know how to do that.

Subsector shapes are formed by NODES and then by SEGS. Without clipping by SEGS the subsector just really extends into infinity.

Segs are also used when drawing the floor and such also along with walls.

However, "breaking" a map by making subsectors non-convex can cause some issues with parts of the code and other things making the assumption that subsectors are always convex (possible 3D renderers and bot code which uses nodes). Doom has a R_PointInSubSector and some other ports (such as ReMooD and Doom Legacy) have a "R_PointInSubSector2" which checks segs also to make sure that the point does not lie outside of the map whereas for the one in Doom the subsectors extend into infinity since the subsector of a specific point is based on the nodes.

You can do what you want, however it will require special NODES, SEGS, and SUBSECTORS handling.

Subsectors cannot span multiple sectors, because subsectors are implicitly bounded by partition lines and each two-sided linedef *must* become a partition line (or be situated on a colinear one) otherwise that boundary will not be rendered properly.

There is no useful "trick" here.

GhostlyDeath said:

However, "breaking" a map by making subsectors non-convex....

Note that with vanilla nodes subsectors can be disjoint (two separate areas) and hence not convex -- that is pretty much the raison d'etre for GLBSP.

Linguica said:

In the engine, however, when the level is being loaded, there is a function P_GroupLines() where it assigns to each subsector a corresponding sector, based on the first seg in the list.

This is what kills my idea. It's merely an optimization, as I expected, but it breaks it. I thought that when drawing a seg, the engine would find this one seg's linedef, then this one linedef's respective sidedef, then this one sidedef's respective sector, and draw this sector in front of the seg. If it worked like this, my idea would work. But it seems that the engine is optimized to already remember a sector for each subsector (which it technically wouldn't have to), probably to speed up rendering, and that's the only reason why my subsector idea won't work. Right?

Linguica said:

This is also fine, so long as you don't accidentally set up a loop. Again, this was something I did in my linguortal tests. If multiple nodes point to the same subsector, then the first one reached will draw the subsector's segs as normal, and when the other nodes are reached, they will try and draw the same subsector's segs but instantly give up and move on because that part of the screen was already drawn.

This, however, sounds very positive to me, even if the previous idea couldn't work. I was thinking about it overnight, scrapped several more ideas as unreliable to work, but one idea makes me believe it should work, and it would finally allow to make a BSP builder which doesn't need to split any segs during the partitioning process. I will make a new simple example map to test it out.

GhostlyDeath said:

Subsector shapes are formed by NODES and then by SEGS. Without clipping by SEGS the subsector just really extends into infinity.

andrewj said:

Subsectors cannot span multiple sectors, because subsectors are implicitly bounded by partition lines and each two-sided linedef *must* become a partition line (or be situated on a colinear one) otherwise that boundary will not be rendered properly.

Note that the partition lines bounding a subsector can be implicit, which is what I expected from my special subsectors - to be fully bounded by implicit lines at the circumference, and only contain 2 segs in its own middle area.

I'm still not sure what the point of that whole thing would be. It seems to me that if you have two sectors, covered by a number of subsectors, and you fool the engine into believing all these subsectors belong to one of the sectors but not the other, the effect you'll get in rendering will be, at best, identical to what you'd get if you had only one sector.

I didn't want subsectors to belong to any sector at all. Only their respective segs to belong to 2 different sectors. The effect would be that it would allow for creating BSP trees with slightly lesser depth and number of subsectors.