Manually setting Z-order

[renton_django]

@Noldea

This is really only optimal when the # of inserts/z-changes <  log n  (which I think in most cases would be pretty rare - for my case anyways).

The real load on your function is the iterator that cycles through the list searching for the place it should be inserted. We have to assume the worst case of O(n) for each insertion. Using a divide and conquer technique using the size() of the list and having the iterator move around accordingly could reduce each insertion to O(log n).

The way it stands right now :

Sorting: O(n log n)
Inserting with this method: O(n * # of inserts/z-changes)  (Not even counting the complexity of removing a changed Drawable before re-insertion.)


Noldea, I am going to try and build off your idea this week and see if I can make it faster.

[NoIdea]

My code is not fully optimize because as you say, using dichotomy is faster. However, my solution should be optimal enough and is very easy to code. Furthermore, when using dichotomie, you may not want to use a list anymore because accessing elements without an iterator is much slower.
With list, I don't know which one is quickest.
However, if you use vector, it migth be worse because of moving all the elements.
There might be a better container and it depends on the uses but it would be best if you could compare performance.
I'm using this method in my game and I have No problems since I insert/change z-order quite rarely.

[Nexus]

You should really use a profiler and test different implementations instead of only making assumptions. Not least because the result may look different depending on the compiler or platform.

[renton_django]

True.

I plan on having a lot of stuff going on in my game, so I guess I tend to get a little overly-obsessed with optimization sometimes...

My z-order is based on the y-position value of my on-screen Drawables and I plan on having lots of Drawables on-screen at any given time, so I've got the potential for many z-order changes per frame. I tried out a list::sort() per frame, and it's actually causing very negligible performance loss, so I think I may stick with that for now.

I need to take your guys advice and remember that practice > theory

[wilbefast]

I think this may be very helpful

I'm horrified that you're even considering resorting the draw list every frame. You're insane  :shock:

You're basing the depth (Z) of each object on their y value, so it's unlikely to change much every frame. Maybe 15-20 per frame maximum. So why not pull each element out, shift it along left or right, and reinsert it again?

Hell, if the order doesn't change, you needn't even erase the element in the first place, and in practice 90% of the Drawables don't need to be moved each frame: you're effectively reinserting them back where they were before!

Here's some code that's technically O(n) in the worst case scenario, but in practice it generally works at O(1)

Code: [Select]

Drawable :: updatePosition()
{
   if(movement.y )
     Level::getInstance()->setDrawableDepth(this,position.y+movement.y)

   position+=movement;
}


and

Code: [Select]


Level::setDrawableDepth(Drawable* drawable, uint newDepth)
{
    short side = sign(newDepth - drawable->getDepth());

   if(!sign) //no need to move: no change in depth
      return;

   if(sign > 0)
   {
       Draw_container::iterator i = drawable->getDrawNode();

       if(i == draw_list.end()) //no need to move: highest depth
           return;

       i++; //'i' now points to element to this right of 'visible'

       if((*i)->getDepth()>=newDepth) //no need to move: already sorted
           return;

      i++;
      static bool added;
      added = false;
      while(!added && i != draw_list.end())
      {
         if((*i)->getDepth()>=newDepth)
        {
             draw_list.insert(i,visible); //add 'visible' in front of i
             added = true;
             i-- //move i back to point at 'visible'
         }
         else
             i++;
      }
      if(!added) //i == draw_list.end()
      {
         draw_list.push_back(visible);
         i = draw_list.end(); i--; //better safe than sorry ;-)
      }
   }
   
   /* similar sort of thing for i < 0 */

   //remember to remove the original reference to 'visible'
   draw_list.erase(visible->getDrawNode());
   //reset the draw node
   visible->setDrawNode(i);
}

That's ~pseudocode written from memory, but PM me if you want to look at what I actually wrote. The point is that it works, and in stress tests performs a lot better than reinsertion from the beginning (eg - calling the function used to create the draw list in the first place).

[nfries88]

Laurent, I believe that OpenGL has had a depth buffer (which provides the requested functionality) since version 1.1 at the very latest; which any modern system (which, unless you intend to port SFML to archaic systems in the future, is all of the ones supported by SFML) will certainly support.

As for the thread starter, if maintaining the scaling/rotation heirarchy is important to you, SFML does provide sf::Drawable::transformToLocal to easily allow you to do the same thing. According to the documentation, this was added in SFML 1.4.