Finding a free point to place a mesh

Questions
1

The essence of the problem: there are a lot of objects on the scene, I need to place the object at a random point inside a certain zone so that the objects do not intersect with other objects

I have a scale of all meshes and their positions, I know how to do it all in principle, but recently I learned about raycast and

const intersects = this.raycaster.intersectObjects([
scene,
…scene.children
]);

Do you have any working example with raycaster?

That is, if very briefly: I need to put the object at a random point inside the zone so that the object does not intersect with other objects

2

This topic is fantastic, thanks for bringing that up. :raised_hands:

At some point in your implementation, you will be performing collision detection test against an ordered list of candidates locations. This part can be calculated in (close enough to) real-time. But before that, you need to pre-calculate (off-line) the overall region of interest into smaller chunks of space. Now, depending on your specific use case, you may want to pick one among different approaches:

  • Space partitioning. Golden bullet is to use a BSP/octree as a base for keep track of unused space, that can be queried on-line for an specific leaf size, which in turn correspond to the bounding volume size of the object you want to allocate. Pre-calculation here is building/populating the octree, good news is that they are very efficient at this and can even be computed again if the scene is not static (to a certain extent, obviously).

  • An inverted approach would be to treat the unused space like a big concave 3d object. In that case, off-line computation has to deal with i) obtaining the geometry (someone did this using marching cubes), and ii) measuring the object ‘thickness’ (you can approximate this inverting the face normals and calculating the AO term).

  • There are other smart/crazy ideas floating around, most of them are related to represent/store space in alternative formats, like this clever one.

Regarding the collision detection itself, generally you will be safe using Axis-Aligned Bounding Box tests, or leveraging the costly Separating Axis Theorem for special cases (like convex-convex). For performance reasons, it is suggested that you split collision detection in two phases, a broad one for discarting low-value candidates, and a narrow one, to go precise.

If you have jumped into actually writing code you can share your progress here :muscle:

1 Like
3

Maybe checking boundingbox intersections