commit 59d958cf4c60c3de53d4fc9200bc66e1881096a8 parent cdd516cee038074a846c2b9c52ff9c12f8009b5f Author: Michael Savage <mikejsavage@gmail.com> Date: Wed Dec 28 00:26:51 +0200 Slightly faster ray vs quadtree/terrain + return triangle normal Diffstat:
| heightmap.cc | | | 41 | ++++++++++++++++++++--------------------- |
| heightmap.h | | | 2 | +- |
| hm.cc | | | 6 | +++--- |
| mod_btt.cc | | | 5 | ++++- |
| terrain_manager.cc | | | 12 | +++++++++--- |
| terrain_manager.h | | | 2 | +- |
diff --git a/heightmap.cc b/heightmap.cc @@ -63,14 +63,12 @@ float Heightmap::bilerp_height( float x, float y ) const { // // -bool ray_vs_aabb( AABB aabb, v3 start, v3 dir, float * t ) { +bool ray_vs_aabb( AABB aabb, v3 start, v3 inv_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; @@ -265,9 +263,11 @@ HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm, array< Heightm return qt; } -static bool ray_vs_quadtree_node( const HeightmapQuadTree * qt, size_t node_idx, AABBu32 aabb, v3 origin, v3 direction, float * t ) { +static bool ray_vs_quadtree_node( + const HeightmapQuadTree * qt, size_t node_idx, AABBu32 aabb, + v3 ray_origin, v3 ray_dir, v3 inv_dir, float * t, v3 * xnormal +) { if( aabb.maxs.x - aabb.mins.x == 1 || aabb.maxs.y - aabb.mins.y == 1 ) { - float min_t = 0; bool hit = false; u32 x = aabb.mins.x; @@ -280,30 +280,29 @@ static bool ray_vs_quadtree_node( const HeightmapQuadTree * qt, size_t node_idx, // bottom right triangle float t0; - bool hit0 = ray_vs_triangle( origin, direction, p0, p1, p3, &t0 ); + v3 normal0 = triangle_normal( p0, p1, p3 ); + bool hit0 = ray_vs_triangle( ray_origin, ray_dir, p0, p1, p3, &t0 ); if( hit0 ) { - if( !hit || t0 < min_t ) { - min_t = t0; + if( !hit || t0 < *t ) { + *t = t0; + *xnormal = normal0; hit = true; } } // top left triangle float t1; - bool hit1 = ray_vs_triangle( origin, direction, p0, p3, p2, &t1 ); + v3 normal1 = triangle_normal( p0, p3, p2 ); + bool hit1 = ray_vs_triangle( ray_origin, ray_dir, p0, p3, p2, &t1 ); if( hit1 ) { - if( !hit || t1 < min_t ) { - min_t = t1; + if( !hit || t1 < *t ) { + *t = t1; + *xnormal = normal1; hit = true; } } - if( hit ) { - *t = min_t; - return true; - } - - return false; + return hit; } AABBu32 aabbs[ 4 ]; @@ -311,7 +310,7 @@ static bool ray_vs_quadtree_node( const HeightmapQuadTree * qt, size_t node_idx, u32 hit_mask = 0; for( int i = 0; i < 4; 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; + hit_mask |= u32( ray_vs_aabb( AABB( aabbs[ i ] ), ray_origin, inv_dir, &ts[ i ] ) ) << i; } u32 visited_mask = 0; @@ -329,7 +328,7 @@ static bool ray_vs_quadtree_node( const HeightmapQuadTree * qt, size_t node_idx, } } - if( ray_vs_quadtree_node( qt, child_idx( node_idx, lowest ), aabbs[ lowest ], origin, direction, t ) ) { + if( ray_vs_quadtree_node( qt, child_idx( node_idx, lowest ), aabbs[ lowest ], ray_origin, ray_dir, inv_dir, t, xnormal ) ) { return true; } @@ -339,10 +338,10 @@ static bool ray_vs_quadtree_node( const HeightmapQuadTree * qt, size_t node_idx, return false; } -bool ray_vs_quadtree( const HeightmapQuadTree * qt, v3 origin, v3 direction, float * t ) { +bool ray_vs_quadtree( const HeightmapQuadTree * qt, v3 ray_origin, v3 ray_dir, v3 inv_dir, float * t, v3 * xnormal ) { 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, 0, aabb, origin, direction, t ); + return ray_vs_quadtree_node( qt, 0, aabb, ray_origin, ray_dir, inv_dir, t, xnormal ); } diff --git a/heightmap.h b/heightmap.h @@ -114,6 +114,6 @@ struct AABB { } }; -bool ray_vs_quadtree( const HeightmapQuadTree * qt, v3 origin, v3 direction, float * t ); +bool ray_vs_quadtree( const HeightmapQuadTree * qt, v3 ray_origin, v3 ray_dir, v3 inv_dir, float * t, v3 * xnormal ); #endif // _HEIGHTMAP_H_ diff --git a/hm.cc b/hm.cc @@ -232,11 +232,11 @@ extern "C" GAME_FRAME( game_frame ) { immediate_init( &imm, sphere, ARRAY_COUNT( sphere ) ); float t; + v3 normal; v3 seg_end = game->pos + 1024.0f * angles_to_vector( game->angles ); - if( segment_vs_terrain( &game->tm, game->pos, seg_end, &t ) ) { + if( segment_vs_terrain( &game->tm, game->pos, seg_end, &t, &normal ) ) { 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 ) ); + immediate_arrow( &imm, impact, normal, 16, v4( 1, 0, 0, 1 ) ); } // else printf( "nope\n" ); diff --git a/mod_btt.cc b/mod_btt.cc @@ -292,7 +292,10 @@ extern "C" GAME_FRAME( game_frame ) { } float t; - if( ray_vs_quadtree( &qt, game->pos, angles_to_vector( game->angles ), &t ) ) { + v3 ray_dir = angles_to_vector( game->angles ); + v3 inv_dir = v3( 1.0f / ray_dir.x, 1.0f / ray_dir.y, 1.0f / ray_dir.z ); + v3 xnormal; + if( ray_vs_quadtree( &qt, game->pos, ray_dir, inv_dir, &t, &xnormal ) ) { v3 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, v4( 1, 0, 0, 1 ) ); diff --git a/terrain_manager.cc b/terrain_manager.cc @@ -547,11 +547,17 @@ v3 terrain_normal( const TerrainManager * tm, v3 position ) { return normalize( bilerp( normalmap, local_x, local_y ) ); } -bool segment_vs_terrain( const TerrainManager * tm, v3 seg_origin, v3 seg_end, float * t ) { +bool segment_vs_terrain( const TerrainManager * tm, v3 seg_origin, v3 seg_end, float * t, v3 * xnormal ) { PROFILE_FUNCTION(); + v3 dont_care; + if( xnormal == NULL ) { + xnormal = &dont_care; + } + float segment_length = length( seg_end - seg_origin ); - v3 ray_direction = normalize( seg_end - seg_origin ); + v3 ray_dir = normalize( seg_end - seg_origin ); + v3 inv_dir = v3( 1.0f / ray_dir.x, 1.0f / ray_dir.y, 1.0f / ray_dir.z ); bool hit = false; @@ -572,7 +578,7 @@ bool segment_vs_terrain( const TerrainManager * tm, v3 seg_origin, v3 seg_end, f 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 ); + bool tile_hit = ray_vs_quadtree( qt, local_seg_origin, ray_dir, inv_dir, &tile_t, xnormal ); if( tile_hit && ( !hit || tile_t < *t ) && tile_t <= segment_length ) { hit = true; diff --git a/terrain_manager.h b/terrain_manager.h @@ -89,6 +89,6 @@ void terrain_render( TerrainManager * tm, const m4 & V, const m4 & P, float sun, 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 ); +bool segment_vs_terrain( const TerrainManager * tm, v3 seg_origin, v3 seg_end, float * t, v3 * xnormal ); #endif // _TERRAIN_MANAGER_H_