1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // File: vogl_resampler.h
28 // RG: This is public domain code, originally derived from Graphics Gems 3, see: http://code.google.com/p/imageresampler/
29 #include "vogl_core.h"
30 #include "vogl_resampler.h"
31 #include "vogl_resample_filters.h"
35 #define resampler_assert VOGL_ASSERT
37 static inline int resampler_range_check(int v, int h)
40 resampler_assert((v >= 0) && (v < h));
45 #define max(a, b) (((a) > (b)) ? (a) : (b))
49 #define min(a, b) (((a) < (b)) ? (a) : (b))
60 #define RESAMPLER_DEBUG 0
62 // (x mod y) with special handling for negative x values.
63 static inline int posmod(int x, int y)
78 // Float to int cast with truncation.
79 static inline int cast_to_int(Resample_Real i)
84 /* Ensure that the contributing source sample is
85 * within bounds. If not, reflect, clamp, or wrap.
87 int Resampler::reflect(const int j, const int src_x, const Boundary_Op boundary_op)
93 if (boundary_op == BOUNDARY_REFLECT)
100 else if (boundary_op == BOUNDARY_WRAP)
101 n = posmod(j, src_x);
107 if (boundary_op == BOUNDARY_REFLECT)
109 n = (src_x - j) + (src_x - 1);
114 else if (boundary_op == BOUNDARY_WRAP)
115 n = posmod(j, src_x);
125 // The make_clist() method generates, for all destination samples,
126 // the list of all source samples with non-zero weighted contributions.
127 Resampler::Contrib_List *Resampler::make_clist(
128 int src_x, int dst_x, Boundary_Op boundary_op,
129 Resample_Real (*Pfilter)(Resample_Real),
130 Resample_Real filter_support,
131 Resample_Real filter_scale,
132 Resample_Real src_ofs)
136 // The center of the range in DISCRETE coordinates (pixel center = 0.0f).
137 Resample_Real center;
141 int i, j, k, n, left, right;
142 Resample_Real total_weight;
143 Resample_Real xscale, center, half_width, weight;
144 Contrib_List *Pcontrib;
146 Contrib *Pcpool_next;
147 Contrib_Bounds *Pcontrib_bounds;
149 if ((Pcontrib = (Contrib_List *)vogl_calloc(dst_x, sizeof(Contrib_List))) == NULL)
152 Pcontrib_bounds = (Contrib_Bounds *)vogl_calloc(dst_x, sizeof(Contrib_Bounds));
153 if (!Pcontrib_bounds)
159 const Resample_Real oo_filter_scale = 1.0f / filter_scale;
161 const Resample_Real NUDGE = 0.5f;
162 xscale = dst_x / (Resample_Real)src_x;
169 /* Handle case when there are fewer destination
170 * samples than source samples (downsampling/minification).
173 // stretched half width of filter
174 half_width = (filter_support / xscale) * filter_scale;
176 // Find the range of source sample(s) that will contribute to each destination sample.
178 for (i = 0, n = 0; i < dst_x; i++)
180 // Convert from discrete to continuous coordinates, scale, then convert back to discrete.
181 center = ((Resample_Real)i + NUDGE) / xscale;
185 left = cast_to_int((Resample_Real)floor(center - half_width));
186 right = cast_to_int((Resample_Real)ceil(center + half_width));
188 Pcontrib_bounds[i].center = center;
189 Pcontrib_bounds[i].left = left;
190 Pcontrib_bounds[i].right = right;
192 n += (right - left + 1);
195 /* Allocate memory for contributors. */
197 if ((n == 0) || ((Pcpool = (Contrib *)vogl_calloc(n, sizeof(Contrib))) == NULL))
200 vogl_free(Pcontrib_bounds);
205 Pcpool_next = Pcpool;
207 /* Create the list of source samples which
208 * contribute to each destination sample.
211 for (i = 0; i < dst_x; i++)
214 Resample_Real max_w = -1e+20f;
216 center = Pcontrib_bounds[i].center;
217 left = Pcontrib_bounds[i].left;
218 right = Pcontrib_bounds[i].right;
221 Pcontrib[i].p = Pcpool_next;
222 Pcpool_next += (right - left + 1);
223 resampler_assert((Pcpool_next - Pcpool) <= total);
227 for (j = left; j <= right; j++)
228 total_weight += (*Pfilter)((center - (Resample_Real)j) * xscale * oo_filter_scale);
229 const Resample_Real norm = static_cast<Resample_Real>(1.0f / total_weight);
237 for (j = left; j <= right; j++)
239 weight = (*Pfilter)((center - (Resample_Real)j) * xscale * oo_filter_scale) * norm;
243 n = reflect(j, src_x, boundary_op);
246 printf("%i(%f), ", n, weight);
249 /* Increment the number of source
250 * samples which contribute to the
251 * current destination sample.
256 Pcontrib[i].p[k].pixel = (unsigned short)n; /* store src sample number */
257 Pcontrib[i].p[k].weight = weight; /* store src sample weight */
259 total_weight += weight; /* total weight of all contributors */
272 //resampler_assert(Pcontrib[i].n);
273 //resampler_assert(max_k != -1);
274 if ((max_k == -1) || (Pcontrib[i].n == 0))
278 vogl_free(Pcontrib_bounds);
282 if (total_weight != 1.0f)
283 Pcontrib[i].p[max_k].weight += 1.0f - total_weight;
288 /* Handle case when there are more
289 * destination samples than source
290 * samples (upsampling).
293 half_width = filter_support * filter_scale;
295 // Find the source sample(s) that contribute to each destination sample.
297 for (i = 0, n = 0; i < dst_x; i++)
299 // Convert from discrete to continuous coordinates, scale, then convert back to discrete.
300 center = ((Resample_Real)i + NUDGE) / xscale;
304 left = cast_to_int((Resample_Real)floor(center - half_width));
305 right = cast_to_int((Resample_Real)ceil(center + half_width));
307 Pcontrib_bounds[i].center = center;
308 Pcontrib_bounds[i].left = left;
309 Pcontrib_bounds[i].right = right;
311 n += (right - left + 1);
314 /* Allocate memory for contributors. */
317 if ((total == 0) || ((Pcpool = (Contrib *)vogl_calloc(total, sizeof(Contrib))) == NULL))
320 vogl_free(Pcontrib_bounds);
324 Pcpool_next = Pcpool;
326 /* Create the list of source samples which
327 * contribute to each destination sample.
330 for (i = 0; i < dst_x; i++)
333 Resample_Real max_w = -1e+20f;
335 center = Pcontrib_bounds[i].center;
336 left = Pcontrib_bounds[i].left;
337 right = Pcontrib_bounds[i].right;
340 Pcontrib[i].p = Pcpool_next;
341 Pcpool_next += (right - left + 1);
342 resampler_assert((Pcpool_next - Pcpool) <= total);
345 for (j = left; j <= right; j++)
346 total_weight += (*Pfilter)((center - (Resample_Real)j) * oo_filter_scale);
348 const Resample_Real norm = static_cast<Resample_Real>(1.0f / total_weight);
356 for (j = left; j <= right; j++)
358 weight = (*Pfilter)((center - (Resample_Real)j) * oo_filter_scale) * norm;
362 n = reflect(j, src_x, boundary_op);
365 printf("%i(%f), ", n, weight);
368 /* Increment the number of source
369 * samples which contribute to the
370 * current destination sample.
375 Pcontrib[i].p[k].pixel = (unsigned short)n; /* store src sample number */
376 Pcontrib[i].p[k].weight = weight; /* store src sample weight */
378 total_weight += weight; /* total weight of all contributors */
391 //resampler_assert(Pcontrib[i].n);
392 //resampler_assert(max_k != -1);
394 if ((max_k == -1) || (Pcontrib[i].n == 0))
398 vogl_free(Pcontrib_bounds);
402 if (total_weight != 1.0f)
403 Pcontrib[i].p[max_k].weight += 1.0f - total_weight;
411 vogl_free(Pcontrib_bounds);
416 void Resampler::resample_x(Sample *Pdst, const Sample *Psrc)
418 resampler_assert(Pdst);
419 resampler_assert(Psrc);
423 Contrib_List *Pclist = m_Pclist_x;
426 for (i = m_resample_dst_x; i > 0; i--, Pclist++)
428 #if VOGL_RESAMPLER_DEBUG_OPS
429 total_ops += Pclist->n;
432 for (j = Pclist->n, p = Pclist->p, total = 0; j > 0; j--, p++)
433 total += Psrc[p->pixel] * p->weight;
439 void Resampler::scale_y_mov(Sample *Ptmp, const Sample *Psrc, Resample_Real weight, int dst_x)
443 #if VOGL_RESAMPLER_DEBUG_OPS
447 // Not += because temp buf wasn't cleared.
448 for (i = dst_x; i > 0; i--)
449 *Ptmp++ = *Psrc++ * weight;
452 void Resampler::scale_y_add(Sample *Ptmp, const Sample *Psrc, Resample_Real weight, int dst_x)
454 #if VOGL_RESAMPLER_DEBUG_OPS
458 for (int i = dst_x; i > 0; i--)
459 (*Ptmp++) += *Psrc++ * weight;
462 void Resampler::clamp(Sample *Pdst, int n)
467 *Pdst++ = clamp_sample(x);
472 void Resampler::resample_y(Sample *Pdst)
476 Contrib_List *Pclist = &m_Pclist_y[m_cur_dst_y];
478 Sample *Ptmp = m_delay_x_resample ? m_Ptmp_buf : Pdst;
479 resampler_assert(Ptmp);
481 /* Process each contributor. */
483 for (i = 0; i < Pclist->n; i++)
485 /* locate the contributor's location in the scan
486 * buffer -- the contributor must always be found!
489 for (j = 0; j < MAX_SCAN_BUF_SIZE; j++)
490 if (m_Pscan_buf->scan_buf_y[j] == Pclist->p[i].pixel)
493 resampler_assert(j < MAX_SCAN_BUF_SIZE);
495 Psrc = m_Pscan_buf->scan_buf_l[j];
498 scale_y_mov(Ptmp, Psrc, Pclist->p[i].weight, m_intermediate_x);
500 scale_y_add(Ptmp, Psrc, Pclist->p[i].weight, m_intermediate_x);
502 /* If this source line doesn't contribute to any
503 * more destination lines then mark the scanline buffer slot
504 * which holds this source line as free.
505 * (The max. number of slots used depends on the Y
506 * axis sampling factor and the scaled filter width.)
509 if (--m_Psrc_y_count[resampler_range_check(Pclist->p[i].pixel, m_resample_src_y)] == 0)
511 m_Psrc_y_flag[resampler_range_check(Pclist->p[i].pixel, m_resample_src_y)] = FALSE;
512 m_Pscan_buf->scan_buf_y[j] = -1;
516 /* Now generate the destination line */
518 if (m_delay_x_resample) // Was X resampling delayed until after Y resampling?
520 resampler_assert(Pdst != Ptmp);
521 resample_x(Pdst, Ptmp);
525 resampler_assert(Pdst == Ptmp);
529 clamp(Pdst, m_resample_dst_x);
532 bool Resampler::put_line(const Sample *Psrc)
536 if (m_cur_src_y >= m_resample_src_y)
539 /* Does this source line contribute
540 * to any destination line? if not,
544 if (!m_Psrc_y_count[resampler_range_check(m_cur_src_y, m_resample_src_y)])
550 /* Find an empty slot in the scanline buffer. (FIXME: Perf. is terrible here with extreme scaling ratios.) */
552 for (i = 0; i < MAX_SCAN_BUF_SIZE; i++)
553 if (m_Pscan_buf->scan_buf_y[i] == -1)
556 /* If the buffer is full, exit with an error. */
558 if (i == MAX_SCAN_BUF_SIZE)
560 m_status = STATUS_SCAN_BUFFER_FULL;
564 m_Psrc_y_flag[resampler_range_check(m_cur_src_y, m_resample_src_y)] = TRUE;
565 m_Pscan_buf->scan_buf_y[i] = m_cur_src_y;
567 /* Does this slot have any memory allocated to it? */
569 if (!m_Pscan_buf->scan_buf_l[i])
571 if ((m_Pscan_buf->scan_buf_l[i] = (Sample *)vogl_malloc(m_intermediate_x * sizeof(Sample))) == NULL)
573 m_status = STATUS_OUT_OF_MEMORY;
578 // Resampling on the X axis first?
579 if (m_delay_x_resample)
581 resampler_assert(m_intermediate_x == m_resample_src_x);
583 // Y-X resampling order
584 memcpy(m_Pscan_buf->scan_buf_l[i], Psrc, m_intermediate_x * sizeof(Sample));
588 resampler_assert(m_intermediate_x == m_resample_dst_x);
590 // X-Y resampling order
591 resample_x(m_Pscan_buf->scan_buf_l[i], Psrc);
599 const Resampler::Sample *Resampler::get_line()
603 /* If all the destination lines have been
604 * generated, then always return NULL.
607 if (m_cur_dst_y == m_resample_dst_y)
610 /* Check to see if all the required
611 * contributors are present, if not,
615 for (i = 0; i < m_Pclist_y[m_cur_dst_y].n; i++)
616 if (!m_Psrc_y_flag[resampler_range_check(m_Pclist_y[m_cur_dst_y].p[i].pixel, m_resample_src_y)])
619 resample_y(m_Pdst_buf);
626 Resampler::~Resampler()
630 #if VOGL_RESAMPLER_DEBUG_OPS
631 printf("actual ops: %i\n", total_ops);
634 vogl_free(m_Pdst_buf);
639 vogl_free(m_Ptmp_buf);
643 /* Don't deallocate a contibutor list
644 * if the user passed us one of their own.
647 if ((m_Pclist_x) && (!m_clist_x_forced))
649 vogl_free(m_Pclist_x->p);
650 vogl_free(m_Pclist_x);
654 if ((m_Pclist_y) && (!m_clist_y_forced))
656 vogl_free(m_Pclist_y->p);
657 vogl_free(m_Pclist_y);
661 vogl_free(m_Psrc_y_count);
662 m_Psrc_y_count = NULL;
664 vogl_free(m_Psrc_y_flag);
665 m_Psrc_y_flag = NULL;
669 for (i = 0; i < MAX_SCAN_BUF_SIZE; i++)
670 vogl_free(m_Pscan_buf->scan_buf_l[i]);
672 vogl_free(m_Pscan_buf);
677 void Resampler::restart()
679 if (STATUS_OKAY != m_status)
682 m_cur_src_y = m_cur_dst_y = 0;
685 for (i = 0; i < m_resample_src_y; i++)
687 m_Psrc_y_count[i] = 0;
688 m_Psrc_y_flag[i] = FALSE;
691 for (i = 0; i < m_resample_dst_y; i++)
693 for (j = 0; j < m_Pclist_y[i].n; j++)
694 m_Psrc_y_count[resampler_range_check(m_Pclist_y[i].p[j].pixel, m_resample_src_y)]++;
697 for (i = 0; i < MAX_SCAN_BUF_SIZE; i++)
699 m_Pscan_buf->scan_buf_y[i] = -1;
701 vogl_free(m_Pscan_buf->scan_buf_l[i]);
702 m_Pscan_buf->scan_buf_l[i] = NULL;
706 Resampler::Resampler(int src_x, int src_y,
707 int dst_x, int dst_y,
708 Boundary_Op boundary_op,
709 Resample_Real sample_low, Resample_Real sample_high,
710 const char *Pfilter_name,
711 Contrib_List *Pclist_x,
712 Contrib_List *Pclist_y,
713 Resample_Real filter_x_scale,
714 Resample_Real filter_y_scale,
715 Resample_Real src_x_ofs,
716 Resample_Real src_y_ofs)
719 Resample_Real support, (*func)(Resample_Real);
721 resampler_assert(src_x > 0);
722 resampler_assert(src_y > 0);
723 resampler_assert(dst_x > 0);
724 resampler_assert(dst_y > 0);
726 #if VOGL_RESAMPLER_DEBUG_OPS
733 m_delay_x_resample = false;
734 m_intermediate_x = 0;
737 m_clist_x_forced = false;
739 m_clist_y_forced = false;
741 m_Psrc_y_count = NULL;
742 m_Psrc_y_flag = NULL;
744 m_status = STATUS_OKAY;
746 m_resample_src_x = src_x;
747 m_resample_src_y = src_y;
748 m_resample_dst_x = dst_x;
749 m_resample_dst_y = dst_y;
751 m_boundary_op = boundary_op;
753 if ((m_Pdst_buf = (Sample *)vogl_malloc(m_resample_dst_x * sizeof(Sample))) == NULL)
755 m_status = STATUS_OUT_OF_MEMORY;
759 // Find the specified filter.
761 if (Pfilter_name == NULL)
762 Pfilter_name = VOGL_RESAMPLER_DEFAULT_FILTER;
764 for (i = 0; i < g_num_resample_filters; i++)
765 if (strcmp(Pfilter_name, g_resample_filters[i].name) == 0)
768 if (i == g_num_resample_filters)
770 m_status = STATUS_BAD_FILTER_NAME;
774 func = g_resample_filters[i].func;
775 support = g_resample_filters[i].support;
777 /* Create contributor lists, unless the user supplied custom lists. */
781 m_Pclist_x = make_clist(m_resample_src_x, m_resample_dst_x, m_boundary_op, func, support, filter_x_scale, src_x_ofs);
784 m_status = STATUS_OUT_OF_MEMORY;
790 m_Pclist_x = Pclist_x;
791 m_clist_x_forced = true;
796 m_Pclist_y = make_clist(m_resample_src_y, m_resample_dst_y, m_boundary_op, func, support, filter_y_scale, src_y_ofs);
799 m_status = STATUS_OUT_OF_MEMORY;
805 m_Pclist_y = Pclist_y;
806 m_clist_y_forced = true;
809 if ((m_Psrc_y_count = (int *)vogl_calloc(m_resample_src_y, sizeof(int))) == NULL)
811 m_status = STATUS_OUT_OF_MEMORY;
815 if ((m_Psrc_y_flag = (unsigned char *)vogl_calloc(m_resample_src_y, sizeof(unsigned char))) == NULL)
817 m_status = STATUS_OUT_OF_MEMORY;
821 /* Count how many times each source line
822 * contributes to a destination line.
825 for (i = 0; i < m_resample_dst_y; i++)
826 for (j = 0; j < m_Pclist_y[i].n; j++)
827 m_Psrc_y_count[resampler_range_check(m_Pclist_y[i].p[j].pixel, m_resample_src_y)]++;
829 if ((m_Pscan_buf = (Scan_Buf *)vogl_malloc(sizeof(Scan_Buf))) == NULL)
831 m_status = STATUS_OUT_OF_MEMORY;
835 for (i = 0; i < MAX_SCAN_BUF_SIZE; i++)
837 m_Pscan_buf->scan_buf_y[i] = -1;
838 m_Pscan_buf->scan_buf_l[i] = NULL;
841 m_cur_src_y = m_cur_dst_y = 0;
843 // Determine which axis to resample first by comparing the number of multiplies required
844 // for each possibility.
845 int x_ops = count_ops(m_Pclist_x, m_resample_dst_x);
846 int y_ops = count_ops(m_Pclist_y, m_resample_dst_y);
848 // Hack 10/2000: Weight Y axis ops a little more than X axis ops.
849 // (Y axis ops use more cache resources.)
850 int xy_ops = x_ops * m_resample_src_y +
851 (4 * y_ops * m_resample_dst_x) / 3;
853 int yx_ops = (4 * y_ops * m_resample_src_x) / 3 +
854 x_ops * m_resample_dst_y;
856 #if VOGL_RESAMPLER_DEBUG_OPS
857 printf("src: %i %i\n", m_resample_src_x, m_resample_src_y);
858 printf("dst: %i %i\n", m_resample_dst_x, m_resample_dst_y);
859 printf("x_ops: %i\n", x_ops);
860 printf("y_ops: %i\n", y_ops);
861 printf("xy_ops: %i\n", xy_ops);
862 printf("yx_ops: %i\n", yx_ops);
865 // Now check which resample order is better. In case of a tie, choose the order
866 // which buffers the least amount of data.
867 if ((xy_ops > yx_ops) ||
868 ((xy_ops == yx_ops) && (m_resample_src_x < m_resample_dst_x)))
870 m_delay_x_resample = true;
871 m_intermediate_x = m_resample_src_x;
875 m_delay_x_resample = false;
876 m_intermediate_x = m_resample_dst_x;
878 #if VOGL_RESAMPLER_DEBUG_OPS
879 printf("delaying: %i\n", m_delay_x_resample);
883 if (m_delay_x_resample)
885 if ((m_Ptmp_buf = (Sample *)vogl_malloc(m_intermediate_x * sizeof(Sample))) == NULL)
887 m_status = STATUS_OUT_OF_MEMORY;
893 void Resampler::get_clists(Contrib_List **ptr_clist_x, Contrib_List **ptr_clist_y)
896 *ptr_clist_x = m_Pclist_x;
899 *ptr_clist_y = m_Pclist_y;
902 int Resampler::get_filter_num()
904 return g_num_resample_filters;
907 const char *Resampler::get_filter_name(int filter_num)
909 if ((filter_num < 0) || (filter_num >= g_num_resample_filters))
912 return g_resample_filters[filter_num].name;