medfall

commit 4a650ec06feada62f855dd8e04b2a0758c6a8b47
parent 24df7e4f19e86902d654c4fd0ef5687be9d2ace2
Author: Michael Savage <mikejsavage@gmail.com>
Date:   Sun, 29 Oct 2017 23:05:40 +0200

Semi-functional collision detection in the clipmap engine

Diffstat:
clipmap.cc
 | 
91
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------------
main.cc
 | 
2
+-
make.lua
 | 
2
+-
pp2.cc
 | 
85
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------

4 files changed, 152 insertions(+), 28 deletions(-)
diff --git a/clipmap.cc b/clipmap.cc
@@ -3,16 +3,26 @@
 #include "game.h"
 #include "renderer.h"
 #include "shaders.h"
+#include "immediate.h"
 #include "text_renderer.h"
 #include "gl.h"
 #include "skybox.h"
 
 #include "libs/lz4/lz4.h"
 
-static Mesh patch;
-static Texture heightmap;
-static Texture normalmap;
-static Texture horizonmap;
+#include "libs/squish/squish.h"
+
+struct ClipmapTerrain
+{
+	Mesh tile;
+	Mesh seam;
+	Texture heightmap;
+	Texture normalmap;
+	Texture horizonmap;
+	HeightmapQuadTree quadtree;
+};
+
+static ClipmapTerrain clipmap;
 
 static u32 PATCH_RESOLUTION = 80;
 static u32 NUM_LODS = 5;
@@ -29,19 +39,32 @@ static void file_get_contents_and_decompress( const char * path, u8 * decompress
 	free( compressed );
 }
 
+struct RGBA {
+	u8 r, g, b, a;
+};
+
 GAME_INIT( game_init ) {
 	{
 		MEMARENA_SCOPED_CHECKPOINT( &mem->persistent_arena );
 
-		u8 * heightmap_data = memarena_push_size( &mem->persistent_arena, 4096 * 4096 );
-		u8 * normalmap_data = memarena_push_size( &mem->persistent_arena, 4096 * 4096 );
-		u8 * horizonmap_data = memarena_push_size( &mem->persistent_arena, 4096 * 4096 / 2 );
+		Heightmap * hm = alloc< Heightmap >( &mem->persistent_arena );
+		hm->width = hm->height = 4096;
+		hm->pixels = memarena_push_many( &mem->persistent_arena, u16, 4096 * 4096 );
 
-		file_get_contents_and_decompress( "terrains/gta16.png.parts/heightmap.bc5.lz4", heightmap_data, 4096 * 4096 );
-		file_get_contents_and_decompress( "terrains/gta16.png.parts/normalmap.bc5.lz4", normalmap_data, 4096 * 4096 );
-		file_get_contents_and_decompress( "terrains/gta16.png.parts/horizonmap.bc4.lz4", horizonmap_data, 4096 * 4096 / 2 );
+		array< HeightmapQuadTreeNode > nodes = alloc_array< HeightmapQuadTreeNode >( &mem->persistent_arena, 4096 * 4096 / 3 );
+		file_get_contents_and_decompress( "terrains/gta16.png.parts/quadtree.lz4", ( u8 * ) nodes.ptr(), nodes.num_bytes() );
+
+		clipmap.quadtree.dim = 4096;
+		clipmap.quadtree.hm = hm;
+		clipmap.quadtree.nodes_memory = nodes.ptr();
+		clipmap.quadtree.nodes = nodes;
 
 		{
+			MEMARENA_SCOPED_CHECKPOINT( &mem->persistent_arena );
+
+			u8 * heightmap_data = memarena_push_size( &mem->persistent_arena, 4096 * 4096 );
+			file_get_contents_and_decompress( "terrains/gta16.png.parts/heightmap.bc5.lz4", heightmap_data, 4096 * 4096 );
+
 			TextureConfig texture_config;
 			texture_config.width = 4096;
 			texture_config.height = 4096;
@@ -49,10 +72,22 @@ GAME_INIT( game_init ) {
 			texture_config.format = TEXFMT_BC5;
 			texture_config.wrap = TEXWRAP_BORDER;
 			texture_config.border_colour = v4( 0 );
-			heightmap = renderer_new_texture( texture_config );
+			clipmap.heightmap = renderer_new_texture( texture_config );
+
+			RGBA * rgba = memarena_push_many( &mem->persistent_arena, RGBA, 4096 * 4096 );
+			squish::DecompressImage( ( u8 * ) rgba, 4096, 4096, heightmap_data, squish::kBc5 );
+
+			for( size_t i = 0; i < 4096 * 4096; i++ ) {
+				clipmap.quadtree.hm->pixels[ i ] = u16( rgba[ i ].r ) * u16( 255 ) + u16( rgba[ i ].g );
+			}
 		}
 
 		{
+			MEMARENA_SCOPED_CHECKPOINT( &mem->persistent_arena );
+
+			u8 * normalmap_data = memarena_push_size( &mem->persistent_arena, 4096 * 4096 );
+			file_get_contents_and_decompress( "terrains/gta16.png.parts/normalmap.bc5.lz4", normalmap_data, 4096 * 4096 );
+
 			TextureConfig texture_config;
 			texture_config.width = 4096;
 			texture_config.height = 4096;
@@ -60,10 +95,15 @@ GAME_INIT( game_init ) {
 			texture_config.format = TEXFMT_BC5;
 			texture_config.wrap = TEXWRAP_BORDER;
 			texture_config.border_colour = v4( 0.5f );
-			normalmap = renderer_new_texture( texture_config );
+			clipmap.normalmap = renderer_new_texture( texture_config );
 		}
 
 		{
+			MEMARENA_SCOPED_CHECKPOINT( &mem->persistent_arena );
+
+			u8 * horizonmap_data = memarena_push_size( &mem->persistent_arena, 4096 * 4096 / 2 );
+			file_get_contents_and_decompress( "terrains/gta16.png.parts/horizonmap.bc4.lz4", horizonmap_data, 4096 * 4096 / 2 );
+
 			TextureConfig texture_config;
 			texture_config.width = 4096;
 			texture_config.height = 4096;
@@ -71,7 +111,7 @@ GAME_INIT( game_init ) {
 			texture_config.format = TEXFMT_BC4;
 			texture_config.wrap = TEXWRAP_BORDER;
 			texture_config.border_colour = v4( 0 );
-			horizonmap = renderer_new_texture( texture_config );
+			clipmap.horizonmap = renderer_new_texture( texture_config );
 		}
 	}
 
@@ -100,7 +140,7 @@ GAME_INIT( game_init ) {
 		mesh_config.positions = renderer_new_vb( vertices.ptr(), vertices.num_bytes() );
 		mesh_config.indices = renderer_new_ib( indices.ptr(), indices.num_bytes() );
 		mesh_config.num_vertices = indices.size();
-		patch = renderer_new_mesh( mesh_config );
+		clipmap.tile = renderer_new_mesh( mesh_config );
 	}
 
 	game->pos = v3( 0, 0, 100 );
@@ -137,7 +177,6 @@ GAME_FRAME( game_frame ) {
 	v3 up = normalize( cross( right, forward ) );
 
 	const float speed = 100.0f;
-	// const float speed = 1.0f;
 	game->pos += forward * dt * fb * speed;
 	game->pos += right * dt * lr * speed;
 	game->pos.z += dt * dz * speed;
@@ -176,17 +215,31 @@ GAME_FRAME( game_frame ) {
 				render_state.uniforms[ UNIFORMS_VIEW ] = view_uniforms;
 				render_state.uniforms[ UNIFORMS_SUN ] = sun_uniforms;
 				render_state.uniforms[ UNIFORMS_CLIPMAP ] = renderer_uniforms( offset, scale );
-				render_state.textures[ 0 ] = heightmap;
-				render_state.textures[ 1 ] = normalmap;
-				render_state.textures[ 2 ] = horizonmap;
+				render_state.textures[ 0 ] = clipmap.heightmap;
+				render_state.textures[ 1 ] = clipmap.normalmap;
+				render_state.textures[ 2 ] = clipmap.horizonmap;
 				render_state.textures[ 3 ] = renderer_blue_noise();
 				// render_state.wireframe = true;
-				renderer_draw_mesh( patch, render_state );
+				renderer_draw_mesh( clipmap.tile, render_state );
 			}
 		}
 	}
 
 	{
+		float t;
+		v3 normal;
+		if( ray_vs_quadtree( &clipmap.quadtree, Ray3( game->pos + v3( 2048, 2048, 0 ), forward ), &t, &normal ) ) {
+			v3 impact = game->pos + forward * t;
+			immediate_arrow( impact, v3( 0, 0, 1 ), 16, v4( 0, 1, 1, 1 ) );
+		}
+
+		RenderState impact_render_state;
+		impact_render_state.shader = get_shader( SHADER_FLAT_VERTEX_COLOURS );
+		impact_render_state.uniforms[ UNIFORMS_VIEW ] = view_uniforms;
+		immediate_render( impact_render_state );
+	}
+
+	{
 		const str< 128 > status( "Frame time: {.1}ms FPS: {.1}", dt * 1000.0f, 1.0f / dt );
 		draw_text( status.c_str(), 2, 2, 16.0f );
 		draw_text( str< 128 >( "pos = {.1}", game->pos ).c_str(), 2, 20, 16 );
diff --git a/main.cc b/main.cc
@@ -22,7 +22,7 @@ GameFrame game_frame;
 int main( int argc, char ** argv ) {
 	install_debug_signal_handlers( true );
 
-	size_t persistent_size = megabytes( 64 );
+	size_t persistent_size = megabytes( 150 );
 	u8 * persistent_memory = ( u8 * ) malloc( persistent_size );
 	if( persistent_memory == NULL ) {
 		FATAL( "couldn't allocate persistent memory" );
diff --git a/make.lua b/make.lua
@@ -46,7 +46,7 @@ bin( "bsp", { "main", "bsp", "bsp_renderer", game_objs }, { game_libs } )
 -- TODO: fix btt build
 -- bin( "btt", { "main", "mod_btt", "btt", "heightmap", "skybox", "lz4", game_objs }, { "stb_image", game_libs } )
 bin( "sm", { "main", "shadow_map", game_objs }, { game_libs } )
-bin( "clipmap", { "main", "clipmap", "skybox", game_objs }, { "lz4", game_libs } )
+bin( "clipmap", { "main", "clipmap", "heightmap", "skybox", game_objs }, { "lz4", "squish", game_libs } )
 
 msvc_bin_ldflags( "bsp", "opengl32.lib gdi32.lib" )
 gcc_bin_ldflags( "bsp", game_ldflags )
diff --git a/pp2.cc b/pp2.cc
@@ -4,6 +4,7 @@
 #include "linear_algebra.h"
 #include "dynstr.h"
 #include "int_conversions.h"
+#include "heightmap.h"
 #include "autogdb.h"
 
 #include "libs/squish/squish.h"
@@ -87,6 +88,53 @@ static void compute_normals( const array2d< u16 > heightmap, array2d< v3 > norma
 	}
 }
 
+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< HeightmapQuadTreeNode > & 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< HeightmapQuadTreeNode > & 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 );
 
@@ -136,17 +184,13 @@ int main( int argc, char ** argv ) {
 	ASSERT( png != NULL );
 
 	array2d< u16 > heightmap( png, w, h );
-	array2d< RGBA > heightmap_split = alloc_array2d< RGBA >( &arena, w, h );
-
-	array2d< v3 > normalmap_v3 = alloc_array2d< v3 >( &arena, w, h );
-	array2d< RGBA > normalmap = alloc_array2d< RGBA >( &arena, w, h );
-
-	array2d< float > horizonmap_float = alloc_array2d< float >( &arena, w, h );
-	array2d< RGBA > horizonmap = alloc_array2d< RGBA >( &arena, w, h );
 
 	{
 		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;
@@ -165,6 +209,9 @@ int main( int argc, char ** argv ) {
 		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++ ) {
@@ -184,6 +231,9 @@ int main( int argc, char ** argv ) {
 		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++ ) {
@@ -200,6 +250,27 @@ int main( int argc, char ** argv ) {
 		write_compressed_texture( &arena, horizonmap_path, horizonmap, squish::kBc4 );
 	}
 
+	{
+		MEMARENA_SCOPED_CHECKPOINT( &arena );
+		printf( "computing quadtree\n" );
+
+		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 ) = heightmap.try_get( x, y, 0 );
+			}
+		}
+
+		size_t num_nodes = quadtree_max_nodes( heightmap1.w, heightmap1.h );
+		array< HeightmapQuadTreeNode > nodes = alloc_array< HeightmapQuadTreeNode >( &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;