 Timestamp:
 03/21/12 18:36:20 (5 years ago)
 Files:

 1 modified
Legend:
 Unmodified
 Added
 Removed

OpenSceneGraph/trunk/src/osgUtil/DelaunayTriangulator.cpp
r12795 r13041 1 /* *c++* OpenSceneGraph  Copyright (C) 19982006 Robert Osfield 1 /* *c++* OpenSceneGraph  Copyright (C) 19982006 Robert Osfield 2 2 * 3 * This library is open source and may be redistributed and/or modified under 4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or 3 * This library is open source and may be redistributed and/or modified under 4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or 5 5 * (at your option) any later version. The full license is in LICENSE file 6 6 * included with this distribution, and on the openscenegraph.org website. 7 * 7 * 8 8 * This library is distributed in the hope that it will be useful, 9 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 11 * OpenSceneGraph Public License for more details. 12 12 */ … … 38 38 // return (Cx, Cy, r^2) 39 39 inline osg::Vec3 compute_circumcircle( 40 const osg::Vec3 &a, 41 const osg::Vec3 &b, 40 const osg::Vec3 &a, 41 const osg::Vec3 &b, 42 42 const osg::Vec3 &c) 43 43 { 44 float D = 45 (a.x()  c.x()) * (b.y()  c.y())  44 float D = 45 (a.x()  c.x()) * (b.y()  c.y())  46 46 (b.x()  c.x()) * (a.y()  c.y()); 47 47 … … 60 60 else 61 61 { 62 cx = 63 (((a.x()  c.x()) * (a.x() + c.x()) + 62 cx = 63 (((a.x()  c.x()) * (a.x() + c.x()) + 64 64 (a.y()  c.y()) * (a.y() + c.y())) / 2 * (b.y()  c.y())  65 65 ((b.x()  c.x()) * (b.x() + c.x()) + 66 66 (b.y()  c.y()) * (b.y() + c.y())) / 2 * (a.y()  c.y())) / D; 67 67 68 cy = 69 (((b.x()  c.x()) * (b.x() + c.x()) + 68 cy = 69 (((b.x()  c.x()) * (b.x() + c.x()) + 70 70 (b.y()  c.y()) * (b.y() + c.y())) / 2 * (a.x()  c.x())  71 71 ((a.x()  c.x()) * (a.x() + c.x()) + … … 85 85 inline bool point_in_circle(const osg::Vec3 &point, const osg::Vec3 &circle) 86 86 { 87 float r2 = 88 (point.x()  circle.x()) * (point.x()  circle.x()) + 87 float r2 = 88 (point.x()  circle.x()) * (point.x()  circle.x()) + 89 89 (point.y()  circle.y()) * (point.y()  circle.y()); 90 90 return r2 <= circle.z()*circle.z(); … … 158 158 b_(0), 159 159 c_(0) {} 160 161 160 161 162 162 Triangle(Vertex_index a, Vertex_index b, Vertex_index c, osg::Vec3Array *points) 163 : a_(a), 164 b_(b), 165 c_(c), 163 : a_(a), 164 b_(b), 165 c_(c), 166 166 cc_(compute_circumcircle((*points)[a_], (*points)[b_], (*points)[c_])) 167 167 { … … 174 174 { 175 175 if (&rhs==this) return *this; 176 176 177 177 a_ = rhs.a_; 178 178 b_ = rhs.b_; … … 182 182 edge_[1] = rhs.edge_[1]; 183 183 edge_[2] = rhs.edge_[2]; 184 184 185 185 return *this; 186 186 } … … 241 241 ie1=c(); 242 242 ie2=a(); 243 } 243 } 244 244 if (ip1==ie1  ip2==ie1) return false; 245 245 if (ip1==ie2  ip2==ie2) return false; 246 246 247 247 osg::Vec2 tp1((*points)[ie1].x(),(*points)[ie1].y()); 248 248 osg::Vec2 tp2((*points)[ie2].x(),(*points)[ie2].y()); 249 249 return intersect(tp1,tp2,p1,p2); 250 250 } 251 251 252 252 bool intersectedby(const osg::Vec2 p1,const osg::Vec2 p2,osg::Vec3Array *points) const { 253 253 // true if line [p1,p2] cuts at least one edge of this triangle … … 290 290 291 291 int lineBisectTest(const osg::Vec3 apt,const osg::Vec3 bpt,const osg::Vec3 cpt, const osg::Vec2 p2) const 292 { 292 { 293 293 osg::Vec2 vp2tp=p2osg::Vec2(apt.x(), apt.y()); // vector from p1 to a. 294 294 // test is: cross product (z component) with ab,ac is opposite signs … … 310 310 return 0; 311 311 } 312 312 313 313 int lineBisects(osg::Vec3Array *points, const unsigned int ip1, const osg::Vec2 p2) const 314 { 314 { 315 315 // return true if line starts at vertex <ip1> and lies between the 2 edges which meet at vertex 316 316 // <vertex> is that which uses index ip1. … … 343 343 return 0; 344 344 } 345 345 346 346 private: 347 347 … … 355 355 if (det!=0) 356 356 { 357 // point on line is P=p1+ua.(p2p1) and Q=p3+ub.(p4p3) 357 // point on line is P=p1+ua.(p2p1) and Q=p3+ub.(p4p3) 358 358 float ua=((p4.x()p3.x())*(p1.y()p3.y())(p4.y()p3.y())*(p1.x()p3.x()))/det; 359 359 float ub=((p2.x()p1.x())*(p1.y()p3.y())(p2.y()p1.y())*(p1.x()p3.x()))/det; … … 365 365 return false; 366 366 } 367 367 368 368 Vertex_index a_; 369 369 Vertex_index b_; 370 370 Vertex_index c_; 371 osg::Vec3 cc_; 371 osg::Vec3 cc_; 372 372 Edge edge_[3]; 373 373 }; … … 452 452 osg::ref_ptr<osg::Vec3Array> constraintverts=new osg::Vec3Array; 453 453 osg::ref_ptr<osgUtil::Tessellator> tscx=new osgUtil::Tessellator; // this assembles all the constraints 454 454 455 455 for (std::vector<unsigned int>::iterator itint=vindexlist.begin(); itint!=vindexlist.end(); itint++) 456 456 { … … 458 458 constraintverts>push_back((*points)[*itint]); 459 459 } 460 460 461 461 unsigned int npts=vindexlist.size(); 462 462 … … 470 470 471 471 // extract triangles from gtess 472 472 473 473 unsigned int ipr; 474 474 for (ipr=0; ipr<gtess>getNumPrimitiveSets(); ipr++) … … 493 493 pidx=vindexlist[prset>index(ic)]; 494 494 } 495 495 496 496 if (prset>index(ic+1)>=npts) 497 497 { … … 504 504 pidx1=vindexlist[prset>index(ic+1)]; 505 505 } 506 506 507 507 if (prset>index(ic+2)>=npts) 508 508 { … … 541 541 pidx1=vindexlist[prset>index(ic+1)]; 542 542 } 543 543 544 544 if (prset>index(ic+2)>=npts) 545 545 { … … 548 548 pidx2=points>size()1; 549 549 } 550 else 550 else 551 551 { 552 552 pidx2=vindexlist[prset>index(ic+2)]; 553 553 } 554 554 555 555 if (ic%2==0) 556 556 { … … 564 564 } 565 565 break; 566 566 567 567 case osg::PrimitiveSet::TRIANGLE_FAN: 568 568 { … … 590 590 pidx1=vindexlist[prset>index(ic)]; 591 591 } 592 592 593 593 if (prset>index(ic+1)>=npts) 594 594 { // this is an added point. … … 637 637 */ 638 638 int nrem=0; 639 osg::Vec3Array *vertices= dynamic_cast< osg::Vec3Array*>(getVertexArray()); 639 osg::Vec3Array *vertices= dynamic_cast< osg::Vec3Array*>(getVertexArray()); 640 640 if (vertices) 641 641 { … … 793 793 // initialize storage structures 794 794 Triangle_list triangles; 795 Triangle_list discarded_tris; 795 Triangle_list discarded_tris; 796 796 797 797 // GWM July 2005 add constraint vertices to terrain … … 825 825 // presort sample points 826 826 OSG_INFO << "DelaunayTriangulator: presorting sample points\n"; 827 std::sort(points>begin(), points>end(), Sample_point_compare); 827 std::sort(points>begin(), points>end(), Sample_point_compare); 828 828 // 24.12.06 add convex hull of points to force sensible outline. 829 829 osg::ref_ptr<osgUtil::DelaunayConstraint> dcconvexhull=getconvexhull(points); … … 831 831 832 832 // set the last valid index for the point list 833 GLuint last_valid_index = points>size()  1; 833 GLuint last_valid_index = points>size()  1; 834 834 835 835 // find the minimum and maximum x values in the point list … … 837 837 float maxx = (*points)[last_valid_index].x(); 838 838 839 // find the minimum and maximum y values in the point list 839 // find the minimum and maximum y values in the point list 840 840 float miny = (*points)[0].y(); 841 841 float maxy = miny; 842 842 843 843 OSG_INFO << "DelaunayTriangulator: finding minimum and maximum Y values\n"; 844 844 osg::Vec3Array::const_iterator mmi; … … 848 848 if (mmi>y() > maxy) maxy = mmi>y(); 849 849 } 850 850 851 851 // add supertriangle vertices to the point list 852 852 // gwm added 1.05* to ensure that supervertices are outside the domain of points. … … 860 860 points_>push_back(osg::Vec3(maxx + .10*(maxx  minx), maxy + .10*(maxy  miny), 0)); 861 861 points_>push_back(osg::Vec3(minx  .10*(maxx  minx), maxy + .10*(maxy  miny), 0)); 862 863 // add supertriangles to triangle list 862 863 // add supertriangles to triangle list 864 864 triangles.push_back(Triangle(last_valid_index+1, last_valid_index+2, last_valid_index+3, points)); 865 865 triangles.push_back(Triangle(last_valid_index+4, last_valid_index+1, last_valid_index+3, points)); 866 866 867 868 // begin triangulation 867 868 // begin triangulation 869 869 GLuint pidx = 0; 870 osg::Vec3Array::const_iterator i; 871 872 OSG_INFO << "DelaunayTriangulator: triangulating vertex grid (" << (points>size()3) <<" points)\n"; 870 osg::Vec3Array::const_iterator i; 871 872 OSG_INFO << "DelaunayTriangulator: triangulating vertex grid (" << (points>size()3) <<" points)\n"; 873 873 874 874 for (i=points>begin(); i!=points>end(); ++i, ++pidx) … … 922 922 edge.set_duplicate(!edge.get_duplicate()); 923 923 } 924 } 924 } 925 925 triangles.erase(j); 926 926 } … … 982 982 if (titr>isedge(ip1,ip2)) edgused=true; 983 983 if (titr>isedge(ip2,ip1)) edgused=true; 984 // if (edgused) OSG_WARN << "Edge used in triangle " << it << " " << 984 // if (edgused) OSG_WARN << "Edge used in triangle " << it << " " << 985 985 // titr>a()<<","<< titr>b()<<","<< titr>c()<< std::endl; 986 986 it++; … … 1007 1007 { 1008 1008 // triangle titr starts the constraint edge 1009 std::vector<unsigned int> edgeRight, edgeLeft; 1009 std::vector<unsigned int> edgeRight, edgeLeft; 1010 1010 edgeRight.push_back(ip1); 1011 1011 edgeLeft.push_back(ip1); … … 1038 1038 icut=tradj>whichEdge(points_.get(),p1,p2,e1,e2); 1039 1039 // OSG_WARN << ntr << " cur triedge " << icut << " " << ip1 << 1040 // " to " << ip2 << " tadj " << tradj>a()<< ","<<tradj>b() <<"," 1040 // " to " << ip2 << " tadj " << tradj>a()<< ","<<tradj>b() <<"," 1041 1041 // <<tradj>c() <<std::endl; 1042 1042 if (icut==1) {e1=tradj>b(); e2=tradj>c();} // icut=1 implies vertex a is not involved … … 1080 1080 { 1081 1081 bool deleted=false; 1082 for (std::vector<const Triangle *>::iterator deleteTri=trisToDelete.begin(); 1082 for (std::vector<const Triangle *>::iterator deleteTri=trisToDelete.begin(); 1083 1083 deleteTri!=trisToDelete.end(); ) 1084 1084 { … … 1159 1159 } 1160 1160 } 1161 1161 1162 1162 // LF August 2011 fix crash when no triangle is created 1163 1163 if (!pt_indices.size()) 1164 1164 { 1165 1165 OSG_WARN << "Warning: DelaunayTriangulator::triangulate(): no triangle generated" << std::endl; 1166 return false; 1167 } 1168 1166 return false; 1167 } 1168 1169 1169 prim_tris_ = new osg::DrawElementsUInt(GL_TRIANGLES, pt_indices.size(), &(pt_indices.front())); 1170 1170 1171 1171 OSG_INFO << "DelaunayTriangulator: process done, " << prim_tris_>getNumPrimitives() << " triangles remain\n"; 1172 1172 1173 1173 return true; 1174 1174 } … … 1265 1265 } 1266 1266 } 1267 1267 1268 1268 return theta/osg::PI/2.0; // should be 0 or 2 pi. 1269 1269 } 1270 1270 osg::DrawElementsUInt *DelaunayConstraint::makeDrawable() 1271 { 1271 { 1272 1272 // initialize index storage vector for internal triangles. 1273 1273 std::vector<GLuint> pt_indices; … … 1276 1276 for (ti=_interiorTris.begin(); ti!=_interiorTris.end(); ++ti) 1277 1277 { 1278 1278 1279 1279 // if (normals_.valid()) { 1280 1280 // (normals_.get())>push_back(ti>compute_normal(points)); 1281 1281 // } 1282 1282 1283 1283 pt_indices.push_back((*ti)[0]); 1284 1284 pt_indices.push_back((*ti)[1]); … … 1286 1286 } 1287 1287 prim_tris_ = new osg::DrawElementsUInt(GL_TRIANGLES, pt_indices.size(), &(pt_indices.front())); 1288 1288 1289 1289 return prim_tris_.get(); 1290 1290 } 1291 bool DelaunayConstraint::contains(const osg::Vec3 &testpoint) const 1291 bool DelaunayConstraint::contains(const osg::Vec3 &testpoint) const 1292 1292 { 1293 1293 // true if point is internal to the loop. … … 1295 1295 return fabs(theta)>0.9; // should be 0 or 1 (or 2,3,4 for very complex not permitted loops). 1296 1296 } 1297 bool DelaunayConstraint::outside(const osg::Vec3 &testpoint) const 1297 bool DelaunayConstraint::outside(const osg::Vec3 &testpoint) const 1298 1298 { 1299 1299 // true if point is outside the loop. … … 1365 1365 tscx>setTessellationType(osgUtil::Tessellator::TESS_TYPE_GEOMETRY); 1366 1366 tscx>setBoundaryOnly(true); 1367 tscx>setWindingType( osgUtil::Tessellator::TESS_WINDING_ODD); 1367 tscx>setWindingType( osgUtil::Tessellator::TESS_WINDING_ODD); 1368 1368 // ODD chooses the winding =1, NOT overlapping areas of constraints. 1369 1369 // nb this includes all the edges where delaunay constraints meet 1370 1370 // draw a case to convince yourself!. 1371 1371 1372 1372 tscx>retessellatePolygons(*this); // find all edges 1373 1373 }