medfall

pp.cc (11624B)

---

 #include "intrinsics.h"
 #include "array.h"
 #include "memory_arena.h"
 #include "linear_algebra.h"
 #include "aabb.h"
 #include "dynstr.h"
 #include "int_conversions.h"
 #include "heightmap.h"
 #include "decompress_bc.h"
 #include "autogdb.h"
 
 #include "rng/pcg.h"
 
 #include "libs/lz4/lz4.h"
 #include "libs/lz4/lz4hc.h"
 
 #include "libs/squish/squish.h"
 
 #include "libs/stb/stb_image.h"
 #include "libs/stb/stb_image_write.h"
 
 static float tan_theta( v2 a, v2 b ) {
 	v2 d = a - b;
 	return -d.y / d.x;
 }
 
 static void compute_row_of_horizons(
 	MemoryArena * arena,
 	const array2d< u16 > heightmap, array2d< float > horizons,
 	size_t y
 ) {
 	MEMARENA_SCOPED_CHECKPOINT( arena );
 
 	array< v2 > hull = memarena_push_array( arena, v2, heightmap.w );
 	hull[ 0 ] = v2( 0, heightmap( 0, y ) / 256.0f );
 	horizons( 0, y ) = 0.0f;
 
 	size_t hull_size = 1;
 
 	for( size_t x = 1; x < heightmap.w; x++ ) {
 		v2 p( checked_cast< float >( x ), heightmap( x, y ) / 256.0f );
 
 		while( hull_size > 1 && tan_theta( p, hull[ hull_size - 1 ] ) <= tan_theta( hull[ hull_size - 1 ], hull[ hull_size - 2 ] ) ) {
 			hull_size--;
 		}
 
 		horizons( x, y ) = max( 0.0f, tan_theta( p, hull[ hull_size - 1 ] ) );
 
 		hull[ hull_size ] = p;
 		hull_size++;
 	}
 }
 
 static void compute_horizons(
 	MemoryArena * arena,
 	const array2d< u16 > heightmap, array2d< float > horizons
 ) {
 	ASSERT( heightmap.w == horizons.w && heightmap.h == horizons.h );
 
 	for( size_t y = 0; y < heightmap.h; y++ ) {
 		compute_row_of_horizons( arena, heightmap, horizons, y );
 	}
 }
 
 static v3 simple_normal( const array2d< u16 > heightmap, size_t x, size_t y ) {
 	size_t x_plus_one = x + 1;
 	size_t x_minus_one = x - 1;
 	size_t y_plus_one = y + 1;
 	size_t y_minus_one = y - 1;
 
 	if( x == 0 ) x_minus_one = x;
 	if( x == heightmap.w - 1 ) x_plus_one = x;
 	if( y == 0 ) y_minus_one = y;
 	if( y == heightmap.h - 1 ) y_plus_one = y;
 
 	v3 tangent(
 		checked_cast< float >( x_plus_one - x_minus_one ),
 		0,
 		heightmap( x_plus_one, y ) / 256.0f - heightmap( x_minus_one, y ) / 256.0f );
 	v3 bitangent(
 		0,
 		checked_cast< float >( y_plus_one - y_minus_one ),
 		heightmap( x, y_plus_one ) / 256.0f - heightmap( x, y_minus_one ) / 256.0f );
 
 	return normalize( cross( tangent, bitangent ) );
 }
 
 static v3 compute_normal( const array2d< u16 > heightmap, size_t x, size_t y ) {
 	if( x == 0 || x == heightmap.w - 1 || y == 0 || y == heightmap.h - 1 ) {
 		return simple_normal( heightmap, x, y );
 	}
 
 	float mm = heightmap( x - 1, y - 1 ) / 256.0f;
 	float me = heightmap( x - 1, y + 0 ) / 256.0f;
 	float mp = heightmap( x - 1, y + 1 ) / 256.0f;
 	float em = heightmap( x + 0, y - 1 ) / 256.0f;
 	// float ee = heightmap( x + 0, y + 0 ) / 256.0f;
 	float ep = heightmap( x + 0, y + 1 ) / 256.0f;
 	float pm = heightmap( x + 1, y - 1 ) / 256.0f;
 	float pe = heightmap( x + 1, y + 0 ) / 256.0f;
 	float pp = heightmap( x + 1, y + 1 ) / 256.0f;
 
 	float grad_y = -( mm + 2.0f * em + pm - ( mp + 2.0f * ep + pp ) ) / 8.0f;
 	float grad_x = -( mm + 2.0f * me + mp - ( pm + 2.0f * pe + pp ) ) / 8.0f;
 
 	v3 tangent = v3( 1, 0, grad_x );
 	v3 bitangent = v3( 0, 1, grad_y );
 
 	return normalize( cross( tangent, bitangent ) );
 }
 
 static void compute_normals( const array2d< u16 > heightmap, array2d< v3 > normals ) {
 	for( size_t y = 0; y < heightmap.h; y++ ) {
 		for( size_t x = 0; x < heightmap.w; x++ ) {
 			normals( x, y ) = compute_normal( heightmap, x, y );
 		}
 	}
 }
 
 static size_t quadtree_max_nodes( size_t w, size_t h ) {
 	// with a power of 2 + 1 sized quadtree with a 2x2 bottom level it
 	// should be exactly 1/3 (1/4 + 1/16 + ...)
 	return ( ( w - 1 ) * ( h - 1 ) ) / 3;
 }
 
 static size_t child_idx( size_t node_idx, size_t quadrant ) {
 	return node_idx * 4 + quadrant + 1;
 }
 
 static void build_quadtree_node( const array2d< u16 > heightmap, array< QuadTreeNode > & nodes, size_t node_idx, MinMaxu32 aabb ) {
 	nodes[ node_idx ].min_z = U16_MAX;
 	nodes[ node_idx ].max_z = 0;
 
 	if( aabb.maxs.x - aabb.mins.x == 2 || aabb.maxs.y - aabb.mins.y == 2 ) {
 		for( size_t y = aabb.mins.y; y <= aabb.maxs.y; y++ ) {
 			for( size_t x = aabb.mins.x; x <= aabb.maxs.x; x++ ) {
 				u16 h = heightmap( x, y );
 				nodes[ node_idx ].min_z = min( h, nodes[ node_idx ].min_z );
 				nodes[ node_idx ].max_z = max( h, nodes[ node_idx ].max_z );
 			}
 		}
 
 		return;
 	}
 
 	u16 lo = U16_MAX;
 	u16 hi = 0;
 	for( int i = 0; i < 4; i++ ) {
 		build_quadtree_node( heightmap, nodes, child_idx( node_idx, i ), aabb.quadrant( i ) );
 		lo = min( lo, nodes[ child_idx( node_idx, i ) ].min_z );
 		hi = max( hi, nodes[ child_idx( node_idx, i ) ].max_z );
 	}
 
 	nodes[ node_idx ].min_z = lo;
 	nodes[ node_idx ].max_z = hi;
 }
 
 static void build_quadtree( const array2d< u16 > heightmap, array< QuadTreeNode > & nodes ) {
 	ASSERT( nodes.n >= quadtree_max_nodes( heightmap.w, heightmap.h ) );
 	ASSERT( heightmap.w == heightmap.h );
 
 	size_t dim = heightmap.w - 1;
 	MinMaxu32 aabb( v3u32( 0, 0, 0 ), v3u32( dim, dim, U16_MAX ) );
 	build_quadtree_node( heightmap, nodes, 0, aabb );
 }
 
 static void write_compressed_file( MemoryArena * arena, const DynamicString & path, const void * data, size_t len ) {
 	MEMARENA_SCOPED_CHECKPOINT( arena );
 
 	const int COMPRESSION_LEVEL = LZ4HC_DEFAULT_CLEVEL;
 	int lz4_bound = LZ4_compressBound( len );
 	char * lz4 = memarena_push_many( arena, char, lz4_bound );
 	int lz4_size = LZ4_compress_HC( ( const char * ) data, lz4, len, lz4_bound, COMPRESSION_LEVEL );
 
 	FILE * file = fopen( path.c_str(), "wb" );
 	ASSERT( file != NULL );
 	fwrite( lz4, 1, lz4_size, file );
 	ASSERT( ferror( file ) == 0 );
 	fclose( file );
 }
 
 struct RGBA { u8 r, g, b, a; };
 
 static u8 * write_compressed_texture( MemoryArena * arena, const DynamicString & path, const array2d< RGBA > data, int squish_flags ) {
 	int w = checked_cast< int >( data.w );
 	int h = checked_cast< int >( data.h );
 
 	int dxt_size = squish::GetStorageRequirements( w, h, squish_flags );
 	u8 * dxt = memarena_push_many( arena, u8, dxt_size );
 	squish::CompressImage( ( const u8 * ) data.ptr(), w, h, dxt, squish_flags );
 
 	write_compressed_file( arena, path, dxt, dxt_size );
 
 	// DynamicString png_path( "{}.png", path );
 	// stbi_write_png( png_path.c_str(), data.w, data.h, 4, data.ptr(), 0 );
 
 	return dxt;
 }
 
 const size_t MAX_TREES = 262144 / 4;
 
 static bool ok_tree_position( PCG * rng, const array2d< u16 > heightmap, const array2d< v3 > normalmap, v2 pos, v3 * tree ) {
 	u16 height = bilerp01( heightmap, pos.x, pos.y );
 	double p = 1;
 	if( height <= 5 * 256 ) return false;
 	if( height > 235 * 256 ) return false;
 	if( height >= 200 * 256 ) {
 		p *= double( 235 * 256 - height ) / double( 235 * 256 - 200 * 256 );
 	}
 
 	v3 normal = normalize( bilerp01( normalmap, pos.x, pos.y ) );
 	if( normal.z < 0.3 ) return false;
 
 	p *= ( normal.z - 0.3 ) / 0.7;
 
 	if( !rng_p( rng, p ) ) return false;
 
 	*tree = v3( pos.x * heightmap.w, pos.y * heightmap.h, height / 256.0f );
 	return true;
 }
 
 static void hammersley( size_t n, array< v2 > points ) {
 	for( size_t i = 0; i < n; i++ ) {
 		float u = 0;
 		float v = ( i + 0.5f ) / n;
 		float p = 0.5;
 
 		size_t x = i;
 		while( x > 0 ) {
 			if( x % 2 == 1 ) u += p;
 			p /= 2;
 			x /= 2;
 		}
 
 		points[ i ] = v2( u, v );
 	}
 }
 
 static size_t place_trees( MemoryArena * arena, const array2d< u16 > heightmap, const array2d< v3 > normalmap, array< v3 > trees ) {
 	MEMARENA_SCOPED_CHECKPOINT( arena );
 
 	array< v2 > points = memarena_push_array( arena, v2, trees.n );
 	hammersley( MAX_TREES, points );
 
 	PCG rng = new_pcg();
 
 	size_t placed = 0;
 	for( v2 point : points ) {
 		v3 pos;
 		if( ok_tree_position( &rng, heightmap, normalmap, point, &pos ) ) {
 			trees[ placed ] = pos;
 			placed++;
 		}
 	}
 
 	return placed;
 }
 
 int main( int argc, char ** argv ) {
 	install_debug_signal_handlers();
 
 	static u8 arena_memory[ megabytes( 512 ) ];
 	MemoryArena arena;
 	memarena_init( &arena, arena_memory, ARRAY_COUNT( arena_memory ) );
 
 	DynamicString input_path( "terrains/gta16.png" );
 	DynamicString output_path( "{}.parts", input_path );
 
 	printf( "decoding\n" );
 	int w, h;
 	u16 * png = ( u16 * ) stbi_load_16( input_path.c_str(), &w, &h, NULL, 1 );
 	ASSERT( png != NULL );
 
 	array2d< u16 > heightmap( png, w, h );
 	array2d< u16 > bc5_heightmap = alloc_array2d< u16 >( &arena, heightmap.w, heightmap.h );
 
 	mkdir( "terrains", 0755 );
 	mkdir( output_path.c_str(), 0755 );
 
 	{
 		MEMARENA_SCOPED_CHECKPOINT( &arena );
 		printf( "computing heightmaps\n" );
 
 		array2d< RGBA > heightmap_split = alloc_array2d< RGBA >( &arena, w, h );
 
 		for( int y = 0; y < h; y++ ) {
 			for( int x = 0; x < w; x++ ) {
 				heightmap_split( x, y ).r = heightmap( x, y ) / 256;
 				heightmap_split( x, y ).g = heightmap( x, y ) % 256;
 				heightmap_split( x, y ).b = 0;
 				heightmap_split( x, y ).a = 255;
 			}
 		}
 
 		printf( "compressing\n" );
 		DynamicString heightmap_path( "{}/heightmap.bc5.lz4", output_path );
 		u8 * bc5 = write_compressed_texture( &arena, heightmap_path, heightmap_split, squish::kBc5 );
 
 		bc5_to_heightmap( &arena, bc5_heightmap, bc5 );
 	}
 
 	{
 		MEMARENA_SCOPED_CHECKPOINT( &arena );
 		printf( "computing normalmap\n" );
 
 		array2d< v3 > normalmap_v3 = alloc_array2d< v3 >( &arena, w, h );
 		array2d< RGBA > normalmap = alloc_array2d< RGBA >( &arena, w, h );
 
 		compute_normals( heightmap, normalmap_v3 );
 		for( int y = 0; y < h; y++ ) {
 			for( int x = 0; x < w; x++ ) {
 				normalmap( x, y ).r = quantize01( ( normalmap_v3( x, y ).x + 1.0f ) / 2.0f, 8 );
 				normalmap( x, y ).g = quantize01( ( normalmap_v3( x, y ).y + 1.0f ) / 2.0f, 8 );
 				normalmap( x, y ).b = 0;
 				normalmap( x, y ).a = 255;
 			}
 		}
 
 		printf( "compressing\n" );
 		DynamicString normalmap_path( "{}/normalmap.bc5.lz4", output_path );
 		write_compressed_texture( &arena, normalmap_path, normalmap, squish::kBc5 );
 
 		{
 			printf( "planting trees\n" );
 
 			array< v3 > trees = alloc_array< v3 >( &arena, MAX_TREES );
 			size_t num_trees = place_trees( &arena, bc5_heightmap, normalmap_v3, trees );
 
 			printf( "compressing\n" );
 			DynamicString trees_path( "{}/trees.lz4", output_path );
 			write_compressed_file( &arena, trees_path, trees.ptr(), num_trees * sizeof( v3 ) );
 		}
 	}
 
 	{
 		MEMARENA_SCOPED_CHECKPOINT( &arena );
 		printf( "computing horizonmap\n" );
 
 		array2d< float > horizonmap_float = alloc_array2d< float >( &arena, w, h );
 		array2d< RGBA > horizonmap = alloc_array2d< RGBA >( &arena, w, h );
 
 		compute_horizons( &arena, heightmap, horizonmap_float );
 		for( int y = 0; y < h; y++ ) {
 			for( int x = 0; x < w; x++ ) {
 				float theta01 = atanf( horizonmap_float( x, y ) ) * 2.0f / PI;
 				horizonmap( x, y ).r = quantize01( theta01, 8 );
 				horizonmap( x, y ).g = 0;
 				horizonmap( x, y ).b = 0;
 				horizonmap( x, y ).a = 255;
 			}
 		}
 
 		printf( "compressing\n" );
 		DynamicString horizonmap_path( "{}/horizonmap.bc4.lz4", output_path );
 		write_compressed_texture( &arena, horizonmap_path, horizonmap, squish::kBc4 );
 	}
 
 	{
 		MEMARENA_SCOPED_CHECKPOINT( &arena );
 		printf( "computing quadtree\n" );
 
 		// quadtree needs POT+1 heightmap, so pad with zeroes
 		array2d< u16 > heightmap1 = alloc_array2d< u16 >( &arena, heightmap.w + 1, heightmap.h + 1 );
 		for( size_t y = 0; y < heightmap1.h; y++ ) {
 			for( size_t x = 0; x < heightmap1.w; x++ ) {
 				heightmap1( x, y ) = bc5_heightmap.try_get( x, y, 0 );
 			}
 		}
 
 		size_t num_nodes = quadtree_max_nodes( heightmap1.w, heightmap1.h );
 		array< QuadTreeNode > nodes = alloc_array< QuadTreeNode >( &arena, num_nodes );
 
 		build_quadtree( heightmap1, nodes );
 
 		printf( "compressing\n" );
 		DynamicString quadtree_path( "{}/quadtree.lz4", output_path );
 		write_compressed_file( &arena, quadtree_path, nodes.ptr(), nodes.num_bytes() );
 	}
 
 	stbi_image_free( png );
 
 	return 0;
 }