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

[BeRo]

I do want to share my useful BeRoTriangulation unit here. It's a robust 2D polygon triangulator for non-realtime-usages (or with caching on load time) by combining non-constrained delaunay triangulation with the Bowyer–Watson algorithm 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 and not just only simple polygons.

It needs and uses the Clipper library from http://www.angusj.com/delphi/clipper.php for the polygon clipping work.

And it contains also a second seidel-algorithm-based non-robust variant for realtime-usages.

And here is the link: http://rootserver.rosseaux.net/stuff/BeRoTriangulation.pas

It's licensed under the Boost Software License.

So have a lot fun with it :D

Edit:

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;InputP olygonFillRule:TBeRoTriangulationPolygonFillRule=b tpfrEVENODD;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;InputP olygonFillRule:TBeRoTriangulationPolygonFillRule=b tpfrEVENODD):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):boole an;




// 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):boole an;


with the fill rules:



TBeRoTriangulationPolygonFillRule=(btpfrEVENODD,bt pfrNONZERO,btpfrPOSITIVE,btpfrNEGATIVE,btpfrABSGEQ TWO);


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.

[JC_]

thank you, it can be usefull for my projects :)

[paul_nicholls]

BeRo does it again :D
Nice dude ;)

[laggyluk]

umm.. and what's the use for it? :P

[SilverWarior]

Triangualtion is used in programaticaly creating 2D polygons made from triangles when all you have is just basic imput data like a shape outline of the specific polygon.
It is also commonly used in image vectoriaztion (converting raster image into verctor based image).

[BeRo]

umm.. and what's the use for it? :P

For example for to draw 2D polygons with OpenGL without external gluTess or another external 3rd Triangulation library.

[BeRo]

Triangualtion is used in programaticaly creating 2D polygons made from triangles when all you have is just basic imput data like a shape outline of the specific polygon.
It is also commonly used in image vectoriaztion (converting raster image into verctor based image).

The common image vectorization algorithms are working without triangulation, like my unreleased but for-usage-ready image vectorization algorithm, which I've implemented some years ago. They (at least my algorithm) are working per color image quantization and then greedy from the outside inwards colorwise image contour path tracing together with incremental color plane flipping toward into the inner contour paths.

[laggyluk]

ok, that's cool

[SilverWarior]

The common image vectorization algorithms are working without triangulation, like my unreleased but for-usage-ready image vectorization algorithm, which I've implemented some years ago. They (at least my algorithm) are working per color image quantization and then greedy from the outside inwards colorwise image contour path tracing together with incremental color plane flipping toward into the inner contour paths.

Wel I gues that then I haven't tried to use the most common approach when I was trying to implement image vectorization myself some ten years ago.
In the approach I used I first tried to convert the raster image into a scetch like image (just lines representing objects shapes) and then I was applying a triangualization algorithm to that scetch image.
It worked half of the time which was a huge sucses at that time for me. But I never figured out why it doesen't always works since I didn't know wheter the cause for that might be either in my "scetchink" code or the triangualization code which wasn't mine.
Anywhay after some time I lost interest in that firstly becouse it didn't always work and I had no diea why. Frankly even now I don't know how I managed to make it work even those half times.
Another reason why I lost interest in that is becouse it was extreemly slow. Why it was slow? Becouse at that time I was still working with Canvas.Pixel-s. And what is worse I was working with Images instead of bitmaps which made everything even worse.

[phibermon]

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

[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;InputP olygonFillRule:TBeRoTriangulationPolygonFillRule=b tpfrEVENODD):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;InputP olygonFillRule:TBeRoTriangulationPolygonFillRule=b tpfrEVENODD):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):boole an;


with the fill rules:



TBeRoTriangulationPolygonFillRule=(btpfrEVENODD,bt pfrNONZERO,btpfrPOSITIVE,btpfrNEGATIVE,btpfrABSGEQ TWO);


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;InputP olygonFillRule:TBeRoTriangulationPolygonFillRule=b tpfrEVENODD;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;InputP olygonFillRule:TBeRoTriangulationPolygonFillRule=b tpfrEVENODD):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):boole an;




// 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):boole an;


with the fill rules:



TBeRoTriangulationPolygonFillRule=(btpfrEVENODD,bt pfrNONZERO,btpfrPOSITIVE,btpfrNEGATIVE,btpfrABSGEQ TWO);


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.