1 /* Copyright 2005 Nicholas Bishop
2 *
3 * This file is part of SharpConstruct.
4 *
5 * SharpConstruct is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * SharpConstruct is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with SharpConstruct; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
18
19 #include "Brush.h"
20 #include "Mesh.h"
21 #include "MeshHistory.h"
22 #include "Utilities.h"
23 #include <algorithm>
24 #include <limits>
25
26 #include <iostream>
27
28 using namespace SharpConstruct;
29 using SharpConstruct::Optimized::Point3D;
30
Move(float x,float y,float z)31 void Mesh::Move( float x, float y, float z )
32 {
33 for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
34 {
35 _vertex_locations[ i ].X() += x;
36 _vertex_locations[ i ].Y() += y;
37 _vertex_locations[ i ].Z() += z;
38 }
39
40 _change_operation( false, true );
41
42 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
43 }
44
Resize(float x,float y,float z)45 void Mesh::Resize( float x, float y, float z )
46 {
47 for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
48 {
49 if( x > 0 )
50 _vertex_locations[ i ].X() *= x;
51 else if( x < 0 )
52 _vertex_locations[ i ].X() /= -x;
53 if( y > 0 )
54 _vertex_locations[ i ].Y() *= y;
55 else if( y < 0 )
56 _vertex_locations[ i ].Y() /= -y;
57 if( z > 0 )
58 _vertex_locations[ i ].Z() *= z;
59 else if( z < 0 )
60 _vertex_locations[ i ].Z() /= -z;
61 }
62
63 RecalculateAllNormals();
64 _change_operation( false, true );
65 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
66 }
67
68 /** Smooths the entire mesh.
69 *
70 * Smooths every point in the mesh. Accepts a strength value between zero and
71 * one.
72 **/
Smooth(float strength)73 void Mesh::Smooth( float strength )
74 {
75 Point3D average;
76
77 for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
78 {
79 average = VertexNeighborLocAverage( i );
80
81 _vertex_locations[ i ] += ( average - _vertex_locations[ i ] ) * strength;
82 }
83
84 RecalculateAllNormals();
85 _change_operation( false, true );
86 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
87 }
88
89 /**
90 *
91 **/
Deflate(float v)92 void Mesh::Deflate( float v )
93 {
94 Point3D nloc;
95 for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
96 {
97 _vertex_locations[ i ] += _vertex_normals[ i ] * v;
98 }
99 RecalculateAllNormals();
100 _change_operation( false, true );
101 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
102 }
103
104 /** Normalizes the distances of vertices from the model's center
105 *
106 */
Spherize(float strength)107 void Mesh::Spherize( float strength )
108 {
109 CalculateBoundingSphere();
110
111 const float sub( 1 - strength );
112 for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
113 {
114 Point3D& v( _vertex_locations[ i ] );
115 //const float distance( _center.Distance( _vertex_locations[ i ] ) );
116 Point3D copy( v );
117 Normalize( copy );
118 v = v * sub + copy * strength;
119 }
120
121 RecalculateAllNormals();
122 _change_operation( false, true );
123 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
124 }
125
126 /** Floods the entire mesh with the current color.
127 *
128 * All vertex colors are shifted towards the current color. Accepts an intensity
129 * value between 0 and 1.
130 **/
Flood(const Color & color,const float intensity)131 void Mesh::Flood( const Color& color, const float intensity )
132 {
133 if( intensity == 1 )
134 {
135 for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
136 _vertex_colors[ i ] = color;
137 }
138 else
139 {
140 for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
141 {
142 _vertex_colors[ i ].Red = _vertex_colors[ i ].Red +
143 ( color.Red - _vertex_colors[ i ].Red )
144 * intensity;
145 _vertex_colors[ i ].Green = _vertex_colors[ i ].Green +
146 ( color.Green - _vertex_colors[ i ].Green )
147 * intensity;
148 _vertex_colors[ i ].Blue = _vertex_colors[ i ].Blue +
149 ( color.Blue - _vertex_colors[ i ].Blue )
150 * intensity;
151 }
152 }
153 _change_operation( false, true );
154 MeshHistory::Instance().SignalEntireSectionChanged().emit( false, true, false );
155 }
156
157 struct subtri
158 {
159 unsigned O[ 3 ];
160 unsigned P[ 3 ];
161 };
162 struct subquad
163 {
164 unsigned O[ 4 ];
165 unsigned P[ 4 ];
166 };
167
Subdivide(bool smooth)168 void Mesh::Subdivide( bool smooth )
169 {
170 std::vector< subtri > st( _triangles.size() );
171 unsigned lndx = _vertex_locations.size();
172
173 for( unsigned i = 0; i < _triangles.size(); ++i )
174 {
175 // Copy _triangles data to st
176 for( unsigned j = 0; j <= 2; j++ )
177 st[ i ].O[ j ] = _triangles[ i ].V[ j ];
178
179 // For each edge
180 for( unsigned j = 0; j <= 2; j++ )
181 {
182 int j2 = j + 1;
183 if( j2 > 2 )
184 j2 = 0;
185
186 // Find all polygon users
187 std::map< unsigned, unsigned > tusrs = _triangle_users( st[ i ].O[ j ], st[ i ].O[ j2 ] );
188
189 std::map< unsigned, unsigned >::iterator it;
190 int subndx = -1;
191
192 for( std::map< unsigned, unsigned >::iterator it = tusrs.begin();
193 it != tusrs.end(); it++ )
194 {
195 if( ( *it ).first < i )
196 {
197 it = tusrs.begin();
198 subndx = st[ ( *it ).first ].P[ ( *it ).second - 1 ];
199 break;
200 }
201 }
202
203 // If not found, calculate a new midpoint
204 if( subndx == -1 )
205 {
206 _vertex_locations.resize( _vertex_locations.size() + 1 );
207 _vertex_locations[ lndx ].Midpoint( _vertex_locations[ st[ i ].O[ j ] ],
208 _vertex_locations[ st[ i ].O[ j2 ] ] );
209 _vertex_colors.resize( _vertex_colors.size() + 1 );
210 _vertex_colors[ lndx ] = MixColors( _vertex_colors[ st[ i ].O[ j ] ],
211 _vertex_colors[ st[ i ].O[ j2 ] ] );
212 st[ i ].P[ j ] = lndx++;
213 }
214 else
215 {
216 st[ i ].P[ j ] = subndx;
217 }
218 }
219 }
220
221 std::vector< subquad > sq( _quads.size() );
222 lndx = _vertex_locations.size();
223
224 for( unsigned i = 0; i < _quads.size(); ++i )
225 {
226 // Copy quad data to sq
227 for( unsigned j = 0; j <= 3; j++ )
228 sq[ i ].O[ j ] = _quads[ i ].V[ j ];
229
230 // For each edge
231 for( unsigned j = 0; j <= 3; j++ )
232 {
233 int j2 = j + 1;
234 if( j2 > 3 )
235 j2 = 0;
236
237 // Find all polygon users
238 std::map< unsigned, unsigned > tusrs = _triangle_users( sq[ i ].O[ j ], sq[ i ].O[ j2 ] );
239
240 std::map< unsigned, unsigned >::iterator it;
241 int subndx = -1;
242
243 if( tusrs.size() )
244 {
245 it = tusrs.begin();
246 subndx = st[ ( *it ).first ].P[ ( *it ).second - 1 ];
247 }
248
249 // No connected triangles
250 if( subndx == -1 )
251 {
252 std::map< unsigned, unsigned > qusrs = _quad_users( sq[ i ].O[ j ], sq[ i ].O[ j2 ] );
253 for( it = qusrs.begin(); it != qusrs.end(); it++ )
254 {
255 if( ( *it ).first < i )
256 {
257 subndx = sq[ ( *it ).first ].P[ (int)(( *it ).second) - 1 ];
258 break;
259 }
260 }
261 }
262
263 // If not found, calculate a new midpoint
264 if( subndx == -1 )
265 {
266 _vertex_locations.resize( _vertex_locations.size() + 1 );
267 _vertex_locations[ lndx ].Midpoint( _vertex_locations[ sq[ i ].O[ j ] ],
268 _vertex_locations[ sq[ i ].O[ j2 ] ] );
269 _vertex_colors.resize( _vertex_colors.size() + 1 );
270 _vertex_colors[ lndx ] = MixColors( _vertex_colors[ sq[ i ].O[ j ] ],
271 _vertex_colors[ sq[ i ].O[ j2 ] ] );
272 sq[ i ].P[ j ] = lndx++;
273 }
274 else
275 {
276 sq[ i ].P[ j ] = subndx;
277 }
278 }
279 }
280
281 _triangles.clear();
282 _quads.clear();
283 /* This loop makes the following subdivisional pattern:
284 *
285 * /\ /\
286 * / \ ====\ /__\
287 * / \ ====/ /\ /\
288 * /______\ /__\/__\
289 *
290 * Currently disabled in favor of a quad-producing algorithm.
291 */
292 /*for( unsigned i = 0; i < st.size(); ++i )
293 {
294 _triangles.push_back( Triangle( st[ i ].O[ 0 ], st[ i ].P[ 0 ], st[ i ].P[ 2 ] ) );
295 _triangles.push_back( Triangle( st[ i ].P[ 0 ], st[ i ].O[ 1 ], st[ i ].P[ 1 ] ) );
296 _triangles.push_back( Triangle( st[ i ].P[ 1 ], st[ i ].O[ 2 ], st[ i ].P[ 2 ] ) );
297 _triangles.push_back( Triangle( st[ i ].P[ 0 ], st[ i ].P[ 1 ], st[ i ].P[ 2 ] ) );
298 }*/
299
300 // This loop produces three quads instead of four triangles.
301 for( unsigned i = 0; i < st.size(); ++i )
302 {
303 // Find center
304 Point3D cen( 0, 0, 0 );
305 for( unsigned j = 0; j <= 2; j++ )
306 cen += _vertex_locations[ st[ i ].O[ j ] ];
307 cen /= 3;
308
309 unsigned cndx = _vertex_locations.size();
310 _vertex_locations.push_back( cen );
311 _vertex_colors.push_back( MixColors( _vertex_colors[ st[ i ].O[ 0 ] ],
312 _vertex_colors[ st[ i ].O[ 1 ] ],
313 _vertex_colors[ st[ i ].O[ 2 ] ] ) );
314
315 _quads.push_back( Quad( cndx, st[ i ].P[ 2 ], st[ i ].O[ 0 ], st[ i ].P[ 0 ] ) );
316 _quads.push_back( Quad( cndx, st[ i ].P[ 0 ], st[ i ].O[ 1 ], st[ i ].P[ 1 ] ) );
317 _quads.push_back( Quad( cndx, st[ i ].P[ 1 ], st[ i ].O[ 2 ], st[ i ].P[ 2 ] ) );
318 }
319
320 for( unsigned i = 0; i < sq.size(); ++i )
321 {
322 // Find center
323 Point3D cen( 0, 0, 0 );
324 for( unsigned j = 0; j <= 3; j++ )
325 cen += _vertex_locations[ sq[ i ].O[ j ] ];
326 cen /= 4;
327
328 unsigned cndx = _vertex_locations.size();
329 _vertex_locations.push_back( cen );
330 _vertex_colors.push_back( MixColors( _vertex_colors[ sq[ i ].O[ 0 ] ],
331 _vertex_colors[ sq[ i ].O[ 1 ] ],
332 _vertex_colors[ sq[ i ].O[ 2 ] ],
333 _vertex_colors[ sq[ i ].O[ 3 ] ] ) );
334
335 _quads.push_back( Quad( sq[ i ].O[ 0 ], sq[ i ].P[ 0 ], cndx, sq[ i ].P[ 3 ] ) );
336 _quads.push_back( Quad( sq[ i ].P[ 0 ], sq[ i ].O[ 1 ], sq[ i ].P[ 1 ], cndx ) );
337 _quads.push_back( Quad( sq[ i ].P[ 1 ], sq[ i ].O[ 2 ], sq[ i ].P[ 2 ], cndx ) );
338 _quads.push_back( Quad( sq[ i ].P[ 2 ], sq[ i ].O[ 3 ], sq[ i ].P[ 3 ], cndx ) );
339 }
340
341 // Return mesh data to a consistent state
342
343 _recalculate_vertex_users();
344 _vertex_normals.resize( _vertex_locations.size() );
345 _triangle_normals.resize( _triangles.size() );
346 _quad_normals.resize( _quads.size() );
347 //_recalculate_all_normals();
348 if( smooth )
349 {
350 Optimized::Point3DVector nv( _vertex_locations );
351 for( unsigned i = 0; i < _vertex_locations.size(); ++i )
352 {
353 unsigned count = 0, j;
354
355 nv[ i ] = Point3D( 0, 0, 0 );
356 //nv[ i ] = _vertex_locations[ i ];
357 for( j = 0; j < _vertex_users[ i ].Triangles.size(); j++ )
358 nv[ i ] += _polygon_center( _triangles[ _vertex_users[ i ].Triangles[ j ] ] );
359 count += j;
360
361 for( j = 0; j < _vertex_users[ i ].Quads.size(); j++ )
362 nv[ i ] += _polygon_center( _quads[ _vertex_users[ i ].Quads[ j ] ] );
363 count += j;
364
365 nv[ i ] /= count;
366 }
367 _vertex_locations = nv;
368 }
369
370 _reset_visibles();
371
372 _visible_elements.RestoreOrder.Enabled = false;
373
374 _change_operation( true, true );
375
376 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, true, true );
377 }
378
379 /*void Mesh::Optimize( float amt )
380 {
381 const int orig = _polygon_normals.size();
382 std::vector< std::map< unsigned, float > > dists(
383 _vertex_polygon_indices.size() );
384
385 // Dists has one map for every vertex; the map contains every other vertex
386 // the vertex is connected to (key) and the distance between them as the
387 // value
388 for( unsigned i = 0; i < _vertex_locations.size(); ++i )
389 {
390 std::set< unsigned > cs = _connected_vertices( i );
391 for( std::set< unsigned >::iterator it = cs.begin(); it != cs.end();
392 ++it )
393 {
394 if( *it < i )
395 continue;
396 dists[ i ][ *it ] = _vertex_locations[ i ].Distance(
397 _vertex_locations[ *it ] );
398 }
399 }
400 while( (int)_indices.size() / 3 > orig - amt )
401 {
402 unsigned P[ 0 ] = 0, P[ 1 ] = *_connected_vertices( 0 ).begin();
403 float shortest = _vertex_locations[ P[ 0 ] ].Distance( _vertex_locations[ P[ 1 ] ] );
404
405 for( unsigned i = 1; i < dists.size(); ++i )
406 {
407 for( std::map< unsigned, float >::iterator it = dists[ i ].begin();
408 it != dists[ i ].end(); ++it )
409 {
410 if( ( *it ).second < shortest ||
411 shortest < std::numeric_limits< float >::epsilon() )
412 {
413 shortest = ( *it ).second;
414 P[ 0 ] = i;
415 P[ 1 ] = ( *it ).first;
416 }
417 }
418 }
419
420 std::map< unsigned, unsigned > cn = _polygons_with_vertices( P[ 0 ], P[ 1 ] );
421
422 // Polygons that use P[ 1 ] should use P[ 0 ] instead
423 for( unsigned i = 0; i < _vertex_polygon_indices[ P[ 1 ] ].size(); ++i )
424 {
425 for( unsigned j = 0; j <= 2; j++ )
426 {
427 const unsigned p = _vertex_polygon_indices[ P[ 1 ] ][ i ];
428 if( _indices[ p * 3 + j ] == P[ 1 ] )
429 _indices[ p * 3 + j ] = P[ 0 ];
430 }
431 }
432
433 // Remove polygons that use both P[ 0 ] and P[ 1 ]
434 for( std::map< unsigned, unsigned >::reverse_iterator i = cn.rbegin();
435 i != cn.rend(); ++i )
436 {
437 for( unsigned j = 0; j <= 2; j++ )
438 {
439 const int ndx = _indices[ ( *i ).first * 3 + j ];
440 for( unsigned k = 0; k < _vertex_polygon_indices[ ndx ].size(); k++ )
441 {
442 *//* if( _vertex_polygon_indices[ ndx ][ k ] == ( *i ).first )
443 _vertex_polygon_indices[ ndx ].erase(
444 _vertex_polygon_indices[ ndx ].begin() + k );*//*
445 }
446 }
447 //std::cout << "rm: " << ( *i ).first << std::endl;
448 _indices.erase( _indices.begin() + ( *i ).first * 3,
449 _indices.begin() + ( *i ).first * 3 + 3 );
450 }
451
452 // P[ 0 ] = the midpoint of P[ 0 ] and P[ 1 ]
453 _vertex_locations[ P[ 0 ] ].Midpoint( _vertex_locations[ P[ 0 ] ], _vertex_locations[ P[ 1 ] ] );
454
455 _vertex_polygon_indices[ P[ 1 ] ].clear();
456 _recalculate_vertex_polygon_indices();
457
458 dists[ P[ 0 ] ].clear();
459 dists[ P[ 1 ] ].clear();
460
461 //std::cout << P[ 0 ] << " " << P[ 1 ] << std::endl;
462 }
463
464 _polygon_normals.resize( _indices.size() / 3 );
465 _recalculate_vertex_polygon_indices();
466 RecalculateAllNormals();
467
468 _change_operation();
469 }*/
470
RemoveDuplicates()471 int Mesh::RemoveDuplicates()
472 {
473 return 0;
474 /*unsigned int i, j, k, l, total = 0;
475
476 for( i = 0; i < _vertices.size() - 1; ++i )
477 for( j = i + 1; j < _vertices.size(); j++ )
478 if( _vertices[ i ].Location == _vertices[ j ].Location )
479 {
480 // We've found a duplicate, destroy it
481 _vertices.erase( _vertices.begin() + j );
482
483 for( k = 0; k < _vertex_polygon_indices[ j ].size(); k++ )
484 {
485 // Copy all of the jth's polygons to i's vector
486 _vertex_polygon_indices[ i ].push_back( _vertex_polygon_indices[ j ][ k ] );
487 for( l = 0; l < 3; l++ )
488 if( _indices[ _vertex_polygon_indices[ j ][ k * 3 + l ] ] == j )
489 // Set any index equaling j to i
490 _indices[ _vertex_polygon_indices[ j ][ k * 3 + l ] ] == i;
491 }
492
493 // Destroy the extra vertex_polygon_index
494 _vertex_polygon_indices.erase( _vertex_polygon_indices.begin() + j );
495
496 for( k = 0; k < _indices.size(); k++ )
497 if( _indices[ k ] > j )
498 _indices[ k ]--;
499 total++;
500 j--;
501 }
502
503 _recalculate_all_normals();
504
505 return total;*/
506 }
507
Mirror(bool x,bool y,bool z)508 void Mesh::Mirror( bool x, bool y, bool z )
509 {
510 if( !x && !y && !z )
511 return;
512
513 for( unsigned i = 0; i < _vertex_locations.size(); ++i )
514 {
515 if( x )
516 _vertex_locations[ i ].X() = -_vertex_locations[ i ].X();
517 if( y )
518 _vertex_locations[ i ].Y() = -_vertex_locations[ i ].Y();
519 if( z )
520 _vertex_locations[ i ].Z() = -_vertex_locations[ i ].Z();
521 }
522
523 if( !( ( x && y && !z ) || ( x && z && !y ) || ( y && z && !x ) ) )
524 FlipNormals();
525
526
527 RecalculateAllNormals();
528 _change_operation( false, true );
529 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
530 }
531
FlipNormals()532 void Mesh::FlipNormals()
533 {
534 for( unsigned i = 0; i < _triangles.size(); ++i )
535 _triangles[ i ].ReverseVertices();
536 for( unsigned i = 0; i < _quads.size(); ++i )
537 _quads[ i ].ReverseVertices();
538
539 RecalculateAllNormals();
540 _change_operation( true, true );
541 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, true, true );
542 }
543
Unify()544 void Mesh::Unify()
545 {
546 CalculateBoundingSphere();
547
548 for( unsigned i = 0; i < _vertex_locations.size(); ++i )
549 {
550 _vertex_locations[ i ] -= _center;
551 _vertex_locations[ i ] /= _diameter / 2;
552 }
553 _change_operation( false, true );
554 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
555 }
556
ToTriangles()557 void Mesh::ToTriangles()
558 {
559 const std::string total( ToString( static_cast< float >
560 ( _quads.size() ) ) );
561 for( unsigned i = 0; i < _quads.size(); ++i )
562 {
563 _triangles.push_back( Triangle( _quads[ i ].V[ 0 ],
564 _quads[ i ].V[ 1 ],
565 _quads[ i ].V[ 2 ] ) );
566 _triangles.push_back( Triangle( _quads[ i ].V[ 0 ],
567 _quads[ i ].V[ 2 ],
568 _quads[ i ].V[ 3 ] ) );
569
570 /*Messenger << OutputValue( ( i + 1 ) * 1.0f / _quads.size() )
571 << ( i + 1 ) << " / " << total << OutputFlush();*/
572 }
573 _quads.clear();
574 _quad_normals.clear();
575
576 _reset_visibles();
577
578 _triangle_normals.resize( _triangles.size() );
579 _recalculate_vertex_users();
580 RecalculateAllNormals();
581
582 _visible_elements.RestoreOrder.Enabled = false;
583
584 _change_operation( true, true );
585
586 MeshHistory::Instance().SignalEntireSectionChanged().emit( true, true, true );
587 }
588