1 /**************************************************************************\
2  * Copyright (c) Kongsberg Oil & Gas Technologies AS
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met:
8  *
9  * Redistributions of source code must retain the above copyright notice,
10  * this list of conditions and the following disclaimer.
11  *
12  * Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in the
14  * documentation and/or other materials provided with the distribution.
15  *
16  * Neither the name of the copyright holder nor the names of its
17  * contributors may be used to endorse or promote products derived from
18  * this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 \**************************************************************************/
32 
33 /*!
34   \class SoNormalCache SoNormalCache.h Inventor/caches/SoNormalCache.h
35   \brief The SoNormalCache class is used to hold cached normals.
36 
37   \ingroup caches
38 
39   As an extension to the original SGI Open Inventor v2.1 API, it is
40   also possible to generate normals using this class.
41 
42   It is more powerful and easier to use than the SoNormalGenerator
43   class. It is possible to generate normals per vertex with indices
44   (using much less memory than plain per vertex normals), and it
45   contains special methods to generate normals for triangle strips and
46   quads.
47 */
48 
49 // *************************************************************************
50 
51 #include <Inventor/caches/SoNormalCache.h>
52 
53 #include <cfloat> // FLT_EPSILON
54 
55 #include <Inventor/misc/SoNormalGenerator.h>
56 #include <Inventor/lists/SbList.h>
57 #include <Inventor/errors/SoDebugError.h>
58 
59 #include "tidbitsp.h"
60 
61 // *************************************************************************
62 
63 #ifndef DOXYGEN_SKIP_THIS
64 class SoNormalCacheP {
65 public:
66   int numNormals;
67   union {
68     const SbVec3f *normals;
69     SoNormalGenerator *generator;
70   } normalData;
71   SbList <int32_t> indices;
72   SbList <SbVec3f> normalArray;
73 };
74 #endif // DOXYGEN_SKIP_THIS
75 
76 //
77 // FIXME: add test to shrink normalArray.
78 //
79 
80 #define NORMAL_EPSILON FLT_EPSILON
81 
82 #define PRIVATE(obj) ((obj)->pimpl)
83 
84 #define NORMALCACHE_DEBUG 0 // Set to one for debug output
85 
86 // *************************************************************************
87 
88 /*!
89   Contructor with \a state being the current state.
90 */
SoNormalCache(SoState * const state)91 SoNormalCache::SoNormalCache(SoState * const state)
92   : SoCache(state)
93 {
94   PRIVATE(this) = new SoNormalCacheP;
95   PRIVATE(this)->normalData.normals = NULL;
96   PRIVATE(this)->numNormals = 0;
97 
98 #if COIN_DEBUG
99   if (coin_debug_caching_level() > 0) {
100     SoDebugError::postInfo("SoNormalCache::SoNormalCache",
101                            "Cache created: %p", this);
102 
103   }
104 #endif // debug
105 }
106 
107 /*!
108   Destructor
109 */
~SoNormalCache()110 SoNormalCache::~SoNormalCache()
111 {
112 #if COIN_DEBUG
113   if (coin_debug_caching_level() > 0) {
114     SoDebugError::postInfo("SoNormalCache::~SoNormalCache",
115                            "Cache destructed: %p", this);
116 
117   }
118 #endif // debug
119 
120   this->clearGenerator();
121   delete PRIVATE(this);
122 }
123 
124 /*!
125   Sets an array of normals for this cache. The normals will not
126   be deleted when the instance is deleted.
127 */
128 void
set(const int num,const SbVec3f * const normals)129 SoNormalCache::set(const int num, const SbVec3f * const normals)
130 {
131   this->clearGenerator();
132   PRIVATE(this)->numNormals = num;
133   PRIVATE(this)->normalData.normals = normals;
134   PRIVATE(this)->indices.truncate(0, TRUE);
135   PRIVATE(this)->normalArray.truncate(0, TRUE);
136 }
137 
138 /*!
139   Uses a normal generator in this cache. The normal generator will
140   be deleted when the cache is deleted or reset.
141 */
142 void
set(SoNormalGenerator * generator)143 SoNormalCache::set(SoNormalGenerator * generator)
144 {
145   this->clearGenerator();
146   PRIVATE(this)->indices.truncate(0, TRUE);
147   PRIVATE(this)->normalArray.truncate(0, TRUE);
148   PRIVATE(this)->numNormals = 0;
149   PRIVATE(this)->normalData.generator = generator;
150 }
151 
152 /*!
153   Returns the number of normals in the cache.
154 */
155 int
getNum(void) const156 SoNormalCache::getNum(void) const
157 {
158   if (PRIVATE(this)->numNormals == 0 && PRIVATE(this)->normalData.generator) {
159     return PRIVATE(this)->normalData.generator->getNumNormals();
160   }
161   return PRIVATE(this)->numNormals;
162 }
163 
164 /*!
165   Return a pointer to the normals in this cache.
166 */
167 const SbVec3f *
getNormals(void) const168 SoNormalCache::getNormals(void) const
169 {
170   if (PRIVATE(this)->numNormals == 0 && PRIVATE(this)->normalData.generator) {
171     return PRIVATE(this)->normalData.generator->getNormals();
172   }
173   return PRIVATE(this)->normalData.normals;
174 }
175 
176 /*!
177   Returns the number of indices in this cache. Normals are
178   generated with PER_VERTEX_INDEXED binding.
179 */
180 int
getNumIndices(void) const181 SoNormalCache::getNumIndices(void) const
182 {
183   return PRIVATE(this)->indices.getLength();
184 }
185 
186 /*!
187   Returns the normal indices.
188 */
189 const int32_t *
getIndices(void) const190 SoNormalCache::getIndices(void) const
191 {
192   if (PRIVATE(this)->indices.getLength()) return PRIVATE(this)->indices.getArrayPtr();
193   return NULL;
194 }
195 
196 //
197 // calculates the normal vector for a vertex, based on the
198 // normal vectors of all incident faces
199 //
200 static void
calc_normal_vec(const SbVec3f * facenormals,const int facenum,const int numfacenorm,SbList<int32_t> & faceArray,const float threshold,SbVec3f & vertnormal)201 calc_normal_vec(const SbVec3f * facenormals, const int facenum,
202                 const int numfacenorm, SbList <int32_t> & faceArray,
203                 const float threshold, SbVec3f & vertnormal)
204 {
205   // start with face normal vector
206   const SbVec3f * facenormal = & facenormals[facenum];
207   vertnormal = *facenormal;
208 
209   int n = faceArray.getLength();
210   int currface;
211 
212   for (int i = 0; i < n; i++) {
213     currface = faceArray[i];
214     if (currface != facenum) { // check all but this face
215       if (currface < numfacenorm || numfacenorm == -1) { // -1 means: assume
216         const SbVec3f & normal = facenormals[currface];  // everything is ok
217         if ((normal.dot(*facenormal)) > threshold) {
218           // smooth towards this face
219           vertnormal += normal;
220         }
221       }
222       else {
223         static int calc_norm_error = 0;
224         if (calc_norm_error < 1) {
225           SoDebugError::postWarning("SoNormalCache::calc_normal_vec", "Normals "
226                                     "have not been specified for all faces. "
227                                     "this warning will only be shown once, "
228                                     "but there might be more errors");
229         }
230 
231         calc_norm_error++;
232       }
233     }
234   }
235 }
236 
237 /*!
238   Generates normals for each vertex for each face. It is possible to
239   specify face normals if these have been calculated somewhere else,
240   otherwise the face normals will be calculated before the vertex
241   normals are calculated. \a tristrip should be \c TRUE if the
242   geometry consists of triangle strips.
243 */
244 void
generatePerVertex(const SbVec3f * const coords,const unsigned int numcoords,const int32_t * vindex,const int numvi,const float crease_angle,const SbVec3f * facenormals,const int numfacenormals,const SbBool ccw,const SbBool tristrip)245 SoNormalCache::generatePerVertex(const SbVec3f * const coords,
246                                  const unsigned int numcoords,
247                                  const int32_t * vindex,
248                                  const int numvi,
249                                  const float crease_angle,
250                                  const SbVec3f * facenormals,
251                                  const int numfacenormals,
252                                  const SbBool ccw,
253                                  const SbBool tristrip)
254 {
255 #if NORMALCACHE_DEBUG && COIN_DEBUG
256   SoDebugError::postInfo("SoNormalCache::generatePerVertex", "generating normals");
257 #endif
258 
259   this->clearGenerator();
260   PRIVATE(this)->indices.truncate(0);
261   PRIVATE(this)->normalArray.truncate(0);
262 
263 
264 #if COIN_DEBUG && 0 // debug
265   SoDebugError::postInfo("SoNormalCache::generatePerVertex", "%d", numvi);
266   for (int vrtidx=0; vrtidx < numvi; vrtidx++)
267     fprintf(stdout, "%d ", vindex[vrtidx]);
268   fprintf(stdout, "\n");
269 #endif // debug
270 
271 
272   int numfacenorm = numfacenormals;
273   SoNormalCache tempcache(NULL);
274   const SbVec3f * facenorm = const_cast<SbVec3f *>(facenormals);
275   if (facenorm == NULL) {
276     // use a SoNormalCache to store temporary data
277     if (tristrip) {
278       tempcache.generatePerFaceStrip(coords, numcoords, vindex, numvi, ccw);
279     }
280     else {
281       tempcache.generatePerFace(coords, numcoords, vindex, numvi, ccw);
282     }
283 
284     facenorm = tempcache.getNormals();
285     numfacenorm = tempcache.getNum();
286 
287     assert(facenorm && "Normals should be generated for all coords");
288   }
289 
290   // find biggest vertex index
291   int i;
292   int maxi = 0;
293   int temp;
294   for (i = 0; i < numvi; i++) {
295     temp = vindex[i]; // don't care about -1's
296     if (temp > maxi) maxi = temp;
297   }
298 
299   // for each vertex, store all faceindices the vertex is a part of
300   SbList<int32_t> * vertexFaceArray = new SbList<int32_t>[maxi+1]; // [0, maxi]
301 
302   // for each vertex, store all normals that have been calculated
303   SbList <int32_t>* vertexNormalArray = new SbList<int32_t>[maxi+1]; // [0, maxi]
304 
305   int numfaces = 0;
306 
307   if (tristrip) {
308     // Find and save the faces belonging to the different vertices
309     i = 0;
310     while (i + 2 < numvi) {
311       temp = vindex[i];
312       if (temp >= 0 && static_cast<unsigned int>(temp) < numcoords) {
313         vertexFaceArray[temp].append(numfaces);
314       }
315       else {
316         i = i+1;
317         numfaces++;
318         continue;
319       }
320 
321       temp = vindex[i+1];
322       if (temp >= 0 && static_cast<unsigned int>(temp) < numcoords) {
323         vertexFaceArray[temp].append(numfaces);
324       }
325       else {
326         i = i+2;
327         numfaces++;
328         continue;
329       }
330 
331       temp = vindex[i+2];
332       if (temp >= 0 && static_cast<unsigned int>(temp) < numcoords) {
333         vertexFaceArray[temp].append(numfaces);
334       }
335       else {
336         i = i+3;
337         numfaces++;
338         continue;
339       }
340 
341       temp = i+3 < numvi ? vindex[i+3] : -1;
342       if (temp < 0 || static_cast<unsigned int>(temp) >= numcoords) {
343         i = i + 4; // Jump to next possible face
344         numfaces++;
345         continue;
346       }
347 
348       i++;
349       numfaces++;
350     }
351   }
352   else { // !tristrip
353     for (i = 0; i < numvi; i++) {
354       temp = vindex[i];
355       if (temp >= 0 && static_cast<unsigned int>(temp) < numcoords) {
356         vertexFaceArray[temp].append(numfaces);
357       }
358       else {
359         numfaces++;
360       }
361     }
362   }
363 
364   float threshold = static_cast<float>(cos(SbClamp(crease_angle, 0.0f, static_cast<float>(M_PI))));
365   SbBool found;
366   int currindex = 0; // current normal index
367   int nindex = 0;
368   int j, n ;
369   int facenum = 0;
370   int stripcnt = 0;
371 
372   for (i = 0; i < numvi; i++) {
373     currindex = vindex[i];
374     if (currindex >= 0 && static_cast<unsigned int>(currindex) < numcoords) {
375       if (tristrip) {
376         if (++stripcnt > 3) facenum++; // next face
377       }
378       // calc normal for this vertex
379       SbVec3f tmpvec;
380       calc_normal_vec(facenorm, facenum, numfacenorm, vertexFaceArray[currindex],
381                       threshold, tmpvec);
382 
383       // Be robust when it comes to erroneously specified triangles.
384       if ((tmpvec.normalize() == 0.0f) && coin_debug_extra()) {
385 #if COIN_DEBUG
386         static uint32_t normgenerrors_vertex = 0;
387         if (normgenerrors_vertex < 1) {
388           SoDebugError::postWarning("SoNormalCache::generatePerVertex","Unable to "
389                                     "generate valid normal for face %d", facenum);
390         }
391         normgenerrors_vertex++;
392 #endif // COIN_DEBUG
393       }
394       // it's really ok to have a null vector for a face/vertex, and we
395       // should not set it to some dummy vector. A null vector just
396       // means that the face is empty, and that the face shouldn't be
397       // considered when generating vertex normals.
398       // pederb, 2005-12-21
399 
400       if (PRIVATE(this)->normalArray.getLength() <= nindex)
401         PRIVATE(this)->normalArray.append(tmpvec);
402       else
403         PRIVATE(this)->normalArray[nindex] = tmpvec;
404 
405       // try to find equal normal (total smoothing)
406       SbList <int32_t> & array = vertexNormalArray[currindex];
407       found = FALSE;
408       n = array.getLength();
409       int same_normal = -1;
410       for (j = 0; j < n && !found; j++) {
411         same_normal = array[j];
412         found = PRIVATE(this)->normalArray[same_normal].equals(PRIVATE(this)->normalArray[nindex],
413                                                       NORMAL_EPSILON);
414       }
415       if (found)
416         PRIVATE(this)->indices.append(same_normal);
417       // might be equal to the previous normal (when all normals for a face are equal)
418       else if ((nindex > 0) &&
419                PRIVATE(this)->normalArray[nindex].equals(PRIVATE(this)->normalArray[nindex-1],
420                                                 NORMAL_EPSILON)) {
421         PRIVATE(this)->indices.append(nindex-1);
422       }
423       else {
424         PRIVATE(this)->indices.append(nindex);
425         array.append(nindex);
426         nindex++;
427       }
428     }
429     else { // new face
430       facenum++;
431       stripcnt = 0;
432       PRIVATE(this)->indices.append(-1); // add a -1 for PER_VERTEX_INDEXED binding
433     }
434   }
435   if (PRIVATE(this)->normalArray.getLength()) {
436     PRIVATE(this)->normalData.normals = PRIVATE(this)->normalArray.getArrayPtr();
437     PRIVATE(this)->numNormals = PRIVATE(this)->normalArray.getLength();
438   }
439 #if NORMALCACHE_DEBUG && COIN_DEBUG
440   SoDebugError::postInfo("SoNormalCache::generatePerVertex",
441                          "generated normals per vertex: %p %d %d\n",
442                          PRIVATE(this)->normalData.normals, PRIVATE(this)->numNormals, PRIVATE(this)->indices.getLength());
443 #endif
444   delete [] vertexFaceArray;
445   delete [] vertexNormalArray;
446 }
447 
448 /*!
449   Generates face normals for the faceset defined by \a coords
450   and \a cind.
451 */
452 void
generatePerFace(const SbVec3f * const coords,const unsigned int numcoords,const int32_t * cind,const int nv,const SbBool ccw)453 SoNormalCache::generatePerFace(const SbVec3f * const coords,
454                                const unsigned int numcoords,
455                                const int32_t * cind,
456                                const int nv,
457                                const SbBool ccw)
458 {
459 #if NORMALCACHE_DEBUG && COIN_DEBUG
460     SoDebugError::postInfo("SoNormalCache::generatePerFace", "generating normals");
461 #endif
462 
463   this->clearGenerator();
464   PRIVATE(this)->indices.truncate(0);
465   PRIVATE(this)->normalArray.truncate(0, TRUE);
466 
467   const int32_t * cstart = cind;
468   const int32_t * endptr = cind + nv;
469 
470   SbVec3f tmpvec;
471 
472   int maxcoordidx = numcoords - 1;
473 
474   while (cind + 2 < endptr) {
475     int v0 = cind[0];
476     int v1 = cind[1];
477     int v2 = cind[2];
478 
479     if (v0 < 0 || v1 < 0 || v2 < 0 ||
480         v0 > maxcoordidx || v1 > maxcoordidx || v2 > maxcoordidx) {
481 #if COIN_DEBUG
482       SoDebugError::postWarning("SoNormalCache::generatePerFace",
483                                 "Polygon with less than three valid "
484                                 "vertices detected. (offset: %d, [%d %d %d]). "
485                                 "Should be within [0, %d].",
486                                 cind - cstart, v0, v1, v2, maxcoordidx);
487 #endif // COIN_DEBUG
488 
489        // Insert dummy normal for robustness
490       SbVec3f dummynormal;
491       dummynormal.setValue(0.0f, 0.0f, 0.0f);
492       PRIVATE(this)->normalArray.append(dummynormal);
493 
494       // Skip ahead to next possible index
495       if (cind[0] < 0 || cind[0] > maxcoordidx) {
496         cind += 1;
497       }
498       else if (cind[1] < 0 || cind[1] > maxcoordidx) {
499         cind += 2;
500       }
501       else if (cind + 3 < endptr && (cind[2] < 0 || cind[2] > maxcoordidx)) {
502         cind += 3;
503       }
504       else {
505         cind += 3; // For robustness check after while loop
506         break;
507       }
508 
509       continue;
510     }
511 
512     if (cind + 3 >= endptr || cind[3] < 0 || cind[3] > maxcoordidx) { // triangle
513       if (!ccw)
514         tmpvec = (coords[v0] - coords[v1]).cross(coords[v2] - coords[v1]);
515       else
516         tmpvec = (coords[v2] - coords[v1]).cross(coords[v0] - coords[v1]);
517 
518       // Be robust when it comes to erroneously specified triangles.
519       if ((tmpvec.normalize() == 0.0f) && coin_debug_extra()) {
520         static uint32_t normgenerrors_face = 0;
521         if (normgenerrors_face < 1) {
522           SoDebugError::postWarning("SoNormalCache::generatePerFace",
523                                     "Erroneous triangle specification in model "
524                                     "(indices= [%d, %d, %d], "
525                                     "coords=<%f, %f, %f>, <%f, %f, %f>, <%f, %f, %f>) "
526                                     "(this warning will be printed only once, "
527                                     "but there might be more errors).",
528                                     v0, v1, v2,
529                                     coords[v0][0], coords[v0][1], coords[v0][2],
530                                     coords[v1][0], coords[v1][1], coords[v1][2],
531                                     coords[v2][0], coords[v2][1], coords[v2][2]);
532         }
533         normgenerrors_face++;
534       }
535 
536       PRIVATE(this)->normalArray.append(tmpvec);
537       cind += 4; // goto next triangle/polygon
538     }
539     else { // more than 3 vertices
540       // use Newell's method to calculate normal vector
541       const SbVec3f * vert1, * vert2;
542       tmpvec.setValue(0.0f, 0.0f, 0.0f);
543       vert2 = coords + v0;
544       cind++; // v0 is already read
545 
546       // The cind < endptr check makes us robust with regard to a
547       // missing "-1" termination of the coordIndex field of the
548       // IndexedShape nodetype.
549       while (cind < endptr && *cind >= 0 && *cind <= maxcoordidx) {
550         vert1 = vert2;
551         vert2 = coords + *cind++;
552         tmpvec[0] += ((*vert1)[1] - (*vert2)[1]) * ((*vert1)[2] + (*vert2)[2]);
553         tmpvec[1] += ((*vert1)[2] - (*vert2)[2]) * ((*vert1)[0] + (*vert2)[0]);
554         tmpvec[2] += ((*vert1)[0] - (*vert2)[0]) * ((*vert1)[1] + (*vert2)[1]);
555       }
556 
557       vert1 = vert2;  // last edge (back to v0)
558       vert2 = coords + v0;
559       tmpvec[0] += ((*vert1)[1] - (*vert2)[1]) * ((*vert1)[2] + (*vert2)[2]);
560       tmpvec[1] += ((*vert1)[2] - (*vert2)[2]) * ((*vert1)[0] + (*vert2)[0]);
561       tmpvec[2] += ((*vert1)[0] - (*vert2)[0]) * ((*vert1)[1] + (*vert2)[1]);
562 
563       // Be robust when it comes to erroneously specified polygons.
564       if ((tmpvec.normalize() == 0.0f) && coin_debug_extra()) {
565         static uint32_t normgenerrors_face = 0;
566         if (normgenerrors_face < 1) {
567           SoDebugError::postWarning("SoNormalCache::generatePerFace",
568                                     "Erroneous polygon specification in model. "
569                                     "Unable to generate normal; using dummy normal. "
570                                     "(this warning will be printed only once, "
571                                     "but there might be more errors).");
572         }
573         normgenerrors_face++;
574       }
575 
576       PRIVATE(this)->normalArray.append(ccw ? tmpvec : -tmpvec);
577       cind++; // skip the -1
578     }
579   }
580 
581   if (endptr - cind > 0) {
582 #if COIN_DEBUG
583     SoDebugError::postWarning("SoNormalCache::generatePerFace", "Face "
584                               "specification did not end with a valid "
585                               "polygon. Too few points");
586 #endif // COIN_DEBUG
587     SbVec3f dummynormal;
588     dummynormal.setValue(0.0f, 0.0f, 0.0f);
589     PRIVATE(this)->normalArray.append(dummynormal);
590   }
591 
592   if (PRIVATE(this)->normalArray.getLength()) {
593     PRIVATE(this)->normalData.normals = PRIVATE(this)->normalArray.getArrayPtr();
594     PRIVATE(this)->numNormals = PRIVATE(this)->normalArray.getLength();
595   }
596 
597 #if NORMALCACHE_DEBUG && COIN_DEBUG // debug
598   SoDebugError::postInfo("SoNormalCache::generatePerFace",
599                          "generated normals per face: %p %d",
600                          PRIVATE(this)->normalData.normals, PRIVATE(this)->numNormals);
601 #endif // debug
602 }
603 
604 /*!
605   Generates face normals for triangle strips.
606 */
607 void
generatePerFaceStrip(const SbVec3f * const coords,const unsigned int numcoords,const int32_t * cind,const int nv,const SbBool ccw)608 SoNormalCache::generatePerFaceStrip(const SbVec3f * const coords,
609                                     const unsigned int numcoords,
610                                     const int32_t * cind,
611                                     const int nv,
612                                     const SbBool ccw)
613 {
614 #if NORMALCACHE_DEBUG && COIN_DEBUG
615   SoDebugError::postInfo("SoNormalCache::generatePerFaceStrip", "generating normals");
616 #endif
617 
618   this->clearGenerator();
619   PRIVATE(this)->indices.truncate(0);
620   PRIVATE(this)->normalArray.truncate(0, TRUE);
621 
622   const int32_t * cstart = cind;
623   const int32_t * endptr = cind + nv;
624 
625   const SbVec3f * c0, * c1, * c2;
626   SbVec3f n;
627 
628   SbBool flip = ccw;
629 
630   const int maxcoordidx = numcoords - 1;
631 
632   while (cind + 2 < endptr) {
633     if (cind[0] < 0 || cind[1] < 0 || cind[2] < 0 ||
634         cind[0] > maxcoordidx || cind[1] > maxcoordidx || cind[2] > maxcoordidx) {
635 #if COIN_DEBUG
636       SoDebugError::postWarning("SoNormalCache::generatePerFaceStrip", "Erroneous "
637                                 "coordinate index detected (offset: %d, [%d %d %d]). Should be "
638                                 "within [0, %d].",
639                                 cind - cstart, *(cind), *(cind+1), *(cind+2), maxcoordidx);
640 #endif // COIN_DEBUG
641 
642       // Insert dummy normal for robustness
643       SbVec3f dummynormal;
644       dummynormal.setValue(0.0, 0.0, 0.0);
645       PRIVATE(this)->normalArray.append(dummynormal);
646 
647       // Skip to next possibly valid index
648       if (cind[0] < 0 || cind[0] > maxcoordidx) {
649         cind += 1;
650       }
651       else if (cind[1] < 0 || cind[1] > maxcoordidx) {
652         cind += 2;
653       }
654       else if (cind + 3 < endptr && (cind[2] < 0 || cind[2] > maxcoordidx)) {
655         cind += 3;
656       }
657       else {
658         cind += 3; // For robustness check after while loop
659         break;
660       }
661 
662       continue;
663     }
664 
665     flip = ccw;
666     c0 = &coords[*cind++];
667     c1 = &coords[*cind++];
668     c2 = &coords[*cind++];
669 
670     if (!flip)
671       n = (*c0 - *c1).cross(*c2 - *c1);
672     else
673       n = (*c2 - *c1).cross(*c0 - *c1);
674 
675     static uint32_t normgenerrors_facestrip = 0;
676     if ((n.normalize() == 0.0f) && coin_debug_extra()) {
677       if (normgenerrors_facestrip < 1) {
678         SoDebugError::postWarning("SoNormalCache::generatePerFaceStrip",
679                                   "Erroneous triangle specification in model "
680                                   "(coords=<%f, %f, %f>, <%f, %f, %f>, <%f, %f, %f>) "
681                                   "(this warning will be printed only once, "
682                                   "but there might be more errors).",
683                                   c0[0][0], c0[0][1], c0[0][2],
684                                   c1[0][0], c1[0][1], c1[0][2],
685                                   c2[0][0], c2[0][1], c2[0][2]);
686 
687 
688 
689       }
690       normgenerrors_facestrip++;
691     }
692 
693     PRIVATE(this)->normalArray.append(n);
694 
695     int idx = cind < endptr ? *cind++ : -1;
696     while (idx >= 0 && idx <= maxcoordidx) {
697       c0 = c1;
698       c1 = c2;
699       c2 = &coords[idx];
700       flip = !flip;
701       if (!flip)
702         n = (*c0 - *c1).cross(*c2 - *c1);
703       else
704         n = (*c2 - *c1).cross(*c0 - *c1);
705 
706       if ((n.normalize() == 0.0f) && coin_debug_extra()) {
707         if (normgenerrors_facestrip < 1) {
708           SoDebugError::postWarning("SoNormalCache::generatePerFaceStrip",
709                                     "Erroneous triangle specification in model "
710                                     "(coords=<%f, %f, %f>, <%f, %f, %f>, <%f, %f, %f>) "
711                                     "(this warning will be printed only once, "
712                                     "but there might be more errors).",
713                                     c0[0][0], c0[0][1], c0[0][2],
714                                     c1[0][0], c1[0][1], c1[0][2],
715                                     c2[0][0], c2[0][1], c2[0][2]);
716         }
717         normgenerrors_facestrip++;
718       }
719 
720       PRIVATE(this)->normalArray.append(n);
721       idx = cind < endptr ? *cind++ : -1;
722     }
723 #if COIN_DEBUG
724     if (idx > maxcoordidx) {
725       static uint32_t normgenerrors_facestrip = 0;
726       if (normgenerrors_facestrip < 1) {
727         SoDebugError::postWarning("SoNormalCache::generatePerFaceStrip",
728                                   "Erroneous polygon specification in model. "
729                                   "Index out of bounds: %d. Max index: %d. "
730                                   "(this warning will be printed only once, "
731                                   "but there might be more errors).",
732                                   idx, maxcoordidx);
733       }
734       normgenerrors_facestrip++;
735     }
736 #endif // COIN_DEBUG
737   }
738 
739   if (endptr - cind > 0) {
740 #if COIN_DEBUG
741     SoDebugError::postWarning("SoNormalCache::generatePerFaceStrip", "Strip "
742                               "did not end with a valid polygon. Too few "
743                               "points");
744 #endif // COIN_DEBUG
745     SbVec3f dummynormal;
746     dummynormal.setValue(0.0, 0.0, 0.0);
747     PRIVATE(this)->normalArray.append(dummynormal);
748   }
749 
750   if (PRIVATE(this)->normalArray.getLength()) {
751     PRIVATE(this)->normalData.normals = PRIVATE(this)->normalArray.getArrayPtr();
752     PRIVATE(this)->numNormals = PRIVATE(this)->normalArray.getLength();
753   }
754 
755 #if NORMALCACHE_DEBUG && COIN_DEBUG
756   SoDebugError::postInfo("SoNormalCache::generatePerFaceStrip",
757                          "generated tristrip normals per face: %p %d",
758                          PRIVATE(this)->normalData.normals, PRIVATE(this)->numNormals);
759 #endif // debug
760 
761 }
762 
763 /*!
764   Generates one normal per triangle strips (avarages all triangle normals).
765 */
766 void
generatePerStrip(const SbVec3f * const coords,const unsigned int numcoords,const int32_t * cind,const int nv,const SbBool ccw)767 SoNormalCache::generatePerStrip(const SbVec3f * const coords,
768                                 const unsigned int numcoords,
769                                 const int32_t * cind,
770                                 const int nv,
771                                 const SbBool ccw)
772 {
773 #if NORMALCACHE_DEBUG && COIN_DEBUG
774   SoDebugError::postInfo("SoNormalCache::generatePerStrip", "generating normals");
775 #endif
776 
777   this->clearGenerator();
778   PRIVATE(this)->indices.truncate(0);
779   PRIVATE(this)->normalArray.truncate(0, TRUE);
780 
781   const int32_t * cstart = cind;
782   const int32_t * endptr = cind + nv;
783 
784   const SbVec3f * c0, * c1, * c2;
785   SbVec3f n;
786 
787   SbBool flip = ccw;
788 
789   const int maxcoordidx = numcoords - 1;
790 
791   while (cind + 2 < endptr) {
792     if (cind[0] < 0 || cind[1] < 0 || cind[2] < 0 ||
793         cind[0] > maxcoordidx || cind[1] > maxcoordidx || cind[2] > maxcoordidx) {
794 #if COIN_DEBUG
795       SoDebugError::postWarning("SoNormalCache::generatePerStrip", "Erroneous "
796                                 "coordinate index detected (offset: %d, [%d %d %d]). Should be "
797                                 "within [0, %d].",
798                                 cind - cstart, *(cind), *(cind+1), *(cind+2), maxcoordidx);
799 #endif // COIN_DEBUG
800       // Insert dummy normal for robustness
801       SbVec3f dummynormal;
802       dummynormal.setValue(0.0f, 0.0f, 0.0f);
803       PRIVATE(this)->normalArray.append(dummynormal);
804 
805       // Skip to next possibly valid index
806       if (cind[0] < 0 || cind[0] > maxcoordidx) {
807         cind += 1;
808       }
809       else if (cind[1] < 0 || cind[1] > maxcoordidx) {
810         cind += 2;
811       }
812       else if (cind + 3 < endptr && (cind[2] < 0 || cind[2] > maxcoordidx)) {
813         cind += 3;
814       }
815       else {
816         cind += 3; // For robustness check after while loop
817         break;
818       }
819 
820       continue;
821     }
822 
823     flip = ccw;
824     c0 = &coords[*cind++];
825     c1 = &coords[*cind++];
826     c2 = &coords[*cind++];
827 
828     if (!flip)
829       n = (*c0 - *c1).cross(*c2 - *c1);
830     else
831       n = (*c2 - *c1).cross(*c0 - *c1);
832 
833     int idx = cind < endptr ? *cind++ : -1;
834     while (idx >= 0 && idx <= maxcoordidx) {
835       c0 = c1;
836       c1 = c2;
837       c2 = &coords[idx];
838       flip = !flip;
839       if (!flip)
840         n += (*c0 - *c1).cross(*c2 - *c1);
841       else
842         n += (*c2 - *c1).cross(*c0 - *c1);
843       idx = cind < endptr ? *cind++ : -1;
844     }
845 
846 #if COIN_DEBUG
847     if (idx > maxcoordidx) {
848       static uint32_t normgenerrors_strip = 0;
849       if (normgenerrors_strip < 1) {
850         SoDebugError::postWarning("SoNormalCache::generatePerStrip",
851                                   "Erroneous polygon specification in model. "
852                                   "Index out of bounds: %d. Max index: %d. "
853                                   "(this warning will be printed only once, "
854                                   "but there might be more errors).",
855                                   idx, maxcoordidx);
856       }
857       normgenerrors_strip++;
858     }
859 #endif // COIN_DEBUG
860 
861     if ((n.normalize() == 0.0f) && coin_debug_extra()) {
862       static uint32_t normgenerrors_strip = 0;
863       if (normgenerrors_strip < 1) {
864         SoDebugError::postWarning("SoNormalCache::generatePerStrip",
865                                   "Erroneous polygon specification in model.  "
866                                   "Unable to generate non-zero normal. Using "
867                                   "dummy normal. "
868                                   "(this warning will be printed only once, "
869                                   "but there might be more errors).");
870       }
871       normgenerrors_strip++;
872     }
873 
874     PRIVATE(this)->normalArray.append(n);
875   }
876 
877   if (endptr - cind > 0) {
878 #if COIN_DEBUG
879     SoDebugError::postWarning("SoNormalCache::generatePerStrip", "Strip did "
880                               "not end with a valid polygon. Too few points");
881 #endif // COIN_DEBUG
882     SbVec3f dummynormal;
883     dummynormal.setValue(0.0, 0.0, 0.0);
884     PRIVATE(this)->normalArray.append(dummynormal);
885   }
886 
887   if (PRIVATE(this)->normalArray.getLength()) {
888     PRIVATE(this)->normalData.normals = PRIVATE(this)->normalArray.getArrayPtr();
889     PRIVATE(this)->numNormals = PRIVATE(this)->normalArray.getLength();
890   }
891 
892 #if NORMALCACHE_DEBUG && COIN_DEBUG
893   SoDebugError::postInfo("SoNormalCache::generatePerStrip",
894                          "generated normals per strip: %p %d\n",
895                          PRIVATE(this)->normalData.normals, PRIVATE(this)->numNormals);
896 #endif
897 
898 }
899 
900 /*!
901   Generates PER_VERTEX normals for quad data.
902 */
903 void
generatePerVertexQuad(const SbVec3f * const coords,const unsigned int numcoords,const int vPerRow,const int vPerColumn,const SbBool ccw)904 SoNormalCache::generatePerVertexQuad(const SbVec3f * const coords,
905                                      const unsigned int numcoords,
906                                      const int vPerRow,
907                                      const int vPerColumn,
908                                      const SbBool ccw)
909 {
910 #if NORMALCACHE_DEBUG && COIN_DEBUG
911   SoDebugError::postInfo("SoNormalCache::generatePerVertexQuad", "generating normals");
912 #endif
913 
914   this->clearGenerator();
915   PRIVATE(this)->normalArray.truncate(0, TRUE);
916   // avoid reallocations in growable array by setting the buffer size first
917   PRIVATE(this)->normalArray.ensureCapacity(vPerRow * vPerColumn);
918 
919   SoNormalCache tempcache(NULL);
920   tempcache.generatePerFaceQuad(coords, numcoords, vPerRow, vPerColumn, ccw);
921   const SbVec3f * facenormals = tempcache.getNormals();
922   int numfacenormals = tempcache.getNum(); // Used for extra robustness
923 
924 #define IDX(r, c) ((r)*(vPerRow-1)+(c))
925 
926   for (int i = 0; i < vPerColumn; i++) {
927     for (int j = 0; j < vPerRow; j++) {
928       const int idx1 = IDX(i, j);
929       const int idx2 = IDX(i-1, j);
930       const int idx3 = IDX(i-1, j-1);
931       const int idx4 = IDX(i, j-1);
932 
933       SbVec3f n(0, 0, 0);
934 
935       if (i < vPerColumn-1 && j < vPerRow-1 && idx1 < numfacenormals) n += facenormals[idx1];
936       if (i > 0 && j < vPerRow-1 && idx2 < numfacenormals) n += facenormals[idx2];
937       if (j > 0 && i > 0 && idx3 < numfacenormals) n += facenormals[idx3];
938       if (j > 0 && i < vPerColumn-1 && idx4 < numfacenormals) n += facenormals[idx4];
939 
940       if ((n.normalize() == 0.0f) && coin_debug_extra()) {
941         static uint32_t normgenerrors_vertexquad = 0;
942         if (normgenerrors_vertexquad < 1) {
943           SoDebugError::postWarning("SoNormalCache::generatePerVertexQuad",
944                                     "Erroneous polygon specification in model. "
945                                     "Unable to generate valid normal, adding dummy. "
946                                     "(this warning will be printed only once, "
947                                     "but there might be more errors).");
948         }
949         normgenerrors_vertexquad++;
950       }
951       PRIVATE(this)->normalArray.append(ccw ? -n : n);
952     }
953   }
954 
955 #undef IDX
956 
957   PRIVATE(this)->normalData.normals = PRIVATE(this)->normalArray.getArrayPtr();
958   PRIVATE(this)->numNormals = PRIVATE(this)->normalArray.getLength();
959 
960 #if NORMALCACHE_DEBUG && COIN_DEBUG
961   SoDebugError::postInfo("SoNormalCache::generatePerVertexQuad",
962                          "generated normals per vertex quad: %p %d\n",
963                          PRIVATE(this)->normalData.normals, PRIVATE(this)->numNormals);
964 #endif
965 }
966 
967 /*!
968   Generates per face normals for quad data.
969 */
970 void
generatePerFaceQuad(const SbVec3f * const coords,const unsigned int numcoords,const int vPerRow,const int vPerColumn,const SbBool ccw)971 SoNormalCache::generatePerFaceQuad(const SbVec3f * const coords,
972                                    const unsigned int numcoords,
973                                    const int vPerRow,
974                                    const int vPerColumn,
975                                    const SbBool ccw)
976 {
977 #if NORMALCACHE_DEBUG && COIN_DEBUG
978   SoDebugError::postInfo("SoNormalCache::generatePerFaceQuad", "generating normals");
979 #endif
980 
981   this->clearGenerator();
982   PRIVATE(this)->normalArray.truncate(0, TRUE);
983   // avoid reallocations in growable array by setting the buffer size first
984   PRIVATE(this)->normalArray.ensureCapacity((vPerRow-1)*(vPerColumn-1));
985 
986 #if COIN_DEBUG
987   if (vPerRow <= 1 || vPerColumn <= 1 ||
988       static_cast<unsigned int>(vPerRow * vPerColumn) > numcoords) {
989 
990     SoDebugError::postWarning("SoNormalCache::generatePerFaceQuad", "Illegal "
991                               "facequad dimension: [%d %d] with %d coordinates "
992                               "available. verticesPerRow and verticesPerColumn "
993                               "should be > 1, and verticesPerRow * verticesPerColumn "
994                               "<= number of coordinates available.",
995                               vPerRow, vPerColumn, numcoords);
996   }
997 #endif // COIN_DEBUG
998 
999 #define IDX(r, c) ((r)*(vPerRow)+(c))
1000 
1001   for (int i = 0; i < vPerColumn-1; i++) {
1002     for (int j = 0; j < vPerRow-1; j++) {
1003       const unsigned int idx1 = IDX(i, j);
1004       const unsigned int idx2 = IDX(i+1, j);
1005       const unsigned int idx3 = IDX(i, j+1);
1006 
1007       if (idx2 < numcoords) { // Check the largest index only
1008         SbVec3f n = (coords[idx2] - coords[idx1]).cross(coords[idx3] - coords[idx1]);
1009 
1010         // Be robust when it comes to erroneously specified polygons.
1011         if ((n.normalize() == 0.0f) && coin_debug_extra())  {
1012           static uint32_t normgenerrors_facequad = 0;
1013           if (normgenerrors_facequad < 1) {
1014             SoDebugError::postWarning("SoNormalCache::generatePerFaceQuad",
1015                                       "Erroneous triangle specification in model "
1016                                       "(indices= [%d, %d, %d], "
1017                                       "coords=<%f, %f, %f>, <%f, %f, %f>, <%f, %f, %f>) "
1018                                       "(this warning will be printed only once, "
1019                                       "but there might be more errors).",
1020                                       idx1, idx2, idx3,
1021                                       coords[idx1][0], coords[idx1][1], coords[idx1][2],
1022                                       coords[idx2][0], coords[idx2][1], coords[idx2][2],
1023                                       coords[idx3][0], coords[idx3][1], coords[idx3][2]);
1024           }
1025           normgenerrors_facequad++;
1026         }
1027 
1028         PRIVATE(this)->normalArray.append(ccw ? -n : n);
1029       }
1030       else {
1031         // Generate normals even for invalid input
1032         SbVec3f dummynormal(0.0, 0.0, 0.0);
1033         PRIVATE(this)->normalArray.append(ccw ? -dummynormal : dummynormal);
1034       }
1035     }
1036   }
1037 
1038 #undef IDX
1039 
1040   if (PRIVATE(this)->normalArray.getLength()) {
1041     PRIVATE(this)->normalData.normals = PRIVATE(this)->normalArray.getArrayPtr();
1042     PRIVATE(this)->numNormals = PRIVATE(this)->normalArray.getLength();
1043   }
1044 
1045 #if NORMALCACHE_DEBUG && COIN_DEBUG
1046   SoDebugError::postInfo("SoNormalCache::generatePerFaceQuad",
1047                          "generated normals per face quad: %p %d\n",
1048                          PRIVATE(this)->normalData.normals, PRIVATE(this)->numNormals);
1049 #endif
1050 
1051 }
1052 
1053 /*!
1054   Generates per row normals for quad data.
1055 */
1056 void
generatePerRowQuad(const SbVec3f * const coords,const unsigned int numcoords,const int vPerRow,const int vPerColumn,const SbBool ccw)1057 SoNormalCache::generatePerRowQuad(const SbVec3f * const coords,
1058                                   const unsigned int numcoords,
1059                                   const int vPerRow,
1060                                   const int vPerColumn,
1061                                   const SbBool ccw)
1062 {
1063 #if NORMALCACHE_DEBUG && COIN_DEBUG
1064   SoDebugError::postInfo("SoNormalCache::generatePerRowQuad", "generating normals");
1065 #endif
1066 
1067   this->clearGenerator();
1068   PRIVATE(this)->normalArray.truncate(0, TRUE);
1069   SbVec3f n;
1070 
1071 #if COIN_DEBUG
1072   if (vPerRow <= 1 || vPerColumn <= 1 ||
1073       static_cast<unsigned int>(vPerRow * vPerColumn) > numcoords) {
1074     SoDebugError::postWarning("SoNormalCache::generatePerRowQuad", "Illegal "
1075                               "facequad dimension: [%d %d] with %d coordinates "
1076                               "available. verticesPerRow and verticesPerColumn "
1077                               "should be > 1, and verticesPerRow * verticesPerColumn "
1078                               "<= number of coordinates available.",
1079                               vPerRow, vPerColumn, numcoords);
1080   }
1081 #endif // COIN_DEBUG
1082 
1083 #define IDX(r, c) ((r)*(vPerRow)+(c))
1084 
1085   for (int i = 0; i < vPerColumn-1; i++) {
1086     n.setValue(0.0f, 0.0f, 0.0f);
1087     for (int j = 0; j < vPerRow-1; j++) {
1088       const unsigned int idx1 = IDX(i, j);
1089       const unsigned int idx2 = IDX(i+1, j);
1090       const unsigned int idx3 = IDX(i, j+1);
1091 
1092       if (idx2 < numcoords) { // Check largest index only
1093         n += (coords[idx2] - coords[idx1]).cross(coords[idx3] - coords[idx1]);
1094       }
1095     }
1096 
1097     // Be robust when it comes to erroneously specified polygons.
1098     if ((n.normalize() == 0.0f) && coin_debug_extra()) {
1099       static uint32_t normgenerrors_rowquad = 0;
1100       if (normgenerrors_rowquad < 1) {
1101         SoDebugError::postWarning("SoNormalCache::generatePerRowQuad",
1102                                   "Erroneous polygon specification in model. "
1103                                   "Unable to generate valid normal, adding null vector. "
1104                                   "(this warning will be printed only once, "
1105                                   "but there might be more errors).");
1106       }
1107       normgenerrors_rowquad++;
1108     }
1109     PRIVATE(this)->normalArray.append(ccw ? -n : n);
1110   }
1111 
1112 #undef IDX
1113 
1114   if (PRIVATE(this)->normalArray.getLength()) {
1115     PRIVATE(this)->normalData.normals = PRIVATE(this)->normalArray.getArrayPtr();
1116     PRIVATE(this)->numNormals = PRIVATE(this)->normalArray.getLength();
1117   }
1118 
1119 #if NORMALCACHE_DEBUG && COIN_DEBUG
1120   SoDebugError::postInfo("SoNormalCache::generatePerRowQuad",
1121                          "generated normals per row quad: %p %d\n",
1122                          PRIVATE(this)->normalData.normals, PRIVATE(this)->numNormals);
1123 #endif
1124 
1125 }
1126 
1127 //
1128 // frees generator and resets normal data.
1129 //
1130 void
clearGenerator(void)1131 SoNormalCache::clearGenerator(void)
1132 {
1133   if (PRIVATE(this)->numNormals == 0 && PRIVATE(this)->normalData.generator) {
1134     delete PRIVATE(this)->normalData.generator;
1135   }
1136   PRIVATE(this)->normalData.normals = NULL;
1137   PRIVATE(this)->numNormals = 0;
1138 }
1139 
1140 #undef NORMAL_EPSILON
1141 #undef NORMALCACHE_DEBUG
1142 #undef PRIVATE
1143