基于物理的建模与动画 Chapter One - Three_基于物理的建模与动画 pdf

本书以 基于物理的建模与动画（Foundations of Physically Based Modeling and Animation） 为textbook

Chapter One. Introduction

four parts

1. fundmental
   Chapter One - Three
2. paritcles
   Chapter Four - Eight
3. rigid body dynamics
   Chapter Nine - Twelve
4. simulation of fluid
   Chapter Thirteen = Fifteen

Chapter Two. Model & Simulation

Euler method

Chapter Three. Collision & elastic sphere

3.1 collision process

1. collision detection
   whether collide or not
2. collision determination
   when and where collide occured
3. collision response
   effect of collision

3.1.1 collision detection

For a point $(x_0,y_0,z_0)$ and a plane $Ax+By+Cz=0$, we can use the value of $P(x_0,y_0,z_0)=A{x}_0+B{y}_0+C{z}_0$ to determine which side the point belongs.

Another common method is to use normal vector $\hat{n}=[n_x{n}_y{n}_z{]}^T$and a point $p(p_x,p_y,p_z)$ on the plane.
These variables can construct a plane like $n_{x}x+n_{y}y+n_{z}z-\hat{\mathbf{n}}\cdot \mathbf{p}=0$, or in concise terms $(\mathbf{x}-\mathbf{p})\cdot \hat{\mathbf{n}}=0$
The projection distance from point to plane can be got by $d=(\mathbf{x}-\mathbf{p})\cdot \hat{\mathbf{n}}$

3.1.2 collision determination

The following is got by Euler method
We use $d^{[n]}$ denotes the projection distance timestep begins, and $d^{[n+1]}$ denotes timestep ends.
We suppose that the velocity is constant in the duration.(Euler method)
So we can get the timestep fraction $f=\frac{d^{[n]}}{d^{[n]}-d^{[n+1]}}$,
and the timestep when the collision occurs in this turn is $fh$.
Using this,we get the new state and calculate the remain timestep.

pseudo code:
h is timestep, n is step, t is current time, s is state

s = s0, n = 0, t = 0;
while t < tmax do
{
	TimestepRemaining = h;
	Timestep = TimestepRemaining;
	while TimestepRemaining > 0
	{
		s_deriv = GetDeriv(S);
		s_new = Intergate(s, s_deriv, Timestep);
		if CollisionBetween(s, s_new)
		{
			calcuate f;		// f means timestep fraction
			Timestep_collision = f * Timestep;
			s_new = Intergate(s, s_deriv, Timestep_collision);
			CollisionResponse(s_new);
		}
		TimestepRemaining = TimestepRemaining - Timestep;
		s = s_new;
	}
	n = n + 1, t = n * h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.1.3 collision response

In this chapter, we simplify the siutuation and suppose there is no rotation and the plane is infinite.
The collision response can be devided two parts, elasticity & friction.Here we use ${}^{-}$ to denote the state before collision, ${}^{+}$ to denote the state after collision.
From the sumption, we know $x^{-}=x^{+}$, and we want to get $v^{+}$ from $v^{-}$
Let $\hat{\mathbf{n}}$ denote the normal factor, we know ${\mathbf{v}}_{\mathbf{n}}^{-}=({\mathbf{v}}^{-}\cdot \hat{\mathbf{n}})\hat{\mathbf{n}},{\mathbf{v}}_{\mathbf{t}}^{-}={\mathbf{v}}^{-}-{\mathbf{v}}_{\mathbf{n}}^{-}$

3.1.3.1 elasticity

coefficient of restitution $c_r$
${\mathbf{v}}_{\mathbf{n}}^{+}=-c_r{\mathbf{v}}_{\mathbf{n}}^{-}=-c_r({\mathbf{v}}^{-}\cdot \hat{\mathbf{n}})\hat{\mathbf{n}}$

3.1.3.2 friction

coefficient of friction $c_f$
${\mathbf{v}}_{\mathbf{t}}^{+}=(1-c_f){\mathbf{v}}_{\mathbf{t}}^{-}=(1-c_f)({\mathbf{v}}^{-}-{\mathbf{v}}_{\mathbf{n}}^{-})$
Another point to be considerated is the bound of ${\mathbf{v}}_{\mathbf{t}}^{+}⩾0$
${\mathbf{v}}_{\mathbf{t}}^{+}={\mathbf{v}}_{\mathbf{t}}^{-}-min(\mu ||{\mathbf{v}}_{\mathbf{n}}^{-}||,||{\mathbf{v}}_{\mathbf{t}}^{-}||)\widehat{{\mathbf{v}}_{\mathbf{t}}^{-}}$

then we can get the final ${\mathbf{v}}^{+}={\mathbf{v}}_{\mathbf{n}}^{+}+{\mathbf{v}}_{\mathbf{t}}^{+}$

3.2 Bouncing ball

The problem we face in this stage is numberical precision & resting condition.

3.2.1 numerical precesion

a useful method is to avoid round-off error is tolerance.
$a-b=0\Rightarrow a>b-ϵ$ & $a<b+ϵ$
$a>b\Rightarrow a-b>ϵ$
$a<b\Rightarrow a-b<-ϵ$

While tolerance still has two limitis.

1. First, it’s difficult to find a good enough number, which not only captures all the error, but also doesn’t cause misjudgment of equality.
2. The second problem is incidence intransitivity.
   $a=b$ & $b=c$ may not reach a conclusion that $a=c$

3.2.2 resting condition

Four steps:

1. $||\mathbf{v}||<{ϵ}_1$
2. whether there is a plane to make $d<{ϵ}_2$ or not
3. $\mathbf{F}\cdot \hat{\mathbf{n}}<{ϵ}_3$
   here $F$ is the total force, $\hat{\mathbf{n}}$ is normal vector
4. $||{\mathbf{F}}_{\mathbf{t}}||<\mu ||{\mathbf{F}}_{\mathbf{n}}||$

However, in complex simulations, it’s a NP-complete problem to calculate accurately.More content is in Chapter Nine.

3.3 Polygonal geometry

The actual situation is that the plane is finite.
A plane can be uniquely represented by normal vector $\hat{\mathbf{n}}$ and a point $\mathbf{p}$ on plane.
$\hat{\mathbf{n}}=\frac{({\mathbf{p}}_1-{\mathbf{p}}_0)\ast ({\mathbf{p}}_2-{\mathbf{p}}_0)}{||({\mathbf{p}}_1-{\mathbf{p}}_0)\ast ({\mathbf{p}}_2-{\mathbf{p}}_0)||}$
Let $\mathbf{p}={\mathbf{p}}_0$ (${\mathbf{p}}_0$ is a point on the plane, or vertex of polygonal geometry particularly)
The distance from point $\mathbf{x}$ to the plane can be represented by
$d=(\mathbf{x}-\mathbf{p})\cdot \hat{\mathbf{n}}$
All the point on the plane satisfy $(\mathbf{x}-\mathbf{p})\cdot \hat{\mathbf{n}}=0$

fault

3.3.1 P31 tolerance $ϵ$,$a-b>ϵ$