Sign in to follow this  

PVS calculation for 2d map

This topic is 4095 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, Im working on a simple 3d game and Im trying to figure out a good way to create a pre-calculated PVS map. The world map is a 2d array each element represents a "block" (with a fixed size 64x64x64). I have tried two approaches, 1) I go through the 2d map casting a ray from each corner of the current block to every other solid blocks courners. This method worked but very slow and I want to collect information on none solid blocks for ambient lightning on movie objects. 2) I go through the 2d map and for every element i create two cones (two half circles actualy) and go through the 2d map again checking if the block is inside the cone and then if the block is solid. If the block is solid a i need to split up the current cone into two too narrow the field of view. I haven't finished the second method because half way in I thought of a case where my teori didn't work. If a block is 64x64x64 then blocks visible from the center of the current block is different from another poin in the block (for isntance the edges), this can be fixed (well not fixed but a better approximation) by doing a "cone sweep test" for all 4 corners and one form the center but I'm afraid that will take too long. Both those two approaches seems to complicated for a simple 2d map to me, I think I'm making it harder for myself then it really is. Does anyone have a better method or an idea for a method ?

Share this post


Link to post
Share on other sites
Hmm, well first question is do you need precalculated visibility? Can you get away with a simple brute force dynamic approach? If you have a fixed camera angle (for example, isometric starcraft\diablo style) you can just do a simple bounds check on a uniform (or even non uniform) grid of map cells.

~Graham

Share this post


Link to post
Share on other sites
Sorry I wasn't clear enough, the game is a third person shooter (like Wolfenstein 3D, no raycaster though) so the camera view is changing (it is free moving camera in all direction not like wolfenstein where it fixed in one axis).

Also I want to use the result of the PVS calculation to make it easier to add ambient light not a block by just going through every visible block from a light source and just add the intensity.

Share this post


Link to post
Share on other sites
Ah ok, so the brute force method would not suffice for what you want to accomplish. It sounds like PVS is the way to go, though either way the solution will take a decent amount of time. However, you are precalculating this stuff anyways, so the added time will usually result in better runtime results and efficient culling.

~Graham

Share this post


Link to post
Share on other sites
Well, I do not know of (though I'm sure there a bunch) of any 2D PVS calculation algorithm, as I have only used the traditional ray-based approach with a graph flood-fill to check for leaks. If your maps are anything remotely "funky", even for a single level, you'll want the traditional approach. You could maybe hack something if your roof is ALWAYS the same height from the floor and doors are just an open space between the floor and roof (no edging) - and no windows or crazy geometry with holes - it would maybe work.

http://www.cs.virginia.edu/~luebke/publications/portals.html

http://www.tml.tkk.fi/Opinnot/Tik-111.500/2003/paperit/MikkoLaakso.pdf#search=%22calculating%20pvs%202d%20map%22

http://www.crystalspace3d.org/tikiwiki/tiki-index.php?page=PVS

Hopefully that helps ya, unfortunately I cannot release any code to you under NDA or I would definitely do that.

Cheers!

~Graham

[Edited by - gwihlidal on September 26, 2006 3:28:07 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
cast a ray along the left side of your view frustum, by 'walking' along this ray starting at the camera, see what gridlines it intersects till it finally hits a solid gridline(a wall).
this wall is visible
'slide' the ray to the right along that single wall to it's corner
now reapeat the ray walking check, if you hit something closer, then 'slide' along that wall for the next ray check
or it might hit some more distant wall, same deal tho...
and so on...

in this manner... rather than have rays everywhere (potentially wasteful as they might hit the same wall many times) your rays are chosen only to check the critical points of the map -the corners of walls where map features transition
and it only checks the nearest one; ignoring those that are hidden behind...

Share this post


Link to post
Share on other sites
I will try the easiest method first and go from there, thanks guys.

gwihlidal: No code needed I rather read theoretical methods and figure the coding out myself (more fun that way)

Share this post


Link to post
Share on other sites

This topic is 4095 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

Sign in to follow this