0
\$\begingroup\$

Is it possible to automatically detect walls in polygon soup?

Of course it's hard to strictly define what a wall is, my slightly vague definition would be:

A wall is a largest possible box (not necessarily axis-aligned) with its entire volume covered by subset of geometry in that polygon set.

Provided set of polygons may contain multiple walls, walls under specific low volume should be ignored, walls may overlap if it's easier for the algorithm, subset of geometry used to construct a wall may have larger volume than the wall itself, but opposite is not allowed.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ "Is it possible" - let's say the answer is "yes" - does that answer your question? If not, then you're probably not concerned with possibility, but with how to do it. Try giving us a bit more context about the game feature you're trying to build using this detection algorithm - that will give us useful clues into what features we need to capture, and what kinds of approximations/shortcuts might be available/acceptable. \$\endgroup\$
    – DMGregory ♦
    Commented Jul 22, 2019 at 16:19
  • \$\begingroup\$ @DMGregory Well, I'm hoping there are some papers related to the subject that I could read, but don't know how exactly to find them myself - maybe someone in community could point me towards them or at least provide me with some better name of the problem, so I could search for them myself. \$\endgroup\$
    – zduny
    Commented Jul 22, 2019 at 18:41
  • 1
    \$\begingroup\$ Links to existing documents isn't really what our Q&A format here is best at. That's more of a search engine's wheelhouse. If you're having trouble finding the right keywords to search, or related work to research, asking in Game Development Chat can be a good way to gather informal suggestions. For a Q&A post, answers are expected to contain a reasonably complete solution, not just links to further reading, so defining your problem in more context & detail can help us suggest solutions to the concrete problem you're facing \$\endgroup\$
    – DMGregory ♦
    Commented Jul 22, 2019 at 19:00

2 Answers 2

Reset to default
0
\$\begingroup\$

I'd try:

  • Generate a BSP from the complete set of polygons.

  • Clip each polygon from the original set against the BSP. If the entire polygon is "inside" the tree, then it is completely covered and meets your definition of "wall."

BSP generation can be a bit taxing depending on the size and complexity of your input dataset. If you're not doing this real time, or if the data set is small-ish (a relative term on modern hardware), that shouldn't really be an issue.

You may be able to speed things up by checking each poly as its added to the tree. If the whole poly is clipped, mark it as a wall and leave it out of the tree.

Now, this assumes that the walls are already part of the input dataset. If that's not the case, and you need to generate a set of walls from the input data, that could also be handled via a BSP, but it'll be a bit more involved.

\$\endgroup\$
0
\$\begingroup\$

Is the mesh created by hand or computer-generated or scanned (i.e. contains noise)?

I was thinking that 3D scanning systems like http://structure.io and Microsoft HoloLense probably have to solve a similar problem when the scanned mesh is used in a 3D engine and allow "physical" interaction.

In Unity there is a Spatial Mapping Collider, but they don't really mention the concepts behind the collision detection.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .