[CLOSED] love.math.triangulate bugs out

[s-ol]

I tried modelling a player as a simple polygon, but obviously I ended up with something concave.
I tried using

Code: Select all

love.math.triangulate()

to turn it into (convex) triangles so I can draw it, but that function fails as soon as you have some kind of "S" shape in your polygon:


I attached a little löve program that stores all points you click and passes them through math.triangulate (if there are more than 2), rendering them on screen.

Code: Select all

polys = {}

function love.draw()
    if #polys < 6 then return end
    for i,v in ipairs( love.math.triangulate( polys ) ) do
        love.graphics.polygon( "fill", v )
    end
end

function love.mousepressed()
    table.insert( polys, love.mouse.getX() )
    table.insert( polys, love.mouse.getY() )
end

function love.keypressed()
    print( "-------------" )
    for i,v in ipairs( polys ) do
        print( "{ " .. v .. ", " .. v[2] .. " }," )
    end
end

as .love:

polytest.love

(373 Bytes) Downloaded 101 times

[s-ol]

Also I'm too dumb to write a better algorhytmn's implementation for this, but I did find one that should do this correctly:

Seidel's polygon triangulation

1. Decompose the Polygon into Trapezoids.
2. Decompose the Trapezoids into Monotone Polygons.
3. Triangulate the Monotone Polygons. (can be left out for rendering with love.graphics.polygon)

There is a JS implementation though that I might be able to port (this is also the smallest tesselation/triangulation library I have found in terms of SLOC)

For now, I'll just use haxe for this quick prototype, I felt sorry for abandoning that language anway

[vrld]

Are you sure this is a bug in löve? Is your polygon really a simple polygon?
I modified your code to draw the triangles and the original polygon as well:

Code: Select all

polys = {}

function love.draw()
	if #polys < 6 then return end
	love.graphics.setLineJoin("none")
	local ok, tri = pcall(love.math.triangulate, polys)
	if ok then
		for i,v in ipairs(tri) do
			love.graphics.setColor(100,100,100,100)
			love.graphics.polygon( "fill", v )
			love.graphics.setColor(170,255,170)
			love.graphics.polygon( "line", v )
		end
	end

	love.graphics.setLineWidth(3)
	love.graphics.setColor(170,170,255)
	love.graphics.polygon( "line", polys )
	love.graphics.setLineWidth(1)
end

function love.mousepressed()
	table.insert( polys, love.mouse.getX() )
	table.insert( polys, love.mouse.getY() )
end

triangulate.png (54.09 KiB) Viewed 6223 times

triangulate2.png (142.16 KiB) Viewed 6223 times

BTW: Löve uses Kongs triangulation, which I think is simpler than other algorithms. You can look at the C++ implementation here. HardonCollider has equivalent code in Lua.

[s-ol]

Have you messed around with it a bit?
I'll try and record a video of when it breaks for me, I'm sure I never crossed any old polyline segments, and thats basically the only difference for non-simple polygons, no?

Video: https://gfycat.com/JauntyShockedBigmouthbass

btw I like your project naming convention

[Zilarrezko]

wait... Is triangulating working with non multiples of 3?

[slime]

Have you messed around with it a bit?
I'll try and record a video of when it breaks for me, I'm sure I never crossed any old polyline segments, and thats basically the only difference for non-simple polygons, no?

Video: https://gfycat.com/JauntyShockedBigmouthbass

I used vrld's modified code to duplicate what you're doing in that video:

wait... Is triangulating working with non multiples of 3?

triangulate creates triangles out of a polygon made of any number of vertices (the minimum being 3), as long as it's simple.

That being said, it might be useful for LÖVE to use something like this polygon partitioning library in the future.

[s-ol]

Have you messed around with it a bit?
I'll try and record a video of when it breaks for me, I'm sure I never crossed any old polyline segments, and thats basically the only difference for non-simple polygons, no?

Video: https://gfycat.com/JauntyShockedBigmouthbass

I used vrld's modified code to duplicate what you're doing in that video:

wait... Is triangulating working with non multiples of 3?

triangulate creates triangles out of a polygon made of any number of vertices (the minimum being 3), as long as it's simple.

That being said, it might be useful for LÖVE to use something like this polygon triangulation library in the future.

oooooh, now I get it; I of course can't triangulate a "WIP" simple polygon if it's not simple at that point. Thanks for making me notice, thread can be closed now

EDIT: interesting link tho. The most useful algorithm would be "Hertel-Mehlhorn" I guess, it runs faster than the last one and works pretty good. Also convex polygons are enough to render as fans without any following calculations, so we're "good" at that point.

[s-ol]

Also, I just stumbled upon your post about geometry shaders:

Only if there's a really good reason to (so far I haven't found one).
Geometry shaders would add several complications to the shader pipeline, they're usually slower (and less useful) than tessellation shaders, they aren't supported on all systems, and I believe there are two separate distinct versions of them which might require separate shaders written for each.
Since they aren't actually very useful, it seems like a lot of hassle for no good reason to add proper support, if that's even possible.

I am currently working on a case where they would be useful to render pseudo-3d perspective stuff (see attached .love),

[Zilarrezko]

triangulate creates triangles out of a polygon made of any number of vertices (the minimum being 3), as long as it's simple.

That being said, it might be useful for LÖVE to use something like this polygon partitioning library in the future.

I guess my polygon isn't simple :/ still not workin' out for me.

[s-ol]

triangulate creates triangles out of a polygon made of any number of vertices (the minimum being 3), as long as it's simple.

That being said, it might be useful for LÖVE to use something like this polygon partitioning library in the future.

I guess my polygon isn't simple :/ still not workin' out for me.

Post an image of what you are trying to do or some code!