From e227331a6b5626e100705fcff3269fd8479ea988 Mon Sep 17 00:00:00 2001 From: giraffedata Date: Sat, 29 Sep 2018 03:18:57 +0000 Subject: Promote current Development release as Advanced git-svn-id: http://svn.code.sf.net/p/netpbm/code/advanced@3352 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- generator/pamtris/boundaries.c | 334 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 334 insertions(+) create mode 100644 generator/pamtris/boundaries.c (limited to 'generator/pamtris/boundaries.c') diff --git a/generator/pamtris/boundaries.c b/generator/pamtris/boundaries.c new file mode 100644 index 00000000..8ea28682 --- /dev/null +++ b/generator/pamtris/boundaries.c @@ -0,0 +1,334 @@ +/*============================================================================= + boundaries.c +=============================================================================== + 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. +=============================================================================*/ + +#include + +#include +#include + +#include "utils.h" +#include "fract.h" + + +#include "boundaries.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 * 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_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. +-----------------------------------------------------------------------------*/ + int16_t leftmost_x; + int16_t rightmost_x; + 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; + 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 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) { + if (top2mid_step.negative_flag) { + 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) { + 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) { + 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; + + 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_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 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]; +} + + -- cgit 1.4.1