From 3f975965e98544e4c22eba2838ecaf00a24eb836 Mon Sep 17 00:00:00 2001
From: Biliogadafr <Biliogadafr@gmail.com>
Date: Tue, 26 May 2015 22:17:54 +0300
Subject: Add get_color_at_offset(). Ensure correct points order.

---
 scene/2d/particles_2d.cpp      | 30 +-----------------
 scene/resources/color_ramp.cpp | 72 ++++++++++++++++++++++++++++++++++++------
 scene/resources/color_ramp.h   |  3 ++
 3 files changed, 67 insertions(+), 38 deletions(-)

diff --git a/scene/2d/particles_2d.cpp b/scene/2d/particles_2d.cpp
index 6effd4f31d..f0b7c2be60 100644
--- a/scene/2d/particles_2d.cpp
+++ b/scene/2d/particles_2d.cpp
@@ -528,35 +528,7 @@ void Particles2D::_notification(int p_what) {
 
 				if(color_ramp.is_valid())
 				{
-					Vector<ColorRamp::Point>& color_points = color_ramp->get_points();
-
-					int cpos=0;
-
-					while(cpos<color_points.size()) {
-
-						if (color_points[cpos].offset > ptime)
-							break;
-						cpos++;
-					}
-
-					cpos--;
-					//could be faster..
-					if (cpos==-1)
-						if(color_points.size())
-							color=color_points[0].color;//Extend color to the beginning
-						else
-							color=Color(1,1,1,1);//If no points just use white.
-					else {
-						if (cpos==color_points.size()-1)
-							color=color_points[cpos].color;
-						else {
-							float diff = (color_points[cpos+1].offset-color_points[cpos].offset);
-							if (diff>0)
-								color=color_points[cpos].color.linear_interpolate(color_points[cpos+1].color, (ptime - color_points[cpos].offset) / diff );
-							else
-								color=color_points[cpos+1].color;
-						}
-					}
+					color = color_ramp->get_color_at_offset(ptime);
 				} else
 				{
 					color = default_color;
diff --git a/scene/resources/color_ramp.cpp b/scene/resources/color_ramp.cpp
index ef32ccb6a7..df235e2f2c 100644
--- a/scene/resources/color_ramp.cpp
+++ b/scene/resources/color_ramp.cpp
@@ -17,6 +17,7 @@ ColorRamp::ColorRamp() {
 	points[0].offset = 0;
 	points[1].color = Color(1,1,1,1);
 	points[1].offset = 1;
+	is_sorted = true;
 }
 
 ColorRamp::~ColorRamp() {
@@ -25,9 +26,6 @@ ColorRamp::~ColorRamp() {
 
 void ColorRamp::_bind_methods() {
 
-	//ObjectTypeDB::bind_method(_MD("set_offset", "pos", "offset"),&ColorRamp::set_offset);
-	//ObjectTypeDB::bind_method(_MD(COLOR_RAMP_GET_OFFSETS),&ColorRamp::get_offset);
-
 	ObjectTypeDB::bind_method(_MD(COLOR_RAMP_SET_OFFSETS,"offsets"),&ColorRamp::set_offsets);
 	ObjectTypeDB::bind_method(_MD(COLOR_RAMP_GET_OFFSETS),&ColorRamp::get_offsets);
 
@@ -58,19 +56,22 @@ Vector<Color> ColorRamp::get_colors() const {
 	return colors;
 }
 
-void ColorRamp::set_offsets(const Vector<float>& offsets) {
-	points.resize(offsets.size());
+void ColorRamp::set_offsets(const Vector<float>& p_offsets) {
+	points.resize(p_offsets.size());
 	for(int i = 0; i < points.size(); i++)
 	{
-		points[i].offset = offsets[i];
+		points[i].offset = p_offsets[i];
 	}
+	is_sorted = false;
 }
 
-void ColorRamp::set_colors(const Vector<Color>& colors) {
-	points.resize(colors.size());
+void ColorRamp::set_colors(const Vector<Color>& p_colors) {
+	if(points.size()<p_colors.size())
+		is_sorted = false;
+	points.resize(p_colors.size());
 	for(int i = 0; i < points.size(); i++)
 	{
-		points[i].color = colors[i];
+		points[i].color = p_colors[i];
 	}
 }
 
@@ -80,12 +81,14 @@ Vector<ColorRamp::Point>& ColorRamp::get_points() {
 
 void ColorRamp::set_points(Vector<ColorRamp::Point>& p_points) {
 	points = p_points;
+	is_sorted = false;
 }
 
 void ColorRamp::set_offset(int pos, const float offset) {
 	if(points.size() <= pos)
 		points.resize(pos + 1);
 	points[pos].offset = offset;
+	is_sorted = false;
 }
 
 float ColorRamp::get_offset(int pos) const {
@@ -96,7 +99,10 @@ float ColorRamp::get_offset(int pos) const {
 
 void ColorRamp::set_color(int pos, const Color& color) {
 	if(points.size() <= pos)
+	{
 		points.resize(pos + 1);
+		is_sorted = false;
+	}
 	points[pos].color = color;
 }
 
@@ -106,6 +112,54 @@ Color ColorRamp::get_color(int pos) const {
 	return Color(0,0,0,1); //TODO: Maybe throw some error instead?
 }
 
+Color ColorRamp::get_color_at_offset(float p_offset) {
+
+	if (points.empty())
+		return Color(0,0,0,1);
+
+	if (points.size() == 1)
+		return points[0].color;
+
+	if(!is_sorted)
+	{
+		points.sort();
+		is_sorted = true;
+	}
+
+	//binary search
+	int low = 0;
+	int high = points.size() -1;
+	int middle;
+
+	while( low <= high )
+	{
+		middle = ( low  + high ) / 2;
+		Point& point = points[middle];
+		if( point.offset > p_offset ) {
+			high = middle - 1; //search low end of array
+		} else if ( point.offset < p_offset) {
+			low = middle + 1; //search high end of array
+		} else {
+			return point.color;
+		}
+	}
+
+	//return interpolated value
+	if (points[middle].offset>p_offset)
+	{
+		middle--;
+	}
+	int first=middle;
+	int second=middle+1;
+	if(second>=points.size())
+		return points[points.size()-1].color;
+	if(first<0)
+		return points[0].color;
+	Point& pointFirst = points[first];
+	Point& pointSecond = points[second];
+	return pointFirst.color.linear_interpolate(pointSecond.color, (p_offset-pointFirst.offset)/(pointSecond.offset - pointFirst.offset));
+}
+
 int ColorRamp::get_points_count() const {
 	return points.size();
 }
diff --git a/scene/resources/color_ramp.h b/scene/resources/color_ramp.h
index e2f1ac5ed4..7db8b4f3b0 100644
--- a/scene/resources/color_ramp.h
+++ b/scene/resources/color_ramp.h
@@ -23,6 +23,7 @@ public:
 
 private:
 	Vector<Point> points;
+	bool is_sorted;
 
 protected:
 	static void _bind_methods();
@@ -46,6 +47,8 @@ public:
 	void set_colors(const Vector<Color>& colors);
 	Vector<Color> get_colors() const;
 
+	Color get_color_at_offset(float offset);
+
 	int get_points_count() const;
 };
 
-- 
cgit v1.2.3