ents.FindInWhatever: Explained

I got bored and decided to take a look at the ents.FindInShapes through the looking glass. This thread is the result. Here I will attempt to explain the inner workings of those functions.

Most of you have probably figured a lot of this stuff out, but I figured I should post this for those who are curious. Before I start I’d like to make it clear that I’m not 100% sure on these, my examples are just educated guesses. I also have not tested any of the code shown here, its mostly just concept code.

With that being said, lets start with **[Ents.FindInBox

http://wiki.garrysmod.com/favicon.ico](wiki.garrysmod.com/?title=Ents.FindInBox)**. For this one we are looking for entities between certain boundries.

Here’s what it might look like in Lua:
[lua]
function ents.FindInBox(vMin, vMax) --vMin and vMax represent the lower/upper bounds (diagonally opposite corners) of our box

local boxEnts = {} --Lets make a table

for _, v in pairs(ents.GetAll()) do --Grabbing all of the entities to loop through
	
	--Now we check to see if the nearest point on the entity's bounding box is inside of our lower/upper bounds.
	if v:NearestPoint(vMin) >= vMin and v:NearestPoint(vMax) <= vMax  then
		
		table.insert(boxEnts, v)
		
	end
	
end

return boxEnts --Return the table of our entities

end
[/lua]
Now wasn’t that just insanely simple?

For a while I had been wondering what’s going on inside of **[Ents.FindInSphere

http://wiki.garrysmod.com/favicon.ico](wiki.garrysmod.com/?title=Ents.FindInSphere)**. Well, today it finally occurred to me that it wasn’t really checking within a given space.

Lets step back a second and take a look at what a circle is.

Okay, so a circle is a set of equidistant points around a given origin. That’s why all circles have an area of zero, since point has no area. That means a set of them won’t either. The area you find in most math problems is the area inside of a circle, but I digress.

Now lets take it up a notch and talk about spheres. A sphere is a set of equidistant points around an origin within a 3-dimensional space. Some of you may see where I’m going with this.

Finding objects in a sphere is not actually checking in a space. All you really have to do is check the distance. The ents.FindInSphere function probably looks something like this in Lua:
[lua]
function ents.FindInSphere(vPos, fRadius) --vPos is our origin, and fRadius is the radius

local sphereEnts = {} --Lets make a table again!
local radsqrd = fRadius^2 --Optimization so that the math doesn't need to be done every iteration of our loop

for _, v in pairs(ents.GetAll()) do --Grabbing all of the entities to loop through (again)
	
	--Now we check to see if the nearest point on the entity's bounding box is closer to the center
	--than the length of the radius
	if (vPos - v:NearestPoint(vPos)):LengthSqr() <= radsqrd then 
		
		table.insert(sphereEnts, v) --Insert the entity into our table
		
	end
	
end

return sphereEnts --Return the table of our entities

end
[/lua]
As you can see, you don’t need anything complicated. Since a set of points around the origin represent the contents of the sphere, all you need to do is check if the position of the entity is closer to the center than the points are. It’s a lot simpler than I thought it would be.

Here comes the more complicated one: **[Ents.FindInCone

http://wiki.garrysmod.com/favicon.ico](wiki.garrysmod.com/?title=Ents.FindInCone)**. I disagree with the explanation on the wiki talking about cutting a sphere in half and such.
First off, lets look at the dimensions we are dealing with.

http://accad.osu.edu/~pgerstma/class/vnv/resources/info/AnnotatedVrmlRef/Images/Cone.gif

This time we will be using our geometry skills. I hope you all payed attention in math class!

This function uses a few more arguments than the last two. We have a start position, the direction that it’s pointed in, the distance which determines the end position, and a radius.
We’re going to use a method similar to what we used for ents.FindInSphere. For this to work, however, we need to know the radius at any given point on the cone.

Okay, now we can check if an entity is in our cone as it gets closer to the tip, but first we need to find out how far the entity is from the center line connecting our starting and ending positions.
Now we need to use some formulas. What we’re going to do is make a triangle out of the start point, end point, and entity position. Let’s call them A, B, and C. The lengths between them are a, b, and c. This means the distance we are looking for is the height of the triangle, represented by h.

Here is a diagram:

http://img684.imageshack.us/img684/4526/cone1.png

Then we use a lovely little thing called Heron’s Formula. Heron’s Formula says that if the sides of the triangle are a, b, c, and the semiperimeter is s (s = (a+b+c)/2), then the area is

.

Since the area of a triangle is half the base times the height (a = ½bh ), we can find our height!

So lets try this:



With triangle sides a, b, c

s = (a+b+c)/2
area^2 = s(s-a)(s-b)(s-c)
area/½b = h


So now that we have h, we need to know where it is located along the cone’s center, represented by D. We can find this by finding the length of one of the segments of the base side that is split by the height line. This is represented by l in the diagram.
To do this, we will use the Pathagorean Theorum (a^2+b^2=c^2), except this time our base line is the h line. In this case we need to find a.



With triangle sides a, b, c

c^2 = a^2+b^2
a^2 = c^2-b^2


Here’s what I think it looks like in Lua:
[lua]
–So we have a starting position (vPos), a direction to point in (vDir), a distance (fDistance), and a radius (fRadius)
function ents.FindInCone(vPos, vDir, fDistance, fRadius)

local coneEnts = {} --Lets make a table again (again)

for _, v in pairs(ents.GetAll()) do --This is getting old.
	
	--We're going to make a triangle with the start/end positions and the entity's position
	local A, B, C = vPos, vPos+vDir*fDistance, v:GetPos() 	--Our triangle corner positions
															--A = start, B = end, C = entity
	
	--Now we're going to find the distance between each point
	local a, b, c = (A - B):Length(), (B - C):Length(), (A - C):Length() 	--Our triangle side lengths
																			--a = A to B, b = B to C, c = C to A
	
	local s = (a+b+c)/2 --Our subperimeter using Heron's Formula
	
	local area = math.sqrt(s(s-a)(s-b)(s-c)) --Square root of our subperimeter gives us the area
	
	local h = area/(a/2) 	--Using the area formula (a = 1/2bh) to give us the height of our triangle
							--The height of our triangle is basically the distance from our entity to the line connecting the
							--start and end of the cone
	
	local l = math.sqrt(c^2 - h^2) 	--This is the length from our starting pos to where the height
									--line hits the center line
	
	local rad = fRadius * l / fDistance --This is the length of the cone radius at the given height
	
	--We now check if the entity is within the radius of the cone based on it's location along the center line
	if (vPos - v:NearestPoint(vPos)):LengthSqr() <= rad^2 then 
		
		table.insert(coneEnts, v) --Get in there you whore
		
	end
	
end

return coneEnts --Return the table of our entities

end
[/lua]
Correct me on any logic/math errors. I’m not great with math.

Hopefully I haven’t made too many mistakes, and perhaps someone will find this remotely useful.

No idea if everything is correct but either way you get an “i” for effort:v:

Thanks. Took me a while to figure out the cone part. I’m not great at math, so that one took some research.

The ents.FindInSphere probably compares the square of the length (x^2 + y^2) with the square of the radius because a square root is relatively slow.

Why would I use square roots in FindInSphere?

[lua](vPos - v:GetPos()):Length()[/lua]

Nice. Looks like you put allot of effort into this :stuck_out_tongue:

How is that using a square root?

Also it turns out the position checking is a bit more complex than I thought. I’ll be rewriting some of these soon. I’ll need to check whether or not all the points on the entity’s Bounding Box are inside too. If anyone would like to help by posting corrections I’d appreciate it. This is for the benefit of the community, not just me.

Pythagoras…

[editline]03:40PM[/editline]

To find the length of a vector you do Sqrt(x^2 + y^2 + z^2).

You’re talking about FindInCone, not Sphere.

No I am not, line 8 of FindInSphere.

It’s checking the length between the two points. I don’t see anything about squares. That is unless the Length function does that. If so I didn’t know.

That is what I am saying, the Length method uses Pythagoras to find the length of the vector (is there any other way of doing it?). Seeing as a square root is computationally expensive, it is more likely to be doing this:
[lua]if (vPos - v:NearestPoint(vPos)):LengthSqr() <= fRadius^2 then[/lua]

[editline]03:45PM[/editline]

Where LengthSqr returns x^2 + y^2 + z^2. (No Sqrt involved).

Thanks. I’ll fix that on all of them.

One other optimization, don’t perform fRadius^2 every time you check the distance. Do it once at the start of the function.

Nev said for FindInBox to work, I need to do a check like this:
[lua]
local vNearMin, vNearMax = v:NearestPoint( vMin ), v:NearestPoint( vMax );

	if( ( vNearMin &gt;= vMin && vNearMin &lt;= vMax ) || ( vNearMax &gt;= vMin && vNearMax &lt;= vMax ) ) then
	--Now we check to see if the nearest point on the entity's bounding box is inside of our lower/upper bounds.[/lua]

But apparently that won’t work in all cases, like if the entity is near one of the corners of the box. How can I fix that?

Yea.

So much geometry :ohdear:

I think the explanation of find in cone talks about half spheres, because it’s actually using half a find in sphere, to be cheaper than doing all the calculations for a cone?

I dont think it was meant to be run every second or something?

This thread is beautiful.