射线三角相交选取不起作用 [英] Ray-Triangle intersection picking not working
问题描述
过去几天，我一直在为此工作，但一直处于困境.我需要能够触摸屏幕并返回模型上最接近与在拾取点生成的光线相交的近平面的点的x，y，z坐标.我认为我的问题的一部分是我在模型的整个渲染代码中进行了一堆矩阵变换和旋转，尽管我感兴趣的几何图形都在特定的变换状态下进行了渲染.我正在使用的代码如下.如果有人可以帮助我弄清楚如何使它正常工作，那将是非常棒的. checkCollision()被提供给用户单击的点，而gluUnProject()应该将我的2d选择点转换为我的近平面和远平面上的3D坐标，0为近平面，而1为远平面.我的用法在这里，并且在渲染几何图形之前就被调用了，所以所有变换都已经应用了:
I've been working on this for the past several days and have been stuck. I need to be able to touch the screen and return the x,y,z coordinates of the point on my model closest to the near plane that intersects the ray generated at the pick point. I think part of my problem is I'm doing a bunch of matrix transformations and rotations throughout the render code for my model, although the geometry I'm interested in is all rendered at a specific transformation state. My code that I'm using is below. If anyone can help me figure out how to get this working, that would be awesome. checkCollision() is fed the point that the user clicks on, and gluUnProject() is supposed to transform my 2d pick point into 3D coordinates on my near and far planes, 0 being the near plane and 1 being the far plane. My usage is here and is called right before the geometry is rendered, so all transforms have already been applied:
[self checkCollision:touchPoint panVector:panVec];
下面的代码是冲突检查代码:
This code below is the collision checking code:
-(Boolean) checkCollision:(CGPoint)winPos panVector:(Vector3f*)panVec
{
glGetIntegerv(GL_VIEWPORT, viewport);
winPos.y = (float)viewport[3] - winPos.y;
Vector3f nearPoint;
Vector3f farPoint;
glGetFloatv(GL_PROJECTION_MATRIX, projection);
glGetFloatv(GL_MODELVIEW_MATRIX, modelview);
//Retreiving position projected on near plane
gluUnProject(winPos.x, winPos.y , 0, modelview, projection, viewport, &nearPoint.x, &nearPoint.y, &nearPoint.z);
//Retreiving position projected on far plane
gluUnProject(winPos.x, winPos.y, 1, modelview, projection, viewport, &farPoint.x, &farPoint.y, &farPoint.z);
Vector3f *near = [[Vector3f alloc] initWithFloatsX:nearPoint.x Y:nearPoint.y Z:nearPoint.z];
Vector3f *far = [[Vector3f alloc] initWithFloatsX:farPoint.x Y:farPoint.y Z:farPoint.z];
Vector3f *d = [Vector3f subtractV1:far minusV2:near];
Vector3f *v0 = [[Vector3f alloc] init];
Vector3f *v1 = [[Vector3f alloc] init];
Vector3f *v2 = [[Vector3f alloc] init];
Vector3f *e1; // = [[Vector3f alloc] init];
Vector3f *e2; // = [[Vector3f alloc] init];
for (int i = 0; i < assemblyObj->numObjects; i++) {
for (int j = 0; j < assemblyObj->partList[i].numVertices; j+=18) {
v0.x = assemblyObj->partList[i].vertices[j+0];
v0.y = assemblyObj->partList[i].vertices[j+1];
v0.z = assemblyObj->partList[i].vertices[j+2];
v1.x = assemblyObj->partList[i].vertices[j+6];
v1.y = assemblyObj->partList[i].vertices[j+7];
v1.z = assemblyObj->partList[i].vertices[j+8];
v2.x = assemblyObj->partList[i].vertices[j+12];
v2.y = assemblyObj->partList[i].vertices[j+13];
v2.z = assemblyObj->partList[i].vertices[j+14];
e1 = [Vector3f subtractV1:v1 minusV2:v0];
e2 = [Vector3f subtractV1:v2 minusV2:v0];
Vector3f *p = [[Vector3f alloc] init];
[Vector3f cross:p V1:d V2:e2];
float a = [Vector3f dot:e1 V2:p];
if (a > -.000001 && a < .000001) {
continue;
}
float f = 1/a;
Vector3f *s = [Vector3f subtractV1:near minusV2:v0];
float u = f*([Vector3f dot:s V2:p]);
if (u<0 || u>1) {
continue;
}
Vector3f *q = [[Vector3f alloc] init];
[Vector3f cross:q V1:s V2:e1];
float v = f*([Vector3f dot:d V2:q]);
if (v<0 || (u+v)>1) {
continue;
}
//NSLog(@"hit polygon");
return true;
}
}
//NSLog(@"didn't hit polygon");
return FALSE;
}
GLint gluUnProject(GLfloat winx, GLfloat winy, GLfloat winz,
const GLfloat model[16], const GLfloat proj[16],
const GLint viewport[4],
GLfloat * objx, GLfloat * objy, GLfloat * objz)
{
/* matrice de transformation */
GLfloat m[16], A[16];
GLfloat in[4], out[4];
/* transformation coordonnees normalisees entre -1 et 1 */
in[0] = (winx - viewport[0]) * 2 / viewport[2] - 1.f;
in[1] = (winy - viewport[1]) * 2 / viewport[3] - 1.f;
in[2] = 2 * winz - 1.f;
in[3] = 1.f;
/* calcul transformation inverse */
matmul(A, proj, model);
invert_matrix(A, m);
/* d'ou les coordonnees objets */
transform_point(out, m, in);
if (out[3] == 0.f)
return GL_FALSE;
*objx = out[0] / out[3];
*objy = out[1] / out[3];
*objz = out[2] / out[3];
return GL_TRUE;
}
void transform_point(GLfloat out[4], const GLfloat m[16], const GLfloat in[4])
{
#define M(row,col) m[col*4+row]
out[0] =
M(0, 0) * in[0] + M(0, 1) * in[1] + M(0, 2) * in[2] + M(0, 3) * in[3];
out[1] =
M(1, 0) * in[0] + M(1, 1) * in[1] + M(1, 2) * in[2] + M(1, 3) * in[3];
out[2] =
M(2, 0) * in[0] + M(2, 1) * in[1] + M(2, 2) * in[2] + M(2, 3) * in[3];
out[3] =
M(3, 0) * in[0] + M(3, 1) * in[1] + M(3, 2) * in[2] + M(3, 3) * in[3];
#undef M
}
void matmul(GLfloat * product, const GLfloat * a, const GLfloat * b)
{
/* This matmul was contributed by Thomas Malik */
GLfloat temp[16];
GLint i;
#define A(row,col) a[(col<<2)+row]
#define B(row,col) b[(col<<2)+row]
#define T(row,col) temp[(col<<2)+row]
/* i-te Zeile */
for (i = 0; i < 4; i++) {
T(i, 0) =
A(i, 0) * B(0, 0) + A(i, 1) * B(1, 0) + A(i, 2) * B(2, 0) + A(i,
3) *
B(3, 0);
T(i, 1) =
A(i, 0) * B(0, 1) + A(i, 1) * B(1, 1) + A(i, 2) * B(2, 1) + A(i,
3) *
B(3, 1);
T(i, 2) =
A(i, 0) * B(0, 2) + A(i, 1) * B(1, 2) + A(i, 2) * B(2, 2) + A(i,
3) *
B(3, 2);
T(i, 3) =
A(i, 0) * B(0, 3) + A(i, 1) * B(1, 3) + A(i, 2) * B(2, 3) + A(i,
3) *
B(3, 3);
}
#undef A
#undef B
#undef T
memcpy(product, temp, 16 * sizeof(GLfloat));
}
int invert_matrix(const GLfloat * m, GLfloat * out)
{
/* NB. OpenGL Matrices are COLUMN major. */
#define SWAP_ROWS(a, b) { GLfloat *_tmp = a; (a)=(b); (b)=_tmp; }
#define MAT(m,r,c) (m)[(c)*4+(r)]
GLfloat wtmp[4][8];
GLfloat m0, m1, m2, m3, s;
GLfloat *r0, *r1, *r2, *r3;
r0 = wtmp[0], r1 = wtmp[1], r2 = wtmp[2], r3 = wtmp[3];
r0[0] = MAT(m, 0, 0), r0[1] = MAT(m, 0, 1),
r0[2] = MAT(m, 0, 2), r0[3] = MAT(m, 0, 3),
r0[4] = 1.f, r0[5] = r0[6] = r0[7] = 0.f,
r1[0] = MAT(m, 1, 0), r1[1] = MAT(m, 1, 1),
r1[2] = MAT(m, 1, 2), r1[3] = MAT(m, 1, 3),
r1[5] = 1.f, r1[4] = r1[6] = r1[7] = 0.f,
r2[0] = MAT(m, 2, 0), r2[1] = MAT(m, 2, 1),
r2[2] = MAT(m, 2, 2), r2[3] = MAT(m, 2, 3),
r2[6] = 1.f, r2[4] = r2[5] = r2[7] = 0.f,
r3[0] = MAT(m, 3, 0), r3[1] = MAT(m, 3, 1),
r3[2] = MAT(m, 3, 2), r3[3] = MAT(m, 3, 3),
r3[7] = 1.f, r3[4] = r3[5] = r3[6] = 0.f;
/* choose pivot - or die */
if (fabsf(r3[0]) > fabsf(r2[0]))
SWAP_ROWS(r3, r2);
if (fabsf(r2[0]) > fabsf(r1[0]))
SWAP_ROWS(r2, r1);
if (fabsf(r1[0]) > fabsf(r0[0]))
SWAP_ROWS(r1, r0);
if (0.f == r0[0])
return GL_FALSE;
/* eliminate first variable */
m1 = r1[0] / r0[0];
m2 = r2[0] / r0[0];
m3 = r3[0] / r0[0];
s = r0[1];
r1[1] -= m1 * s;
r2[1] -= m2 * s;
r3[1] -= m3 * s;
s = r0[2];
r1[2] -= m1 * s;
r2[2] -= m2 * s;
r3[2] -= m3 * s;
s = r0[3];
r1[3] -= m1 * s;
r2[3] -= m2 * s;
r3[3] -= m3 * s;
s = r0[4];
if (s != 0.f) {
r1[4] -= m1 * s;
r2[4] -= m2 * s;
r3[4] -= m3 * s;
}
s = r0[5];
if (s != 0.f) {
r1[5] -= m1 * s;
r2[5] -= m2 * s;
r3[5] -= m3 * s;
}
s = r0[6];
if (s != 0.f) {
r1[6] -= m1 * s;
r2[6] -= m2 * s;
r3[6] -= m3 * s;
}
s = r0[7];
if (s != 0.f) {
r1[7] -= m1 * s;
r2[7] -= m2 * s;
r3[7] -= m3 * s;
}
/* choose pivot - or die */
if (fabsf(r3[1]) > fabsf(r2[1]))
SWAP_ROWS(r3, r2);
if (fabsf(r2[1]) > fabsf(r1[1]))
SWAP_ROWS(r2, r1);
if (0.f == r1[1])
return GL_FALSE;
/* eliminate second variable */
m2 = r2[1] / r1[1];
m3 = r3[1] / r1[1];
r2[2] -= m2 * r1[2];
r3[2] -= m3 * r1[2];
r2[3] -= m2 * r1[3];
r3[3] -= m3 * r1[3];
s = r1[4];
if (0.f != s) {
r2[4] -= m2 * s;
r3[4] -= m3 * s;
}
s = r1[5];
if (0.f != s) {
r2[5] -= m2 * s;
r3[5] -= m3 * s;
}
s = r1[6];
if (0.f != s) {
r2[6] -= m2 * s;
r3[6] -= m3 * s;
}
s = r1[7];
if (0.f != s) {
r2[7] -= m2 * s;
r3[7] -= m3 * s;
}
/* choose pivot - or die */
if (fabs(r3[2]) > fabs(r2[2]))
SWAP_ROWS(r3, r2);
if (0.f == r2[2])
return GL_FALSE;
/* eliminate third variable */
m3 = r3[2] / r2[2];
r3[3] -= m3 * r2[3], r3[4] -= m3 * r2[4],
r3[5] -= m3 * r2[5], r3[6] -= m3 * r2[6], r3[7] -= m3 * r2[7];
/* last check */
if (0.f == r3[3])
return GL_FALSE;
s = 1.f / r3[3]; /* now back substitute row 3 */
r3[4] *= s;
r3[5] *= s;
r3[6] *= s;
r3[7] *= s;
m2 = r2[3]; /* now back substitute row 2 */
s = 1.f / r2[2];
r2[4] = s * (r2[4] - r3[4] * m2), r2[5] = s * (r2[5] - r3[5] * m2),
r2[6] = s * (r2[6] - r3[6] * m2), r2[7] = s * (r2[7] - r3[7] * m2);
m1 = r1[3];
r1[4] -= r3[4] * m1, r1[5] -= r3[5] * m1,
r1[6] -= r3[6] * m1, r1[7] -= r3[7] * m1;
m0 = r0[3];
r0[4] -= r3[4] * m0, r0[5] -= r3[5] * m0,
r0[6] -= r3[6] * m0, r0[7] -= r3[7] * m0;
m1 = r1[2]; /* now back substitute row 1 */
s = 1.f / r1[1];
r1[4] = s * (r1[4] - r2[4] * m1), r1[5] = s * (r1[5] - r2[5] * m1),
r1[6] = s * (r1[6] - r2[6] * m1), r1[7] = s * (r1[7] - r2[7] * m1);
m0 = r0[2];
r0[4] -= r2[4] * m0, r0[5] -= r2[5] * m0,
r0[6] -= r2[6] * m0, r0[7] -= r2[7] * m0;
m0 = r0[1]; /* now back substitute row 0 */
s = 1.f / r0[0];
r0[4] = s * (r0[4] - r1[4] * m0), r0[5] = s * (r0[5] - r1[5] * m0),
r0[6] = s * (r0[6] - r1[6] * m0), r0[7] = s * (r0[7] - r1[7] * m0);
MAT(out, 0, 0) = r0[4];
MAT(out, 0, 1) = r0[5], MAT(out, 0, 2) = r0[6];
MAT(out, 0, 3) = r0[7], MAT(out, 1, 0) = r1[4];
MAT(out, 1, 1) = r1[5], MAT(out, 1, 2) = r1[6];
MAT(out, 1, 3) = r1[7], MAT(out, 2, 0) = r2[4];
MAT(out, 2, 1) = r2[5], MAT(out, 2, 2) = r2[6];
MAT(out, 2, 3) = r2[7], MAT(out, 3, 0) = r3[4];
MAT(out, 3, 1) = r3[5], MAT(out, 3, 2) = r3[6];
MAT(out, 3, 3) = r3[7];
return GL_TRUE;
#undef MAT
#undef SWAP_ROWS
}
我遵循贾斯汀·迈纳斯(Justin Meiners)提出的渲染点的建议，向我展示我的拾取射线在哪里生成，我可以看到现在发生了什么，但不知道为什么.我的场景通过四元数实现了圆弧球旋转，缩放和平移.我将大致列出场景正在执行的操作，然后是拾取射线正在发生的操作.
I followed Justin Meiners suggestion of rendering points to show me where my pick ray is getting generated and I can see what's happening now, but don't know why. My scene implements arcball rotation, zooming and panning through quaternions. I'll roughly lay out what my scene is doing then what is happening with my pick ray.
首先，设置我的视口:
glViewport(0, 0, scene.width, scene.height);
glOrthof(-11.25, 11.25, -14.355, 14.355, -1000, 1000);
接下来，我抓取了16元素矩阵，将其用作arcball方法的一部分，以浏览场景并将模型视图矩阵乘以它:
Next, I grab the 16 element matrix that I use as part of my arcball method to navigate my scene and multiply my modelview matrix by it:
float mat[16];
[arcball get_Renamed:mat];
glMultMatrixf(mat);
现在，我来做我的选择:
Now, I do my pick ray:
glGetIntegerv(GL_VIEWPORT, viewport);
glGetFloatv(GL_PROJECTION_MATRIX, projection);
glGetFloatv(GL_MODELVIEW_MATRIX, modelview);
touchPoint.y = (float)viewport[3] - touchPoint.y;
Vector3f nearPoint, farPoint;
//Retreiving position projected on near plane
gluUnProject(touchPoint.x, touchPoint.y , 0, modelview, projection, viewport, &nearPoint.x, &nearPoint.y, &nearPoint.z);
//Retreiving position projected on far plane
gluUnProject(touchPoint.x, touchPoint.y, 1, modelview, projection, viewport, &farPoint.x, &farPoint.y, &farPoint.z);
float coords[3] = {nearPoint.x, nearPoint.y, nearPoint.z};
float coords2[3] = {farPoint.x, farPoint.y, farPoint.z};
glPointSize(100);
glColor4f(1, 0, 0, 1);
glEnableClientState(GL_VERTEX_ARRAY);
glVertexPointer(3, GL_FLOAT, sizeof(coords[0])*3, coords);
glDrawArrays(GL_POINTS, 0, 1);
glPointSize(150);
glColor4f(0, 0, 1, 1);
glEnableClientState(GL_VERTEX_ARRAY);
glVertexPointer(3, GL_FLOAT, sizeof(coords2[0])*3, coords2);
glDrawArrays(GL_POINTS, 0, 1);
glDisableClientState(GL_VERTEX_ARRAY);
我这样做了，在旋转场景之前效果很好，但是一旦我开始旋转场景，远点就开始移动.如果我将场景精确地旋转180度，则远点将与近点重新对齐.知道发生了什么吗?电弧球只是基于Ken Shoemake的算法.
I do this, and it works fine before I rotate my scene, but as soon as I start to rotate my scene, the far point starts to move around. If I rotate the scene around exactly 180 degrees, the far point is back in line with the near point. Any idea what is going on? The arcball is just based on Ken Shoemake's algorithm.
推荐答案
我终于弄清楚我在做什么错.创建它们后，您必须立即获得GL_VIEWPORT和GL_PROJECTION_MATRIX的状态，该状态恰好在
I finally figured out what I was doing wrong. You have to get the state of GL_VIEWPORT and GL_PROJECTION_MATRIX right after you create them, which is right after the
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
通话.如果稍后再执行此操作，则矩阵转换会影响视口和投影矩阵.看起来好像他们不应该，但是他们确实如此.您希望获得选择状态的唯一矩阵是modelview矩阵，当您的modelview具有与尝试执行gluUnProject的几何相同的转换时，您想要这样做.一旦我弄清楚了，光线拾取算法就可以很好地工作.在iPad上，它可以在19ms内对15,000个三角形执行三角射线相交，相当于每秒约80万个相交.对于iPad来说还算不错，尽管我确信可以通过预先计算三角形平面方程来提高性能.感谢您的建议，他们帮助我弄清楚了所发生的事情，以便我进行修复.
calls. If you do this later, then your matrix transformations are affecting your viewport and projection matrices. It doesn't seem like they should, but they do. The only matrix you want to get the state of when you do your picking is the modelview matrix, and you want to do that when your modelview has the same transformations as the geometry you are trying to perform gluUnProject on. Once I figured that out, the ray picking algorithm worked great. On the iPad, it can perform triangle-ray intersection on 15,000 triangles in 19ms, which equates to about 800,000 intersections per second. Not too bad for an iPad, although I'm sure performance could be improved by precomputing triangle plane equations. Thanks for the suggestions, they helped me to figure out what was going on so I could fix it.
这篇关于射线三角相交选取不起作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
