Calculating Approximately Uniform Positions Across a Mesh's Surface.

Can anybody recommend any algorithms that might be partially (or perhaps even entirely,) geared towards the following use scenario:

You input something like the following:


Out comes something like this (excuse the crudeness, the distance between points should appear approximately equal):


Additional parameters could have something to do with minimum/maximum distance between points, or how many points should be spread across the surface (I would imagine farther down the road, some sort of random distribution would be useful).

 

I needed to procedurally generate a plane mesh similar to this recently. It needed equal spaced distance points inside the mesh too. Are you trying to get them in equal rows/columns with a margin between them, or are you after them being randomly spaced out, but at equal distance? Also what you're doing with it can make a difference on my suggestions for you.

 

The idea is to use this method to distribute bits of vegetation like tufts of grass and flowers into areas of varied size.
First and foremost, I would like something that allows me to quickly fill an area, and ideally on top of that, allow me to add a bit of randomness to the placement to break the pattern a bit.

The simplest form I had pictured, would be a way to first distribute points equally without randomness, and then offset every position by a little bit of randomness (nothing smart at first: I'd have to manually make sure the offset isn't too big).

My dream solution would be something that lets me configure not only distribution density of points, but also lets me tune the ratio of objects to be spread across the surface and how they are distributed internally (0.1 blue flowers, 0.5 yellow flowers, 0.4 grass, minimum distance between types etc). But I figure I'd start by figuring an even distribution method out first.

 

Also, I figured I'd limit myself to completely flat surfaces at first, in case that factors into the complexity.

 

Here's an example close to what I might be using. The green area would be evenly (ish) filled with grass.

 

You want to look at a Poisson disk sampling algorithm. https://www.jasondavies.com/poisson-disc/

 

Interesting. Maybe the simplest form I described could be combined with that method applied to a simple plane (serving as the bounds of the input), and then something that checks whether the points generated are inside the input area. Pretty bruteforce, but seems like a decent enough start.

 

I'm not sure whether it's good advice for you, but things like Gaia from the asset store place prefabs of set arrangements of plants as well as individual plants. So it can look 'semi-arranged', like how some plants are associated with each other and can be found in bunches, ect. Just a random thought for the future.

 

Anything helps, I didn't know about that tool. It looks really nice. Personally I'm more inclined towards combining many small solutions and doing so myself. I've found large toolkits of the sort a bit bothersome if I want to be able to control how they both function in the editor and at runtime. Often it's all a bit glued together and you have to take what you get.
But it factors in that the types of project I work on make it difficult to argue for the inclusion of large third party assets for maintenance and documentation reasons, or so I've found at least. I could definitely see myself relying on them in other cases.

 

Nah I'm in the same boat as you. My angle is when people have spent a long time developing a system similar to what you're making, it can be a good idea to see some of the features they have and see if there's any easy wins or good ideas.

 

That's a reasonable philosophy, yes. Even if you don't use the tool, you can try to understand what methods they're using, and if they can't do what you need, why that is, whether it's technically limited or absent by design.

I would also add, regardless of their potential usefulness, I tend to throw tools out of my projects out of principle if I discover that they're bogging down the editor needlessly (poorly designed editor interface, throwing its weight around even when you're not using the tool). But that's just me.

 

A bit of pruning is always nice

 

If anyone is also wondering about procedural spawning inside rect bounds, I stumbled onto this nice tutorial on poisson disc sampling:

(source code and more stuff by the author are linked in the video description)

 

Here are the test scripts I'm using with the tutorial code from the video.

For generating points inside a rect:

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3. using UnityEngine;
4. using UnityEngine.Events;
5.  
6. internal class PoissonRectDistribution : MonoBehaviour
7. {
8.     public Vector2 areaSize = Vector2.one;
9.     public float radius = 1;
10.     public int rejectionSamples = 30;
11.  
12.     public void DoDistribution()
13.     {
14.         _onResult.Invoke(PoissonDiscSampling.GeneratePoints(radius, areaSize, rejectionSamples));
15.     }
16.  
17.     [Serializable] private class PointResultEvent : UnityEvent<List<Vector2>>{}
18.     [SerializeField] private PointResultEvent _onResult = null;
19. }

For translating 2D points to 3D.

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3. using UnityEngine;
4. using UnityEngine.Events;
5.  
6. internal class Translate2DPoints : MonoBehaviour
7. {
8.     public void Translate(List<Vector2> points)
9.     {
10.         _onResult.Invoke(Calculate(points));
11.     }
12.  
13.     [Serializable] private class PointResultEvent : UnityEvent<Vector3[]>{}
14.     [SerializeField] private PointResultEvent _onResult = null;
15.  
16.     private Vector3[] Calculate(List<Vector2> points)
17.     {
18.         var translatedPoints = new Vector3[points.Count];
19.         for(int i = 0; i < points.Count; i++) { translatedPoints[i] = new Vector3(points[i].x, 0, points[i].y); }
20.         return translatedPoints;
21.     }
22. }

For spawning objects:

Code (CSharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using UnityEngine;
4.  
5. internal class TestSpawn : MonoBehaviour
6. {
7.     public GameObject prefab = null;
8.     public void DoSpawn (Vector3[] positions)
9.     {
10.         foreach(var p in positions)
11.         {
12.             var g = Instantiate(prefab, p, Quaternion.identity);
13.             g.SetActive(true);
14.         }
15.     }
16. }
17.  

(Note: that "On Unity Event" script basically just calls something on Awake, Start, Update etc.)

 

Oh that's lovely, I might use this. Thanks.

 

For posterity, here's how the bruteforce method I was pondering looks like when applied on top (checking if every single generated point is inside a 2D polygon and discarding those outside).