1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 #pragma once
18
19 /** \file
20 * \ingroup freestyle
21 * \brief Classes to define a Winged Edge data structure.
22 */
23
24 #include <iterator>
25 #include <vector>
26
27 #include "../geometry/Geom.h"
28
29 #include "../scene_graph/FrsMaterial.h"
30
31 #include "../system/FreestyleConfig.h"
32
33 #include "BLI_math.h"
34
35 #ifdef WITH_CXX_GUARDEDALLOC
36 # include "MEM_guardedalloc.h"
37 #endif
38
39 using namespace std;
40
41 namespace Freestyle {
42
43 using namespace Geometry;
44
45 /**********************************
46 * *
47 * *
48 * WVertex *
49 * *
50 * *
51 **********************************/
52
53 class WOEdge;
54 class WEdge;
55 class WShape;
56 class WFace;
57
58 class WVertex {
59 protected:
60 int _Id; // an identificator
61 Vec3f _Vertex;
62 vector<WEdge *> _EdgeList;
63 WShape *_Shape; // the shape to which the vertex belongs
64 bool _Smooth; // flag to indicate whether the Vertex belongs to a smooth edge or not
65 short _Border; // 1 -> border, 0 -> no border, -1 -> not set
66
67 public:
68 void *userdata; // designed to store specific user data
WVertex(const Vec3f & v)69 inline WVertex(const Vec3f &v)
70 {
71 _Id = 0;
72 _Vertex = v;
73 userdata = NULL;
74 _Shape = NULL;
75 _Smooth = true;
76 _Border = -1;
77 }
78
79 /*! Copy constructor */
80 WVertex(WVertex &iBrother);
81 virtual WVertex *duplicate();
~WVertex()82 virtual ~WVertex()
83 {
84 }
85
86 /*! accessors */
GetVertex()87 inline Vec3f &GetVertex()
88 {
89 return _Vertex;
90 }
91
GetEdges()92 inline vector<WEdge *> &GetEdges()
93 {
94 return _EdgeList;
95 }
96
GetId()97 inline int GetId()
98 {
99 return _Id;
100 }
101
shape()102 inline WShape *shape() const
103 {
104 return _Shape;
105 }
106
isSmooth()107 inline bool isSmooth() const
108 {
109 return _Smooth;
110 }
111
112 bool isBoundary();
113
114 /*! modifiers */
setVertex(const Vec3f & v)115 inline void setVertex(const Vec3f &v)
116 {
117 _Vertex = v;
118 }
119
setEdges(const vector<WEdge * > & iEdgeList)120 inline void setEdges(const vector<WEdge *> &iEdgeList)
121 {
122 _EdgeList = iEdgeList;
123 }
124
setId(int id)125 inline void setId(int id)
126 {
127 _Id = id;
128 }
129
setShape(WShape * iShape)130 inline void setShape(WShape *iShape)
131 {
132 _Shape = iShape;
133 }
134
setSmooth(bool b)135 inline void setSmooth(bool b)
136 {
137 _Smooth = b;
138 }
139
setBorder(bool b)140 inline void setBorder(bool b)
141 {
142 if (b) {
143 _Border = 1;
144 }
145 else {
146 _Border = 0;
147 }
148 }
149
150 /*! Adds an edge to the edges list */
151 void AddEdge(WEdge *iEdge);
152
ResetUserData()153 virtual void ResetUserData()
154 {
155 userdata = NULL;
156 }
157
158 public:
159 /*! Iterator to iterate over a vertex incoming edges in the CCW order*/
160 #if defined(__GNUC__) && (__GNUC__ < 3)
161 class incoming_edge_iterator : public input_iterator<WOEdge *, ptrdiff_t>
162 #else
163 class incoming_edge_iterator : public iterator<input_iterator_tag, WOEdge *, ptrdiff_t>
164 #endif
165 {
166 private:
167 WVertex *_vertex;
168 //
169 WOEdge *_begin;
170 WOEdge *_current;
171
172 public:
173 #if defined(__GNUC__) && (__GNUC__ < 3)
incoming_edge_iterator()174 inline incoming_edge_iterator() : input_iterator<WOEdge *, ptrdiff_t>()
175 {
176 }
177 #else
178 inline incoming_edge_iterator() : iterator<input_iterator_tag, WOEdge *, ptrdiff_t>()
179 {
180 }
181 #endif
~incoming_edge_iterator()182 virtual ~incoming_edge_iterator(){}; // soc
183
184 protected:
185 friend class WVertex;
incoming_edge_iterator(WVertex * iVertex,WOEdge * iBegin,WOEdge * iCurrent)186 inline incoming_edge_iterator(WVertex *iVertex, WOEdge *iBegin, WOEdge *iCurrent)
187 #if defined(__GNUC__) && (__GNUC__ < 3)
188 : input_iterator<WOEdge *, ptrdiff_t>()
189 #else
190 : iterator<input_iterator_tag, WOEdge *, ptrdiff_t>()
191 #endif
192 {
193 _vertex = iVertex;
194 _begin = iBegin;
195 _current = iCurrent;
196 }
197
198 public:
incoming_edge_iterator(const incoming_edge_iterator & iBrother)199 inline incoming_edge_iterator(const incoming_edge_iterator &iBrother)
200 #if defined(__GNUC__) && (__GNUC__ < 3)
201 : input_iterator<WOEdge *, ptrdiff_t>(iBrother)
202 #else
203 : iterator<input_iterator_tag, WOEdge *, ptrdiff_t>(iBrother)
204 #endif
205 {
206 _vertex = iBrother._vertex;
207 _begin = iBrother._begin;
208 _current = iBrother._current;
209 }
210
211 public:
212 // operators
213 // operator corresponding to ++i
214 virtual incoming_edge_iterator &operator++()
215 {
216 increment();
217 return *this;
218 }
219
220 // operator corresponding to i++
221 virtual incoming_edge_iterator operator++(int)
222 {
223 incoming_edge_iterator tmp = *this;
224 increment();
225 return tmp;
226 }
227
228 // comparibility
229 virtual bool operator!=(const incoming_edge_iterator &b) const
230 {
231 return ((_current) != (b._current));
232 }
233
234 virtual bool operator==(const incoming_edge_iterator &b) const
235 {
236 return ((_current) == (b._current));
237 }
238
239 // dereferencing
240 virtual WOEdge *operator*();
241 // virtual WOEdge **operator->();
242 protected:
243 virtual void increment();
244
245 #ifdef WITH_CXX_GUARDEDALLOC
246 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WVertex:incoming_edge_iterator")
247 #endif
248 };
249
250 /*! Iterator to iterate over a vertex faces in the CCW order */
251 #if defined(__GNUC__) && (__GNUC__ < 3)
252 class face_iterator : public input_iterator<WFace *, ptrdiff_t>
253 #else
254 class face_iterator : public iterator<input_iterator_tag, WFace *, ptrdiff_t>
255 #endif
256 {
257 private:
258 incoming_edge_iterator _edge_it;
259
260 public:
261 #if defined(__GNUC__) && (__GNUC__ < 3)
face_iterator()262 inline face_iterator() : input_iterator<WFace *, ptrdiff_t>()
263 {
264 }
265 #else
266 inline face_iterator() : iterator<input_iterator_tag, WFace *, ptrdiff_t>()
267 {
268 }
269 #endif
~face_iterator()270 virtual ~face_iterator(){}; // soc
271
272 protected:
273 friend class WVertex;
face_iterator(incoming_edge_iterator it)274 inline face_iterator(incoming_edge_iterator it)
275 #if defined(__GNUC__) && (__GNUC__ < 3)
276 : input_iterator<WFace *, ptrdiff_t>()
277 #else
278 : iterator<input_iterator_tag, WFace *, ptrdiff_t>()
279 #endif
280 {
281 _edge_it = it;
282 }
283
284 public:
face_iterator(const face_iterator & iBrother)285 inline face_iterator(const face_iterator &iBrother)
286 #if defined(__GNUC__) && (__GNUC__ < 3)
287 : input_iterator<WFace *, ptrdiff_t>(iBrother)
288 #else
289 : iterator<input_iterator_tag, WFace *, ptrdiff_t>(iBrother)
290 #endif
291 {
292 _edge_it = iBrother._edge_it;
293 }
294
295 public:
296 // operators
297 // operator corresponding to ++i
298 virtual face_iterator &operator++()
299 {
300 increment();
301 return *this;
302 }
303
304 // operator corresponding to i++
305 virtual face_iterator operator++(int)
306 {
307 face_iterator tmp = *this;
308 increment();
309 return tmp;
310 }
311
312 // comparibility
313 virtual bool operator!=(const face_iterator &b) const
314 {
315 return ((_edge_it) != (b._edge_it));
316 }
317
318 virtual bool operator==(const face_iterator &b) const
319 {
320 return ((_edge_it) == (b._edge_it));
321 }
322
323 // dereferencing
324 virtual WFace *operator*();
325 // virtual WOEdge **operator->();
326
327 protected:
increment()328 inline void increment()
329 {
330 ++_edge_it;
331 }
332
333 #ifdef WITH_CXX_GUARDEDALLOC
334 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WVertex:face_iterator")
335 #endif
336 };
337
338 public:
339 /*! iterators access */
340 virtual incoming_edge_iterator incoming_edges_begin();
341 virtual incoming_edge_iterator incoming_edges_end();
342
faces_begin()343 virtual face_iterator faces_begin()
344 {
345 return face_iterator(incoming_edges_begin());
346 }
347
faces_end()348 virtual face_iterator faces_end()
349 {
350 return face_iterator(incoming_edges_end());
351 }
352
353 #ifdef WITH_CXX_GUARDEDALLOC
354 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WVertex")
355 #endif
356 };
357
358 /**********************************
359 * *
360 * *
361 * WOEdge *
362 * *
363 * *
364 **********************************/
365
366 class WFace;
367 class WEdge;
368
369 class WOEdge {
370 protected:
371 #if 0
372 WOEdge *_paCWEdge; // edge reached when traveling clockwise on aFace from the edge
373 WOEdge *_pbCWEdge; // edge reached when traveling clockwise on bFace from the edge
374 WOEdge *_paCCWEdge; // edge reached when traveling counterclockwise on aFace from the edge
375 WOEdge *_pbCCWEdge; // edge reached when traveling counterclockwise on bFace from the edge
376 #endif
377 WVertex *_paVertex; // starting vertex
378 WVertex *_pbVertex; // ending vertex
379 WFace *_paFace; // when following the edge, face on the right
380 WFace *_pbFace; // when following the edge, face on the left
381 WEdge *_pOwner; // Edge
382
383 Vec3f _vec;
384 float _angle;
385
386 public:
387 void *userdata;
388
WOEdge()389 inline WOEdge()
390 {
391 #if 0
392 _paCWEdge = NULL;
393 _pbCWEdge = NULL;
394 _paCCWEdge = NULL;
395 _pbCCWEdge = NULL;
396 #endif
397 _paVertex = NULL;
398 _pbVertex = NULL;
399 _paFace = NULL;
400 _pbFace = NULL;
401 _pOwner = NULL;
402 userdata = NULL;
403 }
404
~WOEdge()405 virtual ~WOEdge(){}; // soc
406
407 /*! copy constructor */
408 WOEdge(WOEdge &iBrother);
409 virtual WOEdge *duplicate();
410
411 /*! accessors */
412 #if 0
413 inline WOEdge *GetaCWEdge()
414 {
415 return _paCWEdge;
416 }
417
418 inline WOEdge *GetbCWEdge()
419 {
420 return _pbCWEdge;
421 }
422
423 inline WOEdge *GetaCCWEdge()
424 {
425 return _paCCWEdge;
426 }
427
428 inline WOEdge *GetbCCWEdge()
429 {
430 return _pbCCWEdge;
431 }
432 #endif
433
GetaVertex()434 inline WVertex *GetaVertex()
435 {
436 return _paVertex;
437 }
438
GetbVertex()439 inline WVertex *GetbVertex()
440 {
441 return _pbVertex;
442 }
443
GetaFace()444 inline WFace *GetaFace()
445 {
446 return _paFace;
447 }
448
GetbFace()449 inline WFace *GetbFace()
450 {
451 return _pbFace;
452 }
453
GetOwner()454 inline WEdge *GetOwner()
455 {
456 return _pOwner;
457 }
458
GetVec()459 inline const Vec3f &GetVec()
460 {
461 return _vec;
462 }
463
GetAngle()464 inline const float GetAngle()
465 {
466 return _angle;
467 }
468
469 /*! modifiers */
470 #if 0
471 inline void SetaCWEdge(WOEdge *pe)
472 {
473 _paCWEdge = pe;
474 }
475
476 inline void SetbCWEdge(WOEdge *pe)
477 {
478 _pbCWEdge = pe;
479 }
480
481 inline void SetaCCWEdge(WOEdge *pe)
482 {
483 _paCCWEdge = pe;
484 }
485
486 inline void SetbCCCWEdge(WOEdge *pe)
487 {
488 _pbCCWEdge = pe;
489 }
490 #endif
491
492 inline void setVecAndAngle();
493
setaVertex(WVertex * pv)494 inline void setaVertex(WVertex *pv)
495 {
496 _paVertex = pv;
497 setVecAndAngle();
498 }
499
setbVertex(WVertex * pv)500 inline void setbVertex(WVertex *pv)
501 {
502 _pbVertex = pv;
503 setVecAndAngle();
504 }
505
setaFace(WFace * pf)506 inline void setaFace(WFace *pf)
507 {
508 _paFace = pf;
509 setVecAndAngle();
510 }
511
setbFace(WFace * pf)512 inline void setbFace(WFace *pf)
513 {
514 _pbFace = pf;
515 setVecAndAngle();
516 }
517
setOwner(WEdge * pe)518 inline void setOwner(WEdge *pe)
519 {
520 _pOwner = pe;
521 }
522
523 /*! Retrieves the list of edges in CW order */
524 inline void RetrieveCWOrderedEdges(vector<WEdge *> &oEdges);
525
526 WOEdge *twin();
527 WOEdge *getPrevOnFace();
528
ResetUserData()529 virtual void ResetUserData()
530 {
531 userdata = NULL;
532 }
533
534 #ifdef WITH_CXX_GUARDEDALLOC
535 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WOEdge")
536 #endif
537 };
538
539 /**********************************
540 * *
541 * *
542 * WEdge *
543 * *
544 * *
545 **********************************/
546
547 class WEdge {
548 protected:
549 WOEdge *_paOEdge; // first oriented edge
550 WOEdge *_pbOEdge; // second oriented edge
551 short _nOEdges; // number of oriented edges associated with this edge. (1 means border edge)
552 bool _Mark; // user-specified edge mark for feature edge detection
553 int _Id; // Identifier for the edge
554
555 public:
556 void *userdata; // designed to store specific user data
557
WEdge()558 inline WEdge()
559 {
560 _paOEdge = NULL;
561 _pbOEdge = NULL;
562 _nOEdges = 0;
563 userdata = NULL;
564 }
565
WEdge(WOEdge * iOEdge)566 inline WEdge(WOEdge *iOEdge)
567 {
568 _paOEdge = iOEdge;
569 _pbOEdge = NULL;
570 _nOEdges = 1;
571 userdata = NULL;
572 }
573
WEdge(WOEdge * iaOEdge,WOEdge * ibOEdge)574 inline WEdge(WOEdge *iaOEdge, WOEdge *ibOEdge)
575 {
576 _paOEdge = iaOEdge;
577 _pbOEdge = ibOEdge;
578 _nOEdges = 2;
579 userdata = NULL;
580 }
581
582 /*! Copy constructor */
583 WEdge(WEdge &iBrother);
584 virtual WEdge *duplicate();
585
~WEdge()586 virtual ~WEdge()
587 {
588 if (_paOEdge) {
589 delete _paOEdge;
590 _paOEdge = NULL;
591 }
592
593 if (_pbOEdge) {
594 delete _pbOEdge;
595 _pbOEdge = NULL;
596 }
597 }
598
599 /*! checks whether two WEdge have a common vertex.
600 * Returns a pointer on the common vertex if it exists, NULL otherwise.
601 */
CommonVertex(WEdge * iEdge1,WEdge * iEdge2)602 static inline WVertex *CommonVertex(WEdge *iEdge1, WEdge *iEdge2)
603 {
604 if (!iEdge1 || !iEdge2) {
605 return NULL;
606 }
607
608 WVertex *wv1 = iEdge1->GetaOEdge()->GetaVertex();
609 WVertex *wv2 = iEdge1->GetaOEdge()->GetbVertex();
610 WVertex *wv3 = iEdge2->GetaOEdge()->GetaVertex();
611 WVertex *wv4 = iEdge2->GetaOEdge()->GetbVertex();
612
613 if ((wv1 == wv3) || (wv1 == wv4)) {
614 return wv1;
615 }
616 else if ((wv2 == wv3) || (wv2 == wv4)) {
617 return wv2;
618 }
619 return NULL;
620 }
621
622 /*! accessors */
GetaOEdge()623 inline WOEdge *GetaOEdge()
624 {
625 return _paOEdge;
626 }
627
GetbOEdge()628 inline WOEdge *GetbOEdge()
629 {
630 return _pbOEdge;
631 }
632
GetNumberOfOEdges()633 inline short GetNumberOfOEdges()
634 {
635 return _nOEdges;
636 }
637
GetMark()638 inline bool GetMark()
639 {
640 return _Mark;
641 }
642
GetId()643 inline int GetId()
644 {
645 return _Id;
646 }
647
GetaVertex()648 inline WVertex *GetaVertex()
649 {
650 return _paOEdge->GetaVertex();
651 }
652
GetbVertex()653 inline WVertex *GetbVertex()
654 {
655 return _paOEdge->GetbVertex();
656 }
657
GetaFace()658 inline WFace *GetaFace()
659 {
660 return _paOEdge->GetaFace();
661 }
662
GetbFace()663 inline WFace *GetbFace()
664 {
665 return _paOEdge->GetbFace();
666 }
667
GetOtherOEdge(WOEdge * iOEdge)668 inline WOEdge *GetOtherOEdge(WOEdge *iOEdge)
669 {
670 if (iOEdge == _paOEdge) {
671 return _pbOEdge;
672 }
673 else {
674 return _paOEdge;
675 }
676 }
677
678 /*! modifiers */
setaOEdge(WOEdge * iEdge)679 inline void setaOEdge(WOEdge *iEdge)
680 {
681 _paOEdge = iEdge;
682 }
683
setbOEdge(WOEdge * iEdge)684 inline void setbOEdge(WOEdge *iEdge)
685 {
686 _pbOEdge = iEdge;
687 }
688
AddOEdge(WOEdge * iEdge)689 inline void AddOEdge(WOEdge *iEdge)
690 {
691 if (!_paOEdge) {
692 _paOEdge = iEdge;
693 _nOEdges++;
694 return;
695 }
696 if (!_pbOEdge) {
697 _pbOEdge = iEdge;
698 _nOEdges++;
699 return;
700 }
701 }
702
setNumberOfOEdges(short n)703 inline void setNumberOfOEdges(short n)
704 {
705 _nOEdges = n;
706 }
707
setMark(bool mark)708 inline void setMark(bool mark)
709 {
710 _Mark = mark;
711 }
712
setId(int id)713 inline void setId(int id)
714 {
715 _Id = id;
716 }
717
ResetUserData()718 virtual void ResetUserData()
719 {
720 userdata = NULL;
721 }
722
723 #ifdef WITH_CXX_GUARDEDALLOC
724 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WEdge")
725 #endif
726 };
727
728 /**********************************
729 * *
730 * *
731 * WFace *
732 * *
733 * *
734 **********************************/
735
736 class WFace {
737 protected:
738 vector<WOEdge *> _OEdgeList; // list of oriented edges of bording the face
739 Vec3f _Normal; // normal to the face
740 // in case there is a normal per vertex.
741 // The normal number i corresponds to the aVertex of the oedge number i, for that face
742 vector<Vec3f> _VerticesNormals;
743 vector<Vec2f> _VerticesTexCoords;
744
745 int _Id;
746 unsigned _FrsMaterialIndex;
747 bool _Mark; // Freestyle face mark (if true, feature edges on this face are ignored)
748
749 public:
750 void *userdata;
WFace()751 inline WFace()
752 {
753 userdata = NULL;
754 _FrsMaterialIndex = 0;
755 }
756
757 /*! copy constructor */
758 WFace(WFace &iBrother);
759 virtual WFace *duplicate();
~WFace()760 virtual ~WFace()
761 {
762 }
763
764 /*! accessors */
getEdgeList()765 inline const vector<WOEdge *> &getEdgeList()
766 {
767 return _OEdgeList;
768 }
769
GetOEdge(int i)770 inline WOEdge *GetOEdge(int i)
771 {
772 return _OEdgeList[i];
773 }
774
GetNormal()775 inline Vec3f &GetNormal()
776 {
777 return _Normal;
778 }
779
GetId()780 inline int GetId()
781 {
782 return _Id;
783 }
784
frs_materialIndex()785 inline unsigned frs_materialIndex() const
786 {
787 return _FrsMaterialIndex;
788 }
789
GetMark()790 inline bool GetMark() const
791 {
792 return _Mark;
793 }
794
795 const FrsMaterial &frs_material();
796
797 /*! The vertex of index i corresponds to the a vertex of the edge of index i */
GetVertex(unsigned int index)798 inline WVertex *GetVertex(unsigned int index)
799 {
800 #if 0
801 if (index >= _OEdgeList.size()) {
802 return NULL;
803 }
804 #endif
805 return _OEdgeList[index]->GetaVertex();
806 }
807
808 /*! returns the index at which iVertex is stored in the array.
809 * returns -1 if iVertex doesn't belong to the face.
810 */
GetIndex(WVertex * iVertex)811 inline int GetIndex(WVertex *iVertex)
812 {
813 int index = 0;
814 for (vector<WOEdge *>::iterator woe = _OEdgeList.begin(), woend = _OEdgeList.end();
815 woe != woend;
816 woe++) {
817 if ((*woe)->GetaVertex() == iVertex) {
818 return index;
819 }
820 ++index;
821 }
822 return -1;
823 }
824
RetrieveVertexList(vector<WVertex * > & oVertices)825 inline void RetrieveVertexList(vector<WVertex *> &oVertices)
826 {
827 for (vector<WOEdge *>::iterator woe = _OEdgeList.begin(), woend = _OEdgeList.end();
828 woe != woend;
829 woe++) {
830 oVertices.push_back((*woe)->GetaVertex());
831 }
832 }
833
RetrieveBorderFaces(vector<const WFace * > & oWFaces)834 inline void RetrieveBorderFaces(vector<const WFace *> &oWFaces)
835 {
836 for (vector<WOEdge *>::iterator woe = _OEdgeList.begin(), woend = _OEdgeList.end();
837 woe != woend;
838 woe++) {
839 WFace *af;
840 if ((af = (*woe)->GetaFace())) {
841 oWFaces.push_back(af);
842 }
843 }
844 }
845
GetBordingFace(int index)846 inline WFace *GetBordingFace(int index)
847 {
848 #if 0
849 if (index >= _OEdgeList.size()) {
850 return NULL;
851 }
852 #endif
853 return _OEdgeList[index]->GetaFace();
854 }
855
GetBordingFace(WOEdge * iOEdge)856 inline WFace *GetBordingFace(WOEdge *iOEdge)
857 {
858 return iOEdge->GetaFace();
859 }
860
GetPerVertexNormals()861 inline vector<Vec3f> &GetPerVertexNormals()
862 {
863 return _VerticesNormals;
864 }
865
GetPerVertexTexCoords()866 inline vector<Vec2f> &GetPerVertexTexCoords()
867 {
868 return _VerticesTexCoords;
869 }
870
871 /*! Returns the normal of the vertex of index index */
GetVertexNormal(int index)872 inline Vec3f &GetVertexNormal(int index)
873 {
874 return _VerticesNormals[index];
875 }
876
877 /*! Returns the tex coords of the vertex of index index */
GetVertexTexCoords(int index)878 inline Vec2f &GetVertexTexCoords(int index)
879 {
880 return _VerticesTexCoords[index];
881 }
882
883 /*! Returns the normal of the vertex iVertex for that face */
GetVertexNormal(WVertex * iVertex)884 inline Vec3f &GetVertexNormal(WVertex *iVertex)
885 {
886 int i = 0;
887 int index = 0;
888 for (vector<WOEdge *>::const_iterator woe = _OEdgeList.begin(), woend = _OEdgeList.end();
889 woe != woend;
890 woe++) {
891 if ((*woe)->GetaVertex() == iVertex) {
892 index = i;
893 break;
894 }
895 ++i;
896 }
897
898 return _VerticesNormals[index];
899 }
900
GetNextOEdge(WOEdge * iOEdge)901 inline WOEdge *GetNextOEdge(WOEdge *iOEdge)
902 {
903 bool found = false;
904 vector<WOEdge *>::iterator woe, woend, woefirst;
905 woefirst = _OEdgeList.begin();
906 for (woe = woefirst, woend = _OEdgeList.end(); woe != woend; ++woe) {
907 if (found) {
908 return (*woe);
909 }
910
911 if ((*woe) == iOEdge) {
912 found = true;
913 }
914 }
915
916 // We left the loop. That means that the first OEdge was the good one:
917 if (found) {
918 return (*woefirst);
919 }
920
921 return NULL;
922 }
923
924 WOEdge *GetPrevOEdge(WOEdge *iOEdge);
925
numberOfEdges()926 inline int numberOfEdges() const
927 {
928 return _OEdgeList.size();
929 }
930
numberOfVertices()931 inline int numberOfVertices() const
932 {
933 return _OEdgeList.size();
934 }
935
936 /*! Returns true if the face has one ot its edge which is a border edge */
isBorder()937 inline bool isBorder() const
938 {
939 for (vector<WOEdge *>::const_iterator woe = _OEdgeList.begin(), woeend = _OEdgeList.end();
940 woe != woeend;
941 ++woe) {
942 if ((*woe)->GetOwner()->GetbOEdge() == 0) {
943 return true;
944 }
945 }
946 return false;
947 }
948
949 /*! modifiers */
setEdgeList(const vector<WOEdge * > & iEdgeList)950 inline void setEdgeList(const vector<WOEdge *> &iEdgeList)
951 {
952 _OEdgeList = iEdgeList;
953 }
954
setNormal(const Vec3f & iNormal)955 inline void setNormal(const Vec3f &iNormal)
956 {
957 _Normal = iNormal;
958 }
959
setNormalList(const vector<Vec3f> & iNormalsList)960 inline void setNormalList(const vector<Vec3f> &iNormalsList)
961 {
962 _VerticesNormals = iNormalsList;
963 }
964
setTexCoordsList(const vector<Vec2f> & iTexCoordsList)965 inline void setTexCoordsList(const vector<Vec2f> &iTexCoordsList)
966 {
967 _VerticesTexCoords = iTexCoordsList;
968 }
969
setId(int id)970 inline void setId(int id)
971 {
972 _Id = id;
973 }
974
setFrsMaterialIndex(unsigned iMaterialIndex)975 inline void setFrsMaterialIndex(unsigned iMaterialIndex)
976 {
977 _FrsMaterialIndex = iMaterialIndex;
978 }
979
setMark(bool iMark)980 inline void setMark(bool iMark)
981 {
982 _Mark = iMark;
983 }
984
985 /*! designed to build a specialized WEdge for use in MakeEdge */
instanciateEdge()986 virtual WEdge *instanciateEdge() const
987 {
988 return new WEdge;
989 }
990
991 /*! Builds an oriented edge
992 * Returns the built edge.
993 * v1, v2
994 * Vertices at the edge's extremities
995 * The edge is oriented from v1 to v2.
996 */
997 virtual WOEdge *MakeEdge(WVertex *v1, WVertex *v2);
998
999 /*! Adds an edge to the edges list */
AddEdge(WOEdge * iEdge)1000 inline void AddEdge(WOEdge *iEdge)
1001 {
1002 _OEdgeList.push_back(iEdge);
1003 }
1004
1005 /*! For triangles, returns the edge opposite to the vertex in e.
1006 * returns false if the face is not a triangle or if the vertex is not found
1007 */
1008 bool getOppositeEdge(const WVertex *v, WOEdge *&e);
1009
1010 /*! compute the area of the face */
1011 float getArea();
1012
1013 WShape *getShape();
ResetUserData()1014 virtual void ResetUserData()
1015 {
1016 userdata = NULL;
1017 }
1018
1019 #ifdef WITH_CXX_GUARDEDALLOC
1020 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WFace")
1021 #endif
1022 };
1023
1024 /**********************************
1025 * *
1026 * *
1027 * WShape *
1028 * *
1029 * *
1030 **********************************/
1031
1032 class WShape {
1033 protected:
1034 vector<WVertex *> _VertexList;
1035 vector<WEdge *> _EdgeList;
1036 vector<WFace *> _FaceList;
1037 int _Id;
1038 string _Name;
1039 string _LibraryPath;
1040 static unsigned _SceneCurrentId;
1041 #if 0
1042 Vec3f _min;
1043 Vec3f _max;
1044 #endif
1045 vector<FrsMaterial> _FrsMaterials;
1046 #if 0
1047 float _meanEdgeSize;
1048 #endif
1049
1050 public:
WShape()1051 inline WShape()
1052 {
1053 #if 0
1054 _meanEdgeSize = 0;
1055 #endif
1056 _Id = _SceneCurrentId;
1057 _SceneCurrentId++;
1058 }
1059
1060 /*! copy constructor */
1061 WShape(WShape &iBrother);
1062 virtual WShape *duplicate();
1063
~WShape()1064 virtual ~WShape()
1065 {
1066 if (_EdgeList.size() != 0) {
1067 vector<WEdge *>::iterator e;
1068 for (e = _EdgeList.begin(); e != _EdgeList.end(); ++e) {
1069 delete (*e);
1070 }
1071 _EdgeList.clear();
1072 }
1073
1074 if (_VertexList.size() != 0) {
1075 vector<WVertex *>::iterator v;
1076 for (v = _VertexList.begin(); v != _VertexList.end(); ++v) {
1077 delete (*v);
1078 }
1079 _VertexList.clear();
1080 }
1081
1082 if (_FaceList.size() != 0) {
1083 vector<WFace *>::iterator f;
1084 for (f = _FaceList.begin(); f != _FaceList.end(); ++f) {
1085 delete (*f);
1086 }
1087 _FaceList.clear();
1088 }
1089 }
1090
1091 /*! accessors */
getEdgeList()1092 inline vector<WEdge *> &getEdgeList()
1093 {
1094 return _EdgeList;
1095 }
1096
getVertexList()1097 inline vector<WVertex *> &getVertexList()
1098 {
1099 return _VertexList;
1100 }
1101
GetFaceList()1102 inline vector<WFace *> &GetFaceList()
1103 {
1104 return _FaceList;
1105 }
1106
GetId()1107 inline unsigned GetId()
1108 {
1109 return _Id;
1110 }
1111
1112 #if 0
1113 inline void bbox(Vec3f &min, Vec3f &max)
1114 {
1115 min = _min;
1116 max = _max;
1117 }
1118 #endif
1119
frs_material(unsigned i)1120 inline const FrsMaterial &frs_material(unsigned i) const
1121 {
1122 return _FrsMaterials[i];
1123 }
1124
frs_materials()1125 inline const vector<FrsMaterial> &frs_materials() const
1126 {
1127 return _FrsMaterials;
1128 }
1129
1130 #if 0
1131 inline const float getMeanEdgeSize() const
1132 {
1133 return _meanEdgeSize;
1134 }
1135 #endif
1136
getName()1137 inline const string &getName() const
1138 {
1139 return _Name;
1140 }
1141
getLibraryPath()1142 inline const string &getLibraryPath() const
1143 {
1144 return _LibraryPath;
1145 }
1146
1147 /*! modifiers */
setCurrentId(const unsigned id)1148 static inline void setCurrentId(const unsigned id)
1149 {
1150 _SceneCurrentId = id;
1151 }
1152
setEdgeList(const vector<WEdge * > & iEdgeList)1153 inline void setEdgeList(const vector<WEdge *> &iEdgeList)
1154 {
1155 _EdgeList = iEdgeList;
1156 }
1157
setVertexList(const vector<WVertex * > & iVertexList)1158 inline void setVertexList(const vector<WVertex *> &iVertexList)
1159 {
1160 _VertexList = iVertexList;
1161 }
1162
setFaceList(const vector<WFace * > & iFaceList)1163 inline void setFaceList(const vector<WFace *> &iFaceList)
1164 {
1165 _FaceList = iFaceList;
1166 }
1167
setId(int id)1168 inline void setId(int id)
1169 {
1170 _Id = id;
1171 }
1172
1173 #if 0
1174 inline void setBBox(const Vec3f &min, const Vec3f &max)
1175 {
1176 _min = min;
1177 _max = max;
1178 }
1179 #endif
1180
setFrsMaterial(const FrsMaterial & frs_material,unsigned i)1181 inline void setFrsMaterial(const FrsMaterial &frs_material, unsigned i)
1182 {
1183 _FrsMaterials[i] = frs_material;
1184 }
1185
setFrsMaterials(const vector<FrsMaterial> & iMaterials)1186 inline void setFrsMaterials(const vector<FrsMaterial> &iMaterials)
1187 {
1188 _FrsMaterials = iMaterials;
1189 }
1190
setName(const string & name)1191 inline void setName(const string &name)
1192 {
1193 _Name = name;
1194 }
1195
setLibraryPath(const string & path)1196 inline void setLibraryPath(const string &path)
1197 {
1198 _LibraryPath = path;
1199 }
1200
1201 /*! designed to build a specialized WFace for use in MakeFace */
instanciateFace()1202 virtual WFace *instanciateFace() const
1203 {
1204 return new WFace;
1205 }
1206
1207 /*! adds a new face to the shape
1208 * returns the built face.
1209 * iVertexList
1210 * List of face's vertices. These vertices are not added to the WShape vertex list; they are
1211 * supposed to be already stored when calling MakeFace. The order in which the vertices are
1212 * stored in the list determines the face's edges orientation and (so) the face orientation.
1213 * iMaterialIndex
1214 * The material index for this face
1215 */
1216 virtual WFace *MakeFace(vector<WVertex *> &iVertexList,
1217 vector<bool> &iFaceEdgeMarksList,
1218 unsigned iMaterialIndex);
1219
1220 /*! adds a new face to the shape. The difference with the previous method is that this one is
1221 * designed to build a WingedEdge structure for which there are per vertex normals, opposed to
1222 * per face normals. returns the built face. iVertexList List of face's vertices. These vertices
1223 * are not added to the WShape vertex list; they are supposed to be already stored when calling
1224 * MakeFace. The order in which the vertices are stored in the list determines the face's edges
1225 * orientation and (so) the face orientation. iMaterialIndex The materialIndex for this face
1226 * iNormalsList
1227 * The list of normals, iNormalsList[i] corresponding to the normal of the vertex
1228 * iVertexList[i] for that face. iTexCoordsList The list of tex coords, iTexCoordsList[i]
1229 * corresponding to the normal of the vertex iVertexList[i] for that face.
1230 */
1231 virtual WFace *MakeFace(vector<WVertex *> &iVertexList,
1232 vector<Vec3f> &iNormalsList,
1233 vector<Vec2f> &iTexCoordsList,
1234 vector<bool> &iFaceEdgeMarksList,
1235 unsigned iMaterialIndex);
1236
AddEdge(WEdge * iEdge)1237 inline void AddEdge(WEdge *iEdge)
1238 {
1239 _EdgeList.push_back(iEdge);
1240 }
1241
AddFace(WFace * iFace)1242 inline void AddFace(WFace *iFace)
1243 {
1244 _FaceList.push_back(iFace);
1245 }
1246
AddVertex(WVertex * iVertex)1247 inline void AddVertex(WVertex *iVertex)
1248 {
1249 iVertex->setShape(this);
1250 _VertexList.push_back(iVertex);
1251 }
1252
ResetUserData()1253 inline void ResetUserData()
1254 {
1255 for (vector<WVertex *>::iterator v = _VertexList.begin(), vend = _VertexList.end(); v != vend;
1256 v++) {
1257 (*v)->ResetUserData();
1258 }
1259
1260 for (vector<WEdge *>::iterator e = _EdgeList.begin(), eend = _EdgeList.end(); e != eend; e++) {
1261 (*e)->ResetUserData();
1262 // manages WOEdge:
1263 WOEdge *oe = (*e)->GetaOEdge();
1264 if (oe) {
1265 oe->ResetUserData();
1266 }
1267 oe = (*e)->GetbOEdge();
1268 if (oe) {
1269 oe->ResetUserData();
1270 }
1271 }
1272
1273 for (vector<WFace *>::iterator f = _FaceList.begin(), fend = _FaceList.end(); f != fend; f++) {
1274 (*f)->ResetUserData();
1275 }
1276 }
1277
1278 #if 0
1279 inline void ComputeBBox()
1280 {
1281 _min = _VertexList[0]->GetVertex();
1282 _max = _VertexList[0]->GetVertex();
1283
1284 Vec3f v;
1285 for (vector<WVertex *>::iterator wv = _VertexList.begin(), wvend = _VertexList.end();
1286 wv != wvend;
1287 wv++) {
1288 for (unsigned int i = 0; i < 3; i++) {
1289 v = (*wv)->GetVertex();
1290 if (v[i] < _min[i]) {
1291 _min[i] = v[i];
1292 }
1293 if (v[i] > _max[i]) {
1294 _max[i] = v[i];
1295 }
1296 }
1297 }
1298 }
1299 #endif
1300
1301 #if 0
1302 inline float ComputeMeanEdgeSize()
1303 {
1304 _meanEdgeSize = _meanEdgeSize / _EdgeList.size();
1305 return _meanEdgeSize;
1306 }
1307 #else
1308 real ComputeMeanEdgeSize() const;
1309 #endif
1310
1311 protected:
1312 /*!
1313 * Builds the face passed as argument (which as already been allocated)
1314 * - iVertexList
1315 * List of face's vertices. These vertices are not added to the WShape vertex list;
1316 * they are supposed to be already stored when calling MakeFace.
1317 * The order in which the vertices are stored in the list determines
1318 * the face's edges orientation and (so) the face orientation.
1319 * - iMaterialIndex
1320 * The material index for this face
1321 * - face
1322 * The Face that is filled in
1323 */
1324 virtual WFace *MakeFace(vector<WVertex *> &iVertexList,
1325 vector<bool> &iFaceEdgeMarksList,
1326 unsigned iMaterialIndex,
1327 WFace *face);
1328
1329 #ifdef WITH_CXX_GUARDEDALLOC
1330 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WShape")
1331 #endif
1332 };
1333
1334 /**********************************
1335 * *
1336 * *
1337 * WingedEdge *
1338 * *
1339 * *
1340 **********************************/
1341
1342 class WingedEdge {
1343 public:
WingedEdge()1344 WingedEdge()
1345 {
1346 _numFaces = 0;
1347 }
1348
~WingedEdge()1349 ~WingedEdge()
1350 {
1351 clear();
1352 }
1353
clear()1354 void clear()
1355 {
1356 for (vector<WShape *>::iterator it = _wshapes.begin(); it != _wshapes.end(); it++) {
1357 delete *it;
1358 }
1359 _wshapes.clear();
1360 _numFaces = 0;
1361 }
1362
addWShape(WShape * wshape)1363 void addWShape(WShape *wshape)
1364 {
1365 _wshapes.push_back(wshape);
1366 _numFaces += wshape->GetFaceList().size();
1367 }
1368
getWShapes()1369 vector<WShape *> &getWShapes()
1370 {
1371 return _wshapes;
1372 }
1373
getNumFaces()1374 unsigned getNumFaces()
1375 {
1376 return _numFaces;
1377 }
1378
1379 private:
1380 vector<WShape *> _wshapes;
1381 unsigned _numFaces;
1382
1383 #ifdef WITH_CXX_GUARDEDALLOC
1384 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WingedEdge")
1385 #endif
1386 };
1387
1388 /*
1389 * #############################################
1390 * #############################################
1391 * #############################################
1392 * ###### ######
1393 * ###### I M P L E M E N T A T I O N ######
1394 * ###### ######
1395 * #############################################
1396 * #############################################
1397 * #############################################
1398 */
1399 /* for inline functions */
RetrieveCWOrderedEdges(vector<WEdge * > & oEdges)1400 void WOEdge::RetrieveCWOrderedEdges(vector<WEdge *> &oEdges)
1401 {
1402 WOEdge *currentOEdge = this;
1403 do {
1404 WOEdge *nextOEdge = currentOEdge->GetbFace()->GetNextOEdge(currentOEdge);
1405 oEdges.push_back(nextOEdge->GetOwner());
1406 currentOEdge = nextOEdge->GetOwner()->GetOtherOEdge(nextOEdge);
1407 } while (currentOEdge && (currentOEdge->GetOwner() != GetOwner()));
1408 }
1409
setVecAndAngle()1410 inline void WOEdge::setVecAndAngle()
1411 {
1412 if (_paVertex && _pbVertex) {
1413 _vec = _pbVertex->GetVertex() - _paVertex->GetVertex();
1414 if (_paFace && _pbFace) {
1415 float sine = (_pbFace->GetNormal() ^ _paFace->GetNormal()) * _vec / _vec.norm();
1416 if (sine >= 1.0) {
1417 _angle = M_PI / 2.0;
1418 return;
1419 }
1420 if (sine <= -1.0) {
1421 _angle = -M_PI / 2.0;
1422 return;
1423 }
1424 _angle = ::asin(sine);
1425 }
1426 }
1427 }
1428
1429 } /* namespace Freestyle */
1430