Freestyle: minor optimization for space from mesh importing to feature edge detection.
[blender.git] / source / blender / freestyle / intern / winged_edge / WXEdge.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_WX_EDGE_H__
22 #define __FREESTYLE_WX_EDGE_H__
23
24 /** \file blender/freestyle/intern/winged_edge/WXEdge.h
25  *  \ingroup freestyle
26  *  \brief Classes to define an Extended Winged Edge data structure.
27  *  \author Stephane Grabli
28  *  \date 26/10/2003
29  */
30
31 #include "Curvature.h"
32 #include "Nature.h"
33 #include "WEdge.h"
34
35 #ifdef WITH_CXX_GUARDEDALLOC
36 #include "MEM_guardedalloc.h"
37 #endif
38
39 namespace Freestyle {
40
41 typedef Nature::EdgeNature WXNature;
42
43 /**********************************
44  *                                *
45  *                                *
46  *             WXVertex           *
47  *                                *
48  *                                *
49  **********************************/
50
51 class WXVertex : public WVertex
52 {
53 private:
54         // Curvature info
55         CurvatureInfo *_curvatures;
56
57 public:
58         inline WXVertex(const Vec3r &v) : WVertex(v)
59         {
60                 _curvatures = NULL;
61         }
62
63         /*! Copy constructor */
64         WXVertex(WXVertex& iBrother) : WVertex(iBrother)
65         {
66                 _curvatures = new CurvatureInfo(*iBrother._curvatures);
67         }
68
69         virtual WVertex *duplicate()
70         {
71                 WXVertex *clone = new WXVertex(*this);
72                 return clone;
73         }
74
75         virtual ~WXVertex()
76         {
77                 if (_curvatures)
78                         delete _curvatures;
79         }
80
81         virtual void Reset()
82         {
83                 if (_curvatures)
84                         _curvatures->Kr = 0.0;
85         }
86
87         inline void setCurvatures(CurvatureInfo *ci)
88         {
89                 _curvatures = ci;
90         }
91
92         inline bool isFeature();
93
94         inline CurvatureInfo *curvatures()
95         {
96                 return _curvatures;
97         }
98
99 #ifdef WITH_CXX_GUARDEDALLOC
100         MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WXVertex")
101 #endif
102 };
103
104
105 /**********************************
106  *                                *
107  *                                *
108  *             WXEdge             *
109  *                                *
110  *                                *
111  **********************************/
112
113 class WXEdge : public WEdge
114 {
115 private:
116         // flag to indicate whether the edge is a silhouette edge or not
117         WXNature _nature;
118         // 0: the order doesn't matter. 1: the order is the orginal one. -1: the order is not good
119         short _order;
120         // A front facing edge is an edge for which the bording face which is the nearest from the viewpoint is front.
121         // A back facing edge is the opposite.
122         bool _front;
123
124 public:
125         inline WXEdge() : WEdge()
126         {
127                 _nature = Nature::NO_FEATURE;
128                 _front = false;
129                 _order = 0;
130         }
131
132         inline WXEdge(WOEdge *iOEdge) : WEdge(iOEdge)
133         {
134                 _nature = Nature::NO_FEATURE;
135                 _front = false;
136                 _order = 0;
137         }
138
139         inline WXEdge(WOEdge *iaOEdge, WOEdge *ibOEdge) : WEdge(iaOEdge, ibOEdge)
140         {
141                 _nature = Nature::NO_FEATURE;
142                 _front = false;
143                 _order = 0;
144         }
145
146         /*! Copy constructor */
147         inline WXEdge(WXEdge& iBrother) : WEdge(iBrother)
148         {
149                 _nature = iBrother.nature();
150                 _front = iBrother._front;
151                 _order = iBrother._order;
152         }
153
154         virtual WEdge *duplicate()
155         {
156                 WXEdge *clone = new WXEdge(*this);
157                 return clone;
158         }
159
160         virtual ~WXEdge() {}
161
162         virtual void Reset()
163         {
164                 _nature  = _nature & ~Nature::SILHOUETTE;
165                 _nature  = _nature & ~Nature::SUGGESTIVE_CONTOUR;
166         }
167
168         /*! accessors */
169         inline WXNature nature()
170         {
171                 return _nature;
172         }
173
174         inline bool front()
175         {
176                 return _front;
177         }
178
179         inline short order() const
180         {
181                 return _order;
182         }
183
184         /*! modifiers */
185         inline void setFront(bool iFront)
186         {
187                 _front = iFront;
188         }
189
190         inline void setNature(WXNature iNature)
191         {
192                 _nature = iNature;
193         }
194
195         inline void AddNature(WXNature iNature)
196         {
197                 _nature = _nature | iNature;
198         }
199
200         inline void setOrder(int i)
201         {
202                 _order = i;
203         }
204
205 #ifdef WITH_CXX_GUARDEDALLOC
206         MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WXEdge")
207 #endif
208 };
209
210 /**********************************
211  *                                *
212  *                                *
213  *             WXFace             *
214  *                                *
215  *                                *
216  **********************************/
217
218 /*! Class to store a smooth edge (i.e Hertzman & Zorin smooth silhouette edges) */
219 class WXSmoothEdge
220 {
221 public:
222         typedef unsigned short Configuration;
223         static const Configuration EDGE_EDGE = 1;
224         static const Configuration VERTEX_EDGE = 2;
225         static const Configuration EDGE_VERTEX = 3;
226
227         WOEdge *_woea; // Oriented edge from which the silhouette edge starts
228         WOEdge *_woeb; // Oriented edge where the silhouette edge ends
229         real _ta;      // The silhouette starting point's coordinates are : _woea[0]+ta*(_woea[1]-_woea[0])
230         real _tb;      // The silhouette ending point's coordinates are : _woeb[0]+ta*(_woeb[1]-_woeb[0])
231         bool _front;
232         Configuration _config;
233
234         WXSmoothEdge()
235         {
236                 _woea = NULL;
237                 _woeb = NULL;
238                 _ta = 0;
239                 _tb = 0;
240                 _front = false;
241                 _config = EDGE_EDGE;
242         }
243
244         WXSmoothEdge(const WXSmoothEdge& iBrother)
245         {
246                 _woea = iBrother._woea;
247                 _woeb = iBrother._woeb;
248                 _ta = iBrother._ta;
249                 _tb = iBrother._tb;
250                 _config = iBrother._config;
251                 _front = iBrother._front;
252         }
253
254         ~WXSmoothEdge() {}
255
256         inline WOEdge *woea()
257         {
258                 return _woea;
259         }
260
261         inline WOEdge *woeb()
262         {
263                 return _woeb;
264         }
265
266         inline real ta() const
267         {
268                 return _ta;
269         }
270
271         inline real tb() const
272         {
273                 return _tb;
274         }
275
276         inline bool front() const
277         {
278                 return _front;
279         }
280
281         inline Configuration configuration() const
282         {
283                 return _config;
284         }
285
286         /*! modifiers */
287         inline void setWOeA(WOEdge *iwoea)
288         {
289                 _woea = iwoea;
290         }
291
292         inline void setWOeB(WOEdge *iwoeb)
293         {
294                 _woeb = iwoeb;
295         }
296
297         inline void setTa(real ta)
298         {
299                 _ta = ta;
300         }
301
302         inline void setTb(real tb)
303         {
304                 _tb = tb;
305         }
306
307         inline void setFront(bool iFront)
308         {
309                 _front = iFront;
310         }
311
312         inline void setConfiguration(Configuration iConf)
313         {
314                 _config = iConf;
315         }
316
317 #ifdef WITH_CXX_GUARDEDALLOC
318         MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WXSmoothEdge")
319 #endif
320 };
321
322 /* Class to store a value per vertex and a smooth edge.
323  * The WXFace stores a list of these
324  */
325 class WXFace;
326
327 class WXFaceLayer
328 {
329 public:
330         void *userdata;
331         WXFace *_pWXFace;
332         // in case of silhouette: the values obtained when computing the normal-view direction dot product. _DotP[i] is
333         // this value for the vertex i for that face.
334         vector<real> _DotP;
335         WXSmoothEdge *_pSmoothEdge;
336         WXNature _Nature;
337
338         //oldtmp values
339         // count the number of positive dot products for vertices.
340         // if this number is != 0 and !=_DotP.size() -> it is a silhouette fac
341         unsigned _nPosDotP;
342
343         unsigned _nNullDotP; // count the number of null dot products for vertices.
344         unsigned _ClosestPointIndex;
345         bool _viewDependant;
346
347         WXFaceLayer(WXFace *iFace, WXNature iNature, bool viewDependant)
348         {
349                 _pWXFace = iFace;
350                 _pSmoothEdge = NULL;
351                 _nPosDotP = 0;
352                 _nNullDotP = 0;
353                 _Nature = iNature;
354                 _viewDependant = viewDependant;
355                 userdata = NULL;
356         }
357
358         WXFaceLayer(const WXFaceLayer& iBrother)
359         {
360                 _pWXFace = iBrother._pWXFace;
361                 _pSmoothEdge = NULL;
362                 _DotP = iBrother._DotP;
363                 _nPosDotP = iBrother._nPosDotP;
364                 _nNullDotP = iBrother._nNullDotP;
365                 _Nature = iBrother._Nature;
366                 if (iBrother._pSmoothEdge) {  // XXX ? It's set to null a few lines above!
367                         _pSmoothEdge = new WXSmoothEdge(*(iBrother._pSmoothEdge));
368                 }
369                 _viewDependant = iBrother._viewDependant;
370                 userdata = NULL;
371         }
372
373         virtual ~WXFaceLayer()
374         {
375                 if (!_DotP.empty())
376                         _DotP.clear();
377                 if (_pSmoothEdge) {
378                         delete _pSmoothEdge;
379                         _pSmoothEdge = NULL;
380                 }
381         }
382
383         inline const real dotP(int i) const
384         {
385                 return _DotP[i];
386         }
387
388         inline unsigned nPosDotP() const
389         {
390                 return _nPosDotP;
391         }
392
393         inline unsigned nNullDotP() const
394         {
395                 return _nNullDotP;
396         }
397
398         inline int closestPointIndex() const
399         {
400                 return _ClosestPointIndex;
401         }
402
403         inline WXNature nature() const
404         {
405                 return _Nature;
406         }
407
408         inline bool hasSmoothEdge() const
409         {
410                 if (_pSmoothEdge)
411                         return true;
412                 return false;
413         }
414
415         inline WXFace *getFace()
416         {
417                 return _pWXFace;
418         }
419
420         inline WXSmoothEdge *getSmoothEdge()
421         {
422                 return _pSmoothEdge;
423         }
424
425         inline bool isViewDependant() const
426         {
427                 return _viewDependant;
428         }
429
430         inline void setClosestPointIndex(int iIndex)
431         {
432                 _ClosestPointIndex = iIndex;
433         }
434
435         inline void removeSmoothEdge()
436         {
437                 if (!_DotP.empty())
438                         _DotP.clear();
439                 if (_pSmoothEdge) {
440                         delete _pSmoothEdge;
441                         _pSmoothEdge = NULL;
442                 }
443         }
444
445         /*! If one of the face layer vertex has a DotP equal to 0, this method returns the vertex where it happens */
446         unsigned int Get0VertexIndex() const;
447
448         /*! In case one of the edge of the triangle is a smooth edge, this method allows to retrieve the concerned edge */
449         unsigned int GetSmoothEdgeIndex() const;
450
451         /*! retrieves the edges of the triangle for which the signs are different (a null value is not considered) for
452          *  the dotp values at each edge extrimity
453          */
454         void RetrieveCuspEdgesIndices(vector<int>& oCuspEdges);
455
456         WXSmoothEdge *BuildSmoothEdge();
457
458         inline void setDotP(const vector<real>& iDotP)
459         {
460                 _DotP = iDotP;
461         }
462
463         inline void PushDotP(real iDotP)
464         {
465                 _DotP.push_back(iDotP);
466                 if (iDotP > 0)
467                         ++_nPosDotP;
468                 if (iDotP == 0)
469                         ++_nNullDotP;
470         }
471
472         inline void ReplaceDotP(unsigned int index, real newDotP)
473         {
474                 _DotP[index] = newDotP;
475                 updateDotPInfos();
476         }
477
478         inline void updateDotPInfos()
479         {
480                 _nPosDotP = 0;
481                 _nNullDotP = 0;
482                 for (vector<real>::iterator d = _DotP.begin(), dend = _DotP.end(); d != dend; ++d) {
483                         if ((*d) > 0)
484                                 ++_nPosDotP;
485                         if ((*d) == 0)
486                                 ++_nNullDotP;
487                 }
488         }
489
490 #ifdef WITH_CXX_GUARDEDALLOC
491         MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WXFaceLayer")
492 #endif
493 };
494
495 class WXFace : public WFace
496 {
497 protected:
498         Vec3r _center; // center of the face
499         real _Z; // distance from viewpoint to the center of the face
500         bool _front; // flag to tell whether the face is front facing or back facing
501         real _dotp;  // value obtained when computing the normal-viewpoint dot product
502
503         vector<WXFaceLayer *> _SmoothLayers; // The data needed to store one or several smooth edges that traverse the face
504
505 public:
506         inline WXFace() : WFace()
507         {
508                 _Z = 0.0;
509                 _front = false;
510         }
511
512         /*! Copy constructor */
513         WXFace(WXFace& iBrother) : WFace(iBrother)
514         {
515                 _center = iBrother.center();
516                 _Z = iBrother.Z();
517                 _front = iBrother.front();
518                 for (vector<WXFaceLayer*>::iterator wxf = iBrother._SmoothLayers.begin(), wxfend = iBrother._SmoothLayers.end();
519                      wxf != wxfend;
520                      ++wxf)
521                 {
522                         _SmoothLayers.push_back(new WXFaceLayer(**wxf));
523                 }
524         }
525
526         virtual WFace *duplicate()
527         {
528                 WXFace *clone = new WXFace(*this);
529                 return clone;
530         }
531
532         virtual ~WXFace()
533         {
534                 if (!_SmoothLayers.empty()) {
535                         for (vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
536                              wxf != wxfend;
537                              ++wxf)
538                         {
539                                 delete (*wxf);
540                         }
541                         _SmoothLayers.clear();
542                 }
543         }
544
545         /*! designed to build a specialized WEdge for use in MakeEdge */
546         virtual WEdge *instanciateEdge() const
547         {
548                 return new WXEdge;
549         }
550
551         /*! accessors */
552         inline Vec3r& center()
553         {
554                 return _center;
555         }
556
557         inline real Z()
558         {
559                 return _Z;
560         }
561
562         inline bool front()
563         {
564                 return _front;
565         }
566
567         inline real dotp()
568         {
569                 return _dotp;
570         }
571
572         inline bool hasSmoothEdges() const
573         {
574                 for (vector<WXFaceLayer*>::const_iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
575                      wxf != wxfend;
576                      ++wxf)
577                 {
578                         if ((*wxf)->hasSmoothEdge()) {
579                                 return true;
580                         }
581                 }
582                 return false;
583         }
584
585         vector<WXFaceLayer*>& getSmoothLayers()
586         {
587                 return _SmoothLayers;
588         }
589
590         /*! retrieve the smooth edges that match the Nature given as argument */
591         void retrieveSmoothEdges(WXNature iNature, vector<WXSmoothEdge *>& oSmoothEdges)
592         {
593                 for (vector<WXFaceLayer *>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
594                      wxf != wxfend;
595                      ++wxf)
596                 {
597                         if ((*wxf)->hasSmoothEdge() && ((*wxf)->_Nature & iNature)) {
598                                 oSmoothEdges.push_back((*wxf)->_pSmoothEdge);
599                         }
600                 }
601         }
602
603         void retrieveSmoothEdgesLayers(WXNature iNature, vector<WXFaceLayer *>& oSmoothEdgesLayers)
604         {
605                 for (vector<WXFaceLayer *>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
606                      wxf != wxfend;
607                      ++wxf)
608                 {
609                         if ((*wxf)->hasSmoothEdge() && ((*wxf)->_Nature & iNature)) {
610                                 oSmoothEdgesLayers.push_back((*wxf));
611                         }
612                 }
613         }
614
615         void retrieveSmoothLayers(WXNature iNature, vector<WXFaceLayer *>& oSmoothLayers)
616         {
617                 for (vector<WXFaceLayer *>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
618                      wxf != wxfend;
619                      ++wxf)
620                 {
621                         if ((*wxf)->_Nature & iNature) {
622                                 oSmoothLayers.push_back(*wxf);
623                         }
624                 }
625         }
626
627         /*! modifiers */
628         inline void setCenter(const Vec3r& iCenter)
629         {
630                 _center = iCenter;
631         }
632
633         void ComputeCenter();
634
635         inline void setZ(real z)
636         {
637                 _Z = z;
638         }
639
640         inline void setFront(bool iFront)
641         {
642                 _front = iFront;
643         }
644
645         inline void setDotP(real iDotP)
646         {
647                 _dotp = iDotP;
648                 if (_dotp > 0)
649                         _front = true;
650                 else
651                         _front = false;
652         }
653
654         inline void AddSmoothLayer(WXFaceLayer *iLayer)
655         {
656                 _SmoothLayers.push_back(iLayer);
657         }
658
659         inline void Reset()
660         {
661                 vector<WXFaceLayer *> layersToKeep;
662                 for (vector<WXFaceLayer *>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
663                      wxf != wxfend;
664                      ++wxf)
665                 {
666                         if ((*wxf)->isViewDependant())
667                                 delete (*wxf);
668                         else
669                                 layersToKeep.push_back(*wxf);
670                 }
671                 _SmoothLayers = layersToKeep;
672         }
673
674         /*! Clears everything */
675         inline void Clear()
676         {
677                 for (vector<WXFaceLayer *>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
678                      wxf != wxfend;
679                      ++wxf)
680                 {
681                         delete (*wxf);
682                 }
683                 _SmoothLayers.clear();
684         }
685
686         virtual void ResetUserData()
687         {
688                 WFace::ResetUserData();
689                 for (vector<WXFaceLayer *>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end();
690                      wxf != wxfend;
691                      ++wxf)
692                 {
693                         (*wxf)->userdata = NULL;
694                 }
695         }
696
697 #ifdef WITH_CXX_GUARDEDALLOC
698         MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WXFace")
699 #endif
700 };
701
702
703 /**********************************
704  *                                *
705  *                                *
706  *             WXShape            *
707  *                                *
708  *                                *
709  **********************************/
710
711 class WXShape : public WShape
712 {
713 public:
714         typedef WXShape type_name;
715
716 protected:
717         bool _computeViewIndependent; // flag to indicate whether the view independent stuff must be computed or not
718
719 public:
720         inline WXShape() : WShape()
721         {
722                 _computeViewIndependent = true;
723         }
724
725         /*! copy constructor */
726         inline WXShape(WXShape& iBrother) : WShape(iBrother)
727         {
728                 _computeViewIndependent = iBrother._computeViewIndependent;
729         }
730
731         virtual WShape *duplicate()
732         {
733                 WXShape *clone = new WXShape(*this);
734                 return clone;
735         }
736
737         virtual ~WXShape() {}
738
739         inline bool getComputeViewIndependentFlag() const
740         {
741                 return _computeViewIndependent;
742         }
743
744         inline void setComputeViewIndependentFlag(bool iFlag)
745         {
746                 _computeViewIndependent = iFlag;
747         }
748
749         /*! designed to build a specialized WFace for use in MakeFace */
750         virtual WFace *instanciateFace() const
751         {
752                 return new WXFace;
753         }
754
755         /*! adds a new face to the shape returns the built face.
756          *   iVertexList
757          *      List of face's vertices. These vertices are not added to the WShape vertex list; they are supposed
758          *      to be already stored when calling MakeFace. The order in which the vertices are stored in the list
759          *      determines the face's edges orientation and (so) the face orientation.
760          */
761         virtual WFace *MakeFace(vector<WVertex *>& iVertexList, vector<bool>& iFaceEdgeMarksList, unsigned iMaterialIndex);
762
763         /*! adds a new face to the shape. The difference with the previous method is that this one is designed to build
764          *  a WingedEdge structure for which there are per vertex normals, opposed to per face normals.
765          *  returns the built face.
766          *   iVertexList
767          *      List of face's vertices. These vertices are not added to the WShape vertex list; they are supposed to be
768          *      already stored when calling MakeFace.
769          *      The order in which the vertices are stored in the list determines the face's edges orientation and (so) the
770          *      face orientation.
771          *   iNormalsList
772          *     The list of normals, iNormalsList[i] corresponding to the normal of the vertex iVertexList[i] for that face.
773          *   iTexCoordsList
774          *     The list of tex coords, iTexCoordsList[i] corresponding to the normal of the vertex iVertexList[i] for
775          *     that face.
776          */
777         virtual WFace *MakeFace(vector<WVertex *>& iVertexList, vector<Vec3r>& iNormalsList, vector<Vec2r>& iTexCoordsList,
778                                 vector<bool>& iFaceEdgeMarksList, unsigned iMaterialIndex);
779
780         /*! Reset all edges and vertices flags (which might have been set up on a previous pass) */
781         virtual void Reset()
782         {
783                 // Reset Edges
784                 vector<WEdge *>& wedges = getEdgeList();
785                 for (vector<WEdge *>::iterator we = wedges.begin(), weend = wedges.end(); we != weend; ++we) {
786                         ((WXEdge *)(*we))->Reset();
787                 }
788
789                 //Reset faces:
790                 vector<WFace *>& wfaces = GetFaceList();
791                 for (vector<WFace *>::iterator wf = wfaces.begin(), wfend = wfaces.end(); wf != wfend; ++wf) {
792                         ((WXFace *)(*wf))->Reset();
793                 }
794         }
795         /*! accessors */
796
797 #ifdef WITH_CXX_GUARDEDALLOC
798         MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:WXShape")
799 #endif
800 };
801
802 /*
803
804 #############################################
805 #############################################
806 #############################################
807 ######                                 ######
808 ######   I M P L E M E N T A T I O N   ######
809 ######                                 ######
810 #############################################
811 #############################################
812 #############################################
813
814 */
815 /* for inline functions */
816
817 bool WXVertex::isFeature()
818 {
819         int counter = 0;
820         vector<WEdge *>& vedges = GetEdges();
821         for (vector<WEdge *>::iterator ve = vedges.begin(), vend = vedges.end(); ve != vend; ++ve) {
822                 if (((WXEdge *)(*ve))->nature() != Nature::NO_FEATURE)
823                         counter++;
824         }
825
826         if ((counter == 1) || (counter > 2))
827                 return true;
828         return false;
829 }
830
831 } /* namespace Freestyle */
832
833 #endif  // __FREESTYLE_WX_EDGE_H__