Hi, I’ve recently began researching about how I’d achieve determining the volume of said space size at a specific location in real-time. I’ve ended up getting pretty lost about figuring a efficient solution towards this, I suppose some form of convex hull algorithm in tandem with raycasting is required for figuring this out?
Use cases would be something such as real-time dynamic sound propagation or custom dynamic lighting features which applies in-doors or out-doors in the game world.
This problem has kept me really thinking and I’ve still yet to figure this out, I’d appreciate anyone giving a proper guide for this.
For anyone going to post a paper from some other external source, please be reminded that this is to be done on Roblox, and that performance heavy solutions are something I’m not going for.
Edit :
It’s silly that I have to also mention but this must apply for figuring the rough estimate area volume of a room that could come in any size or shape.
It’d be more helpful if you described the actual use case you need this for. The more specific the better, because there’s a million ways of interpreting “determine volume of space via raycasts”.
You need the length, width and height.
L * W * H = area
You can have it raycast from center. To the up vector, right vector and look vector. Then take each value*2 since it’s in the center. The apply the formula above.
Six rays being casted aren’t going to help in a actual scenario with a detailed map, try figuring this out for a non-box shaped room and there’s your problem.
You would have to cast a lot of points to map out the room. In a 360 degree rotation. Then create shapes according to the points then calculate the area of each shape. Shapes have to be within the inside of all points. The more points created the more accurate. Sound like it will create a lot of lag
Do you need exact-ish answers or are estimates fine? What format is your volume data in? E.g. do you have mesh data or just parts?
Anyway, there’s the good old grade school method for estimating the area of a shape by counting how many cells of a grid the volume overlaps and multiplying by the area of a cell. Same idea works for volume. Smaller grid = better estimate. It depends on being able to determine if a point is inside or outside the shape.
The raycast idea could work, but you’d have to cast rays from many different points, not just the centroid - or any single point for that matter - to deal with concavity, like you mentioned. If you find points on the surface of the shape you could use those as additional points to raycast from. This has the disadvantage that if there’s a small-ish “tunnel” from one part of the shape to another it might be completely missed, so there isn’t really any bound on the amount of error. In the worst cast you’d start in a tiny part and miss most of the shape.
The best way is definitely if you have the mesh data for the shape, that way you can calculate the exact volume. There’s a paper (http://chenlab.ece.cornell.edu/Publication/Cha/icip01_Cha.pdf) linked to from here that describes a really simple and pretty fast algorithm for mesh volumes. Ask away if you find parts of it difficult
As for making it fast enough to work in real time, how static are your environments? If they’re mostly or completely static, it might make sense to compute some things ahead of time.
Can you visualize it for us? You said a 50x50 stud room so I’m guessing you’re trying to hit an object inside the room and find its volume? Is that it? Or the volume of all the objects in the room? I’m also not super clear on what you’re trying to figure out…
