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