Occlusion Culling Algorithm help wanted
Author
I''ve got a problem.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
For occlusion culling I want an Algorithm that creates for
any polygon (it may be concave or convex)in 3D Space a number of
n (which is given) boxes
which have the property that they all lie completely IN the polygon
and that they are of the biggest possible size to fit the above condition.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Such an Algorithm could be used in the following way::: When we create bounding boxes for each object, we could test if they lie in the n boxes once created with the algorithm above for prevoiusly rendered polygons. If they do, the object we want to render now is completely invisible and we don''t have to draw it.
I don''t know any method for creating such n inner boxes of biggest possible size for a polygone.
HEEEEEEEEEEELLLLLLP me PLLEEEEEASE if you do so
I guess this problem will be extremely hard to get stable, if you want to solve it analytically on arbitrary objects. While it is possible (it''s more or less an optimization problem: the optimal dataset, that fits a given set of constraint equations, needs to be found), you''ll run into lots of problems: floating point accuracy, local minima/maxima in the iteration process, etc.
I would suggest a discrete approach: first create a 3D voxel representation of your object. Voxels that are completely inside the object are set to 1, voxels outside (or intersecting the outline) are set to 0. Gives you a volumetric voxel field.
Now, use some kind of heuristic to determine the optimal set of bounding boxes that fit the voxelset in such a way, that no bounding box ever contains a 0-voxel. Since this step operates solely on a discrete datafield, there are no accuracy issues and mathematical instabilities.
/ Yann
I would suggest a discrete approach: first create a 3D voxel representation of your object. Voxels that are completely inside the object are set to 1, voxels outside (or intersecting the outline) are set to 0. Gives you a volumetric voxel field.
Now, use some kind of heuristic to determine the optimal set of bounding boxes that fit the voxelset in such a way, that no bounding box ever contains a 0-voxel. Since this step operates solely on a discrete datafield, there are no accuracy issues and mathematical instabilities.
/ Yann
start from the objects near you
project a shadow of the objects
save those shadows somewhere
go to the objects far away, and see if they are inside the shadow, if they are, don''t render them..
Something like this should work..
Bruno
project a shadow of the objects
save those shadows somewhere
go to the objects far away, and see if they are inside the shadow, if they are, don''t render them..
Something like this should work..
Bruno
Author
@Bruno
The problem with the shadow is::: when there are very complex objects there''s much runtime processing necessary.
Or do you know a fast accurate way to create a shadow???? If so then please inform me.
I don''t want to transform an object in 2D Space, build the convex hull!!!!!!!, notice the points and then finally create the shadow with my viewpoint. Does there any other method exist to avoid the convex hull?????
@Yann L
the method with the voxels is very good but what about the heuristic for the boxes?? the problem is then to have g voxels and we want n boxes fitting most voxels. Do you know a good method for this???
By the way
thank you both for trying to help me!!!!!!!!!!
The problem with the shadow is::: when there are very complex objects there''s much runtime processing necessary.
Or do you know a fast accurate way to create a shadow???? If so then please inform me.
I don''t want to transform an object in 2D Space, build the convex hull!!!!!!!, notice the points and then finally create the shadow with my viewpoint. Does there any other method exist to avoid the convex hull?????
@Yann L
the method with the voxels is very good but what about the heuristic for the boxes?? the problem is then to have g voxels and we want n boxes fitting most voxels. Do you know a good method for this???
By the way
thank you both for trying to help me!!!!!!!!!!
Have you downloaded the Hybrid/Renderware Umbra/dPVS reference manual yet ? - http://www.hybrid.fi/dpvs_download.html it contains a great amount of great information about occlusion systems. Might give you some alternative ideas.
--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com
--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com
quote:
the method with the voxels is very good but what about the heuristic for the boxes?? the problem is then to have g voxels and we want n boxes fitting most voxels. Do you know a good method for this???
As always, you have tons of options to solve that problem. Since it''s preprocessing, performance shouldn''t be too much of an issue.
Try that simple algorithm (from the top of my head, might have some flaws):
Create a ''3D mipmap'' hierarchy from your voxel volume, always merging 2*2*2 cubes. Don''t interpolate, but make the target voxel in a lower resolution level be 1, only if all of it''s parent voxels are 1. You now have a hierarchical voxel set.
Now a start an iterative process: search the largest bounding box that does not contain any 0-voxels in the set. Use the 3D hierarchy to accelerate the process (besides that, it''s basically brute force). As soon as it is found, save the coordinates of the bounding box in a list, and set all voxels it contains to 0 (also update the parent voxels in the hierarchy). Iterate, until no active (1) voxels are left in the set.
You can''t specify the number of bounding boxes using that method, it will always be more or less optimal (the smallest possible number). I say ''more or less'', because depending on the shape of your voxel object, this algorithm is prone to getting stuck in local minima. But the bounding box set shouldn''t be too bad.
/ Yann
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
