Polygon Selection Tutorial
By Alan Baylis 09/08/2003
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;
}
}
Above Content Copyright © 1998 - 2005 Alan Baylis, All Rights Reserved
