实现细节

github cutt
CUTT: A HIGH-PERFORMANCE TENSOR TRANSPOSE LIBRARY FOR GPUS

cutt将_g拷贝到_h

intro

两个phase,

• 扫描(x,y)所在的列，也就是x固定。计算列上每一个点到(x,y)的直线距离。
• 扫描行，计算距离。

phase 1

就是双向扫描，

phase 2

scan 3:

先解释一下抛物线。固定y=y0，给定obs坐标(i,j)，那么y0这条线上的点到obs就是抛物线。

u在x轴递增(0–>m-1)，先不考虑i>u处的obstacle。
case b:
如果u处的obs和y0上所有点的距离(用t[q]来代表)，比所有点与其之前计算过的最近obs距离都要小，那么u将之前的obs都dominant了，现在只有一个seg，那就是u对y0的距离抛物线。
如果不是case b,那么计算x轴上转折点，也就是u可以dominant多少。算出的转折点是w，如果w>m，那么就是case a，不符合。
case c: 在x>w的时候，u dominant其他obs，此时进行更新。
增加一段seg;
增加的seg最近的obs为u;
增加一个转折点。

scan 4:

从后向前计算dt.遇上一个分界点，将obs切换到左边一个。