| dc.description.abstract | Geometric computations are essential in many real-world problems. One important
issue in geometric computations is that the geometric models in these problems
can be so large that computations on them have infeasible storage or computation
time requirements. Decomposition is a technique commonly used to partition complex
models into simpler components. Whereas decomposition into convex components results
in pieces that are easy to process, such decompositions can be costly to construct
and can result in representations with an unmanageable number of components. In
this work, we have developed an approximate technique, called Approximate Convex
Decomposition (ACD), which decomposes a given polygon or polyhedron into "approximately
convex" pieces that may provide similar benefits as convex components,
while the resulting decomposition is both significantly smaller (typically by orders of
magnitude) and can be computed more efficently. Indeed, for many applications, an
ACD can represent the important structural features of the model more accurately
by providing a mechanism for ignoring less significant features, such as wrinkles and
surface texture. Our study of a wide range of applications shows that in addition to
providing computational efficiency, ACD also provides natural multi-resolution or hierarchical
representations. In this dissertation, we provide some examples of ACD's
many potential applications, such as particle simulation, mesh generation, motion
planning, and skeleton extraction. | en |
