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