很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

WebGL2.0从入门到精通-2、数据结构与算法（一、动态化类型数组的封装）

作者：很楠不爱3 | 2024-06-16 15:46:02

踩

webgl2

二、数据结构与算法

一、动态化类型数组的封装（ArrayBuffer、TypedArray、DataView）

在说 ArrayBuffer、TypedArray、DataView 之前，先了解一下什么是字节序。

1、字节序

字节序是数值在内存中的存储方式。分为小端字节序（little-endian）和大端字节序（big-endian）两种

所有的英特尔处理器都使用小端字节序，我们个人电脑基本都是小端字节序，小端字节序会把最不重要的放在最前，可类比欧洲通用的日期书写方式（例如，31 December 2050。年份是最重要的，月份其次，日期最后）

大端字节序则是相反的顺序，可类比 ISO 日期格式（例如 2050-12-31）。

big-endian 通常被称作"网络字节顺序"（"network byte order"）, 因为互联网标准通常要求数据使用 big-endian 存储，从标准 Unix 套接字（socket）层开始，一直到标准化网络的二进制数据结构。

了解了字节序之后，再了解一下字节序与 TypedArray、DataView 的关系

2、字节序与 TypedArray、DataView 的关系

TypedArray 中，字节序会跟随系统的字节序，于是基本都是小端字节序，是不支持自己设置的，于是就会带来一个问题：如果从网络请求来的数据是大端字节序，会导致数据无法解析。

相比之下，DataView 可以支持设置字节序，举个例子：


const buffer = new ArrayBuffer(24);
const dv = new DataView(buffer);
 
// 小端字节序
const v1 = dv.getUint16(1, true);
 
// 大端字节序
const v2 = dv.getUint16(3, false);
 
// 大端字节序
const v3 = dv.getUint16(3);

DataView 实例方法的第二个参数，可以用来设置字节序，默认是大端字节序

如果不确定计算机上的字节序，可以通过这个方法来判断：


 const littleEndian = (function() {
  const buffer = new ArrayBuffer(2);
  new DataView(buffer).setInt16(0, 256, true);
  return new Int16Array(buffer)[0] === 256;
})();

如果返回true，就是小端字节序；如果返回false，就是大端字节序。

因此三者之间的关系可以总结为：

ArrayBuffer，设计用于保存给定数量的二进制数据的数据结构。

TypedArray，操作 ArrayBuffer 的一种视图，每一项都是相同的大小和类型。

DataView，操作 ArrayBuffer 的另外一种视图，不同的地方是每一项可以有自己的大小和类型.

TypedArray 使用系统默认的端序（基本都是小端字节序），DataView 默认为大端序（同时也支持自定义/设置端序类型）。

TypedArray 的目的是提供一种方法来组合二进制数据以便在同一系统上使用 - 因此它选择特定的字节序会更好。

另一方面，DataView 意在用于序列化和反序列化二进制数据以用于传输。这就是为什么手动选择字节序是有意义的。大端序的默认值正是因为大端序常用于网络传输（有时称为“网络端序”）。如果数据被流化，则可以仅通过在下一个存储器位置处添加输入数据来组合数据。（当我们创建的二进制数据离开浏览器时 - 无论是通过网络传输到其他系统还是以文件下载的形式发送给用户，处理二进制数据的最简单的方法是就是使用 DataView。）

在 this HTML5Rocks article from 2012 讲到:

通常情况下，当应用程序从服务器读取二进制数据时，需要扫描一次以将其转换为应用程序在内部使用的数据结构。
在此阶段应使用DataView。
将多字节类型数组视图（Int16Array，Uint16Array等）直接与通过 XMLHttpRequest，FileReader 或任何其他输入/输出 API 获取的数据结合使用并不是一个好主意，因为类型化数组视图使用CPU的原生字节序。

TypedArrays 非常适合创建二进制数据，例如传递给 Canvas2D ImageData 或 WebGL。

DataView 是一种安全的方式来处理接收到的或者发送到其他系统上的二进制数据。

TypedArray 和 DataView 都是操作 ArrayBuffer 的一种视图，TypedArray 和 DataView 在操作数据时（增加、删除等）实际上是在操作 ArrayBuffer，也就是 TypedArray 和 DataView 都有对应的 ArrayBuffer 用来数据的实际存储、更新、删除等。

3、TypedArray（类型化数组）

由于 Array 对象可以容纳任意类型及动态增长这两个特点，进而导致运行效率低下及占用更多的内存消耗。

为了解决此问题，JS/TS 引入了 ArrayBuffer、DataView 及 TypedArray（包括一系列对象，统称为类型数组。）

TypedArray（类型化数组）用于存储单一类型的数据。

通过这些构造函数生成的数组，和普通数组类似，可以使用所有数组的方法，它们和普通数组的区别是：

TypedArray 元素都是一个类型的

TypedArray 元素是连续的，不会有空位

TypedArray 模式元素的初始值都是 0

TypedArray 只是一层视图，数据都存储到底层的 ArrayBuffer 中

那么，如何使用这些视图来对 ArrayBuffer 进行操作呢？


  const typeArray = new Int8Array(8);
typeArray[0] = 32;
console.log(typeArray);  // [32, 0, 0, 0, 0, 0, 0, 0]
 
const typeArray1 = new Int8Array(typeArray);
typeArray1[1] = 42;
console.log(typeArray1); // [32, 42, 0, 0, 0, 0, 0, 0]

如果我们在 ArrayBuffer 上新建视图的话


// 生成8个字节内存空间
const buf = new ArrayBuffer(8);
const int8Array = new Int8Array(buf, 0);
int8Array[3] = 32;
const int16Array = new Int16Array(buf, 0, 4);
int16Array[0] = 42;
console.log(int16Array);  // [42, 8192, 0, 0] 因为第三个字节被设置为 32，于是使用两个字节表示一个整数时，就变成了 00010000 00000000，也就是 2 的 13 次方，8192
console.log(int8Array);   // [42, 0, 0, 32, 0, 0, 0, 0]

这时我们可以看到，使用 int8 和 int16 两种方式新建的视图是相互影响的，都是直接修改的底层 buffer 的数据，他们只是操作底层 buffer 数据的两种视图。

另外，普通数组的操作方法，对 TypeArray 也完全适用。和普通数组相比 TypeArray 的最大优势是可以直接操作内存，另外，不需要做数据类型的转换，于是速度要快很多。

https://www.html5rocks.com/en/tutorials/webgl/typed_arrays/是一个很好的教程，讲解了如何使用类型数组处理二进制数据，以及它在实际项目中的应用。

Float32Array 类型数组代表的是平台字节顺序为32位的浮点数型数组(对应于 C 浮点数据类型) 。如果需要控制字节顺序，使用 DataView 替代。其内容初始化为0。一旦建立起来，你可以使用这个对象的方法对其元素进行操作，或者使用标准数组索引语法 (使用方括号)。

Float32Array 的构造函数如下（其他类型数组具有相同的操作方式）：


 // From a length
var float32 = new Float32Array(2);
float32[0] = 42;
console.log(float32[0]); // 42
console.log(float32.length); // 2
console.log(float32.BYTES_PER_ELEMENT); // 4
 
// From an array
var arr = new Float32Array([21,31]);
console.log(arr[1]); // 31
 
// From another TypedArray
var x = new Float32Array([21, 31]);
var y = new Float32Array(x);
console.log(y[0]); // 21
 
// From an ArrayBuffer
var buffer = new ArrayBuffer(16);
var z = new Float32Array(buffer, 0, 4);
 
// 长度作为参数
let f1=new Float32Array(5)
f1 // [0,0,0,0,0]
 
// 普通数组作为参数
let f2=new Float32Array([1,2,3,4,5])
f2 // [1,2,3,4,5]
let f3=new Float32Array([1,"xiaobai",{},[2,3]])
f3 // [1, NaN, NaN, NaN]
 
// 类型数组作为参数
let f1=new Float32Array([1,2])
let f2=new Float32Array(f1)
f2 // [[1, 2]

4、DataView

如果一段数据中包括多种类型（比如从服务器传来的 http 数据），除了可以通过分别设置 TypeArray 起始字节和长度外，还可以使用 DataView 来做自定义的复合视图。

在初始设计上 ArrayBuffer 的 TypedArray 视图，是用来向网卡、声卡等本机设备传递数据；DataView 是用来处理网络设备传来的数据的，并且支持设置字节序（将在后面讲到）

DataView 本身也是一个构造函数:

new DataView(ArrayBuffer buffer [, 字节起始位置 [, 长度]]);

举个例子：


const buf = new ArrayBuffer(24);
const dataview = new DataView(buf);

这样就新建了一个 DataView 视图，DataView 实例提供了 10 种方法读写内存

DataView.prototype.getInt8()

DataView.prototype.getUint8()

DataView.prototype.getInt16()

DataView.prototype.getUint16()

DataView.prototype.getInt32()

DataView.prototype.getUint32()

DataView.prototype.getFloat32()

DataView.prototype.getFloat64()

DataView.prototype.getBigInt64()

DataView.prototype.getBigUint64()

以 DataView.prototype.getInt8() 为例

dataview.getInt8(byteOffset)

表示 DataView 实例从第 byteOffset 字节开始，读取一个有符号的 8bit 整数（一个字节），继续前面的举个例子：


const buf = new ArrayBuffer(24);
const dataview = new DataView(buf);
 
dataview.setInt8(1, 3);
dataview.getInt8(1);     // 3

这就是利用实例上的不同方法，进行内存读取和写入的操作。

到这里你可能认为，如果通过不同类型的 TypeArray，指定起始字节和长度，也能达到一样的效果，但是 DataView 还有另外一个特性：设置字节序。两者的不同上面已经提及。

5、动态类型化数组

TypedArray（类型化数组）都是定长数组，无法在运行时自动增加元素个数，从而获得类似 Array（数组对象）一样的元素数量动态增长的效果。因此需要封装一个可以动态增长的动态类型化数组。

例如在 WebGL 中要用 Float32Array 对象来存储位置坐标、纹理坐标、颜色、法向量、切向量等顶点属性数据，使用 Uint16Array 对象来存储三角形或线段的索引数据等。

新建 TypedArrayList.ts 文件，其为封装的动态类型化数组，文件内容如下：


    export class TypedArrayList<T extends Uint16Array | Float32Array | Uint8Array> {
  // 内部使用类型数组，类型数组必须是Uint16Array | Float32Array | Uint8Array之一
  private _array: T;
 
  // 如果需要在ArrayList<T>的构造函数中new一个类型数组，必须要提供该类型数组的构造函数签名
  private _typedArrayConstructor: new (length: number) => T;
 
  // _length表示当前已经使用过的元素个数，而_capacity是指当前已经预先内存分配好的的元素个数
  private _length: number; // 已使用容量，当前数组已经存入的个数
  private _capacity: number; // 最大容量，当前数组支持存入的个数
 
  // 提供一个回调函数，当_capacity发生改变时，调用该回调函数，即改变数组容量时回调
  public capacityChangedCallback:
    | ((arrayList: TypedArrayList<T>) => void)
    | null;
 
  public constructor(
    typedArrayConstructor: new (capacity: number) => T, // 使用方式 new TypedArrayList( Float32Array, 6 * 7 ); 这里使用方式中的 Float32Array 就是用来确定 类型数组必须是Uint16Array | Float32Array | Uint8Array之一
    capacity: number = 8
  ) {
    this._typedArrayConstructor = typedArrayConstructor;
 
    this._capacity = capacity; // 而预先分配内存的个数为capacity
 
    // 确保初始化时至少有8个元素的容量
    if (this._capacity <= 0) {
      this._capacity = 8; // 默认分配8个元素内存
    }
 
    this._array = new this._typedArrayConstructor(this._capacity); // 预先分配capacity个元素的内存，使用时相当于：new Float32Array(10) 创建一个容量/长度为 10 的  类型为 Float32Array 的数组
 
    this._length = 0; // 初始化时，其_length为0，实际使用的长度(存入的数据的个数)
 
    this.capacityChangedCallback = null; //默认情况下，回调函数为null
  }
 
  // 只读属性：获取数组当前实际存入数据个数
  public get length(): number {
    return this._length;
  }
  // 只读属性：获取数组当前最大容量
  public get capacity(): number {
    return this._capacity;
  }
  // 只读属性：获取当前数组的实际类型
  public get typeArray(): T {
    return this._array;
  }
 
  // TypedArrayList 实现的目的是为了减少内存的重新分配，能够不断被重用，而 clear 方法时能够重用 TypedArrayList 的一个重要操作
  // 最简单高效的处理方式，直接设置_length为0，重用整个类型数组
  // TypedArray 有四个特点：
  // 1. TypedArray 元素都是一个类型的
  // 2. TypedArray 元素是连续的，不会有空位
  // 3. TypedArray 模式元素的初始值都是 0
  // 4. TypedArray 只是一层视图，数据都存储到底层的 ArrayBuffer 中
  // 利用第三个特点，当清除数组时，数组的容量始终为 this._capacity，且每个数组位置上的初始数字都为 0，即数组始终有值
  public clear(): void {
    this._length = 0;
    // 也可以循环调用 remove 方法 清除所有
  }
 
  // 从数组中删除 index 位置的元素 返回删除的元素
  public remove(idx: number): number {
    if (idx < 0 || idx >= this._length) {
      throw new Error("索引越界！");
    }
    const num = this._array[idx];
    for (let i = idx; i < this.length; i++) {
      this._array[i] = this._array[i + 1];
    }
    // TypedArray 有四个特点：
    // 1. TypedArray 元素都是一个类型的
    // 2. TypedArray 元素是连续的，不会有空位
    // 3. TypedArray 模式元素的初始值都是 0
    // 4. TypedArray 只是一层视图，数据都存储到底层的 ArrayBuffer 中
    // 利用第三个特点，remove 某个位置的元素时，只需要直接移除即可，不需要对最后一个录入的数据进行重新赋值
    // 比如：数组长度为 8，已经录入了三个数字,[0,1,2,0,0,0,0,0],这时删除了下标为 1（此处值也为 1）的数字后，不需要将第三个数，下标为 2（删除前数值也为 2）的值重新设置值
    // 因为元素的初始值都是 0，移除一位之后，后面的会自动补为 0，数组容量的长度始终为 8
    this._length--;
    return num;
  }
 
  public pushArray(nums: number[]): void {
    for (const num of nums) {
      this.push(num);
    }
  }
  // push 具有动态增加容量的功能 以防止添加的数据个数超过当前实际容量
  public push(num: number): number {
    // 如果当前的length超过了预先分配的内存容量
    // 那就需要进行内存扩容
    if (this._length >= this._capacity) {
      // this._length 是实时增加的，最大也不会超过 this._capacity 因此扩容时  this._capacity 哪怕只时增加一个 也是可以的
      //如果最大容量数>0
      if (this._capacity > 0) {
        //增加当前的最大容量数即进行数组扩容 数组扩容策略可以自行定制 如果 this._capacity 每次都是一个一个增加，会导致频繁进行扩容 这里默认使用的扩容策略为
        // 每次扩容在原来的基础上增加一倍，即原本为 10，下次为 20，再下一次为 40，以此类推
        this._capacity += this._capacity;
      }
      // 用旧数组保存
      let oldArray: T = this._array;
      // 重新初始化/扩容原本数组
      this._array = new this._typedArrayConstructor(this._capacity);
      // 将oldArray中的数据复制到新建的array中
      this._array.set(oldArray);
      // 如果有回调函数，则调用回调函数
      if (this.capacityChangedCallback) {
        this.capacityChangedCallback(this);
      }
    }
    // 当使用了 clear 方法后，this._length 被设置为 0，此时 this._array 可能还是上一次操作后的数组
    // 此时并没有清空 this._array 或重新初始化 this._array，上一次 this._array 被分配的内存空间被重新使用，而不是再次分配新的内存
    // 进而减少了内存的分配
    // 同时数组的数据从 数组下标为 0 的地方进行了数据重新录入（覆盖）
    // 从而实现较少内存的重新分配的同时可以重用上一次的内存空间实现新的数据的录入
    // 这里需要注意一个问题就是：当进行重新复用时 如果新录入的数据只有 10 个，而上次录入的数据可能有 20 个
    // 这时前 10 个肯定被重新录入，即为最新的数据，但后 10 个依然为上次录入的数据
    // 因此 _array 被设计为 私有属性 即无法直接获取 _array
    // 而是需要通过 subArray 或 slice 方法来获取到最大范围为 0 到 this._length 的数组（即当前最新录入数据的所有数组（即获取的是从 0 到 10 的数组，而不是 0 到 20 的数组，虽然 _array 实际上为 20 的数组））
    // 这样就保证了数组从更新、获取、重新复用整个逻辑上都是最新的。
    this._array[this._length] = num;
    return this._length++;
  }
  // 根据数组下标获取指定位置的数据
  public at(idx: number): number {
    if (idx < 0 || idx >= this.length) {
      throw new Error("索引越界！");
    }
    // 都是number类型
    let ret: number = this._array[idx];
    return ret;
  }
 
  // subArray 和 slice
  // 无需考虑 end 是否大于数组的实际使用数据的个数或容量长度，大于 this.length 时，会自动约束至 this.length
  // 具有以下特性：
  // 1、被 begin 和 end 指定的范围将会收束与当前数组的有效索引
  // 2、若计算后得出的长度是负数，将会被收束成 0
  // 3、若 begin 或 end 是负数，将会被当做成是从数组末端读取的索引
  // 参考： https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/subarray
  // 参考： https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/slice
 
  // slice 和 subArray 的最大不同之处在于：
 
  // 1、ArrayBuffer 对象用来表示通用的、固定长度的原始二进制数据缓冲区。
  //     它是一个字节数组，通常在其他语言中称为“byte array”。
  //     你不能直接操作 ArrayBuffer 的内容，而是要通过 类型数组对象 或 DataView 对象来操作，
  //     它们会将缓冲区中的数据表示为特定的格式，并通过这些格式来读写缓冲区的内容。
  // 2、TypedArray 和 DataView 都是操作 ArrayBuffer 的一种视图，
  //    TypedArray 和 DataView 在操作数据时（增加、删除等）实际上是在操作 ArrayBuffer，
  //     也就是 TypedArray 和 DataView 都有对应的 ArrayBuffer 用来数据的实际存储、更新、删除等。
  // 3、slice 方法在创建新类型数组的同时还会重新创建并复制源类型数组中的 ArrayBuffer 数据
  //    而 subarray 方法不会重新创建并复制，而仅仅是共享了源类型数组的 ArrayBuffer
  // 4、这样带来的就是：由于 subarray 共享源数组的 ArrayBuffer，因此 subarray 返回的数组如果被修改后，源数组的内容也会被修改，slice 则不会
 
  public subArray(start: number = 0, end: number = this.length): T {
    return this._array.subarray(start, end) as T;
  }
 
  public slice(start: number = 0, end: number = this.length): T {
    return this._array.slice(start, end) as T;
  }
}

使用 demo，方法如下：

yarn dev 运行后可以看到结果：

先初始化了一个长度为 8 的 Float32Array，并初始化赋值了前三位，值分别为 0,1,2，并打印结果；

然后执行了 remove 数组下标为 1 的数据，并打印结果。

yarn dev 和 yarn build 运行结果一致。

至此动态类型化数组就封装完成了，支持 push、remove、clear 以及重要的复用。

为了实现动态类型化数组的封装，这里在根目录下新建了一个 src 文件夹，在 src 文件夹下新建了 dataStructures 文件夹，为后续存放封装的各类数据结构，在 dataStructures 下新建了 TypedArrayList.ts 为封装的动态化类型数组。

为了验证动态化类型数组，在 samples 下新增了 dataStructures 的测试 demo。

tsconfig.json 的 include 新增了 src：

至此封装及测试动态化类型数组就完成了。还修改了其他内容，请参考项目代码。

项目代码对应版本地址

本章参考如下：

《TypeScript 图形渲染实战——基于WebGL的3D架构与实现》

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/727231