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