1 /*
2 Open Asset Import Library (assimp)
3 ----------------------------------------------------------------------
4
5 Copyright (c) 2006-2021, assimp team
6
7
8 All rights reserved.
9
10 Redistribution and use of this software in source and binary forms,
11 with or without modification, are permitted provided that the
12 following conditions are met:
13
14 * Redistributions of source code must retain the above
15 copyright notice, this list of conditions and the
16 following disclaimer.
17
18 * Redistributions in binary form must reproduce the above
19 copyright notice, this list of conditions and the
20 following disclaimer in the documentation and/or other
21 materials provided with the distribution.
22
23 * Neither the name of the assimp team, nor the names of its
24 contributors may be used to endorse or promote products
25 derived from this software without specific prior
26 written permission of the assimp team.
27
28 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39
40 ----------------------------------------------------------------------
41 */
42
43 /** @file BlenderTessellator.cpp
44 * @brief A simple tessellation wrapper
45 */
46
47
48 #ifndef ASSIMP_BUILD_NO_BLEND_IMPORTER
49
50 #include "BlenderDNA.h"
51 #include "BlenderScene.h"
52 #include "BlenderBMesh.h"
53 #include "BlenderTessellator.h"
54
55 #include <stddef.h>
56
57 static const unsigned int BLEND_TESS_MAGIC = 0x83ed9ac3;
58
59 #if ASSIMP_BLEND_WITH_GLU_TESSELLATE
60
61 namspace Assimp
62 {
63 template< > const char* LogFunctions< BlenderTessellatorGL >::Prefix()
64 {
65 static auto prefix = "BLEND_TESS_GL: ";
66 return prefix;
67 }
68 }
69
70 using namespace Assimp;
71 using namespace Assimp::Blender;
72
73 #ifndef CALLBACK
74 #define CALLBACK
75 #endif
76
77 // ------------------------------------------------------------------------------------------------
BlenderTessellatorGL(BlenderBMeshConverter & converter)78 BlenderTessellatorGL::BlenderTessellatorGL( BlenderBMeshConverter& converter ):
79 converter( &converter )
80 {
81 }
82
83 // ------------------------------------------------------------------------------------------------
~BlenderTessellatorGL()84 BlenderTessellatorGL::~BlenderTessellatorGL( )
85 {
86 }
87
88 // ------------------------------------------------------------------------------------------------
Tessellate(const MLoop * polyLoop,int vertexCount,const std::vector<MVert> & vertices)89 void BlenderTessellatorGL::Tessellate( const MLoop* polyLoop, int vertexCount, const std::vector< MVert >& vertices )
90 {
91 AssertVertexCount( vertexCount );
92
93 std::vector< VertexGL > polyLoopGL;
94 GenerateLoopVerts( polyLoopGL, polyLoop, vertexCount, vertices );
95
96 TessDataGL tessData;
97 Tesssellate( polyLoopGL, tessData );
98
99 TriangulateDrawCalls( tessData );
100 }
101
102 // ------------------------------------------------------------------------------------------------
AssertVertexCount(int vertexCount)103 void BlenderTessellatorGL::AssertVertexCount( int vertexCount )
104 {
105 if ( vertexCount <= 4 )
106 {
107 ThrowException( "Expected more than 4 vertices for tessellation" );
108 }
109 }
110
111 // ------------------------------------------------------------------------------------------------
GenerateLoopVerts(std::vector<VertexGL> & polyLoopGL,const MLoop * polyLoop,int vertexCount,const std::vector<MVert> & vertices)112 void BlenderTessellatorGL::GenerateLoopVerts( std::vector< VertexGL >& polyLoopGL, const MLoop* polyLoop, int vertexCount, const std::vector< MVert >& vertices )
113 {
114 for ( int i = 0; i < vertexCount; ++i )
115 {
116 const MLoop& loopItem = polyLoop[ i ];
117 const MVert& vertex = vertices[ loopItem.v ];
118 polyLoopGL.push_back( VertexGL( vertex.co[ 0 ], vertex.co[ 1 ], vertex.co[ 2 ], loopItem.v, BLEND_TESS_MAGIC ) );
119 }
120 }
121
122 // ------------------------------------------------------------------------------------------------
Tesssellate(std::vector<VertexGL> & polyLoopGL,TessDataGL & tessData)123 void BlenderTessellatorGL::Tesssellate( std::vector< VertexGL >& polyLoopGL, TessDataGL& tessData )
124 {
125 GLUtesselator* tessellator = gluNewTess( );
126 gluTessCallback( tessellator, GLU_TESS_BEGIN_DATA, reinterpret_cast< void ( CALLBACK * )( ) >( TessellateBegin ) );
127 gluTessCallback( tessellator, GLU_TESS_END_DATA, reinterpret_cast< void ( CALLBACK * )( ) >( TessellateEnd ) );
128 gluTessCallback( tessellator, GLU_TESS_VERTEX_DATA, reinterpret_cast< void ( CALLBACK * )( ) >( TessellateVertex ) );
129 gluTessCallback( tessellator, GLU_TESS_COMBINE_DATA, reinterpret_cast< void ( CALLBACK * )( ) >( TessellateCombine ) );
130 gluTessCallback( tessellator, GLU_TESS_EDGE_FLAG_DATA, reinterpret_cast< void ( CALLBACK * )( ) >( TessellateEdgeFlag ) );
131 gluTessCallback( tessellator, GLU_TESS_ERROR_DATA, reinterpret_cast< void ( CALLBACK * )( ) >( TessellateError ) );
132 gluTessProperty( tessellator, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_NONZERO );
133
134 gluTessBeginPolygon( tessellator, &tessData );
135 gluTessBeginContour( tessellator );
136
137 for ( unsigned int i = 0; i < polyLoopGL.size( ); ++i )
138 {
139 gluTessVertex( tessellator, reinterpret_cast< GLdouble* >( &polyLoopGL[ i ] ), &polyLoopGL[ i ] );
140 }
141
142 gluTessEndContour( tessellator );
143 gluTessEndPolygon( tessellator );
144 }
145
146 // ------------------------------------------------------------------------------------------------
TriangulateDrawCalls(const TessDataGL & tessData)147 void BlenderTessellatorGL::TriangulateDrawCalls( const TessDataGL& tessData )
148 {
149 // NOTE - Because we are supplying a callback to GLU_TESS_EDGE_FLAG_DATA we don't technically
150 // need support for GL_TRIANGLE_STRIP and GL_TRIANGLE_FAN but we'll keep it here in case
151 // GLU tessellate changes or tri-strips and fans are wanted.
152 // See: http://www.opengl.org/sdk/docs/man2/xhtml/gluTessCallback.xml
153 for ( unsigned int i = 0; i < tessData.drawCalls.size( ); ++i )
154 {
155 const DrawCallGL& drawCallGL = tessData.drawCalls[ i ];
156 const VertexGL* vertices = &tessData.vertices[ drawCallGL.baseVertex ];
157 if ( drawCallGL.drawMode == GL_TRIANGLES )
158 {
159 MakeFacesFromTris( vertices, drawCallGL.vertexCount );
160 }
161 else if ( drawCallGL.drawMode == GL_TRIANGLE_STRIP )
162 {
163 MakeFacesFromTriStrip( vertices, drawCallGL.vertexCount );
164 }
165 else if ( drawCallGL.drawMode == GL_TRIANGLE_FAN )
166 {
167 MakeFacesFromTriFan( vertices, drawCallGL.vertexCount );
168 }
169 }
170 }
171
172 // ------------------------------------------------------------------------------------------------
MakeFacesFromTris(const VertexGL * vertices,int vertexCount)173 void BlenderTessellatorGL::MakeFacesFromTris( const VertexGL* vertices, int vertexCount )
174 {
175 const int triangleCount = vertexCount / 3;
176 for ( int i = 0; i < triangleCount; ++i )
177 {
178 int vertexBase = i * 3;
179 converter->AddFace( vertices[ vertexBase + 0 ].index, vertices[ vertexBase + 1 ].index, vertices[ vertexBase + 2 ].index );
180 }
181 }
182
183 // ------------------------------------------------------------------------------------------------
MakeFacesFromTriStrip(const VertexGL * vertices,int vertexCount)184 void BlenderTessellatorGL::MakeFacesFromTriStrip( const VertexGL* vertices, int vertexCount )
185 {
186 const int triangleCount = vertexCount - 2;
187 for ( int i = 0; i < triangleCount; ++i )
188 {
189 int vertexBase = i;
190 converter->AddFace( vertices[ vertexBase + 0 ].index, vertices[ vertexBase + 1 ].index, vertices[ vertexBase + 2 ].index );
191 }
192 }
193
194 // ------------------------------------------------------------------------------------------------
MakeFacesFromTriFan(const VertexGL * vertices,int vertexCount)195 void BlenderTessellatorGL::MakeFacesFromTriFan( const VertexGL* vertices, int vertexCount )
196 {
197 const int triangleCount = vertexCount - 2;
198 for ( int i = 0; i < triangleCount; ++i )
199 {
200 int vertexBase = i;
201 converter->AddFace( vertices[ 0 ].index, vertices[ vertexBase + 1 ].index, vertices[ vertexBase + 2 ].index );
202 }
203 }
204
205 // ------------------------------------------------------------------------------------------------
TessellateBegin(GLenum drawModeGL,void * userData)206 void BlenderTessellatorGL::TessellateBegin( GLenum drawModeGL, void* userData )
207 {
208 TessDataGL& tessData = *reinterpret_cast< TessDataGL* >( userData );
209 tessData.drawCalls.push_back( DrawCallGL( drawModeGL, tessData.vertices.size( ) ) );
210 }
211
212 // ------------------------------------------------------------------------------------------------
TessellateEnd(void *)213 void BlenderTessellatorGL::TessellateEnd( void* )
214 {
215 // Do nothing
216 }
217
218 // ------------------------------------------------------------------------------------------------
TessellateVertex(const void * vtxData,void * userData)219 void BlenderTessellatorGL::TessellateVertex( const void* vtxData, void* userData )
220 {
221 TessDataGL& tessData = *reinterpret_cast< TessDataGL* >( userData );
222
223 const VertexGL& vertex = *reinterpret_cast< const VertexGL* >( vtxData );
224 if ( vertex.magic != BLEND_TESS_MAGIC )
225 {
226 ThrowException( "Point returned by GLU Tessellate was probably not one of ours. This indicates we need a new way to store vertex information" );
227 }
228 tessData.vertices.push_back( vertex );
229 if ( tessData.drawCalls.size( ) == 0 )
230 {
231 ThrowException( "\"Vertex\" callback received before \"Begin\"" );
232 }
233 ++( tessData.drawCalls.back( ).vertexCount );
234 }
235
236 // ------------------------------------------------------------------------------------------------
TessellateCombine(const GLdouble intersection[3],const GLdouble * [4],const GLfloat[4],GLdouble ** out,void * userData)237 void BlenderTessellatorGL::TessellateCombine( const GLdouble intersection[ 3 ], const GLdouble* [ 4 ], const GLfloat [ 4 ], GLdouble** out, void* userData )
238 {
239 ThrowException( "Intersected polygon loops are not yet supported" );
240 }
241
242 // ------------------------------------------------------------------------------------------------
TessellateEdgeFlag(GLboolean,void *)243 void BlenderTessellatorGL::TessellateEdgeFlag( GLboolean, void* )
244 {
245 // Do nothing
246 }
247
248 // ------------------------------------------------------------------------------------------------
TessellateError(GLenum errorCode,void *)249 void BlenderTessellatorGL::TessellateError( GLenum errorCode, void* )
250 {
251 ThrowException( reinterpret_cast< const char* >( gluErrorString( errorCode ) ) );
252 }
253
254 #endif // ASSIMP_BLEND_WITH_GLU_TESSELLATE
255
256 #if ASSIMP_BLEND_WITH_POLY_2_TRI
257
258 namespace Assimp
259 {
Prefix()260 template< > const char* LogFunctions< BlenderTessellatorP2T >::Prefix()
261 {
262 static auto prefix = "BLEND_TESS_P2T: ";
263 return prefix;
264 }
265 }
266
267 using namespace Assimp;
268 using namespace Assimp::Blender;
269
270 // ------------------------------------------------------------------------------------------------
BlenderTessellatorP2T(BlenderBMeshConverter & converter)271 BlenderTessellatorP2T::BlenderTessellatorP2T( BlenderBMeshConverter& converter ):
272 converter( &converter )
273 {
274 }
275
276 // ------------------------------------------------------------------------------------------------
~BlenderTessellatorP2T()277 BlenderTessellatorP2T::~BlenderTessellatorP2T( )
278 {
279 }
280
281 // ------------------------------------------------------------------------------------------------
Tessellate(const MLoop * polyLoop,int vertexCount,const std::vector<MVert> & vertices)282 void BlenderTessellatorP2T::Tessellate( const MLoop* polyLoop, int vertexCount, const std::vector< MVert >& vertices )
283 {
284 AssertVertexCount( vertexCount );
285
286 // NOTE - We have to hope that points in a Blender polygon are roughly on the same plane.
287 // There may be some triangulation artifacts if they are wildly different.
288
289 std::vector< PointP2T > points;
290 Copy3DVertices( polyLoop, vertexCount, vertices, points );
291
292 PlaneP2T plane = FindLLSQPlane( points );
293
294 aiMatrix4x4 transform = GeneratePointTransformMatrix( plane );
295
296 TransformAndFlattenVectices( transform, points );
297
298 std::vector< p2t::Point* > pointRefs;
299 ReferencePoints( points, pointRefs );
300
301 p2t::CDT cdt( pointRefs );
302
303 cdt.Triangulate( );
304 std::vector< p2t::Triangle* > triangles = cdt.GetTriangles( );
305
306 MakeFacesFromTriangles( triangles );
307 }
308
309 // ------------------------------------------------------------------------------------------------
AssertVertexCount(int vertexCount)310 void BlenderTessellatorP2T::AssertVertexCount( int vertexCount )
311 {
312 if ( vertexCount <= 4 )
313 {
314 ThrowException( "Expected more than 4 vertices for tessellation" );
315 }
316 }
317
318 // ------------------------------------------------------------------------------------------------
Copy3DVertices(const MLoop * polyLoop,int vertexCount,const std::vector<MVert> & vertices,std::vector<PointP2T> & points) const319 void BlenderTessellatorP2T::Copy3DVertices( const MLoop* polyLoop, int vertexCount, const std::vector< MVert >& vertices, std::vector< PointP2T >& points ) const
320 {
321 points.resize( vertexCount );
322 for ( int i = 0; i < vertexCount; ++i )
323 {
324 const MLoop& loop = polyLoop[ i ];
325 const MVert& vert = vertices[ loop.v ];
326
327 PointP2T& point = points[ i ];
328 point.point3D.Set( vert.co[ 0 ], vert.co[ 1 ], vert.co[ 2 ] );
329 point.index = loop.v;
330 point.magic = BLEND_TESS_MAGIC;
331 }
332 }
333
334 // ------------------------------------------------------------------------------------------------
GeneratePointTransformMatrix(const Blender::PlaneP2T & plane) const335 aiMatrix4x4 BlenderTessellatorP2T::GeneratePointTransformMatrix( const Blender::PlaneP2T& plane ) const
336 {
337 aiVector3D sideA( 1.0f, 0.0f, 0.0f );
338 if ( std::fabs( plane.normal * sideA ) > 0.999f )
339 {
340 sideA = aiVector3D( 0.0f, 1.0f, 0.0f );
341 }
342
343 aiVector3D sideB( plane.normal ^ sideA );
344 sideB.Normalize( );
345 sideA = sideB ^ plane.normal;
346
347 aiMatrix4x4 result;
348 result.a1 = sideA.x;
349 result.a2 = sideA.y;
350 result.a3 = sideA.z;
351 result.b1 = sideB.x;
352 result.b2 = sideB.y;
353 result.b3 = sideB.z;
354 result.c1 = plane.normal.x;
355 result.c2 = plane.normal.y;
356 result.c3 = plane.normal.z;
357 result.a4 = plane.centre.x;
358 result.b4 = plane.centre.y;
359 result.c4 = plane.centre.z;
360 result.Inverse( );
361
362 return result;
363 }
364
365 // ------------------------------------------------------------------------------------------------
TransformAndFlattenVectices(const aiMatrix4x4 & transform,std::vector<Blender::PointP2T> & vertices) const366 void BlenderTessellatorP2T::TransformAndFlattenVectices( const aiMatrix4x4& transform, std::vector< Blender::PointP2T >& vertices ) const
367 {
368 for ( size_t i = 0; i < vertices.size( ); ++i )
369 {
370 PointP2T& point = vertices[ i ];
371 point.point3D = transform * point.point3D;
372 point.point2D.set( point.point3D.y, point.point3D.z );
373 }
374 }
375
376 // ------------------------------------------------------------------------------------------------
ReferencePoints(std::vector<Blender::PointP2T> & points,std::vector<p2t::Point * > & pointRefs) const377 void BlenderTessellatorP2T::ReferencePoints( std::vector< Blender::PointP2T >& points, std::vector< p2t::Point* >& pointRefs ) const
378 {
379 pointRefs.resize( points.size( ) );
380 for ( size_t i = 0; i < points.size( ); ++i )
381 {
382 pointRefs[ i ] = &points[ i ].point2D;
383 }
384 }
385
386 // ------------------------------------------------------------------------------------------------
GetActualPointStructure(p2t::Point & point) const387 inline PointP2T& BlenderTessellatorP2T::GetActualPointStructure( p2t::Point& point ) const
388 {
389 #if defined __clang__
390 # pragma clang diagnostic push
391 # pragma clang diagnostic ignored "-Winvalid-offsetof"
392 #endif // __clang__
393 unsigned int pointOffset = offsetof( PointP2T, point2D );
394 #if defined __clang__
395 # pragma clang diagnostic pop
396 #endif
397 PointP2T& pointStruct = *reinterpret_cast< PointP2T* >( reinterpret_cast< char* >( &point ) - pointOffset );
398 if ( pointStruct.magic != static_cast<int>( BLEND_TESS_MAGIC ) )
399 {
400 ThrowException( "Point returned by poly2tri was probably not one of ours. This indicates we need a new way to store vertex information" );
401 }
402 return pointStruct;
403 }
404 // ------------------------------------------------------------------------------------------------
MakeFacesFromTriangles(std::vector<p2t::Triangle * > & triangles) const405 void BlenderTessellatorP2T::MakeFacesFromTriangles( std::vector< p2t::Triangle* >& triangles ) const
406 {
407 for ( size_t i = 0; i < triangles.size( ); ++i )
408 {
409 p2t::Triangle& Triangle = *triangles[ i ];
410
411 PointP2T& pointA = GetActualPointStructure( *Triangle.GetPoint( 0 ) );
412 PointP2T& pointB = GetActualPointStructure( *Triangle.GetPoint( 1 ) );
413 PointP2T& pointC = GetActualPointStructure( *Triangle.GetPoint( 2 ) );
414
415 converter->AddFace( pointA.index, pointB.index, pointC.index );
416 }
417 }
418
419 // ------------------------------------------------------------------------------------------------
p2tMax(float a,float b)420 inline float p2tMax( float a, float b )
421 {
422 return a > b ? a : b;
423 }
424
425 // ------------------------------------------------------------------------------------------------
426 // Adapted from: http://missingbytes.blogspot.co.uk/2012/06/fitting-plane-to-point-cloud.html
FindLargestMatrixElem(const aiMatrix3x3 & mtx) const427 float BlenderTessellatorP2T::FindLargestMatrixElem( const aiMatrix3x3& mtx ) const
428 {
429 float result = 0.0f;
430
431 for ( unsigned int x = 0; x < 3; ++x )
432 {
433 for ( unsigned int y = 0; y < 3; ++y )
434 {
435 result = p2tMax( std::fabs( mtx[ x ][ y ] ), result );
436 }
437 }
438
439 return result;
440 }
441
442 // ------------------------------------------------------------------------------------------------
443 // Apparently Assimp doesn't have matrix scaling
ScaleMatrix(const aiMatrix3x3 & mtx,float scale) const444 aiMatrix3x3 BlenderTessellatorP2T::ScaleMatrix( const aiMatrix3x3& mtx, float scale ) const
445 {
446 aiMatrix3x3 result;
447
448 for ( unsigned int x = 0; x < 3; ++x )
449 {
450 for ( unsigned int y = 0; y < 3; ++y )
451 {
452 result[ x ][ y ] = mtx[ x ][ y ] * scale;
453 }
454 }
455
456 return result;
457 }
458
459
460 // ------------------------------------------------------------------------------------------------
461 // Adapted from: http://missingbytes.blogspot.co.uk/2012/06/fitting-plane-to-point-cloud.html
GetEigenVectorFromLargestEigenValue(const aiMatrix3x3 & mtx) const462 aiVector3D BlenderTessellatorP2T::GetEigenVectorFromLargestEigenValue( const aiMatrix3x3& mtx ) const
463 {
464 const float scale = FindLargestMatrixElem( mtx );
465 aiMatrix3x3 mc = ScaleMatrix( mtx, 1.0f / scale );
466 mc = mc * mc * mc;
467
468 aiVector3D v( 1.0f );
469 aiVector3D lastV = v;
470 for ( int i = 0; i < 100; ++i )
471 {
472 v = mc * v;
473 v.Normalize( );
474 if ( ( v - lastV ).SquareLength( ) < 1e-16f )
475 {
476 break;
477 }
478 lastV = v;
479 }
480 return v;
481 }
482
483 // ------------------------------------------------------------------------------------------------
484 // Adapted from: http://missingbytes.blogspot.co.uk/2012/06/fitting-plane-to-point-cloud.html
FindLLSQPlane(const std::vector<PointP2T> & points) const485 PlaneP2T BlenderTessellatorP2T::FindLLSQPlane( const std::vector< PointP2T >& points ) const
486 {
487 PlaneP2T result;
488
489 aiVector3D sum( 0.0 );
490 for ( size_t i = 0; i < points.size( ); ++i )
491 {
492 sum += points[ i ].point3D;
493 }
494 result.centre = sum * (ai_real)( 1.0 / points.size( ) );
495
496 ai_real sumXX = 0.0;
497 ai_real sumXY = 0.0;
498 ai_real sumXZ = 0.0;
499 ai_real sumYY = 0.0;
500 ai_real sumYZ = 0.0;
501 ai_real sumZZ = 0.0;
502 for ( size_t i = 0; i < points.size( ); ++i )
503 {
504 aiVector3D offset = points[ i ].point3D - result.centre;
505 sumXX += offset.x * offset.x;
506 sumXY += offset.x * offset.y;
507 sumXZ += offset.x * offset.z;
508 sumYY += offset.y * offset.y;
509 sumYZ += offset.y * offset.z;
510 sumZZ += offset.z * offset.z;
511 }
512
513 aiMatrix3x3 mtx( sumXX, sumXY, sumXZ, sumXY, sumYY, sumYZ, sumXZ, sumYZ, sumZZ );
514
515 const ai_real det = mtx.Determinant( );
516 if ( det == 0.0f )
517 {
518 result.normal = aiVector3D( 0.0f );
519 }
520 else
521 {
522 aiMatrix3x3 invMtx = mtx;
523 invMtx.Inverse( );
524 result.normal = GetEigenVectorFromLargestEigenValue( invMtx );
525 }
526
527 return result;
528 }
529
530 #endif // ASSIMP_BLEND_WITH_POLY_2_TRI
531
532 #endif // ASSIMP_BUILD_NO_BLEND_IMPORTER
533