使用Rust trait 抽象三维几何数据类型

在对rust的trait, generics等概念有了一定理解后,我尝试集中编写一些三维几何数据的容器类作为渲染引擎的基础库。

如果你对three.js比较了解的话,我这里做的,其实就是使用rust编写Geometry,BufferGeometry等容器类,three的geometry写的是很挫的,寄希望于rust这门优秀的语言,我试图提升一下自我要求,比如:

  • 尝试将拓扑信息编码在类型之中,这样假设我有一个描述以triangleList为布局的几何数据,不应该赋值给一个以trianglestrip为布局的几何数据。
  • 可以使用任何用户自定义的顶点数据结构
  • 提供一个统一的图元迭代器,图元的类型由拓扑类型决定
  • 同时支持index/无index, interleaved/非interleaved的buffer数据

统一interleaved和非interleaved的数据

我们正常在opengl/webgl中使用的数据都是非interleaved的,比如一般来说position是一个单独的buffer,normal也是一个单独的buffer,uv也是。而interleaved版本是position + normal + uv交替存储,只使用一个buffer。

虽然我一般都是使用非interleave版本,但事实上interleaved才是较为原始的数据存储,假设你如下定义一个struct,标记内存布局使用C语言标准。对于一个Vec<Vertex>, 它的内存事实上完全就是interleaving的,你可以直接transmute一下上传,没有多余的拷贝。

1
2
3
4
5
6
7
8
9
#[repr(C)]
#[derive(Clone, Copy, soa_derive::StructOfArray)]
pub struct Vertex {
pub position: Vec3<f32>,
pub normal: Vec3<f32>,
pub uv: Vec2<f32>,
}

let my_geometry_data: Vec<Vertex>;

而我们常用的非interleave版本本质上是这个:

1
2
3
4
5
6
7
pub struct VertexArray {
pub position: Vec<Vec3<f32>>,
pub normal: Vec<Vec3<f32>>,
pub uv: Vec<Vec2<f32>>,
}

let my_geometry_data: VertexArray;

本质上就是struct of array 和 array of struct 的区别。你也看到,我在Vertex上标记soa_derive::StructOfArray, 这个库可以为我们自动生成 struct of array版本的类型,并实现As<[T]> + Index<usize>这两个trait, 这使得两种容器类型在使用上一模一样。

所以和这个抹平差异的思想一致。实际数据的存储上,容器要满足的trait是:

1
2
3
4
5
6
7
8
9
pub trait GeometryDataContainer<T>:
AsRef<[T]> + Clone + Index<usize, Output = T> + FromIterator<T>
{
}

// 为普通vec实现
impl<T: Clone> GeometryDataContainer<T> for Vec<T> {}
// 为自动的soa derive实现
impl<T: StructOfArray, A: T::ArrayType> GeometryDataContainer<T> for A {}

顶点,拓扑,和图元的trait约束

一个几何由很多顶点构成,先不考虑有没有index,这些顶点每一个/两个/三个 形成一个三角形/线段/点,如果再考虑是list还是strip,又可分为每过一个图元步进几个顶点数据。这些如何使用trait来抽象呢?

先看顶点,这里我们把问题再放窄一点,要求顶点必须是能提供3d空间点的信息, 3d空间点也不再加一层泛型,就f32吧,所以所有顶点应该实现这个trait:

1
2
3
pub trait Positioned3D: Copy {
fn position(&self) -> Vec3<f32>;
}

顶点构成图元, 图元的约束可以是这样:

1
2
3
4
5
6
7
pub trait PrimitiveData<T: Positioned3D> {
type IndexIndicator;
const DATA_STRIDE: usize;
fn from_indexed_data(index: &[u16], data: &[T], offset: usize) -> Self;
fn create_index_indicator(index: &[u16], offset: usize) -> Self::IndexIndicator;
fn from_data(data: &[T], offset: usize) -> Self;
}

来看几个impl可能会更清楚:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
impl<T: Positioned3D> PrimitiveData<T> for Triangle<T> {
type IndexIndicator = Triangle<u16>;
const DATA_STRIDE: usize = 3;
fn from_indexed_data(index: &[u16], data: &[T], offset: usize) -> Self {
let a = data[index[offset] as usize];
let b = data[index[offset + 1] as usize];
let c = data[index[offset + 2] as usize];
Triangle { a, b, c }
}

fn create_index_indicator(index: &[u16], offset: usize) -> Self::IndexIndicator {
let a = index[offset];
let b = index[offset + 1];
let c = index[offset + 2];
Triangle { a, b, c }
}

fn from_data(data: &[T], offset: usize) -> Self {
let a = data[offset];
let b = data[offset + 1];
let c = data[offset + 2];
Triangle { a, b, c }
}
}

impl<T: Positioned3D> PrimitiveData<T> for LineSegment<T> {
type IndexIndicator = LineSegment<u16>;
const DATA_STRIDE: usize = 2;
...
}

DATA_STRIDE就是上文提到的数据宽度,三个方法就是具体从一个slice里读取并构造出图元的实现,IndexIndicator辅助支持indexgeometry。这个trait配合上面的容器抽象,我们就可以在容器的指定位置读取图元。

基于顶点和图元,我们还需要描述拓扑的信息,显然,拓扑可以使用零尺寸类型表达

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pub trait PrimitiveTopology<T: Positioned3D> {
type Primitive: PrimitiveData<T>;
const STRIDE: usize;
}

// 这里不多举例,可以看到拓扑这个trait同时link了对顶点的约束,以及对应的图元类型,和步进长度
pub struct TriangleList;
impl<T: Positioned3D> PrimitiveTopology<T> for TriangleList {
type Primitive = Triangle<T>;
const STRIDE: usize = 3;
}

pub struct TriangleStrip;
impl<T: Positioned3D> PrimitiveTopology<T> for TriangleStrip {
type Primitive = Triangle<T>;
const STRIDE: usize = 1;
}

构造我们的几何类型

Index和非Index版本的数据结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub struct IndexedGeometry<
V: Positioned3D = Vertex,
T: PrimitiveTopology<V> = TriangleList,
U: GeometryDataContainer<V> = Vec<V>,
> {
pub data: U,
pub index: Vec<u16>,
_v_phantom: PhantomData<V>,
_phantom: PhantomData<T>,
}

pub struct NoneIndexedGeometry<
V: Positioned3D = Vertex,
T: PrimitiveTopology<V> = TriangleList,
U: GeometryDataContainer<V> = Vec<V>,
> {
pub data: U,
_v_phantom: PhantomData<V>,
_phantom: PhantomData<T>,
}

基于这两种geometry,配合上面的一些内容,可以直接实现出图元的迭代器,包括ExactSizeIterator。很简单,这里就不放出实现了。

可以看到我们有两个geometry,有index的和无index的,这应该需要统一一下。他们应该要实现同一个trait,这个trait应该是几何数据最基础的trait。 从抽象的角度来看,我们只关心图元,应该是要能返回图元的ExactSizeIterator,以及图元的随机访问能力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pub trait AbstractGeometry: Sized {
type Vertex: Positioned3D;
type Topology: PrimitiveTopology<Self::Vertex>;

fn wrap<'a>(&'a self) -> AbstractGeometryRef<'a, Self> {
AbstractGeometryRef { wrapped: self }
}

fn primitive_iter<'a>(&'a self) -> AbstractPrimitiveIter<'a, Self> {
AbstractPrimitiveIter(self)
}

fn primitive_at(
&self,
primitive_index: usize,
) -> Option<<Self::Topology as PrimitiveTopology<Self::Vertex>>::Primitive>;
}

因为返回的迭代器势必要对源数据保持一个借用关系,如果我要把这个迭代器的类型写进AbstractGeometry的关联类型的话,会有个生命周期参数要填。为了解决这个问题我参考了一些做法做了一些尝试,最后做法是再间接return中间的迭代器结构,让这个中间的迭代器实现IntoIterator,而这个实现我们在为AbstractGeometry实现一些通用方法的时候加上这个trait约束即可,其中生命周期参数通过HRTB注入。比如下面这个为所有几何类型实现获得光线相交点的列表的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl<'a, V, P, T, G> IntersectAble<AbstractGeometryRef<'a, G>, IntersectionList3D, Config> for Ray3
where
V: Positioned3D,
P: IntersectAble<Ray3, NearestPoint3D, Config> + PrimitiveData<V>,
T: PrimitiveTopology<V, Primitive = P>,
G: AbstractGeometry<Vertex = V, Topology = T>,
for<'b> AbstractPrimitiveIter<'b, G>: IntoIterator<Item = T::Primitive>,
{
fn intersect(&self, geometry: &AbstractGeometryRef<'a, G>, conf: &Config) -> IntersectionList3D {
IntersectionList3D(
geometry
.primitive_iter()
.into_iter()
.filter_map(|p| p.intersect(self, conf).0)
.collect(),
)
}
}

这个实现等价于threejs分散在各个class内的raycast方法,在我们的抽象体系下只有短短这么一点。从类型上可以看到,除了为了支持AbstractGeometry的trait约束,我只要要求图元实现了和光线相交的trait,那么任意满足这组约束的几何就可以直接支持这个行为。而由于完全是静态的trait的分发,编译时rust会根据你实际使用到的所有可能的图元/顶点/拓扑/几何/类型的组合生成代码,然后再层层内联高度优化,而这些代码原先都是手写的,科学技术真是第一生产力。

通用渲染用的mesh几何数据的实现还在开发中,实际实现可参考:
https://github.com/mikialex/rendiation/tree/master/mesh-buffer/src/geometry