Алгоритм линии С ++ Брезенхема рисует дугу и вращает

Question

Я ищу способ создать дугу с помощью алгоритма линии Брезенхэма.Этот алгоритм рисует идеальный круг, но что, если мне нужно нарисовать дугу (от 0 до Пи) и повернуть ее на 30 градусов (например)?

void DrawCircle(HDC hdc,int x0, int y0, int radius) 
{
        int x = 0;
        int y = radius;
        int delta = 2 - 2 * radius;
        int error = 0;

        while(y >= 0) {
                //SetPixel(hdc,x0 + x, y0 + y,pencol);
                SetPixel(hdc,x0 + x, y0 - y,pencol);
                //SetPixel(hdc,x0 - x, y0 + y,pencol);
                SetPixel(hdc,x0 - x, y0 - y,pencol);
                error = 2 * (delta + y) - 1;
                if(delta < 0 && error <= 0) {
                        ++x;
                        delta += 2 * x + 1;
                        continue;
                }
                error = 2 * (delta - x) - 1;
                if(delta > 0 && error > 0) {
                        --y;
                        delta += 1 - 2 * y;
                        continue;
                }
                ++x;
                delta += 2 * (x - y);
                --y;
        }
}

Answer 1

Чтобы получить 1/2 круга (в пи), вызовите только одну из ваших процедур SetPixel. Для поворота дуги на 30 градусов требуется триггер. Вы можете позволить вышеуказанному циклу работать до тех пор, пока ваше отношение х / у не станет равным tan (30 градусов), а затем начать рисовать, пока ваше отношение не достигнет значения, при котором вы хотите остановиться. Не самый эффективный способ, но он будет работать. Чтобы улучшить его, вам нужно предварительно рассчитать начальные 4 значения переменной. Вы можете взять значения из вышеприведенного прогона и подключить их в качестве начальных значений, и это будет очень эффективно.

Получили ли вы вышеуказанный алгоритм из Черной книги Майкла Абраша ? Если нет, я бы воспользовался этим в качестве второго ориентира для быстрого рисования окружности / дуги.

Ну, увы, эллипсы, которые разрывают главу, там не были включены. Вот что-то, что я нашел в Интернете, которое утверждает, что оно от Абраша:

/* One of Abrash's ellipse algorithms  */

void draw_ellipse(int x, int y, int a, int b, int color)
{
    int wx, wy;
    int thresh;
    int asq = a * a;
    int bsq = b * b;
    int xa, ya;

    draw_pixel(x, y+b, color);
    draw_pixel(x, y-b, color);

    wx = 0;
    wy = b;
    xa = 0;
    ya = asq * 2 * b;
    thresh = asq / 4 - asq * b;

    for (;;) {
        thresh += xa + bsq;

        if (thresh >= 0) {
            ya -= asq * 2;
            thresh -= ya;
            wy--;
        }

        xa += bsq * 2;
        wx++;

        if (xa >= ya)
          break;


        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }

    draw_pixel(x+a, y, color);
    draw_pixel(x-a, y, color);

    wx = a;
    wy = 0;
    xa = bsq * 2 * a;

    ya = 0;
    thresh = bsq / 4 - bsq * a;

    for (;;) {
        thresh += ya + asq;

        if (thresh >= 0) {
            xa -= bsq * 2;
            thresh = thresh - xa;
            wx--;
        }

        ya += asq * 2;
        wy++;

        if (ya > xa)
          break;

        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }
}

Идея состоит в том, что вы рисуете 8-й круг за раз х4, а затем переворачиваете, чтобы получить остальные 8-е. Тем не менее, не дает прямого ответа на ваш вопрос. Работая над этим ...

Опять же, ваш код выше должен работать, вам просто нужно тщательно контролировать начальные и конечные условия. Значение y> = 0 должно быть таким, каким будет значение y после окончания длины «дуги», а начальные значения должны быть рассчитаны, чтобы стать началом вашей дуги.

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

Answer 2

Если вам точно не нужен Брезенхем, в этой статье SO есть быстрый шаговый метод , в котором вы можете установить центральную точку, Начальная точка и угол дуги. Для него не нужен критерий остановки, потому что он уже включен в алгоритм (по углу дуги). Что делает его быстрым, так это предварительный расчет коэффициентов тангенциального и радиального перемещения, и в самом цикле нет вызовов триггерных функций, только умножение, сложение и вычитание.

AFAIK существует три типа методов:
А) Инкрементальный, как Брезенхэм
Б) Подразделить метод, как этот
В) ступенчатый (или сегментный) метод

Я возьму медленный пример пошагового метода (не используйте его, если важна скорость):

// I know the question is tagged c++, but the idea comes clear in javascript
var start_angle = 0.5, end_angle = 1.1, r = 30;
for(var i = start_angle; i < end_angle; i = i + 0.05)
{
  drawpixel(x: 50 + Math.cos(i) * r, y: 100 + Math.sin(i) * r); // center point is (x = 50, y = 100)
}

Медлительность происходит от cos и греха, которые повторяются (без необходимости) в цикле. Это может быть решено путем предварительного вычисления cos и sin, как описано в вышеупомянутой публикации SO. Это означает огромное ускорение (в среднем 12x в топ-5 движков JavaScript).

Я сделал не полностью сопоставимое speedtest различных алгоритмов рисования кругов и дуг. Bresenham быстр, но необходимо добавить логику критериев запуска и остановки, что немного замедляет алгоритм. Если вам действительно нужны Брезенхем и Арк, у меня нет готового решения для этого и пока не нашел такого. Это, конечно, возможно. Кстати, пошаговый метод с использованием предварительно рассчитанных триггеров не так плох по производительности по сравнению с Bresenham (по крайней мере, в javascript). Пожалуйста, проверьте на C ++ и сообщите.