diff options
85 files changed, 3558 insertions, 2173 deletions
diff --git a/.github/workflows/android_builds.yml b/.github/workflows/android_builds.yml index 143f3961cf..697600abe3 100644 --- a/.github/workflows/android_builds.yml +++ b/.github/workflows/android_builds.yml @@ -6,6 +6,7 @@ env: GODOT_BASE_BRANCH: master SCONSFLAGS: platform=android verbose=yes warnings=extra werror=yes --jobs=2 module_text_server_fb_enabled=yes SCONS_CACHE_LIMIT: 4096 + ANDROID_NDK_VERSION: 21.1.6352462 jobs: android-template: @@ -28,6 +29,10 @@ jobs: with: java-version: 8 + - name: Install Android NDK r21 + run: | + sudo ${ANDROID_HOME}/tools/bin/sdkmanager --install 'ndk;${{env.ANDROID_NDK_VERSION}}' + # Upload cache on completion and check it out now - name: Load .scons_cache directory id: android-template-cache @@ -59,7 +64,7 @@ jobs: - name: Compilation env: SCONS_CACHE: ${{github.workspace}}/.scons_cache/ - ANDROID_NDK_ROOT: /usr/local/lib/android/sdk/ndk-bundle + ANDROID_NDK_ROOT: /usr/local/lib/android/sdk/ndk/${{env.ANDROID_NDK_VERSION}}/ run: | scons target=release tools=no android_arch=armv7 scons target=release tools=no android_arch=arm64v8 diff --git a/.github/workflows/static_checks.yml b/.github/workflows/static_checks.yml index da3327246b..12270a848a 100644 --- a/.github/workflows/static_checks.yml +++ b/.github/workflows/static_checks.yml @@ -18,7 +18,9 @@ jobs: - name: Install dependencies run: | - sudo apt-get install -qq dos2unix recode clang-format + sudo apt-get install -qq dos2unix recode clang-format-11 + sudo update-alternatives --remove-all clang-format + sudo update-alternatives --install /usr/bin/clang-format clang-format /usr/bin/clang-format-11 100 sudo pip3 install black==20.8b1 pygments - name: File formatting checks (file_format.sh) diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md index 1abd76b2ff..4387750f28 100644 --- a/CONTRIBUTING.md +++ b/CONTRIBUTING.md @@ -72,6 +72,11 @@ by drag and dropping the file in the GitHub edition field. We recommend always attaching a minimal reproduction project, even if the issue may seem simple to reproduce manually. +**Note for C# users:** If your issue is not Mono-specific, please upload a +minimal reproduction project written in GDScript or VisualScript. +This will make it easier for contributors to reproduce the issue +locally as not everyone has a Mono setup available. + **If you've been asked by a maintainer to upload a minimal reproduction project, you *must* do so within 7 days.** Otherwise, your bug report will be closed as it'll be considered too difficult to diagnose. diff --git a/COPYRIGHT.txt b/COPYRIGHT.txt index 655c008083..b9b15abf5d 100644 --- a/COPYRIGHT.txt +++ b/COPYRIGHT.txt @@ -320,6 +320,12 @@ Comment: Minimal PCG32 implementation Copyright: 2014, M.E. O'Neill License: Apache-2.0 +Files: ./thirdparty/misc/polypartition.cpp + ./thirdparty/misc/polypartition.h +Comment: PolyPartition / Triangulator +Copyright: 2011-2021, Ivan Fratric and contributors +License: Expat + Files: ./thirdparty/misc/r128.c ./thirdparty/misc/r128.h Comment: r128 library @@ -338,12 +344,6 @@ Comment: stb libraries Copyright: Sean Barrett License: public-domain or Unlicense or Expat -Files: ./thirdparty/misc/triangulator.cpp - ./thirdparty/misc/triangulator.h -Comment: PolyPartition -Copyright: 2011, Ivan Fratric -License: Expat - Files: ./thirdparty/misc/yuv2rgb.h Comment: YUV2RGB Copyright: 2008-2011, Robin Watts diff --git a/core/SCsub b/core/SCsub index c9f84a9a00..21829553a7 100644 --- a/core/SCsub +++ b/core/SCsub @@ -54,7 +54,7 @@ thirdparty_misc_sources = [ "smaz.c", # C++ sources "pcg.cpp", - "triangulator.cpp", + "polypartition.cpp", "clipper.cpp", ] thirdparty_misc_sources = [thirdparty_misc_dir + file for file in thirdparty_misc_sources] diff --git a/core/core_bind.cpp b/core/core_bind.cpp index a84a208050..000b628ba7 100644 --- a/core/core_bind.cpp +++ b/core/core_bind.cpp @@ -228,24 +228,32 @@ Error _OS::shell_open(String p_uri) { return OS::get_singleton()->shell_open(p_uri); } -int _OS::execute(const String &p_path, const Vector<String> &p_arguments, bool p_blocking, Array p_output, bool p_read_stderr) { - OS::ProcessID pid = -2; - int exitcode = 0; +int _OS::execute(const String &p_path, const Vector<String> &p_arguments, Array r_output, bool p_read_stderr) { List<String> args; for (int i = 0; i < p_arguments.size(); i++) { args.push_back(p_arguments[i]); } String pipe; - Error err = OS::get_singleton()->execute(p_path, args, p_blocking, &pid, &pipe, &exitcode, p_read_stderr); - p_output.clear(); - p_output.push_back(pipe); + int exitcode = 0; + Error err = OS::get_singleton()->execute(p_path, args, &pipe, &exitcode, p_read_stderr); + r_output.push_back(pipe); + if (err != OK) { + return -1; + } + return exitcode; +} + +int _OS::create_process(const String &p_path, const Vector<String> &p_arguments) { + List<String> args; + for (int i = 0; i < p_arguments.size(); i++) { + args.push_back(p_arguments[i]); + } + OS::ProcessID pid = 0; + Error err = OS::get_singleton()->create_process(p_path, args, &pid); if (err != OK) { return -1; - } else if (p_blocking) { - return exitcode; - } else { - return pid; } + return pid; } Error _OS::kill(int p_pid) { @@ -697,7 +705,8 @@ void _OS::_bind_methods() { ClassDB::bind_method(D_METHOD("get_processor_count"), &_OS::get_processor_count); ClassDB::bind_method(D_METHOD("get_executable_path"), &_OS::get_executable_path); - ClassDB::bind_method(D_METHOD("execute", "path", "arguments", "blocking", "output", "read_stderr"), &_OS::execute, DEFVAL(true), DEFVAL(Array()), DEFVAL(false)); + ClassDB::bind_method(D_METHOD("execute", "path", "arguments", "output", "read_stderr"), &_OS::execute, DEFVAL(Array()), DEFVAL(false)); + ClassDB::bind_method(D_METHOD("create_process", "path", "arguments"), &_OS::create_process); ClassDB::bind_method(D_METHOD("kill", "pid"), &_OS::kill); ClassDB::bind_method(D_METHOD("shell_open", "uri"), &_OS::shell_open); ClassDB::bind_method(D_METHOD("get_process_id"), &_OS::get_process_id); diff --git a/core/core_bind.h b/core/core_bind.h index 30dfa2d7a8..665858cd26 100644 --- a/core/core_bind.h +++ b/core/core_bind.h @@ -155,8 +155,8 @@ public: int get_low_processor_usage_mode_sleep_usec() const; String get_executable_path() const; - int execute(const String &p_path, const Vector<String> &p_arguments, bool p_blocking = true, Array p_output = Array(), bool p_read_stderr = false); - + int execute(const String &p_path, const Vector<String> &p_arguments, Array r_output = Array(), bool p_read_stderr = false); + int create_process(const String &p_path, const Vector<String> &p_arguments); Error kill(int p_pid); Error shell_open(String p_uri); diff --git a/core/io/resource.cpp b/core/io/resource.cpp index 716da5e395..2c97e617f2 100644 --- a/core/io/resource.cpp +++ b/core/io/resource.cpp @@ -386,6 +386,7 @@ void Resource::_bind_methods() { ClassDB::bind_method(D_METHOD("is_local_to_scene"), &Resource::is_local_to_scene); ClassDB::bind_method(D_METHOD("get_local_scene"), &Resource::get_local_scene); ClassDB::bind_method(D_METHOD("setup_local_to_scene"), &Resource::setup_local_to_scene); + ClassDB::bind_method(D_METHOD("emit_changed"), &Resource::emit_changed); ClassDB::bind_method(D_METHOD("duplicate", "subresources"), &Resource::duplicate, DEFVAL(false)); ADD_SIGNAL(MethodInfo("changed")); diff --git a/core/math/basis.cpp b/core/math/basis.cpp index 26b4caba39..cbdd8a8c9f 100644 --- a/core/math/basis.cpp +++ b/core/math/basis.cpp @@ -790,8 +790,8 @@ Quat Basis::get_quat() const { temp[2] = ((m.elements[1][0] - m.elements[0][1]) * s); } else { int i = m.elements[0][0] < m.elements[1][1] ? - (m.elements[1][1] < m.elements[2][2] ? 2 : 1) : - (m.elements[0][0] < m.elements[2][2] ? 2 : 0); + (m.elements[1][1] < m.elements[2][2] ? 2 : 1) : + (m.elements[0][0] < m.elements[2][2] ? 2 : 0); int j = (i + 1) % 3; int k = (i + 2) % 3; diff --git a/core/math/geometry_2d.cpp b/core/math/geometry_2d.cpp index 5d4c31088b..783750b9e6 100644 --- a/core/math/geometry_2d.cpp +++ b/core/math/geometry_2d.cpp @@ -31,7 +31,7 @@ #include "geometry_2d.h" #include "thirdparty/misc/clipper.hpp" -#include "thirdparty/misc/triangulator.h" +#include "thirdparty/misc/polypartition.h" #define STB_RECT_PACK_IMPLEMENTATION #include "thirdparty/misc/stb_rect_pack.h" @@ -39,16 +39,16 @@ Vector<Vector<Vector2>> Geometry2D::decompose_polygon_in_convex(Vector<Point2> polygon) { Vector<Vector<Vector2>> decomp; - List<TriangulatorPoly> in_poly, out_poly; + List<TPPLPoly> in_poly, out_poly; - TriangulatorPoly inp; + TPPLPoly inp; inp.Init(polygon.size()); for (int i = 0; i < polygon.size(); i++) { inp.GetPoint(i) = polygon[i]; } - inp.SetOrientation(TRIANGULATOR_CCW); + inp.SetOrientation(TPPL_ORIENTATION_CCW); in_poly.push_back(inp); - TriangulatorPartition tpart; + TPPLPartition tpart; if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { // Failed. ERR_PRINT("Convex decomposing failed!"); return decomp; @@ -56,8 +56,8 @@ Vector<Vector<Vector2>> Geometry2D::decompose_polygon_in_convex(Vector<Point2> p decomp.resize(out_poly.size()); int idx = 0; - for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) { - TriangulatorPoly &tp = I->get(); + for (List<TPPLPoly>::Element *I = out_poly.front(); I; I = I->next()) { + TPPLPoly &tp = I->get(); decomp.write[idx].resize(tp.GetNumPoints()); diff --git a/core/math/geometry_3d.cpp b/core/math/geometry_3d.cpp index a918d1de0d..553184303d 100644 --- a/core/math/geometry_3d.cpp +++ b/core/math/geometry_3d.cpp @@ -33,7 +33,7 @@ #include "core/string/print_string.h" #include "thirdparty/misc/clipper.hpp" -#include "thirdparty/misc/triangulator.h" +#include "thirdparty/misc/polypartition.h" void Geometry3D::MeshData::optimize_vertices() { Map<int, int> vtx_remap; diff --git a/core/object/undo_redo.cpp b/core/object/undo_redo.cpp index c699820e75..3b1165b8f6 100644 --- a/core/object/undo_redo.cpp +++ b/core/object/undo_redo.cpp @@ -53,6 +53,23 @@ void UndoRedo::_discard_redo() { actions.resize(current_action + 1); } +bool UndoRedo::_redo(bool p_execute) { + ERR_FAIL_COND_V(action_level > 0, false); + + if ((current_action + 1) >= actions.size()) { + return false; //nothing to redo + } + + current_action++; + if (p_execute) { + _process_operation_list(actions.write[current_action].do_ops.front()); + } + version++; + emit_signal("version_changed"); + + return true; +} + void UndoRedo::create_action(const String &p_name, MergeMode p_mode) { uint32_t ticks = OS::get_singleton()->get_ticks_msec(); @@ -242,7 +259,7 @@ bool UndoRedo::is_committing_action() const { return committing > 0; } -void UndoRedo::commit_action() { +void UndoRedo::commit_action(bool p_execute) { ERR_FAIL_COND(action_level <= 0); action_level--; if (action_level > 0) { @@ -255,8 +272,9 @@ void UndoRedo::commit_action() { } committing++; - redo(); // perform action + _redo(p_execute); // perform action committing--; + if (callback && actions.size() > 0) { callback(callback_ud, actions[actions.size() - 1].name); } @@ -323,19 +341,7 @@ void UndoRedo::_process_operation_list(List<Operation>::Element *E) { } bool UndoRedo::redo() { - ERR_FAIL_COND_V(action_level > 0, false); - - if ((current_action + 1) >= actions.size()) { - return false; //nothing to redo - } - - current_action++; - - _process_operation_list(actions.write[current_action].do_ops.front()); - version++; - emit_signal("version_changed"); - - return true; + return _redo(true); } bool UndoRedo::undo() { @@ -351,6 +357,24 @@ bool UndoRedo::undo() { return true; } +int UndoRedo::get_history_count() { + ERR_FAIL_COND_V(action_level > 0, -1); + + return actions.size(); +} + +int UndoRedo::get_current_action() { + ERR_FAIL_COND_V(action_level > 0, -1); + + return current_action; +} + +String UndoRedo::get_action_name(int p_id) { + ERR_FAIL_INDEX_V(p_id, actions.size(), ""); + + return actions[p_id].name; +} + void UndoRedo::clear_history(bool p_increase_version) { ERR_FAIL_COND(action_level > 0); _discard_redo(); @@ -480,7 +504,7 @@ Variant UndoRedo::_add_undo_method(const Variant **p_args, int p_argcount, Calla void UndoRedo::_bind_methods() { ClassDB::bind_method(D_METHOD("create_action", "name", "merge_mode"), &UndoRedo::create_action, DEFVAL(MERGE_DISABLE)); - ClassDB::bind_method(D_METHOD("commit_action"), &UndoRedo::commit_action); + ClassDB::bind_method(D_METHOD("commit_action", "execute"), &UndoRedo::commit_action, DEFVAL(true)); ClassDB::bind_method(D_METHOD("is_committing_action"), &UndoRedo::is_committing_action); { @@ -505,8 +529,14 @@ void UndoRedo::_bind_methods() { ClassDB::bind_method(D_METHOD("add_undo_property", "object", "property", "value"), &UndoRedo::add_undo_property); ClassDB::bind_method(D_METHOD("add_do_reference", "object"), &UndoRedo::add_do_reference); ClassDB::bind_method(D_METHOD("add_undo_reference", "object"), &UndoRedo::add_undo_reference); + + ClassDB::bind_method(D_METHOD("get_history_count"), &UndoRedo::get_history_count); + ClassDB::bind_method(D_METHOD("get_current_action"), &UndoRedo::get_current_action); + ClassDB::bind_method(D_METHOD("get_action_name"), &UndoRedo::get_action_name); ClassDB::bind_method(D_METHOD("clear_history", "increase_version"), &UndoRedo::clear_history, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("get_current_action_name"), &UndoRedo::get_current_action_name); + ClassDB::bind_method(D_METHOD("has_undo"), &UndoRedo::has_undo); ClassDB::bind_method(D_METHOD("has_redo"), &UndoRedo::has_redo); ClassDB::bind_method(D_METHOD("get_version"), &UndoRedo::get_version); diff --git a/core/object/undo_redo.h b/core/object/undo_redo.h index 7b28b138c1..a08ca7792f 100644 --- a/core/object/undo_redo.h +++ b/core/object/undo_redo.h @@ -84,6 +84,7 @@ private: void _pop_history_tail(); void _process_operation_list(List<Operation>::Element *E); void _discard_redo(); + bool _redo(bool p_execute); CommitNotifyCallback callback = nullptr; void *callback_ud = nullptr; @@ -109,11 +110,15 @@ public: void add_undo_reference(Object *p_object); bool is_committing_action() const; - void commit_action(); + void commit_action(bool p_execute = true); bool redo(); bool undo(); String get_current_action_name() const; + + int get_history_count(); + int get_current_action(); + String get_action_name(int p_id); void clear_history(bool p_increase_version = true); bool has_undo(); diff --git a/core/os/os.h b/core/os/os.h index ed3c6ddc94..e02ce7d5ec 100644 --- a/core/os/os.h +++ b/core/os/os.h @@ -129,7 +129,8 @@ public: virtual int get_low_processor_usage_mode_sleep_usec() const; virtual String get_executable_path() const; - virtual Error execute(const String &p_path, const List<String> &p_arguments, bool p_blocking = true, ProcessID *r_child_id = nullptr, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) = 0; + virtual Error execute(const String &p_path, const List<String> &p_arguments, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) = 0; + virtual Error create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id = nullptr) = 0; virtual Error kill(const ProcessID &p_pid) = 0; virtual int get_process_id() const; virtual void vibrate_handheld(int p_duration_ms = 500); diff --git a/doc/classes/Animation.xml b/doc/classes/Animation.xml index d26c0e8605..9720405ffd 100644 --- a/doc/classes/Animation.xml +++ b/doc/classes/Animation.xml @@ -168,7 +168,7 @@ <argument index="2" name="stream" type="Resource"> </argument> <description> - Sets the stream of the key identified by [code]key_idx[/code] to value [code]offset[/code]. The [code]track_idx[/code] must be the index of an Audio Track. + Sets the stream of the key identified by [code]key_idx[/code] to value [code]stream[/code]. The [code]track_idx[/code] must be the index of an Audio Track. </description> </method> <method name="bezier_track_get_key_in_handle" qualifiers="const"> diff --git a/doc/classes/OS.xml b/doc/classes/OS.xml index 65a815a603..ed94f9d90f 100644 --- a/doc/classes/OS.xml +++ b/doc/classes/OS.xml @@ -25,6 +25,29 @@ [b]Note:[/b] This method is implemented on Linux, macOS and Windows. </description> </method> + <method name="create_process"> + <return type="int"> + </return> + <argument index="0" name="path" type="String"> + </argument> + <argument index="1" name="arguments" type="PackedStringArray"> + </argument> + <description> + Creates a new process that runs independently of Godot. It will not terminate if Godot terminates. The file specified in [code]path[/code] must exist and be executable. Platform path resolution will be used. The [code]arguments[/code] are used in the given order and separated by a space. + If the process creation succeeds, the method will return the new process ID, which you can use to monitor the process (and potentially terminate it with [method kill]). If the process creation fails, the method will return [code]-1[/code]. + For example, running another instance of the project: + [codeblocks] + [gdscript] + var pid = OS.create_process(OS.get_executable_path(), []) + [/gdscript] + [csharp] + var pid = OS.CreateProcess(OS.GetExecutablePath(), new string[] {}); + [/csharp] + [/codeblocks] + See [method execute] if you wish to run an external command and retrieve the results. + [b]Note:[/b] This method is implemented on Android, iOS, Linux, macOS and Windows. + </description> + </method> <method name="delay_msec" qualifiers="const"> <return type="void"> </return> @@ -71,48 +94,34 @@ </argument> <argument index="1" name="arguments" type="PackedStringArray"> </argument> - <argument index="2" name="blocking" type="bool" default="true"> - </argument> - <argument index="3" name="output" type="Array" default="[ ]"> + <argument index="2" name="output" type="Array" default="[ ]"> </argument> - <argument index="4" name="read_stderr" type="bool" default="false"> + <argument index="3" name="read_stderr" type="bool" default="false"> </argument> <description> - Execute the file at the given path with the arguments passed as an array of strings. Platform path resolution will take place. The resolved file must exist and be executable. - The arguments are used in the given order and separated by a space, so [code]OS.execute("ping", ["-w", "3", "godotengine.org"], false)[/code] will resolve to [code]ping -w 3 godotengine.org[/code] in the system's shell. - This method has slightly different behavior based on whether the [code]blocking[/code] mode is enabled. - If [code]blocking[/code] is [code]true[/code], the Godot thread will pause its execution while waiting for the process to terminate. The shell output of the process will be written to the [code]output[/code] array as a single string. When the process terminates, the Godot thread will resume execution. - If [code]blocking[/code] is [code]false[/code], the Godot thread will continue while the new process runs. It is not possible to retrieve the shell output in non-blocking mode, so [code]output[/code] will be empty. - The return value also depends on the blocking mode. When blocking, the method will return an exit code of the process. When non-blocking, the method returns a process ID, which you can use to monitor the process (and potentially terminate it with [method kill]). If the process forking (non-blocking) or opening (blocking) fails, the method will return [code]-1[/code] or another exit code. - Example of blocking mode and retrieving the shell output: + Executes a command. The file specified in [code]path[/code] must exist and be executable. Platform path resolution will be used. The [code]arguments[/code] are used in the given order and separated by a space. If an [code]output[/code] [Array] is provided, the complete shell output of the process will be appended as a single [String] element in [code]output[/code]. If [code]read_stderr[/code] is [code]true[/code], the output to the standard error stream will be included too. + If the command is successfully executed, the method will return the exit code of the command, or [code]-1[/code] if it fails. + [b]Note:[/b] The Godot thread will pause its execution until the executed command terminates. Use [Thread] to create a separate thread that will not pause the Godot thread, or use [method create_process] to create a completely independent process. + For example, to retrieve a list of the working directory's contents: [codeblocks] [gdscript] var output = [] - var exit_code = OS.execute("ls", ["-l", "/tmp"], true, output) + var exit_code = OS.execute("ls", ["-l", "/tmp"], output) [/gdscript] [csharp] var output = new Godot.Collections.Array(); - int exitCode = OS.Execute("ls", new string[] {"-l", "/tmp"}, true, output); - [/csharp] - [/codeblocks] - Example of non-blocking mode, running another instance of the project and storing its process ID: - [codeblocks] - [gdscript] - var pid = OS.execute(OS.get_executable_path(), [], false) - [/gdscript] - [csharp] - var pid = OS.Execute(OS.GetExecutablePath(), new string[] {}, false); + int exitCode = OS.Execute("ls", new string[] {"-l", "/tmp"}, output); [/csharp] [/codeblocks] - If you wish to access a shell built-in or perform a composite command, a platform-specific shell can be invoked. For example: + To execute a composite command, a platform-specific shell can be invoked. For example: [codeblocks] [gdscript] var output = [] - OS.execute("CMD.exe", ["/C", "cd %TEMP% && dir"], true, output) + OS.execute("CMD.exe", ["/C", "cd %TEMP% && dir"], output) [/gdscript] [csharp] var output = new Godot.Collections.Array(); - OS.Execute("CMD.exe", new string[] {"/C", "cd %TEMP% && dir"}, true, output); + OS.Execute("CMD.exe", new string[] {"/C", "cd %TEMP% && dir"}, output); [/csharp] [/codeblocks] [b]Note:[/b] This method is implemented on Android, iOS, Linux, macOS and Windows. diff --git a/doc/classes/PhysicsDirectSpaceState2D.xml b/doc/classes/PhysicsDirectSpaceState2D.xml index c26cf0514c..b6f95305ed 100644 --- a/doc/classes/PhysicsDirectSpaceState2D.xml +++ b/doc/classes/PhysicsDirectSpaceState2D.xml @@ -16,8 +16,9 @@ <argument index="0" name="shape" type="PhysicsShapeQueryParameters2D"> </argument> <description> - Checks how far the shape can travel toward a point. If the shape can not move, the array will be empty. - [b]Note:[/b] Both the shape and the motion are supplied through a [PhysicsShapeQueryParameters2D] object. The method will return an array with two floats between 0 and 1, both representing a fraction of [code]motion[/code]. The first is how far the shape can move without triggering a collision, and the second is the point at which a collision will occur. If no collision is detected, the returned array will be [code][1, 1][/code]. + Checks how far a [Shape2D] can move without colliding. All the parameters for the query, including the shape and the motion, are supplied through a [PhysicsShapeQueryParameters2D] object. + Returns an array with the safe and unsafe proportions (between 0 and 1) of the motion. The safe proportion is the maximum fraction of the motion that can be made without a collision. The unsafe proportion is the minimum fraction of the distance that must be moved for a collision. If no collision is detected a result of [code][1.0, 1.0][/code] will be returned. + [b]Note:[/b] Any [Shape2D]s that the shape is already colliding with e.g. inside of, will be ignored. Use [method collide_shape] to determine the [Shape2D]s that the shape is already colliding with. </description> </method> <method name="collide_shape"> diff --git a/doc/classes/PhysicsDirectSpaceState3D.xml b/doc/classes/PhysicsDirectSpaceState3D.xml index 789e8cc731..243d071c56 100644 --- a/doc/classes/PhysicsDirectSpaceState3D.xml +++ b/doc/classes/PhysicsDirectSpaceState3D.xml @@ -18,8 +18,9 @@ <argument index="1" name="motion" type="Vector3"> </argument> <description> - Checks whether the shape can travel to a point. The method will return an array with two floats between 0 and 1, both representing a fraction of [code]motion[/code]. The first is how far the shape can move without triggering a collision, and the second is the point at which a collision will occur. If no collision is detected, the returned array will be [code][1, 1][/code]. - If the shape can not move, the returned array will be [code][0, 0][/code] under Bullet, and empty under GodotPhysics3D. + Checks how far a [Shape3D] can move without colliding. All the parameters for the query, including the shape, are supplied through a [PhysicsShapeQueryParameters3D] object. + Returns an array with the safe and unsafe proportions (between 0 and 1) of the motion. The safe proportion is the maximum fraction of the motion that can be made without a collision. The unsafe proportion is the minimum fraction of the distance that must be moved for a collision. If no collision is detected a result of [code][1.0, 1.0][/code] will be returned. + [b]Note:[/b] Any [Shape3D]s that the shape is already colliding with e.g. inside of, will be ignored. Use [method collide_shape] to determine the [Shape3D]s that the shape is already colliding with. </description> </method> <method name="collide_shape"> diff --git a/doc/classes/Resource.xml b/doc/classes/Resource.xml index 0f4c170324..a9697c7fce 100644 --- a/doc/classes/Resource.xml +++ b/doc/classes/Resource.xml @@ -29,6 +29,19 @@ [b]Note:[/b] If [code]subresources[/code] is [code]true[/code], this method will only perform a shallow copy. Nested resources within subresources will not be duplicated and will still be shared. </description> </method> + <method name="emit_changed"> + <return type="void"> + </return> + <description> + Emits the [signal changed] signal. + If external objects which depend on this resource should be updated, this method must be called manually whenever the state of this resource has changed (such as modification of properties). + The method is equivalent to: + [codeblock] + emit_signal("changed") + [/codeblock] + [b]Note:[/b] This method is called automatically for built-in resources. + </description> + </method> <method name="get_local_scene" qualifiers="const"> <return type="Node"> </return> diff --git a/doc/classes/RichTextLabel.xml b/doc/classes/RichTextLabel.xml index 147e41bf1b..a182abc17b 100644 --- a/doc/classes/RichTextLabel.xml +++ b/doc/classes/RichTextLabel.xml @@ -455,6 +455,7 @@ </member> <member name="visible_characters" type="int" setter="set_visible_characters" getter="get_visible_characters" default="-1"> The restricted number of characters to display in the label. If [code]-1[/code], all characters will be displayed. + [b]Note:[/b] Setting this property updates [member percent_visible] based on current [method get_total_character_count]. </member> </members> <signals> diff --git a/doc/classes/UndoRedo.xml b/doc/classes/UndoRedo.xml index 2cc3e974e2..0e4a76a1a9 100644 --- a/doc/classes/UndoRedo.xml +++ b/doc/classes/UndoRedo.xml @@ -110,8 +110,10 @@ <method name="commit_action"> <return type="void"> </return> + <argument index="0" name="execute" type="bool" default="true"> + </argument> <description> - Commit the action. All "do" methods/properties are called/set when this function is called. + Commit the action. If [code]execute[/code] is true (default), all "do" methods/properties are called/set when this function is called. </description> </method> <method name="create_action"> @@ -126,11 +128,34 @@ The way actions are merged is dictated by the [code]merge_mode[/code] argument. See [enum MergeMode] for details. </description> </method> + <method name="get_action_name"> + <return type="String"> + </return> + <argument index="0" name="arg0" type="int"> + </argument> + <description> + Gets the action name from its index. + </description> + </method> + <method name="get_current_action"> + <return type="int"> + </return> + <description> + Gets the index of the current action. + </description> + </method> <method name="get_current_action_name" qualifiers="const"> <return type="String"> </return> <description> - Gets the name of the current action. + Gets the name of the current action, equivalent to [code]get_action_name(get_current_action())[/code]. + </description> + </method> + <method name="get_history_count"> + <return type="int"> + </return> + <description> + Return how many element are in the history. </description> </method> <method name="get_version" qualifiers="const"> diff --git a/drivers/unix/os_unix.cpp b/drivers/unix/os_unix.cpp index dfa7ba895d..d94c2126ef 100644 --- a/drivers/unix/os_unix.cpp +++ b/drivers/unix/os_unix.cpp @@ -257,31 +257,26 @@ uint64_t OS_Unix::get_ticks_usec() const { return longtime; } -Error OS_Unix::execute(const String &p_path, const List<String> &p_arguments, bool p_blocking, ProcessID *r_child_id, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { +Error OS_Unix::execute(const String &p_path, const List<String> &p_arguments, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { #ifdef __EMSCRIPTEN__ // Don't compile this code at all to avoid undefined references. // Actual virtual call goes to OS_JavaScript. ERR_FAIL_V(ERR_BUG); #else - if (p_blocking && r_pipe) { - String argss; - argss = "\"" + p_path + "\""; - + if (r_pipe) { + String command = "\"" + p_path + "\""; for (int i = 0; i < p_arguments.size(); i++) { - argss += String(" \"") + p_arguments[i] + "\""; + command += String(" \"") + p_arguments[i] + "\""; } - if (read_stderr) { - argss += " 2>&1"; // Read stderr too + command += " 2>&1"; // Include stderr } else { - argss += " 2>/dev/null"; //silence stderr + command += " 2>/dev/null"; // Silence stderr } - FILE *f = popen(argss.utf8().get_data(), "r"); - - ERR_FAIL_COND_V_MSG(!f, ERR_CANT_OPEN, "Cannot pipe stream from process running with following arguments '" + argss + "'."); + FILE *f = popen(command.utf8().get_data(), "r"); + ERR_FAIL_COND_V_MSG(!f, ERR_CANT_OPEN, "Cannot create pipe from command: " + command); char buf[65535]; - while (fgets(buf, 65535, f)) { if (p_pipe_mutex) { p_pipe_mutex->lock(); @@ -292,10 +287,10 @@ Error OS_Unix::execute(const String &p_path, const List<String> &p_arguments, bo } } int rv = pclose(f); + if (r_exitcode) { *r_exitcode = WEXITSTATUS(rv); } - return OK; } @@ -303,14 +298,7 @@ Error OS_Unix::execute(const String &p_path, const List<String> &p_arguments, bo ERR_FAIL_COND_V(pid < 0, ERR_CANT_FORK); if (pid == 0) { - // is child - - if (!p_blocking) { - // For non blocking calls, create a new session-ID so parent won't wait for it. - // This ensures the process won't go zombie at end. - setsid(); - } - + // The child process Vector<CharString> cs; cs.push_back(p_path.utf8()); for (int i = 0; i < p_arguments.size(); i++) { @@ -324,24 +312,56 @@ Error OS_Unix::execute(const String &p_path, const List<String> &p_arguments, bo args.push_back(0); execvp(p_path.utf8().get_data(), &args[0]); - // still alive? something failed.. - fprintf(stderr, "**ERROR** OS_Unix::execute - Could not create child process while executing: %s\n", p_path.utf8().get_data()); + // The execvp() function only returns if an error occurs. + ERR_PRINT("Could not create child process: " + p_path); raise(SIGKILL); } - if (p_blocking) { - int status; - waitpid(pid, &status, 0); - if (r_exitcode) { - *r_exitcode = WIFEXITED(status) ? WEXITSTATUS(status) : status; + int status; + waitpid(pid, &status, 0); + if (r_exitcode) { + *r_exitcode = WIFEXITED(status) ? WEXITSTATUS(status) : status; + } + return OK; +#endif +} + +Error OS_Unix::create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id) { +#ifdef __EMSCRIPTEN__ + // Don't compile this code at all to avoid undefined references. + // Actual virtual call goes to OS_JavaScript. + ERR_FAIL_V(ERR_BUG); +#else + pid_t pid = fork(); + ERR_FAIL_COND_V(pid < 0, ERR_CANT_FORK); + + if (pid == 0) { + // The new process + // Create a new session-ID so parent won't wait for it. + // This ensures the process won't go zombie at the end. + setsid(); + + Vector<CharString> cs; + cs.push_back(p_path.utf8()); + for (int i = 0; i < p_arguments.size(); i++) { + cs.push_back(p_arguments[i].utf8()); } - } else { - if (r_child_id) { - *r_child_id = pid; + Vector<char *> args; + for (int i = 0; i < cs.size(); i++) { + args.push_back((char *)cs[i].get_data()); } + args.push_back(0); + + execvp(p_path.utf8().get_data(), &args[0]); + // The execvp() function only returns if an error occurs. + ERR_PRINT("Could not create child process: " + p_path); + raise(SIGKILL); } + if (r_child_id) { + *r_child_id = pid; + } return OK; #endif } diff --git a/drivers/unix/os_unix.h b/drivers/unix/os_unix.h index 7d1f1c82c2..6c79d984e9 100644 --- a/drivers/unix/os_unix.h +++ b/drivers/unix/os_unix.h @@ -82,7 +82,8 @@ public: virtual void delay_usec(uint32_t p_usec) const override; virtual uint64_t get_ticks_usec() const override; - virtual Error execute(const String &p_path, const List<String> &p_arguments, bool p_blocking = true, ProcessID *r_child_id = nullptr, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) override; + virtual Error execute(const String &p_path, const List<String> &p_arguments, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) override; + virtual Error create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id = nullptr) override; virtual Error kill(const ProcessID &p_pid) override; virtual int get_process_id() const override; diff --git a/editor/editor_file_system.cpp b/editor/editor_file_system.cpp index 208f678947..76814ea378 100644 --- a/editor/editor_file_system.cpp +++ b/editor/editor_file_system.cpp @@ -1477,20 +1477,21 @@ void EditorFileSystem::update_file(const String &p_file) { String type = ResourceLoader::get_resource_type(p_file); if (cpos == -1) { - //the file did not exist, it was added + // The file did not exist, it was added. - late_added_files.insert(p_file); //remember that it was added. This mean it will be scanned and imported on editor restart + late_added_files.insert(p_file); // Remember that it was added. This mean it will be scanned and imported on editor restart. int idx = 0; + String file_name = p_file.get_file(); for (int i = 0; i < fs->files.size(); i++) { - if (p_file < fs->files[i]->file) { + if (file_name < fs->files[i]->file) { break; } idx++; } EditorFileSystemDirectory::FileInfo *fi = memnew(EditorFileSystemDirectory::FileInfo); - fi->file = p_file.get_file(); + fi->file = file_name; fi->import_modified_time = 0; fi->import_valid = ResourceLoader::is_import_valid(p_file); diff --git a/editor/editor_node.cpp b/editor/editor_node.cpp index 6f03518029..b41bf81161 100644 --- a/editor/editor_node.cpp +++ b/editor/editor_node.cpp @@ -2855,8 +2855,7 @@ void EditorNode::_discard_changes(const String &p_str) { args.push_back(exec.get_base_dir()); args.push_back("--project-manager"); - OS::ProcessID pid = 0; - Error err = OS::get_singleton()->execute(exec, args, false, &pid); + Error err = OS::get_singleton()->create_process(exec, args); ERR_FAIL_COND(err); } break; } @@ -4703,8 +4702,8 @@ void EditorNode::_scene_tab_closed(int p_tab, int option) { } bool unsaved = (p_tab == editor_data.get_edited_scene()) ? - saved_version != editor_data.get_undo_redo().get_version() : - editor_data.get_scene_version(p_tab) != 0; + saved_version != editor_data.get_undo_redo().get_version() : + editor_data.get_scene_version(p_tab) != 0; if (unsaved) { save_confirmation->get_ok_button()->set_text(TTR("Save & Close")); save_confirmation->set_text(vformat(TTR("Save changes to '%s' before closing?"), scene->get_filename() != "" ? scene->get_filename() : "unsaved scene")); @@ -5139,9 +5138,7 @@ void EditorNode::_global_menu_new_window(const Variant &p_tag) { List<String> args; args.push_back("-p"); String exec = OS::get_singleton()->get_executable_path(); - - OS::ProcessID pid = 0; - OS::get_singleton()->execute(exec, args, false, &pid); + OS::get_singleton()->create_process(exec, args); } } @@ -5467,7 +5464,7 @@ void EditorNode::_print_handler(void *p_this, const String &p_string, bool p_err static void _execute_thread(void *p_ud) { EditorNode::ExecuteThreadArgs *eta = (EditorNode::ExecuteThreadArgs *)p_ud; - Error err = OS::get_singleton()->execute(eta->path, eta->args, true, nullptr, &eta->output, &eta->exitcode, true, &eta->execute_output_mutex); + Error err = OS::get_singleton()->execute(eta->path, eta->args, &eta->output, &eta->exitcode, true, &eta->execute_output_mutex); print_verbose("Thread exit status: " + itos(eta->exitcode)); if (err != OK) { eta->exitcode = err; diff --git a/editor/editor_run.cpp b/editor/editor_run.cpp index 6fae56074d..e46f4eb65a 100644 --- a/editor/editor_run.cpp +++ b/editor/editor_run.cpp @@ -201,7 +201,7 @@ Error EditorRun::run(const String &p_scene, const String &p_custom_args, const L int instances = EditorSettings::get_singleton()->get_project_metadata("debug_options", "run_debug_instances", 1); for (int i = 0; i < instances; i++) { OS::ProcessID pid = 0; - Error err = OS::get_singleton()->execute(exec, args, false, &pid); + Error err = OS::get_singleton()->create_process(exec, args, &pid); ERR_FAIL_COND_V(err, err); pids.push_back(pid); } diff --git a/editor/plugins/canvas_item_editor_plugin.cpp b/editor/plugins/canvas_item_editor_plugin.cpp index 498f9d5c19..49af478307 100644 --- a/editor/plugins/canvas_item_editor_plugin.cpp +++ b/editor/plugins/canvas_item_editor_plugin.cpp @@ -3149,16 +3149,16 @@ void CanvasItemEditor::_draw_ruler_tool() { float arc_1_start_angle = end_to_begin.x < 0 ? - (end_to_begin.y < 0 ? 3.0 * Math_PI / 2.0 - vertical_angle_rad : Math_PI / 2.0) : - (end_to_begin.y < 0 ? 3.0 * Math_PI / 2.0 : Math_PI / 2.0 - vertical_angle_rad); + (end_to_begin.y < 0 ? 3.0 * Math_PI / 2.0 - vertical_angle_rad : Math_PI / 2.0) : + (end_to_begin.y < 0 ? 3.0 * Math_PI / 2.0 : Math_PI / 2.0 - vertical_angle_rad); float arc_1_end_angle = arc_1_start_angle + vertical_angle_rad; // Constrain arc to triangle height & max size float arc_1_radius = MIN(MIN(arc_radius_max_length_percent * ruler_length, ABS(end_to_begin.y)), arc_max_radius); float arc_2_start_angle = end_to_begin.x < 0 ? - (end_to_begin.y < 0 ? 0.0 : -horizontal_angle_rad) : - (end_to_begin.y < 0 ? Math_PI - horizontal_angle_rad : Math_PI); + (end_to_begin.y < 0 ? 0.0 : -horizontal_angle_rad) : + (end_to_begin.y < 0 ? Math_PI - horizontal_angle_rad : Math_PI); float arc_2_end_angle = arc_2_start_angle + horizontal_angle_rad; // Constrain arc to triangle width & max size float arc_2_radius = MIN(MIN(arc_radius_max_length_percent * ruler_length, ABS(end_to_begin.x)), arc_max_radius); diff --git a/editor/plugins/curve_editor_plugin.cpp b/editor/plugins/curve_editor_plugin.cpp index 88e56ccfb9..bff5cb8d2a 100644 --- a/editor/plugins/curve_editor_plugin.cpp +++ b/editor/plugins/curve_editor_plugin.cpp @@ -353,8 +353,8 @@ void CurveEditor::open_context_menu(Vector2 pos) { _context_menu->add_check_item(TTR("Linear"), CONTEXT_LINEAR); bool is_linear = _selected_tangent == TANGENT_LEFT ? - _curve_ref->get_point_left_mode(_selected_point) == Curve::TANGENT_LINEAR : - _curve_ref->get_point_right_mode(_selected_point) == Curve::TANGENT_LINEAR; + _curve_ref->get_point_left_mode(_selected_point) == Curve::TANGENT_LINEAR : + _curve_ref->get_point_right_mode(_selected_point) == Curve::TANGENT_LINEAR; _context_menu->set_item_checked(_context_menu->get_item_index(CONTEXT_LINEAR), is_linear); diff --git a/editor/plugins/script_editor_plugin.cpp b/editor/plugins/script_editor_plugin.cpp index 1af790c48d..216c0c3bef 100644 --- a/editor/plugins/script_editor_plugin.cpp +++ b/editor/plugins/script_editor_plugin.cpp @@ -1954,7 +1954,20 @@ void ScriptEditor::_update_script_names() { Vector<String> disambiguated_script_names; Vector<String> full_script_paths; for (int j = 0; j < sedata.size(); j++) { - disambiguated_script_names.append(sedata[j].name.replace("(*)", "").get_file()); + String name = sedata[j].name.replace("(*)", ""); + ScriptListName script_display = (ScriptListName)(int)EditorSettings::get_singleton()->get("text_editor/script_list/list_script_names_as"); + switch (script_display) { + case DISPLAY_NAME: { + name = name.get_file(); + } break; + case DISPLAY_DIR_AND_NAME: { + name = name.get_base_dir().get_file().plus_file(name.get_file()); + } break; + default: + break; + } + + disambiguated_script_names.append(name); full_script_paths.append(sedata[j].tooltip); } @@ -2198,7 +2211,7 @@ bool ScriptEditor::edit(const RES &p_resource, int p_line, int p_col, bool p_gra args.push_back(script_path); } - Error err = OS::get_singleton()->execute(path, args, false); + Error err = OS::get_singleton()->create_process(path, args); if (err == OK) { return false; } diff --git a/editor/project_manager.cpp b/editor/project_manager.cpp index dacd0162ba..1007a6c689 100644 --- a/editor/project_manager.cpp +++ b/editor/project_manager.cpp @@ -1297,9 +1297,7 @@ void ProjectList::_global_menu_new_window(const Variant &p_tag) { List<String> args; args.push_back("-p"); String exec = OS::get_singleton()->get_executable_path(); - - OS::ProcessID pid = 0; - OS::get_singleton()->execute(exec, args, false, &pid); + OS::get_singleton()->create_process(exec, args); } void ProjectList::_global_menu_open_project(const Variant &p_tag) { @@ -1310,9 +1308,7 @@ void ProjectList::_global_menu_open_project(const Variant &p_tag) { List<String> args; args.push_back(conf); String exec = OS::get_singleton()->get_executable_path(); - - OS::ProcessID pid = 0; - OS::get_singleton()->execute(exec, args, false, &pid); + OS::get_singleton()->create_process(exec, args); } } @@ -2055,9 +2051,7 @@ void ProjectManager::_open_selected_projects() { } String exec = OS::get_singleton()->get_executable_path(); - - OS::ProcessID pid = 0; - Error err = OS::get_singleton()->execute(exec, args, false, &pid); + Error err = OS::get_singleton()->create_process(exec, args); ERR_FAIL_COND(err); } @@ -2143,9 +2137,7 @@ void ProjectManager::_run_project_confirm() { } String exec = OS::get_singleton()->get_executable_path(); - - OS::ProcessID pid = 0; - Error err = OS::get_singleton()->execute(exec, args, false, &pid); + Error err = OS::get_singleton()->create_process(exec, args); ERR_FAIL_COND(err); } } @@ -2270,8 +2262,7 @@ void ProjectManager::_language_selected(int p_id) { void ProjectManager::_restart_confirm() { List<String> args = OS::get_singleton()->get_cmdline_args(); String exec = OS::get_singleton()->get_executable_path(); - OS::ProcessID pid = 0; - Error err = OS::get_singleton()->execute(exec, args, false, &pid); + Error err = OS::get_singleton()->create_process(exec, args); ERR_FAIL_COND(err); _dim_window(); diff --git a/main/main.cpp b/main/main.cpp index 25c559dac1..58782fa9c1 100644 --- a/main/main.cpp +++ b/main/main.cpp @@ -2686,8 +2686,7 @@ void Main::cleanup() { //attempt to restart with arguments String exec = OS::get_singleton()->get_executable_path(); List<String> args = OS::get_singleton()->get_restart_on_exit_arguments(); - OS::ProcessID pid = 0; - OS::get_singleton()->execute(exec, args, false, &pid); + OS::get_singleton()->create_process(exec, args); OS::get_singleton()->set_restart_on_exit(false, List<String>()); //clear list (uses memory) } diff --git a/modules/bullet/rigid_body_bullet.cpp b/modules/bullet/rigid_body_bullet.cpp index 7a53f91b33..4763098584 100644 --- a/modules/bullet/rigid_body_bullet.cpp +++ b/modules/bullet/rigid_body_bullet.cpp @@ -322,7 +322,8 @@ void RigidBodyBullet::set_space(SpaceBullet *p_space) { if (space) { can_integrate_forces = false; isScratchedSpaceOverrideModificator = false; - + // Remove any constraints + space->remove_rigid_body_constraints(this); // Remove this object form the physics world space->remove_rigid_body(this); } diff --git a/modules/bullet/space_bullet.cpp b/modules/bullet/space_bullet.cpp index a8d55b59b3..d7dd11d2a5 100644 --- a/modules/bullet/space_bullet.cpp +++ b/modules/bullet/space_bullet.cpp @@ -177,8 +177,10 @@ bool BulletPhysicsDirectSpaceState::cast_motion(const RID &p_shape, const Transf bt_xform_to.getOrigin() += bt_motion; if ((bt_xform_to.getOrigin() - bt_xform_from.getOrigin()).fuzzyZero()) { + r_closest_safe = 1.0f; + r_closest_unsafe = 1.0f; bulletdelete(btShape); - return false; + return true; } GodotClosestConvexResultCallback btResult(bt_xform_from.getOrigin(), bt_xform_to.getOrigin(), &p_exclude, p_collide_with_bodies, p_collide_with_areas); @@ -477,7 +479,7 @@ void SpaceBullet::add_rigid_body(RigidBodyBullet *p_body) { } } -void SpaceBullet::remove_rigid_body(RigidBodyBullet *p_body) { +void SpaceBullet::remove_rigid_body_constraints(RigidBodyBullet *p_body) { btRigidBody *btBody = p_body->get_bt_rigid_body(); int constraints = btBody->getNumConstraintRefs(); @@ -487,6 +489,10 @@ void SpaceBullet::remove_rigid_body(RigidBodyBullet *p_body) { dynamicsWorld->removeConstraint(btBody->getConstraintRef(i)); } } +} + +void SpaceBullet::remove_rigid_body(RigidBodyBullet *p_body) { + btRigidBody *btBody = p_body->get_bt_rigid_body(); if (p_body->is_static()) { dynamicsWorld->removeCollisionObject(btBody); diff --git a/modules/bullet/space_bullet.h b/modules/bullet/space_bullet.h index 42f982d5f0..0f2482e551 100644 --- a/modules/bullet/space_bullet.h +++ b/modules/bullet/space_bullet.h @@ -151,6 +151,7 @@ public: void reload_collision_filters(AreaBullet *p_area); void add_rigid_body(RigidBodyBullet *p_body); + void remove_rigid_body_constraints(RigidBodyBullet *p_body); void remove_rigid_body(RigidBodyBullet *p_body); void reload_collision_filters(RigidBodyBullet *p_body); diff --git a/modules/fbx/data/fbx_mesh_data.cpp b/modules/fbx/data/fbx_mesh_data.cpp index 963a815896..883651943e 100644 --- a/modules/fbx/data/fbx_mesh_data.cpp +++ b/modules/fbx/data/fbx_mesh_data.cpp @@ -34,7 +34,7 @@ #include "scene/resources/mesh.h" #include "scene/resources/surface_tool.h" -#include "thirdparty/misc/triangulator.h" +#include "thirdparty/misc/polypartition.h" template <class T> T collect_first(const Vector<VertexData<T>> *p_data, T p_fall_back) { @@ -930,30 +930,30 @@ void FBXMeshData::triangulate_polygon(Ref<SurfaceTool> st, Vector<int> p_polygon } } - TriangulatorPoly triangulator_poly; - triangulator_poly.Init(polygon_vertex_count); + TPPLPoly tppl_poly; + tppl_poly.Init(polygon_vertex_count); std::vector<Vector2> projected_vertices(polygon_vertex_count); for (int i = 0; i < polygon_vertex_count; i += 1) { const Vector2 pv(poly_vertices[i][axis_1_coord], poly_vertices[i][axis_2_coord]); projected_vertices[i] = pv; - triangulator_poly.GetPoint(i) = pv; + tppl_poly.GetPoint(i) = pv; } - triangulator_poly.SetOrientation(TRIANGULATOR_CCW); + tppl_poly.SetOrientation(TPPL_ORIENTATION_CCW); - List<TriangulatorPoly> out_poly; + List<TPPLPoly> out_poly; - TriangulatorPartition triangulator_partition; - if (triangulator_partition.Triangulate_OPT(&triangulator_poly, &out_poly) == 0) { // Good result. - if (triangulator_partition.Triangulate_EC(&triangulator_poly, &out_poly) == 0) { // Medium result. - if (triangulator_partition.Triangulate_MONO(&triangulator_poly, &out_poly) == 0) { // Really poor result. + TPPLPartition tppl_partition; + if (tppl_partition.Triangulate_OPT(&tppl_poly, &out_poly) == 0) { // Good result. + if (tppl_partition.Triangulate_EC(&tppl_poly, &out_poly) == 0) { // Medium result. + if (tppl_partition.Triangulate_MONO(&tppl_poly, &out_poly) == 0) { // Really poor result. ERR_FAIL_MSG("The triangulation of this polygon failed, please try to triangulate your mesh or check if it has broken polygons."); } } } std::vector<Vector2> tris(out_poly.size()); - for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) { - TriangulatorPoly &tp = I->get(); + for (List<TPPLPoly>::Element *I = out_poly.front(); I; I = I->next()) { + TPPLPoly &tp = I->get(); ERR_FAIL_COND_MSG(tp.GetNumPoints() != 3, "The triangulator retuned more points, how this is possible?"); // Find Index diff --git a/modules/gltf/gltf_document.cpp b/modules/gltf/gltf_document.cpp index 580bc006f5..ebf30b13f2 100644 --- a/modules/gltf/gltf_document.cpp +++ b/modules/gltf/gltf_document.cpp @@ -805,7 +805,9 @@ Error GLTFDocument::_encode_buffer_views(Ref<GLTFState> state) { } Error GLTFDocument::_parse_buffer_views(Ref<GLTFState> state) { - ERR_FAIL_COND_V(!state->json.has("bufferViews"), ERR_FILE_CORRUPT); + if (!state->json.has("bufferViews")) { + return OK; + } const Array &buffers = state->json["bufferViews"]; for (GLTFBufferViewIndex i = 0; i < buffers.size(); i++) { const Dictionary &d = buffers[i]; @@ -942,7 +944,9 @@ GLTFDocument::GLTFType GLTFDocument::_get_type_from_str(const String &p_string) } Error GLTFDocument::_parse_accessors(Ref<GLTFState> state) { - ERR_FAIL_COND_V(!state->json.has("accessors"), ERR_FILE_CORRUPT); + if (!state->json.has("accessors")) { + return OK; + } const Array &accessors = state->json["accessors"]; for (GLTFAccessorIndex i = 0; i < accessors.size(); i++) { const Dictionary &d = accessors[i]; diff --git a/modules/mono/csharp_script.cpp b/modules/mono/csharp_script.cpp index da4ece8c5c..18fe44108f 100644 --- a/modules/mono/csharp_script.cpp +++ b/modules/mono/csharp_script.cpp @@ -3584,9 +3584,9 @@ Error CSharpScript::load_source_code(const String &p_path) { ERR_FAIL_COND_V_MSG(ferr != OK, ferr, ferr == ERR_INVALID_DATA ? - "Script '" + p_path + "' contains invalid unicode (UTF-8), so it was not loaded." + "Script '" + p_path + "' contains invalid unicode (UTF-8), so it was not loaded." " Please ensure that scripts are saved in valid UTF-8 unicode." : - "Failed to read file: '" + p_path + "'."); + "Failed to read file: '" + p_path + "'."); #ifdef TOOLS_ENABLED source_changed_cache = true; diff --git a/modules/mono/editor/GodotTools/GodotTools/Build/MsBuildFinder.cs b/modules/mono/editor/GodotTools/GodotTools/Build/MsBuildFinder.cs index e2feb66e35..5ef55fea49 100644 --- a/modules/mono/editor/GodotTools/GodotTools/Build/MsBuildFinder.cs +++ b/modules/mono/editor/GodotTools/GodotTools/Build/MsBuildFinder.cs @@ -181,7 +181,7 @@ namespace GodotTools.Build var outputArray = new Godot.Collections.Array<string>(); int exitCode = Godot.OS.Execute(vsWherePath, vsWhereArgs, - blocking: true, output: (Godot.Collections.Array)outputArray); + output: (Godot.Collections.Array)outputArray); if (exitCode != 0) return string.Empty; diff --git a/modules/mono/editor/GodotTools/GodotTools/Export/XcodeHelper.cs b/modules/mono/editor/GodotTools/GodotTools/Export/XcodeHelper.cs index 219b7a698a..93ef837a83 100755 --- a/modules/mono/editor/GodotTools/GodotTools/Export/XcodeHelper.cs +++ b/modules/mono/editor/GodotTools/GodotTools/Export/XcodeHelper.cs @@ -27,7 +27,7 @@ namespace GodotTools.Export { var outputWrapper = new Godot.Collections.Array(); - int exitCode = Godot.OS.Execute("xcode-select", new string[] { "--print-path" }, blocking: true, output: outputWrapper); + int exitCode = Godot.OS.Execute("xcode-select", new string[] { "--print-path" }, output: outputWrapper); if (exitCode == 0) { diff --git a/modules/mono/editor/bindings_generator.cpp b/modules/mono/editor/bindings_generator.cpp index 59ce617990..38e403b2e1 100644 --- a/modules/mono/editor/bindings_generator.cpp +++ b/modules/mono/editor/bindings_generator.cpp @@ -365,7 +365,7 @@ String BindingsGenerator::bbcode_to_xml(const String &p_bbcode, const TypeInterf xml_output.append("</c>"); } else if (link_tag == "enum") { StringName search_cname = !target_itype ? target_cname : - StringName(target_itype->name + "." + (String)target_cname); + StringName(target_itype->name + "." + (String)target_cname); const Map<StringName, TypeInterface>::Element *enum_match = enum_types.find(search_cname); diff --git a/modules/mono/editor/script_class_parser.cpp b/modules/mono/editor/script_class_parser.cpp index 8f9a31a5b9..e81cbe4ebd 100644 --- a/modules/mono/editor/script_class_parser.cpp +++ b/modules/mono/editor/script_class_parser.cpp @@ -735,9 +735,9 @@ Error ScriptClassParser::parse_file(const String &p_filepath) { ERR_FAIL_COND_V_MSG(ferr != OK, ferr, ferr == ERR_INVALID_DATA ? - "File '" + p_filepath + "' contains invalid unicode (UTF-8), so it was not loaded." + "File '" + p_filepath + "' contains invalid unicode (UTF-8), so it was not loaded." " Please ensure that scripts are saved in valid UTF-8 unicode." : - "Failed to read file: '" + p_filepath + "'."); + "Failed to read file: '" + p_filepath + "'."); run_dummy_preprocessor(source, p_filepath); diff --git a/modules/mono/mono_gd/gd_mono.cpp b/modules/mono/mono_gd/gd_mono.cpp index 875d20ebe4..43a39a4966 100644 --- a/modules/mono/mono_gd/gd_mono.cpp +++ b/modules/mono/mono_gd/gd_mono.cpp @@ -593,8 +593,8 @@ ApiAssemblyInfo::Version ApiAssemblyInfo::Version::get_from_loaded_assembly(GDMo ApiAssemblyInfo::Version api_assembly_version; const char *nativecalls_name = p_api_type == ApiAssemblyInfo::API_CORE ? - BINDINGS_CLASS_NATIVECALLS : - BINDINGS_CLASS_NATIVECALLS_EDITOR; + BINDINGS_CLASS_NATIVECALLS : + BINDINGS_CLASS_NATIVECALLS_EDITOR; GDMonoClass *nativecalls_klass = p_api_assembly->get_class(BINDINGS_NAMESPACE, nativecalls_name); @@ -757,11 +757,11 @@ String GDMono::update_api_assemblies_from_prebuilt(const String &p_config, const #define FAIL_REASON(m_out_of_sync, m_prebuilt_exists) \ ( \ (m_out_of_sync ? \ - String("The assembly is invalidated ") : \ - String("The assembly was not found ")) + \ + String("The assembly is invalidated ") : \ + String("The assembly was not found ")) + \ (m_prebuilt_exists ? \ - String("and the prebuilt assemblies are missing.") : \ - String("and we failed to copy the prebuilt assemblies."))) + String("and the prebuilt assemblies are missing.") : \ + String("and we failed to copy the prebuilt assemblies."))) String dst_assemblies_dir = GodotSharpDirs::get_res_assemblies_base_dir().plus_file(p_config); @@ -820,8 +820,8 @@ bool GDMono::_load_core_api_assembly(LoadedApiAssembly &r_loaded_api_assembly, c // If running the project manager, load it from the prebuilt API directory String assembly_dir = !Main::is_project_manager() ? - GodotSharpDirs::get_res_assemblies_base_dir().plus_file(p_config) : - GodotSharpDirs::get_data_editor_prebuilt_api_dir().plus_file(p_config); + GodotSharpDirs::get_res_assemblies_base_dir().plus_file(p_config) : + GodotSharpDirs::get_data_editor_prebuilt_api_dir().plus_file(p_config); String assembly_path = assembly_dir.plus_file(CORE_API_ASSEMBLY_NAME ".dll"); @@ -853,8 +853,8 @@ bool GDMono::_load_editor_api_assembly(LoadedApiAssembly &r_loaded_api_assembly, // If running the project manager, load it from the prebuilt API directory String assembly_dir = !Main::is_project_manager() ? - GodotSharpDirs::get_res_assemblies_base_dir().plus_file(p_config) : - GodotSharpDirs::get_data_editor_prebuilt_api_dir().plus_file(p_config); + GodotSharpDirs::get_res_assemblies_base_dir().plus_file(p_config) : + GodotSharpDirs::get_data_editor_prebuilt_api_dir().plus_file(p_config); String assembly_path = assembly_dir.plus_file(EDITOR_API_ASSEMBLY_NAME ".dll"); diff --git a/modules/mono/mono_gd/gd_mono_marshal.cpp b/modules/mono/mono_gd/gd_mono_marshal.cpp index 57fbf5b7e1..286858bff1 100644 --- a/modules/mono/mono_gd/gd_mono_marshal.cpp +++ b/modules/mono/mono_gd/gd_mono_marshal.cpp @@ -1677,8 +1677,8 @@ Callable managed_to_callable(const M_Callable &p_managed_callable) { return Callable(managed_callable); } else { Object *target = p_managed_callable.target ? - unbox<Object *>(CACHED_FIELD(GodotObject, ptr)->get_value(p_managed_callable.target)) : - nullptr; + unbox<Object *>(CACHED_FIELD(GodotObject, ptr)->get_value(p_managed_callable.target)) : + nullptr; StringName *method_ptr = unbox<StringName *>(CACHED_FIELD(StringName, ptr)->get_value(p_managed_callable.method_string_name)); StringName method = method_ptr ? *method_ptr : StringName(); return Callable(target, method); @@ -1723,8 +1723,8 @@ M_Callable callable_to_managed(const Callable &p_callable) { Signal managed_to_signal_info(const M_SignalInfo &p_managed_signal) { Object *owner = p_managed_signal.owner ? - unbox<Object *>(CACHED_FIELD(GodotObject, ptr)->get_value(p_managed_signal.owner)) : - nullptr; + unbox<Object *>(CACHED_FIELD(GodotObject, ptr)->get_value(p_managed_signal.owner)) : + nullptr; StringName *name_ptr = unbox<StringName *>(CACHED_FIELD(StringName, ptr)->get_value(p_managed_signal.name_string_name)); StringName name = name_ptr ? *name_ptr : StringName(); return Signal(owner, name); diff --git a/modules/mono/utils/mono_reg_utils.cpp b/modules/mono/utils/mono_reg_utils.cpp index 27c2b2c5c1..bb1265e959 100644 --- a/modules/mono/utils/mono_reg_utils.cpp +++ b/modules/mono/utils/mono_reg_utils.cpp @@ -173,7 +173,7 @@ String find_msbuild_tools_path() { String output; int exit_code; - OS::get_singleton()->execute(vswhere_path, vswhere_args, true, nullptr, &output, &exit_code); + OS::get_singleton()->execute(vswhere_path, vswhere_args, &output, &exit_code); if (exit_code == 0) { Vector<String> lines = output.split("\n"); diff --git a/platform/android/export/export.cpp b/platform/android/export/export.cpp index 08ee410a96..cdcc39c6e7 100644 --- a/platform/android/export/export.cpp +++ b/platform/android/export/export.cpp @@ -308,7 +308,7 @@ class EditorExportPlatformAndroid : public EditorExportPlatform { List<String> args; args.push_back("devices"); int ec; - OS::get_singleton()->execute(adb, args, true, nullptr, &devices, &ec); + OS::get_singleton()->execute(adb, args, &devices, &ec); Vector<String> ds = devices.split("\n"); Vector<String> ldevices; @@ -361,7 +361,7 @@ class EditorExportPlatformAndroid : public EditorExportPlatform { int ec2; String dp; - OS::get_singleton()->execute(adb, args, true, nullptr, &dp, &ec2); + OS::get_singleton()->execute(adb, args, &dp, &ec2); Vector<String> props = dp.split("\n"); String vendor; @@ -432,7 +432,7 @@ class EditorExportPlatformAndroid : public EditorExportPlatform { List<String> args; args.push_back("kill-server"); - OS::get_singleton()->execute(adb, args, true); + OS::get_singleton()->execute(adb, args); }; } @@ -1800,7 +1800,7 @@ public: args.push_back("uninstall"); args.push_back(get_package_name(package_name)); - err = OS::get_singleton()->execute(adb, args, true, nullptr, nullptr, &rv); + err = OS::get_singleton()->execute(adb, args, nullptr, &rv); } print_line("Installing to device (please wait...): " + devices[p_device].name); @@ -1815,7 +1815,7 @@ public: args.push_back("-r"); args.push_back(tmp_export_path); - err = OS::get_singleton()->execute(adb, args, true, nullptr, nullptr, &rv); + err = OS::get_singleton()->execute(adb, args, nullptr, &rv); if (err || rv != 0) { EditorNode::add_io_error("Could not install to device."); CLEANUP_AND_RETURN(ERR_CANT_CREATE); @@ -1832,7 +1832,7 @@ public: args.push_back(devices[p_device].id); args.push_back("reverse"); args.push_back("--remove-all"); - OS::get_singleton()->execute(adb, args, true, nullptr, nullptr, &rv); + OS::get_singleton()->execute(adb, args, nullptr, &rv); if (p_debug_flags & DEBUG_FLAG_REMOTE_DEBUG) { int dbg_port = EditorSettings::get_singleton()->get("network/debug/remote_port"); @@ -1843,7 +1843,7 @@ public: args.push_back("tcp:" + itos(dbg_port)); args.push_back("tcp:" + itos(dbg_port)); - OS::get_singleton()->execute(adb, args, true, nullptr, nullptr, &rv); + OS::get_singleton()->execute(adb, args, nullptr, &rv); print_line("Reverse result: " + itos(rv)); } @@ -1857,7 +1857,7 @@ public: args.push_back("tcp:" + itos(fs_port)); args.push_back("tcp:" + itos(fs_port)); - err = OS::get_singleton()->execute(adb, args, true, nullptr, nullptr, &rv); + err = OS::get_singleton()->execute(adb, args, nullptr, &rv); print_line("Reverse result2: " + itos(rv)); } } else { @@ -1885,7 +1885,7 @@ public: args.push_back("-n"); args.push_back(get_package_name(package_name) + "/com.godot.game.GodotApp"); - err = OS::get_singleton()->execute(adb, args, true, nullptr, nullptr, &rv); + err = OS::get_singleton()->execute(adb, args, nullptr, &rv); if (err || rv != 0) { EditorNode::add_io_error("Could not execute on device."); CLEANUP_AND_RETURN(ERR_CANT_CREATE); @@ -2288,7 +2288,7 @@ public: args.push_back(user); args.push_back(export_path); int retval; - OS::get_singleton()->execute(apksigner, args, true, NULL, NULL, &retval); + OS::get_singleton()->execute(apksigner, args, nullptr, &retval); if (retval) { EditorNode::add_io_error("'apksigner' returned with error #" + itos(retval)); return ERR_CANT_CREATE; @@ -2303,7 +2303,7 @@ public: args.push_back("--verbose"); args.push_back(export_path); - OS::get_singleton()->execute(apksigner, args, true, NULL, NULL, &retval); + OS::get_singleton()->execute(apksigner, args, nullptr, &retval); if (retval) { EditorNode::add_io_error("'apksigner' verification of " + export_label + " failed."); return ERR_CANT_CREATE; diff --git a/platform/android/java/lib/src/org/godotengine/godot/GodotGLRenderView.java b/platform/android/java/lib/src/org/godotengine/godot/GodotGLRenderView.java index b536733201..63c91561ff 100644 --- a/platform/android/java/lib/src/org/godotengine/godot/GodotGLRenderView.java +++ b/platform/android/java/lib/src/org/godotengine/godot/GodotGLRenderView.java @@ -188,15 +188,15 @@ public class GodotGLRenderView extends GLSurfaceView implements GodotRenderView if (GLUtils.use_32) { setEGLConfigChooser(translucent ? - new RegularFallbackConfigChooser(8, 8, 8, 8, 24, stencil, + new RegularFallbackConfigChooser(8, 8, 8, 8, 24, stencil, new RegularConfigChooser(8, 8, 8, 8, 16, stencil)) : - new RegularFallbackConfigChooser(8, 8, 8, 8, 24, stencil, + new RegularFallbackConfigChooser(8, 8, 8, 8, 24, stencil, new RegularConfigChooser(5, 6, 5, 0, 16, stencil))); } else { setEGLConfigChooser(translucent ? - new RegularConfigChooser(8, 8, 8, 8, 16, stencil) : - new RegularConfigChooser(5, 6, 5, 0, 16, stencil)); + new RegularConfigChooser(8, 8, 8, 8, 16, stencil) : + new RegularConfigChooser(5, 6, 5, 0, 16, stencil)); } break; } diff --git a/platform/iphone/export/export.cpp b/platform/iphone/export/export.cpp index 3253112bf3..9dfd8a2c1b 100644 --- a/platform/iphone/export/export.cpp +++ b/platform/iphone/export/export.cpp @@ -979,7 +979,7 @@ Error EditorExportPlatformIOS::_codesign(String p_file, void *p_userdata) { codesign_args.push_back("-s"); codesign_args.push_back(data->preset->get(data->debug ? "application/code_sign_identity_debug" : "application/code_sign_identity_release")); codesign_args.push_back(p_file); - return OS::get_singleton()->execute("codesign", codesign_args, true); + return OS::get_singleton()->execute("codesign", codesign_args); } return OK; } @@ -1229,7 +1229,7 @@ Error EditorExportPlatformIOS::_copy_asset(const String &p_out_dir, const String install_name_args.push_back(String("@rpath").plus_file(framework_name).plus_file(file_name)); install_name_args.push_back(destination); - OS::get_singleton()->execute("install_name_tool", install_name_args, true); + OS::get_singleton()->execute("install_name_tool", install_name_args); } // Creating Info.plist @@ -1848,7 +1848,7 @@ Error EditorExportPlatformIOS::export_project(const Ref<EditorExportPreset> &p_p archive_args.push_back("archive"); archive_args.push_back("-archivePath"); archive_args.push_back(archive_path); - err = OS::get_singleton()->execute("xcodebuild", archive_args, true); + err = OS::get_singleton()->execute("xcodebuild", archive_args); ERR_FAIL_COND_V(err, err); if (ep.step("Making .ipa", 4)) { @@ -1863,7 +1863,7 @@ Error EditorExportPlatformIOS::export_project(const Ref<EditorExportPreset> &p_p export_args.push_back("-allowProvisioningUpdates"); export_args.push_back("-exportPath"); export_args.push_back(dest_dir); - err = OS::get_singleton()->execute("xcodebuild", export_args, true); + err = OS::get_singleton()->execute("xcodebuild", export_args); ERR_FAIL_COND_V(err, err); #else print_line(".ipa can only be built on macOS. Leaving Xcode project without building the package."); diff --git a/platform/javascript/os_javascript.cpp b/platform/javascript/os_javascript.cpp index 3fb5d4ad6a..b922b2ba91 100644 --- a/platform/javascript/os_javascript.cpp +++ b/platform/javascript/os_javascript.cpp @@ -106,14 +106,18 @@ void OS_JavaScript::finalize() { // Miscellaneous -Error OS_JavaScript::execute(const String &p_path, const List<String> &p_arguments, bool p_blocking, ProcessID *r_child_id, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { +Error OS_JavaScript::execute(const String &p_path, const List<String> &p_arguments, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { + return create_process(p_path, p_arguments); +} + +Error OS_JavaScript::create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id) { Array args; for (const List<String>::Element *E = p_arguments.front(); E; E = E->next()) { args.push_back(E->get()); } String json_args = JSON::print(args); int failed = godot_js_os_execute(json_args.utf8().get_data()); - ERR_FAIL_COND_V_MSG(failed, ERR_UNAVAILABLE, "OS::execute() must be implemented in JavaScript via 'engine.setOnExecute' if required."); + ERR_FAIL_COND_V_MSG(failed, ERR_UNAVAILABLE, "OS::execute() or create_process() must be implemented in JavaScript via 'engine.setOnExecute' if required."); return OK; } diff --git a/platform/javascript/os_javascript.h b/platform/javascript/os_javascript.h index 9c8da0c898..8db62d9d1c 100644 --- a/platform/javascript/os_javascript.h +++ b/platform/javascript/os_javascript.h @@ -70,7 +70,8 @@ public: MainLoop *get_main_loop() const override; bool main_loop_iterate(); - Error execute(const String &p_path, const List<String> &p_arguments, bool p_blocking = true, ProcessID *r_child_id = nullptr, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) override; + Error execute(const String &p_path, const List<String> &p_arguments, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) override; + Error create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id = nullptr) override; Error kill(const ProcessID &p_pid) override; int get_process_id() const override; diff --git a/platform/linuxbsd/crash_handler_linuxbsd.cpp b/platform/linuxbsd/crash_handler_linuxbsd.cpp index 90e34f8e77..ea0222cb19 100644 --- a/platform/linuxbsd/crash_handler_linuxbsd.cpp +++ b/platform/linuxbsd/crash_handler_linuxbsd.cpp @@ -104,7 +104,7 @@ static void handle_crash(int sig) { // Try to get the file/line number using addr2line int ret; - Error err = OS::get_singleton()->execute(String("addr2line"), args, true, nullptr, &output, &ret); + Error err = OS::get_singleton()->execute(String("addr2line"), args, &output, &ret); if (err == OK) { output.erase(output.length() - 1, 1); } diff --git a/platform/linuxbsd/display_server_x11.cpp b/platform/linuxbsd/display_server_x11.cpp index 1ee5cd3923..00b90923de 100644 --- a/platform/linuxbsd/display_server_x11.cpp +++ b/platform/linuxbsd/display_server_x11.cpp @@ -191,7 +191,7 @@ void DisplayServerX11::alert(const String &p_alert, const String &p_title) { } if (program.length()) { - OS::get_singleton()->execute(program, args, true); + OS::get_singleton()->execute(program, args); } else { print_line(p_alert); } diff --git a/platform/linuxbsd/os_linuxbsd.cpp b/platform/linuxbsd/os_linuxbsd.cpp index 68290bb4ec..44b3930d6c 100644 --- a/platform/linuxbsd/os_linuxbsd.cpp +++ b/platform/linuxbsd/os_linuxbsd.cpp @@ -128,7 +128,7 @@ Error OS_LinuxBSD::shell_open(String p_uri) { args.push_back(p_uri); // Agnostic - ok = execute("xdg-open", args, true, nullptr, nullptr, &err_code); + ok = execute("xdg-open", args, nullptr, &err_code); if (ok == OK && !err_code) { return OK; } else if (err_code == 2) { @@ -136,25 +136,25 @@ Error OS_LinuxBSD::shell_open(String p_uri) { } // GNOME args.push_front("open"); // The command is `gio open`, so we need to add it to args - ok = execute("gio", args, true, nullptr, nullptr, &err_code); + ok = execute("gio", args, nullptr, &err_code); if (ok == OK && !err_code) { return OK; } else if (err_code == 2) { return ERR_FILE_NOT_FOUND; } args.pop_front(); - ok = execute("gvfs-open", args, true, nullptr, nullptr, &err_code); + ok = execute("gvfs-open", args, nullptr, &err_code); if (ok == OK && !err_code) { return OK; } else if (err_code == 2) { return ERR_FILE_NOT_FOUND; } // KDE - ok = execute("kde-open5", args, true, nullptr, nullptr, &err_code); + ok = execute("kde-open5", args, nullptr, &err_code); if (ok == OK && !err_code) { return OK; } - ok = execute("kde-open", args, true, nullptr, nullptr, &err_code); + ok = execute("kde-open", args, nullptr, &err_code); return !err_code ? ok : FAILED; } @@ -232,7 +232,7 @@ String OS_LinuxBSD::get_system_dir(SystemDir p_dir) const { String pipe; List<String> arg; arg.push_back(xdgparam); - Error err = const_cast<OS_LinuxBSD *>(this)->execute("xdg-user-dir", arg, true, nullptr, &pipe); + Error err = const_cast<OS_LinuxBSD *>(this)->execute("xdg-user-dir", arg, &pipe); if (err != OK) { return "."; } @@ -307,7 +307,7 @@ Error OS_LinuxBSD::move_to_trash(const String &p_path) { List<String> args; args.push_back(p_path); args.push_front("trash"); // The command is `gio trash <file_name>` so we need to add it to args. - Error result = execute("gio", args, true, nullptr, nullptr, &err_code); // For GNOME based machines. + Error result = execute("gio", args, nullptr, &err_code); // For GNOME based machines. if (result == OK && !err_code) { return OK; } else if (err_code == 2) { @@ -317,7 +317,7 @@ Error OS_LinuxBSD::move_to_trash(const String &p_path) { args.pop_front(); args.push_front("move"); args.push_back("trash:/"); // The command is `kioclient5 move <file_name> trash:/`. - result = execute("kioclient5", args, true, nullptr, nullptr, &err_code); // For KDE based machines. + result = execute("kioclient5", args, nullptr, &err_code); // For KDE based machines. if (result == OK && !err_code) { return OK; } else if (err_code == 2) { @@ -326,7 +326,7 @@ Error OS_LinuxBSD::move_to_trash(const String &p_path) { args.pop_front(); args.pop_back(); - result = execute("gvfs-trash", args, true, nullptr, nullptr, &err_code); // For older Linux machines. + result = execute("gvfs-trash", args, nullptr, &err_code); // For older Linux machines. if (result == OK && !err_code) { return OK; } else if (err_code == 2) { @@ -432,7 +432,7 @@ Error OS_LinuxBSD::move_to_trash(const String &p_path) { mv_args.push_back(trash_path + "/files"); { int retval; - Error err = execute("mv", mv_args, true, nullptr, nullptr, &retval); + Error err = execute("mv", mv_args, nullptr, &retval); // Issue an error if "mv" failed to move the given resource to the trash can. if (err != OK || retval != 0) { diff --git a/platform/osx/crash_handler_osx.mm b/platform/osx/crash_handler_osx.mm index 4d6ed41a73..147ce26779 100644 --- a/platform/osx/crash_handler_osx.mm +++ b/platform/osx/crash_handler_osx.mm @@ -135,7 +135,7 @@ static void handle_crash(int sig) { int ret; String out = ""; - Error err = OS::get_singleton()->execute(String("atos"), args, true, NULL, &out, &ret); + Error err = OS::get_singleton()->execute(String("atos"), args, &out, &ret); if (err == OK && out.substr(0, 2) != "0x") { out.erase(out.length() - 1, 1); output = out; diff --git a/platform/osx/display_server_osx.mm b/platform/osx/display_server_osx.mm index bb3c1d47b7..2d43454501 100644 --- a/platform/osx/display_server_osx.mm +++ b/platform/osx/display_server_osx.mm @@ -256,9 +256,7 @@ static NSCursor *_cursorFromSelector(SEL selector, SEL fallback = nil) { List<String> args; args.push_back(((OS_OSX *)(OS_OSX::get_singleton()))->open_with_filename); String exec = OS::get_singleton()->get_executable_path(); - - OS::ProcessID pid = 0; - OS::get_singleton()->execute(exec, args, false, &pid); + OS::get_singleton()->create_process(exec, args); } #endif return YES; diff --git a/platform/osx/export/export.cpp b/platform/osx/export/export.cpp index 752b119958..337cfd6808 100644 --- a/platform/osx/export/export.cpp +++ b/platform/osx/export/export.cpp @@ -419,7 +419,7 @@ Error EditorExportPlatformOSX::_notarize(const Ref<EditorExportPreset> &p_preset args.push_back(p_path); String str; - Error err = OS::get_singleton()->execute("xcrun", args, true, nullptr, &str, nullptr, true); + Error err = OS::get_singleton()->execute("xcrun", args, &str, nullptr, true); ERR_FAIL_COND_V(err != OK, err); print_line("altool (" + p_path + "):\n" + str); @@ -470,7 +470,7 @@ Error EditorExportPlatformOSX::_code_sign(const Ref<EditorExportPreset> &p_prese args.push_back(p_path); String str; - Error err = OS::get_singleton()->execute("codesign", args, true, nullptr, &str, nullptr, true); + Error err = OS::get_singleton()->execute("codesign", args, &str, nullptr, true); ERR_FAIL_COND_V(err != OK, err); print_line("codesign (" + p_path + "):\n" + str); @@ -504,7 +504,7 @@ Error EditorExportPlatformOSX::_create_dmg(const String &p_dmg_path, const Strin args.push_back(p_app_path_name); String str; - Error err = OS::get_singleton()->execute("hdiutil", args, true, nullptr, &str, nullptr, true); + Error err = OS::get_singleton()->execute("hdiutil", args, &str, nullptr, true); ERR_FAIL_COND_V(err != OK, err); print_line("hdiutil returned: " + str); diff --git a/platform/uwp/export/export.cpp b/platform/uwp/export/export.cpp index 860448ceac..1aad2bfa1a 100644 --- a/platform/uwp/export/export.cpp +++ b/platform/uwp/export/export.cpp @@ -760,7 +760,7 @@ class EditorExportPlatformUWP : public EditorExportPlatform { result = result.replace("$version_string$", version); Platform arch = (Platform)(int)p_preset->get("architecture/target"); - String architecture = arch == ARM ? "arm" : arch == X86 ? "x86" : "x64"; + String architecture = arch == ARM ? "arm" : (arch == X86 ? "x86" : "x64"); result = result.replace("$architecture$", architecture); result = result.replace("$display_name$", String(p_preset->get("package/display_name")).is_empty() ? (String)ProjectSettings::get_singleton()->get("application/config/name") : String(p_preset->get("package/display_name"))); @@ -1411,7 +1411,7 @@ public: args.push_back(cert_pass); args.push_back(p_path); - OS::get_singleton()->execute(signtool_path, args, true); + OS::get_singleton()->execute(signtool_path, args); #endif // WINDOWS_ENABLED return OK; diff --git a/platform/uwp/os_uwp.cpp b/platform/uwp/os_uwp.cpp index 18d5d7e08d..5760bcc72c 100644 --- a/platform/uwp/os_uwp.cpp +++ b/platform/uwp/os_uwp.cpp @@ -638,7 +638,11 @@ void OS_UWP::set_custom_mouse_cursor(const RES &p_cursor, CursorShape p_shape, c // TODO } -Error OS_UWP::execute(const String &p_path, const List<String> &p_arguments, bool p_blocking, ProcessID *r_child_id, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { +Error OS_UWP::execute(const String &p_path, const List<String> &p_arguments, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { + return FAILED; +}; + +Error OS_UWP::create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id) { return FAILED; }; diff --git a/platform/uwp/os_uwp.h b/platform/uwp/os_uwp.h index edc197ad08..a4d3d6d52a 100644 --- a/platform/uwp/os_uwp.h +++ b/platform/uwp/os_uwp.h @@ -199,7 +199,8 @@ public: virtual void delay_usec(uint32_t p_usec) const; virtual uint64_t get_ticks_usec() const; - virtual Error execute(const String &p_path, const List<String> &p_arguments, bool p_blocking = true, ProcessID *r_child_id = nullptr, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr); + virtual Error execute(const String &p_path, const List<String> &p_arguments, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr); + virtual Error create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id = nullptr); virtual Error kill(const ProcessID &p_pid); virtual bool has_environment(const String &p_var) const; diff --git a/platform/windows/export/export.cpp b/platform/windows/export/export.cpp index 084a5bee1d..222597b3ff 100644 --- a/platform/windows/export/export.cpp +++ b/platform/windows/export/export.cpp @@ -173,11 +173,11 @@ void EditorExportPlatformWindows::_rcedit_add_data(const Ref<EditorExportPreset> } #ifdef WINDOWS_ENABLED - OS::get_singleton()->execute(rcedit_path, args, true); + OS::get_singleton()->execute(rcedit_path, args); #else // On non-Windows we need WINE to run rcedit args.push_front(rcedit_path); - OS::get_singleton()->execute(wine_path, args, true); + OS::get_singleton()->execute(wine_path, args); #endif } @@ -314,7 +314,7 @@ Error EditorExportPlatformWindows::_code_sign(const Ref<EditorExportPreset> &p_p #endif String str; - Error err = OS::get_singleton()->execute(signtool_path, args, true, nullptr, &str, nullptr, true); + Error err = OS::get_singleton()->execute(signtool_path, args, &str, nullptr, true); ERR_FAIL_COND_V(err != OK, err); print_line("codesign (" + p_path + "): " + str); diff --git a/platform/windows/os_windows.cpp b/platform/windows/os_windows.cpp index 051b69e8d9..f0848ff880 100644 --- a/platform/windows/os_windows.cpp +++ b/platform/windows/os_windows.cpp @@ -410,24 +410,23 @@ String OS_Windows::_quote_command_line_argument(const String &p_text) const { return p_text; } -Error OS_Windows::execute(const String &p_path, const List<String> &p_arguments, bool p_blocking, ProcessID *r_child_id, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { +Error OS_Windows::execute(const String &p_path, const List<String> &p_arguments, String *r_pipe, int *r_exitcode, bool read_stderr, Mutex *p_pipe_mutex) { String path = p_path.replace("/", "\\"); + String command = _quote_command_line_argument(path); + for (const List<String>::Element *E = p_arguments.front(); E; E = E->next()) { + command += " " + _quote_command_line_argument(E->get()); + } - if (p_blocking && r_pipe) { - String argss = _quote_command_line_argument(path); - for (const List<String>::Element *E = p_arguments.front(); E; E = E->next()) { - argss += " " + _quote_command_line_argument(E->get()); - } - + if (r_pipe) { if (read_stderr) { - argss += " 2>&1"; // Read stderr too + command += " 2>&1"; // Include stderr } - // Note: _wpopen is calling command as "cmd.exe /c argss", instead of executing it directly, add extra quotes around full command, to prevent it from stripping quotes in the command. - argss = _quote_command_line_argument(argss); - - FILE *f = _wpopen((LPCWSTR)(argss.utf16().get_data()), L"r"); - ERR_FAIL_COND_V(!f, ERR_CANT_OPEN); + // Add extra quotes around the full command, to prevent it from stripping quotes in the command, + // because _wpopen calls command as "cmd.exe /c command", instead of executing it directly + command = _quote_command_line_argument(command); + FILE *f = _wpopen((LPCWSTR)(command.utf16().get_data()), L"r"); + ERR_FAIL_COND_V_MSG(!f, ERR_CANT_OPEN, "Cannot create pipe from command: " + command); char buf[65535]; while (fgets(buf, 65535, f)) { if (p_pipe_mutex) { @@ -438,20 +437,40 @@ Error OS_Windows::execute(const String &p_path, const List<String> &p_arguments, p_pipe_mutex->unlock(); } } - int rv = _pclose(f); + if (r_exitcode) { *r_exitcode = rv; } - return OK; } - String cmdline = _quote_command_line_argument(path); - const List<String>::Element *I = p_arguments.front(); - while (I) { - cmdline += " " + _quote_command_line_argument(I->get()); - I = I->next(); + ProcessInfo pi; + ZeroMemory(&pi.si, sizeof(pi.si)); + pi.si.cb = sizeof(pi.si); + ZeroMemory(&pi.pi, sizeof(pi.pi)); + LPSTARTUPINFOW si_w = (LPSTARTUPINFOW)&pi.si; + + int ret = CreateProcessW(nullptr, (LPWSTR)(command.utf16().ptrw()), nullptr, nullptr, false, NORMAL_PRIORITY_CLASS & CREATE_NO_WINDOW, nullptr, nullptr, si_w, &pi.pi); + ERR_FAIL_COND_V_MSG(ret == 0, ERR_CANT_FORK, "Could not create child process: " + command); + + WaitForSingleObject(pi.pi.hProcess, INFINITE); + if (r_exitcode) { + DWORD ret2; + GetExitCodeProcess(pi.pi.hProcess, &ret2); + *r_exitcode = ret2; + } + CloseHandle(pi.pi.hProcess); + CloseHandle(pi.pi.hThread); + + return OK; +}; + +Error OS_Windows::create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id) { + String path = p_path.replace("/", "\\"); + String command = _quote_command_line_argument(path); + for (const List<String>::Element *E = p_arguments.front(); E; E = E->next()) { + command += " " + _quote_command_line_argument(E->get()); } ProcessInfo pi; @@ -460,27 +479,15 @@ Error OS_Windows::execute(const String &p_path, const List<String> &p_arguments, ZeroMemory(&pi.pi, sizeof(pi.pi)); LPSTARTUPINFOW si_w = (LPSTARTUPINFOW)&pi.si; - Char16String modstr = cmdline.utf16(); // Windows wants to change this no idea why. - int ret = CreateProcessW(nullptr, (LPWSTR)(modstr.ptrw()), nullptr, nullptr, 0, NORMAL_PRIORITY_CLASS & CREATE_NO_WINDOW, nullptr, nullptr, si_w, &pi.pi); - ERR_FAIL_COND_V(ret == 0, ERR_CANT_FORK); + int ret = CreateProcessW(nullptr, (LPWSTR)(command.utf16().ptrw()), nullptr, nullptr, false, NORMAL_PRIORITY_CLASS & CREATE_NO_WINDOW, nullptr, nullptr, si_w, &pi.pi); + ERR_FAIL_COND_V_MSG(ret == 0, ERR_CANT_FORK, "Could not create child process: " + command); - if (p_blocking) { - WaitForSingleObject(pi.pi.hProcess, INFINITE); - if (r_exitcode) { - DWORD ret2; - GetExitCodeProcess(pi.pi.hProcess, &ret2); - *r_exitcode = ret2; - } - - CloseHandle(pi.pi.hProcess); - CloseHandle(pi.pi.hThread); - } else { - ProcessID pid = pi.pi.dwProcessId; - if (r_child_id) { - *r_child_id = pid; - } - process_map->insert(pid, pi); + ProcessID pid = pi.pi.dwProcessId; + if (r_child_id) { + *r_child_id = pid; } + process_map->insert(pid, pi); + return OK; }; diff --git a/platform/windows/os_windows.h b/platform/windows/os_windows.h index 78258f132b..1a8791196b 100644 --- a/platform/windows/os_windows.h +++ b/platform/windows/os_windows.h @@ -136,7 +136,8 @@ public: virtual void delay_usec(uint32_t p_usec) const override; virtual uint64_t get_ticks_usec() const override; - virtual Error execute(const String &p_path, const List<String> &p_arguments, bool p_blocking = true, ProcessID *r_child_id = nullptr, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) override; + virtual Error execute(const String &p_path, const List<String> &p_arguments, String *r_pipe = nullptr, int *r_exitcode = nullptr, bool read_stderr = false, Mutex *p_pipe_mutex = nullptr) override; + virtual Error create_process(const String &p_path, const List<String> &p_arguments, ProcessID *r_child_id = nullptr) override; virtual Error kill(const ProcessID &p_pid) override; virtual int get_process_id() const override; diff --git a/scene/2d/collision_polygon_2d.cpp b/scene/2d/collision_polygon_2d.cpp index 7347b7829a..851e40cda6 100644 --- a/scene/2d/collision_polygon_2d.cpp +++ b/scene/2d/collision_polygon_2d.cpp @@ -36,7 +36,7 @@ #include "scene/resources/concave_polygon_shape_2d.h" #include "scene/resources/convex_polygon_shape_2d.h" -#include "thirdparty/misc/triangulator.h" +#include "thirdparty/misc/polypartition.h" void CollisionPolygon2D::_build_polygon() { parent->shape_owner_clear_shapes(owner_id); @@ -194,6 +194,7 @@ void CollisionPolygon2D::set_polygon(const Vector<Point2> &p_polygon) { if (parent) { _build_polygon(); + _update_in_shape_owner(); } update(); update_configuration_warning(); @@ -208,6 +209,7 @@ void CollisionPolygon2D::set_build_mode(BuildMode p_mode) { build_mode = p_mode; if (parent) { _build_polygon(); + _update_in_shape_owner(); } } diff --git a/scene/2d/collision_shape_2d.cpp b/scene/2d/collision_shape_2d.cpp index acdde96df0..37bed577ac 100644 --- a/scene/2d/collision_shape_2d.cpp +++ b/scene/2d/collision_shape_2d.cpp @@ -141,6 +141,9 @@ void CollisionShape2D::_notification(int p_what) { } void CollisionShape2D::set_shape(const Ref<Shape2D> &p_shape) { + if (p_shape == shape) { + return; + } if (shape.is_valid()) { shape->disconnect("changed", callable_mp(this, &CollisionShape2D::_shape_changed)); } @@ -151,6 +154,7 @@ void CollisionShape2D::set_shape(const Ref<Shape2D> &p_shape) { if (shape.is_valid()) { parent->shape_owner_add_shape(owner_id, shape); } + _update_in_shape_owner(); } if (shape.is_valid()) { diff --git a/scene/2d/navigation_region_2d.cpp b/scene/2d/navigation_region_2d.cpp index 72dc8bd9ad..7360fce330 100644 --- a/scene/2d/navigation_region_2d.cpp +++ b/scene/2d/navigation_region_2d.cpp @@ -37,7 +37,7 @@ #include "navigation_2d.h" #include "servers/navigation_server_2d.h" -#include "thirdparty/misc/triangulator.h" +#include "thirdparty/misc/polypartition.h" #ifdef TOOLS_ENABLED Rect2 NavigationPolygon::_edit_get_rect() const { @@ -228,7 +228,7 @@ void NavigationPolygon::make_polygons_from_outlines() { MutexLock lock(navmesh_generation); navmesh.unref(); } - List<TriangulatorPoly> in_poly, out_poly; + List<TPPLPoly> in_poly, out_poly; Vector2 outside_point(-1e10, -1e10); @@ -278,23 +278,23 @@ void NavigationPolygon::make_polygons_from_outlines() { bool outer = (interscount % 2) == 0; - TriangulatorPoly tp; + TPPLPoly tp; tp.Init(olsize); for (int j = 0; j < olsize; j++) { tp[j] = r[j]; } if (outer) { - tp.SetOrientation(TRIANGULATOR_CCW); + tp.SetOrientation(TPPL_ORIENTATION_CCW); } else { - tp.SetOrientation(TRIANGULATOR_CW); + tp.SetOrientation(TPPL_ORIENTATION_CW); tp.SetHole(true); } in_poly.push_back(tp); } - TriangulatorPartition tpart; + TPPLPartition tpart; if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { //failed! ERR_PRINT("NavigationPolygon: Convex partition failed!"); return; @@ -304,8 +304,8 @@ void NavigationPolygon::make_polygons_from_outlines() { vertices.resize(0); Map<Vector2, int> points; - for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) { - TriangulatorPoly &tp = I->get(); + for (List<TPPLPoly>::Element *I = out_poly.front(); I; I = I->next()) { + TPPLPoly &tp = I->get(); struct Polygon p; diff --git a/scene/3d/collision_shape_3d.cpp b/scene/3d/collision_shape_3d.cpp index 47966c772b..503d1be104 100644 --- a/scene/3d/collision_shape_3d.cpp +++ b/scene/3d/collision_shape_3d.cpp @@ -93,7 +93,6 @@ void CollisionShape3D::_notification(int p_what) { if (shape.is_valid()) { parent->shape_owner_add_shape(owner_id, shape); } - _update_in_shape_owner(); } } break; case NOTIFICATION_ENTER_TREE: { @@ -170,6 +169,9 @@ void CollisionShape3D::_bind_methods() { } void CollisionShape3D::set_shape(const Ref<Shape3D> &p_shape) { + if (p_shape == shape) { + return; + } if (!shape.is_null()) { shape->unregister_owner(this); shape->disconnect("changed", callable_mp(this, &CollisionShape3D::_shape_changed)); diff --git a/scene/3d/gpu_particles_collision_3d.cpp b/scene/3d/gpu_particles_collision_3d.cpp index 145b5afbd0..97241be60f 100644 --- a/scene/3d/gpu_particles_collision_3d.cpp +++ b/scene/3d/gpu_particles_collision_3d.cpp @@ -293,11 +293,11 @@ void GPUParticlesCollisionSDF::_find_closest_distance(const Vector3 &p_pos, cons SGN(cb.cross(nor).dot(pb)) + SGN(ac.cross(nor).dot(pc)) < 2.0) ? - MIN(MIN( + MIN(MIN( Vector3_dot2(ba * CLAMP(ba.dot(pa) / Vector3_dot2(ba), 0.0, 1.0) - pa), Vector3_dot2(cb * CLAMP(cb.dot(pb) / Vector3_dot2(cb), 0.0, 1.0) - pb)), Vector3_dot2(ac * CLAMP(ac.dot(pc) / Vector3_dot2(ac), 0.0, 1.0) - pc)) : - nor.dot(pa) * nor.dot(pa) / Vector3_dot2(nor)); + nor.dot(pa) * nor.dot(pa) / Vector3_dot2(nor)); closest_distance = MIN(closest_distance, inside_d); } diff --git a/scene/3d/node_3d.cpp b/scene/3d/node_3d.cpp index 503dd5735b..2a49e60669 100644 --- a/scene/3d/node_3d.cpp +++ b/scene/3d/node_3d.cpp @@ -239,8 +239,8 @@ void Node3D::set_transform(const Transform &p_transform) { void Node3D::set_global_transform(const Transform &p_transform) { Transform xform = (data.parent && !data.top_level_active) ? - data.parent->get_global_transform().affine_inverse() * p_transform : - p_transform; + data.parent->get_global_transform().affine_inverse() * p_transform : + p_transform; set_transform(xform); } diff --git a/scene/3d/physics_joint_3d.cpp b/scene/3d/physics_joint_3d.cpp index 0a2af6b0cd..326b91b6ed 100644 --- a/scene/3d/physics_joint_3d.cpp +++ b/scene/3d/physics_joint_3d.cpp @@ -114,21 +114,23 @@ void Joint3D::_update_joint(bool p_only_free) { return; } - if (!body_a) { - SWAP(body_a, body_b); - } - warning = String(); update_configuration_warning(); - joint = _configure_joint(body_a, body_b); + if (body_a) { + joint = _configure_joint(body_a, body_b); + } else if (body_b) { + joint = _configure_joint(body_b, nullptr); + } ERR_FAIL_COND_MSG(!joint.is_valid(), "Failed to configure the joint."); PhysicsServer3D::get_singleton()->joint_set_solver_priority(joint, solver_priority); - ba = body_a->get_rid(); - body_a->connect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &Joint3D::_body_exit_tree), make_binds(body_a->get_instance_id())); + if (body_a) { + ba = body_a->get_rid(); + body_a->connect(SceneStringNames::get_singleton()->tree_exiting, callable_mp(this, &Joint3D::_body_exit_tree), make_binds(body_a->get_instance_id())); + } if (body_b) { bb = body_b->get_rid(); diff --git a/scene/gui/rich_text_label.cpp b/scene/gui/rich_text_label.cpp index a1aa72b29a..05ca97491b 100644 --- a/scene/gui/rich_text_label.cpp +++ b/scene/gui/rich_text_label.cpp @@ -3677,6 +3677,7 @@ void RichTextLabel::set_percent_visible(float p_percent) { } main->first_invalid_line = 0; //invalidate ALL _validate_line_caches(main); + _change_notify("visible_characters"); update(); } } @@ -3890,6 +3891,15 @@ void RichTextLabel::_bind_methods() { void RichTextLabel::set_visible_characters(int p_visible) { visible_characters = p_visible; + if (p_visible == -1) { + percent_visible = 1; + } else { + int total_char_count = get_total_character_count(); + if (total_char_count > 0) { + percent_visible = (float)p_visible / (float)total_char_count; + } + } + _change_notify("percent_visible"); update(); } diff --git a/scene/gui/tab_container.cpp b/scene/gui/tab_container.cpp index 7f0d7b6e7b..64a2a1843d 100644 --- a/scene/gui/tab_container.cpp +++ b/scene/gui/tab_container.cpp @@ -789,6 +789,10 @@ Control *TabContainer::get_current_tab_control() const { void TabContainer::remove_child_notify(Node *p_child) { Container::remove_child_notify(p_child); + if (!Object::cast_to<Control>(p_child)) { + return; + } + call_deferred("_update_current_tab"); p_child->disconnect("renamed", callable_mp(this, &TabContainer::_child_renamed_callback)); diff --git a/scene/resources/particles_material.cpp b/scene/resources/particles_material.cpp index 73b7a5cfe9..3aa9f9b3bc 100644 --- a/scene/resources/particles_material.cpp +++ b/scene/resources/particles_material.cpp @@ -646,7 +646,7 @@ void ParticlesMaterial::_update_shader() { code += " for(int i=0;i<emit_count;i++) {\n"; code += " uint flags = FLAG_EMIT_POSITION|FLAG_EMIT_ROT_SCALE;\n"; code += " if (sub_emitter_keep_velocity) flags|=FLAG_EMIT_VELOCITY;\n"; - code += " emit_particle(TRANSFORM,VELOCITY,vec4(0.0),vec4(0.0),flags);\n"; + code += " emit_subparticle(TRANSFORM,VELOCITY,vec4(0.0),vec4(0.0),flags);\n"; code += " }"; } diff --git a/servers/physics_2d/space_2d_sw.cpp b/servers/physics_2d/space_2d_sw.cpp index ad5dca37e4..068bc7fc0a 100644 --- a/servers/physics_2d/space_2d_sw.cpp +++ b/servers/physics_2d/space_2d_sw.cpp @@ -278,9 +278,9 @@ bool PhysicsDirectSpaceState2DSW::cast_motion(const RID &p_shape, const Transfor continue; } - //test initial overlap + //test initial overlap, ignore objects it's inside of. if (CollisionSolver2DSW::solve(shape, p_xform, Vector2(), col_obj->get_shape(shape_idx), col_obj_xform, Vector2(), nullptr, nullptr, nullptr, p_margin)) { - return false; + continue; } //just do kinematic solving diff --git a/servers/physics_3d/joints/generic_6dof_joint_3d_sw.cpp b/servers/physics_3d/joints/generic_6dof_joint_3d_sw.cpp index 7eb49e657b..13b389251f 100644 --- a/servers/physics_3d/joints/generic_6dof_joint_3d_sw.cpp +++ b/servers/physics_3d/joints/generic_6dof_joint_3d_sw.cpp @@ -132,7 +132,7 @@ real_t G6DOFRotationalLimitMotor3DSW::solveAngularLimits( real_t oldaccumImpulse = m_accumulatedImpulse; real_t sum = oldaccumImpulse + clippedMotorImpulse; - m_accumulatedImpulse = sum > hi ? real_t(0.) : sum < lo ? real_t(0.) : sum; + m_accumulatedImpulse = sum > hi ? real_t(0.) : (sum < lo ? real_t(0.) : sum); clippedMotorImpulse = m_accumulatedImpulse - oldaccumImpulse; @@ -201,7 +201,7 @@ real_t G6DOFTranslationalLimitMotor3DSW::solveLinearAxis( real_t oldNormalImpulse = m_accumulatedImpulse[limit_index]; real_t sum = oldNormalImpulse + normalImpulse; - m_accumulatedImpulse[limit_index] = sum > hi ? real_t(0.) : sum < lo ? real_t(0.) : sum; + m_accumulatedImpulse[limit_index] = sum > hi ? real_t(0.) : (sum < lo ? real_t(0.) : sum); normalImpulse = m_accumulatedImpulse[limit_index] - oldNormalImpulse; Vector3 impulse_vector = axis_normal_on_a * normalImpulse; diff --git a/servers/physics_3d/space_3d_sw.cpp b/servers/physics_3d/space_3d_sw.cpp index 0395a3339c..6cc7ad2676 100644 --- a/servers/physics_3d/space_3d_sw.cpp +++ b/servers/physics_3d/space_3d_sw.cpp @@ -274,11 +274,11 @@ bool PhysicsDirectSpaceState3DSW::cast_motion(const RID &p_shape, const Transfor continue; } - //test initial overlap + //test initial overlap, ignore objects it's inside of. sep_axis = p_motion.normalized(); if (!CollisionSolver3DSW::solve_distance(shape, p_xform, col_obj->get_shape(shape_idx), col_obj_xform, point_A, point_B, aabb, &sep_axis)) { - return false; + continue; } //just do kinematic solving diff --git a/servers/rendering/renderer_rd/renderer_scene_render_rd.cpp b/servers/rendering/renderer_rd/renderer_scene_render_rd.cpp index 188bcde8d7..a655edcfa7 100644 --- a/servers/rendering/renderer_rd/renderer_scene_render_rd.cpp +++ b/servers/rendering/renderer_rd/renderer_scene_render_rd.cpp @@ -4416,7 +4416,10 @@ void RendererSceneRenderRD::gi_probe_update(RID p_probe, bool p_update_light_ins } } - dmap.uniform_set = RD::get_singleton()->uniform_set_create(uniforms, giprobe_lighting_shader_version_shaders[(write && plot) ? GI_PROBE_SHADER_VERSION_DYNAMIC_SHRINK_WRITE_PLOT : write ? GI_PROBE_SHADER_VERSION_DYNAMIC_SHRINK_WRITE : GI_PROBE_SHADER_VERSION_DYNAMIC_SHRINK_PLOT], 0); + dmap.uniform_set = RD::get_singleton()->uniform_set_create( + uniforms, + giprobe_lighting_shader_version_shaders[(write && plot) ? GI_PROBE_SHADER_VERSION_DYNAMIC_SHRINK_WRITE_PLOT : (write ? GI_PROBE_SHADER_VERSION_DYNAMIC_SHRINK_WRITE : GI_PROBE_SHADER_VERSION_DYNAMIC_SHRINK_PLOT)], + 0); } gi_probe->dynamic_maps.push_back(dmap); @@ -4850,7 +4853,16 @@ void RendererSceneRenderRD::_debug_giprobe(RID p_gi_probe, RD::DrawListID p_draw } giprobe_debug_uniform_set = RD::get_singleton()->uniform_set_create(uniforms, giprobe_debug_shader_version_shaders[0], 0); - RD::get_singleton()->draw_list_bind_render_pipeline(p_draw_list, giprobe_debug_shader_version_pipelines[p_emission ? GI_PROBE_DEBUG_EMISSION : p_lighting ? (gi_probe->has_dynamic_object_data ? GI_PROBE_DEBUG_LIGHT_FULL : GI_PROBE_DEBUG_LIGHT) : GI_PROBE_DEBUG_COLOR].get_render_pipeline(RD::INVALID_ID, RD::get_singleton()->framebuffer_get_format(p_framebuffer))); + + int giprobe_debug_pipeline = GI_PROBE_DEBUG_COLOR; + if (p_emission) { + giprobe_debug_pipeline = GI_PROBE_DEBUG_EMISSION; + } else if (p_lighting) { + giprobe_debug_pipeline = gi_probe->has_dynamic_object_data ? GI_PROBE_DEBUG_LIGHT_FULL : GI_PROBE_DEBUG_LIGHT; + } + RD::get_singleton()->draw_list_bind_render_pipeline( + p_draw_list, + giprobe_debug_shader_version_pipelines[giprobe_debug_pipeline].get_render_pipeline(RD::INVALID_ID, RD::get_singleton()->framebuffer_get_format(p_framebuffer))); RD::get_singleton()->draw_list_bind_uniform_set(p_draw_list, giprobe_debug_uniform_set, 0); RD::get_singleton()->draw_list_set_push_constant(p_draw_list, &push_constant, sizeof(GIProbeDebugPushConstant)); RD::get_singleton()->draw_list_draw(p_draw_list, false, cell_count, 36); diff --git a/servers/rendering/renderer_rd/renderer_storage_rd.cpp b/servers/rendering/renderer_rd/renderer_storage_rd.cpp index 1ffc024d42..b74a1083e7 100644 --- a/servers/rendering/renderer_rd/renderer_storage_rd.cpp +++ b/servers/rendering/renderer_rd/renderer_storage_rd.cpp @@ -8780,7 +8780,7 @@ RendererStorageRD::RendererStorageRD() { actions.renames["RESTART_VELOCITY"] = "restart_velocity"; actions.renames["RESTART_COLOR"] = "restart_color"; actions.renames["RESTART_CUSTOM"] = "restart_custom"; - actions.renames["emit_particle"] = "emit_particle"; + actions.renames["emit_subparticle"] = "emit_subparticle"; actions.renames["COLLIDED"] = "collided"; actions.renames["COLLISION_NORMAL"] = "collision_normal"; actions.renames["COLLISION_DEPTH"] = "collision_depth"; diff --git a/servers/rendering/renderer_rd/shaders/particles.glsl b/servers/rendering/renderer_rd/shaders/particles.glsl index 926c7ef9fc..cb6d8dc7f6 100644 --- a/servers/rendering/renderer_rd/shaders/particles.glsl +++ b/servers/rendering/renderer_rd/shaders/particles.glsl @@ -173,7 +173,7 @@ uint hash(uint x) { return x; } -bool emit_particle(mat4 p_xform, vec3 p_velocity, vec4 p_color, vec4 p_custom, uint p_flags) { +bool emit_subparticle(mat4 p_xform, vec3 p_velocity, vec4 p_color, vec4 p_custom, uint p_flags) { if (!params.can_emit) { return false; } diff --git a/servers/rendering/shader_types.cpp b/servers/rendering/shader_types.cpp index c1fa4a8ca7..e99b8504bb 100644 --- a/servers/rendering/shader_types.cpp +++ b/servers/rendering/shader_types.cpp @@ -347,7 +347,7 @@ ShaderTypes::ShaderTypes() { emit_vertex_func.arguments.push_back(ShaderLanguage::StageFunctionInfo::Argument("custom", ShaderLanguage::TYPE_VEC4)); emit_vertex_func.arguments.push_back(ShaderLanguage::StageFunctionInfo::Argument("flags", ShaderLanguage::TYPE_UINT)); emit_vertex_func.return_type = ShaderLanguage::TYPE_BOOL; //whether it could emit - shader_modes[RS::SHADER_PARTICLES].functions["compute"].stage_functions["emit_particle"] = emit_vertex_func; + shader_modes[RS::SHADER_PARTICLES].functions["compute"].stage_functions["emit_subparticle"] = emit_vertex_func; } shader_modes[RS::SHADER_PARTICLES].modes.push_back("collision_use_scale"); diff --git a/tests/test_math.cpp b/tests/test_math.cpp index cda0cffda3..26c2aa2088 100644 --- a/tests/test_math.cpp +++ b/tests/test_math.cpp @@ -617,7 +617,7 @@ MainLoop *test() { List<String> args; args.push_back("-l"); - Error err = OS::get_singleton()->execute("/bin/ls", args, true, nullptr, &ret); + Error err = OS::get_singleton()->execute("/bin/ls", args, &ret); print_line("error: " + itos(err)); print_line(ret); diff --git a/thirdparty/README.md b/thirdparty/README.md index 6df303015b..3803e87fea 100644 --- a/thirdparty/README.md +++ b/thirdparty/README.md @@ -424,6 +424,11 @@ Collection of single-file libraries used in Godot components. * Upstream: http://www.pcg-random.org * Version: minimal C implementation, http://www.pcg-random.org/download.html * License: Apache 2.0 +- `polypartition.{cpp,h}` + * Upstream: https://github.com/ivanfratric/polypartition (`src/polypartition.{cpp,h}`) + * Version: git (7bdffb428b2b19ad1c43aa44c714dcc104177e84, 2021) + * Modifications: Change from STL to Godot types (see provided patch). + * License: MIT - `r128.h` * Upstream: https://github.com/fahickman/r128 * Version: 1.4.4 (cf2e88fc3e7d7dfe99189686f914874cd0bda15e, 2020) @@ -441,10 +446,6 @@ Collection of single-file libraries used in Godot components. * Upstream: https://github.com/nothings/stb * Version: 1.20 (314d0a6f9af5af27e585336eecea333e95c5a2d8, 2020) * License: Public Domain or Unlicense or MIT -- `triangulator.{cpp,h}` - * Upstream: https://github.com/ivanfratric/polypartition (`src/polypartition.cpp`) - * Version: TBD, class was renamed - * License: MIT - `yuv2rgb.h` * Upstream: http://wss.co.uk/pinknoise/yuv2rgb/ (to check) * Version: ? diff --git a/thirdparty/misc/patches/polypartition-godot-types.patch b/thirdparty/misc/patches/polypartition-godot-types.patch new file mode 100644 index 0000000000..59fdb2707c --- /dev/null +++ b/thirdparty/misc/patches/polypartition-godot-types.patch @@ -0,0 +1,819 @@ +diff --git a/thirdparty/misc/polypartition.cpp b/thirdparty/misc/polypartition.cpp +index 3a8a6efa8319..4f1b6dcb21d8 100644 +--- a/thirdparty/misc/polypartition.cpp ++++ b/thirdparty/misc/polypartition.cpp +@@ -23,10 +23,7 @@ + + #include "polypartition.h" + +-#include <math.h> +-#include <string.h> + #include <algorithm> +-#include <vector> + + TPPLPoly::TPPLPoly() { + hole = false; +@@ -186,7 +183,7 @@ int TPPLPartition::Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TP + // Removes holes from inpolys by merging them with non-holes. + int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + TPPLPolyList polys; +- TPPLPolyList::iterator holeiter, polyiter, iter, iter2; ++ TPPLPolyList::Element *holeiter, *polyiter, *iter, *iter2; + long i, i2, holepointindex, polypointindex; + TPPLPoint holepoint, polypoint, bestpolypoint; + TPPLPoint linep1, linep2; +@@ -198,15 +195,15 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + + // Check for the trivial case of no holes. + hasholes = false; +- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) { +- if (iter->IsHole()) { ++ for (iter = inpolys->front(); iter; iter = iter->next()) { ++ if (iter->get().IsHole()) { + hasholes = true; + break; + } + } + if (!hasholes) { +- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) { +- outpolys->push_back(*iter); ++ for (iter = inpolys->front(); iter; iter = iter->next()) { ++ outpolys->push_back(iter->get()); + } + return 1; + } +@@ -216,8 +213,8 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + while (1) { + // Find the hole point with the largest x. + hasholes = false; +- for (iter = polys.begin(); iter != polys.end(); iter++) { +- if (!iter->IsHole()) { ++ for (iter = polys.front(); iter; iter = iter->next()) { ++ if (!iter->get().IsHole()) { + continue; + } + +@@ -227,8 +224,8 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + holepointindex = 0; + } + +- for (i = 0; i < iter->GetNumPoints(); i++) { +- if (iter->GetPoint(i).x > holeiter->GetPoint(holepointindex).x) { ++ for (i = 0; i < iter->get().GetNumPoints(); i++) { ++ if (iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) { + holeiter = iter; + holepointindex = i; + } +@@ -237,24 +234,24 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + if (!hasholes) { + break; + } +- holepoint = holeiter->GetPoint(holepointindex); ++ holepoint = holeiter->get().GetPoint(holepointindex); + + pointfound = false; +- for (iter = polys.begin(); iter != polys.end(); iter++) { +- if (iter->IsHole()) { ++ for (iter = polys.front(); iter; iter = iter->next()) { ++ if (iter->get().IsHole()) { + continue; + } +- for (i = 0; i < iter->GetNumPoints(); i++) { +- if (iter->GetPoint(i).x <= holepoint.x) { ++ for (i = 0; i < iter->get().GetNumPoints(); i++) { ++ if (iter->get().GetPoint(i).x <= holepoint.x) { + continue; + } +- if (!InCone(iter->GetPoint((i + iter->GetNumPoints() - 1) % (iter->GetNumPoints())), +- iter->GetPoint(i), +- iter->GetPoint((i + 1) % (iter->GetNumPoints())), ++ if (!InCone(iter->get().GetPoint((i + iter->get().GetNumPoints() - 1) % (iter->get().GetNumPoints())), ++ iter->get().GetPoint(i), ++ iter->get().GetPoint((i + 1) % (iter->get().GetNumPoints())), + holepoint)) { + continue; + } +- polypoint = iter->GetPoint(i); ++ polypoint = iter->get().GetPoint(i); + if (pointfound) { + v1 = Normalize(polypoint - holepoint); + v2 = Normalize(bestpolypoint - holepoint); +@@ -263,13 +260,13 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + } + } + pointvisible = true; +- for (iter2 = polys.begin(); iter2 != polys.end(); iter2++) { +- if (iter2->IsHole()) { ++ for (iter2 = polys.front(); iter2; iter2->next()) { ++ if (iter2->get().IsHole()) { + continue; + } +- for (i2 = 0; i2 < iter2->GetNumPoints(); i2++) { +- linep1 = iter2->GetPoint(i2); +- linep2 = iter2->GetPoint((i2 + 1) % (iter2->GetNumPoints())); ++ for (i2 = 0; i2 < iter2->get().GetNumPoints(); i2++) { ++ linep1 = iter2->get().GetPoint(i2); ++ linep2 = iter2->get().GetPoint((i2 + 1) % (iter2->get().GetNumPoints())); + if (Intersects(holepoint, polypoint, linep1, linep2)) { + pointvisible = false; + break; +@@ -292,18 +289,18 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + return 0; + } + +- newpoly.Init(holeiter->GetNumPoints() + polyiter->GetNumPoints() + 2); ++ newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2); + i2 = 0; + for (i = 0; i <= polypointindex; i++) { +- newpoly[i2] = polyiter->GetPoint(i); ++ newpoly[i2] = polyiter->get().GetPoint(i); + i2++; + } +- for (i = 0; i <= holeiter->GetNumPoints(); i++) { +- newpoly[i2] = holeiter->GetPoint((i + holepointindex) % holeiter->GetNumPoints()); ++ for (i = 0; i <= holeiter->get().GetNumPoints(); i++) { ++ newpoly[i2] = holeiter->get().GetPoint((i + holepointindex) % holeiter->get().GetNumPoints()); + i2++; + } +- for (i = polypointindex; i < polyiter->GetNumPoints(); i++) { +- newpoly[i2] = polyiter->GetPoint(i); ++ for (i = polypointindex; i < polyiter->get().GetNumPoints(); i++) { ++ newpoly[i2] = polyiter->get().GetPoint(i); + i2++; + } + +@@ -312,8 +309,8 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + polys.push_back(newpoly); + } + +- for (iter = polys.begin(); iter != polys.end(); iter++) { +- outpolys->push_back(*iter); ++ for (iter = polys.front(); iter; iter = iter->next()) { ++ outpolys->push_back(iter->get()); + } + + return 1; +@@ -524,13 +521,13 @@ int TPPLPartition::Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles) { + + int TPPLPartition::Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles) { + TPPLPolyList outpolys; +- TPPLPolyList::iterator iter; ++ TPPLPolyList::Element *iter; + + if (!RemoveHoles(inpolys, &outpolys)) { + return 0; + } +- for (iter = outpolys.begin(); iter != outpolys.end(); iter++) { +- if (!Triangulate_EC(&(*iter), triangles)) { ++ for (iter = outpolys.front(); iter; iter = iter->next()) { ++ if (!Triangulate_EC(&(iter->get()), triangles)) { + return 0; + } + } +@@ -543,7 +540,7 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) { + } + + TPPLPolyList triangles; +- TPPLPolyList::iterator iter1, iter2; ++ TPPLPolyList::Element *iter1, *iter2; + TPPLPoly *poly1 = NULL, *poly2 = NULL; + TPPLPoly newpoly; + TPPLPoint d1, d2, p1, p2, p3; +@@ -578,19 +575,19 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) { + return 0; + } + +- for (iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) { +- poly1 = &(*iter1); ++ for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) { ++ poly1 = &(iter1->get()); + for (i11 = 0; i11 < poly1->GetNumPoints(); i11++) { + d1 = poly1->GetPoint(i11); + i12 = (i11 + 1) % (poly1->GetNumPoints()); + d2 = poly1->GetPoint(i12); + + isdiagonal = false; +- for (iter2 = iter1; iter2 != triangles.end(); iter2++) { ++ for (iter2 = iter1; iter2; iter2 = iter2->next()) { + if (iter1 == iter2) { + continue; + } +- poly2 = &(*iter2); ++ poly2 = &(iter2->get()); + + for (i21 = 0; i21 < poly2->GetNumPoints(); i21++) { + if ((d2.x != poly2->GetPoint(i21).x) || (d2.y != poly2->GetPoint(i21).y)) { +@@ -660,16 +657,16 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) { + } + + triangles.erase(iter2); +- *iter1 = newpoly; +- poly1 = &(*iter1); ++ iter1->get() = newpoly; ++ poly1 = &(iter1->get()); + i11 = -1; + + continue; + } + } + +- for (iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) { +- parts->push_back(*iter1); ++ for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) { ++ parts->push_back(iter1->get()); + } + + return 1; +@@ -677,13 +674,13 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) { + + int TPPLPartition::ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts) { + TPPLPolyList outpolys; +- TPPLPolyList::iterator iter; ++ TPPLPolyList::Element *iter; + + if (!RemoveHoles(inpolys, &outpolys)) { + return 0; + } +- for (iter = outpolys.begin(); iter != outpolys.end(); iter++) { +- if (!ConvexPartition_HM(&(*iter), parts)) { ++ for (iter = outpolys.front(); iter; iter = iter->next()) { ++ if (!ConvexPartition_HM(&(iter->get()), parts)) { + return 0; + } + } +@@ -824,8 +821,8 @@ int TPPLPartition::Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles) { + newdiagonal.index1 = 0; + newdiagonal.index2 = n - 1; + diagonals.push_back(newdiagonal); +- while (!diagonals.empty()) { +- diagonal = *(diagonals.begin()); ++ while (!diagonals.is_empty()) { ++ diagonal = diagonals.front()->get(); + diagonals.pop_front(); + bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex; + if (bestvertex == -1) { +@@ -873,10 +870,10 @@ void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 + pairs->push_front(newdiagonal); + dpstates[a][b].weight = w; + } else { +- if ((!pairs->empty()) && (i <= pairs->begin()->index1)) { ++ if ((!pairs->is_empty()) && (i <= pairs->front()->get().index1)) { + return; + } +- while ((!pairs->empty()) && (pairs->begin()->index2 >= j)) { ++ while ((!pairs->is_empty()) && (pairs->front()->get().index2 >= j)) { + pairs->pop_front(); + } + pairs->push_front(newdiagonal); +@@ -885,7 +882,7 @@ void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 + + void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { + DiagonalList *pairs = NULL; +- DiagonalList::iterator iter, lastiter; ++ DiagonalList::Element *iter, *lastiter; + long top; + long w; + +@@ -902,23 +899,23 @@ void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPS + } + if (j - i > 1) { + pairs = &(dpstates[i][j].pairs); +- iter = pairs->end(); +- lastiter = pairs->end(); +- while (iter != pairs->begin()) { ++ iter = pairs->back(); ++ lastiter = pairs->back(); ++ while (iter != pairs->front()) { + iter--; +- if (!IsReflex(vertices[iter->index2].p, vertices[j].p, vertices[k].p)) { ++ if (!IsReflex(vertices[iter->get().index2].p, vertices[j].p, vertices[k].p)) { + lastiter = iter; + } else { + break; + } + } +- if (lastiter == pairs->end()) { ++ if (lastiter == pairs->back()) { + w++; + } else { +- if (IsReflex(vertices[k].p, vertices[i].p, vertices[lastiter->index1].p)) { ++ if (IsReflex(vertices[k].p, vertices[i].p, vertices[lastiter->get().index1].p)) { + w++; + } else { +- top = lastiter->index1; ++ top = lastiter->get().index1; + } + } + } +@@ -927,7 +924,7 @@ void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPS + + void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { + DiagonalList *pairs = NULL; +- DiagonalList::iterator iter, lastiter; ++ DiagonalList::Element *iter, *lastiter; + long top; + long w; + +@@ -946,21 +943,21 @@ void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPS + if (k - j > 1) { + pairs = &(dpstates[j][k].pairs); + +- iter = pairs->begin(); +- if ((!pairs->empty()) && (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->index1].p))) { ++ iter = pairs->front(); ++ if ((!pairs->is_empty()) && (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p))) { + lastiter = iter; +- while (iter != pairs->end()) { +- if (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->index1].p)) { ++ while (iter) { ++ if (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p)) { + lastiter = iter; +- iter++; ++ iter = iter->next(); + } else { + break; + } + } +- if (IsReflex(vertices[lastiter->index2].p, vertices[k].p, vertices[i].p)) { ++ if (IsReflex(vertices[lastiter->get().index2].p, vertices[k].p, vertices[i].p)) { + w++; + } else { +- top = lastiter->index2; ++ top = lastiter->get().index2; + } + } else { + w++; +@@ -981,11 +978,11 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + DiagonalList diagonals, diagonals2; + Diagonal diagonal, newdiagonal; + DiagonalList *pairs = NULL, *pairs2 = NULL; +- DiagonalList::iterator iter, iter2; ++ DiagonalList::Element *iter, *iter2; + int ret; + TPPLPoly newpoly; +- std::vector<long> indices; +- std::vector<long>::iterator iiter; ++ List<long> indices; ++ List<long>::Element *iiter; + bool ijreal, jkreal; + + n = poly->GetNumPoints(); +@@ -1110,35 +1107,35 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + newdiagonal.index1 = 0; + newdiagonal.index2 = n - 1; + diagonals.push_front(newdiagonal); +- while (!diagonals.empty()) { +- diagonal = *(diagonals.begin()); ++ while (!diagonals.is_empty()) { ++ diagonal = diagonals.front()->get(); + diagonals.pop_front(); + if ((diagonal.index2 - diagonal.index1) <= 1) { + continue; + } + pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); +- if (pairs->empty()) { ++ if (pairs->is_empty()) { + ret = 0; + break; + } + if (!vertices[diagonal.index1].isConvex) { +- iter = pairs->end(); ++ iter = pairs->back(); + iter--; +- j = iter->index2; ++ j = iter->get().index2; + newdiagonal.index1 = j; + newdiagonal.index2 = diagonal.index2; + diagonals.push_front(newdiagonal); + if ((j - diagonal.index1) > 1) { +- if (iter->index1 != iter->index2) { ++ if (iter->get().index1 != iter->get().index2) { + pairs2 = &(dpstates[diagonal.index1][j].pairs); + while (1) { +- if (pairs2->empty()) { ++ if (pairs2->is_empty()) { + ret = 0; + break; + } +- iter2 = pairs2->end(); ++ iter2 = pairs2->back(); + iter2--; +- if (iter->index1 != iter2->index1) { ++ if (iter->get().index1 != iter2->get().index1) { + pairs2->pop_back(); + } else { + break; +@@ -1153,21 +1150,21 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + diagonals.push_front(newdiagonal); + } + } else { +- iter = pairs->begin(); +- j = iter->index1; ++ iter = pairs->front(); ++ j = iter->get().index1; + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = j; + diagonals.push_front(newdiagonal); + if ((diagonal.index2 - j) > 1) { +- if (iter->index1 != iter->index2) { ++ if (iter->get().index1 != iter->get().index2) { + pairs2 = &(dpstates[j][diagonal.index2].pairs); + while (1) { +- if (pairs2->empty()) { ++ if (pairs2->is_empty()) { + ret = 0; + break; + } +- iter2 = pairs2->begin(); +- if (iter->index2 != iter2->index2) { ++ iter2 = pairs2->front(); ++ if (iter->get().index2 != iter2->get().index2) { + pairs2->pop_front(); + } else { + break; +@@ -1197,8 +1194,8 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + newdiagonal.index1 = 0; + newdiagonal.index2 = n - 1; + diagonals.push_front(newdiagonal); +- while (!diagonals.empty()) { +- diagonal = *(diagonals.begin()); ++ while (!diagonals.is_empty()) { ++ diagonal = diagonals.front()->get(); + diagonals.pop_front(); + if ((diagonal.index2 - diagonal.index1) <= 1) { + continue; +@@ -1210,8 +1207,8 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + indices.push_back(diagonal.index2); + diagonals2.push_front(diagonal); + +- while (!diagonals2.empty()) { +- diagonal = *(diagonals2.begin()); ++ while (!diagonals2.is_empty()) { ++ diagonal = diagonals2.front()->get(); + diagonals2.pop_front(); + if ((diagonal.index2 - diagonal.index1) <= 1) { + continue; +@@ -1220,16 +1217,16 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + jkreal = true; + pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); + if (!vertices[diagonal.index1].isConvex) { +- iter = pairs->end(); ++ iter = pairs->back(); + iter--; +- j = iter->index2; +- if (iter->index1 != iter->index2) { ++ j = iter->get().index2; ++ if (iter->get().index1 != iter->get().index2) { + ijreal = false; + } + } else { +- iter = pairs->begin(); +- j = iter->index1; +- if (iter->index1 != iter->index2) { ++ iter = pairs->front(); ++ j = iter->get().index1; ++ if (iter->get().index1 != iter->get().index2) { + jkreal = false; + } + } +@@ -1253,11 +1250,12 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + indices.push_back(j); + } + +- std::sort(indices.begin(), indices.end()); ++ //std::sort(indices.begin(), indices.end()); ++ indices.sort(); + newpoly.Init((long)indices.size()); + k = 0; +- for (iiter = indices.begin(); iiter != indices.end(); iiter++) { +- newpoly[k] = vertices[*iiter].p; ++ for (iiter = indices.front(); iiter != indices.back(); iiter = iiter->next()) { ++ newpoly[k] = vertices[iiter->get()].p; + k++; + } + parts->push_back(newpoly); +@@ -1281,7 +1279,7 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + // "Computational Geometry: Algorithms and Applications" + // by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. + int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys) { +- TPPLPolyList::iterator iter; ++ TPPLPolyList::Element *iter; + MonotoneVertex *vertices = NULL; + long i, numvertices, vindex, vindex2, newnumvertices, maxnumvertices; + long polystartindex, polyendindex; +@@ -1291,11 +1289,8 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + bool error = false; + + numvertices = 0; +- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) { +- if (!iter->Valid()) { +- return 0; +- } +- numvertices += iter->GetNumPoints(); ++ for (iter = inpolys->front(); iter; iter++) { ++ numvertices += iter->get().GetNumPoints(); + } + + maxnumvertices = numvertices * 3; +@@ -1303,8 +1298,8 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + newnumvertices = numvertices; + + polystartindex = 0; +- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) { +- poly = &(*iter); ++ for (iter = inpolys->front(); iter; iter++) { ++ poly = &(iter->get()); + polyendindex = polystartindex + poly->GetNumPoints() - 1; + for (i = 0; i < poly->GetNumPoints(); i++) { + vertices[i + polystartindex].p = poly->GetPoint(i); +@@ -1360,14 +1355,14 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + // Note that while set doesn't actually have to be implemented as + // a tree, complexity requirements for operations are the same as + // for the balanced binary search tree. +- std::set<ScanLineEdge> edgeTree; ++ Set<ScanLineEdge> edgeTree; + // Store iterators to the edge tree elements. + // This makes deleting existing edges much faster. +- std::set<ScanLineEdge>::iterator *edgeTreeIterators, edgeIter; +- edgeTreeIterators = new std::set<ScanLineEdge>::iterator[maxnumvertices]; +- std::pair<std::set<ScanLineEdge>::iterator, bool> edgeTreeRet; ++ Set<ScanLineEdge>::Element **edgeTreeIterators, *edgeIter; ++ edgeTreeIterators = new Set<ScanLineEdge>::Element *[maxnumvertices]; ++ //Pair<Set<ScanLineEdge>::iterator, bool> edgeTreeRet; + for (i = 0; i < numvertices; i++) { +- edgeTreeIterators[i] = edgeTree.end(); ++ edgeTreeIterators[i] = nullptr; + } + + // For each vertex. +@@ -1387,13 +1382,14 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + newedge.p1 = v->p; + newedge.p2 = vertices[v->next].p; + newedge.index = vindex; +- edgeTreeRet = edgeTree.insert(newedge); +- edgeTreeIterators[vindex] = edgeTreeRet.first; ++ //edgeTreeRet = edgeTree.insert(newedge); ++ //edgeTreeIterators[vindex] = edgeTreeRet.first; ++ edgeTreeIterators[vindex] = edgeTree.insert(newedge); + helpers[vindex] = vindex; + break; + + case TPPL_VERTEXTYPE_END: +- if (edgeTreeIterators[v->previous] == edgeTree.end()) { ++ if (edgeTreeIterators[v->previous] == edgeTree.back()) { + error = true; + break; + } +@@ -1412,29 +1408,30 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); +- if (edgeIter == edgeTree.begin()) { ++ if (edgeIter == edgeTree.front()) { + error = true; + break; + } + edgeIter--; + // Insert the diagonal connecting vi to helper(e_j) in D. +- AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->index], ++ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + vindex2 = newnumvertices - 2; + v2 = &(vertices[vindex2]); + // helper(e_j) in v_i. +- helpers[edgeIter->index] = vindex; ++ helpers[edgeIter->get().index] = vindex; + // Insert e_i in T and set helper(e_i) to v_i. + newedge.p1 = v2->p; + newedge.p2 = vertices[v2->next].p; + newedge.index = vindex2; +- edgeTreeRet = edgeTree.insert(newedge); +- edgeTreeIterators[vindex2] = edgeTreeRet.first; ++ //edgeTreeRet = edgeTree.insert(newedge); ++ //edgeTreeIterators[vindex2] = edgeTreeRet.first; ++ edgeTreeIterators[vindex2] = edgeTree.insert(newedge); + helpers[vindex2] = vindex2; + break; + + case TPPL_VERTEXTYPE_MERGE: +- if (edgeTreeIterators[v->previous] == edgeTree.end()) { ++ if (edgeTreeIterators[v->previous] == edgeTree.back()) { + error = true; + break; + } +@@ -1452,25 +1449,25 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); +- if (edgeIter == edgeTree.begin()) { ++ if (edgeIter == edgeTree.front()) { + error = true; + break; + } + edgeIter--; + // If helper(e_j) is a merge vertex. +- if (vertextypes[helpers[edgeIter->index]] == TPPL_VERTEXTYPE_MERGE) { ++ if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) { + // Insert the diagonal connecting v_i to helper(e_j) in D. +- AddDiagonal(vertices, &newnumvertices, vindex2, helpers[edgeIter->index], ++ AddDiagonal(vertices, &newnumvertices, vindex2, helpers[edgeIter->get().index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + // helper(e_j) <- v_i +- helpers[edgeIter->index] = vindex2; ++ helpers[edgeIter->get().index] = vindex2; + break; + + case TPPL_VERTEXTYPE_REGULAR: + // If the interior of P lies to the right of v_i. + if (Below(v->p, vertices[v->previous].p)) { +- if (edgeTreeIterators[v->previous] == edgeTree.end()) { ++ if (edgeTreeIterators[v->previous] == edgeTree.back()) { + error = true; + break; + } +@@ -1488,27 +1485,28 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + newedge.p1 = v2->p; + newedge.p2 = vertices[v2->next].p; + newedge.index = vindex2; +- edgeTreeRet = edgeTree.insert(newedge); +- edgeTreeIterators[vindex2] = edgeTreeRet.first; ++ //edgeTreeRet = edgeTree.insert(newedge); ++ //edgeTreeIterators[vindex2] = edgeTreeRet.first; ++ edgeTreeIterators[vindex2] = edgeTree.insert(newedge); + helpers[vindex2] = vindex; + } else { + // Search in T to find the edge e_j directly left of v_i. + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); +- if (edgeIter == edgeTree.begin()) { ++ if (edgeIter == edgeTree.front()) { + error = true; + break; + } +- edgeIter--; ++ edgeIter = edgeIter->prev(); + // If helper(e_j) is a merge vertex. +- if (vertextypes[helpers[edgeIter->index]] == TPPL_VERTEXTYPE_MERGE) { ++ if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) { + // Insert the diagonal connecting v_i to helper(e_j) in D. +- AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->index], ++ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + // helper(e_j) <- v_i. +- helpers[edgeIter->index] = vindex; ++ helpers[edgeIter->get().index] = vindex; + } + break; + } +@@ -1569,8 +1567,8 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto + + // Adds a diagonal to the doubly-connected list of vertices. + void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, +- TPPLVertexType *vertextypes, std::set<ScanLineEdge>::iterator *edgeTreeIterators, +- std::set<ScanLineEdge> *edgeTree, long *helpers) { ++ TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, ++ Set<ScanLineEdge> *edgeTree, long *helpers) { + long newindex1, newindex2; + + newindex1 = *numvertices; +@@ -1597,14 +1595,14 @@ void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, lon + vertextypes[newindex1] = vertextypes[index1]; + edgeTreeIterators[newindex1] = edgeTreeIterators[index1]; + helpers[newindex1] = helpers[index1]; +- if (edgeTreeIterators[newindex1] != edgeTree->end()) { +- edgeTreeIterators[newindex1]->index = newindex1; ++ if (edgeTreeIterators[newindex1] != edgeTree->back()) { ++ edgeTreeIterators[newindex1]->get().index = newindex1; + } + vertextypes[newindex2] = vertextypes[index2]; + edgeTreeIterators[newindex2] = edgeTreeIterators[index2]; + helpers[newindex2] = helpers[index2]; +- if (edgeTreeIterators[newindex2] != edgeTree->end()) { +- edgeTreeIterators[newindex2]->index = newindex2; ++ if (edgeTreeIterators[newindex2] != edgeTree->back()) { ++ edgeTreeIterators[newindex2]->get().index = newindex2; + } + } + +@@ -1830,13 +1828,13 @@ int TPPLPartition::TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles + + int TPPLPartition::Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles) { + TPPLPolyList monotone; +- TPPLPolyList::iterator iter; ++ TPPLPolyList::Element *iter; + + if (!MonotonePartition(inpolys, &monotone)) { + return 0; + } +- for (iter = monotone.begin(); iter != monotone.end(); iter++) { +- if (!TriangulateMonotone(&(*iter), triangles)) { ++ for (iter = monotone.front(); iter; iter = iter->next()) { ++ if (!TriangulateMonotone(&(iter->get()), triangles)) { + return 0; + } + } +diff --git a/thirdparty/misc/polypartition.h b/thirdparty/misc/polypartition.h +index f163f5d2173f..b2d905a3ef76 100644 +--- a/thirdparty/misc/polypartition.h ++++ b/thirdparty/misc/polypartition.h +@@ -24,8 +24,9 @@ + #ifndef POLYPARTITION_H + #define POLYPARTITION_H + +-#include <list> +-#include <set> ++#include "core/math/vector2.h" ++#include "core/templates/list.h" ++#include "core/templates/set.h" + + typedef double tppl_float; + +@@ -44,49 +45,7 @@ enum TPPLVertexType { + }; + + // 2D point structure. +-struct TPPLPoint { +- tppl_float x; +- tppl_float y; +- // User-specified vertex identifier. Note that this isn't used internally +- // by the library, but will be faithfully copied around. +- int id; +- +- TPPLPoint operator+(const TPPLPoint &p) const { +- TPPLPoint r; +- r.x = x + p.x; +- r.y = y + p.y; +- return r; +- } +- +- TPPLPoint operator-(const TPPLPoint &p) const { +- TPPLPoint r; +- r.x = x - p.x; +- r.y = y - p.y; +- return r; +- } +- +- TPPLPoint operator*(const tppl_float f) const { +- TPPLPoint r; +- r.x = x * f; +- r.y = y * f; +- return r; +- } +- +- TPPLPoint operator/(const tppl_float f) const { +- TPPLPoint r; +- r.x = x / f; +- r.y = y / f; +- return r; +- } +- +- bool operator==(const TPPLPoint &p) const { +- return ((x == p.x) && (y == p.y)); +- } +- +- bool operator!=(const TPPLPoint &p) const { +- return !((x == p.x) && (y == p.y)); +- } +-}; ++typedef Vector2 TPPLPoint; + + // Polygon implemented as an array of points with a "hole" flag. + class TPPLPoly { +@@ -168,9 +127,9 @@ class TPPLPoly { + }; + + #ifdef TPPL_ALLOCATOR +-typedef std::list<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList; ++typedef List<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList; + #else +-typedef std::list<TPPLPoly> TPPLPolyList; ++typedef List<TPPLPoly> TPPLPolyList; + #endif + + class TPPLPartition { +@@ -209,9 +168,9 @@ public: + }; + + #ifdef TPPL_ALLOCATOR +- typedef std::list<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList; ++ typedef List<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList; + #else +- typedef std::list<Diagonal> DiagonalList; ++ typedef List<Diagonal> DiagonalList; + #endif + + // Dynamic programming state for minimum-weight triangulation. +@@ -265,8 +224,8 @@ public: + // Helper functions for MonotonePartition. + bool Below(TPPLPoint &p1, TPPLPoint &p2); + void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, +- TPPLVertexType *vertextypes, std::set<ScanLineEdge>::iterator *edgeTreeIterators, +- std::set<ScanLineEdge> *edgeTree, long *helpers); ++ TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, ++ Set<ScanLineEdge> *edgeTree, long *helpers); + + // Triangulates a monotone polygon, used in Triangulate_MONO. + int TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles); diff --git a/thirdparty/misc/polypartition.cpp b/thirdparty/misc/polypartition.cpp new file mode 100644 index 0000000000..4f1b6dcb21 --- /dev/null +++ b/thirdparty/misc/polypartition.cpp @@ -0,0 +1,1849 @@ +/*************************************************************************/ +/* Copyright (c) 2011-2021 Ivan Fratric and contributors. */ +/* */ +/* 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 "polypartition.h" + +#include <algorithm> + +TPPLPoly::TPPLPoly() { + hole = false; + numpoints = 0; + points = NULL; +} + +TPPLPoly::~TPPLPoly() { + if (points) { + delete[] points; + } +} + +void TPPLPoly::Clear() { + if (points) { + delete[] points; + } + hole = false; + numpoints = 0; + points = NULL; +} + +void TPPLPoly::Init(long numpoints) { + Clear(); + this->numpoints = numpoints; + points = new TPPLPoint[numpoints]; +} + +void TPPLPoly::Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) { + Init(3); + points[0] = p1; + points[1] = p2; + points[2] = p3; +} + +TPPLPoly::TPPLPoly(const TPPLPoly &src) : + TPPLPoly() { + hole = src.hole; + numpoints = src.numpoints; + + if (numpoints > 0) { + points = new TPPLPoint[numpoints]; + memcpy(points, src.points, numpoints * sizeof(TPPLPoint)); + } +} + +TPPLPoly &TPPLPoly::operator=(const TPPLPoly &src) { + Clear(); + hole = src.hole; + numpoints = src.numpoints; + + if (numpoints > 0) { + points = new TPPLPoint[numpoints]; + memcpy(points, src.points, numpoints * sizeof(TPPLPoint)); + } + + return *this; +} + +TPPLOrientation TPPLPoly::GetOrientation() const { + long i1, i2; + tppl_float area = 0; + for (i1 = 0; i1 < numpoints; i1++) { + i2 = i1 + 1; + if (i2 == numpoints) { + i2 = 0; + } + area += points[i1].x * points[i2].y - points[i1].y * points[i2].x; + } + if (area > 0) { + return TPPL_ORIENTATION_CCW; + } + if (area < 0) { + return TPPL_ORIENTATION_CW; + } + return TPPL_ORIENTATION_NONE; +} + +void TPPLPoly::SetOrientation(TPPLOrientation orientation) { + TPPLOrientation polyorientation = GetOrientation(); + if (polyorientation != TPPL_ORIENTATION_NONE && polyorientation != orientation) { + Invert(); + } +} + +void TPPLPoly::Invert() { + std::reverse(points, points + numpoints); +} + +TPPLPartition::PartitionVertex::PartitionVertex() : + previous(NULL), next(NULL) { +} + +TPPLPoint TPPLPartition::Normalize(const TPPLPoint &p) { + TPPLPoint r; + tppl_float n = sqrt(p.x * p.x + p.y * p.y); + if (n != 0) { + r = p / n; + } else { + r.x = 0; + r.y = 0; + } + return r; +} + +tppl_float TPPLPartition::Distance(const TPPLPoint &p1, const TPPLPoint &p2) { + tppl_float dx, dy; + dx = p2.x - p1.x; + dy = p2.y - p1.y; + return (sqrt(dx * dx + dy * dy)); +} + +// Checks if two lines intersect. +int TPPLPartition::Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22) { + if ((p11.x == p21.x) && (p11.y == p21.y)) { + return 0; + } + if ((p11.x == p22.x) && (p11.y == p22.y)) { + return 0; + } + if ((p12.x == p21.x) && (p12.y == p21.y)) { + return 0; + } + if ((p12.x == p22.x) && (p12.y == p22.y)) { + return 0; + } + + TPPLPoint v1ort, v2ort, v; + tppl_float dot11, dot12, dot21, dot22; + + v1ort.x = p12.y - p11.y; + v1ort.y = p11.x - p12.x; + + v2ort.x = p22.y - p21.y; + v2ort.y = p21.x - p22.x; + + v = p21 - p11; + dot21 = v.x * v1ort.x + v.y * v1ort.y; + v = p22 - p11; + dot22 = v.x * v1ort.x + v.y * v1ort.y; + + v = p11 - p21; + dot11 = v.x * v2ort.x + v.y * v2ort.y; + v = p12 - p21; + dot12 = v.x * v2ort.x + v.y * v2ort.y; + + if (dot11 * dot12 > 0) { + return 0; + } + if (dot21 * dot22 > 0) { + return 0; + } + + return 1; +} + +// Removes holes from inpolys by merging them with non-holes. +int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { + TPPLPolyList polys; + TPPLPolyList::Element *holeiter, *polyiter, *iter, *iter2; + long i, i2, holepointindex, polypointindex; + TPPLPoint holepoint, polypoint, bestpolypoint; + TPPLPoint linep1, linep2; + TPPLPoint v1, v2; + TPPLPoly newpoly; + bool hasholes; + bool pointvisible; + bool pointfound; + + // Check for the trivial case of no holes. + hasholes = false; + for (iter = inpolys->front(); iter; iter = iter->next()) { + if (iter->get().IsHole()) { + hasholes = true; + break; + } + } + if (!hasholes) { + for (iter = inpolys->front(); iter; iter = iter->next()) { + outpolys->push_back(iter->get()); + } + return 1; + } + + polys = *inpolys; + + while (1) { + // Find the hole point with the largest x. + hasholes = false; + for (iter = polys.front(); iter; iter = iter->next()) { + if (!iter->get().IsHole()) { + continue; + } + + if (!hasholes) { + hasholes = true; + holeiter = iter; + holepointindex = 0; + } + + for (i = 0; i < iter->get().GetNumPoints(); i++) { + if (iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) { + holeiter = iter; + holepointindex = i; + } + } + } + if (!hasholes) { + break; + } + holepoint = holeiter->get().GetPoint(holepointindex); + + pointfound = false; + for (iter = polys.front(); iter; iter = iter->next()) { + if (iter->get().IsHole()) { + continue; + } + for (i = 0; i < iter->get().GetNumPoints(); i++) { + if (iter->get().GetPoint(i).x <= holepoint.x) { + continue; + } + if (!InCone(iter->get().GetPoint((i + iter->get().GetNumPoints() - 1) % (iter->get().GetNumPoints())), + iter->get().GetPoint(i), + iter->get().GetPoint((i + 1) % (iter->get().GetNumPoints())), + holepoint)) { + continue; + } + polypoint = iter->get().GetPoint(i); + if (pointfound) { + v1 = Normalize(polypoint - holepoint); + v2 = Normalize(bestpolypoint - holepoint); + if (v2.x > v1.x) { + continue; + } + } + pointvisible = true; + for (iter2 = polys.front(); iter2; iter2->next()) { + if (iter2->get().IsHole()) { + continue; + } + for (i2 = 0; i2 < iter2->get().GetNumPoints(); i2++) { + linep1 = iter2->get().GetPoint(i2); + linep2 = iter2->get().GetPoint((i2 + 1) % (iter2->get().GetNumPoints())); + if (Intersects(holepoint, polypoint, linep1, linep2)) { + pointvisible = false; + break; + } + } + if (!pointvisible) { + break; + } + } + if (pointvisible) { + pointfound = true; + bestpolypoint = polypoint; + polyiter = iter; + polypointindex = i; + } + } + } + + if (!pointfound) { + return 0; + } + + newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2); + i2 = 0; + for (i = 0; i <= polypointindex; i++) { + newpoly[i2] = polyiter->get().GetPoint(i); + i2++; + } + for (i = 0; i <= holeiter->get().GetNumPoints(); i++) { + newpoly[i2] = holeiter->get().GetPoint((i + holepointindex) % holeiter->get().GetNumPoints()); + i2++; + } + for (i = polypointindex; i < polyiter->get().GetNumPoints(); i++) { + newpoly[i2] = polyiter->get().GetPoint(i); + i2++; + } + + polys.erase(holeiter); + polys.erase(polyiter); + polys.push_back(newpoly); + } + + for (iter = polys.front(); iter; iter = iter->next()) { + outpolys->push_back(iter->get()); + } + + return 1; +} + +bool TPPLPartition::IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) { + tppl_float tmp; + tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y); + if (tmp > 0) { + return 1; + } else { + return 0; + } +} + +bool TPPLPartition::IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) { + tppl_float tmp; + tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y); + if (tmp < 0) { + return 1; + } else { + return 0; + } +} + +bool TPPLPartition::IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p) { + if (IsConvex(p1, p, p2)) { + return false; + } + if (IsConvex(p2, p, p3)) { + return false; + } + if (IsConvex(p3, p, p1)) { + return false; + } + return true; +} + +bool TPPLPartition::InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p) { + bool convex; + + convex = IsConvex(p1, p2, p3); + + if (convex) { + if (!IsConvex(p1, p2, p)) { + return false; + } + if (!IsConvex(p2, p3, p)) { + return false; + } + return true; + } else { + if (IsConvex(p1, p2, p)) { + return true; + } + if (IsConvex(p2, p3, p)) { + return true; + } + return false; + } +} + +bool TPPLPartition::InCone(PartitionVertex *v, TPPLPoint &p) { + TPPLPoint p1, p2, p3; + + p1 = v->previous->p; + p2 = v->p; + p3 = v->next->p; + + return InCone(p1, p2, p3, p); +} + +void TPPLPartition::UpdateVertexReflexity(PartitionVertex *v) { + PartitionVertex *v1 = NULL, *v3 = NULL; + v1 = v->previous; + v3 = v->next; + v->isConvex = !IsReflex(v1->p, v->p, v3->p); +} + +void TPPLPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) { + long i; + PartitionVertex *v1 = NULL, *v3 = NULL; + TPPLPoint vec1, vec3; + + v1 = v->previous; + v3 = v->next; + + v->isConvex = IsConvex(v1->p, v->p, v3->p); + + vec1 = Normalize(v1->p - v->p); + vec3 = Normalize(v3->p - v->p); + v->angle = vec1.x * vec3.x + vec1.y * vec3.y; + + if (v->isConvex) { + v->isEar = true; + for (i = 0; i < numvertices; i++) { + if ((vertices[i].p.x == v->p.x) && (vertices[i].p.y == v->p.y)) { + continue; + } + if ((vertices[i].p.x == v1->p.x) && (vertices[i].p.y == v1->p.y)) { + continue; + } + if ((vertices[i].p.x == v3->p.x) && (vertices[i].p.y == v3->p.y)) { + continue; + } + if (IsInside(v1->p, v->p, v3->p, vertices[i].p)) { + v->isEar = false; + break; + } + } + } else { + v->isEar = false; + } +} + +// Triangulation by ear removal. +int TPPLPartition::Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles) { + if (!poly->Valid()) { + return 0; + } + + long numvertices; + PartitionVertex *vertices = NULL; + PartitionVertex *ear = NULL; + TPPLPoly triangle; + long i, j; + bool earfound; + + if (poly->GetNumPoints() < 3) { + return 0; + } + if (poly->GetNumPoints() == 3) { + triangles->push_back(*poly); + return 1; + } + + numvertices = poly->GetNumPoints(); + + vertices = new PartitionVertex[numvertices]; + for (i = 0; i < numvertices; i++) { + vertices[i].isActive = true; + vertices[i].p = poly->GetPoint(i); + if (i == (numvertices - 1)) { + vertices[i].next = &(vertices[0]); + } else { + vertices[i].next = &(vertices[i + 1]); + } + if (i == 0) { + vertices[i].previous = &(vertices[numvertices - 1]); + } else { + vertices[i].previous = &(vertices[i - 1]); + } + } + for (i = 0; i < numvertices; i++) { + UpdateVertex(&vertices[i], vertices, numvertices); + } + + for (i = 0; i < numvertices - 3; i++) { + earfound = false; + // Find the most extruded ear. + for (j = 0; j < numvertices; j++) { + if (!vertices[j].isActive) { + continue; + } + if (!vertices[j].isEar) { + continue; + } + if (!earfound) { + earfound = true; + ear = &(vertices[j]); + } else { + if (vertices[j].angle > ear->angle) { + ear = &(vertices[j]); + } + } + } + if (!earfound) { + delete[] vertices; + return 0; + } + + triangle.Triangle(ear->previous->p, ear->p, ear->next->p); + triangles->push_back(triangle); + + ear->isActive = false; + ear->previous->next = ear->next; + ear->next->previous = ear->previous; + + if (i == numvertices - 4) { + break; + } + + UpdateVertex(ear->previous, vertices, numvertices); + UpdateVertex(ear->next, vertices, numvertices); + } + for (i = 0; i < numvertices; i++) { + if (vertices[i].isActive) { + triangle.Triangle(vertices[i].previous->p, vertices[i].p, vertices[i].next->p); + triangles->push_back(triangle); + break; + } + } + + delete[] vertices; + + return 1; +} + +int TPPLPartition::Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles) { + TPPLPolyList outpolys; + TPPLPolyList::Element *iter; + + if (!RemoveHoles(inpolys, &outpolys)) { + return 0; + } + for (iter = outpolys.front(); iter; iter = iter->next()) { + if (!Triangulate_EC(&(iter->get()), triangles)) { + return 0; + } + } + return 1; +} + +int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) { + if (!poly->Valid()) { + return 0; + } + + TPPLPolyList triangles; + TPPLPolyList::Element *iter1, *iter2; + TPPLPoly *poly1 = NULL, *poly2 = NULL; + TPPLPoly newpoly; + TPPLPoint d1, d2, p1, p2, p3; + long i11, i12, i21, i22, i13, i23, j, k; + bool isdiagonal; + long numreflex; + + // Check if the poly is already convex. + numreflex = 0; + for (i11 = 0; i11 < poly->GetNumPoints(); i11++) { + if (i11 == 0) { + i12 = poly->GetNumPoints() - 1; + } else { + i12 = i11 - 1; + } + if (i11 == (poly->GetNumPoints() - 1)) { + i13 = 0; + } else { + i13 = i11 + 1; + } + if (IsReflex(poly->GetPoint(i12), poly->GetPoint(i11), poly->GetPoint(i13))) { + numreflex = 1; + break; + } + } + if (numreflex == 0) { + parts->push_back(*poly); + return 1; + } + + if (!Triangulate_EC(poly, &triangles)) { + return 0; + } + + for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) { + poly1 = &(iter1->get()); + for (i11 = 0; i11 < poly1->GetNumPoints(); i11++) { + d1 = poly1->GetPoint(i11); + i12 = (i11 + 1) % (poly1->GetNumPoints()); + d2 = poly1->GetPoint(i12); + + isdiagonal = false; + for (iter2 = iter1; iter2; iter2 = iter2->next()) { + if (iter1 == iter2) { + continue; + } + poly2 = &(iter2->get()); + + for (i21 = 0; i21 < poly2->GetNumPoints(); i21++) { + if ((d2.x != poly2->GetPoint(i21).x) || (d2.y != poly2->GetPoint(i21).y)) { + continue; + } + i22 = (i21 + 1) % (poly2->GetNumPoints()); + if ((d1.x != poly2->GetPoint(i22).x) || (d1.y != poly2->GetPoint(i22).y)) { + continue; + } + isdiagonal = true; + break; + } + if (isdiagonal) { + break; + } + } + + if (!isdiagonal) { + continue; + } + + p2 = poly1->GetPoint(i11); + if (i11 == 0) { + i13 = poly1->GetNumPoints() - 1; + } else { + i13 = i11 - 1; + } + p1 = poly1->GetPoint(i13); + if (i22 == (poly2->GetNumPoints() - 1)) { + i23 = 0; + } else { + i23 = i22 + 1; + } + p3 = poly2->GetPoint(i23); + + if (!IsConvex(p1, p2, p3)) { + continue; + } + + p2 = poly1->GetPoint(i12); + if (i12 == (poly1->GetNumPoints() - 1)) { + i13 = 0; + } else { + i13 = i12 + 1; + } + p3 = poly1->GetPoint(i13); + if (i21 == 0) { + i23 = poly2->GetNumPoints() - 1; + } else { + i23 = i21 - 1; + } + p1 = poly2->GetPoint(i23); + + if (!IsConvex(p1, p2, p3)) { + continue; + } + + newpoly.Init(poly1->GetNumPoints() + poly2->GetNumPoints() - 2); + k = 0; + for (j = i12; j != i11; j = (j + 1) % (poly1->GetNumPoints())) { + newpoly[k] = poly1->GetPoint(j); + k++; + } + for (j = i22; j != i21; j = (j + 1) % (poly2->GetNumPoints())) { + newpoly[k] = poly2->GetPoint(j); + k++; + } + + triangles.erase(iter2); + iter1->get() = newpoly; + poly1 = &(iter1->get()); + i11 = -1; + + continue; + } + } + + for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) { + parts->push_back(iter1->get()); + } + + return 1; +} + +int TPPLPartition::ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts) { + TPPLPolyList outpolys; + TPPLPolyList::Element *iter; + + if (!RemoveHoles(inpolys, &outpolys)) { + return 0; + } + for (iter = outpolys.front(); iter; iter = iter->next()) { + if (!ConvexPartition_HM(&(iter->get()), parts)) { + return 0; + } + } + return 1; +} + +// Minimum-weight polygon triangulation by dynamic programming. +// Time complexity: O(n^3) +// Space complexity: O(n^2) +int TPPLPartition::Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles) { + if (!poly->Valid()) { + return 0; + } + + long i, j, k, gap, n; + DPState **dpstates = NULL; + TPPLPoint p1, p2, p3, p4; + long bestvertex; + tppl_float weight, minweight, d1, d2; + Diagonal diagonal, newdiagonal; + DiagonalList diagonals; + TPPLPoly triangle; + int ret = 1; + + n = poly->GetNumPoints(); + dpstates = new DPState *[n]; + for (i = 1; i < n; i++) { + dpstates[i] = new DPState[i]; + } + + // Initialize states and visibility. + for (i = 0; i < (n - 1); i++) { + p1 = poly->GetPoint(i); + for (j = i + 1; j < n; j++) { + dpstates[j][i].visible = true; + dpstates[j][i].weight = 0; + dpstates[j][i].bestvertex = -1; + if (j != (i + 1)) { + p2 = poly->GetPoint(j); + + // Visibility check. + if (i == 0) { + p3 = poly->GetPoint(n - 1); + } else { + p3 = poly->GetPoint(i - 1); + } + if (i == (n - 1)) { + p4 = poly->GetPoint(0); + } else { + p4 = poly->GetPoint(i + 1); + } + if (!InCone(p3, p1, p4, p2)) { + dpstates[j][i].visible = false; + continue; + } + + if (j == 0) { + p3 = poly->GetPoint(n - 1); + } else { + p3 = poly->GetPoint(j - 1); + } + if (j == (n - 1)) { + p4 = poly->GetPoint(0); + } else { + p4 = poly->GetPoint(j + 1); + } + if (!InCone(p3, p2, p4, p1)) { + dpstates[j][i].visible = false; + continue; + } + + for (k = 0; k < n; k++) { + p3 = poly->GetPoint(k); + if (k == (n - 1)) { + p4 = poly->GetPoint(0); + } else { + p4 = poly->GetPoint(k + 1); + } + if (Intersects(p1, p2, p3, p4)) { + dpstates[j][i].visible = false; + break; + } + } + } + } + } + dpstates[n - 1][0].visible = true; + dpstates[n - 1][0].weight = 0; + dpstates[n - 1][0].bestvertex = -1; + + for (gap = 2; gap < n; gap++) { + for (i = 0; i < (n - gap); i++) { + j = i + gap; + if (!dpstates[j][i].visible) { + continue; + } + bestvertex = -1; + for (k = (i + 1); k < j; k++) { + if (!dpstates[k][i].visible) { + continue; + } + if (!dpstates[j][k].visible) { + continue; + } + + if (k <= (i + 1)) { + d1 = 0; + } else { + d1 = Distance(poly->GetPoint(i), poly->GetPoint(k)); + } + if (j <= (k + 1)) { + d2 = 0; + } else { + d2 = Distance(poly->GetPoint(k), poly->GetPoint(j)); + } + + weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2; + + if ((bestvertex == -1) || (weight < minweight)) { + bestvertex = k; + minweight = weight; + } + } + if (bestvertex == -1) { + for (i = 1; i < n; i++) { + delete[] dpstates[i]; + } + delete[] dpstates; + + return 0; + } + + dpstates[j][i].bestvertex = bestvertex; + dpstates[j][i].weight = minweight; + } + } + + newdiagonal.index1 = 0; + newdiagonal.index2 = n - 1; + diagonals.push_back(newdiagonal); + while (!diagonals.is_empty()) { + diagonal = diagonals.front()->get(); + diagonals.pop_front(); + bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex; + if (bestvertex == -1) { + ret = 0; + break; + } + triangle.Triangle(poly->GetPoint(diagonal.index1), poly->GetPoint(bestvertex), poly->GetPoint(diagonal.index2)); + triangles->push_back(triangle); + if (bestvertex > (diagonal.index1 + 1)) { + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = bestvertex; + diagonals.push_back(newdiagonal); + } + if (diagonal.index2 > (bestvertex + 1)) { + newdiagonal.index1 = bestvertex; + newdiagonal.index2 = diagonal.index2; + diagonals.push_back(newdiagonal); + } + } + + for (i = 1; i < n; i++) { + delete[] dpstates[i]; + } + delete[] dpstates; + + return ret; +} + +void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) { + Diagonal newdiagonal; + DiagonalList *pairs = NULL; + long w2; + + w2 = dpstates[a][b].weight; + if (w > w2) { + return; + } + + pairs = &(dpstates[a][b].pairs); + newdiagonal.index1 = i; + newdiagonal.index2 = j; + + if (w < w2) { + pairs->clear(); + pairs->push_front(newdiagonal); + dpstates[a][b].weight = w; + } else { + if ((!pairs->is_empty()) && (i <= pairs->front()->get().index1)) { + return; + } + while ((!pairs->is_empty()) && (pairs->front()->get().index2 >= j)) { + pairs->pop_front(); + } + pairs->push_front(newdiagonal); + } +} + +void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { + DiagonalList *pairs = NULL; + DiagonalList::Element *iter, *lastiter; + long top; + long w; + + if (!dpstates[i][j].visible) { + return; + } + top = j; + w = dpstates[i][j].weight; + if (k - j > 1) { + if (!dpstates[j][k].visible) { + return; + } + w += dpstates[j][k].weight + 1; + } + if (j - i > 1) { + pairs = &(dpstates[i][j].pairs); + iter = pairs->back(); + lastiter = pairs->back(); + while (iter != pairs->front()) { + iter--; + if (!IsReflex(vertices[iter->get().index2].p, vertices[j].p, vertices[k].p)) { + lastiter = iter; + } else { + break; + } + } + if (lastiter == pairs->back()) { + w++; + } else { + if (IsReflex(vertices[k].p, vertices[i].p, vertices[lastiter->get().index1].p)) { + w++; + } else { + top = lastiter->get().index1; + } + } + } + UpdateState(i, k, w, top, j, dpstates); +} + +void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { + DiagonalList *pairs = NULL; + DiagonalList::Element *iter, *lastiter; + long top; + long w; + + if (!dpstates[j][k].visible) { + return; + } + top = j; + w = dpstates[j][k].weight; + + if (j - i > 1) { + if (!dpstates[i][j].visible) { + return; + } + w += dpstates[i][j].weight + 1; + } + if (k - j > 1) { + pairs = &(dpstates[j][k].pairs); + + iter = pairs->front(); + if ((!pairs->is_empty()) && (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p))) { + lastiter = iter; + while (iter) { + if (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p)) { + lastiter = iter; + iter = iter->next(); + } else { + break; + } + } + if (IsReflex(vertices[lastiter->get().index2].p, vertices[k].p, vertices[i].p)) { + w++; + } else { + top = lastiter->get().index2; + } + } else { + w++; + } + } + UpdateState(i, k, w, j, top, dpstates); +} + +int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { + if (!poly->Valid()) { + return 0; + } + + TPPLPoint p1, p2, p3, p4; + PartitionVertex *vertices = NULL; + DPState2 **dpstates = NULL; + long i, j, k, n, gap; + DiagonalList diagonals, diagonals2; + Diagonal diagonal, newdiagonal; + DiagonalList *pairs = NULL, *pairs2 = NULL; + DiagonalList::Element *iter, *iter2; + int ret; + TPPLPoly newpoly; + List<long> indices; + List<long>::Element *iiter; + bool ijreal, jkreal; + + n = poly->GetNumPoints(); + vertices = new PartitionVertex[n]; + + dpstates = new DPState2 *[n]; + for (i = 0; i < n; i++) { + dpstates[i] = new DPState2[n]; + } + + // Initialize vertex information. + for (i = 0; i < n; i++) { + vertices[i].p = poly->GetPoint(i); + vertices[i].isActive = true; + if (i == 0) { + vertices[i].previous = &(vertices[n - 1]); + } else { + vertices[i].previous = &(vertices[i - 1]); + } + if (i == (poly->GetNumPoints() - 1)) { + vertices[i].next = &(vertices[0]); + } else { + vertices[i].next = &(vertices[i + 1]); + } + } + for (i = 1; i < n; i++) { + UpdateVertexReflexity(&(vertices[i])); + } + + // Initialize states and visibility. + for (i = 0; i < (n - 1); i++) { + p1 = poly->GetPoint(i); + for (j = i + 1; j < n; j++) { + dpstates[i][j].visible = true; + if (j == i + 1) { + dpstates[i][j].weight = 0; + } else { + dpstates[i][j].weight = 2147483647; + } + if (j != (i + 1)) { + p2 = poly->GetPoint(j); + + // Visibility check. + if (!InCone(&vertices[i], p2)) { + dpstates[i][j].visible = false; + continue; + } + if (!InCone(&vertices[j], p1)) { + dpstates[i][j].visible = false; + continue; + } + + for (k = 0; k < n; k++) { + p3 = poly->GetPoint(k); + if (k == (n - 1)) { + p4 = poly->GetPoint(0); + } else { + p4 = poly->GetPoint(k + 1); + } + if (Intersects(p1, p2, p3, p4)) { + dpstates[i][j].visible = false; + break; + } + } + } + } + } + for (i = 0; i < (n - 2); i++) { + j = i + 2; + if (dpstates[i][j].visible) { + dpstates[i][j].weight = 0; + newdiagonal.index1 = i + 1; + newdiagonal.index2 = i + 1; + dpstates[i][j].pairs.push_back(newdiagonal); + } + } + + dpstates[0][n - 1].visible = true; + vertices[0].isConvex = false; // By convention. + + for (gap = 3; gap < n; gap++) { + for (i = 0; i < n - gap; i++) { + if (vertices[i].isConvex) { + continue; + } + k = i + gap; + if (dpstates[i][k].visible) { + if (!vertices[k].isConvex) { + for (j = i + 1; j < k; j++) { + TypeA(i, j, k, vertices, dpstates); + } + } else { + for (j = i + 1; j < (k - 1); j++) { + if (vertices[j].isConvex) { + continue; + } + TypeA(i, j, k, vertices, dpstates); + } + TypeA(i, k - 1, k, vertices, dpstates); + } + } + } + for (k = gap; k < n; k++) { + if (vertices[k].isConvex) { + continue; + } + i = k - gap; + if ((vertices[i].isConvex) && (dpstates[i][k].visible)) { + TypeB(i, i + 1, k, vertices, dpstates); + for (j = i + 2; j < k; j++) { + if (vertices[j].isConvex) { + continue; + } + TypeB(i, j, k, vertices, dpstates); + } + } + } + } + + // Recover solution. + ret = 1; + newdiagonal.index1 = 0; + newdiagonal.index2 = n - 1; + diagonals.push_front(newdiagonal); + while (!diagonals.is_empty()) { + diagonal = diagonals.front()->get(); + diagonals.pop_front(); + if ((diagonal.index2 - diagonal.index1) <= 1) { + continue; + } + pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); + if (pairs->is_empty()) { + ret = 0; + break; + } + if (!vertices[diagonal.index1].isConvex) { + iter = pairs->back(); + iter--; + j = iter->get().index2; + newdiagonal.index1 = j; + newdiagonal.index2 = diagonal.index2; + diagonals.push_front(newdiagonal); + if ((j - diagonal.index1) > 1) { + if (iter->get().index1 != iter->get().index2) { + pairs2 = &(dpstates[diagonal.index1][j].pairs); + while (1) { + if (pairs2->is_empty()) { + ret = 0; + break; + } + iter2 = pairs2->back(); + iter2--; + if (iter->get().index1 != iter2->get().index1) { + pairs2->pop_back(); + } else { + break; + } + } + if (ret == 0) { + break; + } + } + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = j; + diagonals.push_front(newdiagonal); + } + } else { + iter = pairs->front(); + j = iter->get().index1; + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = j; + diagonals.push_front(newdiagonal); + if ((diagonal.index2 - j) > 1) { + if (iter->get().index1 != iter->get().index2) { + pairs2 = &(dpstates[j][diagonal.index2].pairs); + while (1) { + if (pairs2->is_empty()) { + ret = 0; + break; + } + iter2 = pairs2->front(); + if (iter->get().index2 != iter2->get().index2) { + pairs2->pop_front(); + } else { + break; + } + } + if (ret == 0) { + break; + } + } + newdiagonal.index1 = j; + newdiagonal.index2 = diagonal.index2; + diagonals.push_front(newdiagonal); + } + } + } + + if (ret == 0) { + for (i = 0; i < n; i++) { + delete[] dpstates[i]; + } + delete[] dpstates; + delete[] vertices; + + return ret; + } + + newdiagonal.index1 = 0; + newdiagonal.index2 = n - 1; + diagonals.push_front(newdiagonal); + while (!diagonals.is_empty()) { + diagonal = diagonals.front()->get(); + diagonals.pop_front(); + if ((diagonal.index2 - diagonal.index1) <= 1) { + continue; + } + + indices.clear(); + diagonals2.clear(); + indices.push_back(diagonal.index1); + indices.push_back(diagonal.index2); + diagonals2.push_front(diagonal); + + while (!diagonals2.is_empty()) { + diagonal = diagonals2.front()->get(); + diagonals2.pop_front(); + if ((diagonal.index2 - diagonal.index1) <= 1) { + continue; + } + ijreal = true; + jkreal = true; + pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); + if (!vertices[diagonal.index1].isConvex) { + iter = pairs->back(); + iter--; + j = iter->get().index2; + if (iter->get().index1 != iter->get().index2) { + ijreal = false; + } + } else { + iter = pairs->front(); + j = iter->get().index1; + if (iter->get().index1 != iter->get().index2) { + jkreal = false; + } + } + + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = j; + if (ijreal) { + diagonals.push_back(newdiagonal); + } else { + diagonals2.push_back(newdiagonal); + } + + newdiagonal.index1 = j; + newdiagonal.index2 = diagonal.index2; + if (jkreal) { + diagonals.push_back(newdiagonal); + } else { + diagonals2.push_back(newdiagonal); + } + + indices.push_back(j); + } + + //std::sort(indices.begin(), indices.end()); + indices.sort(); + newpoly.Init((long)indices.size()); + k = 0; + for (iiter = indices.front(); iiter != indices.back(); iiter = iiter->next()) { + newpoly[k] = vertices[iiter->get()].p; + k++; + } + parts->push_back(newpoly); + } + + for (i = 0; i < n; i++) { + delete[] dpstates[i]; + } + delete[] dpstates; + delete[] vertices; + + return ret; +} + +// Creates a monotone partition of a list of polygons that +// can contain holes. Triangulates a set of polygons by +// first partitioning them into monotone polygons. +// Time complexity: O(n*log(n)), n is the number of vertices. +// Space complexity: O(n) +// The algorithm used here is outlined in the book +// "Computational Geometry: Algorithms and Applications" +// by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. +int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys) { + TPPLPolyList::Element *iter; + MonotoneVertex *vertices = NULL; + long i, numvertices, vindex, vindex2, newnumvertices, maxnumvertices; + long polystartindex, polyendindex; + TPPLPoly *poly = NULL; + MonotoneVertex *v = NULL, *v2 = NULL, *vprev = NULL, *vnext = NULL; + ScanLineEdge newedge; + bool error = false; + + numvertices = 0; + for (iter = inpolys->front(); iter; iter++) { + numvertices += iter->get().GetNumPoints(); + } + + maxnumvertices = numvertices * 3; + vertices = new MonotoneVertex[maxnumvertices]; + newnumvertices = numvertices; + + polystartindex = 0; + for (iter = inpolys->front(); iter; iter++) { + poly = &(iter->get()); + polyendindex = polystartindex + poly->GetNumPoints() - 1; + for (i = 0; i < poly->GetNumPoints(); i++) { + vertices[i + polystartindex].p = poly->GetPoint(i); + if (i == 0) { + vertices[i + polystartindex].previous = polyendindex; + } else { + vertices[i + polystartindex].previous = i + polystartindex - 1; + } + if (i == (poly->GetNumPoints() - 1)) { + vertices[i + polystartindex].next = polystartindex; + } else { + vertices[i + polystartindex].next = i + polystartindex + 1; + } + } + polystartindex = polyendindex + 1; + } + + // Construct the priority queue. + long *priority = new long[numvertices]; + for (i = 0; i < numvertices; i++) { + priority[i] = i; + } + std::sort(priority, &(priority[numvertices]), VertexSorter(vertices)); + + // Determine vertex types. + TPPLVertexType *vertextypes = new TPPLVertexType[maxnumvertices]; + for (i = 0; i < numvertices; i++) { + v = &(vertices[i]); + vprev = &(vertices[v->previous]); + vnext = &(vertices[v->next]); + + if (Below(vprev->p, v->p) && Below(vnext->p, v->p)) { + if (IsConvex(vnext->p, vprev->p, v->p)) { + vertextypes[i] = TPPL_VERTEXTYPE_START; + } else { + vertextypes[i] = TPPL_VERTEXTYPE_SPLIT; + } + } else if (Below(v->p, vprev->p) && Below(v->p, vnext->p)) { + if (IsConvex(vnext->p, vprev->p, v->p)) { + vertextypes[i] = TPPL_VERTEXTYPE_END; + } else { + vertextypes[i] = TPPL_VERTEXTYPE_MERGE; + } + } else { + vertextypes[i] = TPPL_VERTEXTYPE_REGULAR; + } + } + + // Helpers. + long *helpers = new long[maxnumvertices]; + + // Binary search tree that holds edges intersecting the scanline. + // Note that while set doesn't actually have to be implemented as + // a tree, complexity requirements for operations are the same as + // for the balanced binary search tree. + Set<ScanLineEdge> edgeTree; + // Store iterators to the edge tree elements. + // This makes deleting existing edges much faster. + Set<ScanLineEdge>::Element **edgeTreeIterators, *edgeIter; + edgeTreeIterators = new Set<ScanLineEdge>::Element *[maxnumvertices]; + //Pair<Set<ScanLineEdge>::iterator, bool> edgeTreeRet; + for (i = 0; i < numvertices; i++) { + edgeTreeIterators[i] = nullptr; + } + + // For each vertex. + for (i = 0; i < numvertices; i++) { + vindex = priority[i]; + v = &(vertices[vindex]); + vindex2 = vindex; + v2 = v; + + // Depending on the vertex type, do the appropriate action. + // Comments in the following sections are copied from + // "Computational Geometry: Algorithms and Applications". + // Notation: e_i = e subscript i, v_i = v subscript i, etc. + switch (vertextypes[vindex]) { + case TPPL_VERTEXTYPE_START: + // Insert e_i in T and set helper(e_i) to v_i. + newedge.p1 = v->p; + newedge.p2 = vertices[v->next].p; + newedge.index = vindex; + //edgeTreeRet = edgeTree.insert(newedge); + //edgeTreeIterators[vindex] = edgeTreeRet.first; + edgeTreeIterators[vindex] = edgeTree.insert(newedge); + helpers[vindex] = vindex; + break; + + case TPPL_VERTEXTYPE_END: + if (edgeTreeIterators[v->previous] == edgeTree.back()) { + error = true; + break; + } + // If helper(e_i - 1) is a merge vertex + if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) { + // Insert the diagonal connecting vi to helper(e_i - 1) in D. + AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + // Delete e_i - 1 from T + edgeTree.erase(edgeTreeIterators[v->previous]); + break; + + case TPPL_VERTEXTYPE_SPLIT: + // Search in T to find the edge e_j directly left of v_i. + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); + if (edgeIter == edgeTree.front()) { + error = true; + break; + } + edgeIter--; + // Insert the diagonal connecting vi to helper(e_j) in D. + AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + vindex2 = newnumvertices - 2; + v2 = &(vertices[vindex2]); + // helper(e_j) in v_i. + helpers[edgeIter->get().index] = vindex; + // Insert e_i in T and set helper(e_i) to v_i. + newedge.p1 = v2->p; + newedge.p2 = vertices[v2->next].p; + newedge.index = vindex2; + //edgeTreeRet = edgeTree.insert(newedge); + //edgeTreeIterators[vindex2] = edgeTreeRet.first; + edgeTreeIterators[vindex2] = edgeTree.insert(newedge); + helpers[vindex2] = vindex2; + break; + + case TPPL_VERTEXTYPE_MERGE: + if (edgeTreeIterators[v->previous] == edgeTree.back()) { + error = true; + break; + } + // if helper(e_i - 1) is a merge vertex + if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) { + // Insert the diagonal connecting vi to helper(e_i - 1) in D. + AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + vindex2 = newnumvertices - 2; + v2 = &(vertices[vindex2]); + } + // Delete e_i - 1 from T. + edgeTree.erase(edgeTreeIterators[v->previous]); + // Search in T to find the edge e_j directly left of v_i. + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); + if (edgeIter == edgeTree.front()) { + error = true; + break; + } + edgeIter--; + // If helper(e_j) is a merge vertex. + if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) { + // Insert the diagonal connecting v_i to helper(e_j) in D. + AddDiagonal(vertices, &newnumvertices, vindex2, helpers[edgeIter->get().index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + // helper(e_j) <- v_i + helpers[edgeIter->get().index] = vindex2; + break; + + case TPPL_VERTEXTYPE_REGULAR: + // If the interior of P lies to the right of v_i. + if (Below(v->p, vertices[v->previous].p)) { + if (edgeTreeIterators[v->previous] == edgeTree.back()) { + error = true; + break; + } + // If helper(e_i - 1) is a merge vertex. + if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) { + // Insert the diagonal connecting v_i to helper(e_i - 1) in D. + AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + vindex2 = newnumvertices - 2; + v2 = &(vertices[vindex2]); + } + // Delete e_i - 1 from T. + edgeTree.erase(edgeTreeIterators[v->previous]); + // Insert e_i in T and set helper(e_i) to v_i. + newedge.p1 = v2->p; + newedge.p2 = vertices[v2->next].p; + newedge.index = vindex2; + //edgeTreeRet = edgeTree.insert(newedge); + //edgeTreeIterators[vindex2] = edgeTreeRet.first; + edgeTreeIterators[vindex2] = edgeTree.insert(newedge); + helpers[vindex2] = vindex; + } else { + // Search in T to find the edge e_j directly left of v_i. + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); + if (edgeIter == edgeTree.front()) { + error = true; + break; + } + edgeIter = edgeIter->prev(); + // If helper(e_j) is a merge vertex. + if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) { + // Insert the diagonal connecting v_i to helper(e_j) in D. + AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + // helper(e_j) <- v_i. + helpers[edgeIter->get().index] = vindex; + } + break; + } + + if (error) + break; + } + + char *used = new char[newnumvertices]; + memset(used, 0, newnumvertices * sizeof(char)); + + if (!error) { + // Return result. + long size; + TPPLPoly mpoly; + for (i = 0; i < newnumvertices; i++) { + if (used[i]) { + continue; + } + v = &(vertices[i]); + vnext = &(vertices[v->next]); + size = 1; + while (vnext != v) { + vnext = &(vertices[vnext->next]); + size++; + } + mpoly.Init(size); + v = &(vertices[i]); + mpoly[0] = v->p; + vnext = &(vertices[v->next]); + size = 1; + used[i] = 1; + used[v->next] = 1; + while (vnext != v) { + mpoly[size] = vnext->p; + used[vnext->next] = 1; + vnext = &(vertices[vnext->next]); + size++; + } + monotonePolys->push_back(mpoly); + } + } + + // Cleanup. + delete[] vertices; + delete[] priority; + delete[] vertextypes; + delete[] edgeTreeIterators; + delete[] helpers; + delete[] used; + + if (error) { + return 0; + } else { + return 1; + } +} + +// Adds a diagonal to the doubly-connected list of vertices. +void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, + TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, + Set<ScanLineEdge> *edgeTree, long *helpers) { + long newindex1, newindex2; + + newindex1 = *numvertices; + (*numvertices)++; + newindex2 = *numvertices; + (*numvertices)++; + + vertices[newindex1].p = vertices[index1].p; + vertices[newindex2].p = vertices[index2].p; + + vertices[newindex2].next = vertices[index2].next; + vertices[newindex1].next = vertices[index1].next; + + vertices[vertices[index2].next].previous = newindex2; + vertices[vertices[index1].next].previous = newindex1; + + vertices[index1].next = newindex2; + vertices[newindex2].previous = index1; + + vertices[index2].next = newindex1; + vertices[newindex1].previous = index2; + + // Update all relevant structures. + vertextypes[newindex1] = vertextypes[index1]; + edgeTreeIterators[newindex1] = edgeTreeIterators[index1]; + helpers[newindex1] = helpers[index1]; + if (edgeTreeIterators[newindex1] != edgeTree->back()) { + edgeTreeIterators[newindex1]->get().index = newindex1; + } + vertextypes[newindex2] = vertextypes[index2]; + edgeTreeIterators[newindex2] = edgeTreeIterators[index2]; + helpers[newindex2] = helpers[index2]; + if (edgeTreeIterators[newindex2] != edgeTree->back()) { + edgeTreeIterators[newindex2]->get().index = newindex2; + } +} + +bool TPPLPartition::Below(TPPLPoint &p1, TPPLPoint &p2) { + if (p1.y < p2.y) { + return true; + } else if (p1.y == p2.y) { + if (p1.x < p2.x) { + return true; + } + } + return false; +} + +// Sorts in the falling order of y values, if y is equal, x is used instead. +bool TPPLPartition::VertexSorter::operator()(long index1, long index2) { + if (vertices[index1].p.y > vertices[index2].p.y) { + return true; + } else if (vertices[index1].p.y == vertices[index2].p.y) { + if (vertices[index1].p.x > vertices[index2].p.x) { + return true; + } + } + return false; +} + +bool TPPLPartition::ScanLineEdge::IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const { + tppl_float tmp; + tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y); + if (tmp > 0) { + return 1; + } + + return 0; +} + +bool TPPLPartition::ScanLineEdge::operator<(const ScanLineEdge &other) const { + if (other.p1.y == other.p2.y) { + if (p1.y == p2.y) { + return (p1.y < other.p1.y); + } + return IsConvex(p1, p2, other.p1); + } else if (p1.y == p2.y) { + return !IsConvex(other.p1, other.p2, p1); + } else if (p1.y < other.p1.y) { + return !IsConvex(other.p1, other.p2, p1); + } else { + return IsConvex(p1, p2, other.p1); + } +} + +// Triangulates monotone polygon. +// Time complexity: O(n) +// Space complexity: O(n) +int TPPLPartition::TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles) { + if (!inPoly->Valid()) { + return 0; + } + + long i, i2, j, topindex, bottomindex, leftindex, rightindex, vindex; + TPPLPoint *points = NULL; + long numpoints; + TPPLPoly triangle; + + numpoints = inPoly->GetNumPoints(); + points = inPoly->GetPoints(); + + // Trivial case. + if (numpoints == 3) { + triangles->push_back(*inPoly); + return 1; + } + + topindex = 0; + bottomindex = 0; + for (i = 1; i < numpoints; i++) { + if (Below(points[i], points[bottomindex])) { + bottomindex = i; + } + if (Below(points[topindex], points[i])) { + topindex = i; + } + } + + // Check if the poly is really monotone. + i = topindex; + while (i != bottomindex) { + i2 = i + 1; + if (i2 >= numpoints) { + i2 = 0; + } + if (!Below(points[i2], points[i])) { + return 0; + } + i = i2; + } + i = bottomindex; + while (i != topindex) { + i2 = i + 1; + if (i2 >= numpoints) { + i2 = 0; + } + if (!Below(points[i], points[i2])) { + return 0; + } + i = i2; + } + + char *vertextypes = new char[numpoints]; + long *priority = new long[numpoints]; + + // Merge left and right vertex chains. + priority[0] = topindex; + vertextypes[topindex] = 0; + leftindex = topindex + 1; + if (leftindex >= numpoints) { + leftindex = 0; + } + rightindex = topindex - 1; + if (rightindex < 0) { + rightindex = numpoints - 1; + } + for (i = 1; i < (numpoints - 1); i++) { + if (leftindex == bottomindex) { + priority[i] = rightindex; + rightindex--; + if (rightindex < 0) { + rightindex = numpoints - 1; + } + vertextypes[priority[i]] = -1; + } else if (rightindex == bottomindex) { + priority[i] = leftindex; + leftindex++; + if (leftindex >= numpoints) { + leftindex = 0; + } + vertextypes[priority[i]] = 1; + } else { + if (Below(points[leftindex], points[rightindex])) { + priority[i] = rightindex; + rightindex--; + if (rightindex < 0) { + rightindex = numpoints - 1; + } + vertextypes[priority[i]] = -1; + } else { + priority[i] = leftindex; + leftindex++; + if (leftindex >= numpoints) { + leftindex = 0; + } + vertextypes[priority[i]] = 1; + } + } + } + priority[i] = bottomindex; + vertextypes[bottomindex] = 0; + + long *stack = new long[numpoints]; + long stackptr = 0; + + stack[0] = priority[0]; + stack[1] = priority[1]; + stackptr = 2; + + // For each vertex from top to bottom trim as many triangles as possible. + for (i = 2; i < (numpoints - 1); i++) { + vindex = priority[i]; + if (vertextypes[vindex] != vertextypes[stack[stackptr - 1]]) { + for (j = 0; j < (stackptr - 1); j++) { + if (vertextypes[vindex] == 1) { + triangle.Triangle(points[stack[j + 1]], points[stack[j]], points[vindex]); + } else { + triangle.Triangle(points[stack[j]], points[stack[j + 1]], points[vindex]); + } + triangles->push_back(triangle); + } + stack[0] = priority[i - 1]; + stack[1] = priority[i]; + stackptr = 2; + } else { + stackptr--; + while (stackptr > 0) { + if (vertextypes[vindex] == 1) { + if (IsConvex(points[vindex], points[stack[stackptr - 1]], points[stack[stackptr]])) { + triangle.Triangle(points[vindex], points[stack[stackptr - 1]], points[stack[stackptr]]); + triangles->push_back(triangle); + stackptr--; + } else { + break; + } + } else { + if (IsConvex(points[vindex], points[stack[stackptr]], points[stack[stackptr - 1]])) { + triangle.Triangle(points[vindex], points[stack[stackptr]], points[stack[stackptr - 1]]); + triangles->push_back(triangle); + stackptr--; + } else { + break; + } + } + } + stackptr++; + stack[stackptr] = vindex; + stackptr++; + } + } + vindex = priority[i]; + for (j = 0; j < (stackptr - 1); j++) { + if (vertextypes[stack[j + 1]] == 1) { + triangle.Triangle(points[stack[j]], points[stack[j + 1]], points[vindex]); + } else { + triangle.Triangle(points[stack[j + 1]], points[stack[j]], points[vindex]); + } + triangles->push_back(triangle); + } + + delete[] priority; + delete[] vertextypes; + delete[] stack; + + return 1; +} + +int TPPLPartition::Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles) { + TPPLPolyList monotone; + TPPLPolyList::Element *iter; + + if (!MonotonePartition(inpolys, &monotone)) { + return 0; + } + for (iter = monotone.front(); iter; iter = iter->next()) { + if (!TriangulateMonotone(&(iter->get()), triangles)) { + return 0; + } + } + return 1; +} + +int TPPLPartition::Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles) { + TPPLPolyList polys; + polys.push_back(*poly); + + return Triangulate_MONO(&polys, triangles); +} diff --git a/thirdparty/misc/polypartition.h b/thirdparty/misc/polypartition.h new file mode 100644 index 0000000000..b2d905a3ef --- /dev/null +++ b/thirdparty/misc/polypartition.h @@ -0,0 +1,378 @@ +/*************************************************************************/ +/* Copyright (c) 2011-2021 Ivan Fratric and contributors. */ +/* */ +/* 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. */ +/*************************************************************************/ + +#ifndef POLYPARTITION_H +#define POLYPARTITION_H + +#include "core/math/vector2.h" +#include "core/templates/list.h" +#include "core/templates/set.h" + +typedef double tppl_float; + +enum TPPLOrientation { + TPPL_ORIENTATION_CW = -1, + TPPL_ORIENTATION_NONE = 0, + TPPL_ORIENTATION_CCW = 1, +}; + +enum TPPLVertexType { + TPPL_VERTEXTYPE_REGULAR = 0, + TPPL_VERTEXTYPE_START = 1, + TPPL_VERTEXTYPE_END = 2, + TPPL_VERTEXTYPE_SPLIT = 3, + TPPL_VERTEXTYPE_MERGE = 4, +}; + +// 2D point structure. +typedef Vector2 TPPLPoint; + +// Polygon implemented as an array of points with a "hole" flag. +class TPPLPoly { + protected: + TPPLPoint *points; + long numpoints; + bool hole; + + public: + // Constructors and destructors. + TPPLPoly(); + ~TPPLPoly(); + + TPPLPoly(const TPPLPoly &src); + TPPLPoly &operator=(const TPPLPoly &src); + + // Getters and setters. + long GetNumPoints() const { + return numpoints; + } + + bool IsHole() const { + return hole; + } + + void SetHole(bool hole) { + this->hole = hole; + } + + TPPLPoint &GetPoint(long i) { + return points[i]; + } + + const TPPLPoint &GetPoint(long i) const { + return points[i]; + } + + TPPLPoint *GetPoints() { + return points; + } + + TPPLPoint &operator[](int i) { + return points[i]; + } + + const TPPLPoint &operator[](int i) const { + return points[i]; + } + + // Clears the polygon points. + void Clear(); + + // Inits the polygon with numpoints vertices. + void Init(long numpoints); + + // Creates a triangle with points p1, p2, and p3. + void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3); + + // Inverts the orfer of vertices. + void Invert(); + + // Returns the orientation of the polygon. + // Possible values: + // TPPL_ORIENTATION_CCW: Polygon vertices are in counter-clockwise order. + // TPPL_ORIENTATION_CW: Polygon vertices are in clockwise order. + // TPPL_ORIENTATION_NONE: The polygon has no (measurable) area. + TPPLOrientation GetOrientation() const; + + // Sets the polygon orientation. + // Possible values: + // TPPL_ORIENTATION_CCW: Sets vertices in counter-clockwise order. + // TPPL_ORIENTATION_CW: Sets vertices in clockwise order. + // TPPL_ORIENTATION_NONE: Reverses the orientation of the vertices if there + // is one, otherwise does nothing (if orientation is already NONE). + void SetOrientation(TPPLOrientation orientation); + + // Checks whether a polygon is valid or not. + inline bool Valid() const { return this->numpoints >= 3; } +}; + +#ifdef TPPL_ALLOCATOR +typedef List<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList; +#else +typedef List<TPPLPoly> TPPLPolyList; +#endif + +class TPPLPartition { + protected: + struct PartitionVertex { + bool isActive; + bool isConvex; + bool isEar; + + TPPLPoint p; + tppl_float angle; + PartitionVertex *previous; + PartitionVertex *next; + + PartitionVertex(); + }; + + struct MonotoneVertex { + TPPLPoint p; + long previous; + long next; + }; + + class VertexSorter { + MonotoneVertex *vertices; + +public: + VertexSorter(MonotoneVertex *v) : + vertices(v) {} + bool operator()(long index1, long index2); + }; + + struct Diagonal { + long index1; + long index2; + }; + +#ifdef TPPL_ALLOCATOR + typedef List<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList; +#else + typedef List<Diagonal> DiagonalList; +#endif + + // Dynamic programming state for minimum-weight triangulation. + struct DPState { + bool visible; + tppl_float weight; + long bestvertex; + }; + + // Dynamic programming state for convex partitioning. + struct DPState2 { + bool visible; + long weight; + DiagonalList pairs; + }; + + // Edge that intersects the scanline. + struct ScanLineEdge { + mutable long index; + TPPLPoint p1; + TPPLPoint p2; + + // Determines if the edge is to the left of another edge. + bool operator<(const ScanLineEdge &other) const; + + bool IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const; + }; + + // Standard helper functions. + bool IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3); + bool IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3); + bool IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p); + + bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p); + bool InCone(PartitionVertex *v, TPPLPoint &p); + + int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22); + + TPPLPoint Normalize(const TPPLPoint &p); + tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2); + + // Helper functions for Triangulate_EC. + void UpdateVertexReflexity(PartitionVertex *v); + void UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices); + + // Helper functions for ConvexPartition_OPT. + void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates); + void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); + void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); + + // Helper functions for MonotonePartition. + bool Below(TPPLPoint &p1, TPPLPoint &p2); + void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, + TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, + Set<ScanLineEdge> *edgeTree, long *helpers); + + // Triangulates a monotone polygon, used in Triangulate_MONO. + int TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles); + + public: + // Simple heuristic procedure for removing holes from a list of polygons. + // It works by creating a diagonal from the right-most hole vertex + // to some other visible vertex. + // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices. + // Space complexity: O(n) + // params: + // inpolys: + // A list of polygons that can contain holes. + // Vertices of all non-hole polys have to be in counter-clockwise order. + // Vertices of all hole polys have to be in clockwise order. + // outpolys: + // A list of polygons without holes. + // Returns 1 on success, 0 on failure. + int RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys); + + // Triangulates a polygon by ear clipping. + // Time complexity: O(n^2), n is the number of vertices. + // Space complexity: O(n) + // params: + // poly: + // An input polygon to be triangulated. + // Vertices have to be in counter-clockwise order. + // triangles: + // A list of triangles (result). + // Returns 1 on success, 0 on failure. + int Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles); + + // Triangulates a list of polygons that may contain holes by ear clipping + // algorithm. It first calls RemoveHoles to get rid of the holes, and then + // calls Triangulate_EC for each resulting polygon. + // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices. + // Space complexity: O(n) + // params: + // inpolys: + // A list of polygons to be triangulated (can contain holes). + // Vertices of all non-hole polys have to be in counter-clockwise order. + // Vertices of all hole polys have to be in clockwise order. + // triangles: + // A list of triangles (result). + // Returns 1 on success, 0 on failure. + int Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles); + + // Creates an optimal polygon triangulation in terms of minimal edge length. + // Time complexity: O(n^3), n is the number of vertices + // Space complexity: O(n^2) + // params: + // poly: + // An input polygon to be triangulated. + // Vertices have to be in counter-clockwise order. + // triangles: + // A list of triangles (result). + // Returns 1 on success, 0 on failure. + int Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles); + + // Triangulates a polygon by first partitioning it into monotone polygons. + // Time complexity: O(n*log(n)), n is the number of vertices. + // Space complexity: O(n) + // params: + // poly: + // An input polygon to be triangulated. + // Vertices have to be in counter-clockwise order. + // triangles: + // A list of triangles (result). + // Returns 1 on success, 0 on failure. + int Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles); + + // Triangulates a list of polygons by first + // partitioning them into monotone polygons. + // Time complexity: O(n*log(n)), n is the number of vertices. + // Space complexity: O(n) + // params: + // inpolys: + // A list of polygons to be triangulated (can contain holes). + // Vertices of all non-hole polys have to be in counter-clockwise order. + // Vertices of all hole polys have to be in clockwise order. + // triangles: + // A list of triangles (result). + // Returns 1 on success, 0 on failure. + int Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles); + + // Creates a monotone partition of a list of polygons that + // can contain holes. Triangulates a set of polygons by + // first partitioning them into monotone polygons. + // Time complexity: O(n*log(n)), n is the number of vertices. + // Space complexity: O(n) + // params: + // inpolys: + // A list of polygons to be triangulated (can contain holes). + // Vertices of all non-hole polys have to be in counter-clockwise order. + // Vertices of all hole polys have to be in clockwise order. + // monotonePolys: + // A list of monotone polygons (result). + // Returns 1 on success, 0 on failure. + int MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys); + + // Partitions a polygon into convex polygons by using the + // Hertel-Mehlhorn algorithm. The algorithm gives at most four times + // the number of parts as the optimal algorithm, however, in practice + // it works much better than that and often gives optimal partition. + // It uses triangulation obtained by ear clipping as intermediate result. + // Time complexity O(n^2), n is the number of vertices. + // Space complexity: O(n) + // params: + // poly: + // An input polygon to be partitioned. + // Vertices have to be in counter-clockwise order. + // parts: + // Resulting list of convex polygons. + // Returns 1 on success, 0 on failure. + int ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts); + + // Partitions a list of polygons into convex parts by using the + // Hertel-Mehlhorn algorithm. The algorithm gives at most four times + // the number of parts as the optimal algorithm, however, in practice + // it works much better than that and often gives optimal partition. + // It uses triangulation obtained by ear clipping as intermediate result. + // Time complexity O(n^2), n is the number of vertices. + // Space complexity: O(n) + // params: + // inpolys: + // An input list of polygons to be partitioned. Vertices of + // all non-hole polys have to be in counter-clockwise order. + // Vertices of all hole polys have to be in clockwise order. + // parts: + // Resulting list of convex polygons. + // Returns 1 on success, 0 on failure. + int ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts); + + // Optimal convex partitioning (in terms of number of resulting + // convex polygons) using the Keil-Snoeyink algorithm. + // For reference, see M. Keil, J. Snoeyink, "On the time bound for + // convex decomposition of simple polygons", 1998. + // Time complexity O(n^3), n is the number of vertices. + // Space complexity: O(n^3) + // params: + // poly: + // An input polygon to be partitioned. + // Vertices have to be in counter-clockwise order. + // parts: + // Resulting list of convex polygons. + // Returns 1 on success, 0 on failure. + int ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts); +}; + +#endif diff --git a/thirdparty/misc/triangulator.cpp b/thirdparty/misc/triangulator.cpp deleted file mode 100644 index d6b63c6638..0000000000 --- a/thirdparty/misc/triangulator.cpp +++ /dev/null @@ -1,1550 +0,0 @@ -//Copyright (C) 2011 by Ivan Fratric -// -//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 <stdio.h> -#include <string.h> -#include <math.h> - -#include "triangulator.h" - - -#define TRIANGULATOR_VERTEXTYPE_REGULAR 0 -#define TRIANGULATOR_VERTEXTYPE_START 1 -#define TRIANGULATOR_VERTEXTYPE_END 2 -#define TRIANGULATOR_VERTEXTYPE_SPLIT 3 -#define TRIANGULATOR_VERTEXTYPE_MERGE 4 - -TriangulatorPoly::TriangulatorPoly() { - hole = false; - numpoints = 0; - points = NULL; -} - -TriangulatorPoly::~TriangulatorPoly() { - if(points) delete [] points; -} - -void TriangulatorPoly::Clear() { - if(points) delete [] points; - hole = false; - numpoints = 0; - points = NULL; -} - -void TriangulatorPoly::Init(long numpoints) { - Clear(); - this->numpoints = numpoints; - points = new Vector2[numpoints]; -} - -void TriangulatorPoly::Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3) { - Init(3); - points[0] = p1; - points[1] = p2; - points[2] = p3; -} - -TriangulatorPoly::TriangulatorPoly(const TriangulatorPoly &src) { - hole = src.hole; - numpoints = src.numpoints; - points = new Vector2[numpoints]; - memcpy(points, src.points, numpoints*sizeof(Vector2)); -} - -TriangulatorPoly& TriangulatorPoly::operator=(const TriangulatorPoly &src) { - Clear(); - hole = src.hole; - numpoints = src.numpoints; - points = new Vector2[numpoints]; - memcpy(points, src.points, numpoints*sizeof(Vector2)); - return *this; -} - -int TriangulatorPoly::GetOrientation() { - long i1,i2; - real_t area = 0; - for(i1=0; i1<numpoints; i1++) { - i2 = i1+1; - if(i2 == numpoints) i2 = 0; - area += points[i1].x * points[i2].y - points[i1].y * points[i2].x; - } - if(area>0) return TRIANGULATOR_CCW; - if(area<0) return TRIANGULATOR_CW; - return 0; -} - -void TriangulatorPoly::SetOrientation(int orientation) { - int polyorientation = GetOrientation(); - if(polyorientation&&(polyorientation!=orientation)) { - Invert(); - } -} - -void TriangulatorPoly::Invert() { - long i; - Vector2 *invpoints; - - invpoints = new Vector2[numpoints]; - for(i=0;i<numpoints;i++) { - invpoints[i] = points[numpoints-i-1]; - } - - delete [] points; - points = invpoints; -} - -Vector2 TriangulatorPartition::Normalize(const Vector2 &p) { - Vector2 r; - real_t n = sqrt(p.x*p.x + p.y*p.y); - if(n!=0) { - r = p/n; - } else { - r.x = 0; - r.y = 0; - } - return r; -} - -real_t TriangulatorPartition::Distance(const Vector2 &p1, const Vector2 &p2) { - real_t dx,dy; - dx = p2.x - p1.x; - dy = p2.y - p1.y; - return(sqrt(dx*dx + dy*dy)); -} - -//checks if two lines intersect -int TriangulatorPartition::Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22) { - if((p11.x == p21.x)&&(p11.y == p21.y)) return 0; - if((p11.x == p22.x)&&(p11.y == p22.y)) return 0; - if((p12.x == p21.x)&&(p12.y == p21.y)) return 0; - if((p12.x == p22.x)&&(p12.y == p22.y)) return 0; - - Vector2 v1ort,v2ort,v; - real_t dot11,dot12,dot21,dot22; - - v1ort.x = p12.y-p11.y; - v1ort.y = p11.x-p12.x; - - v2ort.x = p22.y-p21.y; - v2ort.y = p21.x-p22.x; - - v = p21-p11; - dot21 = v.x*v1ort.x + v.y*v1ort.y; - v = p22-p11; - dot22 = v.x*v1ort.x + v.y*v1ort.y; - - v = p11-p21; - dot11 = v.x*v2ort.x + v.y*v2ort.y; - v = p12-p21; - dot12 = v.x*v2ort.x + v.y*v2ort.y; - - if(dot11*dot12>0) return 0; - if(dot21*dot22>0) return 0; - - return 1; -} - -//removes holes from inpolys by merging them with non-holes -int TriangulatorPartition::RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys) { - List<TriangulatorPoly> polys; - List<TriangulatorPoly>::Element *holeiter,*polyiter,*iter,*iter2; - long i,i2,holepointindex,polypointindex; - Vector2 holepoint,polypoint,bestpolypoint; - Vector2 linep1,linep2; - Vector2 v1,v2; - TriangulatorPoly newpoly; - bool hasholes; - bool pointvisible; - bool pointfound; - - //check for trivial case (no holes) - hasholes = false; - for(iter = inpolys->front(); iter; iter=iter->next()) { - if(iter->get().IsHole()) { - hasholes = true; - break; - } - } - if(!hasholes) { - for(iter = inpolys->front(); iter; iter=iter->next()) { - outpolys->push_back(iter->get()); - } - return 1; - } - - polys = *inpolys; - - while(1) { - //find the hole point with the largest x - hasholes = false; - for(iter = polys.front(); iter; iter=iter->next()) { - if(!iter->get().IsHole()) continue; - - if(!hasholes) { - hasholes = true; - holeiter = iter; - holepointindex = 0; - } - - for(i=0; i < iter->get().GetNumPoints(); i++) { - if(iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) { - holeiter = iter; - holepointindex = i; - } - } - } - if(!hasholes) break; - holepoint = holeiter->get().GetPoint(holepointindex); - - pointfound = false; - for(iter = polys.front(); iter; iter=iter->next()) { - if(iter->get().IsHole()) continue; - for(i=0; i < iter->get().GetNumPoints(); i++) { - if(iter->get().GetPoint(i).x <= holepoint.x) continue; - if(!InCone(iter->get().GetPoint((i+iter->get().GetNumPoints()-1)%(iter->get().GetNumPoints())), - iter->get().GetPoint(i), - iter->get().GetPoint((i+1)%(iter->get().GetNumPoints())), - holepoint)) - continue; - polypoint = iter->get().GetPoint(i); - if(pointfound) { - v1 = Normalize(polypoint-holepoint); - v2 = Normalize(bestpolypoint-holepoint); - if(v2.x > v1.x) continue; - } - pointvisible = true; - for(iter2 = polys.front(); iter2; iter2=iter2->next()) { - if(iter2->get().IsHole()) continue; - for(i2=0; i2 < iter2->get().GetNumPoints(); i2++) { - linep1 = iter2->get().GetPoint(i2); - linep2 = iter2->get().GetPoint((i2+1)%(iter2->get().GetNumPoints())); - if(Intersects(holepoint,polypoint,linep1,linep2)) { - pointvisible = false; - break; - } - } - if(!pointvisible) break; - } - if(pointvisible) { - pointfound = true; - bestpolypoint = polypoint; - polyiter = iter; - polypointindex = i; - } - } - } - - if(!pointfound) return 0; - - newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2); - i2 = 0; - for(i=0;i<=polypointindex;i++) { - newpoly[i2] = polyiter->get().GetPoint(i); - i2++; - } - for(i=0;i<=holeiter->get().GetNumPoints();i++) { - newpoly[i2] = holeiter->get().GetPoint((i+holepointindex)%holeiter->get().GetNumPoints()); - i2++; - } - for(i=polypointindex;i<polyiter->get().GetNumPoints();i++) { - newpoly[i2] = polyiter->get().GetPoint(i); - i2++; - } - - polys.erase(holeiter); - polys.erase(polyiter); - polys.push_back(newpoly); - } - - for(iter = polys.front(); iter; iter=iter->next()) { - outpolys->push_back(iter->get()); - } - - return 1; -} - -bool TriangulatorPartition::IsConvex(Vector2& p1, Vector2& p2, Vector2& p3) { - real_t tmp; - tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); - if(tmp>0) return 1; - else return 0; -} - -bool TriangulatorPartition::IsReflex(Vector2& p1, Vector2& p2, Vector2& p3) { - real_t tmp; - tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); - if(tmp<0) return 1; - else return 0; -} - -bool TriangulatorPartition::IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p) { - if(IsConvex(p1,p,p2)) return false; - if(IsConvex(p2,p,p3)) return false; - if(IsConvex(p3,p,p1)) return false; - return true; -} - -bool TriangulatorPartition::InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p) { - bool convex; - - convex = IsConvex(p1,p2,p3); - - if(convex) { - if(!IsConvex(p1,p2,p)) return false; - if(!IsConvex(p2,p3,p)) return false; - return true; - } else { - if(IsConvex(p1,p2,p)) return true; - if(IsConvex(p2,p3,p)) return true; - return false; - } -} - -bool TriangulatorPartition::InCone(PartitionVertex *v, Vector2 &p) { - Vector2 p1,p2,p3; - - p1 = v->previous->p; - p2 = v->p; - p3 = v->next->p; - - return InCone(p1,p2,p3,p); -} - -void TriangulatorPartition::UpdateVertexReflexity(PartitionVertex *v) { - PartitionVertex *v1,*v3; - v1 = v->previous; - v3 = v->next; - v->isConvex = !IsReflex(v1->p,v->p,v3->p); -} - -void TriangulatorPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) { - long i; - PartitionVertex *v1,*v3; - Vector2 vec1,vec3; - - v1 = v->previous; - v3 = v->next; - - v->isConvex = IsConvex(v1->p,v->p,v3->p); - - vec1 = Normalize(v1->p - v->p); - vec3 = Normalize(v3->p - v->p); - v->angle = vec1.x*vec3.x + vec1.y*vec3.y; - - if(v->isConvex) { - v->isEar = true; - for(i=0;i<numvertices;i++) { - if((vertices[i].p.x==v->p.x)&&(vertices[i].p.y==v->p.y)) continue; - if((vertices[i].p.x==v1->p.x)&&(vertices[i].p.y==v1->p.y)) continue; - if((vertices[i].p.x==v3->p.x)&&(vertices[i].p.y==v3->p.y)) continue; - if(IsInside(v1->p,v->p,v3->p,vertices[i].p)) { - v->isEar = false; - break; - } - } - } else { - v->isEar = false; - } -} - -//triangulation by ear removal -int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) { - long numvertices; - PartitionVertex *vertices; - PartitionVertex *ear; - TriangulatorPoly triangle; - long i,j; - bool earfound; - - if(poly->GetNumPoints() < 3) return 0; - if(poly->GetNumPoints() == 3) { - triangles->push_back(*poly); - return 1; - } - - numvertices = poly->GetNumPoints(); - - vertices = new PartitionVertex[numvertices]; - for(i=0;i<numvertices;i++) { - vertices[i].isActive = true; - vertices[i].p = poly->GetPoint(i); - if(i==(numvertices-1)) vertices[i].next=&(vertices[0]); - else vertices[i].next=&(vertices[i+1]); - if(i==0) vertices[i].previous = &(vertices[numvertices-1]); - else vertices[i].previous = &(vertices[i-1]); - } - for(i=0;i<numvertices;i++) { - UpdateVertex(&vertices[i],vertices,numvertices); - } - - for(i=0;i<numvertices-3;i++) { - earfound = false; - //find the most extruded ear - for(j=0;j<numvertices;j++) { - if(!vertices[j].isActive) continue; - if(!vertices[j].isEar) continue; - if(!earfound) { - earfound = true; - ear = &(vertices[j]); - } else { - if(vertices[j].angle > ear->angle) { - ear = &(vertices[j]); - } - } - } - if(!earfound) { - delete [] vertices; - return 0; - } - - triangle.Triangle(ear->previous->p,ear->p,ear->next->p); - triangles->push_back(triangle); - - ear->isActive = false; - ear->previous->next = ear->next; - ear->next->previous = ear->previous; - - if(i==numvertices-4) break; - - UpdateVertex(ear->previous,vertices,numvertices); - UpdateVertex(ear->next,vertices,numvertices); - } - for(i=0;i<numvertices;i++) { - if(vertices[i].isActive) { - triangle.Triangle(vertices[i].previous->p,vertices[i].p,vertices[i].next->p); - triangles->push_back(triangle); - break; - } - } - - delete [] vertices; - - return 1; -} - -int TriangulatorPartition::Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) { - List<TriangulatorPoly> outpolys; - List<TriangulatorPoly>::Element*iter; - - if(!RemoveHoles(inpolys,&outpolys)) return 0; - for(iter=outpolys.front();iter;iter=iter->next()) { - if(!Triangulate_EC(&(iter->get()),triangles)) return 0; - } - return 1; -} - -int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) { - List<TriangulatorPoly> triangles; - List<TriangulatorPoly>::Element *iter1,*iter2; - TriangulatorPoly *poly1,*poly2; - TriangulatorPoly newpoly; - Vector2 d1,d2,p1,p2,p3; - long i11,i12,i21,i22,i13,i23,j,k; - bool isdiagonal; - long numreflex; - - //check if the poly is already convex - numreflex = 0; - for(i11=0;i11<poly->GetNumPoints();i11++) { - if(i11==0) i12 = poly->GetNumPoints()-1; - else i12=i11-1; - if(i11==(poly->GetNumPoints()-1)) i13=0; - else i13=i11+1; - if(IsReflex(poly->GetPoint(i12),poly->GetPoint(i11),poly->GetPoint(i13))) { - numreflex = 1; - break; - } - } - if(numreflex == 0) { - parts->push_back(*poly); - return 1; - } - - if(!Triangulate_EC(poly,&triangles)) return 0; - - for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) { - poly1 = &(iter1->get()); - for(i11=0;i11<poly1->GetNumPoints();i11++) { - d1 = poly1->GetPoint(i11); - i12 = (i11+1)%(poly1->GetNumPoints()); - d2 = poly1->GetPoint(i12); - - isdiagonal = false; - for(iter2 = iter1; iter2 ; iter2=iter2->next()) { - if(iter1 == iter2) continue; - poly2 = &(iter2->get()); - - for(i21=0;i21<poly2->GetNumPoints();i21++) { - if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue; - i22 = (i21+1)%(poly2->GetNumPoints()); - if((d1.x != poly2->GetPoint(i22).x)||(d1.y != poly2->GetPoint(i22).y)) continue; - isdiagonal = true; - break; - } - if(isdiagonal) break; - } - - if(!isdiagonal) continue; - - p2 = poly1->GetPoint(i11); - if(i11 == 0) i13 = poly1->GetNumPoints()-1; - else i13 = i11-1; - p1 = poly1->GetPoint(i13); - if(i22 == (poly2->GetNumPoints()-1)) i23 = 0; - else i23 = i22+1; - p3 = poly2->GetPoint(i23); - - if(!IsConvex(p1,p2,p3)) continue; - - p2 = poly1->GetPoint(i12); - if(i12 == (poly1->GetNumPoints()-1)) i13 = 0; - else i13 = i12+1; - p3 = poly1->GetPoint(i13); - if(i21 == 0) i23 = poly2->GetNumPoints()-1; - else i23 = i21-1; - p1 = poly2->GetPoint(i23); - - if(!IsConvex(p1,p2,p3)) continue; - - newpoly.Init(poly1->GetNumPoints()+poly2->GetNumPoints()-2); - k = 0; - for(j=i12;j!=i11;j=(j+1)%(poly1->GetNumPoints())) { - newpoly[k] = poly1->GetPoint(j); - k++; - } - for(j=i22;j!=i21;j=(j+1)%(poly2->GetNumPoints())) { - newpoly[k] = poly2->GetPoint(j); - k++; - } - - triangles.erase(iter2); - iter1->get() = newpoly; - poly1 = &(iter1->get()); - i11 = -1; - - continue; - } - } - - for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) { - parts->push_back(iter1->get()); - } - - return 1; -} - -int TriangulatorPartition::ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts) { - List<TriangulatorPoly> outpolys; - List<TriangulatorPoly>::Element* iter; - - if(!RemoveHoles(inpolys,&outpolys)) return 0; - for(iter=outpolys.front();iter;iter=iter->next()) { - if(!ConvexPartition_HM(&(iter->get()),parts)) return 0; - } - return 1; -} - -//minimum-weight polygon triangulation by dynamic programming -//O(n^3) time complexity -//O(n^2) space complexity -int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) { - long i,j,k,gap,n; - DPState **dpstates; - Vector2 p1,p2,p3,p4; - long bestvertex; - real_t weight,minweight,d1,d2; - Diagonal diagonal,newdiagonal; - List<Diagonal> diagonals; - TriangulatorPoly triangle; - int ret = 1; - - n = poly->GetNumPoints(); - dpstates = new DPState *[n]; - for(i=1;i<n;i++) { - dpstates[i] = new DPState[i]; - } - - //init states and visibility - for(i=0;i<(n-1);i++) { - p1 = poly->GetPoint(i); - for(j=i+1;j<n;j++) { - dpstates[j][i].visible = true; - dpstates[j][i].weight = 0; - dpstates[j][i].bestvertex = -1; - if(j!=(i+1)) { - p2 = poly->GetPoint(j); - - //visibility check - if(i==0) p3 = poly->GetPoint(n-1); - else p3 = poly->GetPoint(i-1); - if(i==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(i+1); - if(!InCone(p3,p1,p4,p2)) { - dpstates[j][i].visible = false; - continue; - } - - if(j==0) p3 = poly->GetPoint(n-1); - else p3 = poly->GetPoint(j-1); - if(j==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(j+1); - if(!InCone(p3,p2,p4,p1)) { - dpstates[j][i].visible = false; - continue; - } - - for(k=0;k<n;k++) { - p3 = poly->GetPoint(k); - if(k==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(k+1); - if(Intersects(p1,p2,p3,p4)) { - dpstates[j][i].visible = false; - break; - } - } - } - } - } - dpstates[n-1][0].visible = true; - dpstates[n-1][0].weight = 0; - dpstates[n-1][0].bestvertex = -1; - - for(gap = 2; gap<n; gap++) { - for(i=0; i<(n-gap); i++) { - j = i+gap; - if(!dpstates[j][i].visible) continue; - bestvertex = -1; - for(k=(i+1);k<j;k++) { - if(!dpstates[k][i].visible) continue; - if(!dpstates[j][k].visible) continue; - - if(k<=(i+1)) d1=0; - else d1 = Distance(poly->GetPoint(i),poly->GetPoint(k)); - if(j<=(k+1)) d2=0; - else d2 = Distance(poly->GetPoint(k),poly->GetPoint(j)); - - weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2; - - if((bestvertex == -1)||(weight<minweight)) { - bestvertex = k; - minweight = weight; - } - } - if(bestvertex == -1) { - for(i=1;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - - return 0; - } - - dpstates[j][i].bestvertex = bestvertex; - dpstates[j][i].weight = minweight; - } - } - - newdiagonal.index1 = 0; - newdiagonal.index2 = n-1; - diagonals.push_back(newdiagonal); - while(!diagonals.is_empty()) { - diagonal = (diagonals.front()->get()); - diagonals.pop_front(); - bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex; - if(bestvertex == -1) { - ret = 0; - break; - } - triangle.Triangle(poly->GetPoint(diagonal.index1),poly->GetPoint(bestvertex),poly->GetPoint(diagonal.index2)); - triangles->push_back(triangle); - if(bestvertex > (diagonal.index1+1)) { - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = bestvertex; - diagonals.push_back(newdiagonal); - } - if(diagonal.index2 > (bestvertex+1)) { - newdiagonal.index1 = bestvertex; - newdiagonal.index2 = diagonal.index2; - diagonals.push_back(newdiagonal); - } - } - - for(i=1;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - - return ret; -} - -void TriangulatorPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) { - Diagonal newdiagonal; - List<Diagonal> *pairs; - long w2; - - w2 = dpstates[a][b].weight; - if(w>w2) return; - - pairs = &(dpstates[a][b].pairs); - newdiagonal.index1 = i; - newdiagonal.index2 = j; - - if(w<w2) { - pairs->clear(); - pairs->push_front(newdiagonal); - dpstates[a][b].weight = w; - } else { - if((!pairs->is_empty())&&(i <= pairs->front()->get().index1)) return; - while((!pairs->is_empty())&&(pairs->front()->get().index2 >= j)) pairs->pop_front(); - pairs->push_front(newdiagonal); - } -} - -void TriangulatorPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { - List<Diagonal> *pairs; - List<Diagonal>::Element *iter,*lastiter; - long top; - long w; - - if(!dpstates[i][j].visible) return; - top = j; - w = dpstates[i][j].weight; - if(k-j > 1) { - if (!dpstates[j][k].visible) return; - w += dpstates[j][k].weight + 1; - } - if(j-i > 1) { - pairs = &(dpstates[i][j].pairs); - iter = NULL; - lastiter = NULL; - while(iter!=pairs->front()) { - if (!iter) - iter=pairs->back(); - else - iter=iter->prev(); - - if(!IsReflex(vertices[iter->get().index2].p,vertices[j].p,vertices[k].p)) lastiter = iter; - else break; - } - if(lastiter == NULL) w++; - else { - if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->get().index1].p)) w++; - else top = lastiter->get().index1; - } - } - UpdateState(i,k,w,top,j,dpstates); -} - -void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { - List<Diagonal> *pairs; - List<Diagonal>::Element* iter,*lastiter; - long top; - long w; - - if(!dpstates[j][k].visible) return; - top = j; - w = dpstates[j][k].weight; - - if (j-i > 1) { - if (!dpstates[i][j].visible) return; - w += dpstates[i][j].weight + 1; - } - if (k-j > 1) { - pairs = &(dpstates[j][k].pairs); - - iter = pairs->front(); - if((!pairs->is_empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) { - lastiter = iter; - while(iter!=NULL) { - if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p)) { - lastiter = iter; - iter=iter->next(); - } - else break; - } - if(IsReflex(vertices[lastiter->get().index2].p,vertices[k].p,vertices[i].p)) w++; - else top = lastiter->get().index2; - } else w++; - } - UpdateState(i,k,w,j,top,dpstates); -} - -int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) { - Vector2 p1,p2,p3,p4; - PartitionVertex *vertices; - DPState2 **dpstates; - long i,j,k,n,gap; - List<Diagonal> diagonals,diagonals2; - Diagonal diagonal,newdiagonal; - List<Diagonal> *pairs,*pairs2; - List<Diagonal>::Element* iter,*iter2; - int ret; - TriangulatorPoly newpoly; - List<long> indices; - List<long>::Element* iiter; - bool ijreal,jkreal; - - n = poly->GetNumPoints(); - vertices = new PartitionVertex[n]; - - dpstates = new DPState2 *[n]; - for(i=0;i<n;i++) { - dpstates[i] = new DPState2[n]; - } - - //init vertex information - for(i=0;i<n;i++) { - vertices[i].p = poly->GetPoint(i); - vertices[i].isActive = true; - if(i==0) vertices[i].previous = &(vertices[n-1]); - else vertices[i].previous = &(vertices[i-1]); - if(i==(poly->GetNumPoints()-1)) vertices[i].next = &(vertices[0]); - else vertices[i].next = &(vertices[i+1]); - } - for(i=1;i<n;i++) { - UpdateVertexReflexity(&(vertices[i])); - } - - //init states and visibility - for(i=0;i<(n-1);i++) { - p1 = poly->GetPoint(i); - for(j=i+1;j<n;j++) { - dpstates[i][j].visible = true; - if(j==i+1) { - dpstates[i][j].weight = 0; - } else { - dpstates[i][j].weight = 2147483647; - } - if(j!=(i+1)) { - p2 = poly->GetPoint(j); - - //visibility check - if(!InCone(&vertices[i],p2)) { - dpstates[i][j].visible = false; - continue; - } - if(!InCone(&vertices[j],p1)) { - dpstates[i][j].visible = false; - continue; - } - - for(k=0;k<n;k++) { - p3 = poly->GetPoint(k); - if(k==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(k+1); - if(Intersects(p1,p2,p3,p4)) { - dpstates[i][j].visible = false; - break; - } - } - } - } - } - for(i=0;i<(n-2);i++) { - j = i+2; - if(dpstates[i][j].visible) { - dpstates[i][j].weight = 0; - newdiagonal.index1 = i+1; - newdiagonal.index2 = i+1; - dpstates[i][j].pairs.push_back(newdiagonal); - } - } - - dpstates[0][n-1].visible = true; - vertices[0].isConvex = false; //by convention - - for(gap=3; gap<n; gap++) { - for(i=0;i<n-gap;i++) { - if(vertices[i].isConvex) continue; - k = i+gap; - if(dpstates[i][k].visible) { - if(!vertices[k].isConvex) { - for(j=i+1;j<k;j++) TypeA(i,j,k,vertices,dpstates); - } else { - for(j=i+1;j<(k-1);j++) { - if(vertices[j].isConvex) continue; - TypeA(i,j,k,vertices,dpstates); - } - TypeA(i,k-1,k,vertices,dpstates); - } - } - } - for(k=gap;k<n;k++) { - if(vertices[k].isConvex) continue; - i = k-gap; - if((vertices[i].isConvex)&&(dpstates[i][k].visible)) { - TypeB(i,i+1,k,vertices,dpstates); - for(j=i+2;j<k;j++) { - if(vertices[j].isConvex) continue; - TypeB(i,j,k,vertices,dpstates); - } - } - } - } - - - //recover solution - ret = 1; - newdiagonal.index1 = 0; - newdiagonal.index2 = n-1; - diagonals.push_front(newdiagonal); - while(!diagonals.is_empty()) { - diagonal = (diagonals.front()->get()); - diagonals.pop_front(); - if((diagonal.index2 - diagonal.index1) <=1) continue; - pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); - if(pairs->is_empty()) { - ret = 0; - break; - } - if(!vertices[diagonal.index1].isConvex) { - iter = pairs->back(); - - j = iter->get().index2; - newdiagonal.index1 = j; - newdiagonal.index2 = diagonal.index2; - diagonals.push_front(newdiagonal); - if((j - diagonal.index1)>1) { - if(iter->get().index1 != iter->get().index2) { - pairs2 = &(dpstates[diagonal.index1][j].pairs); - while(1) { - if(pairs2->is_empty()) { - ret = 0; - break; - } - iter2 = pairs2->back(); - - if(iter->get().index1 != iter2->get().index1) pairs2->pop_back(); - else break; - } - if(ret == 0) break; - } - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = j; - diagonals.push_front(newdiagonal); - } - } else { - iter = pairs->front(); - j = iter->get().index1; - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = j; - diagonals.push_front(newdiagonal); - if((diagonal.index2 - j) > 1) { - if(iter->get().index1 != iter->get().index2) { - pairs2 = &(dpstates[j][diagonal.index2].pairs); - while(1) { - if(pairs2->is_empty()) { - ret = 0; - break; - } - iter2 = pairs2->front(); - if(iter->get().index2 != iter2->get().index2) pairs2->pop_front(); - else break; - } - if(ret == 0) break; - } - newdiagonal.index1 = j; - newdiagonal.index2 = diagonal.index2; - diagonals.push_front(newdiagonal); - } - } - } - - if(ret == 0) { - for(i=0;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - delete [] vertices; - - return ret; - } - - newdiagonal.index1 = 0; - newdiagonal.index2 = n-1; - diagonals.push_front(newdiagonal); - while(!diagonals.is_empty()) { - diagonal = (diagonals.front())->get(); - diagonals.pop_front(); - if((diagonal.index2 - diagonal.index1) <= 1) continue; - - indices.clear(); - diagonals2.clear(); - indices.push_back(diagonal.index1); - indices.push_back(diagonal.index2); - diagonals2.push_front(diagonal); - - while(!diagonals2.is_empty()) { - diagonal = (diagonals2.front()->get()); - diagonals2.pop_front(); - if((diagonal.index2 - diagonal.index1) <= 1) continue; - ijreal = true; - jkreal = true; - pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); - if(!vertices[diagonal.index1].isConvex) { - iter = pairs->back(); - j = iter->get().index2; - if(iter->get().index1 != iter->get().index2) ijreal = false; - } else { - iter = pairs->front(); - j = iter->get().index1; - if(iter->get().index1 != iter->get().index2) jkreal = false; - } - - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = j; - if(ijreal) { - diagonals.push_back(newdiagonal); - } else { - diagonals2.push_back(newdiagonal); - } - - newdiagonal.index1 = j; - newdiagonal.index2 = diagonal.index2; - if(jkreal) { - diagonals.push_back(newdiagonal); - } else { - diagonals2.push_back(newdiagonal); - } - - indices.push_back(j); - } - - indices.sort(); - newpoly.Init((long)indices.size()); - k=0; - for(iiter = indices.front();iiter;iiter=iiter->next()) { - newpoly[k] = vertices[iiter->get()].p; - k++; - } - parts->push_back(newpoly); - } - - for(i=0;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - delete [] vertices; - - return ret; -} - -//triangulates a set of polygons by first partitioning them into monotone polygons -//O(n*log(n)) time complexity, O(n) space complexity -//the algorithm used here is outlined in the book -//"Computational Geometry: Algorithms and Applications" -//by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars -int TriangulatorPartition::MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys) { - List<TriangulatorPoly>::Element *iter; - MonotoneVertex *vertices; - long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices; - long polystartindex, polyendindex; - TriangulatorPoly *poly; - MonotoneVertex *v,*v2,*vprev,*vnext; - ScanLineEdge newedge; - bool error = false; - - numvertices = 0; - for(iter = inpolys->front(); iter ; iter=iter->next()) { - numvertices += iter->get().GetNumPoints(); - } - - maxnumvertices = numvertices*3; - vertices = new MonotoneVertex[maxnumvertices]; - newnumvertices = numvertices; - - polystartindex = 0; - for(iter = inpolys->front(); iter ; iter=iter->next()) { - poly = &(iter->get()); - polyendindex = polystartindex + poly->GetNumPoints()-1; - for(i=0;i<poly->GetNumPoints();i++) { - vertices[i+polystartindex].p = poly->GetPoint(i); - if(i==0) vertices[i+polystartindex].previous = polyendindex; - else vertices[i+polystartindex].previous = i+polystartindex-1; - if(i==(poly->GetNumPoints()-1)) vertices[i+polystartindex].next = polystartindex; - else vertices[i+polystartindex].next = i+polystartindex+1; - } - polystartindex = polyendindex+1; - } - - //construct the priority queue - long *priority = new long [numvertices]; - for(i=0;i<numvertices;i++) priority[i] = i; - SortArray<long,VertexSorter> sorter; - sorter.compare.vertices=vertices; - sorter.sort(priority,numvertices); - - //determine vertex types - char *vertextypes = new char[maxnumvertices]; - for(i=0;i<numvertices;i++) { - v = &(vertices[i]); - vprev = &(vertices[v->previous]); - vnext = &(vertices[v->next]); - - if(Below(vprev->p,v->p)&&Below(vnext->p,v->p)) { - if(IsConvex(vnext->p,vprev->p,v->p)) { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_START; - } else { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_SPLIT; - } - } else if(Below(v->p,vprev->p)&&Below(v->p,vnext->p)) { - if(IsConvex(vnext->p,vprev->p,v->p)) - { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_END; - } else { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_MERGE; - } - } else { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_REGULAR; - } - } - - //helpers - long *helpers = new long[maxnumvertices]; - - //binary search tree that holds edges intersecting the scanline - //note that while set doesn't actually have to be implemented as a tree - //complexity requirements for operations are the same as for the balanced binary search tree - Set<ScanLineEdge> edgeTree; - //store iterators to the edge tree elements - //this makes deleting existing edges much faster - Set<ScanLineEdge>::Element **edgeTreeIterators,*edgeIter; - edgeTreeIterators = new Set<ScanLineEdge>::Element*[maxnumvertices]; - //Pair<Set<ScanLineEdge>::Element*,bool> edgeTreeRet; - for(i = 0; i<numvertices; i++) edgeTreeIterators[i] = NULL; - - //for each vertex - for(i=0;i<numvertices;i++) { - vindex = priority[i]; - v = &(vertices[vindex]); - vindex2 = vindex; - v2 = v; - - //depending on the vertex type, do the appropriate action - //comments in the following sections are copied from "Computational Geometry: Algorithms and Applications" - switch(vertextypes[vindex]) { - case TRIANGULATOR_VERTEXTYPE_START: - //Insert ei in T and set helper(ei) to vi. - newedge.p1 = v->p; - newedge.p2 = vertices[v->next].p; - newedge.index = vindex; - edgeTreeIterators[vindex] = edgeTree.insert(newedge); - helpers[vindex] = vindex; - break; - - case TRIANGULATOR_VERTEXTYPE_END: - //if helper(ei-1) is a merge vertex - if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(ei-1) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - } - //Delete ei-1 from T - edgeTree.erase(edgeTreeIterators[v->previous]); - break; - - case TRIANGULATOR_VERTEXTYPE_SPLIT: - //Search in T to find the edge e j directly left of vi. - newedge.p1 = v->p; - newedge.p2 = v->p; - edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.front()) { - error = true; - break; - } - edgeIter=edgeIter->prev(); - //Insert the diagonal connecting vi to helper(ej) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - vindex2 = newnumvertices-2; - v2 = &(vertices[vindex2]); - //helper(e j)�vi - helpers[edgeIter->get().index] = vindex; - //Insert ei in T and set helper(ei) to vi. - newedge.p1 = v2->p; - newedge.p2 = vertices[v2->next].p; - newedge.index = vindex2; - - edgeTreeIterators[vindex2] = edgeTree.insert(newedge); - helpers[vindex2] = vindex2; - break; - - case TRIANGULATOR_VERTEXTYPE_MERGE: - //if helper(ei-1) is a merge vertex - if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(ei-1) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - vindex2 = newnumvertices-2; - v2 = &(vertices[vindex2]); - } - //Delete ei-1 from T. - edgeTree.erase(edgeTreeIterators[v->previous]); - //Search in T to find the edge e j directly left of vi. - newedge.p1 = v->p; - newedge.p2 = v->p; - edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.front()) { - error = true; - break; - } - edgeIter=edgeIter->prev(); - //if helper(ej) is a merge vertex - if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(e j) in D. - AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->get().index], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - } - //helper(e j)�vi - helpers[edgeIter->get().index] = vindex2; - break; - - case TRIANGULATOR_VERTEXTYPE_REGULAR: - //if the interior of P lies to the right of vi - if(Below(v->p,vertices[v->previous].p)) { - //if helper(ei-1) is a merge vertex - if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(ei-1) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - vindex2 = newnumvertices-2; - v2 = &(vertices[vindex2]); - } - //Delete ei-1 from T. - edgeTree.erase(edgeTreeIterators[v->previous]); - //Insert ei in T and set helper(ei) to vi. - newedge.p1 = v2->p; - newedge.p2 = vertices[v2->next].p; - newedge.index = vindex2; - edgeTreeIterators[vindex2] = edgeTree.insert(newedge); - helpers[vindex2] = vindex; - } else { - //Search in T to find the edge ej directly left of vi. - newedge.p1 = v->p; - newedge.p2 = v->p; - edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.front()) { - error = true; - break; - } - edgeIter=edgeIter->prev(); - //if helper(ej) is a merge vertex - if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(e j) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - } - //helper(e j)�vi - helpers[edgeIter->get().index] = vindex; - } - break; - } - - if(error) break; - } - - char *used = new char[newnumvertices]; - memset(used,0,newnumvertices*sizeof(char)); - - if(!error) { - //return result - long size; - TriangulatorPoly mpoly; - for(i=0;i<newnumvertices;i++) { - if(used[i]) continue; - v = &(vertices[i]); - vnext = &(vertices[v->next]); - size = 1; - while(vnext!=v) { - vnext = &(vertices[vnext->next]); - size++; - } - mpoly.Init(size); - v = &(vertices[i]); - mpoly[0] = v->p; - vnext = &(vertices[v->next]); - size = 1; - used[i] = 1; - used[v->next] = 1; - while(vnext!=v) { - mpoly[size] = vnext->p; - used[vnext->next] = 1; - vnext = &(vertices[vnext->next]); - size++; - } - monotonePolys->push_back(mpoly); - } - } - - //cleanup - delete [] vertices; - delete [] priority; - delete [] vertextypes; - delete [] edgeTreeIterators; - delete [] helpers; - delete [] used; - - if(error) { - return 0; - } else { - return 1; - } -} - -//adds a diagonal to the doubly-connected list of vertices -void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, - char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, - Set<ScanLineEdge> *edgeTree, long *helpers) -{ - long newindex1,newindex2; - - newindex1 = *numvertices; - (*numvertices)++; - newindex2 = *numvertices; - (*numvertices)++; - - vertices[newindex1].p = vertices[index1].p; - vertices[newindex2].p = vertices[index2].p; - - vertices[newindex2].next = vertices[index2].next; - vertices[newindex1].next = vertices[index1].next; - - vertices[vertices[index2].next].previous = newindex2; - vertices[vertices[index1].next].previous = newindex1; - - vertices[index1].next = newindex2; - vertices[newindex2].previous = index1; - - vertices[index2].next = newindex1; - vertices[newindex1].previous = index2; - - //update all relevant structures - vertextypes[newindex1] = vertextypes[index1]; - edgeTreeIterators[newindex1] = edgeTreeIterators[index1]; - helpers[newindex1] = helpers[index1]; - if(edgeTreeIterators[newindex1] != NULL) - edgeTreeIterators[newindex1]->get().index = newindex1; - vertextypes[newindex2] = vertextypes[index2]; - edgeTreeIterators[newindex2] = edgeTreeIterators[index2]; - helpers[newindex2] = helpers[index2]; - if(edgeTreeIterators[newindex2] != NULL) - edgeTreeIterators[newindex2]->get().index = newindex2; -} - -bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) { - if(p1.y < p2.y) return true; - else if(p1.y == p2.y) { - if(p1.x < p2.x) return true; - } - return false; -} - - - - - -//sorts in the falling order of y values, if y is equal, x is used instead -bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) const { - if(vertices[index1].p.y > vertices[index2].p.y) return true; - else if(vertices[index1].p.y == vertices[index2].p.y) { - if(vertices[index1].p.x > vertices[index2].p.x) return true; - } - return false; -} - -bool TriangulatorPartition::ScanLineEdge::IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const { - real_t tmp; - tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); - if(tmp>0) return 1; - else return 0; -} - -bool TriangulatorPartition::ScanLineEdge::operator < (const ScanLineEdge & other) const { - if(other.p1.y == other.p2.y) { - if(p1.y == p2.y) { - if(p1.y < other.p1.y) return true; - else return false; - } - if(IsConvex(p1,p2,other.p1)) return true; - else return false; - } else if(p1.y == p2.y) { - if(IsConvex(other.p1,other.p2,p1)) return false; - else return true; - } else if(p1.y < other.p1.y) { - if(IsConvex(other.p1,other.p2,p1)) return false; - else return true; - } else { - if(IsConvex(p1,p2,other.p1)) return true; - else return false; - } -} - -//triangulates monotone polygon -//O(n) time, O(n) space complexity -int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles) { - long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex; - Vector2 *points; - long numpoints; - TriangulatorPoly triangle; - - numpoints = inPoly->GetNumPoints(); - points = inPoly->GetPoints(); - - //trivial calses - if(numpoints < 3) return 0; - if(numpoints == 3) { - triangles->push_back(*inPoly); - } - - topindex = 0; bottomindex=0; - for(i=1;i<numpoints;i++) { - if(Below(points[i],points[bottomindex])) bottomindex = i; - if(Below(points[topindex],points[i])) topindex = i; - } - - //check if the poly is really monotone - i = topindex; - while(i!=bottomindex) { - i2 = i+1; if(i2>=numpoints) i2 = 0; - if(!Below(points[i2],points[i])) return 0; - i = i2; - } - i = bottomindex; - while(i!=topindex) { - i2 = i+1; if(i2>=numpoints) i2 = 0; - if(!Below(points[i],points[i2])) return 0; - i = i2; - } - - char *vertextypes = new char[numpoints]; - long *priority = new long[numpoints]; - - //merge left and right vertex chains - priority[0] = topindex; - vertextypes[topindex] = 0; - leftindex = topindex+1; if(leftindex>=numpoints) leftindex = 0; - rightindex = topindex-1; if(rightindex<0) rightindex = numpoints-1; - for(i=1;i<(numpoints-1);i++) { - if(leftindex==bottomindex) { - priority[i] = rightindex; - rightindex--; if(rightindex<0) rightindex = numpoints-1; - vertextypes[priority[i]] = -1; - } else if(rightindex==bottomindex) { - priority[i] = leftindex; - leftindex++; if(leftindex>=numpoints) leftindex = 0; - vertextypes[priority[i]] = 1; - } else { - if(Below(points[leftindex],points[rightindex])) { - priority[i] = rightindex; - rightindex--; if(rightindex<0) rightindex = numpoints-1; - vertextypes[priority[i]] = -1; - } else { - priority[i] = leftindex; - leftindex++; if(leftindex>=numpoints) leftindex = 0; - vertextypes[priority[i]] = 1; - } - } - } - priority[i] = bottomindex; - vertextypes[bottomindex] = 0; - - long *stack = new long[numpoints]; - long stackptr = 0; - - stack[0] = priority[0]; - stack[1] = priority[1]; - stackptr = 2; - - //for each vertex from top to bottom trim as many triangles as possible - for(i=2;i<(numpoints-1);i++) { - vindex = priority[i]; - if(vertextypes[vindex]!=vertextypes[stack[stackptr-1]]) { - for(j=0;j<(stackptr-1);j++) { - if(vertextypes[vindex]==1) { - triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]); - } else { - triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]); - } - triangles->push_back(triangle); - } - stack[0] = priority[i-1]; - stack[1] = priority[i]; - stackptr = 2; - } else { - stackptr--; - while(stackptr>0) { - if(vertextypes[vindex]==1) { - if(IsConvex(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]])) { - triangle.Triangle(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]]); - triangles->push_back(triangle); - stackptr--; - } else { - break; - } - } else { - if(IsConvex(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]])) { - triangle.Triangle(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]]); - triangles->push_back(triangle); - stackptr--; - } else { - break; - } - } - } - stackptr++; - stack[stackptr] = vindex; - stackptr++; - } - } - vindex = priority[i]; - for(j=0;j<(stackptr-1);j++) { - if(vertextypes[stack[j+1]]==1) { - triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]); - } else { - triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]); - } - triangles->push_back(triangle); - } - - delete [] priority; - delete [] vertextypes; - delete [] stack; - - return 1; -} - -int TriangulatorPartition::Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) { - List<TriangulatorPoly> monotone; - List<TriangulatorPoly>::Element* iter; - - if(!MonotonePartition(inpolys,&monotone)) return 0; - for(iter = monotone.front(); iter;iter=iter->next()) { - if(!TriangulateMonotone(&(iter->get()),triangles)) return 0; - } - return 1; -} - -int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) { - List<TriangulatorPoly> polys; - polys.push_back(*poly); - - return Triangulate_MONO(&polys, triangles); -} diff --git a/thirdparty/misc/triangulator.h b/thirdparty/misc/triangulator.h deleted file mode 100644 index 24b79e7d34..0000000000 --- a/thirdparty/misc/triangulator.h +++ /dev/null @@ -1,306 +0,0 @@ -//Copyright (C) 2011 by Ivan Fratric -// -//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. - -#ifndef TRIANGULATOR_H -#define TRIANGULATOR_H - -#include "core/templates/list.h" -#include "core/math/vector2.h" -#include "core/templates/set.h" - -//2D point structure - -#define TRIANGULATOR_CCW 1 -#define TRIANGULATOR_CW -1 -//Polygon implemented as an array of points with a 'hole' flag -class TriangulatorPoly { -protected: - - - - Vector2 *points; - long numpoints; - bool hole; - -public: - - //constructors/destructors - TriangulatorPoly(); - ~TriangulatorPoly(); - - TriangulatorPoly(const TriangulatorPoly &src); - TriangulatorPoly& operator=(const TriangulatorPoly &src); - - //getters and setters - long GetNumPoints() { - return numpoints; - } - - bool IsHole() { - return hole; - } - - void SetHole(bool hole) { - this->hole = hole; - } - - Vector2 &GetPoint(long i) { - return points[i]; - } - - Vector2 *GetPoints() { - return points; - } - - Vector2& operator[] (int i) { - return points[i]; - } - - //clears the polygon points - void Clear(); - - //inits the polygon with numpoints vertices - void Init(long numpoints); - - //creates a triangle with points p1,p2,p3 - void Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3); - - //inverts the orfer of vertices - void Invert(); - - //returns the orientation of the polygon - //possible values: - // Triangulator_CCW : polygon vertices are in counter-clockwise order - // Triangulator_CW : polygon vertices are in clockwise order - // 0 : the polygon has no (measurable) area - int GetOrientation(); - - //sets the polygon orientation - //orientation can be - // Triangulator_CCW : sets vertices in counter-clockwise order - // Triangulator_CW : sets vertices in clockwise order - void SetOrientation(int orientation); -}; - -class TriangulatorPartition { -protected: - struct PartitionVertex { - bool isActive; - bool isConvex; - bool isEar; - - Vector2 p; - real_t angle; - PartitionVertex *previous; - PartitionVertex *next; - }; - - struct MonotoneVertex { - Vector2 p; - long previous; - long next; - }; - - struct VertexSorter{ - mutable MonotoneVertex *vertices; - bool operator() (long index1, long index2) const; - }; - - struct Diagonal { - long index1; - long index2; - }; - - //dynamic programming state for minimum-weight triangulation - struct DPState { - bool visible; - real_t weight; - long bestvertex; - }; - - //dynamic programming state for convex partitioning - struct DPState2 { - bool visible; - long weight; - List<Diagonal> pairs; - }; - - //edge that intersects the scanline - struct ScanLineEdge { - mutable long index; - Vector2 p1; - Vector2 p2; - - //determines if the edge is to the left of another edge - bool operator< (const ScanLineEdge & other) const; - - bool IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const; - }; - - //standard helper functions - bool IsConvex(Vector2& p1, Vector2& p2, Vector2& p3); - bool IsReflex(Vector2& p1, Vector2& p2, Vector2& p3); - bool IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p); - - bool InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p); - bool InCone(PartitionVertex *v, Vector2 &p); - - int Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22); - - Vector2 Normalize(const Vector2 &p); - real_t Distance(const Vector2 &p1, const Vector2 &p2); - - //helper functions for Triangulate_EC - void UpdateVertexReflexity(PartitionVertex *v); - void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices); - - //helper functions for ConvexPartition_OPT - void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates); - void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); - void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); - - //helper functions for MonotonePartition - bool Below(Vector2 &p1, Vector2 &p2); - void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, - char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, - Set<ScanLineEdge> *edgeTree, long *helpers); - - //triangulates a monotone polygon, used in Triangulate_MONO - int TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles); - -public: - - //simple heuristic procedure for removing holes from a list of polygons - //works by creating a diagonal from the rightmost hole vertex to some visible vertex - //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons that can contain holes - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // outpolys : a list of polygons without holes - //returns 1 on success, 0 on failure - int RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys); - - //triangulates a polygon by ear clipping - //time complexity O(n^2), n is the number of vertices - //space complexity: O(n) - //params: - // poly : an input polygon to be triangulated - // vertices have to be in counter-clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles); - - //triangulates a list of polygons that may contain holes by ear clipping algorithm - //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon - //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons to be triangulated (can contain holes) - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles); - - //creates an optimal polygon triangulation in terms of minimal edge length - //time complexity: O(n^3), n is the number of vertices - //space complexity: O(n^2) - //params: - // poly : an input polygon to be triangulated - // vertices have to be in counter-clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles); - - //triangulates a polygons by firstly partitioning it into monotone polygons - //time complexity: O(n*log(n)), n is the number of vertices - //space complexity: O(n) - //params: - // poly : an input polygon to be triangulated - // vertices have to be in counter-clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles); - - //triangulates a list of polygons by firstly partitioning them into monotone polygons - //time complexity: O(n*log(n)), n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons to be triangulated (can contain holes) - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles); - - //creates a monotone partition of a list of polygons that can contain holes - //time complexity: O(n*log(n)), n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons to be triangulated (can contain holes) - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // monotonePolys : a list of monotone polygons (result) - //returns 1 on success, 0 on failure - int MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys); - - //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm - //the algorithm gives at most four times the number of parts as the optimal algorithm - //however, in practice it works much better than that and often gives optimal partition - //uses triangulation obtained by ear clipping as intermediate result - //time complexity O(n^2), n is the number of vertices - //space complexity: O(n) - //params: - // poly : an input polygon to be partitioned - // vertices have to be in counter-clockwise order - // parts : resulting list of convex polygons - //returns 1 on success, 0 on failure - int ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts); - - //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm - //the algorithm gives at most four times the number of parts as the optimal algorithm - //however, in practice it works much better than that and often gives optimal partition - //uses triangulation obtained by ear clipping as intermediate result - //time complexity O(n^2), n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : an input list of polygons to be partitioned - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // parts : resulting list of convex polygons - //returns 1 on success, 0 on failure - int ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts); - - //optimal convex partitioning (in terms of number of resulting convex polygons) - //using the Keil-Snoeyink algorithm - //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998 - //time complexity O(n^3), n is the number of vertices - //space complexity: O(n^3) - // poly : an input polygon to be partitioned - // vertices have to be in counter-clockwise order - // parts : resulting list of convex polygons - //returns 1 on success, 0 on failure - int ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts); -}; - - -#endif |