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

Настоящее изобретение относится к области компьютерной графики. Технический результат – повышение производительности процесса отрисовки трехмерной сцены. Способ удаления невидимых поверхностей трехмерной сцены включает: получение на сервере исходных данных по объектам трехмерной сцены и их иерархии из канала обмена данных; получение на сервере данных по текущему положению камеры относительно сцены из канала обмена данных; формирование реестра всех трехмерных объектов сцены для отрисовки, в котором каждый объект представлен своим уникальным идентификатором; осуществление на сервере первичной выбраковки трехмерных объектов по методу отсечения по пирамиде видимости; исключение из реестра на сервере перекрываемых трехмерных объектов, также не требующих отрисовки, посредством последовательного запуска двух проходов одновременной отрисовки всех объектов, причем на первом проходе создают карту минимальных z-глубин путем запуска одновременной отрисовки всех объектов реестра на сервере; на втором проходе определяют для каждого из объектов количество фрагментов, в которых он виден, путем запуска повторной одновременной отрисовки всех объектов на сервере. 2 н. и 6 з.п. ф-лы, 7 ил.

 

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

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

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

[002] В настоящее время современные решения в системах автоматизированного проектирования (CAD), архитектурном моделировании, разработке компьютерных игр, технологиях VR и AR требует интерактивной визуализации динамических данных очень больших объемов, на порядки превосходящих имеющиеся вычислительные мощности.

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

[004] Из уровня техники известен источник информации US 6480205 В1 «Method and apparatus for occlusion culling in graphics systems», патентообладатель: Nvidia Corporation, дата публикации: 12.11.2002. В данном техническом решении обработка Z-буфером трехмерных сцен становится более эффективной благодаря способу удаления невидимых поверхностей (англ. occlusion culling), при котором перекрываемая геометрия удаляется до растеризации. Способ использует иерархическую z-буферизацию для уменьшения количества информации об изображении и глубины, к которой необходимо получить доступ. Отдельный этап отбора в графическом конвейере отбирает перекрываемую геометрию и пропускает видимую геометрию на этап рендеринга. На этапе отбраковки сохраняется собственная z-пирамида, в которой хранятся значения z с низкой точностью (например, в 8 бит). Эффективность иерархической z-буферизации достигается путем иерархического решения линейных уравнений.

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

[005] Данное техническое решение направлено на устранение недостатков, свойственных решениям, известным из уровня техники.

[006] Технической проблемой, решаемой в данном техническом решении, является исключение невидимых объектов и поверхностей трехмерной сцены.

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

[008] Данный технический результат достигается благодаря осуществлению способа удаления невидимых поверхностей трехмерной сцены, в котором получают на сервере исходные данные по объектам трехмерной сцены и их иерархии по слоям из канала обмена данных; затем получают на сервере данные по текущему положению камеры относительно трехмерной сцены из канала обмена данных; после чего формируют реестр всех трехмерных объектов сцены для отрисовки, в котором каждый трехмерный объект представлен своим уникальным идентификатором; далее осуществляют на сервере первичную выбраковку трехмерных объектов по методу отсечения по пирамиде видимости, подразумевающий априорное исключение объектов, находящихся вне поля зрения камеры, с учетом их иерархической вложенности; исключают из реестра на сервере перекрываемые трехмерные объекты, также не требующие отрисовки, посредством последовательного запуска двух проходов одновременной отрисовки всех объектов, причем на первом проходе создают карту минимальных z-глубин путем запуска одновременной отрисовки всех объектов реестра на сервере; на втором проходе определяют для каждого из объектов количество фрагментов, в которых он виден, путем запуска повторной одновременной отрисовки всех объектов на сервере.

[009] В некоторых вариантах осуществления исходные данные по иерархии объектов трехмерной сцены содержат данные о состоянии трехмерных объектов, которые содержатся в трехмерной сцене.

[0010] В некоторых вариантах осуществления реестр всех трехмерных объектов сцены представляет собой упорядоченный набор идентификаторов объектов.

[0011] В некоторых вариантах осуществления реестр трехмерных объектов сцены формируют на основании требований к компонентам по иерархии физического мира в порядке возрастания или убывания.

[0012] В некоторых вариантах осуществления реестр всех трехмерных объектов сцены представлен в виде BSP дерева или восьмеричного дерева.

[0013] В некоторых вариантах осуществления при осуществлении первичной выбраковки трехмерных объектов, применяют ко всем вершинам полигонов трехмерной сцены проекционную матрицу.

[0014] В некоторых вариантах осуществления перед выполнением последовательных отрисовок реестр объектов сжимается с удалением ранее исключенных объектов.

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

[0015] Признаки и преимущества настоящего технического решения станут очевидными из приводимого ниже подробного описания и прилагаемых чертежей, на которых:

[0016] На Фиг. 1 - приведена схема взаимодействия клиентского приложения и сервера для отрисовки 3D-сцены;

[0017] На Фиг. 2 - приведена блок-схема способа удаления невидимых поверхностей трехмерной сцены;

[0018] На Фиг. 3 показан вариант реализации графического конвейера (прохода или цикла отрисовки);

[0019] На Фиг. 4 показан вариант представления уровней детализации объектов;

[0020] На Фиг. 5 показан вариант осуществления выбраковки по фрустуму и перекрытию (по выделенному вектору минимум буфера глубины эквивалентен 3);

[0021] На Фиг. 6 показаны фигуры (ограничивающие объем), например, сфера, параллелепипеды (ООВВ, ААВВ);

[0022] На Фиг. 7 - приведена схема системы удаления невидимых поверхностей трехмерной сцены.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

[0024] Техническое решение может быть реализовано в виде распределенной компьютерной системы.

[0025] В данном изобретении под системой подразумевается компьютерная система, ЭВМ (электронно-вычислительная машина), ЧПУ (числовое программное управление), ПЛК (программируемый логический контроллер), компьютеризированные системы управления и любые другие устройства, способные выполнять заданную, четко определенную последовательность операций (действий, инструкций).

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

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

[0028] Ниже будут описаны понятия и определения, необходимые для подробного раскрытия осуществляемого технического решения.

[0029] Модель (3D-модель) - исходная трехмерная модель (состоящая из 3D-объектов), представленная в одном из существующих 3D-форматов (Autodesk FBX и пр.), в отношении которых решается задача интерактивной 3D-визуализации.

[0030] Сетка (Mesh, Геометрия объекта) - трехмерная сетка, совокупность точек и граней которой описывают геометрию соответствующего 3D-объекта.

[0031] Цикл отрисовки (graphics pipeline, пайплайн, графический конвейер) - это цепочка процессов преобразования сценария (исходных данных) в 2D (двухмерную) картинку или в последовательность картинок (видео), отображаемых на экране, выполняемая графической картой (GPU). Как правило носит стандартный характер (состав шагов незначительно варьируется от аппаратных и программных реализаций), но в последних версиях программных решений (напр. Vulkan API) может быть настраиваемым (оптимизируемым).

[0032] Уникальный идентификатор (UID) - уникальный код, однозначно идентифицирующий элемент в семействе / массиве / списке. Может как совпадать с индексом элемента в данном семействе / массиве, так и отличаться от него.

[0033] Макет модели (Layout) - набор данных, описывающих перечень и иерархическую вложенность (родитель-ребенок) объектов 3D-модели, ссылки на геометрию (в случае партий - на геометрию эталонного объекта) в виде UID и параметры их пространственного преобразования относительно родительских объектов (трансформы из локальных в родительскую систему координат).

[0034] Матрицы пространственного преобразования (Transforms, Трансформы) - численные матрицы 4×4, описывающие преобразования над пространственным положением объекта: сдвиг, поворот, масштаб.

[0035] Клиентская часть (клиент, клиентский рендер, клиентский вьюер) - клиентская часть программного решения, исполняемая в среде web-браузера (JS) и отвечающая за интерактивную 3D-визуализацию исходной модели.

[0036] Выбраковка невидимых объектов (Occlusion Culling, ОС, ОС-вычисления) - определение объектов, которые не требуют отрисовки в текущем кадре (находятся вне обзора камеры, либо заслонены другими объектами).

[0037] Реестр объектов к отрисовке - перечень объектов, которые подлежат отрисовке на экране. Является результатом выполнения ОС-вычислений.

[0038] Распределенная выбраковка невидимых объектов (Server-side Occlusion Culling, SSOC) - способ организации распределенных ОС-вычислений на архитектуре «клиент-сервер», при котором расчет выбраковываемых объектов для клиентской части частично или полностью выполняется его серверной частью (сервер поддержки).

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

[0040] Asset-сервер (Asset-Store, AS-сервер) - серверная часть программного решения, отвечающая за публикацию исходных данных в серверном пространстве и организующая доступ к ним для остальных компонентов решения.

[0041] Канал обмена данными (Web-Socket, WS) - распределенная часть программного решения (используется как на клиентской, так и на серверной стороне решения), используемая для обмена информацией о состоянии 3D-объектов и сцены в целом.

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

[0043] Буфер чтения - буфер в GPU-памяти, используемый для отрисовки текущего кадра. Каждая отрисовка (graphics pipeline) производится на базе информации, размещенной в этом буфере (непрерывный цикл).

[0044] Буфер записи - буфер в GPU-памяти, который используется для подготовки нового буфера чтения в случае, если сцена в «текущем» кадре изменилась (сдвинулись объекты, повернулась камера и т.д.). После того, как буфер записи полностью подготовлен - отрисовка переключается на него (он становится буфером чтения), а предшествующий буфер чтения используется в последующем как буфер записи (меняются местами).

[0045] Партия объектов (Batch, инстансы, instances) - группировка объектов идентичной геометрии (т.е. которые отличаются только разными сдвигами / поворотами / масштабом) в одну партию, для которой задается описание геометрии эталонного объекта, а остальные - задаются в виде трансформов из объектного (т.е. эталонного объекта) в мировое пространство.

[0046] Объектно-ориентированный ограничивающий параллелепипед (ОВВ, ООВВ, Object-Oriented Bounding Box) - одна из вариаций технологии ограничивающих объемов, используемой для упрощения вспомогательных вычислений при 3D-визуализациях путем проведения тестов (вычислений) над упрощенным представлением объектов (используется в случаях, когда вычисления по точной геометрии объектов занимают неоправданно много времени / ресурсов).

[0047] Multi-Draw Indirect Call (MDI-вызовы, MDI-техники) - способ отрисовки большого количества объектов, основанный на расширенных функциях Vulkan API и подразумевающих распределенные алгоритмы отрисовок (создание буферов команд и их параметров на CPU с последующей параллельной/одновременной отрисовкой на GPU).

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

[0049] Растеризация - это перевод изображения, описанного векторным форматом в пиксели или точки, для вывода на дисплей или принтер. Процесс, обратный векторизации.

[0050] Первоначально пользователь технического решения инициирует загрузку трехмерной модели 102 в web-браузере 101 путем перехода по ранее полученной URL-ссылке (как показано на Фиг. 1).

[0051] Затем при загрузке контента, размещенного по URL-ссылке, производится кэширование в клиентском приложении:

- модуля отображения 3D-сцены (JS-код, исполняемый в среде web-браузера);

- макета 3D-сцены (оптимизированного под работу со средством отображения).

[0052] После запуска модуль отображения открывает канал обмена данными с сервером 103 и запрашивает поддержку для отрисовки текущей трехмерной модели (направляет ее уникальный идентификатор UID).

[0053] Сервер 103 запрашивает с AS-сервера 104 макет трехмерной сцены (по ее уникальному идентификатору UID), упрощенную геометрию всех ее объектов и предварительно рассчитанные параметры их ООВВ, а также открывает канал обмена данными с клиентом (со своей стороны), после чего осуществляет способ удаления невидимых поверхностей трехмерной сцены, показанный на Фиг. 2.

[0054] Согласно примерному варианту осуществления способ удаления невидимых поверхностей трехмерной сцены работает на сервере 103 следующим образом:

[0055] Шаг 201: получают на сервере исходные данные по объектам трехмерной сцены и их иерархии по слоям из канала обмена данных.

[0056] На данном шаге получают на сервере 103 исходные данные по иерархии объектов трехмерной сцены по слоям из канала обмена данных, представляющие собой макет 3D-сцены, оптимизированный под SSOC-сервер, а также упрощенную геометрию и параметры ООВВ каждого объекта, которые рассчитываются заранее.

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

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

[0059] Шаг 202: Также получают на сервере 103 данные по текущему положению камеры относительно трехмерной сцены из канала обмена данных;

[0060] Шаг 203: формируют реестр всех трехмерных объектов сцены для отрисовки, в котором каждый трехмерный объект представлен своим уникальным идентификатором.

[0061] Реестром трехмерных объектов является упорядоченный набор идентификаторов объектов.

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

[0063] Данный упорядоченный набор со сложными трехмерными объектами может быть представлен в виде древовидных иерархий. В данном варианте осуществления может формироваться многомасштабное представление в виде BSP дерева или восьмеричного дерева.

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

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

[0066] Таким образом, нет необходимости отрисовывать объекты, находящиеся сзади или сбоку от камеры и не попадающие в поле зрения. Отрисовываются только те объекты, которые находятся в поле видимости камеры, или в объеме видимости камеры. Этот объем и является усеченной пирамидой, все что находится вне пирамиды находится и вне экрана.

[0067] Исходя из сказанного выше, для определения видимости вершины необходимо проверить, находится ли обрабатываемая вершина внутри усеченной пирамиды, либо домножить вершины на матрицу проецирования и проверить, находится ли вершина внутри единичного куба. В некоторых вариантах осуществления на видимость проверяются только несложные геометрические фигуры, состоящие из нескольких вершин, и, если вся фигура оказывается вне видимости, то часть сцены, заключенная в нее, может быть отброшена. В роли таких фигур (ограничивающих объемов) могут выступать фигуры, известные и применяемые из уровня техники, например, сфера, параллелепипеды (ООВВ, ААВВ) и т.д. Таким образом, несложно организовать отсечение компактных моделей (в том числе динамических) с учетом их иерархии. Иерархия учитывается следующим образом: если родительский элемент не прошел проверку Frustum, дочерний элемент не проверяют. Фигуры, ограничивающие объем видимости, и их параметры получают из Asset-сервера 104 заранее.

[0068] При выбраковке объектов их идентификаторы в реестре на сервере 103 принимают нулевые значения.

[0069] Дополнительно из текущего реестра на сервере 103 выбракованные (обнуленные) на предыдущем шаге элементы с помощью его сжатия (stream compaction).

[0070] Способ stream compaction (уплотнение / сокращение потока) является операцией удаления нежелательных элементов из коллекции. Stream compaction является ключевым шагом по нескольким важным алгоритмам, особенно в области параллельного программирования, где нередко приходится обрабатывать большую и разреженную структуру данных (параллельное пересечение дерева по дереву, трассировка лучей и т.д.), что может привести к ухудшению производительности общего алгоритма.

[0071] Шаг 205: исключают из реестра на сервере 103 перекрываемые трехмерные объекты, также не требующие отрисовки, посредством последовательного запуска двух проходов одновременной отрисовки всех объектов.

[0072] На данном шаге удаляются объекты, которые «перекрываются» другими (либо являются очень маленькими) и не видны на экране.

[0073] В некоторых вариантах осуществления удаляют не объекты целиком, а их перекрываемые части для отрисовки.

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

[0075] Объекты, у которых фактическое количество таких фрагментов ниже минимально-необходимого, подлежат выбраковке, а их идентификаторам в текущем реестре на сервере устанавливается нулевое значение.

[0076] Определение фактического количества таких фрагментов для каждого объекта, так называемая проверка видимости, производится путем имитации отрисовки трехмерной сцены и расчета выбраковочных метрик в процессе ее выполнения.

[0077] Выполнение данного шага технического решения производится на сервере поддержки (SSOC-сервер). Это позволяет существенно снизить нагрузку на клиентское приложение в процессе отрисовки текущей сцены.

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

[0079] Шаг 301: расчет вершин (координаты/цвета/нормали/координат текстур для вершин).

[0080] Шаг 302: преобразование (обработка) вершин:

а. Вершинный шэйдер (Vertex Shader, VS);

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

[0082] Шейдерами (Shaders) называют микропрограммы, задаваемые инструкциями API, которые динамически изменяют алгоритм работы графического процессора видеокарты. Вершинные шейдеры (Vertex Shaders) определяют порядок трансформации вершин треугольников в полигональной модели. Изменение свойств вершины вызывает необходимость пересчета большого объема данных, что сильно загружает центральный процессор и шину AGP. С появлением чипсетов, поддерживающих технологию вершинных шейдеров (например, GeForce3/4, Radeon 8500), задачи расчета трансформации вершин решаются графическим процессором, то есть объем геометрических данных, передаваемых по шине AGP, резко снижается. Например, вместо большого массива новых параметров освещения вершин теперь достаточно передать несколько коротких инструкций API для графического процессора.

[0083] Аппаратными средствами графического процессора можно выполнять, например, следующие преобразования (обработку) вершин:

[0084] - межкадровая интерполяция вершин (Key Frame Interpolation), что существенно ускоряет анимацию;

[0085] - наложение вершин (Vertex Blending) с использованием более чем четырех матриц преобразования, что облегчает «скелетную» анимацию сложных моделей без их разбиения на несколько частей;

[0086] - процедурная геометрия, то есть искажение свойств вершин каким-либо параметрическим объектом (например, волны на водной поверхности или перекатывающиеся под кожей мускулы персонажа);

[0087] - сложные модели освещения, учитывающие свойства материала объектов.

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

b. Тесселяция (HS+Tess+DS), то есть сглаживание стыков за счет более мелкой нарезки объектов;

[0089] Современные графические процессоры (GPU) умеют выполнять дополнительные операции, например тесселяцию (Tesselation), то есть разделение исходных треугольников на более мелкие компоненты. Одним из методов улучшения формы трехмерных полигональных моделей и снижения потока данных служит применение трехмерных поверхностей высокого порядка. В этом случае исходный объект можно представить меньшим числом элементов, а детализацию выполнить средствами графического адаптера путем разбиения граней на мелкие треугольники, зависимости от заданной степени тесселяции исходный треугольник может различными способами разбиваться на более мелкие (от 4 до 64). Этот процесс эффективно обсчитывается в графическом процессоре. Тесселяция позволяет несколько повысить качество отображения объектов, однако не избавляет от коренного недостатка: сравнительно грубых исходных граней.

c. Геометрический шэйдер (GS).

[0090] Геометрический шейдер (GS) получает на вход уже собранный примитив, вершины которого были обработаны вершинным шейдером. Он имеет доступ сразу ко всем вершинам примитива и в результате своей работы он отбрасывает исходный примитив, создавая вместо него ноль или более примитивов (при этом типы входных и выходных примитивов могут не совпадать). Геометрический шейдер может получать на вход один из пяти типов примитивов, при этом входной тип для шейдера явно задается в его тексте. Допустимыми входными типами примитивов являются: точки, линии, треугольники, отрезок с двумя соседними точками и треугольник с соседними вершинами. Эти типы примитивов позволяют передавать в геометрический шейдер не только сам выводимый примитив (отрезок или треугольник), но и соседние с ним примитивы. Таким образом, геометрический шейдер может, например, определять какие из ребер треугольного мэша является контурными (т.е. разделяют лицевые и нелицевые грани).

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

[0092] Шаг 303: сборка примитивов

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

[0094] Шаг 304. Растеризация (заполнение примитивов пикселями) + ранний тест глубины (depth test) и трафаретов (stencil test).

[0095] Координата Z характеризует глубину сцены, то есть степень удаления объектов от камеры (плоскости проецирования). Очевидно, что проекция непрозрачных объектов, расположенных ближе к камере, будет частично или полностью перекрывать проекцию удаленных объектов, исключая их видимость для наблюдателя. Кроме того, грани объекта, обращенные к плоскости проецирования, препятствуют видимости расположенных с тыла элементов. Графический адаптер должен определить, какие объекты следует отображать, а какие скрыть. Для этого координаты глубины помещают в Z-буфер. Для оценки сложности сцены применительно к видимости ее элементов по глубине применяют показатель перекрытия полигонов (Overdraw). Например, если значение Overdraw составляет три единицы (что характерно для современных программ), это означает, что в среднем один видимый полигон перекрывает три полигона, расположенных глубже.

[0096] Шаг 305: фрагментные (пиксельные) шэйдеры (интерполяцией цвета, текстур и света).

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

[0098] Пиксельные шейдеры - это программные инструкции, выполняемые видеочипом во время растеризации для каждого пикселя изображения, они производят выборку из текстур и/или математические операции над цветом и значением глубины (Z-buffer) пикселей. Все инструкции пиксельного шейдера выполняются попиксельно, после того, как операции с трансформированием и освещением геометрии завершены. Пиксельный шейдер в итоге своей работы выдает конечное значение цвета пикселя и Z-значение для последующего этапа графического конвейера, блендинга. Наиболее простой пример пиксельного шейдера, который можно привести: мультитекстурирование, просто смешение двух текстур (diffuse и lightmap, например) и наложение результата вычисления на пиксель.

[0099] Шаг 306: по-фрагментная обработка:

a. Отсечение по проекции (scissor test)

b. Отсечение по шаблону/трафарету (stencil test)

c. Тест глубины (поздний)

[00100] На этом шаге проводится ряд по-фрагментных тестов, таких как тест отсечения (scissor test), тест прозрачности (alpha test), тест трафарета (stencil test) и тест глубины (depth test). Эти тесты определяют конечный вид, цвет и глубину фрагмента перед обновлением экранного буфера. Если какой либо тест проходит с ошибкой, то фрагмент не обновляется.

[00101] Шаг 307: блендинг и итоговая отрисовка.

[00102] После тестов выполняется операция смешивания (blending), которая комбинирует финальный цвет фрагмента с текущим цветом пиксела, а итоговый результат записывается в экранный буфер. Операция смешивания выполняется на этом этапе, поскольку стадия текстурирования и окрашивания не имеют доступа к экранному буферу.

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

[00104] Шаг 205: исключают из реестра на сервере перекрываемые трехмерные объекты, также не требующие отрисовки, посредством последовательного запуска двух циклов отрисовки.

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

[00106] Шаг 205 а): На первом шаге отрисовки создают карту минимальных z-глубин для каждого фрагмента путем первичной отрисовки объектов реестра на сервере 103 с использованием их низкополигональных геометрических представлений и упрощенного цикла конвейера (только вершинный шэйдер и растеризация с ранним тестом глубины), при котором буфер глубины используется в режиме «записи» (без отсечений).

[00107] Реализацию этого шага обеспечивают следующим образом: объекты помещаются на сцену в виде «загрубленных» 3D-геометрий (низкого разрешения - Фиг.4) и запускаются на отрисовку (с учетом поворотов/сдвигов, выполняемых на этапе вершинного шэйдера). Растеризация производится в режиме «записи» буфера глубины (без отсечения), в результате чего для каждого фрагмента (пикселя) на экране определяется минимальное расстояние до ближайшего к нему объекта (см. Фиг. 5). Множество таких метрик (минимумов глубины) для каждого фрагмента (пикселя) экрана образуют карту минимальных z-глубин.

[00108] Шаг 205 б): на втором проходе отрисовки определяют для каждого из объектов количество фрагментов, в которых он виден, путем вторичной отрисовки объектов на сервере 103 с использованием их сонаправленных ограничивающих параллелепипедов (ООВВ), как например показано на Фиг. 6, и прохода конвейера (дополняется геометрическим и фрагментным шэйдерами) в режиме отсечения по буферу глубины на базе ранее полученной карты.

[00109] Реализацию этого шага обеспечивают следующим образом: на трехмерную сцену помещаются ООВВ каждого объекта (формируются на геометрическом шейдере по заранее просчитанным параметрам, получаемым с Asset-сервера 104 при загрузке макета модели), что обеспечивает высокую скорость прохождения этого прохода. Каждому ООВВ задается уникальный индекс и помещается в буфер памяти, доступный используемым в отрисовке шейдерам. Ранее сохраненная карта минимальных z-глубин помещается в текущий буфер глубины, после чего он переводится в режим «чтения» и запускается многопотоковая растеризация (все ООВВ отрисовываются параллельно, каждый в своем потоке) с выполнением раннего теста на отсечение по глубине (стандартная функциональность данного шага графического конвейера). Фрагменты (пикселы), требующие отрисовки по итогам этого теста, поступают в обработку на фрагментный шейдер, где они засчитываются в счет увеличения количества пикселей видимости объекта, которому соответствует текущий индекс ООВВ.

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

[00111] Затем обнуляют в реестре идентификаторы невидимых (перекрываемых) трехмерных объектов, выявляемых путем сопоставления фактического количества фрагментов, где объект виден, и минимального количества фрагментов, необходимого для признания объекта видимым.

[00112] На данном шаге осуществляется переход от массивов идентификаторов объектов «к отрисовке» (каждый UID занимает не менее 2 байт) к бинарной карте (последовательность 0 и 1), где необходимость «отрисовать» объект отмечается единичным значением бита с тем же порядковым номером, что и индекс объекта в иерархии макета модели.

[00113] В некоторых вариантах осуществления, заявленный способ выполняется на системе удаления невидимых поверхностей трехмерной сцены, показанной на Фиг. 7.

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

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

[0001] Система 700 может включать один или более следующих компонент: компонент 701 обработки данных, устройство 702 хранения данных, компонент 703 питания, компонент 704 мультимедиа, интерфейс 705 ввода / вывода (I / О), сенсорный компонент 706, компонент 707 передачи данных.

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

[0003] Устройство 702 хранения данных (или память в некоторых вариантах реализации) выполнено с возможностью хранения различных типов данных для поддержки работы системы. Примеры таких данных включают в себя реестр трехмерных объектов сцены, z-буфер, инструкции из любого приложения или способа, изображения, видео, и т.д. Устройство 702 хранения данных может быть реализовано в виде любого типа энергозависимого запоминающего устройства, энергонезависимого запоминающего устройства или их комбинации, например, Статического Оперативного Запоминающего Устройства (СОЗУ), Электрически Стираемого Программируемого Постоянного Запоминающего Устройства (ЭСППЗУ), Стираемого Программируемого Постоянного Запоминающего Устройства (СППЗУ), Программируемого Постоянного Запоминающего Устройства (ППЗУ), Постоянного Запоминающего Устройства (ПЗУ), магнитной памяти, флэш-памяти, магнитного или оптического диска, не ограничиваясь.

[0004] В некоторых вариантах реализации, компонент 703 питания обеспечивает электричеством различные компоненты системы 700. Компонент 703 питания может включать систему управления электропитанием, один или более источник питания, и другие узлы для генерации, управления и распределения электроэнергии к системе 700.

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

[0006] Интерфейс 705 ввода/вывода обеспечивает интерфейс между компонентом обработки данных и любым известным из уровня техники периферийным интерфейсным модулем.

[00116] Сенсорный компонент 706 содержит один или более сенсоров и выполнен с возможностью обеспечения различных аспектов оценки состояния системы. Например, сенсорный компонент 706 может обнаружить состояния вкл/выкл системы, относительное расположение компонентов, например, дисплея и кнопочной панели системы, изменение положения системы или одного компонента системы, наличие или отсутствие контакта между пользователем и системой, а также ориентацию или ускорение/замедление системы. Сенсорный компонент 706 содержит бесконтактный датчик, выполненный с возможностью обнаружения присутствия пользователя, находящегося поблизости, когда нет физического контакта. Сенсорный компонент содержит оптический датчик (например, КМОП или ПЗС-датчик изображения) выполненный с возможностью визуализации трехмерной сцены в клиентском приложении. В некоторых вариантах реализации сенсорный компонент 706 содержит датчик ускорения, гироскоп, магнитный датчик, датчик давления или датчик температуры.

[00117] Компонент 707 передачи данных выполнен с возможностью облегчения проводной или беспроводной связи между системой и другими устройствами. В некоторых вариантах реализации компонент 707 передачи данных открывает канал обмена данными между сервером и клиентским приложением. Система 700 может получить доступ к беспроводной сети на основе стандарта связи, таких как WiFi, 2G или 3G, или их комбинации. В одном примерном варианте компонент 707 передачи данных получает широковещательный сигнал или трансляцию, связанную с ними информацию из внешней широковещательной системы управления через широковещательный канал. В одном варианте осуществления компонент 707 передачи данных содержит модуль коммуникации ближнего поля (NFC), чтобы облегчить ближнюю связь, или модуль для радиочастотной идентификации (RFID), модуль передачи данных в инфракрасном диапазоне (IrDA), или сверхширокополосной (UWB) технологии, либо модуль Bluetooth (ВТ) или иное средство, пригодное для беспроводной передачи данных.

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

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

получают на сервере исходные данные по объектам трехмерной сцены и их иерархии из канала обмена данных;

получают на сервере данные по текущему положению камеры относительно трехмерной сцены из канала обмена данных;

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

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

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

на первом проходе создают карту минимальных z-глубин путем запуска одновременной отрисовки всех объектов реестра на сервере;

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

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

3. Способ по п. 1, характеризующийся тем, что реестр всех трехмерных объектов сцены представляет собой упорядоченный набор идентификаторов объектов.

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

5. Способ по п. 1, характеризующийся тем, что реестр всех трехмерных объектов сцены представлен в виде BSP дерева или восьмеричного дерева.

6. Способ по п. 1, характеризующийся тем, что при осуществлении первичной выбраковки трехмерных объектов применяют ко всем вершинам полигонов трехмерной сцены проекционную матрицу.

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

8. Система удаления невидимых поверхностей трехмерной сцены, содержащая:

один или более компонент обработки данных;

одно или более устройство хранения данных;

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