Pixi.js: Z-Indexing

[bchevalier]

Hello,
I was wondering what Pixi-people thought about having the possibility to specify z-index for elements within containers.

There is a small project I work on to test various components among which is a custom version of Pixi with a data-structure that efficiently handle z-indexed children in the containers. It allows for much faster sprite removal than a simple array (Array.splice is slow) and it allows me to very easily place my elements in the scene with a smaller number of containers to hold my sprites, leading to smaller rendering overhead.

The problem is that it is incompatible with the current API. I would like to know what is the position of the Pixi-leaders on the matter?

[GoodBoyDigital]

Sound neat @bchevalier !

Anymore info you have on the data structure would be ace. Im sure there is a way it could be done.

Thanks!

[cvissie]

Funny enough I haven't found much use for this. At first I was also quite irritated coming from a late Flex background where I could easily set depth.

With HTML5 I find that I try to keep my scenes as little complex as possible for mobile sake.

And in doing so I have the following patch/addon in my code for the odd scenario where I require to set the depth.

  /**
   * This addon adds depth property to PIXI.DisplayObject and sortChildrenByDepth to PIXI.Container
   *
   */
  (function () {
    PIXI.DisplayObject.prototype.depth = 0;

    PIXI.Container.prototype.sortChildrenByDepth = function () {
      this.children.mergeSort(sortByDepth);
    };

    function sortByDepth(a, b) {
      var left = a.depth;
      var right = b.depth;
      if (left < right)
        return -1;
      if (left == right)
        return 0;
      else
        return 1;
    }
  })();

And the following Array prototype.

  "use strict";

  var p = Array.prototype;

  p.mergeSort = mergeSort;
  p.bubbleSort = bubbleSort;
  p.shuffle = shuffle;
  p.swap = swap;

  function shuffle() {
    var o = this;
    for (var j, x, i = o.length; i; j = Math.floor(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
  }

  function swap(a, b) {
    var o = this;
    var temp = o[a];
    o[a] = o[b];
    o[b] = temp;
    return o;
  }

  function bubbleSort(compare) {
    var a = this;
    var swapped;
    do
    {
      swapped = false;
      for (var i = 0; i < a.length - 1; i++) {
        if (compare(a[i], a[i + 1]) > 0) {
          var temp = a[i];
          a[i] = a[i + 1];
          a[i + 1] = temp;
          swapped = true;
        }
      }
    } while (swapped);
  }

  function mergeSort(compare) {
    var items = this;

    if (items.length < 2) {
      return items;
    }

    var middle = Math.floor(items.length / 2),
      left = items.slice(0, middle),
      right = items.slice(middle),
      params = merge(left.mergeSort(compare), right.mergeSort(compare), compare);

    // Add the arguments to replace everything between 0 and last item in the array
    params.unshift(0, items.length);
    items.splice.apply(items, params);
    return items;
  }

  function merge(left, right, compare) {
    var result = [],
      il = 0,
      ir = 0;

    while (il < left.length && ir < right.length) {
      if (compare(left[il], right[ir]) < 0) {
        result.push(left[il++]);
      } else {
        result.push(right[ir++]);
      }
    }

    return result.concat(left.slice(il)).concat(right.slice(ir));
  }

This way I can call container.sortByDepth() whenever I set a child's depth parameter.

Obviously this becomes unfeasible very quickly the moment you have depth/z-index changes often.

BUT. As a whole I'm quite in favor of having it managed internally by PIXI :) As long as it's fast e.g. log(n) addition and removal.

[bchevalier]

The data-structure I use is a doubly linked list (I have used it in several projects already).
It's in O(n) for addition (amortized O(1) if addition at the beginning or the end of the list) and in O(1) for removal. Since an array would be O(1) for addition and O(n) for removal, it seems pretty similar in terms of performance, but actually the O(n) operation for removing an element in an array is much slower than the O(n) for adding an element in the doubly linked list.

This data-structure is also very efficient at repositioning elements whose z-index change only slightly, for instance in 3D-Iso games the characters can move forward and backward.

For large amount of elements I have also implemented an avl tree(which I also used in several projects) that is in O(log(n)) for both addition and removal. However I mainly develop mobile games and I usually had to handle small amounts of elements and therefore found that the doubly list was more efficient. Also, it would take longer (in terms of execution time) to reposition elements whose z-index changes only slightly in a tree than in a list. I would also need to change the implementation of the tree to allow iterating quickly through elements in order (which is possible and not too much work).

[englercj]

We used to use a linked list instead of an array, but the reality is that you iterate over children way more often than you change their contents. Because of that we switched back to an array for maximum iteration performance. You may change some children every few frames, we we have to iterate every element of every container, every single frame. Iteration is the operation we have to ensure is as fast as possible.

[bchevalier]

Yes, that was my problem too. When I did some benchmarks one year ago, it looked like iterating through arrays was twice as fast as iterating through linked list on most major browsers (except chrome). But when I ran the benchmarks again lately all the browsers had identical performance for iterating through arrays and linked list. I guess that's due to JavaScript compilers getting better. May be that deserves some JSperf.

[GoodBoyDigital]

Nice! I love a double linked list :D As @englercj mentioned, Pixi's v1 ran of double linked lists :)
We changed as arrays are just a lot easier to manage and manipulate. For a general use case sorting the children array with a sort function is the way i usually go.

What ares to you feel are incompatible with the current api? Creating a container custom container that uses a linked list rather than an array would do the trick i imagine?

Cheers!

Mat

[bchevalier]

The problem is that you would then have to maintain 2 different type of containers and particle containers that would be identical except for the data-structure storing the children.

[alaa-eddine]

I had a similar need for an isometric engine where Z-indexing is mandatory, and I tested many custom data structures with more or less success ....
My final conclusion was that using the original datastructure (Array) is the more balanced choice. not the best for performance but the it prevent some troubles and complications.

what I do to get correct z-indexing is adding a z value to sprites (or a meta data holding Z value), detect Z values changes in the code, and in that case set a Zdirty to true.
when Zdirty flag is true I call a sort function based on z values before rendering.

I'm using this technique in a game with more than 8192 sprites and it runs just fine on brower and many mobile devices.

the trick is to identify and sort only sprites inside the viewport.

[bchevalier]

I imagine that sorting almost sorted array is quite fast on any major browser (depending on the cases doing it on a linked list could be either faster or slower).

The performance issues is mainly if sprites were to be (added and) removed very frequently because calling splice is quite inefficient.

I've used the doubly linked list extensively and do not remember having more complications than I would have with an array.

[GoodBoyDigital]

closing this for now. z-indexing can be achieved using children.sort(). I do it all the time :D

[eranimo]

What a horrible solution...

[ivanpopelyshev]

@eranimo

PIXI still doesn't have built-in solution for that, nobody made not-horrible solution ;)

Except this thing that may be we'll be added later: https://github.com/pixijs/pixi-display/

[otoinsa]

Eh... sort() is such an strange way of doing it; there so much that can go wrong with sort()

[alaa-eddine]

@otoinsa actually, sort() works just fine, the only requirement is to maintain a correct Z value .
I calculate it this way : Z = x * map_width + y (it could also be Z = y * map_height + x depending on your orientation) ....
this is a video showing it in action : https://www.youtube.com/watch?v=HYLR7XjRvBU

[lock[bot]]

This thread has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.