tessellation

[Usnul]

Hi, i noticed some over-tessellation happening, shapes that could be split into a few triangle instead end up being inefficiently sub-divided into more than optimal number of triangles. I'm not sure if this has much to do with the fact that input geometry is tessellated itself. For instance you can see here that something odd is happening on the red surface facing the observer, especially towards the top edge, there are clearly 2 triangles where only 1 is necessary in subtraction case:
https://github-camo.global.ssl.fastly.net/3c59c49f85dc01a6691a44ffda53f6b0659f775c/687474703a2f2f6576616e772e6769746875622e636f6d2f6373672e6a732f696d6167652e706e67
in your example at
http://evanw.github.io/lightgl.js/tests/csg.html
in

a.intersect(b).subtract(c.union(d).union(e))

you can see that upper rim is being split into two bands, this introduces additional vertices along the interaction of those bands, these are quite clearly unnecessary. Perhaps add an optimization pass to merge triangles that are adjacent and lie in the same plane. Maybe even go as far as converting all such triangle groups into shapes and throwing them at GL tessellator. This will probably slow down geometry construction, so i would suggest an optimization routine if these artifacts are not due to "buggy" implementation.

PS:
awesome library by the way

[janhelleman]

The problem you are refering to happens because all polygons are tested against planes, and if intersecting with the plane (read plane, not polygon to polygon) split into two to be distributed as front or back sorted nodes. This happens through a recursive function that only stops when an end point is reached.

To get rid of the overhead of triangles a triangulation code has to be written. This means finding edges and holes, sorting them, and applying a triangulation technique instead of the rather simplified triangulation at hand in this code. Read up on delaunay triangulation or earclipping. Both can be used with holes, but earclipping is tricky with it.