sorting grass for alpha blending

Started by
16 comments, last by s_p_oneil 18 years, 10 months ago
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.
Advertisement
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.


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


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


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).
¿We Create World?
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).

This topic is closed to new replies.

Advertisement