1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/openctm/compressMG2.c	Thu Sep 26 04:47:05 2013 +0300
     1.3 @@ -0,0 +1,1319 @@
     1.4 +//-----------------------------------------------------------------------------
     1.5 +// Product:     OpenCTM
     1.6 +// File:        compressMG2.c
     1.7 +// Description: Implementation of the MG2 compression method.
     1.8 +//-----------------------------------------------------------------------------
     1.9 +// Copyright (c) 2009-2010 Marcus Geelnard
    1.10 +//
    1.11 +// This software is provided 'as-is', without any express or implied
    1.12 +// warranty. In no event will the authors be held liable for any damages
    1.13 +// arising from the use of this software.
    1.14 +//
    1.15 +// Permission is granted to anyone to use this software for any purpose,
    1.16 +// including commercial applications, and to alter it and redistribute it
    1.17 +// freely, subject to the following restrictions:
    1.18 +//
    1.19 +//     1. The origin of this software must not be misrepresented; you must not
    1.20 +//     claim that you wrote the original software. If you use this software
    1.21 +//     in a product, an acknowledgment in the product documentation would be
    1.22 +//     appreciated but is not required.
    1.23 +//
    1.24 +//     2. Altered source versions must be plainly marked as such, and must not
    1.25 +//     be misrepresented as being the original software.
    1.26 +//
    1.27 +//     3. This notice may not be removed or altered from any source
    1.28 +//     distribution.
    1.29 +//-----------------------------------------------------------------------------
    1.30 +
    1.31 +#include <stdlib.h>
    1.32 +#include <math.h>
    1.33 +#include "openctm.h"
    1.34 +#include "internal.h"
    1.35 +
    1.36 +#ifdef __DEBUG_
    1.37 +#include <stdio.h>
    1.38 +#endif
    1.39 +
    1.40 +// We need PI
    1.41 +#ifndef PI
    1.42 +#define PI 3.141592653589793238462643f
    1.43 +#endif
    1.44 +
    1.45 +
    1.46 +//-----------------------------------------------------------------------------
    1.47 +// _CTMgrid - 3D space subdivision grid.
    1.48 +//-----------------------------------------------------------------------------
    1.49 +typedef struct {
    1.50 +  // Axis-aligned boudning box for the grid.
    1.51 +  CTMfloat mMin[3];
    1.52 +  CTMfloat mMax[3];
    1.53 +
    1.54 +  // How many divisions per axis (minimum 1).
    1.55 +  CTMuint mDivision[3];
    1.56 +
    1.57 +  // Size of each grid box.
    1.58 +  CTMfloat mSize[3];
    1.59 +} _CTMgrid;
    1.60 +
    1.61 +//-----------------------------------------------------------------------------
    1.62 +// _CTMsortvertex - Vertex information.
    1.63 +//-----------------------------------------------------------------------------
    1.64 +typedef struct {
    1.65 +  // Vertex X coordinate (used for sorting).
    1.66 +  CTMfloat x;
    1.67 +
    1.68 +  // Grid index. This is the index into the 3D space subdivision grid.
    1.69 +  CTMuint mGridIndex;
    1.70 +
    1.71 +  // Original index (before sorting).
    1.72 +  CTMuint mOriginalIndex;
    1.73 +} _CTMsortvertex;
    1.74 +
    1.75 +//-----------------------------------------------------------------------------
    1.76 +// _ctmSetupGrid() - Setup the 3D space subdivision grid.
    1.77 +//-----------------------------------------------------------------------------
    1.78 +static void _ctmSetupGrid(_CTMcontext * self, _CTMgrid * aGrid)
    1.79 +{
    1.80 +  CTMuint i;
    1.81 +  CTMfloat factor[3], sum, wantedGrids;
    1.82 +
    1.83 +  // Calculate the mesh bounding box
    1.84 +  aGrid->mMin[0] = aGrid->mMax[0] = self->mVertices[0];
    1.85 +  aGrid->mMin[1] = aGrid->mMax[1] = self->mVertices[1];
    1.86 +  aGrid->mMin[2] = aGrid->mMax[2] = self->mVertices[2];
    1.87 +  for(i = 1; i < self->mVertexCount; ++ i)
    1.88 +  {
    1.89 +    if(self->mVertices[i * 3] < aGrid->mMin[0])
    1.90 +      aGrid->mMin[0] = self->mVertices[i * 3];
    1.91 +    else if(self->mVertices[i * 3] > aGrid->mMax[0])
    1.92 +      aGrid->mMax[0] = self->mVertices[i * 3];
    1.93 +    if(self->mVertices[i * 3 + 1] < aGrid->mMin[1])
    1.94 +      aGrid->mMin[1] = self->mVertices[i * 3 + 1];
    1.95 +    else if(self->mVertices[i * 3 + 1] > aGrid->mMax[1])
    1.96 +      aGrid->mMax[1] = self->mVertices[i * 3 + 1];
    1.97 +    if(self->mVertices[i * 3 + 2] < aGrid->mMin[2])
    1.98 +      aGrid->mMin[2] = self->mVertices[i * 3 + 2];
    1.99 +    else if(self->mVertices[i * 3 + 2] > aGrid->mMax[2])
   1.100 +      aGrid->mMax[2] = self->mVertices[i * 3 + 2];
   1.101 +  }
   1.102 +
   1.103 +  // Determine optimal grid resolution, based on the number of vertices and
   1.104 +  // the bounding box.
   1.105 +  // NOTE: This algorithm is quite crude, and could very well be optimized for
   1.106 +  // better compression levels in the future without affecting the file format
   1.107 +  // or backward compatibility at all.
   1.108 +  for(i = 0; i < 3; ++ i)
   1.109 +    factor[i] = aGrid->mMax[i] - aGrid->mMin[i];
   1.110 +  sum = factor[0] + factor[1] + factor[2];
   1.111 +  if(sum > 1e-30f)
   1.112 +  {
   1.113 +    sum = 1.0f / sum;
   1.114 +    for(i = 0; i < 3; ++ i)
   1.115 +      factor[i] *= sum;
   1.116 +    wantedGrids = powf(100.0f * self->mVertexCount, 1.0f / 3.0f);
   1.117 +    for(i = 0; i < 3; ++ i)
   1.118 +    {
   1.119 +      aGrid->mDivision[i] = (CTMuint) ceilf(wantedGrids * factor[i]);
   1.120 +      if(aGrid->mDivision[i] < 1)
   1.121 +        aGrid->mDivision[i] = 1;
   1.122 +    }
   1.123 +  }
   1.124 +  else
   1.125 +  {
   1.126 +    aGrid->mDivision[0] = 4;
   1.127 +    aGrid->mDivision[1] = 4;
   1.128 +    aGrid->mDivision[2] = 4;
   1.129 +  }
   1.130 +#ifdef __DEBUG_
   1.131 +  printf("Division: (%d %d %d)\n", aGrid->mDivision[0], aGrid->mDivision[1], aGrid->mDivision[2]);
   1.132 +#endif
   1.133 +
   1.134 +  // Calculate grid sizes
   1.135 +  for(i = 0; i < 3; ++ i)
   1.136 +    aGrid->mSize[i] = (aGrid->mMax[i] - aGrid->mMin[i]) / aGrid->mDivision[i];
   1.137 +}
   1.138 +
   1.139 +//-----------------------------------------------------------------------------
   1.140 +// _ctmPointToGridIdx() - Convert a point to a grid index.
   1.141 +//-----------------------------------------------------------------------------
   1.142 +static CTMuint _ctmPointToGridIdx(_CTMgrid * aGrid, CTMfloat * aPoint)
   1.143 +{
   1.144 +  CTMuint i, idx[3];
   1.145 +
   1.146 +  for(i = 0; i < 3; ++ i)
   1.147 +  {
   1.148 +    idx[i] = (CTMuint) floorf((aPoint[i] - aGrid->mMin[i]) / aGrid->mSize[i]);
   1.149 +    if(idx[i] >= aGrid->mDivision[i])
   1.150 +      idx[i] = aGrid->mDivision[i] - 1;
   1.151 +  }
   1.152 +
   1.153 +  return idx[0] + aGrid->mDivision[0] * (idx[1] + aGrid->mDivision[1] * idx[2]);
   1.154 +}
   1.155 +
   1.156 +//-----------------------------------------------------------------------------
   1.157 +// _ctmGridIdxToPoint() - Convert a grid index to a point (the min x/y/z for
   1.158 +// the given grid box).
   1.159 +//-----------------------------------------------------------------------------
   1.160 +static void _ctmGridIdxToPoint(_CTMgrid * aGrid, CTMuint aIdx, CTMfloat * aPoint)
   1.161 +{
   1.162 +  CTMuint gridIdx[3], zdiv, ydiv, i;
   1.163 +
   1.164 +  zdiv = aGrid->mDivision[0] * aGrid->mDivision[1];
   1.165 +  ydiv = aGrid->mDivision[0];
   1.166 +
   1.167 +  gridIdx[2] =  aIdx / zdiv;
   1.168 +  aIdx -= gridIdx[2] * zdiv;
   1.169 +  gridIdx[1] =  aIdx / ydiv;
   1.170 +  aIdx -= gridIdx[1] * ydiv;
   1.171 +  gridIdx[0] = aIdx;
   1.172 +
   1.173 +  for(i = 0; i < 3; ++ i)
   1.174 +    aPoint[i] = gridIdx[i] * aGrid->mSize[i] + aGrid->mMin[i];
   1.175 +}
   1.176 +
   1.177 +//-----------------------------------------------------------------------------
   1.178 +// _compareVertex() - Comparator for the vertex sorting.
   1.179 +//-----------------------------------------------------------------------------
   1.180 +static int _compareVertex(const void * elem1, const void * elem2)
   1.181 +{
   1.182 +  _CTMsortvertex * v1 = (_CTMsortvertex *) elem1;
   1.183 +  _CTMsortvertex * v2 = (_CTMsortvertex *) elem2;
   1.184 +  if(v1->mGridIndex != v2->mGridIndex)
   1.185 +    return v1->mGridIndex - v2->mGridIndex;
   1.186 +  else if(v1->x < v2->x)
   1.187 +    return -1;
   1.188 +  else if(v1->x > v2->x)
   1.189 +    return 1;
   1.190 +  else
   1.191 +    return 0;
   1.192 +}
   1.193 +
   1.194 +//-----------------------------------------------------------------------------
   1.195 +// _ctmSortVertices() - Setup the vertex array. Assign each vertex to a grid
   1.196 +// box, and sort all vertices.
   1.197 +//-----------------------------------------------------------------------------
   1.198 +static void _ctmSortVertices(_CTMcontext * self, _CTMsortvertex * aSortVertices,
   1.199 +  _CTMgrid * aGrid)
   1.200 +{
   1.201 +  CTMuint i;
   1.202 +
   1.203 +  // Prepare sort vertex array
   1.204 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.205 +  {
   1.206 +    // Store vertex properties in the sort vertex array
   1.207 +    aSortVertices[i].x = self->mVertices[i * 3];
   1.208 +    aSortVertices[i].mGridIndex = _ctmPointToGridIdx(aGrid, &self->mVertices[i * 3]);
   1.209 +    aSortVertices[i].mOriginalIndex = i;
   1.210 +  }
   1.211 +
   1.212 +  // Sort vertices. The elements are first sorted by their grid indices, and
   1.213 +  // scondly by their x coordinates.
   1.214 +  qsort((void *) aSortVertices, self->mVertexCount, sizeof(_CTMsortvertex), _compareVertex);
   1.215 +}
   1.216 +
   1.217 +//-----------------------------------------------------------------------------
   1.218 +// _ctmReIndexIndices() - Re-index all indices, based on the sorted vertices.
   1.219 +//-----------------------------------------------------------------------------
   1.220 +static int _ctmReIndexIndices(_CTMcontext * self, _CTMsortvertex * aSortVertices,
   1.221 +  CTMuint * aIndices)
   1.222 +{
   1.223 +  CTMuint i, * indexLUT;
   1.224 +
   1.225 +  // Create temporary lookup-array, O(n)
   1.226 +  indexLUT = (CTMuint *) malloc(sizeof(CTMuint) * self->mVertexCount);
   1.227 +  if(!indexLUT)
   1.228 +  {
   1.229 +    self->mError = CTM_OUT_OF_MEMORY;
   1.230 +    return CTM_FALSE;
   1.231 +  }
   1.232 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.233 +    indexLUT[aSortVertices[i].mOriginalIndex] = i;
   1.234 +
   1.235 +  // Convert old indices to new indices, O(n)
   1.236 +  for(i = 0; i < self->mTriangleCount * 3; ++ i)
   1.237 +    aIndices[i] = indexLUT[self->mIndices[i]];
   1.238 +
   1.239 +  // Free temporary lookup-array
   1.240 +  free((void *) indexLUT);
   1.241 +
   1.242 +  return CTM_TRUE;
   1.243 +}
   1.244 +
   1.245 +//-----------------------------------------------------------------------------
   1.246 +// _compareTriangle() - Comparator for the triangle sorting.
   1.247 +//-----------------------------------------------------------------------------
   1.248 +static int _compareTriangle(const void * elem1, const void * elem2)
   1.249 +{
   1.250 +  CTMuint * tri1 = (CTMuint *) elem1;
   1.251 +  CTMuint * tri2 = (CTMuint *) elem2;
   1.252 +  if(tri1[0] != tri2[0])
   1.253 +    return tri1[0] - tri2[0];
   1.254 +  else
   1.255 +    return tri1[1] - tri2[1];
   1.256 +}
   1.257 +
   1.258 +//-----------------------------------------------------------------------------
   1.259 +// _ctmReArrangeTriangles() - Re-arrange all triangles for optimal
   1.260 +// compression.
   1.261 +//-----------------------------------------------------------------------------
   1.262 +static void _ctmReArrangeTriangles(_CTMcontext * self, CTMuint * aIndices)
   1.263 +{
   1.264 +  CTMuint * tri, tmp, i;
   1.265 +
   1.266 +  // Step 1: Make sure that the first index of each triangle is the smallest
   1.267 +  // one (rotate triangle nodes if necessary)
   1.268 +  for(i = 0; i < self->mTriangleCount; ++ i)
   1.269 +  {
   1.270 +    tri = &aIndices[i * 3];
   1.271 +    if((tri[1] < tri[0]) && (tri[1] < tri[2]))
   1.272 +    {
   1.273 +      tmp = tri[0];
   1.274 +      tri[0] = tri[1];
   1.275 +      tri[1] = tri[2];
   1.276 +      tri[2] = tmp;
   1.277 +    }
   1.278 +    else if((tri[2] < tri[0]) && (tri[2] < tri[1]))
   1.279 +    {
   1.280 +      tmp = tri[0];
   1.281 +      tri[0] = tri[2];
   1.282 +      tri[2] = tri[1];
   1.283 +      tri[1] = tmp;
   1.284 +    }
   1.285 +  }
   1.286 +
   1.287 +  // Step 2: Sort the triangles based on the first triangle index
   1.288 +  qsort((void *) aIndices, self->mTriangleCount, sizeof(CTMuint) * 3, _compareTriangle);
   1.289 +}
   1.290 +
   1.291 +//-----------------------------------------------------------------------------
   1.292 +// _ctmMakeIndexDeltas() - Calculate various forms of derivatives in order to
   1.293 +// reduce data entropy.
   1.294 +//-----------------------------------------------------------------------------
   1.295 +static void _ctmMakeIndexDeltas(_CTMcontext * self, CTMuint * aIndices)
   1.296 +{
   1.297 +  CTMint i;
   1.298 +  for(i = self->mTriangleCount - 1; i >= 0; -- i)
   1.299 +  {
   1.300 +    // Step 1: Calculate delta from second triangle index to the previous
   1.301 +    // second triangle index, if the previous triangle shares the same first
   1.302 +    // index, otherwise calculate the delta to the first triangle index
   1.303 +    if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
   1.304 +      aIndices[i * 3 + 1] -= aIndices[(i - 1) * 3 + 1];
   1.305 +    else
   1.306 +      aIndices[i * 3 + 1] -= aIndices[i * 3];
   1.307 +
   1.308 +    // Step 2: Calculate delta from third triangle index to the first triangle
   1.309 +    // index
   1.310 +    aIndices[i * 3 + 2] -= aIndices[i * 3];
   1.311 +
   1.312 +    // Step 3: Calculate derivative of the first triangle index
   1.313 +    if(i >= 1)
   1.314 +      aIndices[i * 3] -= aIndices[(i - 1) * 3];
   1.315 +  }
   1.316 +}
   1.317 +
   1.318 +//-----------------------------------------------------------------------------
   1.319 +// _ctmRestoreIndices() - Restore original indices (inverse derivative
   1.320 +// operation).
   1.321 +//-----------------------------------------------------------------------------
   1.322 +static void _ctmRestoreIndices(_CTMcontext * self, CTMuint * aIndices)
   1.323 +{
   1.324 +  CTMuint i;
   1.325 +
   1.326 +  for(i = 0; i < self->mTriangleCount; ++ i)
   1.327 +  {
   1.328 +    // Step 1: Reverse derivative of the first triangle index
   1.329 +    if(i >= 1)
   1.330 +      aIndices[i * 3] += aIndices[(i - 1) * 3];
   1.331 +
   1.332 +    // Step 2: Reverse delta from third triangle index to the first triangle
   1.333 +    // index
   1.334 +    aIndices[i * 3 + 2] += aIndices[i * 3];
   1.335 +
   1.336 +    // Step 3: Reverse delta from second triangle index to the previous
   1.337 +    // second triangle index, if the previous triangle shares the same first
   1.338 +    // index, otherwise reverse the delta to the first triangle index
   1.339 +    if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
   1.340 +      aIndices[i * 3 + 1] += aIndices[(i - 1) * 3 + 1];
   1.341 +    else
   1.342 +      aIndices[i * 3 + 1] += aIndices[i * 3];
   1.343 +  }
   1.344 +}
   1.345 +
   1.346 +//-----------------------------------------------------------------------------
   1.347 +// _ctmMakeVertexDeltas() - Calculate various forms of derivatives in order to
   1.348 +// reduce data entropy.
   1.349 +//-----------------------------------------------------------------------------
   1.350 +static void _ctmMakeVertexDeltas(_CTMcontext * self, CTMint * aIntVertices,
   1.351 +  _CTMsortvertex * aSortVertices, _CTMgrid * aGrid)
   1.352 +{
   1.353 +  CTMuint i, gridIdx, prevGridIndex, oldIdx;
   1.354 +  CTMfloat gridOrigin[3], scale;
   1.355 +  CTMint deltaX, prevDeltaX;
   1.356 +
   1.357 +  // Vertex scaling factor
   1.358 +  scale = 1.0f / self->mVertexPrecision;
   1.359 +
   1.360 +  prevGridIndex = 0x7fffffff;
   1.361 +  prevDeltaX = 0;
   1.362 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.363 +  {
   1.364 +    // Get grid box origin
   1.365 +    gridIdx = aSortVertices[i].mGridIndex;
   1.366 +    _ctmGridIdxToPoint(aGrid, gridIdx, gridOrigin);
   1.367 +
   1.368 +    // Get old vertex coordinate index (before vertex sorting)
   1.369 +    oldIdx = aSortVertices[i].mOriginalIndex;
   1.370 +
   1.371 +    // Store delta to the grid box origin in the integer vertex array. For the
   1.372 +    // X axis (which is sorted) we also do the delta to the previous coordinate
   1.373 +    // in the box.
   1.374 +    deltaX = (CTMint) floorf(scale * (self->mVertices[oldIdx * 3] - gridOrigin[0]) + 0.5f);
   1.375 +    if(gridIdx == prevGridIndex)
   1.376 +      aIntVertices[i * 3] = deltaX - prevDeltaX;
   1.377 +    else
   1.378 +      aIntVertices[i * 3] = deltaX;
   1.379 +    aIntVertices[i * 3 + 1] = (CTMint) floorf(scale * (self->mVertices[oldIdx * 3 + 1] - gridOrigin[1]) + 0.5f);
   1.380 +    aIntVertices[i * 3 + 2] = (CTMint) floorf(scale * (self->mVertices[oldIdx * 3 + 2] - gridOrigin[2]) + 0.5f);
   1.381 +
   1.382 +    prevGridIndex = gridIdx;
   1.383 +    prevDeltaX = deltaX;
   1.384 +  }
   1.385 +}
   1.386 +
   1.387 +//-----------------------------------------------------------------------------
   1.388 +// _ctmRestoreVertices() - Calculate inverse derivatives of the vertices.
   1.389 +//-----------------------------------------------------------------------------
   1.390 +static void _ctmRestoreVertices(_CTMcontext * self, CTMint * aIntVertices,
   1.391 +  CTMuint * aGridIndices, _CTMgrid * aGrid, CTMfloat * aVertices)
   1.392 +{
   1.393 +  CTMuint i, gridIdx, prevGridIndex;
   1.394 +  CTMfloat gridOrigin[3], scale;
   1.395 +  CTMint deltaX, prevDeltaX;
   1.396 +
   1.397 +  scale = self->mVertexPrecision;
   1.398 +
   1.399 +  prevGridIndex = 0x7fffffff;
   1.400 +  prevDeltaX = 0;
   1.401 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.402 +  {
   1.403 +    // Get grid box origin
   1.404 +    gridIdx = aGridIndices[i];
   1.405 +    _ctmGridIdxToPoint(aGrid, gridIdx, gridOrigin);
   1.406 +
   1.407 +    // Restore original point
   1.408 +    deltaX = aIntVertices[i * 3];
   1.409 +    if(gridIdx == prevGridIndex)
   1.410 +      deltaX += prevDeltaX;
   1.411 +    aVertices[i * 3] = scale * deltaX + gridOrigin[0];
   1.412 +    aVertices[i * 3 + 1] = scale * aIntVertices[i * 3 + 1] + gridOrigin[1];
   1.413 +    aVertices[i * 3 + 2] = scale * aIntVertices[i * 3 + 2] + gridOrigin[2];
   1.414 +
   1.415 +    prevGridIndex = gridIdx;
   1.416 +    prevDeltaX = deltaX;
   1.417 +  }
   1.418 +}
   1.419 +
   1.420 +//-----------------------------------------------------------------------------
   1.421 +// _ctmCalcSmoothNormals() - Calculate the smooth normals for a given mesh.
   1.422 +// These are used as the nominal normals for normal deltas & reconstruction.
   1.423 +//-----------------------------------------------------------------------------
   1.424 +static void _ctmCalcSmoothNormals(_CTMcontext * self, CTMfloat * aVertices,
   1.425 +  CTMuint * aIndices, CTMfloat * aSmoothNormals)
   1.426 +{
   1.427 +  CTMuint i, j, k, tri[3];
   1.428 +  CTMfloat len;
   1.429 +  CTMfloat v1[3], v2[3], n[3];
   1.430 +
   1.431 +  // Clear smooth normals array
   1.432 +  for(i = 0; i < 3 * self->mVertexCount; ++ i)
   1.433 +    aSmoothNormals[i] = 0.0f;
   1.434 +
   1.435 +  // Calculate sums of all neigbouring triangle normals for each vertex
   1.436 +  for(i = 0; i < self->mTriangleCount; ++ i)
   1.437 +  {
   1.438 +    // Get triangle corner indices
   1.439 +    for(j = 0; j < 3; ++ j)
   1.440 +      tri[j] = aIndices[i * 3 + j];
   1.441 +
   1.442 +    // Calculate the normalized cross product of two triangle edges (i.e. the
   1.443 +    // flat triangle normal)
   1.444 +    for(j = 0; j < 3; ++ j)
   1.445 +    {
   1.446 +      v1[j] = aVertices[tri[1] * 3 + j] - aVertices[tri[0] * 3 + j];
   1.447 +      v2[j] = aVertices[tri[2] * 3 + j] - aVertices[tri[0] * 3 + j];
   1.448 +    }
   1.449 +    n[0] = v1[1] * v2[2] - v1[2] * v2[1];
   1.450 +    n[1] = v1[2] * v2[0] - v1[0] * v2[2];
   1.451 +    n[2] = v1[0] * v2[1] - v1[1] * v2[0];
   1.452 +    len = sqrtf(n[0] * n[0] + n[1] * n[1] + n[2] * n[2]);
   1.453 +    if(len > 1e-10f)
   1.454 +      len = 1.0f / len;
   1.455 +    else
   1.456 +      len = 1.0f;
   1.457 +    for(j = 0; j < 3; ++ j)
   1.458 +      n[j] *= len;
   1.459 +
   1.460 +    // Add the flat normal to all three triangle vertices
   1.461 +    for(k = 0; k < 3; ++ k)
   1.462 +      for(j = 0; j < 3; ++ j)
   1.463 +        aSmoothNormals[tri[k] * 3 + j] += n[j];
   1.464 +  }
   1.465 +
   1.466 +  // Normalize the normal sums, which gives the unit length smooth normals
   1.467 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.468 +  {
   1.469 +    len = sqrtf(aSmoothNormals[i * 3] * aSmoothNormals[i * 3] + 
   1.470 +                aSmoothNormals[i * 3 + 1] * aSmoothNormals[i * 3 + 1] +
   1.471 +                aSmoothNormals[i * 3 + 2] * aSmoothNormals[i * 3 + 2]);
   1.472 +    if(len > 1e-10f)
   1.473 +      len = 1.0f / len;
   1.474 +    else
   1.475 +      len = 1.0f;
   1.476 +    for(j = 0; j < 3; ++ j)
   1.477 +      aSmoothNormals[i * 3 + j] *= len;
   1.478 +  }
   1.479 +}
   1.480 +
   1.481 +//-----------------------------------------------------------------------------
   1.482 +// _ctmMakeNormalCoordSys() - Create an ortho-normalized coordinate system
   1.483 +// where the Z-axis is aligned with the given normal.
   1.484 +// Note 1: This function is central to how the compressed normal data is
   1.485 +//  interpreted, and it can not be changed (mathematically) without making the
   1.486 +//  coder/decoder incompatible with other versions of the library!
   1.487 +// Note 2: Since we do this for every single normal, this routine needs to be
   1.488 +//  fast. The current implementation uses: 12 MUL, 1 DIV, 1 SQRT, ~6 ADD.
   1.489 +//-----------------------------------------------------------------------------
   1.490 +static void _ctmMakeNormalCoordSys(CTMfloat * aNormal, CTMfloat * aBasisAxes)
   1.491 +{
   1.492 +  CTMfloat len, * x, * y, * z;
   1.493 +  CTMuint i;
   1.494 +
   1.495 +  // Pointers to the basis axes (aBasisAxes is a 3x3 matrix)
   1.496 +  x = aBasisAxes;
   1.497 +  y = &aBasisAxes[3];
   1.498 +  z = &aBasisAxes[6];
   1.499 +
   1.500 +  // Z = normal (must be unit length!)
   1.501 +  for(i = 0; i < 3; ++ i)
   1.502 +    z[i] = aNormal[i];
   1.503 +
   1.504 +  // Calculate a vector that is guaranteed to be orthogonal to the normal, non-
   1.505 +  // zero, and a continuous function of the normal (no discrete jumps):
   1.506 +  // X = (0,0,1) x normal + (1,0,0) x normal
   1.507 +  x[0] =  -aNormal[1];
   1.508 +  x[1] =  aNormal[0] - aNormal[2];
   1.509 +  x[2] =  aNormal[1];
   1.510 +
   1.511 +  // Normalize the new X axis (note: |x[2]| = |x[0]|)
   1.512 +  len = sqrtf(2.0 * x[0] * x[0] + x[1] * x[1]);
   1.513 +  if(len > 1.0e-20f)
   1.514 +  {
   1.515 +    len = 1.0f / len;
   1.516 +    x[0] *= len;
   1.517 +    x[1] *= len;
   1.518 +    x[2] *= len;
   1.519 +  }
   1.520 +
   1.521 +  // Let Y = Z x X  (no normalization needed, since |Z| = |X| = 1)
   1.522 +  y[0] = z[1] * x[2] - z[2] * x[1];
   1.523 +  y[1] = z[2] * x[0] - z[0] * x[2];
   1.524 +  y[2] = z[0] * x[1] - z[1] * x[0];
   1.525 +}
   1.526 +
   1.527 +//-----------------------------------------------------------------------------
   1.528 +// _ctmMakeNormalDeltas() - Convert the normals to a new coordinate system:
   1.529 +// magnitude, phi, theta (relative to predicted smooth normals).
   1.530 +//-----------------------------------------------------------------------------
   1.531 +static CTMint _ctmMakeNormalDeltas(_CTMcontext * self, CTMint * aIntNormals,
   1.532 +  CTMfloat * aVertices, CTMuint * aIndices, _CTMsortvertex * aSortVertices)
   1.533 +{
   1.534 +  CTMuint i, j, oldIdx, intPhi;
   1.535 +  CTMfloat magn, phi, theta, scale, thetaScale;
   1.536 +  CTMfloat * smoothNormals, n[3], n2[3], basisAxes[9];
   1.537 +
   1.538 +  // Allocate temporary memory for the nominal vertex normals
   1.539 +  smoothNormals = (CTMfloat *) malloc(3 * sizeof(CTMfloat) * self->mVertexCount);
   1.540 +  if(!smoothNormals)
   1.541 +  {
   1.542 +    self->mError = CTM_OUT_OF_MEMORY;
   1.543 +    return CTM_FALSE;
   1.544 +  }
   1.545 +
   1.546 +  // Calculate smooth normals (Note: aVertices and aIndices use the sorted
   1.547 +  // index space, so smoothNormals will too)
   1.548 +  _ctmCalcSmoothNormals(self, aVertices, aIndices, smoothNormals);
   1.549 +
   1.550 +  // Normal scaling factor
   1.551 +  scale = 1.0f / self->mNormalPrecision;
   1.552 +
   1.553 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.554 +  {
   1.555 +    // Get old normal index (before vertex sorting)
   1.556 +    oldIdx = aSortVertices[i].mOriginalIndex;
   1.557 +
   1.558 +    // Calculate normal magnitude (should always be 1.0 for unit length normals)
   1.559 +    magn = sqrtf(self->mNormals[oldIdx * 3] * self->mNormals[oldIdx * 3] +
   1.560 +                 self->mNormals[oldIdx * 3 + 1] * self->mNormals[oldIdx * 3 + 1] +
   1.561 +                 self->mNormals[oldIdx * 3 + 2] * self->mNormals[oldIdx * 3 + 2]);
   1.562 +    if(magn < 1e-10f)
   1.563 +      magn = 1.0f;
   1.564 +
   1.565 +    // Invert magnitude if the normal is negative compared to the predicted
   1.566 +    // smooth normal
   1.567 +    if((smoothNormals[i * 3] * self->mNormals[oldIdx * 3] +
   1.568 +        smoothNormals[i * 3 + 1] * self->mNormals[oldIdx * 3 + 1] +
   1.569 +        smoothNormals[i * 3 + 2] * self->mNormals[oldIdx * 3 + 2]) < 0.0f)
   1.570 +      magn = -magn;
   1.571 +
   1.572 +    // Store the magnitude in the first element of the three normal elements
   1.573 +    aIntNormals[i * 3] = (CTMint) floorf(scale * magn + 0.5f);
   1.574 +
   1.575 +    // Normalize the normal (1 / magn) - and flip it if magn < 0
   1.576 +    magn = 1.0f / magn;
   1.577 +    for(j = 0; j < 3; ++ j)
   1.578 +      n[j] = self->mNormals[oldIdx * 3 + j] * magn;
   1.579 +
   1.580 +    // Convert the normal to angular representation (phi, theta) in a coordinate
   1.581 +    // system where the nominal (smooth) normal is the Z-axis
   1.582 +    _ctmMakeNormalCoordSys(&smoothNormals[i * 3], basisAxes);
   1.583 +    for(j = 0; j < 3; ++ j)
   1.584 +      n2[j] = basisAxes[j * 3] * n[0] +
   1.585 +              basisAxes[j * 3 + 1] * n[1] +
   1.586 +              basisAxes[j * 3 + 2] * n[2];
   1.587 +    if(n2[2] >= 1.0f)
   1.588 +      phi = 0.0f;
   1.589 +    else
   1.590 +      phi = acosf(n2[2]);
   1.591 +    theta = atan2f(n2[1], n2[0]);
   1.592 +
   1.593 +    // Round phi and theta (spherical coordinates) to integers. Note: We let the
   1.594 +    // theta resolution vary with the x/y circumference (roughly phi).
   1.595 +    intPhi = (CTMint) floorf(phi * (scale / (0.5f * PI)) + 0.5f);
   1.596 +    if(intPhi == 0)
   1.597 +      thetaScale = 0.0f;
   1.598 +    else if(intPhi <= 4)
   1.599 +      thetaScale = 2.0f / PI;
   1.600 +    else
   1.601 +      thetaScale = ((CTMfloat) intPhi) / (2.0f * PI);
   1.602 +    aIntNormals[i * 3 + 1] = intPhi;
   1.603 +    aIntNormals[i * 3 + 2] = (CTMint) floorf((theta + PI) * thetaScale + 0.5f);
   1.604 +  }
   1.605 +
   1.606 +  // Free temporary resources
   1.607 +  free(smoothNormals);
   1.608 +
   1.609 +  return CTM_TRUE;
   1.610 +}
   1.611 +
   1.612 +//-----------------------------------------------------------------------------
   1.613 +// _ctmRestoreNormals() - Convert the normals back to cartesian coordinates.
   1.614 +//-----------------------------------------------------------------------------
   1.615 +static CTMint _ctmRestoreNormals(_CTMcontext * self, CTMint * aIntNormals)
   1.616 +{
   1.617 +  CTMuint i, j, intPhi;
   1.618 +  CTMfloat magn, phi, theta, scale, thetaScale;
   1.619 +  CTMfloat * smoothNormals, n[3], n2[3], basisAxes[9];
   1.620 +
   1.621 +  // Allocate temporary memory for the nominal vertex normals
   1.622 +  smoothNormals = (CTMfloat *) malloc(3 * sizeof(CTMfloat) * self->mVertexCount);
   1.623 +  if(!smoothNormals)
   1.624 +  {
   1.625 +    self->mError = CTM_OUT_OF_MEMORY;
   1.626 +    return CTM_FALSE;
   1.627 +  }
   1.628 +
   1.629 +  // Calculate smooth normals (nominal normals)
   1.630 +  _ctmCalcSmoothNormals(self, self->mVertices, self->mIndices, smoothNormals);
   1.631 +
   1.632 +  // Normal scaling factor
   1.633 +  scale = self->mNormalPrecision;
   1.634 +
   1.635 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.636 +  {
   1.637 +    // Get the normal magnitude from the first of the three normal elements
   1.638 +    magn = aIntNormals[i * 3] * scale;
   1.639 +
   1.640 +    // Get phi and theta (spherical coordinates, relative to the smooth normal).
   1.641 +    intPhi = aIntNormals[i * 3 + 1];
   1.642 +    phi = intPhi * (0.5f * PI) * scale;
   1.643 +    if(intPhi == 0)
   1.644 +      thetaScale = 0.0f;
   1.645 +    else if(intPhi <= 4)
   1.646 +      thetaScale = PI / 2.0f;
   1.647 +    else
   1.648 +      thetaScale = (2.0f * PI) / ((CTMfloat) intPhi);
   1.649 +    theta = aIntNormals[i * 3 + 2] * thetaScale - PI;
   1.650 +
   1.651 +    // Convert the normal from the angular representation (phi, theta) back to
   1.652 +    // cartesian coordinates
   1.653 +    n2[0] = sinf(phi) * cosf(theta);
   1.654 +    n2[1] = sinf(phi) * sinf(theta);
   1.655 +    n2[2] = cosf(phi);
   1.656 +    _ctmMakeNormalCoordSys(&smoothNormals[i * 3], basisAxes);
   1.657 +    for(j = 0; j < 3; ++ j)
   1.658 +      n[j] = basisAxes[j] * n2[0] +
   1.659 +             basisAxes[3 + j] * n2[1] +
   1.660 +             basisAxes[6 + j] * n2[2];
   1.661 +
   1.662 +    // Apply normal magnitude, and output to the normals array
   1.663 +    for(j = 0; j < 3; ++ j)
   1.664 +      self->mNormals[i * 3 + j] = n[j] * magn;
   1.665 +  }
   1.666 +
   1.667 +  // Free temporary resources
   1.668 +  free(smoothNormals);
   1.669 +
   1.670 +  return CTM_TRUE;
   1.671 +}
   1.672 +
   1.673 +//-----------------------------------------------------------------------------
   1.674 +// _ctmMakeUVCoordDeltas() - Calculate various forms of derivatives in order
   1.675 +// to reduce data entropy.
   1.676 +//-----------------------------------------------------------------------------
   1.677 +static void _ctmMakeUVCoordDeltas(_CTMcontext * self, _CTMfloatmap * aMap,
   1.678 +  CTMint * aIntUVCoords, _CTMsortvertex * aSortVertices)
   1.679 +{
   1.680 +  CTMuint i, oldIdx;
   1.681 +  CTMint u, v, prevU, prevV;
   1.682 +  CTMfloat scale;
   1.683 +
   1.684 +  // UV coordinate scaling factor
   1.685 +  scale = 1.0f / aMap->mPrecision;
   1.686 +
   1.687 +  prevU = prevV = 0;
   1.688 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.689 +  {
   1.690 +    // Get old UV coordinate index (before vertex sorting)
   1.691 +    oldIdx = aSortVertices[i].mOriginalIndex;
   1.692 +
   1.693 +    // Convert to fixed point
   1.694 +    u = (CTMint) floorf(scale * aMap->mValues[oldIdx * 2] + 0.5f);
   1.695 +    v = (CTMint) floorf(scale * aMap->mValues[oldIdx * 2 + 1] + 0.5f);
   1.696 +
   1.697 +    // Calculate delta and store it in the converted array. NOTE: Here we rely
   1.698 +    // on the fact that vertices are sorted, and usually close to each other,
   1.699 +    // which means that UV coordinates should also be close to each other...
   1.700 +    aIntUVCoords[i * 2] = u - prevU;
   1.701 +    aIntUVCoords[i * 2 + 1] = v - prevV;
   1.702 +
   1.703 +    prevU = u;
   1.704 +    prevV = v;
   1.705 +  }
   1.706 +}
   1.707 +
   1.708 +//-----------------------------------------------------------------------------
   1.709 +// _ctmRestoreUVCoords() - Calculate inverse derivatives of the UV
   1.710 +// coordinates.
   1.711 +//-----------------------------------------------------------------------------
   1.712 +static void _ctmRestoreUVCoords(_CTMcontext * self, _CTMfloatmap * aMap,
   1.713 +  CTMint * aIntUVCoords)
   1.714 +{
   1.715 +  CTMuint i;
   1.716 +  CTMint u, v, prevU, prevV;
   1.717 +  CTMfloat scale;
   1.718 +
   1.719 +  // UV coordinate scaling factor
   1.720 +  scale = aMap->mPrecision;
   1.721 +
   1.722 +  prevU = prevV = 0;
   1.723 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.724 +  {
   1.725 +    // Calculate inverse delta
   1.726 +    u = aIntUVCoords[i * 2] + prevU;
   1.727 +    v = aIntUVCoords[i * 2 + 1] + prevV;
   1.728 +
   1.729 +    // Convert to floating point
   1.730 +    aMap->mValues[i * 2] = (CTMfloat) u * scale;
   1.731 +    aMap->mValues[i * 2 + 1] = (CTMfloat) v * scale;
   1.732 +
   1.733 +    prevU = u;
   1.734 +    prevV = v;
   1.735 +  }
   1.736 +}
   1.737 +
   1.738 +//-----------------------------------------------------------------------------
   1.739 +// _ctmMakeAttribDeltas() - Calculate various forms of derivatives in order
   1.740 +// to reduce data entropy.
   1.741 +//-----------------------------------------------------------------------------
   1.742 +static void _ctmMakeAttribDeltas(_CTMcontext * self, _CTMfloatmap * aMap,
   1.743 +  CTMint * aIntAttribs, _CTMsortvertex * aSortVertices)
   1.744 +{
   1.745 +  CTMuint i, j, oldIdx;
   1.746 +  CTMint value[4], prev[4];
   1.747 +  CTMfloat scale;
   1.748 +
   1.749 +  // Attribute scaling factor
   1.750 +  scale = 1.0f / aMap->mPrecision;
   1.751 +
   1.752 +  for(j = 0; j < 4; ++ j)
   1.753 +    prev[j] = 0;
   1.754 +
   1.755 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.756 +  {
   1.757 +    // Get old attribute index (before vertex sorting)
   1.758 +    oldIdx = aSortVertices[i].mOriginalIndex;
   1.759 +
   1.760 +    // Convert to fixed point, and calculate delta and store it in the converted
   1.761 +    // array. NOTE: Here we rely on the fact that vertices are sorted, and
   1.762 +    // usually close to each other, which means that attributes should also
   1.763 +    // be close to each other (and we assume that they somehow vary slowly with
   1.764 +    // the geometry)...
   1.765 +    for(j = 0; j < 4; ++ j)
   1.766 +    {
   1.767 +      value[j] = (CTMint) floorf(scale * aMap->mValues[oldIdx * 4 + j] + 0.5f);
   1.768 +      aIntAttribs[i * 4 + j] = value[j] - prev[j];
   1.769 +      prev[j] = value[j];
   1.770 +    }
   1.771 +  }
   1.772 +}
   1.773 +
   1.774 +//-----------------------------------------------------------------------------
   1.775 +// _ctmRestoreAttribs() - Calculate inverse derivatives of the vertex
   1.776 +// attributes.
   1.777 +//-----------------------------------------------------------------------------
   1.778 +static void _ctmRestoreAttribs(_CTMcontext * self, _CTMfloatmap * aMap,
   1.779 +  CTMint * aIntAttribs)
   1.780 +{
   1.781 +  CTMuint i, j;
   1.782 +  CTMint value[4], prev[4];
   1.783 +  CTMfloat scale;
   1.784 +
   1.785 +  // Attribute scaling factor
   1.786 +  scale = aMap->mPrecision;
   1.787 +
   1.788 +  for(j = 0; j < 4; ++ j)
   1.789 +    prev[j] = 0;
   1.790 +
   1.791 +  for(i = 0; i < self->mVertexCount; ++ i)
   1.792 +  {
   1.793 +    // Calculate inverse delta, and convert to floating point
   1.794 +    for(j = 0; j < 4; ++ j)
   1.795 +    {
   1.796 +      value[j] = aIntAttribs[i * 4 + j] + prev[j];
   1.797 +      aMap->mValues[i * 4 + j] = (CTMfloat) value[j] * scale;
   1.798 +      prev[j] = value[j];
   1.799 +    }
   1.800 +  }
   1.801 +}
   1.802 +
   1.803 +//-----------------------------------------------------------------------------
   1.804 +// _ctmCompressMesh_MG2() - Compress the mesh that is stored in the CTM
   1.805 +// context, and write it the the output stream in the CTM context.
   1.806 +//-----------------------------------------------------------------------------
   1.807 +int _ctmCompressMesh_MG2(_CTMcontext * self)
   1.808 +{
   1.809 +  _CTMgrid grid;
   1.810 +  _CTMsortvertex * sortVertices;
   1.811 +  _CTMfloatmap * map;
   1.812 +  CTMuint * indices, * deltaIndices, * gridIndices;
   1.813 +  CTMint * intVertices, * intNormals, * intUVCoords, * intAttribs;
   1.814 +  CTMfloat * restoredVertices;
   1.815 +  CTMuint i;
   1.816 +
   1.817 +#ifdef __DEBUG_
   1.818 +  printf("COMPRESSION METHOD: MG2\n");
   1.819 +#endif
   1.820 +
   1.821 +  // Setup 3D space subdivision grid
   1.822 +  _ctmSetupGrid(self, &grid);
   1.823 +
   1.824 +  // Write MG2-specific header information to the stream
   1.825 +  _ctmStreamWrite(self, (void *) "MG2H", 4);
   1.826 +  _ctmStreamWriteFLOAT(self, self->mVertexPrecision);
   1.827 +  _ctmStreamWriteFLOAT(self, self->mNormalPrecision);
   1.828 +  _ctmStreamWriteFLOAT(self, grid.mMin[0]);
   1.829 +  _ctmStreamWriteFLOAT(self, grid.mMin[1]);
   1.830 +  _ctmStreamWriteFLOAT(self, grid.mMin[2]);
   1.831 +  _ctmStreamWriteFLOAT(self, grid.mMax[0]);
   1.832 +  _ctmStreamWriteFLOAT(self, grid.mMax[1]);
   1.833 +  _ctmStreamWriteFLOAT(self, grid.mMax[2]);
   1.834 +  _ctmStreamWriteUINT(self, grid.mDivision[0]);
   1.835 +  _ctmStreamWriteUINT(self, grid.mDivision[1]);
   1.836 +  _ctmStreamWriteUINT(self, grid.mDivision[2]);
   1.837 +
   1.838 +  // Prepare (sort) vertices
   1.839 +  sortVertices = (_CTMsortvertex *) malloc(sizeof(_CTMsortvertex) * self->mVertexCount);
   1.840 +  if(!sortVertices)
   1.841 +  {
   1.842 +    self->mError = CTM_OUT_OF_MEMORY;
   1.843 +    return CTM_FALSE;
   1.844 +  }
   1.845 +  _ctmSortVertices(self, sortVertices, &grid);
   1.846 +
   1.847 +  // Convert vertices to integers and calculate vertex deltas (entropy-reduction)
   1.848 +  intVertices = (CTMint *) malloc(sizeof(CTMint) * 3 * self->mVertexCount);
   1.849 +  if(!intVertices)
   1.850 +  {
   1.851 +    self->mError = CTM_OUT_OF_MEMORY;
   1.852 +    free((void *) sortVertices);
   1.853 +    return CTM_FALSE;
   1.854 +  }
   1.855 +  _ctmMakeVertexDeltas(self, intVertices, sortVertices, &grid);
   1.856 +
   1.857 +  // Write vertices
   1.858 +#ifdef __DEBUG_
   1.859 +  printf("Vertices: ");
   1.860 +#endif
   1.861 +  _ctmStreamWrite(self, (void *) "VERT", 4);
   1.862 +  if(!_ctmStreamWritePackedInts(self, intVertices, self->mVertexCount, 3, CTM_FALSE))
   1.863 +  {
   1.864 +    free((void *) intVertices);
   1.865 +    free((void *) sortVertices);
   1.866 +    return CTM_FALSE;
   1.867 +  }
   1.868 +
   1.869 +  // Prepare grid indices (deltas)
   1.870 +  gridIndices = (CTMuint *) malloc(sizeof(CTMuint) * self->mVertexCount);
   1.871 +  if(!gridIndices)
   1.872 +  {
   1.873 +    self->mError = CTM_OUT_OF_MEMORY;
   1.874 +    free((void *) intVertices);
   1.875 +    free((void *) sortVertices);
   1.876 +    return CTM_FALSE;
   1.877 +  }
   1.878 +  gridIndices[0] = sortVertices[0].mGridIndex;
   1.879 +  for(i = 1; i < self->mVertexCount; ++ i)
   1.880 +    gridIndices[i] = sortVertices[i].mGridIndex - sortVertices[i - 1].mGridIndex;
   1.881 +  
   1.882 +  // Write grid indices
   1.883 +#ifdef __DEBUG_
   1.884 +  printf("Grid indices: ");
   1.885 +#endif
   1.886 +  _ctmStreamWrite(self, (void *) "GIDX", 4);
   1.887 +  if(!_ctmStreamWritePackedInts(self, (CTMint *) gridIndices, self->mVertexCount, 1, CTM_FALSE))
   1.888 +  {
   1.889 +    free((void *) gridIndices);
   1.890 +    free((void *) intVertices);
   1.891 +    free((void *) sortVertices);
   1.892 +    return CTM_FALSE;
   1.893 +  }
   1.894 +
   1.895 +  // Calculate the result of the compressed -> decompressed vertices, in order
   1.896 +  // to use the same vertex data for calculating nominal normals as the
   1.897 +  // decompression routine (i.e. compensate for the vertex error when
   1.898 +  // calculating the normals)
   1.899 +  restoredVertices = (CTMfloat *) malloc(sizeof(CTMfloat) * 3 * self->mVertexCount);
   1.900 +  if(!restoredVertices)
   1.901 +  {
   1.902 +    self->mError = CTM_OUT_OF_MEMORY;
   1.903 +    free((void *) gridIndices);
   1.904 +    free((void *) intVertices);
   1.905 +    free((void *) sortVertices);
   1.906 +    return CTM_FALSE;
   1.907 +  }
   1.908 +  for(i = 1; i < self->mVertexCount; ++ i)
   1.909 +    gridIndices[i] += gridIndices[i - 1];
   1.910 +  _ctmRestoreVertices(self, intVertices, gridIndices, &grid, restoredVertices);
   1.911 +
   1.912 +  // Free temporary resources
   1.913 +  free((void *) gridIndices);
   1.914 +  free((void *) intVertices);
   1.915 +
   1.916 +  // Perpare (sort) indices
   1.917 +  indices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
   1.918 +  if(!indices)
   1.919 +  {
   1.920 +    self->mError = CTM_OUT_OF_MEMORY;
   1.921 +    free((void *) restoredVertices);
   1.922 +    free((void *) sortVertices);
   1.923 +    return CTM_FALSE;
   1.924 +  }
   1.925 +  if(!_ctmReIndexIndices(self, sortVertices, indices))
   1.926 +  {
   1.927 +    free((void *) indices);
   1.928 +    free((void *) restoredVertices);
   1.929 +    free((void *) sortVertices);
   1.930 +    return CTM_FALSE;
   1.931 +  }
   1.932 +  _ctmReArrangeTriangles(self, indices);
   1.933 +
   1.934 +  // Calculate index deltas (entropy-reduction)
   1.935 +  deltaIndices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
   1.936 +  if(!indices)
   1.937 +  {
   1.938 +    self->mError = CTM_OUT_OF_MEMORY;
   1.939 +    free((void *) indices);
   1.940 +    free((void *) restoredVertices);
   1.941 +    free((void *) sortVertices);
   1.942 +    return CTM_FALSE;
   1.943 +  }
   1.944 +  for(i = 0; i < self->mTriangleCount * 3; ++ i)
   1.945 +    deltaIndices[i] = indices[i];
   1.946 +  _ctmMakeIndexDeltas(self, deltaIndices);
   1.947 +
   1.948 +  // Write triangle indices
   1.949 +#ifdef __DEBUG_
   1.950 +  printf("Indices: ");
   1.951 +#endif
   1.952 +  _ctmStreamWrite(self, (void *) "INDX", 4);
   1.953 +  if(!_ctmStreamWritePackedInts(self, (CTMint *) deltaIndices, self->mTriangleCount, 3, CTM_FALSE))
   1.954 +  {
   1.955 +    free((void *) deltaIndices);
   1.956 +    free((void *) indices);
   1.957 +    free((void *) restoredVertices);
   1.958 +    free((void *) sortVertices);
   1.959 +    return CTM_FALSE;
   1.960 +  }
   1.961 +
   1.962 +  // Free temporary data for the indices
   1.963 +  free((void *) deltaIndices);
   1.964 +
   1.965 +  if(self->mNormals)
   1.966 +  {
   1.967 +    // Convert normals to integers and calculate deltas (entropy-reduction)
   1.968 +    intNormals = (CTMint *) malloc(sizeof(CTMint) * 3 * self->mVertexCount);
   1.969 +    if(!intNormals)
   1.970 +    {
   1.971 +      self->mError = CTM_OUT_OF_MEMORY;
   1.972 +      free((void *) indices);
   1.973 +      free((void *) restoredVertices);
   1.974 +      free((void *) sortVertices);
   1.975 +      return CTM_FALSE;
   1.976 +    }
   1.977 +    if(!_ctmMakeNormalDeltas(self, intNormals, restoredVertices, indices, sortVertices))
   1.978 +    {
   1.979 +      free((void *) indices);
   1.980 +      free((void *) intNormals);
   1.981 +      free((void *) restoredVertices);
   1.982 +      free((void *) sortVertices);
   1.983 +      return CTM_FALSE;
   1.984 +    }
   1.985 +
   1.986 +    // Write normals
   1.987 +#ifdef __DEBUG_
   1.988 +    printf("Normals: ");
   1.989 +#endif
   1.990 +    _ctmStreamWrite(self, (void *) "NORM", 4);
   1.991 +    if(!_ctmStreamWritePackedInts(self, intNormals, self->mVertexCount, 3, CTM_FALSE))
   1.992 +    {
   1.993 +      free((void *) indices);
   1.994 +      free((void *) intNormals);
   1.995 +      free((void *) restoredVertices);
   1.996 +      free((void *) sortVertices);
   1.997 +      return CTM_FALSE;
   1.998 +    }
   1.999 +
  1.1000 +    // Free temporary normal data
  1.1001 +    free((void *) intNormals);
  1.1002 +  }
  1.1003 +
  1.1004 +  // Free restored indices and vertices
  1.1005 +  free((void *) indices);
  1.1006 +  free((void *) restoredVertices);
  1.1007 +
  1.1008 +  // Write UV maps
  1.1009 +  map = self->mUVMaps;
  1.1010 +  while(map)
  1.1011 +  {
  1.1012 +    // Convert UV coordinates to integers and calculate deltas (entropy-reduction)
  1.1013 +    intUVCoords = (CTMint *) malloc(sizeof(CTMint) * 2 * self->mVertexCount);
  1.1014 +    if(!intUVCoords)
  1.1015 +    {
  1.1016 +      self->mError = CTM_OUT_OF_MEMORY;
  1.1017 +      free((void *) sortVertices);
  1.1018 +      return CTM_FALSE;
  1.1019 +    }
  1.1020 +    _ctmMakeUVCoordDeltas(self, map, intUVCoords, sortVertices);
  1.1021 +
  1.1022 +    // Write UV coordinates
  1.1023 +#ifdef __DEBUG_
  1.1024 +    printf("Texture coordinates (%s): ", map->mName ? map->mName : "no name");
  1.1025 +#endif
  1.1026 +    _ctmStreamWrite(self, (void *) "TEXC", 4);
  1.1027 +    _ctmStreamWriteSTRING(self, map->mName);
  1.1028 +    _ctmStreamWriteSTRING(self, map->mFileName);
  1.1029 +    _ctmStreamWriteFLOAT(self, map->mPrecision);
  1.1030 +    if(!_ctmStreamWritePackedInts(self, intUVCoords, self->mVertexCount, 2, CTM_TRUE))
  1.1031 +    {
  1.1032 +      free((void *) intUVCoords);
  1.1033 +      free((void *) sortVertices);
  1.1034 +      return CTM_FALSE;
  1.1035 +    }
  1.1036 +
  1.1037 +    // Free temporary UV coordinate data
  1.1038 +    free((void *) intUVCoords);
  1.1039 +
  1.1040 +    map = map->mNext;
  1.1041 +  }
  1.1042 +
  1.1043 +  // Write vertex attribute maps
  1.1044 +  map = self->mAttribMaps;
  1.1045 +  while(map)
  1.1046 +  {
  1.1047 +    // Convert vertex attributes to integers and calculate deltas (entropy-reduction)
  1.1048 +    intAttribs = (CTMint *) malloc(sizeof(CTMint) * 4 * self->mVertexCount);
  1.1049 +    if(!intAttribs)
  1.1050 +    {
  1.1051 +      self->mError = CTM_OUT_OF_MEMORY;
  1.1052 +      free((void *) sortVertices);
  1.1053 +      return CTM_FALSE;
  1.1054 +    }
  1.1055 +    _ctmMakeAttribDeltas(self, map, intAttribs, sortVertices);
  1.1056 +
  1.1057 +    // Write vertex attributes
  1.1058 +#ifdef __DEBUG_
  1.1059 +    printf("Vertex attributes (%s): ", map->mName ? map->mName : "no name");
  1.1060 +#endif
  1.1061 +    _ctmStreamWrite(self, (void *) "ATTR", 4);
  1.1062 +    _ctmStreamWriteSTRING(self, map->mName);
  1.1063 +    _ctmStreamWriteFLOAT(self, map->mPrecision);
  1.1064 +    if(!_ctmStreamWritePackedInts(self, intAttribs, self->mVertexCount, 4, CTM_TRUE))
  1.1065 +    {
  1.1066 +      free((void *) intAttribs);
  1.1067 +      free((void *) sortVertices);
  1.1068 +      return CTM_FALSE;
  1.1069 +    }
  1.1070 +
  1.1071 +    // Free temporary vertex attribute data
  1.1072 +    free((void *) intAttribs);
  1.1073 +
  1.1074 +    map = map->mNext;
  1.1075 +  }
  1.1076 +
  1.1077 +  // Free temporary data
  1.1078 +  free((void *) sortVertices);
  1.1079 +
  1.1080 +  return CTM_TRUE;
  1.1081 +}
  1.1082 +
  1.1083 +//-----------------------------------------------------------------------------
  1.1084 +// _ctmUncompressMesh_MG2() - Uncmpress the mesh from the input stream in the
  1.1085 +// CTM context, and store the resulting mesh in the CTM context.
  1.1086 +//-----------------------------------------------------------------------------
  1.1087 +int _ctmUncompressMesh_MG2(_CTMcontext * self)
  1.1088 +{
  1.1089 +  CTMuint * gridIndices, i;
  1.1090 +  CTMint * intVertices, * intNormals, * intUVCoords, * intAttribs;
  1.1091 +  _CTMfloatmap * map;
  1.1092 +  _CTMgrid grid;
  1.1093 +
  1.1094 +  // Read MG2-specific header information from the stream
  1.1095 +  if(_ctmStreamReadUINT(self) != FOURCC("MG2H"))
  1.1096 +  {
  1.1097 +    self->mError = CTM_BAD_FORMAT;
  1.1098 +    return CTM_FALSE;
  1.1099 +  }
  1.1100 +  self->mVertexPrecision = _ctmStreamReadFLOAT(self);
  1.1101 +  if(self->mVertexPrecision <= 0.0f)
  1.1102 +  {
  1.1103 +    self->mError = CTM_BAD_FORMAT;
  1.1104 +    return CTM_FALSE;
  1.1105 +  }
  1.1106 +  self->mNormalPrecision = _ctmStreamReadFLOAT(self);
  1.1107 +  if(self->mNormalPrecision <= 0.0f)
  1.1108 +  {
  1.1109 +    self->mError = CTM_BAD_FORMAT;
  1.1110 +    return CTM_FALSE;
  1.1111 +  }
  1.1112 +  grid.mMin[0] = _ctmStreamReadFLOAT(self);
  1.1113 +  grid.mMin[1] = _ctmStreamReadFLOAT(self);
  1.1114 +  grid.mMin[2] = _ctmStreamReadFLOAT(self);
  1.1115 +  grid.mMax[0] = _ctmStreamReadFLOAT(self);
  1.1116 +  grid.mMax[1] = _ctmStreamReadFLOAT(self);
  1.1117 +  grid.mMax[2] = _ctmStreamReadFLOAT(self);
  1.1118 +  if((grid.mMax[0] < grid.mMin[0]) ||
  1.1119 +     (grid.mMax[1] < grid.mMin[1]) ||
  1.1120 +     (grid.mMax[2] < grid.mMin[2]))
  1.1121 +  {
  1.1122 +    self->mError = CTM_BAD_FORMAT;
  1.1123 +    return CTM_FALSE;
  1.1124 +  }
  1.1125 +  grid.mDivision[0] = _ctmStreamReadUINT(self);
  1.1126 +  grid.mDivision[1] = _ctmStreamReadUINT(self);
  1.1127 +  grid.mDivision[2] = _ctmStreamReadUINT(self);
  1.1128 +  if((grid.mDivision[0] < 1) || (grid.mDivision[1] < 1) || (grid.mDivision[2] < 1))
  1.1129 +  {
  1.1130 +    self->mError = CTM_BAD_FORMAT;
  1.1131 +    return CTM_FALSE;
  1.1132 +  }
  1.1133 +
  1.1134 +  // Initialize 3D space subdivision grid
  1.1135 +  for(i = 0; i < 3; ++ i)
  1.1136 +    grid.mSize[i] = (grid.mMax[i] - grid.mMin[i]) / grid.mDivision[i];
  1.1137 +
  1.1138 +  // Read vertices
  1.1139 +  if(_ctmStreamReadUINT(self) != FOURCC("VERT"))
  1.1140 +  {
  1.1141 +    self->mError = CTM_BAD_FORMAT;
  1.1142 +    return CTM_FALSE;
  1.1143 +  }
  1.1144 +  intVertices = (CTMint *) malloc(sizeof(CTMint) * self->mVertexCount * 3);
  1.1145 +  if(!intVertices)
  1.1146 +  {
  1.1147 +    self->mError = CTM_OUT_OF_MEMORY;
  1.1148 +    return CTM_FALSE;
  1.1149 +  }
  1.1150 +  if(!_ctmStreamReadPackedInts(self, intVertices, self->mVertexCount, 3, CTM_FALSE))
  1.1151 +  {
  1.1152 +    free((void *) intVertices);
  1.1153 +    return CTM_FALSE;
  1.1154 +  }
  1.1155 +
  1.1156 +  // Read grid indices
  1.1157 +  if(_ctmStreamReadUINT(self) != FOURCC("GIDX"))
  1.1158 +  {
  1.1159 +    free((void *) intVertices);
  1.1160 +    self->mError = CTM_BAD_FORMAT;
  1.1161 +    return CTM_FALSE;
  1.1162 +  }
  1.1163 +  gridIndices = (CTMuint *) malloc(sizeof(CTMuint) * self->mVertexCount);
  1.1164 +  if(!gridIndices)
  1.1165 +  {
  1.1166 +    self->mError = CTM_OUT_OF_MEMORY;
  1.1167 +    free((void *) intVertices);
  1.1168 +    return CTM_FALSE;
  1.1169 +  }
  1.1170 +  if(!_ctmStreamReadPackedInts(self, (CTMint *) gridIndices, self->mVertexCount, 1, CTM_FALSE))
  1.1171 +  {
  1.1172 +    free((void *) gridIndices);
  1.1173 +    free((void *) intVertices);
  1.1174 +    return CTM_FALSE;
  1.1175 +  }
  1.1176 +
  1.1177 +  // Restore grid indices (deltas)
  1.1178 +  for(i = 1; i < self->mVertexCount; ++ i)
  1.1179 +    gridIndices[i] += gridIndices[i - 1];
  1.1180 +
  1.1181 +  // Restore vertices
  1.1182 +  _ctmRestoreVertices(self, intVertices, gridIndices, &grid, self->mVertices);
  1.1183 +
  1.1184 +  // Free temporary resources
  1.1185 +  free((void *) gridIndices);
  1.1186 +  free((void *) intVertices);
  1.1187 +
  1.1188 +  // Read triangle indices
  1.1189 +  if(_ctmStreamReadUINT(self) != FOURCC("INDX"))
  1.1190 +  {
  1.1191 +    self->mError = CTM_BAD_FORMAT;
  1.1192 +    return CTM_FALSE;
  1.1193 +  }
  1.1194 +  if(!_ctmStreamReadPackedInts(self, (CTMint *) self->mIndices, self->mTriangleCount, 3, CTM_FALSE))
  1.1195 +    return CTM_FALSE;
  1.1196 +
  1.1197 +  // Restore indices
  1.1198 +  _ctmRestoreIndices(self, self->mIndices);
  1.1199 +
  1.1200 +  // Check that all indices are within range
  1.1201 +  for(i = 0; i < (self->mTriangleCount * 3); ++ i)
  1.1202 +  {
  1.1203 +    if(self->mIndices[i] >= self->mVertexCount)
  1.1204 +    {
  1.1205 +      self->mError = CTM_INVALID_MESH;
  1.1206 +      return CTM_FALSE;
  1.1207 +    }
  1.1208 +  }
  1.1209 +
  1.1210 +  // Read normals
  1.1211 +  if(self->mNormals)
  1.1212 +  {
  1.1213 +    intNormals = (CTMint *) malloc(sizeof(CTMint) * self->mVertexCount * 3);
  1.1214 +    if(!intNormals)
  1.1215 +    {
  1.1216 +      self->mError = CTM_OUT_OF_MEMORY;
  1.1217 +      return CTM_FALSE;
  1.1218 +    }
  1.1219 +    if(_ctmStreamReadUINT(self) != FOURCC("NORM"))
  1.1220 +    {
  1.1221 +      self->mError = CTM_BAD_FORMAT;
  1.1222 +      free((void *) intNormals);
  1.1223 +      return CTM_FALSE;
  1.1224 +    }
  1.1225 +    if(!_ctmStreamReadPackedInts(self, intNormals, self->mVertexCount, 3, CTM_FALSE))
  1.1226 +    {
  1.1227 +      free((void *) intNormals);
  1.1228 +      return CTM_FALSE;
  1.1229 +    }
  1.1230 +
  1.1231 +    // Restore normals
  1.1232 +    if(!_ctmRestoreNormals(self, intNormals))
  1.1233 +    {
  1.1234 +      free((void *) intNormals);
  1.1235 +      return CTM_FALSE;
  1.1236 +    }
  1.1237 +
  1.1238 +    // Free temporary normals data
  1.1239 +    free((void *) intNormals);
  1.1240 +  }
  1.1241 +
  1.1242 +  // Read UV maps
  1.1243 +  map = self->mUVMaps;
  1.1244 +  while(map)
  1.1245 +  {
  1.1246 +    intUVCoords = (CTMint *) malloc(sizeof(CTMint) * self->mVertexCount * 2);
  1.1247 +    if(!intUVCoords)
  1.1248 +    {
  1.1249 +      self->mError = CTM_OUT_OF_MEMORY;
  1.1250 +      return CTM_FALSE;
  1.1251 +    }
  1.1252 +    if(_ctmStreamReadUINT(self) != FOURCC("TEXC"))
  1.1253 +    {
  1.1254 +      self->mError = CTM_BAD_FORMAT;
  1.1255 +      free((void *) intUVCoords);
  1.1256 +      return CTM_FALSE;
  1.1257 +    }
  1.1258 +    _ctmStreamReadSTRING(self, &map->mName);
  1.1259 +    _ctmStreamReadSTRING(self, &map->mFileName);
  1.1260 +    map->mPrecision = _ctmStreamReadFLOAT(self);
  1.1261 +    if(map->mPrecision <= 0.0f)
  1.1262 +    {
  1.1263 +      self->mError = CTM_BAD_FORMAT;
  1.1264 +      free((void *) intUVCoords);
  1.1265 +      return CTM_FALSE;
  1.1266 +    }
  1.1267 +    if(!_ctmStreamReadPackedInts(self, intUVCoords, self->mVertexCount, 2, CTM_TRUE))
  1.1268 +    {
  1.1269 +      free((void *) intUVCoords);
  1.1270 +      return CTM_FALSE;
  1.1271 +    }
  1.1272 +
  1.1273 +    // Restore UV coordinates
  1.1274 +    _ctmRestoreUVCoords(self, map, intUVCoords);
  1.1275 +
  1.1276 +    // Free temporary UV coordinate data
  1.1277 +    free((void *) intUVCoords);
  1.1278 +
  1.1279 +    map = map->mNext;
  1.1280 +  }
  1.1281 +
  1.1282 +  // Read vertex attribute maps
  1.1283 +  map = self->mAttribMaps;
  1.1284 +  while(map)
  1.1285 +  {
  1.1286 +    intAttribs = (CTMint *) malloc(sizeof(CTMint) * self->mVertexCount * 4);
  1.1287 +    if(!intAttribs)
  1.1288 +    {
  1.1289 +      self->mError = CTM_OUT_OF_MEMORY;
  1.1290 +      return CTM_FALSE;
  1.1291 +    }
  1.1292 +    if(_ctmStreamReadUINT(self) != FOURCC("ATTR"))
  1.1293 +    {
  1.1294 +      self->mError = CTM_BAD_FORMAT;
  1.1295 +      free((void *) intAttribs);
  1.1296 +      return CTM_FALSE;
  1.1297 +    }
  1.1298 +    _ctmStreamReadSTRING(self, &map->mName);
  1.1299 +    map->mPrecision = _ctmStreamReadFLOAT(self);
  1.1300 +    if(map->mPrecision <= 0.0f)
  1.1301 +    {
  1.1302 +      self->mError = CTM_BAD_FORMAT;
  1.1303 +      free((void *) intAttribs);
  1.1304 +      return CTM_FALSE;
  1.1305 +    }
  1.1306 +    if(!_ctmStreamReadPackedInts(self, intAttribs, self->mVertexCount, 4, CTM_TRUE))
  1.1307 +    {
  1.1308 +      free((void *) intAttribs);
  1.1309 +      return CTM_FALSE;
  1.1310 +    }
  1.1311 +
  1.1312 +    // Restore vertex attributes
  1.1313 +    _ctmRestoreAttribs(self, map, intAttribs);
  1.1314 +
  1.1315 +    // Free temporary vertex attribute data
  1.1316 +    free((void *) intAttribs);
  1.1317 +
  1.1318 +    map = map->mNext;
  1.1319 +  }
  1.1320 +
  1.1321 +  return CTM_TRUE;
  1.1322 +}