Geometric Representations and Transformations

Abstract

This chapter provides important background material that will be needed for Part II. Formulating and solving motion planning problems require defining and ma-nipulating complicated geometric models of a system of bodies in space. Section 3.1 introduces geometric modeling, which focuses mainly on semi-algebraic mod-eling because it is an important part of Chapter 6. If your interest is mainly in Chapter 5, then understanding semi-algebraic models is not critical. Sections 3.2 and 3.3 describe how to transform a single body and a chain of bodies, re-spectively. This will enable the robot to “move. ” These sections are essential for understanding all of Part II and many sections beyond. It is expected that many readers will already have some or all of this background (especially Section 3.2, but it is included for completeness). Section 3.4 extends the framework for trans-forming chains of bodies to transforming trees of bodies, which allows modeling of complicated systems, such as humanoid robots and flexible organic molecules. Finally, Section 3.5 briefly covers transformations that do not assume each body is rigid. 3.1 Geometric Modeling A wide variety of approaches and techniques for geometric modeling exist, and the particular choice usually depends on the application and the difficulty of the problem. In most cases, there are generally two alternatives: 1) a boundary repre-sentation, and 2) a solid representation. Suppose we would like to define a model of a planet. Using a boundary representation, we might write the equation of a sphere that roughly coincides with the planet’s surface. Using a solid represen-tation, we would describe the set of all points that are contained in the sphere. Both alternatives will be considered in this section. The first step is to define the worldW for which there are two possible choices: 1) a 2D world, in which W = R2, and 2) a 3D world, in which W = R3. These