- Home /
Random position inside Mesh
Hey guys,
I'm trying to get a random point inside of a mesh. At the moment, my plan is to calculate a random point on a random triangle, and cast a ray inside the mesh (in the opposite direction of the normal). This gives me the distance to the opposite side of the mesh, which I can use to calculate a random Point along the ray. This idea has 3 problems though. Firstly I can't cast a ray against a mesh without a collider, secondly I generally can't cast a ray against the inner side of a mesh, even if it would have a collider, and thirdly the random point wouldn't be distributed uniformly, as some parts of the mesh may have more triangles then others. Another idea would be to generate random points inside of certain bounds, and check whether or not it is inside of the mesh. This may be quite a lot slower than the idea above, and additionally I have no real idea how to determine whether my point is inside of the mesh without using raycasting (which I can't use because of the points above).
Am I missing something obvious? How can I calculate a random point inside of a mesh? Is there another actually doable way to achieve this? Is there a way to fix my problems?
Thank you for every answer!
It's just so obvious - I can't believe didn't think of this yesterday. Be sure to read my correction in the answer before you program anything $$anonymous$$aul! Cheers!!
Answer by Fattie · Aug 05, 2012 at 07:28 AM
The whole thing dramatically depends on the shape you are dealing with. Does it fold back on itself? Based on everything you have said, it appears you are dealing with a simple convex shape that never folds back on itself.
So, for a "simple and reasonable" shape, you very simply do this:
Just pick two points on the surface, and then pick a random point between that line.
IT'S SO DAMN OBVIOUS!!! DOH!!...
Just pick ONE point on the surface, and, the center. Doh!
For a random point on the surface, just use one of the vertices. So in 99% of use cases you can very easily get a "random point inside the object" with a ilne of code..
RPIO = randompointalongline( vertices(random), the center )
It's that simple.
Some points:
The position of the "center" just doesn't matter much. Ue an empty object as a marker, place it centrally using your eye, and call it "NominalCenter" and use that.
Do not ever use the method mentioned yesterday of two points on the surface. That is wrong. It's a bad idea for a number of reasons, and it is wrong.
A neat touch: Note that these points are of course distributed along lines from the verts. If you need more randomness: It is inconceivable you will need more randomness for a video game, so just in theory: if you need more randomness, don't try to move the random-vert. Just move the nominalCenter randomly! Pretty huh? So the "pointless more random" formula is:
jiggledCenter = nominalCenter but move it randomly by 10% of the size of the object
RPIO = randompointalongline( vertices(random), jiggledCenter )
3b. You can always safely jiggle the nominalCenter, whereas you can't always safely or easily jiggle either the vert point or the result point. So this is the perfect incredibly pretty solution. Once again, in avideo game, it is inconceivable you'd need to do this. The solution "random point along line from random vert to nominal center" will always give you perfectly wonderful RPIOs for your video game. BTW regarding the "10%", just any distance about the typical gap between your verts. In fact, in Unity simply define a cube in the middle of the object and use "random point in cube" to get that jiggled-nominal-center-point.
if you're wondering "how simple" does the object have to be. Obviously, it just comes down to this: you have to have a line of sight from everywhere on the surface, to, the nominalCenter. As long as that is true, you can use this method. Indeed, for jiggly shapes, you can even use that to decide where to sit the nominalCenter. Note that this is one of a number of reasons you should never use the two-points-on-surface system: in TPOAS it is much easier to stumble on a line that crosses the surface - TPOAS was just a bad idea, sorry I mentioned it.
For future readers. Following were some general comments on randomness:
BTW Maul I've just noticed you wrote this "thirdly the random point wouldn't be distributed uniformly, as some parts of the mesh may have more triangles then others".
In a sense, "that is wrong" fortunately. A number of issues arise:
If the inequality in distribution of tris is MODEST, it's actually NOT immediately apparent that it would affect the distribution of the randomness badly. randomness distribution is a tricky thing as you know. If you simply add (for God's sake) two random numbers, you do not get a new random number. (You get a new distribution - not "random" as humans normally mean the word.) Note that in any event: it's impossible to have verts themselves perfectly evenly distributed on a surface generally speaking, so if you were actually going to worry about the fact that there were a few more triangles in one area, it would be pointless worrying about that since the verts aren't perfectly distributed anyway. So we can say that if the tris are reasonably distributed (like on any model ever in any video game ever) you have no concern
say your model is, for some reason, incredibly clumpy in one area. then --- change the model. if you have a spectacularly simple solution that has the requirement: "this works perfectly, but it does not work well for ridiculously clumpy models" -- then just look at the model, and if it's wildly clumpy somewhere just send it back to the art depertment explaining that for technical reason you can't have a widly clumpy model
Note that: if you're going to get in to the mathematical underpinnings of the question. it's just not clear at all if it is the case that: random points along random lines in an object, lead to random points in the object. I wouldn't bet that leads definitively to an even distribution of random points, in a hard-core mathematical sense. For video games, yes it's perfect. HOWEVER...
Having said "it's perfect" there's a big problem, because we know nothing about your use case! The last time I had to do this, IN FACT, it turned out that having them evenly distrubuted inside the object was useless. the human hand-eye just doesn't work like that. In practice, you needed them random, and, "not too close to the surfaces". So that changes the whole thing too.
Phew! Fortunately writing these long answers is my thinking time! :)
That would definitely work with convex shapes, but it wouldn't work for concave shapes. The random point on the line can be
var randomPoint = Vector3.Lerp (point1, point2, Random.value);
For sure Eric, that's why it says (in BOLD typography) .... IF the shape is "reasonable" ...
Pls see my philosophical comments on how you simply can't address this question until he tells more about the domain of the problem.
(Sure, there's a general sort of scientific solution, but that's useless for video game programmers, we need fast clever solutions that work most days!)
I like your overall idea, especially since it's pretty fast to calculate.
Talking about the distribution of random points, you are totally right there! It was quite late when I wrote the question (it really bothered me the whole night that I was unable to find a reasonable soloution), and while I was writing the question, I suddenly thought about the triangledistribution, and being a mathematician, the resulting "random distribution" was totally unacceptable to me :) In a video game however, you are totally right and, as you said, it's perfect :) Thank you a lot for all your comments!
Well, your 2 points solution is exactly what I was looking for. I know that it's 100% enough for a video game, my brain was just unable to accept that last night :) I just was unable to find an exact way to do it, but as you said, it's not needed to be that accurate.
Answer by Anisoropos · Dec 16, 2015 at 06:46 PM
I ran into the same problem today and solved it by implementing and extending the method described here.
You can view the results in this video and download the asset (don't be shy, it's free :)).
Thanks for this, you did a great job explaining the logic in your comments and ultimately your version produced the best distribution for me (compared to suggestions elsewhere).
Can you explain or post the code somewhere else? When i download i get a .gz file filled with maps with assets.file inside...
I am not sure what file you are downloading. The asset posted by Anisoropos is a .unitypakage hosted on Google drive. Download the entire file and then open it with unity, or launch unity and import the package. It includes a demo scene as pictured above. The actual code implementing the solution is the script that adds methods to the mesh class.
Answer by Bryan-Legend · Jan 26, 2020 at 03:15 AM
Here's how I did this.
Vector3 result;
do {
result = new Vector3(
UnityEngine.Random.Range(collider.bounds.min.x + margin, collider.bounds.max.x - margin),
collider.bounds.center.y,
UnityEngine.Random.Range(collider.bounds.min.z + margin, collider.bounds.max.z - margin)
);
} while (!IsInside(collider, result));
// https://answers.unity.com/questions/40996/check-if-position-is-inside-a-collider.html
public static bool IsInside(Collider c, Vector3 point)
{
var closest = c.ClosestPoint(point);
// Because closest=point if point is inside - not clear from docs I feel
return closest == point;
}
Answer by Eric5h5 · Aug 05, 2012 at 03:26 AM
What I would probably do is first make a new list of Vector3s. Then loop through a 3D grid of points, where the size of the grid is the bounds of the mesh. (The density of the grid would be up to you.) For each point, check to see if it's inside the mesh. If so, add it to the list; if not, skip to the next point. This way you end up with a list of points that's inside the mesh, so you can simply pick randomly from this list.
However, if getting the random point inside a mesh is just a one-shot deal, it may be more efficient to pick a random point inside the mesh bounds and do the "point inside mesh" test, repeating with new random points if necessary until it succeeds.
The only part that's a bit tricky is the "check if a point is inside the mesh" bit, but that can be done by looping through all the triangles in the mesh and comparing the point against each one: if the point is on the "inside" of them all, then it's inside the mesh volume. Comparing a point to a triangle to see what side it's on isn't Unity-specific and it's pretty simple to find various resources for algorithms to do this, such as this page.
Just FTR. Looking at Eric's first system, which is to compute a list of points inside the object at development time. Let's say you do that, and for clarity we'll say each point is one inch apart.
Now, if for some incredibly bizarre reason at run-time you need $$anonymous$$ORE granularity than that: Essentially, take two adjacent points (preferably diagonally adjacent) and pick a random point between those two points.
{Sorry for the edit - I've realised it makes two emails appear. By adjacent I mean preferably diagonally adjacent - of course! :) }
Assu$$anonymous$$g that you are not dealing with any incredibly bizarre shapes, that will give you a further solution.
{Indeed you can pick a random point between any random two of the precomputed points, but also see my answer, for that matter.}
Just a re$$anonymous$$der that it is all-but impossible you would need more randomness in a video game, the system Eric describes in the first paragraph should serve perfectly.
Ok, time to write lots of comments (Sorry about all the e-mails). I really like the system Eric described at his first paragraph, and this is probably what I will be using. Thank you for that!
Answer by danieldownes · Mar 21 at 10:00 AM
None of the above code samples work well as do not consider the size of each triangle.
You'll need to get total area of each triangle, then find a random point within that area, then lookup which triangle that point relates to, and then which point in the triangle that random point refers to.
This works for all mesh types, and gives fully distributed results.
Code here:
https://gist.github.com/danieldownes/b1c9bab09cce013cc30a4198bfeda0aa
Well, yours doesn't work either since you pick a point on fht surface of a mesh, not inside it which was the question. Though Bryan-Legend's version does work fine and has a uniform distribution inside the mesh. However for meshes which have a bad mesh volume to bounds volume ratio it's kinda expensive as the average tries would go up.
Your method does work for picking a point on the surface of a mesh. A similar approach can be used for the actual problem by splitting the whole mesh into tetrehedrons. Calculate the volume of each tetrehedron, pick one of the tetrahedron and then pick a random point inside that.
Note that you're solution for a point on the surface doesn't require the "cumulativeSizes" array at all. You just need the total area and the sizes array. When you rolled your random number you simply subtract the size if the current triangle. If the value is equal or less than 0 you have found your triangle index. So it would simply be:
int triIndex = -1;
for (int i = 0; i < sizes.Length; i++)
{
randomsample -= sizes[i];
if (randomsample <= 0)
{
triIndex = i;
break;
}
}
You also could calculate the total area as you create your sizes array and use an out parameter to pass back your total area. Also you could cut the memory allocation by 4 by simply caching mesh.triangles
and mesh.vertices
in a local variable. Those are properties which create a new array each time you read them because they are reading the data from the native C++ side so it has to create a new managed array each time.
Another optimisation if you need to use this method a lot would be to precalculate the sizes array once for a mesh abd keep the vertices and triangles array. It's also always a good idea to make pure utility methods static. This makes it much clearer that all required information is passed through the arguments.
Your answer
Follow this Question
Related Questions
Why is raycast not working with mesh collider 0 Answers
Rendering part of the mesh 0 Answers
Mesh Collider Issue(?) - Raycast (ScreenPointToRay) Appears to Collide on Nothing 0 Answers
Detecting the subobject of a mesh 1 Answer
Are tag settings passed down from Game Object parent to mesh child? 1 Answer