Jump to content
  • Advertisement
Sign in to follow this  

Above which triangle is the object located?

This topic is 4089 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

http://img179.imageshack.us/img179/5224/theballoz9.png Basically, what I want to do is to find out the height of the ground beneath an object. I have a function that returns the intersection point of a line and a triangle (if any), which works. The problem is that I have to try it on different triangles from the ground object until I find an intersection. This doesn't seem very effective, so what I'm looking for is an (effective) algorithm that can determine which triangle the object is located above so only one intersection test has to be done. Thanks in advance.

Share this post

Link to post
Share on other sites
Approach 1. Preprocess the data and create a rectangular array of grid cells, the entire array overlapping all your triangles. For each cell, generate a list of triangles that are partially or fully contained in the cell. At runtime, you can quickly determine which cell your object is over. Then iterate through the triangle list of that cell and do ray-triangle intersection tests.

Approach 2. Preprocess the data so that each triangle stores pointers to its adjacent triangles. The first object-over-triangle test is the expensive one. Assuming your object is moving, the next object-over-triangle test does the ray-triangle intersection with the current triangle. If it is, you are quickly finished. If it is not, select the adjacent triangle that is "in the direction of motion" of the object from its last position to current position. Repeat searching adjacent triangles until you find the one the object is over. (This is sometimes called a "linear walk".)

Share this post

Link to post
Share on other sites
Thanks for the reply.

I suppose I'll go with the first approach. The second is clever, but the first one will be easier for me to make.

Thanks again.

Share this post

Link to post
Share on other sites
From your image it looks like you want the height from a height field (?)

float Terrain::GetHeight(float x, float z) const
//Hitta höjden för hörnen i cellen
const float ll= GetHeight((int)x, (int)z );
const float lr= GetHeight((int)x+1 , (int)z );
const float ul= GetHeight((int)x , (int)z+1);
const float ur= GetHeight((int)x+1 , (int)z+1);

//Beräkna positionen i cellen (kvadraten)
//moa plocka fram decimaldelen
const float dx= x-/*(float)*/((int)x);
const float dz= z-/*(float)*/((int)z);

//Dela i två trianglar

| 1 / |
| / 2 |

if(dx + dz < 1.0) // Första triangeln
//const float slopeX = lr - ll;
//const float slopeZ = ul - ll;
const float slopeX = ul - ur;
const float slopeZ = lr - ur;
return ll + (slopeX*dx) + (slopeZ*dz);
else //Andra
//const float slopeX = lr - ur;
//const float slopeZ = ul - ur;
const float slopeX = ll - lr;
const float slopeZ = ll - ul;
return ur + (slopeX*(1.0f-dx)) + (slopeZ*(1.0f-dz));

//Bilinjär interpolering (?) (direkt i cellen, måste vara plan)
//return (ll * (1.0f - dz - dx + (dx * dz)) +
// ul * (dx - (dx * dz)) +
// ur * (dx * dz) +
// lr * (dz - (dz * dx)));

[Edited by - Calexus on May 10, 2007 7:47:49 AM]

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!