Category Archives: Math

Designing a Function

My Universal Periodic Function

I searched for a function with a small parameter set which can:

Create high frequent basic tones
Be used for fading of different frequencies
Be used as fade function for the volume

I started with following ideas: A function for a sound must be periodic. I choose as the domain for one period and a co-domain of because then we have a good control later when using this function. To get something periodic in the interval we could use fmod or just the fractional part. As long as we define a function in the given interval we do not need to think about periodicity.
Furthermore I would like to be able to mix any standard periodic function (Sinus, Triangle, Square, Sawtooth) by setting parameters. I designed 3 parameters to achieve that:

Shape: Just interpolate between Sinus and Triangle function. This can be seen as smoothness parameter too. The implementation is as simple as the idea. The triangle function is designed from three lines with slopes 4, -4 and 4 again.

Stretch: Add some space at the vertices of the base functions. This can be used to create a Rectangular function or it is useful for volume and frequency fading too. Just take the first half and you have a function which fades in and out and keeps one level in between.

Shift: Move the vertices left and right (point symmetric). Values near -1 or 1 create a Sawtooth function. Again using only the first half this can be used to control fading.

Moreover Stretch and Shift can be used to design Attack, Sustain and Release of a note. This is not the full ADSR model, but if I can use the same function on many levels it is a good compromise.

Implementation

I started with the implementation of the shape factor. Here I had no better idea than a simple interpolation. The Triangle wave consists of three linear functions: . To combine them one could use branches for and , but I expect the usage of min/max to be faster. This time there isn't any parameter which disturbs the ordering of the functions as in the example above.

float upf(float _x, float _shape)
{
	float sinX = sin( _x * PIx2 );
	float triangleX = 4.0f * max(min(_x, 0.5f - _x), _x - 1.0f);

	return lerp(sinX, triangleX, _shape);
}

float upf(float _x, float _shape)

{

float sinX = sin( _x * PIx2 );

float triangleX = 4.0f * max(min(_x, 0.5f - _x), _x - 1.0f);

return lerp(sinX, triangleX, _shape);

}

Afterwards I added the stretch factor. Therefore we must solve the problem: How can we add space at the points 0.25 and 0.75?
Easier is to think: How must x look like that sin(x) will have these plateaus?

So if we have a function as on the picture we are ready. Applying it to x before calling upf(x) adds the plateaus. Moreover we don't need to bother about the shape factor. Its functionality is orthogonal so we can change the parameters independently.

This trick to remap the input is like changing the contrast in a picture. All we need is a monotonous function and we can change the out coming function while staying inside the given range.

In the implementation I just focused on one single step in , copied that and added 0.5 to the right side.

float stretch(float _x, float _stretch)
{
	// Use only one step function and copy it.
	bool secondHalf = (_x >= 0.5f);
	// The slope if the lines between the constant sections goes from
	// 1 (_stretch = 0) to infinity (rectangular function _stretch = 1).
	if( _stretch == 1 ) return secondHalf ? 0.75f : 0.25f;
	float slope = 1.0f / (1.0f - _stretch);
	_x -= secondHalf ? 0.5f : 0.0f;
	_x *= slope;
	_x = max(min(0.25f, _x), _x - 0.5f * slope * _stretch);
	return secondHalf ? (_x + 0.5f) : _x;
}

float stretch(float _x, float _stretch)

{

// Use only one step function and copy it.

bool secondHalf = (_x >= 0.5f);

// The slope if the lines between the constant sections goes from

// 1 (_stretch = 0) to infinity (rectangular function _stretch = 1).

if( _stretch == 1 ) return secondHalf ? 0.75f : 0.25f;

float slope = 1.0f / (1.0f - _stretch);

_x -= secondHalf ? 0.5f : 0.0f;

_x *= slope;

_x = max(min(0.25f, _x), _x - 0.5f * slope * _stretch);

return secondHalf ? (_x + 0.5f) : _x;

}

Last of all we will add the shift parameter the same way as the stretch parameter. Again a picture can explain that best. Essentially we are using the example from the introduction but we choose the point . For the right side the same slopes can be used again so three lines (two with the same scope) are created from the one point.

Holding is important because we want the shift to move the vertices and no arbitrary points. At the point where the remapping returns 0.25 the vertices are created later which is where we want the change in frequency to happen. I also tested a smoother (exponential) step function but it was less controllable.

float shift(float _x, float _shift)
{
	// Compute the point where the lines should intersect:
	float px = _shift * 0.25f + 0.25f;
	float py = 0.25f;
	// Calculate m*x+n with one of the three lines.
	if( _x < px ) return (py / px) * _x;
	if( _x <= (1.0f-px) ) {
		float m = py / (0.5-px);
		return m * _x + 0.5f - 0.5f * m;
	}
	return (py / px) * _x + 1.0f - (py / px);
}

float shift(float _x, float _shift)

{

// Compute the point where the lines should intersect:

float px = _shift * 0.25f + 0.25f;

float py = 0.25f;

// Calculate m*x+n with one of the three lines.

if( _x < px ) return (py / px) * _x;

if( _x <= (1.0f-px) ) {

float m = py / (0.5-px);

return m * _x + 0.5f - 0.5f * m;

}

return (py / px) * _x + 1.0f - (py / px);

}

This time I consider branching as faster. It is also important to guarantee stability. For parameters -1 and 1 px gets 0. For both cases the branching will end up in the middle part where everything works fine. Otherwise we could get a division by zero.

Summary

Taking all together we have a really customizable function.

float upf(float _x, float _shape, float _stretch, float _shift)
{
	// Make it periodic
	_x -= floor(_x);

	_x = shift(_x, _shift);
	_x = stretch(_x, _stretch);
	return upf(_x, _shape);
}

float upf(float _x, float _shape, float _stretch, float _shift)

{

// Make it periodic

_x -= floor(_x);

_x = shift(_x, _shift);

_x = stretch(_x, _stretch);

return upf(_x, _shape);

}

Except the function shown here I earlier created a light falloff function without a singularity and a determined radius... I could get used to build my own functions. Finally I will give you a list of things I learned:

Use a tool which can plot functions.
Always draw your idea of a function on a paper and than try to find an approximation.
You should know graphs of functions as: sinus, tangents, exp, gauss, ln, polynomials, ...
Linear functions are your friend for parametrization: you will exactly know what they will do.
Many things can be achieved with a polynomial: If you have enough criteria as fixed points and derivatives you can just solve some equations to find the proper factors for a fitting polynomial

Collision Detection Basics

The basis for all collision detections is analytical geometry. Math can answer the question where two primitives intersect or give the distance between two objects. This post will only cover such basic functions. So it is a collection of primitive - primitive relation functions. There are two functions given. The first only returns collision or not. The second variant returns a resolvement vector. This is a translation vector which have to be applied to object 1 to move the two objects out of each other.

3D

Object	Properties
Sphere	center , radius
Line	start and end , implicit direction
Triangle	The 3 vertices in counter clock wise order , implicit normal

Sphere - Sphere

For a detection the distance has to be less or equal to the sum of the radi.

For resolvement just take the connection between the midpoints and the intersection length.

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2 )
{
	float fLen = lensq( _S1.vCenter - _S2.vCenter );
	float fr   = _S1.fRadius + _S2.fRadius;
	return fLen <= fr*fr;
}

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2, Vec3& _vResolve )
{
	_vResolve = _S1.vCenter - _S2.vCenter;
	float fLen = len( _vResolve );
	if( fLen > _S1.fRadius + _S2.fRadius ) return false;

	fLen = (fLen - (_S1.fRadius + _S2.fRadius)) / fLen;
	_vResolve *= fLen;
	return true;
}

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2 )

{

float fLen = lensq( _S1.vCenter - _S2.vCenter );

float fr = _S1.fRadius + _S2.fRadius;

return fLen <= fr*fr;

}

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2, Vec3& _vResolve )

{

_vResolve = _S1.vCenter - _S2.vCenter;

float fLen = len( _vResolve );

if( fLen > _S1.fRadius + _S2.fRadius ) return false;

fLen = (fLen - (_S1.fRadius + _S2.fRadius)) / fLen;

_vResolve *= fLen;

return true;

}

Sphere - Line

First the nearest point on a straight must be computed. If this point does not lie between the start and the end point choose the start or end point respectively.

The resolvement vector is the connection between sphere center and the nearest point on the line.

Vec3 ClosestPointOnLine( const Vec3& _vPoint,
			 const Vec3& _vLineS,
			 const Vec3& _vLineE )
{
	Vec3 d(_vLineE - _vLineS);
	Vec3 w(_vPoint - _vLineS);

	float fR = (dot(w, d) / lensq(d));

	// Nearest point to _vPoint is _vLineS
	if(fR <= 0.0f) return _vLineS;
	// Nearest point is on the line
	else if(fR < 1.0f) return _vLineS + d * fR;
	// Nearest point to _vPoint is _vLineE
	else return _vLineE;
}

bool SphereLineCollision( const Sphere& _S, const Line& _L )
{
    return lensq(_S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd )) <= _S.fRadius*_S.fRadius;
}

bool SphereLineCollision( const Sphere& _S, const Line& _L, Vec3& _vResolve )
{
    _vResolve = _S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd );
    return lensq(_vResolve) <= _S.fRadius*_S.fRadius;
}

Vec3 ClosestPointOnLine( const Vec3& _vPoint,

const Vec3& _vLineS,

const Vec3& _vLineE )

{

Vec3 d(_vLineE - _vLineS);

Vec3 w(_vPoint - _vLineS);

float fR = (dot(w, d) / lensq(d));

// Nearest point to _vPoint is _vLineS

if(fR <= 0.0f) return _vLineS;

// Nearest point is on the line

else if(fR < 1.0f) return _vLineS + d * fR;

// Nearest point to _vPoint is _vLineE

else return _vLineE;

}

bool SphereLineCollision( const Sphere& _S, const Line& _L )

{

return lensq(_S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd )) <= _S.fRadius*_S.fRadius;

}

bool SphereLineCollision( const Sphere& _S, const Line& _L, Vec3& _vResolve )

{

_vResolve = _S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd );

return lensq(_vResolve) <= _S.fRadius*_S.fRadius;

}

Sphere - Triangle

The usual way to do this is to project the sphere center to the triangle's plane. Afterwards the barycentric coordinates of the point would be calculated to test if it is inside. If not we still have to test whether the circle from the plane-sphere cut intersects with a triangle or not. Therefore it is sufficient to test the 3 line-sphere cuts because the center is definitely outside. I changed the middle part to hopefully increase the speed. Instead of calculating the barycentric coordinates I compute the closest points on all three sides which I would need in the last step non the less. Then the following condition must be true if the point is inside: the opposite vertex to a side (and therefore a point on that side) must lie on two different "sides" of the projected center. So the dot product of the vectors from the center to a closest point on a triangle-side and to the related triangle-vertex has to be at least 0.

There was one problem when using a full triangle collision in the game Pathfinder. Imagine a box made of triangles. Then the sphere is placed on top near to an edge. The simulation will first push the sphere down. Afterwards the collision detection would report two triangles. The one on the top and one of a side where the sphere collides with a back face. This has the effect that the sphere is pushed away from the edge to the box center on the upper side. To avoid that I use the condition if( fDist < 0.0f || fDist > _S.fRadius ) in lines 10 and 46 instead of if( abs(fDist) > _S.fRadius ) .

bool SphereTriangleCollision( const Sphere& _S,
			const Triangle& _T )
{
	Vec3 A = _T.v1-_T.v0;
	Vec3 B = _T.v2-_T.v1;
	Vec3 C = _T.v2-_T.v0;

	// Distance sphere plane - do not collide with back faces
	float fDist = dot( _T.n, _S.vCenter-_T.v0 );
	if( abs(fDist) > _S.fRadius )
		return false;

	// Circle point one the plane
	Vec3 P = _S.vCenter - _T.n * fDist;

	// Closest point on all edges
	Vec3 P_v0 = P-_T.v0;
	Vec3 P_v1 = P-_T.v1;
	Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );
	Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );
	Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

	// The vertex on the opposite side of the edge cannot lie in the same
	// direction as the nearest point if P lies inside the triangle.
	bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;
	bInside &= dot( CoE2-P, P_v1 ) > 0.0f;	// Inverse sign because of use from P-v1
	bInside &= dot( CoE3-P, P_v0 ) > 0.0f;	// Inverse sign because of use from P-v0
	if( bInside ) return true;

	// Search for a collision on a edge or vertex
	if( lensq(CoE1-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;
	if( lensq(CoE2-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;
	return ( lensq(CoE3-_S.vCenter) < _S.fRadius * _S.fRadius );
}

bool SphereTriangleCollision( const Sphere& _S,
			const Triangle& _T,
			Vec3& _vResolve )
{
	Vec3 A = _T.v1-_T.v0;
	Vec3 B = _T.v2-_T.v1;
	Vec3 C = _T.v2-_T.v0;

 	// Distance sphere plane
	float fDist = dot( _T.n, _S.vCenter-_T.v0 );
	if( abs(fDist) > _S.fRadius )
		return false;

	// Circle point one the plane
	Vec3 P = _S.vCenter - _T.n * fDist;

	// Closest point on all edges
	Vec3 P_v0 = P-_T.v0;
	Vec3 P_v1 = P-_T.v1;
	Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );
	Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );
	Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

	// The vertex on the opposite side of the edge cannot lie in the same
	// direction as the nearest point if P lies inside the triangle.
	bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;
	bInside &= dot( CoE2-P, P_v1 ) > 0.0f;	// Inverse sign because of use from P-v1
	bInside &= dot( CoE3-P, P_v0 ) > 0.0f;	// Inverse sign because of use from P-v0
	if( bInside )
	{
		// COLLISION inside the triangle
		_vResolve = _T.n * max( 0.0f, _S.fRadius - abs(fDist) ) * sgn(fDist);
		return true;
	}

	// Search for a collision on a edge or vertex
	Vec3 vShortest(CoE1-_S.vCenter);	float fLenShortest = lensq(vShortest);
	fDist = lensq(CoE2-_S.vCenter);	if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE2-_S.vCenter; }
	fDist = lensq(CoE3-_S.vCenter);	if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE3-_S.vCenter; }

	// Collision on edge or vertex
	if( fLenShortest < _S.fRadius * _S.fRadius )
	{
		fLenShortest = sqrt(fLenShortest);
		 _vResolve = vShortest * (( fLenShortest - _S.fRadius ) / fLenShortest);
		return true;
	}

	return false;
}

bool SphereTriangleCollision( const Sphere& _S,

const Triangle& _T )

{

Vec3 A = _T.v1-_T.v0;

Vec3 B = _T.v2-_T.v1;

Vec3 C = _T.v2-_T.v0;

// Distance sphere plane - do not collide with back faces

float fDist = dot( _T.n, _S.vCenter-_T.v0 );

if( abs(fDist) > _S.fRadius )

return false;

// Circle point one the plane

Vec3 P = _S.vCenter - _T.n * fDist;

// Closest point on all edges

Vec3 P_v0 = P-_T.v0;

Vec3 P_v1 = P-_T.v1;

Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );

Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );

Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

// The vertex on the opposite side of the edge cannot lie in the same

// direction as the nearest point if P lies inside the triangle.

bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;

bInside &= dot( CoE2-P, P_v1 ) > 0.0f; // Inverse sign because of use from P-v1

bInside &= dot( CoE3-P, P_v0 ) > 0.0f; // Inverse sign because of use from P-v0

if( bInside ) return true;

// Search for a collision on a edge or vertex

if( lensq(CoE1-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;

if( lensq(CoE2-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;

return ( lensq(CoE3-_S.vCenter) < _S.fRadius * _S.fRadius );

}

bool SphereTriangleCollision( const Sphere& _S,

const Triangle& _T,

Vec3& _vResolve )

{

Vec3 A = _T.v1-_T.v0;

Vec3 B = _T.v2-_T.v1;

Vec3 C = _T.v2-_T.v0;

// Distance sphere plane

float fDist = dot( _T.n, _S.vCenter-_T.v0 );

if( abs(fDist) > _S.fRadius )

return false;

// Circle point one the plane

Vec3 P = _S.vCenter - _T.n * fDist;

// Closest point on all edges

Vec3 P_v0 = P-_T.v0;

Vec3 P_v1 = P-_T.v1;

Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );

Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );

Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

// The vertex on the opposite side of the edge cannot lie in the same

// direction as the nearest point if P lies inside the triangle.

bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;

bInside &= dot( CoE2-P, P_v1 ) > 0.0f; // Inverse sign because of use from P-v1

bInside &= dot( CoE3-P, P_v0 ) > 0.0f; // Inverse sign because of use from P-v0

if( bInside )

{

// COLLISION inside the triangle

_vResolve = _T.n * max( 0.0f, _S.fRadius - abs(fDist) ) * sgn(fDist);

return true;

}

// Search for a collision on a edge or vertex

Vec3 vShortest(CoE1-_S.vCenter); float fLenShortest = lensq(vShortest);

fDist = lensq(CoE2-_S.vCenter); if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE2-_S.vCenter; }

fDist = lensq(CoE3-_S.vCenter); if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE3-_S.vCenter; }

// Collision on edge or vertex

if( fLenShortest < _S.fRadius * _S.fRadius )

{

fLenShortest = sqrt(fLenShortest);

_vResolve = vShortest * (( fLenShortest - _S.fRadius ) / fLenShortest);

return true;

}

return false;

}

Developerblog – Johannes Jendersie

Content Generators & Demos

Category Archives: Math

Designing a Function

My Universal Periodic Function

Implementation

Summary

Collision Detection Basics

3D

Sphere - Sphere

Sphere - Line

Sphere - Triangle