1 /* NAME:
2 E3GeometryTriMeshOptimize.cpp
3
4 DESCRIPTION:
5 Functions to optimize a TriMesh for use by the interactive renderer.
6
7 COPYRIGHT:
8 Copyright (c) 2005, Quesa Developers. All rights reserved.
9
10 For the current release of Quesa, please see:
11
12 <http://www.quesa.org/>
13
14 Redistribution and use in source and binary forms, with or without
15 modification, are permitted provided that the following conditions
16 are met:
17
18 o Redistributions of source code must retain the above copyright
19 notice, this list of conditions and the following disclaimer.
20
21 o Redistributions in binary form must reproduce the above
22 copyright notice, this list of conditions and the following
23 disclaimer in the documentation and/or other materials provided
24 with the distribution.
25
26 o Neither the name of Quesa nor the names of its contributors
27 may be used to endorse or promote products derived from this
28 software without specific prior written permission.
29
30 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
36 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
37 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
38 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
39 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
40 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 ___________________________________________________________________________
42 */
43 #include "E3GeometryTriMeshOptimize.h"
44
45 #include "E3Memory.h"
46 #include "E3Utils.h"
47 #include "E3Set.h"
48 #include "E3ClassTree.h"
49 #include "QuesaMath.h"
50
51 #include <vector>
52 #include <algorithm>
53
54 #define EQ3ThrowIfMemFail_( x ) do { if ( (x) == NULL ) { \
55 throw std::bad_alloc(); \
56 } } while (false)
57
58 #define EQ3ThrowIf_( x ) do { if ( (x) ) { \
59 throw std::exception(); \
60 } } while (false)
61
62 namespace
63 {
64 const float kDegenerateLengthSquared = 1.0e-12f;
65
66 typedef std::vector< TQ3Vector3D > VecVec;
67
68 typedef std::vector< TQ3Int32 > IntVec;
69
70 class TriMeshOptimizer
71 {
72 public:
73 TriMeshOptimizer(
74 const TQ3TriMeshData& inData,
75 TQ3TriMeshData& outData );
76
77 TQ3Boolean Optimize();
78
79 private:
80 void FindOrigAtts();
81 TQ3Boolean IsOptNeeded() const;
82 void EnsureFaceNormals();
83 void MakeInstanceToPoint();
84 void FindBackLinks();
85 bool ArePointsSimilar( TQ3Int32 inPt1, TQ3Int32 inPt2 );
86 TQ3Int32 FindPrevSimilarPoint( TQ3Int32 inPtInstanceIndex );
87 void FindDictinctVertices();
88 void BuildNewTriMesh();
89 void BuildFaces();
90 void BuildFaceAttributes();
91 void BuildEdges();
92 void BuildEdgeAttributes();
93 void BuildPoints();
94 void BuildVertexAttributes();
95 void ComputeBounds();
96
97 const TQ3TriMeshData& mOrigData;
98 TQ3TriMeshData& mResultData;
99
100 const TQ3Vector3D* mOrigFaceNormals;
101 const TQ3Vector3D* mOrigVertexNormals;
102 const TQ3ColorRGB* mOrigFaceColor;
103 const TQ3ColorRGB* mOrigVertexColor;
104 const TQ3ColorRGB* mOrigFaceTransparency;
105 const TQ3ColorRGB* mOrigVertexTransparency;
106 const TQ3ColorRGB* mOrigFaceSpecularColor;
107 const TQ3ColorRGB* mOrigVertexSpecularColor;
108
109 VecVec mComputedFaceNormals;
110 const TQ3Vector3D* mResultFaceNormals;
111 IntVec mInstanceToPoint;
112 IntVec mPrevPointInstance;
113 IntVec mInstanceToVertex;
114 IntVec mVertexToPoint;
115 IntVec mVertexToFace;
116 IntVec mPointToVertex;
117 };
118 }
119
TriMeshOptimizer(const TQ3TriMeshData & inData,TQ3TriMeshData & outData)120 TriMeshOptimizer::TriMeshOptimizer(
121 const TQ3TriMeshData& inData,
122 TQ3TriMeshData& outData )
123 : mOrigData( inData )
124 , mResultData( outData )
125 , mOrigFaceNormals( NULL )
126 , mOrigVertexNormals( NULL )
127 , mOrigFaceColor( NULL )
128 , mOrigVertexColor( NULL )
129 , mOrigFaceTransparency( NULL )
130 , mOrigVertexTransparency( NULL )
131 , mOrigFaceSpecularColor( NULL )
132 , mOrigVertexSpecularColor( NULL )
133 , mResultFaceNormals( NULL )
134 {
135 }
136
Optimize()137 TQ3Boolean TriMeshOptimizer::Optimize()
138 {
139 FindOrigAtts();
140
141 TQ3Boolean optNeeded = IsOptNeeded();
142
143 if (optNeeded)
144 {
145 EnsureFaceNormals();
146 MakeInstanceToPoint();
147 FindBackLinks();
148 FindDictinctVertices();
149 BuildNewTriMesh();
150 }
151
152 return optNeeded;
153 }
154
IsOptNeeded() const155 TQ3Boolean TriMeshOptimizer::IsOptNeeded() const
156 {
157 TQ3Boolean needOpt = kQ3False;
158
159 if ( (mOrigFaceNormals == NULL) ||
160 (mOrigVertexNormals == NULL) ||
161 ((mOrigFaceColor != NULL) && (mOrigVertexColor == NULL)) ||
162 ((mOrigFaceTransparency != NULL) && (mOrigVertexTransparency == NULL)) ||
163 ((mOrigFaceSpecularColor != NULL) && (mOrigVertexSpecularColor == NULL))
164 )
165 {
166 needOpt = kQ3True;
167 }
168
169 return needOpt;
170 }
171
172 /*!
173 @function MakeInstanceToPoint
174
175 @abstract For convenience, convert the triangles array into
176 a straight array of point indices.
177 */
MakeInstanceToPoint()178 void TriMeshOptimizer::MakeInstanceToPoint()
179 {
180 mInstanceToPoint.resize( mOrigData.numTriangles * 3 );
181
182 for (TQ3Uns32 i = 0; i < mOrigData.numTriangles; ++i)
183 {
184 mInstanceToPoint[ 3 * i ] = mOrigData.triangles[i].pointIndices[0];
185 mInstanceToPoint[ 3 * i + 1 ] = mOrigData.triangles[i].pointIndices[1];
186 mInstanceToPoint[ 3 * i + 2 ] = mOrigData.triangles[i].pointIndices[2];
187 }
188 }
189
190 /*!
191 @function FindBackLinks
192
193 @abstract For each point instance in mInstanceToPoint, find the previous instance
194 of the same point and record its index within mInstanceToPoint in an
195 array mPrevPointInstance. When there is no previous instance,
196 record -1.
197 */
FindBackLinks()198 void TriMeshOptimizer::FindBackLinks()
199 {
200 const TQ3Int32 kNumCoordIndices = mInstanceToPoint.size();
201 mPrevPointInstance.resize( kNumCoordIndices, -1 );
202 IntVec mostRecentPointInstance( mOrigData.numPoints, -1 );
203
204 for (TQ3Int32 i = 0; i < kNumCoordIndices; ++i)
205 {
206 TQ3Int32 pointIndex = mInstanceToPoint[i];
207 if (mostRecentPointInstance[ pointIndex ] >= 0)
208 {
209 mPrevPointInstance[i] = mostRecentPointInstance[ pointIndex ];
210 }
211 else
212 {
213 mPrevPointInstance[i] = -1;
214 }
215 mostRecentPointInstance[ pointIndex ] = i;
216 }
217 }
218
IsSameColor(const TQ3ColorRGB & inOne,const TQ3ColorRGB & inTwo)219 static bool IsSameColor( const TQ3ColorRGB& inOne, const TQ3ColorRGB& inTwo )
220 {
221 return fabsf(inOne.r - inTwo.r) + fabsf(inOne.g - inTwo.g) +
222 fabsf(inOne.b - inTwo.b) < FLT_EPSILON;
223 }
224
225 /*!
226 @function ArePointsSimilar
227
228 @abstract Determine whether two instances of the same point (given by
229 indices into mInstanceToPoint) should be treated as the same
230 vertex.
231 */
ArePointsSimilar(TQ3Int32 inPt1,TQ3Int32 inPt2)232 bool TriMeshOptimizer::ArePointsSimilar( TQ3Int32 inPt1, TQ3Int32 inPt2 )
233 {
234 bool isSame = true;
235 TQ3Int32 face1, face2;
236
237 face1 = inPt1 / 3;
238 face2 = inPt2 / 3;
239
240 // If vertex normals do not exist, similar instances must have the same
241 // face normal.
242 if (mOrigVertexNormals == NULL)
243 {
244 float dotProd = Q3FastVector3D_Dot( &mResultFaceNormals[face1],
245 &mResultFaceNormals[ face2 ] );
246
247 if (dotProd < 1.0f - FLT_EPSILON)
248 {
249 isSame = false;
250 }
251 }
252
253 // If the instances seem the same so far, and there are face colors but
254 // not vertex colors, then the face colors may distinguish them.
255 if ( isSame && (mOrigFaceColor != NULL) && (mOrigVertexColor == NULL) )
256 {
257 isSame = IsSameColor( mOrigFaceColor[face1], mOrigFaceColor[face2] );
258 }
259
260 // Same for transparency color.
261 if ( isSame && (mOrigFaceTransparency != NULL) && (mOrigVertexTransparency == NULL) )
262 {
263 isSame = IsSameColor( mOrigFaceTransparency[face1], mOrigFaceTransparency[face2] );
264 }
265
266 // Same for specular color.
267 if ( isSame && (mOrigFaceSpecularColor != NULL) && (mOrigVertexSpecularColor == NULL) )
268 {
269 isSame = IsSameColor( mOrigFaceSpecularColor[face1], mOrigFaceSpecularColor[face2] );
270 }
271
272 return isSame;
273 }
274
275 /*!
276 @function FindPrevSimilarPoint
277
278 @abstract Given a point instance index (index into mInstanceToPoint), find a
279 previous instance of the same point that can be considered to
280 be the same vertex.
281 */
FindPrevSimilarPoint(TQ3Int32 inPtInstanceIndex)282 TQ3Int32 TriMeshOptimizer::FindPrevSimilarPoint( TQ3Int32 inPtInstanceIndex )
283 {
284 TQ3Int32 prevSimilarIndex = -1;
285 TQ3Int32 prevIndex;
286 for (prevIndex = mPrevPointInstance[ inPtInstanceIndex ];
287 prevIndex >= 0;
288 prevIndex = mPrevPointInstance[ prevIndex ])
289 {
290 if (prevIndex >= mInstanceToPoint.size())
291 {
292 break;
293 }
294 else if (prevIndex < 0)
295 {
296 break;
297 }
298 else if(ArePointsSimilar( inPtInstanceIndex, prevIndex ))
299 {
300 prevSimilarIndex = prevIndex;
301 break;
302 }
303 }
304 return prevSimilarIndex;
305 }
306
307
308 /*!
309 @function FindDictinctVertices
310
311 @abstract Decide how points need to be duplicated.
312
313 @discussion Let's say the original TriMesh has F faces and P points.
314 The array mInstanceToPoint can be thought of as a function
315 from the set {0... 3F-1} to the set {0... P-1}.
316 Here we will construct an array mInstanceToVertex,
317 mapping {0... 3F-1} to {0... V-1}, and an array mVertexToPoint
318 mapping {0... V-1} to {0... P-1}, such that
319 mVertexToPoint[ mInstanceToVertex[i] ] == mInstanceToPoint[i]
320 for each i, and if i and j are instances that are not
321 "similar", mInstanceToVertex[i] != mInstanceToVertex[j].
322 We also need an array mVertexToFace that will map a vertex
323 to one of the faces that contains it, and an array
324 mPointToVertex that maps a point to one of the vertices at
325 that location.
326 */
FindDictinctVertices()327 void TriMeshOptimizer::FindDictinctVertices()
328 {
329 const TQ3Int32 kNumInstances = mInstanceToPoint.size();
330 mInstanceToVertex.resize( kNumInstances );
331 mPointToVertex.resize( mOrigData.numPoints, -1 );
332 TQ3Int32 i;
333
334 for (i = 0; i < kNumInstances; ++i)
335 {
336 TQ3Int32 prevSimilar = FindPrevSimilarPoint( i );
337 if (prevSimilar < 0)
338 {
339 // new vertex
340 mVertexToPoint.push_back( mInstanceToPoint[i] );
341 mInstanceToVertex[i] = mVertexToPoint.size() - 1;
342 mVertexToFace.push_back( i / 3 );
343 mPointToVertex[ mInstanceToPoint[i] ] = mVertexToPoint.size() - 1;
344 }
345 else
346 {
347 mInstanceToVertex[i] = mInstanceToVertex[ prevSimilar ];
348 }
349 }
350 }
351
352 /*!
353 @function BuildNewTriMesh
354
355 @abstract Set up the new TriMesh data.
356 */
BuildNewTriMesh()357 void TriMeshOptimizer::BuildNewTriMesh()
358 {
359 E3Shared_Acquire( &mResultData.triMeshAttributeSet, mOrigData.triMeshAttributeSet );
360 BuildFaces();
361 BuildFaceAttributes();
362 BuildEdges();
363 BuildEdgeAttributes();
364 BuildPoints();
365 BuildVertexAttributes();
366 ComputeBounds();
367 }
368
BuildFaces()369 void TriMeshOptimizer::BuildFaces()
370 {
371 mResultData.numTriangles = mOrigData.numTriangles;
372 mResultData.triangles = static_cast<TQ3TriMeshTriangleData*>(
373 E3Memory_Allocate( mResultData.numTriangles *
374 sizeof(TQ3TriMeshTriangleData) ) );
375 EQ3ThrowIfMemFail_( mResultData.triangles );
376
377 for (TQ3Uns32 i = 0; i < mResultData.numTriangles; ++i)
378 {
379 mResultData.triangles[i].pointIndices[0] = mInstanceToVertex[ 3 * i ];
380 mResultData.triangles[i].pointIndices[1] = mInstanceToVertex[ 3 * i + 1 ];
381 mResultData.triangles[i].pointIndices[2] = mInstanceToVertex[ 3 * i + 2 ];
382 }
383 }
384
GetAttributeSize(TQ3AttributeType inAttType)385 static TQ3Uns32 GetAttributeSize( TQ3AttributeType inAttType )
386 {
387 TQ3ObjectType attType = E3Attribute_AttributeToClassType( inAttType );
388 E3ClassInfoPtr theClass = E3ClassTree::GetClass( attType );
389 EQ3ThrowIf_( theClass == NULL );
390 TQ3Uns32 attrSize = theClass->GetInstanceSize();
391 return attrSize;
392 }
393
CopyAttributeData(TQ3Uns32 inNumElements,const TQ3TriMeshAttributeData & inSrc,TQ3TriMeshAttributeData & outDest)394 static void CopyAttributeData(
395 TQ3Uns32 inNumElements,
396 const TQ3TriMeshAttributeData& inSrc,
397 TQ3TriMeshAttributeData& outDest )
398 {
399 outDest.attributeType = inSrc.attributeType;
400
401 TQ3Uns32 attrSize = GetAttributeSize( inSrc.attributeType );
402 TQ3Uns32 bytes = inNumElements * attrSize;
403 if (bytes == 0)
404 {
405 outDest.data = NULL;
406 }
407 else
408 {
409 outDest.data = E3Memory_Allocate( bytes );
410 EQ3ThrowIfMemFail_( outDest.data );
411 E3Memory_Copy( inSrc.data, outDest.data, bytes );
412 }
413
414 if ( (inSrc.attributeUseArray == NULL) || (inNumElements == 0) )
415 {
416 outDest.attributeUseArray = NULL;
417 }
418 else
419 {
420 bytes = inNumElements;
421 outDest.attributeUseArray = static_cast<char*>( E3Memory_Allocate( bytes ) );
422 EQ3ThrowIfMemFail_( outDest.attributeUseArray );
423 E3Memory_Copy( inSrc.attributeUseArray, outDest.attributeUseArray, bytes );
424 }
425 }
426
BuildFaceAttributes()427 void TriMeshOptimizer::BuildFaceAttributes()
428 {
429 const TQ3Uns32 kNumAtts = mOrigData.numTriangleAttributeTypes;
430 mResultData.numTriangleAttributeTypes = kNumAtts;
431 if (mOrigFaceNormals == NULL)
432 {
433 mResultData.numTriangleAttributeTypes += 1;
434 }
435 mResultData.triangleAttributeTypes = static_cast<TQ3TriMeshAttributeData*>(
436 E3Memory_AllocateClear( mResultData.numTriangleAttributeTypes *
437 sizeof(TQ3TriMeshAttributeData) ) );
438 EQ3ThrowIfMemFail_( mResultData.triangleAttributeTypes );
439 TQ3Uns32 i;
440
441 for (i = 0; i < kNumAtts; ++i)
442 {
443 CopyAttributeData( mOrigData.numTriangles,
444 mOrigData.triangleAttributeTypes[i],
445 mResultData.triangleAttributeTypes[i] );
446 }
447
448 if (mOrigFaceNormals == NULL)
449 {
450 mResultData.triangleAttributeTypes[ kNumAtts ].attributeType
451 = kQ3AttributeTypeNormal;
452
453 mResultData.triangleAttributeTypes[ kNumAtts ].data =
454 E3Memory_Allocate( mOrigData.numTriangles * sizeof(TQ3Vector3D) );
455 EQ3ThrowIfMemFail_( mResultData.triangleAttributeTypes[ kNumAtts ].data );
456 E3Memory_Copy( &mComputedFaceNormals[0],
457 mResultData.triangleAttributeTypes[ kNumAtts ].data,
458 mOrigData.numTriangles * sizeof(TQ3Vector3D) );
459 }
460 }
461
BuildEdges()462 void TriMeshOptimizer::BuildEdges()
463 {
464 mResultData.numEdges = mOrigData.numEdges;
465
466 if (mResultData.numEdges == 0)
467 {
468 mResultData.edges = NULL;
469 }
470 else
471 {
472 mResultData.edges = static_cast<TQ3TriMeshEdgeData*>(
473 E3Memory_Allocate( mOrigData.numEdges * sizeof(TQ3TriMeshEdgeData) ) );
474 EQ3ThrowIfMemFail_( mResultData.edges );
475 E3Memory_Copy( mOrigData.edges, mResultData.edges,
476 mOrigData.numEdges * sizeof(TQ3TriMeshEdgeData) );
477
478 // Update point indices
479 for (TQ3Uns32 i = 0; i < mOrigData.numEdges; ++i)
480 {
481 mResultData.edges[i].pointIndices[0] =
482 mPointToVertex[ mResultData.edges[i].pointIndices[0] ];
483 mResultData.edges[i].pointIndices[1] =
484 mPointToVertex[ mResultData.edges[i].pointIndices[1] ];
485 }
486 }
487 }
488
BuildEdgeAttributes()489 void TriMeshOptimizer::BuildEdgeAttributes()
490 {
491 mResultData.numEdgeAttributeTypes = mOrigData.numEdgeAttributeTypes;
492
493 if (mResultData.numEdgeAttributeTypes == 0)
494 {
495 mResultData.edgeAttributeTypes = NULL;
496 }
497 else
498 {
499 mResultData.edgeAttributeTypes = static_cast<TQ3TriMeshAttributeData*>(
500 E3Memory_AllocateClear( mResultData.numEdgeAttributeTypes *
501 sizeof(TQ3TriMeshAttributeData) ) );
502 EQ3ThrowIfMemFail_( mResultData.edgeAttributeTypes );
503
504 for (TQ3Uns32 i = 0; i < mOrigData.numEdgeAttributeTypes; ++i)
505 {
506 CopyAttributeData( mOrigData.numEdges,
507 mOrigData.edgeAttributeTypes[i],
508 mResultData.edgeAttributeTypes[i] );
509 }
510 }
511 }
512
BuildPoints()513 void TriMeshOptimizer::BuildPoints()
514 {
515 mResultData.numPoints = mVertexToPoint.size();
516
517 if (mResultData.numPoints == 0)
518 {
519 mResultData.points = NULL;
520 }
521 else
522 {
523 mResultData.points = static_cast<TQ3Point3D*>(
524 E3Memory_AllocateClear( mResultData.numPoints * sizeof(TQ3Point3D) ) );
525 EQ3ThrowIfMemFail_( mResultData.points );
526
527 for (TQ3Uns32 i = 0; i < mResultData.numPoints; ++i)
528 {
529 mResultData.points[i] = mOrigData.points[ mVertexToPoint[i] ];
530 }
531 }
532 }
533
BuildVertexAttributes()534 void TriMeshOptimizer::BuildVertexAttributes()
535 {
536 bool isAddingNormals = (mOrigVertexNormals == NULL);
537 bool isAddingColor = ((mOrigFaceColor != NULL) && (mOrigVertexColor == NULL));
538 bool isAddingTransparency = ((mOrigFaceTransparency != NULL) &&
539 (mOrigVertexTransparency == NULL));
540 bool isAddingSpecular = ((mOrigFaceSpecularColor != NULL) &&
541 (mOrigVertexSpecularColor == NULL));
542
543 mResultData.numVertexAttributeTypes = mOrigData.numVertexAttributeTypes;
544 if (isAddingNormals)
545 {
546 mResultData.numVertexAttributeTypes += 1;
547 }
548 if (isAddingColor)
549 {
550 mResultData.numVertexAttributeTypes += 1;
551 }
552 if (isAddingTransparency)
553 {
554 mResultData.numVertexAttributeTypes += 1;
555 }
556 if (isAddingSpecular)
557 {
558 mResultData.numVertexAttributeTypes += 1;
559 }
560
561 mResultData.vertexAttributeTypes = static_cast<TQ3TriMeshAttributeData*>(
562 E3Memory_AllocateClear( mResultData.numVertexAttributeTypes *
563 sizeof(TQ3TriMeshAttributeData) ) );
564 EQ3ThrowIfMemFail_( mResultData.vertexAttributeTypes );
565 TQ3Uns32 i, j;
566
567 for (i = 0; i < mOrigData.numVertexAttributeTypes; ++i)
568 {
569 mResultData.vertexAttributeTypes[i].attributeType =
570 mOrigData.vertexAttributeTypes[i].attributeType;
571
572 TQ3Uns32 attrSize = GetAttributeSize(
573 mOrigData.vertexAttributeTypes[i].attributeType );
574 char* srcData;
575 char* dstData;
576
577 if (mResultData.numPoints > 0)
578 {
579 mResultData.vertexAttributeTypes[i].data =
580 E3Memory_Allocate( attrSize * mResultData.numPoints );
581 EQ3ThrowIfMemFail_( mResultData.vertexAttributeTypes[i].data );
582
583 srcData = static_cast<char*>( mOrigData.vertexAttributeTypes[i].data );
584 dstData = static_cast<char*>( mResultData.vertexAttributeTypes[i].data );
585
586 for (j = 0; j < mResultData.numPoints; ++j)
587 {
588 E3Memory_Copy( srcData + mVertexToPoint[j] * attrSize,
589 dstData + j * attrSize, attrSize );
590 }
591
592 if (mOrigData.vertexAttributeTypes[i].attributeUseArray != NULL)
593 {
594 mResultData.vertexAttributeTypes[i].attributeUseArray =
595 static_cast<char*>( E3Memory_Allocate( mResultData.numPoints ) );
596 EQ3ThrowIfMemFail_( mResultData.vertexAttributeTypes[i].attributeUseArray );
597
598 for (j = 0; j < mResultData.numPoints; ++j)
599 {
600 mResultData.vertexAttributeTypes[i].attributeUseArray[ j ] =
601 mOrigData.vertexAttributeTypes[i].attributeUseArray[
602 mVertexToPoint[j] ];
603 }
604 }
605 }
606 }
607
608 if (isAddingNormals)
609 {
610 mResultData.vertexAttributeTypes[i].attributeType = kQ3AttributeTypeNormal;
611 TQ3Vector3D* vertNormals = static_cast<TQ3Vector3D*>(
612 E3Memory_Allocate( mResultData.numPoints * sizeof(TQ3Vector3D) ) );
613 EQ3ThrowIfMemFail_( vertNormals );
614 mResultData.vertexAttributeTypes[i].data = vertNormals;
615
616 for (j = 0; j < mResultData.numPoints; ++j)
617 {
618 vertNormals[j] = mResultFaceNormals[ mVertexToFace[j] ];
619 }
620 ++i;
621 }
622
623 if (isAddingColor)
624 {
625 mResultData.vertexAttributeTypes[i].attributeType = kQ3AttributeTypeDiffuseColor;
626 TQ3ColorRGB* vertColors = static_cast<TQ3ColorRGB*>(
627 E3Memory_Allocate( mResultData.numPoints * sizeof(TQ3ColorRGB) ) );
628 EQ3ThrowIfMemFail_( vertColors );
629 mResultData.vertexAttributeTypes[i].data = vertColors;
630
631 for (j = 0; j < mResultData.numPoints; ++j)
632 {
633 vertColors[j] = mOrigFaceColor[ mVertexToFace[j] ];
634 }
635 ++i;
636 }
637
638 if (isAddingTransparency)
639 {
640 mResultData.vertexAttributeTypes[i].attributeType = kQ3AttributeTypeTransparencyColor;
641 TQ3ColorRGB* vertTrans = static_cast<TQ3ColorRGB*>(
642 E3Memory_Allocate( mResultData.numPoints * sizeof(TQ3ColorRGB) ) );
643 EQ3ThrowIfMemFail_( vertTrans );
644 mResultData.vertexAttributeTypes[i].data = vertTrans;
645
646 for (j = 0; j < mResultData.numPoints; ++j)
647 {
648 vertTrans[j] = mOrigFaceTransparency[ mVertexToFace[j] ];
649 }
650 ++i;
651 }
652
653 if (isAddingSpecular)
654 {
655 mResultData.vertexAttributeTypes[i].attributeType = kQ3AttributeTypeSpecularColor;
656 TQ3ColorRGB* vertSpecs = static_cast<TQ3ColorRGB*>(
657 E3Memory_Allocate( mResultData.numPoints * sizeof(TQ3ColorRGB) ) );
658 EQ3ThrowIfMemFail_( vertSpecs );
659 mResultData.vertexAttributeTypes[i].data = vertSpecs;
660
661 for (j = 0; j < mResultData.numPoints; ++j)
662 {
663 vertSpecs[j] = mOrigFaceSpecularColor[ mVertexToFace[j] ];
664 }
665 ++i;
666 }
667 }
668
ComputeBounds()669 void TriMeshOptimizer::ComputeBounds()
670 {
671 Q3BoundingBox_SetFromPoints3D( &mResultData.bBox, mResultData.points,
672 mResultData.numPoints, sizeof(TQ3Point3D) );
673 }
674
675
676 /*!
677 @function EnsureFaceNormals
678
679 @abstract If face normals were not provided, create them.
680 */
EnsureFaceNormals()681 void TriMeshOptimizer::EnsureFaceNormals()
682 {
683 if (mOrigFaceNormals == NULL)
684 {
685 mComputedFaceNormals.resize( mOrigData.numTriangles );
686
687 TQ3Vector3D theNormal;
688 TQ3Uns32 i;
689
690 for (i = 0; i < mOrigData.numTriangles; ++i)
691 {
692 typedef TQ3TriMeshTriangleData& TQ3TriMeshTriangleDataRef; // limited VC++ 6.0
693
694 TQ3TriMeshTriangleDataRef aFace( mOrigData.triangles[i] );
695
696 Q3FastPoint3D_CrossProductTri(
697 &mOrigData.points[ aFace.pointIndices[0] ],
698 &mOrigData.points[ aFace.pointIndices[1] ],
699 &mOrigData.points[ aFace.pointIndices[2] ],
700 &theNormal );
701 float lenSq = Q3FastVector3D_LengthSquared( &theNormal );
702
703 if (lenSq < kDegenerateLengthSquared)
704 {
705 theNormal.x = 1.0f;
706 theNormal.y = theNormal.z = 0.0f;
707 }
708 else
709 {
710 float len = sqrt( lenSq );
711 Q3FastVector3D_Scale( &theNormal, 1.0f/len, &theNormal );
712 }
713 mComputedFaceNormals[i] = theNormal;
714 }
715 mResultFaceNormals = &mComputedFaceNormals[0];
716 }
717 else
718 {
719 mResultFaceNormals = mOrigFaceNormals;
720 }
721 }
722
FindOrigAtts()723 void TriMeshOptimizer::FindOrigAtts()
724 {
725 TQ3Uns32 i;
726
727 for (i = 0; i < mOrigData.numTriangleAttributeTypes; ++i)
728 {
729 switch (mOrigData.triangleAttributeTypes[i].attributeType)
730 {
731 case kQ3AttributeTypeNormal:
732 mOrigFaceNormals = static_cast<const TQ3Vector3D*>(
733 mOrigData.triangleAttributeTypes[i].data );
734 break;
735
736 case kQ3AttributeTypeDiffuseColor:
737 mOrigFaceColor = static_cast<const TQ3ColorRGB*>(
738 mOrigData.triangleAttributeTypes[i].data );
739 break;
740
741 case kQ3AttributeTypeTransparencyColor:
742 mOrigFaceTransparency = static_cast<const TQ3ColorRGB*>(
743 mOrigData.triangleAttributeTypes[i].data );
744 break;
745
746 case kQ3AttributeTypeSpecularColor:
747 mOrigFaceSpecularColor = static_cast<const TQ3ColorRGB*>(
748 mOrigData.triangleAttributeTypes[i].data );
749 break;
750 }
751 }
752
753
754 for (i = 0; i < mOrigData.numVertexAttributeTypes; ++i)
755 {
756 switch (mOrigData.vertexAttributeTypes[i].attributeType)
757 {
758 case kQ3AttributeTypeNormal:
759 mOrigVertexNormals = static_cast<const TQ3Vector3D*>(
760 mOrigData.vertexAttributeTypes[i].data );
761 break;
762
763 case kQ3AttributeTypeDiffuseColor:
764 mOrigVertexColor = static_cast<const TQ3ColorRGB*>(
765 mOrigData.vertexAttributeTypes[i].data );
766 break;
767
768 case kQ3AttributeTypeTransparencyColor:
769 mOrigVertexTransparency = static_cast<const TQ3ColorRGB*>(
770 mOrigData.vertexAttributeTypes[i].data );
771 break;
772
773 case kQ3AttributeTypeSpecularColor:
774 mOrigVertexSpecularColor = static_cast<const TQ3ColorRGB*>(
775 mOrigData.vertexAttributeTypes[i].data );
776 break;
777 }
778 }
779 }
780
781 /*!
782 @function E3TriMesh_OptimizeData
783
784 @abstract Modify TriMesh data, if needed, for efficient use by the
785 interactive renderer.
786
787 @discussion This operation modifies TriMesh data so that:
788 <ol>
789 <li>Face normals exist.</li>
790 <li>Vertex normals exist.</li>
791 <li>If Face colors exist, then vertex colors exist.</li>
792 </ol>
793
794 If face normals do not already exist, they will be computed
795 by cross products of edges. The orientation will be assumed
796 to be counterclockwise.
797
798 If vertex normals do not already exist, they will be derived
799 from face normals. When a vertex belongs to faces with
800 different normals, the vertex will be duplicated.
801
802 If a color attribute (diffuse, transparent, or specular) exists
803 on faces but not vertices, it will be converted to a vertex
804 attribute, duplicating vertices when needed.
805
806 If no optimization is needed, outDidChange will return kQ3False
807 and outData will be cleared to zero. If optimization was
808 performed, indicated by outDidChange being kQ3True, then you
809 are responsible for calling Q3TriMesh_EmptyData on the outData
810 structure when you are done with it.
811
812 @param inData TriMesh data.
813 @param outData Receives new TriMesh data, if outDidChange is true.
814 @param outDidChange Receives a flag indicating whether new data
815 was created.
816 @result Success or failure of the operation.
817 */
E3TriMesh_OptimizeData(const TQ3TriMeshData & inData,TQ3TriMeshData & outData,TQ3Boolean & outDidChange)818 TQ3Status E3TriMesh_OptimizeData( const TQ3TriMeshData& inData,
819 TQ3TriMeshData& outData,
820 TQ3Boolean& outDidChange )
821 {
822 TQ3Status theStatus = kQ3Success;
823 outDidChange = kQ3False;
824 E3Memory_Clear( &outData, sizeof(TQ3TriMeshData) );
825
826 try
827 {
828 TriMeshOptimizer optimizer( inData, outData );
829
830 outDidChange = optimizer.Optimize();
831 }
832 catch (...)
833 {
834 theStatus = kQ3Failure;
835 E3Memory_Clear( &outData, sizeof(TQ3TriMeshData) );
836 }
837
838 return theStatus;
839 }
840
841
842 /*!
843 @function E3TriMesh_Optimize
844
845 @abstract Modify a TriMesh, if needed, for efficient use by the
846 interactive renderer.
847
848 @discussion See discussion of E3TriMesh_OptimizeData for the optimizations
849 that are performed. If no optimizations are needed, NULL
850 is returned.
851
852 @param inTriMesh A TriMesh geometry.
853 @result A TriMesh or NULL.
854 */
E3TriMesh_Optimize(TQ3GeometryObject inTriMesh)855 TQ3GeometryObject E3TriMesh_Optimize( TQ3GeometryObject inTriMesh )
856 {
857 TQ3GeometryObject theResult = NULL;
858
859 TQ3TriMeshData* origData = NULL;
860
861 if (kQ3Success == Q3TriMesh_LockData( inTriMesh, kQ3True, &origData ))
862 {
863 TQ3Boolean didChange = kQ3False;
864 TQ3TriMeshData optData;
865
866 if ( (kQ3Success == E3TriMesh_OptimizeData( *origData, optData, didChange )) &&
867 (didChange == kQ3True) )
868 {
869 theResult = Q3TriMesh_New( &optData );
870
871 Q3TriMesh_EmptyData( &optData );
872 }
873 }
874
875 return theResult;
876 }
877