Cleanup: misc spelling fixes
[blender.git] / source / blender / freestyle / intern / view_map / Silhouette.h
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 #ifndef __FREESTYLE_SILHOUETTE_H__
18 #define __FREESTYLE_SILHOUETTE_H__
19
20 /** \file
21  * \ingroup freestyle
22  * \brief Classes to define a silhouette structure
23  */
24
25 #include <float.h>
26 #include <iostream>
27 #include <set>
28 #include <string>
29 #include <vector>
30
31 #include "Interface0D.h"
32 #include "Interface1D.h"
33
34 #include "../geometry/BBox.h"
35 #include "../geometry/Geom.h"
36 #include "../geometry/Polygon.h"
37
38 #include "../scene_graph/FrsMaterial.h"
39
40 #include "../system/Exception.h"
41 #include "../system/FreestyleConfig.h"
42
43 #include "../winged_edge/Curvature.h"
44
45 #ifdef WITH_CXX_GUARDEDALLOC
46 #  include "MEM_guardedalloc.h"
47 #endif
48
49 using namespace std;
50
51 namespace Freestyle {
52
53 using namespace Geometry;
54
55 class ViewShape;
56 typedef vector<ViewShape *> occluder_container;
57
58 /**********************************/
59 /*                                */
60 /*                                */
61 /*             SVertex            */
62 /*                                */
63 /*                                */
64 /**********************************/
65
66 class FEdge;
67 class ViewVertex;
68 class SShape;
69
70 /*! Class to define a vertex of the embedding. */
71 class SVertex : public Interface0D {
72  public:  // Implementation of Interface0D
73   /*! Returns the string "SVertex" .*/
74   virtual string getExactTypeName() const
75   {
76     return "SVertex";
77   }
78
79   // Data access methods
80   /*! Returns the 3D x coordinate of the vertex .*/
81   virtual real getX() const
82   {
83     return _Point3D.x();
84   }
85
86   /*! Returns the 3D y coordinate of the vertex .*/
87   virtual real getY() const
88   {
89     return _Point3D.y();
90   }
91
92   /*! Returns the 3D z coordinate of the vertex .*/
93   virtual real getZ() const
94   {
95     return _Point3D.z();
96   }
97
98   /*!  Returns the 3D point. */
99   virtual Vec3r getPoint3D() const
100   {
101     return _Point3D;
102   }
103
104   /*! Returns the projected 3D  x coordinate of the vertex .*/
105   virtual real getProjectedX() const
106   {
107     return _Point2D.x();
108   }
109
110   /*! Returns the projected 3D  y coordinate of the vertex .*/
111   virtual real getProjectedY() const
112   {
113     return _Point2D.y();
114   }
115
116   /*! Returns the projected 3D  z coordinate of the vertex .*/
117   virtual real getProjectedZ() const
118   {
119     return _Point2D.z();
120   }
121
122   /*!  Returns the 2D point. */
123   virtual Vec2r getPoint2D() const
124   {
125     return Vec2r(_Point2D.x(), _Point2D.y());
126   }
127
128   /*! Returns the FEdge that lies between this Svertex and the Interface0D given as argument. */
129   virtual FEdge *getFEdge(Interface0D &);
130
131   /*! Returns the Id of the vertex .*/
132   virtual Id getId() const
133   {
134     return _Id;
135   }
136
137   /*! Returns the nature of the vertex .*/
138   virtual Nature::VertexNature getNature() const;
139
140   /*! Cast the Interface0D in SVertex if it can be. */
141   virtual SVertex *castToSVertex();
142
143   /*! Cast the Interface0D in ViewVertex if it can be. */
144   virtual ViewVertex *castToViewVertex();
145
146   /*! Cast the Interface0D in NonTVertex if it can be. */
147   virtual NonTVertex *castToNonTVertex();
148
149   /*! Cast the Interface0D in TVertex if it can be. */
150   virtual TVertex *castToTVertex();
151
152  public:
153   typedef vector<FEdge *> fedges_container;
154
155  private:
156   Id _Id;
157   Vec3r _Point3D;
158   Vec3r _Point2D;
159   set<Vec3r> _Normals;
160   vector<FEdge *> _FEdges;   // the edges containing this vertex
161   SShape *_Shape;            // the shape to which belongs the vertex
162   ViewVertex *_pViewVertex;  // The associated viewvertex, in case there is one.
163 #if 0
164   real _curvatureFredo;
165   Vec2r _directionFredo;
166 #endif
167   CurvatureInfo *_curvature_info;
168
169  public:
170   /*! A field that can be used by the user to store any data.
171    *  This field must be reset afterwards using ResetUserData().
172    */
173   void *userdata;
174
175   /*! Default constructor.*/
176   inline SVertex()
177   {
178     _Id = 0;
179     userdata = NULL;
180     _Shape = NULL;
181     _pViewVertex = 0;
182     _curvature_info = 0;
183   }
184
185   /*! Builds a SVertex from 3D coordinates and an Id. */
186   inline SVertex(const Vec3r &iPoint3D, const Id &id)
187   {
188     _Point3D = iPoint3D;
189     _Id = id;
190     userdata = NULL;
191     _Shape = NULL;
192     _pViewVertex = 0;
193     _curvature_info = 0;
194   }
195
196   /*! Copy constructor. */
197   inline SVertex(SVertex &iBrother)
198   {
199     _Id = iBrother._Id;
200     _Point3D = iBrother.point3D();
201     _Point2D = iBrother.point2D();
202     _Normals = iBrother._Normals;
203     _FEdges = iBrother.fedges();
204     _Shape = iBrother.shape();
205     _pViewVertex = iBrother._pViewVertex;
206     if (!(iBrother._curvature_info)) {
207       _curvature_info = 0;
208     }
209     else {
210       _curvature_info = new CurvatureInfo(*(iBrother._curvature_info));
211     }
212     iBrother.userdata = this;
213     userdata = 0;
214   }
215
216   /*! Destructor. */
217   virtual ~SVertex()
218   {
219     if (_curvature_info) {
220       delete _curvature_info;
221     }
222   }
223
224   /*! Cloning method. */
225   virtual SVertex *duplicate()
226   {
227     SVertex *clone = new SVertex(*this);
228     return clone;
229   }
230
231   /*! operator == */
232   virtual bool operator==(const SVertex &iBrother)
233   {
234     return ((_Point2D == iBrother._Point2D) && (_Point3D == iBrother._Point3D));
235   }
236
237   /* accessors */
238   inline const Vec3r &point3D() const
239   {
240     return _Point3D;
241   }
242
243   inline const Vec3r &point2D() const
244   {
245     return _Point2D;
246   }
247
248   /*! Returns the set of normals for this Vertex.
249    *  In a smooth surface, a vertex has exactly one normal.
250    *  In a sharp surface, a vertex can have any number of normals.
251    */
252   inline set<Vec3r> normals()
253   {
254     return _Normals;
255   }
256
257   /*! Returns the number of different normals for this vertex. */
258   inline unsigned normalsSize() const
259   {
260     return _Normals.size();
261   }
262
263   inline const vector<FEdge *> &fedges()
264   {
265     return _FEdges;
266   }
267
268   inline fedges_container::iterator fedges_begin()
269   {
270     return _FEdges.begin();
271   }
272
273   inline fedges_container::iterator fedges_end()
274   {
275     return _FEdges.end();
276   }
277
278   inline SShape *shape()
279   {
280     return _Shape;
281   }
282
283   inline real z() const
284   {
285     return _Point2D[2];
286   }
287
288   /*! If this SVertex is also a ViewVertex, this method returns a pointer onto this ViewVertex.
289    *  0 is returned otherwise.
290    */
291   inline ViewVertex *viewvertex()
292   {
293     return _pViewVertex;
294   }
295
296   /*! modifiers */
297   /*! Sets the 3D coordinates of the SVertex. */
298   inline void setPoint3D(const Vec3r &iPoint3D)
299   {
300     _Point3D = iPoint3D;
301   }
302
303   /*! Sets the 3D projected coordinates of the SVertex. */
304   inline void setPoint2D(const Vec3r &iPoint2D)
305   {
306     _Point2D = iPoint2D;
307   }
308
309   /*! Adds a normal to the Svertex's set of normals. If the same normal is already in the set,
310    * nothing changes. */
311   inline void AddNormal(const Vec3r &iNormal)
312   {
313     _Normals.insert(iNormal);  // if iNormal in the set already exists, nothing is done
314   }
315
316   void setCurvatureInfo(CurvatureInfo *ci)
317   {
318     if (_curvature_info) {  // Q. is this an error condition? (T.K. 02-May-2011)
319       delete _curvature_info;
320     }
321     _curvature_info = ci;
322   }
323
324   const CurvatureInfo *getCurvatureInfo() const
325   {
326     return _curvature_info;
327   }
328
329 #if 0
330   /* Fredo's normal and curvature*/
331   void setCurvatureFredo(real c)
332   {
333     _curvatureFredo = c;
334   }
335
336   void setDirectionFredo(Vec2r d)
337   {
338     _directionFredo = d;
339   }
340
341   real curvatureFredo()
342   {
343     return _curvatureFredo;
344   }
345
346   const Vec2r directionFredo()
347   {
348     return _directionFredo;
349   }
350 #endif
351
352   /*! Sets the Id */
353   inline void setId(const Id &id)
354   {
355     _Id = id;
356   }
357
358   inline void setFEdges(const vector<FEdge *> &iFEdges)
359   {
360     _FEdges = iFEdges;
361   }
362
363   inline void setShape(SShape *iShape)
364   {
365     _Shape = iShape;
366   }
367
368   inline void setViewVertex(ViewVertex *iViewVertex)
369   {
370     _pViewVertex = iViewVertex;
371   }
372
373   /*! Add an FEdge to the list of edges emanating from this SVertex. */
374   inline void AddFEdge(FEdge *iFEdge)
375   {
376     _FEdges.push_back(iFEdge);
377   }
378
379   /*! Remove an FEdge from the list of edges emanating from this SVertex. */
380   inline void RemoveFEdge(FEdge *iFEdge)
381   {
382     for (vector<FEdge *>::iterator fe = _FEdges.begin(), fend = _FEdges.end(); fe != fend; fe++) {
383       if (iFEdge == (*fe)) {
384         _FEdges.erase(fe);
385         break;
386       }
387     }
388   }
389
390   /* replaces edge 1 by edge 2 in the list of edges */
391   inline void Replace(FEdge *e1, FEdge *e2)
392   {
393     vector<FEdge *>::iterator insertedfe;
394     for (vector<FEdge *>::iterator fe = _FEdges.begin(), fend = _FEdges.end(); fe != fend; fe++) {
395       if ((*fe) == e1) {
396         insertedfe = _FEdges.insert(fe, e2);  // inserts e2 before fe.
397         // returns an iterator pointing toward e2. fe is invalidated.
398         // we want to remove e1, but we can't use fe anymore:
399         ++insertedfe;  // insertedfe points now to e1
400         _FEdges.erase(insertedfe);
401         return;
402       }
403     }
404   }
405
406  public:
407   /* Information access interface */
408   FEdge *fedge();  // for non T vertex
409
410   inline const Vec3r &point2d() const
411   {
412     return point2D();
413   }
414
415   inline const Vec3r &point3d() const
416   {
417     return point3D();
418   }
419
420   inline Vec3r normal() const
421   {
422     if (_Normals.size() == 1) {
423       return (*(_Normals.begin()));
424     }
425     Exception::raiseException();
426     return *(_Normals.begin());
427   }
428
429   // Material material() const ;
430   Id shape_id() const;
431   const SShape *shape() const;
432   float shape_importance() const;
433
434   const int qi() const;
435   occluder_container::const_iterator occluders_begin() const;
436   occluder_container::const_iterator occluders_end() const;
437   bool occluders_empty() const;
438   int occluders_size() const;
439   const Polygon3r &occludee() const;
440   const SShape *occluded_shape() const;
441   const bool occludee_empty() const;
442   real z_discontinuity() const;
443 #if 0
444   inline float local_average_depth() const;
445   inline float local_depth_variance() const;
446   inline real local_average_density(float sigma = 2.3f) const;
447   inline Vec3r shaded_color() const;
448   inline Vec3r orientation2d() const;
449   inline Vec3r orientation3d() const;
450   inline Vec3r curvature2d_as_vector() const;
451   /*! angle in radians */
452   inline real curvature2d_as_angle() const;
453 #endif
454
455 #ifdef WITH_CXX_GUARDEDALLOC
456   MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SVertex")
457 #endif
458 };
459
460 /**********************************/
461 /*                                */
462 /*                                */
463 /*             FEdge              */
464 /*                                */
465 /*                                */
466 /**********************************/
467
468 class ViewEdge;
469
470 /*! Base Class for feature edges.
471  *  This FEdge can represent a silhouette, a crease, a ridge/valley, a border or a suggestive
472  * contour. For silhouettes,  the FEdge is oriented such as, the visible face lies on the left of
473  * the edge. For borders, the FEdge is oriented such as, the face lies on the left of the edge. An
474  * FEdge can represent an initial edge of the mesh or runs across a face of the initial mesh
475  * depending on the smoothness or sharpness of the mesh. This class is specialized into a smooth
476  * and a sharp version since their properties slightly vary from one to the other.
477  */
478 class FEdge : public Interface1D {
479  public:  // Implementation of Interface0D
480   /*! Returns the string "FEdge". */
481   virtual string getExactTypeName() const
482   {
483     return "FEdge";
484   }
485
486   // Data access methods
487
488   /*! Returns the 2D length of the FEdge. */
489   virtual real getLength2D() const
490   {
491     if (!_VertexA || !_VertexB) {
492       return 0;
493     }
494     return (_VertexB->getPoint2D() - _VertexA->getPoint2D()).norm();
495   }
496
497   /*! Returns the Id of the FEdge. */
498   virtual Id getId() const
499   {
500     return _Id;
501   }
502
503  public:
504   // An edge can only be of one kind (SILHOUETTE or BORDER, etc...)
505   // For an multi-nature edge there must be several different FEdge.
506   //  DEBUG:
507   //  Vec3r A;
508   //  Vec3r u;
509   //  vector<Polygon3r> _Occludees;
510   //  Vec3r intersection;
511   //  vector<Vec3i> _Cells;
512
513  protected:
514   SVertex *_VertexA;
515   SVertex *_VertexB;
516   Id _Id;
517   Nature::EdgeNature _Nature;
518   // vector<Polygon3r> _Occluders; // visibility // NOT HANDLED BY THE COPY CONSTRUCTOR!!
519
520   FEdge *_NextEdge;  // next edge on the chain
521   FEdge *_PreviousEdge;
522   ViewEdge *_ViewEdge;
523   // Sometimes we need to deport the visibility computation onto another edge. For example the
524   // exact edges use edges of the mesh to compute their visibility
525
526   Polygon3r _aFace;  // The occluded face which lies on the right of a silhouette edge
527   Vec3r _occludeeIntersection;
528   bool _occludeeEmpty;
529
530   bool _isSmooth;
531
532   bool _isInImage;
533
534   bool _isTemporary;
535
536  public:
537   /*! A field that can be used by the user to store any data.
538    *  This field must be reset afterwards using ResetUserData().
539    */
540   void *userdata;
541
542   /*! Default constructor */
543   inline FEdge()
544   {
545     userdata = NULL;
546     _VertexA = NULL;
547     _VertexB = NULL;
548     _Nature = Nature::NO_FEATURE;
549     _NextEdge = NULL;
550     _PreviousEdge = NULL;
551     _ViewEdge = NULL;
552     //_hasVisibilityPoint = false;
553     _occludeeEmpty = true;
554     _isSmooth = false;
555     _isInImage = true;
556     _isTemporary = false;
557   }
558
559   /*! Builds an FEdge going from vA to vB. */
560   inline FEdge(SVertex *vA, SVertex *vB)
561   {
562     userdata = NULL;
563     _VertexA = vA;
564     _VertexB = vB;
565     _Nature = Nature::NO_FEATURE;
566     _NextEdge = NULL;
567     _PreviousEdge = NULL;
568     _ViewEdge = NULL;
569     //_hasVisibilityPoint = false;
570     _occludeeEmpty = true;
571     _isSmooth = false;
572     _isInImage = true;
573     _isTemporary = false;
574   }
575
576   /*! Copy constructor */
577   inline FEdge(FEdge &iBrother)
578   {
579     _VertexA = iBrother.vertexA();
580     _VertexB = iBrother.vertexB();
581     _NextEdge = iBrother.nextEdge();
582     _PreviousEdge = iBrother._PreviousEdge;
583     _Nature = iBrother.getNature();
584     _Id = iBrother._Id;
585     _ViewEdge = iBrother._ViewEdge;
586     //_hasVisibilityPoint = iBrother._hasVisibilityPoint;
587     //_VisibilityPointA = iBrother._VisibilityPointA;
588     //_VisibilityPointB = iBrother._VisibilityPointB;
589     _aFace = iBrother._aFace;
590     _occludeeEmpty = iBrother._occludeeEmpty;
591     _isSmooth = iBrother._isSmooth;
592     _isInImage = iBrother._isInImage;
593     _isTemporary = iBrother._isTemporary;
594     iBrother.userdata = this;
595     userdata = 0;
596   }
597
598   /*! Destructor */
599   virtual ~FEdge()
600   {
601   }
602
603   /*! Cloning method. */
604   virtual FEdge *duplicate()
605   {
606     FEdge *clone = new FEdge(*this);
607     return clone;
608   }
609
610   /* accessors */
611   /*! Returns the first SVertex. */
612   inline SVertex *vertexA()
613   {
614     return _VertexA;
615   }
616
617   /*! Returns the second SVertex. */
618   inline SVertex *vertexB()
619   {
620     return _VertexB;
621   }
622
623   /*! Returns the first SVertex if i=0, the second SVertex if i=1. */
624   inline SVertex *operator[](const unsigned short int &i) const
625   {
626     return (i % 2 == 0) ? _VertexA : _VertexB;
627   }
628
629   /*! Returns the nature of the FEdge. */
630   inline Nature::EdgeNature getNature() const
631   {
632     return _Nature;
633   }
634
635   /*! Returns the FEdge following this one in the ViewEdge.
636    *  If this FEdge is the last of the ViewEdge, 0 is returned.
637    */
638   inline FEdge *nextEdge()
639   {
640     return _NextEdge;
641   }
642
643   /*! Returns the Edge preceding this one in the ViewEdge.
644    *  If this FEdge is the first one of the ViewEdge, 0 is returned.
645    */
646   inline FEdge *previousEdge()
647   {
648     return _PreviousEdge;
649   }
650
651   inline SShape *shape()
652   {
653     return _VertexA->shape();
654   }
655
656 #if 0
657   inline int invisibility() const
658   {
659     return _Occluders.size();
660   }
661 #endif
662
663   int invisibility() const;
664
665 #if 0
666   inline const vector<Polygon3r> &occluders() const
667   {
668     return _Occluders;
669   }
670 #endif
671
672   /*! Returns a pointer to the ViewEdge to which this FEdge belongs to. */
673   inline ViewEdge *viewedge() const
674   {
675     return _ViewEdge;
676   }
677
678   inline Vec3r center3d()
679   {
680     return Vec3r((_VertexA->point3D() + _VertexB->point3D()) / 2.0);
681   }
682
683   inline Vec3r center2d()
684   {
685     return Vec3r((_VertexA->point2D() + _VertexB->point2D()) / 2.0);
686   }
687
688 #if 0
689   inline bool hasVisibilityPoint() const
690   {
691     return _hasVisibilityPoint;
692   }
693
694   inline Vec3r visibilityPointA() const
695   {
696     return _VisibilityPointA;
697   }
698
699   inline Vec3r visibilityPointB() const
700   {
701     return _VisibilityPointB;
702   }
703 #endif
704
705   inline const Polygon3r &aFace() const
706   {
707     return _aFace;
708   }
709
710   inline const Vec3r &getOccludeeIntersection()
711   {
712     return _occludeeIntersection;
713   }
714
715   inline bool getOccludeeEmpty()
716   {
717     return _occludeeEmpty;
718   }
719
720   /*! Returns true if this FEdge is a smooth FEdge. */
721   inline bool isSmooth() const
722   {
723     return _isSmooth;
724   }
725
726   inline bool isInImage() const
727   {
728     return _isInImage;
729   }
730
731   inline bool isTemporary() const
732   {
733     return _isTemporary;
734   }
735
736   /* modifiers */
737   /*! Sets the first SVertex. */
738   inline void setVertexA(SVertex *vA)
739   {
740     _VertexA = vA;
741   }
742
743   /*! Sets the second SVertex. */
744   inline void setVertexB(SVertex *vB)
745   {
746     _VertexB = vB;
747   }
748
749   /*! Sets the FEdge Id . */
750   inline void setId(const Id &id)
751   {
752     _Id = id;
753   }
754
755   /*! Sets the pointer to the next FEdge. */
756   inline void setNextEdge(FEdge *iEdge)
757   {
758     _NextEdge = iEdge;
759   }
760
761   /*! Sets the pointer to the previous FEdge. */
762   inline void setPreviousEdge(FEdge *iEdge)
763   {
764     _PreviousEdge = iEdge;
765   }
766
767   /*! Sets the nature of this FEdge. */
768   inline void setNature(Nature::EdgeNature iNature)
769   {
770     _Nature = iNature;
771   }
772
773 #if 0
774   inline void AddOccluder(Polygon3r &iPolygon)
775   {
776     _Occluders.push_back(iPolygon);
777   }
778 #endif
779
780   /*! Sets the ViewEdge to which this FEdge belongs to. */
781   inline void setViewEdge(ViewEdge *iViewEdge)
782   {
783     _ViewEdge = iViewEdge;
784   }
785
786 #if 0
787   inline void setHasVisibilityPoint(bool iBool)
788   {
789     _hasVisibilityPoint = iBool;
790   }
791
792   inline void setVisibilityPointA(const Vec3r &iPoint)
793   {
794     _VisibilityPointA = iPoint;
795   }
796
797   inline void setVisibilityPointB(const Vec3r &iPoint)
798   {
799     _VisibilityPointB = iPoint;
800   }
801 #endif
802
803   inline void setaFace(Polygon3r &iFace)
804   {
805     _aFace = iFace;
806   }
807
808   inline void setOccludeeIntersection(const Vec3r &iPoint)
809   {
810     _occludeeIntersection = iPoint;
811   }
812
813   inline void setOccludeeEmpty(bool iempty)
814   {
815     _occludeeEmpty = iempty;
816   }
817
818   /*! Sets the flag telling whether this FEdge is smooth or sharp.
819    *  true for Smooth, false for Sharp.
820    */
821   inline void setSmooth(bool iFlag)
822   {
823     _isSmooth = iFlag;
824   }
825
826   inline void setIsInImage(bool iFlag)
827   {
828     _isInImage = iFlag;
829   }
830
831   inline void setTemporary(bool iFlag)
832   {
833     _isTemporary = iFlag;
834   }
835
836   /* checks whether two FEdge have a common vertex.
837    *  Returns a pointer on the common vertex if it exists, NULL otherwise.
838    */
839   static inline SVertex *CommonVertex(FEdge *iEdge1, FEdge *iEdge2)
840   {
841     if ((NULL == iEdge1) || (NULL == iEdge2)) {
842       return NULL;
843     }
844
845     SVertex *sv1 = iEdge1->vertexA();
846     SVertex *sv2 = iEdge1->vertexB();
847     SVertex *sv3 = iEdge2->vertexA();
848     SVertex *sv4 = iEdge2->vertexB();
849
850     if ((sv1 == sv3) || (sv1 == sv4)) {
851       return sv1;
852     }
853     else if ((sv2 == sv3) || (sv2 == sv4)) {
854       return sv2;
855     }
856
857     return NULL;
858   }
859
860   inline const SVertex *min2d() const
861   {
862     if (_VertexA->point2D() < _VertexB->point2D()) {
863       return _VertexA;
864     }
865     else {
866       return _VertexB;
867     }
868   }
869
870   inline const SVertex *max2d() const
871   {
872     if (_VertexA->point2D() < _VertexB->point2D()) {
873       return _VertexB;
874     }
875     else {
876       return _VertexA;
877     }
878   }
879
880   /* Information access interface */
881
882   // Material material() const;
883   Id shape_id() const;
884   const SShape *shape() const;
885   float shape_importance() const;
886
887   inline const int qi() const
888   {
889     return invisibility();
890   }
891
892   occluder_container::const_iterator occluders_begin() const;
893   occluder_container::const_iterator occluders_end() const;
894   bool occluders_empty() const;
895   int occluders_size() const;
896
897   inline const Polygon3r &occludee() const
898   {
899     return aFace();
900   }
901
902   const SShape *occluded_shape() const;
903
904 #if 0
905   inline const bool occludee_empty() const
906   {
907     return _occludeeEmpty;
908   }
909 #endif
910
911   const bool occludee_empty() const;
912   real z_discontinuity() const;
913
914 #if 0
915   inline float local_average_depth(int iCombination = 0) const;
916   inline float local_depth_variance(int iCombination = 0) const;
917   inline real local_average_density(float sigma = 2.3f, int iCombination = 0) const;
918   inline Vec3r shaded_color(int iCombination = 0) const
919   {
920   }
921 #endif
922
923   int viewedge_nature() const;
924
925   // float viewedge_length() const;
926
927   inline Vec3r orientation2d() const
928   {
929     return Vec3r(_VertexB->point2d() - _VertexA->point2d());
930   }
931
932   inline Vec3r orientation3d() const
933   {
934     return Vec3r(_VertexB->point3d() - _VertexA->point3d());
935   }
936
937 #if 0
938   inline real curvature2d() const
939   {
940     return viewedge()->curvature2d((_VertexA->point2d() + _VertexB->point2d()) / 2.0);
941   }
942
943   inline Vec3r curvature2d_as_vector(int iCombination = 0) const;
944
945   /* angle in degrees*/
946   inline real curvature2d_as_angle(int iCombination = 0) const;
947 #endif
948
949   // Iterator access (Interface1D)
950   /*! Returns an iterator over the 2 (!) SVertex pointing to the first SVertex. */
951   virtual inline Interface0DIterator verticesBegin();
952
953   /*! Returns an iterator over the 2 (!) SVertex pointing after the last SVertex. */
954   virtual inline Interface0DIterator verticesEnd();
955
956   /*! Returns an iterator over the FEdge points, pointing to the first point. The difference with
957    * verticesBegin() is that here we can iterate over points of the FEdge at a any given sampling.
958    *  Indeed, for each iteration, a virtual point is created.
959    *  \param t:
960    *    The sampling with which we want to iterate over points of this FEdge.
961    */
962   virtual inline Interface0DIterator pointsBegin(float t = 0.0f);
963
964   /*! Returns an iterator over the FEdge points, pointing after the last point. The difference with
965    * verticesEnd() is that here we can iterate over points of the FEdge at a any given sampling.
966    *  Indeed, for each iteration, a virtual point is created.
967    *  \param t:
968    *    The sampling with which we want to iterate over points of this FEdge.
969    */
970   virtual inline Interface0DIterator pointsEnd(float t = 0.0f);
971
972 #ifdef WITH_CXX_GUARDEDALLOC
973   MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:FEdge")
974 #endif
975 };
976
977 //
978 // SVertexIterator
979 //
980 /////////////////////////////////////////////////
981
982 namespace FEdgeInternal {
983
984 class SVertexIterator : public Interface0DIteratorNested {
985  public:
986   SVertexIterator()
987   {
988     _vertex = NULL;
989     _edge = NULL;
990   }
991
992   SVertexIterator(const SVertexIterator &vi)
993   {
994     _vertex = vi._vertex;
995     _edge = vi._edge;
996   }
997
998   SVertexIterator(SVertex *v, FEdge *edge)
999   {
1000     _vertex = v;
1001     _edge = edge;
1002   }
1003
1004   SVertexIterator &operator=(const SVertexIterator &vi)
1005   {
1006     _vertex = vi._vertex;
1007     _edge = vi._edge;
1008     return *this;
1009   }
1010
1011   virtual string getExactTypeName() const
1012   {
1013     return "SVertexIterator";
1014   }
1015
1016   virtual SVertex &operator*()
1017   {
1018     return *_vertex;
1019   }
1020
1021   virtual SVertex *operator->()
1022   {
1023     return &(operator*());
1024   }
1025
1026   virtual SVertexIterator &operator++()
1027   {
1028     increment();
1029     return *this;
1030   }
1031
1032   virtual SVertexIterator operator++(int)
1033   {
1034     SVertexIterator ret(*this);
1035     increment();
1036     return ret;
1037   }
1038
1039   virtual SVertexIterator &operator--()
1040   {
1041     decrement();
1042     return *this;
1043   }
1044
1045   virtual SVertexIterator operator--(int)
1046   {
1047     SVertexIterator ret(*this);
1048     decrement();
1049     return ret;
1050   }
1051
1052   virtual int increment()
1053   {
1054     if (_vertex == _edge->vertexB()) {
1055       _vertex = 0;
1056       return 0;
1057     }
1058     _vertex = _edge->vertexB();
1059     return 0;
1060   }
1061
1062   virtual int decrement()
1063   {
1064     if (_vertex == _edge->vertexA()) {
1065       _vertex = 0;
1066       return 0;
1067     }
1068     _vertex = _edge->vertexA();
1069     return 0;
1070   }
1071
1072   virtual bool isBegin() const
1073   {
1074     return _vertex == _edge->vertexA();
1075   }
1076
1077   virtual bool isEnd() const
1078   {
1079     return _vertex == _edge->vertexB();
1080   }
1081
1082   virtual bool operator==(const Interface0DIteratorNested &it) const
1083   {
1084     const SVertexIterator *it_exact = dynamic_cast<const SVertexIterator *>(&it);
1085     if (!it_exact) {
1086       return false;
1087     }
1088     return ((_vertex == it_exact->_vertex) && (_edge == it_exact->_edge));
1089   }
1090
1091   virtual float t() const
1092   {
1093     if (_vertex == _edge->vertexA()) {
1094       return 0.0f;
1095     }
1096     return ((float)_edge->getLength2D());
1097   }
1098   virtual float u() const
1099   {
1100     if (_vertex == _edge->vertexA()) {
1101       return 0.0f;
1102     }
1103     return 1.0f;
1104   }
1105
1106   virtual SVertexIterator *copy() const
1107   {
1108     return new SVertexIterator(*this);
1109   }
1110
1111  private:
1112   SVertex *_vertex;
1113   FEdge *_edge;
1114 };
1115
1116 }  // end of namespace FEdgeInternal
1117
1118 // Iterator access (implementation)
1119
1120 Interface0DIterator FEdge::verticesBegin()
1121 {
1122   Interface0DIterator ret(new FEdgeInternal::SVertexIterator(_VertexA, this));
1123   return ret;
1124 }
1125
1126 Interface0DIterator FEdge::verticesEnd()
1127 {
1128   Interface0DIterator ret(new FEdgeInternal::SVertexIterator(0, this));
1129   return ret;
1130 }
1131
1132 Interface0DIterator FEdge::pointsBegin(float /*t*/)
1133 {
1134   return verticesBegin();
1135 }
1136
1137 Interface0DIterator FEdge::pointsEnd(float /*t*/)
1138 {
1139   return verticesEnd();
1140 }
1141
1142 /*! Class defining a sharp FEdge. A Sharp FEdge corresponds to an initial edge of the input mesh.
1143  *  It can be a silhouette, a crease or a border. If it is a crease edge, then it is borded
1144  *  by two faces of the mesh. Face a lies on its right whereas Face b lies on its left.
1145  *  If it is a border edge, then it doesn't have any face on its right, and thus Face a = 0.
1146  */
1147 class FEdgeSharp : public FEdge {
1148  protected:
1149   Vec3r _aNormal;  // When following the edge, normal of the right face
1150   Vec3r _bNormal;  // When following the edge, normal of the left face
1151   unsigned _aFrsMaterialIndex;
1152   unsigned _bFrsMaterialIndex;
1153   bool _aFaceMark;
1154   bool _bFaceMark;
1155
1156  public:
1157   /*! Returns the string "FEdgeSharp" . */
1158   virtual string getExactTypeName() const
1159   {
1160     return "FEdgeSharp";
1161   }
1162
1163   /*! Default constructor. */
1164   inline FEdgeSharp() : FEdge()
1165   {
1166     _aFrsMaterialIndex = _bFrsMaterialIndex = 0;
1167     _aFaceMark = _bFaceMark = false;
1168   }
1169
1170   /*! Builds an FEdgeSharp going from vA to vB. */
1171   inline FEdgeSharp(SVertex *vA, SVertex *vB) : FEdge(vA, vB)
1172   {
1173     _aFrsMaterialIndex = _bFrsMaterialIndex = 0;
1174     _aFaceMark = _bFaceMark = false;
1175   }
1176
1177   /*! Copy constructor. */
1178   inline FEdgeSharp(FEdgeSharp &iBrother) : FEdge(iBrother)
1179   {
1180     _aNormal = iBrother._aNormal;
1181     _bNormal = iBrother._bNormal;
1182     _aFrsMaterialIndex = iBrother._aFrsMaterialIndex;
1183     _bFrsMaterialIndex = iBrother._bFrsMaterialIndex;
1184     _aFaceMark = iBrother._aFaceMark;
1185     _bFaceMark = iBrother._bFaceMark;
1186   }
1187
1188   /*! Destructor. */
1189   virtual ~FEdgeSharp()
1190   {
1191   }
1192
1193   /*! Cloning method. */
1194   virtual FEdge *duplicate()
1195   {
1196     FEdge *clone = new FEdgeSharp(*this);
1197     return clone;
1198   }
1199
1200   /*! Returns the normal to the face lying on the right of the FEdge. If this FEdge is a border,
1201    *  it has no Face on its right and therefore, no normal.
1202    */
1203   inline const Vec3r &normalA()
1204   {
1205     return _aNormal;
1206   }
1207
1208   /*! Returns the normal to the face lying on the left of the FEdge. */
1209   inline const Vec3r &normalB()
1210   {
1211     return _bNormal;
1212   }
1213
1214   /*! Returns the index of the material of the face lying on the
1215    *  right of the FEdge. If this FEdge is a border,
1216    *  it has no Face on its right and therefore, no material.
1217    */
1218   inline unsigned aFrsMaterialIndex() const
1219   {
1220     return _aFrsMaterialIndex;
1221   }
1222
1223   /*! Returns the material of the face lying on the right of the FEdge. If this FEdge is a border,
1224    *  it has no Face on its right and therefore, no material.
1225    */
1226   const FrsMaterial &aFrsMaterial() const;
1227
1228   /*! Returns the index of the material of the face lying on the left of the FEdge. */
1229   inline unsigned bFrsMaterialIndex() const
1230   {
1231     return _bFrsMaterialIndex;
1232   }
1233
1234   /*! Returns the  material of the face lying on the left of the FEdge. */
1235   const FrsMaterial &bFrsMaterial() const;
1236
1237   /*! Returns the face mark of the face lying on the right of the FEdge.
1238    *  If this FEdge is a border, it has no Face on its right and thus false is returned.
1239    */
1240   inline bool aFaceMark() const
1241   {
1242     return _aFaceMark;
1243   }
1244
1245   /*! Returns the face mark of the face lying on the left of the FEdge. */
1246   inline bool bFaceMark() const
1247   {
1248     return _bFaceMark;
1249   }
1250
1251   /*! Sets the normal to the face lying on the right of the FEdge. */
1252   inline void setNormalA(const Vec3r &iNormal)
1253   {
1254     _aNormal = iNormal;
1255   }
1256
1257   /*! Sets the normal to the face lying on the left of the FEdge. */
1258   inline void setNormalB(const Vec3r &iNormal)
1259   {
1260     _bNormal = iNormal;
1261   }
1262
1263   /*! Sets the index of the material lying on the right of the FEdge.*/
1264   inline void setaFrsMaterialIndex(unsigned i)
1265   {
1266     _aFrsMaterialIndex = i;
1267   }
1268
1269   /*! Sets the index of the material lying on the left of the FEdge.*/
1270   inline void setbFrsMaterialIndex(unsigned i)
1271   {
1272     _bFrsMaterialIndex = i;
1273   }
1274
1275   /*! Sets the face mark of the face lying on the right of the FEdge. */
1276   inline void setaFaceMark(bool iFaceMark)
1277   {
1278     _aFaceMark = iFaceMark;
1279   }
1280
1281   /*! Sets the face mark of the face lying on the left of the FEdge. */
1282   inline void setbFaceMark(bool iFaceMark)
1283   {
1284     _bFaceMark = iFaceMark;
1285   }
1286
1287 #ifdef WITH_CXX_GUARDEDALLOC
1288   MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:FEdgeSharp")
1289 #endif
1290 };
1291
1292 /*! Class defining a smooth edge. This kind of edge typically runs across a face of the input mesh.
1293  * It can be a silhouette, a ridge or valley, a suggestive contour.
1294  */
1295 class FEdgeSmooth : public FEdge {
1296  protected:
1297   Vec3r _Normal;
1298   unsigned _FrsMaterialIndex;
1299 #if 0
1300   bool _hasVisibilityPoint;
1301   Vec3r _VisibilityPointA;  // The edge on which the visibility will be computed represented
1302   Vec3r _VisibilityPointB;  // using its 2 extremity points A and B
1303 #endif
1304   void *_Face;  // In case of exact silhouette, Face is the WFace crossed by Fedge
1305                 // NOT HANDLED BY THE COPY CONSTRUCTEUR
1306   bool _FaceMark;
1307
1308  public:
1309   /*! Returns the string "FEdgeSmooth" . */
1310   virtual string getExactTypeName() const
1311   {
1312     return "FEdgeSmooth";
1313   }
1314
1315   /*! Default constructor. */
1316   inline FEdgeSmooth() : FEdge()
1317   {
1318     _Face = NULL;
1319     _FaceMark = false;
1320     _FrsMaterialIndex = 0;
1321     _isSmooth = true;
1322   }
1323
1324   /*! Builds an FEdgeSmooth going from vA to vB. */
1325   inline FEdgeSmooth(SVertex *vA, SVertex *vB) : FEdge(vA, vB)
1326   {
1327     _Face = NULL;
1328     _FaceMark = false;
1329     _FrsMaterialIndex = 0;
1330     _isSmooth = true;
1331   }
1332
1333   /*! Copy constructor. */
1334   inline FEdgeSmooth(FEdgeSmooth &iBrother) : FEdge(iBrother)
1335   {
1336     _Normal = iBrother._Normal;
1337     _Face = iBrother._Face;
1338     _FaceMark = iBrother._FaceMark;
1339     _FrsMaterialIndex = iBrother._FrsMaterialIndex;
1340     _isSmooth = true;
1341   }
1342
1343   /*! Destructor. */
1344   virtual ~FEdgeSmooth()
1345   {
1346   }
1347
1348   /*! Cloning method. */
1349   virtual FEdge *duplicate()
1350   {
1351     FEdge *clone = new FEdgeSmooth(*this);
1352     return clone;
1353   }
1354
1355   inline void *face() const
1356   {
1357     return _Face;
1358   }
1359
1360   /*! Returns the face mark of the face it is running across. */
1361   inline bool faceMark() const
1362   {
1363     return _FaceMark;
1364   }
1365
1366   /*! Returns the normal to the Face it is running across. */
1367   inline const Vec3r &normal()
1368   {
1369     return _Normal;
1370   }
1371
1372   /*! Returns the index of the material of the face it is running across. */
1373   inline unsigned frs_materialIndex() const
1374   {
1375     return _FrsMaterialIndex;
1376   }
1377
1378   /*! Returns the material of the face it is running across. */
1379   const FrsMaterial &frs_material() const;
1380
1381   inline void setFace(void *iFace)
1382   {
1383     _Face = iFace;
1384   }
1385
1386   /*! Sets the face mark of the face it is running across. */
1387   inline void setFaceMark(bool iFaceMark)
1388   {
1389     _FaceMark = iFaceMark;
1390   }
1391
1392   /*! Sets the normal to the Face it is running across. */
1393   inline void setNormal(const Vec3r &iNormal)
1394   {
1395     _Normal = iNormal;
1396   }
1397
1398   /*! Sets the index of the material of the face it is running across. */
1399   inline void setFrsMaterialIndex(unsigned i)
1400   {
1401     _FrsMaterialIndex = i;
1402   }
1403
1404 #ifdef WITH_CXX_GUARDEDALLOC
1405   MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:FEdgeSmooth")
1406 #endif
1407 };
1408
1409 /**********************************/
1410 /*                                */
1411 /*                                */
1412 /*             SShape             */
1413 /*                                */
1414 /*                                */
1415 /**********************************/
1416
1417 /*! Class to define a feature shape. It is the gathering of feature elements from an identified
1418  * input shape */
1419 class SShape {
1420  private:
1421   vector<FEdge *> _chains;          // list of fedges that are chains starting points.
1422   vector<SVertex *> _verticesList;  // list of all vertices
1423   vector<FEdge *> _edgesList;       // list of all edges
1424   Id _Id;
1425   string _Name;
1426   string _LibraryPath;
1427   BBox<Vec3r> _BBox;
1428   vector<FrsMaterial> _FrsMaterials;
1429
1430   float _importance;
1431
1432   ViewShape *_ViewShape;
1433
1434  public:
1435   /*! A field that can be used by the user to store any data.
1436    *  This field must be reset afterwards using ResetUserData().
1437    */
1438   void *userdata;  // added by E.T.
1439
1440   /*! Default constructor */
1441   inline SShape()
1442   {
1443     userdata = NULL;
1444     _importance = 0.0f;
1445     _ViewShape = NULL;
1446   }
1447
1448   /*! Copy constructor */
1449   inline SShape(SShape &iBrother)
1450   {
1451     userdata = NULL;
1452     _Id = iBrother._Id;
1453     _Name = iBrother._Name;
1454     _LibraryPath = iBrother._LibraryPath;
1455     _BBox = iBrother.bbox();
1456     _FrsMaterials = iBrother._FrsMaterials;
1457     _importance = iBrother._importance;
1458     _ViewShape = iBrother._ViewShape;
1459
1460     //---------
1461     // vertices
1462     //---------
1463     vector<SVertex *>::iterator sv, svend;
1464     vector<SVertex *> &verticesList = iBrother.getVertexList();
1465     for (sv = verticesList.begin(), svend = verticesList.end(); sv != svend; sv++) {
1466       SVertex *newv = new SVertex(*(*sv));
1467       newv->setShape(this);
1468       _verticesList.push_back(newv);
1469     }
1470
1471     //------
1472     // edges
1473     //------
1474     vector<FEdge *>::iterator e, eend;
1475     vector<FEdge *> &edgesList = iBrother.getEdgeList();
1476     for (e = edgesList.begin(), eend = edgesList.end(); e != eend; e++) {
1477       FEdge *newe = (*e)->duplicate();
1478       _edgesList.push_back(newe);
1479     }
1480
1481     //-------------------------
1482     // starting chain edges
1483     //-------------------------
1484     vector<FEdge *>::iterator fe, fend;
1485     vector<FEdge *> &fedges = iBrother.getChains();
1486     for (fe = fedges.begin(), fend = fedges.end(); fe != fend; fe++) {
1487       _chains.push_back((FEdge *)((*fe)->userdata));
1488     }
1489
1490     //-------------------------
1491     // remap edges in vertices:
1492     //-------------------------
1493     for (sv = _verticesList.begin(), svend = _verticesList.end(); sv != svend; sv++) {
1494       const vector<FEdge *> &fedgeList = (*sv)->fedges();
1495       vector<FEdge *> newfedgelist;
1496       for (vector<FEdge *>::const_iterator fed = fedgeList.begin(), fedend = fedgeList.end();
1497            fed != fedend;
1498            fed++) {
1499         FEdge *current = *fed;
1500         newfedgelist.push_back((FEdge *)current->userdata);
1501       }
1502       (*sv)->setFEdges(newfedgelist);
1503     }
1504
1505     //-------------------------------------
1506     // remap vertices and nextedge in edges:
1507     //-------------------------------------
1508     for (e = _edgesList.begin(), eend = _edgesList.end(); e != eend; e++) {
1509       (*e)->setVertexA((SVertex *)((*e)->vertexA()->userdata));
1510       (*e)->setVertexB((SVertex *)((*e)->vertexB()->userdata));
1511       (*e)->setNextEdge((FEdge *)((*e)->nextEdge()->userdata));
1512       (*e)->setPreviousEdge((FEdge *)((*e)->previousEdge()->userdata));
1513     }
1514
1515     // reset all brothers userdata to NULL:
1516     //-------------------------------------
1517     //---------
1518     // vertices
1519     //---------
1520     for (sv = _verticesList.begin(), svend = _verticesList.end(); sv != svend; sv++) {
1521       (*sv)->userdata = NULL;
1522     }
1523
1524     //------
1525     // edges
1526     //------
1527     for (e = _edgesList.begin(), eend = _edgesList.end(); e != eend; e++) {
1528       (*e)->userdata = NULL;
1529     }
1530   }
1531
1532   /*! Cloning method. */
1533   virtual SShape *duplicate()
1534   {
1535     SShape *clone = new SShape(*this);
1536     return clone;
1537   }
1538
1539   /*! Destructor. */
1540   virtual inline ~SShape()
1541   {
1542     vector<SVertex *>::iterator sv, svend;
1543     vector<FEdge *>::iterator e, eend;
1544     if (0 != _verticesList.size()) {
1545       for (sv = _verticesList.begin(), svend = _verticesList.end(); sv != svend; sv++) {
1546         delete (*sv);
1547       }
1548       _verticesList.clear();
1549     }
1550
1551     if (0 != _edgesList.size()) {
1552       for (e = _edgesList.begin(), eend = _edgesList.end(); e != eend; e++) {
1553         delete (*e);
1554       }
1555       _edgesList.clear();
1556     }
1557
1558     //! Clear the chains list
1559     //-----------------------
1560     if (0 != _chains.size()) {
1561       _chains.clear();
1562     }
1563   }
1564
1565   /*! Adds a FEdge to the list of FEdges. */
1566   inline void AddEdge(FEdge *iEdge)
1567   {
1568     _edgesList.push_back(iEdge);
1569   }
1570
1571   /*! Adds a SVertex to the list of SVertex of this Shape.
1572    * The SShape attribute of the SVertex is also set to 'this'.
1573    */
1574   inline void AddNewVertex(SVertex *iv)
1575   {
1576     iv->setShape(this);
1577     _verticesList.push_back(iv);
1578   }
1579
1580   inline void AddChain(FEdge *iEdge)
1581   {
1582     _chains.push_back(iEdge);
1583   }
1584
1585   inline SVertex *CreateSVertex(const Vec3r &P3D, const Vec3r &P2D, const Id &id)
1586   {
1587     SVertex *Ia = new SVertex(P3D, id);
1588     Ia->setPoint2D(P2D);
1589     AddNewVertex(Ia);
1590     return Ia;
1591   }
1592
1593   /*! Splits an edge into several edges.
1594    *  The edge's vertices are passed rather than the edge itself. This way, all feature edges
1595    * (SILHOUETTE, CREASE, BORDER) are splitted in the same time. The processed edges are flagged as
1596    * done (using the userdata flag).One single new vertex is created whereas several splitted edges
1597    * might created for the different kinds of edges. These new elements are added to the lists
1598    *  maintained by the shape.
1599    *  New chains are also created.
1600    *    ioA
1601    *      The first vertex for the edge that gets splitted
1602    *    ioB
1603    *      The second vertex for the edge that gets splitted
1604    *    iParameters
1605    *      A vector containing 2D real vectors indicating the parameters giving the intersections
1606    * coordinates in 3D and in 2D. These intersections points must be sorted from B to A. Each
1607    * parameter defines the intersection point I as I=A+T*AB. T<0 and T>1 are then incorrect insofar
1608    * as they give intersections points that lie outside the segment. ioNewEdges The edges that are
1609    * newly created (the initial edges are not included) are added to this list.
1610    */
1611   inline void SplitEdge(FEdge *fe, const vector<Vec2r> &iParameters, vector<FEdge *> &ioNewEdges)
1612   {
1613     SVertex *ioA = fe->vertexA();
1614     SVertex *ioB = fe->vertexB();
1615     Vec3r A = ioA->point3D();
1616     Vec3r B = ioB->point3D();
1617     Vec3r a = ioA->point2D();
1618     Vec3r b = ioB->point2D();
1619
1620     Vec3r newpoint3d, newpoint2d;
1621     vector<SVertex *> intersections;
1622     real t, T;
1623     for (vector<Vec2r>::const_iterator p = iParameters.begin(), pend = iParameters.end();
1624          p != pend;
1625          p++) {
1626       T = (*p)[0];
1627       t = (*p)[1];
1628
1629       if ((t < 0) || (t > 1)) {
1630         cerr << "Warning: Intersection out of range for edge " << ioA->getId() << " - "
1631              << ioB->getId() << endl;
1632       }
1633
1634       // compute the 3D and 2D coordinates for the intersections points:
1635       newpoint3d = Vec3r(A + T * (B - A));
1636       newpoint2d = Vec3r(a + t * (b - a));
1637
1638       // create new SVertex:
1639       // (we keep B's id)
1640       SVertex *newVertex = new SVertex(newpoint3d, ioB->getId());
1641       newVertex->setPoint2D(newpoint2d);
1642
1643       // Add this vertex to the intersections list:
1644       intersections.push_back(newVertex);
1645
1646       // Add this vertex to this sshape:
1647       AddNewVertex(newVertex);
1648     }
1649
1650     for (vector<SVertex *>::iterator sv = intersections.begin(), svend = intersections.end();
1651          sv != svend;
1652          sv++) {
1653       // SVertex *svA = fe->vertexA();
1654       SVertex *svB = fe->vertexB();
1655
1656       // We split edge AB into AA' and A'B. A' and A'B are created.
1657       // AB becomes (address speaking) AA'. B is updated.
1658       //--------------------------------------------------
1659       // The edge AB becomes edge AA'.
1660       (fe)->setVertexB((*sv));
1661       // a new edge, A'B is created.
1662       FEdge *newEdge;
1663       if (fe->isSmooth()) {
1664         newEdge = new FEdgeSmooth((*sv), svB);
1665         FEdgeSmooth *se = dynamic_cast<FEdgeSmooth *>(newEdge);
1666         FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
1667         se->setFrsMaterialIndex(fes->frs_materialIndex());
1668       }
1669       else {
1670         newEdge = new FEdgeSharp((*sv), svB);
1671         FEdgeSharp *se = dynamic_cast<FEdgeSharp *>(newEdge);
1672         FEdgeSharp *fes = dynamic_cast<FEdgeSharp *>(fe);
1673         se->setaFrsMaterialIndex(fes->aFrsMaterialIndex());
1674         se->setbFrsMaterialIndex(fes->bFrsMaterialIndex());
1675       }
1676
1677       newEdge->setNature((fe)->getNature());
1678
1679       // to build a new chain:
1680       AddChain(newEdge);
1681       // add the new edge to the sshape edges list.
1682       AddEdge(newEdge);
1683       // add new edge to the list of new edges passed as argument:
1684       ioNewEdges.push_back(newEdge);
1685
1686       // update edge A'B for the next pointing edge
1687       newEdge->setNextEdge((fe)->nextEdge());
1688       fe->nextEdge()->setPreviousEdge(newEdge);
1689       Id id(fe->getId().getFirst(), fe->getId().getSecond() + 1);
1690       newEdge->setId(fe->getId());
1691       fe->setId(id);
1692
1693       // update edge AA' for the next pointing edge
1694       // ioEdge->setNextEdge(newEdge);
1695       (fe)->setNextEdge(NULL);
1696
1697       // update vertex pointing edges list:
1698       // -- vertex B --
1699       svB->Replace((fe), newEdge);
1700       // -- vertex A' --
1701       (*sv)->AddFEdge((fe));
1702       (*sv)->AddFEdge(newEdge);
1703     }
1704   }
1705
1706   /* splits an edge into 2 edges. The new vertex and edge are added to the sshape list of vertices
1707    * and edges a new chain is also created. returns the new edge. ioEdge The edge that gets
1708    * splitted newpoint x,y,z coordinates of the new point.
1709    */
1710   inline FEdge *SplitEdgeIn2(FEdge *ioEdge, SVertex *ioNewVertex)
1711   {
1712     // soc unused - SVertex *A = ioEdge->vertexA();
1713     SVertex *B = ioEdge->vertexB();
1714
1715     // We split edge AB into AA' and A'B. A' and A'B are created.
1716     // AB becomes (address speaking) AA'. B is updated.
1717     //--------------------------------------------------
1718     // a new edge, A'B is created.
1719     FEdge *newEdge;
1720     if (ioEdge->isSmooth()) {
1721       newEdge = new FEdgeSmooth(ioNewVertex, B);
1722       FEdgeSmooth *se = dynamic_cast<FEdgeSmooth *>(newEdge);
1723       FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(ioEdge);
1724       se->setNormal(fes->normal());
1725       se->setFrsMaterialIndex(fes->frs_materialIndex());
1726       se->setFaceMark(fes->faceMark());
1727     }
1728     else {
1729       newEdge = new FEdgeSharp(ioNewVertex, B);
1730       FEdgeSharp *se = dynamic_cast<FEdgeSharp *>(newEdge);
1731       FEdgeSharp *fes = dynamic_cast<FEdgeSharp *>(ioEdge);
1732       se->setNormalA(fes->normalA());
1733       se->setNormalB(fes->normalB());
1734       se->setaFrsMaterialIndex(fes->aFrsMaterialIndex());
1735       se->setbFrsMaterialIndex(fes->bFrsMaterialIndex());
1736       se->setaFaceMark(fes->aFaceMark());
1737       se->setbFaceMark(fes->bFaceMark());
1738     }
1739     newEdge->setNature(ioEdge->getNature());
1740
1741     if (ioEdge->nextEdge() != 0) {
1742       ioEdge->nextEdge()->setPreviousEdge(newEdge);
1743     }
1744
1745     // update edge A'B for the next pointing edge
1746     newEdge->setNextEdge(ioEdge->nextEdge());
1747     // update edge A'B for the previous pointing edge
1748     newEdge->setPreviousEdge(0);  // because it is now a TVertex
1749     Id id(ioEdge->getId().getFirst(), ioEdge->getId().getSecond() + 1);
1750     newEdge->setId(ioEdge->getId());
1751     ioEdge->setId(id);
1752
1753     // update edge AA' for the next pointing edge
1754     ioEdge->setNextEdge(0);  // because it is now a TVertex
1755
1756     // update vertex pointing edges list:
1757     // -- vertex B --
1758     B->Replace(ioEdge, newEdge);
1759     // -- vertex A' --
1760     ioNewVertex->AddFEdge(ioEdge);
1761     ioNewVertex->AddFEdge(newEdge);
1762
1763     // to build a new chain:
1764     AddChain(newEdge);
1765     AddEdge(newEdge);  // FIXME ??
1766
1767     // The edge AB becomes edge AA'.
1768     ioEdge->setVertexB(ioNewVertex);
1769
1770     if (ioEdge->isSmooth()) {
1771       ((FEdgeSmooth *)newEdge)->setFace(((FEdgeSmooth *)ioEdge)->face());
1772     }
1773
1774     return newEdge;
1775   }
1776
1777   /*! Sets the Bounding Box of the Shape */
1778   inline void setBBox(const BBox<Vec3r> &iBBox)
1779   {
1780     _BBox = iBBox;
1781   }
1782
1783   /*! Compute the bbox of the sshape */
1784   inline void ComputeBBox()
1785   {
1786     if (0 == _verticesList.size()) {
1787       return;
1788     }
1789
1790     Vec3r firstVertex = _verticesList[0]->point3D();
1791     real XMax = firstVertex[0];
1792     real YMax = firstVertex[1];
1793     real ZMax = firstVertex[2];
1794
1795     real XMin = firstVertex[0];
1796     real YMin = firstVertex[1];
1797     real ZMin = firstVertex[2];
1798
1799     vector<SVertex *>::iterator v, vend;
1800     // parse all the coordinates to find the Xmax, YMax, ZMax
1801     for (v = _verticesList.begin(), vend = _verticesList.end(); v != vend; v++) {
1802       Vec3r vertex = (*v)->point3D();
1803       // X
1804       real x = vertex[0];
1805       if (x > XMax) {
1806         XMax = x;
1807       }
1808       else if (x < XMin) {
1809         XMin = x;
1810       }
1811
1812       // Y
1813       real y = vertex[1];
1814       if (y > YMax) {
1815         YMax = y;
1816       }
1817       else if (y < YMin) {
1818         YMin = y;
1819       }
1820
1821       // Z
1822       real z = vertex[2];
1823       if (z > ZMax) {
1824         ZMax = z;
1825       }
1826       else if (z < ZMin) {
1827         ZMin = z;
1828       }
1829     }
1830
1831     setBBox(BBox<Vec3r>(Vec3r(XMin, YMin, ZMin), Vec3r(XMax, YMax, ZMax)));
1832   }
1833
1834   inline void RemoveEdgeFromChain(FEdge *iEdge)
1835   {
1836     for (vector<FEdge *>::iterator fe = _chains.begin(), feend = _chains.end(); fe != feend;
1837          fe++) {
1838       if (iEdge == (*fe)) {
1839         _chains.erase(fe);
1840         break;
1841       }
1842     }
1843   }
1844
1845   inline void RemoveEdge(FEdge *iEdge)
1846   {
1847     for (vector<FEdge *>::iterator fe = _edgesList.begin(), feend = _edgesList.end(); fe != feend;
1848          fe++) {
1849       if (iEdge == (*fe)) {
1850         _edgesList.erase(fe);
1851         break;
1852       }
1853     }
1854   }
1855
1856   /* accessors */
1857   /*! Returns the list of SVertex of the Shape. */
1858   inline vector<SVertex *> &getVertexList()
1859   {
1860     return _verticesList;
1861   }
1862
1863   /*! Returns the list of FEdges of the Shape. */
1864   inline vector<FEdge *> &getEdgeList()
1865   {
1866     return _edgesList;
1867   }
1868
1869   inline vector<FEdge *> &getChains()
1870   {
1871     return _chains;
1872   }
1873
1874   /*! Returns the bounding box of the shape. */
1875   inline const BBox<Vec3r> &bbox()
1876   {
1877     return _BBox;
1878   }
1879
1880   /*! Returns the ith material of the shape. */
1881   inline const FrsMaterial &frs_material(unsigned i) const
1882   {
1883     return _FrsMaterials[i];
1884   }
1885
1886   /*! Returns the list of materials of the Shape. */
1887   inline const vector<FrsMaterial> &frs_materials() const
1888   {
1889     return _FrsMaterials;
1890   }
1891
1892   inline ViewShape *viewShape()
1893   {
1894     return _ViewShape;
1895   }
1896
1897   inline float importance() const
1898   {
1899     return _importance;
1900   }
1901
1902   /*! Returns the Id of the Shape. */
1903   inline Id getId() const
1904   {
1905     return _Id;
1906   }
1907
1908   /*! Returns the name of the Shape. */
1909   inline const string &getName() const
1910   {
1911     return _Name;
1912   }
1913
1914   /*! Returns the library path of the Shape. */
1915   inline const string &getLibraryPath() const
1916   {
1917     return _LibraryPath;
1918   }
1919
1920   /* Modififers */
1921   /*! Sets the Id of the shape.*/
1922   inline void setId(Id id)
1923   {
1924     _Id = id;
1925   }
1926
1927   /*! Sets the name of the shape.*/
1928   inline void setName(const string &name)
1929   {
1930     _Name = name;
1931   }
1932
1933   /*! Sets the library path of the shape.*/
1934   inline void setLibraryPath(const string &path)
1935   {
1936     _LibraryPath = path;
1937   }
1938
1939   /*! Sets the list of materials for the shape */
1940   inline void setFrsMaterials(const vector<FrsMaterial> &iMaterials)
1941   {
1942     _FrsMaterials = iMaterials;
1943   }
1944
1945   inline void setViewShape(ViewShape *iShape)
1946   {
1947     _ViewShape = iShape;
1948   }
1949
1950   inline void setImportance(float importance)
1951   {
1952     _importance = importance;
1953   }
1954
1955 #ifdef WITH_CXX_GUARDEDALLOC
1956   MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SShape")
1957 #endif
1958 };
1959
1960 } /* namespace Freestyle */
1961
1962 #endif  // __FREESTYLE_SILHOUETTE_H__