Assignment Goals

The primary goals of this assignment are:

  1. Create a UE5 Plugin.
  2. Extend the Blueprint system.
  3. Create and use a blue noise point distribution

For this assignment, you'll be creating a new Blueprint node and data type in a UE5 plugin. In this case, we'll create a new Blueprint type to hold data about a blue noise point distribution generated using Mitchell's best candidate algorithm. You'll also create a native make function for this type, and a blueprint node to return a point location from it.

Objects distributed using true random numbers will tend to be clumpy because each position is independent of all of the ones before, so has no memory that another object has been placed nearby or that there is an unfilled gap. A blue noise distribution spaces has correlation between the point placements to make them more even in density, To summarize Mitchell's algorithm, you first place one point at a random x/y location. At each step, select several candidate points and keep the one furthest from any already placed points. You should use distance calculations that wrap around from left to right and top to bottom so the distribution will tile and to avoid a preference for point locations along the edges.

The linked page suggests choosing a set of candidate points at each iteration proportional to the number of points placed so far. If you naively loop through all of the already placed points to find the distances for each candidate, the resulting algorithm to generate N points will run in O(N3) time

Randomly placed trees Blue-noise-distributed trees
Randomly distributed objects Blue-noise distributed objects

Details

For this assignment, I've gone a bit more general with the steps than in other assignments so far, though I have given some pointers for where to find examples of code similar to what you will need to write.

Create a project

  1. Create a Blank C++ project with no starter content called assn4, and a level called assn4 set as your default editor level.
    • As usual, put the project at the top level of your git repository

Create a Blueprint test case

  1. Create a Blueprint actor to spawn models with random positions and rotations within a square.
  2. Your Blueprint should have four variables: an integer random seed, a number of elements to spawn, and two hidden RandomStream variables (one for positions and one for rotation).
    • When you create a variable, you can change its type in the drop down next to the variable name in the variables list, or the type, allowable range and other attributes in the details panel on the right
    • Click the closed eye icon next to the variable name in the variable list to make it visible in the editor details window. Otherwise, it is considered a hidden local variable.
  3. The screenshot below shows a working Construction script actor Blueprint to do the random placement. Recreate this Blueprint or something similar.
    • Initialize the random stream for position given the seed. We are not seeding the rotation stream, so it'll always be initialized with a seed of 0, but being able to re-seed the positions is more important to create different but reproducable distributions.
    • Add an InstancedStaticMeshComponent
      • In the detail panel for this node, you can choose any static mesh and material you want, either one already available or by making something new
      • I used the SimplePivotPainterExample mesh, which is a bare tree, though any other mesh could work
    • Loop for the number of elements
    • On each iteration, create a transform using the position random stream for X/Y, and the rotation random stream for orientation.
    • Use AddInstance to add a copy at that location
    • Note that you can clean up the connections a little by double-clicking on any connection line when it is highlighted to create a reroute node. These appear as a little dot along the connection path, and allows some control over the paths of long connections. In the example here, there are two on the white path between "Add Instanced Static Mesh" and "For Loop".

Blueprint for random distribution

Create a Blueprint plugin

  1. In Edit > Plugins, create a new Blueprint plugin
  2. Once loaded, you can recompile and hot-reload from Tools > Debug > Modules > (find your plugin in the list) > Recompile
    • The editor toolbar "Compile" button only does "game module" code (actors and components), not plugins!

Create Blueprint nodes and data

  1. Make a Blueprint type to hold a random stream object, the range for the generated points, and set of generated 2D point locations
    • Look for things tagged USTRUCT(BlueprintType) for examples of Blueprint-accessible types
    • KismetMathLibrary has some of the simpler examples.
  2. Make Blueprint native make node to initialize that type from a random seed and the min and max bounds
    • Look for examples of the USTRUCT side of this with HasNativeMake
    • Look for examples of the UFUNCTION side of this with NativeMakeFunc
  3. Make a Blueprint node to generate a new point from the stream
    • To get something working and testable quickly, you can just return a random position (equivalent to the first Blueprint) before you do the full blue noise algorithm.

Blueprint test case

  1. Make a copy of your existing Blueprint test class
  2. Modify it to use your new blue noise type instead of RandomStream for the position.
    • This should look similar to the image below (yours does not need to be exactly identical to this).
    • Note that any time the type or blueprint node signatures change, you will probably have to delete and recreate the portions of the blueprint network that use them. Implentation changes in the C++ will should work without updating the blueprint

Blueprint for blue noise distribution

Mitchell's Best-candidate Algorithm

  1. Implement Mitchell's best-candidate algorithm in your Blueprint node.
  2. If N points have been generated so far, your node should try at least 5N candidate points, and return the one farthest from any already placed point.

Grad Students

Use some data structure to make the point distance queries faster (for the undergrad version of the assignment, you can just do a linear search through all of the already-placed points). A few options include a uniform grid (with re-binning as the number of points grows), a quad tree, a K-D tree, or a BSP tree.

Submission

As always, for full credit, you must have multiple incremental commits during your development.

Add an assn4.txt. Tell us what works and what doesn't, and anything else you think we should know for grading.

Include a few representative screen shots showing different numbers of spawned objects with both the random and blue noise distributions.

Push to your github, and tag your final commit with an assn4 tag (git tag assn4 followed by git push origin assn4).