medfall

commit 1bef1d52b1a8ad495002ba9d3a1bd6e3dbb94f7f
parent c3203917749fa18ff9c8419609b8745a6d3b2e25
Author: Michael Savage <mikejsavage@gmail.com>
Date:   Sun Jul  2 23:21:55 +0300

2x2 quadtree leaves. Chops quadtree disk size from 26MB to 7MB

Diffstat:
heightmap.cc
 | 
92
++++++++++++++++++++++++++++++++++++++++++-------------------------------------
1 file changed, 49 insertions(+), 43 deletions(-)
diff --git a/heightmap.cc b/heightmap.cc
@@ -188,15 +188,17 @@ static size_t child_idx( size_t node_idx, size_t quadrant ) {
 }
 
 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;
-		u16 a = heightmap_height_u16( qt->hm, x, y );
-		u16 b = heightmap_height_u16( qt->hm, x + 1, y );
-		u16 c = heightmap_height_u16( qt->hm, x, y + 1 );
-		u16 d = heightmap_height_u16( 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 );
+	qt->nodes[ node_idx ].min_z = U16_MAX;
+	qt->nodes[ node_idx ].max_z = 0;
+
+	if( aabb.maxs.x - aabb.mins.x == 2 || aabb.maxs.y - aabb.mins.y == 2 ) {
+		for( size_t y = aabb.mins.y; y <= aabb.maxs.y; y++ ) {
+			for( size_t x = aabb.mins.x; x <= aabb.maxs.x; x++ ) {
+				u16 h = heightmap_height_u16( qt->hm, x, y );
+				qt->nodes[ node_idx ].min_z = min( h, qt->nodes[ node_idx ].min_z );
+				qt->nodes[ node_idx ].max_z = max( h, qt->nodes[ node_idx ].max_z );
+			}
+		}
 
 		return;
 	}
@@ -214,10 +216,10 @@ static void heightmap_build_quadtree_node( HeightmapQuadTree * qt, size_t node_i
 }
 
 size_t heightmap_quadtree_max_nodes( const Heightmap * hm ) {
-	// with a power of 2 + 1 sized quadtree it should be exactly 4/3 (1 +
-	// 1/4 + 1/16 + ...) but with other sizes it gets funny. 1.34 seems to
-	// work with minimal wasted space
-	return size_t( 1.34 * ( hm->width - 1 ) * ( hm->width - 1 ) );
+	// with a power of 2 + 1 sized quadtree with a 2x2 bottom level it
+	// should be exactly 1/3 (1/4 + 1/16 + ...) but with other sizes it
+	// gets funny. 0.34 seems to work with minimal wasted space
+	return size_t( 0.34 * ( hm->width - 1 ) * ( hm->width - 1 ) );
 }
 
 HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm, array< HeightmapQuadTreeNode > & nodes ) {
@@ -266,38 +268,42 @@ static bool ray_vs_quadtree_node(
 	const HeightmapQuadTree * qt, size_t node_idx, AABBu32 aabb,
 	const Ray3 & ray, float * t, v3 * xnormal
 ) {
-	if( aabb.maxs.x - aabb.mins.x == 1 || aabb.maxs.y - aabb.mins.y == 1 ) {
+	if( aabb.maxs.x - aabb.mins.x == 2 || aabb.maxs.y - aabb.mins.y == 2 ) {
 		bool hit = false;
 
-		u32 x = aabb.mins.x;
-		u32 y = aabb.mins.y;
-
-		v3 p0 = qt->hm->point( x, y );
-		v3 p1 = qt->hm->point( x + 1, y );
-		v3 p2 = qt->hm->point( x, y + 1 );
-		v3 p3 = qt->hm->point( x + 1, y + 1 );
-
-		// bottom right triangle
-		float 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 < *t ) {
-				*t = t0;
-				*xnormal = normal0;
-				hit = true;
-			}
-		}
-
-		// top left triangle
-		float 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 < *t ) {
-				*t = t1;
-				*xnormal = normal1;
-				hit = true;
+		for( size_t i = 0; i < 2; i++ ) {
+			for( size_t j = 0; j < 2; j++ ) {
+				u32 x = aabb.mins.x + j;
+				u32 y = aabb.mins.y + i;
+
+				v3 p0 = qt->hm->point( x, y );
+				v3 p1 = qt->hm->point( x + 1, y );
+				v3 p2 = qt->hm->point( x, y + 1 );
+				v3 p3 = qt->hm->point( x + 1, y + 1 );
+
+				// bottom right triangle
+				float 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 < *t ) {
+						*t = t0;
+						*xnormal = normal0;
+						hit = true;
+					}
+				}
+
+				// top left triangle
+				float 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 < *t ) {
+						*t = t1;
+						*xnormal = normal1;
+						hit = true;
+					}
+				}
 			}
 		}