优化图形绘制( 光栏法 )｜社区征文
前言
什么是 <光栏法>?它能做什么?
相信大家都有过图形绘制的案例.那么大家应该也都有遇到过绘制点位过多导致DrawCall暴涨的情况.
我们假设一个场景,例如: 需要一个画板的功能,用户可以再画板上随意绘制图形,之后实时将绘制的过程同步给其他用户;
这个时候我们将面临两大难题:
-
绘制N条线段后DrawCall增加导致掉帧卡顿;
-
产生点位数据太大,传输慢或丢包严重;
那么如何优化这两个问题呢?
首先我们得了解什么是 光栏法, 它能做什么?
简介
光栏法是一种矢量数据的压缩算法。
光栏法的基本思路是对每一条曲线上的所有点, 逐点定义一个扇形区域。若曲线的下一节点在扇形外, 则保留当前节点; 若曲线的下一节点在扇形内, 则舍去当前节点。
正文
在基本了解了算法的概念之后.我们就可以开始进入实践阶段,之后我会已比较简单的理解方式来阐述整个算法的核心;
创建画板
要实现上述功能,首先我们要在Creator 中创建一个画板;创建画板我们可以利用cc.graphics组件;
-
在Creator节点上添加一个空节点,绑上cc.graphics组件,通过对应参数对graphics进行设置;
-
创建一个脚本 Draw.js 并绑定在 drawLayout 节点上;
接下下来脚本中需要添加一些初始化设定个:
// 添加交互区域的 点击/移动/抬起 事件
// 处理每个事件
// 在move的时候取A,B两点画线
onLoad () {
this._startPoint = null;
this._draw = this.node.getComponent( cc.Graphics );
this._draw.lineWidth = 5;
this._points = [];
this.node.on( cc.Node.EventType.TOUCH_START, this._touchStart, this );
},
_touchStart ( e ) {
this._startPoint = this.node.convertToNodeSpaceAR( e.getLocation() );
this._draw.moveTo( this._startPoint.x, this._startPoint.y );
this.node.on( cc.Node.EventType.TOUCH_MOVE, this._touchMove, this );
this.node.on( cc.Node.EventType.TOUCH_END, this._touchEnded, this );
},
_touchMove ( e ) {
let location = this.node.convertToNodeSpaceAR( e.getLocation() );
this._draw.lineTo( location.x, location.y );
this._draw.stroke();
this._points.push( location );
},
_touchEnded ( e ) {
this.node.off( cc.Node.EventType.TOUCH_MOVE, this._touchMove, this );
this.node.off( cc.Node.EventType.TOUCH_END, this._touchEnded, this );
this._startPoint = null;
let location = this.node.convertToNodeSpaceAR( e.getLocation() );
}
这样一来,我们就得到了一个简易的画板,可以在画板上进行一些绘制操作;
这个时候,我们也能看到绘制组件暴露出来的问题, 一笔绘制的points达到了2288组,draw call 987,这对于一个简单的图形来说,已经很吃力了;
算法原理
初始化画板工作完成后,我们先来了解一下算法的原理,算法是通过怎样的形式优化point的;
首先,我们能确定的是绘制是通过AB连点相连得到的一条直线,而一个圆可以拆解成一个N个扇形;哪我们如何简化point呢?
假设1: 从(0,0)–(0,100)绘制一条直线,那么此时的points=[{0,0},{0,100}],只有两个点,但如果是通过ToucherMove来获取的点位信息绘制就可能得到point=[{0,0},{0,1},{0,2}…{0,100}],如果我们能识别它是一条直线,就可以将中间的点位全部省略;
假设2: 如果是一个不规则图形,例如圆弧,如图2-1:
这样我们可以看到,一个圆弧上由N个点组成,但如果把它分成N个扇形区域,然后舍去扇形区域内临近的点位,反复操作,直到点位缩小到我们设置的口径内?
接下来我们结合一下光栏法的原理,<每一条曲线上的所有点, 逐点定义一个扇形区域>;
设口径为d;两点坐标为p1,p2;连接p1和p2点,过 p2点作一条垂直于p1p2的直线,在该垂线上取两点a1和a2,使a1p2＝a2,p2＝d/2,此时a1和a2为“光栏”边界点,p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边,这就定义了一个扇形(这个扇形的口朝向曲线的前进方向,边长是任意的).通过p1并在扇形内的所有直线都具有这种性质,即p1p2上各点到这些直线的垂距都不大于d/2.
那么若p3点在扇形内,则舍去p2点.然后连接p1和p3,过p3作p1p1的垂线,该垂线与前面定义的扇形边交于c1和c2.在垂线上找到b1和b2点,使p3b1＝p3b2＝d/2,若b1或b2点落在原扇形外面,则用c1或c2取代,此时用p1b1和p1c2定义一个新的扇形,这当然是口径(b1c2)缩小了的“光栏”.
实现
了解完整个逻辑之后,我们就可以开始规划实现内容了,简单总结就是: 我们需要通过一个口径对绘制的图形创建无数个扇形区域,然后舍去扇形区域内相邻坐标的点位,以此循环操作;
举个"栗子":
设口径为: caliber
绘制点位为: points1.点是否在光栏内;
2.叉积判断
3.获取上下向量
4.点在光栏内处理
5.缩小口径
6.将有效点相连
现在有了光栏法的概念,有了需求,也有了逻辑走向,接下来就可以规划我们的代码块了.
- 设置光栏:
通过两点之间的距离和之前设定的口径(caliber),可以计算出光栏的角度(angle),用角度就能过得到上下两条射线的夹角,实际上这种就是通过角度和距离还获取向量;
let getLightBarVector = ( p1, p2, caliber ) => {
let len = this.pGetDistance( p1, p2 );
let angle = Math.atan2( caliber * 0.5, len );
let up = this.pRotate( p2.sub( p1 ), this.pForAngle( angle ) );
let down = this.pRotate( p2.sub( p1 ), this.pForAngle( -angle ) );
return { up, down };
}
- 判断点是否在光栏内,通过计算两点的叉积,可以的出点前AB点位是否处在我们设定好的光栏内;
let isInLightBar = ( up, down, p1, p ) => {
let line = p.sub(p1);
if ( line.cross( up ) >= 0 && line.cross( down ) <= 0 ) {
return true
}
return false
}
- 逐步缩小光栏区域:
let acosVector = ( v1, v2 ) => {
return Math.acos( v1.dot( v2 ) / ( v1.mag() * v2.mag() ) )
}
有了这三组核心算法之后,剩下的工作其实就是些遍历点位,持续判断的过程了.只要是 if(isInLightBar) 就证明连线的下一个点位是在光栏内的.可以被舍弃;
完整代码
simplifyLightBar ( points, caliber ) {
if ( caliber <= 0 ) {
return points;
}
if ( points.length < 2 ) {
return points
}
// 点是否在光栏内
// @param p1 光栏起始点
// @param p
let isInLightBar = ( up, down, p1, p ) => {
let line = p.sub(p1);
if ( line.cross( up ) >= 0 && line.cross( down ) <= 0 ) {
return true
}
return false
}
// 获取光栏上下向量
let getLightBarVector = ( p1, p2, caliber ) => {
let len = this.pGetDistance( p1, p2 );
let angle = Math.atan2( caliber * 0.5, len );
let up = this.pRotate( p2.sub( p1 ), this.pForAngle( angle ) );
let down = this.pRotate( p2.sub( p1 ), this.pForAngle( -angle ) );
return { up, down };
}
let acosVector = ( v1, v2 ) => {
return Math.acos( v1.dot( v2 ) / ( v1.mag() * v2.mag() ) )
}
let pointList = [];
for ( let p of points ) {
p.enable = true;
pointList.push( p );
}
let p1 = pointList[ 0 ];
let p2 = pointList[ 1 ];
let light = getLightBarVector( p1, p2, caliber );
let up = light.up;
let down = light.down;
let lastIndex = 1;
for ( let i = 2; i < pointList.length; i++ ) {
let p = pointList[ i ];
if ( isInLightBar( up, down, p1, p ) ) {
// 如果下一个点在光栏内，则删除上一个点，当前点为新p2
points[ i - 1 ].enable = false;
p2 = points[ i ];
let light = getLightBarVector( p1, p2, caliber );
let newUp = light.up, newDown = light.down;
// 缩小光栏口径
let p1p2 = p2.sub(p1);
// 缩小光栏口径
if ( acosVector( p1p2, newDown ) < acosVector( p1p2, down ) ) {
down = newDown;
}
if ( acosVector( p1p2, newUp ) < acosVector( p1p2, up ) ) {
up = newUp;
}
} else {
// 如果不在，则保留上一个点，以上一个点为新p1
points[ i - 1 ].enable = true;
p1 = points[ i - 1 ];
p2 = points[ i ];
let light = getLightBarVector( p1, p2, caliber );
up = light.up;
down = light.down;
// 上一个有效点到现在有效点直线， 之间如果有回折，那最末端的点应该保留
let lastPoint = points[ lastIndex ];
let maxDis = 0;
let maxDisIndex = 0;
for ( let i = lastIndex; i > 0; i-- ) {
let dis = this.pGetDistance( lastPoint, points[ i ] );
if ( dis > maxDis ) {
maxDis = dis;
maxDisIndex = i;
}
}
if ( maxDis - this.pGetDistance( lastPoint, p1 ) > caliber ) {
points[ maxDisIndex ].enable = true;
}
lastIndex = i - 1;
}
}
let newPoints = [];
for ( let p of points ) {
if ( p.enable ) {
newPoints.push( cc.v2( p.x, p.y ) );
}
}
return newPoints
}
代码部分已经完成了,接下来我们来看看效果;
caliber = 10;
现在我们看到非常明显的变化.但是弧线看起来还不太圆润,因为优化后的点位很少.所有我们还有把口径调小的空间;
caliber = 3;
那么现在的这个效果看上去就很平滑了,而优化的程度达到了**80%**以上.效果还是很不错的;
总结
到此,整个光栏法的核心部分就已经全部介绍完毕了,后续会更大家分享一些关于绘图的高级用法和优化;感谢大伙抽空看完此篇文章,如有纰漏或者其他想法的同学,欢迎评论区一起探讨!