commit 12822ce7fc92ef98c7b29f55be35eae132b28e3e parent 5c84cb1cd2daa34d04ce52c62db7494ce1325786 Author: Michael Savage <mikejsavage@gmail.com> Date: Fri Dec 9 20:45:58 +0200 First attempt at terrain collision detection Diffstat:
| hm.cc | | | 64 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- |
| terrain_manager.cc | | | 158 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------ |
| terrain_manager.h | | | 6 | ++++++ |
diff --git a/hm.cc b/hm.cc @@ -6,6 +6,7 @@ #include "log.h" #include "heightmap.h" #include "terrain_manager.h" +#include "linear_algebra.h" #include "skybox.h" #include "work_queue.h" #include "text_renderer.h" @@ -60,6 +61,32 @@ static const char * textured_frag_src = GLSL( } ); +static const char * vert_outline_src = GLSL( + in vec3 position; + in vec3 colour; + + out vec3 frag_colour; + + layout( std140 ) uniform v_hot { + mat4 vp; + }; + + void main() { + frag_colour = colour; + gl_Position = vp * vec4( position, 1.0 ); + } +); + +static const char * frag_outline_src = GLSL( + in vec3 frag_colour; + + out vec4 screen_colour; + + void main() { + screen_colour = vec4( frag_colour, 1.0 ); + } +); + static v3 angles_to_vector( v3 angles ) { return v3( -sin( angles.y ) * sin( angles.x ), @@ -93,6 +120,9 @@ extern "C" GAME_INIT( game_init ) { game->test_shader = renderer_new_shader( vert_src, frag_src ); + game->test_outline_shader = renderer_new_shader( vert_outline_src, frag_outline_src ); + ub_sphere = renderer_new_ub(); + game->test_sun = 0.3f; const size_t triangles = 65536; @@ -170,14 +200,42 @@ extern "C" GAME_FRAME( game_frame ) { skybox_render( &game->skybox, game->angles, game->test_sun ); terrain_render( &game->tm, V, P, game->test_sun, current_time ); + // struct { m4 V; m4 P; } uniforms = { V, P }; + // renderer_ub_data( tree_uniforms, &uniforms, sizeof( uniforms ) ); + // + // RenderState trees_render_state = { }; + // trees_render_state.shader = tree_shader; + // trees_render_state.ubs[ UB_VS_HOT ] = tree_uniforms; + // trees_render_state.cull_face = CULLFACE_DISABLED; + // renderer_draw_mesh( tree_mesh, trees_render_state ); + RenderState immediate_render_state = { }; immediate_render_state.shader = game->test_shader; immediate_render_state.depth_func = DEPTHFUNC_DISABLED; immediate_render( &game->test_immediate, immediate_render_state ); - ImmediateContext imm; - ImmediateTriangle asdf[ 32 ]; - immediate_init( &imm, asdf, 32 ); + { + ImmediateContext imm; + ImmediateTriangle sphere[ 4096 ]; + immediate_init( &imm, sphere, ARRAY_COUNT( sphere ) ); + + float t; + v3 seg_end = game->pos + 1024.0f * angles_to_vector( game->angles ); + if( segment_vs_terrain( &game->tm, game->pos, seg_end, &t ) ) { + v3 impact = game->pos + angles_to_vector( game->angles ) * t; + immediate_arrow( &imm, impact, terrain_normal( &game->tm, impact ), 32, v4( 1, 0, 0, 1 ) ); + immediate_sphere( &imm, impact, 4, v4( 1, 0, 0, 1 ) ); + } + // else printf( "nope\n" ); + + m4 VP = V * P; + renderer_ub_data( ub_sphere, &VP, sizeof( VP ) ); + + RenderState impact_render_state = { }; + impact_render_state.shader = game->test_outline_shader; + impact_render_state.ubs[ UB_VS_HOT ] = ub_sphere; + immediate_render( &imm, impact_render_state ); + } { char buf[ 128 ]; diff --git a/terrain_manager.cc b/terrain_manager.cc @@ -120,44 +120,61 @@ static WORK_QUEUE_CALLBACK( async_load_tile ) { free( alt ); const CompressedTile & compressed_tile = tm->compressed_tiles[ tx ][ ty ]; - u32 width, height; + DecompressedTile & decompressed_tile = tm->decompressed_tiles[ tx ][ ty ]; size_t num_points = ( TILE_SIZE + 1 ) * ( TILE_SIZE + 1 ); - size_t decompressed_heightmap_size = num_points * sizeof( u8 ); - size_t decompressed_normalmap_size = num_points * sizeof( v3 ); - size_t decompressed_horizonmap_size = num_points * sizeof( float ); - // TODO: width/height might not be TILE_SIZE on the edges of the map - width = height = TILE_SIZE + 1; + // heightmap + size_t decompressed_heightmap_size = num_points * sizeof( u8 ); u8 * decompressed_heightmap = ( u8 * ) malloc( decompressed_heightmap_size ); - assert( decompressed_heightmap != NULL ); + ASSERT( decompressed_heightmap != NULL ); int ok_heightmap = LZ4_decompress_safe( ( const char * ) compressed_tile.heightmap_data, ( char * ) decompressed_heightmap, compressed_tile.heightmap_size, decompressed_heightmap_size ); - assert( ok_heightmap > 0 ); + ASSERT( ok_heightmap > 0 ); - u8 * decompressed_normalmap = ( u8 * ) malloc( decompressed_normalmap_size ); - assert( decompressed_normalmap != NULL ); + heightmap_init( &decompressed_tile.heightmap, decompressed_heightmap, TILE_SIZE + 1, TILE_SIZE + 1 ); + + // normalmap + size_t decompressed_normalmap_size = num_points * sizeof( v3 ); + v3 * decompressed_normalmap = ( v3 * ) malloc( decompressed_normalmap_size ); + ASSERT( decompressed_normalmap != NULL ); int ok_normalmap = LZ4_decompress_safe( ( const char * ) compressed_tile.normalmap_data, ( char * ) decompressed_normalmap, compressed_tile.normalmap_size, decompressed_normalmap_size ); - assert( ok_normalmap > 0 ); + ASSERT( ok_normalmap > 0 ); + + decompressed_tile.normalmap = decompressed_normalmap; + // horizonmap + size_t decompressed_horizonmap_size = num_points * sizeof( float ); float * decompressed_horizonmap = ( float * ) malloc( decompressed_horizonmap_size ); - assert( decompressed_horizonmap != NULL ); + ASSERT( decompressed_horizonmap != NULL ); int ok_horizonmap = LZ4_decompress_safe( ( const char * ) compressed_tile.horizonmap_data, ( char * ) decompressed_horizonmap, compressed_tile.horizonmap_size, decompressed_horizonmap_size ); - assert( ok_horizonmap > 0 ); - - DecompressedTile decompressed_tile; - heightmap_init( &decompressed_tile.heightmap, decompressed_heightmap, width, height ); - decompressed_tile.normalmap = ( v3 * ) decompressed_normalmap; - tm->decompressed_tiles[ tx ][ ty ] = decompressed_tile; - + ASSERT( ok_horizonmap > 0 ); + + // quadtree + size_t max_decompressed_quadtree_size = heightmap_quadtree_max_nodes( &decompressed_tile.heightmap ) * sizeof( HeightmapQuadTreeNode ); + HeightmapQuadTreeNode * decompressed_quadtree = ( HeightmapQuadTreeNode * ) malloc( max_decompressed_quadtree_size ); + ASSERT( decompressed_quadtree != NULL ); + int ok_quadtree = LZ4_decompress_safe( + ( const char * ) compressed_tile.quadtree_data, + ( char * ) decompressed_quadtree, + compressed_tile.quadtree_size, max_decompressed_quadtree_size ); + ASSERT( ok_quadtree > 0 ); + size_t decompressed_quadtree_size = checked_cast< size_t >( ok_quadtree ); + + decompressed_tile.quadtree.dim = TILE_SIZE; + decompressed_tile.quadtree.nodes_memory = decompressed_quadtree; + decompressed_tile.quadtree.nodes = array< HeightmapQuadTreeNode >( decompressed_quadtree, decompressed_quadtree_size / sizeof( HeightmapQuadTreeNode ) ); + decompressed_tile.quadtree.hm = &decompressed_tile.heightmap; + + // generate btt // TODO: should generate a triangle mesh here instead of in gpubtt_init MemoryArena btt_arena; void * btt_memory = malloc( megabytes( 16 ) ); @@ -171,6 +188,7 @@ static WORK_QUEUE_CALLBACK( async_load_tile ) { gpu_tile_data.horizonmap_size = decompressed_horizonmap_size; tm->gpu_tiles[ tx ][ ty ] = gpu_tile_data; + // mark as ready to upload store_release( &tm->tile_states[ tx ][ ty ], TILE_READY_FOR_UPLOAD ); } @@ -207,6 +225,7 @@ static void terrain_unload_tile( TerrainManager * tm, s32 tx, s32 ty ) { printf( "destroyed %d %d\n", tx, ty ); heightmap_destroy( &tm->decompressed_tiles[ tx ][ ty ].heightmap ); free( tm->decompressed_tiles[ tx ][ ty ].normalmap ); + free( tm->decompressed_tiles[ tx ][ ty ].quadtree.nodes_memory ); gpubtt_destroy( &tm->gpubtts[ tx ][ ty ] ); store_release( &tm->tile_states[ tx ][ ty ], TILE_EMPTY ); @@ -233,14 +252,17 @@ void terrain_init( str< 512 > heightmap_path( "%s/%d_%d_heightmap.lz4", tiles_dir, tx, ty ); str< 512 > normalmap_path( "%s/%d_%d_normals.lz4", tiles_dir, tx, ty ); str< 512 > horizonmap_path( "%s/%d_%d_horizons.lz4", tiles_dir, tx, ty ); + str< 512 > quadtree_path( "%s/%d_%d_quadtree.lz4", tiles_dir, tx, ty ); - size_t heightmap_size, normalmap_size, horizonmap_size; + size_t heightmap_size, normalmap_size, horizonmap_size, quadtree_size; u8 * heightmap = file_get_contents( heightmap_path.c_str(), &heightmap_size ); u8 * normalmap = file_get_contents( normalmap_path.c_str(), &normalmap_size ); u8 * horizonmap = file_get_contents( horizonmap_path.c_str(), &horizonmap_size ); + u8 * quadtree = file_get_contents( + quadtree_path.c_str(), &quadtree_size ); CompressedTile & compressed_tile = tm->compressed_tiles[ tx ][ ty ]; compressed_tile.heightmap_data = heightmap; @@ -249,6 +271,8 @@ void terrain_init( compressed_tile.normalmap_size = normalmap_size; compressed_tile.horizonmap_data = horizonmap; compressed_tile.horizonmap_size = horizonmap_size; + compressed_tile.quadtree_data = quadtree; + compressed_tile.quadtree_size = quadtree_size; store_release( &tm->tile_states[ tx ][ ty ], TILE_EMPTY ); } @@ -405,7 +429,7 @@ void terrain_render( TerrainManager * tm, const m4 & V, const m4 & P, float sun, &tm->gpubtts[ tx ][ ty ], gpu_tile_data.btt, &ohm, - ( v3 * ) tm->decompressed_tiles[ tx ][ ty ].normalmap, + tm->decompressed_tiles[ tx ][ ty ].normalmap, gpu_tile_data.horizonmap ); free( gpu_tile_data.btt_memory ); @@ -473,8 +497,96 @@ float terrain_height( const TerrainManager * tm, v3 position ) { s32 tx = position.x / TILE_SIZE; s32 ty = position.y / TILE_SIZE; + TileState tile_state = checked_cast< TileState >( load_acquire( &tm->tile_states[ tx ][ ty ] ) ); + if( tile_state != TILE_READY_FOR_UPLOAD && tile_state != TILE_ON_GPU ) { + return 0.0f; + } + const Heightmap * hm = &tm->decompressed_tiles[ tx ][ ty ].heightmap; - return hm->bilerp_height( position.x - tx * TILE_SIZE, - position.y - ty * TILE_SIZE ); + return hm->bilerp_height( position.x - tx * TILE_SIZE, position.y - ty * TILE_SIZE ); +} + +template< typename T > +static T lerp( T a, float t, T b ) { + ASSERT( t >= 0.0f && t <= 1.0f ); + return a * ( 1.0f - t ) + b * t; +} + +template< typename T > +static T bilerp( const array2d< T > arr, float x, float y ) { + size_t xi = ( size_t ) x; + size_t yi = ( size_t ) y; + size_t xi1 = min( xi + 1, arr.w - 1 ); + size_t yi1 = min( yi + 1, arr.h - 1 ); + + float xf = x - xi; + float yf = y - yi; + + T a = arr( xi, yi ); + T b = arr( xi1, yi ); + T c = arr( xi, yi1 ); + T d = arr( xi1, yi1 ); + + T ab = lerp( a, xf, b ); + T cd = lerp( c, xf, d ); + + return lerp( ab, yf, cd ); +} + +v3 terrain_normal( const TerrainManager * tm, v3 position ) { + assert( position.x >= 0 ); + assert( position.y >= 0 ); + assert( position.x < tm->width ); + assert( position.y < tm->height ); + + s32 tx = position.x / TILE_SIZE; + s32 ty = position.y / TILE_SIZE; + + TileState tile_state = checked_cast< TileState >( load_acquire( &tm->tile_states[ tx ][ ty ] ) ); + if( tile_state != TILE_READY_FOR_UPLOAD && tile_state != TILE_ON_GPU ) { + return v3( 0, 0, 1 ); + } + + const array2d< v3 > normalmap( tm->decompressed_tiles[ tx ][ ty ].normalmap, TILE_SIZE, TILE_SIZE ); + + float local_x = position.x - tx * TILE_SIZE; + float local_y = position.y - ty * TILE_SIZE; + + // TODO: the values we read from normalmap are totally hosed + return normalize( bilerp( normalmap, local_x, local_y ) ); +} + +bool segment_vs_terrain( const TerrainManager * tm, v3 seg_origin, v3 seg_end, float * t ) { + v3 ray_direction = normalize( seg_end - seg_origin ); + bool hit = false; + + // TODO: bresenhams vs top level + for( u16 vy = 0; vy < VIEW_SIZE; vy++ ) { + for( u16 vx = 0; vx < VIEW_SIZE; vx++ ) { + s32 tx = vx + tm->tile_x - VIEW_HALF; + s32 ty = vy + tm->tile_y - VIEW_HALF; + + if( tx < 0 || ty < 0 ) continue; + + TileState tile_state = checked_cast< TileState >( load_acquire( &tm->tile_states[ tx ][ ty ] ) ); + if( tile_state != TILE_READY_FOR_UPLOAD && tile_state != TILE_ON_GPU ) { + continue; + } + + v3 local_seg_origin = seg_origin - v3( tx * TILE_SIZE, ty * TILE_SIZE, 0 ); + + const HeightmapQuadTree * qt = &tm->decompressed_tiles[ tx ][ ty ].quadtree; + // TODO: convert from tile t to global t + float tile_t; + bool tile_hit = ray_vs_quadtree( qt, local_seg_origin, ray_direction, &tile_t ); + + if( tile_hit && ( !hit || tile_t < *t ) ) { + hit = true; + *t = tile_t; + } + } + } + + return hit; } diff --git a/terrain_manager.h b/terrain_manager.h @@ -23,6 +23,8 @@ struct CompressedTile { size_t normalmap_size; u8 * horizonmap_data; size_t horizonmap_size; + u8 * quadtree_data; + size_t quadtree_size; }; struct GPUTileData { @@ -36,6 +38,7 @@ struct DecompressedTile { // TODO: merge this + Heightmap Heightmap heightmap; v3 * normalmap; + HeightmapQuadTree quadtree; }; enum TileState { @@ -81,5 +84,8 @@ void terrain_teleport( TerrainManager * tm, v3 position ); void terrain_update( TerrainManager * tm, v3 position ); void terrain_render( TerrainManager * tm, const m4 & V, const m4 & P, float sun, double current_time ); float terrain_height( const TerrainManager * tm, v3 position ); +v3 terrain_normal( const TerrainManager * tm, v3 position ); + +bool segment_vs_terrain( const TerrainManager * tm, v3 seg_origin, v3 seg_end, float * t ); #endif // _TERRAIN_MANAGER_H_