logo资料库

Vector field processing.pdf

发布时间：2022-06-30 发布人：admin 分类：说明书 资料大小：16.65M 资料格式：pdf 举报 版权申诉
第1页 / 共48页
第2页 / 共48页
第3页 / 共48页
第4页 / 共48页
第5页 / 共48页
第6页 / 共48页
第7页 / 共48页
第8页 / 共48页
资料共48页，剩余部分请下载后查看
    Vector Field Processing on Triangle Meshes Course Notes ACM SIGGRAPH Asia 2015 ORGANIZERS: FERNANDO DE GOES Pixar Animations Studios MATHIEU DESBRUN Caltech YIYING TONG Michigan State University
    Abstract While scalar fields on surfaces have been staples of geometry processing, the use of tangent vector fields has steadily grown in geometry processing over the last two decades: they are crucial to encoding directions and sizing on surfaces as commonly required in tasks such as texture synthesis, non-photorealistic rendering, digital grooming, and meshing. There are, however, a variety of discrete representations of tangent vector fields on triangle meshes, and each approach offers different trade- offs among simplicity, efficiency, and accuracy depending on the targeted application. This course reviews the three main families of discretizations used to design computational tools for vector field processing on triangle meshes: face-based, edge-based, and vertex-based representations. In the process of reviewing the computational tools offered by these representations, we go over a large body of recent developments in vector field processing in the area of discrete differential geometry. We also discuss the theoretical and practical limitations of each type of discretization, and cover increasingly-common extensions such as n-direction and n-vector fields. While the course will focus on explaining the key approaches to practical encoding (including data structures) and manipulation (including discrete operators) of finite- dimensional vector fields, important differential geometric notions will also be covered: as often in Discrete Differential Geometry, the discrete picture will be used to illustrate deep continuous concepts such as covariant derivatives, metric connections, or Bochner Laplacians.
    Preface T hese course notes provide a review of the various representations of tangent vector fields on triangulated surfaces. Over the past decades, a number of approaches to express, design, and analyze vector fields on arbitrary meshes have been proposed in geometry processing, targeting a series of applications varying from rendering to animation. Some describe vector fields through values on vertices, some on edges, and some on faces; some treat vector fields as piecewise constant, some as piecewise linear, and some even involve non-linear finite elements. This lack of a unified approach to vector field representation and manipulation can be confusing for practitioners, and rare are the references that discuss the pros and cons of these various representations. The chapters in this document were written with this fact in mind, as a way to offer an introduction to the motivations, benefits, and shortcomings of the most common discretizations of vector fields in graphics—along with their associated discrete differential operators (curl, divergence, Laplacian, etc). Emphasis is placed on the tradeoffs between simplicity, efficiency, and accuracy of these geometry processing tools for applications ranging from texture synthesis to meshing. In many ways, this course is a continuation of ACM SIGGRAPH courses on Course rationale. Discrete Differential Geometry (SIGGRAPH ’05 and ’06, and SIGGRAPH Asia ’09) and Discrete Exterior Calculus (SIGGRAPH ’13) taught over the past decade. Nevertheless, it does not require familiarity with these former courses. The course will, instead, introduce topics absent from previous offerings such as connections, covariant derivatives, and interpolating basis functions for vector fields— which are gaining popularity among practitioners, but for which no tutorials are available. The notes are intended for graduate students, researchers, and developers interested in geometry processing. Practitioners will find concrete data structures and numerical tools for the manipulation of vector fields on triangle surfaces, while scholars will learn how to preserve geometrical and topological continuous properties in the finite-dimensional realm. Pedagogical Intentions. These course notes were conceived to complement a half-day course at SIGGRAPH Asia ’15, so we mostly mirrored its three-part structure, reviewing works where vector fields are stored per face first, then describing those using per-edge representation, then finally going over the more difficult case of per-vertex encoding. For each representation, we provide its essential mathematical background as well as a few examples of real-world applications. The course material aims at providing not only a literature review of the field of vector field processing, but also to introduce basic geometric concepts that the field of differential geometry has developed to provide a principled approach to vector calculus on arbitrary manifolds. The theme of discrete differential geometry (i.e., finite dimensional approximations that respect key properties of their infinite-dimensional counterparts) will be omnipresent in the course, and numerical advantages and limitations will be highlighted, often using concrete applications for better illustration. As a consequence, the material should be accessible to anyone who has had exposure to basic linear algebra and vector calculus. A basic understanding of differential geometry is also recommended, but not mandatory. Throughout these notes, we strived to present each mathematical concept using a concrete geometric picture; we punt most of the associated abstract or algebraic arguments to existing references for the readers who want to get a more thorough exposition. Credit where credit is due. We are indebted to our coauthors for the material included in [Tong et al. 2003; Wang et al. 2006; Fisher et al. 2007; Hertzmann and Zorin 2000; Crane et al. 2010; Crane et al. 2013; de Goes et al. 2014; Liu et al. 2015]. We also thank the attendants of our previous classes for their feedback by which our approach was informed.
    Introduction to Discrete Vector Fields 1 Vector fields in geometry processing Before delving into the technical details of how vector fields are encoded in traditional geometry processing methods, we provide some background on the relevance and difficulties of discrete vector fields in graphics. 1.1 Motivation Numerous applications in computer graphics need to manipulate tangent vector fields on triangle meshes. For instance, example-based texture synthesis needs a vector field to define the texture’s local orientation and scale. Non-photorealistic rendering often renders brush strokes and hatches along a vector field as well. Fur in computer-generated movies is typically derived from an artist-designed vector field to indicate hair direction and length (see inset). Vector fields can also be used to derive a quad mesh for which edges align to the local direction and scale of the field. Even animation can benefit from the notion of vector fields since they are the main physical variable to simulate all sorts of fluid motion on geometric domains. Finally, it is important to point out that vector fields are the simplest members of the more general notion of n-vector fields (also called n-rotational symmetry or n-RoSy fields) and n-direction fields (unit n-vector fields), which include direction (n = 1), line (n = 2) and cross (n = 4) fields. As such, knowing how to manipulate vector fields on surfaces often generalizes to more general fields without significant changes. 1.2 A first look at discrete vector fields cPixar/Disney Defining a tangent vector field on a triangulated surface is indubitably more involved than a scalar function. First, the very fact that each vector is supposed to be within a tangent plane is at odds with the fact that a triangle mesh does not even have a clear, canonical definition of a tangent space for points along an edge or at a vertex. Second, one could think that it is as simple as storing two scalar fields, one for each coordinate; but that would be assuming that one has previously defined a notion of local coordinate frame at every point on the surface—a difficult task in itself as it involves parameterization and defining two basis vector fields over the parameterization chart! No surprise, then, that there exist multiple ways of encoding a vector field over a mesh. Moreover, a vector field can contain a number of singularities, which often require careful handling in practical applications. For a scalar field, there are also special points, easily identified as local maxima, local minima, or saddle points; but the catalog of singularities for vector fields is now more involved. In fact one can define the index for a singularity that basically measures the angular variation of the vector field around a singularity (i.e., the number of times it coils around). Moreover, the sum of these indices for an arbitrary vector field must be fixed for a given surface. That is to say, you cannot ask a vector field for too much: the topology of the surface over which then tangent vector field is defined will force some global behavior. This is what the “hairy ball theorem” [Eisenberg and Guy 1979] states: you simply cannot comb a sphere without creating at least one cowlick somewhere; yet you can comb a
    doughnut, as these two geometric objects differ in topology. Geometry and topology of vector fields are thus intimately linked... Since we usually seek smooth-looking vector fields, we also need to define a notion of smoothness that is intuitive, both quantitatively (so that we can objectively refer to a vector field as being smoother than another) and visually (so that it looks nice in the “eyeball norm” as well). While smoothness and derivatives of scalar functions are typically high school topics, derivatives of vector fields on non-flat surfaces are more involved, and a few specific definitions of derivatives will be relevant for the design of vector fields. Only then can a user expect to turn a sparse set of constraints (prescribing alignment and magnitude) into a smooth vector field automatically fitting these input constraints—thus making the process of designing a vector field simple, intuitive, and hopefully fast. 1.3 Representations Since the choice of smoothness and input constraints depends very much on how vector fields are defined over a triangle mesh, we must first and foremost decide on a finite-dimensional representation of vector fields over the underlying surface. Such representations are often grounded in differential geometry, and will serve as the principles for the discretization of tangent vector fields on triangle meshes. In R2, we are used to manipulate vector fields as a set of two coordinates per point associated to a global coordinate system. Note that these coordinates depend on the choice of a basis, so the vector field is only encoded via coordinates. Yet the field itself is a geometrical object that retains its own identity regardless of how one chooses to describe it in a basis. For tangent vector fields on a non-flat surface, one cannot use a single coordinate frame; instead, one is required to define a coordinate frame for each tangent plane (possibly through charts) if one wishes to retain the two-coordinate representation of vector fields—and we will see that, fortunately, a triangle mesh provides ample opportunities to define local frames. A vector field then becomes an assignment of a tangent vector to each point on a manifold surface. In the language of fiber bundles1, a vector field is thus a section of the tangent bundle, in the sense that from all the tangent vectors associated to each point of the manifold, we pick a particular one, and this choice of tangent vector per surface point defines a vector field. Existing discrete representations of vector fields mimic this fiber bundle point of view as we will review in these notes. One can also do away with coordinates altogether. We will show that one can sample a vector field, much like one can sample a scalar field and, from these samples, a reconstruction of the original field can be found. Other ways to think of vector fields on manifolds in the continuous setting can also be leveraged to derive discrete representations. For instance, vector fields can be characterized as derivations of smooth functions on a manifold using directional derivative; this has led to an operator representation of vector fields, used first in fluid animation [Mullen et al. 2009; Pavlov et al. 2011; Gawlik et al. 2011], and more recently in geometry processing [Azencot et al. 2013; Azencot et al. 2015]. 1.4 Vector calculus Many of the elements of differential and integral calculus extend to vector fields quite naturally, but can involve advanced geometric notions. A particularly difficult endeavor in vector calculus over surfaces is how to talk about the difference between two nearby tangent vectors: while this notion is trivial in a flat space where coordinates in a common basis can be used, we have to find a proper geometric approach to define it on a curved domain. A covariant derivative introduces such an extra geometric structure on a manifold which allows vectors in neighboring tangent spaces to be compared. This extra structure is 1The term fiber bundle can be intuitively understood by thinking of it as a hairbrush: for each point of a base space (cylinder), there is a vector space (bristle) associated to it. A fiber bundle is thus a way of knitting together several spaces to create a bigger space. By picking a particular point on the bristle at each point of the base manifold in a continuous fashion, we construct a (cross-)section of the hairbrush (in our context, a vector field—but the same holds for any fiber field).
    necessary since there is no canonical way to compare vectors from different vector spaces. Covariant differentiation also helps to define the notion of parallel transport along a path, the analog of a translation in R2. Working with a connection on the tangent bundle (to compare two nearby tangent vectors, and thus induce a covariant derivative) will eliminate the need for awkward manipulations of Christoffel symbols traditionally found in differential geometry. Our course notes review various approximations of these notions, and as one might expect from any numerical treatment, various tradeoffs between simplicity and accuracy will be provided. 2 Overview The core of these course notes is made of three chapters, each reviewing one particular vector field representation on triangle meshes. By design, each chapter is essentially independent of the others. However, the order in which these chapters are presented was decided based on the complexity of the material. The reader can thus decide whether to read the chapters sequentially, or directly skip to the material most relevant to her. 2.1 A chapter-by-chapter synopsis Existing geometry processing methods generally use one of three different encoding of vector fields. We review them one by one, contrasting their pluses and minuses. Face-based vector fields. The first part of the course focuses on piecewise-constant vector fields per triangle. As a triangle is flat, it is particularly convenient to define a tangent vector on its supporting plane. Even with jumps between faces, we will be able to define discrete notions of divergence, curl, or even Laplacian of these vector fields, and we will point out that each vector field can be decomposed into curl- and divergence-free components using (plain or mixed) finite elements. We will also introduce a very simple discrete notion of connection, corresponding to a single angle for every pair of adjacent triangles, as an alternative way to think of the vector field which extends to arbitrary n-vector fields. Edge-based vector fields. The second part of the course discusses the use of edge integration (i.e., line integral) to represent a discrete vector field. We review how these edge values can, through piecewise-linear Whitney basis functions, be interpolated into vector fields or, equivalently, covector fields. This approach produces locally linear vector fields, although normal continuity across edges is not guaranteed. Nevertheless, discrete differential operators can be easily derived and computed just like in the previous case, from which one can easily design vector fields in realtime on triangle meshes. Vertex-based vector fields. The third and last part then reviews recent approaches encoding vector fields using vertex-based non-linear basis functions. By thinking of the one-ring of a vertex as a chart, a continuous vector field can be defined on an arbitrary triangle mesh, from which operators such as the divergence, curl, and covariant derivative can be directly derived. This will even allow us to define the notion of smoothest n-vector and n-direction field for a surface, which will correspond to a generalized eigenvalue problem. The reader will have noticed that the ordering also corresponds to various orders of continuity—from discontinuous to continuous—of the discrete representations. It also, coincidentally, involves increasingly complex computational tools to evaluate differential operators in a weak form on these vector fields. 2.2 Applications Applications using vector fields as input or guidance are legion. As our course focuses on the underlying representation of vector fields, we made no effort to review thoroughly the numerous geometry processing applications that each representation has been used in. Instead, we weaved examples of non-photo realistic rendering, quad meshing, or vector field design in every chapter to provide a more thorough
    description of the use of each representation. The reader interested in a broader perspective on these applications is referred to the numerous books and courses on geometry processing. 2.3 Notations Throughout these notes, we assume that we are working with a triangle mesh, approximating a smooth surface, that is of arbitrary topology, orientable, compact, and 2-manifold (possibly with boundary). We denote its vertex set V ={vi}, its edge set E ={eij} and its triangle set T ={tijk} (1≤ i, j, k ≤ n = |V |). Each triangle is counterclockwise oriented and each edge carries an arbitrary but fixed intrinsic orientation. Note that index order matters since eij has opposite orientation from eji, and similarly for triangles. Vertices are given positions P ={pv ∈R3|v∈ V }, which define the surface through piecewise linear interpolation over each triangle, so that pij = pj−pi represents the edge as a segment in R3. The intrinsic volumes of edges and triangles will be denoted |e| (length) and |t| (area), and we assume these are all nonzero, i.e., there are no degenerate edges. For a vertex, we define |v| = 1. We also assign a (lumped) area per edge and vertex: aij is one third of the triangle areas incident to eij, and ai is one third of the one-ring area. Moreover, we indicate αjki as the angle of the triangle tijk at vertex vk, so that the αkij. Finally, we denote discrete Gaussian curvature κi of vertex vi is the angle defect κi = 2π− the imaginary number as i when we use complex numbers. 3 Differential geometry primer for vector fields tijk In this section, we tersely review some key continuous geometric notions that will come up in these notes. While these notions can be introduced in various ways, we focus as much as possible on intrinsic definitions to provide a very geometric explanation of their meaning. For more details, see, e.g., [Abraham et al. 1988]. The reader is invited to refer back to this primer when the discretization of operators is discussed during the class, to better understand how the discrete and differential viewpoints coincide—yet sometimes differ. 3.1 Tangent Vector Fields Consider a compact topological 2-manifold M, covered by a collection (atlas) of charts that have C∞ smooth transition functions between each overlapping pair (which always exists [Grimm and Hughes 1995]). The notion of tangent planes and vectors can be defined intrinsically (i.e., independent of the embedding of the manifold in a Euclidean space) via, for instance, the tangency among smooth curves passing through a common point. Definition 1 ([Abraham et al. 1988]). Let x = (x1, x2) be a local chart mapping an open set U⊂M to R2. A smooth curve c passing through a point p∈ U is a map c : I → U for which the interval I ⊂ R contains 0, c(0) = p, and x ◦ c is C 2. Two smooth curves c1 and c2 are said to be tangent at p if and only if (1) (x ◦ c1)(0) = (x ◦ c2)(0). Note that this definition of tangency is independent of the choice of charts. Tangent curves can thus be used as an equivalence relation defining intrinsic vector spaces tangent to M. Definition 2 ([Abraham et al. 1988]). A tangent vector at p∈ M is the equivalence class [c]p of curves tangent to curve c at p. The space of tangent vectors is called the tangent space at p, denoted as TpM. The tangent bundle is the (disjoint) union of tangent spaces T M = ∪p∈M TpM. When the surface M has an embedding in R3, one can further express the tangent vectors as 3D vectors orthogonal to the surface normal, as classically explained in differential geometry of surfaces. Observe that the tangent space TpM at any point p∈ M is two dimensional and a tangent vector u = [c]p can
    be represented in components as (u1, u2) = ((x1 ◦ c)(0), (x2 ◦ c)(0)) given a chart x. Thus, the tan- gent bundle T M admits the structure of a 4-manifold with charts (x1, x2, u1, u2) induced by the atlas of M. Definition 3 ([Abraham et al. 1988]). A (tangent) vector field u is a continuous map M → T M from a point p∈ M to a vector u(p)∈ TpM. A local frame field of M on a chart is defined as two vector fields (e1, e2) that are linearly independent pointwise. Global frame fields do not exist in general, otherwise one could build a continuous vector field that is nonzero everywhere on a genus-0 surface, thus contradicting the hairy ball theorem [Eisenberg and Guy 1979]. Consequently, T M does not usually have the structure of M×R2, even though on a chart U, T U does have the structure of U×R2. On a chart with a local frame field, a vector field u can be expressed in components as u = u1e1 + u2e2. (2) The aforementioned chart of T M can be seen as a special case of the component representation, with ei (often denoted as ∂/∂xi) being the equivalence class of the curves generated by varying coordinate xi while keeping the other coordinate fixed. Definition 4 ([Abraham et al. 1988]). A covector ω at p is defined as a linear map ω : TpM → R. The space of covectors is a linear space itself, denoted as T ∗ One can likewise define smooth fields of covectors, which are also called (differential) 1-forms. They can be represented in local bases (η1, η2) defined by ηi(ej) = δi One can also augment a surface M with a metric by assigning an inner product (symmetric positive definite bilinear mapping) ·,·p for every tangent space TpM—e.g., for an embedded surface, it can be defined by the inner product of the corresponding 3D vectors in the 3D Euclidean space. Finally, we point out that the directional derivative of a function f over M w.r.t. a vector u = [c]p∈ TpM is defined as (f◦c)(0), corresponding to df (u) in the language of differential forms and to the more familiar inner product ∇f, u when a metric is available [Abraham et al. 1988]. 3.2 Covariant Derivative j given a frame field (e1, e2). pM. In order to take derivatives of vector fields, one must account for the fact that vectors in nearby tangent spaces are expressed on different local frames. The concept of covariant differentiation, denoted ∇, provides a principled way to compare nearby tangent vectors and measure their differences. The basic geometric intuition behind the covariant derivative of a vector field u at a point p is that ∇u encodes the rate of change of u around p. Projecting the derivative of a vector field u along a vector w leads to a vector ∇wu, which indicates the difference between vectors u(p) at p and u(q) at a nearby point q≡ c(), where c is a curve passing through p in the equivalence class w, and ∈R is approaching zero (Fig. 1). However, these vectors live in different tangent spaces, so the component-wise differences depend on the choice of local basis frames, and taking their differences in a manner that is purely in- trinsic (i.e., coordinate/frame independent) requires the additional notion of connection as we now review. Definition 5 ([Spivak 1979]). A covariant derivative (or an affine connection) is an operator ∇ mapping a vector w∈ TpM and a vector field u to a vector ∇wu∈ TpM, so that it is linear in both u and w and satisfies Leibniz’s product rule, i.e., for a vector field u and a smooth function f, one has ∇w(f u) = df (w)u + f∇wu. Using the representation of the vector field u in a local frame field (e1, e2), we can expand the covariant derivative through linearity and product rule in u as: dui(w)ei + ui∇wei , i=1,2 ∇wu =
    分享到：
    赞 收藏

    相关推荐

    资料库

    游戏开发

    共收录170份资料，累计3个分类，关注成员有19位，主要包括：cocos2D,其他,Unity3D

    热门标签

    cocos2D 其他 Unity3D

    最新资料