Regenerate Points 實現(xiàn)解析！ Marching Squares !
編輯器里
Regenerate Points功能怎么實現(xiàn)？節(jié)點動態(tài)加載了spriteFrame,怎么重新獲取碰撞組件多邊形頂點數(shù)組points?
背景
在 Cocos Creator 編輯中，多邊形碰撞組件中有一個 Regenerate Points 的功能，這個功能可以根據(jù)組件依附的節(jié)點上的 Sprite 組件的貼圖的像素點來自動生成相應輪廓的頂點。Threshold 指明生成貼圖輪廓頂點間的最小距離，值越大則生成的點越少。
白玉無冰源于興趣，對其中的實現(xiàn)做一些研究。最終研究成果如下文所示。
實現(xiàn)
編輯器中的實現(xiàn)主要以下幾步：
讀取圖片所有的像素點數(shù)據(jù) 計算圍成輪廓的像素點 計算頂點(處理 Threshold)對結(jié)果進行坐標轉(zhuǎn)換
以下是在 Canvas 中計算輪廓(紅邊)和和計算頂點(藍點)的效果。
獲取像素點數(shù)據(jù)
編輯中讀取像素數(shù)據(jù)用了sharp這個庫去讀取。
白玉無冰這里采用 Canvas 獲取圖片像素數(shù)據(jù)。
const?img?=?new?Image();
img.crossOrigin?=?'anonymous';
img.src?=?'./白玉無冰.png';
const?canvas?=?document.getElementById('canvas');
const?ctx?=?canvas.getContext('2d');
img.onload?=?function?()?{
????main();
};
const?main?=?function?()?{
????ctx.clearRect(0,?0,?canvas.width,?canvas.height);
????ctx.drawImage(img,?0,?0);
????const?canvasImageData?=?ctx.getImageData(0,?0,?canvas.width,?canvas.height);
????const?data?=?canvasImageData.data;
????//?data?就是像素數(shù)據(jù)，從左往右，從上往下的像素數(shù)據(jù)
}
計算圍成輪廓的像素點
核心思路是參考 Marching Squares 算法：
先從上到下，從左到右的順序，找到第一個不透明的點。 根據(jù)當前點的 左上/左邊/上邊/當前點 四個點的透明值計算一個值，根據(jù)這個值判斷往哪個方向移動 移動后繼續(xù)計算，繼續(xù)移動，直到回到第一個點
簡單來說就是，找一個點，然后逆時針環(huán)繞一圈。
先看看如何根據(jù)當前點周圍的透明度值計算一個值，這里巧妙地使用了二進制相加，可以通過和判斷不同情況。
/*
checking?the?2x2?pixel?grid,?assigning?these?values?to?each?pixel,?if?not?transparent
+---+---+
|?1?|?2?|
+---+---+
|?4?|?8?|?<-?current?pixel?(curx,cury)
+---+---+
*/
//?以下為偽代碼
let?state?=?0;
let?tl?=?{x:(x-1),?y:(y-1)}
state?+=?(containsPoint(tl)&&getAlphaByPos(tl)>0)??1:0;
let?tr?=?{x:(x-1),?y:(y)}
state?+=?(containsPoint(tr)&&getAlphaByPos(tr)>0)??2:0;
let?bl?=?{x:(x-1),?y:(y)}
state?+=?(containsPoint(bl)&&getAlphaByPos(bl)>0)??4:0;
let?br?=?{x:(x),?y:(y)}
state?+=?(containsPoint(br)&&getAlphaByPos(br)>0)??8:0;
根據(jù)不同的值，走不同的方向。
這里簡單解釋一下為何是這么走，因為我們考慮的是逆時針行走，所有箭頭方向的左側(cè)必須有像素，箭頭方向的右側(cè)必須不能有像素。
整合一下，完整的JS代碼如下:
const?marching_squares?=?{
????NONE:?0,
????UP:?1,
????LEFT:?2,
????DOWN:?3,
????RIGHT:?4,
????getBlobOutlinePoints:?function?(data,?width,?height,?loop)?{
????????marching_squares.data?=?data,
????????????marching_squares.width?=?width,
????????????marching_squares.height?=?height,
????????????marching_squares.loop?=?loop;
????????var?p?=?marching_squares.getFirstNonTransparentPixelTopDown(),
????????????result?=?marching_squares.walkPerimeter(p.x,?p.y);
????????return?marching_squares.width?=?null,
????????????marching_squares.height?=?null,
????????????marching_squares.data?=?null,
????????????marching_squares.loop?=?null,
????????????result
????},
????getFirstNonTransparentPixelTopDown:?function?()?{
????????var?t,?a,?data?=?marching_squares.data,
????????????width?=?marching_squares.width,
????????????height?=?marching_squares.height,
????????????s?=?0;
????????for?(t?=?0;?t?for?(a?=?0;?a?4)?if?(data[s?+?3]?>?0)?return?{
????????????x:?a,
????????????y:?t
????????};
????????return?null
????},
????walkPerimeter:?function?(pos_x,?pos_y)?{
????????pos_x?0?&&?(pos_x?=?0),
????????????pos_x?>?marching_squares.width?&&?(pos_x?=?marching_squares.width),
????????????pos_y?0?&&?(pos_y?=?0),
????????????pos_y?>?marching_squares.height?&&?(pos_y?=?marching_squares.height);
????????var?x?=?pos_x,
????????????y?=?pos_y,
????????????result?=?[{?x,?y?}];
????????do?{
????????????switch?(marching_squares.step(x,?y,?marching_squares.data),?marching_squares.nextStep)?{
????????????????case?marching_squares.UP:
????????????????????y--;
????????????????????break;
????????????????case?marching_squares.LEFT:
????????????????????x--;
????????????????????break;
????????????????case?marching_squares.DOWN:
????????????????????y++;
????????????????????break;
????????????????case?marching_squares.RIGHT:
????????????????????x++
????????????}
????????????x?>=?0?&&?x?<=?marching_squares.width?&&?y?>=?0?&&?y?<=?marching_squares.height?&&?result.push({?x,?y?})
????????}?while?(x?!==?pos_x?||?y?!==?pos_y);
????????return?marching_squares.loop?&&?result.push({?x,?y?}),
????????????result
????},
????step:?function?(x,?y,?data)?{
????????var?width?=?marching_squares.width,
????????????rowOffset?=?4?*?width,
????????????upLeftIndex?=?(y?-?1)?*?rowOffset?+?4?*?(x?-?1),
????????????isInLeft?=?x?>?0,
????????????isInRight?=?x?????????????isInDown?=?y?????????????isInUp?=?y?>?0;
????????marching_squares.upLeft?=?isInUp?&&?isInLeft?&&?data[upLeftIndex?+?3]?>?0;
????????marching_squares.upRight?=?isInUp?&&?isInRight?&&?data[upLeftIndex?+?7]?>?0;
????????marching_squares.downLeft?=?isInDown?&&?isInLeft?&&?data[upLeftIndex?+?rowOffset?+?3]?>?0;
????????marching_squares.downRight?=?isInDown?&&?isInRight?&&?data[upLeftIndex?+?rowOffset?+?7]?>?0;
????????marching_squares.previousStep?=?marching_squares.nextStep;
????????marching_squares.state?=?0;
????????marching_squares.upLeft?&&?(marching_squares.state?|=?1);
????????marching_squares.upRight?&&?(marching_squares.state?|=?2);
????????marching_squares.downLeft?&&?(marching_squares.state?|=?4);
????????marching_squares.downRight?&&?(marching_squares.state?|=?8);
????????switch?(marching_squares.state)?{
????????????case?1:
????????????????marching_squares.nextStep?=?marching_squares.UP;
????????????????break;
????????????case?2:
????????????case?3:
????????????????marching_squares.nextStep?=?marching_squares.RIGHT;
????????????????break;
????????????case?4:
????????????????marching_squares.nextStep?=?marching_squares.LEFT;
????????????????break;
????????????case?5:
????????????????marching_squares.nextStep?=?marching_squares.UP;
????????????????break;
????????????case?6:
????????????????marching_squares.previousStep?==?marching_squares.UP???marching_squares.nextStep?=?marching_squares.LEFT?:?marching_squares.nextStep?=?marching_squares.RIGHT;
????????????????break;
????????????case?7:
????????????????marching_squares.nextStep?=?marching_squares.RIGHT;
????????????????break;
????????????case?8:
????????????????marching_squares.nextStep?=?marching_squares.DOWN;
????????????????break;
????????????case?9:
????????????????marching_squares.previousStep?==?marching_squares.RIGHT???marching_squares.nextStep?=?marching_squares.UP?:?marching_squares.nextStep?=?marching_squares.DOWN;
????????????????break;
????????????case?10:
????????????case?11:
????????????????marching_squares.nextStep?=?marching_squares.DOWN;
????????????????break;
????????????case?12:
????????????????marching_squares.nextStep?=?marching_squares.LEFT;
????????????????break;
????????????case?13:
????????????????marching_squares.nextStep?=?marching_squares.UP;
????????????????break;
????????????case?14:
????????????????marching_squares.nextStep?=?marching_squares.LEFT;
????????????????break;
????????????default:
????????????????marching_squares.nextStep?=?marching_squares.NONE
????????}
????}
};
對應之前的canvas中的數(shù)據(jù)，就可以獲得輪廓的像素點。
let?blobOutlinePoints?=?marching_squares.getBlobOutlinePoints(data,?canvas.width,?canvas.height,?true);
計算頂點
上面得到的像素點過于密集，比如同一直線上只需要兩個點，距離太近的點是否需要截取？
編輯器內(nèi)是這么做的：
先拿出起始點和終點 找出一個中間點，該點到 起點和終點連成的直線 的距離最大 判斷這個距離 如果大于 Threshold，把這些點根據(jù)中間分成兩份，繼續(xù)第一步，再把兩份拼接起來。如果小于 Threshold，返回[起點，終點]
這里涉及了一個點到直接的距離公式。
將上面的設計轉(zhuǎn)成代碼如下：
const?pointLineDistance?=?function?(point,?linePointBegin,?linePointEnd)?{
????let?result,?k,?b;
????if?(linePointBegin.x?===?linePointEnd.x)?{
????????result?=?Math.abs(point.x?-?linePointBegin.x)
????}?else?{
????????//?y?=?kx?+?b
????????k?=?(linePointEnd.y?-?linePointBegin.y)?/?(linePointEnd.x?-?linePointBegin.x);
????????b?=?linePointBegin.y?-?k?*?linePointBegin.x;
????????//?kx?-?y?+?b?=?0
????????result?=?Math.abs(k?*?point.x?-?point.y?+?b)?/?Math.sqrt(Math.pow(k,?2)?+?1);
????}
????return?result
}
const?rdp?=?function?rdp(points,?threshold)?{
????var?point0?=?points[0],
????????point_end?=?points[points.length?-?1];
????if?(points.length?3)?return?points;
????for?(var?slice_index?=?-1,?max_dis?=?0,?index?=?1;?index?1;?index++)?{
????????var?cur_dis?=?pointLineDistance(points[index],?point0,?point_end);
????????cur_dis?>?max_dis?&&?(max_dis?=?cur_dis,?slice_index?=?index)
????}
????if?(max_dis?>?threshold)?{
????????var?left_poins?=?points.slice(0,?slice_index?+?1),
????????????right_points?=?points.slice(slice_index),
????????????left_rdp?=?rdp(left_poins,?threshold),
????????????right_rdp?=?rdp(right_points,?threshold);
????????return?left_rdp.slice(0,?left_rdp.length?-?1).concat(right_rdp)
????}
????return?[point0,?point_end]
};
對應之前的輪廓的像素點，可以得到頂點數(shù)據(jù)。
const?contourPoints?=?rdp(blobOutlinePoints,?config.threshold);
最后處理
因為 Canvas 的坐標系是左上角，與紋理數(shù)據(jù)相符，所以在這個Demo中并不需要處理。
然而，在編輯中，節(jié)點的坐標系與紋理的坐標系不同，需要根據(jù)錨點等參數(shù)再做一次轉(zhuǎn)換，以下是編輯器的處理代碼。
最后
示例 Demo 地址:?
https://lamyoung.gitee.io/web/marching_squares/
本 Demo 僅在一個 Canvas 中實現(xiàn)簡易展示效果, 并未融入Cocos Creator的項目中。若要融入項目，重點要解決如何獲取圖片的像素數(shù)據(jù)，本Demo使用了 canvas的接口，可供參考。
這個算法存在一個問題，只會對第一個不透明的點計算輪廓頂點。如果圖片中有多個輪廓，可以統(tǒng)計之前以遍歷過的點，以及包圍的點，繼續(xù)算下一個輪廓。
最后分享一個大佬那拿到的神秘代碼，不太好直接給出，需要的進一步研究的可以參考使用。
Ly/miZPlvIAyLjTnvJbovpHlmajnmoTosIPor5XnlYzpnaLvvIzlsIbov5nmrrXku6PnoIHlpI3liLbliLDmjqfliLblj7Dlubblm57ovaYKdmFyIGZzID0gcmVxdWlyZSgiZnMiKTsKICAgIHZhciBwYXRoID0gcmVxdWlyZSgicGF0aCIpCiAgICB2YXIgYXBwID0gcmVxdWlyZSgiZWxlY3Ryb24iKS5yZW1vdGUuYXBwOwogICAgLy8gdmFyIGZzaiA9IHJlcXVpcmUoImZzLWpldHBhY2siKTsKICAgIC8vIGV4YW1wbGUgdXNhZ2UgOiBjb3B5RmlsZU91dHNpZGVPZkVsZWN0cm9uQXNhciggIm15Rm9sZGVySW5zaWRlVGhlQXNhckZpbGUiLCBhcHAuZ2V0UGF0aCgidGVtcCIpICsgImNvbS5ibGEuYmxhIgogICAgdmFyIGNvcHlGaWxlT3V0c2lkZU9mRWxlY3Ryb25Bc2FyID0gZnVuY3Rpb24gKHNvdXJjZUluQXNhckFyY2hpdmUsIGRlc3RPdXRzaWRlQXNhckFyY2hpdmUpIHsKICAgICAgICBpZiAoZnMuZXhpc3RzU3luYyhwYXRoLnJlc29sdmUoYXBwLmdldEFwcFBhdGgoKSxzb3VyY2VJbkFzYXJBcmNoaXZlKSkpIHsKICAgICAgICAgICAvLyBjb25zb2xlLmxvZygi5byA5aeLIik7Ci8vY29uc29sZS5sb2co6Lev5b6EOithcHAuZ2V0QXBwUGF0aCgpICsgIi8iICsgc291cmNlSW5Bc2FyQXJjaGl2ZSk7ICAgICAgICAgICAgCiAgICAgICAgICAgIC8vIGZpbGUgd2lsbCBiZSBjb3BpZWQKICAgICAgICAgICAgaWYgKGZzLnN0YXRTeW5jKGFwcC5nZXRBcHBQYXRoKCkgKyAiLyIgKyBzb3VyY2VJbkFzYXJBcmNoaXZlKS5pc0ZpbGUoKSkgewogICAgICAgICAgICAgICAgLy9jb25zb2xlLmxvZygi5aSN5Yi25paH5Lu2IikKICAgICAgICAgICAgICAgIGxldCBmaWxlID0gZGVzdE91dHNpZGVBc2FyQXJjaGl2ZSAKICAgICAgICAgICAgICAgIGxldCBkaXIgPSBwYXRoLmRpcm5hbWUoZmlsZSk7CiAgICAgICAgICAgICAgICBpZiAoIWZzLmV4aXN0c1N5bmMoZGlyKSkgewogICAgICAgICAgICAgICAgICAgIGZzLm1rZGlyU3luYyhkaXIsIHsgcmVjdXJzaXZlOiB0cnVlIH0pOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZnMud3JpdGVGaWxlU3luYyhmaWxlLCBmcy5yZWFkRmlsZVN5bmMoYXBwLmdldEFwcFBhdGgoKSArICIvIiArIHNvdXJjZUluQXNhckFyY2hpdmUpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICAvLyBkaXIgaXMgYnJvd3NlZAogICAgICAgICAgICBlbHNlIGlmIChmcy5zdGF0U3luYyhhcHAuZ2V0QXBwUGF0aCgpICsgIi8iICsgc291cmNlSW5Bc2FyQXJjaGl2ZSkuaXNEaXJlY3RvcnkoKSkgewogICAgICAgICAgICAgICAgLy9jb25zb2xlLmxvZygi5aSN5Yi25paH5Lu25aS5IikKICAgICAgICAgICAgICAgIGZzLnJlYWRkaXJTeW5jKGFwcC5nZXRBcHBQYXRoKCkgKyAiLyIgKyBzb3VyY2VJbkFzYXJBcmNoaXZlKS5mb3JFYWNoKGZ1bmN0aW9uIChmaWxlT3JGb2xkZXJOYW1lKSB7CiAgICAgICAgICAgICAgICAgICAgY29weUZpbGVPdXRzaWRlT2ZFbGVjdHJvbkFzYXIoc291cmNlSW5Bc2FyQXJjaGl2ZSArICIvIiArIGZpbGVPckZvbGRlck5hbWUsIGRlc3RPdXRzaWRlQXNhckFyY2hpdmUgKyAiLyIgKyBmaWxlT3JGb2xkZXJOYW1lKTsKICAgICAgICAgICAgICAgIH0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQovL+eEtuWQjuWcqOaOp+WItuWPsO+8jOaJp+ihjOS7peS4i+mAu+i+ke+8jOebruagh+aWh+S7tuWkuei3r+W+hO+8jOiHquW3seS/ruaUuQpjb3B5RmlsZU91dHNpZGVPZkVsZWN0cm9uQXNhcigiLi8iLCJEOlxcQ29jb3NEYXNoYm9hcmRfMS4wLjhcXHJlc291cmNlc1xcLmVkaXRvcnNcXENyZWF0b3JcXDIuNC40XFxyZXNvdXJjZXNcXGFwcCIp
參考資料
https://en.wikipedia.org/wiki/Marching_squares
https://github.com/cocos2d/cocos2d-x/blob/v3/cocos/2d/CCAutoPolygon.cpp
https://developer.mozilla.org/en-US/docs/Web/API/Canvas_API/Tutorial/Pixel_manipulation_with_canvas
https://github.com/lovell/sharp
以上為白玉無冰關(guān)于 Regenerate Points 實現(xiàn)解析 的分享，歡迎大家留言討論。
如切如磋，如琢如磨。
關(guān)于泰勒公式展開
寫一個位圖字體制作工具
替代 toDataURL 的方案
Fake3D && Shader
MatCap && Shader
如何抄shader
3D折紙
更多精彩歡迎關(guān)注微信公眾號
點擊“閱讀原文”查看精選導航
“點贊“ ”在看”?鼓勵一下
▼
評論
圖片
表情