Входные данные и внутреннее представление

АНАЛИЗ ЭФФЕКТИВНОСТИ

Не всегда простые программы лучше сложных. В некоторых задачах простые алгоритмы работают слишком медленно и требуются более мощные алгоритмы, иногда реализуемые в виде чрезвычайно сложных программ. Примером может служить задача сортировки. Программы, описанные в главе 4, для формирования перспективных чертежей были сравнительно простыми и быстрыми. Очевидно, что сложность таких программ будет значительно возрастать, если потребуется автоматически удалять невидимые части отрезков. Наряду со сложностью самой задачи неизбежно возникают другие проблемы, когда программа должна работать как можно быстрее. Кроме обеспечения эффективности необходимо удовлетворить требования общности, устойчивости к ошибкам и удобства для пользователей, что в конечном счете приводит к потенциальному усложнению программы. Этим четырем аспектам качества уделено столько внимания, что читатель может подумать, что теперь мы будем рассматривать только очень сложные программы. На самом деле более привлекательно начать с анализа несколько упрощенной программы, чем с быстро работающей, но непонятной. Поэтому начнем с программы, обладающей сложностью порядка п. Это означает, что время вычислений будет примерно пропорционально п, где п — число отрезков прямых линий или полигонов, подлежащих вычерчиванию. Программа будет работать достаточно быстро при вычерчивании простых объектов, содержащих несколько сотен граней. Данные, описывающие объект, будут храниться в массивах фиксированных размеров. Это также ограничит сложность объектов. Кроме этих ограничений, в остальном программа будет достаточно общей: в принципе могут быть вычерчены любые конечные объекты, имеющие только конечное число плоских граней. Что же касается устойчивости к ошибкам и удобства пользователей, то не будем требовать, чтобы все ошибки при их. появлении сопровождались четкими сообщениями и чтобы объекты определялись наиболее удобным способом. Позднее эта программа будет усовершенствована, особенно в отношении эффективности. Проблема удаления невидимых линий реализуется алгоритмами с чрезвычайно большими затратами вычислительного времени и она всегда была хорошей задачей для программирующих математиков.

Ребро объекта может закрываться полностью или частично одной или несколькими гранями этого же объекта. Каждое ребро — это конечный отрезок прямой линии. Объект может состоять из нескольких частей, не обязательно соединяющихся между собой. На рис. 8.1 изображены тетраэдр и куб с вершинами, обозначенными числами 0, 1, 2,... вместо букв А, В, С,.... Точки с обозначениями 12, 13, 14 позволяют вычертить положительные координатные полуоси.

Составим такую программу, которая прочтет данные, описывающие точку наблюдения и объекты. Для любой (реальной) точки наблюдения графический вывод будет представлять собой изображение объекта. Будем считать объект непрозрачным. Пользователь должен задать две входные строки данных, определяющие точку О в прямоугольной системе координат и сферические координаты rho.theta.phi для точки наблюдения. Для рис. 8.1 это будут следующие строки:

2.5 1 1 (центр объекта О)

8 20 70 (rho.theta.phi)

He будем здесь уделять много внимания удобству пользователя, а лучше введем концепцию кодирования вершин: поскольку каждая вершина потребуется несколько раз, то было бы очень нецелесообразно многократно задавать ее координаты. В данном примере для каждой вершины будем задавать ее номер от 0 до 11 вместе со значениями координат по осям х, у, z. Конец этой части вводимой информации будет обозначаться отдельной строкой с символом # в первой позиции:

0 5 0 0	(x0=5,y0=0,z0=0)	8 2 0 2
1 3 2 0	(xl=3, yl=2, zl=0)	9 2 2 2
2 3 0 0	(и т.д.)	10 0 2 2
3 3 0 2		11 0 0 2
4 2 0 0		12 7 0 0
5 2 2 0		13 0 4 0
6 0 2 0		14 0 0 3
7 0 0 0		#

Точка О объекта является началом системы мировых координат, используемой в программе (обратите внимание на различие между буквой О и цифрой 0). Поскольку она имеет координаты (2.5, 1, 1), то внутри программы координаты точек с 0 по 14 будут уменьшены на эти значения. Так, на­пример, точке 9 будут присвоены значения координат (-0.5, 1, I) вместо заданных (2, 2, 2). Каждая грань объекта может быть описана в виде любой конечной области плоскости с границами в виде отрезков прямых линий. В качестве примера такой области можно назвать полигон, в котором допустимы также и отверстия. Чтобы программа была проще, пользователь должен сам разбить такие области на треугольники. Эти треугольники затем будут использоваться для определения, не закрывают ли они отрезки прямых линий. По причинам, которые поясним ниже, номера вершин в каждом треугольнике перечисляются в порядке обхода против часовой стрелки при рассматривании их с внешней стороны объекта. Каждая грань куба разбивается на два треугольника. Эту часть входных данных опять завершает символ # (на новой строке).

1 3 0	(треугольные грани тетраэдра)
1 2 3
2 0 3
0 2 I
4 5 8	(передняя грань куба)
8 5 9
5 6 9	(правая грань)
9 6 10
8 9 10	(верхняя грань)
8 10 II
6 7 10	(задняя грань)
10 7 II
7 4 8	(левая грань)
7 8 II
6 5 4	(нижняя грань)
6 4 7	#

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

7 12	(ось х)	5 6
7 13	(ось у)	8 9
7 14	(ocь z)	8 9
0 1	(тетраэдр)	9 10
1 3		10 11
3 0		8 11
1 2		4 8
2 3		6 10
4 5	(куб)

Программа выполнит считывание всех входных данных из файла, имя которого передается в качестве аргументов программы (argc и argv). Координаты каждой вершины сохраняются в массиве VERTEX, элементами которого являются структуры, содержащие три поля х, у, z. Заданные пользовательские координаты сначала переводятся в координаты системы, начало которой расположено в объектной точке О. Внутренние мировые координаты, в свою очередь, преобразуются в видовые координаты с помощью видовых преобразований. И именно эти видовые координаты записываются в массив VERTEX:

I	VERTEX[ i ]
½	х У z
¯	¯ ¯ ¯
	...
	...
.	...
.	...

Как мы уже знаем, точка Е — начало системы видовых коор­динат, и направление наблюдения совпадает с направлением оси z. Следовательно, все значения VERTEX[i].z должны быть положительными. Это условие проверяется в программе, и выполнение программы прекращается, если оно не выполнено. Список треугольников запоминается в массиве TRIANGLE:

J	TRIANGLE [ J ]
½	А В С a b с h
¯	¯ ¯ ¯ ¯ ¯ ¯ ¯
	.......
	.......
.	.......

Вместе с номерами вершин для каждого треугольника записываются коэффициенты а, b, с, h уравнения плоскости

ax+by+cz = h (8.1)

в которой расположен треугольник. Конечно, их можно было бы рассчитывать каждый раз, когда они оказываются необходимыми, но это означало бы напрасную трату времени, поскольку они требуются довольно часто. (Здесь четвертый коэффициент обозначен через h вместо d, так как эта буква уже использована для обозначения расстояния до экрана.) Коэффициенты а, b, с выбираются такими, чтобы удовлетворялось условие

a²+b²+с²=1 и h>=0

Тогда уравнение (8.1) можно записать в виде скалярного произведения

n * х = h

где

n = [а Ь с]

х = [х у z]

Так называемый вектор нормали n представляет собой вектор единичной длины, перпендикулярный плоскости треугольника. Для любой точки Х в этой плоскости вектор х = ЕХ имеет такое свойство, что его скалярное произведение h=n•х равно расстоянию между точкой Е и плоскостью. Скалярное произведение было введено ранее. Заметим, что здесь мы используем систему видовых координат с точкой Е в качестве начала системы координат и отрезок ЕО определяет положительное направление оси z. Плоскость, параллельная экрану, описывается уравнением z = h, которое является вырожденным случаем общего уравнения (8.1) при а=b=0, с=1. В общем случае коэффициенты а, b, с, h вычисляются по координатам вершин треугольника А, В, С. Плоскость, проходящая через эти точки, описывается уравнением

в виде

В программе коэффициенты a, b, с, h вычисляются по формулам:

a = yA* (zB-zC-yB * (zA-zC) + yC * (zA-zB);

b = - (xA* (zB-zC) - xB * (zA-zC) + xC * (zA-zB));

c = xA* (yB-yC) -xB * (yA-yC)+xC * (yA-yB);

h = xA * (yB*zC - yC*zB) - xB * (yA*zC - yC*zA) + xC * (yA*zB - yB*zA);

if (h > 0)

{ r = sqrt(a*a+b*b+c*c);

a = a/r; b = b/r; с = c/r; h = h/r;

} else

{... /* Треугольник АВС может быть проигнорирован по указанным ниже.причинам */

}

Однократное вычисление коэффициентов а, b, с, h, вместо их определения при каждой проверке отрезка на видимость, позволяет значительно сократить время вычислений. Если программа действительно должна быть по возможности проще, то необходимо было бы запоминать все треугольники по мере их ввода. Однако те треугольники, которые находятся сзади, сохранять не требуется и их можно проигнорировать. Рассмотрим треугольник 123 на рис. 8.1. На картинке он закрыт треугольником 130. Поскольку последний треугольник закрывает часть отрезка 45, то можно проигнорировать тот факт, что предыдущий треугольник делает то же самое. Задние грани закрываются видимыми гранями. Хотя задние грани могут закрывать от глаза некоторые точки, эти же точки закрываются и видимыми гранями. Вот почему задние грани можно проигнорировать. Самый простой способ идентификации задних граней основан на ориентации вершин. Если мы посмотрим на грань 123 на рис. 8.1 в трехмерном пространстве извне (то есть со стороны отрицательной полуоси х), то порядок обхода вершин 123 при вводе будет против часовой стрелки, поскольку такая ориентация требовалась при определении входной последовательности. Однако на рис. 8.1 порядок обхода 123 соответствует движению часовой стрелки. Это означает, что на картинке эта грань видна через тело объекта, а не извне. Таким образом, грань 123 — задняя. Применение этого способа определения положения граней для других треугольников на рис. 8.1 может послужить хорошим упражнением. Обращаясь к концу параграфа 3.4, можно

обнаружить, что в этом случае требуется найти значение детерминанта

где X_A, Y_A, X_B,,Y_B,,X_C,Y_C — экранные координаты вершин А, В, С треугольника. Треугольник АВС будет задним, если D< 0. Но нет необходимости в действительном вычислении детерминанта, поскольку можно записать

(8.2)

Так как значения Za, Zb, Zc всегда положительны, то D имеет тот же знак, что и величина h, вычисленная в предыдущей программе. Если h= 0, то плоскость АВС проходит через точку начала координат Е, совпадающей с точкой наблюдения. В этом случае треугольник АВС не будет закрывать никаких отрезков и его не надо запоминать в массиве TRIANGLE. При h<0 детерминант D также имеет отрицательный знак и треугольник АВС является задним. Поэтому треугольник АВС будем записывать в массив только в том случае, если h > 0 или, другими словами, если D > 0. С помощью векторного произведения можно убедиться, что треугольник АВС — задний, из условия h < 0 и без привлечения экранных координат. Но доказательство этого условия оставляем для упражнения читателям с хорошей математической подготовкой.

Дата добавления: 2014-01-14