poly2tri library to Lua (math for 2d navmesh)

[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 (6.88 KiB) Viewed 7368 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)

[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).

[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 }

[AntonioModer]

Thank you very much, ivan.
Thanks for your library.
You directed me to a properly direction: i need read a math course, heh.
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 ...

[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>

[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)

[AntonioModer]

Thanks, Ivan, its work.
Now i work on graph-math class for universal pathfinding.

test.png (235.79 KiB) Viewed 7082 times

[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)

[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

[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++.