flat assembler
Message board for the users of flat assembler.
![]() |
Author |
|
Vasilev Vjacheslav 26 Feb 2007, 11:19
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)); } |
|||
![]() |
|
Vasilev Vjacheslav 26 Feb 2007, 11:25
<sorry for double post>
Last edited by Vasilev Vjacheslav on 26 Feb 2007, 13:56; edited 1 time in total |
|||
![]() |
|
SomeoneNew 26 Feb 2007, 11:25
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. |
|||
![]() |
|
Goplat 27 Feb 2007, 02:10
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] @@: |
|||
![]() |
|
tantrikwizard 27 Feb 2007, 02:29
anyone know of an MMX or SSE implementation to check many points?
|
|||
![]() |
|
SomeoneNew 27 Feb 2007, 08:02
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 ![]() |
|||
![]() |
|
Madis731 27 Feb 2007, 13:46
should it be limited to SSE2? or can I use Packed Horizontal Subtract etc.
EDIT: I was kidding, no SSE3 was actually needed ![]() Last edited by Madis731 on 10 Mar 2007, 00:21; edited 1 time in total |
|||
![]() |
|
WytRaven 27 Feb 2007, 14:40
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 ![]() _________________ All your opcodes are belong to us |
|||
![]() |
|
f0dder 27 Feb 2007, 15:09
Have you profiled your code to see how much time you actually spend doing the "point in rect" code?
|
|||
![]() |
|
Madis731 09 Mar 2007, 23:35
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
![]() Maybe you have use for 3-digit IQ when doing MultiPointAgainstMultiRect routine ![]() Some day I will try to prove the WytRaven's code and make an SSE loop out of it ![]() 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 ![]() 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 |
|||
![]() |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2025, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.