Polygon drawing

how to draw polygon by computer, 2D & 3D polygons

1. Polygon DrawingPolygon Drawing
CG Seminar
By
Ali Abdul_Zahraa

2. polygon
0
A polygon is a bounded region of a plane.
0It is bounded by a series of line segments.
0 A line segment is a piece of a line that runs from one
point to another point.
0 The line segment end point is called a vertex.
0 Each vertex is shared by exactly two line segments

3. polygon
0A polygon in a computer graphics system is a two-
dimensional shape that is modeled and stored within
its database (memory) .
0A polygon can be colored, shaded and textured, and
its position in the database (memory) is defined by
the coordinates of its vertices (corners(

4. Polygons types
Main Types Are :
0Convex polygons
0Concave polygons
0Complex polygons

5. Convex polygons
0A convex polygon is a simple polygon whose
interior is a convex set.
0In a convex polygon, all interior angles are less
than 180 degrees

6. Convex polygons
0Every line segment between two vertices remains
inside or on the boundary of the polygon.

7. Convex polygons
0The intersection of two convex polygons is a
convex polygon

8. Convex polygons
0Helly's theorem: For every collection of at least 3
convex polygons: if the intersection of every 3 of them
is nonempty, then the whole collection has a
nonempty intersection.

9. Convex polygons
0Every polygon inscribed in a circle (such that all
vertices of the polygon touch the circle), if not self-
intersecting, is convex. However, not every convex
polygon can be inscribed in a circle

11. Concave or non-convex polygons
0A simple (non-self-intersecting) polygon that is not
convex is called concave, non-convex or reentrant.
A simple concave polygon will always have an interior
angle with a measure that is greater than 180
degrees.
0It is always possible to partition a concave polygon
into a set of convex polygons

13. Complex polygons
0Complex polygons are a real mess. The edges of
complex polygons cross each other.

14. Regular & irregular
polygon
0A polygon is equilateral if all of its sides are of the
same length.
0A polygon is equiangular if all of its angles are of
equal measure.
0A regular polygon is a polygon that is both
equilateral and equiangular.

15. Named Polygons
0Triangle 3 sides
0Quadrilateral 4 sides
0Tetragon 4 sides
0Pentagon 5 sides
0Hexagon 6 sides
0Heptagon 7 sides
0Octagon 8 sides
0Decagon 10 sides
0Dodecagon 12 sides

17. process of drawing
0There are at least three different names for the
process of drawing :
1 . it called "rendering" which means to make a copy of
something. when you draw a polygon you are making
a visible copy of its representation in memory.

18. process of drawing
2. Another term "scan conversion." This means
drawing it as a set of scan lines. It also implies that
you want to draw it in scan line order, from the top of
the screen to the bottom of the screen, to match the
way the electron beam scans out the picture on the
tube. The term comes from the days before frame
buffers when the picture had to be scan converted on
the fly for each frame.

19. process of drawing
3. The other term used to describe drawing into a
frame buffer is "rasterization.". That makes a raster
the picture part of a CRT and rasterization is the
process of drawing something on a CRT.

20. make a good polygon rendering
algorithm
0Speed is important. Faster is better as long as the picture
is good enough for your purpose.
0Memory isn't cheap. Don't use more than you need. But, if
you can trade memory for speed, go for it.
0It is not OK to leave gaps between polygons that share
edges.
0What you see on the screen has to be an accurate
representation of the mathematical model.
0The algorithm must be extendible. Vertices contain more
than just X and Y coordinates. You need a Z coordinate for
hidden surface removal. You might also have colors at each
coordinate to support color blending across the polygon
face. And, you might want to carry texture coordinates
along.

21. Vertex & edge
0A vertex is a point. vertex can fall in a lot of different
places on a pixel.
0An edge is a line that runs from one vertex to another.
That means that an edge starts somewhere inside a
pixel and ends inside another pixel

22. 2D polygon drawing
0The simplest way to represent a polygon is as a list of
its vertices. You just assume that there is a line
segment connecting the first vertex on the list with
the second, the second with the third, and so on until
you reach the last vertex. The last vertex is connected
to the first vertex to close the polygon boundary.
0 bresenham's , DDA (useful).

23. Parity test
0The well defined ways to decide what part of a
plane is inside a polygon. The idea of the parity
test is to trace a line from outside the polygon
("from infinity") to the other side of the polygon
(negative infinity) and count how many times the
line crosses an edge of the polygon.
0If the line has crossed an odd number of edges it's
inside the polygon and if it's crossed an even
number of edges it's outside the polygon .

24. 0A frame buffer is a two dimensional array of pixels.
0Each row of pixels in the frame buffer tells the
video hardware what color to draw along a scan
line of the display screen.
0This means that we can draw a polygon by coloring
the parts of the scan line that are inside the
polygon and the parity test is just perfect for telling
when a scan line is inside a polygon.
0 For any scan line find all the places that it crosses a
polygon edge, sort the crossings by their X
coordinate, and fill in the part of the scan line
between each pair of crossings.

25. The edge problem
0It’s happen when the drawing algorithm entered in
infinite loop of edge (lines) drawing that when the
first and last edge not determined, the drawer may
draw the edge between vertices many time
0Or when the edge fall between two polygons will be
filled in by both polygons. Filling the pixel twice is
wasteful

26. The edge problem
0So to solve this problem must adding another vector to save
how is vertices was visited.
0Also it’s a solving to a problem that happen In parity test
when the vertex fall on scan line, each vertex belong to two
edges so that will give not accurate number of scan line hit ,
so it will solved by this method.

27. 3D polygon Drawing
0An easy way to determine a path along a polygonal
surface mesh is to determine a plane that contains the
two points and is generally perpendicular to the
surface.
0The intersection of the plane with the faces making up
the surface mesh will define a path between the two
points

28. 0a greedy-type algorithm can be used to construct a
path of edges along a mesh surface from a given start
vertex to a given destination vertex
0 For each edge emanating from the current vertex
(initially the start vertex), calculate the projection of
the edge onto the straight line between the current
vertex and the destination vertex

29. 0 Divide this distance by the length of the edge
to get the cosine of the angle between the
edge and the straight line.
0The edge with the largest cosine is the edge
most in the direction of the straight line;
choose this edge to add to the path
0Keep applying this until the destination edge
is reached.
0Improvements to this approach can be made
by allowing the path to cut across polygons to
arrive at points along opposite edges rather
than by going vertex to vertex

30. 0Candidate edges can be generated by projecting the
straight line onto polygons containing the vertex
and then computing their cosine values for
consideration.
0 If a path downhill from an initial point on the
surface is desired, then the surface normal and
global up vector can be used to determine the
downhill vector.
0The cross product of the normal and global up
vector defines a vector that lies on the surface
perpendicular to the downhill direction. So the
cross product of this vector and the normal vector
defines the downhill (and uphill) vector on a plane

31. polyhedron
0A polyhedron is a 3-dimensional figure whose
surfaces are polygons.

32. Which of these is
polyhedron???

33. References
0http://www.mathopenref.com/polygon.html
0Computer Animation Algorithms and Techniques,
Rick Parent
0http://en.wikipedia.org/wiki/Polygon

34. Thank
U
☺ ☺ ☺

35. 0Hyperplane separation theorem: Any two convex
polygons have a separator line. If the polygons are
closed and at least one of them is compact, then there
are even two parallel separator lines (with a gap
between them)

36. 0Krein–Milman theorem: A convex polygon is
the convex hull of its vertices. ) one only needs
the corners of the polygon to recover the
entire polygon shape.(

37. 0Inscribed triangle property: Of all triangles contained
in a convex polygon, there exists a triangle with a
maximal area whose vertices are all polygon vertices