dali-physics/third-party/chipmunk2d/objectivec/src/ChipmunkTileCache.m

   1 // Copyright 2013 Howling Moon Software. All rights reserved.
   2 // See http://chipmunk2d.net/legal.php for more information.
   3
   4 #import "ChipmunkTileCache.h"
   5
   6
   7 @interface ChipmunkCachedTile : NSObject {
   8         cpBB _bb;
   9         bool _dirty;
  10
  11         ChipmunkCachedTile *_next, *_prev;
  12
  13         NSArray *_shapes;
  14 }
  15
  16 @property(nonatomic, readonly) cpBB bb;
  17 @property(nonatomic, assign) bool dirty;
  18
  19 @property(nonatomic, assign) ChipmunkCachedTile *next;
  20 @property(nonatomic, assign) ChipmunkCachedTile *prev;
  21
  22 @property(nonatomic, retain) NSArray *shapes;
  23
  24 @end
  25
  26
  27
  28 @implementation ChipmunkCachedTile
  29
  30 @synthesize bb = _bb, dirty = _dirty, shapes = _shapes, next = _next, prev = _prev;
  31
  32 static cpBB
  33 ChipmunkCachedTileBB(ChipmunkCachedTile *tile)
  34 {
  35         return tile->_bb;
  36 }
  37
  38 static void
  39 ChipmunkCachedTileQuery(cpVect *pos, ChipmunkCachedTile *tile, cpCollisionID id, ChipmunkCachedTile **out)
  40 {
  41         if(cpBBContainsVect(tile->_bb, *pos)) (*out) = tile;
  42 }
  43
  44
  45 -(id)initWithBB:(cpBB)bb
  46 {
  47         if((self = [super init])) _bb = bb;
  48         return self;
  49 }
  50
  51 -(void)dealloc
  52 {
  53         self.shapes = nil;
  54         [super dealloc];
  55 }
  56
  57 @end
  58
  59
  60
  61 @implementation ChipmunkAbstractTileCache
  62
  63 @synthesize marchHard = _marchHard, sampler = _sampler, tileOffset = _tileOffset;
  64
  65 -(id)initWithSampler:(ChipmunkAbstractSampler *)sampler space:(ChipmunkSpace *)space tileSize:(cpFloat)tileSize samplesPerTile:(NSUInteger)samplesPerTile cacheSize:(NSUInteger)cacheSize
  66 {
  67         if((self = [super init])){
  68                 _sampler = [sampler retain];
  69                 _space = [space retain];
  70
  71                 _tileSize = tileSize;
  72                 _samplesPerTile =samplesPerTile;
  73                 _tileOffset = cpvzero;
  74
  75                 _cacheSize = cacheSize;
  76                 [self resetCache];
  77         }
  78
  79         return self;
  80 }
  81
  82 -(void)removeShapesForTile:(ChipmunkCachedTile *)tile
  83 {
  84         for(ChipmunkShape *shape in tile.shapes) [_space remove:shape];
  85 }
  86
  87 -(void)dealloc
  88 {
  89         for(ChipmunkCachedTile *tile = _cacheTail; tile; tile = tile.next){
  90                 [tile autorelease];
  91         }
  92
  93         [_sampler release];
  94         [_space release];
  95
  96         cpSpatialIndexFree(_tileIndex);
  97
  98         [super dealloc];
  99 }
 100
 101 -(void)resetCache
 102 {
 103         _ensuredDirty = TRUE;
 104
 105         // Reset the spatial index.
 106         if(_tileIndex) cpSpatialIndexFree(_tileIndex);
 107         _tileIndex = cpSpaceHashNew(_tileSize, (int)_cacheSize, (cpSpatialIndexBBFunc)ChipmunkCachedTileBB, NULL);
 108
 109         // Remove all the shapes and release all the tiles.
 110         for(ChipmunkCachedTile *tile = _cacheTail; tile; tile = tile.next){
 111                 [self removeShapesForTile:tile];
 112                 [tile autorelease];
 113         }
 114
 115         // Clear out the tile list.
 116         _cacheHead = _cacheTail = nil;
 117         _tileCount = 0;
 118 }
 119
 120 -(void)marchTile:(ChipmunkCachedTile *)tile
 121 {
 122         // Remove old shapes for this tile.
 123         for(ChipmunkShape *shape in tile.shapes) [_space remove:shape];
 124         cpPolylineSet *set = cpPolylineSetNew();
 125
 126         (_marchHard ? cpMarchHard : cpMarchSoft)(
 127                 tile.bb, _samplesPerTile, _samplesPerTile, _sampler.marchThreshold,
 128                 (cpMarchSegmentFunc)cpPolylineSetCollectSegment, set,
 129                 _sampler.sampleFunc, _sampler
 130         );
 131
 132         if(set->count){
 133                 ChipmunkBody *staticBody = [ChipmunkBody staticBody];
 134                 NSMutableArray *shapes = [NSMutableArray array];
 135
 136                 for(int i=0; i<set->count; i++){
 137                         cpPolyline *simplified = [self simplify:set->lines[i]];
 138
 139                         for(int i=0; i<simplified->count - 1; i++){
 140                                 ChipmunkSegmentShape *segment = [self makeSegmentFor:staticBody from:simplified->verts[i] to:simplified->verts[i+1]];
 141                                 [shapes addObject:segment];
 142                                 [_space add:segment];
 143                         }
 144
 145                         cpPolylineFree(simplified);
 146                 }
 147
 148                 tile.shapes = shapes;
 149         } else {
 150                 tile.shapes = nil;
 151         }
 152
 153         cpPolylineSetFree(set, TRUE);
 154         tile.dirty = FALSE;
 155 }
 156
 157 static inline ChipmunkCachedTile *
 158 GetTileAt(cpSpatialIndex *index, int i, int j, cpFloat size, cpVect offset)
 159 {
 160         // Cannot directly get spatial hash cells, so we'll point query at the centers.
 161         cpVect point = cpv((i + 0.5)*size + offset.x, (j + 0.5)*size + offset.y);
 162         ChipmunkCachedTile *tile = nil;
 163         cpSpatialIndexQuery(index, &point, cpBBNewForCircle(point, 0.0f), (cpSpatialIndexQueryFunc)ChipmunkCachedTileQuery, &tile);
 164
 165         return tile;
 166 }
 167
 168 struct TileRect {int l, b, r, t;};
 169
 170 static inline cpBB
 171 BBForTileRect(struct TileRect rect, cpFloat size, cpVect offset)
 172 {
 173         return cpBBNew(rect.l*size + offset.x, rect.b*size + offset.y, rect.r*size + offset.x, rect.t*size + offset.y);
 174 }
 175
 176 static inline struct TileRect
 177 TileRectForBB(cpBB bb, cpFloat size, cpVect offset, cpFloat spt_inv)
 178 {
 179         return (struct TileRect){
 180                 (int)cpffloor((bb.l - offset.x)/size - spt_inv),
 181                 (int)cpffloor((bb.b - offset.x)/size - spt_inv),
 182                 (int) cpfceil((bb.r - offset.y)/size + spt_inv),
 183                 (int) cpfceil((bb.t - offset.y)/size + spt_inv),
 184         };
 185 }
 186
 187 -(void)markDirtyRect:(cpBB)bounds
 188 {
 189         cpFloat size = _tileSize;
 190         cpVect offset = _tileOffset;
 191         struct TileRect rect = TileRectForBB(bounds, size, offset, 1.0/(cpFloat)_samplesPerTile);
 192
 193         if(!_ensuredDirty && cpBBContainsBB(_ensuredBB, BBForTileRect(rect, size, offset))){
 194                 _ensuredDirty = TRUE;
 195         }
 196
 197         for(int i=rect.l; i<rect.r; i++){
 198                 for(int j=rect.b; j<rect.t; j++){
 199                         ChipmunkCachedTile *tile = GetTileAt(_tileIndex, i, j, size, offset);
 200                         if(tile) tile.dirty = TRUE;
 201                 }
 202         }
 203 }
 204
 205 -(void)pushTile:(ChipmunkCachedTile *)tile
 206 {
 207         [tile retain];
 208
 209         _cacheHead.next = tile;
 210         tile.prev = _cacheHead;
 211
 212         _cacheHead = tile;
 213         _cacheTail = _cacheTail ?: tile;
 214 }
 215
 216 -(void)removeTile:(ChipmunkCachedTile *)tile
 217 {
 218         if(tile.prev == nil && _cacheTail == tile) _cacheTail = tile.next;
 219         if(tile.next == nil && _cacheHead == tile) _cacheHead = tile.prev;
 220
 221         tile.prev.next = tile.next;
 222         tile.next.prev = tile.prev;
 223         tile.prev = tile.next = nil;
 224
 225         [tile autorelease];
 226 }
 227
 228 #define LOADING_FACTOR 1.0
 229
 230 //extern double GetMilliseconds();
 231
 232 -(void)ensureRect:(cpBB)bounds
 233 {
 234 //      double time = GetMilliseconds();
 235
 236         cpFloat size = _tileSize;
 237         cpVect offset = _tileOffset;
 238         struct TileRect rect = TileRectForBB(bounds, size, offset, 1.0/(cpFloat)_samplesPerTile);
 239
 240         cpBB ensure = BBForTileRect(rect, size, offset);
 241         if(!_ensuredDirty && cpBBContainsBB(_ensuredBB, ensure)) return;
 242
 243 //      int count = 0;
 244 //      printf("Marching tiles in (% 4d, % 4d) - (% 4d, % 4d):\n", l, b, r, t);
 245         for(int i=rect.l; i<rect.r; i++){
 246                 for(int j=rect.b; j<rect.t; j++){
 247 //                      printf("Marching tile (% 4d, % 4d)\n", i, j);
 248
 249                         ChipmunkCachedTile *tile = GetTileAt(_tileIndex, i, j, size, offset);
 250
 251                         if(!tile){
 252                                 // Tile does not exist yet, make a new dirty tile.
 253                                 // Let the code below push it into the tile list.
 254                                 tile = [[ChipmunkCachedTile alloc] initWithBB:BBForTileRect((struct TileRect){i, j, i+1, j+1}, size, offset)];
 255                                 tile.dirty = TRUE;
 256
 257                                 cpSpatialIndexInsert(_tileIndex, tile, (cpHashValue)tile);
 258                                 _tileCount++;
 259                         }
 260
 261                         if(tile.dirty) [self marchTile:tile];
 262
 263                         // Move tile to the front of the cache. (or add it for the first time)
 264                         [self removeTile:tile];
 265                         [self pushTile:tile];
 266                 }
 267         }
 268
 269         _ensuredBB = ensure;
 270         _ensuredDirty = FALSE;
 271
 272         // Remove tiles used the longest ago if over the cache count;
 273         NSInteger removeCount = _tileCount - _cacheSize;
 274         for(int i=0; i<removeCount; i++){
 275                 cpSpatialIndexRemove(_tileIndex, _cacheTail, (cpHashValue)_cacheTail);
 276                 [self removeShapesForTile:_cacheTail];
 277                 [self removeTile:_cacheTail];
 278
 279                 _tileCount--;
 280         }
 281
 282 //      NSLog(@"Updated %3d tiles in %6.3fms", count, GetMilliseconds() - time);
 283 }
 284
 285 -(cpPolyline *)simplify:(cpPolyline *)polyline
 286 {
 287         @throw [NSException
 288                 exceptionWithName:NSInternalInconsistencyException
 289                 reason:[NSString stringWithFormat:@"You must override %@ in a subclass", NSStringFromSelector(_cmd)]
 290                 userInfo:nil
 291         ];
 292 }
 293
 294 -(ChipmunkSegmentShape *)makeSegmentFor:(ChipmunkBody *)staticBody from:(cpVect)a to:(cpVect)b
 295 {
 296         @throw [NSException
 297                 exceptionWithName:NSInternalInconsistencyException
 298                 reason:[NSString stringWithFormat:@"You must override %@ in a subclass", NSStringFromSelector(_cmd)]
 299                 userInfo:nil
 300         ];
 301 }
 302
 303 @end
 304
 305
 306
 307 @implementation ChipmunkBasicTileCache
 308
 309 @synthesize simplifyThreshold = _simplifyThreshold;
 310
 311 @synthesize segmentRadius = _segmentRadius;
 312
 313 @synthesize segmentFriction = _segmentFriction;
 314 @synthesize segmentElasticity = _segmentElasticity;
 315
 316 @synthesize segmentFilter = _segmentFilter;
 317
 318 @synthesize segmentCollisionType = _segmentCollisionType;
 319
 320 -(id)initWithSampler:(ChipmunkAbstractSampler *)sampler space:(ChipmunkSpace *)space tileSize:(cpFloat)tileSize samplesPerTile:(NSUInteger)samplesPerTile cacheSize:(NSUInteger)cacheSize
 321 {
 322         if((self = [super initWithSampler:sampler space:space tileSize:tileSize samplesPerTile:samplesPerTile cacheSize:cacheSize])){
 323                 _simplifyThreshold = 2.0;
 324
 325                 _segmentRadius = 0.0;
 326
 327                 _segmentFriction = 1.0;
 328                 _segmentElasticity = 1.0;
 329
 330                 _segmentFilter = CP_SHAPE_FILTER_ALL;
 331
 332                 _segmentCollisionType = (cpCollisionType)0;
 333         }
 334
 335         return self;
 336 }
 337
 338 -(cpPolyline *)simplify:(cpPolyline *)polyline
 339 {
 340         return cpPolylineSimplifyCurves(polyline, _simplifyThreshold);
 341 }
 342
 343 -(ChipmunkSegmentShape *)makeSegmentFor:(ChipmunkBody *)staticBody from:(cpVect)a to:(cpVect)b
 344 {
 345         ChipmunkSegmentShape *segment = [ChipmunkSegmentShape segmentWithBody:staticBody from:a to:b radius:_segmentRadius];
 346         segment.friction = _segmentFriction;
 347         segment.elasticity = _segmentElasticity;
 348         segment.filter = _segmentFilter;
 349         segment.collisionType = _segmentCollisionType;
 350
 351         return segment;
 352 }
 353
 354 @end