Interior Volume Detection

Given a piece of geometry - typically the exterior of a building - I need to be able to generate a shape that represents it's interior volume.

Sounds like you want something like a low poly occlusion mesh?

Simplygon can generate this, but i have not tried yet: https://simplygon.com/#get

Your algorithm may work depending on your needs and inputs.

Other ideas:

* Voxelization + flood filling

* BSP tree for exact solution

Hey JoelJ

Yeah a low-poly occlusion mesh is exactly what I'm after; a bounding volume that can trigger audio events when a player enters an indoor area.

I'll have a look at simplygon, see if I can get something up and running.

Voxelization is an awesome idea, and should be relatively easy to implement, thanks for that. I'll have to look in to BSP trees as well.

Thanks!

On 6/9/2017 at 3:36 PM, JoeJ said:

Given a piece of geometry - typically the exterior of a building - I need to be able to generate a shape that represents it's interior volume.

Sounds like you want something like a low poly occlusion mesh?

Simplygon can generate this, but i have not tried yet: https://simplygon.com/#get

Your algorithm may work depending on your needs and inputs.

Other ideas:

* Voxelization + flood filling

* BSP tree for exact solution

Hey JoeJ

I've been having a play with a couple of the ideas you suggested, and while the voxel flood fill seems to work quite well (although expensive) I'm not sure how to go about evaluating space with a BSP tree.

I've been able to build a BSP tree of course, but I don't see how to extract the spatial information from it since it only really storing the relationship between individual polygons... if that makes sense I've read that you can represent the empty space using something called a solid-leaf BSP tree, but can't find any descriptions of the algorithm, just that it exists.

Cheers!

You can use a BSP to seperate solid from empty space if the leafs of the tree contain convex polyhedra, which are either all solid or all empty. IIRC Quake used empty leafs, so if you are in a cube like room it's likely all wall that you see are the surface of a single leaf node (though there may be some splits dividing the room into two or more volumes). If there is a door to another room, the empty volume inside the door is another leaf, and the other rooms walls form another leaf as well.

There are some chapters about BSP in Quake / Doom here: http://www.jagregory.com/abrash-black-book/

The faces of the door volume are invisible but still there. They connect one empty space to another - those faces ar often referred as portals and have been used to precompute a PVS to get a list of potential visible leafs from the camara leaf.

See for the nightmare of implementation - you should njot need this, but just to give you a hint on complexity: http://www.cs.utah.edu/~jsnider/SeniorProj/BSP/default.htm

So for you it might be better to store solid instead empy leafs. The algorithm would help to find a single fused mesh from multiple models that build up your world, and from that you could use a polygon reduction algorithm to get a low poly version. Or you can reduce the BSP itself (e.g. remove the few small leafs that from a football in a stadium).

Also low poly BSPs are very good to ray trace (should be much faster than voxels), if you want it to trace sound rays around in real time.

BSPs are often used for boolean CSG mesh opartions (union, subtract, intersection), maybe a good search term as well.

But it's really the last option - it will drive you crazy to do this robustly for the detailed stuff we use in actual games. I guess you have to invest so much time, building low poly meshes by artists might be cheaper

So if voxels do it, why is performance an issue? Do you want to do this in real time? Generating BSP in real time is no option. BSP can handle details at any scale and are exact, but that's the only advantage over easy voxels and this should not be necessary for sound.

Edit: Did you try Simplygon? I did not find the occlusion mesh generation in the tool, also i did not find the SDK after installation, but this stuff should be there.

Hey JoeJ,

Thanks for the awesome response

The purpose of this is to automate the placement of sound occlusion volumes in the world, so a completely robust solution isn't necessary. I'm just trying to cut down the manual, repetitive work that sound designers have to do in our level editor.

Performance isn't really an issue since this is all going to be done in an offline process, and while the voxel solution is working well so far it is by no means complete... just trying to cover all of my bases here

I haven't tried Simplygon, but I have been looking at Recast - an open source navmesh generation system. It seems to do a really good job mapping out mesh interiors.

Recast works by voxelization and then producing some low poly navmesh?

Do you think this might work for low poly occluders as well?

That's what i'm looking for: A single double sided polygon for each wall

Haven't figured out exactly how recast works yet, but it can output voxels for walkable surfaces it detects. The code is reasonably well documented too.

I was half thinking I could grab it's interior edge detection algorithm to walk around the interiors of the geometry I'm looking at... then just extend the resulting mesh to the desired height.

It's an impressive piece of tech; very quick generation and handles things like stairs without any trouble.

https://github.com/recastnavigation/recastnavigation