Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Page 1 of 3 123 LastLast
Results 1 to 10 of 28

Thread: Ray Cast / Ray Tracing

  1. #1
    Intern Contributor
    Join Date
    Apr 2015
    Posts
    75

    Question Ray Cast / Ray Tracing

    Hello, I would like to ask some theoretical Questions here , combined with some pseudo code to explain what i need or mean. So recently i implemented traditional ray casting from the camera's position into the scene. I will devide my post in 2 parts:

    PART ONE:
    Ray Unprojecting from far to near plane
    Code :
            float mouse_x = (float)InputState::getMOUSE_X();
    	float mouse_y = WINDOW_HEIGHT - (float)InputState::getMOUSE_Y();
    	glm::vec4 viewport = glm::vec4(0.0f, 0.0f, WINDOW_WIDTH, WINDOW_HEIGHT);
    	this->ray_start = glm::unProject(glm::vec3(mouse_x, mouse_y, 0.0f), camera->getViewMatrix(), Projection, viewport);
    	this->ray_end = glm::unProject(glm::vec3(mouse_x, mouse_y, 1.0f), camera->getViewMatrix(), Projection, viewport);
    Then i implemented a simple function to detect if the ray has collided with a bounding sphere.
    Code :
           glm::vec3 vSphereCenter = Sphere->getCenter();
    	glm::vec3 vA = this->ray_start;
    	glm::vec3 vB = this->ray_end;
    	float fSphereRadius = Sphere->getRadius();
     
    	glm::vec3 vDirToSphere = vSphereCenter - vA;
    	glm::vec3 vLineDir = glm::normalize(vB - vA);
    	float fLineLength = glm::distance(vA, vB);
    	float t = glm::dot(vDirToSphere, vLineDir);
    	glm::vec3 vClosestPoint;
     
    	if (t <= 0.0f)
    		vClosestPoint = vA;
    	else if (t >= fLineLength)
    		vClosestPoint = vB;
    	else
    		vClosestPoint = vA + vLineDir*t;
     
    	return glm::distance(vSphereCenter, vClosestPoint) <= fSphereRadius;

    So far so good. The code above works. Here starts my broken "theory" / "questions". Let's say that we have a scene that consists of models. All models have some auto-generated bounding spheres. So we want to check whitch object the player has "clicked" on , or the object the ray intersects with.First when i was thinking about this. I didnt think that several models can be in a line (in each axis), thats why you should loop over all the models that have been hit and find the closest to the camera. Look at the pseudo code mix below, added some comments as well.
    Code :
    //Here i present you the Pseudo C++ mix :D
    std::vector<models> scene_models;   //All Models in the scene
    std::vector<models> selected_models; //All models that have been hit by the ray
     
    //Loop over every model find where the ray intersects
    for(i,scene_models.size())
    {
      if(RayIntersectsWith(model[i]->getBoundSphere())
          {
             selected_models.pushback(model[i])
          }
    }
    //Loop over all intersected model and find the one closest to the camera
    for(i,selected_models.size())
    {
      //get the distance(camera->pos,selected_models[i]->getBoundSphere()->getCenter());
      //Find the one closest to the camera = closest_model_to_the_camera;
    }
    //Do something with closest_model_to_the_camera
    My Question is as follows: Is this the right way to go ? Would it work ? Is there a more efficient way to apply this ?


    PART TWO
    This part is not connected with the part one. Here i wanted to ask how would one implement terrain responsive ray. A ray that can return the world coords on a 3D Terrain. Currently i have something that works , but not that well. At the moment i am using the ray and performing a binary search to find the point on the terrain
    Code :
    //What i mean by binary search:
    Take the starting point of the ray. Set Ray Lenght. 
    1. Take the middle point of the ray.
    2. Determine if that point is above of below the terrain
    3. if the point is below the terrain take the upper half / else take the lower half of the ray
    4. Repeat N times steps 1-4. (Recursivly)
    //This is not very accurate nor efficient way but does find the exact world position on the terrain, the more times(the bigger the N) you repeat the process the more accurate the result is.

    . And it does work , the only problem is that i have to use big camera angle (~near 90 degrees). The terrain i am using is generated from a height map.
    My question is: Is there some stable, reliable way to return the world coordinates on terrain from the ray.

  2. #2
    Junior Member Newbie
    Join Date
    May 2015
    Posts
    9
    Quote Originally Posted by Asmodeus View Post
    Code :
    //Here i present you the Pseudo C++ mix :D
    std::vector<models> scene_models;   //All Models in the scene
    std::vector<models> selected_models; //All models that have been hit by the ray
     
    //Loop over every model find where the ray intersects
    for(i,scene_models.size())
    {
      if(RayIntersectsWith(model[i]->getBoundSphere())
          {
             selected_models.pushback(model[i])
          }
    }
    //Loop over all intersected model and find the one closest to the camera
    for(i,selected_models.size())
    {
      //get the distance(camera->pos,selected_models[i]->getBoundSphere()->getCenter());
      //Find the one closest to the camera = closest_model_to_the_camera;
    }
    //Do something with closest_model_to_the_camera
    My Question is as follows: Is this the right way to go ? Would it work ? Is there a more efficient way to apply this ?
    I'm not entirely sure if it would be more efficient in your case, but couldn't you create a 2D array (full of 0's) representing what the camera is looking at and put a unique index at the locations where there's supposed to be a model? The index could then be used in a hash/lookup table to find a pointer directing to the model(s). That way, all you'd have to do is to find the 2D position of the mouse, transform that position into indices, look up if there's something in the array at those indices and run your 'closest to camera' function only on the models represented by the index. In cases where you have loads of model, you'd at least save the time you'd waste iterating on non-useful models.
    Last edited by CodcULaval; 07-13-2015 at 07:28 AM.

  3. #3
    Intern Contributor
    Join Date
    Apr 2015
    Posts
    75
    Yea its possible. Also keep in mind that the vector<ofmodels> wont represent all models in the world , only those closest to the camer / or those that will be visible by it. So they wont be that much. Also alot of the scene is usually static. I was just asking if my approach is correct ? Am i on the right path ?

  4. #4
    Junior Member Newbie
    Join Date
    May 2015
    Posts
    9
    Quote Originally Posted by Asmodeus View Post
    Yea its possible. Also keep in mind that the vector<ofmodels> wont represent all models in the world , only those closest to the camer / or those that will be visible by it. So they wont be that much. Also alot of the scene is usually static. I was just asking if my approach is correct ? Am i on the right path ?
    If you only need to know if it works, then yes, I do believe that your method would work.

  5. #5
    Intern Contributor
    Join Date
    Apr 2015
    Posts
    75
    One question tho', i am having not very good time calculating the bounding sphere. Here is the sample snippet, the sphere does seem correct but i dont think that the center is calculated correclty. For example with a simple tree the sphere tends to be around the stem of the tree, same goes for a human-type mesh the sphere's center is around the feet/knees i would expect it to be above the waist
    Code :
    void BoundingSphere::calculateBoundingSphere(std::vector<glm::vec3> vertices)
    {
    	vec3 _center = vec3(0.0f, 0.0f, 0.0f);
    	for (int i = 0; i<vertices.size(); i++) {
    		_center += vertices[i];
    	}
    	_center /= (float)vertices.size();
     
    	float _radius = 0.0f;
    	for (int i = 0; i<vertices.size(); i++) {
    		vec3 v = vertices[i] - _center;
    		float distSq = glm::length(v);
    		if (distSq > _radius)
    			_radius = distSq;
    	}
    	_radius = sqrtf(_radius);
    	this->center = _center;
    	this->radius = _radius;
    }

    EDIT: Also having mostly uneven meshes i should probably move to OBB or AABB
    Last edited by Asmodeus; 07-13-2015 at 11:27 AM.

  6. #6
    Senior Member OpenGL Guru
    Join Date
    Jun 2013
    Posts
    2,959
    Quote Originally Posted by Asmodeus View Post
    This part is not connected with the part one. Here i wanted to ask how would one implement terrain responsive ray. A ray that can return the world coords on a 3D Terrain. Currently i have something that works , but not that well. At the moment i am using the ray and performing a binary search to find the point on the terrain
    Unless I'm misunderstanding your approach, it's incorrrect. If the ray intersects the terrain in multiple locations, it won't necessarily find the intersection which is closest to the viewpoint.

    You can't do this by divide-and-conquer unless you have quadtrees (i.e. mipmaps) containing the minimum and maximum heights for each node. Even then, you may need to recurse into the nearest node first before determining that there's no collision there then recursing into the farther nodes. IOW, in the worst case (for a ray tangential to the surface) it's O(n) not O(log(n)).

    Quote Originally Posted by Asmodeus View Post
    My question is: Is there some stable, reliable way to return the world coordinates on terrain from the ray.
    You know (or presumably can easily find out) the start and end points of the ray in world coordinates, which can be interpolated to find any point on the ray.

  7. #7
    Senior Member OpenGL Guru
    Join Date
    Jun 2013
    Posts
    2,959
    Quote Originally Posted by Asmodeus View Post
    One question tho', i am having not very good time calculating the bounding sphere. Here is the sample snippet, the sphere does seem correct but i dont think that the center is calculated correclty. For example with a simple tree the sphere tends to be around the stem of the tree, same goes for a human-type mesh the sphere's center is around the feet/knees i would expect it to be above the waist
    Your calculation will find a point which is biased toward whichever side of the model has more vertices. There are various algorithms for finding the minimum bounding sphere or a close approximation to it (Link), but they're significantly more complex. A simple alternative is to use the midpoint of the bounding box.

    From your descriptions of the behaviour with a human and a tree, it sounds as if the vertical component is inverted. Are you neglecting to apply any relevant transformations to the centroid?

  8. #8
    Intern Contributor
    Join Date
    Apr 2015
    Posts
    75
    Well i apply scaling to the sphere and transform its position if thats what you mean. While i was waiting for new responses here i managed to create simple AABB generation for meshes and then found a very useful (custom) algorithm that finds intersection between ray and obb. The cool thing is that you can pass a AABB + ModelMatrix and the function that checks the intersection will convert it into an OBB , then check for intersection and return the value. Its handy and pretty accurate. One thing i am missing is that i found out that if i pass only Tranf*Rotation (its all working smooth and fine, pixel perfect detection) but if i pass as model matrix Transf*Rotation*Scaling , the intersection is detected as if the obb is downscaled instead of the opposite.
    Also forgot to mention that i scale the aabb max and min with the scaling factor of the mesh. (i assume this is correct since if i dont do this the box's size is with the mesh's base one)

  9. #9
    Senior Member OpenGL Guru
    Join Date
    Jun 2013
    Posts
    2,959
    Quote Originally Posted by Asmodeus View Post
    One thing i am missing is that i found out that if i pass only Tranf*Rotation (its all working smooth and fine, pixel perfect detection) but if i pass as model matrix Transf*Rotation*Scaling , the intersection is detected as if the obb is downscaled instead of the opposite.
    If you're transforming the ray into the coordinate system of the AABB, you need to use the inverse matrix.

    If you're composing the matrix from primitive transformations, you can avoid a generalised matrix inverse by using (A*B)-1=B-1*A-1 and inverting the individual transformations. Rotation can be inverted by negating the angle, translation by negating the vector, scaling by using the reciprocal of the scale factors.

  10. #10
    Intern Contributor
    Join Date
    Apr 2015
    Posts
    75
    As far as i can see the function does not take in account the scaling. Just a sample snippet from the code. As far as i can see the snippet below shows extrapolation of position and rotation from the matrix.
    Code :
            glm::vec3 OBBposition_worldspace(ModelMatrix[3].x, ModelMatrix[3].y, ModelMatrix[3].z);
    	glm::vec3 delta = OBBposition_worldspace - ray_origin;
    	{
     
    		glm::vec3 xaxis(ModelMatrix[0].x, ModelMatrix[0].y, ModelMatrix[0].z); 
    		float e = glm::dot(xaxis, delta);
    		float f = glm::dot(ray_direction, xaxis);
     
                    //Where below calculations are processed for axis y,z

    About my Part 2 question for the terrain , could you elaborate ?

    "You know (or presumably can easily find out) the start and end points of the ray in world coordinates, which can be interpolated to find any point on the ray."
    I have the start and end points of the ray. But what do you mean by interpolating ?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •