Handling 'continuous' or donut-like shaped holes

[GoogleCodeExporter]

Hi,

I am unsure if my case falls within what the README says will not work, but see 
the attached picture.  We are attempting triangulate the playable area of a map 
in our game, Bitfighter.  The walls are in blue and are the non-playable area 
sent as holes to poly2tri.

Before passing points into poly2tri, we use the excellent Clipper library 
(http://www.angusj.com/delphi/clipper.php) to ensure all of the walls are 
merged appropriately and there are no duplicate points, etc.

However, many times there is a wall that forms a continuous boundary and is 
therefore returned as two concentric polygons with the outer polygon wound 
counter-clockwise and the inner polygon wound clockwise (or the other way).  
This is just how Clipper outputs such a polygon.

Is it possible for poly2tri to handle such a case?

Original issue reported on code.google.com by buckyballreaction on 18 Apr 2013 at 5:53

Attachments:

• 6screenshot_12.png

[GoogleCodeExporter]

Forgot to be clear:  I wish to triangulate the entire black areas within the 
continuous walls, and any area that may be contained within further concentric 
or closed-off areas.

Also, there are triangles outside the walls because I used a basic rectangle as 
the outer polyline for the map - maps don't have to be closed off with walls.

Original comment by buckyballreaction on 18 Apr 2013 at 6:19

[GoogleCodeExporter]

Thanks for responding.  Attached is a simpler case (and as you can see I got it 
to work - more on that in a bit).  When triangulating an area such as this, I 
set the bounding polyline to be an exterior box with points:

bounds:
-336.000000, -336.000000
-336.000000, 336.000000
336.000000, 336.000000
336.000000, -336.000000

Then I sanitize all the walls' geometry by running it through Clipper as a 
polygon union and nonZero winding rule (which means inner holes return opposite 
winding).

The output geometry for the donut or circuit-hole is as follows:

polygon 0:
-289.760010, 304.000000
-304.000000, 289.760010
-304.000000, -289.760010
-289.760010, -304.000000
289.760010, -304.000000
304.000000, -289.760010
304.000000, 289.760010
289.760010, 304.000000

polygon 1:
-206.000000, 206.000000
206.000000, 206.000000
206.000000, -206.000000
-206.000000, -206.000000

Now last night one of the other developers suggested that I:
 1. Take any clockwise-wound output polygon of clipper to be a new polyline bound
 2. Add all the other counter-clockwise output polygons as holes to each new polyline bound
 3. Run poly2tri triangulation against each polyline bound

This seemed too simple, but it worked!  And that is what you see in the 
attached image.

Now, I have made some improvements to this algorithm that sped it up by about 
an order of magnitude.  Basically #2 in the steps above now becomes:

 2. Add holes to current polyline bound only if it is found interior to the polyline bound

Because Clipper is really good at sanitizing input data (and I used the union 
mode), all I had to do was check if one point of the hole was within the 
polyline bound to make sure the entire hole was within.

So this seems to work really well on levels with really complex geometry (see 
second attached picture) and very quickly.

It would be nice if poly2tri could somehow handle this case internally instead 
of my implementation.  Were you saying that it could?  

It may be even faster if it could do everything in one pass on one polyline 
bound instead of multiple passes like I have implemented.

Now it's my turn to hope I cleared things up.  :)

Original comment by buckyballreaction on 19 Apr 2013 at 2:45

Attachments:

• screenshot_18.png
• screenshot_19.png

[GoogleCodeExporter]

Need to understand exactly what kind of data you have before the triangulation. 

In the picture I guess you are just using a rectangle as polygon and adding 
your three toplevel ccw polygons as holes.

What you want is to triangulate the thin areas between the inner and outer 
walls of these three polygons?

If you are planing on using the triangulation for pathing or collision checks. 
Why use a thin wall and not just a border that decides what is inside and 
outside.

Anyways the triangulation part itself in poly2tri is just triangulating a bunch 
of points and enforced linesegments/constraints. It's just when we cleanup the 
triangulation and decide what triangles to keep we take advantage of the 
knowledge that we have a simple polygon. Eg. we can easily find a starting 
triangle that we know are inside the polygon and then find every other 
connected triangle that are inside.

So it wouldn't be impossible to have a bunch of nested polygons in a single 
triangulation and then write a new meshClean. Lets say you take one edge from 
each ccw polygon and use it get a starting triangle from the triangulation. You 
could then loop over all ccw polygons and find all triangles inside each of 
these polygons.

Haven't used clipper. Do you have some kind of tree structure of ccw and cw 
polygons to know what is inside what or just flat list of polygons?

Don't know if that made things clearer or not :)

Original comment by thahlen@gmail.com on 19 Apr 2013 at 12:43

[GoogleCodeExporter]

Oh, sorry.  I am using the c++ version of poly2tri, latest commit from version 
control, no alterations.

I did think about using a hierarchical system to reduce the holes-within-holes 
complexity, but I kept it simple (and I'm no computational geometrist).  :)

The orientation information was a blessing to have in order to make my 
adaptation of poly2tri work.  Are you saying that orientation wouldn't be 
needed to properly triangulate this case in a more efficient manner?

Original comment by buckyballreaction on 19 Apr 2013 at 5:26

[GoogleCodeExporter]

Ok, I understood right the first time then.

What language version of poly2tri are you using?

Yes it should be possible to perform all triangulations in one pass. Then loop 
over each cw polygon and using one edge/point from that polygon find all 
triangles inside that polygon. 

Since the information of orientation and that the triangulation contains 
multiple polygons is information only your code knows about. This isn't 
something I just can add to poly2tri without some new api interface. 

You could tweak poly2tri to you needs. I think the code change to do this would 
be pretty minimal. The only problem to solve is to go from a point on one of 
the cw polygons and find a triangle that is inside that polygon. Given that 
triangle we can use existing code to get all other triangles inside that 
polygon.

The more I think about this I think you might need a hierarchical search 
structure to make it faster than your current solution. A structure that can 
find a specific triangle given a certain point.

I would probably have solved it like you have now and keep it simple :)

Original comment by thahlen@gmail.com on 19 Apr 2013 at 4:44

[GoogleCodeExporter]

Yes the orientation information is needed when you have nested polygon/holes.

Current implementation of poly2tri did not need it since it was simply focused 
on triangulating a single polygon with holes. I think keeping it simple is what 
has made so many port this lib to other languages.

Any expansions and new features would most likely have to be release as a new 
lib since it would be impossible to keep all language ports in sync.

Btw always fun to see what poly2tri is used for. Games are my favorite ;) 

Original comment by thahlen@gmail.com on 19 Apr 2013 at 5:54

[GoogleCodeExporter]

Yeah a polygon clipping library is great. 

I was actually working on one right after poly2tri was released. Was going to 
use it as an optional input validator. Someday I'm going to finish it :)

Original comment by thahlen@gmail.com on 19 Apr 2013 at 7:43

• Changed state: Done

[GoogleCodeExporter]

OK.  I completely understand about keeping something easily portable.

I'll just stick to my implementation and slowly implement more and more 
optimizations as I find them.  This bug could be probably be closed.

One other thing while I have you here :)

A note somewhere about using something like the Clipper library may help those 
people with input problems (although maybe it's just for my specific case)

I've been surprisingly pleased with how robust poly2tri has been otherwise - we 
have some crazy levels that it handled without problems.

Thank you for a great library!

Original comment by buckyballreaction on 19 Apr 2013 at 6:15

[GoogleCodeExporter]

You might find this talk interesting with regards to clipper.
https://github.com/mrdoob/three.js/issues/3386

Original comment by thahlen@gmail.com on 29 Apr 2013 at 11:40

[GoogleCodeExporter]

Very interesting..  I will look at the ExPolygons structure as it will probably 
be much faster than my horrid implementation.

Also, I've given more thought to what you said about doing the triangulation in 
one pass with poly2tri.  

I've thought about adding another method to add multiple 'polylines'.  Then 
upon clean-up when it collects the triangles, it will somehow skip triangles 
within a polyline.  I'm a bit weak algorithmically here, and much of c++ port 
is not documented, but I figure that if I can somehow determine the number of 
holes and polylines that a triangle is in, then I can only cleanup those 
triangles where (polylines - holes == 0).

Would you have any further pointers about what methods in the API would be able 
to help me here?  

I'm open to alternate plans of attach as well..

Original comment by buckyballreaction on 29 Apr 2013 at 1:59

[GoogleCodeExporter]

I happened to talk to someone about clipper.
He said:

"Clipper has an exPolygons structure (in newest Clipper it is replaced by 
PolyTree) which is populated automatically in every boolean operation (if 
wanted), so there is no need to make any point in polygon checking. This is 
especially useful as a pre-triangulation step."

eg. you should be able to get a tree with the contours so you don't have to 
find out yourself what are inside what.

Original comment by thahlen@gmail.com on 29 Apr 2013 at 3:49

[GoogleCodeExporter]

If you can get a tree of contours right out of clipper so you don't have to do 
the point in polygons tests yourself and then just use poly2tri like you do now 
and triangulate polygon by polygon.

I don't think there is that much overhead to triangulate several small polygon 
instead one pass triangulation, since poly2tri doesn't use any expensive search 
structures.

Original comment by thahlen@gmail.com on 29 Apr 2013 at 3:59

[GoogleCodeExporter]

If you wanted to try making a one pass triangulator. 

Do it like this: 
1. make the outer polygon a rectangle then just add every polyline as a hole.
2. alter void Sweep::FinalizationPolygon(SweepContext& tcx)
This is called after tirangulation.
You need to loop thru all polylines you know are polygons(cw polylines?)
Find one triangle inside each polygon then call tcx.MeshClean(*t);

So your only issue is finding the starting triangle for each cw polyline.
There are no search structure in place for this for really good performance.

Original comment by thahlen@gmail.com on 29 Apr 2013 at 5:24

[GoogleCodeExporter]

I just came across my old post here and I realized I didn't actually follow up.

I took your advice and I was able to successfully use the polygon-tree 
(ExPolygons) output from clipper and use poly2tri on each hole or child-hole.  
This ended up being much better than anything previously attempted by me, and 
the results were very efficient.

Thanks again!

Original comment by buckyballreaction on 23 Sep 2013 at 3:06

[GoogleCodeExporter]

Great to hear :)

Original comment by thahlen@gmail.com on 23 Sep 2013 at 8:07

[GoogleCodeExporter]

Follow-up #2:

Someone urged us to release our code that combined clipper + poly2tri for 
complex, robust triangulation as a library for wider usage.  We just barely did 
that here:

https://github.com/raptor/clip2tri

The code is still highly specific to the bitfighter code base (and could use a 
*lot* of clean-up) but maybe it'll help someone looking to do what we do.

Original comment by buckyballreaction on 26 Aug 2014 at 3:10