From 09aa6ba330e44a81a00462a4a1ff9cad69e82bb8 Mon Sep 17 00:00:00 2001 From: curt Date: Sat, 27 Mar 1999 05:30:12 +0000 Subject: [PATCH] Handle corner nodes separately from the rest of the fitted nodes. Add fitted nodes in after corners and polygon nodes since the fitted nodes are less important. Subsequent nodes will "snap" to previous nodes if they are "close enough." Need to manually divide segments to prevent "T" intersetions which can confound the triangulator. Hey, I got to use a recursive method! Pass along correct triangle attributes to output file generator. Do fine grained node snapping for corners and polygons, but course grain node snapping for fitted terrain nodes. --- Triangulate/triangle.cxx | 64 ++++++++++++++++---- Triangulate/triangle.hxx | 15 ++++- Triangulate/trieles.hxx | 20 ++++++- Triangulate/trinodes.cxx | 51 ++++++++++++---- Triangulate/trinodes.hxx | 47 +++++++++++++++ Triangulate/trisegs.cxx | 126 +++++++++++++++++++++++++++++++++++++-- Triangulate/trisegs.hxx | 33 +++++++++- 7 files changed, 322 insertions(+), 34 deletions(-) diff --git a/Triangulate/triangle.cxx b/Triangulate/triangle.cxx index b1beaa79f..5aa396721 100644 --- a/Triangulate/triangle.cxx +++ b/Triangulate/triangle.cxx @@ -37,7 +37,8 @@ FGTriangle::~FGTriangle( void ) { // populate this class based on the specified gpc_polys list int -FGTriangle::build( const fitnode_list& fit_list, +FGTriangle::build( const fitnode_list& corner_list, + const fitnode_list& fit_list, const FGgpcPolyList& gpc_polys ) { FGTriPoly poly; @@ -48,18 +49,20 @@ FGTriangle::build( const fitnode_list& fit_list, // char junkn[256]; // FILE *junkfp; - // traverse the dem fit list and gpc_polys building a unified node - // list and converting the polygons so that they reference the - // node list by index (starting at zero) rather than listing the - // points explicitely + // traverse the dem corner and fit lists and gpc_polys building a + // unified node list and converting the polygons so that they + // reference the node list by index (starting at zero) rather than + // listing the points explicitely + // first the corners since these are important const_fitnode_list_iterator f_current, f_last; - f_current = fit_list.begin(); - f_last = fit_list.end(); + f_current = corner_list.begin(); + f_last = corner_list.end(); for ( ; f_current != f_last; ++f_current ) { index = in_nodes.unique_add( *f_current ); } + // next process the polygons gpc_polygon *gpc_poly; const_gpcpoly_iterator current, last; @@ -87,6 +90,8 @@ FGTriangle::build( const fitnode_list& fit_list, } for ( int j = 0; j < gpc_poly->num_contours; j++ ) { + cout << " processing contour, nodes = " + << gpc_poly->contour[j].num_vertices << endl; poly.erase(); @@ -115,6 +120,13 @@ FGTriangle::build( const fitnode_list& fit_list, } } + // last, do the rest of the height nodes + f_current = fit_list.begin(); + f_last = fit_list.end(); + for ( ; f_current != f_last; ++f_current ) { + index = in_nodes.course_add( *f_current ); + } + for ( int i = 0; i < FG_MAX_AREA_TYPES; ++i ) { if ( polylist[i].size() ) { cout << get_area_name((AreaType)i) << " = " @@ -126,6 +138,7 @@ FGTriangle::build( const fitnode_list& fit_list, // that is used by the "Triangle" lib. int i1, i2; + point_list node_list = in_nodes.get_node_list(); for ( int i = 0; i < FG_MAX_AREA_TYPES; ++i ) { cout << "area type = " << i << endl; tripoly_list_iterator tp_current, tp_last; @@ -139,11 +152,13 @@ FGTriangle::build( const fitnode_list& fit_list, for ( int j = 0; j < (int)(poly.size()) - 1; ++j ) { i1 = poly.get_pt_index( j ); i2 = poly.get_pt_index( j + 1 ); - trisegs.unique_add( FGTriSeg(i1, i2) ); + // calc_line_params(i1, i2, &m, &b); + trisegs.unique_divide_and_add( node_list, FGTriSeg(i1, i2) ); } i1 = poly.get_pt_index( 0 ); i2 = poly.get_pt_index( poly.size() - 1 ); - trisegs.unique_add( FGTriSeg(i1, i2) ); + // calc_line_params(i1, i2, &m, &b); + trisegs.unique_divide_and_add( node_list, FGTriSeg(i1, i2) ); } } @@ -197,6 +212,7 @@ static void write_out_data(struct triangulateio *out) { i, out->regionlist[4*i], out->regionlist[4*i + 1], out->regionlist[4*i + 2]); } + fclose(fp); } @@ -312,17 +328,22 @@ int FGTriangle::run_triangulate() { vorout.normlist = (REAL *) NULL; // Needed only if -v switch used. // TEMPORARY - // write_out_data(&in); + write_out_data(&in); // Triangulate the points. Switches are chosen to read and write // a PSLG (p), preserve the convex hull (c), number everything // from zero (z), assign a regional attribute to each element (A), // and produce an edge list (e), and a triangle neighbor list (n). - triangulate("pczq15Aen", &in, &out, &vorout); + string tri_options = "pczq10Aen"; + // string tri_options = "pzAen"; + // string tri_options = "pczq15S400Aen"; + cout << "Triangulation with options = " << tri_options << endl; + + triangulate(tri_options.c_str(), &in, &out, &vorout); // TEMPORARY - write_out_data(&out); + // write_out_data(&out); // now copy the results back into the corresponding FGTriangle // structures @@ -336,13 +357,19 @@ int FGTriangle::run_triangulate() { // triangles int n1, n2, n3; + double attribute; for ( int i = 0; i < out.numberoftriangles; i++ ) { n1 = out.trianglelist[i * 3]; n2 = out.trianglelist[i * 3 + 1]; n3 = out.trianglelist[i * 3 + 2]; + if ( out.numberoftriangleattributes > 0 ) { + attribute = out.triangleattributelist[i]; + } else { + attribute = 0.0; + } // cout << "triangle = " << n1 << " " << n2 << " " << n3 << endl; - elelist.push_back( FGTriEle( n1, n2, n3 ) ); + elelist.push_back( FGTriEle( n1, n2, n3, attribute ) ); } // free mem allocated to the "Triangle" structures @@ -371,6 +398,17 @@ int FGTriangle::run_triangulate() { // $Log$ +// Revision 1.12 1999/03/27 05:30:12 curt +// Handle corner nodes separately from the rest of the fitted nodes. +// Add fitted nodes in after corners and polygon nodes since the fitted nodes +// are less important. Subsequent nodes will "snap" to previous nodes if +// they are "close enough." +// Need to manually divide segments to prevent "T" intersetions which can +// confound the triangulator. Hey, I got to use a recursive method! +// Pass along correct triangle attributes to output file generator. +// Do fine grained node snapping for corners and polygons, but course grain +// node snapping for fitted terrain nodes. +// // Revision 1.11 1999/03/23 22:02:51 curt // Refinements in naming and organization. // diff --git a/Triangulate/triangle.hxx b/Triangulate/triangle.hxx index ba4fb4cbf..8106c3ab3 100644 --- a/Triangulate/triangle.hxx +++ b/Triangulate/triangle.hxx @@ -76,7 +76,9 @@ public: int add_nodes(); // populate this class based on the specified gpc_polys list - int build( const fitnode_list& fit_list, const FGgpcPolyList& gpc_polys ); + int build( const fitnode_list& corner_list, + const fitnode_list& fit_list, + const FGgpcPolyList& gpc_polys ); // front end triangulator for polygon list int run_triangulate(); @@ -90,6 +92,17 @@ public: // $Log$ +// Revision 1.9 1999/03/27 05:30:13 curt +// Handle corner nodes separately from the rest of the fitted nodes. +// Add fitted nodes in after corners and polygon nodes since the fitted nodes +// are less important. Subsequent nodes will "snap" to previous nodes if +// they are "close enough." +// Need to manually divide segments to prevent "T" intersetions which can +// confound the triangulator. Hey, I got to use a recursive method! +// Pass along correct triangle attributes to output file generator. +// Do fine grained node snapping for corners and polygons, but course grain +// node snapping for fitted terrain nodes. +// // Revision 1.8 1999/03/23 22:02:52 curt // Refinements in naming and organization. // diff --git a/Triangulate/trieles.hxx b/Triangulate/trieles.hxx index 8a867fc0e..2d22c7db5 100644 --- a/Triangulate/trieles.hxx +++ b/Triangulate/trieles.hxx @@ -42,11 +42,15 @@ FG_USING_STD(vector); class FGTriEle { int n1, n2, n3; + double attribute; + public: // Constructor and destructor inline FGTriEle( void ) { }; - inline FGTriEle( int i1, int i2, int i3 ) { n1 = i1; n2 = i2; n3 = i3; } + inline FGTriEle( int i1, int i2, int i3, double a ) { + n1 = i1; n2 = i2; n3 = i3; attribute = a; + } inline ~FGTriEle( void ) { }; @@ -56,6 +60,9 @@ public: inline void set_n2( int i ) { n2 = i; } inline int get_n3() const { return n3; } inline void set_n3( int i ) { n3 = i; } + + inline double get_attribute() const { return attribute; } + inline void set_attribute( double a ) { attribute = a; } }; @@ -68,6 +75,17 @@ typedef triele_list::const_iterator const_triele_list_iterator; // $Log$ +// Revision 1.3 1999/03/27 05:30:14 curt +// Handle corner nodes separately from the rest of the fitted nodes. +// Add fitted nodes in after corners and polygon nodes since the fitted nodes +// are less important. Subsequent nodes will "snap" to previous nodes if +// they are "close enough." +// Need to manually divide segments to prevent "T" intersetions which can +// confound the triangulator. Hey, I got to use a recursive method! +// Pass along correct triangle attributes to output file generator. +// Do fine grained node snapping for corners and polygons, but course grain +// node snapping for fitted terrain nodes. +// // Revision 1.2 1999/03/23 22:02:53 curt // Refinements in naming and organization. // diff --git a/Triangulate/trinodes.cxx b/Triangulate/trinodes.cxx index 75b5b302d..50e7df7ee 100644 --- a/Triangulate/trinodes.cxx +++ b/Triangulate/trinodes.cxx @@ -35,18 +35,6 @@ FGTriNodes::~FGTriNodes( void ) { } -// return true of the two points are "close enough" as defined by -// FG_PROXIMITY_EPSILON -inline bool FGTriNodes::close_enough( const Point3D& p1, const Point3D& p2 ) { - if ( ( fabs(p1.x() - p2.x()) < FG_PROXIMITY_EPSILON ) && - ( fabs(p1.y() - p2.y()) < FG_PROXIMITY_EPSILON ) ) { - return true; - } else { - return false; - } -} - - // Add a point to the point list if it doesn't already exist. Returns // the index (starting at zero) of the point in the list. int FGTriNodes::unique_add( const Point3D& p ) { @@ -82,7 +70,46 @@ int FGTriNodes::simple_add( const Point3D& p ) { } +// Add a point to the point list if it doesn't already exist. Returns +// the index (starting at zero) of the point in the list. Use a +// course proximity check +int FGTriNodes::course_add( const Point3D& p ) { + point_list_iterator current, last; + int counter = 0; + + // cout << p.x() << "," << p.y() << endl; + + // see if point already exists + current = node_list.begin(); + last = node_list.end(); + for ( ; current != last; ++current ) { + if ( course_close_enough(p, *current) ) { + // cout << "found an existing match!" << endl; + return counter; + } + + ++counter; + } + + // add to list + node_list.push_back( p ); + + return counter; +} + + // $Log$ +// Revision 1.6 1999/03/27 05:30:15 curt +// Handle corner nodes separately from the rest of the fitted nodes. +// Add fitted nodes in after corners and polygon nodes since the fitted nodes +// are less important. Subsequent nodes will "snap" to previous nodes if +// they are "close enough." +// Need to manually divide segments to prevent "T" intersetions which can +// confound the triangulator. Hey, I got to use a recursive method! +// Pass along correct triangle attributes to output file generator. +// Do fine grained node snapping for corners and polygons, but course grain +// node snapping for fitted terrain nodes. +// // Revision 1.5 1999/03/23 22:02:54 curt // Refinements in naming and organization. // diff --git a/Triangulate/trinodes.hxx b/Triangulate/trinodes.hxx index ab1b36504..860b63034 100644 --- a/Triangulate/trinodes.hxx +++ b/Triangulate/trinodes.hxx @@ -41,6 +41,7 @@ FG_USING_STD(vector); #define FG_PROXIMITY_EPSILON 0.000001 +#define FG_COURSE_EPSILON 0.0003 typedef vector < Point3D > point_list; @@ -58,6 +59,10 @@ private: // FG_PROXIMITY_EPSILON bool close_enough( const Point3D& p, const Point3D& p ); + // return true of the two points are "close enough" as defined by + // FG_COURSE_EPSILON + bool course_close_enough( const Point3D& p1, const Point3D& p2 ); + public: // Constructor and destructor @@ -71,6 +76,11 @@ public: // Add the point with no uniqueness checking int simple_add( const Point3D& p ); + // Add a point to the point list if it doesn't already exist. + // Returns the index (starting at zero) of the point in the list. + // Use a course proximity check + int course_add( const Point3D& p ); + // return the master node list inline point_list get_node_list() const { return node_list; } @@ -79,10 +89,47 @@ public: }; +// return true of the two points are "close enough" as defined by +// FG_PROXIMITY_EPSILON +inline bool FGTriNodes::close_enough( const Point3D& p1, const Point3D& p2 ) { + if ( ( fabs(p1.x() - p2.x()) < FG_PROXIMITY_EPSILON ) && + ( fabs(p1.y() - p2.y()) < FG_PROXIMITY_EPSILON ) ) { + return true; + } else { + return false; + } +} + + +// return true of the two points are "close enough" as defined by +// FG_COURSE_EPSILON +inline bool FGTriNodes::course_close_enough( const Point3D& p1, + const Point3D& p2 ) +{ + if ( ( fabs(p1.x() - p2.x()) < FG_COURSE_EPSILON ) && + ( fabs(p1.y() - p2.y()) < FG_COURSE_EPSILON ) ) { + return true; + } else { + return false; + } +} + + #endif // _TRINODES_HXX // $Log$ +// Revision 1.6 1999/03/27 05:30:16 curt +// Handle corner nodes separately from the rest of the fitted nodes. +// Add fitted nodes in after corners and polygon nodes since the fitted nodes +// are less important. Subsequent nodes will "snap" to previous nodes if +// they are "close enough." +// Need to manually divide segments to prevent "T" intersetions which can +// confound the triangulator. Hey, I got to use a recursive method! +// Pass along correct triangle attributes to output file generator. +// Do fine grained node snapping for corners and polygons, but course grain +// node snapping for fitted terrain nodes. +// // Revision 1.5 1999/03/23 22:02:55 curt // Refinements in naming and organization. // diff --git a/Triangulate/trisegs.cxx b/Triangulate/trisegs.cxx index 6d4ac1bb5..62cf4d03a 100644 --- a/Triangulate/trisegs.cxx +++ b/Triangulate/trisegs.cxx @@ -22,6 +22,10 @@ // (Log is kept at end of this file) +#include +#include + +#include "trinodes.hxx" #include "trisegs.hxx" @@ -35,15 +39,16 @@ FGTriSegments::~FGTriSegments( void ) { } -// Add a point to the point list if it doesn't already exist. -// Returns the index (starting at zero) of the point in the list. -int FGTriSegments::unique_add( const FGTriSeg& s ) { +// Add a segment to the segment list if it doesn't already exist. +// Returns the index (starting at zero) of the segment in the list. +int FGTriSegments::unique_add( const FGTriSeg& s ) +{ triseg_list_iterator current, last; int counter = 0; // cout << s.get_n1() << "," << s.get_n2() << endl; - // see if point already exists + // check if segment already exists current = seg_list.begin(); last = seg_list.end(); for ( ; current != last; ++current ) { @@ -62,7 +67,120 @@ int FGTriSegments::unique_add( const FGTriSeg& s ) { } +// Divide segment if there are other points on it, return the divided +// list of segments +void FGTriSegments::unique_divide_and_add( const point_list& nodes, + const FGTriSeg& s ) +{ + Point3D p0 = nodes[ s.get_n1() ]; + Point3D p1 = nodes[ s.get_n2() ]; + + bool found_extra = false; + int extra_index; + int counter; + double m, b, y_err, x_err; + const_point_list_iterator current, last; + + // bool temp = false; + // if ( s == FGTriSeg( 170, 206 ) ) { + // cout << "this is it!" << endl; + // temp = true; + // } + + if ( fabs(p0.x() - p1.x()) > FG_EPSILON ) { + // use y = mx + b + + // sort these in a sensable order + if ( p0.x() > p1.x() ) { + Point3D tmp = p0; + p0 = p1; + p1 = tmp; + } + + m = (p0.y() - p1.y()) / (p0.x() - p1.x()); + b = p1.y() - m * p1.x(); + + // if ( temp ) { + // cout << "m = " << m << " b = " << b << endl; + // } + + current = nodes.begin(); + last = nodes.end(); + counter = 0; + for ( ; current != last; ++current ) { + if ( (current->x() > (p0.x() + FG_EPSILON)) + && (current->x() < (p1.x() - FG_EPSILON)) ) { + + // if ( temp ) { + // cout << counter << endl; + // } + + y_err = fabs(current->y() - (m * current->x() + b)); + + if ( y_err < 10 * FG_EPSILON ) { + cout << "FOUND EXTRA SEGMENT NODE (Y)" << endl; + cout << p0 << " < " << *current << " < " + << p1 << endl; + found_extra = true; + extra_index = counter; + break; + } + } + ++counter; + } + } else { + // use x = constant + + // sort these in a sensable order + if ( p0.y() > p1.y() ) { + Point3D tmp = p0; + p0 = p1; + p1 = tmp; + } + + current = nodes.begin(); + last = nodes.end(); + counter = 0; + for ( ; current != last; ++current ) { + // cout << counter << endl; + if ( (current->y() > p0.y()) && (current->y() < p1.y()) ) { + x_err = fabs(current->x() - p0.x()); + if ( x_err < 10*FG_EPSILON ) { + cout << "FOUND EXTRA SEGMENT NODE (X)" << endl; + found_extra = true; + extra_index = counter; + break; + } + } + ++counter; + } + } + + if ( found_extra ) { + // recurse with two sub segments + cout << "dividing " << s.get_n1() << " " << extra_index + << " " << s.get_n2() << endl; + unique_divide_and_add( nodes, FGTriSeg( s.get_n1(), extra_index ) ); + unique_divide_and_add( nodes, FGTriSeg( extra_index, s.get_n2() ) ); + } else { + // this segment does not need to be divided, lets add it + unique_add( s ); + } +} + + // $Log$ +// Revision 1.4 1999/03/27 05:30:17 curt +// Handle corner nodes separately from the rest of the fitted nodes. +// Add fitted nodes in after corners and polygon nodes since the fitted nodes +// are less important. Subsequent nodes will "snap" to previous nodes if +// they are "close enough." +// Need to manually divide segments to prevent "T" intersetions which can +// confound the triangulator. Hey, I got to use a recursive method! +// Pass along correct triangle attributes to output file generator. +// Do fine grained node snapping for corners and polygons, but course grain +// node snapping for fitted terrain nodes. +// // Revision 1.3 1999/03/23 22:02:57 curt // Refinements in naming and organization. // diff --git a/Triangulate/trisegs.hxx b/Triangulate/trisegs.hxx index 31189d591..09fd5b921 100644 --- a/Triangulate/trisegs.hxx +++ b/Triangulate/trisegs.hxx @@ -35,6 +35,8 @@ #include +#include "trinodes.hxx" + FG_USING_STD(vector); @@ -46,7 +48,10 @@ public: // Constructor and destructor inline FGTriSeg( void ) { }; - inline FGTriSeg( int i1, int i2 ) { n1 = i1; n2 = i2; } + inline FGTriSeg( int i1, int i2 ) { + n1 = i1; + n2 = i2; + } inline ~FGTriSeg( void ) { }; @@ -77,16 +82,27 @@ private: triseg_list seg_list; + // Divide segment if there are other points on it, return the + // divided list of segments + triseg_list divide_segment( const point_list& nodes, + const FGTriSeg& s ); + public: // Constructor and destructor FGTriSegments( void ); ~FGTriSegments( void ); - // Add a point to the point list if it doesn't already exist. - // Returns the index (starting at zero) of the point in the list. + // Add a segment to the segment list if it doesn't already exist. + // Returns the index (starting at zero) of the segment in the + // list. int unique_add( const FGTriSeg& s ); + // Add a segment to the segment list if it doesn't already exist. + // Returns the index (starting at zero) of the segment in the list. + void unique_divide_and_add( const point_list& node_list, + const FGTriSeg& s ); + // return the master node list inline triseg_list get_seg_list() const { return seg_list; } @@ -99,6 +115,17 @@ public: // $Log$ +// Revision 1.3 1999/03/27 05:30:18 curt +// Handle corner nodes separately from the rest of the fitted nodes. +// Add fitted nodes in after corners and polygon nodes since the fitted nodes +// are less important. Subsequent nodes will "snap" to previous nodes if +// they are "close enough." +// Need to manually divide segments to prevent "T" intersetions which can +// confound the triangulator. Hey, I got to use a recursive method! +// Pass along correct triangle attributes to output file generator. +// Do fine grained node snapping for corners and polygons, but course grain +// node snapping for fitted terrain nodes. +// // Revision 1.2 1999/03/20 20:33:00 curt // First mostly successful tile triangulation works. There's plenty of tweaking // to do, but we are marching in the right direction. -- 2.39.5