Archived

This topic is now archived and is closed to further replies.

tiutiu

Occlusion culling

Recommended Posts

Hiya, im trying to implement occlusion culling in my engine. I have a collection of planes forming de frustum in Camera class, so i have a minimum of 6 planes (viewing frustum) that cannot be popped out. I want to use O.Culling in my quadtree, so leaf nodes are potential occluders and their AABB generates occlusion planes that are added to the camera and used to cull remaining objects. My question is, do i have to sort the occluders by distance to camera? When do i have to do so? hmmm i've read gamasutra's article "Fast Occlusion Culling in outdoor rendering" or something like that but i need a bit of help for clearing up the OC algorithm implementation. here is an image of my engine rendering the quadtree with leaf nodes Bounding boxes (each node has a world bounding box but i dont render em in this shot). http://membres.lycos.fr/stonedrat/shot6-occlusion-culling.jpg pink triangle is camera, green lines are the viewing frustum, and red rectangle would be the edges of the leaf BBox that should be used to compute occlusion planes. [edited by - tiutiu on August 11, 2003 7:17:23 AM]

Share this post


Link to post
Share on other sites
well, sorting would at least prevent you to do a lot of tests that are occluded by something closer to the camera anyway. the problem i see is that using the bounding box as occluder is only a good idea if the terrain is completely filling this box.

Share this post


Link to post
Share on other sites
I''ve been reading much more about that topic and i''ve seen so many problems.

An AABB is not the best volume to enclose a portion of terrain (or a quadtree leaf node). The bound should be a minimum volume OBB or a convex hull.

So what method do you use for occlusion culling? i think its an interesting topic because there are so many ways of implementing it.

Share this post


Link to post
Share on other sites
Maitaining a mathematically accurate convex hull would be an overkill even if it was aligned according to cardinal axes. What is this converx hull you speak off? In my terrain, I''m thinking of performing hierarchial occlusion culling with AABB, however the problem is for example a spike in the heightmap(white bit in the middle of black bits and that would destroy the idea.

Share this post


Link to post
Share on other sites
if you just want to get it up and running use the lowest point of the bounding box. its pretty much guaranted that everything below the bounding box is completely filled ,-) (though you shouldnt try this with anything but a terrain).

what im currently doing (as i dont want to use the much more efficient horzion approach) is building a frustum for the object i want to TEST (not every single potential occluder), then use line rasterization to trace a line from the patch im in to the patch i want to test. at this point you already know your octant (the direction youre moving) and which two corners of the bounding box are the furthest left and right. a regular grid has a few nice attributes that make things easier. for example you will never need more than two patches (or whatever you call them) to occlude another one.

for the height it sounds more complicated than it is. if your point of view is above the top of the bb you want to test you pick the corner thats closer to you for the test object and the one further away for the occluder.. or the other way round if your pov is lower (i guess you can leave that one out and use the center or whatever if you use the lowest point). just take a piece of paper and draw around a little to see the reason for this.

so now with two points for left/right and one for top i build three planes. for every occluder you come across first test if its top point (simple case: minY of the bb) is above the top plane. if not, skip it. then see if left and right are outside on their sides. if they are the occluder is completely filling the frustum and hence hiding the tested object. if one of those two is outside (its impossible for both being outside at the same time) just take the neighbouring patch on this size and do the height test (no need for left/right, as two next to each other ALWAYS are broad enough).

the drawback is of course that for every part not failing the view frustum test you start a line and test every occluder on the way (for rather flat terrains that might be pretty much useless work, though skiping patches below a certain height can help). also in my case the line drawing was taking more time than the actual occlusion test.

this wont work for hierachical approaches (not without modifications at least) as its building on a grid where every cell has the same size (except you either add more neighbours or limit yourself to testing only single patches as occluders).

if you dont care about a few kb more data id probably go for horizons, if you dont mind your culling take twice as long as just frustum culling the above should work too. or you just take a piece of paper and try to make something up. usually its not the best solution or you just find out that someone else did the same (just better) a long time ago, but its still fun and sometimes necessary to better understand those other solutions.

if you got a gf3 or better you can see it at work:
terrain.zip
pic1
pic2

those terrible colors are a weird way to follow the culling. red means didnt occlude, green means occluded alone (or occluded by a single patch), yellow means a neughbour was tested, blue means it was tested as neighbour but didnt occlude, light blue means neighbour and occluded (or occluded by patch+neighbour). well, or just ignore the colors, stare at the picture and save the money for drugs *lol*

Share this post


Link to post
Share on other sites
I dont understand your method, i''ve read your reply 3 or 4 times but i still dont get it (maybe its my english level, i dont know).

What i want first of all is occlusion culling for my terrain. First i thought using AABB should be ok, but they dont fit good with geometry. The problem is to calculate the occluding plane/planes so every node below that plane is occluded (that means if im climbing a hill the plane formed with my position and the hill are occluding everything below them.

So i need a little explanation on how to accomplish that task, or a bit of orientation if im looking to the wrong way (or algorithm hehe). Thanks a lot for your help Trienco

Share this post


Link to post
Share on other sites
This is one method http://www.gamasutra.com/features/20020717/bacik_01.htm however it requires somewhat accurate calculation of convex hulls. Also on flipcode there are quite a few articles on the same topic.

Oh by the trienco, that terrain looks really nice. Looks like you are pushing a ton of triangles in the normal treshold level. For some reason it crashed on my computer once I started moving around and I never got to experience with the occluding.


What about the nvidia/hp occlusion culling extensions? What kind advatanges do they give you?

Back to original topic, well as far as I understood the hierarchial occlusion culling is only for octrees, because every patch needs to be aligned the same and they have to be of same size. I believe glBASE iScape project has full source on that one.

Share this post


Link to post
Share on other sites
its rather my english combined with my complete unability to explain things. i'll try to load up a few sketches. the main idea is not to build a frustum for the occluder but the occluded object (but thats probably just the result of me testing if something is occluded instead of testing what something is occluding).

problem is you have to use the lowest point. you could calculate a few of those for different directions, but simply using the lowest point of the bb for the occluder and the highest for the occluded isnt as bad as it seems ,-)


"Oh by the trienco, that terrain looks really nice. Looks like you are pushing a ton of triangles in the normal treshold level. For some reason it crashed on my computer once I started moving around and I never got to experience with the occluding."

not as many as id like to. the old version had the typical 12million per second, the new one is down to 8 (though the tex coords are quite far away from the position coords in memory, which might be the reason for this difference.. most of it is pretty much the same). you can change the threshold until youre below 5000 rendered triangles. doesnt look as bad as i thought but of course you shouldnt complain about lod popping if you do ,-).

did it crash when you tried to move or after moving a few seconds?

[edited by - Trienco on August 12, 2003 1:53:38 PM]

Share this post


Link to post
Share on other sites

What do you think of this idea...

1. I build a octree out of the mesh
2. I cull out any nodes not in view
3. for each visible node I render to a texture using a different color for each node
4. I then read each pixel of the texture and set the node as visible if it''s color is there
5. build a list of only visible nodes and render them

*remember the nodes that are rendered to the texture do not have to be the full poly version...maybe the same low res used for collision

ok..heres a quick hack to test the idea and it seems to work, the bigger the texture the more accurate the culling but slower to cull...

http://dab20030.tripod.com/Occlusion.zip

you can see the effect of the culling best in wireframe mode (press f) and turn the occlusion on/off (press o)
move around with wsad qz

Share this post


Link to post
Share on other sites
hm.. id have two problems with that. first that sounds exactly like what the occlusion query extensions do, second, when i played around with them just rendering the bounding box to test if its visibile took nearly as long as just rendering the whole thing. together with reading back the results etc. all that occlusion testing took longer than it would have to just render it all. so its only useful if you have a whole lot of geometry you can cull at once.

on second glance. theres one difference. the extension requires to render occluders first and then do the testing, while yours doesnt require any sorting or whatever. i cant download the file, but if you got it to work fast enough to actually really save any time then it doesnt sound too bad. though i usually try to seperate everything accessing the api from the rest. preparing the scene for rendering should be done without touching the api to maximize the time it got to render your last frame. but doing the occlusion as very last step before rendering should be enough.

something like:
do updates
prepare scene for rendering
swapbuffer
render scene

because doing:
render scene
swapbuffer

will mean you have to wait for the scene to be rendered before you can swap the buffers, ergo youre not getting the full advantage of letting cpu and gpu work indepent of each other.


i uploaded something that probably wont help to much. its supposed to illustrate the two frustum planes, the used corners of the bbox (left/right) the corners that depend on whether your pov is above the box or below (front/back or back/front) and the division into octants, as the octant decides which corners and neighbours to use.

also i uploaded a new binary and hope it doesnt crash (also has part of an editor, which so far only allows to draw on the terrain and set the blend factors)
http://festini.device-zero.de/occ.gif

Share this post


Link to post
Share on other sites
Hmm... I think I will leave occlusion culling for awhile and move to triangle reduction.

Oh and by the way the terrain crashed after moving. Everything sort of started turning into red and crahsed.

Share this post


Link to post
Share on other sites
Im with Captain Goatse, i think ill focus on triangle reduction and using GeoMipMapping (i got a paper on it). I''ve been looking to your source code Trienco and its a bit weird hehe.

In that paper they say to have N copies of each patch (with N=Number of geomipmaps) so you render the copy for each LoD for the patch, obtained with camera distance and other parameters.
The problems are the cracks in patch junctions with different LoD. The paper says that to solve this we use traingle fans for the links between patches. Is that what you do in your source code? I see LinkPiece and BodyPiece clases, are they the links between different geomipmap levels?

Hmmm i hope you could explain a bit your implementation of geomipmapping, cuz i didnt know of that kind of terrain management.

Cheers

Share this post


Link to post
Share on other sites
quote:
Original post by Captain Goatse
Hmm... I think I will leave occlusion culling for awhile and move to triangle reduction.

Oh and by the way the terrain crashed after moving. Everything sort of started turning into red and crahsed.


hmmm.. i thought there might be the usual wild memory writes but purify didnt find anything. turning into red is wanted for a short period when the sun sets, but it doesnt sound like this kind of turning red. what card and driver are you using? whats confusing me is that moving will change nothing but the modelview matrix. damn, i need more different machines to test. for example if changing to overhead view with s will also crash, or if disabling occlusion culling with o would solve it. another problem is of course, that the default movement speed is so high, that youre reloading 3 of 9 sectors every .5 - 1 seconds. if this version was still distributing it over a few steps and your machine is really fast it might end up needing a reload before the old one finished (i could only get that a few times and then decided that the new map format and compressed textures loaded so fast, that it doesnt make sense to divide into smaller steps anyway).

Share this post


Link to post
Share on other sites
quote:
Original post by tiutiu
Im with Captain Goatse, i think ill focus on triangle reduction and using GeoMipMapping (i got a paper on it). I''ve been looking to your source code Trienco and its a bit weird hehe.



hehe, and its completely uncommented, optimized at weird places and still shorter and cleaner than the original "building site" (where you just add more and more stuff with the mess getting bigger and bigger)

quote:

In that paper they say to have N copies of each patch (with N=Number of geomipmaps) so you render the copy for each LoD for the patch, obtained with camera distance and other parameters.



i dont have different copies of the patch itself (in fact the way i got the geometry now is more confusing but meant to save memory). just different index arrays for different lods that skip unneeded vertices. as this array is the same for every single patch (only the offset into the vertex buffer changes) you need one for every lod and variant. typically thats those 16 per lod (. is a missing side):

xxx xxx xxx xxx x.x
xxx xx. xxx .xx xxx
xxx xxx x.x xxx xxx

x.x x.x x.x xxx xxx xxx
xx. xxx .xx xx. .x. .xx
xxx x.x xxx x.x xxx x.x

x.x x.x x.x xxx x.x
xx. .x. .xx .x. .x.
x.x xxx x.x x.x x.x

quote:

The problems are the cracks in patch junctions with different LoD. The paper says that to solve this we use traingle fans for the links between patches. Is that what you do in your source code? I see LinkPiece and BodyPiece clases, are they the links between different geomipmap levels?



i didnt like the fans. in some situations a fan connecting all vertices to the corner looks plain ugly (imagine this point being high up while the points at the opposite end are rather low.. you end up with ugly edges).

the body pieces are different versions of the body with parts left out that are replaced with linking pieces. the linking pieces are the worst code i''ve ever written, because all those variables for different levels and the weird indexing are making it hard to follow. what its doing is this (two examples, because i was always pis.. when they''d only show it for a difference of one level):

x-x x----x
|/| |././|
x.| x../.|
|\| |./..|
x-x x....|
|/| |.\..|
x.| x..\.|
|\| |.\.\|
x-x x----x

not as simple as a fan but more regular. or you just imagine it as a couple of fans along the edge (2 in this case).

quote:

Hmmm i hope you could explain a bit your implementation of geomipmapping, cuz i didnt know of that kind of terrain management.



hm.. i start by not telling that im not using any kind of quadtree. i played around with it to speed up culling and other things but ended up being either slower or at least not faster than doing it brute force.

all in all its your basic geomipmapping with a few small changes to save memory and avoid redundant data. lod is selected via precomputed error per patch and lod divided through squared screen distance.

if you have any specific questions about certain parts of it, just ask ,-)

Share this post


Link to post
Share on other sites