Blame c++/perspective/src/generator.cpp

531f67
#include <ctime></ctime>
531f67
3a6f9b
#include <iostream></iostream>
3a6f9b
531f67
#include "generator.h"
531f67
531f67
5f2fc2
void
5f2fc2
Generator::GenSurface::reset() {
5f2fc2
	if (data) delete[] data;
5f2fc2
	data = nullptr;
5f2fc2
	w = h = 0;
5f2fc2
	m_offset = ULongIntVector2();
5f2fc2
	m_step = 0;
5f2fc2
}
5f2fc2
5f2fc2
void
5f2fc2
Generator::GenSurface::create(const ULongIntPair2 &bounds, ULongInt step) {
5f2fc2
	ULongIntPair2 b = bounds;
5f2fc2
5f2fc2
	reset();
5f2fc2
	
5f2fc2
	assert(!(step & (step - 1)));
5f2fc2
	assert(b.p1.x != b.p0.x);
5f2fc2
	assert(b.p1.y != b.p0.y);
5f2fc2
	assert(b.p1.x - b.p0.x <= big);
5f2fc2
	assert(b.p1.y - b.p0.y <= big);
5f2fc2
	
5f2fc2
	b.p0.x = b.p0.x & ~(step - 1);
5f2fc2
	b.p0.y = b.p0.y & ~(step - 1);
5f2fc2
	if (!(b.p0.x & step)) b.p0.x -= step;
5f2fc2
	if (!(b.p0.y & step)) b.p0.y -= step;
5f2fc2
	
5f2fc2
	b.p1.x = ((b.p1.x - 1) & ~(step - 1)) + step;
5f2fc2
	b.p1.y = ((b.p1.y - 1) & ~(step - 1)) + step;
5f2fc2
	if (!(b.p1.x & step)) b.p1.x += step;
5f2fc2
	if (!(b.p1.y & step)) b.p1.y += step;
5f2fc2
	
5f2fc2
	w = (b.p1.x - b.p0.x)/step + 1;
5f2fc2
	h = (b.p1.y - b.p0.y)/step + 1;
5f2fc2
5f2fc2
	assert(w <= max_side);
5f2fc2
	assert(h <= max_side);
5f2fc2
	assert(w*h <= max_area);
5f2fc2
	
5f2fc2
	m_step = step;
5f2fc2
	m_offset = b.p0;
5f2fc2
	data = new Vector4[w*h];
5f2fc2
	
5f2fc2
	assert(is_valid());
5f2fc2
}
5f2fc2
5f2fc2
Generator::GenSurface&
5f2fc2
Generator::GenSurface::operator= (const GenSurface &other) {
5f2fc2
	if (&other != this) {
5f2fc2
		reset();
5f2fc2
		if (other.is_valid()) {
5f2fc2
			w = other.w;
5f2fc2
			h = other.h;
5f2fc2
			m_offset = other.m_offset;
5f2fc2
			m_step = other.m_step;
5f2fc2
			data = new Vector4[w*h];
5f2fc2
			memcpy(data, other.data, sizeof(Vector4)*w*h);
5f2fc2
			assert(is_valid());
5f2fc2
		}
5f2fc2
	}
5f2fc2
	return *this;
5f2fc2
}
5f2fc2
5f2fc2
5f2fc2
531f67
Generator::Generator(): Generator(random(time(NULL))) { }
531f67
531f67
Generator::Generator(ULongInt seed):
3a6f9b
	max_cache_count(4ll*1024*1024*1024/sizeof(CacheEntry))
531f67
{
531f67
	set_seed(seed);
531f67
	LongIntVector2 a(1, 2);
531f67
	LongIntVector2 b(3);
531f67
	m_cache[ULongIntVector2()];
531f67
	m_cache_top = m_cache.begin();
531f67
	m_cache_top->second.next = m_cache_top->second.previous = m_cache_top;
531f67
}
531f67
531f67
void
531f67
Generator::set_seed(ULongInt x) {
531f67
	for(int i = 0; i < 2; ++i)
531f67
		for(int j = 0; j < 4; ++j)
531f67
			x = random( m_seeds[i][j] = x );
531f67
}
531f67
531f67
531f67
Real
531f67
Generator::random(const ULongIntVector2 &coord, int index) const {
5f2fc2
	ULongInt rx = coord.x ^ seeds_x()[index];
5f2fc2
	ULongInt ry = coord.y ^ seeds_y()[index];
5f2fc2
	ULongInt seed = random(rx ^ random(ry));
5f2fc2
	seed = random(seed ^ ry);
5f2fc2
	seed = random(seed ^ random(rx));
5f2fc2
	return random_to_real(seed)*2 - 1;
5f2fc2
	//return random_to_normal(seed, random(seed));
531f67
}
531f67
531f67
Vector4
531f67
Generator::generate(const ULongIntVector2 &coord, bool shrink_cache) const {
531f67
	// search value in cache
531f67
	
531f67
	Cache::iterator i = m_cache.find(coord);
531f67
	bool found = i != m_cache.end();
531f67
	if (found) {
531f67
		i->second.previous->second.next = i->second.next;
531f67
		i->second.next->second.previous = i->second.previous;
531f67
		assert(!i->second.in_use);
531f67
		if (i->second.in_use) return i->second.value;
531f67
	} else {
531f67
		i = m_cache.insert(Cache::value_type(coord, CacheEntry())).first;
531f67
		++m_cache_count;
531f67
	}
531f67
	i->second.in_use = true;
531f67
	i->second.previous = m_cache_top;
531f67
	i->second.next = i->second.previous->second.next;
531f67
	m_cache_top = i;
531f67
	i->second.previous->second.next = i;
531f67
	i->second.next->second.previous = i;
531f67
531f67
	while (shrink_cache && m_cache_count > max_cache_count) {
531f67
		Cache::iterator ri = m_cache_top->second.next;
531f67
		if (ri->second.in_use) break;
531f67
		ri->second.previous->second.next = ri->second.next;
531f67
		ri->second.next->second.previous = ri->second.previous;
531f67
		m_cache.erase(ri);
531f67
		--m_cache_count;
531f67
	}
531f67
	
531f67
	Vector4 &value = i->second.value;
531f67
	if (!found) {
531f67
		// generate new value
531f67
		
531f67
		for(int j = 0; j < 4; ++j)
531f67
			value[j] = random(coord, j);
531f67
		
531f67
		ULongInt x_minus_one = coord.x - 1;
531f67
		ULongInt y_minus_one = coord.y - 1;
531f67
		ULongInt level_x = coord.x ? (coord.x ^ x_minus_one) >> 1 : (ULongInt)-1;
531f67
		ULongInt level_y = coord.y ? (coord.y ^ y_minus_one) >> 1 : (ULongInt)-1;
531f67
		ULongInt level = (level_x < level_y ? level_x : level_y) + 1;
531f67
a1942e
		if (level && level < one) {
077021
			value /= one/level;
531f67
			if (level_x == level_y) {
531f67
				// square corners
531f67
				value += ( generate(ULongIntVector2(coord.x - level, coord.y - level))
077021
						 + generate(ULongIntVector2(coord.x - level, coord.y + level))
077021
						 + generate(ULongIntVector2(coord.x + level, coord.y - level))
077021
						 + generate(ULongIntVector2(coord.x + level, coord.y + level)) )*0.25;
531f67
			} else {
531f67
				// diamond corners
531f67
				value += ( generate(ULongIntVector2(coord.x - level, coord.y))
077021
						 + generate(ULongIntVector2(coord.x + level, coord.y))
077021
						 + generate(ULongIntVector2(coord.x, coord.y - level))
077021
						 + generate(ULongIntVector2(coord.x, coord.y + level)) )*0.25;
531f67
			}
531f67
		}
531f67
	}
531f67
	i->second.in_use = false;
531f67
	
531f67
	return value;
531f67
}
531f67
531f67
Vector4
531f67
Generator::generate(const Vector2 &coord, const Vector2 &precision) const {
531f67
	const int bits = clz(ULongInt(0));
531f67
	
531f67
	ULongIntVector2 coord_int(
531f67
		(ULongInt)(LongInt)(coord.x*one),
531f67
		(ULongInt)(LongInt)(coord.y*one) );
531f67
	ULongIntVector2 precision_int(
531f67
		(ULongInt)(LongInt)(precision.x*one),
531f67
		(ULongInt)(LongInt)(precision.y*one) );
531f67
	int level_x = bits - clz(precision_int.x);
531f67
	int level_y = bits - clz(precision_int.y);
531f67
	coord_int.x = (coord_int.x >> level_x) << level_x;
531f67
	coord_int.y = (coord_int.y >> level_y) << level_y;
531f67
	return generate(coord_int);
531f67
}
531f67
531f67
void
5f2fc2
Generator::generate(GenSurface &target) const {
5f2fc2
	assert(target.is_valid());
5f2fc2
	const ULongInt step = target.step();
5f2fc2
	
5f2fc2
	if (step && step < one) {
5f2fc2
		ULongIntVector2 onev(one, one);
5f2fc2
		GenSurface surface(ULongIntPair2(target.p0() - onev, target.p1() + onev), one);
5f2fc2
		generate(surface);
5f2fc2
		generate(target, surface);
5f2fc2
		return;
5f2fc2
	}
5f2fc2
	
5f2fc2
	const ULongInt w = target.width();
5f2fc2
	const ULongInt h = target.height();
5f2fc2
5f2fc2
	const ULongInt report_count = 1ull*1024ull*1024ull;
5f2fc2
	std::cout << "    generate base " << w << "x" << h << ": ";
5f2fc2
	ULongInt count = 0;
5f2fc2
	
5f2fc2
	const ULongIntVector2 p0 = target.p0();
5f2fc2
	ULongIntVector2 p = p0;
5f2fc2
	for(ULongInt y = 0; y < h; ++y, p.x = p0.x, p.y += step) {
5f2fc2
		Vector4 *pixel = target[y];
5f2fc2
		for(ULongInt x = 0; x < w; ++x, ++pixel, p.x += step) {
5f2fc2
			for(int j = 0; j < 4; ++j)
5f2fc2
				(*pixel)[j] = random(p, j);
5f2fc2
		}
5f2fc2
		if ((count += w) >= report_count) { std::cout << "."; count = 0; }
5f2fc2
	}
5f2fc2
5f2fc2
	std::cout << std::endl;
5f2fc2
}
5f2fc2
5f2fc2
void
5f2fc2
Generator::generate(GenSurface &target, const GenSurface &source) const {
5f2fc2
	assert(target.is_valid());
5f2fc2
	assert(source.is_valid());
5f2fc2
	assert(target.step());
5f2fc2
	assert(target.step() < one);
5f2fc2
	assert(source.step());
5f2fc2
	assert(source.step() <= one);
5f2fc2
	assert(source.step() > target.step());
5f2fc2
	
5f2fc2
	const ULongInt step = target.step();
5f2fc2
	const ULongInt source_step = step << 1;
5f2fc2
	
5f2fc2
	if (source_step != source.step()) {
5f2fc2
		GenSurface surface(ULongIntPair2(target.p0(), target.p1()), source_step);
5f2fc2
		generate(surface, source);
5f2fc2
		generate(target, surface);
5f2fc2
		return;
5f2fc2
	}
5f2fc2
5f2fc2
	const ULongInt tw = target.width();
5f2fc2
	const ULongInt th = target.height();
5f2fc2
5f2fc2
	const ULongInt sw = source.width();
5f2fc2
	const ULongInt sh = source.height();
5f2fc2
	
5f2fc2
	const ULongIntVector2 target_offset = target.offset();
5f2fc2
	
5f2fc2
	const ULongIntVector2 shift(
5f2fc2
		(target.offset().x - source.offset().x)/step,
5f2fc2
		(target.offset().y - source.offset().y)/step );
5f2fc2
	assert(shift.x);
5f2fc2
	assert(shift.y);
5f2fc2
	assert(shift.x <= max_side << 1);
5f2fc2
	assert(shift.y <= max_side << 1);
5f2fc2
	
5f2fc2
	assert(sw > (tw - 1 + shift.x)/2 + 1);
5f2fc2
	assert(sh > (th - 1 + shift.y)/2 + 1);
5f2fc2
	
5f2fc2
	const Real deviation_base = 0.65;
5f2fc2
	Real deviation = 1;
5f2fc2
	for(ULongInt i = one; step < i; i >>= 1)
5f2fc2
		deviation *= deviation_base;
5f2fc2
	//const Real deviation = Real(step)/one;
5f2fc2
	
5f2fc2
	ULongIntVector2 coord, start;
5f2fc2
5f2fc2
	const ULongInt report_count = 2ull*1024ull*1024ull;
5f2fc2
	std::cout << "    generate subs " << tw << "x" << th << ": ";
5f2fc2
	ULongInt count = 0;
5f2fc2
	
5f2fc2
	// copy
5f2fc2
	ULongInt x0 = 1, y0 = 1;
5f2fc2
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
5f2fc2
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
5f2fc2
		Vector4* tp  = &target[y][x0];
5f2fc2
		ULongInt sy  = (y  + shift.y)/2;
5f2fc2
		ULongInt sx0 = (x0 + shift.x)/2;
5f2fc2
		const Vector4* sp  = &source[sy][sx0];
5f2fc2
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, ++sp)
5f2fc2
			*tp = *sp;
5f2fc2
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
5f2fc2
	}
5f2fc2
	
5f2fc2
	// square
5f2fc2
	x0 = 0, y0 = 0;
5f2fc2
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
5f2fc2
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
5f2fc2
		Vector4* tp  = &target[y][x0];
5f2fc2
		ULongInt sy  = (y  + shift.y)/2;
5f2fc2
		ULongInt sx0 = (x0 + shift.x)/2;
5f2fc2
		const Vector4* sp0 = &source[sy][sx0];
5f2fc2
		const Vector4* sp1 = &source[sy + 1][sx0];
5f2fc2
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, ++sp0, ++sp1) {
5f2fc2
			*tp = Vector4(
5f2fc2
					random(coord, 0),
5f2fc2
					random(coord, 1),
5f2fc2
					random(coord, 2),
5f2fc2
					random(coord, 3) )*deviation
5f2fc2
				+ (sp0[0] + sp0[1] + sp1[0] + sp1[1])*0.25;
5f2fc2
		}
5f2fc2
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
5f2fc2
	}
5f2fc2
5f2fc2
	// diamond 1
5f2fc2
	x0 = 1, y0 = 0;
5f2fc2
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
5f2fc2
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
5f2fc2
		Vector4* tp  = &target[y][x0];
5f2fc2
		ULongInt sy  = (y  + shift.y)/2;
5f2fc2
		ULongInt sx0 = (x0 + shift.x)/2;
5f2fc2
		const Vector4* sp0 = &source[sy][sx0];
5f2fc2
		const Vector4* sp1 = &source[sy + 1][sx0];
5f2fc2
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, ++sp0, ++sp1) {
5f2fc2
			*tp = Vector4(
5f2fc2
					random(coord, 0),
5f2fc2
					random(coord, 1),
5f2fc2
					random(coord, 2),
5f2fc2
					random(coord, 3) )*deviation
5f2fc2
				+ (*sp0 + *sp1 + *(tp-1) + *(tp+1))*0.25;
5f2fc2
		}
5f2fc2
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
5f2fc2
	}
5f2fc2
5f2fc2
	// diamond 2
5f2fc2
	x0 = 0, y0 = 1;
5f2fc2
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
5f2fc2
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
5f2fc2
		Vector4* tp  = &target[y  ][x0];
5f2fc2
		Vector4* tp0 = &target[y-1][x0];
5f2fc2
		Vector4* tp1 = &target[y+1][x0];
5f2fc2
		ULongInt sy  = (y  + shift.y)/2;
5f2fc2
		ULongInt sx0 = (x0 + shift.x)/2;
5f2fc2
		const Vector4* sp = &source[sy][sx0];
5f2fc2
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, tp0 += 2, tp1 += 2, ++sp) {
5f2fc2
			*tp = Vector4(
5f2fc2
					random(coord, 0),
5f2fc2
					random(coord, 1),
5f2fc2
					random(coord, 2),
5f2fc2
					random(coord, 3) )*deviation
5f2fc2
				+ (sp[0] + sp[1] + *tp0 + *tp1)*0.25;
5f2fc2
		}
5f2fc2
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
5f2fc2
	}
5f2fc2
5f2fc2
	std::cout << std::endl;
5f2fc2
}
5f2fc2
5f2fc2
5f2fc2
void
4dc49c
Generator::generate(Surface &target, const Pair2 &bounds) const {
531f67
	if (target.empty()) return;
5f2fc2
	
5f2fc2
	const int w = target.width();
5f2fc2
	const int h = target.height();
5f2fc2
	
5f2fc2
	std::cout << "generate " << w << "x" << h << std::endl;
5f2fc2
5f2fc2
	assert(fabs(bounds.p0.x)*one < big);
5f2fc2
	assert(fabs(bounds.p0.y)*one < big);
5f2fc2
	assert(fabs(bounds.p1.x)*one < big);
5f2fc2
	assert(fabs(bounds.p1.y)*one < big);
5f2fc2
	
4dc49c
	Vector2 d = bounds.distance();
5f2fc2
	d.x /= w;
5f2fc2
	d.y /= h;
5f2fc2
	const Vector2 precision(fabs(d.x/2.0), fabs(d.x/2.0));
5f2fc2
	const Real precision_max = std::max(precision.x, precision.y);
531f67
	
5f2fc2
	Color gray(0.5, 0.5, 0.5, 0.5);
5f2fc2
	if (precision_max >= Real(gray1)/Real(one)) {
5f2fc2
		// fill target by gray color
5f2fc2
		std::cout << "    gray" << std::endl;
5f2fc2
		for(int r = 0; r < h; ++r) {
5f2fc2
			Color *p = target[r];
5f2fc2
			for(int c = 0; c < w; ++c, ++p)
5f2fc2
				*p = gray;
5f2fc2
		}
5f2fc2
		return;
5f2fc2
	}
5f2fc2
	
5f2fc2
	Real gray_alpha = 0;
5f2fc2
	if (precision_max > Real(gray0)/Real(one)) {
5f2fc2
		Real l0 = log(Real(gray0)/Real(one));
5f2fc2
		Real l1 = log(Real(gray1)/Real(one));
5f2fc2
		Real lp = log(precision_max);
5f2fc2
		gray_alpha = (lp - l0)/(l1 - l0);
5f2fc2
	}
5f2fc2
	Real alpha = 1.0 - gray_alpha;
5f2fc2
	gray *= gray_alpha;
5f2fc2
	
5f2fc2
	const ULongIntPair2 gen_bounds(
5f2fc2
		ULongIntVector2( ULongInt(floor(bounds.p0.x*one)) - 1,
5f2fc2
						 ULongInt(floor(bounds.p0.y*one)) - 1 ),
5f2fc2
		ULongIntVector2( ULongInt(ceil (bounds.p1.x*one)) + 1,
5f2fc2
						 ULongInt(ceil (bounds.p1.y*one)) + 1 ));
3a6f9b
	
5f2fc2
	ULongInt step_x = 1, step_y = 1;
5f2fc2
	while(step_x < precision.x*one - real_precision && step_x < big) step_x <<= 1;
5f2fc2
	while(step_y < precision.y*one - real_precision && step_y < big) step_y <<= 1;
5f2fc2
	
5f2fc2
	const ULongInt step_max = std::max(step_x, step_y);
5f2fc2
	const ULongInt step_min = std::min(step_x, step_y);
5f2fc2
	const ULongInt step_diff = step_max / step_min;
5f2fc2
	assert(step_diff);
5f2fc2
5f2fc2
	const ULongInt step_base = step_max/std::min(step_diff, 1ull << 2);
5f2fc2
	GenSurface gen_surface(gen_bounds, step_base);
5f2fc2
	generate(gen_surface);
5f2fc2
	
5f2fc2
	std::cout << "    convert" << std::endl;
5f2fc2
	const ULongInt step = gen_surface.step();
5f2fc2
	const ULongIntVector2 offset(
5f2fc2
		gen_surface.offset().x - step/2,
5f2fc2
		gen_surface.offset().y - step/2 );
4dc49c
	Vector2 p = bounds.p0;
4dc49c
	for(int r = 0; r < target.height(); ++r, p.x = bounds.p0.x, p.y += d.y) {
5f2fc2
		Color *pixel = target[r];
5f2fc2
		ULongInt rr = (ULongInt(round(p.y*one)) - offset.y)/step;
5f2fc2
		assert(rr < gen_surface.height());
5f2fc2
		
5f2fc2
		for(int c = 0; c < target.width(); ++c, ++pixel, p.x += d.x) {
5f2fc2
			ULongInt cc = (ULongInt(round(p.x*one)) - offset.x)/step;
5f2fc2
			assert(cc < gen_surface.width());
5f2fc2
			
5f2fc2
			const Vector4 &v = gen_surface[rr][cc];
5f2fc2
			*pixel = Color( flip_clamp((v.x + 1)*0.5),
5f2fc2
							flip_clamp((v.y + 1)*0.5),
5f2fc2
							flip_clamp((v.z + 1)*0.5),
5f2fc2
							flip_clamp((v.w + 1)*0.5) )*alpha + gray;
531f67
		}
531f67
	}
531f67
}
57974f
57974f
57974f
Real
57974f
Generator::checks_value(Real coord, Real inv_precision) const {
57974f
	Real x = fabs(coord - floor(coord) - 0.5);
57974f
	return clamp(inv_precision*(0.25 - x), -1, 1);
57974f
}
57974f
57974f
Real
57974f
Generator::checks_value(const Vector2 &coord, const Vector2 &inv_precision) const {
57974f
	Real x = checks_value(coord.x, inv_precision.x)
57974f
		   * checks_value(coord.y, inv_precision.y);
57974f
	return (x + 1)*0.5;
57974f
}
57974f
57974f
void
57974f
Generator::generate_checks(Surface &target, const Pair2 &bounds) const {
57974f
	if (target.empty()) return;
57974f
	
57974f
	const int w = target.width();
57974f
	const int h = target.height();
57974f
	
57974f
	const Color colors[2] = {
57974f
		Color(1, 1, 1, 1),
57974f
		Color(0, 0, 1, 1) };
57974f
	
57974f
	Vector2 d = bounds.distance();
57974f
	d.x /= w;
57974f
	d.y /= h;
57974f
	
57974f
	Vector2 inv_precision(
57974f
		2/std::max(fabs(d.x), real_precision),
57974f
		2/std::max(fabs(d.y), real_precision) );
57974f
57974f
	Vector2 p = bounds.p0;
57974f
	for(int r = 0; r < h; ++r, p.x = bounds.p0.x, p.y += d.y) {
57974f
		Color *pixel = target[r];
57974f
		Real ay = checks_value(p.y, inv_precision.y);
57974f
		for(int c = 0; c < w; ++c, ++pixel, p.x += d.x) {
57974f
			Real ax = checks_value(p.x, inv_precision.x);
57974f
			Real a = (ax*ay + 1)*0.5;
57974f
			*pixel = colors[0]*a + colors[1]*(1 - a);
57974f
		}
57974f
	}
57974f
}