Archived

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

Eric

Backface-culling a group of faces

Recommended Posts

I''m working on a ROAM-based terrain engine. Because I''ll be rendering stuff like canyons, mountains, and other steep terrain, I think there will be lots of opportunities for backface-culling. I''m trying to figure out a way to backface-cull groups of faces cheaply. For example, a cliff side may contain hundreds of faces, but they all point in basically the same direction, so I shouldn''t have to perform a backface test on every individual face. Now, to apply this to ROAM: Recall that, in ROAM, a node is basically a right-triangular patch of the heightmap. If the node is currently a leaf node, then it is rendered with a single triangle. If the node is currently an internal node, then the node contains two or more leaf nodes. So, what I want to do is backface-cull internal nodes, especially ones which are high up in the tree. Basically, I would try to backface-cull the top two nodes in the ROAM hierarchy. If a node could not be culled, I would try to cull its two children, and so on down the tree. I''ve found a solution that works in 2D, but I don''t think it will translate to 3D. Nevertheless, here it is: A portion of a 1D heightmap is being rendered with 8 lines. The two red lines have been precalculated (Its fairly intuitive to see how I''ve come up with these). Now, notice that, if the camera were anywhere in the pink region, then none of the 8 lines would be visible. The camera is in the pink region if (1) it is below both of the two lines, and (2) it is not directly above this portion of the 1D heightmap. To make the 1st test faster, I can precalculate the point P, the green ray, and the cosine of the angle between the green ray and the two red lines. (This is essentially a 2D cone.) Then, I can do a dot product of the camera position and the point P, and compare it to the precalculated cosine value. Like I said, I don''t see a way to translate this to 3D. Presumably, I should be able to find three planes equivalent to the two red lines, or a 3D cone equivalent to the 2D one. Any suggestions on this idea? Any other ideas?

Share this post


Link to post
Share on other sites
Won''t things be even harder when changing between multiple resolutions of terrain? since the edges you thought might block the view could be moving.

You could create a BSP tree, and have a visibility list for each section of it.

Share this post


Link to post
Share on other sites
core114, when I read your post, I was like, "that''s so clever, there must be an acronym for it!" And there is: PVS (potentially visible sets). Why I''ve never bothered to look into this concept before, I don''t know

Anyway, I see that PVS could be faster and more effective than any kind of backface-culling. However, it may be too expensive in terms of memory usage.

Also, I think I''ve figured out how to generate the 3D cone for a triangular patch (if anyone is interested, just ask). core114, regarding your point about multiple resolutions, I think that the highest LOD for a given patch is always going to be the "worst case", so I would just use that to generate the cone.

Any more suggestions on this are welcome.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yes you are on the right way. Will xplain quickly but roughly :

Now consider the rejection volume of each triangle is an half space defined by the oriented plane equation. OK

The exact common rejection volume is the intersection of all these half spaces, thus a convex (opened or close). If the convex shape is closed then your patch is really discontinuous ! LOL U cant cull triangles at once for this one except inside a very small convex area. No use.

However this convex hull will be too complicated for real time.

Then conservatively degrade it. Compute a medium axis (easy). Project every plane on the axis. Take the lowest intersection point I on this axis. And translate all your planes down so that they meet I. Now your convex shape has become a cone which is contained into the exact rejection volume.

Depending on how many planes actually border this cone you may choose a plane definition or a circular/(elliptic?) based cone approximation.

It''s not easy but can be done. With great efficiency since it''s caching ! The memory cost can be compared to the number of faces per patch.

Charles B from Paris

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I am interested in coding it for myself. Maybe would U mind to share that work in a C or C++ lib ?

Charles B from Paris

Share this post


Link to post
Share on other sites
Charles, thanks so much for your feedback. Your method of resolving the half spaces into the cone-shaped region sounds good, and the elliptical approximation is an interesting idea.

I found this article on hierarchical backface culling in which they create a "back" region by intersecting the half spaces of all the triangles, just as you''ve described.

I was planning to diverge from this slightly by taking into account occlusion information about a patch. A patch can be completely non-visible even when some of its triangles are not back-facing, because the edges of the patch can occlude interior triangles. This is illustrated in my 1D example above -- notice that if the camera is in the pink region on the left, just below the red line, then nearly half of the 8 lines are front-facing, yet the patch is not visible.

Anyway I haven''t decided whether to actually attempt this or to go the PVS route, but if I do, I''d be glad to share my results. Post here or email me at eundersan@mail.utexas.edu if you''re interested.

Share this post


Link to post
Share on other sites
1) My answer was clearly about backface culling. But in fact that is maybe not so useful for you ! . In the particular case of a terrain, rejection volumes are useful If your patches are small enough to be monotonuous - let's say north facing side only - thus invisible on the other side of the hill which is roughly half of the cases. Else if you have a creast in the patch - let's say with a north facing side and a south facing side - then the common rejection volume will be underground ! Underground camera ? Mining game ? LOL In this case you'd better forget the rejection volume for that patch !

2) Now your 1D example. Even if it's not pure backfacing but "backfacing + self occlusion" your 2D example - which could be extended to 3D almost like for backfacing - shows rejection volumes well under the ground again ! Thus the same critics.

3) The BSP+PVS solution is irrelevant too. How many triangles does your terrain contain at the maximum theorical precision, 1 million, 1 billion ? Probably too much to compute a BSP-PVS !

3) However this bad idea can become a good one with a little shift. Think bounding volume now. Your 2 red lines + 2 verticals is an accurate convex bounding shape of your 2D patch !

If the bounding volume of the patch is occluded then the patch is ! Eureka !

4) Test the following idea ! Precompute occluders and occludees.

Occludees are these bounding volumes of the patches. These bounding volumes will look like the lowest LOD of your patch but will contain the highest LOD which is rather accurate.

Occluders can be the successive cuts of your terrain in both x and y direction ! If your height map is n*n then you will have n+n occluders. Each occluder will be saved as a 2D line of segments, an outline ! Now let's look a bit deeper. This line will be too complex at the highest level of detail. Now figure out your 2D scheme but this time find 2 red lines under the outline (what we called a 2D patch in 2) ).

All right ! The memory cost for both occluders and occludees is relatively low ! Now can you guess how these data can be used in your ROAM drawing pipeline to efficiently cull patches.

Choose one of the +/-x or +/-y direction depending on your camera. Now parse the ROAM in this direction. Now process row by row. Each time project the new outline. Then merge it with the previous one. Then for each patch check if the convex projected outline of the occludee is hidden by the outline of your current occluder ! It's basically an intersection check of two segmented lines. And one is convex ! Great. It's worth trying it for a real time terrain ! It's a very efficient overlap reduction, an actual optimization !

e-mail me if you think it's a great idea. I need the same technology for my own 3D engine. But it's a lot of work to do. You need to be good at geometric algorithms 2D and 3D.


Edited by - Charles B on January 20, 2002 3:17:26 PM

Share this post


Link to post
Share on other sites
Charles, your row-by-row approach is interesting. It seems like your occluder line is going to quickly become highly segmented as you progressively merge in more of the stored lines. Maybe you could somehow decrease its LOD after each merge by combining segments.

Unfortunately for me, my ROAM implementation allows the triangles to split a little off-center (the idea is that this will allow them to fit the underlying heightmap better). Since my triangles do not stay in a neat grid of rows and columns, your row-by-row approach would probably not work for me.

So, for now, I am still leaning towards the patch back-facing approach. I found this article in which the author is computing occlusion similarly to what I have in mind.

Share this post


Link to post
Share on other sites