diff options
Diffstat (limited to 'source/blender/freestyle/intern/winged_edge/WEdge.cpp')
| -rwxr-xr-x | source/blender/freestyle/intern/winged_edge/WEdge.cpp | 732 |
1 files changed, 732 insertions, 0 deletions
diff --git a/source/blender/freestyle/intern/winged_edge/WEdge.cpp b/source/blender/freestyle/intern/winged_edge/WEdge.cpp new file mode 100755 index 00000000000..79b3a8dae26 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WEdge.cpp @@ -0,0 +1,732 @@ + +// +// Copyright (C) : Please refer to the COPYRIGHT file distributed +// with this source distribution. +// +// This program is free software; you can redistribute it and/or +// modify it under the terms of the GNU General Public License +// as published by the Free Software Foundation; either version 2 +// of the License, or (at your option) any later version. +// +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +// +/////////////////////////////////////////////////////////////////////////////// + +#include <iostream> +#include "WEdge.h" + +/*! Temporary structures */ +class vertexdata +{ +public: + WVertex *_copy; +}; + +class oedgedata +{ +public: + WOEdge *_copy; +}; + +class edgedata +{ +public: + WEdge *_copy; +}; + +class facedata +{ +public: + WFace *_copy; +}; + + + /**********************************/ + /* */ + /* */ + /* WVertex */ + /* */ + /* */ + /**********************************/ + +WVertex::WVertex(WVertex& iBrother) +{ + _Id = iBrother._Id; + _Vertex = iBrother._Vertex; + _EdgeList = iBrother._EdgeList; + + _Shape = iBrother._Shape; + _Smooth = iBrother._Smooth; + _Border = iBrother._Border; + userdata = NULL; + iBrother.userdata = new vertexdata; + ((vertexdata*)(iBrother.userdata))->_copy = this; +} + +WVertex* WVertex::dupplicate() +{ + WVertex *clone = new WVertex(*this); + return clone; +} + + +WOEdge* WVertex::incoming_edge_iterator::operator*() + +{ + return _current; +} +void WVertex::incoming_edge_iterator::increment(){ + WOEdge *twin = _current->twin(); + if(!twin){ + // we reached a hole + _current = 0; + return; + } + WOEdge *next = twin->getPrevOnFace(); + if(next == _begin){ + next = 0; + } + _current = next; +} + +WFace* WVertex::face_iterator::operator*(){ + WOEdge * woedge = *_edge_it; + if(woedge == 0) + return 0; + return (woedge)->GetbFace(); +} + +//bool WVertex::isBoundary () const{ +// return _Border; +//} +bool WVertex::isBoundary () +{ + if(_Border == 1) + return true; + else if(_Border == 0) + return false; + + vector<WEdge *>::const_iterator it; + for(it=_EdgeList.begin(); it!=_EdgeList.end(); it++){ + if((*it)->GetNumberOfOEdges() == 1){ + _Border = 1; + return true; + } + } + //if (!(*it)->GetaOEdge()->GetaFace()) return true; + _Border = 0; + return false; +} + +void WVertex::AddEdge(WEdge *iEdge) { + _EdgeList.push_back(iEdge); +} + +WVertex::incoming_edge_iterator WVertex::incoming_edges_begin(){ + WOEdge *begin; + WEdge * wedge = _EdgeList.front(); + WOEdge* aOEdge = wedge->GetaOEdge(); + if(aOEdge->GetbVertex() == this) + begin = aOEdge; + else + begin = _EdgeList.front()->GetbOEdge(); + return incoming_edge_iterator(this, begin, begin); +} +WVertex::incoming_edge_iterator WVertex::incoming_edges_end(){ + WOEdge *begin; + WOEdge* aOEdge = _EdgeList.front()->GetaOEdge(); + if(aOEdge->GetbVertex() == this) + begin = aOEdge; + else + begin = _EdgeList.front()->GetbOEdge(); + return incoming_edge_iterator(this, begin, 0); +} +//WOEdge** WVertex::incoming_edge_iterator::operator->() +//{ +// WOEdge ** ppaOEdge = (*_iter)->GetaOEdge(); +// if(aOEdge->GetbVertex() == _vertex) +// return ppaOEdge; +// else +// { +// WOEdge *bOEdge = (*_iter)->GetbOEdge(); +// return &bOEdge; +// } +// +//} + /**********************************/ + /* */ + /* */ + /* WOEdge */ + /* */ + /* */ + /**********************************/ + +WOEdge::WOEdge(WOEdge& iBrother) +{ + _paVertex = iBrother.GetaVertex(); + _pbVertex = iBrother.GetbVertex(); + _paFace = iBrother.GetaFace(); + _pbFace = iBrother.GetbFace(); + _pOwner = iBrother.GetOwner(); + userdata = NULL; + iBrother.userdata = new oedgedata; + ((oedgedata*)(iBrother.userdata))->_copy = this; +} + +WOEdge * WOEdge::dupplicate() +{ + WOEdge *clone = new WOEdge(*this); + return clone; +} + +Vec3r +WOEdge::getVec3r () +{ + return Vec3r(_pbVertex->GetVertex() - _paVertex->GetVertex()); +} + +WOEdge * WOEdge::twin () +{ + return GetOwner()->GetOtherOEdge(this); +} + +WOEdge * +WOEdge::getPrevOnFace() +{ + return _pbFace->GetPrevOEdge(this); +} + + /**********************************/ + /* */ + /* */ + /* WEdge */ + /* */ + /* */ + /**********************************/ + +WEdge::WEdge(WEdge& iBrother) +{ + _paOEdge = NULL; + _pbOEdge = NULL; + WOEdge *aoedge = iBrother.GetaOEdge(); + WOEdge *boedge = iBrother.GetbOEdge(); + userdata = NULL; + + if(NULL != aoedge) + //_paOEdge = new WOEdge(*aoedge); + _paOEdge = aoedge->dupplicate(); + if(NULL != boedge) + //_pbOEdge = new WOEdge(*boedge); + _pbOEdge = boedge->dupplicate(); + + _nOEdges = iBrother.GetNumberOfOEdges(); + _Id = iBrother.GetId(); + iBrother.userdata = new edgedata; + ((edgedata*)(iBrother.userdata))->_copy = this; +} + +WEdge * WEdge::dupplicate() +{ + WEdge *clone = new WEdge(*this); + return clone; +} + + /**********************************/ + /* */ + /* */ + /* WFace */ + /* */ + /* */ + /**********************************/ + + +WFace::WFace(WFace& iBrother) +{ + _OEdgeList = iBrother.GetEdgeList(); + _Normal = iBrother.GetNormal(); + _VerticesNormals = iBrother._VerticesNormals; + _VerticesTexCoords = iBrother._VerticesTexCoords; + _Id = iBrother.GetId(); + _MaterialIndex = iBrother._MaterialIndex; + userdata = NULL; + iBrother.userdata = new facedata; + ((facedata*)(iBrother.userdata))->_copy = this; +} + +WFace * WFace::dupplicate() +{ + WFace * clone = new WFace(*this); + return clone; +} + +const Material& WFace::material() { + return getShape()->material(_MaterialIndex); +} + +WOEdge * WFace::MakeEdge(WVertex *v1, WVertex *v2) +{ + // First check whether the same oriented edge already exists + // or not: + vector<WEdge *>& v1Edges = v1->GetEdges(); + for(vector<WEdge*>::iterator it1=v1Edges.begin(), end=v1Edges.end(); + it1!=end; + it1++) + { + + WEdge *we=(*it1); + + WOEdge *woea = we->GetaOEdge(); + + if((woea->GetaVertex() == v1) && (woea->GetbVertex() == v2)) + //if((*it1)->GetbVertex() == v2) + { + // The oriented edge already exists + cerr << "Warning: edge " << v1->GetId() << " - " << v2->GetId() << " appears twice, correcting" << endl; + // Adds the edge to the face + //AddEdge((*it1)->GetaOEdge()); + AddEdge(woea); + (*it1)->SetNumberOfOEdges((*it1)->GetNumberOfOEdges()+1); + //sets these vertices as border: + v1->SetBorder(true); + v2->SetBorder(true); + //return (*it1)->GetaOEdge(); + return woea; + } + + WOEdge *woeb = we->GetbOEdge(); + if((woeb != 0) && (woeb->GetaVertex() == v1) && (woeb->GetbVertex() == v2)) + + //if((*it1)->GetbVertex() == v2) + + { + // The oriented edge already exists + cerr << "Warning: edge " << v1->GetId() << " - " << v2->GetId() << " appears twice, correcting" << endl; + // Adds the edge to the face + //AddEdge((*it1)->GetaOEdge()); + AddEdge(woeb); + (*it1)->SetNumberOfOEdges((*it1)->GetNumberOfOEdges()+1); + //sets these vertices as border: + v1->SetBorder(true); + v2->SetBorder(true); + //return (*it1)->GetaOEdge(); + return woeb; + } + } + + // the oriented edge we're about to build + WOEdge *pOEdge = new WOEdge; + + WEdge * edge; // The edge containing the oriented edge. + + // checks whether this edge already exists or not + // If it exists, it points outward v2 + + bool exist = false; + WOEdge *pInvertEdge = NULL; // The inverted edge if it exists + vector<WEdge *>& v2Edges = v2->GetEdges(); + vector<WEdge *>::iterator it; + for(it=v2Edges.begin(); it!=v2Edges.end(); it++) + { + if((*it)->GetbVertex() == v1) + { + // The invert edge already exists + exist = true; + pInvertEdge = (*it)->GetaOEdge(); + break; + } + } + + //DEBUG: + + + if(true == exist) // The invert edge already exists + { + // Retrieves the corresponding edge + edge = pInvertEdge->GetOwner(); + + // Sets the a Face (retrieved from pInvertEdge + pOEdge->SetaFace(pInvertEdge->GetbFace()); + + // Updates the invert edge: + pInvertEdge->SetaFace(this); + } + else // The invert edge does not exist yet + { + // we must create a new edge + //edge = new WEdge; + edge = instanciateEdge(); + + // updates the a,b vertex edges list: + v1->AddEdge(edge); + v2->AddEdge(edge); + + } + + pOEdge->SetOwner(edge); + // Add the vertices: + pOEdge->SetaVertex(v1); + pOEdge->SetbVertex(v2); + + // Debug: + if(v1->GetId() == v2->GetId()) + cerr << "Warning: edge " << this << " null with vertex " << v1->GetId() << endl; + + edge->AddOEdge(pOEdge); + //edge->SetNumberOfOEdges(edge->GetNumberOfOEdges()+1); + + // Add this face (the b face) + pOEdge->SetbFace(this); + + // Adds the edge to the face + AddEdge(pOEdge); + + return pOEdge; +} + + +bool +WFace::getOppositeEdge (const WVertex *v, WOEdge* &e) +{ + if (_OEdgeList.size()!=3) return false; + + vector<WOEdge *>::iterator it; + e=NULL; + for(it=_OEdgeList.begin(); it!=_OEdgeList.end(); it++) + if ((*it)->GetaVertex()==v) e=*it; + if (!e) return false; + e=NULL; + for(it=_OEdgeList.begin(); it!=_OEdgeList.end(); it++) + if (((*it)->GetaVertex()!=v) && ((*it)->GetbVertex()!=v)) e=*it; + if (!e) return false; + else return true; +} + +real +WFace::getArea () +{ + vector<WOEdge *>::iterator it; + Vec3r origin=(*(_OEdgeList.begin()))->GetaVertex()->GetVertex(); + it=_OEdgeList.begin(); + real a=0; + for (it=it++; it!=_OEdgeList.end(); it++) { + Vec3r v1=Vec3r((*it)->GetaVertex()->GetVertex() - origin); + Vec3r v2=Vec3r((*it)->GetbVertex()->GetVertex() - origin); + a += (v1 ^ v2).norm() / 2.0; + } + return a; +} + + +WOEdge* +WFace::GetPrevOEdge(WOEdge* iOEdge) + { + vector<WOEdge*>::iterator woe,woend, woefirst; + woefirst = _OEdgeList.begin(); + woend=_OEdgeList.end(); + WOEdge *prev =*woefirst; + woe=woefirst; + woe++; + for(; + woe!=woend; + woe++) + { + if((*woe) == iOEdge) + return prev; + prev= *woe; + } + // We left the loop. That means that the first + // OEdge was the good one: + if((*woefirst)==iOEdge) + return prev; + + return NULL; + } + +WShape * WFace::getShape() +{ + return GetVertex(0)->shape(); +} + + /**********************************/ + /* */ + /* */ + /* WShape */ + /* */ + /* */ + /**********************************/ + + +LIB_WINGED_EDGE_EXPORT +unsigned WShape::_SceneCurrentId = 0; + +WShape * WShape::dupplicate() +{ + WShape *clone = new WShape(*this); + return clone; +} + +WShape::WShape(WShape& iBrother) +{ + _Id = iBrother.GetId(); + _Materials = iBrother._Materials; + _meanEdgeSize = iBrother._meanEdgeSize; + iBrother.bbox(_min, _max); + vector<WVertex*>& vertexList = iBrother.GetVertexList(); + vector<WVertex*>::iterator v=vertexList.begin(), vend=vertexList.end(); + for(; + v!=vend; + v++) + { + //WVertex *newVertex = new WVertex(*(*v)); + WVertex *newVertex = (*v)->dupplicate(); + + newVertex->SetShape(this); + AddVertex(newVertex); + } + + vector<WEdge*>& edgeList = iBrother.GetEdgeList(); + vector<WEdge*>::iterator e=edgeList.begin(), eend=edgeList.end(); + for(; + e!=eend; + e++) + { + //WEdge *newEdge = new WEdge(*(*e)); + WEdge *newEdge = (*e)->dupplicate(); + AddEdge(newEdge); + } + + vector<WFace*>& faceList = iBrother.GetFaceList(); + vector<WFace*>::iterator f=faceList.begin(), fend=faceList.end(); + for(; + f!=fend; + f++) + { + //WFace *newFace = new WFace(*(*f)); + WFace *newFace = (*f)->dupplicate(); + AddFace(newFace); + } + + // update all pointed addresses thanks to the newly created objects: + vend=_VertexList.end(); + for(v=_VertexList.begin(); + v!=vend; + v++) + { + const vector<WEdge*>& vedgeList = (*v)->GetEdges(); + vector<WEdge*> newvedgelist; + unsigned int i; + for(i=0; i<vedgeList.size(); i++) + { + WEdge *current = vedgeList[i]; + edgedata * currentvedata = (edgedata*)current->userdata; + newvedgelist.push_back(currentvedata->_copy); + } + (*v)->SetEdges(newvedgelist); + } + + eend = _EdgeList.end(); + for(e=_EdgeList.begin(); + e!=eend; + e++) + { + // update aOedge: + WOEdge *aoEdge = (*e)->GetaOEdge(); + aoEdge->SetaVertex(((vertexdata*)(aoEdge->GetaVertex()->userdata))->_copy); + aoEdge->SetbVertex(((vertexdata*)(aoEdge->GetbVertex()->userdata))->_copy); + if(NULL != aoEdge->GetaFace()) + aoEdge->SetaFace(((facedata*)(aoEdge->GetaFace()->userdata))->_copy); + aoEdge->SetbFace(((facedata*)(aoEdge->GetbFace()->userdata))->_copy); + aoEdge->SetOwner(((edgedata*)(aoEdge->GetOwner()->userdata))->_copy); + // update bOedge: + + WOEdge *boEdge = (*e)->GetbOEdge(); + if(boEdge != 0) + { + boEdge->SetaVertex(((vertexdata*)(boEdge->GetaVertex()->userdata))->_copy); + boEdge->SetbVertex(((vertexdata*)(boEdge->GetbVertex()->userdata))->_copy); + if(NULL != boEdge->GetaFace()) + boEdge->SetaFace(((facedata*)(boEdge->GetaFace()->userdata))->_copy); + boEdge->SetbFace(((facedata*)(boEdge->GetbFace()->userdata))->_copy); + boEdge->SetOwner(((edgedata*)(boEdge->GetOwner()->userdata))->_copy); + } + } + + fend = _FaceList.end(); + for(f=_FaceList.begin(); + f!=fend; + f++) + { + unsigned i; + const vector<WOEdge*>& oedgeList = (*f)->GetEdgeList(); + vector<WOEdge*> newoedgelist; + + unsigned n = oedgeList.size(); + for(i=0; i<n; i++) + { + WOEdge *current = oedgeList[i]; + oedgedata * currentoedata = (oedgedata*)current->userdata; + newoedgelist.push_back(currentoedata->_copy); + //oedgeList[i] = currentoedata->_copy; + //oedgeList[i] = ((oedgedata*)(oedgeList[i]->userdata))->_copy; + } + (*f)->SetEdgeList(newoedgelist); + } + + // Free all memory (arghh!) + // Vertex + vend = iBrother.GetVertexList().end(); + for(v=iBrother.GetVertexList().begin(); + v!=vend; + v++) + { + delete (vertexdata*)((*v)->userdata); + (*v)->userdata = NULL; + } + + // Edges and OEdges: + eend = iBrother.GetEdgeList().end(); + for(e=iBrother.GetEdgeList().begin(); + e!=eend; + e++) + { + delete (edgedata*)((*e)->userdata); + (*e)->userdata = NULL; + // OEdge a : + delete (oedgedata*)((*e)->GetaOEdge()->userdata); + (*e)->GetaOEdge()->userdata = NULL; + // OEdge b: + WOEdge* oedgeb = (*e)->GetbOEdge(); + if(NULL != oedgeb) + { + delete (oedgedata*)(oedgeb->userdata); + oedgeb->userdata = NULL; + } + } + // Faces + fend = iBrother.GetFaceList().end(); + for(f=iBrother.GetFaceList().begin(); + f!=fend; + f++) + { + delete (facedata*)((*f)->userdata); + (*f)->userdata = NULL; + } +} + +WFace* WShape::MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterial) +{ + // allocate the new face + WFace *face = instanciateFace(); + + return MakeFace(iVertexList, iMaterial, face); +} + +WFace * WShape::MakeFace(vector<WVertex*>& iVertexList, vector<Vec3r>& iNormalsList, vector<Vec2r>& iTexCoordsList, unsigned iMaterial) +{ + // allocate the new face + WFace *face = MakeFace(iVertexList, iMaterial); + + if(0 == face) + + return 0; + + // set the list of per-vertex normals + face->SetNormalList(iNormalsList); + // set the list of per-vertex tex coords + face->SetTexCoordsList(iTexCoordsList); + + return face; +} + +WFace* WShape::MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterial, WFace *face) +{ + + int id = _FaceList.size(); + + face->SetMaterialIndex(iMaterial); + + // Check whether we have a degenerated face: + + // LET'S HACK IT FOR THE TRIANGLE CASE: + + if(3 == iVertexList.size()) + + { + + if((iVertexList[0] == iVertexList[1]) + + || (iVertexList[0] == iVertexList[2]) + + || (iVertexList[2] == iVertexList[1])) + + { + + cerr << "Warning: degenerated triangle detected, correcting" << endl; + return 0; + + } + + } + // vertex pointers used to build each edge + vector<WVertex*>::iterator va, vb, it; + + va = iVertexList.begin(); + vb = va; + for(; va != iVertexList.end(); va = vb) + { + vb++; + // Adds va to the vertex list: + //face->AddVertex(*va); + + WOEdge * oedge; + if(*va == iVertexList.back()) + oedge = face->MakeEdge(*va, iVertexList.front()); //for the last (closing) edge + else + oedge = face->MakeEdge(*va, *vb); + + + if(oedge == 0) + return 0; + + + WEdge *edge = oedge->GetOwner(); + if(1 == edge->GetNumberOfOEdges()) + { + // means that we just created a new edge and that we must add it to the + // shape's edges list + edge->SetId(_EdgeList.size()); + AddEdge(edge); + // compute the mean edge value: + _meanEdgeSize += edge->GetaOEdge()->getVec3r().norm(); + } + } + + // compute the face normal (v1v2 ^ v1v3) + WVertex *v1, *v2, *v3; + it = iVertexList.begin(); + v1 = *it; + it++; + v2 = *it; + it++; + v3 = *it; + + Vec3r vector1(v2->GetVertex()-v1->GetVertex()); + Vec3r vector2(v3->GetVertex()-v1->GetVertex()); + + Vec3r normal(vector1 ^ vector2); + normal.normalize(); + face->SetNormal(normal); + + // Add the face to the shape's faces list: + face->SetId(id); + AddFace(face); + + return face; +} |