ГЛАВА 12

Общий алгоритм удаления невидимых линий

Как и в предыдущих главах, мы полагаем, что объекты создаются программой "SCENE3", но теперь мы требуем, чтобы NOV вершин, принадлежащих изображаемым объектам, хранились в массивах X, Y, Z. Их перспективная проекция на визуальную плоскость хранится в массивах V и W. NOF граней хранятся в виде списка принадлежащих им вершин в массиве F (допускаются грани, содержащие не более шести вершин), в массиве H хранится число вершин каждой грани.

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

Мы также полагаем, что любой из отрезков, из которых состоит рисунок, получается в результате пересечения двух смежных граней: если требуется изобразить отдельную линию, то её следует представить, как вырожденную грань, ограниченную двумя отрезками. Эти ограничения введены для ускорения алгоритма удаления невидимых линий. Это очень важно, так как мы теперь приближаемся к предельным возможностям SPECTRUMa. Даже для такого простого рисунка, как два куба на рис. 40, требуется около пяти минут машинного времени, а для более сложных изображений ещё больше. SPECTRUM не был рассчитан на решение таких сложных задач, и то, что нам удается это сделать, следует считать показателем высокого качества работы проектировщиков SPECTRUMa.

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

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

Предположим, что типичная прямая Г3' в наблюдаемом положении соединяет две точки (X1',Y1',Z1') с (X2',Y2',Z2'), тогда координаты точки, лежащей на этой прямой, есть

(1-#)*(X',Y1',Z1')+#*(X2',Y2',Z2')

Предположим, что две концевые точки проецируются в точки (X1,Y1) и (X2,Y2) визуальной плоскости. Тогда Г3 проецируется на визуальную плоскость как прямая Г2, а координаты точек, лежащих на этой прямой есть

(1-MU)*(X1,Y1)+MU*(X2,Y2)

Обратите внимание, что ниоткуда не вытекает, что точка (1^)*(Xr,Yr,Z1')+ Ф*(X2',Y2',Z2') проецируется в точку (ЬФ^^Д^+Ф*^^), это означает, что Ф не равно MU.

Пусть грань общего положения ОМЕГА1 проецируется на область ОМЕГА2, лежащую в визуальной плоскости. Предположим, что H вершин проекции грани есть (XI,YI), где 1<=I<=H. Пусть 1-ое ребро ОМЕГА2 пересекает Г2 в точке (1- Л^^Д^Л!*^^!^^!)). Если ЛК0 или Ш>1, то это означает, что Г2 пересекает продолжение I-го ребра в точке, лежащей за пределами области ОМЕГА2: если 0<=Ш<=1, тогда Г2 пересекает область ОМЕГА2 в точке, лежащей на I-ом ребре. Так как проекция выпуклой грани выпукла, то число точек пересечения либо равно нулю, или равно двум (возможно совпадающим точкам).

Нам требуется рассмотреть только случай несовпадающих точек: предположим, что соответствующие этим точкам значения параметра MU есть MU(MIN) и MU(MAX), где MU(MIN)<MU(MAX). Тогда точки пересечения с Г2 есть

(1-MU(MIN))*(X1,Y1)+ MU(MIN)*(X2,Y2) и (1-MU(MAX))*(X1,Y1)+ MU(MAX)*(X2,Y2).

Теперь необходимо установить, является ли отрезок, заключенный между этими точками, видимым или нет. Это проверяется нахождением середины этого отрезка - точки

(X(MID),Y(MID))=(1-MU(MID))*(X1,Y1)+MU(MID)*(X2,Y2),

где

MU(MID)=(MU(MIN)+MU(MAX))/2.

Затем мы находим точку (X,Y,Z), лежащую на Г3 такую, что перспективной проекцией этой точки будет (X(MIN),Y(MIN)). Отрезок линии между точками, со значениями параметра MU, равными MU(MIN) и MU(MAX) является невидимым, если и только если точка (X,Y,Z) и глаз наблюдателя расположены по разные стороны плоскости, в которой лежит ОМЕГА3. Уравнения этой плоскости можно найти с помощью методов главы 1, а затем применить для проверки приведенного выше условия функциональное представление этой плоскости.

Обратите внимание, что X*PPD/Z=X(MID), Y*PPD/Z=Y(MID) и точка (X,Y,Z) лежит на Г3. Поэтому для некоторого значения параметра Ф:

Х=(1-Ф)*Х1'+Ф*Х2', Y=(1-#)*Y1'+#*Y2' иZ=(1-#)*Z1'+#*Z2';

так как

X(MID)=((X1^,+#*(X2^,-X1^,))*PPD)/(Z1^,+#*(Z2^,-Z1')) и Y(MID)=((Y1^,+#*(Y2^,-Y1^,))*PPD)/(Z1^,+#*(Z2^,-Z1')),

то отсюда следует, что

#=(X(MID)*Z1,-X1,*PPD)/((X2,-X1,)*PPD-X(MID)*(Z2,-Z1,))= (Y(MID)*Z1,-Y1,*PPD)/((Y2,-Y1,)*PPD-Y(MID)*(Z2,-Z1,))

Это позволяет нам вычислить Ф, а следовательно и точку (X,Y,Z), которая в свою очередь используется для проверки того, видима ли часть отрезка Г2 или нет.

В алгоритме, реализованном в программе "HIDDEN" на листинге 12.1, каждая линия, принадлежащая какому-либо объекту, сравнивается со всеми видимыми гранями (теми, проекции которых обходятся против часовой стрелки). Обратите внимание, что мы считаем, что все объекты непрозрачны, то есть невозможно увидеть внутреннюю поверхность ни одной из граней, т.е. увидеть грань, проекция которой обходится по часовой стрелке. Информация о ребрах содержится в информации о гранях, причём каждое ребро встречается дважды, один раз оно проходит от точки IV1 к точке IV2. Для того чтобы избежать повторений, мы рассматриваем только такие ребра, у которых IV1<IV2. Мы сопоставляем ребра только с видимыми гранями, так в силу наложенных на объекты ограничений, если ребро заслонено от наблюдателя невидимой гранью, то оно должно быть отделено от наблюдателя так же и видимой гранью.

Предположим, что на некотором этапе процедуры сравнения для прямой Г2, соединяющей вершины K-ой грани IV1 и IV2, мы нашли NRL видимых подотрезков данного отрезка; мы полагаем, что NRL<50. Значения параметра MU, соответствующего концевым точкам M-того видимого отрезка, заносятся в массив L как L(1,M) и L(2,M).

В начале процедуры мы полагаем NRL=1, L(1,1)=0 и L(2,1)=1. что означает, что мы считаем прямую видимой. Если на этой стадии обнаруживается новый невидимый отрезок, определяемый значениями MU(MIN) и MU(MAX) (переменные МАХ и MIN), то эти значения заносятся в массив L, и NRL соответствующим образом изменяет своё значение.

Когда прямая сравнивается со всеми видимыми гранями, то в результате у нас NRL видимых отрезков, которые можно нанести на экран. Если в какой-нибудь момент NRL принимает значение 0, то это означает, что весь отрезок является невидимым, а следовательно можно прекратить процедуру сравнения для этого отрезка.

Пример 12.1

Теперь мы можем удалить невидимые линии на рис. 37; результат показан на рис. 40. Значение входных параметров: HORIZ=9, VERT=6, глаз наблюдателя расположен в точке (15,10,15), взгляд направлен в (0,0,0).

Рис. 40.

LISTING 12.1

7000 REM HIDDEN/GENERAL HIDDEN LINE ALGORITM

REM IN - NOV,NOL,PPD,R(4,4),X(NOV),Y(NOV),Z(NOV),V(NOV),W(NOV),H(NOF)

DIM L(2,50): DIM G(NOF): LET EPS=0.000001

REM CHECK ON I,TH PROJECTED FACET-ANTICLOCKWISE SET G(I)=1, CLOCKWISE OR SET G(I)=0. FOR I=1 TO NOF LET I1=F(1,I): LET I2=F(2,I): LET I3=F(3,I): LET DX1=X2-X1: LET DX2=X3-X2: LET G(I)=0

IF DX1*DY2-DX2*DY1>0 AND H(I)>2 THEN LET G(I)=1 NEXT I

REM FIND J,TH LINE ON THE EDGE OF I,TH FACET. FOR I=1 TO NOF LET HH=H(I): LET IV1=F(HH,I) LET X1=V(IV1): LET Y1=W(IV1) FOR J=1 TO HH LET IV2=F(J,I)

LET X2=V(IV2): LET Y2=W(IV2) IF IV1>IV2 THEN GO TO 8160 REM INITIALISE VARIABLES. LET NRL=1: LET L(1,1)=0: LET L(2,1)=1 LET CA=X2-X1: LET CB=Y1-Y2

7200 LET CC=-X1*CB-Y1*CA

7209 REM COMPARE THIS LINE WITH THE K'TH FACET.

7210 FOR K=1 TO NOF

7220 IF G(K)=0 THEN GO TO 8040

7230 IF K=1 THEN GO TO 8040

7240 LET in=H(K)

7249 REM LOOP TO FIND TWO POINTS OF INTERSECTION OF PROJECTED LINE WITH PROJECTED FACET. THESE POINTS SPECIFIED BY MU VALUES MIN AND MAX.

7250 LET MAX=-1: LET MIN=2 7260 LET JV1=F(in,K)

7270 LET VX1=V(JV1): LET WY1=W(JV1)

7280 LET S1=SGN(CA*WY1+CB*VX1+CC)

7290 FOR M=1 TO in

7300 LET JV2=F(M,K)

7310 LET VX2=V(JV2): LET WY2=W(JV2)

7320 LET S2=SGN(CA*WY2+CB*VX2+CC)

7330 IF S1=S2 THEN GO TO 7500

7340 LET XE=VX1-VX2: LET YE=WY1-WY2

7350 LET XF=VX1-X1: LET YF=WY1-Y1

7360 LET DISC=CA*YE+CB*XE

7369 REM IF LINE IS PARALLEL TO A LINE ON THE FACET THEN EXIT FACET LOOP.

7370 IF ABS DISC>EPS THEN GO TO 7440 7380 IF ABS CA>EPS THEN GO TO 7410 7390 IF ABS XF<EPS THEN GO TO 8040 7400 GO TO 7500

7410 LET LAMBDA=XF/CA

7420 IF ABS (XF+LAMBDA*CB)<EPS THEN GO TO 8040

7430 GO TO 7500

7440 LET LAMBDA=(CA*YF+CB*XF)/DISC

7449 REM IF LINE MISSES K'TH FACET THEN GO TO NEXT FACET.

7450 IF LAMBDA<-EPS THEN GO TO 7500 7460 IF LAMBDA>1+EPS THEN GO TO 7500 7470 LET MU=(YE*XF-XE*YF)/DISC

7479 REM A TRUE INTERSECTION SO UPDATE MAX AND MIN.

7480 IF MAX<MU THEN LET MAX=MU 7490 IF MIN>MU THEN LET MIN=MU 7500 LET S1=S2

7510 LET VX1=VX2: LET WY1=WY2

7520 NEXT M

7529 REM CHECK IF INTERSECTIONS LIE BETWEEN SPECIFIED END POINTS OF LINE.

7530 IF MIN>1 THEN GO TO 8040 7540 IF MAX<0 THEN GO TO 8040 7550 IF MAX>1 THEN LET MAX=1 7560 IF MIN<0 THEN LET MIN=0

7570 IF MAX-MIN<EPS THEN GO TO 8040

7579 REM CALCULATE XMID AND YMID

7580 LET MID=(MAX+MIN)*0.5: LET MUD=1-MID 7590 LET XMID=MUD*X1+MID*X2

7600 LET YMID=MUD*Y1+MID*Y2

7610 LET DENOM=PPD*(X(IV2)-X(IV1))-XMID*(Z(IV2)-Z(IV1))

7620 IF ABS DENOM<EPS THEN GO TO 7650

7629 REM CALCULATE PHI AND HENCE XHAT,YHAT,ZHAT.

7630 LET PHI=(XMID*Z(IV1)-PPD*X(IV1))/DENOM 7640 GO TO 7670

7650 LET DENOM=PPD*(Y(IV2)-Y(IV1))-YMID*(Z(IV2)-Z(IV1))

7660 LET PHI=(YMID*Z(IV1)-PPD*Y(IV1))/DENOM

7670 LET ZHAT=(1-PHI)*Z(IV1)+PHI*Z(IV2)

7680 LET FACT=ZHAT/PPD

7690 LET XHAT=XMID*FACT: LET YHAT=YMID*FACT

7699 REM CALCULATE COEFFICIENTS OF PLANE CONTAINING FACET - A,B,C,D.

7700 LET JV1=F(1,K): LET JV2=F(2,K): LET JV3=F(3,K) 7710 LET DX1=X(JV1)-X(JV2)

7720 LET DX3=X(JV3)-X(JV2)

7730 LET DY1=Y(JV1)-Y(JV2)

7740 LET DY3=Y(JV3)-Y(JV2)

7750 LET DZ1=Z(JV1)-Z(JV2) 7760 LET DZ3=Z(JV3)-Z(JV2)

7770 LET A=DY1*DZ3-DY3*DZ1

7780 LET B=DZ1*DX3-DZ3*DX1

7790 LET C=DX1*DY3-DX3*DY1

7800 LET D=A*X(JV1)+B*Y(JV1)+C*Z(JV1)

7810 LET S1=A*XHAT+B*YHAT+C*ZHAT-D

7819 REM IF FACET HIDES PART OF LINE THEN CHANGE THE L ARRAY.

7820 IF ABS S1 <EPS THEN GO TO 8040

7830 IF ABS (SGN S1+SGN D)<2 THEN GO TO 8040

7840 LET MORE=NRL

7850 FOR M=1 TO NRL

7860 LET R1=L(1,M): LET R2=L(2,M)

7870 IF (R1>MAX) OR (R2<MIN) THEN GO TO 7960

7880 IF (R1>=MIN) AND (R2<=MAX) THEN GO TO 7950

7890 IF (R1<MIN) AND (R2>MAX) THEN GO TO 7920

7900 IF (R1<MIN) THEN GO TO 7940

7910 LET L(1,M)=MAX: GO TO 7960

7920 LET MORE=MORE+1

7930 LET L(1,MORE)=MAX: LET L(2,MORE)=R2 7940 LET L(2,M)=MIN: GO TO 7960 7950 LET L(1,M)=-1 7960 NEXT M

7969 REM TIDY UP THE L ARRAY.

7970 LET NRL=0

7980 FOR M=1 TO MORE

7990 IF L(1,M)<=EPS THEN GO TO 8020

8000 LET NRL=NRL+1

8010 LET L(1,NRL)=L(1,M): LET L(2,NRL)=L(2,M) 8020 NEXT M

8030 IF NRL=0 THEN GO TO 8160 8040 NEXT K

8049 REM DRAW VISIBLE PARTS OF LINE.

8050 FOR K=1 TO NRL

8060 LET R1=L(1,K): LET R2=1-R1

8070 LET XP1=X1*R2+X2*R1

8080 LET YP1=Y1*R2+Y2*R1

8090 LET R1=L(2,K): LET R2=1-R1

8100 LET XP2=X1*R2+X2*R1

8110 LET YP2=Y1*R2+Y2*R1

8120 IF (ABS(XP1-XP2)<EPS) AND (ABS(YP1-YP2)<EPS) THEN GO TO 8150 8130 LET XPT=XP1: LET YPT=YP1: GO SUB MOVETO 8140 LET XPT=XP2: LET YPT=YP2: GO SUB LINETO 8150 NEXT K

8160 LET IV1=IV2: LET X1=X2: LET Y1=Y2 8170 NEXT J 8180 NEXT I 8190 RETURN

Мы используем программу "HIDDEN", приведенную на листинге 12.1, "LIB1", "LIB3" и подпрограммы "SCENE3" и "CUBE", приведенные на листинге 12.2. В этой последней версии подпрограммы "CUBE" мы привлекли все методы построения объектов, использующие операции с массивами. Мы умышленно используем куб в наших программах, так как это чрезвычайно простой объект, на котором удается легко продемонстрировать общие идеи трёхмерной графики. Теперь настало время усложнить сами объекты: если вы понимаете ограничения, накладываемые алгоритмами на объекты, то все идеи, изложенные ранее, остаются в силе. Пользователи с объёмом памяти 16К обнаружат, что столь сложные программы не помещаются в памяти. В этом случае программы следует разбить на независимые сегменты, а информация об объектах и массивы должны записываться на пленку.

LISTING 12.2

6000 REM SCENES/EXAMPLES

6010 DIM X(16): DIM Y(16): DIM Z(16)

6020 DIM V(16): DIM W(16): DIM H(12): DIM F(4,12)

6030 DIM A(4,4): DIM B(4,4): DIM R(4,4): DIM Q(4,4)

6040 LET CUBE=6500: LET HIDDEN=7000

6050 LET PPD=3*VERT: LET NOV=0: LET NOF=0

6059 REM PUT FIRST CUBE IN OBSERVED POSITION-(ACTUAL-SETUP).

6060 GO SUB IDR3: GO SUB LOOK3 6070 GO SUB CUBE

6079 REM COPY ACTUAL TO OBSERVED MATRIX INTO Q.

6080 FOR I=1 TO 4: FOR J=1 TO 4

6090 LET Q(I,J)=R(I,J)

6100 NEXT J: NEXT I: GO SUB IDR3

6109 REM CALCULATE SETUP TO ACTUAL MATRIX.

6110 LET TX=3: LET TY=1.5: LET TZ=2: GO SUB TRAN3: GO SUB MULT3

6119 REM RECOVER ACTUAL TO OBSERVED MATRIX.

6120 FOR I=1 TO 4: FOR J=1 TO 4 6130 LET A(I,J)=Q(I,J)

6140 NEXT J: NEXT I

6149 REM CALCULATE SETUP TO OBSERVED MATRIX.

6150 GO SUB MULT3

6159 REM PLACE SECOND CUBE AND DRAW HIDDEN LINE VIEW OF SCENE.

6160 GO SUB CUBE 6170 GO SUB HIDDEN 6180 RETURN

6500 REM CUBE/VERTICES AND FACETS (STORED)

6501 REM IN - PPD,NOV,VOF,R(4,4),(NOV),Y(NOV),Z(NOV),V(NOV),W(NOV),H(NOF), F(4,NOF)

6502 REM OUT - NOV,NOF,X(NOV),Y(NOV),Z(NOV),V(NOV),W(NOV),H(NOF),F(4,NOF) 6510 DATA 1,1,1,1,1,-1,1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,-1,-1,1 6520 DATA 1,2,3,4,5,8,7,6,1,5,6,2,2,6,7,3,3,7,8,4,4,8,5,1

6530 RESTORE CUBE

6539 REM EXTEND DATA BASE OF VERTICES IN OBSERVED POSITION.

6540 LET NV=NOV 6550 FOR I=1 TO 8

6560 READ XX,YY,ZZ: LET NOV=NOV+1

6570 LET X(NOV)=XX*R(1,1)+YY*R(1,2)+ZZ*R(1,3)+R(1,4) 6580 LET Y(NOV)=XX*R(2,1)+YY*R(2,2)+ZZ*R(2,3)+R(2,4) 6590 LET Z(NOV)=XX*R(3,1)+YY*R(3,2)+ZZ*R(3,3)+R(3,4)

6599 REM PERSPECTIVE TRANSFORM.

6600 LET V(NOV)=PPD*X(NOV)/Z(NOV) 6610 LET W(NOV)=PPD*Y(NOV)/Z(NOV) 6620 NEXT I

6629 REM READ A*ND EXTEND DATA BASE OF FACETS.

6630 FOR I=1 TO 6

6640 READ F1,F2,F3,F4: LET NOF=NOF+1 6650 LET H(NOF)=4

6660 LET F(1,NOF)=F1+NV: LET F(2,NOF)=F2+NV 6670 LET F(3,NOF)=F3+NV: LET F(4,NOF)=F4+NV 6680 NEXT I 6690 RETURN LISTING 12.3

6500 REM ICOSA/HEDRON

6501 REM IN AND OUT-SAME AS CUBE ABOVE.

6510 DATA 0,1,T,T,0,1,1,T,0,0,-1,T,T,0,-1,-1,T,0,0,1,-T,-T,0,1,1,-T,0,0,-1,-T, -T,0,-1,-1,-T,0

6520 DATA 1,3,2,1,2,4,1,4,8,1,8,6,1,6,3,2,3,5,2,9,4,4,12,8,8,11,6,3,6,7,2,5,9, 4,9,12,8,12,11,6,11,7,3,7,5,5,10,9,

6530 RESTORE ICOSA: LET T=(1+SQR 5)/2

6539 REM EXTEND DATA BASE OF VERTICES IN OBSERVED POSITION.

6540 LET NV=NOV 6550 FOR I=1 TO 12

6560 READ XX,YY,ZZ: LET NOV=NOV+1

6570 LET X(NOV)=XX*R(1,1)+YY*R(1,2)+ZZ*R(1,3)+R(1,4) 6580 LET Y(NOV)=XX*R(2,1)+YY*R(2,2)+ZZ*R(2,3)+R(2,4) 6590 LET Z(NOV)=XX*R(3,1)+YY*R(3,2)+ZZ*R(3,3)+R(3,4)

6599 REM PERSPECTIVE TRANSFORM.

6600 LET V(NOV)=X(NOV)*PPD/Z(NOV) 6610 LET W(NOV)=Y(NOV)*PPD/Z(NOV) 6620 NEXT I

6629 REM READ AND EXTEND DATA BASE OF FACETS.

6630 FOR I=1 TO 20

6640 READ F1,F2,F3: LET NOF=NOF+1 6650 LET H(NOF)=3

6660 LET F(1,NOF)=F1+NV: LET F(2,NOF)=F2+NV: LET F(3,NOF)=F3+NV 6670 NEXT I

6680 RETURN LISTING 12.4

6700 REM CUBOCT/AHEDRON

6701 REM IN AND OUT - SAME AS CUBE ABOVE.

6710 DATA 0,1,1,1,0,1,1,1,0,0,-1,1,1,0,-1,-1,1,0,0,1,-1,-1,0,1,1,-1,0,0,-1,-1,-1,0,-1,-1,-1,0

6720 DATA 1,2,4,8,1,6,7,3,2,3,5,9,4,9,10,12,5,7,11,10,6,8,12,11

6730 DATA 1,3,2,1,8,6,2,9,4,3,7,5,4,12,8,5,10,9,6,11,7,10,11,12

6740 RESTORE CUBOST

6750 LET NV=NOV

6760 FOR I=1 TO 12

6770 READ XX,YY,ZZ: LET NOV=NOV+1

6780 LET X(NOV)=XX*R(1,1)+YY*R(1,2)+ZZ*R(1,3)+R(1,4)

6790 LET Y(NOV)=XX*R(2,1)+YY*R(2,2)+ZZ*R(2,3)+R(2,4)

6800 LET Z(NOV)=XX*R(3,1)+YY*R(3,2)+ZZ*R(3,3)+R(3,4)

6810 LET V(NOV)=X(NOV)*PPD/Z(NOV)

6820 LET W(NOV)=Y(NOV)*PPD/Z(NOV)

6830 NEXT I

6840 FOR I=1 TO 6

6850 READ F1,F2,F3,F4: LET NOF=NOF+1 6860 LET H(NOF)=4

6870 LET F(1,NOF)=F1+NV: LET F(2,NOF)=F2+NV: LET F(3,NOF)=F3+NV: LET F(4,NOF)=F4+NV

6880 NEXT I 6890 FOR I=1 TO 8

6900 READ F1,F2,F3: LET NOF=NOF+1 6910 LET H(NOF)=3

6920 LET F(1,NOF)=F1+NV: LET F(2,NOF)=F2+NV: LET F(3,NOF)=F3+NV 6930 NEXT I 6940 RETURN Упражнение 12.1

Постройте композицию, состоящую из кубов, тетраэдров, пирамид, октаэдров, икосаэдров, кубических октаэдров. Для того, чтобы облегчить вашу задачу, на листингах 12.3 и 12.4 приведены конструирующие программы для кубооктаэдра и икосаэдра. Напишите конструирующую программу для октаэдра, и, пожалуй, ещё более сложную программу для ромбического додекаэдра. LISTING 12.5

6000 REM SCENES/TWO STARS HIDDEN LINES REMOVED 6010 DIM X(22): DIM Y(22): DIM Z(22) 6020 DIM V(22): DIM W(22): DIM H(36): DIM F(3,36) 6030 DIM A(4,4): DIM В(4,4): DIM R(4,4): DIM Q(4,4) 6040 LET STAR1=6500: LET STAR2=6700: LET HIDDEN=7000 6050 LET PPD=3*VERT: LET NOV=0: LET NOF=0

6059 REM PLACE FIRST STAR.

6060 GO SUB IDR3: GO SUB LOOK3 6070 LET A=6: GO SUB STAR1 6080 FOR I=1 TO 4: FOR J=1 TO 4 6090 LET Q(I,J)=R(I,J)

6100 NEXT J: NEXT I: GO SUB IDR3

6109 REM PLACE SECOND STAR.

6110 LET TX=5: LET TY=5: LET TZ=5: GO SUB TRAN3: GO SUB MULT3 6120 FOR I=1 TO 4: FOR J=1 TO 4

6130 LET A(I,J)=Q(I,J)

6140 NEXT J: NEXT I

6150 GO SUB MULT3

6160 LET A=4: GO SUB STAR2

6170 GO SUB HIDDEN

6180 RETURN

LISTING 12.6

6500 REM STAR1

6501 REM IN AND OUT - SAME AS CUBE ABOVE.

6509 REM STAR BASED ON A CUBE.

6510 DATA 1,1,1,1,1,-1,1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,-1,-1,1,A,0,0,-A,0,0,0,A,0,0,-A,0,0,0,A,0,0,-A

6520 DATA

1,2,9,2,3,9,3,4,9,4,1,9,6,5,10,5,8,10,8,7,10,7,6,10,2,1,11,1,5,11,5,6,11,6,2,11,4,3,1 2,3,7,12,7,8,12,8,4,12,1,4,13,4,8,13,8,5,13,5,1,13,3,2,14,2,6,14,6,7,14,7,3,14

6530	RESTORE STAR1
6540	LET NV=NOV
6550	FOR I=1 TO 14
6560	READ XX,YY,ZZ: LET NOV=NOV+1
6570	LET X(NOV)=XX*R(1,1)+YY*R(1,2)+ZZ*R(1,3)+R(1	,4)
6580	LET Y(NOV)=XX*R(2,1)+YY*R(2,2)+ZZ*R(2,3)+R(2	,4)
6590	LET Z(NOV)=XX*R(3,1)+YY*R(3,2)+ZZ*R(3,3)+R(3	,4)
6600	LET V(NOV)=PPD*X(NOV)/Z(NOV)
6610	LET W(NOV)=PPD*Y(NOV)/Z(NOV)
6620	NEXT I
6630	FOR I=1 TO 24
6640	READ F1,F2,F3: LET NOF=NOF+1
6650	LET H(NOF)=3
6660	LET F(1,NOF)=F1+NV: LET F(2,NOF)=F2+NV: LET	F(3,NOF)=	F3+NV
6670	NEXT I
6680	RETURN
LISTING 12.7
6700	REM STAR2
6701	REM IN AND OUT - SAME AS CUBE ABOVE.
6709	REM STAR BASED ON A TETRAHDRON.
6710	DATA 1,1,1,1,-1,-1,-1,1,-1,-1,-1,1,-A,-A,-A,	-A,A,A,A,	A,A,A,A, A
6720	DATA 2,1,8,3,2,8,1,3,8,1,2,7,4,1,7,2,4,7,2,3	,5,4,2,5,	3,4,5,3,1,6,4,3,6,1,
6730	RESTORE STAR2
6740	LET NV=NOV
6750	FOR I=1 TO 8
6760	READ XX,YY,ZZ: LET NOV=NOV+1
6770	LET X(NOV)=XX*R(1,1)+YY*R(1,2)+ZZ*R(1,3)+R(1	,4)
6780	LET Y(NOV)=XX*R(2,1)+YY*R(2,2)+ZZ*R(2,3)+R(2	,4)
6790	LET Z(NOV)=XX*R(3,1)+YY*R(3,2)+ZZ*R(3,3)+R(3	,4)
6800	LET V(NOV)=PPD*X(NOV)/Z(NOV)
6810	LET W(NOV)=PPD*Y(NOV)/Z(NOV)
6820	NEXT I
6830	FOR I=1 TO 12
6840	READ F1,F2,F3: LET NOF=NOF+1
6850	LET H(NOF)=3
6860	LET F(1,NOF)=F1+NV: LET F(2,NOF)=F2+NV: LET	F(3,NOF)=	F3+NV
6870	NEXT I
6880	RETURN
Пример 12.2

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

На листинге 12.5 приведена программа "SCENE3", а на листингах 12.6 и 12.7 приведены программы, генерирующие два звездообразных трёхмерных объекта (при генерации каждого из которых следует задать параметр A, определяющий длину лучей). Обе эти программы при построении используют формы куба и октаэдра. Изображение двух звёзд (кстати, очень эффектное) может быть получено, если задать следующие значения параметров: HORIZ=48, VERT=32, точка, в которой расположен глаз - (35,20,25), а взгляд направлен в точку (0,0,0).

Упражнение 12.2

Программа на листинге 10.1 проверяет, что порядок обхода вершин треугольной грани - против часовой стрелки. Эта программа была написана для выпуклых тел, содержащих начало координат. Переделайте программу с учётом общего случая. Это означает, что задаются две точки, лежащие по разные стороны от плоскости, содержащей одну из граней объекта. В одной из этих точек находится глаз наблюдателя, а другая точка, не обязательно являющаяся началом координат, - внутренняя точка тела. Используйте эту программу для проверки объектов программы 12.6 и 12.7.

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

Упражнение 12.3

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

I-ое ребро, 1<=I<=NOL. После того измените алгоритм удаления невидимых линий так, чтобы в нём не рассматривались прямые, являющиеся пересечением двух невидимых граней, и не сравнивалась грань с прямыми, лежащими на этой грани.

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

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

В следующей главе мы рассмотрим более сложные методы символьной графики и введём один метод мультипликации трёхмерной графики.

Список программ

1. "LIB 1", "LIB3", листинг 12.1 ("HIDDEN") и 12.2 ("SCENES" и "CUBE"). Входные данные: HORIZ, VERT, (EX,EY,EZ), (XD,DY,DZ). Введите, например, следующие значения:

а) 9,6, (15,10,5), (0,0,0);

б) 9,6, (10,10,-10), (0,1,0).

2. "LIB 1", "LIB3", листинги 12.1 ("HIDDEN") и 12.2 ("SCENES"), загрузите в память программы 12.3 ("ICOSA") и 12.4 ("CUBOCT") и измените подпрограмму "SCENE3" следующим образом:

6010 DIM X(24): DIM Y(24): DIM 7(24)

6020 DIM V(24): DIM W(24): DIM P(34): DIM H(34)

6040 LET CUBOCT=6700: LET ICOSA=6500: LET HIDDEN=7000

6070 GO SUB ICOSA

6160 GO SUB CUBOCT

Входные данные: HORIZ, VERT, (EX,EY,EZ), (DX,DY,DZ). Введите, например,

а) 9, 6, (15,10,5), (0,0,0);

б) 9, 6, (-10,10,10), (0,1,0).

3. "LIBr, "LIB3", листинг 12.1 ("HIDDEN"), 12.5 ("TWOSTARS"), и 12.6 ("STAR1"), и 12.7 ("STAR2"). Входные данные: HORIZ, VERT, (EX,EY,EZ), (DX,DY,DZ). Попробуйте ввести, например,

а) 60, 40, (10,20,30), (0,0,0);

б) 90, 60, (-10-,20,-10), (0,1,0).

1. Предисловие - данная книга является введением в предмет компьютерной графики, может рассматриваться как дешевый пакет программ.
2. Введение - Эту книгу можно можно рассматривать как книгу рецептов графических программ, позволяющих рисовать сложные картинки с помощью SPECTRUMa.
3. Графические команды ZX SPECTRUM - Команды PAPER и INK; Дисплейный файл; Команда BORDER; Символьные блоки; Команды PLOT и DRAW; Команды PRINT и LIST; Команды INVERSE и OVER; Команды FLASH и BRIGHT; Атрибуты; Простейшее движущееся изображение; Команды CIRCLE и DRAW; Цвета в символьном блоке; Простая игра.
4. От реальных координат к пикселям - Примитивы, обеспечивающие карту пространства на графическом экране; Список программ;
5. Геометрия декартовой плоскости - Кадрирование; Задание кривых с помощью функциональной зависимости; Список программ.
6. Матричное представление преобразований двумерного пространства - Композиция преобразований; Перенос; Растяжение; Вращение относительно начала координат; Обратное преобразование; Размещение объекта; Рассматривание объекта; Вычерчивание объекта; Сложные изображения - метод построения изображения "по кирпичикам"; Эффективное использование матриц; Хранение информации об изображении; Список программ.
7. Символьная графика ZX SPECTRUM - Стандартный набор символов; Графический режим работы; Блочная графика; Графика, определяемая пользователем; Альтернативные множества символов; Список программ.
8. Диаграммы и графики - Курсоры; Атрибуты; Точки и линии; Запись и загрузка; Надписи; Данные для графиков; Специальные символы; Определенные пользователем символы для использования в гистограммах; Гистограммы; Круговые диаграммы; Штриховка секторов; Графики; Список программ.
9. Трёхмерная декартова геометрия - Определение прямой; Угол между двумя направляющими векторами; Определение плоскости70 Точка пересечения прямой и плоскости; Расстояние от точки до прямой; Точка пересечения двух прямых; Плоскость, проходящая через три неколлинеарные точки; Точка пересечения трёх плоскостей; Линия пересечения двух плоскостей; Функциональное представление поверхности; Лежит ли точка по ту же сторону от плоскости, что и начало координат?; Каково направление обхода двумерного многоугольника, заданного последовательностью своих вершин?
10. Матричное представление преобразования трехмерного пространства - Параллельный перенос; Растяжение; Вращение относительно координатной оси; Вращение на угол ТЕТА относительно оси X; Обратное преобразование; Поворот на угол NU относительно произвольной оси.
11. Ортогональные проекции - Исходное положение; Фактическое положение; Наблюдаемое положение; Ортогональная проекция; Вычисление матрицы Q, переводящей объект из фактического положения в наблюдаемое; Как задавать объект; Конструирующие подпрограммы и метод построения блоков; Тела вращения.
12. Простые алгоритмы удаления невидимых линий и поверхностей - Ориентация треугольника в трехмерном пространстве; Алгоритм удаления скрытых поверхностей для случая тела, ограниченного замкнутой и выпуклой поверхностью; Тела вращения; Вычерчивание поверхности специального вида, лежащей в трехмерном пространстве.
13. Перспективная проекция - Что такое перспективное видение? Построение перспективной проекции точки; Свойства перспективной проекции; Выбор визуальной плоскости; Кадрирование изображения; Список программ.
14. Общий алгоритм удаления невидимых линий - алгоритм для перспективного отображения трехмерного обьекта, хранящегося в памяти.
15. Белее сложные элементы программирования - Управление выполнением программ; Структура дисплейного файла; Быстрое преобразование содержимого экрана; Мультипликация; Свертка; Структура программ на бейсике (перенумерация и уничтожение); Структура программы на бейсике (эффективные программы); Синхронное изображение.
16. Действующий пример видеоигры - Описание игры; Передний план; Фон; Каскадная мультипликация; Другие методы мультипликации.
17. Проекты - ПРИЛОЖЕНИЕ А.

  Оставте Ваш отзыв:

  НИК/ИМЯ

  ПОЧТА (шифруется)

  КОД