summaryrefslogtreecommitdiff
path: root/scene/resources/bit_mask.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'scene/resources/bit_mask.cpp')
-rw-r--r--scene/resources/bit_mask.cpp220
1 files changed, 158 insertions, 62 deletions
diff --git a/scene/resources/bit_mask.cpp b/scene/resources/bit_mask.cpp
index 85e36abf4e..39206ed043 100644
--- a/scene/resources/bit_mask.cpp
+++ b/scene/resources/bit_mask.cpp
@@ -29,6 +29,7 @@
/*************************************************************************/
#include "bit_mask.h"
+
#include "io/image_loader.h"
void BitMap::create(const Size2 &p_size) {
@@ -189,13 +190,13 @@ Vector<Vector2> BitMap::_march_square(const Rect2i &rect, const Point2i &start)
{ //square value
/*
- checking the 2x2 pixel grid, assigning these values to each pixel, if not transparent
- +---+---+
- | 1 | 2 |
- +---+---+
- | 4 | 8 | <- current pixel (curx,cury)
- +---+---+
- */
+ checking the 2x2 pixel grid, assigning these values to each pixel, if not transparent
+ +---+---+
+ | 1 | 2 |
+ +---+---+
+ | 4 | 8 | <- current pixel (curx,cury)
+ +---+---+
+ */
//NOTE: due to the way we pick points from texture, rect needs to be smaller, otherwise it goes outside 1 pixel
Rect2i fixed_rect = Rect2i(rect.position, rect.size - Size2i(2, 2));
Point2i tl = Point2i(curx - 1, cury - 1);
@@ -215,13 +216,13 @@ Vector<Vector2> BitMap::_march_square(const Rect2i &rect, const Point2i &start)
case 5:
case 13:
/* going UP with these cases:
- 1 5 13
- +---+---+ +---+---+ +---+---+
- | 1 | | | 1 | | | 1 | |
- +---+---+ +---+---+ +---+---+
- | | | | 4 | | | 4 | 8 |
- +---+---+ +---+---+ +---+---+
- */
+ 1 5 13
+ +---+---+ +---+---+ +---+---+
+ | 1 | | | 1 | | | 1 | |
+ +---+---+ +---+---+ +---+---+
+ | | | | 4 | | | 4 | 8 |
+ +---+---+ +---+---+ +---+---+
+ */
stepx = 0;
stepy = -1;
break;
@@ -230,13 +231,13 @@ Vector<Vector2> BitMap::_march_square(const Rect2i &rect, const Point2i &start)
case 10:
case 11:
/* going DOWN with these cases:
- 8 10 11
- +---+---+ +---+---+ +---+---+
- | | | | | 2 | | 1 | 2 |
- +---+---+ +---+---+ +---+---+
- | | 8 | | | 8 | | | 8 |
- +---+---+ +---+---+ +---+---+
- */
+ 8 10 11
+ +---+---+ +---+---+ +---+---+
+ | | | | | 2 | | 1 | 2 |
+ +---+---+ +---+---+ +---+---+
+ | | 8 | | | 8 | | | 8 |
+ +---+---+ +---+---+ +---+---+
+ */
stepx = 0;
stepy = 1;
break;
@@ -245,13 +246,13 @@ Vector<Vector2> BitMap::_march_square(const Rect2i &rect, const Point2i &start)
case 12:
case 14:
/* going LEFT with these cases:
- 4 12 14
- +---+---+ +---+---+ +---+---+
- | | | | | | | | 2 |
- +---+---+ +---+---+ +---+---+
- | 4 | | | 4 | 8 | | 4 | 8 |
- +---+---+ +---+---+ +---+---+
- */
+ 4 12 14
+ +---+---+ +---+---+ +---+---+
+ | | | | | | | | 2 |
+ +---+---+ +---+---+ +---+---+
+ | 4 | | | 4 | 8 | | 4 | 8 |
+ +---+---+ +---+---+ +---+---+
+ */
stepx = -1;
stepy = 0;
break;
@@ -260,25 +261,25 @@ Vector<Vector2> BitMap::_march_square(const Rect2i &rect, const Point2i &start)
case 3:
case 7:
/* going RIGHT with these cases:
- 2 3 7
- +---+---+ +---+---+ +---+---+
- | | 2 | | 1 | 2 | | 1 | 2 |
- +---+---+ +---+---+ +---+---+
- | | | | | | | 4 | |
- +---+---+ +---+---+ +---+---+
- */
+ 2 3 7
+ +---+---+ +---+---+ +---+---+
+ | | 2 | | 1 | 2 | | 1 | 2 |
+ +---+---+ +---+---+ +---+---+
+ | | | | | | | 4 | |
+ +---+---+ +---+---+ +---+---+
+ */
stepx = 1;
stepy = 0;
break;
case 9:
/*
- +---+---+
- | 1 | |
- +---+---+
- | | 8 |
- +---+---+
- this should normally go UP, but if we already been here, we go down
- */
+ +---+---+
+ | 1 | |
+ +---+---+
+ | | 8 |
+ +---+---+
+ this should normally go UP, but if we already been here, we go down
+ */
if (case9s.has(Point2i(curx, cury))) {
//found, so we go down, and delete from case9s;
stepx = 0;
@@ -293,14 +294,14 @@ Vector<Vector2> BitMap::_march_square(const Rect2i &rect, const Point2i &start)
break;
case 6:
/*
- 6
- +---+---+
- | | 2 |
- +---+---+
- | 4 | |
- +---+---+
- this normally go RIGHT, but if its coming from UP, it should go LEFT
- */
+ 6
+ +---+---+
+ | | 2 |
+ +---+---+
+ | 4 | |
+ +---+---+
+ this normally go RIGHT, but if its coming from UP, it should go LEFT
+ */
if (case6s.has(Point2i(curx, cury))) {
//found, so we go down, and delete from case6s;
stepx = -1;
@@ -418,31 +419,91 @@ static Vector<Vector2> reduce(const Vector<Vector2> &points, const Rect2i &rect,
return result;
}
+struct FillBitsStackEntry {
+ Point2i pos;
+ int i;
+ int j;
+};
+
static void fill_bits(const BitMap *p_src, Ref<BitMap> &p_map, const Point2i &p_pos, const Rect2i &rect) {
- for (int i = p_pos.x - 1; i <= p_pos.x + 1; i++) {
- for (int j = p_pos.y - 1; j <= p_pos.y + 1; j++) {
+ // Using a custom stack to work iteratively to avoid stack overflow on big bitmaps
+ PoolVector<FillBitsStackEntry> stack;
+ // Tracking size since we won't be shrinking the stack vector
+ int stack_size = 0;
- if (i < rect.position.x || i >= rect.position.x + rect.size.x)
- continue;
- if (j < rect.position.y || j >= rect.position.y + rect.size.y)
- continue;
+ Point2i pos = p_pos;
+ int next_i;
+ int next_j;
- if (p_map->get_bit(Vector2(i, j)))
- continue;
+ bool reenter = true;
+ bool popped = false;
+ do {
+ if (reenter) {
+ next_i = pos.x - 1;
+ next_j = pos.y - 1;
+ reenter = false;
+ }
+
+ for (int i = next_i; i <= pos.x + 1; i++) {
+ for (int j = next_j; j <= pos.y + 1; j++) {
+ if (popped) {
+ // The next loop over j must start normally
+ next_j = pos.y;
+ popped = false;
+ // Skip because an iteration was already executed with current counter values
+ continue;
+ }
- else if (p_src->get_bit(Vector2(i, j))) {
- p_map->set_bit(Vector2(i, j), true);
- fill_bits(p_src, p_map, Point2i(i, j), rect);
+ if (i < rect.position.x || i >= rect.position.x + rect.size.x)
+ continue;
+ if (j < rect.position.y || j >= rect.position.y + rect.size.y)
+ continue;
+
+ if (p_map->get_bit(Vector2(i, j)))
+ continue;
+
+ else if (p_src->get_bit(Vector2(i, j))) {
+ p_map->set_bit(Vector2(i, j), true);
+
+ FillBitsStackEntry se = { pos, i, j };
+ stack.resize(MAX(stack_size + 1, stack.size()));
+ stack.set(stack_size, se);
+ stack_size++;
+
+ pos = Point2i(i, j);
+ reenter = true;
+ break;
+ }
+ }
+ if (reenter) {
+ break;
}
}
- }
+ if (!reenter) {
+ if (stack_size) {
+ FillBitsStackEntry se = stack.get(stack_size - 1);
+ stack_size--;
+ pos = se.pos;
+ next_i = se.i;
+ next_j = se.j;
+ popped = true;
+ }
+ }
+ } while (reenter || popped);
+
+#ifdef DEBUG_ENABLED
+ print_line("max stack size: " + itos(stack.size()));
+#endif
}
+
Vector<Vector<Vector2> > BitMap::clip_opaque_to_polygons(const Rect2 &p_rect, float p_epsilon) const {
Rect2i r = Rect2i(0, 0, width, height).clip(p_rect);
+#ifdef DEBUG_ENABLED
print_line("Rect: " + r);
+#endif
Point2i from;
Ref<BitMap> fill;
fill.instance();
@@ -454,9 +515,13 @@ Vector<Vector<Vector2> > BitMap::clip_opaque_to_polygons(const Rect2 &p_rect, fl
if (!fill->get_bit(Point2(j, i)) && get_bit(Point2(j, i))) {
Vector<Vector2> polygon = _march_square(r, Point2i(j, i));
+#ifdef DEBUG_ENABLED
print_line("pre reduce: " + itos(polygon.size()));
+#endif
polygon = reduce(polygon, r, p_epsilon);
+#ifdef DEBUG_ENABLED
print_line("post reduce: " + itos(polygon.size()));
+#endif
polygons.push_back(polygon);
fill_bits(this, fill, Point2i(j, i), r);
}
@@ -510,6 +575,34 @@ void BitMap::grow_mask(int p_pixels, const Rect2 &p_rect) {
}
}
+Array BitMap::_opaque_to_polygons_bind(const Rect2 &p_rect, float p_epsilon) const {
+
+ Vector<Vector<Vector2> > result = clip_opaque_to_polygons(p_rect, p_epsilon);
+
+ // Convert result to bindable types
+
+ Array result_array;
+ result_array.resize(result.size());
+ for (int i = 0; i < result.size(); i++) {
+
+ const Vector<Vector2> &polygon = result[i];
+
+ PoolVector2Array polygon_array;
+ polygon_array.resize(polygon.size());
+
+ {
+ PoolVector2Array::Write w = polygon_array.write();
+ for (int j = 0; j < polygon.size(); j++) {
+ w[j] = polygon[j];
+ }
+ }
+
+ result_array[i] = polygon_array;
+ }
+
+ return result_array;
+}
+
void BitMap::_bind_methods() {
ClassDB::bind_method(D_METHOD("create", "size"), &BitMap::create);
@@ -526,6 +619,9 @@ void BitMap::_bind_methods() {
ClassDB::bind_method(D_METHOD("_set_data"), &BitMap::_set_data);
ClassDB::bind_method(D_METHOD("_get_data"), &BitMap::_get_data);
+ ClassDB::bind_method(D_METHOD("grow_mask", "pixels", "rect"), &BitMap::grow_mask);
+ ClassDB::bind_method(D_METHOD("opaque_to_polygons", "rect", "epsilon"), &BitMap::_opaque_to_polygons_bind, DEFVAL(2.0));
+
ADD_PROPERTY(PropertyInfo(Variant::DICTIONARY, "data", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_NOEDITOR | PROPERTY_USAGE_INTERNAL), "_set_data", "_get_data");
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-11 09:47:18 +0000