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分割的方式也并不唯一一样,关键还是选择对自己最容易掌握,最有利的算法。
分享到:
相关推荐
此篇论文描述了前一些年的3D游戏中广泛使用的BSP场景组织结构的算法,全篇英文,不过却是深入简出,对于想了解和研究BSP场景组织算法的朋友是份非常好的资料
原创文章,著作权属本人所有,本人也对一切言行负有责任,望大家能尊重劳动者的辛勤努力,不要侵犯我们这些底层劳动人民的知识产权。
详细介绍BSP树(Binary  Space  Partioning  trees,二维空间分割树)的原理和实现。
如碰撞检测 A* 四叉树 BSP分割树 地形LOD等等
实现了一个2D的BSP树,并能判断鼠标有没有点中一个比较复杂的凹面体。
■ 描述windows embedded CE是如何管理虚拟内存的。 ■ 为硬件平台配置正确的静态内存映射。 ■ 在系统中映射非连续的物理内存到虚拟内存上。 ■ 在OAL及设备驱动之间共享资源。
针对三角面元目标提出了一种高效率的空间分割算法.该方法以一种空间点与单位立方体位置关系的判断法则为基础,并逐渐延拓到参数直线、三角形的空间分割上,给出了一种新的三角形面元目标快速分割的解决方法.介绍了...
2440 5.0BSP串口源码集合——我给代码所引用的库都找出来了,并且建了sourceinsight工程以及加了个增加串口的文档
Quake3 BSP 技术简析 关于bsp技术的论文,喜欢游戏制作或者想了解bsp的可以下载看看 相关技术可以去搜索更多专业论文
收集各种开发板wince BSP资源: 6410 sd启动裸跑 mini2440 Android系统 WINCE6 VMWARE BSP 三星CPU资料 三星S3C2416 三星S3C2440A 三星S3C2443 三星S3C6410 优龙开发板wince5.0 BSP和资料 友善之臂Micro2440、...
3D游戏中的BSP二叉空间分割技术.doc
SAP BSP使用前的必要配置 内有截图 详细步骤
9.1 引言——一种拟人的游戏界面 9.2 将语言表述转变为动画——示例 9.2.1 IMPROV(纽约大学媒体研究实验室) 9.2.2 PAR体系结构(宾夕法尼亚大学人体建模和仿真中心) 9.2.3 具体化的对话界面代理(MIT媒体实验室) 9.2.4...
1、创建BSP树。 此BSP树为满树,即所有节点/叶子全部创建。 用户可以自定义此BSP树的深度和所处的... BSP树创建成功后用户可调用此子模块查看此BSP树,会显示每个结点的编号,值和在场景中的坐标。3、查看BSP树的深度。
9.1 引言——一种拟人的游戏界面 9.2 将语言表述转变为动画——示例 9.2.1 IMPROV(纽约大学媒体研究实验室) 9.2.2 PAR体系结构(宾夕法尼亚大学人体建模和仿真中心) 9.2.3 具体化的对话界面代理(MIT媒体实验室) 9.2.4...
本文档概括地描述了构成板级支持包(BSP)的元素,VxWorks BSP的要求以及引导过程中BSP的一般行为。 本文档概述了将现有BSP移植到新硬件平台或使用参考BSP或模板BSP作为起点为自定义硬件编写新的VxWorks BSP所需的...
自己在学习ZC702中写的一份文档,主要针对初学linux的人,介绍如何安装xilinx的嵌入式linux系统——Petalinux和zc702的BSP。
RT-Thread的BSP制作文档,转成pdf方便大家阅读 源连接 github.com/RT-Thread/rt-thread/blame/master/bsp/stm32/docs/STM32系列BSP制作教程.md
应用二叉空间分割算法实现了扇区间平均流量的均衡,结合动态规划方法提出了逐阶段动态搜索协调流量最小的二叉空间分割算法,解决了算法运行效率低的问题。仿真实例表明,该方法均衡了不同扇区间的平均流量,保证了...
摘要:从词向量的训练模式入手,研究了基于语料语句分割(BWP)算法,分隔符分割(BSP)算法以及属性主题分割(BTP)算法三种分割情况下的词向量训练结果的优劣。