kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #19161
Re: Segmentation fault when using Clipper and SHAPE_POLY_SET in 3D viewer. Need help.
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.wlostowski@xxxxxxx>
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
Follow ups
References
