summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.u_world.c.swpbin0 -> 24576 bytes
-rwxr-xr-xbuild.sh8
-rw-r--r--common.h416
-rw-r--r--main.c1556
-rw-r--r--player.c384
-rwxr-xr-xrrtbin0 -> 64240 bytes
-rw-r--r--tex/1.jpgbin0 -> 64371 bytes
-rw-r--r--tex/2.jpgbin0 -> 224082 bytes
-rw-r--r--tex/6.jpgbin0 -> 18022 bytes
-rw-r--r--u_math.c151
-rw-r--r--u_misc.c36
-rw-r--r--u_platform.c56
-rw-r--r--u_ray.c257
-rw-r--r--u_world.c428
-rw-r--r--worldbin0 -> 21124 bytes
-rw-r--r--world_konkursbin0 -> 20732 bytes
16 files changed, 3292 insertions, 0 deletions
diff --git a/.u_world.c.swp b/.u_world.c.swp
new file mode 100644
index 0000000..7079a04
--- /dev/null
+++ b/.u_world.c.swp
Binary files differ
diff --git a/build.sh b/build.sh
new file mode 100755
index 0000000..ca04100
--- /dev/null
+++ b/build.sh
@@ -0,0 +1,8 @@
+#!/bin/bash
+INPUT="main.c u_platform.c u_math.c u_misc.c u_world.c u_ray.c player.c"
+OUTPUT="rrt"
+FLAGS_CC="-Wall -O3 -fno-diagnostics-show-caret -Wno-unused-result -ffast-math -march=native"
+FLAGS_LD="-lSDL2 -lSDL2_image -lrt -lm"
+
+echo "-------------------------"
+gcc $INPUT -o $OUTPUT $FLAGS_CC $FLAGS_LD
diff --git a/common.h b/common.h
new file mode 100644
index 0000000..a9261b8
--- /dev/null
+++ b/common.h
@@ -0,0 +1,416 @@
+/*
+=======================================================================
+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/>.
+=======================================================================
+*/
+
+#ifndef __COMMON_HEADER
+#define __COMMON_HEADER
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdarg.h>
+#include <string.h>
+#include <math.h>
+#include <ctype.h>
+#include <SDL2/SDL.h>
+#include <SDL2/SDL_image.h>
+
+//TODO: figure out the platform here
+#define PLATFORM_POSIX
+/////////////////
+
+#define PROGRAM_NAME "RRT"
+//#define PROGRAM_VERSION "pre-alpha"
+//#define PROGRAM_FULLNAME PROGRAM_NAME " (" PROGRAM_VERSION ")"
+#define PROGRAM_FULLNAME PROGRAM_NAME
+
+typedef enum
+{
+ false,
+ true
+} bool_t;
+
+#define Swap(T,a,b) {T ___t;___t=(a);(a)=(b);(b)=___t;}
+
+ /* Scalar utilities */
+
+typedef float vec_t;
+
+#define V1Min(a,b) ((a)<(b)?(a):(b))
+#define V1Max(a,b) ((a)>(b)?(a):(b))
+#define V1Clamp(n,a,b) ((n)<(a)?(a):(n)>(b)?(b):(n))
+#define V1Epscmp(a,b,e) (fabs((a)-(b))<e)
+#define V1Lerp(f,a,b) ((a)+((b)-(a))*(f))
+
+ /* Vector utilities */
+
+typedef vec_t vec2_t[2];
+typedef vec_t vec3_t[3];
+typedef vec_t vec4_t[4];
+
+#define V2Set(R,x,y) ((R)[0]=(x),\
+ (R)[1]=(y))
+#define V3Set(R,x,y,z) ((R)[0]=(x),\
+ (R)[1]=(y),\
+ (R)[2]=(z))
+#define V4Set(R,x,y,z,w) ((R)[0]=(x),\
+ (R)[1]=(y),\
+ (R)[2]=(z),\
+ (R)[3]=(w))
+
+#define V2Copy(R,A) ((R)[0]=(A)[0],\
+ (R)[1]=(A)[1])
+#define V3Copy(R,A) ((R)[0]=(A)[0],\
+ (R)[1]=(A)[1],\
+ (R)[2]=(A)[2])
+#define V4Copy(R,A) ((R)[0]=(A)[0],\
+ (R)[1]=(A)[1],\
+ (R)[2]=(A)[2],\
+ (R)[3]=(A)[3])
+
+#define V2Add(R,A,B) ((R)[0]=(A)[0]+(B)[0],\
+ (R)[1]=(A)[1]+(B)[1])
+#define V3Add(R,A,B) ((R)[0]=(A)[0]+(B)[0],\
+ (R)[1]=(A)[1]+(B)[1],\
+ (R)[2]=(A)[2]+(B)[2])
+#define V4Add(R,A,B) ((R)[0]=(A)[0]+(B)[0],\
+ (R)[1]=(A)[1]+(B)[1],\
+ (R)[2]=(A)[2]+(B)[2],\
+ (R)[3]=(A)[3]+(B)[3])
+
+#define V2Sub(R,A,B) ((R)[0]=(A)[0]-(B)[0],\
+ (R)[1]=(A)[1]-(B)[1])
+#define V3Sub(R,A,B) ((R)[0]=(A)[0]-(B)[0],\
+ (R)[1]=(A)[1]-(B)[1],\
+ (R)[2]=(A)[2]-(B)[2])
+#define V4Sub(R,A,B) ((R)[0]=(A)[0]-(B)[0],\
+ (R)[1]=(A)[1]-(B)[1],\
+ (R)[2]=(A)[2]-(B)[2],\
+ (R)[3]=(A)[3]-(B)[3])
+
+#define V2Mul(R,A,s) ((R)[0]=(A)[0]*(s),\
+ (R)[1]=(A)[1]*(s))
+#define V3Mul(R,A,s) ((R)[0]=(A)[0]*(s),\
+ (R)[1]=(A)[1]*(s),\
+ (R)[2]=(A)[2]*(s))
+#define V4Mul(R,A,s) ((R)[0]=(A)[0]*(s),\
+ (R)[1]=(A)[1]*(s),\
+ (R)[2]=(A)[2]*(s),\
+ (R)[3]=(A)[3]*(s))
+
+
+#define V2Mul2(R,A,s1,B,s2) ((R)[0]=(A)[0]*(s1)+(B)[0]*(s2),\
+ (R)[1]=(A)[1]*(s1)+(B)[1]*(s2))
+#define V3Mul2(R,A,s1,B,s2) ((R)[0]=(A)[0]*(s1)+(B)[0]*(s2),\
+ (R)[1]=(A)[1]*(s1)+(B)[1]*(s2),\
+ (R)[2]=(A)[2]*(s1)+(B)[2]*(s2))
+#define V4Mul2(R,A,s1,B,s2) ((R)[0]=(A)[0]*(s1)+(B)[0]*(s2),\
+ (R)[1]=(A)[1]*(s1)+(B)[1]*(s2),\
+ (R)[2]=(A)[2]*(s1)+(B)[2]*(s2),\
+ (R)[3]=(A)[3]*(s1)+(B)[3]*(s2))
+
+#define V2VMul(R,A,B) ((R)[0]=(A)[0]*(B)[0],\
+ (R)[1]=(A)[1]*(B)[1])
+#define V3VMul(R,A,B) ((R)[0]=(A)[0]*(B)[0],\
+ (R)[1]=(A)[1]*(B)[1],\
+ (R)[2]=(A)[2]*(B)[2])
+#define V4VMul(R,A,B) ((R)[0]=(A)[0]*(B)[0],\
+ (R)[1]=(A)[1]*(B)[1],\
+ (R)[2]=(A)[2]*(B)[2],\
+ (R)[3]=(A)[3]*(B)[3])
+
+#define V2MA(R,A,s,B) ((R)[0]=(A)[0]+(s)*(B)[0],\
+ (R)[1]=(A)[1]+(s)*(B)[1])
+#define V3MA(R,A,s,B) ((R)[0]=(A)[0]+(s)*(B)[0],\
+ (R)[1]=(A)[1]+(s)*(B)[1],\
+ (R)[2]=(A)[2]+(s)*(B)[2])
+#define V4MA(R,A,s,B) ((R)[0]=(A)[0]+(s)*(B)[0],\
+ (R)[1]=(A)[1]+(s)*(B)[1],\
+ (R)[2]=(A)[2]+(s)*(B)[2],\
+ (R)[3]=(A)[3]+(s)*(B)[3])
+
+#define V2VMA(R,A,S,B) ((R)[0]=(A)[0]+(S)[0]*(B)[0],\
+ (R)[1]=(A)[1]+(S)[1]*(B)[1])
+#define V3VMA(R,A,S,B) ((R)[0]=(A)[0]+(S)[0]*(B)[0],\
+ (R)[1]=(A)[1]+(S)[1]*(B)[1],\
+ (R)[2]=(A)[2]+(S)[2]*(B)[2])
+#define V4VMA(R,A,S,B) ((R)[0]=(A)[0]+(S)[0]*(B)[0],\
+ (R)[1]=(A)[1]+(S)[1]*(B)[1],\
+ (R)[2]=(A)[2]+(S)[2]*(B)[2],\
+ (R)[3]=(A)[3]+(S)[3]*(B)[3])
+
+#define V2MA2(R,A,s1,V1,s2,V2) ((R)[0]=(A)[0]+(s1)*(V1)[0]+(s2)*(V2)[0],\
+ (R)[1]=(A)[1]+(s1)*(V1)[1]+(s2)*(V2)[1])
+#define V3MA2(R,A,s1,V1,s2,V2) ((R)[0]=(A)[0]+(s1)*(V1)[0]+(s2)*(V2)[0],\
+ (R)[1]=(A)[1]+(s1)*(V1)[1]+(s2)*(V2)[1],\
+ (R)[2]=(A)[2]+(s1)*(V1)[2]+(s2)*(V2)[2])
+#define V4MA2(R,A,s1,V1,s2,V2) ((R)[0]=(A)[0]+(s1)*(V1)[0]+(s2)*(V2)[0],\
+ (R)[1]=(A)[1]+(s1)*(V1)[1]+(s2)*(V2)[1],\
+ (R)[2]=(A)[2]+(s1)*(V1)[2]+(s2)*(V2)[2],\
+ (R)[3]=(A)[3]+(s1)*(V1)[3]+(s2)*(V2)[3])
+
+#define V2Lerp(R,s,A,B) ((R)[0]=V1Lerp(s,(A)[0],(B)[0]),\
+ (R)[1]=V1Lerp(s,(A)[1],(B)[1]))
+#define V3Lerp(R,s,A,B) ((R)[0]=V1Lerp(s,(A)[0],(B)[0]),\
+ (R)[1]=V1Lerp(s,(A)[1],(B)[1]),\
+ (R)[2]=V1Lerp(s,(A)[2],(B)[2]))
+#define V4Lerp(R,s,A,B) ((R)[0]=V1Lerp(s,(A)[0],(B)[0]),\
+ (R)[1]=V1Lerp(s,(A)[1],(B)[1]),\
+ (R)[2]=V1Lerp(s,(A)[2],(B)[2]),\
+ (R)[3]=V1Lerp(s,(A)[3],(B)[3]))
+
+#define V2Dot(A,B) ((A)[0]*(B)[0]+\
+ (A)[1]*(B)[1])
+#define V3Dot(A,B) ((A)[0]*(B)[0]+\
+ (A)[1]*(B)[1]+\
+ (A)[2]*(B)[2])
+#define V4Dot(A,B) ((A)[0]*(B)[0]+\
+ (A)[1]*(B)[1]+\
+ (A)[2]*(B)[2]+\
+ (A)[3]*(B)[3])
+
+#define V3Cross(R,A,B) ((R)[0]=(A)[1]*(B)[2]-(A)[2]*(B)[1],\
+ (R)[1]=(A)[2]*(B)[0]-(A)[0]*(B)[2],\
+ (R)[2]=(A)[0]*(B)[1]-(A)[1]*(B)[0])
+
+#define V2Length(A) sqrt((A)[0]*(A)[0]+\
+ (A)[1]*(A)[1])
+#define V3Length(A) sqrt((A)[0]*(A)[0]+\
+ (A)[1]*(A)[1]+\
+ (A)[2]*(A)[2])
+#define V4Length(A) sqrt((A)[0]*(A)[0]+\
+ (A)[1]*(A)[1]+\
+ (A)[2]*(A)[2]+\
+ (A)[3]*(A)[3])
+
+//note: using the same vector for input and output will produce
+// bogus results
+#define V2ZSq(R,A) ((R)[0]=(A)[0]*(A)[0]-(A)[1]*(A)[1], \
+ (R)[1]=2.0*(A)[0]*(A)[1]);
+
+ /* Matrix utilities */
+
+typedef vec_t m3_t[9];
+
+#define M3Set(r,a,b,c,d,e,f,g,h,i) \
+((r)[0]=(a),(r)[1]=(b),(r)[2]=(c),\
+ (r)[3]=(d),(r)[4]=(e),(r)[5]=(f),\
+ (r)[6]=(g),(r)[7]=(h),(r)[8]=(i))
+
+#define M3Copy(r,a) \
+((r)[0]=(a)[0],(r)[1]=(a)[1],(r)[2]=(a)[2],\
+ (r)[3]=(a)[3],(r)[4]=(a)[4],(r)[5]=(a)[5],\
+ (r)[6]=(a)[6],(r)[7]=(a)[7],(r)[8]=(a)[8])
+
+#define M3RotX(r,a) \
+M3Set(r,1.0,0.0,0.0,0.0,cos(a),-sin(a),0.0,sin(a),cos(a))
+#define M3RotY(r,a) \
+M3Set(r,cos(a),0.0,sin(a),0.0,1.0,0.0,-sin(a),0.0,cos(a))
+#define M3RotZ(r,a) \
+M3Set(r,cos(a),-sin(a),0.0,sin(a),cos(a),0.0,0.0,0.0,1.0)
+
+#define M3Product(r,a,b) \
+((r)[0]=(a)[2]*(b)[6]+(a)[1]*(b)[3]+(a)[0]*(b)[0],\
+ (r)[1]=(a)[2]*(b)[7]+(a)[1]*(b)[4]+(a)[0]*(b)[1],\
+ (r)[2]=(a)[2]*(b)[8]+(a)[1]*(b)[5]+(a)[0]*(b)[2],\
+ (r)[3]=(a)[5]*(b)[6]+(a)[4]*(b)[3]+(a)[3]*(b)[0],\
+ (r)[4]=(a)[5]*(b)[7]+(a)[4]*(b)[4]+(a)[3]*(b)[1],\
+ (r)[5]=(a)[5]*(b)[8]+(a)[4]*(b)[5]+(a)[3]*(b)[2],\
+ (r)[6]=(a)[8]*(b)[6]+(a)[7]*(b)[3]+(a)[6]*(b)[0],\
+ (r)[7]=(a)[8]*(b)[7]+(a)[7]*(b)[4]+(a)[6]*(b)[1],\
+ (r)[8]=(a)[8]*(b)[8]+(a)[7]*(b)[5]+(a)[6]*(b)[2])
+
+ /* Color utilities */
+
+#define C_RED 0
+#define C_GREEN 1
+#define C_BLUE 2
+
+#define C_HUE 0
+#define C_SATURATION 1
+#define C_VALUE 2
+
+#define C_ALPHA 3
+
+ /* u_misc */
+
+#define VA_MAX 2048
+#define VA_BUFFERS 6
+
+ /* u_world */
+
+typedef uint8_t W_blockdata_t;
+
+enum
+{
+ BLOCK_NONE,
+ BLOCK_GROUND,
+ BLOCK_CONCRETE,
+ BLOCK_METAL,
+ BLOCK_MIRROR,
+ BLOCK_LIGHT,
+ BLOCK_BANNER
+};
+
+typedef struct W_otnode_s W_otnode_t;
+struct W_otnode_s
+{
+ W_blockdata_t data;
+ vec3_t aabb[ 2 ];
+
+ int i;
+ W_otnode_t *p;
+ W_otnode_t *n[ 8 ];
+};
+
+typedef struct
+{
+ bool_t inuse;
+ bool_t sun;
+ bool_t flashlight;
+ bool_t flashlight_enabled;
+
+ uint64_t timestamp;
+
+ vec3_t origin;
+ vec3_t direction;
+ vec3_t velocity;
+ vec3_t light;
+} W_light_t;
+
+#define MAX_DLIGHTS 16
+
+typedef struct
+{
+ W_otnode_t *otroot;
+ W_light_t lights[ MAX_DLIGHTS ];
+
+ vec3_t saved_origin;
+ vec3_t saved_angles;
+} W_world_t;
+
+ /* u_ray */
+
+
+typedef struct
+{
+ vec3_t org;
+ vec_t limit;
+ vec3_t dir;
+
+ int dsign[ 3 ]; // 0 or 1
+ int dsign2[ 3 ]; // -1 or +1
+ vec3_t dinv;
+ int dinvsign[ 3 ]; // 0 or 1
+ int otorder[ 8 ]; // octtree tracing order
+ vec3_t aabb[ 2 ];
+} ray_t;
+
+typedef struct
+{
+ bool_t startsolid;
+
+ vec_t dist;
+ vec3_t hit;
+ vec3_t normal;
+
+ W_blockdata_t data;
+
+ //used only internally
+ bool_t exit;
+} rtres_t;
+
+ /* player */
+
+typedef uint32_t G_time_t;
+
+typedef struct
+{
+ vec3_t origin;
+ vec3_t velocity;
+ vec3_t angles;
+ m3_t matrix;
+ m3_t flatMatrix;
+ vec3_t aabb[ 2 ];
+
+ G_time_t lastPhysicsTime;
+ bool_t onGround;
+
+ vec2_t cmd_move;
+ bool_t cmd_jump;
+ bool_t cmd_down;
+ bool_t cmd_sprint;
+ bool_t cmd_noclip;
+} G_player_t;
+
+// main.c
+extern const size_t _Material_count;
+
+// u_platform.c
+uint64_t U_Clock( void );
+uint64_t U_Microclock( void );
+uint64_t U_Nanoclock( void );
+
+// u_math.c
+vec_t V2Normalize( vec2_t v );
+vec_t V3Normalize( vec3_t v );
+vec_t V4Normalize( vec4_t v );
+void V3AnglesToMatrix( m3_t out, const vec3_t angles );
+void V3Reflect( vec3_t out, const vec3_t in, const vec3_t normal );
+void V3HSVtoRGB( vec3_t out, const vec3_t in );
+void V3RGBtoHSV( vec3_t out, const vec3_t in );
+
+// u_misc.c
+const char *va( const char *fmt, ... );
+
+// u_world.c
+void W_InitWorld( W_world_t *world );
+void W_DeleteWorld( W_world_t *world );
+
+W_otnode_t *W_NewOTNode( W_otnode_t *p, int i );
+void W_DeleteOTNode( W_otnode_t *n );
+
+W_otnode_t *W_Point( W_otnode_t *node, vec3_t const point );
+W_otnode_t *W_Trace( W_world_t *world, const W_otnode_t *ignore, const ray_t *ray, rtres_t *rt );
+
+bool_t W_Optimize( W_otnode_t *node );
+
+void W_CreateEmptyWorld( W_world_t *world );
+int W_Load( W_world_t *world, const char *file );
+void W_Save( const W_world_t *world, const char *file );
+
+void W_Dump( W_world_t *world );
+void W_Stats( const W_world_t *world, size_t *nodes, size_t *leaves );
+
+// u_ray.c
+bool_t U_PointInAABB( const vec3_t point, const vec3_t *aabb );
+bool_t U_PointInAABB2( const vec3_t point, const vec3_t *aabb );
+//org and dir can be NULL if ray already has them
+void U_BuildRay( const vec3_t org, const vec3_t dir, vec_t limit, ray_t *ray, rtres_t *rt );
+bool_t U_RT_Zplane( vec_t z, const ray_t *ray, rtres_t *rt );
+bool_t U_RT_AABB_Fast( const vec3_t const *aabb, const ray_t *ray, rtres_t *rt );
+bool_t U_RT_AABB( const vec3_t const *aabb, const ray_t *ray, rtres_t *rt );
+
+// player.c
+W_blockdata_t G_RemoveBlock( W_world_t *world, vec3_t vieworg, vec3_t viewdir, size_t targetDepth );
+bool_t G_PlaceBlock( W_world_t *world, vec3_t vieworg, vec3_t viewdir, W_blockdata_t block, size_t targetDepth );
+void G_RunPlayer( W_world_t *world, G_player_t *p );
+void G_RecolorBlock( W_world_t *world, vec3_t vieworg, vec3_t viewdir );
+W_otnode_t *G_BoxTrace( W_world_t *world, rtres_t *rt_best, const ray_t *ray, const vec3_t *aabb );
+void G_MovePlayer( W_world_t *world, G_player_t *p, vec_t delta );
+
+#endif //__COMMON_HEADER
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..71ae19d
--- /dev/null
+++ b/main.c
@@ -0,0 +1,1556 @@
+/*
+=======================================================================
+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"
+
+//#define NO_THREADING
+
+typedef struct
+{
+ size_t x0, y0, x1, y1;
+} R_tile_t;
+
+typedef struct
+{
+ bool_t done;
+
+ uint8_t *pixels;
+ size_t width, height;
+ int pitch;
+ uint32_t format, bpp;
+
+ size_t tileSize;
+ SDL_mutex *tilesLock;
+ R_tile_t *tiles;
+ size_t tileCount, tileNext;
+} R_frame_t;
+
+typedef struct
+{
+ bool_t shaded;
+ bool_t overlay; //crosshair
+ size_t samples;
+
+ bool_t phong;
+ bool_t phong_specular;
+ bool_t phong_shadows;
+
+ bool_t monteCarlo;
+ bool_t globalIllumination;
+
+ bool_t fresnel;
+} R_quality_t;
+
+typedef enum
+{
+ R_WORKER_QUIT,
+ R_WORKER_IDLE,
+ R_WORKER_RENDERING,
+ R_WORKER_DONE
+} R_workerstate_t;
+
+typedef struct
+{
+ vec3_t origin;
+ vec3_t angles;
+ float fov, projdist;
+ m3_t matrix;
+} R_view_t;
+
+typedef struct
+{
+ size_t id;
+ R_workerstate_t state;
+
+ R_frame_t *fb;
+ size_t x0, y0, x1, y1;
+ SDL_mutex *sync, *sync2;
+ R_quality_t quality;
+
+ size_t pixelsDone;
+
+ W_world_t *world;
+ R_view_t *view;
+} R_workerdata_t;
+
+typedef struct
+{
+ SDL_Thread *thread;
+ R_workerdata_t data;
+} R_worker_t;
+
+typedef struct
+{
+ size_t depth;
+} R_workerlocal_t;
+
+#define R_FRAMETIME_SAMPLES 8
+typedef struct
+{
+ bool_t ready;
+
+ struct
+ {
+ size_t resw, resh;
+ float supersampling;
+ int scaleQuality;
+ size_t workerCount;
+ size_t tileSize;
+ } cfg;
+
+ SDL_Window *window;
+ SDL_Renderer *renderer;
+ SDL_Texture *frameTexture;
+ R_frame_t frame;
+ R_quality_t quality;
+
+ //R_world_t world;
+ R_view_t view;
+
+ R_worker_t *workers;
+ size_t workerCount;
+
+ size_t frameCount;
+ size_t frameTimes[ R_FRAMETIME_SAMPLES ];
+ size_t nextFrameTime;
+ float fps;
+} R_state_t;
+
+typedef struct
+{
+ bool_t transparent;
+ vec3_t color;
+
+ vec_t mapScale;
+
+ //Phong
+ vec_t diffuseCoeff;
+ vec_t specularCoeff;
+ vec_t specularExponent;
+
+ //Snell, Fresnel
+ vec_t refractiveIndex;
+} R_material_t;
+
+static const R_material_t _Materials[ ] =
+{
+ { }, // BLOCK_NONE
+ // R G B uv dif spe exp ir
+ { false, { 0.7, 0.3, 0.0 }, 0.15, 0.9, 0.1, 1.0, 1.5 }, // BLOCK_GROUND
+ { false, { 0.8, 0.8, 0.8 }, 0.15, 0.8, 0.2, 1.5, 1.5 }, // BLOCK_CONCRETE
+
+ { false, { 1.0, 1.0, 1.0 }, 1.0, 0.3, 0.7, 12, 1.5 }, // BLOCK_METAL
+ { false, { 0.0, 1.0, 0.0 }, 1.0, 0.0, 1.0, INFINITY, 1.5 }, // BLOCK_MIRROR
+ { false, { 25.0, 25.0, 25.0 }, 1.0, 0.0, 0.0, 0.0, 0.0 }, // BLOCK_LIGHT
+
+ { false, { 0.7, 0.3, 0.0 }, 1.0, 0.8, 0.2, 3.0, 1.5 } // BLOCK_BANNER
+};
+const size_t _Material_count = sizeof( _Materials ) / sizeof( R_material_t );
+
+typedef struct
+{
+ SDL_Surface *diffuse;
+} R_mapset_t;
+
+R_mapset_t _Material_mapsets[ sizeof( _Materials ) / sizeof( R_material_t ) ];
+
+int R_Init( R_state_t *rs )
+{
+ size_t i;
+ R_mapset_t *mapset;
+
+ //TODO: error handling
+ IMG_Init( IMG_INIT_JPG | IMG_INIT_PNG );
+
+ memset( rs, 0, sizeof( R_state_t ) );
+ memset( &_Material_mapsets, 0, sizeof( _Material_mapsets ) );
+
+ for( i = 1; i < _Material_count; i++ )
+ {
+ mapset = _Material_mapsets + i;
+
+ mapset->diffuse = IMG_Load( va( "tex/%i.jpg", i ) );
+ if( !mapset->diffuse )
+ fprintf( stderr, "IMG_Load: %s\n", IMG_GetError( ) );
+ }
+
+ return 0;
+}
+
+int R_Configure( R_state_t *rs )
+{
+ rs->cfg.resw = 1280;
+ rs->cfg.resh = 720;
+ rs->cfg.supersampling = 0.2f;
+ rs->cfg.scaleQuality = 1;
+ rs->cfg.workerCount = 8;
+ rs->cfg.tileSize = 64;
+ rs->view.fov = 0.5 * M_PI;
+
+ rs->quality.shaded = false;
+ return 0;
+}
+
+int R_InitScreen(R_state_t *rs)
+{
+ //todo: error catching
+ printf("R_InitScreen: %zux%zu\n",rs->cfg.resw,rs->cfg.resh);
+
+ if( rs->frameTexture )
+ SDL_DestroyTexture(rs->frameTexture);
+ if( rs->window )
+ SDL_DestroyWindow(rs->window);
+ if( rs->renderer )
+ SDL_DestroyRenderer(rs->renderer);
+
+ rs->window = SDL_CreateWindow(
+ PROGRAM_FULLNAME, SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED,
+ rs->cfg.resw, rs->cfg.resh, SDL_WINDOW_OPENGL | SDL_WINDOW_INPUT_GRABBED
+ );
+ if( !rs->window )
+ {
+ printf( "SDL_CreateWindow: %s\n", SDL_GetError( ) );
+ abort( );
+ }
+
+ rs->renderer=SDL_CreateRenderer(
+ rs->window,-1, SDL_RENDERER_ACCELERATED
+ );
+ if( !rs->renderer )
+ {
+ printf( "SDL_CreateRenderer: %s\n", SDL_GetError( ) );
+ abort( );
+ }
+
+ rs->frame.width = rs->cfg.resw * rs->cfg.supersampling;
+ rs->frame.height = rs->cfg.resh * rs->cfg.supersampling;
+ rs->frameTexture=SDL_CreateTexture(
+ rs->renderer, SDL_PIXELFORMAT_BGR888, SDL_TEXTUREACCESS_STREAMING,
+ rs->frame.width, rs->frame.height
+ );
+ rs->frame.tileSize = rs->cfg.tileSize;
+
+ {
+ int w, h;
+
+ SDL_QueryTexture(
+ rs->frameTexture, &rs->frame.format, NULL, &w, &h );
+ rs->frame.width = w;
+ rs->frame.height = h;
+ }
+
+ if( rs->frame.format != SDL_PIXELFORMAT_BGR888 )
+ printf( "R_InitScreen: wrong pixel format %i\n", rs->frame.format );
+
+ rs->frame.bpp = 4;
+ rs->frame.pitch = rs->frame.width * rs->frame.bpp;
+
+ rs->frame.tilesLock = SDL_CreateMutex( );
+
+ rs->ready = true;
+ return 0;
+}
+
+
+//R_InitWorkers: set up the configured worker count
+int R_Worker( R_workerdata_t *w );
+int R_InitWorkers( R_state_t *rs )
+{
+#ifndef NO_THREADING
+ size_t i;
+ R_worker_t *w;
+
+ printf( "R_InitWorkers: %zu thread%s\n",
+ rs->cfg.workerCount, ( rs->cfg.workerCount == 1 ? "" : "s" ) );
+
+ //nothing to do
+ if( rs->cfg.workerCount == rs->workerCount )
+ return 0;
+
+ //remove some workers
+ if( rs->cfg.workerCount < rs->workerCount )
+ {
+ for( i = rs->cfg.workerCount; i < rs->workerCount; i++ )
+ {
+ w = rs->workers + i;
+ w->data.state = R_WORKER_QUIT;
+ SDL_UnlockMutex( w->data.sync );
+ SDL_WaitThread( w->thread, NULL );
+ }
+ }
+
+ rs->workers = realloc(
+ rs->workers,
+ rs->cfg.workerCount * sizeof( R_worker_t )
+ );
+
+ //allocate more workers
+ if( rs->cfg.workerCount > rs->workerCount )
+ {
+ for( i = rs->workerCount; i < rs->cfg.workerCount; i++ )
+ {
+ w = rs->workers + i;
+ w->data.id = i;
+ w->data.state = R_WORKER_IDLE;
+ w->data.sync = SDL_CreateMutex();
+ SDL_LockMutex( w->data.sync );
+ w->data.sync2 = SDL_CreateMutex();
+ w->thread = SDL_CreateThread(
+ ( SDL_ThreadFunction )R_Worker,
+ va( "render worker %i", i ),
+ &w->data
+ );
+ }
+ }
+
+ rs->workerCount = rs->cfg.workerCount;
+
+ return 0;
+#endif
+}
+
+void R_GenerateTiles( R_frame_t *fb )
+{
+/*
+ R_tile_t *t;
+ size_t x, y, th, tv;
+
+ th = fb->width / fb->tileSize;
+ if( fb->width % fb->tileSize )
+ th++;
+ tv = fb->height / fb->tileSize;
+ if( fb->height % fb->tileSize )
+ tv++;
+
+ fb->tileCount = th * tv;
+ fb->tiles = realloc( fb->tiles, sizeof( R_tile_t ) * fb->tileCount );
+
+ for( t = fb->tiles, y = 0; y < tv; y++ )
+ for( x = 0; x < th; x++, t++ )
+ {
+ t->x0 = x * fb->tileSize;
+ t->y0 = y * fb->tileSize;
+ t->x1 = ( x + 1 ) * fb->tileSize - 1;
+ if( t->x1 > fb->width - 1 )
+ t->x1 = fb->width - 1;
+ t->y1 = ( y + 1 ) * fb->tileSize - 1;
+ if( t->y1 > fb->height - 1 )
+ t->y1 = fb->height - 1;
+ }
+
+ fb->tileNext = 0;
+*/
+
+ R_tile_t *t;
+ size_t y;
+
+ fb->tileCount = fb->height;
+ fb->tiles = realloc( fb->tiles, sizeof( R_tile_t ) * fb->tileCount );
+
+ for( t = fb->tiles, y = 0; y < fb->height; y++, t++ )
+ {
+ t->x0 = 0;
+ t->x1 = fb->width - 1;
+ t->y0 = y;
+ t->y1 = y;
+ }
+
+ fb->tileNext = 0;
+};
+
+inline bool_t R_Worker_FindTile( R_workerdata_t *w )
+{
+ R_tile_t *t;
+
+ SDL_LockMutex( w->fb->tilesLock );
+
+ if( w->fb->tileNext >= w->fb->tileCount )
+ {
+ SDL_UnlockMutex( w->fb->tilesLock );
+ return false;
+ }
+
+ t = w->fb->tiles + w->fb->tileNext++;
+
+ SDL_UnlockMutex( w->fb->tilesLock );
+
+ w->x0 = t->x0;
+ w->y0 = t->y0;
+ w->x1 = t->x1;
+ w->y1 = t->y1;
+
+ return true;
+}
+
+W_world_t world;
+
+
+static void R_Sky( vec3_t out, const vec3_t dir, const R_quality_t *quality )
+{
+ vec_t dot;
+
+ dot = V3Dot( dir, world.lights[ 0 ].direction );
+
+ //sun
+ if( dot > 0.9999 )
+ {
+ V3Set( out, 3, 3, 3 );
+ return;
+ }
+
+ if( !quality->globalIllumination )
+ {
+ V3Set( out, 0, 0, 0 );
+ return;
+ }
+
+ if( dot < 0 )
+ dot = 0;
+
+ dot *= dot * dot * dot * 1.6;
+ dot += 0.4;
+
+ V3Set( out, dot, dot, dot );
+}
+
+static void R_MapTexture( vec3_t out, const vec3_t point, const vec3_t normal, vec_t scale, const SDL_Surface *surf )
+{
+ vec_t u = 0.0, v = 0.0;
+ size_t x, y;
+
+ if( surf == _Material_mapsets[ BLOCK_BANNER ].diffuse )
+ {
+ u = ( point[ 1 ] + 9.0 ) / 16.0;
+ v = ( point[ 2 ] - 24.0 ) / 16.0;
+ }
+ else
+ {
+ if( normal[ 2 ] == -1.0 || normal[ 2 ] == 1.0 )
+ {
+ u = point[ 0 ];
+ v = point[ 1 ];
+ }
+ else if( normal[ 0 ] == -1.0 || normal[ 0 ] == 1.0 )
+ {
+ u = point[ 1 ];
+ v = point[ 2 ];
+ }
+ else if( normal[ 1 ] == -1.0 || normal[ 1 ] == 1.0 )
+ {
+ u = point[ 2 ];
+ v = point[ 0 ];
+ }
+ }
+
+ //FIXME: lame negative number handling
+ u = fmod( u + 500, 1.0 / scale ) * scale;
+ v = fmod( v + 500, 1.0 / scale ) * scale;
+
+ x = u * surf->w;
+ y = v * surf->h;
+
+ x %= surf->w;
+ y %= surf->h;
+ //*(uint32_t*)(w->fb->pixels+y*w->fb->pitch+x*4)=r_|(g_<<8)|(b_<<16);
+ out[ 0 ] = 0.00390625 * *(uint8_t*)(surf->pixels + y * surf->pitch + x * 3 );
+ out[ 1 ] = 0.00390625 * *(uint8_t*)(surf->pixels + y * surf->pitch + x * 3 + 1 );
+ out[ 2 ] = 0.00390625 * *(uint8_t*)(surf->pixels + y * surf->pitch + x * 3 + 2 );
+}
+
+inline static void R_Phong( vec3_t out, const vec3_t point, const vec3_t viewdir, const vec3_t normal, const W_otnode_t *ignore, const R_material_t *mat, const R_quality_t *quality )
+{
+ int i;
+ ray_t shray;
+ rtres_t shrt;
+ vec_t dot, dist, lightMod;
+ vec3_t pass;
+ bool_t shadowed;
+
+ V3Set( out, 0, 0, 0 );
+
+ //iterate through all dynamic lights
+ for( i = 0; i < MAX_DLIGHTS; i++ )
+ {
+ W_light_t *light = world.lights + i;
+
+ V3Set( pass, 0, 0, 0 );
+
+ if( !light->inuse )
+ continue;
+
+ V3Copy( shray.org, point );
+
+ if( !light->sun )
+ {
+ V3Sub( shray.dir, light->origin, point );
+ dist = V3Normalize( shray.dir );
+ }
+ else
+ {
+ V3Copy( shray.dir, light->direction );
+ dist = INFINITY;
+ }
+
+ if( light->flashlight )
+ {
+ if( !light->flashlight_enabled )
+ continue;
+
+ dot = V3Dot( light->direction, shray.dir );
+ if( dot > -0.6 )
+ continue;
+
+ dot = -dot;
+ dot -= 0.6;
+ dot /= 0.4;
+ lightMod = sqrt( dot );
+ }
+ else
+ lightMod = 1.0;
+
+ dot = V3Dot( normal, shray.dir );
+
+ if( dot < 0 )
+ continue;
+
+ shadowed = false;
+
+ if( quality->phong_shadows )
+ {
+ U_BuildRay( NULL, NULL, dist, &shray, &shrt );
+ shadowed = ( W_Trace( &world, ignore, &shray, &shrt ) != NULL );
+ }
+
+ if( shadowed )
+ continue;
+
+ if( light->sun )
+ V3Mul( pass, light->light, dot );
+ else
+ V3Mul( pass, light->light, dot / dist / dist * lightMod );
+
+ V3Mul( pass, pass, mat->diffuseCoeff );
+
+ if( mat->specularCoeff > 0 )
+ {
+ vec_t specular;
+ vec3_t ref;
+
+ V3Reflect( ref, shray.dir, normal );
+
+ dot = V3Dot( ref, viewdir );
+
+ if( dot > 0 )
+ {
+ specular = pow( dot, mat->specularExponent ) * mat->specularCoeff;
+ V3MA( pass, pass, specular, light->light );
+ }
+ }
+
+ V3Add( out, out, pass );
+ }
+}
+
+#define R_RVP_SIZE 123456
+
+typedef struct
+{
+ vec3_t table[ R_RVP_SIZE ];
+ size_t i;
+} R_randvecpool_t;
+
+void R_GenerateRVP( R_randvecpool_t *rvp )
+{
+ size_t i;
+ vec_t p, y;
+ m3_t M, My, Mz;
+
+ for( i = 0; i < R_RVP_SIZE; i++ )
+ {
+ p = ( (vec_t)rand( ) / RAND_MAX ) * 2.0 * M_PI;
+ y = ( (vec_t)rand( ) / RAND_MAX ) * 2.0 * M_PI;
+ M3RotY( My, p );
+ M3RotZ( Mz, y );
+ M3Product( M, My, Mz );
+ V3Copy( rvp->table[ i ], M );
+ }
+}
+
+void R_v3rand( vec3_t out, R_randvecpool_t *rvp, const vec3_t normal )
+{
+ rvp->i++;
+ rvp->i %= R_RVP_SIZE;
+
+ V3Copy( out, rvp->table[ rvp->i ] );
+
+ if( !normal )
+ return;
+
+ if( V1Epscmp( normal[ 0 ], 1, 1e-5 ) )
+ out[ 0 ] = fabs( out[ 0 ] );
+ else if( V1Epscmp( normal[ 0 ], -1, 1e-5 ) )
+ out[ 0 ] = -fabs( out[ 0 ] );
+ else if( V1Epscmp( normal[ 1 ], 1, 1e-5 ) )
+ out[ 1 ] = fabs( out[ 1 ] );
+ else if( V1Epscmp( normal[ 1 ], -1, 1e-5 ) )
+ out[ 1 ] = -fabs( out[ 1 ] );
+ else if( V1Epscmp( normal[ 2 ], 1, 1e-5 ) )
+ out[ 2 ] = fabs( out[ 2 ] );
+ else if( V1Epscmp( normal[ 2 ], -1, 1e-5 ) )
+ out[ 2 ] = -fabs( out[ 2 ] );
+}
+
+void R_PT_Trace_R( vec3_t out, vec3_t in_mask, const vec3_t org, const vec3_t dir, const W_otnode_t *ignore, const R_quality_t *quality, R_randvecpool_t *rvp, size_t *depth )
+{
+ vec3_t mask;
+ W_otnode_t *node;
+ ray_t ray;
+ rtres_t rt;
+ const R_material_t *mat;
+ bool_t reflection = false;
+ const R_mapset_t *mapset;
+
+ (*depth)++;
+
+ U_BuildRay( org, dir, INFINITY, &ray, &rt );
+ node = W_Trace( &world, ignore, &ray, &rt );
+
+ if( !node )
+ {
+ vec3_t sky;
+
+ R_Sky( sky, ray.dir, quality );
+ V3VMA( out, out, in_mask, sky );
+ goto out;
+ }
+
+ V3MA( rt.hit, ray.org, rt.dist, ray.dir );
+ mat = _Materials + node->data;
+ mapset = _Material_mapsets + node->data;
+
+ if( node->data == BLOCK_LIGHT )
+ {
+ V3VMA( out, out, in_mask, mat->color );
+
+ goto out;
+ }
+
+ if( mapset->diffuse )
+ {
+ vec3_t color;
+ R_MapTexture( color, rt.hit, rt.normal, mat->mapScale, mapset->diffuse );
+ V3VMul( mask, in_mask, color );
+ }
+ else
+ V3VMul( mask, in_mask, mat->color );
+
+ //Phong shading
+ if( !mat->transparent )
+ {
+ if( quality->phong )
+ {
+ vec3_t phong;
+ R_Phong( phong, rt.hit, ray.dir, rt.normal, node, mat, quality );
+ V3VMA( out, out, mask, phong );
+ }
+ }
+
+ if( (*depth) > 3 )
+ goto out;
+
+ reflection = false;
+
+ if( mat->specularExponent == INFINITY )
+ reflection = true;
+ else if( quality->monteCarlo )
+ {
+ vec_t R;
+ R = (vec_t)rand() / RAND_MAX;
+ reflection = ( R < mat->specularCoeff );
+ }
+
+ if( !reflection )
+ {
+ //global illumination
+ if( !mat->transparent )
+ {
+ if( quality->monteCarlo && quality->globalIllumination )
+ {
+ vec3_t r;
+ vec3_t mask_gi;
+
+ R_v3rand( r, rvp, rt.normal );
+
+ V3Mul( mask_gi, mask, mat->diffuseCoeff );
+
+ R_PT_Trace_R( out, mask_gi, rt.hit, r, node, quality, rvp, depth );
+ }
+ }
+ //pass through (DOES NOT WORK)
+ /*else
+ {
+ vec_t R, C, B;
+ vec3_t rfa;
+
+ ray_t rfaray;
+ rtres_t rfart;
+
+ R = 1.0 / mat->refractiveIndex;
+ C = -V3Dot( rt.normal, ray.dir );
+
+ B = R * C - sqrt( 1 - R * R * ( 1 - C * C ) );
+
+ V3Mul2( rfa, ray.dir, R, rt.normal, B );
+
+ V3MA( rfaray.org, rt.hit, 150, rfa );
+ V3Mul( rfaray.dir, rfa, -1 );
+
+ U_BuildRay( NULL, NULL, INFINITY, &rfaray, &rfart );
+
+ if( !U_RT_AABB( (const vec3_t*)node->aabb, &ray, &rt ) )
+ printf( "wtf\n" );
+
+ V3MA( rfart.hit, rfaray.org, rfart.dist, rfaray.dir );
+
+ R_PT_Trace_R( out, mask, rfart.hit, rfa, node, quality, rvp, depth );
+
+ goto out;
+ }*/
+ }
+ else
+ {
+ vec3_t ref;
+
+ V3Reflect( ref, ray.dir, rt.normal );
+
+ if( mat->specularExponent == INFINITY )
+ {
+ V3VMul( mask, mask, mat->color );
+ R_PT_Trace_R( out, mask, rt.hit, ref, node, quality, rvp, depth );
+ }
+ else if( quality->monteCarlo )
+ {
+ vec3_t rnd;
+
+ R_v3rand( rnd, rvp, NULL );
+ V3MA( ref, ref, 1.0 / mat->specularExponent, rnd );
+ V3Normalize( ref );
+
+ if( V3Dot( ref, rt.normal ) < 0 )
+ goto out;
+
+ V3VMul( mask, mask, mat->color );
+
+ R_PT_Trace_R( out, mask, rt.hit, ref, node, quality, rvp, depth );
+ }
+ }
+
+out:
+ (*depth)--;
+}
+
+void R_PT_Trace( vec3_t out, const ray_t *ray, const R_quality_t *quality, R_randvecpool_t *rvp )
+{
+ vec3_t mask;
+ size_t i, depth;
+
+ V3Set( out, 0, 0, 0 );
+ V3Set( mask, 1, 1, 1 );
+ depth = 0;
+
+ for( i = 0; i < quality->samples; i++ )
+ R_PT_Trace_R( out, mask, ray->org, ray->dir, NULL, quality, rvp, &depth );
+
+ V3Mul( out, out, 1.0 / quality->samples );
+
+ if( quality->phong && quality->globalIllumination )
+ V3Mul( out, out, 0.5 );
+}
+
+bool_t R_Lightbulbs( vec3_t out, const ray_t *ray )
+{
+ size_t i;
+ W_light_t *light;
+ vec3_t delta;
+ vec_t dist;
+
+ for( i = 0; i < MAX_DLIGHTS; i++ )
+ {
+ light = world.lights + i;
+
+ if( !light->inuse || light->sun || light->flashlight )
+ continue;
+
+ V3Sub( delta, light->origin, ray->org );
+ dist = V3Normalize( delta );
+
+ if( V3Dot( delta, ray->dir ) > ( 1 - 1 / ( dist * 500 ) ) )
+ {
+ V3Copy( out, light->light );
+ return true;
+ }
+ }
+ return false;
+}
+
+void R_SimpleTrace( vec3_t out, const ray_t *ray )
+{
+ rtres_t rt;
+
+ memset( &rt, 0, sizeof( rtres_t ) );
+
+ if( W_Trace( &world, NULL, ray, &rt ) )
+ V3Set( out, 4.0 / rt.dist, 0, 0 );
+ else
+ V3Set( out, 0, 0, 1 );
+}
+
+int R_Worker( R_workerdata_t *w )
+{
+ size_t x, y;
+ R_randvecpool_t rvp;
+
+#ifdef NO_THREADING
+ {
+ static int init = 0;
+ if( !init )
+ R_GenerateRVP( &rvp );
+ init = 1;
+ }
+#else
+ R_GenerateRVP( &rvp );
+#endif
+
+#ifndef NO_THREADING
+ while( 1 )
+ {
+ if( w->state == R_WORKER_IDLE )
+ {
+ //lock the sync2 to indicate that work is not complete (since the
+ //worker hasn't even started computing)
+ SDL_LockMutex( w->sync2 );
+
+ //sleep until the main thread wakes the worker up by releasing the
+ //sync mutex
+ SDL_LockMutex( w->sync );
+ SDL_UnlockMutex( w->sync );
+ }
+ else if( w->state==R_WORKER_QUIT )
+ break;
+ else if( w->state==R_WORKER_RENDERING )
+ {
+#endif
+ ray_t ray;
+ vec3_t color;
+ uint8_t r_, g_, b_;
+ float _x,_y;
+ float _x_min;
+ float d_x, d_y;
+ int cx, cy;
+
+ w->pixelsDone = 0;
+
+ cx = w->fb->width / 2;
+ cy = w->fb->height / 2;
+
+ V3Copy( ray.org, w->view->origin );
+
+ d_x = 2.0 / w->fb->height;
+ d_y = 2.0 / w->fb->height;
+
+ while( R_Worker_FindTile( w ) )
+ {
+ _x = _x_min = (float)( (int)w->x0 + ( (int)w->fb->height - (int)w->fb->width ) / 2 ) / w->fb->height * 2.0 - 1.0;
+ _y = (float)w->y0 / w->fb->height * 2.0 - 1.0;
+
+ for( y = w->y0; y <= w->y1; y++, _x = _x_min, _y += d_y )
+ for( x = w->x0; x <= w->x1; x++, _x += d_x )
+ {
+ //GETRIDOFITLATER: crosshair
+ if( w->quality.overlay )
+ {
+ int dx, dy;
+
+ dx = abs( cx - x );
+ dy = abs( cy - y );
+
+ if( dx + dy <= 1 )
+ {
+ *(uint32_t*)(w->fb->pixels+y*w->fb->pitch+x*4)=0xFFFFFFFF;
+ w->pixelsDone++;
+ continue;
+ }
+ }
+
+ V3Mul( ray.dir, w->view->matrix, w->view->projdist );
+
+ V3MA2( ray.dir, ray.dir,
+ _x, w->view->matrix + 3,
+ _y, w->view->matrix + 6 );
+
+ V3Normalize( ray.dir );
+
+ U_BuildRay( NULL, NULL, INFINITY, &ray, NULL );
+
+ if( !R_Lightbulbs( color, &ray ) )
+ {
+ if( w->quality.shaded )
+ {
+ R_PT_Trace( color, &ray, &w->quality, &rvp );
+ }
+ else
+ R_SimpleTrace( color, &ray );
+ }
+
+ r_ = (uint8_t)( V1Clamp( color[ 0 ], 0.0, 1.0) * 255.0 );
+ g_ = (uint8_t)( V1Clamp( color[ 1 ], 0.0, 1.0) * 255.0 );
+ b_ = (uint8_t)( V1Clamp( color[ 2 ], 0.0, 1.0) * 255.0 );
+ *(uint32_t*)(w->fb->pixels+y*w->fb->pitch+x*4)=r_|(g_<<8)|(b_<<16);
+
+ w->pixelsDone++;
+ }
+ }
+
+#ifndef NO_THREADING
+
+ w->state = R_WORKER_DONE;
+
+ //work is done, unlock sync2 so the main thread can synchronize
+ //and display the frame
+ SDL_UnlockMutex( w->sync2 );
+ }
+ else if( w->state == R_WORKER_DONE )
+ SDL_Delay( 0 ); //FIXME: get rid of this
+ }
+
+ SDL_DestroyMutex( w->sync );
+ SDL_DestroyMutex( w->sync2 );
+
+#endif
+
+ return 0;
+}
+
+void R_CalculateView( R_view_t *view )
+{
+ V3AnglesToMatrix( view->matrix, view->angles );
+ view->projdist = 1.0 / ( tan ( 0.5 * view->fov ) );
+}
+
+void R_ViewFromPlayer( R_state_t *rs, const G_player_t *p )
+{
+ V3Copy( rs->view.origin, p->origin );
+ V3Copy( rs->view.angles, p->angles );
+ M3Copy( rs->view.matrix, p->matrix );
+}
+
+void R_Render( R_state_t *rs )
+{
+ uint64_t t_begin, t_delta;
+ size_t i;
+ R_workerdata_t *w;
+
+ //start measuring render time
+ t_begin = U_Microclock();
+
+ //reset tiles
+ rs->frame.tileNext = 0;
+
+ //calculate the view matrix
+ R_CalculateView( &rs->view );
+
+ SDL_LockTexture(
+ rs->frameTexture, NULL,
+ (void**)&rs->frame.pixels,
+ &rs->frame.pitch
+ );
+
+#ifndef NO_THREADING
+ //update & resume all workers
+ for( i = 0; i < rs->workerCount; i++ )
+ {
+ w = &rs->workers[ i ].data;
+
+ w->fb = &rs->frame;
+ w->view = &rs->view;
+ memcpy( &w->quality, &rs->quality, sizeof( R_quality_t ) );
+
+ //start the thread by changing the state to RENDERING and unlocking
+ //the sync mutex
+ w->state = R_WORKER_RENDERING;
+ SDL_UnlockMutex( w->sync );
+ }
+
+ //wait for all workers
+ for( i = 0; i < rs->workerCount; i++ )
+ {
+ w = &rs->workers[ i ].data;
+ //wait for the thread to finish computing
+ SDL_LockMutex( w->sync2 );
+ SDL_UnlockMutex( w->sync2 );
+ //lock the sync mutex THEN change the worker's state back to idle
+ SDL_LockMutex( w->sync );
+ w->state = R_WORKER_IDLE;
+ }
+#else
+ {
+ /* size_t id;
+ R_workerstate_t state;
+
+ R_frame_t *fb;
+ size_t x0, y0, x1, y1;
+ SDL_mutex *sync, *sync2;
+ R_quality_t quality;
+
+ size_t pixelsDone;
+
+ W_world_t *world;
+ R_view_t *view;*/
+ R_workerdata_t worker;
+ worker.fb = &rs->frame;
+ worker.quality = rs->quality;
+ worker.world = &world;
+ worker.view = &rs->view;
+
+ R_Worker( &worker );
+ }
+#endif
+
+ //display the render result
+ SDL_UnlockTexture( rs->frameTexture );
+ SDL_RenderCopy( rs->renderer, rs->frameTexture, NULL, NULL );
+ SDL_RenderPresent( rs->renderer );
+
+ //finish measuring render time
+ t_delta = U_Microclock() - t_begin;
+ rs->frameCount++;
+ rs->frameTimes[ rs->nextFrameTime++ ] = t_delta;
+ rs->nextFrameTime %= R_FRAMETIME_SAMPLES;
+ rs->fps = 0.0f;
+ if(rs->frameCount >= R_FRAMETIME_SAMPLES)
+ {
+ for( i = 0; i < R_FRAMETIME_SAMPLES; i++ )
+ rs->fps += 1.0e+6 / rs->frameTimes[ i ];
+ rs->fps /= R_FRAMETIME_SAMPLES;
+ }
+}
+
+void R_OfflineRender( R_state_t *rs )
+{
+#ifndef NO_THREADING
+ uint64_t t_begin, t_delta;
+ size_t i, totalPixels;
+ R_workerdata_t *w;
+ R_frame_t frame;
+ R_quality_t offq; //TODO: move out of here
+ SDL_Surface *image;
+
+ t_begin = U_Microclock();
+
+ R_CalculateView( &rs->view );
+
+ frame.width = 1280;
+ frame.height = 720;
+ frame.tileSize = 64;
+
+ totalPixels = frame.width * frame.height;
+
+ memcpy( &offq, &rs->quality, sizeof( R_quality_t ) );
+ offq.overlay = false;
+ if( offq.monteCarlo )
+ offq.samples *= 10;
+
+ R_GenerateTiles( &frame );
+
+ frame.tilesLock = SDL_CreateMutex( );
+
+ image = SDL_CreateRGBSurface(
+ SDL_SWSURFACE, frame.width, frame.height, 32,
+ 0x000000ff, 0x0000ff00, 0x00ff0000, 0xff000000
+ );
+
+ SDL_LockSurface( image );
+
+ frame.pixels = image->pixels;
+ frame.pitch = image->pitch;
+
+ //resume all workers
+ for( i = 0; i < rs->workerCount; i++ )
+ {
+ w=&rs->workers[i].data;
+
+ w->fb = &frame;
+ w->view = &rs->view;
+ memcpy( &w->quality, &offq, sizeof( R_quality_t ) );
+
+ //start the thread by changing the state to RENDERING and unlocking
+ //the sync mutex
+ w->state = R_WORKER_RENDERING;
+ SDL_UnlockMutex( w->sync );
+ }
+
+ printf( "\nRendering: ---%%") ;
+
+ while( 1 )
+ {
+ size_t i, pixelsDone = 0;
+
+ for( i = 0; i < rs->workerCount; i++ )
+ pixelsDone += rs->workers[ i ].data.pixelsDone;
+
+ printf( "\b\b\b\b%3i%%", (int)( 100.0 * (float)pixelsDone / totalPixels ) );
+ fflush( stdout );
+
+ if( pixelsDone == totalPixels )
+ break;
+
+ SDL_Delay( 50 );
+ }
+
+ //wait for all workers
+ for( i = 0; i < rs->workerCount; i++ )
+ {
+ w = &rs->workers[ i ].data;
+ //wait for the thread to finish computing
+ SDL_LockMutex( w->sync2 );
+ SDL_UnlockMutex( w->sync2 );
+ //lock the sync mutex THEN change the worker's state back to idle
+ SDL_LockMutex( w->sync );
+ w->state = R_WORKER_IDLE;
+ }
+
+ //display the render result
+ SDL_UnlockSurface( image );
+
+ //finish measuring render time
+ t_delta = U_Microclock() - t_begin;
+ printf("\b\b\b\b100%% (%.1fs)\n", (float)t_delta * 1.0e-6 );
+
+ SDL_SaveBMP( image, "offline.bmp" );
+
+ SDL_DestroyMutex( frame.tilesLock );
+ free( frame.tiles );
+ SDL_FreeSurface( image );
+#endif
+}
+
+void R_Quit( R_state_t *rs )
+{
+ size_t i;
+
+ //workers
+ rs->cfg.workerCount = 0;
+ R_InitWorkers( rs );
+
+ //tiles
+ free( rs->frame.tiles );
+ SDL_DestroyMutex( rs->frame.tilesLock );
+
+ //mapsets
+ for( i = 1; i < _Material_count; i++ )
+ SDL_FreeSurface( _Material_mapsets[ i ].diffuse );
+
+
+ //SDL stuff
+ SDL_DestroyTexture( rs->frameTexture );
+ SDL_DestroyRenderer( rs->renderer );
+ SDL_DestroyWindow( rs->window );
+
+ rs->ready = false;
+}
+
+
+ G_player_t player;
+ R_state_t rs;
+
+int main( int argc, char **argv )
+{
+ SDL_Event event;
+ W_blockdata_t blockSelection = BLOCK_CONCRETE;
+ bool_t grabbed = true;
+ SDL_Thread *evthd;
+ uint64_t phystime = 0;
+
+ R_Init( &rs );
+ R_Configure( &rs );
+ R_InitScreen( &rs );
+ R_InitWorkers( &rs );
+ R_GenerateTiles( &rs.frame );
+ rs.quality.overlay = true;
+
+ SDL_SetRelativeMouseMode( SDL_TRUE );
+
+
+ W_InitWorld( &world );
+
+ world.otroot = W_NewOTNode( NULL, 0 );
+ V3Set( world.otroot->aabb[ 0 ], -32, -32, -32 );
+ V3Set( world.otroot->aabb[ 1 ], 32, 32, 32 );
+
+ if( W_Load( &world, "world" ) )
+ {
+ W_DeleteWorld( &world );
+ W_CreateEmptyWorld( &world );
+ }
+
+ V3Copy( player.origin, world.saved_origin );
+ V3Copy( player.angles, world.saved_angles );
+ V3Set( player.velocity, 0, 0, 0 );
+ player.lastPhysicsTime = U_Clock( );
+
+ V3Set( player.aabb[ 0 ], -0.4, -0.4, -1 );
+ V3Set( player.aabb[ 1 ], 0.4, 0.4, 0.5 );
+
+ world.lights[ 0 ].inuse =
+ world.lights[ 0 ].sun = true;
+ V3Set( world.lights[ 0 ].light, 1.6, 1.6, 1.6 );
+
+ world.lights[ 1 ].inuse =
+ world.lights[ 1 ].flashlight = true;
+
+ phystime = U_Clock( );
+
+ while( true )
+ {
+ while( SDL_PollEvent( &event ) )
+ switch( event.type )
+ {
+ case SDL_QUIT:
+ goto main_loop_break;
+ case SDL_KEYDOWN:
+ {
+ switch( event.key.keysym.sym )
+ {
+ case SDLK_F1:
+ grabbed ^= true;
+ SDL_SetRelativeMouseMode( ( grabbed ? SDL_TRUE : SDL_FALSE ) );
+ break;
+
+ case SDLK_F4:
+ V3Set( player.origin, 0, 0, -10 );
+ V3Set( player.angles, 0, 0, 0 );
+ V3Set( player.velocity, 0, 0, 0 );
+ break;
+
+ case SDLK_f:
+ world.lights[ 1 ].flashlight_enabled ^= 1;
+ break;
+
+ case SDLK_m:
+ G_RecolorBlock( &world, rs.view.origin, rs.view.matrix );
+ break;
+
+ case SDLK_o:
+ if( world.otroot )
+ W_Optimize( world.otroot );
+ break;
+
+ case SDLK_p:
+ W_Dump( &world );
+ break;
+
+ //throw a light
+ case SDLK_q:
+ {
+ int i;
+ W_light_t *light;
+
+ for( i = 0; i < MAX_DLIGHTS; i++ )
+ {
+ light = world.lights + i;
+
+ if( light->inuse )
+ continue;
+
+ light->timestamp = U_Clock( );
+ light->inuse = true;
+ light->sun = false;
+
+ V3Copy( light->origin, rs.view.origin );
+ V3Mul( light->velocity, rs.view.matrix, 3.0 );
+
+ switch( rand( ) % 6 )
+ {
+ case 0: V3Set( light->light, 1, 0, 0 ); break;
+ case 1: V3Set( light->light, 1, 1, 0 ); break;
+ case 2: V3Set( light->light, 0, 1, 0 ); break;
+ case 3: V3Set( light->light, 0, 1, 1 ); break;
+ case 4: V3Set( light->light, 0, 0, 1 ); break;
+ case 5: V3Set( light->light, 1, 0, 1 ); break;
+ }
+ V3Mul( light->light, light->light, 10 );
+
+ break;
+ }
+ }
+ break;
+
+ case SDLK_F11:
+ R_OfflineRender( &rs );
+ break;
+
+ //not shaded
+ case SDLK_1:
+ rs.quality.shaded = false;
+ break;
+
+ //Phong
+ case SDLK_2:
+ rs.quality.shaded = true;
+ rs.quality.samples = 1;
+ rs.quality.phong = true;
+ rs.quality.phong_shadows = false;
+ rs.quality.monteCarlo = false;
+ rs.quality.globalIllumination = false;
+ rs.quality.fresnel = false;
+ break;
+
+ //shadowed Phong
+ case SDLK_3:
+ rs.quality.shaded = true;
+ rs.quality.samples = 1;
+ rs.quality.phong = true;
+ rs.quality.phong_shadows = true;
+ rs.quality.monteCarlo = false;
+ rs.quality.globalIllumination = false;
+ rs.quality.fresnel = false;
+ break;
+
+ //full w/o GI
+ case SDLK_4:
+ rs.quality.shaded = true;
+ rs.quality.samples = 1;
+ rs.quality.phong = true;
+ rs.quality.phong_shadows = true;
+ rs.quality.monteCarlo = true;
+ rs.quality.globalIllumination = false;
+ break;
+
+ //GI only
+ case SDLK_5:
+ rs.quality.shaded = true;
+ rs.quality.samples = 1;
+ rs.quality.phong = false;
+ rs.quality.monteCarlo = true;
+ rs.quality.globalIllumination = true;
+ break;
+
+ //full
+ case SDLK_6:
+ rs.quality.shaded = true;
+ rs.quality.samples = 1;
+ rs.quality.phong = true;
+ rs.quality.phong_shadows = true;
+ rs.quality.monteCarlo = true;
+ rs.quality.globalIllumination = true;
+ break;
+
+ //full @ 5 samples
+ case SDLK_7:
+ rs.quality.shaded = true;
+ rs.quality.samples = 5;
+ rs.quality.phong = true;
+ rs.quality.phong_shadows = true;
+ rs.quality.monteCarlo = true;
+ rs.quality.globalIllumination = true;
+ break;
+
+ case SDLK_z: blockSelection = BLOCK_CONCRETE; break;
+ case SDLK_x: blockSelection = BLOCK_GROUND; break;
+ case SDLK_r: blockSelection = BLOCK_METAL; break;
+ case SDLK_t: blockSelection = BLOCK_MIRROR; break;
+ case SDLK_y: blockSelection = BLOCK_LIGHT; break;
+ case SDLK_u: blockSelection = BLOCK_BANNER; break;
+ }
+ }
+ break;
+
+ case SDL_MOUSEBUTTONDOWN:
+ switch( event.button.button )
+ {
+ case SDL_BUTTON_LEFT:
+ G_RemoveBlock( &world, rs.view.origin, rs.view.matrix, 6 );
+ break;
+
+ case SDL_BUTTON_RIGHT:
+ G_PlaceBlock( &world, rs.view.origin, rs.view.matrix, blockSelection, 6 );
+ break;
+ }
+ break;
+
+ case SDL_MOUSEMOTION:
+ {
+ float x_, y_;
+
+ if( !rs.ready )
+ break;
+
+ x_ = -0.005f * event.motion.xrel / rs.view.projdist;
+ y_ = 0.005f * event.motion.yrel / rs.view.projdist;
+
+ player.angles[ 2 ] += x_;
+ player.angles[ 1 ] += y_;
+
+ player.angles[ 1 ] =
+ V1Clamp( player.angles[ 1 ], -0.5 * M_PI, 0.5 * M_PI );
+ }
+ break;
+
+ case SDL_MOUSEWHEEL:
+ {
+ static int level = 0;
+
+ level -= event.wheel.y;
+ if( level > 0 )
+ level = 0;
+ rs.view.fov = 0.6 * M_PI * pow( 1.1, level );
+ }
+ break;
+ }
+
+ //input
+ {
+ const uint8_t *keys;
+ keys = SDL_GetKeyboardState( NULL );
+
+ V2Set( player.cmd_move, 0, 0 );
+ player.cmd_jump = false;
+ player.cmd_down = false;
+ player.cmd_sprint = false;
+ player.cmd_noclip = false;
+
+ if( keys[ SDL_SCANCODE_A ] )
+ player.cmd_move[ 0 ] -= 1.0;
+ if( keys[ SDL_SCANCODE_D ] )
+ player.cmd_move[ 0 ] += 1.0;
+ if( keys[ SDL_SCANCODE_W ] )
+ player.cmd_move[ 1 ] += 1.0;
+ if( keys[ SDL_SCANCODE_S ] )
+ player.cmd_move[ 1 ] -= 1.0;
+ if( keys[ SDL_SCANCODE_SPACE ] )
+ player.cmd_jump = true;
+ if( keys[ SDL_SCANCODE_C] )
+ player.cmd_down = true;
+ if( keys[ SDL_SCANCODE_LSHIFT ] )
+ player.cmd_sprint = true;
+ if( keys[ SDL_SCANCODE_LCTRL ] )
+ player.cmd_noclip = true;
+ }
+
+ G_RunPlayer( &world, &player );
+ R_ViewFromPlayer( &rs, &player );
+
+ //physics
+ {
+ G_time_t frametime;
+ frametime = U_Clock( );
+
+ while( phystime + 10 < frametime )
+ {
+ size_t i;
+ const vec_t delta = 0.01;
+
+ for( i = 0; i < MAX_DLIGHTS; i++ )
+ {
+ W_light_t *light = world.lights + i;
+
+ if( !light->inuse )
+ continue;
+
+ if( light->sun )
+ {
+ vec_t t;
+
+ t = 1.0e-6 * U_Microclock( ) * 0.3;
+ V3Set( light->direction, cos( t ), sin( t ), -0.5 );
+ V3Normalize( light->direction );
+ continue;
+ }
+
+ if( light->flashlight )
+ {
+ vec_t brightness;
+
+ V3MA2( light->origin, player.origin, 0.1, player.matrix,
+ 0.1, player.matrix + 3 );
+ V3Copy( light->direction, player.matrix );
+
+ brightness = (vec_t)rand() / RAND_MAX * 0.1 + 1.0 * 5.0;
+
+ V3Set( light->light, 1.0, 0.8, 0.5 );
+ V3Mul( light->light, light->light, brightness );
+
+ continue;
+ }
+
+ light->velocity[ 2 ] += 5 * delta;
+
+ {
+ G_player_t fake;
+
+ V3Copy( fake.origin, light->origin );
+ V3Copy( fake.velocity, light->velocity );
+
+ V3Set( fake.aabb[ 0 ], -0.1, -0.1, -0.1 );
+ V3Set( fake.aabb[ 1 ], 0.1, 0.1, 0.1 );
+
+ G_MovePlayer( &world, &fake, delta );
+
+ V3Copy( light->origin, fake.origin );
+ V3Copy( light->velocity, fake.velocity );
+ }
+
+ if( frametime - light->timestamp > 8000 || light->origin[ 2 ] > 32 )
+ light->inuse = false;
+ }
+
+ phystime += 10;
+ }
+ }
+
+ R_Render( &rs );
+
+ {
+ //static uint64_t last = 0;
+
+ //if( U_Microclock() > last + 500000 )
+ {
+ size_t nodes, leaves;
+ W_Stats( &world, &nodes, &leaves );
+ printf( "\r \r%.1f %zu(%zu)", rs.fps, nodes, leaves );
+ fflush( stdout );
+ //last = U_Microclock();
+ }
+ }
+ }
+
+main_loop_break:
+
+ V3Copy( world.saved_origin, player.origin );
+ V3Copy( world.saved_angles, player.angles );
+ W_Save( &world, "world" );
+
+ W_DeleteWorld( &world );
+
+ R_Quit( &rs );
+ SDL_WaitThread( evthd, 0 );
+ SDL_Quit();
+
+ return 0;
+}
diff --git a/player.c b/player.c
new file mode 100644
index 0000000..e844a5a
--- /dev/null
+++ b/player.c
@@ -0,0 +1,384 @@
+/*
+=======================================================================
+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"
+
+W_blockdata_t G_RemoveBlock( W_world_t *world, vec3_t vieworg, vec3_t viewdir, size_t targetDepth )
+{
+ ray_t ray;
+ rtres_t rtres;
+ W_otnode_t *target, *node;
+ W_blockdata_t block;
+ size_t i, depth;
+
+ U_BuildRay( vieworg, viewdir, INFINITY, &ray, &rtres );
+
+new_target:
+
+ target = W_Trace( world, NULL, &ray, &rtres );
+
+ if( !target )
+ return BLOCK_NONE;
+
+ for( depth = 0, node = target; node != world->otroot; node = node->p, depth++ );
+
+ if( depth < targetDepth )
+ {
+ for( i = 0; i < 8; i++ )
+ {
+ target->n[ i ] = W_NewOTNode( target, i );
+ memcpy( &target->n[ i ]->data, &target->data, sizeof( W_blockdata_t ) );
+ }
+ memset( &target->data, 0, sizeof( W_blockdata_t ) );
+ goto new_target;
+ }
+ else if( depth == targetDepth )
+ block = target->data;
+ else
+ block = BLOCK_NONE;
+
+ W_DeleteOTNode( target );
+ return block;
+}
+
+bool_t G_PlaceBlock( W_world_t *world, vec3_t vieworg, vec3_t viewdir, W_blockdata_t blockdata, size_t targetDepth )
+{
+ ray_t ray;
+ rtres_t rtres;
+ W_otnode_t *target, *node;
+ vec3_t point;
+ size_t depth;
+
+ U_BuildRay( vieworg, viewdir, INFINITY, &ray, &rtres );
+
+ if( !W_Trace( world, NULL, &ray, &rtres ) )
+ return false;
+
+ V3MA2( point, ray.org, rtres.dist, ray.dir, 1.0e-2, rtres.normal );
+
+ target = W_Point( world->otroot, point );
+
+ if( !target )
+ return false;
+
+ if( target->data )
+ return false;
+
+ for( depth = 0, node = target; node != world->otroot; node = node->p, depth++ );
+
+ while( depth < targetDepth )
+ {
+ int index, ix, iy, iz;
+ vec3_t center;
+
+ V3Lerp( center, 0.5, target->aabb[ 0 ], target->aabb[ 1 ] );
+
+ ix = ( point[ 0 ] > center[ 0 ] );
+ iy = ( point[ 1 ] >= center[ 1 ] );
+ iz = ( point[ 2 ] >= center[ 2 ] );
+
+ index = ix | ( iy << 1 ) | ( iz << 2 );
+ if( target->n[ index ] )
+ printf( "wtf???\n" );
+
+ memset( &target->data, 0, sizeof( W_blockdata_t ) );
+ target = target->n[ index ] = W_NewOTNode( target, index );
+
+ depth++;
+ }
+
+ if( depth > targetDepth )
+ return false; //no space
+
+ target->data = blockdata;
+
+ return true;
+}
+
+void G_RecolorBlock( W_world_t *world, vec3_t vieworg, vec3_t viewdir )
+{
+ W_otnode_t *node;
+ ray_t ray;
+ rtres_t rtres;
+
+ U_BuildRay( vieworg, viewdir, INFINITY, &ray, &rtres );
+
+ node = W_Trace( world, NULL, &ray, &rtres );
+
+ if( node )
+ {
+ node->data++;
+ node->data %= _Material_count;
+ if( node->data == 0 )
+ node->data = 1;
+ }
+}
+
+bool_t G_ExactTraceAABB( const vec3_t const *aabb, const ray_t *ray, rtres_t *rt )
+{
+ vec_t tn, tp, tyn, typ, tzn, tzp;
+
+ tn = ( aabb[ ray->dinvsign[ 0 ] ][ 0 ] - ray->org[ 0 ] ) * ray->dinv[ 0 ];
+ tp = ( aabb[ 1 - ray->dinvsign[ 0 ] ][ 0 ] - ray->org[ 0 ] ) * ray->dinv[ 0 ];
+
+ tyn = ( aabb[ ray->dinvsign[ 1 ] ][ 1 ] - ray->org[ 1 ] ) * ray->dinv[ 1 ];
+ typ = ( aabb[ 1 - ray->dinvsign[ 1 ] ][ 1 ] - ray->org[ 1 ] ) * ray->dinv[ 1 ];
+
+ V3Set( rt->normal, ray->dsign2[ 0 ], 0, 0 );
+
+ V3MA( rt->hit, ray->org, tn, ray->dir );
+ rt->hit[ 0 ] = aabb[ ray->dinvsign[ 0 ] ][ 0 ];
+
+ if( ( tn > typ ) || ( tyn > tp ) )
+ return false;
+
+ if( tyn > tn )
+ {
+ tn = tyn;
+ V3Set( rt->normal, 0, ray->dsign2[ 1 ], 0 );
+
+ V3MA( rt->hit, ray->org, tn, ray->dir );
+ rt->hit[ 1 ] = aabb[ ray->dinvsign[ 1 ] ][ 1 ];
+ }
+
+ if( typ < tp )
+ tp = typ;
+
+ tzn = ( aabb[ ray->dinvsign[ 2 ] ][ 2 ] - ray->org[ 2 ] ) * ray->dinv[ 2 ];
+ tzp = ( aabb[ 1 - ray->dinvsign[ 2 ] ][ 2 ] - ray->org[ 2 ] ) * ray->dinv[ 2 ];
+
+ if( ( tn > tzp ) || ( tzn > tp ) )
+ return false;
+
+ if( tzn > tn )
+ {
+ tn = tzn;
+ V3Set( rt->normal, 0, 0, ray->dsign2[ 2 ] );
+ V3MA( rt->hit, ray->org, tn, ray->dir );
+ rt->hit[ 2 ] = aabb[ ray->dinvsign[ 2 ] ][ 2 ];
+ }
+
+ if( tzp < tp )
+ tp = tzp;
+
+ rt->dist = tn;
+
+ return tn >= 0;
+}
+
+static void G_BoxTrace_R( W_otnode_t *node, W_otnode_t **node_best, rtres_t *rt_best, const ray_t *ray, const vec3_t *delta )
+{
+ size_t i;
+ bool_t intersects;
+ vec3_t aabb[ 2 ];
+ rtres_t rt;
+
+ V3Add( aabb[ 0 ], node->aabb[ 0 ], delta[ 0 ] );
+ V3Add( aabb[ 1 ], node->aabb[ 1 ], delta[ 1 ] );
+
+ if( U_PointInAABB2( ray->org, (const vec3_t *)aabb ) )
+ {
+ if( node->data )
+ return;
+ intersects = true;
+ }
+ else
+ intersects = G_ExactTraceAABB( (const vec3_t*)aabb, ray, &rt );
+
+ if( !intersects )
+ return;
+
+ if( node->data )
+ {
+ if( rt_best->dist >= rt.dist )
+ {
+ (*node_best) = node;
+ memcpy( rt_best, &rt, sizeof( rtres_t ) );
+ rt_best->data = node->data;
+ }
+ }
+ else
+ for( i = 0; i < 8; i++ )
+ if( node->n[ i ] )
+ G_BoxTrace_R( node->n[ i ], node_best, rt_best, ray, delta );
+}
+
+W_otnode_t *G_BoxTrace( W_world_t *world, rtres_t *rt_best, const ray_t *ray, const vec3_t *aabb )
+{
+ W_otnode_t *out_node = NULL;
+
+ memset( rt_best, 0, sizeof( rtres_t ) );
+ rt_best->dist = INFINITY;
+
+ if( !world->otroot )
+ return NULL;
+
+ G_BoxTrace_R( world->otroot, &out_node, rt_best, ray, aabb );
+
+ if( rt_best->dist > ray->limit )
+ return NULL;
+
+ return out_node;
+}
+
+void G_ClipVelocity( vec3_t out, vec3_t in, vec3_t normal )
+{
+ vec_t dot;
+
+ dot = V3Dot( in, normal );
+ V3Mul2( out, in, 1, normal, -dot );
+}
+
+
+
+//FIXME: G_BoxTrace gets stuck on edges
+void G_MovePlayer( W_world_t *world, G_player_t *p, vec_t delta )
+{
+ ray_t ray;
+ rtres_t rtres;
+ vec_t disp, speed;
+ bool_t clip;
+
+ while( delta > 1e-3 )
+ {
+ V3Copy( ray.dir, p->velocity );
+ speed = V3Normalize( ray.dir );
+ disp = speed * delta;
+
+ U_BuildRay( p->origin, p->velocity, disp, &ray, &rtres );
+
+ clip = ( G_BoxTrace( world, &rtres, &ray, (const vec3_t*)p->aabb ) != NULL );
+
+ if( clip )
+ {
+ V3Copy( p->origin, rtres.hit );
+ delta -= rtres.dist / V3Length( p->velocity );
+
+ V3Reflect( p->velocity, p->velocity, rtres.normal );
+
+ //G_ClipVelocity( p->velocity, p->velocity, rtres.normal );
+ }
+ else
+ {
+ V3MA( p->origin, p->origin, disp, ray.dir );
+ break;
+ }
+ }
+}
+
+/*
+void G_RunPlayer( W_world_t *world, G_player_t *p )
+{
+ G_time_t frametime;
+ vec_t delta;
+ frametime = U_Clock( );
+
+ V3AnglesToMatrix( p->matrix, p->angles );
+ M3RotZ( p->flatMatrix, p->angles[ 2 ] );
+
+ #define TIMESTEP 10
+
+ while( p->lastPhysicsTime + TIMESTEP < frametime )
+ {
+ vec3_t wishvel;
+
+ delta = 1.0e-3 * TIMESTEP;
+
+ if( p->cmd_noclip )
+ {
+ vec_t mod;
+
+ mod = delta * ( p->cmd_sprint ? 20 : 6 );
+
+ V3MA2( p->origin, p->origin, p->cmd_move[ 0 ] * mod, p->matrix + 3, p->cmd_move[ 1 ] * mod, p->matrix );
+ if( p->cmd_jump )
+ V3MA( p->origin, p->origin, -mod, p->matrix + 6 );
+
+ V3Set( p->velocity, 0, 0, 0 );
+
+ p->lastPhysicsTime += TIMESTEP;
+ continue;
+ }
+
+ {
+ ray_t ray;
+ rtres_t rtres;
+
+ V3Copy( ray.org, p->origin );
+ V3Set( ray.dir, 0, 0, 1 );
+ U_BuildRay( NULL, NULL, 0.01, &ray, &rtres );
+ p->onGround = ( G_BoxTrace( world, &rtres, &ray, (const vec3_t*)p->aabb ) != NULL );
+ }
+
+ if( p->onGround && p->cmd_jump )
+ p->velocity[ 2 ] = -2.6;
+
+ V3Mul2( wishvel, p->flatMatrix + 3, p->cmd_move[ 0 ],
+ p->flatMatrix, p->cmd_move[ 1 ] );
+ wishvel[ 2 ] = 0.0;
+ V2Normalize( wishvel );
+
+ V2Mul( wishvel, wishvel, 2 );
+ if( p->cmd_sprint )
+ V2Mul( wishvel, wishvel, 2 );
+
+
+ V2Lerp( p->velocity, 0.1, p->velocity, wishvel );
+ p->velocity[ 2 ] += 5.81 * delta;
+
+ G_MovePlayer( world, p, delta );
+
+ p->lastPhysicsTime += TIMESTEP;
+ }
+}*/
+
+void G_RunPlayer( W_world_t *world, G_player_t *p )
+{
+ G_time_t frametime;
+ vec_t delta;
+ frametime = U_Clock( );
+
+ V3AnglesToMatrix( p->matrix, p->angles );
+
+ #define TIMESTEP 10
+
+ while( p->lastPhysicsTime + TIMESTEP < frametime )
+ {
+ size_t i;
+ vec_t mod;
+ vec3_t target;
+
+ delta = 1.0e-3 * TIMESTEP;
+
+ mod = ( p->cmd_sprint ? 20 : 6 );
+
+ for( i = 0; i < 3; i++ )
+ target[ i ] = p->cmd_move[ 0 ] * p->matrix[ i + 3 ] +
+ p->cmd_move[ 1 ] * p->matrix[ i ] +
+ ( p->cmd_jump ? -p->matrix[ i + 6 ] : 0 ) +
+ ( p->cmd_down ? p->matrix[ i + 6 ] : 0 );
+ V3Mul( target, target, mod );
+
+ V3Lerp( p->velocity, 0.1, p->velocity, target );
+
+ V3MA( p->origin, p->origin, delta, p->velocity );
+
+ p->lastPhysicsTime += TIMESTEP;
+ }
+}
diff --git a/rrt b/rrt
new file mode 100755
index 0000000..c3362a6
--- /dev/null
+++ b/rrt
Binary files differ
diff --git a/tex/1.jpg b/tex/1.jpg
new file mode 100644
index 0000000..5468118
--- /dev/null
+++ b/tex/1.jpg
Binary files differ
diff --git a/tex/2.jpg b/tex/2.jpg
new file mode 100644
index 0000000..ce5439d
--- /dev/null
+++ b/tex/2.jpg
Binary files differ
diff --git a/tex/6.jpg b/tex/6.jpg
new file mode 100644
index 0000000..e07fbca
--- /dev/null
+++ b/tex/6.jpg
Binary files differ
diff --git a/u_math.c b/u_math.c
new file mode 100644
index 0000000..8169e15
--- /dev/null
+++ b/u_math.c
@@ -0,0 +1,151 @@
+/*
+=======================================================================
+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"
+
+vec_t V2Normalize( vec2_t v )
+{
+ vec_t l, il;
+
+ l = V2Length( v );
+
+ if( l )
+ {
+ il = 1.0 / l;
+ V2Mul( v, v, il );
+ }
+ else
+ V2Set( v, 0, 0 );
+
+ return l;
+}
+
+vec_t V3Normalize( vec3_t v )
+{
+ vec_t l, il;
+
+ l = V3Length( v );
+
+ if( l )
+ {
+ il = 1.0 / l;
+ V3Mul( v, v, il );
+ }
+ else
+ V3Set( v, 0, 0, 0 );
+
+ return l;
+}
+
+vec_t V4Normalize( vec4_t v )
+{
+ vec_t l, il;
+
+ l = V4Length( v );
+
+ if( l )
+ {
+ il = 1.0 / l;
+ V4Mul( v, v, il );
+ }
+ else
+ V4Set( v, 0, 0, 0, 0 );
+
+ return l;
+}
+
+void V3Reflect( vec3_t out, const vec3_t in, const vec3_t normal )
+{
+ vec_t dot;
+
+ dot = V3Dot( in, normal );
+ V3MA( out, in, -2.0 * dot, normal );
+}
+
+void V3AnglesToMatrix( m3_t out, const vec3_t angles )
+{
+ m3_t M, Mx, My, Mz;
+
+ M3RotX( Mx, angles[ 0 ] );
+ M3RotY( My, angles[ 1 ] );
+ M3RotZ( Mz, angles[ 2 ] );
+
+ M3Product( M, Mx, My );
+ M3Product( out, M, Mz );
+}
+
+void V3HSVtoRGB( vec3_t out, const vec3_t in )
+{
+ vec_t C, H_, X, m;
+
+ C = in[ C_VALUE ] * in[ C_SATURATION ];
+
+ H_= in[ C_HUE ] / 60.0;
+ X = C * ( 1.0 - fabs( fmod( H_, 2.0 ) - 1.0 ) );
+
+ m = in[ C_VALUE ] - C;
+
+ H_ = fmod( H_, 6.0f );
+
+ if( H_ >= 5.0 )
+ V3Set( out, C, 0, X );
+ else if( H_ >= 4.0 )
+ V3Set( out, X, 0, C );
+ else if( H_ >= 3.0 )
+ V3Set( out, 0, X, C );
+ else if( H_ >= 2.0 )
+ V3Set( out, 0, C, X );
+ else if( H_ >= 1.0 )
+ V3Set( out, X, C, 0 );
+ else
+ V3Set( out, C, X, 0 );
+
+ out[ C_RED ] += m;
+ out[ C_GREEN ] += m;
+ out[ C_BLUE ] += m;
+}
+
+void V3RGBtoHSV( vec3_t out, const vec3_t in )
+{
+ vec_t M, m, C;
+
+ M = V1Max( V1Max( in[ 0 ], in[ 1 ] ), in[ 2 ] );
+ m = V1Min( V1Min( in[ 0 ], in[ 1 ] ), in[ 2 ] );
+
+ C = M - m;
+
+ if( V1Epscmp( C, 0, 1.0e-4 ) )
+ out[ C_HUE ] = 0;
+ else if( V1Epscmp( M, in[ C_RED ], 1.0e-4 ) )
+ out[ C_HUE ] = fmod( ( in[ C_GREEN ] - in[ C_BLUE ] ) / C, 6 );
+ else if( V1Epscmp( M, in[ C_GREEN ], 1.0e-4 ) )
+ out[ C_HUE ] = ( in[ C_BLUE ] - in[ C_RED ] ) / C + 2;
+ else
+ out[ C_HUE ] = ( in[ C_RED ] - in[ C_GREEN ] ) / C + 4;
+
+ out[ C_HUE ] *= 60;
+
+ out[ C_VALUE ] = M;
+
+ if( V1Epscmp( C, 0, 1.0e-4 ) )
+ out[ C_SATURATION ] = 0;
+ else
+ out[ C_SATURATION ] = C / out[ C_VALUE ];
+}
+
diff --git a/u_misc.c b/u_misc.c
new file mode 100644
index 0000000..88529ef
--- /dev/null
+++ b/u_misc.c
@@ -0,0 +1,36 @@
+/*
+=======================================================================
+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"
+
+const char *va( const char *fmt, ... )
+{
+ va_list vl;
+ static char bufs[ VA_BUFFERS ][ VA_MAX ];
+ static int i = 0;
+
+ i++;
+ i %= VA_BUFFERS;
+
+ va_start( vl, fmt );
+ vsnprintf( bufs[ i ], VA_MAX, fmt, vl );
+ va_end( vl );
+
+ return bufs[ i ];
+}
diff --git a/u_platform.c b/u_platform.c
new file mode 100644
index 0000000..a3c8a93
--- /dev/null
+++ b/u_platform.c
@@ -0,0 +1,56 @@
+/*
+=======================================================================
+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"
+
+#ifdef PLATFORM_POSIX
+ #include <time.h>
+#endif
+
+// U_Clock: measure time with 1ms precision
+uint64_t U_Clock( void )
+{
+ return SDL_GetTicks( );
+}
+
+// U_Microclock: measure time with 1us precision
+uint64_t U_Microclock( void )
+{
+#ifdef PLATFORM_POSIX
+ struct timespec t;
+ clock_gettime( CLOCK_MONOTONIC, &t );
+ return t.tv_sec * 1000000 + t.tv_nsec / 1000;
+#else
+ //TODO: win32 timers here
+ return SDL_GetTicks( ) * 1000;
+#endif
+}
+
+// U_Nanoclock: measure time with 1ns precision
+uint64_t U_Nanoclock( void )
+{
+#ifdef PLATFORM_POSIX
+ struct timespec t;
+ clock_gettime( CLOCK_MONOTONIC, &t );
+ return t.tv_sec * 1000000000 + t.tv_nsec;
+#else
+ //TODO: win32 timers here
+ return SDL_GetTicks( ) * 1000000;
+#endif
+}
diff --git a/u_ray.c b/u_ray.c
new file mode 100644
index 0000000..8473799
--- /dev/null
+++ b/u_ray.c
@@ -0,0 +1,257 @@
+/*
+=======================================================================
+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 U_BuildRay( const vec3_t org, const vec3_t dir, vec_t limit, ray_t *ray, rtres_t *rt )
+{
+ size_t i;
+
+ if( org )
+ V3Copy( ray->org, org );
+ if( dir )
+ V3Copy( ray->dir, dir );
+
+ for( i = 0; i < 3; i++ )
+ ray->dinv[ i ] = 1.0 / ray->dir[ i ];
+
+ for( i = 0; i < 3; i++ )
+ ray->dinvsign[ i ] = ( ray->dinv[ i ] < 0 );
+
+ for( i = 0; i < 3; i++ )
+ ray->dsign[ i ] = ( ray->dir[ i ] >= 0.0 ? 1 : 0 );
+
+ for( i = 0; i < 3; i++ )
+ ray->dsign2[ i ] = ( ray->dir[ i ] <= 0.0 ? 1 : -1 );
+
+ #define ORDER( a, b, c, d, e, f, g, h ) \
+ ray->otorder[ 0 ] = a; \
+ ray->otorder[ 1 ] = b; \
+ ray->otorder[ 2 ] = c; \
+ ray->otorder[ 3 ] = d; \
+ ray->otorder[ 4 ] = e; \
+ ray->otorder[ 5 ] = f; \
+ ray->otorder[ 6 ] = g; \
+ ray->otorder[ 7 ] = h;
+
+ switch( ray->dsign[ 0 ] |
+ ray->dsign[ 1 ] << 1 |
+ ray->dsign[ 2 ] << 2 )
+ {
+ case 0: // nnn
+ ORDER( 7, 5, 6, 3, 4, 1, 2, 0 );
+ break;
+
+ case 1: // pnn
+ ORDER( 6, 4, 7, 2, 5, 0, 3, 1 );
+ break;
+
+ case 2: // npn
+ ORDER( 5, 4, 7, 1, 6, 0, 3, 2 );
+ break;
+
+ case 3: // ppn
+ ORDER( 4, 5, 6, 0, 7, 1, 2, 3 );
+ break;
+
+ case 4: // nnp
+ ORDER( 3, 1, 2, 7, 5, 0, 6, 4 );
+ break;
+
+ case 5: // pnp
+ ORDER( 2, 0, 3, 6, 4, 7, 1, 5 );
+ break;
+
+ case 6: // npp
+ ORDER( 1, 0, 3, 5, 4, 7, 2, 6 );
+ break;
+
+ case 7: // ppp
+ ORDER( 0, 1, 2, 4, 5, 6, 3, 7 );
+ break;
+ }
+
+ ray->limit = limit;
+
+ V3Copy( ray->aabb[ 0 ], ray->org );
+ V3MA( ray->aabb[ 1 ], ray->org, limit, ray->dir );
+
+ for( i = 0; i < 3; i++ )
+ if( ray->aabb[ 0 ][ i ] > ray->aabb[ 1 ][ i ] )
+ Swap( vec_t, ray->aabb[ 0 ][ i ], ray->aabb[ 1 ][ i ] );
+
+ if( rt )
+ memset( rt, 0, sizeof( rtres_t ) );
+}
+
+bool_t U_PointInAABB2( const vec3_t point, const vec3_t *aabb )
+{
+ return ( point[ 0 ] > aabb[ 0 ][ 0 ] &&
+ point[ 1 ] > aabb[ 0 ][ 1 ] &&
+ point[ 2 ] > aabb[ 0 ][ 2 ] &&
+ point[ 0 ] < aabb[ 1 ][ 0 ] &&
+ point[ 1 ] < aabb[ 1 ][ 1 ] &&
+ point[ 2 ] < aabb[ 1 ][ 2 ] );
+}
+
+bool_t U_PointInAABB( const vec3_t point, const vec3_t *aabb )
+{
+ return ( point[ 0 ] >= aabb[ 0 ][ 0 ] &&
+ point[ 1 ] >= aabb[ 0 ][ 1 ] &&
+ point[ 2 ] >= aabb[ 0 ][ 2 ] &&
+ point[ 0 ] <= aabb[ 1 ][ 0 ] &&
+ point[ 1 ] <= aabb[ 1 ][ 1 ] &&
+ point[ 2 ] <= aabb[ 1 ][ 2 ] );
+}
+
+//based upon ioquake3's BoundsIntersect
+bool_t U_AABBIntersect( const vec3_t a[ 2 ], const vec3_t b[ 2 ] )
+{
+ if( a[ 1 ][ 0 ] < b[ 0 ][ 0 ] ||
+ a[ 1 ][ 1 ] < b[ 0 ][ 1 ] ||
+ a[ 1 ][ 2 ] < b[ 0 ][ 2 ] ||
+ a[ 0 ][ 0 ] > b[ 1 ][ 0 ] ||
+ a[ 0 ][ 1 ] > b[ 1 ][ 1 ] ||
+ a[ 0 ][ 2 ] > b[ 1 ][ 2 ] )
+ return false;
+ return true;
+}
+
+bool_t U_RT_Zplane(
+ vec_t z,
+ const ray_t *ray,
+ rtres_t *rt
+ )
+{
+ vec_t dz;
+
+ if( ray->dinvsign[ 2 ] ||
+ ray->org[ 2 ] > z )
+ return false;
+
+ dz = z - ray->org[ 2 ];
+
+ rt->hit[ 0 ] = ray->org[ 0 ] + ray->dir[ 0 ] * ray->dinv[ 2 ] * dz;
+ rt->hit[ 1 ] = ray->org[ 1 ] + ray->dir[ 1 ] * ray->dinv[ 2 ] * dz;
+ rt->hit[ 2 ] = z;
+
+ V3Set( rt->normal, 0, 0, -1 );
+
+ return true;
+}
+
+//all the ray-box intersection code is based upon the paper:
+// Amy Williams, Steve Barrus, R. Keith Morley, and Peter Shirley
+// "An Efficient and Robust Ray-Box Intersection Algorithm"
+// Journal of graphics tools, 10(1):49-54, 2005
+bool_t U_RT_AABB_Fast(
+ const vec3_t const *aabb,
+ const ray_t *ray,
+ rtres_t *rt
+ )
+{
+ vec_t tn, tp, tyn, typ, tzn, tzp;
+
+ //if( !U_AABBIntersect( ray->aabb, aabb ) )
+ // return false;
+
+ if( U_PointInAABB( ray->org, aabb ) )
+ return true;
+
+ tn = ( aabb[ ray->dinvsign[ 0 ] ][ 0 ] - ray->org[ 0 ] ) * ray->dinv[ 0 ];
+ tp = ( aabb[ 1 - ray->dinvsign[ 0 ] ][ 0 ] - ray->org[ 0 ] ) * ray->dinv[ 0 ];
+
+ tyn = ( aabb[ ray->dinvsign[ 1 ] ][ 1 ] - ray->org[ 1 ] ) * ray->dinv[ 1 ];
+ typ = ( aabb[ 1 - ray->dinvsign[ 1 ] ][ 1 ] - ray->org[ 1 ] ) * ray->dinv[ 1 ];
+
+ if( ( tn > typ ) || ( tyn > tp ) )
+ return false;
+
+ if( tyn > tn )
+ tn = tyn;
+
+ if( typ < tp )
+ tp = typ;
+
+ tzn = ( aabb[ ray->dinvsign[ 2 ] ][ 2 ] - ray->org[ 2 ] ) * ray->dinv[ 2 ];
+ tzp = ( aabb[ 1 - ray->dinvsign[ 2 ] ][ 2 ] - ray->org[ 2 ] ) * ray->dinv[ 2 ];
+
+ if( ( tn > tzp ) || ( tzn > tp ) )
+ return false;
+
+ if( tzn > tn )
+ tn = tzn;
+
+ if( tzp < tp )
+ tp = tzp;
+
+ rt->dist = tn;
+
+ return tn > 0;
+}
+
+bool_t U_RT_AABB(
+ const vec3_t const *aabb,
+ const ray_t *ray,
+ rtres_t *rt
+ )
+{
+ vec_t tn, tp, tyn, typ, tzn, tzp;
+
+ if( !U_AABBIntersect( ray->aabb, aabb ) )
+ return false;
+
+ if( U_PointInAABB( ray->org, aabb ) )
+ return true;
+
+ tn = ( aabb[ ray->dinvsign[ 0 ] ][ 0 ] - ray->org[ 0 ] ) * ray->dinv[ 0 ];
+ tp = ( aabb[ 1 - ray->dinvsign[ 0 ] ][ 0 ] - ray->org[ 0 ] ) * ray->dinv[ 0 ];
+
+ tyn = ( aabb[ ray->dinvsign[ 1 ] ][ 1 ] - ray->org[ 1 ] ) * ray->dinv[ 1 ];
+ typ = ( aabb[ 1 - ray->dinvsign[ 1 ] ][ 1 ] - ray->org[ 1 ] ) * ray->dinv[ 1 ];
+
+ V3Set( rt->normal, ray->dsign2[ 0 ], 0, 0 );
+
+ if( ( tn > typ ) || ( tyn > tp ) )
+ return false;
+
+ if( tyn > tn )
+ tn = tyn,
+ V3Set( rt->normal, 0, ray->dsign2[ 1 ], 0 );
+
+ if( typ < tp )
+ tp = typ;
+
+ tzn = ( aabb[ ray->dinvsign[ 2 ] ][ 2 ] - ray->org[ 2 ] ) * ray->dinv[ 2 ];
+ tzp = ( aabb[ 1 - ray->dinvsign[ 2 ] ][ 2 ] - ray->org[ 2 ] ) * ray->dinv[ 2 ];
+
+ if( ( tn > tzp ) || ( tzn > tp ) )
+ return false;
+
+ if( tzn > tn )
+ tn = tzn,
+ V3Set( rt->normal, 0, 0, ray->dsign2[ 2 ] );
+
+ if( tzp < tp )
+ tp = tzp;
+
+ rt->dist = tn;
+
+ return tn > 0;
+}
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 );
+}
diff --git a/world b/world
new file mode 100644
index 0000000..02a771c
--- /dev/null
+++ b/world
Binary files differ
diff --git a/world_konkurs b/world_konkurs
new file mode 100644
index 0000000..df835e5
--- /dev/null
+++ b/world_konkurs
Binary files differ