goat3d

annotate libs/openctm/compressMG1.c @ 14:188c697b3b49

find changesets by author, revision, files, or words in the commit message
- added a document describing the goat3d file format chunk hierarchy - started an alternative XML-based file format - added the openctm library
author John Tsiombikas <nuclear@member.fsf.org>
date Thu, 26 Sep 2013 04:47:05 +0300
parents
children
rev   line source
nuclear@14 1 //-----------------------------------------------------------------------------
nuclear@14 2 // Product: OpenCTM
nuclear@14 3 // File: compressMG1.c
nuclear@14 4 // Description: Implementation of the MG1 compression method.
nuclear@14 5 //-----------------------------------------------------------------------------
nuclear@14 6 // Copyright (c) 2009-2010 Marcus Geelnard
nuclear@14 7 //
nuclear@14 8 // This software is provided 'as-is', without any express or implied
nuclear@14 9 // warranty. In no event will the authors be held liable for any damages
nuclear@14 10 // arising from the use of this software.
nuclear@14 11 //
nuclear@14 12 // Permission is granted to anyone to use this software for any purpose,
nuclear@14 13 // including commercial applications, and to alter it and redistribute it
nuclear@14 14 // freely, subject to the following restrictions:
nuclear@14 15 //
nuclear@14 16 // 1. The origin of this software must not be misrepresented; you must not
nuclear@14 17 // claim that you wrote the original software. If you use this software
nuclear@14 18 // in a product, an acknowledgment in the product documentation would be
nuclear@14 19 // appreciated but is not required.
nuclear@14 20 //
nuclear@14 21 // 2. Altered source versions must be plainly marked as such, and must not
nuclear@14 22 // be misrepresented as being the original software.
nuclear@14 23 //
nuclear@14 24 // 3. This notice may not be removed or altered from any source
nuclear@14 25 // distribution.
nuclear@14 26 //-----------------------------------------------------------------------------
nuclear@14 27
nuclear@14 28 #include <stdlib.h>
nuclear@14 29 #include <math.h>
nuclear@14 30 #include "openctm.h"
nuclear@14 31 #include "internal.h"
nuclear@14 32
nuclear@14 33 #ifdef __DEBUG_
nuclear@14 34 #include <stdio.h>
nuclear@14 35 #endif
nuclear@14 36
nuclear@14 37
nuclear@14 38 //-----------------------------------------------------------------------------
nuclear@14 39 // _compareTriangle() - Comparator for the triangle sorting.
nuclear@14 40 //-----------------------------------------------------------------------------
nuclear@14 41 static int _compareTriangle(const void * elem1, const void * elem2)
nuclear@14 42 {
nuclear@14 43 CTMuint * tri1 = (CTMuint *) elem1;
nuclear@14 44 CTMuint * tri2 = (CTMuint *) elem2;
nuclear@14 45 if(tri1[0] != tri2[0])
nuclear@14 46 return tri1[0] - tri2[0];
nuclear@14 47 else
nuclear@14 48 return tri1[1] - tri2[1];
nuclear@14 49 }
nuclear@14 50
nuclear@14 51 //-----------------------------------------------------------------------------
nuclear@14 52 // _ctmReArrangeTriangles() - Re-arrange all triangles for optimal
nuclear@14 53 // compression.
nuclear@14 54 //-----------------------------------------------------------------------------
nuclear@14 55 static void _ctmReArrangeTriangles(_CTMcontext * self, CTMuint * aIndices)
nuclear@14 56 {
nuclear@14 57 CTMuint * tri, tmp, i;
nuclear@14 58
nuclear@14 59 // Step 1: Make sure that the first index of each triangle is the smallest
nuclear@14 60 // one (rotate triangle nodes if necessary)
nuclear@14 61 for(i = 0; i < self->mTriangleCount; ++ i)
nuclear@14 62 {
nuclear@14 63 tri = &aIndices[i * 3];
nuclear@14 64 if((tri[1] < tri[0]) && (tri[1] < tri[2]))
nuclear@14 65 {
nuclear@14 66 tmp = tri[0];
nuclear@14 67 tri[0] = tri[1];
nuclear@14 68 tri[1] = tri[2];
nuclear@14 69 tri[2] = tmp;
nuclear@14 70 }
nuclear@14 71 else if((tri[2] < tri[0]) && (tri[2] < tri[1]))
nuclear@14 72 {
nuclear@14 73 tmp = tri[0];
nuclear@14 74 tri[0] = tri[2];
nuclear@14 75 tri[2] = tri[1];
nuclear@14 76 tri[1] = tmp;
nuclear@14 77 }
nuclear@14 78 }
nuclear@14 79
nuclear@14 80 // Step 2: Sort the triangles based on the first triangle index
nuclear@14 81 qsort((void *) aIndices, self->mTriangleCount, sizeof(CTMuint) * 3, _compareTriangle);
nuclear@14 82 }
nuclear@14 83
nuclear@14 84 //-----------------------------------------------------------------------------
nuclear@14 85 // _ctmMakeIndexDeltas() - Calculate various forms of derivatives in order to
nuclear@14 86 // reduce data entropy.
nuclear@14 87 //-----------------------------------------------------------------------------
nuclear@14 88 static void _ctmMakeIndexDeltas(_CTMcontext * self, CTMuint * aIndices)
nuclear@14 89 {
nuclear@14 90 CTMint i;
nuclear@14 91 for(i = self->mTriangleCount - 1; i >= 0; -- i)
nuclear@14 92 {
nuclear@14 93 // Step 1: Calculate delta from second triangle index to the previous
nuclear@14 94 // second triangle index, if the previous triangle shares the same first
nuclear@14 95 // index, otherwise calculate the delta to the first triangle index
nuclear@14 96 if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
nuclear@14 97 aIndices[i * 3 + 1] -= aIndices[(i - 1) * 3 + 1];
nuclear@14 98 else
nuclear@14 99 aIndices[i * 3 + 1] -= aIndices[i * 3];
nuclear@14 100
nuclear@14 101 // Step 2: Calculate delta from third triangle index to the first triangle
nuclear@14 102 // index
nuclear@14 103 aIndices[i * 3 + 2] -= aIndices[i * 3];
nuclear@14 104
nuclear@14 105 // Step 3: Calculate derivative of the first triangle index
nuclear@14 106 if(i >= 1)
nuclear@14 107 aIndices[i * 3] -= aIndices[(i - 1) * 3];
nuclear@14 108 }
nuclear@14 109 }
nuclear@14 110
nuclear@14 111 //-----------------------------------------------------------------------------
nuclear@14 112 // _ctmRestoreIndices() - Restore original indices (inverse derivative
nuclear@14 113 // operation).
nuclear@14 114 //-----------------------------------------------------------------------------
nuclear@14 115 static void _ctmRestoreIndices(_CTMcontext * self, CTMuint * aIndices)
nuclear@14 116 {
nuclear@14 117 CTMuint i;
nuclear@14 118
nuclear@14 119 for(i = 0; i < self->mTriangleCount; ++ i)
nuclear@14 120 {
nuclear@14 121 // Step 1: Reverse derivative of the first triangle index
nuclear@14 122 if(i >= 1)
nuclear@14 123 aIndices[i * 3] += aIndices[(i - 1) * 3];
nuclear@14 124
nuclear@14 125 // Step 2: Reverse delta from third triangle index to the first triangle
nuclear@14 126 // index
nuclear@14 127 aIndices[i * 3 + 2] += aIndices[i * 3];
nuclear@14 128
nuclear@14 129 // Step 3: Reverse delta from second triangle index to the previous
nuclear@14 130 // second triangle index, if the previous triangle shares the same first
nuclear@14 131 // index, otherwise reverse the delta to the first triangle index
nuclear@14 132 if((i >= 1) && (aIndices[i * 3] == aIndices[(i - 1) * 3]))
nuclear@14 133 aIndices[i * 3 + 1] += aIndices[(i - 1) * 3 + 1];
nuclear@14 134 else
nuclear@14 135 aIndices[i * 3 + 1] += aIndices[i * 3];
nuclear@14 136 }
nuclear@14 137 }
nuclear@14 138
nuclear@14 139 //-----------------------------------------------------------------------------
nuclear@14 140 // _ctmCompressMesh_MG1() - Compress the mesh that is stored in the CTM
nuclear@14 141 // context, and write it the the output stream in the CTM context.
nuclear@14 142 //-----------------------------------------------------------------------------
nuclear@14 143 int _ctmCompressMesh_MG1(_CTMcontext * self)
nuclear@14 144 {
nuclear@14 145 CTMuint * indices;
nuclear@14 146 _CTMfloatmap * map;
nuclear@14 147 CTMuint i;
nuclear@14 148
nuclear@14 149 #ifdef __DEBUG_
nuclear@14 150 printf("COMPRESSION METHOD: MG1\n");
nuclear@14 151 #endif
nuclear@14 152
nuclear@14 153 // Perpare (sort) indices
nuclear@14 154 indices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
nuclear@14 155 if(!indices)
nuclear@14 156 {
nuclear@14 157 self->mError = CTM_OUT_OF_MEMORY;
nuclear@14 158 return CTM_FALSE;
nuclear@14 159 }
nuclear@14 160 for(i = 0; i < self->mTriangleCount * 3; ++ i)
nuclear@14 161 indices[i] = self->mIndices[i];
nuclear@14 162 _ctmReArrangeTriangles(self, indices);
nuclear@14 163
nuclear@14 164 // Calculate index deltas (entropy-reduction)
nuclear@14 165 _ctmMakeIndexDeltas(self, indices);
nuclear@14 166
nuclear@14 167 // Write triangle indices
nuclear@14 168 #ifdef __DEBUG_
nuclear@14 169 printf("Inidices: ");
nuclear@14 170 #endif
nuclear@14 171 _ctmStreamWrite(self, (void *) "INDX", 4);
nuclear@14 172 if(!_ctmStreamWritePackedInts(self, (CTMint *) indices, self->mTriangleCount, 3, CTM_FALSE))
nuclear@14 173 {
nuclear@14 174 free((void *) indices);
nuclear@14 175 return CTM_FALSE;
nuclear@14 176 }
nuclear@14 177
nuclear@14 178 // Free temporary resources
nuclear@14 179 free((void *) indices);
nuclear@14 180
nuclear@14 181 // Write vertices
nuclear@14 182 #ifdef __DEBUG_
nuclear@14 183 printf("Vertices: ");
nuclear@14 184 #endif
nuclear@14 185 _ctmStreamWrite(self, (void *) "VERT", 4);
nuclear@14 186 if(!_ctmStreamWritePackedFloats(self, self->mVertices, self->mVertexCount * 3, 1))
nuclear@14 187 {
nuclear@14 188 free((void *) indices);
nuclear@14 189 return CTM_FALSE;
nuclear@14 190 }
nuclear@14 191
nuclear@14 192 // Write normals
nuclear@14 193 if(self->mNormals)
nuclear@14 194 {
nuclear@14 195 #ifdef __DEBUG_
nuclear@14 196 printf("Normals: ");
nuclear@14 197 #endif
nuclear@14 198 _ctmStreamWrite(self, (void *) "NORM", 4);
nuclear@14 199 if(!_ctmStreamWritePackedFloats(self, self->mNormals, self->mVertexCount, 3))
nuclear@14 200 return CTM_FALSE;
nuclear@14 201 }
nuclear@14 202
nuclear@14 203 // Write UV maps
nuclear@14 204 map = self->mUVMaps;
nuclear@14 205 while(map)
nuclear@14 206 {
nuclear@14 207 #ifdef __DEBUG_
nuclear@14 208 printf("UV coordinates (%s): ", map->mName ? map->mName : "no name");
nuclear@14 209 #endif
nuclear@14 210 _ctmStreamWrite(self, (void *) "TEXC", 4);
nuclear@14 211 _ctmStreamWriteSTRING(self, map->mName);
nuclear@14 212 _ctmStreamWriteSTRING(self, map->mFileName);
nuclear@14 213 if(!_ctmStreamWritePackedFloats(self, map->mValues, self->mVertexCount, 2))
nuclear@14 214 return CTM_FALSE;
nuclear@14 215 map = map->mNext;
nuclear@14 216 }
nuclear@14 217
nuclear@14 218 // Write attribute maps
nuclear@14 219 map = self->mAttribMaps;
nuclear@14 220 while(map)
nuclear@14 221 {
nuclear@14 222 #ifdef __DEBUG_
nuclear@14 223 printf("Vertex attributes (%s): ", map->mName ? map->mName : "no name");
nuclear@14 224 #endif
nuclear@14 225 _ctmStreamWrite(self, (void *) "ATTR", 4);
nuclear@14 226 _ctmStreamWriteSTRING(self, map->mName);
nuclear@14 227 if(!_ctmStreamWritePackedFloats(self, map->mValues, self->mVertexCount, 4))
nuclear@14 228 return CTM_FALSE;
nuclear@14 229 map = map->mNext;
nuclear@14 230 }
nuclear@14 231
nuclear@14 232 return CTM_TRUE;
nuclear@14 233 }
nuclear@14 234
nuclear@14 235 //-----------------------------------------------------------------------------
nuclear@14 236 // _ctmUncompressMesh_MG1() - Uncmpress the mesh from the input stream in the
nuclear@14 237 // CTM context, and store the resulting mesh in the CTM context.
nuclear@14 238 //-----------------------------------------------------------------------------
nuclear@14 239 int _ctmUncompressMesh_MG1(_CTMcontext * self)
nuclear@14 240 {
nuclear@14 241 CTMuint * indices;
nuclear@14 242 _CTMfloatmap * map;
nuclear@14 243 CTMuint i;
nuclear@14 244
nuclear@14 245 // Allocate memory for the indices
nuclear@14 246 indices = (CTMuint *) malloc(sizeof(CTMuint) * self->mTriangleCount * 3);
nuclear@14 247 if(!indices)
nuclear@14 248 {
nuclear@14 249 self->mError = CTM_OUT_OF_MEMORY;
nuclear@14 250 return CTM_FALSE;
nuclear@14 251 }
nuclear@14 252
nuclear@14 253 // Read triangle indices
nuclear@14 254 if(_ctmStreamReadUINT(self) != FOURCC("INDX"))
nuclear@14 255 {
nuclear@14 256 self->mError = CTM_BAD_FORMAT;
nuclear@14 257 free(indices);
nuclear@14 258 return CTM_FALSE;
nuclear@14 259 }
nuclear@14 260 if(!_ctmStreamReadPackedInts(self, (CTMint *) indices, self->mTriangleCount, 3, CTM_FALSE))
nuclear@14 261 return CTM_FALSE;
nuclear@14 262
nuclear@14 263 // Restore indices
nuclear@14 264 _ctmRestoreIndices(self, indices);
nuclear@14 265 for(i = 0; i < self->mTriangleCount * 3; ++ i)
nuclear@14 266 self->mIndices[i] = indices[i];
nuclear@14 267
nuclear@14 268 // Free temporary resources
nuclear@14 269 free(indices);
nuclear@14 270
nuclear@14 271 // Read vertices
nuclear@14 272 if(_ctmStreamReadUINT(self) != FOURCC("VERT"))
nuclear@14 273 {
nuclear@14 274 self->mError = CTM_BAD_FORMAT;
nuclear@14 275 return CTM_FALSE;
nuclear@14 276 }
nuclear@14 277 if(!_ctmStreamReadPackedFloats(self, self->mVertices, self->mVertexCount * 3, 1))
nuclear@14 278 return CTM_FALSE;
nuclear@14 279
nuclear@14 280 // Read normals
nuclear@14 281 if(self->mNormals)
nuclear@14 282 {
nuclear@14 283 if(_ctmStreamReadUINT(self) != FOURCC("NORM"))
nuclear@14 284 {
nuclear@14 285 self->mError = CTM_BAD_FORMAT;
nuclear@14 286 return CTM_FALSE;
nuclear@14 287 }
nuclear@14 288 if(!_ctmStreamReadPackedFloats(self, self->mNormals, self->mVertexCount, 3))
nuclear@14 289 return CTM_FALSE;
nuclear@14 290 }
nuclear@14 291
nuclear@14 292 // Read UV maps
nuclear@14 293 map = self->mUVMaps;
nuclear@14 294 while(map)
nuclear@14 295 {
nuclear@14 296 if(_ctmStreamReadUINT(self) != FOURCC("TEXC"))
nuclear@14 297 {
nuclear@14 298 self->mError = CTM_BAD_FORMAT;
nuclear@14 299 return 0;
nuclear@14 300 }
nuclear@14 301 _ctmStreamReadSTRING(self, &map->mName);
nuclear@14 302 _ctmStreamReadSTRING(self, &map->mFileName);
nuclear@14 303 if(!_ctmStreamReadPackedFloats(self, map->mValues, self->mVertexCount, 2))
nuclear@14 304 return CTM_FALSE;
nuclear@14 305 map = map->mNext;
nuclear@14 306 }
nuclear@14 307
nuclear@14 308 // Read vertex attribute maps
nuclear@14 309 map = self->mAttribMaps;
nuclear@14 310 while(map)
nuclear@14 311 {
nuclear@14 312 if(_ctmStreamReadUINT(self) != FOURCC("ATTR"))
nuclear@14 313 {
nuclear@14 314 self->mError = CTM_BAD_FORMAT;
nuclear@14 315 return 0;
nuclear@14 316 }
nuclear@14 317 _ctmStreamReadSTRING(self, &map->mName);
nuclear@14 318 if(!_ctmStreamReadPackedFloats(self, map->mValues, self->mVertexCount, 4))
nuclear@14 319 return CTM_FALSE;
nuclear@14 320 map = map->mNext;
nuclear@14 321 }
nuclear@14 322
nuclear@14 323 return CTM_TRUE;
nuclear@14 324 }