Способ и система построения навигационных маршрутов в трехмерной модели виртуального тура

Изобретение относится к области компьютерной техники, в частности, к методам построения навигационных маршрутов для пользователя в виртуальной среде. Техническим результатом является повышение точности построения навигационных маршрутов на основе окружающего пространства для пользователя в трехмерной модели виртуального тура. Способ построения навигационных маршрутов для пользователя в трехмерной модели виртуального тура, содержащий этапы, на которых: выполняют съемку окружающего пространства с помощью 3D-камеры, передают данные съемки окружающего пространства с камеры на сервер, на котором формируется трехмерная модель виртуального тура, которая содержит трехмерные объекты, соответствующие объектам окружающего пространства области съемки, получают набор точек с заданными координатами трёхмерной модели объекта виртуального тура, причем каждая точка соответствует точке расположения камеры на объекте, и формируют по меньшей мере два параллельных луча в трехмерной модели объекта из первой точки к точкам из набора точек, которые характеризуют месторасположения камеры на объекте. 2 н.п. ф-лы, 7 ил.

 

ОБЛАСТЬ ТЕХНИКИ

[0001] Настоящее техническое решение относится к области компьютерной техники, в частности, к методам построения навигационных маршрутов для пользователя в виртуальной среде, такой как, например, трехмерная модель виртуального тура.

УРОВЕНЬ ТЕХНИКИ

[0002] Виртуальный тур представляет собой способ реалистичного отображения трехмерного многоэлементного пространства на средстве пользователя, которым может выступать компьютерное устройство (компьютер, планшет или смартфон) или средство виртуальной реальности. Элементами виртуального тура, как правило, являются сферические панорамы, соединенные между собой интерактивными ссылками-переходами (также точки перехода или хотспотами). Виртуальные туры могут также включать цилиндрические панорамы, виртуальные 3D-объекты, обыкновенные фотографии, видео, звук и т.д. При этом панорамы в виртуальном туре имеют привязку к карте по координатам места съемки и ориентированы по сторонам света.

[0003] Иными словами, виртуальный тур является общим обозначением для трехмерной модели окружения, сформированной с помощью нескольких сферических панорам, а также облаков точек, получаемых с помощью лазерной съемки Лидаром (англ. Lidar - Light Detection and Ranging), связанных в единый объект для отображения с помощью точек перехода, по которым в процессе просмотра можно виртуально «перемещаться». В виртуальные туры могут включаться и другие интерактивные элементы: всплывающие информационные окна, поясняющие надписи, графически оформленные клавиши управления и т.п.

[0004] В связи с этим, построение навигационных маршрутов между точками перехода для пользователя является неотъемлемой частью процесса создания виртуального тура. Так, функциональные возможности навигации, доступные пользователю при перемещении по виртуальному туру, во многом определяют отображаемые пользователю элементы трехмерной модели окружения, что для некоторых типов виртуальных туров, таких как, виртуальные туры по недвижимости, является ключевой особенностью. Кроме того, сложный и/или запутанный маршрут, построенный по точкам навигации (точки перехода) может привести к тому, что пользователь не сфокусирует свое внимание на некоторых

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

[0005] Так, одним из примеров такой технологии, является технология, описанная в патенте США № US 2007/198178 A1 (TRIMBY MARTIN W, et al.), опубл. 23.08.2007, в которой раскрывается способ построения маршрута между точками виртуального тура с учетом препятствий, расположенных в сцене указанного виртуального тура.

[0006] Недостатком такого рода решений является низкая эффективность построения навигационных маршрутов для пользователя ввиду отсутствия возможности построения маршрута в зависимости от высоты и типа препятствия. Кроме того, такого рода решения не предполагают возможность сокращения точек навигации, отображаемых пользователю виртуального тура, что может приводить к высокой плотности однотипных точек, которые будут перекрывать элементы виртуального тура и, как следствие, приводить к неэффективной навигации пользователя по такому туру.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[0007] Заявленное решение решает техническую проблему эффективного построения навигационных маршрутов для пользователя по виртуальному туру.

[0008] Технический результат заключается в повышении эффективности построения навигационных маршрутов для пользователя в трехмерной модели виртуального тура.

[0009] В предпочтительном варианте осуществления заявленного решения заявлен способ построения навигационных маршрутов для пользователя в трехмерной модели виртуального тура, выполняющийся по меньшей мере одним процессором, и содержащий этапы, на которых:

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

b. формируют граф достижимости из полученного набора точек и выбирают первую точку из набора точек в качестве начальной точки маршрута пользователя;

c. формируют по меньшей мере два параллельных луча из первой точки к точкам из набора точек, полученного на этапе а), причем указанные лучи расположены на разной высоте относительно координаты первой точки;

d. формируют ребра графа достижимости между всеми точками, которых достиг по меньшей мере один выпущенный луч;

e. итеративно повторяют этапы c)-d) для каждой точки из набора точек;

f. формируют для каждой точки из набора точек по меньшей мере один путь навигации, причем по меньшей мере одному пути навигации соответствует ребро графа достижимости между двумя точками;

g. осуществляют построение всех возможных навигационных маршрутов по виртуальному туру для пользователя на основе сформированных путей навигации.

[0010] Заявленное решение также осуществляется с помощью системы построения навигационных маршрутов для пользователя в трехмерной модели виртуального тура, которая содержит по меньшей мере один процессор, функционально связанный с по меньшей мере одной памятью, хранящей машиночитаемые инструкции, которые при их выполнении процессором реализуют вышеуказанный способ.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0011] Фиг. 1 иллюстрирует блок-схему способа построения навигационного маршрута пользователя в трехмерной модели виртуального тура.

[0012] Фиг. 2 иллюстрирует общую схему построения виртуального тура.

[0013] Фиг. 3 иллюстрирует пример процесса съемки с помощью 3D-камеры.

[0014] Фиг. 4 иллюстрирует пример сформированных путей навигации.

[0015] Фиг. 5-6 иллюстрируют примеры формирования путей навигации между точками навигации.

[0016] Фиг. 7 иллюстрирует пример общего вида элементов вычислительной системы, которая обеспечивает реализацию заявленного решения.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

[0017] Заявленное техническое решение предлагает новый подход, обеспечивающий повышение эффективности построения навигационных маршрутов для пользователя в виртуальном туре за счет добавления точек навигации в указанный маршрут с учетом особенностей высоты расположения самих точек и высоты элементов трехмерной модели, которые создают препятствия между соединяемыми точками. Кроме того, заявленное решение также обеспечивает возможность сокращения точек навигации, отображаемых пользователю виртуального тура, что, как следствие, снижает плотность отображаемых точек в трехмерной модели и повышает скорость отображения виртуального тура на устройстве пользователя.

[0018] На Фиг. 1 представлена блок схема способа построения навигационных маршрутов для пользователя в трехмерной модели виртуального тура (100), который раскрыт поэтапно более подробно ниже. Указанный способ (100) заключается в выполнении этапов, направленных на обработку различных цифровых данных, полученных с 3D-камеры (240). Обработка, как правило, выполняется с помощью элементов системы построения навигационных маршрутов для пользователя в виртуальном туре (210), представленной, например, в виде сервера, содержащего процессор, графический процессор (GPU), вычислительный модуль и т.д., функционально связанный с по меньшей мере одной памятью, которая хранит машиночитаемые инструкции, которые при их выполнении процессором реализуют способ (100). Более подробно элементы системы (210) раскрыты на Фиг. 7.

[0019] На этапе (110) выполняется получение набора точек с заданными координатами трехмерной модели объекта виртуального тура, причем каждая точка соответствует точке расположения камеры на объекте.

[0020] На Фиг. 2 представлена общая схема взаимодействия пользователя с виртуальным туром. Генерация виртуального тура (200) осуществляется системой (210), к которой подключаются пользователи (220) с помощью различного вида вычислительных устройств (221-223). Система (210) может представлять собой, например, сервер, облачный сервер, кластер серверов и т.д. В качестве устройств могут выступать, например, смартфон, компьютер, ноутбук, планшет, смарт ТВ, средство виртуальной реальности и прочие устройства, которые функционально могут воспроизводить и формировать интерфейс для пользовательского взаимодействия с виртуальным туром (200), независимо от принципа его отображения (дисплей устройства, виртуальная реальность) и взаимодействия с объектами внутри тура (с помощью средств ввода или контроллеров, предназначенных для виртуальной реальности).

[0021] Система (210) представляет собой стандартное вычислительное компьютерное устройство и может являться как сервером или серверным кластером, так и облачным сервером. Основная задача системы (210) осуществлять обработку получаемых с 3D-камеры (240) данных для генерирования виртуальных туров (200) и построения навигационных маршрутов в таких турах в соответствии с заявленным способом (100). Так, система (210), например, сервер, может генерировать виртуальный тур (200) путем обработки данных (облака точек, фотопанорамы, изображения), поступающих со специализированной 3D-камеры (240) и осуществлять дальнейшие этапы способа (100) для построения маршрута для пользователя. Кроме того, система (210) выполнена с

возможностью осуществлять обработку данных для предоставления виртуальных туров (200) для передачи на пользовательские устройства (220).

[0022] Обмен информацией между пользователями (220) и системой (210) осуществляется посредством канала передачи данных (230), который представляет собой глобальную сеть «Интернет». Протокол реализации канала передачи данных (230) может выбираться из любого известного типа протоколов, таких как: LAN, WAN, PAN, WLAN, IEEE 802.11, GSM и т.п. Соответствующий протокол и тип подключения конкретного устройства (221-223) к системе (210) определяется исходя из технического воплощения такого типа устройства и соответствующего аппаратного оснащения для выполнения связи с сетью «Интернет».

[0023] В качестве 3D-камеры (240) для съемки трехмерных виртуальных туров (200) может применяться, например, 3D-камера FilinCam V6/V7/X1 и др. 3D-камера 3D-камера (240) предназначена для съемки помещений и открытых пространств для дальнейшего создания их фотореалистичных цифровых моделей и виртуальных туров. Процесс съемки включает сбор и предварительную обработку сырых данных с 3D-камеры (240), которая также содержит по меньшей мере: вычислительный модуль (процессор или микроконтроллер), память, лидар, акселлерометр датчик IMU и энкодер (датчик угла поворота), которые необходимы для формирования набора данных для последующего формирования виртуальных туров (200). Управление камерой (240) осуществляется через программное приложение, установленное на мобильном устройстве оператора, например, планшете, смартфоне или ноутбуке. По окончании съемки полученные данные выгружаются с 3D-камеры (240) в систему (210), где происходит их хранение, обработка, создание 3D-моделей отсканированного пространства, виртуальных туров (200) и построение навигационных маршрутов для пользователя по указанным турам. Готовые виртуальные туры (200), со сгенерированными возможными навигационными маршрутами для пользователя далее могут предоставляться пользователям (220), путем получения доступа вычислительным устройством пользователя (221-223) по каналу передачи данных (230) к указанной системе.

[0024] Соответственно, после создания 3D-модели отсканированного пространства, строится навигационный маршрут для пользователя по указанной модели. В качестве набора точек, которые соответствуют точкам навигации по виртуальному туру, на этапе (110), система (210) получает точки с заданными координатами в формате (х, у, z), которые являются координатами точки расположения камеры (240) на объекте, которому соответствует построенная 3D-модель. Так, координаты точки навигации в трехмерной модели, соответствующие расположению камеры в пространстве могут быть получены из

метаданных снимка, который был сделан камерой (240) в процессе съемки объекта для последующего построения на его основе виртуального труа (200).

[0025] Рассмотрим более подробно процесс получения координат каждой точки из набора точек.

[0026] На Фиг. 3 представлен пример процесса съемки области с помощью 3D-камеры для последующего построения на его основе виртуального труа (200). Процесс съемки начинается с установки камеры (240), закрепленной на штативе, в начальную точку съемки (точки 1-6 на Фиг. 3). Камера (240) совершает полный оборот вокруг оси, сканируя окружающее пространство лидаром и несколько раз останавливаясь, чтобы выполнить серию фотоснимков. В результате формируется так называемый "свип" (от англ. Sweep), т.е. набор данных, состоящий из нескольких HDR-снимков, лидарного облака точек и метаданных.

[0027] Пример данных, хранимых в свипе.

- 3 серии по 6 или 7 (в зависимости от выбранного режима) снимков с камеры (140), которые используются для создания HDR-изображений;

- Набор срезов лидара для создания облака точек;

- Кватернионы и углы отклонения камеры (240) от горизонта на момент начала и окончания съемки свипа, рассчитанные на основе данных акселерометра и гироскопа IMU;

- Данные энкодера (временные метки, углы поворота камеры).

- Метаданные (например, режим съемки свипа: разрешение съемки, время и прочее).

[0028] После получения данных в рамках съемки первого свипа в точке №1 камера (240) перемещается в новую точку съемки (например, точка №2) и выполняется съемку следующего свипа. Набор отснятых свипов, приведенный к единой системе координат, называется "сценой".

[0029] Как показано на Фиг. 3, свипы в сцене всегда организованы в древовидный ациклический граф с единственным начальным узлом. Для каждого свипа в сцене, кроме первого, определен так называемый "родительский" свип. По умолчанию родительским считается последний снятый свип, но при необходимости родительским свипом может быть назначен любой из отснятых свипов. Например, на Фиг. 3 родительским для свипа №4 является не свип №3, как было бы назначено по умолчанию, а свип №2.

[0030] Каждый свип имеет свою систему координат, которая совпадает с системой координат 3D-камеры (240) на момент начала съемки данного свипа. Система координат первого свипа также служит системой координат сцены. Таким образом, чтобы построить

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

[0031] Для этого используется алгоритм привязки, который анализирует облака точек и фотопанорамы двух соседних (т.е. соединенных одним ребром графа) свипов в дереве, ищет совпадающие участки, на их основе определяет взаимное расположение и ориентацию этих свипов в сцене и рассчитывает матрицу перехода между ними.

[0032] Алгоритм привязки рассчитывает матрицы перехода T_ij для каждой пары соседних свипов S_i и S_j. Чтобы перевести облако точек P_i свипа S_i в систему координат свипа S_j, достаточно умножить его на T_ij.

Здесь и далее используется следующая нотация:

• S_i - свип с номером i. Например, S₃ - свип №3.

• P_i облако точек свипа S_i в собственной системе координат. Например, Р₃ - облако точек свипа №3.

• P_i^j облако точек свипа S_i, переведенное в систему координат свипа S_j. Например, Р₃⁵ - облако точек свипа №3 в системе координат свипа №5.

• T_ij - матрица перехода, служащая для преобразования облака точек свипа S_i в систему координат свипа S_j. Например, Т₃₅ матрица перехода, переводящая облако точек Р₃ в Р₃⁵.

[0033] Чтобы перевести облако точек P_j свипа S_j в систему координат свипа S_i, достаточно умножить это облако точек на матрицу Τ_ji, обратную к T_ij.

[0034] Если свипы не являются соседними в дереве, задача разделяется на несколько последовательных шагов. Например, чтобы на Фиг. 1 перевести облако точек свипа S₆ в систему координат свипа S₁, его следует сначала перевести в систему координат свипа S₅, затем S₂, и наконец S₁. Для этого необходимо последовательно умножить облако точек свипа S₆ на матрицы перехода Т₆₅, Т₅₂ и Т₂₁:

Или, более кратко:

[0035] Следует отметить, что древовидная структура графа гарантирует единственность пути между любыми двумя свипами в сцене. Таким образом, чтобы привести все свипы к единой системе координат, на графе необходимо определить единственно возможный путь от каждого свипа до начального свипа №1 и последовательно применять умножение на соответствующие матрицы перехода. В результате этой процедуры формируется сцена, содержащая все отснятые панорамы и облака точек в единой системе координат, что позволяет определять координаты каждой точки из набора точек.

[0036] Возвращаясь к этапу (110), для построения всех возможных навигационных маршрутов, т.е. для нахождения возможных путей навигации между всеми точками навигации, система (210), как было описано выше, получает координаты каждой точки из набора точек.

[0037] Навигационным маршрутом может являться, например, перемещение пользователя по заданным точкам навигации в виртуальном туре. Так, при просмотре виртуального тура с использованием компьютера навигационный маршрут может включать в себя манипулирование устройством управления курсором, таким как мышь или трекпад, и/или нажатие клавиш клавиатуры, для перемещения из одной точки навигации, в которой осуществляется отображение элементов виртуального тура, соответствующих объектам в реальном мире, к другой точке навигации. Кроме того, при использовании гарнитуры VR перемещение по навигационному маршруту может включать направление взгляда, движение головы или ручного контроллера в определенном направлении с последующим выполнением действия, запускающего процесс перемещения пользователя к точке навигации. Действие может представлять взаимодействие с элементом управления на гарнитуре, на портативном устройстве и т.д.

[0038] Набор точек навигации - это визуальные индикаторы, отображаемые пользователю в виртуальном туре (200) в которые пользователь может перемещаться для путешествия по указанному туру и, соответственно, осуществлять просмотр элементов виртуального тура, отображенных для конкретной точки. Как указывалось выше, точки навигации соответствуют координатам камеры (240), из которых осуществлялось сканирование объекта для последующего создания трехмерной модели виртуального тура (200). Точки навигации могут принимать различные формы, например, точки навигации могут отображаться как круги, сферы, флажки и т.д., в определенных координатах (х, у, z) виртуального тура (200). Кроме того, указанные точки также могут иметь различный размер.

[0039] Как было указано выше, точки навигации, как правило, соответствуют позициям захвата изображений с камеры (240), на основе которых строилась 3D-модель виртуального тура (200). Так, некоторые точки навигации, соответствующие позициям камеры (240), могут находиться близко к различным препятствиям, таким как стены, клумбы, столешницы и другие элементы виртуального тура. Виртуальный тур (200) может иметь множество зон, например, комнат или других функциональных пространств, отделенных друг от друга препятствиями. Так, трехмерная модель виртуального тура (200) может включать в себя несколько комнат, которые отделены между собой различными препятствиями. В каждой комнате расположена по меньшей мере одна точка навигации, из которой пользователю доступен просмотр окружающего пространства. Для возможности пользователя последовательно перемещаться между указанными точками навигации с посещением всех комнат, указанные точки должны быть соединены между собой в навигационный маршрут пользователя. При этом маршрут между точками строится только при прямой видимости точек в 3D модели. Указанная особенность необходима для осуществления плавного перехода между элементами (например, комнатами) виртуального тура, чтобы исключить дезориентацию пользователя в пространстве, а также повысить реалистичность погружения пользователя в виртуальный тур. Кроме того, отображение точек, находящихся за препятствием, выраженным элементом виртуального тура (например, стена), может привести к тому, что указанная точка будет перекрывать другие элементы, расположенные на указанном препятствии, что также является критичным для определенных типов виртуального тура (туры по недвижимости).

[0040] Таким образом, на указанном этапе (110), происходит получение набора точек с заданными координатами (х, у, z) трехмерной модели объекта виртуального тура (200) (точки навигации), причем каждая точка соответствует точке расположения камеры (240) на объекте для последующего определения всех возможных навигационных маршрутов перемещения пользователя между указанными точками.

[0041] Далее способ (100) переходит к этапу (120).

[0042] На этапе (120) формируют граф достижимости из полученного набора точек и выбирают первую точку из набора точек в качестве начальной точки маршрута пользователя.

[0043] В теории графов, достижимость относится к способности получения пути от одной вершины графа к другой. Вершина (точка навигации) может достичь другой вершины (другой точки навигации), если существует последовательность смежных вершин (т.е. путей навигации), начинающаяся с первой вершины и заканчивающийся второй вершины, которую необходимо достичь. Более подробно, сведения, раскрывающие понятие

графа достижимости раскрыты в уровне техники, например, доступном по ссылке: https://mmass.rn/lighting/dostizhimost-otnoshenie-dostizhimosti-otnoshenie-dostizhimosti-dlya/

[0044] Следовательно, для построения навигационных маршрутов в виртуальном туре (200), требуется определить все возможные пути навигации между указанными точками навигации. Для этого, из полученного на этапе (110) набора точек, формируется ориентированный граф, где, соответственно, каждая точка из набора точек является вершиной указанного графа. Стоит отметить, что в качестве начальной точки может быть выбрана как случайная точка, так и точка, соответствующая начальной позиции в виртуальном туре, например, позиции камеры перед входной дверью в виртуальном туре по недвижимости. Указанный граф, на данном этапе еще не содержит ребер, т.е. является не соединенным, что интерпретируется как отсутствие путей между вершинами графа.

[0045] Граф, состоящий из точек навигации может храниться в памяти системы (210) и программно управляться указанной системой (210) как структура данных, подходящая для представления графа. Предпочтительно структура данных графа имеет элементы структуры данных, представляющие узлы графа, и элементы структуры данных. Элементы структуры данных для узлов графа могут включать в себя информацию, идентифицирующую соответствующие точки навигации, которые представляют узлы. Такая узловая информация может включать в себя информацию, идентифицирующую соответствующие точки навигации, и/или координаты, идентифицирующие местоположения соответствующих точек навигации. Например, координаты могут идентифицировать местоположения в трехмерном координатном пространстве трехмерной модели, представляющей пространственные измерения моделируемой реальной среды. Элементы структуры данных ребер графа могут связывать (например, указателями, ссылкой или идентификаторами) элементы структуры данных узлов.

[0046] Основной особенностью построения ребер графа, которые интерпретируются как возможный путь навигации между соседними точками навигации, является требование к обеспечению прямой видимости между точками навигации в координатной сетке трехмерной модели виртуального тура. Как упоминалось выше, при построении реалистичного маршрута для пользователя, пользователь должен иметь возможность перемещаться по трехмерной модели виртуального тура также, как указанный пользователь перемещался бы по реальному объекту, на основе которого была создана указанная трехмерная модель. Для решения указанной проблемы, в известном уровне техники, были разработаны методики, которые основываются на построении маршрута для пользователя с учетом препятствий, имеющихся в трехмерной модели виртуального тура (стена, и т.д.). Указанные методики построены на принципе рейкастинга (от англ. Ray casting), см.

например: https://ru.wikipedia.org/wiki/Ray_casting. Однако указанные методики могут приводить к таким ситуациям, когда луч, выпущенный из одной точке к другой, не достигает точки, хотя в действительности, проход между указанными точками существует, что соответственно отражается на эффективности построения маршрута и, как следствие, может привести к невозможности посещения пользователем такой точки (ввиду исключения ее из маршрута, как недостижимую). Заявленное решение призвано решить указанную проблему.

[0047] Для решения вышеописанной проблемы и построения высокоэффективного и полного маршрута для пользователя, способ (100) переходит к этапам (130-140).

[0048] На этапе (140) выполняется определение достижимости между всеми соседними вершинами графа. Для этого на этапе (130) в трехмерной модели виртуального тура формируются по меньшей мере два параллельных луча из первой точки навигации к остальным точкам навигации из набора точек, полученного на этапе (110), причем указанные лучи расположены на разной высоте относительно координаты первой точки. Т.е. указанный этап (130) определяет возможность соединения вершин графа между собой для дальнейшего определения возможных маршрутов навигации. При достижении по меньшей мере одного луча, выпущенного из первой точки во вторую точку, результат может быть занесен в память системы (210), например, в виде таблицы, для последующего принятия решения о соединении указанных точек в графе. Указанный этап выполняется в автоматизированном режиме системой (210) в момент реализации способа (100). Таким образом, возможность соединения точек навигации (формирование ребра графа между указанными точками) может быть записана в двумерную таблицу. Например, возможность соединения двух точек может быть записана в ячейке, соответствующей двум позициям точек. В некоторых вариантах осуществления возможность подключения может быть записана как двоичное число, где «1» соответствует «соединению», а «0» - «отсутствию соединения».

[0049] Рассмотрим указанные этапы (130-140) более подробно на примере, показанном на Фиг. 5. На Фиг. 5 представлена схематическая карта трехмерной модели виртуального тура, где точки навигации (501, 502) являются точками перемещения пользователя по виртуальному туру. Для определения возможности добавления ребра в графе достижимости между точками навигации (501, 502) (этап (140)), система (210) получает координаты каждой точки в указанной трехмерной модели и осуществляет этап (130).

[0050] Так как при создании 3D-модели камера может устанавливаться в произвольные места сканируемого объекта, может возникнуть ситуация, когда точки навигации расположены в одном объекте (комната и т.д.), однако не имеют прямой видимости между

друг другом. При этом в реальном мире существует свободный проход между указанными точками, лестница на возвышение и т.д. При использовании известных из уровня техники подходов такие точки не будут иметь путь навигации, т.е. не будут соединены ребром в графе достижимости, что, в случае отсутствия других путей к точке, приведет к невозможности посещения пользователем указанной точки. Для решения указанной проблемы был предложен подход, заключающийся в «бросании» (выпускании) не одного луча, а множества параллельных лучей на разной высоте. Термины «бросание», выпускание, проведение и т.д., в настоящей заявки означают один из методов рендеринга в компьютерной графике, при котором сцена строится на основе замеров пересечения лучей с визуализируемой поверхностью.

[0051] Возвращаясь к Фиг. 5, начальной позицией пользователя в виртуальном туре является точка (501). При применении известных подходов, подразумевающих только «бросание» одного луча к координатам точки (502), указанный луч встретился бы с препятствием, что не позволило бы сформировать путь навигации между точками (501 и 502). Заявленный подход, в свою очередь, на этапе (130) формирует из координаты выбранной точки (501) в трехмерной модели множество параллельных лучей (511-514), расположенных на разной высоте, т.е. с разными координатами высоты, при сохранении остальных пространственных координат, в точку (502), тем самым определяя путь навигации между указанными точками (возможность формирования ребра графа достижимости между вершинами, выраженными точками (501, 502), т.е. этап (140)). При этом ребро графа формируется в том случае, если по меньшей мере один луч, выпущенный из точки (501), достиг точки (502). Стоит отметить, что хотя на указанной Фиг. 5 показано только две точки, количество точек может быть любым и зависит от плотности фотоснимков, совершенных камерой (240) в выбранной трехмерной модели.

[0052] Указанные этапы (130 140) далее итеративно повторяются для каждой точки из набора точек, полученного на этапе (110). Система (210) выполняет указанную последовательность действий из каждой точки, добавленной в граф достижимости на этапе (120). Так, система (210) может определить, все ли точки навигации были добавлены в таблицу, определяющую возможность соединения указанных точек (ребра графа). Если это так, способ (100) переходит к этапу (150). Иначе, способ (100) вернется к этапам (130-140), чтобы выполнить указанную операцию со следующей точкой из набора точек.

[0053] Кроме того, в одном частном варианте осуществления, лучи, сформированные из первой точки ко второй точки могут считаться достигшими второй точки, если по меньшей мере один луч достиг координат второй точки в пределах заданного порога допустимых координат высоты.

[0054] Рассмотрим указанный частный вариант осуществления, показанный на Фиг. 6. При создании маршрутов по виртуальному туру на открытых пространствах могут возникнуть ситуации, когда, например, первая точка навигации располагается перед невысоким препятствием, которое в реальном мире можно преодолеть, однако, как упоминалось выше, при построении маршрута в 3D модели не всегда будет добавлена в указанный маршрут. Так, на фиг.6 показан сквер, в котором между точками (601 и 602) существует низкое препятствие, например, в виде цветочного вазона, зеленой изгороди и т.д. Луч (611), проведенный на малой высоте, «упирается» в препятствие и не достигает точки (602), но луч (612), проведенный выше, свободно достигает точки (612). При использовании известных подходов итоговый граф достижимости не будет содержать прохода между точками (601 и 602), хотя в реальности проход будет существовать. Таким образом, проведение множества лучей позволяет составить более корректный граф достижимости, что, в свою очередь повышает эффективность построения навигационных маршрутов для пользователя. При этом, заданная пороговая величина координат высоты, при которой точки могут быть соединены, задается, например, перед созданием маршрута для пользователя в зависимости от требований к виртуальному туру.

[0055] Таким образом, на этапах (130-140) из первой точки проводится множество лучей во все точки из набора точек, причем указанные лучи формируются на разной высоте, т.е. из разных координат высоты указанной точки и по результатам такой операции принимается решение о добавлении ребра графа достижимости между указанными точками. Еще раз необходимо подчеркнуть, что несмотря на то, что указанные этапы (130-140) описаны для двух точек, данные действия могут применяться к любому количеству точек, содержащихся в наборе точек. Указанная особенность обеспечивает новый подход, позволяющий осуществлять построение более корректного графа достижимости, с учетом особенностей рельефа и/или высоты препятствий, которые в реальном мире являются легкопроходимыми и где должен существовать проход, что повышает эффективность построения навигационного маршрута.

[0056] Далее способ (100) переходит к этапу (150).

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

[0058] Как упоминалось выше, путь навигации представляет собой возможность прямого перехода из одной вершины (точки навигации) графа в другую, по меньшей мере одну, вершину графа. Указанные пути навигации необходимы для построения всех

возможных навигационных маршрутов в виртуальном туре, на основе различных путей навигации.

[0059] Так, на Фиг. 4, для перехода от просмотра элементов трехмерной модели из позиции 1 в позицию 5, пользователь должен быть перемещен через промежуточные позиции (например, позиции 2, 3, 4), которые являются возможными путями навигации из позиции 1. Так, позиция 1, соответственно имеет три пути навигации в позиции 2, 3, 4. Соответственно позиция 2 имеет два пути навигации в позицию 5 и позицию 3, и т.д. Указанные пути навигации имитируют переход пользователя в реальном мире по соответствующему объекту. Причем стоит отметить, что ввиду препятствий, расположенных между позициями 1 и 5, отсутствует прямая видимость, что не позволяет соединить указанные точки и, соответственно, сформировать прямой маршрут. При этом, как видно на Фиг. 6, для пользователя будет существовать множество навигационных маршрутов из позиции 1 в позицию 5, которые базируются на путях навигации.

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

[0061] После определения всех путей навигации между точками навигации, способ (100) переходит к этапу (160).

[0062] На этапе (160) осуществляют построение всех возможных навигационных маршрутов по виртуальному туру для пользователя на основе сформированных путей навигации.

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

[0064] Так, если речь идет о виртуальном туре по недвижимости, то в качестве лучшего маршрута будет выбран маршрут, захватывающих все помещения указанного объекта недвижимости, причем, в качестве дополнительного критерия может быть выбран критерий не повторяемости комнат для улучшения пользовательского восприятия.

[0065] В другом частном варианте осуществления набор маршрутов может быть сгенерирован и быть отображен в качестве подсказки с доступными точками для перемещения на пользовательском устройстве в момент прохождения виртуального тура (200).

[0066] В еще одном частном варианте осуществления критерий может заключаться в том, что количество точек на маршруте является наименьшим и/или длина маршрута является наименьшей.

[0067] Для специалиста в данной области техники очевидно, что указанные выше примеры являются лишь одним из возможных способов применения сформированных навигационных маршрутов и не должны ограничивать настоящее решение. Основной задачей указанного решения является эффективное формирование всех возможных навигационных маршрутов для пользователя по трехмерной модели виртуального тура.

[0068] Возвращаясь к этапу (160) на основе определенных путей навигации система (210), формирует набор навигационных маршрутов, определяя возможные переходы от начальной точки из набора точек ко всем остальным точкам. Например, первая точка может быть начальной точкой перед входом в трехмерную модель недвижимости, вторая точка может являться коридором, а третья и четвертая точки могут являться кухней и гостиной, которые доступны из коридора. Таким образом, набор навигационных маршрутов для пользователя будет содержать два маршрута, состоящих из перехода из первой точки во вторую, а потом в третью, и, соответственно, состоящий из перехода из первой точки во вторую и четвертую.

[0069] Указанный сформированный набор навигационных маршрутов для пользователя может быть сохранен в памяти (210) для последующего отображения в GUI пользователя при отображении трехмерной модели виртуального тура.

[0070] Кроме того, в одном частном варианте осуществления, на основе сформированных навигационных маршрутов из трехмерной модели могут быть удалены некоторые точки навигации. Так, например, при нахождении двух точек навигации в одной комнате ближе порогового расстояния друг к другу, одна из точек может быть удалена как неинформативная. При этом удаление точки возможно только в том случае, если дальнейший путь навигации одинаков из обеих точек. Таким образом, точка навигации, являющаяся кандидатом на удаление, может являться точкой захвата фотоизображения, которое в значительной степени дублируются с фотоизображениями из ближайшей точки навигации. Также, некоторые точки навигации могут быть расположены очень близко к стенам или другим крупным объектам и не иметь дальнейших путей навигации. Указанные точки также могут быть удалены из виртуального тура.

[0071] На Фиг. 7 представлен пример общего вид вычислительно устройство (700), на базе которого может быть реализована система (210), выполняющая заявленный способ (100), указанное устройство также может являться, например, сервером, персональным компьютером, частью вычислительного кластера, обрабатывающим необходимые данные для осуществления заявленного технического решения.

[0072] В общем случае устройство (700) содержит такие компоненты, как: один или более процессоров (701), по меньшей мере одну память (702), средство хранения данных (703), интерфейсы ввода/вывода (704), средство В/В (705), средство сетевого взаимодействия (706), которые объединяются посредством универсальной шины.

[0073] Процессор (701) выполняет основные вычислительные операции, необходимые для обработки данных при выполнении способа (100). Процессор (701) исполняет необходимые машиночитаемые команды, содержащиеся в оперативной памяти (702).

[0074] Память (702), как правило, выполнена в виде ОЗУ и содержит необходимую программную логику, обеспечивающую требуемый функционал.

[0075] Средство хранения данных (703) может выполняться в виде HDD, SSD дисков, рейд массива, флэш-памяти, оптических накопителей информации (CD, DVD, MD, Blue-Ray дисков) и т.п. Средства (703) позволяют выполнять долгосрочное хранение различного вида информации, например полученные координаты точек навигации, построенные навигационные маршруты и навигационные пути и т.п.

[0076] Для организации работы компонентов устройства (700) и организации работы внешних подключаемых устройств применяются различные виды интерфейсов В/В (704). Выбор соответствующих интерфейсов зависит от конкретного исполнения вычислительного устройства, которые могут представлять собой, не ограничиваясь: PCI, AGP, PS/2, IrDa, FireWire, LPT, COM, SAT A, IDE, Lightning, USB (2.0, 3.0, 3.1, micro, mini, type C), TRS/Audio jack (2.5, 3.5, 6.35), HDMI, DVI, VGA, Display Port, RJ45, RS232 и т.п.

[0077] Выбор интерфейсов (704) зависит от конкретного исполнения устройства (700), которое может быть реализовано на базе широко класса устройств, например, персональный компьютер, мейнфрейм, ноутбук, серверный кластер, тонкий клиент, смартфон, сервер и т.п.

[0078] В качестве средств В/В данных (705) может использоваться: клавиатура, джойстик, дисплей (сенсорный дисплей), монитор, сенсорный дисплей, тачпад, манипулятор мышь, световое перо, стилус, сенсорная панель, трекбол, динамики, микрофон, средства дополненной реальности, оптические сенсоры, планшет, световые индикаторы, проектор, камера, средства биометрической идентификации (сканер сетчатки глаза, сканер отпечатков пальцев, модуль распознавания голоса) и т.п.

[0079] Средства сетевого взаимодействия (706) выбираются из устройств, обеспечивающий сетевой прием и передачу данных, например, Ethernet карту, WLAN/Wi-Fi модуль, Bluetooth модуль, BLE модуль, NFC модуль, IrDa, RFID модуль, GSM модем и т.п. С помощью средств (706) обеспечивается организация обмена данными между, например, системой (210), представленной в виде сервера и камерой (240), а также пользовательскими устройствами (221-223) по проводному или беспроводному каналу передачи данных, например, WAN, PAN, ЛВС (LAN), Интранет, Интернет, WLAN, WMAN или GSM.

[0080] Конкретный выбор элементов устройства (700) для реализации различных программно-аппаратных архитектурных решений может варьироваться с сохранением обеспечиваемого требуемого функционала.

[0081] Представленные материалы заявки раскрывают предпочтительные примеры реализации технического решения и не должны трактоваться как ограничивающие иные, частные примеры его воплощения, не выходящие за пределы испрашиваемой правовой охраны, которые являются очевидными для специалистов соответствующей области техники. Таким образом, объем настоящего технического решения ограничен только объемом прилагаемой формулы.

1. Способ построения навигационных маршрутов для пользователя в трехмерной модели виртуального тура, содержащий этапы, на которых:

a. выполняют съемку окружающего пространства с помощью 3D-камеры;

b. передают данные съемки окружающего пространства с камеры на сервер, на котором формируется трехмерная модель виртуального тура, которая содержит трехмерные объекты, соответствующие объектам окружающего пространства области съемки;

c. получают набор точек с заданными координатами трёхмерной модели объекта виртуального тура, причем каждая точка соответствует точке расположения камеры на объекте;

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

e. формируют по меньшей мере два параллельных луча в трехмерной модели объекта из первой точки к точкам из набора точек, которые характеризуют месторасположения камеры на объекте, полученного на этапе c), причем указанные лучи расположены на разной высоте относительно координаты первой точки;

f. формируют ребра графа достижимости между всеми точками, которых достиг по меньшей мере один выпущенный луч;

g. итеративно повторяют этапы e)-f) для каждой точки из набора точек;

h. формируют для каждой точки из набора точек по меньшей мере один путь навигации, причем по меньшей мере одному пути навигации соответствует ребро графа достижимости между двумя точками;

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

2. Система построения навигационных маршрутов для пользователя в трехмерной модели виртуального тура, содержащая: по меньшей мере один процессор, функционально связанный с по меньшей мере одной памятью, хранящей машиночитаемые инструкции, которые при их выполнении процессором реализуют способ по п. 1.