В предыдущей статье мы рассказали о «Планоплане», нашем онлайн-планировщике и дизайнере квартир. С небольшим отрывом в опросе победила тема о школьной геометрии в «Планоплане» и Unity3D, о чём с удовольствием и рассказываем.
Если коротко просуммировать наш опыт, оказывается, что уместное использование достаточно простых алгоритмов улучшает продукт в разы. В статье мы решили обойтись без формул и кусков кода, потому что используются несложные алгоритмы. Если некоторые из них всё-таки нужны — пишите в комментариях.
Пересечения стен ищутся очень просто. У каждой стены есть две линии, грубо говоря, внешняя и внутренняя. С помощью решения системы из двух уравнений можно найти точки пересечения каждой пары прямых на плоскости (исключая граничные случаи когда прямые параллельны или угол между ними маленький). Курс алгебры за 7 класс.
Слева видно хорошее пересечение стен. Справа граничный случай, когда точка пересечения стен находится в неприемлемом месте. Пересечения стен определяются в Unity3D динамически, если положение или толщина стен изменяются.
Следующий шаг к реалистичности после расчёта правильных пересечений прямых стен — построение и пересечение кривых стен.
Кривые стены строятся с помощью квадратичных кривых Безье. Алгоритм простой: когда у нас есть две точки (начало и конец стены), мы вручную выбираем третью точку. По этим трем точкам алгоритм может найти любую точку на кривой. Кривые стены состоят из множества блоков центр каждого из которых лежит на этой кривой. На погонный метр стены приходится примерно 10 блоков — число подобрано эмпирически.
Концы стен триангулируются немного по-другому, чтобы обеспечить правильность стыков с другими стенами.
Получается довольно простой меш, который не сильно влияет на производительность.
Сложность такие стены создают в том, что мы пока не придумали как встраивать в них окна, двери, проемы. Изгибать окна и двери в программе можно, но так не бывает в реальной жизни. Зато для построения балконов, различных выступов (часто бывают в современных домах) изогнутые стены подходят отлично.
Применение булевых операций (см. дальше) позволит решить данную проблему. Если есть другие идеи или истории из реальной жизни о проёмах, окнах и дверях в изогнутых стенах — добро пожаловать в комментарии.
Пересечение кривых стен рассчитывается чуть хитрее — и тут надо разобраться с триангуляцией Делоне и генерацией мешей.
Широко известно, что 3D-графика имеет дело с приближением объектов реального мира с помощью треугольников. Кроме того, интуитивно понятно, что любую поверхность можно приблизить треугольниками бесконечным количеством способов. Даже многоугольник с большим количеством вершин можно разбить на треугольники очень большим количеством способов.
Один из наиболее известных способов (курс геометрии за 9 класс) — триангуляция Делоне (названная не в честь абы какого француза, а именем русского математика Бориса Николаевича Делоне).
До использования триангуляции меши генерировались из прямоугольных частей. На примере оконного проёма, генерировался прямоугольник до окна, над и под окном и после окна. Это накладывает определенные ограничения на форму самого окна — для такого метода окно может быть только квадратным.
Было
Стало
В случае с прямоугольным окном эффект неочевиден, но триангуляция Делоне позволила нам использовать различные формы, размеры и положение отверстий в стене.
У нас используется триангуляция с ограничениями. В этом случае поверхность задается двумя типами контуров: внешним — задающим внешние границы, и внутренним — задающим ограничения (или, проще, отверстия). Внутренних контуров может быть несколько.
Как пытливый читатель успел понять к этому разделу, все элементы в проекте, за исключением подготовленной мебели, генерируются в «Планоплане» на лету.
Прямые стены в 2D-режиме генерируются по шести точкам (два конца средней линии стены и четыре вершины четырёхугольника), имеют ширину, длину и высоту.
Кривые стены в 2D-режиме (как мы уже описали выше) генерируются по массиву точек, лежащих на квадратичной кривой Безье, имеют ширину, длину и высоту.
Стены в режиме 3D генерируются на основании данных 2D-стены и высоты стены.
В стенах генерируются отверстия под окна и двери и зашиваются откосами, генерируемыми по контуру отверстия. Могут быть практически любой формы.
Пол и потолок автоматически создаются по точкам, описывающим данную комнату (см. далее про поиск комнат). Используется триангуляция Делоне.
Для генерации контурных элементов (например, плинтусов) используются два контура — сечение и путь.
Задача наших джедаев от школьной геометрии на сегодняшний день — внедрение булевых операций для расчёта пересечения поверхностей в трёхмерном пространстве (например, для кривого зонирования кривых стен). В данный момент булевые операции применяются только для создания рендера квартиры со срезанными стенами, вроде такого.
Вот как это выглядит в теории:
А вот так выглядят текущие разработки на практике.
В будущем планируется повсеместное внедрение булевых операций, что позволит нам совершенно без ограничений расставлять окна, двери (например можно будет легко разместить окно над окном, или окно над дверью, вынести окно в край стены, расположить окно в стыке стен и т. п.). Также это позволит нам создавать отверстия в полу и потолке для реализации лестничных проемов или встраивать такие элементы как раковина в абсолютно любую столешницу, просто вырезая в ней отверстие.
В перспективе планируется реализация размещения окон и дверей непосредственно в 3D-режиме.
На закуску, из несложных алгоритмов, в «Планоплане» реализован автоматический поиск комнат, что позволяет снять с пользователя работу по их ручному выставлению. Например, если пользователь создаёт замкнутый контур из стен, пол и потолок создаются в «Планоплане» автоматически. Это позволяет пользователю строить квартиру «стена за стеной», а не видоизменять базовый квадрат комнаты.
Поиск реализован рекурсивно, на основе связей между точками (стенами) по методу правого обхода.
Наше руководство и Unity-бойцы в лице Антона Jagahee Карпунцова выступят с рассказом о «Планоплане» на CG Event 1 декабря в 14:30 (Москва, Holiday Inn Сокольники, зал «Чистые пруды»). Приходите посмотреть, позадавать вопросы, пообщаться с разработчиками и покрутить в руках Oculus Rift.
На базе выступления на CG Event, в следующей статье цикла расскажем о том, как в «Планоплане» устроен серверный рендеринг изображений пользователей.
Если коротко просуммировать наш опыт, оказывается, что уместное использование достаточно простых алгоритмов улучшает продукт в разы. В статье мы решили обойтись без формул и кусков кода, потому что используются несложные алгоритмы. Если некоторые из них всё-таки нужны — пишите в комментариях.
Правильные пересечения стен, плинтусов и других поверхностей
Пересечения стен ищутся очень просто. У каждой стены есть две линии, грубо говоря, внешняя и внутренняя. С помощью решения системы из двух уравнений можно найти точки пересечения каждой пары прямых на плоскости (исключая граничные случаи когда прямые параллельны или угол между ними маленький). Курс алгебры за 7 класс.
Слева видно хорошее пересечение стен. Справа граничный случай, когда точка пересечения стен находится в неприемлемом месте. Пересечения стен определяются в Unity3D динамически, если положение или толщина стен изменяются.
Кривые стены и проёмы
Следующий шаг к реалистичности после расчёта правильных пересечений прямых стен — построение и пересечение кривых стен.
Кривые стены строятся с помощью квадратичных кривых Безье. Алгоритм простой: когда у нас есть две точки (начало и конец стены), мы вручную выбираем третью точку. По этим трем точкам алгоритм может найти любую точку на кривой. Кривые стены состоят из множества блоков центр каждого из которых лежит на этой кривой. На погонный метр стены приходится примерно 10 блоков — число подобрано эмпирически.
Концы стен триангулируются немного по-другому, чтобы обеспечить правильность стыков с другими стенами.
Получается довольно простой меш, который не сильно влияет на производительность.
Сложность такие стены создают в том, что мы пока не придумали как встраивать в них окна, двери, проемы. Изгибать окна и двери в программе можно, но так не бывает в реальной жизни. Зато для построения балконов, различных выступов (часто бывают в современных домах) изогнутые стены подходят отлично.
Применение булевых операций (см. дальше) позволит решить данную проблему. Если есть другие идеи или истории из реальной жизни о проёмах, окнах и дверях в изогнутых стенах — добро пожаловать в комментарии.
Пересечение кривых стен рассчитывается чуть хитрее — и тут надо разобраться с триангуляцией Делоне и генерацией мешей.
Триангуляция Делоне и фигурные проёмы
Широко известно, что 3D-графика имеет дело с приближением объектов реального мира с помощью треугольников. Кроме того, интуитивно понятно, что любую поверхность можно приблизить треугольниками бесконечным количеством способов. Даже многоугольник с большим количеством вершин можно разбить на треугольники очень большим количеством способов.
Один из наиболее известных способов (курс геометрии за 9 класс) — триангуляция Делоне (названная не в честь абы какого француза, а именем русского математика Бориса Николаевича Делоне).
До использования триангуляции меши генерировались из прямоугольных частей. На примере оконного проёма, генерировался прямоугольник до окна, над и под окном и после окна. Это накладывает определенные ограничения на форму самого окна — для такого метода окно может быть только квадратным.
Было
Стало
В случае с прямоугольным окном эффект неочевиден, но триангуляция Делоне позволила нам использовать различные формы, размеры и положение отверстий в стене.
У нас используется триангуляция с ограничениями. В этом случае поверхность задается двумя типами контуров: внешним — задающим внешние границы, и внутренним — задающим ограничения (или, проще, отверстия). Внутренних контуров может быть несколько.
Процедурная генерация мешей
Как пытливый читатель успел понять к этому разделу, все элементы в проекте, за исключением подготовленной мебели, генерируются в «Планоплане» на лету.
Прямые стены в 2D-режиме генерируются по шести точкам (два конца средней линии стены и четыре вершины четырёхугольника), имеют ширину, длину и высоту.
Кривые стены в 2D-режиме (как мы уже описали выше) генерируются по массиву точек, лежащих на квадратичной кривой Безье, имеют ширину, длину и высоту.
Стены в режиме 3D генерируются на основании данных 2D-стены и высоты стены.
В стенах генерируются отверстия под окна и двери и зашиваются откосами, генерируемыми по контуру отверстия. Могут быть практически любой формы.
Пол и потолок автоматически создаются по точкам, описывающим данную комнату (см. далее про поиск комнат). Используется триангуляция Делоне.
Для генерации контурных элементов (например, плинтусов) используются два контура — сечение и путь.
Вырезание мешей (булевые операции)
Задача наших джедаев от школьной геометрии на сегодняшний день — внедрение булевых операций для расчёта пересечения поверхностей в трёхмерном пространстве (например, для кривого зонирования кривых стен). В данный момент булевые операции применяются только для создания рендера квартиры со срезанными стенами, вроде такого.
Вот как это выглядит в теории:
А вот так выглядят текущие разработки на практике.
В будущем планируется повсеместное внедрение булевых операций, что позволит нам совершенно без ограничений расставлять окна, двери (например можно будет легко разместить окно над окном, или окно над дверью, вынести окно в край стены, расположить окно в стыке стен и т. п.). Также это позволит нам создавать отверстия в полу и потолке для реализации лестничных проемов или встраивать такие элементы как раковина в абсолютно любую столешницу, просто вырезая в ней отверстие.
В перспективе планируется реализация размещения окон и дверей непосредственно в 3D-режиме.
Поиск комнат
На закуску, из несложных алгоритмов, в «Планоплане» реализован автоматический поиск комнат, что позволяет снять с пользователя работу по их ручному выставлению. Например, если пользователь создаёт замкнутый контур из стен, пол и потолок создаются в «Планоплане» автоматически. Это позволяет пользователю строить квартиру «стена за стеной», а не видоизменять базовый квадрат комнаты.
Поиск реализован рекурсивно, на основе связей между точками (стенами) по методу правого обхода.
8 шагов с картинками
1. Cтроим стены и точки.
2. Начинаем поиск замкнутого контура с одной из стен.
3. Исходя из связей между точками, переходим к самой правой (по углам) стене у второй точки выбранной стены.
4. Далее так и идём, пока не уткнемся в начальную стену.
5. Создаём комнату.
6. Переходим к поиску следующей комнаты. Там, как видно, есть заковырка с тупиковыми стенами. Мы просто находим стену, у которой нет продолжения, и помечаем ее тупиковой. Возвращаемся на шаг назад и ищем следующую правую стену, исключая тупиковые.
Ещё шаг назад.
7. Идём дальше…
… пока не замкнём контур опять.
8. На этом поиск завершён. Все контуры найдены.
Стоит сказать о паре нюансов.
2. Начинаем поиск замкнутого контура с одной из стен.
3. Исходя из связей между точками, переходим к самой правой (по углам) стене у второй точки выбранной стены.
4. Далее так и идём, пока не уткнемся в начальную стену.
5. Создаём комнату.
6. Переходим к поиску следующей комнаты. Там, как видно, есть заковырка с тупиковыми стенами. Мы просто находим стену, у которой нет продолжения, и помечаем ее тупиковой. Возвращаемся на шаг назад и ищем следующую правую стену, исключая тупиковые.
Ещё шаг назад.
7. Идём дальше…
… пока не замкнём контур опять.
8. На этом поиск завершён. Все контуры найдены.
Стоит сказать о паре нюансов.
- Мы перебираем стены и исключаем из дальнейшего перебора те, что являются тупиковыми, а также те, что уже состоят в двух замкнутых контурах.
- В ходе поиска мы находим и внешний контур, который включает в себя все комнаты. Его также исключаем.
Хочу узнать больше!
Наше руководство и Unity-бойцы в лице Антона Jagahee Карпунцова выступят с рассказом о «Планоплане» на CG Event 1 декабря в 14:30 (Москва, Holiday Inn Сокольники, зал «Чистые пруды»). Приходите посмотреть, позадавать вопросы, пообщаться с разработчиками и покрутить в руках Oculus Rift.
На базе выступления на CG Event, в следующей статье цикла расскажем о том, как в «Планоплане» устроен серверный рендеринг изображений пользователей.
