summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJohnathan Roatch2020-12-01 21:32:37 -0500
committerJohnathan Roatch2020-12-01 21:32:37 -0500
commit10c39268701b9842e8d03c32d22308276316ba04 (patch)
treeb89902e2098d97e5ce214ef88594d7b151eae6e6
parent91bcf91e055835de363e862c7babfad3841cec53 (diff)
downloadjrrtilevq-10c39268701b9842e8d03c32d22308276316ba04.tar.gz
jrrtilevq-10c39268701b9842e8d03c32d22308276316ba04.zip
Compacted empty tile and matrix spots to skip over faster.
-rw-r--r--jrrtilevq.h173
1 files changed, 57 insertions, 116 deletions
diff --git a/jrrtilevq.h b/jrrtilevq.h
index a385560..af100da 100644
--- a/jrrtilevq.h
+++ b/jrrtilevq.h
@@ -113,19 +113,6 @@ static double jrrtilevq_float_from_u64(uint64_t value)
return fresult - 1.0;
}
-/*
-// count trailing zeros. For the inverse of "1 << x"
-static int jrrtilevq_ctz(uint64_t x)
-{
- if (!x)
- return sizeof(uint64_t)*8;
- // TODO: find a way to detect and use "return __builtin_ctz(x);"
- int t = 0;
- while ((x & (1<<t)) == 0)
- t++;
- return t;
-}*/
-
// throughout the program a 3 bit transform number is passed around
// this is what that transform does. The order between swap and the flips
// is important, because they form the basis for 90°/270° rotaions
@@ -209,42 +196,6 @@ static void jrrtilevq_inv_distance_matrix_coords(uint32_t* x_out, uint32_t* y_ou
*y_out = y;
}
-
-/*int jrrtilevq_pad_image(uint8_t** image, unsigned* width, unsigned* height, unsigned tile_width, unsigned tile_height, int grid_offset_x, int grid_offset_y)
-{
- assert(image && *image && width && *width && height && *height && tile_width && tile_height);
-
- uint8_t* old_image = *image;
- unsigned old_width = *width;
- unsigned old_height = *height;
- unsigned left_pad = grid_offset_x % tile_width;
- unsigned top_pad = grid_offset_y % tile_height;
- unsigned new_width = (((old_width + left_pad) + tile_width - 1) / tile_width) * tile_width;
- unsigned new_height = (((old_height + top_pad) + tile_height - 1) / tile_height) * tile_height;
-
- if ((old_height * old_width) == (new_height * new_width))
- return 0;
-
- uint8_t* new_image = JRRTILEVQ_MALLOC(old_height * old_width * 4);
- if (!new_image)
- return 1;
-
- uint8_t* src = old_image;
- uint8_t* src_end = old_image + (old_height * old_width * 4);
- uint8_t* dst = new_image + (((top_pad * new_width) + left_pad) * 4);
- while (src < src_end) {
- memcpy(dst, src, old_width * 4);
- dst += new_width * 4;
- src += old_width * 4;
- }
-
- JRRTILEVQ_FREE(old_image);
- *image = new_image;
- *width = new_width;
- *height = new_height;
- return 0;
-}*/
-
/*static void jrrtilevq_flip_tile(uint8_t *tile, int w, int h, int t) {
assert(tile && w && h);
@@ -264,54 +215,6 @@ static void jrrtilevq_inv_distance_matrix_coords(uint32_t* x_out, uint32_t* y_ou
}
}*/
-/* static int jrrtilevq_find_tile_normalization(const uint8_t *tile, int w, int h, int allowed_flips)
-{
- assert(tile && (w > 0) && (h > 0));
-
- // Identity the only option, nothing to do then.
- if (allowed_transforms <= 1)
- return 0;
-
- // allowed_flips are in the perspective of the tilemap entries
- // which means 1/4 turn rotaions must be reversed in the tile data
- // in order to counter the rotaions applied from the tilemap.
- // Also always have identity be an option.
- int canidate_transforms = ((allowed_flips & 0x40) >> 1) | ((allowed_flips & 0x20) << 1) | (allowed_flips & 0x9f) | 1;
-
- // can't transpose x/y on non square tiles
- if (w != h)
- canidate_transforms &= 0x0f;
-
- // for each pixel, look at all transforms and choose only
- // the ones that have the smallest index value.
- int x, y, i, t, p;
- for (y = 0; y < h; ++y) {
- for (x = 0; x < w; ++x) {
- int min_index = INT_MAX;
- p = 0;
- for (t = 0; t < 8; ++t) {
- if (canidate_transforms & (1<<t)) {
- i = jrrtilevq_tile_coords(x, y, w, h, t);
- if (tile[i] < min_index)
- min_index = tile[i];
- ++p;
- }
- }
- if (p <= 1)
- return jrrtilevq_ctz(canidate_transforms);
- for (t = 0; t < 8; ++t) {
- if (canidate_transforms & (1<<t)) {
- i = jrrtilevq_tile_coords(x, y, w, h, t);
- if (min_index < tile[i])
- canidate_transforms &= ~(1<<t);
- }
- }
- }
- }
- return jrrtilevq_ctz(canidate_transforms);
-} */
-
-
static uint32_t jrrtilevq_hashmap_find_slot(const struct jrrtilevq_tilemap* tm, const uint8_t* tile)
{
assert(tm && tile);
@@ -544,7 +447,6 @@ int jrrtilevq_tilemap_make(struct jrrtilevq_tilemap* tm_out, const uint8_t* imag
tm.pal_array[0] = 0x00000000;
tm.n_pals = 1;
-
tm.pal_array[255] = 0xffff00ff;
int image_pixel_x, image_pixel_y;
@@ -643,6 +545,11 @@ void debug_render_and_wait(struct jrrtilevq_tilemap* tm)
image_width = tm->distance_matrix_width;
uint8_t* image = JRRTILEVQ_MALLOC(image_width * image_height * sizeof(uint32_t));
+ for (y = 0; y < image_height; ++y) {
+ for (x = 0; x < image_width; ++x) {
+ jrrtilevq_write_u32_le(image + ((y * image_width + x) * sizeof(uint32_t)), 0xff000000);
+ }
+ }
jrrtilevq_tilemap_render(image, image_width, image_height, tm, 0, 0);
uint64_t* total_distances = JRRTILEVQ_MALLOC(tm->distance_matrix_width * sizeof(uint64_t));
@@ -777,10 +684,10 @@ int jrrtilevq_tilemap_reduce(struct jrrtilevq_tilemap* tm, unsigned target_n_til
tm->n_pairs = 0;
for (index_m = 0; index_m < tm->distance_matrix_capacity; ++index_m) {
jrrtilevq_inv_distance_matrix_coords(&index_a, &index_b, index_m, matrix_width);
- if (!tm->count_array[index_a])
- continue;
- if (!tm->count_array[index_b])
+ if (index_b >= tm->n_tiles) {
+ index_m += index_b-1;
continue;
+ }
d = tm->distance_matrix[index_m];
if (!((d & 0x1fffffff) <= min_distance)) {
if ((d & 0x1fffffff) < next_min_distance)
@@ -824,45 +731,79 @@ stop_selecting:
jrrtilevq_make_merged_tile(tm, merged_tile, index_a, index_b, flip_b, bias);
for (ty = 0; ty < tm->map_height; ++ty) {
for (tx = 0; tx < tm->map_width; ++tx) {
+ uint8_t flip_m;
if ((tm->map[ty * tm->map_width + tx] & 0x1fffffff) == index_b) {
- uint8_t flip_m = tm->map[ty * tm->map_width + tx] >> 29;
+ flip_m = tm->map[ty * tm->map_width + tx] >> 29;
flip_m = jrrtilevq_apply_t(flip_b, flip_m);
tm->map[ty * tm->map_width + tx] = index_m | ((uint32_t)flip_m << 29);
}
+ if ((tm->map[ty * tm->map_width + tx] & 0x1fffffff) == (tm->n_tiles-1)) {
+ flip_m = tm->map[ty * tm->map_width + tx] >> 29;
+ tm->map[ty * tm->map_width + tx] = index_b | ((uint32_t)flip_m << 29);
+ }
}
}
memcpy(tm->tile_array + (index_m * tile_size), merged_tile, tile_size);
tm->count_array[index_a] = 0;
tm->count_array[index_b] = 0;
tm->count_array[index_m] = count_m;
- --n_tiles_to_merge;
- if (!n_tiles_to_merge)
- break;
+ uint32_t index_a2;
+ uint32_t index_b2;
for (j = i+1; j < tm->n_pairs; ++j) {
- uint32_t index_a2;
- uint32_t index_b2;
+ /*d = tm->index_pair_queue[j];
+ jrrtilevq_inv_distance_matrix_coords(&index_a2, &index_b2, (d & 0x1fffffff), matrix_width);
+ if (index_a2 == index_b)
+ index_a2 = index_m;
+ if (index_b2 == index_b)
+ index_b2 = index_m;
+ if (index_a2 == tm->n_tiles-1)
+ index_a2 = index_b;
+ if (index_b2 == tm->n_tiles-1)
+ index_b2 = index_b;
+ if (index_a2 == index_b2) {
+ tm->index_pair_queue[j] = UINT32_MAX;
+ } else {
+ d = jrrtilevq_distance_matrix_coords(index_a2, index_b2, matrix_width) | (d & 0xe0000000);
+ tm->index_pair_queue[j] = d;
+ }*/
d = tm->index_pair_queue[j];
jrrtilevq_inv_distance_matrix_coords(&index_a2, &index_b2, (d & 0x1fffffff), matrix_width);
if ((index_a == index_a2)
|| (index_b == index_a2)
|| (index_a == index_b2)
- || (index_b == index_b2))
+ || (index_b == index_b2)
+ || (tm->n_tiles-1 == index_a2)
+ || (tm->n_tiles-1 == index_b2))
tm->index_pair_queue[j] = UINT32_MAX;
}
assert(index_m < matrix_width);
// Update distance_matrix but only the row for the new tile.
- index_b = index_m;
- for (index_a = 0; index_a < index_b; ++index_a) {
- d = jrrtilevq_minimum_changed_pixels(tm, index_a, index_b, allowed_flips);
- index_m = jrrtilevq_distance_matrix_coords(index_a, index_b, matrix_width);
+ index_b2 = index_m;
+ for (index_a2 = 0; index_a2 < index_b2; ++index_a2) {
+ d = jrrtilevq_minimum_changed_pixels(tm, index_a2, index_b2, allowed_flips);
+ index_m = jrrtilevq_distance_matrix_coords(index_a2, index_b2, matrix_width);
tm->distance_matrix[index_m] = d;
}
- //index_a = index_b;
- for (index_b = index_a+1; index_b < matrix_width; ++index_b) {
- d = jrrtilevq_minimum_changed_pixels(tm, index_a, index_b, allowed_flips);
- index_m = jrrtilevq_distance_matrix_coords(index_a, index_b, matrix_width);
+ index_a2 = index_b2;
+ for (index_b2 = index_a2+1; index_b2 < tm->n_tiles; ++index_b2) {
+ d = jrrtilevq_minimum_changed_pixels(tm, index_a2, index_b2, allowed_flips);
+ index_m = jrrtilevq_distance_matrix_coords(index_a2, index_b2, matrix_width);
tm->distance_matrix[index_m] = d;
}
+ --tm->n_tiles;
+ memcpy(tm->tile_array + (index_b * tile_size), tm->tile_array + (tm->n_tiles * tile_size), tile_size);
+ tm->count_array[index_b] = tm->count_array[tm->n_tiles];
+ tm->count_array[tm->n_tiles] = 0;
+ for (index_a2 = 0; index_a2 < tm->n_tiles; ++index_a2) {
+ if (index_a2 == index_b)
+ continue;
+ index_b2 = jrrtilevq_distance_matrix_coords(index_a2, tm->n_tiles, matrix_width);
+ index_m = jrrtilevq_distance_matrix_coords(index_a2, index_b, matrix_width);
+ tm->distance_matrix[index_m] = tm->distance_matrix[index_b2];
+ }
+ --n_tiles_to_merge;
+ if (!n_tiles_to_merge)
+ break;
}
min_distance = next_min_distance;
}