Ray casting for Selection

If anyone is interested I had to pull out Foley van dam Feiner and Hughes and discover how to cast a ray into the screen from a mouse point and then use it to calculate if and where it interesects any particular objects face. You can of course use the OPENGL selection method (limited to 64 named Items) but it really is pants.

The method I implemented does the following:

1 - calculate ray and ray normal

2 - do quick sphere based interesetion test
on modelled parts COG’s

3- do a face by face analysis to determine
if the ray hits the plane of an individual triangle.

4- tranform all all face coords and hit pt into the same coordinate system, and then rotate to eliminate an axis.

5- perform a simple 2d PtInPolygon analysis
as all points can be represented in 2D integer space.

So if anyone is interested let me know and I will put hte psuedo code out there.

P.S. If you dont know what foley van dam feiner and hughes is dont worry, I have owned the book for 4 years now and I’m still not quite sure.

>>You can of course use the OPENGL selection method (limited to 64 named Items) but it really is pants.

Selection is not limited to 64 named items, but to 64 name stack entries.
Using glLoadName on the top of stack allows to use 2^32-1 different objects.

Some Additions to point 1 and 4:

Originally posted by vs:

1 - calculate ray and ray normal

  1. To give an example how to do it in OpenGL:

Give this function a 2D screen point and get back the start and end point of the 3D line.

bool Part3DPane::PickRay(Point2D pIn, Point3D &p1, Point3D &p2)
{
GLdouble o1x,o1y,o1z;
GLdouble o2x,o2y,o2z;

if (!valid_draw)
return false;

LockOpenGL();

gluUnProject(pIn.x(),drawSizeY - pIn.y(),0.0,modelMatrix,projMatrix,viewport,&o1x,&o1y,&o1z);
gluUnProject(pIn.x(),drawSizeY - pIn.y(),1.0,modelMatrix,projMatrix,viewport,&o2x,&o2y,&o2z);

p1.x(o1x);
p1.y(o1y);
p1.z(o1z);

p2.x(o2x);
p2.y(o2y);
p2.z(o2z);

UnlockOpenGL();

return true;
}

Originally posted by vs:

4- tranform all all face coords and hit pt into the same coordinate system, and then rotate to eliminate an axis.

  1. I found a much faster way instead of rotating the face vertices and the intersection vertex into 2D. As you only need to do a point in polygon test, the correct coordinates are not neccessary. That means, that the face could be stretched. So, just determine the biggest of the x,y,z values and kick it. Thats a 2D projection than, not a rotation. But it’s much faster (Foley van Dam is a standard book, but its getting older each day ;-))

Kilam.

[This message has been edited by Kilam Malik (edited 08-15-2000).]

You wrote :

That means, that the face could be stretched. So, just determine the biggest of the x,y,z values and kick it. Thats a 2D projection then, not a rotation.

Please enlighten me on what you mean by “kicking” and is a 2D projection faster than a simple rotation??

Sorry, I’m not a native english speaker. With “kick” I mean to just not use it. I try to explain with an example. Think of having a triangle with the points (4/4/0), (20/4/5), (10/15/7). Its a triangle lieing nearly in the x/y plane, but point 2 and 3 are on z=5 and 7 in your direction. Now imagine a ray intersecting this triangle in e.g. (10/10/4) (I only estimated it!). The triangle has the estimated normal (-0.2/ 0.2/ 0.8). Now you find the component of the vector which has the highest value. This is the z-value here. This value is no longer needed in the 3 triangle points and in the intersection point. So you get the 2D coordinates (4/4), (20/4), (10/15) and intersection point (10/10). So projection is just leave/kick the component with the highest normal-component. This should be much faster than a rotation (multiply each point with a matrix which you have to determine before with the plane on which the triangle lies).

Hope this is understandable.

Kilam.

Would you mind posting the full source code for this please? That would be IMMENSELY helpful!! :wink:

OK, i cutted out the interesting lines from my source code. Don’t mind about the bad code, its about 3 years old and mostly in C:

int GetDropCoord(Vector3D v)
// Get the coordinate which could be dropped:
{
double x,y,z;

x=fabs(v.x());
y=fabs(v.y());
z=fabs(v.z());
if (x>=y)
if (x>=z)
return DROPX;
if (y>=x)
if (y>=z)
return DROPY;
return DROPZ;
}

Point2D DropCoord(Point3D p,int drop)
// Drop the drop-coordinate from the 3D point and returns the resulting 2D point.
{
switch(drop)
{
case DROPX:
return Point2D(p.y(),p.z());
case DROPY:
return Point2D(p.x(),p.z());
case DROPZ:
return Point2D(p.x(),p.y());
default:
return Point2D(p.x(),p.y());
}
}

int InsideLoop(Loop *l,Vertex *v)
// l = loop of a face. v = intersection point
// of ray with loop.
{
int drop=GetDropCoord(l->face); // Get drop coord from the face normal.

Point2D x = DropCoord(v->pnt,drop); // Drop a component to project the intersection.

int n = NumberOfPointsInLoop(l);

// Now convert all 3D points in this loop to 2D points by projection:
Point2D *pnt = new Point2D[n];
HalfEdge *scan=l->hEdge;
n=0;
do
{
pnt[n] = DropCoord(scan->vertex->pnt, drop);
n++;
}
while ((scan=scan->next)!=l->hEdge);

return Math2DInsidePolygon(pnt,n,x); // Test, if x lies inside loop.
}

It’s a 3D-solid which is hit by a ray here. So you will see some variables like face and loop and halfedge and so on. Don’t mind about them, they are only used to traverse the solid and get the polygon data.

Kilam.

P.S.: How can I use spaces in my source code post? Looks awful in this unformatted state…

[This message has been edited by Kilam Malik (edited 08-17-2000).]

[This message has been edited by Kilam Malik (edited 08-17-2000).]

[This message has been edited by Kilam Malik (edited 08-17-2000).]

Click on the icon with the pen above this message to see the method in the quoted text.
… ehmm, I mean the one with the arrow.

P.S.: How can I use spaces in my source code post? Looks awful in this unformatted state…

[This message has been edited by Relic (edited 08-17-2000).]

Oh yeah, looks good :wink: Thanks.

Thanks Kilam.

Your suggestion for Point 4 does work. It is approximatley 15% faster thant rotating the matrices, and the code is simpler.