[PATCH 15/29] barriers: Replace complex intersection test with simpler math
Peter Hutterer
peter.hutterer at who-t.net
Tue Dec 11 23:19:08 PST 2012
From: "Jasper St. Pierre" <jstpierre at mecheye.net>
Since barriers are axis-aligned, we can do the intersection test with
simple interpolation rather than line-segment intersection. This also
helps us out in the future when we want the barriers to extend to be
rays and lines rather than just segments.
Signed-off-by: Jasper St. Pierre <jstpierre at mecheye.net>
---
Xi/xibarriers.c | 78 ++++++++++++++++++++-------------------------------------
1 file changed, 27 insertions(+), 51 deletions(-)
diff --git a/Xi/xibarriers.c b/Xi/xibarriers.c
index 2e7f2cc..a65d208 100644
--- a/Xi/xibarriers.c
+++ b/Xi/xibarriers.c
@@ -140,6 +140,9 @@ barrier_is_blocking_direction(const struct PointerBarrier * barrier,
return (barrier->directions & direction) != direction;
}
+#define T(v, a, b) (((float)v) - (a)) / ((b) - (a))
+#define F(t, a, b) ((t) * ((a) - (b)) + (a))
+
/**
* Test if the movement vector x1/y1 → x2/y2 is intersecting with the
* barrier. A movement vector with the startpoint or endpoint adjacent to
@@ -157,67 +160,40 @@ BOOL
barrier_is_blocking(const struct PointerBarrier * barrier,
int x1, int y1, int x2, int y2, double *distance)
{
- BOOL rc = FALSE;
- float ua, ub, ud;
- int dir = barrier_get_direction(x1, y1, x2, y2);
-
- /* Algorithm below doesn't handle edge cases well, hence the extra
- * checks. */
if (barrier_is_vertical(barrier)) {
- /* handle immediate barrier adjacency, moving away */
- if (dir & BarrierPositiveX && x1 == barrier->x1)
+ float t, y;
+ t = T(barrier->x1, x1, x2);
+ if (t < 0 || t > 1)
return FALSE;
- if (dir & BarrierNegativeX && x1 == (barrier->x1 - 1))
+
+ /* Edge case: moving away from barrier. */
+ if (x2 > x1 && t == 0)
return FALSE;
- /* startpoint adjacent to barrier, moving towards -> block */
- if (dir & BarrierPositiveX && x1 == (barrier->x1 - 1) && y1 >= barrier->y1 && y1 <= barrier->y2) {
- *distance = 0;
- return TRUE;
- }
- if (dir & BarrierNegativeX && x1 == barrier->x1 && y1 >= barrier->y1 && y1 <= barrier->y2) {
- *distance = 0;
- return TRUE;
- }
+
+ y = F(t, y1, y2);
+ if (y < barrier->y1 || y > barrier->y2)
+ return FALSE;
+
+ *distance = sqrt((pow(y - y1, 2) + pow(barrier->x1 - x1, 2)));
+ return TRUE;
}
else {
- /* handle immediate barrier adjacency, moving away */
- if (dir & BarrierPositiveY && y1 == barrier->y1)
+ float t, x;
+ t = T(barrier->y1, y1, y2);
+ if (t < 0 || t > 1)
return FALSE;
- if (dir & BarrierNegativeY && y1 == (barrier->y1 - 1))
- return FALSE;
- /* startpoint adjacent to barrier, moving towards -> block */
- if (dir & BarrierPositiveY && y1 == (barrier->y1 - 1) && x1 >= barrier->x1 && x1 <= barrier->x2) {
- *distance = 0;
- return TRUE;
- }
- if (dir & BarrierNegativeY && y1 == barrier->y1 && x1 >= barrier->x1 && x1 <= barrier->x2) {
- *distance = 0;
- return TRUE;
- }
- }
- /* not an edge case, compute distance */
- ua = 0;
- ud = (barrier->y2 - barrier->y1) * (x2 - x1) - (barrier->x2 -
- barrier->x1) * (y2 - y1);
- if (ud != 0) {
- ua = ((barrier->x2 - barrier->x1) * (y1 - barrier->y1) -
- (barrier->y2 - barrier->y1) * (x1 - barrier->x1)) / ud;
- ub = ((x2 - x1) * (y1 - barrier->y1) -
- (y2 - y1) * (x1 - barrier->x1)) / ud;
- if (ua < 0 || ua > 1 || ub < 0 || ub > 1)
- ua = 0;
- }
+ /* Edge case: moving away from barrier. */
+ if (y2 > y1 && t == 0)
+ return FALSE;
- if (ua > 0 && ua <= 1) {
- double ix = barrier->x1 + ua * (barrier->x2 - barrier->x1);
- double iy = barrier->y1 + ua * (barrier->y2 - barrier->y1);
+ x = F(t, x1, x2);
+ if (x < barrier->x1 || x > barrier->x2)
+ return FALSE;
- *distance = sqrt(pow(x1 - ix, 2) + pow(y1 - iy, 2));
- rc = TRUE;
+ *distance = sqrt((pow(x - x1, 2) + pow(barrier->y1 - y1, 2)));
+ return TRUE;
}
-
- return rc;
}
#define HIT_EDGE_EXTENTS 2
--
1.8.0.1
More information about the xorg-devel
mailing list