Mommy, can you check if there's a visplane under my bed? Thoughts & research on visplane overflows and preventing them.

[boris]

3 hours ago, zokum said:

The DB2 stuff isn't of much use as it recomputes the subsectors with an interal node build.

That's not the case. The DB2 family doesn't even have an internal node builder, it reads the data right from the WAD. The nodes only get rebuilt (with an external node builder) if one of the lumps required for the mode are missing, or if the map was changed.

[zokum]

Could be I was wrong, but I think @Linguica tried to use it for some research, and it didn't work out very well due to the forced rebuild. They might have changed the code since then, that would be nice.

It probably was done with an external node builder, but it happens behind your back :)

[anotak]

a MAJOR correction: the bsp is traversed breadth-first, not depth-first

 

i really dunno why i thought it was depth-first

 

edit: see below

Edited August 2, 2019 by anotak

[boris]

10 hours ago, zokum said:

Could be I was wrong, but I think @Linguica tried to use it for some research, and it didn't work out very well due to the forced rebuild. They might have changed the code since then, that would be nice.

It probably was done with an external node builder, but it happens behind your back :)

Quite possible that this was the case in early version, but in GZDB-BF it's definitely not the case. I checked both the code and tried it out with the debugger.

[AngryCPPCoder]

On 9/12/2018 at 10:46 PM, anotak said:

a MAJOR correction: the bsp is traversed breadth-first, not depth-first

 

i really dunno why i thought it was depth-first 

 

That is not true, depth first is correct. the traversal goes left and right in tree until you find the player (that is depth) and then you go opposite direction based on your path in stack Link1, Link2.

[anotak]

dammit lol,

 

i initially had the correct thing after looking at the source code, when writing this.

 

then i had a certain person who knows a good deal better than me about doom renderers "correct" me incorrectly and i didn't bother to double check, i just assumed the person knew better than me.

 

whooops. thanks. i double checked the source now. fixed it

[AngryCPPCoder]

Just to clarify things to whoever needs to understand why this is a depth first search that looks like a "breadth first".

The misconception of breadth first comes from visualizing what happens we render the walls closest to player to furthest, you can visualize this as a circle growing around the player giving the illusion of breadth first traversal, but that is not true. That illusion is due to how the data is stored in the BSP tree and how we visualize it. Most of the BSP data is used splitting the map and only leaf nodes are the ones we really care about or use in rendering.

* How BSP is traversed by mixing Pre and Post order tree traversal or as I see it a modified binary search which are all a depth first traversal.

* Breadth first algorithm requires a queue to keep tack of the tree breadth, which is not there in BSP traversal.

 

 

[andrewj]

18 hours ago, AngryCPPCoder said:

 

That is not true, depth first is correct. the traversal goes left and right in tree until you find the player (that is depth) and then you go opposite direction based on your path in stack Link1, Link2.

I have read those two articles and I think some of the things you say are not really right or accurate.

 

Firstly, the renderer does not actually care what subsector the player (more precisely: the camera) is in -- it does not need to find that subsector in order to render a scene.  Yes the BSP tree is used to find subsectors for things, but that is mainly for the physics (to find what sector player is in to check heights when moving, etc).

 

Secondly I don't think the code comments about "recursively divide the front space" are either misleading or wrong.  One important point of the BSP for rendering is about being able to quickly discard big chunks of the map which are off-screen or behind walls -- via the R_CheckBBox call in R_Render.  If you nerf R_CheckBBox, make it always return true, then R_Render will visit every single subsector in the map, leading to a significant slowdown in rendering.

 

Sorry if that's not very constructive, I just think that you need someone with more experience with BSP rendering to proofread those articles and help clear up some of the rough edges.

[AngryCPPCoder]

8 hours ago, andrewj said:

I have read those two articles and I think some of the things you say are not really right or accurate.

 

Firstly, the renderer does not actually care what subsector the player (more precisely: the camera) is in -- it does not need to find that subsector in order to render a scene.  Yes the BSP tree is used to find subsectors for things, but that is mainly for the physics (to find what sector player is in to check heights when moving, etc).

 

Secondly I don't think the code comments about "recursively divide the front space" are either misleading or wrong.  One important point of the BSP for rendering is about being able to quickly discard big chunks of the map which are off-screen or behind walls -- via the R_CheckBBox call in R_Render.  If you nerf R_CheckBBox, make it always return true, then R_Render will visit every single subsector in the map, leading to a significant slowdown in rendering.

 

Sorry if that's not very constructive, I just think that you need someone with more experience with BSP rendering to proofread those articles and help clear up some of the rough edges.

First, I'm happy to discuss and correct my understanding so don't worry about that point.

 

1- About the first the BSP traversal does use the player coordinates as a vector, so the player X, Y does make a difference in your traversal, (also the goal of the BSP traversal is to get to the sector closest to the player) Please correct me if you think this is not true.

 

2-Yes  the code comment is misleading, let have a look at this code

side = R_PointOnSide (viewx, viewy, bsp); 
// Recursively divide front space. (This comment is misleading and not true) 
R_RenderBSPNode (bsp->children[side]); 

 

if Side is true or false (front or back) you will still execute the R_RenderBSPNode but passing a different side, so you will call R_RenderBSPNode with sometimes Front and sometimes the back. This makes the above comment misleading which indicated front only space.

 

If you think something I miss understood, please help me clarify my understanding and I will credit you for the correction.