Jump to content
  • Advertisement
Sign in to follow this  
clb

View-independent "presorting" of triangles in a vertex buffer.

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

Hi,

When rendering a transparent object (in a single vertex buffer) on a GPU, depending on the ordering of the triangles inside the vertex buffer, you may get artifacts due to overlapping triangles being rendered in wrong order.

A solution to this is to treat the vertex buffer as dynamic, and to sort the contents per-frame (or use a BSP to produce a proper sorted order). Another solution is to use depth peeling. These both have performance limitations which in my case are unacceptable.

I've been toying with the idea of implementing a method referred to as "presorting", in which you sort the triangles in the vertex buffer in such an order, that rendering the triangles in that order give correct results view-independently. This kind of sort order does not always exist.

The difficulty with this method is that I'm very unsure how robust the mechanism would be, and if there might be some pathological (but perhaps common?) cases that are problematic. I've been trying to find some material about this method of presorting, to know if someone has investigated this method further. Unfortunately, I can't seem to find any good publications on it, perhaps my search skills are failing? Or perhaps this method is so obvious, that it is regarded as a folklore method?

The only sources I found is a video from Assembly 2002 talk on optimizing a software renderer by Paul Endresen, where he describes this method. This video is available at http://www.scene.org/file.php?file=%2Fresources%2Fseminars%2Fcode%2Fasm02_-_paul_lone_starr_endresen_-_software_3d_rendering.wmv&fileinfo .See time 16:34 - 26:00. At 24:00 he says "We didn't put too much effort in to finding out where to split". Does anyone know if there's some source where this kind of splitting method has been investigated?

At 24:47 a person from the audience refers to this algorithm having been implemented in "already in 1979 or something", "by a guy Schumacher or similar". Do you know of an academic paper or a book that describes this method?

Another source where this method is described can be found on this web page: http://www.mindcontrol.org/~hplus/graphics/sort-alpha.html . But this page also doesn't talk about its robustness, or about the possibility of splitting to reduce visual artifacts. I'd be interested in seeing some real case data, to see what kind of artifacts I might have expect.

Do you implement this method? How well does it work?

Share this post


Link to post
Share on other sites
Advertisement
In the game I'm working we do pre-calculated sorting for hair. We just sort each polygon based on its distance to the skull. But to support rendering backfaces, we actually double the geometry and the "backface" geometry is sorted backwards and rendered first. You'll still find some polygons drawn in the wrong order, but since they don't flicker when the camera angle changes they don't attract as much attention.

Share this post


Link to post
Share on other sites
Thanks for the reply. I guess it's true that since the sorting is not done per-frame, the visual appearance is the same, with the same artifacts, so it mightn't be that bad even if some small polys are rendered in wrong order.

Share this post


Link to post
Share on other sites
Some simple cases that will never work with presorting:

1. Glass house, or a car with windows
2. Particle systems
3. Foliage

#3 is particularly problematic, since it usually involves intersecting triangles. And no amount of triangle sorting can fix intersecting triangles...you have to use a technique that work on the pixel level.

Share this post


Link to post
Share on other sites
True, dynamic/deforming or animated objects cannot utilize presorting, since the object structure varies over time. For foliage and other cases involving intersecting triangles, a solution would be to split the intersecting triangles into separate one, but e.g. in the case of foliage this can be prohibitive, since it quickly grows the triangle counts and limits the number of foliage you can have.

I'm not sure what kind of glass house or car you are thinking, but I suspect presorting could very well be applied in both cases. A glass house (in the simplest case) is a convex object, which, just like a translucent sphere, can utilize presorting. I think it's a similar case with a car, since the windows will lie in a convex-like shape around the object, and there are no complicated concave configurations.

I think I'm going to go ahead and implement it. Hopefully it can also work in some more complicated cases.

Share this post


Link to post
Share on other sites
Nevermind on the glass house/car bit...now that I've actually read a bit about presorting I can see how those would work. :P

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!