Все хотят

Интересно, тут есть ещё кто живой?
А кто в теме или хотя бы недавно учился?
А то я старый и тупой, и я не понимаю: Почему алгоритм Брезенхема (Bresenham) завершается?
В классической реализации там один цикл, который делает шаг по x, или шаг по y или оба одновременно. Условием завершения цикла является достижение конечной точки и по x и по y _одновременно_! Понятно, что они достигнут, но кто обещал, что одновременно???

а они и не должны достигать одновременно

мне вот интересно кто еще тут в курсе что такое алгорится брезенхема ))

Да я сам неделю как узнал.
А вот и должны: там условие завершения цикла
$currX == $maxX and $currY == $maxY

Ну и кроме того, я же ленивый... Но когда я алгоритм чуть поменял - он, сцуко, завершаться тут же перестал. Я понимаю, почему: x и y достигают конечной точки не одновременно. Но почему оригинальный завершается?

Я на нём делал отрисовку линий

И отрисовку текстур на сходной штуке тоже

Единственное, я вроде делал просто for по разнице стартовых точек, сначала по х, потом по у

а смысл если эта операция теперь делается графическим процессором? Брезенхем это во времена когда надо было пикселы в видеоамяти вручную закрашивать

Я софтрендер писал

Оно сейчас ещё и кривые делает с заливкой

Уже почти все компоненты готовы, скоро мультик можно будет делать

я помню еще алгоритм брезенхема использовали для векторизации

когда на растровой картинке пытались найти линии

Если dy<=dx, то всегда делается шаг по х и может быть шаг по y.

Если dy>dx, то всегда делается шаг по y и может быть шаг по x.

Ну понеслись воспоминания...
Я, разумеется, не линии на экране рисую. Я рисую прямую на растровой картинке и хочу получить пиксели.
Код на php такой:
function bresenhamGlobalPixels($x0, $y0, $x1, $y1){
$pixels = [];

$dx = abs($x1 - $x0);
$dy = abs($y1 - $y0);

$stepX = ($x0 < $x1) ? 1 : -1;
$stepY = ($y0 < $y1) ? 1 : -1;

$err = $dx - $dy;

while (true) {
$pixels[] = ['x' => $x0, 'y' => $y0];

if ($x0 == $x1 and $y0 == $y1) {
break;
}

$e2 = 2 * $err;
if ($e2 > -$dy) {
$err -= $dy;
$x0 += $stepX;
};
if ($e2 < $dx) {
$err += $dx;
$y0 += $stepY;
};
};
return $pixels;
};
Оно работает. Но я не понимаю, как.

Ну и по определению, мы попадаем в конечную точку.

Но где в этом определении, что одновременно по x и по y?

Что значит "одновременно"? А как может быть не одновременно?

потому что мы так x и y ставим

Оно теперь и лисичек может рисовать

Легко. Сперва по одной координате, а потом по другой.
Условие окончания цикла в приведённом коде сработает только тогда, когда последний шаг - по диагонали. И он, сцуко, всегда по диагонали. Почему?

Мы одну из координат всегда увеличиваем на 1. Она проходит все значения от начала до конца и все.

идем по x и на каждом шаге y или меняем на 1 или не меняем

Только не всегда одну и ту же.

В смысле? 😁
Для фиксированного набора x1y1, x2y2 -- одну и ту же.

что тут непонятного? по x у нас цикл for с шагом 1 и на каждом шаге принимается решение увеличить y или нет. гарантированно что на последнем шаге н всегда будет равен конченому значению

Отлично, по x достигли конца, по y - нет. На следующем обороте x может увеличиться, и привет.
И так оно и происходит.

Во первых, по y -- да. Во вторых, зачем увеличивать x, если мы уже до конца дошли?

у нас нет цикла по y. только по x. когда там добавить 1 к y мы сами решаем

Так не проверяется же, что дошли до конца.

С чего вдруг?

мы прибавляем 1 к y когда превышает невязку

Так если линия от х1у1 до х2у2, то на х2 у2 тоже сто процентов достигнут, максимум за исключением погрешности

идя вдоль x мы эту невязку накпливаем

превысило сразу пррибавляем 1 и невязку зануляем

Ну она не зануляется, Остаток остается.

а невязку мы перед циклом вычисляем грубо говоря как тангенс

ну я несколько упростил

Ну вот это ключевое соображение. Кажется, что ещё чуть-чуть, и я пойму...

я этого не касался последние 30 лет ))

ввиду не актульности задач

появление графическиз процессоров полностью изменило картину

Да я бы всю жизнь не касался: я тупой.

ну когда то этим занимался и в видопамять напрямую писал

Ну я же линию на экране рисую. Я глубину получаю из фалов DEM вдоль локсодромии.

неужели для этого нет готовой функции?

Ну вот нет. Даже для высоты, хотя DEM с высотой существуют давно.

Впрочем, есть некий продукт, где эта задача решается. Даже с открытым кодом. Но там такой говнокод на TypeScript, что проще самому написать. Собственно получение пикселей с картинки там в хрен знает какой библиотеке, я даже не докопался.

а вообще сейчас операция рисования пиксела существует или надо рисовать линию с однинаковым началом и концом?

Эээ... Смотря где.... Я же говорю - я ничего не рисую.

а что тогда? битмап что ли сделать?

я не уловил конечную цель задачи

Да нет, у меня узкоспециализированная задача.
Вот есть файлы DEM. Это такая растровая картинка, в которой цветом пикселя закодирована высота земной поверхности, средняя по площади этого пикселя. Сами картинки - это квадратики (тайлы называются), который покрывают поверхность Земли в соответствии с правилами проекции. Конкретно - WGS84. Она кривая, но удобная.
Прикладная задача состоит в том, чтобы зная положение самолёта или парохода, направление и скорость его движения - определить, не впаяется ли он во что-нибудь в течение заданного времени.
Алгоритмически это сводится к растеризации отрезка пути пикселями файла DEM. Нуивот.

а расетризация тут зачем? не проще ли пересечения линий считать?

Дык глубина - это точки. Определяем глубину вдоль пути.

если там глубины или высоты вроде бы строят линии уровни. метод "нарисоват и закрасить" а потом смотреть что дает getpixel в данной точке рабочий но медленный

Дык в том то весь и цимес, что появились тайлы в формате DEM - сплошное поле параметра, закодированное цветом. Не нужно строить линии уровня и закрашивать - всё уже сделано. Нужно только взять цвет.
Поэтому я надеюсь, что всё будет работать быстро.

тогда я опять не понимаю какую линию надо рисовать. ну грубо говоря взяли значение цвета в данной точке и сравнили с пороговым значением

тайл я так понимаю это квадрат по русски

или мы прокладываем маршрут про брезенхема и в каждой точке вместо закраски берем значение пиксила с кординатами и сравниваем с пороговым значением. так что?

В данной - это в какой? Вот линия - это и есть набор требуемых точек. В прикладном смысле линия (отрезок, да) - это путь, который потенциально пройдёт судно с текущего момента за, скажем, 10 минут. В текущем направлении с текущей скоростью.
Если где-то на этом отрезке мы найдём глубину меньше пороговой - объявляем тревогу. Типа - опасность заехать на мель.
И так - каждое определение положения судна. А современные приёмники ГПС делают это 10 раз в секунду.

Ну да, тайл - это квадрат, конечно, но в русском сегодня - это картографический термин.

у примерно так я и сказал. а нельзя нарисовать картинку с курсом и наложить ее в качестве фильтра?

мне думается так оно будет быстрее чем самопальный брезенхем делать

при условии что счас на дворе не 90-ый год и мы имеем предстввление о шейдерах

А фильтром-то что будет?
И самопальный Брезенхейм - это вон те 30 строчек. Для остального потребуется ... ну, ещё столько же.

я не про то что будет быстрее написать а что будет быстрее работать

на картинку со значениями глубин накладываем картинку с курсом а там какая то фнукция отсечения типа если меньше то красим в черный а если больше то в белый

Что до шейдеров - мы, конечно, имеем понятие, но нужно иметь ещё и где эти шейдеры есть. А софтина должна работать на примерно маршрутизаторе - в 10 раз слабее Raspbery Pi и без всякого графического процессора. Облом с шейдерами.

Я понял про фильтр, и это мысль хорошая, но вот требования к аппаратуре....

а ну тогда правильно

брезенхем самое лучшее раз у нас входные данные в виде растра

фильтр без шейдеров будет тормозить

ну то есть фактически задача как раз и формулируется что у нас на дворе 90-ый год и современных средств компьютерной графики у нас нет

кстати в почему пых неужели там нельзя как то на си собрать кросс-компиляцией и запустить?

Ну как бы хотелось бы обойтись...
Это софт для любительской навигации. Типа, яхтсменов. Типа, на борту сервер, который отвечает за всё вот это, который потребляет электричества как фонарик, и второй такой же лежит в железной коробке в рундуке, чтобы когда в основной ударит молния - просто заменить. Такая концепция.
Несколько условная, но я так вижу.

ну просто если железка настолько слабая то интерпретатор пыха это слишком оверхед

Потому и PHP - не нужно ничего компилировать, занимает мало места и работает быстро. Типа, яхтсмен сжёг свой сервер в жопе мира, пошёл в лавочку, купил другой маршрутизатор, и...

ну я лично помню насколько брезенхем был медленный даже на паскале

Да ни хрена. Тут есть реальный опыт.
А кроме того, наиболее массовая сегодня любительская навигация - вообще на node.js Её на маршрутизатор даже не поставить.

во временя 286-х и доса

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

а питона на железке нету?

А нафига? .Даже микропитон толще, а там вообще ничего нет.

потому что он умеет компилировать

соотвественно и скорость будет

Да хрен его знает... Меня этот Цирк Пайтона эстетически не удовлетворяет. Мне на нём писать неприятно. И там сокеты через жопу.

а профит то в чем?

А нету профита 😊

на яхте то хоть катают? ))

Да у меня своя... Ну, была. Т.е., теоретически она и сейчас есть, но она в Финляндии. А визу, понятно, не дают.

Если у вас там поверхность земли в пикселях записана, то почему вы «прямую» чертите, а не геодезическую?