flat assembler
Message board for the users of flat assembler.

Index > Heap > How to optimally calculate object overlap

Author
Thread Post new topic Reply to topic
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Problem:
Two rectangles, both have the same y-coordinates, but x-s are different and so are their lengths. What is the minimal algorithm?

Solution1:
rect1.left > rect2.left && rect1.left < rect2.right ||
rect1.right > rect2.left && rect1.right < rect2.right

Solution2:
rect1.left <= rect2.right && rect1.right >= rect2.left ??
Does this work in any situation?

Solution3:
Any shorter ones?

_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 15 Jun 2008, 19:25
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17247
Location: In your JS exploiting you and your system
revolution
I would expect that IntersectRect will use an optimal algo. You can disassemble it and see what it does.
Post 15 Jun 2008, 19:32
View user's profile Send private message Visit poster's website Reply with quote
rCX



Joined: 29 Jul 2007
Posts: 166
Location: Maryland, USA
rCX
Functions I wrote for my games.

FASM implementation:
Code:
;______Rectangle-Rectangle Overlap_____
;Input:
;    [a.x1], [a.y1],[a.x2],[a.y2]
;       [b.x1], [b.y1],[b.x2],[b.y2]
;Output:
;       cf = 0 if no overlap; cf = 1 if overlap
RectangleRectangleOverlap:
   pusha
       pushf

   mov ax,[b.x1]   ;ax = b.x1
  mov bx,[b.y1]   ;bx = b.y1
  mov cx,[b.x2]   ;cx = b.x2
  mov dx,[b.y2]   ;dx = b.y2

      cmp [a.y1],dx   ;\IF a.y1 > b.y2 THEN GOTO .NoOverlap
   jg .NoOverlap   ;/
  cmp [a.x2],ax   ;\IF a.x2 < b.x1 THEN GOTO .NoOverlap
   jl .NoOverlap   ;/
  cmp [a.y2],bx   ;\IF a.y2 < b.y1 THEN GOTO .NoOverlap
   jl .NoOverlap   ;/
  cmp [a.x1],cx   ;\IF a.x1 > b.x2 THEN GOTO .NoOverlap
   jg .NoOverlap   ;/

      .Overlap:
               popf
                stc     ;cf = 1 (cy); Rectangles Overlap
            jmp .Return

     .NoOverlap:
             popf
                clc     ;cf = 0 (nc); Rectangles do not overlap

 .Return:
                popa
                ret
    


FreeBASIC implementation
Code:
'Detects whether two rectangular areas, (Ax1,Ay1)-(Ax2,Ay2) and (Bx1,By1)-(Bx2,By2), overlap.  It returns...
'       TRUE if rectangles overlap
'        FALSE if rectangles don't overlap
Function RectangleRectangleOverlap(Ax1 As Integer,Ay1 As Integer,Ax2 As Integer,Ay2 As Integer,Bx1 As Integer,By1 As Integer,Bx2 As Integer,By2 As Integer) As Byte
   Return Not ( (Ay1 > By2) Or (Ax2 < Bx1) Or (Ay2 < By1) Or (Ax1 > Bx2) )
End Function
    
Post 15 Jun 2008, 19:54
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Oh yeah, the solution 2 works. I see that you, rCX, also assumed that rectangles are drawn from upper-left to lower-right
Post 15 Jun 2008, 21:11
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
this is the hit.inc function for fool.

it will test the collision between two sets of coordinates.

X1,Y1,XL1,YL1
X2,Y2,XL2,YL2

Code:
hit:
.call=0
.x=4
.y=8
.xl=12
.yl=16
.func=4
.param=8
.size=12
.data=16
; edi= parent item
; esi = current item
        push eax ebx ecx edx
        mov ecx,[esi+.size]
        shr ecx,2
        jl .end
.next:
        push ecx esi edi
        mov esi,[esi+ecx*4+.data]
.xx:    ; compare the x coordinates
        mov eax,[esi+.x]
        mov ebx,[esi+.xl]
        mov ecx,[edi+.x]
        mov edx,[edi+.xl]
        cmp edx,0
        jge @f
        add ecx,edx
        neg edx
@@:
        sub eax,ecx
        jl @f
        sub eax,edx
        jg .not
        jmp .yy
@@:
        add eax,ebx
        jle .not
.yy:    ; test the Y coordinates
        mov eax,[esi+.y]
        mov ebx,[esi+.yl]
        mov ecx,[edi+.y]
        mov edx,[edi+.yl]
        cmp edx,0
        jge @f
        add ecx,edx
        neg edx
@@:
        sub eax,ecx
        jl @f
        sub eax,edx
        jg .not  ; there is no collision
        jmp .ok  
@@:
        add eax,ebx
        jle .not
.ok:     ; collision loop
        pop edi esi ecx
        mov eax,[esi+.func]
        or eax,eax   ; is it a null pointer?
        je @f
        call eax   ; will call the function assigned to the current collision.
@@:
        jmp .end
.not:     ; no collision loop
        pop edi esi ecx
        dec ecx
        jnl .next             ; do the next detection
.end:
        pop edx ecx ebx eax
        ret
    


it seems that it can be avantageouslly optimised by the RCX solution...
Very Happy
now, an application of this function:

Code:
.hit    dd f.hit,.function,.param,@f-$-4
        dd ball0,ball1,ball2,ball3
        dd ball4,ball5,ball6,ball7
        @@:
.param    dd variable
.function  dd f.asm,@f
              @@:
             ; here the asm code to execute when there is a collision///
    
Post 15 Jun 2008, 21:37
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Okay, all are great general solutions, but my problem was simpler - no change in the y-coordine so this one was already sorted out. Thanks for helping. I will stick with solution 2. I think I've proved that it will work in any solution.
Post 24 Jun 2008, 17:25
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 can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.