memononen/libtess2

Game and tools oriented refactored version of GLU tesselator.

libtess2's Issues

Add CMakelists and fix warnings

Hi @memononen ,

I know that you're not maintaining this library anymore. Still, I'm currently using it in https://github.com/vgc/vgc, and I've made very small changes:

• Adding a CMakeLists.txt file
• Fixing a compiler warning

See: master...vgc:vgc-mods

Would it make sense if I submit pull requests with the above changes, and then if you bump the version to 1.0.3? Note that before doing the PRs, I would improve the CMakeLists.txt a little: I'm currently printing a message which was okay in my use case, but is most likely undesirable for other clients.

One other option might be that I become the official maintainer, if that sounds like something you'd be interested in.

Thanks for this great library,

Boris

Document GLU implementation used as starting point

It would be interresting to document the initial GLU source code location/revision you used as starting point, as GLU seems to live on (slowly) in Mesa (http://cgit.freedesktop.org/mesa/glu/).

Just an user feedback.

I've tried a lot of libraries to replace the glu tessselator and this is the first one to give me
consistant (and correct) results.

As a thank you, I want to offer you my first impressions on the api as an user :

Globally the library is easy to use and more expressive than glu (no need to define edgeCallback
to get only triangles, no need to use gluTessNormal to inform that only x and y are used...).

For tessTesselate I've found 'polySize' and 'vertexSize' not to be enought expressive names :
it was not immediatly clear that this was only for defining the output format.

For tessAddContour, it's specified that only tessReal is accepted but :

• reading the function signature it's not that clear that this means 'only float'
• it will be nice to have a parameter to specify the type, like it's done in the opengl api,
  so libtess2 could do the conversion internally if necessary

After tessTesselate, the result is accessible throught getter like tessGetVertices. I've not
found (in tesselator.h) how much time the returned arrays are valid. I assume this is till the
next call to tessTesselate, but maybe it's till the next call to tessAddContour, or else ?

If the library segfault, it's not obvious what went wrong even with NDEBUG not defined,
not a big issue as the interface is still simple it's relatively easy to check everything.

Again, theses are just my personnal impressions so feel free to ignore them if you find them
not relevant.

setjmp in tess.c crashes when using a custom allocator

its an alignment issue because jumpbuf needs to be aligned to 16 bytes, so I had to make sure my custom allocator was aligning stuff to 16 byte boundaries (instead of 8 bytes as indicated by alignof(std::max_align_t))

it was a little bit frustrating to figure this out, so if setjmp is really absolutely necessary for memory management, then in the comment about TESSalloc it should mention that it needs to return buffers aligned to 16-byte boundaries, or add an "alignment" parameter to memalloc since I'm pretty sure only the TESStesselator needs to be aligned anyway

Crash tessellating very thin quad

Passing the following quad to glutess2 causes a crash in sweep.c:499:
RegionAbove(regUp)->dirty = regUp->dirty = TRUE;

9.5,7.5,-0.5
9.5,2,-0.5
9.5,2,-0.4999999701976776123
9.5,7.5,-0.4999999701976776123

The test cmd-line tool at https://github.com/openscad/libtess2/tree/test can be used to easily reproduce.

Backtrace:

  * frame #0: 0x000000010004fea0 polyhole-tessellator-libtess2`CheckForRightSplice(tess=0x0000000101406230, regUp=0x0000000101809830) + 608 at sweep.c:499
    frame #1: 0x0000000100050e5f polyhole-tessellator-libtess2`CheckForIntersect(tess=0x0000000101406230, regUp=0x0000000101809830) + 2143 at sweep.c:630
    frame #2: 0x00000001000501cc polyhole-tessellator-libtess2`WalkDirtyRegions(tess=0x0000000101406230, regUp=0x0000000101809830) + 652 at sweep.c:775
    frame #3: 0x000000010004fa46 polyhole-tessellator-libtess2`AddRightEdges(tess=0x0000000101406230, regUp=0x0000000101809830, eFirst=0x000000010180c348, eLast=0x000000010180c348, eTopLeft=0x000000010180c348, cleanUp=1) + 918 at sweep.c:395
    frame #4: 0x000000010004f046 polyhole-tessellator-libtess2`ConnectLeftVertex(tess=0x0000000101406230, vEvent=0x000000010181c478) + 742 at sweep.c:1017
    frame #5: 0x000000010004e905 polyhole-tessellator-libtess2`SweepEvent(tess=0x0000000101406230, vEvent=0x000000010181c478) + 101 at sweep.c:1043
    frame #6: 0x000000010004e1df polyhole-tessellator-libtess2`tessComputeInterior(tess=0x0000000101406230) + 255 at sweep.c:1312
    frame #7: 0x00000001000549d8 polyhole-tessellator-libtess2`tessTesselate(tess=0x0000000101406230, windingRule=0, elementType=3, polySize=3, vertexSize=3, normal=0x0000000000000000) + 456 at tess.c:1032

Variable inspection at time of crash:

New Release?

Just noticed 7 commits since last release.

Is the master branch stable enough now for another release?

Better triangulation of regions

I notice that after identifying monotone regions, the region is triangulated into a triangle fan using a relatively naive technique. This generates triangles without regard to their aspect ratio, and even tends to generate "zero triangles" (three collinear vertices).
Now, for rendering, this usually not a problem, but for other uses it causes problems, e.g. due to these triangles not having a normal vector and thus don't live in a well-defined plane.

Have you thought about rewriting the triangle fanning code to produce better triangles, or are you interested in accepting such patches?

I realize that for rendering of strips, fanning is more performant than other organizations, but we could make this an option.

Non Deterministic Now!

So I updated to the latest commit (8862c3f) and running on the build farm gives me non-deterministic results from each run producing differences each time. This wasn't the case before. It's hard to see what is wrong.

This update solved a number of crashing problems I had with collinear verts so was excited when it was updated.

Here's a typical build-farm run showing the diffs etc.
Images.zip

I'll try to set-up a test to show this ASAP.

Getting wrong Triangles when trying to tesselate

I have been trying to use libtess2 to do some tesselation. And in some cases I am getting the wrong triangles. I have included one set of points in which I am getting the wrong output.

std::vector Points{1.3515, -0.8156, 1.3672, -0.8156, 1.3329, -0.5057, 1.3174, -0.5057};
TESStesselator* pTess = tessNewTess(nullptr);
tessAddContour(pTess, 2, Points.data(), 2 * sizeof(float), 4);
tessTesselate(pTess, TESS_WINDING_NONZERO, TESS_POLYGONS, 3, 2, 0);

I have accounted for the order of vertices using tessGetVertexElements and matched the right indexes from tessGetElements. With or without it, either way, the resulting triangles seem weird.

is the triangle I am getting from this.

Am I missing something from the way I call the functions ? Or is there something else that I need to do to get the right triangles?

assertion when processing a degenerate rectangle

The assertion is thrown in tesedgeSign:

TESSreal tesedgeSign( TESSvertex *u, TESSvertex *v, TESSvertex *w )
{
    /* Returns a number whose sign matches EdgeEval(u,v,w) but which
    * is cheaper to evaluate.  Returns > 0, == 0 , or < 0
    * as v is above, on, or below the edge uw.
    */
    TESSreal gapL, gapR;

    assert( VertLeq( u, v ) && VertLeq( v, w )); // ASSERTION THROWN HERE

    gapL = v->s - u->s;
    gapR = w->s - v->s;

    if( gapL + gapR > 0 ) {
        return (v->t - w->t) * gapL + (v->t - u->t) * gapR;
    }
    /* vertical line */
    return 0;
}

in geom.c.

The cause seems to be that it is processing a rectangle where all the x cooordinates are the same (so the rectangle is just a line) and the first and last points are the same:

11333544,13772171
11333544,13772299
11333544,13772107
11333544,13772171

It would be great if libtess2 could handle degenerate cases gracefully.

tessTesselate infinite loop

Hi from Unity again! We're seeing the occasional "freeze" reported in libtess2 from the PolygonCollider2D. The following code consistently freezes it it 'tessMeshMergeConvexFaces'. Last report honest!

{
    struct vec2
    {
        vec2(float _x, float _y)
            : x(_x)
            , y(_y)
        {}

        float x;
        float y;
    };
    vec2 points[232] =
    {
        vec2(-0.373205036f, -0.330940127f),
        vec2(-0.0999999940f, -0.0577350110f),
        vec2(0.000000000f, 0.000000000f),
        vec2(0.0999999866f, 0.173205078f),
        vec2(0.199999973f, 0.000000000f),
        vec2(0.399999976f, 0.000000000f),
        vec2(0.600000024f, 0.000000000f),
        vec2(0.700000048f, 0.173205197f),
        vec2(0.800000131f, 0.346410304f),
        vec2(0.700000107f, 0.446410298f),
        vec2(0.563397527f, 0.483012855f),
        vec2(0.600000143f, 0.619615376f),
        vec2(0.700000107f, 0.561880350f),
        vec2(0.800000191f, 0.735085368f),
        vec2(0.600000203f, 0.735085487f),
        vec2(0.600000143f, 0.619615436f),
        vec2(0.463397622f, 0.656218052f),
        vec2(0.500000238f, 0.792820573f),
        vec2(0.463397771f, 0.929423153f),
        vec2(0.600000381f, 0.966025591f),
        vec2(0.600000262f, 0.850555539f),
        vec2(0.800000250f, 0.850555420f),
        vec2(0.700000346f, 1.02376056f),
        vec2(0.600000322f, 0.966025591f),
        vec2(0.563397825f, 1.10262811f),
        vec2(0.700000405f, 1.13923061f),
        vec2(0.800000489f, 1.23923051f),
        vec2(0.900000393f, 1.13923049f),
        vec2(0.800000370f, 1.08149552f),
        vec2(0.900000274f, 0.908290386f),
        vec2(1.00000048f, 1.08149540f),
        vec2(0.900000513f, 1.13923049f),
        vec2(1.10000050f, 1.13923037f),
        vec2(1.20000029f, 0.966025174f),
        vec2(1.10000038f, 1.02376032f),
        vec2(1.00000024f, 0.850555301f),
        vec2(1.20000029f, 0.850555182f),
        vec2(1.20000041f, 0.966025233f),
        vec2(1.30000019f, 0.792820036f),
        vec2(1.20000005f, 0.619615018f),
        vec2(1.20000017f, 0.735085070f),
        vec2(1.00000012f, 0.735085249f),
        vec2(1.09999990f, 0.561880052f),
        vec2(1.19999993f, 0.619614959f),
        vec2(1.23660231f, 0.483012378f),
        vec2(1.09999979f, 0.446410000f),
        vec2(1.00000012f, 0.346410245f),
        vec2(1.20000005f, 0.346410275f),
        vec2(1.10000002f, 0.173205197f),
        vec2(1.30000007f, 0.173205212f),
        vec2(1.20000005f, 0.000000000f),
        vec2(1.09999919f, -0.173204690f),
        vec2(1.30000007f, -0.173204988f),
        vec2(1.20000005f, -0.346410096f),
        vec2(1.40000010f, -0.346410125f),
        vec2(1.30000007f, -0.519615233f),
        vec2(1.40000010f, -0.692820311f),
        vec2(1.50000012f, -0.866025388f),
        vec2(1.40000021f, -1.03922975f),
        vec2(1.60000014f, -1.03923047f),
        vec2(1.50000012f, -1.21243548f),
        vec2(1.40000021f, -1.38564014f),
        vec2(1.30000043f, -1.55884552f),
        vec2(1.40000057f, -1.65884542f),
        vec2(1.50000060f, -1.83205056f),
        vec2(1.40000057f, -1.77431548f),
        vec2(1.30000067f, -1.94752061f),
        vec2(1.50000072f, -1.94752038f),
        vec2(1.50000072f, -1.83205032f),
        vec2(1.60000074f, -2.00525546f),
        vec2(1.50000060f, -2.17846060f),
        vec2(1.50000072f, -2.06299043f),
        vec2(1.30000067f, -2.06299067f),
        vec2(1.40000081f, -2.23619556f),
        vec2(1.50000072f, -2.17846036f),
        vec2(1.40000176f, -2.35166526f),
        vec2(1.30000222f, -2.45166564f),
        vec2(1.20000172f, -2.35166621f),
        vec2(1.30000162f, -2.29393077f),
        vec2(1.20000112f, -2.12072587f),
        vec2(1.10000145f, -2.29393125f),
        vec2(1.20000160f, -2.35166621f),
        vec2(1.10000169f, -2.45166636f),
        vec2(1.00000155f, -2.35166645f),
        vec2(0.963398576f, -2.48826909f),
        vec2(1.00000143f, -2.62487149f),
        vec2(0.863398910f, -2.66147447f),
        vec2(0.863398671f, -2.54600430f),
        vec2(0.663398683f, -2.54600453f),
        vec2(0.763398886f, -2.71920943f),
        vec2(0.863398731f, -2.66147399f),
        vec2(0.900001764f, -2.79807639f),
        vec2(1.00000167f, -2.69807625f),
        vec2(1.10000181f, -2.79807615f),
        vec2(1.00000191f, -2.85581136f),
        vec2(1.10000205f, -3.02901626f),
        vec2(1.20000184f, -2.85581112f),
        vec2(1.10000169f, -2.79807615f),
        vec2(1.20000160f, -2.69807601f),
        vec2(1.30000174f, -2.79807591f),
        vec2(1.33660424f, -2.66147280f),
        vec2(1.30000150f, -2.52487040f),
        vec2(1.43660402f, -2.48826766f),
        vec2(1.43660414f, -2.60373759f),
        vec2(1.63660419f, -2.60373735f),
        vec2(1.53660405f, -2.43053246f),
        vec2(1.43660414f, -2.48826814f),
        vec2(1.40000176f, -2.35166526f),
        vec2(1.53660357f, -2.31506276f),
        vec2(1.73660362f, -2.31506228f),
        vec2(1.63660371f, -2.37279749f),
        vec2(1.73660421f, -2.54600215f),
        vec2(1.83660352f, -2.37279677f),
        vec2(1.73660326f, -2.31506205f),
        vec2(1.93660331f, -2.31506133f),
        vec2(2.03660393f, -2.48826599f),
        vec2(1.93660378f, -2.43053150f),
        vec2(1.83660424f, -2.60373688f),
        vec2(2.03660417f, -2.60373664f),
        vec2(2.03660393f, -2.48826647f),
        vec2(2.17320657f, -2.52486873f),
        vec2(2.13660431f, -2.66147137f),
        vec2(2.17320704f, -2.79807377f),
        vec2(2.03660464f, -2.83467674f),
        vec2(2.03660440f, -2.71920657f),
        vec2(1.83660436f, -2.71920705f),
        vec2(1.93660450f, -2.89241195f),
        vec2(2.03660440f, -2.83467674f),
        vec2(2.07320714f, -2.97127914f),
        vec2(1.93660474f, -3.00788212f),
        vec2(1.83660483f, -3.10788226f),
        vec2(1.73660469f, -3.00788236f),
        vec2(1.83660460f, -2.95014715f),
        vec2(1.73660445f, -2.77694225f),
        vec2(1.63660479f, -2.95014763f),
        vec2(1.73660493f, -3.00788260f),
        vec2(1.63660502f, -3.10788274f),
        vec2(1.53660464f, -3.00788307f),
        vec2(1.50000215f, -3.14448571f),
        vec2(1.53660500f, -3.28108811f),
        vec2(1.40000248f, -3.31769109f),
        vec2(1.40000224f, -3.20222092f),
        vec2(1.20000219f, -3.20222116f),
        vec2(1.30000234f, -3.37542605f),
        vec2(1.40000224f, -3.31769085f),
        vec2(1.43660510f, -3.45429325f),
        vec2(1.30000257f, -3.49089622f),
        vec2(1.20000267f, -3.59089637f),
        vec2(1.10000253f, -3.49089646f),
        vec2(1.20000243f, -3.43316126f),
        vec2(1.10000229f, -3.25995636f),
        vec2(1.00000262f, -3.43316174f),
        vec2(1.10000277f, -3.49089670f),
        vec2(1.00000286f, -3.59089684f),
        vec2(0.900002718f, -3.49089694f),
        vec2(0.763400078f, -3.45429468f),
        vec2(0.800002337f, -3.31769204f),
        vec2(0.900002480f, -3.37542677f),
        vec2(1.00000226f, -3.20222163f),
        vec2(0.800002277f, -3.20222187f),
        vec2(0.800002396f, -3.31769204f),
        vec2(0.663399816f, -3.28108954f),
        vec2(0.700002193f, -3.14448690f),
        vec2(0.663399458f, -3.00788450f),
        vec2(0.800001919f, -2.97128177f),
        vec2(0.800002158f, -3.08675170f),
        vec2(1.00000215f, -3.08675146f),
        vec2(0.900002003f, -2.91354656f),
        vec2(0.800002098f, -2.97128177f),
        vec2(0.763399243f, -2.83467937f),
        vec2(0.663399577f, -2.93467975f),
        vec2(0.563399255f, -2.83468008f),
        vec2(0.663399041f, -2.77694464f),
        vec2(0.563398480f, -2.60373998f),
        vec2(0.463399172f, -2.77694535f),
        vec2(0.563399434f, -2.83467984f),
        vec2(0.463399887f, -2.93468022f),
        vec2(0.363399416f, -2.83468080f),
        vec2(0.226796716f, -2.79807878f),
        vec2(0.263398767f, -2.66147614f),
        vec2(0.363398969f, -2.71921062f),
        vec2(0.463398546f, -2.54600525f),
        vec2(0.263398528f, -2.54600549f),
        vec2(0.263398647f, -2.66147566f),
        vec2(0.126796067f, -2.62487316f),
        vec2(0.163398430f, -2.48827052f),
        vec2(0.126795709f, -2.35166812f),
        vec2(0.263398170f, -2.31506538f),
        vec2(0.263398379f, -2.43053532f),
        vec2(0.463398397f, -2.43053508f),
        vec2(0.363398254f, -2.25733018f),
        vec2(0.263398409f, -2.31506538f),
        vec2(0.226795480f, -2.17846298f),
        vec2(0.363397956f, -2.14186001f),
        vec2(0.463397712f, -2.04185987f),
        vec2(0.563397944f, -2.14185953f),
        vec2(0.463398069f, -2.19959474f),
        vec2(0.563398421f, -2.37279963f),
        vec2(0.663398087f, -2.19959426f),
        vec2(0.563398004f, -2.14185929f),
        vec2(0.663397908f, -2.04185915f),
        vec2(0.763398290f, -2.14185882f),
        vec2(0.800000787f, -2.00525618f),
        vec2(0.763397992f, -1.86865366f),
        vec2(0.900000513f, -1.83205092f),
        vec2(0.900000751f, -1.94752097f),
        vec2(1.10000074f, -1.94752073f),
        vec2(1.00000060f, -1.77431571f),
        vec2(0.900000632f, -1.83205080f),
        vec2(0.863397956f, -1.69544828f),
        vec2(1.00000048f, -1.65884566f),
        vec2(1.10000026f, -1.55884552f),
        vec2(0.900000274f, -1.55884564f),
        vec2(0.800000131f, -1.38564062f),
        vec2(0.700000107f, -1.21243548f),
        vec2(0.500000238f, -1.32790589f),
        vec2(0.426795065f, -1.25470090f),
        vec2(0.400000036f, -1.15470088f),
        vec2(0.499999940f, -1.09696567f),
        vec2(0.399999887f, -1.03923070f),
        vec2(0.399999887f, -0.923760653f),
        vec2(0.499999851f, -0.866025567f),
        vec2(0.599999845f, -0.923760533f),
        vec2(0.699999809f, -0.866025448f),
        vec2(0.799999654f, -0.692820251f),
        vec2(0.899999499f, -0.519615054f),
        vec2(0.799999356f, -0.346410036f),
        vec2(0.699999213f, -0.173205033f),
        vec2(0.500000000f, -0.173205078f),
        vec2(0.299999982f, -0.173205093f),
        vec2(0.0999999866f, -0.173205078f),
        vec2(0.000000000f, -0.230940104f)
    };

    TESStesselator* tess = tessNewTess(NULL);
    tessAddContour(tess, 2, points, sizeof(vec2), 232);
    tessTesselate(tess, TESS_WINDING_ODD, TESS_POLYGONS, 8, 2, NULL);
    tessDeleteTess(tess);
}

tess->outOfMemory not initialized

Hi,

the variable TESStesselator::outOfMemory is never initialized, causing (randomly) the tessTessellate() function to return 0.

I just fixed by adding: tess->outOfMemory = 0; to the beginning of the tessTesselate() function.

Best Regards.

Wrong output of specific polygon

Hi Mikko
I'm a C++ developer from China. Thank you for contributing this great library.
However, I find something wrong when I draw a rectangle with a hole which has 2 coincident edges. The version is v1.0.2.
As shown below, When I draw a rectangle(0->1->2->3) with a hole(4->5->6->7). Line 56 coincides with Line 32, and Line 01 coincides with Line 47.
Forgive me that I can't attach my source code for some reason. My code like this:

tessAddContour(tess, 2, polyPoints[0], 2 * sizeof(float), 4);
tessAddContour(tess, 2, polyPoints[1], 2 * sizeof(float), 4);

tessTesselate(tess, TessWindingRule::TESS_WINDING_ODD, TessElementType::TESS_POLYGONS, 3, 2, 0);

triangleVerts = tessGetVertices(tess);
elemCount = tessGetElementCount(tess);
triangleElems = tessGetElements(tess);

After that, I find that elemCount is 3, and I calculate the output triangles by triangleVerts and triangleElems in TESS_POLYGONS way. I get only 3 triangles:
(0,5,3)(5,0,4)(2,7,1). After renderring, my output picture shown like this below. One triangle (2,7,6) is missing.

I'm confused and I've done many experiments. I find that this commit will cause my problem. I am sure about this. I would be very greatful if you can point the connection between this "<=" and my problem, Or maybe my code is wrong?

Why is regUp marked as "dirty" in CheckForXXXX?

hi!

I am very interested in the tesselation algorithm, but I do not understand the following code from CheckForXXXX:

RegionAbove(regUp)->dirty = regUp->dirty = TRUE;

regUp and regLo have been processed after calling CheckForXXXX and the dictionary edge ordering has been corrected.

So I think we only need mark RegionAbove(regUp) as "dirty".

Why is also regUp marked as "dirty"?

Thanks!

Degenerate Triangle

Is it expected that the lib can produce degenerate triangles? I had a case which was giving me a 0,0,0 normal for the first polygon and a degenerate triangle was to blame. This is not a big deal as its easy to process out now that I am aware of this possibility, but I wanted to check in case its considered a bug.

Colinear triangle when convex contour has colinear points on vertical right side

Hi,

I'm not sure if this is a bug or design limitation, but: the tesselator appears to create a colinear triangle (e.g. a triangle where all 3 vertices are colinear) if the input is a single contour with colinear vertices on a vertical right side.

Here's my test program.

static void test()
{
	float v[10] = {
		-20.0, 	5.00,
		0.00,		5.00,
		0.00,		15.00,
		0.00,		 25.00,
		-20.0,		 25.00
	};
	
	TESStesselator * t = tessNewTess(nullptr);
	
	tessAddContour(t, 2, v, 2 * sizeof(float), 5);

	float nrm[3] = { 0, 0, 1 };

	int ok = tessTesselate(t, TESS_WINDING_POSITIVE, TESS_POLYGONS, 3, 2, nrm);
	
	if(ok)
	{
		const float * v = tessGetVertices(t);
		int ic = tessGetElementCount(t);
		const int * idx = tessGetElements(t);

		while(ic--)
		{
			int i1 = *idx++;
			int i2 = *idx++;
			int i3 = *idx++;
			printf("Tri: (%.2f,%.2f) (%.2f,%.2f) (%.2f,%.2f)\n",
				v[i1*2],v[i1*2+1],
				v[i2*2],v[i2*2+1],
				v[i3*2],v[i3*2+1]);
		}
	}
	tessDeleteTess(t);
}

The output is:

Tri: (-20.00,25.00) (0.00,5.00) (0.00,25.00)
Tri: (0.00,5.00) (-20.00,25.00) (-20.00,5.00)```
My expectation is that the 3 right-most colinear vertical vertices would not be organized into a single triangle.

Note that if the data is rotated 180 so that the left side has the colinear vertices, the colinear triangle does not occur.  Changing the vertex table to

```	float v[10] = {
		20.0, 		-5.00,
		0.00,		-5.00,
		0.00,		-15.00,
		0.00,		 -25.00,
		20.0,		 -25.00
	};

gives us

Tri: (0.00,-5.00) (20.00,-25.00) (20.00,-5.00)
Tri: (0.00,-15.00) (20.00,-25.00) (0.00,-5.00)
Tri: (20.00,-25.00) (0.00,-15.00) (0.00,-25.00)

where each triangle is non-colinear.

Replace assert ()'s with error handling

Hi, Mikko! Thanks for the awesome library!

We'd like to see libtess2 fail gracefully on malformed geometry, etc. instead of assert. Ideally we'd get back an error code indicating what happened.

Any plans for a modification like this?

Consultation on release plan

Dear Sir,

We have used your open source software in a product that is about to be released. Thank you for your generosity and contribution to the community.

Before we officially release our product, we need to evaluate that the open source software used is in its normal lifecycle. We noticed that libtess2 has not been updated for several years.

I personally know that libtess2 is quite stable and has been widely used in many products (such as flutter, Kanzi, etc.), but for some reason, we still need your formal confirmation that: libtess2 is mature and stable enough, so there won't be new features, no need for massive bugfix, and no plan for releasing new versions.

We hope you can provide us with an answer that is clear and concise. If you have any questions, please do not hesitate to contact us.

Thank you for your time and attention.

Best regards,

Wang

License Link not working

I can find the license info with a google search, but the license link in the repository doesn't exist anymore for the SGI license.

Shared library

Hi,

I want to package libtess2 for Fedora. However I'd need to do so as a shared library with SONAME.

I'd like to collaborate with you on the version here. Is libtess2.so.1 fine?

Wrong tessellation of self-intersecting contour

I tested a little your library and I created a case which is incorrectly tessellated. I attached a test file - it contains the problematic contour. First line contains number of vertices and then followed vertices (x, y, z values split by spaces).
contour3.txt

I use the LibTess2 library with doubles instead of floats (TESSreal type). The problematic intersection is between edge (2-1) and edge (75-76) (numbers are the indices of vertices). I tried also to debug the the code in sweep.c but I didn't find exactly where the problem is. If all vertices are slightly rotated around z-axis (like by 5 degrees) than the tessellation is correct.

note: option TESS_CONSTRAINED_DELAUNAY_TRIANGULATION changes the output triangles, but it produces same filled area

The wrong tessellation:

NaN coordinates cause segfault

If the input coordinates are NaN, the call to tessTesselate segfaults in pqInit, since the code falsely assumes a total ordering. Possibly tessAddCountour should check that the values are not NaN?

Specifically, it defines its comparisons as:

#define LT(x,y)     (! LEQ(y,x))
#define GT(x,y)     (! LEQ(x,y))

The function LEQ eventually expands to does comparisons with <= and <, which are always false for NaN. Thus LT(x, y) is always true, and the code here:

do {
  do { ++i; } while( GT( **i, *piv ));
  do { --j; } while( LT( **j, *piv ));
  Swap( i, j );
} while( i < j );

increments i until that pointer escapes the array bounds.

tessMeshRefineDelaunay issues

Hello.

I’m encountering a few anomalies with tessMeshRefineDelaunay in libtess2-1.0.2.

I’ve written a very simple example/test program that creates 1 or more, non-overlapping, circle or annulus like shapes, each with a user specified number of steps/points. These are all added to a TESStesselator using tessAddContour, CONSTRAINED_DELAUNAY_TRIANGULATION (CDT) is enabled (optionally) and then a single call to tessTesselate is made. The results are then output as EPS (which is easily viewed on macOS using Preview.app). Some timing stats are also reported.

This can create outputs from ~500 bytes (8 points, 1 contour → 6 triangles) to >500 MB (10,240,000 points, 400 contours → 10,240,000 triangles).

[The full program is only ~100 lines. I can post it here if requested.]

For example with 3 circles of 8 points each & CDT on; the output is:

But, with the same inputs but CDT off all 3 'circles' look like the rightmost one.
Is this expected behaviour? If I space out the shapes then the 2nd & 3rd look the same (but different from any of the above).

While experimenting with this I noticed that tessMeshRefineDelaunay does:

libtess2/Source/tess.c

Line 481 in fc52516

maxIter = maxFaces * maxFaces;

(where maxIter & maxFaces are ints) to limit the iteration count.
When maxFaces > 46,340 maxIter becomes negative (or undefined) resulting in no or a random amount of refinement.

This can be fixed with this change:

463:	long maxFaces = 0, maxIter = 0, iter = 0;

to:

libtess2/Source/tess.c

Line 463 in fc52516

int maxFaces = 0, maxIter = 0, iter = 0;

However, this does not fix the original problem. But it can cause tessMeshRefineDelaunay to dominate the run time. (I’ve seen billions of iterations in its while loop.) Further, if I run the program with (for instance):
        shape=annulus, steps=256, repeats=5, CDT=on it takes ~186 ms.
But with:
        shape=annulus, steps=257, repeats=5, CDT=on it takes ~3 ms.
And with CDT=off they both take ~2 ms.

So, in summary, I’m not convinced tessMeshRefineDelaunay is behaving correctly.

… a short while later …

I found this paper http://www.math.uha.fr/chevallier/publication/2009_07_09_article_cgta.pdf.
And, based on a cursory glance, I replaced the stack in tessMeshRefineDelaunay with a queue.
This appears to give better output results and can be as much as 100 (or even 300) times as fast when dealing with large numbers (>10,000) of triangles.

Here’s the minimal patch:

--- Source/tess.c~orig	2019-04-22 20:05:13.000000000 +0100
+++ Source/tess.c	2023-09-12 16:58:57.000000000 +0100
@@ -406,0 +407 @@
+	EdgeStackNode *end;
@@ -412 +413 @@
-	stack->top = NULL;
+	stack->top = stack->end = NULL;
@@ -432,2 +433,4 @@
-	node->next = stack->top;
-	stack->top = node;
+	node->next = NULL;
+	if (stack->end) stack->end->next = node;
+	else if (!stack->top) stack->top = node;
+	stack->end = node;
@@ -463 +466 @@
-	int maxFaces = 0, maxIter = 0, iter = 0;
+	long maxFaces = 0, maxIter = 0, iter = 0;

strange behavior with TESS_WINDING_POSITIVE and TESS_BOUNDARY_CONTOURS

Hello Mikko Mononen,

while working with the problem of offsetting polygons in 2d, I came across
with your "libtess2" and its pascal-port "fpc-libtess2". When tesselating
with winding rule "TESS_WINDING_POSITIVE" and the element type
"TESS_BOUNDARY_CONTOURS" I found a strange behavior. Sometimes the correct
result was delivered, sometimes not and I do not know why =(.
I want to show in 2 examples what I mean.
The two polygons

const TESSreal offsetSquare[26] = {
0, 0,
0, 80,
200,80,
200, 0,
120, 0,
120, 200,
200, 200,
200, 120,
0, 120,
0, 200,
80, 200,
80, 0,
0,0
} ;

and

const TESSreal offsetHouse[32]= {
0,0,
0,20,
100,20,
100,0,
80,0,
80,100,
100,100,
86,84,
36,136,
50,150,
64,136,
14,84,
0,100,
20,100,
20,0,
0,0
};

can be obtained by (raw) offsetting to the left
1.) a square in CCR orientation 0,0 200,0 200,200, 0,200, 0,0 with
offsetting value=20
2.) a shape of a simple house in CCR orientation
0,0 100,0 100,100, 50,150 0,100 0,0 with offsetting value=20

When tesselating with

1.)
tessAddContour(tess, 2, &offsetSquare[0], 2 * sizeof(TESSreal), 13);
t=tessTesselate(tess, TESS_WINDING_POSITIVE, TESS_BOUNDARY_CONTOURS, 0, 2, 0);

I got as result the 16 vertices of the 4 outer squares, which all have
the negative winding number (-1). The correct result are 4 vertices of
the inner square with winding number (+1), the downscaled square.
So the delivered result is that of the winding rule TESS_WINDING_NEGATIVE.

This is the output-result (x-,y-component):
80, 0
0 , 0
0 , 80
80 , 80
200 , 0
120 , 0
120 , 80
200 , 80
200 , 120
120 , 120
120 , 200
200 , 200
80 , 120
0 , 120
0 , 200
80, 200

2.)
tessAddContour(tess, 2, &offsetHouse[0], 2 * sizeof(TESSreal), 16);
t=tessTesselate(tess, TESS_WINDING_POSITIVE, TESS_BOUNDARY_CONTOURS, 0, 2, 0);

I got correct result of 5 vertices of the region with winding number (+1),
the downscaled shape of a house. The 5 regions with winding number (-1)
are correctly deleted.

This is the output-result (x-, y-component):
80, 90
50 , 121
20 , 90
20 , 20
80 , 20

The fpc-libtes2 delivers the same results as your libtess2.

These are only two examples of many cases I got the correct or false
results and I don't know the reason. For me it looks as if in the course
of tesselation the orientation of the input polygon is changed from
CW -> CCW or vice versa.

I didn't try the GLU tesselator from SGI, that seems to me too complicated
with all the callbacks. So I hope you can solve my dilemma.

Udo Krix

comment problem

In the comment of the struct TessElementType, for the example for,

I think the line ;

// glVertex2fv(&verts[(base+count) * vertexSize]);

should be 👍

// glVertex2fv(&verts[(base+j) * vertexSize]);

Intersection vertex issue

This is more a question than an issue:

I'm feeding a self-intersecting polygon to the tessellator, e.g. an hourglass:

0 0 0
1 0 0
0 1 0
1 1 0

Now, this will be tessellated into two triangles
[1 0 0], [0 0 0] , []
[1 1 0], [], [0 1 0]

I don't generally know which intersection this is and there is no callback to let me calculate it.
I see that the demo program just ignore them.
Since I plan on using this to tessellate manifold meshes, I cannot just leave out triangles as that would destroy the connectivity of my mesh.

Could someone shed some light on this?

GLU callbacks

Hi.Nice port :) But I wonder how can I simulate original GLU's callbacks like

  gluTessCallback(tess, GLU_TESS_VERTEX_DATA ,vertexCallback);

  gluTessCallback(tess, GLU_TESS_COMBINE_DATA,combineCallback);

  gluTessCallback(tess, GLU_TESS_EDGE_FLAG ,edgeFlagCallback);

Assert failure tessellating planar triangle

Passing the following triangle to the tessellator causes an assert failure:

Assertion failed: (VertLeq( u, v ) && VertLeq( v, w )), function tesedgeSign, file ../Source/geom.c, line 83.

-70.4956,14.872283,14.6119
-70.4956,14.8722944,32.6832
-70.4956,14.872283,14.6119

The cause seems to be that the sentinels used for the edge dict touches the bounding box when any dimension of the bounding box is 0. The is again amplified by the worst-case normal being chosen for collinear input polygons. I'll send a patch for the latter issue shortly.

A special case of this issue is when a polygon is collinear in an axis-aligned fashion. In this case, my fix for the normal vector won't help:

0,0,0
0,0,1
0,0,2

Negative winding broken

I use the glu tesselator for computing intersections and subtractions of regions. When I switched to tess2 it does not work for subtraction anymore and apparently the negative winding does not work anymore. Maybe this was an "optimization" for the case of triangles but not correct for contours.

Also, it seems to be slower than the original glu for simple polygons without overlapping contours or inner contours.

Is there a way to mark which triangle edges are polygon edges?

Some output polygon edges are interior to a tessellated polygon, and some are exterior to it (i.e. edges of the tessellated poly.) Is there any way to get this information out of libtess2?

E.g. if I tessellate a quad with triangles, two edges of each output triangle will be "exterior edges", and one edge of each output triangle will be an "interior edge."

I'd like to know which are which so I can draw tessellated polygon outlines in the same pass that I draw the fills. (I.e. via this technique: http://codeflow.org/entries/2012/aug/02/easy-wireframe-display-with-barycentric-coordinates/) So I need to know which edges not to draw for that to work.

Floating point precision bugs?

Any interest in glitch cases due to floating point precision? I'm opening this issue in case you're looking for repo steps.

The code below shows the error. We'd expect a result with 8 verts, but instead get 7. Rounding to 4 decimal places gives the expected result.

I vaguely recall a way to configure fp rounding in an earlier version, but can't seem to find it in the history. I added rounding to my calling code, so not a big deal. But it would be awesome to see a more robust way to handle these cases or a note in the docs about why they happen and how to avoid them.

Thanks for making a great library! :)

// clamping these to 4 decimal places gives the expected result
float contour0 [] = {
    40.000000, 36.770508,
    -33.541019, 0.000000,
    40.000000, -36.770508,
};

float contour1 [] = {
    -65.000000, 65.000000,
    -65.000000, -65.000000,
    65.000000, -65.000000,
    65.000000, -15.729490,
    10.000000, 11.770510,
    10.000000, -10.000000,
    -10.000000, -10.000000,
    -10.000000, 10.000000,
    10.000000, 10.000000,
    10.000006, -11.770506,
    65.000008, 15.729493,
    65.000000, 65.000000,
};

float contour2 [] = {
    115.000000, 74.270508,
    35.000004, 34.270512,
    35.000000, -34.270508,
    115.000000, -74.270508,
};

TESStesselator* tess = tessNewTess ( 0 );

tessAddContour ( tess, 2, contour0, 8, 3 );
tessAddContour ( tess, 2, contour1, 8, 12 );
tessAddContour ( tess, 2, contour2, 8, 4 );

float normal [] = { 0, 0, 1 };

// should give us a shape with 8 vertices
tessTesselate ( tess, TESS_WINDING_NONZERO, TESS_BOUNDARY_CONTOURS, 0, 0, normal );

const float* verts = tessGetVertices ( tess );
const int* elems = tessGetElements ( tess );
int nelems = tessGetElementCount ( tess );

for ( int i = 0; i < nelems; ++i ) {
    int b = elems [( i * 2 )];
    int n = elems [( i * 2 ) + 1 ];
    
    for ( int j = 0; j < n; ++j ) {
    
        size_t idx = ( b + j ) * 2;
        float x = verts [ idx ];
        float y = verts [ idx + 1 ];
    
        printf ( "%d %d: %f %f\n", i, j, x, y );
    }
}

tessDeleteTess ( tess );

Assert in sweep.cpp (Line 351) - Expression "VertLeq( e->Org, e->Dst )"

Hi from Unity! We're seeing the occasional crash and infinite loop in libtess2 from the PolygonCollider2D. The following code produces a crash:

    struct vec2
    {
        vec2(float _x, float _y)
            : x(_x)
            , y(_y)
        {}

        float x;
        float y;
    };
    vec2 points[34] =
    {
        vec2(3.65450994e-08f, -0.545000076f),
        vec2(2.17929479e-08f, -0.325000018f),
        vec2(1.64285296e-08f, -0.245000020f),
        vec2(5.02914155e-09f, -0.0750000030f),
        vec2(-2.34693287e-09f, 0.0350000039f),
        vec2(-5.02914155e-09f, 0.0750000030f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-7.04079861e-09f, 0.105000012f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-5.02914155e-09f, 0.0750000030f),
        vec2(-1.00582831e-09f, 0.0150000015f),
        vec2(-7.04079861e-09f, 0.105000012f),
        vec2(-1.24052164e-08f, 0.185000017f),
        vec2(-1.70990830e-08f, 0.255000025f),
        vec2(-2.24634995e-08f, 0.335000008f),
        vec2(-2.58162611e-08f, 0.385000050f),
        vec2(-3.65450994e-08f, 0.545000076f),
        vec2(-3.65450994e-08f, 0.545000076f),
        vec2(-3.18512328e-08f, 0.475000054f),
        vec2(-2.71573661e-08f, 0.405000061f),
        vec2(-1.70990830e-08f, 0.255000025f),
        vec2(-8.38190317e-09f, 0.125000015f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-3.68803743e-09f, 0.0550000072f),
        vec2(-3.35276112e-10f, 0.00500000035f),
        vec2(5.69969405e-09f, -0.0850000083f),
        vec2(2.51457095e-08f, -0.375000060f),
        vec2(3.92273058e-08f, -0.585000038f),
        vec2(3.98978557e-08f, -0.595000029f),
        vec2(3.98978557e-08f, -0.595000029f),
        vec2(3.92273058e-08f, -0.585000038f),
        vec2(2.51457095e-08f, -0.375000060f),
        vec2(3.98978557e-08f, -0.595000029f),
        vec2(3.98978557e-08f, -0.595000029f)
    };

    TESStesselator* tess = tessNewTess(NULL);
    tessAddContour(tess, 2, points, sizeof(vec2), 34);
    tessTesselate(tess, TESS_WINDING_ODD, TESS_POLYGONS, 8, 2, NULL);
    tessDeleteTess(tess);
}

Trying to triangulate a square

Hello! First of all, big shoutout for your work from Ukraine! I like the way you organised the library, but I have couple of questions.

Now, as a test assignment in order to understand quirks & features of libtess2, I decided to triangulate a simple square:

let tl = TextureVertex(x: -1.0, y: 1.0, z: 0.0, s: 0.0, t: 0.0)
let tr = TextureVertex(x:  1.0, y: 1.0, z: 0.0, s: 1.0, t: 0.0)
let br = TextureVertex(x:  1.0, y:-1.0, z: 0.0, s: 1.0, t: 1.0)
let bl = TextureVertex(x: -1.0, y:-1.0, z: 0.0, s: 0.0, t: 1.0)

TextureVertex is a simple C-based struct which I'm using in my Swift layer.

Here's how my work with libtess2 looks like:

- (NSArray<NSNumber *> *)triangulate_TextureVertex:(TextureVertex *)vertices verticesCount:(int)count
{
    tessAddContour(tesselator, 2, vertices, sizeof(TextureVertex), count);
    
    if (tessTesselate(tesselator, TESS_WINDING_POSITIVE, TESS_POLYGONS, 6, 0, 0)) {
        
        const float *verts = tessGetVertices(tesselator);
        const int *vinds = tessGetVertexIndices(tesselator);
        
        
        for (int i = 0; i < 6; i++) {
            //NSLog(@"vert = %f", verts[i]);
            NSLog(@"index = %d", vinds[i]);
        }
        
        NSLog(@"Hold!");
    }
    
    return nil;
}

That's an Objective-C method in which I wrap the work with libtess2. This way I can use your library from my Swift code.

So as you can see I have a test for-loop where I can check out proposed indices set, and I'm kind of expecting to have 6 indices, because square is made of 2 triangles which means 2 set of 3 vertex indices.

But the weird part is that in the response I have only 4 indices [2, 3, 0, 1]. Obviously that's not enough to draw a square, at least 2 indices are missing. I decided to check tessGetVertices() just to see if x and y of Vertex are grabbed properly, but it looks legit.

Also - where can I get an info about indices count? Is there a function which can do that for me?

I understand that I might made some rookie mistake and would be happy if you could point me to it. If you need any additional info from me, just let me know.

With regards,
Yevhen