1/*
2Open Asset Import Library (assimp)
3----------------------------------------------------------------------
4
5Copyright (c) 2006-2019, assimp team
6
7
8All rights reserved.
9
10Redistribution and use of this software in source and binary forms,
11with or without modification, are permitted provided that the
12following 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
28THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38OF 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
57static const unsigned int BLEND_TESS_MAGIC = 0x83ed9ac3;
58
59#if ASSIMP_BLEND_WITH_GLU_TESSELLATE
60
61namspace Assimp
62{
63 template< > const char* LogFunctions< BlenderTessellatorGL >::Prefix()
64 {
65 static auto prefix = "BLEND_TESS_GL: ";
66 return prefix;
67 }
68}
69
70using namespace Assimp;
71using namespace Assimp::Blender;
72
73#ifndef CALLBACK
74#define CALLBACK
75#endif
76
77// ------------------------------------------------------------------------------------------------
78BlenderTessellatorGL::BlenderTessellatorGL( BlenderBMeshConverter& converter ):
79 converter( &converter )
80{
81}
82
83// ------------------------------------------------------------------------------------------------
84BlenderTessellatorGL::~BlenderTessellatorGL( )
85{
86}
87
88// ------------------------------------------------------------------------------------------------
89void 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// ------------------------------------------------------------------------------------------------
103void BlenderTessellatorGL::AssertVertexCount( int vertexCount )
104{
105 if ( vertexCount <= 4 )
106 {
107 ThrowException( "Expected more than 4 vertices for tessellation" );
108 }
109}
110
111// ------------------------------------------------------------------------------------------------
112void 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// ------------------------------------------------------------------------------------------------
123void 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// ------------------------------------------------------------------------------------------------
147void 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// ------------------------------------------------------------------------------------------------
173void 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// ------------------------------------------------------------------------------------------------
184void 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// ------------------------------------------------------------------------------------------------
195void 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// ------------------------------------------------------------------------------------------------
206void 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// ------------------------------------------------------------------------------------------------
213void BlenderTessellatorGL::TessellateEnd( void* )
214{
215 // Do nothing
216}
217
218// ------------------------------------------------------------------------------------------------
219void 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// ------------------------------------------------------------------------------------------------
237void 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// ------------------------------------------------------------------------------------------------
243void BlenderTessellatorGL::TessellateEdgeFlag( GLboolean, void* )
244{
245 // Do nothing
246}
247
248// ------------------------------------------------------------------------------------------------
249void 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
258namespace Assimp
259{
260 template< > const char* LogFunctions< BlenderTessellatorP2T >::Prefix()
261 {
262 static auto prefix = "BLEND_TESS_P2T: ";
263 return prefix;
264 }
265}
266
267using namespace Assimp;
268using namespace Assimp::Blender;
269
270// ------------------------------------------------------------------------------------------------
271BlenderTessellatorP2T::BlenderTessellatorP2T( BlenderBMeshConverter& converter ):
272 converter( &converter )
273{
274}
275
276// ------------------------------------------------------------------------------------------------
277BlenderTessellatorP2T::~BlenderTessellatorP2T( )
278{
279}
280
281// ------------------------------------------------------------------------------------------------
282void 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, targetVertices&: points );
291
292 PlaneP2T plane = FindLLSQPlane( points );
293
294 aiMatrix4x4 transform = GeneratePointTransformMatrix( plane );
295
296 TransformAndFlattenVectices( transform, vertices&: 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// ------------------------------------------------------------------------------------------------
310void BlenderTessellatorP2T::AssertVertexCount( int vertexCount )
311{
312 if ( vertexCount <= 4 )
313 {
314 ThrowException( msg: "Expected more than 4 vertices for tessellation" );
315 }
316}
317
318// ------------------------------------------------------------------------------------------------
319void BlenderTessellatorP2T::Copy3DVertices( const MLoop* polyLoop, int vertexCount, const std::vector< MVert >& vertices, std::vector< PointP2T >& points ) const
320{
321 points.resize( new_size: 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( pX: vert.co[ 0 ], pY: vert.co[ 1 ], pZ: vert.co[ 2 ] );
329 point.index = loop.v;
330 point.magic = BLEND_TESS_MAGIC;
331 }
332}
333
334// ------------------------------------------------------------------------------------------------
335aiMatrix4x4 BlenderTessellatorP2T::GeneratePointTransformMatrix( const Blender::PlaneP2T& plane ) const
336{
337 aiVector3D sideA( 1.0f, 0.0f, 0.0f );
338 if ( std::fabs( x: 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// ------------------------------------------------------------------------------------------------
366void 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( x_: point.point3D.y, y_: point.point3D.z );
373 }
374}
375
376// ------------------------------------------------------------------------------------------------
377void BlenderTessellatorP2T::ReferencePoints( std::vector< Blender::PointP2T >& points, std::vector< p2t::Point* >& pointRefs ) const
378{
379 pointRefs.resize( new_size: points.size( ) );
380 for ( size_t i = 0; i < points.size( ); ++i )
381 {
382 pointRefs[ i ] = &points[ i ].point2D;
383 }
384}
385
386// ------------------------------------------------------------------------------------------------
387inline PointP2T& BlenderTessellatorP2T::GetActualPointStructure( p2t::Point& point ) const
388{
389 unsigned int pointOffset = offsetof( PointP2T, point2D );
390 PointP2T& pointStruct = *reinterpret_cast< PointP2T* >( reinterpret_cast< char* >( &point ) - pointOffset );
391 if ( pointStruct.magic != static_cast<int>( BLEND_TESS_MAGIC ) )
392 {
393 ThrowException( msg: "Point returned by poly2tri was probably not one of ours. This indicates we need a new way to store vertex information" );
394 }
395 return pointStruct;
396}
397
398// ------------------------------------------------------------------------------------------------
399void BlenderTessellatorP2T::MakeFacesFromTriangles( std::vector< p2t::Triangle* >& triangles ) const
400{
401 for ( size_t i = 0; i < triangles.size( ); ++i )
402 {
403 p2t::Triangle& Triangle = *triangles[ i ];
404
405 PointP2T& pointA = GetActualPointStructure( point&: *Triangle.GetPoint( index: 0 ) );
406 PointP2T& pointB = GetActualPointStructure( point&: *Triangle.GetPoint( index: 1 ) );
407 PointP2T& pointC = GetActualPointStructure( point&: *Triangle.GetPoint( index: 2 ) );
408
409 converter->AddFace( v1: pointA.index, v2: pointB.index, v3: pointC.index );
410 }
411}
412
413// ------------------------------------------------------------------------------------------------
414inline float p2tMax( float a, float b )
415{
416 return a > b ? a : b;
417}
418
419// ------------------------------------------------------------------------------------------------
420// Adapted from: http://missingbytes.blogspot.co.uk/2012/06/fitting-plane-to-point-cloud.html
421float BlenderTessellatorP2T::FindLargestMatrixElem( const aiMatrix3x3& mtx ) const
422{
423 float result = 0.0f;
424
425 for ( unsigned int x = 0; x < 3; ++x )
426 {
427 for ( unsigned int y = 0; y < 3; ++y )
428 {
429 result = p2tMax( a: std::fabs( x: mtx[ x ][ y ] ), b: result );
430 }
431 }
432
433 return result;
434}
435
436// ------------------------------------------------------------------------------------------------
437// Apparently Assimp doesn't have matrix scaling
438aiMatrix3x3 BlenderTessellatorP2T::ScaleMatrix( const aiMatrix3x3& mtx, float scale ) const
439{
440 aiMatrix3x3 result;
441
442 for ( unsigned int x = 0; x < 3; ++x )
443 {
444 for ( unsigned int y = 0; y < 3; ++y )
445 {
446 result[ x ][ y ] = mtx[ x ][ y ] * scale;
447 }
448 }
449
450 return result;
451}
452
453
454// ------------------------------------------------------------------------------------------------
455// Adapted from: http://missingbytes.blogspot.co.uk/2012/06/fitting-plane-to-point-cloud.html
456aiVector3D BlenderTessellatorP2T::GetEigenVectorFromLargestEigenValue( const aiMatrix3x3& mtx ) const
457{
458 const float scale = FindLargestMatrixElem( mtx );
459 aiMatrix3x3 mc = ScaleMatrix( mtx, scale: 1.0f / scale );
460 mc = mc * mc * mc;
461
462 aiVector3D v( 1.0f );
463 aiVector3D lastV = v;
464 for ( int i = 0; i < 100; ++i )
465 {
466 v = mc * v;
467 v.Normalize( );
468 if ( ( v - lastV ).SquareLength( ) < 1e-16f )
469 {
470 break;
471 }
472 lastV = v;
473 }
474 return v;
475}
476
477// ------------------------------------------------------------------------------------------------
478// Adapted from: http://missingbytes.blogspot.co.uk/2012/06/fitting-plane-to-point-cloud.html
479PlaneP2T BlenderTessellatorP2T::FindLLSQPlane( const std::vector< PointP2T >& points ) const
480{
481 PlaneP2T result;
482
483 aiVector3D sum( 0.0 );
484 for ( size_t i = 0; i < points.size( ); ++i )
485 {
486 sum += points[ i ].point3D;
487 }
488 result.centre = sum * (ai_real)( 1.0 / points.size( ) );
489
490 ai_real sumXX = 0.0;
491 ai_real sumXY = 0.0;
492 ai_real sumXZ = 0.0;
493 ai_real sumYY = 0.0;
494 ai_real sumYZ = 0.0;
495 ai_real sumZZ = 0.0;
496 for ( size_t i = 0; i < points.size( ); ++i )
497 {
498 aiVector3D offset = points[ i ].point3D - result.centre;
499 sumXX += offset.x * offset.x;
500 sumXY += offset.x * offset.y;
501 sumXZ += offset.x * offset.z;
502 sumYY += offset.y * offset.y;
503 sumYZ += offset.y * offset.z;
504 sumZZ += offset.z * offset.z;
505 }
506
507 aiMatrix3x3 mtx( sumXX, sumXY, sumXZ, sumXY, sumYY, sumYZ, sumXZ, sumYZ, sumZZ );
508
509 const ai_real det = mtx.Determinant( );
510 if ( det == 0.0f )
511 {
512 result.normal = aiVector3D( 0.0f );
513 }
514 else
515 {
516 aiMatrix3x3 invMtx = mtx;
517 invMtx.Inverse( );
518 result.normal = GetEigenVectorFromLargestEigenValue( mtx: invMtx );
519 }
520
521 return result;
522}
523
524#endif // ASSIMP_BLEND_WITH_POLY_2_TRI
525
526#endif // ASSIMP_BUILD_NO_BLEND_IMPORTER
527

source code of qt3d/src/3rdparty/assimp/src/code/Blender/BlenderTessellator.cpp