权威指南：多边形网格处理与计算机图形学

5星 · 超过95%的资源需积分: 50 134 浏览量更新于2024-07-29 2 收藏 23.09MB PDF 举报

"Polygon mesh processing是INRIA发布的一本关于网格处理的权威书籍，由Mario Botsch、Leif Kobbelt、Mark Pauly、Pierre Alliez和Bruno Lévy等人共同编著，由AK Peters Ltd.出版。这本书详细探讨了多面体网格处理的最新技术和理论，适合于对计算机图形学、几何数据处理等领域感兴趣的读者。" 本书的主要内容涵盖了多面体网格的各个方面，包括但不限于： 1. **表面表示与特性** (Surface Representations): 这一部分可能讨论了如何用数学方式定义和描述一个几何表面，以及这些表面的特性，如连续性、光滑度和拓扑结构。表面可以是三角形或四边形网格，它们在计算机图形学中广泛用于表示3D物体。 2. **逼近能力** (Approximation Power): 书中可能深入分析了不同类型的网格如何近似复杂的几何形状。这可能涉及误差分析，如何优化网格以更精确地表示原始几何体，以及如何在保持几何精度的同时减少多边形数量。 3. **数据结构与算法** : 书中可能介绍了用于存储和操作网格的数据结构，如半边结构(Half-Edge)和面向切线场(Triangle Tessellation)等，并讨论了相关的算法，如网格简化、平滑、细分和变形。 4. **几何处理** : 可能包含了对网格的编辑操作，如切割、焊接、插入和删除顶点，以及如何进行拓扑修改和几何修正。此外，还可能讨论了表面的参数化和纹理映射技术。 5. **应用与案例** : 可能会通过实际应用案例，如游戏开发、影视特效、产品设计和模拟仿真等，来展示多面体网格处理的重要性及其在各个领域的应用。 6. **数学基础** : 预计书中会涉及到一些必要的数学背景，如线性代数、微分几何和离散数学，这些都是理解和实现网格处理算法的基础。 7. **参考文献与索引** : 书中包含的参考文献将引导读者深入研究特定主题，而索引则方便查找特定概念和技术。这本书对于理解多面体网格处理的理论、算法和实践具有极高的价值，无论你是学生、研究人员还是从业人员，都能从中受益匪浅。它不仅提供了理论知识，也强调了实用性和可实施性，是计算机图形学领域不可或缺的参考资料。

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

gaozhanheng

粉丝: 0
资源: 2

权威指南：多边形网格处理与计算机图形学

Polygon Mesh Processing

多边形网格处理库-C/C++开发

openmesh 半边数据结构 多边形网格处理C++函数库

三维几何处理：Polygon Mesh Processing

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

PolygonMesh

在数字化复杂三维物体时，多边形网格（Polygon Mesh）的应用原理是什么？如何通过Polygon Mesh提升模型的精确度和质量？

如何理解Polygon Mesh在3D物体数字化中的作用和重要性？

在复杂三维物体数字化过程中，多边形网格（Polygon Mesh）起到了哪些关键作用，以及它是如何影响最终模型质量的？

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

最新资源

openmesh 半边数据结构多边形网格处理C++函数库