寻路网格Nav Mesh的生成原理

2023-10-10 10:40

本文主要是介绍寻路网格Nav Mesh的生成原理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1 简介
  • 2 背景和相关工作
    • 2.1 Recast
      • 2.1.1 输入准备
      • 2.1.2 光栅化
      • 2.1.3 过滤
      • 2.1.4 区域的产生
      • 2.1.5 轮廓 - 和 多边形网格的产生

这篇文章将会翻译一篇来自布莱金理工学院的论文 Towards Real-Time NavMesh Generation Using GPU Accelerated Scene Voxelization的前一小部分。传统的NavMesh生成是在CPU上做的体素化,这篇文章主要讨论的是如何将这部分搬到GPU上做,从而起到加速计算的效果。不过本文只翻译前半部分,前一小部分概述了整个Nav Mesh网格生成的原理。
本次翻译最主要的目的是自己的学习,所以如果翻译得不好,大可不必过多指责。

1 简介

传统的虚拟世界(比如3D游戏)上的寻路通常会使用寻路网格(Nav Mesh)达成目标,这是一个3D地形上的2D的凸多边形组成的网络,用来表示那些表面是可走的。在Nav Mesh上,可以使用一些图形搜索算法,比如A *算法来查找一条从一个表面到另一个表面的最短路径。有许多方式可以生成这个Nav Mesh,这其中,许多游戏引擎,尤其是Unity,CryEngine,Unreal,还有许多游戏,都使用了一种场景体素化(Scene Voxelization)的技术去生成Nav Mesh,这是一个将三角面转化成体素的方法,目的是在将寻路代理(pathFinding agent)的体积纳入考虑范围的同时评估哪个场景上哪些表面是可达的。这个过程是非常消耗计算资源的。与此同时,在其他领域,比如基于体素的锥形光线追踪(Voxel Cone Tracing for Global Illumination)证明了能够利用图形硬件的并行化加快计算速度。Recast是一个流行的库,用来在任意多边形表面上利用场景体素化技术生成寻路网格。但这个过程是在CPU上计算的,这就提供了将计算过程移植到GPU上从而提升性能的可能性。这篇论文将展示一种基于GPU的体素化技术,从而在Recast种替换它的CPU计算过程。

2 背景和相关工作

Nav Mesh可以从表示游戏世界的体素中生成。把游戏世界看作是体素的好处是对于那些不在同一个网格上但是重叠或相交的三角面依然可以被连接成一个表面。另一个好处是对于场景中的一些空隙,比如很低的天花板,或者悬浮的集合体,可以很容易地被纳入计算。

2.1 Recast

由Mikko Mononen开发的Recast是一个用于生成Nav Mesh的最先进的跨平台库,它被许多游戏引擎引用,并被kethera1和Unreal等平台扩展。Recast通过输入任意的3D多边形来生成Nav Mesh,比如一个游戏关卡。输入的多边形几何没有任何限制。为了能够从这些输入中生成Nav Mesh,这些几何必须被光栅化为体素。这里光栅化跟体素化是一个意思,同时在本篇文章当中交叉使用。一个标准的Nav Mesh生成管线中大致可分成以下一个步骤:

2.1.1 输入准备

为了能够光栅化输入的几何体,必须做一些准备工作。在这个阶段,每一个三角面都将被添加一个标记,用来指示它上面是否可行走。一个三角面当它的倾斜角小于一个既定的阈值时,将被标记为可行走的。这可以通过比较三角面的法线的Y坐标和角度阈值的余弦值做到。

2.1.2 光栅化

在光栅化阶段,一个高度场将被生成。一个高度场是一个游程编码(Run-Length encoding)的体素域,包含了一个(XZ)二维数组,每个元素记录着Y轴方向上的一个区间(span)列表。一个区间定义了Y轴方向上同类型的体素集合(比如都是可行走的,或者都是不可行走的)。这些光栅化算法是基于CPU的,原理是将三角形分割成多边形,这些多边形于垂直体素列的边缘相交,并创建一个从最低点体素到最高点体素长成的空间。

2.1.3 过滤

光栅化阶段产生的高度场在被用作生成Nav Mesh之前需要一些额外的过滤操作。在过滤阶段,三种过滤方法会运行,以此确定最终的高度场。

  • 过滤毗邻的障碍物 - 如果一个区间有一个毗邻的区间,毗邻的区间的高度是可行走范围内的,那么这个区间就被标记为可行走的。这个过滤使得一些小型的障碍物或楼梯变得可行走。
  • 过滤岩壁区间 - 一个岩壁区间将被标记为不可行走的。一个区间如果它的任何一个邻居的高度比当前区间高度低很多(whose heights are too far down),那么这个区间就标记为不可行走的。
  • 过滤低空悬浮区间 - 一个区间如果没有足够的高度让寻路代理通过,那么这个区间就被标记为不可行走的。

2.1.4 区域的产生

一个高度场通过体素化和过滤之后,就可以被简化成一片区域(region),这片区域就表示该场景中能够行走的范围。在Recast中,提供了三种产生区域的方法,这三种方法各有利弊。

2.1.5 轮廓 - 和 多边形网格的产生

一旦区域生成,就可以进一步提取出更简化的轮廓了。在这个阶段,一个最大误差的阈值指定了轮廓线和区域边缘的区别程度。还有一个阈值指定轮廓的最大长度。任何长度大于阈值的轮廓部分都将会被剔除。
在这里插入图片描述
这五张图分别代表了上述的五个过程。

这篇关于寻路网格Nav Mesh的生成原理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/Terie/article/details/101026211
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/179905

相关文章

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

Spring @Scheduled注解及工作原理

《Spring@Scheduled注解及工作原理》Spring的@Scheduled注解用于标记定时任务,无需额外库,需配置@EnableScheduling,设置fixedRate、fixedDe... 目录1.@Scheduled注解定义2.配置 @Scheduled2.1 开启定时任务支持2.2 创建

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

Nacos注册中心和配置中心的底层原理全面解读

《Nacos注册中心和配置中心的底层原理全面解读》:本文主要介绍Nacos注册中心和配置中心的底层原理的全面解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录临时实例和永久实例为什么 Nacos 要将服务实例分为临时实例和永久实例?1.x 版本和2.x版本的区别

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2