libsdl-org
SDL_FRect off-by-one bugs
SDL_IntersectFRectAndLine calculates the wrong answer in the following example:
SDL_FRect fr = { 2.5f, 1.5f, 15.25f, 12.0f };
float x1 = 5.0f, y1 = 6.0f, x2 = 23.0f, y2 = 6.0f;
SDL_IntersectFRectAndLine(&fr, &x1, &y1, &x2, &y2);
printf("clipped line %f, %f, %f, %f\n", x1, y1, x2, y2);
produces the output
clipped line 5.000000, 6.000000, 16.750000, 6.000000
The value of x2 in the result should be 17.75, not 16.75.
Using SDL2-2.26.1 on Windows.
I think this is ok. you're intersecting an horizontal line. on the x range, the rect starts at 2.5f, and measure 15.25f. size of pixel is 1. so it ends at 17.75f, but the last pixel is a 16.75f
You may be right - but in that case, there is a bug in SDL_PointInFRect:
SDL_FRect fr = { 2.5f, 1.5f, 15.25f, 12.0f };
SDL_FPoint fp = { 17.5f, 6.0f };
printf("point %s in rect\n", SDL_PointInFRect(&fp, &fr) ? "" : "not");
produces the output
point in rect
These functions can't both be working correctly. The point (17.5, 6.0) is on the line. It is also in the rect (according to SDL_PointInFRect). But it is not in the intersection of the line and the rect (according to SDL_IntersectFRectAndLine).
My understanding of how FRects work is that they include all points (a,b) with x <= a < x+w and y <= b < y+h -- which would mean the bug here is the SDL_IntersectFRectAndLine one originally reported.
Here's another instance of the bug, in which the behaviour is obviously wrong:
SDL_FRect fr = { 2.5f, 1.5f, 0.25f, 12.0f };
float x1 = 0.0f, y1 = 6.0f, x2 = 23.0f, y2 = 6.0f;
SDL_IntersectFRectAndLine(&fr, &x1, &y1, &x2, &y2);
printf("clipped line %f, %f, %f, %f\n", x1, y1, x2, y2);
produces the output
clipped line 2.500000, 6.000000, 1.750000, 6.000000
The intersection of the line and the rect lies almost entirely outside the rect (according to SDL_IntersectFRectAndLine).
(BTW, in both this example and the original one SDL_IntersectFRectAndLine returns true, indicating a non-empty intersection.)
As you said,
The point (17.5, 6.0) is on the line. It is also in the rect (according to SDL_PointInFRect). But it is not in the intersection of the line and the rect (according to SDL_IntersectFRectAndLine).
is a surprising result.
thinking about it, it sounds like
"line intersect rect" isn't the same as "rect intersect line".
"a intersect b", cant be read as "select the point of a, that are also very close to b.
SDL_PointInFRect is somehow a "point intersect rect", which will return the "point" when true. but "rect intersect point" would return a different point.
So this may be explained with: SDL_PointInFRect: this is a point intersect rect. and then you use a "rect intersect line" ... so this add hopefully some sense to the initial sentence
... there is a big mess here :)
I looked at the source code. The int and float versions of the rectangle functions use the same code: the file SDL_rect_impl.h is #included twice, once to generate the Rect functions and then again to generate the FRect functions.
The problem seems to be this. A rect (either kind, int or float) { x, y, w, h } consists of those points { a, b } satisfying x <= a < x+w and y <= b < y+h. In some places the code assumes that these inequalities are equivalent to x <= a <= x+w-1 and y <= b <= y+h-1, which is correct for ints but not for floats.
Another place where this causes a bug is in SDL_EncloseFPoints:
SDL_FPoint fpts[3] = { { 1.25f, 2.5f }, { 1.75f, 3.75f }, { 3.5f, 3.0f } };
int count = 3;
SDL_FRect clip = { 0.0f, 1.0f, 4.0f, 4.0f };
SDL_FRect result;
SDL_EncloseFPoints(fpts, count, &clip, &result);
printf("enclosing rectangle: %f %f %f %f\n", result.x, result.y, result.w, result.h);
for(int i=0; i != count; i++)
printf("%f, %f is %sin the clip rect and %sin the enclosing rect\n", fpts[i].x, fpts[i].y,
SDL_PointInFRect(&fpts[i], &clip) ? "" : "not ",
SDL_PointInFRect(&fpts[i], &result) ? "" : "not ");
which produces the output
enclosing rectangle: 1.250000 2.500000 1.500000 2.250000
1.250000, 2.500000 is in the clip rect and in the enclosing rect
1.750000, 3.750000 is in the clip rect and in the enclosing rect
3.500000, 3.000000 is in the clip rect and not in the enclosing rect
The enclosing rect (found by SDL_EncloseFPoints) does not contain (according to SDL_PointInFRect) one of the points it is meant to be enclosing.
Are we just looking for something like this? I feel like there's a ton of corner cases we need to watch out for if we change this, so I want to make sure this meets all conditions before we do.
diff --git a/src/video/SDL_rect_impl.h b/src/video/SDL_rect_impl.h
index 4b8713c37..deb743bf8 100644
--- a/src/video/SDL_rect_impl.h
+++ b/src/video/SDL_rect_impl.h
@@ -190,8 +190,8 @@ SDL_bool SDL_ENCLOSEPOINTS(const POINTTYPE *points, int count, const RECTTYPE *c
SDL_bool added = SDL_FALSE;
const SCALARTYPE clip_minx = clip->x;
const SCALARTYPE clip_miny = clip->y;
- const SCALARTYPE clip_maxx = clip->x + clip->w - 1;
- const SCALARTYPE clip_maxy = clip->y + clip->h - 1;
+ const SCALARTYPE clip_maxx = clip->x + clip->w;
+ const SCALARTYPE clip_maxy = clip->y + clip->h;
/* Special case for empty rectangle */
if (SDL_RECTEMPTY(clip)) {
@@ -202,8 +202,8 @@ SDL_bool SDL_ENCLOSEPOINTS(const POINTTYPE *points, int count, const RECTTYPE *c
x = points[i].x;
y = points[i].y;
- if (x < clip_minx || x > clip_maxx ||
- y < clip_miny || y > clip_maxy) {
+ if (x < clip_minx || x >= clip_maxx ||
+ y < clip_miny || y >= clip_maxy) {
continue;
}
if (!added) {
That looks like the right approach.
But there is a tricky issue at the end of SDL_ENCLOSEPOINTS: having determined that the smallest and greatest x-coordinates of the points are minx and maxx respectively, we need to set result->x to minx and result->w to a value just great enough that maxx < minx + result->w. Similarly for the y-coordinates.
For ints, the current code does it correctly:
result->w = (maxx - minx) + 1;
For floats, a different solution is needed. I think this works:
result->w = nextafterf(maxx, maxx + 1.0f) - nextafterf(minx, minx - 1.0f);
(Note that
result->w = nextafterf(maxx - minx, maxx - minx + 1.0f)
wouldn't do it, because e.g. 601.0f < 600.0f + nextafterf(1.0f, 2.0f) evaluates to false.)
The following code produces no output.
SDL_FRect result;
float h = 1.0f/128.0f;
for(float xmin = -1024.0f; xmin <= 1024.0f; xmin += h)
for(float xmax = xmin; xmax <= 1024.0f; xmax += h)
{
result.x = xmin;
result.w = nextafterf(xmax, xmax + 1.0f) - nextafterf(xmin, xmin - 1.0f);
if( !(xmax < result.x + result.w) )
printf("enclosing rect too small, it doesn't contain x = %.7f\n", xmax);
float x = xmax + 1.0f/4096.0f;
if( x < result.x + result.w )
printf("enclosing rect too large, it contains x = %.12f\n", x);
}
This seems to be a good solution for floats of magnitude typical for pixel coordinates (1 to 1024),
I hope this isn't oversimplifying the problem, but now I have the w and h calculated the same way and then bumped out by an epsilon value (1 for integers, SDL_FLT_EPSILON for floats)...I think this satisfies the conditions?
(SDL_FLT_EPSILON looks like this, in the headers:
#ifdef FLT_EPSILON
#define SDL_FLT_EPSILON FLT_EPSILON
#else
#define SDL_FLT_EPSILON 1.1920928955078125e-07F /* 0x0.000002p0 */
#endif
)
diff --git a/src/video/SDL_rect.c b/src/video/SDL_rect.c
index 1b461d230..5f4d5d2bb 100644
--- a/src/video/SDL_rect.c
+++ b/src/video/SDL_rect.c
@@ -90,6 +90,7 @@ SDL_bool SDL_GetSpanEnclosingRect(int width, int height,
#define POINTTYPE SDL_Point
#define SCALARTYPE int
#define COMPUTEOUTCODE ComputeOutCode
+#define ENCLOSEPOINTS_EPSILON 1
#define SDL_HASINTERSECTION SDL_HasIntersection
#define SDL_INTERSECTRECT SDL_IntersectRect
#define SDL_RECTEMPTY SDL_RectEmpty
@@ -102,6 +103,7 @@ SDL_bool SDL_GetSpanEnclosingRect(int width, int height,
#define POINTTYPE SDL_FPoint
#define SCALARTYPE float
#define COMPUTEOUTCODE ComputeOutCodeF
+#define ENCLOSEPOINTS_EPSILON SDL_FLT_EPSILON
#define SDL_HASINTERSECTION SDL_HasIntersectionF
#define SDL_INTERSECTRECT SDL_IntersectFRect
#define SDL_RECTEMPTY SDL_FRectEmpty
diff --git a/src/video/SDL_rect_impl.h b/src/video/SDL_rect_impl.h
index b0e3901b1..7504b8956 100644
--- a/src/video/SDL_rect_impl.h
+++ b/src/video/SDL_rect_impl.h
@@ -192,8 +192,8 @@ SDL_bool SDL_ENCLOSEPOINTS(const POINTTYPE *points, int count, const RECTTYPE *c
SDL_bool added = SDL_FALSE;
const SCALARTYPE clip_minx = clip->x;
const SCALARTYPE clip_miny = clip->y;
- const SCALARTYPE clip_maxx = clip->x + clip->w - 1;
- const SCALARTYPE clip_maxy = clip->y + clip->h - 1;
+ const SCALARTYPE clip_maxx = clip->x + clip->w;
+ const SCALARTYPE clip_maxy = clip->y + clip->h;
/* Special case for empty rectangle */
if (SDL_RECTEMPTY(clip)) {
@@ -204,8 +204,8 @@ SDL_bool SDL_ENCLOSEPOINTS(const POINTTYPE *points, int count, const RECTTYPE *c
x = points[i].x;
y = points[i].y;
- if (x < clip_minx || x > clip_maxx ||
- y < clip_miny || y > clip_maxy) {
+ if (x < clip_minx || x >= clip_maxx ||
+ y < clip_miny || y >= clip_maxy) {
continue;
}
if (!added) {
@@ -264,8 +264,8 @@ SDL_bool SDL_ENCLOSEPOINTS(const POINTTYPE *points, int count, const RECTTYPE *c
if (result) {
result->x = minx;
result->y = miny;
- result->w = (maxx - minx) + 1;
- result->h = (maxy - miny) + 1;
+ result->w = (maxx - minx) + ENCLOSEPOINTS_EPSILON;
+ result->h = (maxy - miny) + ENCLOSEPOINTS_EPSILON;
}
return SDL_TRUE;
}
@@ -430,6 +430,7 @@ SDL_bool SDL_INTERSECTRECTANDLINE(const RECTTYPE *rect, SCALARTYPE *X1, SCALARTY
#undef POINTTYPE
#undef SCALARTYPE
#undef COMPUTEOUTCODE
+#undef ENCLOSEPOINTS_EPSILON
#undef SDL_HASINTERSECTION
#undef SDL_INTERSECTRECT
#undef SDL_RECTEMPTY
If this feels right, I'll push to revision control!
That seems like the right general approach. But for the calculation in the floating-point case, it is not enough to just let the epsilon value be SDL_FLT_EPSILON, or any other constant.
In floating-point, larger numbers are represented with less precision - they have fewer digits after the binary point. So, for example (I tried this just now), 1.0f + SDL_FLT_EPSILON > 1.0f evaluates to true, but 2.0f + SDL_FLT_EPSILON > 2.0f evaluates to false, because SDL_FLT_EPSILON is too small to make any difference when added to a number as big as 2.
This means that the size of the epsilon value that needs to be added depends on the magnitude of the floats involved. Instead of a constant that is #defineed differently in the int and float cases, perhaps there should be a function or macro? Something like
/* int version */
int span(int minx, int maxx)
{
return maxx - minx + 1;
}
/* float version */
float span(float minx, float maxx)
{
return nextafterf(xmax, xmax + 1.0f) - nextafterf(xmin, xmin - 1.0f);
}
The nextafterf function deals with the varying-magnitude problem by always adding an epsilon of appropriate size. Note that we don't know a priori which of xmin and xmax has the larger magnitude, because xmin could be negative.
Whatever the resolution is for this, we should add test cases to testautomation to make sure we have fixed the issues and can regression test in the future.
Ugh, floating point is the worst.
This seems kinda inefficient, and we'll have to wire a nextafterf implementation into our C runtime support, but it is what it is.
I'll mess with this shortly and close this out.
My hero! I saw the nextafterf commit, and it looked like a lot of work.
Do you want me to finish this bug with it, or are you still going?
Here's my first attempt, using the same logic as integer rects, where the area inside the rectangle includes the topleft corner and does not include the bottom right corner. I'm also not completely convinced this representation of rectangle is correct, so feedback welcome!
I don't think this covers all the intersection cases correctly and may regress the integer versions, so eyes on this are appreciated!
Another way of looking at this is what is the floating point rectangle that encloses 0,0? Is it { 0, 0, 0, 0 } or { 0, 0, epsilon, epsilon }?
Either way, I think we'll need to review all of the 2D renderer code that converts input coordinates from int to float and then does clipping on them, and this isn't safe for 2.28.
So I talked to some smart people, and the trick is that clipping is done mathematically correct, but lines are rendered such that they don't draw the final pixel so they don't overlap into the edge of the clipping rectangle. (BTW, @icculus this is why we had such problems rendering lines exactly the way we wanted them)
This has pretty significant implications for passing floating point values to the 2D rendering API, so I'm going to hold off on this until we have a chance to look through this more carefully.
On the up side, it means we don't need nextafterf() 😄
So... I'm coming back to this, and I'm changing SDL floating point rectangles to be mathematically correct.
- A floating point rectangle contains all points >= x and <= x + w
- A floating point rectangle is only empty if it has negative width. The zero rectangle contains the zero point.
- Adjacent floating point rectangles intersect along their shared side
This has pretty striking implications for the software renderer, so I'll have to work through those.
However, it does mean that all the examples listed here work the way you'd expect:
{
SDL_FRect fr = { 2.5f, 1.5f, 15.25f, 12.0f };
float x1 = 5.0f, y1 = 6.0f, x2 = 23.0f, y2 = 6.0f;
SDL_GetRectAndLineIntersectionFloat(&fr, &x1, &y1, &x2, &y2);
SDL_Log("clipped line %f, %f, %f, %f\n", x1, y1, x2, y2);
}
{
SDL_FRect fr = { 2.5f, 1.5f, 15.25f, 12.0f };
SDL_FPoint fp = { 17.5f, 6.0f };
SDL_Log("point %sin rect\n", SDL_PointInRectFloat(&fp, &fr) ? "" : "not ");
}
{
SDL_FRect fr = { 2.5f, 1.5f, 0.25f, 12.0f };
float x1 = 0.0f, y1 = 6.0f, x2 = 23.0f, y2 = 6.0f;
SDL_GetRectAndLineIntersectionFloat(&fr, &x1, &y1, &x2, &y2);
SDL_Log("clipped line %f, %f, %f, %f\n", x1, y1, x2, y2);
}
{
SDL_FPoint fpts[3] = { { 1.25f, 2.5f }, { 1.75f, 3.75f }, { 3.5f, 3.0f } };
int count = 3;
SDL_FRect clip = { 0.0f, 1.0f, 4.0f, 4.0f };
SDL_FRect result;
SDL_GetRectEnclosingPointsFloat(fpts, count, &clip, &result);
SDL_Log("enclosing rectangle: %f %f %f %f\n", result.x, result.y, result.w, result.h);
for (int i = 0; i != count; i++)
SDL_Log("%f, %f is %sin the clip rect and %sin the enclosing rect\n", fpts[i].x, fpts[i].y,
SDL_PointInRectFloat(&fpts[i], &clip) ? "" : "not ",
SDL_PointInRectFloat(&fpts[i], &result) ? "" : "not ");
}
Gives the output:
INFO: clipped line 5.000000, 6.000000, 17.750000, 6.000000
INFO: point in rect
INFO: clipped line 2.500000, 6.000000, 2.750000, 6.000000
INFO: enclosing rectangle: 1.250000 2.500000 2.250000 1.250000
INFO: 1.250000, 2.500000 is in the clip rect and in the enclosing rect
INFO: 1.750000, 3.750000 is in the clip rect and in the enclosing rect
INFO: 3.500000, 3.000000 is in the clip rect and in the enclosing rect