poly2tri library to Lua (math for 2d navmesh)

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
AntonioModer
Party member
Posts: 202
Joined: Fri Jun 15, 2012 5:31 pm
Location: Belarus
Contact:

poly2tri library to Lua (math for 2d navmesh)

Post by AntonioModer »

poly2tri - a 2D constrained Delaunay triangulation library.
The main advantage of this library for me - it is possible to make a hole in the polygons.
https://code.google.com/p/poly2tri/
https://github.com/jhasse/poly2tri
Example:
dude_cdt.png
dude_cdt.png (6.88 KiB) Viewed 6875 times
I make top-down-view game engine.
This is library is needed for me to build 2d-navmesh(viewtopic.php?f=5&t=81229), like this: http://www.gamedev.net/page/resources/_ ... shes-r3393
But I did not have enough skill to link this library with Lua (variants to link: LuaJIT.FFI + poly2tri-C; Lua + poly2tri-C++).
Maybe someone will be able to start it?
That would be very cool.
I could have in the future release my 2d-navmesh library on the free license. ;)
Maybe there are analogs in Lua?
If not, I'll will try port poly2tri-JS library to native Lua. (https://github.com/r3mi/poly2tri.js)
Last edited by AntonioModer on Thu Nov 12, 2015 4:07 am, edited 6 times in total.
User avatar
AntonioModer
Party member
Posts: 202
Joined: Fri Jun 15, 2012 5:31 pm
Location: Belarus
Contact:

Re: poly2tri library to Lua

Post by AntonioModer »

Ok then, i found this Lua module: https://github.com/Yonaba/delaunay
It is suitable for me, but there is a lack: https://github.com/Yonaba/delaunay/issues/3
Now i will fix this lack.

Edit.
This code is work fine: https://gist.github.com/AlliedEnvy/1009522
I will work on 2d navmesh (navigation mesh).
Last edited by AntonioModer on Mon Oct 26, 2015 11:27 pm, edited 2 times in total.
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: poly2tri library to Lua (for 2d navmesh)

Post by ivan »

The main advantage of poly2tri is the speed.
The library uses a sweepline so the triangulation is fast so it's good for rendering.
For optimal triangulation/partitioning there may be better solutions.

If you just want to support holes, you can do that using 'ear clipping' which is simple but slower.
With ear clipping, you first 'cut out' all of the holes in a specific order then you get
a resulting 'weakly simple polygon' and you triangulate that polygon.
I have a mediocre implementation here:
triangulation and hole cutting: https://bitbucket.org/itraykov/utils/sr ... /poly2.lua
polygon library: https://bitbucket.org/itraykov/utils/sr ... h/poly.lua
vector and point in triangle library: https://bitbucket.org/itraykov/utils/sr ... th/vec.lua
You need to include these three files in order to make it work.

Example with one hole:

Code: Select all

poly = require("utils.math.poly2")

polygon = { ... } -- polygon contour
hole = { ... } -- hole

polygon = poly.cuthole(polygon, hole)
triangles = poly.triangulate(polygon)
Example with multiple holes:

Code: Select all

poly = require("utils.math.poly2")

polygon = { ... } -- polygon contour
holes = { { ... }, { ... } } -- list of holes

holes = poly.sortholes(holes)
for i = 1, #holes do
  polygon = poly.cuthole(polygon, holes[i])
end
triangles = poly.triangulate(polygon)
Note that with the above implementation polygons and holes are represented as a list of coordinate pairs:

Code: Select all

polygon = { 0,0,  10,0,  10,10,  0,10 }
User avatar
AntonioModer
Party member
Posts: 202
Joined: Fri Jun 15, 2012 5:31 pm
Location: Belarus
Contact:

Re: poly2tri library to Lua (for 2d navmesh)

Post by AntonioModer »

Thank you very much, ivan. :)
Thanks for your library.
You directed me to a properly direction: i need read a math course, heh. :ultraglee:
Also I found awesome thing(The Computational Geometry Algorithms Library): http://doc.cgal.org/latest/Manual/packages.html

I did not detect one thing: I also need to work with convex polygons.
I'll work on it, and I will keep informed of development ...
User avatar
AntonioModer
Party member
Posts: 202
Joined: Fri Jun 15, 2012 5:31 pm
Location: Belarus
Contact:

Re: poly2tri library to Lua (math for 2d navmesh)

Post by AntonioModer »

Ivan, i have error with your code, i cant fix this, help me please:

Code: Select all

local poly2 = require("poly2")

local polygon = {}
polygon[#polygon+1] = 100
polygon[#polygon+1] = 100
polygon[#polygon+1] = 200*5
polygon[#polygon+1] = 100
polygon[#polygon+1] = 200*5
polygon[#polygon+1] = 200*5
polygon[#polygon+1] = 100
polygon[#polygon+1] = 200*5

local hole = {}
hole[#hole+1] = 150
hole[#hole+1] = 150
hole[#hole+1] = 250
hole[#hole+1] = 150
hole[#hole+1] = 250
hole[#hole+1] = 250
hole[#hole+1] = 150
hole[#hole+1] = 250

local polygonCut = poly2.cuthole(polygon, hole)    -- error here !!!
local triangles = poly2.triangulate(polygonCut)

Code: Select all

Error: code/math/itraykov/poly.lua:312: attempt to perform arithmetic on local 'by' (a nil value)
stack traceback:
	code/debug/log.lua:90: in function '__sub'
	code/math/itraykov/poly.lua:312: in function 'area2'
	code/math/itraykov/poly.lua:337: in function 'ccw'
	code/math/itraykov/poly2.lua:27: in function 'cuthole'
	code/math/itraykovPoly2Test.lua:46: in main chunk
	[C]: in function 'require'
	code/graphics.lua:312: in function 'draw'
	code/loveDraw.lua:3: in function 'draw'
	main.lua:95: in function <main.lua:52>
	[C]: in function 'xpcall'
	[string "boot.lua"]:1501: in function <[string "boot.lua"]:1496>
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: poly2tri library to Lua (math for 2d navmesh)

Post by ivan »

Sorry about that Antonio, the bug was caused by a change in the api of poly2.lua.
I have added the fix on Bitbucket, you have to change line 88:

Code: Select all

if k ~= j and poly.reflex(p, (k + 1)/2) then
so that the index supplied to poly.reflex must be in range between 1 to #polygon/2

Your example works fine after this change.

Note how the output triangles work:

Code: Select all

local poly2 = require("utils.math.poly2")

local polygon =
{
  100,100,
  200*5,100,
  200*5,200*5,
  100,200*5
}

local hole =
{
  150,150,
  250,150,
  250,250,
  150,250
}

local polygonCut = poly2.cuthole(polygon, hole) 
local triangles = poly2.triangulate(polygonCut)

-- iterate triangles
for i = 1, #triangles, 6 do
  local ax, ay = triangles[i], triangles[i + 1]
  local bx, by = triangles[i + 2], triangles[i + 3]
  local cx, cy = triangles[i + 4], triangles[i + 5]
end
Also, remember that if you have more than one hole, they have to be sorted.
In the future I should probably merge 'cuthole' and 'triangulate' into:
triangles = poly2.triangulate(polygon, holes, triangles)
User avatar
AntonioModer
Party member
Posts: 202
Joined: Fri Jun 15, 2012 5:31 pm
Location: Belarus
Contact:

Re: poly2tri library to Lua (math for 2d navmesh)

Post by AntonioModer »

Thanks, Ivan, its work. :)
Now i work on graph-math class for universal pathfinding.
test.png
test.png (235.79 KiB) Viewed 6589 times
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: poly2tri library to Lua (math for 2d navmesh)

Post by ivan »

Cool. There are a few limitations you have to be aware of:
1.the ear clipping method produces long thin triangles which are not very good for physics

2.polygons must be 'cleaned up' so that there are no shared reflex vertices

not allowed (shared reflex vertex or self-intersections):

Code: Select all

1 ---- 2   1 ---- 2
  \  /       \  /
 6 \/ 3       \/  ?
   /\         /\
  /  \       /  \
5 ---- 4   3 ---- 4
shared reflex vertices (6&3) and self-intersections (?) require
additional partitioning/math which is not related to triangulation.

allowed (shared non-reflex vertex):

Code: Select all

          ---------
          |       |
-------   | ----- |
\ --- /   | |   | |
 \\ //    | -- -- |
  \|/     |   |   |
   V      ---- ----
allowed as long as the shared vertices are non-reflex

3.if you have multiple holes they cannot touch the outer polygon or intersect with other holes

4.ear clipping is slow for large polygons (+1000 vertices)
User avatar
Tanner
Party member
Posts: 166
Joined: Tue Apr 10, 2012 1:51 am

Re: poly2tri library to Lua (math for 2d navmesh)

Post by Tanner »

Looks like you got it sorted out but, for future reference, I did make a simple wrapper around poly2tri which you can require from Lua as a C module: https://github.com/TannerRogalsky/lua-poly2tri
User avatar
AntonioModer
Party member
Posts: 202
Joined: Fri Jun 15, 2012 5:31 pm
Location: Belarus
Contact:

Re: poly2tri library to Lua (math for 2d navmesh)

Post by AntonioModer »

Wow. Thank you very much, Tanner. Great library! This is exactly what I wanted! :)
I will try it in the future.
Most likely, I will use it in the final version of my open-source Navmesh library.

Please, if not too much trouble, could you download here(on this forum topic) the binary library files to link with Lua for Windows(32 and 64 bit versions).
It would save a lot of time for me in future, in develop my Navmesh library. Because I'm a noob in C and C++. :)
Last edited by AntonioModer on Sun Mar 06, 2016 3:53 pm, edited 1 time in total.
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 59 guests