Всем привет! Мы — команда Smart vision в Домклик, и мы предлагаем нашим клиентам различные инструменты для помощи в подборе жилья, чтобы им было как можно комфортнее. Один из таких инструментов — автоматическая расстановка мебели, чтобы наши пользователи смогли посмотреть на трёхмерную квартиру с обстановкой и лучше понимали размеры помещения. Пока программа доступна в тестовом контуре внутри экосистемы Домклик. Мы не рассматриваем этот алгоритм в качестве инструмента для идеальной расстановки мебели, это лишь помощь клиенту в расстановке мебели для дальнейшей работы с ней.

Есть много статей о решении этой задачи: с применением GAN, который генерирует на плане помещения цветовую область для размещения мебели; с помощью классических методов на основе набора правил; или с помощью более редких графовых методов. Но все существующие методы объединяет то, что все они или не реализованы (либо находятся в закрытом доступе), или не учитывают, например, окна и двери, а также тип помещения (гостиная, спальня, детская, кухня, санузел и т.д.). Мы постарались избавиться от этих недостатков в своём инструменте.

С чем предстоит работать?

Что у нас есть для начала: 

• Типы помещений:  коридор,  гостиная, спальня и т.д. 

• Набор точек по каждому типу в двумерной системе координат: point[x,y]. 

• Объекты мебели в виде ID, который связывает двумерный и трёхмерный объект. 

• И подробная методичка от дизайнеров с набором мебели для каждого типа помещения в зависимости от площади комнат.

Первый возникший вопрос: с какими объектами мебели будем работать, с двумерными или трёхмерными? И второй, более фундаментальный: как мы будем решать задачу, с помощью deep learning или методов на основе правил (rules based; кто-то скажет что это куча if-ов)? Мы решили использовать двумерные объекты в формате SVG, потому что с ними проще работать, они представлены набором точек и занимают гораздо меньше памяти для их хранения. А при ответе на второй вопрос мы воспользовались советом «если можно не использовать сетки, то лучше их не использовать» и решили остановиться на методе, основанном на правилах, хотя в дальнейшем не стали исключать возможность использования  методов на основе машинного обучения.

Структура алгоритма

1. Выбираем помещение для расстановки мебели.

2. Разбиваем его на подпространства — условные секторы для расстановки мебели.

3. Находим пересечения окон и дверей с подпространствами, чтобы понять, к каким из них те относятся, ведь в дальнейшем мебель не должна закрывать эти проёмы.

4. Добавляем мебель в помещение, по умолчанию она встаёт в центр.

5. Затем раскидываем мебель по подпространствам, рассчитываем её координаты относительно подпространств. Раскидываем «жадно»: берём один объект, находим для него подпространство и перемещаем в него, берём следующий, и так для каждого объекта. При этом учитываем окна и двери, чтобы мебель их не закрывала 

6. Смещаем мебель к стенам основного помещения, не обращая внимание на подпространства.

7. Расставим зависимые объекты: мебель, расположение которой зависит от другого объекта, например, прикроватная тумбочка.

8. Ищем коллизии между объектами и окнами и дверями.

9. Если коллизий нет, то оставляем текущее расположение мебели; если они есть, то разрешаем их смещением объектов друг относительно друга.

Теперь рассмотрим ключевые этапы алгоритма.

Разделение помещения на подпространства

Делим на квадраты и обязательно нумеруем их. Кстати, мы также рассматривали разделение по алгоритму binary space partitioning, его использовал Джон Кармак в движке DOOM.

Выбор подпространства для мебели

Получили пронумерованную схему деления помещения на подпространства:

В зависимости от типа помещения и его площади предполагается использовать уникальный набор мебели. Информацию о дальнейшем ей расположении берём из руководства дизайнеров (спасибо им за подробный документ). А также у нас есть ряд правил, по которым те или иные типы мебели должны располагаться в помещении относительно друг друга. Например, диван в гостиной должен быть напротив телевизора на расстоянии не менее 700 мм. Напомню, что необходимо учитывать двери и окна, чтобы мебель их не закрывала.

Теперь у нас есть информация о подпространствах, типах мебели и расположении окон и дверей относительно подпространств. Мы можем составить несколько сценариев расположения мебели в подпространстве в зависимости от расположения дверей и окон. Например:

Спасибо школьной геометрии! Мы использовали композиции параллельных переносов на ориентированный вектор. Что нам для этого необходимо?

Рассмотрим пример перемещения обычного прямоугольного дивана. Мы хотим переставить его из центра помещения, куда он попал по умолчанию, в выбранное для него подпространство (ячейку). Представляем диван как bounding box — четыре точки в двумерном пространстве с координатами x,y — и находим его центр, то есть центроид дивана. Берём выбранное подпространство — это тоже набор точек, в большинстве случаев составляющих прямоугольник — и находим его центр. Теперь у нас есть два центроида, дивана и подпространства. Из них получаем направленный вектор от дивана к подпространству и делаем параллельный перенос на вектор. 

Таким образом мы перемещаем объекты в центр подпространств и поворачиваем их. Изначально вся мебель ориентирована лицом  направлении минуса по оси y, а после первого перемещения объекта мебель поворачивается «спиной» к стене.

Теперь необходимо подвинуть диван к стене. Находим минимальное расстояние от него до основного пространства (часть помещения, не разбитая на подпространства), на выходе получаем две точки: одна на границе дивана, другая — на границе пространства. Далее опять параллельный перенос на вектор, и так со всей мебелью.

Но проблема в том, что если мы помещаем объекты в подпространства и двигаем их один раз к ближайшим стенам, то они легко могут пересекаться между собой, например диван со шкафом. Хорошо, что все объекты представлены в виде bounding box и мы можем легко найти пересечения с помощью библиотеки shapely, предварительно сделав из bbox полигон и применив метод intersection. Также при размещении объектов учитываем:

1. регламентированную ширину прохода между мебелью;

2. размеры мебели относительно площади помещения;

3. мебель не должна закрывать окна и двери.

Расстановка зависимых объектов

Рассмотрим пример с прикроватной тумбочкой и кроватью. После перемещения кровати в её конечное местоположение нужно к ней поставить тумбочку. Сама кровать располагается в определённом подпространстве. Мы можем выбрать соседние свободные ячейки и поместить туда прикроватную тумбочку, после чего подвинуть её до кровати (по описанной выше процедуре, только уже относительно самой кровати), и ещё один раз двигаем тумбочку, теперь до ближайшей стены, чтобы она плотно прилегала к стене и изголовью кровати.

Обработка коллизий объектов мебели, дверей и окон

Начнем с классификации дверей и окон в конкретном помещении. Например, в гостиной может быть три типа дверей и один — окон:

• входная дверь, она обычно располагается между коридором и комнатой;

• межкомнатные двери, ведущие в другие помещения;

• балконные двери. 

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

Поэтому когда мы разбиваем основное пространство на части, мы учитываем расположение дверей и окон относительно этих подпространств, таким образом исключая риски расположения объектов мебели, которые будут закрывать двери и окна. Но этого мало, пришлось добавить ещё один круг проверок на коллизии после расстановки мебели в помещении. Находим пересечения объектов с дверями и окнами и двигаем их, пока пересечения не исчезнут; а если это невозможно, то просто удаляем объект. Протестировав такой подход, мы поняли, что обычно удаляются «рабочие столы», а смещаются «шкафы для одежды». 

Результат

Итак, что у получается в итоге. На вход приходит набор мебели, представленный точками и ID объектов, а также помещения, которые отличаются по функциональному назначению. На выходе из алгоритма получаем ID объектов мебели с обновлёнными точками, которые расположены относительно помещения. Затем алгоритм связывает мебель по ID с её трёхмерным представлением и добавляет в трёхмерную модель помещения, сделанную из чертежа квартиры.

P.S.

Не так давно Nvidia выпустила свой алгоритм автоматической расстановки мебели в трёхмерном пространстве на основе нейронных сетей, который выглядить очень круто, но не учитывает окна и двери и не предлагает предварительно обученных моделей.