|
UNIT
– 1 |
|||
|
INTRODUCTION TO COMPUTER GRAPHICS |
|||
|
Unit-01/Lecture-01 |
|||
|
It is the creation
and manipulation of graphic images by means of a computer. (rgpv2003,2007)
The interaction and
understanding of computers and interpretation of data has been made easier
because of computer graphics. Computer graphic development has had a
significant impact on many types of media and has
revolutionized animation, movies and the video game industry. “A picture is worth a thousand words.” Computer graphics mean
the creation and manipulation of pictures with aid of a computer. Video games
represent the first major use in the home graphics. ·
Computer
graphics can be classified into two broad categories- (I) non-interactive or passive
computer graphics (II)Interactive computer graphics Non interactive has no
control over the image. Such picture may be generated on paper or film using
a computer controlled plotter; familiar examples of this form of computer
graphics includes the titles shown on TV and other forms of computer art. Interactive computer
graphics means two-way communication between computer and user. We can give
the observer some control over the image by providing him with an input
device, such as the lever of ping pong game so that he can signal his request
to the computer. In it the picture is changing instantaneously in response to
user commands. Example of this form
includes flight simulation used for training of pilots. ·
Modern
graphics display consists of three components-
I.
Digital memory or frame buffer- Used to store the displayed image
a matrix of intensity values.
II.
Monitor- A home TV set without the tuning
and receiving electronics.
III.
Simple interface- it is the display controller that
passes the contents of frame buffer to the monitor. The image must be passed
repeatedly to the monitor 30 or more times a second, in order to maintain a
steady picture on the screen. ·
Cathode
Ray Tube (rgpv2003,2007) The primary output device in a graphics system is a video
monitor. The operation of most video monitors is based on the standard
cathode ray tube (CRT) design.
A CRT is an evacuated glass tube. An electron gun at the rear of the tube
produces a beam of electrons which is directed towards the front of the tube
(screen). The inner side of the screen is
coated with phosphor substance which gives off light when it is stroked by
electrons. It is possible to control the point at which the electron beam
strikes the screen, and therefore the position of the dot upon the screen, by
deflecting the electron beam. The beam is positioned
on the screen by a deflection system of
the cathode-ray-tube consists of two pairs of parallel plates, referred to as
the vertical and horizontal deflection plates.
The intensity of the beam is controlled by
the intensity signal on the control grid. A beam of electrons
(cathode rays), emitted by an electron gun, passes through focusing and
deflection systems that direct the beam towards specified position on the
phosphor-coated screen. The phosphor then emits a small spot of light at each
position contacted by the electron beam. Because the light emitted by the
phosphor fades very rapidly, some method is needed for maintaining the screen
picture. One way to keep the phosphor glowing is to redraw the picture
repeatedly by quickly directing the electron beam back over the same points.
This type of display is called a refresh CRT. The primary components of an electron gun in a CRT are the
heated metal cathode and a control grid (Fig. 3). Heat is supplied to the
cathode by directing a current through a coil of wire, called the filament,
inside the cylindrical cathode structure. This causes electrons to be “boiled
off” the hot cathode surface. In the vacuum inside the CRT envelope,
negatively charged electrons are then accelerated toward the phosphor coating
by a high positive voltage. The accelerating voltage can be generated with a
positively charged metal coating on the in side of the CRT envelope near the
phosphor screen, or an accelerating anode can be used, a in fig below .
Sometimes the electron gun is built to contain the accelerating anode and
focusing system within the same unit. Spots of light are produced on the screen by the transfer of the
CRT beam energy to the phosphor. When the electrons in the beam collide with
the phosphor coating, they are stopped and there are stopped and their
kinetic energy is absorbed by the phosphor. Part of the beam energy s
converted by friction into heat energy, and the remainder causes electron in
the phosphor atoms to move up to higher quantum-energy levels. After a short
time, the “excited” phosphor electrons begin dropping back to their stable
ground state, giving up their extra energy as small quantum of light energy.
What we see on the screen is the combined effect of all the electrons light
emissions: a glowing spot that quickly fades after all the excited phosphor
electrons have returned to their ground energy level. The frequency (or
color) of the light emitted by the phosphor is proportional to the energy
difference between the excited quantum state and the ground state. Different kinds of phosphor are available for use in a CRT.
Besides color, a major difference between phosphors is their persistence: how
long they continue to emit light (that is, have excited electrons returning to the ground state) after the
CRT beam is removed. Persistence is defined as the time it takes the emitted
light from the screen to decay to one-tenth of its original intensity.
Lower-persistence phosphors require higher refresh rates to maintain a
picture on the screen without flicker. A phosphor with low persistence is
useful for animation; a high-persistence phosphor is useful for displaying
highly complex, static pictures. Although some phosphor have a persistence
greater than 1 second, graphics monitor are usually constructed with a
persistence in the range from 10 to 60 microseconds Figure 3 CRT screen
The
voltage applied to vertical plates controls the vertical deflection of the
electron beam and voltage applied to the horizontal deflection plates controls
the horizontal deflection of the electron beam. There are two techniques used
for producing images on the CRT screen: Vector scan / random scan and Raster
scan. When the phosphor is hit by the electron beam it absorbs
energy and jumps to a higher quantum-energy level. As it returns to its
normal level it emits visible light i.e. it phosphoresces. In the
phosphors used in graphics devices the persistence of the
phosphorescence is typically 10-60 microseconds. Before the human visual system can see a transient image it must
be continually redrawn (refreshed) at a rate higher than the critical fusion
frequency of the human visual system. To allow the human visual system to see
a continuously refreshed image without flicker the refresh rate has to be at
least 60 c/s.
·
Types of Monitors: (rgpv2005,2007,2009) 1. LCD 2. Plasma 3. LED LCD Monitors
Liquid crystal display
monitors are not the latest but the later version than CRT monitors. Unlike
CRT monitors, these monitors are compact and slim. These monitors do consume
low and almost have no dependency on backlight technology. Due to its quality
of consuming low power and compact in shape and size, it has been well
adapted in the time when energy efficiency is the main concern. In spite of all these
technological modest characteristics, these monitors have limited viewing
angles, colors, and contrasts. Issues like bleeding and distorting brightness
from edges and some more related issues have been reported in some models. Plasma Monitors
Plasma screen and/or
plasma monitors are considered as high contrast screen with bright, vibrant
colors and brightness that claims to make your visual experience worthwhile. It works on plasma
discharge on almost ideally flat panel of glass. The discharge is composed of
xenon and neon without any use of mercury in it. Plasma monitors are
in, mainly because of their excellent and remarkable viewing angles, color
saturation, and contrasts. In comparison with LCD,
Plasma monitors have less blocky-looking picture. However, Plasmas are heavy
in weight and available in larger dimensions only. These kinds of monitors
do easily suffer image burn-in. Unlike other monitors like CRT, Plasma
monitors do not allow use of optical objects like lights pens and light guns. SED
Monitors SED is abbreviated form
of Surface-conducted electron-emitted display. These are high resolution and
flat penal display screens. Some of these display units are even more than 40
inches in diagonal measurements. These display units are
composed from an electron-emitting array and layer of phosphorus. Array and
layer of phosphorus are separated by thin sheet that allows air to pass. SED
consumes less energy in comparison with CRT and it gives higher resolution
picture. LED Monitors
Another type of monitor is organic light-emitting diode monitors.
This term is abbreviated as OLED monitors. This is in actual a thin film
of light-emitting diode, which we all knows as LEDs. |
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
Describe the working of raster
refresh display tube. How different gray levels are incorporated in it? |
Dec 2003 |
10 |
|
Q.2 |
Explain the working of cathode
ray-tube? |
June 2003, Dec 2007 |
10 |
|
Q.3 |
Write short note on RGB monitors. |
Dec 2003, June 2004 |
10 |
|
Q.4 |
Discuss application of Computer
Graphics |
Dec 2015 |
02 |
|
Q.5 |
Explain the design issues in color
CRT moniotor |
Dec 2015 |
07 |
|
UNIT
– 1 |
|||
|
Raster-scan system |
|||
|
Unit-01/Lecture-02 |
|||
|
Raster-scan technique (rgpv2005,2007,2009) In a raster- scan system, the electron beam is swept across the screen, one row at a time from top to bottom. As the electron beam moves across each row, the beam intensity is turned on and off to create a pattern of illuminated spots. Picture definition is stored in memory area called the refresh buffer or frame buffer. This memory area holds the set of intensity values for all the screen points. Stored intensity values are then retrieved from the refresh buffer and “painted” on the screen one row (scan line) at a time (Fig. 4). Each screen point is referred to as a pixel or pel (shortened forms of picture element). Refreshing on raster-scan displays is carried out at the rate of 60 to 80 frames per second, although some systems are designed for higher refresh rates. Sometimes, refresh rates are described in units of cycles per second, or Hertz (Hz), where a cycle corresponds to one frame. At the end of each scan line, the electron beam returns to the left side of the screen to begin displaying the next scan line. The return to the left of the screen, after refreshing each scan line, is called the horizontal retrace of the electron beam. And at the end of each frame (displayed in 1/80th to 1/60th of a second), the electron beam returns (vertical retrace) to the top left corner of the screen to begin the next frame. On some raster-scan systems (and in TV sets), each frame is displayed in two passes using an interlaced refresh procedure. In the first pass, the beam sweeps across every other scan line from top to bottom. Then after the vertical retrace, the beam sweeps out the remaining scan lines (fig.below). Interlacing of the scan lines in this way allows us to see the entire screen displayed in one-half the time it would have taken to sweep across all the lines at once from top to bottom.
Figure 4 Raster Scan Technique Raster-scan
system
(rgpv2005,2007,2009) In addition to the central processing unit a special purpose
processor called the video controller or display controller is used to
control the operation of the display device
Architecture of Simple Raster graphics system
To speed up pixel processing video controllers can retrieve multiple
pixel values from the refresh buffer on each pass. The multiple pixel
intensities are then stored in a separate register and used to control the
CRT beam intensity for a group of adjacent pixels. When this group of the
pixel has been processed the next block of pixel values is retrieved from the
frame buffer.
Architecture
of Raster graphics system with a display processor Raster
Scan display processor Rectangular
Grid of Pixel Positions |
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
Differentiate between raster –scan and random scan system. |
Rgpv 2005,2007,2009 |
10 |
|
Q.2 |
Describe
the working of raster refresh display tube. How different gray levels are
incorporated in it? |
Dec 2003 |
10 |
|
Q3 |
Explain the raster scan graphics. How do we generate a raster image?
Also discuss the application areas of raster graphics. |
June
2009 |
10 |
|
Q4 |
Difference between Raster Scan and Random Scan Systems ? |
Dec
2015 Dec
2014 |
03 |
|
UNIT
– 1 |
|||
|
Random
Scan System |
|||
|
Unit-01/Lecture-03 |
|||
|
Random-scan technique (Rgpv 2005, 2006,2007,2009) Random scan monitors draw a picture one line at a time and for this reason are also referred to as vector displays (or stroke-writing or calligraphic displays). The component lines of a picture can be drawn (Figure 5) and refreshed by a random-scan system in any specified order. Refresh
rate on a random-scan system depends on the number of lines to be displayed.
Picture definition is now stored as a set of line-drawing commands in an area
of memory referred to as the refresh display file. Sometimes the refresh
display file is called the display list, display program, or
simply the refresh buffer. To display a specified picture, the system
cycles through the set of commands in the display file, drawing each
component line in turn.
After all line- drawing commands have been processed, the system cycles back
to the first line command in the list. Random-scan displays are designed to
draw al the component lines of a picture 30 to 60times each second.
Figure 5 Random Scan Techniques Random Scan System
Architecture
of a Simple Random Scan System Application programs are stored in system
memory. Graphics commands in the program are translated by the graphics
package into a display file stored in the system memory. This display file is
accessed by the display processor to refresh the screen. Display processor in
a random scan system is referred to as a display processing unit or graphics
controller. Random
scan monitors draw a picture one line at a time and for this reason are also
referred to as vector displays
(or stroke-writing or calligraphic displays).The component lines of a picture
can be drawn and refreshed by a random-scan system in any specified order. Refresh
rate on a random-scan system depends on the number of lines to be displayed.
Picture definition is now stored as a set of line-drawing commands in an area
of memory referred to as the refresh display file. Sometimes the refresh
display file is called the display list,
display program, or simply the refresh
buffer. To display a specified picture, the system cycles
through the set of commands in the display file, drawing each component line
in turn. After all line- drawing commands have been processed, the system
cycles back to the first line command in the list. Random-scan displays are
designed to draw al the component lines of a picture 30 to 60times each
second. Shadow-mask (Rgpv
2005,2009 ) Shadow-mask methods are commonly used in
raster-scan systems (including color TV) because they produce a much wider range
of color than the beam penetration method. A shadow-mask CRT has three
phosphor color dots at each pixel position. One phosphor dot emits a red
light, another emits a green light, and the third emits a blue light. This
type of CRT has three electron guns, one for each color dot, and a shadow-
mask grid just behind the phosphor –coated screen. Figure 6 below illustrates
the delta-delta shadow-mask method, commonly used in color CRT systems. The
three electron beam are deflected and focused as a group onto the shadow
mask, which contains a series of holes aligned with the phosphor-dot
patterns. When the three beams pass through a hole in the shadow mask, they
activate a dot triangle, which appears as a small color spot the screen the
phosphor dots in the triangles are arranged so that each electron beam can
activate only its corresponding color dot when it passes through the shadow
mask.
Figure 6 Shadow Mask Techniques |
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
Explain the working of random-scan displays. |
June
2006 |
10 |
|
Q.2 |
What is the role of shadow mask
used in graphics monitors? What do u mean by VGA and SVGA monitors? |
June 2005,2009 |
10 |
|
Q.3 |
What is the purpose of display processor in computer system?Give the
architecture of a raster system with display processor. |
June
2009 |
10 |
|
UNIT
– 1 |
|||
|
Pixel / Display
Processor / Frame Buffer/ Direct Color Frame buffer |
|||
|
Unit-01/Lecture-04 |
|||
|
Pixel (picture element)
Display Processor Purpose: frees
the CPU from the graphics routine task. Major task:
digitizes a picture definition given in an application program into a set of
pixel values for storage in the frame buffer. This digitization process is
called scan conversion. Straight lines and other
geometric objects are scan converted into a set of discrete points,
corresponding to screen pixel locations. Characters can
be defined with rectangular pixel grids, or they can be defined with outline
shapes. The array size for character grids can vary from about 5x7 to 9x12 or
more for higher quality displays.
A character grid is displayed
by superimposing the rectangular grid pattern into the frame buffer at
a specified coordinate position. For characters that are
defined as outlines, the shapes are scanned converted into the frame
buffer by locating the pixels positions closest to the outline. Frame Buffer (Rgpv 2007,2008) Each screen pixel corresponds
to a particular entry in a 2D array residing in memory. This memory is called
a frame buffer or a bit map. The number of rows in
the frame buffer equals to the number of raster lines on the display
screen. The number of columns in this array equals to the number of pixels
on each raster line. The term pixel is also used to describe the row and the
column location in the frame buffer array that corresponds to the screen
location. A 512x512 display screen requires 262144 pixel memory locations. Whenever we wish to display a pixel on
the screen, a specific value is placed into the corresponding memory location
in the frame buffer array. Each screen pixel’s location
and corresponding memory’s location in the frame buffer is accessed by
nonnegative integer coordinate pair (x, y). The x value refers to
the column, the y value to the row position. The origin of this coordinate
system is positioned at the bottom-left corner of the screen or it is
positioned at the upper-left corner of the screen.
Frame Buffer Refresh
Refresh rate is usually 30-75Hz Direct Color Frame buffer
(Rgpv 2007,2008) Store
the actual intensities of R, G, and B individually in the frame buffer. 24
bits per pixel = 8 bits red, 8 bits green, 8 bits blue
True Color Mode-Frame buffer contains 24-bit (RGB) or 32-bit
(RGBA) for each pixel in true color mode.
Video controller Video controller
is used to control the operation of the display device (Monitor/Screen).
Video controller accesses the frame buffer to refresh the screen. In figure,
the basic refresh operations of the video-controller are shown.
Two registers are used to store the coordinates of the screen
pixels. Initially, the x register
is set to 0 and the y register is set to the value for
the top scan line. The contents of the frame buffer at this pixel position
are then retrieved and used to set the intensity of the CRT beam. Then the x register is incremented
by 1, and the process is
repeated for the next pixel on the top scan line. This procedure is continued
for each pixel along the top scan line. After the last pixel on the top
scan line has been processed, the x
register is reset to 0 and the y register is set to the value for the next scan line
down from the top of the screen. Pixels along this scan line are then
processed in turn, and the procedure is repeated for each successive scan
line. After cycling through all pixels along the bottom scan line (y=0), the
video controller resets the registers to the first pixels position on the top
scan line and the refresh process starts over. The screen must be refreshed
at a rate of at least 60 frames per second. |
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
Write short notes on frame buffer. |
Rgpv 2007,2008 |
10 |
|
Q.2 |
Explain the concept of lookup
table. |
Rgpv 2007,2008 |
10 |
|
Q.3 |
|
Rgpv 2012 |
10 |
|
UNIT
– 1 |
|||
|
Input and Output Devices/
Computer display standard / Applications of Computer Graphics |
|||
|
Unit-01/Lecture-05 |
|||
|
Input and Output Devices The user of an interactive
graphics system communicates with the graphics program by means of input devices such as keyboard, mouse, joystick, light pen; graphics tablet (digitizer), touch panels, voice
systems, and scanners.
Typically, the primary output device in a graphics system is a video monitor
such as Cathode Ray Tube (CRT) and Liquid
Crystal Display (LCD). We can obtain hard-copy output for our
images in several formats for presentations or archiving. Hard copy devices
include slides film, printers, and plotters. Computer display standard (Rgpv-2003,2005) Various computer display
standards or display modes have been used in the history of the
personal computer. They are often a combination
of Display resolution:
specified as the width and height in pixels, Color depth:
measured in bits, and Refresh rate:
expressed in hertz. A computer image is usually
represented as a discrete grid of pixels. The number of pixels determines the
resolution of the image. Typical resolutions range from 320x200 to
2000x1500 The color depth: is the
number of distinct colors that can be represented by a pixel depends on the
number of bits per pixel (bpp). A 1 bpp image uses 1
bit for each pixel, so each pixel can be either on or off. Each additional bit doubles
the number of colors available, so a 2 bpp image can have 4 colors, and a 3
bpp image can have 8 colors:
For color depths of 15
or more bits per pixel, the depth is normally the sum of the bits
allocated to each of the red, green, and blue components (RGB). High
color, usually meaning 16 bpp, normally has five bits for red
and blue, and six bits for green,
as the human eye is more sensitive to errors in green than in the other two
primary colors. For applications involving transparency, the 16
bits may be divided into five bits each of red, green, and blue, with
one bit left for transparency. A 24-bit
depth allows 8 bits per component. On some systems, 32-bit depth is available: this means that each 24-bit pixel has
an extra 8 bits to describe its opacity
(for purposes of combining with another image). Applications of Computer
Graphics ü Computer Aided Design (CAD) ü Computer Aided Geometric Design (CAGD) ü Entertainment (animation, games, etc.) ü Computer Art ü Presentation Graphics ü Education and Training ü Geographic Information Systems (GIS) ü Visualization (Scientific Vis., Inform.
Vis.) ü Medical
Visualization ü Image Processing ü Graphical User Interfaces |
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
Standard TV has 480 scan lines. If the aspect ratio is ¾.what is the
capacity of frame buffer needed if 2 bits per pixel is used? |
June
2003, dec
2005 |
10 |
|
Q.2 |
Explain the display standard of
computer graphics |
Rgpv 2005 |
10 |
|
UNIT
– 1 |
|||
|
Scan Conversion |
|||
|
Unit-01/Lecture-06 |
|||
|
Scan Conversion
(Rgpv 2005,2009,2011) The Problem of Scan Conversion- A
line segment in a scene is defined by the coordinate positions of the line
end-points.
But what happens when we try to draw this on a pixel
based display?
How do we choose which pixels to turn on? Considerations to keep in mind: –
The line has to look good •
Avoid jaggies –
It has to be lightening fast! •
How many lines need to be drawn in
a typical scene? This is going to come back to bite us again and
again. Line
Equations- lines drawing Equations Slope-
(Rgpv 2010,11)
Intercept
line equation: Where:
Lines & Slopes: Ø The
slope of a line (m) is defined by its start and end coordinates Ø The
diagram below shows some examples of lines and their slopes
We could
simply work out the corresponding y coordinate for each unit x
coordinate Let’s
consider the following example:
First work out m and b:
Now for
each x value work out the y value: Now just round off the results and turn on these
pixels to draw our line
However, this approach
is just way too slow In particular look out
for: –
The
equation y = mx + b requires the multiplication of m by x –
Rounding
off the resulting y coordinates We need a faster
solution, in the previous
example we chose to solve the parametric line equation to give us the y
coordinate for each unit x coordinate. What if we had done it
the other way around? So this gives us: Leaving out the details
this gives us:
We can see easily that
this line doesn’t look very good! We choose which way to work out the line
pixels based on the slope of the line. If the slope of a line
is between -1 and 1 then we work out the y coordinates for a line
based on its unit x coordinates. Otherwise we do the opposite – x
coordinates are computed based on unit y coordinates.
|
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
What do you mean by scan-conversion techniques? What methods are
adopted to remove the side effects of scan conversion? |
Rgpv 2005,2009,2011 |
10 |
|
Q.2 |
Write algorithm for scan
converting point and a line. |
Rgpv 2010,2011 |
10 |
|
Q.3 |
How long would it take to load a 1280 X 1024 frame buffer with 24
bit pixel,if 10bits can be transferred per second ? |
Dec 2014 |
02 |
, 
, 
, 
|
UNIT
– 1 |
|||
|
DDA-Digital Differential Algorithm (or Basic Incremental
Algorithm) |
|||
|
Unit-01/Lecture-07 |
|||
|
Three line drawing algorithms will
be discussed below. They are: ( Rgpv-2009,11) Ø
Digital
Differential Algorithm (DDA) Ø
Midpoint Line Algorithm Ø
Bresenham’s Line Algorithm DDA-Digital
Differential Algorithm (or Basic Incremental Algorithm) The DDA Algorithm The digital differential analyzer (DDA) algorithm takes an incremental approach in order to speed up scan conversion Simply
calculate yk+1
based on yk Consider the list of points that we determined
for the line in our previous example: (2, 2), (3, 23/5),
(4, 31/5), (5, 34/5), (6, 42/5),
(7, 5) Notice
that as the x coordinates go up by one, the y coordinates simply go up by the
slope of the line This is the key insight in the DDA algorithm. When the slope of the line is between -1 and 1 begin at the first point in the line and, by incrementing the x coordinate by 1, calculate the corresponding y coordinates as follows: When the slope is outside these limits, increment
the y coordinate by 1 and calculate the corresponding x
coordinates as follows:
Again the values calculated by the
equations used by the DDA algorithm must be rounded to match pixel values
DDA Algorithm Example
(brute force approach) ·
For y =
mx + b, slope m = Dy / Dx ·
Idea is
to increment x by 1 (xi) and calculate yi=mxi
+ b ·
Pixel to
be turned on is at (xi, round(yi))
The simplicity of this algorithm
is its advantage but it is inefficient due to ·
Floating
point multiplication and Addition ·
Rounding We can eliminate the
multiplication by noting that: yi+1 = mxi+1 +
b = m(xi +Dx
) + b = yi + mDx since Dx = 1 = yi + m (For slope |m| > 1, just do the
opposite: increment y and compute x, xi+1=xi+m-1.) C code Line (int x0,
int y0, int x1, int y1) { int x; float m, y; m = (y1-y0)/(x1-x0); y=y0; for (x=x0; x<=x1; x++) { TurnOn(x, (int)(y+0.5)); y+=m; } } must check for special case m =
infinity. Drawback: ·
Floating
point values (m,y) ·
Round
operation ·
Special
cases m = 0 or infinity |
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
|
2011 |
10 |
|
Q.2 |
|
2013 |
7 |
|
Q.3 |
Briefly describe DDA algorithm? |
Dec 2015 |
2 |
|
UNIT
– 1 |
|||
|
Midpoint Line Algorithm(variant of Bresenham’s) |
|||
|
Unit-01/Lecture-08 |
|||
|
Reduces to Bresenham’s for lines
and circles
(RGPV-2009,10,11) ·
Uses
only integer arithmetic and no rounding ·
Idea is
to provide the best-fit approximation to a true line by minimizing the error
(distance) to the true line. ·
Slope 0 £
m £ 1 (rest is done with reflection) ·
Endpoints
: (x0, y0) and (x1, y1)
E – east pixel from P NE – northeast pixel Q – intersection point of line
with x = xp+1 M – midpoint of E and NE Idea ·
If Q
> M then pick NE ·
If Q
< M then pick E ·
If Q = M
then pick either one (but be consistent) Error will be £
0.5 How to do: ·
Line
(implicit form) F(x,y) = ax + by + c = 0 (a, b, c = ?) ·
slope
intercept form y = (dy/dx)x + B dy ·x - dx·y
+ B·dx = 0 ·
therefore a = dy, b = -dx and c = Bdx ·
F(x,y) =
0 – on line > 0 – for points below
line < 0 – for points above
line ·
so, need
only compute F(xp+1,yp+1/2) and test it’s sign ·
assume
that d = F(xp+1, yp+1/2) then d > 0 pick NE d < 0 pick E d = 0 pick either, say E iteratively calculate d: depends on pick of NE or E ·
if E dnew = F(xp+2,
yp+1/2) = a(xp+2) + b(yp+1/2)
+ c but dold = a(xp+1) + b(yp+1/2)
+ c therefore dnew = dold + a DE = a = dy so, do not have to computer F
directly ·
if NE dnew = F(xp+2,
yp+1+1/2)
dnew = dold
+ a + b DNE = a + b = dy – dx ·
so at
each step, pick between NE and E by sign of d, then update d by DNE or DE ·
to begin d = F(x0+1, y0+1/2) = F(x0, y0)
+ a + b/2 = a + b/2 = dy – dx/2 ·
can get rid
of fraction dx/2 by replacing F(x,y) by 2F(x,y), so need only simple
addition. C code Line (int x0, int y0, int x1, int
y1) {
int dx, dy, dE, dNE, d, x, y;
dx = x1 – x0;
dy = y1 = y0;
d = 2 * dy – dx;
dE = 2 * dy;
dNE = 2 * (dy – dx);
x = x0;
y = y0;
while (x<x1){ if (d <=0) { d+=dE; ++x; } else { d+=dNE; x++; y++; } TurnOn(x,y);
} } Addition Issues ·
Endpoint
order a line from P0 to P1 must be the same as the line from P1
to P0 ·
Starting
at the edge of a clip rectangle must know error at clip point or line will be altered if
assumed to be starting point ·
Varying
the intensity of a line as a function of slope one way to reduce aliasing ·
Outline
primitives composed of lines |
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
Explain the Brersenham’s line algorithm for drawing a line with a
slope less than 1 and grater than 0. |
2011 |
8 |
|
Q.2 |
|
2012 |
10 |
|
Q.3 |
Write the Bresenham line algorithm |
Dec 2014 |
02 |
|
UNIT
– 1 |
|||
|
Bresenham's Circle Algorithm |
|||
|
Unit-01/Lecture-09 |
|||
|
Bresenham's Circle Algorithm (RGPV-2010,11, 12) We know that there are 360 degrees in a circle. First we see that a
circle is symmetrical about the x axis, so only the first 180 degrees need to
be calculated. Next, we see that it's also symmetrical about the y axis, so now
we only need to calculate the first 90 degrees. Finally, we see that the
circle is also symmetrical about the 45 degree diagonal axis, so we only need
to calculate the first 45 degrees. Bresenham's circle algorithm calculates the locations of the pixels
in the first 45 degrees. It assumes that the circle is centered on the origin
shifting the original center coordinates (centerx,centery). So for every
pixel (x,y) it calculates, we draw a pixel in each of the 8 octants of the
circle :
As can be easily intercepted, the continuous arc of the circle can
not be plotted on a raster display device, but has to be approximated by
choosing the pixels to be highlighted. At any point (x,y), we have two
choices – to choose the pixel on east of it, i.e. N(x+1,y) or the south-east
pixel S(x+1,y-1). To choose the pixel, we determine the errors involved with
both N & S which are f(N) and f(S) respectively and whichever gives the
lesser error, we choose that pixel. if di<=0, and if
di>0,
|
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
|
2012 |
10 |
|
Q.2 |
|
2013 |
7 |
|
Q.3 |
Apply midpoint circle drawing
algorithm to draw a circle of radius 8. |
Dec 2014 |
7 |
|
Q.4 |
Write the steps of mid-point
circle generation algorithm and use it to find the pixels would be needed to
put on to generate an arc with outer origin laying between (-9,0) and (0,9). |
Dec 2015 |
7 |
|
UNIT
– 1 |
|||
|
Scan line Fill Algorithm |
|||
|
Unit-01/Lecture-10 |
|||
|
Scan line Fill Algorithm − Intersect scanline with polygon edges − Fill between pairs of intersections − Basic algorithm: For y = ymin to ymax 1) intersect scan line y with each edge 2) sort int eresections by increasing x[p0,p1,p2,p3] 3) fill pairwise (p0 −> p1, p2−> p3, ....)
However, we need to handle some special cases and improve the
performance Special handling: a) Make sure we only fill the interior pixels Define interior: For a given pair of intersectin points (Xi, Y), (Xj, Y) −> Fill ceiling(Xi) to floor(Xj) important when we have
polygons adjacentto each other b) Intersection has an integer X coordinate −> if Xi is integer, we define it to be interior −> if Xj is integer, we define it to be exterior (so don’t
fill) Special handling(cont’d) c) Intersection is an edge end point
Intersection points: (p0, p1, p2) ??? −> (p0,p1,p1,p2) sowe can still fill pairwise −> In fact, if we compute the intersection of the scanline
with edge e1 and e2 separately, we will get the intersection point p1 twice. Keep both of the p1. Special handling(cont’d) c) Intersection is an edge end point (cont’d)
However, in this case we don’t want to count p1 twice (p0,p1,p1,p2,p3), otherwisewe willfill pixels betweenp1 and
p2, which is wrong Special handling(cont’d) c) Intersection is an edge end point (cont’d) Rule: If the intersectionis the ymin of theedge’s endpoint, count
it. Otherwise, don’t.
|
|||
|
S.NO |
RGPV
QUESTIONS |
Year |
Marks |
|
Q.1 |
|
2011
dec |
10 |
|
Q.2 |
|
2011 jun |
14 |
|
Q.3 |
Discuss following in brief: 1)
Character generations 2)
Boundary fill and Flood fill |
Dec 2015 |
7 |
