Mask.cpp

Go to the documentation of this file.
00001 // -*- c-basic-offset: 4 -*-
00002 
00011 /*  This program is free software; you can redistribute it and/or
00012  *  modify it under the terms of the GNU General Public
00013  *  License as published by the Free Software Foundation; either
00014  *  version 2 of the License, or (at your option) any later version.
00015  *
00016  *  This software is distributed in the hope that it will be useful,
00017  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019  *  General Public License for more details.
00020  *
00021  *  You should have received a copy of the GNU General Public
00022  *  License along with this software; if not, write to the Free Software
00023  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00024  *
00025  */
00026 
00027 // for debugging
00028 #include <iostream>
00029 #include <stdio.h>
00030 
00031 #include "Mask.h"
00032 
00033 #include <iostream>
00034 #include <vector>
00035 #include <panotools/PanoToolsInterface.h>
00036 #include <panodata/PTScriptParsing.h>
00037 
00038 namespace HuginBase {
00039 
00040 using namespace hugin_utils;
00041 
00042 bool MaskPolygon::isInside(const FDiff2D p) const
00043 {
00044     if(m_polygon.size()<3)
00045         return false;
00046     if(!m_boundingBox.contains(vigra::Point2D(p.x,p.y)))
00047         return false;
00048     int wind=getWindingNumber(p);
00049     if(m_invert)
00050         return wind==0;
00051     else
00052         return wind!=0;
00053 };
00054 
00055 int MaskPolygon::getWindingNumber(const FDiff2D p) const
00056 {
00057     // algorithm is modified version of winding number method
00058     // described at http://www.softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
00059     // Copyright 2001, softSurfer (www.softsurfer.com)
00060     // This code may be freely used and modified for any purpose
00061     // providing that this copyright notice is included with it.
00062     if(m_polygon.size()<3)
00063         return 0;
00064     int wind=0;
00065     FDiff2D a=m_polygon[m_polygon.size()-1];
00066     for(unsigned int i=0;i<m_polygon.size();i++)
00067     {
00068         FDiff2D b=m_polygon[i];
00069         if(a.y<=p.y)
00070         {
00071             if(b.y>p.y)
00072                 if((b.x-a.x)*(p.y-a.y)<(p.x-a.x)*(b.y-a.y))
00073                     wind++;
00074         }
00075         else
00076         {
00077             if(b.y<=p.y)
00078                 if((b.x-a.x)*(p.y-a.y)>(p.x-a.x)*(b.y-a.y))
00079                     wind--;
00080         };
00081         a=b;
00082     };
00083     return wind;
00084 };
00085 
00086 int MaskPolygon::getTotalWindingNumber() const
00087 {
00088     if(m_polygon.size()<2)
00089         return 0;
00090     MaskPolygon diffPoly;
00091     unsigned int count=m_polygon.size();
00092     for(unsigned int i=0;i<count;i++)
00093     {
00094         diffPoly.addPoint(m_polygon[(i+1)%count]-m_polygon[i]);
00095     };
00096     return diffPoly.getWindingNumber(FDiff2D(0,0));
00097 };
00098 
00099 bool MaskPolygon::isPositive() const
00100 {
00101     return (m_maskType==Mask_positive) || 
00102            (m_maskType==Mask_Stack_positive);
00103 };
00104 
00105 void MaskPolygon::setMaskPolygon(const VectorPolygon newMask)
00106 {
00107     m_polygon=newMask;
00108     calcBoundingBox();
00109 };
00110 
00111 void MaskPolygon::addPoint(const FDiff2D p) 
00112 {
00113     m_polygon.push_back(p);
00114     calcBoundingBox();
00115 };
00116 
00117 void MaskPolygon::insertPoint(const unsigned int index, const FDiff2D p)
00118 {
00119     if(index<=m_polygon.size())
00120     {
00121         m_polygon.insert(m_polygon.begin()+index,p);
00122         calcBoundingBox();
00123     };
00124 };
00125 
00126 
00127 void MaskPolygon::removePoint(const unsigned int index)
00128 {
00129     if(index<m_polygon.size())
00130     {
00131         m_polygon.erase(m_polygon.begin()+index);
00132         calcBoundingBox();
00133     };
00134 };
00135 
00136 void MaskPolygon::movePointTo(const unsigned int index, const hugin_utils::FDiff2D p)
00137 {
00138     if(index<m_polygon.size())
00139     {
00140         m_polygon[index].x=p.x;
00141         m_polygon[index].y=p.y;
00142         calcBoundingBox();
00143     };
00144 };
00145 
00146 void MaskPolygon::movePointBy(const unsigned int index, const hugin_utils::FDiff2D diff)
00147 {
00148     if(index<m_polygon.size())
00149     {
00150         m_polygon[index].x+=diff.x;
00151         m_polygon[index].y+=diff.y;
00152         calcBoundingBox();
00153     };
00154 };
00155 
00156 void MaskPolygon::scale(const double factorx,const double factory)
00157 {
00158     for(unsigned int i=0;i<m_polygon.size();i++)
00159     {
00160         m_polygon[i].x*=factorx;
00161         m_polygon[i].y*=factory;
00162     };
00163     calcBoundingBox();
00164 };
00165 
00166 void MaskPolygon::transformPolygon(const PTools::Transform &trans)
00167 {
00168     double xnew,ynew;
00169     VectorPolygon newPoly;
00170     for(unsigned int i=0;i<m_polygon.size();i++)
00171     {
00172         if(trans.transformImgCoord(xnew,ynew,m_polygon[i].x,m_polygon[i].y))
00173         {
00174             newPoly.push_back(FDiff2D(xnew,ynew));
00175         };
00176     };
00177     m_polygon=newPoly;
00178     calcBoundingBox();
00179 };
00180 
00181 void MaskPolygon::subSample(const double max_distance)
00182 {
00183     if(m_polygon.size()<3)
00184         return;
00185     VectorPolygon oldPoly=m_polygon;
00186     unsigned int count=oldPoly.size();
00187     m_polygon.clear();
00188     for(unsigned int i=0;i<count;i++)
00189     {
00190         addPoint(oldPoly[i]);
00191         FDiff2D p1=oldPoly[i];
00192         FDiff2D p2=oldPoly[(i+1)%count];
00193         double distance=norm(p2-p1);
00194         if(distance>max_distance)
00195         {
00196             //add intermediate points
00197             double currentDistance=max_distance;
00198             while(currentDistance<distance)
00199             {
00200                 FDiff2D p_new=p1+(p2-p1)*currentDistance/distance;
00201                 addPoint(p_new);
00202                 currentDistance+=max_distance;
00203             };
00204         };
00205     };
00206 };
00207 
00208 void MaskPolygon::calcBoundingBox()
00209 {
00210     if(m_polygon.size()>0)
00211     {
00212         m_boundingBox.setUpperLeft(vigra::Point2D(m_polygon[0].x,m_polygon[0].y));
00213         m_boundingBox.setLowerRight(vigra::Point2D(m_polygon[0].x+1,m_polygon[0].y+1));
00214         if(m_polygon.size()>1)
00215         {
00216             for(unsigned int i=1;i<m_polygon.size();i++)
00217             {
00218                 m_boundingBox|=vigra::Point2D(m_polygon[i].x,m_polygon[i].y);
00219             };
00220         };
00221         //adding a small border to get no rounding error because polygon coordinates are float
00222         //numbers, but bounding box has integer coordinates
00223         m_boundingBox.addBorder(2);
00224     };
00225 };
00226 
00227 //helper function for clipping
00228 enum clipSide
00229 {
00230     clipLeft=0,
00231     clipRight,
00232     clipTop,
00233     clipBottom
00234 };
00235 
00236 bool clip_isSide(const FDiff2D p, const vigra::Rect2D r, const clipSide side)
00237 {
00238     switch(side){
00239         case clipLeft:
00240             return p.x>=r.left();
00241         case clipRight:
00242             return p.x<=r.right();
00243         case clipTop:
00244             return p.y>=r.top();
00245         case clipBottom:
00246             return p.y<=r.bottom();
00247     };
00248     //this should never happens
00249     return false;
00250 }
00251 
00252 FDiff2D clip_getIntersection(const FDiff2D p, const FDiff2D q, const vigra::Rect2D r, const clipSide side)
00253 {
00254     double a;
00255     double b;
00256     double xnew;
00257     double ynew;
00258     if(q.x-p.x==0)
00259     {
00260         a=0;
00261         b=p.y;
00262     }
00263     else
00264     {
00265         a=(q.y-p.y)/(q.x-p.x);
00266         b=p.y-p.x*a;
00267     };
00268     switch(side){
00269         case clipLeft:
00270             xnew=r.left();
00271             ynew=xnew*a+b;
00272             break;
00273         case clipRight:
00274             xnew=r.right();
00275             ynew=xnew*a+b;
00276             break;
00277         case clipTop:
00278             ynew=r.top();
00279             if(a!=0)
00280                 xnew=(ynew-b)/a;
00281             else
00282                 xnew=p.x;
00283             break;
00284         case clipBottom:
00285             ynew=r.bottom();
00286             if(a!=0)
00287                 xnew=(ynew-b)/a;
00288             else
00289                 xnew=p.x;
00290             break;
00291     };
00292     return FDiff2D(xnew,ynew);
00293 };
00294 
00295 VectorPolygon clip_onPlane(const VectorPolygon polygon, const vigra::Rect2D r, const clipSide side)
00296 {
00297     if(polygon.size()<3)
00298     {
00299         return polygon;
00300     };
00301     FDiff2D s=polygon[polygon.size()-1];
00302     FDiff2D p;
00303     VectorPolygon newPolygon;
00304     for(unsigned int i=0;i<polygon.size();i++)
00305     {
00306         p=polygon[i];
00307         if(clip_isSide(p,r,side))
00308         {
00309             // point p is "inside"
00310             if(!clip_isSide(s,r,side))
00311                 // and point s is "outside"
00312                 newPolygon.push_back(clip_getIntersection(p,s,r,side));
00313             newPolygon.push_back(p);
00314         }
00315         else
00316         {
00317             //point p is "outside"
00318             if(clip_isSide(s,r,side))
00319                 //ans point s is "inside"
00320                 newPolygon.push_back(clip_getIntersection(s,p,r,side));
00321         };
00322         s=p;
00323     };
00324     return newPolygon;
00325 };
00326 
00327 bool MaskPolygon::clipPolygon(const vigra::Rect2D rect)
00328 {
00329     //clipping using Sutherland-Hodgman algorithm
00330     m_polygon=clip_onPlane(m_polygon, rect, clipLeft);
00331     m_polygon=clip_onPlane(m_polygon, rect, clipRight);
00332     m_polygon=clip_onPlane(m_polygon, rect, clipTop);
00333     m_polygon=clip_onPlane(m_polygon, rect, clipBottom);
00334     return (m_polygon.size()>2);
00335 };
00336 
00337 //helper function for clipping
00344 bool clip_insideCircle(const FDiff2D p, const FDiff2D center, const double radius)
00345 {
00346     return p.squareDistance(center)<=radius*radius;
00347 };
00348 
00356 std::vector<FDiff2D> clip_getIntersectionCircle(const FDiff2D p, const FDiff2D s, const FDiff2D center, const double radius)
00357 {
00358     std::vector<FDiff2D> intersections;
00359     FDiff2D slope=s-p;
00360     if(slope.squareLength()<1e-5)
00361     {
00362         return intersections;
00363     };
00364     FDiff2D p2=p-center;
00365     double dotproduct=p2.x*slope.x+p2.y*slope.y;
00366     double root=sqrt(dotproduct*dotproduct-slope.squareLength()*(p2.squareLength()-radius*radius));
00367     double t1=(-dotproduct+root)/slope.squareLength();
00368     double t2=(-dotproduct-root)/slope.squareLength();
00369     std::set<double> t;
00370     if(t1>0 && t1<1)
00371     {
00372         t.insert(t1);
00373     };
00374     if(t2>0 && t2<1)
00375     {
00376         if(fabs(t2-t1)>1e-5)
00377         {
00378             t.insert(t2);
00379         };
00380     };
00381     if(t.size()>0)
00382     {
00383         for(std::set<double>::const_iterator it=t.begin();it!=t.end();it++)
00384         {
00385             intersections.push_back(p+slope*(*it));
00386         };
00387     };
00388     return intersections;
00389 };
00390 
00392 double angle_between(const FDiff2D a, const FDiff2D b)
00393 {
00394     return asin((a.x*b.y-a.y*b.x)/(sqrt(a.squareLength())*sqrt(b.squareLength())));
00395 };
00396 
00404 void generateArc(VectorPolygon& poly, const FDiff2D s, const FDiff2D center, const double radius, const bool clockwise)
00405 {
00406     if(poly.size()==0)
00407     {
00408         return;
00409     };
00410     FDiff2D p=poly[poly.size()-1];
00411     double maxDistance=5.0;
00412     if(p.squareDistance(s)<maxDistance*maxDistance)
00413     {
00414         return;
00415     };
00416     double angle=atan2(p.y-center.y,p.x-center.x);
00417     double final_angle=atan2(s.y-center.y,s.x-center.x);
00418     //step 1 degree or less, so that max distance between 2 points is smaller than maxDistance
00419     double step=std::min<double>(PI/180,atan2(maxDistance,radius));
00420     if(!clockwise)
00421     {
00422         while(final_angle<angle)
00423         {
00424             final_angle+=2*PI;
00425         };
00426         angle+=step;
00427         while(angle<final_angle)
00428         {
00429             poly.push_back(FDiff2D(cos(angle)*radius+center.x,sin(angle)*radius+center.y));
00430             angle+=step;
00431         };
00432     }
00433     else
00434     {
00435         while(final_angle>angle)
00436         {
00437             final_angle-=2*PI;
00438         };
00439         angle-=step;
00440         while(angle>final_angle)
00441         {
00442             poly.push_back(FDiff2D(cos(angle)*radius+center.x,sin(angle)*radius+center.y));
00443             angle-=step;
00444         };
00445     };
00446 };
00447 
00448 bool MaskPolygon::clipPolygon(const FDiff2D center,const double radius)
00449 {
00450     if(radius<=0 || m_polygon.size()<3)
00451     {
00452         return false;
00453     };
00454     FDiff2D s=m_polygon[m_polygon.size()-1];
00455     bool s_inside=clip_insideCircle(s,center,radius);
00456     FDiff2D p;
00457     VectorPolygon newPolygon;
00458     bool needsFinalArc=false;
00459     double angleCovered=0;
00460     double angleCoveredOffset=0;
00461     for(unsigned int i=0;i<m_polygon.size();i++)
00462     {
00463         p=m_polygon[i];
00464         bool p_inside=clip_insideCircle(p,center,radius);
00465         if(p_inside)
00466         {
00467             if(s_inside)
00468             {
00469                 //both points inside
00470                 newPolygon.push_back(p);
00471             }
00472             else
00473             {
00474                 //line crosses circles from outside
00475                 std::vector<FDiff2D> points=clip_getIntersectionCircle(p,s,center,radius);
00476                 DEBUG_ASSERT(points.size()==1);
00477                 angleCovered+=angle_between(s-center,points[0]-center);
00478                 if(newPolygon.size()==0)
00479                 {
00480                     needsFinalArc=true;
00481                     angleCoveredOffset=angleCovered;
00482                 }
00483                 else
00484                 {
00485                     generateArc(newPolygon,points[0],center,radius,angleCovered<0);
00486                 };
00487                 newPolygon.push_back(points[0]);
00488                 newPolygon.push_back(p);
00489             };
00490         }
00491         else
00492         {
00493             if(!s_inside)
00494             {
00495                 //both points outside of circle
00496                 std::vector<FDiff2D> points=clip_getIntersectionCircle(s,p,center,radius);
00497                 //intersection can only be zero points or 2 points
00498                 if(points.size()>1)
00499                 {
00500                     angleCovered+=angle_between(s-center,points[0]-center);
00501                     if(newPolygon.size()==0)
00502                     {
00503                         needsFinalArc=true;
00504                         angleCoveredOffset=angleCovered;
00505                     }
00506                     else
00507                     {
00508                         generateArc(newPolygon,points[0],center,radius,angleCovered<0);
00509                     };
00510                     newPolygon.push_back(points[0]);
00511                     newPolygon.push_back(points[1]);
00512                     angleCovered=angle_between(points[1]-center,p-center);
00513                 }
00514                 else
00515                 {
00516                     angleCovered+=angle_between(s-center,p-center);
00517                 };
00518             }
00519             else
00520             {
00521                 //line segment intersects circle from inside
00522                 std::vector<FDiff2D> points=clip_getIntersectionCircle(s,p,center,radius);
00523                 angleCovered=0;
00524                 DEBUG_ASSERT(points.size()==1);
00525                 newPolygon.push_back(points[0]);
00526             };
00527         };
00528         s=p;
00529         s_inside=p_inside;
00530     };
00531     if(needsFinalArc && newPolygon.size()>1)
00532     {
00533         generateArc(newPolygon,newPolygon[0],center,radius,(angleCovered+angleCoveredOffset)<0);
00534     };        
00535     m_polygon=newPolygon;
00536     return (m_polygon.size()>2);
00537 };
00538 
00539 void MaskPolygon::rotate90(bool clockwise,unsigned int maskWidth,unsigned int maskHeight)
00540 {
00541     for(unsigned int i=0;i<m_polygon.size();i++)
00542     {
00543         if(clockwise)
00544         {
00545             FDiff2D p=m_polygon[i];
00546             m_polygon[i].x=maskHeight-p.y;
00547             m_polygon[i].y=p.x;
00548         }
00549         else
00550         {
00551             FDiff2D p=m_polygon[i];
00552             m_polygon[i].x=p.y;
00553             m_polygon[i].y=maskWidth-p.x;
00554         };
00555     };
00556 };
00557 
00558 unsigned int MaskPolygon::FindPointNearPos(const FDiff2D p, const double tol)
00559 {
00560     if(m_polygon.size()==0)
00561         return UINT_MAX;
00562     FDiff2D p1;
00563     unsigned int j=m_polygon.size()-1;
00564     FDiff2D p2=m_polygon[j];
00565     for(unsigned int i=0;i<m_polygon.size();i++)
00566     {
00567         p1=m_polygon[i];
00568         // find intersection of perpendicular through point p and line between point i and j 
00569         FDiff2D diff=p2-p1;
00570         if(norm(diff)<0.001)
00571             continue;
00572         double u=((p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y))/sqr(norm(diff));
00573         if((u>=0.1) && (u<=0.9))
00574         {
00575             // intersection is between p1 and p2
00576             FDiff2D footpoint=p1+diff*u;
00577             // now check distance between intersection and p
00578             if(norm(p-footpoint)<tol)
00579                 return i==0 ? j+1 : i;
00580         };
00581         j=i;
00582         p2=p1;
00583     };
00584     return UINT_MAX;
00585 };
00586 
00587 MaskPolygon &MaskPolygon::operator=(const MaskPolygon otherPoly)
00588 {
00589     if (this == &otherPoly)
00590         return *this;
00591     setMaskType(otherPoly.getMaskType());
00592     setMaskPolygon(otherPoly.getMaskPolygon());
00593     setImgNr(otherPoly.getImgNr());
00594     setInverted(otherPoly.isInverted());
00595     return *this;
00596 };
00597 
00598 const bool MaskPolygon::operator==(const MaskPolygon &otherPoly) const
00599 {
00600     return ((m_maskType == otherPoly.getMaskType()) && (m_polygon == otherPoly.getMaskPolygon()));
00601 };
00602 
00603 bool MaskPolygon::parsePolygonString(const std::string polygonStr)
00604 {
00605     m_polygon.clear();
00606     if(polygonStr.length()==0)
00607         return false;
00608     std::stringstream is(polygonStr);
00609     while(is.good())
00610     {
00611         double x;
00612         double y;
00613         if(is>>x)
00614             if(is>>y)
00615                 m_polygon.push_back(FDiff2D(x,y));
00616     };
00617     return m_polygon.size()>2;
00618 };
00619 
00620 void MaskPolygon::printPolygonLine(std::ostream &o, const unsigned int newImgNr) const
00621 {
00622     o<<"k i"<<newImgNr<<" ";
00623     o<<"t"<<(int)m_maskType<<" ";
00624     o<<"p\"";
00625     for(unsigned int i=0; i<m_polygon.size(); i++)
00626     {
00627         o<<m_polygon[i].x<<" "<<m_polygon[i].y;
00628         if((i+1)!=m_polygon.size())
00629             o<<" ";
00630     };
00631     o<<"\""<<std::endl;
00632 };
00633 
00634 void LoadMaskFromStream(std::istream& stream,vigra::Size2D& imageSize, MaskPolygonVector &newMasks, size_t imgNr)
00635 {
00636     while (stream.good()) 
00637     {
00638         std::string line;
00639         std::getline(stream,line);
00640         switch (line[0]) 
00641         {
00642             case '#':
00643             {
00644                 unsigned int w;
00645                 if (PTScriptParsing::getIntParam(w, line, "w"))
00646                     imageSize.setWidth(w);
00647                 unsigned int h;
00648                 if (PTScriptParsing::getIntParam(h, line, "h"))
00649                     imageSize.setHeight(h);
00650                 break;
00651             }
00652             case 'k':
00653             {
00654                 HuginBase::MaskPolygon newPolygon;
00655                 //Ignore image number set in mask
00656                 newPolygon.setImgNr(imgNr);
00657                 unsigned int param;
00658                 if (PTScriptParsing::getIntParam(param,line,"t"))
00659                 {
00660                     newPolygon.setMaskType((HuginBase::MaskPolygon::MaskType)param);
00661                 }
00662                 std::string format;
00663                 if (PTScriptParsing::getPTParam(format,line,"p"))
00664                 {
00665                     if(newPolygon.parsePolygonString(format)) {
00666                         newMasks.push_back(newPolygon);
00667                     } 
00668                 }
00669                 break;
00670             }
00671             default:
00672             {
00673                 break;
00674             }
00675         }
00676     }
00677 };
00678 
00679 void SaveMaskToStream(std::ostream& stream, vigra::Size2D imageSize, MaskPolygon &maskToWrite, size_t imgNr)
00680 {
00681     stream << "# w" << imageSize.width() << " h" << imageSize.height() << std::endl;
00682     maskToWrite.printPolygonLine(stream, imgNr);
00683 };
00684 
00685 } // namespace

Generated on Wed Jul 16 01:25:38 2014 for Hugintrunk by  doxygen 1.3.9.1