Invalid polygon

Yirkash · March 17, 2021, 3:57pm

Good afternoon,

I’m building some polygons to procedurally draw some stairs, and sometimes I get an invalid polygon message:

WARNING: Polygon could not be generated. The polygon outline is invalid, possibly due to holes or self-intersection.

I’ve read quite a bit about the subject, trying to find the problem. Since the polygons were being procedurally generated, I printed out some of the list of vertices, so I could reliably replicate the problem. I managed to get a set of vertexes that consistently gave the error, but there weren’t any duplicate vertices or intersecting lines. Moreover, I tried removing vertices one by one, and some vertices would remove the warning when missing (though you could remove any one of those, and the others would no longer be offenders).

In any case, I’m running out of ideas of how or why this polygon is breaking, so I thought I’d post here and see if anybody could see what’s wrong.

This polygon will draw:

vertices = {
    0, -10.164,
    30.8, -10.164,
    30.8, -20.328,
    61.6, -20.328,
    61.6, -30.492,
    92.4, -30.492,
    92.4, -40.656,
    123.2, -40.656,
    123.2, -50.82,
    154, -50.82,
    154, -60.984,
    184.8, -60.984,
    184.8, -71.148,
    215.6, -71.148,
    215.6, -81.312,
    246.4, -81.312,
    246.4, -91.476,
    277.2, -91.476,
    277.2, -101.64,
    308, -101.64,
    308, -111.804,
    338.8, -111.804,
    338.8, -121.968,
    369.6, -121.968,
    369.6, -132.132,
    400.4, -132.132,
    400.4, -142.296,
    431.2, -142.296,
    431.2, -152.46,
    462, -152.46,
    462, -162.624,
    492.8, -162.624,
    --492.8, -172.788,
    --523.6, -172.788,
    523.6, 1080,
    0, 1080,
}

local newPoly = display.newPolygon( display.contentCenterX, display.contentCenterY, vertices )
newPoly.anchorY = 0

This, on the other hand, will not.

vertices = {
    0, -10.164,
    30.8, -10.164,
    30.8, -20.328,
    61.6, -20.328,
    61.6, -30.492,
    92.4, -30.492,
    92.4, -40.656,
    123.2, -40.656,
    123.2, -50.82,
    154, -50.82,
    154, -60.984,
    184.8, -60.984,
    184.8, -71.148,
    215.6, -71.148,
    215.6, -81.312,
    246.4, -81.312,
    246.4, -91.476,
    277.2, -91.476,
    277.2, -101.64,
    308, -101.64,
    308, -111.804,
    338.8, -111.804,
    338.8, -121.968,
    369.6, -121.968,
    369.6, -132.132,
    400.4, -132.132,
    400.4, -142.296,
    431.2, -142.296,
    431.2, -152.46,
    462, -152.46,
    462, -162.624,
    492.8, -162.624,
    492.8, -172.788,
    523.6, -172.788,
    523.6, 1080,
    0, 1080,
}

local newPoly = display.newPolygon( display.contentCenterX, display.contentCenterY, vertices )
newPoly.anchorY = 0

And once again, this one will draw.

vertices = {
    0, -10.164,
    30.8, -10.164,
    --30.8, -20.328,
    --61.6, -20.328,
    --61.6, -30.492,
    --92.4, -30.492,
    --92.4, -40.656,
    --123.2, -40.656,
    --123.2, -50.82,
    --154, -50.82,
    154, -60.984,
    184.8, -60.984,
    184.8, -71.148,
    215.6, -71.148,
    215.6, -81.312,
    246.4, -81.312,
    246.4, -91.476,
    277.2, -91.476,
    277.2, -101.64,
    308, -101.64,
    308, -111.804,
    338.8, -111.804,
    338.8, -121.968,
    369.6, -121.968,
    369.6, -132.132,
    400.4, -132.132,
    400.4, -142.296,
    431.2, -142.296,
    431.2, -152.46,
    462, -152.46,
    462, -162.624,
    492.8, -162.624,
    492.8, -172.788,
    523.6, -172.788,
    523.6, 1080,
    0, 1080,
}

local newPoly = display.newPolygon( display.contentCenterX, display.contentCenterY, vertices )
newPoly.anchorY = 0

For clarity’s sake, I’ve commented out vertices instead of removing them, so it’s more obvious what has been removed in each case.

To make it even more baffling, it also draws correctly if I leave all points in place, but reduce the vertical height of the polygon by making the last two vertices have 359 instead of 1080 as the y coordinate.

523.6, 359,
0, 359,

Now I feel I might be missing something incredibly obvious, but I’m at a loss at to where else to look or what more to consider. Any help would be really appreciated.

Thanks in advance!

roaminggamer · March 18, 2021, 12:29am

Can you post the settings used in cofig.lua and tell us what simulated device you’re using?

Meanwhile.

I would pre-parse any points table and use integer values.
(Maybe) Depending upon the settings in config.lua and the scaling you end up using, one or more of your points may end up in the same position, which I think is wrong.
To get better help in the future (for anything ambiguous), if you can, please supply a fully runnable mini-project so others can download it and run it. It puts us all on the same page and saves folks who want to help a lot of effort.

Here is a sample that reproduces your error, then resolves it by rounding all of the values to integers.

https://github.com/roaminggamer/RG_FreeStuff/raw/master/AskEd/2021/03/polygon_help.zip

My best guess is that by passing in floats, you ran into an issue where a segment doubled back on itself or (nearly) crossed a prior segment.

Yirkash · March 18, 2021, 9:20am

Thanks for the prompt reply. Here’s my config.lua contents. I’ve tried with all three scaling methods (letterbox, zoomEven and adaptive), and it didn’t make any difference.

application =
{
    content =
    {
        width = 640,
        height = 960, 
        scale = "letterbox",
        fps = 60,
    },
}

I’m using the Samsung Galaxy S5 (1080x1920) simulated device. But I’ve tried it on several other simulated devices (both Android and iOS) with the same results.

And finally, here’s a mini-project that reproduces the problem. I’ll make sure to include one in any future posts, thanks for the tip.

PolygonTest (zip file, 68Kb)

I’ll try rounding values, and let you know how that comes up.

Thanks a lot for your help!

Edited to add that rounding indeed fixed the problem, with minimal visual effect!

XeduR · March 18, 2021, 4:02pm

This is a particularly weird one indeed.

It also starts working if you just comment out a specific individual vertex, like {215.6, -71.148} or different groups of two vertices.

I’ve worked a lot with polygons and if I’d have to guess, I’d lean towards @roaminggamer’s suggestion of floats messing things up, though I’m not sure how or why that’d happen.

Yirkash · March 19, 2021, 8:05am

Indeed rounding the values solved the problem, but I’m still rather surprised it did. I mean, I would think it’d be easier for two vertices to end up in the same coordinates if their values are rounded, right? But the empyrical truth is, the problem disappeared once rounded. My best guess would be that there might be some underlying issue with floating point math, but I’m obviously just wild guessing.

Anyway, for anybody that might find this thread in the future, the fix for me was rounding the values.

XeduR · March 19, 2021, 1:08pm

Yeah, the weird thing is that it should, at least theoretically, treat the exact same floating point numbers the same, but it’s probably handling them differently, causing a segment to double back on itself like roaminggamer suggested.

I’m not sure how the polygons are created in Solar2D, but it might be the case that the vertices are drawn in a loop where the next one’s position is dependent on the previous one. Floating point numbers behave very strangely with decimals. For instance, the code below should always print out the current iteration, i, and 0 (zero we are dividing the iteration by the increment), however, the remainder goes off the rails pretty quick.

local step = 0.01
for i = 0, 0.5, step do
    print( i, i%step )
end

-- output is:
15:01:02.873  0	0
15:01:02.873  0.01	0
15:01:02.873  0.02	0
15:01:02.873  0.03	0
15:01:02.873  0.04	0
15:01:02.873  0.05	0
15:01:02.873  0.06	6.9388939039072e-18
15:01:02.873  0.07	0
15:01:02.873  0.08	0
15:01:02.873  0.09	0
15:01:02.873  0.1	0.01
15:01:02.873  0.11	0.01
15:01:02.873  0.12	0.01
15:01:02.873  0.13	0.01
15:01:02.873  0.14	0.01
15:01:02.873  0.15	0
15:01:02.873  0.16	0
15:01:02.873  0.17	0
15:01:02.873  0.18	2.7755575615629e-17
15:01:02.873  0.19	2.7755575615629e-17
15:01:02.873  0.2	2.7755575615629e-17
15:01:02.873  0.21	5.5511151231258e-17
15:01:02.873  0.22	5.5511151231258e-17
15:01:02.873  0.23	5.5511151231258e-17
15:01:02.873  0.24	8.3266726846887e-17
15:01:02.873  0.25	5.5511151231258e-17
15:01:02.873  0.26	5.5511151231258e-17
15:01:02.873  0.27	5.5511151231258e-17
15:01:02.873  0.28	5.5511151231258e-17
15:01:02.873  0.29	1.1102230246252e-16
15:01:02.873  0.3	1.1102230246252e-16
15:01:02.873  0.31	1.1102230246252e-16
15:01:02.873  0.32	1.1102230246252e-16
15:01:02.873  0.33	1.1102230246252e-16
15:01:02.873  0.34	1.1102230246252e-16
15:01:02.873  0.35	1.1102230246252e-16
15:01:02.873  0.36	1.6653345369377e-16
15:01:02.873  0.37	1.6653345369377e-16
15:01:02.873  0.38	1.6653345369377e-16
15:01:02.873  0.39	1.6653345369377e-16
15:01:02.873  0.4	1.6653345369377e-16
15:01:02.873  0.41	1.6653345369377e-16
15:01:02.873  0.42	2.2204460492503e-16
15:01:02.873  0.43	2.2204460492503e-16
15:01:02.873  0.44	2.2204460492503e-16
15:01:02.873  0.45	2.2204460492503e-16
15:01:02.873  0.46	2.2204460492503e-16
15:01:02.873  0.47	2.2204460492503e-16
15:01:02.873  0.48	2.7755575615629e-16
15:01:02.873  0.49	2.7755575615629e-16

So, if the polygon gets messed up because of something like this, then we should add a gotcha to the documentation concerning this. The best solution would naturally be to have the engine floor/round the numbers, if something like this can occur.

Yirkash · March 19, 2021, 3:19pm

Just for the sake of completeness, here’s an excerpt of the code that generates the vertices:

local function getStairVertices (drop, width)
    local numSteps = math.ceil( width / 32 )
    local stepDrop, stepWidth = drop / numSteps, width / numSteps
    local vertices = {}
    for i=1, numSteps do
        -- ------ Start of horizontal step
        vertices[#vertices+1] = (i-1) * stepWidth
        vertices[#vertices+1] = i * stepDrop
        -- ------ End of horizontal step
        vertices[#vertices+1] = i * stepWidth
        vertices[#vertices+1] = i * stepDrop
    end
    -- ------ Lower right corner
    vertices[#vertices+1] = numSteps * stepWidth
    vertices[#vertices+1] = display.contentHeight * 3
    -- ------ Lower left corner
    vertices[#vertices+1] = 0
    vertices[#vertices+1] = display.contentHeight * 3
    
    return vertices
end

local vertices = getStairVertices(-172.788, 523.6)

I didn’t think it was necessary, since the vertices that I provided in the first post were already causing trouble, and there were no duplicate points. But here it is nonetheless, for what it’s worth.

And here’s the version that rounds the values, which works:

local function getStairVertices (drop, width)
    local numSteps = math.ceil( width / 32 )
    local stepDrop, stepWidth = drop / numSteps, width / numSteps
    local vertices = {}
    for i=1, numSteps do
        -- ------ Start of horizontal step
        vertices[#vertices+1] = math.round( (i-1) * stepWidth )
        vertices[#vertices+1] = math.round( i * stepDrop )
        -- ------ End of horizontal step
        vertices[#vertices+1] = math.round( i * stepWidth )
        vertices[#vertices+1] = math.round( i * stepDrop )
    end
    -- ------ Lower right corner
    vertices[#vertices+1] = math.round( numSteps * stepWidth )
    vertices[#vertices+1] = display.contentHeight * 3
    -- ------ Lower left corner
    vertices[#vertices+1] = 0
    vertices[#vertices+1] = display.contentHeight * 3
    
    return vertices
end

local vertices = getStairVertices(-172.788, 523.6)