text: /*************************************************************************/
  /*  geometry_2d.cpp                                                      */
  /*************************************************************************/
  /*                       This file is part of:                           */
  /*                           Valjang Engine                                */
  /*                      http://Valjang.fr                          */
  /*************************************************************************/
  /* Copyright (c) 2007-2020 Valjang.                 */
  /* Copyright (c) 2014-2020 Valjang 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 "geometry_2d.h"
  
  #include "thirdparty/misc/clipper.hpp"
  #include "thirdparty/misc/triangulator.h"
  #define STB_RECT_PACK_IMPLEMENTATION
  #include "thirdparty/misc/stb_rect_pack.h"
  
  #define SCALE_FACTOR 100000.0 // Based on CMP_EPSILON.
  
  Vector<Vector<Vector2>> Geometry2D::decompose_polygon_in_convex(Vector<Point2> polygon) {
  	Vector<Vector<Vector2>> decomp;
  	List<TriangulatorPoly> in_poly, out_poly;
  
  	TriangulatorPoly inp;
  	inp.Init(polygon.size());
  	for (int i = 0; i < polygon.size(); i++) {
  		inp.GetPoint(i) = polygon[i];
  	}
  	inp.SetOrientation(TRIANGULATOR_CCW);
  	in_poly.push_back(inp);
  	TriangulatorPartition tpart;
  	if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { // Failed.
  		ERR_PRINT("Convex decomposing failed!");
  		return decomp;
  	}
  
  	decomp.resize(out_poly.size());
  	int idx = 0;
  	for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) {
  		TriangulatorPoly &tp = I->get();
  
  		decomp.write[idx].resize(tp.GetNumPoints());
  
  		for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
  			decomp.write[idx].write[i] = tp.GetPoint(i);
  		}
  
  		idx++;
  	}
  
  	return decomp;
  }
  
  struct _AtlasWorkRect {
  	Size2i s;
  	Point2i p;
  	int idx;
  	_FORCE_INLINE_ bool operator<(const _AtlasWorkRect &p_r) const { return s.width > p_r.s.width; };
  };
  
  struct _AtlasWorkRectResult {
  	Vector<_AtlasWorkRect> result;
  	int max_w;
  	int max_h;
  };
  
  void Geometry2D::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size) {
  	// Super simple, almost brute force scanline stacking fitter.
  	// It's pretty basic for now, but it tries to make sure that the aspect ratio of the
  	// resulting atlas is somehow square. This is necessary because video cards have limits.
  	// On texture size (usually 2048 or 4096), so the more square a texture, the more chances.
  	// It will work in every hardware.
  	// For example, it will prioritize a 1024x1024 atlas (works everywhere) instead of a
  	// 256x8192 atlas (won't work anywhere).
  
  	ERR_FAIL_COND(p_rects.size() == 0);
  
  	Vector<_AtlasWorkRect> wrects;
  	wrects.resize(p_rects.size());
  	for (int i = 0; i < p_rects.size(); i++) {
  		wrects.write[i].s = p_rects[i];
  		wrects.write[i].idx = i;
  	}
  	wrects.sort();
  	int widest = wrects[0].s.width;
  
  	Vector<_AtlasWorkRectResult> results;
  
  	for (int i = 0; i <= 12; i++) {
  		int w = 1 << i;
  		int max_h = 0;
  		int max_w = 0;
  		if (w < widest) {
  			continue;
  		}
  
  		Vector<int> hmax;
  		hmax.resize(w);
  		for (int j = 0; j < w; j++) {
  			hmax.write[j] = 0;
  		}
  
  		// Place them.
  		int ofs = 0;
  		int limit_h = 0;
  		for (int j = 0; j < wrects.size(); j++) {
  			if (ofs + wrects[j].s.width > w) {
  				ofs = 0;
  			}
  
  			int from_y = 0;
  			for (int k = 0; k < wrects[j].s.width; k++) {
  				if (hmax[ofs + k] > from_y) {
  					from_y = hmax[ofs + k];
  				}
  			}
  
  			wrects.write[j].p.x = ofs;
  			wrects.write[j].p.y = from_y;
  			int end_h = from_y + wrects[j].s.height;
  			int end_w = ofs + wrects[j].s.width;
  			if (ofs == 0) {
  				limit_h = end_h;
  			}
  
  			for (int k = 0; k < wrects[j].s.width; k++) {
  				hmax.write[ofs + k] = end_h;
  			}
  
  			if (end_h > max_h) {
  				max_h = end_h;
  			}
  
  			if (end_w > max_w) {
  				max_w = end_w;
  			}
  
  			if (ofs == 0 || end_h > limit_h) { // While h limit not reached, keep stacking.
  				ofs += wrects[j].s.width;
  			}
  		}
  
  		_AtlasWorkRectResult result;
  		result.result = wrects;
  		result.max_h = max_h;
  		result.max_w = max_w;
  		results.push_back(result);
  	}
  
  	// Find the result with the best aspect ratio.
  
  	int best = -1;
  	real_t best_aspect = 1e20;
  
  	for (int i = 0; i < results.size(); i++) {
  		real_t h = next_power_of_2(results[i].max_h);
  		real_t w = next_power_of_2(results[i].max_w);
  		real_t aspect = h > w ? h / w : w / h;
  		if (aspect < best_aspect) {
  			best = i;
  			best_aspect = aspect;
  		}
  	}
  
  	r_result.resize(p_rects.size());
  
  	for (int i = 0; i < p_rects.size(); i++) {
  		r_result.write[results[best].result[i].idx] = results[best].result[i].p;
  	}
  
  	r_size = Size2(results[best].max_w, results[best].max_h);
  }
  
  Vector<Vector<Point2>> Geometry2D::_polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open) {
  	using namespace ClipperLib;
  
  	ClipType op = ctUnion;
  
  	switch (p_op) {
  		case OPERATION_UNION:
  			op = ctUnion;
  			break;
  		case OPERATION_DIFFERENCE:
  			op = ctDifference;
  			break;
  		case OPERATION_INTERSECTION:
  			op = ctIntersection;
  			break;
  		case OPERATION_XOR:
  			op = ctXor;
  			break;
  	}
  	Path path_a, path_b;
  
  	// Need to scale points (Clipper's requirement for robust computation).
  	for (int i = 0; i != p_polypath_a.size(); ++i) {
  		path_a << IntPoint(p_polypath_a[i].x * SCALE_FACTOR, p_polypath_a[i].y * SCALE_FACTOR);
  	}
  	for (int i = 0; i != p_polypath_b.size(); ++i) {
  		path_b << IntPoint(p_polypath_b[i].x * SCALE_FACTOR, p_polypath_b[i].y * SCALE_FACTOR);
  	}
  	Clipper clp;
  	clp.AddPath(path_a, ptSubject, !is_a_open); // Forward compatible with Clipper 10.0.0.
  	clp.AddPath(path_b, ptClip, true); // Polylines cannot be set as clip.
  
  	Paths paths;
  
  	if (is_a_open) {
  		PolyTree tree; // Needed to populate polylines.
  		clp.Execute(op, tree);
  		OpenPathsFromPolyTree(tree, paths);
  	} else {
  		clp.Execute(op, paths); // Works on closed polygons only.
  	}
  	// Have to scale points down now.
  	Vector<Vector<Point2>> polypaths;
  
  	for (Paths::size_type i = 0; i < paths.size(); ++i) {
  		Vector<Vector2> polypath;
  
  		const Path &scaled_path = paths[i];
  
  		for (Paths::size_type j = 0; j < scaled_path.size(); ++j) {
  			polypath.push_back(Point2(
  					static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR,
  					static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR));
  		}
  		polypaths.push_back(polypath);
  	}
  	return polypaths;
  }
  
  Vector<Vector<Point2>> Geometry2D::_polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) {
  	using namespace ClipperLib;
  
  	JoinType jt = jtSquare;
  
  	switch (p_join_type) {
  		case JOIN_SQUARE:
  			jt = jtSquare;
  			break;
  		case JOIN_ROUND:
  			jt = jtRound;
  			break;
  		case JOIN_MITER:
  			jt = jtMiter;
  			break;
  	}
  
  	EndType et = etClosedPolygon;
  
  	switch (p_end_type) {
  		case END_POLYGON:
  			et = etClosedPolygon;
  			break;
  		case END_JOINED:
  			et = etClosedLine;
  			break;
  		case END_BUTT:
  			et = etOpenButt;
  			break;
  		case END_SQUARE:
  			et = etOpenSquare;
  			break;
  		case END_ROUND:
  			et = etOpenRound;
  			break;
  	}
  	ClipperOffset co(2.0, 0.25 * SCALE_FACTOR); // Defaults from ClipperOffset.
  	Path path;
  
  	// Need to scale points (Clipper's requirement for robust computation).
  	for (int i = 0; i != p_polypath.size(); ++i) {
  		path << IntPoint(p_polypath[i].x * SCALE_FACTOR, p_polypath[i].y * SCALE_FACTOR);
  	}
  	co.AddPath(path, jt, et);
  
  	Paths paths;
  	co.Execute(paths, p_delta * SCALE_FACTOR); // Inflate/deflate.
  
  	// Have to scale points down now.
  	Vector<Vector<Point2>> polypaths;
  
  	for (Paths::size_type i = 0; i < paths.size(); ++i) {
  		Vector<Vector2> polypath;
  
  		const Path &scaled_path = paths[i];
  
  		for (Paths::size_type j = 0; j < scaled_path.size(); ++j) {
  			polypath.push_back(Point2(
  					static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR,
  					static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR));
  		}
  		polypaths.push_back(polypath);
  	}
  	return polypaths;
  }
  
  Vector<Point2i> Geometry2D::pack_rects(const Vector<Size2i> &p_sizes, const Size2i &p_atlas_size) {
  	Vector<stbrp_node> nodes;
  	nodes.resize(p_atlas_size.width);
  
  	stbrp_context context;
  	stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
  
  	Vector<stbrp_rect> rects;
  	rects.resize(p_sizes.size());
  
  	for (int i = 0; i < p_sizes.size(); i++) {
  		rects.write[i].id = 0;
  		rects.write[i].w = p_sizes[i].width;
  		rects.write[i].h = p_sizes[i].height;
  		rects.write[i].x = 0;
  		rects.write[i].y = 0;
  		rects.write[i].was_packed = 0;
  	}
  
  	int res = stbrp_pack_rects(&context, rects.ptrw(), rects.size());
  	if (res == 0) { //pack failed
  		return Vector<Point2i>();
  	}
  
  	Vector<Point2i> ret;
  	ret.resize(p_sizes.size());
  
  	for (int i = 0; i < p_sizes.size(); i++) {
  		Point2i r(rects[i].x, rects[i].y);
  		ret.write[i] = r;
  	}
  
  	return ret;
  }
  
  Vector<Vector3i> Geometry2D::partial_pack_rects(const Vector<Vector2i> &p_sizes, const Size2i &p_atlas_size) {
  	Vector<stbrp_node> nodes;
  	nodes.resize(p_atlas_size.width);
  	zeromem(nodes.ptrw(), sizeof(stbrp_node) * nodes.size());
  
  	stbrp_context context;
  	stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
  
  	Vector<stbrp_rect> rects;
  	rects.resize(p_sizes.size());
  
  	for (int i = 0; i < p_sizes.size(); i++) {
  		rects.write[i].id = i;
  		rects.write[i].w = p_sizes[i].width;
  		rects.write[i].h = p_sizes[i].height;
  		rects.write[i].x = 0;
  		rects.write[i].y = 0;
  		rects.write[i].was_packed = 0;
  	}
  
  	stbrp_pack_rects(&context, rects.ptrw(), rects.size());
  
  	Vector<Vector3i> ret;
  	ret.resize(p_sizes.size());
  
  	for (int i = 0; i < p_sizes.size(); i++) {
  		ret.write[rects[i].id] = Vector3i(rects[i].x, rects[i].y, rects[i].was_packed != 0 ? 1 : 0);
  	}
  
  	return ret;
  }
  