Extrude feature has issues when complex paths from text fonts are used

[madhephaestus]

I have been attempting to make an automatic extrusion from text using Javas font's and the PathIterator interface. This is the gist that is working in BowlerStudio demonstrating that the points are being created in a sane way and in the right locations:

https://gist.github.com/madhephaestus/da78cb13a62c1a5c691f

If you uncomment line 45, you will get the error.

I use a simple loop to create the array list of points from the PathIterator then extrude the points with the Extrude.points. This causes this exception:

java.lang.RuntimeException: Intersecting Constraints eu.mihosoft.vrl.v3d.ext.org.poly2tri.DelaunayTriangle@152491d5 is constrained Edge accross [389.1875,-64.78125] at eu.mihosoft.vrl.v3d.ext.org.poly2tri.DTSweep.flipEdgeEvent(DTSweep.java:614) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.DTSweep.flipEdgeEvent(DTSweep.java:654) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.DTSweep.edgeEvent(DTSweep.java:591) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.DTSweep.edgeEvent(DTSweep.java:360) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.DTSweep.sweep(DTSweep.java:136) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.DTSweep.triangulate(DTSweep.java:103) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:127) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:117) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:86) at eu.mihosoft.vrl.v3d.ext.org.poly2tri.PolygonUtil.concaveToConvex(PolygonUtil.java:99) at eu.mihosoft.vrl.v3d.Extrude.extrude(Extrude.java:92) at eu.mihosoft.vrl.v3d.Extrude.points(Extrude.java:82) at eu.mihosoft.vrl.v3d.Extrude$points.call(Unknown Source) at Script1.run(Script1.groovy:57) at com.neuronrobotics.bowlerstudio.scripting.ScriptingEngine.runGroovy(ScriptingEngine.java:376) at com.neuronrobotics.bowlerstudio.scripting.ScriptingEngine.inlineScriptRun(ScriptingEngine.java:340) at com.neuronrobotics.bowlerstudio.scripting.ScriptingEngineWidget$5.run(ScriptingEngineWidget.java:426)

[madhephaestus]

Hmm, the more i think about this, the PathIterator is exactly the interface you would want for creating polygons. It has directionality, quadratic, and bezier built right into the pathing, AND if it was both forward and backwards generatable from polygons, you could implement most of a slicer for 3d printing and all the information you would need to run say a cnc or a laser/water jet cutter...

I have a great interest in this, but i get lost trying to figure out how the polygon function works to fix it.

[miho]

I am using Poly2Tri for converting concave polygons to convex polygons. If your path contains holes then you have to tell the Poly2Tri library that there are holes it has to consider. The JCSG Extrude class only supports simple polygons (no holes, no intersections). Could this be the problem?

[madhephaestus]

Each polygon is a single profile, i was going to worry about the holes and negatives later. As you can see in the picture each color represents a different profile. An interesting new issue is that i can get it to work with Helvetica, but not any serifed fonts...

[madhephaestus]

I noticed i can use Extrude.isCCW(Polygon.fromPoints(points)) to decide if the points are an interior (cutout) or exterior shape!

But still, the Times New Roman is not working, but Helvedica is nearly fully working.

[madhephaestus]

This issue is still a problem, even with the latest update to the triangulation function. The resulting extrusion from certain convex polygons produce erroneous shapes during triangulation. These bad polygons poison the CSG tree and cause fault with any code using them later on. I have come across this bug while implementing a font extrusion feature and also when implementing a DXF loader for JCSG.

[miho]

You pointed out the problem yourself, we only extrude polygons without holes. For more complex cases, poly2tri should be used directly.

For common cases, such as text, we just added a clean api to resolve the issue.

[madhephaestus]

I actually separated out the polygons with holes and resolved the polygon wrapping direction problem to detect "hole" shapes and exterior shapes. This issue arises when certain concave polygons are used to extrude. For example, the outline of lowercase helvedica 'e' becomes invalid because the outside and inside flip at the corner where the 'e' moves from the straight part to the curved part forming the beginning of a concave polygon.

[miho]

Can you create a test case that reproduces the specific issue? Are you sure, it is not related to intersecting edges? This is usually the root of such problems.

[miho]

Anyway, we support text now in version 0.4

[madhephaestus]

Cool, i saw the 3d text add, just merged it in! Ill try to put together a unit test today. I have come across this issue loading fonts, DXF's and 0 radius cylinders. How does the triangulation system deal with points on top of one another? Or 90 degree concave turns in the polygon?

[madhephaestus]

Ok, i think i have figured out what my issue was here. When points repeat or are exactly on top of each other, they create path lengths of 0. Maybe a check on minimum path length and a point merging strategy when points are too close would resolve this in the general case? this would have fixed the cone and duplicate point issue with the same strategy. Could you point me to where a check and merge could happen? I'd be happy to try to implement one in a clean branch so you can merge it in. I am working on loading DXF and SVF vectors, and my ability to check the file sanity before loading is limited. It would be better if it was part of the extrude functionality maybe?