diff options
-rw-r--r-- | doc/HISTORY | 3 | ||||
-rw-r--r-- | generator/pamtris/Makefile | 27 | ||||
-rw-r--r-- | generator/pamtris/boundaries.c | 287 | ||||
-rw-r--r-- | generator/pamtris/common.h | 437 | ||||
-rw-r--r-- | generator/pamtris/depend.mk | 36 | ||||
-rw-r--r-- | generator/pamtris/framebuffer.c | 252 | ||||
-rw-r--r-- | generator/pamtris/input.c | 626 | ||||
-rw-r--r-- | generator/pamtris/pamtris.c | 129 | ||||
-rw-r--r-- | generator/pamtris/triangle.c | 406 | ||||
-rw-r--r-- | generator/pamtris/utils.c | 178 |
10 files changed, 2381 insertions, 0 deletions
diff --git a/doc/HISTORY b/doc/HISTORY index 684459bc..48d24aae 100644 --- a/doc/HISTORY +++ b/doc/HISTORY @@ -6,6 +6,9 @@ CHANGE HISTORY not yet BJH Release 10.84.00 + Add pamtris. Thanks Lucas Brunno Luna + <lucaslunar32@hotmail.com>. + pbmtext: -wchar works with built-in fonts. pbmtext: improved -verbose information about BDF fonts: 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..04237e59 --- /dev/null +++ b/generator/pamtris/boundaries.c @@ -0,0 +1,287 @@ +#include <stdlib.h> + +#include "common.h" + + + +static fract +make_pos_fract(int32_t const quotient, + int32_t const remainder) { + + fract retval; + + retval.q = quotient; + retval.r = remainder; + retval.negative_flag = 0; + + return retval; +} + + + +void +init_boundary_buffer(boundary_info * bi, + int16_t height) { + MALLOCARRAY_NOFAIL(bi->buffer, height * 2 * sizeof(int16_t)); +} + + + +void +free_boundary_buffer(boundary_info * bi) { + free(bi->buffer); +} + + + +bool +gen_triangle_boundaries(int32_t xy[3][2], + boundary_info * bi, + int16_t width, + int16_t height) { + + int16_t leftmost_x = xy[0][0]; + int16_t rightmost_x = xy[0][0]; + int mid_is_to_the_left; + fract left_x; + fract right_x; + bool no_upper_part; + int32_t top2mid_delta; + int32_t top2bot_delta; + int32_t mid2bot_delta; + fract top2mid_step; + fract top2bot_step; + fract mid2bot_step; + fract* upper_left_step; + fract* lower_left_step; + fract* upper_right_step; + fract* lower_right_step; + int32_t upper_left_delta; + int32_t lower_left_delta; + int32_t upper_right_delta; + int32_t lower_right_delta; + fract* left_step[2]; + fract* right_step[2]; + int32_t left_delta[2]; + int32_t right_delta[2]; + int16_t* num_rows_ptr[2]; + int32_t y; + int32_t i = 0; + uint8_t k = 0; + + 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 topmost scanline or + completely below the bottom 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; + + left_x = make_pos_fract(xy[0][0], 0); + right_x = make_pos_fract(xy[0][0], 0); + + if (xy[0][1] == xy[1][1]) { + /* Triangle has only a lower part. */ + + mid_is_to_the_left = 0; + + right_x.q = xy[1][0]; + } else 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; + } + + no_upper_part = (xy[1][1] == xy[0][1]); + + top2mid_delta = xy[1][1] - xy[0][1] + !no_upper_part; + top2bot_delta = xy[2][1] - xy[0][1] + 1; + mid2bot_delta = xy[2][1] - xy[1][1] + no_upper_part; + + gen_steps(&xy[0][0], &xy[1][0], &top2mid_step, 1, top2mid_delta); + gen_steps(&xy[0][0], &xy[2][0], &top2bot_step, 1, top2bot_delta); + gen_steps(&xy[1][0], &xy[2][0], &mid2bot_step, 1, mid2bot_delta); + + if (mid_is_to_the_left == 2) { + if (top2bot_step.negative_flag == true) { + if (top2mid_step.negative_flag == true) { + if (top2mid_step.q == top2bot_step.q) { + mid_is_to_the_left = + top2mid_step.r * top2bot_delta > + top2bot_step.r * top2mid_delta; + } else { + mid_is_to_the_left = top2mid_step.q < top2bot_step.q; + } + } else { + mid_is_to_the_left = 0; + } + } else { + if (top2mid_step.negative_flag == false) { + if (top2mid_step.q == top2bot_step.q) { + mid_is_to_the_left = + top2mid_step.r * top2bot_delta < + top2bot_step.r * top2mid_delta; + } else { + mid_is_to_the_left = top2mid_step.q < top2bot_step.q; + } + } else { + mid_is_to_the_left = 1; + } + } + } + if (mid_is_to_the_left) { + upper_left_step = &top2mid_step; + lower_left_step = &mid2bot_step; + upper_right_step = &top2bot_step; + lower_right_step = upper_right_step; + + upper_left_delta = top2mid_delta; + lower_left_delta = mid2bot_delta; + upper_right_delta = top2bot_delta; + lower_right_delta = upper_right_delta; + } else { + upper_right_step = &top2mid_step; + lower_right_step = &mid2bot_step; + upper_left_step = &top2bot_step; + lower_left_step = upper_left_step; + + upper_right_delta = top2mid_delta; + lower_right_delta = mid2bot_delta; + upper_left_delta = top2bot_delta; + lower_left_delta = upper_left_delta; + } + + left_step[0] = upper_left_step; + left_step[1] = lower_left_step; + right_step[0] = upper_right_step; + right_step[1] = lower_right_step; + left_delta[0] = upper_left_delta; + left_delta[1] = lower_left_delta; + right_delta[0] = upper_right_delta; + right_delta[1] = lower_right_delta; + num_rows_ptr[0] = &bi->num_upper_rows; + num_rows_ptr[1] = &bi->num_lower_rows; + + y = xy[0][1]; + + i = 0; + k = 0; + + if (no_upper_part == true) { + k = 1; + + right_x.q = xy[1][0]; + } + + step_up(&left_x, left_step[k], 1, left_delta[k]); + step_up(&right_x, right_step[k], 1, right_delta[k]); + + while (k < 2) { + int32_t end = xy[k + 1][1] + k; + + if (y < 0) { + int32_t delta; + + if (end > 0) { + delta = -y; + } else { + delta = xy[k + 1][1] - y; + } + + y += delta; + + multi_step_up(&left_x, left_step[k], 1, delta, left_delta[k]); + multi_step_up(&right_x, right_step[k], 1, delta, right_delta[k]); + + if (y < 0) { + k++; + continue; + } + } else if(y >= height) { + return mid_is_to_the_left; + } + + if (end > height) { + end = height; + } + + while (y < end) { + if (left_x.q >= width || right_x.q < 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++] = left_x.q; + bi->buffer[i++] = right_x.q; + + (*(num_rows_ptr[k]))++; + } + + step_up(&left_x, left_step[k], 1, left_delta[k]); + step_up(&right_x, right_step[k], 1, right_delta[k]); + + y++; + } + k++; + } + return mid_is_to_the_left; +} + + + +void +get_triangle_boundaries(uint16_t row_index, + int32_t * left, + int32_t * right, + const boundary_info * bi) { + + uint32_t i = row_index << 1; + + *left = bi->buffer[i]; + *right = bi->buffer[i + 1]; +} + + diff --git a/generator/pamtris/common.h b/generator/pamtris/common.h new file mode 100644 index 00000000..eb9496fa --- /dev/null +++ b/generator/pamtris/common.h @@ -0,0 +1,437 @@ +#include <netpbm/pam.h> +#include <netpbm/shhopt.h> +#include <netpbm/mallocvar.h> + +#include <stdbool.h> +#include <stdint.h> + +#define MAX_MAXVAL 65535 +#define MAX_NUM_ATTRIBS 20 +#define MAX_Z ((1 << 30) - 1) + +/*---------------------------------------------------------------------------- + Struct definitions +----------------------------------------------------------------------------*/ + + +typedef struct { +/*---------------------------------------------------------------------------- + This struct and the functions that manipulate variables of this type act + as a substitute for floating point computations. Here, whenever we need a + value with a fractional component, we represent it using two parts: 1. An + integer part, called the "quotient", and 2. A fractional part, which is + itself composed of a "remainder" (or "numerator") and a "divisor" (or + "denominator"). The fract struct provides storage for the quotient and the + remainder, but the divisor must be given separately (because it often + happens in this program that whenever we are dealing with one variable of + type fract, we are dealing with more of them at the same time, and they + all have the same divisor). + + To be more precise, the way we actually use variables of this type works + like this: We read integer values through standard input; When drawing + triangles, we need need to calculate differences between some pairs of + these input values and divide such differences by some other integer, + which is the above mentioned divisor. That result is then used to compute + successive interpolations between the two values for which we had + originally calculated the difference, and is therefore called the + "interpolation step". The values between which we wish to take successive + interpolations are called the "initial value" and the "final value". The + interpolation procedure works like this: First, we transform the initial + value into a fract variable by equating the quotient of that variable to + the initial value and assigning 0 to its remainder. Then, we successivelly + apply the interpolation step to that variable through successive calls to + step_up and/or multi_step_up until the quotient of the variable equals the + final value. Each application of step_up or multi_step_up yields a + particular linear interpolation between the initial and final values. + + If and only if a particular fract variable represents an interpolation + step, the "negative_flag" field indicates whether the step is negative + (i. e. negative_flag == true) or not (negative_flag == false). This is + necessary in order to make sure that variables are "stepped up" in the + appropriate direction, so to speak, as the field which stores the + remainder in any fract variable, "r", is always equal to or above 0, and + the quotient of a step may be 0, so the actual sign of the step value is + not always discoverable through a simple examination of the sign of the + quotient. On the other hand, if the variable does not represent an + interpolation step, the negative_flag is meaningless. +-----------------------------------------------------------------------------*/ + int32_t q; /* Quotient */ + int32_t r: 31; /* Remainder */ + bool negative_flag: 1; +} fract; + + + +/* Each of the following structs has only one instance, which are created in + the main function. +*/ + +typedef struct { +/*---------------------------------------------------------------------------- + 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". + */ + 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; + + + +typedef struct { +/*---------------------------------------------------------------------------- + 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; + +typedef struct { +/*---------------------------------------------------------------------------- + Information necessary for the "process_next_command" function. It must be + initialized through "init_input_processor" and freed by + "free_input_processor". +-----------------------------------------------------------------------------*/ + char * buffer; + size_t length; + uint64_t number; +} input_info; + +/*---------------------------------------------------------------------------- + Utility functions +-----------------------------------------------------------------------------*/ + +/*---------------------------------------------------------------------------- + Generate the interpolation steps for a collection of initial and final + values. "begin" points to an array of initial values, "end" points to the + array of corresponding final values; each interpolation step is stored in + the appropriate position in the array pointed by "out"; "elements" indicates + the number of elements in each of the previously mentioned arrays and + "divisor" is the common value by which we want to divide the difference + between each element in the array pointed to by "end" and the corresponding + element in the array pointed to by "begin". After an execution of this + function, for each out[i], with 0 <= i < elements, the following will hold: + + 1. If divisor > 1: + out[i].q = (end[i] - begin[i]) / divisor + out[i].r = abs((end[i] - begin[i]) % divisor) + + 2. If divisor == 1 || divisor == 0: + out[i].q = end[i] - begin[i] + out[i].r = 0 +-----------------------------------------------------------------------------*/ +void +gen_steps(const int32_t * begin, + const int32_t * end, + fract * out, + uint8_t elements, + int32_t divisor); + +/*---------------------------------------------------------------------------- + Apply interpolation steps (see above) to a collection of fract + variables (also see above) once. This is done by adding the + quotient of each step to the quotient of the corresponding variable + and the remainder of that step to the remainder of the variable. If the + remainder of the variable becomes equal to or larger than the + divisor, we increment the quotient of the variable if the negetive_flag + of the step is false, or decrement it if the negetive_flag is true, and + subtract the divisor from the remainder of the variable (in both cases). + + It *is* safe to pass a 0 divisor to this function. +-----------------------------------------------------------------------------*/ +void +step_up(fract * vars, + const fract * steps, + uint8_t elements, + int32_t divisor); + +/*---------------------------------------------------------------------------- + Similar to step_up, but apply the interpolation step an arbitrary number + of times, instead of just once. + + It *is* also safe to pass a 0 divisor to this function. +-----------------------------------------------------------------------------*/ +void +multi_step_up(fract * vars, + const fract * steps, + uint8_t elements, + int32_t times, + int32_t divisor); + +void +fract_to_int32_array(const fract * in, + int32_t * out, + uint8_t elements); + +void +int32_to_fract_array(const int32_t * in, + fract * out, + uint8_t elements); + +/*---------------------------------------------------------------------------- + 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. +-----------------------------------------------------------------------------*/ +void +sort3(uint8_t * index_array, + const int32_t * y_array, + const int32_t * x_array); + +/*---------------------------------------------------------------------------- + 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. +-----------------------------------------------------------------------------*/ + +/*---------------------------------------------------------------------------- + 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. +-----------------------------------------------------------------------------*/ +int +set_tupletype(const char * str, + char tupletype[256]); + +int +init_framebuffer(framebuffer_info *); + +void +free_framebuffer(framebuffer_info *); + +void +print_framebuffer(framebuffer_info *); + +void +clear_framebuffer(bool clear_image_buffer, + bool clear_z_buffer, + framebuffer_info *); + +/*---------------------------------------------------------------------------- + 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. +-----------------------------------------------------------------------------*/ +int +realloc_image_buffer(int32_t new_maxval, + int32_t new_num_attribs, + framebuffer_info *); + +/*---------------------------------------------------------------------------- + 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. +-----------------------------------------------------------------------------*/ +void draw_span(uint32_t base, + uint16_t length, + fract * attribs_start, + const fract * attribs_steps, + int32_t divisor, + framebuffer_info *); + + +/*---------------------------------------------------------------------------- + Boundary buffer functions +------------------------------------------------------------------------------ + New triangles are drawn one scanline at a time, and for every such scanline + 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. +-----------------------------------------------------------------------------*/ + +void +init_boundary_buffer(boundary_info * , + int16_t height); + +void +free_boundary_buffer(boundary_info *); + +/*---------------------------------------------------------------------------- + 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_row is accordingly set to -1. The argument is a 3-element array + of pairs of int16_t's 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. +-----------------------------------------------------------------------------*/ + +bool +gen_triangle_boundaries(int32_t xy[3][2], + boundary_info *, + int16_t width, + int16_t height); + +/*---------------------------------------------------------------------------- + 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. +-----------------------------------------------------------------------------*/ +void +get_triangle_boundaries(uint16_t row_index, + int32_t * left, + int32_t * right, + const boundary_info *); + +/*---------------------------------------------------------------------------- + Triangle functions +-----------------------------------------------------------------------------*/ + +void +draw_triangle(int32_t xy[3][2], + int32_t attribs[3][MAX_NUM_ATTRIBS + 1], + boundary_info *, + framebuffer_info *); + +/*---------------------------------------------------------------------------- + Input handling functions +-----------------------------------------------------------------------------*/ + +void +init_input_processor(input_info *); + +void +free_input_processor(input_info *); + +/*---------------------------------------------------------------------------- + Doesn't necessarily process a command, just the next line of input, which + may be empty. Always returns 1, except when it cannot read any more lines of + input, an image buffer reallocation fails, or a "q" command is found in the + input -- in such cases it returns 0. +-----------------------------------------------------------------------------*/ +int +process_next_command(input_info *, + boundary_info *, + framebuffer_info *); diff --git a/generator/pamtris/depend.mk b/generator/pamtris/depend.mk new file mode 100644 index 00000000..3b6df8e2 --- /dev/null +++ b/generator/pamtris/depend.mk @@ -0,0 +1,36 @@ +triangle.o: triangle.c common.h importinc/netpbm/pam.h \ + importinc/netpbm/pm_config.h importinc/netpbm/pm.h \ + importinc/netpbm/pnm.h importinc/netpbm/ppm.h importinc/netpbm/pgm.h \ + importinc/netpbm/pbm.h importinc/netpbm/ppmcmap.h \ + importinc/netpbm/shhopt.h importinc/netpbm/mallocvar.h \ + importinc/netpbm/pm_config.h +framebuffer.o: framebuffer.c common.h importinc/netpbm/pam.h \ + importinc/netpbm/pm_config.h importinc/netpbm/pm.h \ + importinc/netpbm/pnm.h importinc/netpbm/ppm.h importinc/netpbm/pgm.h \ + importinc/netpbm/pbm.h importinc/netpbm/ppmcmap.h \ + importinc/netpbm/shhopt.h importinc/netpbm/mallocvar.h \ + importinc/netpbm/pm_config.h +boundaries.o: boundaries.c common.h importinc/netpbm/pam.h \ + importinc/netpbm/pm_config.h importinc/netpbm/pm.h \ + importinc/netpbm/pnm.h importinc/netpbm/ppm.h importinc/netpbm/pgm.h \ + importinc/netpbm/pbm.h importinc/netpbm/ppmcmap.h \ + importinc/netpbm/shhopt.h importinc/netpbm/mallocvar.h \ + importinc/netpbm/pm_config.h +pamtris.o: pamtris.c common.h importinc/netpbm/pam.h \ + importinc/netpbm/pm_config.h importinc/netpbm/pm.h \ + importinc/netpbm/pnm.h importinc/netpbm/ppm.h importinc/netpbm/pgm.h \ + importinc/netpbm/pbm.h importinc/netpbm/ppmcmap.h \ + importinc/netpbm/shhopt.h importinc/netpbm/mallocvar.h \ + importinc/netpbm/pm_config.h +input.o: input.c common.h importinc/netpbm/pam.h \ + importinc/netpbm/pm_config.h importinc/netpbm/pm.h \ + importinc/netpbm/pnm.h importinc/netpbm/ppm.h importinc/netpbm/pgm.h \ + importinc/netpbm/pbm.h importinc/netpbm/ppmcmap.h \ + importinc/netpbm/shhopt.h importinc/netpbm/mallocvar.h \ + importinc/netpbm/pm_config.h +utils.o: utils.c common.h importinc/netpbm/pam.h \ + importinc/netpbm/pm_config.h importinc/netpbm/pm.h \ + importinc/netpbm/pnm.h importinc/netpbm/ppm.h importinc/netpbm/pgm.h \ + importinc/netpbm/pbm.h importinc/netpbm/ppmcmap.h \ + importinc/netpbm/shhopt.h importinc/netpbm/mallocvar.h \ + importinc/netpbm/pm_config.h diff --git a/generator/pamtris/framebuffer.c b/generator/pamtris/framebuffer.c new file mode 100644 index 00000000..cbb1e4a8 --- /dev/null +++ b/generator/pamtris/framebuffer.c @@ -0,0 +1,252 @@ +#include <stdlib.h> +#include <string.h> + +#include "common.h" + + + +int +set_tupletype(const char * str, + char tupletype[256]) { + + if (str == NULL) { + memset(tupletype, 0, 256); + + return 1; + } else { + size_t len = strlen(str); + + 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 * fbi) { + + uint8_t num_planes = fbi->num_attribs + 1; + + uint32_t 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 * fbi) { + + free(fbi->img.buffer); + free(fbi->z.buffer); + + pnm_freepamrow(fbi->pamrow); +} + + + +int +realloc_image_buffer(int32_t new_maxval, + int32_t new_num_attribs, + framebuffer_info * fbi) { + + uint8_t num_planes = fbi->num_attribs + 1; + + pnm_freepamrow(fbi->pamrow); + fbi->pamrow = NULL; + + 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* 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 * fbi) { + + uint8_t num_planes = fbi->num_attribs + 1; + uint32_t i = 0; + uint32_t end = fbi->width * fbi->height; + + pnm_writepaminit(&fbi->outpam); + + while (i != end) { + int j; + for (j = 0; j < fbi->width; j++) { + uint32_t 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 clear_image_buffer, + bool clear_z_buffer, + framebuffer_info* 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 base, + uint16_t length, + fract * attribs_start, + const fract * attribs_steps, + int32_t div, + framebuffer_info * fbi) { + + uint8_t num_planes = fbi->num_attribs + 1; + + unsigned int i; + + /* Process each pixel in the span: */ + + for (i = 0; i < length; i++) { + int32_t z = MAX_Z - attribs_start[fbi->num_attribs].q; + uint32_t z_mask = -(~(z - fbi->z.buffer[base + i]) >> 31); + uint32_t n_z_mask = ~z_mask; + + uint32_t j = base + i; + uint32_t k = j * num_planes; + + 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 framebuffer; otherwise, the + framebuffer will be updated with the new values. + */ + fbi->z.buffer[j] = (fbi->z.buffer[j] & n_z_mask) | (z & z_mask); + + for (l = 0; l < fbi->num_attribs; l++) { + fbi->img.buffer[k + l] = + (fbi->img.buffer[k + l] & n_z_mask) | + (attribs_start[l].q & z_mask); + } + + fbi->img.buffer[k + fbi->num_attribs] = + (fbi->img.buffer[k + fbi->num_attribs] & n_z_mask) | + (fbi->maxval & z_mask); + + /* Compute the attribute values for the next pixel: */ + + step_up(attribs_start, attribs_steps, num_planes, div); + } +} + + diff --git a/generator/pamtris/input.c b/generator/pamtris/input.c new file mode 100644 index 00000000..0daa623e --- /dev/null +++ b/generator/pamtris/input.c @@ -0,0 +1,626 @@ +#include <stdlib.h> +#include <stdio.h> +#include <ctype.h> + +#include "common.h" + +#define MAX_COORD 32767 +#define MIN_COORD -MAX_COORD + +#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" + +#define WARNING_EXCESS_ARGS "warning: ignoring excess arguments: line %lu." +#define SYNTAX_ERROR "syntax error: line %lu." + +typedef struct { + int32_t v_xy[3][2]; + /* X- and Y-coordinates of the vertices for the current triangle. + int32_t v_attribs[3][MAX_NUM_ATTRIBS + 1]; // Vertex attributes for + the current triangle. Includes the Z-coordinates. + */ + int32_t v_attribs[3][MAX_NUM_ATTRIBS + 1]; + /* 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 +clear_attribs(state_info * si, + int32_t maxval, + int16_t num_attribs) { + + unsigned int i; + + for (i = 0; i < num_attribs; i++) { + si->curr_attribs[i] = maxval; + } +} + + + +void +init_input_processor(input_info * ii) { + + MALLOCARRAY_NOFAIL(ii->buffer, 128); + + ii->length = 128; + ii->number = 1; +} + + + +void +free_input_processor(input_info * ii) { + free(ii->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 +next_token(char * string_ptr) { + + token retval; + + while (*string_ptr != '\0' && isspace(*string_ptr)) { + string_ptr++; + } + + retval.begin = string_ptr; + + while (*string_ptr != '\0' && !isspace(*string_ptr)) + { + string_ptr++; + } + + retval.end = string_ptr; + + return retval; +} + + + +static bool +validate_string(const char * target, + const char * src_begin, + const char * src_end) { + + uint8_t chars_matched = 0; + + while (src_begin != src_end && target[chars_matched] != '\0') { + if (*src_begin == target[chars_matched]) { + chars_matched++; + } else { + break; + } + + src_begin++; + } + + if (!isspace(*src_begin) && *src_begin != '\0') { + return false; + } + + return true; +} + + + +static void +init_state(state_info * si) { + + si->next = 0; + si->draw = false; + si->mode = DRAW_MODE_TRIANGLES; +} + + + +static void +make_lowercase(token t) { + + while (t.begin != t.end) { + *t.begin = tolower(*t.begin); + + t.begin++; + } +} + + + +static void +remove_comments(char * str) { + + while (*str != '\0') { + if (*str == '#') { + *str = '\0'; + + return; + } + + str++; + } +} + + + +int +process_next_command(input_info * line, + boundary_info * bi, + framebuffer_info * fbi) { + + static state_info state; + + token nt; + + long int i_args[MAX_NUM_ATTRIBS]; + /* For storing potential integer arguments. */ + char * strtol_end = NULL; + /* To compare against nt.end when checking for errors with strtol */ + bool unrecognized_cmd = false; + /* To print out an error message in case an unrecognized command was + given. + */ + bool unrecognized_arg = false; + /* To print out an error message in case an unrecognized argument was + given. + */ + bool break_out = false; + /* To break out of the below switch statement when an invalid argument + is found. + */ + bool ok = false; + /* Indicates whether the input line was OK so that we can print out a + warning in case of excess arguments. + */ + + if (state.initialized == false) { + init_state(&state); + clear_attribs(&state, fbi->maxval, fbi->num_attribs); + + state.initialized = true; + } + + if (getline(&line->buffer, &line->length, stdin) == -1) { + return 0; + } + + remove_comments(line->buffer); + + nt = next_token(line->buffer); + + make_lowercase(nt); + + switch (*nt.begin) { + case 'm': + if (validate_string(CMD_SET_MODE, nt.begin, nt.end) == false) { + unrecognized_cmd = true; + + break; + } + + nt = next_token(nt.end); + + if (*nt.begin == '\0') { + pm_errormsg(SYNTAX_ERROR, line->number); + + break; + } + + make_lowercase(nt); + + switch(*nt.begin) { + case 't': + if (validate_string(ARG_TRIANGLES, nt.begin, nt.end) == false) { + unrecognized_arg = true; + + break; + } + + state.mode = DRAW_MODE_TRIANGLES; + state.draw = false; + state.next = 0; + + ok = true; + + break; + case 's': + if (validate_string(ARG_STRIP, nt.begin, nt.end) == false) { + unrecognized_arg = true; + + break; + } + + state.mode = DRAW_MODE_STRIP; + state.draw = false; + state.next = 0; + + ok = true; + + break; + case 'f': + if (validate_string(ARG_FAN, nt.begin, nt.end) == false) { + unrecognized_arg = true; + + break; + } + + state.mode = DRAW_MODE_FAN; + state.draw = false; + state.next = 0; + + ok = true; + + break; + default: + unrecognized_arg = true; + } + + if (unrecognized_arg == true) { + pm_errormsg("error: unrecognized drawing mode (\"%c\"): " + "line %lu.", *nt.begin, line->number); + } + + break; + case 'a': { + uint8_t i; + if (validate_string(CMD_SET_ATTRIBS, nt.begin, nt.end) == false) { + unrecognized_cmd = true; + + break; + } + + for (i = 0; i < fbi->num_attribs; i++) { + nt = next_token(nt.end); + + i_args[i] = strtol(nt.begin, &strtol_end, 10); + + if (*nt.begin == '\0' || strtol_end != nt.end) { + pm_errormsg(SYNTAX_ERROR, line->number); + + break_out = true; + + break; + } + + if (i_args[i] < 0 || i_args[i] > fbi->maxval) { + pm_errormsg("error: argument(s) out of bounds: line %lu.", + line->number); + + break_out = true; + + break; + } + } + + if (break_out == true) + { + break; + } + + for (i = 0; i < fbi->num_attribs; i++) { + state.curr_attribs[i] = i_args[i]; + } + + ok = true; + + } break; + case 'v': { + uint8_t i; + + if (validate_string(CMD_VERTEX, nt.begin, nt.end) == false) { + unrecognized_cmd = true; + + break; + } + + for (i = 0; i < 3; i++) { + nt = next_token(nt.end); + + i_args[i] = strtol(nt.begin, &strtol_end, 10); + + if (*nt.begin == '\0' || strtol_end != nt.end) { + pm_errormsg(SYNTAX_ERROR, line->number); + + break_out = true; + + break; + } + + if (i < 2) { + if (i_args[i] < MIN_COORD || i_args[i] > MAX_COORD) { + pm_errormsg( + "error: coordinates out of bounds: line %lu.", + line->number); + + break_out = true; + + break; + } + } else { + if (i_args[i] < 0 || i_args[i] > MAX_Z) { + pm_errormsg( + "error: Z component out of bounds: line %lu.", + line->number); + + break_out = true; + + break; + } + } + } + + if (break_out == true) + { + break; + } + + for (i = 0; i < fbi->num_attribs; i++) { + state.v_attribs[state.next][i] = state.curr_attribs[i]; + } + + state.v_attribs[state.next][fbi->num_attribs] = i_args[2]; + + state.v_xy[state.next][0] = i_args[0]; + state.v_xy[state.next][1] = i_args[1]; + + state.next++; + + if (state.draw == false) { + if (state.next == 3) { + state.draw = true; + } + } + + if (state.draw) { + draw_triangle(state.v_xy, state.v_attribs, bi, fbi); + } + + if (state.next == 3) { + switch(state.mode) { + case DRAW_MODE_FAN: + state.next = 1; + break; + case DRAW_MODE_TRIANGLES: + state.draw = false; + case DRAW_MODE_STRIP: + default: + state.next = 0; + } + } + + ok = true; + + } break; + case 'p': + if (validate_string(CMD_PRINT, nt.begin, nt.end) == false) { + unrecognized_cmd = true; + + break; + } + case '!': + if (*nt.begin == '!') { + if (nt.end - nt.begin > 1) { + unrecognized_cmd = true; + + break; + } + } + + print_framebuffer(fbi); + + ok = true; + + break; + case 'c': + if (validate_string(CMD_CLEAR, nt.begin, nt.end) == false) { + unrecognized_cmd = true; + + break; + } + case '*': + if (*nt.begin == '*') { + if(nt.end - nt.begin > 1) + { + unrecognized_cmd = true; + + break; + } + } + + nt = next_token(nt.end); + + if (*nt.begin != '\0') { + make_lowercase(nt); + + switch(*nt.begin) { + case 'i': + if (validate_string("image", nt.begin, nt.end) == false) { + unrecognized_arg = true; + + break; + } + + clear_framebuffer(true, false, fbi); + + break; + case 'd': + if (validate_string("depth", nt.begin, nt.end) == false) { + unrecognized_arg = true; + + break; + } + case 'z': + if (*nt.begin == 'z') { + if (nt.end - nt.begin > 1) { + unrecognized_arg = true; + + break; + } + } + + clear_framebuffer(false, true, fbi); + + break; + default: + unrecognized_arg = true; + } + + if (unrecognized_arg == true) { + pm_errormsg("error: unrecognized argument: line %lu.", + line->number); + + break; + } + } else { + clear_framebuffer(true, true, fbi); + } + + ok = true; + + break; + case 'r': { + uint8_t i; + + if (validate_string(CMD_RESET, nt.begin, nt.end) == false) { + unrecognized_cmd = true; + + break; + } + + for (i = 0; i < 2; i++) { + nt = next_token(nt.end); + + i_args[i] = strtol(nt.begin, &strtol_end, 10); + + if (*nt.begin == '\0' || nt.end != strtol_end) { + pm_errormsg(SYNTAX_ERROR, line->number); + + break_out = true; + + break; + } + } + + if (break_out == true) { + break; + } + + if (i_args[0] < 1 || i_args[0] > MAX_MAXVAL) { + pm_errormsg("error: invalid new maxval: line %lu.", + line->number); + + break; + } + + if (i_args[1] < 1 || i_args[1] > MAX_NUM_ATTRIBS) { + pm_errormsg("error: invalid new number of generic vertex " + "attributes: line %lu.", line->number); + + break; + } + + nt = next_token(nt.end); + + if (*nt.begin != '\0') { + if (!set_tupletype(nt.begin, fbi->outpam.tuple_type)) { + pm_message("warning: could not set new tuple type; " + "using a null string: line %lu.", + line->number); + + set_tupletype(NULL, fbi->outpam.tuple_type); + } + } else { + set_tupletype(NULL, fbi->outpam.tuple_type); + } + + if (!realloc_image_buffer(i_args[0], i_args[1], fbi)) { + pm_errormsg + ( + "fatal error upon reading line %lu: " + "could not reallocate image buffer -- " + "terminating pamtris.", + line->number + ); + + return 0; + } + + state.next = 0; + state.draw = false; + + clear_attribs(&state, fbi->maxval, fbi->num_attribs); + + } break; + case 'q': + if (validate_string(CMD_QUIT, nt.begin, nt.end) == false) { + unrecognized_cmd = true; + + break; + } + + return 0; + case '\0': + break; + default: + unrecognized_cmd = true; + } + + { + char next = *next_token(nt.end).begin; + + if (unrecognized_cmd == true) { + pm_errormsg("error: unrecognized command: line %lu.", + line->number); + } + else if (ok == true && next != '\0') { + pm_message(WARNING_EXCESS_ARGS, line->number); + } + } + line->number++; + + return 1; +} + + diff --git a/generator/pamtris/pamtris.c b/generator/pamtris/pamtris.c new file mode 100644 index 00000000..2ef57891 --- /dev/null +++ b/generator/pamtris/pamtris.c @@ -0,0 +1,129 @@ +#include <stdlib.h> + +#include "common.h" + +#define MAX_METRICS 8192 + + + +static int +parse_command_line ( + int argv_idx, + int * argc_ptr, + const char ** argv, + int32_t * width, + int32_t * height, + int32_t * maxval, + int32_t * num_attribs, + char tupletype[256]) { + + optEntry * option_def; + optStruct3 opt; + /* Instructions to pm_optParseOptions3 on how to parse our options */ + unsigned int option_def_index; + + char * tupletype_ptr; + + unsigned int width_spec, height_spec, maxval_spec, attribs_spec; + unsigned int tupletype_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, "maxval", OPT_INT, maxval, &maxval_spec, 0); + OPTENT3(0, "num_attribs", OPT_INT, num_attribs, &attribs_spec, 0); + OPTENT3(0, "tupletype", OPT_STRING, &tupletype_ptr, &tupletype_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) { + pm_errormsg( + "you must at least specify -width, -height and -num_attribs."); + + 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 > MAX_MAXVAL) { + pm_errormsg("invalid maxval."); + + return 0; + } + } else { + *maxval = 255; + } + + if (*num_attribs < 1 || *num_attribs > MAX_NUM_ATTRIBS) { + pm_errormsg("invalid number of generic attributes per vertex."); + + return 0; + } + + if (tupletype_spec) { + if (!set_tupletype(tupletype_ptr, tupletype)) { + pm_errormsg("warning: invalid tuple type; using the null string."); + + set_tupletype(NULL, tupletype); + } + } + + return 1; +} + + + +int +main(int argc, const char ** argv) { + + framebuffer_info fbi; + boundary_info bi; + input_info ii; + + pm_proginit(&argc, (const char**)argv); + + set_tupletype(NULL, fbi.outpam.tuple_type); + + if (!parse_command_line(1, &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); + + init_input_processor(&ii); + + while (process_next_command(&ii, &bi, &fbi)); + + free_input_processor(&ii); + 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..570cff5f --- /dev/null +++ b/generator/pamtris/triangle.c @@ -0,0 +1,406 @@ +#include <stdlib.h> +#include <string.h> + +#include "common.h" + + + +static void +draw_partial_triangle( + const fract * left_attribs_input, + const fract * left_attribs_steps, + const fract * right_attribs_input, + const fract * right_attribs_steps, + int32_t left_div, + int32_t right_div, + bool upper_part, + const boundary_info * bi, + framebuffer_info * fbi) { + + uint8_t num_planes = fbi->num_attribs + 1; + + fract * left_attribs; + fract * right_attribs; + + int32_t first_row_index; + int32_t last_row_index; + + MALLOCARRAY_NOFAIL(left_attribs, num_planes); + MALLOCARRAY_NOFAIL(right_attribs, num_planes); + + memcpy(left_attribs, left_attribs_input, num_planes * sizeof(fract)); + memcpy(right_attribs, right_attribs_input, num_planes * sizeof(fract)); + + 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 row_delta = last_row_index - first_row_index; + int32_t row = first_row_index; + + int32_t left_boundary; + int32_t right_boundary; + + while (row <= last_row_index) { + get_triangle_boundaries(row, &left_boundary, &right_boundary, bi); + { + int32_t column_delta = right_boundary - left_boundary; + int32_t start_column = left_boundary; + int32_t span_length = column_delta; + + fract * attribs_start; + int32_t * attribs_begin; + int32_t * attribs_end; + fract * attribs_steps; + + MALLOCARRAY(attribs_start, num_planes); + MALLOCARRAY(attribs_begin, num_planes); + MALLOCARRAY(attribs_end, num_planes); + MALLOCARRAY(attribs_steps, num_planes); + + fract_to_int32_array(left_attribs, attribs_begin, num_planes); + fract_to_int32_array(right_attribs, attribs_end, num_planes); + + int32_to_fract_array(attribs_begin, attribs_start, num_planes); + + gen_steps(attribs_begin, attribs_end, attribs_steps, + num_planes, column_delta); + + if (left_boundary < 0) { + start_column = 0; + + span_length += left_boundary; + + multi_step_up(attribs_start, attribs_steps, num_planes, + -left_boundary, column_delta); + } + + if (right_boundary >= fbi->width) { + span_length -= right_boundary - fbi->width; + } else { + span_length++; + } + + draw_span( + ((bi->start_scanline + row) * fbi->width) + start_column, + span_length, attribs_start, attribs_steps, column_delta, + fbi); + + if (row_delta > 0) { + step_up(left_attribs, left_attribs_steps, num_planes, + left_div); + step_up(right_attribs, right_attribs_steps, num_planes, + right_div); + } + row++; + free(attribs_steps); + free(attribs_end); + free(attribs_begin); + free(attribs_start); + } + } + } + free(right_attribs); + free(left_attribs); +} + + + +static void +draw_degenerate_horizontal(int32_t xy[3][2], + fract * attribs_left, + fract * attribs_mid, + const fract * top2mid_steps, + const fract * top2bot_steps, + const fract * mid2bot_steps, + int32_t top2mid_delta, + int32_t top2bot_delta, + int32_t mid2bot_delta, + framebuffer_info* fbi) { + + uint8_t num_planes = fbi->num_attribs + 1; + + fract * attribs_left_bkup; + + MALLOCARRAY_NOFAIL(attribs_left_bkup, num_planes); + + memcpy(attribs_left_bkup, attribs_left, num_planes * sizeof(fract)); + + { + int16_t y = xy[0][1]; + + int16_t x[3]; + int16_t x_start[3]; + fract * attribs[3]; + const fract * steps[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] = attribs_left; + attribs[1] = attribs_left_bkup; + attribs[2] = attribs_mid; + + steps[0] = top2bot_steps; + steps[1] = top2mid_steps; + steps[2] = mid2bot_steps; + + 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++) { + int32_t column_delta = span_length[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], steps[i], num_planes, -x_start[i], + column_delta); + + 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], steps[i], column_delta, fbi); + } + } + free(attribs_left_bkup); +} + + + +void +draw_triangle(int32_t xy_input[3][2], + int32_t attribs_input[3][MAX_NUM_ATTRIBS + 1], + boundary_info * bi, + framebuffer_info * fbi) { + + uint8_t num_planes = fbi->num_attribs + 1; + + int32_t xy[3][2]; + int32_t * attribs[3]; + unsigned int i; + uint8_t index_array[3]; + int32_t y_array[3]; + int32_t x_array[3]; + + MALLOCARRAY_NOFAIL(attribs[0], num_planes); + MALLOCARRAY_NOFAIL(attribs[1], num_planes); + MALLOCARRAY_NOFAIL(attribs[2], num_planes); + + memcpy(xy, xy_input, sizeof(xy)); + + for (i = 0; i < 3; i++) { + memcpy(attribs[i], attribs_input[i], num_planes * sizeof(int32_t)); + } + + /* 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 top = index_array[0]; + uint8_t mid = index_array[1]; + uint8_t bot = index_array[2]; + + bool mid_is_to_the_left; + + int32_t xy_sorted[3][2]; + + 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 completely out of the bounds of the framebuffer. */ + + return; + } else { + bool no_upper_part = (xy_sorted[1][1] == xy_sorted[0][1]); + + bool horizontal = (xy[0][1] == xy[1][1] && xy[1][1] == xy[2][1]); + /* We are dealing with a degenerate horizontal triangle */ + + uint8_t 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]; + + fract * top2mid_steps; + fract * top2bot_steps; + fract * mid2bot_steps; + + fract * upper_left_attribs_steps; + fract * lower_left_attribs_steps; + fract * upper_right_attribs_steps; + fract * lower_right_attribs_steps; + + int32_t upper_left_delta; + int32_t lower_left_delta; + int32_t upper_right_delta; + int32_t lower_right_delta; + + fract * left_attribs; + fract * right_attribs; + + MALLOCARRAY_NOFAIL(top2mid_steps, num_planes); + MALLOCARRAY_NOFAIL(top2bot_steps, num_planes); + MALLOCARRAY_NOFAIL(mid2bot_steps, num_planes); + MALLOCARRAY_NOFAIL(left_attribs, num_planes); + MALLOCARRAY_NOFAIL(right_attribs, num_planes); + + if (horizontal == false) { + top2mid_delta += !no_upper_part; + top2bot_delta += 1; + mid2bot_delta += no_upper_part; + } + + gen_steps(attribs[top], attribs[mid], top2mid_steps, num_planes, + top2mid_delta); + gen_steps(attribs[top], attribs[bot], top2bot_steps, num_planes, + top2bot_delta); + gen_steps(attribs[mid], attribs[bot], mid2bot_steps, num_planes, + mid2bot_delta); + + int32_to_fract_array(attribs[top], left_attribs, num_planes); + int32_to_fract_array(attribs[top], right_attribs, num_planes); + + if (mid_is_to_the_left == true) { + upper_left_attribs_steps = top2mid_steps; + lower_left_attribs_steps = mid2bot_steps; + upper_right_attribs_steps = top2bot_steps; + lower_right_attribs_steps = upper_right_attribs_steps; + + upper_left_delta = top2mid_delta; + lower_left_delta = mid2bot_delta; + upper_right_delta = top2bot_delta; + lower_right_delta = upper_right_delta; + } else { + upper_right_attribs_steps = top2mid_steps; + lower_right_attribs_steps = mid2bot_steps; + upper_left_attribs_steps = top2bot_steps; + lower_left_attribs_steps = upper_left_attribs_steps; + + upper_right_delta = top2mid_delta; + lower_right_delta = mid2bot_delta; + upper_left_delta = top2bot_delta; + lower_left_delta = upper_left_delta; + } + + if (no_upper_part) { + int32_to_fract_array(attribs[mid], right_attribs, num_planes); + + if (horizontal) { + draw_degenerate_horizontal( + xy_sorted, + left_attribs, right_attribs, + top2mid_steps, top2bot_steps, mid2bot_steps, + top2mid_delta, top2bot_delta, mid2bot_delta, + fbi + ); + + return; + } + + step_up(left_attribs, lower_left_attribs_steps, num_planes, + lower_left_delta); + step_up(right_attribs, lower_right_attribs_steps, num_planes, + lower_right_delta); + } else { + int32_t delta; + + step_up(left_attribs, upper_left_attribs_steps, num_planes, + upper_left_delta); + step_up(right_attribs, upper_right_attribs_steps, num_planes, + upper_right_delta); + + if (bi->num_upper_rows > 0) { + + if (bi->start_scanline > xy[top][1]) { + delta = bi->start_scanline - xy[top][1]; + + multi_step_up(left_attribs, upper_left_attribs_steps, + num_planes, delta, upper_left_delta); + multi_step_up(right_attribs, upper_right_attribs_steps, + num_planes, delta, upper_right_delta); + } + + draw_partial_triangle( + left_attribs, upper_left_attribs_steps, + right_attribs, upper_right_attribs_steps, + upper_left_delta, upper_right_delta, + true, + bi, + fbi + ); + + delta = xy[mid][1] - bi->start_scanline; + } else { + delta = top2mid_delta; + } + + multi_step_up(left_attribs, upper_left_attribs_steps, + num_planes, delta, upper_left_delta); + multi_step_up(right_attribs, upper_right_attribs_steps, + num_planes, delta, upper_right_delta); + } + + if (bi->start_scanline > xy[mid][1]) { + int32_t delta = bi->start_scanline - xy[mid][1]; + + multi_step_up(left_attribs, lower_left_attribs_steps, + num_planes, delta, lower_left_delta); + multi_step_up(right_attribs, lower_right_attribs_steps, + num_planes, delta, lower_right_delta); + } + + draw_partial_triangle( + left_attribs, lower_left_attribs_steps, + right_attribs, lower_right_attribs_steps, + lower_left_delta, lower_right_delta, + false, + bi, + fbi + ); + free(right_attribs); free(left_attribs); + free(mid2bot_steps); free(top2bot_steps); free(top2mid_steps); + } + } + free(attribs[2]); free(attribs[1]); free(attribs[0]); +} + + diff --git a/generator/pamtris/utils.c b/generator/pamtris/utils.c new file mode 100644 index 00000000..550cc41d --- /dev/null +++ b/generator/pamtris/utils.c @@ -0,0 +1,178 @@ +#include <stdlib.h> + +#include "common.h" + +void +step_up(fract * vars, + const fract * steps, + uint8_t elements, + int32_t div) { + + unsigned int i; + + for (i = 0; i < elements; ++i) { + uint32_t negative_mask = -steps[i].negative_flag; + vars[i].q += steps[i].q; + vars[i].r += steps[i].r; + + { + uint32_t overdiv_mask = -(((uint32_t)~(vars[i].r - div)) >> 31); + /* = ~0 if var->r >= div; 0 otherwise. */ + + vars[i].q += (negative_mask | 1) & overdiv_mask; + /* = (-1 if the step is negative; 1 otherwise) &'ed with + overdiv_mask. vars[i].r -= div & overdiv_mask; + */ + } + } +} + + + +void +multi_step_up(fract * vars, + const fract * steps, + uint8_t elements, + int32_t times, + int32_t div) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + uint32_t negative_mask = -steps[i].negative_flag; + + vars[i].q += times * steps[i].q; + vars[i].r += times * steps[i].r; + + if(vars[i].r >= div && div != 0) { + int32_t r_q = vars[i].r / div; + int32_t r_r = vars[i].r % div; + + vars[i].q += (-r_q & negative_mask) | (r_q & ~negative_mask); + /* = -r_q if the step is negative; r_q, otherwise. */ + vars[i].r = r_r; + } + } +} + + + +void +gen_steps(const int32_t * begin, + const int32_t * end, + fract * out, uint8_t elements, int32_t div) { + + if (div > 1) { + unsigned int i; + + for (i = 0; i < elements; i++) { + int32_t delta = end[i] - begin[i]; + + out[i].q = delta / div; + out[i].r = abs(delta % div); + out[i].negative_flag = ((uint32_t)delta) >> 31; + } + } else { + unsigned int i; + + for (i = 0; i < elements; i++) { + int32_t delta = end[i] - begin[i]; + + out[i].q = delta; + out[i].r = 0; + out[i].negative_flag = ((uint32_t)delta) >> 31; + } + } +} + + + +void +fract_to_int32_array(const fract * in, + int32_t * out, + uint8_t elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + out[i] = in[i].q; + } +} + + + +void +int32_to_fract_array(const int32_t * in, + fract * out, + uint8_t elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + out[i].q = in[i]; + out[i].r = 0; + } +} + + + +static void +swap(uint8_t * a, + uint8_t * b) { +/*---------------------------------------------------------------------------- + Swap the contents pointed to by a and b. +-----------------------------------------------------------------------------*/ + uint8_t temp = *a; + *a = *b; + *b = temp; +} + + + +void +sort3(uint8_t * index_array, + const int32_t * y_array, + const int32_t * x_array) { + + uint8_t * ia = index_array; + const int32_t * ya = y_array; + const int32_t * xa = x_array; + + 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); + } + } +} + + |