Способ отсечения линии и способ отображения трехмерного изображения на основе этого способа

Изобретение относится к способу отсечения линии для удаления ненужных звеньев линии с узлами и структуры звеньев в трехмерном изображении. Техническим результатом является сокращение объема и повышение эффективности вычислений, а также увеличение скорости отображения элементов при отображении трехмерных изображений. Способ заключается в следующем: определяют находятся ли узлы линии трехмерного изображения, подлежащего проецированию на плоскость, внутри или вне отображаемого объема, путем сравнения значений по оси z для этих узлов со значением по оси z для плоскости отсечения относительно положения центра проекции, причем плоскость отсечения размещают между положением центра проекции и плоскостью проекции, вычисляют точки пересечения плоскости отсечения и звеньев, соединяющих узлы линии, строят новую линию, используя вычисленные точки пересечения и узлы, находящиеся внутри отображаемого объема. Заявлены также способы отображения трехмерного изображения с использованием отсечения линии. 6 н. и 25 з.п. ф-лы, 22 ил.

 

ПРЕДПОСЫЛКИ К СОЗДАНИЮ ИЗОБРЕТЕНИЯ

1. Область техники, к которой относится изобретение

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

2. Описание уровня техники

Обычная обработка трехмерной графики включает операцию отсечения для отсечения части трехмерного изображения, которая не предназначена для отображения на экране. Например, как показано на фиг.1, отсечение выполняют для удаления данных для тех частей трехмерного изображения, которые находятся вне границ отображаемого объема 120, если смотреть на трехмерное изображение из положения центра проекции 100, как точки обзора, если данные части трехмерного изображения размещены внутри границ отображаемого объема 120, т.е. внутри шести плоскостей, включающих плоскость проекции 110 и выше, ниже, левее, правее и сзади отображаемого объема 120, проецируют на плоскость проекции 110. Это позволяет уменьшить объем данных, для обработки трехмерного изображения, в связи с чем уменьшается объем вычислений и повышается скорость обработки.

Кроме того, когда линию проецируют на плоскость проекции, узлы линии, находящиеся позади центра проекции 100, проецируются обратно в направлении, противоположном ожидаемому. Таким образом, они должны быть удалены посредством отсечения линии. Т.е., как показано на фиг.2а, если линию 220, находящуюся внутри границы отображаемого объема 210 при наблюдении из положения центра проекции 200, проецируют на плоскость проекции 230, она проецируется как линия 240 на плоскость проекции 230. Однако, как показано на фиг.2b, если с одной стороны узел линии 220 с координатами (x, у, z) находится позади положения центра проекции 200, координаты (x, у, z) узла проецируются как спроецированные координаты (x_p, у_p) на плоскость проекции 230, что приводит к появлению ошибки, при которой линия 220 проецируется как неправильная линия 240а на плоскость проекции 230.

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

На фиг.4 проиллюстрирован реальный принцип отсечения линии и проецирования, в котором звено линии 410, находящееся вне плоскости проекции 400, т.е. вне отображаемого объема, удаляют посредством отсечения от плоскости проекции 400, и проецируются только узлы, находящиеся внутри плоскости проекции 400, т.е. внутри отображаемого объема, если смотреть на них из центра проекции 420. При этом требуется вычислить координаты точек пересечения линии 410 и плоскости проекции 400 для формирования линии, имеющей новую структуру, состоящую из вычисленных координат точек пересечения и координат узлов, находящихся в плоскости проекции 400.

Например, получают точки пересечения nv1, nv2 и nv3 плоскости 400 проецирования и линии 410 с соединенными узлами и звеньями v0, v1, v2, v3 и v4, а узлы v0 и v3, находящиеся вне отображаемого объема, удаляют, благодаря чему выполняют преобразование в линию 410, имеющую новую структуру, состоящую из шести узлов nv1, v1, v2, nv2, nv3 и v4.

Отсечение линии обычным способом выполняют с шести сторон, т.е. по плоскости проекции и верхней, нижней, левой, правой и задней сторонам отображаемого объема. Например, как показано на фиг.5, для линии 500, состоящей из семи узлов v0, v1, v2, v3, v4, v5 и v6, координаты точек пересечения ve2, ve4 и ve6 линии 500 с шестью сторонами, включая плоскость проекции 520 и верхнюю, нижнюю, левую, правую и заднюю стороны отображаемого объема 530, если смотреть из центра проекции 510, рассчитывают для формирования линии с новой структурой, состоящей из ve0(v0), ve1(v1), ve2, ve4, ve5(v5) и ve6.

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

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

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

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

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

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

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

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

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

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

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

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

Координаты точек пересечения линии и плоскости отсечения можно выразить посредством заданного параметрического уравнения. Параметрическое уравнение может быть решено посредством определения параметра t, если значение по оси z для плоскости отсечения задано как k. Таким образом, можно простым способом получить координаты точек пересечения линии и плоскости отсечения.

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

Координаты узлов, составляющих новую линию, определяют, как показано ниже.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На фиг.2а и 2b - эффект обратного проецирования линии, находящейся позади центра проекции.

На фиг.3 продемонстрирована ошибка, возникающая при отображении трехмерной карты.

На фиг.4 проиллюстрированы принципы отсечения и проецирования линии.

На фиг.5 проиллюстрирован обычный способ отсечения линии.

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

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

На фиг.8 проиллюстрирована операция вычисления координат точек пересечения плоскости отсечения и линии в способе отсечения линии согласно настоящему изобретению.

На фиг.9 - общий принцип на примере осуществления способа отсечения линии согласно настоящему изобретению.

На фиг.10а и 10b блок-схема иллюстрирует процесс преобразования двухмерной карты в трехмерную карту и отображения трехмерной карты на экране с использованием приближенного отсечения для линий согласно другому примеру осуществления способа отсечения линии согласно настоящему изобретению.

На фиг.11 блок-схема иллюстрирует пример формирования новой линии на фиг.10а.

На фиг.12а и 12b представлена иллюстрация процесса на примере формирования новой линии, показанного на фиг.11.

На фиг.13 блок-схема иллюстрирует другой пример формирования новой линии на фиг.10а.

На фиг.14а и 14b и фиг.15а и 15b представлена иллюстрация процесса на примере формирования новой линии, показанной на фиг.13.

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

Ниже приведено подробное описание способа отсечения линии и способа отображения трехмерного изображения на основе такого способа отсечения линии согласно настоящему изобретению со ссылками на приведенные чертежи, особенно - на фиг.6-15.

На фиг.6 типичная блок-схема иллюстрирует конфигурацию навигационной системы, для которой применены способ отсечения линии и способ отображения трехмерного изображения на основе способа отсечения линии согласно настоящему изобретению. Как показано на фигуре, навигационная система содержит: GPS (глобальной системы навигации и определения положения) приемник 610, принимающий навигационные сообщения, передаваемые множеством спутников GPS 600; блок хранения картографических данных 620, для предварительного хранения там картографических данных с двухмерными координатами; блок ввода команд 630, для получения управляющих команд, определяемых действиями пользователя; блок управления 640, способный управлять операциями для определения текущего положения транспортного средства на основе навигационных сообщений, принимаемых GPS приемником 610, для считывания картографических данных, с двухмерными координатами определенной области, из блока хранения картографических данных 620 в соответствии с определенным текущим положением транспортного средства, преобразование считанных картографических данных, содержащих двухмерные координаты, в картографические данные с трехмерными координатами, и отображение картографических данных, с трехмерными координатами, для управления маршрутом перемещения транспортного средства; и блок управления отображением 650 текущего положения транспортного средства, и маршрута перемещения вместе с трехмерной картой на панели дисплея 660 под управлением блока управления 640.

GPS приемник 610 навигационной системы, имеющий указанную выше конструкцию, принимает соответствующие навигационные сообщения, передаваемые множеством спутников GPS 600, и вводит их в блок управления 640.

Во время перемещения транспортного средства блок управления 640 определяет текущее положение транспортного средства в соответствии с навигационными сообщениями, принятыми GPS приемником 610 и считывает картографические данные с двухмерными координатами для определенной области из блока хранения картографических данных 620 на основе определенного текущего положения транспортного средства.

Затем блок управления 640 преобразует считанные картографические данные с двухмерными координатами в картографические данные с трехмерными координатами, в то время как отсекают линии в соответствии со способом отсечения линии согласно настоящему изобретению. После этого блок управления 640 выдает преобразованные картографические данные, содержащие трехмерные координаты в блок управления отображением 650, в результате чего трехмерная карта может быть отображена на панели дисплея 660. В этот момент определенное текущее положение транспортного средства одновременно отображают в виде стрелки или подобного знака на трехмерной карте в качестве указания по перемещению транспортного средства.

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

На фиг.7а-7с показаны блок-схемы, иллюстрирующие процесс, при котором блок управления 640 преобразует картографические данные, содержащие двухмерные координаты, в картографические данные, содержащие трехмерные координаты, с отсечением линии в соответствии со способом отсечения линии согласно настоящему изобретению и выводит на экран картографические данные, содержащие трехмерные координаты. Как показано на фиг.7а, блок управления 640 определяет координаты опорной позиции (операция 700). При этом координаты текущего положения транспортного средства, которые блок 640 определяет на основе навигационных сообщений, принятых GPS приемником 610, или координаты позиции, введенные пользователем при помощи блока ввода команд 630, можно определить как координаты исходного положения.

После того как координаты исходного положения будут полностью определены при операции 700, блок управления 640 выполняет процесс инициализации трехмерных сред для отображения трехмерной карты или трехмерных моделей на панели дисплея 660 (операция 710). Процесс инициализации трехмерных сред (операция 710) на операции 710 включает следующие операции. Инициализируется среда освещения (операция 711). При инициализации среды освещения на операции 711 задают точку обзора, линию визирования, направление источника света, интенсивность источника света, цвета и их насыщенность для указания соответствующих сторон строений согласно углам соответствующих сторон строений и т.п. Затем инициализируют буферы глубины (операция 712). Т.е. инициализируют буферы глубины для указания расстояний от точки обзора до позиций, где будут отображены определенные объекты. Затем цвет фона экрана панели дисплея отменяют и настраивают заданный цвет (операция 713).

Когда процесс инициализации трехмерных сред завершают на операции 710, блок управления 640 выполняет процесс установки точки обзора (операция 720). Процесс установки точки обзора на операции 720 состоит из следующих операций. Сначала устанавливают положение точки обзора (операция 721). При установке положения точки обзора, для примера, позицию, поднятую на заданную высоту в координатах исходного положения определенного на операции 700, устанавливают как точку обзора. Затем на операции 722 задают линию визирования, определяющую направление, в котором трехмерная карта или модель просматривают с точки обзора. Например, направление перемещения транспортного средства, определенное блоком управления 640 на основе навигационных сообщений, принятых приемником GPS 610, задают как линию визирования.

Когда процесс установки линии визирования завершают на операции 720, блок управления 640 устанавливает параметры проецирования, используемые при проекционном преобразовании, после чего картографические данные, с трехмерными координатами будут спроецированы на плоскость проекции (операция 730).

Пока блок управления 640 последовательно выполняет процесс инициализации трехмерной среды на операции 710, процесс установки точки обзора на операции 720 и процесс установки параметров проецирования на операции 730, блок управления загружает картографические данные, с двухмерными координатами, которые будут преобразованы в картографические данные, с трехмерными координатами, из блока хранения картографических данных 620 (операция 740). При этом загрузку картографических данных, с двухмерными координатами, выполняют посредством загрузки только картографических данных, содержащих двухмерные координаты, для определенной области вокруг координат опорной позиции определенных на операции 700, из блока хранения картографических данных 620 без загрузки всех картографических данных, с двухмерными координатами, хранящихся в блоке хранения картографических данных 620. Таким образом, достигается основное отсечение.

Во время следующей операции 750 выполняют процесс трехмерного моделирования по преобразованию загруженных картографических данных, с двухмерными координатами, в картографические данные, с трехмерными координатами. Процесс трехмерного моделирования на операции 750 состоит из следующих операций. Базовую карту трехмерной карты с трехмерными координатами формируют на основе загруженных картографических данных, с двухмерными координатами (операция 751). Например, устанавливают линии для дорог, зеленых зон, рек, озер и т.п.Задают высоты вершин для соответствующих строений (операция 752). Формируют строения заданной высоты (операция 753), после чего при помощи стрелок или пунктирных линий формируют маршрут перемещения транспортного средства (операция 754).

При этом процесс загрузки картографических данных, с двухмерными координатами на операции 740 и процесс трехмерного моделирования на операции 750 описаны посредством примера в сочетании с тем вариантом, когда картографические данные, с двухмерными координатами, преобразуют в картографические данные, с трехмерными координатами, в навигационной системе. Однако, что касается игр или аналогичных, где отображают трехмерные изображения, то, поскольку данные трехмерных моделей предварительно сохраняют в памяти, данные трехмерных моделей для конкретной области в координатах исходного положения можно загрузить непосредственно из памяти без выполнения процесса загрузки картографических данных с двухмерными координатами на операции 740, и процесса трехмерного моделирования на операции 750.

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

Когда процесс преобразования точки обзора полностью завершен на операции 760, блок управления 640 выполняет вторичный процесс отсечения и удаляет элементы, находящиеся вне трехмерного отображаемого объема, как показано на фиг.7b (операция 770).

При выполнении вторичного отсечения на операции 770 значения k1 по оси z для всех узлов, составляющих трехмерное изображение, сравнивают со значением k по оси z для плоскости отсечения, узлы, которые по результатам сравнения удовлетворяют условию k1≥k, определяют как узлы, находящиеся внутри отображаемого объема, а узлы, удовлетворяющие условию k1<k, определяют как узлы, находящиеся вне отображаемого объема (операция 771). Затем путем соответствующего сравнения узлов на всех линиях определяют, где находятся узлы - вне или внутри отображаемого объема, в то время как узлы линий последовательно ищут, посредством чего выполняют вторичный процесс отсечения (операция 772).

Во время вторичного процесса отсечения на операции 772 определяют, находятся ли все узлы, составляющие линию, вне отображаемого объема (операция 772-10), и находятся ли все узлы, составляющие линию, внутри отображаемого объема (операция 772-20).

Если на операции 772-10 определяют, что все узлы, составляющие линию, находятся вне отображаемого объема, блок управления 640 удаляет линию, находящуюся вне отображаемого объема (операция 772-30), и определяет, все ли линии полностью найдены (операция 772-60). Если определяют, что не все линии полностью найдены, происходит возврат к операции 772-10, так что можно повторно выполнять операцию определения того, находятся ли все узлы, составляющие линию, вне или внутри отображаемого объема.

Если на операции 772-20 определяют, что все узлы, составляющие линию, находятся внутри отображаемого объема, блок управления 640 определяет соответствующую линию как линию, отображаемую на панели дисплея 660 (операция 772-50). Затем блок управления 640 определяет, все ли линии полностью найдены (операция 772-60). Если определяют, что не все линии полностью найдены, происходит возврат к операции 772-10, так что можно повторно выполнять операцию определения того, находятся ли все узлы, составляющие линию, вне или внутри отображаемого объема.

Однако если при выполнении операции 772-10 определяют, что все узлы, составляющие линию, необязательно находятся вне отображаемого объема и на операции 772-20 определяют, что все узлы необязательно находятся внутри отображаемого объема, это означает, что линия пересекает плоскость отсечения. Блок управления 640 изменяет структуру линии, пересекающей плоскость отсечения, для формирования линии с новой структурой (операция 772-40).

Что касается формирования линии с новой структурой на операции 772-40, области памяти назначают по координатам узлов сформированной линии, которые будут храниться в памяти (операция 772-41). Звенья линии последовательно ищут в порядке размещения узлов, а координаты узлов линии с новой структурой определяют и сохраняют в распределенных областях памяти (операция 772-42).

Координаты узлов линии с новой структурой на операции 772-42 определяют следующим образом.

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

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

При этом расчет координат точки пересечения плоскости отсечения и звена производят следующим образом.

Как показано на фиг.8, если допустить, что звено 820 линии, соединяющей узел A(x1, y1, z1) и узел В(х2, у2, z2), пересекает плоскость отсечения 810, размещенной на позиции со значением k по оси z относительно положения центра проекции 800, т.е. точки обзора О(0, 0, 0), координаты точки пересечения Р(x, у, z) плоскости отсечения 810 и звена 820 можно получить из следующего уравнения 1:

При этом, поскольку значение по оси z плоскости отсечения 810 - это k, параметр t можно получить из следующего уравнения 2:

Затем координаты точки пересечения Р(x, у, z) плоскости отсечения 810 и звена 820 можно выразить при помощи следующей системы уравнений 3:

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

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

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

Т.е., согласно настоящему изобретению, произвольную плоскость отсечения 920 со значением k координаты по оси z формируют между положением центра проекции 900 и плоскостью проекции 910, а отсечение линии выполняют по плоскости отсечения 920, как показано на фиг.9. В этот момент на линии 930, состоящей из узлов v0, v1, v2, v3, v4, v5 и v6, узлы v2 и v3, находящиеся вне плоскости отсечения 920, удаляют, определяют точки пересечения ve2 и ve3 между линией 930 и плоскостью отсечения 920 и затем формируют линию с новой структурой, состоящей из узлов v0, v1, ve2, ve3, v4,v5 и v6.

Когда на операции 772-40 полностью завершают формирование линии с новой структурой, блок управления 640 определяет, что линия с новой структурой - это линия, подлежащая отображению на панели дисплея 660 (операция 772-50), после чего определяет, все ли линии полностью найдены (операция 772-60). Если определено, что не все линии полностью найдены, происходит возврат к операции 772-10, так что может повторно выполняться операция отсечения линии с определением того, находятся ли все узлы, составляющие линию, вне или внутри отображаемого объема.

Если на операции 772-60 определено, что все линии полностью найдены, блок управления 640 удаляет все элементы, которые находятся вне отображаемого объема, из числа многоугольников и географических названий для трехмерного изображения (операция 773) и удаляет перекрывающиеся и скрытые трехмерные стороны (операция 774). Таким образом, выполняют вторичный процесс отсечения.

Когда на операции 770 завершают вторичный процесс отсечения, блок управления 640 выполняет процесс преобразования проецирования (операция 780).

Процесс преобразования проецирования на операции 780, состоит из следующих операций. Трехмерные координаты соответствующих узлов, преобразованные в систему координат на основе точки обзора, подлежат преобразованию на плоскость проекции для получения двухмерных координат (операция 781), и двухмерные координаты, спроецированные на плоскость проекции, т.е. координаты проецирования, преобразуют в экранные координаты (операция 782).

Затем выполняют процесс отображения по отображению трехмерной карты на панели дисплея 660 (операция 790). Процесс отображения, выполняемый на операции 790, состоит из следующих операций. Многоугольники и ломаные линии для плоских объектов, таких как дороги, зеленые зоны, реки и озера, отображают на панели дисплея 660 (операция 791), ломаные линии для маршрута перемещения транспортного средства отображают на панели дисплея 660 (операция 792), ломаные линии для соответствующих трехмерных строений отображают на панели дисплея 660 (операция 793), а текстовые данные, такие как географические названия, затем выводят и отображают на панели дисплея 660 (операция 794).

На фиг.10а и 10b показаны блок-схемы, иллюстрирующие процесс преобразования двухмерной карты в трехмерную карту и отображения трехмерной карты на экране с использованием приближенного отсечения линий согласно другому примеру осуществления способа отсечения линии по настоящему изобретению. Как показано на чертеже, после процесса преобразования точки обзора на операции 760 (фиг.7а) блок управления 640 выполняет вторичный процесс отсечения для удаления всех трехмерных элементов, находящихся вне отображаемого объема (операция 1000).

При выполнении вторичного процесса отсечения (операция 1000) значения k1 по оси z всех узлов, составляющих трехмерное изображение, сравнивают со значением k по оси z для плоскости отсечения, узлы, которые по результатам сравнения удовлетворяют условию k1≥k, определяют как узлы, находящиеся внутри отображаемого объема, а узлы, удовлетворяющие условию k1<k, определяют как узлы, находящиеся вне отображаемого объема (операция 1001). Затем путем соответствующего сравнения узлов для всех линий определяют, где находятся узлы - вне или внутри отображаемого объема, в то время как линии последовательно ищут, посредством чего выполняют вторичный процесс отсечения (операция 1002).

Во время вторичного процесса отсечения на операции 1002 определяют, находятся ли все узлы, составляющие линию, вне отображаемого объема (операция 1002-1), и находятся ли такие узлы внутри отображаемого объема (операция 1002-2).

Если при выполнении операции 1002-1 определено, что все узлы, составляющие линию, находятся вне отображаемого объема, блок управления 640 удаляет соответствующую линию (операция 1002-3) и определяет, все ли линии полностью найдены (операция 1002-6). Если определено, что не все линии полностью найдены, происходит возврат к операции 1002-1, так что можно повторно выполнять операцию выбора следующей линии и определения того, находятся ли все узлы, составляющие линию, вне или внутри отображаемого объема.

Если на операции 1002-2 определено, что все узлы, составляющие линию, находятся внутри отображаемого объема, блок управления 640 определяет соответствующую линию как линию, подлежащую отображению на панели дисплея 660 (операция 1002-5). Затем блок управления 640 определяет, все ли линии полностью найдены (операция 1002-6). Если определено, что не все линии полностью найдены, происходит возврат к операции 1002-1, так что можно повторно выполнять операцию выбора следующей линии и определения того, находятся ли все узлы, составляющие линию, вне или внутри отображаемого объема.

Однако, если на операциях 1002-1 и 1002-2 определено, что все узлы, составляющие линию необязательно находятся вне или внутри отображаемого объема, это означает, что соответствующая линия пересекает плоскость отсечения. Блок управления 640 изменяет структуру линии, пересекающей плоскость отсечения, для формирования линии с новой структурой (операция 1002-4).

На фиг.11 показана блок-схема, иллюстрирующая пример процесса формирования новой линии на операции 1002-4. Как показано на фигуре, блок управления 640 последовательно ищет узлы, составляющие линию, и определяет число узлов, находящихся внутри отображаемого объема (операция 1100), назначает области памяти в зависимости от определенного числа узлов (операция 1110) и формирует новую линию (операция 1120).

При формировании новой линии (операция 1120) выбирают первый узел линии (операция 1121) и определяют, находится ли выбранный первый узел внутри отображаемого объема (операция 1122). Если выбранный первый узел находится внутри отображаемого объема, координаты узла сохраняют в памяти (операция 1123). Если выбранный первый узел не находится внутри отображаемого объема, его координаты не сохраняют в памяти.

Затем определяют, существует ли следующий узел (операция 1124). Если определено, что следующий узел существует, выбирают следующий узел (операция 1125) и происходит возврат к операции 1122, так что операция сохранения координат выбранного узла в памяти повторяют в зависимости от того, находится ли выбранный узел внутри отображаемого объема. Если при выполнении операции 1124 определено, что следующий узел отсутствует, происходит возврат к операции 1002-5.

В этом примере осуществления настоящего изобретения, в котором формируют новую линию, например, на линии, состоящей из семи узлов v0, v1, v2, v3, v4, v5 и v6, показанной на фиг.12а, определяют четыре узла v0, v1, v5 и v6, находящиеся внутри плоскости отсечения 1200, т.е. внутри отображаемого объема. Затем области памяти 1210, в которой будут сохранены координаты четырех узлов, распределяют, как показано на фиг.12b. Координаты ve0, ve1, ve5 и ve6 узлов v0, v1, v5 и v6 сохраняют в распределенных областях памяти 1210 соответственно, для формирования линии с новой структурой.

На фиг.13 блок-схема, иллюстрирует другой пример процесса формирования новой линии на операции 1002-4. Как показано на фигуре, блок управления 640 последовательно ищет все узлы, составляющие линию, и временно сохраняет в памяти координаты узла, который является первым внутри отображаемого объема (операция 1300), и формирует новую линию путем последовательного поиска соответствующих узлов, составляющих линию (операция 1310).

При формировании новой линии на операции 1310 узлы последовательно выбирают по одному, т.е. выбирают первый узел (операция 1311), и определяют, находится ли выбранный узел вне отображаемого объема (операция 1312). Если определено, что выбранный узел не находится вне отображаемого объема, но находится внутри отображаемого объема, координаты соответствующего узла напрямую записывают в память (операция 1313).

Если при выполнении операции 1312 определено, что выбранный узел находится вне отображаемого объема, блок управления 640 определяет, является ли выбранный узел начальным узлом линии (операция 1314). Если определено, что выбранный узел является начальным узлом, временно сохраненные координаты узла, т.е. координаты того узла линии, который находится внутри отображаемого объема, сохраняют как координаты начального узла (операция 1315). Если при выполнении операции 1314 определено, что выбранный узел не является начальным узлом, координаты предшествующего узла копируют как координаты текущего узла и сохраняют в памяти (операция 1316).

Затем определяют, существует ли следующий узел (операция 1317). Если определено, что следующий узел существует, происходит возврат к операции 1311, в результате чего выбирают следующий узел и описанную выше процедуру повторяют.

В этом примере настоящего изобретения, в котором формируют новую линию, последовательно ищут, например, семь узлов v0-v6, составляющих линию 1410, пересекающую плоскость отсечения 1400, как показано на фиг.14а. Что касается узлов v0, v1, v5 и v6, находящихся внутри отображаемого объема, координаты ve0, ve1, ve5 и ve6 узлов v0, v1, v5 и v6 напрямую записывают в память 1420, как показано на фиг.14b. Что касается узлов v2, v3 и v4, находящихся вне отображаемого объема, координаты ve1 узла v1, являющегося предшествующим узлом, находящимся внутри отображаемого объема, последовательно копируют как координаты этих узлов и сохраняют.

Однако, если начальный узел v0 на линии 1510, состоящей из семи узлов v0-v6 и пересекающей плоскость отсечения 1500, является узлом, находящимся вне отображаемого объема, как показано на фиг.15а, ищут узел v2, являющийся первым из узлов v0-v6 узлом, находящимся внутри отображаемого объема, для линии 1510, а координаты ve2 узла v2 копируют как координаты узла v0 и сохраняют в памяти 1520, как показано на фиг.15b. Координаты узла ve2, сохраненные как координаты узла v0, копируют как координаты узла v1, находящегося вне отображаемого объема, а затем сохраняют в памяти. Кроме того, координаты ve2 узла v2 последовательно копируют как координаты узлов v3 и v4, находящихся вне отображаемого объема, а затем сохраняют. В результате формируют линию с новой структурой.

Когда завершен процесс формирования линии с новой структурой на операции 1002-4, блок управления 640 определяет сформированную линию с новой структурой как линию, подлежащую отображению на панели дисплея 660 (операция 1002-5). Блок управления 640 определяет, все ли линии полностью найдены (операция 1002-6). Если определено, что не все линии полностью найдены, происходит возврат к операции 1002-1. Затем повторяют операцию выбора следующей линии и определения того, находятся ли все узлы, составляющие линию, вне или внутри отображаемого объема.

Если на операции 1002-6 определено, что все линии полностью найдены, блок управления 640 удаляет все элементы, находящиеся вне отображаемого объема, среди всех многоугольников и географических названий для трехмерного изображения (операция 1003) и удаляет перекрывающиеся и скрытые трехмерные стороны (операция 1004). Таким образом, выполняют вторичный процесс отсечения.

Когда завершают вторичный процесс отсечения на операции 1000, блок управления 640 выполняет процесс преобразования проецирования (операция 1010).

Процесс преобразования проецирования, выполняемый на операции 1010, состоит из следующих операций. Трехмерные координаты соответствующих узлов, преобразованные в систему координат на основе точки обзора, подлежат преобразованию на плоскость проекции для получения двухмерных координат (операция 1011), и двухмерные координаты, спроецированные на плоскость проекции, т.е. координаты проецирования, преобразуют в экранные координаты (операция 1012).

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

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

Затем выполняют процесс отображения трехмерной карты на панели дисплея 660 (операция 1020). Процесс отображения, выполняемый на операции 1020, состоит из следующих операций. Многоугольники и ломаные линии для плоских объектов, таких как дороги, зеленые зоны, реки и озера, отображают на панели дисплея 660 (операция 1021), ломаные линии для маршрута перемещения транспортного средства отображают на панели дисплея 660 (операция 1022), ломаные линии для соответствующих трехмерных строений отображают на панели дисплея 660 (операция 1023), и текстовые данные, такие как географические названия, затем выводят и отображают на панели дисплея 660 (операция 1024).

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

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

1. Способ отсечения линии, включающий

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

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

2. Способ по п.1, отличающийся тем, что операция отсечения линии включает операции:

(a) назначения областей памяти для хранения координат узлов новой линии;

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

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

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

(e) сохранения узлов новой линии, определенных на операциях (b)-(d), в соответствующих областях памяти, назначенных на операции (а).

3. Способ отсечения линии, включающий

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

4. Способ по п.3, отличающийся тем, что операция отсечения линии включает операции:

(а′) определение числа узлов, находящихся внутри отображаемого объема, среди узлов линии;

(b') назначение областей памяти для хранения координат узлов, число которых определено на операции (а′); и

(с′) построение новой линии путем сохранения координат узлов, находящихся внутри отображаемого объема, определенных на операции (а′) в соответствующих областях памяти, назначенных на операции (b').

5. Способ по п.3, отличающийся тем, что в процессе операции отсечения линии

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

(b′′) последовательно выбирают соответствующие узлы линии и определяют, находятся ли эти узлы внутри или вне отображаемого объема;

(с′′) сохраняют координаты узлов в соответствующих областях памяти, если на операции (b′′) определено, что узлы находятся внутри отображаемого объема;

(d′′) определяют, является ли один из узлов начальным узлом линии, если на операции (b′′) определено, что узлы находятся вне отображаемого объема;

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

(f′′) копируют координаты непосредственно предшествующего узла, сохраненные в памяти на операции (с′′) или (е′′), в соответствующую область памяти для координат текущего узла, если на операции (d′′) определено, что один из узлов не является начальным узлом линии.

6. Способ отображения трехмерного изображения с использованием отсечения линии, включающий

операцию инициализации трехмерной среды для инициализации среды отображения трехмерного изображения

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

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

операцию ввода трехмерного изображения для ввода трехмерного изображения области на основе координат исходного положения;

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

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

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

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

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

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

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

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

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

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

11. Способ по п.6, отличающийся тем, что воспроизведение линии на операции отсечения линии включает в себя

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

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

12. Способ по п.11, отличающийся тем, что плоскость отсечения размещают между центром проекции и плоскостью проекции.

13. Способ по п.11, отличающийся тем, что операция отсечения линии включает в себя операции:

(a) назначение областей памяти для хранения координат узлов новой линии;

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

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

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

(e) сохранение узлов новой линии, определенных на операциях (b)-(d), в соответствующих областях памяти, назначенных на операции (а).

14. Способ по п.6, отличающийся тем, что воспроизведение линии на операции отсечения линии включает в себя

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

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

15. Способ по п.14, отличающийся тем, что плоскость отсечения размещают между центром проекции и плоскостью проекции.

16. Способ по п.14, отличающийся тем, что операция отсечения линии включает в себя операции:

(а′) определение числа узлов, находящихся внутри отображаемого объема, среди узлов линии;

(b') назначение областей памяти для хранения координат узлов, число которых определено на операции (а′); и

(с′) строят новую линию путем сохранения в соответствующих областях памяти, назначенных на операции (b'), координат находящихся внутри отображаемого объема узлов, определенных на операции (а′).

17. Способ по п.16, отличающийся тем, что в процессе операции отсечения линии

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

(b′′) последовательно выбирают соответствующие узлы линии и определяют, находятся ли эти узлы внутри или вне отображаемого объема;

(с′′) сохраняют координаты узлов в соответствующих областях памяти, если на операции (b′′) определено, что узлы находятся внутри отображаемого объема;

(d′′) определяют, является ли один из узлов начальным узлом линии, если на операции (b′′) определено, что узлы находятся вне отображаемого объема;

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

(f′′) копируют координаты непосредственно предшествующего узла, сохраненные в памяти на операции (с′′) или (е′′), в соответствующую область памяти для координат текущего узла, если на операции (d′′) определено, что один из узлов не является начальным узлом линии.

18. Способ отображения трехмерного изображения с использованием отсечения линии, включающий

операцию инициализации трехмерной среды для инициализации среды для отображения трехмерного изображения;

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

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

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

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

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

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

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

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

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

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

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

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

и настройки заданного цвета в качестве цвета фона экрана.

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

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

23. Способ по п.18, отличающийся тем, что воспроизведение линии на операции отсечения линии, включает в себя

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

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

24. Способ по п.23, отличающийся тем, что плоскость отсечения размещают между центром проекции и плоскостью проекции.

25. Способ по п.23, отличающийся тем, что операция отсечения линии включает в себя операции:

(a) назначение областей памяти для хранения координат узлов новой линии;

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

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

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

(e) сохранение узлов новой линии, определенных на операциях (b)-(d), в соответствующих областях памяти, назначенных на операции (а).

26. Способ по п.18, отличающийся тем, что воспроизведение линии на операции отсечения линии включает в себя

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

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

27. Способ по п.26, отличающийся тем, что плоскость отсечения размещают между центром проекции и плоскостью проекции.

28. Способ по п.26, отличающийся тем, что операция отсечения линии включает в себя операции:

(а′) определение числа узлов, находящихся внутри отображаемого объема, среди узлов линии;

(b') назначение областей памяти для хранения координат узлов, число которых определено на операции (а′); и

(с′) строят новую линию путем сохранения в соответствующих областях памяти, назначенных на операции (b'), координат находящихся внутри отображаемого объема узлов, определенных на операции (а′).

29. Способ по п.26, отличающийся тем, что в процессе операции отсечения линии

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

(b′′) последовательно выбирают соответствующие узлы линии и определяют, находятся ли эти узлы внутри или вне отображаемого объема;

(с′′) сохраняют координаты узлов в соответствующих областях памяти, если на операции (b′′) определено, что узлы находятся внутри отображаемого объема;

(d′′) определяют, является ли один из узлов начальным узлом линии, если на операции (b′′) определено, что узлы находятся вне отображаемого объема;

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

(f′′) копируют координаты непосредственно предшествующего узла, сохраненные в памяти на операции (с′′) или (е′′), в соответствующую область памяти для координат текущего узла, если на операции (d′′) определено, что один из узлов не является начальным узлом линии.

30. Способ отображения трехмерного изображения с использованием отсечения линии, включающий

операцию инициализации трехмерной среды для инициализации среды для отображения трехмерного изображения;

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

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

операцию ввода трехмерной модели для ввода трехмерного изображения с трехмерными координатами для области на основе координат исходного положения;

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

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

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

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

31. Способ отображения трехмерного изображения с использованием отсечения линии, включающий

операцию инициализации трехмерной среды для инициализации среды для отображения трехмерного изображения;

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

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

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

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

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

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

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

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

Приоритет: 01.12.2003 - пп.1-31.