1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/openctm/compressMG1.c	Thu Sep 26 04:47:05 2013 +0300
     1.3 @@ -0,0 +1,324 @@
     1.4 +//-----------------------------------------------------------------------------
     1.5 +// Product:     OpenCTM
     1.6 +// File:        compressMG1.c
     1.7 +// Description: Implementation of the MG1 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 +
    1.41 +//-----------------------------------------------------------------------------
    1.42 +// _compareTriangle() - Comparator for the triangle sorting.
    1.43 +//-----------------------------------------------------------------------------
    1.44 +static int _compareTriangle(const void * elem1, const void * elem2)
    1.45 +{
    1.46 +  CTMuint * tri1 = (CTMuint *) elem1;
    1.47 +  CTMuint * tri2 = (CTMuint *) elem2;
    1.48 +  if(tri1[0] != tri2[0])
    1.49 +    return tri1[0] - tri2[0];
    1.50 +  else
    1.51 +    return tri1[1] - tri2[1];
    1.52 +}
    1.53 +
    1.54 +//-----------------------------------------------------------------------------
    1.55 +// _ctmReArrangeTriangles() - Re-arrange all triangles for optimal
    1.56 +// compression.
    1.57 +//-----------------------------------------------------------------------------
    1.58 +static void _ctmReArrangeTriangles(_CTMcontext * self, CTMuint * aIndices)
    1.59 +{
    1.60 +  CTMuint * tri, tmp, i;
    1.61 +
    1.62 +  // Step 1: Make sure that the first index of each triangle is the smallest
    1.63 +  // one (rotate triangle nodes if necessary)
    1.64 +  for(i = 0; i < self->mTriangleCount; ++ i)
    1.65 +  {
    1.66 +    tri = &aIndices[i * 3];
    1.67 +    if((tri[1] < tri[0]) && (tri[1] < tri[2]))
    1.68 +    {
    1.69 +      tmp = tri[0];
    1.70 +      tri[0] = tri[1];
    1.71 +      tri[1] = tri[2];
    1.72 +      tri[2] = tmp;
    1.73 +    }
    1.74 +    else if((tri[2] < tri[0]) && (tri[2] < tri[1]))
    1.75 +    {
    1.76 +      tmp = tri[0];
    1.77 +      tri[0] = tri[2];
    1.78 +      tri[2] = tri[1];
    1.79 +      tri[1] = tmp;
    1.80 +    }
    1.81 +  }
    1.82 +
    1.83 +  // Step 2: Sort the triangles based on the first triangle index
    1.84 +  qsort((void *) aIndices, self->mTriangleCount, sizeof(CTMuint) * 3, _compareTriangle);
    1.85 +}
    1.86 +
    1.87 +//-----------------------------------------------------------------------------
    1.88 +// _ctmMakeIndexDeltas() - Calculate various forms of derivatives in order to
    1.89 +// reduce data entropy.
    1.90 +//-----------------------------------------------------------------------------
    1.91 +static void _ctmMakeIndexDeltas(_CTMcontext * self, CTMuint * aIndices)
    1.92 +{
    1.93 +  CTMint i;
    1.94 +  for(i = self->mTriangleCount - 1; i >= 0; -- i)
    1.95 +  {
    1.96 +    // Step 1: Calculate delta from second triangle index to the previous
    1.97 +    // second triangle index, if the previous triangle shares the same first
    1.98 +    // index, otherwise calculate the delta to the first triangle index
    1.99 +    if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
   1.100 +      aIndices[i * 3 + 1] -= aIndices[(i - 1) * 3 + 1];
   1.101 +    else
   1.102 +      aIndices[i * 3 + 1] -= aIndices[i * 3];
   1.103 +
   1.104 +    // Step 2: Calculate delta from third triangle index to the first triangle
   1.105 +    // index
   1.106 +    aIndices[i * 3 + 2] -= aIndices[i * 3];
   1.107 +
   1.108 +    // Step 3: Calculate derivative of the first triangle index
   1.109 +    if(i >= 1)
   1.110 +      aIndices[i * 3] -= aIndices[(i - 1) * 3];
   1.111 +  }
   1.112 +}
   1.113 +
   1.114 +//-----------------------------------------------------------------------------
   1.115 +// _ctmRestoreIndices() - Restore original indices (inverse derivative
   1.116 +// operation).
   1.117 +//-----------------------------------------------------------------------------
   1.118 +static void _ctmRestoreIndices(_CTMcontext * self, CTMuint * aIndices)
   1.119 +{
   1.120 +  CTMuint i;
   1.121 +
   1.122 +  for(i = 0; i < self->mTriangleCount; ++ i)
   1.123 +  {
   1.124 +    // Step 1: Reverse derivative of the first triangle index
   1.125 +    if(i >= 1)
   1.126 +      aIndices[i * 3] += aIndices[(i - 1) * 3];
   1.127 +
   1.128 +    // Step 2: Reverse delta from third triangle index to the first triangle
   1.129 +    // index
   1.130 +    aIndices[i * 3 + 2] += aIndices[i * 3];
   1.131 +
   1.132 +    // Step 3: Reverse delta from second triangle index to the previous
   1.133 +    // second triangle index, if the previous triangle shares the same first
   1.134 +    // index, otherwise reverse the delta to the first triangle index
   1.135 +    if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
   1.136 +      aIndices[i * 3 + 1] += aIndices[(i - 1) * 3 + 1];
   1.137 +    else
   1.138 +      aIndices[i * 3 + 1] += aIndices[i * 3];
   1.139 +  }
   1.140 +}
   1.141 +
   1.142 +//-----------------------------------------------------------------------------
   1.143 +// _ctmCompressMesh_MG1() - Compress the mesh that is stored in the CTM
   1.144 +// context, and write it the the output stream in the CTM context.
   1.145 +//-----------------------------------------------------------------------------
   1.146 +int _ctmCompressMesh_MG1(_CTMcontext * self)
   1.147 +{
   1.148 +  CTMuint * indices;
   1.149 +  _CTMfloatmap * map;
   1.150 +  CTMuint i;
   1.151 +
   1.152 +#ifdef __DEBUG_
   1.153 +  printf("COMPRESSION METHOD: MG1\n");
   1.154 +#endif
   1.155 +
   1.156 +  // Perpare (sort) indices
   1.157 +  indices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
   1.158 +  if(!indices)
   1.159 +  {
   1.160 +    self->mError = CTM_OUT_OF_MEMORY;
   1.161 +    return CTM_FALSE;
   1.162 +  }
   1.163 +  for(i = 0; i < self->mTriangleCount * 3; ++ i)
   1.164 +    indices[i] = self->mIndices[i];
   1.165 +  _ctmReArrangeTriangles(self, indices);
   1.166 +
   1.167 +  // Calculate index deltas (entropy-reduction)
   1.168 +  _ctmMakeIndexDeltas(self, indices);
   1.169 +
   1.170 +  // Write triangle indices
   1.171 +#ifdef __DEBUG_
   1.172 +  printf("Inidices: ");
   1.173 +#endif
   1.174 +  _ctmStreamWrite(self, (void *) "INDX", 4);
   1.175 +  if(!_ctmStreamWritePackedInts(self, (CTMint *) indices, self->mTriangleCount, 3, CTM_FALSE))
   1.176 +  {
   1.177 +    free((void *) indices);
   1.178 +    return CTM_FALSE;
   1.179 +  }
   1.180 +
   1.181 +  // Free temporary resources
   1.182 +  free((void *) indices);
   1.183 +
   1.184 +  // Write vertices
   1.185 +#ifdef __DEBUG_
   1.186 +  printf("Vertices: ");
   1.187 +#endif
   1.188 +  _ctmStreamWrite(self, (void *) "VERT", 4);
   1.189 +  if(!_ctmStreamWritePackedFloats(self, self->mVertices, self->mVertexCount * 3, 1))
   1.190 +  {
   1.191 +    free((void *) indices);
   1.192 +    return CTM_FALSE;
   1.193 +  }
   1.194 +
   1.195 +  // Write normals
   1.196 +  if(self->mNormals)
   1.197 +  {
   1.198 +#ifdef __DEBUG_
   1.199 +    printf("Normals: ");
   1.200 +#endif
   1.201 +    _ctmStreamWrite(self, (void *) "NORM", 4);
   1.202 +    if(!_ctmStreamWritePackedFloats(self, self->mNormals, self->mVertexCount, 3))
   1.203 +      return CTM_FALSE;
   1.204 +  }
   1.205 +
   1.206 +  // Write UV maps
   1.207 +  map = self->mUVMaps;
   1.208 +  while(map)
   1.209 +  {
   1.210 +#ifdef __DEBUG_
   1.211 +    printf("UV coordinates (%s): ", map->mName ? map->mName : "no name");
   1.212 +#endif
   1.213 +    _ctmStreamWrite(self, (void *) "TEXC", 4);
   1.214 +    _ctmStreamWriteSTRING(self, map->mName);
   1.215 +    _ctmStreamWriteSTRING(self, map->mFileName);
   1.216 +    if(!_ctmStreamWritePackedFloats(self, map->mValues, self->mVertexCount, 2))
   1.217 +      return CTM_FALSE;
   1.218 +    map = map->mNext;
   1.219 +  }
   1.220 +
   1.221 +  // Write attribute maps
   1.222 +  map = self->mAttribMaps;
   1.223 +  while(map)
   1.224 +  {
   1.225 +#ifdef __DEBUG_
   1.226 +    printf("Vertex attributes (%s): ", map->mName ? map->mName : "no name");
   1.227 +#endif
   1.228 +    _ctmStreamWrite(self, (void *) "ATTR", 4);
   1.229 +    _ctmStreamWriteSTRING(self, map->mName);
   1.230 +    if(!_ctmStreamWritePackedFloats(self, map->mValues, self->mVertexCount, 4))
   1.231 +      return CTM_FALSE;
   1.232 +    map = map->mNext;
   1.233 +  }
   1.234 +
   1.235 +  return CTM_TRUE;
   1.236 +}
   1.237 +
   1.238 +//-----------------------------------------------------------------------------
   1.239 +// _ctmUncompressMesh_MG1() - Uncmpress the mesh from the input stream in the
   1.240 +// CTM context, and store the resulting mesh in the CTM context.
   1.241 +//-----------------------------------------------------------------------------
   1.242 +int _ctmUncompressMesh_MG1(_CTMcontext * self)
   1.243 +{
   1.244 +  CTMuint * indices;
   1.245 +  _CTMfloatmap * map;
   1.246 +  CTMuint i;
   1.247 +
   1.248 +  // Allocate memory for the indices
   1.249 +  indices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
   1.250 +  if(!indices)
   1.251 +  {
   1.252 +    self->mError = CTM_OUT_OF_MEMORY;
   1.253 +    return CTM_FALSE;
   1.254 +  }
   1.255 +
   1.256 +  // Read triangle indices
   1.257 +  if(_ctmStreamReadUINT(self) != FOURCC("INDX"))
   1.258 +  {
   1.259 +    self->mError = CTM_BAD_FORMAT;
   1.260 +    free(indices);
   1.261 +    return CTM_FALSE;
   1.262 +  }
   1.263 +  if(!_ctmStreamReadPackedInts(self, (CTMint *) indices, self->mTriangleCount, 3, CTM_FALSE))
   1.264 +    return CTM_FALSE;
   1.265 +
   1.266 +  // Restore indices
   1.267 +  _ctmRestoreIndices(self, indices);
   1.268 +  for(i = 0; i < self->mTriangleCount * 3; ++ i)
   1.269 +    self->mIndices[i] = indices[i];
   1.270 +
   1.271 +  // Free temporary resources
   1.272 +  free(indices);
   1.273 +
   1.274 +  // Read vertices
   1.275 +  if(_ctmStreamReadUINT(self) != FOURCC("VERT"))
   1.276 +  {
   1.277 +    self->mError = CTM_BAD_FORMAT;
   1.278 +    return CTM_FALSE;
   1.279 +  }
   1.280 +  if(!_ctmStreamReadPackedFloats(self, self->mVertices, self->mVertexCount * 3, 1))
   1.281 +    return CTM_FALSE;
   1.282 +
   1.283 +  // Read normals
   1.284 +  if(self->mNormals)
   1.285 +  {
   1.286 +    if(_ctmStreamReadUINT(self) != FOURCC("NORM"))
   1.287 +    {
   1.288 +      self->mError = CTM_BAD_FORMAT;
   1.289 +      return CTM_FALSE;
   1.290 +    }
   1.291 +    if(!_ctmStreamReadPackedFloats(self, self->mNormals, self->mVertexCount, 3))
   1.292 +      return CTM_FALSE;
   1.293 +  }
   1.294 +
   1.295 +  // Read UV maps
   1.296 +  map = self->mUVMaps;
   1.297 +  while(map)
   1.298 +  {
   1.299 +    if(_ctmStreamReadUINT(self) != FOURCC("TEXC"))
   1.300 +    {
   1.301 +      self->mError = CTM_BAD_FORMAT;
   1.302 +      return 0;
   1.303 +    }
   1.304 +    _ctmStreamReadSTRING(self, &map->mName);
   1.305 +    _ctmStreamReadSTRING(self, &map->mFileName);
   1.306 +    if(!_ctmStreamReadPackedFloats(self, map->mValues, self->mVertexCount, 2))
   1.307 +      return CTM_FALSE;
   1.308 +    map = map->mNext;
   1.309 +  }
   1.310 +
   1.311 +  // Read vertex attribute maps
   1.312 +  map = self->mAttribMaps;
   1.313 +  while(map)
   1.314 +  {
   1.315 +    if(_ctmStreamReadUINT(self) != FOURCC("ATTR"))
   1.316 +    {
   1.317 +      self->mError = CTM_BAD_FORMAT;
   1.318 +      return 0;
   1.319 +    }
   1.320 +    _ctmStreamReadSTRING(self, &map->mName);
   1.321 +    if(!_ctmStreamReadPackedFloats(self, map->mValues, self->mVertexCount, 4))
   1.322 +      return CTM_FALSE;
   1.323 +    map = map->mNext;
   1.324 +  }
   1.325 +
   1.326 +  return CTM_TRUE;
   1.327 +}