| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Комбинированный алгоритм Кузьмина |
| Автор: GremlinProg 26.7.2007, 19:55 |
| Я предлагаю обсудить реализацию алгоритма, описанного здесь: http://fit.com.ru/Surveys/Course/Lecture_02_Part_2.doc (суть находится в самом конце дока) Описано сухо, поэтому поясню его со своей точки зрения. По сути, это модернизация всем известного алгоритма Брезенхема построения растра линии. Разница лишь в том, что здесь решается маленькая проблемка такого построения при отсечении отрезка прямоугольником: если вычислить координаты отрезка, например, с помощью отсечения Сазерленда-Кохена и построить его по Брезенхему, то на различных прямоугольниках, эта линия будет рисоваться по-разному. Проблема заключается в том, что при построении полной, неотсеченной версии, координаты отсеченного отрезка не всегда будут находиться на прямой Брезенхема, то же самое касается и начальной ошибки e = 2 * dy - dx, отсюда и ошибка растеризации. Кузьмин предложил более точный способ: вычислять растр, используя параметры полной, неотсеченой версии, но опираясь на координаты отсеченного прямоугольником отрезка: он находит начальные значения для итераций Брезенхема, это xв, yв и e0 (начальная ошибка). Работает нормально, но не учитывается ситуация, когда при вычислении xв в горизонтальном случае, она выпадает из прямоугольного отсечения, то же самое в вертикальном случае, когда точно так же выпадает yв. Если использовать для коррекции итеративные способы, то теряется смысл ускорения Кузьмина (в некоторых случаях, после коррекции, ни один пиксель линии бывает вообще не виден). Вот эту ситуацию и необходимо поправить, естественно, если найдутся умы пересчитать формулу, и позволят не проверять координаты кузьмина дополнительно, это будет большой плюс. |
| Автор: GremlinProg 31.7.2007, 13:48 |
| Все, проблема решена, был недочет в горизонтальном случае, необходимо все же учитывать погрешность при делении, ну и отсечение Сазерленда-Кохена (да и любое другое) порой отсекало видимые фрагменты линии брезенхема, слил три алгоритма в один, расширил его для всех четвертей, получилось неплохо, единственное замечание, конечную точку тоже необходимо просчитывать по Кузьмину, чтобы не терять ни одного пиксела. В целом, работает алгоритм, конечно немного медленнее, чем чистый Брезенхем, но точно, теперь действительно можно одновременно и отсекать и рисовать без потери качества. Поскольку алгоритм отсечения FC (Fast Clipping) Собкова-Поспишила-Янга, с кодированием линий на сегодня самый быстрый для x86, то есть смысл в тройке [Сазерленда-Кохена -> Кузьмин -> Брезенхем] заменить им первый. |
| Автор: GremlinProg 16.8.2007, 19:32 |
| Забыл отметить еще одну деталь. При определении горизонтального или вертикального случая, с помощью векторного произведения, очень часто возникала проблема выхода координаты за пределы прямоугольника, я её решил простой тупой проверкой сазерланда, т.е. вычисляю код после опеределения координаты, а затем, если точка не входит в прямоугольник, пересчитываю координаты. Работает всегда, т. е. если не корректен горизонтальный случай, то корректен вертикальный и наоборот. По крайней мере, сбоев пока не обнаружено, но в ухдшем случае, для одной точки приходится расчитывать оба варианта. демо-пример в приложении. отрезок и прямоугольник можно перемещать мышью: левой - конечные точки , правой - отсечение. красный - брезенхем, зеленый - кузьмин. PS: если проделать то же самое только брезенхемом, за зеленым будет мелькать красный при изменении угла |
| Автор: GremlinProg 23.8.2009, 18:41 |
| открытым текстом исходник не выкладываю, слишком много, прикрепил во вложении это уже несколько устаревшая версия, где расчет обех точек идет в одном направлении отрезка с тех пор я разработал еще две вариации на тему Кузьмина: 1. двунаправленный расчет конечных точек: отрезок обрезается с обеих сторон, этот вариант просто быстрее - меньше костылей, меньше расчетов, 2. кэшируемый вариант: некая виртуальная плоскость разбивается на "квадраты", каждому из которых задается в соответствие физическое окно, (физических квадратов - битмапов, обычно меньше виртуальных) а все линии, частично, либо полностью, задерживаются в некоторой окрестности визуального окна при скроллинге в памяти, позволяя, таким образом , управлять производительностью алгоритма отрисовка линий через всю виртуальную плоскость тут производится так же по кузьмину, просто одним махом вычисляются все пересечения, причем каждая конечная точка одного квадрата является стартовой - другого, т.е. выигрыш уже налицо как руки дойдут, найду, выложу |
| Автор: fsmoke 23.8.2009, 18:50 |
| Огромное спасибо |