3D Game Programming intersection and particle Ming-Te Chi Department of Computer Science,  National Chengchi University 2018

Outline Intersection Particles -介紹鍵盤事件處理的技巧，以及如何得知畫面中物件的位置和名稱 -碰撞的概念 -粒子系統和物理模擬

Intersection

What you need to know Basic geometry Math helps… vectors, points, homogenous coordinates, affine transformations, dot product, cross product, vector projections, normals, planes Math helps… Linear algebra, calculus, differential equations 這一小單元的內容改編至由Ryan Schmidt設計的Everything you ever wanted to know about collision detection http://www.cpsc.ucalgary.ca/~ryansc

Plane Equations (Nx, Ny, Xz) A 3D Plane is defined by a normal and a distance along that normal Plane Equation: Find d: For test point (x,y,z), if plane equation > 0: point on ‘front’ side (in direction of normal), < 0: on ‘back’ side = 0: directly on plane 2D Line ‘Normal’: negate rise and run, find d using the same method P 利用平面方程式偵測，一點(x, y, z)落在平面的哪一側

So where do you start….? First you have to detect collisions With discrete timesteps, every frame you check to see if objects are intersecting (overlapping) Testing if your model’s actual volume overlaps another’s is too slow Use bounding volumes to approximate each object’s real volume 如果逐一的偵測每一個平面和平面是否有碰撞是非常複雜且計算龐大的工作 因此最好將物體以bounding box先代表，簡化計算量

Bounding Volumes Convex-ness is important. Spheres, cylinders, boxes, polyhedra, etc. Really you are only going to use spheres, boxes, and polyhedra (…and probably not polyhedra) Spheres are mostly used for fast culling For boxes and polyhedra, most intersection tests start with point inside-outside tests That’s why convexity matters. There is no general inside-outside test for a 3D concave polyhedron.

2D Point Inside-Outside Tests Convex Polygon Test Test point has to be on same side of all edges Concave Polygon Tests 360 degree angle summation Compute angles between test point and each vertex, inside if they sum to 360 Slow, dot product and acos for each angle!

Closest point on a line Handy for all sorts of things… Pt P2 Pc P1

Spheres as Bounding Volumes Simplest 3D Bounding Volume Center point and radius Point in/out test: Calculate distance between test point and center point If distance <= radius, point is inside You can save a square root by calculating the squared distance and comparing with the squared radius !!! (this makes things a lot faster) It is ALWAYS worth it to do a sphere test before any more complicated test. ALWAYS. I said ALWAYS.

Axis-Aligned Bounding Boxes Specified as two points: Normals are easy to calculate Simple point-inside test:

Problems With AABB’s Not very efficient Rotation can be complicated Must rotate all 8 points of box Other option is to rotate model and rebuild AABB, but this is not efficient

Heirarchical Bounding Volumes Sphere Trees, AABB Trees, OBB Trees Gran Turismo used Sphere Trees Trees are built automagically Usually precomputed, fitting is expensive Accurate bounding of concave objects Down to polygon level if necessary Still very fast See papers on-line Approximating Polyhedra with Spheres for Time-Critical Collision Detection, Philip M. Hubbard

Reducing Collision Tests Testing each object with all others is O(N2) At minimum, do bounding sphere tests first Reduce to O(N+k) with sweep-and-prune See SIGGRAPH 97 Physically Based Modelling Course Notes Spatial Subdivision is fast too Updating after movement can be complicated AABB is easiest to sort and maintain Not necessary to subdivide all 3 dimensions

Particles 接下來以粒子系統來介紹物理定律模擬的觀念

Dynamic Particle Simulation Simplest type of dynamics system Based on basic linear ODE: 常微分方程（ordinary differential equation，簡稱ODE） 牛頓力學第二定律 f=ma 描述外力對於物體質量的加速度變化 由這個式子分解，可以用計算的方式模擬第二運動定律的物理效果

Particle Movement Particle Definition: Position x(x,y,z) Velocity v(x,y,z) Mass m 在電腦數位離散的系統，要用來模擬物理的現像 可以將時間離散地切成間隔， 對於每一個時間間隔， 先根據目前的速度，更新物體的位置 再根據外力，更新新的速度

Collisions Once we detect a collision, we can calculate new path Use coefficient of resititution Reflect vertical component May have to use partial time step

Contact Force A force that acts at the point of contact between two objects

Using Particle Dynamics Each timestep: Update position (add velocity) Calculate forces on particle Update velocity (add force over mass) Model has no rotational velocity You can hack this in by rotating the velocity vector each frame Causes problems with collision response 將以上的概念撰寫成程式 便是在每個時間間距依序更新位置、取得外力(常見的外力有重力)，更新速度 以下外力未考慮旋轉的加速度，如果同學有興趣，可以進一步思考如何整合

Particle Init for(i=0; i<num_particles; i++) { particles[i].mass = 1.0; particles[i].color = i%8; for(j=0; j<3; j++) particles[i].position[j] = 2.0*((float) rand()/RAND_MAX)-1.0; particles[i].velocity[j] = speed*2.0*((float) rand()/RAND_MAX)-1.0; } glPointSize(point_size); 先初始化每一個粒子的位置和加速度向量和大小

update void myIdle() { int i, j, k; float dt; present_time = glutGet(GLUT_ELAPSED_TIME); dt = 0.001*(present_time - last_time); for(i=0; i<num_particles; i++) for(j=0; j<3; j++) particles[i].position[j] += dt*particles[i].velocity[j]; particles[i].velocity[j] += dt*forces(i,j)/particles[i].mass; } collision(i); 當idle事件發生時 先取得和上一次idle的時間差 接下來 先更新位置 再更新速度向量 接下來偵測是否有碰撞

collision int i; for (i=0; i<3; i++) { if(particles[n].position[i]>=1.0) particles[n].velocity[i] = -coef*particles[n].velocity[i]; particles[n].position[i] = 1.0-coef*(particles[n].position[i]-1.0); } if(particles[n].position[i]<=-1.0) particles[n].position[i] = -1.0-coef*(particles[n].position[i]+1.0); 在這個例子，所有的例子都在一個(-1, -1, -1)到(1, 1, 1)的立方體 只有當碰撞到立方體的時才需改變速度向量

Helpful Books Real Time Rendering Graphics Gems series Lots of these notes derived from this book Graphics Gems series Lots of errors, find errata on internet Numerical Recipes in C The mathematical computing bible Game Programming Gems Not much on CD, but lots of neat tricks Lex & Yacc (published by O’reilly) Not about CD, but useful for reading data files

about PC hardware Cache Memory Conditionals are Evil Linear memory access at all costs! Wasting cycles and space to get linear access is often faster. It is worth it to do some profiling. DO NOT USE LINKED LISTS. They are bad. STL vector<T> class is great, so is STL string vector<T> is basically a dynamically-sized array vector.begin() returns a pointer to front of array Conditionals are Evil Branch prediction makes conditionals dangerous They can trash the pipeline, minimize them if possible

about C/C++ compilers Compilers only inline code in headers The inline keyword is only a hint If the code isn’t in a header, inlining is impossible Inlining can be an insane speedup Avoid the temptation to be too OO Simple objects should have simple classes Eg: writing your own templated, dynamically resizable vector class with a bunch of overloaded operators is probably not going to be worth it in the end.

Lots of algorithms have degenerate conditions Numerical Computing Lots of algorithms have degenerate conditions Learn to use isinf(), isnan(), finite() Testing for X = 0 is dangerous If X != 0, but is really small, many algorithms will still degenerate Often better to test fabs(X) < (small number) Avoid sqrt(), pow() – they are slow

Physics engine 2D 3D Box2D http://box2d.org/ bullet3D http://bulletphysics.org PhysX http://developer.nvidia.com/physx 除了自己實做物理模擬 現在有物理引擎，對於物理模擬所需要的元件做有效率地設計 善用這些函式庫，可做出更有趣的遊戲