Overview This topic is about constructive geometry. Our object is to study geometry, all sorts of geometry, and also to present a setting in which to carry out this investigation on a computer. The adjective "constructive" is intended to imply that we will not be satisfied with an answer to a geometric problem unless we […]

# Computer Graphics and Geometric Modeling

## Introduction To Basic Computer Graphics Part 2

Graphics Standards and Primitives A person who wants to develop a graphics program has to learn how to access the graphics capabilities of the system that he/she is working on. Unfortunately, there are many graphics devices out there in the world. If one wanted a program to work with all those devices and if one […]

## Raster Algorithms (Basic Computer Graphics) Part 1

Introduction As pointed out in our introductory topic, the only real implementation constraint that the hardware places on us is that all geometric objects eventually need to be represented by a collection of points in a two-dimensional grid (a raster). The subject matter of this topic is to analyze the geometry of discrete sets and […]

## Raster Algorithms (Basic Computer Graphics) Part 2

Fill Algorithms Contour-filling algorithms are used in many places. For example, in pattern recognition problems integrals may have to be computed over areas; in photo typesetting, fonts are described by contours that are later filled; in animation, the cel painter who fills figures has the next most time-consuming job after the animator. There are two […]

## Raster Algorithms (Basic Computer Graphics) Part 3

The Bresenham Line-Drawing Algorithm Although the DDA algorithms for drawing straight lines are simple, they involve real arithmetic. Some simple modifications result in an algorithm that does only integer arithmetic, and only additions at that. Note that in the case of the simple DDA, either x or y will always be incremented by 1. For […]

## Raster Algorithms (Basic Computer Graphics) Part 4

Choosing the Coordinates of a Pixel Before going on to discuss another scan conversion algorithm we pause to take up a subject that probably did not occur to the reader as being an issue. However, since pixels should be treated as having area, if we consider our image as corresponding to a grid as we […]

## Raster Algorithms (Basic Computer Graphics) Part 5

Drawing Ellipses and Other Conics The equation for the standard ellipse centered at the origin is and we can generate points on it using the standard parameterization Algorithm 2.9.2.2. An improved Bresenham circle-drawing algorithm (one octant). Differentiating equation (2.6) implicitly gives the differential equation This leads to a DDA approach similar to the case […]

## Clipping (Basic Computer Graphics) Part 1

Introduction Planar clipping algorithms rank as probably the second most important type of algorithm in computer graphics, following right behind line-drawing algorithms in importance. Mathematically to clip one set against another means to find their intersection. In practice, one usually wants also to get this intersection in terms of some predefined data structure. This chapter […]

## Clipping (Basic Computer Graphics) Part 2

Liang-Barsky Line Clipping The Liang-Barsky line-clipping algorithm ([LiaB84]) optimizes the Cyrus-Beck line-clipping algorithm in the case where we are clipping against a rectangle. It starts by treating a segment as a parameterized set. LetA typical pointon the oriented line L determined by P1 and P2 then has the form See Figure 3.5. If we letthen […]

## Clipping (Basic Computer Graphics) Part 3

Nicholl-Lee-Nicholl Line Clipping One of the problems common to both the Cohen-Sutherland and the Liang-Barsky algorithm is that more intersections are computed than necessary. For example, consider Figure 3.6 again where we are clipping line segment [P1,P2] against the window. The Cohen-Sutherland algorithm will compute the intersection of the segment with the top boundary at […]