Gcode tools разработка внутренних функций

[Nick]

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

Задача #1

Собственный офсет
На данный момент используется офсет от inkscape (тот который dinamyc offset, он отличается от Контур->офсет). Но он часто дает плохие результаты и результат нельзя сразу же обработать. поэтому нужен свой офсет!

Решенные задачи

Пока нет, но мы будем стремиться заполнить этот список по самое не хочу !

[Nick]

Итак оффсет...

Оффсет кривой безье делается, как оказываеься просто:
Берем параметрическую запись и к ней добавляем ее производную умноженную на радиус офсета.

Затем нужно соединить все концы соседних сегментов. Соединять нужно дугами окружностей.

Далее необходимо сделать клиппинг. Для этого необходимо найти все пересечения каждого сегмента получившейся кривой с каждым сегментом кривой.
Эта проблема самая сложная, пересечений у двух сегментов может быть аж до 9 штук. Но ведь кто-то это решил . Можно как вариант прошариться по коду инкскейпа.

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

Итак, как можно отделить решения? Наверняка количество решений зависит от значения первой и второй производных у(t) по х(t). Причем если вторая производная не меняет свой знак, то сегмент не меняет вогнутости => количество точек пересечения уменьшается. Т.е. если мы разобьем сегменты в точках изменения второй производной, то количество возможных точек пересечения должно уменьшится до 4.

[Nick]

Наверняка количество решений зависит от значения первой и второй производных у(t) по х(t). Причем если вторая производная не меняет свой знак, то сегмент не меняет вогнутости => количество точек пересечения уменьшается. Т.е. если мы разобьем сегменты в точках изменения второй производной, то количество возможных точек пересечения должно уменьшится до 4.

Хотя тут тоже не все так просто, y(x) это не функция, т.к. у(х) может иметь несколько значений для разных x ...
Можно рассмотреть поверхность следующего вида и искать ее нули:

Код: Выделить всё

F(t_1,t_2) = sqrt{(x_1(t_1)-x_2(t_2))^2 + (y1_(t_1)-y_2(t_2)^2)}

Формула оффсета проста:

, где P(t) - это искомая кривая. НО есть маленькое "но", такая кривая не всегда будет кривой Безье того-же порядка.....

Код: Выделить всё

{%OMEGA}(%rho, P(t)) = P(t) + %rho{(y'(t), -x'(t))} over {sqrt{x'(t)^2+y'(t)^2} } 

[Nick]

На счет построения оффсета, как я писал выше кривая полученная при помощи упомянутого выражения не будет кривой безье и еоэтому эту кривую нужно найти. При выполнении функции гравировки мы уже искали значения коэффициентов кривой безье по заданным четырем точкам. Этот метод можно применить и здесь, однако остаются вопросы.
1. По заданым четырем точкам мы можем построить только одну кривую. При этом точки должны быть вида (t, x, y), т.е. для заданного t определяем x и y. Исходя из описанной формулы это мы сделать можем. Нужно только определиться с точками t.
2. Что будет если полученные оффсеты в выбранных точках t будут пересекаться (это будет происходить когда радиус кривизны кривой будет меньше радиуса оффсета)?
3. Будет ли полученная кривая искомым отступом?

[Nick]

Итак, начата разработка вспомогательных функций офсета.
1. Пересечение двух кривых Безье.
Реализация выполнена следующим образом :
Контуры разбиваются на сегменты и ищется пересечения всех сегментов друг с другом.
Сначала рекурсивно разбиваем каждый контур на две части и смотрим пересекаются ли bounds каждой из частей, если пересекаются продолжаем разбиение. (если пересекаются контуры то и их баунды пересекаются). Рекурсия продолжается до достижения заданной глубины разбиения (Можно сделать различную глубину для различных контуров).
Затем каждый из конечных кусочков кривых заменяем прямыми отрезками и ищем их пересечения. (Кстати спорный вопрос, может этого делать не нужно т.к. эти отрезки могут не пересекаться, когда контуры будут пересекаться.)
Затем уточняем каждое из полученных пересечений методом Ньютона. (Через уточнение решения системы двух кубических уравнений от двух переменных).

Остается вопрос определения типа точки пересечения - это пересечение или касание.

[Nick]

Теперь оффсет...

Вот, что пока получается:

Осталось всего-то ничего - join и клиппинг .

[Nick]

Итак офсет готов, хотя к нему нужно будет добавить одну оптимизацию. Join тоже готов. Но его нужно протестировать.
Clipping еще дорабатывается. Пересечение и само пересечение уже есть нужно написать процедуруткоторая определяет какие части нужно отрезать, а какие оставить. Завтра буду целые сутки ехать в поезде, может что-нибудь наклепаю.
Попутно несколько усовершенствовал процедуру нахождения расстояния от точки до кривой.
Push и картинки будут когда приеду.

[Nick]

Итак, первые результаты:
21 Контур офсет с шагом 10.
Время выполнения 231 секунда . Многовато ... Но это пока не проводилось никаких оптимизаций!

gcode bezier offset

Ревизия 98

Чуть-чуть готовый офсет

[Nick]

Итак, разработка собственного офсета подходит к концу!!!
Из недостатков:
1. Медленная работа. Но в нашем случае риалтайм не обязателен, поэтому на данный момент можно оставить как есть. Возможно, потом напишем отдельный модуль на си который будет делать офсет заданной кривой гораздо быстрее.
2. Пока не работает с самопересекающимися контурами. Как вариант решения можно разбивать контур в местах самопересечения. Эта задача не совсем тривиальна и поэтому пока не реализована. Возможны случаи, когда кривую не получится разбить на несколько не пересекающихся контуров.
Преимущества по сравнению с существующим:
1. Настраиваемая точность. Хотя на момент тестирования и разработки точность выставляется 0.5, получившийся офсет гораздо точнее инкскейповского офсета.
2. Отсутствие артефактов. Этим обуславливается возросшее время вычисления. Для каждой точки офсета вычисляется расстояние до начальной кривой. Т.к. эта задача алгебраически не решается, то приходится искать расстояние вычислительными методами, которые требуют время.
3. Возможность использовать офсет внутри gcodetools! Теперь мы сможем создавать фаски всего одним нажатием клавиши, также это позволит автоматически делать чистовой проход и т.д.

Что необходимо доделать:
1. Ориентация кривой и ее субконтуров. Необходимо для правильного определения направления офсета.
2. Автоматическое вычисление радиуса офсета.
3. Офсет самопересекающихся кривых.

[Nick]

Done in 425.998970985 sec
Total offsets count 125
На счет отсутствия артефактов я погорячился, они есть, но они внутри обрабатываемой части...

[Nick]

Урааа!!! Я кажется придумал, как избавится от этих артефактов!!!
Они появлялись из-за сложности задания критерия "входит ли субконтур в офест или нет". Сложность заключается в том, что есть много "не точных" вычислений и много аппроксимаций.

С самого начала создаем оффсет сегмента кривой, в положении его начальной и конечной точки мы можем быть уверенны, т.к. они вычисляются алгебраически. Но, положения каждой точки офсета неточно, т.к. это аппроксимация. Также в процессе офсета, сегмент начальной кривой разбивается на более маленькие для достижения большей точности. В точках офсета начала и конца этих маленьких сегментов мы тоже уверенны - они рассчитаны алгебраически.
Далее мы разбиваем полученный офсет на куски всеми точками пересечения офсета сегмента и офсета остальной кривой.
И наконец-то нам нужно определить какой из этих кусков принадлежит офсету, а какой нет (находится ближе чем нужно).
Критерий:
Если у куска есть контрольные точки посередине - проверяем расстояние от контрольных точек до кривой. (оно должно достаточно точно совпадать).
Если у куска нет контрольных точек - тогда проблема. Т.к. он может быть получен из пересечений двух офсетов двух сегментов и не содержать ни одной "точной" точки. Что делать? Увеличивать допуск? Тогда в офсет могут попасть нежелательные сегменты. Не увеличивать, тогда мы можем исключить правильный сегмент.
Вот мое решение:
Делаем обратный офсет точки середины куска (reverse_offset). Он должен оказаться достаточно близко к исходной кривой. Далее находим ближайшую к reverse_offset точку на кривой. И делаем ее офсет (real_offset). real_offset - это достаточно точный офсет кривой в нужной точке. Если расстояние от кривой до real_offset лежит в заданных границах, то кусок часть искомого офсета.

[Nick]

Новые результаты:
1. Изменена функция клиппинга. Большинство ненужных частей отрезается без использования сложных вычислений.
2. Увеличена скорость работы алгоритма.

Вроде, качество офсета изменилось в лучшую сторону.

Итак, несколько результатов офсета:

Осторожно картинки большие от 0,6 до 2 Мб!

Офсет с шагом 1 всего 33 офсета время выполнения 227 сек.

И два офсета с шагом 10 (внутрь и наружу) время выполнения около 20-30 секунд.

100 офсетов с шагом 1 время выполнения 196 секунд.

12 офсетов с шагом 1 за 15 секунд.

[DMexico]

Есть ли в Inkscape или GCT функция которая возвращает среднюю линию между линиями обводки? Сделал вручную, но как-то непрофессионально это.

[Nick]

Есть engraving он делает примерно то же самое, но линия будет идти два раза (туда и обратно) и будет подходить ко всем углам (хотя, это можно настроить)...