kicad-developers team mailing list archive

[Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>]

On 06.07.2015 11:44, jp charras wrote:
> Le 05/07/2015 21:58, Tomasz Wlostowski a écrit :
>> 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
>>
> 
> Thanks, Tom.
> 
> There is no crash, but unfortunately, with many boards the Fracture
> calculation hangs.
> For some boards, the zone filling hangs.
> 
> See for instance the demo board pic_programmer.kicad_pcb:
> both 3d viewer and zone filling hangs.
> This is also the case of the demo "sonde xilinx"
> 
> (the demo board interf_u.kicad_pcb works fine, both in 3D viewer and
> zone filling.)
> 
Hey JP,

Fresh patch in the attachment.  My mistake.

Tom

>From fc1c53508647569668569b04bbda5ecff7718675 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomasz=20W=C5=82ostowski?= <tomasz.wlostowski@xxxxxxx>
Date: Mon, 6 Jul 2015 14:29:23 +0200
Subject: [PATCH] Fixes to SHAPE_POLY_SET slitting/fracturing algo: - Tom's too
 dumb to use C++ iterators (so he uses pointers now ;) - Some speed
 optimization

---
 3d-viewer/3d_draw_board_body.cpp   |   3 +-
 common/geometry/shape_poly_set.cpp | 149 +++++++++++++++----------------------
 include/geometry/shape_poly_set.h  |   3 +-
 3 files changed, 63 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..4f4762f 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;
-
-        bool connFlag = (*e_nearest)->m_connected;
+        int count = 0;
 
-        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,37 @@ void SHAPE_POLY_SET::fractureSingle( ClipperLib::Paths& paths )
             prev = fe;
             edges.push_back ( fe );
 
+            if(!first)
+            {
+                if( fe->m_p1.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 = (*i)->m_p1.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