Hi folks,
I am facing the following problem:
I have a set of rectangles in memory (defined with X, Y, Width, Height - all bytes) and I need to, for each of them, calculate the intersection rectangles (also X, Y, Width, Height) between them and a reference rectangle (again, X, Y, Width, Height) - in Z80 machine code, as fast as possible.
First things first: is there, by any chance, some free, optimized lib which does that or which could be adapted to do that?
Supposing such lib is not available, I imagine to use a basic algorithm like:
Loop through Rectangles
; test overlap
if (Rn.X + Rn.Width) < RefRect.X, break loop
if (RefRect.X + RefRect.Width) < Rn.X, break loop
if (Rn.Y + Rn.Height) < RefRect.Y, break loop
if (RefRect.Y + RefRect.Height) < Rn.Y, break loop
; overlap confirmed. Calculate intersection
if (Rn.X > RefRect.X)
IntRect.X = Rn.X
IntRect.Width = Min (Rn.Width, RefRect.Width - (Rn.X - RefRect.X))
else
IntRect.X = RefRect.X
IntRect.Width = Min (RefRect.Width, Rn.Width - (RefRect.X - Rn.X))
if (Rn.Y > RefRect.Y)
IntRect.Y = Rn.Y
IntRect.Height = Min (Rn.Height, RefRect.Height - (Rn.Y - RefRect.Y))
else
IntRect.Y = RefRect.Y
IntRect.Height = Min (RefRect.Height, Rn.Height - (RefRect.Y - Rn.Y))
< Use IntRect >
Note: I don't need to store IntRect. If in the end it is all set in registers, all the better.
Question 1: The algorithm is clearly a basic, straight-forward one. I see that maybe treating all horizontal calculations first and all vertical ones afterwards could improve code size and cycles. I wonder, however, if it can be heavily optimized in some way. Do you guys have any idea?
Question 2: It looks to me that implementing an optimized Z80 code for the algorithm above may be somewhat tricky, given the alternances of live data in registers (as opposed to data stored in memory). Do you foresee any pitfalls I'd want to avoid or any path I'd want to pursue in the implementation? Do you have any insights on approaches you'd suggest me to explore?
Thanks in advance!

.