Freestyle: minor optimization for space from mesh importing to feature edge detection.
[blender.git] / source / blender / freestyle / intern / winged_edge / WEdge.cpp
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 /** \file blender/freestyle/intern/winged_edge/WEdge.cpp
22  *  \ingroup freestyle
23  *  \brief Classes to define a Winged Edge data structure.
24  *  \author Stephane Grabli
25  *  \date 18/02/2002
26  */
27
28 #include <iostream>
29
30 #include "WEdge.h"
31
32 namespace Freestyle {
33
34 /*! Temporary structures */
35 class vertexdata
36 {
37 public:
38         WVertex *_copy;
39 };
40
41 class oedgedata
42 {
43 public:
44         WOEdge *_copy;
45 };
46
47 class edgedata
48 {
49 public:
50         WEdge *_copy;
51 };
52
53 class facedata
54 {
55 public:
56         WFace *_copy;
57 };
58
59
60 /**********************************
61  *                                *
62  *                                *
63  *             WVertex            *
64  *                                *
65  *                                *
66  **********************************/
67
68 WVertex::WVertex(WVertex& iBrother)
69 {
70         _Id = iBrother._Id;
71         _Vertex = iBrother._Vertex;
72         _EdgeList = iBrother._EdgeList;
73
74         _Shape = iBrother._Shape;
75         _Smooth = iBrother._Smooth;
76         _Border = iBrother._Border;
77         userdata = NULL;
78         iBrother.userdata = new vertexdata;
79         ((vertexdata *)(iBrother.userdata))->_copy = this;
80 }
81
82 WVertex *WVertex::duplicate()
83 {
84         WVertex *clone = new WVertex(*this);
85         return clone;
86 }
87
88 WOEdge *WVertex::incoming_edge_iterator::operator*()
89 {
90         return _current;
91 }
92
93 void WVertex::incoming_edge_iterator::increment()
94 {
95         WOEdge *twin = _current->twin();
96         if (!twin) {
97                 // we reached a hole
98                 _current = 0;
99                 return;
100         }
101         WOEdge *next = twin->getPrevOnFace();
102         if (next == _begin) {
103                 next = NULL;
104         }
105         _current = next;
106 }
107
108 WFace *WVertex::face_iterator::operator*()
109 {
110         WOEdge *woedge = *_edge_it;
111         if (!woedge)
112                 return NULL;
113         return (woedge)->GetbFace();
114 }
115
116 #if 0
117 bool WVertex::isBoundary () const
118 {
119         return _Border;
120 }
121 #endif
122 bool WVertex::isBoundary ()
123 {
124         if (_Border == 1)
125                 return true;
126         else if (_Border == 0)
127                 return false;
128
129         vector<WEdge *>::const_iterator it;
130         for (it = _EdgeList.begin(); it != _EdgeList.end(); it++) {
131                 if ((*it)->GetNumberOfOEdges() == 1) {
132                         _Border = 1;
133                         return true;
134                 }
135         }
136 #if 0
137         if (!(*it)->GetaOEdge()->GetaFace())
138                 return true;
139 #endif
140         _Border = 0;
141         return false;
142 }
143
144 void WVertex::AddEdge(WEdge *iEdge)
145 {
146         _EdgeList.push_back(iEdge);
147 }
148
149 WVertex::incoming_edge_iterator WVertex::incoming_edges_begin()
150 {
151         WOEdge *begin;
152         WEdge *wedge = _EdgeList.front();
153         WOEdge *aOEdge = wedge->GetaOEdge();
154         if (aOEdge->GetbVertex() == this)
155                 begin = aOEdge;
156         else
157                 begin = _EdgeList.front()->GetbOEdge();
158         return incoming_edge_iterator(this, begin, begin);
159 }
160
161 WVertex::incoming_edge_iterator WVertex::incoming_edges_end()
162 {
163         WOEdge *begin;
164         WOEdge *aOEdge = _EdgeList.front()->GetaOEdge();
165         if (aOEdge->GetbVertex() == this)
166                 begin = aOEdge;
167         else
168                 begin = _EdgeList.front()->GetbOEdge();
169         return incoming_edge_iterator(this, begin, 0);
170 }
171 #if 0
172 WOEdge **WVertex::incoming_edge_iterator::operator->()
173 {
174         WOEdge **ppaOEdge = (*_iter)->GetaOEdge();
175         if (aOEdge->GetbVertex() == _vertex) {
176                 return ppaOEdge;
177         }
178         else {
179                 WOEdge *bOEdge = (*_iter)->GetbOEdge();
180                 return &bOEdge;
181         }
182 }
183 #endif
184
185 /**********************************
186  *                                *
187  *                                *
188  *             WOEdge             *
189  *                                *
190  *                                *
191  **********************************/
192
193 WOEdge::WOEdge(WOEdge& iBrother)
194 {
195         _paVertex = iBrother.GetaVertex();
196         _pbVertex = iBrother.GetbVertex();
197         _paFace = iBrother.GetaFace();
198         _pbFace = iBrother.GetbFace();
199         _pOwner = iBrother.GetOwner();
200         userdata = NULL;
201         iBrother.userdata = new oedgedata;
202         ((oedgedata *)(iBrother.userdata))->_copy = this;
203
204         _vec = iBrother._vec;
205         _angle = iBrother._angle;
206 }
207
208 WOEdge *WOEdge::duplicate()
209 {
210         WOEdge *clone = new WOEdge(*this);
211         return clone;
212 }
213
214 WOEdge *WOEdge::twin ()
215 {
216         return GetOwner()->GetOtherOEdge(this);
217 }
218
219 WOEdge *WOEdge::getPrevOnFace()
220 {
221         return _pbFace->GetPrevOEdge(this);
222 }
223
224 /**********************************
225  *                                *
226  *                                *
227  *             WEdge              *
228  *                                *
229  *                                *
230  **********************************/
231
232 WEdge::WEdge(WEdge& iBrother)
233 {
234         _paOEdge = NULL;
235         _pbOEdge = NULL;
236         WOEdge *aoedge = iBrother.GetaOEdge();
237         WOEdge *boedge = iBrother.GetbOEdge();
238         userdata = NULL;
239
240         if (aoedge)
241                 //_paOEdge = new WOEdge(*aoedge);
242                 _paOEdge = aoedge->duplicate();
243         if (boedge)
244                 //_pbOEdge = new WOEdge(*boedge);
245                 _pbOEdge = boedge->duplicate();
246
247         _nOEdges = iBrother.GetNumberOfOEdges();
248         _Id = iBrother.GetId();
249         iBrother.userdata = new edgedata;
250         ((edgedata *)(iBrother.userdata))->_copy = this;
251 }
252
253 WEdge *WEdge::duplicate()
254 {
255         WEdge *clone = new WEdge(*this);
256         return clone;
257 }
258
259 /**********************************
260  *                                *
261  *                                *
262  *             WFace              *
263  *                                *
264  *                                *
265  **********************************/
266
267 WFace::WFace(WFace& iBrother)
268 {
269         _OEdgeList = iBrother.getEdgeList();
270         _Normal = iBrother.GetNormal();
271         _VerticesNormals = iBrother._VerticesNormals;
272         _VerticesTexCoords = iBrother._VerticesTexCoords;
273         _Id = iBrother.GetId();
274         _FrsMaterialIndex = iBrother._FrsMaterialIndex;
275         _Mark = iBrother._Mark;
276         userdata = NULL;
277         iBrother.userdata = new facedata;
278         ((facedata *)(iBrother.userdata))->_copy = this;
279 }
280
281 WFace *WFace::duplicate()
282 {
283         WFace *clone = new WFace(*this);
284         return clone;
285 }
286
287 const FrsMaterial& WFace::frs_material()
288 {
289         return getShape()->frs_material(_FrsMaterialIndex);
290 }
291
292 WOEdge *WFace::MakeEdge(WVertex *v1, WVertex *v2)
293 {
294         // First check whether the same oriented edge already exists or not:
295         vector<WEdge *>& v1Edges = v1->GetEdges();
296         for (vector<WEdge*>::iterator it1 = v1Edges.begin(), end = v1Edges.end(); it1 != end; it1++) {
297                 WEdge *we = (*it1);
298                 WOEdge *woea = we->GetaOEdge();
299
300                 if ((woea->GetaVertex() == v1) && (woea->GetbVertex() == v2)) {
301                         // The oriented edge already exists
302                         cerr << "Warning: edge " << v1->GetId() << " - " << v2->GetId() << " appears twice, correcting" << endl;
303                         // Adds the edge to the face
304                         AddEdge(woea);
305                         (*it1)->setNumberOfOEdges((*it1)->GetNumberOfOEdges() + 1);
306                         //sets these vertices as border:
307                         v1->setBorder(true);
308                         v2->setBorder(true);
309                         return woea;
310                 }
311
312                 WOEdge *woeb = we->GetbOEdge();
313                 if (woeb && (woeb->GetaVertex() == v1) && (woeb->GetbVertex() == v2)) {
314                         // The oriented edge already exists
315                         cerr << "Warning: edge " << v1->GetId() << " - " << v2->GetId() << " appears twice, correcting" << endl;
316                         // Adds the edge to the face
317                         AddEdge(woeb);
318                         (*it1)->setNumberOfOEdges((*it1)->GetNumberOfOEdges() + 1);
319                         //sets these vertices as border:
320                         v1->setBorder(true);
321                         v2->setBorder(true);
322                         return woeb;
323                 }
324         }
325
326         // the oriented edge we're about to build
327         WOEdge *pOEdge = new WOEdge;
328         // The edge containing the oriented edge.
329         WEdge *edge;
330
331         // checks whether this edge already exists or not
332         // If it exists, it points outward v2
333         bool exist = false;
334         WOEdge *pInvertEdge = NULL; // The inverted edge if it exists
335         vector<WEdge *>& v2Edges = v2->GetEdges();
336         vector<WEdge *>::iterator it;
337         for (it = v2Edges.begin(); it != v2Edges.end(); it++) {
338                 if ((*it)->GetbVertex() == v1) {
339                         // The invert edge already exists
340                         exist = true;
341                         pInvertEdge = (*it)->GetaOEdge();
342                         break;
343                 }
344         }
345
346         //DEBUG:
347         if (true == exist) { // The invert edge already exists
348                 // Retrieves the corresponding edge
349                 edge = pInvertEdge->GetOwner();
350
351                 // Sets the a Face (retrieved from pInvertEdge
352                 pOEdge->setaFace(pInvertEdge->GetbFace());
353
354                 // Updates the invert edge:
355                 pInvertEdge->setaFace(this);
356         }
357         else { // The invert edge does not exist yet
358                 // we must create a new edge
359                 //edge = new WEdge;
360                 edge = instanciateEdge();
361
362                 // updates the a,b vertex edges list:
363                 v1->AddEdge(edge);
364                 v2->AddEdge(edge);
365         }
366
367         pOEdge->setOwner(edge);
368         // Add the vertices:
369         pOEdge->setaVertex(v1);
370         pOEdge->setbVertex(v2);
371
372         // Debug:
373         if (v1->GetId() == v2->GetId())
374                 cerr << "Warning: edge " << this << " null with vertex " << v1->GetId() << endl;
375
376         edge->AddOEdge(pOEdge);
377         //edge->setNumberOfOEdges(edge->GetNumberOfOEdges() + 1);
378
379         // Add this face (the b face)
380         pOEdge->setbFace(this);
381
382         // Adds the edge to the face
383         AddEdge(pOEdge);
384
385         return pOEdge;
386 }
387
388
389 bool WFace::getOppositeEdge(const WVertex *v, WOEdge *&e)
390 {
391         if (_OEdgeList.size() != 3)
392                 return false;
393
394         vector<WOEdge *>::iterator it;
395         e = NULL;
396         for (it = _OEdgeList.begin(); it != _OEdgeList.end(); it++) {
397                 if ((*it)->GetaVertex() == v)
398                         e = *it;
399         }
400         if (!e)
401                 return false;
402         e = NULL;
403         for (it = _OEdgeList.begin(); it != _OEdgeList.end(); it++) {
404                 if (((*it)->GetaVertex() != v) && ((*it)->GetbVertex() != v))
405                         e = *it;
406         }
407         if (!e)
408                 return false;
409         else
410                 return true;
411 }
412
413 real WFace::getArea ()
414 {
415         vector<WOEdge *>::iterator it;
416         Vec3r origin = (*(_OEdgeList.begin()))->GetaVertex()->GetVertex();
417         it = _OEdgeList.begin();
418         real a = 0;
419         for (it = it++; it != _OEdgeList.end(); it++) {
420                 Vec3r v1 = Vec3r((*it)->GetaVertex()->GetVertex() - origin);
421                 Vec3r v2 = Vec3r((*it)->GetbVertex()->GetVertex() - origin);
422                 a += (v1 ^ v2).norm() / 2.0;
423         }
424         return a;
425 }
426
427
428 WOEdge *WFace::GetPrevOEdge(WOEdge *iOEdge)
429 {
430         vector<WOEdge *>::iterator woe, woend, woefirst;
431         woefirst = _OEdgeList.begin();
432         woend = _OEdgeList.end();
433         WOEdge *prev = *woefirst;
434         woe = woefirst;
435         ++woe;
436         for (; woe != woend; woe++) {
437                 if ((*woe) == iOEdge)
438                         return prev;
439                 prev = *woe;
440         }
441         // We left the loop. That means that the first OEdge was the good one:
442         if ((*woefirst) == iOEdge)
443                 return prev;
444
445         return NULL;
446 }
447
448 WShape *WFace::getShape()
449 {
450         return GetVertex(0)->shape();
451 }
452
453
454 /**********************************
455  *                                *
456  *                                *
457  *             WShape             *
458  *                                *
459  *                                *
460  **********************************/
461
462 unsigned WShape::_SceneCurrentId = 0;
463
464 WShape *WShape::duplicate()
465 {
466         WShape *clone = new WShape(*this);
467         return clone;
468 }
469
470 WShape::WShape(WShape& iBrother)
471 {
472         _Id = iBrother.GetId();
473         _Name = iBrother._Name;
474         _FrsMaterials = iBrother._FrsMaterials;
475 #if 0
476         _meanEdgeSize = iBrother._meanEdgeSize;
477         iBrother.bbox(_min, _max);
478 #endif
479         vector<WVertex *>& vertexList = iBrother.getVertexList();
480         vector<WVertex *>::iterator v = vertexList.begin(), vend = vertexList.end();
481         for (; v != vend; ++v) {
482                 //WVertex *newVertex = new WVertex(*(*v));
483                 WVertex *newVertex = (*v)->duplicate();
484
485                 newVertex->setShape(this);
486                 AddVertex(newVertex);
487         }
488
489         vector<WEdge *>& edgeList = iBrother.getEdgeList();
490         vector<WEdge *>::iterator e = edgeList.begin(), eend = edgeList.end();
491         for (; e != eend; ++e) {
492                 //WEdge *newEdge = new WEdge(*(*e));
493                 WEdge *newEdge = (*e)->duplicate();
494                 AddEdge(newEdge);
495         }
496
497         vector<WFace *>& faceList = iBrother.GetFaceList();
498         vector<WFace *>::iterator f = faceList.begin(), fend = faceList.end();
499         for (; f != fend; ++f) {
500                 //WFace *newFace = new WFace(*(*f));
501                 WFace *newFace = (*f)->duplicate();
502                 AddFace(newFace);
503         }
504
505         // update all pointed addresses thanks to the newly created objects:
506         vend = _VertexList.end();
507         for (v = _VertexList.begin(); v != vend; ++v) {
508                 const vector<WEdge *>& vedgeList = (*v)->GetEdges();
509                 vector<WEdge *> newvedgelist;
510                 unsigned int i;
511                 for (i = 0; i < vedgeList.size(); i++) {
512                         WEdge *current = vedgeList[i];
513                         edgedata *currentvedata = (edgedata *)current->userdata;
514                         newvedgelist.push_back(currentvedata->_copy);
515                 }
516                 (*v)->setEdges(newvedgelist);
517         }
518
519         eend = _EdgeList.end();
520         for (e = _EdgeList.begin(); e != eend; ++e) {
521                 // update aOedge:
522                 WOEdge *aoEdge = (*e)->GetaOEdge();
523                 aoEdge->setaVertex(((vertexdata *)(aoEdge->GetaVertex()->userdata))->_copy);
524                 aoEdge->setbVertex(((vertexdata *)(aoEdge->GetbVertex()->userdata))->_copy);
525                 if (aoEdge->GetaFace())
526                         aoEdge->setaFace(((facedata *)(aoEdge->GetaFace()->userdata))->_copy);
527                 aoEdge->setbFace(((facedata *)(aoEdge->GetbFace()->userdata))->_copy);
528                 aoEdge->setOwner(((edgedata *)(aoEdge->GetOwner()->userdata))->_copy);
529
530                 // update bOedge:
531                 WOEdge *boEdge = (*e)->GetbOEdge();
532                 if (boEdge) {
533                         boEdge->setaVertex(((vertexdata *)(boEdge->GetaVertex()->userdata))->_copy);
534                         boEdge->setbVertex(((vertexdata *)(boEdge->GetbVertex()->userdata))->_copy);
535                         if (boEdge->GetaFace())
536                                 boEdge->setaFace(((facedata *)(boEdge->GetaFace()->userdata))->_copy);
537                         boEdge->setbFace(((facedata *)(boEdge->GetbFace()->userdata))->_copy);
538                         boEdge->setOwner(((edgedata *)(boEdge->GetOwner()->userdata))->_copy);
539                 }
540         }
541
542         fend = _FaceList.end();
543         for (f = _FaceList.begin(); f != fend; ++f) {
544                 unsigned int i;
545                 const vector<WOEdge *>& oedgeList = (*f)->getEdgeList();
546                 vector<WOEdge *> newoedgelist;
547
548                 unsigned int n = oedgeList.size();
549                 for (i = 0; i < n; i++) {
550                         WOEdge *current = oedgeList[i];
551                         oedgedata *currentoedata = (oedgedata *)current->userdata;
552                         newoedgelist.push_back(currentoedata->_copy);
553                         //oedgeList[i] = currentoedata->_copy;
554                         //oedgeList[i] = ((oedgedata *)(oedgeList[i]->userdata))->_copy;
555                 }
556                 (*f)->setEdgeList(newoedgelist);
557         }
558
559         // Free all memory (arghh!)
560         // Vertex
561         vend = iBrother.getVertexList().end();
562         for (v = iBrother.getVertexList().begin(); v != vend; ++v) {
563                 delete (vertexdata *)((*v)->userdata);
564                 (*v)->userdata = NULL;
565         }
566
567         // Edges and OEdges:
568         eend = iBrother.getEdgeList().end();
569         for (e = iBrother.getEdgeList().begin(); e != eend; ++e) {
570                 delete (edgedata *)((*e)->userdata);
571                 (*e)->userdata = NULL;
572                 // OEdge a:
573                 delete (oedgedata *)((*e)->GetaOEdge()->userdata);
574                 (*e)->GetaOEdge()->userdata = NULL;
575                 // OEdge b:
576                 WOEdge *oedgeb = (*e)->GetbOEdge();
577                 if (oedgeb) {
578                         delete (oedgedata *)(oedgeb->userdata);
579                         oedgeb->userdata = NULL;
580                 }
581         }
582
583         // Faces
584         fend = iBrother.GetFaceList().end();
585         for (f = iBrother.GetFaceList().begin(); f != fend; ++f) {
586                 delete (facedata *)((*f)->userdata);
587                 (*f)->userdata = NULL;
588         }
589 }
590
591 WFace *WShape::MakeFace(vector<WVertex *>& iVertexList, vector<bool>& iFaceEdgeMarksList, unsigned iMaterial)
592 {
593         // allocate the new face
594         WFace *face = instanciateFace();
595
596         WFace *result = MakeFace(iVertexList, iFaceEdgeMarksList, iMaterial, face);
597         if (!result)
598                 delete face;
599         return result;
600 }
601
602 WFace *WShape::MakeFace(vector<WVertex *>& iVertexList, vector<Vec3r>& iNormalsList, vector<Vec2r>& iTexCoordsList,
603                         vector<bool>& iFaceEdgeMarksList, unsigned iMaterial)
604 {
605         // allocate the new face
606         WFace *face = MakeFace(iVertexList, iFaceEdgeMarksList, iMaterial);
607
608         if (!face)
609                 return NULL;
610
611         // set the list of per-vertex normals
612         face->setNormalList(iNormalsList);
613         // set the list of per-vertex tex coords
614         face->setTexCoordsList(iTexCoordsList);
615
616         return face;
617 }
618
619 WFace *WShape::MakeFace(vector<WVertex *>& iVertexList, vector<bool>& iFaceEdgeMarksList, unsigned iMaterial,
620                         WFace *face)
621 {
622         int id = _FaceList.size();
623
624         face->setFrsMaterialIndex(iMaterial);
625
626         // Check whether we have a degenerated face:
627
628         // LET'S HACK IT FOR THE TRIANGLE CASE:
629
630         if (3 == iVertexList.size()) {
631                 if ((iVertexList[0] == iVertexList[1]) ||
632                     (iVertexList[0] == iVertexList[2]) ||
633                     (iVertexList[2] == iVertexList[1]))
634                 {
635                         cerr << "Warning: degenerated triangle detected, correcting" << endl;
636                         return NULL;
637                 }
638         }
639
640         vector<WVertex *>::iterator it;
641
642         // compute the face normal (v1v2 ^ v1v3)
643         WVertex *v1, *v2, *v3;
644         it = iVertexList.begin();
645         v1 = *it;
646         it++;
647         v2 = *it;
648         it++;
649         v3 = *it;
650
651         Vec3r vector1(v2->GetVertex() - v1->GetVertex());
652         Vec3r vector2(v3->GetVertex() - v1->GetVertex());
653
654         Vec3r normal(vector1 ^ vector2);
655         normal.normalize();
656         face->setNormal(normal);
657
658         vector<bool>::iterator mit = iFaceEdgeMarksList.begin();
659         face->setMark(*mit);
660         mit++;
661
662         // vertex pointers used to build each edge
663         vector<WVertex *>::iterator va, vb;
664
665         va = iVertexList.begin();
666         vb = va;
667         for (; va != iVertexList.end(); va = vb) {
668                 ++vb;
669                 // Adds va to the vertex list:
670                 //face->AddVertex(*va);
671
672                 WOEdge *oedge;
673                 if (*va == iVertexList.back())
674                         oedge = face->MakeEdge(*va, iVertexList.front()); //for the last (closing) edge
675                 else
676                         oedge = face->MakeEdge(*va, *vb);
677
678                 if (!oedge)
679                         return NULL;
680
681                 WEdge *edge = oedge->GetOwner();
682                 if (1 == edge->GetNumberOfOEdges()) {
683                         // means that we just created a new edge and that we must add it to the shape's edges list
684                         edge->setId(_EdgeList.size());
685                         AddEdge(edge);
686 #if 0
687                         // compute the mean edge value:
688                         _meanEdgeSize += edge->GetaOEdge()->GetVec().norm();
689 #endif
690                 }
691
692                 edge->setMark(*mit);
693                 ++mit;
694         }
695
696         // Add the face to the shape's faces list:
697         face->setId(id);
698         AddFace(face);
699
700         return face;
701 }
702
703 real WShape::ComputeMeanEdgeSize() const
704 {
705         real meanEdgeSize = 0.0;
706         for (vector<WEdge *>::const_iterator it = _EdgeList.begin(), itend = _EdgeList.end();
707              it != itend;
708              it++)
709         {
710                 meanEdgeSize += (*it)->GetaOEdge()->GetVec().norm();
711         }
712         return meanEdgeSize / _EdgeList.size();
713 }
714
715 } /* namespace Freestyle */