diff options
Diffstat (limited to 'generator/pamtris')
| -rw-r--r-- | generator/pamtris/Makefile | 27 | ||||
| -rw-r--r-- | generator/pamtris/boundaries.c | 262 | ||||
| -rw-r--r-- | generator/pamtris/boundaries.h | 72 | ||||
| -rw-r--r-- | generator/pamtris/framebuffer.c | 339 | ||||
| -rw-r--r-- | generator/pamtris/framebuffer.h | 75 | ||||
| -rw-r--r-- | generator/pamtris/input.c | 695 | ||||
| -rw-r--r-- | generator/pamtris/input.h | 27 | ||||
| -rw-r--r-- | generator/pamtris/limits_pamtris.h | 11 | ||||
| -rw-r--r-- | generator/pamtris/pamtris.c | 171 | ||||
| -rw-r--r-- | generator/pamtris/triangle.c | 327 | ||||
| -rw-r--r-- | generator/pamtris/triangle.h | 25 | ||||
| -rw-r--r-- | generator/pamtris/utils.c | 266 | ||||
| -rw-r--r-- | generator/pamtris/utils.h | 58 | ||||
| -rw-r--r-- | generator/pamtris/varying.h | 12 |
14 files changed, 2367 insertions, 0 deletions
diff --git a/generator/pamtris/Makefile b/generator/pamtris/Makefile new file mode 100644 index 00000000..d27606e3 --- /dev/null +++ b/generator/pamtris/Makefile @@ -0,0 +1,27 @@ +ifeq ($(SRCDIR)x,x) + SRCDIR = $(CURDIR)/../.. + BUILDDIR = $(SRCDIR) +endif +SUBDIR = generator/pamtris +VPATH=.:$(SRCDIR)/$(SUBDIR) + +include $(BUILDDIR)/config.mk + +PORTBINARIES = pamtris + +MERGEBINARIES = $(PORTBINARIES) + +BINARIES = $(MERGEBINARIES) $(NOMERGEBINARIES) + +ADDL_OBJECTS = boundaries.o framebuffer.o input.o triangle.o utils.o + +OBJECTS = pamtris.o $(ADDL_OBJECTS) + +MERGE_OBJECTS = pamtris.o2 $(ADDL_OBJECTS) + +.PHONY: all +all: $(BINARIES) + +pamtris:%:%.o $(ADDL_OBJECTS) + +include $(SRCDIR)/common.mk diff --git a/generator/pamtris/boundaries.c b/generator/pamtris/boundaries.c new file mode 100644 index 00000000..7045cbc7 --- /dev/null +++ b/generator/pamtris/boundaries.c @@ -0,0 +1,262 @@ +/*============================================================================= + boundaries.c +=============================================================================== + Boundary buffer functions + + New triangles are drawn one row at a time, and for every such row we have + left and right boundary columns within the frame buffer such that the + fraction of the triangle's area within that scanline is enclosed between + those two points (inclusive). Those coordinates may correspond to columns + outside the frame buffer's actual limits, in which case proper + post-processing should be made wherever such coordinates are used to + actually plot anything into the frame buffer. +=============================================================================*/ + +#include <stdlib.h> + +#include <netpbm/mallocvar.h> +#include <netpbm/pm.h> + +#include "varying.h" +#include "utils.h" + + +#include "boundaries.h" + + + +void +init_boundary_buffer(boundary_info * const bi, + int16_t const height) { + + MALLOCARRAY(bi->buffer, height * 2); + + if (!bi->buffer) { + pm_error("unable to get memory for %u-row high boundary buffer.", + height); + } +} + + + +void +free_boundary_buffer(boundary_info * bi) { + free(bi->buffer); +} + + + +bool +gen_triangle_boundaries(Xy const xy, + boundary_info * const bi, + int16_t const width, + int16_t const height) { +/*---------------------------------------------------------------------------- + Generate an entry in the boundary buffer for the boundaries of every + VISIBLE row of a particular triangle. In case there is no such row, + start_scanline is accordingly set to -1. "xy" is a 3-element array + of pairs of integers representing the coordinates of the vertices of + a triangle. Those vertices MUST be already sorted in order from the + uppermost to the lowermost vertex (which is what draw_triangle, the + only function which uses this one, does with the help of sort3). + + The return value indicates whether the middle vertex is to the left of + the line connecting the top vertex to the bottom vertex or not. +-----------------------------------------------------------------------------*/ + int16_t leftmost_x; + int16_t rightmost_x; + int mid_is_to_the_left; + varying top_x; + varying mid_x; + varying bot_x; + varying top2mid; + varying top2bot; + varying mid2bot; + varying* upper_left; + varying* lower_left; + varying* upper_right; + varying* lower_right; + varying* left[2]; + varying* right[2]; + int16_t* num_rows_ptr[2]; + int32_t y; + int32_t i; + uint8_t k; + + leftmost_x = xy._[0][0]; /* initial value */ + rightmost_x = xy._[0][0]; /* initial value */ + + bi->start_scanline = -1; + bi->num_upper_rows = 0; + bi->num_lower_rows = 0; + + if (xy._[2][1] < 0 || xy._[0][1] >= height) { + /* Triangle is either completely above the uppermost scanline or + completely below the lowermost scanline. + */ + + return false; /* Actual value doesn't matter. */ + } + + { + unsigned int i; + + for (i = 1; i < 3; i++) { + if (xy._[i][0] < leftmost_x) { + leftmost_x = xy._[i][0]; + } + + if (xy._[i][0] > rightmost_x) { + rightmost_x = xy._[i][0]; + } + } + } + if (rightmost_x < 0 || leftmost_x >= width) { + /* Triangle is either completely to the left of the leftmost + framebuffer column or completely to the right of the rightmost + framebuffer column. + */ + return false; /* Actual value doesn't matter. */ + } + + if (xy._[0][1] == xy._[1][1] && xy._[1][1] == xy._[2][1]) { + /* Triangle is degenarate: its visual representation consists only of + a horizontal straight line. + */ + + bi->start_scanline = xy._[0][1]; + + return false; /* Actual value doesn't matter. */ + } + + mid_is_to_the_left = 2; + + int32_to_varying_array(&xy._[0][0], &top_x, 1); + int32_to_varying_array(&xy._[1][0], &mid_x, 1); + int32_to_varying_array(&xy._[2][0], &bot_x, 1); + + if (xy._[0][1] == xy._[1][1]) { + /* Triangle has only a lower part. */ + k = 1; + + mid_is_to_the_left = 0; + } else { + k = 0; + + if (xy._[1][1] == xy._[2][1]) { + /* Triangle has only an upper part (plus the row of the middle + vertex). + */ + mid_is_to_the_left = 1; + } + } + + prepare_for_interpolation(&top_x, &mid_x, &top2mid, xy._[1][1] - xy._[0][1], 1); + prepare_for_interpolation(&top_x, &bot_x, &top2bot, xy._[2][1] - xy._[0][1], 1); + prepare_for_interpolation(&mid_x, &bot_x, &mid2bot, xy._[2][1] - xy._[1][1], 1); + + if (mid_is_to_the_left == 2) { + mid_is_to_the_left = top2mid.s < top2bot.s; + } + + if (mid_is_to_the_left) { + upper_left = &top2mid; + lower_left = &mid2bot; + upper_right = &top2bot; + lower_right = upper_right; + } else { + upper_right = &top2mid; + lower_right = &mid2bot; + upper_left = &top2bot; + lower_left = upper_left; + } + + left[0] = upper_left; + left[1] = lower_left; + right[0] = upper_right; + right[1] = lower_right; + + num_rows_ptr[0] = &bi->num_upper_rows; + num_rows_ptr[1] = &bi->num_lower_rows; + + y = xy._[0][1]; + + i = 0; + + while (k < 2) { + int32_t end; + + end = xy._[k + 1][1] + k; /* initial value */ + + if (y < 0) { + int32_t delta; + + if (end > 0) { + delta = -y; + } else { + delta = xy._[k + 1][1] - y; + } + + y += delta; + + multi_step_up(left[k], delta, 1); + multi_step_up(right[k], delta, 1); + + if (y < 0) { + k++; + continue; + } + } else if(y >= height) { + return mid_is_to_the_left; + } + + if (end > height) { + end = height; + } + + while (y < end) { + if (round_varying(*left[k]) >= width || round_varying(*right[k]) < 0) { + if (bi->start_scanline > -1) { + return mid_is_to_the_left; + } + } else { + if (bi->start_scanline == -1) { + bi->start_scanline = y; + } + + bi->buffer[i++] = round_varying(*left[k]); + bi->buffer[i++] = round_varying(*right[k]); + + (*(num_rows_ptr[k]))++; + } + + step_up(left[k], 1); + step_up(right[k], 1); + + y++; + } + k++; + } + return mid_is_to_the_left; +} + + + +void +get_triangle_boundaries(uint16_t const row_index, + int32_t * const left, + int32_t * const right, + const boundary_info * const bi) { +/*---------------------------------------------------------------------------- + Return the left and right boundaries for a given VISIBLE triangle row (the + row index is relative to the first visible row). These values may be out of + the horizontal limits of the frame buffer, which is necessary in order to + compute correct attribute interpolations. +-----------------------------------------------------------------------------*/ + uint32_t const i = row_index << 1; + + *left = bi->buffer[i]; + *right = bi->buffer[i + 1]; +} + + diff --git a/generator/pamtris/boundaries.h b/generator/pamtris/boundaries.h new file mode 100644 index 00000000..70f7f90d --- /dev/null +++ b/generator/pamtris/boundaries.h @@ -0,0 +1,72 @@ +#ifndef BOUNDARIES_H_INCLUDED +#define BOUNDARIES_H_INCLUDED + +#include <stdbool.h> +#include <stdint.h> + +#include "triangle.h" + +typedef struct boundary_info { +/*---------------------------------------------------------------------------- + Information about visible triangle rows' boundaries. Also see the + "boundary buffer functions" below. + + A "visible" triangle row is one which: + + 1. Corresponds to a frame buffer row whose index (from top to bottom) is + equal to or greater than 0 and smaller than the image height; and + + 2. Has at least some of its pixels between the frame buffer columns whose + index (from left to right) is equal to or greater than 0 and smaller + than the image width. +-----------------------------------------------------------------------------*/ + int16_t start_scanline; + /* Index of the frame buffer scanline which contains the first visible + row of the current triangle, if there is any such row. If not, it + contains the value -1. + */ + + int16_t num_upper_rows; + /* The number of visible rows in the upper part of the triangle. The + upper part of a triangle is composed of all the rows starting from + the top vertex down to the middle vertex, but not including this + last one. + */ + + int16_t num_lower_rows; + /* The number of visible rows in the lower part of the triangle. The + lower part of a triangle is composed of all the rows from the + middle vertex to the bottom vertex -- all inclusive. + */ + + int16_t * buffer; + /* This is the "boundary buffer": a pointer to an array of int16_t's + where each consecutive pair of values indicates, in this order, the + columns of the left and right boundary pixels for a particular + visible triangle row. Those boundaries are inclusive on both sides + and may be outside the limits of the frame buffer. This field is + initialized and freed by the functions "init_boundary_buffer" and + "free_boundary_buffer", respectively. + */ +} boundary_info; + +void +init_boundary_buffer(boundary_info * const bdi, + int16_t const height); + +void +free_boundary_buffer(boundary_info *); + +bool +gen_triangle_boundaries(Xy const xy, + boundary_info * const bdi, + int16_t const width, + int16_t const height); + +void +get_triangle_boundaries(uint16_t const row_index, + int32_t * const left, + int32_t * const right, + const boundary_info * const bdi); + +#endif diff --git a/generator/pamtris/framebuffer.c b/generator/pamtris/framebuffer.c new file mode 100644 index 00000000..93263c91 --- /dev/null +++ b/generator/pamtris/framebuffer.c @@ -0,0 +1,339 @@ +/*============================================================================= + framebuffer.c +=============================================================================== + Frame buffer functions + + Every drawing operation is applied on an internal "frame buffer", which is + simply an "image buffer" which represents the picture currently being drawn, + along with a "Z-Buffer" which contains the depth values for every pixel in + the image buffer. Once all desired drawing operations for a particular + picture are effected, a function is provided to print the current contents + of the image buffer as a PAM image on standard output. Another function is + provided to clear the contents of the frame buffer (i. e. set all image + samples and Z-Buffer entries to 0), with the option of only clearing either + the image buffer or the Z-Buffer individually. + + The Z-Buffer works as follows: Every pixel in the image buffer has a + corresponding entry in the Z-Buffer. Initially, every entry in the Z-Buffer + is set to 0. Every time we desire to plot a pixel at some particular + position in the frame buffer, the current value of the corresponding entry + in the Z-Buffer is compared against the the Z component of the incoming + pixel. If MAX_Z minus the value of the Z component of the incoming pixel is + equal to or greater than the current value of the corresponding entry in the + Z-Buffer, the frame buffer is changed as follows: + + 1. All the samples but the last of the corresponding position in the + image buffer are set to equal those of the incoming pixel. + + 2. The last sample, that is, the A-component of the corresponding position + in the image buffer is set to equal the maxval. + + 3. The corresponding entry in the Z-Buffer is set to equal MAX_Z minus the + value of the Z component of the incoming pixel. + + Otherwise, no changes are made on the frame buffer. +=============================================================================*/ +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include <math.h> + +#include "utils.h" +#include "varying.h" +#include "limits_pamtris.h" + +#include "framebuffer.h" + + + +int +set_tupletype(const char * const str, + char * const tupletype) { +/*---------------------------------------------------------------------------- + Set the tuple type for the output PAM images given a string ("str") of 255 + characters or less. If the string has more than 255 characters, the function + returns 0. Otherwise, it returns 1. If NULL is given for the "str" argument, + the tuple type is set to a null string. This function is called during + program initialization and whenever a "r" command is executed. The second + argument must point to the tuple_type member of the "outpam" field in the + framebuffer_info struct. +-----------------------------------------------------------------------------*/ + if (str == NULL) { + memset(tupletype, 0, 256); + } else { + size_t len; + + len = strlen(str); /* initial value */ + + if (len > 255) { + return 0; + } + + if (len > 0) { + memcpy(tupletype, str, len); + } + + tupletype[len--] = '\0'; + + while(len > 0 && isspace(tupletype[len])) { + tupletype[len--] = '\0'; + } + } + + return 1; +} + + + +int +init_framebuffer(framebuffer_info * const fbi) { + + uint8_t const num_planes = fbi->num_attribs + 1; + + uint32_t const elements = fbi->width * fbi->height; + + fbi->img.bytes = elements * (num_planes * sizeof(uint16_t)); + fbi->z.bytes = elements * sizeof(uint32_t); + + fbi->img.buffer = + calloc(fbi->img.bytes / sizeof(uint16_t), sizeof(uint16_t)); + fbi->z.buffer = + calloc(fbi->z.bytes / sizeof(uint32_t), sizeof(uint32_t)); + + if(fbi->img.buffer == NULL || fbi->z.buffer == NULL) { + free(fbi->img.buffer); + free(fbi->z.buffer); + + return 0; + } + + fbi->outpam.size = sizeof(struct pam); + fbi->outpam.len = sizeof(struct pam); + fbi->outpam.file = stdout; + fbi->outpam.format = PAM_FORMAT; + fbi->outpam.plainformat = 0; + fbi->outpam.height = fbi->height; + fbi->outpam.width = fbi->width; + fbi->outpam.depth = num_planes; + fbi->outpam.maxval = fbi->maxval; + fbi->outpam.allocation_depth = 0; + fbi->outpam.comment_p = NULL; + + fbi->pamrow = NULL; + fbi->pamrow = pnm_allocpamrow(&fbi->outpam); + + if (fbi->pamrow == NULL) { + free(fbi->img.buffer); + free(fbi->z.buffer); + + return 0; + } + + return 1; +} + + + +void +free_framebuffer(framebuffer_info * const fbi) { + + free(fbi->img.buffer); + free(fbi->z.buffer); + + pnm_freepamrow(fbi->pamrow); +} + + + +int +realloc_image_buffer(int32_t const new_maxval, + int32_t const new_num_attribs, + framebuffer_info * const fbi) { +/*---------------------------------------------------------------------------- + Reallocate the image buffer with a new maxval and depth, given the struct + with information about the framebuffer. The fields variables "maxval" and + "num_attribs". + + From the point this function is called onwards, new PAM images printed on + standard output will have the new maxval for the maxval and num_attribs + 1 + for the depth. + + This function does *not* check whether the new maxval and num_attribs are + within the proper allowed limits. That is done inside the input processing + function "process_next_command", which is the only function that calls this + one. + + If the function suceeds, the image buffer is left in cleared state. The + Z-Buffer, however, is not touched at all. + + If the new depth is equal to the previous one, no actual reallocation is + performed: only the global variable "maxval" is changed. But the image + buffer is nonetheless left in cleared state regardless. +-----------------------------------------------------------------------------*/ + uint8_t num_planes; + + pnm_freepamrow(fbi->pamrow); + fbi->pamrow = NULL; + + num_planes = fbi->num_attribs + 1; /* initial value */ + + if (new_num_attribs != fbi->num_attribs) { + fbi->num_attribs = new_num_attribs; + num_planes = fbi->num_attribs + 1; + + fbi->img.bytes = + fbi->width * fbi->height * (num_planes * sizeof(uint16_t)); + + { + uint16_t * const new_ptr = + realloc(fbi->img.buffer, fbi->img.bytes); + + if (new_ptr == NULL) { + free(fbi->img.buffer); + fbi->img.buffer = NULL; + + return 0; + } + fbi->img.buffer = new_ptr; + } + } + + fbi->maxval = new_maxval; + + fbi->outpam.size = sizeof(struct pam); + fbi->outpam.len = sizeof(struct pam); + fbi->outpam.file = stdout; + fbi->outpam.format = PAM_FORMAT; + fbi->outpam.plainformat = 0; + fbi->outpam.height = fbi->height; + fbi->outpam.width = fbi->width; + fbi->outpam.depth = num_planes; + fbi->outpam.maxval = fbi->maxval; + fbi->outpam.allocation_depth = 0; + fbi->outpam.comment_p = NULL; + + fbi->pamrow = pnm_allocpamrow(&fbi->outpam); + + if (fbi->pamrow == NULL) { + free(fbi->img.buffer); + fbi->img.buffer = NULL; + + return 0; + } + + memset(fbi->img.buffer, 0, fbi->img.bytes); + + return 1; +} + + + +void +print_framebuffer(framebuffer_info * const fbi) { + + uint8_t const num_planes = fbi->num_attribs + 1; + uint32_t const end = fbi->width * fbi->height; + + uint32_t i; + + pnm_writepaminit(&fbi->outpam); + + for (i = 0; i != end; ) { + int j; + for (j = 0; j < fbi->width; j++) { + uint32_t const k = (i + j) * num_planes; + + unsigned int l; + + for (l = 0; l < num_planes; l++) { + fbi->pamrow[j][l] = fbi->img.buffer[k + l]; + } + } + + pnm_writepamrow(&fbi->outpam, fbi->pamrow); + + i += fbi->width; + } +} + + + +void +clear_framebuffer(bool const clear_image_buffer, + bool const clear_z_buffer, + framebuffer_info * const fbi) { + + if (clear_image_buffer) { + memset(fbi->img.buffer, 0, fbi->img.bytes); + } + + if (clear_z_buffer) { + memset(fbi->z.buffer, 0, fbi->z.bytes); + } +} + + + +void +draw_span(uint32_t const base, + uint16_t const length, + varying * const attribs, + framebuffer_info * const fbi) { +/*---------------------------------------------------------------------------- + Draw a horizontal span of "length" pixels into the frame buffer, performing + the appropriate depth tests. "base" must equal the row of the frame buffer + where one desires to draw the span *times* the image width, plus the column + of the first pixel in the span. + + This function does not perform any kind of bounds checking. +-----------------------------------------------------------------------------*/ + static double const depth_range = MAX_Z; + + uint16_t const maxval = fbi->maxval; + uint8_t const z = fbi->num_attribs; + uint8_t const w = z + 1; + uint8_t const n = w + 1; + + uint8_t const num_planes = w; + + unsigned int i; + + /* Process each pixel in the span: */ + + for (i = 0; i < length; i++) { + int32_t const d = round(depth_range * attribs[z].v); + uint32_t const d_mask = geq_mask64(d, fbi->z.buffer[base + i]); + + uint32_t const j = base + i; + uint32_t const k = j * num_planes; + + varying const inverse_w = inverse_varying(attribs[w]); + + unsigned int l; + + /* The following statements will only have any effect if the depth + test, performed above, has suceeded. I. e. if the depth test fails, + no changes will be made on the frame buffer; otherwise, the + frame buffer will be updated with the new values. + */ + fbi->z.buffer[j] = (fbi->z.buffer[j] & ~d_mask) | (d & d_mask); + + for (l = 0; l < z; l++) { + varying const newval = multiply_varyings(attribs[l], inverse_w); + + fbi->img.buffer[k + l] = + (fbi->img.buffer[k + l] & ~d_mask) | + (round_varying(newval) & d_mask); + } + + fbi->img.buffer[k + z] |= (maxval & d_mask); + + /* Compute the attribute values for the next pixel: */ + + step_up(attribs, n); + } +} + + + diff --git a/generator/pamtris/framebuffer.h b/generator/pamtris/framebuffer.h new file mode 100644 index 00000000..b3d4f7a3 --- /dev/null +++ b/generator/pamtris/framebuffer.h @@ -0,0 +1,75 @@ +#ifndef FRAMEBUFFER_H_INCLUDED +#define FRAMEBUFFER_H_INCLUDED + +#include <stdint.h> +#include <stdbool.h> + +#include "varying.h" +#include "netpbm/pam.h" + +typedef struct framebuffer_info { +/*---------------------------------------------------------------------------- + Information about the frame buffer and PAM output +-----------------------------------------------------------------------------*/ + /* These fields are initialized once by reading the command line + arguments. "maxval" and "num_attribs" may be modified later + through "realloc_image_buffer"; "correct" may also be modified + if the eponymous command is given. + */ + int32_t width; + int32_t height; + int32_t maxval; + int32_t num_attribs; + + /* The fields below must be initialized by "init_framebuffer" and + freed by "free_framebuffer", except for the tuple_type field in + "outpam" which is initialized once by reading the command line + arguments and may be modified later through "set_tupletype". + */ + struct { + uint16_t * buffer; + uint32_t bytes; + } img; /* Image buffer */ + + struct { + uint32_t * buffer; + uint32_t bytes; + } z; /* Z-buffer */ + + struct pam outpam; + + tuple * pamrow; +} framebuffer_info; + + + +int +set_tupletype(const char * const str, + char * const tupletype); + +int +init_framebuffer(framebuffer_info * const fbi); + +void +free_framebuffer(framebuffer_info * const fbi); + +void +print_framebuffer(framebuffer_info * const fbi); + +void +clear_framebuffer(bool const clear_image_buffer, + bool const clear_z_buffer, + framebuffer_info * const fbi); + +int +realloc_image_buffer(int32_t const new_maxval, + int32_t const new_num_attribs, + framebuffer_info * const fbi); + +void +draw_span(uint32_t const base, + uint16_t const length, + varying * const attribs, + framebuffer_info * const fbi); + +#endif diff --git a/generator/pamtris/input.c b/generator/pamtris/input.c new file mode 100644 index 00000000..ffb2a859 --- /dev/null +++ b/generator/pamtris/input.c @@ -0,0 +1,695 @@ +/*============================================================================= + input.c +=============================================================================== + Input handling functions +=============================================================================*/ +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <stdio.h> +#include <ctype.h> + +#include "netpbm/mallocvar.h" +#include "netpbm/pm.h" +#include "netpbm/nstring.h" + +#include "limits_pamtris.h" +#include "framebuffer.h" +#include "triangle.h" + +#include "input.h" + +#define DRAW_MODE_TRIANGLES 1 +#define DRAW_MODE_STRIP 2 +#define DRAW_MODE_FAN 3 + +#define CMD_SET_MODE "mode" +#define CMD_SET_ATTRIBS "attribs" +#define CMD_VERTEX "vertex" +#define CMD_PRINT "print" +#define CMD_CLEAR "clear" +#define CMD_RESET "reset" +#define CMD_QUIT "quit" + +#define ARG_TRIANGLES "triangles" +#define ARG_STRIP "strip" +#define ARG_FAN "fan" +#define ARG_IMAGE "image" +#define ARG_DEPTH "depth" + + +typedef struct { + Xy v_xy; + /* X- and Y-coordinates of the vertices for the current triangle. + */ + Attribs v_attribs; + /* Vertex attributes for the current triangle. Includes the + Z-coordinates. + */ + int32_t curr_attribs[MAX_NUM_ATTRIBS]; + /* Attributes that will be assigned to the next vertex. Does not + include the Z-coordinate. + */ + uint8_t next; + /* Index of the next vertex to be read. */ + bool draw; + /* If true, draws a new triangle upon reading a new vertex. */ + + uint8_t mode; + /* Drawing mode. */ + + bool initialized; +} state_info; + + + +static void +clearAttribs(state_info * const si, + int32_t const maxval, + int16_t const num_attribs) { + + unsigned int i; + + for (i = 0; i < num_attribs; ++i) { + si->curr_attribs[i] = maxval; + } +} + + + +void +input_init(Input * const inputP) { + + inputP->buffer = NULL; + inputP->length = 0; + inputP->number = 1; +} + + + +void +input_term(Input * const inputP) { + + if (inputP->buffer) + free(inputP->buffer); +} + + + +typedef struct { +/*---------------------------------------------------------------------------- + Indicates a whitespace-delimited input symbol. "begin" points to its first + character, and "end" points to one position past its last character. +-----------------------------------------------------------------------------*/ + char * begin; + char * end; +} Token; + + + +static Token +nextToken(char * const startPos) { + + Token retval; + char * p; + + for (p = startPos; *p && isspace(*p); ++p); + + retval.begin = p; + + for (; *p && !isspace(*p); ++p); + + retval.end = p; + + return retval; +} + + + +static bool +stringIsValid(const char * const target, + const char * const srcBegin, + const char * const srcEnd) { + + unsigned int charsMatched; + const char * p; + + for (p = srcBegin, charsMatched = 0; + p != srcEnd && target[charsMatched] != '\0'; ++p) { + + if (*p == target[charsMatched]) + ++charsMatched; + else + break; + } + + return (*p == '\0' || isspace(*p)); +} + + + +static void +initState(state_info * const siP) { + + siP->next = 0; + siP->draw = false; + siP->mode = DRAW_MODE_TRIANGLES; +} + + + +static void +makeLowercase(Token const t) { + + char * p; + + for (p = t.begin; p != t.end; ++p) + *p = tolower(*p); +} + + + +static void +removeComments(char * const str) { + + char * p; + + for (p = &str[0]; *p; ++p) { + if (*p == '#') { + *p = '\0'; + + break; + } + } +} + + + +static void +processM(Token * const ntP, + state_info * const stateP, + bool * const unrecognizedCmdP, + const char ** const errorP) { + + if (!stringIsValid(CMD_SET_MODE, ntP->begin, ntP->end)) { + *unrecognizedCmdP = true; + } else { + *ntP = nextToken(ntP->end); + + *unrecognizedCmdP = false; + + if (*ntP->begin == '\0') + pm_asprintf(errorP, "syntax error"); + else { + makeLowercase(*ntP); + + switch (*ntP->begin) { + case 't': + if (!stringIsValid(ARG_TRIANGLES, ntP->begin, ntP->end)) + pm_asprintf(errorP, "unrecognized drawing mode"); + else { + stateP->mode = DRAW_MODE_TRIANGLES; + stateP->draw = false; + stateP->next = 0; + + *errorP = NULL; + } + break; + case 's': + if (!stringIsValid(ARG_STRIP, ntP->begin, ntP->end)) + pm_asprintf(errorP, "unrecognized drawing mode"); + else { + stateP->mode = DRAW_MODE_STRIP; + stateP->draw = false; + stateP->next = 0; + + *errorP = NULL; + } + break; + case 'f': + if (!stringIsValid(ARG_FAN, ntP->begin, ntP->end)) + pm_asprintf(errorP, "unrecognized drawing mode"); + else { + stateP->mode = DRAW_MODE_FAN; + stateP->draw = false; + stateP->next = 0; + + *errorP = NULL; + } + break; + default: + pm_asprintf(errorP, "unrecognized drawing mode"); + } + } + } +} + + + +static void +processA(Token * const ntP, + state_info * const stateP, + framebuffer_info * const fbiP, + bool * const unrecognizedCmdP, + long int * const iArgs, + const char ** const errorP) { + + if (!stringIsValid(CMD_SET_ATTRIBS, ntP->begin, ntP->end)) { + *unrecognizedCmdP = true; + } else { + unsigned int i; + + *unrecognizedCmdP = false; + + for (i = 0, *errorP = NULL; i < fbiP->num_attribs && !*errorP; ++i) { + char * strtolEnd; + + *ntP = nextToken(ntP->end); + + iArgs[i] = strtol(ntP->begin, &strtolEnd, 10); + + if (*ntP->begin == '\0' || strtolEnd != ntP->end) + pm_asprintf(errorP, "syntax error"); + else { + if (iArgs[i] < 0 || iArgs[i] > fbiP->maxval) + pm_asprintf(errorP, "argument(s) out of bounds"); + } + } + + if (!*errorP) { + unsigned int i; + + for (i = 0; i < fbiP->num_attribs; ++i) + stateP->curr_attribs[i] = iArgs[i]; + } + } +} + + + +static void +processV(Token * const ntP, + state_info * const stateP, + struct boundary_info * const biP, + framebuffer_info * const fbiP, + bool * const unrecognizedCmdP, + long int * const iArgs, + const char ** const errorP) { + + if (!stringIsValid(CMD_VERTEX, ntP->begin, ntP->end)) + *unrecognizedCmdP = true; + else { + unsigned int i; + + *unrecognizedCmdP = false; + + for (i = 0, *errorP = NULL; i < 4 && !*errorP; ++i) { + char * strtolEnd; + + *ntP = nextToken(ntP->end); + + iArgs[i] = strtol(ntP->begin, &strtolEnd, 10); + + if (*ntP->begin == '\0') { + if (i != 3) + pm_asprintf(errorP, "syntax error"); + else + iArgs[i] = 1; + } else { + if (strtolEnd != ntP->end) + pm_asprintf(errorP, "syntax error"); + } + + if (!*errorP) { + if (i < 3) { + if (iArgs[i] < MIN_COORD || iArgs[i] > MAX_COORD) + pm_asprintf(errorP, "coordinates out of bounds"); + } else { + if (iArgs[i] < MIN_INPUT_W || iArgs[i] > MAX_INPUT_W) + pm_asprintf(errorP, + "perspective correction factor (w) " + "out of bounds"); + } + } + } + + if (!*errorP) { + unsigned int i; + + for (i = 0; i < fbiP->num_attribs; ++i) { + stateP->v_attribs._[stateP->next][i] = stateP->curr_attribs[i]; + } + + stateP->v_attribs._[stateP->next][fbiP->num_attribs + 0] = + iArgs[2]; + stateP->v_attribs._[stateP->next][fbiP->num_attribs + 1] = + iArgs[3]; + + stateP->v_xy._[stateP->next][0] = iArgs[0]; + stateP->v_xy._[stateP->next][1] = iArgs[1]; + + ++stateP->next; + + if (!stateP->draw) { + if (stateP->next == 3) + stateP->draw = true; + } + + if (stateP->draw) + draw_triangle(stateP->v_xy, stateP->v_attribs, biP, fbiP); + + if (stateP->next == 3) { + switch(stateP->mode) { + case DRAW_MODE_FAN: + stateP->next = 1; + break; + case DRAW_MODE_TRIANGLES: + stateP->draw = false; + stateP->next = 0; + break; + case DRAW_MODE_STRIP: + stateP->next = 0; + break; + default: + stateP->next = 0; + } + } + } + } +} + + + +static void +processP(Token * const ntP, + framebuffer_info * const fbiP, + bool * const unrecognizedCmdP, + const char ** const errorP) { + + if (!stringIsValid(CMD_PRINT, ntP->begin, ntP->end)) + *unrecognizedCmdP = true; + else { + *unrecognizedCmdP = false; + + print_framebuffer(fbiP); + + *errorP = NULL; + } +} + + + + +static void +processExcl(Token * const ntP, + framebuffer_info * const fbiP, + bool * const unrecognizedCmdP, + const char ** const errorP) { + + if (ntP->end - ntP->begin > 1) + *unrecognizedCmdP = true; + else { + *unrecognizedCmdP = false; + + print_framebuffer(fbiP); + + *errorP = NULL; + } +} + + + +static void +clear(Token * const ntP, + framebuffer_info * const fbiP, + const char ** const errorP) { + + *ntP = nextToken(ntP->end); + + if (*ntP->begin != '\0') { + makeLowercase(*ntP); + + switch(*ntP->begin) { + case 'i': + if (!stringIsValid("image", ntP->begin, ntP->end)) + pm_asprintf(errorP, "unrecognized argument"); + else { + clear_framebuffer(true, false, fbiP); + *errorP = NULL; + } + break; + case 'd': + if (!stringIsValid("depth", ntP->begin, ntP->end)) + pm_asprintf(errorP, "unrecognized argument"); + else { + clear_framebuffer(false, true, fbiP); + *errorP = NULL; + } + break; + case 'z': + if (ntP->end - ntP->begin > 1) + pm_asprintf(errorP, "unrecognized argument"); + else { + clear_framebuffer(false, true, fbiP); + *errorP = NULL; + } + break; + default: + pm_asprintf(errorP, "unrecognized argument"); + } + } else { + clear_framebuffer(true, true, fbiP); + *errorP = NULL; + } +} + + + +static void +processC(Token * const ntP, + framebuffer_info * const fbiP, + bool * const unrecognizedCmdP, + const char ** const errorP) { + + if (!stringIsValid(CMD_CLEAR, ntP->begin, ntP->end)) + *unrecognizedCmdP = true; + else { + *unrecognizedCmdP = false; + + clear(ntP, fbiP, errorP); + } +} + + + +static void +processAsterisk(Token * const ntP, + framebuffer_info * const fbiP, + bool * const unrecognizedCmdP, + const char ** const errorP) { + + if (ntP->end - ntP->begin > 1) + *unrecognizedCmdP = true; + else { + *unrecognizedCmdP = false; + + clear(ntP, fbiP, errorP); + } +} + + + +static void +processR(Token * const ntP, + state_info * const stateP, + framebuffer_info * const fbiP, + bool * const unrecognizedCmdP, + long int * const iArgs, + const char ** const errorP) { + + if (!stringIsValid(CMD_RESET, ntP->begin, ntP->end)) + *unrecognizedCmdP = true; + else { + unsigned int i; + + *unrecognizedCmdP = false; + + for (i = 0, *errorP = NULL; i < 2 && !*errorP; ++i) { + char * strtolEnd; + + *ntP = nextToken(ntP->end); + + iArgs[i] = strtol(ntP->begin, &strtolEnd, 10); + + if (*ntP->begin == '\0' || ntP->end != strtolEnd) + pm_asprintf(errorP, "syntax error"); + } + + if (!*errorP) { + if (iArgs[0] < 1 || iArgs[0] > PAM_OVERALL_MAXVAL) + pm_asprintf(errorP, "invalid new maxval"); + else { + if (iArgs[1] < 1 || iArgs[1] > MAX_NUM_ATTRIBS) + pm_asprintf(errorP, "invalid new number of generic vertex " + "attributes"); + else { + *ntP = nextToken(ntP->end); + + if (*ntP->begin != '\0') { + if (!set_tupletype(ntP->begin, + fbiP->outpam.tuple_type)) { + pm_message( + "warning: could not set new tuple type; " + "using a null string"); + set_tupletype(NULL, fbiP->outpam.tuple_type); + } + } else + set_tupletype(NULL, fbiP->outpam.tuple_type); + + if (!realloc_image_buffer(iArgs[0], iArgs[1], fbiP)) { + pm_error("Unable to allocate memory for " + "image buffer"); + } + + stateP->next = 0; + stateP->draw = false; + + clearAttribs(stateP, fbiP->maxval, fbiP->num_attribs); + } + } + } + } +} + + + +static void +processQ(Token * const ntP, + bool * const unrecognizedCmdP, + bool * const noMoreCommandsP, + const char ** const errorP) { + + if (!stringIsValid(CMD_QUIT, ntP->begin, ntP->end)) + *unrecognizedCmdP = true; + else { + *unrecognizedCmdP = false; + + *noMoreCommandsP = true; + + *errorP = NULL; + } +} + + + +void +input_process_next_command(Input * const inputP, + struct boundary_info * const biP, + framebuffer_info * const fbiP, + bool * const noMoreCommandsP) { +/*---------------------------------------------------------------------------- + Doesn't necessarily process a command, just the next line of input, which + may be empty. + + Return *noMoreCommandsP true iff the next command is a quit command of + there is no next command. +-----------------------------------------------------------------------------*/ + static state_info state; + + Token nt; + + long int iArgs[MAX_NUM_ATTRIBS]; + /* For storing potential integer arguments. */ + bool unrecognizedCmd; + /* Unrecognized command detected */ + bool noMoreCommands; + const char * error; + /* Description of problem with the command; NULL if no problem. + Meaningful only when 'unrecognizedCmd' is false. + */ + + if (!state.initialized) { + initState(&state); + clearAttribs(&state, fbiP->maxval, fbiP->num_attribs); + + state.initialized = true; + } + + { + int eof; + size_t lineLen; + + pm_getline(stdin, &inputP->buffer, &inputP->length, &eof, &lineLen); + + if (eof) { + *noMoreCommandsP = true; + return; + } + } + + removeComments(inputP->buffer); + + nt = nextToken(inputP->buffer); + + makeLowercase(nt); + + noMoreCommands = false; /* initial assumption */ + + switch (nt.begin[0]) { + case 'm': + processM(&nt, &state, &unrecognizedCmd, &error); + break; + case 'a': + processA(&nt, &state, fbiP, &unrecognizedCmd, iArgs, &error); + break; + case 'v': + processV(&nt, &state, biP, fbiP, &unrecognizedCmd, iArgs, &error); + break; + case 'p': + processP(&nt, fbiP, &unrecognizedCmd, &error); + break; + case '!': + processExcl(&nt, fbiP, &unrecognizedCmd, &error); + break; + case 'c': + processC(&nt, fbiP, &unrecognizedCmd, &error); + break; + case '*': + processAsterisk(&nt, fbiP, &unrecognizedCmd, &error); + break; + case 'r': + processR(&nt, &state, fbiP, &unrecognizedCmd, iArgs, &error); + break; + case 'q': + processQ(&nt, &unrecognizedCmd, &noMoreCommands, &error); + break; + case '\0': + break; + default: + unrecognizedCmd = true; + } + + if (!noMoreCommands) { + char const next = *nextToken(nt.end).begin; + + if (unrecognizedCmd) { + pm_errormsg("error: unrecognized command: line %u.", + (unsigned)inputP->number); + } else { + if (error) { + pm_errormsg("Error in line %u: %s", + (unsigned)inputP->number, error); + pm_strfree(error); + } else { + if (next != '\0') + pm_message("warning: ignoring excess arguments: line %u", + (unsigned)inputP->number); + } + } + } + ++inputP->number; + + *noMoreCommandsP = noMoreCommands; +} + + diff --git a/generator/pamtris/input.h b/generator/pamtris/input.h new file mode 100644 index 00000000..d34de3a1 --- /dev/null +++ b/generator/pamtris/input.h @@ -0,0 +1,27 @@ +#ifndef INPUT_H_INCLUDED +#define INPUT_H_INCLUDED + +#include <stdint.h> + +struct boundary_info; +struct framebuffer_info; + +typedef struct { + char * buffer; + size_t length; + uint64_t number; +} Input; + +void +input_init(Input * const inputP); + +void +input_term(Input * const inputP); + +void +input_process_next_command(Input * const inputP, + struct boundary_info * const bdiP, + struct framebuffer_info * const fbiP, + bool * const noMoreCommandsP); + +#endif diff --git a/generator/pamtris/limits_pamtris.h b/generator/pamtris/limits_pamtris.h new file mode 100644 index 00000000..a7ed503f --- /dev/null +++ b/generator/pamtris/limits_pamtris.h @@ -0,0 +1,11 @@ +#ifndef LIMITS_H_INCLUDED +#define LIMITS_H_INCLUDED + +#define MAX_NUM_ATTRIBS 20 +#define MAX_COORD 32767 +#define MIN_COORD (-MAX_COORD) +#define MAX_INPUT_W 1048575 +#define MIN_INPUT_W 1 +#define MAX_Z 0x3FFFFFFF + +#endif diff --git a/generator/pamtris/pamtris.c b/generator/pamtris/pamtris.c new file mode 100644 index 00000000..e0becf7a --- /dev/null +++ b/generator/pamtris/pamtris.c @@ -0,0 +1,171 @@ +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> + +#include "netpbm/mallocvar.h" +#include "netpbm/shhopt.h" +#include "netpbm/pam.h" + +#include "limits_pamtris.h" +#include "framebuffer.h" +#include "boundaries.h" +#include "input.h" + +#define MAX_METRICS 8192 + + + +static int +parse_command_line(int * const argc_ptr, + const char ** const argv, + int32_t * const width, + int32_t * const height, + int32_t * const maxval, + int32_t * const num_attribs, + char * const tupletype) { + + optEntry * option_def; + optStruct3 opt; + /* Instructions to pm_optParseOptions3 on how to parse our options */ + unsigned int option_def_index; + + char * tupletype_tmp; + + unsigned int width_spec, height_spec, attribs_spec, tupletype_spec; + unsigned int rgb_spec, grayscale_spec, maxval_spec; + + MALLOCARRAY_NOFAIL(option_def, 100); + + option_def_index = 0; /* incremented by OPTENT3 */ + OPTENT3(0, "width", OPT_INT, width, &width_spec, 0); + OPTENT3(0, "height", OPT_INT, height, &height_spec, 0); + OPTENT3(0, "num_attribs", OPT_INT, num_attribs, &attribs_spec, 0); + OPTENT3(0, "tupletype", OPT_STRING, &tupletype_tmp, &tupletype_spec, 0); + OPTENT3(0, "rgb", OPT_FLAG, NULL, &rgb_spec, 0); + OPTENT3(0, "grayscale", OPT_FLAG, NULL, &grayscale_spec, 0); + OPTENT3(0, "maxval", OPT_INT, maxval, &maxval_spec, 0); + + opt.opt_table = option_def; + opt.short_allowed = false; + opt.allowNegNum = false; + + pm_optParseOptions3(argc_ptr, (char **)argv, opt, sizeof(opt), 0); + + if (!width_spec || !height_spec || (!attribs_spec && !(rgb_spec || grayscale_spec))) { + pm_errormsg( + "you must at least specify -width, -height and " + "either -num_attribs, -rgb or -grayscale."); + + return 0; + } + + if (rgb_spec + grayscale_spec + attribs_spec != 1) { + pm_errormsg("you must provide either only -num_attribs, " + "-rgb or -grayscale; not a combination of those."); + + return 0; + } + + if (*width < 1 || *width > MAX_METRICS) { + pm_errormsg("invalid width."); + + return 0; + } + + if (*height < 1 || *height > MAX_METRICS) { + pm_errormsg("invalid height."); + + return 0; + } + + if (maxval_spec) { + if (*maxval < 1 || *maxval > PAM_OVERALL_MAXVAL) { + pm_errormsg("invalid maxval."); + + return 0; + } + } else { + *maxval = 255; + } + + if (rgb_spec) { + *num_attribs = 3; + set_tupletype("RGB_ALPHA", tupletype); + } + + if (grayscale_spec) { + *num_attribs = 1; + set_tupletype("GRAYSCALE_ALPHA", tupletype); + } + + if (*num_attribs < 1 || *num_attribs > MAX_NUM_ATTRIBS) { + pm_errormsg("invalid number of generic attributes per vertex."); + + return 0; + } + + if (tupletype_spec) { + if(rgb_spec || grayscale_spec) { + pm_errormsg("you may not provide -tupletype together with " + "-rgb or -grayscale."); + + return 0; + } + + if (!set_tupletype(tupletype_tmp, tupletype)) { + pm_errormsg("warning: invalid tuple type; using empty string."); + + set_tupletype(NULL, tupletype); + } + } + + free(option_def); + + return 1; +} + + + +int +main(int argc, const char ** argv) { + + framebuffer_info fbi; + boundary_info bi; + Input input; + bool no_more_commands; + + pm_proginit(&argc, (const char**)argv); + + set_tupletype(NULL, fbi.outpam.tuple_type); + + if (!parse_command_line(&argc, + argv, + &fbi.width, + &fbi.height, + &fbi.maxval, + &fbi.num_attribs, + fbi.outpam.tuple_type)) { + return 1; + } + + if (!init_framebuffer(&fbi)) { + pm_errormsg("out of memory."); + + return 3; + } + + init_boundary_buffer(&bi, fbi.height); + + input_init(&input); + + for (no_more_commands = false; !no_more_commands; ) + input_process_next_command(&input, &bi, &fbi, &no_more_commands); + + input_term(&input); + free_boundary_buffer(&bi); + free_framebuffer(&fbi); + + return 0; +} + + diff --git a/generator/pamtris/triangle.c b/generator/pamtris/triangle.c new file mode 100644 index 00000000..5143f9ee --- /dev/null +++ b/generator/pamtris/triangle.c @@ -0,0 +1,327 @@ +/*============================================================================= + triangle.c +=============================================================================== + Triangle functions +=============================================================================*/ +#include <stdlib.h> +#include <string.h> + +#include "netpbm/mallocvar.h" + +#include "utils.h" +#include "varying.h" +#include "boundaries.h" +#include "framebuffer.h" + +#include "triangle.h" + +static void +draw_partial_triangle( + const varying * const left_attribs_input, + const varying * const rght_attribs_input, + bool const upper_part, + const boundary_info * const bi, + framebuffer_info * const fbi) { + + uint8_t const z = fbi->num_attribs; + uint8_t const w = z + 1; + uint8_t const n = w + 1; + + varying * left_attribs; + varying * rght_attribs; + + varying * attribs; + + int32_t first_row_index; + int32_t last_row_index; + + MALLOCARRAY_NOFAIL(left_attribs, n); + MALLOCARRAY_NOFAIL(rght_attribs, n); + MALLOCARRAY_NOFAIL(attribs, n); + + memcpy(left_attribs, left_attribs_input, n * sizeof(varying)); + memcpy(rght_attribs, rght_attribs_input, n * sizeof(varying)); + + if (upper_part) { + first_row_index = 0; + last_row_index = bi->num_upper_rows - 1; + } else { + first_row_index = bi->num_upper_rows; + last_row_index = bi->num_upper_rows + bi->num_lower_rows - 1; + } + + { + int32_t const row_delta = last_row_index - first_row_index; + + int32_t row; + + int32_t left_boundary; + int32_t rght_boundary; + + for (row = first_row_index; row <= last_row_index; row++) { + get_triangle_boundaries(row, &left_boundary, &rght_boundary, bi); + { + int32_t const column_delta = rght_boundary - left_boundary; + int32_t start_column; + int32_t span_length; + + start_column = left_boundary; /* initial value */ + span_length = column_delta; /* initial value */ + + prepare_for_interpolation(left_attribs, rght_attribs, + attribs, column_delta, + n); + + if (left_boundary < 0) { + start_column = 0; + + span_length += left_boundary; + + multi_step_up(attribs, -left_boundary, n); + } + + if (rght_boundary >= fbi->width) { + span_length -= rght_boundary - fbi->width; + } else { + span_length++; + } + + draw_span( + (bi->start_scanline + row) * fbi->width + start_column, + span_length, attribs, fbi); + + if (row_delta > 0) { + step_up(left_attribs, n); + step_up(rght_attribs, n); + } + } + } + } + free(attribs); + free(rght_attribs); + free(left_attribs); +} + + + +static void +draw_degenerate_horizontal(Xy const xy, + varying * const top2mid, + varying * const top2bot, + varying * const mid2bot, + framebuffer_info * const fbi) { + + uint8_t const n = fbi->num_attribs + 2; + + { + int16_t const y = xy._[0][1]; + + int16_t x[3]; + int16_t x_start[3]; + varying * attribs[3]; + int32_t span_length[3]; + unsigned int i; + + x[0] = xy._[0][0]; + x[1] = xy._[1][0]; + x[2] = xy._[2][0]; + + x_start[0] = x[0]; + x_start[1] = x[0]; + x_start[2] = x[1]; + + attribs[0] = top2bot; + attribs[1] = top2mid; + attribs[2] = mid2bot; + + span_length[0] = x[2] - x[0]; + span_length[1] = x[1] - x[0]; + span_length[2] = x[2] - x[1]; + + for (i = 0; i < 3; i++) { + if (x_start[i] >= fbi->width || x_start[i] + span_length[i] < 0) { + continue; + } + + if (x_start[i] < 0) { + multi_step_up(attribs[i], -x_start[i], n); + + span_length[i] += x_start[i]; + + x_start[i] = 0; + } + + if (x_start[i] + span_length[i] >= fbi->width) { + span_length[i] -= x_start[i] + span_length[i] - fbi->width; + } else { + span_length[i]++; + } + + draw_span(y * fbi->width + x_start[i], span_length[i], + attribs[i], fbi); + } + } +} + + + +void +draw_triangle(Xy const xy_input, + Attribs const attribs_input, + boundary_info * const bi, + framebuffer_info * const fbi) { + + uint8_t const z = fbi->num_attribs; + uint8_t const w = z + 1; + uint8_t const n = w + 1; + + Xy xy; + varying * attribs[3]; + unsigned int i; + uint8_t index_array[3]; + int32_t y_array[3]; + int32_t x_array[3]; + + MALLOCARRAY_NOFAIL(attribs[0], n); + MALLOCARRAY_NOFAIL(attribs[1], n); + MALLOCARRAY_NOFAIL(attribs[2], n); + + xy = xy_input; + + for (i = 0; i < 3; i++) { + int32_to_varying_array(attribs_input._[i], attribs[i], n); + attribs[i][z] = compute_varying_z(attribs_input._[i][z]); + attribs[i][w] = inverse_varying(attribs[i][w]); + multiply_varying_array_by_varying(attribs[i], attribs[i][w], z); + } + + /* Argument preparations for sort3: */ + + index_array[0] = 0; index_array[1] = 1; index_array[2] = 2; + y_array[0] = xy._[0][1]; y_array[1] = xy._[1][1]; y_array[2] = xy._[2][1]; + x_array[0] = xy._[0][0]; x_array[1] = xy._[1][0]; x_array[2] = xy._[2][0]; + + sort3(index_array, y_array, x_array); + + { + uint8_t const top = index_array[0]; + uint8_t const mid = index_array[1]; + uint8_t const bot = index_array[2]; + + bool mid_is_to_the_left; + + Xy xy_sorted; + + xy_sorted._[0][0] = xy._[top][0]; + xy_sorted._[0][1] = xy._[top][1]; + xy_sorted._[1][0] = xy._[mid][0]; + xy_sorted._[1][1] = xy._[mid][1]; + xy_sorted._[2][0] = xy._[bot][0]; + xy_sorted._[2][1] = xy._[bot][1]; + + mid_is_to_the_left = + gen_triangle_boundaries(xy_sorted, bi, fbi->width, fbi->height); + + if (bi->start_scanline == -1) { + /* Triangle is completely out of the bounds of the frame buffer. */ + } else { + bool const no_upper_part = + (xy_sorted._[1][1] == xy_sorted._[0][1]); + + bool const horizontal = + (xy._[0][1] == xy._[1][1] && xy._[1][1] == xy._[2][1]); + /* Tells whether we are dealing with a degenerate + * horizontal triangle */ + + uint8_t const t = horizontal ^ 1; + + int32_t top2mid_delta = xy._[mid][t] - xy._[top][t]; + int32_t top2bot_delta = xy._[bot][t] - xy._[top][t]; + int32_t mid2bot_delta = xy._[bot][t] - xy._[mid][t]; + + varying * top2mid; + varying * top2bot; + varying * mid2bot; + + varying * upper_left_attribs; + varying * lower_left_attribs; + varying * upper_rght_attribs; + varying * lower_rght_attribs; + + MALLOCARRAY_NOFAIL(top2mid, n); + MALLOCARRAY_NOFAIL(top2bot, n); + MALLOCARRAY_NOFAIL(mid2bot, n); + + prepare_for_interpolation(attribs[top], attribs[mid], top2mid, top2mid_delta, n); + prepare_for_interpolation(attribs[top], attribs[bot], top2bot, top2bot_delta, n); + prepare_for_interpolation(attribs[mid], attribs[bot], mid2bot, mid2bot_delta, n); + + if (mid_is_to_the_left) { + upper_left_attribs = top2mid; + lower_left_attribs = mid2bot; + upper_rght_attribs = top2bot; + lower_rght_attribs = upper_rght_attribs; + } else { + upper_rght_attribs = top2mid; + lower_rght_attribs = mid2bot; + upper_left_attribs = top2bot; + lower_left_attribs = upper_left_attribs; + } + + if (!(horizontal || no_upper_part)) { + int32_t delta; + + if (bi->num_upper_rows > 0) { + if (bi->start_scanline > xy._[top][1]) { + delta = bi->start_scanline - xy._[top][1]; + + multi_step_up(upper_left_attribs, delta, n); + multi_step_up(upper_rght_attribs, delta, n); + } + + draw_partial_triangle( + upper_left_attribs, + upper_rght_attribs, + true, + bi, + fbi + ); + + delta = xy._[mid][1] - bi->start_scanline; + } else { + delta = top2mid_delta; + } + + multi_step_up(upper_left_attribs, delta, n); + multi_step_up(upper_rght_attribs, delta, n); + } + + if (horizontal) { + draw_degenerate_horizontal( + xy_sorted, + top2mid, top2bot, mid2bot, + fbi + ); + } else { + if (bi->start_scanline > xy._[mid][1]) { + int32_t const delta = bi->start_scanline - xy._[mid][1]; + + multi_step_up(lower_left_attribs, delta, n); + multi_step_up(lower_rght_attribs, delta, n); + } + + draw_partial_triangle( + lower_left_attribs, + lower_rght_attribs, + false, + bi, + fbi + ); + } + free(mid2bot); free(top2bot); free(top2mid); + } + } + free(attribs[2]); free(attribs[1]); free(attribs[0]); +} + + diff --git a/generator/pamtris/triangle.h b/generator/pamtris/triangle.h new file mode 100644 index 00000000..e043e95c --- /dev/null +++ b/generator/pamtris/triangle.h @@ -0,0 +1,25 @@ +#ifndef TRIANGLE_H_INCLUDED +#define TRIANGLE_H_INCLUDED + +#include <stdint.h> + +#include "limits_pamtris.h" + +struct boundary_info; +struct framebuffer_info; + +typedef struct { + int32_t _[3][2]; +} Xy; + +typedef struct { + int32_t _[3][MAX_NUM_ATTRIBS + 2]; +} Attribs; + +void +draw_triangle(Xy const xy, + Attribs const attribs, + struct boundary_info * const bdi, + struct framebuffer_info * const fbi); + +#endif diff --git a/generator/pamtris/utils.c b/generator/pamtris/utils.c new file mode 100644 index 00000000..a6b6e7d4 --- /dev/null +++ b/generator/pamtris/utils.c @@ -0,0 +1,266 @@ +/*============================================================================= + utils.c +=============================================================================== + Utility functions +=============================================================================*/ + +#include <stdlib.h> +#include <stdint.h> +#include <math.h> + +#include "limits_pamtris.h" +#include "varying.h" + +#include "utils.h" + + + +void +prepare_for_interpolation(const varying * const begin, + const varying * const end, + varying * const out, + int32_t num_steps, + uint8_t const elements) { + + double inverse_num_steps; + unsigned int i; + + if (num_steps < 1) { + num_steps = 1; + } + + inverse_num_steps = 1.0 / num_steps; + + for (i = 0; i < elements; i++) { + out[i].v = begin[i].v; + out[i].s = (end[i].v - begin[i].v) * inverse_num_steps; + } +} + + + +varying +compute_varying_z(int32_t const input_z) { + + varying retval; + + retval.v = 1.0 / (1 + input_z - MIN_COORD); + retval.s = 0.0; + + return retval; +} + + + +void +multiply_varying_array_by_varying(varying * const vars, + varying const multiplier, + uint8_t const elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + vars[i].v *= multiplier.v; + vars[i].s = 0.0; + } +} + + +void +divide_varying_array_by_varying(varying * const vars, + varying const divisor, + uint8_t const elements) { + + double const inverse_divisor = 1.0 / divisor.v; + + unsigned int i; + + for (i = 0; i < elements; i++) { + vars[i].v *= inverse_divisor; + vars[i].s = 0.0; + } +} + + + +varying +inverse_varying(varying const var) { + + varying retval; + + retval.v = 1.0 / var.v; + retval.s = 0.0; + + return retval; +} + + + +varying +multiply_varyings(varying const a, + varying const b) { + + varying retval; + + retval.v = a.v * b.v; + retval.s = 0.0; + + return retval; +} + + + +void +step_up(varying * const vars, + uint8_t const elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + vars[i].v += vars[i].s; + } +} + + + +void +multi_step_up(varying * const vars, + int32_t const times, + uint8_t const elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + vars[i].v += times * vars[i].s; + } +} + + + +void +int32_to_varying_array(const int32_t * const in, + varying * const out, + uint8_t const elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + out[i].v = in[i]; + out[i].s = 0.0; + } +} + + + +/* static int64_t +abs64(int64_t x) +{ + + int64_t const nm = ~geq_mask64(x, 0); + + return (-x & nm) | (x & ~nm); +} */ + + + +int32_t +round_varying(varying const var) { + + return round(var.v); +} + + + +int64_t +geq_mask64(int64_t a, int64_t b) { + + uint64_t const diff = a - b; + + return -((~diff) >> 63); +} + + + +static void +swap(uint8_t * const a, + uint8_t * const b) { +/*---------------------------------------------------------------------------- + Swap the contents pointed to by a and b. +-----------------------------------------------------------------------------*/ + uint8_t const temp = *a; + + *a = *b; + *b = temp; +} + + + +void +sort3(uint8_t * const index_array, + const int32_t * const y_array, + const int32_t * const x_array) { +/*---------------------------------------------------------------------------- + Sort an index array of 3 elements. This function is used to sort vertices + with regard to relative row from top to bottom, but instead of sorting + an array of vertices with all their coordinates, we simply sort their + indices. Each element in the array pointed to by "index_array" should + contain one of the numbers 0, 1 or 2, and each one of them should be + different. "y_array" should point to an array containing the corresponding + Y coordinates (row) of each vertex and "x_array" should point to an array + containing the corresponding X coordinates (column) of each vertex. + + If the Y coordinates are all equal, the indices are sorted with regard to + relative X coordinate from left to right. If only the top two vertex have + the same Y coordinate, the array is sorted normally with regard to relative + Y coordinate, but the first two indices are then sorted with regard to + relative X coordinate. Finally, If only the bottom two vertex have the same + Y coordinate, the array is sorted normally with regard to relative Y + coordinate, but the last two indices are then sorted with regard to relative + X coordinate. +-----------------------------------------------------------------------------*/ + uint8_t * const ia = index_array; + + const int32_t * ya; + const int32_t * xa; + + ya = y_array; /* initial value */ + xa = x_array; /* initial value */ + + if (ya[0] == ya[1] && ya[1] == ya[2]) { + /* In case the vertices represent a degenerate horizontal triangle, we + sort according to relative X coordinate, as opposed to Y. + */ + ya = xa; + } + + if (ya[ia[2]] < ya[ia[1]]) { + swap(ia, ia + 2); + if (ya[ia[2]] < ya[ia[1]]) { + swap(ia + 1, ia + 2); + if (ya[ia[1]] < ya[ia[0]]) { + swap(ia, ia + 1); + } + } + } else if (ya[ia[1]] < ya[ia[0]]) { + swap(ia, ia + 1); + if (ya[ia[2]] < ya[ia[1]]) { + swap(ia + 1, ia + 2); + } + } + + if (ya == xa) { + return; + } + + if (ya[ia[0]] == ya[ia[1]]) { + if (xa[ia[1]] < xa[ia[0]]) { + swap(ia, ia + 1); + } + } else if (ya[ia[1]] == ya[ia[2]]) { + if (xa[ia[2]] < xa[ia[1]]) { + swap(ia + 1, ia + 2); + } + } +} + + diff --git a/generator/pamtris/utils.h b/generator/pamtris/utils.h new file mode 100644 index 00000000..bd9dcdbe --- /dev/null +++ b/generator/pamtris/utils.h @@ -0,0 +1,58 @@ +#ifndef UTIL_H_INCLUDED +#define UTIL_H_INCLUDED + +#include "varying.h" + +void +prepare_for_interpolation(const varying * const begin, + const varying * const end, + varying * const out, + int32_t num_steps, + uint8_t const elements); + +varying +compute_varying_z(int32_t const input_z); + +void +multiply_varying_array_by_varying(varying * const vars, + varying const divisor, + uint8_t const elements); + +void +divide_varying_array_by_varying(varying * const vars, + varying const divisor, + uint8_t const elements); + +varying +inverse_varying(varying const var); + +varying +multiply_varyings(varying const a, + varying const b); + +void +step_up(varying * const vars, + uint8_t const elements); + +void +multi_step_up(varying * const vars, + int32_t const times, + uint8_t const elements); + +void +int32_to_varying_array(const int32_t * const in, + varying * const out, + uint8_t const elements); + +int32_t +round_varying(varying const var); + +int64_t +geq_mask64(int64_t a, int64_t b); + +void +sort3(uint8_t * const index_array, + const int32_t * const y_array, + const int32_t * const x_array); + +#endif diff --git a/generator/pamtris/varying.h b/generator/pamtris/varying.h new file mode 100644 index 00000000..6605f02d --- /dev/null +++ b/generator/pamtris/varying.h @@ -0,0 +1,12 @@ +#ifndef VARYING_H_INCLUDED +#define VARYING_H_INCLUDED + +#include <stdint.h> + + +typedef struct { + double v; /* Value */ + double s; /* Step */ +} varying; + +#endif |