Board index » delphi » Hit testing using regions (how expensive?)

Hit testing using regions (how expensive?)


2005-05-25 06:09:38 AM
delphi81
Back again with a basic graphics question but I am trying to decide on how to
handle my hit test logic. I have narrowed it down between polygon and
ellipise calculations vs. windows regions. I have seen both and in the past
I've used point point in polygon calculations before but thought I would see
what pros/cons there might be the regions approach.
Thanks,
Shawn
 
 

Re:Hit testing using regions (how expensive?)

It depends on what you are trying to achive.
If you are coding a game, polygonial testing might be a bit overkill - stick
with rectangle testing.
If you are building a paint program, with complex shape masking - then the
penalty is unavoidable.
Here is a routine for testing inside a polygon from my personal collection,
have no idea who wrote it, but perhaps it can help you..
Jon Lennart Aasenden
//##########################################################################
#
// Method: GDXPointInPolygon()
// Purpose: Check if a TPoint exists within a polygon shape
// Author: Unknown
// Changed: 16.05.05
// Comments: None;
//##########################################################################
#
function GDXPointInPolygon(const Points: TGDXPointArray;
X,Y: Integer):Boolean;
var
Count, K, J : Integer;
begin
Result := False;
Count := Length(Points) ;
J := Count-1;
for K := 0 to Count-1 do
begin
if ((Points[K].Y <=Y) and (Y < Points[J].Y)) or
((Points[J].Y <=Y) and (Y < Points[K].Y)) then
begin
if (x < (Points[j].X - Points[K].X) * (y - Points[K].Y) /
(Points[j].Y - Points[K].Y) + Points[K].X) then
Result := not Result;
end;
J := K;
end;
end;
"Shawn Oster" <XXXX@XXXXX.COM>writes
Quote
Back again with a basic graphics question but I am trying to decide on how
to
handle my hit test logic. I have narrowed it down between polygon and
ellipise calculations vs. windows regions. I have seen both and in the past
I've used point point in polygon calculations before but thought I would see
what pros/cons there might be the regions approach.

Thanks,
Shawn


 

Re:Hit testing using regions (how expensive?)

In article <XXXX@XXXXX.COM>, Shawn Oster writes:
Quote
Back again with a basic graphics question but I am trying to decide on how to
handle my hit test logic. I have narrowed it down between polygon and
ellipise calculations vs. windows regions. I have seen both and in the past
I've used point point in polygon calculations before but thought I would see
what pros/cons there might be the regions approach.
Well, the pro for PtInRegion is clearly that you do not need to code it <g>.
How fast it is depends on the complexity of the region, of course, but for any
final word on relative speeds you need to run timing tests.
The con for PtinRegion is the fact that regions consume Windows (GDI)
resources, so if you have many small regions around this may be a problem on
resource-starved environments like Win9x. And of course this approach is
Win32-specific (if Linux or .NET are of some importance for you this might be
the deciding factor. Perversly .NET has point and region classes but there
seems to be no equivalent for PtInRegion, the Region class has no Contains
method... ).
If you are concerned that the PtinPolygon test is too slow you can do the test
in two phases: first test against the bounding rectangle of the polygon, only
do the full test if that test returns true. This speeds up the test if the
mouse is not over the polygons bounding box but of course slows it down if it
is, so this is most suitable if you have many small polygons to test against,
or if the polygons are complex.
Peter Below (TeamB)
Use the newsgroup archives :
www.mers.com/searchsite.html
www.tamaracka.com/search.htm
groups.google.com
www.prolix.be
 

Re:Hit testing using regions (how expensive?)

"Shawn Oster" <XXXX@XXXXX.COM>skrev i meddelandet
Quote
Back again with a basic graphics question but I am trying to decide on how
to handle my hit test logic. I have narrowed it down between polygon and
ellipise calculations vs. windows regions. I have seen both and in the past
I've used point point in polygon calculations before but thought I would see
what pros/cons there might be the regions approach.
How many objects? How complex?
In BlockCAD (see sig) when the mouse is clicked on the screen I loop through
all objects, create the bounding region, test and delete the region again,
with no noticeable time lag even on models with many thousand parts.
OTOH, if you want to higlight on mouse-over, you may need a more optimized
approach.
If you do your own Z-buffer drawing, you could use a separate buffer with an
object pointer for every pixel on the screen, which will make hit testing
instantaneous, at the price of memory (and an extra store instruction in the
rendering loop)...
--
Anders Isaksson, Sweden
BlockCAD: web.telia.com/~u16122508/proglego.htm
Gallery: web.telia.com/~u16122508/gallery/index.htm
 

Re:Hit testing using regions (how expensive?)

"Shawn Oster" <XXXX@XXXXX.COM>writes
Quote
Back again with a basic graphics question but I am trying to decide on how
to handle my hit test logic. I have narrowed it down between polygon and
ellipise calculations vs. windows regions. I have seen both and in the past
I've used point point in polygon calculations before but thought I would see
what pros/cons there might be the regions approach.
You didnt give any details about in what context this is being done.
If you are ONLY using shapes that are smallish, and the entire graphic is
displayed fully in your app, you can get away with using regions. Those are
reasonably quick, even for graphics with many objects. Just create the
region, hit test it, and then _free_ the region, or you will end up with
resource problems.
If you are doing anything else - zooming, panning, etc, use your own
calculations. Its much more flexible, and you wont regret it. Plus,
regions slow down when they're big (such as when you zoom in onto a graphic,
making a shape increase in size and go off the screen).
 

Re:Hit testing using regions (how expensive?)

On Wed, 25 May 2005 10:59:41 +0200, "Peter Below (TeamB)"
<XXXX@XXXXX.COM>writes:
<snip>
Quote

The con for PtinRegion is the fact that regions consume Windows (GDI)
resources, so if you have many small regions around this may be a problem on
resource-starved environments like Win9x. And of course this approach is
Win32-specific (if Linux or .NET are of some importance for you this might be
the deciding factor. Perversly .NET has point and region classes but there
seems to be no equivalent for PtInRegion, the Region class has no Contains
method... ).

<snip>
The .Net Region class does not have PtInRegion, true.
But, both the Rectangle and RectangleF classes do have a Contains
method that returns true if a point is inside the rectangle and
false otherwise.
Using the Region class' GetRegionScans method to obtain an array
of all rectangles comprising the region, the problem boils down
to a simple loop thru the returned array and testing via the
rect[k].Contains method.
Oz
--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
 

Re:Hit testing using regions (how expensive?)

"GrandmasterB" <XXXX@XXXXX.COM>writes
Quote
"Shawn Oster" <XXXX@XXXXX.COM>writes
news:XXXX@XXXXX.COM...
>Back again with a basic graphics question but I am trying to decide on how
>to handle my hit test logic. I have narrowed it down between polygon and
>ellipise calculations vs. windows regions. I have seen both and in the
>past I have used point point in polygon calculations before but thought I'd
>see what pros/cons there might be the regions approach.

You didnt give any details about in what context this is being done.
A simple vector-based editor, something like MS Words drawing object. So I
need rotations, alignment, polygons, ellipises, text, etc.
Quote
If you are doing anything else - zooming, panning, etc, use your own
calculations. Its much more flexible, and you wont regret it. Plus,
regions slow down when they're big (such as when you zoom in onto a
graphic, making a shape increase in size and go off the screen).
Good point. I am layering my development process so first I am just getting
basic rotation and then I will move on to panning and zooming.
Shawn
 

Re:Hit testing using regions (how expensive?)

"Anders Isaksson" <XXXX@XXXXX.COM>writes
Quote
"Shawn Oster" <XXXX@XXXXX.COM>skrev i meddelandet
news:XXXX@XXXXX.COM...
>Back again with a basic graphics question but I am trying to decide on how
>to handle my hit test logic. I have narrowed it down between polygon and
>ellipise calculations vs. windows regions. I have seen both and in the
>past I have used point point in polygon calculations before but thought I'd
>see what pros/cons there might be the regions approach.

How many objects? How complex?
~200 objects
Quote
In BlockCAD (see sig) when the mouse is clicked on the screen I loop
through all objects, create the bounding region, test and delete the
region again, with no noticeable time lag even on models with many
thousand parts.
Thanks for the real-world figures, that is what I was looking for.
Quote
If you do your own Z-buffer drawing, you could use a separate buffer with
an object pointer for every pixel on the screen, which will make hit
testing instantaneous, at the price of memory (and an extra store
instruction in the rendering loop)...
I'm actually already doing this, I keep track of every object's actualy
location on screen vs. it is virtual location in metaunits (basically pixel
location vs. inch/mm location). I keep track of each bounding box as well
as each handle for each element though I am calculating handles even for
non-selected objects which I have a feeling is overkill. I should only
create those handles when an object is actually selected I think.
Shawn
 

Re:Hit testing using regions (how expensive?)

"Peter Below (TeamB)" <XXXX@XXXXX.COM>writes
Quote
In article <XXXX@XXXXX.COM>, Shawn Oster writes:
The con for PtinRegion is the fact that regions consume Windows (GDI)
resources, so if you have many small regions around this may be a problem
on
resource-starved environments like Win9x. And of course this approach is
Win32-specific (if Linux or .NET are of some importance for you this might
be
the deciding factor. Perversly .NET has point and region classes but there
seems to be no equivalent for PtInRegion, the Region class has no Contains
method... ).
I have been toying with writing this little project in either D2005 or
Chrome for the .NET exposure, thanks for the pointers on the .NET classes
and the reminded to keep my logic generic/portable.
Quote
If you are concerned that the PtinPolygon test is too slow you can do the
test
in two phases: first test against the bounding rectangle of the polygon,
only
do the full test if that test returns true. This speeds up the test if the
mouse is not over the polygons bounding box but of course slows it down if
it
is, so this is most suitable if you have many small polygons to test
against,
or if the polygons are complex.
Hmm, good idea, I like the approximate then fine-grained test. I think I'm
settling on doing the calculations myself at this point, but once I start
tackling circles I am wondering if that will change...
Thanks,
Shawn
 

Re:Hit testing using regions (how expensive?)

In article <42961256$XXXX@XXXXX.COM>, Shawn Oster writes:
Quote
Hmm, good idea, I like the approximate then fine-grained test. I think I'm
settling on doing the calculations myself at this point, but once I start
tackling circles I am wondering if that will change...
Circles are easy, you just have to check the distance to the circles center.
Peter Below (TeamB)
Use the newsgroup archives :
www.mers.com/searchsite.html
www.tamaracka.com/search.htm
groups.google.com
www.prolix.be
 

Re:Hit testing using regions (how expensive?)

Quote
Back again with a basic graphics question but I am trying to decide on how
to handle my hit test logic. I have narrowed it down between polygon and
ellipise calculations vs. windows regions. I have seen both and in the past
I've used point point in polygon calculations before but thought I would see
what pros/cons there might be the regions approach.
In DtpDocuments I use a mixed approach:
- First a quick check for each shape using the bounding box, this is just 4
"greater/smaller than" tests per shape, and narrows down detailed hittesting
nicely.
- If that test returns true, depending on the complexity of the shape I
follow a different approach:
- For simple polygonal shapes I do a "point in polygon" check using the
Gauss theorem (as can be found in Graphics32 TPolygon32.PtInPolygon).
- For complex or alpha-blended shapes, I do a hittest on the cache of that
shape to see if the pixel where the mouse is located has an alpha value
above threshold. I don't only test the mouse position, but also some other
positions, in a star-like pattern (M is mouse position):
* * *
* * *
* * M * *
* * *
* * *
This will ensure that the user can easily select a shape, even if the mouse
is not *exactly* over it. The nice thing about using the cached bitmap for
hit-testing is that you can easily avoid having a hit when the user clicks
"through" parts that are transparent (through the middle of the letter O for
instance) or through parts that have very low opacity (outer sides of
shadows, etc). This feels very intuitive for the user, when doing difficult
selection jobs with many layered shapes.
Doing a hittest on the bitmap cache of a shape is also very fast, much
faster than mathematically calculating the hittest with complex polygonal
regions (for text etc).
DtpDocuments is a commercial component, more info here:
www.simdesign.nl/dtpdocuments.html
Kind regards,
Nils Haeck
www.simdesign.nl
 

Re:Hit testing using regions (how expensive?)

Quote
Circles are easy, you just have to check the distance to the circles
center.
One can even optimize this by storing the squared radius of the circle, and
just computing the squared distance to the center. This saves one Sqrt
operation per check :)
Nils
www.simdesign.nl
 

Re:Hit testing using regions (how expensive?)

Quote
- For complex or alpha-blended shapes, I do a hittest on the cache of that
shape to see if the pixel where the mouse is located has an alpha value
above threshold. I don't only test the mouse position, but also some other
positions, in a star-like pattern (M is mouse position):

* * *
* * *
* * M * *
* * *
* * *
Just curious... why a star-like pattern? Intuitively I would use some circle
or rectangle pattern. But probably your star-like pattern has some
advantages I cannot see.
Jens