Graphics Reference
In-Depth Information
CHAPTER 6
Basic Geometric Modeling Tools
Prerequisites: Basic vector algebra
6.1
Introduction
This chapter describes some often-used mathematical tools and formulas in geometric
modeling. The author highly recommends the Graphics Gems series of topics to the
reader (see the “Miscellaneous” section of the Bibliography). These topics contain
many insights into how one can make computations and algorithms more efficient.
We begin by discussing bounding objects, such as boxes, slabs, and spheres, and
their uses in Section 6.2. Next, in Section 6.3 we look at tests for when a point is inside
a region. Section 6.4 describes some facts that, in one way or another, are related to
orientation. Some simple intersection algorithms are discussed in Section 6.5. Section
6.6 has some formulas for distances between objects, Section 6.7 has area and volume
formulas, and Section 6.8 has formulas for circle constructions. We finish the chapter
with some miscellaneous observations in Sections 6.9 and 6.10.
6.2
Bounding Objects and Minimax Tests
Checking for or finding intersections, as for example in clipping, visible surface deter-
mination, and collision detection, is a frequently performed task in graphics. It is also
one that is usually very computation intensive, even for simple objects like polygons.
Now, if complicated objects intersect, then one has to accept the fact that finding this
intersection will take a lot of work. On the other hand, to make lengthy computations
only to find out in the end that the objects do not intersect is very inefficient. One
would like a quicker way to detect when objects are disjoint. A standard way to do
this is to enclose objects in simpler ones and first check for intersections among these
simpler objects. If they do not intersect, then by definition, the original objects will
Search WWH ::




Custom Search