medfall

commit 062074e58165845be38232b119a06c77994d329a
parent 69efb014b7eb05ace52d57b36b142a11837576a8
Author: Michael Savage <mikejsavage@gmail.com>
Date:   Fri Jun  2 01:22:50 +0300

Simplify ray_vs_quadtree_node

Diffstat:
heightmap.cc
 | 
54
++++++++++++++++++++++++++++++++++++------------------
1 file changed, 36 insertions(+), 18 deletions(-)
diff --git a/heightmap.cc b/heightmap.cc
@@ -1,4 +1,5 @@
 #include <stdio.h>
+#include <float.h>
 
 #include "intrinsics.h"
 #include "linear_algebra.h"
@@ -229,6 +230,33 @@ HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm, array< Heightm
 	return qt;
 }
 
+static void swap( int * a, int * b ) {
+	float t = *a;
+	*a = *b;
+	*b = t;
+}
+
+static void sort4( int * indices, float * elems ) {
+	for( int i = 0; i < 4; i++ )
+		indices[ i ] = i;
+
+	// sort a/b and c/d
+	if( elems[ indices[ 0 ] ] > elems[ indices[ 1 ] ] )
+		swap( &indices[ 0 ], &indices[ 1 ] );
+	if( elems[ indices[ 2 ] ] > elems[ indices[ 3 ] ] )
+		swap( &indices[ 2 ], &indices[ 3 ] );
+
+	// find lowest and highest
+	if( elems[ indices[ 0 ] ] > elems[ indices[ 2 ] ] )
+		swap( &indices[ 0 ], &indices[ 2 ] );
+	if( elems[ indices[ 1 ] ] > elems[ indices[ 3 ] ] )
+		swap( &indices[ 1 ], &indices[ 3 ] );
+
+	// sort middle two
+	if( elems[ indices[ 1 ] ] > elems[ indices[ 2 ] ] )
+		swap( &indices[ 1 ], &indices[ 2 ] );
+}
+
 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
@@ -273,32 +301,22 @@ static bool ray_vs_quadtree_node(
 
 	AABBu32 aabbs[ 4 ];
 	float ts[ 4 ];
-	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 ] ), ray_origin, inv_dir, &ts[ i ] ) ) << i;
+		ts[ i ] = FLT_MAX;
+		ray_vs_aabb( AABB( aabbs[ i ] ), ray_origin, inv_dir, &ts[ i ] );
 	}
 
-	u32 visited_mask = 0;
-	for( int i = 0; i < 4; i++ ) {
-		if( visited_mask == hit_mask ) {
-			return false;
-		}
+	int sorted[ 4 ];
+	sort4( sorted, ts );
 
-		u32 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;
-			}
-		}
+	for( int i = 0; i < 4; i++ ) {
+		int idx = sorted[ i ];
+		if( ts[ idx ] == FLT_MAX ) break;
 
-		if( ray_vs_quadtree_node( qt, child_idx( node_idx, lowest ), aabbs[ lowest ], ray_origin, ray_dir, inv_dir, t, xnormal ) ) {
+		if( ray_vs_quadtree_node( qt, child_idx( node_idx, idx ), aabbs[ idx ], ray_origin, ray_dir, inv_dir, t, xnormal ) ) {
 			return true;
 		}
-
-		visited_mask |= 1 << lowest;
 	}
 
 	return false;