• FEATURED

View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Occlusion Culling

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

36 replies to this topic

#21RandomLogic  Members

Posted 05 May 2003 - 03:18 AM

Hi,

When talking about a SW rasterizer. Does this include just what seems obvious to me in order to create the mask, i.e. transformation, line drawing and poly filling, or is there more to it?

Also just out of curiousity what methods (known algo''s???) are used for the line/fill tasks?

And one last... I assume the map is rendered to a 2D array in the main memory.. true or false?

#22CoffeeMug  Members

Posted 05 May 2003 - 08:18 AM

Actually it''s simpler then that. Since you''re only interetsed in the depth buffer the software rasterizer only handles drawing to a depth buffer. You don''t have to worry about coloring.

#23Zemedelec  Members

Posted 05 May 2003 - 08:17 PM

CoffeeMug:
Well, nobody mentioned colouring/texturing - it is obvious one do ot need ''em, isn''t it?
And if there is a way to use c-buffer over z-buffer all things get very fast...

#24treething  Members

Posted 05 May 2003 - 09:11 PM

One thing you can do to speed up the occlusion buffer rendering is to use a single depth value for an entire triangle. When rendering an occluder triangle using the furthest z-value of the 3 vertices for the entire triangle will make the occlusion tests more conservative, but reduces the rendering to filling a span of memory with a single value. Similarly, when doing the occlusion queries you can use the closest z-value of the 3 vertices.

#25CoffeeMug  Members

Posted 05 May 2003 - 09:37 PM

quote:
Original post by treething
One thing you can do to speed up the occlusion buffer rendering is to use a single depth value for an entire triangle. When rendering an occluder triangle using the furthest z-value of the 3 vertices for the entire triangle will make the occlusion tests more conservative, but reduces the rendering to filling a span of memory with a single value.

Hmm... This is an interesting idea. I wonder why I haven''t thought of that Anyway, it''s not as easy as simply filling a span of memory. You still have to go through the scanline algorithm. You can''t just do FillMemory(start, end, zval). This can be fairly expensive with large triangles...

#26treething  Members

Posted 05 May 2003 - 09:48 PM

I should add that its just an idea of mine. I havent actually implemented it, so I dont know for sure if its any good.

#27Yann L  Members

Posted 06 May 2003 - 11:03 AM

quote:

Still wondering what methods people use to choose occluders, since most OC schemes require a good method to get good results. What type of precomputed information do people use and how do you use it for dynamic occulder determination.

More or less distance based selection. Along with estimated projection area (the larger, the better the occluder). Add occluders in order, until a (CPU dependent) maximum number of polygons are reached.

quote:

Do people use time coherence in estimate the occluder set for the next frame?

Not really, at this point. Making good use of time coherency would require a way to consistently check the actual effectiveness of an occluder (ie. how much would the occlusion result degrade, if that occluder was removed). Resolving such dependencies can be very complex and slow, especially when taking the effects of occluder fusion into account. A certain other time coherency is used though, by considering the occluders that were visible on the last frame (ie. that weren't occluded themselves) with a higher priority on the current frame. This gives a slightly better occlusion set, as the number of redundant occluders is reduced.

quote:

Yann, can you estimate how many triangles you render with software rasterizer per frame ?

Hard to say, as I don't use triangles. I use planar shapes instead, arbitrary convex or concave polygons (that can have holes). That way, I only need to evaluate the z-gradients once for each shape. If I used triangles, I would have a lot of redundant gradient computations, since coplanar triangles are very common on occlusion skins.

quote:

Yann: So whats the difference between your method and the hierarchical z-buffer ?

None It essentially is a software rendered hierarchical z-buffer. With the difference, that only dedicated low-poly occlusion geometry is rendered to it, instead of the entire scene.

quote:

Also just out of curiousity what methods (known algo's???) are used for the line/fill tasks?

I simply use the standard "create the outer polygon lines, and fill horizontal spans inbetween" algorithm. That's the same that was commonly used in all those old non-accelerated 3D renderers. It's a little bit modified to support concave polygons.

quote:

And one last... I assume the map is rendered to a 2D array in the main memory.. true or false?

True.

quote:

One thing you can do to speed up the occlusion buffer rendering is to use a single depth value for an entire triangle. When rendering an occluder triangle using the furthest z-value of the 3 vertices for the entire triangle will make the occlusion tests more conservative, but reduces the rendering to filling a span of memory with a single value

Hmm, that would definitely speed up the rendering. But I'm not sure, if the occlusion would not becomne a little too conversative. Note that I didn't try it either, so I'm merely speculating. You would have to take the differential gradients of a polygon (1/z, in screenspace) into account, and if the difference isn't too big, then you could approximate by a constant value. Hmm, sounds good. But you shouldn't so that on all of your occlusion geometry. Imagine the player standing besides a long wall, orthogonal to the camera plane (extending from behind the camera, up to the horizon, filling the entire half of the screen).

The gradient differential would be extremely large, and if you approximated that wall with a constant depth, the occlusion effect would approach zero. Now, if you have an entire town behind that wall, well, you get the rest

But the idea is pretty good, and would probably speed up the rendering process. Especially on occluders being almost parallel to the camera plane. I will try it out on my engine, and report back.

[edited by - Yann L on May 6, 2003 6:06:01 PM]

#28billybob  Members

Posted 06 May 2003 - 11:12 AM

if you have large polygons, it can be really easy to occlude by making planes between the edges of the polygon and the viewer, almost like a frustrum but with more/irregular sides.

#29Heretic  Members

Posted 06 May 2003 - 07:47 PM

quote:

None It essentially is a software rendered hierarchical z-buffer. With the difference, that only dedicated low-poly occlusion geometry is rendered to it, instead of the entire scene

Heh, I thought you said you use HOM

BTW. Have ya measured how much time statistically it takes to test the occlusion. I know its parallel with the GPU but CPU time is also useful for other things, so Im curious...

#30Yann L  Members

Posted 07 May 2003 - 04:46 AM

quote:

Heh, I thought you said you use HOM

Well, HOM just means ''hierarchical occlusion mapping''. How you achieve that, either by coverage maps and depth estimation buffers, as in the first Zhang approach, or by cutting the coverage and keeping an exact depth buffer hierarchy, doesn''t really matter. The result is the same.

quote:

BTW. Have ya measured how much time statistically it takes to test the occlusion. I know its parallel with the GPU but CPU time is also useful for other things, so Im curious...

The test itself is typically very fast. Most positive or negative results can be obtained on a very coarse level, due to the hierarchy. Only half visible objects will recurse into the map, but that''s not really critical either (the whole testing code is in ASM). The bigger issue is the occlusion map rendering and hierarchy creation. Is it worth it ? primarily depends on your level design and geometry. For me, it cuts over 90% of the faces, I couldn''t live without it. But in other cases, it might not be so effective. Best thing, is to include a little runtime profiler into your occlusion code, rdtsc is your friend.

#31treething  Members

Posted 07 May 2003 - 11:18 PM

Hey Yann, did you get a chance to try out the constant-depth idea?

#32Heretic  Members

Posted 07 May 2003 - 11:29 PM

Me thinks that this const-depth idea might be more useful if the space partitioning relied more upon the scene geometry. For example in this long hallway scene you might know that rooms are behind it and only check for the occlusion, not condidering the stored depth. This again can be accomplished via a semi-automatic portalization that I wrote about a couple of posts ago.

#33Yann L  Members

Posted 08 May 2003 - 12:31 AM

quote:
Original post by treething
Hey Yann, did you get a chance to try out the constant-depth idea?

Yes, I did. It works pretty nice, actually. Although I had to set the threshold for the 1/z gradient pretty low. The occlusion went highly conservative very fast, otherwise. Still, I get a speedup of around 60% on the rendering, if directly in front of a parallel wall (obviously, since the constant filling reduces the impact of CPU fillrate). Generally, you can achieve around 20% speedup on a normal camera view. Not bad for such a simple modification.

#34treething  Members

Posted 08 May 2003 - 02:18 PM

Cool.

#350BZEN  Members

Posted 09 May 2003 - 12:29 PM

Yeah, looks like it falls down to applying a ''billboard'', so triangles that have a high gradient would not work. It''s a shame you have to do all that occlusion culling in software. Maybe in next generation of hardware, we''ll get some fast query mechanism to get some feedback from the renderer, if that''s ever possible.

#36CoffeeMug  Members

Posted 10 May 2003 - 04:49 PM

We have that in current generation hardware. The problem is that you cannot take advantage of CPU/GPU parallelization due to the fact that with current state of hardware occlusion culling CPU and GPU need to constantly talk to each other.

Perhaps in the next generation hardware we''ll be able to pass "if..then" instructions to hardware queries, this is when things are going to get really quick.

#37IronPeter  Members

Posted 11 May 2003 - 10:41 PM

What is about visibility determination for shadow-map lighting? For example, object A is invisible, but it can cast shadow to visible object B. So it must be rendered to the sm.

This is more complicated type of visibilty determination. Is it possible to use HOM (rendering from light source) for this purposes?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.