kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #34143
Re: [PATCH] Use polygonal hit testing for module selection
Here's a patch that fixes the issues observed.
I have changed the algorithm to a simpler one that should be more
bulletproof.
I think the optimal approach for complicated footprints is still not this
way, but that would require more time to tweak and optimize (i.e.
generating some kind of bounding hull that is non-convex, and caching it
until the shape changes)
You can see the new patch on Andrzej's test files here:
https://imgur.com/a/L16ky
Purple shows the bounding boxes, yellow shows the selectable area under the
new algorithm.
-Jon
On Wed, Feb 21, 2018 at 1:41 PM, Wayne Stambaugh <stambaughw@xxxxxxxxx>
wrote:
> If you could get it done by Friday before I roll out rc1, that's fine.
>
> Wayne
>
> On 2/21/2018 1:37 PM, Jon Evans wrote:
> > I'll be able to look at it this evening. Can report then whether or not
> > I will have a patch tonight. Up to you whether or not that is too long
> > of a delay.
> >
> > -Jon
> >
> > On Wed, Feb 21, 2018 at 1:32 PM, Wayne Stambaugh <stambaughw@xxxxxxxxx
> > <mailto:stambaughw@xxxxxxxxx>> wrote:
> >
> > Jon,
> >
> > Would you please take a look at this as soon as possible? If you
> cannot
> > get to it in a reasonable amount of time, please let me know so I can
> > back out your polygon hit test patch. We need to be able to select
> > footprints.
> >
> > Thanks,
> >
> > Wayne
> >
> > On 2/21/2018 11:41 AM, Andrzej Wolski wrote:
> > > After this patch, I can no longer select some footprints by
> clicking
> > > inside their area.
> > > Please see the board in an attachment.
> > >
> > > Andrzej
> > >
> > > W dniu 2018-02-20 o 16:44, Wayne Stambaugh pisze:
> > >> Jon,
> > >>
> > >> I merged your patch.
> > >>
> > >> Thanks,
> > >>
> > >> Wayne
> > >>
> > >> On 2/18/2018 7:01 PM, Jon Evans wrote:
> > >>> 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 <mailto:stambaughw@xxxxxxxxx>
> > >>> <mailto:stambaughw@xxxxxxxxx <mailto: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
> > <https://bugs.launchpad.net/kicad/+bug/1749077>
> > >>> <https://bugs.launchpad.net/kicad/+bug/1749077
> > <https://bugs.launchpad.net/kicad/+bug/1749077>>
> > >>>
> > >>> -Jon
> > >>>
> > >>>
> > >>> _______________________________________________
> > >>> Mailing list: https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > >>> <https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>>
> > >>> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> > <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
> > >>> <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx
> > <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>>
> > >>> Unsubscribe : https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > >>> <https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>>
> > >>> More help : https://help.launchpad.net/ListHelp
> > <https://help.launchpad.net/ListHelp>
> > >>> <https://help.launchpad.net/ListHelp
> > <https://help.launchpad.net/ListHelp>>
> > >>>
> > >>>
> > >>> _______________________________________________
> > >>> Mailing list: https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > >>> <https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>>
> > >>> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> > <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
> > >>> <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx
> > <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>>
> > >>> Unsubscribe : https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > >>> <https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>>
> > >>> More help : https://help.launchpad.net/ListHelp
> > <https://help.launchpad.net/ListHelp>
> > >>> <https://help.launchpad.net/ListHelp
> > <https://help.launchpad.net/ListHelp>>
> > >>>
> > >>>
> > >> _______________________________________________
> > >> Mailing list: https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > >> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> > <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
> > >> Unsubscribe : https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > >> More help : https://help.launchpad.net/ListHelp
> > <https://help.launchpad.net/ListHelp>
> > >
> > >
> > >
> > >
> > > _______________________________________________
> > > Mailing list: https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > > Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> > <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
> > > Unsubscribe : https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > > More help : https://help.launchpad.net/ListHelp
> > <https://help.launchpad.net/ListHelp>
> > >
> >
> > _______________________________________________
> > Mailing list: https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> > <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
> > Unsubscribe : https://launchpad.net/~kicad-developers
> > <https://launchpad.net/~kicad-developers>
> > More help : https://help.launchpad.net/ListHelp
> > <https://help.launchpad.net/ListHelp>
> >
> >
>
From ceb5047d9703968d3634916febc926e4c644510c Mon Sep 17 00:00:00 2001
From: Jon Evans <jon@xxxxxxxxxxxxx>
Date: Wed, 21 Feb 2018 20:39:46 -0500
Subject: [PATCH] Change algorithm for GetBoundingPoly() to something that
works better
---
pcbnew/class_module.cpp | 46 ++++++++++++++++++++++++++++++++++++++--------
1 file changed, 38 insertions(+), 8 deletions(-)
diff --git a/pcbnew/class_module.cpp b/pcbnew/class_module.cpp
index 46bb4538e..564cf3c67 100644
--- a/pcbnew/class_module.cpp
+++ b/pcbnew/class_module.cpp
@@ -512,20 +512,50 @@ const EDA_RECT MODULE::GetBoundingBox() const
}
+/**
+ * This is a bit hacky right now for performance reasons.
+ *
+ * We assume that most footprints will have features aligned to the axes in
+ * the zero-rotation state. Therefore, if the footprint is rotated, we
+ * temporarily rotate back to zero, get the bounding box (excluding reference
+ * and value text) and then rotate the resulting poly back to the correct
+ * orientation.
+ *
+ * This is more accurate than using the AABB when most footprints are rotated
+ * off of the axes, but less accurate than computing some kind of bounding hull.
+ * We should consider doing that instead at some point in the future if we can
+ * use a performant algorithm and cache the result to avoid extra computing.
+ */
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 );
+ double orientation = GetOrientationRadians();
+
+ MODULE temp = *this;
+ temp.SetOrientation( 0.0 );
+ BOX2I area = temp.GetFootprintRect();
+
+ poly.NewOutline();
- TransformGraphicShapesWithClearanceToPolygonSet( UNDEFINED_LAYER,
- poly, 0, segcountforcircle, correctionFactor, 0, false );
+ VECTOR2I p = area.GetPosition();
+ poly.Append( p );
+ p.x = area.GetRight();
+ poly.Append( p );
+ p.y = area.GetBottom();
+ poly.Append( p );
+ p.x = area.GetX();
+ poly.Append( p );
+
+ BOARD* board = GetBoard();
+ if( board )
+ {
+ int biggest_clearance = board->GetDesignSettings().GetBiggestClearanceValue();
+ poly.Inflate( biggest_clearance, 4 );
+ }
- poly.NormalizeAreaOutlines();
- poly.Inflate( Millimeter2iu( 0.01 ), segcountforcircle );
+ poly.Inflate( Millimeter2iu( 0.01 ), 4 );
+ poly.Rotate( -orientation, m_Pos );
return poly;
}
--
2.14.1
Follow ups
References
