Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 1806 | yogev_ezra | 1 | /* |
| 2 | ------------------------------------------------------------ |
||
| 3 | Fixed Rate Pig - a fixed logic frame rate demo |
||
| 4 | ------------------------------------------------------------ |
||
| 5 | * Copyright (C) 2004 David Olofson |
||
| 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 |
||
| 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 | } |