Robustness and collinear points compatibility #17

electroremy · 2018-03-18T18:08:17Z

Hi,

I’m very interested in your LibTessDotNet project :-)

Indeed, polygon triangulation is still a “hot topic” in 2018!

I have a VB.NET project that use Clipper and Poly2Tri to make 2.5D pieces for NC milling machines and 3D printers.

Clipper works fine.

But, as you said, Poly2Tri does not support polygons from Clipper, more specifically vertices with same coordinates or coincident points.

As I reported here (greenm01/poly2tri#110), the problem is that you can’t transform any possible 2D shape in polygon tree structure without coincident points. It’s not possible, so poly2tri cannot be used if your software needs to deal with any possible 2D shape.

Here is an example of 2.5D piece:

http://electroremy.free.fr/GitHub/3D_OK.jpg

The blue horizontal surfaces are clipper polygon tree structure (that is to say, polygon with holes, and inside holes, possibly others polygons with holes).

The yellow vertical surfaces are just “walls” that connect the horizontal surfaces together.

I need polygon triangulation to get all blue horizontal surface triangles.

The yellow vertical triangles (walls) are easy to generate, I just need to create two triangles for each polygon or hole edge.

There is another important thing to understanding here: the “T-junction problem”

The “T-junction problem” is described here: https://blackflux.wordpress.com/2014/02/23/meshing-in-voxel-engines-part-1/

To solve the “T-junction problem”, I have to add some collinear points on the polygons after Clipper processing.

Look at the previous image, in which my program adds all collinear points needed.

Now look at the difference in the next picture, without collinear points; you can see the “T-junction problem” on the bright yellow triangle edge:

http://electroremy.free.fr/GitHub/3D_NOK.jpg

So I need triangulation that:

Is fully Clipper compatible
And also take into account with collinear points added; it’s a very important point because a lot of polygons and triangulation computing software are not compatible with polygons with collinear points.

About numerical robustness, the greatest idea of Clipper is to use integer values. That is to say fixed point arithmetic instead of floating point arithmetic.

Floating point arithmetic is a bad idea when you deals with geometry. Because in floating point arithmetic, the precision is depending on the value, so each time you translate an object, there are rounding errors. So in floating point arithmetic, each time you translate an object you get deformation!

Indeed, in fixed point arithmetic, you get the same precision regardless of object position.

That is to say, fixed point arithmetic XY plane is a regular grid plane, but if you use floating point XY coordinates, your XY plane is a strange and insane “variable pitch” grid. So we should never use floating points to deals with geometric problems.

Also I think the best idea is to get a fixed point arithmetic triangulation process, with 64 bits integer values like in Clipper. These code can also be directly integrated in clipper, with also a code to add collinear instead of re-creating the whole polygon tree structure.

Edit : the most recent Clipper update is here : https://sourceforge.net/p/polyclipping/code/HEAD/tree/

Angus J the author of clipper has published a triangulation beta function in 2017-11-12

Thanks!

PS : I'm french, sorry for bad english :-)

speps · 2018-03-18T20:17:58Z

I'm French too so speak French if you prefer.

However, I don't really understand the issue you want me to take a look at. Is it only that you'd like to use fixed point arithmetic instead of floating point?

If that's what you're asked, I would first suggest to try your geometry through LibTessDotNet and see if there's any issues before making assumptions on wether or not you're going to hit precision issues. More so because you can use double in LibTessDotNet as well and probably completely forget about precision issues. I would also add that my code is based on decades old code that's been very robust in regards to precision so far as it handles comparison very well.

Anyway, feel free to switch to French to explain what you want :)

electroremy · 2018-03-19T07:11:35Z

Hi,

I think we should continue in English, because there are not a lot of people dealing with these kinds of problems, and so English allows everybody to both contribute and use the project.

I’m working on my app since 2010. It’s quite a long (!) and fortunately I found clipper that is both:

robustness
permissive use
can represent 100% of possible 2D shapes.

But for the triangulation problem I still have issues. I’ve made a high number of tests, and the best solution is Poly2Tri but Poly2Tri can’t handle 100% of clipper polygons. In fact, as I explained before, Poly2Tri can’t handle 100% of possible 2D shape, it’s a major issue.

So I found your project, and also I’ve read your discuss between you and Pro100AlexHell.
Before trying your project or the Pro100AlexHell fork, I had to know:

if your code is compatible with collinear points (needed to solve the t-junction problem)
if you have still robustness issues.

Also I’ve a lot of “degenerated” polygon sets to tests my software, it will be useful. But I fear that degenerated case for Poly2Tri are not the same for your software. If it’s true, I had to make again hundred and hundred hours of testing.

I use triangulation just for two things in my app:

3D viewing with Open TK
STL file writing

Indeed, I don’t need triangulation for 2D viewing and NC milling, those are the main functions in my app.

If there are little errors in triangulation:

It doesn’t matter for 3D viewing
In some case it doesn’t matter for STL writing if the errors are just little artefacts, because most of 3D printing software have built-in STL correction.
But if triangulation crashes my app, it’s a real problem.

So if a robust and 100% fail-safe triangulation is impossible, I’m searching for a triangulation algorithm that work in most cases, and can give a “degenerated but nice” triangle mesh instead of crashing in particular cases. I’m sure that video games engines and CAD professional software work in this way.

I try to modify Poly2Tri to catch “EdgeEvent” problem and so modify polygons but it’s very difficult. Poly2Tri can’t handle ANY coincident edge, so in several cases you have to cut a polygon into 2, 3 or more little polygons and there is always a case that fails…

When I talk to you about integers VS. floats, it’s not an issue but an idea. I just think it’s possibly easier to get rid of triangulation issues with integers but I’m not sure.

In 1997 I’ve created a CAD software (CiDess), to draw PCB. It’s still available and update (http://cidess.free.fr/index-fr.html); in CiDess I’ve use integer coordinate values because with floats I’ve get rounding errors when moving parts. So I still think that floating point arithmetic is not a good idea for geometric computing.

Unfortunately today CPUs support only integer and floating number, they don’t support fixed point arithmetic. So when dealing with integers you must use scaling and a lot of double <—> integer conversion. Only specials DSPs support fixed point arithmetic.

Thanks

speps · 2018-03-20T21:27:50Z

Please try the library and see if it works. My philosophy is "try before you buy". Download the project, run the TessBed project and open a .txt file that contains your polygon points (one point per line, extra line to have multiple polygons), see the TessBed/Data folder for examples.

This library IS robust, it's based on libtess which was part of SGI GLU library, more than 18 years ago. If you look at TessBed/UnitTests.cs, you'll find plenty of tests that have degenerate cases that are handled correctly by my library. Running TessBed, you'll also find polygons that intersect in many places and even one that I generated with Clipper some time ago and was crashing Poly2Tri but works with mine.

I do agree that fixed point arithmetic is better for geometry and it could be possible to actually use an arbitrary precision library in LibTessDotNet as I've already done the work to handle float or double.

Just to reiterate my point, please use the library in your software directly, replace Poly2Tri and see where it goes. So many times I've seen projects where people don't make progress because they spend time discussing instead of doing :)

KellanHiggins · 2018-03-22T14:15:53Z

Just have to chime in here. This is a great library and other than zero area triangles (which I submitted a pull request and fixed) it has been nothing but great!

electroremy · 2018-03-22T19:19:00Z

Hi,

I've made some tests with LibTessDotNet and compare the results between Poly2Tri.

Poly2Tri procude better quality meshes than LibTessDotNet
Sometimes LibTessDotNet remove added collinear points in polygons
But Poly2Tri crashes on several sample (EdgeEvent), LibTessDotNet do not crash.

In my app, LibTessDotNet and Poly2Tri have the same speed.

If you want both quality and robustness, you can use Poly2Tri, and if it trows an exeption, then use LibTessDotNet

You can look at the following screenshots to get the difference between Poly2Tri and LibTessDotNet :

Sample "BetC" :
LibTessDotNet : http://electroremy.free.fr/GitHub/BetC_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/BetC_P2T.jpg

Sample "ImageDeLaMort" :
LibTessDotNet : http://electroremy.free.fr/GitHub/ImageDeLaMort_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/ImageDeLaMort_P2T.jpg

Sample "T-Junction" :
LibTessDotNet : http://electroremy.free.fr/GitHub/T-Junction_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/T-Junction_P2T.jpg

Sample "TEST_COLINEAR4" :
LibTessDotNet : http://electroremy.free.fr/GitHub/TEST_COLINEAR4_LibTess.jpg
Poly2Tri : FAIL (EdgeEvent) !

Sample "TEST_COLINEAR5" :
LibTessDotNet : http://electroremy.free.fr/GitHub/TEST_COLINEAR5_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/TEST_COLINEAR5_P2T.jpg

Sample "TEST_COLINEAR6" :
LibTessDotNet : http://electroremy.free.fr/GitHub/TEST_COLINEAR6_LibTess.jpg
Poly2Tri : FAIL (EdgeEvent) !

Sample "TEST_COLINEAR7" :
LibTessDotNet : http://electroremy.free.fr/GitHub/TEST_COLINEAR7_LibTess.jpg
Poly2Tri : FAIL (EdgeEvent) !

Sample "_8bits_OK" :
LibTessDotNet : http://electroremy.free.fr/GitHub/_8bits_OK_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/_8bits_OK_P2T.jpg

Sample "________EXGM" :
LibTessDotNet : http://electroremy.free.fr/GitHub/________EXGM_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/________EXGM_P2T.jpg

Sample "________EXG" :
LibTessDotNet : http://electroremy.free.fr/GitHub/________EXG_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/________EXG_P2T.jpg

Sample "________EX" :
LibTessDotNet : http://electroremy.free.fr/GitHub/________EX_LibTess.jpg
Poly2Tri : http://electroremy.free.fr/GitHub/________EX_P2T.jpg

Thanks

speps · 2018-03-22T20:50:19Z

I do agree that LibTessDotNet doesn't produce perfect looking meshes in respect to triangle sizes. However, for most applications, and actually for applications that it wasn't designed for it's sometimes better. For example, when used with OpenGL, it's not great that it produces long thin triangles but for your use case, I would have thought that you didn't care too much about that.

Regarding the colinear points getting removed, do you have a minimal example that would show the removal that you've seen? You can run TessBed and use the Open button to open a .txt file that contains polygons (the format is the same as the example .dat files). If you attach this file, I can have a look at why it's removing points. I'm not sure if it's a bug or a feature but either way it seems fixable.

Really awesome looking application by the way, it's very similar to what @KellanHiggins is doing but you're actually making a physical object from it from what I could see :)

electroremy · 2018-03-24T00:21:27Z

Hi,

It’s strange because LibTessDotNet does not remove all collinear points…

The sample “T-Junction” has collinear points and both Poly2Tri and LibTessDotNet are OK

But in the “TEST_COLINEAR5” LibTessDotNet remove 4 collinear points

“ImageDeLaMort” and “_8bits_OK” are OK with Poly2Tri but there are a lot of errors with LibTessDotNet

Indeed, collinear points into polygons are often considered as useless or errors.
Unfortunately, collinear points cause robustness problems and crash some algorithms!

Thus, clipper removes collinear points!

I need to add collinear points to solve the “T-junction” problem that is a 3D problem and not a 2D problem. But a lot of software made 3D parts as an assembly of 2D shapes. When you deal with arbitrary 3D shape you should already have a triangle mesh or a point cloud to triangulate, that is a problem completely different.

Indeed, my 3D objects (or rather my 2.5D objects) are a stack of 2D layers connected together with walls.
Each 2D layer is a polygon tree structure (polygon with holes with islands with holes…)

When you deal with a 3D or 2.5D triangle mesh, you get “T-junction” problem that does not exist with a single 2D polygon tree structure.

To solve the “T-junction” it’s necessary to add some collinear points. You can see more explanation and samples here: https://blackflux.wordpress.com/2014/02/23/meshing-in-voxel-engines-part-1/

To get an optimal result, I continue to use Poly2Tri, and when Poly2Tri fails, I use LibTessDotNet as “second chance” triangulation to handle “nasty” polygons. In this way I’ve got both robustness and quality. Better: I can put an option so the user of my software can choose between “Poly2Tri only,” “LibTessDotNet only” and “Poly2Tri / LibTessDotNet 2nd chance.”

Fortunately, the LibTessDotNet artifacts and T-junction problems are very tiny, so it’s OK for 3D viewing and it’s OK for 3D printers software that have built-in corrections.

I think I could check if LibTessDotNet returns “flat” triangle (3 vertex collinear) so I can delete those triangles?

I notice that LibTessDotNet use Z coordinate (that are useless in 2D) and also a “data” object. I think I should remove Z and Data to save memory and increase a little bit speed?

Thanks.

speps · 2018-03-24T15:10:50Z

Okay, I think I understand what you mean for the T-junction issue. I really don't think it removes the points. It would be really good if you could provide test data to reproduce the problem you mention for TEST_COLINEAR5 and when it has a lot of errors. I'm sure it could be solved and might be due to precision as you mentioned before. If it's a precision I can look into arbitrary precision libraries or fixed precision and I think it might be possible to integrate into the library (with a performance impact of course).

Regarding the degenerate triangles, that feature is already here, just set NoEmptyPolygons = true on the Tess instance you create.

electroremy · 2018-03-24T17:57:22Z

Hi

I use NoEmptyPolygons = true

I made some tests with DAT files generation :

DAT.zip

Into the zip you will find :

Poly2Tri 3D view output
LibTessDotNet 3D view output
DAT polygon data for TessBed tool

There are 3 sample :

TEST_COLINEAR5
_8bits_OK
ImageDeLaMort

I think it's possibly a precision issue rather than a colinear problem

Thanks

electroremy · 2018-03-24T18:24:00Z

Thus, I notice that you've just uploaded a new release, but I don't understand changes :-P

Thanks

electroremy · 2018-03-24T19:01:11Z

Hi,

Here is my VB.NET code to use LibTessDotNet :

Private Sub TriangulariserPoly(c As PolyNode)
    Dim c2 As Clipper.PolyNode
    Dim c3 As Clipper.PolyNode
    Dim p1 As Clipper.IntPoint
    Dim p2 As Clipper.IntPoint
    Dim i As Integer
    Dim polyg As List(Of IntPoint)

    Dim Tess As LibTessDotNet.Tess
    Dim TessV() As LibTessDotNet.ContourVertex
    Dim TessTri0 As Integer
    Dim TessTri1 As Integer
    Dim TessTri2 As Integer

	'POLY
	Tess = New LibTessDotNet.Tess
	Tess.NoEmptyPolygons = True
	polyg = Clipper.CleanPolygon(c.Contour)
	Call RestoreColinears(polyg, ListCol)
	TessV = New LibTessDotNet.ContourVertex(polyg.Count - 1) {}
	For i = 0 To polyg.Count - 1
		p1 = polyg.Item(i)
		If i = 0 OrElse p2.X <> p1.X OrElse p2.Y <> p1.Y Then
			TessV(i).Position = New LibTessDotNet.Vec3()
			TessV(i).Position.X = p1.X
			TessV(i).Position.Y = p1.Y
			TessV(i).Position.Z = 0
		End If
		p2 = p1
	Next i
	Tess.AddContour(TessV)

	'POLY'S HOLES:
	For Each c2 In c.Childs
		polyg = Clipper.CleanPolygon(c2.Contour)
		Call RestoreColinears(polyg, ListCol)
		TessV = New LibTessDotNet.ContourVertex(polyg.Count - 1) {}
		For i = 0 To polyg.Count - 1
			p1 = polyg.Item(i)
			If i = 0 OrElse p2.X <> p1.X OrElse p2.Y <> p1.Y Then
				TessV(i).Position = New LibTessDotNet.Vec3()
				TessV(i).Position.X = p1.X
				TessV(i).Position.Y = p1.Y
				TessV(i).Position.Z = 0
			End If
			p2 = p1
		Next i
		Tess.AddContour(TessV)
	Next

	'TRIANGULATION
	Tess.Tessellate(LibTessDotNet.WindingRule.EvenOdd, LibTessDotNet.ElementType.Polygons, 3)

	'GET TRIANGLES
	For i = 0 To Tess.ElementCount - 1
		TessTri0 = Tess.Elements(i * 3)
		TessTri1 = Tess.Elements(i * 3 + 1)
		TessTri2 = Tess.Elements(i * 3 + 2)
		If Not (TessTri0 = -1 OrElse TessTri1 = -1 OrElse TessTri2 = -1) Then
			Call EcrireTriangle(Tess.Vertices(TessTri0).Position.X, Tess.Vertices(TessTri0).Position.Y, Tess.Vertices(TessTri1).Position.X, Tess.Vertices(TessTri1).Position.Y, Tess.Vertices(TessTri2).Position.X, Tess.Vertices(TessTri2).Position.Y)
		End If
	Next

	'ISLANDS (POLYS INTO POLY'S HOLES) :
	For Each c2 In c.Childs
		For Each c3 In c2.Childs
			call TriangulariserPoly(c3)
		Next
	Next
End Sub

Thanks

speps · 2018-03-25T11:43:16Z

Thanks for the data, I'll have a look and try to see if it's fixable.

The new release yesterday was only for fixing a bug I introduced which made the callback be null and crash code in TessBed.

electroremy · 2018-03-25T11:58:10Z

Hi,

Another important thing : I use the "single" version of LibTessDotNet, not the "Double"

Indeed, Poly2Tri works with single, so I would first compare P2T with the single version of LibTess

If you open .DAT files, you can see that it's only Integer "big" values (as it comes from clipper output)

I can give you .DAT files for all samples if you want.

Thanks

electroremy · 2018-03-25T15:27:26Z

Hi,

I made a test with LibTessDotNet.Double

The results are the same

Thanks

speps · 2018-03-26T11:52:08Z

If you pull latest master and run TessBed, you should now be able to load a folder of .dat files. I did that with the files from your DAT.zip file.

However, I couldn't see any errors in any of the models. Could you have a look yourself and point me to one that shows problems? Thanks.

electroremy · 2018-03-26T12:32:38Z

Indeed, the errors are "3D" errors and not 2D errors. That is to say, each polygon triangulation is OK but a polygon "layer" does not match perfectly the others polygon "layer".

The .jpg screenshots of the opened STL files with VisCamView let you see the difference between Poly2Tri and LibTessDotNet.

I get the last version but I can't load a whole folder.

Thanks

speps · 2018-03-26T17:43:07Z

Sorry but the screenshots aren't clear enough for me :) Could you circle or put some text and arrows to show me what I should be paying attention to in the screenshots?

From your code above, I think you should only keep the triangulation output from LibTessDotNet. What I mean here is you keep the triangles and use the indices (TessTri0, TessTri1, TessTri2 in your code) to index into your original vertices (the ones you give to the library, from polyg). If you do as your code above, you're converting from integer to float and lose precision. However, you only need the triangles so just keep the triangles, not the vertices and your final output should be perfect as it's the same coordinates without the loss of precision.

EDIT: to make it easier for you, you could also set Data on each ContourVertex to get the original value you had from polyg

Let me know if that didn't make any sort of sense :)

electroremy · 2018-03-26T19:21:13Z

Hi,

Unfortunatelly, errors are little artefacts so there are difficult to see / I should make special "zoom" screenshots for you

Your idea is very great ! Indeed, I just need to pick the point indexes of triangles instead of coordinates !

Thus I can use data object if there a no relationship between polygon points order and triangle indexes.
As you see I first add external polygon's points in the right order, thus each hole points in the right order (clipper generate clockwise / counterclockwise data for external polygons and holes)

But something is strange : I need to convert integer to float because STL files are made with single values... And in a STL file, dimenssions must be in mm so I have to scale my data and use floats.

.... so ...P2T rounding is better than LibTess rounding ???

...or rounding is different from one polygon layer to other ???

It's a good question I will try this !

Thanks

electroremy · 2018-03-26T19:45:22Z

Hello,

I've just try your idea and the result is ... the same :-D :-/

It's both bad and good news : there is no rounding problem, but a problem

I wonder if the problem would be "extra flat triangles" (with an angle close to 0° but not null) ; because LibTessDotNet generate a lot of "flat triangles" and P2T no too much.

Here is two "zoom" screenshots, you can see the difference between P2T and LibTess

On the LibTess picture, there are missing triangle (18995 instead of 19008) ; one "unmatching edge" is marked with yellow color (it's the famous "T-junction problem")
Also, LibTess generate "extra flat triangles" (with an angle very close to 0° but not null)

LibTess :

P2T :

NB : in the picture there are flat triangle that you can't see (quality part check is right, there is no missing triangles in P2T picture, and no so much missing triangle in LibTess picture)

Thanks

electroremy · 2018-03-26T19:57:21Z

This is another king of LibTess error : "unmatching edges" (in yellow) is produced when 2 points of a poly and 1 point of a hole are on a single triangle edge :

Thanks

speps · 2018-03-26T20:05:14Z

You should try setting NoEmptyPolygons to true on the Tess instance, that removes those degenerate triangles (zero area ones).

electroremy · 2018-03-26T20:09:55Z

Hi,

I've already done it

...
Tess = New LibTessDotNet.Tess
Tess.NoEmptyPolygons = True
...

I think that the "extra flat" triangle don't have null but very small area

Thus, a very flat but very long triangle could have a "not so small" area

Thanks.

electroremy · 2018-03-26T20:12:03Z

Also your LibTessDotNet works fine, and the errors I found are both rare and only little artefacts :-)

But as mathematicians, we prefer no errors :-)

electroremy · 2018-03-26T20:15:14Z

I think a "errorless" code is not robust...

It's like if we can't have both quality and robustness

Most of P2T problems come from "FlipScan" algorithm. It's the FlipScan function that give quality mesh and avoid extra flat triangles.

electroremy · 2018-03-26T20:17:57Z

For my app, the best way to deals with triangulation is to use P2T, and when P2T fails, switch to LibTessDotNet.

...it is not as bad as it looks :-)

electroremy · 2018-03-27T12:19:58Z

Hi

I’ve made others tests…

I decided to not remove zero area and flat triangles. It’s very interesting; with LibTessDotNet:

If you delete flat triangles, the triangle mesh is not correct (you will have an unmatched edge problem and a T-junction problem).
But if you keep flat triangles, the triangle mesh is not correct (you will get an intersecting triangle problem).

On the two next pictures you can see the result with no removing flat triangles, and an explanation on the third picture.

Thanks!

KellanHiggins · 2018-03-27T15:19:29Z

I was having issues with zero area triangles on my project and added a test to remove them. I think it is just a byproduct of the LibTessDotNet, since it loves to make reaaaaaaaaaally long and skinny tris.

electroremy · 2018-03-27T15:39:23Z

Hi

If you dont' want zero area triangles you should:

set Tess.NoEmptyPolygons = True just after made a new Tess object
test for each triangle if Abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) > epsilon

For single values, use 1.0E-44 as epsilon (safer than zero)

Thanks

speps · 2018-03-27T16:06:26Z

That's already what LibTessDotNet does though:

                if (NoEmptyPolygons)
                {
                    var area = MeshUtils.FaceArea(f);
                    if (Math.Abs(area) < Real.Epsilon)
                    {
                        continue;
                    }
                }

With Real.Epsilon being 1.401298E-45F (from C# Single.Epsilon).

speps · 2018-03-27T16:09:18Z

Looking at your diagram, I'll have a look at how it's handled and see if it can be fixed. I wonder if it's the sweeping direction that messes it up.

speps · 2018-03-27T17:03:19Z

I ran a simple test using a similar configuration as your example diagram.

Using tjunction.txt, I got this:

As you can see at the bottom of the screenshot, it produces 2 triangles. I intentionally used very big coordinates for those points. Again, I would love to have an example that reproduces the issue you're talking about, a simple case like I just did :)

EDIT: note this is with 4 points, triangulating ABDC as you said.

electroremy · 2018-03-27T18:02:25Z

Hi

My diagram is not an example

My diagram is just a little part of the picture below:

Here, BDC is the yellow edge

Thanks

speps · 2018-03-27T20:11:47Z

What I tried here is a reasonable reproduceable case, the only way to have that BDC triangle is to actually add that edge as a contour. If you only give 4 points, 1 contour to LibTessDotNet like I did, you do not end up with a triangle in BDC at all.

I just made a new release, as before it shows empty triangles, but now in pink (try with issue6-L), it also includes the "Folder" button in the toolbar (in the sub menu on the right): https://github.com/speps/LibTessDotNet/releases/tag/v1.0.68

I tried all files starting with ImageDeLaMort (name of the image from your screenshot) and none of them showed any pink edges so it doesn't result in empty triangles (I didn't have the "No empty" button checked).

From this, I do not understand what data you're giving to LibTessDotNet, is it different from those .dat files you sent me? In your screenshot, are there really multiple points along the yellow edge? I would guess the problem you're pointing at on the yellow edge is that the number of points doesn't match what's on the vertical edge, right?

I'm really interested in helping you figure out what's wrong :)

electroremy · 2018-03-27T20:28:03Z

Thank you very much !

I can make more accurate tests between P2T and LibTess

I hope I can give you a precise case on a single DAT file

Thanks

electroremy · 2018-03-27T21:22:21Z

Hi

Here is more details:

ZIP file with .DAT file of the polygon, and also 3D STL files:

Files.zip

Poly2Tri OK:

LibTess artefact:

The error is more complex than the diagram... I think that kind of case are difficult to handle

Thanks

electroremy · 2018-03-27T21:42:54Z

Hi

Here is another kind of error (common edge with hole):

Files:
DAT3.zip

Poly2Tri OK:

LibTess artefact:

Thanks

speps · 2018-03-28T16:56:00Z

Regarding that last one, I added a zoom feature to TessBed (not in master yet) and it shows like this.

I don't see anything wrong here, can you explain what is the problem? It's very thin triangles I agree but it's valid triangles.

I'll have a look at the other one.

speps · 2018-03-28T17:02:05Z

For the other one, it's actually exactly the same, very thin triangles.

I don't know why your program removes those triangles but they are totally valid from a mesh perspective. Again, very thin, but valid :)

Do you do any post processing after triangulation to remove those triangles?

EDIT: I just noticed in one of your screenshots, those triangles are visible but the edge is painted yellow. How does the detection that makes them yellow work?

electroremy · 2018-03-29T07:32:09Z

Hi

Your zoom feature is a very good idea, thank you very much !!!

My program does not remove triangles if I do not check the "zero triangle remove" option.

The screen shots are not made with my program, but with VisCAM View software.

VisCAM View is a famous software to check the quality of STL files, but I don't know how it works...

Please mind the "T-junction problem" that is not a 2D but a 3D problem, in an STL file, you should not have "vertex on edge" but edges connected together only at edge. It's the raison why I must preserve or add colinear points.

Here is VisCam View software, you can open the STL files with it : https://drive.google.com/open?id=18aLRkoV0l_IV_PgYbUYDcUczWg2eJDJW

Also in some case my program can't add all colinear points ; but you can compare Poly2Tri STL file between LibTessDotNet STL file to see the difference. As my program give to P2T and to LibTess the same polygon data, it's the best way to understand what appends

In VisCamView:

open an STL file
then you can check quality part know or later
in "View" menu, choose "Shaded + wire frame" to see all triangles
in "View" menu, choose "Check part quality"
in "View" menu, choose "Unmatched edge -> draw on model"
in "View" menu, choose "Intersecting triangle"
then you can rotate and zoom with mouse ; on the bottom of the tool bar at the left, you can witch mouse to "move in xy plane" or "shade an wire" to rotate

I don't understand why P2T and LibTess produce different STL result as the process before and after is the same ; P2T triangle mesh is better quality than LibTess but LibTess seems to bo OK also, just with a lot of long and flat triangle.

Thanks

speps · 2018-03-29T15:43:23Z

I used VisCAM and it does the same issue:

I also tried with MeshLab which seemed recommended for doing that kind of check. Here is the result when trying to show non manifold edges:

With those display options:

So I think it's a VisCAM issue rather than a mesh issue.

To download MeshLab if you want to check for yourself: http://www.meshlab.net/

electroremy · 2018-03-29T19:50:33Z

Thank you very much!!!

What a waste of time! It’s difficult to find out the cause of a problem when you use a software chain. Indeed VisCamView may have a precision issue.

I will check again all my samples with meshlab.

Unfortunately VisCamView is one of the few software that handles colored STL files, a feature that is very useful to me for debugging. In a “color” STL file, for each triangle two unused “attribute” bytes are used to set RGB color as explained here: https://en.wikipedia.org/wiki/STL_(file_format)#Color_in_binary_STL

I wonder if some of my very complicated error checks and correction algorithms in my program are still necessary.

Our exchange will be very useful for the Unity, 3D printing and NC milling community.

We can consider that LibTessDotNet is THE library to use for triangulation. For those who want good quality, it’s simple to use Poly2Tri with a try…catch statement, and to use LibTessDotNet when Poly2Tri fails on a polygon.

Thanks

electroremy · 2018-03-29T20:19:44Z

Geometrical computing is difficult because to debug a program, we need a viewing tool that is both fail-safe and relevant. When we have bugs both on program and viewing tool, it’s a nightmare to find out what’s wrong.

Also the “zoom feature” in TessBed will be useful for everybody, we can both check quality of input and quality of triangulation.

I just have an idea: in the TessBed Window it will be interesting to have a textBox that indicates number of vertices in the current view. It’s a good way to be sure that there are no two or more points too close to be distinguished.

For example, if I see 5 points when the textbox indicates 6 points, which means I need to zoom again to find out a “hidden” point and probably a “hidden” triangle.

Thanks

speps · 2018-03-30T10:24:25Z

Unfortunately VisCamView is one of the few software that handles colored STL files, a feature that is very useful to me for debugging. In a “color” STL file

MeshLab does support that already :)

I'll try to submit the zoom feature in TessBed soon. For now, I'll close this issue. Feel free to re-open if needed.

speps closed this as completed Mar 30, 2018

Robustness and collinear points compatibility #17

Robustness and collinear points compatibility #17

Comments

electroremy commented Mar 18, 2018 • edited Loading

speps commented Mar 18, 2018

electroremy commented Mar 19, 2018 • edited Loading

speps commented Mar 20, 2018

KellanHiggins commented Mar 22, 2018

electroremy commented Mar 22, 2018

speps commented Mar 22, 2018

electroremy commented Mar 24, 2018

speps commented Mar 24, 2018

electroremy commented Mar 24, 2018 • edited Loading

electroremy commented Mar 24, 2018 • edited Loading

electroremy commented Mar 24, 2018

speps commented Mar 25, 2018

electroremy commented Mar 25, 2018

electroremy commented Mar 25, 2018

speps commented Mar 26, 2018

electroremy commented Mar 26, 2018

speps commented Mar 26, 2018 • edited Loading

electroremy commented Mar 26, 2018

electroremy commented Mar 26, 2018 • edited Loading

electroremy commented Mar 26, 2018 • edited Loading

speps commented Mar 26, 2018

electroremy commented Mar 26, 2018

electroremy commented Mar 26, 2018

electroremy commented Mar 26, 2018

electroremy commented Mar 26, 2018

electroremy commented Mar 27, 2018

KellanHiggins commented Mar 27, 2018

electroremy commented Mar 27, 2018

speps commented Mar 27, 2018

speps commented Mar 27, 2018

speps commented Mar 27, 2018 • edited Loading

electroremy commented Mar 27, 2018 • edited Loading

speps commented Mar 27, 2018

electroremy commented Mar 27, 2018

electroremy commented Mar 27, 2018

electroremy commented Mar 27, 2018

speps commented Mar 28, 2018

speps commented Mar 28, 2018 • edited Loading

electroremy commented Mar 29, 2018

speps commented Mar 29, 2018 • edited Loading

electroremy commented Mar 29, 2018

electroremy commented Mar 29, 2018

speps commented Mar 30, 2018

electroremy commented Mar 18, 2018 •

edited

Loading

electroremy commented Mar 19, 2018 •

edited

Loading

electroremy commented Mar 24, 2018 •

edited

Loading

electroremy commented Mar 24, 2018 •

edited

Loading

speps commented Mar 26, 2018 •

edited

Loading

electroremy commented Mar 26, 2018 •

edited

Loading

electroremy commented Mar 26, 2018 •

edited

Loading

speps commented Mar 27, 2018 •

edited

Loading

electroremy commented Mar 27, 2018 •

edited

Loading

speps commented Mar 28, 2018 •

edited

Loading

speps commented Mar 29, 2018 •

edited

Loading