The Ecere SDK - sdk/blob - butterbur/src/tesselation.ec

   1 #define property _property
   2 #include <glutess.h>
   3 #undef property
   4
   5 import "ecere"
   6
   7 #if defined(__WIN32__)
   8 #define TESS_CALLBACK_FUNCTION_PROTOTYPE void (__stdcall*)(void)
   9 #else
  10 #define TESS_CALLBACK_FUNCTION_PROTOTYPE void *
  11 #define CALLBACK
  12 #endif
  13
  14 void * eC_malloc(unsigned int size) { return new byte[size]; }
  15 void * eC_realloc(void * pointer, unsigned int size) { return renew pointer byte[size]; }
  16 void eC_free(void * pointer) { delete pointer; }
  17
  18 Mutex tessMutex { };
  19
  20 static Array<Vector3D> vertices { };
  21
  22 static GLUtesselator * butterburTesselator = null;
  23
  24 static double ccw(Pointf a, Pointf b, Pointf c)
  25 {
  26    return (((double)b.x - (double)a.x) * ((double)c.y - (double)a.y) - ((double)c.x - (double)a.x) * ((double)b.y - (double)a.y));
  27 }
  28
  29 static bool selfIntersects(Array<Pointf> points)
  30 {
  31    int i, j;
  32    for(i = 0; i < points.count; i++)
  33    {
  34       Pointf * ap = &points[i], * aq = &points[(i < points.count-1) ? i + 1 : 0];
  35       for(j = 0; j < points.count; j++)
  36       {
  37          Pointf * bp = &points[j], * bq = &points[(j < points.count-1) ? j + 1 : 0];
  38          if(ap != bp && ap != bq && aq != bp && aq != bq)
  39          {
  40             double a = ccw(ap, aq, bp);
  41             double b = ccw(ap, aq, bq);
  42             double c = ccw(bp, bq, ap);
  43             double d = ccw(bp, bq, aq);
  44
  45             #define roundoffDouble  0.00000000001
  46
  47             if(Abs(a) < roundoffDouble) a = 0;
  48             if(Abs(b) < roundoffDouble) b = 0;
  49             if(Abs(c) < roundoffDouble) c = 0;
  50             if(Abs(d) < roundoffDouble) d = 0;
  51
  52             if(Sgn(a) * Sgn(b) < 0 && Sgn(c) * Sgn(d) < 0)
  53                return true;
  54          }
  55       }
  56    }
  57    return false;
  58 }
  59
  60 struct TessPrim
  61 {
  62    GLIMTKMode type;
  63    uint count;
  64    uint32 * indices;
  65    void OnFree()
  66    {
  67       delete indices;
  68    }
  69 };
  70
  71 struct TessPrimData
  72 {
  73    GLIMTKMode which;
  74
  75    Array<CombineVertex> combineVertices;
  76    Array<TessPrim> primitives;
  77    Array<uint> triIndices;
  78    Array<uint> tmpIndices;
  79    Array<Pointf> output;
  80 };
  81
  82 class CombineVertex : struct
  83 {
  84    Pointf position;
  85    int id;
  86 };
  87
  88 static void CALLBACK tessPrimBegin(GLenum which, TessPrimData tesselatorData)
  89 {
  90    tesselatorData.which = which == GL_TRIANGLES ? triangles : which == GL_TRIANGLE_STRIP ? triangleStrip : triangleFan;
  91    if(which != GL_TRIANGLES)
  92    {
  93       tesselatorData.tmpIndices.size = 0;
  94       if(tesselatorData.primitives.size + 1 > tesselatorData.primitives.minAllocSize)
  95          tesselatorData.primitives.minAllocSize += tesselatorData.primitives.minAllocSize / 2;
  96    }
  97 }
  98
  99 static void CALLBACK tessPrimVertex(Pointf * point, TessPrimData tesselatorData)
 100 {
 101    uint index = 0;
 102    uint * indices;
 103
 104    if(tesselatorData.which == triangles)
 105    {
 106       if(tesselatorData.triIndices.size + 1 > tesselatorData.triIndices.minAllocSize)
 107          tesselatorData.triIndices.minAllocSize += tesselatorData.triIndices.minAllocSize / 2;
 108       indices = tesselatorData.triIndices.array;
 109    }
 110    else
 111    {
 112       if(tesselatorData.tmpIndices.size + 1 > tesselatorData.tmpIndices.minAllocSize)
 113          tesselatorData.tmpIndices.minAllocSize += tesselatorData.tmpIndices.minAllocSize / 2;
 114       indices = tesselatorData.tmpIndices.array;
 115    }
 116
 117    if(point >= &tesselatorData.output[0] && point < &tesselatorData.output[tesselatorData.output.count])
 118       index = point - &tesselatorData.output[0];
 119    else
 120    {
 121       CombineVertex vertex = (CombineVertex)point;
 122       index = tesselatorData.output.count + vertex.id;
 123    }
 124
 125    if(tesselatorData.which == triangles)
 126    {
 127       uint ix = tesselatorData.triIndices.size;
 128       tesselatorData.triIndices.size++;
 129       indices[ix] = index;
 130    }
 131    else
 132    {
 133       uint ix = tesselatorData.tmpIndices.size;
 134       tesselatorData.tmpIndices.size++;
 135       indices[ix] = index;
 136    }
 137 }
 138
 139 static void CALLBACK tessPrimEnd(TessPrimData tesselatorData)
 140 {
 141    if(tesselatorData.which != triangles)
 142    {
 143       TessPrim * prim;
 144       uint ix = tesselatorData.primitives.size;
 145       tesselatorData.primitives.size++;
 146       prim = &tesselatorData.primitives[ix];
 147       prim->type = tesselatorData.which;
 148       prim->count = tesselatorData.tmpIndices.count;
 149       prim->indices = new uint32[prim->count];
 150       memcpy(prim->indices, &tesselatorData.tmpIndices[0], sizeof(uint) * prim->count);
 151    }
 152 }
 153
 154 static void CALLBACK tessPrimCombine(GLdouble coords[3], Pointf *d[4],
 155                                      GLfloat w[4], Pointf **dataOut,
 156                                                                                   TessPrimData tesselatorData)
 157 {
 158    CombineVertex vertex
 159    {
 160       position = { (float)coords[0], (float)coords[1] };
 161       id = tesselatorData.combineVertices.count;
 162    };
 163    *dataOut = &vertex.position;
 164    tesselatorData.combineVertices.Add(vertex);
 165 }
 166
 167 void tesselatePolygon(Array<Pointf> area, Array<Pointf> * outputPtr, Array<TessPrim> * primitivesPtr)
 168 {
 169         int i, d;
 170    Pointf * destPoints;
 171    int totalCount = area.count;
 172    int start = 0;
 173    Array<Pointf> output { };
 174    Array<TessPrim> primitives { minAllocSize = 16 };
 175    Array<CombineVertex> combineVertices { };
 176
 177    static TessPrimData tesselatorData;
 178
 179    tessMutex.Wait();
 180
 181    output.size = totalCount;
 182    destPoints = &output[0];
 183
 184    tesselatorData.primitives = primitives;
 185    tesselatorData.combineVertices = combineVertices;
 186    tesselatorData.tmpIndices = { minAllocSize = 16 };
 187    tesselatorData.triIndices = { minAllocSize = 16 };
 188    tesselatorData.output = output;
 189
 190    vertices.size = totalCount;
 191
 192    {
 193       int n = area.count;
 194       d = 0;
 195       for(i = 0; i < n; i++, d++)
 196       {
 197          destPoints[d] = area[i];
 198          vertices[d] = { area[i].x, area[i].y };
 199       }
 200    }
 201
 202    if(!butterburTesselator)
 203    {
 204       butterburTesselator = gluNewTess();
 205
 206       gluTessCallback(butterburTesselator, GLU_TESS_BEGIN_DATA,  (TESS_CALLBACK_FUNCTION_PROTOTYPE)(void *)tessPrimBegin);
 207       gluTessCallback(butterburTesselator, GLU_TESS_END_DATA,    (TESS_CALLBACK_FUNCTION_PROTOTYPE)(void *)tessPrimEnd);
 208       gluTessCallback(butterburTesselator, GLU_TESS_VERTEX_DATA,  (TESS_CALLBACK_FUNCTION_PROTOTYPE)(void *)tessPrimVertex);
 209       gluTessCallback(butterburTesselator, GLU_TESS_COMBINE_DATA, (TESS_CALLBACK_FUNCTION_PROTOTYPE)(void *)tessPrimCombine);
 210
 211       gluTessProperty(butterburTesselator, GLU_TESS_BOUNDARY_ONLY, GL_FALSE);
 212       gluTessProperty(butterburTesselator, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_POSITIVE);
 213    }
 214
 215    gluTessBeginPolygon(butterburTesselator, &tesselatorData);
 216
 217    start = 0;
 218    {
 219       int n = area.count;
 220       if(n && !selfIntersects(area))
 221       {
 222          gluTessBeginContour(butterburTesselator);
 223          d = start;
 224          for(i = 0; i < n; i++, d++)
 225             gluTessVertex(butterburTesselator, (double *)&vertices[d], &destPoints[d]);
 226          gluTessEndContour(butterburTesselator);
 227       }
 228       start += n;
 229    }
 230
 231    gluTessEndPolygon(butterburTesselator);
 232
 233    if(combineVertices.count)
 234    {
 235       int c;
 236       int count = output.count;
 237
 238       output.size = count + combineVertices.count;
 239       for(c = 0; c < combineVertices.count; c++)
 240       {
 241          CombineVertex vertex = combineVertices[c];
 242          output[count++] = vertex.position;
 243          delete vertex;
 244       }
 245    }
 246    delete combineVertices;
 247
 248    if(tesselatorData.triIndices && tesselatorData.triIndices.count)
 249    {
 250       uint ix = primitives.size;
 251       TessPrim * prim;
 252       primitives.size++;
 253       prim = &primitives[ix];
 254       prim->type = triangles;
 255       prim->count = tesselatorData.triIndices.count;
 256       prim->indices = new uint[prim->count];
 257       memcpy(prim->indices, &tesselatorData.triIndices[0], sizeof(uint) * prim->count);
 258    }
 259
 260    primitives.minAllocSize = 0;
 261    delete tesselatorData.triIndices;
 262    delete tesselatorData.tmpIndices;
 263
 264    *outputPtr = output;
 265    *primitivesPtr = primitives;
 266
 267    tessMutex.Release();
 268 }