commit 92cf31f6074489e95b744d846ed6c1aad23f517c parent 594403903485f440f73d0fb6c7c3ec07031af288 Author: Michael Savage <mikejsavage@gmail.com> Date: Sun Nov 13 11:29:54 +0200 Ray-quadtree intersection prototype Diffstat:
| heightmap.cc | | | 298 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| heightmap.h | | | 61 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| mod_btt.cc | | | 55 | +++++++++++++++++++++++++++++++++++++++++++++++++++---- |
diff --git a/heightmap.cc b/heightmap.cc @@ -45,6 +45,12 @@ glm::vec3 Heightmap::point( u32 x, u32 y ) const { return glm::vec3( x, y, pixels[ y * width + x ] ); } +float heightmap_height( const Heightmap * hm, u32 x, u32 y ) { + ASSERT( x < hm->width ); + ASSERT( y < hm->height ); + return hm->pixels[ y * hm->width + x ]; +} + float Heightmap::bilerp_height( float x, float y ) const { const float ix = floorf( x ); const float iy = floorf( y ); @@ -57,3 +63,295 @@ float Heightmap::bilerp_height( float x, float y ) const { glm::vec2( x, y ) ); } + +// +// +// +// +// +// + +template< typename T > +T max( T a, T b, T c, T d ) { + return max( max( max( a, b ), c ), d ); +} + +template< typename T > +T min( T a, T b, T c, T d ) { + return min( min( min( a, b ), c ), d ); +} + +HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm ) { + assert( is_power_of_2( hm->width - 1 ) && hm->width == hm->height ); + + size_t num_nodes = 2 * ( hm->width - 1 ) * ( hm->width - 1 ); + + HeightmapQuadTree qt; + qt.hm = hm; + qt.dim = hm->width - 1; + HeightmapQuadTreeNode * nodes = ( HeightmapQuadTreeNode * ) malloc( num_nodes * sizeof( HeightmapQuadTreeNode ) ); + + // fill in the 1x1 level + size_t last = 0; + size_t curr = 0; + for( size_t y = 0; y < qt.dim; y++ ) { + for( size_t x = 0; x < qt.dim; x++ ) { + HeightmapQuadTreeNode * node = &nodes[ y * qt.dim + x ]; + float a = heightmap_height( hm, x, y ); + float b = heightmap_height( hm, x + 1, y ); + float c = heightmap_height( hm, x, y + 1 ); + float d = heightmap_height( hm, x + 1, y + 1 ); + node->min_z = min( a, b, c, d ); + node->max_z = max( a, b, c, d ); + node->children[ 0 ] = node->children[ 1 ] = node->children[ 2 ] = node->children[ 3 ] = NULL; + curr++; + } + } + + size_t dim = qt.dim / 2; + while( dim > 0 ) { + for( size_t y = 0; y < dim; y++ ) { + for( size_t x = 0; x < dim; x++ ) { + HeightmapQuadTreeNode * node = &nodes[ curr + y * dim + x ]; + node->children[ 0 ] = &nodes[ last + ( y * 2 ) * dim * 2 + ( x * 2 ) ]; + node->children[ 1 ] = &nodes[ last + ( y * 2 ) * dim * 2 + ( x * 2 + 1 ) ]; + node->children[ 2 ] = &nodes[ last + ( y * 2 + 1 ) * dim * 2 + ( x * 2 ) ]; + node->children[ 3 ] = &nodes[ last + ( y * 2 + 1 ) * dim * 2 + ( x * 2 + 1 ) ]; + + node->min_z = min( node->children[ 0 ]->min_z, node->children[ 1 ]->min_z, node->children[ 2 ]->min_z, node->children[ 3 ]->min_z ); + node->max_z = max( node->children[ 0 ]->max_z, node->children[ 1 ]->max_z, node->children[ 2 ]->max_z, node->children[ 3 ]->max_z ); + } + } + last = curr; + curr += dim * dim; + dim /= 2; + } + + qt.root = &nodes[ last ]; + + return qt; +} + +// TODO: aabb_from_corners, rearrange to be min/max +AABB aabb_from_mins_maxs( v3 mins, v3 maxs ) { + assert( mins.x <= maxs.x ); + assert( mins.y <= maxs.y ); + assert( mins.z <= maxs.z ); + return AABB( ( maxs + mins ) / 2, ( maxs - mins ) / 2 ); +} + +bool ray_vs_aabb( AABB aabb, v3 start, v3 dir, float * t ) { + if( aabb.contains( start ) ) { + *t = 0.0f; + return true; + } + v3 inv_dir = v3( 1.0f / dir.x, 1.0f / dir.y, 1.0f / dir.z ); + + float tx1 = (aabb.mins().x - start.x)*inv_dir.x; + float tx2 = (aabb.maxs().x - start.x)*inv_dir.x; + + float tmin = min(tx1, tx2); + float tmax = max(tx1, tx2); + + float ty1 = (aabb.mins().y - start.y)*inv_dir.y; + float ty2 = (aabb.maxs().y - start.y)*inv_dir.y; + + tmin = max(tmin, min(ty1, ty2)); + tmax = min(tmax, max(ty1, ty2)); + + float tz1 = (aabb.mins().z - start.z)*inv_dir.z; + float tz2 = (aabb.maxs().z - start.z)*inv_dir.z; + + tmin = max(tmin, min(tz1, tz2)); + tmax = min(tmax, max(tz1, tz2)); + + if( tmax >= tmin ) { + *t = tmin; + } + return tmax >= tmin; +} + +bool ray_vs_sphere( v3 ray_origin, v3 ray_dir, v3 sphere_origin, float sphere_radius, float * t ) { + v3 m = ray_origin - sphere_origin; + + float b = dot( m, ray_dir ); + float c = dot( m, m ) - sphere_radius * sphere_radius; + + float determinant = b * b - c; + if( determinant < 0 ) { + return false; + } + + *t = -b - sqrtf( determinant ); + return *t >= 0; +} + +bool ray_vs_plane( v3 ray_origin, v3 ray_dir, v3 plane_normal, float plane_distance, float * t ) { + const float epsilon = 0.001f; + float denom = dot( ray_dir, plane_normal ); + if( fabsf( denom ) < epsilon ) { + return false; + } + + *t = ( plane_distance - dot( ray_origin, plane_normal ) ) / denom; + return *t >= 0; +} + +void barycentric( v3 a, v3 b, v3 c, v3 p, float * u, float * v, float * w ) { + v3 ab = b - a; + v3 ac = c - a; + v3 ap = p - a; + + float dabab = dot( ab, ab ); + float dabac = dot( ab, ac ); + float dacac = dot( ac, ac ); + float dapab = dot( ap, ab ); + float dapac = dot( ap, ac ); + float denom = dabab * dacac - dabac * dabac; + + *v = ( dacac * dapab - dabac * dapac ) / denom; + *w = ( dabab * dapac - dabac * dapab ) / denom; + *u = 1.0f - *v - *w; +} + +bool point_in_triangle( v3 p, v3 a, v3 b, v3 c ) { + float u, v, w; + barycentric( a, b, c, p, &u, &v, &w ); + + const float epsilon = 0.0001f; + if( u < -epsilon || u > 1.0f + epsilon ) return false; + if( v < -epsilon || v > 1.0f + epsilon ) return false; + if( w < -epsilon || w > 1.0f + epsilon ) return false; + + return true; +} + +// TODO: not robust w/ thin triangles +v3 triangle_normal( v3 a, v3 b, v3 c ) { + return normalize( cross( b - a, c - a ) ); +} + +bool ray_vs_triangle( v3 ray_origin, v3 ray_dir, v3 p0, v3 p1, v3 p2, float * t ) { + v3 plane_normal = triangle_normal( p0, p1, p2 ); + float plane_dist = dot( p0, plane_normal ); + + if( !ray_vs_plane( ray_origin, ray_dir, plane_normal, plane_dist, t ) ) { + return false; + } + + v3 xpoint = ray_origin + ray_dir * *t; + return point_in_triangle( xpoint, p0, p1, p2 ); +} + +AABB AABB::quadrant( int q ) { + // NW + if( q == 0 ) { + return aabb_from_mins_maxs( mins(), center + v3( 0, 0, extents.z ) ); + } + + // NE + if( q == 1 ) { + return aabb_from_mins_maxs( center - v3( 0, extents.y, extents.z ), center + v3( extents.x, 0, extents.z ) ); + } + + // SW + if( q == 2 ) { + return aabb_from_mins_maxs( center - v3( extents.x, 0, extents.z ), center + v3( 0, extents.y, extents.z ) ); + } + + // SE + assert( q == 3 ); + return aabb_from_mins_maxs( center - v3( 0, 0, extents.z ), maxs() ); +} + +AABB AABB::clamp_z( float lo, float hi ) { + v3 new_mins = mins(); + new_mins.z = max( new_mins.z, lo ); + v3 new_maxs = maxs(); + new_maxs.z = min( new_maxs.z, hi ); + return aabb_from_mins_maxs( new_mins, new_maxs ); +} + +static bool ray_vs_quadtree_node( const Heightmap * hm, const HeightmapQuadTreeNode * node, AABB aabb, v3 origin, v3 direction, float * t, float lol ) { + if( node->children[ 0 ] == NULL ) { + float min_t; + bool hit = false; + // TODO: super bad + for( u32 x = aabb.mins().x + 0.1f; x < aabb.maxs().x + 0.1f; x++ ) { + for( u32 y = aabb.mins().y + 0.1f; y < aabb.maxs().y + 0.1f; y++ ) { + v3 p0 = GLMV3( hm->point( x, y ) ); + v3 p1 = GLMV3( hm->point( x + 1, y ) ); + v3 p2 = GLMV3( hm->point( x, y + 1 ) ); + v3 p3 = GLMV3( hm->point( x + 1, y + 1 ) ); + + // bottom right triangle + float t0; + bool hit0 = ray_vs_triangle( origin, direction, p0, p1, p3, &t0 ); + if( hit0 ) { + if( !hit || t0 < min_t ) { + min_t = t0; + hit = true; + } + } + + // top left triangle + float t1; + bool hit1 = ray_vs_triangle( origin, direction, p0, p3, p2, &t1 ); + if( hit1 ) { + if( !hit || t1 < min_t ) { + min_t = t1; + hit = true; + } + } + } + } + + if( hit ) { + *t = min_t; + return true; + } + + return false; + } + + AABB aabbs[ 4 ]; + float ts[ 4 ]; + int hit_mask = 0; + for( int i = 0; i < 4; i++ ) { + aabbs[ i ] = aabb.quadrant( i ).clamp_z( node->children[ i ]->min_z, node->children[ i ]->max_z ); + hit_mask |= int( ray_vs_aabb( aabbs[ i ], origin, direction, &ts[ i ] ) ) << i; + } + + int visited_mask = 0; + for( int i = 0; i < 4; i++ ) { + if( visited_mask == hit_mask ) { + return false; + } + + int lowest = 0; + for( int j = 0; j < 4; j++ ) { + if( ( hit_mask & ( 1 << j ) ) == 0 ) continue; + if( ( visited_mask & ( 1 << j ) ) != 0 ) continue; + if( ts[ j ] < ts[ lowest ] || ( hit_mask & ( 1 << lowest ) ) == 0 || ( visited_mask & ( 1 << lowest ) ) != 0 ) { + lowest = j; + } + } + + if( ray_vs_quadtree_node( hm, node->children[ lowest ], aabbs[ lowest ], origin, direction, t, ts[ lowest ] ) ) { + return true; + } + + visited_mask |= 1 << lowest; + } + + return false; +} + +bool ray_vs_quadtree( const HeightmapQuadTree * qt, v3 origin, v3 direction, float * t ) { + v3 mins = v3( 0, 0, qt->root->min_z ); + v3 maxs = v3( qt->dim, qt->dim, qt->root->max_z ); + + AABB aabb = aabb_from_mins_maxs( mins, maxs ); + + return ray_vs_quadtree_node( qt->hm, qt->root, aabb, origin, direction, t, 1337 ); +} diff --git a/heightmap.h b/heightmap.h @@ -5,6 +5,7 @@ #include "intrinsics.h" #include "memory_arena.h" +#include "linear_algebra.h" class Heightmap { public: @@ -24,5 +25,65 @@ struct OffsetHeightmap { void heightmap_init( Heightmap * hm, u8 * pixels, u32 width, u32 height ); void heightmap_destroy( Heightmap * hm ); +struct HeightmapQuadTreeNode { + float min_z, max_z; + HeightmapQuadTreeNode * children[ 4 ]; +}; + +struct HeightmapQuadTree { + u32 dim; + HeightmapQuadTreeNode * root; + const Heightmap * hm; +}; + +HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm ); + +// TODO: these are all pretty general +// struct Intersection { +// float t; +// glm::vec3 position; +// glm::vec3 normal; +// }; + +// template< typename T > +// bool open_interval_contains( T lo, T x, T hi ) { +// return ( x - lo ) < ( hi - lo ); +// } +// +// template< typename T > +// bool closed_interval_contains( T lo, T x, T hi ) { +// return ( x - lo ) <= ( hi - lo ); +// } +// +// template< typename T > +// bool closed_intervals_overlap( T lo0, T hi0, T lo1, T hi1 ) { +// return lo0 <= hi1 && lo1 <= hi0; +// } + +struct AABB { + v3 center, extents; + + AABB() { } + + explicit AABB( v3 c, v3 e ) { + assert( e.x >= 0 && e.y >= 0 && e.z >= 0 ); + + center = c; + extents = e; + } + + v3 mins() const { return center - extents; } + v3 maxs() const { return center + extents; } + AABB quadrant( int q ); + AABB clamp_z( float lo, float hi ); + + bool contains( v3 p ) { + return p.x >= mins().x && p.y >= mins().y && p.z >= mins().z && + p.x <= maxs().x && p.y <= maxs().y && p.z <= maxs().z; + } +}; + +bool ray_vs_quadtree( const HeightmapQuadTree * qt, v3 origin, v3 direction, float * t ); +AABB aabb_from_mins_maxs( v3 mins, v3 maxs ); #endif // _HEIGHTMAP_H_ diff --git a/mod_btt.cc b/mod_btt.cc @@ -11,7 +11,9 @@ #include "linear_algebra.h" #include "lz4.h" -static ImmediateTriangle triangles[ 512000 ]; +#define TERRAIN_NAME "grad.png" + +static ImmediateTriangle triangles[ megabytes( 16 ) ]; static ImmediateContext imm; static const char * vert_src = GLSL( @@ -99,6 +101,14 @@ static glm::vec3 angles_to_vector_xy( const glm::vec3 & angles ) { return glm::vec3( sin( angles.y ), cos( angles.y ), 0 ); } +glm::vec3 angles_to_vector( const glm::vec3 & angles ) { + return glm::vec3( + -sin( angles.y ) * sin( angles.x ), + -cos( angles.y ) * sin( angles.x ), + -cos( angles.x ) + ); +} + // static void draw_btt( // const BTT * btt, const Heightmap * hm, // ImmediateContext * imm, @@ -125,6 +135,7 @@ static glm::vec3 angles_to_vector_xy( const glm::vec3 & angles ) { // } static float * horizons; +static HeightmapQuadTree qt; static UB ub_fs, ub_vs; @@ -150,15 +161,16 @@ extern "C" GAME_INIT( game_init ) { ub_fs = renderer_new_ub(); int w, h; - u8 * pixels = stbi_load( "terrains/mountains512.png", &w, &h, NULL, 1 ); + u8 * pixels = stbi_load( "terrains/" TERRAIN_NAME, &w, &h, NULL, 1 ); heightmap_init( &game->hm, pixels, w, h ); + qt = heightmap_build_quadtree( &game->hm ); size_t horizons_size = ( w + 1 ) * ( h + 1 ) * sizeof( float ); horizons = ( float * ) malloc( horizons_size ); assert( horizons != NULL ); size_t compressed_horizons_size; - u8 * compressed_horizons = file_get_contents( "terrains/mountains512.png.parts/0_0_horizons.lz4", &compressed_horizons_size ); + u8 * compressed_horizons = file_get_contents( "terrains/" TERRAIN_NAME ".parts/0_0_horizons.lz4", &compressed_horizons_size ); int ok_horizons = LZ4_decompress_safe( ( const char * ) compressed_horizons, ( char * ) horizons, @@ -170,7 +182,7 @@ extern "C" GAME_INIT( game_init ) { assert( normals != NULL ); size_t compressed_normals_size; - u8 * compressed_normals = file_get_contents( "terrains/mountains512.png.parts/0_0_normals.lz4", &compressed_normals_size ); + u8 * compressed_normals = file_get_contents( "terrains/" TERRAIN_NAME ".parts/0_0_normals.lz4", &compressed_normals_size ); int ok_normals = LZ4_decompress_safe( ( const char * ) compressed_normals, ( char * ) normals, @@ -198,9 +210,27 @@ struct FSData { float sun; }; +static void draw_qt( ImmediateContext * imm, AABB aabb, const HeightmapQuadTreeNode * node ) { + if( aabb.maxs().x - aabb.mins().x >= 31 ) { + glm::vec3 mins( aabb.mins().x, aabb.mins().y, aabb.mins().z ); + glm::vec3 maxs( aabb.maxs().x, aabb.maxs().y, aabb.maxs().z ); + immediate_aabb( imm, mins, maxs, glm::vec4( 0, 0, 1, 1 ) ); + } + else return; + + if( node->children[ 0 ] == NULL ) return; + + for( size_t i = 0; i < 4; i++ ) { + draw_qt( imm, aabb.quadrant( i ).clamp_z( node->children[ i ]->min_z, node->children[ i ]->max_z ), node->children[ i ] ); + } +} + +bool break_on_next = false; extern "C" GAME_FRAME( game_frame ) { glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT ); + if( input->keys[ 't' ] ) break_on_next = true; + const int fb = input->keys[ 'w' ] - input->keys[ 's' ]; const int lr = input->keys[ 'a' ] - input->keys[ 'd' ]; const int dz = input->keys[ KEY_SPACE ] - input->keys[ KEY_LEFTSHIFT ]; @@ -246,7 +276,24 @@ extern "C" GAME_FRAME( game_frame ) { } glUseProgram( game->test_outline_shader ); glUniformMatrix4fv( game->test_outline_un_vp, 1, GL_FALSE, ( float * ) &VP ); + + float t; + if( break_on_next ) asm( "int $3" ); + if( ray_vs_quadtree( &qt, GLMV3( game->pos ), GLMV3( angles_to_vector( game->angles ) ), &t ) ) { + glm::vec3 impact = game->pos + angles_to_vector( game->angles ) * t; + printf( "impact (%f) %f %f %f\n", t, impact.x, impact.y, impact.z ); + immediate_sphere( &imm, impact, 4, glm::vec4( 1, 0, 0, 1 ) ); + } + else printf( "nope\n" ); + immediate_render( &imm, game->test_outline_at_position, game->test_outline_at_colour ); + + immediate_init( &imm, triangles, array_count( triangles ) ); + v3 mins = v3( 0, 0, qt.root->min_z ); + v3 maxs = v3( qt.dim, qt.dim, qt.root->max_z ); + draw_qt( &imm, aabb_from_mins_maxs( mins, maxs ), qt.root ); + glPolygonMode( GL_FRONT_AND_BACK, GL_LINE ); immediate_render( &imm, game->test_outline_at_position, game->test_outline_at_colour ); + glPolygonMode( GL_FRONT_AND_BACK, GL_FILL ); glUseProgram( 0 ); // immediate_init( &imm, triangles, array_count( triangles ) );