text: /*************************************************************************/
  /*  bit_map.cpp                                                          */
  /*************************************************************************/
  /*                       This file is part of:                           */
  /*                           GODOT ENGINE                                */
  /*                      https://godotengine.org                          */
  /*************************************************************************/
  /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur.                 */
  /* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md).   */
  /*                                                                       */
  /* Permission is hereby granted, free of charge, to any person obtaining */
  /* a copy of this software and associated documentation files (the       */
  /* "Software"), to deal in the Software without restriction, including   */
  /* without limitation the rights to use, copy, modify, merge, publish,   */
  /* distribute, sublicense, and/or sell copies of the Software, and to    */
  /* permit persons to whom the Software is furnished to do so, subject to */
  /* the following conditions:                                             */
  /*                                                                       */
  /* The above copyright notice and this permission notice shall be        */
  /* included in all copies or substantial portions of the Software.       */
  /*                                                                       */
  /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       */
  /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    */
  /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
  /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY  */
  /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,  */
  /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE     */
  /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
  /*************************************************************************/
  
  #include "bit_map.h"
  
  #include "core/io/image_loader.h"
  
  void BitMap::create(const Size2 &p_size) {
  
  	ERR_FAIL_COND(p_size.width < 1);
  	ERR_FAIL_COND(p_size.height < 1);
  
  	width = p_size.width;
  	height = p_size.height;
  	bitmask.resize(((width * height) / 8) + 1);
  	zeromem(bitmask.ptrw(), bitmask.size());
  }
  
  void BitMap::create_from_image_alpha(const Ref<Image> &p_image, float p_threshold) {
  
  	ERR_FAIL_COND(p_image.is_null() || p_image->empty());
  	Ref<Image> img = p_image->duplicate();
  	img->convert(Image::FORMAT_LA8);
  	ERR_FAIL_COND(img->get_format() != Image::FORMAT_LA8);
  
  	create(Size2(img->get_width(), img->get_height()));
  
  	const uint8_t *r = img->get_data().ptr();
  	uint8_t *w = bitmask.ptrw();
  
  	for (int i = 0; i < width * height; i++) {
  
  		int bbyte = i / 8;
  		int bbit = i % 8;
  		if (r[i * 2 + 1] / 255.0 > p_threshold) {
  			w[bbyte] |= (1 << bbit);
  		}
  	}
  }
  
  void BitMap::set_bit_rect(const Rect2 &p_rect, bool p_value) {
  
  	Rect2i current = Rect2i(0, 0, width, height).clip(p_rect);
  	uint8_t *data = bitmask.ptrw();
  
  	for (int i = current.position.x; i < current.position.x + current.size.x; i++) {
  
  		for (int j = current.position.y; j < current.position.y + current.size.y; j++) {
  
  			int ofs = width * j + i;
  			int bbyte = ofs / 8;
  			int bbit = ofs % 8;
  
  			uint8_t b = data[bbyte];
  
  			if (p_value)
  				b |= (1 << bbit);
  			else
  				b &= ~(1 << bbit);
  
  			data[bbyte] = b;
  		}
  	}
  }
  
  int BitMap::get_true_bit_count() const {
  
  	int ds = bitmask.size();
  	const uint8_t *d = bitmask.ptr();
  	int c = 0;
  
  	//fast, almost branchless version
  
  	for (int i = 0; i < ds; i++) {
  
  		c += (d[i] & (1 << 7)) >> 7;
  		c += (d[i] & (1 << 6)) >> 6;
  		c += (d[i] & (1 << 5)) >> 5;
  		c += (d[i] & (1 << 4)) >> 4;
  		c += (d[i] & (1 << 3)) >> 3;
  		c += (d[i] & (1 << 2)) >> 2;
  		c += (d[i] & (1 << 1)) >> 1;
  		c += d[i] & 1;
  	}
  
  	return c;
  }
  
  void BitMap::set_bit(const Point2 &p_pos, bool p_value) {
  
  	int x = p_pos.x;
  	int y = p_pos.y;
  
  	ERR_FAIL_INDEX(x, width);
  	ERR_FAIL_INDEX(y, height);
  
  	int ofs = width * y + x;
  	int bbyte = ofs / 8;
  	int bbit = ofs % 8;
  
  	uint8_t b = bitmask[bbyte];
  
  	if (p_value)
  		b |= (1 << bbit);
  	else
  		b &= ~(1 << bbit);
  
  	bitmask.write[bbyte] = b;
  }
  
  bool BitMap::get_bit(const Point2 &p_pos) const {
  
  	int x = Math::fast_ftoi(p_pos.x);
  	int y = Math::fast_ftoi(p_pos.y);
  	ERR_FAIL_INDEX_V(x, width, false);
  	ERR_FAIL_INDEX_V(y, height, false);
  
  	int ofs = width * y + x;
  	int bbyte = ofs / 8;
  	int bbit = ofs % 8;
  
  	return (bitmask[bbyte] & (1 << bbit)) != 0;
  }
  
  Size2 BitMap::get_size() const {
  
  	return Size2(width, height);
  }
  
  void BitMap::_set_data(const Dictionary &p_d) {
  
  	ERR_FAIL_COND(!p_d.has("size"));
  	ERR_FAIL_COND(!p_d.has("data"));
  
  	create(p_d["size"]);
  	bitmask = p_d["data"];
  }
  
  Dictionary BitMap::_get_data() const {
  
  	Dictionary d;
  	d["size"] = get_size();
  	d["data"] = bitmask;
  	return d;
  }
  
  Vector<Vector2> BitMap::_march_square(const Rect2i &rect, const Point2i &start) const {
  
  	int stepx = 0;
  	int stepy = 0;
  	int prevx = 0;
  	int prevy = 0;
  	int startx = start.x;
  	int starty = start.y;
  	int curx = startx;
  	int cury = starty;
  	unsigned int count = 0;
  	Set<Point2i> case9s;
  	Set<Point2i> case6s;
  	Vector<Vector2> _points;
  	do {
  		int sv = 0;
  		{ //square value
  
  			/*
  			checking the 2x2 pixel grid, assigning these values to each pixel, if not transparent
  			+---+---+
  			| 1 | 2 |
  			+---+---+
  			| 4 | 8 | <- current pixel (curx,cury)
  			+---+---+
  			*/
  			Point2i tl = Point2i(curx - 1, cury - 1);
  			sv += (rect.has_point(tl) && get_bit(tl)) ? 1 : 0;
  			Point2i tr = Point2i(curx, cury - 1);
  			sv += (rect.has_point(tr) && get_bit(tr)) ? 2 : 0;
  			Point2i bl = Point2i(curx - 1, cury);
  			sv += (rect.has_point(bl) && get_bit(bl)) ? 4 : 0;
  			Point2i br = Point2i(curx, cury);
  			sv += (rect.has_point(br) && get_bit(br)) ? 8 : 0;
  			ERR_FAIL_COND_V(sv == 0 || sv == 15, Vector<Vector2>());
  		}
  
  		switch (sv) {
  
  			case 1:
  			case 5:
  			case 13:
  				/* going UP with these cases:
  				1          5           13
  				+---+---+  +---+---+  +---+---+
  				| 1 |   |  | 1 |   |  | 1 |   |
  				+---+---+  +---+---+  +---+---+
  				|   |   |  | 4 |   |  | 4 | 8 |
  				+---+---+  +---+---+  +---+---+
  				*/
  				stepx = 0;
  				stepy = -1;
  				break;
  
  			case 8:
  			case 10:
  			case 11:
  				/* going DOWN with these cases:
  				8          10         11
  				+---+---+  +---+---+  +---+---+
  				|   |   |  |   | 2 |  | 1 | 2 |
  				+---+---+  +---+---+  +---+---+
  				|   | 8 |  |   | 8 |  |   | 8 |
  				+---+---+  +---+---+  +---+---+
  				*/
  				stepx = 0;
  				stepy = 1;
  				break;
  
  			case 4:
  			case 12:
  			case 14:
  				/* going LEFT with these cases:
  				4          12         14
  				+---+---+  +---+---+  +---+---+
  				|   |   |  |   |   |  |   | 2 |
  				+---+---+  +---+---+  +---+---+
  				| 4 |   |  | 4 | 8 |  | 4 | 8 |
  				+---+---+  +---+---+  +---+---+
  				*/
  				stepx = -1;
  				stepy = 0;
  				break;
  
  			case 2:
  			case 3:
  			case 7:
  				/* going RIGHT with these cases:
  				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
  				*/
  				if (case9s.has(Point2i(curx, cury))) {
  					//found, so we go down, and delete from case9s;
  					stepx = 0;
  					stepy = 1;
  					case9s.erase(Point2i(curx, cury));
  				} else {
  					//not found, we go up, and add to case9s;
  					stepx = 0;
  					stepy = -1;
  					case9s.insert(Point2i(curx, cury));
  				}
  				break;
  			case 6:
  				/*
  				6
  				+---+---+
  				|   | 2 |
  				+---+---+
  				| 4 |   |
  				+---+---+
  				this normally go RIGHT, but if its coming from RIGHT, it should go LEFT
  				*/
  				if (case6s.has(Point2i(curx, cury))) {
  					//found, so we go left, and delete from case6s;
  					stepx = -1;
  					stepy = 0;
  					case6s.erase(Point2i(curx, cury));
  				} else {
  					//not found, we go right, and add to case6s;
  					stepx = 1;
  					stepy = 0;
  					case6s.insert(Point2i(curx, cury));
  				}
  				break;
  			default:
  				ERR_PRINT("this shouldn't happen.");
  		}
  		//little optimization
  		// if previous direction is same as current direction,
  		// then we should modify the last vec to current
  		curx += stepx;
  		cury += stepy;
  		if (stepx == prevx && stepy == prevy) {
  			_points.write[_points.size() - 1].x = (float)(curx - rect.position.x);
  			_points.write[_points.size() - 1].y = (float)(cury + rect.position.y);
  		} else {
  			_points.push_back(Vector2((float)(curx - rect.position.x), (float)(cury + rect.position.y)));
  		}
  
  		count++;
  		prevx = stepx;
  		prevy = stepy;
  
  		ERR_FAIL_COND_V((int)count > width * height, _points);
  	} while (curx != startx || cury != starty);
  	return _points;
  }
  
  static float perpendicular_distance(const Vector2 &i, const Vector2 &start, const Vector2 &end) {
  	float res;
  	float slope;
  	float intercept;
  
  	if (start.x == end.x) {
  		res = Math::absf(i.x - end.x);
  	} else if (start.y == end.y) {
  		res = Math::absf(i.y - end.y);
  	} else {
  		slope = (end.y - start.y) / (end.x - start.x);
  		intercept = start.y - (slope * start.x);
  		res = Math::absf(slope * i.x - i.y + intercept) / Math::sqrt(Math::pow(slope, 2.0f) + 1.0);
  	}
  	return res;
  }
  
  static Vector<Vector2> rdp(const Vector<Vector2> &v, float optimization) {
  	if (v.size() < 3)
  		return v;
  
  	int index = -1;
  	float dist = 0;
  	//not looping first and last point
  	for (size_t i = 1, size = v.size(); i < size - 1; ++i) {
  		float cdist = perpendicular_distance(v[i], v[0], v[v.size() - 1]);
  		if (cdist > dist) {
  			dist = cdist;
  			index = static_cast<int>(i);
  		}
  	}
  	if (dist > optimization) {
  
  		Vector<Vector2> left, right;
  		left.resize(index);
  		for (int i = 0; i < index; i++) {
  			left.write[i] = v[i];
  		}
  		right.resize(v.size() - index);
  		for (int i = 0; i < right.size(); i++) {
  			right.write[i] = v[index + i];
  		}
  		Vector<Vector2> r1 = rdp(left, optimization);
  		Vector<Vector2> r2 = rdp(right, optimization);
  
  		int middle = r1.size();
  		r1.resize(r1.size() + r2.size());
  		for (int i = 0; i < r2.size(); i++) {
  			r1.write[middle + i] = r2[i];
  		}
  		return r1;
  	} else {
  		Vector<Vector2> ret;
  		ret.push_back(v[0]);
  		ret.push_back(v[v.size() - 1]);
  		return ret;
  	}
  }
  
  static Vector<Vector2> reduce(const Vector<Vector2> &points, const Rect2i &rect, float epsilon) {
  	int size = points.size();
  	// if there are less than 3 points, then we have nothing
  	ERR_FAIL_COND_V(size < 3, Vector<Vector2>());
  	// if there are less than 9 points (but more than 3), then we don't need to reduce it
  	if (size < 9) {
  		return points;
  	}
  
  	float maxEp = MIN(rect.size.width, rect.size.height);
  	float ep = CLAMP(epsilon, 0.0, maxEp / 2);
  	Vector<Vector2> result = rdp(points, ep);
  
  	Vector2 last = result[result.size() - 1];
  
  	if (last.y > result[0].y && last.distance_to(result[0]) < ep * 0.5f) {
  		result.write[0].y = last.y;
  		result.resize(result.size() - 1);
  	}
  	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) {
  
  	// Using a custom stack to work iteratively to avoid stack overflow on big bitmaps
  	Vector<FillBitsStackEntry> stack;
  	// Tracking size since we won't be shrinking the stack vector
  	int stack_size = 0;
  
  	Point2i pos = p_pos;
  	int next_i = 0;
  	int next_j = 0;
  
  	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;
  				}
  
  				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);
  
  	print_verbose("BitMap: Max stack size: " + itos(stack.size()));
  }
  
  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);
  	print_verbose("BitMap: Rect: " + r);
  
  	Point2i from;
  	Ref<BitMap> fill;
  	fill.instance();
  	fill->create(get_size());
  
  	Vector<Vector<Vector2>> polygons;
  	for (int i = r.position.y; i < r.position.y + r.size.height; i++) {
  		for (int j = r.position.x; j < r.position.x + r.size.width; j++) {
  			if (!fill->get_bit(Point2(j, i)) && get_bit(Point2(j, i))) {
  
  				fill_bits(this, fill, Point2i(j, i), r);
  
  				Vector<Vector2> polygon = _march_square(r, Point2i(j, i));
  				print_verbose("BitMap: Pre reduce: " + itos(polygon.size()));
  				polygon = reduce(polygon, r, p_epsilon);
  				print_verbose("BitMap: Post reduce: " + itos(polygon.size()));
  
  				if (polygon.size() < 3) {
  					print_verbose("Invalid polygon, skipped");
  					continue;
  				}
  
  				polygons.push_back(polygon);
  			}
  		}
  	}
  
  	return polygons;
  }
  
  void BitMap::grow_mask(int p_pixels, const Rect2 &p_rect) {
  
  	if (p_pixels == 0) {
  		return;
  	}
  
  	bool bit_value = p_pixels > 0;
  	p_pixels = Math::abs(p_pixels);
  
  	Rect2i r = Rect2i(0, 0, width, height).clip(p_rect);
  
  	Ref<BitMap> copy;
  	copy.instance();
  	copy->create(get_size());
  	copy->bitmask = bitmask;
  
  	for (int i = r.position.y; i < r.position.y + r.size.height; i++) {
  		for (int j = r.position.x; j < r.position.x + r.size.width; j++) {
  			if (bit_value == get_bit(Point2(j, i)))
  				continue;
  
  			bool found = false;
  
  			for (int y = i - p_pixels; y <= i + p_pixels; y++) {
  				for (int x = j - p_pixels; x <= j + p_pixels; x++) {
  
  					bool outside = false;
  
  					if ((x < p_rect.position.x) || (x >= p_rect.position.x + p_rect.size.x) || (y < p_rect.position.y) || (y >= p_rect.position.y + p_rect.size.y)) {
  						// outside of rectangle counts as bit not set
  						if (!bit_value)
  							outside = true;
  						else
  							continue;
  					}
  
  					float d = Point2(j, i).distance_to(Point2(x, y)) - CMP_EPSILON;
  					if (d > p_pixels)
  						continue;
  
  					if (outside || (bit_value == copy->get_bit(Point2(x, y)))) {
  						found = true;
  						break;
  					}
  				}
  				if (found)
  					break;
  			}
  
  			if (found) {
  				set_bit(Point2(j, i), bit_value);
  			}
  		}
  	}
  }
  
  void BitMap::shrink_mask(int p_pixels, const Rect2 &p_rect) {
  
  	grow_mask(-p_pixels, 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];
  
  		PackedVector2Array polygon_array;
  		polygon_array.resize(polygon.size());
  
  		{
  			Vector2 *w = polygon_array.ptrw();
  			for (int j = 0; j < polygon.size(); j++) {
  				w[j] = polygon[j];
  			}
  		}
  
  		result_array[i] = polygon_array;
  	}
  
  	return result_array;
  }
  
  void BitMap::resize(const Size2 &p_new_size) {
  
  	Ref<BitMap> new_bitmap;
  	new_bitmap.instance();
  	new_bitmap->create(p_new_size);
  	int lw = MIN(width, p_new_size.width);
  	int lh = MIN(height, p_new_size.height);
  	for (int x = 0; x < lw; x++) {
  		for (int y = 0; y < lh; y++) {
  			new_bitmap->set_bit(Vector2(x, y), get_bit(Vector2(x, y)));
  		}
  	}
  
  	width = new_bitmap->width;
  	height = new_bitmap->height;
  	bitmask = new_bitmap->bitmask;
  }
  
  Ref<Image> BitMap::convert_to_image() const {
  
  	Ref<Image> image;
  	image.instance();
  	image->create(width, height, false, Image::FORMAT_L8);
  
  	for (int i = 0; i < width; i++) {
  		for (int j = 0; j < height; j++) {
  			image->set_pixel(i, j, get_bit(Point2(i, j)) ? Color(1, 1, 1) : Color(0, 0, 0));
  		}
  	}
  
  	return image;
  }
  void BitMap::blit(const Vector2 &p_pos, const Ref<BitMap> &p_bitmap) {
  
  	int x = p_pos.x;
  	int y = p_pos.y;
  	int w = p_bitmap->get_size().width;
  	int h = p_bitmap->get_size().height;
  
  	for (int i = 0; i < w; i++) {
  		for (int j = 0; j < h; j++) {
  			int px = x + i;
  			int py = y + j;
  			if (px < 0 || px >= width)
  				continue;
  			if (py < 0 || py >= height)
  				continue;
  			if (p_bitmap->get_bit(Vector2(i, j))) {
  				set_bit(Vector2(x, y), true);
  			}
  		}
  	}
  }
  
  void BitMap::_bind_methods() {
  
  	ClassDB::bind_method(D_METHOD("create", "size"), &BitMap::create);
  	ClassDB::bind_method(D_METHOD("create_from_image_alpha", "image", "threshold"), &BitMap::create_from_image_alpha, DEFVAL(0.1));
  
  	ClassDB::bind_method(D_METHOD("set_bit", "position", "bit"), &BitMap::set_bit);
  	ClassDB::bind_method(D_METHOD("get_bit", "position"), &BitMap::get_bit);
  
  	ClassDB::bind_method(D_METHOD("set_bit_rect", "rect", "bit"), &BitMap::set_bit_rect);
  	ClassDB::bind_method(D_METHOD("get_true_bit_count"), &BitMap::get_true_bit_count);
  
  	ClassDB::bind_method(D_METHOD("get_size"), &BitMap::get_size);
  
  	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");
  }
  
  BitMap::BitMap() {
  
  	width = 0;
  	height = 0;
  }
  
  //////////////////////////////////////
  