1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <assert.h> 6 #include <math.h> 7 #include <ppapi/c/ppb_input_event.h> 8 #include <ppapi/cpp/input_event.h> 9 #include <ppapi/cpp/var.h> 10 #include <ppapi/cpp/var_array.h> 11 #include <ppapi/cpp/var_array_buffer.h> 12 #include <ppapi/cpp/var_dictionary.h> 13 #include <pthread.h> 14 #include <stdio.h> 15 #include <stdlib.h> 16 #include <string.h> 17 #include <sys/time.h> 18 #include <unistd.h> 19 20 #include <algorithm> 21 #include <string> 22 23 #include "ppapi_simple/ps.h" 24 #include "ppapi_simple/ps_context_2d.h" 25 #include "ppapi_simple/ps_event.h" 26 #include "ppapi_simple/ps_interface.h" 27 #include "ppapi_simple/ps_main.h" 28 #include "sdk_util/thread_pool.h" 29 30 using namespace sdk_util; // For sdk_util::ThreadPool 31 32 // Global properties used to setup Voronoi demo. 33 namespace { 34 const int kMinRectSize = 4; 35 const int kStartRecurseSize = 32; // must be power-of-two 36 const float kHugeZ = 1.0e38f; 37 const float kPI = M_PI; 38 const float kTwoPI = kPI * 2.0f; 39 const int kFramesToBenchmark = 100; 40 const unsigned int kRandomStartSeed = 0xC0DE533D; 41 const int kMaxPointCount = 1024; 42 const int kStartPointCount = 48; 43 const int kDefaultNumRegions = 256; 44 45 unsigned int g_rand_state = kRandomStartSeed; 46 47 // random number helper 48 inline unsigned char rand255() { 49 return static_cast<unsigned char>(rand_r(&g_rand_state) & 255); 50 } 51 52 // random number helper 53 inline float frand() { 54 return (static_cast<float>(rand_r(&g_rand_state)) / 55 static_cast<float>(RAND_MAX)); 56 } 57 58 // reset random seed 59 inline void rand_reset(unsigned int seed) { 60 g_rand_state = seed; 61 } 62 63 #ifndef NDEBUG 64 // returns true if input is power of two. 65 // only used in assertions. 66 inline bool is_pow2(int x) { 67 return (x & (x - 1)) == 0; 68 } 69 #endif 70 71 inline double getseconds() { 72 const double usec_to_sec = 0.000001; 73 timeval tv; 74 if (0 == gettimeofday(&tv, NULL)) 75 return tv.tv_sec + tv.tv_usec * usec_to_sec; 76 return 0.0; 77 } 78 79 // BGRA helper function, for constructing a pixel for a BGRA buffer. 80 inline uint32_t MakeBGRA(uint32_t b, uint32_t g, uint32_t r, uint32_t a) { 81 return (((a) << 24) | ((r) << 16) | ((g) << 8) | (b)); 82 } 83 } // namespace 84 85 // Vec2, simple 2D vector 86 struct Vec2 { 87 float x, y; 88 Vec2() {} 89 Vec2(float px, float py) { 90 x = px; 91 y = py; 92 } 93 void Set(float px, float py) { 94 x = px; 95 y = py; 96 } 97 }; 98 99 // The main object that runs Voronoi simulation. 100 class Voronoi { 101 public: 102 Voronoi(); 103 virtual ~Voronoi(); 104 // Runs a tick of the simulations, update 2D output. 105 void Update(); 106 // Handle event from user, or message from JS. 107 void HandleEvent(PSEvent* ps_event); 108 109 private: 110 // Methods prefixed with 'w' are run on worker threads. 111 uint32_t* wGetAddr(int x, int y); 112 int wCell(float x, float y); 113 inline void wFillSpan(uint32_t *pixels, uint32_t color, int width); 114 void wRenderTile(int x, int y, int w, int h); 115 void wProcessTile(int x, int y, int w, int h); 116 void wSubdivide(int x, int y, int w, int h); 117 void wMakeRect(int region, int *x, int *y, int *w, int *h); 118 bool wTestRect(int *m, int x, int y, int w, int h); 119 void wFillRect(int x, int y, int w, int h, uint32_t color); 120 void wRenderRect(int x0, int y0, int x1, int y1); 121 void wRenderRegion(int region); 122 static void wRenderRegionEntry(int region, void *thiz); 123 124 // These methods are only called by the main thread. 125 void Reset(); 126 void UpdateSim(); 127 void RenderDot(float x, float y, uint32_t color1, uint32_t color2); 128 void SuperimposePositions(); 129 void Render(); 130 void Draw(); 131 void StartBenchmark(); 132 void EndBenchmark(); 133 // Helper to post small update messages to JS. 134 void PostUpdateMessage(const char* message_name, double value); 135 136 PSContext2D_t* ps_context_; 137 Vec2 positions_[kMaxPointCount]; 138 Vec2 screen_positions_[kMaxPointCount]; 139 Vec2 velocities_[kMaxPointCount]; 140 uint32_t colors_[kMaxPointCount]; 141 float ang_; 142 const int num_regions_; 143 int num_threads_; 144 int point_count_; 145 bool draw_points_; 146 bool draw_interiors_; 147 ThreadPool* workers_; 148 int benchmark_frame_counter_; 149 bool benchmarking_; 150 double benchmark_start_time_; 151 double benchmark_end_time_; 152 }; 153 154 155 void Voronoi::Reset() { 156 rand_reset(kRandomStartSeed); 157 ang_ = 0.0f; 158 for (int i = 0; i < kMaxPointCount; i++) { 159 // random initial start position 160 const float x = frand(); 161 const float y = frand(); 162 positions_[i].Set(x, y); 163 // random directional velocity ( -1..1, -1..1 ) 164 const float speed = 0.0005f; 165 const float u = (frand() * 2.0f - 1.0f) * speed; 166 const float v = (frand() * 2.0f - 1.0f) * speed; 167 velocities_[i].Set(u, v); 168 // 'unique' color (well... unique enough for our purposes) 169 colors_[i] = MakeBGRA(rand255(), rand255(), rand255(), 255); 170 } 171 } 172 173 Voronoi::Voronoi() : num_regions_(kDefaultNumRegions), num_threads_(0), 174 point_count_(kStartPointCount), draw_points_(true), draw_interiors_(true), 175 benchmark_frame_counter_(0), benchmarking_(false) { 176 Reset(); 177 // By default, render from the dispatch thread. 178 workers_ = new ThreadPool(num_threads_); 179 PSEventSetFilter(PSE_ALL); 180 ps_context_ = PSContext2DAllocate(PP_IMAGEDATAFORMAT_BGRA_PREMUL); 181 } 182 183 Voronoi::~Voronoi() { 184 delete workers_; 185 PSContext2DFree(ps_context_); 186 } 187 188 inline uint32_t* Voronoi::wGetAddr(int x, int y) { 189 return ps_context_->data + x + y * ps_context_->stride / sizeof(uint32_t); 190 } 191 192 // This is the core of the Voronoi calculation. At a given point on the 193 // screen, iterate through all voronoi positions and render them as 3D cones. 194 // We're looking for the voronoi cell that generates the closest z value. 195 // (not really cones - since it is all relative, we avoid doing the 196 // expensive sqrt and test against z*z instead) 197 // If multithreading, this function is only called by the worker threads. 198 int Voronoi::wCell(float x, float y) { 199 int closest_cell = 0; 200 float zz = kHugeZ; 201 Vec2* pos = screen_positions_; 202 for (int i = 0; i < point_count_; ++i) { 203 // measured 5.18 cycles per iteration on a core2 204 float dx = x - pos[i].x; 205 float dy = y - pos[i].y; 206 float dd = (dx * dx + dy * dy); 207 if (dd < zz) { 208 zz = dd; 209 closest_cell = i; 210 } 211 } 212 return closest_cell; 213 } 214 215 // Given a region r, derive a non-overlapping rectangle for a thread to 216 // work on. 217 // If multithreading, this function is only called by the worker threads. 218 void Voronoi::wMakeRect(int r, int* x, int* y, int* w, int* h) { 219 const int parts = 16; 220 assert(parts * parts == num_regions_); 221 *w = ps_context_->width / parts; 222 *h = ps_context_->height / parts; 223 *x = *w * (r % parts); 224 *y = *h * ((r / parts) % parts); 225 } 226 227 // Test 4 corners of a rectangle to see if they all belong to the same 228 // voronoi cell. Each test is expensive so bail asap. Returns true 229 // if all 4 corners match. 230 // If multithreading, this function is only called by the worker threads. 231 bool Voronoi::wTestRect(int* m, int x, int y, int w, int h) { 232 // each test is expensive, so exit ASAP 233 const int m0 = wCell(x, y); 234 const int m1 = wCell(x + w - 1, y); 235 if (m0 != m1) return false; 236 const int m2 = wCell(x, y + h - 1); 237 if (m0 != m2) return false; 238 const int m3 = wCell(x + w - 1, y + h - 1); 239 if (m0 != m3) return false; 240 // all 4 corners belong to the same cell 241 *m = m0; 242 return true; 243 } 244 245 // Quickly fill a span of pixels with a solid color. Assumes 246 // span width is divisible by 4. 247 // If multithreading, this function is only called by the worker threads. 248 inline void Voronoi::wFillSpan(uint32_t* pixels, uint32_t color, int width) { 249 if (!draw_interiors_) { 250 const uint32_t gray = MakeBGRA(128, 128, 128, 255); 251 color = gray; 252 } 253 for (int i = 0; i < width; i += 4) { 254 *pixels++ = color; 255 *pixels++ = color; 256 *pixels++ = color; 257 *pixels++ = color; 258 } 259 } 260 261 // Quickly fill a rectangle with a solid color. Assumes 262 // the width w parameter is evenly divisible by 4. 263 // If multithreading, this function is only called by the worker threads. 264 void Voronoi::wFillRect(int x, int y, int w, int h, uint32_t color) { 265 const uint32_t stride_in_pixels = ps_context_->stride / sizeof(uint32_t); 266 uint32_t* pixels = wGetAddr(x, y); 267 for (int j = 0; j < h; j++) { 268 wFillSpan(pixels, color, w); 269 pixels += stride_in_pixels; 270 } 271 } 272 273 // When recursive subdivision reaches a certain minimum without finding a 274 // rectangle that has four matching corners belonging to the same voronoi 275 // cell, this function will break the retangular 'tile' into smaller scanlines 276 // and look for opportunities to quick fill at the scanline level. If the 277 // scanline can't be quick filled, it will slow down even further and compute 278 // voronoi membership per pixel. 279 void Voronoi::wRenderTile(int x, int y, int w, int h) { 280 // rip through a tile 281 const uint32_t stride_in_pixels = ps_context_->stride / sizeof(uint32_t); 282 uint32_t* pixels = wGetAddr(x, y); 283 for (int j = 0; j < h; j++) { 284 // get start and end cell values 285 int ms = wCell(x + 0, y + j); 286 int me = wCell(x + w - 1, y + j); 287 // if the end points are the same, quick fill the span 288 if (ms == me) { 289 wFillSpan(pixels, colors_[ms], w); 290 } else { 291 // else compute each pixel in the span... this is the slow part! 292 uint32_t* p = pixels; 293 *p++ = colors_[ms]; 294 for (int i = 1; i < (w - 1); i++) { 295 int m = wCell(x + i, y + j); 296 *p++ = colors_[m]; 297 } 298 *p++ = colors_[me]; 299 } 300 pixels += stride_in_pixels; 301 } 302 } 303 304 // Take a rectangular region and do one of - 305 // If all four corners below to the same voronoi cell, stop recursion and 306 // quick fill the rectangle. 307 // If the minimum rectangle size has been reached, break out of recursion 308 // and process the rectangle. This small rectangle is called a tile. 309 // Otherwise, keep recursively subdividing the rectangle into 4 equally 310 // sized smaller rectangles. 311 // Note: at the moment, these will always be squares, not rectangles. 312 // If multithreading, this function is only called by the worker threads. 313 void Voronoi::wSubdivide(int x, int y, int w, int h) { 314 int m; 315 // if all 4 corners are equal, quick fill interior 316 if (wTestRect(&m, x, y, w, h)) { 317 wFillRect(x, y, w, h, colors_[m]); 318 } else { 319 // did we reach the minimum rectangle size? 320 if ((w <= kMinRectSize) || (h <= kMinRectSize)) { 321 wRenderTile(x, y, w, h); 322 } else { 323 // else recurse into smaller rectangles 324 const int half_w = w / 2; 325 const int half_h = h / 2; 326 wSubdivide(x, y, half_w, half_h); 327 wSubdivide(x + half_w, y, half_w, half_h); 328 wSubdivide(x, y + half_h, half_w, half_h); 329 wSubdivide(x + half_w, y + half_h, half_w, half_h); 330 } 331 } 332 } 333 334 // This function cuts up the rectangle into power of 2 sized squares. It 335 // assumes the input rectangle w & h are evenly divisible by 336 // kStartRecurseSize. 337 // If multithreading, this function is only called by the worker threads. 338 void Voronoi::wRenderRect(int x, int y, int w, int h) { 339 for (int iy = y; iy < (y + h); iy += kStartRecurseSize) { 340 for (int ix = x; ix < (x + w); ix += kStartRecurseSize) { 341 wSubdivide(ix, iy, kStartRecurseSize, kStartRecurseSize); 342 } 343 } 344 } 345 346 // If multithreading, this function is only called by the worker threads. 347 void Voronoi::wRenderRegion(int region) { 348 // convert region # into x0, y0, x1, y1 rectangle 349 int x, y, w, h; 350 wMakeRect(region, &x, &y, &w, &h); 351 // render this rectangle 352 wRenderRect(x, y, w, h); 353 } 354 355 // Entry point for worker thread. Can't pass a member function around, so we 356 // have to do this little round-about. 357 void Voronoi::wRenderRegionEntry(int region, void* thiz) { 358 static_cast<Voronoi*>(thiz)->wRenderRegion(region); 359 } 360 361 // Function Voronoi::UpdateSim() 362 // Run a simple sim to move the voronoi positions. This update loop 363 // is run once per frame. Called from the main thread only, and only 364 // when the worker threads are idle. 365 void Voronoi::UpdateSim() { 366 ang_ += 0.002f; 367 if (ang_ > kTwoPI) { 368 ang_ = ang_ - kTwoPI; 369 } 370 float z = cosf(ang_) * 3.0f; 371 // push the points around on the screen for animation 372 for (int j = 0; j < kMaxPointCount; j++) { 373 positions_[j].x += (velocities_[j].x) * z; 374 positions_[j].y += (velocities_[j].y) * z; 375 screen_positions_[j].x = positions_[j].x * ps_context_->width; 376 screen_positions_[j].y = positions_[j].y * ps_context_->height; 377 } 378 } 379 380 // Renders a small diamond shaped dot at x, y clipped against the window 381 void Voronoi::RenderDot(float x, float y, uint32_t color1, uint32_t color2) { 382 const int ix = static_cast<int>(x); 383 const int iy = static_cast<int>(y); 384 const uint32_t stride_in_pixels = ps_context_->stride / sizeof(uint32_t); 385 // clip it against window 386 if (ix < 1) return; 387 if (ix >= (ps_context_->width - 1)) return; 388 if (iy < 1) return; 389 if (iy >= (ps_context_->height - 1)) return; 390 uint32_t* pixel = wGetAddr(ix, iy); 391 // render dot as a small diamond 392 *pixel = color1; 393 *(pixel - 1) = color2; 394 *(pixel + 1) = color2; 395 *(pixel - stride_in_pixels) = color2; 396 *(pixel + stride_in_pixels) = color2; 397 } 398 399 // Superimposes dots on the positions. 400 void Voronoi::SuperimposePositions() { 401 const uint32_t white = MakeBGRA(255, 255, 255, 255); 402 const uint32_t gray = MakeBGRA(192, 192, 192, 255); 403 for (int i = 0; i < point_count_; i++) { 404 RenderDot( 405 screen_positions_[i].x, screen_positions_[i].y, white, gray); 406 } 407 } 408 409 // Renders the Voronoi diagram, dispatching the work to multiple threads. 410 void Voronoi::Render() { 411 workers_->Dispatch(num_regions_, wRenderRegionEntry, this); 412 if (draw_points_) 413 SuperimposePositions(); 414 } 415 416 void Voronoi::StartBenchmark() { 417 Reset(); 418 printf("Benchmark started...\n"); 419 benchmark_frame_counter_ = kFramesToBenchmark; 420 benchmarking_ = true; 421 benchmark_start_time_ = getseconds(); 422 } 423 424 void Voronoi::EndBenchmark() { 425 benchmark_end_time_ = getseconds(); 426 printf("Benchmark ended... time: %2.5f\n", 427 benchmark_end_time_ - benchmark_start_time_); 428 benchmarking_ = false; 429 benchmark_frame_counter_ = 0; 430 double result = benchmark_end_time_ - benchmark_start_time_; 431 PostUpdateMessage("benchmark_result", result); 432 } 433 434 // Handle input events from the user and messages from JS. 435 void Voronoi::HandleEvent(PSEvent* ps_event) { 436 // Give the 2D context a chance to process the event. 437 if (0 != PSContext2DHandleEvent(ps_context_, ps_event)) 438 return; 439 if (ps_event->type == PSE_INSTANCE_HANDLEINPUT) { 440 // Convert Pepper Simple event to a PPAPI C++ event 441 pp::InputEvent event(ps_event->as_resource); 442 switch (event.GetType()) { 443 case PP_INPUTEVENT_TYPE_KEYDOWN: { 444 pp::KeyboardInputEvent key = pp::KeyboardInputEvent(event); 445 uint32_t key_code = key.GetKeyCode(); 446 if (key_code == 84) // 't' key 447 if (!benchmarking_) 448 StartBenchmark(); 449 break; 450 } 451 case PP_INPUTEVENT_TYPE_TOUCHSTART: 452 case PP_INPUTEVENT_TYPE_TOUCHMOVE: { 453 pp::TouchInputEvent touches = pp::TouchInputEvent(event); 454 uint32_t count = touches.GetTouchCount(PP_TOUCHLIST_TYPE_TOUCHES); 455 // Touch points 0..n directly set position of points 0..n in 456 // Voronoi diagram. 457 for (uint32_t i = 0; i < count; i++) { 458 pp::TouchPoint touch = 459 touches.GetTouchByIndex(PP_TOUCHLIST_TYPE_TOUCHES, i); 460 pp::FloatPoint point = touch.position(); 461 positions_[i].Set(point.x() / ps_context_->width, 462 point.y() / ps_context_->height); 463 } 464 break; 465 } 466 default: 467 break; 468 } 469 } else if (ps_event->type == PSE_INSTANCE_HANDLEMESSAGE) { 470 // Convert Pepper Simple message to PPAPI C++ var 471 pp::Var var(ps_event->as_var); 472 if (var.is_dictionary()) { 473 pp::VarDictionary dictionary(var); 474 std::string message = dictionary.Get("message").AsString(); 475 if (message == "run_benchmark" && !benchmarking_) 476 StartBenchmark(); 477 else if (message == "draw_points") 478 draw_points_ = dictionary.Get("value").AsBool(); 479 else if (message == "draw_interiors") 480 draw_interiors_ = dictionary.Get("value").AsBool(); 481 else if (message == "set_points") { 482 int num_points = dictionary.Get("value").AsInt(); 483 point_count_ = std::min(kMaxPointCount, std::max(0, num_points)); 484 } else if (message == "set_threads") { 485 int thread_count = dictionary.Get("value").AsInt(); 486 delete workers_; 487 workers_ = new ThreadPool(thread_count); 488 } 489 } 490 } 491 } 492 493 // PostUpdateMessage() helper function for sendimg small messages to JS. 494 void Voronoi::PostUpdateMessage(const char* message_name, double value) { 495 pp::VarDictionary message; 496 message.Set("message", message_name); 497 message.Set("value", value); 498 PSInterfaceMessaging()->PostMessage(PSGetInstanceId(), message.pp_var()); 499 } 500 501 void Voronoi::Update() { 502 PSContext2DGetBuffer(ps_context_); 503 if (NULL == ps_context_->data) 504 return; 505 assert(is_pow2(ps_context_->width)); 506 assert(is_pow2(ps_context_->height)); 507 508 // When benchmarking is running, don't update display via 509 // PSContext2DSwapBuffer() - vsync is enabled by default, and will throttle 510 // the benchmark results. 511 do { 512 UpdateSim(); 513 Render(); 514 if (!benchmarking_) break; 515 --benchmark_frame_counter_; 516 } while (benchmark_frame_counter_ > 0); 517 if (benchmarking_) 518 EndBenchmark(); 519 520 PSContext2DSwapBuffer(ps_context_); 521 } 522 523 // Starting point for the module. We do not use main since it would 524 // collide with main in libppapi_cpp. 525 int example_main(int argc, char* argv[]) { 526 Voronoi voronoi; 527 while (true) { 528 PSEvent* ps_event; 529 // Consume all available events. 530 while ((ps_event = PSEventTryAcquire()) != NULL) { 531 voronoi.HandleEvent(ps_event); 532 PSEventRelease(ps_event); 533 } 534 // Do simulation, render and present. 535 voronoi.Update(); 536 } 537 538 return 0; 539 } 540 541 // Register the function to call once the Instance Object is initialized. 542 // see: pappi_simple/ps_main.h 543 PPAPI_SIMPLE_REGISTER_MAIN(example_main); 544