Holes in contours causes triangulation failure

[timo22345]

Not sure if this is a bug, but the triangulation fails, although shape is simple. See the images, code and description of the problem:

http://stackoverflow.com/questions/16241854/holes-in-polygons-causes-triangulation-failure-in-three-js

Without holes works.

Every combination of orientation has no effect.

---

UPDATE: I checked the Three.js code and there is a link to http://www.sakri.net/blog/2009/06/12/an-approach-to-triangulating-polygons-with-holes/, which says that 90% of times it works.

If that method is used for triangulation in Three.js, 90% propability is not acceptable in production environments.

[WestLangley]

As stated in the guidelines, help requests should be directed to stackoverflow. This board is for bugs and feature requests.

Not sure if this is a bug

If you find a bug, then please see the guidelines for How to Report a Bug.

Also, it would be very helpful if you would simplify your example to a minimal test case. It may give you insight into the cause. For example, try simplifying the shape complexity, or removing holes one-by-one.

90% probability is not acceptable in production environments.

Please understand that three.js is in alpha.

If there is a reliability issue that cannot be resolved, however, then the triangulation code should be moved into the examples, IMO.

[timo22345]

A minimal example: http://jsbin.com/odufih/5/edit, which causes duplicate point error, which is not the case in the http://jsbin.com/odufih/1/edit.

Maybe it's not in my skill level to examine the three.js code, when the author can add console.log(var) to just the proper place which shows the erroneous hole, in minutes. For me it is hours, at least. I'll try to make my code and let other fix their code!

And usually when someone gets a bug report and if he/she wants to be friendly, he/she thanks for helping to find issues in the code...

[leonbloy]

I've also experienced some triangulation failures, with fonts created via typeface.js .

http://st.hjg.com.ar/mysis/mysis?line1=Hello%21&font=lemon

Look into the exclamation point.

[nicholaswmin]

@leonbloy maybe this has nothing to do with this post - the main problem here are erroneous rendering of holes. your exclamation point is solid.

[WestLangley]

@timo22345 I removed all the holes in your dataset except for one, and this is the result.

You have problems with your data and/or data parsing routine.

[timo22345]

@WestLangley: So what are your final thoughts of the requirement for holes?

I have already find:

• Polygon are not to allowed have semi-adjacent duplicate points, but now I find that also
• if polygons itself have not semi-adjacent duplicates, it is not enough. Also hole cannot have a point which share coordinates with contour.
• And not tested this, but maybe also between holes there are not allowed to be semi-adjacent points.
• And I tested also that if hole's vertice is exactly on contours's edge, the triangulation fails.
• And this you already know: any polygon itself cannot have self-intersectings and ALSO holes cannot have "self"-intersectings with other holes or with contour.

My conclusion: this triangulation function is not yet suitable for automatic processes. There are so much possibilities for failures that each and every vertice have to be manually checked.

[WestLangley]

I think pretty much the same as I said earlier:

1. If there is a reliability issue that cannot be resolved, then the three.js triangulation code should be moved into the three.js examples.
2. You, too, have some problems in your own data and/or code, but I am sure you can figure those issues out.

Good luck!

[timo22345]

@WestLangley: To help to isolate the failure source, I and all Three.js developers could be much more easier to try to fix the issue, if it is first isolated to one of the sources: 1) data, 2) my parser code or 3) three.js.

So, to help (not only me) but every other also, I have to ask:

Did you find the source of the problem and if you did, where? "If there is a reliability issue" and "some problem in your data and/or code" are both such sentences that if expressed, nearly requires to be followed by some proofs or evidence. Otherwise they can be ignored.

I cannot find any problems in my data and code. I checked the duplicates in the whole data set. No sequential, no semi-sequential. No overlapping, no self-intersections. All are true simple polygons. So I have to assume that the failing part is not my data. It is either my parser or then three.js. But if you have better knowledge of the failure source, I and others also would appreciate very much your findings.

[timo22345]

If the tria code really is from here: http://www.sakri.net/blog/2009/06/12/an-approach-to-triangulating-polygons-with-holes/

It may have something to do with finding the connection line from hole to outer contour. If you read the above page, there is a comment:

"I discovered a weaknesses in your ‘choping of holes’ approach. It is not checked that other points of the hole are ‘in’ the chopping area. For example: take a square polygon (only 4 points on the corner) and a circular hole in it with lots of points, near one of the corners of the square. The choping ‘area’ is quite big as it will span one side of of the square and will include multiple points of the circle. In this is case, looking for the shorest connection is not enough. A possible candicate connection must be checked on intersection with other points.

A second problem: say I have two holes, hole 1 and hole 2. Hole 2 is in the path of the shortest connection between hole 1 and the polygon…"

For me this sounds a possible candicate for this failure. So if this is the cause, more intelligent "connection line" finding should be performed.

What thoughts?

[nicholaswmin]

I have the same issue here.

[timo22345]

I examined the code and AFAIK the problem lies on the function removeHoles: function ( contour, holes ) . Just in the case if this code is using technique from: http://www.sakri.net/blog/2009/06/12/an-approach-to-triangulating-polygons-with-holes/.

shortest = Number.POSITIVE_INFINITY;

        // Find the shortest pair of pts between shape and hole

        // Note: Actually, I'm not sure now if we could optimize this to be faster than O(m*n)
        // Using distanceToSquared() intead of distanceTo() should speed a little
        // since running square roots operations are reduced.

        for ( h2 = 0; h2 < hole.length; h2 ++ ) {

            pts1 = hole[ h2 ];
            var dist = [];

            for ( p = 0; p < shape.length; p++ ) {

                pts2 = shape[ p ];
                d = pts1.distanceToSquared( pts2 );
                dist.push( d );

                if ( d < shortest ) {

                    shortest = d;
                    holeIndex = h2;
                    shapeIndex = p;

                }

            }

        }

Not sure about this, have to examine this more.

UPDATE:

When removeHoles() return an object, it has a member shape, which is according to source code "shape with no holes", it is the red shape below. The green is the original.

[timo22345]

I didn't get the default triangulator to work. The problem was not my data or my parser. The faulty was the default triangulator in Three.js, but because the code is unknown to me, cannot say where there the problematic code part is.

But fortunately there was already the poly2tri triangulator calling function named triangulateShape2() in three.js, which was commented out (for unknown reason).

I downloaded https://code.google.com/r/remiturboult-poly2tri-js-2/source/browse/src/js/poly2tri.js and replaced in Three.js the line "triangulateShape: function ( contour, holes )" with "triangulateShape2: function ( contour, holes )" to disable the default triangulator.

Then enabled "triangulateShape2 : function( pts, holes )" by changing it to "triangulateShape : function( pts, holes )".

After that the polygon data triangulated exactly right and well! But of course it has also limitations regarding semi-adjacent duplicates, which are needed to handle in a way that doesn't break the geometry.

[WestLangley]

@timo22345 Sorry, I stand corrected. I am no longer convinced that there are problems in your code. I was confused because everything is flipped. Hence, CW rotation becomes CCW, and ( 0, 0 ) moves from the upper-left to the lower-left.

As I requested, we need a simpler test case. I have done some of that work for you below. I replaced the "tree" with a rectangle, and I remove all but the first 4 "holes". A simpler example involves removing your parsing code.

If you consider various combinations of the 4 holes, the results are bizarrre. I have no idea what is going on.

var polys = [ { "outer":[{"X":0,"Y":0},{"X":230,"Y":0},{"X":230,"Y":230},{"X":0,"Y":230}],
            "holes":[
              //[{"X":149.952,"Y":51.338},{"X":150.825,"Y":47.383},{"X":149.554,"Y":48.757}],
              //[{"X":69.191,"Y":54.204},{"X":68.924,"Y":49.128},{"X":67.899,"Y":48.266}],
              //[{"X":117.109,"Y":140.339},{"X":125.864,"Y":116.268},{"X":126.352,"Y":110.58},{"X":122.683,"Y":117.966}],
              [{"X":104.36,"Y":136.75},{"X":100.006,"Y":83.235},{"X":97.063,"Y":84.608},{"X":95.913,"Y":95.243},{"X":93.732,"Y":101.053},{"X":95.356,"Y":116.686}]
            ]
        },
      ]; 

[timo22345]

I don't know also what is wrong, but with exactly same (my coded) parser and using poly2tri as a triangulator in Three.js, the output is this:

And also a little more complicated structure renders without issues:

[WestLangley]

@timo22345 That looks pretty good to me, don't you think? :-)

What do you recommend?

ping @zz85

[timo22345]

@WestLangley Thanks for commenting. I have to make more tests with very complex shapes with tens of holes. And if they all passes, then I assume that the current triangulator can be replaced with poly2tri, as far as my opinion is considered. The one I used is this: https://code.google.com/r/remiturboult-poly2tri-js-2/source/browse/src/js/poly2tri.js

But no hurry to replace anything yet, because (as I described in some of my previous posts) the calling code is there yet in Three.js and people can enable it for testing purposes very easy and download poly2tri.

The licence of poly2tri seems to be BSD, so no issues regarding licencing.

[WestLangley]

@timo22345 I would be grateful if you would continue to pursue this, so, well...., I don't have to. :-)

Being able to articulate the limitations is very important. If the limitations are acceptable, we can note them in the code/docs. If not, we can move the code to the examples. That decision will be up to @mrdoob.

[timo22345]

I tested few limitations already. As I expected, the poly2tri triangulator (as well as the current triangulator) cannot handle:

1) semi-adjacent (=non-sequential) duplicates on the contour 2) semi-adjacent duplicates on the hole(s) 3) duplicates between contour and hole(s) 4) duplicates between hole(s) and hole(s)

Nor these: 5) co-linear edges 6) hole outside contour 7) hole inside hole 8) adjacent duplicate points 9) self-intersections

List seems big, but these restrictions apply also to current triangulator but with the difference that the current one fails also in other cases in an unexpectable way.

[WestLangley]

OK. I see where you are heading with this. I'm thinking it's better to specify requirements, rather than limitations.

For simplicity, it is OK if the requirements are overly-restrictive. We know what we want to support here -- simple closed curves for the contour, and simple, closed, pairwise-disjoint, wholly-contained, curves for the holes.

[obidobi]

To handle the above limitations you need a clipper lib like http://www.angusj.com/delphi/clipper.php then you can triangulate pretty much everything.

Guess someone have to port it to javascript ;)

Btw. poly2tri's home is at http://code.google.com/p/poly2tri/source/browse?repo=javascript Rémi Turboult is managing that repo to so I guess it's better to use that than his clone.

You can try it out at this page: http://javascript.poly2tri.googlecode.com/hg/index.html

[timo22345]

To remove self-intersections and combine common edges and remove duplicates you can use Javascript Clipper:

https://sourceforge.net/p/jsclipper/wiki/Home/ http://jsclipper.sourceforge.net/5.0.2.1/main_demo.html

For now it cannot output ExPolygons structure, which makes automatically contour-holes relationships, but I'll release soon an update to it. All other limitations can be handled using Javascript Clipper, but the semi-adjacent duplicates, because Javascript Clipper (as well as the original Clipper) cannot produce true simple polygons, but weakly-simple polygons, where can be semi-adjacent duplicates. This limitation is possible to handle applying a "broken pen nib" effect on every duplicate (http://stackoverflow.com/a/16183613/1691517).

[obidobi]

I didn't know you worked on a port of Clipper for js! Awesome. Also didn't know about Clipper producing weakly-simple polygons. :(

Apart from that jsclipper and poly2tri should make a great pair ;).

btw I wrote poly2tri and was was working on a clipping lib myself after poly2tri so I know the pain in writing a robust lib that handles every edge case. Was thinking of porting Clipper to java but never got around to it.

[timo22345]

@obidobi The fact that Clipper produces weakly-simple polygons is in fact in this case not the core of the problem. All we know that polygon with holes is not a polygon, it is a set of different polygons with opposite winding orders. Although Clipper would output simple polygons, there still can be duplicates between contour and holes or between holes. This means that also in cases of true simple polygons you have to do something with these duplicates between polygons (eg. "broken pen nib" effect). So it is the same, if Clipper produces simple polygons or not. But of course the scenario, that "broken pen nib" function would be inside Clipper, would make sense. If this effect is minimal (eg. 0.01), it is already enough to make triangulation work. I'm coded and am now testing this like "broken pen nib" function.

[obidobi]

@timo22345 I had a discussion with someone using clipper and poly2tri not long ago. You can see how he solved his problem here: http://code.google.com/p/poly2tri/issues/detail?id=74

But I guess he didn't have that duplicate points issue. Just nested polygons.

I made poly2tri simple in a way to not require winding order since I just needed it for simple non nested polygons.

To support weak-simple polygons with shared points poly2tri would need the input as bunch of oriented line loops with the only requirement that the line loops doesn't intersect. Then poly2tri could with some work be extended to support those cases.

The thing is that I only maintain the Java branch and could not guarantee that any major additions/changes to poly2tri would get pushed to other ports :(.

[timo22345]

@obidobi If I understand right that http://code.google.com/p/poly2tri/issues/detail?id=74 issue: 1) there is a question of the hole edge touching the contour edge, which poly2tri cannot handle. Or 2) then there was an issue of examining what hole belongs to what contour. 3) Or both.

These cases should be handled using Clipper: 1) If for some reason (eg. rounding issues) there are or is likely to are still common edges between hole and contour, they can be handled by offsetting (dilating) holes a bit (eg. 0.01*scale) to make sure that hole and contour have no common edges and then unioning (or doing some other boolean) to make polygons weakly-simple or simple. 2) 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. As far as I understand the user in the question tried to use only Polygons structure and tried to manually find which hole belongs to which contour.

Regarding to weakly simple polygons: They can be handled at least in making first sure that input polygons are made at least weakly simple and then making a "broken pen nib" effect, which is fast because duplicateness comparing can be made using key checking and after that only duplicates are needed to be processed (one sqrt to find a nib point along previous edge and other sqrt to find a nib point along the next edge. The effect is like this, using parameter 5px to make the effect visible, but in reality float 0.001 is enough to make triangulation work:

After this step, the polygons are true simple polygons which has no duplicates in any meaning and the triangulation goes without issues (below nibbed by 0.01):

[obidobi]

Ah I see really nice. The images made it clear what you meant by "broken pen nib". So you have no issues triangulating any shapes now then and all you want is three to use poly2tri?

I will put a link to clipper on poly2tri's homepage. Might make it easier for someone to find it if they don't know about it.

[zz85]

Hi, it has been about 2 years since I touched that triangulation code, sorry if its still been causing problems. Rewriting the triangulation code has always been on my mind, but I have never gotten to do that. If you could, I would encourage you to give it a try.

When I was working on the triangulator, one of the frequent issues were with holes. I wrote the code to integrate tri2poly.js so the triangulator was modular could be swapped out with another. While the currently "default" triangulator isn't the best triangulation approach, it seemed to work well enough with Fonts which was the biggest use case then. At that time, I think we didn't want any additional dependencies, so tri2poly was dropped (the reason the code was commented).

Like Westlangey say if we should move the triangulation to the examples, then I'm sure we could reevaluate the options we have for the polygon triangulation with other libraries. If I'm understanding this thread correctly, would you say poly2tri + clipper is the preferred triangulation solution for three.js now?

[timo22345]

@zz85 I understand the issue. The default works reasonably well without holes, but holes causes so much possiblities for failures that it is not the best option for general polygon triangulator.

All tests with complex polygons with complex contour-hole structures have succeeded so far in poly2tri. But I have not yet tested it with thousands of different polygons to be able to say that it's stability is in production state.

Taking into account that those thousands are not yet tested, for now I can say that Clipper + poly2tri works well together. The "nibbing" technique seems to work reliably, if polygons are cleaned using Clipper's CleanPolygon function which removes (combines into one vertice) too near adjacent vertices (eg. within 0.1 units * scale). After this polygons have to be Simplified (Unioned) using Clipper's Simplify function to remove self-intersections and combine common edges and make polygons weakly-simple which are simple in all other means but regarding semi-adjacent duplicates. The Clipper's CleanPolygon() makes a safe circular region around each vertice inside which we can move semi-adjacent and cross-polygon duplicate points to achieve the "broken pen nib" effect. If vertices are Cleaned using eg. 0.1 units, then eg. 0.01 units "nibbing" is safe to do. And after this the triangulation works without issues. Sounds a bit complicated, but it actually can be achieved using only few lines of code.

The dependency issue is still left. Poly2tri:s update cycle is rather frequent, and it would be nice to make it easy to use the newest version if wanted. One possibility would be to include some stable version in Three.js (eg. the one that I have tested seems to be such), which is not updated before there is a good reason for it (eg. speed, stability or bug-fix). But Three.js is rather big library, and adding one more thousand rows is a decision that have to be made after serious thinking.

I'm not yet sure in which side the "broken-pen-nib" should be done. CleanPolygon (=RemoveTooNearVertices) is about 60 lines of code and BreakPenNibs() is about 200 lines, but because Removing too near vertices can cause minor self-intersections the order is this: clean, union, breaknibs. This means that it may be not wise to implement "nibbing" in Three.js, because then the union feature should be there also which means 2000-6000 lines of Clipper code. So as a conclusion of this paragraph: if user first makes cleaning and unioning using Clipper, it makes output weakly-simple (= have semi-adjacent duplicates). If "nibbing" is inside Three.js, it means that Three.js can accept weakly-simple polygons as input making it more permissive and usable as such. But because user can have made the "nibbing" beforehand, it is waste of resources to make it again. To prevent this the "nibbing" can be made optional using some parameter. 200 lines of code is not much and the algorithm is fast.

But this doesn't solve the bad designed fonts, that have self-intersections, but I assume that this is a font creator side problem to make font outlines to be simple. Fonts can have curves, and these have to be converted to polygons before extruding and this polygonization can cause also self-intersections in some cases, so the fonts that are used in Three.js should be polygonized fonts as far as I can understand. Or how they are handled now?

[timo22345]

@obidobi In the previous post I described a possible scenario regarding Three.js and poly2tri: adding it as a default triangulator seems to be wise and after tests with thousands of complex polygons I can say this more sure :)

Thanks for adding a link to JS Clipper. I'm soon updating the exPolygons bug, so after it the Clipper is more usable as a pre-triangulation step, because it then can provide you the desired contour-hole relationships with only a little overhead. Also some performance issues have to be fixed. Eg. now it uses big integers also in some cases where it is not needed and it slows down the performance a lot: nearly 30% in FF19. Also point creating is now achieved using very slow var IntPoint = function(x,y){this.X=x,this.Y=y}. The more faster at least in FF19 is to use var IntPoint = function(x,y){return {X:x, Y:y}}. Also many of the push commands can be converted to assignments and using preallocated arrays is also significantly faster. Also I'm considering to implement Web Workers in some of the most heavy calculations (eg. finding intersections) in cases where there are huge amount of vertices. And couple of fixes have to be done to make Clipper itself Web Worker ready (but this is a really minor fix). But the first priority is the exPolygons bug fix and some helper functions regarding exPolygons. These are details of my side, but these findings can of course help others also to make code more efficient.

[timo22345]

Here is another rather complex example of Clipper + Poly2tri + Three.js. No issues.

[bhouston]

Great work guys. So is this going to be integrated into ThreeJS or made easy to use in another fashion? This stuff is awesome!

[zz85]

For fonts in three.js, the typeface.js format which are essentially vector fonts are used. Essentially they are a series of paths using bezier curves, lines etc. These are mapped to THREE.Shape which are a similar path representation with holes. The shapes get triangulated in the process, when used with ExtrudeGeometry, just like other shapes.(Wrote a little about this before but the picture links are broken)

But this doesn't solve the bad designed fonts, that have self-intersections, but I assume that this is a font creator side problem to make font outlines to be simple. Fonts can have curves, and these have to be converted to polygons before extruding and this polygonization can cause also self-intersections in some cases, so the fonts that are used in Three.js should be polygonized fonts as far as I can understand. Or how they are handled now?

I think we would all love to see three.js handles complex shapes, so it think it would be a great addition to the examples (and @mrdoob wouldn't mind it there i think).

Just a simple question - apart from LOC, what's the exact filesize for clipper + tri2poly? Also, clipper seems to be a 2D CSG library to me, so are there other purposes aside that and the polygonal simplification functions?

[timo22345]

@zz85 Clipper: 77592 bytes. Poly2tri: 27783 bytes. Total: 105375 bytes. Minified using Google Closure Compiler - Simple (including Copyright lines). Clipper makes union+intersection+xor+difference and polygon offsetting, and it can output contour-holes structure and supports big integers. Big integer part is rather big in JS Clipper: 18265 bytes, but there are parts that are not really needed, but hard to remove. The big integers are needed because Clipper uses integers to achieve numerical robustness.

"2) points extraction from 2d paths" is the most important part of that link that you sent. What algorithm have you used for polygonizing? RSA = Recursive Subdivision Algorithm (De Casteljau), PAA = Parabolic Approximation Algorithm, CAA = Circular Approximation Algorithm, FDA = forward differencing algorithm?

[bhouston]

100kB minified isn't small given that Threejs is currently only 400kB minified, thus it is an increase of 25%. I wonder if there is some way of making a complimentary library that people can use if they need it but not forcing everyone to include all of these advanced features?

[timo22345]

@bhouston I agree that. Clipper is too big to include in main Three.js, as it doesn't add a feature that is used everywhere. Better would be some stable 3D clipping library, that could handle also 2D clipping. But there is again a question is it needed to be included in Three.js or used as a separate lib.

[nicholaswmin]

Separate Extrusion library since it applies only there. Clipper+Three for example. Just my opinion

[timo22345]

@nicholaswmin That may make sense. But because Clipper may be needed also elsewhere in the project (eg. in making polygons weakly-simple for other purposes than triangulation), including it inline in Three.js or Extrude.js would be problematic.

[xxdaggerxx]

Hi, is there any examples i can follow on how to implement Clipper for three.js? I have followed all the examples, but I'm afraid this is way above my head. I am trying to extrude non-English fonts, and some of them triangulate badly. I believe clipper might be the solution. Anyone care to help?

[WestLangley]

@xxdaggerxx As stated in the guidelines, help requests should be directed to stackoverflow. This board is for bugs and feature requests.

It would be great, however, to have a three.js example that demonstrates this approach.

[nicholaswmin]

@xxdaggerxx switch to poly2tri.js

[xxdaggerxx]

@nicholaswmin Yup that's what i did, still not good enough though, especially for Chinese fonts.

[jahting]

When trying out three.js I hit some problems with triangulation and found this thread.

1) Some of the issues mentioned here are certainly a matter of (specified) constraints.

2) Others like those timo22345 cited in https://github.com/mrdoob/three.js/issues/3386#issuecomment-17111341 are certainly bugs. I have constructed some easy ones in http://jsfiddle.net/H794a/ and written a solution which can be viewed at http://jsfiddle.net/H794a/1/.

• All examples using THREE.Shape.Utils.triangulateShape still work.
• timo22345's tree example works too.
• have just added another version of THREE.Shape.Utils.triangulateShape and renamed the old one.
• did extensive unit-testing to its internal helper functions
• didn't remove the old THREE.Shape.Utils.removeHoles, since that would be an API change

3) Some of the issues users have when extruding fonts seem not to come from triangulation but from loading the font definition.

• e.g.: in the example "webgl_geometry_text" type an "%" or German characters like ä, ö in the font "optimer"
• I changed the sequence of path definitions for some character in the font file by hand and the result looked correct.
• Thus I suspect the font loader is not always able to recognize what's a shape and what's a hole.

I don't have lots of other eamples for testing - so it would be great if others could run their data against my changes before I make the pull request.

This is my first try at contributing to a github project and I'm neither an expert at JavaScript. So I hope I didn't make a total mess of it.

[WestLangley]

ping @timo22345 @obidobi @zz85

[WestLangley]

@jahting Perhaps you should file your PR and see what happens... This is an interesting feature, but not one that gets a lot of attention.

[saeidN]

Hi guys, I have a very simple test case for this bug. It's a rectangle with two square holes in it. It results in an invalid shape being rendered with "unable to triangulate polygon!" warning thrown:

var shape = new THREE.Shape();
shape.moveTo(0, 0);
shape.lineTo(1, 0);
shape.lineTo(1, 1);
shape.lineTo(0, 1);

var windowHole = new THREE.Path();
windowHole.moveTo(0.14999999888241292, 0.7758620689655171)
windowHole.lineTo(0.4999999962747097, 0.7758620689655171)
windowHole.lineTo(0.4999999962747097, 0.3448275862068965)
windowHole.lineTo(0.14999999888241292, 0.3448275862068965)
shape.holes.push(windowHole); 

windowHole = new THREE.Path(); 
windowHole.moveTo(0.5999999955296517, 0.7758620689655171) 
windowHole.lineTo(0.7499999944120646, 0.7758620689655171) 
windowHole.lineTo(0.7499999944120646, 0.6034482758620688) 
windowHole.lineTo(0.5999999955296517, 0.6034482758620688) 
shape.holes.push(windowHole); 

var mesh = new THREE.Mesh(new THREE.ShapeGeometry(shape), this.material);
root.add(mesh);

To see the screenshot of what the above code generates go here: http://stackoverflow.com/questions/21337364/simple-holes-arent-rendered-properly-in-three-js

Is this bug being fixed right now? I tried it with yesterday's pull request and it still doesn't work.

[mrdoob]

Could you try with today's build? https://github.com/mrdoob/three.js/tree/dev/build

[zz85]

(sidetracked: i was looking at some JS GLU tesselators, and although i suspect they should be pretty stable, they come at some size cost too. 112kb - https://github.com/memononen/tess2.js/blob/master/src/tess2.js 152kb - emscripten version https://github.com/claus/libtess2.js/blob/master/libtess2.js)

[saeidN]

wow the version 66dev works perfectly in my application with all different rectangular holes combinations that I tried so far! Thanks mrdoob.

[mrdoob]

@saeidN all thanks to @jahting! ^^

[saeidN]

oh yes, thanks @jahting for coding it. great job!