正文

在上篇文章我們討論了使用 臟矩形渲染，通過(guò)重渲染局部的圖形來(lái)提優(yōu)化 Canvas 的性能，將 GPU 密集轉(zhuǎn)換為 CPU  密集。

看這篇文章《Canvas 性能優(yōu)化：臟矩形渲染》

CPU 密集在哪？

在需要遍歷 所有的圖形，判斷它們是否和臟矩形發(fā)生相交（碰撞），保存發(fā)生碰抓給你的圖形，將它們?cè)诰植窟M(jìn)行重繪。

有沒(méi)有辦法減少需要遍歷的圖形，不要遍歷全部的圖形，而是少量的圖形呢？有一個(gè)辦法是使用 四叉樹(shù)。

四叉樹(shù)碰撞檢測(cè)原理

我們將區(qū)域的分割表述為 “節(jié)點(diǎn)”，因?yàn)槭撬牟鏄?shù)；

將畫(huà)布上的真實(shí)圖形就叫做 “圖形”。

四叉樹(shù)本質(zhì)使用了 空間分割，給圖形加 索引，將視口界面分割成多個(gè)區(qū)域，每個(gè)區(qū)域記住自己包含了哪些圖形。

然后移動(dòng)目標(biāo)圖形時(shí)，判斷它落在哪個(gè)區(qū)域，取出所在區(qū)域的圖形，這些圖形集合就是和目標(biāo)圖形發(fā)生碰撞圖形的超集。

這些區(qū)域外的圖形就被我們排除了。

算法實(shí)現(xiàn)的要點(diǎn)：

創(chuàng)建根節(jié)點(diǎn)，根節(jié)點(diǎn)保存區(qū)域的信息 x、y、width 和 height。

添加圖形時(shí)，當(dāng)一個(gè)節(jié)點(diǎn)內(nèi)的節(jié)點(diǎn)數(shù)量大于閥值，就將整個(gè)區(qū)域均等切割為 4 等份的子節(jié)點(diǎn)，將圖形從當(dāng)前區(qū)域取出，重新放入到這些子節(jié)點(diǎn)內(nèi)，從而將節(jié)點(diǎn)的歸屬劃分為更小的區(qū)域。

（原來(lái)的區(qū)域轉(zhuǎn)換為索引層，真正保存節(jié)點(diǎn)的地方放到了它的子區(qū)域上）

當(dāng)我們提供一個(gè)碰撞矩形，我們從四叉樹(shù)頂節(jié)點(diǎn)往下找，看是否有子節(jié)點(diǎn)。如果有，使用矩形碰撞算法找出它所在的子節(jié)點(diǎn)有哪些（可能有多個(gè)）。對(duì)這些子節(jié)點(diǎn)重復(fù)前面的操作，進(jìn)行遞歸，找到所有的圖形。

這些圖形就是碰撞矩形可能相交的矩形，但相對(duì)所有圖形，又不至于太多。

四叉樹(shù)碰撞檢測(cè)算法

先看看經(jīng)典算法實(shí)現(xiàn)。

算法我就不自己實(shí)現(xiàn)了，這里展示 quadtree-js 庫(kù)的代碼實(shí)現(xiàn)。

github.com/timohausman…

構(gòu)造函數(shù)：

function Quadtree(bounds, max_objects, max_levels, level) {
  this.max_objects = max_objects || 10; // 節(jié)點(diǎn)內(nèi)最大對(duì)象數(shù)量
  this.max_levels = max_levels || 4; // 樹(shù)的最大深度
  this.level = level || 0;
  this.bounds = bounds; // 區(qū)域，結(jié)構(gòu)為 {x, y, width, height}
  this.objects = []; // 保存圖形的地方
  this.nodes = []; // 4 個(gè)子節(jié)點(diǎn)，到達(dá)閥值時(shí)才創(chuàng)建
}

這是一個(gè)內(nèi)部私有方法，當(dāng)節(jié)點(diǎn)內(nèi)圖形過(guò)多，超過(guò)閥值，就將當(dāng)前節(jié)點(diǎn)分 裂成 4 個(gè)子節(jié)點(diǎn)：

// 切割：生成 4 個(gè)子節(jié)點(diǎn)
Quadtree.prototype.split = function () {
  var nextLevel = this.level + 1,
    subWidth = this.bounds.width / 2,
    subHeight = this.bounds.height / 2,
    x = this.bounds.x,
    y = this.bounds.y;
  // 右上
  this.nodes[0] = new Quadtree(
    {
      x: x + subWidth,
      y: y,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
  // 左上
  this.nodes[1] = new Quadtree(
    {
      x: x,
      y: y,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
  // 左下
  this.nodes[2] = new Quadtree(
    {
      x: x,
      y: y + subHeight,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
  // 右下
  this.nodes[3] = new Quadtree(
    {
      x: x + subWidth,
      y: y + subHeight,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
};

計(jì)算某個(gè)圖形落在當(dāng)前節(jié)點(diǎn)的哪個(gè)子節(jié)點(diǎn)，拿到對(duì)應(yīng)節(jié)點(diǎn)索引值數(shù)組：

// 找到某個(gè) box 落在在哪個(gè)區(qū)域
Quadtree.prototype.getIndex = function (pRect) {
  var indexes = [],
    verticalMidpoint = this.bounds.x + this.bounds.width / 2,
    horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
  var startIsNorth = pRect.y < horizontalMidpoint,
    startIsWest = pRect.x < verticalMidpoint,
    endIsEast = pRect.x + pRect.width > verticalMidpoint,
    endIsSouth = pRect.y + pRect.height > horizontalMidpoint;
  // top-right quad
  if (startIsNorth && endIsEast) {
    indexes.push(0);
  }
  // top-left quad
  if (startIsWest && startIsNorth) {
    indexes.push(1);
  }
  // bottom-left quad
  if (startIsWest && endIsSouth) {
    indexes.push(2);
  }
  // bottom-right quad
  if (endIsEast && endIsSouth) {
    indexes.push(3);
  }
  return indexes;
};

插入一個(gè)圖形，先看是否存在子節(jié)點(diǎn)，有的話(huà)說(shuō)明當(dāng)前節(jié)點(diǎn)變成了索引層，通過(guò)矩形碰撞算法找到所在的子節(jié)點(diǎn)，對(duì)這些子節(jié)點(diǎn)做插入操作：

Quadtree.prototype.insert = function (pRect) {
  var i = 0,
    indexes;
  // 存在子節(jié)點(diǎn)，則插入到子節(jié)點(diǎn)
  if (this.nodes.length) { 
    indexes = this.getIndex(pRect); // 找到索引位置
    for (i = 0; i < indexes.length; i++) {
      this.nodes[indexes[i]].insert(pRect); // 遞歸 insert
    }
    return;
  }
  // 沒(méi)有子節(jié)點(diǎn)，不是索引層，圖形放到前節(jié)點(diǎn)下
  // （有個(gè)小 BUG，就是不在范圍內(nèi)的圖形也加上去了）
  this.objects.push(pRect);
  // 如果對(duì)象太多，構(gòu)建子節(jié)點(diǎn)
  if (
    this.objects.length > this.max_objects &&
    this.level < this.max_levels
  ) {
    if (!this.nodes.length) {
      this.split();
    }
    // 將 objects 取出，放入這些子節(jié)點(diǎn)中
    for (i = 0; i < this.objects.length; i++) {
      indexes = this.getIndex(this.objects[i]);
      for (var k = 0; k < indexes.length; k++) {
        this.nodes[indexes[k]].insert(this.objects[i]);
      }
    }
    this.objects = [];
  }
};

返回目標(biāo)圖形所在節(jié)點(diǎn)下的所有圖形：

// 傳入一個(gè)矩形，取出它所在節(jié)點(diǎn)的所有矩形
// 這個(gè)方法能返回
Quadtree.prototype.retrieve = function (pRect) {
  // 提取目標(biāo)矩形所在區(qū)間下的所有矩形
  var indexes = this.getIndex(pRect),
    returnObjects = this.objects;
  // 可能需要遞歸。
  //if we have subnodes, retrieve their objects
  if (this.nodes.length) {
    for (var i = 0; i < indexes.length; i++) {
      returnObjects = returnObjects.concat(
        this.nodes[indexes[i]].retrieve(pRect)
      );
    }
  }
  // 移除重復(fù)的節(jié)點(diǎn)
  returnObjects = returnObjects.filter(function (item, index) {
    return returnObjects.indexOf(item) >= index;
  });
  return returnObjects;
};

非常簡(jiǎn)單，一些可以改善的能力。

• 沒(méi)有添加映射功能，最后返回的圖形都是 box 對(duì)象信息，我們可以考慮改造為 insert(rect, data)，保存額外的信息，比如實(shí)際形狀對(duì)象或 id。
• 動(dòng)態(tài)收縮：移除某個(gè)圖形后更新樹(shù)結(jié)構(gòu)，并在發(fā)現(xiàn)圖形數(shù)量低于閥值時(shí)，取出圖形放到父節(jié)點(diǎn)上，銷(xiāo)毀子節(jié)點(diǎn)；
• 修改根節(jié)點(diǎn)范圍 后，需要重置整棵樹(shù)，如何高效重置等；
• 四叉樹(shù)的圖形類(lèi)型，常見(jiàn)的是矩形，但還可以是點(diǎn)、直線、曲線等，如果需要可以考慮支持。

請(qǐng)根據(jù)實(shí)際需要進(jìn)行擴(kuò)展。

一些權(quán)衡

處于節(jié)點(diǎn)內(nèi)分割線上的圖形，它是歸屬于多個(gè)子節(jié)點(diǎn)的，所以最終會(huì)同時(shí)放到它的多個(gè)子節(jié)點(diǎn)下，會(huì)花費(fèi)內(nèi)存。

極端情況下，一個(gè)非常大的圖形，會(huì)保存在所有的節(jié)點(diǎn)下。

如果想節(jié)省內(nèi)存，可以直接保存到當(dāng)前節(jié)點(diǎn)上，不放到子節(jié)點(diǎn)上，可以減少內(nèi)存使用，只是最后返回的被碰撞圖形會(huì)多一點(diǎn)。因?yàn)閳D形可能只壓在了兩個(gè)子節(jié)點(diǎn)的交界線上，比如 A、 B ，但目標(biāo)矩形是在其他的子節(jié)點(diǎn) C 上，但因?yàn)樗鼈儊?lái)自同一個(gè)父節(jié)點(diǎn)，所以拿到了這個(gè)不可能在 C 的圖形。

后者會(huì)更好一些，但如果一個(gè)圖形剛好在畫(huà)布中心，那每次取出的碰撞圖形都會(huì)有它（這點(diǎn)可以通過(guò)松散四叉樹(shù)解決）。

松散四叉樹(shù)

經(jīng)典四叉樹(shù)有個(gè)問(wèn)題，就是如果圖形的物理信息是比較動(dòng)態(tài)的，當(dāng)總是在邊界附近時(shí)，就會(huì)發(fā)生頻繁地將圖形從一個(gè)節(jié)點(diǎn)取出并放到另個(gè)節(jié)點(diǎn)下。

對(duì)此我們可以額外設(shè)置一個(gè)出口邊界。這個(gè)出口邊界要比入口邊界要大，只有當(dāng)圖形離開(kāi)這個(gè)出口邊界，才會(huì)更新提取圖形到新的節(jié)點(diǎn)。

這樣，當(dāng)圖形劃分到另一個(gè)節(jié)點(diǎn)上時(shí)，就 需要移動(dòng)較長(zhǎng)的距離才能回到原來(lái)節(jié)點(diǎn)下，輕微地移動(dòng)不會(huì)導(dǎo)致劇烈的更新。

通常出口邊界邊長(zhǎng)為入口邊界的兩倍最佳，為什么不知道，經(jīng)驗(yàn)之談。

其他空間分割思想的算法

簡(jiǎn)單介紹一些也使用了 空間分割 思想的算法。

• 跳表：一種有序鏈表，通過(guò)疊加大量的索引層，可以進(jìn)行鏈表形式的 “二分查找”，達(dá)到高效的 O(logn) 時(shí)間復(fù)雜度，但也帶來(lái)了內(nèi)存的消耗。Redis 中的有序集合（Sorted Set）底層使用了跳表，一個(gè)原因是可以高效地獲取區(qū)間內(nèi)的數(shù)據(jù)集；
• B+ 樹(shù)：一種平衡二叉樹(shù)，有點(diǎn)像跳表，但樹(shù)的層數(shù)最多為三層，MySQL 的索引實(shí)現(xiàn)使用了 B+ 樹(shù)，因?yàn)閷訑?shù)較少，可以減少 IO 操作；
• R 樹(shù)：R 表示矩形的意思。相比前面兩種單維的范圍查找，R 樹(shù)能做高效的高維查找。比如地圖中，我們可以通過(guò) R 樹(shù)將 距離 相近的高維圖形合并為一個(gè)大節(jié)點(diǎn)，當(dāng)搜索 “2km 內(nèi)的藥店” 時(shí)，如果你落到某個(gè)大節(jié)點(diǎn)上，我們只要遍歷一個(gè)大節(jié)點(diǎn)下的所有節(jié)點(diǎn)，而不是遍歷整個(gè)市，或整個(gè)國(guó)家。

R 樹(shù)的思路是最接近四叉樹(shù)的，它其實(shí)是另一種 減少圖形遍歷的方案，可以適用于高效剔除視口范圍之外的圖形。

R 樹(shù)有個(gè) star 數(shù)很多的庫(kù)，叫做 RBush，感興趣可以看看。

github.com/mourner/rbu…

以上就是JS快速檢索碰撞圖形之四叉樹(shù)碰撞檢測(cè)的詳細(xì)內(nèi)容，更多關(guān)于JS四叉樹(shù)碰撞檢測(cè)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論