ents.FindInWhatever: Explained

[Grea$eMonkey]

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 [b][url=wiki.garrysmod.com/?title=Ents.FindInBox]Ents.FindInBox [img]http://wiki.garrysmod.com/favicon.ico[/img][/url][/b]. 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 [b][url=wiki.garrysmod.com/?title=Ents.FindInSphere]Ents.FindInSphere [img]http://wiki.garrysmod.com/favicon.ico[/img][/url][/b]. 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.

[quote=Wikipedia]A circle is a simple shape of Euclidean geometry consisting of those points in a plane which are equidistant from a given point called the center. The common distance of the points of a circle from its center is called its radius.[/quote]
[img]http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/CIRCLE_1.svg/200px-CIRCLE_1.svg.png[/img]

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 [i]inside[/i] 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: [b][url=wiki.garrysmod.com/?title=Ents.FindInCone]Ents.FindInCone [img]http://wiki.garrysmod.com/favicon.ico[/img][/url][/b]. 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.
[img]http://accad.osu.edu/~pgerstma/class/vnv/resources/info/AnnotatedVrmlRef/Images/Cone.gif[/img]
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.
[quote=Yahoo Answers]If h is the height of the cone and r is the radius of the base, then:
r1/h1 = r/h --> r1 = rh1/h, where:
r1 is the new radius and h1 is the new height.[/quote]

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:
[img]http://img684.imageshack.us/img684/4526/cone1.png[/img]
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 [img]http://mathcentral.uregina.ca/QQ/database/QQ.09.01/bat1.1.gif[/img].

Since the area of a triangle is half the base times the height (a = [i]½bh[/i] ), 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]

[ralle105]

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

[Grea$eMonkey]

[QUOTE=ralle105;19913624]No idea if everything is correct but either way you get an "i" for effort:v:[/QUOTE]

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

[NullPoint]

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.

[Grea$eMonkey]

[QUOTE=NullPoint;19914665]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.[/QUOTE]

Why would I use square roots in FindInSphere?

[NullPoint]

[QUOTE=grea$emonkey;19914853]Why would I use square roots in FindInSphere?[/QUOTE]

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

[MGinshe]

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

[Grea$eMonkey]

[QUOTE=NullPoint;19914901][lua](vPos - v:GetPos()):Length()[/lua][/QUOTE]

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.

[NullPoint]

[QUOTE=grea$emonkey;19914947]How is that using a square root?[/QUOTE]

Pythagoras...

[editline]03:40PM[/editline]

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

[Grea$eMonkey]

[QUOTE=NullPoint;19914952]Pythagoras...[/QUOTE]

You're talking about FindInCone, not Sphere.

[NullPoint]

[QUOTE=grea$emonkey;19914959]You're talking about FindInCone, not Sphere.[/QUOTE]

No I am not, line 8 of FindInSphere.

[Grea$eMonkey]

[QUOTE=NullPoint;19914966]No I am not, line 8 of FindInSphere.[/QUOTE]

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.

[NullPoint]

[QUOTE=grea$emonkey;19914994]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.[/QUOTE]

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

[Grea$eMonkey]

[QUOTE=NullPoint;19915001]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).[/QUOTE]

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

[Jinto]

[QUOTE=NullPoint;19915001]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).[/QUOTE]

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

[Grea$eMonkey]

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 >= vMin && vNearMin <= vMax ) || ( vNearMax >= vMin && vNearMax <= 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?

[NullPoint]

[QUOTE=Jinto;19915094]One other optimization, don't perform fRadius^2 every time you check the distance. Do it once at the start of the function.[/QUOTE]

Yea.

[3mpty]

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?

[commander204]

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

[CowThing]

This thread is beautiful.

[Chad Mobile]

I crapped my pants reading that math stuff :saddowns:

[Grea$eMonkey]

[QUOTE=Empty_Shadow;19924581]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?[/QUOTE]

Possibly, but I don't think using that method would be as accurate as this, since this one actually checks within the cone radius of any given point along its axis. These are just speculations though.

[3mpty]

Well do a comparison and see if it works the same as ents.GetInCone :D

[zenby]

isn't the included ents.FindInCone broken?

[Grea$eMonkey]

[QUOTE=ZenX2;19971182]isn't the included ents.FindInCone broken?[/QUOTE]

Used to be, but not anymore.

[editline]03:31AM[/editline]

That is if you mean by broken, crashing the game every time you attempt to use it.