summaryrefslogtreecommitdiff
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/bind/core_bind.cpp14
-rw-r--r--core/bind/core_bind.h4
-rw-r--r--core/dvector.h17
-rw-r--r--core/io/http_client.cpp43
-rw-r--r--core/io/http_client.h6
-rw-r--r--core/io/resource_format_binary.cpp10
-rw-r--r--core/io/resource_format_xml.cpp5
-rw-r--r--core/list.h56
-rw-r--r--core/math/camera_matrix.cpp19
-rw-r--r--core/math/geometry.h14
-rw-r--r--core/math/math_2d.h162
-rw-r--r--core/math/triangulator.cpp1550
-rw-r--r--core/math/triangulator.h306
-rw-r--r--core/os/input.cpp2
-rw-r--r--core/resource.cpp2
-rw-r--r--core/set.h37
-rw-r--r--core/ustring.cpp296
-rw-r--r--core/ustring.h8
-rw-r--r--core/variant.cpp43
-rw-r--r--core/variant.h6
-rw-r--r--core/variant_call.cpp4
-rw-r--r--core/variant_construct_string.cpp433
-rw-r--r--core/variant_op.cpp41
23 files changed, 3036 insertions, 42 deletions
diff --git a/core/bind/core_bind.cpp b/core/bind/core_bind.cpp
index 0c5d21b4f6..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);
@@ -838,6 +845,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<Vector3> _Geometry::segment_intersects_sphere( const Vector3& p_from, const Vector3& p_to, const Vector3& p_sphere_pos,real_t p_sphere_radius) {
DVector<Vector3> r;
@@ -938,6 +951,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..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();
@@ -248,6 +250,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<Vector3> segment_intersects_sphere( const Vector3& p_from, const Vector3& p_to, const Vector3& p_sphere_pos,real_t p_sphere_radius);
DVector<Vector3> segment_intersects_cylinder( const Vector3& p_from, const Vector3& p_to, float p_height,float p_radius);
DVector<Vector3> segment_intersects_convex(const Vector3& p_from, const Vector3& p_to,const Vector<Plane>& 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/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();
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/list.h b/core/list.h
index f581feb735..ef30e43d21 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<class C>
- void sort_custom() {
+ void sort_custom_inplace() {
if(size()<2)
return;
@@ -603,6 +603,58 @@ public:
_data->last=to;
}
+ template<class C>
+ struct AuxiliaryComparator {
+
+ C compare;
+ _FORCE_INLINE_ bool operator()(const Element *a,const Element* b) const {
+
+ return compare(a->value,b->value);
+ }
+ };
+
+ template<class C>
+ 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<Element*,AuxiliaryComparator<C> > 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;i<s-1;i++) {
+
+ aux_buffer[i]->prev_ptr=aux_buffer[i-1];
+ aux_buffer[i]->next_ptr=aux_buffer[i+1];
+
+ }
+
+ memdelete_arr(aux_buffer);
+ }
+
+
/**
* copy constructor for the list
*/
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/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/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].y<low_limit)
+ goto next2;
+ if (xf_points[1].y<low_limit)
+ goto next2;
+ if (xf_points[2].y<low_limit)
+ goto next2;
+ if (xf_points[3].y<low_limit)
+ goto next2;
+
+ return false;
+
+ next2:
+
+ if (xf_points[0].x>pos.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<low_limit)
+ goto next4;
+ if (xf_points[1].x<low_limit)
+ goto next4;
+ if (xf_points[2].x<low_limit)
+ goto next4;
+ if (xf_points[3].x<low_limit)
+ goto next4;
+
+ return false;
+
+ next4:
+
+ Vector2 xf_points2[4]={
+ pos,
+ Vector2(pos.x+size.x,pos.y),
+ Vector2(pos.x,pos.y+size.y),
+ Vector2(pos.x+size.x,pos.y+size.y),
+ };
+
+ real_t maxa=p_xform.elements[0].dot(xf_points2[0]);
+ real_t mina=maxa;
+
+ real_t dp = p_xform.elements[0].dot(xf_points2[1]);
+ maxa=MAX(dp,maxa);
+ mina=MIN(dp,mina);
+
+ dp = p_xform.elements[0].dot(xf_points2[2]);
+ maxa=MAX(dp,maxa);
+ mina=MIN(dp,mina);
+
+ dp = p_xform.elements[0].dot(xf_points2[3]);
+ maxa=MAX(dp,maxa);
+ mina=MIN(dp,mina);
+
+ real_t maxb=p_xform.elements[0].dot(xf_points[0]);
+ real_t minb=maxb;
+
+ dp = p_xform.elements[0].dot(xf_points[1]);
+ maxb=MAX(dp,maxb);
+ minb=MIN(dp,minb);
+
+ dp = p_xform.elements[0].dot(xf_points[2]);
+ maxb=MAX(dp,maxb);
+ minb=MIN(dp,minb);
+
+ dp = p_xform.elements[0].dot(xf_points[3]);
+ maxb=MAX(dp,maxb);
+ minb=MIN(dp,minb);
+
+
+ if ( mina > 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 {
diff --git a/core/math/triangulator.cpp b/core/math/triangulator.cpp
new file mode 100644
index 0000000000..8f82d76823
--- /dev/null
+++ b/core/math/triangulator.cpp
@@ -0,0 +1,1550 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//Permission is hereby granted, free of charge, to any person obtaining a copy
+//of this software and associated documentation files (the "Software"), to deal
+//in the Software without restriction, including without limitation the rights
+//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+//copies of the Software, and to permit persons to whom the Software is
+//furnished to do so, subject to the following conditions:
+//
+//The above copyright notice and this permission notice shall be included in
+//all copies or substantial portions of the Software.
+//
+//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+//THE SOFTWARE.
+
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#include "triangulator.h"
+
+
+#define TRIANGULATOR_VERTEXTYPE_REGULAR 0
+#define TRIANGULATOR_VERTEXTYPE_START 1
+#define TRIANGULATOR_VERTEXTYPE_END 2
+#define TRIANGULATOR_VERTEXTYPE_SPLIT 3
+#define TRIANGULATOR_VERTEXTYPE_MERGE 4
+
+TriangulatorPoly::TriangulatorPoly() {
+ hole = false;
+ numpoints = 0;
+ points = NULL;
+}
+
+TriangulatorPoly::~TriangulatorPoly() {
+ if(points) delete [] points;
+}
+
+void TriangulatorPoly::Clear() {
+ if(points) delete [] points;
+ hole = false;
+ numpoints = 0;
+ points = NULL;
+}
+
+void TriangulatorPoly::Init(long numpoints) {
+ Clear();
+ this->numpoints = numpoints;
+ points = new Vector2[numpoints];
+}
+
+void TriangulatorPoly::Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3) {
+ Init(3);
+ points[0] = p1;
+ points[1] = p2;
+ points[2] = p3;
+}
+
+TriangulatorPoly::TriangulatorPoly(const TriangulatorPoly &src) {
+ hole = src.hole;
+ numpoints = src.numpoints;
+ points = new Vector2[numpoints];
+ memcpy(points, src.points, numpoints*sizeof(Vector2));
+}
+
+TriangulatorPoly& TriangulatorPoly::operator=(const TriangulatorPoly &src) {
+ Clear();
+ hole = src.hole;
+ numpoints = src.numpoints;
+ points = new Vector2[numpoints];
+ memcpy(points, src.points, numpoints*sizeof(Vector2));
+ return *this;
+}
+
+int TriangulatorPoly::GetOrientation() {
+ long i1,i2;
+ real_t area = 0;
+ for(i1=0; i1<numpoints; i1++) {
+ i2 = i1+1;
+ if(i2 == numpoints) i2 = 0;
+ area += points[i1].x * points[i2].y - points[i1].y * points[i2].x;
+ }
+ if(area>0) return TRIANGULATOR_CCW;
+ if(area<0) return TRIANGULATOR_CW;
+ return 0;
+}
+
+void TriangulatorPoly::SetOrientation(int orientation) {
+ int polyorientation = GetOrientation();
+ if(polyorientation&&(polyorientation!=orientation)) {
+ Invert();
+ }
+}
+
+void TriangulatorPoly::Invert() {
+ long i;
+ Vector2 *invpoints;
+
+ invpoints = new Vector2[numpoints];
+ for(i=0;i<numpoints;i++) {
+ invpoints[i] = points[numpoints-i-1];
+ }
+
+ delete [] points;
+ points = invpoints;
+}
+
+Vector2 TriangulatorPartition::Normalize(const Vector2 &p) {
+ Vector2 r;
+ real_t n = sqrt(p.x*p.x + p.y*p.y);
+ if(n!=0) {
+ r = p/n;
+ } else {
+ r.x = 0;
+ r.y = 0;
+ }
+ return r;
+}
+
+real_t TriangulatorPartition::Distance(const Vector2 &p1, const Vector2 &p2) {
+ real_t dx,dy;
+ dx = p2.x - p1.x;
+ dy = p2.y - p1.y;
+ return(sqrt(dx*dx + dy*dy));
+}
+
+//checks if two lines intersect
+int TriangulatorPartition::Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22) {
+ if((p11.x == p21.x)&&(p11.y == p21.y)) return 0;
+ if((p11.x == p22.x)&&(p11.y == p22.y)) return 0;
+ if((p12.x == p21.x)&&(p12.y == p21.y)) return 0;
+ if((p12.x == p22.x)&&(p12.y == p22.y)) return 0;
+
+ Vector2 v1ort,v2ort,v;
+ real_t dot11,dot12,dot21,dot22;
+
+ v1ort.x = p12.y-p11.y;
+ v1ort.y = p11.x-p12.x;
+
+ v2ort.x = p22.y-p21.y;
+ v2ort.y = p21.x-p22.x;
+
+ v = p21-p11;
+ dot21 = v.x*v1ort.x + v.y*v1ort.y;
+ v = p22-p11;
+ dot22 = v.x*v1ort.x + v.y*v1ort.y;
+
+ v = p11-p21;
+ dot11 = v.x*v2ort.x + v.y*v2ort.y;
+ v = p12-p21;
+ dot12 = v.x*v2ort.x + v.y*v2ort.y;
+
+ if(dot11*dot12>0) return 0;
+ if(dot21*dot22>0) return 0;
+
+ return 1;
+}
+
+//removes holes from inpolys by merging them with non-holes
+int TriangulatorPartition::RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys) {
+ List<TriangulatorPoly> polys;
+ List<TriangulatorPoly>::Element *holeiter,*polyiter,*iter,*iter2;
+ long i,i2,holepointindex,polypointindex;
+ Vector2 holepoint,polypoint,bestpolypoint;
+ Vector2 linep1,linep2;
+ Vector2 v1,v2;
+ TriangulatorPoly newpoly;
+ bool hasholes;
+ bool pointvisible;
+ bool pointfound;
+
+ //check for trivial case (no holes)
+ hasholes = false;
+ for(iter = inpolys->front(); iter; iter=iter->next()) {
+ if(iter->get().IsHole()) {
+ hasholes = true;
+ break;
+ }
+ }
+ if(!hasholes) {
+ for(iter = inpolys->front(); iter; iter=iter->next()) {
+ outpolys->push_back(iter->get());
+ }
+ return 1;
+ }
+
+ polys = *inpolys;
+
+ while(1) {
+ //find the hole point with the largest x
+ hasholes = false;
+ for(iter = polys.front(); iter; iter=iter->next()) {
+ if(!iter->get().IsHole()) continue;
+
+ if(!hasholes) {
+ hasholes = true;
+ holeiter = iter;
+ holepointindex = 0;
+ }
+
+ for(i=0; i < iter->get().GetNumPoints(); i++) {
+ if(iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) {
+ holeiter = iter;
+ holepointindex = i;
+ }
+ }
+ }
+ if(!hasholes) break;
+ holepoint = holeiter->get().GetPoint(holepointindex);
+
+ pointfound = false;
+ for(iter = polys.front(); iter; iter=iter->next()) {
+ if(iter->get().IsHole()) continue;
+ for(i=0; i < iter->get().GetNumPoints(); i++) {
+ if(iter->get().GetPoint(i).x <= holepoint.x) continue;
+ if(!InCone(iter->get().GetPoint((i+iter->get().GetNumPoints()-1)%(iter->get().GetNumPoints())),
+ iter->get().GetPoint(i),
+ iter->get().GetPoint((i+1)%(iter->get().GetNumPoints())),
+ holepoint))
+ continue;
+ polypoint = iter->get().GetPoint(i);
+ if(pointfound) {
+ v1 = Normalize(polypoint-holepoint);
+ v2 = Normalize(bestpolypoint-holepoint);
+ if(v2.x > v1.x) continue;
+ }
+ pointvisible = true;
+ for(iter2 = polys.front(); iter2; iter2=iter2->next()) {
+ if(iter2->get().IsHole()) continue;
+ for(i2=0; i2 < iter2->get().GetNumPoints(); i2++) {
+ linep1 = iter2->get().GetPoint(i2);
+ linep2 = iter2->get().GetPoint((i2+1)%(iter2->get().GetNumPoints()));
+ if(Intersects(holepoint,polypoint,linep1,linep2)) {
+ pointvisible = false;
+ break;
+ }
+ }
+ if(!pointvisible) break;
+ }
+ if(pointvisible) {
+ pointfound = true;
+ bestpolypoint = polypoint;
+ polyiter = iter;
+ polypointindex = i;
+ }
+ }
+ }
+
+ if(!pointfound) return 0;
+
+ newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2);
+ i2 = 0;
+ for(i=0;i<=polypointindex;i++) {
+ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+ for(i=0;i<=holeiter->get().GetNumPoints();i++) {
+ newpoly[i2] = holeiter->get().GetPoint((i+holepointindex)%holeiter->get().GetNumPoints());
+ i2++;
+ }
+ for(i=polypointindex;i<polyiter->get().GetNumPoints();i++) {
+ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+
+ polys.erase(holeiter);
+ polys.erase(polyiter);
+ polys.push_back(newpoly);
+ }
+
+ for(iter = polys.front(); iter; iter=iter->next()) {
+ outpolys->push_back(iter->get());
+ }
+
+ return 1;
+}
+
+bool TriangulatorPartition::IsConvex(Vector2& p1, Vector2& p2, Vector2& p3) {
+ real_t tmp;
+ tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+ if(tmp>0) return 1;
+ else return 0;
+}
+
+bool TriangulatorPartition::IsReflex(Vector2& p1, Vector2& p2, Vector2& p3) {
+ real_t tmp;
+ tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+ if(tmp<0) return 1;
+ else return 0;
+}
+
+bool TriangulatorPartition::IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p) {
+ if(IsConvex(p1,p,p2)) return false;
+ if(IsConvex(p2,p,p3)) return false;
+ if(IsConvex(p3,p,p1)) return false;
+ return true;
+}
+
+bool TriangulatorPartition::InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p) {
+ bool convex;
+
+ convex = IsConvex(p1,p2,p3);
+
+ if(convex) {
+ if(!IsConvex(p1,p2,p)) return false;
+ if(!IsConvex(p2,p3,p)) return false;
+ return true;
+ } else {
+ if(IsConvex(p1,p2,p)) return true;
+ if(IsConvex(p2,p3,p)) return true;
+ return false;
+ }
+}
+
+bool TriangulatorPartition::InCone(PartitionVertex *v, Vector2 &p) {
+ Vector2 p1,p2,p3;
+
+ p1 = v->previous->p;
+ p2 = v->p;
+ p3 = v->next->p;
+
+ return InCone(p1,p2,p3,p);
+}
+
+void TriangulatorPartition::UpdateVertexReflexity(PartitionVertex *v) {
+ PartitionVertex *v1,*v3;
+ v1 = v->previous;
+ v3 = v->next;
+ v->isConvex = !IsReflex(v1->p,v->p,v3->p);
+}
+
+void TriangulatorPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) {
+ long i;
+ PartitionVertex *v1,*v3;
+ Vector2 vec1,vec3;
+
+ v1 = v->previous;
+ v3 = v->next;
+
+ v->isConvex = IsConvex(v1->p,v->p,v3->p);
+
+ vec1 = Normalize(v1->p - v->p);
+ vec3 = Normalize(v3->p - v->p);
+ v->angle = vec1.x*vec3.x + vec1.y*vec3.y;
+
+ if(v->isConvex) {
+ v->isEar = true;
+ for(i=0;i<numvertices;i++) {
+ if((vertices[i].p.x==v->p.x)&&(vertices[i].p.y==v->p.y)) continue;
+ if((vertices[i].p.x==v1->p.x)&&(vertices[i].p.y==v1->p.y)) continue;
+ if((vertices[i].p.x==v3->p.x)&&(vertices[i].p.y==v3->p.y)) continue;
+ if(IsInside(v1->p,v->p,v3->p,vertices[i].p)) {
+ v->isEar = false;
+ break;
+ }
+ }
+ } else {
+ v->isEar = false;
+ }
+}
+
+//triangulation by ear removal
+int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
+ long numvertices;
+ PartitionVertex *vertices;
+ PartitionVertex *ear;
+ TriangulatorPoly triangle;
+ long i,j;
+ bool earfound;
+
+ if(poly->GetNumPoints() < 3) return 0;
+ if(poly->GetNumPoints() == 3) {
+ triangles->push_back(*poly);
+ return 1;
+ }
+
+ numvertices = poly->GetNumPoints();
+
+ vertices = new PartitionVertex[numvertices];
+ for(i=0;i<numvertices;i++) {
+ vertices[i].isActive = true;
+ vertices[i].p = poly->GetPoint(i);
+ if(i==(numvertices-1)) vertices[i].next=&(vertices[0]);
+ else vertices[i].next=&(vertices[i+1]);
+ if(i==0) vertices[i].previous = &(vertices[numvertices-1]);
+ else vertices[i].previous = &(vertices[i-1]);
+ }
+ for(i=0;i<numvertices;i++) {
+ UpdateVertex(&vertices[i],vertices,numvertices);
+ }
+
+ for(i=0;i<numvertices-3;i++) {
+ earfound = false;
+ //find the most extruded ear
+ for(j=0;j<numvertices;j++) {
+ if(!vertices[j].isActive) continue;
+ if(!vertices[j].isEar) continue;
+ if(!earfound) {
+ earfound = true;
+ ear = &(vertices[j]);
+ } else {
+ if(vertices[j].angle > ear->angle) {
+ ear = &(vertices[j]);
+ }
+ }
+ }
+ if(!earfound) {
+ delete [] vertices;
+ return 0;
+ }
+
+ triangle.Triangle(ear->previous->p,ear->p,ear->next->p);
+ triangles->push_back(triangle);
+
+ ear->isActive = false;
+ ear->previous->next = ear->next;
+ ear->next->previous = ear->previous;
+
+ if(i==numvertices-4) break;
+
+ UpdateVertex(ear->previous,vertices,numvertices);
+ UpdateVertex(ear->next,vertices,numvertices);
+ }
+ for(i=0;i<numvertices;i++) {
+ if(vertices[i].isActive) {
+ triangle.Triangle(vertices[i].previous->p,vertices[i].p,vertices[i].next->p);
+ triangles->push_back(triangle);
+ break;
+ }
+ }
+
+ delete [] vertices;
+
+ return 1;
+}
+
+int TriangulatorPartition::Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) {
+ List<TriangulatorPoly> outpolys;
+ List<TriangulatorPoly>::Element*iter;
+
+ if(!RemoveHoles(inpolys,&outpolys)) return 0;
+ for(iter=outpolys.front();iter;iter=iter->next()) {
+ if(!Triangulate_EC(&(iter->get()),triangles)) return 0;
+ }
+ return 1;
+}
+
+int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) {
+ List<TriangulatorPoly> triangles;
+ List<TriangulatorPoly>::Element *iter1,*iter2;
+ TriangulatorPoly *poly1,*poly2;
+ TriangulatorPoly newpoly;
+ Vector2 d1,d2,p1,p2,p3;
+ long i11,i12,i21,i22,i13,i23,j,k;
+ bool isdiagonal;
+ long numreflex;
+
+ //check if the poly is already convex
+ numreflex = 0;
+ for(i11=0;i11<poly->GetNumPoints();i11++) {
+ if(i11==0) i12 = poly->GetNumPoints()-1;
+ else i12=i11-1;
+ if(i11==(poly->GetNumPoints()-1)) i13=0;
+ else i13=i11+1;
+ if(IsReflex(poly->GetPoint(i12),poly->GetPoint(i11),poly->GetPoint(i13))) {
+ numreflex = 1;
+ break;
+ }
+ }
+ if(numreflex == 0) {
+ parts->push_back(*poly);
+ return 1;
+ }
+
+ if(!Triangulate_EC(poly,&triangles)) return 0;
+
+ for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) {
+ poly1 = &(iter1->get());
+ for(i11=0;i11<poly1->GetNumPoints();i11++) {
+ d1 = poly1->GetPoint(i11);
+ i12 = (i11+1)%(poly1->GetNumPoints());
+ d2 = poly1->GetPoint(i12);
+
+ isdiagonal = false;
+ for(iter2 = iter1; iter2 ; iter2=iter2->next()) {
+ if(iter1 == iter2) continue;
+ poly2 = &(iter2->get());
+
+ for(i21=0;i21<poly2->GetNumPoints();i21++) {
+ if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue;
+ i22 = (i21+1)%(poly2->GetNumPoints());
+ if((d1.x != poly2->GetPoint(i22).x)||(d1.y != poly2->GetPoint(i22).y)) continue;
+ isdiagonal = true;
+ break;
+ }
+ if(isdiagonal) break;
+ }
+
+ if(!isdiagonal) continue;
+
+ p2 = poly1->GetPoint(i11);
+ if(i11 == 0) i13 = poly1->GetNumPoints()-1;
+ else i13 = i11-1;
+ p1 = poly1->GetPoint(i13);
+ if(i22 == (poly2->GetNumPoints()-1)) i23 = 0;
+ else i23 = i22+1;
+ p3 = poly2->GetPoint(i23);
+
+ if(!IsConvex(p1,p2,p3)) continue;
+
+ p2 = poly1->GetPoint(i12);
+ if(i12 == (poly1->GetNumPoints()-1)) i13 = 0;
+ else i13 = i12+1;
+ p3 = poly1->GetPoint(i13);
+ if(i21 == 0) i23 = poly2->GetNumPoints()-1;
+ else i23 = i21-1;
+ p1 = poly2->GetPoint(i23);
+
+ if(!IsConvex(p1,p2,p3)) continue;
+
+ newpoly.Init(poly1->GetNumPoints()+poly2->GetNumPoints()-2);
+ k = 0;
+ for(j=i12;j!=i11;j=(j+1)%(poly1->GetNumPoints())) {
+ newpoly[k] = poly1->GetPoint(j);
+ k++;
+ }
+ for(j=i22;j!=i21;j=(j+1)%(poly2->GetNumPoints())) {
+ newpoly[k] = poly2->GetPoint(j);
+ k++;
+ }
+
+ triangles.erase(iter2);
+ iter1->get() = newpoly;
+ poly1 = &(iter1->get());
+ i11 = -1;
+
+ continue;
+ }
+ }
+
+ for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) {
+ parts->push_back(iter1->get());
+ }
+
+ return 1;
+}
+
+int TriangulatorPartition::ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts) {
+ List<TriangulatorPoly> outpolys;
+ List<TriangulatorPoly>::Element* iter;
+
+ if(!RemoveHoles(inpolys,&outpolys)) return 0;
+ for(iter=outpolys.front();iter;iter=iter->next()) {
+ if(!ConvexPartition_HM(&(iter->get()),parts)) return 0;
+ }
+ return 1;
+}
+
+//minimum-weight polygon triangulation by dynamic programming
+//O(n^3) time complexity
+//O(n^2) space complexity
+int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
+ long i,j,k,gap,n;
+ DPState **dpstates;
+ Vector2 p1,p2,p3,p4;
+ long bestvertex;
+ real_t weight,minweight,d1,d2;
+ Diagonal diagonal,newdiagonal;
+ List<Diagonal> diagonals;
+ TriangulatorPoly triangle;
+ int ret = 1;
+
+ n = poly->GetNumPoints();
+ dpstates = new DPState *[n];
+ for(i=1;i<n;i++) {
+ dpstates[i] = new DPState[i];
+ }
+
+ //init states and visibility
+ for(i=0;i<(n-1);i++) {
+ p1 = poly->GetPoint(i);
+ for(j=i+1;j<n;j++) {
+ dpstates[j][i].visible = true;
+ dpstates[j][i].weight = 0;
+ dpstates[j][i].bestvertex = -1;
+ if(j!=(i+1)) {
+ p2 = poly->GetPoint(j);
+
+ //visibility check
+ if(i==0) p3 = poly->GetPoint(n-1);
+ else p3 = poly->GetPoint(i-1);
+ if(i==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(i+1);
+ if(!InCone(p3,p1,p4,p2)) {
+ dpstates[j][i].visible = false;
+ continue;
+ }
+
+ if(j==0) p3 = poly->GetPoint(n-1);
+ else p3 = poly->GetPoint(j-1);
+ if(j==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(j+1);
+ if(!InCone(p3,p2,p4,p1)) {
+ dpstates[j][i].visible = false;
+ continue;
+ }
+
+ for(k=0;k<n;k++) {
+ p3 = poly->GetPoint(k);
+ if(k==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(k+1);
+ if(Intersects(p1,p2,p3,p4)) {
+ dpstates[j][i].visible = false;
+ break;
+ }
+ }
+ }
+ }
+ }
+ dpstates[n-1][0].visible = true;
+ dpstates[n-1][0].weight = 0;
+ dpstates[n-1][0].bestvertex = -1;
+
+ for(gap = 2; gap<n; gap++) {
+ for(i=0; i<(n-gap); i++) {
+ j = i+gap;
+ if(!dpstates[j][i].visible) continue;
+ bestvertex = -1;
+ for(k=(i+1);k<j;k++) {
+ if(!dpstates[k][i].visible) continue;
+ if(!dpstates[j][k].visible) continue;
+
+ if(k<=(i+1)) d1=0;
+ else d1 = Distance(poly->GetPoint(i),poly->GetPoint(k));
+ if(j<=(k+1)) d2=0;
+ else d2 = Distance(poly->GetPoint(k),poly->GetPoint(j));
+
+ weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2;
+
+ if((bestvertex == -1)||(weight<minweight)) {
+ bestvertex = k;
+ minweight = weight;
+ }
+ }
+ if(bestvertex == -1) {
+ for(i=1;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+
+ return 0;
+ }
+
+ dpstates[j][i].bestvertex = bestvertex;
+ dpstates[j][i].weight = minweight;
+ }
+ }
+
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n-1;
+ diagonals.push_back(newdiagonal);
+ while(!diagonals.empty()) {
+ diagonal = (diagonals.front()->get());
+ diagonals.pop_front();
+ bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
+ if(bestvertex == -1) {
+ ret = 0;
+ break;
+ }
+ triangle.Triangle(poly->GetPoint(diagonal.index1),poly->GetPoint(bestvertex),poly->GetPoint(diagonal.index2));
+ triangles->push_back(triangle);
+ if(bestvertex > (diagonal.index1+1)) {
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = bestvertex;
+ diagonals.push_back(newdiagonal);
+ }
+ if(diagonal.index2 > (bestvertex+1)) {
+ newdiagonal.index1 = bestvertex;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_back(newdiagonal);
+ }
+ }
+
+ for(i=1;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+
+ return ret;
+}
+
+void TriangulatorPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) {
+ Diagonal newdiagonal;
+ List<Diagonal> *pairs;
+ long w2;
+
+ w2 = dpstates[a][b].weight;
+ if(w>w2) return;
+
+ pairs = &(dpstates[a][b].pairs);
+ newdiagonal.index1 = i;
+ newdiagonal.index2 = j;
+
+ if(w<w2) {
+ pairs->clear();
+ pairs->push_front(newdiagonal);
+ dpstates[a][b].weight = w;
+ } else {
+ if((!pairs->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<Diagonal> *pairs;
+ List<Diagonal>::Element *iter,*lastiter;
+ long top;
+ long w;
+
+ if(!dpstates[i][j].visible) return;
+ top = j;
+ w = dpstates[i][j].weight;
+ if(k-j > 1) {
+ if (!dpstates[j][k].visible) return;
+ w += dpstates[j][k].weight + 1;
+ }
+ if(j-i > 1) {
+ pairs = &(dpstates[i][j].pairs);
+ iter = NULL;
+ lastiter = NULL;
+ while(iter!=pairs->front()) {
+ if (!iter)
+ iter=pairs->back();
+ else
+ iter=iter->prev();
+
+ if(!IsReflex(vertices[iter->get().index2].p,vertices[j].p,vertices[k].p)) lastiter = iter;
+ else break;
+ }
+ if(lastiter == NULL) w++;
+ else {
+ if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->get().index1].p)) w++;
+ else top = lastiter->get().index1;
+ }
+ }
+ UpdateState(i,k,w,top,j,dpstates);
+}
+
+void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+ List<Diagonal> *pairs;
+ List<Diagonal>::Element* iter,*lastiter;
+ long top;
+ long w;
+
+ if(!dpstates[j][k].visible) return;
+ top = j;
+ w = dpstates[j][k].weight;
+
+ if (j-i > 1) {
+ if (!dpstates[i][j].visible) return;
+ w += dpstates[i][j].weight + 1;
+ }
+ if (k-j > 1) {
+ pairs = &(dpstates[j][k].pairs);
+
+ iter = pairs->front();
+ if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) {
+ lastiter = iter;
+ while(iter!=NULL) {
+ if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p)) {
+ lastiter = iter;
+ iter=iter->next();
+ }
+ else break;
+ }
+ if(IsReflex(vertices[lastiter->get().index2].p,vertices[k].p,vertices[i].p)) w++;
+ else top = lastiter->get().index2;
+ } else w++;
+ }
+ UpdateState(i,k,w,j,top,dpstates);
+}
+
+int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) {
+ Vector2 p1,p2,p3,p4;
+ PartitionVertex *vertices;
+ DPState2 **dpstates;
+ long i,j,k,n,gap;
+ List<Diagonal> diagonals,diagonals2;
+ Diagonal diagonal,newdiagonal;
+ List<Diagonal> *pairs,*pairs2;
+ List<Diagonal>::Element* iter,*iter2;
+ int ret;
+ TriangulatorPoly newpoly;
+ List<long> indices;
+ List<long>::Element* iiter;
+ bool ijreal,jkreal;
+
+ n = poly->GetNumPoints();
+ vertices = new PartitionVertex[n];
+
+ dpstates = new DPState2 *[n];
+ for(i=0;i<n;i++) {
+ dpstates[i] = new DPState2[n];
+ }
+
+ //init vertex information
+ for(i=0;i<n;i++) {
+ vertices[i].p = poly->GetPoint(i);
+ vertices[i].isActive = true;
+ if(i==0) vertices[i].previous = &(vertices[n-1]);
+ else vertices[i].previous = &(vertices[i-1]);
+ if(i==(poly->GetNumPoints()-1)) vertices[i].next = &(vertices[0]);
+ else vertices[i].next = &(vertices[i+1]);
+ }
+ for(i=1;i<n;i++) {
+ UpdateVertexReflexity(&(vertices[i]));
+ }
+
+ //init states and visibility
+ for(i=0;i<(n-1);i++) {
+ p1 = poly->GetPoint(i);
+ for(j=i+1;j<n;j++) {
+ dpstates[i][j].visible = true;
+ if(j==i+1) {
+ dpstates[i][j].weight = 0;
+ } else {
+ dpstates[i][j].weight = 2147483647;
+ }
+ if(j!=(i+1)) {
+ p2 = poly->GetPoint(j);
+
+ //visibility check
+ if(!InCone(&vertices[i],p2)) {
+ dpstates[i][j].visible = false;
+ continue;
+ }
+ if(!InCone(&vertices[j],p1)) {
+ dpstates[i][j].visible = false;
+ continue;
+ }
+
+ for(k=0;k<n;k++) {
+ p3 = poly->GetPoint(k);
+ if(k==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(k+1);
+ if(Intersects(p1,p2,p3,p4)) {
+ dpstates[i][j].visible = false;
+ break;
+ }
+ }
+ }
+ }
+ }
+ for(i=0;i<(n-2);i++) {
+ j = i+2;
+ if(dpstates[i][j].visible) {
+ dpstates[i][j].weight = 0;
+ newdiagonal.index1 = i+1;
+ newdiagonal.index2 = i+1;
+ dpstates[i][j].pairs.push_back(newdiagonal);
+ }
+ }
+
+ dpstates[0][n-1].visible = true;
+ vertices[0].isConvex = false; //by convention
+
+ for(gap=3; gap<n; gap++) {
+ for(i=0;i<n-gap;i++) {
+ if(vertices[i].isConvex) continue;
+ k = i+gap;
+ if(dpstates[i][k].visible) {
+ if(!vertices[k].isConvex) {
+ for(j=i+1;j<k;j++) TypeA(i,j,k,vertices,dpstates);
+ } else {
+ for(j=i+1;j<(k-1);j++) {
+ if(vertices[j].isConvex) continue;
+ TypeA(i,j,k,vertices,dpstates);
+ }
+ TypeA(i,k-1,k,vertices,dpstates);
+ }
+ }
+ }
+ for(k=gap;k<n;k++) {
+ if(vertices[k].isConvex) continue;
+ i = k-gap;
+ if((vertices[i].isConvex)&&(dpstates[i][k].visible)) {
+ TypeB(i,i+1,k,vertices,dpstates);
+ for(j=i+2;j<k;j++) {
+ if(vertices[j].isConvex) continue;
+ TypeB(i,j,k,vertices,dpstates);
+ }
+ }
+ }
+ }
+
+
+ //recover solution
+ ret = 1;
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n-1;
+ diagonals.push_front(newdiagonal);
+ while(!diagonals.empty()) {
+ diagonal = (diagonals.front()->get());
+ diagonals.pop_front();
+ if((diagonal.index2 - diagonal.index1) <=1) continue;
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+ if(pairs->empty()) {
+ ret = 0;
+ break;
+ }
+ if(!vertices[diagonal.index1].isConvex) {
+ iter = pairs->back();
+
+ j = iter->get().index2;
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_front(newdiagonal);
+ if((j - diagonal.index1)>1) {
+ if(iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[diagonal.index1][j].pairs);
+ while(1) {
+ if(pairs2->empty()) {
+ ret = 0;
+ break;
+ }
+ iter2 = pairs2->back();
+
+ if(iter->get().index1 != iter2->get().index1) pairs2->pop_back();
+ else break;
+ }
+ if(ret == 0) break;
+ }
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ diagonals.push_front(newdiagonal);
+ }
+ } else {
+ iter = pairs->front();
+ j = iter->get().index1;
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ diagonals.push_front(newdiagonal);
+ if((diagonal.index2 - j) > 1) {
+ if(iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[j][diagonal.index2].pairs);
+ while(1) {
+ if(pairs2->empty()) {
+ ret = 0;
+ break;
+ }
+ iter2 = pairs2->front();
+ if(iter->get().index2 != iter2->get().index2) pairs2->pop_front();
+ else break;
+ }
+ if(ret == 0) break;
+ }
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_front(newdiagonal);
+ }
+ }
+ }
+
+ if(ret == 0) {
+ for(i=0;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+ delete [] vertices;
+
+ return ret;
+ }
+
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n-1;
+ diagonals.push_front(newdiagonal);
+ while(!diagonals.empty()) {
+ diagonal = (diagonals.front())->get();
+ diagonals.pop_front();
+ if((diagonal.index2 - diagonal.index1) <= 1) continue;
+
+ indices.clear();
+ diagonals2.clear();
+ indices.push_back(diagonal.index1);
+ indices.push_back(diagonal.index2);
+ diagonals2.push_front(diagonal);
+
+ while(!diagonals2.empty()) {
+ diagonal = (diagonals2.front()->get());
+ diagonals2.pop_front();
+ if((diagonal.index2 - diagonal.index1) <= 1) continue;
+ ijreal = true;
+ jkreal = true;
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+ if(!vertices[diagonal.index1].isConvex) {
+ iter = pairs->back();
+ j = iter->get().index2;
+ if(iter->get().index1 != iter->get().index2) ijreal = false;
+ } else {
+ iter = pairs->front();
+ j = iter->get().index1;
+ if(iter->get().index1 != iter->get().index2) jkreal = false;
+ }
+
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ if(ijreal) {
+ diagonals.push_back(newdiagonal);
+ } else {
+ diagonals2.push_back(newdiagonal);
+ }
+
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ if(jkreal) {
+ diagonals.push_back(newdiagonal);
+ } else {
+ diagonals2.push_back(newdiagonal);
+ }
+
+ indices.push_back(j);
+ }
+
+ indices.sort();
+ newpoly.Init((long)indices.size());
+ k=0;
+ for(iiter = indices.front();iiter;iiter=iiter->next()) {
+ newpoly[k] = vertices[iiter->get()].p;
+ k++;
+ }
+ parts->push_back(newpoly);
+ }
+
+ for(i=0;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+ delete [] vertices;
+
+ return ret;
+}
+
+//triangulates a set of polygons by first partitioning them into monotone polygons
+//O(n*log(n)) time complexity, O(n) space complexity
+//the algorithm used here is outlined in the book
+//"Computational Geometry: Algorithms and Applications"
+//by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars
+int TriangulatorPartition::MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys) {
+ List<TriangulatorPoly>::Element *iter;
+ MonotoneVertex *vertices;
+ long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices;
+ long polystartindex, polyendindex;
+ TriangulatorPoly *poly;
+ MonotoneVertex *v,*v2,*vprev,*vnext;
+ ScanLineEdge newedge;
+ bool error = false;
+
+ numvertices = 0;
+ for(iter = inpolys->front(); iter ; iter=iter->next()) {
+ numvertices += iter->get().GetNumPoints();
+ }
+
+ maxnumvertices = numvertices*3;
+ vertices = new MonotoneVertex[maxnumvertices];
+ newnumvertices = numvertices;
+
+ polystartindex = 0;
+ for(iter = inpolys->front(); iter ; iter=iter->next()) {
+ poly = &(iter->get());
+ polyendindex = polystartindex + poly->GetNumPoints()-1;
+ for(i=0;i<poly->GetNumPoints();i++) {
+ vertices[i+polystartindex].p = poly->GetPoint(i);
+ if(i==0) vertices[i+polystartindex].previous = polyendindex;
+ else vertices[i+polystartindex].previous = i+polystartindex-1;
+ if(i==(poly->GetNumPoints()-1)) vertices[i+polystartindex].next = polystartindex;
+ else vertices[i+polystartindex].next = i+polystartindex+1;
+ }
+ polystartindex = polyendindex+1;
+ }
+
+ //construct the priority queue
+ long *priority = new long [numvertices];
+ for(i=0;i<numvertices;i++) priority[i] = i;
+ SortArray<long,VertexSorter> sorter;
+ sorter.compare.vertices=vertices;
+ sorter.sort(priority,numvertices);
+
+ //determine vertex types
+ char *vertextypes = new char[maxnumvertices];
+ for(i=0;i<numvertices;i++) {
+ v = &(vertices[i]);
+ vprev = &(vertices[v->previous]);
+ vnext = &(vertices[v->next]);
+
+ if(Below(vprev->p,v->p)&&Below(vnext->p,v->p)) {
+ if(IsConvex(vnext->p,vprev->p,v->p)) {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_START;
+ } else {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_SPLIT;
+ }
+ } else if(Below(v->p,vprev->p)&&Below(v->p,vnext->p)) {
+ if(IsConvex(vnext->p,vprev->p,v->p))
+ {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_END;
+ } else {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_MERGE;
+ }
+ } else {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_REGULAR;
+ }
+ }
+
+ //helpers
+ long *helpers = new long[maxnumvertices];
+
+ //binary search tree that holds edges intersecting the scanline
+ //note that while set doesn't actually have to be implemented as a tree
+ //complexity requirements for operations are the same as for the balanced binary search tree
+ Set<ScanLineEdge> edgeTree;
+ //store iterators to the edge tree elements
+ //this makes deleting existing edges much faster
+ Set<ScanLineEdge>::Element **edgeTreeIterators,*edgeIter;
+ edgeTreeIterators = new Set<ScanLineEdge>::Element*[maxnumvertices];
+// Pair<Set<ScanLineEdge>::Element*,bool> edgeTreeRet;
+ for(i = 0; i<numvertices; i++) edgeTreeIterators[i] = NULL;
+
+ //for each vertex
+ for(i=0;i<numvertices;i++) {
+ vindex = priority[i];
+ v = &(vertices[vindex]);
+ vindex2 = vindex;
+ v2 = v;
+
+ //depending on the vertex type, do the appropriate action
+ //comments in the following sections are copied from "Computational Geometry: Algorithms and Applications"
+ switch(vertextypes[vindex]) {
+ case TRIANGULATOR_VERTEXTYPE_START:
+ //Insert ei in T and set helper(ei) to vi.
+ newedge.p1 = v->p;
+ newedge.p2 = vertices[v->next].p;
+ newedge.index = vindex;
+ edgeTreeIterators[vindex] = edgeTree.insert(newedge);
+ helpers[vindex] = vindex;
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_END:
+ //if helper(ei-1) is a merge vertex
+ if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(ei-1) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ //Delete ei-1 from T
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_SPLIT:
+ //Search in T to find the edge e j directly left of vi.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if(edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter=edgeIter->prev();
+ //Insert the diagonal connecting vi to helper(ej) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices-2;
+ v2 = &(vertices[vindex2]);
+ //helper(e j)�vi
+ helpers[edgeIter->get().index] = vindex;
+ //Insert ei in T and set helper(ei) to vi.
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+
+ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex2;
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_MERGE:
+ //if helper(ei-1) is a merge vertex
+ if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(ei-1) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices-2;
+ v2 = &(vertices[vindex2]);
+ }
+ //Delete ei-1 from T.
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ //Search in T to find the edge e j directly left of vi.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if(edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter=edgeIter->prev();
+ //if helper(ej) is a merge vertex
+ if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(e j) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ //helper(e j)�vi
+ helpers[edgeIter->get().index] = vindex2;
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_REGULAR:
+ //if the interior of P lies to the right of vi
+ if(Below(v->p,vertices[v->previous].p)) {
+ //if helper(ei-1) is a merge vertex
+ if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(ei-1) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices-2;
+ v2 = &(vertices[vindex2]);
+ }
+ //Delete ei-1 from T.
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ //Insert ei in T and set helper(ei) to vi.
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex;
+ } else {
+ //Search in T to find the edge ej directly left of vi.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if(edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter=edgeIter->prev();
+ //if helper(ej) is a merge vertex
+ if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(e j) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ //helper(e j)�vi
+ helpers[edgeIter->get().index] = vindex;
+ }
+ break;
+ }
+
+ if(error) break;
+ }
+
+ char *used = new char[newnumvertices];
+ memset(used,0,newnumvertices*sizeof(char));
+
+ if(!error) {
+ //return result
+ long size;
+ TriangulatorPoly mpoly;
+ for(i=0;i<newnumvertices;i++) {
+ if(used[i]) continue;
+ v = &(vertices[i]);
+ vnext = &(vertices[v->next]);
+ size = 1;
+ while(vnext!=v) {
+ vnext = &(vertices[vnext->next]);
+ size++;
+ }
+ mpoly.Init(size);
+ v = &(vertices[i]);
+ mpoly[0] = v->p;
+ vnext = &(vertices[v->next]);
+ size = 1;
+ used[i] = 1;
+ used[v->next] = 1;
+ while(vnext!=v) {
+ mpoly[size] = vnext->p;
+ used[vnext->next] = 1;
+ vnext = &(vertices[vnext->next]);
+ size++;
+ }
+ monotonePolys->push_back(mpoly);
+ }
+ }
+
+ //cleanup
+ delete [] vertices;
+ delete [] priority;
+ delete [] vertextypes;
+ delete [] edgeTreeIterators;
+ delete [] helpers;
+ delete [] used;
+
+ if(error) {
+ return 0;
+ } else {
+ return 1;
+ }
+}
+
+//adds a diagonal to the doubly-connected list of vertices
+void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+ char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
+ Set<ScanLineEdge> *edgeTree, long *helpers)
+{
+ long newindex1,newindex2;
+
+ newindex1 = *numvertices;
+ (*numvertices)++;
+ newindex2 = *numvertices;
+ (*numvertices)++;
+
+ vertices[newindex1].p = vertices[index1].p;
+ vertices[newindex2].p = vertices[index2].p;
+
+ vertices[newindex2].next = vertices[index2].next;
+ vertices[newindex1].next = vertices[index1].next;
+
+ vertices[vertices[index2].next].previous = newindex2;
+ vertices[vertices[index1].next].previous = newindex1;
+
+ vertices[index1].next = newindex2;
+ vertices[newindex2].previous = index1;
+
+ vertices[index2].next = newindex1;
+ vertices[newindex1].previous = index2;
+
+ //update all relevant structures
+ vertextypes[newindex1] = vertextypes[index1];
+ edgeTreeIterators[newindex1] = edgeTreeIterators[index1];
+ helpers[newindex1] = helpers[index1];
+ if(edgeTreeIterators[newindex1] != NULL)
+ edgeTreeIterators[newindex1]->get().index = newindex1;
+ vertextypes[newindex2] = vertextypes[index2];
+ edgeTreeIterators[newindex2] = edgeTreeIterators[index2];
+ helpers[newindex2] = helpers[index2];
+ if(edgeTreeIterators[newindex2] != NULL)
+ edgeTreeIterators[newindex2]->get().index = newindex2;
+}
+
+bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) {
+ if(p1.y < p2.y) return true;
+ else if(p1.y == p2.y) {
+ if(p1.x < p2.x) return true;
+ }
+ return false;
+}
+
+
+
+
+
+//sorts in the falling order of y values, if y is equal, x is used instead
+bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) const {
+ if(vertices[index1].p.y > vertices[index2].p.y) return true;
+ else if(vertices[index1].p.y == vertices[index2].p.y) {
+ if(vertices[index1].p.x > vertices[index2].p.x) return true;
+ }
+ return false;
+}
+
+bool TriangulatorPartition::ScanLineEdge::IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const {
+ real_t tmp;
+ tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+ if(tmp>0) return 1;
+ else return 0;
+}
+
+bool TriangulatorPartition::ScanLineEdge::operator < (const ScanLineEdge & other) const {
+ if(other.p1.y == other.p2.y) {
+ if(p1.y == p2.y) {
+ if(p1.y < other.p1.y) return true;
+ else return false;
+ }
+ if(IsConvex(p1,p2,other.p1)) return true;
+ else return false;
+ } else if(p1.y == p2.y) {
+ if(IsConvex(other.p1,other.p2,p1)) return false;
+ else return true;
+ } else if(p1.y < other.p1.y) {
+ if(IsConvex(other.p1,other.p2,p1)) return false;
+ else return true;
+ } else {
+ if(IsConvex(p1,p2,other.p1)) return true;
+ else return false;
+ }
+}
+
+//triangulates monotone polygon
+//O(n) time, O(n) space complexity
+int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles) {
+ long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex;
+ Vector2 *points;
+ long numpoints;
+ TriangulatorPoly triangle;
+
+ numpoints = inPoly->GetNumPoints();
+ points = inPoly->GetPoints();
+
+ //trivial calses
+ if(numpoints < 3) return 0;
+ if(numpoints == 3) {
+ triangles->push_back(*inPoly);
+ }
+
+ topindex = 0; bottomindex=0;
+ for(i=1;i<numpoints;i++) {
+ if(Below(points[i],points[bottomindex])) bottomindex = i;
+ if(Below(points[topindex],points[i])) topindex = i;
+ }
+
+ //check if the poly is really monotone
+ i = topindex;
+ while(i!=bottomindex) {
+ i2 = i+1; if(i2>=numpoints) i2 = 0;
+ if(!Below(points[i2],points[i])) return 0;
+ i = i2;
+ }
+ i = bottomindex;
+ while(i!=topindex) {
+ i2 = i+1; if(i2>=numpoints) i2 = 0;
+ if(!Below(points[i],points[i2])) return 0;
+ i = i2;
+ }
+
+ char *vertextypes = new char[numpoints];
+ long *priority = new long[numpoints];
+
+ //merge left and right vertex chains
+ priority[0] = topindex;
+ vertextypes[topindex] = 0;
+ leftindex = topindex+1; if(leftindex>=numpoints) leftindex = 0;
+ rightindex = topindex-1; if(rightindex<0) rightindex = numpoints-1;
+ for(i=1;i<(numpoints-1);i++) {
+ if(leftindex==bottomindex) {
+ priority[i] = rightindex;
+ rightindex--; if(rightindex<0) rightindex = numpoints-1;
+ vertextypes[priority[i]] = -1;
+ } else if(rightindex==bottomindex) {
+ priority[i] = leftindex;
+ leftindex++; if(leftindex>=numpoints) leftindex = 0;
+ vertextypes[priority[i]] = 1;
+ } else {
+ if(Below(points[leftindex],points[rightindex])) {
+ priority[i] = rightindex;
+ rightindex--; if(rightindex<0) rightindex = numpoints-1;
+ vertextypes[priority[i]] = -1;
+ } else {
+ priority[i] = leftindex;
+ leftindex++; if(leftindex>=numpoints) leftindex = 0;
+ vertextypes[priority[i]] = 1;
+ }
+ }
+ }
+ priority[i] = bottomindex;
+ vertextypes[bottomindex] = 0;
+
+ long *stack = new long[numpoints];
+ long stackptr = 0;
+
+ stack[0] = priority[0];
+ stack[1] = priority[1];
+ stackptr = 2;
+
+ //for each vertex from top to bottom trim as many triangles as possible
+ for(i=2;i<(numpoints-1);i++) {
+ vindex = priority[i];
+ if(vertextypes[vindex]!=vertextypes[stack[stackptr-1]]) {
+ for(j=0;j<(stackptr-1);j++) {
+ if(vertextypes[vindex]==1) {
+ triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
+ } else {
+ triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
+ }
+ triangles->push_back(triangle);
+ }
+ stack[0] = priority[i-1];
+ stack[1] = priority[i];
+ stackptr = 2;
+ } else {
+ stackptr--;
+ while(stackptr>0) {
+ if(vertextypes[vindex]==1) {
+ if(IsConvex(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]])) {
+ triangle.Triangle(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]]);
+ triangles->push_back(triangle);
+ stackptr--;
+ } else {
+ break;
+ }
+ } else {
+ if(IsConvex(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]])) {
+ triangle.Triangle(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]]);
+ triangles->push_back(triangle);
+ stackptr--;
+ } else {
+ break;
+ }
+ }
+ }
+ stackptr++;
+ stack[stackptr] = vindex;
+ stackptr++;
+ }
+ }
+ vindex = priority[i];
+ for(j=0;j<(stackptr-1);j++) {
+ if(vertextypes[stack[j+1]]==1) {
+ triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
+ } else {
+ triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
+ }
+ triangles->push_back(triangle);
+ }
+
+ delete [] priority;
+ delete [] vertextypes;
+ delete [] stack;
+
+ return 1;
+}
+
+int TriangulatorPartition::Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) {
+ List<TriangulatorPoly> monotone;
+ List<TriangulatorPoly>::Element* iter;
+
+ if(!MonotonePartition(inpolys,&monotone)) return 0;
+ for(iter = monotone.front(); iter;iter=iter->next()) {
+ if(!TriangulateMonotone(&(iter->get()),triangles)) return 0;
+ }
+ return 1;
+}
+
+int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
+ List<TriangulatorPoly> polys;
+ polys.push_back(*poly);
+
+ return Triangulate_MONO(&polys, triangles);
+}
diff --git a/core/math/triangulator.h b/core/math/triangulator.h
new file mode 100644
index 0000000000..b6dd7e8236
--- /dev/null
+++ b/core/math/triangulator.h
@@ -0,0 +1,306 @@
+//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 "list.h"
+#include "set.h"
+//2D point structure
+
+
+#define TRIANGULATOR_CCW 1
+#define TRIANGULATOR_CW -1
+//Polygon implemented as an array of points with a 'hole' flag
+class TriangulatorPoly {
+protected:
+
+
+
+ Vector2 *points;
+ long numpoints;
+ bool hole;
+
+public:
+
+ //constructors/destructors
+ TriangulatorPoly();
+ ~TriangulatorPoly();
+
+ TriangulatorPoly(const TriangulatorPoly &src);
+ TriangulatorPoly& operator=(const TriangulatorPoly &src);
+
+ //getters and setters
+ long GetNumPoints() {
+ return numpoints;
+ }
+
+ bool IsHole() {
+ return hole;
+ }
+
+ void SetHole(bool hole) {
+ this->hole = hole;
+ }
+
+ Vector2 &GetPoint(long i) {
+ return points[i];
+ }
+
+ Vector2 *GetPoints() {
+ return points;
+ }
+
+ Vector2& operator[] (int i) {
+ return points[i];
+ }
+
+ //clears the polygon points
+ void Clear();
+
+ //inits the polygon with numpoints vertices
+ void Init(long numpoints);
+
+ //creates a triangle with points p1,p2,p3
+ void Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3);
+
+ //inverts the orfer of vertices
+ void Invert();
+
+ //returns the orientation of the polygon
+ //possible values:
+ // Triangulator_CCW : polygon vertices are in counter-clockwise order
+ // Triangulator_CW : polygon vertices are in clockwise order
+ // 0 : the polygon has no (measurable) area
+ int GetOrientation();
+
+ //sets the polygon orientation
+ //orientation can be
+ // Triangulator_CCW : sets vertices in counter-clockwise order
+ // Triangulator_CW : sets vertices in clockwise order
+ void SetOrientation(int orientation);
+};
+
+class TriangulatorPartition {
+protected:
+ struct PartitionVertex {
+ bool isActive;
+ bool isConvex;
+ bool isEar;
+
+ Vector2 p;
+ real_t angle;
+ PartitionVertex *previous;
+ PartitionVertex *next;
+ };
+
+ struct MonotoneVertex {
+ Vector2 p;
+ long previous;
+ long next;
+ };
+
+ struct VertexSorter{
+ mutable MonotoneVertex *vertices;
+ bool operator() (long index1, long index2) const;
+ };
+
+ struct Diagonal {
+ long index1;
+ long index2;
+ };
+
+ //dynamic programming state for minimum-weight triangulation
+ struct DPState {
+ bool visible;
+ real_t weight;
+ long bestvertex;
+ };
+
+ //dynamic programming state for convex partitioning
+ struct DPState2 {
+ bool visible;
+ long weight;
+ List<Diagonal> pairs;
+ };
+
+ //edge that intersects the scanline
+ struct ScanLineEdge {
+ mutable long index;
+ Vector2 p1;
+ Vector2 p2;
+
+ //determines if the edge is to the left of another edge
+ bool operator< (const ScanLineEdge & other) const;
+
+ bool IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const;
+ };
+
+ //standard helper functions
+ bool IsConvex(Vector2& p1, Vector2& p2, Vector2& p3);
+ bool IsReflex(Vector2& p1, Vector2& p2, Vector2& p3);
+ bool IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p);
+
+ bool InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p);
+ bool InCone(PartitionVertex *v, Vector2 &p);
+
+ int Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22);
+
+ Vector2 Normalize(const Vector2 &p);
+ real_t Distance(const Vector2 &p1, const Vector2 &p2);
+
+ //helper functions for Triangulate_EC
+ void UpdateVertexReflexity(PartitionVertex *v);
+ void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices);
+
+ //helper functions for ConvexPartition_OPT
+ void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
+ void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+ void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+
+ //helper functions for MonotonePartition
+ bool Below(Vector2 &p1, Vector2 &p2);
+ void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+ char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
+ Set<ScanLineEdge> *edgeTree, long *helpers);
+
+ //triangulates a monotone polygon, used in Triangulate_MONO
+ int TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles);
+
+public:
+
+ //simple heuristic procedure for removing holes from a list of polygons
+ //works by creating a diagonal from the rightmost hole vertex to some visible vertex
+ //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons that can contain holes
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // outpolys : a list of polygons without holes
+ //returns 1 on success, 0 on failure
+ int RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys);
+
+ //triangulates a polygon by ear clipping
+ //time complexity O(n^2), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // poly : an input polygon to be triangulated
+ // vertices have to be in counter-clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
+
+ //triangulates a list of polygons that may contain holes by ear clipping algorithm
+ //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon
+ //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons to be triangulated (can contain holes)
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles);
+
+ //creates an optimal polygon triangulation in terms of minimal edge length
+ //time complexity: O(n^3), n is the number of vertices
+ //space complexity: O(n^2)
+ //params:
+ // poly : an input polygon to be triangulated
+ // vertices have to be in counter-clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
+
+ //triangulates a polygons by firstly partitioning it into monotone polygons
+ //time complexity: O(n*log(n)), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // poly : an input polygon to be triangulated
+ // vertices have to be in counter-clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
+
+ //triangulates a list of polygons by firstly partitioning them into monotone polygons
+ //time complexity: O(n*log(n)), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons to be triangulated (can contain holes)
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles);
+
+ //creates a monotone partition of a list of polygons that can contain holes
+ //time complexity: O(n*log(n)), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons to be triangulated (can contain holes)
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // monotonePolys : a list of monotone polygons (result)
+ //returns 1 on success, 0 on failure
+ int MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys);
+
+ //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm
+ //the algorithm gives at most four times the number of parts as the optimal algorithm
+ //however, in practice it works much better than that and often gives optimal partition
+ //uses triangulation obtained by ear clipping as intermediate result
+ //time complexity O(n^2), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // poly : an input polygon to be partitioned
+ // vertices have to be in counter-clockwise order
+ // parts : resulting list of convex polygons
+ //returns 1 on success, 0 on failure
+ int ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts);
+
+ //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm
+ //the algorithm gives at most four times the number of parts as the optimal algorithm
+ //however, in practice it works much better than that and often gives optimal partition
+ //uses triangulation obtained by ear clipping as intermediate result
+ //time complexity O(n^2), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : an input list of polygons to be partitioned
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // parts : resulting list of convex polygons
+ //returns 1 on success, 0 on failure
+ int ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts);
+
+ //optimal convex partitioning (in terms of number of resulting convex polygons)
+ //using the Keil-Snoeyink algorithm
+ //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998
+ //time complexity O(n^3), n is the number of vertices
+ //space complexity: O(n^3)
+ // poly : an input polygon to be partitioned
+ // vertices have to be in counter-clockwise order
+ // parts : resulting list of convex polygons
+ //returns 1 on success, 0 on failure
+ int ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts);
+};
+
+
+#endif
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/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);
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/ustring.cpp b/core/ustring.cpp
index 581cc29440..476ab3f936 100644
--- a/core/ustring.cpp
+++ b/core/ustring.cpp
@@ -34,6 +34,7 @@
#include "io/md5.h"
#include "ucaps.h"
#include "color.h"
+#include "variant.h"
#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))
@@ -981,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);
@@ -990,7 +991,7 @@ String String::num_int64(int64_t p_num) {
int chars=0;
do {
- n/=10;
+ n/=base;
chars++;
} while(n);
@@ -1002,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)
@@ -3518,4 +3526,284 @@ 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]
+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 min_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 '%': { // Replace %% with %
+ formatted += chr(c);
+ in_format = false;
+ break;
+ }
+ case 'd': // Integer (signed)
+ case 'o': // Octal
+ case 'x': // Hexadecimal (lowercase)
+ case 'X': { // Hexadecimal (uppercase)
+ if (value_index >= values.size()) {
+ ERR_EXPLAIN("not enough arguments for format string");
+ ERR_FAIL_V("");
+ }
+
+ 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);
+
+ // 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;
+
+ break;
+ }
+ case 'f': { // Float
+ if (value_index >= values.size()) {
+ ERR_EXPLAIN("not enough arguments for format string");
+ ERR_FAIL_V("");
+ }
+
+ if (!values[value_index].is_num()) {
+ ERR_EXPLAIN("a number is required");
+ ERR_FAIL_V("");
+ }
+
+ double value = values[value_index];
+ String str = String::num(value, min_decimals);
+
+ // Pad decimals out.
+ str = str.pad_decimals(min_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 += 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) {
+ str = str.rpad(min_chars);
+ } else {
+ str = str.lpad(min_chars);
+ }
+
+ formatted += str;
+ ++value_index;
+ 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;
+ }
+ 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) {
+ min_decimals *= 10;
+ min_decimals += n;
+ } else {
+ if (c == '0' && min_chars == 0) {
+ pad_with_zeroes = true;
+ } else {
+ min_chars *= 10;
+ min_chars += n;
+ }
+ }
+ break;
+ }
+ case '.': { // Float separtor.
+ if (in_decimals) {
+ ERR_EXPLAIN("too many decimal points in format");
+ ERR_FAIL_V("");
+ }
+ in_decimals = true;
+ 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;
+ }
+
+ ++value_index;
+ break;
+ }
+
+ default: {
+ ERR_EXPLAIN("unsupported format character");
+ ERR_FAIL_V("");
+ }
+ }
+ } else { // Not in format string.
+ switch (c) {
+ case '%':
+ in_format = true;
+ // Back to defaults:
+ min_chars = 0;
+ min_decimals = 6;
+ pad_with_zeroes = false;
+ left_justified = false;
+ show_sign = false;
+ in_decimals = false;
+ break;
+ default:
+ formatted += chr(c);
+ }
+ }
+ }
+
+ 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;
+}
diff --git a/core/ustring.h b/core/ustring.h
index e1d6761742..af5ffb7c35 100644
--- a/core/ustring.h
+++ b/core/ustring.h
@@ -31,6 +31,7 @@
#include "typedefs.h"
#include "vector.h"
+#include "array.h"
/**
@author red <red@killy>
@@ -127,10 +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;
@@ -203,7 +207,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.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<const String*>(_data._mem)+"\"";
+ case STRING: return "\""+reinterpret_cast<const String*>(_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<Variant>::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<Vector3> vec = operator DVector<Vector3>();
- String str="[";
+ String str="Vector3Array([";
for(int i=0;i<vec.size();i++) {
if (i>0)
str+=", ";
str+=Variant( vec[i] ).get_construct_string();
}
- return str+"]";
+ return str+"])";
} break;
case STRING_ARRAY: {
DVector<String> vec = operator DVector<String>();
- String str="[";
+ String str="StringArray([";
for(int i=0;i<vec.size();i++) {
if (i>0)
str+=", ";
str=str+=Variant( vec[i] ).get_construct_string();
}
- return str+"]";
+ return str+"])";
} break;
case INT_ARRAY: {
DVector<int> vec = operator DVector<int>();
- String str="[";
+ String str="IntArray([";
for(int i=0;i<vec.size();i++) {
if (i>0)
str+=", ";
str=str+itos(vec[i]);
}
- return str+"]";
+ return str+"])";
} break;
case REAL_ARRAY: {
DVector<real_t> vec = operator DVector<real_t>();
- String str="[";
+ String str="FloatArray([";
for(int i=0;i<vec.size();i++) {
if (i>0)
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; i<arr.size(); i++) {
if (i)
str+=", ";
- str += arr[i].get_construct_string();
+ str += arr[i].get_construct_string(p_obj_deconstruct,p_deconstruct_ud);
};
return str+"]";
} break;
case OBJECT: {
- if (_get_obj().obj)
- return _get_obj().obj->get_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_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());
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<p_len) {
+
+ Error err = _get_token(p_str,index,p_len,token,line,r_err_str);
+ if (err!=OK)
+ return err;
+
+ if (token.type==TK_BRACKET_CLOSE) {
+
+ return OK;
+ }
+
+ if (need_comma) {
+
+ if (token.type!=TK_COMMA) {
+
+ r_err_str="Expected ','";
+ return ERR_PARSE_ERROR;
+ } else {
+ need_comma=false;
+ continue;
+ }
+ }
+
+ Variant v;
+ err = _parse_value(v,token,p_str,index,p_len,line,r_err_str,p_construct,p_ud);
+ if (err)
+ return err;
+
+ array.push_back(v);
+ need_comma=true;
+
+ }
+
+ return OK;
+
+}
+
+Error VariantConstruct::_parse_dict(Dictionary &dict,const CharType *p_str,int &index, int p_len,int &line,String &r_err_str,Variant::ObjectConstruct* p_construct,void* p_ud) {
+
+ bool at_key=true;
+ Variant key;
+ Token token;
+ bool need_comma=false;
+
+
+ while(index<p_len) {
+
+
+ if (at_key) {
+
+ Error err = _get_token(p_str,index,p_len,token,line,r_err_str);
+ if (err!=OK)
+ return err;
+
+ if (token.type==TK_CURLY_BRACKET_CLOSE) {
+
+ return OK;
+ }
+
+ if (need_comma) {
+
+ if (token.type!=TK_COMMA) {
+
+ r_err_str="Expected '}' or ','";
+ return ERR_PARSE_ERROR;
+ } else {
+ need_comma=false;
+ continue;
+ }
+ }
+
+ err = _parse_value(key,token,p_str,index,p_len,line,r_err_str,p_construct,p_ud);
+
+
+ if (err!=OK)
+ return err;
+
+ err = _get_token(p_str,index,p_len,token,line,r_err_str);
+
+ if (err!=OK)
+ return err;
+
+ if (token.type!=TK_COLON) {
+
+ r_err_str="Expected ':'";
+ return ERR_PARSE_ERROR;
+ }
+ at_key=false;
+ } else {
+
+
+ Error err = _get_token(p_str,index,p_len,token,line,r_err_str);
+ if (err!=OK)
+ return err;
+
+ Variant v;
+ err = _parse_value(v,token,p_str,index,p_len,line,r_err_str,p_construct,p_ud);
+ if (err)
+ return err;
+ dict[key]=v;
+ need_comma=true;
+ at_key=true;
+ }
+ }
+
+ return OK;
+}
+
+
+Error VariantConstruct::parse(const String& p_string,Variant& r_ret,String &r_err_str,int &r_err_line,Variant::ObjectConstruct* p_construct,void* p_ud) {
+
+
+ const CharType *str = p_string.ptr();
+ int idx = 0;
+ int len = p_string.length();
+ Token token;
+ r_err_line=0;
+ String aux_key;
+
+ Error err = _get_token(str,idx,len,token,r_err_line,r_err_str);
+ if (err)
+ return err;
+
+ return _parse_value(r_ret,token,str,idx,len,r_err_line,r_err_str,p_construct,p_ud);
+}
+
+
diff --git a/core/variant_op.cpp b/core/variant_op.cpp
index ec43b1275c..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;
@@ -736,6 +739,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<const String*>(p_a._data._mem);
+
+ if (p_b.type==ARRAY) {
+ // e.g. "frog %s %d" % ["fish", 12]
+ const Array *arr=reinterpret_cast<const Array*>(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;
@@ -1687,6 +1704,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 +2395,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: {
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-02 16:37:12 +0000