o3dgcTriangleListEncoder.inl 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719
  1. /*
  2. Copyright (c) 2013 Khaled Mammou - Advanced Micro Devices, Inc.
  3. Permission is hereby granted, free of charge, to any person obtaining a copy
  4. of this software and associated documentation files (the "Software"), to deal
  5. in the Software without restriction, including without limitation the rights
  6. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  7. copies of the Software, and to permit persons to whom the Software is
  8. furnished to do so, subject to the following conditions:
  9. The above copyright notice and this permission notice shall be included in
  10. all copies or substantial portions of the Software.
  11. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  12. IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  13. FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  14. AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  15. LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  16. OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  17. THE SOFTWARE.
  18. */
  19. #pragma once
  20. #ifndef O3DGC_TRIANGLE_LIST_ENCODER_INL
  21. #define O3DGC_TRIANGLE_LIST_ENCODER_INL
  22. namespace o3dgc
  23. {
  24. // extract opposite edge
  25. template <class T>
  26. inline void CompueOppositeEdge(const long focusVertex,
  27. const T * triangle,
  28. long & a, long & b)
  29. {
  30. if ((long) triangle[0] == focusVertex)
  31. {
  32. a = triangle[1];
  33. b = triangle[2];
  34. }
  35. else if ((long) triangle[1] == focusVertex)
  36. {
  37. a = triangle[2];
  38. b = triangle[0];
  39. }
  40. else
  41. {
  42. a = triangle[0];
  43. b = triangle[1];
  44. }
  45. }
  46. inline bool IsCase0(long degree, long numIndices, const long * const ops, const long * const indices)
  47. {
  48. // ops: 1000001 vertices: -1 -2
  49. if ((numIndices != 2) || (degree < 2)) {
  50. return false;
  51. }
  52. if ((indices[0] != -1) ||(indices[1] != -2) ||
  53. (ops[0] != 1) ||(ops[degree-1] != 1) ) return false;
  54. for (long u = 1; u < degree-1; u++) {
  55. if (ops[u] != 0) return false;
  56. }
  57. return true;
  58. }
  59. inline bool IsCase1(long degree, long numIndices, const long * const ops, const long * const indices)
  60. {
  61. // ops: 1xxxxxx1 indices: -1 x x x x x -2
  62. if ((degree < 2) || (numIndices < 1))
  63. {
  64. return false;
  65. }
  66. if ((indices[0] != -1) ||(indices[numIndices-1] != -2) ||
  67. (ops[0] != 1) ||(ops[degree-1] != 1) ) return false;
  68. return true;
  69. }
  70. inline bool IsCase2(long degree, long numIndices, const long * const ops, const long * const indices)
  71. {
  72. // ops: 00000001 indices: -1
  73. if ((degree < 2) || (numIndices!= 1))
  74. {
  75. return false;
  76. }
  77. if ((indices[0] != -1) || (ops[degree-1] != 1) ) return false;
  78. for (long u = 0; u < degree-1; u++) {
  79. if (ops[u] != 0) return false;
  80. }
  81. return true;
  82. }
  83. inline bool IsCase3(long degree, long numIndices, const long * const ops, const long * const indices)
  84. {
  85. // ops: 00000001 indices: -2
  86. if ((degree < 2) || (numIndices!= 1))
  87. {
  88. return false;
  89. }
  90. if ((indices[0] != -2) || (ops[degree-1] != 1) ) return false;
  91. for (long u = 0; u < degree-1; u++) {
  92. if (ops[u] != 0) return false;
  93. }
  94. return true;
  95. }
  96. inline bool IsCase4(long degree, long numIndices, const long * const ops, const long * const indices)
  97. {
  98. // ops: 10000000 indices: -1
  99. if ((degree < 2) || (numIndices!= 1))
  100. {
  101. return false;
  102. }
  103. if ((indices[0] != -1) || (ops[0] != 1) ) return false;
  104. for (long u = 1; u < degree; u++)
  105. {
  106. if (ops[u] != 0) return false;
  107. }
  108. return true;
  109. }
  110. inline bool IsCase5(long degree, long numIndices, const long * const ops, const long * const indices)
  111. {
  112. // ops: 10000000 indices: -2
  113. if ((degree < 2) || (numIndices!= 1))
  114. {
  115. return false;
  116. }
  117. if ((indices[0] != -2) || (ops[0] != 1) ) return false;
  118. for (long u = 1; u < degree; u++) {
  119. if (ops[u] != 0) return false;
  120. }
  121. return true;
  122. }
  123. inline bool IsCase6(long degree, long numIndices, const long * const ops, const long * const /*indices*/)
  124. {
  125. // ops: 0000000 indices:
  126. if (numIndices!= 0)
  127. {
  128. return false;
  129. }
  130. for (long u = 0; u < degree; u++)
  131. {
  132. if (ops[u] != 0) return false;
  133. }
  134. return true;
  135. }
  136. inline bool IsCase7(long degree, long numIndices, const long * const ops, const long * const indices)
  137. {
  138. // ops: 1000001 indices: -2 -1
  139. if ((numIndices!= 2) || (degree < 2))
  140. {
  141. return false;
  142. }
  143. if ((indices[0] != -2) ||(indices[1] != -1) ||
  144. (ops[0] != 1) ||(ops[degree-1] != 1) ) return false;
  145. for (long u = 1; u < degree-1; u++)
  146. {
  147. if (ops[u] != 0) return false;
  148. }
  149. return true;
  150. }
  151. inline bool IsCase8(long degree, long numIndices, const long * const ops, const long * const indices)
  152. {
  153. // ops: 1xxxxxx1 indices: -1 x x x x x -2
  154. if ((degree < 2) || (numIndices < 1))
  155. {
  156. return false;
  157. }
  158. if ((indices[0] != -2) ||(indices[numIndices-1] != -1) ||
  159. (ops[0] != 1) ||(ops[degree-1] != 1) ) return false;
  160. return true;
  161. }
  162. template <class T>
  163. TriangleListEncoder<T>::TriangleListEncoder(void)
  164. {
  165. m_vtags = 0;
  166. m_ttags = 0;
  167. m_tmap = 0;
  168. m_vmap = 0;
  169. m_count = 0;
  170. m_invVMap = 0;
  171. m_invTMap = 0;
  172. m_nonConqueredTriangles = 0;
  173. m_nonConqueredEdges = 0;
  174. m_visitedVertices = 0;
  175. m_visitedVerticesValence = 0;
  176. m_vertexCount = 0;
  177. m_triangleCount = 0;
  178. m_maxNumVertices = 0;
  179. m_maxNumTriangles = 0;
  180. m_numTriangles = 0;
  181. m_numVertices = 0;
  182. m_triangles = 0;
  183. m_maxSizeVertexToTriangle = 0;
  184. m_streamType = O3DGC_STREAM_TYPE_UNKOWN;
  185. }
  186. template <class T>
  187. TriangleListEncoder<T>::~TriangleListEncoder()
  188. {
  189. delete [] m_vtags;
  190. delete [] m_vmap;
  191. delete [] m_invVMap;
  192. delete [] m_invTMap;
  193. delete [] m_visitedVerticesValence;
  194. delete [] m_visitedVertices;
  195. delete [] m_ttags;
  196. delete [] m_tmap;
  197. delete [] m_count;
  198. delete [] m_nonConqueredTriangles;
  199. delete [] m_nonConqueredEdges;
  200. }
  201. template <class T>
  202. O3DGCErrorCode TriangleListEncoder<T>::Init(const T * const triangles,
  203. long numTriangles,
  204. long numVertices)
  205. {
  206. assert(numVertices > 0);
  207. assert(numTriangles > 0);
  208. m_numTriangles = numTriangles;
  209. m_numVertices = numVertices;
  210. m_triangles = triangles;
  211. m_vertexCount = 0;
  212. m_triangleCount = 0;
  213. if (m_numVertices > m_maxNumVertices)
  214. {
  215. delete [] m_vtags;
  216. delete [] m_vmap;
  217. delete [] m_invVMap;
  218. delete [] m_visitedVerticesValence;
  219. delete [] m_visitedVertices;
  220. m_maxNumVertices = m_numVertices;
  221. m_vtags = new long [m_numVertices];
  222. m_vmap = new long [m_numVertices];
  223. m_invVMap = new long [m_numVertices];
  224. m_visitedVerticesValence = new long [m_numVertices];
  225. m_visitedVertices = new long [m_numVertices];
  226. }
  227. if (m_numTriangles > m_maxNumTriangles)
  228. {
  229. delete [] m_ttags;
  230. delete [] m_tmap;
  231. delete [] m_invTMap;
  232. delete [] m_nonConqueredTriangles;
  233. delete [] m_nonConqueredEdges;
  234. delete [] m_count;
  235. m_maxNumTriangles = m_numTriangles;
  236. m_ttags = new long [m_numTriangles];
  237. m_tmap = new long [m_numTriangles];
  238. m_invTMap = new long [m_numTriangles];
  239. m_count = new long [m_numTriangles+1];
  240. m_nonConqueredTriangles = new long [m_numTriangles];
  241. m_nonConqueredEdges = new long [2*m_numTriangles];
  242. }
  243. memset(m_vtags , 0x00, sizeof(long) * m_numVertices );
  244. memset(m_vmap , 0xFF, sizeof(long) * m_numVertices );
  245. memset(m_invVMap, 0xFF, sizeof(long) * m_numVertices );
  246. memset(m_ttags , 0x00, sizeof(long) * m_numTriangles);
  247. memset(m_tmap , 0xFF, sizeof(long) * m_numTriangles);
  248. memset(m_invTMap, 0xFF, sizeof(long) * m_numTriangles);
  249. memset(m_count , 0x00, sizeof(long) * (m_numTriangles+1));
  250. m_vfifo.Allocate(m_numVertices);
  251. m_ctfans.SetStreamType(m_streamType);
  252. m_ctfans.Allocate(m_numVertices, m_numTriangles);
  253. // compute vertex-to-triangle adjacency information
  254. m_vertexToTriangle.AllocateNumNeighborsArray(numVertices);
  255. m_vertexToTriangle.ClearNumNeighborsArray();
  256. long * numNeighbors = m_vertexToTriangle.GetNumNeighborsBuffer();
  257. for(long i = 0, t = 0; i < m_numTriangles; ++i, t+=3)
  258. {
  259. ++numNeighbors[ triangles[t ] ];
  260. ++numNeighbors[ triangles[t+1] ];
  261. ++numNeighbors[ triangles[t+2] ];
  262. }
  263. m_maxSizeVertexToTriangle = 0;
  264. for(long i = 0; i < numVertices; ++i)
  265. {
  266. if (m_maxSizeVertexToTriangle < numNeighbors[i])
  267. {
  268. m_maxSizeVertexToTriangle = numNeighbors[i];
  269. }
  270. }
  271. m_vertexToTriangle.AllocateNeighborsArray();
  272. m_vertexToTriangle.ClearNeighborsArray();
  273. for(long i = 0, t = 0; i < m_numTriangles; ++i, t+=3)
  274. {
  275. m_vertexToTriangle.AddNeighbor(triangles[t ], i);
  276. m_vertexToTriangle.AddNeighbor(triangles[t+1], i);
  277. m_vertexToTriangle.AddNeighbor(triangles[t+2], i);
  278. }
  279. return O3DGC_OK;
  280. }
  281. template <class T>
  282. O3DGCErrorCode TriangleListEncoder<T>::Encode(const T * const triangles,
  283. const unsigned long * const indexBufferIDs,
  284. const long numTriangles,
  285. const long numVertices,
  286. BinaryStream & bstream)
  287. {
  288. assert(numVertices > 0);
  289. assert(numTriangles > 0);
  290. Init(triangles, numTriangles, numVertices);
  291. unsigned char mask = 0;
  292. bool encodeTrianglesOrder = (indexBufferIDs != 0);
  293. if (encodeTrianglesOrder)
  294. {
  295. long numBufferIDs = 0;
  296. for (long t = 0; t < numTriangles; t++)
  297. {
  298. if (numBufferIDs <= (long) indexBufferIDs[t])
  299. {
  300. ++numBufferIDs;
  301. assert(numBufferIDs <= numTriangles);
  302. }
  303. ++m_count[indexBufferIDs[t]+1];
  304. }
  305. for (long i = 2; i <= numBufferIDs; i++)
  306. {
  307. m_count[i] += m_count[i-1];
  308. }
  309. mask += 2; // preserved triangles order
  310. }
  311. bstream.WriteUChar(mask, m_streamType);
  312. bstream.WriteUInt32(m_maxSizeVertexToTriangle, m_streamType);
  313. long v0;
  314. for (long v = 0; v < m_numVertices; v++)
  315. {
  316. if (!m_vtags[v])
  317. {
  318. m_vfifo.PushBack(v);
  319. m_vtags[v] = 1;
  320. m_vmap[v] = m_vertexCount++;
  321. m_invVMap[m_vmap[v]] = v;
  322. while (m_vfifo.GetSize() > 0 )
  323. {
  324. v0 = m_vfifo.PopFirst();
  325. ProcessVertex(v0);
  326. }
  327. }
  328. }
  329. if (encodeTrianglesOrder)
  330. {
  331. long t, prev = 0;
  332. long pred;
  333. for (long i = 0; i < numTriangles; ++i)
  334. {
  335. t = m_invTMap[i];
  336. m_tmap[t] = m_count[ indexBufferIDs[t] ]++;
  337. pred = m_tmap[t] - prev;
  338. m_ctfans.PushTriangleIndex(pred);
  339. prev = m_tmap[t] + 1;
  340. }
  341. for (long tt = 0; tt < numTriangles; ++tt)
  342. {
  343. m_invTMap[m_tmap[tt]] = tt;
  344. }
  345. }
  346. m_ctfans.Save(bstream, encodeTrianglesOrder, m_streamType);
  347. return O3DGC_OK;
  348. }
  349. template <class T>
  350. O3DGCErrorCode TriangleListEncoder<T>::CompueLocalConnectivityInfo(const long focusVertex)
  351. {
  352. long t, v, p;
  353. m_numNonConqueredTriangles = 0;
  354. m_numConqueredTriangles = 0;
  355. m_numVisitedVertices = 0;
  356. for(long i = m_vertexToTriangle.Begin(focusVertex); i < m_vertexToTriangle.End(focusVertex); ++i)
  357. {
  358. t = m_vertexToTriangle.GetNeighbor(i);
  359. if ( m_ttags[t] == 0) // non-processed triangle
  360. {
  361. m_nonConqueredTriangles[m_numNonConqueredTriangles] = t;
  362. CompueOppositeEdge( focusVertex,
  363. m_triangles + (3*t),
  364. m_nonConqueredEdges[m_numNonConqueredTriangles*2],
  365. m_nonConqueredEdges[m_numNonConqueredTriangles*2+1]);
  366. ++m_numNonConqueredTriangles;
  367. }
  368. else // triangle already processed
  369. {
  370. m_numConqueredTriangles++;
  371. p = 3*t;
  372. // extract visited vertices
  373. for(long k = 0; k < 3; ++k)
  374. {
  375. v = m_triangles[p+k];
  376. if (m_vmap[v] > m_vmap[focusVertex]) // vertices are insertices by increasing traversal order
  377. {
  378. bool foundOrInserted = false;
  379. for (long j = 0; j < m_numVisitedVertices; ++j)
  380. {
  381. if (m_vmap[v] == m_visitedVertices[j])
  382. {
  383. m_visitedVerticesValence[j]++;
  384. foundOrInserted = true;
  385. break;
  386. }
  387. else if (m_vmap[v] < m_visitedVertices[j])
  388. {
  389. ++m_numVisitedVertices;
  390. for (long h = m_numVisitedVertices-1; h > j; --h)
  391. {
  392. m_visitedVertices[h] = m_visitedVertices[h-1];
  393. m_visitedVerticesValence[h] = m_visitedVerticesValence[h-1];
  394. }
  395. m_visitedVertices[j] = m_vmap[v];
  396. m_visitedVerticesValence[j] = 1;
  397. foundOrInserted = true;
  398. break;
  399. }
  400. }
  401. if (!foundOrInserted)
  402. {
  403. m_visitedVertices[m_numVisitedVertices] = m_vmap[v];
  404. m_visitedVerticesValence[m_numVisitedVertices] = 1;
  405. m_numVisitedVertices++;
  406. }
  407. }
  408. }
  409. }
  410. }
  411. // re-order visited vertices by taking into account their valence (i.e., # of conquered triangles incident to each vertex)
  412. // in order to avoid config. 9
  413. if (m_numVisitedVertices > 2)
  414. {
  415. long y;
  416. for(long x = 1; x < m_numVisitedVertices; ++x)
  417. {
  418. if (m_visitedVerticesValence[x] == 1)
  419. {
  420. y = x;
  421. while( (y > 0) && (m_visitedVerticesValence[y] < m_visitedVerticesValence[y-1]) )
  422. {
  423. swap(m_visitedVerticesValence[y], m_visitedVerticesValence[y-1]);
  424. swap(m_visitedVertices[y], m_visitedVertices[y-1]);
  425. --y;
  426. }
  427. }
  428. }
  429. }
  430. if (m_numNonConqueredTriangles > 0)
  431. {
  432. // compute triangle-to-triangle adjacency information
  433. m_triangleToTriangle.AllocateNumNeighborsArray(m_numNonConqueredTriangles);
  434. m_triangleToTriangle.ClearNumNeighborsArray();
  435. m_triangleToTriangleInv.AllocateNumNeighborsArray(m_numNonConqueredTriangles);
  436. m_triangleToTriangleInv.ClearNumNeighborsArray();
  437. long * const numNeighbors = m_triangleToTriangle.GetNumNeighborsBuffer();
  438. long * const invNumNeighbors = m_triangleToTriangleInv.GetNumNeighborsBuffer();
  439. for(long i = 0; i < m_numNonConqueredTriangles; ++i)
  440. {
  441. for(long j = i+1; j < m_numNonConqueredTriangles; ++j)
  442. {
  443. if (m_nonConqueredEdges[2*i+1] == m_nonConqueredEdges[2*j]) // edge i is connected to edge j
  444. {
  445. ++numNeighbors[i];
  446. ++invNumNeighbors[j];
  447. }
  448. if (m_nonConqueredEdges[2*i] == m_nonConqueredEdges[2*j+1]) // edge i is connected to edge j
  449. {
  450. ++numNeighbors[j];
  451. ++invNumNeighbors[i];
  452. }
  453. }
  454. }
  455. m_triangleToTriangle.AllocateNeighborsArray();
  456. m_triangleToTriangle.ClearNeighborsArray();
  457. m_triangleToTriangleInv.AllocateNeighborsArray();
  458. m_triangleToTriangleInv.ClearNeighborsArray();
  459. for(long i = 0; i < m_numNonConqueredTriangles; ++i)
  460. {
  461. for(long j = 1; j < m_numNonConqueredTriangles; ++j)
  462. {
  463. if (m_nonConqueredEdges[2*i+1] == m_nonConqueredEdges[2*j]) // edge i is connected to edge j
  464. {
  465. m_triangleToTriangle.AddNeighbor(i, j);
  466. m_triangleToTriangleInv.AddNeighbor(j, i);
  467. }
  468. if (m_nonConqueredEdges[2*i] == m_nonConqueredEdges[2*j+1]) // edge i is connected to edge j
  469. {
  470. m_triangleToTriangle.AddNeighbor(j, i);
  471. m_triangleToTriangleInv.AddNeighbor(i, j);
  472. }
  473. }
  474. }
  475. }
  476. return O3DGC_OK;
  477. }
  478. template <class T>
  479. O3DGCErrorCode TriangleListEncoder<T>::ComputeTFANDecomposition(const long focusVertex)
  480. {
  481. long processedTriangles = 0;
  482. long minNumInputEdges;
  483. long numInputEdges;
  484. long indexSeedTriangle;
  485. long seedTriangle;
  486. long currentIndex;
  487. long currentTriangle;
  488. long i0, i1, index;
  489. m_tfans.Clear();
  490. while (processedTriangles != m_numNonConqueredTriangles)
  491. {
  492. // find non processed triangle with lowest number of inputs
  493. minNumInputEdges = m_numTriangles;
  494. indexSeedTriangle = -1;
  495. for(long i = 0; i < m_numNonConqueredTriangles; ++i)
  496. {
  497. numInputEdges = m_triangleToTriangleInv.GetNumNeighbors(i);
  498. if ( !m_ttags[m_nonConqueredTriangles[i]] &&
  499. numInputEdges < minNumInputEdges )
  500. {
  501. minNumInputEdges = numInputEdges;
  502. indexSeedTriangle = i;
  503. if (minNumInputEdges == 0) // found boundary triangle
  504. {
  505. break;
  506. }
  507. }
  508. }
  509. assert(indexSeedTriangle >= 0);
  510. seedTriangle = m_nonConqueredTriangles[indexSeedTriangle];
  511. m_tfans.AddTFAN();
  512. m_tfans.AddVertex( focusVertex );
  513. m_tfans.AddVertex( m_nonConqueredEdges[indexSeedTriangle*2] );
  514. m_tfans.AddVertex( m_nonConqueredEdges[indexSeedTriangle*2 + 1] );
  515. m_ttags[ seedTriangle ] = 1; // mark triangle as processed
  516. m_tmap[seedTriangle] = m_triangleCount++;
  517. m_invTMap[m_tmap[seedTriangle]] = seedTriangle;
  518. ++processedTriangles;
  519. currentIndex = indexSeedTriangle;
  520. currentTriangle = seedTriangle;
  521. do
  522. {
  523. // find next triangle
  524. i0 = m_triangleToTriangle.Begin(currentIndex);
  525. i1 = m_triangleToTriangle.End(currentIndex);
  526. currentIndex = -1;
  527. for(long i = i0; i < i1; ++i)
  528. {
  529. index = m_triangleToTriangle.GetNeighbor(i);
  530. currentTriangle = m_nonConqueredTriangles[index];
  531. if ( !m_ttags[currentTriangle] )
  532. {
  533. currentIndex = index;
  534. m_tfans.AddVertex( m_nonConqueredEdges[currentIndex*2+1] );
  535. m_ttags[currentTriangle] = 1; // mark triangle as processed
  536. m_tmap [currentTriangle] = m_triangleCount++;
  537. m_invTMap[m_tmap [currentTriangle]] = currentTriangle;
  538. ++processedTriangles;
  539. break;
  540. }
  541. }
  542. } while (currentIndex != -1);
  543. }
  544. return O3DGC_OK;
  545. }
  546. template <class T>
  547. O3DGCErrorCode TriangleListEncoder<T>::CompressTFAN(const long focusVertex)
  548. {
  549. m_ctfans.PushNumTFans(m_tfans.GetNumTFANs());
  550. const long ntfans = m_tfans.GetNumTFANs();
  551. long degree;
  552. long k0, k1;
  553. long v0;
  554. long ops[O3DGC_MAX_TFAN_SIZE];
  555. long indices[O3DGC_MAX_TFAN_SIZE];
  556. long numOps;
  557. long numIndices;
  558. long pos;
  559. long found;
  560. if (m_tfans.GetNumTFANs() > 0)
  561. {
  562. for(long f = 0; f != ntfans; f++)
  563. {
  564. degree = m_tfans.GetTFANSize(f) - 1;
  565. m_ctfans.PushDegree(degree-2+ m_numConqueredTriangles);
  566. numOps = 0;
  567. numIndices = 0;
  568. k0 = 1 + m_tfans.Begin(f);
  569. k1 = m_tfans.End(f);
  570. for(long k = k0; k < k1; k++)
  571. {
  572. v0 = m_tfans.GetVertex(k);
  573. if (m_vtags[v0] == 0)
  574. {
  575. ops[numOps++] = 0;
  576. m_vtags[v0] = 1;
  577. m_vmap[v0] = m_vertexCount++;
  578. m_invVMap[m_vmap[v0]] = v0;
  579. m_vfifo.PushBack(v0);
  580. m_visitedVertices[m_numVisitedVertices++] = m_vmap[v0];
  581. }
  582. else
  583. {
  584. ops[numOps++] = 1;
  585. pos = 0;
  586. found = 0;
  587. for(long u=0; u < m_numVisitedVertices; ++u)
  588. {
  589. pos++;
  590. if (m_visitedVertices[u] == m_vmap[v0])
  591. {
  592. found = 1;
  593. break;
  594. }
  595. }
  596. if (found == 1)
  597. {
  598. indices[numIndices++] = -pos;
  599. }
  600. else
  601. {
  602. indices[numIndices++] = m_vmap[v0] - m_vmap[focusVertex];
  603. }
  604. }
  605. }
  606. //-----------------------------------------------
  607. if (IsCase0(degree, numIndices, ops, indices))
  608. {
  609. // ops: 1000001 vertices: -1 -2
  610. m_ctfans.PushConfig(0);
  611. }
  612. else if (IsCase1(degree, numIndices, ops, indices))
  613. {
  614. // ops: 1xxxxxx1 vertices: -1 x x x x x -2
  615. long u = 1;
  616. for(u = 1; u < degree-1; u++)
  617. {
  618. m_ctfans.PushOperation(ops[u]);
  619. }
  620. for(u =1; u < numIndices-1; u++)
  621. {
  622. m_ctfans.PushIndex(indices[u]);
  623. }
  624. m_ctfans.PushConfig(1);
  625. }
  626. else if (IsCase2(degree, numIndices, ops, indices))
  627. {
  628. // ops: 00000001 vertices: -1
  629. m_ctfans.PushConfig(2);
  630. }
  631. else if (IsCase3(degree, numIndices, ops, indices))
  632. {
  633. // ops: 00000001 vertices: -2
  634. m_ctfans.PushConfig(3);
  635. }
  636. else if (IsCase4(degree, numIndices, ops, indices))
  637. {
  638. // ops: 10000000 vertices: -1
  639. m_ctfans.PushConfig(4);
  640. }
  641. else if (IsCase5(degree, numIndices, ops, indices))
  642. {
  643. // ops: 10000000 vertices: -2
  644. m_ctfans.PushConfig(5);
  645. }
  646. else if (IsCase6(degree, numIndices, ops, indices))
  647. {
  648. // ops: 00000000 vertices:
  649. m_ctfans.PushConfig(6);
  650. }
  651. else if (IsCase7(degree, numIndices, ops, indices))
  652. {
  653. // ops: 1000001 vertices: -1 -2
  654. m_ctfans.PushConfig(7);
  655. }
  656. else if (IsCase8(degree, numIndices, ops, indices))
  657. {
  658. // ops: 1xxxxxx1 vertices: -2 x x x x x -1
  659. long u = 1;
  660. for(u =1; u < degree-1; u++)
  661. {
  662. m_ctfans.PushOperation(ops[u]);
  663. }
  664. for(u =1; u < numIndices-1; u++)
  665. {
  666. m_ctfans.PushIndex(indices[u]);
  667. }
  668. m_ctfans.PushConfig(8);
  669. }
  670. else
  671. {
  672. long u = 0;
  673. for(u =0; u < degree; u++)
  674. {
  675. m_ctfans.PushOperation(ops[u]);
  676. }
  677. for(u =0; u < numIndices; u++)
  678. {
  679. m_ctfans.PushIndex(indices[u]);
  680. }
  681. m_ctfans.PushConfig(9);
  682. }
  683. }
  684. }
  685. return O3DGC_OK;
  686. }
  687. template <class T>
  688. O3DGCErrorCode TriangleListEncoder<T>::ProcessVertex(const long focusVertex)
  689. {
  690. CompueLocalConnectivityInfo(focusVertex);
  691. ComputeTFANDecomposition(focusVertex);
  692. CompressTFAN(focusVertex);
  693. return O3DGC_OK;
  694. }
  695. }
  696. #endif //O3DGC_TRIANGLE_LIST_ENCODER_INL