Sign in to follow this  
mictian

sorting grass for alpha blending

Recommended Posts

I am trying to render a bunch of meshes with alpha-blended grass textures on them. I know I have to render them back to front for a proper effect, but what is the best way to do this? I guess if I use some n^2 sort I might be able to get a better runtime by exploiting temporal coherence. However I had a different idea that I want some feedback on. I was thinking of doing a radix based sort, on the squared distance from viewpoint to the grass mesh. But instead of having each radix "bucket" be the same size, I would have them more fine-grained near the user and larger in the distance, like some sort of logarthmic scale. Let me know what you think of this idea, or if i sould just go ahead with some n^2 crapola. Rob edit: drunk typing

Share this post


Link to post
Share on other sites
Alternativly, cheat and just use alpha testing. Then you don't need any sorting (or blending) so you can have much denser grass. With a suitable alpha test value you still get nice irregular edges.

Share this post


Link to post
Share on other sites
just to extend the sort talk, n^2 is the worse algorithm you can think of for general use, use mergesort or quicksort (better) which has O(n*log(n)) as complexity, making theme slaughter insertionsort O(n^2). (the only reason insertionsort exists is because of the O(n) best case for already sorted lists)

Share this post


Link to post
Share on other sites
Hi there, Orangytang!

Could you perhaps explain a little more about alpha testing...?

Do I have to disable glBlend first?

p.s a sample code would be very nice. :D



btw, I tried using alpha testing before, but it still needed sorting... :(

Share this post


Link to post
Share on other sites
Quote:
Original post by Rasmadrakbtw, I tried using alpha testing before, but it still needed sorting... :(


The point of alpha testing is to not require sorting... and according to nvidia and the people who tried it, it works.

Share this post


Link to post
Share on other sites
I haven't used alpha testing, so my info is limited, but I am able to give you some pointers from NeHe lesson 32.

Instead of
glEnable(GL_BLEND);
you can use

glAlphaFunc(GL_GREATER,0.1f);
glEnable(GL_ALPHA_TEST);
and you don't need to sort your grass meshes. However, you can only blend using completely transparent pixels and completely opaque.
How you can get irregular edges by playing with the alpha value I don't know, maybe OrangyTang can help you with that.

Share this post


Link to post
Share on other sites
Sorry I said the wrong name.
http://developer.nvidia.com/object/Interactive_Order_Transparency.html
There you have true alpha transparency without sorting at all.

However, using the Alpha Test you will still get artifacts, one way or the other, either the outer edges might get cut away (more or less), or you will see through (more or less), will get the worst away.

However, doing sorting or the nvidia-documentation is the only way without sorting that I've ever heard of (and likely there is no other to speak of as the nvidia solution has been brought up).

So it's just too choose, I'm guessing the nvidia solution is overkill for most applications.

Share this post


Link to post
Share on other sites
Thanks guys, I have never heard of the alpha test before, I will give this a go and see what results I can get.

Thanks again.

rob

Share this post


Link to post
Share on other sites
I would stick with alpha testing and alpha coverage (which is multisampled alpha testing, http://humus.ca/index.php?page=3D).

Share this post


Link to post
Share on other sites
There are a couple of other possibilities depending on how you are doing your grass.

One trick is to have about 6-12 different index lists, each with the grass sorted in a different order, along a different world space xz vector. When rendering the grass, choose the one that most matches the camera's view vector.

If you are creating grass around the player, you could create it in radial bands, with each band drawn from furthest to nearest.

I should point out that these two approaches would allow for alpha blending, and not simply alpha testing.

Share this post


Link to post
Share on other sites
Quote:
(the only reason insertionsort exists is because of the O(n) best case for already sorted lists)


Which is really handy for sorting objects while rendering because of the temporal coherence. Having to do a FULL logn*n sort vs doing about an n sort every frame isn't as good as it could be.

Share this post


Link to post
Share on other sites
Quote:
Original post by Cypher19
Quote:
(the only reason insertionsort exists is because of the O(n) best case for already sorted lists)


Which is really handy for sorting objects while rendering because of the temporal coherence. Having to do a FULL logn*n sort vs doing about an n sort every frame isn't as good as it could be.


I'm not sure if I misunderstand you, or you misunderstood me...

But, if insertionsort is gonna be any faster than Qsort for large sets of polygons (even for small), the list is going to be SORTED, very very SORTED, in such a way that there is a max of 5-6 malplaced elements, otherwise insertionsort will go waaaaaaay beyond quicksort in time.

Share this post


Link to post
Share on other sites
Hmm considering you still have a circle of grass around the camera, what do you do if the camera moves and new chunks have to be added? How can that done efficiently, without having to check each grass chunk again whether its still in range? New grass-chunks may also create somewhat large memory movements which are a performance killer as well.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dtag
Hmm considering you still have a circle of grass around the camera, what do you do if the camera moves and new chunks have to be added? How can that done efficiently, without having to check each grass chunk again whether its still in range? New grass-chunks may also create somewhat large memory movements which are a performance killer as well.


Wouldn't it just be possible to have some algorithm for drawing grass, e.g., drawing grass with one unit spacing in both directions (x and y), in this way you could easily determine what grass needs to be added, what's to be removed and easily have them all sorted (as you could create the grass in the right order easily).

(Of course it doesn't need to be lines, but the same applies, but with variation)

Just a thought

EDIT: now I mean like really dense gras, not the stripes seen in many games, those shouldn't be too advanced.

Share this post


Link to post
Share on other sites
My guess is that is going to look too uniform to look natural. When you look along the x / y axis then, you are going to see all grass in a line etc..

Share this post


Link to post
Share on other sites
Quote:
Original post by Dtag
My guess is that is going to look too uniform to look natural. When you look along the x / y axis then, you are going to see all grass in a line etc..


That's what I meant with variations, even if you draw them all in lines you can have variations within the box so that they can range from e.g. -0.8 to 0.8, as having them all drawn in lines will make them evenly distributed too.

Share this post


Link to post
Share on other sites
my original idea was to simply bucket sort the grass meshes based on some log of their distance to the camera. This way I would get more "buckets" up close, and fewer farther back in the distance, having the effect that sorting is more fine grained where it is needed. This would be O(n).

Share this post


Link to post
Share on other sites
Quote:
Original post by mictian
my original idea was to simply bucket sort the grass meshes based on some log of their distance to the camera. This way I would get more "buckets" up close, and fewer farther back in the distance, having the effect that sorting is more fine grained where it is needed. This would be O(n).


This should work well enough. Download SpeedTree to see what the alpha test version looks like. The main problem I have with it is the poor visual quality when the grass is in front of the sky (i.e. when looking at the top of a hill or ridge). When drawing grass in front of grass, it looks fine.

I have run a GPU performance test on alpha test vs. alpha blend, and the alpha test ran slower on the GPU (Radeon 9600). This happened even when rendering front-to-back, which should've been fast because it eliminates pixel overdraw. In any case, feel free to run your own tests and use whichever version fits best with your application (depending on how heavily you're hitting the CPU vs. the GPU).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this