Polygon网格处理：经典概览

5星 · 超过95%的资源需积分: 50 158 浏览量更新于2024-07-19 7 收藏 23.17MB PDF 举报

"Polygon Mesh Processing 经典 - 多边形网格处理的重要书籍" Polygon Mesh Processing 是一本关于多边形网格处理的权威性著作，由Mario Botsch、Leif Kobbelt、Mark Pauly、Pierre Alliez和Bruno Lévy等业界专家合著。这本书由AK Peters Ltd.出版，旨在深入探讨3D几何数据处理和计算机图形学中的关键概念和技术。本书主要关注的是多边形网格，这是一种广泛用于3D建模、动画、游戏开发、计算机视觉和虚拟现实等领域的数据结构。在3D图形中，多边形网格用于表示表面，通常由多个三角形或四边形组成，它们组合起来可以近似任何复杂的形状。在"Surface Representations"一章中，作者们讨论了表面定义和其属性，包括拓扑结构（如顶点、边和面）、连续性和光滑性。这一部分阐述了如何构建和存储这些网格，以及如何衡量它们的几何质量。 "Approximation Power"章节则涉及了多边形网格作为几何模型的逼近能力。它解释了如何通过增加或减少多边形的数量来控制细节级别，以及如何通过细分技术将低多边形模型转换为高细节的表面。书中还涵盖了诸如网格简化、平滑、变形、纹理映射、碰撞检测和物理模拟等重要主题。网格简化是优化3D模型的关键，通过减少多边形数量而不显著影响视觉质量。平滑和变形技术则允许创建更真实感的形状，而纹理映射则为表面添加细节和颜色。碰撞检测和物理模拟在交互式应用和游戏中至关重要，确保对象能够正确地相互作用。此外，书中的数学模型部分深入浅出地介绍了线性代数、微分几何和几何算法，这些都是理解和实现多边形网格处理技术的基础。这些理论知识结合实例，使读者能够掌握实际应用中的计算技巧。 Polygon Mesh Processing 还提供了丰富的参考文献和索引，方便读者进一步探索相关领域。这是一本面向高级学生、研究人员和专业开发者的必备读物，对于希望深入了解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页未读，继续阅读

huchao871014

粉丝: 3
资源: 68

Polygon网格处理：经典概览

Polygon Mesh Processing

Polygon mesh processing

MESH网格划分课程

三维几何处理：Polygon Mesh Processing

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

PolygonMesh

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

Polygon网格处理技术探索

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

CGAL 5.4 CGAL::Surface_mesh 怎么挖洞

最新资源