flat assembler
Message board for the users of flat assembler.

Index > Main > PointInRect - Can it be done Faster?

Author
Thread Post new topic Reply to topic
SomeoneNew



Joined: 12 Aug 2006
Posts: 54
SomeoneNew
I'm using PointInRect(); from the std API quite A LOT in my program and I was wondering if I could make a faster version, however I'd like to ask for other's experiences.

That said, I understand how to perform a check to see whether a bi-dimensional coordinate resides within a rect, problem being I'm not sure I'll gain any speed by coding my own. I'd sure have one less dependency though.

What would be the fastest way to perform this checks?


Thanks.

_________________
Im new, sorry if I bothered with any stupid question Smile
Post 26 Feb 2007, 11:07
View user's profile Send private message Reply with quote
Vasilev Vjacheslav



Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
i don't know if this can be really optimized

Code:
BOOL STDCALL PtInRect(CONST RECT *lprc, POINT pt)
{
  return((pt.x >= lprc->left) && (pt.x < lprc->right) &&
         (pt.y >= lprc->top) && (pt.y < lprc->bottom));
}
    
Post 26 Feb 2007, 11:19
View user's profile Send private message Reply with quote
Vasilev Vjacheslav



Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
<sorry for double post>


Last edited by Vasilev Vjacheslav on 26 Feb 2007, 13:56; edited 1 time in total
Post 26 Feb 2007, 11:25
View user's profile Send private message Reply with quote
SomeoneNew



Joined: 12 Aug 2006
Posts: 54
SomeoneNew
fair enough, pretty close to my own routine. what I wanted to ask is if theres any type of "batch" processing for this type of and comparison.

thanks vasilev.
Post 26 Feb 2007, 11:25
View user's profile Send private message Reply with quote
Goplat



Joined: 15 Sep 2006
Posts: 181
Goplat
If you want to check a whole bunch of points against one rectangle you could translate it into a left/top/width/height struct. This allows you do do the check a bit faster, like this: (sets carry if point is inside)
Code:
        mov eax,[X]
        sub eax,[left]
        cmp eax,[width]
        jae @f
        mov eax,[Y]
        sub eax,[top]
        cmp eax,[height]
@@:    
Post 27 Feb 2007, 02:10
View user's profile Send private message Reply with quote
tantrikwizard



Joined: 13 Dec 2006
Posts: 142
tantrikwizard
anyone know of an MMX or SSE implementation to check many points?
Post 27 Feb 2007, 02:29
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
SomeoneNew



Joined: 12 Aug 2006
Posts: 54
SomeoneNew
Thanks.


@tantrikwizard@,
You got it right. Thats the type of question I'm having as well.

I need to perform this operation multiple consecutive times and I was looking for the fastest way. Think about a 2D game with lots of objects, You would perform rect collision detection checking with this type of code, but when performances an issue... You want to squeeze as much juice from that fruit as you can.

I also use it for the menus and gui all over the place.

_________________
Im new, sorry if I bothered with any stupid question Smile
Post 27 Feb 2007, 08:02
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
should it be limited to SSE2? or can I use Packed Horizontal Subtract etc.
EDIT: I was kidding, no SSE3 was actually needed Razz simple parallel ALU unit operations


Last edited by Madis731 on 10 Mar 2007, 00:21; edited 1 time in total
Post 27 Feb 2007, 13:46
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
WytRaven



Joined: 08 Sep 2004
Posts: 45
Location: Canberra, Australia
WytRaven
I don't know where I came across this originally but I've been using it for years. I haven't even compared it to other methods but I'll post it here as food for thought anyway.

Pseudo Code:
Code:
if ((((PointX - RectLeft) XOR (PointX - RectRight)) AND ((PointY - RectTop) XOR (PointY - RectBottom))) AND 0x80000000)
{
    True: point in rect
}
else
{
    False: point not in rect
}
    

Considering I've been using this blindly for years I would be interested in a superior sollution to this very common operation too Smile

_________________
All your opcodes are belong to us
Post 27 Feb 2007, 14:40
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
Have you profiled your code to see how much time you actually spend doing the "point in rect" code?
Post 27 Feb 2007, 15:09
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
Here it is, it checks many points against one rectangle, but no IQ higher than 60 is required to convert it to one point against many rectangles Smile

Maybe you have use for 3-digit IQ when doing MultiPointAgainstMultiRect routine Very Happy

Some day I will try to prove the WytRaven's code and make an SSE loop out of it Wink Cheers!
Code:
        ;Make 4x2 PointsInRect calculations in parallel
        ;Can be modified upto 4x(13..14) in one pass
        ;points are words X,Y,X,Y,....
        ;rects are words X1,Y1,X2,Y2,....
        ;if you have a X1,Y1,W,H configuration then it
        ;saves some instructions
        movdqa  xmm0,dqword[points]     ;first set
        movdqa  xmm1,dqword[points+16]  ;second four points

        movq    xmm14,qword[rects]      ;our rectangle
        pshufd  xmm15,xmm14,00000000b   ;X1,Y1,.. * 4
        pshufd  xmm14,xmm14,01010101b   ;X2,Y2,.. * 4
        psubw   xmm14,xmm15             ;widths,heights * 4

        psubw   xmm0,xmm15 ;points normalised to the l/t corner
        psubw   xmm1,xmm15

        psubw   xmm0,dqword[maxnegative];down to negative wrapover
        psubw   xmm1,dqword[maxnegative];MMX/SSE only have signed cmp

        psubw   xmm14,dqword[maxnegative]

        movdqa  xmm15,xmm14             ;we can reuse xmm15

        pcmpgtw xmm14,xmm0              ;Make flags
        movdqa  xmm0,xmm14
        pshuflw xmm0,xmm0,10110001b     ;X can be in rect while Y not
        pshufhw xmm0,xmm0,10110001b     ;or the other way so we must
        pand    xmm0,xmm14              ;make the result definite

        pcmpgtw xmm15,xmm1              ;You can add these for any new point
        movdqa  xmm1,xmm15              ;groups introduced, but xmm14 or
        pshuflw xmm1,xmm1,10110001b     ;some other register needs to be reused
        pshufhw xmm1,xmm1,10110001b
        pand    xmm1,xmm15
        ;OUT:xmm0,xmm1
        ;0FFFFFFFFh means point in a rect
        ; 00000000h means outside
        ;Rules are: Left,Top can equal
        ;           Right,Bottom can not
        ;Changed by maxnegative 8000=>7FFF
    

Here's the data section:
Code:
align 16
maxnegative dq 8000800080008000h,8000800080008000h
points dw 10,31
       dw 255,24
       dw 2453,304
       dw 21,199
       dw 420,300
       dw 13,3
       dw 3,0
       dw 14,125

rects  dw 10,24,40,200  
    


As always not very optimized, blah..blah, you can do anything you like with it & stuff...

EDIT:
Okay, it works and its fast (23 instructions compared to 22 in the above implementations), but there are two main pain-points. One of them what I hate is that I couldn't do it using only 4 XMM registers and other being the awkward output 80000000h (alternatively 80008000h) indicating inside the rect.
There are some ways around it including lots of lines Smile, but its possible as you can see from the additional lines making it 25 instructions total.
Here it is:
Code:
        ;Make 4x2 PointsInRect calculations in parallel
        ;Can be modified upto 4x12 in one pass
        ;points are words X,Y,X,Y,....
        ;rects are words X1,Y1,X2,Y2,....
        ;if you have a X1,Y1,W,H configuration then it
        ;adds some instructions
        movdqa  xmm0,dqword[points]     ;first set
        movdqa  xmm1,dqword[points+16]  ;second four points

        movq    xmm14,qword[rects]      ;our rectangle
        pshufd  xmm15,xmm14,00000000b   ;X1,Y1,.. * 4
        pshufd  xmm14,xmm14,01010101b   ;X2,Y2,.. * 4

        movdqa  xmm2,xmm0
        movdqa  xmm3,xmm1

        psubw   xmm0,xmm15              ;X,Y - Left,Top
        psubw   xmm1,xmm15
        psubw   xmm2,xmm14              ;X,Y - Right,Bottom
        psubw   xmm3,xmm14

        pxor    xmm0,xmm2
        pxor    xmm1,xmm3

        movdqa  xmm2,xmm0
        pshuflw xmm2,xmm2,10110001b     ;X can be in rect while Y not
        pshufhw xmm2,xmm2,10110001b     ;or the other way so we must
        pand    xmm0,xmm2               ;make the result definite
        pand    xmm0,dqword[flags]

        movdqa  xmm3,xmm1               ;groups introduced, but xmm14 or
        pshuflw xmm3,xmm3,10110001b     ;some other register needs to be reused
        pshufhw xmm3,xmm3,10110001b
        pand    xmm1,xmm3
        pand    xmm1,dqword[flags]
        ;OUT:xmm0,xmm1
        ;080000000h means point in a rect
        ; 00000000h means outside
        pcmpeqd xmm0,dqword[flags]      ;Alternatively
        pcmpeqd xmm1,dqword[flags]
        ;OUT:xmm0,xmm1
        ;0FFFFFFFFh means point in a rect
        ; 00000000h means outside
    


You need additional flags definition in your data:
Code:
flags       dq 8000000080000000h,8000000080000000h
    
Post 09 Mar 2007, 23:35
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
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
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.