第一步:如果给定点 z 在八叉树包围盒内就从所属的最末端的子包围盒叶子节点开始,如果在八叉树外的话就从任意最靠近的叶子节点开始,先找一个最靠近 z 的候选点 A,如果叶子节点包围盒是空的,就递归向上,总之先找到第一个候选点 A。
第二步:以 z 为圆心,z 到 A 的距离为半径,做一个球体 S,把球体 S 同八叉树求交(离 z 最近的点一定落在这个球体范围内),筛选出有交集的叶子节点包围盒,然后迭代这些叶子节点包围盒里的点,一旦找到更近的就缩小球的范围,这样就能找到离 z 最近的点了。
如果要找前 k 个距离最近的点,你需要维护一个长度为 K 的优先队列(或者最大堆),在找到最近邻居的基础上,将兄弟节点邻近的候选点都填充到队列里,直到队列里装满 k 个点,此时以 z 为圆心,队列里第 k 个离 z 最近的点为半径,对八叉树做一次范围搜索(前 k 个点一定落在该范围内),搜索过程中不断更新优先队列并及时根据最新的第 k 个点离 z 的距离调整半径。
定点数这玩意儿并不是什么新东西,早年 CPU 浮点性能不够,定点数技巧大量活跃于各类图形图像处理的热点路径中。今天 CPU 浮点上来了,但很多情况下整数仍然快于浮点,因此比如:libcario (gnome/quartz 后端)及 pixman 之类的很多库里你仍然找得到定点数的身影。那么今天我们就来看看使用定点数到底能快多少。
void ARGBAffineRow_C(const uint8_t* src_argb,
int src_argb_stride,
uint8_t* dst_argb,
const float* uv_dudv,
int width) {
int i;
// Render a row of pixels from source into a buffer.
float uv[2];
uv[0] = uv_dudv[0];
uv[1] = uv_dudv[1];
for (i = 0; i < width; ++i) {
int x = (int)(uv[0]);
int y = (int)(uv[1]);
*(uint32_t*)(dst_argb) = *(const uint32_t*)(src_argb + y * src_argb_stride + x * 4);
dst_argb += 4;
uv[0] += uv_dudv[2];
uv[1] += uv_dudv[3];
}
}
Recent Comments