Poisson Disk Sampling - Blueprint implementation - Feedback welcomed

Hi, Community!

this is my first post, hopefully not the last!
I’ve been fiddling around with Unreal for almost an year now and I’ve been lurking the foruns, IRC, reddit, etc.
I’ve been working on a personal project Forsaken Void that we’ve started on Unity but then due to some limitations we switched to UE and so we had to start from the 0 (in terms of gameplay, implementation, etc)

Why am I creating this thread?
Well… I’m finally doing something that I’m beginning to be proud-of and by the title you’ve guessed it right!

It is a Poisson Disk sampling algorithm as seen on bl.ocks’s implementation and visualization.
Right now it is sampling points inside a 3D cube.

There are a few features that I would like to implement further down the road:

  • Dimension Independent - Be able to sample over a 1D, 2D, 3D, 4D space
  • Constraint checker - Defining some predefined areas that no points should exist
  • Any shape, not only inside a box

This Poisson Sampler is Blueprint only! (at least for now) I’m trying to squeeze the most out of it in order to understand what it can or can’t do.
I’ve finished my first implementation but it was a brute-force implementation and now I’m implementing according to Bridson’s implementation.
My first approach was able to produce 10k samples in under 0.2 seconds, but there were some issues and so that benchmark might not be correct.

I’m using this sampler to create an asteroid field that seems overwhelmingly big and “somewhat” natural\uniform for the player.

With the output from the Poisson Sampling I’m using it to feed the static mesh creation, but right now I can only achieve the 10k instances only with the hierarchical instanced static mesh, with all that entails.
Using some of the tips found at Map Generator thread by Zeustiak I intend to have two sets of asteroids an hierachical instanciated and one of dynamic meshs.

What do you feel about this?
Anything I’m doing wrong?
Do you feel it will be used by the community?
Was it done already? (I didn’t found anything related to it, but sure there are some C++ implementations UE4-unrelated but that could be used nonetheless and I intend to use that as an benchmark)

As soon as I get to finish it I will post it into next post (a screenshot and\or the uasset) and eventually unto Git (right now it is on my private rep.) I hope to post it sometime around this weekend.

Hope to hear some critiques\feedback from you!


Here are the blueprint functions:

Hard to give you any advice since you haven’t yet shown much, but it sounds like things should work pretty well once you get them implemented. :slight_smile:

By dynamic mesh, you mean static meshes or something else? I am assuming these will spawn in when you get close enough to interact with an asteroid?

Have you thought about using a grid and randomly offsetting the vector for each point? What kind of advantages does Poisson have over that for your use case?

Hi Zeustiak, thank you for your time!

First of all, I took sometime to take the screenshot of the BP!
Is there already an easy way to share BP screenshots?

By dynamic mesh I did wanted to mean Static Meshes with Mobility set to movable.

That would be the idea yes. So I would be swapping the “static\hierarchical” asteroid with the movable one (so that physics\etc can kick in)

Could you please elaborate more on this idea? :o
Do you mean to generate the Asteroids on runtime as the player “moves” around?

Well the “thing” about poisson is that, first of all it started as an concrete to-do objective :P, but with the idea that the distribution of the asteroids wouldn’t be that chaotic.
Each asteroid would be at least at a given distance from each other.
When I tried the brute-force implementation it really got interesting, just moving around the asteroid field and dodging the asteroids.
A purely random implementation would give patches of areas condensed with asteroids (with some collision between them) and patches without asteroids.

I would generate this region of asteroids only at load time, between playable-areas or based on distance to the player.

The implementation I gave in my first post, it takes 0.3s to generate 8k instances. Over 8k I’m hitting the blueprint loop iterations limit and I need to optimize this a little and, eventually, split the loop over several loops (as mentioned in some other posts pointing to some work done by Rama’s, which I didn’t found) even you Zeustiak mentioned that problem.

There is a lot of space for improvement.
There is always the possibility of me being overthinking\overdoing something that could be hellishly simpler than I’m making it to be.

I use photobucket, but there are other hosting sites as well.

Create a plain square(or cube) grid of vectors, and then for each vector randomly offset it by some amount in any given direction. You will probably want this offset to be somewhat less than the distance between points on the grid. Then, you could also label certain grid points as off limits for asteroids to create large gaps in the field.

You could probably even do mini-poisson sampling on top of the grid by spawning a handful of asteroids centered on each of the grid points and doing the sampling only with those asteroids. You may not need the additional sampling, but it depends on how the first step works for you.

You went into the project settings>general settings and increased the loop limit to the max of ~2 billion right? If so, then I am assuming you are hitting the loop limit because there is a lot of “wasted” resampling of the same node points over and over. I have a similar problem with my river right now, where a river flows out, finds itself trapped in a corner, and then the whole thing is dumped and restarted. If you use a random offset grid, then you should have much fewer wasted iterations.