Cleanup: preprocessor indentation
[blender.git] / source / blender / freestyle / intern / geometry / GeomCleaner.cpp
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/freestyle/intern/geometry/GeomCleaner.cpp
22  *  \ingroup freestyle
23  *  \brief Class to define a cleaner of geometry providing a set of useful tools
24  *  \author Stephane Grabli
25  *  \date 04/03/2002
26  */
27
28 #if 0
29 #if defined(__GNUC__) && (__GNUC__ >= 3)
30 // hash_map is not part of the C++ standard anymore;
31 // hash_map.h has been kept though for backward compatibility
32 #  include <hash_map.h>
33 #else
34 #  include <hash_map>
35 #endif
36 #endif
37
38 #include <stdio.h>
39 #include <list>
40 #include <map>
41
42 #include "GeomCleaner.h"
43
44 #include "../system/TimeUtils.h"
45
46 #include "BKE_global.h"
47
48 using namespace std;
49
50 namespace Freestyle {
51
52 void GeomCleaner::SortIndexedVertexArray(const float *iVertices, unsigned iVSize, const unsigned *iIndices,
53                                          unsigned iISize, float **oVertices, unsigned **oIndices)
54 {
55         // First, we build a list of IndexVertex:
56         list<IndexedVertex> indexedVertices;
57         unsigned i;
58         for (i = 0; i < iVSize; i += 3) {
59                 indexedVertices.push_back(IndexedVertex(Vec3f(iVertices[i], iVertices[i + 1], iVertices[i + 2]), i / 3));
60         }
61
62         // q-sort
63         indexedVertices.sort();
64
65         // build the indices mapping array:
66         unsigned *mapIndices = new unsigned[iVSize / 3];
67         *oVertices = new float[iVSize];
68         list<IndexedVertex>::iterator iv;
69         unsigned newIndex = 0;
70         unsigned vIndex = 0;
71         for (iv = indexedVertices.begin(); iv != indexedVertices.end(); iv++) {
72                 // Build the final results:
73                 (*oVertices)[vIndex] = iv->x();
74                 (*oVertices)[vIndex + 1] = iv->y();
75                 (*oVertices)[vIndex + 2] = iv->z();
76
77                 mapIndices[iv->index()] = newIndex;
78                 newIndex++;
79                 vIndex += 3;
80         }
81
82         // Build the final index array:
83         *oIndices = new unsigned[iISize];
84         for (i = 0; i < iISize; i++) {
85                 (*oIndices)[i] = 3 * mapIndices[iIndices[i] / 3];
86         }
87
88         delete [] mapIndices;
89 }
90
91 void GeomCleaner::CompressIndexedVertexArray(const float *iVertices, unsigned iVSize, const unsigned *iIndices,
92                                              unsigned iISize, float **oVertices, unsigned *oVSize, unsigned **oIndices)
93 {
94         // First, we build a list of IndexVertex:
95         vector<Vec3f> vertices;
96         unsigned i;
97         for (i = 0; i < iVSize; i += 3) {
98                 vertices.push_back(Vec3f(iVertices[i], iVertices[i + 1], iVertices[i + 2]));
99         }
100
101         unsigned *mapVertex = new unsigned[iVSize];
102         vector<Vec3f>::iterator v = vertices.begin();
103
104         vector<Vec3f> compressedVertices;
105         Vec3f previous = *v;
106         mapVertex[0] = 0;
107         compressedVertices.push_back(vertices.front());
108
109         v++;
110         Vec3f current;
111         i = 1;
112         for (; v != vertices.end(); v++) {
113                 current = *v;
114                 if (current == previous)
115                         mapVertex[i] = compressedVertices.size() - 1;
116                 else {
117                         compressedVertices.push_back(current);
118                         mapVertex[i] = compressedVertices.size() - 1;
119                 }
120                 previous = current;
121                 i++;
122         }
123
124         // Builds the resulting vertex array:
125         *oVSize = 3 * compressedVertices.size();
126         *oVertices = new float[*oVSize];
127         i = 0;
128         for (v = compressedVertices.begin(); v != compressedVertices.end(); v++) {
129                 (*oVertices)[i] = (*v)[0];
130                 (*oVertices)[i + 1] = (*v)[1];
131                 (*oVertices)[i + 2] = (*v)[2];
132                 i += 3;
133         }
134
135         // Map the index array:
136         *oIndices = new unsigned[iISize];
137         for (i = 0; i < iISize; i++) {
138                 (*oIndices)[i] = 3 * mapVertex[iIndices[i] / 3];
139         }
140
141         delete [] mapVertex;
142 }
143
144 void GeomCleaner::SortAndCompressIndexedVertexArray(const float *iVertices, unsigned iVSize, const unsigned *iIndices,
145                                                     unsigned iISize, float **oVertices, unsigned *oVSize,
146                                                     unsigned **oIndices)
147 {
148         // tmp arrays used to store the sorted data:
149         float *tmpVertices;
150         unsigned *tmpIndices;
151
152         Chronometer chrono;
153         // Sort data
154         chrono.start();
155         GeomCleaner::SortIndexedVertexArray(iVertices, iVSize, iIndices, iISize, &tmpVertices, &tmpIndices);
156         if (G.debug & G_DEBUG_FREESTYLE) {
157                 printf("Sorting: %lf sec.\n", chrono.stop());
158         }
159
160         // compress data
161         chrono.start();
162         GeomCleaner::CompressIndexedVertexArray(tmpVertices, iVSize, tmpIndices, iISize, oVertices, oVSize, oIndices);
163         real duration = chrono.stop();
164         if (G.debug & G_DEBUG_FREESTYLE) {
165                 printf("Merging: %lf sec.\n", duration);
166         }
167
168         // deallocates memory:
169         delete [] tmpVertices;
170         delete [] tmpIndices;
171 }
172
173 /*! Defines a hash table used for searching the Cells */
174 struct GeomCleanerHasher {
175 #define _MUL 950706376UL
176 #define _MOD 2147483647UL
177         inline size_t operator() (const Vec3r& p) const
178         {
179                 size_t res = ((unsigned long) (p[0] * _MUL)) % _MOD;
180                 res = ((res + (unsigned long) (p[1]) * _MUL)) % _MOD;
181                 return ((res +(unsigned long) (p[2]) * _MUL)) % _MOD;
182         }
183 #undef _MUL
184 #undef _MOD
185 };
186
187 void GeomCleaner::CleanIndexedVertexArray(const float *iVertices, unsigned iVSize, const unsigned *iIndices,
188                                           unsigned iISize, float **oVertices, unsigned *oVSize, unsigned **oIndices)
189 {
190         typedef map<Vec3f, unsigned> cleanHashTable;
191         vector<Vec3f> vertices;
192         unsigned i;
193         for (i = 0; i < iVSize; i += 3)
194                 vertices.push_back(Vec3f(iVertices[i], iVertices[i + 1], iVertices[i + 2]));
195
196         cleanHashTable ht;
197         vector<unsigned> newIndices;
198         vector<Vec3f> newVertices;
199
200         // elimination of needless points
201         unsigned currentIndex = 0;
202         vector<Vec3f>::const_iterator v = vertices.begin();
203         vector<Vec3f>::const_iterator end = vertices.end();
204         cleanHashTable::const_iterator found;
205         for (; v != end; v++) {
206                 found = ht.find(*v);
207                 if (found != ht.end()) {
208                         // The vertex is already in the new array.
209                         newIndices.push_back((*found).second);
210                 }
211                 else {
212                         newVertices.push_back(*v);
213                         newIndices.push_back(currentIndex);
214                         ht[*v] = currentIndex;
215                         currentIndex++;
216                 }
217         }
218
219         // creation of oVertices array:
220         *oVSize = 3 * newVertices.size();
221         *oVertices = new float[*oVSize];
222         currentIndex = 0;
223         end = newVertices.end();
224         for (v = newVertices.begin(); v != end ; v++) {
225                 (*oVertices)[currentIndex++] = (*v)[0];
226                 (*oVertices)[currentIndex++] = (*v)[1];
227                 (*oVertices)[currentIndex++] = (*v)[2];
228         }
229
230         // map new indices:
231         *oIndices = new unsigned[iISize];
232         for (i = 0; i < iISize; i++)
233                 (*oIndices)[i] = 3 * newIndices[iIndices[i] / 3];
234 }
235
236 } /* namespace Freestyle */