summaryrefslogtreecommitdiff
path: root/src/libs/graphics/intersec.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/libs/graphics/intersec.c')
-rw-r--r--src/libs/graphics/intersec.c415
1 files changed, 415 insertions, 0 deletions
diff --git a/src/libs/graphics/intersec.c b/src/libs/graphics/intersec.c
new file mode 100644
index 0000000..02a5226
--- /dev/null
+++ b/src/libs/graphics/intersec.c
@@ -0,0 +1,415 @@
+//Copyright Paul Reiche, Fred Ford. 1992-2002
+
+/*
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#include "libs/graphics/context.h"
+#include "libs/graphics/drawable.h"
+#include "libs/graphics/tfb_draw.h"
+#include "libs/log.h"
+
+//#define DEBUG_INTERSEC
+
+static inline BOOLEAN
+images_intersect (IMAGE_BOX *box1, IMAGE_BOX *box2, const RECT *rect)
+{
+ return TFB_DrawImage_Intersect (box1->FramePtr->image, box1->Box.corner,
+ box2->FramePtr->image, box2->Box.corner, rect);
+}
+
+static TIME_VALUE
+frame_intersect (INTERSECT_CONTROL *pControl0, RECT *pr0,
+ INTERSECT_CONTROL *pControl1, RECT *pr1, TIME_VALUE t0,
+ TIME_VALUE t1)
+{
+ SIZE time_error0, time_error1;
+ SIZE cycle0, cycle1;
+ SIZE dx_0, dy_0, dx_1, dy_1;
+ SIZE xincr0, yincr0, xincr1, yincr1;
+ SIZE xerror0, xerror1, yerror0, yerror1;
+ RECT r_intersect;
+ IMAGE_BOX IB0, IB1;
+ BOOLEAN check0, check1;
+
+ IB0.FramePtr = pControl0->IntersectStamp.frame;
+ IB0.Box.corner = pr0->corner;
+ IB0.Box.extent.width = GetFrameWidth (IB0.FramePtr);
+ IB0.Box.extent.height = GetFrameHeight (IB0.FramePtr);
+ IB1.FramePtr = pControl1->IntersectStamp.frame;
+ IB1.Box.corner = pr1->corner;
+ IB1.Box.extent.width = GetFrameWidth (IB1.FramePtr);
+ IB1.Box.extent.height = GetFrameHeight (IB1.FramePtr);
+
+ dx_0 = pr0->extent.width;
+ dy_0 = pr0->extent.height;
+ if (dx_0 >= 0)
+ xincr0 = 1;
+ else
+ {
+ xincr0 = -1;
+ dx_0 = -dx_0;
+ }
+ if (dy_0 >= 0)
+ yincr0 = 1;
+ else
+ {
+ yincr0 = -1;
+ dy_0 = -dy_0;
+ }
+ if (dx_0 >= dy_0)
+ cycle0 = dx_0;
+ else
+ cycle0 = dy_0;
+ xerror0 = yerror0 = cycle0;
+
+ dx_1 = pr1->extent.width;
+ dy_1 = pr1->extent.height;
+ if (dx_1 >= 0)
+ xincr1 = 1;
+ else
+ {
+ xincr1 = -1;
+ dx_1 = -dx_1;
+ }
+ if (dy_1 >= 0)
+ yincr1 = 1;
+ else
+ {
+ yincr1 = -1;
+ dy_1 = -dy_1;
+ }
+ if (dx_1 >= dy_1)
+ cycle1 = dx_1;
+ else
+ cycle1 = dy_1;
+ xerror1 = yerror1 = cycle1;
+
+ check0 = check1 = FALSE;
+ if (t0 <= 1)
+ {
+ time_error0 = time_error1 = 0;
+ if (t0 == 0)
+ {
+ ++t0;
+ goto CheckFirstIntersection;
+ }
+ }
+ else
+ {
+ SIZE delta;
+ COUNT start;
+ long error;
+
+ start = (COUNT)cycle0 * (COUNT)(t0 - 1);
+ time_error0 = start & ((1 << TIME_SHIFT) - 1);
+ if ((start >>= (COUNT)TIME_SHIFT) > 0)
+ {
+ if ((error = (long)xerror0
+ - (long)dx_0 * (long)start) > 0)
+ xerror0 = (SIZE)error;
+ else
+ {
+ delta = -(SIZE)(error / (long)cycle0) + 1;
+ IB0.Box.corner.x += xincr0 * delta;
+ xerror0 = (SIZE)(error + (long)cycle0 * (long)delta);
+ }
+ if ((error = (long)yerror0
+ - (long)dy_0 * (long)start) > 0)
+ yerror0 = (SIZE)error;
+ else
+ {
+ delta = -(SIZE)(error / (long)cycle0) + 1;
+ IB0.Box.corner.y += yincr0 * delta;
+ yerror0 = (SIZE)(error + (long)cycle0 * (long)delta);
+ }
+ pr0->corner = IB0.Box.corner;
+ }
+
+ start = (COUNT)cycle1 * (COUNT)(t0 - 1);
+ time_error1 = start & ((1 << TIME_SHIFT) - 1);
+ if ((start >>= (COUNT)TIME_SHIFT) > 0)
+ {
+ if ((error = (long)xerror1
+ - (long)dx_1 * (long)start) > 0)
+ xerror1 = (SIZE)error;
+ else
+ {
+ delta = -(SIZE)(error / (long)cycle1) + 1;
+ IB1.Box.corner.x += xincr1 * delta;
+ xerror1 = (SIZE)(error + (long)cycle1 * (long)delta);
+ }
+ if ((error = (long)yerror1
+ - (long)dy_1 * (long)start) > 0)
+ yerror1 = (SIZE)error;
+ else
+ {
+ delta = -(SIZE)(error / (long)cycle1) + 1;
+ IB1.Box.corner.y += yincr1 * delta;
+ yerror1 = (SIZE)(error + (long)cycle1 * (long)delta);
+ }
+ pr1->corner = IB1.Box.corner;
+ }
+ }
+
+ pControl0->last_time_val = pControl1->last_time_val = t0;
+ do
+ {
+ ++t0;
+ if ((time_error0 += cycle0) >= (1 << TIME_SHIFT))
+ {
+ if ((xerror0 -= dx_0) <= 0)
+ {
+ IB0.Box.corner.x += xincr0;
+ xerror0 += cycle0;
+ }
+ if ((yerror0 -= dy_0) <= 0)
+ {
+ IB0.Box.corner.y += yincr0;
+ yerror0 += cycle0;
+ }
+
+ check0 = TRUE;
+ time_error0 -= (1 << TIME_SHIFT);
+ }
+
+ if ((time_error1 += cycle1) >= (1 << TIME_SHIFT))
+ {
+ if ((xerror1 -= dx_1) <= 0)
+ {
+ IB1.Box.corner.x += xincr1;
+ xerror1 += cycle1;
+ }
+ if ((yerror1 -= dy_1) <= 0)
+ {
+ IB1.Box.corner.y += yincr1;
+ yerror1 += cycle1;
+ }
+
+ check1 = TRUE;
+ time_error1 -= (1 << TIME_SHIFT);
+ }
+
+ if (check0 || check1)
+ { /* if check0 && check1, this may not be quite right --
+ * if shapes had a pixel's separation to begin with
+ * and both moved toward each other, you would actually
+ * get a pixel overlap but since the last positions were
+ * separated by a pixel, the shapes wouldn't be touching
+ * each other.
+ */
+CheckFirstIntersection:
+ if (BoxIntersect (&IB0.Box, &IB1.Box, &r_intersect)
+ && images_intersect (&IB0, &IB1, &r_intersect))
+ return (t0);
+
+ if (check0)
+ {
+ pr0->corner = IB0.Box.corner;
+ pControl0->last_time_val = t0;
+ check0 = FALSE;
+ }
+ if (check1)
+ {
+ pr1->corner = IB1.Box.corner;
+ pControl1->last_time_val = t0;
+ check1 = FALSE;
+ }
+ }
+ } while (t0 <= t1);
+
+ return ((TIME_VALUE)0);
+}
+
+TIME_VALUE
+DrawablesIntersect (INTERSECT_CONTROL *pControl0,
+ INTERSECT_CONTROL *pControl1, TIME_VALUE max_time_val)
+{
+ SIZE dy;
+ SIZE time_y_0, time_y_1;
+ RECT r0, r1;
+ FRAME FramePtr0, FramePtr1;
+
+ if (!ContextActive () || max_time_val == 0)
+ return ((TIME_VALUE)0);
+ else if (max_time_val > MAX_TIME_VALUE)
+ max_time_val = MAX_TIME_VALUE;
+
+ pControl0->last_time_val = pControl1->last_time_val = 0;
+
+ r0.corner = pControl0->IntersectStamp.origin;
+ r1.corner = pControl1->IntersectStamp.origin;
+
+ r0.extent.width = pControl0->EndPoint.x - r0.corner.x;
+ r0.extent.height = pControl0->EndPoint.y - r0.corner.y;
+ r1.extent.width = pControl1->EndPoint.x - r1.corner.x;
+ r1.extent.height = pControl1->EndPoint.y - r1.corner.y;
+
+ FramePtr0 = pControl0->IntersectStamp.frame;
+ if (FramePtr0 == 0)
+ return(0);
+ r0.corner.x -= FramePtr0->HotSpot.x;
+ r0.corner.y -= FramePtr0->HotSpot.y;
+
+ FramePtr1 = pControl1->IntersectStamp.frame;
+ if (FramePtr1 == 0)
+ return(0);
+ r1.corner.x -= FramePtr1->HotSpot.x;
+ r1.corner.y -= FramePtr1->HotSpot.y;
+
+ dy = r1.corner.y - r0.corner.y;
+ time_y_0 = dy - GetFrameHeight (FramePtr0) + 1;
+ time_y_1 = dy + GetFrameHeight (FramePtr1) - 1;
+ dy = r0.extent.height - r1.extent.height;
+
+ if ((time_y_0 <= 0 && time_y_1 >= 0)
+ || (time_y_0 > 0 && dy >= time_y_0)
+ || (time_y_1 < 0 && dy <= time_y_1))
+ {
+ SIZE dx;
+ SIZE time_x_0, time_x_1;
+
+ dx = r1.corner.x - r0.corner.x;
+ time_x_0 = dx - GetFrameWidth (FramePtr0) + 1;
+ time_x_1 = dx + GetFrameWidth (FramePtr1) - 1;
+ dx = r0.extent.width - r1.extent.width;
+
+ if ((time_x_0 <= 0 && time_x_1 >= 0)
+ || (time_x_0 > 0 && dx >= time_x_0)
+ || (time_x_1 < 0 && dx <= time_x_1))
+ {
+ TIME_VALUE intersect_time;
+
+ if (dx == 0 && dy == 0)
+ time_y_0 = time_y_1 = 0;
+ else
+ {
+ SIZE t;
+ long time_beg, time_end, fract;
+
+ if (time_y_1 < 0)
+ {
+ t = time_y_0;
+ time_y_0 = -time_y_1;
+ time_y_1 = -t;
+ }
+ else if (time_y_0 <= 0)
+ {
+ if (dy < 0)
+ time_y_1 = -time_y_0;
+ time_y_0 = 0;
+ }
+ if (dy < 0)
+ dy = -dy;
+ if (dy < time_y_1)
+ time_y_1 = dy;
+ /* just to be safe, widen search area */
+ --time_y_0;
+ ++time_y_1;
+
+ if (time_x_1 < 0)
+ {
+ t = time_x_0;
+ time_x_0 = -time_x_1;
+ time_x_1 = -t;
+ }
+ else if (time_x_0 <= 0)
+ {
+ if (dx < 0)
+ time_x_1 = -time_x_0;
+ time_x_0 = 0;
+ }
+ if (dx < 0)
+ dx = -dx;
+ if (dx < time_x_1)
+ time_x_1 = dx;
+ /* just to be safe, widen search area */
+ --time_x_0;
+ ++time_x_1;
+
+#ifdef DEBUG_INTERSEC
+ log_add (log_Debug, "FramePtr0<%d, %d> --> <%d, %d>",
+ GetFrameWidth (FramePtr0), GetFrameHeight (FramePtr0),
+ r0.corner.x, r0.corner.y);
+ log_add (log_Debug, "FramePtr1<%d, %d> --> <%d, %d>",
+ GetFrameWidth (FramePtr1), GetFrameHeight (FramePtr1),
+ r1.corner.x, r1.corner.y);
+ log_add (log_Debug, "time_x(%d, %d)-%d, time_y(%d, %d)-%d",
+ time_x_0, time_x_1, dx, time_y_0, time_y_1, dy);
+#endif /* DEBUG_INTERSEC */
+ if (dx == 0)
+ {
+ time_beg = time_y_0;
+ time_end = time_y_1;
+ fract = dy;
+ }
+ else if (dy == 0)
+ {
+ time_beg = time_x_0;
+ time_end = time_x_1;
+ fract = dx;
+ }
+ else
+ {
+ long time_x, time_y;
+
+ time_x = (long)time_x_0 * (long)dy;
+ time_y = (long)time_y_0 * (long)dx;
+ time_beg = time_x < time_y ? time_y : time_x;
+
+ time_x = (long)time_x_1 * (long)dy;
+ time_y = (long)time_y_1 * (long)dx;
+ time_end = time_x > time_y ? time_y : time_x;
+
+ fract = (long)dx * (long)dy;
+ }
+
+ if ((time_beg <<= TIME_SHIFT) < fract)
+ time_y_0 = 0;
+ else
+ time_y_0 = (SIZE)(time_beg / fract);
+
+ if (time_end >= fract /* just in case of overflow */
+ || (time_end <<= TIME_SHIFT) >=
+ fract * (long)max_time_val)
+ time_y_1 = max_time_val - 1;
+ else
+ time_y_1 = (SIZE)((time_end + fract - 1) / fract) - 1;
+ }
+
+#ifdef DEBUG_INTERSEC
+ log_add (log_Debug, "start_time = %d, end_time = %d",
+ time_y_0, time_y_1);
+#endif /* DEBUG_INTERSEC */
+ if (time_y_0 <= time_y_1
+ && (intersect_time = frame_intersect (
+ pControl0, &r0, pControl1, &r1,
+ (TIME_VALUE)time_y_0, (TIME_VALUE)time_y_1)))
+ {
+ FramePtr0 = pControl0->IntersectStamp.frame;
+ pControl0->EndPoint.x = r0.corner.x + FramePtr0->HotSpot.x;
+ pControl0->EndPoint.y = r0.corner.y + FramePtr0->HotSpot.y;
+ FramePtr1 = pControl1->IntersectStamp.frame;
+ pControl1->EndPoint.x = r1.corner.x + FramePtr1->HotSpot.x;
+ pControl1->EndPoint.y = r1.corner.y + FramePtr1->HotSpot.y;
+
+ return (intersect_time);
+ }
+ }
+ }
+
+ return ((TIME_VALUE)0);
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-06 20:35:17 +0000