3
$\begingroup$

Basically, I'm interested in doing 2 things. Let's say we have a mesh M.

1. Find the minimum number of points(inside M) required to see the whole M.

2. Decompose M into polyhedrons which can be seen by only one point inside of them.

There are many articles on 2, for example I've found algorithms on convex decomposition of an object. I can surely use such algorithms but I need to have this ready in a sort amount of time and I think I can benefit from 1 and solve 2 very easily.

Let's say solution of 1 gives that the minimum number is N. The solution I'm thinking of requires finding the visibility of these N points, meaning I already have the parts of the object each of these points can see.

Having these parts I can easily construct the visible object from each point, excluding overlapping parts, therefore getting a minimum decomposition for my object.

My main concern is my solution for the first problem. I can't find anything on this online. I did find adequate information on the 2D art gallery problem but not on this. My only idea is to take samples of points in the object and do the following :

First I find the visibility polyhedron of every point inside the object ( that is the part of the object I can see).

Then for every combination of these points I combine their visibility polygons and see if their union forms M. The union with the least number of points is my solution.

Inspecting all the combinations is heavy obviously.I can save time starting from some upper bound but that is not the point. Is there a faster or less "brute force" approach?

$\endgroup$
  • 1
    $\begingroup$ The 2D art gallery problem is $\exists \mathbb{R}$-complete, so the 3D problem is as well. This implies you should not expect to find any algorithm that is efficient, scales well to large meshes, and always provides the optimal answer. Also, there is no known constant-factor approximation algorithm for the 2D problem. You could try reading the best approx. algorithm for the 2D problem and see if its ideas extend to the 3D setting as well (Wikipedia cites arxiv.org/abs/1607.05527). $\endgroup$ – D.W. Jun 10 '18 at 19:31
  • 1
    $\begingroup$ O'Rourke's book has a section on the 3D art gallery problem but from a quick skim it looks like it has no useful positive results; only negative results. $\endgroup$ – D.W. Jun 10 '18 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.