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