These tutorials focus mainly on OpenGL, Win32 programming and the ODE physics engine. OpenGL has moved on to great heights and I don't cover the newest features but cover all of the basic concepts you will need with working example programs.

Working with the Win32 API is a great way to get to the heart of Windows and is just as relevant today as ever before. Whereas ODE has been marginalized as hardware accelerated physics becomes more common.

Games and graphics utilities can be made quickly and easily using game engines like Unity so this and Linux development in general will be the focus of my next tutorials.

Polygon Selection Tutorial

By Alan Baylis 09/08/2003

Download for Visual Studio 7.0

Accurate polygon selection (or picking) using the mouse is necessary for most graphics applications but I felt the OpenGL method using selection mode was too cumbersome for my tastes and wouldn't be as accurate as a line plane intersection test. I may be wrong, but the method I use is intuitive and requires no redrawing of the primitives.

To explain the process I will just give a brief description of how the following function SelectPolygon works. The image above shows the view frustum as seen from the camera at C and the near and far clip planes. To find which polygon the mouse is over we first construct a ray (marked in blue) from the camera position to a point on the near clip plane. The start point is the camera position itself and the end point is defined by the mouse (x, y) coordinates and the depth of the near clip plane. Using these start and end points we can then define a line that passes through the world (marked in red), we next loop through each polygon in the scene and check for any intersections with this line and return the index of the closest polygon intersected (polygon 1 in this case.) To find the intersection with the polygons I have used a function called line_plane_collision written by Kevin Kaiser and another called CheckPointInTriangle by Kasper Fauerby, they are included at the end of this page. The line_plane_collision function will register an intersection with polygons behind the camera so we need to check whether the point of collision is within the view frustum before continuing. CheckPointInTriangle only works with triangles which is recommended but can tessellate an n-sided polygon to check whether the collision point is within any of the sections. SelectPolygon also makes use of gluUnProject to find the end point of the ray, it most likely multiplies the projection and modelview matrices together and then multiplies the windows coordinates by the inverse of the combined matrix, but I haven't looked into it closely. If you want, you can set the initial shortest distance to a shorter distance so that only the polygons within that range will be tested. The function also expects that both the vector and vertex classes have an overloaded = operator, so you may need to modify it a bit if you aren't using overloaded operators.

SelectPolygon() creates a ray from the current camera coordinates to a point equal to the distance of the near clip plane into the screen that is coincident with the mouse coordinates passed in and checks for an intersection along the line of this ray with the array ofpolygons passed in. If there is an intersection then the function returns the zero based index of the closest polygon intersected or -1 if there was no intersection. The polygons passed in must have between 3 to 29 sides, be convex, non-degenerate and have their normals set.MouseX and MouseY are relative to the top-left corner of the window.

int SelectPolygon(HWND hWnd, POLYGON* Polygons, int numPolys, int MouseX, int MouseY) { POLYGON tempPolygon; VECTOR CollisionPoint, p0, pN, a, b, c; int tempPolygonNumber; // Returned index VECTOR tempVect; GLfloat Distance; VERTEX tempVertex; VECTOR WorldPos; // Set to an initial distance further than all polygons GLfloat ShortestDistance = 10000000; bool flag = false; // Flag indicating intersection status // Temporary variables for polygon tessellation int numNewPolygons = 0; POLYGON newPolygon[30]; // Get the modelview and projection matrices double WorldPosX, WorldPosY, WorldPosZ, MousePosX, MousePosY, MousePosZ; double ModelMatrix[16]; glGetDoublev(GL_MODELVIEW_MATRIX, ModelMatrix); double ProjMatrix[16]; glGetDoublev(GL_PROJECTION_MATRIX, ProjMatrix); // Get the current viewport int Viewport[4]; glGetIntegerv(GL_VIEWPORT, Viewport); if (MouseX >= Viewport[0] && MouseX <= Viewport[2] && MouseY >= Viewport[1] && MouseY <= Viewport[3]) { // Set the end point of ray in windows coordinates MousePosX = MouseX; MousePosY = Viewport[3] - MouseY; // invert mouse Y coordinate MousePosZ = 0.5; // Near clip plane depth value // Get unprojected end point gluUnProject ( MousePosX, MousePosY, MousePosZ, ModelMatrix, ProjMatrix, Viewport, &WorldPosX, &WorldPosY, &WorldPosZ ); WorldPos.x = WorldPosX; WorldPos.y = WorldPosY; WorldPos.z = WorldPosZ; // Check for line polygon collision with all polygons for (int outerloop = 0; outerloop < numPolys; outerloop++) { // Make a copy of the polygon to work with tempPolygon.Vertex[0] = Polygons[outerloop].Vertex[0]; tempPolygon.Vertex[1] = Polygons[outerloop].Vertex[1]; tempPolygon.Vertex[2] = Polygons[outerloop].Vertex[2]; tempPolygon.numVertices = Polygons[outerloop].numVertices; // Get a point on the polygon p0 = tempPolygon.Vertex[0].coords; // Get the polygons normal pN = tempPolygon.Vertex[0].normal; // Find collision point on the plane CollisionPoint = line_plane_collision(&camera[currentCamera].Position, &WorldPos, &tempPolygon); // If the collision point is outside the frustum // (indicating a collision behind the camera) then continue // this function is defined in the general.cpp source file if (!CheckClipPlanes(camera[currentCamera], CollisionPoint)) continue; // Subdivide polygon into new polygons numNewPolygons = 0; for (int innerloop = 2; innerloop < tempPolygon.numVertices; innerloop++) { numNewPolygons++; newPolygon[innerloop - 2].Vertex[0] = tempPolygon.Vertex[0]; newPolygon[innerloop - 2].Vertex[1] = tempPolygon.Vertex[innerloop - 1]; newPolygon[innerloop - 2].Vertex[2] = tempPolygon.Vertex[innerloop]; } // If collision point is within the new polygons for (int innerloop = 0; innerloop < numNewPolygons; innerloop++) { a = newPolygon[innerloop].Vertex[0].coords; b = newPolygon[innerloop].Vertex[1].coords; c = newPolygon[innerloop].Vertex[2].coords; // Function is in the collision.cpp source file if (CheckPointInTriangle(CollisionPoint, a, b, c)) { // Find distance to the collision point tempVect = CollisionPoint - camera[currentCamera].Position; Distance = tempVect.GetMagnitude(); // If this intersection is closest if (Distance < ShortestDistance) { tempPolygonNumber = outerloop; ShortestDistance = Distance; flag = true; } } } } if (flag) return tempPolygonNumber; else return -1; } }