1/* 2Copyright (c) 2013 Khaled Mammou - Advanced Micro Devices, Inc. 3 4Permission is hereby granted, free of charge, to any person obtaining a copy 5of this software and associated documentation files (the "Software"), to deal 6in the Software without restriction, including without limitation the rights 7to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8copies of the Software, and to permit persons to whom the Software is 9furnished to do so, subject to the following conditions: 10 11The above copyright notice and this permission notice shall be included in 12all copies or substantial portions of the Software. 13 14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20THE SOFTWARE. 21*/ 22 23#pragma once 24#ifndef O3DGC_TRIANGLE_LIST_DECODER_INL 25#define O3DGC_TRIANGLE_LIST_DECODER_INL 26 27namespace o3dgc 28{ 29 template<class T> 30 O3DGCErrorCode TriangleListDecoder<T>::Init(T * const triangles, 31 const long numTriangles, 32 const long numVertices, 33 const long maxSizeV2T) 34 { 35 assert(numVertices > 0); 36 assert(numTriangles > 0); 37 m_numTriangles = numTriangles; 38 m_numVertices = numVertices; 39 m_triangles = triangles; 40 m_vertexCount = 0; 41 m_triangleCount = 0; 42 m_itNumTFans = 0; 43 m_itDegree = 0; 44 m_itConfig = 0; 45 m_itOperation = 0; 46 m_itIndex = 0; 47 if (m_numVertices > m_maxNumVertices) 48 { 49 m_maxNumVertices = m_numVertices; 50 delete [] m_visitedVerticesValence; 51 delete [] m_visitedVertices; 52 m_visitedVerticesValence = new long [m_numVertices]; 53 m_visitedVertices = new long [m_numVertices]; 54 } 55 56 if (m_decodeTrianglesOrder && m_tempTrianglesSize < m_numTriangles) 57 { 58 delete [] m_tempTriangles; 59 m_tempTrianglesSize = m_numTriangles; 60 m_tempTriangles = new T [3*m_tempTrianglesSize]; 61 } 62 63 m_ctfans.SetStreamType(m_streamType); 64 m_ctfans.Allocate(m_numVertices, m_numTriangles); 65 m_tfans.Allocate(2 * m_numVertices, 8 * m_numVertices); 66 67 // compute vertex-to-triangle adjacency information 68 m_vertexToTriangle.AllocateNumNeighborsArray(numVertices); 69 long * numNeighbors = m_vertexToTriangle.GetNumNeighborsBuffer(); 70 for(long i = 0; i < numVertices; ++i) 71 { 72 numNeighbors[i] = maxSizeV2T; 73 } 74 m_vertexToTriangle.AllocateNeighborsArray(); 75 m_vertexToTriangle.ClearNeighborsArray(); 76 return O3DGC_OK; 77 } 78 template<class T> 79 O3DGCErrorCode TriangleListDecoder<T>::Decompress() 80 { 81 for(long focusVertex = 0; focusVertex < m_numVertices; ++focusVertex) 82 { 83 if (focusVertex == m_vertexCount) 84 { 85 m_vertexCount++; // insert focusVertex 86 } 87 CompueLocalConnectivityInfo(focusVertex); 88 DecompressTFAN(focusVertex); 89 } 90 return O3DGC_OK; 91 } 92 template<class T> 93 O3DGCErrorCode TriangleListDecoder<T>::Reorder() 94 { 95 if (m_decodeTrianglesOrder) 96 { 97 unsigned long itTriangleIndex = 0; 98 long prevTriangleIndex = 0; 99 long t; 100 memcpy(m_tempTriangles, m_triangles, m_numTriangles * 3 * sizeof(T)); 101 for(long i = 0; i < m_numTriangles; ++i) 102 { 103 t = m_ctfans.ReadTriangleIndex(itTriangleIndex) + prevTriangleIndex; 104 assert( t >= 0 && t < m_numTriangles); 105 memcpy(m_triangles + 3 * t, m_tempTriangles + 3 * i, sizeof(T) * 3); 106 prevTriangleIndex = t + 1; 107 } 108 } 109 return O3DGC_OK; 110 } 111 template<class T> 112 O3DGCErrorCode TriangleListDecoder<T>::CompueLocalConnectivityInfo(const long focusVertex) 113 { 114 long t = 0; 115 long p, v; 116 m_numConqueredTriangles = 0; 117 m_numVisitedVertices = 0; 118 for(long i = m_vertexToTriangle.Begin(focusVertex); (t >= 0) && (i < m_vertexToTriangle.End(focusVertex)); ++i) 119 { 120 t = m_vertexToTriangle.GetNeighbor(i); 121 if ( t >= 0) 122 { 123 ++m_numConqueredTriangles; 124 p = 3*t; 125 // extract visited vertices 126 for(long k = 0; k < 3; ++k) 127 { 128 v = m_triangles[p+k]; 129 if (v > focusVertex) // vertices are insertices by increasing traversal order 130 { 131 bool foundOrInserted = false; 132 for (long j = 0; j < m_numVisitedVertices; ++j) 133 { 134 if (v == m_visitedVertices[j]) 135 { 136 m_visitedVerticesValence[j]++; 137 foundOrInserted = true; 138 break; 139 } 140 else if (v < m_visitedVertices[j]) 141 { 142 ++m_numVisitedVertices; 143 for (long h = m_numVisitedVertices-1; h > j; --h) 144 { 145 m_visitedVertices[h] = m_visitedVertices[h-1]; 146 m_visitedVerticesValence[h] = m_visitedVerticesValence[h-1]; 147 } 148 m_visitedVertices[j] = v; 149 m_visitedVerticesValence[j] = 1; 150 foundOrInserted = true; 151 break; 152 } 153 } 154 if (!foundOrInserted) 155 { 156 m_visitedVertices[m_numVisitedVertices] = v; 157 m_visitedVerticesValence[m_numVisitedVertices] = 1; 158 m_numVisitedVertices++; 159 } 160 } 161 } 162 } 163 } 164 // re-order visited vertices by taking into account their valence (i.e., # of conquered triangles incident to each vertex) 165 // in order to avoid config. 9 166 if (m_numVisitedVertices > 2) 167 { 168 long y; 169 for(long x = 1; x < m_numVisitedVertices; ++x) 170 { 171 172 if (m_visitedVerticesValence[x] == 1) 173 { 174 y = x; 175 while( (y > 0) && (m_visitedVerticesValence[y] < m_visitedVerticesValence[y-1]) ) 176 { 177 swap(m_visitedVerticesValence[y], m_visitedVerticesValence[y-1]); 178 swap(m_visitedVertices[y], m_visitedVertices[y-1]); 179 --y; 180 } 181 } 182 } 183 } 184 return O3DGC_OK; 185 } 186 template<class T> 187 O3DGCErrorCode TriangleListDecoder<T>::DecompressTFAN(const long focusVertex) 188 { 189 long ntfans; 190 long degree, config; 191 long op; 192 long index; 193 long k0, k1; 194 long b, c, t; 195 196 ntfans = m_ctfans.ReadNumTFans(m_itNumTFans); 197 if (ntfans > 0) 198 { 199 for(long f = 0; f != ntfans; f++) 200 { 201 m_tfans.AddTFAN(); 202 degree = m_ctfans.ReadDegree(m_itDegree) +2 - m_numConqueredTriangles; 203 config = m_ctfans.ReadConfig(m_itConfig); 204 k0 = m_tfans.GetNumVertices(); 205 m_tfans.AddVertex(focusVertex); 206 switch(config) 207 { 208 case 0:// ops: 1000001 vertices: -1 -2 209 m_tfans.AddVertex(m_visitedVertices[0]); 210 for(long u = 1; u < degree-1; u++) 211 { 212 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 213 m_tfans.AddVertex(m_vertexCount++); 214 } 215 m_tfans.AddVertex(m_visitedVertices[1]); 216 break; 217 case 1: // ops: 1xxxxxx1 vertices: -1 x x x x x -2 218 m_tfans.AddVertex(m_visitedVertices[0]); 219 for(long u = 1; u < degree-1; u++) 220 { 221 op = m_ctfans.ReadOperation(m_itOperation); 222 if (op == 1) 223 { 224 index = m_ctfans.ReadIndex(m_itIndex); 225 if ( index < 0) 226 { 227 m_tfans.AddVertex(m_visitedVertices[-index-1]); 228 } 229 else 230 { 231 m_tfans.AddVertex(index + focusVertex); 232 } 233 } 234 else 235 { 236 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 237 m_tfans.AddVertex(m_vertexCount++); 238 } 239 } 240 m_tfans.AddVertex(m_visitedVertices[1]); 241 break; 242 case 2: // ops: 00000001 vertices: -1 243 for(long u = 0; u < degree-1; u++) 244 { 245 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 246 m_tfans.AddVertex(m_vertexCount++); 247 } 248 m_tfans.AddVertex(m_visitedVertices[0]); 249 break; 250 case 3: // ops: 00000001 vertices: -2 251 for(long u=0; u < degree-1; u++) 252 { 253 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 254 m_tfans.AddVertex(m_vertexCount++); 255 } 256 m_tfans.AddVertex(m_visitedVertices[1]); 257 break; 258 case 4: // ops: 10000000 vertices: -1 259 m_tfans.AddVertex(m_visitedVertices[0]); 260 for(long u = 1; u < degree; u++) 261 { 262 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 263 m_tfans.AddVertex(m_vertexCount++); 264 } 265 break; 266 case 5: // ops: 10000000 vertices: -2 267 m_tfans.AddVertex(m_visitedVertices[1]); 268 for(long u = 1; u < degree; u++) 269 { 270 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 271 m_tfans.AddVertex(m_vertexCount++); 272 } 273 break; 274 case 6:// ops: 00000000 vertices: 275 for(long u = 0; u < degree; u++) 276 { 277 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 278 m_tfans.AddVertex(m_vertexCount++); 279 } 280 break; 281 case 7: // ops: 1000001 vertices: -2 -1 282 m_tfans.AddVertex(m_visitedVertices[1]); 283 for(long u = 1; u < degree-1; u++) 284 { 285 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 286 m_tfans.AddVertex(m_vertexCount++); 287 } 288 m_tfans.AddVertex(m_visitedVertices[0]); 289 break; 290 case 8: // ops: 1xxxxxx1 vertices: -2 x x x x x -1 291 m_tfans.AddVertex(m_visitedVertices[1]); 292 for(long u = 1; u < degree-1; u++) 293 { 294 op = m_ctfans.ReadOperation(m_itOperation); 295 if (op == 1) 296 { 297 index = m_ctfans.ReadIndex(m_itIndex); 298 if ( index < 0) 299 { 300 m_tfans.AddVertex(m_visitedVertices[-index-1]); 301 } 302 else 303 { 304 m_tfans.AddVertex(index + focusVertex); 305 } 306 } 307 else 308 { 309 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 310 m_tfans.AddVertex(m_vertexCount++); 311 } 312 } 313 m_tfans.AddVertex(m_visitedVertices[0]); 314 break; 315 case 9: // general case 316 for(long u = 0; u < degree; u++) 317 { 318 op = m_ctfans.ReadOperation(m_itOperation); 319 if (op == 1) 320 { 321 index = m_ctfans.ReadIndex(m_itIndex); 322 if ( index < 0) 323 { 324 m_tfans.AddVertex(m_visitedVertices[-index-1]); 325 } 326 else 327 { 328 m_tfans.AddVertex(index + focusVertex); 329 } 330 } 331 else 332 { 333 m_visitedVertices[m_numVisitedVertices++] = m_vertexCount; 334 m_tfans.AddVertex(m_vertexCount++); 335 } 336 } 337 break; 338 339 } 340 //logger.write_2_log("\t degree=%i \t cas = %i\n", degree, cas); 341 k1 = m_tfans.GetNumVertices(); 342 b = m_tfans.GetVertex(k0+1); 343 for (long k = k0+2; k < k1; k++) 344 { 345 c = m_tfans.GetVertex(k); 346 t = m_triangleCount*3; 347 348 m_triangles[t++] = (T) focusVertex; 349 m_triangles[t++] = (T) b; 350 m_triangles[t ] = (T) c; 351 352 m_vertexToTriangle.AddNeighbor(focusVertex, m_triangleCount); 353 m_vertexToTriangle.AddNeighbor(b , m_triangleCount); 354 m_vertexToTriangle.AddNeighbor(c , m_triangleCount); 355 b=c; 356 m_triangleCount++; 357 } 358 } 359 } 360 return O3DGC_OK; 361 } 362} 363#endif //O3DGC_TRIANGLE_LIST_DECODER_INL 364 365