SFML community forums

General => Feature requests => Topic started by: Imbue on November 22, 2008, 05:51:36 am

Title: Manually setting Z-order
Post by: Imbue on November 22, 2008, 05:51:36 am
Will SFML ever support a real Z-order system?

Since SFML uses OpenGL it seems like this should be an easy thing to add.

Perhaps add a method to sf::Drawable like SetZ(float z)? If it's left at zero then the Z order is determined by the render order, otherwise it's predetermined by z.

Seems like a simple enough thing, it would really help in some situations.

Thanks.
Title: Re: Manually setting Z-order
Post by: Wizzard on November 22, 2008, 07:29:56 am
Quote from: "Imbue"
Seems like a simple enough thing, it would really help in some situations.

Giving some examples would really help your cause.
Title: Manually setting Z-order
Post by: Imbue on November 22, 2008, 09:19:54 am
Sure, here's my current situation:

Drawables have a nice feature where any calls to Render inside of another Render inherit their parent's transformations. This make Drawables nice for creating hierarchies for character animation. For example, if you have a "body" object owning an "arm" object (which in turn owns a "hand" object), SFML can propagate any changes to the body's position down to the arm (Internally I believe this is just using OpenGL's matrix stack). The biggest problem of doing it that way is that it makes controlling draw order (and therefor Z order) difficult.

If you have any suggestions on how to otherwise accomplish this, please tell me.

On an only slightly related topic, why is sf::Drawable::GetMatrix() protected and not public? I feel that Matrices are a higher level concept and should be allowed for more use by the end user. The alternative is a call to GetPosition(), GetScale(), GetCenter(), and GetRotation(). Doesn't that seem like a lower level interface with less encapsulation?

BTW, I'm a noob at all this, so I'm definitely open to any suggestions.

Thanks. :D
Title: Manually setting Z-order
Post by: bullno1 on November 22, 2008, 09:50:52 am
Z ordering is a "high level" concept. SFML is quite low-level. There is no "scenegraph" structure. You need to manually call window.Draw() on your Drawables so there's no way SFML can determine the order of drawing. I think this is a design decision, the author wants you to do it yourself and implement it the way you like. Thanks to that, in my engine, I can implement layers of sprite and different methods of ordering sprite within the same layer(based on z or based on y for 2D RPGs) .

Regarding the matrix thing, I have requested this before. For now, you can...
Edit the header  8) . There's no need to recompile. I believe that protected or private modifier only decides whether a method is "exported". Members are always exported or else how can the compiler know how to allocate memory when we create new objects?

Quote
If you have any suggestions on how to otherwise accomplish this, please tell me.

Order the list of sprite yourself. std::sort or std::list::sort should do the trick.
Title: Manually setting Z-order
Post by: Imbue on November 22, 2008, 10:26:56 am
Quote from: "bullno1"
Quote
If you have any suggestions on how to otherwise accomplish this, please tell me.

Order the list of sprite yourself. std::sort or std::list::sort should do the trick.
Thanks, for you suggestion, but I think you missed the point of my example. SFML does give a "scene graph" like quality, and you can have complicated object hierarchies by using recursive sf::Drawable::Render calls. This nearly forces an arbitrary Z ordering, though.

If I instead throw my objects in a sorted container (like std::set) I lose this scene graph quality and would have to re-implement it myself. Honestly, I may and do just that. If I hack GetMatrix() to be public, it shouldn't be too tough to make a reasonable 2d scene graph.
Title: Manually setting Z-order
Post by: Laurent on November 22, 2008, 11:41:30 am
You mean you have a hierarchy of drawables, but this hierarchy defines an incorrect order of drawing ? Can you tell us more about this situation ?
Title: Manually setting Z-order
Post by: bullno1 on November 22, 2008, 01:29:48 pm
Quote
You mean you have a hierarchy of drawables, but this hierarchy defines an incorrect order of drawing ? Can you tell us more about this situation ?


I think he means that he create his own Drawable class which has children. In the render method of the parent, he calls the children's Render method. The children Render methods re-use the parent's transformation state and this enables a relative coordinate system and a hierarchy. However, by doing this, he cannot control the z-order since the children are always drawn before or after the parents. And the render order of parents also decides the order of their children
Title: Manually setting Z-order
Post by: Laurent on November 22, 2008, 01:47:01 pm
That's exactly why I'm asking this question. Usually, one of the benefits of having a hierarchy is that it also defines a valid order of traversal for drawing.
Title: Manually setting Z-order
Post by: Imbue on November 22, 2008, 06:59:27 pm
Sure, say I'm looking at a side view of a person. This person's body has a left leg and a right leg. Since this is a side view, on leg should be drawn before (under - obstructed by) the body, and one leg should be drawn after (above) the body. That's still doable, but means the hierarchy is transversed several times and the code becomes messy.

So consider a tree like this for a character's lower body facing right (draw order parenthesized):
Code: [Select]

          body(3)
        /      \
left leg(2)    right leg(4)
left foot(1)   right foot(5)


So body needs to draw one leg, itself, and then the other leg. One leg draws it's child first, one leg draws it's child after. With a more complicated hierarchy, draw may have to be called multiple times on the some member. In a real situation I'd have the legs split, and also arms, and a head to deal with, at the very least.

More to the point, I'd like my character animation to simply read some rules from an XML file and do the right thing. I suppose the current situation could still be made to work OK, but it would be much easier to specify a Z order to SFML and make the transversal once.

I know that with SMFL the way it is now, I can draw anything. If you're going for an absolute minimal approach, I can respect that and work around it. I just think it would be cool to give the end user a choice of draw order, and passing a Z value to OpenGL. I suppose if you want to implement software rendering in the future, then Z order may be a bad thing.

Thanks.
Title: Manually setting Z-order
Post by: Imbue on November 22, 2008, 07:00:53 pm
BTW, Laurent, whats the rational for hiding GetMatrix()?

Thanks.
Title: Manually setting Z-order
Post by: Laurent on November 23, 2008, 12:03:18 am
Matrices are usually hard to understand and to manipulate for beginners. I prefer providing helper functions which modify internal matrices indirectly.

Moreover, matrices initially didn't exist. They're just an implementation optimization; one day I might end up removing them for any reason. So they should never appear in the public interface.
Title: Manually setting Z-order
Post by: Imbue on March 21, 2009, 04:35:55 am
I'm working on my game again after a hiatus with another project.

This Z-ordering is still an issue for me. What is the best way to do what I'm looking for? If I draw in order, it seems that I'll have to forgo using nested Render() calls, which would be a shame. Any advice would be appreciated.

Surely other people have this problem. There must be a reasonable solution.

Why doesn't SFML allow arbitrary Z-ordering, though? It seems like it would be free, performance wise.

Thanks.
Title: Manually setting Z-order
Post by: Laurent on March 21, 2009, 09:44:21 am
Quote
Why doesn't SFML allow arbitrary Z-ordering, though? It seems like it would be free, performance wise.

SFML can't delay drawing operations in order to reorder them, and can't use Z-Buffer because it might not be available on some platforms. So, SFML can't do Z-ordering :)
Title: Manually setting Z-order
Post by: Imbue on March 21, 2009, 10:13:57 am
Laurent, thanks for the definitive answer.

I'm still looking for advice then, from anyone, on workarounds. Should I implement my own scene graph? Are there decent libraries out there for that already?
Title: Manually setting Z-order
Post by: Hiura on March 21, 2009, 11:03:07 am
Why not using a sprite manager (or something like that) to manage your Z-order ?
Title: Manually setting Z-order
Post by: Nexus on March 21, 2009, 02:09:39 pm
If there is any reason not to draw the sprites directly in the order you want them to be placed on the screen, you can have a sprite manager class which holds a container of sprites that can be sorted. The standard container std::priority_queue might be an option.
Title: Manually setting Z-order
Post by: Imbue on March 21, 2009, 10:12:02 pm
Sure, storing all the sprites and sorting by Z-order is probably best. I could probably just keep pointers to them in a std::set<> sorted by Z-order.

The downside there, is that I'd have to control the movement manually of all the sprites. For example, I'd have to manually set the position of a "foot" sprite when the "leg" sprite moves. The best way I see to do that is to override GetMatrix() and make it public, then just multiply the matrices together. However, if matrices might disappear in future versions, that scares me.

My other option is to treat SFML as just a pure rendering library, and not use it to store any position information. The would mean simply creating a new sprite every frame. It seems like a shame to duplicate all that though, and it might run slightly slower.

Hmmmm.

Thanks.
Title: Manually setting Z-order
Post by: Nexus on March 22, 2009, 02:41:13 pm
Quote from: "Imbue"
The downside there, is that I'd have to control the movement manually of all the sprites. For example, I'd have to manually set the position of a "foot" sprite when the "leg" sprite moves.
I don't really understand the connection with Z-order... You'd have to move a "foot" anyway after moving the "leg", wouldn't you? And besides, you could automatize that...

Quote from: "Imbue"
My other option is to treat SFML as just a pure rendering library, and not use it to store any position information. The would mean simply creating a new sprite every frame. It seems like a shame to duplicate all that though, and it might run slightly slower.
Separating logic from graphics is a good idea. There are different approaches: One of them is to recreate sprites every frame. Alternatively, you can hold sprites in a associative container, change for every object only a few properties like position, rotation and redraw the sprites every frame.
Title: Manually setting Z-order
Post by: Imbue on March 22, 2009, 08:18:57 pm
Quote from: "Nexus"
Quote from: "Imbue"
The downside there, is that I'd have to control the movement manually of all the sprites. For example, I'd have to manually set the position of a "foot" sprite when the "leg" sprite moves.
I don't really understand the connection with Z-order... You'd have to move a "foot" anyway after moving the "leg", wouldn't you? And besides, you could automatize that...
In SFML, if you draw a sprite inside of another Render() call, it will inherit its parent's properties (scale, position, rotation). So basically, just by having one object own a sprite as a member, that is taken care of automatically, provided you don't care too much about Z-order.

That is all calculated on the graphics card, and it works the same way with 3D models. You can even nest many levels deep, like rotating a shoulder rotates an arm which rotates a forearm which rotates a hand... all automatically.

So now it looks like I'll have a person class that holds all of its body parts, instead of a person class only holding a torso (which in turn holds arms and legs, etc).
Title: Manually setting Z-order
Post by: drakelord on May 30, 2009, 08:53:22 am
Another option would be to derive a new class from the sprite class, add in your own float for z order, then have a map or some sort of list of sprites that are sorted by z order and drawn in that order.
Title: Manually setting Z-order
Post by: TheMiss on May 02, 2010, 02:40:05 pm
Oh! come on, I manually sort z order (sf::Sprite of course) by std::list.sort().

It really hurts performance!

 :?

Are there any way to improve it?
Title: Manually setting Z-order
Post by: gsaurus on May 02, 2010, 11:24:25 pm
Quote from: "TheMiss"
Oh! come on, I manually sort z order (sf::Sprite of course) by std::list.sort().

It really hurts performance!

 :?

Are there any way to improve it?

I said it more than once on other threads, use a std::multiset, it keeps all elements sorted.
When you update the z order of a sprite, remove that sprite from the set and add it again. This way it "sorts" that sprite only, doesn't have to sort the whole container.
Title: Manually setting Z-order
Post by: TheMiss on May 03, 2010, 09:10:58 am
Oh thanks!

I found the thread you said about.

How I skipped it over?
Title: Manually setting Z-order
Post by: Xorlium on July 20, 2010, 06:53:18 pm
But then if you modify the z-value of a sprite, don't you invalidate the multi-set?
Title: Manually setting Z-order
Post by: CBenni::O on July 20, 2010, 10:21:31 pm
Or you can use a Z-Buffer if you have lots of Sprites ;)

OGL should suport this...

bye, CBenni::O
Title: Manually setting Z-order
Post by: l0calh05t on July 21, 2010, 07:53:02 am
Quote from: "TheMiss"
Oh! come on, I manually sort z order (sf::Sprite of course) by std::list.sort().

It really hurts performance!

 :?

Are there any way to improve it?


use a floating point radix sort?
Title: Manually setting Z-order
Post by: namuol on September 21, 2010, 05:56:16 pm
Quote from: "Xorlium"
But then if you modify the z-value of a sprite, don't you invalidate the multi-set?


The best solution would be to use accessor/mutator functions which automatically sort the list if the z value has changed.

Here's a Z-sorted sprite example (psuedo-C++):

Code: [Select]

class ZSprite : public sf::Sprite
{
  private:
    double z;
    std::list<ZSprite*>* list;
   
  public:
    ZSprite([[Sprite args...]],
                double z=0.0,
                std::list<ZSprite*>* list)
    {
        this->z = z;
        this->list = list;
    }

    double GetZ() { return z; }

    void SetZ(double value)
    {
        if( z != value )
        {
            z = value;
            [[sort your list here...]]
        }
    }
};
Title: Manually setting Z-order
Post by: Laurent on September 21, 2010, 08:17:03 pm
There's no need to sort the list every time a sprite is modified, just do it once before drawing. Of course it depends if you have mostly static sprites or dynamic ones, but at least this strategy is consistent, you know that you have no more than 1 sort per frame.
Title: Manually setting Z-order
Post by: renton_django on October 05, 2010, 08:08:11 pm
I have been having similar problems to the previous posters.

I think most people feel that a std::list sort (O(n log n) is too expensive to be running each frame if it doesn't have to be.

I still have to evaluate the std::multiset insertion/deletion method.
Title: Manually setting Z-order
Post by: NoIdea on October 05, 2010, 08:47:04 pm
Personnaly, I don't use std::sort or std:::lists::sort.
Since elements are always inserted/changed z-order/... less than once per frame, the best performance solution is :
-each_time you add an element, you put it in the right place (insertion).
-each time you change an element's Z-order, you put it in the right place.

=>Your elements are always sorted even if you never sort them all

=> you can delete a Drawable without sorting anything.
=>You only use a bit of performance when you add/change a element.
=> to draw, just create an iterator and draw them all.

Pseudo code :

Code: [Select]
Class::inset_new(Drawable*d, unsigned plan)
    std::list<std::pair<Drawable*, unsigned int> >::iterator it;
    for(it=mylist.begin();it!=mylist.end();it++)
        if(it->second>plan)
            break;
    mylist.insert(std::make_pair(d,plan));


I let you guess the slution for changing Z-order.
This code is Pseudo code because I will not assure it will work (didn't check nor reread myself).
Title: Manually setting Z-order
Post by: renton_django on October 05, 2010, 09:43:57 pm
@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.
Title: Manually setting Z-order
Post by: NoIdea on October 06, 2010, 08:29:53 pm
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.
Title: Manually setting Z-order
Post by: Nexus on October 06, 2010, 08:39:32 pm
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.
Title: Manually setting Z-order
Post by: renton_django on October 06, 2010, 11:14:24 pm
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
Title: Manually setting Z-order
Post by: wilbefast on October 14, 2010, 10:29:27 pm
I think this may be very helpful (http://wilbefast.com/2010/10/11/tricky-tiles/)

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).
Title: Manually setting Z-order
Post by: nfries88 on October 27, 2010, 09:15:29 pm
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.