HardonCollider: Polygon incompatible with triangulation

[Golan2781]

Hi!
I'm currently trying to get HardonCollider to work properly with collision shapes supplied from an external map source(Tiled). The problem is that many of the shapes created for collision detection in the editor are not reliably compatible with the Kong algorithm used to subdivide the polygon into triangles. While collinear points are discarded when the polygon is first passed to the shape constructor, many of my shapes end up with collinear points during the triangulation process (see the attached sketch) causing the process to fail when trying to convert these invalid triangles to shapes (all three vertices get discarded, creating an empty shape).

Now, the easiest solution would of course be not to use such shapes, but they are simply the most practical solution for the mapping part. I've got some basic ideas to address the issue (discard invalid triangles, discard points with adjacent collinear points, reinitialise the remaining polygon every step) but I've got almost no experience with such algorithms so I'd probably break something or take a very inefficient approach. Any help and tips on how to do this efficiently would be greatly appreciated! Thanks in advance!

[MarekkPie]

All this talk about Hardon is getting me horny.

[gfreak]

All this talk about Hardon is getting me horny.

o_O

[Jasoco]

All this talk about pie is making me hungy.

But this thread isn't about food. It's about a problem. Hopefully someone who actually knows the answer will post.

[vrld]

This appears to be a bug with HardonCollider. You can fix it by changing the function pointInTriangle() in polygon.lua to:

Code: Select all

local function pointInTriangle(q, p1,p2,p3)
    local v1,v2 = p2 - p1, p3 - p1
    local qp = q - p1
    local dv = v1:cross(v2)
    local l = qp:cross(v2)
    if l < 0 then return false end
    local m = v1:cross(qp)
    if m < 0 then return false end
    return (l+m)/dv < 1
end

I will upload a fixed version soon.

[Golan2781]

Thanks for the reply and help!
With the updated pointInTriangle, it now fails the assert stating "Cannot triangulate polygon (is the polygon intersecting itself?)". I guess it simply ends up with the last three points all in a row, then tries to triangulate these until it fails.

I've fixed it for now by adding a check in the main loop to discard the current point if it is collinear with its directly adjacent points. If I'm not mistaken, this should merely simplify the polygon, not discard any otherwise needed information. This also works with the original pointInTriangle function.

Code: Select all

	local nPoints, skipped = #vertices, 0
	local p = adj[ vertices[2] ]
	while nPoints > 3 do
		-- discard collinear
		if areCollinear(p.l, p.p, p.r) then
			adj[p.p] = nil
			adj[p.l].r = p.r
			adj[p.r].l = p.l
			nPoints = nPoints - 1
			skipped = 0
			p = adj[p.l]
		-- triangulate of vertex is valid
		elseif not concave[p.p] and isEar(p.l, p.p, p.r) then
			triangles[#triangles+1] = Polygon( unpackHelper(p.l, p.p, p.r) )
			if concave[p.l] and ccw(adj[p.l].l, p.l, p.r) then
				concave[p.l] = nil
			end
			if concave[p.r] and ccw(p.l, p.r, adj[p.r].r) then
				concave[p.r] = nil
			end
			-- remove point from list
			adj[p.p] = nil
			adj[p.l].r = p.r
			adj[p.r].l = p.l
			nPoints = nPoints - 1
			skipped = 0
			p = adj[p.l]
		else
			p = adj[p.r]
			skipped = skipped + 1
			assert(skipped <= nPoints, "Cannot triangulate polygon (is the polygon intersecting itself?)")
		end
	end
	triangles[#triangles+1] = Polygon( unpackHelper(p.l, p.p, p.r) )

The polygon I'm operating on is:

Code: Select all

            { x = 0, y = 0 },
            { x = -32, y = 0 },
            { x = -32, y = 96 },
            { x = -320, y = 96 },
            { x = -320, y = 128 },
            { x = -160, y = 128 },
            { x = -160, y = 160 },
            { x = -64, y = 160 },
            { x = -64, y = 288 },
            { x = -32, y = 288 },
            { x = -32, y = 448 },
            { x = 0, y = 448 }