btt.cc (3262B)
1 #include "intrinsics.h" 2 #include "memory_arena.h" 3 #include "btt.h" 4 #include "heightmap.h" 5 6 /* 7 * triangles should look like this: 8 * 9 * v1 10 * / \ 11 * / \ 12 * / \ 13 * v0 /______________\ v2 14 * hypotenuse 15 */ 16 17 static void btt_link_diamond( MemoryArena * arena, BTT * node ) { 18 node->left = alloc< BTT >( arena ); 19 node->right = alloc< BTT >( arena ); 20 21 *node->left = { }; 22 *node->right = { }; 23 24 node->left->left_sibling = node->right; 25 node->right->right_sibling = node->left; 26 27 node->left->bottom = node->left_sibling; 28 node->right->bottom = node->right_sibling; 29 30 if( node->left_sibling ) { 31 BTT * ls = node->left_sibling; 32 if( ls->left_sibling == node ) ls->left_sibling = node->left; 33 if( ls->right_sibling == node ) ls->right_sibling = node->left; 34 if( ls->bottom == node ) ls->bottom = node->left; 35 } 36 37 if( node->right_sibling ) { 38 BTT * rs = node->right_sibling; 39 if( rs->left_sibling == node ) rs->left_sibling = node->right; 40 if( rs->right_sibling == node ) rs->right_sibling = node->right; 41 if( rs->bottom == node ) rs->bottom = node->right; 42 } 43 } 44 45 static void btt_split( MemoryArena * arena, BTT * node ) { 46 ASSERT( node != NULL ); 47 ASSERT( node->left == NULL && node->right == NULL ); 48 49 if( node->bottom && node->bottom->bottom != node ) { 50 btt_split( arena, node->bottom ); 51 } 52 53 btt_link_diamond( arena, node ); 54 55 if( node->bottom ) { 56 btt_link_diamond( arena, node->bottom ); 57 58 node->left->right_sibling = node->bottom->right; 59 node->right->left_sibling = node->bottom->left; 60 61 node->bottom->left->right_sibling = node->right; 62 node->bottom->right->left_sibling = node->left; 63 } 64 } 65 66 static s32 square_distance( v2s32 u, v2s32 v ) { 67 v2s32 d = v - u; 68 return dot( d, d ); 69 } 70 71 static bool btt_should_split( const array2d< u16 > hm, v2s32 v0, v2s32 v1, v2s32 v2, v2s32 mid ) { 72 if( square_distance( v0, v2 ) <= 4 ) return false; 73 74 const float avg_height = ( heightmap_height( hm, v0.x, v0.y ) + heightmap_height( hm, v2.x, v2.y ) ) * 0.5f; 75 const float error = fabsf( avg_height - heightmap_height( hm, mid.x, mid.y ) ); 76 77 if( error > 2.0f ) return true; 78 79 return btt_should_split( hm, v1, mid, v0, ( v1 + v0 ) / 2 ) || btt_should_split( hm, v2, mid, v1, ( v2 + v1 ) / 2 ); 80 } 81 82 static void btt_build( 83 const array2d< u16 > hm, MemoryArena * arena, 84 BTT * node, v2s32 v0, v2s32 v1, v2s32 v2 85 ) { 86 v2s32 mid = ( v0 + v2 ) / 2; 87 88 if( !node->left ) { 89 ASSERT( node->right == NULL ); 90 91 if( btt_should_split( hm, v0, v1, v2, mid ) ) { 92 btt_split( arena, node ); 93 } 94 } 95 96 if( node->left ) { 97 ASSERT( node->right != NULL ); 98 99 btt_build( hm, arena, node->left, v1, mid, v0 ); 100 btt_build( hm, arena, node->right, v2, mid, v1 ); 101 } 102 } 103 104 BTTs btt_from_heightmap( const array2d< u16 > hm, MemoryArena * arena ) { 105 BTTs roots; 106 107 roots.left_root = alloc< BTT >( arena ); 108 roots.right_root = alloc< BTT >( arena ); 109 110 *roots.left_root = { }; 111 *roots.right_root = { }; 112 113 roots.left_root->bottom = roots.right_root; 114 roots.right_root->bottom = roots.left_root; 115 116 btt_build( hm, arena, roots.left_root, v2s32( 0, 0 ), v2s32( 0, hm.h - 1 ), v2s32( hm.w - 1, hm.h - 1 ) ); 117 btt_build( hm, arena, roots.right_root, v2s32( hm.w - 1, hm.h - 1 ), v2s32( hm.w - 1, 0 ), v2s32( 0, 0 ) ); 118 119 return roots; 120 }