Coons BVH for Freeform Geometric Models

晃晃

Coons BVH for Freeform Geometric Models

Yong-Joon Kim1 Young-Taek Oh1 Seung-Hyun Yoon2 Myung-Soo Kim1 Gershon Elber3

1Seoul National University 2Dongguk University 3Technion





Abstract

We present a compact representation for the bounding volume hi-

erarchy (BVH) of freeform NURBS surfaces using Coons patches.

Following the Coons construction, each subpatch can be bounded

very efficiently using the bilinear surface determined by the four

corners. The BVH of freeform surfaces is represented as a hierar-

chy of Coons patch approximation until the difference is reduced to

within a given error bound. Each leaf node contains a single Coons

patch, where a detailed BVH for the patch can be represented very

compactly using two lists (containing curve approximation errors)

of length proportional only to the height of the BVH. We demon-

strate the effectiveness of our compact BVH representation using

several experimental results from real-time applications in collision

detection and minimum distance computation for freeform models.

Keywords: Coons patch, freeform surface, bilinear surface,

NURBS, bounding volume hierarchy (BVH), tetrahedron, offset,

collision detection, minimum distance computation

1 Introduction

Hierarchical spatial data structures play an essential role in the de-

sign of efficient geometric algorithms for three-dimensional ob-

jects [Samet 2006]. Real-time algorithms for polygonal meshes

employ various different types of BVHs that are built in a pre-

processing stage of the geometric computation [Akenine-M¨ oller et

al. 2008]. The BVH for a polygonal mesh usually requires a much

larger memory space compared to the original model itself [Yoon

and Manocha 2006]. Thus it is an important subject of research to

develop compact representations for BVH structures.

Freeform geometric models are more compact than polygonal

meshes. The BVH structure of freeform geometry can be gener-

ated by recursively subdividing the freeform surfaces [Johnson and

Cohen 1998]. Nevertheless, it is unclear, in general, where to stop

the recursive subdivision and how to proceed with the geometric

computation when we reach the leaf level. In this paper, we ad-

dress these two important issues and propose a compact BVH con-

struction scheme for freeform geometry that is based on the special

structure of the Coons patch.

The Coons patch is one of the earliest freeform representation

schemes in CAGD and was developed in the early 1960’s [Coons

1964]. (For an introduction to Coons patches, see Chapter 14 of

[Cohen et al. 2001] and Chapter 22 of [Farin 2002].) Compared

with other freeform surfaces, such as B-spline or B´ ezier surfaces,

Coons patches are seldom used in contemporary freeform model-

ing applications. Nevertheless, there are many useful properties

of Coons patches that we employ in this work for the acceleration

of geometric algorithms for freeform shapes. The most important

property, for our purpose, is that Coons patches are uniquely deter-

mined by their boundary curves. As a direct consequence, Coons

patches can be subdivided very efficiently by evaluating points only

on their boundary curves.











全文请下载附件：

C.R.CAN

既来之，则看之！

tc

很有心,部分已收录自用,谢谢

晃晃

心中有爱，爱咋咋地

tc

顶!学习了!阅!

菜刀吻电线

加精、加亮滴铁子，尤其要多丁页丁页

菜刀吻电线

好`我顶``顶顶

tc

谢谢楼主，真是太实用了