medfall

commit 47831cd14540339593bef496e9e398b4ce0ed49b
parent f8bea513b8756edcaaea63d1c9832d6dc2f9a673
Author: Michael Savage <mikejsavage@gmail.com>
Date:   Sun Nov 13 19:41:26 +0200

Tighter quadtree node bounds

Diffstat:
heightmap.cc
 | 
6
++++--
1 file changed, 4 insertions(+), 2 deletions(-)
diff --git a/heightmap.cc b/heightmap.cc
@@ -275,8 +275,10 @@ static void heightmap_build_quadtree_node( HeightmapQuadTree * qt, size_t node_i
 }
 
 HeightmapQuadTree heightmap_build_quadtree( const Heightmap * hm ) {
-	// convervative upper bound
-	size_t num_nodes = 2 * ( hm->width - 1 ) * ( hm->width - 1 );
+	// 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
+	size_t num_nodes = 1.34 * ( hm->width - 1 ) * ( hm->width - 1 );
 
 	HeightmapQuadTree qt;
 	qt.hm = hm;