Debian Codegraph @

apps/tools/ivnorm/Faces.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 //
38 // Some convenient routines for doing stuff with faces.
39 //
40
41 #include <assert.h>
42 #include <cmath>
43 #include "Faces.h"
44 #include "Edges.h"
45
46 #include <Inventor/nodes/SoNormal.h>
47 #include <Inventor/nodes/SoIndexedFaceSet.h>
48
49 //
50 // Find a face's normal, assuming its vertices are in
51 // counter-clockwise order.
52 //
53 void
54 Face::findNormal(const SbVec3f *verts)
55 {
56 // Use Newell's method to find face normal. See Newman & Sproull,
57 // pg. 499. This is better than the three-point cross-product
58 // method.
59
60 normal[0] = normal[1] = normal[2] = 0.0;
61
62 for (int i = 0; i < nv; i++)
63 {
64 int iv1 = int(v[i]);
65 int iv2 = int(v[(i+1)%nv]);
66
67 if (iv1 == iv2) continue;
68
69 SbVec3f v1 = verts[iv1];
70 SbVec3f v2 = verts[iv2];
71
72 normal[0] += (v1[1] - v2[1])*(v1[2] + v2[2]);
73 normal[1] += (v1[2] - v2[2])*(v1[0] + v2[0]);
74 normal[2] += (v1[0] - v2[0])*(v1[1] + v2[1]);
75 }
76 if (orientation == Face::CW) normal.negate();
77
78 if (normal.length() < 0.00001)
79 {
80 degenerate = 1;
81 }
82 else
83 {
84 normal.normalize();
85 degenerate = 0;
86 }
87 }
88
89 //
90 // Set this face's orientation relative to a given edge
91 //
92 void
93 Face::orientFace(int v1, int v2)
94 {
95 int v1_i;
96
97 // First, figure out which index is v1
98
99 for (v1_i = 0; v1_i < nv; v1_i++)
100 {
101 if (v[v1_i] == v1)
102 {
103 // Now just have to determine whether v2 is the next or previous
104 // vertex.
105 if (v[(v1_i+1)%nv] == v2) // Next
106 {
107 orientation = CCW;
108 break;
109 }
110 else if (v[(v1_i+nv-1)%nv] == v2) // Previous
111 {
112 orientation = CW;
113 break;
114 }
115 // Otherwise, keep on checking; we may be traversing a
116 // degenerate edge or strange facet where vertices are repeated.
117 }
118 }
119 assert(v1_i != nv); // Assertion: we found it.
120 }
121
122 FaceList::FaceList()
123 {
124 verts = NULL;
125 faceSet = NULL;
126 ed = NULL;
127 vd = NULL;
128 convex = TRUE;
129 solid = TRUE;
130 verbose = FALSE;
131 }
132
133 FaceList::FaceList(const SbVec3f *v, EdgeDict *e)
134 {
135 verts = v;
136 ed = e;
137 vd = NULL;
138 faceSet = NULL;
139 convex = TRUE;
140 solid = TRUE;
141 verbose = FALSE;
142 }
143
144 FaceList::FaceList(const SbVec3f *v, SoIndexedFaceSet *fs, SbBool vrb)
145 {
146 verts = v;
147 faceSet = fs; fs->ref();
148 convex = TRUE;
149 solid = TRUE;
150 vd = NULL;
151 verbose = vrb;
152
153 ed = new EdgeDict(1000);
154
155 SoMFInt32 *coord_indices = &faceSet->coordIndex;
156 int ni = coord_indices->getNum();
157
158 int32_t *indices = coord_indices->startEditing();
159
160 int start_o_face = 0;
161
162 // Now fill in face and edge structures
163 int n_degenerate_faces = 0;
164 int n_degenerate_edges = 0;
165 for (int i = 0, ct=0; i < coord_indices->getNum(); i++)
166 {
167 if (indices[i] == SO_END_FACE_INDEX
168 || i == coord_indices->getNum()-1)
169 {
170 Face *f = new Face;
171 if (indices[i] == SO_END_FACE_INDEX)
172 f->nv = i - start_o_face;
173 else
174 f->nv = i - start_o_face + 1;
175 f->v = indices+start_o_face;
176 f->vct = ct; // first vertex index count for this face.
177 f->vidx = start_o_face;
178 f->vn = NULL;
179 f->orientation = Face::UNKNOWN;
180
181 f->findNormal(verts);
182 if (f->degenerate)
183 {
184 ++n_degenerate_faces;
185 f->orientation = Face::CCW;
186 }
187 else for (int j = 0; j < f->nv; j++)
188 {
189 int i1 = (int)f->v[j];
190 int i2 = (int)f->v[(j+1)%f->nv];
191 if (i1 != i2)
192 ed->Add(f, i1, i2);
193 else ++n_degenerate_edges;
194 }
195
196 start_o_face = i+1;
197
198 append(f);
199 }
200 else
201 ct++; // "ct" counts the non-END entries, for use
202 // as the index into a per_vertex normal set
203 }
204 if (n_degenerate_faces != 0)
205 {
206 if (verbose) fprintf(stderr, "Detected %d degenerate faces\n",
207 n_degenerate_faces);
208 }
209 if (n_degenerate_edges != 0)
210 {
211 if (verbose) fprintf(stderr, "Detected %d degenerate edges\n",
212 n_degenerate_edges);
213 }
214 }
215
216 void
217 FaceList::append(Face *f)
218 {
219 SbPList::append((void *)f);
220 }
221
222 //
223 // This isn't accurate; we just use it to figure out if the volume is
224 // positive or negative to try to figure out if the surface is
225 // oriented correctly.
226 //
227 float
228 FaceList::volume()
229 {
230 int i, j;
231
232 int total_v = 0;
233 SbVec3f average(0.0, 0.0, 0.0);
234
235 for (j = 0; j < getLength(); j++)
236 {
237 Face *f = (*this)[j];
238 if (f->degenerate) continue;
239
240 for (i = 0; i < f->nv; i++)
241 {
242 average += verts[f->v[i]];
243 ++total_v;
244 }
245 }
246 average /= (float) total_v;
247
248 float result = 0.0;
249
250 for (j = 0; j < getLength(); j++)
251 {
252 Face *f = (*this)[j];
253 if (f->degenerate) continue;
254
255 for (i = 1; i < f->nv-1; i++)
256 {
257 SbVec3f v1 = verts[f->v[0]] - average;
258 SbVec3f v2 = verts[f->v[i]] - average;
259 SbVec3f v3 = verts[f->v[i+1]] - average;
260
261 float t = (v1.cross(v2)).dot(v3);
262 if (f->orientation == Face::CCW)
263 {
264 result += t;
265 }
266 else if (f->orientation == Face::CW)
267 {
268 result -= t;
269 }
270 else
271 {
272 assert(0);
273 }
274 }
275 }
276 return result;
277 }
278
279 FaceList::~FaceList()
280 {
281 if (faceSet != NULL)
282 {
283 delete ed;
284 faceSet->coordIndex.finishEditing();
285 faceSet->unref();
286 for (int i = 0; i < getLength(); i++)
287 {
288 delete (*this)[i];
289 }
290 truncate(0);
291 }
292
293 if (vd)
294 delete [] vd;
295 }
296
297 void
298 FaceList::reverseOrientation()
299 {
300 for (int i = 0; i < getLength(); i++)
301 {
302 Face *f = (*this)[i];
303
304 if (f->orientation == Face::CW)
305 {
306 f->orientation = Face::CCW;
307 }
308 else if (f->orientation == Face::CCW)
309 {
310 f->orientation = Face::CW;
311 }
312 else
313 {
314 assert(0);
315 }
316 }
317 }
318
319 //
320 // This routine works by starting with a 'seed' face and assumes that
321 // its orientation is correct. It then visits all neighboring faces
322 // and makes their orientations consistent with the seed face's.
323 //
324 void
325 FaceList::findOrientation()
326 {
327 orientOutward();
328
329 correctOrientation();
330 }
331
332 void
333 FaceList::findFacetNormals(SoNormal *n)
334 {
335 assert(n != NULL && faceSet != NULL);
336
337 for (int i = 0; i < getLength(); i++)
338 {
339 (*this)[i]->findNormal(verts);
340 n->vector.set1Value(i, (*this)[i]->normal);
341 }
342 }
343
344 //
345 // Assuming that the correct orientation of a 'seed' face has been
346 // discovered, this routine figures out the correct orientation for
347 // all faces connected to that face.
348 //
349 void
350 FaceList::recursivelyOrient(Face *seed)
351 {
352 int i, j;
353 FaceList others;
354
355 if (seed->degenerate) return;
356
357 for (i = 0; i < seed->nv; i++)
358 {
359 j = (i+1)%seed->nv;
360
361 // Find other faces attached to this edge
362 ed->OtherFaces(seed, seed->v[i], seed->v[j], others);
363
364 for (int f = 0; f < others.getLength(); f++)
365 {
366 if (others[f]->orientation == Face::UNKNOWN)
367 {
368 if (seed->orientation == Face::CW)
369 others[f]->orientFace((int)seed->v[i], (int)seed->v[j]);
370 else if (seed->orientation == Face::CCW)
371 others[f]->orientFace((int)seed->v[j], (int)seed->v[i]);
372 else assert(0); // Should never happen
373
374 append(others[f]);
375 recursivelyOrient(others[f]);
376 }
377 }
378 }
379 }
380
381 //
382 // This routine takes a collection of faces and trys to figure out
383 // which way is out.
384 //
385 void
386 FaceList::orientOutward()
387 {
388 // int num_fragments = 0;
389
390 //
391 // Loop through all the faces; if we find one whose orientation
392 // hasn't been determined, will try to determine its orientation.
393 //
394 for (int i = 0; i < getLength(); i++)
395 {
396 Face *f = (*this)[i];
397 if (f->orientation != Face::UNKNOWN) continue;
398
399 // First, take a wild guess...
400 f->orientation = Face::CCW;
401
402 // ++num_fragments;
403
404 FaceList fragment(verts, ed);
405 fragment.append(f);
406
407 // Now recursively orient the faces connected to this face.
408 fragment.recursivelyOrient(f);
409
410 // Take a reasonable guess for whether or not that first face
411 // is oriented correctly:
412 float v = fragment.volume();
413
414 if (v*v < 0.00001*0.00001) // FLAT
415 {
416 // Do something...
417 // fprintf(stderr, "Flat fragment found\n");
418 }
419 else if (v < 0.0)
420 fragment.reverseOrientation();
421 }
422 // fprintf(stderr, "There were %d fragments\n", num_fragments);
423 }
424
425 void
426 FaceList::correctOrientation()
427 {
428 for (int i = 0; i < getLength(); i++)
429 {
430 Face *f = (*this)[i];
431 if (f->orientation == Face::CW)
432 {
433 for (int j = 0; j < f->nv/2; j++)
434 {
435 int k = f->nv - j - 1;
436 int32_t t = f->v[j];
437 f->v[j] = f->v[k];
438 f->v[k] = t;
439 }
440 f->orientation = Face::CCW;
441 }
442 }
443 }
444
445 void
446 FaceList::findShapeInfo()
447 {
448 FaceList others;
449 convex = TRUE;
450 solid = TRUE;
451
452 for (int k=0; k< getLength(); k++) {
453
454 Face *f = (*this)[k];
455 if (f->degenerate)
456 continue;
457
458 // If a face has more than 3 vertices, assume it's convex.
459 if (f->nv > 3) {
460 convex = FALSE;
461 }
462
463 // run through the edges of the face
464 for (int i = 0; i < f->nv; i++) {
465
466 int j = (i+1)%f->nv;
467
468 // Find other faces attached to this edge
469 ed->OtherFaces(f, f->v[i], f->v[j], others);
470
471 if (others.getLength() == 0) {
472 solid = FALSE;
473 break;
474 }
475 }
476
477 // we can quit searching if we've found
478 // out all there is to know.
479 if (!convex && !solid)
480 break;
481 }
482 }
483
484
485 int
486 FaceList::findBodies()
487 {
488 buildVertexDict();
489
490 // clear all faces
491 int i;
492 for (i=0; i< getLength(); i++)
493 (*this)[i]->body = -1;
494
495 int bodyN = 0;
496
497 for (i=0; i<getLength(); i++) {
498
499 Face *f = (*this)[i];
500
501 // each time we find an unmarked face,
502 // it's on a previously-undiscovered body
503 if (f->body == -1) {
504 f->body = bodyN++;
505 recursivelyMarkBody(f);
506 }
507 }
508
509 return bodyN;
510 }
511
512 void
513 FaceList::recursivelyMarkBody(Face *f)
514 {
515 int i;
516
517 assert(f->body != -1); // only recurse on marked faces
518
519 for (i = 0; i < f->nv; i++)
520 {
521 // get list of faces sharing this vertex
522 const FaceList &faces = vd[f->v[i]];
523
524 for (int j=0; j<faces.getLength(); j++) {
525 if (faces[j]->body == f->body) {
526 ; // nothing to do if the other face is already part of this body
527 }
528 else if (faces[j]->body == -1) {
529 // the other face is still unmarked, so mark it and recurse
530 faces[j]->body = f->body;
531 recursivelyMarkBody(faces[j]);
532 }
533 else {
534 assert(0); // vertex dictionary isn't commutative??
535 }
536 }
537 }
538 }
539
540 void
541 FaceList::extractBody(int b,
542 int &bnf, int32_t *fNewFromOld, int32_t *fOldFromNew,
543 int &bnv, int32_t *vNewFromOld, int32_t *vOldFromNew)
544 {
545 // build the face maps
546 int f, bf;
547 for (f=0, bf=0; f < getLength(); f++) {
548 if ((*this)[f]->body == b) {
549 // f is the old face index
550 // bf is the new face index
551 fNewFromOld[f] = bf;
552 fOldFromNew[bf] = f;
553 bf++;
554 }
555 }
556 bnf = bf;
557
558 // build the vertex maps
559 int ni, i;
560 for (ni=0, i=0; i < vdSize; i++) {
561 const FaceList &faces = vd[i];
562 SbBool isInBody = FALSE;
563 for (int j = 0; j < faces.getLength(); j++) if (faces[j]->body == b) {
564 isInBody = TRUE;
565 break;
566 }
567 if (isInBody) {
568 // i is the old vertex index
569 // ni is the new vertex index
570 vNewFromOld[i] = ni;
571 vOldFromNew[ni] = i;
572 ni++;
573 }
574 else
575 vNewFromOld[i] = -1;
576 }
577 bnv = ni;
578 }
579
580
581 void
582 FaceList::buildVertexDict()
583 {
584 // already built?
585 if (vd) return;
586
587 int biggest_index = 0;
588 int i;
589 for (i = 0; i < getLength(); i++) {
590 Face *f = (*this)[i];
591 for (int j = 0; j < f->nv; j++) {
592 if (f->v[j] > biggest_index) biggest_index = f->v[j];
593 }
594 }
595
596 vd = new FaceList[biggest_index+1];
597 vdSize = biggest_index+1;
598
599 // Build list of faces around each vertex
600 for (i = 0; i < getLength(); i++)
601 {
602 Face *f = (*this)[i];
603
604 for (int j = 0; j < f->nv; j++)
605 {
606 vd[f->v[j]].append(f);
607 }
608 }
609
610 }
611
612
613 void
614 FaceList::findVertexNormals(SoNormal *norm, SoIndexedFaceSet *ifs,
615 float creaseAngle)
616 {
617 buildVertexDict();
618
619 // Initialize all faces
620 int i;
621 for (i = 0; i < getLength(); i++)
622 {
623 Face *f = (*this)[i];
624
625 f->findNormal(verts);
626 f->vn = new int32_t[f->nv];
627 for (int j = 0; j < f->nv; j++)
628 {
629 f->vn[j] = -1;
630 }
631 }
632
633 // Finally, create normals
634 norm->vector.deleteValues(0); // get rid of default value
635 int count = 0;
636 for (i = 0; i < getLength(); i++)
637 {
638 Face *f = (*this)[i];
639
640 for (int j = 0; j < f->nv; j++)
641 {
642 if (f->degenerate)
643 {
644 f->vn[j] = getIdx(norm->vector, SbVec3f(0,0,0));
645 }
646 else if (f->vn[j] == -1)
647 {
648 SbVec3f t;
649 vd[f->v[j]].averageNormals(norm->vector, f->normal,
650 creaseAngle,
651 f->v[j]);
652 }
653 ifs->normalIndex.set1Value(count, f->vn[j]);
654 ++count;
655 }
656 ifs->normalIndex.set1Value(count, SO_END_FACE_INDEX);
657 ++count;
658 }
659 }
660
661 //
662 // get the index of a vector in a SFVec3f;
663 // adds the vector if needed.
664 //
665 // use: private
666 //
667
668 int
669 FaceList::getIdx(SoMFVec3f &mf, const SbVec3f &p)
670 {
671 int n = mf.getNum();
672 SbVec3f *v = mf.startEditing();
673
674 // search from the end, since recent vectors are likely to be reused
675 for (int i=n-1; i>=0; i--)
676 if (p == v[i]) {
677 mf.finishEditing();
678 return i;
679 }
680
681 mf.finishEditing();
682 mf.set1Value(n, p);
683 return n;
684 }
685
686 //
687 // Average the normals around a vertex to get a vertex normal. Skip
688 // faces that are too different (as defined by creaseAngle)
689 //
690 void
691 FaceList::averageNormals(SoMFVec3f &norms, SbVec3f &reference,
692 float creaseAngle, int whichV)
693 {
694 SbVec3f average;
695 average.setValue(0.0, 0.0, 0.0);
696
697 float ca = cos(creaseAngle);
698
699 int num = 0;
700 int max = getLength();
701
702 // first, loop through and compute the average
703 int i;
704 for (i = 0; i < max; i++)
705 {
706 Face *f = (*this)[i];
707 if (f->degenerate) continue;
708
709 float dp = reference.dot(f->normal);
710 if (dp >= ca)
711 {
712 average += f->normal; ++num;
713
714 }
715 }
716 assert(num != 0);
717 average /= (float)num;
718 average.normalize();
719
720 // insert the average into the mfield
721 int index = getIdx(norms, average);
722
723 // loop through again and insert the average's index
724 // into the face arrays
725 for (i = 0; i < max; i++)
726 {
727 Face *f = (*this)[i];
728 if (f->degenerate) continue;
729
730 float dp = reference.dot(f->normal);
731 if (dp >= ca)
732 {
733 for (int j = 0; j < f->nv; j++)
734 {
735 if (f->v[j] == whichV)
736 f->vn[j] = index;
737 }
738 }
739 }
740 assert(num != 0);
741 average /= (float)num;
742 average.normalize();
743 }