1 /**************************************************************************** 2 * VCGLib o o * 3 * Visual and Computer Graphics Library o o * 4 * _ O _ * 5 * Copyright(C) 2004-2016 \/)\/ * 6 * Visual Computing Lab /\/| * 7 * ISTI - Italian National Research Council | * 8 * \ * 9 * All rights reserved. * 10 * * 11 * This program is free software; you can redistribute it and/or modify * 12 * it under the terms of the GNU General Public License as published by * 13 * the Free Software Foundation; either version 2 of the License, or * 14 * (at your option) any later version. * 15 * * 16 * This program is distributed in the hope that it will be useful, * 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) * 20 * for more details. * 21 * * 22 ****************************************************************************/ 23 24 #ifndef __VCGLIB_PLANAR_POLYGON_TESSELLATOR 25 #define __VCGLIB_PLANAR_POLYGON_TESSELLATOR 26 27 #include <assert.h> 28 #include <vcg/space/segment2.h> 29 #include <vcg/math/random_generator.h> 30 31 namespace vcg { 32 33 /** \addtogroup space */ 34 /*@{*/ 35 /** 36 A very simple earcut tessellation of planar 2D polygon. 37 Input: a vector or Point2<> 38 Output: a vector of faces as a triple of indices to the input vector 39 */ 40 template <class ScalarType> Cross(const Point2<ScalarType> & p00,const Point2<ScalarType> & p01,const Point2<ScalarType> & p10,const Point2<ScalarType> & p11)41 bool Cross( const Point2<ScalarType> & p00, 42 const Point2<ScalarType> & p01, 43 const Point2<ScalarType> & p10, 44 const Point2<ScalarType> & p11) 45 { 46 Point2<ScalarType> vec0 = p01-p00; 47 Point2<ScalarType> vec1 = p11-p10; 48 if ( ( vec0^ (p11-p00)) * ( vec0^ (p10 - p00)) >=0) return false; 49 if ( ( vec1^ (p01-p10)) * ( vec1^ (p00 - p10)) >=0) return false; 50 return true; 51 } 52 53 template <class S> Intersect(size_t cur,int v2,std::vector<int> & next,std::vector<Point2<S>> & points2)54 bool Intersect(size_t cur , int v2, std::vector<int> & next, std::vector<Point2<S> > & points2){ 55 for(size_t i = 0; i < points2.size();++i) 56 if( (next[i]!=-1) && (i!=cur)) 57 if( Cross(points2[cur], points2[v2],points2[i],points2[next[i]])) 58 return true; 59 return false; 60 } 61 62 63 template <class POINT_CONTAINER> TessellatePlanarPolygon2(POINT_CONTAINER & points2,std::vector<int> & output)64 void TessellatePlanarPolygon2( POINT_CONTAINER & points2, std::vector<int> & output){ 65 typedef typename POINT_CONTAINER::value_type Point2x; 66 typedef typename Point2x::ScalarType S; 67 // tessellate 68 // first very inefficient implementation 69 std::vector<int> next,prev; 70 for(size_t i = 0; i < points2.size(); ++i) next.push_back((i+1)%points2.size()); 71 for(size_t i = 0; i < points2.size(); ++i) prev.push_back((i+points2.size()-1)%points2.size()); 72 int v1,v2; 73 // check orientation 74 S orient = 0.0; 75 for(size_t i = 0 ; i < points2.size(); ++i){ 76 v1 = next[i]; 77 v2 = next[v1]; 78 orient+= (points2[v1] - points2[0]) ^ (points2[v2] - points2[0]); 79 } 80 orient = (orient>0)? 1.0:-1.0; 81 82 int cur = 0; 83 while(output.size()<3*(points2.size()-2)){ 84 v1 = next[cur]; 85 v2 = next[v1]; 86 if( ( (orient*((points2[v1] - points2[cur]) ^ (points2[v2] - points2[cur]))) >= 0.0) && 87 !Intersect(cur, v2,next,points2)) 88 { 89 // output the face 90 output.push_back(cur); 91 output.push_back(v1); 92 output.push_back(v2); 93 94 // readjust the topology 95 next[cur] = v2; 96 prev[v2] = cur; 97 prev[v1] = -1;//unnecessary 98 next[v1] = -1;//unnecessary 99 } 100 else 101 do{cur = (cur+1)%points2.size();} while(next[cur]==-1); 102 } 103 } 104 105 /** 106 A very simple earcut tessellation of planar 2D polygon. 107 Input: a vector or Point3<> 108 Output: a vector of faces as a triple of indices to the input vector 109 110 */ 111 112 template <class POINT_CONTAINER> TessellatePlanarPolygon3(POINT_CONTAINER & points,std::vector<int> & output)113 void TessellatePlanarPolygon3( POINT_CONTAINER & points, std::vector<int> & output){ 114 typedef typename POINT_CONTAINER::value_type Point3x; 115 typedef typename Point3x::ScalarType S; 116 Point3x n; 117 118 math::SubtractiveRingRNG rg; 119 size_t i12[2]; 120 S bestsn = -1.0; 121 Point3x bestn,u,v; 122 for(size_t i =0; i < points.size();++i){ 123 for(size_t j = 0; j < 2; ++j){ i12[j] = i; while(i12[j]==i) i12[j] = rg.generate(points.size()-1);} 124 n = (points[i12[0]]-points[i])^(points[i12[1]]-points[i]); 125 S sn = n.SquaredNorm(); 126 if(sn > bestsn){ bestsn = sn; bestn = n;} 127 } 128 129 GetUV(n,u,v); 130 // project the coordinates 131 std::vector<Point2<S> > points2; 132 for(size_t i = 0; i < points.size(); ++i){ 133 Point3x & p = points[i]; 134 points2.push_back(Point2<S>(p*u,p*v)); 135 } 136 TessellatePlanarPolygon2( points2,output); 137 } 138 139 /*@}*/ 140 } // end namespace 141 #endif 142