Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2. ------------------------------------------------------------
  3.         Fixed Rate Pig - a fixed logic frame rate demo
  4. ------------------------------------------------------------
  5.  * Copyright (C) 2004 David Olofson <david@olofson.net>
  6.  *
  7.  * This software is released under the terms of the GPL.
  8.  *
  9.  * Contact author for permission if you want to use this
  10.  * software, or work derived from it, under other terms.
  11.  */
  12.  
  13. #include <stdlib.h>
  14. #include "engine.h"
  15.  
  16. /* Approximate worth of one dirtyrect in pixels. */
  17. #define PIG_WORST_MERGE         300
  18.  
  19. /*
  20.  * If the merged result gets at most this many percent
  21.  * bigger than the larger of the two input rects,
  22.  * accept it as Perfect.
  23.  */
  24. #define PIG_INSTANT_MERGE       10
  25.  
  26.  
  27. PIG_dirtytable *pig_dirty_open(int size)
  28. {
  29.         PIG_dirtytable *pdt = (PIG_dirtytable *)malloc(sizeof(PIG_dirtytable));
  30.         if(!pdt)
  31.                 return NULL;
  32.  
  33.         pdt->size = size;
  34.         pdt->rects = (SDL_Rect *)calloc(size, sizeof(SDL_Rect));
  35.         if(!pdt->rects)
  36.         {
  37.                 free(pdt);
  38.                 return NULL;
  39.         }
  40.  
  41.         pdt->count = 0;
  42.         pdt->best = 0;
  43.         return pdt;
  44. }
  45.  
  46.  
  47. void pig_dirty_close(PIG_dirtytable *pdt)
  48. {
  49.         free(pdt->rects);
  50.         free(pdt);
  51. }
  52.  
  53.  
  54. void pig_mergerect(SDL_Rect *from, SDL_Rect *to)
  55. {
  56.         int x1 = from->x;
  57.         int y1 = from->y;
  58.         int x2 = from->x + from->w;
  59.         int y2 = from->y + from->h;
  60.         if(to->x < x1)
  61.                 x1 = to->x;
  62.         if(to->y < y1)
  63.                 y1 = to->y;
  64.         if(to->x + to->w > x2)
  65.                 x2 = to->x + to->w;
  66.         if(to->y + to->h > y2)
  67.                 y2 = to->y + to->h;
  68.         to->x = x1;
  69.         to->y = y1;
  70.         to->w = x2 - x1;
  71.         to->h = y2 - y1;
  72. }
  73.  
  74.  
  75. void pig_intersectrect(SDL_Rect *from, SDL_Rect *to)
  76. {
  77.         int Amin, Amax, Bmin, Bmax;
  78.         Amin = to->x;
  79.         Amax = Amin + to->w;
  80.         Bmin = from->x;
  81.         Bmax = Bmin + from->w;
  82.         if(Bmin > Amin)
  83.                 Amin = Bmin;
  84.         to->x = Amin;
  85.         if(Bmax < Amax)
  86.                 Amax = Bmax;
  87.         to->w = Amax - Amin > 0 ? Amax - Amin : 0;
  88.  
  89.         Amin = to->y;
  90.         Amax = Amin + to->h;
  91.         Bmin = from->y;
  92.         Bmax = Bmin + from->h;
  93.         if(Bmin > Amin)
  94.                 Amin = Bmin;
  95.         to->y = Amin;
  96.         if(Bmax < Amax)
  97.                 Amax = Bmax;
  98.         to->h = Amax - Amin > 0 ? Amax - Amin : 0;
  99. }
  100.  
  101.  
  102. void pig_dirty_add(PIG_dirtytable *pdt, SDL_Rect *dr)
  103. {
  104.         int i, j, best_i, best_loss;
  105.         /*
  106.          * Look for merger candidates.
  107.          *
  108.          * We start right before the best match we
  109.          * had the last time around. This can give
  110.          * us large numbers of direct or quick hits
  111.          * when dealing with old/new rects for moving
  112.          * objects and the like.
  113.          */
  114.         best_i = -1;
  115.         best_loss = 100000000;
  116.         if(pdt->count)
  117.                 i = (pdt->best + pdt->count - 1) % pdt->count;
  118.         for(j = 0; j < pdt->count; ++j)
  119.         {
  120.                 int a1, a2, am, ratio, loss;
  121.                 SDL_Rect testr;
  122.  
  123.                 a1 = dr->w * dr->h;
  124.  
  125.                 testr = pdt->rects[i];
  126.                 a2 = testr.w * testr.h;
  127.  
  128.                 pig_mergerect(dr, &testr);
  129.                 am = testr.w * testr.h;
  130.  
  131.                 /* Perfect or Instant Pick? */
  132.                 ratio = 100 * am / (a1 > a2 ? a1 : a2);
  133.                 if(ratio < PIG_INSTANT_MERGE)
  134.                 {
  135.                         /* Ok, this is good enough! Stop searching. */
  136.                         pig_mergerect(dr, &pdt->rects[i]);
  137.                         pdt->best = i;
  138.                         return;
  139.                 }
  140.  
  141.                 loss = am - a1 - a2;
  142.                 if(loss < best_loss)
  143.                 {
  144.                         best_i = i;
  145.                         best_loss = loss;
  146.                         pdt->best = i;
  147.                 }
  148.  
  149.                 ++i;
  150.                 i %= pdt->count;
  151.         }
  152.         /* ...and if the best result is good enough, merge! */
  153.         if((best_i >= 0) && (best_loss < PIG_WORST_MERGE))
  154.         {
  155.                 pig_mergerect(dr, &pdt->rects[best_i]);
  156.                 return;
  157.         }
  158.  
  159.         /* Try to add to table... */
  160.         if(pdt->count < pdt->size)
  161.         {
  162.                 pdt->rects[pdt->count++] = *dr;
  163.                 return;
  164.         }
  165.  
  166.         /* Emergency: Table full! Grab best candidate... */
  167.         pig_mergerect(dr, &pdt->rects[best_i]);
  168. }
  169.  
  170.  
  171. void pig_dirty_merge(PIG_dirtytable *pdt, PIG_dirtytable *from)
  172. {
  173.         int i;
  174.         for(i = 0; i < from->count; ++i)
  175.                 pig_dirty_add(pdt, from->rects + i);
  176. }
  177.