Не знаю, только ли мне это свойственно, но я испытываю какой-то первобытную радость, когда вижу сложные паттерны, возникающие из сред, кажущихся хаотичными.
Представьте галереи колоний муравьёв, невероятно идеальные шестиугольники пчелиных сот или прожилки листьев. Никаких архитекторов или чертежей, лишь набор простых правил, приводящий к созданию великолепных узоров. Не знаю почему, но наблюдение за такими структурами всегда вызывает положительные ощущения.
Люди тоже их создают. Для меня один из самых удивительных паттернов, которые мы придумали — это дороги.
Иногда я представляю инопланетян из далёких галактик, которые откроют Землю уже спустя много времени после нашего ухода. Леса, снова занятые природой, города, превратившиеся в развалины; однако между ними всё равно заметен слабый паттерн — сеть дорог. Мне нравится думать, что они будут чувствовать то же самое, что и я, когда смотрю на природные паттерны: «Ого, кто-то действительно это продумал».
Градостроительные симуляторы и их дороги
Должен сказать, что дороги восхищали меня с детства.
До сих пор помню, как в возрасте шести-семи лет впервые играл в SimCity 2000. Я понял не особо многое и не знал, что такое зонирование, налоги и спрос. Но дороги сразу меня восхитили.
Я считаю, что дороги — основа каждого градостроительного симулятора. Ткань, из которой создаются города. С того времени я играл почти во все градостроительные симуляторы, действие которых происходит в наше время. Тем временем я начал замечать дороги в реальном мире. Исследовать их более детально.
Развязки. Перекрёстки с круговым движением. Эстакады. Сужения полос. Замечал каждую мелочь.
Хотя в каждой новой игре происходит шаг вперёд по сравнению с предыдущей, что-то всё равно продолжало казаться неестественным.
В SimCity 4 появились подъёмы и диагональные дороги. В SimCity 2013 добавились извилистые дороги. Затем пришла Cities: Skylines, дав нам огромную свободу. В ней можно было размещать дороги свободно и объединять их в перекрёстки под любыми углами, строить эстакады на разных высотах, создавая безумные, но реалистичные развязки. Думаю, это стало самым крупным прорывом.
Но меня всё равно что-то продолжало напрягать. Въезды на шоссе оставались нереалистично резкими или вихляющими, скоростные полосы в некоторых точках изгибались слишком сильно, а радиусы углов на перекрёстках выглядели странно.
Просто посмотрите на это. Наверно, такие кошмары снятся проектировщикам автострад.
А затем появились моды. И моды изменили всё. Увлечённое сообщество дало новую степень свободы. Можно было строить почти всё: идеальные сужающиеся полосы, реалистичную разметку и плавные переходы. Это полностью изменило игру. Особенно я горжусь своим пятиполосным турбоперекрёстком:
Но даже после этого моды не казались полностью естественными. Они всё ещё были ограничены исходной системой игры.
Cities: Skylines 2 подняла планку ещё выше: полосы и разметка стали ещё реалистичнее. Думаю, сегодня неопытный глаз не сможет отличить игру от реальности.
Тогда я перестал искать и начал пытаться понять, как проектируют дороги инженеры и как их кодируют разработчики игр.
Однако потом я столкнулся с фундаментальной проблемой, лежащей в самом основании этой задачи. Она сводится к тому, что знает и любит каждый разработчик:
Кривые Безье
Если вы разрабатываете проекты в Unity/Unreal или пробовали творить в практически любом векторном графическом редакторе, то они вам хорошо известны. Кривые Безье — изящный, интуитивно понятный и невероятно мощный инструмент для создания плавных интерполяций между двумя точками с учётом какого-то направления движения (касательной).
Кажется, что так и должны вести дороги, правда? Разумеется, разработчики игр решили, что эти кривые подойдут идеально.
Должен признать, в них есть своя красота. Но под их поверхностью скрывается неприятная правда.
Когда кривые Безье не справляются с задачей
Дело в том, что форма дорог в реальной жизни определяется непреложным фактором: колёсными осями автомобилей. Как бы вы ни вели машину, расстояние между левым и правым колесом остаётся постоянным. Это можно заметить по следам шин на песке или в снегу. Это две идеально параллельные траектории, постоянно находящиеся на одном расстоянии и сохраняющие постоянную форму кривой.
Машины не ездят по абстрактным кривым Безье, а перемещаются по воображаемым рельсам.
Проблема кривых Безье заключается в том, что при смещении они не сохраняют форму и кривизну.
При плавных поворотах они выглядят неплохо, но когда изгибы становятся более резкими, их математика начинает давать сбой. Выражаясь математически, смещение кривой Безье не остаётся кривой Безье.
Когда игровые движки пытаются генерировать дорожную сеть на основе кривой Безье, при достаточно острых углах геометрия часто разваливается. Степень изгиба внутреннего угла отличается от степени внешнего. Это создаёт сдавливание, самопересекающуюся геометрию.
Вот самый наглядный пример того, как кривые Безье подводят нас в крайних ситуациях.
Подведём итог: у кривых Безье нет ограничений. Та свобода, которую они обеспечивают, и становится их ахиллесовой пятой. Реальные дороги проектируются с учётом ограничений реального движения. Траектория движения автомобиля не может волшебным образом пересечь сама себя.
Детсадовская математика
Хорошо, допустим, но что же позволяет сохранить параллельность? Если вы уже выпустились из детского сада, то вам это понятие знакомо: это КРУГ.
Он обладает почти волшебным свойством: как бы мы его ни смещали, в результате всё равно получится круговая дуга, идеально параллельная исходной. Это очень красиво.
Отказ от кривых Безье в пользу круговых дуг даёт нам ещё один неожиданный бонус. Для процедурного создания перекрёстков движку приходится много раз за кадр выполнять множество операций вычислений пересечения кривой и кривой. Пересечение двух кривых Безье — достаточно сложная конструкция. С одной стороны, нужно найти корни многочлена, применить итеративные численные методы, алгоритм де Кастельжо + вычисление ограничивающих прямоугольников и множество проверок схождения. Для круговых дуг же нужна всего лишь простая формула, вычисляемая за O(1).
Сшивая вместе круговые дуги разного радиуса, можно создавать любые форму, придерживаясь при этом строгих принципов проектирования.
Следующий уровень
Но на этом история не заканчивается. У круговых дуг тоже есть проблемы (о, нет, не может быть). Проблема окружностей в инфраструктуре заключается в том, что они обладают постоянной кривизной. Это значит, что при входе в круговую кривую из прямой линии, поперечная сила резко увеличивается с нуля до фиксированного постоянного значения (определяемого радиусом окружности). Если бы вы находились в машине или поезде, входящем на высокой скорости в такую кривую, то чувствовали бы себя ужасно.
Инженерам-строителям нужно учитывать и это. Но тогда какая же кривая сохраняет параллельность при смещении и в то же время обладает плавно увеличивающейся кривизной?
Представляю вашему вниманию переходные кривые, самая известная из которых — это клотоида.
Клотоида постепенно повышает кривизну с увеличением расстояния. Сначала она почти прямая, а потом постепенно закручивается всё сильнее. Руль машины поворачивается плавно. Силы нарастают естественным образом, а тело водителя и пассажиров едва замечает переход.
Эти кривые обеспечивают комфортную поездку на высоких скоростях благодаря сохранению параллельных смещений и непрерывным изменениям кривизны.
Но в то же время они — настоящий математический кошмар. Дифференциальная геометрия. Интегралы... Наверно, именно поэтому большинство разработчиков игр не осмеливаются даже браться за них.
Но это нормально.
По городским улицам транспорт движется медленно. Для перекрёстков городских дорог круговые арки — вполне приемлемый выбор.
Почему я создал собственную систему дорог
Важно ли то, о чём я рассуждал выше? Важно ли 99 процентам игроков в градостроительные симуляторы, какую форму будет иметь радиус угла на перекрёстке? Скорее всего, нет. Так зачем заморачиваться?
Во-первых, из любопытства. Как любой нерд, одержимый мельчайшими деталями какой-то узкой темы, я просто хотел понять, как бы сам реализовал эту систему. Мне хотелось подвергнуть сомнению статус кво.
Во-вторых, даже если успешные игры и не рендерят дороги правильно, они всё равно на световые года опережают те решения, которые может найти онлайн инди-разработчик. Связанные с этой темой уториалы и ассеты выглядят очень печально. Лично мне наскучили сетки и мне просто хотелось создать более качественное решение, чтобы поделиться им со всеми, кто решит разработать градостроительный симулятор.
Структуры данных дорог
Слой модели данных
В разработке ПО я часто вижу, как люди тратят слишком мало времени на представление данных в своих программах. Я считаю, что модель данных настолько фундаментальна для любого ПО, что может быть причиной его успеха или провала.
Бесчисленное количество раз я встречал такой подход: «Сейчас быстренько реализую что-нибудь, чтобы система развивалась, а по ходу дела выполню рефакторинг и буду добавлять новое». Мне нравится воспринимать модель данных, как чертежи строительного проекта. Необходимо всё тщательно продумывать ещё до начала. Нельзя просто изменить планы уже в процессе строительства, не пойдя при этом на серьёзные компромиссы.
Моя цель заключалась в разработке модели данных, которая буквально может описать любую дорожную инфраструктуру, которая есть в реальной жизни. Возникает такой вопрос: как можно представить дороги в виде данных? Давайте начнём с простейшего способа.
Сетка
Наиболее примитивный способ описания дорог — это, конечно, сетка. Я упоминаю её лишь для полноты информации; очевидно, что это больше стилизованное представление, нежели реалистичное.
В дорожных системах на основе сеток каждая ячейка или пустая, или содержит дорогу, или перекрёсток. В некоторых играх разработчики идут дальше и добавляют разные углы, чтобы можно было создавать диагональные дороги или подъёмы, но внутри представление остаётся таким же: в каждом тайле хранится информация о том, как должен выглядеть сегмент дороги.
Посмотрите на эту развязку-клевер из TheoTown; должен признать, что это красиво.
Представление на основе узлов
Перейдём к первому представлению данных, которое я начал рассматривать серьёзно: систему на основе узлов. Первой моей игрой, в которой геометрия дорог процедурно отрисовывалась на основе узлов, стала Cities: Skylines 1. В те времена меня поразила та степень свободы и настраиваемости, которую обеспечивала эта модель.
Если вы выбираете лучший способ хранения данных дорог, то это решение может показаться очевидным. Когда студенты изучают графы на курсе Computer Science, их обычно объясняют на примере дорог. Принцип прост: рёбра — это сегменты дороги, а узлы — перекрёстки. Зачем должно понадобиться что-то ещё?
Данные для этой модели просты: у каждого узла есть координата центра и список входящих рёбер. В рёбрах хранится информация о ширине дороги, количестве полос и другие сведения о сегменте дороги. Новые узлы создаются в местах пересечений двух сегментов дорог. Движок генерирует геометрию, соединяя полосы каждого входящего сегмента с полосами других сегментов.
Неочевидная проблема: полосы
На первый взгляд, всё работает замечательно. И в большинстве сценариев это действительно так. Проблема такого подхода становится очевиднее в пограничных сценариях, например, на развилках и слияниях полос автострад.
Рассмотрим пример трёхполосного шоссе из CS1, где внешняя полоса сворачивает на съезд.
В реальности левые линии должны продолжаться прямо, а внешняя правая отделиться. Если дорога описывается только её центральной линией, то эта информация теряется. Система видит только, что два сегмента соединяются в узле, и из этого должна решить, как соединяются полосы. Информация о том, какая полоса должна продолжаться, сливаться или расходиться, отсутствует, потому что это изначально не кодировалось в представлении данных.
Кроме того, существует и геометрическое ограничение. Чтобы при такой системе полосы плавно сливались на перекрёстках, связанные сегменты должны иметь достаточное смещение от центра узла. Из-за этого два перекрёстка невозможно разместить на произвольно близком расстоянии друг от друга. Иными словами, между узлами должен находиться сегмент минимальной длины. Вот как начинает ломаться геометрия, когда в CS2 пытаешься присоединить узкую дорогу рядом с большим перекрёстком:
Обходные решения
Описанные мной проблемы были решены талантливыми хобби-разработчиками из сообщества CS1. Например, мод Node Controller обеспечивает возможность подробного управления свойствами узла, что позволяет вручную настраивать соединения и выравнивания сегментов. Честно говоря, когда я играл в игру, этот мод для меня изменил всё. По сути, он позволяет изменять центральную линию дороги, чтобы её ребро выравнивалось с ребром другого сегмента дороги. Это исправляло перекрёстки, но ломало выравнивание в отдалении от них.
В Cities: Skylines II разработчики устранили многие из этих недостатков, добавив поверх базового представления узлов слои более умных инструментов. Они внедрили возможность выравнивания новых сегментов непосредственно по существующим полосам, что позволяло создавать гораздо более реалистичные автострады. Однако, несмотря на эти косметические улучшения, внутренняя логика на основе узлов сохранялась, и мы можем видеть её ограничения в определённых пограничных случаях:
Недостающее звено
После того, как я поэкспериментировал со множеством разных подходов, мне стало очевидно, что проблема заключалась не в геометрии, а в информации. Данных о центральной точке узла и о соединяющих его рёбрах недостаточно для описания дорожной сети, учитывающей согласование полос и сложные сценарии.
Я люблю архитектуру и особенно городское планирование. Иногда без какой-либо причины я изучаю планы новых проектов застройки моего города, отправленных на утверждение. Разглядывая их, я заметил, что в них часто бывают диаграммы поперечного сечения дорог.
Они называются профилями дорог и выглядят примерно так:
И тогда меня озарило: что, если вместо узлов с центральными точками в качестве источника истины мы будем использовать информацию о расположении самих полос в пространстве? Если в явном виде указать, где должна находиться каждая полоса по обоим концам сегмента дороги, то больше не будет неоднозначностей о том, как они должны соединяться при образовании перекрёстков.
Профили
Когда я говорил выше, что в системе, над которой я работаю, не используются узлы, я был не совсем точен. На самом деле, в системе есть узлы, но применяются они контринтуитивным образом.
Узел — это не физический перекрёсток, а ребро — не физический сегмент дороги. Физические элементы (сегменты и перекрёстки) задаются узлами. Они соединяются друг с другом рёбрами, представляющими собой линии нулевой ширины, которые задают поперечное сечение дороги в определённой точке. Эти профили — абстрактные описания, не имеющие визуального представления, они служат исключительно для задания дорожной сети и хранения данных полос.
Если вкратце, раньше соответствие было таким:
Узлы = перекрёстки
Рёбра = сегменты дороги
а стало таким:
Узлы = все физические элементы (сегменты и перекрёстки)
Рёбра = воображаемые линии поперечного сечения.
Мы храним дорогу не в виде центральной линии с какой-то шириной между двумя дорогами, а сохраняем профили в точках соединений. В каждом профиле содержится вся информация о поперечном сечении дороги в конкретной точке соединения: количество полос, ширина полос, типы полос (автомобильная, разделительная, пешеходная дорожка, велосипедная и так далее).
При создании перекрёстка соединением разных профилей непрерывность полос обеспечивается намеренно. Перекрёстки и сегменты дороги генерируются созданием плавных переходов между профилями.
Вот визуализация этого:
Кодирование этих данных для каждого профиля позволяет моделировать любую сложную дорожную инфраструктуру. Вот, как накладывается эта модель на турбоперекрёсток из реального мира:
Изящное решение
Кто-то может теперь задаться вопросом: зачем нужно такое контринтуитивное представление, если в решение на основе узлов можно добавить немного логики и оно тоже будет работать? Причина заключается в изяществе. Я считаю решение изящным, если оно работает без специальной обработки всех возможных случаев.
Если вы разработчик игр, представьте разницу между углами Эйлера и кватернионами. И те, и другие выражают поворот объекта. Углы Эйлера подходят в большинстве случаев, но ломаются в пограничном (блокировка осей), а кватернионы очень контринтуитивны, но обеспечивают универсально надёжное и изящное решение.
Изобретаем велосипед?
Я был горд, когда наконец пришёл к этому решению, но несколько человек сразу же сообщили мне, что эта задача уже была решена в автомобилестроение при помощи спецификации ASAM OpenDrive. Это гораздо более сложная система, но концептуально довольно близкая в том смысле, что структура полос задаётся явно, а не определяется по центральной линии. Внутри перекрёстка каждое движение поворота представлено в виде отдельной соединяющейся дороги. Узнав о том, что такая система уже существует, я немного смутился, но в конечном итоге остался доволен тем, что самостоятельно дошёл до правильного решения. Наверняка после дополнительной работы можно создать отображение этих моделей данных друг в друга без потерь.
Все дороги строятся из одной простой геометрии
Хорошей аналогией для профилей могут служить кривые Безье. Для хранения кривой Безье не нужно сохранять всю кривую в явном виде, достаточно опорных точек и положений касательных. Благодаря паре формул можно воссоздать контур, выполнив интерполяцию между опорными точками.
В моей системе представление на основе профилей работает аналогичным образом. Профили — это контрольная информация, а геометрия, определяющая контур дороги — это интерполированный результат этих профилей.
Ниже я расскажу, как при помощи зелёных профилей генерирую плавные параллельные контуры.
Проблема геометрии
В начале статьи я объяснил, что стало причиной моего исследования: оказалось, что большинство разработчиков игр использует неподходящий инструмент; они рендерят дороги, расширяя кривую Безье центральной линии. Я же изначально знал, что для создания формы дороги хочу использовать только отрезки и круговые дуги.
Определившись с этими требованиями, можно свести задачу к геометрической:
Дано: два профиля с произвольными позициями и направлениями. Как соединить их соответствующие конечные точки при помощи плавных параллельных дуг?
Благодаря простому геометрическому свойству окружностей мы можем сразу упростить задачу. Равномерно расставленные вдоль радиуса точки при повороте относительно того же центра образуют концентрические дуги. Если наши профили имеют одинаковую длину, нам достаточно вычислить контур только для одной пары соответствующих конечных точек. Применив то же построение вдоль профиля, мы естественным образом получим параллельные контуры.
Следовательно, задача сводится к следующей:
Пусть даны две точки A и B с векторами направлений
и
. Найти круговую дугу, соединяющую A c B и касательную к
Одной дуги недостаточно
Наверно, вы догадались об этом, даже не приступив к решению. Две произвольные точки, у каждой из которых есть заданный вектор касательной, не всегда могут быть соединены одной круговой дугой, касательной к обоим векторам. На самом деле, это возможно только в особом оптимальном случае: когда точки лежат на одной окружности.
Может показаться, что мы зашли в тупик. Сформулированные нами ограничения просто нельзя соблюсти. Тем не менее, в реальной жизни дороги, заданные только дугами и отрезками, всё-таки существуют. Решение заключается в том, чтобы снизить строгость ограничений, позволив каждой дуге иметь отрезок, идущий до точки пересечения с касательной прямой.
Геометрическое решение
Построение происходит так:
Берём две конечные точки (обозначим их A и B).
Из каждой точки проводим прямую в направлении, в котором должна продолжаться дорога (перпендикулярно профилю). Я буду называть их продолжающие линии.
Обозначим точку пересечения этих прямых C.
Теперь у нас есть два отрезка, CA и CB, длина которых в общем случае различна. Допустим, что CB длиннее CA.
Начав из B и двигаясь по продолжающей линии к C, мы выбираем такую новую точку M, что CM=CA.
Далее проводим через M прямую, перпендикулярную второй продолжающей линии, и прямую через A, перпендикулярную первой.
Эти два перпендикуляра пересекаются в новой точке O.
Теорема о касательной и радиусе гласит, что радиус всегда перпендикулярен касательной в точке касания. То есть если OM и OA — это радиусы одной окружности, то окружность будет касаться продолжающих линий в M и A.
Нам осталось лишь доказать, что OM=OA.
Доказать это достаточно просто. Рассмотрим прямоугольные треугольники OCM и OCA с общей гипотенузой OC. Поскольку мы выбрали M так, что CM=CA, можно сделать вывод, что треугольники равны и что OM=OA. Это доказывает, что O — центр окружности, идущей через M и A.
Следовательно, окончательным контуром будет дуга из A в M, а которой следует отрезок из M в B.
Сначала прямая, потом дуга, вот и весь секрет.
Наверно, прочитавшие это инженеры скажут, что это просто скругление. Да, я не изобрёл ничего нового, это называется построением скругления между двумя прямыми. Но с одной особенностью: точка касания всегда фиксирована и мы вычисляем вторую.
Интерполяция профилей
Итак, теперь, когда мы можем создавать плавный контур между двумя конечными точками в заданном направлении, можно вернуться и исходной задаче: соединению исходного и целевого профилей.
В большинстве случаев эта задача решается очень просто.
Если два профиля одинаковы по длине и их продолжающие линии пересекаются удобным образом, то для соединения профилей целиком достаточно применить одно и то же построение к их соответствующим концам. Иными словами, мы решаем одну и ту же геометрическую задачу с обоих сторон поперечного сечения дороги и два её края естественным образом будут параллельны.
То есть в случае самых простых сегментов дороги всё сводится к повторению одной и той же операции между начальным и конечным профилями. Вот, как это происходит графически:
Следующая задача
Разумеется, не каждая допустимая пара профилей расположена под таким удобным углом, что их продолжающие линии пересекаются и могут образовывать переход.
Следующая задача заключается в поиске решения для других пограничных случаев. Описанный выше способ не сработает, если продолжающие линии не пересекаются.
Такой сценарий вполне возможен: дороги не всегда изгибаются, иногда они смещаются.
Иными словами, в один момент автомобиль может быть выровнен колёсами по AB и ему нужно выполнить плавный переход к CD. На практике это означает, что сначала нужно сделать поворот в одну сторону, потом в другую, создав S-образный путь.
Для создания такого перехода недостаточно одной дуги, требуется как минимум две, поэтому нам нужно новое решение.
Промежуточный профиль
Я вспомнил, что как раз такой сдвиг видел, когда играл со своей дочкой в железные дороги LEGO.
Соединение двух дуговых деталей с поворотами в разные стороны создаёт красивый S-образный переход при сдвиге.
Это привело меня к выводу: задачу необязательно решать за один этап, нужно всего лишь найти способ соединения одних и тех же базовых строительных блоков.
Нужно найти промежуточный профиль, который позволит разбить задачу на две части, решение которых при помощи прямых и дуг мне уже известно.
Возвращаемся к кривым?
Как я и говорил, кривые плохо подходят в качестве основного описания формы дороги, однако они хороши в одном: нахождении нужных позиции и ориентации этого промежуточного профиля.
Лучше всего здесь подойдёт сплайн Эрмита между центром исходного и целевого профилей.
Сплайн Эрмита получает на входе две точки A,B и два вектора касательных , и выполняет плавную интерполяцию между ними. При t=0 мы получим начальную точку, при t=1 — конечную. При любом другом промежуточном t мы получим плавный контур, соответствующий указанным направлениям касательных в обеих конечных точках.
Теоретически, «идеальное» место для вставки промежуточного профиля — это точка перегиба, в которой кривая меняет изгиб. На самом деле, есть сложный математический способ нахождения точки вычислением производных сплайна первого и второго порядка и решением многочлена третьей степени. Если вам любопытно, подробности приведены в сноске к статье.
Но я ведь говорил, что наши вычисления будут простыми? На практике, такая точность нам не нужна.
При удобных величинах и (примерно 1,0-1,5 величины расстояния между центральными точками) простого вычисления сплайна Эрмита при t=0,5 достаточно для получения достаточно хорошей аппроксимации местонахождения перегиба.
Вычислив P(0,5), мы получим центральную точку профиля. (Где P(t) — это сплайн Эрмита в параметрическом виде.)
Если для функции декартова пространства первая производная даёт нам наклон графика при определённом значении x, то для двухмерной параметрической кривой первая производная даёт нам вектор скорости: движение точки с изменением t. Если считать t временем, то она даст нам одновременно и скорость, и направление движения.
В нашем случае важно лишь направление, то есть касательная. Просто вычислив P’(0,5), мы получим направление касательной к кривой в этой точке.
С точки зрения программирования, P и P‘ — это просто формулы, вычисляемые за O(1).
Особые случаи
Теперь мы умеем обрабатывать самые полезные соединения профилей, но всё равно остаётся пара особых сценариев, о которых стоит поговорить.
Первый: продолжающие линии параллельны и идут в одном направлении.
Построить соединение в этом случае очень просто: с одной стороны используем полуокружность, а затем прямой сегмент.
Последнее семейство пограничных случаев: когда продолжающие линии не пересекаются так, чтобы можно было выполнить построение при помощи одного промежуточного профиля.
Я уверен в том, что, приложив достаточные усилия, можно создать для таких сценариев общее решение, однако иногда необходимо признать пределы возможностей инструмента и встроить ограничения, не позволяющие пользователю оказываться в подобных ситуациях.
Встраиваем ограничения
Вместо того, чтобы стремиться реализовать все возможные комбинации, я решил встроить ограничения непосредственно в инструмент прокладки дорог.
Если разделить плоскость пополам при помощи бесконечной прямой исходного профиля, то в случае, когда пользователь попробует поместить следующий профиль за полуплоскостью, мы принудительно делаем так, чтобы ориентация этого нового профиля соответствовала ориентации исходного. Это сводит систему к одному из рассмотренных выше более простых случаев, которые мы уже научились соединять надёжным образом.
Что дальше?
У нас уже есть базовый строительный блок дорожной сети: способ плавного соединения двух профилей одними отрезками и дугами.
Это позволяет нам прокладывать дороги любой формы.
Следующим шагом станет динамическое создание перекрёстков и связывание этих строительных блоков в более сложные сети.
Этим мы займёмся в следующем посте.
Сноски
-
Чтобы понять, как математически найти эту точку перегиба, нужно подумать о том, что нам говорят о природе этой точки первая и вторая производные параметрической кривой. Первая производная P′(t) сообщает нам направление движения, а вторая P′′(t) говорит, как направление меняется со временем; иными словами, как поворачивает кривая (её кривизну).
Можно провести аналогию: P′(t) — это направление, в котором светят фары, а P′′(t) — направление, в котором поворачивает руль. Точка перегиба — это момент, когда они совпадут; перед сменой направления кривая на мгновение приостанавливается.
Чтобы определить, выровнены ли два вектора, можно вычислить их векторное произведение. Если оно равно 0, то они или имеют одно направление, или идут в противоположных. То есть с математической точки зрения, поиск точки перегиба эквивалентен решению уравнения P′(t) ⨯ P′′(t) = 0