SHARE
TWEET

Untitled

a guest Jan 29th, 2020 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. static void ViewportSortParentSpritesSegtree10(ParentSpriteToSortVector *psdv)
  2. {
  3.     if (psdv->size() < 2) return;
  4.     auto t = getticks();
  5.  
  6.     struct Node {
  7.         int32 x = INT32_MAX;
  8.         int32 y = INT32_MAX;
  9.         int32 z = INT32_MAX;
  10.  
  11.         Node() {}
  12.         Node(int32 x, int32 y, int32 z)
  13.             :x(x), y(y), z(z) {}
  14.     };
  15.  
  16.     auto n = psdv->size();
  17.     std::vector<Node> nodes(2 * n);
  18.  
  19.     uint32 next_order = 0;
  20.     for (auto p = psdv->rbegin(); p != psdv->rend(); p++) {
  21.         (*p)->order = next_order++;
  22.         (*p)->comparison_done = false;
  23.         (*p)->comparison_fin = false;
  24.     }
  25.  
  26.     auto sprites = *psdv;
  27.     std::stable_sort(sprites.begin(), sprites.end(), [](const ParentSpriteToDraw *a, const ParentSpriteToDraw *b) {
  28.         // return std::tie(a->ymin, a->xmin, a->zmin) > std::tie(b->ymin, b->xmin, b->zmin);
  29.         // return a->xmin + a->ymin + a->zmin < b->xmin + b->ymin + b->zmin;
  30.         return a->ymin > b->ymin;
  31.     });
  32.  
  33.     std::vector<size_t> sprite_order(n);
  34.     sprite_order.reserve(2 * n);
  35.  
  36.     auto &v = *psdv;
  37.     for (auto i = n; i < 2 * n; i++) {
  38.         auto p = sprites[i - n];
  39.         sprite_order[p->order] = i;
  40.         auto &c = nodes[i];
  41.         c.x = p->xmin;
  42.         c.y = p->ymin;
  43.         c.z = p->zmin;
  44.         // this->nodes[i] = Node(p->xmin, p->ymin, p->zmin, p->order, p);
  45.     }
  46.     for(auto i = n - 1; i > 0; i--) {
  47.         auto &a = nodes[i * 2];
  48.         auto &b = nodes[i * 2 + 1];
  49.         auto &c = nodes[i];
  50.         c.x = min(a.x, b.x);
  51.         c.y = min(a.y, b.y);
  52.         c.z = min(a.z, b.z);
  53.         // this->nodes[i] = Node(min(a.x, b.x), min(a.y, b.y), min(a.z, b.z), min(a.order, b.order));
  54.     }
  55.  
  56.     std::vector<size_t> moving;
  57.     std::stack<ParentSpriteToDraw *> compared;
  58.  
  59.     auto out = psdv->begin();
  60.     std::queue<size_t> q;
  61.  
  62.     double s1=elapsed(getticks(), t), s2=0, s3 = 0, s4=0, s5=0, s6=0;
  63.  
  64.     int ii=0, jj=0, kk=0;
  65.     while (!sprite_order.empty()) {
  66.         t = getticks();
  67.         // std::cout << "REMOVE" << *s << std::endl;
  68.         auto i = sprite_order.back();
  69.         auto s = sprites[i - n];
  70.         if (s->comparison_fin) {
  71.             sprite_order.pop_back();
  72.             continue;
  73.         }
  74.         if (s->comparison_done) {
  75.             *(out++) = s;
  76.             s->comparison_fin = true;
  77.             sprite_order.pop_back();
  78.             continue;
  79.         }
  80.  
  81.         auto &c = nodes[i];
  82.         // this->nodes[index] = Node(x, y, z, order, nullptr);
  83.         c.x = INT32_MAX;
  84.         c.y = INT32_MAX;
  85.         c.z = INT32_MAX;
  86.         for(; i > 1; i >>= 1) {
  87.             auto &a = nodes[i];
  88.             auto &b = nodes[i ^ 1];
  89.             auto x = min(a.x, b.x), y = min(a.y, b.y), z = min(a.z, b.z);
  90.             auto &c = nodes[i >> 1];
  91.             c.x = x;
  92.             c.y = y;
  93.             c.z = z;
  94.         }
  95.  
  96.         s2 += elapsed(getticks(), t); t = getticks();
  97.         ii++;
  98.  
  99.         moving.clear();
  100.  
  101.         // auto &a = nodes[1];
  102.         // if (a.x <= s->xmax && a.y <= s->ymax && a.z <= s->zmax) {
  103.         q.push(2);
  104.         // }
  105.  
  106.         // std::cout << "QUERY " <<  *s << std::endl;
  107.         while (!q.empty()) {
  108.             auto i = q.front();
  109.             q.pop();
  110.             jj++;
  111.  
  112.             for (auto j = 0; j < 2; j++, i++) {
  113.                 auto &a = nodes[i];
  114.                 // std::cout << "TEST " << a.x << " " << a.y << " " << a.z << "   " << !(a.x > s->xmax || a.y > s->ymax || a.z > s->zmax) << " " << i << std::endl;
  115.                 if (a.x > s->xmax || a.y > s->ymax || a.z > s->zmax) continue;
  116.  
  117.                 if (i < n) {
  118.                     q.push(i * 2);
  119.                     continue;
  120.                 }
  121.  
  122.                 // std::cout << "FOUND " << a.x << " " << a.y << " " << a.z << "   " << i << std::endl;
  123.                 kk++;
  124.  
  125.                 auto p = sprites[i - n];
  126.                 if (s->xmin <= p->xmax && // overlap in X?
  127.                         s->ymin <= p->ymax && // overlap in Y?
  128.                         s->zmin <= p->zmax) { // overlap in Z?
  129.                     if (s->xmin + s->xmax + s->ymin + s->ymax + s->zmin + s->zmax <=
  130.                             p->xmin + p->xmax + p->ymin + p->ymax + p->zmin + p->zmax) {
  131.                         continue;
  132.                     }
  133.                 }
  134.                 // __m128i s_min = LOAD_128((__m128i*) &s->xmin);
  135.                 // __m128i p_max = LOAD_128((__m128i*) &p->xmax);
  136.                 // __m128i r = _mm_cmplt_epi32(p_max, s_min);
  137.                 // if (_mm_testz_si128(mask_ptest, r)) {
  138.                 //     if (s->xmin + s->xmax + s->ymin + s->ymax + s->zmin + s->zmax <=
  139.                 //             p->xmin + p->xmax + p->ymin + p->ymax + p->zmin + p->zmax) {
  140.                 //         continue;
  141.                 //     }
  142.                 // }
  143.  
  144.                 moving.push_back(i);
  145.             }
  146.         }
  147.  
  148.         s3 += elapsed(getticks(), t); t = getticks();
  149.  
  150.         if (moving.empty()) {
  151.             *(out++) = s;
  152.             s->comparison_fin = true;
  153.             sprite_order.pop_back();
  154.             continue;
  155.         }
  156.         s4 += elapsed(getticks(), t); t = getticks();
  157.  
  158.         std::sort(moving.begin(), moving.end(), [&sprites, n](size_t a, size_t b) {
  159.             return sprites[a - n]->order > sprites[b - n]->order;
  160.         });
  161.  
  162.         // std::cout << "SPLIT " << *s << " " << moving.size() << std::endl;
  163.         // std::cout << "SPLIT " << *s << " " << moving.size() << " " << **moving.begin() << " " << **moving.rbegin() << std::endl;
  164.  
  165.         s->order = next_order++;
  166.         s->comparison_done = true;
  167.  
  168.         for (auto i: moving) {
  169.             auto p = sprites[i - n];
  170.             p->order = next_order++;
  171.             sprite_order.push_back(i);
  172.         }
  173.  
  174.         s5 += elapsed(getticks(), t); t = getticks();
  175.     }
  176.     s6 += elapsed(getticks(), t); t = getticks();
  177.  
  178.     std::cout << "segtree10_T  1: " << s1  / 100000 << "  2: " << s2  / 100000 << "  3: " << s3  / 100000 << "  4: " << s4 / 100000 << "  5: " << s5 / 100000 << "  6: " << s6 / 100000 << std::endl;
  179.     std::cout << "segtree10_i " << ii << " " << jj << " " << kk << std::endl;
  180. }
  181.  
  182. segtree10_T  1: 38.0  2: 28.9  3: 164.6  4: 0.5  5: 1.0  6: 0.0
  183. segtree10_i 27940 670653 3135
  184. 24.3
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top