The title pretty much explains it but I'm gonna go into more details. We have 3D mesh object and we want to decompose it into separate objects so that each one of these objects can be seen completely if we place a point somewhere inside them. The point location will not be random. We just need to make sure that there is a place inside the objects where the point can see the object completely.

If we speak in 2D terms, we are trying to break down the mesh in star-shaped polyhedrons.

There is an algorithm on this by Keil for the 2 dimensions (Minimum star-shaped decomposition) but I haven't found anything on 3D.

There are,however, papers on convex decomposition and this works but it will lead into more parts than I would like . Will I have to rely on these? How else should I approach this?

Extra notes: We have to do with polyhedrons with no holes and the decomposition doesn't have to be the minimum one.

  • \$\begingroup\$ Possible duplicate of gamedev.stackexchange.com/questions/53142/… \$\endgroup\$
    – user116458
    Jul 5, 2018 at 12:42
  • \$\begingroup\$ I'm not looking for convex decomposition. I just asked if that's my only alternative. \$\endgroup\$ Jul 5, 2018 at 12:43
  • \$\begingroup\$ Try searching for approximate convex decomposition. That will give you the minimum parts \$\endgroup\$
    – user116458
    Jul 5, 2018 at 12:46
  • \$\begingroup\$ Can I see the paper that you mentioned \$\endgroup\$
    – user116458
    Jul 5, 2018 at 12:47
  • 1
    \$\begingroup\$ This is related to (but not quite) the Art Gallery Problem for 3D, and it's an area of ongoing research. The general problem is both hard to solve optimally and hard to approximate well, so it helps to narrow down your requirements. Do you have any constraints on the shapes of the polyhedra you expect as inputs? (Eg. can they have holes, how many and of what shapes; are their faces orthogonal to one another, is there any pattern to their reflex edges...) And do you need the minimum such decomposition, or can your application tolerate some excess guards/parts? \$\endgroup\$
    – DMGregory
    Jul 5, 2018 at 13:15


You must log in to answer this question.

Browse other questions tagged .