Sine Language Lesson, Part 2

In Part 1 of this post I discussed some useful applications of the sine function without really delving into the details of how it works. Specifically, we focused on the equation y = sin(x). Here is a more useful variation of the sine function as demonstrated in the Ocean Waves demo:

y = A * sin(K*distance - F*time + S)

• A = amplitude
• K = angular frequency
• F = time frequency
• S = shift

Amplitude represents the height of the wave; it typically ranges from -1 to 1 but can be set to an arbitrary value (e.g. set A = 25 for the wave to range from -25 to 25). The angular frequency represents how quickly the wave travels vertically. The time frequency represents how quickly the wave travels horizontally; note that F*time can be omitted from the sine function to view a static snapshot of the wave at a point in time but is included in the Ocean Waves demo to provide the effect of a wave in motion. Finally, the shift parameter allows us to move the wave by a horizontal offset so it starts from a new position (e.g. setting S = -π/2 would map it to the cosine function).

The Point Light demo from Part 1 sets the light source position's Z-coordinate using a simple sine function and then calculates the X- and Y-coordinates as sine functions using the computed Z value as the distance parameter. The Ocean Waves demo combines multiple sine waves to achieve the illusion of irregularity (not all waves in the ocean are the same height and hit shore at the same regular time interval). For example, to apply the effects of y = sin(x) and y = 12 * sin(3x), we can simply write y = sin(x) + (12 * sin(3x)). Observe that the two functions are added together. Watch the web preview of Combining Sine Waves to see the concept in motion.

I hope this post encourages you to investigate some potential uses of sine/cosine functions, as well as return to Part 1 if you missed the demo programs. It seems some things we learned in high school actually did turn out to be useful!

Sine Language Lesson, Part 1

I've had this idea ruminating in my mind for some time now. Math is a big part of graphics development and I'm certainly no expert, but I wanted to show off some cool things that can be done with sine waves. This part introduces the concept and shows some fun demo programs you can play with; part two will delve into the inner workings of the demos, which have been adapted from Frank Luna's Introduction to 3D Game Programming with DirectX 9.0c: A Shader Approach.

You may remember from your high school Trigonometry class (don't worry if not, it was a long time ago for me too!) those two periodic functions, sine (pronounced "sign") and cosine ("co-sign"). They're essentially the same function and you could map one to the other with a slight shift. Cosine has some unique applications of its own, such as determining light intensity based on viewing angle, but the demos below will focus primarily on sine waves.

Credit: Wikimedia Commons

Notice a few interesting properties from the graph above. One is that a sine wave repeats itself every 2π (π ≈ 3.14159) or 360 degrees along the X-axis. Another is that it oscillates between the Y values -1 and 1. We write the function y = sin(x) to indicate the Y value as a function of X; see from the graph above that Y = 0 when X is any multiple of π and Y is either 1 or -1 (the peaks and valleys) when X is an odd multiple of π/2.

Point Light Demo - Download Program!

This demo shows how sine waves can be used to animate a light source. Use the specified keys to combine waves, creating a variety of unique horizontal and vertical motion paths.

Before learning this elegant method, my approach to animating an object that sways back and forth, or moves repeatedly up and down along a pole, was to use code like this in my update loop:

    static bool moveUp = true;
    if (moveUp) 
    { if (shipPos.y < 100) shipPos.y += value; else moveUp = false; }
    else 
    { if (shipPos.y > -100) shipPos.y -= value; else moveUp = true; }

With sine waves, this code reduces simply to shipPos.y = 100 * sin(x)! Notice that I multiplied by 100 to get the desired range instead of the standard oscillation from -1 to 1.

Ocean Waves Demo - Download Program!

This demo illustrates the effects of adding sine waves and two different wave types, circular and directional. Use the specified keys to play with parameters and change the wave patterns.

As with the Point Light demo, you will need to have DirectX (from Windows Update) installed in order to run the program.

These are just a couple applications of the sine function. Because of its periodic repetition, it could have many potential uses; some fellow GCG forum members cited their implementations of a 3D carousel and a wavy spaceship flight path as additional examples.

I hope you enjoy the demo programs of this post, though I admit I still need to learn better methods of input handling. Part two will describe wave alterations, based on the Ocean Waves demo, in greater detail. Until then, feel free to let us know: What's the coolest thing you've done with sine/cosine waves?

Point-Plane Collision Detection Explained

In my previous post I presented a function for detecting collision of a point in 3D space with a plane (surface of an object). It works well enough in my SkyCop demo because all I need to check is if the tip of the primary ship intersects the surface of other ships. Here's a description of the code, broken into seven steps to help you understand this basic form of collision detection.

1)	Understand the Plane Equation: Ax + By + Cz + D = 0
	The plane equation tells us that a point (x,y,z) is on a plane having normal vector (A,B,C) and distance D from the origin when Ax + By + Cz + D = 0. If we plug in A, B, C, D, x, y, z and get any value other than zero, the point (x,y,z) is not on the plane. Also note that since the dot product of vectors (A,B,C) and (x,y,z) equals Ax + By + Cz, we can rewrite the Plane Equation as DotProduct(N, P) + D = 0 for N=(A,B,C) and P=(x,y,z).
2)	Get the collision surface's normal vector.
	As noted above, in order to detect if a point is on our collision surface (such as a wall we want to prevent the player from running through), we need to know the normal vector perpendicular to the surface. A normal vector is computed by taking the cross product of two vectors on the plane. The simplest 2D plane we can create in 3D space is a triangle with three vertices (call them vP1, vP2, and vP3) and I will focus on a triangular collision surface for simplicity. We compute the normal vector by generating a vector from vP1 to vP2 and another from vP2 to vP3 and then take the cross product of those two vectors to obtain the normal vector. Finally, the normal vector is normalized (made to have a length of 1.0) to simplify calculations. vN1 = (vP2 - vP1); vN2 = (vP3 - vP2); D3DXVec3Cross(&vNormal, &vN1, &vN2); D3DXVec3Normalize(&vNormal, &vNormal);
3)	Get plane distance using the Plane Equation.
	Using our revision of the Plane Equation, DotProduct(N, P) + D = 0, we can solve for D to get D = -DotProduct(N, P). So we compute D by plugging in the normal vector and any point on the plane; any of the triangle surface's three vertices will suffice. d = - D3DXVec3Dot(&vP1, &vNormal);
4)	Classify the start and destination points.
	Now that we've determined the collision surface's normal vector and distance from the origin (A, B, C, and D) we can use the Plane Equation for something really cool: determining if a given point lies on the plane! When we plug a point P=(x,y,z) into the left side of our revised plane equation DotProduct(N, P) + D we get a result value, p. If p > 0, the point is in front of the plane. If p < 0, the point is behind the plane. And of course we know that if p = 0 the point lies on the plane. Since we're only concerned with detecting collisions for moving objects, there must be a start position where the object moved from (pstart) and a destination position (pdest) to which the object is moved. The trick is realizing that a collision only occurs if these two positions have different locations in relation to the plane -- if they're both in front of or both behind the plane, no collision occurred and we can return from the function. p = (D3DXVec3Dot(&vNormal, &pStart) + d); if ( p > 0.0f ) pStartLoc = PlaneFront; else if ( p < 0.0f ) pStartLoc = PlaneBack; else pStartLoc = OnPlane; p = (D3DXVec3Dot(&vNormal, &pDest) + d); if( p > 0.0f ) pDestLoc = PlaneFront; else if (p < 0.0f ) pDestLoc = PlaneBack; else pDestLoc = OnPlane; if (pStartLoc == pDestLoc) return false;
5)	Get the ray.
	At this point we know that an intersection did occur! Great, but there is a small problem; we don't know where it occurred, which is equally important. The plane that was crossed is an infinitely expanding plane in 3D space, often called a hyperplane, so we need to check if the collision occurred within the bounds of our collision surface's borders. Computing the vector, called a "ray", from our object's start position (pstart) to its destination position (pdest) helps determine where the collision occurred. The vector is normalized to simplify calculations. ray = pDest - pStart; D3DXVec3Normalize(&ray, &ray);
6)	Get the intersection point.
	Vector math tells us that we can access points along a ray from pstart to pdest using the formula (pstart + ray * t). Since we know that a point along our ray from pstart to pdest definitely intersects the plane, we use the plane equation to determine the value of t below. Note that I've plugged the intersection point (pstart + ray * t) into the Plane Equation instead of a generic (x,y,z) because we know that point lies on the plane. I've also renamed pstart to "s" and the ray to "r" for brevity. A(sx + rx*t) + B(sy + ry*t) + C(sz + rz*t) + D = 0 A*sx + A*rx*t + B*sy + B*ry*t + C*sz + C*rz*t + D = 0 DotProduct(N, s) + t*DotProduct(N, r) + D = 0 t = - (DotProduct(N, s) + D) / DotProduct(N, r) We've already computed the normal vector N=(A,B,C) as well as the plane distance D and the ray so we can calcuate t. Then we plug it into our formula to get the actual intersection point on the plane. t = - (d + D3DXVec3Dot(&vNormal, &pStart)) / D3DXVec3Dot(&vNormal, &ray); intersect = pStart + (ray * t);
7)	Determine if intersection hit the collision surface!
	We're almost there! We determined the intersection point where our object collided on a hyperplane corresponding to the collision surface. So the final question is, "Does the intersection point fall within the bounds of our collision surface?" In order to answer that question we compute vectors from the intersection point to the surface vertices and measure the angles between those vectors. If we form a complete circle, we know the point lies within the bounds of our collision surface! v1 = intersect - vP1; v2 = intersect - vP2; v3 = intersect - vP3; D3DXVec3Normalize(&v1, &v1); D3DXVec3Normalize(&v2, &v2); D3DXVec3Normalize(&v3, &v3); // Angles around intersection should total 360 degrees (2 PI) thetaSum = acos(D3DXVec3Dot(&v1, &v2)) + acos(D3DXVec3Dot(&v2, &v3)) + acos(D3DXVec3Dot(&v3, &v1)); if (fabs(thetaSum - (2 * D3DX_PI)) < 0.1) return true; else return false;

There are a couple caveats to this method of collision detection. The first is that the triangle surface vertices vP1-vP3 must be specified in clockwise order so the surface normal vector is computed correctly. We also have to allow for a small margin of error in the calculation of the sum of angles due to the lack of floating-point precision. Finally, I've read that this method should only be used on convex (as opposed to concave) polygons which do not curve inward on themselves.

I know this is very low-level and there are probably simpler ways to do it (bounding boxes/spheres come to mind...), but it's kinda neat to see how the math makes it work! Please feel free to post comments/questions to let me know what you think of this tutorial. I hope it provides a clearer understanding of what's going on under-the-hood in basic point-plane collision detection.