commit f8bea513b8756edcaaea63d1c9832d6dc2f9a673 parent a0967cba2c1faa6714988b08369e59268aaee023 Author: Michael Savage <mikejsavage@gmail.com> Date: Sun Nov 13 17:51:56 +0200 Faster/simpler quadtree code, accept non-power-of-2 heightmaps Diffstat:
| heightmap.cc | | | 282 | ++++++++++++++++++++++++++++++++++++++++++------------------------------------- |
| heightmap.h | | | 86 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------- |
| mod_btt.cc | | | 23 | +++++++++++++---------- |
diff --git a/heightmap.cc b/heightmap.cc @@ -4,6 +4,7 @@ #include "intrinsics.h" #include "heightmap.h" +#include "log.h" #include "memory_arena.h" const float SLOPE = 0.3; @@ -45,7 +46,7 @@ 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 ) { +u8 heightmap_height( const Heightmap * hm, u32 x, u32 y ) { ASSERT( x < hm->width ); ASSERT( y < hm->height ); return hm->pixels[ y * hm->width + x ]; @@ -81,94 +82,37 @@ 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 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 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; + 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)); + 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; + 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)); + tmin = max( tmin, min( tz1, tz2 ) ); + tmax = min( tmax, max( tz1, tz2 ) ); if( tmax >= tmin ) { *t = tmin; + return true; } - return tmax >= tmin; + return false; } bool ray_vs_sphere( v3 ray_origin, v3 ray_dir, v3 sphere_origin, float sphere_radius, float * t ) { @@ -243,66 +187,139 @@ bool ray_vs_triangle( v3 ray_origin, v3 ray_dir, v3 p0, v3 p1, v3 p2, float * 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 ) ); +u32 mean( u32 a, u32 b ) { + return a / 2 + b / 2 + ( a & b & 1 ); +} + +v3u32 mean( v3u32 mins, v3u32 maxs ) { + ASSERT( mins.x <= maxs.x ); + ASSERT( mins.y <= maxs.y ); + ASSERT( mins.z <= maxs.z ); + return mins + ( maxs - mins ) / 2; +} + +AABBu32 AABBu32::quadrant( int q ) const { + switch( checked_cast< Quadrant >( q ) ) { + case QUADRANT_SW: { + v3u32 mx = maxs; + mx.x = mean( mins.x, maxs.x ); + mx.y = mean( mins.y, maxs.y ); + return AABBu32( mins, mx ); + } + + case QUADRANT_SE: { + v3u32 mn = mins; + v3u32 mx = maxs; + mn.x = mean( mins.x, maxs.x ); + mx.y = mean( mins.y, maxs.y ); + return AABBu32( mn, mx ); + } + + case QUADRANT_NW: { + v3u32 mn = mins; + v3u32 mx = maxs; + mn.y = mean( mins.y, maxs.y ); + mx.x = mean( mins.x, maxs.x ); + return AABBu32( mn, mx ); + } + + case QUADRANT_NE: { + v3u32 mn = mins; + mn.x = mean( mins.x, maxs.x ); + mn.y = mean( mins.y, maxs.y ); + return AABBu32( mn, maxs ); + } } - // NE - if( q == 1 ) { - return aabb_from_mins_maxs( center - v3( 0, extents.y, extents.z ), center + v3( extents.x, 0, extents.z ) ); + FATAL( "bad quadrant" ); + return AABBu32(); +} + +AABBu32 AABBu32::clamp_z( u32 lo, u32 hi ) { + v3u32 mn = mins; + v3u32 mx = maxs; + mn.z = max( mn.z, lo ); + mx.z = min( mx.z, hi ); + return AABBu32( mn, mx ); +} + +static size_t child_idx( size_t node_idx, size_t quadrant ) { + return node_idx * 4 + quadrant + 1; +} + +static void heightmap_build_quadtree_node( HeightmapQuadTree * qt, size_t node_idx, AABBu32 aabb ) { + if( aabb.maxs.x - aabb.mins.x == 1 || aabb.maxs.y - aabb.mins.y == 1 ) { + u32 x = aabb.mins.x; + u32 y = aabb.mins.y; + u8 a = heightmap_height( qt->hm, x, y ); + u8 b = heightmap_height( qt->hm, x + 1, y ); + u8 c = heightmap_height( qt->hm, x, y + 1 ); + u8 d = heightmap_height( qt->hm, x + 1, y + 1 ); + qt->nodes[ node_idx ].min_z = min( a, b, c, d ); + qt->nodes[ node_idx ].max_z = max( a, b, c, d ); + + return; } - // SW - if( q == 2 ) { - return aabb_from_mins_maxs( center - v3( extents.x, 0, extents.z ), center + v3( 0, extents.y, extents.z ) ); + u8 lo = 255; + u8 hi = 0; + for( size_t i = 0; i < 4; i++ ) { + AABBu32 asdf = aabb.quadrant( i ); + heightmap_build_quadtree_node( qt, child_idx( node_idx, i ), aabb.quadrant( i ) ); + lo = min( lo, qt->nodes[ child_idx( node_idx, i ) ].min_z ); + hi = max( hi, qt->nodes[ child_idx( node_idx, i ) ].max_z ); } - // SE - assert( q == 3 ); - return aabb_from_mins_maxs( center - v3( 0, 0, extents.z ), maxs() ); + qt->nodes[ node_idx ].min_z = lo; + qt->nodes[ node_idx ].max_z = hi; } -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 ); +HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm ) { + // convervative upper bound + size_t num_nodes = 2 * ( hm->width - 1 ) * ( hm->width - 1 ); + + HeightmapQuadTree qt; + qt.hm = hm; + qt.dim = hm->width - 1; + qt.nodes_memory = ( HeightmapQuadTreeNode * ) malloc( num_nodes * sizeof( HeightmapQuadTreeNode ) ); + qt.nodes = array< HeightmapQuadTreeNode >( qt.nodes_memory, num_nodes ); + + AABBu32 aabb( v3u32( 0, 0, 0 ), v3u32( qt.dim, qt.dim, 255 ) ); + heightmap_build_quadtree_node( &qt, 0, aabb ); + + return qt; } -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 ) { +static bool ray_vs_quadtree_node( const HeightmapQuadTree * qt, size_t node_idx, AABBu32 aabb, v3 origin, v3 direction, float * t ) { + if( aabb.maxs.x - aabb.mins.x == 1 || aabb.maxs.y - aabb.mins.y == 1 ) { 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; - } - } + + u32 x = aabb.mins.x; + u32 y = aabb.mins.y; + + v3 p0 = GLMV3( qt->hm->point( x, y ) ); + v3 p1 = GLMV3( qt->hm->point( x + 1, y ) ); + v3 p2 = GLMV3( qt->hm->point( x, y + 1 ) ); + v3 p3 = GLMV3( qt->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; } } @@ -314,21 +331,21 @@ static bool ray_vs_quadtree_node( const Heightmap * hm, const HeightmapQuadTreeN return false; } - AABB aabbs[ 4 ]; + AABBu32 aabbs[ 4 ]; float ts[ 4 ]; - int hit_mask = 0; + u32 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; + aabbs[ i ] = aabb.quadrant( i ).clamp_z( qt->nodes[ child_idx( node_idx, i ) ].min_z, qt->nodes[ child_idx( node_idx, i ) ].max_z ); + hit_mask |= u32( ray_vs_aabb( AABB( aabbs[ i ] ), origin, direction, &ts[ i ] ) ) << i; } - int visited_mask = 0; + u32 visited_mask = 0; for( int i = 0; i < 4; i++ ) { if( visited_mask == hit_mask ) { return false; } - int lowest = 0; + u32 lowest = 0; for( int j = 0; j < 4; j++ ) { if( ( hit_mask & ( 1 << j ) ) == 0 ) continue; if( ( visited_mask & ( 1 << j ) ) != 0 ) continue; @@ -337,7 +354,7 @@ static bool ray_vs_quadtree_node( const Heightmap * hm, const HeightmapQuadTreeN } } - if( ray_vs_quadtree_node( hm, node->children[ lowest ], aabbs[ lowest ], origin, direction, t, ts[ lowest ] ) ) { + if( ray_vs_quadtree_node( qt, child_idx( node_idx, lowest ), aabbs[ lowest ], origin, direction, t ) ) { return true; } @@ -348,10 +365,9 @@ static bool ray_vs_quadtree_node( const Heightmap * hm, const HeightmapQuadTreeN } 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 ); + v3u32 mins = v3u32( 0, 0, qt->nodes[ 0 ].min_z ); + v3u32 maxs = v3u32( qt->dim, qt->dim, qt->nodes[ 0 ].max_z ); + AABBu32 aabb( mins, maxs ); - return ray_vs_quadtree_node( qt->hm, qt->root, aabb, origin, direction, t, 1337 ); + return ray_vs_quadtree_node( qt, 0, aabb, origin, direction, t ); } diff --git a/heightmap.h b/heightmap.h @@ -26,13 +26,13 @@ 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 ]; + u8 min_z, max_z; }; struct HeightmapQuadTree { u32 dim; - HeightmapQuadTreeNode * root; + HeightmapQuadTreeNode * nodes_memory; + array< HeightmapQuadTreeNode > nodes; const Heightmap * hm; }; @@ -60,30 +60,84 @@ HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm ); // return lo0 <= hi1 && lo1 <= hi0; // } +enum Quadrant { + QUADRANT_SW, + QUADRANT_SE, + QUADRANT_NW, + QUADRANT_NE, +}; + +struct v3u32 { + u32 x, y, z; + + v3u32() { } + + explicit v3u32( u32 a, u32 b, u32 c ) { + x = a; + y = b; + z = c; + } +}; + +struct AABBu32 { + v3u32 mins, maxs; + + AABBu32() { } + + explicit AABBu32( v3u32 a, v3u32 b ) { + mins.x = min( a.x, b.x ); + mins.y = min( a.y, b.y ); + mins.z = min( a.z, b.z ); + maxs.x = max( a.x, b.x ); + maxs.y = max( a.y, b.y ); + maxs.z = max( a.z, b.z ); + } + + AABBu32 quadrant( int q ) const; + AABBu32 clamp_z( u32 lo, u32 hi ); +}; + +inline v3u32 operator+( v3u32 u, v3u32 v ) { + return v3u32( u.x + v.x, u.y + v.y, u.z + v.z ); +} + +inline v3u32 operator-( v3u32 u, v3u32 v ) { + return v3u32( u.x - v.x, u.y - v.y, u.z - v.z ); +} + +inline v3u32 operator/( v3u32 v, u32 d ) { + return v3u32( v.x / d, v.y / d, v.z / d ); +} + struct AABB { - v3 center, extents; + v3 mins, maxs; AABB() { } - explicit AABB( v3 c, v3 e ) { - assert( e.x >= 0 && e.y >= 0 && e.z >= 0 ); - - center = c; - extents = e; + explicit AABB( v3 a, v3 b ) { + mins.x = min( a.x, b.x ); + mins.y = min( a.y, b.y ); + mins.y = min( a.z, b.z ); + maxs.y = max( a.x, b.x ); + maxs.y = max( a.y, b.y ); + maxs.y = max( a.z, b.z ); } - v3 mins() const { return center - extents; } - v3 maxs() const { return center + extents; } - AABB quadrant( int q ); - AABB clamp_z( float lo, float hi ); + explicit AABB( AABBu32 aabb ) { + mins.x = checked_cast< float >( aabb.mins.x ); + mins.y = checked_cast< float >( aabb.mins.y ); + mins.z = checked_cast< float >( aabb.mins.z ); + maxs.x = checked_cast< float >( aabb.maxs.x ); + maxs.y = checked_cast< float >( aabb.maxs.y ); + maxs.z = checked_cast< float >( aabb.maxs.z ); + } 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; + 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,7 @@ #include "linear_algebra.h" #include "lz4.h" -#define TERRAIN_NAME "grad.png" +#define TERRAIN_NAME "mountains512.png" static ImmediateTriangle triangles[ megabytes( 16 ) ]; static ImmediateContext imm; @@ -210,18 +210,21 @@ 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 ); +static void draw_qt( ImmediateContext * imm, AABBu32 aabb, const array< HeightmapQuadTreeNode > nodes, size_t node_idx ) { + if( aabb.maxs.x - aabb.mins.x >= 32 ) { + 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; + if( aabb.maxs.x - aabb.mins.x == 1 || aabb.maxs.y - aabb.mins.y == 1 ) { + 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 ] ); + AABBu32 child_aabb = aabb.quadrant( i ).clamp_z( nodes[ node_idx * 4 + i + 1 ].min_z, nodes[ node_idx * 4 + i + 1 ].max_z ); + draw_qt( imm, child_aabb, nodes, node_idx * 4 + i + 1 ); } } @@ -288,9 +291,9 @@ extern "C" GAME_FRAME( game_frame ) { 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 ); + v3u32 mins = v3u32( 0, 0, qt.nodes[ 0 ].min_z ); + v3u32 maxs = v3u32( qt.dim, qt.dim, qt.nodes[ 0 ].max_z ); + draw_qt( &imm, AABBu32( mins, maxs ), qt.nodes, 0 ); 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 );