##
Bilgisayar grafikleri için optimum veri yapıları

Bilgisayar grafikleri için optimum veri yapıları

##### Dosyalar

##### Tarih

1990

##### Yazarlar

Savaş, Gülay

##### Süreli Yayın başlığı

##### Süreli Yayın ISSN

##### Cilt Başlığı

##### Yayınevi

Fen Bilimleri Enstitüsü

##### Özet

Tez konusunu oluşturan "Bilgisayar grafikleri için optimal veri yapıları" çalışması 7 ana bölümden oluşmuştur. Birinci bölümde, bilgisayar grafiklerinin amaçları ve kullanım yerleri üzerinde kısaca durulmuştur. İkinci bölümde, ekrandaki görüntünün oluşumu ile il gili birtakım temel bilgiler, modlar, renk kullanımı, gö rüntü belleği iç yapısı, ekran görüntüsünün kontrolü gibi grafik konusunda çalışmaya başlamadan evvel bilinmesi gere ken birtakım temel kavramlar üzerinde durulmuş, kullanıcı lara ve programcılara bu konuya başlamadan evvel genel bir grafik mantığı verilmesine çalışılmıştır. üçüncü bölümde VGA Adaptörü tanıtılmıştır. Dördüncü bölümde, bilgisayar grafiklerinin oluşumun da temel teşkil eden elemanlar nokta ve doğrular üzerinde durulmuş ve bunlar yardımıyla oluşturulan iki boyutlu eğri ler ve düzlemler anlatılmıştır. Beşinci bölümde, üç boyutlu dönüşümler ve izdüşüm lerden bahsedilirken bir yandan da bunlarla ilgili temel ma tematiksel denklemler ve konuyu aydınlatan şekiller veril miştir. Altıncı bölümde, eğri yüzeylerden birçoğu tanıtılmış bunların parametrik gösterimleri verilmiştir. Yedinci bölümde, uzay eğrilerine ve bunlardan özel likle üçüncü dereceden uzay eğrileri üzerinde durulmuş ve bunlarla ilgili temel denklemler verilmiştir. Yukarıdaki bölümlerde bütün bu konularla ilgili ve rilen denklemler, bilgisayar grafiklerinin mantığını oluş turmada kullanılan esas denklemlerdir ve programlamada bü yük kolaylık sağlarlar. Bütün bunların programını oluştururken yapılması ge reken en önemli husus ise uygun bir veri yapısı oluşturmak tır. Bunun için ise matrislerden ve kayıtlardan yararlanıl maktadır.

Since computer graphics is a relatively new teehology, it is necessary to clarify the current terminology. A number of terms and definitions are used rather loosely in this field. In particular, computer aided design (CAD), interactive graphics (IS), computer graphics (CG), and computer aided manufacturing (CAM), are frequently used interchangeably or in such a manner that considerable confusion exist as to the precise meaning. Of these terms CAD the most general. CAD may be defined as any use of the computer to aid in the design of an individual part, a subsystem, or a total system. The use does not have to involve graphics. The design process may be at the system concept level or at the detail part design level. It may also involve an interface with CAM. Computer graphics is the use of a computer to define, store, manipulate, interrogate, and present pictorial output, This is essentialy a passive operation. The computer prepares and presents stored information to an observer in the form of pictures. The observer has no direct control over the picture being presented. Interactive graphics also uses the computer to prepare and present pictorial material. However, in interactive graphics the observer can influence the picture as it is being presented; i.e., the observer interacts with the picture in real time. To see the importance of real time restriction, consider the problem of rotating a complex threejiimensional picture composed of 1000 lines at a reasonable rotation rate, say, 15 /second. As we shall see subsequently, the 1000 lines of the picture are most conveniently represented by a 1000 x 4 matrix of homogeneous coordinates of the end points of the lines, and the rota tion is most conveniently accomplished by multiplying this 1000 x 4 matrix by a 4 x 4 transformation matrix. Accomplishing the required matrix multiplication requires 16000 multiplications, 12000 additions, and 1000 divisions. If this matrix multiplication is accomplished in software, the time is significant. To see this, consider that a ¦typical minicomputer using a hardware floating-point processor requires 6 microseconds to multiply two numbers, 4 microseconds to add two numbers, and 8 microseconds to divide two numbers. Thus the matrix multiplication requires 0.15 seconds. Since computer displays that allow dynamic motion require that the picture he redrawn (refreshed) at least 30 times each second in order to avoid flicker, it is obvius that the picture ©annot change smoothly. Even if it is assumed that the picture is recalculated (update) only 15 times each second, i.e., every degree, it is still not possible to accomplish a smooth rotation in software. Thus this now no longer interactive graphics. So regain the ahility to interactively present the picture several things can be done. Clever programming can reduce the time to accomplish the required matrix multiplication. However, a point will he reached where thi is no longer possible. The complexity of the picture can he reduced. In this case, the resulting picture may not be acceptable, finally, the matrix multiplication can be accomplished by using a special-purpose digital hardware matrix multiplier. Biis is the most promising approach. It can easily handle the problem outlined above. The necessary considerations for development of a software system for the fundamental drawing, devici-control and data-handlig aspects of computer graphics is given below. Computer Graphics Software: In developing the concepts for a computer graphics software system it is convenient to divide the overall system into several parts. Two of the obvius parts are the support computer and the graphics device itself. These are both hardware. In considering these descriptions a not too narrow view should be taken. In general, the support computer is the system on which the data base exists and on which software manipulation of the data base occurs. However, in some systems this function may be physically split between two or more computer systems. The graphics device is the hardware which actually produces the picture. A conceptual view of a computer graphics software system is shown in Fig.l. Two software systems produce an interface between the support computer and the graphics device. The first is the data base manipulation software. The mathematical basis for this system is very important. The second is a software system which provides an interface between the normal "drawing functions" and the - VIII - um mum. Slf PORT (OTWER DUA B& miiUATKK sdftwc arrarcmuiER (EVİSEB KIA MSE snwt/ıır«ıwt - IMISfAd SURWH1 9JWR1 OMWU! GIWIICS ttvıcıs piçtik Figüre 1. Conceptual view of a computer graphics software system hardware associated with a particular graphics derice. It is this system which causes the necessary codes (infor mation in terms of binary bits) to be sent to the graphics device to cause that device to draw lines, plot points, etc. Computer Graphics Primitives: As pointed out above, when designing or building a computer graphics system it is convenient to define those areas where the support computer must interact with the graphics device. All graphics devices, receive information from the support computer as a data stream composed of binary bits. In particular cases one or more bits may be significiant. However, except for very sophisticated users, the composition of thi data stream is seldom of interest. It is more convenient to think of the fundemental effects that the data stream has on the graphics device. These fundamental effects are called graphics primitives. They generally fall into three areas: cursor control, device state or mode control, and graphic input. Here cursor is used in a general sense to mean the electron beam on a CRT graphics device, the print head on a teletype, high-speed printer, electrostatic dot matrix printer, or the pen on a pen and ink plotter, etc. - ix - Overview Of Computer Graphics: Computer graphics as defined above can be a very complex and diverse subject. It encompasses field of study as diverse as electronic and mechanical design list and tree structures for preparing and presenting pictures to an observer using a computer graphics system. Computer graphics can be divided into the following areas : Representing pictures to be presented Preparing pictures for presentation Presenting previously prepared pictures Interacting with the picture Here the word "picture11 is used in its broadest sense to mean any collection of lines, points, text, etc., to be displayed on a graphics device. A picture may be as simple as a single line or curve, or it may be a full scaled and annotated graph or a complex representation of an aircraft, ship, or automobile. Representing Pictures To Be Presented: fundamentally the pictures represented in computer graphics can be considered as a collection of lines, points, and textual material. A line can be represented by the coordinates of its ends points (xl,yl,zl) and (x2,j2tz2)f a point by a single-coordinate triplet (xl,yl,zl), and textual material by collections of lines or points. The representation of textual material is by far the most complex, involving in many ceses curved lines or dot matrices. However, unless the user is concerned with pattern recognition, the design of graphic hardware, or unusual character sets, he or she need not be concerned with these details, since almost all graphics devices have built-in "hardware" or software character generators. The representation of curved lines is usually accomplished by approximating them by short straight-line segment. However, this is sometimes accomplished using hardware curve generators. Preparing Pictures Por Presentation: Pictures ultimately consist of points. The coordinates of these points are generally stored in a file (array) prior to being used to present the picture. This file (array) is called a data base. Yery comlex pictures require very complex data bases which require a comlex program to - x - access them. These complex data bases may involve ring structures, tree structures, etc., and the base itself may contain pointers, substructures, and other nongraphic data. However, many computer graphics applications involve much simpler pictures for -which the user can readily invent simple data base structures which the user can readily invent simple data base structures which can be easily accessed. Points are the basic building blocks of a graphics data base. îhere are three basic methods or instructions for treating a point as a graphic geometric entity: move the beam, pen, cursor, plotting head to the point, draw a line to that point, or draw a dot at that point. Fundamentally there are two ways to specify the position of a point: ab solute or relatively (incremental ; coordinates. In relative or incremental coordinates the position of a point is defined by giving the displaearaent of the point with respect to the previous point.

Since computer graphics is a relatively new teehology, it is necessary to clarify the current terminology. A number of terms and definitions are used rather loosely in this field. In particular, computer aided design (CAD), interactive graphics (IS), computer graphics (CG), and computer aided manufacturing (CAM), are frequently used interchangeably or in such a manner that considerable confusion exist as to the precise meaning. Of these terms CAD the most general. CAD may be defined as any use of the computer to aid in the design of an individual part, a subsystem, or a total system. The use does not have to involve graphics. The design process may be at the system concept level or at the detail part design level. It may also involve an interface with CAM. Computer graphics is the use of a computer to define, store, manipulate, interrogate, and present pictorial output, This is essentialy a passive operation. The computer prepares and presents stored information to an observer in the form of pictures. The observer has no direct control over the picture being presented. Interactive graphics also uses the computer to prepare and present pictorial material. However, in interactive graphics the observer can influence the picture as it is being presented; i.e., the observer interacts with the picture in real time. To see the importance of real time restriction, consider the problem of rotating a complex threejiimensional picture composed of 1000 lines at a reasonable rotation rate, say, 15 /second. As we shall see subsequently, the 1000 lines of the picture are most conveniently represented by a 1000 x 4 matrix of homogeneous coordinates of the end points of the lines, and the rota tion is most conveniently accomplished by multiplying this 1000 x 4 matrix by a 4 x 4 transformation matrix. Accomplishing the required matrix multiplication requires 16000 multiplications, 12000 additions, and 1000 divisions. If this matrix multiplication is accomplished in software, the time is significant. To see this, consider that a ¦typical minicomputer using a hardware floating-point processor requires 6 microseconds to multiply two numbers, 4 microseconds to add two numbers, and 8 microseconds to divide two numbers. Thus the matrix multiplication requires 0.15 seconds. Since computer displays that allow dynamic motion require that the picture he redrawn (refreshed) at least 30 times each second in order to avoid flicker, it is obvius that the picture ©annot change smoothly. Even if it is assumed that the picture is recalculated (update) only 15 times each second, i.e., every degree, it is still not possible to accomplish a smooth rotation in software. Thus this now no longer interactive graphics. So regain the ahility to interactively present the picture several things can be done. Clever programming can reduce the time to accomplish the required matrix multiplication. However, a point will he reached where thi is no longer possible. The complexity of the picture can he reduced. In this case, the resulting picture may not be acceptable, finally, the matrix multiplication can be accomplished by using a special-purpose digital hardware matrix multiplier. Biis is the most promising approach. It can easily handle the problem outlined above. The necessary considerations for development of a software system for the fundamental drawing, devici-control and data-handlig aspects of computer graphics is given below. Computer Graphics Software: In developing the concepts for a computer graphics software system it is convenient to divide the overall system into several parts. Two of the obvius parts are the support computer and the graphics device itself. These are both hardware. In considering these descriptions a not too narrow view should be taken. In general, the support computer is the system on which the data base exists and on which software manipulation of the data base occurs. However, in some systems this function may be physically split between two or more computer systems. The graphics device is the hardware which actually produces the picture. A conceptual view of a computer graphics software system is shown in Fig.l. Two software systems produce an interface between the support computer and the graphics device. The first is the data base manipulation software. The mathematical basis for this system is very important. The second is a software system which provides an interface between the normal "drawing functions" and the - VIII - um mum. Slf PORT (OTWER DUA B& miiUATKK sdftwc arrarcmuiER (EVİSEB KIA MSE snwt/ıır«ıwt - IMISfAd SURWH1 9JWR1 OMWU! GIWIICS ttvıcıs piçtik Figüre 1. Conceptual view of a computer graphics software system hardware associated with a particular graphics derice. It is this system which causes the necessary codes (infor mation in terms of binary bits) to be sent to the graphics device to cause that device to draw lines, plot points, etc. Computer Graphics Primitives: As pointed out above, when designing or building a computer graphics system it is convenient to define those areas where the support computer must interact with the graphics device. All graphics devices, receive information from the support computer as a data stream composed of binary bits. In particular cases one or more bits may be significiant. However, except for very sophisticated users, the composition of thi data stream is seldom of interest. It is more convenient to think of the fundemental effects that the data stream has on the graphics device. These fundamental effects are called graphics primitives. They generally fall into three areas: cursor control, device state or mode control, and graphic input. Here cursor is used in a general sense to mean the electron beam on a CRT graphics device, the print head on a teletype, high-speed printer, electrostatic dot matrix printer, or the pen on a pen and ink plotter, etc. - ix - Overview Of Computer Graphics: Computer graphics as defined above can be a very complex and diverse subject. It encompasses field of study as diverse as electronic and mechanical design list and tree structures for preparing and presenting pictures to an observer using a computer graphics system. Computer graphics can be divided into the following areas : Representing pictures to be presented Preparing pictures for presentation Presenting previously prepared pictures Interacting with the picture Here the word "picture11 is used in its broadest sense to mean any collection of lines, points, text, etc., to be displayed on a graphics device. A picture may be as simple as a single line or curve, or it may be a full scaled and annotated graph or a complex representation of an aircraft, ship, or automobile. Representing Pictures To Be Presented: fundamentally the pictures represented in computer graphics can be considered as a collection of lines, points, and textual material. A line can be represented by the coordinates of its ends points (xl,yl,zl) and (x2,j2tz2)f a point by a single-coordinate triplet (xl,yl,zl), and textual material by collections of lines or points. The representation of textual material is by far the most complex, involving in many ceses curved lines or dot matrices. However, unless the user is concerned with pattern recognition, the design of graphic hardware, or unusual character sets, he or she need not be concerned with these details, since almost all graphics devices have built-in "hardware" or software character generators. The representation of curved lines is usually accomplished by approximating them by short straight-line segment. However, this is sometimes accomplished using hardware curve generators. Preparing Pictures Por Presentation: Pictures ultimately consist of points. The coordinates of these points are generally stored in a file (array) prior to being used to present the picture. This file (array) is called a data base. Yery comlex pictures require very complex data bases which require a comlex program to - x - access them. These complex data bases may involve ring structures, tree structures, etc., and the base itself may contain pointers, substructures, and other nongraphic data. However, many computer graphics applications involve much simpler pictures for -which the user can readily invent simple data base structures which the user can readily invent simple data base structures which can be easily accessed. Points are the basic building blocks of a graphics data base. îhere are three basic methods or instructions for treating a point as a graphic geometric entity: move the beam, pen, cursor, plotting head to the point, draw a line to that point, or draw a dot at that point. Fundamentally there are two ways to specify the position of a point: ab solute or relatively (incremental ; coordinates. In relative or incremental coordinates the position of a point is defined by giving the displaearaent of the point with respect to the previous point.

##### Açıklama

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 1990

##### Anahtar kelimeler

Bilgisayar grafikleri,
Veri yapıları,
Video grafikleri dizisi,
Computer graphics,
Data structures,
Video graphics array