decomposition of non-convex objects

[Vadim Shapiro]

This problem is a special case of the boundary to CSG conversion, 
where CSG form is limited to the union of intersection (sum of products) 
terms.   Some references:

@Article{sv91a,
 author = {V. Shapiro and D. L. Vossler}, 
 title = {Construction and optimization of {CSG} representations}, 
 journal = {Computer-aided design},
 volume = 23, number = 1,
 pages = {4--20}, 
 month = jan,
 year = 1991    }

@Article{shvo93,
 author = {Shapiro, V. and Vossler, D. L.},
 title = {Separation for boundary to {CSG} conversion},
 journal = {ACM Transactions on Graphics},
 volume = 12,
 number = 1,
 month = jan,
 year = 1993,
 pages = {35--55}}

The first reference is probably sufficient for your purposes.  
The second deals  more with curved solids.
There is also an implementation of the general conversion procedure for 
solids bounded by planar and quadric halfspaces that can be modified 
to produce this form of CSG only.   The implementation requires use of 
Parasolid kernel and is publicly available from Cornell or from U. Wisconsin.

Cheers, 

-Vadim 

Vadim Shapiro
--------------------------------------------------------------------
Mechanical Engineering and Computer Sciences
University of Wisconsin-Madison     
1513 University Avenue,  Madison, WI  53706  SA
phone: (608) 262-3591,   fax: (608) 265-2316
vshapiro at engr.wisc.edu   http://sal-cnc.me.wisc.edu/ 

At 07:30 PM 4/17/99 -0400, Brad Barber wrote:
>I received the following request from John Nagle.  Any ideas?
>
>Thanks for your help.
>							--Brad
>
>-----------------
>X-Sender: nagle at shell5.ba.best.com
>Date: Mon, 12 Apr 1999 19:06:06 -0800
>To: Brad Barber <bradb at shore.net>
>From: nagle at animats.com (John Nagle)
>Subject: Decomposition into convex objects
>
>    A problem related to convex hulling is the decomposition of a nonconvex
>solid into convex solids.  This problem doesn't seem to be well-studied.
>Is there any active work in that area of which you are aware?
>
>    It's worth noting that, while the usual mathematical formulation of
>this question is the decomposition of a nonconvex solid into a set of convex
>solids whose sum is the original solid, a set of convex solids whose UNION
>is the original solid would be equally useful for collision detection work.
>That might be an easier problem.
>
>    In fact, decomposition into a set of convex patches whose sum is the
>surface of the original would be quite useful for collision detection,
>and probably much easier than the other problems.  The hard problems
>in convex decomposition mostly involve the creation of new interior
>surfaces.
>
>                                        John Nagle
>                                        Animats
>                                        www.animats.com
>
>
>
>
>--------------------------------------------
>Brad Barber   Cambridge MA   bradb at shore.net 
>http://www.geom.umn.edu/locate/qhull  version 2.6
>
>-------------
>The compgeom mailing lists: see
>http://netlib.bell-labs.com/netlib/compgeom/readme.html
>or send mail to compgeom-request at research.bell-labs.com with the line:
>send readme
>Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.
> 


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.