Jump to content

  • Log In with Google      Sign In   
  • Create Account


The Expensive Square Root Function


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 iedoc   Members   -  Reputation: 663

Like
0Likes
Like

Posted 02 September 2011 - 05:27 AM

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[i].x;
		distY = point.y - triVert[i].y;
		distZ = point.z - triVert[i].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[i].x - triVert[i+1].x;
		distY = triVert[i].y - triVert[i+1].y;
		distZ = triVert[i].z - triVert[i+1].z;  

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

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

		smallTriArea[i] = 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?
Braynzar Soft - DirectX Lessons & Game Programming Resources!

Sponsor:

#2 japro   Members   -  Reputation: 887

Like
2Likes
Like

Posted 02 September 2011 - 05:43 AM

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.

#3 iedoc   Members   -  Reputation: 663

Like
0Likes
Like

Posted 02 September 2011 - 06:48 AM

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!
Braynzar Soft - DirectX Lessons & Game Programming Resources!

#4 rip-off   Moderators   -  Reputation: 7651

Like
0Likes
Like

Posted 02 September 2011 - 07:13 AM

I should have thought about checking if the point is on the right side of the triangles edges myself...

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.

#5 Tournicoti   Prime Members   -  Reputation: 682

Like
0Likes
Like

Posted 02 September 2011 - 07:48 AM

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.

#6 iedoc   Members   -  Reputation: 663

Like
0Likes
Like

Posted 02 September 2011 - 09:18 AM

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
Braynzar Soft - DirectX Lessons & Game Programming Resources!

#7 RobTheBloke   Crossbones+   -  Reputation: 2295

Like
0Likes
Like

Posted 02 September 2011 - 09:31 AM

So my question is, Can i find the areas of the triangles WITHOUT using the sqrt() function?


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


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

#include <xmmintrin.h>
inline float fastSqrt(float x)
{
  _mm_store_ss(&x, _mm_sqrt_ss(_mm_load_ss(&x)));
  return x;
}


#8 japro   Members   -  Reputation: 887

Like
0Likes
Like

Posted 02 September 2011 - 12:28 PM

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.

#9 iedoc   Members   -  Reputation: 663

Like
0Likes
Like

Posted 03 September 2011 - 03:50 AM

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

Edited by iedoc, 03 September 2011 - 04:01 AM.

Braynzar Soft - DirectX Lessons & Game Programming Resources!

#10 wildbunny   Members   -  Reputation: 550

Like
1Likes
Like

Posted 03 September 2011 - 04:01 AM

Ok, lets sort this out :)

The area of a triangle is simply half of the 2d cross-product of two of the triangle axis.

http://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm

No need for sqrt() at all.

#11 Álvaro   Crossbones+   -  Reputation: 11877

Like
0Likes
Like

Posted 06 September 2011 - 09:16 AM

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.

#12 wildbunny   Members   -  Reputation: 550

Like
2Likes
Like

Posted 06 September 2011 - 03:20 PM

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 :)

(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).



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:

public function GetArea( ):Number
{
	var area:Number = 0;
	for ( var i:int = 0; i<m_numPoints; i++ )
	{
		var P0:Vector2 = m_localSpacePoints[i];
		var P1:Vector2 = m_localSpacePoints[(i+1)%m_numPoints];
		
		area += P0.Cross( P1 );
	} 
	
	return area/2;
}


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 :)

Cheers, Paul.

#13 iedoc   Members   -  Reputation: 663

Like
0Likes
Like

Posted 08 September 2011 - 07:35 AM

I just had to say wildbunny, ^^^ That is a great function! ;)
Braynzar Soft - DirectX Lessons & Game Programming Resources!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS