計算機科學(xué)與數(shù)學(xué)

計算機科學(xué)與數(shù)學(xué)

郭百寧

微軟亞洲研究院

“諸位在校，有兩個問題應(yīng)該問問自己：

第一，到浙大來做什么？第二，將來畢業(yè)

了做什么樣的人？”

浙江大學(xué)前校長竺可楨

學(xué)習(xí)計算機科學(xué)=學(xué)習(xí)編程?

計算機科學(xué)

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

□數(shù)學(xué)是基礎(chǔ)（內(nèi)功心法）

□增強數(shù)學(xué)功力，提高學(xué)習(xí)層次

物理學(xué)本身也分成了許多獨立的領(lǐng)域，其中

每一個領(lǐng)域都可以消耗我們短促的一生的全部精

力，還不一定能滿足我們獲得更深奧知識的欲望

O在這里，大量彼此間無聯(lián)系的試驗數(shù)據(jù)也是人

們難以招架的?？墒窃谶@個領(lǐng)域中。我很快就學(xué)

會從一大堆充斥我們的頭腦、分散我們對本質(zhì)事

物注意力的東西中，分辨出哪些可能導(dǎo)致根本性

的結(jié)果，而置其他于不顧。

愛因斯坦

要掌握物理學(xué)基本原理方面的更

淵博的知識，離不開非常錯綜復(fù)雜的

數(shù)學(xué)方法。經(jīng)過多年的獨立科學(xué)研究

,我才逐漸明白了這個道理。

愛因斯坦

科學(xué)的崛起總是伴隨數(shù)學(xué)的突飛猛進(jìn)

文藝復(fù)興時期

?笛卡兒(1596-1650)

-解析幾何：笛卡兒坐標(biāo)系

?德薩格(1591-1661)

-射影幾何

?費馬(1601-1665)

■變分原理：測地線

?牛頓(1642-1727)

-微積分I

?萊布尼茨(1646-1716)

-微積分

???相信我，如果我可以重新開始學(xué)習(xí)，我將聽

從柏拉圖的建議，從數(shù)學(xué)開始。

伽利略

數(shù)學(xué)的威力（魅力）

□透過表面現(xiàn)象，看到最重要的基本原理

■例：歐氏幾何

□科學(xué)的深入總是伴隨與數(shù)學(xué)的深層次結(jié)合

■例：物理學(xué)的幾何化

■抽象但威力巨大

歐幾里得（公元前350年）《原本》

?歐幾里得幾何公設(shè)

■任意兩點間可作唯一的直線

■任何線段可以無限延長

■以任一點為中心和任一距離為

半徑可作一圓

■所有直角彼此相等

■對于一直線L和該直線外的一點

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

相交的直線。

源于少數(shù)原理，...卻結(jié)出累累碩果,

這就是幾何的驕傲。

——牛頓

物理基本原理的幾何命題

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

封閉表面的電通量典封閉曲面內(nèi)電荷之間的關(guān)

系。

□法拉第電磁感應(yīng)定律是電磁學(xué)中的一條基本定

律，跟變壓器、電感元件及多種發(fā)電機的運作

有密切關(guān)系（任何封閉電路中感應(yīng)電動勢的大

小，等于穿過這一電路磁通量的變化率）。

□幾何命題：一個區(qū)域的邊界是沒有邊界的

―■—詳見:—楊振寧，“愛因斯坦對物理學(xué)的貢獻(xiàn)）

物理學(xué)的幾何化

圖的b.l

一個區(qū)域的邊界是沒有邊界的。此繆畢烏斯(

Moebius)條帶僅有一個表面，其邊界是單一邊緣，可

是邊緣本身并無邊界。關(guān)于此定理的進(jìn)一步解釋，見

圖80b,2。［楊振寧：“愛因斯坦對物理學(xué)的貢獻(xiàn)”，

插圖由路易斯?富爾干尼(LouisFulgoni)作。］

物理學(xué)的幾何化

圖80b.2拓?fù)鋵W(xué)定理

一個區(qū)域的邊界本身沒有邊界。在左圖中，帶陰影的二維區(qū)

域有一個一維圈作其邊界。此圈沒有端點，即它本身并無邊界。

中圖的三維區(qū)域由一個封閉的二維曲面限定其范圍。這個曲

面同樣無邊緣，也就是無邊界。

若我們將此區(qū)域割開，拋去下部，則給了曲面一邊緣。但同

時我們另外創(chuàng)造出一個平面，如右圖所示。此圖中的三維區(qū)域的

邊界包括兩部分，一為曲面，一為平面。每一部分都有邊界，這

兩個邊界正好方向也相反，互相抵消，所以右圖的三維區(qū)域的總

邊界也沒有邊界。

回到計算機科學(xué)。。

□透過表面現(xiàn)象，看到最重要的基本原理

□學(xué)問的深入總是伴隨與數(shù)學(xué)的深層次結(jié)合

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