From dc9f5457ee20ab17bb54551497703e9d9bf91573 Mon Sep 17 00:00:00 2001
From: Paweł Redman <pawel.redman@gmail.com>
Date: Wed, 26 Jul 2017 17:38:26 +0200
Subject: Initial commit.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This is the ray tracer/path tracer I've written for Otwarty Międzyszkolny Konkurs Fizyczny in March/April of 2014.
There is no proper history as back then I had no idea how to use a VCS.
---
 .u_world.c.swp |  Bin 0 -> 24576 bytes
 build.sh       |    8 +
 common.h       |  416 +++++++++++++++
 main.c         | 1556 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 player.c       |  384 ++++++++++++++
 rrt            |  Bin 0 -> 64240 bytes
 tex/1.jpg      |  Bin 0 -> 64371 bytes
 tex/2.jpg      |  Bin 0 -> 224082 bytes
 tex/6.jpg      |  Bin 0 -> 18022 bytes
 u_math.c       |  151 ++++++
 u_misc.c       |   36 ++
 u_platform.c   |   56 ++
 u_ray.c        |  257 ++++++++++
 u_world.c      |  428 ++++++++++++++++
 world          |  Bin 0 -> 21124 bytes
 world_konkurs  |  Bin 0 -> 20732 bytes
 16 files changed, 3292 insertions(+)
 create mode 100644 .u_world.c.swp
 create mode 100755 build.sh
 create mode 100644 common.h
 create mode 100644 main.c
 create mode 100644 player.c
 create mode 100755 rrt
 create mode 100644 tex/1.jpg
 create mode 100644 tex/2.jpg
 create mode 100644 tex/6.jpg
 create mode 100644 u_math.c
 create mode 100644 u_misc.c
 create mode 100644 u_platform.c
 create mode 100644 u_ray.c
 create mode 100644 u_world.c
 create mode 100644 world
 create mode 100644 world_konkurs

diff --git a/.u_world.c.swp b/.u_world.c.swp
new file mode 100644
index 0000000..7079a04
Binary files /dev/null and b/.u_world.c.swp 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
Binary files /dev/null and b/rrt differ
diff --git a/tex/1.jpg b/tex/1.jpg
new file mode 100644
index 0000000..5468118
Binary files /dev/null and b/tex/1.jpg differ
diff --git a/tex/2.jpg b/tex/2.jpg
new file mode 100644
index 0000000..ce5439d
Binary files /dev/null and b/tex/2.jpg differ
diff --git a/tex/6.jpg b/tex/6.jpg
new file mode 100644
index 0000000..e07fbca
Binary files /dev/null and b/tex/6.jpg 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
Binary files /dev/null and b/world differ
diff --git a/world_konkurs b/world_konkurs
new file mode 100644
index 0000000..df835e5
Binary files /dev/null and b/world_konkurs differ
-- 
cgit