triangles and fancy stuff

3 files changed, 219 insertions, 41 deletions

diff --git a/main.c b/main.c
index b2f63ce..ea75c32 100644
--- a/main.c
+++ b/main.c
@@ -2,32 +2,38 @@
 #include <stdlib.h>
 #include <assert.h>
 #include <stdio.h>
+#include <pthread.h>
+
 #include "vector.h"
 
 #include <SDL/SDL.h>
 #include <SDL/SDL_video.h>
 
-#define WIDTH 320
-#define HEIGHT 240
+#define WIDTH 40
+#define HEIGHT 30
 
 #define MAX(a, b) ((a>b)?(a):(b))
 #define MIN(a, b) ((a<b)?(a):(b))
 #define SQR(a) ((a)*(a))
 #define SIGN(x) ((x)<0?-1:1)
 
-#define MAX_BOUNCES 2
-#define MOVE_FACTOR .1
+#define MAX_BOUNCES 200
+#define MIN_BOUNCES 2
+#define MOVE_FACTOR .15
+#define TARGET_MS 50
 
+#define PPMOUT
 
 #define MOUSELOOK
 
 struct rgb_t { unsigned char r, g, b; };
 
 struct object_t {
-    enum { SPHERE, PLANE } type;
+    enum { SPHERE, PLANE, TRI } type;
     union {
         struct { vector center; scalar radius; } sphere;
         struct { vector point, normal; } plane;
+        struct { vector points[3]; } tri;
     };
     struct rgb_t color;
     int specularity; /* 0-255 */
@@ -109,6 +115,56 @@ inline bool object_intersects(const struct object_t *obj, vector o, vector d, sc
         *t = t1;
         return true;
     }
+    case TRI:
+    {
+        vector u = vect_sub(obj->tri.points[1], obj->tri.points[0]);
+        vector v = vect_sub(obj->tri.points[2], obj->tri.points[0]);
+        vector normal = vect_cross(u, v);
+        if(vect_abs(normal) == 0)
+        {
+            //printf("degenerate triangle\n");
+            return false;
+        }
+        scalar denom = vect_dot(normal, d);
+        /* doesn't intersect plane of triangle */
+        if(!denom)
+        {
+            //printf("parallel\n");
+            return false;
+        }
+        scalar t1 = vect_dot(normal, vect_sub(obj->tri.points[0], o)) / denom;
+        /* behind camera */
+        if(t1 <= 0)
+        {
+            //printf("behind camera\n");
+            return false;
+        }
+
+        vector pt = vect_add(vect_mul(d, t1), o);
+        vect_to_rect(&pt);
+        scalar uu, uv, vv, wu, wv;
+        uu = vect_dot(u, u);
+        uv = vect_dot(u, v);
+        vv = vect_dot(v, v);
+        vector w = vect_sub(pt, obj->tri.points[0]);
+        wu = vect_dot(w, u);
+        wv = vect_dot(w, v);
+        denom = SQR(uv) - uu * vv;
+        scalar s1 = (uv * wv - vv * wu) / denom;
+        if(s1 < 0. || s1 > 1.)
+        {
+            //printf("not inside\n");
+            return false;
+        }
+        scalar s2 = (uv * wu - uu * wv) / denom;
+        if(s2 < 0. || (s1 + s2) > 1.)
+        {
+            //printf("not inside\n");
+            return false;
+        }
+        *t = t1;
+        return true;
+    }
     }
 }
 
@@ -123,6 +179,10 @@ vector normal_at_point(vector pt, const struct object_t *obj)
     case PLANE:
         normal = obj->plane.normal;
         break;
+    case TRI:
+        normal = vect_cross(vect_sub(obj->tri.points[1], obj->tri.points[2]),
+                            vect_sub(obj->tri.points[3], obj->tri.points[2]));
+        break;
     default:
         assert(false);
     }
@@ -180,7 +240,7 @@ struct rgb_t trace_ray(const struct scene_t *scene, vector orig, vector d, int m
     vector copy = d;
     vect_to_sph(&copy);
 
-    struct rgb_t primary = blend((struct rgb_t) {0xff, 0xff, 0xff}, (struct rgb_t) { 0x00, 0x00, 0xff },
+    struct rgb_t primary = blend((struct rgb_t) {0, 0x96, 0xff}, (struct rgb_t) { 0xfe, 0xfe, 0xfe },
                                  ABS(copy.sph.elevation * 2 / M_PI * 255));
     scalar hit_dist; /* distance from camera in terms of d */
     const struct object_t *hit_obj = scene_intersections(scene, orig, d, &hit_dist, avoid);
@@ -224,7 +284,7 @@ struct rgb_t trace_ray(const struct scene_t *scene, vector orig, vector d, int m
 
             scalar shade = vect_dot(normal, light_dir);
             if(shade > 0)
-                shade_total += shade * scene->lights[i].intensity;
+                shade_total += shade * scene->lights[i].intensity * 1 / (SQR(light_dist));
         }
 
         if(shade_total > 1)
@@ -252,16 +312,16 @@ struct rgb_t trace_ray(const struct scene_t *scene, vector orig, vector d, int m
 void render_lines(unsigned char *fb, int w, int h,
                   const struct scene_t *scene,
                   const struct camera_t *cam,
-                  int start, int end)
+                  int start, int end, int bounces, int worker)
 {
     scalar scale_x = cam->fov_x / w, scale_y = cam->fov_y / h;
 
     vector direction = cam->direction;
     vect_to_sph(&direction);
 
-    for(int y = start; y < end; ++y)
+    for(int y = 0; y < h; ++y)
     {
-        for(int x = 0; x < w; ++x)
+        for(int x = start; x < end; ++x)
         {
             /* trace a ray from the camera into the scene */
             /* figure out how to rotate the offset vector to suit the
@@ -282,12 +342,22 @@ void render_lines(unsigned char *fb, int w, int h,
 
             /* cam->origin and d now form the camera ray */
 
-            struct rgb_t color = trace_ray(scene, cam->origin, d, MAX_BOUNCES, NULL);
+            struct rgb_t color = trace_ray(scene, cam->origin, d, bounces, NULL);
 
+#ifdef PPMOUT
+            fb[y * w * 3 + 3 * x] = color.r;
+            fb[y * w * 3 + 3 * x + 1] = color.g;
+            fb[y * w * 3 + 3 * x + 2] = color.b;
+#else
             fb[y * w * 3 + 3 * x] = color.b;
             fb[y * w * 3 + 3 * x + 1] = color.g;
             fb[y * w * 3 + 3 * x + 2] = color.r;
+#endif
+
         }
+#ifdef PPMOUT
+        printf("Worker %d: %d%% (%d/%d)\n", worker, 100 * y / h, y, h);
+#endif
     }
 }
 
@@ -297,19 +367,20 @@ struct renderinfo_t {
     const struct scene_t *scene;
     const struct camera_t *cam;
     int start, end;
-
+    int bounces;
+    int worker;
 };
 
 void *thread(void *ptr)
 {
     struct renderinfo_t *info = ptr;
-    render_lines(info->fb, info->w, info->h, info->scene, info->cam, info->start, info->end);
+    render_lines(info->fb, info->w, info->h, info->scene, info->cam, info->start, info->end, info->bounces, info->worker);
     return NULL;
 }
 
 void render_scene(unsigned char *fb, int w, int h,
                   const struct scene_t *scene,
-                  const struct camera_t *cam, int n_threads)
+                  const struct camera_t *cam, int n_threads, int n_bounces)
 {
     struct renderinfo_t *info = malloc(sizeof(struct renderinfo_t) * n_threads);
     pthread_t *threads = malloc(sizeof(pthread_t) * n_threads);
@@ -320,8 +391,10 @@ void render_scene(unsigned char *fb, int w, int h,
         info[i].h = h;
         info[i].scene = scene;
         info[i].cam = cam;
-        info[i].start = h * i / n_threads;
-        info[i].end = h * (i + 1) / n_threads;
+        info[i].start = w * i / n_threads;
+        info[i].end = w * (i + 1) / n_threads;
+        info[i].bounces = n_bounces;
+        info[i].worker = i;
         pthread_create(threads + i, NULL, thread, info + i);
     }
 
@@ -331,25 +404,32 @@ void render_scene(unsigned char *fb, int w, int h,
     free(info);
 }
 
+scalar rand_norm(void)
+{
+    return rand() / (scalar)RAND_MAX;
+}
+
 int main()
 {
     struct scene_t scene;
     scene.bg.r = 0x87;
     scene.bg.g = 0xce;
     scene.bg.b = 0xeb;
-    scene.ambient = .2;
+    scene.ambient = .5;
 
-    struct object_t sph[4];
+    struct object_t sph[8];
+
+#if 1
     sph[0].type = SPHERE;
     sph[0].sphere.center = (vector) { RECT, {0, 1, 1 } };
     sph[0].sphere.radius = 1;
     sph[0].color = (struct rgb_t){0, 0, 0xff};
-    sph[0].specularity = 40;
+    sph[0].specularity = 0xf0;
 
     sph[1].type = SPHERE;
     sph[1].sphere.center = (vector) { RECT, {0, 1, -1 } };
     sph[1].sphere.radius = 1;
-    sph[1].color = (struct rgb_t){0, 0, 0xff};
+    sph[1].color = (struct rgb_t){0xff, 0, 0};
     sph[1].specularity = 40;
 
     sph[2].type = SPHERE;
@@ -363,26 +443,81 @@ int main()
     sph[3].plane.normal = (vector) { RECT, {0, 1, 0 } };
     sph[3].color = (struct rgb_t) {0, 0xff, 0};
     sph[3].specularity = 0;
+#endif
 
-    struct light_t lights[1];
-    lights[0].position = (vector) { RECT, {0, 10, 0} };
-    lights[0].intensity = 2;
+    sph[4].type = TRI;
+    sph[4].tri.points[0] = (vector) { RECT, {0, 0, 0 } };
+    sph[4].tri.points[1] = (vector) { RECT, {0, 5, 0 } };
+    sph[4].tri.points[2] = (vector) { RECT, {0, 0, 5 } };
+    sph[4].color = (struct rgb_t) {0xff, 0, 0xff};
+    sph[4].specularity = 0;
+
+    sph[5].type = TRI;
+    sph[5].tri.points[0] = (vector) { RECT, {0, 5, 5 } };
+    sph[5].tri.points[1] = (vector) { RECT, {0, 5, 0 } };
+    sph[5].tri.points[2] = (vector) { RECT, {0, 0, 5 } };
+    sph[5].color = (struct rgb_t) {0xff, 0, 0xff};
+    sph[5].specularity = 0;
+
+    sph[6].type = TRI;
+    sph[6].tri.points[0] = (vector) { RECT, {10, 0, -5 } };
+    sph[6].tri.points[1] = (vector) { RECT, {5, 5, 0 } };
+    sph[6].tri.points[2] = (vector) { RECT, {0, 0, -5 } };
+    sph[6].color = (struct rgb_t) {0xff, 0, 0xff};
+    sph[6].specularity = 0xe0;
+#if 0
+    sph[4].type = PLANE;
+    sph[4].plane.point = (vector) { RECT, {10, 0, 0 } };
+    sph[4].plane.normal = (vector) { RECT, {-1, 0, 0 } };
+    sph[4].color = (struct rgb_t) {224, 223, 91};
+    sph[4].specularity = 0xf0;
+
+    sph[5].type = PLANE;
+    sph[5].plane.point = (vector) { RECT, {-10, 0, 0 } };
+    sph[5].plane.normal = (vector) { RECT, {1, 0, 0 } };
+    sph[5].color = (struct rgb_t) {224, 223, 91};
+    sph[5].specularity = 0xf0;
+
+
+    sph[4].type = PLANE;
+    sph[4].plane.point = (vector) { RECT, {0, 0, -10 } };
+    sph[4].plane.normal = (vector) { RECT, {0, 0, 1 } };
+    sph[4].color = (struct rgb_t) {224, 223, 91};
+    sph[4].specularity = 0xf0;
+
+    sph[5].type = PLANE;
+    sph[5].plane.point = (vector) { RECT, {0, 0, 10 } };
+    sph[5].plane.normal = (vector) { RECT, {0, 0, -1 } };
+    sph[5].color = (struct rgb_t) {224, 223, 91};
+    sph[5].specularity = 0xf0;
+#endif
+
+    /* distribute evenly in a sphere of r = 1 */
+    struct light_t lights[50];
+    for(int i = 0; i < 50; ++i)
+    {
+        lights[i].position = vect_add((vector) { RECT, {5, 10, 0} },
+                                      (vector) { SPH, { .sph.r = rand_norm(),
+                                                  .sph.elevation = 2 * M_PI * (rand_norm() - .5),
+                                                  .sph.azimuth = 4 * M_PI * (rand_norm() - .5) } } );
+        lights[i].intensity = 4;
+    }
 
     scene.objects = sph;
-    scene.n_objects = 4;
+    scene.n_objects = 7;
     scene.lights = lights;
-    scene.n_lights = 1;
+    scene.n_lights = 50;
 
     struct camera_t cam;
-    cam.origin = (vector){ RECT, {-5, 0, 0} };
+    cam.origin = (vector){ RECT, {-5, 2, -1} };
     cam.direction = (vector){ RECT, {0, 0, 1} };
     cam.fov_x = M_PI / 2;
     cam.fov_y = M_PI / 2 * HEIGHT / WIDTH;
 
     unsigned char *fb = malloc(WIDTH * HEIGHT * 3);
 
-#if 0
-    render_scene(fb, WIDTH, HEIGHT, &scene, &cam, 2);
+#ifdef PPMOUT
+    render_scene(fb, WIDTH, HEIGHT, &scene, &cam, 2, MAX_BOUNCES);
     FILE *f = fopen("test.ppm", "w");
     fprintf(f, "P6\n%d %d\n%d\n", WIDTH, HEIGHT, 255);
     fwrite(fb, WIDTH * HEIGHT, 3, f);
@@ -391,13 +526,18 @@ int main()
     return 0;
 
 #else
+    /* auto-adjusting */
+    int bounces = MIN_BOUNCES;
+
     SDL_Init(SDL_INIT_VIDEO);
-    SDL_Surface *screen = SDL_SetVideoMode(WIDTH, HEIGHT, 24, SDL_HWSURFACE | SDL_FULLSCREEN);
+    SDL_Surface *screen = SDL_SetVideoMode(WIDTH, HEIGHT, 24, SDL_HWSURFACE);
     SDL_EnableKeyRepeat(500, 50);
 
+    int ts = SDL_GetTicks();
+
     while(1)
     {
-        lights[0].position.rect.z += .05;
+        //lights[0].position.rect.z += .05;
 #ifdef MOUSELOOK
         /* mouse look */
         int x, y;
@@ -405,13 +545,36 @@ int main()
         x -= WIDTH / 2;
         y -= HEIGHT / 2;
         vect_to_sph(&cam.direction);
-        cam.direction.sph.azimuth += M_PI/30 * SIGN(x)*SQR((scalar)x / WIDTH);
-        cam.direction.sph.elevation += M_PI/30 * SIGN(y)*SQR((scalar)y / HEIGHT);
+        cam.direction.sph.azimuth += M_PI/10 * SIGN(x)*SQR((scalar)x / WIDTH);
+        cam.direction.sph.elevation += M_PI/10 * SIGN(y)*SQR((scalar)y / HEIGHT);
 #endif
 
-        render_scene(fb, WIDTH, HEIGHT, &scene, &cam, 2);
+        render_scene(fb, WIDTH, HEIGHT, &scene, &cam, 2, bounces);
         memcpy(screen->pixels, fb, WIDTH * HEIGHT * 3);
         SDL_UpdateRect(screen, 0, 0, 0, 0);
+
+        int now = SDL_GetTicks();
+        int dt = now - ts;
+
+        if(dt < TARGET_MS && bounces < MAX_BOUNCES)
+        {
+            /* too fast! */
+            bounces *= 2;
+            if(bounces > MAX_BOUNCES)
+                bounces = MAX_BOUNCES;
+        }
+        else if(dt > TARGET_MS && bounces > MIN_BOUNCES)
+        {
+            bounces /= 2;
+            if(bounces < MIN_BOUNCES)
+                bounces = MIN_BOUNCES;
+        }
+
+
+        printf("%d bounces\n", bounces);
+
+        ts = now;
+
         SDL_Event e;
         //printf("camera at %f, %f, %f\n", cam.origin.rect.x, cam.origin.rect.y, cam.origin.rect.z);
         while(SDL_PollEvent(&e))
@@ -435,17 +598,21 @@ int main()
                     cam.origin.rect.y -= .1;
                     break;
                 case SDLK_a:
-                    vect_to_sph(&cam.direction);
-                    cam.direction.sph.azimuth += M_PI/2;
-                    cam.origin = vect_sub(cam.origin, vect_mul(cam.direction, MOVE_FACTOR));
-                    cam.direction.sph.azimuth -= M_PI/2;
+                {
+                    vector tmp = cam.direction;
+                    vect_to_sph(&tmp);
+                    tmp.sph.azimuth -= M_PI/2;
+                    cam.origin = vect_add(cam.origin, vect_mul(tmp, MOVE_FACTOR));
                     break;
+                }
                 case SDLK_d:
-                    vect_to_sph(&cam.direction);
-                    cam.direction.sph.azimuth -= M_PI/2;
-                    cam.origin = vect_sub(cam.origin, vect_mul(cam.direction, MOVE_FACTOR));
-                    cam.direction.sph.azimuth += M_PI/2;
+                {
+                    vector tmp = cam.direction;
+                    vect_to_sph(&tmp);
+                    tmp.sph.azimuth += M_PI/2;
+                    cam.origin = vect_add(cam.origin, vect_mul(tmp, MOVE_FACTOR));
                     break;
+                }
                 case SDLK_w:
                     cam.origin = vect_add(cam.origin, vect_mul(cam.direction, MOVE_FACTOR));
                     break;
diff --git a/vector.c b/vector.c
index 6a19cc9..9ba7bc9 100644
--- a/vector.c
+++ b/vector.c
@@ -123,3 +123,13 @@ vector vect_normalize(vector v)
     }
     return v;
 }
+
+vector vect_cross(vector v1, vector v2)
+{
+    vect_to_rect(&v1);
+    vect_to_rect(&v2);
+    vector ret = { RECT, { v1.rect.y * v2.rect.z - v1.rect.z * v2.rect.y,
+                           v1.rect.z * v2.rect.x - v1.rect.x * v2.rect.z,
+                           v1.rect.x * v2.rect.y - v1.rect.y * v2.rect.x, } };
+    return ret;
+}
diff --git a/vector.h b/vector.h
index f7b3949..c4f5ab3 100644
--- a/vector.h
+++ b/vector.h
@@ -27,3 +27,4 @@ void vect_to_rect(vector*);
 void vect_to_sph(vector*);
 
 scalar vect_dot(vector v1, vector v2);
+vector vect_cross(vector v1, vector v2);