    11. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА»	1G7 

    11. Проект «Построение изображения полиэдра» 

    В настоящее время во многих областях науки и техники используются разные 
методы моделирования геометрических объектов в трехмерном пространстве. Один 
из способов моделирования состоит в том, чтобы аппроксимировать реальный 
объект набором выпуклых плоских многоугольников (piic. 11.1), Такой н а (юр 
""мы будем называть полиэдром, многоугольники — гранями, а их сто« роны — 
ребрами полиэдра, Как мы видим, при изображении полиэдра реально изображаются 
не сами многоугольники, а линии, их ограничивающие, т, е, ребра. Однако если 
изобразить все ребра вообще, то получится запутанная, непривычная для человека 
картинка (рис. 11.2). 
    Для получения удобного для человека рис. 11.1 нужно при построении 
изображения учитывать, что некоторые ребра могут оказаться полностью или 
частично невидимыми, так как их могут 

    168 ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    загородить грани полиэдра. Таким образом, при построении изобра*' жения  
надо  «удалить»   (т.   е.  не  рисовать)   части   ребер,  которые 

    Рис.  11.2 

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

    II. ПРОЕКТ  «ПОСТРОЕНИЕ  ИЗОБРАЖЕНИЯ ПОЛИЭДРА»     169 

    рый вектор). Мы будем представлять себе этот вектор направлен* ным вверх, 
параллельные ему прямые я плоскости называть вертикальными, а ортогональные — 
горизонтальными. Задача состоит в том, чтобы построить вид полиэдра из 
«бесконечно высокой» точки с учетом того, что одни грани могут загораживать 
другие, или, 

    <<Высокая» горизонтальная плоскость 
    Вектор проектирования 

    Рис.   11.3 

    другими словами, построить плоское изображение видимой части поличдра 
(параллельная проекция вдоль вектора проектирввания) на «достаточно высокой» 
горизонтальной плоскости (рис. 11.3), 
    Примерами полиэдров могут служить поверхности куба или пакета молока с 
отрезанным углом, полураскрытая веером книга и даже набор пересекающихся 
многоугольников (рис. 11.4), 

    Рис.   11.4 

    Простейший способ задать полиэдр — перечислить координаты вершин каждой 
грани. На практике, однако, этот способ не применяется, так как он обладает 
рядом недостатков. Поэтому мы поступим следующим образом: занумеруем все 
вершины полиэдра и будем считать, что каждое ре~ёр'6 полиэдра задается парой 
номеров— номером начала и номером конца. Далее для задания грани перечислим 
все ребра, ограничивающие данную грань (т. е, все пары номеров вершин). 
Описанная информация задает так на«. зываемый абстрактный полиэдр и позволяет 
отвечать на комбинз-. 

    170     ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    торные вопросы вида «сколько вершин в данной грани?», «имеют ли дне данные 
грани общую вершину?» и т. д. Эта комбинаторная информация, однако, ничего не 
говорит о расположении полиэдра в трехмерном пространстве. Чтобы задать такое 
расположение, достаточно задать отображение множества «абстрактных» вершин (т. 
е. множества их_номе?ов) „в.ЕЗ.. Эта "часть информации о полиэдре 
д1л5еТГЗЭЭвается'жетричесяой (числовой). 
    Будем считать, что и комбинаторная, и метрическая информация о конкретном 
полиэдре, изображение которого надо построить, содержится в базовом 
__ислолнителе «Полиэдр» и может быть получена с помоиСыйГследующих предписаний: 
    1. множество граней   :: множество элементов типа грань 
    2. множество ребер     :: множество элементов типа ребро 
    3. R3 (вх : вершина)   :     точка R3 | отображение вершин в R3 типы: 
    грань       = множество элементов типа ребро ребро       = запись (начало, 
конец : вершина) вершина = Z+ точка R3 = запись (х, у, z : число) 
    Информация о векторе проектирования может быть получена с помощью предписания 
    1. вектор проектирования :: вектор R3 
    базового  исполнителя  «Проектор».  Этот  же  исполнитель  по  предписанию 
    2. изобразить отрезок <вх : отрезок R3> 
    проектирует  отрезок  вдоль  вектора проектирования  и  изображает его. Здесь 
    типы: 
    отрезок R3 = запись (начало, конец: точка R3) точка R3, вектор R3 = запись 
(х, у, z : число) 
    Таким образом, наша задача — реализовать программу построения изображения 
полиэдра на базе исполнителей «Полиэдр» и «Проектор». 
    Реализация. Поскольку плоское изображение полиэдра состоит из проекций 
видимых частей ребер, то естественно строить его следующим образом: перебрать 
все ребра полиэдра и для каждого ребра изобразить его видимую часть. Мы здесь 
опять воспользуемся аналогией со светом — расположим «бесконечно высоко 
вверху» солнце и будем называть видимые части ребр 
    а просветами, а часть, загороженную некоторой гранью, — тенью от грани на 
ребро (рис, 11,5). 

    11. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ  ПОЛИЭДРА»	171 

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

    Рис. 11.5 

    Поскольку мы сначала перебираем все ребра, а потом для каждого ребра 
перебираем все грани, то самым крупным образованием в этой ситуации является 
ребро. Поэтому в соответствии с технологией «свер-ixy вниз» примем решение, 
что вес действия с конкретным ребром в целом будет производить специальный 
промежуточный исполнитель «Изобразитсль так: 
    ребра». Тогда первый шаг декомпозиции можно записать 
    программа построение изображения полиэдра . дано        : | полиэдр в R3 
(исполнитель "Полиэдр") .	| направление проектирования (исполнитель 
"Проектор") . получить: | плоское  изображение   ребер  полиэдра  
(параллельная | проекция) с "удалением невидимых линий" 
    . цикл у ребро е Полиэдр.множество ребер выполнять ] 
    . .       Изобразитель ребра.начать работу (вх:ребро) 
    . .       цикл у грань <= Полиэдр.множество граней выполнять 
    . .       .     Изобразитель ребра.учесть тень от грани (вх: грань) 
    . .       конец цикла 
    . .       Изобразитель ребра.кончить работу 
    . конец цикла 
    конец программы 
    ! Обратите внимание, что ребро, с которым будет работать Изо* бразитель 
ребра, указывается только в предписании «начать работу». Мы предполагаем, что 
Изобразитель ребра сам запомнит это ребро и потом использует при учете тени от 
грани. Мы предполагаем также, что по предписанию «кончить работу» Изобразитель 
ребра изображает оставшиеся на ребре просветы и лишь затем заканчивает работу. 
    Теперь надо формализовать понятие «тень от грани на ребро» и понять как 
Изобразитель ребра будет по этим теням строить просветы. Первая идея состоит в 
том, что поскольку каждая тень и каждый просвет — это некоторые отрезки на 
ребре, то можно ввести одномерные координаты на реоре и работать с отрезками 

    172	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    в этих одномерных координатах, а не с отрезками в R3. Такой переход от 
трехмерных объектов к одномерным заметно упрощает работу. В соответствии с 
технологией «сверху вниз» задачу полу-чения «одномерных» теней мы возложим на 
специального исполнителя «Геометр», а все операции над отрезками в одномерных 
ко "ординатах — на исполнителя «Отрезки». Вторая идея состоит в том, что если 
ребро считать фиксированным, то просветы можно рассматривать как индуктивную 
функцию от последовательности1 учитываемых граней, а точнее их теней. При 
получении очередной старые  просветы очередная  теш» новые  просветы 

    -t <») а X В f (»Xx) з 

    Рис.   11.6 

    тени х надо просмотреть все имеющиеся просветы f((o) и исключить из них 
части, попавшие в тень. Оставшиеся после этого просветы и есть f(co*x) (рис. 11.6). 
    В начальный момент (до получения первой тени от грани) просветы {(Л) 
должны состоять из одного отрезка, соответствующего всему ребру. 
    Нам будет удобно хранить просветы в линейном однонаправленном списке (Л1 
-списке) и модифицировать этот список при по< лучении очередной тени: 
    исполнитель Изобразитель ребра .   СП: 
    1. начать работу (вх : ребро) 
    2. учесть тень от грани (вх. : грань) 
    3. кончить работу 
    . типы: 
    .   отрезок =...[ отрезок на изображаемом ребре 
    . объекты: 
    .   Просветы: Л1-список элементов типа отрезок 
    . идеи реализации: 
    .    Список  "Просветы"  хранит просветы между тенями от уже уч-,   теаных 
(с момента начала работы) граней 
    . используемые исполнители: 
    .    Геометр, Проектор, Отрезки конец описаний | ___„____. 
    II. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА» 173 
    программа начать работу (вх : ребро) 
    . дано        :    ребро : ребро | "абстрактное" ребро полиэдра 
    . получить: | Просветы состоят из всего ребра 
    .    Геометр.начать работу (вх : ребро, 
    .	Проектор.вектор проектирования) 
    .    Просветы.начать работу 
    .    Просветы.добавить элемент (в*: Геометр.ребро!) ;за   указателем 
    конец программы 

    Здесь «ребро!» — предписание Геометра, которое вырабатывает значение типа 
«отрезок», задающее все ребро в одномерных координатах. Использование этого 
предписания позволяет в Изобразителе ребра не знать конкретных одномерных 
координат начала и конца ребра. 
    программа учесть тень от грани (вх: грань) . дин»         :     
грань:грань | "абстрактная" грань полиэдра . получить: | в списке "Просветы" 
учтена тень от новой грани 
    .    тень := Геометр.тень от грани (вх: грань) | в одномерн.коорд. если 
Отрезки.отрезок (тень) вырожден то ничего не делать 
    ,    .   иначе 
    ,    .   I IpucucTu.установить указатель в начало списка 
    .    .   цикл пока Просветы.указатель не в конце списка выполнять 
    .    .   .     Просветы.взять элемент sa указателем в (вых : просвет) .   
.     Отрезки.получить разность (вх: просвет, тень) .   .	в  (вых: левая 
компонента, правая компонента) .   .     если  Отрезки.отрезок (левая 
компонента) не вырожден то .   .     .    Просветы.добавить (левая компонента) 
за указателем 
    ...      .    ПРОСИСТМ. передвинуть указатель вперед 
    ,    .   .     конец если 
    .   .     если Отрезки.отрезок (правая компонента) не вырожден .то 
    ,    .   .     .   Просветы.добавить (правая компонента), за указателем .  
 .     .    Просветы.передвинуть указатель вперед 
    .    .   .     конец если .   конец цикла 
    .    конец если 
    конец программы 
    Чтобы понять работу этой программы, надо разобраться в том, 1:акой отрезок 
называется вырожденным и что такое разность двух отрезков. 
    Отрезком с началом а и концом b мы называем множество точек t е R таких, 
что а ^ t ^ Ь, Тем самым при а = b отрезок 

    174	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    сводится к точке, а при а > b является пустым. В обоих случаях (т, е. при 
а 5= Ь)  отрезок называется вырожденным, 
    Предписание «получить разность <вх: А, В) ...» исполнителя «Отрезки» 
получает разность множества точек отрезка А и множества внутренних точек 
отрезка В, например, как изображено на рис. 11.7. 
    просвет 
    темь. 
    разность 
    j——I 
    левая кскпсме?нта (левее тени) 

    Рис. П.7 
    (прав 

    В зависимости от расположения отрезков «просвет» и «тень» разность может 
быть пустой (если просвет целиком попал в тень) или состоять из одной точки 
(рис. 11.8), из одного отрезка, двух точек, отрезка и точки, двух отрезков. 
    Нам, однако, будет удобнее считать, что разность во всех случаях состоит 
из двух отрезков, но один из них или они оба могут 

    Просвет 
    тещ. 
    левай компонента «левее тени} 
    компонента {правее тени) 

    Рис. 11.8 

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

    программа кончить работу 
    . дано        : 
    , получить: | изображение просветов (т, е. видимой части ребра) 
    .	Просветы.установить указатель в начало списка 
    .	цикл у * *= части списка Просветы за указателем выполнят.» 
    .	.  Проектор.изобразить отрезок (Геометр.R3(вх: х}) 
    .	конец цикла 
    .	Просветы.кончить работу 
    .	Геометр.кончить работу 
    конец программы 


    11. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА» 175 

    Здесь   «Геометр.К3<вх : х> *—это   предписание,  которое  по  отрезку х в 
одномерных координатах па ребре вырабатывает значение, . являющееся отрезком в 
трехмерном пространстве. 

    jjКонец исполнителя 
    |= = = = = = = = = = =.=.=. — — — — = =. = —— в = = = = = = и 
    =1         „ 

    Итак, мы совершили очередном шаг декомпозиции и нам осталось реализовать 
исполнителей «Геометр» и «Отрезки». Поскольку мы подозреваем, что Геометр в 
иерархии исполнителей будет занимать более высокое положение (так как при его 
реализации могут потребоваться какие-то операции с отрезками), то мы сначала 
реализуем его. Система предписаний этого исполнителя выглядит так: 
    • 
    1. начать работу (вх: ребро, вектор проектирования) 
    2.	ребро!                                    : отрезок 
    3.	теш. от грипп (вх : грань)     : отрезок 
    4.	И'Л (вх : отрезок)                      : отрезок #д 
    Б.	кончить работу 

    Поскольку Геометр информацию об обрабатываемом ребре и некторе 
проектирования получает лишь в предписании «начать работу;», я зта информация 
необходима "и в других предписаниях (нпнрнмгр, при нахождении тени от грани), 
то мы введем гло-fxuiMiiiie объекты объекты: 
    хО, xl: точка R3   [начало и конец обрабатываемого ребра 
    р        : вектор R3 |вектор проектирования 
    и  которых  при  начале работы запомним соответствующую ипфор-мпцию. 
    ()А|1й1И'||> шшминие, что мы различаем Точки и векторы трехмерною 
npofijiuiicTua. Дне точки можно вычесть и получить вектор, к точке можно 
прибавить вектор и снова получить точку и т. д. J (рнбавнть точку к точке или 
умножить точку на число нельзя Подобное разграничение позволяет контролировать 
правильность формул и шшлитичсской геометрии подобно тому, как учет раз-мгрнштсП 
наличии позволяет проводить контроль физических формул. Все операции над 
точками и векторами R3 мы будем выполнять с помощью специального исполнителя 
«Стереометр». Именно он будет сводить эти операции к операциям, которые умеет 
выполнять Универсальный Выполнитель. Например, для векторов х и у мы можем 
написать х:= у, но 
    вместо х :_=;—у должны писать 
    х:= Стереометр.произведение (у) на (—1). 
    Предписания «ребро!» и «тень от грани» должны вырабатывать отрезок в 
одномерных координатах на ребре. Мы будем обо

    176	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    значать точки ребра в одномерных координатах буквой t,  а сами -координаты 
называть t-координатами. По одномерной координате t точка х на ребре с началом 
хО и концом xl  вычисляется следующим образом: 

    х = (xl — хО) * (t — tO)/(tl - tO) + хО; 
    где Ш и tl —t-координаты начала и конца ребра. 

    Основным и наиболее содержательным предписанием Геометра является 
предписание «тень от грани». Именно в процессе реализации этого предписания 
были введены локальные предписания, перечисленные в системе предписаний через 
дефис (-): 
    исполнитель Геометр 
    . СП: 
    1. начать работу {вх: ребро .вектор проектирования) 
    2. ребро 1 
    3. тень от грани {вх : грань) 
    — грань {вх:грань) вертикальна 
    — центр {вх : грань) 
    — горизонтальное пересечение {вх: а,Ь,с: точка R3) 
    — вертикальное пересечение {вх : а,Ь,с : точка R3) 
    — пересечение с {вх: а: точка R3,n: вектор R3) 
    4.   R3 {вх : отрезок) 
    — R3_o6paa {вх : t: число) 
    5.   кончить работу 
    :отрезок :отрезок : да/нет : точка R3 :отрезок :отрезок :отрезок 
    : отрезок R3 •.точка R3 
    константы: 
    to	=0.0 (одномерная координата начала ребра tl             =1.0 
[одномерная координата конца ребра 
    типы: 
    .	отрезок R3 = запись (начало,конец:точка R3) 
    ,	точка R3,вектор R3= . . . 
    ,	отрезок    = запись (начало,конец : число) 
    ,	грань       = множество элементов типа ребро 
    .	ребро       = запись (начало,конец: вершина) 
    .	вершина = .. . 
    . объекты: 
    .   xO.xl:точка R3 | начало и конец обрабатываемого ребра ,   р       : 
вектор R3 |вектор проектирования 

    II. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА» 177 

    . используемые исполнители: 
    .   Полиэдр, Отрезки, Стереометр (С) конец описаний J — — — —— — — 
    программа начать работу {вх: ребро, вектор проектирования) 
    . дано         :    вектор проектирования : вектор  R3, 
    .	ребро:ребро ["абстрактное" ребро полиэдра 
    . получить: | установлены соотв. значения глобальных объектов 
    .   хО := Полиэдр.R3 {ребро.начало) .    xl := Полиэдр.R3 {ребро.конец) 
    р:= вектор проектирования	• конец программы 
    программа ребро!: отрезок ==(tO, tl) 

    Итак, мы подошли к центральному месту реализации Геометра — нахождению 
тени от грани на ребро. Прежде всего разберемся с тем, что такое тень. Будем в 
рамках нашей аналогии считать, что Mil грань спорху падает параллельный 
вектору р поток света. Мно-мичтио нип'шюмых гранью точек пространства образует 
при этом нплуГич-копе'шую призму, у которой основанием является грань 
по-лиздра, а боковая поверхность параллельна вектору р и направлена н 
противоположную сторону (рис. 11.5). Тень от грани на ребро есть пересечение 
ребра с этой призмой: 

    тень = ребро П призма 

    '(Здесь и далее мы будем считать, что грань не вертикальна, т. е. по 
параллельна исктору р.) Заметим, что призму следует считать открытой, т. е. 
считать, что граница призмы тени не принадлежит, так как в противном случае 
каждая грань будет затенять себя и изображение окажется пустым. 
    Естественно попытаться свести нахождение пересечения ребра с призмой к 
каким-нибудь более элементарным операциям. Мы сделаем это, представив призму в 
виде пересечения открытых полупространств. Например, треугольную призму можно 
представить в ииде пересечения четырех полупространств (рис. 11.9). 
    Первое полупространство ограничено плоскостью, проходящей через грань 
полиэдра, и расположено со стороны, противоположной направлению вектора р; это 
полупространство мы будем называть горизонтальным. Остальные полупространства 
ограничены вертикальными плоскостями, проходящими через то или иное ребро 
грани, и расположены так, что сама грань {или, что то же самое, ее центр) 

    178	гл. 2. НЕСКОЛЬКО ПРИМЕРОВ ПРОГРАММ 

    содержится   в   соответствующем   полупространстве;   эти   
полупро-странства мы будем называть вертикальными. Итак, призма = ГПВ1 ПВ2ПВЗ, 
    где   Г — горизонтальное  полупространство,   а   В1,   В2,   ВЗ — верти-' 
кальные. Следовательно, 
    тень = ребро fl призма = ребро |"|Г Л В1 Л В2 П ВЗ •« 
    = РГПРВ1ПРВ2ПРВЗ, 
    где РГ = ребро П Г, a PBi = ребро П Bi, i = 1, 2, 3. И РГ, и PBJ 
    являются отрезками  (точнее интервалами или полуинтервалами) на   1 

    И. ПРОЕКТ  .ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА», 179 

    рас.  11.9. а)  призма,  б)   четыре полупространства, пересечение которых 
дает призму   ребре;   мы  их   будем   называть   соответственно   горизонтальным  и 
вертикальными пересечениями. 
    Таким образом, мы можем отдельно находить пересечения ребра с каждым из 
полупространств, а потом пересечь получившиеся от« резки на ребре между собой. 
Поскольку грань может быть многоугольной,   естественно   сначала   найти   
горизонтальное   пересечение, а оставшиеся вертикальные обрабатывать в цикле: 
программа тень от грани (вх : грань): отрезо 
    к .   дано        :   грань :грань |"абстрактная" грань полиэдра .   
получить: | затеняемый гранью отрезок ребра в t-координатах 1 (или пустой 
отрезок, елли грань вертикальна) 
    если грань (вх: грань) вертикальна то ответ :=(tl,tO) .   иначе 
    с := центр (вх: грань) 
    грань.скопировать какой нибудь элемент в (вых:ребро) .      а := 
Полиэдр.R3 (ребро.начало) .     b := Полиэдр.R3 (ребро.конец) 
    ответ ;= горизонтальное пересечение (вх: а,Ь,с) 
    цикл у ребро е множества грань выполнять .     •     а ;= По диэдр. R3 
(ребро, начало) 
    .    .     .     b := Полиэдр.R3 (ребро.конец) 
    .    .     ,     z := вертикальное пересечение (вх:а,Ь,с) 
    .     ,     .     Отрезки.(вх/вых : ответ) пересечь с (BX:Z) 
    конец цикла конец если конец программы 
    При реализации этой программы мы в соответствии с технологией «сверху 
вниз» отложили «на потом» всю содержательную работу (аналитическую геометрию), 
для чего воспользовались четырьмя локальными программами. 
    Программа «грань вертикальна» проверяет, параллельна ли грань вектору 
проектирования. Программа «центр» предназначена для получения какой-нибудь 
внутренней точки грани. Ъ качестве такой точки можно взять, например, центр 
тяжести вершин грани, Ути дпе программы реализуйте самостоятельно. 
    Осташниеся дне программы находят пересечение ребра с гори-вонталын.ш   или 
  вертикальным   полупространством   соответственно. Начало и  конец ребра,  а 
 также вектор  проектирования  являются глобальными   объектами   Геометра,   
а   полупространства   задаются и пиле трех точек трехмерного пространства. 
программа горизонтальное пересечение (вх 
    : а,Ь,с): отрезок .   дано         :    а,Ь,с: точка R3    | три точки 
плоскости грани, .	| не лежащие на одной прямой .   получить: | пересечение (в 
t-координатах ) ребра (xO.xl) с .                      | полупространством, 
ограниченным плоскостью abc я | направленным в сторону вектора — р 
    ab:-« С.рпэпость (пх:Ь,а) ВС !"• С.рялпос! I. (их: с, л) 
    | вектор ab := b — а | вектор   ас := с — а 
    (точки в R3) (точки в R3) 
    | выбор нормали к 1 плоскости abc, | сонаправлеиной | с вектором р 
    М :•« С. век горние произведение (ab,ac) если С.скалярное произведение 
<п,р)   <0.0 .  то п := С. произведение (п) на (—1) конец если ответ := 
пересечение с (вх:а,п) конец программы 
    программа вертикальное пересечение (вх: а,Ь,с): отрезок . дано        :   
а,Ь,с: точка R3   | три точки плоскости грани, 
    | не лежащие на одной прямой 
    . получить: (пересечение (в t-координатах) ребра (xO.xl) с ,	| 
полупространством, которое содержит точку с и .                      
|ограничено вертикальной (параллельной р) [плоскостью, проходящей через точки а,Ь 

    180	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    Рис.    11.10 

    .	ab := С.разность (вх:Ь,а) [вектор ab := b — а (точки в R3) 
    .	ас := С. разность (вх:с,а) (вектор ас := с — а (точки в R3) 
    ,	п := С. векторное произведение (ab,p)              [выбор нормали 
    .	если С.скалярное произведение (п,ас)>0.0 |к плоскости, 
    .	.   то п := С.произведение (п) на (—1)             [направленной 
    .	конец если                                         -             I 
наружу от грани 
    .	ответ := пересечение с (вх:а,п) конец программы 

    Итак, мы спели получение тени от грани на ребро к нахожде* нию  
пересечения   (в t-координатах)   ребра и  полупространства, за-•'- . данного 
точкой а граничной плоскости и нор-|;   малью п к этой плоскости, направленной 
на-"ружу™"п*олупространстБа  (рис.  11.10). Для на-. хождения этого   
пересечения   рассмотрим ли-" ";  нейную неоднородную функцию 
    /      L (х) = скалярное произведение   (п,х — а}< 
    .>     которая обращается в нуль на граничной плоскости и возрастает вдоль 
вектора п. Тогда ограничивающее полупространство можно 
    описать как множество тех точек х е R3, в которых L(x)<0, т. е. как 
область отрицательности функции L. В концах обрабатываемого ребра функция L 
принимает значения 
    L0= L (xO) =скалярное произведение (п,хО —• а), LI = L (xl) «= скалярное 
произведение (n,xl — а). 
    Рассмотрим сужение этой функции на обрабатываемое ребро и подставим вместо 
х его выражение через t-координату на ребре. Вновь полученная функция (будем 
обозначать се той же буквой L) определена на отрезке [tO, tl] и принимает на 
его концах значения LO и L1. Поскольку эта функция является линейной 
неоднородной функцией, то ее значения в промежуточных точках отрезка можно 
вычислить по формуле	. . ^ , 
    L (t) = (LI — LO) * (t — tO)/(tl — tO) + LO. 
    В частности, корень функции L(t) можно найти из соотношения 
(Ll-LO)*(t--tO)/(tl-tO) + LO = 0.0,	/ 
    т. е. t:=t9 + (0.0-LO)/(Ll-LO)*(tl-tO). 
    Таким образом, искомое пересечение обрабатываемого ребра с ограничивающим 
полупространством — это интервал отридательностц 

    11. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА»	181 

    функции L(t) на отрезке [tO, tl]. Пустой интервал мы будем кодировать 
парой (tl.tO): 
    программа пересечение с (вх: а,п):отрезох 
    .   дано         :    а : точка R3 • 
    .	п: вектор R3 |п===0 
    .   получить: (пересечение (в t-координатах) ребра (xO.xl) с 
    | полупространством, которое направлено в сторону (вектора —п и ограничено 
плоскостью^ с нормалью п | проходящей через точку а 
    ахО := С.разность (вх:хО,а) .     axl := С.разность (вх:х!,а)	. 
    LO := С.скалярное произведение (п.ахО)   |т. е. LO:=(n,xO — a) .     L1 
:•• С.скалярное произведение (и,axl)   | т. е. Ll:=(n,xl — a) 
    выбор 
    .     .    при 1.0^0.0 и Ll> 0.0=*-ответ :=(tl,tO) 1 пусто .     ,    при 
L0< 0.0 и LK 0.0=*-ответ := (tO,tl) | все ребро 
    .    иначе => 
    .     t := tO + (0.0 -LO)/(Ll-LO)*(tl-tO)| корень L .     .      выбор	. . 
   .     .   при LO < 0.0»»- ответ := (tO,t) .     .      .   при LI < 0.0=*- 
ответ :=(t,tl) 
    .      .   иначе => отказ ,    .     конец выбора 
    конец выбора конец программы 
    программа R3 (их : отрезок): отрезок R3 == 
    (1<Н   оЛряэ (их : отрезок.начало), R3_o6paa (вх : отрезок.конец)) 
программа 1<3_образ (вх : t: число): точка R3 . дано        :   t: число, 
tO<t<tl 11 — координата точки на  ребре . получить: | координаты точки t в R3: 
    | xO + (xl - хО) * (t - tO)/(tl - tO) 
    dx 
    dxt ответ 
    = С.разность (вх:х!,хО) 
    = С. произведение <вх: dx) на (их: (t — tO)/(t I — tO)) 
    = С.сумма (exixO.dxt) 
    конец программы программа кончить работу' 
    ; ничего не делать 
    конец исполнителя 
    Еще один шаг декомпозиции совершен, и теперь осталось pea-лизовать 
исполнителей «Отрезки» в «Стереометр». Эти исполнители 

    182	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    не завзят друг от друга, и поэтому мы сначала реализуем то, что попроще — 
Отрезки: исполнитель Отрезки . СП: 
    1   отрезок (вх: А : отрезок) вырожден      : да/нет 
    2. получить разность (вх: А, В : отрезок) в (вых : L.R -.отрезок) 
    3. (вх/вых: А: отрезок) пересечь с (вх: В-.отрезок) 

    типы: отрезок = запись (начало, конец : число) 
    | если А.начало > А.кояец, то отрезок А пуст конец описаний |------ — - 
——— --        --      -      ~~ 
    1  программа отрезок (вх: А : отрезок) вырожден : да/нет == 
    1   1,ршрам	v                                                     
(А.начало >А.конец) 
    п  программа получить разность (вх:А,В) в (вых:Ь,К) 
    дано         '    А В:отрезок 
    \ получить:   L.R: отрезок [левая (Lett) и   правая (Right) отно-| 
снтельно В компоненты разности А\В 


    П. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА» 183 


    •   L.начало := А.начало 
    L.конец    := минимум (А.конец, В.начало) R.начало := максимум (А.начало, 
В.конец) .   R. конец   := А. конец конец программы 
    • программа (вх/вых: А: отрезок) пересечь с (вх : В : отрезок) . дано      
  :   А, В: отрезок . получить: |А:=ЛГ|В 
    !   А.начало := максимум (А.начало, В.начало) 
    А.конец    := минимум (А.конец, В.конец) конец программы конец исполнителя 
1==. = = = = === = = = = === = = == = = =х="=="~'~~~"" 
    Убедиться в правильности программы «пересечь с» можно, либо разобрав все 
случаи на картинках, либо формально, следующим образом: 
    А = и>А.начало}П(*<А.конец} (пересечение двух лучей) 
    В = {1 > В. начало} П U < В. конец} 
    Значит, 
    АПВ =={t> А. начало} П(1>В. начало} fUt < А. конец) П "        
х	{t<B.конец} = (t > максимум (А. начало, В. начало)} П 
    (t<минимум (А.конец, В.конец)}	: 
    И наконец, последний шаг декомпозиции — реализация Стерео-метра, т. е. 
сведение операций над точками и векторами в R3 к операциям над координатами 
этих точек и векторов: 
    исполнитель Стереометр .СП: 
    .      1. разность (вх : а,Ь : точка R3)	: вектор R3 .     2. сумма (вх : 
а : точка R3, Ь : вектор R3)                       : точка R3 
    3. произведение (вх : а : вектор R3) на (вх : k : число) : вектор R3 
    4. скалярное произведение   (вх : а,Ъ: вектор R3)	: число 
    5. векторное произведение (вх : а,Ь : вектор R3)	: вектор R3 
    . типы: 
    .      точка R3, вектор R3 • конец описаний 1 -—-
    = запись (x,y,z : число) 
    программа разность (ЕХ : а,Ь : точка R3): вектор R3 = = 
    ((а.х — b.x), (a.y —b.y), (а.2 — b.z)) 
    программа сумма (вх : а :точка R3, Ь: вектор R3): точка R3== 
    ((a.x + b.x), (а.у Ч-b.y), (a.z + b.z)) 
    программа произведение (вх : а) на (вх : k : число): вектор R3 == 
    ((k*.a.x), (k* а.у), (k*a.z)) 
    щкм'риммп скнлириос прошшсдсппс (вх : а,Ь : вектор R3): число —= 
    (a.x*b.x+a.y*b.y + a.z*b.z) 
    программа векторное произведение (вх : а, Ь): вектор R3== 
    ((«.у * b.z — a.z * b.y), (a.z * b.x — а.х * b.z), (a.x*b.y — a.y*b.x)) 
    вомец исполнителя | = = = = =, = = ===== === = ===; = = ==,= ,= = = .»,»*, 

    Оптимизация алгоритма построения изображения полиэдра. Итяк, мы лппгршпли 
реализацию проекта «Построение изображения поличдря» и н-нерь можем обсудить, 
что получилось. Получилась ри;||К|Г>1>к111ная по технологии «сверху вниз» 
хорошо структурнро-ниннаи программа, которая, однако, достаточно наивна, 
делает много лишней работы и на сложных полиэдрах (несколько тысяч ребер и 
граней) будет работать очень долго. Хорошая структурировав ность программы 
позволяет се легко менять и оптимизировать. Мы сейчас опишем две такие 
модификации: фильтрование и предкомпи-ляцию граней. Еще одна модификация будет 
описана в разд.,,15. 
    Фильтровани^~гранё'йГТ1осмотрим, где наша программа де'лает лишнюю работу, 
которой можно было бы избежать. Наиболее содержательным является выполнение 
программы «Изобразитель реб-ра.учесть тень от грани» — при этом происходит 
обращение к исполнителю «Геометр», находятся нормаль и центр грани, 
горизонтальное и вертикальные пересечения, пересекаются отрезки в 
t-коордн-патах на ребре и т, д, Все эти действия выполняются для каждой 

    184	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    пары (ребро, грань). Но взгляните на рис. 11.11 —для каждого конкретного 
ребра лишь очень немногие грани (а именно грани, распо-ложенные на плоскости 
проекции рядом с ребром) действительно 

    Рис.  11.11 

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

    Рис. 11.12 

    Одно из решений выглядит так: введем на плоскости проекции координаты u, 
v. Назовем прямоугольником грани наименьший прямоугольник вида umin sj uej 
umax, vmin =?J v ^ vmax, содержащий проекцию    грани,    Аналогично    
определим    прямоугольник    ребра (рис, 11.12). 

    11. ПРОЕКТ сПОСТРОЕИИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА» 185 

    Очевидно, что если прямоугольники ребра и грани не пересекаются, то грань 
заведомо не затеняет ребро, и, значит, эту грань можно не учитывать при 
построении изображения видимой, части ребра: 
    программа построение изображения полиэдра 
    .   дано         : | полиэдр в R3 (исполнитель "Полиэдр") 
    | направление проектирования (исполнитель "Проектор") .   получить: | 
плоское изображение ребер полиэдра (параллельная 
    | проекция) с "удалением невидимых линий" 
    цикл у ребро е Полиэдр.множество ребер выполнять .    .    Фильтр.начать 
работу (вх: ребро)	• .     .    Изобразитель ребра.начать работу (вх :ребро) . 
    .     цикл у грань е Полиэдр.множество граней выполнять .     .     .      
если Фильтр.грань (вх : грань) имеет отношение к  ребру .     .то 
    Изобразитель ребра.учесть тень от грани  (вх: грань) конец если .     .    
конец цикла 
    ,     ,    II iofi|)n:iiiT(Mi. pi'fipn.кончить работу .     .    
Фильтр.кончить работу 
    конец цикла конец программы 
    Здесь предписание «грань имеет отношение к ребру» исполнителя «Фильтр» 
вырабатывает значение да, если прямоугольник грани пересекает прямоугольник 
ребра, и нет в противном случае, 
    исполнитель Фильтр . СП: 
    1. начать работу (вх:ребро) 
    2. грань (вх : грань) имеет отношение к ребру      : да/нет 
    3. кончить работу 
    ;,    типы: 
    i     прямоугольник = запись (umin,vmin,umax, vmax : R) 
    .    объекты: 
    P : прямоугольник | прямоугольник ребра на плоскости UV 
    .    используемые исполнители: 
    UV    | (нахождение прямоугольников ребер и граней) 
    конец описаний 

    ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 186 

    программа начать работу (вх: ребро) . дано        :ребро: ребро . получить: 
    .   Р := UV.прямоугольник ребра (вх": ребро) 
    конец программы 
    программа грань (вх: грань) имеет отношение к ребру: да/нет 
    , дано         :    грань:грань 
    , получить: | ответ = (прямоугольники ребра и грани пересекаются) 
    ,    Г := UV.прямоугольник грани (их: грань) 
    ,   ответ := 
    ,        максимум (P.umm.r.umin) < минимум(Р.итах,Г.ипгах) и 
    максимум (P.vmin,Г.vmin) < минимум (P.vmax.r.vmax) конец программы 
    программа кончить работу = ничего не делать конец исполнителя [   —=-- = = 
»i«1=-- = = -===- —======. = =>=.e 

    Реализация исполнителя UV оставляется читателю. Заметим лишь, что 
координаты и и v на плоскости проекции могут быть и косоугольными. Например, 
если вектор проектирования не параллелен плоскости z = 0 (т. е. p.z =?fe 0), 
то в качестве и и v можно использовать просто х и у компоненты трехмерных 
координат то-•чек плоскости проекции. 
    В  модифицированной  программе для далеких от ребра граней проводятся  
только тривиальные  вычисления  прямоугольника  грани и сравнение этого  
прямоугольника  с  прямоугольником  ребра.  Поскольку для каждого конкретного 
ребра  подавляющая  масса  граней являются далекими, то скорость построения 
изображения полиэдра возрастет примерно во столько 
    раз, во сколько фильтрование быстрее учета тени от грани на ребро. Таким 
образом, фильтр тем лучше, чем меньше гранен он пропускает и чем быстрее он 
работает.   Эти  требования  являются   противоречивыми.   Идеальным   по 
критерию  минимума  граней  является   фильтр,  который  пропускает только 
действительно затеняющие ребро грани. Однако определение таких граней  почти  
не  отличается  от  нахождения  тени от грани па ребро и никакого выигрыша в 
скорости не дает. Идеальным по критерию скорости работы является фильтр, 
который пропускает все грани вообще, но применение такого фильтра 
бессмысленно. Поэтому требуется разумный компромисс — фильтр, который быстро 
отсеивает основную  массу  не имеющих  отношения  к ребру  граней, пропуская, 
быть может, какое-то количество «подозрительных» ??а

    II.  ПРОЕКТ  «ПОСТРОЕНИЕ  ИЗОБРАЖЕНИЯ ПОЛНЭДРА> 187 
    
    ней, на самом деле ребро не затеняющих. Одним из таких разумных 
коТипромнссов  и  является   реализованный  выше фильтр   на  основе прямоугольников. 
    Предкомпиляций граней. Можно ожидать, что после введения фильтра основное 
время работы будет уходить на выполнение программы «грань имеет отношение к 
ребру». Эта программа вызывается для каждой пары (ребро, грань) и состоит в 
вычислении прямоугольника грани и анализе его пересечения с прямоугольником 
ребра. Таким образом, прямоугольник каждой гран и вычисляется многократно 
(заново для каждого ребра). Очевидная оптимизация состоит в том, чтобы заранее 
до начала построения изображения одни раз вычислить прямоугольники всех 
граней, запомнить их и использовать при фильтровании. 
    Опнсинмый прием носит общий характер и называется заменой интср-. 
i\i>era((uu л<тпил«1(1ч'Д. ['.ели эадли объект и необходимо многократно 
ис-иильзшыть сиедсиня, которые нзилекаюгся из описания объекта ценой каких ю 
вычислении, то вместо многократного повторения этих вычислений (интерпретации 
описания объекта) можно провести их заранее (компилировать описание объекта) и 
запомнить результат. Заметим, что для запоминания результата компиляции 
требуется дополнительная память. Вопрос о соотношении интерпретации и 
компиляции в каждом конкретном случае ]'СШ»ет1'н по-своему, исходя из 
специфики задачи. Если, например, основное йрсмч iioi'i роения изображения 
полиэдра и после введения фильтра тра THRU на нахождение теней ст граней, то 
при предкомпиляции разумно вычислять не только прямоугольник грани, но и 
коэффициенты линейных неоднородных функций, задающих тень от грани в R3. 
    Обратите внимание, что, несмотря на все оптимизации, мы по-прежнему для 
каждого ребра анализируем все грани, только теперь для большинства граней этот 
анализ производится достаточно бистро. Построение изображения полиэдра можно 
еще ускорить, mill дли каждою ребра анализировать только близкие, 
«по-дшритсмшшс» грани, а далекие вообще никак не рассматривать. Идеи такой 
реализации (идеи двумерного хеширования по равномерной сетке), а также сама 
реализация будут изложены в разд, 15'.' 

    ЗАДАЧИ И УПРАЖНЕНИЯ 

    В задачах 1—7, при необходимости изменив проект «Построение изображения 
полиэдра», напишите программу, которая находит: 
    1. Сумму длин всех ребер полиэдра. 
    2. Число вершин грани <вх : грань). 
    3. Число геометрически различных' вершин полиэдра. 
    4. Видима ли точка <вх : точка R3>. 5. Число граней полиэдра, 
пересекающихся с <вх : отрезок R3). 
    6. Число.всех полностью видимых ребер полиэдра. 
    7. Число всех полностью невидимых ребер полиэдра. 

    188 гл. г. НЕСКОЛЬКО ПРИМЕРОВ ПРОГРАММ 

    8. Реализуйте исполнителя UV. 
    9. Реализуйте предкомпиляцию прямоугольников граней, считая, что 
предписание «Полиэдр.множество граней» принимает и вы* рабатывает значение 
типа «множество элементов типа грань с нагрузкой типа прямоугольник». 
    10. Считая, что исполнитель «Проектор» вместо вектора проек. тироваяия 
работает с точкой f из R3 и плоскостью П, отделяющей f от полиэдра, напишите 
программу, которая строит изображение полиэдра на плоскости П при 
перспективной проекции с центром в точке f.