summaryrefslogtreecommitdiff
path: root/u_world.c
diff options
context:
space:
mode:
Diffstat (limited to 'u_world.c')
-rw-r--r--u_world.c428
1 files changed, 428 insertions, 0 deletions
diff --git a/u_world.c b/u_world.c
new file mode 100644
index 0000000..385c9fc
--- /dev/null
+++ b/u_world.c
@@ -0,0 +1,428 @@
+/*
+=======================================================================
+This file is part of Redman's RT.
+
+Redman's RT is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+
+Redman's RT is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with Redman's RT. If not, see <http://www.gnu.org/licenses/>.
+=======================================================================
+*/
+
+#include "common.h"
+
+void W_InitWorld( W_world_t *world )
+{
+ memset( world, 0, sizeof( W_world_t ) );
+}
+
+void W_DeleteWorld( W_world_t *world )
+{
+ if( world->otroot )
+ W_DeleteOTNode( world->otroot );
+ world->otroot = NULL;
+}
+
+W_otnode_t *W_NewOTNode( W_otnode_t *p, int i )
+{
+ W_otnode_t *n;
+
+ //todo: error handling
+ n = malloc( sizeof( W_otnode_t ) );
+ memset( n, 0, sizeof( W_otnode_t ) );
+
+ n->i = i;
+ n->p = p;
+
+#define SUBNODE( dx, dy, dz ) \
+ V3Set( n->aabb[ 0 ], p->aabb[ 0 ][ 0 ] + dx, p->aabb[ 0 ][ 1 ] + dy, p->aabb[ 0 ][ 2 ] + dz ), \
+ V3Set( n->aabb[ 1 ], n->aabb[ 0 ][ 0 ] + d, n->aabb[ 0 ][ 1 ] + d, n->aabb[ 0 ][ 2 ] + d );
+
+ if( p )
+ {
+ float d;
+
+ d = ( p->aabb[ 1 ][ 0 ] - p->aabb[ 0 ][ 0 ] ) * 0.5;
+
+ switch( i )
+ {
+ case 0:
+ SUBNODE( 0, 0, 0 )
+ break;
+ case 1:
+ SUBNODE( d, 0, 0 )
+ break;
+ case 2:
+ SUBNODE( 0, d, 0 )
+ break;
+ case 3:
+ SUBNODE( d, d, 0 )
+ break;
+ case 4:
+ SUBNODE( 0, 0, d )
+ break;
+ case 5:
+ SUBNODE( d, 0, d )
+ break;
+ case 6:
+ SUBNODE( 0, d, d )
+ break;
+ case 7:
+ SUBNODE( d, d, d )
+ break;
+ }
+ }
+
+ return n;
+}
+
+void W_DeleteOTNode( W_otnode_t *n )
+{
+ int i;
+
+ for( i = 0; i < 8; i++ )
+ if( n->n[ i ] )
+ W_DeleteOTNode( n->n[ i ] );
+
+ if( n->p )
+ n->p->n[ n->i ] = NULL;
+
+ free( n );
+}
+
+static void W_Generate_R( W_otnode_t *node, size_t *depth, size_t targetDepth )
+{
+ size_t i;
+
+ (*depth)++;
+
+#if 0
+ if( (*depth) <= targetDepth )
+ {
+ for( i = 0; i < 8; i++ )
+ {
+ node->n[ i ] = W_NewOTNode( node, i );
+ W_Generate_R( node->n[ i ], depth, targetDepth );
+ }
+ node->data = 0;
+ }
+ else
+ node->data = ( node->aabb[ 1 ][ 2 ] > 31.99 );
+#endif
+
+ for( i = 0; i < 8; i++ )
+ {
+ if( ( rand( ) % 10 < 9 ) && (*depth) <= targetDepth )
+ {
+ node->data = 0;
+ node->n[ i ] = W_NewOTNode( node, i );
+ W_Generate_R( node->n[ i ], depth, targetDepth );
+ }
+ else
+ node->data = rand( ) % 2;
+ }
+
+ (*depth)--;
+}
+
+void W_CreateEmptyWorld( W_world_t *world )
+{
+ size_t depth = 0;
+
+ world->otroot = W_NewOTNode( NULL, 0 );
+ world->otroot->data = 1;
+ V3Set( world->otroot->aabb[ 0 ], -32, -32, -32 );
+ V3Set( world->otroot->aabb[ 1 ], 32, 32, 32 );
+
+ W_Generate_R( world->otroot, &depth, 8 );
+ W_Optimize( world->otroot );
+
+ V3Set( world->saved_origin, 0, 0, -16 );
+ V3Set( world->saved_angles, 0, 0, 0 );
+}
+
+W_otnode_t *W_Point( W_otnode_t *node, vec3_t const point )
+{
+ size_t _debug_depth = 0;
+ size_t i;
+ W_otnode_t *n;
+
+ if( !U_PointInAABB( point, (const vec3_t*)node->aabb ) )
+ return NULL;
+
+ n = node;
+
+deeper:
+ for( i = 0; i < 8; i++ )
+ {
+ if( !n->n[ i ] )
+ continue;
+
+ if( !U_PointInAABB( point, (const vec3_t*)n->n[ i ]->aabb ) )
+ continue;
+
+ n = n->n[ i ];
+ _debug_depth++;
+ goto deeper;
+ }
+
+ return n;
+}
+
+static W_otnode_t *W_Trace_R(
+ W_otnode_t *n, const W_otnode_t *ignore, const ray_t *ray, rtres_t *rt )
+{
+ size_t i;
+ bool_t intersects;
+ W_otnode_t *_n;
+
+ if( n == ignore )
+ return NULL;
+
+ if( !n->data )
+ intersects = U_RT_AABB_Fast( (const vec3_t const*) n->aabb, ray, rt );
+ else
+ intersects = U_RT_AABB( (const vec3_t const*) n->aabb, ray, rt );
+
+ if( rt->startsolid || rt->dist > ray->limit )
+ {
+ rt->exit = true;
+ return NULL;
+ }
+
+ if( n->data )
+ {
+ if( intersects )
+ {
+ memcpy( &rt->data, &n->data, sizeof( W_blockdata_t ) );
+ return n;
+ }
+ else
+ return NULL;
+ }
+ else if( !intersects )
+ return NULL;
+
+ for( i = 0; i < 8; i++ )
+ if( n->n[ ray->otorder[ i ] ] )
+ if( ( _n = W_Trace_R( n->n [ ray->otorder[ i ] ], ignore, ray, rt ) )
+ && !rt->exit )
+ return _n;
+
+ return NULL;
+}
+
+W_otnode_t *W_Trace( W_world_t *world, const W_otnode_t *ignore, const ray_t *ray, rtres_t *rt )
+{
+ if( world->otroot )
+ return W_Trace_R( world->otroot, ignore, ray, rt );
+ else
+ return false;
+}
+
+bool_t W_Optimize( W_otnode_t *node )
+{
+ bool_t optimized = false;
+ size_t i;
+ W_blockdata_t data = BLOCK_NONE;
+
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ if( W_Optimize( node->n[ i ] ) )
+ optimized = true;
+
+ if( node->data )
+ goto skip_removal;
+
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ goto skip_removal;
+
+ W_DeleteOTNode( node );
+ return true;
+
+skip_removal:
+
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ if( node->n[ i ]->data != BLOCK_NONE )
+ {
+ data = node->n[ i ]->data;
+ break;
+ }
+
+ if( data == BLOCK_NONE )
+ goto skip_merge;
+
+ for( i = 0; i < 8; i++ )
+ {
+ if( !node->n[ i ] )
+ goto skip_merge;
+
+ if( node->n[ i ]->data != data )
+ goto skip_merge;
+ }
+
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ W_DeleteOTNode( node->n[ i ] );
+
+ node->data = data;
+ return true;
+
+skip_merge:
+ return optimized;
+}
+
+
+void W_Save_R( const W_otnode_t *node, FILE *fd )
+{
+ int i;
+ uint8_t cflags;
+
+ cflags = ( node->n[ 0 ] != NULL ) |
+ ( ( node->n[ 1 ] != NULL ) << 1 ) |
+ ( ( node->n[ 2 ] != NULL ) << 2 ) |
+ ( ( node->n[ 3 ] != NULL ) << 3 ) |
+ ( ( node->n[ 4 ] != NULL ) << 4 ) |
+ ( ( node->n[ 5 ] != NULL ) << 5 ) |
+ ( ( node->n[ 6 ] != NULL ) << 6 ) |
+ ( ( node->n[ 7 ] != NULL ) << 7 );
+
+
+ fwrite( &node->data, sizeof( W_blockdata_t ), 1, fd );
+ fwrite( &cflags, sizeof( cflags ), 1, fd );
+
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ W_Save_R( node->n[ i ], fd );
+}
+
+void W_Save( const W_world_t *world, const char *file )
+{
+ FILE *fd;
+
+ fd = fopen( file, "wb" );
+
+ if( !fd )
+ return;
+
+ fwrite( world->saved_origin, sizeof( vec_t ), 3, fd );
+ fwrite( world->saved_angles, sizeof( vec_t ), 3, fd );
+
+ if( world->otroot )
+ W_Save_R( world->otroot, fd );
+
+ fclose( fd );
+}
+
+void W_Load_R( W_otnode_t *node, FILE *fd, size_t *count )
+{
+ int i;
+ uint8_t cflags;
+
+ (*count)++;
+
+ fread( &node->data, sizeof( W_blockdata_t ), 1, fd );
+ fread( &cflags, sizeof( cflags ), 1, fd );
+
+ for( i = 0; i < 8; i++ )
+ if( cflags & ( 1 << i ) )
+ {
+ node->n[ i ] = W_NewOTNode( node, i );
+ W_Load_R( node->n[ i ], fd, count );
+ }
+}
+
+int W_Load( W_world_t *world, const char *file )
+{
+ FILE *fd;
+ size_t count = 0;
+
+ fd = fopen( file, "rb" );
+
+ if( !fd )
+ return 1;
+
+ fread( world->saved_origin, sizeof( vec_t ), 3, fd );
+ fread( world->saved_angles, sizeof( vec_t ), 3, fd );
+
+ W_Load_R( world->otroot, fd, &count );
+
+ fclose( fd );
+
+ printf( "loaded nodes: %zu\n", count );
+
+ return 0;
+}
+
+static void W_Dump_R( W_otnode_t *node, size_t *count, size_t *depth )
+{
+ size_t i;
+
+ (*depth)++;
+
+ printf( "%*s%p, %i {\n", (int)(*depth) * 2, "", node, node->data );
+
+ if( *depth > 50 )
+ {
+ printf( "CIRCULAR REFERENCE\n" );
+ return;
+ }
+
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ W_Dump_R( node->n[ i ], count, depth );
+
+ printf( "%*s}\n", (int)(*depth) * 2, "" );
+
+ (*depth)--;
+}
+
+void W_Dump( W_world_t *world )
+{
+ size_t count = 0, depth = 0;
+
+ if( !world->otroot )
+ {
+ printf( "empty world\n" );
+ return;
+ }
+
+ printf( "world\n{" );
+ W_Dump_R( world->otroot, &count, &depth );
+ printf( "}\nnodes: %zu\n", count );
+}
+
+
+static void W_Stats_R( const W_otnode_t *node, size_t *nodes, size_t *leaves )
+{
+ size_t i;
+ bool_t leaf = true;
+
+ (*nodes)++;
+
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ leaf = false, W_Stats_R( node->n[ i ], nodes, leaves );
+
+ if( leaf )
+ (*leaves)++;
+}
+
+void W_Stats( const W_world_t *world, size_t *nodes, size_t *leaves )
+{
+ (*nodes) = 0;
+ (*leaves) = 0;
+
+ if( world->otroot )
+ W_Stats_R( world->otroot, nodes, leaves );
+}
generated by cgit (git 2.34.1) at 2024-05-07 16:09:40 +0000