Polygon网格处理：原理与应用探索

5星 · 超过95%的资源需积分: 12 95 浏览量更新于2024-07-18 1 收藏 22.84MB PDF 举报

"Polygon Mesh Processing" 本书《Polygon Mesh Processing》深入探讨了网格处理的各个方面，旨在为读者提供关于这一领域的全面理解和实用技术。作者包括Mario Botsch、Leif Kobbelt、Mark Pauly、Pierre Alliez和Bruno Lévy等在图形学领域有影响力的专家，由AK Peters, Ltd.出版。该书涵盖了从理论基础到实际应用的广泛内容，对于想要学习和理解网格处理的人来说是一份宝贵的资源。 1. 表面表示（Surface Representations）网格处理的基础是表面的定义和其属性。在这一章中，作者介绍了不同的表面表示方法，如多边形网格（Polygon Meshes）、参数化表面（Parameterized Surfaces）和细分表面（Subdivision Surfaces）。这些表示方法各有优缺点，适用于不同的应用场景。例如，多边形网格易于处理和渲染，但可能无法精确地捕捉复杂的几何形状；而细分表面则通过迭代平滑过程提高几何细节，适合创建高质量的有机形状。 2. 近似能力（Approximation Power）网格处理的一个关键方面是其近似真实世界物体的能力。本章节讨论了如何使用有限的几何元素（如多边形）来逼近任意形状，并分析了不同近似方法的误差和效率。这涉及到诸如误差度量、形状保持和细分技术等概念，它们对于优化网格质量和计算性能至关重要。 3. 几何数据处理（Geometry Data Processing）网格处理不仅涉及表面表示，还包括数据结构、算法和操作，如拓扑操作（Topology Operations）、网格简化（Mesh Simplification）、平滑（Smoothing）、变形（Deformation）和修复（Repair）。这些处理技术有助于减小模型大小，提高渲染速度，同时保持视觉质量。例如，LOD（Level of Detail）技术用于根据观察距离动态调整模型细节，以平衡性能和逼真度。 4. 数学模型（Mathematical Models）网格处理离不开数学的支持。书中详细阐述了支撑这些算法的数学基础，如线性代数、向量和矩阵运算、几何变换、微分几何以及离散微分几何等。这些数学工具为解决网格处理中的问题提供了理论框架。 5. 计算机图形学应用（Computer Graphics Applications）网格处理在计算机图形学中有广泛的应用，包括游戏开发、电影特效、虚拟现实、医学成像、产品设计等。书中会展示如何将上述理论和技术应用于实际场景，如光照计算、碰撞检测、动画和物理模拟等。 6. 参考文献与索引（Bibliographical References and Index）书末提供了详细的参考文献列表，便于读者进一步研究相关主题。索引则方便读者快速定位特定概念或技术。《Polygon Mesh Processing》是一本全面介绍网格处理的权威著作，无论对初学者还是专业人士，都是深入理解和掌握这一领域的宝贵资料。通过阅读，读者不仅可以了解网格处理的基本概念，还能学习到最新的研究成果和实践技巧。

4 1. Surface Representations

Figure 1.2. A manifold curve. While the points f(a), f(b), and f(c) are all

in close spatial proximity, only f (a) and f(b) are geodesic neighbors since their

pre-images a and b are neighbors, too. In red: The pre-image of a suﬃciently

small δ neighborhood around f (a) in IR

lies in an ε neighborhood of a in IR.

Since in most applications the raw information about the input surface

is obtained by discrete sampling (i.e., by evaluation if there already exists

a digital representation, or by probing if the input comes from a real ob-

ject), the ﬁrst step in generating a mathematical surface representation is

to establish continuity. This requires building a consistent neighborhood

relation between the samples. In this context, consistency refers to the

existence of a manifold surface from which the samples are drawn.

While this so-called geodesic neighborhood relation (in contrast to a

spatial neighborhood relation) is diﬃcult to access in implicit representa-

tions, it is quite easy to extract from parametric representations in which

two points on the surface are in geodesic proximity, if the corresponding

pre-images in Ω are close to each other (see Figure 1.2). From this obser-

vation we can derive an alternative characterization of local manifoldness:

a continuous parametric surface is locally manifold at a surface point p if,

for every other surface point q within a suﬃciently small sphere of radius δ

around p, the corresponding pre-image is contained in a circle of some ra-

dius ε = O(δ) around the pre-image of p. A more intuitive way to express

this condition is to say that the surface patch that lies within a suﬃciently

small δ-sphere around p is topologically equivalent (homeomorphic) to a

disk. Since this second deﬁnition does not require a parameterization, it

applies to implicit representations as well.

When generating a continuous surface from a set of discrete samples, we

can either require this surface to interpolate the samples or to approximate

them subject to a certain prescribed tolerance. The latter case is considered

more relevant in practical applications, since samples are usually aﬀected by

position noise and the surface in between the samples is an approximation

6 1. Surface Representations

Since our surface representations are supposed to support eﬃcient pro-

cessing, a natural choice is to restrict functions to the class of polynomi-

als because those can be evaluated by elementary arithmetic operations.

Another justiﬁcation for the restriction to polynomials is the well-known

Weierstrass theorem that guarantees that each smooth function can be

approximated by a polynomial up to any desired precision [Ross 80].

From calculus we know that a C

∞

function g with bounded derivatives

can be approximated over an interval of length h by a polynomial of degree

p such that the approximation error behaves like O(h

p+1

) (e.g., Taylor’s

theorem or generalized mean value theorem) [Rudin 02]. As a consequence

there are, in principle, two possibilities to improve the accuracy of an ap-

proximation with piecewise polynomials. We can either raise the degree of

the polynomial (p-reﬁnement) or we can reduce the size of the individual

segments and use more segments for the approximation (h-reﬁnement).

In geometry processing applications, h-reﬁnement is usually preferred

over p-reﬁnement since, for a discretely sampled input surface, we can-

not make reasonable assumptions about the boundedness of higher-order

derivatives. Moreover, for piecewise polynomials with higher degree, the

smoothness conditions between segments are sometimes quite diﬃcult

to satisfy. Finally, with today’s computer architectures, processing a large

number of very simple objects is often much more eﬃcient than processing a

smaller number of more complex ones. This is why the somewhat extremal

choice of C

piecewise linear surface representations, i.e., polygonal meshes,

have become the widely established standard in geometry processing.

While, for parametric surfaces, the O(h

p+1

) approximation error esti-

mate follows from the mean value theorem in a straightforward manner,

a more careful consideration is necessary for implicit representations. The

generalized mean value theorem states that if a suﬃciently smooth function

g over an interval [a, a + h] is interpolated at the abscissae t

, . . . , t

by a

polynomial f of degree p, then the approximation error is bounded by

|f(t) − g(t)| ≤

(p + 1)!

max f

(p+1)

i=0

− t) = O(h

p+1

For an implicit representation G: IR

→ IR and the corresponding polyno-

mial approximant F , this theorem is still valid; however, here the actual

surface geometry is not deﬁned by the function values G(x), for which this

theorem gives an error estimate, but by the zero level set of G, i.e., by

S = {x ∈ IR

|G(x) = 0}.

Consider a point x on the implicit surface deﬁned by the approximating

polynomial F , i.e., F (x) = 0 within some voxel. We can ﬁnd a correspond-

ing point x + d on the implicit surface deﬁned by G, i.e., G(x + d) = 0

by shooting a ray in normal direction to F , i.e., d = d ∇F/k∇F k. For a

1.3. Parametric Surface Representations 7

suﬃciently small voxel size h, we obtain

|F (x + d)| ≈ |d| k∇F (x)k ⇒ |d| ≈

|F (x + d)|

k∇F (x)k

and from the mean value theorem we get

|F (x + d) − G(x + d)| = |F (x + d)| = O(h

p+1

which yields |d| = O(h

p+1

) if the magnitude of the gradient k∇F k is

bounded from below by some ε > 0. In practice one tries to ﬁnd an

approximating polynomial F with low variation of the gradient magnitude

in order to have a uniform distribution of the approximation error.

1.3 Parametric Surface Representations

Parametric surface representations have the advantage that the function

f : Ω → S enables the reduction of many 3D problems on the surface S

to 2D problems in the parameter domain Ω. For instance, sample points

on the surface can easily be generated by sampling the domain Ω and

evaluating the function f . In a similar manner, geodesic neighborhoods,

i.e., neighborhoods on the surface S, can easily be found by considering

neighboring points in the parameter domain Ω. A simple composition

of f with a deformation function d : IR

→ IR

results in an eﬃcient

modiﬁcation of the surface geometry.

On the other hand, generating a parametric surface parameterization f

can be very complex, since the parameter domain Ω has to match the topo-

logical and metric structure of the surface S (Chapter 5). When chang-

ing the shape of S, it might be necessary to update the parameteriza-

tion accordingly in order to reﬂect the respective changes of the under-

lying geometry: a low-distortion parameterization requires the metrics in

S and Ω to be similar, and hence we have to avoid or adapt to excessive

stretching.

Since the manifold surface S is deﬁned as the range of the parameteriza-

tion f, its topology is equivalent to that of Ω if f is continuous and injective.

This implies that changing the topology of a parametric surface S can be

extremely complicated because not only the parameterization but also the

domain Ω has to be adjusted accordingly. The typical inside/outside or

signed distance queries are, in general, also very expensive on paramet-

ric surfaces since they usually require ﬁnding the closest point on S to the

query point (foot point). The same applies to the detection of self-collisions

(i.e., non-injectivities). Hence, topological modiﬁcation and spatial queries

are the weak points of parametric surfaces.

8 1. Surface Representations

1.3.1 Spline Surfaces

Tensor-product spline surfaces—often called NURBS—are the standard

surface representation in today’s CAD systems. They are used for con-

structing high-quality surfaces (“class A”) as well as for freeform surface

editing tasks. Spline surfaces can be described conveniently by piecewise

polynomial or rational B-spline basis functions N

(·). For more detail, see

e.g., [Farin 97, Piegl and Tiller 97, Prautzsch et al. 02].

A tensor product spline surface f of bi-degree n is a piecewise polyno-

mial surface that is built by connecting several polynomial patches in a

smooth C

n−1

manner. The rectangular segments are deﬁned by two knot

vectors {u

, . . . , u

m+n

} and {v

, . . . , v

k+n

} and the overall surface is then

obtained by

f : [u

, u

] × [v

, v

] → IR

(1.1)

(u, v) 7→

i=0

j=0

(u)N

(v). (1.2)

The control points c

∈ IR

deﬁne the so-called control mesh of the spline

surface. Because N

(u) ≥ 0 and

≡ 1, each surface point f(u, v) is a

convex combination of the control points c

; i.e., the surface lies within the

convex hull of the control mesh. Due to the minimal support of the basis

functions, each control point has local inﬂuence only. These two properties

cause spline surfaces to closely follow the control mesh, thereby providing

a geometrically intuitive metaphor for modeling the shape of surfaces by

adjusting their control points.

A tensor-product surface—as the image of a rectangular domain under

the parameterization f—always represents a rectangular surface patch em-

bedded in IR

. If shapes of more complicated topological structure are to

be represented by spline surfaces, the model has to be decomposed into a

number of (possibly trimmed) tensor-product patches.

As a consequence of these topological constraints, typical CAD models

often consist of a huge collection of surface patches. In order to represent a

high-quality, globally smooth surface, these patches have to be connected in

a smooth manner, leading to additional geometric constraints that have to

be taken care of throughout all surface processing phases. The large number

of surface patches and the resulting topological and geometric constraints

signiﬁcantly complicate surface construction, and in particular the later

surface modeling tasks.

Another drawback of classical tensor-product spline representations is

that adding more control vertices (reﬁnement) is only possible by split-

ting parameter intervals [u

, u

i+1

] or [v

, v

j+1

], which aﬀects an entire

row or column of the control mesh, respectively. Here, the alternative

剩余242页未读，继续阅读

zktxbj

粉丝: 0
资源: 4

Polygon网格处理：原理与应用探索

Polygon Mesh Processing

PolygonMesh

CGAL::intersection()

CGAL 5.4 CGAL::Surface_mesh 怎么挖洞

如何使用CGAL在surfacemesh中抠洞

c++编程计算三角网格

给定地面实况分割，怎么使用标准软件CGAL（计算几何算法库）2提取线粒体中心线

给我提供6个点云精简的实现代码

matlab将点云形成封闭曲面

利用CGAL对网格填洞( Filling holes)

最新资源