Imgui: Flood fill generic polygon (not strictly convex); methods?
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.
inflex
All 31 comments
You are looking for polygon triangulation
O(n log n) algorithms exist.
ratchetfreak
on 1 Aug 2016
If you implement something it would be nice to post your code here too :)
ocornut
on 1 Aug 2016
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
on 1 Aug 2016
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.
inflex
on 2 Aug 2016
It looks pretty good and not noisy here.
ocornut
on 3 Aug 2016
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
on 3 Aug 2016
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);
inflex
on 3 Aug 2016
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.
inflex
on 3 Aug 2016
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.
ocornut
on 3 Aug 2016
@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.
inflex
on 3 Aug 2016
Closing this now, if that's ok.
ocornut
on 5 Aug 2016
@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...
Flix01
on 6 Aug 2016
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
on 6 Aug 2016
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.
inflex
on 6 Aug 2016
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).
Flix01
on 6 Aug 2016
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.
inflex
on 6 Aug 2016
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.
ocornut
on 6 Aug 2016
@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.
Flix01
on 7 Aug 2016
@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.
inflex
on 7 Aug 2016
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.!
ocornut
on 7 Aug 2016
@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.
Flix01
on 7 Aug 2016
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.
inflex
on 7 Aug 2016
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):
Flix01
on 7 Aug 2016
@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 :)
inflex
on 7 Aug 2016
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...)]:
Flix01
on 8 Aug 2016
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).
ocornut
on 8 Aug 2016
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.
Flix01
on 8 Aug 2016
Definitely would prefer a range specifier, or predefined delimiter (-FLT_MAX, -FLT_MAX ? )
inflex
on 8 Aug 2016
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
on 8 Aug 2016
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...)!
Flix01
on 8 Aug 2016
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.
pierr3
on 21 Aug 2020
Related issues
bizehao
路
3Comments
inflex
路
3Comments
DarkLinux
路
3Comments
spaderthomas
路
3Comments
mkanakis
路
3Comments