Blender  V3.3
GeomCleaner.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
8 #if 0
9 # if defined(__GNUC__) && (__GNUC__ >= 3)
10 // hash_map is not part of the C++ standard anymore;
11 // hash_map.h has been kept though for backward compatibility
12 # include <hash_map.h>
13 # else
14 # include <hash_map>
15 # endif
16 #endif
17 
18 #include <cstdio>
19 #include <list>
20 #include <map>
21 
22 #include "GeomCleaner.h"
23 
24 #include "../system/TimeUtils.h"
25 
26 #include "BKE_global.h"
27 
28 using namespace std;
29 
30 namespace Freestyle {
31 
32 void GeomCleaner::SortIndexedVertexArray(const float *iVertices,
33  unsigned iVSize,
34  const unsigned *iIndices,
35  unsigned iISize,
36  float **oVertices,
37  unsigned **oIndices)
38 {
39  // First, we build a list of IndexVertex:
40  list<IndexedVertex> indexedVertices;
41  unsigned i;
42  for (i = 0; i < iVSize; i += 3) {
43  indexedVertices.emplace_back(Vec3f(iVertices[i], iVertices[i + 1], iVertices[i + 2]), i / 3);
44  }
45 
46  // q-sort
47  indexedVertices.sort();
48 
49  // build the indices mapping array:
50  unsigned *mapIndices = new unsigned[iVSize / 3];
51  *oVertices = new float[iVSize];
52  list<IndexedVertex>::iterator iv;
53  unsigned newIndex = 0;
54  unsigned vIndex = 0;
55  for (iv = indexedVertices.begin(); iv != indexedVertices.end(); iv++) {
56  // Build the final results:
57  (*oVertices)[vIndex] = iv->x();
58  (*oVertices)[vIndex + 1] = iv->y();
59  (*oVertices)[vIndex + 2] = iv->z();
60 
61  mapIndices[iv->index()] = newIndex;
62  newIndex++;
63  vIndex += 3;
64  }
65 
66  // Build the final index array:
67  *oIndices = new unsigned[iISize];
68  for (i = 0; i < iISize; i++) {
69  (*oIndices)[i] = 3 * mapIndices[iIndices[i] / 3];
70  }
71 
72  delete[] mapIndices;
73 }
74 
75 void GeomCleaner::CompressIndexedVertexArray(const float *iVertices,
76  unsigned iVSize,
77  const unsigned *iIndices,
78  unsigned iISize,
79  float **oVertices,
80  unsigned *oVSize,
81  unsigned **oIndices)
82 {
83  // First, we build a list of IndexVertex:
84  vector<Vec3f> vertices;
85  unsigned i;
86  for (i = 0; i < iVSize; i += 3) {
87  vertices.emplace_back(iVertices[i], iVertices[i + 1], iVertices[i + 2]);
88  }
89 
90  unsigned *mapVertex = new unsigned[iVSize];
91  vector<Vec3f>::iterator v = vertices.begin();
92 
93  vector<Vec3f> compressedVertices;
94  Vec3f previous = *v;
95  mapVertex[0] = 0;
96  compressedVertices.push_back(vertices.front());
97 
98  v++;
99  Vec3f current;
100  i = 1;
101  for (; v != vertices.end(); v++) {
102  current = *v;
103  if (current == previous) {
104  mapVertex[i] = compressedVertices.size() - 1;
105  }
106  else {
107  compressedVertices.push_back(current);
108  mapVertex[i] = compressedVertices.size() - 1;
109  }
110  previous = current;
111  i++;
112  }
113 
114  // Builds the resulting vertex array:
115  *oVSize = 3 * compressedVertices.size();
116  *oVertices = new float[*oVSize];
117  i = 0;
118  for (v = compressedVertices.begin(); v != compressedVertices.end(); v++) {
119  (*oVertices)[i] = (*v)[0];
120  (*oVertices)[i + 1] = (*v)[1];
121  (*oVertices)[i + 2] = (*v)[2];
122  i += 3;
123  }
124 
125  // Map the index array:
126  *oIndices = new unsigned[iISize];
127  for (i = 0; i < iISize; i++) {
128  (*oIndices)[i] = 3 * mapVertex[iIndices[i] / 3];
129  }
130 
131  delete[] mapVertex;
132 }
133 
134 void GeomCleaner::SortAndCompressIndexedVertexArray(const float *iVertices,
135  unsigned iVSize,
136  const unsigned *iIndices,
137  unsigned iISize,
138  float **oVertices,
139  unsigned *oVSize,
140  unsigned **oIndices)
141 {
142  // tmp arrays used to store the sorted data:
143  float *tmpVertices;
144  unsigned *tmpIndices;
145 
146  Chronometer chrono;
147  // Sort data
148  chrono.start();
149  GeomCleaner::SortIndexedVertexArray(
150  iVertices, iVSize, iIndices, iISize, &tmpVertices, &tmpIndices);
151  if (G.debug & G_DEBUG_FREESTYLE) {
152  printf("Sorting: %lf sec.\n", chrono.stop());
153  }
154 
155  // compress data
156  chrono.start();
157  GeomCleaner::CompressIndexedVertexArray(
158  tmpVertices, iVSize, tmpIndices, iISize, oVertices, oVSize, oIndices);
159  real duration = chrono.stop();
160  if (G.debug & G_DEBUG_FREESTYLE) {
161  printf("Merging: %lf sec.\n", duration);
162  }
163 
164  // deallocates memory:
165  delete[] tmpVertices;
166  delete[] tmpIndices;
167 }
168 
171 #define _MUL 950706376UL
172 #define _MOD 2147483647UL
173  inline size_t operator()(const Vec3r &p) const
174  {
175  size_t res = ((unsigned long)(p[0] * _MUL)) % _MOD;
176  res = ((res + (unsigned long)(p[1]) * _MUL)) % _MOD;
177  return ((res + (unsigned long)(p[2]) * _MUL)) % _MOD;
178  }
179 #undef _MUL
180 #undef _MOD
181 };
182 
183 void GeomCleaner::CleanIndexedVertexArray(const float *iVertices,
184  unsigned iVSize,
185  const unsigned *iIndices,
186  unsigned iISize,
187  float **oVertices,
188  unsigned *oVSize,
189  unsigned **oIndices)
190 {
191  using cleanHashTable = map<Vec3f, unsigned>;
192  vector<Vec3f> vertices;
193  unsigned i;
194  for (i = 0; i < iVSize; i += 3) {
195  vertices.emplace_back(iVertices[i], iVertices[i + 1], iVertices[i + 2]);
196  }
197 
198  cleanHashTable ht;
199  vector<unsigned> newIndices;
200  vector<Vec3f> newVertices;
201 
202  // elimination of needless points
203  unsigned currentIndex = 0;
204  vector<Vec3f>::const_iterator v = vertices.begin();
205  vector<Vec3f>::const_iterator end = vertices.end();
206  cleanHashTable::const_iterator found;
207  for (; v != end; v++) {
208  found = ht.find(*v);
209  if (found != ht.end()) {
210  // The vertex is already in the new array.
211  newIndices.push_back((*found).second);
212  }
213  else {
214  newVertices.push_back(*v);
215  newIndices.push_back(currentIndex);
216  ht[*v] = currentIndex;
217  currentIndex++;
218  }
219  }
220 
221  // creation of oVertices array:
222  *oVSize = 3 * newVertices.size();
223  *oVertices = new float[*oVSize];
224  currentIndex = 0;
225  end = newVertices.end();
226  for (v = newVertices.begin(); v != end; v++) {
227  (*oVertices)[currentIndex++] = (*v)[0];
228  (*oVertices)[currentIndex++] = (*v)[1];
229  (*oVertices)[currentIndex++] = (*v)[2];
230  }
231 
232  // map new indices:
233  *oIndices = new unsigned[iISize];
234  for (i = 0; i < iISize; i++) {
235  (*oIndices)[i] = 3 * newIndices[iIndices[i] / 3];
236  }
237 }
238 
239 } /* namespace Freestyle */
@ G_DEBUG_FREESTYLE
Definition: BKE_global.h:181
#define _MOD
#define _MUL
Class to define a cleaner of geometry providing a set of useful tools.
ATTR_WARN_UNUSED_RESULT const BMVert * v
struct Vec3f Vec3f
#define G(x, y, z)
inherits from class Rep
Definition: AppCanvas.cpp:18
double real
Definition: Precision.h:12
size_t operator()(const Vec3r &p) const