Jump to content
  • Advertisement

Archived

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

tiutiu

Occlusion culling

This topic is 5599 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

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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!