# Tag: math

Entries for tag "math", ordered from most recent. Entry count: 62.

Warning! Some information on this page is older than 6 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

Pages: 1 2 3 4 ... 8

# SBX - Scale-Bias Transform

Wed
23
Jan 2013

A class of 2D or 3D point and vector transformations called affine transformations (that is - linear transformation plus translation) can be conveniently represented by matrix. But sometimes we don't need possibility of input x to influence output y or vice versa. For example, that's the case when we want to convert coordinates of mouse cursor from pixels, like we take it from WinAPI (where X goes right from 0 to e.g. 1280 and Y goes down from 0 to e.g. 720) to post-projective 3D space (where X goes right from -1.0 to +1.0 and Y goes up from -1.0 on the bottom to +1.0 on the top). Then every component can be transformed independently using linear transform, like this:

`Parameters are: scale.xy, bias.xy.Given input point i.xy, output point o.xy is:o.x = i.x * scale.x + bias.xo.y = i.y * scale.y + bias.y`

This seems trivial, but what if we wanted to encapsulate such transformation in a new data structure and define operations on it, like we do on matrices? Let's call it SBX - Scale-Bias Transform. I propose following structure:

`struct ScaleBiasXform{    static const ScaleBiasXform IDENTITY;    vec2 Scale;    vec2 Bias;};`

And following functions:

`void Construct(ScaleBiasXform& out,    const vec2& input1, const vec2& output1,    const vec2& input2, const vec2& output2);void Scaling(ScaleBiasXform& out, float scale);void Scaling(ScaleBiasXform& out, const vec2& scale);void Translation(ScaleBiasXform& out, const vec2& vec);void Inverse(ScaleBiasXform& out, const ScaleBiasXform& sbx);void Combine(ScaleBiasXform& out, const ScaleBiasXform& sbx1, const ScaleBiasXform& sbx2);void TransformPoint(vec2& out, const vec2& point, const ScaleBiasXform& sbx);void UntransformPoint(vec2& out, const vec2& point, const ScaleBiasXform& sbx);void TransformVector(vec2& out, const vec2& vec, const ScaleBiasXform& sbx);void UntransformVector(vec2& out, const vec2& vec, const ScaleBiasXform& sbx);`

• vec2 is obviously structure containing: float x, y;
• vec2 has some overloaded operators, including lhs*rhs and lhs/rhs, which perform per-component multiplication or division.
• common::CalcLinearFactors used in CPP file is function from my CommonLib, defined in Base.hpp.

# Particle System - How to Store Particle Age?

Wed
12
Dec 2012

Particle effects are nice because they are simple and look interesting. Besides, coding it is fun. So I code it again :) Particle systems can have state (when parameters of each particle are calculated based on previous values and time step) or stateless (when parameters are always recalculated from scratch using fixed function and current time). My current particle system has the state.

Today a question came to my mind about how to store age of a particle to delete it after some expiration time, determined by the emitter and also unique for each particle. First, let's think for a moment about the operations we need to perform on this data. We need to: 1. increment age by time step 2. check if particle expired and should be deleted.

If that was all, the solution would be simple. It would be enough to store just one number, let's call it TimeLeft. Assigned to the particle life duration at the beginning, it would be:

`Step with dt: TimeLeft = TimeLeft - dtDelete if: TimeLeft <= 0`

But what if we additionally want to determine the progress of the particle lifetime, e.g. to interpolate its color of other parameters depending on it? The progress can be expressed in seconds (or whatever time unit we use) or in percent (0..1). My first idea was to simply store two numbers, expressed in seconds: Age and MaxAge. Age would be initialized to 0 and MaxAge to particle lifetime duration. Then:

`Step with dt: Age = Age + dtDelete if: Age > MaxAgeProgress: AgePercent progress: Age / MaxAge`

Looks OK, but it involves costly division. So I came up with an idea of pre-dividing everything here by MaxAge, thus defining new parameters: AgeNorm = Age / MaxAge (which goes from 0 to 1 during particle lifetime) and AgeIncrement = 1 / MaxAge. Then it gives:

`Step with dt: AgeNorm = AgeNorm + dt * AgeIncrementDelete if: AgeNorm > 1Progress: Age / AgeIncrementPercent progress: AgeNorm`

This needs additional multiplication during time step and division when we want to determine progress in seconds. But as I consider progress in percent more useful than the absolute progress value in seconds, that's my solution of choice for now.

# DirectXMath - A First Look

Sun
15
Apr 2012

Programmers using DirectX have access to the accompanying library full of routines that support various 3D math calculations. First it was D3DX - auxilliary library tightly coupled with DirectX itself. It's still there, but some time ago Microsoft released a new library called XNA Math. I've written about it here. This library also ships with latest versions of DirectX SDK (which was last updated in Jun 2010), but it is something completely new - a more independent, small, elegant and efficient library, portable between Windows (where it can use SSE2 or old FPU) and Xbox 360.

Now Microsoft comes up with another library called DirectXMath. See the official documentation and introductory blog post for details. As a successor of XNA Math, it looks very similar. Main differences are:

• They dropped support for Xbox 360. The library is now portable between Windows (using SSE2 or FPU) and ARM (using NEON).
• It is now a C++ library, makes use of namespaces and templates, so it no longer works with C.
• It makes use of new C++11 standard (and requires compiler that supports it), including integer types from <cstdint> like uint32_t instead of types from <Windows.h> like DWORD.

Sounds great? Well, I didn't tell yet how to get it. It's not shipped with DirectX SDK. You need the SDK for Windows 8. They say that:

The library is annotated using SAL2 (rather than the older VS-style or Windows-style annotations), so requires the standalone Windows SDK for Windows 8 Consumer Preview or some additional fixups to use with Visual C++ 2010.

So probably I'm not going to switch to this new library anytime soon :P

# Ball Physics

Sat
17
Mar 2012

Checking collision between different kinds of 2D or 3D shapes is a subject I deal with for some time. It is useful in game development to determine if some object is visible or affected by light and this if it should be rendered. I have lots of function to check such collisions in the math module of CommonLib library.

But that is only the beginning if you want to make physics. Adding physical behavior to your game requires additional calculations to correct positions and apply forces to colliding bodies. I prepared a small code snippet that implements physical 2D collision between moving circle and another moving circle (calculated by CircleToCircleCollision function), static line (CircleToLineCollision function) and static axis-aligned rectangle (CircleToRectangleCollision function).

The code uses some good practices (like fixed time step) as well as bad practices (like Euler integration). It should be enough for a simple physics in game like a platformer.

# Vector Register Size - Diagram

Thu
29
Sep 2011

It may be hard to imagine and remember what is the exact number of bits, bytes, words or floats in some piece of data, like a SIMD register. So today I've made following diagram/cheatsheet:

Here you can find its "source" in OpenOffice Draw format: Vector_register_size.odg.

# DevMeeting and Demoscene Night

Sun
24
Jul 2011

Yesterday I attended two events related to my interests. First was about collision detection in JavaScript games, organized by Marek Pawłowski from devmeetings.pl. During this almost 12-hour workshop we could learn about JavaScript, as well as some theory of 2D collision detection and space partitioning techniques. Nothing new for me, but I liked formula of this workshop. We could learn some theory from slides, but most of the time we had some tasks to code on our laptops - first to implement a simple library for aspects in JavaScript and then to code Asteroids game, including precise collision detection and QuadTree. Most of the code for this game was ready - we were given a framework, as well as libraries with math and a class for QuadTree. Our task was to just to connect it together. I think it's a good way of teaching programming in practice.

Web technologies are not my main interest, but I like JavaScript. I even think  it's the most beautiful scripting language in terms of syntax. Being able to freely draw 2D (using HTML Canvas) as well as 3D graphics (using WebGL) makes it a good technology for learning and prototyping geometry or gameplay algorithms. Marek also pointed on the DevMeeting an interesting conclusion that it's very easy to port algorithms from C/C++ to JavaScript. But on the other hand, Dab reminded me today that Lua is a scripting language with very similar features, but faster and more lightweight interpreter, so it's still better choice as a scripting language embedded in high-performance software like games.

Second event was Noc z Demosceną - Demoscene Night. It took place in Fabryka Kotłów club (former No Mercy). During that night we could see some olschool, as well as newschool demos presented on a a big screen and, what is most important, meet some nice people there. Thanks Voyager for organizing this event! It was great especially because the 3-day demoscene party RiverWash, which took place here in Warsaw in last 2 years, this year is in Łódź and I can't attend it. This night was very inspiring and now I feel like developing a technology to make a demo :)

Comments | #demoscene #webdev #javascript #math #events

# Bit Tricks with Modulo

Sat
26
Feb 2011

I like to emphasize that programming is not so similar to maths as some people say. We are used to thinking about numbers in decimal numeral system and the operations that seem most natural for us are arithmetic computations like additions, multiplication and division. On the other hand, computer works with numbers stored in binary system and bitwise operations are most efficient and natural for it. Another difference is modulo operation (the remainder after division) - a function not so frequently used in math classes, but very important in programming. That's what I'd like to talk about here.

Modulo in C++ can be done using % operator, but just as division, it is quite slow. So when doing a common operation of cycling between subsequent numbers from a limited range:

`x2 = (x1 + 1) % n;`

few alternatives have been developed for some special cases, using bitwise operations.

First, when the divisor is a power of 2, we can use bitwise and (operator &) to mask only least significant bits of the addition result. But this optimization can be done automatically by the compiler (at least my Visual C++ 2010).

`// 7 = 0b111, so it masks 3 least significant bits.// Equal to (x1 + 1) % 8x2 = (x1 + 1) & 7;`

When we only cycle between two values - 0 and 1 - we can use XOR (operator ^):

`// Equal to (x1 + 1) % 2, for values 0, 1.x2 = x1 ^ 1;`

Finally, when we cycle between three values - 0, 1, 2 (like when indexing x, y, z components of a 3D vector), we can use the trick invented by Christer Ericson (at the end of the linked page). I came across it recently on Twitter and that's what inspired me to write this article.

`// Equal to (x1 + 1) % 3, for values 0, 1, 2.x2 = (1 << x1) & 3;`

# XNA Math and Access Violation

Wed
16
Feb 2011

XNA Math is a great math library bundled with DirectX SDK. I've written about it here: Introduction to XNA Math, XNA Math Cheat Sheet. Recently I've started coding some small raytracer using this library (especially XMVECTOR type) and I came across an error:

Google didn't display many results when asked about this error in connection with "XNA Math" or "XMVECTOR", but I found a topic on our Polish gamdev forum: xnamath i dziwne crashe. Directed to other web places from there, I discovered that, just as I thought, this bug comes from misaligned address of the vector. XMVECTOR on PC is an alias for SSE __m128 type, which has to be always aligned to 16-byte boundary. Compiler seems to know about this alignment requirement and respects it whenever XMVECTOR is defined on the stack, passed as function parameter or returned from a function, but not when the vector is a member of some dynamically allocated class or struct. So this won't work:

`struct Scene {    XMVECTOR dir_to_light;};Scene *scene = new Scene();scene->dir_to_light = XMVector3Normalize(    XMVectorSet(1.5f, 1.f, -2.f, 0.f)); // Crash!`

Adding special alignment declaration supported by Visual C++ - __declspec(align(16)) - doesn't help. it looks like operator new always aligns allocated objects to 8 bytes and there is no way to change this behavior other than redefining it to use your own custom memory allocator.

So I suppose the most simple and convenient way to walk around this problem is to use more "casual" types for storing vectors - the ones that do not use SSE and do not require alignment, like XMFLAOT3 (which is just struct with float x, y, z). Anyway XMVECTOR is designed to optimize computations when compiler is able to place it in the CPU registers. So my solution looks like this:

`struct Scene {    XMFLOAT3 dir_to_light;};Scene *scene = new Scene();XMVECTOR dir_to_light = XMVector3Normalize(    XMVectorSet(1.5f, 1.f, -2.f, 0.f));XMStoreFloat3(&scene->dir_to_light, dir_to_light);...XMVECTOR dir_to_light = XMLoadFloat3(&scene->dir_to_light);XMVECTOR n_dot_l = XMVectorSaturate(XMVector3Dot(normal, dir_to_light));`