三维几何处理：Polygon Mesh Processing

需积分: 50 50 浏览量更新于2024-07-18 1 收藏 23.02MB PDF 举报

"Polygon Mesh Processing" 是一本由Mario Botsch、Leif Kobbelt、Mark Pauly、Pierre Alliez和Bruno L´evy等人合著的专业书籍，由AK Peters Ltd.出版。该书专注于几何处理和多边形网格处理，详细探讨了3D物体的精确数字化技术，如计算机断层扫描、磁共振成像、3D激光扫描等。在3D获取技术的创新推动下，我们能够利用诸如CT扫描、MRI、3D激光扫描、超声波、雷达和显微镜等方法，对复杂三维物体进行高精度的数字化。这些技术的进步为3D建模和处理领域提供了丰富的数据来源，使我们能够创建和操作复杂的多边形网格模型。 "Polygon Mesh Processing"一书深入讲解了表面表示法及其特性，包括如何定义和评估表面的质量。它探讨了多边形网格作为几何数据结构的能力，如何用有限的多边形近似连续的表面，并分析了这种近似的精度和局限性。书中可能涵盖了从基本的几何概念到高级的处理算法，例如： 1. **表面定义与性质**：这部分可能介绍了如何使用多边形网格来表示3D形状，以及网格的拓扑结构（如连接关系）和几何属性（如平滑度和曲率）。 2. **近似能力**：作者可能会讨论如何通过不同的网格化方法，如细分、简化或优化，来平衡模型的质量与复杂性，以及如何评估这些近似的质量标准，如误差度量和保真度。 3. **数学模型**：书中可能涉及了用于描述和操作多边形网格的数学工具，包括线性代数、几何变换、微分几何和图论等。 4. **计算机图形学**：这部分内容可能涵盖多边形渲染、光照模型、碰撞检测、物理模拟等在计算机图形学中的应用。 5. **多边形处理**：可能详细讲解了各种处理技术，如网格修复（消除洞、冗余边等）、平滑、细分、减面、变形、纹理映射等，这些都是3D建模和动画中的核心步骤。 6. **算法实现**：书中的实例可能包含了实际的编程实现，指导读者如何在软件中应用这些处理技术。此外，书籍可能还包括了参考文献和索引，以便读者进一步研究相关主题。这本书对于从事3D建模、游戏开发、视觉效果、医学图像分析、产品设计等领域的专业人士和学者来说，是一份宝贵的资源。通过学习，读者可以掌握创建、修改和分析3D多边形网格模型所需的知识和技能。

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页未读，继续阅读

yuerZ6

粉丝: 93
资源: 2

三维几何处理：Polygon Mesh Processing

PolygonMesh处理：计算机图形学的热点

Polygon网格处理：经典概览

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

Polygon mesh processing

PolygonMesh

lod-mesh：具有动态细节水平（LOD）的3D多边形网格渲染器

Polygon网格处理技术探索

CGAL 5.4 CGAL::Surface_mesh 怎么挖洞

基于springboot共享经济背景下校园闲置物品交易平台源码数据库文档.zip

基于WoodandBerry1和非耦合控制WoodandBerry2来实现控制木材和浆果蒸馏柱控制Simulink仿真.rar

最新资源