HyperHacker 136 Report post Posted July 22, 2006 I wrote this function a while ago to convert screen coordinates to world coordinates, so that I could then check if the line created by this intersected any of the triangles on the screen, in order to select them: /* Converts screen coords to world coords Inputs: -XPos, YPos: Screen coords. -WorldPos1: [Out] A vector containing the actual world coordinates. -WorldPos2: [Out] A vector containing the world coordinates, but at maximum depth. Notes: -Automatically flips the Y coord - 0,0 is the top left like it should be. -WorldPos2 is provided so that you can easily determine if a given screen coordinate is overtop of a triangle by forming a line between the two (from the clicked position to the farthest visible point). WorldPos1 and WorldPos2 can be NULL. */ void ScreenToWorldCoords(int XPos, int YPos, Vector* WorldPos1, Vector* WorldPos2) { GLint Viewport[4]; GLdouble ModelView[16], Projection[16]; GLfloat XP, YP, ZP; GLdouble WX, WY, WZ; //World coords this translates to glGetIntegerv(GL_VIEWPORT, Viewport); //Get the viewport coords - Viewport[] = x, y, width, height XP = (GLfloat)XPos; YP = (GLfloat)(Viewport[3] - YPos); glGetDoublev(GL_MODELVIEW_MATRIX, ModelView); //Get the matrices glGetDoublev(GL_PROJECTION_MATRIX, Projection); glReadPixels((GLint)XP, (GLint)YP, 1, 1, GL_DEPTH_COMPONENT, GL_FLOAT, &ZP); //Get the depth of the pixel if(WorldPos1) { gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)ZP, ModelView, Projection, Viewport, &WX, &WY, &WZ); //This gives us the coords of that pixel (*WorldPos1) = Vector((GLfloat)WX, (GLfloat)WY, (GLfloat)WZ); } if(WorldPos2) { gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)0.0, ModelView, Projection, Viewport, &WX, &WY, &WZ); (*WorldPos2) = Vector((GLfloat)WX, (GLfloat)WY, (GLfloat)WZ); } } This was working in an old version, but after adding support for camera rotation, it no longer works even when the camera isn't rotated. The only thing I changed in the drawing code is adding these glRotatef() calls: glLoadIdentity(); glRotatef(Camera.XRot, 1.0, 0.0, 0.0); glRotatef(Camera.YRot, 0.0, 1.0, 0.0); glRotatef(Camera.ZRot, 0.0, 0.0, 1.0); glTranslatef(Camera.XPos, Camera.YPos, Camera.ZPos); glTranslatef(this->XPos, this->YPos, this->ZPos); glBegin(GL_TRIANGLES); I've checked over everything related to drawing, hit detection and mouse input at least 8 times, compared the source with the old version, etc. I modified both versions to display the two points being returned by ScreenToWorldCoords() as a line between them and the numbers themselves. In the old version the line never even appears (I made sure it's being drawn). In the new version both the line and coordinates clearly indicate the problem: The points returned are wrong. The line that should be projected from the mouse's world position out to the edge of the world is only ever at one of those points - sometimes it comes from way out there to the bottom of the screen, and sometimes it goes from the mouse position, plus an arbitrary depth, straight up. I understand you're supposed to apply any translations, rotations, etc before calling gluUnProject(), and that helped a bit, but still didn't get it working the way it was. The best result I got was by loading the identity matrix into both the modelview and projection matrices, and then repeating all translations and rotations, before calling gluUnProject(). This got correct-looking coordinates - the same X and Y position, following the mouse - but the Z coordinates were always 1.0 and -1.0 instead of Camera.ZPos and the edge of the world like they should be. I checked out the coordinates being returned by both versions under various circumstances: When moving the mouse off the top left corner, where no object exists: New: -92.582, 70.574, -69.654 -1.329, 2.492, -1.000 Old: -1.637, 3.732, -1.232 -1.329, 3.500, -1.000 When pointing at an object around the center of the screen: New: 0.054, 0.740, -4.342 0.013, 1.325, -1.000 Old: -0.030, -0.017, -7.279 -0.004, 2.154, -1.000 They seem to give similar results when pointing at an object, but radically different when not. In fact in the new version I can see the coordinates changing in relation to where the mouse is on the object, and in many cases the line comes down and stops right at its surface, but it doesn't get selected. I just don't understand why... I'd just implemented proper camera rotation, and it was working and then stopped. When I look closer, I can see two large problems... one is that the Z axis, and possibly others, is backward. As I move the mouse along a triangle, up the Z axis, the line is actually moving down the axis. Its coordinates go down, whereas if I move the camera in the same direction, the camera coordinates go up. The second problem is that as soon as the mouse isn't over an object, the X, Y and Z values all seem to be completely random. As I move further up the screen, X and Y jump back and forth between numbers like 62 and 10000 while Z just seems to jump to random 4- or 5-digit numbers. Also, here's the code that tests whether a line intersects a triangle; it's exactly the same in both versions: /* Checks if a line intersects a triangle. Inputs: -LineStart: Position the line starts at. -LineEnd: Position the line ends at. -Tri: Shape to check. -Point1, Point2, Point3: Points of Tri that form the triangle to test. Returns: True if the line intersects the triangle, false otherwise. */ bool LineIntersectsTriangle(Vector LineStart, Vector LineEnd, SHAPE3D* Tri, unsigned int Point1, unsigned int Point2, unsigned int Point3) { Vector V, Intersect, T1, T2, T3, Norm; GLfloat D1, D2; V = Tri->Point[Point2].Position - Tri->Point[Point1].Position; Norm = V.CrossProduct(Tri->Point[Point3].Position - Tri->Point[Point1].Position); Norm.Normalize(); D1 = (LineStart - Tri->Point[Point1].Position).DotProduct(Norm); D2 = (LineEnd - Tri->Point[Point1].Position).DotProduct(Norm); if((D1*D2 < 0.0) //Line crosses triangle && (D1 != D2)) //and line and plane aren't parallel - we have a hit { Intersect = Vector(LineStart + (LineEnd - LineStart) * (-D1 / (D2 - D1))); T1 = Norm.CrossProduct(Tri->Point[Point2].Position - Tri->Point[Point1].Position); T2 = Norm.CrossProduct(Tri->Point[Point3].Position - Tri->Point[Point2].Position); T3 = Norm.CrossProduct(Tri->Point[Point1].Position - Tri->Point[Point3].Position); if((T1.DotProduct(Intersect - Tri->Point[Point1].Position) >= 0.0) && (T2.DotProduct(Intersect - Tri->Point[Point2].Position) >= 0.0) && (T3.DotProduct(Intersect - Tri->Point[Point1].Position) >= 0.0)) return true; } return false; } The code that handles mouse input and checks if the line intersects any triangles is exactly the same in both versions. The only change between the object drawing code is adding camera rotation, and removing it again doesn't affect anything. [edit] I noticed it works as well as the old version (which really isn't very well), even when the camera is rotated, so long as it stays at position 0,0,0. As soon as the camera moves it all goes out the window. Seems like it's overcompensating for camera movement; if I move the camera up a little, I have to click way below a polygon to hit it. I noticed a signifigant improvement by not loading the identity matrix before calling gluUnProject(), and instead doing this: glTranslatef(-Camera.XPos, -Camera.YPos, -Camera.ZPos); It's still buggy, though. Loading the identity matrix doesn't actually do any good; after doing so, it always just maps the screen coordinates to the coordinates of the viewport itself, not the polygons in it. (If I move the mouse to the left border, the X position is -1.0. The Z positions are always 1.0 and -1.0.) What I suspect is the biggest problem is that it's being called before the object drawing code, relying on the fact that this code doesn't reset the matrices when it's done (since it does so when it starts) and thus just using the data from whatever object was drawn last on the previous frame. Seems like the perfect answer, but again, correcting this has done nothing. >_< [Edited by - HyperHacker on July 22, 2006 5:51:14 AM] 0 Share this post Link to post Share on other sites
Guest Anonymous Poster Report post Posted July 27, 2006 Try normalizing your window coordinates (XP, YP) w.r.t. the center of your screen (ie: XP and YP would be in the range of XP = [-aspect,aspect], Yp = [-1,1], instead of XP = [0,width], YP = [0,height]). 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted July 27, 2006 OK, so like this?XP = ((GLfloat)XPos / (Viewport[2] / 2.0) - 1.0) * ((GLfloat)Viewport[2] / Viewport[3]);YP = (GLfloat)((Viewport[3] / 2.0) - YPos) / (Viewport[3] / 2.0);That gets me X coordinates between -1.3 and 1.3 and Y coordinates between -1.0 and 1.0 (on a 640x480 window, so aspect is 1.3~). With that, the Z coordinates returned by gluUnProject() appear correct but the X and Y are way off (both around 50-60 - the Z coord is ~52.25 - when they should be close to zero). Also, the coordinates returned are all negated (-52 instead of 52, 60 instead of -60, etc) but it's easy enough to compensate for that. 0 Share this post Link to post Share on other sites
i-photon 145 Report post Posted July 28, 2006 I typed this in exactly like this and it worked for me:// transforms up hereint vp[4];double x,y,z;float fz;double M[16],P[16];glGetDoublev(GL_MODELVIEW_MATRIX,&M[0]);glGetDoublev(GL_PROJECTION_MATRIX,&P[0]);glGetIntegerv(GL_VIEWPORT,&vp[0]);glReadPixels(CursorX,vp[3]-CursorY,1,1,GL_DEPTH_COMPONENT,GL_FLOAT,&fz);gluUnProject((double)CursorX,(double)(vp[3]-CursorY),(double)fz,&M[0],&P[0],&vp[0],&x,&y,&z);edit: I noticed on your glReadPixels() call you didn't invert the Y axis as you did with the gluUnProject() call.I hope that helped :) 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted July 28, 2006 Eh? Both calls use YP which is the inverted Y position. Your example is basically what I've been doing.Here's the latest version, which seems to be getting the Z coord right:void ScreenToWorldCoords(int XPos, int YPos, Vector* WorldPos1, Vector* WorldPos2){ GLint Viewport[4]; GLdouble ModelView[16], Projection[16]; GLfloat XP, YP, ZP; GLdouble WX, WY, WZ; //World coords this translates to glLoadIdentity(); glRotatef(Camera.Rotation.X, 1.0, 0.0, 0.0); glRotatef(Camera.Rotation.Y, 0.0, 1.0, 0.0); glRotatef(Camera.Rotation.Z, 0.0, 0.0, 1.0); glTranslatef(Camera.Position.X, Camera.Position.Y, Camera.Position.Z); /*glRotatef(Camera.Rotation.X, 1.0, 0.0, 0.0); glRotatef(Camera.Rotation.Y, 0.0, 1.0, 0.0); glRotatef(Camera.Rotation.Z, 0.0, 0.0, 1.0); glTranslatef(-Camera.Position.X, -Camera.Position.Y, -Camera.Position.Z);*/ glGetIntegerv(GL_VIEWPORT, Viewport); //Get the viewport coords - Viewport[] = x, y, width, height //XP = (GLfloat)XPos / Viewport[2]; XP = ((GLfloat)XPos / (Viewport[2] / 2.0) - 1.0) * ((GLfloat)Viewport[2] / Viewport[3]); YP = (GLfloat)((Viewport[3] / 2.0) - YPos) / (Viewport[3] / 2.0); glGetDoublev(GL_MODELVIEW_MATRIX, ModelView); //Get the matrices glGetDoublev(GL_PROJECTION_MATRIX, Projection); glReadPixels(XPos, Viewport[3] - YPos, 1, 1, GL_DEPTH_COMPONENT, GL_FLOAT, &ZP); //Get the depth of the pixel DebugOut(DO_ALL, "Mouse: %d, %d = %2.3f, %2.3f, %2.3f\n", XPos, Viewport[3] - YPos, XP, YP, ZP); if(WorldPos1) { gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)ZP, ModelView, Projection, Viewport, &WX, &WY, &WZ); //This gives us the coords of that pixel (*WorldPos1) = -Vector((GLfloat)WX, (GLfloat)WY, (GLfloat)WZ); } if(WorldPos2) { gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)0.0, ModelView, Projection, Viewport, &WX, &WY, &WZ); (*WorldPos2) = -Vector((GLfloat)WX, (GLfloat)WY, (GLfloat)WZ); }} 0 Share this post Link to post Share on other sites
i-photon 145 Report post Posted July 28, 2006 oh... that was actually something I had to correct in mine (duh). (O_<)Yes, I know it is what you were doing.I think its weird that it didn't work for you.The other guy who said normalize your window coords was wrong,you just directly convert to doubles from ints.This also worked for me (yes, this is essentially a re-worked verion of yours):typedef struct tagVECTOR{ double x; double y; double z;}vector;void ScreenToWorld(int CX, int CY, vector *p, vector *nzp){ int vp[4]; float fz; vector V; double M[16],P[16]; glGetDoublev(GL_MODELVIEW_MATRIX,&M[0]); glGetDoublev(GL_PROJECTION_MATRIX,&P[0]); glGetIntegerv(GL_VIEWPORT,&vp[0]); int iY = vp[3]-CY; glReadPixels(CX,iY,1,1,GL_DEPTH_COMPONENT,GL_FLOAT,&fz); if(0 != p) { gluUnProject((double)CX,(double)iY,(double)fz,&M[0],&P[0],&vp[0],&V.x,&V.y,&V.z); *p = V; // the compiler will just copy this temp struct into the one at *p } if(0 != nzp) { gluUnProject((double)CX,(double)iY,0.0,&M[0],&P[0],&vp[0],&V.x,&V.y,&V.z); *nzp = V; }}Try copy/pasting this. I did and it worked fine.Again, I hope this helps.... 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted July 28, 2006 I tried copying that as well as just changing my own to the same thing, in both cases it only worked as well as it did before; works OK (not perfect) until the camera moves. Maybe it has to do with my Vector being an actual class (not just a struct) and using GLfloat instead of double? (I had to add some casting to your code to work with it, but it worked as well as mine. The coordinates I'm working with are actually stored as unsigned shorts, and I have to divide them by 24 to get the real value, so double seems like overkill.)I keep forgetting to mention, adding rotation didn't break it. For a while it was working just fine no matter where the camera was or how it was rotated. It just stopped when I was fixing other things, I'm not sure when exactly.Also, it doesn't seem to make any difference whether I translate/rotate to the camera position or not, nor whether I load the identity matrix before doing so. The only thing unusual I noticed is that the position indicator line only appears when the camera is moved, which is when it stops working. I can see the line hitting polygons, and they get highlighted when it does; it's just either starting or ending at the wrong point, so the wrong polygons get hit.[edit] I made some diagrams of the areas I can select:This is at position 0,0,0. The polygons in the red boxes are the ones I can select. There's a few others that occasionally become highlighted, some seemingly at random, others at points not on them (for example, I can select one of those black ones at the left by putting the mouse on the white one above it). It almost seems like there's a pattern to the colours that can be selected, but applying textures to them doesn't seem to change anything. Also, I can actually hit a few more in wireframe mode for some reason.Move the camera up to 0,-1,0 and these polygons are the only ones that ever get hit. Worse, they seem to just get hit randomly, with the cursor position having almost no apparent relation to which one gets hit when. The yellow vertical line at the left is supposed to be showing the ray casted out from the cursor position (Pt1 and Pt2 displayed in the corner are its coordinates) but it's nowhere near the cursor (which has conveniently left a green square on the screen below the line). At the right I circled the area where one polygon got hit once, but I wasn't able to reproduce it.[Edited by - HyperHacker on July 28, 2006 5:23:52 AM] 0 Share this post Link to post Share on other sites
i-photon 145 Report post Posted July 28, 2006 I should have asked this beforehand: What compiler are you using?Does it have a debugger built into it that will allow you to watchwhat is happening to the variables?edit: You shouldn't have to divide by anything to convert a short to an int, or an int to a double. All that happens is the compiler drops the short into the end of a long. That division could very well be the problem.edit (again): As far as double overkill: There is no need to worry about the number being too big/accurate, only when memory becomes an issue while storing them.Well, as far as GLfloat goes, its just a typedef of a float (so it's treated the same way), the compiler should make automatic conversions, albeit while complaining at the same time.As far as the vector class goes, it should be the same as a struct, just with an extra 4 bytes at the begining for type info/vtable pointer added by the compiler (that is if you are either using virtuals in the inheritence chain [if there is one] or have enabled type info), so it isn't the problem.Here's what I'd do:For the time being, completely ignore the triangle intersector and anything else not related to extracting and rendering the two points you're interested in.Here's a layout of what I think your rendering loop should (or might already) look like:1) Perform ALL global transforms here2) Render and transform objects here3) Convert screen coordinates here4) Draw the two points you're interested inAnd if THAT didn't work, I would just very carefully re-write the whole thing using a new set of objects in a separate program.edit: As in step-by-step, introduce each part of the process until you encounter a problem. Take apart the converter if you have to.And as a very last resort, I'd design my own camera, avoiding theglXXX() transform calls completely. However, I cross that bridge ONLYwhen I get there.After you get that working, implementing the intersector should be a breeze.[Edited by - i-photon on July 28, 2006 9:00:13 PM] 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted July 29, 2006 Alright, I think the problem was mostly because I was checking screen coordinates before I drew things. Doing that after instead, the line indicating the two points renders fine, but it's still highlighting the wrong polygons. Here's a nice example:The blue polygon there is the one being highlighted, while the red and yellow line connects the points that the camera was and the point that was clicked. I can click most of the grass just fine though. In another example that I don't have a picture of, the points of the line are 34.75, 4.373, -79.828 and 16.471, 8.767, -61.0, but the point that gets highlighted is way out at 87.5, 12.5, -200.0. (The camera is around the same place as this image, but the point is way out on those hills at the back.)The division you mentioned is necessary because the polygon data is stored as unsigned shorts and needs to be scaled down. It's only done when loading the scene to get the proper polygon coordinates that get stored.BTW, this is when loading the identity matrix and then re-applying the camera translation and rotation. It seems to work when not doing that, though. Also, the line is in the right spot even when the camera is rotated to arbitrary angles on all 3 axes. 0 Share this post Link to post Share on other sites
i-photon 145 Report post Posted August 5, 2006 Sorry to reply so late... I didn't know you meant thecoordiantes you were talking about were for your triangles, I thought they werethe usual HIWORD() LOWORD() in a DWORD pair that comes from windows.Do the triangles still seem to get selected at random? I suspect it may bethe intersector in that case. At first sight, yours looks fine. BUT just to be certain, try another one:[SOURCE]int test_linetri(point &A, point &B, triangle &T){ vector C = A - T.v[0]; vector D = B - A; vector E1 = T.v[1]-T.v[0]; vector E2 = T.v[0]-T.v[2]; vector N = UnitV(Cross(E1,E2)); float t = Dot(N,D); if(t > 0.0f) // prevents the line from intersecting triangles // "behind" it. { t = -Dot(N,C)/t; D = t*D + T.v[0]; // D is now the intersection if(Dot(Cross(D-T.v[0],E1),N) >= 0.0f) if(Dot(Cross(D-T.v[2],E2),N) >= 0.0f) if(Dot(Cross(D-T.v[2], T.v[2]-T.v[1]),N) >= 0.0f) return 1; } return 0;}[/SOURCE] 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted August 5, 2006 I'm sure the problem is with the intersector, since the line always points directly from the camera to the triangle, but it's a completely different triangle that gets selected. Unfortunately I don't understand any of that horribly messy code. 0 Share this post Link to post Share on other sites
i-photon 145 Report post Posted August 5, 2006 You mean I'M MESSY!?!?!? :PIf you don't understand what its doing, here's the basic idea:1) First, you need to get the line's direction.Subtract point B on the line from point A. This give the vector from A pointingto where B is relative to A (treating A as the origin), I'll call it D.2) Next, you need to measure the line w.r.t. one of the triangle's veritces.This is done by picking one (any one) of the vertices to act as the origin.Now subtract point A from that vertex and store it in a temp (call itC).3) Now, you need the triangle's normal. Optimally these are best stored witheach triangle or vertex (depending on your representation) simply to save a lotof time.4) To get a normal to a triangle, take the cross product of any of the twoedges. I.E: I would say edge 1 = vert[1]-vert[0] and edge 2 = vert[0]-vert[2].Now cross edge 1 and edge 2 (in that order) to create a normal, then normalizeit.5) Next, intersect the line with the plane represented by that normal.Use the following formula:t = -Dot(Normal,C)/Dot(Normal,D)Intersection = t*D + C.Note that this is still relative to the vertex that was picked in step 2.6) Next we check to see if the point is actually in the triangle:We need vectors from each of the triangle's vertices to the point of intersection.We already have the one from the vertex we chose in step 2 to the intersection,just need the other two.Why is this necessary? It is a heuristical intersection test which uses thecross product of each edge versus each vector form the triangle's vertices tothe point of intersection dotted against the traingle's normal. The fact is,for ANY n-sided convex polygon, those dot products will all have the same signif the point is inside.The piled if()s in the algorithm I posted prevent unneeded computation. In theway I was performing the dot products, they would all be positive if the pointwas inside. If one happened to be negative, the point is obviously outside thetriangle.Here's a picture of what I'm saying:If the dot product of each of the three red vectors versus the triangle'snormal are all the same sign, the point of intersection (blue dot) lies withinthe triangle.Edit: To get the actual point of intersection, add the vertex picked in step 2to the intersection obtained from step 5.[Edited by - i-photon on August 5, 2006 9:40:09 PM] 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted August 7, 2006 OK, so like this?bool LineIntersectsTriangle(Vector LineStart, Vector LineEnd, SHAPE3D* Tri, unsigned int Point1, unsigned int Point2, unsigned int Point3){ Vector Line = LineEnd - LineStart; Vector Measure = LineStart - Tri->Point[Point1].Position; //Calculate normal Vector Edge1 = Tri->Point[Point2].Position - Tri->Point[Point1].Position; Vector Edge2 = Tri->Point[Point1].Position - Tri->Point[Point3].Position; Vector Normal = Edge1.CrossProduct(Edge2); Normal.Normalize(); GLfloat T = -Normal.DotProduct(Measure) / Normal.DotProduct(Line); Vector Intersect = (Measure + Line) * T; if((Intersect - Tri->Point[Point1].Position).CrossProduct(Edge1).DotProduct(Normal) < 0.0) return false; if((Intersect - Tri->Point[Point2].Position).CrossProduct(Edge2).DotProduct(Normal) < 0.0) return false; if((Intersect - Tri->Point[Point3].Position).CrossProduct(Tri->Point[Point3].Position - Tri->Point[Point2].Position).DotProduct(Normal) < 0.0) return false; return true;}With that, no matter where I click it thinks I clicked a polygon at (62.625, -6.250, 63.875). Maybe there's something wrong with the vector class itself? Are the operators in the right order and all that?class Vector { private: public: GLfloat X, Y, Z; //Position Vector() //Constructor { X = 0.0; Y = 0.0; Z = 0.0; } Vector(GLfloat InX, GLfloat InY, GLfloat InZ) //Constructor { X = InX; Y = InY; Z = InZ; } inline bool operator== (const Vector& V2) const { return ((X == V2.X) && (Y == V2.Y) && (Z == V2.Z)); } inline Vector operator+ (const Vector& V2) const { return Vector(X + V2.X, Y + V2.Y, Z + V2.Z); } inline Vector operator- (const Vector& V2) const { return Vector(X - V2.X, Y - V2.Y, Z - V2.Z); } inline Vector operator- () const //Negative { return Vector(-X, -Y, -Z); } inline Vector operator/ (const Vector& V2) const { return Vector(X / V2.X, Y / V2.Y, Z / V2.Z); } inline Vector operator/ (GLfloat S) const { GLfloat F = 1.0 / S; return Vector(X * S, Y * S, Z * S); } inline Vector operator* (const Vector& V2) const { return Vector(X * V2.X, Y * V2.Y, Z * V2.Z); } inline Vector operator* (GLfloat S) const { return Vector(X * S, Y * S, Z * S); } inline Vector CrossProduct(const Vector& V2) { return Vector((Y * V2.Z) - (Z * V2.Y), (Z * V2.X) - (X * V2.Z), (X * V2.Y) - (Y * V2.X)); } inline GLfloat DotProduct(const Vector& V2) { return (X * V2.X) + (Y * V2.Y) + (Z * V2.Z); } inline void Normalize() //Normalizes the vector { GLfloat t = sqrtf((X * X) + (Y * Y) + (Z * Z)); X /= t; Y /= t; Z /= t; }};[edit] I investigated a bit and it seems to actually be interseting many triangles. Something must be horribly, horribly wrong because when I changed < 0.0 to <= 0.0 it suddenly hit them all - somehow the result is less than zero, but neither less than or equal to zero? O_o[edit again] I realized one flaw in my code is that I was calling this function too many times per shape, comparing it to nonexistant points. Having fixed that, I changed the comparisons to <= 0.0 again. As it is, this results in no triangles being hit, but if I change this:GLfloat T = -Normal.DotProduct(Measure) / Normal.DotProduct(Line);to this:GLfloat T = -(Normal.DotProduct(Measure) / Normal.DotProduct(Line));it almost works. The wrong triangles still get hit but they're all in a line (as if it's working correctly, but with the line in the wrong place).[more edits] Well, after screwing around with it for an hour, I've managed to make it...-Hit every polygon.-Hit every polygon that has the same Y coordinate for all points.-Hit every polygon that has the same X/Z coordinates for all points.-Hit random polygons.-On rare occasions, hit all the polygons in a straight line, but not the line being tested.I've tried everything and no longer have any idea what I'm doing. >_<[Edited by - HyperHacker on August 8, 2006 8:57:40 PM] 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted August 9, 2006 W00t! I've got it THIIIIIIIS close to working, by writing a whole new app that just renders some triangles (using as few classes as possible in case of memory corruption), analyzing what the function is doing (specifically, where it's returning false and why), and tweaking it until it worked 100% in the test program. I copied that back into the main program, and it's working in almost every case. I have yet to see it claim to hit a polygon that it shouldn't be hitting, the only issue is it's not hitting a few that it should.bool LineIntersectsTriangle(Vector LineStart, Vector LineEnd, SHAPE3D* Tri, unsigned int Point0, unsigned int Point1, unsigned int Point2){ Vector V, Intersect, T1, T2, T3, Norm; GLfloat D1, D2; V = Tri->Point[Point1].Position - Tri->Point[Point0].Position; Norm = V.CrossProduct(Tri->Point[Point2].Position - Tri->Point[Point0].Position); Norm.Normalize(); D1 = (LineStart - Tri->Point[Point0].Position).DotProduct(Norm); D2 = (LineEnd - Tri->Point[Point0].Position).DotProduct(Norm); if((D1 * D2) > 0.0) return false; //Doesn't cross if(D1 == D2) return false; //Parallel Intersect = Vector(LineStart + (LineEnd - LineStart) * (-D1 / (D2 - D1))); T1 = Norm.CrossProduct(Tri->Point[Point1].Position - Tri->Point[Point0].Position); T2 = Norm.CrossProduct(Tri->Point[Point2].Position - Tri->Point[Point1].Position); T3 = Norm.CrossProduct(Tri->Point[Point0].Position - Tri->Point[Point2].Position); if((T1.DotProduct(Intersect - Tri->Point[Point0].Position) >= 0.0) && (T2.DotProduct(Intersect - Tri->Point[Point1].Position) >= 0.0) && (T3.DotProduct(Intersect - Tri->Point[Point0].Position) >= 0.0)) return true; return false;}A few examples of places I can't hit:From this angle, I cannot hit the brick wall. By facing toward it, no problem.I can hit the left Yoshi sign no problem, but not the right. There is at least one other such sign I can't seem to hit.I can hit the top of the brick wall, but not the sides.The signs are actually composed of four shapes like this: _ _|\|\| ¯ ¯Two make up the front of the sign, and two make up the back which has a different texture. There's some Z-fighting here which I can't seem to get rid of (anyone have any ideas?) so I suspect that might contribute to the problem there. The wall has me stumped though. Whatever the case, these spots all have something in common - all the triangles face straight up. I can hit other such triangles fine, though.What bugs me the most is I can hit all of these - indeed, any triangle at all - in wireframe mode. O_o Also, I can't hit the back of any triangle (hence why I suspect Z-fighting is part of the problem) even when culling is disabled. (I never have managed to.)[edit] Wrong image tags. ^_^;[another edit] Alright, I figured out why I can only select certain polygons in wireframe mode. In normal mode, the line only extends out to the polygon, and at some angles (or with culled polygons) does not actually intersect it. In wireframe mode it goes right on through. Now to figure out how to fix that...[edit again] Of course, I do that by changing a line in ScreenToWorldCoords:gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)ZP, ModelView, Projection, Viewport, &WX, &WY, &WZ);togluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)1.0, ModelView, Projection, Viewport, &WX, &WY, &WZ);99% working now. The intersection code is working perfectly. The only problem I'm having is pretty minor, but baffling nonetheless. I use ScreenToWorldCoords() to get the line coordinates, then LineIntersectsTriangle() to see which polygons fall under the cursor. I then do some simple comparisons to see which of these polygons' Z position is closest to the cursor position, so I select the object under the cursor rather than one behind it. This works most of the time, but if I click a certain position on the polygon, it seems to get omitted from the depth test, and one behind it gets selected. In fact it's usually the farthest one that gets selected in this case, no matter how many are actually being tested. Again, the intersector is working and correctly telling me that these polygons are being hit; the problem lies in the depth test not correctly testing them.Here is the updated code that does all of this. (I might end up removing WorldPos3 from ScreenToWorldCoords(). I thought it might give me the coordinates of every pixel that the line intersects, but it only gives the closest one, which would be useful except it doesn't work in wireframe mode.)/*Converts screen coords to world coordsInputs: -XPos, YPos: Screen coords. -WorldPos1: [Out] A vector containing the actual world coordinates. -WorldPos2: [Out] A vector containing the world coordinates, but at maximum depth. -WorldPos3: [Out] A vector containing the world coordinates of the pixel.Notes: -Automatically flips the Y coord - 0,0 is the top left like it should be. -WorldPos2 is provided so that you can easily determine if a given screen coordinate is overtop of a triangle by forming a line between the two (from the clicked position to the farthest visible point). WorldPos3 is provided so that you can do manual depth testing, in case you want to filter out polygons behind others. WorldPos1, WorldPos2 and WorldPos3 can all be NULL if you don't need them.*/void ScreenToWorldCoords(int XPos, int YPos, Vector* WorldPos1, Vector* WorldPos2, Vector* WorldPos3){ GLint Viewport[4]; GLdouble ModelView[16], Projection[16]; GLfloat XP, YP, ZP; GLdouble WX, WY, WZ; //World coords this translates to glLoadIdentity(); glRotatef(Camera.Rotation.X, 1.0, 0.0, 0.0); glRotatef(Camera.Rotation.Y, 0.0, 1.0, 0.0); glRotatef(Camera.Rotation.Z, 0.0, 0.0, 1.0); glTranslatef(Camera.Position.X, Camera.Position.Y, Camera.Position.Z); /*glRotatef(Camera.Rotation.X, 1.0, 0.0, 0.0); glRotatef(Camera.Rotation.Y, 0.0, 1.0, 0.0); glRotatef(Camera.Rotation.Z, 0.0, 0.0, 1.0); glTranslatef(-Camera.Position.X, -Camera.Position.Y, -Camera.Position.Z);*/ glGetIntegerv(GL_VIEWPORT, Viewport); //Get the viewport coords - Viewport[] = x, y, width, height //XP = (GLfloat)XPos / Viewport[2]; /*XP = ((GLfloat)XPos / (Viewport[2] / 2.0) - 1.0) * ((GLfloat)Viewport[2] / Viewport[3]); YP = (GLfloat)((Viewport[3] / 2.0) - YPos) / (Viewport[3] / 2.0);*/ XP = XPos; YP = Viewport[3] - YPos; glGetDoublev(GL_MODELVIEW_MATRIX, ModelView); //Get the matrices glGetDoublev(GL_PROJECTION_MATRIX, Projection); glReadPixels((GLint)XP, (GLint)YP, 1, 1, GL_DEPTH_COMPONENT, GL_FLOAT, &ZP); //Get the depth of the pixel //DebugOut(DO_ALL, "Mouse: %d, %d = %2.3f, %2.3f, %2.3f\n", XPos, Viewport[3] - YPos, XP, YP, ZP); if(WorldPos1) { gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)0.0, ModelView, Projection, Viewport, &WX, &WY, &WZ); //This gives us the near end of the line (at the cursor) (*WorldPos1) = Vector((GLfloat)WX, (GLfloat)WY, (GLfloat)WZ); } if(WorldPos2) { gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)1.0, ModelView, Projection, Viewport, &WX, &WY, &WZ); //the far end, (*WorldPos2) = Vector((GLfloat)WX, (GLfloat)WY, (GLfloat)WZ); } if(WorldPos3) { gluUnProject((GLdouble)XP, (GLdouble)YP, (GLdouble)ZP, ModelView, Projection, Viewport, &WX, &WY, &WZ); //and the coords of the actual pixel at this location. (*WorldPos3) = Vector((GLfloat)WX, (GLfloat)WY, (GLfloat)WZ); }}/*Checks if a line intersects a triangle.Inputs: -LineStart: Position the line starts at. -LineEnd: Position the line ends at. -Tri: Shape to check. -Point1, Point2, Point3: Points of Tri that form the triangle to test.Returns: True if the line intersects the triangle, false otherwise.*/bool LineIntersectsTriangle(Vector LineStart, Vector LineEnd, SHAPE3D* Tri, unsigned int Point0, unsigned int Point1, unsigned int Point2){ Vector V, Intersect, T1, T2, T3, Norm; GLfloat D1, D2; V = Tri->Point[Point1].Position - Tri->Point[Point0].Position; Norm = V.CrossProduct(Tri->Point[Point2].Position - Tri->Point[Point0].Position); Norm.Normalize(); D1 = (LineStart - Tri->Point[Point0].Position).DotProduct(Norm); D2 = (LineEnd - Tri->Point[Point0].Position).DotProduct(Norm); if((D1 * D2) > 0.0) return false; //Doesn't cross if(D1 == D2) return false; //Parallel Intersect = Vector(LineStart + (LineEnd - LineStart) * (-D1 / (D2 - D1))); T1 = Norm.CrossProduct(Tri->Point[Point1].Position - Tri->Point[Point0].Position); T2 = Norm.CrossProduct(Tri->Point[Point2].Position - Tri->Point[Point1].Position); T3 = Norm.CrossProduct(Tri->Point[Point0].Position - Tri->Point[Point2].Position); if((T1.DotProduct(Intersect - Tri->Point[Point0].Position) >= 0.0) && (T2.DotProduct(Intersect - Tri->Point[Point1].Position) >= 0.0) && (T3.DotProduct(Intersect - Tri->Point[Point0].Position) >= 0.0)) return true; return false;}//-------code that checks for intersections and selects the closest polygon that was hit#define Difference(x, y) ((x > y) ? x - y : y - x)int i, j, k;int ClickedObj=-1, ClickedShape=-1, ClickedPoint=-1;Vector ClickNear, ClickFar, ClickPixel;Vector TDepth;if(MouseMoved){ ClickedObj = -1; ClickedShape = -1; ClickedPoint = -1; TDepth.X = 10000.0; TDepth.Y = 10000.0; TDepth.Z = FRUSTUM_DEPTH; //Get the world position we clicked ScreenToWorldCoords(MouseX, MouseY, &ClickNear, &ClickFar, &ClickPixel); //DebugOut(DO_ALL, "Click at %d, %d = %2.3f, %2.3f, %2.3f\n", MouseX, MouseY, ClickPos1.X, ClickPos1.Y, ClickPos1.Z); int Hits = 0, R; //todo: remove for(i=0; i<NumLevelObjects; i++) { for(j=0; j<LevelObject[i]->NumShapes; j++) { for(k=0; k<(LevelObject[i]->Shape[j].NumPoints - 2); k++) { /* See if the line between the cursor and the edge of the world intersects any polygons. There's a depth test here to ensure only the closest polygon gets selected, but it doesn't work very well. */ LevelObject[i]->Shape[j].Point[k].Highlighted = false; LevelObject[i]->Shape[j].Point[k+1].Highlighted = false; LevelObject[i]->Shape[j].Point[k+2].Highlighted = false; R = LineIntersectsTriangle(ClickNear, ClickFar, &LevelObject[i]->Shape[j], k, k+1, k+2); if(R) { Hits++; //LevelObject[i]->Shape[j].Point[k].Highlighted = true; //if(Difference(LevelObject[i]->Shape[j].Point[k].Position.Z, ClickPixel.Z) < TDepth) //Closer than previous check if( (Difference(LevelObject[i]->Shape[j].Point[k].Position.X, ClickPixel.X) <= TDepth.X) && (Difference(LevelObject[i]->Shape[j].Point[k].Position.Y, ClickPixel.Y) <= TDepth.Y) && (Difference(LevelObject[i]->Shape[j].Point[k].Position.Z, ClickPixel.Z) <= TDepth.Z)) { ClickedObj = i; ClickedShape = j; ClickedPoint = k; TDepth.X = Difference(LevelObject[i]->Shape[j].Point[k].Position.X, ClickPixel.X); TDepth.Y = Difference(LevelObject[i]->Shape[j].Point[k].Position.Y, ClickPixel.Y); TDepth.Z = Difference(LevelObject[i]->Shape[j].Point[k].Position.Z, ClickPixel.Z); //DebugOut(DO_ALL, "Hit %d: Pixel @ %2.3f, %2.3f, %2.3f\n", Hits, ClickPixel.X, ClickPixel.Y, ClickPixel.Z); //break; } } //if(R) } //for k //if(Hits) break; } //for j //if(Hits) break; } //for i DebugOut(DO_ALL, "%d hits\n", Hits); if((ClickedObj >= 0) && (ClickedShape >= 0) && (ClickedPoint >= 0)) { //LevelObject[ClickedObj]->Shape[ClickedShape].Point[ClickedPoint].Highlighted = true; LevelObject[ClickedObj]->Shape[ClickedShape].Point[0].Highlighted = true; LevelObject[ClickedObj]->Shape[ClickedShape].Point[1].Highlighted = true; LevelObject[ClickedObj]->Shape[ClickedShape].Point[2].Highlighted = true; DebugOut(DO_ALL, "Clicked obj %d, shp %d, pt %d (%2.3f, %2.3f, %2.3f; px@ %2.3f, %2.3f, %2.3f)\n", ClickedObj, ClickedShape, ClickedPoint, LevelObject[ClickedObj]->Shape[ClickedShape].Point[2].Position.X, LevelObject[ClickedObj]->Shape[ClickedShape].Point[2].Position.Y, LevelObject[ClickedObj]->Shape[ClickedShape].Point[2].Position.Z, ClickPixel.X, ClickPixel.Y, ClickPixel.Z); } MouseMoved = false;}Again, depending where I click, the depth test will just ignore one or more polygons or in some cases work in reverse. (Possibly just ignoring all but the farthest polygon.) The pixel coords returned are correct.Here's a picture demonstrating the problem:The yellow circle is where the camera was; the line indicates where I clicked and what direction the camera was facing. The line intersects a polygon on either side of the wall, as well as the grass. The red polygon is the one that ends up being selected, when it should be one on the other side of the wall.[Edited by - HyperHacker on August 10, 2006 12:03:11 AM] 0 Share this post Link to post Share on other sites
i-photon 145 Report post Posted August 10, 2006 It sounds like you've got this all worked out.As for that weird triangle on the other side of the wall,just dot its normal against the direction of the pick ray(from the camera to the point). If its positive, reject the triangle.However, I wasn't able to read the whole post(really, really big on my laptop).Well, good luck with that one! 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted August 10, 2006 Thanks, but I'm not sure you understood the problem. I want triangles to be selected from the back like that. In this case, however, there is another triangle on the other side of the wall that should be getting selected instead. The depth testing routine seems to have ignored that one and taken the next, which is the one shown in the picture. 0 Share this post Link to post Share on other sites
HyperHacker 136 Report post Posted August 14, 2006 Well, I think I managed to hammer out a solution. The depth testing is working quite nicely now. :)int Hits = 0, R; //todo: removeGLdouble M[16];ScreenToWorldCoords(MouseX, MouseY, &ClickNear, &ClickFar, &ClickPixel);glGetDoublev(GL_MODELVIEW_MATRIX, M);for(i=0; i<NumLevelObjects; i++){ for(j=0; j<LevelObject[i]->NumShapes; j++) { for(k=0; k<(LevelObject[i]->Shape[j].NumPoints - 2); k++) { /* See if the line between the cursor and the edge of the world intersects any polygons. There's a depth test here to ensure only the closest polygon gets selected, but it doesn't work very well. */ LevelObject[i]->Shape[j].Point[k].Highlighted = false; LevelObject[i]->Shape[j].Point[k+1].Highlighted = false; LevelObject[i]->Shape[j].Point[k+2].Highlighted = false; Vector N = Vector( ClickPixel.X + (POLY_HIT_LENGTH * M[0]) + (POLY_HIT_LENGTH * M[1]) + (POLY_HIT_LENGTH * M[2]), ClickPixel.Y + (POLY_HIT_LENGTH * M[4]) + (POLY_HIT_LENGTH * M[5]) + (POLY_HIT_LENGTH * M[6]), ClickPixel.Z + (POLY_HIT_LENGTH * M[8]) + (POLY_HIT_LENGTH * M[9]) + (POLY_HIT_LENGTH * M[10]) ); Vector F = Vector( ClickPixel.X + (-POLY_HIT_LENGTH * M[0]) + (-POLY_HIT_LENGTH * M[1]) + (-POLY_HIT_LENGTH * M[2]), ClickPixel.Y + (-POLY_HIT_LENGTH * M[4]) + (-POLY_HIT_LENGTH * M[5]) + (-POLY_HIT_LENGTH * M[6]), ClickPixel.Z + (-POLY_HIT_LENGTH * M[8]) + (-POLY_HIT_LENGTH * M[9]) + (-POLY_HIT_LENGTH * M[10]) ); R = LineIntersectsTriangle(N, F, &LevelObject[i]->Shape[j], k, k+1, k+2); if(R) { Hits++; ClickedObj = i; ClickedShape = j; ClickedPoint = k; TDepth.X = Difference(LevelObject[i]->Shape[j].Point[k].Position.X, ClickPixel.X); TDepth.Y = Difference(LevelObject[i]->Shape[j].Point[k].Position.Y, ClickPixel.Y); TDepth.Z = Difference(LevelObject[i]->Shape[j].Point[k].Position.Z, ClickPixel.Z); } //if(R) } //for k //if(Hits) break; } //for j //if(Hits) break;} //for iScreenToWorldCoords() now returns ClickPixel, the coordinates of the exact pixel I clicked on. I figured the best way to find the correct triangle would be a point-in-triangle algorithm. However I couldn't find any and don't know much about writing my own, so I cheated a bit. This actually uses the modelview matrix to create a very small line segment going through the pixel, and then simply uses the LineIntersectsTriangle() function I already had to determine if that line is within any triangles. Of course if the two are really close together it still can't tell them apart, but usually at that point they're Z-fighting anyway. (POLY_HIT_LENGTH is defined as 0.5. Reducing it makes the segment smaller, working around this problem in many cases, but using too small a value makes it impossible to hit triangles at near-parallel angles.) 0 Share this post Link to post Share on other sites
Guest Anonymous Poster Report post Posted August 15, 2006 Quote:Original post by i-photonWell, as far as GLfloat goes, its just a typedef of a float (so it's treated the same way), the compiler should make automatic conversions, albeit while complaining at the same time.This is not quite correct.a GLfloat has a fixed size on ALL platforms, the size of float is platform dependant. 0 Share this post Link to post Share on other sites