Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
Sign in to follow this  
sirjuddington

BSP and determining subsector visibility

Recommended Posts

Ok, I've been battling with this for a while and have been getting nowhere :P

Basically, how does one determine what subsectors are visible and which aren't by using the BSP tree? Everything I've found so far has either been utterly confusing or not what I wanted (building the BSP I don't care about).

The reason I'm asking is because I've been working on SLADE a fair bit lately and have basic 3d editing working. (here's a screenie ;) And yes, the hilighting effect can be disabled if desired).

Problem is, large maps go horribly slow because not only is the entire map being drawn every frame, but every time it determines what the camera is pointing at it has to scan through all sectors in the entire level (plus a lot of other stuff). It'd be much quicker if I could just ignore subsectors that aren't visible.

Anyway, any help would be greatly appreciated ;)

Share this post


Link to post

Well, I can help, but I hope im signing my own death warrant :P

The BSP tree doesnt help you determining visiblity. The BSP tree is only a system to quickly determine the order of subsectors (and thus also the order of walls since subsectors are convex) front-to-back or back-to-front from a certain point of view (your position).

I recommend you walk the BSP tree to find subsectors in front-to-back order. So if you're on the front side of a split line, do that part of the tree first, and the other part later. Now, the way I do it; For every subsector you encounter, get the segs (wall pieces). When the seg is part of a single-sided line (meaning there cant be anything behind it, thus you cant see through), project the seg on a visibility buffer (just a temporary array in memory which represents all angles within your FOV, the resolution of this buffer only determines the visibility accuracy you will have near the edges of walls). You get the angle from your point of view for the start of the seg and for the end of the seg and "render" this part on the visiblity buffer as "blocked". Now for every subsector you encounter, implend a check which checks if any of this subsector's segs would be overlapping "non-blocked" parts of your visibility buffer, which means it will be visible. If all parts on the visiblity buffer where the segs are projected are marked as "blocked" it means that previous (closer) walls occlude them, thus they cannot be seen and there is no need to draw them.

In my sources I call the visibility buffer a "clipbuffer" (it clips what you dont need to see) and you can find it in clip.cpp of the Doom Builder source. Before you begin your BSP walk, do a SetClipbuffer(1); to block everything and use WriteClipRange() to open up parts of your FOV (there is no need to see behind you). When looking up or down for a specific amount, just use SetClipbuffer(0); only to allow viewing behind you as well. (otherwise you would see only half of the floor/ceiling) My clipbuffer represents an entire circle of all angles, regardless of FOV. Therefor you can just calculate the angle from the seg vertices to your position and use that as angle in WriteClipRange() and TestClipRange().

Share this post


Link to post

The BSP tree doesn't tell you directly what is visible and what isn't.

What it does give you is the proper rendering order. You traverse the whole tree, but at each Node you decide which way to go (left or right) based on which side of the node-line the camera is on.

This means that subsectors closest to the camera will be visited before ones further away. That's important.

To actually get the speed benefit, when you render a "blocked" wall (1-sided or closed-door), you remember the horizontal range in some structure. During the BSP tree traversal you check whether the BBOX of the current node is behind a blocked area: if it is then skip it.

That's basically it. I assume you are already checking the node BBOXes against the camera frustum.

Share this post


Link to post

Ah, thanks for the responses. I think I get it now. Of course that doesn't mean anything until I actually try to implement it :P

Anyway it's a bit too late to start now (3:31am), so I'll see how I go tomorrow ;)

Share this post


Link to post

Is it just me, or do BSPs seem horribly complicated? Carmack said back when he released the Doom source that you wouldn't even need the BSP, just rendering the entire level should be fast enough. And that was in the days of a Voodoo1.

Share this post


Link to post

Fast enough, but not the fastest way. He probably meant 35 FPS with modern hardware for that time.

Share this post


Link to post

nightice said:
Is it just me, or do BSPs seem horribly complicated?


That depends. A BSP is not that complex once you understand how it works (not that it means creating a proper one is trivial though!)

Carmack said back when he released the Doom source that you wouldn't even need the BSP, just rendering the entire level should be fast enough. And that was in the days of a Voodoo1.



If you take your average original Doom level that is true. But beware if you get some complex modern map. It won't be fun to play at all.

Share this post


Link to post

Speaking of which, has anyone tried to do rendering in Doom using quad trees? Presumably it'd be slower than BSP, but if I'm not mistaken it would scale as well for large levels.

The obvious benefit would be the possibility to have dynamic geometry.

Share this post


Link to post

Idea: For the sector the player is currently in, find all sectors that the REJECT says it can see, and render current sector and ones specified by the reject. I dunno if it would work, just a thought.

Share this post


Link to post
nightice said:

Idea: For the sector the player is currently in, find all sectors that the REJECT says it can see, and render current sector and ones specified by the reject. I dunno if it would work, just a thought.

It would work if the REJECT data was guaranteed to be well constructed. However often the REJECT is not built at all, or when it is then it uses a lousy algorithm like "distance between sectors <= 1024".

The concept is called Potential Visible Set, and the Vavoom engine uses this method, though it can take a while to generate the required data.

Fredrik said
(quadtree stuff)

It's an interesting idea, I think it would be slower than BSP, you would also need to do some sorting to get proper rendering (that's another nice thing the BSP gives you). If I had a completely free week or two, I'd try it out :)

EDIT: a very significant problem remains: polygonising (triangulating) sectors. Doing it robustly could be expensive.

Share this post


Link to post

Hmm, ok I've got the viewbuffer working fine, (it doesn't draw anything behind the view). Now I can't seem to get the rest working properly. I'm pretty sure I'm not walking the bsp tree correctly. Is there anything wrong with this function?

void walk_bsp_tree(unsigned short node)
{
	if (node & CHILD_IS_SUBSEC)
	{
		short subsect = node & ~CHILD_IS_SUBSEC;

		if (subsect_is_visible(subsect))
			sects[subsect]->visible = true;

		return;
	}

	if (view_buffer_full())
		return;

	int x1 = gl_nodes[node].x;
	int y1 = gl_nodes[node].y;
	int x2 = x1 + gl_nodes[node].dx;
	int y2 = y1 + gl_nodes[node].dy;

	rect_t part(x1, y1, x2, y2);

	if (determine_line_side(part, camera.position.x / scale, camera.position.y / scale))
	{
		walk_bsp_tree(gl_nodes[node].right_child);
		walk_bsp_tree(gl_nodes[node].left_child);
	}
	else
	{
		walk_bsp_tree(gl_nodes[node].left_child);
		walk_bsp_tree(gl_nodes[node].right_child);
	}
}
As far as I can tell that should work, but it doesn't seem to be visiting subsectors in the right order...

Share this post


Link to post
Ajapted said:

EDIT: a very significant problem remains: polygonising (triangulating) sectors. Doing it robustly could be expensive.

You could pre-compute the level and just re-polygonize the affected sectors when a vertex is moved.

Share this post


Link to post
SlayeR said:

Is there anything wrong with this function?

This first thing that looks wrong to me is the "/ scale" stuff with the camera coordinates.

The second thing is, you are not processing the subsectors here. (Unless subsect_is_visible() actually updates the view_buffer, which would be bad since the function looks like a mere query). Instead of setting a flag, call the method to draw the subsector (and as a by-product update the view_buffer).

Lastly, you're not testing the node's bbox. I'm guessing view_buffer_full() checks if the entire screen has been filled. This may be sufficient (I'm not sure), but it's not optimal.

Fredrik wrote:
You could pre-compute the level ...

That's what I was meant. Doom's geometry allows concavities, holes and islands, and this makes it difficult to process - google around for "triangulation". (Actually I've got an idea on how do to it, now all I need is some time to try it :)

Share this post


Link to post
Ajapted said:

This first thing that looks wrong to me is the "/ scale" stuff with the camera coordinates.

That's actually needed. The camera position is scaled and the partition line isn't (so I need to get them both to the same scale).


The second thing is, you are not processing the subsectors here. (Unless subsect_is_visible() actually updates the view_buffer, which would be bad since the function looks like a mere query). Instead of setting a flag, call the method to draw the subsector (and as a by-product update the view_buffer).

Yeah subsect_is_visible() updates the view_buffer :P I should probably change that eventually. For now though I just want to get it working :/


Lastly, you're not testing the node's bbox. I'm guessing view_buffer_full() checks if the entire screen has been filled. This may be sufficient (I'm not sure), but it's not optimal.

I know, I didn't see the need to since view_buffer_full() does indeed check if the entire buffer is full. So yeah it's not optimal but it should at least work.

Still can't figure this out... :/ Oh well, in the meantime I've added things to 3d mode ;)

Share this post


Link to post
Ajapted said:

That's what I was meant. Doom's geometry allows concavities, holes and islands, and this makes it difficult to process - google around for "triangulation". (Actually I've got an idea on how do to it, now all I need is some time to try it :)

Well, all nodes builders generate the convex subsectors (which of course are trivial to triangulate), can't you just use that code?

Share this post


Link to post
Fredrik said:

Well, all nodes builders generate the convex subsectors (which of course are trivial to triangulate), can't you just use that code?

That's what I want to try. It ultimately depends on how fast it is whether this way is viable. And I fear all the map-tricks will be even harder to emulate with this method.

Share this post


Link to post

Hah, finally got it working ok. It wasn't the walk_bsp_tree() function at all, but a few problems with the angle computation stuff. Now all I need to do is finish up line drawing and zdoom support and it should be ready for the next release ;)

Share this post


Link to post

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
Sign in to follow this  
×