[计算机图形学]几何:网格处理(前瞻预习/复习回顾)

一、前言 

网格的三种处理:网格细分,网格简化,网格正则化,细分会产生更多的三角面片来让模型更加光滑,简化则相反会减少网格的三角面片数量,正则化则会让三角形面更加规则。如上图中最右边两幅图,左边的一张奶牛网格的三角面片有很多狭长的三角形,而正则化可以让它变成右边那幅图,也就是三角面片都接近于正三角形,这在计算的时候会带来很多便利。而本篇我们主要介绍网格的细分和简化这两部分。

二、网格细分—Mesh subdivision

1.Loop subdivision—Loop细分

Loop细分分为两步,第一步是增加三角形的数量,它增加三角形数量的方法非常直接,直接取三条边的中点连线就可以从一个三角形细分出4个三角形。第二步就是调整顶点的位置,从而让模型更加光滑一些,而顶点又分为新生成的顶点和原来的顶点,它们的调整策略是不同的。

新生成顶点的调整策略:只要这个新顶点不在边界上,如上图,在网格内部的白点。那么我们设白点所在的这条线的两端顶点分别为AB,另外两个顶点为CD(顺序无所谓),那么新顶点的位置应该被更新为3/8*(A+B)+1/8*(C+D),实际上就是一种加权平均,AB两点因为距离近所以对它的影响更大一些。这也就是新生成顶点的调整策略。

原来的老顶点调整策略:同样用到加权平均,只不过用了新的规则,一部分受周围老的顶点的影响,另一部分受自己影响。(1 - n*u) * original_position + u * neighbor_position_sum

简单的说就是先确定这个老顶点(图中白点)的度 n(度:一个顶点连接几条边),再确定它临近顶点位置的总和sum,(再规定一个数u根据实际情况决定),那么就得到了上面的公式,也就是:  (1-n*u)*自己的位置+u*sum,很好理解,它揭示了如果这个点连接的三角形很多,则说明这个点不那么重要,所以它调整的位置更多的是根据它周围老顶点的影响,而反之,如果它连接的三角形很少,则说明这个顶点很重要,它自己的影响要大一些,决定调整位置的权重也就大一些。

2.Catmull-Clark Subdivision(General Mesh)—Catmull-Clark细分

 为什么要引入Catmull-Clark细分呢?我们前面提到的Loop细分只能细分三角形网格,而Catmull-Clark细分适用于更常规的情况,也就是它可以处理既有三角形又有四边形的网格。

在介绍之前我们先定义Catmull-Clark细分中的几个概念。

1.奇异点:度不为4的点,也就是上图中的紫色顶点

2.非四边形面:也就是上图黄色三角形标注的面

同样的Catmull-Clark细分也分为两部分,(1)引入新的顶点,(2)调整顶点的位置。

怎么引入新的顶点呢,我们对于每个面,在它们中间加入一个点,在它们的每个边上增加一个中点,再将它们连起来,如下图

从这我们还可以得出几个性质,我们发现细分之后增加了2个奇异点,老的奇异点的度为5,新的奇异点的度为3,而且我们发现只要在非四边形面点一点,那么它一定是奇异点。但我们也发现经过一次细分后,所有的非四边形面消失了,也就是说经过一次细分后,再次细分的时候就不会增加新的奇异点了。这说明Catmull-Clark细分具有很好的性质。

 又经过了2次Catmull-Clark细分后的网格

接下来就是调整顶点的操作,分为三种点,第一种是在面内新生成的点,第二种是在边中心点生成的新的顶点,第三种是老的顶点。它们分别有对应的不同的调整公式,如上图,总体来说仍然是一种加权平均的思想。

三、网格简化—Mesh simplification

网格的简化和细分同样重要,在有些情况,我们的计算性能不足以支持过多的三角形顶点的变换,在这种情况下我们就需要通过网格简化来减少顶点和三角形面片数来降低对性能的消耗。同时,在一个场景中,如果一个模型距离视线较远,那我们就不需要显示过多的层次细节,也就可以用细节层次较低的模型来减少性能消耗,这和Mipmap对纹理的优化是同一个道理,当然,纹理的层次结构的连续过度很好做,但网格的层次结构优化当今仍然是图形学正在研究的困难问题之一。

1.边坍缩—Edge Collapsing

这里介绍一种方法叫做边坍缩,也就是把几个顶点捏在一起,这样就减少了边面数,当然这里也有很多值得说的地方,比如我们怎么确定要坍缩哪条边,也就是哪条边对整个网格形体来说不太重要,以及新捏出来的点的位置应该放在哪?

而这里用到的方法叫做二次误差度量,对于新捏出的简化后的一个顶点,也就是上图中的蓝色的顶点,我们找到影响它的各个面,把该顶点与各个面的距离的平方和求出来,而在调整这个点的过程中,一定有一个位置是使得这个平方和最小的,那么这个位置也就是最优位置,那么新捏成的这个点的位置也就随之确定了。

再回到我们另外一个问题,怎么确定坍缩哪条边呢?这里同样用到二次误差度量,在一个网格中,我们对每条边都做一次二次度量误差,也就是说对每条边坍缩后对网格的整体影响做一个预计算并排序,那么开始坍缩的时候,先从那条二次度量误差最小的那条边做坍缩。

这里也有问题,那就是,我们每坍缩一条边之后,会对其它边的二次度量误差产生影响,也就是说,每坍缩一条边之后,我们的其它边坍缩后的对网格的影响要重新计算。也就是说我们需要一种数据结构,我们能瞬间取到最小值,也就是O(1),并且我们能动态的更新重新排序剩下的受影响的数据,也就是优先队列/堆这也就支持了我们每次取二次度量误差最小的边进行坍缩,然后再取受影响之后的二次度量误差最小的边进行坍缩,然后循环往复的过程。

还有一个问题,我们想对整体的网格进行简化且不损失整体轮廓,也就是说我们想找到的是对全局的一个最优化办法,但我们实际上做的是对一条边也就是局部找最优化办法,我们在试图通过局部优化达到整体的优化,这实际上是一种贪心算法,这并不是一种能完全保证全局最优性的算法。但在实际的场景中,几乎没有特别复杂的网格使得实际优化后的模型和这种贪心算法的结果相差的特别远的情况,所以人们还在用这种方法简化网格 。

 

四、总结 

到这里,几何部分的内容就就讲完了,我们从最开始的隐式,显式表示,到贝塞尔曲线和曲面,再到本篇的网格细分和简化都介绍了一遍,这部分和shader中的曲面细分着色器以及3ds MAX中的网格平滑操作都有很大的关系。下一篇将开启GAMES101光线追踪的部分,会涉及到很多物理学的知识,我们先从几何第三节的结尾的阴影图开始介绍,最后把鄙人所理解的通过我认为简单易懂的方式写出来,下篇见。

参考:

Lecture 12 Geometry 3_哔哩哔哩_bilibili

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/12478.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

理解C语言中的空指针和野指针

在C语言中,指针是一个非常重要的概念,可以用于操作变量和数据结构。但是,指针也是很容易出错的地方。其中包括两种可能的错误:空指针和野指针。 空指针 空指针指代无效的地址,表示指针不指向内存中的任何一个合法对象…

浏览器便携化操作方法

直接进入主题 如果我们不想把 Chrome 安装进 C 盘,又或者想测试多配置,那么浏览器的便携化就非常重要了。 浏览器便携化的方法有很多,国内常用的有两种。 1、MyChrome MyChrome 最早由网友“甲壳虫”开发,除了浏览器便携化&a…

camunda如何启动一个流程

在 Camunda 中启动一个流程需要使用 Camunda 提供的 API 或者用户界面进行操作。以下是两种常用的启动流程的方式: 1、通过 Camunda 任务列表启动流程:在 Camunda 任务列表中,可以看到已经部署的流程,并可以点击“Start”按钮&am…

【微服务】6、一篇文章学会使用 SpringCloud 的网关

目录 一、网关作用二、网关的技术实现三、简单使用四、predicates(1) 网关路由可配置的内容(2) 路由断言工厂(Route Predicate Factory) 五、filters(1) GatewayFilter(2) 给全部进入 userservice 的请求添加请求头(3) 全局过滤器 —— GlobalFilter(4) …

如何在矩池云上部署 Carla,模拟自动驾驶

简介 Carla 是一款基于 Python 编写和 UE(虚幻引擎)的开源仿真器,用于模拟自动驾驶车辆在不同场景下的行为和决策。它提供了高度可定制和可扩展的驾驶环境,包括城市、高速公路和农村道路等。Carla 还提供了丰富的 API 和工具&…

LeetCode算法小抄 -- 环检测算法 和 拓扑排序算法

LeetCode算法小抄 -- 环检测算法 和 拓扑排序算法 环检测算法(DFS)[207. 课程表](https://leetcode.cn/problems/course-schedule/) 拓扑排序算法(DFS)[210. 课程表 II](https://leetcode.cn/problems/course-schedule-ii/) 环检测算法(BFS)拓扑排序算法(BFS) ⚠申明&#xff1…

Python Web开发技巧II

Postman安置Cookie 对于大型项目而已,所携带的cookie往往都不止一个,而是一堆,甚至特别特别长,postman文档提供的cookie操作是全局的,但需要一个一个打(折磨),唯一的优点就是作用域…

3.7 曲率

学习目标: 如果我要学习高等数学中的曲率,我会遵循以下步骤: 1.熟悉相关的数学概念:在学习曲率之前,我们需要了解曲线、切线和曲率半径等相关的数学概念。因此,我会复习这些概念,以便更好地理…

Java阶段一Day21

Java阶段一Day21 文章目录 Java阶段一Day21多线程并发原理使用场景创建并启动线程创建线程的方法 进程线程的生命周期获取线程信息的方法 教师总结新单词多线程概念线程:一个顺序的单一的程序执行流程就是一个线程。代码一句一句的有先后顺序的执行。多线程:多个单一顺序执行的…

Nacos 客户端服务注册源码分析-篇二

Nacos 客户端服务注册源码分析-篇二 继续接上回,上回分析到 NacosNamingService 的整个注册的流程,其实是通过 NacosFactory.createNamingService 方法,反射获取 NacosNamingService 接口的实现类 NacosNamingService ,而 NacosN…

【计算方法】正交区域查询---KD-Tree概念

一、说明 kd 树是一种二叉树数据结构,可以用来进行高效的 kNN 计算。kd 树算法偏于复杂,本篇将先介绍以二叉树的形式来记录和索引空间的思路,以便读者更轻松地理解 kd 树。 二、正交区域查找 2.1 定义 对于k维空间的张量数据表格&#xff0…

一键生成元宇宙 AI又杀疯了

人类十几年的进步水平,AI用几个月就能轻易实现。在展示了超强的文本对话能力和一键生图功能后,AI大模型不打算停下,开始挑战搭建3D空间这一更高难度的动作。 这次,Facebook母公司Meta想当一把主导者。几天前,它的首席…

信号生成和可视化——周期性/非周期性波形

信号生成和可视化 此示例说明如何使用 Signal Processing Toolbox™ 中提供的函数生成广泛使用的周期和非周期性波形、扫频正弦波和脉冲序列。尝试此示例Copy Command Copy Code 周期性波形 除了 MATLAB 中的 sin 和 cos 函数外,Signal Processing Toolbox™ 还…

redis主从复制详解

文章目录 主从复制概述主从复制的作用主要包括:数据冗余故障恢复负载均衡高可用基石 主从库之间采用的是读写分离的方式读操作写操作 主从复制原理全量复制确立主从关系全量复制的三个阶段第一阶段是主从库间建立连接、协商同步的过程,主要是为全量复制做…

MobileNetV3详细原理(含torch源码)

作者:爱笑的男孩。 个人简介:打工人。 持续分享:机器学习、深度学习、python相关内容、日常BUG解决方法及Windows&Linux实践小技巧。 如发现文章有误,麻烦请指出,我会及时去纠正。有其他需要可以私信我或者发我邮箱…

Linux系统上如何禁用 USB 存储

Linux系统上如何禁用 USB 存储 为了保护数据不被泄漏,我们使用软件和硬件防火墙来限制外部未经授权的访问,但是数据泄露也可能发生在内部。 为了消除这种可能性,机构会限制和监测访问互联网,同时禁用 USB 存储设备。 我是艾西&…

uni-app常用配置

保存自动格式化 工具》设置》编辑器设置》保存时自动格式化 JS语法检查 安装eslint-js插件eslint-js - DCloud 插件市场用于校验js和html中的js代码https://ext.dcloud.net.cn/plugin?id2037工具》设置》插件配置》eslint-js 启用实时校检 Vue语法检查 安装eslint-vue插件…

如何突破LinkedIn领英限制,导出非好友邮箱等社交方式

相信做外贸的朋友都有使用过Linkedin,如果还没有使用过的话,我只能说您错过一个很好的平台。只要是厉害的外贸人都特别擅长用Linkedin找客户。 那为什么说Linkedin是外贸业务员开发客户最有效的途径呢?主要基于以下几点: 第一&a…

强训之【井字棋和密码强度等级】

目录 1.井字棋1.1题目1.2思路讲解1.3代码展示 2.密码强度判断2.1题目2.2思路讲解2.3代码 3.选择题 1.井字棋 1.1题目 链接: link 描述 给定一个二维数组board,代表棋盘,其中元素为1的代表是当前玩家的棋子,0表示没有棋子,-1代表…

禅道OpenAI更新至1.2版本,超多实用功能惊喜上线!

广受欢迎的禅道OpenAI插件近日成功发布,截至目前已更新至1.2版本。 截至本版本发布,禅道OpenAI已经拥有了神奇海螺(ChatGPT聊天)、需求润色、任务润色、Bug润色及本次的需求一键生成用例功能,仍有更多实用的新功能正在…