Обработка сплайнов и кривых Безье

[VLarin]

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

Тема слита из двух. Dan_Te

[незваный гость]

VLarin писал(а):

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

Лучше бы отдельную тему начать.

Вас интересуют пересечения двухмерных сплайнов? одномерных? С вычислительной точки зрения или теоретической?

[VLarin]

To незванный гость:
Интересует двумерный случай и численное решение. Просто интересен сам факт, и если Вы с этим сталкивались, то как реализовали?

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

[незваный гость]

Я по прежнему не очень понимаю, что мешает пересчитать перпендикуляры в момент изменения сплайна, и запомнить перпендикуляры. Есть, конечно, одна хитрость, а именно, прилипание контрольных точек сплайна к перпендикуляру к этому же сплайну (в процессе редактирования). На самом деле, такой пересчет достаточно быстр. (И я не уверен, что сделан качественно. Например, найдет ли он все перпендикуляры из точки к сплайну [типа фасолины].)

Если честно, то я сплайны не люблю. После некоторого опыта работы, я склоняюсь к выводу, что Adobe была права, пойдя по пути кривых Безье. При сшивке двух кривых достаточно колинеарности направляющих векторов. Сплайн-сшивка накладывает более сложное условие. В результате, требуется больше сегментов для решения той же задачи. А лишние сегменты не бесплатны со многих точек зрения. При растризации, например, округление создает артефакты. При обработке (прилипание ли, построение перпендикуляров ли, редактирование кривых ли - все едино) - дополнительную сложность (времени обработки). Плюс - нелокальность изменений. Даже вставка точки (разбиение сегмента на два), по моему (пишу по памяти, могу быть не прав), не может быть сделана точно при редактировании сплайна. Все это усугубляется, если работать в целочисленных координатах. Я, надо признаться, немало восхищаюсь Adobe. Действительно творческая компания, с глубоким R&D и крепкой деловой хваткой.

Я надеюсь, что Вы поясните подробнее, если я ответил не на Ваш Вопрос.

P.S. Может все-таки стоит отделиться в тему типа "обработка сплайнов и кривых Безье"?

[VLarin]

В процессе создания графиков и работе с геометрией столкнулся с необходимостью быстрого вычисления точек пересечения перпендикуляров и касательных из произвольных точек со сплайнами. Если кто сталкивался с такой задачей, интересно узнать как Вы это решили. Интересуют алгоритмы быстрого вычиление точек пересечения со сплайнами.

Трудность задачи сводится к тому, что точки пересечения нужно определять динамически при перемещении курсора мыши, связи с чем заранее эти точки определить нельзя. При этом, как видно из ACAD'a и ряда других программ они это решили, и при перемещении мышки они довольно шустро определяют эти точки на ходу.

[VLarin]

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

А так задача следующая: определение значений на графике при перещения курсора мыши, так называемый "курсор данных". Самая грамотная привязка к кривым - это прявязка к точкам пересечения перпендикуляров из текущей точки на сплайны. Это поволяет определять значения как для почти вертикальных графиков, так и почти для горизонтальных.
При этом многие деятели в связи со сложностью такого подхода зачастую используют текущую координату Х курсора мыши, но при этом, пробежать по почти вертикальной кривой не получится.

Обычно число сплайнов, предстваляющих одну кривую на графике, зависит от числа точек и обычно может быть порядка 100-1000. На графике может быть несколько кривых. Для определения кривой, к которой нужно привязаться, нужно определить длинны отрезков перпендикуляров, и найти самый короткий. И уже для этого перпендикуляра определить значения, отрисовать их и все прочее. В итоге получаем громадное количество вычислений при перемещений курсора. Но как я смотрю, например в проге AWR Microwave Office, они с этим справились.

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

Цитата:

P.S. Может все-таки стоит отделиться в тему типа "обработка сплайнов и кривых Безье"?

http://dxdy.ru/viewtopic.php?t=857&sid=ffddd284c30e8ed7027d58e02ebbaaa8

[незваный гость]

Совсем я тупой. Точка перпендикуляра - это как я понимаю [локально] ближайшая точка сплайна к заданной точке. Т.е. Ваша задача суть найти точку сплайна ближайшую к данной?

Эта задача, в общем, решаться может примерно так: каждый сегмент сплайна отдельно. Сегмент сплайна - это кривая Безье (и мы имеем ее определяющий четырехугольник). Во-первых, большинство из них "хорошие" (то есть, без точек перегиба, петель, остриев, и т.п.). Плохие можно заранее отметить, дабы каждый раз в суете мышинной не проверять. Во вторых, легко построить перпендикуляры к концам (перпендикуляры к соответсвующим отрезкам четырехугольника). Эти перпендикуляры зададут "веер". Если точка находиться вне этого веера, то перпендикуляра внутри нет. Это отсекает бОльшую часть сегментов сплайна. Обычно остается два-три, для которых можно искать решение как угодно, например методом Ньютона (Я бы, правда, записал уравнение квадрата расстояния от точки до точки сегмента сплайна, и искал бы нули производной. Всё уравнение пятой степени, а не девятой). "Плохие" сегменты можно нарезать на несколько "хороших" (опять же, в момент редактирования).

Коли именно ближайшая точка интересует, процесс отсечения может быть продолжен (а может быть, с этого следует начинать). А именно, если объемлющий многоугольник одного сегмента лежит дальше, чем объемлющий многоугольник другого, то первый можно не рассматривать. (Правда, тут надо быть аккуратным. Именно многоугольник, а не вершины.)

Когда точка найдена (параметр точки) - остальное дело нехитрой техники. Крошим сегмент на два алгорифмом де Кастельжо, и имеем касательные. Ну а перпендикуляр к прямой - это круто.

Если мутно, скажите, попробую нарисовать... Рисование время жрет, так что если Вам не нжно - лень...

[VLarin]

Цитата:

Эти перпендикуляры зададут "веер"

- не совсем понятно.

И попутно такой вопрос - выделение сплайнов - здесь, как по классике, нужно к точке, указанной мышкой добавить некоторую DELTA (5 - 10 пикселей). То есть опять приходим к определению наименьшей дистанции до сплайна, лежащей в диапазоне [-DELTA, DELTA]. И по другому ни как?

Просто чего-чего, а в сплайнах я не особо, и какой грамотной литературы почитать по работе со сплайнами в CAD'ах - не знаю:)).

[незваный гость]

Перпендикуляры образуют "веер". В силу непрерывной дифференциируемости кривой Безье, они заметают некоторую часть плоскости (отдельные прямые нарисованы для примера). Нас интересуют точки справа от левой и слева от правой... Принадлежность точки к полуплоскости проверяется в координатах ну очень быстро. (Если нужен допуск, то граничные прямые можно слегка подвинуть).

[незваный гость]

VLarin писал(а):

выделение сплайнов - здесь, как по классике, нужно к точке, указанной мышкой добавить некоторую DELTA (5 - 10 пикселей). То есть опять приходим к определению наименьшей дистанции до сплайна, лежащей в диапазоне [-DELTA, DELTA]. И по другому ни как?

Литературы мало, поскольку никто не заинтересован писать. "AutoCAD летает". И что, AutoDesk заинтересована учить своих конкурентов, как оно, чтобы летало? А, если заключает контракт с университетом, наложит такие условия на публикации... Результат - старье, ничего не найти.

Для прилипния/выделения не очень важно точное определение мин дистанции . Как правило, на таком малом расстояниии от точки находится один-два-три сегмента. Их можно быстро представить в виде ломанной, и прокрутить по ломанной. Ну, а потом уж уточнить (обычно, и это не очень нужно). Поскольку быстрое рисование - процесс важный, то преобразование Безье в ломаную высоко оптимзировано, а потому преобразование + пробег работают быстро.

Интересно, что отсечку сегментов проще делать не по четырехугольнику, а по прямоугольнику, включающему четырехугольник. Быстрее, хотя и грубо.

[VLarin]

Цитата:

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

Здесь не все так просто. Точка, из которой можно провести перпендикуляр (с учетом того, что его длина не фиксирована), может быть где угодно.


При этом может быть и такое

[VLarin]

Пока это рисовал, покапался в ACAD - у него есть и сплайны, и Безье. При этом в явном виде рисуются только сплайны.
Отрисовывает сплайны линиями, из-за чего при масштабировании ерунда полная получается (он так и арки рисует, ускоряют типа и на специальные алгоритмы рисования сплайнов они забили).
При обрезке сплайна крошит его на Безье-curve.

[незваный гость]

VLarin писал(а):

Здесь не все так просто. Точка, из которой можно провести перпендикуляр (с учетом того, что его длина не фиксирована), может быть где угодно.

Я упрощал, и упростил слишком сильно. Да, Вы правы. Более точно критерий звучит как "справа от одной, слева от другой прямой." Черт здесь не очень страшен, поскольку речь идет просто о знаках соответсвующих векторных произведений.

VLarin писал(а):

При этом может быть и такое

Может - это просто пример "плохой" кривой. Ее следует нарезать на две-три перед поиском точек экстремума (по точкам перегиба). Тогда все будет работать.

Есть такая статья: Approximating Cubic Bezier Curves in Flash MX - By Timothée Groleau. Мне, в общем, понравилась больше всего (из того, что я видел). Там в конце и ссылки есть.

[незваный гость]

Еще одна интересная задача:
Предположим, у нас есть кривая Безье. Мы вставили точку, разбив ее на две. Подумав некоторое время (предполагая, что нет undo), мы пытаемся удалить эту точку. По идее, должна получиться исходна кривая. А вот как это сделать? (При разбивке моги возникнуть, например, ошибки округления). В более ощем случае, есть пара соединенных к.Б., которые надо аппроксимировать одной... желательно, с минимальным отклонением.

[незваный гость]

VLarin писал(а):

Здесь не все так просто. Точка, из которой можно провести перпендикуляр (с учетом того, что его длина не фиксирована), может быть где угодно.

Вы еще правее, чем мое предыдущее сообщение

Черная-то точка - Бог с ней, там все более или менее понятно. Но вот красная гадит фундаментально, и, по моему, существует почти всегда. Интересно!