مدلهای الگوریتمی و فیزیکی، سامانههای ذرهای و قیود
فصل ۹ — روشهای Procedural
تا اینجا فرض کردهایم Geometric Objectها با Surfaceهایشان توصیف میشوند و Surfaceها با Convex Planar Polygon مدل یا تقریب زده میشوند. Polygonal Model بهدلیل سادگی Description و قابلیت Rendering مستقیم روی Graphics Systemهای موجود بسیار موفق بوده است.
بااینحال، حتی در CAD بزرگ، Flight Simulator، Computer Animation، Interactive Game و Film VFX محدودیتهای این روش روشن شد. پدیدههایی مانند Cloud، Smoke و Water با مجموعهای ثابت از Polygonها بهخوبی مدل نمیشوند؛ افزودن Physical Constraint و Complex Behavior نیز ذاتاً بخشی از Polygonal Modeling نیست.
در پاسخ، Procedural Modelها توسعه یافتند: روشهای Algorithmic برای ساخت Representation پدیدهٔ زیربنایی که Polygon را فقط هنگام نیاز در Rendering Process تولید میکنند.
۹٫۱ Algorithmic Modelها
در تاریخ Computer Graphics، میل به Realism تقریباً همیشه از رشد Hardware سریعتر بوده است. حتی اگر Commodity Hardware بیش از دهها میلیون Polygon در ثانیه Render کند، Flight Simulation، Virtual Reality و Game ممکن است صدها میلیون Polygon در ثانیه بخواهند و یک Data Set منفرد میتواند بیش از یک میلیارد Polygon داشته باشد.
بخشی از این نیاز ناشی از Modeling Paradigmهای موجود است. اگر Model فقط Polygonهایی را تولید کند که هم Visible هستند و هم Projection آنها حداقل به اندازهٔ یک Pixel است، تعداد Polygon لازم میتواند بسیار کمتر شود. نمونهای از این ایده را در Culling پیش از Rendering Pipeline دیدهایم.
Procedural Methodها Object را Algorithmically توصیف و Polygon را فقط هنگام نیاز تولید میکنند. Analogy مفید، نمایش Irrational Numberها در Computer است. مثلاً (\sqrt2) را میتوان با Decimal Approximation، Equation (x^2=2)، یا Algorithm تعریف کرد.
Newton Method از (x_0=1) شروع میکند و Recurrence زیر را تکرار میکند:
x_{k+1}=\frac{x_k}{2}+\frac{1}{x_k}.
هر مقدار تقریب بهتری از (\sqrt2) است. بنابراین Number از دید Computer میتواند Program/Algorithm باشد.
در Graphics نیز Sphere مرکز مبدأ را میتوان با Equation
x^2+y^2+z^2=r^2
یا با Algorithm Subdivision چهاروجهی فصل ۵ تعریف کرد. مزیت View دوم این است که Sphere کوچک در Screen Space میتواند با Triangle کمتر و Sphere بزرگ با Detail بیشتر Render شود.
مشکل دوم Polygonal Modeling، ادغام دشوار Graphics با Physical Law است. ساخت و Animateکردن Polygonal Object ساده است، اما جلوگیری از نفوذ Solidها در یکدیگر و شبیهسازی Collision فیزیکی صحیح بسیار دشوارتر است.
چهار رویکرد Procedural معرفی میشود. نخست Particle System مبتنی بر Newtonian Physics است. گروهی از Particleها با حل Coupled Differential Equationها رفتار پیچیده تولید میکنند و Position آنها محل قرارگیری Graphical Objectها را میدهد.
رویکرد دوم Language-Based Model است که Complexity را با Ruleهایی شبیه Natural/Computer Language کنترل میکند و Objectهای طبیعی را با Grammarهای کوتاه تولید مینماید. ترکیب آن با Fractal Geometry امکان تولید فقط همان تعداد Polygon لازم برای Display را میدهد.
رویکرد سوم Fractal Geometry بر Self-Similarity پدیدههای طبیعی تکیه دارد و Model را در Level of Detail دلخواه تولید میکند. رویکرد چهارم Procedural Noise برای افزودن Randomness کنترلشده است و در Texture Map، Turbulence، Motion و Objectهای Fuzzy مانند Cloud استفاده میشود.
۹٫۲ مدلهای Physically Based و Particle Systemها
قدرت و در عین حال ضعف Computer Graphics این است که Model میتواند بر هر Principle دلخواه بنا شود و الزاماً Physical Reality را رعایت نکند. سنت رایج این بود که اگر Result «درست به نظر برسد» کافی است. این آزادی برای Special Effect در Game/Film و نیز Scientific Visualization بسیار مفید بوده است؛ میتوان Shapeهایی را دید که در فضای سهبعدی عادی وجود ندارند یا Prototypeهایی ساخت که Material/Equipment واقعی هنوز اجازهٔ ساختشان را نمیدهد.
اما در Simulation دنیای واقعی مشکل آغاز میشود. حرکت گروهی Object در Space ساده است، ولی Detectکردن Collision و Response فیزیکی درست سخت است. در Computer Graphics بسیار آسانتر است Ball از Wall عبور کند تا اینکه Elastic Bounce آن صحیح مدل شود.
Physically Based Modeling Objectهای گرافیکی را تابع Physical Law میکند. یک مسیر، مدلکردن Physics کامل Process و Driveکردن Graphics از Dynamics/Continuum Mechanics است. مسیر دوم استفاده از Basic Physics بههمراه Mathematical Constraint برای کنترل Dynamic Behavior است؛ این فصل مسیر دوم را برای Particleها دنبال میکند.
Particle System مجموعهای از Particleها، معمولاً Point Mass، است که Dynamic Behavior آنها با حل Coupled Differential Equationها تعیین میشود. در Fluid Dynamics میتوان بهجای حل مستقیم PDE، گروه Particleهای تحت Force/Constraint را دنبال کرد. Solid Deformable نیز میتواند Array سهبعدی Particleهای متصل با Spring باشد؛ Force خارجی Particleها را جابهجا میکند و Position آنها Shape Solid را تقریب میزند.
در Graphics، Particle System برای Firework، Flocking Bird، Wave و پدیدههای بسیار دیگری استفاده میشود. Dynamics فقط Position Particleها را میدهد؛ در هر Position میتوان بهجای Point یک Graphical Object مانند Spark یا Character قرار داد.
برای هر Particle قوانین فیزیکی Equationهایی ایجاد میکنند که Numerically در Time Stepها حل میشوند. پس از Update State، هر Particle Render میشود.
۹٫۳ Newtonian Particleها
مجموعهای از Particleها را تابع Newton’s Laws در نظر میگیریم. مزیت Newtonian Model، Physics ساده و شناختهشده همراه با دامنهٔ وسیع Behavior است.
Newton’s Second Law:
ma=f,
که در آن Mass m ضربدر Acceleration Vector a برابر Sum Force Vectorهاست.
برای Ideal Point Mass، State فقط با Position و Velocity تعیین میشود. بنابراین Particle در سه بعد ۶ Degree of Freedom و System با n Particle دارای 6n State Variable است.
State Particle i شامل Position
p_i=\begin{bmatrix}x_i\\y_i\\z_i\end{bmatrix}
و Velocity
v_i=\begin{bmatrix}\dot{x}_i\\\dot{y}_i\\\dot{z}_i\end{bmatrix}
است. چون Acceleration مشتق Velocity و Velocity مشتق Position است، Newton’s Law به شش First-Order Differential Equation برای هر Particle تبدیل میشود:
\dot p_i=v_i,
\dot v_i=\frac{1}{m_i}f_i(t).
پس Dynamics مجموعهٔ n Particle با 6n Coupled Ordinary Differential Equation کنترل میشود.
هر Particle علاوه بر State میتواند Attributeهایی مانند Mass و Propertyهای Behavior/Display داشته باشد. Render Attributeها Color، Shape و Surface Property را تعیین میکنند. هر Particle از نظر Dynamics Point Mass است، ولی از نظر Display میتواند Person در Crowd، Molecule در Chemical Simulation یا Piece of Cloth در Flag Simulation باشد. Particle System Location و Velocity Center of Mass را میدهد و Graphical Object مناسب در آن Position قرار میگیرد.
Set نیروهای ({f_i}) رفتار System را تعیین میکند. Forceها به State و Time وابستهاند و میتوانند از Spring Physics، Constraintهای دلخواه یا External Forceهایی مانند Gravity ناشی شوند. با طراحی Force مناسب Behavior مطلوب ایجاد میشود.
Dynamic State System با Numerical Method و Time Stepping Differential Equationها محاسبه میشود. در هر Time Step، ابتدا User-Defined Function Forceهای وارد بر n Particle را محاسبه میکند؛ سپس ODE Solver State را Update میکند و در پایان Position جدید و Attributeها برای Render Graphical Objectهای متناظر استفاده میشوند:
float time, delta; float state[6n], force[3n];
state=get_initial_state();
for(time=t0; time<time_final; time+=delta)
{
/* compute forces */
force=force_function(state, time);
/* apply standard differential equation solver */
state=ode(force, state, time, delta);
/* display result */
render(state, time);
}
جزء اصلی Application-Specific، تابع محاسبهٔ Force هر Particle است.
۹٫۳٫۱ Particleهای مستقل
اگر Force وارد بر Particle i از سایر Particleها مستقل باشد:
f_i=f_i(p_i,v_i).
سادهترین مثال Gravity ثابت است:
\frac{f_i}{m_i}=g,
و اگر جهت پایین محور y باشد:
g=\begin{bmatrix}0\\-g\\0\end{bmatrix}.
هر Particle مسیر Parabolic طی میکند. افزودن Force متناسب با Velocity، Friction/Drag میسازد. اگر Attributeهایی مانند Color با Time تغییر کنند و هر Particle Lifetime تصادفی داشته باشد، میتوان Firework شبیهسازی کرد.
External Forceها میتوانند مستقل روی هر Particle اعمال شوند. با Random Drift و Renderکردن هر Particle بهصورت Object بزرگ، میتوان Cloud یا Flowهای ساده ساخت.
۹٫۳٫۲ Spring Forceها
برای n Particle مستقل، Force Calculation مرتبهٔ (O(n)) دارد. در حالت عمومی که هر Particle با همهٔ Particleهای دیگر Pairwise Interaction دارد، هزینه (O(n^2)) میشود. برای System بزرگ معمولاً Interaction را به Neighborهای نزدیک محدود میکنیم.
برای Surface متغیر مانند Curtain یا Flag، Location هر Particle Vertex یک Rectangular Mesh است.
شکل ۹٫۱ — Mesh از Particleها.
Shape Mesh با External Forceهایی مثل Gravity/Wind و Internal Forceهای نگهدارندهٔ Surface تغییر میکند. برای Particle (p_{ij})، کافی است Interaction با چهار Neighbor (p_{i+1,j})، (p_{i-1,j})، (p_{i,j+1})، (p_{i,j-1}) محاسبه شود؛ بنابراین هزینه همچنان (O(n)) است.
دو Particle مجاور p و q را با Spring متصل کنید. اگر (d=p-q)، Spring Rest Length برابر s و Spring Constant برابر (k_s) باشد، Hooke’s Law:
f=-k_s(|d|-s)\frac{d}{|d|}.
شکل ۹٫۲ — دو Particle متصل با Spring.
هرچه Spring بیشتر Stretch شود، Restoring Force بزرگتر است؛ اگر Compress شود نیز Force آن را به Rest Length بازمیگرداند.
Hooke’s Law ساده Damping ندارد و Mass-Spring System پس از Perturbation برای همیشه Oscillate میکند. برای افزودن Drag/Damping، جملهای وابسته به Relative Velocity در جهت Spring Force اضافه میشود. Fraction مؤثر Velocity Projection آن روی Vector بین دو Particle است.
شکل ۹٫۳ — محاسبهٔ Spring Damping Force.
با (\dot d=\dot p-\dot q):
f=-\left[k_s(|d|-s)+k_d\frac{\dot d\cdot d}{|d|}\right]\frac{d}{|d|},
که (k_d) Damping Constant است. Mass-Spring System دارای Damping، در نبود External Force در نهایت به Rest میرسد.
Mesh Particleای که هر Interior Particle با چهار Neighbor Spring دارد و تحت Wind است میتواند Flag/Curtain را شبیهسازی کند. پس از تعیین Positionها در هر Time Step، Mesh با روشهایی مانند Texture Mapping Render میشود تا Detail ظاهری Surface ایجاد گردد.
۹٫۳٫۳ Attractive و Repulsive Forceها
Spring Force گروه Particle را کنار هم نگه میدارد؛ Repulsive Force Particleها را از هم دور و Attractive Force آنها را نزدیک میکند. Repulsion برای Distribution Particle روی Surface یا جلوگیری از برخورد Objectها و Attraction برای Solar System یا Satellite Motion قابل استفاده است. Equationهای Attraction و Repulsion اساساً فقط در Sign تفاوت دارند و یک Physical Model میتواند هر دو را همزمان داشته باشد.
برای دو Particle در p و q، Repulsive Force در جهت (d=p-q) و متناسب با عکس فاصله است. یک Inverse-Square نمونه:
f=-k_r\frac{d}{|d|^3}.
با تغییر Sign و انتخاب Constant متناسب با Massها، همین فرم Gravitational Attraction را میدهد.
اگر هر Particle با همه تعامل کند، Attraction/Repulsion هزینهٔ (O(n^2)) دارد. برخلاف Spring Mesh، Particleها Topological Neighbor ثابت ندارند. یک Strategy تقسیم Space به Cellهای سهبعدی است؛ هر Cell میتواند چند Particle یا هیچ Particle داشته باشد.
شکل ۹٫۴ — تقسیم Space به Cellها.
اگر Force با Distance سریع کاهش یابد، Cell Size را طوری انتخاب میکنیم که اثر Particleهای خارج Cell جاری و Cellهای Adjacent ناچیز باشد. در این صورت Force Calculation به حدود (O(n)) کاهش مییابد. البته Partitioning هزینه دارد و Particleها بین Cellها حرکت میکنند؛ پس پس از هر Time Step باید Membership بهروزرسانی شود.
راه دیگر جایگزینکردن Particle–Particle Interaction با Force Field است. مثلاً برای Gravity روی Earth Surface معمولاً از Gravitational Field استفاده میکنیم، نه Pairwise Force بین Point Mass جسم و Mass مرکز Earth. در Particle System میتوان Field تقریبی را روی Grid محاسبه کرد و Force هر Particle را از نزدیکترین Grid Pointها گرفت؛ سپس پس از State Update، Field را نیز Update کرد. این Strategyها اغلب Complexity را از (O(n^2)) به حدود (O(n\log n)) کاهش میدهند.
۹٫۴ حل Particle Systemها
برای n Particle و Forceهای ساده، کل System با 6n ODE از فرم
\dot u=g(u,t)
توصیف میشود که u آرایهٔ Position/Velocityها و g شامل Internal/External Forceهاست.
برای دو Particle a و b متصل با Spring بدون Damping، State میتواند چنین باشد:
u^T=[a_x,a_y,a_z,\dot a_x,\dot a_y,\dot a_z,b_x,b_y,b_z,\dot b_x,\dot b_y,\dot b_z].
با دانستن External Force و State در زمان t میتوان g را Evaluate کرد؛ مؤلفههای Position مشتقشان Velocity است و مؤلفههای Velocity از Spring Force میآیند.
Numerical ODE Solverها با Evaluateکردن g، State آینده را Approximate میکنند. خانوادهای از Solverها از Taylor’s Theorem حاصل میشود. سادهترین روش Euler Method است.
Equation
\dot u=g(u,t)
را روی Time Interval کوچک h Integrate میکنیم:
u(t+h)-u(t)=\int_t^{t+h}g(u,\tau)d\tau.
اگر h کوچک باشد، g در Interval با مقدار آن در t تقریب زده میشود:
u(t+h)\approx u(t)+h g(u(t),t).
یعنی Derivative در زمان t برای Step به State آینده استفاده میشود. این تقریب با دو Term اول Taylor Expansion منطبق است:
u(t+h)=u(t)+h\dot u(t)+O(h^2),
پس Local Error متناسب با (h^2) است.
شکل ۹٫۵ — تقریب Solution یک Differential Equation با Euler Method.
Euler Method بسیار ساده است: Forceها را در زمان t محاسبه، g را Evaluate، در h ضرب و به State جاری اضافه میکنیم. همین Step برای t+2h، t+3h و غیره تکرار میشود. هر Step فقط یک Force Evaluation لازم دارد.
دو مسئلهٔ اصلی Euler Method، Accuracy و Stability هستند و هر دو به Step Size وابستهاند. خطای Per-Step مرتبهٔ (O(h^2)) دارد؛ برای Accuracy بیشتر باید h کوچکتر شود و Computational Cost بالا رود.
Stability مشکل مهمتری است. Error هر Step از Approximation Taylor و Numerical Error محاسبات میآید. این Errorها ممکن است در Stepهای بعدی خنثی شوند یا Accumulate کنند تا Solution واقعی را بپوشانند؛ حالت دوم Numerical Instability است. برای Forceهای استاندارد، Step Size کافی کوچک Stability را تضمین میکند، اما ممکن است آنقدر کوچک لازم باشد که Simulation عملاً کند شود.
این مشکل در Spring-Mass System شدید است؛ Spring Constant، Stiffness System را تعیین میکند و Equationهای حاصل ممکن است Stiff ODE باشند.
دو Strategy وجود دارد: استفاده از Solverهای ویژهٔ Stiff Equation، یا انتخاب Methodهای مشابه Euler با Accuracy بالاتر در هر Step. روش دوم را بررسی میکنیم.
از
u(t+h)=u(t)+\int_t^{t+h}g(u,\tau)d\tau
شروع میکنیم. این بار Integral را با Average دو Endpoint تقریب میزنیم:
\int_t^{t+h}g(u,\tau)d\tau\approx\frac{h}{2}[g(u(t),t)+g(u(t+h),t+h)].
چون (g(u(t+h),t+h)) هنوز معلوم نیست، با Euler Approximation محاسبه میشود:
g(u(t+h),t+h)\approx g(u(t)+hg(u(t),t),t+h).
این روش Improved Euler یا Second-Order Runge–Kutta است. برای هر Step دو Evaluation از g لازم دارد، اما Error مرتبهٔ (O(h^3)) است و معمولاً Step Size بزرگتری با Stability بهتر ممکن میشود.
خانوادهٔ Runge–Kutta با Formulaهای دقیقتر ادامه مییابد. روش مشهور Fourth-Order چهار Function Evaluation در هر Step دارد و Error بسیار کوچکتری ایجاد میکند. Solverهای عملی همچنین Step Size را Adaptive تنظیم میکنند تا Stability و Accuracy حفظ شود.
۹٫۵ Constraintها
تنها حل Differential Equation برای Particleها برای Behaviorهایی مثل Collision کافی نیست. اگر Solid Object را Collection Particle کامل فیزیکی بدانیم، برخورد با Wall به System بسیار پیچیدهای منجر میشود. بهتر است Conditionهایی مانند «دو Solid نمیتوانند در هم نفوذ کنند» را بهعنوان Constraint جدا از Lawهای Particle تعریف کنیم.
دو نوع Constraint داریم:
- Hard Constraint باید دقیقاً رعایت شود؛ Ball باید از Wall Bounce کند و نباید از آن عبور کند یا بیدلیل پیش از تماس منحرف شود.
- Soft Constraint فقط باید تقریباً رعایت شود؛ مثلاً فاصلهٔ دو Particle در Mesh نزدیک مقدار مشخص باقی بماند.
۹٫۵٫۱ Collisionها
Hard Constraintها عموماً دشوارند، اما Collision برای Ideal Point Particle قابل مدیریت است. مسئله دو بخش دارد: Detection و Reaction.
فرض کنید Particleها یکدیگر را Repel میکنند؛ بنابراین فقط Collision Particle با Geometric Objectهای دیگر بررسی میشود. اگر n Particle و m Polygon داشته باشیم، در هر Time Step باید بررسی شود آیا Particle از Polygon عبور کرده است.
شکل ۹٫۶ — Particle نفوذکرده در Polygon.
Collision را میتوان با قرار دادن Position Particle در Plane Equation Polygon تشخیص داد. اگر ODE Step کوچک باشد، Velocity بین Stepها تقریباً ثابت است و با Linear Interpolation میتوان Time دقیق برخورد را پیدا کرد.
رفتار پس از Collision مشابه Reflection نور است. برای برخوردی که Speed حفظ میشود، Direction در جهت Perfect Reflection تغییر میکند. با Normal در Collision Point (P_c) و Previous Position (P_0):
r=2[(P_0-P_c)\cdot n]n-(P_0-P_c).
Particle در امتداد این Reflected Direction به اندازهای قرار میگیرد که اگر Collision Detection نبود به داخل Polygon نفوذ میکرد.
Tangential Component Velocity بدون تغییر میماند و Normal Component Sign عوض میکند. اگر برخورد Energy از دست بدهد، Coefficient of Restitution کسری از Normal Velocity باقیمانده پس از Collision را تعیین میکند.
شکل ۹٫۷ — Reflection Particle.
شکل ۹٫۸ — Position پس از Collision.
در Elastic/Partially Elastic Collision، Reflection Direction مانند قبل محاسبه ولی Normal Velocity با Coefficient of Restitution Scale میشود.
بخش پرهزینه Collision معمولاً Detection است. در Gameها Approximate Detection کافی است و Complex Object میتواند با Bounding Volume ساده جایگزین شود.
Point Particleها محاسبات برخورد Objectهای Finite Size را بسیار ساده میکنند. Collision بین Objectهای Extended به Clipping Arbitrary Objectها شبیه است: Conceptually ساده ولی Implementation پرهزینه و پیچیده. Finite Object همچنین Rotational/Inertial Degree of Freedom اضافه میکند و Dimension Equation System بیشتر میشود. در Computer Graphics غالباً Point Particle Approximation کافی است و Graphical Object مناسب در Position آن Render میشود.
شکل ۹٫۹ — Contact Force.
Hard Constraint مهم دیگر Contact Force است. Particleای را در نظر بگیرید که Force آن را روی Surface میفشارد و میراند. Particle نه میتواند Surface را Penetrate کند و نه باید Bounce شود. تنها Tangential Component Applied Force، یعنی مؤلفه در امتداد Surface، باعث Motion میشود و Friction نیز در همین جهت قابل اعمال است.
Collision Detection بین خود Particleها نیز اغلب (O(n^2)) است. مثلاً در Pool یا Molecule Simulation، هر Pair ممکن است Collide کند. Brute Force تمام Pairها را در هر Step بررسی میکند؛ Bounding-Box Method و Hardware Collision Support روشهای سریعترند.
۹٫۵٫۲ Soft Constraintها
بیشتر Hard Constraintها اعمال ریاضی دشواری دارند. Constraintهایی مانند Maximum Velocity یا Constant Total Energy ممکن است دیگر به ODE ساده منجر نشوند.
در بسیاری از کاربردها Soft Constraint کافی است. اگر Position Particle یعنی p باید نزدیک (p_0) بماند، Penalty Function زیر تعریف میشود:
|p-p_0|^2.
هرچه مقدار کوچکتر باشد Constraint بهتر رعایت شده است. چنین تابعی نمونهای از Energy Function است که مقدار نوعی Energy ذخیرهشده در System را بیان میکند. در Physics، Potential/Kinetic Energy نمونهاند. Physical Lawها را میتوان هم با Differential Equation و هم با Minimization Energy Expression نوشت. مزیت فرم Energy این است که Constraint/Desired Behavior را مستقیم بهصورت Potential یا Energy Function بیان میکند؛ تبدیل آن به Force Law فرایندی استاندارد است.
۹٫۶ یک Particle System ساده
یک System ساده میسازیم که بعداً قابل گسترش است. Particleها Newtonian هستند و State با Position/Velocity توصیف میشود؛ هر Particle Color Index و Mass نیز دارد:
typedef point4 vec4;
typedef struct particle
{
int color;
point4 position;
vec4 velocity;
float mass;
} particle;
Position و Velocity با Homogeneous Coordinate چهاربعدی ذخیره میشوند. System آرایهای از Particleهاست:
particle particles[MAX_NUM_PARTICLES];
برای Initialization، Particleها را با Location تصادفی در Cube مرکز مبدأ با Side Length=2 و Velocity تصادفی میسازیم:
int num_particles;
for(int i=0; i<num_particles; i++)
{
particles[i].mass = 1.0;
particles[i].color = i%NUM_COLORS;
for(int 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;
}
particles[i].position[3] = 1.0;
particles[i].velocity[3] = 0.0;
}
۹٫۶٫۱ نمایش Particleها
با دانستن Position میتوان هر Primitive دلخواهی Render کرد. سادهترین حالت یک Point برای هر Particle است.
void display(void)
{
glClear(GL_COLOR_BUFFER_BIT);
for(i=0; i<num_particles; i++)
{
point_colors[i+24] = colors[particles[i].color];
points[i+24] = particles[i].position;
}
glBindBuffer(GL_ARRAY_BUFFER, buffers[0]);
glBufferData(GL_ARRAY_BUFFER, sizeof(points), +sizeof(colors)NULL,
GL_DYNAMIC_DRAW);
glBufferSubData(GL_ARRAY_BUFFER, 0, sizeofpoints,points);
glBufferSubData(GL_ARRAY_BUFFER, sizeof(points), sizeof(colors),colors);
glDrawArrays(GL_POINTS, 24, num_particles);
glutSwapBuffers();
}
Color Palette:
typedef color4 vec4;
color4 colors[8] = {color4(0.0,0.0,0.0, 1.0), color4(1.0,0.0,0.0, 1.0),
color4(1.0,1.0,0.0, 1.0), color4(0.0,1.0,0.0, 1.0),
color4(0.0,0.0,1.0, 1.0), color4(1.0,0.0,1.0, 1.0),
color4(0.0,1.0,1.0, 1.0), color4(1.0,1.0,1.0, 1.0)};
۹٫۶٫۲ Updateکردن Position Particleها
Idle Callback با Elapsed Time و Euler Integration Position/Velocity را Update میکند:
float last_time, present_time;
void idle(void)
{
int i, j;
float dt;
present_time = glutGet(GLUT_ELAPSED_TIME); /* in milliseconds */
dt = 0.001*(present_time - last_time); /* in seconds */
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);
}
last_time = present_time;
glutPostRedisplay();
}
Position با Velocity و Velocity با Force Update میشود. Code فرض میکند dt آنقدر کوچک است که Force را هنگام Update هر Particle بتوان محاسبه کرد. Robustتر آن است که ابتدا Force همهٔ Particleها محاسبه و در Array ذخیره و سپس Stateها Update شوند.
تابع collision Particleها را داخل Box نگه میدارد و میتواند بعداً برای Particle–Particle Collision نیز گسترش یابد.
۹٫۶٫۳ Collisionها
پس از Increment Position، بررسی میکنیم آیا Particle از یکی از Sideهای Axis-Aligned Box عبور کرده است. Bounce بهصورت Reflection است؛ بنابراین Sign مؤلفهٔ Velocity در Normal Direction عوض میشود. اگر Coefficient of Restitution کمتر از ۱ باشد، Speed بعد از برخورد کاهش مییابد.
float coef; /* coefficient of restitution */
void collision(int n)
{
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].velocity[i] = -coef*particles[n].velocity[i];
particles[n].position[i] = -1.0-coef*
(particles[n].position[i]+1.0);
}
}
}
۹٫۶٫۴ Forceها
اگر Force صفر باشد، Particleها با مسیر Linear در Box Bounce میکنند. اگر coef<1 باشد، Collisionها بهتدریج Energy را کم میکنند. سادهترین External Force، Gravity است:
bool gravity = TRUE;
float forces(int i, int j)
{
if(!gravity) return(0.0);
else if(j==1) return(-1.0);
else return(0.0);
}
Attractive/Repulsive Force را نیز میتوان با محاسبهٔ Distance همهٔ Pairها و Inverse-Square Term اضافه کرد.
۹٫۶٫۵ Flocking
کاربرد جذاب Particle System، تولید Behavior ظاهراً پیچیده از Ruleهای سادهٔ Interaction است. نمونهٔ کلاسیک Flocking Bird است: چگونه گروه بزرگی از Birdها بدون دانستن Position همهٔ دیگران Flock را حفظ میکنند؟
یک Rule ساده، Steering هر Particle به سمت Center of System است. در هر Update، Average Position یا Center of Mass محاسبه میشود:
float cm[3];
for (k=0; k<3; k++)
{
cm[k]=0;
for(i=0;i<num_particles;i++) cm[k]+=particles[i].position[k];
cm[k]/=num_particles;
}
سپس Velocity Direction جدید میتواند بین Velocity فعلی و Vector از Position Particle به Average Position قرار گیرد.
شکل ۹٫۱۰ — تغییر جهت Particle به سمت Center of Mass.
این Rule بهتنهایی Cohesion ایجاد میکند و با Ruleهای دیگری مانند Separation از Neighborهای نزدیک و Alignment با Velocity همسایهها میتوان Flocking واقعگرایانهتری ساخت.
۹٫۷ Language-Based Modelها
Graphهایی مانند Tree و DAG تنها یک روش نمایش Hierarchical Relationship هستند. Language-Based Model راه دیگری است و به Procedural Methodهایی برای Objectهایی مانند Plant و Terrain منجر میشود.
در طبیعت دو Tree از یک Species دقیقاً یکسان نیستند، اما Species قابل تشخیص است. Algorithm میتواند در هر اجرا Realization متفاوتی بسازد ولی Ruleهای ساختاری ثابت داشته باشد. Tree Data Structure و Grammar برای تولید Objectهای Plant-Like مناسباند.
در Computer Science، Tree برای Parseکردن Sentenceهای Computer/Natural Language به Constituentها استفاده میشود. در Compiler، Parsing Structure Statement را تعیین میکند؛ در Natural Language نیز Grammar Correctness بررسی میشود. Parse Tree، Syntax را نشان میدهد و Interpretation Symbolها Semantics را میدهد.
میان Ruleهای یک Language و Treeهای Syntax آن رابطهٔ مستقیم وجود دارد. این ایده را به Hierarchical Object گرافیکی تعمیم میدهیم. چنین Systemهایی Tree Grammar نام دارند. Grammar از Symbolها و Production Ruleهایی تشکیل میشود که یک Symbol را با یک یا چند Symbol جایگزین میکنند؛ مثلاً:
A\rightarrow BC,
B\rightarrow ABA.
با مجموعه Productionها میتوان تعداد نامتناهی String تولید کرد. اگر برای یک Symbol چند Rule ممکن باشد و Selection تصادفی انجام شود، هر اجرای Program میتواند String متفاوتی بسازد ولی همگی از Grammar مشترک پیروی میکنند.