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

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

Иллюстрации

Показать все

Реферат

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

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).

Во время вторичного проц