flat assembler
Message board for the users of flat assembler.

 Index > Heap > How to optimally calculate object overlap
Author
 Thread
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 http://www.agner.org/optimize/
15 Jun 2008, 19:25
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.
15 Jun 2008, 19:32
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
```
15 Jun 2008, 19:54
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
15 Jun 2008, 21:11
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...

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///
```
15 Jun 2008, 21:37
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.
24 Jun 2008, 17:25
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum

Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.