How does this PVS algorithm sound?

Have you considered how much storage your PVS data will take for large areas? How big are the sub-cubes you use for the ray marching? Changing the size of those cubes will radically affect the amount of storage needed for the whole data set, as well as affecting the accuracy of the algorithm overall. You're also talking about a huge number of ray marches, which might get pretty slow (think of all the different permutations you'd have to compute even for a 4x4x4 cube).

You might consider doing something like a kd-tree or an octree to subdivide the space instead of regular cubes; marching a ray through an octree is slightly harder than a regular cube grid, but an interesting exercise, and it could be a decent way to optimize the algorithm overall.

In general it's a reasonable approach from a theoretical standpoint, but you might find that the practical cost of actually doing all that math is a bit prohibitive. Kudos for thinking about it enough to get this far, though!

Have you considered how much storage your PVS data will take for large areas? How big are the sub-cubes you use for the ray marching? Changing the size of those cubes will radically affect the amount of storage needed for the whole data set, as well as affecting the accuracy of the algorithm overall. You're also talking about a huge number of ray marches, which might get pretty slow (think of all the different permutations you'd have to compute even for a 4x4x4 cube).

You might consider doing something like a kd-tree or an octree to subdivide the space instead of regular cubes; marching a ray through an octree is slightly harder than a regular cube grid, but an interesting exercise, and it could be a decent way to optimize the algorithm overall.

In general it's a reasonable approach from a theoretical standpoint, but you might find that the practical cost of actually doing all that math is a bit prohibitive. Kudos for thinking about it enough to get this far, though!

I was going to make the cube size adjustable by the user and I was also thinking about using a tree structure to optimize it. However, I just had a crazy idea. What if I used the GPU to accelerate the process? Imagine something like shadow mapping and each polygon is colored using the vertex shader based on which cube it's in. Then I would have to somehow detect the presence of particular color in a texture to indicate the object is visible. Not worked out the details yet...

My point is that even for a 4x4x4 grid, you're talking about 4096 different permutations that have to be tested. To get reasonable culling, you would have to use a very large grid for any realistically-sized level. Even a 10x10x10 grid is 1 million permutations. If each permutation takes 1 KB to list every visible triangle (which is optimistic), you're storing almost a GB of data just for your PVS.

You're onto a decent idea, but there's a couple missing pieces. First, you need to be able to compute which cell a triangle is in rather than storing it. Second, you need to be able to compute the PVS on the fly using the camera's view frustum (plus of course frustums for any reflective/refractive surfaces, etc. etc.) instead of trying to store it all in a massive lookup.

Once you get these two elements combined, you're really just doing a frustum+octree cull, which is already a pretty well-known technique and easy enough to implement.

My point is that even for a 4x4x4 grid, you're talking about 4096 different permutations that have to be tested. To get reasonable culling, you would have to use a very large grid for any realistically-sized level. Even a 10x10x10 grid is 1 million permutations. If each permutation takes 1 KB to list every visible triangle (which is optimistic), you're storing almost a GB of data just for your PVS.

You're onto a decent idea, but there's a couple missing pieces. First, you need to be able to compute which cell a triangle is in rather than storing it. Second, you need to be able to compute the PVS on the fly using the camera's view frustum (plus of course frustums for any reflective/refractive surfaces, etc. etc.) instead of trying to store it all in a massive lookup.

Once you get these two elements combined, you're really just doing a frustum+octree cull, which is already a pretty well-known technique and easy enough to implement.

I think you may have misunderstood the idea a bit. Here is the basic class I'm going to use to hold the PVS data:



class __declspec(dllexport) PVS
{
public:
Mesh* Mesh;
Ovgl::Vector3 Min;
Ovgl::Vector3 Max;
std::vector< PVS* > PVSets;
};


As you see it has a mesh which is the triangles in that cube. Min and Max is the bounding box for that set and PVSets are the potentially visible sets.

I think you may have misunderstood the idea a bit. Here is the basic class I'm going to use to hold the PVS data:



class __declspec(dllexport) PVS
{
public:
Mesh* Mesh;
Ovgl::Vector3 Min;
Ovgl::Vector3 Max;
std::vector< PVS* > PVSets;
};


As you see it has a mesh which is the triangles in that cube. Min and Max is the bounding box for that set and PVSets are the potentially visible sets.

Why don't you use an octree? Min and max are implicit and PVSets can be calculated easily on the fly.

[quote name='SteveDeFacto' timestamp='1314951119' post='4856643']
I think you may have misunderstood the idea a bit. Here is the basic class I'm going to use to hold the PVS data:



class __declspec(dllexport) PVS
{
public:
Mesh* Mesh;
Ovgl::Vector3 Min;
Ovgl::Vector3 Max;
std::vector< PVS* > PVSets;
};


As you see it has a mesh which is the triangles in that cube. Min and Max is the bounding box for that set and PVSets are the potentially visible sets.

Why don't you use an octree? Min and max are implicit and PVSets can be calculated easily on the fly.
[/quote]

Yes I think you are right, an octree would be far better than searching a list of bounding boxes. However, computing the PVSets is always going to be a time consuming process. The main thing I'm wanting to improve is the what in which I determine if a set is visible or not. The method of ray casting is not very satisfactory to me because to really get a flawless test I need to cast a ray from every single position inside the cube to every single position inside the object. There is a way to do it but the math confuses me... Something about ray casting with 5 dimensions...

Yes I think you are right, an octree would be far better than searching a list of bounding boxes. However, computing the PVSets is always going to be a time consuming process. The main thing I'm wanting to improve is the what in which I determine if a set is visible or not. The method of ray casting is not very satisfactory to me because to really get a flawless test I need to cast a ray from every single position inside the cube to every single position inside the object. There is a way to do it but the math confuses me... Something about ray casting with 5 dimensions...

Maybe I'm wrong but I think you are mixing two different things: octree frustum culling and sparse voxel octrees.

I think you are referring to SVOs (Sparse Voxel Octrees) when you speak about raycasting since in octree frustum culling there's no need to fire even a single ray.

Octree frustum culling works this way.
1- you split your model with the octree nodes, stopping when they reach a minimum number of polygons or a minimum size in 3d units. This structure is precalculated and exported in your custom format.
2- at runtime you can easily check which nodes are visible with frustum culling.
3- you draw the meshes inside visible nodes

ps for small models, expecially if you have a wide number of materials and smart rendering pipelines, it might be faster NOT to use an "acceleration" structure like that because it's not easy to find a compromise between useful culling and speed. The more nodes you have the more effective culling is but as the number of nodes increases also the number of draw calls does (this is the obvious result of the splitting process). From my pov balancing that isn't easy... on some models I just don't use any acceleration structure.

[quote name='SteveDeFacto' timestamp='1314954731' post='4856656']
Yes I think you are right, an octree would be far better than searching a list of bounding boxes. However, computing the PVSets is always going to be a time consuming process. The main thing I'm wanting to improve is the what in which I determine if a set is visible or not. The method of ray casting is not very satisfactory to me because to really get a flawless test I need to cast a ray from every single position inside the cube to every single position inside the object. There is a way to do it but the math confuses me... Something about ray casting with 5 dimensions...

Maybe I'm wrong but I think you are mixing two different things: octree frustum culling and sparse voxel octrees.

I think you are referring to SVOs (Sparse Voxel Octrees) when you speak about raycasting since in octree frustum culling there's no need to fire even a single ray.

Octree frustum culling works this way.
1- you split your model with the octree nodes, stopping when they reach a minimum number of polygons or a minimum size in 3d units. This structure is precalculated and exported in your custom format.
2- at runtime you can easily check which nodes are visible with frustum culling.
3- you draw the meshes inside visible nodes

ps for small models, expecially if you have a wide number of materials and smart rendering pipelines, it might be faster NOT to use an "acceleration" structure like that because it's not easy to find a compromise between useful culling and speed. The more nodes you have the more effective culling is but as the number of nodes increases also the number of draw calls does (this is the obvious result of the splitting process). From my pov balancing that isn't easy... on some models I just don't use any acceleration structure.
[/quote]


No, I'm talking about this. Mainly this part:

[font=sans-serif][size=2]

Exact algorithms
These provide optimal visibility sets, where there is no image error and no redundancy. They are, however, complex to implement and typically run a lot slower than other PVS based visibility algorithms. Teller computed exact visibility for a scene subdivided into cells and portals[sup][7][/sup] (see also portal rendering).

The first general tractable 3D solutions were presented in 2002 by Nirenstein et al.[sup][1][/sup] and Bittner[sup][8][/sup]. Haumont et al.[sup][9][/sup] improve on the performance of these techniques significantly. Bittner et al.[sup][10][/sup] solve the problem for 2.5D urban scenes. Although not quite related to PVS computation, the work on the 3D Visibility Complex and 3D Visibility Skeleton by Durand [sup][3][/sup] provides an excellent theoretical background on analytic visibility.

Visibility in 3D is inherently a 4-Dimensional problem. To tackle this, solutions are often performed using Plücker (see Julius Plücker) coordinates, which effectively linearize the problem in a 5D projective space. Ultimately, these problems are solved with higher dimensional constructive solid geometry.

[/quote]

[/font]

maybe you could take a look at the quake/halflife source, I think it's using the PVS and it seems to have quite good results. (why reinventing the wheel? )

The part I'm questioning is if ray casting from all 8 corners is enough to detect visibility. Just seems ghetto but I think it should technically work fine.

Not entirely sure exactly how you mean your algorithm should work, but that's probably not enough. It's very possible to have a cube where only somewhere in the center can you see through a small portal at another part of the map. Generally you can't prove something to be hidden with raycasts, you need to do volume-casts of the union of all potential view volumes and make sure the volume is completely clipped.

One way that can work if you have fitting geometry (indoor maps for example with lots of hidden areas), is to divide your entire map into regions (could be cubes intersected with the open volume of the map), and construct portals to all adjacent regions. Then you construct the visible volume through each portal (starts as an infinite half-space) and basically flood fill the whole map while clipping the view volume when entering neighboring regions, stopping if the volume is completely clipped. I guess this algorithm is O(n^2) over the amount of regions in the worst-case, but there's a lot of early stopping if your map isn't very open.
I think earlier Quake games did something like that, using the BSP leafs as convex regions with portals in between. It's an expensive calculation but not extremely expensive. For a map with many closed spaces and corridors you can have tens of thousands of convex regions and still never have to fill very many before any potential visibility is cleared.

[quote name='SteveDeFacto' timestamp='1314922536' post='4856533']
The part I'm questioning is if ray casting from all 8 corners is enough to detect visibility. Just seems ghetto but I think it should technically work fine.

Not entirely sure exactly how you mean your algorithm should work, but that's probably not enough. It's very possible to have a cube where only somewhere in the center can you see through a small portal at another part of the map. Generally you can't prove something to be hidden with raycasts, you need to do volume-casts of the union of all potential view volumes and make sure the volume is completely clipped.

One way that can work if you have fitting geometry (indoor maps for example with lots of hidden areas), is to divide your entire map into regions (could be cubes intersected with the open volume of the map), and construct portals to all adjacent regions. Then you construct the visible volume through each portal (starts as an infinite half-space) and basically flood fill the whole map while clipping the view volume when entering neighboring regions, stopping if the volume is completely clipped. I guess this algorithm is O(n^2) over the amount of regions in the worst-case, but there's a lot of early stopping if your map isn't very open.
I think earlier Quake games did something like that, using the BSP leafs as convex regions with portals in between. It's an expensive calculation but not extremely expensive. For a map with many closed spaces and corridors you can have tens of thousands of convex regions and still never have to fill very many before any potential visibility is cleared.
[/quote]

Yes, that is the problem I've been thinking about. You seem to have a clear grasp on the concept I speak of. The amount of time it takes to run the algorithm is not of importance since it will be done during the creation of the map much like compiling a .map file to a .bsp file.

I think you may have misunderstood the idea a bit. Here is the basic class I'm going to use to hold the PVS data:



class __declspec(dllexport) PVS
{
public:
Mesh* Mesh;
Ovgl::Vector3 Min;
Ovgl::Vector3 Max;
std::vector< PVS* > PVSets;
};


As you see it has a mesh which is the triangles in that cube. Min and Max is the bounding box for that set and PVSets are the potentially visible sets.

I'm not sure I follow your intent with this class.

I'm guessing that an instance of PVS represents a single cube in the grid? And that the PVSets member describes all the other visible cubes? How does that work? Isn't it true that all cubes are potentially visible from all other cubes unless you have an incredibly well-occluded map? In general I'm not sure I understand what you mean PVSets to represent and how it maps onto the algorithm you describe.

[quote name='SteveDeFacto' timestamp='1314951119' post='4856643']
I think you may have misunderstood the idea a bit. Here is the basic class I'm going to use to hold the PVS data:



class __declspec(dllexport) PVS
{
public:
Mesh* Mesh;
Ovgl::Vector3 Min;
Ovgl::Vector3 Max;
std::vector< PVS* > PVSets;
};


As you see it has a mesh which is the triangles in that cube. Min and Max is the bounding box for that set and PVSets are the potentially visible sets.

I'm not sure I follow your intent with this class.

I'm guessing that an instance of PVS represents a single cube in the grid? And that the PVSets member describes all the other visible cubes? How does that work? Isn't it true that all cubes are potentially visible from all other cubes unless you have an incredibly well-occluded map? In general I'm not sure I understand what you mean PVSets to represent and how it maps onto the algorithm you describe.
[/quote]


Yes, your first few statements basically cover the concept but I don't necessarily think it will require an unreasonably highly occluded map. Take for example a half life 2 map. Should decrease polygon count to around 20% of the full map and [color="#1C2837"]frustum culling it could improve performance even more. With less occluded maps the polygon count would probably be lower so there will be less need for it. I think all around this is a good solution but the real question is how to compute the PVS without any errors... Also I'm talking about spiting the map into far more sets than 4x4x4 more like 256*256*256

By my estimation, that comes to 281,474,976,710,656 permutations you need to handle. Are you sure you've thought through the implications of this?

By my estimation, that comes to 281,474,976,710,656 permutations you need to handle. Are you sure you've thought through the implications of this?

What do you mean by [color="#1C2837"]permutations? I know I would need to handle 16,777,216 sets but with an o[color="#1C2837"]ctree it should be manageable and it should only take a bit more memory than the original mesh.

There are 16,777,216 cubes. Each cube needs to test each other cube in the grid to see if that cube is visible, because a cube might be occluded from one side but not the other if you have reflective or transparent surfaces. That means 281 trillion combinations of cubes-testing-visibility-of-other-cubes to get a complete, fully accurate PVS database in the general, worst case.

There are 16,777,216 cubes. Each cube needs to test each other cube in the grid to see if that cube is visible, because a cube might be occluded from one side but not the other if you have reflective or transparent surfaces. That means 281 trillion combinations of cubes-testing-visibility-of-other-cubes to get a complete, fully accurate PVS database in the general, worst case.

That is done during map compile time and can be saved into the map file. Yes, compiling the map will be a slow process but in the end it will be worth the performance gain. At the moment I can't render a complex map with more than 15 FPS... I'm pretty sure this would be close to how half life 2 does it though I don't intend to support portal rendering at the moment.

Suppose you can calculate a complete PVS for each cube in your 256x256x256 grid in 1 millisecond.

This leaves 8,295 years of calculation just for one map.


Are you sure you have thought through the implications of your idea?

Suppose you can calculate a complete PVS for each cube in your 256x256x256 grid in 1 millisecond.

This leaves 8,295 years of calculation just for one map.


Are you sure you have thought through the implications of your idea?

Your math is WAY off! ROFL! There are [color=#1C2837][size=2]16,777,216 cubes which means it will take 4.6 hours... However 256x256x256 is on the extremely heavy side.