Sort order of transparent textures

Problems with Canvas, OpenGL, etc...

Sort order of transparent textures

Postby tiggr » Mon Jun 28, 2010 4:38 pm

Hi,

I'm trying to wrap my head around getting transparent textures to work properly (or figure out what I am doing wrong currently).
I am using a simple test where I bind a transparent texture to a moving quad (in z), and then I bind it to another quad and put this quad behind (z is lower on second image). This _should_ result in the second image being shown under the other closer one. It works like expected when I render them in order back to front (as expected).

I use depth testing and when not using transparent textures this works, do I really have to control the rendering order to get this to work? (sorting the scene before drawing it?)

Regards
/David
tiggr
Freshman
Freshman
 
Posts: 3
Joined: Mon Jun 21, 2010 8:30 am

Top

Re: Sort order of transparent textures

Postby MichaelEGR » Mon Jun 28, 2010 6:28 pm

tiggr wrote:Hi,
I use depth testing and when not using transparent textures this works, do I really have to control the rendering order to get this to work? (sorting the scene before drawing it?)


It all depends on what you want for results. A quick and dirty approach is to turn off depth testing and use additive blending and not care about order. That only works for some effects and purposes; sometimes smoke / particle effects.

Otherwise yeah order matters for all non-additive transparency. The standard approach is the "painter's algorithm" where the scene is drawn back to front. A particularly helpful sort algorithm is the radix sort. You do have to sort the objects based on the current observer position/direction.
Founder & Principal Architect; EGR Software LLC
http://www.typhonrt.org
http://www.egrsoftware.com
User avatar
MichaelEGR
Senior Developer
Senior Developer
 
Posts: 147
Joined: Thu Jan 21, 2010 5:30 am
Location: San Francisco, CA

Re: Sort order of transparent textures

Postby tiggr » Mon Jun 28, 2010 9:15 pm

Hi,

Ok, that's what I expected to hear, thanks for the confirmation. As a follow-up, what kind of data structure would you use the radix sort in? I am thinking scenegraphs and stuff like that, never used one but gather it would be pretty straight forward? Any good resources for this?

Also, slightly OT, if doing animations on these transparent sprites, what is the best way (small sprites, many frames, few total sprites) to achieve this? I was thinking of using larger sprite-sheets and use glSubTexImage2D to select which region to fetch from for each new frame of animation.
Is this the best practise to do this? In terms of memory/fps that is.

Regards
/David
tiggr
Freshman
Freshman
 
Posts: 3
Joined: Mon Jun 21, 2010 8:30 am

Re: Sort order of transparent textures

Postby impi » Fri Jul 30, 2010 11:11 am

Sorting all objects with the normal Collections.sort is not so bad as you may think, i use this for my game and its pretty fast. Only think about datastructure and radix sort stuff, if you have problems with your performance at this (which i don't think)

Make sure you profile your code to determine performance bottlenecks and dont pre optimize so hardly
impi
Developer
Developer
 
Posts: 29
Joined: Wed Apr 28, 2010 11:17 pm

Re: Sort order of transparent textures

Postby MichaelEGR » Tue Aug 03, 2010 1:58 pm

impi wrote:Sorting all objects with the normal Collections.sort is not so bad as you may think, i use this for my game and its pretty fast. Only think about datastructure and radix sort stuff, if you have problems with your performance at this (which i don't think) Make sure you profile your code to determine performance bottlenecks and dont pre optimize so hardly


I'm not sure what kind of games / real time apps you create, but this is actually really bad advice. If you profile your code as you suggest you'll see all sorts of nastiness that one Collections.sort call introduces from a ton of background garbage to recursive method invocation and on...

First off you are using a base Java collection List<T> to store your data, and unless it's an ArrayList and you don't use iterators you're dealing with lots of background garbage just with throw away iterators alone especially in a tight loop when accessing your data.

Lets quickly examine Collections.sort as it's gets much worse. The Arrays and Collections sort methods are general purpose!

Didn't use code formating so color highlighting works; below is Collections.sort:

public static <T extends Comparable<? super T>> void sort(List<T> list)
{
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j = 0; j < a.length; j++)
{
i.next();
i.set((T) a[j]);
}
}

- The 1st major gotcha is the toArray copy of the List data.
- Arrays.sort -> it's a recursive implementation of mergesort that uses clone. Code following below.
- list.listiterator() creates a throw away iterator
- a.length is a method call
- additional method overhead of next/set calls

Below is Arrays.sort:

public static void sort(Object[] a)
{
Object[] aux = (Object[])a.clone();
mergeSort(aux, a, 0, a.length, 0);
}

Then of course take a look at "mergeSort" and the recursive nature of the algorithm; recursive method invocation is a big no no for performance.

Sorting I'm afraid is one area where you want to choose a specific implementation that is right for the purpose especially if you want to create a glitch free experience. If you have GC issues in your game/app it could easily come from one Collections.sort call in a tight loop. Also another distinction is that radix sort allows one to determine a secondary sort criteria on the fly. This could be the texture ID or in the case of the painters algorithm the distance to the object. One is sorting these secondary data points and not the objects themselves. Radix sort allows you to get a sorted indice array back to index into the data structure holding objects to render; preferably it's just a vanilla array and not a Collection.

Check out this for a RadixSort implementation that I've used successfully for quite some time:
http://spgl.cvs.sourceforge.net/viewvc/ ... lgorithms/

I made further modifications myself, but that is a good start for an optimal sorting algorithm for sorting texture IDs and potentially integer distances / transparent objects for the painters algorithm.
Founder & Principal Architect; EGR Software LLC
http://www.typhonrt.org
http://www.egrsoftware.com
User avatar
MichaelEGR
Senior Developer
Senior Developer
 
Posts: 147
Joined: Thu Jan 21, 2010 5:30 am
Location: San Francisco, CA

Top

Return to Android 2D/3D Graphics - OpenGL Problems

Who is online

Users browsing this forum: No registered users and 2 guests