ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ОПЕРАТОРА. Учебное пособие для студентов специальности 220301 Москва 2011 2 Содержание
 Скачать 2.77 Mb.
|
|
4.8.1. Построение графика функции двух переменных. Линии горизонта Рассмотрим задачу построения графика функции двух переменных z=f(x,у) в виде сетки координатных линий х=const и у=const. При параллельном проектировании вдоль оси Oz проекцией вертикальной линии в объектном пространстве будет вертикальная линия на картинной плоскости (экране). Легко убедиться в том, что в этом случае точка р(х,у,z) переходит в точку ((р, е 1 ),(р, e 2 )) на картинной плоскости, где 0 , sin , cos 1 e , cos , sin cos , sin sin 2 e , а направление проектирования имеет вид: sin , cos cos , cos sin 3 e , где 2 , 2 , 2 , 0 Чаще всего применяется полигональный способ представления графика: функция приближается прямоугольной матрицей значений функции в узлах сетки, а сам график представляется наборами ломаных линий, соответствующих постоянным значениям х и у. Рассмотрим сначала построение графика функции в виде набора линий, соответствующих постоянным значениям у, считая, что углы φ и ψ подобраны таким образом, что при y 1 >y 2 плоскость у = y 1 расположена ближе к картинной плоскости, чем плоскость у = y 2 Каждая линия семейства z=f(x, y i ) лежит в своей плоскости у = y i , причем все эти плоскости параллельны и, следовательно, не могут пересекаться. Из этого следует, что при у j > y i линия z=f(x, y j ) не может закрывать собой линию z=f(x, y i ) и, значит, каждая линия z=f(x,y j ) может быть закрыта только предыдущими линиями z=f(x, y i ), i=1,…,j-1. 104 Таким образом, возможен следующий алгоритм построения графика функции z=f(x,y): линии рисуются в порядке удаления (возрастания у – front-to- back) и при рисовании очередной линии выводится только та ее часть, которая ранее нарисованными линиями не закрывается. Для определения частей линии z = f(x, у k ), которые не закрывают ранее нарисованных линий, вводятся так называемые линии горизонта, или контурные линии. Изначально линии горизонта не инициализированы, поэтому первая линия выводится полностью (так как она ближе всего расположена к наблюдателю, то закрывать ее ничто не может). После этого линии горизонта инициализируются так, что в выводимых точках они совпадают с линией, выведенной первой. Рис. 104. График двух функций БЕЗ удаления невидимых линий. Рис. 105. График двух функций с удаленными невидимыми линиями. Вторая линия также выводится полностью, и линии горизонта корректируются следующим образом: нижняя линия горизонта в любой из точек равна минимуму из двух уже выведенных линий, верхняя – максимуму. Рассмотрим область экрана между верхней и нижней линиями горизонта – она является проекцией части графика функции, заключенной в полосе y 1 ≤ y ≤ y 2 , и, очевидно, находится ближе, чем все остальные линии вида z = f(x, у i ), i > 2. Поэтому те части линий, которые при проектировании попадают в эту область, указанной частью графика закрываются и при данном способе проектирования не видны. Тем самым следующая линия будет рисоваться только в тех местах, где ее проекция лежит вне области, задаваемой контурными линиями. Пусть проекцией линии z = f(x, y k ) на картинную плоскость является линия Y=Y k (X), где (X,Y) – координаты на картинной плоскости, причем Y – вертикальная 105 координата. Контурные линии Y k max (X) и Y k min (X) определяются следующими соотношениями: ). ( min ) ( ), ( max ) ( 1 1 min 1 1 max x Y X Y x Y X Y i k i k i k i k На экране рисуются только те части линии Y=Y k (x), которые, находятся выше линии Y k max (X)или ниже линии Y k min (X). Такой алгоритм называется методом плавающего горизонта. 4.8.2. Отсечение нелицевых граней Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали (рис. 106). Несложно заметить, что если вектор нормали грани n составляет с вектором l, задающим направление проектирования, тупой угол (вектор нормали направлен от наблюдателя), то эта грань заведомо не может быть видна. Такие грани называются нелицевыми. Если соответствующий угол является острым, грань называется лицевой. При параллельном проектировании условие на угол, для того чтобы грань была видна, можно записать в виде неравенства (n,l)>0, поскольку направление проектирования от грани не зависит. При центральном проектировании с центром в точке с вектор проектирования для точки р будет равен l = с - р. Для определения того, является заданная грань лицевой или нет, достаточно взять произвольную точку p этой грани и проверить выполнение условия: (n,l)>0. Знак этого скалярного произведения не зависит от выбора точки на грани, а определяется тем, в каком полупространстве относительно плоскости, содержащей данную грань, лежит центр проектирования. Так как при центральном проектировании проектирующий луч зависит от грани (и не зависит от выбора точки на грани), то лицевая грань может стать нелицевой, а нелицевая может стать лицевой даже при параллельном сдвиге. При параллельном проектировании сдвиг не изменяет углов и то, является ли грань лицевой или нет, зависит только от угла между нормалью к грани и направлением проектирования. Заметим, что если по аналогии с определением принадлежности точки многоугольнику пропустить через произвольную точку картинной плоскости проектирующий луч к объектам сцены, то число пересечений луча с лицевыми гранями будет равняться числу пересечений луча с нелицевыми гранями. В случае, когда сцена представляет собой один выпуклый многогранник, удаление нелицевых граней полностью решает задачу удаления невидимых граней. 106 Рис. 106. Многогранник, с заданными для каждой грани, векторами l,n. Хотя в общем случае предложенный подход и не решает задачи удаления полностью, но, тем не менее, позволяет примерно вдвое сократить количество рассматриваемых граней вследствие того, что нелицевые грани всегда не видны; что же касается лицевых граней, то в общей ситуации части некоторых лицевых граней могут быть закрыты другими лицевыми гранями. Ребра между нелицевыми гранями также всегда не видны. Однако ребро между лицевой и нелицевой гранями вполне может быть и видимым. 4.8.3. Алгоритм Робертса Первым алгоритмом удаления невидимых линий был алгоритм Робертса, требующий, чтобы каждая грань была выпуклым многоугольником. Опишем этот алгоритм. Сначала отбрасываются все ребра, обе определяющие грани которых являются нелицевыми (ни одно из таких ребер заведомо не видно). Следующим шагом является проверка на закрывание каждого из оставшихся pебер со всеми лицевыми гранями многогранника. Возможны следующие случаи: • грань ребра не закрывает (рис. 107 а); Рис. 107. Варианты расположения ребра и грани • грань полностью закрывает ребро (тогда оно удаляется из списка рассматриваемых ребер) (рис. 107 б); • грань частично закрывает ребро (в этом случае ребро разбивается на несколько частей, видимыми из которых являются не более двух; само ребро l n a б в 107 удаляется из списка, но в список проверенных ребер добавляются те его части, которые данной гранью не закрываются) (рис. 107 в). Рассмотрим, как осуществляются эти проверки. Пусть задано ребро АВ, где точка А имеет координаты (x a , y a ), а точка В – (х b , у b ). Прямая, проходящая через отрезок АВ, задается уравнениями ), ( ) ( a b a a b a y y t y y x x t x x причем сам отрезок соответствует значениям параметра 1 0 t Данную прямую можно задать неявным образом как , 0 ) , ( y x F где ). ( ) ( ) ( ) ( ) , ( a a b a a b y y x y x x y y y x F Предположим, что проекция грани задается набором проекций вершин Р 1 , ..., P k с координатами (х i ,у i ), i = 1,...,n. Обозначим через F i значение функции F в точке P i и рассмотрим i-й отрезок проекции грани Р i , Р i +1. Этот отрезок пересекает прямую АВ тогда и только тогда, когда функция F принимает значения разных знаков на концах этого отрезка, а именно при 0 1 i i F F Случай, когда 0 1 i F будем отбрасывать, чтобы дважды не засчитывать прямую, проходящую через вершину, для обоих выходящих из нее отрезков. Итак, мы считаем, что пересечение имеет место в двух случаях: 0 , 0 , 0 , 0 1 1 i i i i F F F F Точка пересечения определяется соотношениями ), ( ) ( 1 1 i i i i i i y y s y y x x s x x где 1 i i i F F F s Отсюда легко находится значение параметра t: , , , a b a b a b a a b a b a b a x x y y y y y y t y y x x x x x x t Возможны следующие случаи: 1. Отрезок не имеет пересечения с проекцией грани, кроме, быть может, одной точки. Это может иметь место, когда • прямая АВ не пересекает ребра проекции (рис. 108 а); • прямая АВ пересекает ребра проекций в двух точках t 1 и t 2 , но либо t 1 <0, t 2 <0, либо t 1 > 1, t 2 > 1 (рис. 108 б); • прямая АВ проходит через одну вершину, не задевая внутренности треугольника (рис. 108 в). 108 Очевидно, что в этом случае соответствующая грань никак не может закрывать собой ребро АВ. Рис. 108. Пример пересечения отрезка с проекциями граней 2. Проекция ребра полностью содержится внутри проекции грани (рис. 109 а). Тогда есть две точки пересечения прямой АВ и границы грани и t 1 <0<1 2 . Если грань, лежит ближе к картинной плоскости, чем ребро, то ребро полностью невидимо и удаляется. 3. Прямая АВ пересекает ребра проекции грани в двух точках и либо t 1 <0≤t 2 ≤1, либо 0 1 ≤1 2 (рис. 109 б и в). Если ребро АВ находится дальше от картинной плоскости, чем соответствующая грань, то оно разбивается на две части, одна из которых полностью закрывается гранью и потому отбрасывается. Проекция второй части лежит вне проекции грани и поэтому этой гранью не закрывается. а б в г Рис. 109. Пример пересечения отрезка с проекциями граней 1. Прямая АВ пересекает ребра проекции грани в двух точках, причем (рис. 109 г) 0 1 2 <1. Если ребро АВ лежит дальше от картинной плоскости, чем соответствующая грань, то оно разбивается на три части, средняя из которых отбрасывается. Для определения того, что лежит ближе к картинной плоскости – отрезок АВ (проекция которого лежит в проекции грани) или сама грань, через эту грань проводится плоскость 0 ) , ( c p n (где n – нормальный вектор грани), разбивающая все пространство на два полупространства. Если оба конца отрезка АВ лежат в том же полупространстве, в котором находится и наблюдатель, то отрезок лежит ближе к грани; если оба конца находятся в другом полупространстве, то А В а) б) в) А В 109 отрезок лежит дальше. Случай, когда концы лежат в разных полупространствах, здесь невозможен (это означало бы, что отрезок АВ пересекает внутреннюю часть грани). Если общее количество граней равно n, то временные затраты для данного алгоритма составляют О(n 2 ). Количество проверок можно заметно сократить, если воспользоваться разбиением картинной плоскости. Разобьем видимую часть картинной плоскости (экран) на N 1 ·N 2 равных частей (клеток) и для каждой клетки А ij построим список всех лицевых граней, чьи проекции имеют с данной клеткой непустое пересечение. Для проверки произвольного ребра на пересечение с гранями отберем сначала все те клетки, которые проекция данного ребра пересекает. Ясно, что проверять на пересечение с ребром имеет смысл только те грани, которые содержатся в списках этих клеток. В качестве шага разбиения обычно выбирается О(l), где l – характерный размер ребра в сцене. Для любого ребра количество проверяемых граней практически не зависит от общего числа граней и совокупные временные затраты алгоритма на проверку пересечений составляют О(n), где n – количество ребер в сцене. Поскольку процесс построения списков заключается в переборе всех граней, их проектировании и определении клеток, в которые попадают проекции, то затраты на составление всех списков также составляют О(n). 4.8.4. Алгоритм Аппеля. Количественная невидимость Рассмотрим произвольное гладкое выпуклое тело в пространстве. Взяв произвольную точку Р на границе этого тела, назовем ее лицевой, если (n,l)>0, где n – вектор внешней нормали к границе в этой точке. Если же (n,l)<0, то данная точка является нелицевой (и, соответственно, невидимой). Это определение подобно определению лицевой и нелицевой грани (п.4.8.2.). В силу гладкости поверхности у лицевой (нелицевой) точки существует достаточно малая окрестность, целиком состоящая из лицевых (нелицевых) точек и проектирующаяся на картинную плоскость взаимно однозначно (не закрывая саму себя) (рис. 110). У точек, для которых (n,l) = 0, подобной окрестности (состоящей только из лицевых или только нелицевых точек) может не существовать. Такие точки, в отличие от (регулярных) точек называются нерегулярными (особыми) точками проектирования (рис. 111). В общем случае множество всех нерегулярных точек (n,l) = 0 образует на поверхности рассматриваемого объекта гладкую кривую, называемую контурной линией. Эта линия разбивает поверхность выпуклого тела на две части, каждая из которых однозначно проектируется на картинную плоскость и целиком состоит из регулярных точек. Одна из этих частей является полностью видимой, а другая – полностью невидимой. 110 Рис. 110. Пример регулярных точек Рис. 111. Пример НЕрегулярных точек Попытаемся обобщить этот подход на случай одного или нескольких невыпуклых тел. Множество всех контурных линий (их уже может быть несколько) разбивает границы тел на набор связных частей (компонент), каждая из которых по-прежнему взаимнооднозначно проектируется на картинную плоскость и состоит либо из лицевых, либо из нелицевых точек. Никакая из этих частей не может закрывать себя при проектировании, однако возможны случаи, когда одна такая часть закрывает другую. Чтобы это учесть, введем числовую характеристику невидимости – так называемую количественную невидимость точки, определив ее как количество точек, закрывающих при проектировании данную точку. Точка оказывается видимой только в том случае, когда ее количественная невидимость равна нулю. Количественная невидимость является кусочно-постоянной функцией и может изменять свое значение лишь в тех точках, проекции которых на картинную плоскость лежат в проекции одной из контурных линий. Итак, проекции контурных линий разбивают картинную плоскость на области, каждая из которых является проекцией части объекта, а сами поверхности, ограничивающие тела, разбиваются контурными линиями на однозначно проектирующиеся фрагменты с постоянной количественной невидимостью. В общем случае при проектировании гладких поверхностей возникает два основных типа особенностей (все остальные возможные особенности могут быть приведены к ним сколь угодно малыми «шевелениями»): 1) линии складки, являющиеся регулярными проекциями контурных линий на картинную плоскость и представляющие собой регулярные кривые на поверхности, взаимно однозначно проектирующиеся на картинную плоскость (рис. 110), и 2) изолированные точки сборки, которые лежат на линиях складки (контурных линиях) и являются особыми точками проектирования контурных линий на картинную плоскость. Рассмотрим теперь изменение количественной невидимости вдоль самой контурной линии. Можно показать, что она может измениться только в двух случаях – при прохождении позади контурной линии и в точках сборки. В первом случае происходит загораживание складкой другого участка поверхности, и количественная невидимость изменяется на два. Во втором случае происходит 111 загораживание поверхностью самой себя, и количественная невидимость изменяется на единицу. Таким образом, для определения видимости достаточно найти контурные линии и их проекциями разбить всю картинную плоскость на области, являющиеся видимыми частями проекций объектов сцены. В результате мы приходим к следующему алгоритму: на границах тел выделяется множество контурных линий С. Каждая из этих линий разбивается на части в тех точках, где она закрывается при проектировании на картинную плоскость какой-либо линией этого множества, проходящей в точке закрывания ближе к картинной плоскости. Контурные линии разбиваются и в точках сборки. В результате получается множество линий, на каждой из которых количественная невидимость одна и та же (постоянна). В случае, когда рассматриваются поверхности, не являющиеся границами сплошных тел, к множеству контурных линий С следует добавить и граничные линии этих поверхностей. Если рассматриваемые объекты являются лишь кусочно-гладкими, то к множеству линий С следует добавить также линии излома (линии, где происходит потеря гладкости). Данный метод может быть применен и для решения задачи удаления невидимых поверхностей – получившиеся линии разбивают картинную плоскость на области, каждая из которых соответствует видимой части одного из объектов сцены. Метод с успехом можно применить и для работы с полигональными объектами. Одним из вариантов такого применения является алгоритм Аппеля. Аппель вводит понятие количественной невидимости QI (quontitative invisibility) точки как число лицевых граней, ее закрывающих. Это несколько отличается от определения, введенного ранее, однако существо подхода остается неизменным. Контурная линия полигонального объекта состоит из тех ребер, для которых одна из проходящих граней является лицевой, а другая – нелицевой. Так, для многогранника на рис. 112 контурной линией является ломаная ABCIJDEKLGA. Рассмотрим, как меняется количественная невидимость вдоль ребра. Для определения видимости ребер произвольного многогранника сначала берется какая-либо его вершина и ее количественная невидимость определяется непосредственно. Далее прослеживается изменение количественной невидимости вдоль каждого из ребер, выходящих из этой вершины. Эти ребра проверяются на прохождение позади контурной линии, и их количественная невидимость в соответствующих точках изменяется. При прохождении ребра позади контурной линии количественная невидимость точек ребра изменяется на единицу. Те части отрезка, для которых количественная невидимость равна нулю, сразу же рисуются. Следующим шагом является определение количественной невидимости для ребер, выходящих из новой вершины, и т. д. 112 Рис. 112. Пример контурной линии В результате определяется количественная невидимость всех ребер связной компоненты сцены, содержащей исходную вершину (и при этом видимые части ребер этой компоненты сразу же рисуются). В случае, когда рассматривается изменение количественной невидимости вдоль ребра, выходящего из вершины, принадлежащей контурной линии, необходимо проверить, не закрывается ли это ребро одной из граней, выходящей из этой вершины (как, например, грань DEKJ закрывает ребро DJ, и это является аналогом точки сборки). Так как для реальных объектов количество ребер, входящих в контурную линию, намного меньше общего числа ребер (если общее количество ребер равно n, то количество ребер, входящих в контурную линию, –О( n )), алгоритм Аппеля является более эффективным, чем алгоритм Робертса. На поверхности многогранников можно выделить набор линий такой, что каждая контурная линия независимо от направления проектирования обязательно пересечет хотя бы одну из линий этого набора. Таким образом, для отыскания контурных линий необязательно перебирать все ребра – достаточно проверить заданный набор и восстановить контурные линии от точек пересечения с этим набором. Замечание. Для повышения эффективности данного алгоритма возможно использование разбиения картинной плоскости – для каждой клетки разбиения строится список ребер контурной линии, чьи проекции пересекают данную клетку. |