How to place an object on the scene in a random position so that the object does not intersect with other objects?
Please give any working example
1 Like
Keep track of positions for previously added object. Before inserting new object, check its bounding area doesn’t intersect with other bounding boxes or spheres.
1 Like
You may look into poison disk sampling like this lib does. There are also various other methods, including distribution patterns that won’t need intersection checks at all with some restrictions. @prisoner849 also made a example with a distribution pattern.
The most simple you can do is iterating over a grid, randomly skipping steps and those steps you place a object you displace it randomly by a minor displacement not too far than the cell, ideally voronoi can help but will define the radius of space.
Poison disk might suit your case best but you didn’t further describe your scenario and usecase.
1 Like
THREE.MeshSurfaceSampler might also help with getting random positions on the surface of a mesh —
https://threejs.org/examples/?q=scatter#webgl_instancing_scatter
It doesn’t check for collisions, however, you’d need to do that part another way.
1 Like
Maybe I’m wrong, but as far as I know bounding boxes, besides only being axis aligned, they are just … boxes, so they won’t follow the actual geometry of the object or align with it in terms of rotations and such.
A more precise yet slightly more complicated (and probably more intensive, depending on geometries) approach to check intersections of arbitrary geometries would be to:
- iterate through the first object’s position attribute (i.e. the vertices) and construct Line3-s correspoding to the a, b, c sides of each face / triangle in the geometry
- iterate through the second object’s position attribute and create Triangles corresponding to its faces
- get the Planes corresponding to the second object’s triangles
- test if the planes for the second object intersect the lines for the first object
- if there is intersection, check if the said point belongs to the triangles for the second object
- if no intersection, safe to place the first object at its position in the scene; if intersection exists and also belongs to one of the second object triangles / faces, try another random position to place the first object
Again, this is kind of messy and not as straightforward as it should be since there’s no direct Triangle.intersectsLine() or Line3.intersectsTriangle() (although you can test if a raycaster Ray intersects a triangle easily, but rays are not finite as lines are), so it’s only suited if you absolutely need precision. Assuming a proper implementation via 2 major nested for loops, one handling the things related to the first object (aka the object to be placed), and the other the stuff related to the second object (which would itself be an interation over the already existing objects), this could work.
The main idea here is that if a side of a an object’s face intersects one of the faces of another object, then the two objects intersect as well. Considering every face is basically a triangle and each of its sides is a line, as far as I know, this more or less boils down to whether one object’s lines intersect the other object’s triangles.
I would say that considering the different suggestions you are receiving, it seems that you have stated the question in a rather vague way, so in order to narrow it you should define some aspects like:
- do you have access to a record of previous objects locations?
- it is allowed/expected to apply affine transformations to the new object (i.e. rotation, scale) to fit in?
- is the target area shape known in advance? Is it a plane/surface, maybe it follows a parametric function, or is it just void?
- do you need all posible locations that fit? Or a ordered list of the top 5 locations with more free space? or just any random position?
Consider defining these and/or other aspects; in that way your questions appear better defined, and you would get guidance on specific steps in your develpement. It is important that you tell not only the problem you are facing but also what you have tried so far, ideally with a editable demo so we can make scoped suggestions.
And please, if you don’t receive what you expected, don’t just start a new post with the same question. We are all trying our best to help eachother, if you do that answers get fragmented and so the chances that others in the future may get helped.
1 Like
I did the following, each object on the map added a zone that is slightly larger than the object itself
https://pastebin.com/jVPVK5a0
and
https://pastebin.com/TDf1CCJr
Then I send a request from the server to the clients in which I want to get a random point on the map and check if the object intersects with other objects using zones
It works, but I don’t like the implementation, there must be a smarter option
I just need to put an object on the stage so that this one does not intersect with other objects in size, this is an absolutely random point within mesh
this.mesh = new Mesh(
new BoxBufferGeometry(this.halfExtents.x * 2, this.halfExtents.y * 2, 3, 1, 1, 1),
new MeshBasicMaterial({ color: 0xff00ff, wireframe: true })
)
(this.mesh - separately created separately from all mesh zones, to just get a random point inside it)
If your objects are just untransformed (i.e not translated, rotated or scaled) cubes, like it appears from your 2nd pastebin link, a simple if in a for similar to how you wrote is enough, no need for “zones” or “halfExtends”. For an untransformed cube, a point is outside if its coordinates are not within the [leftsidex…rightsidex], [bottomsidey…topsidey], [farsidez…nearsidez] intervals. Since you want to check this not just for a point but for all the points inside the to-be-placed cube, you’d need to test if its similar intervals are outside the corresponding intervals of each of your already existing cubes.
If your objects can be transformed, are not necessarily cubes, and you don’t care too much about precision or accouting for every “empty volume” created around the object due to rotations, then using boundingBoxes and a method like Box3.intersectsBox() provide an easy way to test the possible intersections and decide accordingly.
If your objects can be transformed, are arbitrary and you do care about precision and accounting for every “empty space gap” after rotations, then I’m afraid a solution like I suggested above is one of the few available.
The alternatives, like others already pointed out, are more about smartly getting the needed values based on precomputed distributions where points (or positions, if you like) are more or less uniformly spaced (based on a given radius) while still giving the appearance of being random. Obviously, such alternatives do not account for the rotational gaps mentioned above either.
So, what you choose really depends on what objects you have in mind, how you want those objects to be placed, whether you apply constraints on the objects’ sizes, and so on.
The @ anidivr logic is the best way to approach this.
A simple collision function:
If the sum of boundingSphere radiuses is less than the distance, you are golden.