快速构建SAH基础的包围体积层次

需积分: 18 162 浏览量更新于2024-09-07 收藏 313KB PDF 举报

"快速构建基于表面面积启发式的包围体积层次结构" 在计算机图形学领域，"fastbuild bvh"指的是快速构建基于表面面积启发式（Surface Area Heuristic, SAH）的包围体积层次结构（Bounding Volume Hierarchy, BVH）。BVH是一种数据结构，常用于加速三维几何对象的碰撞检测、光线追踪等任务。它通过将物体分组并用包围盒（bounding box）来代表这些分组，减少不必要的计算，提高效率。 Ingo Wald等人在论文"On fast Construction of SAH-based Bounding Volume Hierarchies"中提出了一种方法，该方法允许快速地、逐帧地、从零开始重建BVH，从而消除了基于BVH的光线追踪器对更新或拟合的依赖。这种方法在具有8个核心的双核2.6 GHz Clovertown系统上，能够以大约13-21帧/秒的速度渲染包含252K三角形的爆炸龙模型（包括动画三角形、逐帧重建、着色、阴影和显示），并且构建本身只需要不到20毫秒的时间。重要的是，这种方法对三角形的分布几乎不敏感，因此帧率的变化仅由遍历成本的变化引起，而不是由于BVH质量的下降。 ABSTRACT部分进一步指出，随着光线遍历性能的提升，实时光线追踪变得越来越实际，研究焦点正从更快的遍历技术转向更有效的BVH构造算法。这表明，尽管光线追踪的性能已经足够强大，但为了实现真正的实时性，快速构建高质量的BVH仍然是一个关键问题。构建高效的BVH通常涉及两个主要步骤：分割和包围盒选择。分割过程是将几何体划分为较小的子集，而包围盒选择则是为每个子集找到最佳的包围结构。SAH是一种常用的优化策略，它通过比较不同分割方案下穿过包围盒的光线预期交点数量来最小化总体的遍历成本。 Wald等人提出的方法可能包括创新的分割策略和优化的包围盒分配算法，以确保即使在物体动态变化的情况下也能快速有效地构建BVH。此外，他们可能还考虑了如何平衡构建时间和遍历时间，以及如何处理非均匀分布的几何体，以避免因局部密集区域导致的性能下降。 "fastbuild bvh"是实时三维渲染中的关键技术，它允许在每帧开始时重建BVH，适应场景的变化，而不会牺牲性能或质量。这样的技术对于推动实时光线追踪在游戏、影视特效、虚拟现实等领域的应用具有重要意义。

On fast Construction of SAH-based Bounding Volume Hierarchies

Ingo Wald

SCI Institute, University of Utah

Intel Corp, Santa Clara, CA

Figure 1: We present a method that enables fast, per-frame and from-scratch re-builds of a bounding volume hierarchy, thus completely removing

a BVH-based ray tracer’s reliance on updating or re-ﬁtting. On a dual-2.6GHz Clovertown system (8 cores total), our method renders the

exploding dragon model (252K triangles) at around 13–21 frames per second (1024x1024 pixels) including animating the triangles, per-frame

rebuilds, shading, shadows, and display. The build itself takes less than 20ms, and is nearly agnostic to the distribution of the triangles; thus, the

variation in frame rate (21 fps for the initial, smooth frame, and 13 fps for the timestep corresponding to the four th image) is due only to varying

traversal cost, without any deterioration in BVH quality at all (i.e., when starting with the last frame, the frame rate actually increases).

ABSTRACT

With ray traversal performance reaching the point where real-time

ray tracing becomes practical, ray tracing research is now shifting

away from faster traversal, and towards the question what has to

be done to use it in truly interactive applications such as games.

Such applications are problematic because when geometry changes

every frame, the ray tracer’s internal index data structures are no

longer valid. Fully rebuilding all data structures every frame is the

most general approach to handling changing geometry, but was long

considered impractical except for grid-based grid based ray tracers,

trivial scenes, or reduced quality of the index structure. In this pa-

per, we investigate how some of the fast, approximate construction

techniques that have recently been proposed for kd-trees can also

be applied to bounding volume hierarchies (BVHs). We argue that

these work even better for BVHs than they do for kd-trees, and

demonstrate that when using those techniques, BVHs can be rebuilt

up to 10× faster than competing kd-tree based techniques.

1 INTRODUCTION

While ray tracing has always been the method of choice for most

ofﬂine rendering systems, it was long considered impractical for

interactive applications, like games. With ever more capable hard-

ware

and continuously improved algorithms, however, it is now

possible to trace severeal million rays per second on a desktop

PC. At this performance ray tracing slowly starts to get interesting

even for what eventually is the dominating application for graphics

technology—games. Games, however, are highly dynamic in na-

ture. Thus, the ray tracer has to either rebuild or update its internal

data structures every frame, and achieving interactive performance

requires to look at both traversal performance and rebuild/update

performance at the same time.

Though we refer the reader to a recent survey for a more com-

plete discussion on ray tracing animated scenes [20], the generally

accepted opinion today seems to be that among the three dominant

ray tracing data structures—grids, kd-trees, and BVHs—grids are

easiest to rebuild but less efﬁcient to travers e, while kd-trees and

BVHs are more efﬁcient, but harder to build (with the most efﬁ-

A dual-3 GHz Clovertown PC already reaches 19 2 GFLOPs peak (2

CPUs× 4 cores × 4-wide SIMD/cycle× MADD× 3 GHz=192GFLOPs)

cient techniques requiring many seconds even for moderately com-

plex scenes [19]).

For bounding volume hierarchies, this has led to various ef-

forts to avoid full rebuilding by relying on reﬁtting the BVH [11,

18]–potentially coupled with selective restructuring [22] or in-

frequent/asynchronous rebuilding [8, 11]. Fast re-building from

scratch has received far less attention. W

achter et al [16] have pro-

posed a fast spatial-median build that was originally proposed for

their s-kd-tree like “bounding interval hierarchy” (BIH), but which

applies to traditional BVHs, too. W

achter’s BIH-style build—once

applied to BVHs—allows for fast building of BVHs, but leads to

somewhat reduced traversal performance because it no longer em-

ploys a surface area heuristics (SAH) for determining how to best

build the hierarchy, and instead always splits at the spatial median.

For kd-trees, the set of techniques for fast tree construc-

tion is much richer, including hierarchical ray transformation

schemes [17], “fuzzy” kd-trees and motion decomposition [3], and,

in particular, fast “scan”-techniques that still employ a (somewhat

simpliﬁed) surface area heuristic, but achieve signiﬁcantly high

build performance by slightly approximating a full SAH build. In

addition, Hunt et al. [6] have shown that when some coarse scene

graph information is available, these fast scan-based techniques can

be accelerated by up to another order of magnitude if scanning,

build-from-hierarchy, and lazy construction are combined.

For BVHs, such fast from-scratch build techniques have not yet

been investigated. This is surprising, since BVHs have some nice

properties that make them, in fact, more amenable to these tech-

niques than kd-trees: First, BVHs have fewer nodes than a kd-tree,

so fewer operations have to be performed; second, all BVH build al-

gorithms to date use only the triangle centroids, anyway, so there is

no need for handling cases where triangles “overlap” a split plane

(in a BVH, a triangle will always be on exactly one side); third,

since each triangle is referenced exactly once the total number of

nodes in a BVH is bounded by 2N −1 (where N is the number of

triangles), so the build can be performed f ully in place without any

additional management of node memory

While being able to expect that binning techniques to be at least

Note that in general this signiﬁcantly over-estimates actual memory

consumption (at 4 triangles per leaf, it overestimates node memory by 4×),

but even then a BVH consumes less memory than a kd-tree [4].

下载后可阅读完整内容，剩余7页未读，立即下载

weixin_42894024

粉丝: 0
资源: 2

快速构建SAH基础的包围体积层次

BVH 文件播放器

临时中转文件

OpenWRT-fastbuild

Bvh.rar_BVH 文件播放器_Bvh插件_bvh 播放_bvh播放_bvh文件播放器

BVH.rar_BVH包围盒_bvh_bvh ray tracing_bvh层次包围盒_光线追踪

BVH.rar_bvh

bvh.zip_bvh

BVH-player.rar_bvh_opengl bvh_player

BVH-OGRE.rar_BVH-OGRE.rar_Ogre_ Ogre_bvh_ogre_ogre bvh

bvh reader

最新资源