Visualization Library 2.0.0-b3

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

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
AdjacencyExtractor.hpp
Go to the documentation of this file.
1 /**************************************************************************************/
2 /* */
3 /* Visualization Library */
4 /* http://visualizationlibrary.org */
5 /* */
6 /* Copyright (c) 2005-2017, 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 
32 #ifndef AdjacencyExtractor_INCLUDE_ONCE
33 #define AdjacencyExtractor_INCLUDE_ONCE
34 
36 #include <vlGraphics/Geometry.hpp>
37 #include <vlCore/Time.hpp>
38 
39 namespace vl
40 {
42  private:
43  struct SEdge {
44  u32 A,B,O;
45 
46  SEdge() {
47  A = B = O = 0xFFFFFFFF;
48  }
49 
50  SEdge(u32 a, u32 b, u32 o) {
51  A = a;
52  B = b;
53  O = o;
54  }
55 
56  bool isNull() const {
57  return A == 0xFFFFFFFF;
58  }
59 
60  u64 id() const {
61  return (u64)A | ( (u64)B << 32 );
62  }
63 
64  u64 other() const {
65  return (u64)B | ( (u64)A << 32 );
66  }
67 
68  bool operator<( const SEdge& other ) const {
69  return id() < other.id();
70  }
71 
72  bool operator==( const SEdge& other ) const {
73  return id() == other.id();
74  }
75  };
76 
77  struct STriangle {
78  SEdge edge[3];
79  STriangle( u32 a, u32 b, u32 c ) {
80  edge[0] = SEdge(a,b,c);
81  edge[1] = SEdge(b,c,a);
82  edge[2] = SEdge(c,a,b);
83  }
84  };
85 
87  static const int VL_SEdgeMap_SLOTS = 4;
88 
89  struct SEdgeMapSlots {
90  SEdge slot[ VL_SEdgeMap_SLOTS ];
91  };
92 
94  struct SEdgeMap {
95  std::map<u64, SEdge> edge_map;
96  std::vector<SEdgeMapSlots> cache;
97  int cache_hits;
98  int edge_count;
99 
100  size_t memoryUsed() const {
101  return cache.size() * sizeof( SEdgeMapSlots ) + edge_map.size() * ( sizeof( SEdge ) + sizeof( u64 ) );
102  }
103 
104  SEdgeMap( int size = 104729 ) {
105  cache.resize( size );
106  cache_hits = 0;
107  edge_count = 0;
108  }
109 
110  void put(u64 uid, const SEdge& edge) {
111  ++edge_count;
112  VL_CHECK( ! edge.isNull() );
113  u64 p = uid % cache.size();
114  for( int i = 0; i < VL_SEdgeMap_SLOTS; ++i ) {
115  if ( cache[ p ].slot[ i ].isNull() ) {
116  cache[ p ].slot[ i ] = edge;
117  VL_CHECK( ! cache[ p ].slot[ i ].isNull() );
118  ++cache_hits;
119  return;
120  }
121  }
122  edge_map[ uid ] = edge;
123  }
124 
125  bool get(u64 uid, SEdge& edge_out) {
126  edge_out = SEdge();
127  VL_CHECK( edge_out.isNull() );
128  u64 p = uid % cache.size();
129  for( int i = 0; i < VL_SEdgeMap_SLOTS; ++i ) {
130  if ( ! cache[ p ].slot[ i ].isNull() && cache[ p ].slot[ i ].id() == uid ) {
131  edge_out = cache[ p ].slot[ i ];
132  return true;
133  }
134  }
135 
136  std::map<u64, SEdge>::iterator it = edge_map.find( uid );
137  if ( it != edge_map.end() ) {
138  edge_out = it->second;
139  return true;
140  } else {
141  return false;
142  }
143  }
144  };
145 
153  class SEdgeMapFast {
154  struct SEdgeSlot {
155  SEdge edge;
156  SEdgeSlot* next;
157  SEdgeSlot() {
158  next = NULL;
159  }
160  };
161 
162  private:
163  std::vector<SEdgeSlot> cache;
164  std::vector<SEdgeSlot> free_slots;
165  SEdgeSlot* free_slots_head;
166 
167  public:
168  int cache_hits;
169  int edge_count;
170  int free_slots_used;
171  int max_size;
172 
173  public:
175  SEdgeMapFast( int size = 104729 ) {
176  max_size = size;
177  cache_hits = 0;
178  edge_count = 0;
179  free_slots_used = 0;
180  cache.resize( size );
181  free_slots.resize( size );
182  free_slots_head = &free_slots[0];
183  for( int i = 0; i < free_slots.size() - 1; ++i ) {
184  free_slots[i].next = &free_slots[i + 1];
185  }
186  }
187 
188  size_t memoryUsed() const {
189  return cache.size() * sizeof( SEdgeSlot ) + free_slots.size() * sizeof( SEdgeSlot );
190  }
191 
192  void put(u64 uid, const SEdge& edge) {
193  ++edge_count;
194  u64 p = uid % cache.size();
195 
196  // Find and replace
197  SEdgeSlot* slot = &cache[ p ];
198  SEdgeSlot* last = NULL;
199  for( ; slot != NULL; last = slot, slot = slot->next )
200  {
201  // first is free or found the edge
202  if( slot->edge.isNull() || slot->edge.id() == edge.id() ) {
203  slot->edge = edge;
204  if ( last == NULL) {
205  ++cache_hits;
206  }
207  return;
208  }
209  }
210 
211  // Out of memory: increase SEdgeMapFast size when constructing it.
212  VL_CHECK( free_slots_head );
213 
214  // Get a free slot and append it to the end of the list
215  SEdgeSlot* free_slot = free_slots_head;
216  free_slots_head = free_slots_head->next;
217  free_slot->next = NULL;
218  free_slot->edge = edge;
219  last->next = free_slot;
220  ++free_slots_used;
221  }
222 
223  bool get(u64 uid, SEdge& edge_out) {
224  edge_out = SEdge();
225  u64 p = uid % cache.size();
226  // find
227  for( SEdgeSlot* slot = &cache[ p ]; slot != NULL; slot = slot->next ) {
228  if ( ! slot->edge.isNull() && slot->edge.id() == uid ) {
229  edge_out = slot->edge;
230  return true;
231  }
232  }
233  return false;
234  }
235  };
236 
237  public:
238  static ref< Geometry > extract( Geometry* geom ) {
239 
240  #ifndef NDEBUG
241  float t0 = Time::currentTime();
242  #endif
243 
244  ref< Geometry > geom_adj = new Geometry;
245  geom_adj->setVertexArray( geom->vertexArray() );
246  geom_adj->setNormalArray( geom->normalArray() );
247 
248  int total_triangles = 0;
249  for( int idc = 0; idc < geom->drawCalls().size(); ++idc ) {
250  int triangle_count = 0;
251  const DrawCall* dc = geom->drawCalls()[ idc ].get();
252  int indices = dc->countIndices();
253  SEdgeMapFast edge_map( indices );
254  // SEdgeMap edge_map( indices * 2 );
255 
256  if ( dc->primitiveType() == vl::PT_LINES_ADJACENCY ||
260  Log::error( "AdjacencyExtractor::extract(): geometry has already adjacency information." );
261  return NULL;
262  }
263 
264  for( TriangleIterator trit = dc->triangleIterator(); trit.hasNext(); trit.next() )
265  {
266  u32 a = trit.a();
267  u32 b = trit.b();
268  u32 c = trit.c();
269  STriangle triangle( a, b, c );
270  edge_map.put( triangle.edge[0].id(), triangle.edge[0] );
271  edge_map.put( triangle.edge[1].id(), triangle.edge[1] );
272  edge_map.put( triangle.edge[2].id(), triangle.edge[2] );
273  ++triangle_count;
274  }
275  total_triangles += triangle_count;
276 
278  geom_adj->drawCalls().push_back( dc_adj.get() );
279  dc_adj->indexBuffer()->resize( triangle_count * 6 );
280  GLuint* P = dc_adj->indexBuffer()->begin();
281 
282  for( TriangleIterator trit = dc->triangleIterator(); trit.hasNext(); trit.next(), P += 6 )
283  {
284  u32 a = trit.a();
285  u32 b = trit.b();
286  u32 c = trit.c();
287 
288  // NOTE: degenerate edges are important for border detection.
289 
290  P[0] = a;
291  P[1] = a; // degenerate
292  P[2] = b;
293  P[3] = b; // degenerate
294  P[4] = c;
295  P[5] = c; // degenerate
296 
297  STriangle triangle( a, b, c );
298  SEdge edge;
299  if ( edge_map.get( triangle.edge[0].other(), edge ) ) {
300  VL_CHECK( ! edge.isNull() );
301  P[1] = edge.O;
302  }
303  if ( edge_map.get( triangle.edge[1].other(), edge ) ) {
304  VL_CHECK( ! edge.isNull() );
305  P[3] = edge.O;
306  }
307  if ( edge_map.get( triangle.edge[2].other(), edge ) ) {
308  VL_CHECK( ! edge.isNull() );
309  P[5] = edge.O;
310  }
311  }
312 
313  #ifndef NDEBUG
314  printf("EdgeMap: edge-count: %d, cache-hits: %d (%.1f%%), cache MB: %.1f\n",
315  edge_map.edge_count, edge_map.cache_hits, 100.0f * edge_map.cache_hits / edge_map.edge_count,
316  edge_map.memoryUsed() / (1024.0 * 1024.0) );
317  #endif
318  }
319 
320  #ifndef NDEBUG
321  float secs = Time::currentTime() - t0;
322  printf( "Adjacency Time: %.1fs, %.1fKtri/sec (%d)\n", secs, total_triangles / secs / 1000.0f, total_triangles );
323  #endif
324 
325  return geom_adj;
326  }
327  };
328 }
329 
330 #endif
bool hasNext()
Returns false if the iterator has reached the end of the triangle list.
unsigned long long u64
64 bits unsigned integer
Definition: std_types.hpp:55
const T * get() const
Definition: Object.hpp:128
const ArrayAbstract * vertexArray() const
Conventional vertex array.
Definition: Geometry.hpp:248
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:164
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.
See DrawElements.
virtual TriangleIterator triangleIterator() const =0
Returns a TriangleIterator used to iterate through the triangles of a DrawCall.
unsigned int u32
32 bits unsigned integer
Definition: std_types.hpp:51
Iterator used to extract the indices of every single triangle of a DrawCall regardless of the primiti...
#define NULL
Definition: OpenGLDefs.hpp:81
u32 countIndices() const
Counts the number of virtual indices of a DrawCall., i.e.
Definition: DrawCall.hpp:142
static ref< Geometry > extract(Geometry *geom)
The base class of DrawArrays, DrawElements, MultiDrawElements and DrawRangeElements.
Definition: DrawCall.hpp:90
static real currentTime()
Seconds passed from an arbitrary origin QueryPerformanceFrequency should be called only once in the a...
Definition: Time.cpp:114
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
EPrimitiveType primitiveType() const
Returns the draw call&#39;s primitive type.
Definition: DrawCall.hpp:110
#define VL_CHECK(expr)
Definition: checks.hpp:73
const ArrayAbstract * normalArray() const
Conventional normal array.
Definition: Geometry.hpp:254
Collection< DrawCall > & drawCalls()
Returns the list of DrawCall objects bound to a Geometry.
Definition: Geometry.hpp:102