Visualization Library 2.1.0

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
PolygonSimplifier.cpp
Go to the documentation of this file.
1 /**************************************************************************************/
2 /* */
3 /* Visualization Library */
4 /* http://visualizationlibrary.org */
5 /* */
6 /* Copyright (c) 2005-2020, Michele Bosi */
7 /* All rights reserved. */
8 /* */
9 /* Redistribution and use in source and binary forms, with or without modification, */
10 /* are permitted provided that the following conditions are met: */
11 /* */
12 /* - Redistributions of source code must retain the above copyright notice, this */
13 /* list of conditions and the following disclaimer. */
14 /* */
15 /* - Redistributions in binary form must reproduce the above copyright notice, this */
16 /* list of conditions and the following disclaimer in the documentation and/or */
17 /* other materials provided with the distribution. */
18 /* */
19 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */
20 /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */
21 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */
22 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR */
23 /* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES */
24 /* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */
25 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON */
26 /* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */
27 /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */
28 /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
29 /* */
30 /**************************************************************************************/
31 
34 #include <vlCore/Time.hpp>
35 #include <vlCore/Log.hpp>
36 #include <vlCore/Say.hpp>
37 #include <set>
38 
39 using namespace vl;
40 
41 //-----------------------------------------------------------------------------
42 namespace
43 {
44  class VertexPtrWrapper
45  {
46  public:
47  VertexPtrWrapper(PolygonSimplifier::Vertex* ptr=NULL): mVertex(ptr) {}
48 
49  bool operator==(const VertexPtrWrapper& other) const
50  {
51  return mVertex == other.mVertex;
52  }
53 
54  bool operator!=(const VertexPtrWrapper& other) const
55  {
56  return mVertex == other.mVertex;
57  }
58 
59  bool operator<(const VertexPtrWrapper& other) const
60  {
61  if ( mVertex->collapseCost() != other.mVertex->collapseCost() )
62  return mVertex->collapseCost() < other.mVertex->collapseCost();
63  else
64  return mVertex < other.mVertex;
65  }
67  };
68 }
69 //-----------------------------------------------------------------------------
71 {
72  if (!mInput)
73  {
74  Log::error("PolygonSimplifier::simplify() : no input Geometry specified.\n");
75  return;
76  }
77 
78  // we don't support vertex attributes of any kind yet
79  #ifndef NDEBUG
80  bool problem = false;
81  for( int i = VA_Position + 1; i < VA_MaxAttribCount; ++i )
82  problem |= mInput->vertexAttribArray(i) != NULL;
83  if (problem)
84  Log::warning("PolygonSimplifier::simplify() simplifies only the position array of a Geometry, the other attibutes will be discarded.\n");
85  #endif
86 
87  Time timer;
88  timer.start();
89 
90  if ( removeDoubles() )
91  {
92  DoubleVertexRemover remover;
93  remover.removeDoubles( mInput.get() );
94  }
95 
96  std::vector<fvec3> verts;
97  std::vector<int> indices;
98  indices.reserve(1000);
99 
100  // merge all triangles in a single DrawElementsUInt
102  for( size_t i=0; i<mInput->drawCalls().size(); ++i )
103  {
104  DrawCall* prim = mInput->drawCalls().at(i);
105  for(TriangleIterator trit = prim->triangleIterator(); trit.hasNext(); trit.next())
106  {
107  indices.push_back( trit.a() );
108  indices.push_back( trit.b() );
109  indices.push_back( trit.c() );
110  }
111  }
112 
113  if (indices.empty())
114  {
115  Log::warning("PolygonSimplifier::simplify() : no triangles found in input Geometry.\n");
116  return;
117  }
118 
119  ArrayAbstract* posarr = mInput->vertexArray();
120 
121  if (!posarr)
122  {
123  Log::warning("PolygonSimplifier::simplify() : no vertices found in input Geometry.\n");
124  return;
125  }
126 
127  // fill vertices
128  verts.resize( posarr->size() );
129  for( size_t i=0; i< posarr->size(); ++i )
130  verts[i] = (fvec3)posarr->getAsVec3(i);
131 
132  if (verts.empty())
133  {
134  Log::warning("PolygonSimplifier::simplify() : no vertices found in input Geometry.\n");
135  return;
136  }
137 
138  simplify(verts, indices);
139 
140  if (verbose())
141  Log::print( Say("PolygonSimplifier::simplify() done in %.3ns\n") << timer.elapsed() );
142 }
143 //-----------------------------------------------------------------------------
144 void PolygonSimplifier::simplify(const std::vector<fvec3>& in_verts, const std::vector<int>& in_tris)
145 {
146  if (verbose())
147  Log::print("PolygonSimplifier::simplify() starting ... \n");
148 
149  Time timer;
150  timer.start();
151 
152  // sort simplification targets 1.0 -> 0.0
153  std::sort(mTargets.begin(), mTargets.end());
154  std::reverse(mTargets.begin(), mTargets.end());
155 
156  mSimplifiedVertices.clear();
157  mSimplifiedTriangles.clear();
158  mProtectedVerts.clear();
159  mTriangleLump.clear();
160  mVertexLump.clear(); // mic fixme: this is the one taking time.
161 
162  // preallocate vertices and triangles in one chunk
163  mTriangleLump.resize(in_tris.size()/3);
164  mVertexLump.resize(in_verts.size());
165 
166  int polys_before = (int)in_tris.size() / 3;
167  int verts_before = (int)in_verts.size();
168 
169  mSimplifiedTriangles.resize( in_tris.size() / 3 );
170  mSimplifiedVertices.resize( in_verts.size() );
171 
172 #define SHUFFLE_VERTICES 0
173 
174 #if SHUFFLE_VERTICES
175  std::vector<Vertex*> vertex_pool;
176  vertex_pool.resize( in_verts.size() );
177  for(int i=0; i<(int)mVertexLump.size(); ++i)
178  vertex_pool[i] = &mVertexLump[i];
179 
180  // shuffle the vertices
181  for(int i=0; i<(int)vertex_pool.size(); ++i)
182  {
183  int a = int( (float)rand() / (RAND_MAX+1) * vertex_pool.size() );
184  int b = int( (float)rand() / (RAND_MAX+1) * vertex_pool.size() );
185  Vertex* tmp = vertex_pool[a];
186  vertex_pool[a] = vertex_pool[b];
187  vertex_pool[b] = tmp;
188  }
189 #endif
190 
191  // initialize vertices
192  for(int ivert=0; ivert<(int)in_verts.size(); ++ivert)
193  {
194 #if SHUFFLE_VERTICES
195  mSimplifiedVertices[ivert] = vertex_pool[ivert];
196 #else
197  mSimplifiedVertices[ivert] = &mVertexLump[ivert];
198 #endif
199  mSimplifiedVertices[ivert]->mPosition = in_verts[ivert];
200  // so that the user knows which vertex is which and can regenerate per-vertex
201  // information like textures coordinates, colors etc.
202  mSimplifiedVertices[ivert]->mOriginalIndex = ivert;
203 
204  // unprotect the vertex
205  mSimplifiedVertices[ivert]->mProtected = false;
206 
207  // reserve the memory for quicker allocation
208  mSimplifiedVertices[ivert]->mIncidentTriangles.reserve(12);
209  mSimplifiedVertices[ivert]->mAdjacentVerts.reserve(12);
210  }
211 
212  // initialize triangles
213  for(int idx=0, itri=0; idx<(int)in_tris.size(); idx+=3, ++itri)
214  {
215  mSimplifiedTriangles[itri] = &mTriangleLump[itri];
216  mSimplifiedTriangles[itri]->mVertices[0] = mSimplifiedVertices[ in_tris[idx+0] ];
217  mSimplifiedTriangles[itri]->mVertices[1] = mSimplifiedVertices[ in_tris[idx+1] ];
218  mSimplifiedTriangles[itri]->mVertices[2] = mSimplifiedVertices[ in_tris[idx+2] ];
219  }
220 
221  // compute vertex/vertex and vertex/triangle connectivity
222  for(int itri=0; itri<(int)mSimplifiedTriangles.size(); ++itri)
223  {
224  // add this triangle to all its vertices
225  mSimplifiedTriangles[itri]->mVertices[0]->mIncidentTriangles.push_back( mSimplifiedTriangles[itri] );
226  mSimplifiedTriangles[itri]->mVertices[1]->mIncidentTriangles.push_back( mSimplifiedTriangles[itri] );
227  mSimplifiedTriangles[itri]->mVertices[2]->mIncidentTriangles.push_back( mSimplifiedTriangles[itri] );
228  // add adjacent vertices
229  mSimplifiedTriangles[itri]->mVertices[0]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[1] ); // vertex 0
230  mSimplifiedTriangles[itri]->mVertices[0]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[2] );
231  mSimplifiedTriangles[itri]->mVertices[1]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[0] ); // vertex 1
232  mSimplifiedTriangles[itri]->mVertices[1]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[2] );
233  mSimplifiedTriangles[itri]->mVertices[2]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[0] ); // vertex 2
234  mSimplifiedTriangles[itri]->mVertices[2]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[1] );
235  // compute normal
236  mSimplifiedTriangles[itri]->computeNormal();
237  // error
238  QErr qerr = mSimplifiedTriangles[itri]->computeQErr();
239  mSimplifiedTriangles[itri]->mVertices[0]->addQErr(qerr);
240  mSimplifiedTriangles[itri]->mVertices[1]->addQErr(qerr);
241  mSimplifiedTriangles[itri]->mVertices[2]->addQErr(qerr);
242  }
243 
244  // - remove vertices without triangles
245  // - compute edge penalties
246  // - initialize the collapse info of each vertex
247  for( int ivert=(int)mSimplifiedVertices.size(); ivert--; )
248  {
249  if ( mSimplifiedVertices[ivert]->incidentTrianglesCount() == 0 )
250  mSimplifiedVertices.erase( mSimplifiedVertices.begin() + ivert );
251  else
252  {
253  mSimplifiedVertices[ivert]->computeEdgePenalty();
254  computeCollapseInfo( mSimplifiedVertices[ivert] );
255  }
256  }
257 
258  // sets the protected vertices
259  for(int i=0; i<(int)mProtectedVerts.size(); ++i)
260  {
261  VL_CHECK(mProtectedVerts[i] < (int)mSimplifiedVertices.size() )
262  mSimplifiedVertices[ mProtectedVerts[i] ]->mProtected = true;
263  }
264 
265  if (verbose())
266  Log::print(Say("database setup = %.3n\n") << timer.elapsed() );
267 
268  std::set<VertexPtrWrapper> vertex_set;
269  for(int ivert=0; ivert<(int)mSimplifiedVertices.size(); ++ivert)
270  if ( !mSimplifiedVertices[ivert]->mProtected )
271  vertex_set.insert( mSimplifiedVertices[ivert] );
272 
273  if (verbose())
274  Log::print(Say("heap setup = %.3n\n") << timer.elapsed() );
275 
276  // loop through the simplification targets
277  for(size_t itarget=0, remove_order=0; itarget<mTargets.size(); ++itarget)
278  {
279  const int target_vertex_count = mTargets[itarget];
280 
281  if (target_vertex_count < 3)
282  {
283  Log::print(Say("Invalid target_vertex_count = %n\n") << target_vertex_count);
284  return;
285  }
286 
287  timer.start(1);
288 
289  std::vector< PolygonSimplifier::Vertex* > adj_verts;
290  for( ; (int)vertex_set.size()>target_vertex_count; ++remove_order )
291  {
292  std::set<VertexPtrWrapper>::iterator it = vertex_set.begin();
293  PolygonSimplifier::Vertex* v = it->mVertex;
294  v->mRemoveOrder = (int)remove_order;
295  vertex_set.erase(it);
296 
297  // remove the adjacent vertices to v and v->collapseVert()
298  adj_verts.clear();
299  for(int i=0; i<v->adjacentVerticesCount(); ++i)
300  {
301  VL_CHECK( v != v->adjacentVertex(i) )
303 
304  adj_verts.push_back( v->adjacentVertex(i) );
305  adj_verts.back()->mAlreadyProcessed = true;
306  vertex_set.erase( v->adjacentVertex(i) );
307  }
308  for(int i=0; i<v->collapseVertex()->adjacentVerticesCount(); ++i)
309  {
311  {
312  adj_verts.push_back( v->collapseVertex()->adjacentVertex(i) );
313  vertex_set.erase( v->collapseVertex()->adjacentVertex(i) );
314  }
315  }
316 
317  VL_CHECK(!v->removed())
320 
321  collapse( v );
322 
323  // reinsert the adj_verts if not removed
324  // NOTE: v->collapseVertex() might have been also removed
325  for( int i=(int)adj_verts.size(); i--; )
326  {
327  adj_verts[i]->mAlreadyProcessed = false;
328 
329  if ( adj_verts[i]->removed() )
330  continue;
331 
332  computeCollapseInfo( adj_verts[i] );
333 
334  VL_CHECK( adj_verts[i]->checkTriangles() )
335  VL_CHECK( adj_verts[i]->collapseVertex() != v )
336  VL_CHECK( !adj_verts[i]->collapseVertex()->removed() )
337 
338  vertex_set.insert( adj_verts[i] );
339  }
340  }
341 
342  if (verbose())
343  Log::print(Say("simplification = %.3ns (%.3ns)\n") << timer.elapsed() << timer.elapsed(1) );
344 
345  outputSimplifiedGeometry();
346  }
347 
348  if (verbose() && !output().empty())
349  {
350  float elapsed = (float)timer.elapsed();
351  int polys_after = output().back()->drawCalls().at(0)->countTriangles();
352  int verts_after = output().back()->vertexArray() ? (int)output().back()->vertexArray()->size() : 0;
353  Log::print(Say("POLYS: %n -> %n, %.2n%%, %.1nT/s\n") << polys_before << polys_after << 100.0f*verts_after/verts_before << (polys_before - polys_after)/elapsed );
354  Log::print(Say("VERTS: %n -> %n, %.2n%%, %.1nV/s\n") << verts_before << verts_after << 100.0f*verts_after/verts_before << (verts_before - verts_after)/elapsed );
355  }
356 }
357 //-----------------------------------------------------------------------------
359 {
360  // count vertices required
361  size_t vert_count = 0;
362  for(int i=0; i<(int)mSimplifiedVertices.size(); ++i)
363  vert_count += mSimplifiedVertices[i]->mRemoved ? 0 : 1;
364 
365  // regenerate vertex buffer & generate indices for index buffer
366  ref<ArrayFloat3> arr_f3 = new ArrayFloat3;
367  arr_f3->resize(vert_count);
368  for(int i=0, vert_index=0; i<(int)mSimplifiedVertices.size(); ++i)
369  {
370  if (!mSimplifiedVertices[i]->mRemoved)
371  {
372  arr_f3->at(vert_index) = mSimplifiedVertices[i]->mPosition;
373  mSimplifiedVertices[i]->mSimplifiedIndex = vert_index++;
374  }
375  }
376 
377  // count indices required
378  size_t index_count = 0;
379  for(size_t i=0; i<mSimplifiedTriangles.size(); ++i)
380  index_count += mSimplifiedTriangles[i]->mRemoved ? 0 : 3;
381 
382  // regenerate index buffer
384  de->indexBuffer()->resize(index_count);
386  for(size_t i=0; i<mSimplifiedTriangles.size(); ++i)
387  {
388  if(!mSimplifiedTriangles[i]->mRemoved)
389  {
390  VL_CHECK( !mSimplifiedTriangles[i]->mVertices[0]->mRemoved )
391  VL_CHECK( !mSimplifiedTriangles[i]->mVertices[1]->mRemoved )
392  VL_CHECK( !mSimplifiedTriangles[i]->mVertices[2]->mRemoved )
393 
394  ptr[0] = mSimplifiedTriangles[i]->mVertices[0]->mSimplifiedIndex;
395  ptr[1] = mSimplifiedTriangles[i]->mVertices[1]->mSimplifiedIndex;
396  ptr[2] = mSimplifiedTriangles[i]->mVertices[2]->mSimplifiedIndex;
397  ptr+=3;
398  }
399  }
400  VL_CHECK(ptr == de->indexBuffer()->end());
401 
402  // output geometry
403  mOutput.push_back( new Geometry );
404  mOutput.back()->setVertexArray( arr_f3.get() );
405  mOutput.back()->drawCalls().push_back( de.get() );
406 }
407 //-----------------------------------------------------------------------------
409 {
410  mSimplifiedVertices.clear();
411  mSimplifiedTriangles.clear();
412  mProtectedVerts.clear();
413  mTriangleLump.clear();
414  mVertexLump.clear();
415 }
416 //-----------------------------------------------------------------------------
The ArrayAbstract class defines an abstract interface to conveniently manipulate data stored in a Buf...
Definition: Array.hpp:58
void start(int index=0)
Definition: Time.hpp:76
bool hasNext()
Returns false if the iterator has reached the end of the triangle list.
real elapsed(int index=0) const
Definition: Time.hpp:82
bool mAlreadyProcessed
internally used
const T_VectorType * end() const
Definition: Array.hpp:249
const T * get() const
Definition: Object.hpp:128
A simple String formatting class.
Definition: Say.hpp:124
static void warning(const String &message)
Use this function to provide information about situations that might lead to errors or loss of data...
Definition: Log.cpp:155
bool removed() const
has the vertex been removed
static void error(const String &message)
Use this function to provide information about run-time errors: file not found, out of memory...
Definition: Log.cpp:165
int mRemoveOrder
when the vertex has collapsed
Removes from a Geometry the vertices with the same attributes.
void removeDoubles(Geometry *geom)
void resize(size_t dim)
Definition: Array.hpp:233
Vertex * collapseVertex() const
vertex to which collapse
virtual vec3 getAsVec3(size_t vector_index) const =0
Returns a vector from the buffer as a vec3 value.
const T_VectorType * begin() const
Definition: Array.hpp:245
The Geometry class is a Renderable that implements a polygonal mesh made of polygons, lines and points.
Definition: Geometry.hpp:66
Visualization Library main namespace.
bool operator!=(const ref< T1 > &o1, const ref< T2 > &o2)
Definition: Object.hpp:145
ArrayUInt1 ::scalar_type index_type
Simple class to be used as a timer and to retrieve the current time and date.
Definition: Time.hpp:49
See DrawElements.
virtual TriangleIterator triangleIterator() const =0
Returns a TriangleIterator used to iterate through the triangles of a DrawCall.
static void print(const String &message)
Application message for the user.
Definition: Log.cpp:136
A Vertex as defined by PolygonSimplifier.
Iterator used to extract the indices of every single triangle of a DrawCall regardless of the primiti...
int adjacentVerticesCount() const
ajacent vertices
#define NULL
Definition: OpenGLDefs.hpp:81
arr_type * indexBuffer()
The BufferObject containing the indices used to render.
T_VectorType & at(size_t i)
Definition: Array.hpp:255
The quadric error metric as defined by PolygonSimplifier.
The base class of DrawArrays, DrawElements, MultiDrawElements and DrawRangeElements.
Definition: DrawCall.hpp:90
virtual size_t size() const =0
Returns the number of elements of an array.
bool operator==(const ref< T1 > &o1, const ref< T2 > &o2)
Definition: Object.hpp:144
The ref<> class is used to reference-count an Object.
Definition: Object.hpp:55
An array of vl::fvec3.
Definition: Array.hpp:414
#define VL_CHECK(expr)
Definition: checks.hpp:73
Vertex * adjacentVertex(int index) const