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
29FractalEngine::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
64FractalEngine::~FractalEngine()
65{
66	delete_sem(fRenderSem);
67	delete_sem(fRenderStoppedSem);
68}
69
70
71void 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
166void 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
183void 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
210void 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
231status_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
291void 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
332const double gJuliaA = 0;
333const double gJuliaB = 1;
334
335const uint8 gEscapeHorizon = 4;
336
337
338int32 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
362int32 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
392int32 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
422int32 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
449int32 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
483int32 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