加速多核架构上骨架隐式曲面的多边形化

train.jpg
 

作者: Pourya Shirazianpourya.jpg

 


Pourya Shirazian,加拿大维多利亚大学Pourya 是 UVIC 的计算机科学博士生,授业教师是 Brian Wyvill 博士。他主要的研究领域包括隐函数建模及可变形模型可视化。
他目前负责的项目是骨架隐式模型实时渲染,该项目将有利于基于草图的建模系统,支持实时设计更多的复杂模型。

 

 

 

摘要:

 


使用多边形化方法渲染隐式曲面的交互式设计系统在交互式回应用户改变时会有困难。为了解决这一问题,我们建议采用新方法镶嵌 Blobtree 骨架隐式模型,即使用由包围盒控制的分治策略。我们的算法利用了多核架构上可用的并行处理能力。

 

 

 

 

推荐的算法


BlobTree 构建了一种直观的机制,用于借助 CSG、混合、变形及仿射变换【1】组织骨架隐式基元。在标量场中将模型可视化为等值面;采用空间分区算法,只需找到正常体素网格顶点处的字段值。这一步骤通过在每一点穿越 BlobTree 完成。字段值比等值大的点被认为是位于模型“内部”。当使用蜂窝栅极多边形化处理【3】模型,这一流程需依次重复进行。如下,n 由单元大小参数导出:

eqn1.png

使用常规的移动立方体方法,字段求值的成本将成为系统的瓶颈。我们推荐的算法如下:

 

 

 

1. 每个骨架基元 s_i 包括网格内部点 φ_i 列表。(φ_i 具有至少一个要素,其必须位于基元骨架上或十分靠近后者。)

2. 我们会计算出整个模型的范围框。(使用骨架及有效半径计算每个骨架基元的包围盒;树节点将会相应地修改范围框。)

3. 把范围框分成“线程卷”,一个线程卷用于处理器上可用的每个物理线程。

4. 然后,将每个线程卷与一系列体元相关联。对于每个体元列表,我们必须生成关联的三角形列表。实施步骤如下:

首要的问题就是确保每个基元有一个曲面种子点。(步骤 a 到 d 将不会成为系统瓶颈。)

4a.对于每个线程卷 tv,我们考虑的是 S={s_1,s_2,…,s_q},即 BlobTree(其范围框与线程卷相交)中的所有基元节点的集。

4b.对于 S 中的每个要素 s_i,检查 φ_i 中的所有内部点位于 tv 内的情况。一旦发现某个点位于 tv 内,光线就会依次射向那个点及 tv 的每个角落。如果没有发现内部点位于 tv 内,光线会从 tv 中心射向其所有角落。

4c.我们使用求根法寻找 tv 内部曲面上的种子点。

4d.此时,一些基元节点可能没有种子点。对于每个没有种子点的 s_i,另一光线会从内部点φ_i 射向 s_i 的每个骨架点。然后,我们重复步骤 (c),直到每个潜在内部点列表分解成一个种子点。

第二个问题就是寻找所有与每个线程卷 tv 内等值面相交的立方体元。

4e.当前 tv 内曲面上的种子点被用作局部坐标系统的起点。在起点创建规定大小的立方体元,并将其添加到当前体元 V 的列表中。

4f.计算 V 中每个交叉体元的所有角落的字段值,且对于和曲面相交的每个边缘(即每个具有一个内侧及一个外侧端点的边缘),把与其相邻的 3 个立方体加入 V 中 (如果它们位于 tv 内)。

4g.对于每个体元,使用【3】中的散列函数从配置中生成相应的三角形。将所有生成的三角形添加到 T 中。

5. 最后,将针对每个线程卷生成的三角形列表合并到全局列表,然后传给渲染器。

FlowChart.png
图 1. 描述算法的流程图

我们可针对每个体元使用连续法,避免将减缓曲面搜索的冗余空间分割。某些情况下,沿 tv 边界拼接网格可能会成为唯一的问题;由于我们将直接渲染网格,因此不会产生视觉缺陷。

我们采用了两种不同的方法实施这一算法。开始,我们使用英特尔线程构建模块 (TBB)将范围框分割应用于多核 CPU,并使用 TBB 将算法分为 2 个主要步骤。起初,我们在立体范围框上应用了 Parallel_For 模板功能。在每个体元内,我们创建了穿越该体元流形的所有立方体的列表,并使用 Parallel_Reduce 运算对立方体列表进一步进行三角测定。

在第二种方法中,我们使用了多核编程范例。主应用程序将树结构汇集到数据包中,并将其作为信息发送至设备应用。在设备端,打开该数据包并将其转换为轻量型树。我们使用了单独的线程创建两个相同的分割为体元及三角测定每个体元的步骤。最后,将得到的网格直接渲染至设备环境。

在性能方面,如果与串行移动立方体方法相比,我们的 CPU 实施则实现了最大为 10 倍的加速。另外,由于在处理每个线程卷时使用了基础的连续法并对字段值进行了高速缓存,所以每个三角形的字段值评估数量已降低了至少 4 倍。

timing.jpg
表 2. 单元尺寸不同的各帧的渲染性能对比。蓝色、红色和绿色栏分别代表 MC、继续和 Parsip。纵轴表示数百秒的对数渲染时间。

fvept.jpg
表 3. 单元尺寸不同的各三角形的字段值评估对比。蓝色、红色和绿色栏分别代表 MC、继续和 Parsip。

threads.jpg
表 4. 线程数与毫秒计多边形化时间对比

 


参考:

  1. Wyvill, B., Guy, A., & Galin, E. (1999). Extending the CSG Tree - Warping, Blending and Boolean Operations in an Implicit Surface Modeling System. In Computer Graphics Forum (Vol. 18, p. 149–158).
  2. Bloomenthal, J. (1994). An implicit surface polygonizer. Graphics gems IV, 1, 324–349. Citeseer.
  3. Wyvill, G., McPheeters, C., and Wyvill, B., (1986) Data Structure for Soft Objects, In The Visual Computer, (Vol. 2, Num. 4, p. 227-234).
  4. Complete paper on this work: /sites/default/files/m/5/0/1/Parsip_ExtendedAbstract.pdf
  5. Poster Presentation from Grand 2010 (Ottowa,Canada): /sites/default/files/m/1/0/f/Parsip_Poster.pdf

 

 

顾问: Brian Wyvill


brian.jpgBrian Wyvill 在获得了布拉德福德大学计算机制图专业的博士学位之后,在伦敦皇家艺术学院任博士后一职。20 世纪 70 年代末,他参与了电影《异形》连续镜头的制作。Brian 在卡尔加里大学度过了 25 载,现在是维多利亚大学的加拿大首席科学家,正全身心研究隐函数建模和动画制作,及非真实感渲染。

 

 

 

 

更多资源:


http://webhome.csc.uvic.ca/~pouryash/
http://webhome.cs.uvic.ca/~blob/papers.html
http://www.csc.uvic.ca/Research/graphics/

 

 

 

 

 

Pourya Shirazian
04-12-2010
04-12-2010
Tech Articles
 
Research
 
 
 
no
Interactive design systems that use polygonization methods for rendering implicit surfaces have difficulty in responding interactively to user changes. To address this, we propose a novel approach for tessellating Blobtree skeletal implicit models using a divide and conquer strategy controlled by bounding volumes. Our algorithm leverages the parallel processing power available on Many-Core architectures.
Para obtener información más completa sobre las optimizaciones del compilador, consulte nuestro Aviso de optimización.