src/voronoi/voronoi.cc

// Copyright (c) 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <assert.h>
#include <math.h>
#include <ppapi/c/ppb_input_event.h>
#include <ppapi/cpp/input_event.h>
#include <ppapi/cpp/var.h>
#include <ppapi/cpp/var_array.h>
#include <ppapi/cpp/var_array_buffer.h>
#include <ppapi/cpp/var_dictionary.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <algorithm>
#include <string>

#include "common/fps.h"
#include "ppapi_simple/ps.h"
#include "ppapi_simple/ps_context_2d.h"
#include "ppapi_simple/ps_event.h"
#include "ppapi_simple/ps_interface.h"
#include "ppapi_simple/ps_main.h"
#include "sdk_util/thread_pool.h"

using namespace sdk_util;  // For sdk_util::ThreadPool

// Global properties used to setup Voronoi demo.
namespace {
const int kMinRectSize = 4;
const int kStartRecurseSize = 32;  // must be power-of-two
const float kHugeZ = 1.0e38f;
const float kPI = M_PI;
const float kTwoPI = kPI * 2.0f;
const unsigned int kRandomStartSeed = 0xC0DE533D;
const int kMaxPointCount = 1024;
const int kStartPointCount = 48;
const int kDefaultNumRegions = 256;

unsigned int g_rand_state = kRandomStartSeed;

// random number helper
inline unsigned char rand255() {
  return static_cast<unsigned char>(rand_r(&g_rand_state) & 255);
}

// random number helper
inline float frand() {
  return (static_cast<float>(rand_r(&g_rand_state)) /
      static_cast<float>(RAND_MAX));
}

// reset random seed
inline void rand_reset(unsigned int seed) {
  g_rand_state = seed;
}

inline uint32_t next_pow2(uint32_t x) {
  // Via Hacker's Delight, section 3.2 "Rounding Up/Down to the Next Power of 2"
  --x;
  x |= (x >> 1);
  x |= (x >> 2);
  x |= (x >> 4);
  x |= (x >> 8);
  x |= (x >> 16);
  return x + 1;
}

// BGRA helper function, for constructing a pixel for a BGRA buffer.
inline uint32_t MakeBGRA(uint32_t b, uint32_t g, uint32_t r, uint32_t a) {
  return (((a) << 24) | ((r) << 16) | ((g) << 8) | (b));
}
}  // namespace

// Vec2, simple 2D vector
struct Vec2 {
  float x, y;
  Vec2() {}
  Vec2(float px, float py) {
    x = px;
    y = py;
  }
  void Set(float px, float py) {
    x = px;
    y = py;
  }
};

// The main object that runs Voronoi simulation.
class Voronoi {
 public:
  Voronoi();
  virtual ~Voronoi();
  // Runs a tick of the simulations, update 2D output.
  void Update();
  // Handle event from user, or message from JS.
  void HandleEvent(PSEvent* ps_event);

 private:
  // Methods prefixed with 'w' are run on worker threads.
  uint32_t* wGetAddr(int x, int y);
  int wCell(float x, float y);
  inline void wFillSpan(uint32_t *pixels, uint32_t color, int width);
  void wRenderTile(int x, int y, int w, int h);
  void wProcessTile(int x, int y, int w, int h);
  void wSubdivide(int x, int y, int w, int h);
  void wMakeRect(int region, int *x, int *y, int *w, int *h);
  bool wTestRect(int *m, int x, int y, int w, int h);
  void wFillRect(int x, int y, int w, int h, uint32_t color);
  void wRenderRect(int x0, int y0, int x1, int y1);
  void wRenderRegion(int region);
  static void wRenderRegionEntry(int region, void *thiz);

  // These methods are only called by the main thread.
  void Reset();
  void UpdateSim();
  void RenderDot(float x, float y, uint32_t color1, uint32_t color2);
  void SuperimposePositions();
  void Render();
  void Draw();
  // Helper to post small update messages to JS.
  void PostUpdateMessage(const char* message_name, double value);

  PSContext2D_t* ps_context_;
  Vec2 positions_[kMaxPointCount];
  Vec2 screen_positions_[kMaxPointCount];
  Vec2 velocities_[kMaxPointCount];
  uint32_t colors_[kMaxPointCount];
  float ang_;
  const int num_regions_;
  int num_threads_;
  int point_count_;
  bool draw_points_;
  bool draw_interiors_;
  ThreadPool* workers_;
  FpsState fps_state_;
};


void Voronoi::Reset() {
  rand_reset(kRandomStartSeed);
  ang_ = 0.0f;
  for (int i = 0; i < kMaxPointCount; i++) {
    // random initial start position
    const float x = frand();
    const float y = frand();
    positions_[i].Set(x, y);
    // random directional velocity ( -1..1, -1..1 )
    const float speed = 0.0005f;
    const float u = (frand() * 2.0f - 1.0f) * speed;
    const float v = (frand() * 2.0f - 1.0f) * speed;
    velocities_[i].Set(u, v);
    // 'unique' color (well... unique enough for our purposes)
    colors_[i] = MakeBGRA(rand255(), rand255(), rand255(), 255);
  }
}

Voronoi::Voronoi() : num_regions_(kDefaultNumRegions), num_threads_(0),
    point_count_(kStartPointCount), draw_points_(true), draw_interiors_(true) {
  Reset();
  // By default, render from the dispatch thread.
  workers_ = new ThreadPool(num_threads_);
  PSEventSetFilter(PSE_ALL);
  ps_context_ = PSContext2DAllocate(PP_IMAGEDATAFORMAT_BGRA_PREMUL);
  FpsInit(&fps_state_);
}

Voronoi::~Voronoi() {
  delete workers_;
  PSContext2DFree(ps_context_);
}

inline uint32_t* Voronoi::wGetAddr(int x, int y) {
  return ps_context_->data + x + y * ps_context_->stride / sizeof(uint32_t);
}

// This is the core of the Voronoi calculation.  At a given point on the
// screen, iterate through all voronoi positions and render them as 3D cones.
// We're looking for the voronoi cell that generates the closest z value.
// (not really cones - since it is all relative, we avoid doing the
// expensive sqrt and test against z*z instead)
// If multithreading, this function is only called by the worker threads.
int Voronoi::wCell(float x, float y) {
  int closest_cell = 0;
  float zz = kHugeZ;
  Vec2* pos = screen_positions_;
  for (int i = 0; i < point_count_; ++i) {
    // measured 5.18 cycles per iteration on a core2
    float dx = x - pos[i].x;
    float dy = y - pos[i].y;
    float dd = (dx * dx + dy * dy);
    if (dd < zz) {
      zz = dd;
      closest_cell = i;
    }
  }
  return closest_cell;
}

// Given a region r, derive a non-overlapping rectangle for a thread to
// work on.
// If multithreading, this function is only called by the worker threads.
void Voronoi::wMakeRect(int r, int* x, int* y, int* w, int* h) {
  const int parts = 16;
  assert(parts * parts == num_regions_);
  // Round up to the nearest power of two so we can divide by parts cleanly. We
  // could round up to the nearest 16 pixels, but it runs much faster when
  // subdividing power-of-two squares.
  //
  // Many of these squares are outside of the canvas, but they will be
  // trivially culled by wRenderRect.
  *w = static_cast<int>(next_pow2(ps_context_->width)) / parts;
  *h = static_cast<int>(next_pow2(ps_context_->height)) / parts;
  *x = *w * (r % parts);
  *y = *h * ((r / parts) % parts);
}

// Test 4 corners of a rectangle to see if they all belong to the same
// voronoi cell.  Each test is expensive so bail asap.  Returns true
// if all 4 corners match.
// If multithreading, this function is only called by the worker threads.
bool Voronoi::wTestRect(int* m, int x, int y, int w, int h) {
  // each test is expensive, so exit ASAP
  const int m0 = wCell(x, y);
  const int m1 = wCell(x + w - 1, y);
  if (m0 != m1) return false;
  const int m2 = wCell(x, y + h - 1);
  if (m0 != m2) return false;
  const int m3 = wCell(x + w - 1, y + h - 1);
  if (m0 != m3) return false;
  // all 4 corners belong to the same cell
  *m = m0;
  return true;
}

// Quickly fill a span of pixels with a solid color.
// If multithreading, this function is only called by the worker threads.
inline void Voronoi::wFillSpan(uint32_t* pixels, uint32_t color, int width) {
  if (!draw_interiors_) {
    const uint32_t gray = MakeBGRA(128, 128, 128, 255);
    color = gray;
  }

  for (int i = 0; i < width; ++i)
    *pixels++ = color;
}

// Quickly fill a rectangle with a solid color.
// If multithreading, this function is only called by the worker threads.
void Voronoi::wFillRect(int x, int y, int w, int h, uint32_t color) {
  const uint32_t stride_in_pixels = ps_context_->stride / sizeof(uint32_t);
  uint32_t* pixels = wGetAddr(x, y);
  for (int j = 0; j < h; j++) {
    wFillSpan(pixels, color, w);
    pixels += stride_in_pixels;
  }
}

// When recursive subdivision reaches a certain minimum without finding a
// rectangle that has four matching corners belonging to the same voronoi
// cell, this function will break the retangular 'tile' into smaller scanlines
//  and look for opportunities to quick fill at the scanline level.  If the
// scanline can't be quick filled, it will slow down even further and compute
// voronoi membership per pixel.
void Voronoi::wRenderTile(int x, int y, int w, int h) {
  // rip through a tile
  const uint32_t stride_in_pixels = ps_context_->stride / sizeof(uint32_t);
  uint32_t* pixels = wGetAddr(x, y);
  for (int j = 0; j < h; j++) {
    // get start and end cell values
    int ms = wCell(x + 0, y + j);
    int me = wCell(x + w - 1, y + j);
    // if the end points are the same, quick fill the span
    if (ms == me) {
      wFillSpan(pixels, colors_[ms], w);
    } else {
      // else compute each pixel in the span... this is the slow part!
      uint32_t* p = pixels;
      *p++ = colors_[ms];
      for (int i = 1; i < (w - 1); i++) {
        int m = wCell(x + i, y + j);
        *p++ = colors_[m];
      }
      *p++ = colors_[me];
    }
    pixels += stride_in_pixels;
  }
}

// Take a rectangular region and do one of -
//   If all four corners below to the same voronoi cell, stop recursion and
// quick fill the rectangle.
//   If the minimum rectangle size has been reached, break out of recursion
// and process the rectangle.  This small rectangle is called a tile.
//   Otherwise, keep recursively subdividing the rectangle into 4 equally
// sized smaller rectangles.
// If multithreading, this function is only called by the worker threads.
void Voronoi::wSubdivide(int x, int y, int w, int h) {
  int m;
  // if all 4 corners are equal, quick fill interior
  if (wTestRect(&m, x, y, w, h)) {
    wFillRect(x, y, w, h, colors_[m]);
  } else {
    // did we reach the minimum rectangle size?
    if ((w <= kMinRectSize) || (h <= kMinRectSize)) {
      wRenderTile(x, y, w, h);
    } else {
      // else recurse into smaller rectangles
      const int half_w = w / 2;
      const int half_h = h / 2;
      wSubdivide(x, y, half_w, half_h);
      wSubdivide(x + half_w, y, w - half_w, half_h);
      wSubdivide(x, y + half_h, half_w, h - half_h);
      wSubdivide(x + half_w, y + half_h, w - half_w, h - half_h);
    }
  }
}

// This function cuts up the rectangle into squares (preferably power-of-two).
// If multithreading, this function is only called by the worker threads.
void Voronoi::wRenderRect(int x, int y, int w, int h) {
  for (int iy = y; iy < (y + h); iy += kStartRecurseSize) {
    for (int ix = x; ix < (x + w); ix += kStartRecurseSize) {
      int iw = kStartRecurseSize;
      int ih = kStartRecurseSize;
      // Clamp width + height.
      if (ix + iw > ps_context_->width)
        iw = ps_context_->width - ix;
      if (iy + ih > ps_context_->height)
        ih = ps_context_->height - iy;
      if (iw <= 0 || ih <= 0)
        continue;

      wSubdivide(ix, iy, iw, ih);
    }
  }
}

// If multithreading, this function is only called by the worker threads.
void Voronoi::wRenderRegion(int region) {
  // convert region # into x0, y0, x1, y1 rectangle
  int x, y, w, h;
  wMakeRect(region, &x, &y, &w, &h);
  // render this rectangle
  wRenderRect(x, y, w, h);
}

// Entry point for worker thread.  Can't pass a member function around, so we
// have to do this little round-about.
void Voronoi::wRenderRegionEntry(int region, void* thiz) {
  static_cast<Voronoi*>(thiz)->wRenderRegion(region);
}

// Function Voronoi::UpdateSim()
// Run a simple sim to move the voronoi positions.  This update loop
// is run once per frame.  Called from the main thread only, and only
// when the worker threads are idle.
void Voronoi::UpdateSim() {
  ang_ += 0.002f;
  if (ang_ > kTwoPI) {
    ang_ = ang_ - kTwoPI;
  }
  float z = cosf(ang_) * 3.0f;
  // push the points around on the screen for animation
  for (int j = 0; j < kMaxPointCount; j++) {
    positions_[j].x += (velocities_[j].x) * z;
    positions_[j].y += (velocities_[j].y) * z;
    screen_positions_[j].x = positions_[j].x * ps_context_->width;
    screen_positions_[j].y = positions_[j].y * ps_context_->height;
  }
}

// Renders a small diamond shaped dot at x, y clipped against the window
void Voronoi::RenderDot(float x, float y, uint32_t color1, uint32_t color2) {
  const int ix = static_cast<int>(x);
  const int iy = static_cast<int>(y);
  const uint32_t stride_in_pixels = ps_context_->stride / sizeof(uint32_t);
  // clip it against window
  if (ix < 1) return;
  if (ix >= (ps_context_->width - 1)) return;
  if (iy < 1) return;
  if (iy >= (ps_context_->height - 1)) return;
  uint32_t* pixel = wGetAddr(ix, iy);
  // render dot as a small diamond
  *pixel = color1;
  *(pixel - 1) = color2;
  *(pixel + 1) = color2;
  *(pixel - stride_in_pixels) = color2;
  *(pixel + stride_in_pixels) = color2;
}

// Superimposes dots on the positions.
void Voronoi::SuperimposePositions() {
  const uint32_t white = MakeBGRA(255, 255, 255, 255);
  const uint32_t gray = MakeBGRA(192, 192, 192, 255);
  for (int i = 0; i < point_count_; i++) {
    RenderDot(
        screen_positions_[i].x, screen_positions_[i].y, white, gray);
  }
}

// Renders the Voronoi diagram, dispatching the work to multiple threads.
void Voronoi::Render() {
  workers_->Dispatch(num_regions_, wRenderRegionEntry, this);
  if (draw_points_)
    SuperimposePositions();
}

// Handle input events from the user and messages from JS.
void Voronoi::HandleEvent(PSEvent* ps_event) {
  // Give the 2D context a chance to process the event.
  if (0 != PSContext2DHandleEvent(ps_context_, ps_event))
    return;
  if (ps_event->type == PSE_INSTANCE_HANDLEINPUT) {
    // Convert Pepper Simple event to a PPAPI C++ event
    pp::InputEvent event(ps_event->as_resource);
    switch (event.GetType()) {
      case PP_INPUTEVENT_TYPE_TOUCHSTART:
      case PP_INPUTEVENT_TYPE_TOUCHMOVE: {
        pp::TouchInputEvent touches = pp::TouchInputEvent(event);
        uint32_t count = touches.GetTouchCount(PP_TOUCHLIST_TYPE_TOUCHES);
        // Touch points 0..n directly set position of points 0..n in
        // Voronoi diagram.
        for (uint32_t i = 0; i < count; i++) {
          pp::TouchPoint touch =
              touches.GetTouchByIndex(PP_TOUCHLIST_TYPE_TOUCHES, i);
          pp::FloatPoint point = touch.position();
          positions_[i].Set(point.x() / ps_context_->width,
                            point.y() / ps_context_->height);
        }
        break;
      }
      default:
        break;
    }
  } else if (ps_event->type == PSE_INSTANCE_HANDLEMESSAGE) {
    // Convert Pepper Simple message to PPAPI C++ var
    pp::Var var(ps_event->as_var);
    if (var.is_dictionary()) {
      pp::VarDictionary dictionary(var);
      std::string message = dictionary.Get("message").AsString();
      if (message == "draw_points")
        draw_points_ = dictionary.Get("value").AsBool();
      else if (message == "draw_interiors")
        draw_interiors_ = dictionary.Get("value").AsBool();
      else if (message == "set_points") {
        int num_points = dictionary.Get("value").AsInt();
        point_count_ = std::min(kMaxPointCount, std::max(0, num_points));
      } else if (message == "set_threads") {
        int thread_count = dictionary.Get("value").AsInt();
        delete workers_;
        workers_ = new ThreadPool(thread_count);
      }
    }
  }
}

// PostUpdateMessage() helper function for sendimg small messages to JS.
void Voronoi::PostUpdateMessage(const char* message_name, double value) {
  pp::VarDictionary message;
  message.Set("message", message_name);
  message.Set("value", value);
  PSInterfaceMessaging()->PostMessage(PSGetInstanceId(), message.pp_var());
}

void Voronoi::Update() {
  PSContext2DGetBuffer(ps_context_);
  if (NULL == ps_context_->data)
    return;

  UpdateSim();
  Render();
  PSContext2DSwapBuffer(ps_context_);

  double fps;
  if (FpsStep(&fps_state_, &fps))
    PostUpdateMessage("fps", fps);
}

// Starting point for the module.  We do not use main since it would
// collide with main in libppapi_cpp.
int example_main(int argc, char* argv[]) {
  Voronoi voronoi;
  while (true) {
    PSEvent* ps_event;
    // Consume all available events.
    while ((ps_event = PSEventTryAcquire()) != NULL) {
      voronoi.HandleEvent(ps_event);
      PSEventRelease(ps_event);
    }
    // Do simulation, render and present.
    voronoi.Update();
  }

  return 0;
}

// Register the function to call once the Instance Object is initialized.
// see: pappi_simple/ps_main.h
PPAPI_SIMPLE_REGISTER_MAIN(example_main);