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 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 64 FractalEngine::~FractalEngine() 65 { 66 delete_sem(fRenderSem); 67 delete_sem(fRenderStoppedSem); 68 } 69 70 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 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 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 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 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 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 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 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 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 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 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 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