BSP分割算法补充——关于分割一个三角形
上篇文档写完后,做了一个比较复杂的场景,进行分割后发现原算法的一些问题,在此做一个补充。根据此补充,原文档将被删掉重新修改完后再发,对各位读者造成的不便,希望大家能够见谅。
在上篇文章里谈到的分割算法里有关被分割面的处理,采取的是直接将被分割面正负都放的策略。当时认为这只会对AABB的计算产生影响,所以也就堂而皇之这么写上去了。这个算法虽然简单,但是在之后的Portal处理时会面临很多困难,这一点也是我开始没有考虑到的。
在将场景变得复杂之后,这个问题就越发显现出来:在有些叶子,将会仅包括若干被分割的共享三角形,且这些三角形根本无法构成封闭空间。然而,这些叶子却被送入了Portal计算,最后出来的Portal非常诡异,甚至包括了在同一面上的若干个Portal。
用更多的思路更改Portal算法,倒不如从根本上将空间分割得更为合理,也就是采取标准的做法:将被分割三角形分割开,分割为多个三角形,分别放入相应空间。
其实这个算法很简单,一个三角形如果被一个平面分割,直观上看,有且只有两种情况:一种是在正负各生成一个三角形;另一个是在一侧有一个三角形,另一侧有两个三角形。直观上说,无论哪种情况,关键算法流程都是:
顺序访问原三角形的边,设边的第一个顶点是v0,第二个顶点是v1。
如果这个边的两个顶点均在平面一侧,则两个顶点算入平面相应一侧的新多边形。
如果有一个点在平面上,则这个点如果是这个边的第一个顶点,应该在平面两侧的新多边形中都要放。如果是第二个顶点,则需要判断第一个顶点在平面的哪一侧,并将之放入相应空间(只放一次)。可参考下图(左)来进行理解。
如果这个边被平面切割,则:首先算出来切割后的顶点vip,注意这里需要根据顶点格式分割,法线、纹理坐标均应分割。这时,同样是判断第一个顶点在平面哪一侧,根据此,把v0、vip、v1按照相应顺序组合,分别放到两侧的多边形中(在这过程中,vip会两侧都放)。
这个算法有几个需要注意的地方:
首先,为了生成顶点顺序与原三角形一致的三角形(即顺时针三角形生成后仍是顺时针,逆时针三角形生成后仍是逆时针),我们必须要按照相应的顺序遍历原三角形的边:v0-v1、v1-v2、v2-v0,只有顺序访问原三角形的边才能保证生成后的三角形的顺序。如果一开始的顺序就很诡异,那么最后生成出来的三角形顺序将很难保证,代码也会很不直观。
第二,分割出来两侧的是多边形而不是三角形,这需要分开判断,如果多边形的顶点数量是3,说明这一侧生成的是一个三角形,那么就好办了,直接使用这个三角形即可。如果是4,说明是一个四边形。如果设四边形顶点顺序是v0 v1 v2 v3那么,组成这个四边形的两个三角形分别应该是v0-v1-v2和v0-v2-v3。具体的推导过程就不说了,如果觉得难于理解,可以参考下面的图,就容易明白了。其中,OV是指原始三角形的三个顶点,V是分割后的这个四边形的四个顶点,请注意顺序。
第三,注意法线的切分,如果两个顶点的法线方向正好相反(当然,这是特殊情况),那么最后生成的新顶点的法线会是0!在这种情况下,法线需要单独作一下处理,我的处理是将整个面的法线赋给这个顶点,当然,您也可能有更好的方式。
第四,在分割中会生成新的顶点和面,所以最后BSP的顶点数和面数经常会超过在模型原始数据里的顶点数和面数。但现在由于没有被两个叶子共同共享的三角形了,所以,一个叶子中的三角形可以统一建一张IB,一次渲染了,速度当然会比使用共享面要快。
切分算法并不是唯一的,正如BSP分割的方式也并不唯一一样,关键还是选择对自己最容易掌握,最有利的算法。
分享到:
相关推荐
总的来说,报告“CG Lab: SEARCHING A TRIANGULATION”聚焦于在三角剖分中查找点所属三角形的高效算法——Delaunay搜索,以及与之相关的Delaunay三角剖分和预处理技术。这种方法在大规模计算几何问题中有着显著的...
SparkGraphX提供了一个类似于Pregel的API,使得用户可以更容易地实现图算法。 **2.5.2 pregel实现最短路径** 在SparkGraphX中,可以通过PregelAPI实现最短路径算法。这种算法基于BSP模型,通过迭代的方式逐步更新...
内容概要:本文档详细介绍了 DeepSeek 这一高效、经济的人工智能解决方案,旨在为企业端、产品端以及开发者提供深度技术支持。对于企业而言,DeepSeek 带来了显著的成本效益和生产效率提升;而对于具体的产品和服务,它增强了用户体验的质量。特别是针对开发者,文档深入浅出地讲解了如何利用 DeepSeek 实现自动化代码生成、改写等辅助开发功能,并且提供了具体的步骤指导以满足不同环境下的部署需求,包括直接通过官方API接入、本地私有化部署或借助云平台进行托管的方式。 适合人群:希望降低开发门槛,提高工作效率的软件工程师和技术团队。 使用场景及目标:开发者可以根据自身条件选择最适合自己的部署方案来整合 DeepSeek 技术,进而达到优化编码过程、减少人为错误的目的。 其他说明:文中还包括了许多实际操作的例子,如通过代码改写的实例来展示如何改进现有程序段落,还有详细的API使用指南帮助初学者快速上手DeepSeek。此外,还提供了大量外部参考资料链接以便进一步扩展知识和技能范围。
lusted_3cd_01_0318
Cherry Studio是一款支持多模型服务的 Windows/macOS GPT 客户端。通过与Ollama搭配,搭建个人本地AI大模型
chromedriver-win64-136.0.7058.0.zip
matlab程序代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
mellitz_3cd_01_1116
基于MATLAB的牛顿迭代法实现
steenman_01_0908
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
stone_3ck_01a_0518
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
lusted_3cd_01_1117
管理层情感语调,或称为管理层语调,是一个在财务与会计领域中常用的概念,特别是在分析上市公司信息披露质量时。它主要指的是管理层在上市公司文字信息披露过程中,用词所体现出的情感倾向和可理解性。 本数据复刻了《财经研究》《中南财经政法大学学报》等顶级期刊的核心解释变量的做法。情感语调对企业未来盈余和未来绩效具有较强解释力、降低会计信息误定价、为分析师预测提供增量信息,而投资者也会对管理层情感语调做出积极反应。 情感语调1=(正面词汇数量-负面词汇数量)/词汇总量;数值越大,情感倾向越偏向正面积极。 情感语调2=(正面词汇数量-负面词汇数量)/(正面词汇数量+负面词汇数量);数值越大,情感倾向越偏向正面积极。 指标 证券代码、企业代码、年份、证券简称、行业代码、行业名称、正面词汇数量、负面词汇数量、词汇总量、句子数量、文字数量、情感语调1、情感语调2。
mellitz_3cd_02_0318
moore_01_0909
lusted_3ck_02a_0119
pimpinella_3cd_01_0916