Hi Wayne,
In my testing there is no performance impact, but more testing is welcome.
It shouldn't be doing the calculation on too many objects in general, since
this is a "second pass" hit test that applies to modules that have a
bounding box overlapping the mouse cursor.
However, I did some more testing and discovered some weird behavior, so I
have tweaked the algorithm in the attached new version of the patch.
-Jon
On Sun, Feb 18, 2018 at 5:25 PM, Wayne Stambaugh <stambau...@gmail.com>
wrote:
> Hey Jon,
>
> Did you notice an performance hit with your patch? Obviously there is
> going to be more overhead calculating a polygon versus a rectangle. I just
> want to be sure we are not causing any usability issues due to the polygon
> calculations.
>
> Thanks,
>
> Wayne
>
>
> On 02/18/2018 12:10 PM, Jon Evans wrote:
>
>> Hi all,
>>
>> The attached patch adds some plumbing to calculate and make use of a
>> polygonal bounding area for modules. It fixes the below issue and in
>> general improves the accuracy of selection in my testing.
>>
>> This mechanism could be extended to other objects besides modules if it's
>> useful. I figured I'd start by sending out this patch to get feedback, and
>> if it gets merged, look for other areas where we could improve things by
>> using polygons instead of bounding boxes.
>>
>> https://bugs.launchpad.net/kicad/+bug/1749077
>>
>> -Jon
>>
>>
>> _______________________________________________
>> 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
>>
>>
> _______________________________________________
> 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
>
From caf208e46f5a0a78ce6c1da5a13882f28096f941 Mon Sep 17 00:00:00 2001
From: Jon Evans <j...@craftyjon.com>
Date: Sun, 18 Feb 2018 19:00:29 -0500
Subject: [PATCH] Use polygonal hit testing for module selection
---
common/geometry/shape_poly_set.cpp | 25 ++++++++++++----------
include/geometry/shape_poly_set.h | 15 +++++++++----
pcbnew/board_items_to_polygon_shape_transform.cpp | 13 ++++++++----
pcbnew/class_module.cpp | 26 +++++++++++++++++++++++
pcbnew/class_module.h | 24 ++++++++++++++++++---
pcbnew/collectors.cpp | 3 ++-
6 files changed, 83 insertions(+), 23 deletions(-)
diff --git a/common/geometry/shape_poly_set.cpp b/common/geometry/shape_poly_set.cpp
index c2821ff0b..49e3a66ed 100644
--- a/common/geometry/shape_poly_set.cpp
+++ b/common/geometry/shape_poly_set.cpp
@@ -1402,19 +1402,19 @@ bool SHAPE_POLY_SET::CollideEdge( const VECTOR2I& aPoint,
}
-bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex ) const
+bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
{
if( m_polys.size() == 0 ) // empty set?
return false;
// If there is a polygon specified, check the condition against that polygon
if( aSubpolyIndex >= 0 )
- return containsSingle( aP, aSubpolyIndex );
+ return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
// In any other case, check it against all polygons in the set
for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
{
- if( containsSingle( aP, polygonIdx ) )
+ if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
return true;
}
@@ -1440,20 +1440,23 @@ void SHAPE_POLY_SET::RemoveVertex( VERTEX_INDEX aIndex )
}
-bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex ) const
+bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
{
// Check that the point is inside the outline
if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
{
- // Check that the point is not in any of the holes
- for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
+ if( !aIgnoreHoles )
{
- const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
+ // Check that the point is not in any of the holes
+ for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
+ {
+ const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
- // If the point is inside a hole (and not on its edge),
- // it is outside of the polygon
- if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
- return false;
+ // If the point is inside a hole (and not on its edge),
+ // it is outside of the polygon
+ if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
+ return false;
+ }
}
return true;
diff --git a/include/geometry/shape_poly_set.h b/include/geometry/shape_poly_set.h
index ee9144d60..cec587022 100644
--- a/include/geometry/shape_poly_set.h
+++ b/include/geometry/shape_poly_set.h
@@ -933,9 +933,15 @@ class SHAPE_POLY_SET : public SHAPE
bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
int aClearance = 0 );
- ///> Returns true if a given subpolygon contains the point aP. If aSubpolyIndex < 0
- ///> (default value), checks all polygons in the set
- bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1 ) const;
+ /**
+ * Returns true if a given subpolygon contains the point aP
+ *
+ * @param aP is the point to check
+ * @param aSubpolyIndex is the subpolygon to check, or -1 to check all
+ * @param aIgnoreHoles controls whether or not internal holes are considered
+ * @return true if the polygon contains the point
+ */
+ bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, bool aIgnoreHoles = false ) const;
///> Returns true if the set is empty (no polygons at all)
bool IsEmpty() const
@@ -1112,10 +1118,11 @@ class SHAPE_POLY_SET : public SHAPE
* the aSubpolyIndex-th polygon will be tested.
* @param aSubpolyIndex is an integer specifying which polygon in the set has to be
* checked.
+ * @param aIgnoreHoles can be set to true to ignore internal holes in the polygon
* @return bool - true if aP is inside aSubpolyIndex-th polygon; false in any other
* case.
*/
- bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex ) const;
+ bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles = false ) const;
/**
* Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet
diff --git a/pcbnew/board_items_to_polygon_shape_transform.cpp b/pcbnew/board_items_to_polygon_shape_transform.cpp
index fd3e763b0..4d5200e61 100644
--- a/pcbnew/board_items_to_polygon_shape_transform.cpp
+++ b/pcbnew/board_items_to_polygon_shape_transform.cpp
@@ -138,7 +138,7 @@ void MODULE::TransformPadsShapesWithClearanceToPolygon( PCB_LAYER_ID aLayer,
wxSize margin;
for( ; pad != NULL; pad = pad->Next() )
{
- if( !pad->IsOnLayer(aLayer) )
+ if( aLayer != UNDEFINED_LAYER && !pad->IsOnLayer(aLayer) )
continue;
// NPTH pads are not drawn on layers if the shape size and pos is the same
@@ -206,7 +206,8 @@ void MODULE::TransformGraphicShapesWithClearanceToPolygonSet(
int aInflateValue,
int aCircleToSegmentsCount,
double aCorrectionFactor,
- int aCircleToSegmentsCountForTexts ) const
+ int aCircleToSegmentsCountForTexts,
+ bool aIncludeText ) const
{
std::vector<TEXTE_MODULE *> texts; // List of TEXTE_MODULE to convert
EDGE_MODULE* outline;
@@ -219,7 +220,8 @@ void MODULE::TransformGraphicShapesWithClearanceToPolygonSet(
{
TEXTE_MODULE* text = static_cast<TEXTE_MODULE*>( item );
- if( text->GetLayer() == aLayer && text->IsVisible() )
+ if( ( aLayer != UNDEFINED_LAYER && text->GetLayer() == aLayer )
+ && text->IsVisible() )
texts.push_back( text );
break;
@@ -228,7 +230,7 @@ void MODULE::TransformGraphicShapesWithClearanceToPolygonSet(
case PCB_MODULE_EDGE_T:
outline = (EDGE_MODULE*) item;
- if( outline->GetLayer() != aLayer )
+ if( aLayer != UNDEFINED_LAYER && outline->GetLayer() != aLayer )
break;
outline->TransformShapeWithClearanceToPolygon( aCornerBuffer, 0,
@@ -240,6 +242,9 @@ void MODULE::TransformGraphicShapesWithClearanceToPolygonSet(
}
}
+ if( !aIncludeText )
+ return;
+
// Convert texts sur modules
if( Reference().GetLayer() == aLayer && Reference().IsVisible() )
texts.push_back( &Reference() );
diff --git a/pcbnew/class_module.cpp b/pcbnew/class_module.cpp
index c201a0f5d..46bb4538e 100644
--- a/pcbnew/class_module.cpp
+++ b/pcbnew/class_module.cpp
@@ -512,6 +512,25 @@ const EDA_RECT MODULE::GetBoundingBox() const
}
+SHAPE_POLY_SET MODULE::GetBoundingPoly() const
+{
+ const int segcountforcircle = 8;
+ double correctionFactor = 1.0 / cos( M_PI / (segcountforcircle * 2) );
+ SHAPE_POLY_SET poly;
+
+ TransformPadsShapesWithClearanceToPolygon( UNDEFINED_LAYER,
+ poly, 0, segcountforcircle, correctionFactor );
+
+ TransformGraphicShapesWithClearanceToPolygonSet( UNDEFINED_LAYER,
+ poly, 0, segcountforcircle, correctionFactor, 0, false );
+
+ poly.NormalizeAreaOutlines();
+ poly.Inflate( Millimeter2iu( 0.01 ), segcountforcircle );
+
+ return poly;
+}
+
+
void MODULE::GetMsgPanelInfo( std::vector< MSG_PANEL_ITEM >& aList )
{
int nbpad;
@@ -607,6 +626,13 @@ bool MODULE::HitTest( const wxPoint& aPosition ) const
}
+bool MODULE::HitTestAccurate( const wxPoint& aPosition ) const
+{
+ auto shape = GetBoundingPoly();
+ return shape.Contains( aPosition, -1, true );
+}
+
+
bool MODULE::HitTest( const EDA_RECT& aRect, bool aContained, int aAccuracy ) const
{
EDA_RECT arect = aRect;
diff --git a/pcbnew/class_module.h b/pcbnew/class_module.h
index 3eca1a015..ac5d1c2ec 100644
--- a/pcbnew/class_module.h
+++ b/pcbnew/class_module.h
@@ -148,6 +148,12 @@ public:
*/
EDA_RECT GetFootprintRect() const;
+ /**
+ * Returns a bounding polygon for the shapes and pads in the module
+ * This operation is slower but more accurate than calculating a bounding box
+ */
+ SHAPE_POLY_SET GetBoundingPoly() const;
+
// Virtual function
const EDA_RECT GetBoundingBox() const override;
@@ -336,7 +342,7 @@ public:
* and adds these polygons to aCornerBuffer
* Useful to generate a polygonal representation of a footprint
* in 3D view and plot functions, when a full polygonal approach is needed
- * @param aLayer = the current layer: pads on this layer are considered
+ * @param aLayer = the layer to consider, or UNDEFINED_LAYER to consider all
* @param aCornerBuffer = the buffer to store polygons
* @param aInflateValue = an additionnal size to add to pad shapes
* aInflateValue = 0 to have the exact pad size
@@ -366,7 +372,7 @@ public:
* and adds these polygons to aCornerBuffer
* Useful to generate a polygonal representation of a footprint
* in 3D view and plot functions, when a full polygonal approach is needed
- * @param aLayer = the current layer: items on this layer are considered
+ * @param aLayer = the layer to consider, or UNDEFINED_LAYER to consider all
* @param aCornerBuffer = the buffer to store polygons
* @param aInflateValue = a value to inflate shapes
* aInflateValue = 0 to have the exact shape size
@@ -385,7 +391,8 @@ public:
int aInflateValue,
int aCircleToSegmentsCount,
double aCorrectionFactor,
- int aCircleToSegmentsCountForTexts = 0 ) const;
+ int aCircleToSegmentsCountForTexts = 0,
+ bool aIncludeText = true ) const;
/**
* @brief TransformGraphicTextWithClearanceToPolygonSet
@@ -430,6 +437,17 @@ public:
bool HitTest( const wxPoint& aPosition ) const override;
+ /**
+ * Tests if a point is inside the bounding polygon of the module
+ *
+ * The other hit test methods are just checking the bounding box, which
+ * can be quite inaccurate for rotated or oddly-shaped footprints.
+ *
+ * @param aPosition is the point to test
+ * @return true if aPosition is inside the bounding polygon
+ */
+ bool HitTestAccurate( const wxPoint& aPosition ) const;
+
bool HitTest( const EDA_RECT& aRect, bool aContained = true, int aAccuracy = 0 ) const override;
/**
diff --git a/pcbnew/collectors.cpp b/pcbnew/collectors.cpp
index 8b3e7d37a..cd692adfc 100644
--- a/pcbnew/collectors.cpp
+++ b/pcbnew/collectors.cpp
@@ -399,7 +399,8 @@ SEARCH_RESULT GENERAL_COLLECTOR::Inspect( EDA_ITEM* testItem, void* testData )
{
if( item->HitTest( m_RefPos ) )
{
- Append( item );
+ if( !module || module->HitTestAccurate( m_RefPos ) )
+ Append( item );
goto exit;
}
}
--
2.14.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
