Skip to main content
GameDev.net gamedev.net
🔒 Locked

The Expensive Square Root Function

Started by iedoc Sep 2, 2011 at 11:27 AM 11 replies 5.5k views
Original Post
iedoc
iedoc
I'm trying to check if a point is inside a triangle. I'm doing this by finding the area of the main triangle, and then the area of three triangles using the three points from the first triangle, and the point i want to check if its inside the first triangle. If the point is inside the first triangle, then the three smaller triangles' areas added up should equal the main triangles area, otherwise if the point is outside the main triangle, the three smaller triangles areas summed up will be greater than the main triangles area.

So my question is, Can i find the areas of the triangles WITHOUT using the sqrt() function? that function is so expensive, it could mean the difference between 400 fps and 4 fps (I didn't find those exact fps results, but it does mean the difference between smooth gameplay, and very choppy gameplay).

I've tried to just remove all the sqrt() functions, I figured the result should be the same in the end, but i was wrong.

Anyway, here's my code:

//Find area of first triangle
float distX = triV1.x - triV2.x;
float distY = triV1.y - triV2.y;
float distZ = triV1.z - triV2.z;

float edgeLength1 = sqrt(distX*distX + distY*distY + distZ*distZ);

distX = triV1.x - triV3.x;
distY = triV1.y - triV3.y;
distZ = triV1.z - triV3.z;

float edgeLength2 = sqrt(distX*distX + distY*distY + distZ*distZ);

distX = triV2.x - triV3.x;
distY = triV2.y - triV3.y;
distZ = triV2.z - triV3.z;

float edgeLength3 = sqrt(distX*distX + distY*distY + distZ*distZ);

float s = (edgeLength1 + edgeLength2 + edgeLength3)/2.0f;

float mainTriArea = sqrt(s*(s-edgeLength1)*(s-edgeLength2)*(s-edgeLength3));

//Find areas of the three triangles created with the point

float smallTriArea[3] = {0.0f, 0.0f, 0.0f};
XMFLOAT3 triVert[4];
triVert[0] = triV1;
triVert[1] = triV2;
triVert[2] = triV3;
triVert[3] = triV1; //When i=2, i+1 will be triV1

//Find 3 triangle areas using the plane intersecting point
for(int i = 0; i < 3; i++)
{
distX = point.x - triVert.x;
distY = point.y - triVert.y;
distZ = point.z - triVert.z;

edgeLength1 = sqrt(distX*distX + distY*distY + distZ*distZ);

distX = point.x - triVert[i+1].x;
distY = point.y - triVert[i+1].y;
distZ = point.z - triVert[i+1].z;

edgeLength2 = sqrt(distX*distX + distY*distY + distZ*distZ);

distX = triVert.x - triVert[i+1].x;
distY = triVert.y - triVert[i+1].y;
distZ = triVert.z - triVert[i+1].z;

edgeLength3 = sqrt(distX*distX + distY*distY + distZ*distZ);

s = (edgeLength1 + edgeLength2 + edgeLength3)/2.0f;

smallTriArea = sqrt(s*(s-edgeLength1)*(s-edgeLength2)*(s-edgeLength3));
}

float totalSmallTriArea = smallTriArea[0] + smallTriArea[1] + smallTriArea[2];

//Compare the three smaller triangle areas with the main triangles area
//Subtract a small value from totalSmallTriArea to make up for inacuracy
if(mainTriArea >= (totalSmallTriArea - 0.001f))
{
return true;
}


I've tried to remove just the sqrt() functions from the final areas of each triangle, but that results in more of an approximation than exact, so i lose a lot of accuracy.

I would like to keep the accuracy

any ideas?
japro
japro

I'm trying to check if a point is inside a triangle. I'm doing this by finding the area of the main triangle, and then the area of three triangles using the three points from the first triangle, and the point i want to check if its inside the first triangle. If the point is inside the first triangle, then the three smaller triangles' areas added up should equal the main triangles area, otherwise if the point is outside the main triangle, the three smaller triangles areas summed up will be greater than the main triangles area.


I'm not sure if there is a way to remove the sqrts from that algorithm. But you can sure check if a point is inside a triangle without them. Check out barycentric coordinates for example. Or you could possibly also use dot products with the normal vectors of the edges to determine if the point is on the "correct side" of each edge.
iedoc
iedoc
That's what I was afraid of, not being able to remove the sqrt. But you provided me with an even better AND easier way of doing it! I should have thought about checking if the point is on the right side of the triangles edges myself, but I'm happy you gave me the idea! That will kill two birds with one stone! less code and no more sqrt! I know what barycentric coords are, but I never spent the time to learn ENOUGH about them. I think I will now though, since that appears to be an even more efficient way of doing this.Two thumb up!
rip-off
rip-off

I should have thought about checking if the point is on the right side of the triangles edges myself...
[/quote]
Even if you didn't - a quick Google for "point in triangle test" would expose you to lots of techniques, and with more research you can find performance comparisons for the various techniques.

Lean on the experience of the many people who have walked this path before you.
blog | twitter
Adaline
Adaline
Hello

If you can determine the normal that points towards the outside of the triangle for each edge, you can simply check if the point in 'behind' the 3 edges. If so, the point is inside the triangle.
iedoc
iedoc
i usually always do research before asking questions. That's why I don't usually have to ask questions here first. So your right, I really don't have an excuse for asking this one, sorry

I just liked the method I was already doing it by because I came up with it on my own without research, I guess I didn't put enough thought into alternatives though. But thanks for the reply altogether japro
RobTheBloke
RobTheBloke
So my question is, Can i find the areas of the triangles WITHOUT using the sqrt() function? [/quote]

Not really. The length of the vector returned from the cross product (of both edges) will be equal to half the area, but then again the magnitude requires a sqrt to calculate.

You can however find whether the point is in the triangle *without* calculating the triangle area.

that function is so expensive[/quote]

The stdlib function is, but the equivalent intrinsic is not....

[source]
#include
inline float fastSqrt(float x)
{
_mm_store_ss(&x, _mm_sqrt_ss(_mm_load_ss(&x)));
return x;
}
[/source]
japro
japro
Hmm, now that I think of it. If v and u are the edges of a triangle and rv a by 90° rotated version of v, shouldn't the area be:

A = 1/2 * dot(v,v)*dot(rv,u)/(dot(v,v))

the Idea is to express u and v in the base formed by v and rv... both projections require normalization of v but since you end up multiplying them anyway you might as well "normalize" the whole result with the square of of v's length

Edit: obviously this is just the same as:

A = 1/2*dot(rv,u)

also since dot(u,v) = cos(angle)*|u|*|v| and rv is rotated by 90° it follows that dot(u,rv) = sin(angle)*|u|*|v| which is essentially the area of the parallelogram spanned by u and v right? That's maybe the more intuitive way to think about it.
iedoc
iedoc
That's interesting RobTheBloke, I wasn't aware of that function (don't say i didn't google for another sqrt function, because your right, i didn't...).

I'm going to have to spend a little time thinking about that japro. I'm still interested in calculating the area of a triangle without sqrt functions anyway.

Thanks again for the replies

I was looking at your post again japro, And it was making sense, but then I realized, i would still need to find the length of the triangles edges before i used that equation right? So there's still the problem of finding the length of the edges without square root right? But I see that would at least get rid of at least two square roots if that equation actually works
alvaro
alvaro
The way I think of the area of a triangle is this:

|x1 y1 1|
|x2 y2 1| * (1/2)
|x3 y3 1|

Similarly, the volume of a tetrahedron is

|x1 y1 z1 1|
|x2 y2 z2 1|
|x3 y3 z3 1| * (1/6)
|x4 y4 z4 1|

You get a sign that has to do with the notion of orientation. You can take the absolute value if you want, but the sign is often helpful (for instance, when computing that area of any polygon, you can simply add up the signed areas of the triangles formed by each side of the polygon and an arbitrary point).

This actually works for R^n, multiplying the determinant by (1/n!). But 2D and 3D are probably the only cases you'll be interested in for game development.
wildbunny
wildbunny

You get a sign that has to do with the notion of orientation. You can take the absolute value if you want, but the sign is often helpful (for instance, when computing that area of any polygon, you can simply add up the


The sign also tells you if you have the polygon winding order round the wrong way, because it will be negative in that case

[color="#1C2837"] (for instance, when computing that area of any polygon, you can simply add up the signed areas of the triangles formed by each side of the polygon and an arbitrary point).
[color="#1C2837"][/quote]
[color="#1C2837"]
[color="#1c2837"]Actually, an interesting property of the area calculation means you can calculate the area of a polygon simply by looping over the vertices and summing the cross-product of sequential vertices like this:

[color="#1c2837"]public function GetArea( ):Number
{
var area:Number = 0;
for ( var i:int = 0; i<m_numPoints; i++ )
{
var P0:Vector2 = m_localSpacePoints;
var P1:Vector2 = m_localSpacePoints[(i+1)%m_numPoints];

area += P0.Cross( P1 );
}

return area/2;
}


[color="#1c2837"]No matter what space those vertices are in, the area returned by this function is the same, which is slightly counter intuitive but makes for a nice tight loop

[color="#1c2837"]Cheers, Paul.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.