1 /*
2 * Copyright 2016, Haiku, Inc. All rights reserved.
3 * Distributed under the terms of the MIT license.
4 *
5 * Authors:
6 * Augustin Cavalier <waddlesplash>
7 * kerwizzy
8 */
9 #include "FractalEngine.h"
10
11 #include <algorithm>
12 #include <math.h>
13
14 #include <Bitmap.h>
15 #include <String.h>
16
17 #include "Colorsets.h"
18
19
20 //#define TRACE_MANDELBROT_ENGINE
21 #ifdef TRACE_MANDELBROT_ENGINE
22 # include <stdio.h>
23 # define TRACE(x...) printf(x)
24 #else
25 # define TRACE(x...)
26 #endif
27
28
FractalEngine(BHandler * parent,BLooper * looper)29 FractalEngine::FractalEngine(BHandler* parent, BLooper* looper)
30 :
31 BLooper("FractalEngine"),
32 fWidth(0), fHeight(0),
33 fRenderBuffer(NULL),
34 fRenderBufferLen(0),
35 fSubsampling(2),
36 fMessenger(parent, looper),
37 fRenderStopping(false),
38 fRenderStopped(true),
39 fResizing(false),
40 fIterations(1024),
41 fColorset(Colorset_Royal)
42 {
43 fDoSet = &FractalEngine::DoSet_Mandelbrot;
44
45 fRenderSem = create_sem(0, "RenderSem");
46 fRenderStoppedSem = create_sem(0, "RenderStopped");
47
48 system_info info;
49 get_system_info(&info);
50 fThreadCount = info.cpu_count;
51
52 if (fThreadCount > MAX_RENDER_THREADS)
53 fThreadCount = MAX_RENDER_THREADS;
54
55 for (uint8 i = 0; i < fThreadCount; i++) {
56 fRenderThreads[i] = spawn_thread(&FractalEngine::RenderThread,
57 BString().SetToFormat("RenderThread%d", i).String(),
58 B_NORMAL_PRIORITY, this);
59 resume_thread(fRenderThreads[i]);
60 }
61 }
62
63
~FractalEngine()64 FractalEngine::~FractalEngine()
65 {
66 delete_sem(fRenderSem);
67 delete_sem(fRenderStoppedSem);
68 }
69
70
MessageReceived(BMessage * msg)71 void FractalEngine::MessageReceived(BMessage* msg)
72 {
73 switch (msg->what) {
74 case MSG_CHANGE_SET:
75 switch (msg->GetUInt8("set", 0)) {
76 case 0: fDoSet = &FractalEngine::DoSet_Mandelbrot; break;
77 case 1: fDoSet = &FractalEngine::DoSet_BurningShip; break;
78 case 2: fDoSet = &FractalEngine::DoSet_Tricorn; break;
79 case 3: fDoSet = &FractalEngine::DoSet_Julia; break;
80 case 4: fDoSet = &FractalEngine::DoSet_OrbitTrap; break;
81 case 5: fDoSet = &FractalEngine::DoSet_Multibrot; break;
82 }
83 break;
84 case MSG_SET_PALETTE:
85 switch (msg->GetUInt8("palette", 0)) {
86 case 0: fColorset = Colorset_Royal; break;
87 case 1: fColorset = Colorset_DeepFrost; break;
88 case 2: fColorset = Colorset_Frost; break;
89 case 3: fColorset = Colorset_Fire; break;
90 case 4: fColorset = Colorset_Midnight; break;
91 case 5: fColorset = Colorset_Grassland; break;
92 case 6: fColorset = Colorset_Lightning; break;
93 case 7: fColorset = Colorset_Spring; break;
94 case 8: fColorset = Colorset_HighContrast; break;
95 }
96 break;
97 case MSG_SET_ITERATIONS:
98 fIterations = msg->GetUInt16("iterations", 0);
99 break;
100 case MSG_SET_SUBSAMPLING:
101 fSubsampling = msg->GetUInt8("subsampling", 1);
102 break;
103
104 case MSG_RESIZE: {
105 TRACE("Got MSG_RESIZE\n");
106 if (fResizing) {
107 // Will be true throughout this whole handler. Set false at the end
108 TRACE("Breaking out of MSG_RESIZE handler\n");
109 break;
110 }
111 fResizing = true;
112 StopRender();
113
114 delete[] fRenderBuffer;
115 fRenderBuffer = NULL;
116
117 fWidth = msg->GetUInt16("width", 320);
118 fHeight = msg->GetUInt16("height", 240);
119
120 fRenderBufferLen = fWidth * fHeight * 3;
121 fRenderBuffer = new uint8[fRenderBufferLen];
122 TRACE("New buffer width %u height %u ptr = %p\n",
123 fWidth, fHeight, fRenderBuffer);
124
125 memset(fRenderBuffer, 0, fRenderBufferLen);
126
127 BMessage message(MSG_BUFFER_CREATED);
128 fMessenger.SendMessage(&message);
129
130 fResizing = false;
131 break;
132 }
133 case MSG_RENDER: {
134 TRACE("Got MSG_RENDER.\n");
135 if (fResizing)
136 break;
137
138 // Stop the render if one is already running
139 StopRender();
140 Render(msg->GetDouble("locationX", 0), msg->GetDouble("locationY", 0),
141 msg->GetDouble("size", 0.005));
142 break;
143 }
144 case MSG_THREAD_RENDER_COMPLETE: {
145 TRACE("Got MSG_THREAD_RENDER_COMPLETE for thread %d\n",
146 msg->GetUInt8("thread", 0));
147
148 int32 threadsStopped;
149 get_sem_count(fRenderStoppedSem, &threadsStopped);
150 TRACE("threadsStopped = %d\n",threadsStopped);
151 if (threadsStopped == fThreadCount) {
152 TRACE("Done rendering!\n");
153 BMessage message(MSG_RENDER_COMPLETE);
154 fMessenger.SendMessage(&message);
155 }
156 break;
157 }
158
159 default:
160 BLooper::MessageReceived(msg);
161 break;
162 }
163 }
164
165
WriteToBitmap(BBitmap * bitmap)166 void FractalEngine::WriteToBitmap(BBitmap* bitmap)
167 {
168 Lock();
169 BSize size = bitmap->Bounds().Size();
170 if (size.IntegerWidth() != fWidth || size.IntegerHeight() != fHeight) {
171 // some resize happened and now this won't work.
172 Unlock();
173 return;
174 }
175 TRACE("Drawing from = %p\n",fRenderBuffer);
176 bitmap->ImportBits(fRenderBuffer,
177 fRenderBufferLen, fWidth * 3, 0,
178 B_RGB24);
179 Unlock();
180 }
181
182
StopRender()183 void FractalEngine::StopRender()
184 {
185 if (fRenderStopped || fRenderStopping) {
186 // if fRenderStopped is true, then render is already stopped,
187 // so we can't stop it again!
188 // if fStopRender is true, then the fRenderStoppedSem are already
189 // trying to be acquired, so stuff would break if we tried to acquire
190 // them again.
191 return;
192 }
193 fRenderStopping = true;
194 TRACE("Stopping render...\n");
195 for (uint i = 0; i < fThreadCount; i++) {
196 TRACE("Stopping thread %d\n",i);
197 acquire_sem(fRenderStoppedSem);
198 // wait till all the threads are stopped...
199 }
200 int32 threadsStopped;
201 get_sem_count(fRenderStoppedSem, &threadsStopped);
202 TRACE("stopped sem count after stop = %d\n",threadsStopped);
203 fRenderStopping = false;
204 fRenderStopped = true;
205
206 TRACE("Render stopped.\n");
207 }
208
209
Render(double locationX,double locationY,double size)210 void FractalEngine::Render(double locationX, double locationY, double size)
211 {
212 if (fRenderStopping)
213 debugger("Error: Render shouldn't be called while fRenderStopping = true\n");
214 if (!fRenderStopped)
215 debugger("Error: Render already running\n");
216
217 fRenderStopped = false;
218 // This means that future Render calls will need to call stop render
219
220 fLocationX = locationX;
221 fLocationY = locationY;
222 fSize = size;
223
224 TRACE("Location (%%.100g): %.100g;%.100g;%.100g\n", fLocationX, fLocationY, fSize);
225
226 for (uint8 i = 0; i < fThreadCount; i++) {
227 release_sem(fRenderSem);
228 }
229 }
230
RenderThread(void * data)231 status_t FractalEngine::RenderThread(void* data)
232 {
233 FractalEngine* engine = static_cast<FractalEngine*>(data);
234 thread_id self = find_thread(NULL);
235 uint8 threadNum = 0;
236 for (uint8 i = 0; i < engine->fThreadCount; i++) {
237 if (engine->fRenderThreads[i] == self) {
238 threadNum = i;
239 break;
240 }
241 }
242
243 while (true) {
244 TRACE("Thread %d awaiting semaphore...\n", threadNum);
245 acquire_sem(engine->fRenderSem);
246 TRACE("Thread %d got semaphore!\n", threadNum);
247
248 uint16 width = engine->fWidth;
249 uint16 height = engine->fHeight;
250 uint16 halfHeight = height / 2;
251 uint16 threadWidth = width / engine->fThreadCount;
252
253 uint16 startX = threadWidth * threadNum;
254 uint16 endX = threadWidth * (threadNum + 1);
255
256 for (uint16 y = 0; y<halfHeight; y++) {
257 for (uint16 x = startX; x<endX; x++) {
258 engine->RenderPixel(x, halfHeight + y);
259 // max y to RenderPixel will be
260 // floor(height/2)*2 = height-height%2.
261 // Thus there will be a line of blank pixels if height
262 // is not even. Is this a problem?
263 engine->RenderPixel(x, halfHeight - y - 1);
264 // min y to RenderPixel will be
265 // halfHeight-(halfHeight-1)-1 = 0
266 }
267
268 if (engine->fRenderStopping) {
269 TRACE("Thread %d stopping\n", threadNum);
270
271 // Restart the loop to release fRenderStoppedSem and tell
272 // the main thread that this thread is stopped, as well as
273 // to update width, height, etc.
274 break;
275 }
276 }
277
278 if (!engine->fRenderStopping) {
279 // if we got here, then this thread has finished rendering.
280 BMessage message(FractalEngine::MSG_THREAD_RENDER_COMPLETE);
281 message.AddUInt8("thread", threadNum);
282 engine->PostMessage(&message);
283 }
284
285 release_sem(engine->fRenderStoppedSem);
286 }
287 return B_OK;
288 }
289
290
RenderPixel(uint32 x,uint32 y)291 void FractalEngine::RenderPixel(uint32 x, uint32 y)
292 {
293 double real = (x * fSize + fLocationX) - (fWidth / 2 * fSize);
294 double imaginary = (y * -(fSize) + fLocationY) - (fHeight / 2 * -(fSize));
295
296 double subsampleDelta = fSize / fSubsampling;
297 uint16 nSamples = fSubsampling * fSubsampling;
298
299 int16 totalR = 0;
300 int16 totalG = 0;
301 int16 totalB = 0;
302 for (uint8 subX = 0; subX < fSubsampling; subX++) {
303 for (uint8 subY = 0; subY < fSubsampling; subY++) {
304 double sampleReal = real + subX * subsampleDelta;
305 double sampleImaginary = imaginary + subY * subsampleDelta;
306
307 int32 sampleIterToEscape = (this->*fDoSet)(sampleReal, sampleImaginary);
308
309 uint16 sampleLoc = 0;
310 if (sampleIterToEscape == -1)
311 // Didn't escape.
312 sampleLoc = 999;
313 else
314 sampleLoc = 998 - (sampleIterToEscape % 999);
315 sampleLoc *= 3;
316
317 totalR += fColorset[sampleLoc + 0];
318 totalG += fColorset[sampleLoc + 1];
319 totalB += fColorset[sampleLoc + 2];
320 }
321 }
322
323
324 uint32 offsetBase = fWidth * y * 3 + x * 3;
325 fRenderBuffer[offsetBase + 2] = totalR / nSamples; // fRenderBuffer is BGR
326 fRenderBuffer[offsetBase + 1] = totalG / nSamples;
327 fRenderBuffer[offsetBase + 0] = totalB / nSamples;
328 }
329
330
331 // Magic numbers & other general constants
332 const double gJuliaA = 0;
333 const double gJuliaB = 1;
334
335 const uint8 gEscapeHorizon = 4;
336
337
DoSet_Mandelbrot(double real,double imaginary)338 int32 FractalEngine::DoSet_Mandelbrot(double real, double imaginary)
339 {
340 double zReal = 0;
341 double zImaginary = 0;
342
343 for (int32 i = 0; i < fIterations; i++) {
344 double zRealSq = zReal * zReal;
345 double zImaginarySq = zImaginary * zImaginary;
346 double nzReal = (zRealSq + (-1 * zImaginarySq));
347
348 zImaginary = 2 * (zReal * zImaginary);
349 zReal = nzReal;
350
351 zReal += real;
352 zImaginary += imaginary;
353
354 // If it is outside the 2 unit circle...
355 if ((zRealSq + zImaginarySq) > gEscapeHorizon)
356 return i; // stop it from running longer
357 }
358 return -1;
359 }
360
361
DoSet_BurningShip(double real,double imaginary)362 int32 FractalEngine::DoSet_BurningShip(double real, double imaginary)
363 {
364 double zReal = 0;
365 double zImaginary = 0;
366
367 // It looks "upside down" otherwise.
368 imaginary = -imaginary;
369
370 for (int32 i = 0; i < fIterations; i++) {
371 zReal = fabs(zReal);
372 zImaginary = fabs(zImaginary);
373
374 double zRealSq = zReal * zReal;
375 double zImaginarySq = zImaginary * zImaginary;
376 double nzReal = (zRealSq + (-1 * zImaginarySq));
377
378 zImaginary = 2 * (zReal * zImaginary);
379 zReal = nzReal;
380
381 zReal += real;
382 zImaginary += imaginary;
383
384 // If it is outside the 2 unit circle...
385 if ((zRealSq + zImaginarySq) > gEscapeHorizon)
386 return i; // stop it from running longer
387 }
388 return -1;
389 }
390
391
DoSet_Tricorn(double real,double imaginary)392 int32 FractalEngine::DoSet_Tricorn(double real, double imaginary)
393 {
394 double zReal = 0;
395 double zImaginary = 0;
396
397 real = -real;
398
399 for (int32 i = 0; i < fIterations; i++) {
400 double znRe = zImaginary * -1;
401 zImaginary = zReal * -1;
402 zReal = znRe; // Swap the real and complex parts each time.
403
404 double zRealSq = zReal * zReal;
405 double zImaginarySq = zImaginary * zImaginary;
406 double nzReal = (zRealSq + (-1 * zImaginarySq));
407
408 zImaginary = 2 * (zReal * zImaginary);
409 zReal = nzReal;
410
411 zReal += real;
412 zImaginary += imaginary;
413
414 // If it is outside the 2 unit circle...
415 if ((zRealSq + zImaginarySq) > gEscapeHorizon)
416 return i; // stop it from running longer
417 }
418 return -1;
419 }
420
421
DoSet_Julia(double real,double imaginary)422 int32 FractalEngine::DoSet_Julia(double real, double imaginary)
423 {
424 double zReal = real;
425 double zImaginary = imaginary;
426
427 double muRe = gJuliaA;
428 double muIm = gJuliaB;
429
430 for (int32 i = 0; i < fIterations; i++) {
431 double zRealSq = zReal * zReal;
432 double zImaginarySq = zImaginary * zImaginary;
433 double nzReal = (zRealSq + (-1 * (zImaginarySq)));
434
435 zImaginary = 2 * (zReal * zImaginary);
436 zReal = nzReal;
437
438 zReal += muRe;
439 zImaginary += muIm;
440
441 // If it is outside the 2 unit circle...
442 if ((zRealSq + zImaginarySq) > gEscapeHorizon)
443 return i; // stop it from running longer
444 }
445 return -1;
446 }
447
448
DoSet_OrbitTrap(double real,double imaginary)449 int32 FractalEngine::DoSet_OrbitTrap(double real, double imaginary)
450 {
451 double zReal = 0;
452 double zImaginary = 0;
453
454 double closest = 10000000;
455 double distance = 0;
456 double lineDist = 0;
457
458 for (int32 i = 0; i < fIterations; i++) {
459 double zRealSq = zReal * zReal;
460 double zImaginarySq = zImaginary * zImaginary;
461 double nzReal = (zRealSq + (-1 * zImaginarySq));
462
463 zImaginary = 2 * (zReal * zImaginary);
464 zReal = nzReal;
465
466 zReal += real;
467 zImaginary += imaginary;
468
469 distance = sqrt(zRealSq + zImaginarySq);
470 lineDist = fabs(zReal + zImaginary);
471
472 // If it is closer than ever before...
473 if (lineDist < closest)
474 closest = lineDist;
475
476 if (distance > gEscapeHorizon)
477 return static_cast<int32>(floor(4 * log(4 / closest)));
478 }
479 return static_cast<int32>(floor(4 * log(4 / closest)));
480 }
481
482
DoSet_Multibrot(double real,double imaginary)483 int32 FractalEngine::DoSet_Multibrot(double real, double imaginary)
484 {
485 double zReal = 0;
486 double zImaginary = 0;
487
488 for (int32 i = 0; i < fIterations; i++) {
489 double zRealSq = zReal * zReal;
490 double zImaginarySq = zImaginary * zImaginary;
491 double nzReal = (zRealSq * zReal - 3 * zReal * zImaginarySq);
492
493 zImaginary = 3 * (zRealSq * zImaginary) - (zImaginarySq * zImaginary);
494
495 zReal = nzReal;
496 zReal += real;
497 zImaginary += imaginary;
498
499 // If it is outside the 2 unit circle...
500 if ((zRealSq + zImaginarySq) > gEscapeHorizon)
501 return i; // stop it from running longer
502 }
503 return -1;
504 }
505