Фильтруй базар!

Добился почти идеального качества картинки, правда за счет резкого падения производительности (правда на моём компьютере програмка бегает очень даже шустро, если включить оптимизацию в clang).

В этой программе я буду использовать карту высот 512x512 и такую же "текстурку" (на самом деле простой массив, генерируемый на ходу, но SDL также отлично работает и с файлами.)

Вспомним, теперь, что координаты в пространстве мы представляли числами типа int (что и понятно, ведь из координат строится индекс массива - целое число!).

Теперь представим, что наши карта высот и текстуры - некие функции от координат x,y, где x и y - вещественные числа. Тогда логичнее задать наши координаты числами типа float или double (хотя тут кроется потеря производительности, например, мы уже не сможем продолжить нашу карту на всю плоскость простыми бинарными операциями и будем использовать деление и умножение).

Как найти эту функцию? Тут мы будем пользоваться техникой билинейной фильтрации, основанной на билинейной интерполяции.

Допустим, мы знаем, что в координатах x = x0, y = y0 f(x,y) = z0, где x0, y0 целые числа.
Аналогично:
f(x1,y0) = z1
f(x0,y1) = z2
f(x1,y1) = z3 (все координаты - целые)

Определим z = f(x,y) так:





Как определить высоту ландшафта в точках (2.32, 3.54)? Возьмем x0=2, y0=3, x1=3, y1=4 как можно ближе к нашим координатам и воспользуемся данными формулами.

В этом и заключается принцип билинейной фильтрации - взять 4 соседних пиксела, где значение высоты известно и интерполировать по ним.

Формулы можно упростить. Как? Смотри википедию. Я лишь приведу готовый результат + картинки.

Картинка до (картинка после - в начале статьи):


Недостаток таков: при передвижении по миру высота пика будет меняться + картинка выглядит блочной. Это связано с тем, что семплы на карте высот берутся не все, а через некоторый шаг.
Избавиться от этого просто: уменьшить шаг хода луча. Тогда получим идеальную картинку, лишенную всякой блочности (но потеряем в производительности):



Код программы:

Открыть спойлер

#include <stdlib.h>
#include <math.h>
#include "SDL.h"

int scw = 1280;
int sch = 1024;

int mapw = 512;
int maph = 512;

void filldata (int *hei, int *col)
{
    int p = 0;
    int x,y;
    for (y=0; y<maph; y++)
    {
        for (x=0; x<mapw; x++)
        {
            double x1 = (x-mapw/2)*0.3;
            double y1 = (y-maph/2)*0.3;
            col[p] = 3*(cos(x*0.2) + sin (y*0.3)) + 88;
            hei[p] = 1000*sin(sqrt(x1*x1+y1*y1))/(1+sqrt(x1*x1+y1*y1));
            
            p++;
        }
    }
}

void fillpalette (SDL_Surface *screen)
{
    SDL_Color colors[256];
    int i;
    /* Fill colors with color information */
    for(i=0;i<=256;i++)
    {
        colors[i].r=i;
        colors[i].g=i/3;
        colors[i].b=i/3;
    }
    SDL_SetPalette(screen, SDL_LOGPAL|SDL_PHYSPAL, colors, 0, 256);
}

void checkevents(double *ang, int *x, int *y)
{
    SDL_Event event;
    if (SDL_PollEvent(&event))
    {
        switch (event.type) {
        case SDL_QUIT:
            exit(0);
        }
    }
    Uint8 *keystate = SDL_GetKeyState (NULL);
    if (keystate[SDLK_LEFT]) *ang += 0.02;
    if (keystate[SDLK_RIGHT]) *ang -= 0.02;
    if (keystate[SDLK_a] || keystate[SDLK_d] || keystate[SDLK_w] || keystate[SDLK_s])
    {
        int xd, yd;
        xd = 0;
        yd = 0;
        if (keystate[SDLK_a]) xd = -3;
        if (keystate[SDLK_d]) xd = 3;
        if (keystate[SDLK_w]) yd = 3;
        if (keystate[SDLK_s]) yd = -3;
        
        *x += yd*cos(*ang) + xd*sin(*ang);
        *y += -yd*sin(*ang) + xd*cos(*ang);
    }
}

void fillarray (int *a, int val, int size)
{
    int i;
    for (i=0; i<size; i++) a[i] = val;
}

void blacken_screen (SDL_Surface *screen)
{
    SDL_Rect rect;
    rect.x = 0;
    rect.y = 0;
    rect.w = scw;
    rect.h = sch;

    SDL_FillRect (screen, &rect, 0);
}

double get_filtered_val (int *val, double xf, double yf)
{
    int x = xf;
    int y = yf;
    double diffx = xf - x;
    double diffy = yf - y;
    double oppx = 1 - diffx;
    double oppy = 1 - diffy;

    if ((x==511) || (y==511)) return val[mapw*x+y];

    return (val[x*mapw+y]*oppx + val[(x+1)*mapw+y]*diffx)*oppy + \
        (val[x*mapw+y+1]*oppx + val[(x+1)*mapw+y+1]*diffx)*diffy;
}

int main ()
{
    if ( SDL_Init(SDL_INIT_VIDEO) < 0 )
    {
        fprintf(stderr, "Cannot initialize SDL: %s\n", SDL_GetError());
        exit(1);
    }

    SDL_Surface *screen;
    screen = SDL_SetVideoMode(scw, sch, 8, SDL_SWSURFACE|SDL_HWPALETTE);
    if ( screen == NULL )
    {// Если установить разрешение не удалось
        fprintf(stderr, "Cannot set resolution %ix%i: %s\n", scw, sch, SDL_GetError());
        exit(1);
    }

    fillpalette (screen);
    int hei[mapw*maph-1];
    int col[mapw*maph-1];
    filldata (hei, col);

    int posx = 0;
    int posy = 0;

    double ang = 0;
    int horiz = -100;

    double dd = 3.0;
    double de = dd * 128; // 128 is the max "distance"
    double x,y,z;

    double amax = M_PI/2.6;
    double a;
    int sx;

    int maxh[scw];

    int bin1 = mapw*(maph-1);
    int bin2 = maph-1;
    
    while (1)
    {
        SDL_LockSurface(screen);

        blacken_screen (screen);

        int startidx = ((posx*mapw) & bin1) + (posy&bin2);
        int starth = hei[startidx];
        int posz = 250+starth/2;
//        int posz = 400;

        double sinang = sin(ang);
        double cosang = cos(ang);
        
        fillarray (maxh, sch-1, scw);
        for (sx=0;sx<scw;sx++)
        {
            double d;

            a = amax*sx/scw;
            double tana = tan (a);
            for (d=0;d<=de;d+=dd)
            {
                double y1 = d*/*cos(amax)**/tana;
                double x1 = d;//*cos(amax);

                x = posx + x1*cosang+y1*sinang;
                y = posy - x1*sinang+y1*cosang;
                z = posz - d;//*sin(amax);
                
                int xdiv = x/mapw;
                int ydiv = y/maph;
                x = fabs (x - xdiv*mapw);
                y = fabs (y - ydiv*maph);
                int h = get_filtered_val (hei, x, y);

                int sy = sch/2 + 40*(z-h)/(d+1);
                if (sy<0) sy = 0;
                if (sy>sch-1) sy = sch-1;

                if (sy<maxh[sx])
                {
                    int startpos = maxh[sx];
                    maxh[sx]=sy;
                    int syi;
                    for (syi=startpos; syi>=sy; syi--)
                    {

                        int color = get_filtered_val (col, x, y);
                        *((Uint8*)screen->pixels+sx+scw*syi) = color;
                    }
                }
            }
        }

        SDL_UnlockSurface(screen);
        SDL_Flip (screen);
        checkevents (&ang, &posx, &posy);
        }

    return atexit(SDL_Quit);
}