5
$\begingroup$

I am working with a PWP3D-like algorithm that renders silhouettes of a mesh in order to segment a frame of video and update an object's pose. Because it is only the silhouettes of the mesh that matter, it would be nice to automatically generate simpler meshes where the indents/concavities that do not affect the silhouette are removed. That is, I want to generate a simpler mesh that has the exact same silhouette as the original when viewed at any angle from any position outside of the mesh's convex hull.

Is there an existing technique for doing this? Or even just some definitions other than "indent" that better describe this problem that might aid in a web search for this? I've currently found mesh simplification/decimation techniques that aim to preserve silhouettes, but these are not exactly what I'm looking for right now, and they generally seem to just simplify indents rather than outright removing/filling them. I have an idea for an algorithm that I think would work, but I want to check if anything else already exists.

As a visual example of what I mean, below is a mesh that, if such a technique were applied, would have the orange-highlighted faces removed and be turned into an ordinary cube.

An example of a mesh that would become a cube if such a technique were applied

At the same time, though, the problem is not as simple as just taking the convex hull, because this mesh, for example, is fine as it is. A mesh shaped like a 3D letter C

$\endgroup$
1
  • 2
    $\begingroup$ This is a really interesting question that I don’t have a full answer for, but one observation: it looks like a determining factor in whether a given polygon contributes to the silhouette is whether any of the vertices it’s connected to are below the plane of the polygon. That might help decide what to remove. $\endgroup$ Mar 1 at 18:28
3
$\begingroup$

After a fair bit of reading and skimming through papers, I have yet to find a good definition other than "indent" for what I want to remove, but I have found answers to pretty much everything else.

The concept of a "Visual Hull" is what I was looking for regarding a mesh that doesn't have these indents. While the Wikipedia page, and a bunch of other resources, usually just refer to visual hulls created from a finite set of viewpoints, e.g. a set of real-life cameras, Laurentini, who introduced the term "Visual Hull", also introduces a term "External Visual Hull" to refer to one created using every possible viewpoint outside of the convex hull [1]. This will have the exact same silhouette as the original mesh when viewed from any position outside the convex hull at any angle, so it was exactly what I was looking for.

[1] also contains an algorithm for computing the external visual hull for polyhedra, but it is sorta brute-force and is $O(n^{12})$. In [2], Petitjean introduces a much more efficient algorithm for polyhedra, and Bottino and Laurentini also describe a more efficient algorithm in [3]. In addition to these algorithms for polyhedra, other works by Laurentini also discuss algorithms for doing the same for curved objects, surfaces of revolution, etc. I have yet to come across anyone actually implementing these algorithms, though.

I'd like to describe all of these in more detail, but I still need to finish reading through them, and based on some deadlines coming up, I do not think I will have the time to do so for a little while. I hope to eventually come back to this post and edit it to actually describe at least one of the algorithms. However, if someone reading this wants to look these up for themselves, then in addition to the below citations, I would like to note that even if you don't normally have access to papers, e.g. through a post-secondary institution, all of these seem to be publicly available. You can download [1] from ResearchGate here, download [2] from ResearchGate here (though I have no clue why different authors are listed for it than Petitjean), and [3] can be found in Google Books.

Citations:

[1] Laurentini, Aldo. (1994). The Visual Hull Concept for Silhouette-Based Image Understanding. Pattern Analysis and Machine Intelligence, IEEE Transactions on. 16. 150-162. 10.1109/34.273735.

[2] Petitjean, S. (1998). A computational geometric approach to visual hulls. International Journal of Computational Geometry & Applications, 8(04), 407-436.

[3] Bottino, Andrea & Laurentini, Aldo. (2006). Retrieval of Shape from Silhouette. 10.1016/S1076-5670(05)39001-X.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.