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

Question

Я ищу способ сделать дугу с помощью алгоритма линии Брезенхэма. Этот алгоритм рисует идеальный круг, но что, если мне нужно нарисовать дугу (от 0 до Pi) и повернуть ее на 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 градусов требуется триггер. Вы можете позволить вышеуказанному циклу работать до тех пор, пока ваше отношение x/y не станет равным 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

Если вам точно не нужен Bresenham, в этом посте 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(50 + Math.cos(i) * r, y: 100 + Math.sin(i) * r); // center point is (50,100)
}

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

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