• Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

The unholy trinity - BSPs, Culling and Occlusion

Sign in to follow this  


I figured out how to use the BSP data, but unfortunately that only gave me the rendering order, it doesn't actually speed anything up.

For every sub-sector I come across in the tree I'm supposed to test its bounding box against the frustum and then "clip" it and check if the screen is "full". If the screen is "full" the BSP reader stops(this is the speed part).

My frustum culling stuff isn't the best, but it works 99% of the time(the other 1% it draws nothing...). The problem now is testing wether the screen is "full". After looking at the source to several ports it seems the idea is to test the angles between the camera position and the line vertices and see if they're in the field of view, then write to some kind of 1D buffer.

Red is the camera and frustum, 1 and 2 are sub-sectors, and the green lines are the angles to test.

Anyone have any idea how to do this? I've been trying for a week to implement my own as well as converting the code from other ports, but have yet to find one that works. A massive rate++ to anyone with the solution(or some cookies if I've already rated you).

Not to disappoint in the screenshot department, here's a nice high-res one.
(warning the whole thing is about 1MB in size)

Sign in to follow this  


Recommended Comments

I'm a bit confused as to what you need to do there.

So, you have the 2D camera position, 2D vertices and an angle for the camera.

What I'd do is create a 1D buffer of bools. Let's assuming we're using degrees for the sake of simplicity; it's 360 elements long. It's a circular buffer, imagine that it's looped around your camera - so element 0 is North, element 90 is East and so on.

At the start of the frame, I'd clear it down to all false. Let's say my FOV is 90°. I'd set a counter to 90.

Now, I work out which walls I'm drawing. As I draw each one, I calculate the angle to the end vertices from the current camera location (Math.Atan2()). Let's say that we have a wall and we know it goes from 30° to 60° (where 0° points North). We now clip this to our total FOV (assume I'm looking North, my FOV ranges from -45° to 44°) so the range is 30° to 44°. I now go through my circular buffer from elements from 30 to 44 (inclusive). If an element is false, I set it to true then decrement my counter (which had been preset to 90 earlier).

Once the counter has become 0, or underflowed, I know an entire screen has been filled.

For pixel-perfect accuracy, the size of the buffer would have to be (360 / FOV) * ScreenWidth. You could easily reduce this further by only making it ScreenWidth wide and subtracting the left FOV boundary (-45 in the earlier example) from the indicies we use to check if the column had been filled before.

Either I've just
  1. stated the obvious; or
  2. missed the point entirely.
But whatever.

Nice screenshot.

Share this comment

Link to comment
Well that's actually what I've been trying to do, except with an incrementing counter, but that doesn't matter.

I got it kind of working this morning, it turned out my frustum and BSP code was completely incorrect. It still missed a lot of lines though.

I'm going to forget about this for now though and go implement some gameplay, I'll deal with it later. Thanks for trying though.

Share this comment

Link to comment

regarding the bsp-tree & frustum-culling stuff, I think I have found a resource that may help answer some/all of your questions.

at this link: http://www.hlnum.org/english/doc/gfx/gfx_index.html

there are links to a lot of great stuff there, much dealing with concepts you're working on now, but the one you want is called

"Optimizing BSP Tree Traversal" ... it's the third link down on the page.

the author's name is Hin Jang, and he includes a great references list at the bottom.

Please let me know if it helps...
(email: phaedrus99@gmail.com)

BTW, I love what you're doing here in your journal, it is a great help to others in understanding issues they might face when learning graphics programming, especially those interested in doom & 3d game-engine design.

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement