kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #34026
Re: [PATCH] Use polygonal hit testing for module selection
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 <stambaughw@xxxxxxxxx>
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@xxxxxxxxxxxxxxxxxxx
>> Unsubscribe : https://launchpad.net/~kicad-developers
>> More help : https://help.launchpad.net/ListHelp
>>
>>
> _______________________________________________
> Mailing list: https://launchpad.net/~kicad-developers
> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> 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 <jon@xxxxxxxxxxxxx>
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
Follow ups
References
