dijkstra算法_【从Houdini到UE4】基于点云与Dijkstra的血管生长特效蓝图底层算法实现...

本文将讲述点云在虚幻引擎中的部分运用以及血管生长的特效的制作方法。

关注我的b站～

https://space.bilibili.com/198377617/?share_source=copy_link&share_medium=iphone&bbid=Y84C1A87238831C048E09014BFC2D3B481AF&ts=1587578403

项目链接，请多支持^_^：

https://www.unrealengine.com/marketplace/zh-CN/product/vein-growth-effect-point-cloud-function-library-in-blueprint

原视频网址，请多帮忙点赞^_^https://www.youtube.com/watch?v=p9u-j8suzDc

鄙人原来希望的是着重讲解一下点云的渲染以及形变，但是由于鸽了太久（抱歉），虚幻的新粒子系统Niagara出现了，渲染部分会变得异常简单，因此着重点变为在特效中的运用。

目录

零、动机一、点云的生成 1.生成 2.R2 Seqence二、最短路径算法Dijkstra三、桶排序

1.桶排序

2.针对kNN的优化四、kNN 1.暴力法 2.kdTree 3.VoxelGrid五、邻接矩阵的生成六、血管生长特效

七、问题与改进

零、动机

最近接触了一下Houdini，被其简单易用的节点吸引了。在网上看到了许多实用且有趣的特效，我开始思考，是否这些特效能够在一些游戏引擎中实现呢（指不使用任何插件）？毕竟算法是基本，特效也是建立在算法之上的。怀着这种想法，本人打算写下几篇，从Houdini到UE4的文章。这个系列不打算简单地使用插件来完成这些特效的转换，而是从底层原理出发，在UE中重新实现一次，并分享给读者们。全文讲述思路比较多，因为是本人个人的思路，还请斧正。

一、点云的生成

Houdini中，VeinGrowth的特效是通过模型的顶点连接到终点的最短路径实现的。

具体在Houdini中的实现参考：https://www.youtube.com/watch?v=sonXI31wDxs&t=262s

因为在Houdini中模型均为高模（相对于游戏），因此点比较密集与均匀。考虑到游戏中的模型通常都是优化过的，因此“点”的构造显得十分重要。

1.生成
要想让点均匀分布在模型表面，并不是一件容易的事情。一开始最基本的想法都是在每个三角形上均匀撒点，最后得到的点集就是均匀的结果。但是这种朴素的思想会引来一个巨大的bug，想象一下，当两个表面贴合得很近的时候，两个表面生成的点，极有可能“贴合”在一点，导致分配不均匀。
因此这个“均匀”的定义就显得有二义性，是表面均匀还是空间均匀，需要进行考虑。如果是空间上的均匀，思路也很简单，用网格包裹模型，在经过网格的地方随机填入点，并投影在三角形上，便可以得到“空间均匀”的点。
当然这个操作的代价也是巨大的，一个是不能控制点的大概数目，因为网格的粗细会明显影响其数目，除非网格密度尽可能得大。其次是对于蓝图来说，复杂度太高，对运算不友好。
因此还是选择第一种表面均匀的方法，然后判断两个点是否靠得太近，来选择是否保留，来尽量控制空间上的分布。但是这里就会引入一个问题，这个“Fuse”的操作，已经铁定是

三角形内随机撒点(Uniform random point in triangle)：
用到了Trilinear coordinates的方法
这里只给出公式，具体推导可以参考

https://en.m.wikipedia.org/wiki/Trilinear_coordinates

根据常识，对于面积大的三

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！