 |
BorlandTalk.com
Borland discussion newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Shawn Oster
Guest
|
 Posted: Tue May 24, 2005 10:09 pm Post subject: Hit testing using regions (how expensive?) |
 |
|
Back again with a basic graphics question but I'm trying to decide on how to
handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the past
I've used point point in polygon calculations before but thought I'd see
what pros/cons there might be the regions approach.
Thanks,
Shawn
|
|
| Back to top |
|
 |
Jon Lennart Aasenden
Guest
|
| Posted: Wed May 25, 2005 7:45 am Post subject: 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"
| Quote: | Back again with a basic graphics question but I'm trying to decide on how
to
handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the past
I've used point point in polygon calculations before but thought I'd see
what pros/cons there might be the regions approach.
Thanks,
Shawn
|
|
|
| Back to top |
|
|
Peter Below (TeamB)
Guest
|
| Posted: Wed May 25, 2005 8:59 am Post subject: Re: Hit testing using regions (how expensive?) |
|
|
In article <4293a5b8 (AT) newsgroups (DOT) borland.com>, Shawn Oster wrote:
| Quote: | Back again with a basic graphics question but I'm trying to decide on how to
handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the past
I've used point point in polygon calculations before but thought I'd 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 :
http://www.mers.com/searchsite.html
http://www.tamaracka.com/search.htm
http://groups.google.com
http://www.prolix.be
|
|
| Back to top |
|
|
Anders Isaksson
Guest
|
| Posted: Wed May 25, 2005 4:26 pm Post subject: Re: Hit testing using regions (how expensive?) |
|
|
"Shawn Oster" <soster (AT) colorflex (DOT) com> skrev i meddelandet
news:4293a5b8 (AT) newsgroups (DOT) borland.com...
| Quote: | Back again with a basic graphics question but I'm trying to decide on how
to handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the past
I've 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?
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: http://web.telia.com/~u16122508/proglego.htm
Gallery: http://web.telia.com/~u16122508/gallery/index.htm
|
|
| Back to top |
|
|
GrandmasterB
Guest
|
| Posted: Wed May 25, 2005 5:56 pm Post subject: Re: Hit testing using regions (how expensive?) |
|
|
"Shawn Oster" <soster (AT) colorflex (DOT) com> wrote
| Quote: | Back again with a basic graphics question but I'm trying to decide on how
to handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the past
I've 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.
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'll 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).
|
|
| Back to top |
|
|
ozbear
Guest
|
| Posted: Thu May 26, 2005 8:01 am Post subject: Re: Hit testing using regions (how expensive?) |
|
|
On Wed, 25 May 2005 10:59:41 +0200, "Peter Below (TeamB)"
<100113.1101 (AT) compuXXserve (DOT) com> wrote:
<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?
|
|
| Back to top |
|
|
Shawn Oster
Guest
|
| Posted: Thu May 26, 2005 6:11 pm Post subject: Re: Hit testing using regions (how expensive?) |
|
|
"GrandmasterB" <Fizzle (AT) shizzle (DOT) com> wrote
| Quote: | "Shawn Oster" <soster (AT) colorflex (DOT) com> wrote in message
news:4293a5b8 (AT) newsgroups (DOT) borland.com...
Back again with a basic graphics question but I'm trying to decide on how
to handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the
past I've 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'm layering my development process so first I'm just getting
basic rotation and then I'll move on to panning and zooming.
Shawn
|
|
| Back to top |
|
|
Shawn Oster
Guest
|
| Posted: Thu May 26, 2005 6:14 pm Post subject: Re: Hit testing using regions (how expensive?) |
|
|
"Anders Isaksson" <isaksson.etuna (AT) REMOVEebox (DOT) tninet.se> wrote
| Quote: | "Shawn Oster" <soster (AT) colorflex (DOT) com> skrev i meddelandet
news:4293a5b8 (AT) newsgroups (DOT) borland.com...
Back again with a basic graphics question but I'm trying to decide on how
to handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the
past I've 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's 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's 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'm 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
|
|
| Back to top |
|
|
Shawn Oster
Guest
|
| Posted: Thu May 26, 2005 6:17 pm Post subject: Re: Hit testing using regions (how expensive?) |
|
|
"Peter Below (TeamB)" <100113.1101 (AT) compuXXserve (DOT) com> wrote
| Quote: | In article <4293a5b8 (AT) newsgroups (DOT) borland.com>, Shawn Oster wrote:
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'm wondering if that will change...
Thanks,
Shawn
|
|
| Back to top |
|
|
Peter Below (TeamB)
Guest
|
| Posted: Fri May 27, 2005 2:37 pm Post subject: Re: Hit testing using regions (how expensive?) |
|
|
In article <42961256$1 (AT) newsgroups (DOT) borland.com>, Shawn Oster wrote:
| 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'm 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 :
http://www.mers.com/searchsite.html
http://www.tamaracka.com/search.htm
http://groups.google.com
http://www.prolix.be
|
|
| Back to top |
|
|
Nils Haeck
Guest
|
| Posted: Tue May 31, 2005 8:29 pm Post subject: Re: Hit testing using regions (how expensive?) |
|
|
| Quote: | Back again with a basic graphics question but I'm trying to decide on how
to handle my hit test logic. I've narrowed it down between polygon and
ellipise calculations vs. windows regions. I've seen both and in the past
I've used point point in polygon calculations before but thought I'd 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:
http://www.simdesign.nl/dtpdocuments.html
Kind regards,
Nils Haeck
www.simdesign.nl
|
|
| Back to top |
|
|
Nils Haeck
Guest
|
| Posted: Wed Jun 01, 2005 11:02 am Post subject: 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
|
|
| Back to top |
|
|
Jens Gruschel
Guest
|
| Posted: Fri Jun 03, 2005 3:07 pm Post subject: 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'd use some circle
or rectangle pattern. But probably your star-like pattern has some
advantages I cannot see.
Jens
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
