On 04.07.2015 23:08, Tomasz Wlostowski wrote: > On 04.07.2015 22:10, jp charras wrote: >> Tomasz, Orson, >> >> May I ask you to have a look at the calculations in >> 3d_draw_board_body.cpp, lines 377 to 392 > Hi,
Please test the attached patch. Tom
>From eabc846e51b23d2f03d6f5a1ba748a6d310f94bc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Tomasz=20W=C5=82ostowski?= <tomasz.wlostow...@cern.ch> Date: Sun, 5 Jul 2015 21:58:01 +0200 Subject: [PATCH] SHAPE_POLY_SET: Fixed crash in 3d-viewer (Tom's too dumb to use C++ iterators). Also improved the speed of slitting algorithm --- 3d-viewer/3d_draw_board_body.cpp | 3 +- common/geometry/shape_poly_set.cpp | 150 +++++++++++++++---------------------- include/geometry/shape_poly_set.h | 3 +- 3 files changed, 64 insertions(+), 92 deletions(-) diff --git a/3d-viewer/3d_draw_board_body.cpp b/3d-viewer/3d_draw_board_body.cpp index 3860a4c..c5511f1 100644 --- a/3d-viewer/3d_draw_board_body.cpp +++ b/3d-viewer/3d_draw_board_body.cpp @@ -354,7 +354,8 @@ void EDA_3D_CANVAS::buildBoard3DView( GLuint aBoardList, GLuint aBodyOnlyList, if( bufferPolys.GetCornersCount() == 0 ) continue; -#if 1 // Set to 1 to use boost::polygon to subtract holes to copper areas +#if 0 + // Set to 1 to use boost::polygon to subtract holes to copper areas // (due to bugs in boost::polygon, this is deprecated and Clipper is used instead KI_POLYGON_SET currLayerPolyset; KI_POLYGON_SET polysetHoles; diff --git a/common/geometry/shape_poly_set.cpp b/common/geometry/shape_poly_set.cpp index 04c89d7..f68b94c 100644 --- a/common/geometry/shape_poly_set.cpp +++ b/common/geometry/shape_poly_set.cpp @@ -237,7 +237,6 @@ struct FractureEdge { FractureEdge(bool connected, Path* owner, int index) : m_connected(connected), - m_owner(owner), m_next(NULL) { m_p1 = (*owner)[index]; @@ -246,7 +245,6 @@ struct FractureEdge FractureEdge(int64_t y = 0) : m_connected(false), - m_owner(NULL), m_next(NULL) { m_p1.Y = m_p2.Y = y; @@ -254,7 +252,6 @@ struct FractureEdge FractureEdge(bool connected, const IntPoint& p1, const IntPoint& p2) : m_connected(connected), - m_owner(NULL), m_p1(p1), m_p2(p2), m_next(NULL) @@ -271,117 +268,76 @@ struct FractureEdge } bool m_connected; - Path* m_owner; IntPoint m_p1, m_p2; FractureEdge *m_next; }; -struct CompareEdges -{ - bool operator()(const FractureEdge *a, const FractureEdge *b) const - { - if( std::min(a->m_p1.Y, a->m_p2.Y) < std::min(b->m_p1.Y, b->m_p2.Y) ) - return true; - return false; - } -}; -typedef std::vector<FractureEdge*> FractureEdgeSet; +typedef std::vector<FractureEdge *> FractureEdgeSet; static int processEdge ( FractureEdgeSet& edges, FractureEdge* edge ) { - int n = 0; int64_t x = edge->m_p1.X; int64_t y = edge->m_p1.Y; + int64_t min_dist = std::numeric_limits<int64_t>::max(); + int64_t x_nearest = 0; + FractureEdge* e_nearest = NULL; - int64_t min_dist_l = std::numeric_limits<int64_t>::max(); - int64_t min_dist_r = std::numeric_limits<int64_t>::max(); - int64_t x_nearest_l = 0, x_nearest_r = 0, x_nearest; + for(FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i) + { + if( ! (*i)->matches(y) ) + continue; - // fixme: search edges in sorted multiset - // FractureEdge comp_min( std::min(edge->m_p1.Y, edge->m_p2.Y) ); - // FractureEdgeSet::iterator e_begin = edges.lower_bound ( &comp_min ); + int64_t x_intersect; - FractureEdgeSet::iterator e_nearest_l = edges.end(), e_nearest_r = edges.end(), e_nearest; + if( (*i)->m_p1.Y == (*i)->m_p2.Y ) // horizontal edge + x_intersect = std::max ( (*i)->m_p1.X, (*i)->m_p2.X ); + else + x_intersect = (*i)->m_p1.X + rescale((*i)->m_p2.X - (*i)->m_p1.X, y - (*i)->m_p1.Y, (*i)->m_p2.Y - (*i)->m_p1.Y ); + int64_t dist = (x - x_intersect); - for(FractureEdgeSet::iterator i = edges.begin() ; i != edges.end(); ++i) - { - n++; - if( (*i)->matches(y) ) + if(dist > 0 && dist < min_dist) { - int64_t x_intersect; - if( (*i)->m_p1.Y == (*i)->m_p2.Y ) // horizontal edge - x_intersect = std::max ( (*i)->m_p1.X, (*i)->m_p2.X ); - else - x_intersect = (*i)->m_p1.X + rescale((*i)->m_p2.X - (*i)->m_p1.X, y - (*i)->m_p1.Y, (*i)->m_p2.Y - (*i)->m_p1.Y ); - - int64_t dist = (x - x_intersect); - - if(dist > 0 && dist < min_dist_l) - { - min_dist_l = dist; - x_nearest_l = x_intersect; - e_nearest_l = i; - } - - if(dist <= 0 && (-dist) < min_dist_r) - { - min_dist_r = -dist; - x_nearest_r = x_intersect; - e_nearest_r = i; - } + min_dist = dist; + x_nearest = x_intersect; + e_nearest = (*i); } } - if(e_nearest_l != edges.end() || e_nearest_r != edges.end()) + if(e_nearest && e_nearest->m_connected ) { - if( e_nearest_l !=edges.end() && ( (*e_nearest_l)->m_connected || ((*e_nearest_l) ->m_owner != edge->m_owner ))) - { - e_nearest = e_nearest_l; - x_nearest = x_nearest_l; - } - else if( e_nearest_r !=edges.end() && ( (*e_nearest_r)->m_connected || ((*e_nearest_r) ->m_owner != edge->m_owner ) )) { - e_nearest = e_nearest_r; - x_nearest = x_nearest_r; - } - else - return 0; + int count = 0; - bool connFlag = (*e_nearest)->m_connected; - - FractureEdge split_1 ( connFlag, (*e_nearest)->m_p1, IntPoint(x_nearest, y) ); - FractureEdge *lead1 = new FractureEdge( connFlag, IntPoint(x_nearest, y), IntPoint(x, y) ); - FractureEdge *lead2 = new FractureEdge( connFlag, IntPoint(x, y), IntPoint(x_nearest, y) ); - FractureEdge *split_2 = new FractureEdge ( connFlag, IntPoint(x_nearest, y), (*e_nearest)->m_p2 ); + FractureEdge *lead1 = new FractureEdge( true, IntPoint(x_nearest, y), IntPoint(x, y) ); + FractureEdge *lead2 = new FractureEdge( true, IntPoint(x, y), IntPoint(x_nearest, y) ); + FractureEdge *split_2 = new FractureEdge ( true, IntPoint(x_nearest, y), e_nearest->m_p2 ); edges.push_back(split_2); edges.push_back(lead1); edges.push_back(lead2); - FractureEdge* link = (*e_nearest)->m_next; + FractureEdge* link = e_nearest->m_next; - (*e_nearest)->m_p1 = split_1.m_p1; - (*e_nearest)->m_p2 = IntPoint(x_nearest, y); - (*e_nearest)->m_connected = connFlag; - (*e_nearest)->m_next = lead1; + e_nearest->m_p2 = IntPoint(x_nearest, y); + e_nearest->m_next = lead1; lead1->m_next = edge; + FractureEdge *last; for(last = edge; last->m_next != edge; last = last->m_next) { - last->m_connected = connFlag; - last->m_owner = NULL; + last->m_connected = true; + count++; } - last->m_owner = NULL; - last->m_connected = connFlag; + last->m_connected = true; last->m_next = lead2; lead2->m_next = split_2; split_2->m_next = link; - return 1; + return count + 1; } return 0; @@ -390,6 +346,7 @@ static int processEdge ( FractureEdgeSet& edges, FractureEdge* edge ) void SHAPE_POLY_SET::fractureSingle( ClipperLib::Paths& paths ) { FractureEdgeSet edges; + FractureEdgeSet border_edges; FractureEdge *root = NULL; bool first = true; @@ -404,6 +361,15 @@ void SHAPE_POLY_SET::fractureSingle( ClipperLib::Paths& paths ) int index = 0; FractureEdge *prev = NULL, *first_edge = NULL; + + int64_t x_min = std::numeric_limits<int64_t>::max(); + + for(unsigned i = 0; i < path.size(); i++) + { + if( path[i].X < x_min ) + x_min = path[i].X; + } + for(unsigned i = 0; i < path.size(); i++) { FractureEdge *fe = new FractureEdge ( first, &path, index++ ); @@ -422,34 +388,38 @@ void SHAPE_POLY_SET::fractureSingle( ClipperLib::Paths& paths ) prev = fe; edges.push_back ( fe ); + if(!first) + { + if(fe->m_p1.X == x_min || fe->m_p2.X == x_min) + border_edges.push_back(fe); + + } + if(!fe->m_connected) num_unconnected++; } - first = false; // first path is always the outline } - while(1) + // keep connecting holes to the main outline, until there's no holes left... + while(num_unconnected > 0) { - int n_unconnected = 0; + int64_t x_min = std::numeric_limits<int64_t>::max(); - for(FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i ) - { - if(!(*i)->m_connected) - n_unconnected++; - } + FractureEdge *smallestX; - if(!n_unconnected) - break; - - for(FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i ) + // find the left-most hole edge and merge with the outline + for(FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i ) { - if(!(*i)->m_connected) + int64_t xt = std::min((*i)->m_p1.X, (*i)->m_p2.X); + if( (xt < x_min) && ! (*i)->m_connected ) { - if (processEdge ( edges, *i ) ) - break; + x_min = xt; + smallestX = *i; } } + + num_unconnected -= processEdge ( edges, smallestX ); } paths.clear(); diff --git a/include/geometry/shape_poly_set.h b/include/geometry/shape_poly_set.h index 4988752..63fe903 100644 --- a/include/geometry/shape_poly_set.h +++ b/include/geometry/shape_poly_set.h @@ -91,7 +91,7 @@ class SHAPE_POLY_SET : public SHAPE ///> Performs outline erosion/shrinking void Erode ( int aFactor ); - ///> Converts a set of polygons with holes to a singe outline with 'slits'/'fractures' connecting the outer ring + ///> Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the outer ring ///> to the inner holes void Fracture (); @@ -113,6 +113,7 @@ class SHAPE_POLY_SET : public SHAPE const BOX2I BBox( int aClearance = 0 ) const; + // fixme: add collision support bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const { return false; } bool Collide( const SEG& aSeg, int aClearance = 0 ) const { return false; } -- 1.9.1
_______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp