Jan 19

用栅格化的思维进行地图散点数据绘制

Lrdcq , 2019/01/19 21:45 , 程序 , 閱讀(814) , Via 本站原創
原理上,这个课题利用point做粒子效果就可以解决,本不需要通过shader去处理。不过作为用gl的思维进行地图栅格数据绘制课题的后续,还是提出以下。本方案的核心思路还是数据栅格化,降纬处理数据减少碰撞测试次数提升性能。
Demo:http://lrdcq.com/test/mapwebgltiles/scatter/

思路

对于地图上的散点数据,我们还是将他们落到格子里:

1. 将地图区域划为MxN个格子,每个格子里会有0-x个点的经纬度数据,如果划分得相对合理,我们的x将极小(demo里总数据量约7w+,x为6)。

2. 假设我的栅格的大小为(x,y),如果我的每个点的绘制区域的大小也正好是(m,n)=(x,y),如下图

點擊在新視窗中瀏覽此圖片

那我每一个栅格里点的绘制区域都有可能覆盖到3x3共计9个栅格的像素。同理,对于任意(m,n)的绘制区域,我们需要检查(ceil(m/x) * 2 + 1, ceil(n/y) * 2 + 1)的区域的像素。那对应的,对于我们的shader处理每一个像素时,我们需要检测周围这么大的区域的栅格里是否有数据。

3. 对每个像素处理,对拿到的可能覆盖范围内的所有数据点做矩形(即绘制区域)碰撞测试,如果到当前像素在某个数据点的绘制范围内,则取对应图片进行绘制。

相对于纯栅格绘制,这个散点的栅格绘制方案的成本包括多检索(ceil(m/x) * 2 + 1, ceil(n/y) * 2 + 1)的区域,并且每个区域需要做做多0-x次碰撞测试。以demo的数据来说,性能消耗最多是3x3x6攻击54倍——当然对于shader来说,这个也不算什么的样子。

Code

这里有一个思路转换。原本方案的数据图像(即一个像素表示一个栅格的图片),每个像素里根本没存储啥东西,所以像素数据非常无所谓。但是现在这个方案,我们需要在数据图像中储存这个像素,就是这个栅格里包含了多少个点,还有每一个点的经纬度。

1. 储存经纬度,一个像素0xFFFFFFFF储存经纬度可以储存到小数点后7位了。而如果用rgb,不用a的六位0xFFFFFF来储存经纬度,可以储存到小数点后5位。5位的进度已经是米级的了,所以五位就够了。所以我们可以用两个像素0xAABBCCFF,0xAABBCCFF来足够准确的表述以个数据点的经纬度还可以储存256*256的其他信息。完全够了。

2. 因为我们的数据图像的像素要表示栅格,因此我们开了第二个图片,数据图像2,来储存所有的经纬度点数据。只需要两个两个一组把所有数据按即有顺序罗列在图片里面就行了。

點擊在新視窗中瀏覽此圖片

生成数据图像2的数据写入片段是:

var writeToInfo = function(zx, zy, imageData, point,count) {
    var offset = 512 * zy + zx * 2;
    let x = Math.floor(point.x * 100000);
    let y = Math.floor(point.y * 100000);
    
    imageData.data[4 * offset] = Math.floor(x / (256 * 256)) % 256;
    imageData.data[4 * offset + 1] = Math.floor(x / (256)) % 256;
    imageData.data[4 * offset + 2] = Math.floor(x) % 256;
    imageData.data[4 * offset + 3] = 255;
    
    imageData.data[4 * offset + 4] = Math.floor(y / (256 * 256)) % 256;
    imageData.data[4 * offset + 5] = Math.floor(y / (256)) % 256;
    imageData.data[4 * offset + 6] = Math.floor(y) % 256;
    imageData.data[4 * offset + 7] = 255;
}

3. 那我们原本的数据图像储存什么呢。就用来储存像素的数量,可以具体的数据在数据图像2的offset好了,我们用0xFFFFFF的rgb来储存offset,这可是16777216的数据量,就是说原理上能指向共计1677w以上数量的点,肯定够用的。a的0xFF来储存这个格子的数据数量,也就是说最多可以储存256个数据。

點擊在新視窗中瀏覽此圖片

生产数据图像的写入片段:

var writeToData = function(answer, imageData, zx, zy, num) {
  answer.y = 1200 - answer.y;
    var offset = answer.x + answer.y * 800;
    imageData.data[4 * offset] = zx;
    imageData.data[4 * offset + 1] = Math.floor(zy / 256) % 256;
    imageData.data[4 * offset + 2] = zy % 256;
    imageData.data[4 * offset + 3] = num ? 255 - num : 0;
}

那么,我们在shader里按照之前的流程,先解析出当前的经纬度,和当前在哪个栅格中,这里,我们需要解析3x3共计9个栅格了。
同时,对每个栅格的所有数据进行for循环处理:

  //读取数据图像
        vec4 data[9];
        vec2 uv = vec2(answer.x / L_mapWidth, 1.0 - answer.y / L_mapHeight);
        vec2 px = vec2(1.0, 1.0) / vec2(L_mapWidth, L_mapHeight);

        //3x3的数据范围
        data[0] = texture2D(dataImage, uv + vec2(-px.x, px.y));
        data[1] = texture2D(dataImage, uv + vec2(0.0, px.y));
        data[2] = texture2D(dataImage, uv + vec2(px.x, px.y));

        data[3] = texture2D(dataImage, uv + vec2(-px.x, 0.0));
        data[4] = texture2D(dataImage, uv);
        data[5] = texture2D(dataImage, uv + vec2(px.x, 0.0));

        data[6] = texture2D(dataImage, uv + vec2(-px.x, -px.y));
        data[7] = texture2D(dataImage, uv + vec2(0.0, -px.y));
        data[8] = texture2D(dataImage, uv + vec2(px.x, -px.y));

        for (int i = 0 ; i < 9 ; i++) {
            vec4 d = data[i];
            //count从a中读取
            float count = d.a > 0.0 ? floor(256.0 - floor(d.a * 256.0)) : 0.0;
            //数据图像2offset从rgb中读取
            vec2 pixel = vec2(floor(d.r * 256.0), floor(d.g * 256.0 * 256.0 + d.b * 256.0));
            //如果存在数据
            if (count > 0.0) {
                //按count循环处理
                //由于glsl语言循环不能有动态变量因此这里的写法直接将循环展开,并且预设最多count为8个
                if (count <= 1.0) {
                    renderPos(pixel, now);
                } else if (count <= 2.0) {
                    renderPos(pixel, now);
                    renderPos(pixel + vec2(1.0, 0.0), now);
                } else if (count <= 3.0) {
                    renderPos(pixel, now);
                    renderPos(pixel + vec2(1.0, 0.0), now);
                    renderPos(pixel + vec2(2.0, 0.0), now);
                } else if (count <= 4.0) {
                    renderPos(pixel, now);
                    renderPos(pixel + vec2(1.0, 0.0), now);
                    renderPos(pixel + vec2(2.0, 0.0), now);
                    renderPos(pixel + vec2(3.0, 0.0), now);
                } else if (count <= 5.0) {
                    renderPos(pixel, now);
                    renderPos(pixel + vec2(1.0, 0.0), now);
                    renderPos(pixel + vec2(2.0, 0.0), now);
                    renderPos(pixel + vec2(3.0, 0.0), now);
                    renderPos(pixel + vec2(4.0, 0.0), now);
                } else if (count <= 6.0) {
                    renderPos(pixel, now);
                    renderPos(pixel + vec2(1.0, 0.0), now);
                    renderPos(pixel + vec2(2.0, 0.0), now);
                    renderPos(pixel + vec2(3.0, 0.0), now);
                    renderPos(pixel + vec2(4.0, 0.0), now);
                    renderPos(pixel + vec2(5.0, 0.0), now);
                } else if (count <= 7.0) {
                    renderPos(pixel, now);
                    renderPos(pixel + vec2(1.0, 0.0), now);
                    renderPos(pixel + vec2(2.0, 0.0), now);
                    renderPos(pixel + vec2(3.0, 0.0), now);
                    renderPos(pixel + vec2(4.0, 0.0), now);
                    renderPos(pixel + vec2(5.0, 0.0), now);
                    renderPos(pixel + vec2(6.0, 0.0), now);
                } else {
                    renderPos(pixel, now);
                    renderPos(pixel + vec2(1.0, 0.0), now);
                    renderPos(pixel + vec2(2.0, 0.0), now);
                    renderPos(pixel + vec2(3.0, 0.0), now);
                    renderPos(pixel + vec2(4.0, 0.0), now);
                    renderPos(pixel + vec2(5.0, 0.0), now);
                    renderPos(pixel + vec2(6.0, 0.0), now);
                    renderPos(pixel + vec2(7.0, 0.0), now);
                }
            }

        }

对于每个数据点,和当前渲染像素的对比,由于是矩形格子,直接解析数据并且比较就可以了:

//判断一个点的数据是否在mark经纬度上并且执行渲染
void renderPos(vec2 pixel, vec2 now) {
    //xy连续两个数据像素
    vec4 data_x = texture2D(data2Image, vec2((pixel.x * 2.0) / L_dataSize, pixel.y / L_dataSize));
    vec4 data_y = texture2D(data2Image, vec2((pixel.x * 2.0 + 1.0) / L_dataSize, pixel.y / L_dataSize));
    //像素转换为经纬度
    vec2 data = vec2(256.0 * 256.0 * floor(256.0 * data_x.r) + 256.0 * floor(256.0 * data_x.g) + floor(data_x.b * 256.0), 256.0 * 256.0 * floor(256.0 * data_y.r) + 256.0 * floor(256.0 * data_y.g) + floor(data_y.b * 256.0));
    vec2 d = vec2(data.x / 100000.0, data.y / 100000.0);
    //当前像素是否在贴近的数据像素范围内
    vec2 dis = now - d;
    if (abs(dis.x) < L_tileWidth / 2.0 && abs(dis.y) < L_tileHeigth / 2.0) {
        //如果在的话,转换数据icon的uv并且渲染icon
        vec2 uv = vec2((dis.x + L_tileWidth / 2.0) / (L_tileWidth / 1.0), 1.0 - (dis.y + L_tileHeigth / 2.0) / (L_tileHeigth / 1.0));
        gl_FragColor = texture2D(iconImage, uv);
    }
}

以上两段shader,基本上就是数据图像生成的js的逆向逻辑。不过glsl的语法和数据类型很奇怪,需要处理和兼容的边界情况相当多,当前这个demo也没有完全处理。

其他

这个方案虽然是走通了,不过这也只是也行的方案的一种。除了经常说的粒子场的形式处理,可能的方案和优化还包括:

1. 数据图像2其实没必要通过图片传进去,可能通过长数据分段传进去更科学,只是如果是js写的话,二进制数据拆包为js的number再传进gl,会有无所谓的性能消耗。如果上webassembly的话,说不定就好很多了。

2. 虽然shader里没有并行buffer,但是如果能把数据图像1的处理结果作为中间数据buffer起来,那么整体可以在保证基本并行的情况下,少计算很大一层,只是多一次离屏渲染而已。

3. 如果从任意数据中划分出均匀合理的栅格,这个看起来大有学问。如果这个做不到的话,这个方案就没有意义,并且说不定还有多余的性能损耗。
关键词:webgl
發表評論
暱稱   密碼   訪客無需密碼
網址   電郵