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

inflex commented

2016-08-01 13:25:24 +00:00

(Migrated from github.com)

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.

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 commented

2016-08-01 13:35:19 +00:00

(Migrated from github.com)

You are looking for polygon triangulation

O(n log n) algorithms exist.

You are looking for [polygon triangulation](https://en.wikipedia.org/wiki/Polygon_triangulation) O(n log n) algorithms exist.

👍 1

ocornut commented

2016-08-01 15:27:28 +00:00

(Migrated from github.com)

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

👍 1

inflex commented

2016-08-01 15:33:34 +00:00

(Migrated from github.com)

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 commented

2016-08-02 02:47:04 +00:00

(Migrated from github.com)

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.

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. ![ss](https://cloud.githubusercontent.com/assets/5660591/17316920/a3f16a86-58bb-11e6-9ccf-dfeb379552d1.png) ![ss](https://cloud.githubusercontent.com/assets/5660591/17316960/07065d7a-58bc-11e6-9ba3-39290725973b.png)

👍 2

ocornut commented

2016-08-03 08:09:54 +00:00

(Migrated from github.com)

It looks pretty good and not noisy here.

inflex commented

2016-08-03 08:44:08 +00:00

(Migrated from github.com)

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.

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 commented

2016-08-03 09:47:34 +00:00

(Migrated from github.com)

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

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](https://github.com/ocornut/imgui/files/399142/scanfillflood.zip)

inflex commented

2016-08-03 09:58:37 +00:00

(Migrated from github.com)

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

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](https://github.com/ocornut/imgui/files/399150/scanfillflood-2.zip)

❤️ 1

ocornut commented

2016-08-03 10:28:43 +00:00

(Migrated from github.com)

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.

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 commented

2016-08-03 14:27:24 +00:00

(Migrated from github.com)

@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 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 commented

2016-08-05 14:32:34 +00:00

(Migrated from github.com)

Closing this now, if that's ok.

👍 1

Flix01 commented

2016-08-06 15:44:49 +00:00

(Migrated from github.com)

@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**: 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...

👍 1

inflex commented

2016-08-06 15:50:08 +00:00

(Migrated from github.com)

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 :)

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 commented

2016-08-06 15:56:40 +00:00

(Migrated from github.com)

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.

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 commented

2016-08-06 16:05:25 +00:00

(Migrated from github.com)

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).

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 commented

2016-08-06 16:22:34 +00:00

(Migrated from github.com)

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.

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. ![ss](https://cloud.githubusercontent.com/assets/5660591/17457777/b6d17ff6-5c44-11e6-8988-40f6de844e12.png)

ocornut commented

2016-08-06 16:47:05 +00:00

(Migrated from github.com)

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.

👍 1

Flix01 commented

2016-08-07 13:30:24 +00:00

(Migrated from github.com)

@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: 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 commented

2016-08-07 13:45:26 +00:00

(Migrated from github.com)

@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.

@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 commented

2016-08-07 14:17:41 +00:00

(Migrated from github.com)

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.!

> 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 commented

2016-08-07 14:31:52 +00:00

(Migrated from github.com)

@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):
Flix01/imgui@41178a2adc/addons/imguihelper/imguihelper.h (L52)
Flix01/imgui@41178a2adc/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: 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]. ![selection_030](https://cloud.githubusercontent.com/assets/9608982/17462936/576ddb22-5cbc-11e6-8815-5bc0340522c2.png) 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 commented

2016-08-07 14:44:23 +00:00

(Migrated from github.com)

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.

> 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.

👍 1

Flix01 commented

2016-08-07 15:27:10 +00:00

(Migrated from github.com)

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):

> 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): ![selection_031](https://cloud.githubusercontent.com/assets/9608982/17463343/f8187bb6-5cc3-11e6-8509-c19a15f1bace.png)

👍 1

inflex commented

2016-08-07 16:00:02 +00:00

(Migrated from github.com)

@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? 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 commented

2016-08-08 10:43:01 +00:00

(Migrated from github.com)

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...)]:

> 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...)]: ![selection_032](https://cloud.githubusercontent.com/assets/9608982/17477432/946480e0-5d65-11e6-9340-cce422d7638b.png)

👍 1

ocornut commented

2016-08-08 11:17:47 +00:00

(Migrated from github.com)

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 commented

2016-08-08 11:22:18 +00:00

(Migrated from github.com)

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.

> 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 commented

2016-08-08 11:30:10 +00:00

(Migrated from github.com)

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

Flix01 commented

2016-08-08 11:59:15 +00:00

(Migrated from github.com)

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.

> 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 commented

2016-08-08 12:32:03 +00:00

(Migrated from github.com)

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...)!

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 commented

2020-08-21 10:37:06 +00:00

(Migrated from github.com)

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.

For anyone still needing to do this, I solved it by using tessellation and [this library](https://github.com/mapbox/earcut.hpp), works great with good performance. Just make sure you draw an edge to your triangles to fill in gaps between them.

VerTiGoEtrex commented

2022-09-22 04:50:49 +00:00

(Migrated from github.com)

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?

I'm using @pierr3 's solution, but running into some issues with gaps appearing between my triangles which I can't seem to resolve. ![1663821839](https://user-images.githubusercontent.com/2846960/191660209-f52b85f9-3c34-4b60-a0d9-3b143cc4f5cd.png) (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? ![1663822096](https://user-images.githubusercontent.com/2846960/191660791-f9727a6a-c3ca-4cff-ab51-1a4202a21ffa.png)

pierr3 commented

2022-09-22 05:11:32 +00:00

(Migrated from github.com)

@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.

> @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.

👍 1

Rows
Columns

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