Changeset 13041 for OpenSceneGraph/trunk/src/osgUtil/DelaunayTriangulator.cpp

Timestamp:

03/21/12 18:36:20 (14 months ago)

Author:

robert

Message:

Ran script to remove trailing spaces and tabs

Files:

• OpenSceneGraph/trunk/src/osgUtil/DelaunayTriangulator.cpp (modified) (40 diffs)

OpenSceneGraph/trunk/src/osgUtil/DelaunayTriangulator.cpp

@@ -1 @@
-/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield 
+/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
  *
- * This library is open source and may be redistributed and/or modified under  
- * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or 
+ * This library is open source and may be redistributed and/or modified under
+ * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
  * (at your option) any later version.  The full license is in LICENSE file
  * included with this distribution, and on the openscenegraph.org website.
- * 
+ *
  * This library 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 
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * OpenSceneGraph Public License for more details.
 */
@@ -38 +38 @@
 // return (Cx, Cy, r^2)
 inline osg::Vec3 compute_circumcircle(
-    const osg::Vec3 &a, 
-    const osg::Vec3 &b, 
+    const osg::Vec3 &a,
+    const osg::Vec3 &b,
     const osg::Vec3 &c)
 {
-    float D = 
-        (a.x() - c.x()) * (b.y() - c.y()) - 
+    float D =
+        (a.x() - c.x()) * (b.y() - c.y()) -
         (b.x() - c.x()) * (a.y() - c.y());
 
@@ -60 +60 @@
     else
     {
-        cx = 
-        (((a.x() - c.x()) * (a.x() + c.x()) + 
+        cx =
+        (((a.x() - c.x()) * (a.x() + c.x()) +
         (a.y() - c.y()) * (a.y() + c.y())) / 2 * (b.y() - c.y()) -
         ((b.x() - c.x()) * (b.x() + c.x()) +
         (b.y() - c.y()) * (b.y() + c.y())) / 2 * (a.y() - c.y())) / D;
 
-        cy = 
-        (((b.x() - c.x()) * (b.x() + c.x()) + 
+        cy =
+        (((b.x() - c.x()) * (b.x() + c.x()) +
         (b.y() - c.y()) * (b.y() + c.y())) / 2 * (a.x() - c.x()) -
         ((a.x() - c.x()) * (a.x() + c.x()) +
@@ -85 +85 @@
 inline bool point_in_circle(const osg::Vec3 &point, const osg::Vec3 &circle)
 {
-    float r2 = 
-        (point.x() - circle.x()) * (point.x() - circle.x()) + 
+    float r2 =
+        (point.x() - circle.x()) * (point.x() - circle.x()) +
         (point.y() - circle.y()) * (point.y() - circle.y());
     return r2 <= circle.z()*circle.z();
@@ -158 +158 @@
         b_(0),
         c_(0) {}
-        
-    
+
+
     Triangle(Vertex_index a, Vertex_index b, Vertex_index c, osg::Vec3Array *points)
-        :    a_(a), 
-            b_(b), 
-            c_(c), 
+        :    a_(a),
+            b_(b),
+            c_(c),
             cc_(compute_circumcircle((*points)[a_], (*points)[b_], (*points)[c_]))
     {
@@ -174 +174 @@
     {
         if (&rhs==this) return *this;
-        
+
         a_ = rhs.a_;
         b_ = rhs.b_;
@@ -182 +182 @@
         edge_[1]  = rhs.edge_[1];
         edge_[2]  = rhs.edge_[2];
-        
+
         return *this;
     }
@@ -241 +241 @@
             ie1=c();
             ie2=a();
-        } 
+        }
         if (ip1==ie1 || ip2==ie1) return false;
         if (ip1==ie2 || ip2==ie2) return false;
-    
+
         osg::Vec2 tp1((*points)[ie1].x(),(*points)[ie1].y());
         osg::Vec2 tp2((*points)[ie2].x(),(*points)[ie2].y());
         return intersect(tp1,tp2,p1,p2);
     }
-    
+
     bool intersectedby(const osg::Vec2 p1,const osg::Vec2 p2,osg::Vec3Array *points) const {
         // true if line [p1,p2] cuts at least one edge of this triangle
@@ -290 +290 @@
 
     int lineBisectTest(const osg::Vec3 apt,const osg::Vec3 bpt,const osg::Vec3 cpt, const osg::Vec2 p2) const
-    { 
+    {
         osg::Vec2 vp2tp=p2-osg::Vec2(apt.x(), apt.y()); // vector from p1 to a.
         // test is: cross product (z component) with ab,ac is opposite signs
@@ -310 +310 @@
         return 0;
     }
-    
+
     int lineBisects(osg::Vec3Array *points, const unsigned int ip1, const osg::Vec2 p2) const
-    { 
+    {
         // return true if line starts at vertex <ip1> and lies between the 2 edges which meet at vertex
         // <vertex> is that which uses index ip1.
@@ -343 +343 @@
         return 0;
     }
-    
+
 private:
 
@@ -355 +355 @@
         if (det!=0)
         {
-            // point on line is P=p1+ua.(p2-p1) and Q=p3+ub.(p4-p3) 
+            // point on line is P=p1+ua.(p2-p1) and Q=p3+ub.(p4-p3)
             float ua=((p4.x()-p3.x())*(p1.y()-p3.y())-(p4.y()-p3.y())*(p1.x()-p3.x()))/det;
             float ub=((p2.x()-p1.x())*(p1.y()-p3.y())-(p2.y()-p1.y())*(p1.x()-p3.x()))/det;
@@ -365 +365 @@
         return false;
     }
-    
+
     Vertex_index a_;
     Vertex_index b_;
     Vertex_index c_;
-    osg::Vec3 cc_;    
+    osg::Vec3 cc_;
     Edge edge_[3];
 };
@@ -452 +452 @@
     osg::ref_ptr<osg::Vec3Array> constraintverts=new osg::Vec3Array;
     osg::ref_ptr<osgUtil::Tessellator> tscx=new osgUtil::Tessellator; // this assembles all the constraints
-    
+
     for (std::vector<unsigned int>::iterator itint=vindexlist.begin(); itint!=vindexlist.end(); itint++)
     {
@@ -458 +458 @@
         constraintverts->push_back((*points)[*itint]);
     }
-    
+
     unsigned int npts=vindexlist.size();
 
@@ -470 +470 @@
 
     // extract triangles from gtess
-    
+
     unsigned int ipr;
     for (ipr=0; ipr<gtess->getNumPrimitiveSets(); ipr++)
@@ -493 +493 @@
                     pidx=vindexlist[prset->index(ic)];
                 }
-                
+
                 if (prset->index(ic+1)>=npts)
                 {
@@ -504 +504 @@
                     pidx1=vindexlist[prset->index(ic+1)];
                 }
-                
+
                 if (prset->index(ic+2)>=npts)
                 {
@@ -541 +541 @@
                     pidx1=vindexlist[prset->index(ic+1)];
                 }
-                
+
                 if (prset->index(ic+2)>=npts)
                 {
@@ -548 +548 @@
                     pidx2=points->size()-1;
                 }
-                else 
+                else
                 {
                     pidx2=vindexlist[prset->index(ic+2)];
                 }
-                
+
                 if (ic%2==0)
                 {
@@ -564 +564 @@
             }
             break;
-            
+
         case osg::PrimitiveSet::TRIANGLE_FAN:
             {
@@ -590 +590 @@
                         pidx1=vindexlist[prset->index(ic)];
                     }
-                    
+
                     if (prset->index(ic+1)>=npts)
                     { // this is an added point.
@@ -637 +637 @@
     */
     int nrem=0;
-    osg::Vec3Array *vertices= dynamic_cast< osg::Vec3Array*>(getVertexArray()); 
+    osg::Vec3Array *vertices= dynamic_cast< osg::Vec3Array*>(getVertexArray());
     if (vertices)
     {
@@ -793 +793 @@
     // initialize storage structures
     Triangle_list triangles;
-    Triangle_list discarded_tris;    
+    Triangle_list discarded_tris;
 
     // GWM July 2005 add constraint vertices to terrain
@@ -825 +825 @@
     // pre-sort sample points
     OSG_INFO << "DelaunayTriangulator: pre-sorting sample points\n";
-    std::sort(points->begin(), points->end(), Sample_point_compare);    
+    std::sort(points->begin(), points->end(), Sample_point_compare);
     // 24.12.06 add convex hull of points to force sensible outline.
     osg::ref_ptr<osgUtil::DelaunayConstraint> dcconvexhull=getconvexhull(points);
@@ -831 +831 @@
 
     // set the last valid index for the point list
-    GLuint last_valid_index = points->size() - 1;    
+    GLuint last_valid_index = points->size() - 1;
 
     // find the minimum and maximum x values in the point list
@@ -837 +837 @@
     float maxx = (*points)[last_valid_index].x();
 
-    // find the minimum and maximum y values in the point list    
+    // find the minimum and maximum y values in the point list
     float miny = (*points)[0].y();
     float maxy = miny;
-    
+
     OSG_INFO << "DelaunayTriangulator: finding minimum and maximum Y values\n";
     osg::Vec3Array::const_iterator mmi;
@@ -848 +848 @@
         if (mmi->y() > maxy) maxy = mmi->y();
     }
-    
+
     // add supertriangle vertices to the point list
     // 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));
     points_->push_back(osg::Vec3(minx - .10*(maxx - minx), maxy + .10*(maxy - miny), 0));
-                                                                   
-    // add supertriangles to triangle list                           
+
+    // add supertriangles to triangle list
     triangles.push_back(Triangle(last_valid_index+1, last_valid_index+2, last_valid_index+3, points));
     triangles.push_back(Triangle(last_valid_index+4, last_valid_index+1, last_valid_index+3, points));
 
-    
-    // begin triangulation    
+
+    // begin triangulation
     GLuint pidx = 0;
-    osg::Vec3Array::const_iterator i;    
-    
-    OSG_INFO << "DelaunayTriangulator: triangulating vertex grid (" << (points->size()-3) <<" points)\n";    
+    osg::Vec3Array::const_iterator i;
+
+    OSG_INFO << "DelaunayTriangulator: triangulating vertex grid (" << (points->size()-3) <<" points)\n";
 
     for (i=points->begin(); i!=points->end(); ++i, ++pidx)
@@ -922 +922 @@
                             edge.set_duplicate(!edge.get_duplicate());
                         }
-                    }                    
+                    }
                     triangles.erase(j);
                 }
@@ -982 +982 @@
                                 if (titr->isedge(ip1,ip2)) edgused=true;
                                 if (titr->isedge(ip2,ip1)) edgused=true;
-                                //        if (edgused) OSG_WARN << "Edge used in triangle " << it << " " << 
+                                //        if (edgused) OSG_WARN << "Edge used in triangle " << it << " " <<
                                 //            titr->a()<<","<< titr->b()<<","<< titr->c()<<  std::endl;
                                 it++;
@@ -1007 +1007 @@
                                     {
                                         // triangle titr starts the constraint edge
-                                        std::vector<unsigned int> edgeRight, edgeLeft; 
+                                        std::vector<unsigned int> edgeRight, edgeLeft;
                                         edgeRight.push_back(ip1);
                                         edgeLeft.push_back(ip1);
@@ -1038 +1038 @@
                                                 icut=tradj->whichEdge(points_.get(),p1,p2,e1,e2);
                                                 //    OSG_WARN  << ntr << " cur triedge " << icut << " " << ip1 <<
-                                                //        " to " << ip2 << " tadj " << tradj->a()<< ","<<tradj->b() <<"," 
+                                                //        " to " << ip2 << " tadj " << tradj->a()<< ","<<tradj->b() <<","
                                                 //        <<tradj->c() <<std::endl;
                                                 if        (icut==1) {e1=tradj->b(); e2=tradj->c();} // icut=1 implies vertex a is not involved
@@ -1080 +1080 @@
                                 {
                                     bool deleted=false;
-                                    for (std::vector<const Triangle *>::iterator deleteTri=trisToDelete.begin(); 
+                                    for (std::vector<const Triangle *>::iterator deleteTri=trisToDelete.begin();
                                     deleteTri!=trisToDelete.end(); )
                                     {
@@ -1159 +1159 @@
         }
     }
-    
+
     // LF August 2011 fix crash when no triangle is created
     if (!pt_indices.size())
     {
         OSG_WARN << "Warning: DelaunayTriangulator::triangulate(): no triangle generated" << std::endl;
-        return false;        
-    }    
-    
+        return false;
+    }
+
     prim_tris_ = new osg::DrawElementsUInt(GL_TRIANGLES, pt_indices.size(), &(pt_indices.front()));
 
     OSG_INFO << "DelaunayTriangulator: process done, " << prim_tris_->getNumPrimitives() << " triangles remain\n";
-    
+
     return true;
 }
@@ -1265 +1265 @@
         }
     }
-    
+
     return theta/osg::PI/2.0; // should be 0 or 2 pi.
 }
 osg::DrawElementsUInt *DelaunayConstraint::makeDrawable()
-{ 
+{
     // initialize index storage vector for internal triangles.
     std::vector<GLuint> pt_indices;
@@ -1276 +1276 @@
     for (ti=_interiorTris.begin(); ti!=_interiorTris.end(); ++ti)
     {
-        
+
         //  if (normals_.valid()) {
         //        (normals_.get())->push_back(ti->compute_normal(points));
         //  }
-        
+
         pt_indices.push_back((*ti)[0]);
         pt_indices.push_back((*ti)[1]);
@@ -1286 +1286 @@
     }
     prim_tris_ = new osg::DrawElementsUInt(GL_TRIANGLES, pt_indices.size(), &(pt_indices.front()));
-    
+
     return prim_tris_.get();
 }
-bool DelaunayConstraint::contains(const osg::Vec3 &testpoint) const 
+bool DelaunayConstraint::contains(const osg::Vec3 &testpoint) const
 {
     // 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).
 }
-bool DelaunayConstraint::outside(const osg::Vec3 &testpoint) const 
+bool DelaunayConstraint::outside(const osg::Vec3 &testpoint) const
 {
     // true if point is outside the loop.
@@ -1365 +1365 @@
     tscx->setTessellationType(osgUtil::Tessellator::TESS_TYPE_GEOMETRY);
     tscx->setBoundaryOnly(true);
-    tscx->setWindingType( osgUtil::Tessellator::TESS_WINDING_ODD); 
+    tscx->setWindingType( osgUtil::Tessellator::TESS_WINDING_ODD);
     //  ODD chooses the winding =1, NOT overlapping areas of constraints.
     // nb this includes all the edges where delaunay constraints meet
     // draw a case to convince yourself!.
-    
+
     tscx->retessellatePolygons(*this); // find all edges
 }