summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore7
-rw-r--r--SConstruct27
-rw-r--r--main.cpp331
-rw-r--r--quadtree.cpp302
-rw-r--r--quadtree.h39
-rw-r--r--scene.cpp46
-rw-r--r--scene.h16
-rw-r--r--vector.cpp146
-rw-r--r--vector.h49
-rw-r--r--video.cpp65
-rw-r--r--video.h18
11 files changed, 1046 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..16c9d65
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,7 @@
+.sconsign.dblite
+/foo
+*.o
+*.ttf
+*.png
+*.jpg
+.*.swp
diff --git a/SConstruct b/SConstruct
new file mode 100644
index 0000000..1e7d2e3
--- /dev/null
+++ b/SConstruct
@@ -0,0 +1,27 @@
+import os
+
+env = Environment(
+ ENV = os.environ,
+)
+
+AddOption('--release', action = 'store_true')
+AddOption('--profiling', action = 'store_true')
+
+env.Append(CPPPATH = ['.'])
+env.Append(LIBS = ['GL', 'GLU'])
+env.ParseConfig('sdl-config --cflags --libs')
+env.ParseConfig('pkg-config --cflags --libs SDL_image')
+env.ParseConfig('pkg-config --cflags --libs ftgl')
+
+if not GetOption('release'):
+ env.Append(CPPFLAGS = ['-Wall', '-g'])
+
+if GetOption('profiling'):
+ env.Append(CPPFLAGS = ['-pg'])
+ env.Append(LINKFLAGS = ['-pg'])
+
+Export('env')
+
+env.Program('foo', Glob('*.cpp'))
+
+# vim: syn=python
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..b653427
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,331 @@
+#include "video.h"
+#include "scene.h"
+#include "vector.h"
+#include "quadtree.h"
+
+#include <SDL_image.h>
+#include <FTGL/ftgl.h>
+#include <boost/format.hpp>
+#include <boost/shared_ptr.hpp>
+
+#define GL_GLEXT_PROTOTYPES
+#include <SDL_opengl.h>
+//#include <GL/gl.h>
+#include <GL/gl.h>
+//#include <GL/glu.h>
+
+#include <iostream>
+#include <cmath>
+#include <list>
+#include <vector>
+#include <map>
+#include <queue>
+
+FTFont *font;
+
+Scene scene;
+
+struct hit_record {
+ uint32_t hits;
+ int32_t min_z;
+ int32_t max_z;
+ uint32_t name;
+};
+
+// TODO: reimplement
+int select(Quadtree& qt, int x, int y) {
+ y = 600-y;
+ glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+
+ GLuint buf[64] = {0};
+ GLint hits, view[4] = {0};
+ uint32_t id = 0;
+ glSelectBuffer(64, buf);
+ glGetIntegerv(GL_VIEWPORT, view);
+ glRenderMode(GL_SELECT);
+ glInitNames();
+
+ //glPushName(0);
+ glMatrixMode(GL_PROJECTION);
+ glPushMatrix();
+ glLoadIdentity();
+ gluPickMatrix(x, y, 1, 1, view);
+ gluPerspective(45, (float)view[2] / (float)view[3], 1, 10000);
+ glMatrixMode(GL_MODELVIEW);
+ glLoadIdentity();
+ scene.lookat();
+
+ std::vector<Quadtree::QuadNode*> nodes;
+ uint32_t index = 0;
+ std::queue<Quadtree::QuadNode*> q;
+ q.push(qt.root);
+ while(!q.empty()) {
+ Quadtree::QuadNode *node = q.front();
+ q.pop();
+ if(node->vertex_array) {
+ glPushName(++index);
+ /*glBegin(GL_QUADS);
+ glVertex3f(node->x - node->width/2,
+ glEnd();*/
+ glPopName();
+ node->draw();
+ } else
+ for(int i = 0; i < 4; i++)
+ q.push(node->children[i]);
+ }
+ glMatrixMode(GL_PROJECTION);
+ glPopMatrix();
+ //glMatrixMode(GL_MODELVIEW);
+ //glFlush();
+ hits = glRenderMode(GL_RENDER);
+ //std::cout << "hits: " << hits << std::endl;
+ for(int i = 0; i < hits; i++) {
+ struct hit_record *hit = (struct hit_record*)(buf + i*sizeof(hit_record));
+ //std::cout << " hits: " << hit->hits << " min_z: " << hit->min_z << " max_z: " << hit->max_z << std::endl;
+ if(hit->hits == 1 && hit->name > 0)
+ id = hit->name;
+ }
+ glMatrixMode(GL_MODELVIEW);
+ //std::cout << "id: " << id << std::endl;
+ if(id > 0) {
+ //return map[vectors[id-1]];
+ }
+ //return Vector3::p();
+ //return id;
+ return 0;
+}
+
+int main(int argc, char **argv) {
+ video::width = 800;
+ video::height = 600;
+ video::init();
+
+ font = new FTTextureFont("font.ttf");
+ font->FaceSize(10);
+
+ SDL_Surface *hm = IMG_Load("heightmap6.png");
+ unsigned char *pixels = (unsigned char*)hm->pixels;
+ float *heightmap = new float[hm->w * hm->h];
+ for(int x = 0; x < hm->w; x++) {
+ for(int y = 0; y < hm->h; y++) {
+ heightmap[y*hm->w + x] = ((float)(pixels[y*hm->w + x]) / 256) * 20;
+ }
+ }
+ int level = 3;
+ Quadtree *qt = new Quadtree(hm->w, hm->h, heightmap, level);
+ //Quadtree qt(qt_size, qt_size, (int)ceil(sqrt(qt_size)));
+
+ GLuint grass_texture;
+ {
+ SDL_Surface *surface = IMG_Load("Grass0073_3_S.jpg");
+ SDL_Surface *image = SDL_CreateRGBSurface(SDL_SWSURFACE, surface->w, surface->h, 32,
+ 0x000000ff, 0x0000ff00, 0x00ff0000, 0xff000000);
+ SDL_Rect area;
+ area.x = area.y = 0;
+ area.w = surface->w;
+ area.h = surface->h;
+ SDL_BlitSurface(surface, &area, image, &area);
+ //glPixelStorei(GL_UNPACK_ALIGNMENT, 4);
+ glGenTextures(1, &grass_texture);
+ glBindTexture(GL_TEXTURE_2D, grass_texture);
+ glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_LINEAR);
+ glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR_MIPMAP_LINEAR);
+ if(image->format->Amask) {
+ //glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, image->w, image->h, 0, GL_RGBA, GL_UNSIGNED_BYTE, image->pixels);
+ gluBuild2DMipmaps(GL_TEXTURE_2D, 4, image->w, image->h, GL_RGBA, GL_UNSIGNED_BYTE, image->pixels);
+ } else {
+ //glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, image->w, image->h, 0, GL_RGB, GL_UNSIGNED_BYTE, image->pixels);
+ gluBuild2DMipmaps(GL_TEXTURE_2D, 3, image->w, image->h, GL_RGB, GL_UNSIGNED_BYTE, image->pixels);
+ }
+ SDL_FreeSurface(surface);
+ SDL_FreeSurface(image);
+ }
+
+ //SDL_WM_GrabInput(SDL_GRAB_ON);
+
+ SDL_Event event;
+ bool running = true;
+ bool grid = false;
+ SDL_WarpMouse(video::width/2, video::height/2);
+ unsigned int last_time = SDL_GetTicks();
+ /*boost::timer t;
+ double last_time = 0;*/
+ while(running) {
+ unsigned int time = SDL_GetTicks();
+ //double time = t.elapsed();
+ //t.restart();
+ unsigned int steps = time - last_time + 1;
+ //double steps = (time - last_time) * 1000;
+ last_time = time;
+ while(SDL_PollEvent(&event)) {
+ switch(event.type) {
+ case SDL_QUIT:
+ running = false;
+ break;
+ case SDL_KEYDOWN:
+ switch(event.key.keysym.sym) {
+ case SDLK_ESCAPE:
+ running = false;
+ break;
+ case SDLK_g:
+ grid = !grid;
+ break;
+ case SDLK_KP_PLUS:
+ delete qt;
+ qt = new Quadtree(hm->w, hm->h, heightmap, ++level);
+ break;
+ case SDLK_KP_MINUS:
+ if(level > 0) {
+ delete qt;
+ qt = new Quadtree(hm->w, hm->h, heightmap, --level);
+ }
+ break;
+ case SDLK_SPACE:
+ scene.yvel = .05;
+ break;
+ default:
+ break;
+ }
+ break;
+ case SDL_MOUSEBUTTONUP:
+ switch(event.button.button) {
+ case SDL_BUTTON_LEFT:
+ // TODO: reimplement selection
+ break;
+ case SDL_BUTTON_WHEELUP:
+ case SDL_BUTTON_WHEELDOWN:
+ // TODO: reimplement?
+ break;
+ }
+ case SDL_MOUSEMOTION:
+ if(event.motion.x == video::width/2 && event.motion.y == video::height/2)
+ break;
+ scene.yaw += (float)event.motion.xrel / 500;
+ scene.pitch += (float)event.motion.yrel / 500;
+ if(scene.yaw > 2*M_PI)
+ scene.yaw -= 2*M_PI;
+ else if(scene.yaw < 0)
+ scene.yaw += 2*M_PI;
+ if(scene.pitch > M_PI)
+ scene.pitch = M_PI;
+ else if(scene.pitch < 0)
+ scene.pitch = 0;
+ SDL_WarpMouse(video::width/2, video::height/2);
+ break;
+ }
+ }
+
+ glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+ glLoadIdentity();
+ video::persp();
+
+ unsigned char *keystate = SDL_GetKeyState(NULL);
+ float forward = 0;
+ float right = 0;
+ bool moved = false;
+ if(keystate[SDLK_w]) {
+ moved = true;
+ forward++;
+ }
+ if(keystate[SDLK_s]) {
+ moved = true;
+ forward--;
+ }
+ if(keystate[SDLK_a]) {
+ moved = true;
+ right--;
+ }
+ if(keystate[SDLK_d]) {
+ moved = true;
+ right++;
+ }
+ if(keystate[SDLK_q])
+ scene.pos.y -= 0.002*steps;
+ if(keystate[SDLK_e])
+ scene.pos.y += 0.002*steps*(keystate[SDLK_LSHIFT]?10:1);
+ if(moved && (forward || right))
+ scene.move(forward, right, steps*(keystate[SDLK_LSHIFT]?10:1));
+
+ std::string move_str;
+ {
+ Quadtree::QuadNode *node = qt->find(scene.pos.x, scene.pos.z);
+ if(node) {
+ float y = node->get_height(scene.pos.x, scene.pos.z);
+ if(scene.pos.y > y && !keystate[SDLK_e])
+ scene.yvel -= 9.81 * steps / 85000;
+ if(scene.yvel < -.5)
+ scene.yvel = -.5;
+ scene.pos.y += scene.yvel;
+ if(scene.pos.y < y) {
+ scene.pos.y = y;
+ scene.yvel = 0;
+ }
+ move_str = (boost::format("%s %.2f,%.2f %dx%d") % scene.pos.str() % node->x % node->y % node->width % node->height).str();
+ }
+ }
+
+ scene.lookat();
+
+ glEnable(GL_LIGHTING);
+ //const float light_pos[4] = {50, 20, 50, 1};
+ const float light_pos[4] = {0, 1, 0, 0};
+ glLightfv(GL_LIGHT0, GL_POSITION, light_pos);
+
+ if(!grid) {
+ glBindTexture(GL_TEXTURE_2D, grass_texture);
+ glEnable(GL_TEXTURE_2D);
+ glBindBuffer(GL_ARRAY_BUFFER, qt->vbo_object);
+ glVertexPointer(3, GL_FLOAT, 0, NULL);
+ glNormalPointer(GL_FLOAT, 0, (GLvoid*)(qt->vertices*3*sizeof(float)));
+ glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(qt->vertices*3*sizeof(float)*2));
+ glEnableClientState(GL_VERTEX_ARRAY);
+ glEnableClientState(GL_NORMAL_ARRAY);
+ glEnableClientState(GL_TEXTURE_COORD_ARRAY);
+ glDrawArrays(GL_TRIANGLES, 0, qt->vertices);
+ glDisableClientState(GL_VERTEX_ARRAY);
+ glDisableClientState(GL_NORMAL_ARRAY);
+ glDisableClientState(GL_TEXTURE_COORD_ARRAY);
+ } else {
+ std::queue<Quadtree::QuadNode*> q;
+ q.push(qt->root);
+ glBindTexture(GL_TEXTURE_2D, grass_texture);
+ glEnable(GL_TEXTURE_2D);
+ while(!q.empty()) {
+ Quadtree::QuadNode *node = q.front();
+ q.pop();
+ if(node->vertex_array) {
+ grid ? node->draw_grid() : node->draw();
+ } else
+ for(int i = 0; i < 4; i++)
+ q.push(node->children[i]);
+ }
+ }
+
+ glDisable(GL_TEXTURE_2D);
+ glDisable(GL_LIGHTING);
+
+ video::ortho();
+ float height = font->LineHeight();
+ glColor3f(1, 1, 1);
+ glTranslatef(0, 600-height, 0);
+ font->Render((boost::format("%dx%d %d levels %d nodes tree creation time: %f steps: %d")
+ % qt->width % qt->height % qt->levels % qt->nodes % qt->init_time % steps).str().c_str());
+ //glTranslatef(0, height, 0);
+ //font->Render((boost::format("selected: %x") % selected).str().c_str());
+ glTranslatef(0, -height, 0);
+ font->Render(move_str.c_str());
+ /*if(selected) {
+ glTranslatef(0, height, 0);
+ //font->Render((boost::format("(%s %s %s %s)") % selected->a->str() % selected->b->str() % selected->c->str() % selected->d->str()).str().c_str());
+ font->Render(selected->str().c_str());
+ }*/
+
+ SDL_GL_SwapBuffers();
+
+ usleep(1000);
+ }
+
+ video::free();
+
+ return 0;
+}
diff --git a/quadtree.cpp b/quadtree.cpp
new file mode 100644
index 0000000..33011d5
--- /dev/null
+++ b/quadtree.cpp
@@ -0,0 +1,302 @@
+#include "quadtree.h"
+#include "vector.h"
+
+#include <boost/format.hpp>
+#include <boost/timer.hpp>
+
+#define GL_GLEXT_PROTOTYPES
+#include <GL/gl.h>
+
+#include <iostream>
+#include <cmath>
+#include <queue>
+
+Quadtree::Quadtree(int width, int height, float *heightmap, int levels) {
+ this->width = width;
+ this->height = height;
+ vbo_object = 0;
+
+ int l = log2f(width);
+ if(levels > l) {
+ levels = l;
+ }
+ heights = heightmap;
+ this->levels = levels;
+
+ boost::timer t;
+ root = new QuadNode(this, NULL, 0, 0, width, height, 1, levels == 0);
+ std::queue<Quadtree::QuadNode*> q;
+ if(levels > 0)
+ q.push(root);
+ while(!q.empty()) {
+ Quadtree::QuadNode *node = q.front();
+ q.pop();
+ node->subdivide(node->level == levels);
+ if(node->level < levels) {
+ for(int i = 0; i < 4; i++)
+ q.push(node->children[i]);
+ }
+ }
+
+ make_vbo();
+
+ init_time = t.elapsed();
+}
+
+Quadtree::~Quadtree() {
+ if(vbo_object)
+ glDeleteBuffers(1, &vbo_object);
+ delete root;
+ //delete[] heights;
+}
+
+Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf) {
+ this->tree = tree;
+ this->parent = parent;
+ this->x = x;
+ this->y = y;
+ this->width = width;
+ this->height = height;
+ this->level = level;
+ children[0] = children[1] = children[2] = children[3] = NULL;
+ if(!leaf) {
+ elems = 0;
+ vertex_array = NULL;
+ return;
+ }
+ elems = 3*5;
+ int size = sizeof(float)*elems;
+ vertex_array = new float[size];
+ vertex_array[0] = x + width / 2;
+ vertex_array[1] = tree->heights[(int)floorf((int)(x + width/2)*tree->height + (int)(y + height/2))];
+ vertex_array[2] = y + height / 2;
+
+ vertex_array[3] = x;
+ vertex_array[4] = tree->heights[(int)floorf(x*tree->height+y)];
+ vertex_array[5] = y;
+
+ vertex_array[6] = x;
+ vertex_array[7] = tree->heights[(int)floorf(x*tree->height + (y + height))];
+ vertex_array[8] = y + height;
+
+ vertex_array[9] = x + width;
+ vertex_array[10] = tree->heights[(int)floorf((x + width)*tree->height + (y + height))];
+ vertex_array[11] = y + height;
+
+ vertex_array[12] = x + width;
+ vertex_array[13] = tree->heights[(int)floorf((x + width)*tree->height + y)];
+ vertex_array[14] = y;
+}
+
+Quadtree::QuadNode::~QuadNode() {
+ if(vertex_array)
+ delete[] vertex_array;
+ for(int i = 0; i < 4; i++)
+ if(children[i])
+ delete children[i];
+}
+
+void Quadtree::QuadNode::subdivide(bool leaf) {
+ if(vertex_array) {
+ elems = 0;
+ delete[] vertex_array;
+ vertex_array = NULL;
+ }
+
+ for(int i = 0; i < 4; i++) {
+ float nx = x + ((i & 1) ^ ((i & 2) >> 1)) * width / 2;
+ float ny = y + ((i & 2) >> 1) * height / 2;
+ children[i] = new QuadNode(tree, this, nx, ny, width / 2, height / 2, level + 1, leaf);
+ }
+}
+
+void Quadtree::QuadNode::draw() {
+ if(!vertex_array)
+ return;
+
+ float tex_coords[4][3][2] = {
+ {{.5, .5}, {0, 0}, {0, 1}},
+ {{.5, .5}, {0, 1}, {1, 1}},
+ {{.5, .5}, {1, 1}, {1, 0}},
+ {{.5, .5}, {1, 0}, {0, 0}}
+ };
+
+ glBegin(GL_TRIANGLES);
+ for(int i = 0; i < 4; i++) {
+ Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+ Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
+ Vector3 c(vertex_array[i == 3 ? 3 : (i*3+6)], vertex_array[i == 3 ? 4 : (i*3+7)], vertex_array[i == 3 ? 5 : (i*3+8)]);
+
+ Vector3 U(c.x-a.x, c.y-a.y, c.z-a.z);
+ Vector3 V(b.x-a.x, b.y-a.y, b.z-a.z);
+ Vector3 N(V.cross(U));
+ glNormal3f(N.x, N.y, N.z);
+
+ glTexCoord2f(tex_coords[i][0][0], tex_coords[i][0][1]);
+ glVertex3f(a.x, a.y, a.z);
+
+ glTexCoord2f(tex_coords[i][1][0], tex_coords[i][1][1]);
+ glVertex3f(b.x, b.y, b.z);
+
+ glTexCoord2f(tex_coords[i][2][0], tex_coords[i][2][1]);
+ glVertex3f(c.x, c.y, c.z);
+ }
+ glEnd();
+}
+
+void Quadtree::QuadNode::draw_grid() {
+ if(!vertex_array)
+ return;
+
+ glNormal3f(0, 1, 0);
+ glBegin(GL_LINES);
+ for(int i = 0; i < 4; i++) {
+ Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+ Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
+
+ glVertex3f(a.x, a.y, a.z);
+ glVertex3f(b.x, b.y, b.z);
+ }
+ glEnd();
+ glBegin(GL_LINE_LOOP);
+ glVertex3f(vertex_array[3], vertex_array[4], vertex_array[5]);
+ glVertex3f(vertex_array[6], vertex_array[7], vertex_array[8]);
+ glVertex3f(vertex_array[9], vertex_array[10], vertex_array[11]);
+ glVertex3f(vertex_array[12], vertex_array[13], vertex_array[14]);
+ glEnd();
+}
+
+float Quadtree::QuadNode::get_height(float px, float py) {
+ bool left;
+ bool top;
+ top = px - x >= height - (py - y);
+ left = px - x >= py - y;
+ Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+ Vector3 b, c;
+ int bi, ci;
+ if(left) {
+ if(top) {
+ bi = 3*3;
+ ci = 4*3;
+ } else {
+ bi = 4*3;
+ ci = 1*3;
+ }
+ } else {
+ if(top) {
+ bi = 2*3;
+ ci = 3*3;
+ } else {
+ bi = 1*3;
+ ci = 2*3;
+ }
+ }
+ b = Vector3(vertex_array[bi], vertex_array[bi+1], vertex_array[bi+2]);
+ c = Vector3(vertex_array[ci], vertex_array[ci+1], vertex_array[ci+2]);
+ float det1 = (b.z - c.z) * (a.x - c.x) + (c.x - b.x) * (a.z - c.z);
+ float det2 = (c.z - a.z) * (b.x - c.x) + (a.x - c.x) * (b.z - c.z);
+ float l1 = ((b.z - c.z) * (px - c.x) + (c.x - b.x) * (py - c.z)) / det1;
+ float l2 = ((c.z - a.z) * (px - c.x) + (a.x - c.x) * (py - c.z)) / det2;
+ float l3 = 1 - l1 - l2;
+ return l1 * a.y + l2 * b.y + l3 * c.y;
+}
+
+unsigned int Quadtree::count_nodes() {
+ std::queue<Quadtree::QuadNode*> q;
+ q.push(root);
+ unsigned int count = 0;
+ while(!q.empty()) {
+ Quadtree::QuadNode *node = q.front();
+ q.pop();
+
+ if(!node->vertex_array) {
+ for(int i = 0; i < 4; i++)
+ q.push(node->children[i]);
+ } else {
+ count++;
+ }
+ }
+
+ return count;
+}
+
+void Quadtree::make_vbo() {
+ nodes = count_nodes();
+ if(vbo_object)
+ glDeleteBuffers(1, &vbo_object);
+ glGenBuffers(1, &vbo_object);
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_object);
+ const size_t vertex_chunk_size = sizeof(float)*3*12;
+ const size_t vertices_size = vertex_chunk_size*nodes;
+ const size_t normal_chunk_size = vertex_chunk_size;
+ const size_t normals_size = normal_chunk_size*nodes;
+ const size_t tex_coord_chunk_size = sizeof(float)*2*12;
+ const size_t tex_coords_size = tex_coord_chunk_size*nodes;
+
+ glBufferData(GL_ARRAY_BUFFER, vertices_size + normals_size + tex_coords_size, NULL, GL_DYNAMIC_DRAW);
+
+ std::queue<Quadtree::QuadNode*> q;
+ q.push(root);
+ unsigned int offset = 0;
+ vertices = nodes*12;
+ unsigned int index = 0;
+ while(!q.empty()) {
+ Quadtree::QuadNode* n = q.front();
+ q.pop();
+ if(!n->vertex_array) {
+ for(int j = 0; j < 4; j++)
+ q.push(n->children[j]);
+ continue;
+ }
+ int size = 12*3*sizeof(float);
+ float v[3*12];
+ v[0] = n->vertex_array[0];
+ v[1] = n->vertex_array[1];
+ v[2] = n->vertex_array[2];
+ float tex_coords[4][3][2] = {
+ {{.5, .5}, {0, 0}, {0, 1}},
+ {{.5, .5}, {0, 1}, {1, 1}},
+ {{.5, .5}, {1, 1}, {1, 0}},
+ {{.5, .5}, {1, 0}, {0, 0}}
+ };
+ for(int i = 0; i < 4; i++) {
+ v[3] = n->vertex_array[i*3+3];
+ v[4] = n->vertex_array[i*3+4];
+ v[5] = n->vertex_array[i*3+5];
+
+ v[6] = n->vertex_array[i == 3 ? 3 : (i*3+6)];
+ v[7] = n->vertex_array[i == 3 ? 4 : (i*3+7)];
+ v[8] = n->vertex_array[i == 3 ? 5 : (i*3+8)];
+ glBufferSubData(GL_ARRAY_BUFFER, vertex_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, v);
+
+ Vector3 U(v[6]-v[0], v[7]-v[1], v[8]-v[2]);
+ Vector3 V(v[3]-v[0], v[4]-v[1], v[5]-v[2]);
+ Vector3 N(V.cross(U));
+ float n[3*3];
+ n[0] = n[3] = n[6] = N.x;
+ n[1] = n[4] = n[7] = N.y;
+ n[2] = n[5] = n[8] = N.z;
+
+ glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normal_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, n);
+ }
+ glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normals_size + tex_coord_chunk_size*index, tex_coord_chunk_size, tex_coords);
+ index++;
+ offset += size;
+ }
+}
+
+Quadtree::QuadNode* Quadtree::find(float x, float y) {
+ QuadNode *node = root;
+ while(!node->vertex_array) {
+ float mx = node->x + node->width / 2;
+ float my = node->y + node->height / 2;
+ int i = 2*(y > my);
+ if(i < 2 && x > mx)
+ i = 1;
+ else if(i == 2 && x < mx)
+ i = 3;
+ node = node->children[i];
+ }
+
+ return node;
+}
diff --git a/quadtree.h b/quadtree.h
new file mode 100644
index 0000000..9a84e98
--- /dev/null
+++ b/quadtree.h
@@ -0,0 +1,39 @@
+#ifndef QUADTREE_H
+#define QUADTREE_H
+
+class Quadtree {
+ public:
+ struct QuadNode {
+ Quadtree *tree;
+ QuadNode *parent;
+ QuadNode *children[4];
+ int elems;
+ float x, y, width, height;
+ int level;
+ float *vertex_array;
+
+ QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf);
+ virtual ~QuadNode();
+
+ void subdivide(bool leaf = true);
+ void draw();
+ void draw_grid();
+ float get_height(float px, float py);
+ };
+
+ float *heights;
+ int width, height, levels;
+ float init_time;
+ QuadNode *root;
+ unsigned int vbo_object;
+ unsigned int nodes;
+ unsigned int vertices;
+ Quadtree(int width, int height, float *heightmap, int levels);
+ virtual ~Quadtree();
+
+ unsigned int count_nodes();
+ void make_vbo();
+ QuadNode *find(float x, float y);
+};
+
+#endif
diff --git a/scene.cpp b/scene.cpp
new file mode 100644
index 0000000..47b76bf
--- /dev/null
+++ b/scene.cpp
@@ -0,0 +1,46 @@
+#include "scene.h"
+
+#include <SDL_opengl.h>
+
+#include <cmath>
+
+#define inrange(a, b, c) ((a) >= (b) && (a) <= (c))
+
+void Scene::lookat() {
+ /* calculate cartesian coordinates for the center vector where yaw is Φ and pitch is θ
+ * x = cos Φ sin θ
+ * y = cos θ
+ * z = sin Φ sin θ
+ */
+ Vector3 center(sinf(pitch) * cosf(yaw), cosf(pitch), sinf(pitch) * sinf(yaw));
+ center += pos;
+ center.y += 1;
+ //Vector3 up(cosf(yaw) * cosf(pitch), sinf(pitch), sinf(yaw) * cosf(pitch));
+ Vector3 up(-cosf(pitch) * cosf(yaw), sinf(pitch), -cosf(pitch) * sinf(yaw));
+ gluLookAt(pos.x, pos.y+1, pos.z,
+ center.x, center.y, center.z,
+ up.x, up.y, up.z);
+}
+
+void Scene::move(float forward, float right, int steps) {
+ Vector2 dir;
+ dir.x += forward*cosf(yaw);
+ dir.y += forward*sinf(yaw);
+
+ dir.x += right*cosf(yaw+M_PI_2);
+ dir.y += right*sinf(yaw+M_PI_2);
+
+ // ensure that the vector length is 1.0
+ dir /= dir.length();
+ dir *= 0.005;
+ dir *= steps;
+
+ float x = pos.x + dir.x;
+ //if(inrange(x, -2, 2))
+ pos.x = x;
+ float z = pos.z + dir.y;
+ //if(inrange(z, -2, 2))
+ pos.z = z;
+ //pos.x += dir.x;
+ //pos.z += dir.y;
+}
diff --git a/scene.h b/scene.h
new file mode 100644
index 0000000..7ae50b8
--- /dev/null
+++ b/scene.h
@@ -0,0 +1,16 @@
+#ifndef SCENE_H
+#define SCENE_H
+
+#include "vector.h"
+
+class Scene {
+ public:
+ float pitch, yaw;
+ Vector3 pos;
+ float yvel;
+
+ void lookat();
+ void move(float forward, float right, int steps);
+};
+
+#endif
diff --git a/vector.cpp b/vector.cpp
new file mode 100644
index 0000000..2da8c99
--- /dev/null
+++ b/vector.cpp
@@ -0,0 +1,146 @@
+#include "vector.h"
+
+#include <boost/format.hpp>
+
+#include <cmath>
+#include <string>
+
+Vector2::Vector2() {
+ x = y = 0;
+}
+
+Vector2::Vector2(const Vector2& v) {
+ x = v.x;
+ y = v.y;
+}
+
+Vector2::Vector2(float x, float y) {
+ this->x = x;
+ this->y = y;
+}
+
+bool Vector2::operator==(const Vector2& v) const {
+ return x == v.x && y == v.y;
+}
+
+Vector2& Vector2::operator+=(const Vector2& v) {
+ x += v.x;
+ y += v.y;
+ return *this;
+}
+
+Vector2& Vector2::operator-=(const Vector2& v) {
+ x -= v.x;
+ y -= v.y;
+ return *this;
+}
+
+Vector2 Vector2::operator-(const Vector2& v) {
+ return Vector2(*this) -= v;
+}
+
+Vector2& Vector2::operator*=(const float f) {
+ x *= f;
+ y *= f;
+ return *this;
+}
+
+Vector2& Vector2::operator/=(const float f) {
+ x /= f;
+ y /= f;
+ return *this;
+}
+
+float Vector2::length() {
+ return sqrtf(x*x + y*y);
+}
+
+std::string Vector2::str() {
+ return (boost::format("[%.2f %.2f]") % x % y).str();
+}
+
+/**
+ * Vector3
+ */
+
+Vector3::Vector3() {
+ x = y = z = 0;
+}
+
+Vector3::Vector3(const Vector3& v) : Vector2(v) {
+ z = v.z;
+}
+
+Vector3::Vector3(float x, float y, float z) : Vector2(x, y) {
+ this->z = z;
+}
+
+bool Vector3::operator==(const Vector3& v) {
+ return x == v.x && y == v.y && z == v.z;
+}
+
+Vector3& Vector3::operator+=(const Vector3& v) {
+ x += v.x;
+ y += v.y;
+ z += v.z;
+ return *this;
+}
+
+Vector3 Vector3::operator+(const Vector3& v) {
+ return Vector3(*this) += v;
+}
+
+Vector3& Vector3::operator-=(const Vector3& v) {
+ x -= v.x;
+ y -= v.y;
+ z -= v.z;
+ return *this;
+}
+
+Vector3 Vector3::operator-(const Vector3& v) {
+ return Vector3(*this) -= v;
+}
+
+Vector3& Vector3::operator*=(const float f) {
+ x *= f;
+ y *= f;
+ z *= f;
+ return *this;
+}
+
+Vector3 Vector3::operator*(const float f) {
+ return Vector3(*this) *= f;
+}
+
+Vector3& Vector3::operator/=(const float f) {
+ x /= f;
+ y /= f;
+ z /= f;
+ return *this;
+}
+
+Vector3 Vector3::operator/(const float f) {
+ return Vector3(*this) /= f;
+}
+
+Vector3 Vector3::cross(const Vector3& v) {
+ return Vector3(y*v.z - z*v.y,
+ z*v.x - x*v.z,
+ x*v.y - y*v.x);
+}
+
+float Vector3::dot(const Vector3& v) {
+ return x*v.x + y*v.y + z*v.z;
+}
+
+Vector2 Vector3::xz() {
+ return Vector2(x, z);
+}
+
+float Vector3::length() {
+ return sqrtf(x*x + y*y + z*z);
+}
+
+std::string Vector3::str() {
+ return (boost::format("[%.2f %.2f %.2f]") % x % y % z).str();
+}
diff --git a/vector.h b/vector.h
new file mode 100644
index 0000000..48deb87
--- /dev/null
+++ b/vector.h
@@ -0,0 +1,49 @@
+#ifndef VECTOR_H
+#define VECTOR_H
+
+#include <boost/shared_ptr.hpp>
+
+#include <string>
+
+class Vector2 {
+ public:
+ float x, y;
+
+ Vector2();
+ Vector2(const Vector2& v);
+ Vector2(float x, float y);
+ bool operator==(const Vector2& v) const;
+ Vector2& operator+=(const Vector2& v);
+ Vector2& operator-=(const Vector2& v);
+ Vector2 operator-(const Vector2& v);
+ Vector2& operator*=(const float f);
+ Vector2& operator/=(const float f);
+ float length();
+ std::string str();
+};
+
+class Vector3 : public Vector2 {
+ public:
+ typedef boost::shared_ptr<Vector3> p;
+ float z;
+
+ Vector3();
+ Vector3(const Vector3& v);
+ Vector3(float x, float y, float z);
+ bool operator==(const Vector3& v);
+ Vector3& operator+=(const Vector3& v);
+ Vector3 operator+(const Vector3& v);
+ Vector3& operator-=(const Vector3& v);
+ Vector3 operator-(const Vector3& v);
+ Vector3& operator*=(const float f);
+ Vector3 operator*(const float f);
+ Vector3& operator/=(const float f);
+ Vector3 operator/(const float f);
+ Vector3 cross(const Vector3& v);
+ float dot(const Vector3& v);
+ Vector2 xz();
+ float length();
+ std::string str();
+};
+
+#endif
diff --git a/video.cpp b/video.cpp
new file mode 100644
index 0000000..6ebe170
--- /dev/null
+++ b/video.cpp
@@ -0,0 +1,65 @@
+#include "video.h"
+
+#include <GL/gl.h>
+#include <GL/glu.h>
+
+SDL_Surface *video::surface = NULL;
+int video::width = 800;
+int video::height = 600;
+
+void video::init() {
+ SDL_Init(SDL_INIT_VIDEO);
+
+ surface = SDL_SetVideoMode(width, height, 32, SDL_OPENGL);
+
+ glClearColor(0, 0, 0, 0);
+ glClearDepth(1);
+ glDepthFunc(GL_LESS);
+ glEnable(GL_DEPTH_TEST);
+
+ glShadeModel(GL_SMOOTH);
+ glEnable(GL_POINT_SMOOTH);
+
+ glEnable(GL_LIGHTING);
+ glEnable(GL_LIGHT0);
+ //glEnable(GL_COLOR_MATERIAL);
+
+ const float light_ambient[4] = {.2, .2, .2, 1};
+ const float light_diffuse[4] = {1, 1, 1, 1};
+ const float light_specular[4] = {1, 1, 1, 1};
+ glLightfv(GL_LIGHT0, GL_AMBIENT, light_ambient);
+ glLightfv(GL_LIGHT0, GL_DIFFUSE, light_diffuse);
+ glLightfv(GL_LIGHT0, GL_SPECULAR, light_specular);
+
+ //glLightModeli(GL_LIGHT_MODEL_LOCAL_VIEWER, GL_TRUE);
+ //glMaterialf(GL_FRONT_AND_BACK, GL_SHININESS, 0);
+ //glColorMaterial(GL_FRONT_AND_BACK, GL_AMBIENT_AND_DIFFUSE);
+
+ glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);
+
+ persp();
+}
+
+void video::free() {
+ SDL_Quit();
+}
+
+void video::persp() {
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+
+ gluPerspective(45, (float)width/(float)height, .1, 1000);
+
+ glMatrixMode(GL_MODELVIEW);
+ glLoadIdentity();
+}
+
+void video::ortho() {
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+
+ glOrtho(0, width, 0, height, 0, 1);
+
+ glMatrixMode(GL_MODELVIEW);
+ glLoadIdentity();
+}
diff --git a/video.h b/video.h
new file mode 100644
index 0000000..5bb694b
--- /dev/null
+++ b/video.h
@@ -0,0 +1,18 @@
+#ifndef VIDEO_H
+#define VIDEO_H
+
+#include <SDL.h>
+
+namespace video {
+ extern int width;
+ extern int height;
+
+ void init();
+ void free();
+ void persp();
+ void ortho();
+
+ extern SDL_Surface *surface;
+} /* video */
+
+#endif