计算机科学与数学

计算机科学与数学

郭百宁

微软亚洲研究院

“诸位在校，有两个问题应该问问自己：

第一，到浙大来做什么？第二，将来毕业

了做什么样的人？”

浙江大学前校长竺可桢

学习计算机科学=学习编程?

计算机科学

□编程是工具（拳法招式）

□数学是基础（内功心法）

□增强数学功力，提高学习层次

物理学本身也分成了许多独立的领域，其中

每一个领域都可以消耗我们短促的一生的全部精

力，还不一定能满足我们获得更深奥知识的欲望

O在这里，大量彼此间无联系的试验数据也是人

们难以招架的。可是在这个领域中。我很快就学

会从一大堆充斥我们的头脑、分散我们对本质事

物注意力的东西中，分辨出哪些可能导致根本性

的结果，而置其他于不顾。

爱因斯坦

要掌握物理学基本原理方面的更

渊博的知识，离不开非常错综复杂的

数学方法。经过多年的独立科学研究

,我才逐渐明白了这个道理。

爱因斯坦

科学的崛起总是伴随数学的突飞猛进

文艺复兴时期

•笛卡儿(1596-1650)

-解析几何：笛卡儿坐标系

•德萨格(1591-1661)

-射影几何

•费马(1601-1665)

■变分原理：测地线

•牛顿(1642-1727)

-微积分I

•莱布尼茨(1646-1716)

-微积分

・・・相信我，如果我可以重新开始学习，我将听

从柏拉图的建议，从数学开始。

伽利略

数学的威力（魅力）

□透过表面现象，看到最重要的基本原理

■例：欧氏几何

□科学的深入总是伴随与数学的深层次结合

■例：物理学的几何化

■抽象但威力巨大

欧几里得（公元前350年）《原本》

•欧几里得几何公设

■任意两点间可作唯一的直线

■任何线段可以无限延长

■以任一点为中心和任一距离为

半径可作一圆

■所有直角彼此相等

■对于一直线L和该直线外的一点

P,存在唯一通过P,并和L不

相交的直线。

源于少数原理，...却结出累累硕果,

这就是几何的骄傲。

——牛顿

物理基本原理的几何命题

□高斯定律是重磁阜裹的重要定理，阐明了流出

封闭表面的电通量典封闭曲面内电荷之间的关

系。

□法拉第电磁感应定律是电磁学中的一条基本定

律，跟变压器、电感元件及多种发电机的运作

有密切关系（任何封闭电路中感应电动势的大

小，等于穿过这一电路磁通量的变化率）。

□几何命题：一个区域的边界是没有边界的

―■—详见:—杨振宁，“爱因斯坦对物理学的贡献）

物理学的几何化

图的b.l

一个区域的边界是没有边界的。此缪毕乌斯(

Moebius)条带仅有一个表面，其边界是单一边缘，可

是边缘本身并无边界。关于此定理的进一步解释，见

图80b,2。［杨振宁：“爱因斯坦对物理学的贡献”，

插图由路易斯・富尔干尼(LouisFulgoni)作。］

物理学的几何化

图80b.2拓扑学定理

一个区域的边界本身没有边界。在左图中，带阴影的二维区

域有一个一维圈作其边界。此圈没有端点，即它本身并无边界。

中图的三维区域由一个封闭的二维曲面限定其范围。这个曲

面同样无边缘，也就是无边界。

若我们将此区域割开，抛去下部，则给了曲面一边缘。但同

时我们另外创造出一个平面，如右图所示。此图中的三维区域的

边界包括两部分，一为曲面，一为平面。每一部分都有边界，这

两个边界正好方向也相反，互相抵消，所以右图的三维区域的总

边界也没有边界。

回到计算机科学。。

□透过表面现象，看到最重要的基本原理

□学问的深入总是伴随与数学的深层次结合

Gradient-BasedAlgorithmsfor

ShapeDeformation

Shapedeformation

Whyit'ssohard?

□Detailpreservation

□Localchanges—>globaleffects

□Seamless:Noartifacts!

Whyit'ssohard?

Whyit'ssohard?

Gradient-BasedAlgorithms

SimeonDenisPoisson

□Histeachers:Laplace,Lagrangef...

□Poisson'sterms:

■Poisson'sequation

■Poisson'sintegral

■Poissondistribution

■Poissonbrackets

■Poisson'sratio

■Poisson'sconstant

1781-1840,France

“Lifeisgoodforonlytwothings:tostudymathematicsandtoteachit：'

PoissonEquation

a2a2

A=

*=—p

p=夕（羽y）

Boundaryconditions

□Dirichletboundaryconditions:f卜。

□Neumannboundaryconditions:

Existenceofsolution

ThesolutionofaPoissonEquationisuniquely

determinedinQ,ifDirichletboundaryconditionsor

Neumannboundaryconditionsarespecifiedon6Q

Physicalorigins

□Electrostaticpotential

人不夕(x)

A①二J、

%

□Gravitationalpotential

A①=-4^Gp(x)

Electrostaticpotential4宓

P（x）ChargeDensity

①ElectricPotential

EElectricField

E=—V①

Derivations

GaussJs

Law:

Gauss's

theorem:

人不夕(X)

A①=

£。

E=—V①PoissonEquation

Relationships

8

管=ME）既写

p

Density

e

(

0

(

C

O

K

")

H

<(X

Q)

「mMGr

F=--------

Gravitationalpotential/

P(x)MassDensity

①GravitationalPotential

gForceField

(acceleration)

g=—V①

Relationships

g

Potential

A①=-4/iGp(x)

AnalogyforGeometry

①ScalarfieldonMesh(Potential)DensityonMesh

AnalogyforImage

p(x)ImageDensity

Image(Potential)

gImageGradient

g=—▽/

Relationships

0g.ds

夕(x)=由v(g)=lim-........

p

Density

A/=-Q(X)

SeamlessCloning

Preciseselection:tediousandunsatisfactory

Alpha-Matting:powerfulbutinvolved

Seamlesscloning:looseselectionbutnoseams?

Perez,Gangnet&Blake,«PoissonImageEditing»

CloningbysolvingPoissonEquation

AZ=div(VIA)s.t.IlaQ=IBlaQ

Perez,Gangnet&Blake,«PoissonImageEditing»

VectorFieldsandPoissonEquation

•Givenavectorfieldw,howcanweapproximate

itusingthegradientfieldofascalarfunction?

-Mathematically,wewanttosolvethisminimization

minjJcW①-dA

•ThePoissonequationsolvesthesameproblem.

-Itrecoversanunknownscalarfunctionfromagiven

vector“guidance”fieldandaboundarycondition.

=①)=V・w①怎=/、

''Beautyandbeast"?

Perez,Gangnet&Blake,«PoissonImageEditing»

Or,"beauty"ancT'beast”?

Perez,Gangnet&Blake,«PoissonImageEditing»

Gradient-BasedAlgorithms

□Localchanges-►globaleffects

□Detailpreservation

□Seamless:Avoidartifactsby

distributingerrorsusingleast-squares

minimization

DiscreteFieldsonTriangleMeshes

[PolthierandPreuss2000]

•Neednewfielddefinitionsfordiscreteirregulargrids,

suchasatrianglemesh.

•DiscreteVectorFields

-Piecewiseconstantvectorfields,i.e.aconstantvector

withineachtriangle.Thevectoriscoplanarwiththetriangle.

•DiscretePotentialFields

-Piecewiselinearpotentialfields,i.e.thepotentialisalinear

combinationofpiecewise-linearbasisfunctions.

-0(x)=£a与(x)

-wheretheweightsforthebasesaredefinedattheverticesofthe

grid.

PoissonEquationonTriangleMeshes

[Tongetal.2003]

•APoissonequationfordiscretefieldsontriangle

meshescanbedefined.

Div(V①)=Divw

(DivwXv;)=工.展卜•

-Div:discretedivergenceoperator

-Mostimportantly,thediscretePoissonequationhas

essentiallythesamepropertiesastheoriginal

Poissonequation.

AnalogyforGeometry

①ScalarfieldonMesh(Potential)DensityonMesh

ABasicPoissonMeshSolver

•Eachofthex,yorzcoordinatesoverameshisa

piecewise-linearfunctiondefinedoveritself.

-Therespectivecoordinateoftheverticesaretheweightsforthe

basisfunctions.

•Thegradientofsuchfunctionsarepiecewiseconstant

vectorfields.

3vectorspertriangle

Theyarecoplanar

withthetriangle

•Keyobservation:Ifwemodifythesevectorfields,new

potentialfields(vertexcoordinates)canbereconstructed

usingthePoissonequation.Thatis,anewmeshis

generated!Howtomodifythevectorfields?

PoissonMeshDeformation

Step1:SpedfyGontrolcurveStep2:Editcontrolcurve

PoissonMeshDeformation

Step3:PropagatelocalStep4:SolvePoissonequation

frametransformations

PoissonMeshDeformation

△U=divWs.t.fI须=/I阳

MeshGeometryGuidanceFieldBoundaryCondition

InteractiveMesh

Deformation

DeformationInterface

□3Dcurvemanipulation[Yu04]

■Tediousandrequireartisticskill

□2Dsketch-basedinterface

■Modeling:Teddyrashi99]

■Editing:[Zelinka04/Kho05/Nealen05]

“Teddy-like”deformation:

intuitiveandeasytouse

2DSketch-basedDeformation

DeformationRetargeting

6

£

1

①

p

f

①

一

U

0

4

B

E

0

J

①

。

Results

2DCartoon3DDeformation

Results

2DCartoon3DDeformation

Results

2DCartoon3DDeformation

Results

2DCartoon3DDeformation

Results

3DDeformation

DeformationConstraints

SIGGRAPH2006

•Gradient-basedalgorithmaregoodatpreservingsurface

details

•Butmanyimportantconstraintscannotbehandled

volumeconstraintskeletonconstraint

SubspaceDeformation

SIGGRAPH2006

•Ageneralframeworkforconstraineddeformation

一Laplacianconstraint-surfacedetails

一Skeletonconstraint-articulatedobjects

一Volumeconstraint-incompressibleobjects

一Projectionconstraint-easymanipulationina2DGUI

•Asubspacesolverfornonlinearconstraints

-Fastandstable

SkeletonConstraint

SIGGRAPH2006

•Articulatedobjects

withskeletonwithoutskeleton

ConstrainedNonlinear

Least-SquaresProblem

min||AX—Z?(X)『subjecttog(x)=0

X

Xvertexpositions

Aconstantmatrix

b(X)nonlinearvectorfunction

g(x)nonlinearvectorfunction

IterativeGauss-NewtonSolver

min||AX—b(X^2subjecttog(x)=0

X

a

min||AXfc+1-Z?(X^|2subjecttog(X川)=0

X

@Slowconvergence

Instability

conventionalsolveroursubspacesolver

SubspaceSolver

MeanValueCoordinates

[Floater05,Ju05]

x，=2＞，,P

j

X二WP

SubspaceSolver

mimin||AX-/?(X)||2subjecttog(X)=0

X

0

min||AWP-b(WP)『subjecttog(WP)=0

XO

A+1

AWpi—b(Wpz)2subjecttog(WP)=0

一Fewervariables,

muchfaster,5x

Morerobust(smooth

analysis)

SubspaceSolver

SIGGRAPH2006

•Handlearbitrary3Dmodels

-Non-manifolds,multipledisconnectedcomponents

SubspaceSolver

SIGGRAPH2006

•Handlearbitrary3Dmodels

-Non-manifolds,multipledisconnectedcomponents

SubspaceSolver

SIGGRAPH2006

•Satisfyconstraintsimposedontheoriginalmodel

-NO-constraintsonthecontrolmesh

originalmodelsimpleinterpolationoursubspacemethod

Results

SIGGRAPH2006

•Adinosaurwalkingbyonlydragginghandles

Results

SIGGRAPH2006

•Ahorsewith

Results

SIGGRAPH2006

•ASantamodelwithmultiplecomponents

SubdivisionSurfaces

SIGGRAPH2007

•Interactivedeformationofsubdivisionsurfaces

一Directmanipulation,detailpreservation,realtime

#vertices184066

»faces:368128

displacement:on

fps:125.7fps:114.5

SIGG