diff options
63 files changed, 3779 insertions, 354 deletions
diff --git a/COPYRIGHT.txt b/COPYRIGHT.txt index eb82c42e6f..c007a7e2b3 100644 --- a/COPYRIGHT.txt +++ b/COPYRIGHT.txt @@ -55,6 +55,14 @@ Comment: Godot Engine logo Copyright: 2017, Andrea Calabró License: CC-BY-4.0 +Files: ./core/math/convex_hull.cpp + ./core/math/convex_hull.h +Comment: Bullet Continuous Collision Detection and Physics Library +Copyright: 2011, Ole Kniemeyer, MAXON, www.maxon.net + 2007-2021, Juan Linietsky, Ariel Manzur. + 2014-2021, Godot Engine contributors. +License: Expat and Zlib + Files: ./modules/fbx/fbx_parser/ Comment: Open Asset Import Library (FBX parser) Copyright: 2006-2020, assimp team diff --git a/core/input/input_map.cpp b/core/input/input_map.cpp index 424509eb47..a43ad4ed7d 100644 --- a/core/input/input_map.cpp +++ b/core/input/input_map.cpp @@ -353,6 +353,7 @@ static const _BuiltinActionDisplayName _builtin_action_display_names[] = { { "ui_text_scroll_down", TTRC("Scroll Down") }, { "ui_text_scroll_down.OSX", TTRC("Scroll Down") }, { "ui_text_select_all", TTRC("Select All") }, + { "ui_text_select_word_under_caret", TTRC("Select Word Under Caret") }, { "ui_text_toggle_insert_mode", TTRC("Toggle Insert Mode") }, { "ui_graph_duplicate", TTRC("Duplicate Nodes") }, { "ui_graph_delete", TTRC("Delete Nodes") }, @@ -651,6 +652,10 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() { default_builtin_cache.insert("ui_text_select_all", inputs); inputs = List<Ref<InputEvent>>(); + inputs.push_back(InputEventKey::create_reference(KEY_D | KEY_MASK_CMD)); + default_builtin_cache.insert("ui_text_select_word_under_caret", inputs); + + inputs = List<Ref<InputEvent>>(); inputs.push_back(InputEventKey::create_reference(KEY_INSERT)); default_builtin_cache.insert("ui_text_toggle_insert_mode", inputs); diff --git a/core/io/file_access_zip.cpp b/core/io/file_access_zip.cpp index 304e24ee90..d7ff1b7e00 100644 --- a/core/io/file_access_zip.cpp +++ b/core/io/file_access_zip.cpp @@ -226,9 +226,7 @@ ZipArchive::ZipArchive() { ZipArchive::~ZipArchive() { for (int i = 0; i < packages.size(); i++) { - FileAccess *f = (FileAccess *)unzGetOpaque(packages[i].zfile); unzClose(packages[i].zfile); - memdelete(f); } packages.clear(); diff --git a/core/math/convex_hull.cpp b/core/math/convex_hull.cpp new file mode 100644 index 0000000000..682a7ea39e --- /dev/null +++ b/core/math/convex_hull.cpp @@ -0,0 +1,2290 @@ +/*************************************************************************/ +/* convex_hull.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2021 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +/* + * Based on Godot's patched VHACD-version of Bullet's btConvexHullComputer. + * See /thirdparty/vhacd/btConvexHullComputer.cpp at 64403ddcab9f1dca2408f0a412a22d899708bbb1 + * In turn, based on /src/LinearMath/btConvexHullComputer.cpp in <https://github.com/bulletphysics/bullet3> + * at 73b217fb07e7e3ce126caeb28ab3c9ddd0718467 + * + * Changes: + * - int32_t is consistently used instead of int in some cases + * - integrated patch db0d6c92927f5a1358b887f2645c11f3014f0e8a from Bullet (CWE-190 integer overflow in btConvexHullComputer) + * - adapted to Godot's code style + * - replaced Bullet's types (e.g. vectors) with Godot's + * - replaced custom Pool implementation with PagedAllocator + */ + +/* +Copyright (c) 2011 Ole Kniemeyer, MAXON, www.maxon.net + +This software is provided 'as-is', without any express or implied warranty. +In no event will the authors be held liable for any damages arising from the use of this software. +Permission is granted to anyone to use this software for any purpose, +including commercial applications, and to alter it and redistribute it freely, +subject to the following restrictions: + +1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. +2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. +3. This notice may not be removed or altered from any source distribution. +*/ + +#include "convex_hull.h" + +#include "core/error/error_macros.h" +#include "core/math/aabb.h" +#include "core/math/math_defs.h" +#include "core/os/memory.h" +#include "core/templates/paged_allocator.h" + +#include <string.h> + +//#define DEBUG_CONVEX_HULL +//#define SHOW_ITERATIONS + +// -- GODOT start -- +// Assembly optimizations are not used at the moment. +//#define USE_X86_64_ASM +// -- GODOT end -- + +#ifdef DEBUG_ENABLED +#define CHULL_ASSERT(m_cond) \ + do { \ + if (unlikely(!(m_cond))) { \ + ERR_PRINT("Assertion \"" _STR(m_cond) "\" failed."); \ + } \ + } while (0) +#else +#define CHULL_ASSERT(m_cond) \ + do { \ + } while (0) +#endif + +#if defined(DEBUG_CONVEX_HULL) || defined(SHOW_ITERATIONS) +#include <stdio.h> +#endif + +// Convex hull implementation based on Preparata and Hong +// Ole Kniemeyer, MAXON Computer GmbH +class ConvexHullInternal { +public: + class Point64 { + public: + int64_t x; + int64_t y; + int64_t z; + + Point64(int64_t p_x, int64_t p_y, int64_t p_z) { + x = p_x; + y = p_y; + z = p_z; + } + + bool is_zero() { + return (x == 0) && (y == 0) && (z == 0); + } + + int64_t dot(const Point64 &b) const { + return x * b.x + y * b.y + z * b.z; + } + }; + + class Point32 { + public: + int32_t x = 0; + int32_t y = 0; + int32_t z = 0; + int32_t index = -1; + + Point32() { + } + + Point32(int32_t p_x, int32_t p_y, int32_t p_z) { + x = p_x; + y = p_y; + z = p_z; + } + + bool operator==(const Point32 &b) const { + return (x == b.x) && (y == b.y) && (z == b.z); + } + + bool operator!=(const Point32 &b) const { + return (x != b.x) || (y != b.y) || (z != b.z); + } + + bool is_zero() { + return (x == 0) && (y == 0) && (z == 0); + } + + Point64 cross(const Point32 &b) const { + return Point64((int64_t)y * b.z - (int64_t)z * b.y, (int64_t)z * b.x - (int64_t)x * b.z, (int64_t)x * b.y - (int64_t)y * b.x); + } + + Point64 cross(const Point64 &b) const { + return Point64(y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x); + } + + int64_t dot(const Point32 &b) const { + return (int64_t)x * b.x + (int64_t)y * b.y + (int64_t)z * b.z; + } + + int64_t dot(const Point64 &b) const { + return x * b.x + y * b.y + z * b.z; + } + + Point32 operator+(const Point32 &b) const { + return Point32(x + b.x, y + b.y, z + b.z); + } + + Point32 operator-(const Point32 &b) const { + return Point32(x - b.x, y - b.y, z - b.z); + } + }; + + class Int128 { + public: + uint64_t low = 0; + uint64_t high = 0; + + Int128() { + } + + Int128(uint64_t p_low, uint64_t p_high) { + low = p_low; + high = p_high; + } + + Int128(uint64_t p_low) { + low = p_low; + high = 0; + } + + Int128(int64_t p_value) { + low = p_value; + if (p_value >= 0) { + high = 0; + } else { + high = (uint64_t)-1LL; + } + } + + static Int128 mul(int64_t a, int64_t b); + + static Int128 mul(uint64_t a, uint64_t b); + + Int128 operator-() const { + return Int128((uint64_t) - (int64_t)low, ~high + (low == 0)); + } + + Int128 operator+(const Int128 &b) const { +#ifdef USE_X86_64_ASM + Int128 result; + __asm__("addq %[bl], %[rl]\n\t" + "adcq %[bh], %[rh]\n\t" + : [rl] "=r"(result.low), [rh] "=r"(result.high) + : "0"(low), "1"(high), [bl] "g"(b.low), [bh] "g"(b.high) + : "cc"); + return result; +#else + uint64_t lo = low + b.low; + return Int128(lo, high + b.high + (lo < low)); +#endif + } + + Int128 operator-(const Int128 &b) const { +#ifdef USE_X86_64_ASM + Int128 result; + __asm__("subq %[bl], %[rl]\n\t" + "sbbq %[bh], %[rh]\n\t" + : [rl] "=r"(result.low), [rh] "=r"(result.high) + : "0"(low), "1"(high), [bl] "g"(b.low), [bh] "g"(b.high) + : "cc"); + return result; +#else + return *this + -b; +#endif + } + + Int128 &operator+=(const Int128 &b) { +#ifdef USE_X86_64_ASM + __asm__("addq %[bl], %[rl]\n\t" + "adcq %[bh], %[rh]\n\t" + : [rl] "=r"(low), [rh] "=r"(high) + : "0"(low), "1"(high), [bl] "g"(b.low), [bh] "g"(b.high) + : "cc"); +#else + uint64_t lo = low + b.low; + if (lo < low) { + ++high; + } + low = lo; + high += b.high; +#endif + return *this; + } + + Int128 &operator++() { + if (++low == 0) { + ++high; + } + return *this; + } + + Int128 operator*(int64_t b) const; + + real_t to_scalar() const { + return ((int64_t)high >= 0) ? real_t(high) * (real_t(0x100000000LL) * real_t(0x100000000LL)) + real_t(low) : -(-*this).to_scalar(); + } + + int32_t get_sign() const { + return ((int64_t)high < 0) ? -1 : (high || low) ? 1 : + 0; + } + + bool operator<(const Int128 &b) const { + return (high < b.high) || ((high == b.high) && (low < b.low)); + } + + int32_t ucmp(const Int128 &b) const { + if (high < b.high) { + return -1; + } + if (high > b.high) { + return 1; + } + if (low < b.low) { + return -1; + } + if (low > b.low) { + return 1; + } + return 0; + } + }; + + class Rational64 { + private: + uint64_t numerator; + uint64_t denominator; + int32_t sign; + + public: + Rational64(int64_t p_numerator, int64_t p_denominator) { + if (p_numerator > 0) { + sign = 1; + numerator = (uint64_t)p_numerator; + } else if (p_numerator < 0) { + sign = -1; + numerator = (uint64_t)-p_numerator; + } else { + sign = 0; + numerator = 0; + } + if (p_denominator > 0) { + denominator = (uint64_t)p_denominator; + } else if (p_denominator < 0) { + sign = -sign; + denominator = (uint64_t)-p_denominator; + } else { + denominator = 0; + } + } + + bool is_negative_infinity() const { + return (sign < 0) && (denominator == 0); + } + + bool is_nan() const { + return (sign == 0) && (denominator == 0); + } + + int32_t compare(const Rational64 &b) const; + + real_t to_scalar() const { + return sign * ((denominator == 0) ? FLT_MAX : (real_t)numerator / denominator); + } + }; + + class Rational128 { + private: + Int128 numerator; + Int128 denominator; + int32_t sign; + bool is_int_64; + + public: + Rational128(int64_t p_value) { + if (p_value > 0) { + sign = 1; + this->numerator = p_value; + } else if (p_value < 0) { + sign = -1; + this->numerator = -p_value; + } else { + sign = 0; + this->numerator = (uint64_t)0; + } + this->denominator = (uint64_t)1; + is_int_64 = true; + } + + Rational128(const Int128 &p_numerator, const Int128 &p_denominator) { + sign = p_numerator.get_sign(); + if (sign >= 0) { + this->numerator = p_numerator; + } else { + this->numerator = -p_numerator; + } + int32_t dsign = p_denominator.get_sign(); + if (dsign >= 0) { + this->denominator = p_denominator; + } else { + sign = -sign; + this->denominator = -p_denominator; + } + is_int_64 = false; + } + + int32_t compare(const Rational128 &b) const; + + int32_t compare(int64_t b) const; + + real_t to_scalar() const { + return sign * ((denominator.get_sign() == 0) ? FLT_MAX : numerator.to_scalar() / denominator.to_scalar()); + } + }; + + class PointR128 { + public: + Int128 x; + Int128 y; + Int128 z; + Int128 denominator; + + PointR128() { + } + + PointR128(Int128 p_x, Int128 p_y, Int128 p_z, Int128 p_denominator) { + x = p_x; + y = p_y; + z = p_z; + denominator = p_denominator; + } + + real_t xvalue() const { + return x.to_scalar() / denominator.to_scalar(); + } + + real_t yvalue() const { + return y.to_scalar() / denominator.to_scalar(); + } + + real_t zvalue() const { + return z.to_scalar() / denominator.to_scalar(); + } + }; + + class Edge; + class Face; + + class Vertex { + public: + Vertex *next = nullptr; + Vertex *prev = nullptr; + Edge *edges = nullptr; + Face *first_nearby_face = nullptr; + Face *last_nearby_face = nullptr; + PointR128 point128; + Point32 point; + int32_t copy = -1; + + Vertex() { + } + +#ifdef DEBUG_CONVEX_HULL + void print() { + printf("V%d (%d, %d, %d)", point.index, point.x, point.y, point.z); + } + + void print_graph(); +#endif + + Point32 operator-(const Vertex &b) const { + return point - b.point; + } + + Rational128 dot(const Point64 &b) const { + return (point.index >= 0) ? Rational128(point.dot(b)) : Rational128(point128.x * b.x + point128.y * b.y + point128.z * b.z, point128.denominator); + } + + real_t xvalue() const { + return (point.index >= 0) ? real_t(point.x) : point128.xvalue(); + } + + real_t yvalue() const { + return (point.index >= 0) ? real_t(point.y) : point128.yvalue(); + } + + real_t zvalue() const { + return (point.index >= 0) ? real_t(point.z) : point128.zvalue(); + } + + void receive_nearby_faces(Vertex *p_src) { + if (last_nearby_face) { + last_nearby_face->next_with_same_nearby_vertex = p_src->first_nearby_face; + } else { + first_nearby_face = p_src->first_nearby_face; + } + if (p_src->last_nearby_face) { + last_nearby_face = p_src->last_nearby_face; + } + for (Face *f = p_src->first_nearby_face; f; f = f->next_with_same_nearby_vertex) { + CHULL_ASSERT(f->nearby_vertex == p_src); + f->nearby_vertex = this; + } + p_src->first_nearby_face = nullptr; + p_src->last_nearby_face = nullptr; + } + }; + + class Edge { + public: + Edge *next = nullptr; + Edge *prev = nullptr; + Edge *reverse = nullptr; + Vertex *target = nullptr; + Face *face = nullptr; + int32_t copy = -1; + + void link(Edge *n) { + CHULL_ASSERT(reverse->target == n->reverse->target); + next = n; + n->prev = this; + } + +#ifdef DEBUG_CONVEX_HULL + void print() { + printf("E%p : %d -> %d, n=%p p=%p (0 %d\t%d\t%d) -> (%d %d %d)", this, reverse->target->point.index, target->point.index, next, prev, + reverse->target->point.x, reverse->target->point.y, reverse->target->point.z, target->point.x, target->point.y, target->point.z); + } +#endif + }; + + class Face { + public: + Face *next = nullptr; + Vertex *nearby_vertex = nullptr; + Face *next_with_same_nearby_vertex = nullptr; + Point32 origin; + Point32 dir0; + Point32 dir1; + + Face() { + } + + void init(Vertex *p_a, Vertex *p_b, Vertex *p_c) { + nearby_vertex = p_a; + origin = p_a->point; + dir0 = *p_b - *p_a; + dir1 = *p_c - *p_a; + if (p_a->last_nearby_face) { + p_a->last_nearby_face->next_with_same_nearby_vertex = this; + } else { + p_a->first_nearby_face = this; + } + p_a->last_nearby_face = this; + } + + Point64 get_normal() { + return dir0.cross(dir1); + } + }; + + template <typename UWord, typename UHWord> + class DMul { + private: + static uint32_t high(uint64_t p_value) { + return (uint32_t)(p_value >> 32); + } + + static uint32_t low(uint64_t p_value) { + return (uint32_t)p_value; + } + + static uint64_t mul(uint32_t a, uint32_t b) { + return (uint64_t)a * (uint64_t)b; + } + + static void shl_half(uint64_t &p_value) { + p_value <<= 32; + } + + static uint64_t high(Int128 p_value) { + return p_value.high; + } + + static uint64_t low(Int128 p_value) { + return p_value.low; + } + + static Int128 mul(uint64_t a, uint64_t b) { + return Int128::mul(a, b); + } + + static void shl_half(Int128 &p_value) { + p_value.high = p_value.low; + p_value.low = 0; + } + + public: + static void mul(UWord p_a, UWord p_b, UWord &r_low, UWord &r_high) { + UWord p00 = mul(low(p_a), low(p_b)); + UWord p01 = mul(low(p_a), high(p_b)); + UWord p10 = mul(high(p_a), low(p_b)); + UWord p11 = mul(high(p_a), high(p_b)); + UWord p0110 = UWord(low(p01)) + UWord(low(p10)); + p11 += high(p01); + p11 += high(p10); + p11 += high(p0110); + shl_half(p0110); + p00 += p0110; + if (p00 < p0110) { + ++p11; + } + r_low = p00; + r_high = p11; + } + }; + +private: + class IntermediateHull { + public: + Vertex *min_xy = nullptr; + Vertex *max_xy = nullptr; + Vertex *min_yx = nullptr; + Vertex *max_yx = nullptr; + + IntermediateHull() { + } + + void print(); + }; + + enum Orientation { NONE, + CLOCKWISE, + COUNTER_CLOCKWISE }; + + Vector3 scaling; + Vector3 center; + PagedAllocator<Vertex> vertex_pool; + PagedAllocator<Edge> edge_pool; + PagedAllocator<Face> face_pool; + LocalVector<Vertex *> original_vertices; + int32_t merge_stamp = 0; + int32_t min_axis = 0; + int32_t med_axis = 0; + int32_t max_axis = 0; + int32_t used_edge_pairs = 0; + int32_t max_used_edge_pairs = 0; + + static Orientation get_orientation(const Edge *p_prev, const Edge *p_next, const Point32 &p_s, const Point32 &p_t); + Edge *find_max_angle(bool p_ccw, const Vertex *p_start, const Point32 &p_s, const Point64 &p_rxs, const Point64 &p_ssxrxs, Rational64 &p_min_cot); + void find_edge_for_coplanar_faces(Vertex *p_c0, Vertex *p_c1, Edge *&p_e0, Edge *&p_e1, Vertex *p_stop0, Vertex *p_stop1); + + Edge *new_edge_pair(Vertex *p_from, Vertex *p_to); + + void remove_edge_pair(Edge *p_edge) { + Edge *n = p_edge->next; + Edge *r = p_edge->reverse; + + CHULL_ASSERT(p_edge->target && r->target); + + if (n != p_edge) { + n->prev = p_edge->prev; + p_edge->prev->next = n; + r->target->edges = n; + } else { + r->target->edges = nullptr; + } + + n = r->next; + + if (n != r) { + n->prev = r->prev; + r->prev->next = n; + p_edge->target->edges = n; + } else { + p_edge->target->edges = nullptr; + } + + edge_pool.free(p_edge); + edge_pool.free(r); + used_edge_pairs--; + } + + void compute_internal(int32_t p_start, int32_t p_end, IntermediateHull &r_result); + + bool merge_projection(IntermediateHull &p_h0, IntermediateHull &p_h1, Vertex *&r_c0, Vertex *&r_c1); + + void merge(IntermediateHull &p_h0, IntermediateHull &p_h1); + + Vector3 to_gd_vector(const Point32 &p_v); + + Vector3 get_gd_normal(Face *p_face); + + bool shift_face(Face *p_face, real_t p_amount, LocalVector<Vertex *> p_stack); + +public: + ~ConvexHullInternal() { + vertex_pool.reset(true); + edge_pool.reset(true); + face_pool.reset(true); + } + + Vertex *vertex_list; + + void compute(const Vector3 *p_coords, int32_t p_count); + + Vector3 get_coordinates(const Vertex *p_v); + + real_t shrink(real_t amount, real_t p_clamp_amount); +}; + +ConvexHullInternal::Int128 ConvexHullInternal::Int128::operator*(int64_t b) const { + bool negative = (int64_t)high < 0; + Int128 a = negative ? -*this : *this; + if (b < 0) { + negative = !negative; + b = -b; + } + Int128 result = mul(a.low, (uint64_t)b); + result.high += a.high * (uint64_t)b; + return negative ? -result : result; +} + +ConvexHullInternal::Int128 ConvexHullInternal::Int128::mul(int64_t a, int64_t b) { + Int128 result; + +#ifdef USE_X86_64_ASM + __asm__("imulq %[b]" + : "=a"(result.low), "=d"(result.high) + : "0"(a), [b] "r"(b) + : "cc"); + return result; + +#else + bool negative = a < 0; + if (negative) { + a = -a; + } + if (b < 0) { + negative = !negative; + b = -b; + } + DMul<uint64_t, uint32_t>::mul((uint64_t)a, (uint64_t)b, result.low, result.high); + return negative ? -result : result; +#endif +} + +ConvexHullInternal::Int128 ConvexHullInternal::Int128::mul(uint64_t a, uint64_t b) { + Int128 result; + +#ifdef USE_X86_64_ASM + __asm__("mulq %[b]" + : "=a"(result.low), "=d"(result.high) + : "0"(a), [b] "r"(b) + : "cc"); + +#else + DMul<uint64_t, uint32_t>::mul(a, b, result.low, result.high); +#endif + + return result; +} + +int32_t ConvexHullInternal::Rational64::compare(const Rational64 &b) const { + if (sign != b.sign) { + return sign - b.sign; + } else if (sign == 0) { + return 0; + } + + // return (numerator * b.denominator > b.numerator * denominator) ? sign : (numerator * b.denominator < b.numerator * denominator) ? -sign : 0; + +#ifdef USE_X86_64_ASM + + int32_t result; + int64_t tmp; + int64_t dummy; + __asm__("mulq %[bn]\n\t" + "movq %%rax, %[tmp]\n\t" + "movq %%rdx, %%rbx\n\t" + "movq %[tn], %%rax\n\t" + "mulq %[bd]\n\t" + "subq %[tmp], %%rax\n\t" + "sbbq %%rbx, %%rdx\n\t" // rdx:rax contains 128-bit-difference "numerator*b.denominator - b.numerator*denominator" + "setnsb %%bh\n\t" // bh=1 if difference is non-negative, bh=0 otherwise + "orq %%rdx, %%rax\n\t" + "setnzb %%bl\n\t" // bl=1 if difference if non-zero, bl=0 if it is zero + "decb %%bh\n\t" // now bx=0x0000 if difference is zero, 0xff01 if it is negative, 0x0001 if it is positive (i.e., same sign as difference) + "shll $16, %%ebx\n\t" // ebx has same sign as difference + : "=&b"(result), [tmp] "=&r"(tmp), "=a"(dummy) + : "a"(denominator), [bn] "g"(b.numerator), [tn] "g"(numerator), [bd] "g"(b.denominator) + : "%rdx", "cc"); + return result ? result ^ sign // if sign is +1, only bit 0 of result is inverted, which does not change the sign of result (and cannot result in zero) + // if sign is -1, all bits of result are inverted, which changes the sign of result (and again cannot result in zero) + : + 0; + +#else + + return sign * Int128::mul(numerator, b.denominator).ucmp(Int128::mul(denominator, b.numerator)); + +#endif +} + +int32_t ConvexHullInternal::Rational128::compare(const Rational128 &b) const { + if (sign != b.sign) { + return sign - b.sign; + } else if (sign == 0) { + return 0; + } + if (is_int_64) { + return -b.compare(sign * (int64_t)numerator.low); + } + + Int128 nbd_low, nbd_high, dbn_low, dbn_high; + DMul<Int128, uint64_t>::mul(numerator, b.denominator, nbd_low, nbd_high); + DMul<Int128, uint64_t>::mul(denominator, b.numerator, dbn_low, dbn_high); + + int32_t cmp = nbd_high.ucmp(dbn_high); + if (cmp) { + return cmp * sign; + } + return nbd_low.ucmp(dbn_low) * sign; +} + +int32_t ConvexHullInternal::Rational128::compare(int64_t b) const { + if (is_int_64) { + int64_t a = sign * (int64_t)numerator.low; + return (a > b) ? 1 : (a < b) ? -1 : + 0; + } + if (b > 0) { + if (sign <= 0) { + return -1; + } + } else if (b < 0) { + if (sign >= 0) { + return 1; + } + b = -b; + } else { + return sign; + } + + return numerator.ucmp(denominator * b) * sign; +} + +ConvexHullInternal::Edge *ConvexHullInternal::new_edge_pair(Vertex *p_from, Vertex *p_to) { + CHULL_ASSERT(p_from && p_to); + Edge *e = edge_pool.alloc(); + Edge *r = edge_pool.alloc(); + e->reverse = r; + r->reverse = e; + e->copy = merge_stamp; + r->copy = merge_stamp; + e->target = p_to; + r->target = p_from; + e->face = nullptr; + r->face = nullptr; + used_edge_pairs++; + if (used_edge_pairs > max_used_edge_pairs) { + max_used_edge_pairs = used_edge_pairs; + } + return e; +} + +bool ConvexHullInternal::merge_projection(IntermediateHull &r_h0, IntermediateHull &r_h1, Vertex *&r_c0, Vertex *&r_c1) { + Vertex *v0 = r_h0.max_yx; + Vertex *v1 = r_h1.min_yx; + if ((v0->point.x == v1->point.x) && (v0->point.y == v1->point.y)) { + CHULL_ASSERT(v0->point.z < v1->point.z); + Vertex *v1p = v1->prev; + if (v1p == v1) { + r_c0 = v0; + if (v1->edges) { + CHULL_ASSERT(v1->edges->next == v1->edges); + v1 = v1->edges->target; + CHULL_ASSERT(v1->edges->next == v1->edges); + } + r_c1 = v1; + return false; + } + Vertex *v1n = v1->next; + v1p->next = v1n; + v1n->prev = v1p; + if (v1 == r_h1.min_xy) { + if ((v1n->point.x < v1p->point.x) || ((v1n->point.x == v1p->point.x) && (v1n->point.y < v1p->point.y))) { + r_h1.min_xy = v1n; + } else { + r_h1.min_xy = v1p; + } + } + if (v1 == r_h1.max_xy) { + if ((v1n->point.x > v1p->point.x) || ((v1n->point.x == v1p->point.x) && (v1n->point.y > v1p->point.y))) { + r_h1.max_xy = v1n; + } else { + r_h1.max_xy = v1p; + } + } + } + + v0 = r_h0.max_xy; + v1 = r_h1.max_xy; + Vertex *v00 = nullptr; + Vertex *v10 = nullptr; + int32_t sign = 1; + + for (int32_t side = 0; side <= 1; side++) { + int32_t dx = (v1->point.x - v0->point.x) * sign; + if (dx > 0) { + while (true) { + int32_t dy = v1->point.y - v0->point.y; + + Vertex *w0 = side ? v0->next : v0->prev; + if (w0 != v0) { + int32_t dx0 = (w0->point.x - v0->point.x) * sign; + int32_t dy0 = w0->point.y - v0->point.y; + if ((dy0 <= 0) && ((dx0 == 0) || ((dx0 < 0) && (dy0 * dx <= dy * dx0)))) { + v0 = w0; + dx = (v1->point.x - v0->point.x) * sign; + continue; + } + } + + Vertex *w1 = side ? v1->next : v1->prev; + if (w1 != v1) { + int32_t dx1 = (w1->point.x - v1->point.x) * sign; + int32_t dy1 = w1->point.y - v1->point.y; + int32_t dxn = (w1->point.x - v0->point.x) * sign; + if ((dxn > 0) && (dy1 < 0) && ((dx1 == 0) || ((dx1 < 0) && (dy1 * dx < dy * dx1)))) { + v1 = w1; + dx = dxn; + continue; + } + } + + break; + } + } else if (dx < 0) { + while (true) { + int32_t dy = v1->point.y - v0->point.y; + + Vertex *w1 = side ? v1->prev : v1->next; + if (w1 != v1) { + int32_t dx1 = (w1->point.x - v1->point.x) * sign; + int32_t dy1 = w1->point.y - v1->point.y; + if ((dy1 >= 0) && ((dx1 == 0) || ((dx1 < 0) && (dy1 * dx <= dy * dx1)))) { + v1 = w1; + dx = (v1->point.x - v0->point.x) * sign; + continue; + } + } + + Vertex *w0 = side ? v0->prev : v0->next; + if (w0 != v0) { + int32_t dx0 = (w0->point.x - v0->point.x) * sign; + int32_t dy0 = w0->point.y - v0->point.y; + int32_t dxn = (v1->point.x - w0->point.x) * sign; + if ((dxn < 0) && (dy0 > 0) && ((dx0 == 0) || ((dx0 < 0) && (dy0 * dx < dy * dx0)))) { + v0 = w0; + dx = dxn; + continue; + } + } + + break; + } + } else { + int32_t x = v0->point.x; + int32_t y0 = v0->point.y; + Vertex *w0 = v0; + Vertex *t; + while (((t = side ? w0->next : w0->prev) != v0) && (t->point.x == x) && (t->point.y <= y0)) { + w0 = t; + y0 = t->point.y; + } + v0 = w0; + + int32_t y1 = v1->point.y; + Vertex *w1 = v1; + while (((t = side ? w1->prev : w1->next) != v1) && (t->point.x == x) && (t->point.y >= y1)) { + w1 = t; + y1 = t->point.y; + } + v1 = w1; + } + + if (side == 0) { + v00 = v0; + v10 = v1; + + v0 = r_h0.min_xy; + v1 = r_h1.min_xy; + sign = -1; + } + } + + v0->prev = v1; + v1->next = v0; + + v00->next = v10; + v10->prev = v00; + + if (r_h1.min_xy->point.x < r_h0.min_xy->point.x) { + r_h0.min_xy = r_h1.min_xy; + } + if (r_h1.max_xy->point.x >= r_h0.max_xy->point.x) { + r_h0.max_xy = r_h1.max_xy; + } + + r_h0.max_yx = r_h1.max_yx; + + r_c0 = v00; + r_c1 = v10; + + return true; +} + +void ConvexHullInternal::compute_internal(int32_t p_start, int32_t p_end, IntermediateHull &r_result) { + int32_t n = p_end - p_start; + switch (n) { + case 0: + r_result.min_xy = nullptr; + r_result.max_xy = nullptr; + r_result.min_yx = nullptr; + r_result.max_yx = nullptr; + return; + case 2: { + Vertex *v = original_vertices[p_start]; + Vertex *w = original_vertices[p_start + 1]; + if (v->point != w->point) { + int32_t dx = v->point.x - w->point.x; + int32_t dy = v->point.y - w->point.y; + + if ((dx == 0) && (dy == 0)) { + if (v->point.z > w->point.z) { + Vertex *t = w; + w = v; + v = t; + } + CHULL_ASSERT(v->point.z < w->point.z); + v->next = v; + v->prev = v; + r_result.min_xy = v; + r_result.max_xy = v; + r_result.min_yx = v; + r_result.max_yx = v; + } else { + v->next = w; + v->prev = w; + w->next = v; + w->prev = v; + + if ((dx < 0) || ((dx == 0) && (dy < 0))) { + r_result.min_xy = v; + r_result.max_xy = w; + } else { + r_result.min_xy = w; + r_result.max_xy = v; + } + + if ((dy < 0) || ((dy == 0) && (dx < 0))) { + r_result.min_yx = v; + r_result.max_yx = w; + } else { + r_result.min_yx = w; + r_result.max_yx = v; + } + } + + Edge *e = new_edge_pair(v, w); + e->link(e); + v->edges = e; + + e = e->reverse; + e->link(e); + w->edges = e; + + return; + } + [[fallthrough]]; + } + case 1: { + Vertex *v = original_vertices[p_start]; + v->edges = nullptr; + v->next = v; + v->prev = v; + + r_result.min_xy = v; + r_result.max_xy = v; + r_result.min_yx = v; + r_result.max_yx = v; + + return; + } + } + + int32_t split0 = p_start + n / 2; + Point32 p = original_vertices[split0 - 1]->point; + int32_t split1 = split0; + while ((split1 < p_end) && (original_vertices[split1]->point == p)) { + split1++; + } + compute_internal(p_start, split0, r_result); + IntermediateHull hull1; + compute_internal(split1, p_end, hull1); +#ifdef DEBUG_CONVEX_HULL + printf("\n\nMerge\n"); + r_result.print(); + hull1.print(); +#endif + merge(r_result, hull1); +#ifdef DEBUG_CONVEX_HULL + printf("\n Result\n"); + r_result.print(); +#endif +} + +#ifdef DEBUG_CONVEX_HULL +void ConvexHullInternal::IntermediateHull::print() { + printf(" Hull\n"); + for (Vertex *v = min_xy; v;) { + printf(" "); + v->print(); + if (v == max_xy) { + printf(" max_xy"); + } + if (v == min_yx) { + printf(" min_yx"); + } + if (v == max_yx) { + printf(" max_yx"); + } + if (v->next->prev != v) { + printf(" Inconsistency"); + } + printf("\n"); + v = v->next; + if (v == min_xy) { + break; + } + } + if (min_xy) { + min_xy->copy = (min_xy->copy == -1) ? -2 : -1; + min_xy->print_graph(); + } +} + +void ConvexHullInternal::Vertex::print_graph() { + print(); + printf("\nEdges\n"); + Edge *e = edges; + if (e) { + do { + e->print(); + printf("\n"); + e = e->next; + } while (e != edges); + do { + Vertex *v = e->target; + if (v->copy != copy) { + v->copy = copy; + v->print_graph(); + } + e = e->next; + } while (e != edges); + } +} +#endif + +ConvexHullInternal::Orientation ConvexHullInternal::get_orientation(const Edge *p_prev, const Edge *p_next, const Point32 &p_s, const Point32 &p_t) { + CHULL_ASSERT(p_prev->reverse->target == p_next->reverse->target); + if (p_prev->next == p_next) { + if (p_prev->prev == p_next) { + Point64 n = p_t.cross(p_s); + Point64 m = (*p_prev->target - *p_next->reverse->target).cross(*p_next->target - *p_next->reverse->target); + CHULL_ASSERT(!m.is_zero()); + int64_t dot = n.dot(m); + CHULL_ASSERT(dot != 0); + return (dot > 0) ? COUNTER_CLOCKWISE : CLOCKWISE; + } + return COUNTER_CLOCKWISE; + } else if (p_prev->prev == p_next) { + return CLOCKWISE; + } else { + return NONE; + } +} + +ConvexHullInternal::Edge *ConvexHullInternal::find_max_angle(bool p_ccw, const Vertex *p_start, const Point32 &p_s, const Point64 &p_rxs, const Point64 &p_sxrxs, Rational64 &p_min_cot) { + Edge *min_edge = nullptr; + +#ifdef DEBUG_CONVEX_HULL + printf("find max edge for %d\n", p_start->point.index); +#endif + Edge *e = p_start->edges; + if (e) { + do { + if (e->copy > merge_stamp) { + Point32 t = *e->target - *p_start; + Rational64 cot(t.dot(p_sxrxs), t.dot(p_rxs)); +#ifdef DEBUG_CONVEX_HULL + printf(" Angle is %f (%d) for ", Math::atan(cot.to_scalar()), (int32_t)cot.is_nan()); + e->print(); +#endif + if (cot.is_nan()) { + CHULL_ASSERT(p_ccw ? (t.dot(p_s) < 0) : (t.dot(p_s) > 0)); + } else { + int32_t cmp; + if (min_edge == nullptr) { + p_min_cot = cot; + min_edge = e; + } else if ((cmp = cot.compare(p_min_cot)) < 0) { + p_min_cot = cot; + min_edge = e; + } else if ((cmp == 0) && (p_ccw == (get_orientation(min_edge, e, p_s, t) == COUNTER_CLOCKWISE))) { + min_edge = e; + } + } +#ifdef DEBUG_CONVEX_HULL + printf("\n"); +#endif + } + e = e->next; + } while (e != p_start->edges); + } + return min_edge; +} + +void ConvexHullInternal::find_edge_for_coplanar_faces(Vertex *p_c0, Vertex *p_c1, Edge *&p_e0, Edge *&p_e1, Vertex *p_stop0, Vertex *p_stop1) { + Edge *start0 = p_e0; + Edge *start1 = p_e1; + Point32 et0 = start0 ? start0->target->point : p_c0->point; + Point32 et1 = start1 ? start1->target->point : p_c1->point; + Point32 s = p_c1->point - p_c0->point; + Point64 normal = ((start0 ? start0 : start1)->target->point - p_c0->point).cross(s); + int64_t dist = p_c0->point.dot(normal); + CHULL_ASSERT(!start1 || (start1->target->point.dot(normal) == dist)); + Point64 perp = s.cross(normal); + CHULL_ASSERT(!perp.is_zero()); + +#ifdef DEBUG_CONVEX_HULL + printf(" Advancing %d %d (%p %p, %d %d)\n", p_c0->point.index, p_c1->point.index, start0, start1, start0 ? start0->target->point.index : -1, start1 ? start1->target->point.index : -1); +#endif + + int64_t max_dot0 = et0.dot(perp); + if (p_e0) { + while (p_e0->target != p_stop0) { + Edge *e = p_e0->reverse->prev; + if (e->target->point.dot(normal) < dist) { + break; + } + CHULL_ASSERT(e->target->point.dot(normal) == dist); + if (e->copy == merge_stamp) { + break; + } + int64_t dot = e->target->point.dot(perp); + if (dot <= max_dot0) { + break; + } + max_dot0 = dot; + p_e0 = e; + et0 = e->target->point; + } + } + + int64_t max_dot1 = et1.dot(perp); + if (p_e1) { + while (p_e1->target != p_stop1) { + Edge *e = p_e1->reverse->next; + if (e->target->point.dot(normal) < dist) { + break; + } + CHULL_ASSERT(e->target->point.dot(normal) == dist); + if (e->copy == merge_stamp) { + break; + } + int64_t dot = e->target->point.dot(perp); + if (dot <= max_dot1) { + break; + } + max_dot1 = dot; + p_e1 = e; + et1 = e->target->point; + } + } + +#ifdef DEBUG_CONVEX_HULL + printf(" Starting at %d %d\n", et0.index, et1.index); +#endif + + int64_t dx = max_dot1 - max_dot0; + if (dx > 0) { + while (true) { + int64_t dy = (et1 - et0).dot(s); + + if (p_e0 && (p_e0->target != p_stop0)) { + Edge *f0 = p_e0->next->reverse; + if (f0->copy > merge_stamp) { + int64_t dx0 = (f0->target->point - et0).dot(perp); + int64_t dy0 = (f0->target->point - et0).dot(s); + if ((dx0 == 0) ? (dy0 < 0) : ((dx0 < 0) && (Rational64(dy0, dx0).compare(Rational64(dy, dx)) >= 0))) { + et0 = f0->target->point; + dx = (et1 - et0).dot(perp); + p_e0 = (p_e0 == start0) ? nullptr : f0; + continue; + } + } + } + + if (p_e1 && (p_e1->target != p_stop1)) { + Edge *f1 = p_e1->reverse->next; + if (f1->copy > merge_stamp) { + Point32 d1 = f1->target->point - et1; + if (d1.dot(normal) == 0) { + int64_t dx1 = d1.dot(perp); + int64_t dy1 = d1.dot(s); + int64_t dxn = (f1->target->point - et0).dot(perp); + if ((dxn > 0) && ((dx1 == 0) ? (dy1 < 0) : ((dx1 < 0) && (Rational64(dy1, dx1).compare(Rational64(dy, dx)) > 0)))) { + p_e1 = f1; + et1 = p_e1->target->point; + dx = dxn; + continue; + } + } else { + CHULL_ASSERT((p_e1 == start1) && (d1.dot(normal) < 0)); + } + } + } + + break; + } + } else if (dx < 0) { + while (true) { + int64_t dy = (et1 - et0).dot(s); + + if (p_e1 && (p_e1->target != p_stop1)) { + Edge *f1 = p_e1->prev->reverse; + if (f1->copy > merge_stamp) { + int64_t dx1 = (f1->target->point - et1).dot(perp); + int64_t dy1 = (f1->target->point - et1).dot(s); + if ((dx1 == 0) ? (dy1 > 0) : ((dx1 < 0) && (Rational64(dy1, dx1).compare(Rational64(dy, dx)) <= 0))) { + et1 = f1->target->point; + dx = (et1 - et0).dot(perp); + p_e1 = (p_e1 == start1) ? nullptr : f1; + continue; + } + } + } + + if (p_e0 && (p_e0->target != p_stop0)) { + Edge *f0 = p_e0->reverse->prev; + if (f0->copy > merge_stamp) { + Point32 d0 = f0->target->point - et0; + if (d0.dot(normal) == 0) { + int64_t dx0 = d0.dot(perp); + int64_t dy0 = d0.dot(s); + int64_t dxn = (et1 - f0->target->point).dot(perp); + if ((dxn < 0) && ((dx0 == 0) ? (dy0 > 0) : ((dx0 < 0) && (Rational64(dy0, dx0).compare(Rational64(dy, dx)) < 0)))) { + p_e0 = f0; + et0 = p_e0->target->point; + dx = dxn; + continue; + } + } else { + CHULL_ASSERT((p_e0 == start0) && (d0.dot(normal) < 0)); + } + } + } + + break; + } + } +#ifdef DEBUG_CONVEX_HULL + printf(" Advanced edges to %d %d\n", et0.index, et1.index); +#endif +} + +void ConvexHullInternal::merge(IntermediateHull &p_h0, IntermediateHull &p_h1) { + if (!p_h1.max_xy) { + return; + } + if (!p_h0.max_xy) { + p_h0 = p_h1; + return; + } + + merge_stamp--; + + Vertex *c0 = nullptr; + Edge *to_prev0 = nullptr; + Edge *first_new0 = nullptr; + Edge *pending_head0 = nullptr; + Edge *pending_tail0 = nullptr; + Vertex *c1 = nullptr; + Edge *to_prev1 = nullptr; + Edge *first_new1 = nullptr; + Edge *pending_head1 = nullptr; + Edge *pending_tail1 = nullptr; + Point32 prev_point; + + if (merge_projection(p_h0, p_h1, c0, c1)) { + Point32 s = *c1 - *c0; + Point64 normal = Point32(0, 0, -1).cross(s); + Point64 t = s.cross(normal); + CHULL_ASSERT(!t.is_zero()); + + Edge *e = c0->edges; + Edge *start0 = nullptr; + if (e) { + do { + int64_t dot = (*e->target - *c0).dot(normal); + CHULL_ASSERT(dot <= 0); + if ((dot == 0) && ((*e->target - *c0).dot(t) > 0)) { + if (!start0 || (get_orientation(start0, e, s, Point32(0, 0, -1)) == CLOCKWISE)) { + start0 = e; + } + } + e = e->next; + } while (e != c0->edges); + } + + e = c1->edges; + Edge *start1 = nullptr; + if (e) { + do { + int64_t dot = (*e->target - *c1).dot(normal); + CHULL_ASSERT(dot <= 0); + if ((dot == 0) && ((*e->target - *c1).dot(t) > 0)) { + if (!start1 || (get_orientation(start1, e, s, Point32(0, 0, -1)) == COUNTER_CLOCKWISE)) { + start1 = e; + } + } + e = e->next; + } while (e != c1->edges); + } + + if (start0 || start1) { + find_edge_for_coplanar_faces(c0, c1, start0, start1, nullptr, nullptr); + if (start0) { + c0 = start0->target; + } + if (start1) { + c1 = start1->target; + } + } + + prev_point = c1->point; + prev_point.z++; + } else { + prev_point = c1->point; + prev_point.x++; + } + + Vertex *first0 = c0; + Vertex *first1 = c1; + bool first_run = true; + + while (true) { + Point32 s = *c1 - *c0; + Point32 r = prev_point - c0->point; + Point64 rxs = r.cross(s); + Point64 sxrxs = s.cross(rxs); + +#ifdef DEBUG_CONVEX_HULL + printf("\n Checking %d %d\n", c0->point.index, c1->point.index); +#endif + Rational64 min_cot0(0, 0); + Edge *min0 = find_max_angle(false, c0, s, rxs, sxrxs, min_cot0); + Rational64 min_cot1(0, 0); + Edge *min1 = find_max_angle(true, c1, s, rxs, sxrxs, min_cot1); + if (!min0 && !min1) { + Edge *e = new_edge_pair(c0, c1); + e->link(e); + c0->edges = e; + + e = e->reverse; + e->link(e); + c1->edges = e; + return; + } else { + int32_t cmp = !min0 ? 1 : !min1 ? -1 : + min_cot0.compare(min_cot1); +#ifdef DEBUG_CONVEX_HULL + printf(" -> Result %d\n", cmp); +#endif + if (first_run || ((cmp >= 0) ? !min_cot1.is_negative_infinity() : !min_cot0.is_negative_infinity())) { + Edge *e = new_edge_pair(c0, c1); + if (pending_tail0) { + pending_tail0->prev = e; + } else { + pending_head0 = e; + } + e->next = pending_tail0; + pending_tail0 = e; + + e = e->reverse; + if (pending_tail1) { + pending_tail1->next = e; + } else { + pending_head1 = e; + } + e->prev = pending_tail1; + pending_tail1 = e; + } + + Edge *e0 = min0; + Edge *e1 = min1; + +#ifdef DEBUG_CONVEX_HULL + printf(" Found min edges to %d %d\n", e0 ? e0->target->point.index : -1, e1 ? e1->target->point.index : -1); +#endif + + if (cmp == 0) { + find_edge_for_coplanar_faces(c0, c1, e0, e1, nullptr, nullptr); + } + + if ((cmp >= 0) && e1) { + if (to_prev1) { + for (Edge *e = to_prev1->next, *n = nullptr; e != min1; e = n) { + n = e->next; + remove_edge_pair(e); + } + } + + if (pending_tail1) { + if (to_prev1) { + to_prev1->link(pending_head1); + } else { + min1->prev->link(pending_head1); + first_new1 = pending_head1; + } + pending_tail1->link(min1); + pending_head1 = nullptr; + pending_tail1 = nullptr; + } else if (!to_prev1) { + first_new1 = min1; + } + + prev_point = c1->point; + c1 = e1->target; + to_prev1 = e1->reverse; + } + + if ((cmp <= 0) && e0) { + if (to_prev0) { + for (Edge *e = to_prev0->prev, *n = nullptr; e != min0; e = n) { + n = e->prev; + remove_edge_pair(e); + } + } + + if (pending_tail0) { + if (to_prev0) { + pending_head0->link(to_prev0); + } else { + pending_head0->link(min0->next); + first_new0 = pending_head0; + } + min0->link(pending_tail0); + pending_head0 = nullptr; + pending_tail0 = nullptr; + } else if (!to_prev0) { + first_new0 = min0; + } + + prev_point = c0->point; + c0 = e0->target; + to_prev0 = e0->reverse; + } + } + + if ((c0 == first0) && (c1 == first1)) { + if (to_prev0 == nullptr) { + pending_head0->link(pending_tail0); + c0->edges = pending_tail0; + } else { + for (Edge *e = to_prev0->prev, *n = nullptr; e != first_new0; e = n) { + n = e->prev; + remove_edge_pair(e); + } + if (pending_tail0) { + pending_head0->link(to_prev0); + first_new0->link(pending_tail0); + } + } + + if (to_prev1 == nullptr) { + pending_tail1->link(pending_head1); + c1->edges = pending_tail1; + } else { + for (Edge *e = to_prev1->next, *n = nullptr; e != first_new1; e = n) { + n = e->next; + remove_edge_pair(e); + } + if (pending_tail1) { + to_prev1->link(pending_head1); + pending_tail1->link(first_new1); + } + } + + return; + } + + first_run = false; + } +} + +struct PointComparator { + _FORCE_INLINE_ bool operator()(const ConvexHullInternal::Point32 &p, const ConvexHullInternal::Point32 &q) const { + return (p.y < q.y) || ((p.y == q.y) && ((p.x < q.x) || ((p.x == q.x) && (p.z < q.z)))); + } +}; + +void ConvexHullInternal::compute(const Vector3 *p_coords, int32_t p_count) { + AABB aabb; + for (int32_t i = 0; i < p_count; i++) { + Vector3 p = p_coords[i]; + if (i == 0) { + aabb.position = p; + } else { + aabb.expand_to(p); + } + } + + Vector3 s = aabb.size; + max_axis = s.max_axis(); + min_axis = s.min_axis(); + if (min_axis == max_axis) { + min_axis = (max_axis + 1) % 3; + } + med_axis = 3 - max_axis - min_axis; + + s /= real_t(10216); + if (((med_axis + 1) % 3) != max_axis) { + s *= -1; + } + scaling = s; + + if (s[0] != 0) { + s[0] = real_t(1) / s[0]; + } + if (s[1] != 0) { + s[1] = real_t(1) / s[1]; + } + if (s[2] != 0) { + s[2] = real_t(1) / s[2]; + } + + center = aabb.position; + + LocalVector<Point32> points; + points.resize(p_count); + for (int32_t i = 0; i < p_count; i++) { + Vector3 p = p_coords[i]; + p = (p - center) * s; + points[i].x = (int32_t)p[med_axis]; + points[i].y = (int32_t)p[max_axis]; + points[i].z = (int32_t)p[min_axis]; + points[i].index = i; + } + + points.sort_custom<PointComparator>(); + + vertex_pool.reset(true); + original_vertices.resize(p_count); + for (int32_t i = 0; i < p_count; i++) { + Vertex *v = vertex_pool.alloc(); + v->edges = nullptr; + v->point = points[i]; + v->copy = -1; + original_vertices[i] = v; + } + + points.clear(); + + edge_pool.reset(true); + + used_edge_pairs = 0; + max_used_edge_pairs = 0; + + merge_stamp = -3; + + IntermediateHull hull; + compute_internal(0, p_count, hull); + vertex_list = hull.min_xy; +#ifdef DEBUG_CONVEX_HULL + printf("max. edges %d (3v = %d)", max_used_edge_pairs, 3 * p_count); +#endif +} + +Vector3 ConvexHullInternal::to_gd_vector(const Point32 &p_v) { + Vector3 p; + p[med_axis] = real_t(p_v.x); + p[max_axis] = real_t(p_v.y); + p[min_axis] = real_t(p_v.z); + return p * scaling; +} + +Vector3 ConvexHullInternal::get_gd_normal(Face *p_face) { + return to_gd_vector(p_face->dir0).cross(to_gd_vector(p_face->dir1)).normalized(); +} + +Vector3 ConvexHullInternal::get_coordinates(const Vertex *p_v) { + Vector3 p; + p[med_axis] = p_v->xvalue(); + p[max_axis] = p_v->yvalue(); + p[min_axis] = p_v->zvalue(); + return p * scaling + center; +} + +real_t ConvexHullInternal::shrink(real_t p_amount, real_t p_clamp_amount) { + if (!vertex_list) { + return 0; + } + int32_t stamp = --merge_stamp; + LocalVector<Vertex *> stack; + vertex_list->copy = stamp; + stack.push_back(vertex_list); + LocalVector<Face *> faces; + + Point32 ref = vertex_list->point; + Int128 hull_center_x(0, 0); + Int128 hull_center_y(0, 0); + Int128 hull_center_z(0, 0); + Int128 volume(0, 0); + + while (stack.size() > 0) { + Vertex *v = stack[stack.size() - 1]; + stack.remove(stack.size() - 1); + Edge *e = v->edges; + if (e) { + do { + if (e->target->copy != stamp) { + e->target->copy = stamp; + stack.push_back(e->target); + } + if (e->copy != stamp) { + Face *face = face_pool.alloc(); + face->init(e->target, e->reverse->prev->target, v); + faces.push_back(face); + Edge *f = e; + + Vertex *a = nullptr; + Vertex *b = nullptr; + do { + if (a && b) { + int64_t vol = (v->point - ref).dot((a->point - ref).cross(b->point - ref)); + CHULL_ASSERT(vol >= 0); + Point32 c = v->point + a->point + b->point + ref; + hull_center_x += vol * c.x; + hull_center_y += vol * c.y; + hull_center_z += vol * c.z; + volume += vol; + } + + CHULL_ASSERT(f->copy != stamp); + f->copy = stamp; + f->face = face; + + a = b; + b = f->target; + + f = f->reverse->prev; + } while (f != e); + } + e = e->next; + } while (e != v->edges); + } + } + + if (volume.get_sign() <= 0) { + return 0; + } + + Vector3 hull_center; + hull_center[med_axis] = hull_center_x.to_scalar(); + hull_center[max_axis] = hull_center_y.to_scalar(); + hull_center[min_axis] = hull_center_z.to_scalar(); + hull_center /= 4 * volume.to_scalar(); + hull_center *= scaling; + + int32_t face_count = faces.size(); + + if (p_clamp_amount > 0) { + real_t min_dist = FLT_MAX; + for (int32_t i = 0; i < face_count; i++) { + Vector3 normal = get_gd_normal(faces[i]); + real_t dist = normal.dot(to_gd_vector(faces[i]->origin) - hull_center); + if (dist < min_dist) { + min_dist = dist; + } + } + + if (min_dist <= 0) { + return 0; + } + + p_amount = MIN(p_amount, min_dist * p_clamp_amount); + } + + uint32_t seed = 243703; + for (int32_t i = 0; i < face_count; i++, seed = 1664525 * seed + 1013904223) { + SWAP(faces[i], faces[seed % face_count]); + } + + for (int32_t i = 0; i < face_count; i++) { + if (!shift_face(faces[i], p_amount, stack)) { + return -p_amount; + } + } + + return p_amount; +} + +bool ConvexHullInternal::shift_face(Face *p_face, real_t p_amount, LocalVector<Vertex *> p_stack) { + Vector3 orig_shift = get_gd_normal(p_face) * -p_amount; + if (scaling[0] != 0) { + orig_shift[0] /= scaling[0]; + } + if (scaling[1] != 0) { + orig_shift[1] /= scaling[1]; + } + if (scaling[2] != 0) { + orig_shift[2] /= scaling[2]; + } + Point32 shift((int32_t)orig_shift[med_axis], (int32_t)orig_shift[max_axis], (int32_t)orig_shift[min_axis]); + if (shift.is_zero()) { + return true; + } + Point64 normal = p_face->get_normal(); +#ifdef DEBUG_CONVEX_HULL + printf("\nShrinking p_face (%d %d %d) (%d %d %d) (%d %d %d) by (%d %d %d)\n", + p_face->origin.x, p_face->origin.y, p_face->origin.z, p_face->dir0.x, p_face->dir0.y, p_face->dir0.z, p_face->dir1.x, p_face->dir1.y, p_face->dir1.z, shift.x, shift.y, shift.z); +#endif + int64_t orig_dot = p_face->origin.dot(normal); + Point32 shifted_origin = p_face->origin + shift; + int64_t shifted_dot = shifted_origin.dot(normal); + CHULL_ASSERT(shifted_dot <= orig_dot); + if (shifted_dot >= orig_dot) { + return false; + } + + Edge *intersection = nullptr; + + Edge *start_edge = p_face->nearby_vertex->edges; +#ifdef DEBUG_CONVEX_HULL + printf("Start edge is "); + start_edge->print(); + printf(", normal is (%lld %lld %lld), shifted dot is %lld\n", normal.x, normal.y, normal.z, shifted_dot); +#endif + Rational128 opt_dot = p_face->nearby_vertex->dot(normal); + int32_t cmp = opt_dot.compare(shifted_dot); +#ifdef SHOW_ITERATIONS + int32_t n = 0; +#endif + if (cmp >= 0) { + Edge *e = start_edge; + do { +#ifdef SHOW_ITERATIONS + n++; +#endif + Rational128 dot = e->target->dot(normal); + CHULL_ASSERT(dot.compare(orig_dot) <= 0); +#ifdef DEBUG_CONVEX_HULL + printf("Moving downwards, edge is "); + e->print(); + printf(", dot is %f (%f %lld)\n", (float)dot.to_scalar(), (float)opt_dot.to_scalar(), shifted_dot); +#endif + if (dot.compare(opt_dot) < 0) { + int32_t c = dot.compare(shifted_dot); + opt_dot = dot; + e = e->reverse; + start_edge = e; + if (c < 0) { + intersection = e; + break; + } + cmp = c; + } + e = e->prev; + } while (e != start_edge); + + if (!intersection) { + return false; + } + } else { + Edge *e = start_edge; + do { +#ifdef SHOW_ITERATIONS + n++; +#endif + Rational128 dot = e->target->dot(normal); + CHULL_ASSERT(dot.compare(orig_dot) <= 0); +#ifdef DEBUG_CONVEX_HULL + printf("Moving upwards, edge is "); + e->print(); + printf(", dot is %f (%f %lld)\n", (float)dot.to_scalar(), (float)opt_dot.to_scalar(), shifted_dot); +#endif + if (dot.compare(opt_dot) > 0) { + cmp = dot.compare(shifted_dot); + if (cmp >= 0) { + intersection = e; + break; + } + opt_dot = dot; + e = e->reverse; + start_edge = e; + } + e = e->prev; + } while (e != start_edge); + + if (!intersection) { + return true; + } + } + +#ifdef SHOW_ITERATIONS + printf("Needed %d iterations to find initial intersection\n", n); +#endif + + if (cmp == 0) { + Edge *e = intersection->reverse->next; +#ifdef SHOW_ITERATIONS + n = 0; +#endif + while (e->target->dot(normal).compare(shifted_dot) <= 0) { +#ifdef SHOW_ITERATIONS + n++; +#endif + e = e->next; + if (e == intersection->reverse) { + return true; + } +#ifdef DEBUG_CONVEX_HULL + printf("Checking for outwards edge, current edge is "); + e->print(); + printf("\n"); +#endif + } +#ifdef SHOW_ITERATIONS + printf("Needed %d iterations to check for complete containment\n", n); +#endif + } + + Edge *first_intersection = nullptr; + Edge *face_edge = nullptr; + Edge *first_face_edge = nullptr; + +#ifdef SHOW_ITERATIONS + int32_t m = 0; +#endif + while (true) { +#ifdef SHOW_ITERATIONS + m++; +#endif +#ifdef DEBUG_CONVEX_HULL + printf("Intersecting edge is "); + intersection->print(); + printf("\n"); +#endif + if (cmp == 0) { + Edge *e = intersection->reverse->next; + start_edge = e; +#ifdef SHOW_ITERATIONS + n = 0; +#endif + while (true) { +#ifdef SHOW_ITERATIONS + n++; +#endif + if (e->target->dot(normal).compare(shifted_dot) >= 0) { + break; + } + intersection = e->reverse; + e = e->next; + if (e == start_edge) { + return true; + } + } +#ifdef SHOW_ITERATIONS + printf("Needed %d iterations to advance intersection\n", n); +#endif + } + +#ifdef DEBUG_CONVEX_HULL + printf("Advanced intersecting edge to "); + intersection->print(); + printf(", cmp = %d\n", cmp); +#endif + + if (!first_intersection) { + first_intersection = intersection; + } else if (intersection == first_intersection) { + break; + } + + int32_t prev_cmp = cmp; + Edge *prev_intersection = intersection; + Edge *prev_face_edge = face_edge; + + Edge *e = intersection->reverse; +#ifdef SHOW_ITERATIONS + n = 0; +#endif + while (true) { +#ifdef SHOW_ITERATIONS + n++; +#endif + e = e->reverse->prev; + CHULL_ASSERT(e != intersection->reverse); + cmp = e->target->dot(normal).compare(shifted_dot); +#ifdef DEBUG_CONVEX_HULL + printf("Testing edge "); + e->print(); + printf(" -> cmp = %d\n", cmp); +#endif + if (cmp >= 0) { + intersection = e; + break; + } + } +#ifdef SHOW_ITERATIONS + printf("Needed %d iterations to find other intersection of p_face\n", n); +#endif + + if (cmp > 0) { + Vertex *removed = intersection->target; + e = intersection->reverse; + if (e->prev == e) { + removed->edges = nullptr; + } else { + removed->edges = e->prev; + e->prev->link(e->next); + e->link(e); + } +#ifdef DEBUG_CONVEX_HULL + printf("1: Removed part contains (%d %d %d)\n", removed->point.x, removed->point.y, removed->point.z); +#endif + + Point64 n0 = intersection->face->get_normal(); + Point64 n1 = intersection->reverse->face->get_normal(); + int64_t m00 = p_face->dir0.dot(n0); + int64_t m01 = p_face->dir1.dot(n0); + int64_t m10 = p_face->dir0.dot(n1); + int64_t m11 = p_face->dir1.dot(n1); + int64_t r0 = (intersection->face->origin - shifted_origin).dot(n0); + int64_t r1 = (intersection->reverse->face->origin - shifted_origin).dot(n1); + Int128 det = Int128::mul(m00, m11) - Int128::mul(m01, m10); + CHULL_ASSERT(det.get_sign() != 0); + Vertex *v = vertex_pool.alloc(); + v->point.index = -1; + v->copy = -1; + v->point128 = PointR128(Int128::mul(p_face->dir0.x * r0, m11) - Int128::mul(p_face->dir0.x * r1, m01) + Int128::mul(p_face->dir1.x * r1, m00) - Int128::mul(p_face->dir1.x * r0, m10) + det * shifted_origin.x, + Int128::mul(p_face->dir0.y * r0, m11) - Int128::mul(p_face->dir0.y * r1, m01) + Int128::mul(p_face->dir1.y * r1, m00) - Int128::mul(p_face->dir1.y * r0, m10) + det * shifted_origin.y, + Int128::mul(p_face->dir0.z * r0, m11) - Int128::mul(p_face->dir0.z * r1, m01) + Int128::mul(p_face->dir1.z * r1, m00) - Int128::mul(p_face->dir1.z * r0, m10) + det * shifted_origin.z, + det); + v->point.x = (int32_t)v->point128.xvalue(); + v->point.y = (int32_t)v->point128.yvalue(); + v->point.z = (int32_t)v->point128.zvalue(); + intersection->target = v; + v->edges = e; + + p_stack.push_back(v); + p_stack.push_back(removed); + p_stack.push_back(nullptr); + } + + if (cmp || prev_cmp || (prev_intersection->reverse->next->target != intersection->target)) { + face_edge = new_edge_pair(prev_intersection->target, intersection->target); + if (prev_cmp == 0) { + face_edge->link(prev_intersection->reverse->next); + } + if ((prev_cmp == 0) || prev_face_edge) { + prev_intersection->reverse->link(face_edge); + } + if (cmp == 0) { + intersection->reverse->prev->link(face_edge->reverse); + } + face_edge->reverse->link(intersection->reverse); + } else { + face_edge = prev_intersection->reverse->next; + } + + if (prev_face_edge) { + if (prev_cmp > 0) { + face_edge->link(prev_face_edge->reverse); + } else if (face_edge != prev_face_edge->reverse) { + p_stack.push_back(prev_face_edge->target); + while (face_edge->next != prev_face_edge->reverse) { + Vertex *removed = face_edge->next->target; + remove_edge_pair(face_edge->next); + p_stack.push_back(removed); +#ifdef DEBUG_CONVEX_HULL + printf("2: Removed part contains (%d %d %d)\n", removed->point.x, removed->point.y, removed->point.z); +#endif + } + p_stack.push_back(nullptr); + } + } + face_edge->face = p_face; + face_edge->reverse->face = intersection->face; + + if (!first_face_edge) { + first_face_edge = face_edge; + } + } +#ifdef SHOW_ITERATIONS + printf("Needed %d iterations to process all intersections\n", m); +#endif + + if (cmp > 0) { + first_face_edge->reverse->target = face_edge->target; + first_intersection->reverse->link(first_face_edge); + first_face_edge->link(face_edge->reverse); + } else if (first_face_edge != face_edge->reverse) { + p_stack.push_back(face_edge->target); + while (first_face_edge->next != face_edge->reverse) { + Vertex *removed = first_face_edge->next->target; + remove_edge_pair(first_face_edge->next); + p_stack.push_back(removed); +#ifdef DEBUG_CONVEX_HULL + printf("3: Removed part contains (%d %d %d)\n", removed->point.x, removed->point.y, removed->point.z); +#endif + } + p_stack.push_back(nullptr); + } + + CHULL_ASSERT(p_stack.size() > 0); + vertex_list = p_stack[0]; + +#ifdef DEBUG_CONVEX_HULL + printf("Removing part\n"); +#endif +#ifdef SHOW_ITERATIONS + n = 0; +#endif + uint32_t pos = 0; + while (pos < p_stack.size()) { + uint32_t end = p_stack.size(); + while (pos < end) { + Vertex *kept = p_stack[pos++]; +#ifdef DEBUG_CONVEX_HULL + kept->print(); +#endif + bool deeper = false; + Vertex *removed; + while ((removed = p_stack[pos++]) != nullptr) { +#ifdef SHOW_ITERATIONS + n++; +#endif + kept->receive_nearby_faces(removed); + while (removed->edges) { + if (!deeper) { + deeper = true; + p_stack.push_back(kept); + } + p_stack.push_back(removed->edges->target); + remove_edge_pair(removed->edges); + } + } + if (deeper) { + p_stack.push_back(nullptr); + } + } + } +#ifdef SHOW_ITERATIONS + printf("Needed %d iterations to remove part\n", n); +#endif + + p_stack.resize(0); + p_face->origin = shifted_origin; + + return true; +} + +static int32_t get_vertex_copy(ConvexHullInternal::Vertex *p_vertex, LocalVector<ConvexHullInternal::Vertex *> &p_vertices) { + int32_t index = p_vertex->copy; + if (index < 0) { + index = p_vertices.size(); + p_vertex->copy = index; + p_vertices.push_back(p_vertex); +#ifdef DEBUG_CONVEX_HULL + printf("Vertex %d gets index *%d\n", p_vertex->point.index, index); +#endif + } + return index; +} + +real_t ConvexHullComputer::compute(const Vector3 *p_coords, int32_t p_count, real_t p_shrink, real_t p_shrink_clamp) { + if (p_count <= 0) { + vertices.clear(); + edges.clear(); + faces.clear(); + return 0; + } + + ConvexHullInternal hull; + hull.compute(p_coords, p_count); + + real_t shift = 0; + if ((p_shrink > 0) && ((shift = hull.shrink(p_shrink, p_shrink_clamp)) < 0)) { + vertices.clear(); + edges.clear(); + faces.clear(); + return shift; + } + + vertices.resize(0); + edges.resize(0); + faces.resize(0); + + LocalVector<ConvexHullInternal::Vertex *> old_vertices; + get_vertex_copy(hull.vertex_list, old_vertices); + int32_t copied = 0; + while (copied < (int32_t)old_vertices.size()) { + ConvexHullInternal::Vertex *v = old_vertices[copied]; + vertices.push_back(hull.get_coordinates(v)); + ConvexHullInternal::Edge *first_edge = v->edges; + if (first_edge) { + int32_t first_copy = -1; + int32_t prev_copy = -1; + ConvexHullInternal::Edge *e = first_edge; + do { + if (e->copy < 0) { + int32_t s = edges.size(); + edges.push_back(Edge()); + edges.push_back(Edge()); + Edge *c = &edges[s]; + Edge *r = &edges[s + 1]; + e->copy = s; + e->reverse->copy = s + 1; + c->reverse = 1; + r->reverse = -1; + c->target_vertex = get_vertex_copy(e->target, old_vertices); + r->target_vertex = copied; +#ifdef DEBUG_CONVEX_HULL + printf(" CREATE: Vertex *%d has edge to *%d\n", copied, c->get_target_vertex()); +#endif + } + if (prev_copy >= 0) { + edges[e->copy].next = prev_copy - e->copy; + } else { + first_copy = e->copy; + } + prev_copy = e->copy; + e = e->next; + } while (e != first_edge); + edges[first_copy].next = prev_copy - first_copy; + } + copied++; + } + + for (int32_t i = 0; i < copied; i++) { + ConvexHullInternal::Vertex *v = old_vertices[i]; + ConvexHullInternal::Edge *first_edge = v->edges; + if (first_edge) { + ConvexHullInternal::Edge *e = first_edge; + do { + if (e->copy >= 0) { +#ifdef DEBUG_CONVEX_HULL + printf("Vertex *%d has edge to *%d\n", i, edges[e->copy].get_target_vertex()); +#endif + faces.push_back(e->copy); + ConvexHullInternal::Edge *f = e; + do { +#ifdef DEBUG_CONVEX_HULL + printf(" Face *%d\n", edges[f->copy].get_target_vertex()); +#endif + f->copy = -1; + f = f->reverse->prev; + } while (f != e); + } + e = e->next; + } while (e != first_edge); + } + } + + return shift; +} + +Error ConvexHullComputer::convex_hull(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_mesh) { + r_mesh = Geometry3D::MeshData(); // clear + + if (p_points.size() == 0) { + return FAILED; // matches QuickHull + } + + ConvexHullComputer ch; + ch.compute(p_points.ptr(), p_points.size(), -1.0, -1.0); + + r_mesh.vertices = ch.vertices; + + r_mesh.edges.resize(ch.edges.size()); + for (uint32_t i = 0; i < ch.edges.size(); i++) { + r_mesh.edges.write[i].a = (&ch.edges[i])->get_source_vertex(); + r_mesh.edges.write[i].b = (&ch.edges[i])->get_target_vertex(); + } + + r_mesh.faces.resize(ch.faces.size()); + for (uint32_t i = 0; i < ch.faces.size(); i++) { + const Edge *e_start = &ch.edges[ch.faces[i]]; + const Edge *e = e_start; + Geometry3D::MeshData::Face &face = r_mesh.faces.write[i]; + + do { + face.indices.push_back(e->get_target_vertex()); + + e = e->get_next_edge_of_face(); + } while (e != e_start); + + // compute normal + if (face.indices.size() >= 3) { + face.plane = Plane(r_mesh.vertices[face.indices[0]], r_mesh.vertices[face.indices[2]], r_mesh.vertices[face.indices[1]]); + } else { + WARN_PRINT("Too few vertices per face."); + } + } + + return OK; +} diff --git a/core/math/convex_hull.h b/core/math/convex_hull.h new file mode 100644 index 0000000000..ba7be9c5e8 --- /dev/null +++ b/core/math/convex_hull.h @@ -0,0 +1,112 @@ +/*************************************************************************/ +/* convex_hull.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2021 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +/* +Copyright (c) 2011 Ole Kniemeyer, MAXON, www.maxon.net +This software is provided 'as-is', without any express or implied warranty. +In no event will the authors be held liable for any damages arising from the use of this software. +Permission is granted to anyone to use this software for any purpose, +including commercial applications, and to alter it and redistribute it freely, +subject to the following restrictions: +1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. +2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. +3. This notice may not be removed or altered from any source distribution. +*/ + +#ifndef CONVEX_HULL_H +#define CONVEX_HULL_H + +#include "core/math/geometry_3d.h" +#include "core/math/vector3.h" +#include "core/templates/local_vector.h" +#include "core/templates/vector.h" + +/// Convex hull implementation based on Preparata and Hong +/// See http://code.google.com/p/bullet/issues/detail?id=275 +/// Ole Kniemeyer, MAXON Computer GmbH +class ConvexHullComputer { +public: + class Edge { + private: + int32_t next = 0; + int32_t reverse = 0; + int32_t target_vertex = 0; + + friend class ConvexHullComputer; + + public: + int32_t get_source_vertex() const { + return (this + reverse)->target_vertex; + } + + int32_t get_target_vertex() const { + return target_vertex; + } + + const Edge *get_next_edge_of_vertex() const // clockwise list of all edges of a vertex + { + return this + next; + } + + const Edge *get_next_edge_of_face() const // counter-clockwise list of all edges of a face + { + return (this + reverse)->get_next_edge_of_vertex(); + } + + const Edge *get_reverse_edge() const { + return this + reverse; + } + }; + + // Vertices of the output hull + Vector<Vector3> vertices; + + // Edges of the output hull + LocalVector<Edge> edges; + + // Faces of the convex hull. Each entry is an index into the "edges" array pointing to an edge of the face. Faces are planar n-gons + LocalVector<int32_t> faces; + + /* + Compute convex hull of "count" vertices stored in "coords". + If "shrink" is positive, the convex hull is shrunken by that amount (each face is moved by "shrink" length units + towards the center along its normal). + If "shrinkClamp" is positive, "shrink" is clamped to not exceed "shrinkClamp * innerRadius", where "innerRadius" + is the minimum distance of a face to the center of the convex hull. + The returned value is the amount by which the hull has been shrunken. If it is negative, the amount was so large + that the resulting convex hull is empty. + The output convex hull can be found in the member variables "vertices", "edges", "faces". + */ + real_t compute(const Vector3 *p_coords, int32_t p_count, real_t p_shrink, real_t p_shrink_clamp); + + static Error convex_hull(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_mesh); +}; + +#endif // CONVEX_HULL_H diff --git a/core/string/ustring.cpp b/core/string/ustring.cpp index 3c1afc7f2c..49cf171f2b 100644 --- a/core/string/ustring.cpp +++ b/core/string/ustring.cpp @@ -939,7 +939,7 @@ const char32_t *String::get_data() const { } void String::erase(int p_pos, int p_chars) { - *this = left(p_pos) + substr(p_pos + p_chars, length() - ((p_pos + p_chars))); + *this = left(MAX(p_pos, 0)) + substr(p_pos + p_chars, length() - ((p_pos + p_chars))); } String String::capitalize() const { diff --git a/core/templates/paged_allocator.h b/core/templates/paged_allocator.h index 7002034710..481289309f 100644 --- a/core/templates/paged_allocator.h +++ b/core/templates/paged_allocator.h @@ -35,6 +35,8 @@ #include "core/os/spin_lock.h" #include "core/typedefs.h" +#include <type_traits> + template <class T, bool thread_safe = false> class PagedAllocator { T **page_pool = nullptr; @@ -89,8 +91,10 @@ public: allocs_available++; } - void reset() { - ERR_FAIL_COND(allocs_available < pages_allocated * page_size); + void reset(bool p_allow_unfreed = false) { + if (!p_allow_unfreed || !std::is_trivially_destructible<T>::value) { + ERR_FAIL_COND(allocs_available < pages_allocated * page_size); + } if (pages_allocated) { for (uint32_t i = 0; i < pages_allocated; i++) { memfree(page_pool[i]); diff --git a/doc/classes/CodeEdit.xml b/doc/classes/CodeEdit.xml index 81795abcdd..42a6df866f 100644 --- a/doc/classes/CodeEdit.xml +++ b/doc/classes/CodeEdit.xml @@ -193,8 +193,6 @@ </theme_item> <theme_item name="line_spacing" type="int" default="4"> </theme_item> - <theme_item name="mark_color" type="Color" default="Color( 1, 0.4, 0.4, 0.4 )"> - </theme_item> <theme_item name="normal" type="StyleBox"> </theme_item> <theme_item name="outline_size" type="int" default="0"> diff --git a/doc/classes/ProjectSettings.xml b/doc/classes/ProjectSettings.xml index 24d4a8a46e..690c90a16e 100644 --- a/doc/classes/ProjectSettings.xml +++ b/doc/classes/ProjectSettings.xml @@ -732,6 +732,10 @@ </member> <member name="input/ui_text_select_all" type="Dictionary" setter="" getter=""> </member> + <member name="input/ui_text_select_word_under_caret" type="Dictionary" setter="" getter=""> + If no selection is currently active, selects the word currently under the caret in text fields. If a selection is currently active, deselects the current selection. + [b]Note:[/b] Currently, this is only implemented in [TextEdit], not [LineEdit]. + </member> <member name="input/ui_text_toggle_insert_mode" type="Dictionary" setter="" getter=""> </member> <member name="input/ui_undo" type="Dictionary" setter="" getter=""> diff --git a/doc/classes/Sprite2D.xml b/doc/classes/Sprite2D.xml index 617ad3a371..c320adb1be 100644 --- a/doc/classes/Sprite2D.xml +++ b/doc/classes/Sprite2D.xml @@ -64,7 +64,7 @@ <member name="frame" type="int" setter="set_frame" getter="get_frame" default="0"> Current frame to display from sprite sheet. [member hframes] or [member vframes] must be greater than 1. </member> - <member name="frame_coords" type="Vector2" setter="set_frame_coords" getter="get_frame_coords" default="Vector2( 0, 0 )"> + <member name="frame_coords" type="Vector2i" setter="set_frame_coords" getter="get_frame_coords" default="Vector2i( 0, 0 )"> Coordinates of the frame to display from sprite sheet. This is as an alias for the [member frame] property. [member hframes] or [member vframes] must be greater than 1. </member> <member name="hframes" type="int" setter="set_hframes" getter="get_hframes" default="1"> diff --git a/doc/classes/Sprite3D.xml b/doc/classes/Sprite3D.xml index 658fd1a4f2..a7d61a6bab 100644 --- a/doc/classes/Sprite3D.xml +++ b/doc/classes/Sprite3D.xml @@ -14,7 +14,7 @@ <member name="frame" type="int" setter="set_frame" getter="get_frame" default="0"> Current frame to display from sprite sheet. [member hframes] or [member vframes] must be greater than 1. </member> - <member name="frame_coords" type="Vector2" setter="set_frame_coords" getter="get_frame_coords" default="Vector2( 0, 0 )"> + <member name="frame_coords" type="Vector2i" setter="set_frame_coords" getter="get_frame_coords" default="Vector2i( 0, 0 )"> Coordinates of the frame to display from sprite sheet. This is as an alias for the [member frame] property. [member hframes] or [member vframes] must be greater than 1. </member> <member name="hframes" type="int" setter="set_hframes" getter="get_hframes" default="1"> diff --git a/doc/classes/TextEdit.xml b/doc/classes/TextEdit.xml index b97728ccd4..29067b5534 100644 --- a/doc/classes/TextEdit.xml +++ b/doc/classes/TextEdit.xml @@ -167,6 +167,15 @@ Returns the text of a specific line. </description> </method> + <method name="get_line_background_color"> + <return type="Color"> + </return> + <argument index="0" name="line" type="int"> + </argument> + <description> + Returns the current background color of the line. [code]Color(0, 0, 0, 0)[/code] is returned if no color is set. + </description> + </method> <method name="get_line_count" qualifiers="const"> <return type="int"> </return> @@ -548,6 +557,17 @@ If [code]true[/code], hides the line of the specified index. </description> </method> + <method name="set_line_background_color"> + <return type="void"> + </return> + <argument index="0" name="line" type="int"> + </argument> + <argument index="1" name="color" type="Color"> + </argument> + <description> + Sets the current background color of the line. Set to [code]Color(0, 0, 0, 0)[/code] for no color. + </description> + </method> <method name="set_line_gutter_clickable"> <return type="void"> </return> @@ -987,9 +1007,6 @@ <theme_item name="line_spacing" type="int" default="4"> Sets the spacing between the lines. </theme_item> - <theme_item name="mark_color" type="Color" default="Color( 1, 0.4, 0.4, 0.4 )"> - Sets the [Color] of marked text. - </theme_item> <theme_item name="normal" type="StyleBox"> Sets the [StyleBox] of this [TextEdit]. </theme_item> diff --git a/editor/animation_track_editor.cpp b/editor/animation_track_editor.cpp index 9d5811dcbd..3620fda4f8 100644 --- a/editor/animation_track_editor.cpp +++ b/editor/animation_track_editor.cpp @@ -1659,7 +1659,7 @@ void AnimationTimelineEdit::_gui_input(const Ref<InputEvent> &p_event) { int x = mb->get_position().x - get_name_limit(); float ofs = x / get_zoom_scale() + get_value(); - emit_signal("timeline_changed", ofs, false); + emit_signal("timeline_changed", ofs, false, Input::get_singleton()->is_key_pressed(KEY_ALT)); dragging_timeline = true; } if (!dragging_timeline && mb->get_button_index() == MOUSE_BUTTON_MIDDLE) { @@ -1698,7 +1698,7 @@ void AnimationTimelineEdit::_gui_input(const Ref<InputEvent> &p_event) { if (dragging_timeline) { int x = mm->get_position().x - get_name_limit(); float ofs = x / get_zoom_scale() + get_value(); - emit_signal("timeline_changed", ofs, false); + emit_signal("timeline_changed", ofs, false, Input::get_singleton()->is_key_pressed(KEY_ALT)); } if (panning_timeline) { int x = mm->get_position().x - get_name_limit(); @@ -3254,8 +3254,8 @@ void AnimationTrackEditor::_name_limit_changed() { } } -void AnimationTrackEditor::_timeline_changed(float p_new_pos, bool p_drag) { - emit_signal("timeline_changed", p_new_pos, p_drag); +void AnimationTrackEditor::_timeline_changed(float p_new_pos, bool p_drag, bool p_timeline_only) { + emit_signal("timeline_changed", p_new_pos, p_drag, p_timeline_only); } void AnimationTrackEditor::_track_remove_request(int p_track) { diff --git a/editor/animation_track_editor.h b/editor/animation_track_editor.h index c25865effb..8befc830fa 100644 --- a/editor/animation_track_editor.h +++ b/editor/animation_track_editor.h @@ -328,7 +328,7 @@ class AnimationTrackEditor : public VBoxContainer { void _update_tracks(); void _name_limit_changed(); - void _timeline_changed(float p_new_pos, bool p_drag); + void _timeline_changed(float p_new_pos, bool p_drag, bool p_timeline_only = false); void _track_remove_request(int p_track); void _track_grab_focus(int p_track); diff --git a/editor/code_editor.cpp b/editor/code_editor.cpp index 12e78c3120..87ac16fdcf 100644 --- a/editor/code_editor.cpp +++ b/editor/code_editor.cpp @@ -1474,6 +1474,34 @@ void CodeTextEditor::goto_error() { } } +void CodeTextEditor::_update_text_editor_theme() { + text_editor->add_theme_color_override("background_color", EDITOR_GET("text_editor/highlighting/background_color")); + text_editor->add_theme_color_override("completion_background_color", EDITOR_GET("text_editor/highlighting/completion_background_color")); + text_editor->add_theme_color_override("completion_selected_color", EDITOR_GET("text_editor/highlighting/completion_selected_color")); + text_editor->add_theme_color_override("completion_existing_color", EDITOR_GET("text_editor/highlighting/completion_existing_color")); + text_editor->add_theme_color_override("completion_scroll_color", EDITOR_GET("text_editor/highlighting/completion_scroll_color")); + text_editor->add_theme_color_override("completion_font_color", EDITOR_GET("text_editor/highlighting/completion_font_color")); + text_editor->add_theme_color_override("font_color", EDITOR_GET("text_editor/highlighting/text_color")); + text_editor->add_theme_color_override("line_number_color", EDITOR_GET("text_editor/highlighting/line_number_color")); + text_editor->add_theme_color_override("caret_color", EDITOR_GET("text_editor/highlighting/caret_color")); + text_editor->add_theme_color_override("caret_background_color", EDITOR_GET("text_editor/highlighting/caret_background_color")); + text_editor->add_theme_color_override("font_selected_color", EDITOR_GET("text_editor/highlighting/text_selected_color")); + text_editor->add_theme_color_override("selection_color", EDITOR_GET("text_editor/highlighting/selection_color")); + text_editor->add_theme_color_override("brace_mismatch_color", EDITOR_GET("text_editor/highlighting/brace_mismatch_color")); + text_editor->add_theme_color_override("current_line_color", EDITOR_GET("text_editor/highlighting/current_line_color")); + text_editor->add_theme_color_override("line_length_guideline_color", EDITOR_GET("text_editor/highlighting/line_length_guideline_color")); + text_editor->add_theme_color_override("word_highlighted_color", EDITOR_GET("text_editor/highlighting/word_highlighted_color")); + text_editor->add_theme_color_override("bookmark_color", EDITOR_GET("text_editor/highlighting/bookmark_color")); + text_editor->add_theme_color_override("breakpoint_color", EDITOR_GET("text_editor/highlighting/breakpoint_color")); + text_editor->add_theme_color_override("executing_line_color", EDITOR_GET("text_editor/highlighting/executing_line_color")); + text_editor->add_theme_color_override("code_folding_color", EDITOR_GET("text_editor/highlighting/code_folding_color")); + text_editor->add_theme_color_override("search_result_color", EDITOR_GET("text_editor/highlighting/search_result_color")); + text_editor->add_theme_color_override("search_result_border_color", EDITOR_GET("text_editor/highlighting/search_result_border_color")); + text_editor->add_theme_constant_override("line_spacing", EDITOR_DEF("text_editor/theme/line_spacing", 6)); + emit_signal("load_theme_settings"); + _load_theme_settings(); +} + void CodeTextEditor::_update_font() { text_editor->add_theme_font_override("font", get_theme_font("source", "EditorFonts")); text_editor->add_theme_font_size_override("font_size", get_theme_font_size("source_size", "EditorFonts")); @@ -1497,6 +1525,7 @@ void CodeTextEditor::_update_font() { } void CodeTextEditor::_on_settings_change() { + _update_text_editor_theme(); _update_font(); font_size = EditorSettings::get_singleton()->get("interface/editor/code_font_size"); @@ -1583,14 +1612,11 @@ void CodeTextEditor::_error_pressed(const Ref<InputEvent> &p_event) { void CodeTextEditor::_notification(int p_what) { switch (p_what) { - case EditorSettings::NOTIFICATION_EDITOR_SETTINGS_CHANGED: { - _load_theme_settings(); - emit_signal("load_theme_settings"); - } break; case NOTIFICATION_THEME_CHANGED: { if (toggle_scripts_button->is_visible()) { update_toggle_scripts_button(); } + _update_text_editor_theme(); _update_font(); } break; case NOTIFICATION_ENTER_TREE: { diff --git a/editor/code_editor.h b/editor/code_editor.h index e201da446e..e6dadbd6fa 100644 --- a/editor/code_editor.h +++ b/editor/code_editor.h @@ -161,6 +161,7 @@ class CodeTextEditor : public VBoxContainer { void _on_settings_change(); + void _update_text_editor_theme(); void _update_font(); void _complete_request(); Ref<Texture2D> _get_completion_icon(const ScriptCodeCompletionOption &p_option); diff --git a/editor/editor_inspector.cpp b/editor/editor_inspector.cpp index 29cc4c3c46..0616ab07bd 100644 --- a/editor/editor_inspector.cpp +++ b/editor/editor_inspector.cpp @@ -741,7 +741,7 @@ void EditorProperty::_gui_input(const Ref<InputEvent> &p_event) { if (use_keying_next()) { if (property == "frame_coords" && (object->is_class("Sprite2D") || object->is_class("Sprite3D"))) { - Vector2 new_coords = object->get(property); + Vector2i new_coords = object->get(property); new_coords.x++; if (new_coords.x >= object->get("hframes").operator int64_t()) { new_coords.x = 0; @@ -1824,7 +1824,13 @@ void EditorInspector::update_tree() { } } - String path = basename.left(basename.rfind("/")); + String path; + { + int idx = basename.rfind("/"); + if (idx > -1) { + path = basename.left(idx); + } + } if (use_filter && filter != "") { String cat = path; diff --git a/editor/editor_log.cpp b/editor/editor_log.cpp index 469fb41406..622b3fe355 100644 --- a/editor/editor_log.cpp +++ b/editor/editor_log.cpp @@ -234,7 +234,9 @@ void EditorLog::_add_log_line(LogMessage &p_message, bool p_replace_previous) { if (p_replace_previous) { // Remove last line if replacing, as it will be replace by the next added line. - log->remove_line(log->get_line_count() - 1); + // Why - 2? RichTextLabel is weird. When you add a line, it also adds a NEW line, which is null, + // but it still counts as a line. So if you remove the last line (count - 1) you are actually removing nothing... + log->remove_line(log->get_line_count() - 2); log->increment_line_count(); } diff --git a/editor/editor_spin_slider.cpp b/editor/editor_spin_slider.cpp index 942a2d35ab..657dcfa760 100644 --- a/editor/editor_spin_slider.cpp +++ b/editor/editor_spin_slider.cpp @@ -70,6 +70,7 @@ void EditorSpinSlider::_gui_input(const Ref<InputEvent> &p_event) { grabbing_spinner_dist_cache = 0; pre_grab_value = get_value(); grabbing_spinner = false; + grabbing_spinner_mouse_pos = get_global_mouse_position(); } } else { if (grabbing_spinner_attempt) { diff --git a/editor/editor_themes.cpp b/editor/editor_themes.cpp index 2c4f4e2973..463989868d 100644 --- a/editor/editor_themes.cpp +++ b/editor/editor_themes.cpp @@ -216,6 +216,7 @@ void editor_register_and_generate_icons(Ref<Theme> p_theme, bool p_dark_theme = exceptions.insert("Sky"); exceptions.insert("EditorControlAnchor"); exceptions.insert("DefaultProjectIcon"); + exceptions.insert("GuiChecked"); exceptions.insert("GuiCloseCustomizable"); exceptions.insert("GuiGraphNodePort"); exceptions.insert("GuiResizer"); diff --git a/editor/icons/GuiChecked.svg b/editor/icons/GuiChecked.svg index 9bdf5dcb19..31b2995939 100644 --- a/editor/icons/GuiChecked.svg +++ b/editor/icons/GuiChecked.svg @@ -1 +1 @@ -<svg height="16" viewBox="0 0 16 15.999999" width="16" xmlns="http://www.w3.org/2000/svg"><g fill="#e0e0e0"><path d="m3.3333333 1c-1.2887 0-2.3333333 1.0446683-2.3333333 2.3333333v9.3333337c0 1.2887 1.0446683 2.333333 2.3333333 2.333333h9.3333337c1.2887 0 2.333333-1.044668 2.333333-2.333333v-9.3333337c0-1.2887-1.044668-2.3333333-2.333333-2.3333333z" fill-opacity=".188235" stroke-width="1.166667"/><path d="m11.500773 3.7343508-5.6117507 5.6117502-1.7045017-1.6814543-1.4992276 1.4992276 3.2037293 3.1806817 7.1109777-7.1109775z" stroke-width="1.060227"/></g></svg> +<svg height="16" viewBox="0 0 16 15.999999" width="16" xmlns="http://www.w3.org/2000/svg"><path d="m3.3333333 1c-1.2887 0-2.3333333 1.0446683-2.3333333 2.3333333v9.3333337c0 1.2887 1.0446683 2.333333 2.3333333 2.333333h9.3333337c1.2887 0 2.333333-1.044668 2.333333-2.333333v-9.3333337c0-1.2887-1.044668-2.3333333-2.333333-2.3333333z" fill="#699ce8" stroke-width="1.16667"/><path d="m11.500773 3.7343508-5.6117507 5.6117502-1.7045017-1.6814543-1.4992276 1.4992276 3.2037293 3.1806817 7.1109777-7.1109775z" fill="#fff" stroke-width="1.06023"/></svg> diff --git a/editor/import/scene_importer_mesh.cpp b/editor/import/scene_importer_mesh.cpp index bc7e8a1626..fa1a027a8d 100644 --- a/editor/import/scene_importer_mesh.cpp +++ b/editor/import/scene_importer_mesh.cpp @@ -30,6 +30,7 @@ #include "scene_importer_mesh.h" +#include "core/math/math_defs.h" #include "scene/resources/surface_tool.h" void EditorSceneImporterMesh::add_blend_shape(const String &p_name) { @@ -141,6 +142,18 @@ void EditorSceneImporterMesh::set_surface_material(int p_surface, const Ref<Mate surfaces.write[p_surface].material = p_material; } +Basis EditorSceneImporterMesh::compute_rotation_matrix_from_ortho_6d(Vector3 p_x_raw, Vector3 p_y_raw) { + Vector3 x = p_x_raw.normalized(); + Vector3 z = x.cross(p_y_raw); + z = z.normalized(); + Vector3 y = z.cross(x); + Basis basis; + basis.set_axis(Vector3::AXIS_X, x); + basis.set_axis(Vector3::AXIS_Y, y); + basis.set_axis(Vector3::AXIS_Z, z); + return basis; +} + void EditorSceneImporterMesh::generate_lods() { if (!SurfaceTool::simplify_func) { return; @@ -151,6 +164,9 @@ void EditorSceneImporterMesh::generate_lods() { if (!SurfaceTool::simplify_sloppy_func) { return; } + if (!SurfaceTool::simplify_with_attrib_func) { + return; + } for (int i = 0; i < surfaces.size(); i++) { if (surfaces[i].primitive != Mesh::PRIMITIVE_TRIANGLES) { @@ -163,59 +179,62 @@ void EditorSceneImporterMesh::generate_lods() { if (indices.size() == 0) { continue; //no lods if no indices } + Vector<Vector3> normals = surfaces[i].arrays[RS::ARRAY_NORMAL]; uint32_t vertex_count = vertices.size(); const Vector3 *vertices_ptr = vertices.ptr(); - - int min_indices = 10; - int index_target = indices.size() / 2; - print_line("Total indices: " + itos(indices.size())); - float mesh_scale = SurfaceTool::simplify_scale_func((const float *)vertices_ptr, vertex_count, sizeof(Vector3)); - const float target_error = 1e-3f; - float abs_target_error = target_error / mesh_scale; + Vector<float> attributes; + Vector<float> normal_weights; + int32_t attribute_count = 6; + if (normals.size()) { + attributes.resize(normals.size() * attribute_count); + for (int32_t normal_i = 0; normal_i < normals.size(); normal_i++) { + Basis basis; + basis.set_euler(normals[normal_i]); + Vector3 basis_x = basis.get_axis(0); + Vector3 basis_y = basis.get_axis(1); + basis = compute_rotation_matrix_from_ortho_6d(basis_x, basis_y); + basis_x = basis.get_axis(0); + basis_y = basis.get_axis(1); + attributes.write[normal_i * attribute_count + 0] = basis_x.x; + attributes.write[normal_i * attribute_count + 1] = basis_x.y; + attributes.write[normal_i * attribute_count + 2] = basis_x.z; + attributes.write[normal_i * attribute_count + 3] = basis_y.x; + attributes.write[normal_i * attribute_count + 4] = basis_y.y; + attributes.write[normal_i * attribute_count + 5] = basis_y.z; + } + normal_weights.resize(vertex_count); + for (int32_t weight_i = 0; weight_i < normal_weights.size(); weight_i++) { + normal_weights.write[weight_i] = 1.0; + } + } else { + attribute_count = 0; + } + const int min_indices = 10; + const float error_tolerance = 1.44224'95703; // Cube root of 3 + const float threshold = 1.0 / error_tolerance; + int index_target = indices.size() * threshold; + float max_mesh_error_percentage = 1e0f; + float mesh_error = 0.0f; while (index_target > min_indices) { - float error; Vector<int> new_indices; new_indices.resize(indices.size()); - size_t new_len = SurfaceTool::simplify_func((unsigned int *)new_indices.ptrw(), (const unsigned int *)indices.ptr(), indices.size(), (const float *)vertices_ptr, vertex_count, sizeof(Vector3), index_target, abs_target_error, &error); - if ((int)new_len > (index_target * 120 / 100)) { - // Attribute discontinuities break normals. - bool is_sloppy = false; - if (is_sloppy) { - abs_target_error = target_error / mesh_scale; - index_target = new_len; - while (index_target > min_indices) { - Vector<int> sloppy_new_indices; - sloppy_new_indices.resize(indices.size()); - new_len = SurfaceTool::simplify_sloppy_func((unsigned int *)sloppy_new_indices.ptrw(), (const unsigned int *)indices.ptr(), indices.size(), (const float *)vertices_ptr, vertex_count, sizeof(Vector3), index_target, abs_target_error, &error); - if ((int)new_len > (index_target * 120 / 100)) { - break; // 20 percent tolerance - } - sloppy_new_indices.resize(new_len); - Surface::LOD lod; - lod.distance = error * mesh_scale; - abs_target_error = lod.distance; - if (Math::is_equal_approx(abs_target_error, 0.0f)) { - return; - } - lod.indices = sloppy_new_indices; - print_line("Lod " + itos(surfaces.write[i].lods.size()) + " shoot for " + itos(index_target / 3) + " triangles, got " + itos(new_len / 3) + " triangles. Distance " + rtos(lod.distance) + ". Use simplify sloppy."); - surfaces.write[i].lods.push_back(lod); - index_target /= 2; - } - } - break; // 20 percent tolerance + size_t new_len = SurfaceTool::simplify_with_attrib_func((unsigned int *)new_indices.ptrw(), (const unsigned int *)indices.ptr(), indices.size(), (const float *)vertices_ptr, vertex_count, sizeof(Vector3), index_target, max_mesh_error_percentage, &mesh_error, (float *)attributes.ptrw(), normal_weights.ptrw(), attribute_count); + if ((int)new_len > (index_target * error_tolerance)) { + break; } - new_indices.resize(new_len); Surface::LOD lod; - lod.distance = error * mesh_scale; - abs_target_error = lod.distance; - if (Math::is_equal_approx(abs_target_error, 0.0f)) { - return; + lod.distance = mesh_error; + if (Math::is_equal_approx(mesh_error, 0.0f)) { + break; + } + if (new_len <= 0) { + break; } + new_indices.resize(new_len); lod.indices = new_indices; - print_line("Lod " + itos(surfaces.write[i].lods.size()) + " shoot for " + itos(index_target / 3) + " triangles, got " + itos(new_len / 3) + " triangles. Distance " + rtos(lod.distance)); + print_line("Lod " + itos(surfaces.write[i].lods.size()) + " begin with " + itos(indices.size() / 3) + " triangles and shoot for " + itos(index_target / 3) + " triangles. Got " + itos(new_len / 3) + " triangles. Lod screen ratio " + rtos(lod.distance)); surfaces.write[i].lods.push_back(lod); - index_target /= 2; + index_target *= threshold; } } } diff --git a/editor/import/scene_importer_mesh.h b/editor/import/scene_importer_mesh.h index b3e8137e0a..c00339a620 100644 --- a/editor/import/scene_importer_mesh.h +++ b/editor/import/scene_importer_mesh.h @@ -67,6 +67,7 @@ class EditorSceneImporterMesh : public Resource { Ref<EditorSceneImporterMesh> shadow_mesh; Size2i lightmap_size_hint; + Basis compute_rotation_matrix_from_ortho_6d(Vector3 p_x_raw, Vector3 y_raw); protected: void _set_data(const Dictionary &p_data); diff --git a/editor/node_3d_editor_gizmos.cpp b/editor/node_3d_editor_gizmos.cpp index afafd7d195..cc261ea868 100644 --- a/editor/node_3d_editor_gizmos.cpp +++ b/editor/node_3d_editor_gizmos.cpp @@ -30,9 +30,9 @@ #include "node_3d_editor_gizmos.h" +#include "core/math/convex_hull.h" #include "core/math/geometry_2d.h" #include "core/math/geometry_3d.h" -#include "core/math/quick_hull.h" #include "scene/3d/audio_stream_player_3d.h" #include "scene/3d/baked_lightmap.h" #include "scene/3d/collision_polygon_3d.h" @@ -4161,7 +4161,7 @@ void CollisionShape3DGizmoPlugin::redraw(EditorNode3DGizmo *p_gizmo) { if (points.size() > 3) { Vector<Vector3> varr = Variant(points); Geometry3D::MeshData md; - Error err = QuickHull::build(varr, md); + Error err = ConvexHullComputer::convex_hull(varr, md); if (err == OK) { Vector<Vector3> points2; points2.resize(md.edges.size() * 2); diff --git a/editor/plugins/animation_player_editor_plugin.cpp b/editor/plugins/animation_player_editor_plugin.cpp index e459d2f756..bd88d96a66 100644 --- a/editor/plugins/animation_player_editor_plugin.cpp +++ b/editor/plugins/animation_player_editor_plugin.cpp @@ -994,7 +994,7 @@ void AnimationPlayerEditor::_animation_duplicate() { } } -void AnimationPlayerEditor::_seek_value_changed(float p_value, bool p_set) { +void AnimationPlayerEditor::_seek_value_changed(float p_value, bool p_set, bool p_timeline_only) { if (updating || !player || player->is_playing()) { return; }; @@ -1015,18 +1015,18 @@ void AnimationPlayerEditor::_seek_value_changed(float p_value, bool p_set) { pos = Math::snapped(pos, _get_editor_step()); } - if (player->is_valid() && !p_set) { - float cpos = player->get_current_animation_position(); + if (!p_timeline_only) { + if (player->is_valid() && !p_set) { + float cpos = player->get_current_animation_position(); - player->seek_delta(pos, pos - cpos); - } else { - player->stop(true); - player->seek(pos, true); + player->seek_delta(pos, pos - cpos); + } else { + player->stop(true); + player->seek(pos, true); + } } track_editor->set_anim_pos(pos); - - updating = true; }; void AnimationPlayerEditor::_animation_player_changed(Object *p_pl) { @@ -1048,7 +1048,7 @@ void AnimationPlayerEditor::_animation_key_editor_anim_len_changed(float p_len) frame->set_max(p_len); } -void AnimationPlayerEditor::_animation_key_editor_seek(float p_pos, bool p_drag) { +void AnimationPlayerEditor::_animation_key_editor_seek(float p_pos, bool p_drag, bool p_timeline_only) { timeline_position = p_pos; if (!is_visible_in_tree()) { @@ -1070,7 +1070,7 @@ void AnimationPlayerEditor::_animation_key_editor_seek(float p_pos, bool p_drag) updating = true; frame->set_value(Math::snapped(p_pos, _get_editor_step())); updating = false; - _seek_value_changed(p_pos, !p_drag); + _seek_value_changed(p_pos, !p_drag, p_timeline_only); } void AnimationPlayerEditor::_animation_tool_menu(int p_option) { @@ -1693,7 +1693,7 @@ AnimationPlayerEditor::AnimationPlayerEditor(EditorNode *p_editor, AnimationPlay animation->connect("item_selected", callable_mp(this, &AnimationPlayerEditor::_animation_selected)); file->connect("file_selected", callable_mp(this, &AnimationPlayerEditor::_dialog_action)); - frame->connect("value_changed", callable_mp(this, &AnimationPlayerEditor::_seek_value_changed), make_binds(true)); + frame->connect("value_changed", callable_mp(this, &AnimationPlayerEditor::_seek_value_changed), make_binds(true, false)); scale->connect("text_entered", callable_mp(this, &AnimationPlayerEditor::_scale_changed)); renaming = false; diff --git a/editor/plugins/animation_player_editor_plugin.h b/editor/plugins/animation_player_editor_plugin.h index 2f6bf55e4c..5c2348f86b 100644 --- a/editor/plugins/animation_player_editor_plugin.h +++ b/editor/plugins/animation_player_editor_plugin.h @@ -187,7 +187,7 @@ class AnimationPlayerEditor : public VBoxContainer { void _scale_changed(const String &p_scale); void _dialog_action(String p_file); void _seek_frame_changed(const String &p_frame); - void _seek_value_changed(float p_value, bool p_set = false); + void _seek_value_changed(float p_value, bool p_set = false, bool p_timeline_only = false); void _blend_editor_next_changed(const int p_idx); void _list_changed(); @@ -197,7 +197,7 @@ class AnimationPlayerEditor : public VBoxContainer { void _animation_player_changed(Object *p_pl); - void _animation_key_editor_seek(float p_pos, bool p_drag); + void _animation_key_editor_seek(float p_pos, bool p_drag, bool p_timeline_only = false); void _animation_key_editor_anim_len_changed(float p_len); void _unhandled_key_input(const Ref<InputEvent> &p_ev); diff --git a/editor/plugins/script_text_editor.cpp b/editor/plugins/script_text_editor.cpp index 25755cc6cc..72a4bd8243 100644 --- a/editor/plugins/script_text_editor.cpp +++ b/editor/plugins/script_text_editor.cpp @@ -170,66 +170,25 @@ void ScriptTextEditor::_load_theme_settings() { CodeEdit *text_edit = code_editor->get_text_editor(); text_edit->clear_keywords(); + Color updated_marked_line_color = EDITOR_GET("text_editor/highlighting/mark_color"); Color updated_safe_line_number_color = EDITOR_GET("text_editor/highlighting/safe_line_number_color"); - if (updated_safe_line_number_color != safe_line_number_color) { + + bool safe_line_number_color_updated = updated_safe_line_number_color != safe_line_number_color; + bool marked_line_color_updated = updated_marked_line_color != marked_line_color; + if (safe_line_number_color_updated || marked_line_color_updated) { safe_line_number_color = updated_safe_line_number_color; for (int i = 0; i < text_edit->get_line_count(); i++) { - if (text_edit->get_line_gutter_item_color(i, line_number_gutter) != default_line_number_color) { + if (marked_line_color_updated && text_edit->get_line_background_color(i) == marked_line_color) { + text_edit->set_line_background_color(i, updated_marked_line_color); + } + + if (safe_line_number_color_updated && text_edit->get_line_gutter_item_color(i, line_number_gutter) != default_line_number_color) { text_edit->set_line_gutter_item_color(i, line_number_gutter, safe_line_number_color); } } + marked_line_color = updated_marked_line_color; } - Color background_color = EDITOR_GET("text_editor/highlighting/background_color"); - Color completion_background_color = EDITOR_GET("text_editor/highlighting/completion_background_color"); - Color completion_selected_color = EDITOR_GET("text_editor/highlighting/completion_selected_color"); - Color completion_existing_color = EDITOR_GET("text_editor/highlighting/completion_existing_color"); - Color completion_scroll_color = EDITOR_GET("text_editor/highlighting/completion_scroll_color"); - Color completion_font_color = EDITOR_GET("text_editor/highlighting/completion_font_color"); - Color text_color = EDITOR_GET("text_editor/highlighting/text_color"); - Color line_number_color = EDITOR_GET("text_editor/highlighting/line_number_color"); - Color caret_color = EDITOR_GET("text_editor/highlighting/caret_color"); - Color caret_background_color = EDITOR_GET("text_editor/highlighting/caret_background_color"); - Color text_selected_color = EDITOR_GET("text_editor/highlighting/text_selected_color"); - Color selection_color = EDITOR_GET("text_editor/highlighting/selection_color"); - Color brace_mismatch_color = EDITOR_GET("text_editor/highlighting/brace_mismatch_color"); - Color current_line_color = EDITOR_GET("text_editor/highlighting/current_line_color"); - Color line_length_guideline_color = EDITOR_GET("text_editor/highlighting/line_length_guideline_color"); - Color word_highlighted_color = EDITOR_GET("text_editor/highlighting/word_highlighted_color"); - Color mark_color = EDITOR_GET("text_editor/highlighting/mark_color"); - Color bookmark_color = EDITOR_GET("text_editor/highlighting/bookmark_color"); - Color breakpoint_color = EDITOR_GET("text_editor/highlighting/breakpoint_color"); - Color executing_line_color = EDITOR_GET("text_editor/highlighting/executing_line_color"); - Color code_folding_color = EDITOR_GET("text_editor/highlighting/code_folding_color"); - Color search_result_color = EDITOR_GET("text_editor/highlighting/search_result_color"); - Color search_result_border_color = EDITOR_GET("text_editor/highlighting/search_result_border_color"); - - text_edit->add_theme_color_override("background_color", background_color); - text_edit->add_theme_color_override("completion_background_color", completion_background_color); - text_edit->add_theme_color_override("completion_selected_color", completion_selected_color); - text_edit->add_theme_color_override("completion_existing_color", completion_existing_color); - text_edit->add_theme_color_override("completion_scroll_color", completion_scroll_color); - text_edit->add_theme_color_override("completion_font_color", completion_font_color); - text_edit->add_theme_color_override("font_color", text_color); - text_edit->add_theme_color_override("line_number_color", line_number_color); - text_edit->add_theme_color_override("caret_color", caret_color); - text_edit->add_theme_color_override("caret_background_color", caret_background_color); - text_edit->add_theme_color_override("font_selected_color", text_selected_color); - text_edit->add_theme_color_override("selection_color", selection_color); - text_edit->add_theme_color_override("brace_mismatch_color", brace_mismatch_color); - text_edit->add_theme_color_override("current_line_color", current_line_color); - text_edit->add_theme_color_override("line_length_guideline_color", line_length_guideline_color); - text_edit->add_theme_color_override("word_highlighted_color", word_highlighted_color); - text_edit->add_theme_color_override("bookmark_color", bookmark_color); - text_edit->add_theme_color_override("breakpoint_color", breakpoint_color); - text_edit->add_theme_color_override("executing_line_color", executing_line_color); - text_edit->add_theme_color_override("mark_color", mark_color); - text_edit->add_theme_color_override("code_folding_color", code_folding_color); - text_edit->add_theme_color_override("search_result_color", search_result_color); - text_edit->add_theme_color_override("search_result_border_color", search_result_border_color); - - text_edit->add_theme_constant_override("line_spacing", EDITOR_DEF("text_editor/theme/line_spacing", 6)); - theme_loaded = true; if (!script.is_null()) { _set_theme_for_script(); @@ -546,7 +505,7 @@ void ScriptTextEditor::_validate_script() { bool highlight_safe = EDITOR_DEF("text_editor/highlighting/highlight_type_safe_lines", true); bool last_is_safe = false; for (int i = 0; i < te->get_line_count(); i++) { - te->set_line_as_marked(i, line == i); + te->set_line_background_color(i, (line == i) ? marked_line_color : Color(0, 0, 0, 0)); if (highlight_safe) { if (safe_lines.has(i + 1)) { te->set_line_gutter_item_color(i, line_number_gutter, safe_line_number_color); @@ -1937,7 +1896,7 @@ void ScriptTextEditor::register_editor() { #ifdef OSX_ENABLED ED_SHORTCUT("script_text_editor/clone_down", TTR("Clone Down"), KEY_MASK_SHIFT | KEY_MASK_CMD | KEY_C); #else - ED_SHORTCUT("script_text_editor/clone_down", TTR("Clone Down"), KEY_MASK_CMD | KEY_D); + ED_SHORTCUT("script_text_editor/clone_down", TTR("Clone Down"), KEY_MASK_SHIFT | KEY_MASK_CMD | KEY_D); #endif ED_SHORTCUT("script_text_editor/evaluate_selection", TTR("Evaluate Selection"), KEY_MASK_CMD | KEY_MASK_SHIFT | KEY_E); ED_SHORTCUT("script_text_editor/trim_trailing_whitespace", TTR("Trim Trailing Whitespace"), KEY_MASK_CMD | KEY_MASK_ALT | KEY_T); diff --git a/editor/plugins/script_text_editor.h b/editor/plugins/script_text_editor.h index f79abc60ab..f784bbe1f8 100644 --- a/editor/plugins/script_text_editor.h +++ b/editor/plugins/script_text_editor.h @@ -89,6 +89,8 @@ class ScriptTextEditor : public ScriptEditorBase { Color default_line_number_color = Color(1, 1, 1); Color safe_line_number_color = Color(1, 1, 1); + Color marked_line_color = Color(1, 1, 1); + PopupPanel *color_panel = nullptr; ColorPicker *color_picker = nullptr; Vector2 color_position; diff --git a/editor/plugins/shader_editor_plugin.cpp b/editor/plugins/shader_editor_plugin.cpp index 3cdba9cf16..a210a46127 100644 --- a/editor/plugins/shader_editor_plugin.cpp +++ b/editor/plugins/shader_editor_plugin.cpp @@ -37,12 +37,18 @@ #include "editor/editor_node.h" #include "editor/editor_scale.h" #include "editor/editor_settings.h" +#include "editor/project_settings_editor.h" #include "editor/property_editor.h" #include "servers/display_server.h" #include "servers/rendering/shader_types.h" /*** SHADER SCRIPT EDITOR ****/ +static bool saved_warnings_enabled = false; +static bool saved_treat_warning_as_errors = false; +static Map<ShaderWarning::Code, bool> saved_warnings; +static uint32_t saved_warning_flags = 0U; + Ref<Shader> ShaderTextEditor::get_edited_shader() const { return shader; } @@ -57,6 +63,8 @@ void ShaderTextEditor::set_edited_shader(const Ref<Shader> &p_shader) { get_text_editor()->set_text(p_shader->get_code()); get_text_editor()->clear_undo_history(); + get_text_editor()->call_deferred("set_h_scroll", 0); + get_text_editor()->call_deferred("set_v_scroll", 0); _validate_script(); _line_col_changed(); @@ -82,54 +90,21 @@ void ShaderTextEditor::reload_text() { update_line_and_column(); } +void ShaderTextEditor::set_warnings_panel(RichTextLabel *p_warnings_panel) { + warnings_panel = p_warnings_panel; +} + void ShaderTextEditor::_load_theme_settings() { - Color background_color = EDITOR_GET("text_editor/highlighting/background_color"); - Color completion_background_color = EDITOR_GET("text_editor/highlighting/completion_background_color"); - Color completion_selected_color = EDITOR_GET("text_editor/highlighting/completion_selected_color"); - Color completion_existing_color = EDITOR_GET("text_editor/highlighting/completion_existing_color"); - Color completion_scroll_color = EDITOR_GET("text_editor/highlighting/completion_scroll_color"); - Color completion_font_color = EDITOR_GET("text_editor/highlighting/completion_font_color"); - Color text_color = EDITOR_GET("text_editor/highlighting/text_color"); - Color line_number_color = EDITOR_GET("text_editor/highlighting/line_number_color"); - Color caret_color = EDITOR_GET("text_editor/highlighting/caret_color"); - Color caret_background_color = EDITOR_GET("text_editor/highlighting/caret_background_color"); - Color text_selected_color = EDITOR_GET("text_editor/highlighting/text_selected_color"); - Color selection_color = EDITOR_GET("text_editor/highlighting/selection_color"); - Color brace_mismatch_color = EDITOR_GET("text_editor/highlighting/brace_mismatch_color"); - Color current_line_color = EDITOR_GET("text_editor/highlighting/current_line_color"); - Color line_length_guideline_color = EDITOR_GET("text_editor/highlighting/line_length_guideline_color"); - Color word_highlighted_color = EDITOR_GET("text_editor/highlighting/word_highlighted_color"); - Color mark_color = EDITOR_GET("text_editor/highlighting/mark_color"); - Color bookmark_color = EDITOR_GET("text_editor/highlighting/bookmark_color"); - Color breakpoint_color = EDITOR_GET("text_editor/highlighting/breakpoint_color"); - Color executing_line_color = EDITOR_GET("text_editor/highlighting/executing_line_color"); - Color code_folding_color = EDITOR_GET("text_editor/highlighting/code_folding_color"); - Color search_result_color = EDITOR_GET("text_editor/highlighting/search_result_color"); - Color search_result_border_color = EDITOR_GET("text_editor/highlighting/search_result_border_color"); - - get_text_editor()->add_theme_color_override("background_color", background_color); - get_text_editor()->add_theme_color_override("completion_background_color", completion_background_color); - get_text_editor()->add_theme_color_override("completion_selected_color", completion_selected_color); - get_text_editor()->add_theme_color_override("completion_existing_color", completion_existing_color); - get_text_editor()->add_theme_color_override("completion_scroll_color", completion_scroll_color); - get_text_editor()->add_theme_color_override("completion_font_color", completion_font_color); - get_text_editor()->add_theme_color_override("font_color", text_color); - get_text_editor()->add_theme_color_override("line_number_color", line_number_color); - get_text_editor()->add_theme_color_override("caret_color", caret_color); - get_text_editor()->add_theme_color_override("caret_background_color", caret_background_color); - get_text_editor()->add_theme_color_override("font_selected_color", text_selected_color); - get_text_editor()->add_theme_color_override("selection_color", selection_color); - get_text_editor()->add_theme_color_override("brace_mismatch_color", brace_mismatch_color); - get_text_editor()->add_theme_color_override("current_line_color", current_line_color); - get_text_editor()->add_theme_color_override("line_length_guideline_color", line_length_guideline_color); - get_text_editor()->add_theme_color_override("word_highlighted_color", word_highlighted_color); - get_text_editor()->add_theme_color_override("mark_color", mark_color); - get_text_editor()->add_theme_color_override("bookmark_color", bookmark_color); - get_text_editor()->add_theme_color_override("breakpoint_color", breakpoint_color); - get_text_editor()->add_theme_color_override("executing_line_color", executing_line_color); - get_text_editor()->add_theme_color_override("code_folding_color", code_folding_color); - get_text_editor()->add_theme_color_override("search_result_color", search_result_color); - get_text_editor()->add_theme_color_override("search_result_border_color", search_result_border_color); + CodeEdit *text_editor = get_text_editor(); + Color updated_marked_line_color = EDITOR_GET("text_editor/highlighting/mark_color"); + if (updated_marked_line_color != marked_line_color) { + for (int i = 0; i < text_editor->get_line_count(); i++) { + if (text_editor->get_line_background_color(i) == marked_line_color) { + text_editor->set_line_background_color(i, updated_marked_line_color); + } + } + marked_line_color = updated_marked_line_color; + } syntax_highlighter->set_number_color(EDITOR_GET("text_editor/highlighting/number_color")); syntax_highlighter->set_symbol_color(EDITOR_GET("text_editor/highlighting/symbol_color")); @@ -178,6 +153,12 @@ void ShaderTextEditor::_load_theme_settings() { syntax_highlighter->clear_color_regions(); syntax_highlighter->add_color_region("/*", "*/", comment_color, false); syntax_highlighter->add_color_region("//", "", comment_color, true); + + if (warnings_panel) { + // Warnings panel + warnings_panel->add_theme_font_override("normal_font", EditorNode::get_singleton()->get_gui_base()->get_theme_font("main", "EditorFonts")); + warnings_panel->add_theme_font_size_override("normal_font_size", EditorNode::get_singleton()->get_gui_base()->get_theme_font_size("main_size", "EditorFonts")); + } } void ShaderTextEditor::_check_shader_mode() { @@ -224,6 +205,9 @@ void ShaderTextEditor::_validate_script() { ShaderLanguage sl; + sl.enable_warning_checking(saved_warnings_enabled); + sl.set_warning_flags(saved_warning_flags); + Error err = sl.compile(code, ShaderTypes::get_singleton()->get_functions(RenderingServer::ShaderMode(shader->get_mode())), ShaderTypes::get_singleton()->get_modes(RenderingServer::ShaderMode(shader->get_mode())), ShaderLanguage::VaryingFunctionNames(), ShaderTypes::get_singleton()->get_types(), _get_global_variable_type); if (err != OK) { @@ -231,20 +215,70 @@ void ShaderTextEditor::_validate_script() { set_error(error_text); set_error_pos(sl.get_error_line() - 1, 0); for (int i = 0; i < get_text_editor()->get_line_count(); i++) { - get_text_editor()->set_line_as_marked(i, false); + get_text_editor()->set_line_background_color(i, Color(0, 0, 0, 0)); } - get_text_editor()->set_line_as_marked(sl.get_error_line() - 1, true); - + get_text_editor()->set_line_background_color(sl.get_error_line() - 1, marked_line_color); } else { for (int i = 0; i < get_text_editor()->get_line_count(); i++) { - get_text_editor()->set_line_as_marked(i, false); + get_text_editor()->set_line_background_color(i, Color(0, 0, 0, 0)); } set_error(""); } + if (warnings.size() > 0 || err != OK) { + warnings_panel->clear(); + } + warnings.clear(); + for (List<ShaderWarning>::Element *E = sl.get_warnings_ptr(); E; E = E->next()) { + warnings.push_back(E->get()); + } + if (warnings.size() > 0 && err == OK) { + warnings.sort_custom<WarningsComparator>(); + _update_warning_panel(); + } else { + set_warning_nb(0); + } emit_signal("script_changed"); } +void ShaderTextEditor::_update_warning_panel() { + int warning_count = 0; + + warnings_panel->push_table(2); + for (int i = 0; i < warnings.size(); i++) { + ShaderWarning &w = warnings[i]; + + if (warning_count == 0) { + if (saved_treat_warning_as_errors) { + String error_text = "error(" + itos(w.get_line()) + "): " + w.get_message() + " " + TTR("Warnings should be fixed to prevent errors."); + set_error_pos(w.get_line() - 1, 0); + set_error(error_text); + get_text_editor()->set_line_background_color(w.get_line() - 1, marked_line_color); + } + } + + warning_count++; + + // First cell. + warnings_panel->push_cell(); + warnings_panel->push_meta(w.get_line() - 1); + warnings_panel->push_color(warnings_panel->get_theme_color("warning_color", "Editor")); + warnings_panel->add_text(TTR("Line") + " " + itos(w.get_line())); + warnings_panel->add_text(" (" + w.get_name() + "):"); + warnings_panel->pop(); // Color. + warnings_panel->pop(); // Meta goto. + warnings_panel->pop(); // Cell. + + // Second cell. + warnings_panel->push_cell(); + warnings_panel->add_text(w.get_message()); + warnings_panel->pop(); // Cell. + } + warnings_panel->pop(); // Table. + + set_warning_nb(warning_count); +} + void ShaderTextEditor::_bind_methods() { } @@ -358,10 +392,6 @@ void ShaderEditor::_notification(int p_what) { } } -void ShaderEditor::_params_changed() { - shader_editor->_validate_script(); -} - void ShaderEditor::_editor_settings_changed() { shader_editor->update_editor_settings(); @@ -370,8 +400,19 @@ void ShaderEditor::_editor_settings_changed() { shader_editor->get_text_editor()->set_draw_executing_lines_gutter(false); } +void ShaderEditor::_show_warnings_panel(bool p_show) { + warnings_panel->set_visible(p_show); +} + +void ShaderEditor::_warning_clicked(Variant p_line) { + if (p_line.get_type() == Variant::INT) { + shader_editor->get_text_editor()->cursor_set_line(p_line.operator int64_t()); + } +} + void ShaderEditor::_bind_methods() { - ClassDB::bind_method("_params_changed", &ShaderEditor::_params_changed); + ClassDB::bind_method("_show_warnings_panel", &ShaderEditor::_show_warnings_panel); + ClassDB::bind_method("_warning_clicked", &ShaderEditor::_warning_clicked); } void ShaderEditor::ensure_select_current() { @@ -389,6 +430,47 @@ void ShaderEditor::goto_line_selection(int p_line, int p_begin, int p_end) { shader_editor->goto_line_selection(p_line, p_begin, p_end); } +void ShaderEditor::_project_settings_changed() { + _update_warnings(true); +} + +void ShaderEditor::_update_warnings(bool p_validate) { + bool changed = false; + + bool warnings_enabled = GLOBAL_GET("debug/shader_language/warnings/enable").booleanize(); + if (warnings_enabled != saved_warnings_enabled) { + saved_warnings_enabled = warnings_enabled; + changed = true; + } + + bool treat_warning_as_errors = GLOBAL_GET("debug/shader_language/warnings/treat_warnings_as_errors").booleanize(); + if (treat_warning_as_errors != saved_treat_warning_as_errors) { + saved_treat_warning_as_errors = treat_warning_as_errors; + changed = true; + } + + bool update_flags = false; + + for (int i = 0; i < ShaderWarning::WARNING_MAX; i++) { + ShaderWarning::Code code = (ShaderWarning::Code)i; + bool value = GLOBAL_GET("debug/shader_language/warnings/" + ShaderWarning::get_name_from_code(code).to_lower()); + + if (saved_warnings[code] != value) { + saved_warnings[code] = value; + update_flags = true; + changed = true; + } + } + + if (update_flags) { + saved_warning_flags = (uint32_t)ShaderWarning::get_flags_from_codemap(saved_warnings); + } + + if (p_validate && changed && shader_editor && shader_editor->get_edited_shader().is_valid()) { + shader_editor->validate_script(); + } +} + void ShaderEditor::_check_for_external_edit() { if (shader.is_null() || !shader.is_valid()) { return; @@ -560,13 +642,22 @@ void ShaderEditor::_make_context_menu(bool p_selection, Vector2 p_position) { } ShaderEditor::ShaderEditor(EditorNode *p_node) { + GLOBAL_DEF("debug/shader_language/warnings/enable", true); + GLOBAL_DEF("debug/shader_language/warnings/treat_warnings_as_errors", false); + for (int i = 0; i < (int)ShaderWarning::WARNING_MAX; i++) { + GLOBAL_DEF("debug/shader_language/warnings/" + ShaderWarning::get_name_from_code((ShaderWarning::Code)i).to_lower(), true); + } + _update_warnings(false); + shader_editor = memnew(ShaderTextEditor); shader_editor->set_v_size_flags(SIZE_EXPAND_FILL); shader_editor->add_theme_constant_override("separation", 0); shader_editor->set_anchors_and_offsets_preset(Control::PRESET_WIDE); + shader_editor->connect("show_warnings_panel", callable_mp(this, &ShaderEditor::_show_warnings_panel)); shader_editor->connect("script_changed", callable_mp(this, &ShaderEditor::apply_shaders)); EditorSettings::get_singleton()->connect("settings_changed", callable_mp(this, &ShaderEditor::_editor_settings_changed)); + ProjectSettingsEditor::get_singleton()->connect("confirmed", callable_mp(this, &ShaderEditor::_project_settings_changed)); shader_editor->get_text_editor()->set_callhint_settings( EditorSettings::get_singleton()->get("text_editor/completion/put_callhint_tooltip_below_current_line"), @@ -651,7 +742,23 @@ ShaderEditor::ShaderEditor(EditorNode *p_node) { hbc->add_child(goto_menu); hbc->add_child(help_menu); hbc->add_theme_style_override("panel", p_node->get_gui_base()->get_theme_stylebox("ScriptEditorPanel", "EditorStyles")); - main_container->add_child(shader_editor); + + VSplitContainer *editor_box = memnew(VSplitContainer); + main_container->add_child(editor_box); + editor_box->set_anchors_and_offsets_preset(Control::PRESET_WIDE); + editor_box->set_v_size_flags(SIZE_EXPAND_FILL); + editor_box->add_child(shader_editor); + + warnings_panel = memnew(RichTextLabel); + warnings_panel->set_custom_minimum_size(Size2(0, 100 * EDSCALE)); + warnings_panel->set_h_size_flags(SIZE_EXPAND_FILL); + warnings_panel->set_meta_underline(true); + warnings_panel->set_selection_enabled(true); + warnings_panel->set_focus_mode(FOCUS_CLICK); + warnings_panel->hide(); + warnings_panel->connect("meta_clicked", callable_mp(this, &ShaderEditor::_warning_clicked)); + editor_box->add_child(warnings_panel); + shader_editor->set_warnings_panel(warnings_panel); goto_line_dialog = memnew(GotoLineDialog); add_child(goto_line_dialog); diff --git a/editor/plugins/shader_editor_plugin.h b/editor/plugins/shader_editor_plugin.h index 731c0a5b7e..d7da73f2ae 100644 --- a/editor/plugins/shader_editor_plugin.h +++ b/editor/plugins/shader_editor_plugin.h @@ -35,6 +35,7 @@ #include "editor/editor_plugin.h" #include "scene/gui/menu_button.h" #include "scene/gui/panel_container.h" +#include "scene/gui/rich_text_label.h" #include "scene/gui/tab_container.h" #include "scene/gui/text_edit.h" #include "scene/main/timer.h" @@ -44,10 +45,19 @@ class ShaderTextEditor : public CodeTextEditor { GDCLASS(ShaderTextEditor, CodeTextEditor); + Color marked_line_color = Color(1, 1, 1); + + struct WarningsComparator { + _ALWAYS_INLINE_ bool operator()(const ShaderWarning &p_a, const ShaderWarning &p_b) const { return (p_a.get_line() < p_b.get_line()); } + }; + Ref<CodeHighlighter> syntax_highlighter; + RichTextLabel *warnings_panel = nullptr; Ref<Shader> shader; + List<ShaderWarning> warnings; void _check_shader_mode(); + void _update_warning_panel(); protected: static void _bind_methods(); @@ -59,6 +69,7 @@ public: virtual void _validate_script() override; void reload_text(); + void set_warnings_panel(RichTextLabel *p_warnings_panel); Ref<Shader> get_edited_shader() const; void set_edited_shader(const Ref<Shader> &p_shader); @@ -100,6 +111,7 @@ class ShaderEditor : public PanelContainer { PopupMenu *bookmarks_menu; MenuButton *help_menu; PopupMenu *context_menu; + RichTextLabel *warnings_panel = nullptr; uint64_t idle; GotoLineDialog *goto_line_dialog; @@ -109,13 +121,16 @@ class ShaderEditor : public PanelContainer { ShaderTextEditor *shader_editor; void _menu_option(int p_option); - void _params_changed(); mutable Ref<Shader> shader; void _editor_settings_changed(); + void _project_settings_changed(); void _check_for_external_edit(); void _reload_shader_from_disk(); + void _show_warnings_panel(bool p_show); + void _warning_clicked(Variant p_line); + void _update_warnings(bool p_validate); protected: void _notification(int p_what); diff --git a/editor/plugins/sprite_frames_editor_plugin.cpp b/editor/plugins/sprite_frames_editor_plugin.cpp index 551d1c027a..59bc8f9e55 100644 --- a/editor/plugins/sprite_frames_editor_plugin.cpp +++ b/editor/plugins/sprite_frames_editor_plugin.cpp @@ -220,7 +220,7 @@ void SpriteFramesEditor::_sheet_zoom_out() { void SpriteFramesEditor::_sheet_zoom_reset() { // Default the zoom to match the editor scale, but don't dezoom on editor scales below 100% to prevent pixel art from looking bad. - sheet_zoom = MAX(1.0, EDSCALE); + sheet_zoom = MAX(1.0f, EDSCALE); Size2 texture_size = split_sheet_preview->get_texture()->get_size(); split_sheet_preview->set_custom_minimum_size(texture_size * sheet_zoom); } @@ -252,10 +252,10 @@ void SpriteFramesEditor::_prepare_sprite_sheet(const String &p_file) { EditorNode::get_singleton()->show_warning(TTR("Unable to load images")); ERR_FAIL_COND(!texture.is_valid()); } - bool new_texture = texture != split_sheet_preview->get_texture(); frames_selected.clear(); last_frame_selected = -1; + bool new_texture = texture != split_sheet_preview->get_texture(); split_sheet_preview->set_texture(texture); if (new_texture) { //different texture, reset to 4x4 @@ -280,17 +280,17 @@ void SpriteFramesEditor::_notification(int p_what) { move_down->set_icon(get_theme_icon("MoveRight", "EditorIcons")); _delete->set_icon(get_theme_icon("Remove", "EditorIcons")); zoom_out->set_icon(get_theme_icon("ZoomLess", "EditorIcons")); - zoom_1->set_icon(get_theme_icon("ZoomReset", "EditorIcons")); + zoom_reset->set_icon(get_theme_icon("ZoomReset", "EditorIcons")); zoom_in->set_icon(get_theme_icon("ZoomMore", "EditorIcons")); new_anim->set_icon(get_theme_icon("New", "EditorIcons")); remove_anim->set_icon(get_theme_icon("Remove", "EditorIcons")); split_sheet_zoom_out->set_icon(get_theme_icon("ZoomLess", "EditorIcons")); - split_sheet_zoom_1->set_icon(get_theme_icon("ZoomReset", "EditorIcons")); + split_sheet_zoom_reset->set_icon(get_theme_icon("ZoomReset", "EditorIcons")); split_sheet_zoom_in->set_icon(get_theme_icon("ZoomMore", "EditorIcons")); [[fallthrough]]; } case NOTIFICATION_THEME_CHANGED: { - splite_sheet_scroll->add_theme_style_override("bg", get_theme_stylebox("bg", "Tree")); + split_sheet_scroll->add_theme_style_override("bg", get_theme_stylebox("bg", "Tree")); } break; case NOTIFICATION_READY: { add_theme_constant_override("autohide", 1); // Fixes the dragger always showing up. @@ -733,7 +733,7 @@ void SpriteFramesEditor::_zoom_out() { } void SpriteFramesEditor::_zoom_reset() { - thumbnail_zoom = MAX(1.0, EDSCALE); + thumbnail_zoom = MAX(1.0f, EDSCALE); tree->set_fixed_column_width(thumbnail_default_size * 3 / 2); tree->set_fixed_icon_size(Size2(thumbnail_default_size, thumbnail_default_size)); } @@ -1086,11 +1086,13 @@ SpriteFramesEditor::SpriteFramesEditor() { zoom_out->set_flat(true); zoom_out->set_tooltip(TTR("Zoom Out")); hbc->add_child(zoom_out); - zoom_1 = memnew(Button); - zoom_1->connect("pressed", callable_mp(this, &SpriteFramesEditor::_zoom_reset)); - zoom_1->set_flat(true); - zoom_1->set_tooltip(TTR("Zoom Reset")); - hbc->add_child(zoom_1); + + zoom_reset = memnew(Button); + zoom_reset->connect("pressed", callable_mp(this, &SpriteFramesEditor::_zoom_reset)); + zoom_reset->set_flat(true); + zoom_reset->set_tooltip(TTR("Zoom Reset")); + hbc->add_child(zoom_reset); + zoom_in = memnew(Button); zoom_in->connect("pressed", callable_mp(this, &SpriteFramesEditor::_zoom_in)); zoom_in->set_flat(true); @@ -1183,16 +1185,16 @@ SpriteFramesEditor::SpriteFramesEditor() { split_sheet_preview->connect("draw", callable_mp(this, &SpriteFramesEditor::_sheet_preview_draw)); split_sheet_preview->connect("gui_input", callable_mp(this, &SpriteFramesEditor::_sheet_preview_input)); - splite_sheet_scroll = memnew(ScrollContainer); - splite_sheet_scroll->set_enable_h_scroll(true); - splite_sheet_scroll->set_enable_v_scroll(true); - splite_sheet_scroll->connect("gui_input", callable_mp(this, &SpriteFramesEditor::_sheet_scroll_input)); - split_sheet_panel->add_child(splite_sheet_scroll); + split_sheet_scroll = memnew(ScrollContainer); + split_sheet_scroll->set_enable_h_scroll(true); + split_sheet_scroll->set_enable_v_scroll(true); + split_sheet_scroll->connect("gui_input", callable_mp(this, &SpriteFramesEditor::_sheet_scroll_input)); + split_sheet_panel->add_child(split_sheet_scroll); CenterContainer *cc = memnew(CenterContainer); cc->add_child(split_sheet_preview); cc->set_h_size_flags(SIZE_EXPAND_FILL); cc->set_v_size_flags(SIZE_EXPAND_FILL); - splite_sheet_scroll->add_child(cc); + split_sheet_scroll->add_child(cc); MarginContainer *split_sheet_zoom_margin = memnew(MarginContainer); split_sheet_panel->add_child(split_sheet_zoom_margin); @@ -1209,12 +1211,14 @@ SpriteFramesEditor::SpriteFramesEditor() { split_sheet_zoom_out->set_tooltip(TTR("Zoom Out")); split_sheet_zoom_out->connect("pressed", callable_mp(this, &SpriteFramesEditor::_sheet_zoom_out)); split_sheet_zoom_hb->add_child(split_sheet_zoom_out); - split_sheet_zoom_1 = memnew(Button); - split_sheet_zoom_1->set_flat(true); - split_sheet_zoom_1->set_focus_mode(FOCUS_NONE); - split_sheet_zoom_1->set_tooltip(TTR("Zoom Reset")); - split_sheet_zoom_1->connect("pressed", callable_mp(this, &SpriteFramesEditor::_sheet_zoom_reset)); - split_sheet_zoom_hb->add_child(split_sheet_zoom_1); + + split_sheet_zoom_reset = memnew(Button); + split_sheet_zoom_reset->set_flat(true); + split_sheet_zoom_reset->set_focus_mode(FOCUS_NONE); + split_sheet_zoom_reset->set_tooltip(TTR("Zoom Reset")); + split_sheet_zoom_reset->connect("pressed", callable_mp(this, &SpriteFramesEditor::_sheet_zoom_reset)); + split_sheet_zoom_hb->add_child(split_sheet_zoom_reset); + split_sheet_zoom_in = memnew(Button); split_sheet_zoom_in->set_flat(true); split_sheet_zoom_in->set_focus_mode(FOCUS_NONE); @@ -1230,14 +1234,14 @@ SpriteFramesEditor::SpriteFramesEditor() { // Config scale. scale_ratio = 1.2f; - thumbnail_default_size = 96 * MAX(1.0, EDSCALE); - thumbnail_zoom = MAX(1.0, EDSCALE); - max_thumbnail_zoom = 8.0f * MAX(1.0, EDSCALE); - min_thumbnail_zoom = 0.1f * MAX(1.0, EDSCALE); + thumbnail_default_size = 96 * MAX(1, EDSCALE); + thumbnail_zoom = MAX(1.0f, EDSCALE); + max_thumbnail_zoom = 8.0f * MAX(1.0f, EDSCALE); + min_thumbnail_zoom = 0.1f * MAX(1.0f, EDSCALE); // Default the zoom to match the editor scale, but don't dezoom on editor scales below 100% to prevent pixel art from looking bad. - sheet_zoom = MAX(1.0, EDSCALE); - max_sheet_zoom = 16.0f * MAX(1.0, EDSCALE); - min_sheet_zoom = 0.01f * MAX(1.0, EDSCALE); + sheet_zoom = MAX(1.0f, EDSCALE); + max_sheet_zoom = 16.0f * MAX(1.0f, EDSCALE); + min_sheet_zoom = 0.01f * MAX(1.0f, EDSCALE); _zoom_reset(); } diff --git a/editor/plugins/sprite_frames_editor_plugin.h b/editor/plugins/sprite_frames_editor_plugin.h index bbc26ca726..77cdbb4af6 100644 --- a/editor/plugins/sprite_frames_editor_plugin.h +++ b/editor/plugins/sprite_frames_editor_plugin.h @@ -54,13 +54,12 @@ class SpriteFramesEditor : public HSplitContainer { Button *move_up; Button *move_down; Button *zoom_out; - Button *zoom_1; + Button *zoom_reset; Button *zoom_in; ItemList *tree; bool loading_scene; int sel; - HSplitContainer *split; Button *new_anim; Button *remove_anim; @@ -79,12 +78,12 @@ class SpriteFramesEditor : public HSplitContainer { ConfirmationDialog *delete_dialog; ConfirmationDialog *split_sheet_dialog; - ScrollContainer *splite_sheet_scroll; + ScrollContainer *split_sheet_scroll; TextureRect *split_sheet_preview; SpinBox *split_sheet_h; SpinBox *split_sheet_v; Button *split_sheet_zoom_out; - Button *split_sheet_zoom_1; + Button *split_sheet_zoom_reset; Button *split_sheet_zoom_in; EditorFileDialog *file_split_sheet; Set<int> frames_selected; diff --git a/editor/plugins/text_editor.cpp b/editor/plugins/text_editor.cpp index e6fb2710ae..1edcbd2cc9 100644 --- a/editor/plugins/text_editor.cpp +++ b/editor/plugins/text_editor.cpp @@ -59,58 +59,7 @@ void TextEditor::_change_syntax_highlighter(int p_idx) { } void TextEditor::_load_theme_settings() { - CodeEdit *text_edit = code_editor->get_text_editor(); - text_edit->get_syntax_highlighter()->update_cache(); - - Color background_color = EDITOR_GET("text_editor/highlighting/background_color"); - Color completion_background_color = EDITOR_GET("text_editor/highlighting/completion_background_color"); - Color completion_selected_color = EDITOR_GET("text_editor/highlighting/completion_selected_color"); - Color completion_existing_color = EDITOR_GET("text_editor/highlighting/completion_existing_color"); - Color completion_scroll_color = EDITOR_GET("text_editor/highlighting/completion_scroll_color"); - Color completion_font_color = EDITOR_GET("text_editor/highlighting/completion_font_color"); - Color text_color = EDITOR_GET("text_editor/highlighting/text_color"); - Color line_number_color = EDITOR_GET("text_editor/highlighting/line_number_color"); - Color caret_color = EDITOR_GET("text_editor/highlighting/caret_color"); - Color caret_background_color = EDITOR_GET("text_editor/highlighting/caret_background_color"); - Color text_selected_color = EDITOR_GET("text_editor/highlighting/text_selected_color"); - Color selection_color = EDITOR_GET("text_editor/highlighting/selection_color"); - Color brace_mismatch_color = EDITOR_GET("text_editor/highlighting/brace_mismatch_color"); - Color current_line_color = EDITOR_GET("text_editor/highlighting/current_line_color"); - Color line_length_guideline_color = EDITOR_GET("text_editor/highlighting/line_length_guideline_color"); - Color word_highlighted_color = EDITOR_GET("text_editor/highlighting/word_highlighted_color"); - Color mark_color = EDITOR_GET("text_editor/highlighting/mark_color"); - Color bookmark_color = EDITOR_GET("text_editor/highlighting/bookmark_color"); - Color breakpoint_color = EDITOR_GET("text_editor/highlighting/breakpoint_color"); - Color executing_line_color = EDITOR_GET("text_editor/highlighting/executing_line_color"); - Color code_folding_color = EDITOR_GET("text_editor/highlighting/code_folding_color"); - Color search_result_color = EDITOR_GET("text_editor/highlighting/search_result_color"); - Color search_result_border_color = EDITOR_GET("text_editor/highlighting/search_result_border_color"); - - text_edit->add_theme_color_override("background_color", background_color); - text_edit->add_theme_color_override("completion_background_color", completion_background_color); - text_edit->add_theme_color_override("completion_selected_color", completion_selected_color); - text_edit->add_theme_color_override("completion_existing_color", completion_existing_color); - text_edit->add_theme_color_override("completion_scroll_color", completion_scroll_color); - text_edit->add_theme_color_override("completion_font_color", completion_font_color); - text_edit->add_theme_color_override("font_color", text_color); - text_edit->add_theme_color_override("line_number_color", line_number_color); - text_edit->add_theme_color_override("caret_color", caret_color); - text_edit->add_theme_color_override("caret_background_color", caret_background_color); - text_edit->add_theme_color_override("font_selected_color", text_selected_color); - text_edit->add_theme_color_override("selection_color", selection_color); - text_edit->add_theme_color_override("brace_mismatch_color", brace_mismatch_color); - text_edit->add_theme_color_override("current_line_color", current_line_color); - text_edit->add_theme_color_override("line_length_guideline_color", line_length_guideline_color); - text_edit->add_theme_color_override("word_highlighted_color", word_highlighted_color); - text_edit->add_theme_color_override("breakpoint_color", breakpoint_color); - text_edit->add_theme_color_override("executing_line_color", executing_line_color); - text_edit->add_theme_color_override("mark_color", mark_color); - text_edit->add_theme_color_override("bookmark_color", bookmark_color); - text_edit->add_theme_color_override("code_folding_color", code_folding_color); - text_edit->add_theme_color_override("search_result_color", search_result_color); - text_edit->add_theme_color_override("search_result_border_color", search_result_border_color); - - text_edit->add_theme_constant_override("line_spacing", EDITOR_DEF("text_editor/theme/line_spacing", 6)); + code_editor->get_text_editor()->get_syntax_highlighter()->update_cache(); } String TextEditor::get_name() { diff --git a/editor/plugins/visual_shader_editor_plugin.cpp b/editor/plugins/visual_shader_editor_plugin.cpp index c2b08d365b..72b19a9074 100644 --- a/editor/plugins/visual_shader_editor_plugin.cpp +++ b/editor/plugins/visual_shader_editor_plugin.cpp @@ -349,6 +349,8 @@ void VisualShaderGraphPlugin::add_node(VisualShader::Type p_type, int p_id) { Ref<VisualShaderNodeGroupBase> group_node = Object::cast_to<VisualShaderNodeGroupBase>(vsnode.ptr()); bool is_group = !group_node.is_null(); + bool is_comment = false; + Ref<VisualShaderNodeExpression> expression_node = Object::cast_to<VisualShaderNodeExpression>(group_node.ptr()); bool is_expression = !expression_node.is_null(); String expression = ""; @@ -392,13 +394,13 @@ void VisualShaderGraphPlugin::add_node(VisualShader::Type p_type, int p_id) { if (is_resizable) { Ref<VisualShaderNodeComment> comment_node = Object::cast_to<VisualShaderNodeComment>(vsnode.ptr()); if (comment_node.is_valid()) { + is_comment = true; node->set_comment(true); Label *comment_label = memnew(Label); node->add_child(comment_label); comment_label->set_h_size_flags(Control::SIZE_EXPAND_FILL); comment_label->set_v_size_flags(Control::SIZE_EXPAND_FILL); - comment_label->set_mouse_filter(Control::MouseFilter::MOUSE_FILTER_STOP); comment_label->set_text(comment_node->get_description()); } } @@ -773,6 +775,9 @@ void VisualShaderGraphPlugin::add_node(VisualShader::Type p_type, int p_id) { if (!uniform.is_valid()) { VisualShaderEditor::get_singleton()->graph->add_child(node); + if (is_comment) { + VisualShaderEditor::get_singleton()->graph->move_child(node, 0); // to prevents a bug where comment node overlaps its content + } VisualShaderEditor::get_singleton()->_update_created_node(node); if (is_resizable) { VisualShaderEditor::get_singleton()->call_deferred("_set_node_size", (int)p_type, p_id, size); @@ -3420,10 +3425,11 @@ void VisualShaderEditor::_update_preview() { Error err = sl.compile(code, ShaderTypes::get_singleton()->get_functions(RenderingServer::ShaderMode(visual_shader->get_mode())), ShaderTypes::get_singleton()->get_modes(RenderingServer::ShaderMode(visual_shader->get_mode())), ShaderLanguage::VaryingFunctionNames(), ShaderTypes::get_singleton()->get_types(), _get_global_variable_type); for (int i = 0; i < preview_text->get_line_count(); i++) { - preview_text->set_line_as_marked(i, false); + preview_text->set_line_background_color(i, Color(0, 0, 0, 0)); } if (err != OK) { - preview_text->set_line_as_marked(sl.get_error_line() - 1, true); + Color error_line_color = EDITOR_GET("text_editor/highlighting/mark_color"); + preview_text->set_line_background_color(sl.get_error_line() - 1, error_line_color); error_text->set_visible(true); String text = "error(" + itos(sl.get_error_line()) + "): " + sl.get_error_text(); diff --git a/modules/gdnavigation/navigation_mesh_generator.cpp b/modules/gdnavigation/navigation_mesh_generator.cpp index a7d4e79148..7d30ce0f44 100644 --- a/modules/gdnavigation/navigation_mesh_generator.cpp +++ b/modules/gdnavigation/navigation_mesh_generator.cpp @@ -32,7 +32,7 @@ #include "navigation_mesh_generator.h" -#include "core/math/quick_hull.h" +#include "core/math/convex_hull.h" #include "core/os/thread.h" #include "scene/3d/collision_shape_3d.h" #include "scene/3d/mesh_instance_3d.h" @@ -220,7 +220,7 @@ void NavigationMeshGenerator::_parse_geometry(Transform p_accumulated_transform, Vector<Vector3> varr = Variant(convex_polygon->get_points()); Geometry3D::MeshData md; - Error err = QuickHull::build(varr, md); + Error err = ConvexHullComputer::convex_hull(varr, md); if (err == OK) { PackedVector3Array faces; diff --git a/modules/meshoptimizer/register_types.cpp b/modules/meshoptimizer/register_types.cpp index a03310f518..77cc82a4e2 100644 --- a/modules/meshoptimizer/register_types.cpp +++ b/modules/meshoptimizer/register_types.cpp @@ -35,6 +35,7 @@ void register_meshoptimizer_types() { SurfaceTool::optimize_vertex_cache_func = meshopt_optimizeVertexCache; SurfaceTool::simplify_func = meshopt_simplify; + SurfaceTool::simplify_with_attrib_func = meshopt_simplifyWithAttributes; SurfaceTool::simplify_scale_func = meshopt_simplifyScale; SurfaceTool::simplify_sloppy_func = meshopt_simplifySloppy; } diff --git a/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2.cs b/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2.cs index 6279ea1ace..ebfe70aa82 100644 --- a/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2.cs +++ b/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2.cs @@ -519,7 +519,7 @@ namespace Godot /// compared to the original, with the same length. /// </summary> /// <returns>The perpendicular vector.</returns> - public Vector2 Perpendicular() + public Vector2 Orthogonal() { return new Vector2(y, -x); } diff --git a/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2i.cs b/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2i.cs index 8dd9ab2f0d..f605ba8fd0 100644 --- a/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2i.cs +++ b/modules/mono/glue/GodotSharp/GodotSharp/Core/Vector2i.cs @@ -248,13 +248,13 @@ namespace Godot } /// <summary> - /// Returns a vector rotated 90 degrees counter-clockwise + /// Returns a perpendicular vector rotated 90 degrees counter-clockwise /// compared to the original, with the same length. /// </summary> /// <returns>The perpendicular vector.</returns> - public Vector2 Perpendicular() + public Vector2i Orthogonal() { - return new Vector2(y, -x); + return new Vector2i(y, -x); } // Constants diff --git a/platform/linuxbsd/os_linuxbsd.cpp b/platform/linuxbsd/os_linuxbsd.cpp index e7d3c9552e..23e448fbd7 100644 --- a/platform/linuxbsd/os_linuxbsd.cpp +++ b/platform/linuxbsd/os_linuxbsd.cpp @@ -116,6 +116,8 @@ String OS_LinuxBSD::get_name() const { return "FreeBSD"; #elif defined(__NetBSD__) return "NetBSD"; +#elif defined(__OpenBSD__) + return "OpenBSD"; #else return "BSD"; #endif diff --git a/platform/osx/display_server_osx.mm b/platform/osx/display_server_osx.mm index a9e9aa889a..4c761e77b5 100644 --- a/platform/osx/display_server_osx.mm +++ b/platform/osx/display_server_osx.mm @@ -368,6 +368,10 @@ static NSCursor *_cursorFromSelector(SEL selector, SEL fallback = nil) { if (wd.resize_disabled) { [wd.window_object setStyleMask:[wd.window_object styleMask] & ~NSWindowStyleMaskResizable]; } + + if (wd.on_top) { + [wd.window_object setLevel:NSFloatingWindowLevel]; + } } - (void)windowDidChangeBackingProperties:(NSNotification *)notification { @@ -2437,7 +2441,7 @@ void DisplayServerOSX::_update_window(WindowData p_wd) { [p_wd.window_object setHidesOnDeactivate:YES]; } else { // Reset these when our window is not a borderless window that covers up the screen - if (p_wd.on_top) { + if (p_wd.on_top && !p_wd.fullscreen) { [p_wd.window_object setLevel:NSFloatingWindowLevel]; } else { [p_wd.window_object setLevel:NSNormalWindowLevel]; @@ -2786,6 +2790,7 @@ void DisplayServerOSX::window_set_mode(WindowMode p_mode, WindowID p_window) { [wd.window_object deminiaturize:nil]; } break; case WINDOW_MODE_FULLSCREEN: { + [wd.window_object setLevel:NSNormalWindowLevel]; if (wd.layered_window) { _set_window_per_pixel_transparency_enabled(true, p_window); } @@ -2903,6 +2908,9 @@ void DisplayServerOSX::window_set_flag(WindowFlags p_flag, bool p_enabled, Windo } break; case WINDOW_FLAG_ALWAYS_ON_TOP: { wd.on_top = p_enabled; + if (wd.fullscreen) { + return; + } if (p_enabled) { [wd.window_object setLevel:NSFloatingWindowLevel]; } else { @@ -2940,7 +2948,11 @@ bool DisplayServerOSX::window_get_flag(WindowFlags p_flag, WindowID p_window) co return [wd.window_object styleMask] == NSWindowStyleMaskBorderless; } break; case WINDOW_FLAG_ALWAYS_ON_TOP: { - return [wd.window_object level] == NSFloatingWindowLevel; + if (wd.fullscreen) { + return wd.on_top; + } else { + return [wd.window_object level] == NSFloatingWindowLevel; + } } break; case WINDOW_FLAG_TRANSPARENT: { return wd.layered_window; diff --git a/platform/uwp/app.cpp b/platform/uwp/app.cpp index b7e4361831..9d6ff10483 100644 --- a/platform/uwp/app.cpp +++ b/platform/uwp/app.cpp @@ -383,7 +383,7 @@ void App::key_event(Windows::UI::Core::CoreWindow ^ sender, bool p_pressed, Wind ke.type = OS_UWP::KeyEvent::MessageType::KEY_EVENT_MESSAGE; ke.unicode = 0; ke.keycode = KeyMappingWindows::get_keysym((unsigned int)key_args->VirtualKey); - ke.physical_keycode = KeyMappingWindows::get_scansym((unsigned int)key_args->KeyStatus.ScanCode); + ke.physical_keycode = KeyMappingWindows::get_scansym((unsigned int)key_args->KeyStatus.ScanCode, key_args->KeyStatus.IsExtendedKey); ke.echo = (!p_pressed && !key_args->KeyStatus.IsKeyReleased) || (p_pressed && key_args->KeyStatus.WasKeyDown); } else { diff --git a/scene/2d/sprite_2d.cpp b/scene/2d/sprite_2d.cpp index 7c93edbff9..20169b1075 100644 --- a/scene/2d/sprite_2d.cpp +++ b/scene/2d/sprite_2d.cpp @@ -254,15 +254,15 @@ int Sprite2D::get_frame() const { return frame; } -void Sprite2D::set_frame_coords(const Vector2 &p_coord) { - ERR_FAIL_INDEX(int(p_coord.x), hframes); - ERR_FAIL_INDEX(int(p_coord.y), vframes); +void Sprite2D::set_frame_coords(const Vector2i &p_coord) { + ERR_FAIL_INDEX(p_coord.x, hframes); + ERR_FAIL_INDEX(p_coord.y, vframes); - set_frame(int(p_coord.y) * hframes + int(p_coord.x)); + set_frame(p_coord.y * hframes + p_coord.x); } -Vector2 Sprite2D::get_frame_coords() const { - return Vector2(frame % hframes, frame / hframes); +Vector2i Sprite2D::get_frame_coords() const { + return Vector2i(frame % hframes, frame / hframes); } void Sprite2D::set_vframes(int p_amount) { @@ -452,7 +452,7 @@ void Sprite2D::_bind_methods() { ADD_PROPERTY(PropertyInfo(Variant::INT, "hframes", PROPERTY_HINT_RANGE, "1,16384,1"), "set_hframes", "get_hframes"); ADD_PROPERTY(PropertyInfo(Variant::INT, "vframes", PROPERTY_HINT_RANGE, "1,16384,1"), "set_vframes", "get_vframes"); ADD_PROPERTY(PropertyInfo(Variant::INT, "frame"), "set_frame", "get_frame"); - ADD_PROPERTY(PropertyInfo(Variant::VECTOR2, "frame_coords", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_EDITOR), "set_frame_coords", "get_frame_coords"); + ADD_PROPERTY(PropertyInfo(Variant::VECTOR2I, "frame_coords", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_EDITOR), "set_frame_coords", "get_frame_coords"); ADD_GROUP("Region", "region_"); ADD_PROPERTY(PropertyInfo(Variant::BOOL, "region_enabled"), "set_region_enabled", "is_region_enabled"); diff --git a/scene/2d/sprite_2d.h b/scene/2d/sprite_2d.h index 9db74cfe26..49df78c59d 100644 --- a/scene/2d/sprite_2d.h +++ b/scene/2d/sprite_2d.h @@ -109,8 +109,8 @@ public: void set_frame(int p_frame); int get_frame() const; - void set_frame_coords(const Vector2 &p_coord); - Vector2 get_frame_coords() const; + void set_frame_coords(const Vector2i &p_coord); + Vector2i get_frame_coords() const; void set_vframes(int p_amount); int get_vframes() const; diff --git a/scene/3d/collision_object_3d.cpp b/scene/3d/collision_object_3d.cpp index 914b3ad816..cba769a8f8 100644 --- a/scene/3d/collision_object_3d.cpp +++ b/scene/3d/collision_object_3d.cpp @@ -215,6 +215,11 @@ void CollisionObject3D::_shape_changed(const Ref<Shape3D> &p_shape) { } void CollisionObject3D::_update_debug_shapes() { + if (!is_inside_tree()) { + debug_shapes_to_update.clear(); + return; + } + for (Set<uint32_t>::Element *shapedata_idx = debug_shapes_to_update.front(); shapedata_idx; shapedata_idx = shapedata_idx->next()) { if (shapes.has(shapedata_idx->get())) { ShapeData &shapedata = shapes[shapedata_idx->get()]; diff --git a/scene/3d/sprite_3d.cpp b/scene/3d/sprite_3d.cpp index 33b8b488c6..be474e82e0 100644 --- a/scene/3d/sprite_3d.cpp +++ b/scene/3d/sprite_3d.cpp @@ -551,15 +551,15 @@ int Sprite3D::get_frame() const { return frame; } -void Sprite3D::set_frame_coords(const Vector2 &p_coord) { - ERR_FAIL_INDEX(int(p_coord.x), hframes); - ERR_FAIL_INDEX(int(p_coord.y), vframes); +void Sprite3D::set_frame_coords(const Vector2i &p_coord) { + ERR_FAIL_INDEX(p_coord.x, hframes); + ERR_FAIL_INDEX(p_coord.y, vframes); - set_frame(int(p_coord.y) * hframes + int(p_coord.x)); + set_frame(p_coord.y * hframes + p_coord.x); } -Vector2 Sprite3D::get_frame_coords() const { - return Vector2(frame % hframes, frame / hframes); +Vector2i Sprite3D::get_frame_coords() const { + return Vector2i(frame % hframes, frame / hframes); } void Sprite3D::set_vframes(int p_amount) { @@ -657,7 +657,7 @@ void Sprite3D::_bind_methods() { ADD_PROPERTY(PropertyInfo(Variant::INT, "hframes", PROPERTY_HINT_RANGE, "1,16384,1"), "set_hframes", "get_hframes"); ADD_PROPERTY(PropertyInfo(Variant::INT, "vframes", PROPERTY_HINT_RANGE, "1,16384,1"), "set_vframes", "get_vframes"); ADD_PROPERTY(PropertyInfo(Variant::INT, "frame"), "set_frame", "get_frame"); - ADD_PROPERTY(PropertyInfo(Variant::VECTOR2, "frame_coords", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_EDITOR), "set_frame_coords", "get_frame_coords"); + ADD_PROPERTY(PropertyInfo(Variant::VECTOR2I, "frame_coords", PROPERTY_HINT_NONE, "", PROPERTY_USAGE_EDITOR), "set_frame_coords", "get_frame_coords"); ADD_GROUP("Region", "region_"); ADD_PROPERTY(PropertyInfo(Variant::BOOL, "region_enabled"), "set_region_enabled", "is_region_enabled"); ADD_PROPERTY(PropertyInfo(Variant::RECT2, "region_rect"), "set_region_rect", "get_region_rect"); diff --git a/scene/3d/sprite_3d.h b/scene/3d/sprite_3d.h index 5e47e66bcb..e3dd117804 100644 --- a/scene/3d/sprite_3d.h +++ b/scene/3d/sprite_3d.h @@ -176,8 +176,8 @@ public: void set_frame(int p_frame); int get_frame() const; - void set_frame_coords(const Vector2 &p_coord); - Vector2 get_frame_coords() const; + void set_frame_coords(const Vector2i &p_coord); + Vector2i get_frame_coords() const; void set_vframes(int p_amount); int get_vframes() const; diff --git a/scene/gui/text_edit.cpp b/scene/gui/text_edit.cpp index e305c6210d..d19d95f6f4 100644 --- a/scene/gui/text_edit.cpp +++ b/scene/gui/text_edit.cpp @@ -253,7 +253,6 @@ void TextEdit::Text::set(int p_line, const String &p_text, const Vector<Vector2i void TextEdit::Text::insert(int p_at, const String &p_text, const Vector<Vector2i> &p_bidi_override) { Line line; line.gutters.resize(gutter_count); - line.marked = false; line.hidden = false; line.data = p_text; line.bidi_override = p_bidi_override; @@ -867,6 +866,8 @@ void TextEdit::_notification(int p_what) { Dictionary color_map = _get_line_syntax_highlighting(minimap_line); + Color line_background_color = text.get_line_background_color(minimap_line); + line_background_color.a *= 0.6; Color current_color = cache.font_color; if (readonly) { current_color = cache.font_readonly_color; @@ -901,6 +902,12 @@ void TextEdit::_notification(int p_what) { } else { RenderingServer::get_singleton()->canvas_item_add_rect(ci, Rect2((xmargin_end + 2), i * 3, cache.minimap_width, 2), cache.current_line_color); } + } else if (line_background_color != Color(0, 0, 0, 0)) { + if (rtl) { + RenderingServer::get_singleton()->canvas_item_add_rect(ci, Rect2(size.width - (xmargin_end + 2) - cache.minimap_width, i * 3, cache.minimap_width, 2), line_background_color); + } else { + RenderingServer::get_singleton()->canvas_item_add_rect(ci, Rect2((xmargin_end + 2), i * 3, cache.minimap_width, 2), line_background_color); + } } Color previous_color; @@ -1048,11 +1055,11 @@ void TextEdit::_notification(int p_what) { break; } - if (text.is_marked(line)) { + if (text.get_line_background_color(line) != Color(0, 0, 0, 0)) { if (rtl) { - RenderingServer::get_singleton()->canvas_item_add_rect(ci, Rect2(size.width - ofs_x - xmargin_end, ofs_y, xmargin_end - xmargin_beg, row_height), cache.mark_color); + RenderingServer::get_singleton()->canvas_item_add_rect(ci, Rect2(size.width - ofs_x - xmargin_end, ofs_y, xmargin_end - xmargin_beg, row_height), text.get_line_background_color(line)); } else { - RenderingServer::get_singleton()->canvas_item_add_rect(ci, Rect2(xmargin_beg + ofs_x, ofs_y, xmargin_end - xmargin_beg, row_height), cache.mark_color); + RenderingServer::get_singleton()->canvas_item_add_rect(ci, Rect2(xmargin_beg + ofs_x, ofs_y, xmargin_end - xmargin_beg, row_height), text.get_line_background_color(line)); } } @@ -3374,13 +3381,18 @@ void TextEdit::_gui_input(const Ref<InputEvent> &p_gui_input) { return; } - // SELECT ALL, CUT, COPY, PASTE. + // SELECT ALL, SELECT WORD UNDER CARET, CUT, COPY, PASTE. if (k->is_action("ui_text_select_all", true)) { select_all(); accept_event(); return; } + if (k->is_action("ui_text_select_word_under_caret", true)) { + select_word_under_caret(); + accept_event(); + return; + } if (k->is_action("ui_cut", true)) { cut(); accept_event(); @@ -4789,7 +4801,6 @@ void TextEdit::_update_caches() { cache.font_selected_color = get_theme_color("font_selected_color"); cache.font_readonly_color = get_theme_color("font_readonly_color"); cache.selection_color = get_theme_color("selection_color"); - cache.mark_color = get_theme_color("mark_color"); cache.current_line_color = get_theme_color("current_line_color"); cache.line_length_guideline_color = get_theme_color("line_length_guideline_color"); cache.code_folding_color = get_theme_color("code_folding_color"); @@ -5019,6 +5030,18 @@ bool TextEdit::is_line_gutter_clickable(int p_line, int p_gutter) const { return text.is_line_gutter_clickable(p_line, p_gutter); } +// Line style +void TextEdit::set_line_background_color(int p_line, const Color &p_color) { + ERR_FAIL_INDEX(p_line, text.size()); + text.set_line_background_color(p_line, p_color); + update(); +} + +Color TextEdit::get_line_background_color(int p_line) { + ERR_FAIL_INDEX_V(p_line, text.size(), Color()); + return text.get_line_background_color(p_line); +} + void TextEdit::add_keyword(const String &p_keyword) { keywords.insert(p_keyword); } @@ -5131,6 +5154,39 @@ void TextEdit::select_all() { update(); } +void TextEdit::select_word_under_caret() { + if (!selecting_enabled) { + return; + } + + if (text.size() == 1 && text[0].length() == 0) { + return; + } + + if (selection.active) { + // Allow toggling selection by pressing the shortcut a second time. + // This is also usable as a general-purpose "deselect" shortcut after + // selecting anything. + deselect(); + return; + } + + int begin = 0; + int end = 0; + const Vector<Vector2i> words = TS->shaped_text_get_word_breaks(text.get_line_data(cursor.line)->get_rid()); + for (int i = 0; i < words.size(); i++) { + if (words[i].x <= cursor.column && words[i].y >= cursor.column) { + begin = words[i].x; + end = words[i].y; + break; + } + } + + select(cursor.line, begin, cursor.line, end); + // Move the cursor to the end of the word for easier editing. + cursor_set_column(end, false); +} + void TextEdit::deselect() { selection.active = false; update(); @@ -5437,12 +5493,6 @@ void TextEdit::_text_changed_emit() { text_changed_dirty = false; } -void TextEdit::set_line_as_marked(int p_line, bool p_marked) { - ERR_FAIL_INDEX(p_line, text.size()); - text.set_marked(p_line, p_marked); - update(); -} - void TextEdit::set_line_as_hidden(int p_line, bool p_hidden) { ERR_FAIL_INDEX(p_line, text.size()); if (is_hiding_enabled() || !p_hidden) { @@ -6980,6 +7030,10 @@ void TextEdit::_bind_methods() { ClassDB::bind_method(D_METHOD("set_line_gutter_clickable", "line", "gutter", "clickable"), &TextEdit::set_line_gutter_clickable); ClassDB::bind_method(D_METHOD("is_line_gutter_clickable", "line", "gutter"), &TextEdit::is_line_gutter_clickable); + // Line style + ClassDB::bind_method(D_METHOD("set_line_background_color", "line", "color"), &TextEdit::set_line_background_color); + ClassDB::bind_method(D_METHOD("get_line_background_color", "line"), &TextEdit::get_line_background_color); + ClassDB::bind_method(D_METHOD("set_highlight_current_line", "enabled"), &TextEdit::set_highlight_current_line); ClassDB::bind_method(D_METHOD("is_highlight_current_line_enabled"), &TextEdit::is_highlight_current_line_enabled); diff --git a/scene/gui/text_edit.h b/scene/gui/text_edit.h index b0c7314c65..6ca50f3e2d 100644 --- a/scene/gui/text_edit.h +++ b/scene/gui/text_edit.h @@ -92,7 +92,7 @@ private: Vector<Vector2i> bidi_override; Ref<TextParagraph> data_buf; - bool marked = false; + Color background_color = Color(0, 0, 0, 0); bool hidden = false; Line() { @@ -129,12 +129,11 @@ private: void set_width(float p_width); int get_line_wrap_amount(int p_line) const; + Vector<Vector2i> get_line_wrap_ranges(int p_line) const; const Ref<TextParagraph> get_line_data(int p_line) const; void set(int p_line, const String &p_text, const Vector<Vector2i> &p_bidi_override); - void set_marked(int p_line, bool p_marked) { text.write[p_line].marked = p_marked; } - bool is_marked(int p_line) const { return text[p_line].marked; } void set_hidden(int p_line, bool p_hidden) { text.write[p_line].hidden = p_hidden; } bool is_hidden(int p_line) const { return text[p_line].hidden; } void insert(int p_at, const String &p_text, const Vector<Vector2i> &p_bidi_override); @@ -167,6 +166,10 @@ private: void set_line_gutter_clickable(int p_line, int p_gutter, bool p_clickable) { text.write[p_line].gutters.write[p_gutter].clickable = p_clickable; } bool is_line_gutter_clickable(int p_line, int p_gutter) const { return text[p_line].gutters[p_gutter].clickable; } + + /* Line style. */ + void set_line_background_color(int p_line, const Color &p_color) { text.write[p_line].background_color = p_color; } + const Color get_line_background_color(int p_line) const { return text[p_line].background_color; } }; struct Cursor { @@ -484,7 +487,6 @@ protected: Color font_selected_color; Color font_readonly_color; Color selection_color; - Color mark_color; Color code_folding_color; Color current_line_color; Color line_length_guideline_color; @@ -561,6 +563,10 @@ public: void set_line_gutter_clickable(int p_line, int p_gutter, bool p_clickable); bool is_line_gutter_clickable(int p_line, int p_gutter) const; + // Line style + void set_line_background_color(int p_line, const Color &p_color); + Color get_line_background_color(int p_line); + enum MenuItems { MENU_CUT, MENU_COPY, @@ -637,7 +643,6 @@ public: void insert_text_at_cursor(const String &p_text); void insert_at(const String &p_text, int at); int get_line_count() const; - void set_line_as_marked(int p_line, bool p_marked); void set_line_as_hidden(int p_line, bool p_hidden); bool is_line_hidden(int p_line) const; @@ -726,6 +731,7 @@ public: void copy(); void paste(); void select_all(); + void select_word_under_caret(); void select(int p_from_line, int p_from_column, int p_to_line, int p_to_column); void deselect(); void swap_lines(int line1, int line2); diff --git a/scene/resources/convex_polygon_shape_3d.cpp b/scene/resources/convex_polygon_shape_3d.cpp index 9e030bc077..6b895da606 100644 --- a/scene/resources/convex_polygon_shape_3d.cpp +++ b/scene/resources/convex_polygon_shape_3d.cpp @@ -29,7 +29,7 @@ /*************************************************************************/ #include "convex_polygon_shape_3d.h" -#include "core/math/quick_hull.h" +#include "core/math/convex_hull.h" #include "servers/physics_server_3d.h" Vector<Vector3> ConvexPolygonShape3D::get_debug_mesh_lines() const { @@ -38,7 +38,7 @@ Vector<Vector3> ConvexPolygonShape3D::get_debug_mesh_lines() const { if (points.size() > 3) { Vector<Vector3> varr = Variant(points); Geometry3D::MeshData md; - Error err = QuickHull::build(varr, md); + Error err = ConvexHullComputer::convex_hull(varr, md); if (err == OK) { Vector<Vector3> lines; lines.resize(md.edges.size() * 2); diff --git a/scene/resources/default_theme/default_theme.cpp b/scene/resources/default_theme/default_theme.cpp index b671ee4644..6e67daf15f 100644 --- a/scene/resources/default_theme/default_theme.cpp +++ b/scene/resources/default_theme/default_theme.cpp @@ -451,7 +451,6 @@ void fill_default_theme(Ref<Theme> &theme, const Ref<Font> &default_font, const theme->set_color("font_readonly_color", "TextEdit", Color(control_font_color.r, control_font_color.g, control_font_color.b, 0.5f)); theme->set_color("font_outline_color", "TextEdit", Color(1, 1, 1)); theme->set_color("selection_color", "TextEdit", control_selection_color); - theme->set_color("mark_color", "TextEdit", Color(1.0, 0.4, 0.4, 0.4)); theme->set_color("code_folding_color", "TextEdit", Color(0.8, 0.8, 0.8, 0.8)); theme->set_color("current_line_color", "TextEdit", Color(0.25, 0.25, 0.26, 0.8)); theme->set_color("caret_color", "TextEdit", control_font_color); @@ -494,7 +493,6 @@ void fill_default_theme(Ref<Theme> &theme, const Ref<Font> &default_font, const theme->set_color("font_readonly_color", "CodeEdit", Color(control_font_color.r, control_font_color.g, control_font_color.b, 0.5f)); theme->set_color("font_outline_color", "CodeEdit", Color(1, 1, 1)); theme->set_color("selection_color", "CodeEdit", control_selection_color); - theme->set_color("mark_color", "CodeEdit", Color(1.0, 0.4, 0.4, 0.4)); theme->set_color("bookmark_color", "CodeEdit", Color(0.5, 0.64, 1, 0.8)); theme->set_color("breakpoint_color", "CodeEdit", Color(0.9, 0.29, 0.3)); theme->set_color("executing_line_color", "CodeEdit", Color(0.98, 0.89, 0.27)); diff --git a/scene/resources/surface_tool.cpp b/scene/resources/surface_tool.cpp index ff682a40f4..f2143e683d 100644 --- a/scene/resources/surface_tool.cpp +++ b/scene/resources/surface_tool.cpp @@ -35,6 +35,7 @@ SurfaceTool::OptimizeVertexCacheFunc SurfaceTool::optimize_vertex_cache_func = nullptr; SurfaceTool::SimplifyFunc SurfaceTool::simplify_func = nullptr; +SurfaceTool::SimplifyWithAttribFunc SurfaceTool::simplify_with_attrib_func = nullptr; SurfaceTool::SimplifyScaleFunc SurfaceTool::simplify_scale_func = nullptr; SurfaceTool::SimplifySloppyFunc SurfaceTool::simplify_sloppy_func = nullptr; diff --git a/scene/resources/surface_tool.h b/scene/resources/surface_tool.h index 28addf2245..f5f3a95b14 100644 --- a/scene/resources/surface_tool.h +++ b/scene/resources/surface_tool.h @@ -78,6 +78,8 @@ public: static OptimizeVertexCacheFunc optimize_vertex_cache_func; typedef size_t (*SimplifyFunc)(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *r_error); static SimplifyFunc simplify_func; + typedef size_t (*SimplifyWithAttribFunc)(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_data, size_t vertex_count, size_t vertex_stride, size_t target_index_count, float target_error, float *result_error, const float *attributes, const float *attribute_weights, size_t attribute_count); + static SimplifyWithAttribFunc simplify_with_attrib_func; typedef float (*SimplifyScaleFunc)(const float *vertex_positions, size_t vertex_count, size_t vertex_positions_stride); static SimplifyScaleFunc simplify_scale_func; typedef size_t (*SimplifySloppyFunc)(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *out_result_error); diff --git a/servers/physics_3d/shape_3d_sw.cpp b/servers/physics_3d/shape_3d_sw.cpp index ccd37ca742..ca7248993f 100644 --- a/servers/physics_3d/shape_3d_sw.cpp +++ b/servers/physics_3d/shape_3d_sw.cpp @@ -31,8 +31,8 @@ #include "shape_3d_sw.h" #include "core/io/image.h" +#include "core/math/convex_hull.h" #include "core/math/geometry_3d.h" -#include "core/math/quick_hull.h" #include "core/templates/sort_array.h" // HeightMapShape3DSW is based on Bullet btHeightfieldTerrainShape. @@ -1089,9 +1089,9 @@ Vector3 ConvexPolygonShape3DSW::get_moment_of_inertia(real_t p_mass) const { } void ConvexPolygonShape3DSW::_setup(const Vector<Vector3> &p_vertices) { - Error err = QuickHull::build(p_vertices, mesh); + Error err = ConvexHullComputer::convex_hull(p_vertices, mesh); if (err != OK) { - ERR_PRINT("Failed to build QuickHull"); + ERR_PRINT("Failed to build convex hull"); } AABB _aabb; diff --git a/servers/rendering/shader_language.cpp b/servers/rendering/shader_language.cpp index e92940b31a..2ce7707257 100644 --- a/servers/rendering/shader_language.cpp +++ b/servers/rendering/shader_language.cpp @@ -33,6 +33,8 @@ #include "core/string/print_string.h" #include "servers/rendering_server.h" +#define HAS_WARNING(flag) (warning_flags & flag) + static bool _is_text_char(char32_t c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'; } @@ -901,6 +903,8 @@ bool ShaderLanguage::is_token_nonvoid_datatype(TokenType p_type) { void ShaderLanguage::clear() { current_function = StringName(); + last_name = StringName(); + last_type = IDENTIFIER_MAX; completion_type = COMPLETION_NONE; completion_block = nullptr; @@ -908,12 +912,20 @@ void ShaderLanguage::clear() { completion_class = SubClassTag::TAG_GLOBAL; completion_struct = StringName(); +#ifdef DEBUG_ENABLED + used_constants.clear(); + used_varyings.clear(); + used_uniforms.clear(); + used_functions.clear(); + used_structs.clear(); + warnings.clear(); +#endif // DEBUG_ENABLED + error_line = 0; tk_line = 1; char_idx = 0; error_set = false; error_str = ""; - last_const = false; while (nodes) { Node *n = nodes; nodes = nodes->next; @@ -921,6 +933,35 @@ void ShaderLanguage::clear() { } } +#ifdef DEBUG_ENABLED +void ShaderLanguage::_parse_used_identifier(const StringName &p_identifier, IdentifierType p_type) { + switch (p_type) { + case IdentifierType::IDENTIFIER_CONSTANT: + if (HAS_WARNING(ShaderWarning::UNUSED_CONSTANT_FLAG) && used_constants.has(p_identifier)) { + used_constants[p_identifier].used = true; + } + break; + case IdentifierType::IDENTIFIER_VARYING: + if (HAS_WARNING(ShaderWarning::UNUSED_VARYING_FLAG) && used_varyings.has(p_identifier)) { + used_varyings[p_identifier].used = true; + } + break; + case IdentifierType::IDENTIFIER_UNIFORM: + if (HAS_WARNING(ShaderWarning::UNUSED_UNIFORM_FLAG) && used_uniforms.has(p_identifier)) { + used_uniforms[p_identifier].used = true; + } + break; + case IdentifierType::IDENTIFIER_FUNCTION: + if (HAS_WARNING(ShaderWarning::UNUSED_FUNCTION_FLAG) && used_functions.has(p_identifier)) { + used_functions[p_identifier].used = true; + } + break; + default: + break; + } +} +#endif // DEBUG_ENABLED + bool ShaderLanguage::_find_identifier(const BlockNode *p_block, bool p_allow_reassign, const FunctionInfo &p_function_info, const StringName &p_identifier, DataType *r_data_type, IdentifierType *r_type, bool *r_is_const, int *r_array_size, StringName *r_struct_name, ConstantNode::Value *r_constant_value) { if (p_function_info.built_ins.has(p_identifier)) { if (r_data_type) { @@ -3602,6 +3643,11 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons if (shader->structs.has(identifier)) { pstruct = shader->structs[identifier].shader_struct; +#ifdef DEBUG_ENABLED + if (check_warnings && HAS_WARNING(ShaderWarning::UNUSED_STRUCT_FLAG) && used_structs.has(identifier)) { + used_structs[identifier].used = true; + } +#endif // DEBUG_ENABLED struct_init = true; } @@ -3825,11 +3871,17 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons } } expr = func; +#ifdef DEBUG_ENABLED + if (check_warnings) { + _parse_used_identifier(name, IdentifierType::IDENTIFIER_FUNCTION); + } +#endif // DEBUG_ENABLED } } else { //an identifier - last_const = false; + last_name = identifier; + last_type = IDENTIFIER_MAX; _set_tkpos(pos); DataType data_type; @@ -3874,12 +3926,16 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons } } } - last_const = is_const; if (ident_type == IDENTIFIER_FUNCTION) { _set_error("Can't use function as identifier: " + String(identifier)); return nullptr; } + if (is_const) { + last_type = IDENTIFIER_CONSTANT; + } else { + last_type = ident_type; + } } Node *index_expression = nullptr; @@ -3953,7 +4009,6 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons arrname->assign_expression = assign_expression; arrname->is_const = is_const; expr = arrname; - } else { VariableNode *varname = alloc_node<VariableNode>(); varname->name = identifier; @@ -3962,6 +4017,11 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons varname->struct_name = struct_name; expr = varname; } +#ifdef DEBUG_ENABLED + if (check_warnings) { + _parse_used_identifier(identifier, ident_type); + } +#endif // DEBUG_ENABLED } } else if (tk.type == TK_OP_ADD) { continue; //this one does nothing @@ -4290,8 +4350,7 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons if (array_size > 0) { tk = _get_token(); if (tk.type == TK_OP_ASSIGN) { - if (last_const) { - last_const = false; + if (last_type == IDENTIFIER_CONSTANT) { _set_error("Constants cannot be modified."); return nullptr; } @@ -4648,9 +4707,10 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons bool unary = false; bool ternary = false; + Operator op = expression[i].op; int priority; - switch (expression[i].op) { + switch (op) { case OP_EQUAL: priority = 8; break; @@ -4771,6 +4831,12 @@ ShaderLanguage::Node *ShaderLanguage::_parse_expression(BlockNode *p_block, cons ERR_FAIL_V(nullptr); //unexpected operator } +#if DEBUG_ENABLED + if (check_warnings && HAS_WARNING(ShaderWarning::FLOAT_COMPARISON_FLAG) && (op == OP_EQUAL || op == OP_NOT_EQUAL) && expression[i - 1].node->get_datatype() == TYPE_FLOAT && expression[i + 1].node->get_datatype() == TYPE_FLOAT) { + _add_line_warning(ShaderWarning::FLOAT_COMPARISON); + } +#endif // DEBUG_ENABLED + if (priority < min_priority) { // < is used for left to right (default) // <= is used for right to left @@ -5483,7 +5549,6 @@ Error ShaderLanguage::_parse_block(BlockNode *p_block, const FunctionInfo &p_fun p_block->statements.push_back(vardecl); p_block->variables[name] = var; - if (tk.type == TK_COMMA) { if (p_block->block_type == BlockNode::BLOCK_TYPE_FOR) { _set_error("Multiple declarations in 'for' loop are not implemented yet."); @@ -6313,7 +6378,11 @@ Error ShaderLanguage::_parse_shader(const Map<StringName, FunctionInfo> &p_funct } shader->structs[st.name] = st; shader->vstructs.push_back(st); // struct's order is important! - +#ifdef DEBUG_ENABLED + if (check_warnings && HAS_WARNING(ShaderWarning::UNUSED_STRUCT_FLAG)) { + used_structs.insert(st.name, Usage(tk_line)); + } +#endif // DEBUG_ENABLED } break; case TK_GLOBAL: { tk = _get_token(); @@ -6660,6 +6729,12 @@ Error ShaderLanguage::_parse_shader(const Map<StringName, FunctionInfo> &p_funct } shader->uniforms[name] = uniform2; +#ifdef DEBUG_ENABLED + if (check_warnings && HAS_WARNING(ShaderWarning::UNUSED_UNIFORM_FLAG)) { + used_uniforms.insert(name, Usage(tk_line)); + } +#endif // DEBUG_ENABLED + //reset scope for next uniform uniform_scope = ShaderNode::Uniform::SCOPE_LOCAL; @@ -6703,6 +6778,11 @@ Error ShaderLanguage::_parse_shader(const Map<StringName, FunctionInfo> &p_funct } shader->varyings[name] = varying; +#ifdef DEBUG_ENABLED + if (check_warnings && HAS_WARNING(ShaderWarning::UNUSED_VARYING_FLAG)) { + used_varyings.insert(name, Usage(tk_line)); + } +#endif // DEBUG_ENABLED } } break; @@ -7049,6 +7129,11 @@ Error ShaderLanguage::_parse_shader(const Map<StringName, FunctionInfo> &p_funct shader->constants[name] = constant; shader->vconstants.push_back(constant); +#ifdef DEBUG_ENABLED + if (check_warnings && HAS_WARNING(ShaderWarning::UNUSED_CONSTANT_FLAG)) { + used_constants.insert(name, Usage(tk_line)); + } +#endif // DEBUG_ENABLED if (tk.type == TK_COMMA) { tk = _get_token(); @@ -7110,6 +7195,12 @@ Error ShaderLanguage::_parse_shader(const Map<StringName, FunctionInfo> &p_funct if (p_functions.has(name)) { func_node->can_discard = p_functions[name].can_discard; + } else { +#ifdef DEBUG_ENABLED + if (check_warnings && HAS_WARNING(ShaderWarning::UNUSED_FUNCTION_FLAG)) { + used_functions.insert(name, Usage(tk_line)); + } +#endif // DEBUG_ENABLED } func_node->body = alloc_node<BlockNode>(); @@ -7443,6 +7534,33 @@ String ShaderLanguage::get_shader_type(const String &p_code) { return String(); } +#ifdef DEBUG_ENABLED +void ShaderLanguage::_check_warning_accums() { + for (Map<ShaderWarning::Code, Map<StringName, Usage> *>::Element *E = warnings_check_map.front(); E; E = E->next()) { + for (const Map<StringName, Usage>::Element *U = (*E->get()).front(); U; U = U->next()) { + if (!U->get().used) { + _add_warning(E->key(), U->get().decl_line, U->key()); + } + } + } +} +List<ShaderWarning>::Element *ShaderLanguage::get_warnings_ptr() { + return warnings.front(); +} +void ShaderLanguage::enable_warning_checking(bool p_enabled) { + check_warnings = p_enabled; +} +bool ShaderLanguage::is_warning_checking_enabled() const { + return check_warnings; +} +void ShaderLanguage::set_warning_flags(uint32_t p_flags) { + warning_flags = p_flags; +} +uint32_t ShaderLanguage::get_warning_flags() const { + return warning_flags; +} +#endif // DEBUG_ENABLED + Error ShaderLanguage::compile(const String &p_code, const Map<StringName, FunctionInfo> &p_functions, const Vector<StringName> &p_render_modes, const VaryingFunctionNames &p_varying_function_names, const Set<String> &p_shader_types, GlobalVariableGetTypeFunc p_global_variable_type_func) { clear(); @@ -7455,6 +7573,12 @@ Error ShaderLanguage::compile(const String &p_code, const Map<StringName, Functi shader = alloc_node<ShaderNode>(); Error err = _parse_shader(p_functions, p_render_modes, p_shader_types); +#ifdef DEBUG_ENABLED + if (check_warnings) { + _check_warning_accums(); + } +#endif // DEBUG_ENABLED + if (err != OK) { return err; } @@ -7864,6 +7988,14 @@ ShaderLanguage::ShaderNode *ShaderLanguage::get_shader() { ShaderLanguage::ShaderLanguage() { nodes = nullptr; completion_class = TAG_GLOBAL; + +#if DEBUG_ENABLED + warnings_check_map.insert(ShaderWarning::UNUSED_CONSTANT, &used_constants); + warnings_check_map.insert(ShaderWarning::UNUSED_FUNCTION, &used_functions); + warnings_check_map.insert(ShaderWarning::UNUSED_STRUCT, &used_structs); + warnings_check_map.insert(ShaderWarning::UNUSED_UNIFORM, &used_uniforms); + warnings_check_map.insert(ShaderWarning::UNUSED_VARYING, &used_varyings); +#endif // DEBUG_ENABLED } ShaderLanguage::~ShaderLanguage() { diff --git a/servers/rendering/shader_language.h b/servers/rendering/shader_language.h index cdedc5edbb..c8c5bb1fa7 100644 --- a/servers/rendering/shader_language.h +++ b/servers/rendering/shader_language.h @@ -39,6 +39,10 @@ #include "core/typedefs.h" #include "core/variant/variant.h" +#ifdef DEBUG_ENABLED +#include "shader_warnings.h" +#endif // DEBUG_ENABLED + class ShaderLanguage { public: struct TkPos { @@ -803,12 +807,42 @@ private: String error_str; int error_line; +#ifdef DEBUG_ENABLED + struct Usage { + int decl_line; + bool used = false; + Usage(int p_decl_line = -1) { + decl_line = p_decl_line; + } + }; + + Map<StringName, Usage> used_constants; + Map<StringName, Usage> used_varyings; + Map<StringName, Usage> used_uniforms; + Map<StringName, Usage> used_functions; + Map<StringName, Usage> used_structs; + Map<ShaderWarning::Code, Map<StringName, Usage> *> warnings_check_map; + + List<ShaderWarning> warnings; + + bool check_warnings = false; + uint32_t warning_flags; + + void _add_line_warning(ShaderWarning::Code p_code, const StringName &p_subject = "") { + warnings.push_back(ShaderWarning(p_code, tk_line, p_subject)); + } + void _add_warning(ShaderWarning::Code p_code, int p_line, const StringName &p_subject = "") { + warnings.push_back(ShaderWarning(p_code, p_line, p_subject)); + } + void _check_warning_accums(); +#endif // DEBUG_ENABLED + String code; int char_idx; int tk_line; StringName current_function; - bool last_const = false; + StringName last_name; VaryingFunctionNames varying_function_names; @@ -849,9 +883,15 @@ private: IDENTIFIER_LOCAL_VAR, IDENTIFIER_BUILTIN_VAR, IDENTIFIER_CONSTANT, + IDENTIFIER_MAX, }; + IdentifierType last_type = IDENTIFIER_MAX; + bool _find_identifier(const BlockNode *p_block, bool p_allow_reassign, const FunctionInfo &p_function_info, const StringName &p_identifier, DataType *r_data_type = nullptr, IdentifierType *r_type = nullptr, bool *r_is_const = nullptr, int *r_array_size = nullptr, StringName *r_struct_name = nullptr, ConstantNode::Value *r_constant_value = nullptr); +#ifdef DEBUG_ENABLED + void _parse_used_identifier(const StringName &p_identifier, IdentifierType p_type); +#endif // DEBUG_ENABLED bool _is_operator_assign(Operator p_op) const; bool _validate_assign(Node *p_node, const FunctionInfo &p_function_info, String *r_message = nullptr); bool _validate_operator(OperatorNode *p_op, DataType *r_ret_type = nullptr); @@ -910,6 +950,16 @@ private: Error _find_last_flow_op_in_op(ControlFlowNode *p_flow, FlowOperation p_op); public: +#ifdef DEBUG_ENABLED + List<ShaderWarning>::Element *get_warnings_ptr(); + + void enable_warning_checking(bool p_enabled); + bool is_warning_checking_enabled() const; + + void set_warning_flags(uint32_t p_flags); + uint32_t get_warning_flags() const; +#endif // DEBUG_ENABLED + //static void get_keyword_list(ShaderType p_type,List<String> *p_keywords); void clear(); diff --git a/servers/rendering/shader_warnings.cpp b/servers/rendering/shader_warnings.cpp new file mode 100644 index 0000000000..aa11b4e397 --- /dev/null +++ b/servers/rendering/shader_warnings.cpp @@ -0,0 +1,131 @@ +/*************************************************************************/ +/* shader_warnings.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2021 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#include "shader_warnings.h" +#include "core/variant/variant.h" + +#ifdef DEBUG_ENABLED + +ShaderWarning::Code ShaderWarning::get_code() const { + return code; +} + +int ShaderWarning::get_line() const { + return line; +} + +const StringName &ShaderWarning::get_subject() const { + return subject; +} + +String ShaderWarning::get_message() const { + switch (code) { + case FLOAT_COMPARISON: + return vformat("Direct floating-point comparison (this may not evaluate to `true` as you expect). Instead, use `abs(a - b) < 0.0001` for an approximate but predictable comparison."); + case UNUSED_CONSTANT: + return vformat("The const '%s' is declared but never used.", subject); + case UNUSED_FUNCTION: + return vformat("The function '%s' is declared but never used.", subject); + case UNUSED_STRUCT: + return vformat("The struct '%s' is declared but never used.", subject); + case UNUSED_UNIFORM: + return vformat("The uniform '%s' is declared but never used.", subject); + case UNUSED_VARYING: + return vformat("The varying '%s' is declared but never used.", subject); + default: + break; + } + return String(); +} + +String ShaderWarning::get_name() const { + return get_name_from_code(code); +} + +String ShaderWarning::get_name_from_code(Code p_code) { + ERR_FAIL_INDEX_V(p_code, WARNING_MAX, String()); + + static const char *names[] = { + "FLOAT_COMPARISON", + "UNUSED_CONSTANT", + "UNUSED_FUNCTION", + "UNUSED_STRUCT", + "UNUSED_UNIFORM", + "UNUSED_VARYING", + }; + + static_assert((sizeof(names) / sizeof(*names)) == WARNING_MAX, "Amount of warning types don't match the amount of warning names."); + + return names[(int)p_code]; +} + +ShaderWarning::Code ShaderWarning::get_code_from_name(const String &p_name) { + for (int i = 0; i < WARNING_MAX; i++) { + if (get_name_from_code((Code)i) == p_name) { + return (Code)i; + } + } + + ERR_FAIL_V_MSG(WARNING_MAX, "Invalid shader warning name: " + p_name); +} + +static Map<int, uint32_t> *code_to_flags_map = nullptr; + +static void init_code_to_flags_map() { + code_to_flags_map = memnew((Map<int, uint32_t>)); + code_to_flags_map->insert(ShaderWarning::FLOAT_COMPARISON, ShaderWarning::FLOAT_COMPARISON_FLAG); + code_to_flags_map->insert(ShaderWarning::UNUSED_CONSTANT, ShaderWarning::UNUSED_CONSTANT_FLAG); + code_to_flags_map->insert(ShaderWarning::UNUSED_FUNCTION, ShaderWarning::UNUSED_FUNCTION_FLAG); + code_to_flags_map->insert(ShaderWarning::UNUSED_STRUCT, ShaderWarning::UNUSED_STRUCT_FLAG); + code_to_flags_map->insert(ShaderWarning::UNUSED_UNIFORM, ShaderWarning::UNUSED_UNIFORM_FLAG); + code_to_flags_map->insert(ShaderWarning::UNUSED_VARYING, ShaderWarning::UNUSED_VARYING_FLAG); +} + +ShaderWarning::CodeFlags ShaderWarning::get_flags_from_codemap(const Map<Code, bool> &p_map) { + uint32_t result = 0U; + + if (code_to_flags_map == nullptr) { + init_code_to_flags_map(); + } + + for (Map<Code, bool>::Element *E = p_map.front(); E; E = E->next()) { + if (E->get()) { + ERR_FAIL_COND_V(!code_to_flags_map->has((int)E->key()), ShaderWarning::NONE_FLAG); + result |= (*code_to_flags_map)[(int)E->key()]; + } + } + return (CodeFlags)result; +} + +ShaderWarning::ShaderWarning(Code p_code, int p_line, const StringName &p_subject) : + code(p_code), line(p_line), subject(p_subject) { +} + +#endif // DEBUG_ENABLED diff --git a/servers/rendering/shader_warnings.h b/servers/rendering/shader_warnings.h new file mode 100644 index 0000000000..c40aeefa2d --- /dev/null +++ b/servers/rendering/shader_warnings.h @@ -0,0 +1,83 @@ +/*************************************************************************/ +/* shader_warnings.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2021 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef SHADER_WARNINGS +#define SHADER_WARNINGS + +#ifdef DEBUG_ENABLED + +#include "core/string/string_name.h" +#include "core/templates/list.h" +#include "core/templates/map.h" + +class ShaderWarning { +public: + enum Code { + FLOAT_COMPARISON, + UNUSED_CONSTANT, + UNUSED_FUNCTION, + UNUSED_STRUCT, + UNUSED_UNIFORM, + UNUSED_VARYING, + WARNING_MAX, + }; + + enum CodeFlags : uint32_t { + NONE_FLAG = 0U, + FLOAT_COMPARISON_FLAG = 1U, + UNUSED_CONSTANT_FLAG = 2U, + UNUSED_FUNCTION_FLAG = 4U, + UNUSED_STRUCT_FLAG = 8U, + UNUSED_UNIFORM_FLAG = 16U, + UNUSED_VARYING_FLAG = 32U, + }; + +private: + Code code; + int line; + StringName subject; + +public: + Code get_code() const; + int get_line() const; + const StringName &get_subject() const; + String get_message() const; + String get_name() const; + + static String get_name_from_code(Code p_code); + static Code get_code_from_name(const String &p_name); + static CodeFlags get_flags_from_codemap(const Map<Code, bool> &p_map); + + ShaderWarning(Code p_code = WARNING_MAX, int p_line = -1, const StringName &p_subject = ""); +}; + +#endif // DEBUG_ENABLED + +#endif // SHADER_WARNINGS diff --git a/tests/test_physics_3d.cpp b/tests/test_physics_3d.cpp index ac8078a0a8..727c44b3ac 100644 --- a/tests/test_physics_3d.cpp +++ b/tests/test_physics_3d.cpp @@ -30,8 +30,8 @@ #include "test_physics_3d.h" +#include "core/math/convex_hull.h" #include "core/math/math_funcs.h" -#include "core/math/quick_hull.h" #include "core/os/main_loop.h" #include "core/os/os.h" #include "core/string/print_string.h" @@ -169,7 +169,7 @@ protected: RID convex_mesh = vs->mesh_create(); Geometry3D::MeshData convex_data = Geometry3D::build_convex_mesh(convex_planes); - QuickHull::build(convex_data.vertices, convex_data); + ConvexHullComputer::convex_hull(convex_data.vertices, convex_data); vs->mesh_add_surface_from_mesh_data(convex_mesh, convex_data); type_mesh_map[PhysicsServer3D::SHAPE_CONVEX_POLYGON] = convex_mesh; diff --git a/tests/test_render.cpp b/tests/test_render.cpp index 72b2840098..9737fd03f3 100644 --- a/tests/test_render.cpp +++ b/tests/test_render.cpp @@ -30,8 +30,8 @@ #include "test_render.h" +#include "core/math/convex_hull.h" #include "core/math/math_funcs.h" -#include "core/math/quick_hull.h" #include "core/os/keyboard.h" #include "core/os/main_loop.h" #include "core/os/os.h" @@ -118,7 +118,7 @@ public: vts.push_back(Vector3(-1, -1, -1)); Geometry3D::MeshData md; - Error err = QuickHull::build(vts, md); + Error err = ConvexHullComputer::convex_hull(vts, md); print_line("ERR: " + itos(err)); test_cube = vs->mesh_create(); vs->mesh_add_surface_from_mesh_data(test_cube, md); diff --git a/thirdparty/README.md b/thirdparty/README.md index 7cedd1a2cb..d3599fd195 100644 --- a/thirdparty/README.md +++ b/thirdparty/README.md @@ -375,6 +375,9 @@ Files extracted from upstream repository: - All files in `src/`. - `LICENSE.md`. +An [experimental upstream feature](https://github.com/zeux/meshoptimizer/tree/simplify-attr), +has been backported, see patch in `patches` directory. + ## miniupnpc diff --git a/thirdparty/meshoptimizer/meshoptimizer.h b/thirdparty/meshoptimizer/meshoptimizer.h index fe8d349731..e44b99ce52 100644 --- a/thirdparty/meshoptimizer/meshoptimizer.h +++ b/thirdparty/meshoptimizer/meshoptimizer.h @@ -299,6 +299,11 @@ MESHOPTIMIZER_EXPERIMENTAL void meshopt_decodeFilterExp(void* buffer, size_t ver MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* result_error); /** + * Experimental: Mesh simplifier with attribute metric; attributes follow xyz position data atm (vertex data must contain 3 + attribute_count floats per vertex) + */ +MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_data, size_t vertex_count, size_t vertex_stride, size_t target_index_count, float target_error, float* result_error, const float* attributes, const float* attribute_weights, size_t attribute_count); + +/** * Experimental: Mesh simplifier (sloppy) * Reduces the number of triangles in the mesh, sacrificing mesh apperance for simplification performance * The algorithm doesn't preserve mesh topology but can stop short of the target goal based on target error. diff --git a/thirdparty/meshoptimizer/patches/attribute-aware-simplify.patch b/thirdparty/meshoptimizer/patches/attribute-aware-simplify.patch new file mode 100644 index 0000000000..cf648b0da3 --- /dev/null +++ b/thirdparty/meshoptimizer/patches/attribute-aware-simplify.patch @@ -0,0 +1,262 @@ +diff --git a/thirdparty/meshoptimizer/meshoptimizer.h b/thirdparty/meshoptimizer/meshoptimizer.h +index fe8d349731..e44b99ce52 100644 +--- a/thirdparty/meshoptimizer/meshoptimizer.h ++++ b/thirdparty/meshoptimizer/meshoptimizer.h +@@ -298,6 +298,11 @@ MESHOPTIMIZER_EXPERIMENTAL void meshopt_decodeFilterExp(void* buffer, size_t ver + */ + MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* result_error); + ++/** ++ * Experimental: Mesh simplifier with attribute metric; attributes follow xyz position data atm (vertex data must contain 3 + attribute_count floats per vertex) ++ */ ++MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_data, size_t vertex_count, size_t vertex_stride, size_t target_index_count, float target_error, float* result_error, const float* attributes, const float* attribute_weights, size_t attribute_count); ++ + /** + * Experimental: Mesh simplifier (sloppy) + * Reduces the number of triangles in the mesh, sacrificing mesh apperance for simplification performance +diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp +index b2cb589462..059cabb055 100644 +--- a/thirdparty/meshoptimizer/simplifier.cpp ++++ b/thirdparty/meshoptimizer/simplifier.cpp +@@ -20,6 +20,8 @@ + #define TRACESTATS(i) (void)0 + #endif + ++#define ATTRIBUTES 8 ++ + // This work is based on: + // Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. 1997 + // Michael Garland. Quadric-based polygonal surface simplification. 1999 +@@ -358,6 +360,10 @@ static void classifyVertices(unsigned char* result, unsigned int* loop, unsigned + struct Vector3 + { + float x, y, z; ++ ++#if ATTRIBUTES ++ float a[ATTRIBUTES]; ++#endif + }; + + static float rescalePositions(Vector3* result, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride) +@@ -414,6 +420,13 @@ struct Quadric + float a10, a20, a21; + float b0, b1, b2, c; + float w; ++ ++#if ATTRIBUTES ++ float gx[ATTRIBUTES]; ++ float gy[ATTRIBUTES]; ++ float gz[ATTRIBUTES]; ++ float gw[ATTRIBUTES]; ++#endif + }; + + struct Collapse +@@ -456,6 +469,16 @@ static void quadricAdd(Quadric& Q, const Quadric& R) + Q.b2 += R.b2; + Q.c += R.c; + Q.w += R.w; ++ ++#if ATTRIBUTES ++ for (int k = 0; k < ATTRIBUTES; ++k) ++ { ++ Q.gx[k] += R.gx[k]; ++ Q.gy[k] += R.gy[k]; ++ Q.gz[k] += R.gz[k]; ++ Q.gw[k] += R.gw[k]; ++ } ++#endif + } + + static float quadricError(const Quadric& Q, const Vector3& v) +@@ -481,6 +504,17 @@ static float quadricError(const Quadric& Q, const Vector3& v) + r += ry * v.y; + r += rz * v.z; + ++#if ATTRIBUTES ++ // see quadricUpdateAttributes for general derivation; here we need to add the parts of (eval(pos) - attr)^2 that depend on attr ++ for (int k = 0; k < ATTRIBUTES; ++k) ++ { ++ float a = v.a[k]; ++ ++ r += a * a * Q.w; ++ r -= 2 * a * (v.x * Q.gx[k] + v.y * Q.gy[k] + v.z * Q.gz[k] + Q.gw[k]); ++ } ++#endif ++ + float s = Q.w == 0.f ? 0.f : 1.f / Q.w; + + return fabsf(r) * s; +@@ -504,6 +538,13 @@ static void quadricFromPlane(Quadric& Q, float a, float b, float c, float d, flo + Q.b2 = c * dw; + Q.c = d * dw; + Q.w = w; ++ ++#if ATTRIBUTES ++ memset(Q.gx, 0, sizeof(Q.gx)); ++ memset(Q.gy, 0, sizeof(Q.gy)); ++ memset(Q.gz, 0, sizeof(Q.gz)); ++ memset(Q.gw, 0, sizeof(Q.gw)); ++#endif + } + + static void quadricFromPoint(Quadric& Q, float x, float y, float z, float w) +@@ -556,6 +597,84 @@ static void quadricFromTriangleEdge(Quadric& Q, const Vector3& p0, const Vector3 + quadricFromPlane(Q, normal.x, normal.y, normal.z, -distance, length * weight); + } + ++#if ATTRIBUTES ++static void quadricUpdateAttributes(Quadric& Q, const Vector3& p0, const Vector3& p1, const Vector3& p2, float w) ++{ ++ // for each attribute we want to encode the following function into the quadric: ++ // (eval(pos) - attr)^2 ++ // where eval(pos) interpolates attribute across the triangle like so: ++ // eval(pos) = pos.x * gx + pos.y * gy + pos.z * gz + gw ++ // where gx/gy/gz/gw are gradients ++ Vector3 p10 = {p1.x - p0.x, p1.y - p0.y, p1.z - p0.z}; ++ Vector3 p20 = {p2.x - p0.x, p2.y - p0.y, p2.z - p0.z}; ++ ++ // we compute gradients using barycentric coordinates; barycentric coordinates can be computed as follows: ++ // v = (d11 * d20 - d01 * d21) / denom ++ // w = (d00 * d21 - d01 * d20) / denom ++ // u = 1 - v - w ++ // here v0, v1 are triangle edge vectors, v2 is a vector from point to triangle corner, and dij = dot(vi, vj) ++ const Vector3& v0 = p10; ++ const Vector3& v1 = p20; ++ float d00 = v0.x * v0.x + v0.y * v0.y + v0.z * v0.z; ++ float d01 = v0.x * v1.x + v0.y * v1.y + v0.z * v1.z; ++ float d11 = v1.x * v1.x + v1.y * v1.y + v1.z * v1.z; ++ float denom = d00 * d11 - d01 * d01; ++ float denomr = denom == 0 ? 0.f : 1.f / denom; ++ ++ // precompute gradient factors ++ // these are derived by directly computing derivative of eval(pos) = a0 * u + a1 * v + a2 * w and factoring out common factors that are shared between attributes ++ float gx1 = (d11 * v0.x - d01 * v1.x) * denomr; ++ float gx2 = (d00 * v1.x - d01 * v0.x) * denomr; ++ float gy1 = (d11 * v0.y - d01 * v1.y) * denomr; ++ float gy2 = (d00 * v1.y - d01 * v0.y) * denomr; ++ float gz1 = (d11 * v0.z - d01 * v1.z) * denomr; ++ float gz2 = (d00 * v1.z - d01 * v0.z) * denomr; ++ ++ for (int k = 0; k < ATTRIBUTES; ++k) ++ { ++ float a0 = p0.a[k], a1 = p1.a[k], a2 = p2.a[k]; ++ ++ // compute gradient of eval(pos) for x/y/z/w ++ // the formulas below are obtained by directly computing derivative of eval(pos) = a0 * u + a1 * v + a2 * w ++ float gx = gx1 * (a1 - a0) + gx2 * (a2 - a0); ++ float gy = gy1 * (a1 - a0) + gy2 * (a2 - a0); ++ float gz = gz1 * (a1 - a0) + gz2 * (a2 - a0); ++ float gw = a0 - p0.x * gx - p0.y * gy - p0.z * gz; ++ ++ // quadric encodes (eval(pos)-attr)^2; this means that the resulting expansion needs to compute, for example, pos.x * pos.y * K ++ // since quadrics already encode factors for pos.x * pos.y, we can accumulate almost everything in basic quadric fields ++ Q.a00 += w * (gx * gx); ++ Q.a11 += w * (gy * gy); ++ Q.a22 += w * (gz * gz); ++ ++ Q.a10 += w * (gy * gx); ++ Q.a20 += w * (gz * gx); ++ Q.a21 += w * (gz * gy); ++ ++ Q.b0 += w * (gx * gw); ++ Q.b1 += w * (gy * gw); ++ Q.b2 += w * (gz * gw); ++ ++ Q.c += w * (gw * gw); ++ ++ // the only remaining sum components are ones that depend on attr; these will be addded during error evaluation, see quadricError ++ Q.gx[k] = w * gx; ++ Q.gy[k] = w * gy; ++ Q.gz[k] = w * gz; ++ Q.gw[k] = w * gw; ++ ++#if TRACE > 2 ++ printf("attr%d: %e %e %e\n", ++ k, ++ (gx * p0.x + gy * p0.y + gz * p0.z + gw - a0), ++ (gx * p1.x + gy * p1.y + gz * p1.z + gw - a1), ++ (gx * p2.x + gy * p2.y + gz * p2.z + gw - a2) ++ ); ++#endif ++ } ++} ++#endif ++ + static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap) + { + for (size_t i = 0; i < index_count; i += 3) +@@ -567,6 +686,9 @@ static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indic + Quadric Q; + quadricFromTriangle(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], 1.f); + ++#if ATTRIBUTES ++ quadricUpdateAttributes(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], Q.w); ++#endif + quadricAdd(vertex_quadrics[remap[i0]], Q); + quadricAdd(vertex_quadrics[remap[i1]], Q); + quadricAdd(vertex_quadrics[remap[i2]], Q); +@@ -1259,13 +1381,19 @@ unsigned int* meshopt_simplifyDebugLoopBack = 0; + #endif + + size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* out_result_error) ++{ ++ return meshopt_simplifyWithAttributes(destination, indices, index_count, vertex_positions_data, vertex_count, vertex_positions_stride, target_index_count, target_error, out_result_error, 0, 0, 0); ++} ++ ++size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_data, size_t vertex_count, size_t vertex_stride, size_t target_index_count, float target_error, float* out_result_error, const float* attributes, const float* attribute_weights, size_t attribute_count) + { + using namespace meshopt; + + assert(index_count % 3 == 0); +- assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256); +- assert(vertex_positions_stride % sizeof(float) == 0); ++ assert(vertex_stride > 0 && vertex_stride <= 256); ++ assert(vertex_stride % sizeof(float) == 0); + assert(target_index_count <= index_count); ++ assert(attribute_count <= ATTRIBUTES); + + meshopt_Allocator allocator; + +@@ -1279,7 +1407,7 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, + // build position remap that maps each vertex to the one with identical position + unsigned int* remap = allocator.allocate<unsigned int>(vertex_count); + unsigned int* wedge = allocator.allocate<unsigned int>(vertex_count); +- buildPositionRemap(remap, wedge, vertex_positions_data, vertex_count, vertex_positions_stride, allocator); ++ buildPositionRemap(remap, wedge, vertex_data, vertex_count, vertex_stride, allocator); + + // classify vertices; vertex kind determines collapse rules, see kCanCollapse + unsigned char* vertex_kind = allocator.allocate<unsigned char>(vertex_count); +@@ -1303,7 +1431,21 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, + #endif + + Vector3* vertex_positions = allocator.allocate<Vector3>(vertex_count); +- rescalePositions(vertex_positions, vertex_positions_data, vertex_count, vertex_positions_stride); ++ rescalePositions(vertex_positions, vertex_data, vertex_count, vertex_stride); ++ ++#if ATTRIBUTES ++ for (size_t i = 0; i < vertex_count; ++i) ++ { ++ memset(vertex_positions[i].a, 0, sizeof(vertex_positions[i].a)); ++ ++ for (size_t k = 0; k < attribute_count; ++k) ++ { ++ float a = attributes[i * attribute_count + k]; ++ ++ vertex_positions[i].a[k] = a * attribute_weights[k]; ++ } ++ } ++#endif + + Quadric* vertex_quadrics = allocator.allocate<Quadric>(vertex_count); + memset(vertex_quadrics, 0, vertex_count * sizeof(Quadric)); +@@ -1395,7 +1537,9 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, + + // result_error is quadratic; we need to remap it back to linear + if (out_result_error) ++ { + *out_result_error = sqrtf(result_error); ++ } + + return result_count; + } diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp index b2cb589462..059cabb055 100644 --- a/thirdparty/meshoptimizer/simplifier.cpp +++ b/thirdparty/meshoptimizer/simplifier.cpp @@ -20,6 +20,8 @@ #define TRACESTATS(i) (void)0 #endif +#define ATTRIBUTES 8 + // This work is based on: // Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. 1997 // Michael Garland. Quadric-based polygonal surface simplification. 1999 @@ -358,6 +360,10 @@ static void classifyVertices(unsigned char* result, unsigned int* loop, unsigned struct Vector3 { float x, y, z; + +#if ATTRIBUTES + float a[ATTRIBUTES]; +#endif }; static float rescalePositions(Vector3* result, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride) @@ -414,6 +420,13 @@ struct Quadric float a10, a20, a21; float b0, b1, b2, c; float w; + +#if ATTRIBUTES + float gx[ATTRIBUTES]; + float gy[ATTRIBUTES]; + float gz[ATTRIBUTES]; + float gw[ATTRIBUTES]; +#endif }; struct Collapse @@ -456,6 +469,16 @@ static void quadricAdd(Quadric& Q, const Quadric& R) Q.b2 += R.b2; Q.c += R.c; Q.w += R.w; + +#if ATTRIBUTES + for (int k = 0; k < ATTRIBUTES; ++k) + { + Q.gx[k] += R.gx[k]; + Q.gy[k] += R.gy[k]; + Q.gz[k] += R.gz[k]; + Q.gw[k] += R.gw[k]; + } +#endif } static float quadricError(const Quadric& Q, const Vector3& v) @@ -481,6 +504,17 @@ static float quadricError(const Quadric& Q, const Vector3& v) r += ry * v.y; r += rz * v.z; +#if ATTRIBUTES + // see quadricUpdateAttributes for general derivation; here we need to add the parts of (eval(pos) - attr)^2 that depend on attr + for (int k = 0; k < ATTRIBUTES; ++k) + { + float a = v.a[k]; + + r += a * a * Q.w; + r -= 2 * a * (v.x * Q.gx[k] + v.y * Q.gy[k] + v.z * Q.gz[k] + Q.gw[k]); + } +#endif + float s = Q.w == 0.f ? 0.f : 1.f / Q.w; return fabsf(r) * s; @@ -504,6 +538,13 @@ static void quadricFromPlane(Quadric& Q, float a, float b, float c, float d, flo Q.b2 = c * dw; Q.c = d * dw; Q.w = w; + +#if ATTRIBUTES + memset(Q.gx, 0, sizeof(Q.gx)); + memset(Q.gy, 0, sizeof(Q.gy)); + memset(Q.gz, 0, sizeof(Q.gz)); + memset(Q.gw, 0, sizeof(Q.gw)); +#endif } static void quadricFromPoint(Quadric& Q, float x, float y, float z, float w) @@ -556,6 +597,84 @@ static void quadricFromTriangleEdge(Quadric& Q, const Vector3& p0, const Vector3 quadricFromPlane(Q, normal.x, normal.y, normal.z, -distance, length * weight); } +#if ATTRIBUTES +static void quadricUpdateAttributes(Quadric& Q, const Vector3& p0, const Vector3& p1, const Vector3& p2, float w) +{ + // for each attribute we want to encode the following function into the quadric: + // (eval(pos) - attr)^2 + // where eval(pos) interpolates attribute across the triangle like so: + // eval(pos) = pos.x * gx + pos.y * gy + pos.z * gz + gw + // where gx/gy/gz/gw are gradients + Vector3 p10 = {p1.x - p0.x, p1.y - p0.y, p1.z - p0.z}; + Vector3 p20 = {p2.x - p0.x, p2.y - p0.y, p2.z - p0.z}; + + // we compute gradients using barycentric coordinates; barycentric coordinates can be computed as follows: + // v = (d11 * d20 - d01 * d21) / denom + // w = (d00 * d21 - d01 * d20) / denom + // u = 1 - v - w + // here v0, v1 are triangle edge vectors, v2 is a vector from point to triangle corner, and dij = dot(vi, vj) + const Vector3& v0 = p10; + const Vector3& v1 = p20; + float d00 = v0.x * v0.x + v0.y * v0.y + v0.z * v0.z; + float d01 = v0.x * v1.x + v0.y * v1.y + v0.z * v1.z; + float d11 = v1.x * v1.x + v1.y * v1.y + v1.z * v1.z; + float denom = d00 * d11 - d01 * d01; + float denomr = denom == 0 ? 0.f : 1.f / denom; + + // precompute gradient factors + // these are derived by directly computing derivative of eval(pos) = a0 * u + a1 * v + a2 * w and factoring out common factors that are shared between attributes + float gx1 = (d11 * v0.x - d01 * v1.x) * denomr; + float gx2 = (d00 * v1.x - d01 * v0.x) * denomr; + float gy1 = (d11 * v0.y - d01 * v1.y) * denomr; + float gy2 = (d00 * v1.y - d01 * v0.y) * denomr; + float gz1 = (d11 * v0.z - d01 * v1.z) * denomr; + float gz2 = (d00 * v1.z - d01 * v0.z) * denomr; + + for (int k = 0; k < ATTRIBUTES; ++k) + { + float a0 = p0.a[k], a1 = p1.a[k], a2 = p2.a[k]; + + // compute gradient of eval(pos) for x/y/z/w + // the formulas below are obtained by directly computing derivative of eval(pos) = a0 * u + a1 * v + a2 * w + float gx = gx1 * (a1 - a0) + gx2 * (a2 - a0); + float gy = gy1 * (a1 - a0) + gy2 * (a2 - a0); + float gz = gz1 * (a1 - a0) + gz2 * (a2 - a0); + float gw = a0 - p0.x * gx - p0.y * gy - p0.z * gz; + + // quadric encodes (eval(pos)-attr)^2; this means that the resulting expansion needs to compute, for example, pos.x * pos.y * K + // since quadrics already encode factors for pos.x * pos.y, we can accumulate almost everything in basic quadric fields + Q.a00 += w * (gx * gx); + Q.a11 += w * (gy * gy); + Q.a22 += w * (gz * gz); + + Q.a10 += w * (gy * gx); + Q.a20 += w * (gz * gx); + Q.a21 += w * (gz * gy); + + Q.b0 += w * (gx * gw); + Q.b1 += w * (gy * gw); + Q.b2 += w * (gz * gw); + + Q.c += w * (gw * gw); + + // the only remaining sum components are ones that depend on attr; these will be addded during error evaluation, see quadricError + Q.gx[k] = w * gx; + Q.gy[k] = w * gy; + Q.gz[k] = w * gz; + Q.gw[k] = w * gw; + +#if TRACE > 2 + printf("attr%d: %e %e %e\n", + k, + (gx * p0.x + gy * p0.y + gz * p0.z + gw - a0), + (gx * p1.x + gy * p1.y + gz * p1.z + gw - a1), + (gx * p2.x + gy * p2.y + gz * p2.z + gw - a2) + ); +#endif + } +} +#endif + static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap) { for (size_t i = 0; i < index_count; i += 3) @@ -567,6 +686,9 @@ static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indic Quadric Q; quadricFromTriangle(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], 1.f); +#if ATTRIBUTES + quadricUpdateAttributes(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], Q.w); +#endif quadricAdd(vertex_quadrics[remap[i0]], Q); quadricAdd(vertex_quadrics[remap[i1]], Q); quadricAdd(vertex_quadrics[remap[i2]], Q); @@ -1260,12 +1382,18 @@ unsigned int* meshopt_simplifyDebugLoopBack = 0; size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float* out_result_error) { + return meshopt_simplifyWithAttributes(destination, indices, index_count, vertex_positions_data, vertex_count, vertex_positions_stride, target_index_count, target_error, out_result_error, 0, 0, 0); +} + +size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_data, size_t vertex_count, size_t vertex_stride, size_t target_index_count, float target_error, float* out_result_error, const float* attributes, const float* attribute_weights, size_t attribute_count) +{ using namespace meshopt; assert(index_count % 3 == 0); - assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256); - assert(vertex_positions_stride % sizeof(float) == 0); + assert(vertex_stride > 0 && vertex_stride <= 256); + assert(vertex_stride % sizeof(float) == 0); assert(target_index_count <= index_count); + assert(attribute_count <= ATTRIBUTES); meshopt_Allocator allocator; @@ -1279,7 +1407,7 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, // build position remap that maps each vertex to the one with identical position unsigned int* remap = allocator.allocate<unsigned int>(vertex_count); unsigned int* wedge = allocator.allocate<unsigned int>(vertex_count); - buildPositionRemap(remap, wedge, vertex_positions_data, vertex_count, vertex_positions_stride, allocator); + buildPositionRemap(remap, wedge, vertex_data, vertex_count, vertex_stride, allocator); // classify vertices; vertex kind determines collapse rules, see kCanCollapse unsigned char* vertex_kind = allocator.allocate<unsigned char>(vertex_count); @@ -1303,7 +1431,21 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, #endif Vector3* vertex_positions = allocator.allocate<Vector3>(vertex_count); - rescalePositions(vertex_positions, vertex_positions_data, vertex_count, vertex_positions_stride); + rescalePositions(vertex_positions, vertex_data, vertex_count, vertex_stride); + +#if ATTRIBUTES + for (size_t i = 0; i < vertex_count; ++i) + { + memset(vertex_positions[i].a, 0, sizeof(vertex_positions[i].a)); + + for (size_t k = 0; k < attribute_count; ++k) + { + float a = attributes[i * attribute_count + k]; + + vertex_positions[i].a[k] = a * attribute_weights[k]; + } + } +#endif Quadric* vertex_quadrics = allocator.allocate<Quadric>(vertex_count); memset(vertex_quadrics, 0, vertex_count * sizeof(Quadric)); @@ -1395,7 +1537,9 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, // result_error is quadratic; we need to remap it back to linear if (out_result_error) + { *out_result_error = sqrtf(result_error); + } return result_count; } |
