kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #35693
Polygon Shape Question
Hi Devs-
I was looking over https://bugs.launchpad.net/bugs/1768862 as it relates
to the PNS checks.
We add custom pad shapes to the PNS obstacle index using a convex hull.
However, there doesn't seem to be a specific restriction that would break
if we allowed concave polygons. I think that the correct restriction is
that the polygon be simple. Collision code doesn't change because we
collide based on the line chain, which is the same restriction for convex
and concave.
Note that this doesn't change how we run the full DRC, generate gerbers or
other aspects outside of PNS.
Am I missing anything? The proposed patch (attached here) renames the
SHAPE_CONVEX class to SHAPE_SIMPLE and adjusts how the vertices are added
for custom pads. Do people see any issues with this?
Thanks-
Seth
From 69140b743b9f6e7ce5fa9a94d24a39c0f0898b2b Mon Sep 17 00:00:00 2001
From: Seth Hillbrand <hillbrand@xxxxxxxxxxx>
Date: Thu, 3 May 2018 10:52:42 -0700
Subject: [PATCH] Setting custom pad shape to be outline for PNS
Changes SHAPE_CONVEX to SHAPE_SIMPLE to better reflect the limitations.
Fixes: lp:1768862
* https://bugs.launchpad.net/kicad/+bug/1768862
---
common/geometry/shape_collisions.cpp | 42 +++++++++++-----------
include/geometry/shape.h | 2 +-
.../geometry/{shape_convex.h => shape_simple.h} | 26 +++++++-------
pcbnew/router/pns_kicad_iface.cpp | 26 ++++++--------
pcbnew/router/pns_logger.cpp | 6 ++--
pcbnew/router/pns_optimizer.cpp | 8 ++---
pcbnew/router/pns_solid.cpp | 8 ++---
pcbnew/router/pns_utils.cpp | 2 +-
pcbnew/router/pns_utils.h | 4 +--
pcbnew/router/router_preview_item.cpp | 7 ++--
10 files changed, 63 insertions(+), 68 deletions(-)
rename include/geometry/{shape_convex.h => shape_simple.h} (89%)
diff --git a/common/geometry/shape_collisions.cpp b/common/geometry/shape_collisions.cpp
index b67c409a7..c614dc97d 100644
--- a/common/geometry/shape_collisions.cpp
+++ b/common/geometry/shape_collisions.cpp
@@ -30,7 +30,7 @@
#include <geometry/shape_circle.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_segment.h>
-#include <geometry/shape_convex.h>
+#include "../../include/geometry/shape_simple.h"
typedef VECTOR2I::extended_type ecoord;
@@ -178,7 +178,7 @@ static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_LINE_CHAIN& aB,
}
-static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_CONVEX& aB, int aClearance,
+static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_SIMPLE& aB, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
bool found;
@@ -228,14 +228,14 @@ static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_LINE_CHAIN&
}
-static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_CONVEX& aB, int aClearance,
+static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_SIMPLE& aB, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
return Collide( aA, aB.Vertices(), aClearance, aNeedMTV, aMTV );
}
-static inline bool Collide( const SHAPE_CONVEX& aA, const SHAPE_CONVEX& aB, int aClearance,
+static inline bool Collide( const SHAPE_SIMPLE& aA, const SHAPE_SIMPLE& aB, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
return Collide( aA.Vertices(), aB.Vertices(), aClearance, aNeedMTV, aMTV );
@@ -257,7 +257,7 @@ static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_LINE_CHAIN& aB, in
}
-static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_CONVEX& aB, int aClearance,
+static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_SIMPLE& aB, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
return Collide( aA, aB.Vertices(), aClearance, aNeedMTV, aMTV );
@@ -288,7 +288,7 @@ static inline bool Collide( const SHAPE_LINE_CHAIN& aA, const SHAPE_SEGMENT& aB,
}
-static inline bool Collide( const SHAPE_CONVEX& aA, const SHAPE_SEGMENT& aB, int aClearance,
+static inline bool Collide( const SHAPE_SIMPLE& aA, const SHAPE_SEGMENT& aB, int aClearance,
bool aNeedMTV, VECTOR2I& aMTV )
{
return Collide( aA.Vertices(), aB, aClearance, aNeedMTV, aMTV );
@@ -340,8 +340,8 @@ bool CollideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeed
case SH_SEGMENT:
return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
- case SH_CONVEX:
- return CollCase<SHAPE_RECT, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+ case SH_SIMPLE:
+ return CollCase<SHAPE_RECT, SHAPE_SIMPLE>( aA, aB, aClearance, aNeedMTV, aMTV );
default:
break;
@@ -363,8 +363,8 @@ bool CollideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeed
case SH_SEGMENT:
return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
- case SH_CONVEX:
- return CollCase<SHAPE_CIRCLE, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+ case SH_SIMPLE:
+ return CollCase<SHAPE_CIRCLE, SHAPE_SIMPLE>( aA, aB, aClearance, aNeedMTV, aMTV );
default:
break;
@@ -386,8 +386,8 @@ bool CollideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeed
case SH_SEGMENT:
return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
- case SH_CONVEX:
- return CollCase<SHAPE_LINE_CHAIN, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+ case SH_SIMPLE:
+ return CollCase<SHAPE_LINE_CHAIN, SHAPE_SIMPLE>( aA, aB, aClearance, aNeedMTV, aMTV );
default:
break;
@@ -409,31 +409,31 @@ bool CollideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, bool aNeed
case SH_SEGMENT:
return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
- case SH_CONVEX:
- return CollCase<SHAPE_CONVEX, SHAPE_SEGMENT>( aB, aA, aClearance, aNeedMTV, aMTV );
+ case SH_SIMPLE:
+ return CollCase<SHAPE_SIMPLE, SHAPE_SEGMENT>( aB, aA, aClearance, aNeedMTV, aMTV );
default:
break;
}
break;
- case SH_CONVEX:
+ case SH_SIMPLE:
switch( aB->Type() )
{
case SH_RECT:
- return CollCase<SHAPE_RECT, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+ return CollCase<SHAPE_RECT, SHAPE_SIMPLE>( aB, aA, aClearance, aNeedMTV, aMTV );
case SH_CIRCLE:
- return CollCase<SHAPE_CIRCLE, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+ return CollCase<SHAPE_CIRCLE, SHAPE_SIMPLE>( aB, aA, aClearance, aNeedMTV, aMTV );
case SH_LINE_CHAIN:
- return CollCase<SHAPE_LINE_CHAIN, SHAPE_CONVEX>( aB, aA, aClearance, aNeedMTV, aMTV );
+ return CollCase<SHAPE_LINE_CHAIN, SHAPE_SIMPLE>( aB, aA, aClearance, aNeedMTV, aMTV );
case SH_SEGMENT:
- return CollCase<SHAPE_CONVEX, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
+ return CollCase<SHAPE_SIMPLE, SHAPE_SEGMENT>( aA, aB, aClearance, aNeedMTV, aMTV );
- case SH_CONVEX:
- return CollCase<SHAPE_CONVEX, SHAPE_CONVEX>( aA, aB, aClearance, aNeedMTV, aMTV );
+ case SH_SIMPLE:
+ return CollCase<SHAPE_SIMPLE, SHAPE_SIMPLE>( aA, aB, aClearance, aNeedMTV, aMTV );
default:
break;
diff --git a/include/geometry/shape.h b/include/geometry/shape.h
index dfbc0c231..1b982ae5d 100644
--- a/include/geometry/shape.h
+++ b/include/geometry/shape.h
@@ -44,7 +44,7 @@ enum SHAPE_TYPE
SH_SEGMENT, ///> line segment
SH_LINE_CHAIN, ///> line chain (polyline)
SH_CIRCLE, ///> circle
- SH_CONVEX, ///> convex polygon
+ SH_SIMPLE, ///> simple polygon
SH_POLY_SET, ///> set of polygons (with holes, etc.)
SH_COMPOUND, ///> compound shape, consisting of multiple simple shapes
SH_ARC ///> circular arc
diff --git a/include/geometry/shape_convex.h b/include/geometry/shape_simple.h
similarity index 89%
rename from include/geometry/shape_convex.h
rename to include/geometry/shape_simple.h
index 104c3ef1f..3d735809f 100644
--- a/include/geometry/shape_convex.h
+++ b/include/geometry/shape_simple.h
@@ -21,8 +21,8 @@
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*/
-#ifndef __SHAPE_CONVEX_H
-#define __SHAPE_CONVEX_H
+#ifndef __SHAPE_SIMPLE_H
+#define __SHAPE_SIMPLE_H
#include <vector>
@@ -31,34 +31,34 @@
#include <geometry/shape_line_chain.h>
/**
- * Class SHAPE_CONVEX
+ * Class SHAPE_SIMPLE
*
- * Represents a convex polygon consisting of a zero-thickness closed chain of
+ * Represents a simple polygon consisting of a zero-thickness closed chain of
* connected line segments.
*
* Internally the vertices are held in a SHAPE_LINE_CHAIN, please note that
* there is a "virtual" line segment between the last and first vertex.
*/
-class SHAPE_CONVEX : public SHAPE
+class SHAPE_SIMPLE : public SHAPE
{
public:
/**
* Constructor
* Creates an empty polygon
*/
- SHAPE_CONVEX() :
- SHAPE( SH_CONVEX )
+ SHAPE_SIMPLE() :
+ SHAPE( SH_SIMPLE )
{
m_points.SetClosed( true );
}
- SHAPE_CONVEX( const SHAPE_CONVEX& aOther ) :
- SHAPE( SH_CONVEX ), m_points( aOther.m_points )
+ SHAPE_SIMPLE( const SHAPE_SIMPLE& aOther ) :
+ SHAPE( SH_SIMPLE ), m_points( aOther.m_points )
{}
SHAPE* Clone() const override
{
- return new SHAPE_CONVEX( *this );
+ return new SHAPE_SIMPLE( *this );
}
/**
@@ -132,9 +132,9 @@ public:
/**
* Function Vertices()
*
- * Returns the list of vertices defining this convex polygon.
+ * Returns the list of vertices defining this simple polygon.
*
- * @return the list of vertices defining this convex polygon
+ * @return the list of vertices defining this simple polygon
*/
const SHAPE_LINE_CHAIN& Vertices() const
{
@@ -186,4 +186,4 @@ private:
SHAPE_LINE_CHAIN m_points;
};
-#endif // __SHAPE_CONVEX_H
+#endif // __SHAPE_SIMPLE_H
diff --git a/pcbnew/router/pns_kicad_iface.cpp b/pcbnew/router/pns_kicad_iface.cpp
index 5a5f9a0c4..78e999534 100644
--- a/pcbnew/router/pns_kicad_iface.cpp
+++ b/pcbnew/router/pns_kicad_iface.cpp
@@ -42,13 +42,14 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_circle.h>
-#include <geometry/shape_convex.h>
#include <geometry/shape_arc.h>
#include <geometry/convex_hull.h>
#include "tools/pcb_tool.h"
#include "pns_kicad_iface.h"
+
+#include "../../include/geometry/shape_simple.h"
#include "pns_routing_settings.h"
#include "pns_sizes_settings.h"
#include "pns_item.h"
@@ -575,15 +576,10 @@ std::unique_ptr<PNS::SOLID> PNS_KICAD_IFACE::syncPad( D_PAD* aPad )
outline.Append( aPad->GetCustomShapeAsPolygon() );
aPad->CustomShapeAsPolygonToBoardPosition( &outline, wx_c, aPad->GetOrientation() );
- SHAPE_CONVEX* shape = new SHAPE_CONVEX();
-
- // We use the convex hull of the pad shape, because PnS knows
- // only convex shapes.
- std::vector<wxPoint> convex_hull;
- BuildConvexHull( convex_hull, outline );
+ SHAPE_SIMPLE* shape = new SHAPE_SIMPLE();
- for( unsigned ii = 0; ii < convex_hull.size(); ii++ )
- shape->Append( convex_hull[ii] );
+ for( auto iter = outline.CIterate( 0 ); iter; iter++ )
+ shape->Append( *iter );
solid->SetShape( shape );
}
@@ -622,7 +618,7 @@ std::unique_ptr<PNS::SOLID> PNS_KICAD_IFACE::syncPad( D_PAD* aPad )
{
wxPoint coords[4];
aPad->BuildPadPolygon( coords, wxSize( 0, 0 ), aPad->GetOrientation() );
- SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+ SHAPE_SIMPLE* shape = new SHAPE_SIMPLE();
for( int ii = 0; ii < 4; ii++ )
{
@@ -642,7 +638,7 @@ std::unique_ptr<PNS::SOLID> PNS_KICAD_IFACE::syncPad( D_PAD* aPad )
// TransformRoundRectToPolygon creates only one convex polygon
SHAPE_LINE_CHAIN& poly = outline.Outline( 0 );
- SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+ SHAPE_SIMPLE* shape = new SHAPE_SIMPLE();
for( int ii = 0; ii < poly.PointCount(); ++ii )
{
@@ -673,7 +669,7 @@ std::unique_ptr<PNS::SOLID> PNS_KICAD_IFACE::syncPad( D_PAD* aPad )
wxPoint end;
wxPoint corner;
- SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+ SHAPE_SIMPLE* shape = new SHAPE_SIMPLE();
int w = aPad->BuildSegmentFromOvalShape( start, end, 0.0, wxSize( 0, 0 ) );
@@ -719,7 +715,7 @@ std::unique_ptr<PNS::SOLID> PNS_KICAD_IFACE::syncPad( D_PAD* aPad )
wxPoint coords[4];
aPad->BuildPadPolygon( coords, wxSize( 0, 0 ), aPad->GetOrientation() );
- SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+ SHAPE_SIMPLE* shape = new SHAPE_SIMPLE();
for( int ii = 0; ii < 4; ii++ )
{
shape->Append( wx_c + coords[ii] );
@@ -738,7 +734,7 @@ std::unique_ptr<PNS::SOLID> PNS_KICAD_IFACE::syncPad( D_PAD* aPad )
// TransformRoundRectToPolygon creates only one convex polygon
SHAPE_LINE_CHAIN& poly = outline.Outline( 0 );
- SHAPE_CONVEX* shape = new SHAPE_CONVEX();
+ SHAPE_SIMPLE* shape = new SHAPE_SIMPLE();
for( int ii = 0; ii < poly.PointCount(); ++ii )
{
@@ -837,7 +833,7 @@ bool PNS_KICAD_IFACE::syncZone( PNS::NODE* aWorld, ZONE_CONTAINER* aZone )
{
VECTOR2I a, b, c;
tri->GetTriangle( i, a, b, c );
- auto triShape = new SHAPE_CONVEX;
+ auto triShape = new SHAPE_SIMPLE;
triShape->Append( a );
triShape->Append( b );
diff --git a/pcbnew/router/pns_logger.cpp b/pcbnew/router/pns_logger.cpp
index 39611c8f4..de95fe700 100644
--- a/pcbnew/router/pns_logger.cpp
+++ b/pcbnew/router/pns_logger.cpp
@@ -30,7 +30,7 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_circle.h>
-#include <geometry/shape_convex.h>
+#include "../../include/geometry/shape_simple.h"
namespace PNS {
@@ -177,9 +177,9 @@ void LOGGER::dumpShape( const SHAPE* aSh )
break;
}
- case SH_CONVEX:
+ case SH_SIMPLE:
{
- const SHAPE_CONVEX* c = (const SHAPE_CONVEX*) aSh;
+ const SHAPE_SIMPLE* c = (const SHAPE_SIMPLE*) aSh;
m_theLog << "convex " << c->PointCount() << " ";
for( int i = 0; i < c->PointCount(); i++ )
diff --git a/pcbnew/router/pns_optimizer.cpp b/pcbnew/router/pns_optimizer.cpp
index d9b969ad6..f6881a510 100644
--- a/pcbnew/router/pns_optimizer.cpp
+++ b/pcbnew/router/pns_optimizer.cpp
@@ -21,8 +21,6 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
-#include <geometry/shape_convex.h>
-
#include <cmath>
#include "pns_line.h"
@@ -30,6 +28,8 @@
#include "pns_node.h"
#include "pns_solid.h"
#include "pns_optimizer.h"
+
+#include "../../include/geometry/shape_simple.h"
#include "pns_utils.h"
#include "pns_router.h"
@@ -669,7 +669,7 @@ OPTIMIZER::BREAKOUT_LIST OPTIMIZER::convexBreakouts( int aWidth,
const SHAPE* aShape, bool aPermitDiagonal ) const
{
BREAKOUT_LIST breakouts;
- const SHAPE_CONVEX* convex = static_cast<const SHAPE_CONVEX*>( aShape );
+ const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aShape );
BOX2I bbox = convex->BBox( 0 );
VECTOR2I p0 = bbox.Centre();
@@ -791,7 +791,7 @@ OPTIMIZER::BREAKOUT_LIST OPTIMIZER::computeBreakouts( int aWidth,
case SH_CIRCLE:
return circleBreakouts( aWidth, shape, aPermitDiagonal );
- case SH_CONVEX:
+ case SH_SIMPLE:
return convexBreakouts( aWidth, shape, aPermitDiagonal );
default:
diff --git a/pcbnew/router/pns_solid.cpp b/pcbnew/router/pns_solid.cpp
index 20b6d0fba..c7e6ae6bd 100644
--- a/pcbnew/router/pns_solid.cpp
+++ b/pcbnew/router/pns_solid.cpp
@@ -25,9 +25,9 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_circle.h>
-#include <geometry/shape_convex.h>
-
#include "pns_solid.h"
+
+#include "../../include/geometry/shape_simple.h"
#include "pns_utils.h"
namespace PNS {
@@ -58,9 +58,9 @@ const SHAPE_LINE_CHAIN SOLID::Hull( int aClearance, int aWalkaroundThickness ) c
return SegmentHull( *seg, aClearance, aWalkaroundThickness );
}
- case SH_CONVEX:
+ case SH_SIMPLE:
{
- SHAPE_CONVEX* convex = static_cast<SHAPE_CONVEX*>( m_shape );
+ SHAPE_SIMPLE* convex = static_cast<SHAPE_SIMPLE*>( m_shape );
return ConvexHull( *convex, cl );
}
diff --git a/pcbnew/router/pns_utils.cpp b/pcbnew/router/pns_utils.cpp
index 84d4ec944..55d20161f 100644
--- a/pcbnew/router/pns_utils.cpp
+++ b/pcbnew/router/pns_utils.cpp
@@ -98,7 +98,7 @@ static void MoveDiagonal( SEG& aDiagonal, const SHAPE_LINE_CHAIN& aVertices, int
}
-const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_CONVEX& aConvex, int aClearance )
+const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_SIMPLE& aConvex, int aClearance )
{
// this defines the horizontal and vertical lines in the hull octagon
BOX2I box = aConvex.BBox( aClearance + HULL_MARGIN );
diff --git a/pcbnew/router/pns_utils.h b/pcbnew/router/pns_utils.h
index cc1f1bbaf..d0244283e 100644
--- a/pcbnew/router/pns_utils.h
+++ b/pcbnew/router/pns_utils.h
@@ -27,7 +27,7 @@
#include <geometry/shape_line_chain.h>
#include <geometry/shape_segment.h>
#include <geometry/shape_rect.h>
-#include <geometry/shape_convex.h>
+#include "../../include/geometry/shape_simple.h"
namespace PNS {
@@ -52,7 +52,7 @@ const SHAPE_LINE_CHAIN SegmentHull( const SHAPE_SEGMENT& aSeg, int aClearance,
* @param aClearance The minimum distance between polygon and hull.
* @return A closed line chain describing the octagon.
*/
-const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_CONVEX& aConvex, int aClearance );
+const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_SIMPLE& aConvex, int aClearance );
SHAPE_RECT ApproximateSegmentAsRect( const SHAPE_SEGMENT& aSeg );
diff --git a/pcbnew/router/router_preview_item.cpp b/pcbnew/router/router_preview_item.cpp
index 0194019c6..b1ba85523 100644
--- a/pcbnew/router/router_preview_item.cpp
+++ b/pcbnew/router/router_preview_item.cpp
@@ -24,13 +24,12 @@
#include <view/view.h>
#include <geometry/shape_rect.h>
-#include <geometry/shape_convex.h>
-
#include "class_track.h"
#include <pcb_painter.h>
#include "router_preview_item.h"
+#include "../../include/geometry/shape_simple.h"
#include "pns_line.h"
#include "pns_segment.h"
#include "pns_via.h"
@@ -245,9 +244,9 @@ void ROUTER_PREVIEW_ITEM::ViewDraw( int aLayer, KIGFX::VIEW* aView ) const
break;
}
- case SH_CONVEX:
+ case SH_SIMPLE:
{
- const SHAPE_CONVEX* c = (const SHAPE_CONVEX*) m_shape;
+ const SHAPE_SIMPLE* c = (const SHAPE_SIMPLE*) m_shape;
std::deque<VECTOR2D> polygon = std::deque<VECTOR2D>();
for( int i = 0; i < c->PointCount(); i++ )
{
--
2.11.0
Follow ups
