src/native_client_sdk/src/gonacl_appengine/src/voronoi/voronoi.cc

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