Jump to content

  • Log In with Google      Sign In   
  • Create Account


kmx

Member Since 06 Feb 2011
Offline Last Active Aug 06 2012 09:21 PM
-----

Topics I've Started

Efficient ray-model intersect testing

23 July 2012 - 12:07 PM

Hi, my project targets mobile devices so I'm looking for ways to optimize it as much as possible. One area that I am particularly concerned about is ray-model intersection.


Here is the approach I am currently using:

Each model has a bounding box that is oriented with the model (OBB). The OBB is generated when the model is loaded and the points of the OBB are transformed when an intersect test needs to be performed (with logic to optimize not regenerating multiple times in a frame or not regenerating when the object position/transformation hasn't changed, etc.).

When it comes time to do the intersect test:
  • First, before transforming the OBB, I do a quick check to make sure the ray isn't headed in completely the opposite direction. If so, exit, no intersection.
  • Next the OBB is transformed if necessary.
  • An intersect test is performed on the sides of the OBB. If no intersection of the OBB, exit, no intersection.
  • If the OBB is intersected, then I loop through each face of the model:
  • Calculate a normal for the face.
  • If the face is pointing away from the vector, proceed to the next face.
  • If not, perform a Moller-Trumbore intersection test of the triangle - return TRUE if intersection found or proceed to next face if not.
What could I do to optimize this, if anything, and still get similar results? Looping through each face is painful, but my models are fairly low polygon count so it's not that bad. One capability I am adding is the ability to manually specify the OBB and have multiple OBBs for an object so they more closely follow its shape. Another thought is to simply return TRUE when the OBB is intersect when the object is far away without going through each face for a more precise detection.

Ray/Triangle Intersection Difficulties

21 July 2012 - 07:30 PM

I realize this topic is covered extensively, but I've looked at dozens of academic presentations and I can't seem to make any of them work.

I am attempting to detect a) whether a ray (poiint/direction) intersects with a given triangle and b) where (in world coordinates). I adapted the following code from the lighthouse 3D article:

[source lang="cpp"]int isx3d(Line3D line, Plane3D plane, Number3D *where) { Number3D e1 = vec3d(plane.v0, plane.v1); Number3D e2 = vec3d(plane.v0, plane.v2); Number3D h = cross3d(line.p1, e2); float a = dot3d(e1, h); if (a > -0.00001 && a < 0.00001) //(close_enough(a, 0.0f)) return FALSE; float f = 1.0f/a; Number3D s = vec3d(plane.v0, line.p0); float u = f*dot3d(s,h); if (u < 0.0f || u > 1.0f) return FALSE; Number3D q = cross3d(s, e1); float v = f*dot3d(line.p1,q); if (v < 0.0f || u+v > 1.0f) return FALSE; float t = f*dot3d(e2, q); if (t > 0.00001) { float w = 1.0f-(u+v); Number3D ww; ww.x = w*plane.v0.x+u*plane.v1.x+v*plane.v2.x; ww.y = w*plane.v0.y+u*plane.v1.y+v*plane.v2.y; ww.z = w*plane.v0.z+u*plane.v1.z+v*plane.v2.z; *where = ww; return TRUE; } return FALSE;}[/source]

This code seems very similar to other examples, but it has a couple of problems:

First, it works when the point of origin is on the negative side of the triangle, but when the point of origin is on the positive side, it can trigger a false positive result (as if it is considering the ray being cast negatively from the point of origin as well).

Second, the resulting point is wrong. I have tried transforming this every way I can think of, but it either walks across the face of the triangle in a diagonal line (instead of horizontally if I just moving the point of of origin on the X/Y plane) or it moves along a curve(?).

How to get 3D coords of window edges / glUnProject?

18 March 2011 - 11:45 PM

I am trying to determine the 3D worldspace coordinates of the 4 corners of the viewport. Such that if I inset them a little and drew lines connecting these coordinates, I would see a frame around the window. I think what I am looking for is essentially the worldspace coordinates of the near clip plane for whatever orientation the camera is currently in.

I've tried using glUnProject, but I'm not getting the expected results. It is returning coordinates that are way larger than my scene. I've various values for the window Z coordinate, but it doesn't seem to make a difference.

Object orientation from quaternion

06 February 2011 - 02:57 PM

I have a quaternion that represents my camera direction. Using this, I can update the camera's position and calculate the look-at coordinates and up vector. All this works great and I've got a nice demo of flying around in a 3D scene with control of heading, pitch and roll of the camera.

Now, I want to place an object directly in front of the camera and keep its position and orientation locked in sync with the camera's. That is - it should just appear fixed in front of the camera.

Using the camera's direction quaternion, I can correctly position the object, but I can't figure out how to calculate the Euler angles that I need to pass to glRotate in order to orient the object.

I've tried numerous examples from euclidianspace.com, including the quaterion-to-euler conversion, but nothing is working. Depending on which direction I'm flying the object twists around in the wrong ways flips upside down or backwards. I really tried to do my homework before posting - I've read and tried dozens of different approaches, but I think I'm probably missing something fundamental.

Even if there is some other way to orient the object, I really would like to be able to determine the Euler angles from the camera direction for other uses in the program.

Here is the quaternion-to-euler code. I keep coming back to this because it seems like it should be what I'm looking for:

public static Number3d toEuler(Quaternion q)
{
  float test = q.x*q.y + q.z*q.w;
  // handle singularities
  if (test > 0.4999f)
    return new Number3d(
      2f*(float)Math.atan2(q.x,q.w)*r2d,
      (float)Math.PI/2*r2d,
      0f);
  if (test < -0.4999f)
    return new Number3d(
      -2f*(float)Math.atan2(q.x,q.w)*r2d,
      (float)-Math.PI/2*r2d,
      0f);
  float sqw = q.w*q.w;
  float sqx = q.x*q.x; 
  float sqy = q.y*q.y;
  float sqz = q.z*q.z;
  return new Number3d(
    (float)Math.atan2(2*q.y*q.w-2*q.x*q.z , sqx - sqy - sqz + sqw)*r2d,
    (float)Math.asin(2*test)*r2d,
    (float)Math.atan2(2*q.x*q.w-2*q.y*q.z , -sqx + sqy - sqz + sqw)*r2d);
}

PARTNERS