From: Charles McGarvey Date: Tue, 7 Feb 2012 16:17:01 +0000 (-0700) Subject: initial commit X-Git-Tag: project1~1 X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Frasterize;a=commitdiff_plain;h=0f2508a4f227523a6b7e54798487af19d06a6ce9 initial commit --- 0f2508a4f227523a6b7e54798487af19d06a6ce9 diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..b3e118f --- /dev/null +++ b/Makefile @@ -0,0 +1,33 @@ + +PROJECT = project1 +SRCS = main.c common.c list.c pixmap.c scene.c tri.c + +VIEWER = feh + +CC = gcc +CFLAGS = -std=c99 -O0 -ggdb +CPPFLAGS= -MMD -DDEBUG +LDLIBS = -lm + +OBJS = $(SRCS:%.c=%.o) +DEPS = $(OBJS:%.o=%.d) + +all: $(PROJECT) + +$(PROJECT): $(OBJS) + $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) + +clean: + rm -f $(PROJECT) $(OBJS) $(DEPS) + +distclean: clean + rm -f scene.ppm scene.bmp + +run: $(PROJECT) + ./$< && $(VIEWER) scene.ppm + +debug: $(PROJECT) + gdb ./$< + +-include $(DEPS) + diff --git a/color.h b/color.h new file mode 100644 index 0000000..ba333e2 --- /dev/null +++ b/color.h @@ -0,0 +1,111 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __COLOR_H__ +#define __COLOR_H__ + +#include "common.h" + + +/* + * A color channel will be the same as a scalar. + */ +typedef scal_t colorchan_t; + +/* + * A color class. + * Colors are represented by RGBA values between 0.0 and 1.0. + */ +struct color +{ + colorchan_t r; + colorchan_t g; + colorchan_t b; + colorchan_t a; +}; +typedef struct color color_t; + +/* + * Initialize a color. + */ +__fast__ +void color_init(color_t* c, colorchan_t r, colorchan_t g, colorchan_t b, colorchan_t a) +{ + c->r = r; + c->g = g; + c->b = b; + c->a = a; +} + + +/* + * Create a new color, copied by value. + */ +__fast__ +color_t color_new(colorchan_t r, colorchan_t g, colorchan_t b, colorchan_t a) +{ + color_t c; + color_init(&c, r, g, b, a); + return c; +} + +#define COLOR_CLEAR color_new(S(0.0), S(0.0), S(0.0), S(0.0)) +#define COLOR_BLACK color_new(S(0.0), S(0.0), S(0.0), S(1.0)) +#define COLOR_RED color_new(S(1.0), S(0.0), S(0.0), S(1.0)) +#define COLOR_GREEN color_new(S(0.0), S(1.0), S(0.0), S(1.0)) +#define COLOR_BLUE color_new(S(0.0), S(0.0), S(1.0), S(1.0)) +#define COLOR_YELLOW color_new(S(1.0), S(1.0), S(0.0), S(1.0)) +#define COLOR_MAGENTA color_new(S(1.0), S(0.0), S(1.0), S(1.0)) +#define COLOR_CYAN color_new(S(0.0), S(1.0), S(1.0), S(1.0)) +#define COLOR_WHITE color_new(S(1.0), S(1.0), S(1.0), S(1.0)) + + +/* + * Define integer types for a 32-bit RGBA color representation. + */ +typedef uint32_t rgba_t; +typedef uint8_t rgbachan_t; + +/* + * Create a new color from a 32-bit RGBA value. + */ +__fast__ +color_t color_from_rgba(rgba_t n) +{ + colorchan_t r = (colorchan_t)UNPACK(n, 3) / S(255.0); + colorchan_t g = (colorchan_t)UNPACK(n, 2) / S(255.0); + colorchan_t b = (colorchan_t)UNPACK(n, 1) / S(255.0); + colorchan_t a = (colorchan_t)UNPACK(n, 0) / S(255.0); + return color_new(r, g, b, a); +} + +/* + * Split a color into 8-bit RGBA channels. + */ +__fast__ +void color_split(color_t c, rgbachan_t* r, rgbachan_t* g, rgbachan_t* b, rgbachan_t* a) +{ + if (r) *r = (rgbachan_t)(c.r * S(255.0)); + if (g) *g = (rgbachan_t)(c.g * S(255.0)); + if (b) *b = (rgbachan_t)(c.b * S(255.0)); + if (a) *a = (rgbachan_t)(c.a * S(255.0)); +} + +/* + * Convert a color to a 32-bit RGBA value. + */ +__fast__ +rgba_t rgba_from_color(color_t c) +{ + rgbachan_t r, g, b, a; + color_split(c, &r, &g, &b, &a); + return ((rgba_t)r << 24) | ((rgba_t)g << 16) | ((rgba_t)b << 8) | (rgba_t)a; +} + + +#endif // __COLOR_H__ + diff --git a/common.c b/common.c new file mode 100644 index 0000000..850778b --- /dev/null +++ b/common.c @@ -0,0 +1,100 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#include +#include +#include +#include +#include + +#include "common.h" + + +static void* (*_mem_fn)(void*, size_t) = NULL; + +static int _mem_blocks = 0; + + +/* + * Check the result of the allocation function and call the callback function + * if it failed. + */ +__fast__ +void* _mem_check(void* mem, void* old, size_t size) +{ + if (mem == NULL && size != 0) { + if (_mem_fn) { + mem = _mem_fn(old, size); + if (mem != NULL) { + goto done; + } + } + fprintf(stderr, "Memory allocation failed: %s\n", strerror(errno)); + abort(); + } + +done: + if (old == NULL) { + ++_mem_blocks; + } + return mem; +} + + +void* mem_alloc(size_t size) +{ + void* mem = _mem_check(malloc(size), NULL, size); +#ifdef MEM_TRACE + fprintf(stderr, " ALLOC %6d %18p %10zd\n", _mem_blocks - 1, mem, size); +#endif + return mem; +} + +void* mem_realloc(void* mem, size_t size) +{ + void* old = mem; + mem = _mem_check(realloc(mem, size), mem, size); +#ifdef MEM_TRACE + fprintf(stderr, " REALLOC %6d %18p %10zd (was %p)\n", _mem_blocks - 1, mem, size, old); +#endif + return mem; +} + +void mem_free(void* mem) +{ + --_mem_blocks; +#ifdef MEM_TRACE + fprintf(stderr, " FREE %6d %18p\n", _mem_blocks, mem); +#endif + free(mem); +} + +void mem_set_fn(void* (*fn)(void*, size_t)) +{ + _mem_fn = fn; +} + +int mem_blocks() +{ + return _mem_blocks; +} + + +void rtrim(char *str) +{ + char *m; + for (m = str + strlen(str) - 1; str <= m && isspace((int)*m); --m); + m[1] = '\0'; +} + +void ltrim(char *str) +{ + char *m; + for (m = str; *m && isspace((int)*m); ++m); + memmove(str, m, strlen(m) + 1); +} + diff --git a/common.h b/common.h new file mode 100644 index 0000000..4b0f7e0 --- /dev/null +++ b/common.h @@ -0,0 +1,114 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __COMMON_H__ +#define __COMMON_H__ + +#include +#include +#include +#include +#include + + +/* + * Define a type for scalar values, either float or double. + */ +#ifdef USE_DOUBLE +typedef double scal_t; +#define S(K) K +#define scal_sin sin +#define scal_cos cos +#else +typedef float scal_t; +#define S(K) K##f +#define scal_sin sinf +#define scal_cos cosf +#endif + +#define S_ZERO S(0.0) + + +/* + * Define a keyword for use while defining small and fast functions. + */ +#define __fast__ static inline + + +/* + * Define some macros for packing and unpacking bytes to and from larger ints. + */ +#define PACK(W,N,B) (((B) << (8 * (N))) | ((W) & ~(0xff << (8 * (N))))) +#define UNPACK(W,N) ((uint8_t)((W) >> (8 * (N))) & 0xff) + + +typedef void (*dtor_t)(void*); +#define DTOR(A) (dtor_t)(A) + + +/* + * Allocate a block of memory of a certain size. This follows the semantics + * of malloc(3), except it will never return NULL and will abort(3) if the + * memory could not be allocated. + */ +void* mem_alloc(size_t size); + +/* + * Change the size of a block of memory. This follows the semantics of + * realloc(3), except it will never return NULL and will abort(3) if the + * memory could not be allocated. + */ +void* mem_realloc(void* mem, size_t size); + +/* + * Deallocate a block of memory previously allocated by mem_alloc or malloc(3) + * and friends. This is essentially just a call to free(3). + */ +void mem_free(void* mem); + +/* + * Set a function to call if either mem_alloc or mem_realloc fails, or NULL if + * no callback should be called. The callback takes the same arguments as + * realloc(3) and may try to fulfill the request. The return value of the + * callback function will be returned from the allocation function and must be + * a valid pointer to an allocated block of memory. The callback function + * should not call mem_alloc or mem_realloc and must not return if a block of + * memory could not be allocated. + */ +void mem_set_fn(void* (*fn)(void*, size_t)); + +/* + * Get the number of blocks currently allocated with either mem_alloc or + * mem_realloc. This number should be zero at the end of a process running + * this program. + */ +int mem_blocks(); + + +/* + * Trim white space off of the right side of a string. + */ +void rtrim(char *str); + +/* + * Trim white space off of the left side of a string. + */ +void ltrim(char *str); + +/* + * Trim white space off of both sides of a string. + */ +__fast__ +void trim(char *str) +{ + rtrim(str); + ltrim(str); +} + + +#endif // __COMMON_H__ + diff --git a/list.c b/list.c new file mode 100644 index 0000000..d1429a4 --- /dev/null +++ b/list.c @@ -0,0 +1,26 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#include "list.h" + +void list_reverse(list_t** l) +{ + list_t* p = *l; + list_t* n = p->link; + + p->link = NULL; + + while (n) { + list_t* t = n->link; + n->link = p; + p = n; + n = t; + } + + *l = p; +} + diff --git a/list.h b/list.h new file mode 100644 index 0000000..5b7980e --- /dev/null +++ b/list.h @@ -0,0 +1,113 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __LIST_H__ +#define __LIST_H__ + +#include "common.h" + + +/* + * A linked-list with a stack-like interface. + * The value of each node can be any pointer. + */ +struct list +{ + void* val; + struct list* link; + void (*dtor)(void*); +}; +typedef struct list list_t; + + +/* + * Add a value to the list. It will become the first item. + * This is a O(1) operation. + */ +__fast__ +void list_push2(list_t** l, void* value, void (*destructor)(void*)) +{ + list_t* n = (list_t*)mem_alloc(sizeof(list_t)); + n->val = value; + n->link = *l; + n->dtor = destructor; + *l = n; +} + +/* + * Add a value to the list with no destructor set. + */ +__fast__ +void list_push(list_t** l, void* value) +{ + list_push2(l, value, 0); +} + + +/* + * Create a new list with a single value. + */ +__fast__ +list_t* list_new2(void* value, void (*destructor)(void*)) +{ + list_t* l = NULL; + list_push2(&l, value, destructor); + return l; +} + +/* + * Create a new list with a single value without a destructor set. + */ +__fast__ +list_t* list_new(void* value) +{ + list_t* l = NULL; + list_push2(&l, value, 0); + return l; +} + + +/* + * Remove a value from the front of the list. If the node has dtor set, it + * will be used to destroy the value. + * This is a O(1) operation. + */ +__fast__ +void list_pop(list_t** l) +{ + list_t* n = (*l)->link; + + if ((*l)->dtor) { + (*l)->dtor((*l)->val); + } + mem_free(*l); + + *l = n; +} + +/* + * Destroy the list, freeing up all of its memory. + * This is a O(n) operation. + */ +__fast__ +void list_destroy(list_t* l) +{ + while (l) { + list_pop(&l); + } +} + + +/* + * Reverse the order of the items in the list. + * This is a O(n) operation. + */ +void list_reverse(list_t** l); + + +#endif // __LIST_H__ + diff --git a/main.c b/main.c new file mode 100644 index 0000000..ba2c577 --- /dev/null +++ b/main.c @@ -0,0 +1,43 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#include + +#include "pixmap.h" +#include "scene.h" + + +/* + * Read a scene file, construct the scene object, draw the scene to a pixmap, + * and export the pixmap in PPM and BMP formats. + */ +int main(int argc, char* argv[]) +{ + scene_t* scene = scene_alloc("scene.u2d"); + if (scene == NULL) { + fprintf(stderr, "An error prevented the scene from loading. Aborting!\n"); + return 1; + } + + pixmap_t* raster = scene_render(scene); + scene_destroy(scene); + + pixmap_export_ppm(raster, "scene.ppm"); + pixmap_export_bmp(raster, "scene.bmp"); + + pixmap_destroy(raster); + +#ifndef NDEBUG + int _blocks = mem_blocks(); + if (_blocks != 0) { + fprintf(stderr, " *** Leaked %d blocks of memory! ***\n", _blocks); + return 1; + } +#endif + return 0; +} + diff --git a/mat.h b/mat.h new file mode 100644 index 0000000..f6d4c1b --- /dev/null +++ b/mat.h @@ -0,0 +1,204 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __MAT_H__ +#define __MAT_H__ + +#include "common.h" +#include "vec.h" + + +/* + * A simple matrix class with column-major storage and notation. + */ +struct mat +{ + vec_t v[4]; +}; +typedef struct mat mat_t; + +/* + * Initialize a matrix with individual components, row by row. + */ +__fast__ +void mat_init(mat_t* m, scal_t m11, scal_t m12, scal_t m13, scal_t m14, + scal_t m21, scal_t m22, scal_t m23, scal_t m24, + scal_t m31, scal_t m32, scal_t m33, scal_t m34, + scal_t m41, scal_t m42, scal_t m43, scal_t m44) +{ + m->v[0] = vec_new2(m11, m21, m31, m41); + m->v[1] = vec_new2(m12, m22, m32, m42); + m->v[2] = vec_new2(m13, m23, m33, m43); + m->v[3] = vec_new2(m14, m24, m34, m44); +} + + +/* + * Create a new matrix with individual components, row by row. + */ +__fast__ +mat_t mat_new(scal_t m11, scal_t m12, scal_t m13, scal_t m14, + scal_t m21, scal_t m22, scal_t m23, scal_t m24, + scal_t m31, scal_t m32, scal_t m33, scal_t m34, + scal_t m41, scal_t m42, scal_t m43, scal_t m44) +{ + mat_t m; + mat_init(&m, m11, m12, m13, m14, + m21, m22, m23, m24, + m31, m32, m33, m34, + m41, m42, m43, m44); + return m; +} + +/* + * Create a new matrix with four column vectors. + */ +__fast__ +mat_t mat_new2(vec_t a, vec_t b, vec_t c, vec_t d) +{ + mat_t m; + m.v[0] = a; + m.v[1] = b; + m.v[2] = c; + m.v[3] = d; + return m; +} + +#define MAT_IDENTITY mat_new(S(1.0), S(0.0), S(0.0), S(0.0), \ + S(0.0), S(1.0), S(0.0), S(0.0), \ + S(0.0), S(0.0), S(1.0), S(0.0), \ + S(0.0), S(0.0), S(0.0), S(1.0)) + + +/* + * Create a new translate matrix. + */ +__fast__ +mat_t MAT_TRANSLATE(scal_t x, scal_t y, scal_t z) +{ + return mat_new(S(1.0), S(0.0), S(0.0), x, + S(0.0), S(1.0), S(0.0), y, + S(0.0), S(0.0), S(1.0), z, + S(0.0), S(0.0), S(0.0), S(1.0)); +} + +/* + * Create a new scale matrix. + */ +__fast__ +mat_t MAT_SCALE(scal_t x, scal_t y, scal_t z) +{ + return mat_new( x, S(0.0), S(0.0), S(0.0), + S(0.0), y, S(0.0), S(0.0), + S(0.0), S(0.0), z, S(0.0), + S(0.0), S(0.0), S(0.0), S(1.0)); +} + +/* + * Create a rotation matrix (around the Z axis). + */ +__fast__ +mat_t MAT_ROTATE_Z(scal_t a) +{ + scal_t sin_a = scal_sin(a); + scal_t cos_a = scal_cos(a); + return mat_new( cos_a, -sin_a, S(0.0), S(0.0), + sin_a, cos_a, S(0.0), S(0.0), + S(0.0), S(0.0), S(1.0), S(0.0), + S(0.0), S(0.0), S(0.0), S(1.0)); +} + +/* + * Create a 2D orthogonal projection matrix. + */ +__fast__ +mat_t MAT_ORTHO(scal_t left, scal_t right, scal_t bottom, scal_t top) +{ + scal_t rml = right - left; + scal_t rpl = right + left; + scal_t tmb = top - bottom; + scal_t tpb = top + bottom; + return mat_new(S(2.0) / rml, S(0.0), S(0.0), -rpl / rml, + S(0.0), S(2.0) / tmb, S(0.0), -tpb / tmb, + S(0.0), S(0.0), S(-1.0), S(0.0), + S(0.0), S(0.0), S(0.0), S(1.0)); +} + +/* + * Create a viewport matrix. + */ +__fast__ +mat_t MAT_VIEWPORT(int x, int y, unsigned w, unsigned h) +{ + scal_t xs = (scal_t)x; + scal_t ys = (scal_t)y; + scal_t ws = (scal_t)w / S(2.0); + scal_t hs = (scal_t)h / S(2.0); + return mat_new( ws, S(0.0), S(0.0), ws + xs, + S(0.0), hs, S(0.0), hs + ys, + S(0.0), S(0.0), S(1.0), S(0.0), + S(0.0), S(0.0), S(0.0), S(1.0)); +} + + +/* + * Get a column vector (can also access the vector array directly). + */ +__fast__ +vec_t mat_col(mat_t m, int i) +{ + return m.v[i]; +} + +/* + * Get a row vector. + */ +__fast__ +vec_t mat_row(mat_t m, int i) +{ + switch (i) { + case 0: + return vec_new2(m.v[0].x, m.v[1].x, m.v[2].x, m.v[3].x); + case 1: + return vec_new2(m.v[0].y, m.v[1].y, m.v[2].y, m.v[3].y); + case 2: + return vec_new2(m.v[0].z, m.v[1].z, m.v[2].z, m.v[3].z); + case 3: + return vec_new2(m.v[0].w, m.v[1].w, m.v[2].w, m.v[3].w); + } +} + + +/* + * Multiply two matrices together. + */ +__fast__ +mat_t mat_mult(mat_t a, mat_t b) +{ +#define _DOT(I,J) vec_dot(mat_row(a,I), mat_col(b,J)) + return mat_new(_DOT(0,0), _DOT(0,1), _DOT(0,2), _DOT(0,3), + _DOT(1,0), _DOT(1,1), _DOT(1,2), _DOT(1,3), + _DOT(2,0), _DOT(2,1), _DOT(2,2), _DOT(2,3), + _DOT(3,0), _DOT(3,1), _DOT(3,2), _DOT(3,3)); +#undef _DOT +} + +/* + * Transform a vector using a matrix. + */ +__fast__ +vec_t mat_apply(mat_t m, vec_t v) +{ + return vec_new2(vec_dot(v,mat_row(m,0)), + vec_dot(v,mat_row(m,1)), + vec_dot(v,mat_row(m,2)), + vec_dot(v,mat_row(m,3))); +} + + +#endif // __MAT_H__ + diff --git a/pixmap.c b/pixmap.c new file mode 100644 index 0000000..44038e3 --- /dev/null +++ b/pixmap.c @@ -0,0 +1,204 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#include +#include +#include +#include + +#include "pixmap.h" + + +struct pixmap +{ + color_t* pixels; + int w; + int h; + int left, right, bottom, top; + mat_t modelview; + mat_t projection; + mat_t final; +}; + + +pixmap_t* pixmap_alloc(int width, int height, color_t fill) +{ + assert(0 < width && 0 < height && "zero-dimension pixmap not allowed"); + size_t size = width * height; + + pixmap_t* p = (pixmap_t*)mem_alloc(sizeof(pixmap_t)); + p->pixels = (color_t*)mem_alloc(sizeof(color_t) * size); + p->w = width; + p->h = height; + p->left = p->bottom = 0; + p->right = width; + p->top = height; + pixmap_clear(p, fill); + return p; +} + +void pixmap_destroy(pixmap_t* p) +{ + mem_free(p->pixels); + mem_free(p); +} + + +void pixmap_clear(pixmap_t* p, color_t fill) +{ + size_t size = p->w * p->h; + for (int i = 0; i < size; ++i) { + p->pixels[i] = fill; + } +} + + +static void _pixmap_set_transformation(pixmap_t* p) +{ + /* + * Just including a viewport transformation in the final transformation. + * This could probably be faster by separating this out. + */ + mat_t viewport = MAT_VIEWPORT(p->left, p->bottom, p->right - p->left, p->top - p->bottom); + p->final = mat_mult(p->projection, p->modelview); + p->final = mat_mult(viewport, p->final); +} + + +void pixmap_viewport(pixmap_t* p, int x, int y, int width, int height) +{ + p->left = x; + p->right = x + width; + p->bottom = y; + p->top = y + height; + _pixmap_set_transformation(p); +} + +void pixmap_modelview(pixmap_t* p, const mat_t* transform) +{ + p->modelview = *transform; + _pixmap_set_transformation(p); +} + +void pixmap_projection(pixmap_t* p, const mat_t* transform) +{ + p->projection = *transform; + _pixmap_set_transformation(p); +} + + +#define _CHECK_WRITE(X) if ((X) <= 0) goto fail + +int pixmap_export_ppm(const pixmap_t* p, const char* filename) +{ + FILE* file = fopen(filename, "w"); + if (file == NULL) { +fail: fprintf(stderr, "Cannot write to %s: %s\n", filename, strerror(errno)); + return -1; + } + + _CHECK_WRITE(fprintf(file, "P3\n%u %u\n255\n", p->w, p->h)); + for (int y = (int)p->h - 1; y >= 0; --y) { + for (int x = 0; x < p->w; ++x) { + rgbachan_t r, g, b; + color_split(p->pixels[y * p->w + x], &r, &g, &b, NULL); + _CHECK_WRITE(fprintf(file, "%hhu %hhu %hhu\n", r, g, b)); + } + } + + fclose(file); + return 0; +} + +int pixmap_export_bmp(const pixmap_t* p, const char* filename) +{ + /* + * This function was adapted from sample code provided with the assignment + * instructions. + */ + FILE* file = fopen(filename, "wb"); + if (file == NULL) { +fail: fprintf(stderr, "Cannot write to %s: %s\n", filename, strerror(errno)); + return -1; + } + + uint16_t magicNumber = 0x4D42; + uint16_t reserved0 = 0;//0x4D41; + uint16_t reserved1 = 0;//0x5454; + uint32_t dataOffset = 54; + uint32_t infoHeaderSize = 40; + uint32_t width = p->w; + uint32_t height = p->h; + uint16_t colorPlanes = 1; + uint16_t bitsPerPixel = 32; + uint32_t compression = 0; + uint32_t dataSize = width * height * bitsPerPixel / 8; + uint32_t horizontalResolution = 2835; + uint32_t verticalResolution = 2835; + uint32_t paletteColorCount = 0; + uint32_t importantPaletteColorCount = 0; + uint32_t fileSize = 54 + dataSize; + + /* + * Check the return values to avoid loud warnings. + */ + _CHECK_WRITE(fwrite(&magicNumber, sizeof(magicNumber), 1, file)); + _CHECK_WRITE(fwrite(&fileSize, sizeof(fileSize), 1, file)); + _CHECK_WRITE(fwrite(&reserved0, sizeof(reserved0), 1, file)); + _CHECK_WRITE(fwrite(&reserved1, sizeof(reserved1), 1, file)); + _CHECK_WRITE(fwrite(&dataOffset, sizeof(dataOffset), 1, file)); + _CHECK_WRITE(fwrite(&infoHeaderSize, sizeof(infoHeaderSize), 1, file)); + _CHECK_WRITE(fwrite(&width, sizeof(width), 1, file)); + _CHECK_WRITE(fwrite(&height, sizeof(height), 1, file)); + _CHECK_WRITE(fwrite(&colorPlanes, sizeof(colorPlanes), 1, file)); + _CHECK_WRITE(fwrite(&bitsPerPixel, sizeof(bitsPerPixel), 1, file)); + _CHECK_WRITE(fwrite(&compression, sizeof(compression), 1, file)); + _CHECK_WRITE(fwrite(&dataSize, sizeof(dataSize), 1, file)); + _CHECK_WRITE(fwrite(&horizontalResolution, sizeof(horizontalResolution), 1, file)); + _CHECK_WRITE(fwrite(&verticalResolution, sizeof(verticalResolution), 1, file)); + _CHECK_WRITE(fwrite(&paletteColorCount, sizeof(paletteColorCount), 1, file)); + _CHECK_WRITE(fwrite(&importantPaletteColorCount, sizeof(importantPaletteColorCount), 1, file)); + + size_t size = width * height; + for (int i = 0; i < size; ++i) + { + rgbachan_t a, r, g, b; + color_split(p->pixels[i], &r, &g, &b, &a); + uint32_t argb = PACK(argb, 3, a); + argb = PACK(argb, 2, r); + argb = PACK(argb, 1, g); + argb = PACK(argb, 0, b); + _CHECK_WRITE(fwrite(&argb, sizeof(argb), 1, file)); + } + + fclose(file); + return 0; +} + + +void pixmap_draw_tri(pixmap_t* p, const tri_t* triangle) +{ + tri_t t = tri_transform(*triangle, p->final); + + for (int y = p->bottom; y < p->top; ++y) { + for (int x = p->left; x < p->right; ++x) { + vec_t pt = vec_new((scal_t)x, (scal_t)y, S(0.0)); + vec_t b = tri_barycentric(&t, pt); + if (vec_is_barycentric(b)) { + color_t* c = p->pixels + y * p->w + x; + color_t color = color_new( + t.a.c.r * b.x + t.b.c.r * b.y + t.c.c.r * b.z, + t.a.c.g * b.x + t.b.c.g * b.y + t.c.c.g * b.z, + t.a.c.b * b.x + t.b.c.b * b.y + t.c.c.b * b.z, + S(1.0) + ); + *c = color; + } + } + } +} + diff --git a/pixmap.h b/pixmap.h new file mode 100644 index 0000000..f97e5b4 --- /dev/null +++ b/pixmap.h @@ -0,0 +1,76 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __PIXMAP_H__ +#define __PIXMAP_H__ + +#include "color.h" +#include "common.h" +#include "tri.h" + + +/* + * A pixel map for storing and manipulating a 2D grid of color values. + */ +typedef struct pixmap pixmap_t; + + +/* + * Create a new pixmap on the heap. + */ +pixmap_t* pixmap_alloc(int width, int height, color_t fill); + +/* + * Free up the memory associated with the pixmap. + */ +void pixmap_destroy(pixmap_t* p); + + +/* + * Fill the entire pixmap with a solid color. + */ +void pixmap_clear(pixmap_t* p, color_t fill); + + +/* + * Set the viewport rectangle. This effectively sets up a clipping rectangle + * where nothing is drawn outside of the rectangle. The default viewport is + * [0, 0, width, height], or the entire pixmap area. + */ +void pixmap_viewport(pixmap_t* p, int x, int y, int width, int height); + +/* + * Set the modelview matrix. This positions the model or camera. + */ +void pixmap_modelview(pixmap_t* p, const mat_t* transform); + +/* + * Set the projection matrix. This provides the transformation matrix for + * converting to screen space. + */ +void pixmap_projection(pixmap_t* p, const mat_t* transform); + + +/* + * Save the pixmap to a PPM file. + */ +int pixmap_export_ppm(const pixmap_t* p, const char* filename); + +/* + * Save the pixmap to a BMP file. + */ +int pixmap_export_bmp(const pixmap_t* p, const char* filename); + + +/* + * Draw a smooth gradient triangle to the pixmap. + */ +void pixmap_draw_tri(pixmap_t* p, const tri_t* triangle); + + +#endif // __PIXMAP_H__ + diff --git a/scene.c b/scene.c new file mode 100644 index 0000000..449dab6 --- /dev/null +++ b/scene.c @@ -0,0 +1,260 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#include +#include +#include + +#include "common.h" +#include "mat.h" +#include "list.h" +#include "scene.h" +#include "tri.h" + + +/* + * A group of triangles and a transformation. + */ +struct _group +{ + list_t* triangles; + mat_t modelview; +}; +typedef struct _group _group_t; + +/* + * Allocate a group by reading raw triangle coordinates from a file. + */ +static _group_t* _group_alloc(const char* filename) +{ + FILE* file = fopen(filename, "r"); + if (file == NULL) { + fprintf(stderr, "Cannot read %s: %s\n", filename, strerror(errno)); + return NULL; + } + + _group_t* g = (_group_t*)mem_alloc(sizeof(_group_t)); + g->triangles = NULL; + g->modelview = MAT_IDENTITY; + + double x1, y1, z1, x2, y2, z2, x3, y3, z3; + while (fscanf(file, " %lf %lf %lf %lf %lf %lf %lf %lf %lf", + &x1, &y1, &z1, &x2, &y2, &z2, &x3, &y3, &z3) == 9) { + tri_t* t = tri_alloc( + vert_new2((scal_t)x1, (scal_t)y1, (scal_t)z1, COLOR_WHITE), + vert_new2((scal_t)x2, (scal_t)y2, (scal_t)z2, COLOR_WHITE), + vert_new2((scal_t)x3, (scal_t)y3, (scal_t)z3, COLOR_WHITE) + ); + list_push2(&g->triangles, t, mem_free); + } + list_reverse(&g->triangles); + + fclose(file); + + if (g->triangles == NULL) { + fprintf(stderr, "No triangles coordinates read from %s\n", filename); + mem_free(g); + return NULL; + } + + return g; +} + +/* + * Destroy a group. + */ +static void _group_destroy(_group_t* g) +{ + list_destroy(g->triangles); + mem_free(g); +} + + +/* + * Set the colors of the triangles in the group as defined in a file. + */ +static int _group_set_colors(_group_t* g, FILE* file) +{ + double r1, g1, b1, r2, g2, b2, r3, g3, b3; + if (fscanf(file, " %lf %lf %lf %lf %lf %lf %lf %lf %lf", + &r1, &g1, &b1, &r2, &g2, &b2, &r3, &g3, &b3) != 9) { + fprintf(stderr, "Cannot read color values from scene file.\n"); + return -1; + } + + for (list_t* i = g->triangles; i; i = i->link) { + tri_t* t = (tri_t*)i->val; + t->a.c = color_new((colorchan_t)r1, (colorchan_t)g1, (colorchan_t)b1, S(1.0)); + t->b.c = color_new((colorchan_t)r2, (colorchan_t)g2, (colorchan_t)b2, S(1.0)); + t->c.c = color_new((colorchan_t)r3, (colorchan_t)g3, (colorchan_t)b3, S(1.0)); + } + return 0; +} + +/* + * Concat a translation matrix to the transformation as defined in a file. + */ +static int _group_add_translate(_group_t* g, FILE* file) +{ + double tx, ty; + if (fscanf(file, " %lf %lf", &tx, &ty) != 2) { + fprintf(stderr, "Cannot read translate coordinates from scene file.\n"); + return -1; + } + + g->modelview = mat_mult(g->modelview, MAT_TRANSLATE((scal_t)tx, (scal_t)ty, S(1.0))); + return 0; +} + +/* + * Concat a rotation matrix to the transformation as defined in a file. + */ +static int _group_add_rotate(_group_t* g, FILE* file) +{ + double theta; + if (fscanf(file, " %lf", &theta) != 1) { + fprintf(stderr, "Cannot read rotation angle from scene file.\n"); + return -1; + } + + g->modelview = mat_mult(g->modelview, MAT_ROTATE_Z((scal_t)theta)); + return 0; +} + +/* + * Concat a scale matrix to the transformation as defined in a file. + */ +static int _group_add_scale(_group_t* g, FILE* file) +{ + double sx, sy; + if (fscanf(file, " %lf %lf", &sx, &sy) != 2) { + fprintf(stderr, "Cannot read scale factors from scene file.\n"); + return -1; + } + + g->modelview = mat_mult(g->modelview, MAT_SCALE((scal_t)sx, (scal_t)sy, S(1.0))); + return 0; +} + + +struct scene +{ + list_t* groups; + int w; + int h; + mat_t projection; +}; + +scene_t* scene_alloc(const char* filename) +{ + scene_t* s = (scene_t*)mem_alloc(sizeof(scene_t)); + s->groups = NULL; + + FILE* file = fopen(filename, "r"); + + int w, h; + double minX, minY, maxX, maxY; + if (fscanf(file, "U2 %d %d %lf %lf %lf %lf", + &w, &h, &minX, &minY, &maxX, &maxY) != 6) { + fprintf(stderr, "Cannot read scene file header.\n"); + return NULL; + } + + s->w = w; + s->h = h; + s->projection = MAT_ORTHO((scal_t)minX, (scal_t)maxX, (scal_t)minY, (scal_t)maxY); + + char grp_filename[4096]; + _group_t* g = NULL; + +#define _ASSERT_G \ +if (g == NULL) { \ + fprintf(stderr, "Unexpected line before group is loaded.\n"); \ + goto fail; \ +} + + char type; + while (fscanf(file, " %c", &type) == 1) { + switch (type) { + case 'g': + if (fgets(grp_filename, 4096, file) == NULL) { + fprintf(stderr, "Cannot read raw triangle filename.\n"); + } + trim(grp_filename); + g = _group_alloc(grp_filename); + if (g == NULL) { + goto fail; + } + list_push2(&s->groups, g, DTOR(_group_destroy)); + break; + + case 'c': + _ASSERT_G; + if (_group_set_colors(g, file) != 0) { + goto fail; + } + break; + + case 't': + _ASSERT_G; + if (_group_add_translate(g, file) != 0) { + goto fail; + } + break; + + case 'r': + if (_group_add_rotate(g, file) != 0) { + goto fail; + } + break; + + case 's': + _ASSERT_G; + if (_group_add_scale(g, file) != 0) { + goto fail; + } + break; + + default: + fprintf(stderr, "Unknown identifier: %c\n", type); + } + } + list_reverse(&s->groups); + +#undef _ASSERT_G + + fclose(file); + return s; + +fail: + scene_destroy(s); + return NULL; +} + +void scene_destroy(scene_t* s) +{ + list_destroy(s->groups); + mem_free(s); +} + + +pixmap_t* scene_render(scene_t* s) +{ + pixmap_t* pix = pixmap_alloc(s->w, s->h, COLOR_BLACK); + pixmap_projection(pix, &s->projection); + + for (list_t* gi = s->groups; gi; gi = gi->link) { + _group_t* g = (_group_t*)gi->val; + pixmap_modelview(pix, &g->modelview); + for (list_t* ti = g->triangles; ti; ti = ti->link) { + pixmap_draw_tri(pix, (tri_t*)ti->val); + } + } + + return pix; +} + diff --git a/scene.h b/scene.h new file mode 100644 index 0000000..7857b76 --- /dev/null +++ b/scene.h @@ -0,0 +1,38 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __SCENE_H__ +#define __SCENE_H__ + +#include "pixmap.h" + + +/* + * A scene. + */ +typedef struct scene scene_t; + +/* + * Allocate a scene by reading in data from a file. + */ +scene_t* scene_alloc(const char* filename); + +/* + * Destroy a scene. + */ +void scene_destroy(scene_t* s); + + +/* + * Render a scene to an in-memory pixmap. The caller takes ownership of the + * returned object and must destroy it when it is no longer needed. + */ +pixmap_t* scene_render(scene_t* s); + + +#endif // __SCENE_H__ + diff --git a/scene.u2d b/scene.u2d new file mode 100644 index 0000000..9873025 --- /dev/null +++ b/scene.u2d @@ -0,0 +1,9 @@ +U2 +500 500 +-1.0 -1.0 1.0 1.0 +g triangle.raw +c 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 +s 0.5 1.0 +t 0.3 -0.2 + + diff --git a/tri.c b/tri.c new file mode 100644 index 0000000..e43faa5 --- /dev/null +++ b/tri.c @@ -0,0 +1,19 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#include "tri.h" + +vec_t tri_barycentric(const tri_t* t, vec_t v) +{ + vec_t c = VEC_ZERO; + scal_t denom = (t->b.v.y - t->c.v.y) * (t->a.v.x - t->c.v.x) + (t->c.v.x - t->b.v.x) * (t->a.v.y - t->c.v.y); + c.x = ((t->b.v.y - t->c.v.y) * (v.x - t->c.v.x) + (t->c.v.x - t->b.v.x) * (v.y - t->c.v.y)) / denom; + c.y = ((t->c.v.y - t->a.v.y) * (v.x - t->c.v.x) + (t->a.v.x - t->c.v.x) * (v.y - t->c.v.y)) / denom; + c.z = S(1.0) - c.x - c.y; + return c; +} + diff --git a/tri.h b/tri.h new file mode 100644 index 0000000..7170d4a --- /dev/null +++ b/tri.h @@ -0,0 +1,88 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __TRI_H__ +#define __TRI_H__ + +#include "mat.h" +#include "vert.h" + + +/* + * A triangle is a polygon of three vertices. + */ +struct tri +{ + vert_t a; + vert_t b; + vert_t c; +}; +typedef struct tri tri_t; + +/* + * Initialize a triangle. + */ +__fast__ +void tri_init(tri_t* t, vert_t a, vert_t b, vert_t c) +{ + t->a = a; + t->b = b; + t->c = c; +} + + +/* + * Create a new triangle. + */ +__fast__ +tri_t tri_new(vert_t a, vert_t b, vert_t c) +{ + tri_t t; + tri_init(&t, a, b, c); + return t; +} + +#define TRI_ZERO tri_new(VERT_ZERO, VERT_ZERO, VERT_ZERO) + + +/* + * Create a new triangle on the heap. + */ +__fast__ +tri_t* tri_alloc(vert_t a, vert_t b, vert_t c) +{ + tri_t* t = (tri_t*)mem_alloc(sizeof(tri_t)); + tri_init(t, a, b, c); + return t; +} + + +/* + * Apply a transformation matrix to alter the triangle geometry. + */ +__fast__ +tri_t tri_transform(tri_t t, mat_t m) +{ + t.a.v = mat_apply(m, t.a.v); + t.b.v = mat_apply(m, t.b.v); + t.c.v = mat_apply(m, t.c.v); + return t; +} + + +/* + * Get the barycentric coordinates of a vector against a triangle. The + * returned coordinates will be a linear combination, but they may not + * actually be barycentric coordinates. Use the function vec_is_barycentric + * to check if they really are barycentric coordinates, meaning the point + * vector v is inside the triangle, ignoring the Z components. + */ +vec_t tri_barycentric(const tri_t* t, vec_t v); + + +#endif // __TRI_H__ + diff --git a/triangle.raw b/triangle.raw new file mode 100644 index 0000000..bb03f00 --- /dev/null +++ b/triangle.raw @@ -0,0 +1,3 @@ +-0.5 -0.5 0.0 + 0.5 -0.5 0.0 + 0.0 0.5 0.0 diff --git a/vec.h b/vec.h new file mode 100644 index 0000000..f08945c --- /dev/null +++ b/vec.h @@ -0,0 +1,144 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __VEC_H__ +#define __VEC_H__ + +#include "common.h" + + +/* + * A simple vector class. + */ +struct vec +{ + scal_t x; + scal_t y; + scal_t z; + scal_t w; +}; +typedef struct vec vec_t; + +/* + * Initialize a vector with four components. + */ +__fast__ +void vec_init(vec_t* v, scal_t x, scal_t y, scal_t z, scal_t w) +{ + v->x = x; + v->y = y; + v->z = z; + v->w = w; +} + + +/* + * Create a new vector with four components. + */ +__fast__ +vec_t vec_new2(scal_t x, scal_t y, scal_t z, scal_t w) +{ + vec_t v; + vec_init(&v, x, y, z, w); + return v; +} + +/* + * Create a new vector with three components. The fourth component is + * initialized to one. + */ +__fast__ +vec_t vec_new(scal_t x, scal_t y, scal_t z) +{ + return vec_new2(x, y, z, S(1.0)); +} + +#define VEC_ZERO vec_new(S(0.0), S(0.0), S(0.0)) +#define VEC_ORTHO_X vec_new(S(1.0), S(0.0), S(0.0)) +#define VEC_ORTHO_Y vec_new(S(0.0), S(1.0), S(0.0)) +#define VEC_ORTHO_Z vec_new(S(0.0), S(0.0), S(1.0)) + + +/* + * Scale the vector with a scalar value. + */ +__fast__ +vec_t vec_scale(vec_t v, scal_t s) +{ + v.x *= s; + v.y *= s; + v.z *= s; + return v; +} + +/* + * Add two vectors together. + */ +__fast__ +vec_t vec_add(vec_t a, vec_t b) +{ + a.x += b.x; + a.y += b.y; + a.z += b.z; + return a; +} + +/* + * Subtract a vector from another vector. + */ +__fast__ +vec_t vec_sub(vec_t a, vec_t b) +{ + a.x -= b.x; + a.y -= b.y; + a.z -= b.z; + return a; +} + + +/* + * Get the dot product of two vectors. + */ +__fast__ +scal_t vec_dot(vec_t a, vec_t b) +{ + return a.x * b.x + a.y * b.y + a.z * b.z + a.w * b.w; +} + +/* + * Get the dot product of two vectors, ignoring the last component. + */ +__fast__ +scal_t vec_dot3(vec_t a, vec_t b) +{ + return a.x * b.x + a.y * b.y + a.z * b.z; +} + + +/* + * Check whether the values of the first three components could actually be + * barycentric coordinates. Note: The necessary condition of each component + * adding up to one is assumed and not checked. + */ +__fast__ +bool vec_is_barycentric(vec_t v) +{ + /* + * XXX: I'm fudging the bounds a little because horizontal edges (relative + * to the screen) are otherwise sometimes really jagged. This probably + * isn't the best solution. + */ + if (S(-0.000001) <= v.x && v.x <= S(1.000001) && + S(-0.000001) <= v.y && v.y <= S(1.000001) && + S(-0.000001) <= v.z && v.z <= S(1.000001)) { + return true; + } + return false; +} + +#endif // __VEC_H__ + diff --git a/vert.h b/vert.h new file mode 100644 index 0000000..232a0cf --- /dev/null +++ b/vert.h @@ -0,0 +1,62 @@ + +/* + * CS5600 University of Utah + * Charles McGarvey + * mcgarvey@eng.utah.edu + */ + +#ifndef __VERT_H__ +#define __VERT_H__ + +#include "color.h" +#include "vec.h" + + +/* + * A vertex is a point and its associated color. + */ +struct vert +{ + vec_t v; + color_t c; +}; +typedef struct vert vert_t; + + +/* + * Initialize a vertex with a point vector and a color. + */ +__fast__ +void vert_init(vert_t* r, vec_t v, color_t c) +{ + r->v = v; + r->c = c; +} + + +/* + * Create a new vertex with a point vector and a color. + */ +__fast__ +vert_t vert_new(vec_t v, color_t c) +{ + vert_t r; + vert_init(&r, v, c); + return r; +} + +/* + * Create a new vertex from vector components and a color. + */ +__fast__ +vert_t vert_new2(scal_t x, scal_t y, scal_t z, color_t c) +{ + vec_t v = vec_new(x, y, z); + return vert_new(v, c); +} + +#define VERT_ZERO vert_new(VEC_ZERO, COLOR_CLEAR) + + +#endif // __VERT_H__ +