GODOT IS OPEN SOURCE

1 files changed, 370 insertions, 0 deletions

diff --git a/core/image_quantize.cpp b/core/image_quantize.cpp
new file mode 100644
index 0000000000..d728a32861
--- /dev/null
+++ b/core/image_quantize.cpp
@@ -0,0 +1,370 @@
+/*************************************************************************/
+/*  image_quantize.cpp                                                   */
+/*************************************************************************/
+/*                       This file is part of:                           */
+/*                           GODOT ENGINE                                */
+/*                    http://www.godotengine.org                         */
+/*************************************************************************/
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur.                 */
+/*                                                                       */
+/* 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 "image.h"
+#include <stdio.h>
+#include "print_string.h"
+#ifdef TOOLS_ENABLED
+#include "set.h"
+#include "sort.h"
+#include "os/os.h"
+
+//#define QUANTIZE_SPEED_OVER_QUALITY
+
+
+Image::MCBlock::MCBlock() {
+
+
+}
+
+Image::MCBlock::MCBlock(BColorPos *p_colors,int p_color_count) {
+
+	colors=p_colors;
+	color_count=p_color_count;
+	min_color.color=BColor(255,255,255,255);
+	max_color.color=BColor(0,0,0,0);
+	shrink();
+}
+
+int Image::MCBlock::get_longest_axis_index() const {
+
+	int max_dist=-1;
+	int max_index=0;
+
+	for(int i=0;i<4;i++) {
+
+		int d = max_color.color.col[i]-min_color.color.col[i];
+		//printf(" ai:%i - %i\n",i,d);
+		if (d>max_dist) {
+			max_index=i;
+			max_dist=d;
+		}
+	}
+
+	return max_index;
+}
+int Image::MCBlock::get_longest_axis_length() const {
+
+	int max_dist=-1;
+	int max_index=0;
+
+	for(int i=0;i<4;i++) {
+
+		int d = max_color.color.col[i]-min_color.color.col[i];
+		if (d>max_dist) {
+			max_index=i;
+			max_dist=d;
+		}
+	}
+
+	return max_dist;
+}
+
+bool Image::MCBlock::operator<(const MCBlock& p_block) const {
+
+	int alen = get_longest_axis_length();
+	int blen = p_block.get_longest_axis_length();
+	if (alen==blen) {
+
+		return colors < p_block.colors;
+	} else
+		return alen < blen;
+
+}
+
+void Image::MCBlock::shrink() {
+
+	min_color=colors[0];
+	max_color=colors[0];
+
+	for(int i=1;i<color_count;i++) {
+
+		for(int j=0;j<4;j++) {
+
+			min_color.color.col[j]=MIN(min_color.color.col[j],colors[i].color.col[j]);
+			max_color.color.col[j]=MAX(max_color.color.col[j],colors[i].color.col[j]);
+		}
+	}
+}
+
+
+
+
+void Image::quantize() {
+
+	Image::Format orig_format=format;
+
+	bool has_alpha = detect_alpha()!=ALPHA_NONE;
+
+	bool quantize_fast=OS::get_singleton()->has_environment("QUANTIZE_FAST");
+
+	convert(FORMAT_RGBA);
+
+	ERR_FAIL_COND( format!=FORMAT_RGBA );
+
+	DVector<uint8_t> indexed_data;
+
+
+	{
+		int color_count = data.size()/4;
+
+		ERR_FAIL_COND(color_count==0);
+
+		Set<MCBlock> block_queue;
+
+		DVector<BColorPos> data_colors;
+		data_colors.resize(color_count);
+
+		DVector<BColorPos>::Write dcw=data_colors.write();
+
+		DVector<uint8_t>::Read dr = data.read();
+		const BColor * drptr=(const BColor*)&dr[0];
+		BColorPos *bcptr=&dcw[0];
+
+
+
+		{
+			for(int i=0;i<color_count;i++) {
+
+				//uint32_t data_ofs=i<<2;
+				bcptr[i].color=drptr[i];//BColor(drptr[data_ofs+0],drptr[data_ofs+1],drptr[data_ofs+2],drptr[data_ofs+3]);
+				bcptr[i].index=i;
+			}
+
+		}
+
+		//printf("color count: %i\n",color_count);
+		/*
+		for(int i=0;i<color_count;i++) {
+
+			BColor bc = ((BColor*)&wb[0])[i];
+			printf("%i - %i,%i,%i,%i\n",i,bc.r,bc.g,bc.b,bc.a);
+		}*/
+
+		MCBlock initial_block((BColorPos*)&dcw[0],color_count);
+
+		block_queue.insert(initial_block);
+
+		while( block_queue.size() < 256 && block_queue.back()->get().color_count > 1 ) {
+
+			MCBlock longest = block_queue.back()->get();
+			//printf("longest: %i (%i)\n",longest.get_longest_axis_index(),longest.get_longest_axis_length());
+
+			block_queue.erase(block_queue.back());
+
+			BColorPos *first = longest.colors;
+			BColorPos *median = longest.colors + (longest.color_count+1)/2;
+			BColorPos *end = longest.colors + longest.color_count;
+
+#if 0
+			int lai =longest.get_longest_axis_index();
+			switch(lai) {
+#if 0
+				case 0: { SortArray<BColorPos,BColorPos::SortR> sort; sort.sort(first,end-first); } break;
+				case 1: { SortArray<BColorPos,BColorPos::SortG> sort; sort.sort(first,end-first); } break;
+				case 2: { SortArray<BColorPos,BColorPos::SortB> sort; sort.sort(first,end-first); } break;
+				case 3: { SortArray<BColorPos,BColorPos::SortA> sort; sort.sort(first,end-first); } break;
+#else
+				case 0: { SortArray<BColorPos,BColorPos::SortR> sort; sort.nth_element(0,end-first,median-first,first); } break;
+				case 1: { SortArray<BColorPos,BColorPos::SortG> sort; sort.nth_element(0,end-first,median-first,first); } break;
+				case 2: { SortArray<BColorPos,BColorPos::SortB> sort; sort.nth_element(0,end-first,median-first,first); } break;
+				case 3: { SortArray<BColorPos,BColorPos::SortA> sort; sort.nth_element(0,end-first,median-first,first); } break;
+#endif
+
+			}
+
+			//avoid same color from being split in 2
+			//search forward and flip
+			BColorPos *median_end=median;
+			BColorPos *p=median_end+1;
+
+			while(p!=end) {
+				if (median_end->color==p->color) {
+					SWAP(*(median_end+1),*p);
+					median_end++;
+				}
+				p++;
+			}
+
+			//search backward and flip
+			BColorPos *median_begin=median;
+			p=median_begin-1;
+
+			while(p!=(first-1)) {
+				if (median_begin->color==p->color) {
+					SWAP(*(median_begin-1),*p);
+					median_begin--;
+				}
+				p--;
+			}
+
+
+			if (first < median_begin) {
+				median=median_begin;
+			} else if (median_end < end-1) {
+				median=median_end+1;
+			} else {
+				break; //shouldn't have arrived here, since it means all pixels are equal, but wathever
+			}
+
+			MCBlock left(first,median-first);
+			MCBlock right(median,end-median);
+
+			block_queue.insert(left);
+			block_queue.insert(right);
+
+#else
+			switch(longest.get_longest_axis_index()) {
+				case 0: { SortArray<BColorPos,BColorPos::SortR> sort; sort.nth_element(0,end-first,median-first,first); } break;
+				case 1: { SortArray<BColorPos,BColorPos::SortG> sort; sort.nth_element(0,end-first,median-first,first); } break;
+				case 2: { SortArray<BColorPos,BColorPos::SortB> sort; sort.nth_element(0,end-first,median-first,first); } break;
+				case 3: { SortArray<BColorPos,BColorPos::SortA> sort; sort.nth_element(0,end-first,median-first,first); } break;
+
+			}
+
+			MCBlock left(first,median-first);
+			MCBlock right(median,end-median);
+
+			block_queue.insert(left);
+			block_queue.insert(right);
+
+
+#endif
+
+
+		}
+
+		while(block_queue.size() > 256) {
+
+			block_queue.erase(block_queue.front());// erase least significant
+		}
+
+		int res_colors=0;
+
+		int comp_size = (has_alpha?4:3);
+		indexed_data.resize(color_count + 256*comp_size);
+
+		DVector<uint8_t>::Write iw = indexed_data.write();
+		uint8_t *iwptr=&iw[0];
+		BColor pallete[256];
+
+	//	print_line("applying quantization - res colors "+itos(block_queue.size()));
+
+		while(block_queue.size()) {
+
+			const MCBlock &b = block_queue.back()->get();
+
+			uint64_t sum[4]={0,0,0,0};
+
+			for(int i=0;i<b.color_count;i++) {
+
+				sum[0]+=b.colors[i].color.col[0];
+				sum[1]+=b.colors[i].color.col[1];
+				sum[2]+=b.colors[i].color.col[2];
+				sum[3]+=b.colors[i].color.col[3];
+			}
+
+			BColor c( sum[0]/b.color_count, sum[1]/b.color_count, sum[2]/b.color_count, sum[3]/b.color_count );
+
+
+
+			//printf(" %i: %i,%i,%i,%i out of %i\n",res_colors,c.r,c.g,c.b,c.a,b.color_count);
+
+
+
+			for(int i=0;i<comp_size;i++) {
+				iwptr[ color_count + res_colors * comp_size + i ] = c.col[i];
+			}
+
+			if (quantize_fast) {
+				for(int i=0;i<b.color_count;i++) {
+					iwptr[b.colors[i].index]=res_colors;
+				}
+			} else {
+
+				pallete[res_colors]=c;
+			}
+
+
+			res_colors++;
+
+			block_queue.erase(block_queue.back());
+
+		}
+
+
+		if (!quantize_fast) {
+
+			for(int i=0;i<color_count;i++) {
+
+				const BColor &c=drptr[i];
+				uint8_t best_dist_idx=0;
+				uint32_t dist=0xFFFFFFFF;
+
+				for(int j=0;j<res_colors;j++) {
+
+					const BColor &pc=pallete[j];
+					uint32_t d = 0;
+					{ int16_t v = (int16_t)c.r-(int16_t)pc.r; d+=v*v; }
+					{ int16_t v = (int16_t)c.g-(int16_t)pc.g; d+=v*v; }
+					{ int16_t v = (int16_t)c.b-(int16_t)pc.b; d+=v*v; }
+					{ int16_t v = (int16_t)c.a-(int16_t)pc.a; d+=v*v; }
+
+					if (d<=dist) {
+						best_dist_idx=j;
+						dist=d;
+					}
+				}
+
+
+				iwptr[ i ] = best_dist_idx;
+
+			}
+		}
+
+		//iw = DVector<uint8_t>::Write();
+		//dr = DVector<uint8_t>::Read();
+		//wb = DVector<uint8_t>::Write();
+	}
+
+	print_line(itos(indexed_data.size()));
+	data=indexed_data;
+	format=has_alpha?FORMAT_INDEXED_ALPHA:FORMAT_INDEXED;
+
+
+} //do none
+
+
+
+#else
+
+
+void Image::quantize() {} //do none
+
+
+#endif