Mercurial

comparison mrjunejune/src/blog/optimizing-grass-rendering/index.md @ 100:65e5a5b89a4e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[Seobeo] Migrated everything to this page.
author June Park <parkjune1995@gmail.com>
date Sat, 03 Jan 2026 07:48:07 -0800
parents
children 7a4e942814bc
comparison
equal deleted inserted replaced
99:684edfaf93b7 100:65e5a5b89a4e
1 # Optimizing Random Placement with Colour Noise
2
3 ### Introduction
4
5 When it comes to placing objects like grass in a scene, achieving a balance between randomness and natural-looking distribution is a challenge. Too much randomness, like white noise, results in unnatural clustering or gaps. On the other hand, a completely uniform pattern can look artificial. Nature strikes a balance, often governed by constraints such as nutrient availability or environmental factors.
6
7 In this blog, I’ll walk you through how I tackled this problem by comparing white noise and blue noise for object placement. I’ll also explore an optimization technique inspired by Casey Muratori’s insights to improve performance, making it feasible for rendering grass in real-time applications.
8
9 ### Understanding White Noise vs. Blue Noise
10
11 White noise is completely random: each point is placed without consideration of others. While this randomness is simple to implement, it results in visually chaotic patterns with undesirable clumping.
12
13 Blue noise introduces spatial constraints, ensuring a minimum distance between points. This results in a more natural, evenly spaced pattern—perfect for simulating real-world distributions like grass or tree placement.
14
15 To visualize this difference, I implemented functions to generate both white and blue noise patterns and compared their results.
16
17
18 ### Implementation Highlights
19
20 #### White Noise
21
22 The **whiteNoiseRandom** function generates points completely randomly within a bounding box:
23
24 ```cpp
25 void whiteNoiseRandom(Vector2& top_left_corner, Vector2& bottom_right_corner, const int& sides, const float& inner_radius, Vector2 positions[], int& i) {
26 std::random_device rd;
27 std::mt19937 gen(rd());
28 std::uniform_real_distribution<float> random_float(0, 1);
29
30 Vector2 start_point = {
31 (random_float(gen) * (bottom_right_corner.x - top_left_corner.x)) + top_left_corner.x ,
32 (random_float(gen) * (bottom_right_corner.y - top_left_corner.y)) + top_left_corner.y
33 };
34 positions[i] = { start_point.x, start_point.y };
35 }
36 ```
37
38 This is computationally the most efficient as there is no constraints on where it can be placed which mean it will often lead to clumping together.
39
40 <div class="center"> <img src="/white_noise_grass.png" /> </div>
41
42 Above image is okay, but lacks realism. We can do better.
43
44
45 #### Blue Noise
46
47 Blue noise requires additional checks to maintain a minimum distance between points, implemented as follows:
48
49 ```cpp
50 void blueNoiseRandom(Vector2& top_left_corner, Vector2& bottom_right_corner, const int& sides, const float& inner_radius, Vector2 positions[], int& i) {
51 std::random_device rd;
52 std::mt19937 gen(rd());
53 std::uniform_real_distribution<float> random_float(0, 1);
54
55 int attempts = 0;
56 const int max_attempts = sides * sides;
57
58 while (attempts < max_attempts) {
59 Vector2 start_point = { random_float(gen) * sides, random_float(gen) * sides };
60 if (x >= top_left_corner.x && x < bottom_right_corner.y && y >= top_left_corner.y && y < bottom_right_corner.y) {
61 bool added = true;
62 for (int j = 0; j < i; j++) {
63 float dx = x - positions[j].x;
64 float dy = y - positions[j].y;
65 if (std::sqrt(dx * dx + dy * dy) < inner_radius) {
66 added = false;
67 break;
68 }
69 }
70 if (added) {
71 positions[i] = { start_point.x, start_point.y };
72 break;
73 }
74 }
75 attempts++;
76 }
77 }
78 ```
79
80 As you can see from below image, this approach improves visual quality...
81
82 <div class="center"> <img src="/blue_noise_random.png" /> </div>
83
84 ...but at the cost of computational complexity. As the number of points increases, available space becomes limited, requiring more attempts to place a point. This can take several seconds, which isn’t ideal.
85
86 <video width="100%" controls>
87 <source src="/slow_blue.mp4" type="video/mp4" />
88 </video>
89
90 ** It takes around 8 seconds for 800 points in 1000 x 800 with 30 radius which means it should be able to add 100 more points in theory **
91
92
93 ### Optimizing Blue Noise Generation
94
95
96 While researching approaches, I came across Casey Muratori’s work on Witness, where he introduced a local sampling optimization. Instead of evaluating the entire grid for each point, checks are limited to a smaller region around the current point. This reduces redundant calculations, especially in dense scenes. Here’s my implementation:
97
98 ```cpp
99 void blueNoiseCircle(Vector2& top_left_corner, Vector2& bottom_right_corner, const int& sides, const float& inner_radius, const float& outer_radius,
100 Vector2& starting_point, Vector2 positions[], int& i){
101 float center_x = starting_point.x;
102 float center_y = starting_point.y;
103
104 std::random_device rd;
105 std::mt19937 gen(rd());
106 std::uniform_real_distribution<float> angle_dist(0, 2 * M_PI);
107 std::uniform_real_distribution<float> radius_dist(0, 1);
108
109 bool added = false;
110 int attempts = 0;
111 const int max_attempts = outer_radius*outer_radius*PI - inner_radius*inner_radius*PI;
112
113 while (attempts <= max_attempts) {
114 float theta = angle_dist(gen);
115 float random_scale = radius_dist(gen);
116 float radius = std::sqrt(random_scale * (outer_radius * outer_radius -
117 inner_radius * inner_radius) +
118 inner_radius * inner_radius);
119 float x = center_x + radius * std::cos(theta);
120 float y = center_y + radius * std::sin(theta);
121
122 added = true;
123 if (x > 0 && x < sides && y > 0 && y < sides) {
124 for (int j = 0; j < i; j++) {
125 Vector2 current_point = positions[j];
126 float dx = x - current_point.x;
127 float dy = y - current_point.y;
128 if (std::sqrt(dx * dx + dy * dy) < inner_radius) {
129 added = false;
130 break;
131 }
132 }
133 if (added) {
134 positions[i] = { x, y };
135 break;
136 }
137 }
138
139 attempts++;
140 }
141 if (!added) {
142 blueNoiseRandom(top_left_corner, bottom_right_corner, sides, inner_radius, positions, i);
143 }
144 }
145 ```
146
147 <video width="100%" controls>
148 <source src="/fast_blue.mp4" type="video/mp4" />
149 </video>
150
151 ** It only took 2 seconds or so. It slows down at the end since it probably needed to look for one or two points using random number **
152
153
154 <div class="center"> <img src="/blue_noises_optimal.png" /> </div>
155
156
157 ### Conclusion
158
159 If you're working on object placement for games, simulations, or any graphics project, understanding the balance between randomness and natural constraints is crucial. Blue noise offers a compelling way to achieve this balance, and with optimizations, it becomes practical for real-time rendering.
160
161 You can find the full source code for my implementation on [GitHub](https://github.com/MrJuneJune/blog_sample_codes/tree/main/performance_tests/noises).