Способ отсечения графического материала в системе обработки графических данных и устройство обработки графических данных

 

Изобретение относится к вычислительной технике. Его использование при создании систем, воспроизводящих графику, позволяет упростить решение задачи вычерчивания линии замыкания вдоль края окна. Способ включает в себя прослеживание по границе элемента для определения точки выхода (EX), в которой граница элемента пересекает границу окна и выходит за просмотровое окно, и прослеживание по границе элемента для определения точки входа (EN), в которой граница элемента пересекает границу окна и входит в просмотровое окно. Технический результат достигается благодаря тому, что определяют, пересекает ли воображаемая линия 12, начинающаяся в данной точке P на границе окна и уходящая от нее на фактически бесконечное расстояние, участок границы элемента вне просмотрового окна между точкой выхода и точкой входа нечетное число раз или четное число раз, и если воображаемая линия пересекает участок нечетное число раз, строят замыкающую линию по границе окна между точкой выхода и точкой входа, проходящую через заранее заданную точку на границе окна, а если воображаемая линия пересекает участок четное число раз, строят замыкающую линию по границе окна между точкой выхода и точкой входа, не проходящую через заранее заданную точку. Устройство снабжено соответствующими средствами для выполнения этих операций. 2 с. и 8 з. п. ф-лы, 7 ил.

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

В большинстве систем, воспроизводящих графику, возникает необходимость отсечения графических данных. Примером такой системы является программа фирмы IBM Graphical Data Display Manager (GDDM) (администратор отображения графической информации), производимая IBM Corporation (GDDM и IBM - товарные знаки International Business Machines Corporation). Программа GDDM выполняется в системе, включающей главный компьютер, к которому подсоединен ряд терминалов. Главный компьютер хранит и обрабатывает графическую информацию и затем передает ее к соответствующему терминалу для отображения. Эти операции системы выполняются под контролем программы GDDM. Одной из функций, которую должна выполнять такая программа, как программа GDDM, является отсечение графического изображения.

Существует ряд известных методов отсечения зон графического изображения, ограниченных своей границей, до так называемых смотровых окон или просмотровых (демонстрационных) окон экрана, например алгоритм Sutherland-Hodgeman, алгоритм Weiler-Atherton. Рассмотрение этих методов можно найти в книге Foley. J. D. , Van Dam A., Fundamentals of Interactive Computer Graphics (Основы интерактивной машинной графики) изд. Addison Wesley, 1982, с. 450 - 457.

Алгоритм Sutherland-Hodgeman работает по принципу, при котором просмотровое окно рассматривается как состоящее из совокупности уходящих в бесконечность линий отсечения. Задача отсечения рассматриваемого многоугольника по единичной уходящей в бесконечность линии отсечения сравнительно простая. Собирая результаты успешных отсечений по данным линиям отсечения, можно определить часть многоугольника, подлежащую отображению. Одна из возникающих проблем касается определения того, как вычертить так называемые линии замыкания между точками на границе многоугольника, полученными в тех местах, где он пересекает просмотровое окно. Стандартный алгоритм Sutherland-Hodgeman дает посторонние (чуждые) линии замыкания, которые следует убрать с помощью дополнительных шагов обработки (данных). Необходимость этой дополнительной обработки для исключения посторонних ребер уменьшает эффективность отсечения.

В качестве альтернативы используется алгоритм Weiler-Atherton. Действие этого алгоритма заключается в трассировке вокруг границы рассматриваемого многоугольника в направлении по часовой стрелке до тех пор, пока не произойдет пересечения с просмотровым окном. Если сторона многоугольника входит в просмотровое окно, алгоритм далее идет вдоль стороны рассматриваемого многоугольника. Если сторона многоугольника покидает просмотровое окно, алгоритм делает первый поворот и следует по краю просмотрового окна. В любом случае пересечение запоминается и используется для того, чтобы точно гарантировать однократное прослеживание по всем траекториям. Несмотря на то что в алгоритме Weiler-Atherton не возникает проблемы, связанной с образованием посторонних линий замыкания, он более сложен, чем алгоритм Sutherland-Hodgeman, что нерационально.

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

С одной стороны, в соответствии с изобретением разработан способ отсечения графического элемента, имеющего границу элемента, до просмотрового окна, имеющего границу окна, в системе обработки графических данных, включающий прослеживание по указанной границе элемента с целью определения точки выхода (EX), в которой указанная граница элемента пересекает указанную границу окна и выходит за указанное просмотровое окно, и прослеживание по указанной границе элемента с целью определения точки входа (EN), в которой указанная граница элемента пересекает указанную границу окна и входит в указанное просмотровое окно, отличающийся тем, что определяется, пересекает ли воображаемая линия, начинающаяся в заданной точке (P) на указанной границе окна уходящая от нее на фактически бесконечное расстояние, данный участок указанной границы элемента вне указанного просмотрового окна между указанной точкой выхода и указанной точкой входа нечетное число раз или четное число раз, и/или (1) если указанная воображаемая линия пересекает указанный участок нечетное число раз, вычерчивается линия замыкания вдоль указанной границы окна между указанной точкой выхода и указанной точкой входа, проходящая через указанную заданную точку на указанной границе окна, или (2) если указанная воображаемая линия пересекает указанный участок четное число раз, вычерчивается линия замыкания вдоль указанной границы окна между указанной точкой выхода и указанной точкой входа, не проходящая через указанную заданную точку.

По изобретению предусмотрен способ, при котором после определения точек выхода и входа может выдаваться верная линия замыкания. Можно было бы использовать вариант алгоритма Sutherland-Hodgeman для определения точек выхода и входа, а изобретение тогда решало бы задачу определения того, каким образом вычертить линию замыкания вдоль границы окна. Такой процесс отсечения не имел бы недостатка обычного алгоритма Sutherland-Hodgeman, связанного с порождением ошибочных линий, замыкания, которые следует убирать с помощью последующих дополнительных шагов обработки данных. Кроме того, такой процесс отсечения не имел бы нежелательной сложности, которая неизбежна при использовании алгоритма Weiler-Atherton. Ни в одном из способов отсечения по предшествующему техническому уровню не контролируется заданная точка на границе окна для определения того, как вычертить линию замыкания.

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

Также рационально, если можно было бы подсчитать общее число пересечений и проверить, является ли оно нечетным или четным, но равным образом возможно, что одноразрядный флажок устанавливается в 1 или 0 при каждом пересечении, фиксируя таким образом только четность числа пересечений. Также рационально, если указанная фактическая уходящая в бесконечность линия могла бы быть прямой (кривой), изогнутой или петлеобразной, но при предпочтительно простых исполнениях использовалась бы прямая линия.

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

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

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

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

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

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

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

На фиг. 1 имеется графический элемент 2 и просмотровое окно 4. Графический элемент 2 имеет границу 6 элемента. Просмотровое окно 4 имеет границу 8 окна. Участок границы 6 элемента, находящийся внутри просмотрового окна 4, один и тот же как в случае А, так и в случае В. Начиная в точке на границе 6 элемента, которая находится внутри просмотрового окна 4, и выполняя прослеживание по границе 6 элемента, система сначала определяет точку выхода EX, в которой граница 6 элемента пересекает границу 8 окна и выходит за пределы просмотрового окна 4. Выполняя дальнейшее прослеживание по границе 6 элемента, система определяет точку входа EN, в которой граница 6 элемента пересекает границу 8 окна и входит в пределы просмотрового окна 4.

Участок границы 6 элемента внутри просмотрового окна 4 и положение точки выхода EX и точки входа EN одинаковы в обоих случаях. Система должна некоторым образом определить, где вычертить линию замыкания 10. Линию замыкания 10 можно было вычертить вдоль границы 8 окна непосредственно от точки EX до EN, или ее можно было бы вычертить вдоль границы 8 окна от точки EX до точки EN через углы b, c, d и a. Как можно видеть при анализе случая А, правильная траектория лежит непосредственно между точкой EX и точкой EN, в то время как в случае В правильная траектория проходит через углы b, c, d и a.

Чтобы отличить эти два случая, система проверяет, сколько раз фактически уходящая в бесконечность воображаемая линия 12 пересекает участок границы 6 элемента за пределами просмотрового окна 4 между точкой выхода EX и точкой входа EN. В случае А проверка дает нулевое (четное) число пересечений, показывающее, что линия замыкания не должна проходить через точку P, т.е. линия замыкания 10 вычерчивается вдоль границы 8 окна непосредственно от точки EX до точки EN. В случае В проверка дает одно (нечетное) пересечение, показывающее, что линия замыкания 10 должна проходить через точку P, т.е. линия замыкания 10 вычерчивается вдоль границы 8 окна через углы b и c, точку P и углы d и a.

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

Граница 6 элемента определена списком команд/векторов, например, начальная область, вектор 1, вектор 2,..., конечная область. Векторы могут быть представлены в виде координат начала и конца, кривые могут быть заданы начальной точкой, конечной точкой и кривизной или любым другим удобным способом представления. Прослеживание по границе 6 элемента включает обработку сверху вниз списка векторов и определение для каждого вектора того, пересекает ли линия, которую он задает, границу окна. Последовательное считывание векторов, их отсечение относительно просмотрового окна 4 и их отображение на дисплее в отсеченном виде известны из предшествующего технического уровня, например из программы GDDM. К известному процессу отсечения добавляются дополнительные шаги обработки данных для определения верной линии замыкания 10. Когда верная линия замыкания определена, она добавляется к строке отсеченных векторов, пересылаемой из главного процессора дисплею.

Фиг. 2 показывает действие изобретения в случае более сложной конфигурации графического элемента 2. Задача системы состоит в том, чтобы выполнить прослеживание по участку границы 6 элемента за пределами просмотрового окна 4 между точкой выхода EX и точкой входа EN, чтобы определить число пересечений данного участка границы 6 элемента с воображаемой линией 12, фактически уходящей в бесконечность от точки Р.

Рассматривая точку P и линию 12, как показано на фигуре, можно обнаружить три пересечения в точках i1, i2, и i3. Это нечетное число пересечений показывает, что линия замыкания 10 должна проходить через точку Р. Как можно видеть, этот результат соответствует данной заданной точке Р. Также показаны точка P' и линия 12'. Здесь имеются два пересечения линии 12 в точках i4 и i5. Это показывает, что линия замыкания 10 не должна проходить через точку P'. Снова можно видеть, что это корректный результат для точки P'.

Фиг. 3 показывает предпочтительный способ проверки, показанной на фиг. 2. Фактически уходящая в бесконечность линия 12 представляет собой продолжение одной из сторон просмотрового окна 4. Точка P совпадает с углом b. Это решение предпочтительно, так как при определении точки выхода и точки входа с помощью известных методов пересечения границы 6 элемента и уходящей в бесконечность линии, включающей сторону просмотрового окна, будут уже определены. В случае, если граница 6 элемента дает пересечение i1, линия замыкания будет проходить через точку P, а если граница 6 элемента не дает пересечений, линия замыкания не будет проходит через точку Р.

Фиг. 4 показывает, как система работает в том случае, если границы элементов касаются линии 12, но не пересекают ее. Участок границы 6 элемента или подходящий к линии 12 и затем касающийся ее, или касающийся и затем уходящий от линии 12 с первой стороны 14 от линии 12, рассматривается как пересекающий линию. Соответственно считается, что графический элемент 22 пересекает линию 12 дважды. Участок 18 границы 6 элемента, который касается и затем уходит от линии 12, рассматривается как пересекающий линию.

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

Фиг. 4 показывает, что система работает в ситуации, когда заданная точка P совпадает или с точкой выхода EX или с точкой входа EN. Точка P рассматривается как часть линии 12, а правило, определяющее, пересечена ли линия 12 границей 6 элемента, то же, что и выше. Правило определения того, проходит ли линия замыкания 10 через точку P, должно быть сделано согласующимся с правилом определения того, пересекает ли граница 6 элемента линию 12. Линия замыкания 10 с концом, совпадающим с точкой P, рассматривается как проходящая через точку P, если линия замыкания 10 имеет участок, который ведет к точке P или от точки P с первой стороны 14 от линии 12. Участок, ведущий к точке P или от точки P с второй стороны 16, не рассматривается как проходящий через точку P.

Соответственно на фиг. 5 графический элемент 26 имеет границу 6 элемента, которая рассматривается как пересекающая линию 12, поскольку он имеет участок границы 6 элемента, который касается и затем уходит от линии 12 с первой стороны 14. В показанном случае проверка определения того, находится ли точка P внутри (в пределах) графического элемента 26, дает, что точка P находится внутри графического элемента 26 и линия замыкания 10 должна проходить через точку P. Линия замыкания 10, вычерченная непосредственно из точки EX до точки EN, будет рассматриваться как проходящая через точку P, так как участок линии замыкания 10 ведет от точки P с первой стороны 14. Следовательно образуется верная линия замыкания.

Напротив, графический элемент 28 имеет границу 6 элемента, которая рассматривается как не пересекающая линию 12, так как участок границы 6 элемента, который касается линии 12 и затем уходит от нее с второй стороны 16, рассматривается как не пересекающий линию 12. При нулевом (четном) числе пересечений определяется, что точка P находится вне графического элемента 28, и следует вычертить линию замыкания 10, не проходящую через точку P. Линия замыкания 10, проходящая от точки EX до точки EN через углы b, c, d и a, рассматривается как не проходящая через точку P, поскольку участок, уходящий от точки P, делает это с второй стороны 16. Снова образуется верная линия замыкания.

Фиг. 6 представляет собой укрупненную блок-схему, показывающую работу одного из вариантов воплощения изобретения. На шаге 32 определяются точки, в которых граница элемента выходит из просмотрового окна и входит в него. На шаге 33 проверяется, равно ли число таких пересечений нулю. Если да, то это означает, что или графический элемент полностью находится внутри просмотрового окна, или просмотровое окно полностью находится внутри графического элемента. Эти две ситуации различаются с помощью шага 34, на котором подсчитывается число пересечений воображаемой линии. Это число или рано нулю (четное - графический элемент внутри просмотрового окна), или равно одному, трем, пяти,... (нечетное - просмотровое окно внутри графического элемента). Если это число четное, то не требуется никакой линии замыкания и графический элемент вычерчивается внутри просмотрового окна (шаг 35). Если это число нечетное, тогда линия замыкания вычерчивается вдоль всей границы окна (шаг 36).

Если на шаге 33 были определены точки входа и выхода, тогда на шаге 37 вычерчиваются те участки границы элемента, которые находятся внутри окна. На шаге 37 идентифицируются точка выхода и точка входа, которая непосредственно следует за ней. Это осуществляется путем выполнения трассировки вокруг границы элемента от начальной точки на границе, которая может находиться внутри или снаружи границы элемента. Если начальная точка находится внутри просмотрового окна, тогда сначала будут определены точка выхода и соответствующая ей точка входа. На шаге 39 определяется число пересечений, а шаги 40 и 41 или 42 обеспечат вычерчивание верной линии замыкания. Однако, если начальная точка находится вне просмотрового окна, тогда первое пересечение границы окна будет в точке входа. Соответствующая ей точка выхода (для целей построения линии замыкания) будет последней точкой выхода, которую достигают перед возвратом к линии замыкания. Чтобы избежать ненужного повторения, определяется число пересечений воображаемой линии между начальной точкой и первой точкой входа, оно запоминается и складывается с числом пересечений между последней точкой выхода и возвратом к начальной точке. Затем производится проверка направления линии замыкания таким образом, как и ранее. В итоге на шаге 43 проверяется, все ли линии замыкания вычерчены, и если нет, то происходит возврат к шагу 38.

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

Фиг. 7 схематично показывает пример вычислительной системы, в которой может быть реализовано данное изобретение. Все, что показано на фиг. 7, может быть названо устройством 48 обработки графических данных. Это устройство состоит из центрального универсального компьютера 68, управляющего рядом дисплеев/терминалов 50 и 52. Компьютер 68 включает центральный процессор 54, хранящуюся в памяти программу обработки графических данных (GDDM) 56 и хранящиеся в памяти графические данные (графические элементы, состоящие из списков векторов) 58, подлежащие обработке и отображению на дисплее. Центральный процессор 54, работая под управлением от программы 56, служит в качестве логической схемы отсечения, выполняющей требуемое отсечение графических элементов 64 и 66, которые нужно воспроизвести на дисплеях 50 и 52. Как показано, различные графические элементы 64 и 66 отсекаются с помощью логической схемы отсечения 54 и 56 таким образом, что отображаются только те части, которые видимы внутри просмотровых окон 60 и 62.

Формула изобретения

1. Способ отсечения графического элемента (2), имеющего границу (6) элемента, до просмотрового окна (4), имеющего границу (8) окна, в системе обработки графических данных, включающий операции: прослеживание по границе элемента для определения точки выхода (ЕХ), в которой граница элемента пересекает границу окна и выходит за просмотровое окно, и прослеживание по границе элемента для определения точки входа (EN), в которой граница элемента пересекает границу окна и входит в просмотровое окно, отличающийся тем, что определяют, пересекает ли воображаемая линия (12), начинающаяся в данной точке (Р) на границе окна и уходящая от нее на фактически бесконечное расстояние, участок границы элемента вне просмотрового окна между точкой выхода и точкой входа нечетное число раз или четное число раз, и/или 1) если воображаемая линия пересекает участок нечетное число раз, строят замыкающую линию по границе окна между точкой выхода и точкой входа и проходящую через заранее заданную точку на границе окна и, 2) если воображаемая линия пересекает участок четное число раз, строят замыкающую линию по границе окна между точкой выхода и точкой входа и не проходящую через заранее заданную точку.

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

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

4. Способ по любому из пп.1 - 3, отличающийся тем, что нечетное или четное число раз определяют прослеживанием по участку.

5. Способ по любому из пп.1 - 4, отличающийся тем, что определяют, что участок пересек воображаемую линию, если участок ведет к воображаемой линии и затем касается (18) ее или касается и затем уходит (20) от воображаемой линии с первой стороны (14) от воображаемой линии, и определяют, что участок границы элемента не пересек воображаемую линию, если участок ведет к воображаемой линии и затем касается ее или касается и затем уходит от воображаемой линии с второй стороны (16) от воображаемой линии.

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

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

8. Устройство (48) обработки графических данных, имеющее дисплей (50, 52) для отображения графических элементов и логическую схему отсечения (54, 56) для отсечения графического элемента, имеющего границу элемента, до просмотрового окна, имеющего границу окна, причем логическая схема включает средство для прослеживания по границе элемента для определения точки выхода, в которой граница элемента пересекает границу окна и выходит за пределы просмотрового окна, и средство для прослеживания по границе элемента для определения точки входа, в которой граница элемента пересекает границу окна и входит в просмотровое окно, отличающееся тем, что содержит средство для определения того, что воображаемая линия (12), которая начинается в заданной точке (Р) на границе окна и уходит от нее на границе окна, так что ее дальний конец лежит за пределами графического элемента, пересекает участок границы элемента за пределами просмотрового окна между точкой выхода и точкой входа нечетное число раз или четное число раз, 1) если воображаемая линия пересекает участок нечетное число раз, строят замыкающую линию по границе окна между точкой выхода и точкой входа и проходящую через заранее заданную точку на границе окна и, 2) если воображаемая линия пересекает участок четное число раз, строят замыкающую линию по границе окна между точкой выхода и точкой входа и не проходящую через заранее заданную точку.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7