Alpha correction

Hi,
When looking through Alphablended Objects you obviously only see the ones draw before.
I used the following code to sort my objects according to the eye. But this method is really slow.
Could someone tell me a faster way to sorten the objects distance to the eye and additional tips to speed it up. (Maybe BSP is the solution. Tell me if theres no other sufficent solution).


	for(int i2 = 0; i2 < numobjects; i2++)
	{
		//Object Distance to Camera
		if(AlphaBlendCorrected)
		{
		    objdist[i2] = Dist(player.x, player.y, player.z, objx[i2], objy[i2], objz[i2]);
			if(!alphablended[objDefinition[i2]])
			{
				if(objdist[i2] < sight+1)
				{
				    objdist[i2] = sight-1;
				}
			}
		}
	}
	if(AlphaBlendCorrected)
	{
        for(int o = sight-alphacorrection; o > -1; o-=alphacorrection+1)
		{
			for(int i3 = 0; i3 < numobjects; i3++)
			{
				if(objdist[i3] < o+2+alphacorrection && objdist[i3] > o-2-alphacorrection)
				{
					DrawObject(objx[i3], objz[i3]);					}
				}
			}
		}
	}

The best solution is having a structure that already gives you all the objects sorted.

A bsp is one, you can also use an octree or a quadtree. An octree or a quadtree are definitly simpler to implement than a bsp, though you will still have to sort the objects in each node when you will go through it. But sorting 3-4 objects at a time is much faster than sorting 100.

Pre defined is a good idea, but what about when I have objects that are constantly moving?

If you want to draw dynamic objects correctly when they’re alphablended, you’ll have to sort them.

  1. Sort the list of objects, then draw the them in order (rather than scanning the list hundreds?, thousands?, millions? of times).
  2. Keep the sorted list between frames and recompute the distances and resort the list as often as necessary. Pick the fastest sort for data that is already mostly sorted.

With an octree or a quadtree it is quite simple, you only need to move your object from node to node.

  1. Keep the sorted list between frames and recompute the distances and resort the list as often as necessary. Pick the fastest sort for data that is already mostly sorted

And AFAIK, that would be natural mergesort.

  • Alex

Thanks everybody. I think I get the point.
Does one of you know a website with a good example octree

And AFAIK, that would be natural mergesort.

Mergesort is always O(n*log n), even for sorted lists. For sorted lists, bubble- and insertion-sort is O(n). So as the list grows, bubble- and insertion-sort is faster than mergesort.

But in the end, you should always try it out, and pick the fastest one.

Mergesort is always O(n*log n), even for sorted lists. For sorted lists, bubble- and insertion-sort is O(n). So as the list grows, bubble- and insertion-sort is faster than mergesort.

Yes, and this is why I recommended natural mergesort. This is a non-recursive variant of mergesort, that performs O(n) on already sorted lists, with a worst case behaviour of O(n log2 n) on non-sorted ones.

  • Alex

It is sometimes worth the effort to do a multithread insertion sort that can run concurrent with the traversal of rendering structures etc. In a scene graph you can “post” the data during traversal to an insertion sort. After the traversal much data is already sorted and therefor can be processed faster. This is true when the scene graph traversal needs syncronisation with external updates and therefor enters some mutexes etc. or when you have got multiprocessor capabilities on your HW.

It is also advisable to save the previous sort that can be used to update occluders that can eliminate graphics in the next pass to be inserted into the sort…