dali-physics/third-party/chipmunk2d/src/cpMarch.c

   1 // Copyright 2013 Howling Moon Software. All rights reserved.
   2 // See http://chipmunk2d.net/legal.php for more information.
   3
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6 #include <math.h>
   7
   8 #include "chipmunk/chipmunk.h"
   9 #include "chipmunk/cpMarch.h"
  10
  11
  12 typedef void (*cpMarchCellFunc)(
  13         cpFloat t, cpFloat a, cpFloat b, cpFloat c, cpFloat d,
  14         cpFloat x0, cpFloat x1, cpFloat y0, cpFloat y1,
  15         cpMarchSegmentFunc segment, void *segment_data
  16 );
  17
  18 // The looping and sample caching code is shared between cpMarchHard() and cpMarchSoft().
  19 static void
  20 cpMarchCells(
  21   cpBB bb, unsigned long x_samples, unsigned long y_samples, cpFloat t,
  22   cpMarchSegmentFunc segment, void *segment_data,
  23   cpMarchSampleFunc sample, void *sample_data,
  24         cpMarchCellFunc cell
  25 ){
  26         cpFloat x_denom = 1.0/(cpFloat)(x_samples - 1);
  27         cpFloat y_denom = 1.0/(cpFloat)(y_samples - 1);
  28
  29         // TODO range assertions and short circuit for 0 sized windows.
  30
  31         // Keep a copy of the previous row to avoid double lookups.
  32         cpFloat *buffer = (cpFloat *)cpcalloc(x_samples, sizeof(cpFloat));
  33         for(unsigned long i=0; i<x_samples; i++) buffer[i] = sample(cpv(cpflerp(bb.l, bb.r, i*x_denom), bb.b), sample_data);
  34
  35         for(unsigned long j=0; j<y_samples-1; j++){
  36                 cpFloat y0 = cpflerp(bb.b, bb.t, (j+0)*y_denom);
  37                 cpFloat y1 = cpflerp(bb.b, bb.t, (j+1)*y_denom);
  38
  39                 cpFloat a, b = buffer[0];
  40                 cpFloat c, d = sample(cpv(bb.l, y1), sample_data);
  41                 buffer[0] = d;
  42
  43                 for(unsigned long i=0; i<x_samples-1; i++){
  44                         cpFloat x0 = cpflerp(bb.l, bb.r, (i+0)*x_denom);
  45                         cpFloat x1 = cpflerp(bb.l, bb.r, (i+1)*x_denom);
  46
  47                         a = b, b = buffer[i + 1];
  48                         c = d, d = sample(cpv(x1, y1), sample_data);
  49                         buffer[i + 1] = d;
  50
  51                         cell(t, a, b, c, d, x0, x1, y0, y1, segment, segment_data);
  52                 }
  53         }
  54
  55         cpfree(buffer);
  56 }
  57
  58
  59 // TODO should flip this around eventually.
  60 static inline void
  61 seg(cpVect v0, cpVect v1, cpMarchSegmentFunc f, void *data)
  62 {
  63         if(!cpveql(v0, v1)) f(v1, v0, data);
  64 }
  65
  66 // Lerps between two positions based on their sample values.
  67 static inline cpFloat
  68 midlerp(cpFloat x0, cpFloat x1, cpFloat s0, cpFloat s1, cpFloat t)
  69 {
  70         return cpflerp(x0, x1, (t - s0)/(s1 - s0));
  71 }
  72
  73 static void
  74 cpMarchCellSoft(
  75         cpFloat t, cpFloat a, cpFloat b, cpFloat c, cpFloat d,
  76         cpFloat x0, cpFloat x1, cpFloat y0, cpFloat y1,
  77         cpMarchSegmentFunc segment, void *segment_data
  78 ){
  79         // TODO this switch part is super expensive, can it be NEONized?
  80         switch((a>t)<<0 | (b>t)<<1 | (c>t)<<2 | (d>t)<<3){
  81                 case 0x1: seg(cpv(x0, midlerp(y0,y1,a,c,t)), cpv(midlerp(x0,x1,a,b,t), y0), segment, segment_data); break;
  82                 case 0x2: seg(cpv(midlerp(x0,x1,a,b,t), y0), cpv(x1, midlerp(y0,y1,b,d,t)), segment, segment_data); break;
  83                 case 0x3: seg(cpv(x0, midlerp(y0,y1,a,c,t)), cpv(x1, midlerp(y0,y1,b,d,t)), segment, segment_data); break;
  84                 case 0x4: seg(cpv(midlerp(x0,x1,c,d,t), y1), cpv(x0, midlerp(y0,y1,a,c,t)), segment, segment_data); break;
  85                 case 0x5: seg(cpv(midlerp(x0,x1,c,d,t), y1), cpv(midlerp(x0,x1,a,b,t), y0), segment, segment_data); break;
  86                 case 0x6: seg(cpv(midlerp(x0,x1,a,b,t), y0), cpv(x1, midlerp(y0,y1,b,d,t)), segment, segment_data);
  87                                                         seg(cpv(midlerp(x0,x1,c,d,t), y1), cpv(x0, midlerp(y0,y1,a,c,t)), segment, segment_data); break;
  88                 case 0x7: seg(cpv(midlerp(x0,x1,c,d,t), y1), cpv(x1, midlerp(y0,y1,b,d,t)), segment, segment_data); break;
  89                 case 0x8: seg(cpv(x1, midlerp(y0,y1,b,d,t)), cpv(midlerp(x0,x1,c,d,t), y1), segment, segment_data); break;
  90                 case 0x9: seg(cpv(x0, midlerp(y0,y1,a,c,t)), cpv(midlerp(x0,x1,a,b,t), y0), segment, segment_data);
  91                                                         seg(cpv(x1, midlerp(y0,y1,b,d,t)), cpv(midlerp(x0,x1,c,d,t), y1), segment, segment_data); break;
  92                 case 0xA: seg(cpv(midlerp(x0,x1,a,b,t), y0), cpv(midlerp(x0,x1,c,d,t), y1), segment, segment_data); break;
  93                 case 0xB: seg(cpv(x0, midlerp(y0,y1,a,c,t)), cpv(midlerp(x0,x1,c,d,t), y1), segment, segment_data); break;
  94                 case 0xC: seg(cpv(x1, midlerp(y0,y1,b,d,t)), cpv(x0, midlerp(y0,y1,a,c,t)), segment, segment_data); break;
  95                 case 0xD: seg(cpv(x1, midlerp(y0,y1,b,d,t)), cpv(midlerp(x0,x1,a,b,t), y0), segment, segment_data); break;
  96                 case 0xE: seg(cpv(midlerp(x0,x1,a,b,t), y0), cpv(x0, midlerp(y0,y1,a,c,t)), segment, segment_data); break;
  97                 default: break; // 0x0 and 0xF
  98         }
  99 }
 100
 101 void
 102 cpMarchSoft(
 103   cpBB bb, unsigned long x_samples, unsigned long y_samples, cpFloat t,
 104   cpMarchSegmentFunc segment, void *segment_data,
 105   cpMarchSampleFunc sample, void *sample_data
 106 ){
 107         cpMarchCells(bb, x_samples, y_samples, t, segment, segment_data, sample, sample_data, cpMarchCellSoft);
 108 }
 109
 110
 111 // TODO should flip this around eventually.
 112 static inline void
 113 segs(cpVect a, cpVect b, cpVect c, cpMarchSegmentFunc f, void *data)
 114 {
 115         seg(b, c, f, data);
 116         seg(a, b, f, data);
 117 }
 118
 119 static void
 120 cpMarchCellHard(
 121         cpFloat t, cpFloat a, cpFloat b, cpFloat c, cpFloat d,
 122         cpFloat x0, cpFloat x1, cpFloat y0, cpFloat y1,
 123         cpMarchSegmentFunc segment, void *segment_data
 124 ){
 125         // midpoints
 126         cpFloat xm = cpflerp(x0, x1, 0.5f);
 127         cpFloat ym = cpflerp(y0, y1, 0.5f);
 128
 129         switch((a>t)<<0 | (b>t)<<1 | (c>t)<<2 | (d>t)<<3){
 130                 case 0x1: segs(cpv(x0, ym), cpv(xm, ym), cpv(xm, y0), segment, segment_data); break;
 131                 case 0x2: segs(cpv(xm, y0), cpv(xm, ym), cpv(x1, ym), segment, segment_data); break;
 132                 case 0x3: seg(cpv(x0, ym), cpv(x1, ym), segment, segment_data); break;
 133                 case 0x4: segs(cpv(xm, y1), cpv(xm, ym), cpv(x0, ym), segment, segment_data); break;
 134                 case 0x5: seg(cpv(xm, y1), cpv(xm, y0), segment, segment_data); break;
 135                 case 0x6: segs(cpv(xm, y0), cpv(xm, ym), cpv(x0, ym), segment, segment_data);
 136                           segs(cpv(xm, y1), cpv(xm, ym), cpv(x1, ym), segment, segment_data); break;
 137                 case 0x7: segs(cpv(xm, y1), cpv(xm, ym), cpv(x1, ym), segment, segment_data); break;
 138                 case 0x8: segs(cpv(x1, ym), cpv(xm, ym), cpv(xm, y1), segment, segment_data); break;
 139                 case 0x9: segs(cpv(x1, ym), cpv(xm, ym), cpv(xm, y0), segment, segment_data);
 140                           segs(cpv(x0, ym), cpv(xm, ym), cpv(xm, y1), segment, segment_data); break;
 141                 case 0xA: seg(cpv(xm, y0), cpv(xm, y1), segment, segment_data); break;
 142                 case 0xB: segs(cpv(x0, ym), cpv(xm, ym), cpv(xm, y1), segment, segment_data); break;
 143                 case 0xC: seg(cpv(x1, ym), cpv(x0, ym), segment, segment_data); break;
 144                 case 0xD: segs(cpv(x1, ym), cpv(xm, ym), cpv(xm, y0), segment, segment_data); break;
 145                 case 0xE: segs(cpv(xm, y0), cpv(xm, ym), cpv(x0, ym), segment, segment_data); break;
 146                 default: break; // 0x0 and 0xF
 147         }
 148 }
 149
 150 void
 151 cpMarchHard(
 152   cpBB bb, unsigned long x_samples, unsigned long y_samples, cpFloat t,
 153   cpMarchSegmentFunc segment, void *segment_data,
 154   cpMarchSampleFunc sample, void *sample_data
 155 ){
 156         cpMarchCells(bb, x_samples, y_samples, t, segment, segment_data, sample, sample_data, cpMarchCellHard);
 157 }