nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // Product:     OpenCTM
nuclear@14: // File:        compressMG1.c
nuclear@14: // Description: Implementation of the MG1 compression method.
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // Copyright (c) 2009-2010 Marcus Geelnard
nuclear@14: //
nuclear@14: // This software is provided 'as-is', without any express or implied
nuclear@14: // warranty. In no event will the authors be held liable for any damages
nuclear@14: // arising from the use of this software.
nuclear@14: //
nuclear@14: // Permission is granted to anyone to use this software for any purpose,
nuclear@14: // including commercial applications, and to alter it and redistribute it
nuclear@14: // freely, subject to the following restrictions:
nuclear@14: //
nuclear@14: //     1. The origin of this software must not be misrepresented; you must not
nuclear@14: //     claim that you wrote the original software. If you use this software
nuclear@14: //     in a product, an acknowledgment in the product documentation would be
nuclear@14: //     appreciated but is not required.
nuclear@14: //
nuclear@14: //     2. Altered source versions must be plainly marked as such, and must not
nuclear@14: //     be misrepresented as being the original software.
nuclear@14: //
nuclear@14: //     3. This notice may not be removed or altered from any source
nuclear@14: //     distribution.
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: 
nuclear@14: #include <stdlib.h>
nuclear@14: #include <math.h>
nuclear@14: #include "openctm.h"
nuclear@14: #include "internal.h"
nuclear@14: 
nuclear@14: #ifdef __DEBUG_
nuclear@14: #include <stdio.h>
nuclear@14: #endif
nuclear@14: 
nuclear@14: 
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // _compareTriangle() - Comparator for the triangle sorting.
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: static int _compareTriangle(const void * elem1, const void * elem2)
nuclear@14: {
nuclear@14:   CTMuint * tri1 = (CTMuint *) elem1;
nuclear@14:   CTMuint * tri2 = (CTMuint *) elem2;
nuclear@14:   if(tri1[0] != tri2[0])
nuclear@14:     return tri1[0] - tri2[0];
nuclear@14:   else
nuclear@14:     return tri1[1] - tri2[1];
nuclear@14: }
nuclear@14: 
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // _ctmReArrangeTriangles() - Re-arrange all triangles for optimal
nuclear@14: // compression.
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: static void _ctmReArrangeTriangles(_CTMcontext * self, CTMuint * aIndices)
nuclear@14: {
nuclear@14:   CTMuint * tri, tmp, i;
nuclear@14: 
nuclear@14:   // Step 1: Make sure that the first index of each triangle is the smallest
nuclear@14:   // one (rotate triangle nodes if necessary)
nuclear@14:   for(i = 0; i < self->mTriangleCount; ++ i)
nuclear@14:   {
nuclear@14:     tri = &aIndices[i * 3];
nuclear@14:     if((tri[1] < tri[0]) && (tri[1] < tri[2]))
nuclear@14:     {
nuclear@14:       tmp = tri[0];
nuclear@14:       tri[0] = tri[1];
nuclear@14:       tri[1] = tri[2];
nuclear@14:       tri[2] = tmp;
nuclear@14:     }
nuclear@14:     else if((tri[2] < tri[0]) && (tri[2] < tri[1]))
nuclear@14:     {
nuclear@14:       tmp = tri[0];
nuclear@14:       tri[0] = tri[2];
nuclear@14:       tri[2] = tri[1];
nuclear@14:       tri[1] = tmp;
nuclear@14:     }
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Step 2: Sort the triangles based on the first triangle index
nuclear@14:   qsort((void *) aIndices, self->mTriangleCount, sizeof(CTMuint) * 3, _compareTriangle);
nuclear@14: }
nuclear@14: 
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // _ctmMakeIndexDeltas() - Calculate various forms of derivatives in order to
nuclear@14: // reduce data entropy.
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: static void _ctmMakeIndexDeltas(_CTMcontext * self, CTMuint * aIndices)
nuclear@14: {
nuclear@14:   CTMint i;
nuclear@14:   for(i = self->mTriangleCount - 1; i >= 0; -- i)
nuclear@14:   {
nuclear@14:     // Step 1: Calculate delta from second triangle index to the previous
nuclear@14:     // second triangle index, if the previous triangle shares the same first
nuclear@14:     // index, otherwise calculate the delta to the first triangle index
nuclear@14:     if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
nuclear@14:       aIndices[i * 3 + 1] -= aIndices[(i - 1) * 3 + 1];
nuclear@14:     else
nuclear@14:       aIndices[i * 3 + 1] -= aIndices[i * 3];
nuclear@14: 
nuclear@14:     // Step 2: Calculate delta from third triangle index to the first triangle
nuclear@14:     // index
nuclear@14:     aIndices[i * 3 + 2] -= aIndices[i * 3];
nuclear@14: 
nuclear@14:     // Step 3: Calculate derivative of the first triangle index
nuclear@14:     if(i >= 1)
nuclear@14:       aIndices[i * 3] -= aIndices[(i - 1) * 3];
nuclear@14:   }
nuclear@14: }
nuclear@14: 
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // _ctmRestoreIndices() - Restore original indices (inverse derivative
nuclear@14: // operation).
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: static void _ctmRestoreIndices(_CTMcontext * self, CTMuint * aIndices)
nuclear@14: {
nuclear@14:   CTMuint i;
nuclear@14: 
nuclear@14:   for(i = 0; i < self->mTriangleCount; ++ i)
nuclear@14:   {
nuclear@14:     // Step 1: Reverse derivative of the first triangle index
nuclear@14:     if(i >= 1)
nuclear@14:       aIndices[i * 3] += aIndices[(i - 1) * 3];
nuclear@14: 
nuclear@14:     // Step 2: Reverse delta from third triangle index to the first triangle
nuclear@14:     // index
nuclear@14:     aIndices[i * 3 + 2] += aIndices[i * 3];
nuclear@14: 
nuclear@14:     // Step 3: Reverse delta from second triangle index to the previous
nuclear@14:     // second triangle index, if the previous triangle shares the same first
nuclear@14:     // index, otherwise reverse the delta to the first triangle index
nuclear@14:     if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
nuclear@14:       aIndices[i * 3 + 1] += aIndices[(i - 1) * 3 + 1];
nuclear@14:     else
nuclear@14:       aIndices[i * 3 + 1] += aIndices[i * 3];
nuclear@14:   }
nuclear@14: }
nuclear@14: 
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // _ctmCompressMesh_MG1() - Compress the mesh that is stored in the CTM
nuclear@14: // context, and write it the the output stream in the CTM context.
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: int _ctmCompressMesh_MG1(_CTMcontext * self)
nuclear@14: {
nuclear@14:   CTMuint * indices;
nuclear@14:   _CTMfloatmap * map;
nuclear@14:   CTMuint i;
nuclear@14: 
nuclear@14: #ifdef __DEBUG_
nuclear@14:   printf("COMPRESSION METHOD: MG1\n");
nuclear@14: #endif
nuclear@14: 
nuclear@14:   // Perpare (sort) indices
nuclear@14:   indices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
nuclear@14:   if(!indices)
nuclear@14:   {
nuclear@14:     self->mError = CTM_OUT_OF_MEMORY;
nuclear@14:     return CTM_FALSE;
nuclear@14:   }
nuclear@14:   for(i = 0; i < self->mTriangleCount * 3; ++ i)
nuclear@14:     indices[i] = self->mIndices[i];
nuclear@14:   _ctmReArrangeTriangles(self, indices);
nuclear@14: 
nuclear@14:   // Calculate index deltas (entropy-reduction)
nuclear@14:   _ctmMakeIndexDeltas(self, indices);
nuclear@14: 
nuclear@14:   // Write triangle indices
nuclear@14: #ifdef __DEBUG_
nuclear@14:   printf("Inidices: ");
nuclear@14: #endif
nuclear@14:   _ctmStreamWrite(self, (void *) "INDX", 4);
nuclear@14:   if(!_ctmStreamWritePackedInts(self, (CTMint *) indices, self->mTriangleCount, 3, CTM_FALSE))
nuclear@14:   {
nuclear@14:     free((void *) indices);
nuclear@14:     return CTM_FALSE;
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Free temporary resources
nuclear@14:   free((void *) indices);
nuclear@14: 
nuclear@14:   // Write vertices
nuclear@14: #ifdef __DEBUG_
nuclear@14:   printf("Vertices: ");
nuclear@14: #endif
nuclear@14:   _ctmStreamWrite(self, (void *) "VERT", 4);
nuclear@14:   if(!_ctmStreamWritePackedFloats(self, self->mVertices, self->mVertexCount * 3, 1))
nuclear@14:   {
nuclear@14:     free((void *) indices);
nuclear@14:     return CTM_FALSE;
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Write normals
nuclear@14:   if(self->mNormals)
nuclear@14:   {
nuclear@14: #ifdef __DEBUG_
nuclear@14:     printf("Normals: ");
nuclear@14: #endif
nuclear@14:     _ctmStreamWrite(self, (void *) "NORM", 4);
nuclear@14:     if(!_ctmStreamWritePackedFloats(self, self->mNormals, self->mVertexCount, 3))
nuclear@14:       return CTM_FALSE;
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Write UV maps
nuclear@14:   map = self->mUVMaps;
nuclear@14:   while(map)
nuclear@14:   {
nuclear@14: #ifdef __DEBUG_
nuclear@14:     printf("UV coordinates (%s): ", map->mName ? map->mName : "no name");
nuclear@14: #endif
nuclear@14:     _ctmStreamWrite(self, (void *) "TEXC", 4);
nuclear@14:     _ctmStreamWriteSTRING(self, map->mName);
nuclear@14:     _ctmStreamWriteSTRING(self, map->mFileName);
nuclear@14:     if(!_ctmStreamWritePackedFloats(self, map->mValues, self->mVertexCount, 2))
nuclear@14:       return CTM_FALSE;
nuclear@14:     map = map->mNext;
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Write attribute maps
nuclear@14:   map = self->mAttribMaps;
nuclear@14:   while(map)
nuclear@14:   {
nuclear@14: #ifdef __DEBUG_
nuclear@14:     printf("Vertex attributes (%s): ", map->mName ? map->mName : "no name");
nuclear@14: #endif
nuclear@14:     _ctmStreamWrite(self, (void *) "ATTR", 4);
nuclear@14:     _ctmStreamWriteSTRING(self, map->mName);
nuclear@14:     if(!_ctmStreamWritePackedFloats(self, map->mValues, self->mVertexCount, 4))
nuclear@14:       return CTM_FALSE;
nuclear@14:     map = map->mNext;
nuclear@14:   }
nuclear@14: 
nuclear@14:   return CTM_TRUE;
nuclear@14: }
nuclear@14: 
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: // _ctmUncompressMesh_MG1() - Uncmpress the mesh from the input stream in the
nuclear@14: // CTM context, and store the resulting mesh in the CTM context.
nuclear@14: //-----------------------------------------------------------------------------
nuclear@14: int _ctmUncompressMesh_MG1(_CTMcontext * self)
nuclear@14: {
nuclear@14:   CTMuint * indices;
nuclear@14:   _CTMfloatmap * map;
nuclear@14:   CTMuint i;
nuclear@14: 
nuclear@14:   // Allocate memory for the indices
nuclear@14:   indices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
nuclear@14:   if(!indices)
nuclear@14:   {
nuclear@14:     self->mError = CTM_OUT_OF_MEMORY;
nuclear@14:     return CTM_FALSE;
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Read triangle indices
nuclear@14:   if(_ctmStreamReadUINT(self) != FOURCC("INDX"))
nuclear@14:   {
nuclear@14:     self->mError = CTM_BAD_FORMAT;
nuclear@14:     free(indices);
nuclear@14:     return CTM_FALSE;
nuclear@14:   }
nuclear@14:   if(!_ctmStreamReadPackedInts(self, (CTMint *) indices, self->mTriangleCount, 3, CTM_FALSE))
nuclear@14:     return CTM_FALSE;
nuclear@14: 
nuclear@14:   // Restore indices
nuclear@14:   _ctmRestoreIndices(self, indices);
nuclear@14:   for(i = 0; i < self->mTriangleCount * 3; ++ i)
nuclear@14:     self->mIndices[i] = indices[i];
nuclear@14: 
nuclear@14:   // Free temporary resources
nuclear@14:   free(indices);
nuclear@14: 
nuclear@14:   // Read vertices
nuclear@14:   if(_ctmStreamReadUINT(self) != FOURCC("VERT"))
nuclear@14:   {
nuclear@14:     self->mError = CTM_BAD_FORMAT;
nuclear@14:     return CTM_FALSE;
nuclear@14:   }
nuclear@14:   if(!_ctmStreamReadPackedFloats(self, self->mVertices, self->mVertexCount * 3, 1))
nuclear@14:     return CTM_FALSE;
nuclear@14: 
nuclear@14:   // Read normals
nuclear@14:   if(self->mNormals)
nuclear@14:   {
nuclear@14:     if(_ctmStreamReadUINT(self) != FOURCC("NORM"))
nuclear@14:     {
nuclear@14:       self->mError = CTM_BAD_FORMAT;
nuclear@14:       return CTM_FALSE;
nuclear@14:     }
nuclear@14:     if(!_ctmStreamReadPackedFloats(self, self->mNormals, self->mVertexCount, 3))
nuclear@14:       return CTM_FALSE;
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Read UV maps
nuclear@14:   map = self->mUVMaps;
nuclear@14:   while(map)
nuclear@14:   {
nuclear@14:     if(_ctmStreamReadUINT(self) != FOURCC("TEXC"))
nuclear@14:     {
nuclear@14:       self->mError = CTM_BAD_FORMAT;
nuclear@14:       return 0;
nuclear@14:     }
nuclear@14:     _ctmStreamReadSTRING(self, &map->mName);
nuclear@14:     _ctmStreamReadSTRING(self, &map->mFileName);
nuclear@14:     if(!_ctmStreamReadPackedFloats(self, map->mValues, self->mVertexCount, 2))
nuclear@14:       return CTM_FALSE;
nuclear@14:     map = map->mNext;
nuclear@14:   }
nuclear@14: 
nuclear@14:   // Read vertex attribute maps
nuclear@14:   map = self->mAttribMaps;
nuclear@14:   while(map)
nuclear@14:   {
nuclear@14:     if(_ctmStreamReadUINT(self) != FOURCC("ATTR"))
nuclear@14:     {
nuclear@14:       self->mError = CTM_BAD_FORMAT;
nuclear@14:       return 0;
nuclear@14:     }
nuclear@14:     _ctmStreamReadSTRING(self, &map->mName);
nuclear@14:     if(!_ctmStreamReadPackedFloats(self, map->mValues, self->mVertexCount, 4))
nuclear@14:       return CTM_FALSE;
nuclear@14:     map = map->mNext;
nuclear@14:   }
nuclear@14: 
nuclear@14:   return CTM_TRUE;
nuclear@14: }