<p>After a fair bit of reading and skimming through papers, I have yet to find a good definition other than &quot;indent&quot; for what I want to remove, but I <em>have</em> found answers to pretty much everything else.</p>
<p>The concept of a &quot;<a href="https://en.wikipedia.org/wiki/Visual_hull" rel="nofollow noreferrer">Visual Hull</a>&quot; 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 &quot;Visual Hull&quot;, also introduces a term &quot;External Visual Hull&quot; to refer to one created using <em>every</em> 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.</p>
<p>[1] also contains an algorithm for computing the external visual hull for polyhedra, but it is sorta brute-force and is <span class="math-container">$O(n^{12})$</span>. 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 <em>implementing</em> these algorithms, though (other than the <a href="https://github.com/cm-1/2D-External-Visual-Hulls" rel="nofollow noreferrer">2D version</a>).</p>
<p>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 <a href="https://www.researchgate.net/publication/3192242_The_Visual_Hull_Concept_for_Silhouette-Based_Image_Understanding" rel="nofollow noreferrer">here</a>, download [2] from ResearchGate <a href="https://www.researchgate.net/publication/2781058_A_Computational_Geometric_Approach_To_Visual_Hulls" rel="nofollow noreferrer">here</a> (though I have no clue why different authors are listed for it than Petitjean), and [3] can be found in Google Books.</p>
<p>Citations:</p>
<p>[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.</p>
<p>[2] Petitjean, S. (1998). A computational geometric approach to visual hulls. International Journal of Computational Geometry &amp; Applications, 8(04), 407-436.</p>
<p>[3] Bottino, Andrea &amp; Laurentini, Aldo. (2006). Retrieval of Shape from Silhouette. 10.1016/S1076-5670(05)39001-X.</p>

CC BY-SA 4.0
2021-03-02T02:07:11.033Z
2024-10-08T18:38:04.327Z
2024-10-08T18:38:04.327Z
FilmCoder
<p>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.</p>
<p>Is there an existing technique for doing this? Or even just some definitions other than &quot;indent&quot; 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.</p>
<p>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.</p>
<p><a href="https://i.sstatic.net/ZgizM.png" rel="noreferrer"><img src="https://i.sstatic.net/ZgizM.png" alt="An example of a mesh that would become a cube if such a technique were applied" /></a></p>
<p>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 href="https://i.sstatic.net/Cg6p5.png" rel="noreferrer"><img src="https://i.sstatic.net/Cg6p5.png" alt="A mesh shaped like a 3D letter C" /></a></p>

CC BY-SA 4.0
2021-03-01T18:28:53.013Z
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.
Noah Witherspoon
<algorithm><computational-geometry><geometry><mesh>
Existing method to automatically fill in this sort of concavity in meshes?
FilmCoder
# Existing method to automatically fill in this sort of concavity in meshes?

(Asked by: username_0 on 2021-02-27)

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](https://i.sstatic.net/ZgizM.png)](https://i.sstatic.net/ZgizM.png)

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](https://i.sstatic.net/Cg6p5.png)](https://i.sstatic.net/Cg6p5.png)

**Tags:** algorithm, computational-geometry, geometry, mesh

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2021-03-02. Score: 4

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](https://en.wikipedia.org/wiki/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 (other than the [2D version](https://github.com/cm-1/2D-External-Visual-Hulls)).

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](https://www.researchgate.net/publication/3192242_The_Visual_Hull_Concept_for_Silhouette-Based_Image_Understanding), download [2] from ResearchGate [here](https://www.researchgate.net/publication/2781058_A_Computational_Geometric_Approach_To_Visual_Hulls) (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.


---

