gistfile1.c

/*
author: jabberx@ymail.com
date  : 23/feb/2013
LICENSE: NO RESTRICTIONS, NO WARRANTIES
*/
 
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
typedef uint32_t u32;
typedef int32_t i32;
typedef uint8_t u8;
#include <SDL/SDL.h>
 
//////////////////////////// глобальные переменные: ///////////////////////////
 
const int width = 320, height = 200;
u32 *scr;
SDL_Surface *sdl_scr;
 
const float MAX_RAY_DIST = 256;
u32 SKY = 0x99AADD;
const u32 BORDER = 0x98765432;
void* root_node[8];
const int oct_depth = 9;
 
/////////////////////////// структуры: ////////////////////////////////////////
 
typedef struct {
    union {
        struct { float x, y, z; };
        struct { float u, v, w; };
        struct { float yaw, pitch, roll; };
        float f[3];
    };
} Vec;
 
typedef struct {
    float f[9];
} Matrix9;
 
///////////////////////////// объявления функций: /////////////////////////////
 
void  octree_add(void** root, int depth, int x, int y, int z, int color);
int   octree_get(void** root, int depth, int x, int y, int z, int *level);
void  octree_load256(void** root, int depth, const char* filename);
void  octree_add_border(void** root, int depth, u32 color);
 
float get_jump_len(Vec *origin, Vec *ray,
                       Vec *cube1, Vec *cube2, Vec *len_to_jump);
u32   ray_cast(Vec pos, Vec dir, float *dist);
 
float get_delta_time();
void  flip_screen();
void  set_point(int x, int y, u32 value);
int   loop(u8 *keys, i32 mouse_x, i32 mouse_y, u8 mouse_l, u8 mouse_r);
 
void  matrix9_fill(Matrix9 *m, Vec *angles);
void  matrix9_vec_mul(Matrix9 *m, Vec *r, Vec *a);
void  vec_add(Vec *r, Vec *a, Vec *b);
void  vec_mul(Vec *r, Vec *a, float v);
float vec_sqr_len(Vec *a);
float vec_len(Vec *a);
void  vec_norm(Vec *r, Vec *a);
void  vec_copy(Vec *d, Vec *s);
void  vec_mul(Vec *r, Vec *a, float v);
void  vec_set(Vec *d, float x, float y, float z);
void  vec_divv(Vec *r, Vec *a, Vec *b);
void  vec_sub(Vec *r, Vec *a, Vec *b);
void  vec_min(Vec *r, Vec *a, Vec *b);
void  vec_max(Vec *r, Vec *a, Vec *b);
 
u32 asm_color(u8 r, u8 g, u8 b);
u32 color_lerp(u32 a, u32 b, float x);
 
/////////////////////////// точка входа: //////////////////////////////////////
 
int main(int argc, char **argv)
{
    scr = calloc(width*height, 4);
    sdl_scr = SDL_SetVideoMode(width, height, 32, SDL_HWSURFACE);
   
    octree_load256(root_node, oct_depth, "land.o256");
    octree_add_border(root_node, oct_depth, BORDER);
   
    for(;;) {
        i32 mouse_x, mouse_y;
        u8 mouse_l, mouse_r, buttons;
        SDL_PumpEvents();
        buttons = SDL_GetMouseState(&mouse_x, &mouse_y);
        mouse_l = buttons&SDL_BUTTON(1);
        mouse_r = buttons&SDL_BUTTON(3);
        if (!loop(SDL_GetKeyState(NULL),
                  mouse_x, mouse_y, mouse_l, mouse_r)) break;
    }
    return 0;
}
 
///////////////////////// главный цикл: ///////////////////////////////////////
 
int collision(Vec cam)
{
    int tmp;
    int dim = 1<<(oct_depth-1);
    if (cam.x<0||cam.y<0||cam.z<0||cam.x>=dim||cam.y>=dim||cam.z>=dim)return 1;
    if (octree_get(root_node, oct_depth, cam.x, cam.y, cam.z, &tmp)) return 1;
    return 0;
}
 
int loop(u8 *keys, i32 mouse_x, i32 mouse_y, u8 mouse_l, u8 mouse_r)
{
    static Vec campos, angles;
    static Matrix9 matrix;
    static int was_init = 0;
    float delta_time = get_delta_time();
    float delta_val  = delta_time * 0.01;
    // инициализация углов и позиции камеры:
    if (!was_init) {
        vec_set(&campos, 64, 64, 100);
        vec_set(&angles, 0, 0, 0);
        matrix9_fill(&matrix, &angles);
        was_init = 1;
    }
    // выход по escape:
    if (keys[SDLK_ESCAPE]) return 0;
   
    // обзор мышью:
    if (mouse_r||mouse_l) {
        float dx, dy;
        SDL_ShowCursor(0);
        dx = (width /2 - mouse_x)*0.12;
        dy = (height/2 - mouse_y)*0.10;
        angles.yaw   += dx;
        angles.pitch += dy;
        angles.roll  -= dx*0.1;
        //if (dx || dy) matrix9_fill(&matrix, &angles);
        SDL_WarpMouse(width/2, height/2);
    }else{
        SDL_ShowCursor(1);
    }
    angles.roll /= 1.1;
    matrix9_fill(&matrix, &angles);
   
    // сброс позиции по нажатию клавиши R:
    if (keys[SDLK_r]) vec_set(&campos, 64, 64, 100);
   
    // движение вперёд/назад:
    float xmot = 2*delta_val*keys[SDLK_d];
    xmot += -2*delta_val*keys[SDLK_a];
    float zmot = 2*delta_val*keys[SDLK_w];
    zmot += -2*delta_val*keys[SDLK_s];
    if (keys[SDLK_LSHIFT]) {
        xmot *= 3; zmot *= 3;
    }
    Vec motion = {  xmot, 0, zmot };
    matrix9_vec_mul(&matrix, &motion, &motion);
    int mlen = vec_len(&motion) + 1;
    motion.x /= (float)mlen;
    motion.y /= (float)mlen;
    motion.z /= (float)mlen;
    int i;
    for(i=0;i<mlen;i++){
        campos.x += motion.x;
        if (collision(campos)) campos.x -= motion.x;
        campos.y += motion.y;
        if (collision(campos)) campos.y -= motion.y;
        campos.z += motion.z;
        if (collision(campos)) campos.z -= motion.z;
    }
 
    // движение вверх/вниз
    if (keys[SDLK_SPACE]) campos.y += 1*delta_val;
    if (collision(campos)) campos.y -= 1*delta_val;
    if (keys[SDLK_LCTRL]) campos.y -= 1*delta_val;
    if (collision(campos)) campos.y += 1*delta_val;
 
    // проход по всем пикселям:
    int x,y;
    for (x=0; x<width;  x+=2)
    for (y=0; y<height; y+=2) {
        Vec ray, result;
        float dist;
        u32 steps = 0;
        u32 color = 0;
        // формируем луч:
        ray.x =  x - width /2;
        ray.y = -y + height/2;
        ray.z = width/1.5;
        vec_norm(&ray, &ray);
        // поворачиваем луч:
        matrix9_vec_mul(&matrix, &ray, &ray);
        // бросаем луч и если было пересечение формируем цвет:
        color = ray_cast(campos, ray, &dist);
        if (!color) color = SKY;
        else if (color==BORDER) color = SKY;
        else {
            float fog_power = dist/MAX_RAY_DIST;
            color = color_lerp(SKY, color, fog_power);
        }
        // рисуем пиксель
        set_point(x, y, color);
    }
    // показываем всё, что нарисовали:
    flip_screen();
   
    // счётчик кадров:
    char buffer[256]; sprintf(buffer, "fps: %.2f", 1000/delta_time);
    SDL_WM_SetCaption(buffer, NULL);
    return 1;
}
 
/////////////////////////// Raycasting: ///////////////////////////////////////
 
inline float get_jump_len(Vec *origin, Vec *ray,
                       Vec *cube1, Vec *cube2, Vec *len_to_jump)
{
    Vec tmin, tmax, t1, t2;
    float tnear;
    vec_sub (&tmin, cube1, origin);
    vec_divv(&tmin, &tmin, ray);
    vec_sub (&tmax, cube2, origin);
    vec_divv(&tmax, &tmax, ray);
    vec_min (&t1, &tmin, &tmax);
    vec_max (&t2, &tmin, &tmax);
    tnear = fmax(fmaxf(t1.x, t1.y), t1.z);
    if (tnear<0) tnear = fminf(fminf(t2.x, t2.y), t2.z);
    vec_mul (len_to_jump, ray, tnear);
    return tnear;
}
 
u32 ray_cast(Vec pos, Vec dir, float *dist)
{
    Vec pos_in_cube, cube1, cube2, jump_len;
    u32 depth = 0, voxel = 0;
    float cube_size, distance = 0;
    vec_set(&cube1, -0.001, -0.001, -0.001);
    for(;;) {
        voxel = octree_get(root_node, oct_depth,
                           (u32)pos.x,
                           (u32)pos.y,
                           (u32)pos.z, &depth);
        if (voxel) break;
        cube_size = 1<<depth;
        vec_set(&cube2, cube_size, cube_size, cube_size);
        pos_in_cube.x = fmodf(pos.x, cube_size);
        pos_in_cube.y = fmodf(pos.y, cube_size);
        pos_in_cube.z = fmodf(pos.z, cube_size);        
        distance += get_jump_len(&pos_in_cube, &dir, &cube1, &cube2, &jump_len);
        vec_add(&pos, &pos, &jump_len);        
        if (distance > MAX_RAY_DIST) break;
    }
    *dist = distance;
    return voxel;
}
 
////////////////////////// работа с экраном: //////////////////////////////////
 
void set_point(int x, int y, u32 value)
{
    x -= x & 1;
    y -= y & 1;
    scr[x+0 + (y+0)*width] = value;
    scr[x+1 + (y+0)*width] = value;
    scr[x+0 + (y+1)*width] = value;
    scr[x+1 + (y+1)*width] = value;
}
 
void flip_screen()
{
    if(SDL_MUSTLOCK(sdl_scr)) if(SDL_LockSurface(sdl_scr)<0) return;
    memcpy(sdl_scr->pixels, scr, width*height*4);
    if(SDL_MUSTLOCK(sdl_scr)) SDL_UnlockSurface(sdl_scr);
    SDL_Flip(sdl_scr);
}
 
/////// векторы и матрицы (здесь не все функции, только нужные): //////////////
 
float vec_sqr_len(Vec *a)
{
    return a->x*a->x + a->y*a->y + a->z*a->z;
}
 
float vec_len(Vec *a)
{
    return sqrtf(vec_sqr_len(a));
}
 
void vec_norm(Vec *r, Vec *a)
{
    float il = 1.0/vec_len(a);
    r->x = a->x * il;
    r->y = a->y * il;
    r->z = a->z * il;
}
 
void vec_add(Vec *r, Vec *a, Vec *b)
{
    r->x = a->x + b->x;
    r->y = a->y + b->y;
    r->z = a->z + b->z;
}
 
void matrix9_fill(Matrix9 *m, Vec *angles)
{
    static const double_t DTR = 0.017453292519943295;
    float cosyaw, cosroll, sinyaw, sinroll, cospitch, sinpitch;
    float yaw = angles->yaw, pitch = angles->pitch, roll = angles->roll;
    yaw *= DTR; pitch *= DTR; roll *= DTR;
    cosyaw = cos(yaw); cosroll = cos(roll); cospitch = cos(pitch);
    sinyaw = sin(yaw); sinroll = sin(roll); sinpitch = sin(pitch);
    m->f[0] =  cosyaw * cosroll; m->f[1] = -cosyaw * sinroll; m->f[2] =  sinyaw;
    m->f[3] =  sinpitch * sinyaw * cosroll + sinroll * cospitch;
    m->f[4] = -sinpitch * sinyaw * sinroll + cosroll * cospitch;
    m->f[5] = -sinpitch * cosyaw;
    m->f[6] = -cospitch * sinyaw * cosroll + sinpitch * sinroll;
    m->f[7] =  cospitch * sinyaw * sinroll + sinpitch * cosroll;
    m->f[8] =  cosyaw * cospitch;
}
 
void matrix9_vec_mul(Matrix9 *m, Vec *_r, Vec *a)
{
    Vec r;
    r.x = m->f[0] * a->x + m->f[3] * a->y + m->f[6] * a->z;
    r.y = m->f[1] * a->x + m->f[4] * a->y + m->f[7] * a->z;
    r.z = m->f[2] * a->x + m->f[5] * a->y + m->f[8] * a->z;
    vec_copy(_r, &r);
}
 
void vec_copy(Vec *d, Vec *s)
{
    d->x = s->x;
    d->y = s->y;
    d->z = s->z;
}
 
void vec_mul(Vec *r, Vec *a, float v)
{
    r->x = a->x * v;
    r->y = a->y * v;
    r->z = a->z * v;
}
 
void vec_set(Vec *d, float x, float y, float z)
{
    d->x = x;
    d->y = y;
    d->z = z;
}
 
void vec_divv(Vec *r, Vec *a, Vec *b)
{
    r->x = a->x / b->x;
    r->y = a->y / b->y;
    r->z = a->z / b->z;
}
 
void vec_sub(Vec *r, Vec *a, Vec *b)
{
    r->x = a->x - b->x;
    r->y = a->y - b->y;
    r->z = a->z - b->z;
}
 
void vec_min(Vec *r, Vec *a, Vec *b)
{
    r->x = fmin(a->x, b->x);
    r->y = fmin(a->y, b->y);
    r->z = fmin(a->z, b->z);
}
 
void vec_max(Vec *r, Vec *a, Vec *b)
{
    r->x = fmax(a->x, b->x);
    r->y = fmax(a->y, b->y);
    r->z = fmax(a->z, b->z);
}
 
/////////////////////////// работа с цветами: /////////////////////////////////
 
inline u32 asm_color(u8 r, u8 g, u8 b)
{
    return (r<<16) | (g<<8) | b;
}
 
inline u8 get_r(u32 color)
{
    return (color & 0xFF0000) >> 16;
}
 
inline u8 get_g(u32 color)
{
    return (color & 0xFF00) >> 8;
}
 
inline u8 get_b(u32 color)
{
    return color & 0xFF;
}
 
inline u32 color_mix(u32 a, u32 b)
{
    return asm_color(
              (get_r(a)+get_r(b))/2,
              (get_g(a)+get_g(b))/2,
              (get_b(a)+get_b(b))/2
             );
}
 
inline u32 color_lerp(u32 a, u32 b, float x)
{
    return asm_color(
              (get_r(a)*x+get_r(b)*(1-x)),
              (get_g(a)*x+get_g(b)*(1-x)),
              (get_b(a)*x+get_b(b)*(1-x))
             );
}
 
/////////////////////////// работа с Octree: //////////////////////////////////
 
void octree_load256(void** root, int depth, const char* filename)
{
    FILE *f = fopen(filename, "rb");
    if (f == NULL) { printf ("can't open file %s\n", filename); return; }
    while (!feof(f)) {
        u8 xyzrgb[6];
        fread(xyzrgb, 1, 6, f);
        octree_add(root, depth, xyzrgb[0], xyzrgb[1], xyzrgb[2],
                                asm_color(xyzrgb[5], xyzrgb[4], xyzrgb[3]));
    }
    fclose(f);
    printf("loading of %s done\n", filename);
}
 
void octree_add_border(void** root, int depth, u32 color)
{
    int dim = 1<<(depth-1);
    int x,y;
    for (x=0;x<dim;x++)
    for (y=0;y<dim;y++) {
        octree_add(root, depth, x, y, 0, color);
        octree_add(root, depth, x, y, dim-1, color);
        octree_add(root, depth, x, 0, y, color);
        octree_add(root, depth, x, dim-1, y, color);
        octree_add(root, depth, 0, x, y, color);
        octree_add(root, depth, dim-1, x, y, color);
    }
}
 
void octree_add(void** root, int depth, int x, int y, int z, int color)
{
    int tx, ty, tz;
    void** *node;    
    depth--; tx = x>>depth; ty = y>>depth; tz = z>>depth;
    node = &(root[tx+(ty<<1)+(tz<<2)]);
    if (*node == NULL) *node = calloc(sizeof(void*), 8);    
    while (depth!=1) {
        x -= tx<<depth; y -= ty<<depth; z -= tz<<depth;        
        depth--; tx = x>>depth; ty = y>>depth; tz = z>>depth;
        node = &((*node)[tx+(ty<<1)+(tz<<2)]);
        if (*node == NULL) *node = calloc(sizeof(void*), 8);
    }    
    x -= tx<<depth; y -= ty<<depth; z -= tz<<depth;
    (*node)[x+(y<<1)+(z<<2)] = color;
}
 
inline int octree_get(void** root, int depth, int x, int y, int z, int *level)
{
    int tx, ty, tz;
    void** *node;
    depth--; tx = x>>depth; ty = y>>depth; tz = z>>depth;
    node = &(root[tx+(ty<<1)+(tz<<2)]);
    if (*node == NULL) { *level = depth; return 0; }
    while (depth!=1) {
        x -= tx<<depth;  y -= ty<<depth; z -= tz<<depth;
        depth--; tx = x>>depth; ty = y>>depth; tz = z>>depth;
        node = &((*node)[tx+(ty<<1)+(tz<<2)]);
        if (*node == NULL) { *level = depth; return 0; }
    }
    x -= tx<<depth; y -= ty<<depth; z -= tz<<depth;  
    *level = 0;
    return (*node)[x+(y<<1)+(z<<2)];
}
 
/////////////////////////// прочее: ///////////////////////////////////////////
 
float get_delta_time()
{
    static u32 last_ticks = 0;
    float delta = 16;
    if (last_ticks == 0) last_ticks = SDL_GetTicks();
    delta = SDL_GetTicks() - last_ticks;
    last_ticks = SDL_GetTicks();
    return delta<1 ? 1 : delta;
}