diff options
| -rw-r--r-- | scene/resources/bit_mask.cpp | 119 | ||||
| -rw-r--r-- | scene/resources/bit_mask.h | 2 |
2 files changed, 109 insertions, 12 deletions
diff --git a/scene/resources/bit_mask.cpp b/scene/resources/bit_mask.cpp index 85e36abf4e..ec1aa7ec46 100644 --- a/scene/resources/bit_mask.cpp +++ b/scene/resources/bit_mask.cpp @@ -418,31 +418,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 +514,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 +574,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 +618,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"); } diff --git a/scene/resources/bit_mask.h b/scene/resources/bit_mask.h index dcd5edb4fb..40f0bfb04a 100644 --- a/scene/resources/bit_mask.h +++ b/scene/resources/bit_mask.h @@ -46,6 +46,8 @@ class BitMap : public Resource { Vector<Vector2> _march_square(const Rect2i &rect, const Point2i &start) const; + Array _opaque_to_polygons_bind(const Rect2 &p_rect, float p_epsilon) const; + protected: void _set_data(const Dictionary &p_d); Dictionary _get_data() const; |