BeRoTriangulation - A robust 2D polygon triangulator for simple and complex polygons

[BeRo]

Do you know how many years I've been looking for tessellation lib I can compile in without using GLU? this is awesome!

Now you're versed in the techniques, can you give me some keywords or your thinking on how to make this viable for 3D geometry? I'm guessing a 3D lib for constructive solid geometry similar to what clipper does for 2D would be needed first?

I've studied the source to the GLU tesselator and I'm thinking of doing a pascal port so I can tessellate on platforms without GLU

I'm writing a third Triangulate function variant in the moment, which will support all known polygon fill rules from gluTess, even.odd, non-zero, positive, negative and greater equal than two, so the unit will have then Triangulate functions, once fiexible robust, once just very robust clipper-unit-based, and once fast. But this third function variant isn't finished yet.

And yes, my unit is only for 2D, so you do need to do 3D-to-2D planar projection like gluTess does it also.

[BeRo]

I've updated the BeRoTriangulation.pas now, so the unit contains three different triangulator implementation variants:

// The flexible semi-robust variant by my own scanline-rasterization-like sweeping algoritm. Algorithm steps:
// 1. Add edges from input polygons
// 2. Split intersecting edges
// 3. Split edges at Y coordinates of all polygon points (including these of intersection edge intersection points)
// 4. Construct y-monotone quads (with a trapezoid-style shape) with scanline-rasterization-like sweeping from
//    top to bottom and from left to right with the wished polygon fill rule
// 5. Optimize and merge these quads from step 4. as far as possible
// 6. Triangulate these quads and construct the final output triangles
// This variant is still experimental, so do use this function variant on your own risk! :-)
// It works for the most all cases, but it outputs more triangles than the both other function variants.
function TriangulateBeRo(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles;InputPolygonFillRule:TBeRoTriangulationPolygonFillRule=btpfrEVENODD):boolean;

// Slow bruteforce-style very robust variant with delaunay algorithm, clipping and earclipping for non-realtime usages
// A robust 2D polygon triangulator by combining non-constrained delaunay triangulation as first pass with polygon
// clipping as middle pass and ear clipping as final pass, so it supports even self-intersecting polygon with holes
// as input. It needs and uses the Clipper library from http://www.angusj.com/delphi/clipper.php for the polygon
// clipping work.
// It doesn't support the btpfrABSGEQTWO polygon fill rule
function TriangulateDelaunayClipping(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles;InputPolygonFillRule:TBeRoTriangulationPolygonFillRule=btpfrEVENODD):boolean;

// Faster non-robust variant with seidel algorithm for realtime usages
// It supports only the even-odd polygon fill rule in this current implementation, and it can handle only simple polygons (with and without holes)
function TriangulateSeidel(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles):boolean;

with the fill rules:

     TBeRoTriangulationPolygonFillRule=(btpfrEVENODD,btpfrNONZERO,btpfrPOSITIVE,btpfrNEGATIVE,btpfrABSGEQTWO);

The TriangulateBeRo variant does support all from gluTess known polygon fill rules: evenodd, nonzero, positive, negative and abs_geq_two

[BeRo]

Here is my 3D triangle-based constructive solid geometry unit: http://rootserver.rosseaux.net/stuff/BeRoCSGBSP.pas just replace the GDFWMath 3D math stuff with your own 3D math library stuff.

[BeRo]

I've updated the BeRoTriangulation.pas again, so the unit contains four different triangulator implementation variants:

// The flexible semi-robust variant by my own scanline-rasterization-like sweeping algoritm. Algorithm steps:
// 1. Add edges from input polygons
// 2. Split intersecting edges
// 3. Split edges at Y coordinates of all polygon points including these of intersection edge intersection points
// 4. Construct y-monotone quads with a trapezoid-style shape with scanline-rasterization-like sweeping from
//    top to bottom and from left to right with the wished polygon fill rule
// 5. Optimize and merge the output from step 4. as far as possible
// This variant is still experimental, so do use this function variant on your own risk! :-)
// It works already pretty good, but it is still in progress.
function TriangulateBeRo(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles;InputPolygonFillRule:TBeRoTriangulationPolygonFillRule=btpfrEVENODD;Quality:longint=$7fffffff):boolean;

// Slow bruteforce-style very robust variant with delaunay algorithm, clipping and earclipping for non-realtime usages
// A robust 2D polygon triangulator by combining non-constrained delaunay triangulation as first pass with polygon
// clipping as middle pass and ear clipping as final pass, so it supports even self-intersecting polygon with holes
// as input. It needs and uses the Clipper library from http://www.angusj.com/delphi/clipper.php for the polygon
// clipping work.
// It doesn't support the btpfrABSGEQTWO polygon fill rule, and the output depends on the correctness/accuracy of the
// 3rd-party clipper library
function TriangulateDelaunayClipping(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles;InputPolygonFillRule:TBeRoTriangulationPolygonFillRule=btpfrEVENODD):boolean;

// Faster non-robust variant with seidel algorithm for realtime usages
// It supports only the even-odd polygon fill rule in this current implementation, and it can handle only simple polygons (with and without holes)
function TriangulateSeidel(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles):boolean;

// Faster non-robust variant with ear clipping algorithm for realtime usages
// It can handle only non-self-intersecting simple polygons without holes
function TriangulateEarClipping(const InputPolygon:TBeRoTriangulationPolygon;var OutputTriangles:TBeRoTriangulationTriangles):boolean;

with the fill rules:

     TBeRoTriangulationPolygonFillRule=(btpfrEVENODD,btpfrNONZERO,btpfrPOSITIVE,btpfrNEGATIVE,btpfrABSGEQTWO);

The TriangulateBeRo variant does support all from gluTess known polygon fill rules: evenodd, nonzero, positive, negative and abs_geq_two

TriangulateBeRo is the best flexible and robust variant, followed by TriangulateDelaunayClipping. But TriangulateDelaunayClipping is depending on the correctness/accuracy of the 3rd-party clipper library. TriangulateSeideland TriangulateEarClipping are faster non-robust triangulation functions for faster usages for example for realtime stuff.