Как уменьшить масштаб блоков, не вызывая перекрытия пикселей

У меня есть куча блоков, которые нужно нарисовать в сетке. Теперь, отображая их в немасштабированном виде, все в порядке, но когда я пытаюсь уменьшить их, чтобы они соответствовали окну, я получаю «артефакты масштабирования», потому что я использую обычную формулу коэффициента масштабирования и плавает.

Есть ли способ избежать этих проблем?

Общие примеры данных:

Original length: 200000

Уменьшено до 25x25 pixel grid (это мало для разработки и отладки) Максимальная уменьшенная длина: 625 (25 * 25)

Scale-ratio: (625 / 200000) = 0,003125

Пример данных 1 — перекрывающиеся масштабированные блоки перезаписывают друг друга Начало блока => конец блока: [начало, конец)

1: 2100 => 2800
2: 2800 => 3600
3: 3600 => 4500
4: 4500 => 5500

Перепрыгивая через вывод этого примера, я думаю, что примеры 2 и 3 помогут понять суть. Оставил для полноты.

Пример данных 2 — неправильный пробел между 2 и 3 Начало блока => конец блока: [начало, конец)

1: 960 => 1440
2: 1440 => 1920
3: 1920 => 2400

1: 960 => 1440, length: 480, scaled length: 1.5:
2: 1440 => 1920, length: 480, scaled length: 1.5:
3: 1920 => 2400, length: 480, scaled length: 1.5:

пиксель начало, конец, длина

1: 3, 0, 1
2: 4, 0, 1
3: 6, 0, 1

Отображаемая сетка:

[ 0, 0, 0, 1, 2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
...

Пример данных 3 – 1 неправильно перемещен на шаг назад Начало блока => конец блока: [начало, конец)

1: 896 => 1344
2: 1344 => 1792
3: 1792 => 2240

1: 896 => 1344, length: 448, scaled length: 1.4:
2: 1344 => 1792, length: 448, scaled length: 1.4:
3: 1792 => 2240, length: 448, scaled length: 1.4:

пиксель начало, конец, длина

1: 2, 0, 1
2: 4, 0, 1
3: 5, 0, 1

Отображаемая сетка:

[ 0, 0, 1, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
...

Как должны были выглядеть данные примера 2 и 3:

[ 0, 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
...

Помните, что значения блока [начало, конец)

Превентивный удар (проголосовавшие против / тролли) Помните: я не экстрасенс и не телепат. Если вы хотите дать негатив, делайте это в ограничительной форме, иначе это бесполезно (я ничему не научусь) и только засорю ветку.

Обновить

#include <iostream>
#include <math.h>
#include <limits.h>
#include <assert.h>
#include <vector>
#include <array>
#include <utility> // pair
#include <algorithm> // for_each

using namespace std;

const size_t width_size = 25; // 25 pixels
const size_t height_size = 25; // 25 pixels
const size_t grid_length = width_size * height_size; // width * height
array<size_t, grid_length> grid;

const size_t original_length = 200000;

typedef pair<unsigned long, unsigned long> block;
vector<block> test_values;

void show_grid()
{
    for (size_t y = 0; y < height_size; ++y) {
        const size_t start_pos_for_current_heigth = y * width_size;
        const size_t end_pos_for_current_heigth = start_pos_for_current_heigth + width_size;

        cout << "[ ";
        for (size_t i = start_pos_for_current_heigth; i < end_pos_for_current_heigth; ++i) {
            if (i + 1 < end_pos_for_current_heigth)
                cout << grid[i] << ", ";
            else
                cout << grid[i];
        };
        cout << " ]" << endl;
    }
}

void scale_and_add(const float scale)
{
    size_t test_value_id = 1;

    for_each(test_values.cbegin(), test_values.cend(), [&](const block &p) {
        const float s_f = p.first * scale;
        const unsigned long s = round(s_f);
        const float e_f = p.second * scale;
        const unsigned long e = round(e_f);
        const unsigned long block_length = p.second - p.first;
        const float block_length_scaled = block_length * scale;
        assert(s <= grid_length);
        assert(e <= grid_length);

        cout << test_value_id << ":" << endl;
        cout << " " << p.first << " => " << p.second << " length: " << block_length << endl;
        cout << " " << s << " (" << s_f << ") => " << e << " (" << e_f << ") length: " << (e - s) << " (" << block_length_scaled << ")" << " (scaled)" << endl;

        for (size_t i = s; i < e; ++i) {
            if (grid[i] != 0) {
                cout << "overlapp detected !" << endl;
            }
            grid[i] = test_value_id;
        }

        ++test_value_id;
    });
}

void reset_common()
{
    grid.fill(0);
    test_values.clear();
}

int main()
{
    const float scale = ((float)grid_length / (float)original_length);
    cout << "scale: " << scale << " length per pixel: " << ((float)original_length / (float)grid_length) << endl;

    // Example data 1
/*    cout << "Example data 1" << endl;

    test_values.push_back(make_pair(2100, 2800));
    test_values.push_back(make_pair(2800, 3600));
    test_values.push_back(make_pair(3600, 4500));
    test_values.push_back(make_pair(4500, 5500));

    scale_and_add(scale);
    show_grid();

    reset_common();

    // Example data 2
    cout << "Example data 2" << endl;

    test_values.push_back(make_pair(960, 1440));
    test_values.push_back(make_pair(1440, 1920));
    test_values.push_back(make_pair(1920, 2400));

    scale_and_add(scale);
    show_grid();

    reset_common();

    // Example data 3
    cout << endl << "Example data 3" << endl;

    test_values.push_back(make_pair(896, 1344));
    test_values.push_back(make_pair(1344, 1792));
    test_values.push_back(make_pair(1792, 2240));

    scale_and_add(scale);
    show_grid();

    reset_common();*/

    // Generated data - to quickly find the problem
    cout << "Generated data" << endl;

    auto to_op = [&](const size_t v) {
        return v * (original_length / grid_length) * 1.3; // 1.4 and 1.5 are also good values to show the problem
    };
    size_t pos = 0;
    size_t psize = 1; // Note this value (length) and check it with the displayed one, you'll be surprised !
    for (size_t g = 0; g < 10; ++g) {
        test_values.push_back(make_pair(to_op(pos), to_op(pos + psize)));
        pos += psize;
    }

    scale_and_add(scale);
    show_grid();

    return 0;
}

Выход:

scale: 0.003125 length per pixel: 320
    Generated data
1:
 0 => 416 length: 416
 0 (0) => 1 (1.3) length: 1 (1.3) (scaled)
2:
 416 => 832 length: 416
 1 (1.3) => 3 (2.6) length: 2 (1.3) (scaled)
3:
 832 => 1248 length: 416
 3 (2.6) => 4 (3.9) length: 1 (1.3) (scaled)
4:
 1248 => 1664 length: 416
 4 (3.9) => 5 (5.2) length: 1 (1.3) (scaled)
5:
 1664 => 2080 length: 416
 5 (5.2) => 7 (6.5) length: 2 (1.3) (scaled)
6:
 2080 => 2496 length: 416
 7 (6.5) => 8 (7.8) length: 1 (1.3) (scaled)
7:
 2496 => 2912 length: 416
 8 (7.8) => 9 (9.1) length: 1 (1.3) (scaled)
8:
 2912 => 3328 length: 416
 9 (9.1) => 10 (10.4) length: 1 (1.3) (scaled)
9:
 3328 => 3744 length: 416
 10 (10.4) => 12 (11.7) length: 2 (1.3) (scaled)
10:
 3744 => 4160 length: 416
 12 (11.7) => 13 (13) length: 1 (1.3) (scaled)
[ 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

Этот пример кода более наглядно демонстрирует мою проблему.

Интересный факт: mingw-g++, который я использовал для написания этого примера, показывает немного другие значения. Я обычно использую Visual Studio 2010, но в этот раз не могу, потому что я не дома.


c++ scale floating-point math pixel
person Carl Serl    schedule 23.09.2011    source источник
comment
Фотографии, вероятно, помогли бы понять проблему здесь.   -  person Collin Dauphinee    schedule 23.09.2011
comment
У меня нет изображения, демонстрирующего эту проблему. Отображаемая сетка является прямой копией и вставкой вывода консольной программы, которую я использовал для поиска этой проблемы. Но я могу показать вам изображение того, как это близко будет выглядеть с графикой: ссылка   -  person Carl Serl    schedule 23.09.2011

Ответы (2)


arrow_upward
0
arrow_downward

Я не уверен, что получаю постановку задачи, но попробую. У вас есть диапазоны информации, которые вы отображаете непрерывно, диапазон обычно [a, b). Все в порядке, когда a и b напрямую представляют пиксели, которые вы пытаетесь нарисовать, но у вас возникают проблемы, когда вы хотите масштабировать все это целиком.

Не имея дело с несколькими строками пикселей, если у вас есть два диапазона R1=[a,b) и R2=[b,c) без масштабирования, вы просто рисуете от a до b-1 и от b до c-1, и ваши диапазоны рисуются так в чем проблема в масштабированном случае рисования от (int)(a*scale) до ((int)(b*scale)-1), а затем от (int)(b*scale) до ((int)(c *масштаб)-1), вы можете использовать любое преобразование с плавающей запятой в целое, округление, пол или потолок, и все будет в порядке.

Следующая проблема будет заключаться в том, что если ваши диапазоны масштабирования составляют менее 1 пикселя, в этом случае вам может потребоваться определить, равен ли размер масштабируемого диапазона 0, и внести поправочный коэффициент (в пикселях), который добавляется в конце расчет.

Псевдокод

DrawRanges(List<Range> ranges, float scale)
  int carry = 0;
  foreach(Range range in ranges)
  {
      int newStart = ceiling(range.start*scale);
      int newEnd = ceiling(range.end*scale)-1;

      if (newStart <= newEnd)
      {
        newEnd = newStart;
        ++carry;
      }
      DrawRange(newStart+carry,newEnd+carry);
  }

Это в конечном итоге потерпит неудачу, если у вас больше диапазонов, чем блоков в уменьшенной сетке, вам нужно будет выяснить, как полностью удалить диапазоны. В диапазоне отрисовки вы сопоставляете свой индекс с фактической координатой блока.

Это решает вашу проблему?

person Harald Scheirich    schedule 23.09.2011
comment
Пожалуйста, посмотрите недавно добавленный пример кода, я извиняюсь, я должен был добавить пример кода для начала. - person Carl Serl; 24.09.2011
comment
Что я вижу в вашем коде, так это то, что вы масштабируете начало, конец и длину блока отдельно, вам определенно следует масштабировать только два из этих трех значений, а третье следует за ним, таким образом, набор будет согласованным, поэтому либо масштабируйте начать, закончить и рассчитать длину от этого или масштабировать начало и длину и рассчитать конец от этого. Масштабирование всех трех вызовет проблемы с округлением, особенно при использовании round(). Это домашнее задание кстати? - person Harald Scheirich; 24.09.2011
comment
Длина указана как отладочное значение. Если вы посмотрите внимательно, я просто печатаю длину. Домашнее задание, я бы хотел, тогда я мог бы просто спросить об этом учителя. Это просто еще один забавный проект. - person Carl Serl; 24.09.2011
comment
Поскольку вы спросили, было ли это домашним заданием. Вы говорите, что решение простое, и я просто его не вижу? - person Carl Serl; 28.09.2011
comment
Нет, такого рода проблемы звучат как домашние задания. Вы смотрите на проблему дискретизации, лишние сэмплы на самом деле не осветляют. В последнем случае похоже, что все диапазоны смежны, не так ли, как вы ожидаете? Я не знаю, чего вы ожидаете, каждый раз, когда вы делаете круг, вы вносите ошибку, в конечном итоге вам, возможно, придется исправить эту ошибку. - person Harald Scheirich; 28.09.2011

arrow_upward
0
arrow_downward

Да, +1, чтобы поддержать вас, вопрос в порядке. Я не знаю, почему люди думают, что так весело ставить минусы, даже не оставляя комментариев.

Ну и к вопросу :-)

Обычно при рисовании у вас возникают проблемы с перекрытием, а в компьютерной 3D-графике с визуализаторами развертки (например, DirectX и OpenGL) они обычно пропускают ровно один пиксель (скажем, все справа и снизу). Может быть, это может помочь вам.

Также возможно, что при идеальном делении у вас нет артефактов, поэтому вам, возможно, придется иметь дело с этим (т. Е. Если значение является «идеальным целым числом», например 185,000000, тогда не удаляйте последний пиксель) .

ХТН

person Valmond    schedule 23.09.2011