Sign in to follow this  

Visibility determination

Recommended Posts

Not that the topic is entirely connected with DirectX, but it concerns 3d graphics and I couldn't find a better place for it. I have a number of polygons and a number of areas (convex hulls, or, in the simplest case, boxes). For every area I want to determine which areas are visible from it (that is, is there a point in area A and a point in area B which are visible to each other). The table will be computed on the stage of creating the scene. Which methods exist for solving the problem? Thanks, in advance.

Share this post

Link to post
Share on other sites
It seems that you need a Portal Engine.

There is a nice article on flipCode about the theory of Portal Engines:

Actually this kind of engine is suitable for indoor scenes. If you need to render outdoor scenes I would go for a octree-based engine.

Share this post

Link to post
Share on other sites
Original post by ReaVeR-Andrey
Not that the topic is entirely connected with DirectX, but it concerns 3d graphics and I couldn't find a better place for it.

How about 'Graphics Programming and Theory', or maybe 'Maths and Physics'. Even 'Game Programming'? [rolleyes]

Anyway, we can be more helpful if you give us a hint as to the environment. If you're indoors, portals or BSPs would be a good place to start. If you're outdoors, then you should look into quadtrees/octrees and PVS culling.


Share this post

Link to post
Share on other sites
I'm just a hobbiest, but I can tell you what I did for my outdoor scene - not that it's necessarily the best way. I might recommend quadtrees before octrees - I found even worlds with a fair amount of elevation differences still seemed to perform a bit better (for me anyway). Once you know which quads are inside your viewing frustum, you can go further by clipping out geometry behind larger obstructions - I did this by tagging larger more definate obstructions and ignoring smaller objects because they're not likely to occlude much. I tagged an invisible bbox around huge chunks of terrain, houses, etc - and then made a "mini-frustum" around the largest obstruction-tagged objects and culled some more quad branches. It seemed to work pretty good - there are probably better ways to do it though.
There are several d3dx functions that can help you to do this, but I don't think there are really any shortcuts/functions specifically for these sorts of things. I'll try to help more if you have any more questions.

ie: Something like this might be handy:

void CalculateViewingFrustum() {
// Get combined matrix
D3DXMATRIXA16 matComb;
D3DXMatrixMultiply(&matComb, &matView, &matProjection);
// Left clipping plane
Frustum[0].a = matComb._14 + matComb._11;
Frustum[0].b = matComb._24 + matComb._21;
Frustum[0].c = matComb._34 + matComb._31;
Frustum[0].d = matComb._44 + matComb._41;
// Right clipping plane
Frustum[1].a = matComb._14 - matComb._11;
Frustum[1].b = matComb._24 - matComb._21;
Frustum[1].c = matComb._34 - matComb._31;
Frustum[1].d = matComb._44 - matComb._41;
// Top clipping plane
Frustum[2].a = matComb._14 - matComb._12;
Frustum[2].b = matComb._24 - matComb._22;
Frustum[2].c = matComb._34 - matComb._32;
Frustum[2].d = matComb._44 - matComb._42;
// Bottom clipping plane
Frustum[3].a = matComb._14 + matComb._12;
Frustum[3].b = matComb._24 + matComb._22;
Frustum[3].c = matComb._34 + matComb._32;
Frustum[3].d = matComb._44 + matComb._42;
// Near clipping plane
Frustum[4].a = matComb._14 + matComb._13;
Frustum[4].b = matComb._24 + matComb._23;
Frustum[4].c = matComb._34 + matComb._33;
Frustum[4].d = matComb._44 + matComb._43;
// Far clipping plane
Frustum[5].a = matComb._14 - matComb._13;
Frustum[5].b = matComb._24 - matComb._23;
Frustum[5].c = matComb._34 - matComb._33;
Frustum[5].d = matComb._44 - matComb._43;

As far as irregular-shaped occlusion goes(hulls), I'm wondering if there's much performance gain(?) Maybe some hierarchial axis aligned bbox's for culling?

Share this post

Link to post
Share on other sites
Really quick and just off of the top of my head "sorry wife agro" but lets say point A is 0 and point b is 2000.0 along the z axis and you are at point A. You would like to see point b in the distance.

So in real life we cannot see objects that are small and far away, but larger objects we can see "they may be small" because they are far away, but up close they are large.

So you would need to write an algorithm that would tell the render to draw these objects if in the view frustem depending on (how far you can see, and the size of an object)

So I might say there is a large tower placed here, it's 1000.0f in height(y) and I also say that any object that is larger then 800.0f (y) in height & is within 2000.0f (z) of myself & is within my view frustom to render this object. And lets say for your camera object you set you can see up to 2000.0f before being culled out. Then you would be able to see point b in the distance from point a if your camera was in the right direction.

Sorry if this not what your looking for, its hard to determine the type of application you have going.

This is in a nutshell (very simplified) what I would use in a 3d world where I am using streaming terrain and have the world objects broken up into different grids using node lists, so I wouldnt have to check all world objects, just however many were in my little grid of an area i was currently present in.

If this is sort of what your asking for, let me know and if you need me to I can fully explain better when i get home this afternoon.

Good luck,

Share this post

Link to post
Share on other sites
Hmm. I tried portal engines, but I decided I'm doing PVS a engine. I need my map editor to generate visibility table that shows which polygons are visible from a given cluster (say, a box). As I said, it may take hours to finish, I don't mind. I've already found information on compressing such information.

Share this post

Link to post
Share on other sites

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