Abstract:

     One common strategy for dealing with large, complex 
models is to partition them into pieces that are easier to 
handle. While 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.  We propose a 
strategy to decompose a model in R^2 or R^3 
into "approximately convex'' pieces. For many applications, 
the approximately convex components of this decomposition 
provide similar benefits as convex components, while the 
resulting decomposition is both significantly smaller and 
can be computed more efficiently. Moreover, for many 
applications, an approximate convex decomposition (ACD) 
provides a mechanism to focus on important structural 
features and ignore less significant features, such as 
wrinkles and other surface texture.

     In this talk, I will present a simple algorithm that 
computes an ACD of a 2D or 3D model by iteratively removing 
(resolving) the most significant non-convex features 
(notches).  We first describe the approach and present 
experimental results as applied to a simple polygon with or 
without holes. In this case, it computes an ACD of a simple 
polygon with n vertices and r notches in O(nr) time; in 
contrast, exact minimum convex decomposition is NP-hard or, 
if the polygon has no holes, takes O(nr^2) time.  We next 
discuss the challenges of extending ACD to polyhedra, 
closed or not, with arbitrary genus, describe strategies 
for addressing these difficulties, and present experimental 
results for ACD of polyhedra. In all studied examples, our 
experimental results show that the resulting decomposition 
is is both significantly smaller and can be computed more 
efficiently. Interestingly, this same strategy can be 
applied to compute both volumetric and surface 
decompositions of polyhedra.

     This work is joint with Nancy Amato. More information 
about this research can be found at 
http://parasol.tamu.edu/groups/amatogroup/research/app-cd/


Bio:

     Jyh-Ming Lien is a Ph.D. student in the Department of 
Computer Science at Texas A&M University working with Dr. 
Nancy Amato. He is a member of the Algorithms & 
Applications Group in the Parasol Lab. His research is in 
the areas of computational geometry, robotics motion 
planning and computer graphics.  He received his B.S. in 
Computer Science from National ChengChi University, Taiwan, 
in 1999. Information about his research and many of his 
publications can be found at: 
http://parasol.tamu.edu/~neilien/