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/utils.c | 256 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 256 insertions(+) create mode 100644 generator/pamtris/utils.c (limited to 'generator/pamtris/utils.c') diff --git a/generator/pamtris/utils.c b/generator/pamtris/utils.c new file mode 100644 index 00000000..09c9b4d0 --- /dev/null +++ b/generator/pamtris/utils.c @@ -0,0 +1,256 @@ +/*============================================================================= + utils.c +=============================================================================== + Utility functions +=============================================================================*/ + +#include +#include + +#include "fract.h" + +#include "utils.h" + + + +void +step_up(fract * const vars, + const fract * const steps, + uint8_t const element_ct, + int32_t const divisor) { +/*---------------------------------------------------------------------------- + Apply interpolation steps steps[] to a collection of fract variables vars[] + once. I.e. add each steps[i] to vars[i]. + + 'element_ct' is the number of elements in 'vars' and 'steps'. + + 'divisor' is the divisor used to interpret the fractions. + + It *is* safe to pass a 0 divisor to this function. +-----------------------------------------------------------------------------*/ + unsigned int i; + + for (i = 0; i < element_ct; ++i) { + /* To add the fraction steps[i] to the fraction vars[i]: add the + quotient of step steps[i] to the quotient of variable vars[i] and + the remainder of the step to the remainder of the variable. If this + makes the agumented remainder equal to or larger than the divisor, + increment the quotient of the variable if the step is positive or + decrement it if the step is negative, and subtract the divisor from + the remainder of the variable (in either case). + */ + + vars[i].q += steps[i].q; + vars[i].r += steps[i].r; + + { + uint32_t const negative_mask = -steps[i].negative_flag; + /* (-1 if the step is negative; 1 otherwise) */ + + uint32_t const overdiv_mask = + -(((uint32_t)~(vars[i].r - divisor)) >> 31); + /* = ~0 if var->r >= div; 0 otherwise. */ + + vars[i].q += (negative_mask | 1) & overdiv_mask; + vars[i].r -= divisor & overdiv_mask; + } + } +} + + + +void +multi_step_up(fract * const vars, + const fract * const steps, + uint8_t const elements, + int32_t const times, + int32_t const div) { +/*---------------------------------------------------------------------------- + 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. +-----------------------------------------------------------------------------*/ + unsigned int i; + + for (i = 0; i < elements; i++) { + uint32_t const 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 const r_q = vars[i].r / div; + int32_t const 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 * const begin, + const int32_t * const end, + fract * const out, + uint8_t const elements, + int32_t const div) { +/*---------------------------------------------------------------------------- + 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 +-----------------------------------------------------------------------------*/ + if (div > 1) { + unsigned int i; + + for (i = 0; i < elements; i++) { + int32_t const 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 const 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 * const in, + int32_t * const out, + uint8_t const elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + out[i] = in[i].q; + } +} + + + +void +int32_to_fract_array(const int32_t * const in, + fract * const out, + uint8_t const elements) { + + unsigned int i; + + for (i = 0; i < elements; i++) { + out[i].q = in[i]; + out[i].r = 0; + } +} + + + +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); + } + } +} + + -- cgit 1.4.1