From 7a41f8c604143eec16c232cffda122b095c5108f Mon Sep 17 00:00:00 2001 From: "Bil Bas (Spooner)" Date: Sat, 10 Jan 2015 20:44:20 +0000 Subject: Added basic sprintf functionality (e.g. "fish %d %s" % [12, Vector2(1, 2)]) --- core/ustring.cpp | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++++ core/ustring.h | 4 ++- core/variant_op.cpp | 14 ++++++++ 3 files changed, 115 insertions(+), 1 deletion(-) (limited to 'core') diff --git a/core/ustring.cpp b/core/ustring.cpp index 581cc29440..a7359f112f 100644 --- a/core/ustring.cpp +++ b/core/ustring.cpp @@ -34,6 +34,8 @@ #include "io/md5.h" #include "ucaps.h" #include "color.h" +#include "variant.h" +#include #define MAX_DIGITS 6 #define UPPERCASE(m_c) (((m_c)>='a' && (m_c)<='z')?((m_c)-('a'-'A')):(m_c)) #define LOWERCASE(m_c) (((m_c)>='A' && (m_c)<='Z')?((m_c)+('a'-'A')):(m_c)) @@ -3518,4 +3520,100 @@ String rtoss(double p_val) { return String::num_scientific(p_val); } +// sprintf is implemented in GDScript via: +// "fish %s pie" % "frog" +// "fish %s %d pie" % ["frog", 12] +const int FORMAT_BUFFER_SIZE = 1024; +const int OUTPUT_BUFFER_SIZE = 1024 * 100; +String String::sprintf(const Array& values) const { + + String formatted; + CharType* self = (CharType*)c_str(); + bool in_format = false; + int value_index = 0; + char format_format[FORMAT_BUFFER_SIZE] = "%d"; + + for (; *self; self++) { + const CharType c = *self; + + if (in_format) { // We have % - lets see what else we get. + switch (c) { + case '%': // Manage %% as % + formatted += chr(c); + in_format = false; + break; + + case 'd': // Integer (signed) + case 'o': // Octal + case 'x': // Hexadecimal (lowercase) + case 'X': // Hexadecimal (uppercase) + if (values[value_index].is_num()) { + char buffer[OUTPUT_BUFFER_SIZE]; + int value = values[value_index]; + format_format[1] = c; + format_format[2] = 0; + ::sprintf(buffer, format_format, value); + + formatted += String(buffer); + ++value_index; + in_format = false; + } else { + // TODO: Error? + } + + break; + + case 'f': // Float + if (values[value_index].is_num()) { + char buffer[OUTPUT_BUFFER_SIZE]; + double value = values[value_index]; + ::sprintf(buffer, "%f", value); + + formatted += String(buffer); + ++value_index; + in_format = false; + } else { + // TODO: Error? + } + + break; + + case 's': // String + String value = values[value_index]; + formatted += value; + ++value_index; + in_format = false; + break; + + // case '-': // Left justify + // break; + + // case '+': // Show + if positive. + // break; + + // case '0': case '1': case '2': case '3': case '4': + // case '5': case '6': case '7': case '8': case '9': + // break; + + // case '.': // Float separtor. + // break; + + // case '*': // Dyanmic width, based on value. + // break; + //default: + // TODO: error? + } + } else { // Not in format string. + switch (c) { + case '%': + in_format = true; + break; + default: + formatted += chr(c); + } + } + } + + return formatted; +} diff --git a/core/ustring.h b/core/ustring.h index e1d6761742..ccbbf5e5d2 100644 --- a/core/ustring.h +++ b/core/ustring.h @@ -31,6 +31,7 @@ #include "typedefs.h" #include "vector.h" +#include "array.h" /** @author red @@ -127,6 +128,7 @@ public: String insert(int p_at_pos,String p_string) const; String pad_decimals(int p_digits) const; String pad_zeros(int p_digits) const; + String sprintf(const Array& values) const; static String num(double p_num,int p_decimals=-1); static String num_scientific(double p_num); static String num_real(double p_num); @@ -203,7 +205,7 @@ public: String xml_unescape() const; String c_escape() const; String c_unescape() const; - + String percent_encode() const; String percent_decode() const; diff --git a/core/variant_op.cpp b/core/variant_op.cpp index ec43b1275c..533a9d6952 100644 --- a/core/variant_op.cpp +++ b/core/variant_op.cpp @@ -736,6 +736,20 @@ void Variant::evaluate(const Operator& p_op, const Variant& p_a, const Variant& } #endif _RETURN( p_a._data._int % p_b._data._int ); + + } else if (p_a.type==STRING) { + const String *str=reinterpret_cast(p_a._data._mem); + + if (p_b.type==ARRAY) { + // e.g. "frog %s %d" % ["fish", 12] + const Array *arr=reinterpret_cast(p_b._data._mem); + _RETURN(str->sprintf(*arr)); + } else { + // e.g. "frog %d" % 12 + Array arr; + arr.push_back(p_b); + _RETURN(str->sprintf(arr)); + } } r_valid=false; -- cgit v1.2.3 From 317c496f5c1aa25af4144ea04cef4ba6fe420830 Mon Sep 17 00:00:00 2001 From: sanikoyes Date: Tue, 20 Jan 2015 20:01:02 +0800 Subject: Add InputEvent::ACTION get/set support for variant Add action_press/action_release method bind --- core/os/input.cpp | 2 ++ core/variant_op.cpp | 24 ++++++++++++++++++++++++ 2 files changed, 26 insertions(+) (limited to 'core') diff --git a/core/os/input.cpp b/core/os/input.cpp index a827e75896..5d4b3a834d 100644 --- a/core/os/input.cpp +++ b/core/os/input.cpp @@ -62,6 +62,8 @@ void Input::_bind_methods() { ObjectTypeDB::bind_method(_MD("set_mouse_mode","mode"),&Input::set_mouse_mode); ObjectTypeDB::bind_method(_MD("get_mouse_mode"),&Input::get_mouse_mode); ObjectTypeDB::bind_method(_MD("warp_mouse_pos","to"),&Input::warp_mouse_pos); + ObjectTypeDB::bind_method(_MD("action_press"),&Input::action_press); + ObjectTypeDB::bind_method(_MD("action_release"),&Input::action_release); BIND_CONSTANT( MOUSE_MODE_VISIBLE ); BIND_CONSTANT( MOUSE_MODE_HIDDEN ); diff --git a/core/variant_op.cpp b/core/variant_op.cpp index ec43b1275c..fbb5e2631d 100644 --- a/core/variant_op.cpp +++ b/core/variant_op.cpp @@ -1687,6 +1687,19 @@ void Variant::set(const Variant& p_index, const Variant& p_value, bool *r_valid) return; } } + if (ie.type == InputEvent::ACTION) { + + if (str =="action") { + valid=true; + ie.action.action=p_value; + return; + } + else if (str == "pressed") { + valid=true; + ie.action.pressed=p_value; + return; + } + } } break; case DICTIONARY: { @@ -2365,6 +2378,17 @@ Variant Variant::get(const Variant& p_index, bool *r_valid) const { return Vector2(ie.screen_drag.speed_x,ie.screen_drag.speed_y); } } + if (ie.type == InputEvent::ACTION) { + + if (str =="action") { + valid=true; + return ie.action.action; + } + else if (str == "pressed") { + valid=true; + ie.action.pressed; + } + } } break; case DICTIONARY: { -- cgit v1.2.3 From 6306254d37292fa2590799c1fdd08536326465d5 Mon Sep 17 00:00:00 2001 From: "Bil Bas (Spooner)" Date: Sun, 1 Feb 2015 18:42:36 +0000 Subject: Completed implementing standard formatting. --- core/ustring.cpp | 171 ++++++++++++++++++++++++++++++++++++++++++------------- core/ustring.h | 4 +- 2 files changed, 135 insertions(+), 40 deletions(-) (limited to 'core') diff --git a/core/ustring.cpp b/core/ustring.cpp index a7359f112f..222c445b43 100644 --- a/core/ustring.cpp +++ b/core/ustring.cpp @@ -35,7 +35,6 @@ #include "ucaps.h" #include "color.h" #include "variant.h" -#include #define MAX_DIGITS 6 #define UPPERCASE(m_c) (((m_c)>='a' && (m_c)<='z')?((m_c)-('a'-'A')):(m_c)) #define LOWERCASE(m_c) (((m_c)>='A' && (m_c)<='Z')?((m_c)+('a'-'A')):(m_c)) @@ -983,7 +982,7 @@ String String::num(double p_num,int p_decimals) { } -String String::num_int64(int64_t p_num) { +String String::num_int64(int64_t p_num, int base, bool capitalize_hex) { bool sign=p_num<0; int64_t num=ABS(p_num); @@ -992,7 +991,7 @@ String String::num_int64(int64_t p_num) { int chars=0; do { - n/=10; + n/=base; chars++; } while(n); @@ -1004,8 +1003,15 @@ String String::num_int64(int64_t p_num) { c[chars]=0; n=num; do { - c[--chars]='0'+(n%10); - n/=10; + int mod = n%base; + if (mod >= 10) { + char a = (capitalize_hex ? 'A' : 'a'); + c[--chars]=a+(mod - 10); + } else { + c[--chars]='0'+mod; + } + + n/=base; } while(n); if (sign) @@ -3520,41 +3526,84 @@ String rtoss(double p_val) { return String::num_scientific(p_val); } +// Right-pad with a character. +String String::rpad(int min_length, const String& character) const { + String s = *this; + int padding = min_length - s.length(); + if (padding > 0) { + for (int i = 0; i < padding; i++) s = s + character; + } + + return s; +} +// Left-pad with a character. +String String::lpad(int min_length, const String& character) const { + String s = *this; + int padding = min_length - s.length(); + if (padding > 0) { + for (int i = 0; i < padding; i++) s = character + s; + } + + return s; +} + // sprintf is implemented in GDScript via: // "fish %s pie" % "frog" // "fish %s %d pie" % ["frog", 12] -const int FORMAT_BUFFER_SIZE = 1024; -const int OUTPUT_BUFFER_SIZE = 1024 * 100; String String::sprintf(const Array& values) const { String formatted; CharType* self = (CharType*)c_str(); bool in_format = false; int value_index = 0; - char format_format[FORMAT_BUFFER_SIZE] = "%d"; + int min_chars; + int num_decimals; + bool in_decimals; + bool pad_with_zeroes; + bool left_justified; + bool show_sign; for (; *self; self++) { const CharType c = *self; if (in_format) { // We have % - lets see what else we get. switch (c) { - case '%': // Manage %% as % + case '%': { // Replace %% with % formatted += chr(c); in_format = false; break; - + } case 'd': // Integer (signed) case 'o': // Octal case 'x': // Hexadecimal (lowercase) - case 'X': // Hexadecimal (uppercase) + case 'X': { // Hexadecimal (uppercase) if (values[value_index].is_num()) { - char buffer[OUTPUT_BUFFER_SIZE]; - int value = values[value_index]; - format_format[1] = c; - format_format[2] = 0; - ::sprintf(buffer, format_format, value); - - formatted += String(buffer); + int64_t value = values[value_index]; + int base; + bool capitalize = false; + switch (c) { + case 'd': base = 10; break; + case 'o': base = 8; break; + case 'x': base = 16; break; + case 'X': base = 16; capitalize = true; break; + } + // Get basic number. + String str = String::num_int64(value, base, capitalize); + + // Sign. + if (show_sign && value >= 0) { + str = str.insert(0, "+"); + } + + // Padding. + String pad_char = pad_with_zeroes ? String("0") : String(" "); + if (left_justified) { + str = str.rpad(min_chars, pad_char); + } else { + str = str.lpad(min_chars, pad_char); + } + + formatted += str; ++value_index; in_format = false; } else { @@ -3562,14 +3611,28 @@ String String::sprintf(const Array& values) const { } break; - - case 'f': // Float + } + case 'f': { // Float if (values[value_index].is_num()) { - char buffer[OUTPUT_BUFFER_SIZE]; double value = values[value_index]; - ::sprintf(buffer, "%f", value); + String str = String::num(value, num_decimals); + + // Pad decimals out. + str = str.pad_decimals(num_decimals); + + // Show sign + if (show_sign && value >= 0) { + str = str.insert(0, "+"); + } + + // Padding + if (left_justified) { + str = str.rpad(min_chars); + } else { + str = str.lpad(min_chars); + } - formatted += String(buffer); + formatted += str; ++value_index; in_format = false; } else { @@ -3577,26 +3640,49 @@ String String::sprintf(const Array& values) const { } break; + } + case 's': { // String + String str = values[value_index]; + // Padding. + if (left_justified) { + str = str.rpad(min_chars); + } else { + str = str.lpad(min_chars); + } - case 's': // String - String value = values[value_index]; - formatted += value; + formatted += str; ++value_index; in_format = false; break; - - // case '-': // Left justify - // break; - - // case '+': // Show + if positive. - // break; - - // case '0': case '1': case '2': case '3': case '4': - // case '5': case '6': case '7': case '8': case '9': - // break; - - // case '.': // Float separtor. - // break; + } + case '-': { // Left justify + left_justified = true; + break; + } + case '+': { // Show + if positive. + show_sign = true; + break; + } + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': { + int n = c - '0'; + if (in_decimals) { + num_decimals *= 10; + num_decimals += n; + } else { + if (c == '0' && min_chars == 0) { + pad_with_zeroes = true; + } else { + min_chars *= 10; + min_chars += n; + } + } + break; + } + case '.': // Float separtor. + in_decimals = true; + num_decimals = 0; // We want to add the value manually. + break; // case '*': // Dyanmic width, based on value. // break; @@ -3608,6 +3694,13 @@ String String::sprintf(const Array& values) const { switch (c) { case '%': in_format = true; + // Back to defaults: + min_chars = 0; + num_decimals = 6; + pad_with_zeroes = false; + left_justified = false; + show_sign = false; + in_decimals = false; break; default: formatted += chr(c); diff --git a/core/ustring.h b/core/ustring.h index ccbbf5e5d2..af5ffb7c35 100644 --- a/core/ustring.h +++ b/core/ustring.h @@ -128,11 +128,13 @@ public: String insert(int p_at_pos,String p_string) const; String pad_decimals(int p_digits) const; String pad_zeros(int p_digits) const; + String lpad(int min_length,const String& character=" ") const; + String rpad(int min_length,const String& character=" ") const; String sprintf(const Array& values) const; static String num(double p_num,int p_decimals=-1); static String num_scientific(double p_num); static String num_real(double p_num); - static String num_int64(int64_t p_num); + static String num_int64(int64_t p_num,int base=10,bool capitalize_hex=false); static String chr(CharType p_char); static String md5(const uint8_t *p_md5); bool is_numeric() const; -- cgit v1.2.3 From af7c8bdf236b7c572bc33a44e3bb64fecdaa99d9 Mon Sep 17 00:00:00 2001 From: "Bil Bas (Spooner)" Date: Sun, 1 Feb 2015 20:18:38 +0000 Subject: Completed more complex formatting. --- core/ustring.cpp | 211 ++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 154 insertions(+), 57 deletions(-) (limited to 'core') diff --git a/core/ustring.cpp b/core/ustring.cpp index 222c445b43..476ab3f936 100644 --- a/core/ustring.cpp +++ b/core/ustring.cpp @@ -3554,15 +3554,17 @@ String String::sprintf(const Array& values) const { String formatted; CharType* self = (CharType*)c_str(); + int num_items = values.size(); bool in_format = false; int value_index = 0; int min_chars; - int num_decimals; + int min_decimals; bool in_decimals; bool pad_with_zeroes; bool left_justified; bool show_sign; + for (; *self; self++) { const CharType c = *self; @@ -3577,71 +3579,88 @@ String String::sprintf(const Array& values) const { case 'o': // Octal case 'x': // Hexadecimal (lowercase) case 'X': { // Hexadecimal (uppercase) - if (values[value_index].is_num()) { - int64_t value = values[value_index]; - int base; - bool capitalize = false; - switch (c) { - case 'd': base = 10; break; - case 'o': base = 8; break; - case 'x': base = 16; break; - case 'X': base = 16; capitalize = true; break; - } - // Get basic number. - String str = String::num_int64(value, base, capitalize); + if (value_index >= values.size()) { + ERR_EXPLAIN("not enough arguments for format string"); + ERR_FAIL_V(""); + } - // Sign. - if (show_sign && value >= 0) { - str = str.insert(0, "+"); - } + if (!values[value_index].is_num()) { + ERR_EXPLAIN("a number is required"); + ERR_FAIL_V(""); + } + + int64_t value = values[value_index]; + int base; + bool capitalize = false; + switch (c) { + case 'd': base = 10; break; + case 'o': base = 8; break; + case 'x': base = 16; break; + case 'X': base = 16; capitalize = true; break; + } + // Get basic number. + String str = String::num_int64(value, base, capitalize); - // Padding. - String pad_char = pad_with_zeroes ? String("0") : String(" "); - if (left_justified) { - str = str.rpad(min_chars, pad_char); - } else { - str = str.lpad(min_chars, pad_char); - } + // Sign. + if (show_sign && value >= 0) { + str = str.insert(0, "+"); + } - formatted += str; - ++value_index; - in_format = false; + // Padding. + String pad_char = pad_with_zeroes ? String("0") : String(" "); + if (left_justified) { + str = str.rpad(min_chars, pad_char); } else { - // TODO: Error? + str = str.lpad(min_chars, pad_char); } - + + formatted += str; + ++value_index; + in_format = false; + break; } case 'f': { // Float - if (values[value_index].is_num()) { - double value = values[value_index]; - String str = String::num(value, num_decimals); + if (value_index >= values.size()) { + ERR_EXPLAIN("not enough arguments for format string"); + ERR_FAIL_V(""); + } - // Pad decimals out. - str = str.pad_decimals(num_decimals); + if (!values[value_index].is_num()) { + ERR_EXPLAIN("a number is required"); + ERR_FAIL_V(""); + } - // Show sign - if (show_sign && value >= 0) { - str = str.insert(0, "+"); - } + double value = values[value_index]; + String str = String::num(value, min_decimals); - // Padding - if (left_justified) { - str = str.rpad(min_chars); - } else { - str = str.lpad(min_chars); - } + // Pad decimals out. + str = str.pad_decimals(min_decimals); + + // Show sign + if (show_sign && value >= 0) { + str = str.insert(0, "+"); + } - formatted += str; - ++value_index; - in_format = false; + // Padding + if (left_justified) { + str = str.rpad(min_chars); } else { - // TODO: Error? + str = str.lpad(min_chars); } + + formatted += str; + ++value_index; + in_format = false; break; } case 's': { // String + if (value_index >= values.size()) { + ERR_EXPLAIN("not enough arguments for format string"); + ERR_FAIL_V(""); + } + String str = values[value_index]; // Padding. if (left_justified) { @@ -3655,6 +3674,47 @@ String String::sprintf(const Array& values) const { in_format = false; break; } + case 'c': { + if (value_index >= values.size()) { + ERR_EXPLAIN("not enough arguments for format string"); + ERR_FAIL_V(""); + } + + // Convert to character. + String str; + if (values[value_index].is_num()) { + int value = values[value_index]; + if (value < 0) { + ERR_EXPLAIN("unsigned byte integer is lower than maximum") + ERR_FAIL_V(""); + } else if (value > 255) { + ERR_EXPLAIN("unsigned byte integer is greater than maximum") + ERR_FAIL_V(""); + } + str = chr(values[value_index]); + } else if (values[value_index].get_type() == Variant::STRING) { + str = values[value_index]; + if (str.length() != 1) { + ERR_EXPLAIN("%c requires number or single-character string"); + ERR_FAIL_V(""); + } + } else { + ERR_EXPLAIN("%c requires number or single-character string"); + ERR_FAIL_V(""); + } + + // Padding. + if (left_justified) { + str = str.rpad(min_chars); + } else { + str = str.lpad(min_chars); + } + + formatted += str; + ++value_index; + in_format = false; + break; + } case '-': { // Left justify left_justified = true; break; @@ -3667,8 +3727,8 @@ String String::sprintf(const Array& values) const { case '5': case '6': case '7': case '8': case '9': { int n = c - '0'; if (in_decimals) { - num_decimals *= 10; - num_decimals += n; + min_decimals *= 10; + min_decimals += n; } else { if (c == '0' && min_chars == 0) { pad_with_zeroes = true; @@ -3679,16 +3739,43 @@ String String::sprintf(const Array& values) const { } break; } - case '.': // Float separtor. + case '.': { // Float separtor. + if (in_decimals) { + ERR_EXPLAIN("too many decimal points in format"); + ERR_FAIL_V(""); + } in_decimals = true; - num_decimals = 0; // We want to add the value manually. + min_decimals = 0; // We want to add the value manually. break; + } + + case '*': { // Dyanmic width, based on value. + if (value_index >= values.size()) { + ERR_EXPLAIN("not enough arguments for format string"); + ERR_FAIL_V(""); + } + + if (!values[value_index].is_num()) { + ERR_EXPLAIN("* wants number"); + ERR_FAIL_V(""); + } + + int size = values[value_index]; + + if (in_decimals) { + min_decimals = size; + } else { + min_chars = size; + } - // case '*': // Dyanmic width, based on value. - // break; + ++value_index; + break; + } - //default: - // TODO: error? + default: { + ERR_EXPLAIN("unsupported format character"); + ERR_FAIL_V(""); + } } } else { // Not in format string. switch (c) { @@ -3696,7 +3783,7 @@ String String::sprintf(const Array& values) const { in_format = true; // Back to defaults: min_chars = 0; - num_decimals = 6; + min_decimals = 6; pad_with_zeroes = false; left_justified = false; show_sign = false; @@ -3708,5 +3795,15 @@ String String::sprintf(const Array& values) const { } } + if (in_format) { + ERR_EXPLAIN("incomplete format"); + ERR_FAIL_V(""); + } + + if (value_index != values.size()) { + ERR_EXPLAIN("not all arguments converted during string formatting"); + ERR_FAIL_V(""); + } + return formatted; } -- cgit v1.2.3 From 84be16758e1816307a47f9cfacca40eea6446f6a Mon Sep 17 00:00:00 2001 From: Jeffrey Steward Date: Tue, 10 Feb 2015 14:22:05 -0700 Subject: Added the default arguments to the binding for ResourceImportMetadata::add_source to match the c++ version --- core/resource.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'core') diff --git a/core/resource.cpp b/core/resource.cpp index 987bd772b0..560ca9a1f2 100644 --- a/core/resource.cpp +++ b/core/resource.cpp @@ -130,7 +130,7 @@ void ResourceImportMetadata::_bind_methods() { ObjectTypeDB::bind_method(_MD("set_editor","name"),&ResourceImportMetadata::set_editor); ObjectTypeDB::bind_method(_MD("get_editor"),&ResourceImportMetadata::get_editor); - ObjectTypeDB::bind_method(_MD("add_source","path","md5"),&ResourceImportMetadata::add_source); + ObjectTypeDB::bind_method(_MD("add_source","path","md5"),&ResourceImportMetadata::add_source, ""); ObjectTypeDB::bind_method(_MD("get_source_path","idx"),&ResourceImportMetadata::get_source_path); ObjectTypeDB::bind_method(_MD("get_source_md5","idx"),&ResourceImportMetadata::get_source_md5); ObjectTypeDB::bind_method(_MD("remove_source","idx"),&ResourceImportMetadata::remove_source); -- cgit v1.2.3 From 78a268c2eb3099103164407761e06afa0c6339d4 Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Wed, 11 Feb 2015 07:57:39 -0300 Subject: fixes to HTTPClient -small unchunked files should work properly -blocking mode should work properly --- core/io/http_client.cpp | 43 ++++++++++++++++++++++++++++++++++--------- core/io/http_client.h | 6 +++++- 2 files changed, 39 insertions(+), 10 deletions(-) (limited to 'core') diff --git a/core/io/http_client.cpp b/core/io/http_client.cpp index faead675d4..c7906018e9 100644 --- a/core/io/http_client.cpp +++ b/core/io/http_client.cpp @@ -273,7 +273,7 @@ Error HTTPClient::poll(){ while(true) { uint8_t byte; int rec=0; - Error err = connection->get_partial_data(&byte,1,rec); + Error err = _get_http_data(&byte,1,rec); if (err!=OK) { close(); status=STATUS_CONNECTION_ERROR; @@ -417,7 +417,7 @@ ByteArray HTTPClient::read_response_body_chunk() { //reading len uint8_t b; int rec=0; - err = connection->get_partial_data(&b,1,rec); + err = _get_http_data(&b,1,rec); if (rec==0) break; @@ -471,7 +471,7 @@ ByteArray HTTPClient::read_response_body_chunk() { } else { int rec=0; - err = connection->get_partial_data(&chunk[chunk.size()-chunk_left],chunk_left,rec); + err = _get_http_data(&chunk[chunk.size()-chunk_left],chunk_left,rec); if (rec==0) { break; } @@ -502,18 +502,23 @@ ByteArray HTTPClient::read_response_body_chunk() { } } else { + + int to_read = MIN(body_left,read_chunk_size); ByteArray ret; - ret.resize(MAX(body_left,tmp_read.size())); + ret.resize(to_read); ByteArray::Write w = ret.write(); int _offset = 0; - while (body_left > 0) { - ByteArray::Write r = tmp_read.write(); + while (to_read > 0) { int rec=0; - err = connection->get_partial_data(r.ptr(),MIN(body_left,tmp_read.size()),rec); + err = _get_http_data(w.ptr()+_offset,to_read,rec); if (rec>0) { - copymem(w.ptr()+_offset,r.ptr(),rec); body_left-=rec; + to_read-=rec; _offset += rec; + } else { + if (to_read>0) //ended up reading less + ret.resize(_offset); + break; } } if (body_left==0) { @@ -557,6 +562,20 @@ bool HTTPClient::is_blocking_mode_enabled() const{ return blocking; } +Error HTTPClient::_get_http_data(uint8_t* p_buffer, int p_bytes,int &r_received) { + + if (blocking) { + + Error err = connection->get_data(p_buffer,p_bytes); + if (err==OK) + r_received=p_bytes; + else + r_received=0; + return err; + } else { + return connection->get_partial_data(p_buffer,p_bytes,r_received); + } +} void HTTPClient::_bind_methods() { @@ -574,6 +593,7 @@ void HTTPClient::_bind_methods() { ObjectTypeDB::bind_method(_MD("get_response_headers_as_dictionary"),&HTTPClient::_get_response_headers_as_dictionary); ObjectTypeDB::bind_method(_MD("get_response_body_length"),&HTTPClient::get_response_body_length); ObjectTypeDB::bind_method(_MD("read_response_body_chunk"),&HTTPClient::read_response_body_chunk); + ObjectTypeDB::bind_method(_MD("set_read_chunk_size","bytes"),&HTTPClient::set_read_chunk_size); ObjectTypeDB::bind_method(_MD("set_blocking_mode","enabled"),&HTTPClient::set_blocking_mode); ObjectTypeDB::bind_method(_MD("is_blocking_mode_enabled"),&HTTPClient::is_blocking_mode_enabled); @@ -664,6 +684,11 @@ void HTTPClient::_bind_methods() { } +void HTTPClient::set_read_chunk_size(int p_size) { + ERR_FAIL_COND(p_size<256 || p_size>(1<<24)); + read_chunk_size=p_size; +} + HTTPClient::HTTPClient(){ tcp_connection = StreamPeerTCP::create_ref(); @@ -677,7 +702,7 @@ HTTPClient::HTTPClient(){ response_num=0; ssl=false; blocking=false; - tmp_read.resize(4096); + read_chunk_size=4096; } HTTPClient::~HTTPClient(){ diff --git a/core/io/http_client.h b/core/io/http_client.h index 09ad64f48a..d0ebaa4596 100644 --- a/core/io/http_client.h +++ b/core/io/http_client.h @@ -157,7 +157,10 @@ private: static void _bind_methods(); StringArray _get_response_headers(); Dictionary _get_response_headers_as_dictionary(); - ByteArray tmp_read; + int read_chunk_size; + + Error _get_http_data(uint8_t* p_buffer, int p_bytes,int &r_received); + public: @@ -185,6 +188,7 @@ public: void set_blocking_mode(bool p_enable); //useful mostly if running in a thread bool is_blocking_mode_enabled() const; + void set_read_chunk_size(int p_size); Error poll(); -- cgit v1.2.3 From c5f509f238576dba39ffcce74ab2066f24e67b58 Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Sat, 14 Feb 2015 12:09:52 -0300 Subject: New Navigation & Pathfinding support for 2D -Added Navigation & NavigationPolygon nodes -Added corresponding visual editor -New pathfinding algorithm is modern and fast! -Similar API to 3D Pathfinding (more coherent) --- core/bind/core_bind.cpp | 7 + core/bind/core_bind.h | 2 + core/dvector.h | 17 + core/math/geometry.h | 14 + core/math/triangulator.cpp | 1543 ++++++++++++++++++++++++++++++++++++++++++++ core/math/triangulator.h | 309 +++++++++ 6 files changed, 1892 insertions(+) create mode 100644 core/math/triangulator.cpp create mode 100644 core/math/triangulator.h (limited to 'core') diff --git a/core/bind/core_bind.cpp b/core/bind/core_bind.cpp index 0c5d21b4f6..a03fd7fe4a 100644 --- a/core/bind/core_bind.cpp +++ b/core/bind/core_bind.cpp @@ -838,6 +838,12 @@ Variant _Geometry::segment_intersects_triangle( const Vector3& p_from, const Vec return Variant(); } + +bool _Geometry::point_is_inside_triangle(const Vector2& s, const Vector2& a, const Vector2& b, const Vector2& c) const { + + return Geometry::is_point_in_triangle(s,a,b,c); +} + DVector _Geometry::segment_intersects_sphere( const Vector3& p_from, const Vector3& p_to, const Vector3& p_sphere_pos,real_t p_sphere_radius) { DVector r; @@ -938,6 +944,7 @@ void _Geometry::_bind_methods() { ObjectTypeDB::bind_method(_MD("segment_intersects_sphere","from","to","spos","sradius"),&_Geometry::segment_intersects_sphere); ObjectTypeDB::bind_method(_MD("segment_intersects_cylinder","from","to","height","radius"),&_Geometry::segment_intersects_cylinder); ObjectTypeDB::bind_method(_MD("segment_intersects_convex","from","to","planes"),&_Geometry::segment_intersects_convex); + ObjectTypeDB::bind_method(_MD("point_is_inside_triangle","point","a","b","c"),&_Geometry::point_is_inside_triangle); ObjectTypeDB::bind_method(_MD("triangulate_polygon","polygon"),&_Geometry::triangulate_polygon); diff --git a/core/bind/core_bind.h b/core/bind/core_bind.h index 12a4ae86eb..f5043ba71f 100644 --- a/core/bind/core_bind.h +++ b/core/bind/core_bind.h @@ -248,6 +248,8 @@ public: Vector3 get_closest_point_to_segment(const Vector3& p_point, const Vector3& p_a,const Vector3& p_b); Variant ray_intersects_triangle( const Vector3& p_from, const Vector3& p_dir, const Vector3& p_v0,const Vector3& p_v1,const Vector3& p_v2); Variant segment_intersects_triangle( const Vector3& p_from, const Vector3& p_to, const Vector3& p_v0,const Vector3& p_v1,const Vector3& p_v2); + bool point_is_inside_triangle(const Vector2& s, const Vector2& a, const Vector2& b, const Vector2& c) const; + DVector segment_intersects_sphere( const Vector3& p_from, const Vector3& p_to, const Vector3& p_sphere_pos,real_t p_sphere_radius); DVector segment_intersects_cylinder( const Vector3& p_from, const Vector3& p_to, float p_height,float p_radius); DVector segment_intersects_convex(const Vector3& p_from, const Vector3& p_to,const Vector& p_planes); diff --git a/core/dvector.h b/core/dvector.h index 72661882cd..29be417844 100644 --- a/core/dvector.h +++ b/core/dvector.h @@ -262,6 +262,23 @@ public: w[bs+i]=r[i]; } + + Error insert(int p_pos,const T& p_val) { + + int s=size(); + ERR_FAIL_INDEX_V(p_pos,s+1,ERR_INVALID_PARAMETER); + resize(s+1); + { + Write w = write(); + for (int i=s;i>p_pos;i--) + w[i]=w[i-1]; + w[p_pos]=p_val; + } + + return OK; + } + + bool is_locked() const { return mem.is_locked(); } inline const T operator[](int p_index) const; diff --git a/core/math/geometry.h b/core/math/geometry.h index 81530e30c0..7e0cc01a22 100644 --- a/core/math/geometry.h +++ b/core/math/geometry.h @@ -511,6 +511,20 @@ public: else return p_segment[0]+n*d; // inside } + + static bool is_point_in_triangle(const Vector2& s, const Vector2& a, const Vector2& b, const Vector2& c) + { + int as_x = s.x-a.x; + int as_y = s.y-a.y; + + bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0; + + if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false; + + if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false; + + return true; + } static Vector2 get_closest_point_to_segment_uncapped_2d(const Vector2& p_point, const Vector2 *p_segment) { Vector2 p=p_point-p_segment[0]; diff --git a/core/math/triangulator.cpp b/core/math/triangulator.cpp new file mode 100644 index 0000000000..6be1cdb330 --- /dev/null +++ b/core/math/triangulator.cpp @@ -0,0 +1,1543 @@ +//Copyright (C) 2011 by Ivan Fratric +// +//Permission is hereby granted, free of charge, to any person obtaining a copy +//of this software and associated documentation files (the "Software"), to deal +//in the Software without restriction, including without limitation the rights +//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +//copies of the Software, and to permit persons to whom the Software is +//furnished to do so, subject to the following conditions: +// +//The above copyright notice and this permission notice shall be included in +//all copies or substantial portions of the Software. +// +//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +//THE SOFTWARE. + + +#include +#include +#include +#include +#include "triangulator.h" +using namespace std; + +#define TRIANGULATOR_VERTEXTYPE_REGULAR 0 +#define TRIANGULATOR_VERTEXTYPE_START 1 +#define TRIANGULATOR_VERTEXTYPE_END 2 +#define TRIANGULATOR_VERTEXTYPE_SPLIT 3 +#define TRIANGULATOR_VERTEXTYPE_MERGE 4 + +TriangulatorPoly::TriangulatorPoly() { + hole = false; + numpoints = 0; + points = NULL; +} + +TriangulatorPoly::~TriangulatorPoly() { + if(points) delete [] points; +} + +void TriangulatorPoly::Clear() { + if(points) delete [] points; + hole = false; + numpoints = 0; + points = NULL; +} + +void TriangulatorPoly::Init(long numpoints) { + Clear(); + this->numpoints = numpoints; + points = new Vector2[numpoints]; +} + +void TriangulatorPoly::Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3) { + Init(3); + points[0] = p1; + points[1] = p2; + points[2] = p3; +} + +TriangulatorPoly::TriangulatorPoly(const TriangulatorPoly &src) { + hole = src.hole; + numpoints = src.numpoints; + points = new Vector2[numpoints]; + memcpy(points, src.points, numpoints*sizeof(Vector2)); +} + +TriangulatorPoly& TriangulatorPoly::operator=(const TriangulatorPoly &src) { + Clear(); + hole = src.hole; + numpoints = src.numpoints; + points = new Vector2[numpoints]; + memcpy(points, src.points, numpoints*sizeof(Vector2)); + return *this; +} + +int TriangulatorPoly::GetOrientation() { + long i1,i2; + real_t area = 0; + for(i1=0; i10) return TRIANGULATOR_CCW; + if(area<0) return TRIANGULATOR_CW; + return 0; +} + +void TriangulatorPoly::SetOrientation(int orientation) { + int polyorientation = GetOrientation(); + if(polyorientation&&(polyorientation!=orientation)) { + Invert(); + } +} + +void TriangulatorPoly::Invert() { + long i; + Vector2 *invpoints; + + invpoints = new Vector2[numpoints]; + for(i=0;i0) return 0; + if(dot21*dot22>0) return 0; + + return 1; +} + +//removes holes from inpolys by merging them with non-holes +int TriangulatorPartition::RemoveHoles(list *inpolys, list *outpolys) { + list polys; + list::iterator holeiter,polyiter,iter,iter2; + long i,i2,holepointindex,polypointindex; + Vector2 holepoint,polypoint,bestpolypoint; + Vector2 linep1,linep2; + Vector2 v1,v2; + TriangulatorPoly newpoly; + bool hasholes; + bool pointvisible; + bool pointfound; + + //check for trivial case (no holes) + hasholes = false; + for(iter = inpolys->begin(); iter!=inpolys->end(); iter++) { + if(iter->IsHole()) { + hasholes = true; + break; + } + } + if(!hasholes) { + for(iter = inpolys->begin(); iter!=inpolys->end(); iter++) { + outpolys->push_back(*iter); + } + return 1; + } + + polys = *inpolys; + + while(1) { + //find the hole point with the largest x + hasholes = false; + for(iter = polys.begin(); iter!=polys.end(); iter++) { + if(!iter->IsHole()) continue; + + if(!hasholes) { + hasholes = true; + holeiter = iter; + holepointindex = 0; + } + + for(i=0; i < iter->GetNumPoints(); i++) { + if(iter->GetPoint(i).x > holeiter->GetPoint(holepointindex).x) { + holeiter = iter; + holepointindex = i; + } + } + } + if(!hasholes) break; + holepoint = holeiter->GetPoint(holepointindex); + + pointfound = false; + for(iter = polys.begin(); iter!=polys.end(); iter++) { + if(iter->IsHole()) continue; + for(i=0; i < iter->GetNumPoints(); i++) { + if(iter->GetPoint(i).x <= holepoint.x) continue; + if(!InCone(iter->GetPoint((i+iter->GetNumPoints()-1)%(iter->GetNumPoints())), + iter->GetPoint(i), + iter->GetPoint((i+1)%(iter->GetNumPoints())), + holepoint)) + continue; + polypoint = iter->GetPoint(i); + if(pointfound) { + v1 = Normalize(polypoint-holepoint); + v2 = Normalize(bestpolypoint-holepoint); + if(v2.x > v1.x) continue; + } + pointvisible = true; + for(iter2 = polys.begin(); iter2!=polys.end(); iter2++) { + if(iter2->IsHole()) continue; + for(i2=0; i2 < iter2->GetNumPoints(); i2++) { + linep1 = iter2->GetPoint(i2); + linep2 = iter2->GetPoint((i2+1)%(iter2->GetNumPoints())); + if(Intersects(holepoint,polypoint,linep1,linep2)) { + pointvisible = false; + break; + } + } + if(!pointvisible) break; + } + if(pointvisible) { + pointfound = true; + bestpolypoint = polypoint; + polyiter = iter; + polypointindex = i; + } + } + } + + if(!pointfound) return 0; + + newpoly.Init(holeiter->GetNumPoints() + polyiter->GetNumPoints() + 2); + i2 = 0; + for(i=0;i<=polypointindex;i++) { + newpoly[i2] = polyiter->GetPoint(i); + i2++; + } + for(i=0;i<=holeiter->GetNumPoints();i++) { + newpoly[i2] = holeiter->GetPoint((i+holepointindex)%holeiter->GetNumPoints()); + i2++; + } + for(i=polypointindex;iGetNumPoints();i++) { + newpoly[i2] = polyiter->GetPoint(i); + i2++; + } + + polys.erase(holeiter); + polys.erase(polyiter); + polys.push_back(newpoly); + } + + for(iter = polys.begin(); iter!=polys.end(); iter++) { + outpolys->push_back(*iter); + } + + return 1; +} + +bool TriangulatorPartition::IsConvex(Vector2& p1, Vector2& p2, Vector2& p3) { + real_t tmp; + tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); + if(tmp>0) return 1; + else return 0; +} + +bool TriangulatorPartition::IsReflex(Vector2& p1, Vector2& p2, Vector2& p3) { + real_t tmp; + tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); + if(tmp<0) return 1; + else return 0; +} + +bool TriangulatorPartition::IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p) { + if(IsConvex(p1,p,p2)) return false; + if(IsConvex(p2,p,p3)) return false; + if(IsConvex(p3,p,p1)) return false; + return true; +} + +bool TriangulatorPartition::InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p) { + bool convex; + + convex = IsConvex(p1,p2,p3); + + if(convex) { + if(!IsConvex(p1,p2,p)) return false; + if(!IsConvex(p2,p3,p)) return false; + return true; + } else { + if(IsConvex(p1,p2,p)) return true; + if(IsConvex(p2,p3,p)) return true; + return false; + } +} + +bool TriangulatorPartition::InCone(PartitionVertex *v, Vector2 &p) { + Vector2 p1,p2,p3; + + p1 = v->previous->p; + p2 = v->p; + p3 = v->next->p; + + return InCone(p1,p2,p3,p); +} + +void TriangulatorPartition::UpdateVertexReflexity(PartitionVertex *v) { + PartitionVertex *v1,*v3; + v1 = v->previous; + v3 = v->next; + v->isConvex = !IsReflex(v1->p,v->p,v3->p); +} + +void TriangulatorPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) { + long i; + PartitionVertex *v1,*v3; + Vector2 vec1,vec3; + + v1 = v->previous; + v3 = v->next; + + v->isConvex = IsConvex(v1->p,v->p,v3->p); + + vec1 = Normalize(v1->p - v->p); + vec3 = Normalize(v3->p - v->p); + v->angle = vec1.x*vec3.x + vec1.y*vec3.y; + + if(v->isConvex) { + v->isEar = true; + for(i=0;ip.x)&&(vertices[i].p.y==v->p.y)) continue; + if((vertices[i].p.x==v1->p.x)&&(vertices[i].p.y==v1->p.y)) continue; + if((vertices[i].p.x==v3->p.x)&&(vertices[i].p.y==v3->p.y)) continue; + if(IsInside(v1->p,v->p,v3->p,vertices[i].p)) { + v->isEar = false; + break; + } + } + } else { + v->isEar = false; + } +} + +//triangulation by ear removal +int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, list *triangles) { + long numvertices; + PartitionVertex *vertices; + PartitionVertex *ear; + TriangulatorPoly triangle; + long i,j; + bool earfound; + + if(poly->GetNumPoints() < 3) return 0; + if(poly->GetNumPoints() == 3) { + triangles->push_back(*poly); + return 1; + } + + numvertices = poly->GetNumPoints(); + + vertices = new PartitionVertex[numvertices]; + for(i=0;iGetPoint(i); + if(i==(numvertices-1)) vertices[i].next=&(vertices[0]); + else vertices[i].next=&(vertices[i+1]); + if(i==0) vertices[i].previous = &(vertices[numvertices-1]); + else vertices[i].previous = &(vertices[i-1]); + } + for(i=0;i ear->angle) { + ear = &(vertices[j]); + } + } + } + if(!earfound) { + delete [] vertices; + return 0; + } + + triangle.Triangle(ear->previous->p,ear->p,ear->next->p); + triangles->push_back(triangle); + + ear->isActive = false; + ear->previous->next = ear->next; + ear->next->previous = ear->previous; + + if(i==numvertices-4) break; + + UpdateVertex(ear->previous,vertices,numvertices); + UpdateVertex(ear->next,vertices,numvertices); + } + for(i=0;ip,vertices[i].p,vertices[i].next->p); + triangles->push_back(triangle); + break; + } + } + + delete [] vertices; + + return 1; +} + +int TriangulatorPartition::Triangulate_EC(list *inpolys, list *triangles) { + list outpolys; + list::iterator iter; + + if(!RemoveHoles(inpolys,&outpolys)) return 0; + for(iter=outpolys.begin();iter!=outpolys.end();iter++) { + if(!Triangulate_EC(&(*iter),triangles)) return 0; + } + return 1; +} + +int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, list *parts) { + list triangles; + list::iterator iter1,iter2; + TriangulatorPoly *poly1,*poly2; + TriangulatorPoly newpoly; + Vector2 d1,d2,p1,p2,p3; + long i11,i12,i21,i22,i13,i23,j,k; + bool isdiagonal; + long numreflex; + + //check if the poly is already convex + numreflex = 0; + for(i11=0;i11GetNumPoints();i11++) { + if(i11==0) i12 = poly->GetNumPoints()-1; + else i12=i11-1; + if(i11==(poly->GetNumPoints()-1)) i13=0; + else i13=i11+1; + if(IsReflex(poly->GetPoint(i12),poly->GetPoint(i11),poly->GetPoint(i13))) { + numreflex = 1; + break; + } + } + if(numreflex == 0) { + parts->push_back(*poly); + return 1; + } + + if(!Triangulate_EC(poly,&triangles)) return 0; + + for(iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) { + poly1 = &(*iter1); + for(i11=0;i11GetNumPoints();i11++) { + d1 = poly1->GetPoint(i11); + i12 = (i11+1)%(poly1->GetNumPoints()); + d2 = poly1->GetPoint(i12); + + isdiagonal = false; + for(iter2 = iter1; iter2 != triangles.end(); iter2++) { + if(iter1 == iter2) continue; + poly2 = &(*iter2); + + for(i21=0;i21GetNumPoints();i21++) { + if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue; + i22 = (i21+1)%(poly2->GetNumPoints()); + if((d1.x != poly2->GetPoint(i22).x)||(d1.y != poly2->GetPoint(i22).y)) continue; + isdiagonal = true; + break; + } + if(isdiagonal) break; + } + + if(!isdiagonal) continue; + + p2 = poly1->GetPoint(i11); + if(i11 == 0) i13 = poly1->GetNumPoints()-1; + else i13 = i11-1; + p1 = poly1->GetPoint(i13); + if(i22 == (poly2->GetNumPoints()-1)) i23 = 0; + else i23 = i22+1; + p3 = poly2->GetPoint(i23); + + if(!IsConvex(p1,p2,p3)) continue; + + p2 = poly1->GetPoint(i12); + if(i12 == (poly1->GetNumPoints()-1)) i13 = 0; + else i13 = i12+1; + p3 = poly1->GetPoint(i13); + if(i21 == 0) i23 = poly2->GetNumPoints()-1; + else i23 = i21-1; + p1 = poly2->GetPoint(i23); + + if(!IsConvex(p1,p2,p3)) continue; + + newpoly.Init(poly1->GetNumPoints()+poly2->GetNumPoints()-2); + k = 0; + for(j=i12;j!=i11;j=(j+1)%(poly1->GetNumPoints())) { + newpoly[k] = poly1->GetPoint(j); + k++; + } + for(j=i22;j!=i21;j=(j+1)%(poly2->GetNumPoints())) { + newpoly[k] = poly2->GetPoint(j); + k++; + } + + triangles.erase(iter2); + *iter1 = newpoly; + poly1 = &(*iter1); + i11 = -1; + + continue; + } + } + + for(iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) { + parts->push_back(*iter1); + } + + return 1; +} + +int TriangulatorPartition::ConvexPartition_HM(list *inpolys, list *parts) { + list outpolys; + list::iterator iter; + + if(!RemoveHoles(inpolys,&outpolys)) return 0; + for(iter=outpolys.begin();iter!=outpolys.end();iter++) { + if(!ConvexPartition_HM(&(*iter),parts)) return 0; + } + return 1; +} + +//minimum-weight polygon triangulation by dynamic programming +//O(n^3) time complexity +//O(n^2) space complexity +int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, list *triangles) { + long i,j,k,gap,n; + DPState **dpstates; + Vector2 p1,p2,p3,p4; + long bestvertex; + real_t weight,minweight,d1,d2; + Diagonal diagonal,newdiagonal; + list diagonals; + TriangulatorPoly triangle; + int ret = 1; + + n = poly->GetNumPoints(); + dpstates = new DPState *[n]; + for(i=1;iGetPoint(i); + for(j=i+1;jGetPoint(j); + + //visibility check + if(i==0) p3 = poly->GetPoint(n-1); + else p3 = poly->GetPoint(i-1); + if(i==(n-1)) p4 = poly->GetPoint(0); + else p4 = poly->GetPoint(i+1); + if(!InCone(p3,p1,p4,p2)) { + dpstates[j][i].visible = false; + continue; + } + + if(j==0) p3 = poly->GetPoint(n-1); + else p3 = poly->GetPoint(j-1); + if(j==(n-1)) p4 = poly->GetPoint(0); + else p4 = poly->GetPoint(j+1); + if(!InCone(p3,p2,p4,p1)) { + dpstates[j][i].visible = false; + continue; + } + + for(k=0;kGetPoint(k); + if(k==(n-1)) p4 = poly->GetPoint(0); + else p4 = poly->GetPoint(k+1); + if(Intersects(p1,p2,p3,p4)) { + dpstates[j][i].visible = false; + break; + } + } + } + } + } + dpstates[n-1][0].visible = true; + dpstates[n-1][0].weight = 0; + dpstates[n-1][0].bestvertex = -1; + + for(gap = 2; gapGetPoint(i),poly->GetPoint(k)); + if(j<=(k+1)) d2=0; + else d2 = Distance(poly->GetPoint(k),poly->GetPoint(j)); + + weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2; + + if((bestvertex == -1)||(weightGetPoint(diagonal.index1),poly->GetPoint(bestvertex),poly->GetPoint(diagonal.index2)); + triangles->push_back(triangle); + if(bestvertex > (diagonal.index1+1)) { + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = bestvertex; + diagonals.push_back(newdiagonal); + } + if(diagonal.index2 > (bestvertex+1)) { + newdiagonal.index1 = bestvertex; + newdiagonal.index2 = diagonal.index2; + diagonals.push_back(newdiagonal); + } + } + + for(i=1;i *pairs; + long w2; + + w2 = dpstates[a][b].weight; + if(w>w2) return; + + pairs = &(dpstates[a][b].pairs); + newdiagonal.index1 = i; + newdiagonal.index2 = j; + + if(wclear(); + pairs->push_front(newdiagonal); + dpstates[a][b].weight = w; + } else { + if((!pairs->empty())&&(i <= pairs->begin()->index1)) return; + while((!pairs->empty())&&(pairs->begin()->index2 >= j)) pairs->pop_front(); + pairs->push_front(newdiagonal); + } +} + +void TriangulatorPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { + list *pairs; + list::iterator iter,lastiter; + long top; + long w; + + if(!dpstates[i][j].visible) return; + top = j; + w = dpstates[i][j].weight; + if(k-j > 1) { + if (!dpstates[j][k].visible) return; + w += dpstates[j][k].weight + 1; + } + if(j-i > 1) { + pairs = &(dpstates[i][j].pairs); + iter = pairs->end(); + lastiter = pairs->end(); + while(iter!=pairs->begin()) { + iter--; + if(!IsReflex(vertices[iter->index2].p,vertices[j].p,vertices[k].p)) lastiter = iter; + else break; + } + if(lastiter == pairs->end()) w++; + else { + if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->index1].p)) w++; + else top = lastiter->index1; + } + } + UpdateState(i,k,w,top,j,dpstates); +} + +void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { + list *pairs; + list::iterator iter,lastiter; + long top; + long w; + + if(!dpstates[j][k].visible) return; + top = j; + w = dpstates[j][k].weight; + + if (j-i > 1) { + if (!dpstates[i][j].visible) return; + w += dpstates[i][j].weight + 1; + } + if (k-j > 1) { + pairs = &(dpstates[j][k].pairs); + + iter = pairs->begin(); + if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->index1].p))) { + lastiter = iter; + while(iter!=pairs->end()) { + if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->index1].p)) { + lastiter = iter; + iter++; + } + else break; + } + if(IsReflex(vertices[lastiter->index2].p,vertices[k].p,vertices[i].p)) w++; + else top = lastiter->index2; + } else w++; + } + UpdateState(i,k,w,j,top,dpstates); +} + +int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, list *parts) { + Vector2 p1,p2,p3,p4; + PartitionVertex *vertices; + DPState2 **dpstates; + long i,j,k,n,gap; + list diagonals,diagonals2; + Diagonal diagonal,newdiagonal; + list *pairs,*pairs2; + list::iterator iter,iter2; + int ret; + TriangulatorPoly newpoly; + list indices; + list::iterator iiter; + bool ijreal,jkreal; + + n = poly->GetNumPoints(); + vertices = new PartitionVertex[n]; + + dpstates = new DPState2 *[n]; + for(i=0;iGetPoint(i); + vertices[i].isActive = true; + if(i==0) vertices[i].previous = &(vertices[n-1]); + else vertices[i].previous = &(vertices[i-1]); + if(i==(poly->GetNumPoints()-1)) vertices[i].next = &(vertices[0]); + else vertices[i].next = &(vertices[i+1]); + } + for(i=1;iGetPoint(i); + for(j=i+1;jGetPoint(j); + + //visibility check + if(!InCone(&vertices[i],p2)) { + dpstates[i][j].visible = false; + continue; + } + if(!InCone(&vertices[j],p1)) { + dpstates[i][j].visible = false; + continue; + } + + for(k=0;kGetPoint(k); + if(k==(n-1)) p4 = poly->GetPoint(0); + else p4 = poly->GetPoint(k+1); + if(Intersects(p1,p2,p3,p4)) { + dpstates[i][j].visible = false; + break; + } + } + } + } + } + for(i=0;i<(n-2);i++) { + j = i+2; + if(dpstates[i][j].visible) { + dpstates[i][j].weight = 0; + newdiagonal.index1 = i+1; + newdiagonal.index2 = i+1; + dpstates[i][j].pairs.push_back(newdiagonal); + } + } + + dpstates[0][n-1].visible = true; + vertices[0].isConvex = false; //by convention + + for(gap=3; gapempty()) { + ret = 0; + break; + } + if(!vertices[diagonal.index1].isConvex) { + iter = pairs->end(); + iter--; + j = iter->index2; + newdiagonal.index1 = j; + newdiagonal.index2 = diagonal.index2; + diagonals.push_front(newdiagonal); + if((j - diagonal.index1)>1) { + if(iter->index1 != iter->index2) { + pairs2 = &(dpstates[diagonal.index1][j].pairs); + while(1) { + if(pairs2->empty()) { + ret = 0; + break; + } + iter2 = pairs2->end(); + iter2--; + if(iter->index1 != iter2->index1) pairs2->pop_back(); + else break; + } + if(ret == 0) break; + } + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = j; + diagonals.push_front(newdiagonal); + } + } else { + iter = pairs->begin(); + j = iter->index1; + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = j; + diagonals.push_front(newdiagonal); + if((diagonal.index2 - j) > 1) { + if(iter->index1 != iter->index2) { + pairs2 = &(dpstates[j][diagonal.index2].pairs); + while(1) { + if(pairs2->empty()) { + ret = 0; + break; + } + iter2 = pairs2->begin(); + if(iter->index2 != iter2->index2) pairs2->pop_front(); + else break; + } + if(ret == 0) break; + } + newdiagonal.index1 = j; + newdiagonal.index2 = diagonal.index2; + diagonals.push_front(newdiagonal); + } + } + } + + if(ret == 0) { + for(i=0;iend(); + iter--; + j = iter->index2; + if(iter->index1 != iter->index2) ijreal = false; + } else { + iter = pairs->begin(); + j = iter->index1; + if(iter->index1 != iter->index2) jkreal = false; + } + + newdiagonal.index1 = diagonal.index1; + newdiagonal.index2 = j; + if(ijreal) { + diagonals.push_back(newdiagonal); + } else { + diagonals2.push_back(newdiagonal); + } + + newdiagonal.index1 = j; + newdiagonal.index2 = diagonal.index2; + if(jkreal) { + diagonals.push_back(newdiagonal); + } else { + diagonals2.push_back(newdiagonal); + } + + indices.push_back(j); + } + + indices.sort(); + newpoly.Init((long)indices.size()); + k=0; + for(iiter = indices.begin();iiter!=indices.end();iiter++) { + newpoly[k] = vertices[*iiter].p; + k++; + } + parts->push_back(newpoly); + } + + for(i=0;i *inpolys, list *monotonePolys) { + list::iterator iter; + MonotoneVertex *vertices; + long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices; + long polystartindex, polyendindex; + TriangulatorPoly *poly; + MonotoneVertex *v,*v2,*vprev,*vnext; + ScanLineEdge newedge; + bool error = false; + + numvertices = 0; + for(iter = inpolys->begin(); iter != inpolys->end(); iter++) { + numvertices += iter->GetNumPoints(); + } + + maxnumvertices = numvertices*3; + vertices = new MonotoneVertex[maxnumvertices]; + newnumvertices = numvertices; + + polystartindex = 0; + for(iter = inpolys->begin(); iter != inpolys->end(); iter++) { + poly = &(*iter); + polyendindex = polystartindex + poly->GetNumPoints()-1; + for(i=0;iGetNumPoints();i++) { + vertices[i+polystartindex].p = poly->GetPoint(i); + if(i==0) vertices[i+polystartindex].previous = polyendindex; + else vertices[i+polystartindex].previous = i+polystartindex-1; + if(i==(poly->GetNumPoints()-1)) vertices[i+polystartindex].next = polystartindex; + else vertices[i+polystartindex].next = i+polystartindex+1; + } + polystartindex = polyendindex+1; + } + + //construct the priority queue + long *priority = new long [numvertices]; + for(i=0;iprevious]); + vnext = &(vertices[v->next]); + + if(Below(vprev->p,v->p)&&Below(vnext->p,v->p)) { + if(IsConvex(vnext->p,vprev->p,v->p)) { + vertextypes[i] = TRIANGULATOR_VERTEXTYPE_START; + } else { + vertextypes[i] = TRIANGULATOR_VERTEXTYPE_SPLIT; + } + } else if(Below(v->p,vprev->p)&&Below(v->p,vnext->p)) { + if(IsConvex(vnext->p,vprev->p,v->p)) + { + vertextypes[i] = TRIANGULATOR_VERTEXTYPE_END; + } else { + vertextypes[i] = TRIANGULATOR_VERTEXTYPE_MERGE; + } + } else { + vertextypes[i] = TRIANGULATOR_VERTEXTYPE_REGULAR; + } + } + + //helpers + long *helpers = new long[maxnumvertices]; + + //binary search tree that holds edges intersecting the scanline + //note that while set doesn't actually have to be implemented as a tree + //complexity requirements for operations are the same as for the balanced binary search tree + set edgeTree; + //store iterators to the edge tree elements + //this makes deleting existing edges much faster + set::iterator *edgeTreeIterators,edgeIter; + edgeTreeIterators = new set::iterator[maxnumvertices]; + pair::iterator,bool> edgeTreeRet; + for(i = 0; ip; + newedge.p2 = vertices[v->next].p; + newedge.index = vindex; + edgeTreeRet = edgeTree.insert(newedge); + edgeTreeIterators[vindex] = edgeTreeRet.first; + helpers[vindex] = vindex; + break; + + case TRIANGULATOR_VERTEXTYPE_END: + //if helper(ei-1) is a merge vertex + if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { + //Insert the diagonal connecting vi to helper(ei-1) in D. + AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + //Delete ei-1 from T + edgeTree.erase(edgeTreeIterators[v->previous]); + break; + + case TRIANGULATOR_VERTEXTYPE_SPLIT: + //Search in T to find the edge e j directly left of vi. + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); + if(edgeIter == edgeTree.begin()) { + error = true; + break; + } + edgeIter--; + //Insert the diagonal connecting vi to helper(ej) in D. + AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + vindex2 = newnumvertices-2; + v2 = &(vertices[vindex2]); + //helper(e j)�vi + helpers[edgeIter->index] = vindex; + //Insert ei in T and set helper(ei) to vi. + newedge.p1 = v2->p; + newedge.p2 = vertices[v2->next].p; + newedge.index = vindex2; + edgeTreeRet = edgeTree.insert(newedge); + edgeTreeIterators[vindex2] = edgeTreeRet.first; + helpers[vindex2] = vindex2; + break; + + case TRIANGULATOR_VERTEXTYPE_MERGE: + //if helper(ei-1) is a merge vertex + if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { + //Insert the diagonal connecting vi to helper(ei-1) in D. + AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + vindex2 = newnumvertices-2; + v2 = &(vertices[vindex2]); + } + //Delete ei-1 from T. + edgeTree.erase(edgeTreeIterators[v->previous]); + //Search in T to find the edge e j directly left of vi. + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); + if(edgeIter == edgeTree.begin()) { + error = true; + break; + } + edgeIter--; + //if helper(ej) is a merge vertex + if(vertextypes[helpers[edgeIter->index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { + //Insert the diagonal connecting vi to helper(e j) in D. + AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + //helper(e j)�vi + helpers[edgeIter->index] = vindex2; + break; + + case TRIANGULATOR_VERTEXTYPE_REGULAR: + //if the interior of P lies to the right of vi + if(Below(v->p,vertices[v->previous].p)) { + //if helper(ei-1) is a merge vertex + if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { + //Insert the diagonal connecting vi to helper(ei-1) in D. + AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + vindex2 = newnumvertices-2; + v2 = &(vertices[vindex2]); + } + //Delete ei-1 from T. + edgeTree.erase(edgeTreeIterators[v->previous]); + //Insert ei in T and set helper(ei) to vi. + newedge.p1 = v2->p; + newedge.p2 = vertices[v2->next].p; + newedge.index = vindex2; + edgeTreeRet = edgeTree.insert(newedge); + edgeTreeIterators[vindex2] = edgeTreeRet.first; + helpers[vindex2] = vindex; + } else { + //Search in T to find the edge ej directly left of vi. + newedge.p1 = v->p; + newedge.p2 = v->p; + edgeIter = edgeTree.lower_bound(newedge); + if(edgeIter == edgeTree.begin()) { + error = true; + break; + } + edgeIter--; + //if helper(ej) is a merge vertex + if(vertextypes[helpers[edgeIter->index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { + //Insert the diagonal connecting vi to helper(e j) in D. + AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->index], + vertextypes, edgeTreeIterators, &edgeTree, helpers); + } + //helper(e j)�vi + helpers[edgeIter->index] = vindex; + } + break; + } + + if(error) break; + } + + char *used = new char[newnumvertices]; + memset(used,0,newnumvertices*sizeof(char)); + + if(!error) { + //return result + long size; + TriangulatorPoly mpoly; + for(i=0;inext]); + size = 1; + while(vnext!=v) { + vnext = &(vertices[vnext->next]); + size++; + } + mpoly.Init(size); + v = &(vertices[i]); + mpoly[0] = v->p; + vnext = &(vertices[v->next]); + size = 1; + used[i] = 1; + used[v->next] = 1; + while(vnext!=v) { + mpoly[size] = vnext->p; + used[vnext->next] = 1; + vnext = &(vertices[vnext->next]); + size++; + } + monotonePolys->push_back(mpoly); + } + } + + //cleanup + delete [] vertices; + delete [] priority; + delete [] vertextypes; + delete [] edgeTreeIterators; + delete [] helpers; + delete [] used; + + if(error) { + return 0; + } else { + return 1; + } +} + +//adds a diagonal to the doubly-connected list of vertices +void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, + char *vertextypes, set::iterator *edgeTreeIterators, + set *edgeTree, long *helpers) +{ + long newindex1,newindex2; + + newindex1 = *numvertices; + (*numvertices)++; + newindex2 = *numvertices; + (*numvertices)++; + + vertices[newindex1].p = vertices[index1].p; + vertices[newindex2].p = vertices[index2].p; + + vertices[newindex2].next = vertices[index2].next; + vertices[newindex1].next = vertices[index1].next; + + vertices[vertices[index2].next].previous = newindex2; + vertices[vertices[index1].next].previous = newindex1; + + vertices[index1].next = newindex2; + vertices[newindex2].previous = index1; + + vertices[index2].next = newindex1; + vertices[newindex1].previous = index2; + + //update all relevant structures + vertextypes[newindex1] = vertextypes[index1]; + edgeTreeIterators[newindex1] = edgeTreeIterators[index1]; + helpers[newindex1] = helpers[index1]; + if(edgeTreeIterators[newindex1] != edgeTree->end()) + edgeTreeIterators[newindex1]->index = newindex1; + vertextypes[newindex2] = vertextypes[index2]; + edgeTreeIterators[newindex2] = edgeTreeIterators[index2]; + helpers[newindex2] = helpers[index2]; + if(edgeTreeIterators[newindex2] != edgeTree->end()) + edgeTreeIterators[newindex2]->index = newindex2; +} + +bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) { + if(p1.y < p2.y) return true; + else if(p1.y == p2.y) { + if(p1.x < p2.x) return true; + } + return false; +} + +//sorts in the falling order of y values, if y is equal, x is used instead +bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) { + if(vertices[index1].p.y > vertices[index2].p.y) return true; + else if(vertices[index1].p.y == vertices[index2].p.y) { + if(vertices[index1].p.x > vertices[index2].p.x) return true; + } + return false; +} + +bool TriangulatorPartition::ScanLineEdge::IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const { + real_t tmp; + tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); + if(tmp>0) return 1; + else return 0; +} + +bool TriangulatorPartition::ScanLineEdge::operator < (const ScanLineEdge & other) const { + if(other.p1.y == other.p2.y) { + if(p1.y == p2.y) { + if(p1.y < other.p1.y) return true; + else return false; + } + if(IsConvex(p1,p2,other.p1)) return true; + else return false; + } else if(p1.y == p2.y) { + if(IsConvex(other.p1,other.p2,p1)) return false; + else return true; + } else if(p1.y < other.p1.y) { + if(IsConvex(other.p1,other.p2,p1)) return false; + else return true; + } else { + if(IsConvex(p1,p2,other.p1)) return true; + else return false; + } +} + +//triangulates monotone polygon +//O(n) time, O(n) space complexity +int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, list *triangles) { + long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex; + Vector2 *points; + long numpoints; + TriangulatorPoly triangle; + + numpoints = inPoly->GetNumPoints(); + points = inPoly->GetPoints(); + + //trivial calses + if(numpoints < 3) return 0; + if(numpoints == 3) { + triangles->push_back(*inPoly); + } + + topindex = 0; bottomindex=0; + for(i=1;i=numpoints) i2 = 0; + if(!Below(points[i2],points[i])) return 0; + i = i2; + } + i = bottomindex; + while(i!=topindex) { + i2 = i+1; if(i2>=numpoints) i2 = 0; + if(!Below(points[i],points[i2])) return 0; + i = i2; + } + + char *vertextypes = new char[numpoints]; + long *priority = new long[numpoints]; + + //merge left and right vertex chains + priority[0] = topindex; + vertextypes[topindex] = 0; + leftindex = topindex+1; if(leftindex>=numpoints) leftindex = 0; + rightindex = topindex-1; if(rightindex<0) rightindex = numpoints-1; + for(i=1;i<(numpoints-1);i++) { + if(leftindex==bottomindex) { + priority[i] = rightindex; + rightindex--; if(rightindex<0) rightindex = numpoints-1; + vertextypes[priority[i]] = -1; + } else if(rightindex==bottomindex) { + priority[i] = leftindex; + leftindex++; if(leftindex>=numpoints) leftindex = 0; + vertextypes[priority[i]] = 1; + } else { + if(Below(points[leftindex],points[rightindex])) { + priority[i] = rightindex; + rightindex--; if(rightindex<0) rightindex = numpoints-1; + vertextypes[priority[i]] = -1; + } else { + priority[i] = leftindex; + leftindex++; if(leftindex>=numpoints) leftindex = 0; + vertextypes[priority[i]] = 1; + } + } + } + priority[i] = bottomindex; + vertextypes[bottomindex] = 0; + + long *stack = new long[numpoints]; + long stackptr = 0; + + stack[0] = priority[0]; + stack[1] = priority[1]; + stackptr = 2; + + //for each vertex from top to bottom trim as many triangles as possible + for(i=2;i<(numpoints-1);i++) { + vindex = priority[i]; + if(vertextypes[vindex]!=vertextypes[stack[stackptr-1]]) { + for(j=0;j<(stackptr-1);j++) { + if(vertextypes[vindex]==1) { + triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]); + } else { + triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]); + } + triangles->push_back(triangle); + } + stack[0] = priority[i-1]; + stack[1] = priority[i]; + stackptr = 2; + } else { + stackptr--; + while(stackptr>0) { + if(vertextypes[vindex]==1) { + if(IsConvex(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]])) { + triangle.Triangle(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]]); + triangles->push_back(triangle); + stackptr--; + } else { + break; + } + } else { + if(IsConvex(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]])) { + triangle.Triangle(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]]); + triangles->push_back(triangle); + stackptr--; + } else { + break; + } + } + } + stackptr++; + stack[stackptr] = vindex; + stackptr++; + } + } + vindex = priority[i]; + for(j=0;j<(stackptr-1);j++) { + if(vertextypes[stack[j+1]]==1) { + triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]); + } else { + triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]); + } + triangles->push_back(triangle); + } + + delete [] priority; + delete [] vertextypes; + delete [] stack; + + return 1; +} + +int TriangulatorPartition::Triangulate_MONO(list *inpolys, list *triangles) { + list monotone; + list::iterator iter; + + if(!MonotonePartition(inpolys,&monotone)) return 0; + for(iter = monotone.begin(); iter!=monotone.end();iter++) { + if(!TriangulateMonotone(&(*iter),triangles)) return 0; + } + return 1; +} + +int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, list *triangles) { + list polys; + polys.push_back(*poly); + + return Triangulate_MONO(&polys, triangles); +} diff --git a/core/math/triangulator.h b/core/math/triangulator.h new file mode 100644 index 0000000000..c34c445892 --- /dev/null +++ b/core/math/triangulator.h @@ -0,0 +1,309 @@ +//Copyright (C) 2011 by Ivan Fratric +// +//Permission is hereby granted, free of charge, to any person obtaining a copy +//of this software and associated documentation files (the "Software"), to deal +//in the Software without restriction, including without limitation the rights +//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +//copies of the Software, and to permit persons to whom the Software is +//furnished to do so, subject to the following conditions: +// +//The above copyright notice and this permission notice shall be included in +//all copies or substantial portions of the Software. +// +//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +//THE SOFTWARE. + +#ifndef TRIANGULATOR_H +#define TRIANGULATOR_H + +#include "math_2d.h" +#include +#include + +//2D point structure + + +#define TRIANGULATOR_CCW 1 +#define TRIANGULATOR_CW -1 +//Polygon implemented as an array of points with a 'hole' flag +class TriangulatorPoly { +protected: + + + + Vector2 *points; + long numpoints; + bool hole; + +public: + + //constructors/destructors + TriangulatorPoly(); + ~TriangulatorPoly(); + + TriangulatorPoly(const TriangulatorPoly &src); + TriangulatorPoly& operator=(const TriangulatorPoly &src); + + //getters and setters + long GetNumPoints() { + return numpoints; + } + + bool IsHole() { + return hole; + } + + void SetHole(bool hole) { + this->hole = hole; + } + + Vector2 &GetPoint(long i) { + return points[i]; + } + + Vector2 *GetPoints() { + return points; + } + + Vector2& operator[] (int i) { + return points[i]; + } + + //clears the polygon points + void Clear(); + + //inits the polygon with numpoints vertices + void Init(long numpoints); + + //creates a triangle with points p1,p2,p3 + void Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3); + + //inverts the orfer of vertices + void Invert(); + + //returns the orientation of the polygon + //possible values: + // Triangulator_CCW : polygon vertices are in counter-clockwise order + // Triangulator_CW : polygon vertices are in clockwise order + // 0 : the polygon has no (measurable) area + int GetOrientation(); + + //sets the polygon orientation + //orientation can be + // Triangulator_CCW : sets vertices in counter-clockwise order + // Triangulator_CW : sets vertices in clockwise order + void SetOrientation(int orientation); +}; + +class TriangulatorPartition { +protected: + struct PartitionVertex { + bool isActive; + bool isConvex; + bool isEar; + + Vector2 p; + real_t angle; + PartitionVertex *previous; + PartitionVertex *next; + }; + + struct MonotoneVertex { + Vector2 p; + long previous; + long next; + }; + + class VertexSorter{ + MonotoneVertex *vertices; + public: + VertexSorter(MonotoneVertex *v) : vertices(v) {} + bool operator() (long index1, long index2); + }; + + struct Diagonal { + long index1; + long index2; + }; + + //dynamic programming state for minimum-weight triangulation + struct DPState { + bool visible; + real_t weight; + long bestvertex; + }; + + //dynamic programming state for convex partitioning + struct DPState2 { + bool visible; + long weight; + std::list pairs; + }; + + //edge that intersects the scanline + struct ScanLineEdge { + mutable long index; + Vector2 p1; + Vector2 p2; + + //determines if the edge is to the left of another edge + bool operator< (const ScanLineEdge & other) const; + + bool IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const; + }; + + //standard helper functions + bool IsConvex(Vector2& p1, Vector2& p2, Vector2& p3); + bool IsReflex(Vector2& p1, Vector2& p2, Vector2& p3); + bool IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p); + + bool InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p); + bool InCone(PartitionVertex *v, Vector2 &p); + + int Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22); + + Vector2 Normalize(const Vector2 &p); + real_t Distance(const Vector2 &p1, const Vector2 &p2); + + //helper functions for Triangulate_EC + void UpdateVertexReflexity(PartitionVertex *v); + void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices); + + //helper functions for ConvexPartition_OPT + void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates); + void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); + void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); + + //helper functions for MonotonePartition + bool Below(Vector2 &p1, Vector2 &p2); + void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, + char *vertextypes, std::set::iterator *edgeTreeIterators, + std::set *edgeTree, long *helpers); + + //triangulates a monotone polygon, used in Triangulate_MONO + int TriangulateMonotone(TriangulatorPoly *inPoly, std::list *triangles); + +public: + + //simple heuristic procedure for removing holes from a list of polygons + //works by creating a diagonal from the rightmost hole vertex to some visible vertex + //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices + //space complexity: O(n) + //params: + // inpolys : a list of polygons that can contain holes + // vertices of all non-hole polys have to be in counter-clockwise order + // vertices of all hole polys have to be in clockwise order + // outpolys : a list of polygons without holes + //returns 1 on success, 0 on failure + int RemoveHoles(std::list *inpolys, std::list *outpolys); + + //triangulates a polygon by ear clipping + //time complexity O(n^2), n is the number of vertices + //space complexity: O(n) + //params: + // poly : an input polygon to be triangulated + // vertices have to be in counter-clockwise order + // triangles : a list of triangles (result) + //returns 1 on success, 0 on failure + int Triangulate_EC(TriangulatorPoly *poly, std::list *triangles); + + //triangulates a list of polygons that may contain holes by ear clipping algorithm + //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon + //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices + //space complexity: O(n) + //params: + // inpolys : a list of polygons to be triangulated (can contain holes) + // vertices of all non-hole polys have to be in counter-clockwise order + // vertices of all hole polys have to be in clockwise order + // triangles : a list of triangles (result) + //returns 1 on success, 0 on failure + int Triangulate_EC(std::list *inpolys, std::list *triangles); + + //creates an optimal polygon triangulation in terms of minimal edge length + //time complexity: O(n^3), n is the number of vertices + //space complexity: O(n^2) + //params: + // poly : an input polygon to be triangulated + // vertices have to be in counter-clockwise order + // triangles : a list of triangles (result) + //returns 1 on success, 0 on failure + int Triangulate_OPT(TriangulatorPoly *poly, std::list *triangles); + + //triangulates a polygons by firstly partitioning it into monotone polygons + //time complexity: O(n*log(n)), n is the number of vertices + //space complexity: O(n) + //params: + // poly : an input polygon to be triangulated + // vertices have to be in counter-clockwise order + // triangles : a list of triangles (result) + //returns 1 on success, 0 on failure + int Triangulate_MONO(TriangulatorPoly *poly, std::list *triangles); + + //triangulates a list of polygons by firstly partitioning them into monotone polygons + //time complexity: O(n*log(n)), n is the number of vertices + //space complexity: O(n) + //params: + // inpolys : a list of polygons to be triangulated (can contain holes) + // vertices of all non-hole polys have to be in counter-clockwise order + // vertices of all hole polys have to be in clockwise order + // triangles : a list of triangles (result) + //returns 1 on success, 0 on failure + int Triangulate_MONO(std::list *inpolys, std::list *triangles); + + //creates a monotone partition of a list of polygons that can contain holes + //time complexity: O(n*log(n)), n is the number of vertices + //space complexity: O(n) + //params: + // inpolys : a list of polygons to be triangulated (can contain holes) + // vertices of all non-hole polys have to be in counter-clockwise order + // vertices of all hole polys have to be in clockwise order + // monotonePolys : a list of monotone polygons (result) + //returns 1 on success, 0 on failure + int MonotonePartition(std::list *inpolys, std::list *monotonePolys); + + //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm + //the algorithm gives at most four times the number of parts as the optimal algorithm + //however, in practice it works much better than that and often gives optimal partition + //uses triangulation obtained by ear clipping as intermediate result + //time complexity O(n^2), n is the number of vertices + //space complexity: O(n) + //params: + // poly : an input polygon to be partitioned + // vertices have to be in counter-clockwise order + // parts : resulting list of convex polygons + //returns 1 on success, 0 on failure + int ConvexPartition_HM(TriangulatorPoly *poly, std::list *parts); + + //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm + //the algorithm gives at most four times the number of parts as the optimal algorithm + //however, in practice it works much better than that and often gives optimal partition + //uses triangulation obtained by ear clipping as intermediate result + //time complexity O(n^2), n is the number of vertices + //space complexity: O(n) + //params: + // inpolys : an input list of polygons to be partitioned + // vertices of all non-hole polys have to be in counter-clockwise order + // vertices of all hole polys have to be in clockwise order + // parts : resulting list of convex polygons + //returns 1 on success, 0 on failure + int ConvexPartition_HM(std::list *inpolys, std::list *parts); + + //optimal convex partitioning (in terms of number of resulting convex polygons) + //using the Keil-Snoeyink algorithm + //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998 + //time complexity O(n^3), n is the number of vertices + //space complexity: O(n^3) + // poly : an input polygon to be partitioned + // vertices have to be in counter-clockwise order + // parts : resulting list of convex polygons + //returns 1 on success, 0 on failure + int ConvexPartition_OPT(TriangulatorPoly *poly, std::list *parts); +}; + + +#endif -- cgit v1.2.3 From 2185c018f6593e6d64b2beb62202d2291e2e008e Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Sun, 15 Feb 2015 01:19:46 -0300 Subject: begin new serialization framework also got rid of STL dependency on triangulator --- core/bind/core_bind.cpp | 7 + core/bind/core_bind.h | 2 + core/math/triangulator.cpp | 325 ++++++++++++++-------------- core/math/triangulator.h | 41 ++-- core/set.h | 37 ++++ core/variant.cpp | 43 ++-- core/variant.h | 6 +- core/variant_construct_string.cpp | 433 ++++++++++++++++++++++++++++++++++++++ 8 files changed, 695 insertions(+), 199 deletions(-) create mode 100644 core/variant_construct_string.cpp (limited to 'core') diff --git a/core/bind/core_bind.cpp b/core/bind/core_bind.cpp index a03fd7fe4a..8d18acdc23 100644 --- a/core/bind/core_bind.cpp +++ b/core/bind/core_bind.cpp @@ -316,6 +316,11 @@ float _OS::get_time_scale() { return OS::get_singleton()->get_time_scale(); } +bool _OS::is_ok_left_and_cancel_right() const { + + return OS::get_singleton()->get_swap_ok_cancel(); +} + /* enum Weekday { DAY_SUNDAY, @@ -699,6 +704,8 @@ void _OS::_bind_methods() { ObjectTypeDB::bind_method(_MD("get_system_dir","dir"),&_OS::get_system_dir); ObjectTypeDB::bind_method(_MD("get_unique_ID"),&_OS::get_unique_ID); + ObjectTypeDB::bind_method(_MD("is_ok_left_and_cancel_right"),&_OS::is_ok_left_and_cancel_right); + ObjectTypeDB::bind_method(_MD("get_frames_per_second"),&_OS::get_frames_per_second); ObjectTypeDB::bind_method(_MD("print_all_textures_by_size"),&_OS::print_all_textures_by_size); diff --git a/core/bind/core_bind.h b/core/bind/core_bind.h index f5043ba71f..057ad90fe9 100644 --- a/core/bind/core_bind.h +++ b/core/bind/core_bind.h @@ -220,6 +220,8 @@ public: void set_time_scale(float p_scale); float get_time_scale(); + bool is_ok_left_and_cancel_right() const; + static _OS *get_singleton() { return singleton; } _OS(); diff --git a/core/math/triangulator.cpp b/core/math/triangulator.cpp index 6be1cdb330..8f82d76823 100644 --- a/core/math/triangulator.cpp +++ b/core/math/triangulator.cpp @@ -22,9 +22,9 @@ #include #include #include -#include + #include "triangulator.h" -using namespace std; + #define TRIANGULATOR_VERTEXTYPE_REGULAR 0 #define TRIANGULATOR_VERTEXTYPE_START 1 @@ -163,9 +163,9 @@ int TriangulatorPartition::Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, } //removes holes from inpolys by merging them with non-holes -int TriangulatorPartition::RemoveHoles(list *inpolys, list *outpolys) { - list polys; - list::iterator holeiter,polyiter,iter,iter2; +int TriangulatorPartition::RemoveHoles(List *inpolys, List *outpolys) { + List polys; + List::Element *holeiter,*polyiter,*iter,*iter2; long i,i2,holepointindex,polypointindex; Vector2 holepoint,polypoint,bestpolypoint; Vector2 linep1,linep2; @@ -177,15 +177,15 @@ int TriangulatorPartition::RemoveHoles(list *inpolys, listbegin(); iter!=inpolys->end(); iter++) { - if(iter->IsHole()) { + for(iter = inpolys->front(); iter; iter=iter->next()) { + if(iter->get().IsHole()) { hasholes = true; break; } } if(!hasholes) { - for(iter = inpolys->begin(); iter!=inpolys->end(); iter++) { - outpolys->push_back(*iter); + for(iter = inpolys->front(); iter; iter=iter->next()) { + outpolys->push_back(iter->get()); } return 1; } @@ -195,8 +195,8 @@ int TriangulatorPartition::RemoveHoles(list *inpolys, listIsHole()) continue; + for(iter = polys.front(); iter; iter=iter->next()) { + if(!iter->get().IsHole()) continue; if(!hasholes) { hasholes = true; @@ -204,38 +204,38 @@ int TriangulatorPartition::RemoveHoles(list *inpolys, listGetNumPoints(); i++) { - if(iter->GetPoint(i).x > holeiter->GetPoint(holepointindex).x) { + for(i=0; i < iter->get().GetNumPoints(); i++) { + if(iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) { holeiter = iter; holepointindex = i; } } } if(!hasholes) break; - holepoint = holeiter->GetPoint(holepointindex); + holepoint = holeiter->get().GetPoint(holepointindex); pointfound = false; - for(iter = polys.begin(); iter!=polys.end(); iter++) { - if(iter->IsHole()) continue; - for(i=0; i < iter->GetNumPoints(); i++) { - if(iter->GetPoint(i).x <= holepoint.x) continue; - if(!InCone(iter->GetPoint((i+iter->GetNumPoints()-1)%(iter->GetNumPoints())), - iter->GetPoint(i), - iter->GetPoint((i+1)%(iter->GetNumPoints())), + for(iter = polys.front(); iter; iter=iter->next()) { + if(iter->get().IsHole()) continue; + for(i=0; i < iter->get().GetNumPoints(); i++) { + if(iter->get().GetPoint(i).x <= holepoint.x) continue; + if(!InCone(iter->get().GetPoint((i+iter->get().GetNumPoints()-1)%(iter->get().GetNumPoints())), + iter->get().GetPoint(i), + iter->get().GetPoint((i+1)%(iter->get().GetNumPoints())), holepoint)) continue; - polypoint = iter->GetPoint(i); + polypoint = iter->get().GetPoint(i); if(pointfound) { v1 = Normalize(polypoint-holepoint); v2 = Normalize(bestpolypoint-holepoint); if(v2.x > v1.x) continue; } pointvisible = true; - for(iter2 = polys.begin(); iter2!=polys.end(); iter2++) { - if(iter2->IsHole()) continue; - for(i2=0; i2 < iter2->GetNumPoints(); i2++) { - linep1 = iter2->GetPoint(i2); - linep2 = iter2->GetPoint((i2+1)%(iter2->GetNumPoints())); + for(iter2 = polys.front(); iter2; iter2=iter2->next()) { + if(iter2->get().IsHole()) continue; + for(i2=0; i2 < iter2->get().GetNumPoints(); i2++) { + linep1 = iter2->get().GetPoint(i2); + linep2 = iter2->get().GetPoint((i2+1)%(iter2->get().GetNumPoints())); if(Intersects(holepoint,polypoint,linep1,linep2)) { pointvisible = false; break; @@ -254,18 +254,18 @@ int TriangulatorPartition::RemoveHoles(list *inpolys, listGetNumPoints() + polyiter->GetNumPoints() + 2); + newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2); i2 = 0; for(i=0;i<=polypointindex;i++) { - newpoly[i2] = polyiter->GetPoint(i); + newpoly[i2] = polyiter->get().GetPoint(i); i2++; } - for(i=0;i<=holeiter->GetNumPoints();i++) { - newpoly[i2] = holeiter->GetPoint((i+holepointindex)%holeiter->GetNumPoints()); + for(i=0;i<=holeiter->get().GetNumPoints();i++) { + newpoly[i2] = holeiter->get().GetPoint((i+holepointindex)%holeiter->get().GetNumPoints()); i2++; } - for(i=polypointindex;iGetNumPoints();i++) { - newpoly[i2] = polyiter->GetPoint(i); + for(i=polypointindex;iget().GetNumPoints();i++) { + newpoly[i2] = polyiter->get().GetPoint(i); i2++; } @@ -274,8 +274,8 @@ int TriangulatorPartition::RemoveHoles(list *inpolys, listpush_back(*iter); + for(iter = polys.front(); iter; iter=iter->next()) { + outpolys->push_back(iter->get()); } return 1; @@ -366,7 +366,7 @@ void TriangulatorPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *ve } //triangulation by ear removal -int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, list *triangles) { +int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, List *triangles) { long numvertices; PartitionVertex *vertices; PartitionVertex *ear; @@ -440,20 +440,20 @@ int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, list *inpolys, list *triangles) { - list outpolys; - list::iterator iter; +int TriangulatorPartition::Triangulate_EC(List *inpolys, List *triangles) { + List outpolys; + List::Element*iter; if(!RemoveHoles(inpolys,&outpolys)) return 0; - for(iter=outpolys.begin();iter!=outpolys.end();iter++) { - if(!Triangulate_EC(&(*iter),triangles)) return 0; + for(iter=outpolys.front();iter;iter=iter->next()) { + if(!Triangulate_EC(&(iter->get()),triangles)) return 0; } return 1; } -int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, list *parts) { - list triangles; - list::iterator iter1,iter2; +int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, List *parts) { + List triangles; + List::Element *iter1,*iter2; TriangulatorPoly *poly1,*poly2; TriangulatorPoly newpoly; Vector2 d1,d2,p1,p2,p3; @@ -480,17 +480,17 @@ int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, listnext()) { + poly1 = &(iter1->get()); for(i11=0;i11GetNumPoints();i11++) { d1 = poly1->GetPoint(i11); i12 = (i11+1)%(poly1->GetNumPoints()); d2 = poly1->GetPoint(i12); isdiagonal = false; - for(iter2 = iter1; iter2 != triangles.end(); iter2++) { + for(iter2 = iter1; iter2 ; iter2=iter2->next()) { if(iter1 == iter2) continue; - poly2 = &(*iter2); + poly2 = &(iter2->get()); for(i21=0;i21GetNumPoints();i21++) { if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue; @@ -536,28 +536,28 @@ int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, listget() = newpoly; + poly1 = &(iter1->get()); i11 = -1; continue; } } - for(iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) { - parts->push_back(*iter1); + for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) { + parts->push_back(iter1->get()); } return 1; } -int TriangulatorPartition::ConvexPartition_HM(list *inpolys, list *parts) { - list outpolys; - list::iterator iter; +int TriangulatorPartition::ConvexPartition_HM(List *inpolys, List *parts) { + List outpolys; + List::Element* iter; if(!RemoveHoles(inpolys,&outpolys)) return 0; - for(iter=outpolys.begin();iter!=outpolys.end();iter++) { - if(!ConvexPartition_HM(&(*iter),parts)) return 0; + for(iter=outpolys.front();iter;iter=iter->next()) { + if(!ConvexPartition_HM(&(iter->get()),parts)) return 0; } return 1; } @@ -565,14 +565,14 @@ int TriangulatorPartition::ConvexPartition_HM(list *inpolys, l //minimum-weight polygon triangulation by dynamic programming //O(n^3) time complexity //O(n^2) space complexity -int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, list *triangles) { +int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, List *triangles) { long i,j,k,gap,n; DPState **dpstates; Vector2 p1,p2,p3,p4; long bestvertex; real_t weight,minweight,d1,d2; Diagonal diagonal,newdiagonal; - list diagonals; + List diagonals; TriangulatorPoly triangle; int ret = 1; @@ -666,7 +666,7 @@ int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, listget()); diagonals.pop_front(); bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex; if(bestvertex == -1) { @@ -697,7 +697,7 @@ int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, list *pairs; + List *pairs; long w2; w2 = dpstates[a][b].weight; @@ -712,15 +712,15 @@ void TriangulatorPartition::UpdateState(long a, long b, long w, long i, long j, pairs->push_front(newdiagonal); dpstates[a][b].weight = w; } else { - if((!pairs->empty())&&(i <= pairs->begin()->index1)) return; - while((!pairs->empty())&&(pairs->begin()->index2 >= j)) pairs->pop_front(); + if((!pairs->empty())&&(i <= pairs->front()->get().index1)) return; + while((!pairs->empty())&&(pairs->front()->get().index2 >= j)) pairs->pop_front(); pairs->push_front(newdiagonal); } } void TriangulatorPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { - list *pairs; - list::iterator iter,lastiter; + List *pairs; + List::Element *iter,*lastiter; long top; long w; @@ -733,25 +733,29 @@ void TriangulatorPartition::TypeA(long i, long j, long k, PartitionVertex *verti } if(j-i > 1) { pairs = &(dpstates[i][j].pairs); - iter = pairs->end(); - lastiter = pairs->end(); - while(iter!=pairs->begin()) { - iter--; - if(!IsReflex(vertices[iter->index2].p,vertices[j].p,vertices[k].p)) lastiter = iter; + iter = NULL; + lastiter = NULL; + while(iter!=pairs->front()) { + if (!iter) + iter=pairs->back(); + else + iter=iter->prev(); + + if(!IsReflex(vertices[iter->get().index2].p,vertices[j].p,vertices[k].p)) lastiter = iter; else break; } - if(lastiter == pairs->end()) w++; + if(lastiter == NULL) w++; else { - if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->index1].p)) w++; - else top = lastiter->index1; + if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->get().index1].p)) w++; + else top = lastiter->get().index1; } } UpdateState(i,k,w,top,j,dpstates); } void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { - list *pairs; - list::iterator iter,lastiter; + List *pairs; + List::Element* iter,*lastiter; long top; long w; @@ -766,36 +770,36 @@ void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *verti if (k-j > 1) { pairs = &(dpstates[j][k].pairs); - iter = pairs->begin(); - if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->index1].p))) { + iter = pairs->front(); + if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) { lastiter = iter; - while(iter!=pairs->end()) { - if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->index1].p)) { + while(iter!=NULL) { + if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p)) { lastiter = iter; - iter++; + iter=iter->next(); } else break; } - if(IsReflex(vertices[lastiter->index2].p,vertices[k].p,vertices[i].p)) w++; - else top = lastiter->index2; + if(IsReflex(vertices[lastiter->get().index2].p,vertices[k].p,vertices[i].p)) w++; + else top = lastiter->get().index2; } else w++; } UpdateState(i,k,w,j,top,dpstates); } -int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, list *parts) { +int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List *parts) { Vector2 p1,p2,p3,p4; PartitionVertex *vertices; DPState2 **dpstates; long i,j,k,n,gap; - list diagonals,diagonals2; + List diagonals,diagonals2; Diagonal diagonal,newdiagonal; - list *pairs,*pairs2; - list::iterator iter,iter2; + List *pairs,*pairs2; + List::Element* iter,*iter2; int ret; TriangulatorPoly newpoly; - list indices; - list::iterator iiter; + List indices; + List::Element* iiter; bool ijreal,jkreal; n = poly->GetNumPoints(); @@ -903,7 +907,7 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, listget()); diagonals.pop_front(); if((diagonal.index2 - diagonal.index1) <=1) continue; pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); @@ -912,23 +916,23 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, listend(); - iter--; - j = iter->index2; + iter = pairs->back(); + + j = iter->get().index2; newdiagonal.index1 = j; newdiagonal.index2 = diagonal.index2; diagonals.push_front(newdiagonal); if((j - diagonal.index1)>1) { - if(iter->index1 != iter->index2) { + if(iter->get().index1 != iter->get().index2) { pairs2 = &(dpstates[diagonal.index1][j].pairs); while(1) { if(pairs2->empty()) { ret = 0; break; } - iter2 = pairs2->end(); - iter2--; - if(iter->index1 != iter2->index1) pairs2->pop_back(); + iter2 = pairs2->back(); + + if(iter->get().index1 != iter2->get().index1) pairs2->pop_back(); else break; } if(ret == 0) break; @@ -938,21 +942,21 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, listbegin(); - j = iter->index1; + iter = pairs->front(); + j = iter->get().index1; newdiagonal.index1 = diagonal.index1; newdiagonal.index2 = j; diagonals.push_front(newdiagonal); if((diagonal.index2 - j) > 1) { - if(iter->index1 != iter->index2) { + if(iter->get().index1 != iter->get().index2) { pairs2 = &(dpstates[j][diagonal.index2].pairs); while(1) { if(pairs2->empty()) { ret = 0; break; } - iter2 = pairs2->begin(); - if(iter->index2 != iter2->index2) pairs2->pop_front(); + iter2 = pairs2->front(); + if(iter->get().index2 != iter2->get().index2) pairs2->pop_front(); else break; } if(ret == 0) break; @@ -978,7 +982,7 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, listget(); diagonals.pop_front(); if((diagonal.index2 - diagonal.index1) <= 1) continue; @@ -989,21 +993,20 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, listget()); diagonals2.pop_front(); if((diagonal.index2 - diagonal.index1) <= 1) continue; ijreal = true; jkreal = true; pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); if(!vertices[diagonal.index1].isConvex) { - iter = pairs->end(); - iter--; - j = iter->index2; - if(iter->index1 != iter->index2) ijreal = false; + iter = pairs->back(); + j = iter->get().index2; + if(iter->get().index1 != iter->get().index2) ijreal = false; } else { - iter = pairs->begin(); - j = iter->index1; - if(iter->index1 != iter->index2) jkreal = false; + iter = pairs->front(); + j = iter->get().index1; + if(iter->get().index1 != iter->get().index2) jkreal = false; } newdiagonal.index1 = diagonal.index1; @@ -1028,8 +1031,8 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, listnext()) { + newpoly[k] = vertices[iiter->get()].p; k++; } parts->push_back(newpoly); @@ -1049,8 +1052,8 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, list *inpolys, list *monotonePolys) { - list::iterator iter; +int TriangulatorPartition::MonotonePartition(List *inpolys, List *monotonePolys) { + List::Element *iter; MonotoneVertex *vertices; long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices; long polystartindex, polyendindex; @@ -1060,8 +1063,8 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li bool error = false; numvertices = 0; - for(iter = inpolys->begin(); iter != inpolys->end(); iter++) { - numvertices += iter->GetNumPoints(); + for(iter = inpolys->front(); iter ; iter=iter->next()) { + numvertices += iter->get().GetNumPoints(); } maxnumvertices = numvertices*3; @@ -1069,8 +1072,8 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li newnumvertices = numvertices; polystartindex = 0; - for(iter = inpolys->begin(); iter != inpolys->end(); iter++) { - poly = &(*iter); + for(iter = inpolys->front(); iter ; iter=iter->next()) { + poly = &(iter->get()); polyendindex = polystartindex + poly->GetNumPoints()-1; for(i=0;iGetNumPoints();i++) { vertices[i+polystartindex].p = poly->GetPoint(i); @@ -1085,7 +1088,9 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li //construct the priority queue long *priority = new long [numvertices]; for(i=0;i sorter; + sorter.compare.vertices=vertices; + sorter.sort(priority,numvertices); //determine vertex types char *vertextypes = new char[maxnumvertices]; @@ -1118,13 +1123,13 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li //binary search tree that holds edges intersecting the scanline //note that while set doesn't actually have to be implemented as a tree //complexity requirements for operations are the same as for the balanced binary search tree - set edgeTree; + Set edgeTree; //store iterators to the edge tree elements //this makes deleting existing edges much faster - set::iterator *edgeTreeIterators,edgeIter; - edgeTreeIterators = new set::iterator[maxnumvertices]; - pair::iterator,bool> edgeTreeRet; - for(i = 0; i::Element **edgeTreeIterators,*edgeIter; + edgeTreeIterators = new Set::Element*[maxnumvertices]; +// Pair::Element*,bool> edgeTreeRet; + for(i = 0; i *inpolys, li newedge.p1 = v->p; newedge.p2 = vertices[v->next].p; newedge.index = vindex; - edgeTreeRet = edgeTree.insert(newedge); - edgeTreeIterators[vindex] = edgeTreeRet.first; + edgeTreeIterators[vindex] = edgeTree.insert(newedge); helpers[vindex] = vindex; break; @@ -1162,24 +1166,24 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li newedge.p1 = v->p; newedge.p2 = v->p; edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.begin()) { + if(edgeIter == edgeTree.front()) { error = true; break; } - edgeIter--; + edgeIter=edgeIter->prev(); //Insert the diagonal connecting vi to helper(ej) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->index], + AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index], vertextypes, edgeTreeIterators, &edgeTree, helpers); vindex2 = newnumvertices-2; v2 = &(vertices[vindex2]); //helper(e j)�vi - helpers[edgeIter->index] = vindex; + helpers[edgeIter->get().index] = vindex; //Insert ei in T and set helper(ei) to vi. newedge.p1 = v2->p; newedge.p2 = vertices[v2->next].p; newedge.index = vindex2; - edgeTreeRet = edgeTree.insert(newedge); - edgeTreeIterators[vindex2] = edgeTreeRet.first; + + edgeTreeIterators[vindex2] = edgeTree.insert(newedge); helpers[vindex2] = vindex2; break; @@ -1198,19 +1202,19 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li newedge.p1 = v->p; newedge.p2 = v->p; edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.begin()) { + if(edgeIter == edgeTree.front()) { error = true; break; } - edgeIter--; + edgeIter=edgeIter->prev(); //if helper(ej) is a merge vertex - if(vertextypes[helpers[edgeIter->index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { + if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { //Insert the diagonal connecting vi to helper(e j) in D. - AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->index], + AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->get().index], vertextypes, edgeTreeIterators, &edgeTree, helpers); } //helper(e j)�vi - helpers[edgeIter->index] = vindex2; + helpers[edgeIter->get().index] = vindex2; break; case TRIANGULATOR_VERTEXTYPE_REGULAR: @@ -1230,27 +1234,26 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li newedge.p1 = v2->p; newedge.p2 = vertices[v2->next].p; newedge.index = vindex2; - edgeTreeRet = edgeTree.insert(newedge); - edgeTreeIterators[vindex2] = edgeTreeRet.first; + edgeTreeIterators[vindex2] = edgeTree.insert(newedge); helpers[vindex2] = vindex; } else { //Search in T to find the edge ej directly left of vi. newedge.p1 = v->p; newedge.p2 = v->p; edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.begin()) { + if(edgeIter == edgeTree.front()) { error = true; break; } - edgeIter--; + edgeIter=edgeIter->prev(); //if helper(ej) is a merge vertex - if(vertextypes[helpers[edgeIter->index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { + if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { //Insert the diagonal connecting vi to helper(e j) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->index], + AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index], vertextypes, edgeTreeIterators, &edgeTree, helpers); } //helper(e j)�vi - helpers[edgeIter->index] = vindex; + helpers[edgeIter->get().index] = vindex; } break; } @@ -1308,8 +1311,8 @@ int TriangulatorPartition::MonotonePartition(list *inpolys, li //adds a diagonal to the doubly-connected list of vertices void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, - char *vertextypes, set::iterator *edgeTreeIterators, - set *edgeTree, long *helpers) + char *vertextypes, Set::Element **edgeTreeIterators, + Set *edgeTree, long *helpers) { long newindex1,newindex2; @@ -1337,13 +1340,13 @@ void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numverti vertextypes[newindex1] = vertextypes[index1]; edgeTreeIterators[newindex1] = edgeTreeIterators[index1]; helpers[newindex1] = helpers[index1]; - if(edgeTreeIterators[newindex1] != edgeTree->end()) - edgeTreeIterators[newindex1]->index = newindex1; + if(edgeTreeIterators[newindex1] != NULL) + edgeTreeIterators[newindex1]->get().index = newindex1; vertextypes[newindex2] = vertextypes[index2]; edgeTreeIterators[newindex2] = edgeTreeIterators[index2]; helpers[newindex2] = helpers[index2]; - if(edgeTreeIterators[newindex2] != edgeTree->end()) - edgeTreeIterators[newindex2]->index = newindex2; + if(edgeTreeIterators[newindex2] != NULL) + edgeTreeIterators[newindex2]->get().index = newindex2; } bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) { @@ -1354,8 +1357,12 @@ bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) { return false; } + + + + //sorts in the falling order of y values, if y is equal, x is used instead -bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) { +bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) const { if(vertices[index1].p.y > vertices[index2].p.y) return true; else if(vertices[index1].p.y == vertices[index2].p.y) { if(vertices[index1].p.x > vertices[index2].p.x) return true; @@ -1392,7 +1399,7 @@ bool TriangulatorPartition::ScanLineEdge::operator < (const ScanLineEdge & other //triangulates monotone polygon //O(n) time, O(n) space complexity -int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, list *triangles) { +int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, List *triangles) { long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex; Vector2 *points; long numpoints; @@ -1524,19 +1531,19 @@ int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, list *inpolys, list *triangles) { - list monotone; - list::iterator iter; +int TriangulatorPartition::Triangulate_MONO(List *inpolys, List *triangles) { + List monotone; + List::Element* iter; if(!MonotonePartition(inpolys,&monotone)) return 0; - for(iter = monotone.begin(); iter!=monotone.end();iter++) { - if(!TriangulateMonotone(&(*iter),triangles)) return 0; + for(iter = monotone.front(); iter;iter=iter->next()) { + if(!TriangulateMonotone(&(iter->get()),triangles)) return 0; } return 1; } -int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, list *triangles) { - list polys; +int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, List *triangles) { + List polys; polys.push_back(*poly); return Triangulate_MONO(&polys, triangles); diff --git a/core/math/triangulator.h b/core/math/triangulator.h index c34c445892..b6dd7e8236 100644 --- a/core/math/triangulator.h +++ b/core/math/triangulator.h @@ -22,9 +22,8 @@ #define TRIANGULATOR_H #include "math_2d.h" -#include -#include - +#include "list.h" +#include "set.h" //2D point structure @@ -119,11 +118,9 @@ protected: long next; }; - class VertexSorter{ - MonotoneVertex *vertices; - public: - VertexSorter(MonotoneVertex *v) : vertices(v) {} - bool operator() (long index1, long index2); + struct VertexSorter{ + mutable MonotoneVertex *vertices; + bool operator() (long index1, long index2) const; }; struct Diagonal { @@ -142,7 +139,7 @@ protected: struct DPState2 { bool visible; long weight; - std::list pairs; + List pairs; }; //edge that intersects the scanline @@ -182,11 +179,11 @@ protected: //helper functions for MonotonePartition bool Below(Vector2 &p1, Vector2 &p2); void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, - char *vertextypes, std::set::iterator *edgeTreeIterators, - std::set *edgeTree, long *helpers); + char *vertextypes, Set::Element **edgeTreeIterators, + Set *edgeTree, long *helpers); //triangulates a monotone polygon, used in Triangulate_MONO - int TriangulateMonotone(TriangulatorPoly *inPoly, std::list *triangles); + int TriangulateMonotone(TriangulatorPoly *inPoly, List *triangles); public: @@ -200,7 +197,7 @@ public: // vertices of all hole polys have to be in clockwise order // outpolys : a list of polygons without holes //returns 1 on success, 0 on failure - int RemoveHoles(std::list *inpolys, std::list *outpolys); + int RemoveHoles(List *inpolys, List *outpolys); //triangulates a polygon by ear clipping //time complexity O(n^2), n is the number of vertices @@ -210,7 +207,7 @@ public: // vertices have to be in counter-clockwise order // triangles : a list of triangles (result) //returns 1 on success, 0 on failure - int Triangulate_EC(TriangulatorPoly *poly, std::list *triangles); + int Triangulate_EC(TriangulatorPoly *poly, List *triangles); //triangulates a list of polygons that may contain holes by ear clipping algorithm //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon @@ -222,7 +219,7 @@ public: // vertices of all hole polys have to be in clockwise order // triangles : a list of triangles (result) //returns 1 on success, 0 on failure - int Triangulate_EC(std::list *inpolys, std::list *triangles); + int Triangulate_EC(List *inpolys, List *triangles); //creates an optimal polygon triangulation in terms of minimal edge length //time complexity: O(n^3), n is the number of vertices @@ -232,7 +229,7 @@ public: // vertices have to be in counter-clockwise order // triangles : a list of triangles (result) //returns 1 on success, 0 on failure - int Triangulate_OPT(TriangulatorPoly *poly, std::list *triangles); + int Triangulate_OPT(TriangulatorPoly *poly, List *triangles); //triangulates a polygons by firstly partitioning it into monotone polygons //time complexity: O(n*log(n)), n is the number of vertices @@ -242,7 +239,7 @@ public: // vertices have to be in counter-clockwise order // triangles : a list of triangles (result) //returns 1 on success, 0 on failure - int Triangulate_MONO(TriangulatorPoly *poly, std::list *triangles); + int Triangulate_MONO(TriangulatorPoly *poly, List *triangles); //triangulates a list of polygons by firstly partitioning them into monotone polygons //time complexity: O(n*log(n)), n is the number of vertices @@ -253,7 +250,7 @@ public: // vertices of all hole polys have to be in clockwise order // triangles : a list of triangles (result) //returns 1 on success, 0 on failure - int Triangulate_MONO(std::list *inpolys, std::list *triangles); + int Triangulate_MONO(List *inpolys, List *triangles); //creates a monotone partition of a list of polygons that can contain holes //time complexity: O(n*log(n)), n is the number of vertices @@ -264,7 +261,7 @@ public: // vertices of all hole polys have to be in clockwise order // monotonePolys : a list of monotone polygons (result) //returns 1 on success, 0 on failure - int MonotonePartition(std::list *inpolys, std::list *monotonePolys); + int MonotonePartition(List *inpolys, List *monotonePolys); //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm //the algorithm gives at most four times the number of parts as the optimal algorithm @@ -277,7 +274,7 @@ public: // vertices have to be in counter-clockwise order // parts : resulting list of convex polygons //returns 1 on success, 0 on failure - int ConvexPartition_HM(TriangulatorPoly *poly, std::list *parts); + int ConvexPartition_HM(TriangulatorPoly *poly, List *parts); //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm //the algorithm gives at most four times the number of parts as the optimal algorithm @@ -291,7 +288,7 @@ public: // vertices of all hole polys have to be in clockwise order // parts : resulting list of convex polygons //returns 1 on success, 0 on failure - int ConvexPartition_HM(std::list *inpolys, std::list *parts); + int ConvexPartition_HM(List *inpolys, List *parts); //optimal convex partitioning (in terms of number of resulting convex polygons) //using the Keil-Snoeyink algorithm @@ -302,7 +299,7 @@ public: // vertices have to be in counter-clockwise order // parts : resulting list of convex polygons //returns 1 on success, 0 on failure - int ConvexPartition_OPT(TriangulatorPoly *poly, std::list *parts); + int ConvexPartition_OPT(TriangulatorPoly *poly, List *parts); }; diff --git a/core/set.h b/core/set.h index d87f635577..95f38d7108 100644 --- a/core/set.h +++ b/core/set.h @@ -249,6 +249,37 @@ private: return (node!=_data._nil)?node:NULL; } + Element *_lower_bound(const T& p_value) const { + + Element *node = _data._root->left; + Element *prev = NULL; + C less; + + while(node!=_data._nil) { + prev=node; + + if (less(p_value,node->value)) + node=node->left; + else if (less(node->value,p_value)) + node=node->right; + else + break; // found + } + + if (node==_data._nil) { + if (prev==NULL) + return NULL; + if (less(prev->value,p_value)) { + + prev=prev->_next; + } + + return prev; + + } else + return node; + } + Element *_insert(const T& p_value, bool& r_exists) { @@ -582,6 +613,12 @@ public: return e; } + + Element *lower_bound(const T& p_value) const { + + return _lower_bound(p_value); + } + inline int size() const { return _data.size_cache; } int calculate_depth() const { diff --git a/core/variant.cpp b/core/variant.cpp index 2f0eca9e91..667a7d8648 100644 --- a/core/variant.cpp +++ b/core/variant.cpp @@ -2631,8 +2631,13 @@ Variant Variant::call(const StringName& p_method,VARIANT_ARG_DECLARE) { return ret; } +void Variant::construct_from_string(const String& p_string,Variant& r_value,ObjectConstruct p_obj_construct,void *p_construct_ud) { + + r_value=Variant(); +} -String Variant::get_construct_string() const { + +String Variant::get_construct_string(ObjectDeConstruct p_obj_deconstruct,void *p_deconstruct_ud) const { switch( type ) { @@ -2640,7 +2645,7 @@ String Variant::get_construct_string() const { case BOOL: return _data._bool ? "true" : "false"; case INT: return String::num(_data._int); case REAL: return String::num(_data._real); - case STRING: return "\""+*reinterpret_cast(_data._mem)+"\""; + case STRING: return "\""+reinterpret_cast(_data._mem)->c_escape()+"\""; case VECTOR2: return "Vector2("+operator Vector2()+")"; case RECT2: return "Rect2("+operator Rect2()+")"; case MATRIX32: return "Matrix32("+operator Matrix32()+")"; @@ -2651,7 +2656,7 @@ String Variant::get_construct_string() const { case QUAT: return "Quat("+operator Quat()+")"; case MATRIX3: return "Matrix3("+operator Matrix3()+")"; case TRANSFORM: return "Transform("+operator Transform()+")"; - case NODE_PATH: return "@\""+operator NodePath()+"\""; + case NODE_PATH: return "@\""+String(operator NodePath()).c_escape()+"\""; case INPUT_EVENT: return "InputEvent()"; case COLOR: return "Color("+String::num( operator Color().r)+","+String::num( operator Color().g)+","+String::num( operator Color().b)+","+String::num( operator Color().a)+")" ; case DICTIONARY: { @@ -2667,8 +2672,8 @@ String Variant::get_construct_string() const { for(List::Element *E=keys.front();E;E=E->next()) { _VariantStrPair sp; - sp.key=E->get().get_construct_string(); - sp.value=d[E->get()].get_construct_string(); + sp.key=E->get().get_construct_string(p_obj_deconstruct,p_deconstruct_ud); + sp.value=d[E->get()].get_construct_string(p_obj_deconstruct,p_deconstruct_ud); pairs.push_back(sp); } @@ -2686,50 +2691,50 @@ String Variant::get_construct_string() const { case VECTOR3_ARRAY: { DVector vec = operator DVector(); - String str="["; + String str="Vector3Array(["; for(int i=0;i0) str+=", "; str+=Variant( vec[i] ).get_construct_string(); } - return str+"]"; + return str+"])"; } break; case STRING_ARRAY: { DVector vec = operator DVector(); - String str="["; + String str="StringArray(["; for(int i=0;i0) str+=", "; str=str+=Variant( vec[i] ).get_construct_string(); } - return str+"]"; + return str+"])"; } break; case INT_ARRAY: { DVector vec = operator DVector(); - String str="["; + String str="IntArray(["; for(int i=0;i0) str+=", "; str=str+itos(vec[i]); } - return str+"]"; + return str+"])"; } break; case REAL_ARRAY: { DVector vec = operator DVector(); - String str="["; + String str="FloatArray(["; for(int i=0;i0) str+=", "; str=str+rtos(vec[i]); } - return str+"]"; + return str+"])"; } break; case ARRAY: { @@ -2738,16 +2743,20 @@ String Variant::get_construct_string() const { for (int i=0; iget_type()+".new()"; - else + if (_get_obj().obj) { + if (p_obj_deconstruct) { + return "Object(\""+p_obj_deconstruct(Variant(*this),p_deconstruct_ud).c_escape()+")"; + } else { + return _get_obj().obj->get_type()+".new()"; + } + } else return "null"; } break; diff --git a/core/variant.h b/core/variant.h index 47fc3f43ac..d5d4792422 100644 --- a/core/variant.h +++ b/core/variant.h @@ -419,7 +419,11 @@ public: static bool has_numeric_constant(Variant::Type p_type, const StringName& p_value); static int get_numeric_constant_value(Variant::Type p_type, const StringName& p_value); - String get_construct_string() const; + typedef String (*ObjectDeConstruct)(const Variant& p_object,void *ud); + typedef void (*ObjectConstruct)(const String& p_text,void *ud,Variant& r_value); + + String get_construct_string(ObjectDeConstruct p_obj_deconstruct=NULL,void *p_deconstruct_ud=NULL) const; + static void construct_from_string(const String& p_string,Variant& r_value,ObjectConstruct p_obj_construct=NULL,void *p_construct_ud=NULL); void operator=(const Variant& p_variant); // only this is enough for all the other types Variant(const Variant& p_variant); diff --git a/core/variant_construct_string.cpp b/core/variant_construct_string.cpp new file mode 100644 index 0000000000..0308fd3180 --- /dev/null +++ b/core/variant_construct_string.cpp @@ -0,0 +1,433 @@ + +#include "variant.h" + +class VariantConstruct { + + enum TokenType { + TK_CURLY_BRACKET_OPEN, + TK_CURLY_BRACKET_CLOSE, + TK_BRACKET_OPEN, + TK_BRACKET_CLOSE, + TK_IDENTIFIER, + TK_STRING, + TK_NUMBER, + TK_COLON, + TK_COMMA, + TK_EOF, + TK_MAX + }; + + enum Expecting { + + EXPECT_OBJECT, + EXPECT_OBJECT_KEY, + EXPECT_COLON, + EXPECT_OBJECT_VALUE, + }; + + struct Token { + + TokenType type; + Variant value; + }; + + static const char * tk_name[TK_MAX]; + + static String _print_var(const Variant& p_var); + + static Error _get_token(const CharType *p_str,int &index, int p_len,Token& r_token,int &line,String &r_err_str); + static Error _parse_value(Variant &value,Token& token,const CharType *p_str,int &index, int p_len,int &line,String &r_err_str,Variant::ObjectConstruct* p_construct,void* p_ud); + static Error _parse_array(Array &array,const CharType *p_str,int &index, int p_len,int &line,String &r_err_str,Variant::ObjectConstruct* p_construct,void* p_ud); + static Error _parse_dict(Dictionary &object,const CharType *p_str,int &index, int p_len,int &line,String &r_err_str,Variant::ObjectConstruct* p_construct,void* p_ud); + +public: + + static Error parse(const String& p_string,Variant& r_ret,String &r_err_str,int &r_err_line,Variant::ObjectConstruct* p_construct,void* p_ud); +}; + + +const char * VariantConstruct::tk_name[TK_MAX] = { + "'{'", + "'}'", + "'['", + "']'", + "identifier", + "string", + "number", + "':'", + "','", + "EOF", +}; + + + +Error VariantConstruct::_get_token(const CharType *p_str, int &idx, int p_len, Token& r_token,int &line,String &r_err_str) { + + while (true) { + switch(p_str[idx]) { + + case '\n': { + + line++; + idx++; + break; + }; + case 0: { + r_token.type=TK_EOF; + return OK; + } break; + case '{': { + + r_token.type=TK_CURLY_BRACKET_OPEN; + idx++; + return OK; + }; + case '}': { + + r_token.type=TK_CURLY_BRACKET_CLOSE; + idx++; + return OK; + }; + case '[': { + + r_token.type=TK_BRACKET_OPEN; + idx++; + return OK; + }; + case ']': { + + r_token.type=TK_BRACKET_CLOSE; + idx++; + return OK; + }; + case ':': { + + r_token.type=TK_COLON; + idx++; + return OK; + }; + case ',': { + + r_token.type=TK_COMMA; + idx++; + return OK; + }; + case '"': { + + idx++; + String str; + while(true) { + if (p_str[idx]==0) { + r_err_str="Unterminated String"; + return ERR_PARSE_ERROR; + } else if (p_str[idx]=='"') { + idx++; + break; + } else if (p_str[idx]=='\\') { + //escaped characters... + idx++; + CharType next = p_str[idx]; + if (next==0) { + r_err_str="Unterminated String"; + return ERR_PARSE_ERROR; + } + CharType res=0; + + switch(next) { + + case 'b': res=8; break; + case 't': res=9; break; + case 'n': res=10; break; + case 'f': res=12; break; + case 'r': res=13; break; + case '\"': res='\"'; break; + case '\\': res='\\'; break; + case '/': res='/'; break; //wtf + case 'u': { + //hexnumbarh - oct is deprecated + + + for(int j=0;j<4;j++) { + CharType c = p_str[idx+j+1]; + if (c==0) { + r_err_str="Unterminated String"; + return ERR_PARSE_ERROR; + } + if (!((c>='0' && c<='9') || (c>='a' && c<='f') || (c>='A' && c<='F'))) { + + r_err_str="Malformed hex constant in string"; + return ERR_PARSE_ERROR; + } + CharType v; + if (c>='0' && c<='9') { + v=c-'0'; + } else if (c>='a' && c<='f') { + v=c-'a'; + v+=10; + } else if (c>='A' && c<='F') { + v=c-'A'; + v+=10; + } else { + ERR_PRINT("BUG"); + v=0; + } + + res<<=4; + res|=v; + + + } + idx+=4; //will add at the end anyway + + + } break; + default: { + + r_err_str="Invalid escape sequence"; + return ERR_PARSE_ERROR; + } break; + } + + str+=res; + + } else { + if (p_str[idx]=='\n') + line++; + str+=p_str[idx]; + } + idx++; + } + + r_token.type=TK_STRING; + r_token.value=str; + return OK; + + } break; + default: { + + if (p_str[idx]<=32) { + idx++; + break; + } + + if (p_str[idx]=='-' || (p_str[idx]>='0' && p_str[idx]<='9')) { + //a number + const CharType *rptr; + double number = String::to_double(&p_str[idx],&rptr); + idx+=(rptr - &p_str[idx]); + r_token.type=TK_NUMBER; + r_token.value=number; + return OK; + + } else if ((p_str[idx]>='A' && p_str[idx]<='Z') || (p_str[idx]>='a' && p_str[idx]<='z')) { + + String id; + + while((p_str[idx]>='A' && p_str[idx]<='Z') || (p_str[idx]>='a' && p_str[idx]<='z')) { + + id+=p_str[idx]; + idx++; + } + + r_token.type=TK_IDENTIFIER; + r_token.value=id; + return OK; + } else { + r_err_str="Unexpected character."; + return ERR_PARSE_ERROR; + } + } + + } + } + + return ERR_PARSE_ERROR; +} + + + +Error VariantConstruct::_parse_value(Variant &value,Token& token,const CharType *p_str,int &index, int p_len,int &line,String &r_err_str,Variant::ObjectConstruct* p_construct,void* p_ud) { + + + if (token.type==TK_CURLY_BRACKET_OPEN) { + + Dictionary d; + Error err = _parse_dict(d,p_str,index,p_len,line,r_err_str,p_construct,p_ud); + if (err) + return err; + value=d; + return OK; + } else if (token.type==TK_BRACKET_OPEN) { + + Array a; + Error err = _parse_array(a,p_str,index,p_len,line,r_err_str,p_construct,p_ud); + if (err) + return err; + value=a; + return OK; + + } else if (token.type==TK_IDENTIFIER) { + + String id = token.value; + if (id=="true") + value=true; + else if (id=="false") + value=false; + else if (id=="null") + value=Variant(); + else { + r_err_str="Expected 'true','false' or 'null', got '"+id+"'."; + return ERR_PARSE_ERROR; + } + return OK; + + } else if (token.type==TK_NUMBER) { + + value=token.value; + return OK; + } else if (token.type==TK_STRING) { + + value=token.value; + return OK; + } else { + r_err_str="Expected value, got "+String(tk_name[token.type])+"."; + return ERR_PARSE_ERROR; + } + + return ERR_PARSE_ERROR; +} + + +Error VariantConstruct::_parse_array(Array &array,const CharType *p_str,int &index, int p_len,int &line,String &r_err_str,Variant::ObjectConstruct* p_construct,void* p_ud) { + + Token token; + bool need_comma=false; + + + while(index Date: Sun, 15 Feb 2015 11:26:31 -0300 Subject: fix return value of slide and reflect closes #1311 --- core/variant_call.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'core') diff --git a/core/variant_call.cpp b/core/variant_call.cpp index 3f2800494d..50a60390e5 100644 --- a/core/variant_call.cpp +++ b/core/variant_call.cpp @@ -1263,8 +1263,8 @@ _VariantCall::addfunc(Variant::m_vtype,Variant::m_ret,_SCS(#m_method),VCALL(m_cl ADDFUNC1(VECTOR2,VECTOR2,Vector2,snapped,VECTOR2,"by",varray()); ADDFUNC0(VECTOR2,REAL,Vector2,get_aspect,varray()); ADDFUNC1(VECTOR2,REAL,Vector2,dot,VECTOR2,"with",varray()); - ADDFUNC1(VECTOR2,REAL,Vector2,slide,VECTOR2,"vec",varray()); - ADDFUNC1(VECTOR2,REAL,Vector2,reflect,VECTOR2,"vec",varray()); + ADDFUNC1(VECTOR2,VECTOR2,Vector2,slide,VECTOR2,"vec",varray()); + ADDFUNC1(VECTOR2,VECTOR2,Vector2,reflect,VECTOR2,"vec",varray()); //ADDFUNC1(VECTOR2,REAL,Vector2,cross,VECTOR2,"with",varray()); ADDFUNC0(RECT2,REAL,Rect2,get_area,varray()); -- cgit v1.2.3 From 4333aa240c68f22b235981bed56d11a592fdfd1d Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Sun, 15 Feb 2015 12:38:25 -0300 Subject: Godot UI is quick and snappy again! Changed linked listed sort to use auxiliary memory this fixes user interface performance issues. --- core/list.h | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 54 insertions(+), 2 deletions(-) (limited to 'core') diff --git a/core/list.h b/core/list.h index f581feb735..0e4ba71ac4 100644 --- a/core/list.h +++ b/core/list.h @@ -30,7 +30,7 @@ #define GLOBALS_LIST_H #include "os/memory.h" - +#include "sort.h" /** * Generic Templatized Linked List Implementation. @@ -551,7 +551,7 @@ public: } template - void sort_custom() { + void sort_custom_inplace() { if(size()<2) return; @@ -603,6 +603,58 @@ public: _data->last=to; } + template + struct AuxiliaryComparator { + + C compare; + _FORCE_INLINE_ bool operator()(const Element *A,const Element* B) const { + + return compare(A->value,B->value); + } + }; + + template + void sort_custom() { + + //this version uses auxiliary memory for speed. + //if you don't want to use auxiliary memory, use the in_place version + + int s = size(); + if(s<2) + return; + + + Element **aux_buffer = memnew_arr(Element*,s); + + int idx=0; + for(Element *E=front();E;E=E->next_ptr) { + + aux_buffer[idx]=E; + idx++; + } + + SortArray > sort; + sort.sort(aux_buffer,s); + + _data->first=aux_buffer[0]; + aux_buffer[0]->prev_ptr=NULL; + aux_buffer[0]->next_ptr=aux_buffer[1]; + + _data->last=aux_buffer[s-1]; + aux_buffer[s-1]->prev_ptr=aux_buffer[s-2]; + aux_buffer[s-1]->next_ptr=NULL; + + for(int i=1;iprev_ptr=aux_buffer[i-1]; + aux_buffer[i]->next_ptr=aux_buffer[i+1]; + + } + + memdelete_arr(aux_buffer); + } + + /** * copy constructor for the list */ -- cgit v1.2.3 From 2478935f9654de9b516f61a43e1b0e0f0d97fb26 Mon Sep 17 00:00:00 2001 From: Felix Laurie von Massenbach Date: Sun, 15 Feb 2015 18:09:11 +0000 Subject: Fix a shadow declaration. --- core/list.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'core') diff --git a/core/list.h b/core/list.h index 0e4ba71ac4..ef30e43d21 100644 --- a/core/list.h +++ b/core/list.h @@ -607,9 +607,9 @@ public: struct AuxiliaryComparator { C compare; - _FORCE_INLINE_ bool operator()(const Element *A,const Element* B) const { + _FORCE_INLINE_ bool operator()(const Element *a,const Element* b) const { - return compare(A->value,B->value); + return compare(a->value,b->value); } }; -- cgit v1.2.3 From 5ef3f7392faf0d2d9c136fc176f7a08cb774fe40 Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Wed, 18 Feb 2015 19:39:44 -0300 Subject: support for light and normal mapping in 2D --- core/math/math_2d.h | 162 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 160 insertions(+), 2 deletions(-) (limited to 'core') diff --git a/core/math/math_2d.h b/core/math/math_2d.h index fa40d305f5..5bc1b5f0be 100644 --- a/core/math/math_2d.h +++ b/core/math/math_2d.h @@ -159,8 +159,8 @@ struct Vector2 { operator String() const { return String::num(x)+","+String::num(y); } - inline Vector2(float p_x,float p_y) { x=p_x; y=p_y; } - inline Vector2() { x=0; y=0; } + _FORCE_INLINE_ Vector2(float p_x,float p_y) { x=p_x; y=p_y; } + _FORCE_INLINE_ Vector2() { x=0; y=0; } }; _FORCE_INLINE_ Vector2 Vector2::plane_project(real_t p_d, const Vector2& p_vec) const { @@ -198,6 +198,8 @@ Vector2 Vector2::linear_interpolate(const Vector2& p_a, const Vector2& p_b,float typedef Vector2 Size2; typedef Vector2 Point2; +struct Matrix32; + struct Rect2 { @@ -224,6 +226,8 @@ struct Rect2 { return true; } + _FORCE_INLINE_ bool intersects_transformed(const Matrix32& p_xform, const Rect2& p_rect) const; + bool intersects_segment(const Point2& p_from, const Point2& p_to, Point2* r_pos=NULL, Point2* r_normal=NULL) const; inline bool encloses(const Rect2& p_rect) const { @@ -597,6 +601,160 @@ struct Matrix32 { }; +bool Rect2::intersects_transformed(const Matrix32& p_xform, const Rect2& p_rect) const { + + //SAT intersection between local and transformed rect2 + + Vector2 xf_points[4]={ + p_xform.xform(p_rect.pos), + p_xform.xform(Vector2(p_rect.pos.x+p_rect.size.x,p_rect.pos.y)), + p_xform.xform(Vector2(p_rect.pos.x,p_rect.pos.y+p_rect.size.y)), + p_xform.xform(Vector2(p_rect.pos.x+p_rect.size.x,p_rect.pos.y+p_rect.size.y)), + }; + + real_t low_limit; + + //base rect2 first (faster) + + if (xf_points[0].y>pos.y) + goto next1; + if (xf_points[1].y>pos.y) + goto next1; + if (xf_points[2].y>pos.y) + goto next1; + if (xf_points[3].y>pos.y) + goto next1; + + return false; + + next1: + + low_limit=pos.y+size.y; + + if (xf_points[0].ypos.x) + goto next3; + if (xf_points[1].x>pos.x) + goto next3; + if (xf_points[2].x>pos.x) + goto next3; + if (xf_points[3].x>pos.x) + goto next3; + + return false; + + next3: + + low_limit=pos.x+size.x; + + if (xf_points[0].x maxb ) + return false; + if ( minb > maxa ) + return false; + + maxa=p_xform.elements[1].dot(xf_points2[0]); + mina=maxa; + + dp = p_xform.elements[1].dot(xf_points2[1]); + maxa=MAX(dp,maxa); + mina=MIN(dp,mina); + + dp = p_xform.elements[1].dot(xf_points2[2]); + maxa=MAX(dp,maxa); + mina=MIN(dp,mina); + + dp = p_xform.elements[1].dot(xf_points2[3]); + maxa=MAX(dp,maxa); + mina=MIN(dp,mina); + + maxb=p_xform.elements[1].dot(xf_points[0]); + minb=maxb; + + dp = p_xform.elements[1].dot(xf_points[1]); + maxb=MAX(dp,maxb); + minb=MIN(dp,minb); + + dp = p_xform.elements[1].dot(xf_points[2]); + maxb=MAX(dp,maxb); + minb=MIN(dp,minb); + + dp = p_xform.elements[1].dot(xf_points[3]); + maxb=MAX(dp,maxb); + minb=MIN(dp,minb); + + + if ( mina > maxb ) + return false; + if ( minb > maxa ) + return false; + + + return true; + +} Vector2 Matrix32::basis_xform(const Vector2& v) const { -- cgit v1.2.3 From a1f715a4da71fbc2b7d6fad68624bf8b22c6da17 Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Mon, 2 Mar 2015 00:54:10 -0300 Subject: support for 2D shadow casters Added support for 2D shadow casters. *DANGER* Shaders in CanvasItem CHANGED, if you are using shader in a CanvasItem and pull this, you will lose them. Shaders now work through a 2D material system similar to 3D. If you don't want to lose the 2D shader code, save the shader as a .shd, then create a material in CanvasItem and re-assign the shader. --- core/io/resource_format_binary.cpp | 10 ++++++++++ core/io/resource_format_xml.cpp | 5 +++++ core/math/camera_matrix.cpp | 19 ++++++++++++++++++- core/variant_op.cpp | 3 +++ 4 files changed, 36 insertions(+), 1 deletion(-) (limited to 'core') diff --git a/core/io/resource_format_binary.cpp b/core/io/resource_format_binary.cpp index e2371fe24f..ead6984650 100644 --- a/core/io/resource_format_binary.cpp +++ b/core/io/resource_format_binary.cpp @@ -1778,6 +1778,11 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path,const RES& p_ f->store_32(VERSION_MINOR); f->store_32(FORMAT_VERSION); + if (f->get_error()!=OK && f->get_error()!=ERR_FILE_EOF) { + f->close(); + return ERR_CANT_CREATE; + } + //f->store_32(saved_resources.size()+external_resources.size()); // load steps -not needed save_unicode_string(p_resource->get_type()); uint64_t md_at = f->get_pos(); @@ -1910,6 +1915,11 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path,const RES& p_ f->store_buffer((const uint8_t*)"RSRC",4); //magic at end + if (f->get_error()!=OK && f->get_error()!=ERR_FILE_EOF) { + f->close(); + return ERR_CANT_CREATE; + } + f->close(); diff --git a/core/io/resource_format_xml.cpp b/core/io/resource_format_xml.cpp index 75384d4ab6..033b4d5e5a 100644 --- a/core/io/resource_format_xml.cpp +++ b/core/io/resource_format_xml.cpp @@ -2592,6 +2592,11 @@ Error ResourceFormatSaverXMLInstance::save(const String &p_path,const RES& p_res } exit_tag("resource_file"); + if (f->get_error()!=OK && f->get_error()!=ERR_FILE_EOF) { + f->close(); + return ERR_CANT_CREATE; + } + f->close(); //memdelete(f); diff --git a/core/math/camera_matrix.cpp b/core/math/camera_matrix.cpp index a60dea7379..fbe5f8c741 100644 --- a/core/math/camera_matrix.cpp +++ b/core/math/camera_matrix.cpp @@ -121,7 +121,7 @@ void CameraMatrix::set_orthogonal(float p_size, float p_aspect, float p_znear, f void CameraMatrix::set_frustum(float p_left, float p_right, float p_bottom, float p_top, float p_near, float p_far) { - +#if 0 ///@TODO, give a check to this. I'm not sure if it's working. set_identity(); @@ -133,10 +133,27 @@ void CameraMatrix::set_frustum(float p_left, float p_right, float p_bottom, floa matrix[2][3]=-(2*p_far*p_near) / (p_far-p_near); matrix[3][2]=-1; matrix[3][3]=0; +#else + float *te = &matrix[0][0]; + float x = 2 * p_near / ( p_right - p_left ); + float y = 2 * p_near / ( p_top - p_bottom ); + + float a = ( p_right + p_left ) / ( p_right - p_left ); + float b = ( p_top + p_bottom ) / ( p_top - p_bottom ); + float c = - ( p_far + p_near ) / ( p_far - p_near ); + float d = - 2 * p_far * p_near / ( p_far - p_near ); + + te[0] = x; te[4] = 0; te[8] = a; te[12] = 0; + te[1] = 0; te[5] = y; te[9] = b; te[13] = 0; + te[2] = 0; te[6] = 0; te[10] = c; te[14] = d; + te[3] = 0; te[7] = 0; te[11] = - 1; te[15] = 0; + +#endif } + float CameraMatrix::get_z_far() const { const float * matrix = (const float*)this->matrix; diff --git a/core/variant_op.cpp b/core/variant_op.cpp index 21bbc8c7ee..d6129e150c 100644 --- a/core/variant_op.cpp +++ b/core/variant_op.cpp @@ -552,6 +552,9 @@ void Variant::evaluate(const Operator& p_op, const Variant& p_a, const Variant& if (p_b.type==MATRIX32) { _RETURN( *p_a._data._matrix32 * *p_b._data._matrix32 ); }; + if (p_b.type==VECTOR2) { + _RETURN( p_a._data._matrix32->xform( *(const Vector2*)p_b._data._mem) ); + }; r_valid=false; return; } break; -- cgit v1.2.3