Flood fill generic polygon (not strictly convex); methods?

[inflex]

I'm drawing a random closed polygon consisting of anything from 4 to 200 segments and may contain holes within (something I may have to just deal with).

I wish to floodfill this polygon but understandably the ImGui one is for convex only (though it's a pretty pattern when used on polygons with concave sections ).

Does anyone have a recommendation or pointer to a routine that works with ImGui primitives and doesn't grind the CPU to a halt?

I was considering just scanline odd/even tests using line-intersection algorithms, just worried it might be too slow and far from optimal algorithmically.

[ratchetfreak]

You are looking for polygon triangulation

O(n log n) algorithms exist.

[ocornut]

If you implement something it would be nice to post your code here too :)

[inflex]

I thought doing the convex hull and minimal bounding box algorithms (for a set of ImVec2 points ) were tricky enough, this one is a new level of brain exercise ( if anyone wants those algorithms/code I'm happy to provide ).

[inflex]

Unfortunately I've ended up cheating with my solution for now. Instead of doing it through triangle decomposition / tessellation I instead build a line-fill pile of scan line orientated vectors which I then redraw each time the poly is moved / resized.

The upside is, it handles holes in the poly ( if p1, p2, p3, ... , pn defines the points and there's a common point in the list indicating a crossover ).

I was thinking I could increase the line stroke width at the expense of edge fidelity but requiring less lines.

[ocornut]

It looks pretty good and not noisy here.

[inflex]

I'll rewrite the code in a more generic form and attach it here, looks like I've got a project tonight.

A "technically correct" triangle tessellated version would have been nice, but this will do for now.

[inflex]

Attached is what I hope is a functioning scan-based fill algorithm.

Only the single function; caller can control the gap/stroke-width directly if wanted.

void PolyFillScanFlood(ImDrawList *draw, vector<ImVec2> *poly, ImColor color, int gap = 1, int strokeWidth = 1);

scanfillflood.zip

[inflex]

Have you ever noticed how many things you pick up after you submit something?

Just realised that the ImVec2 a and b are never even used, they were a carry over from the original algorithm which didn't pan out.

Attached is the 2nd attempt.

scanfillflood-2.zip

[ocornut]

Thanks!

For such a small amount of code you can post it inline:

.h

void PolyFillScanFlood(ImDrawList *draw, vector<ImVec2> *poly, ImColor color, int gap, int strokeWidth);

.cpp

#include <algorithm>
#include <limits>
#include <vector>
#include "imgui/imgui.h"

using namespace std;

#include "imgui-floodfill.h"

void PolyFillScanFlood(ImDrawList *draw, vector<ImVec2> *poly, ImColor color, int gap = 1, int strokeWidth = 1) {

    vector<ImVec2> scanHits;
    static ImVec2 min, max; // polygon min/max points
    auto io = ImGui::GetIO();
    double y;
    bool isMinMaxDone = false;
    unsigned int polysize = poly->size();

    // find the orthagonal bounding box
    // probably can put this as a predefined
    if (!isMinMaxDone) {
        min.x = min.y = DBL_MAX;
        max.x = max.y = DBL_MIN;
        for (auto p : *poly) {
            if (p.x < min.x) min.x = p.x;
            if (p.y < min.y) min.y = p.y;
            if (p.x > max.x) max.x = p.x;
            if (p.y > max.y) max.y = p.y;
        }
        isMinMaxDone = true;
    }

    // Bounds check
    if ((max.x < 0) || (min.x > io.DisplaySize.x) || (max.y < 0) || (min.y > io.DisplaySize.y)) return;

    // Vertically clip
    if (min.y < 0) min.y                = 0;
    if (max.y > io.DisplaySize.y) max.y = io.DisplaySize.y;

    // so we know we start on the outside of the object we step out by 1.
    min.x -= 1;
    max.x += 1;

    // Initialise our starting conditions
    y = min.y;

    // Go through each scan line iteratively, jumping by 'gap' pixels each time
    while (y < max.y) {

        scanHits.clear();

        {
            int jump = 1;
            ImVec2 fp = poly->at(0);

            for (size_t i = 0; i < polysize - 1; i++) {
                ImVec2 pa = poly->at(i);
                ImVec2 pb = poly->at(i+1);

                // jump double/dud points
                if (pa.x == pb.x && pa.y == pb.y) continue;

                // if we encounter our hull/poly start point, then we've now created the
                // closed
                // hull, jump the next segment and reset the first-point
                if ((!jump) && (fp.x == pb.x) && (fp.y == pb.y)) {
                    if (i < polysize - 2) {
                        fp   = poly->at(i + 2);
                        jump = 1;
                        i++;
                    }
                } else {
                    jump = 0;
                }

                // test to see if this segment makes the scan-cut.
                if ((pa.y > pb.y && y < pa.y && y > pb.y) || (pa.y < pb.y && y > pa.y && y < pb.y)) {
                    ImVec2 intersect;

                    intersect.y = y;
                    if (pa.x == pb.x) {
                        intersect.x = pa.x;
                    } else {
                        intersect.x = (pb.x - pa.x) / (pb.y - pa.y) * (y - pa.y) + pa.x;
                    }
                    scanHits.push_back(intersect);
                }
            }

            // Sort the scan hits by X, so we have a proper left->right ordering
            sort(scanHits.begin(), scanHits.end(), [](ImVec2 const &a, ImVec2 const &b) { return a.x < b.x; });

            // generate the line segments.
            {
                int i = 0;
                int l = scanHits.size() - 1; // we need pairs of points, this prevents segfault.
                for (i = 0; i < l; i += 2) {
                    draw->AddLine(scanHits[i], scanHits[i + 1], color, strokeWidth);
                }
            }
        }
        y += gap;
    } // for each scan line
    scanHits.clear();
}

If I were to rework this function for sharing, I'd use raw pointer + count as input (so as to not be depending on std::vector), use ImVector inside the function to sort hits and use C standard lib qsort() for sorting. None of that is needed since this is your private code, just pointing out :)

It's good to have it as reference somewhere. Thanks!

If you use resize(0) instead of clear() you may reuse the buffer for each loop iteration and not heap allocate everytime. You may as wait just reserve like 256 ahead of times, wouldn't hurt since it is temporary buffer anyway.

[inflex]

@ocornut very happy to hear your feedback on the code. This whole project really is my first C++ true experience, the last 30 years have been C, as a result I'm making a bit of a mess with the new work I'm doing.

I'll definitely use those tricks such as resize(0) and reserve in a few other areas too.

I should point out (since I don't think it's explicitly clear) that in order to make this flood fill work if you want holes in your area, you need to fully close the polygon before moving to the next (interior) polygon; that's what the "if ((!jump) && (fp.x == pb.x) && (fp.y == pb.y))" test is for.

[ocornut]

Closing this now, if that's ok.

[Flix01]

@inflex: I've just found a C++, header-only implementation of a 2D convex decomposition here: https://github.com/angelog/bayazit.h It shouldn't be too difficult to remove STL from it and use ImGui structs instead...

The only problem is that the decomposition should be done in a pre-processing step (not every frame).

...just in case you're interested...

[inflex]

Many thanks for that @Flix01 . I'll have to have a look. I agree, something like that you do wish only to do once and then just render the resultant pile of triangles afterwards.

For the task that induced my search for a solution, I'm oddly finding the pin-striping to be most effective, more so than I anticipated (fortunately it's only adding a small CPU hit). That said, I think it'd be great to have a generic poly fill function that does the full fill job :)

[inflex]

Not sure this one will handle holes, as I don't see any mention of it on their page or examples.

The other thing I was going to try was to try merge the slices I generate using the scanline algorithm in to progressively larger convex polys, at the cost of original outline fidelity.

[Flix01]

Yes, your solution looks good (even if I'd like to see a test example on how to call PolyFillScanFlood(...) together with the method code).

For the holes with convex decomposition, I guess you have to define the surface with (at least) a cut and all the internal outline: then you can fill the convex polys and the hole should be visible (the problem here is that then you have to skip the 'cut edge' if you want to stroke/draw the two outlines too).

[inflex]

I did a test with a full fill and on a poly with 198 points, it pushed the CPU up to 60% (G3420) when I thrashed it around (dragging), that's while watching Youtube too.

Dropping it back to 3 gap, 3 width draw makes it a lot faster but there's the issue of slight pinstriping still due to imperfect pixel overlaying.

[ocornut]

If you are doing triangulation you should do it in the natural space of your data and save the indices/vertices, then only transform the vertices during render.

[Flix01]

@inflex: thanx for the performance info.

@ocornut: yes, for example with some kind of ImDrawList method that takes the polygon points, an ImVec2 offset (and maybe a scaling) as additional arguments.

[inflex]

@Flix01 have been trying to conjure up a merging algorithm all day, or a way to save CPU for future redraws (taking in to consideration zoom/rotating) and it always comes back to needing some manner of creating the whole out of smaller convex polygons (once we've got convex we can use the existing ConvexFill()).

For now I'd like to consider offering a patch/PR to do the scan-line method even if it is (relatively) CPU intensive (the upside though is that it does handle holes). With less points/vertices in the poly it should help. There's probably faster ways of computing the cut points than iterating through the whole poly for each scan line, but again, if it's only a few dozen points it's probably not going to impact too severely.

[ocornut]

have been trying to conjure up a merging algorithm all day, or a way to save CPU for future redraws

I don't understand the problem here. Any heavy algorithm you run, you should run it on your untransformed data, so you can reuse the result as long as the object doesn't change, and not have to recompute when moving/zooming.

Please free to post code here for reference, but any code to be merged in ImDrawList needs to be optimal.!

[Flix01]

@inflex: no problem. I was referring to the convex decomposition algorithm, where preprocessing is mandatory: to reuse the decomposition data, we must transform vertices on the fly. Your method does not need that.

P.S. I've added an "imgui port" of the Bayazit's 2D convex decomposition algorithm (the basic one; the one I linked above seems to be better, but I've found it... too late) to my imgui fork together with a test-function that draws a star [= no holes yet].

It's _currently_ (I might move, remove, change it in the future) contained in these two files (guarded by the NO_IMGUIHELPER_DRAW_METHODS_CONCAVEPOLY definition): https://github.com/Flix01/imgui/blob/41178a2adc6198d5ed499220fda769bcf41f7c08/addons/imguihelper/imguihelper.h#L52 https://github.com/Flix01/imgui/blob/41178a2adc6198d5ed499220fda769bcf41f7c08/addons/imguihelper/imguihelper.cpp#L375

However it should be better to port the "newer version", and to put it in a gist... Not sure when/if I'll find the time to do it.

[Edit:] Deleted a duplicated post, and updated the dead links above. Actually I removed that code from imguihelper.h/cpp on Oct 24, 2016, but the links above have been taken from the repository history.

[inflex]

However it should be better to port the "newer version", and to put it in a gist... Not sure when/if I'll find the time to do it.

@Flix01 Likewise time is against me here too. Already been 8 weeks working on this project, time for me to be happy with what is done ( and in fairness, it does perform the functions I need ). Maybe one day.

@ocornut poor choice of wording on my behalf, was intending for it (proper solution) to be such that it doesn't have to be recomputed regardless of transformations, as well as correct for all general polygons and suitably optimal.

Regards, Paul.

[Flix01]

Already been 8 weeks working on this project, time for me to be happy with what is done ( and in fairness, it does perform the functions I need ). Maybe one day.

@inflex: I didn't mean that you should do it! :)

P.S. Holes seem to work perfectly with the 'old' version (please note the 'cut' in the outline):

[inflex]

@Flix01 how are you defining the holes? The method I was subjected to (and hence what drove me to this point) was that the start point would be reused in the poly point array, letting me know it had 'fully closed', the next point was then the start of the new closed hull.

ie, 4,3 7,6 11,2 9,9 11,9, 5,5 4,3 6,6 8,9 8,8

note that the last hull defined doesn't explicitly get closed in my case, though I'm sure some would.

Good luck with it :)

[Flix01]

how are you defining the holes?

I've added the ImDrawListAddHollowQuad(...) method so that you can see that yourself. Basically using 13 points it's something like:

   11      0=7=12     8
    ---------|---------
    |        |        |
    |   -----------   |
    |   |2  1=6  5|   |
    |   |         |   |
    |   |         |   |
    |   |3       4|   |
    |   -----------   |
    |                 |
    -------------------
   10                 9

however that's just a test, the cut could be made better to save a convex shard.

The ordering allows splitting the path to draw the two outlines without the cut [because the method I use to draw the outline now takes (const ImVec2* points,int numPoints) as arguments, and I can pass points (1,2,3,4,5,6) for the inner loop and (7,8,9,10,11,12) for the outer loop (even if one is counterclockwise and the other clockwise...)]:

[ocornut]

The semi standard way of defining holes for csg operations is to use clockwise vs anti-clockwise orders. You still need to pass a list of list somehow, eg a list of points and a list of range pair (start,count).

[Flix01]

The semi standard way of defining holes for csg operations is to use clockwise vs anti-clockwise orders. You still need to pass a list of list somehow, eg a list of points and a list of range pair (start,count).

Good to know. However this is not something I've defined... I've just "ported" this code : https://mpen.ca/406/files/polydecomp-bayazit.zip, documented here: https://mpen.ca/406/bayazit without knowing any particular convention for defining holes: I've just tried that way and it worked.

[inflex]

Definitely would prefer a range specifier, or predefined delimiter (-FLT_MAX, -FLT_MAX ? )

[Flix01]

Definitely would prefer a range specifier, or predefined delimiter (-FLT_MAX, -FLT_MAX ? )

Not sure if it's possible to add it. Actually I'm not even sure that the "csg semi-standard" is not supported by the algorithm (I mean merging one clockwise outline with one counter-clockwise without any cut)...

However that algorithm (Bayazit) seems to be widely used in 2D game engines (*), so I guess they pass holes this way.

(*) For use with 2D game engines the "newer" version is mandatory, since you can specify the maximum number of vertices in each convex shard. In fact the newer version is based on the C# version (with updates from Farseer Physics and Yogesh Kulkarni) that is referenced at the bottom of the documentation.

[Flix01]

Made an optimization (10 points instead of 13; only the two closed loops are specified):

   0=4                1
    -------------------
    |\                |
    |  \-----------   |
    |   |5=9     8|   |
    |   |         |   |
    |   |         |   |
    |   |6       7|   |
    |   -----------   |
    |                 |
    -------------------
    3                 2

It's not too difficult to define holes this way (at least for simple shapes...)!

[pierr3]

For anyone still needing to do this, I solved it by using tessellation and this library, works great with good performance. Just make sure you draw an edge to your triangles to fill in gaps between them.

[VerTiGoEtrex]

I'm using @pierr3 's solution, but running into some issues with gaps appearing between my triangles which I can't seem to resolve. (I turned up the opacity a bit on this image to make the gaps more prominent)

I'm running earcut, then drawing the triangles by calling ImPlot::GetPlotDrawList()->AddTriangleFilled(p1, p2, p3, col) in a loop.

@pierr3 you mentioned you have to draw an edge to the triangles? I can do that by also calling AddTriangle with a small thickness, but since my colors are not 1.0 alpha, I end up with lines appearing rather than gaps. Any thoughts? Perhaps this has something to do with AA?

[pierr3]

@pierr3 you mentioned you have to draw an edge to the triangles? I can do that by also calling AddTriangle with a small thickness, but since my colors are not 1.0 alpha, I end up with lines appearing rather than gaps. Any thoughts? Perhaps this has something to do with AA?

@VerTiGoEtrex It is. I ended up turning off AA and this solved the issue for my purposes.

[thedmd]

I guess I will add my three cents. Taking Flix01 https://github.com/ocornut/imgui/issues/760#issuecomment-238221585 mesh as an example:

# include <imgui.h>

namespace ImDrawListEx {

void AddPolyFilled(ImDrawList* draw_list, const ImVec2* points, const int points_count, ImU32 col);

void PathFill(ImDrawList* draw_list, ImU32 col);

} // namespace ImDrawListEx {

Source: imgui_draw_ex.zip

I was looking for quick way to fill non-convex polygon. Search result were anything but quick, implementations were all over the place. In the end I dusted of my old algorithm knowledge and implemented PathFill using ear clipping method.

Code adhere to ImGui standards with an exception of using auto.

Scratch memory is allocated using single alloca. Omar did mention draw_list->_Data->TempBuffer which I didn't found in my old version of ImGui, which make code work with 1.84+. This temporary buffer can be utilized latter.

Triangulation is enclosed in Triangulator class, which is ~180 lines long. Ear clipping is optimized using reflex vertices, which reduce number of vertices ears tips need to be tested against. Linked lists for ears and reflexes was replaced by flat array to better utilize CPU cache (not benchmarked). Vertices linked list is placed in single memory fragment.

Implementation is split to different methods:

// Triangulate polygon pushing triangles directly into ImDrawList. Very similar to 'AddConvexPolyFilled',
// with an exception of method of picking triangle indices.
void ImDrawListEx_AddPolyFilled_NoClip_NoAA(ImDrawList* draw_list, const ImVec2* points, const int points_count, ImU32 col);

// Triangulate polygon as usual but emit mesh with AA fringe along the edges. This does emiliate artifacts
// present when multiple calls to 'AddConvexPolyFilled' are used to emulate non-convex fill support.
// (see: pie menu test in https://github.com/ocornut/imgui/issues/434#issuecomment-183378673)
void ImDrawListEx_AddPolyFilled_NoClip_AA(ImDrawList* draw_list, const ImVec2* points, const int points_count, ImU32 col);

// Selects between two of the above by inspecting 'Flags'.
void ImDrawListEx_AddPolyFilled_NoClip(ImDrawList* draw_list, const ImVec2* points, const int points_count, ImU32 col);

AddPolyFilled by default does clip rect test to quickly reject off-screen polygon. Such test is faster than triangulation of large polygons so it is by default on. For small polygons it is cheap to perform. This behavior could be controlled with ImDrawListFlags_NoClip or ImDrawFlags_NoClip flag, which isn't a thing yet.

Non-convex polygon filling will always be more expensive than convex one. No amount of optimization will change that.

The question is if this implementation is good enough for it to be considered as a candidate to intagrate with ImGui? @ocornut Would you like me to prepare a PR where code is integrated into ImDrawList?

Oh, and a sneak peak of what triggered this whole side-quest:

[ocornut]

The question is if this implementation is good enough for it to be considered as a candidate to intagrate with ImGui? @ocornut Would you like me to prepare a PR where code is integrated into ImDrawList?

Not ready to give an answer for it yet but this is looking good and happily small!

Notes for later (*)

• Use explicit "concave" name e.g. AddConcavePolyFilled() PathFillConcave() so it's not accidentally misused by people because it has quite large performance implications.
• IsPointInTriangle() exists already as ImTriangleContainsPoint().
• When you use the TempBuffer presumably you can remove the HeapBuffer as well? That may be more important than the alloca.
• AddPolyFilled() could use ImRect to replace the min/max in loop as well as the ImDrawListEx_TestRectOverlap() helper.
• If you need a flag (ImDrawFlags_NoCoarseClipTest may be a good name?) you can declare locally a enum ImDrawFlagsEx_ using some high value (e.g. 1 << 30).

(*) But honestly you don't need to do anything now, I can perform those changes. Code is self-explanatory enough.

My gut feeling is: when you start using that sort of stuff it may lead to a path were you want better tessellation functions, ways to import meaningful data, etc. One suggestion is this could be a mini side-project hosted on its own (thedmd/imgui_draw_concave or perhaps as part of imgui_club/ ?)

[thedmd]

I see filling non-convex paths as a missing link in ImDrawList, especially one supporting AA fringe.

I would argue after including it into ImGui, without any extra facilities that can be build on top. Users will be enabled to render font glyphs or SVG shapes without need to implement this more atomic part.

I don't have a wish of creating ImDrawList replacement, I would rather improve existing implementation when possible. :)

[inflex]

Looking forward to trying a different implementation ( hard to believe this thread is from 2016 ). These days I'm having to use the non-convex fill a lot more than I have in the past. While the performance is okay on reasonable CPUs it would be nice to be more optimal than the current scan-line fill method being used now.

[thedmd]

@ocornut

There will be some tweaks to be done in the code I posted. Mainly related AA fringe and avoiding overdraws.

Offseting polygon is done in most simple way possible, by shifting vertex positions along the normals. This works well for convex paths. Non-convex paths are better at finding the limits of this technique. Shrinking paths, especially small ones can lead to not only points crossing the edges (when top vertex will be placed under the bottom due to shift) but also to splits. Splits are where one path is splitted to two separate paths because part of it collapsed. Reverse thing can happen when expanding - two paths can merege together. Long story short, handling any of this is out of the scope of ImGui.

These tweaks I spoke initially are dealing with imperfections of offsetint a polygon, with an aim to always emit correct amount of triangles. Originaly when path degenerate, triangulation will stop and there will be a 'hole' in the shape - which is much worse visual result than small overdraw.

If anyone need a close to perfect solution, there are libraries (like Clipper2) for that and ImDrawList can be feed with resulting geometry. Vastly more complex and capable.

I think this is what you had in mind when you spoke about side project. I'm not really interested in pursuing that. Having good, but not perfect solution is fine for me. I think filling a star shape shoudn't be a chore in ImGui. : )

Tweaked	Original

[ocornut]

There will be some tweaks to be done in the code I posted. Mainly related AA fringe and avoiding overdraws.

Does it render correctly with transparent color?

I think this is what you had in mind when you spoke about side project.

Not exactly. There’s value in providing a drop-in mini library which adds two functions to ImDrawListEx namespace to do this. In contrast, Clipper2 is more complicated to approach.

I agree that ideally the code can be moved to imgui, but we would already provide quite some tangible value by releasing the ready-to-use form of simple draw list function. Even as a separate file it is closer to being a standard.

I think filling a star shape shoudn't be a chore in ImGui. :)

I agree but I also worry that people expecting a lots from it would forever push for improvements. Eg when you suggested drawing SVG contents in messages above, I am expecting this to raise many more problems than a star-shape ? Curious about overall capabilities of this.

Either way there’s not a lots of difference in term of code between making it a standalone .h/.cpp or making it a PR. Mostly need to get rid of heap allocation I suppose.

[thedmd]

Does it render correctly with transparent color?

Non-AA fill, unconditionally yes.

AA fill, generally yes. Exceptions are present when simple polygon offset algorithm fails.

AA-fringe can generate degenerated mesh. Sometimes shifting vertex by half of a pixel does mangle triangles. Both AddConvexPolyFilled, and AddConcavePolyFilled are prone to this. Both will have artifacts when path is over-tesselated. With AddConvexPolyFilled it is easier to trigger the issue with sharp angles (think: start with many arms falling on single pixel). In both cases transparent polygon will be overdrawn.

I agree that ideally the code can be moved to imgui, but we would already provide quite some tangible value by releasing the ready-to-use form of simple draw list function. Even as a separate file it is closer to being a standard.

I will follow with that you decide.

Curious about overall capabilities of this.

Main difference between convex and non-convex version is the way of picking triangle indices. Convex just use consecutive indices, non-convex pick them from triangulator. That is all the difference in practice. Rest of the code is the same. This is the realisation I came up with after I wrote the code.

Function that handle SVG paths need to be more fancy and is definitely out of the scope of ImGui.

Mostly need to get rid of heap allocation I suppose.

There is not heap allocation. alloca is used and in the future TempBuffer can be utilitzed for that purpose. That HeapStorage you saw was for path, where user did not provide necessary buffer.

Picture is worth a thousand words, so I think I would like to draw a picture with the code : )

Those are the differences between AddConvexPolyFilled and AddConcavePolyFilled.

void ImDrawList::AddConvexPolyFilled(const ImVec2* points, const int points_count, ImU32 col)
{
    // ...

    if (Flags & ImDrawListFlags_AntiAliasedFill)
    {
        // ...

        // convex
        for (int i = 2; i < points_count; i++)
        {
            _IdxWritePtr[0] = (ImDrawIdx)(vtx_inner_idx); _IdxWritePtr[1] = (ImDrawIdx)(vtx_inner_idx + ((i - 1) << 1)); _IdxWritePtr[2] = (ImDrawIdx)(vtx_inner_idx + (i << 1));
            _IdxWritePtr += 3;
        }

        // non-convex
        _Data->TempBuffer.reserve_discard((ImTriangulator::EstimateScratchBufferSize(points_count) + sizeof(ImVec2)) / sizeof(ImVec2));
        auto triangulator = ImTriangulator(points, points_count, _Data->TempBuffer.Data);
        while (triangulator.HasNext())
        {
            auto triangle = triangulator.Next();
            _IdxWritePtr[0] = (ImDrawIdx)(vtx_inner_idx + (triangle.Index[0] << 1)); _IdxWritePtr[1] = (ImDrawIdx)(vtx_inner_idx + (triangle.Index[1] << 1)); _IdxWritePtr[2] = (ImDrawIdx)(vtx_inner_idx + (triangle.Index[2] << 1));
            _IdxWritePtr += 3;
        }

        // ...
    }
    else
    {
        // ...

        // convex
        for (int i = 2; i < points_count; i++)
        {
            _IdxWritePtr[0] = (ImDrawIdx)(_VtxCurrentIdx); _IdxWritePtr[1] = (ImDrawIdx)(_VtxCurrentIdx + i - 1); _IdxWritePtr[2] = (ImDrawIdx)(_VtxCurrentIdx + i);
            _IdxWritePtr += 3;
        }

        // non-convex
        _Data->TempBuffer.reserve_discard((ImTriangulator::EstimateScratchBufferSize(points_count) + sizeof(ImVec2)) / sizeof(ImVec2));
        auto triangulator = ImTriangulator(points, points_count, _Data->TempBuffer.Data);
        while (triangulator.HasNext())
        {
            auto triangle = triangulator.Next();
            _IdxWritePtr[0] = (ImDrawIdx)(_VtxCurrentIdx + triangle.Index[0]); _IdxWritePtr[1] = (ImDrawIdx)(_VtxCurrentIdx + triangle.Index[1]); _IdxWritePtr[2] = (ImDrawIdx)(_VtxCurrentIdx + triangle.Index[2]);
            _IdxWritePtr += 3;
        }
    }
}

Sorry for not showing this earlier, I'm terrible at finding simple explanations fast.

[ocornut]

Main difference between convex and non-convex version is the way of picking triangle indices.

The reason I asked about if it worked with transparent color is I am not sure how to select where to draw the fringe.

There is not heap allocation. alloca is used and in the future TempBuffer can be utilitzed for that purpose. That HeapStorage you saw was for path, where user did not provide necessary buffer.

Oh I see. But since triangular is not going to be a public helper there's no point in exposing this, as we always evaluate the scratch buffer size.

But either way this should best be moved in a branch so we can review the code. I'll work on it.

[thedmd]

The reason I asked about if it worked with transparent color is I am not sure how to select where to draw the fringe.

Oh. That part is identical to convex version. Whole vertex buffer is identical, so fringe goes along the path. What differs is the method of picking triangle indices from inner vertices.

Oh I see. But since triangular is not going to be a public helper there's no point in exposing this, as we always evaluate the scratch buffer size.

👍

[ocornut]

We have merged a concave polygon filler now, based on work from @thedmd 🎉 Main commit 1ff90c52d + various tweaks/tidying up fbf45ad14