Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Determining whether a 3D point is within a square based pyramid

Author
Message
Michael P
19
Years of Service
User Offline
Joined: 6th Mar 2006
Location: London (UK)
Posted: 28th Dec 2010 21:08 Edited at: 28th Dec 2010 21:08
Link
I have a square based pyramid, and I know the coordinates of all 5 points of the pyramid (the top of the pyramid and the 4 corners of the base). The pyramid can be rotated at any angle in 3D space and can be of any dimensions.

I want to know how I can determine whether a point is within this pyramid using mathematics.

This pyramid represents the area which the camera can see where the top corner is the camera and the base is at the end of the camera's range. It is generated by (more information on this is here):
- Determining the positions of the 4 corners of the base when the camera is positioned at 0,0,0 facing at angles 0,0,0.
- Generating a left handed ZYX rotation matrix from the angles that the camera is facing.
- Transforming each base corner's position vector by this rotation matrix.
- Adding the camera's position vector to each base corner's vector.

Here is a picture that might help:


Once again this is in aid of solving this problem; I am now very close to finding a solution!

DarkNet - multiplayer plugin

Attachments

Login to view attachments
Back to top
Profile PM Email
Phaelax
DBPro Master
22
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 28th Dec 2010 22:01 Edited at: 28th Dec 2010 22:02
Link
Easiest way I can think of is to check each plane that makes up the pyramid against your 3D point to see which side of the plane the point lies. Doing this we can determine if its enclosed by all 4 sides (5 counting the base)

First you need to calculate the normal of each plane. For each of the 4 sides, you have 3 points we'll call A, B, C. The cross product of vectors AB and AC will create a vector perpendicular to the plane. You might need to normalize this vector for the next part to work, I can't remember for sure exactly.

Next, take your 3D and calculate the dot product with the normal of each side. If the dot product is positive on all 5 planes, then the point is outside the pyramid. If its negative for each one, then the point is inside.
I may have the positive and negative switched around, it depends on the rotational order the points, see the attached pic. It's important that each side follows the same order of ABC.



"Only the educated are free" ~Epictetus
"Imagination is more important than knowledge..." ~Einstein

Attachments

Login to view attachments
Back to top
Profile PM Email Website
Sven B
20
Years of Service
User Offline
Joined: 5th Jan 2005
Location: Belgium
Posted: 28th Dec 2010 22:14 Edited at: 28th Dec 2010 22:15
Link
By using the view matrix and projection matrix of the camera you're using, it's quite easy to do this though.

Let's say V = view matrix and P = projection matrix.
If Y = X * V * P, where X is the vector you want to test, then what you need to know is right in there.

If the point is in the pyramid, then it means the camera can see it (which is my guess of what you want to do), so you basically need to check whether or not Y.x and Y.y are in the 'screen' (depending on which width/height you pick), and you also need to check the Z-depth after projection.

DBP can build all these matrices for you using the 3D math commands.

Extra info on this:
http://msdn.microsoft.com/en-us/library/bb206269(v=VS.85).aspx

Sven B

Back to top
Profile PM Email
OldPMan
TGC Store Seller
16
Years of Service
User Offline
Joined: 10th Aug 2008
Location:
Posted: 28th Dec 2010 22:47
Link
I can only assume that there is such an option.
By checking the distance from the point to all vertices of the pyramid.
can be

.....already beside..... for all
Back to top
Profile PM Website
Diggsey
19
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 28th Dec 2010 23:32
Link
The viewing region is actually a frustum rather than a pyramid (as there is a near plane as well as a far plane). Check out this code snippet from LiT which shows how to generate the six planes of the frustum from a camera, and also how to check if different shapes are inside it. (Remember, a point is just a sphere with a radius of zero)

http://forum.thegamecreators.com/?m=forum_view&t=67369&b=6

[b]
Back to top
Profile PM Email Website
Michael P
19
Years of Service
User Offline
Joined: 6th Mar 2006
Location: London (UK)
Posted: 29th Dec 2010 19:15 Edited at: 29th Dec 2010 19:17
Link
Thanks guys, I used Phaelax's method and it seems to work well!

I formed 4 triangles (left, right, bottom and top) and calculated their distance from the point being checked. If the left triangle distance is positive, right triangle distance is negative, top triangle distance is negative and bottom triangle distance is positive then the point is inside the square based pyramid.

The distance function is (C++ code):
float distance = (GetEquationalRepresenationD() - n->GetInnerProduct(Q)) / n->GetDistance();

GetEquationalRepresenationD refers to converting from the parametric to equational representation of the plane and is the letter d in the formula: ax1 + bx2 + cx3 = d. n is the normal form of the plane and Q is a point within the plane.

@ Diggsey
This is true but when the near value is 1 (which it is in my case) it is pretty much a square based pyramid.

DarkNet - multiplayer plugin
Back to top
Profile PM Email
Neuro Fuzzy
17
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 29th Dec 2010 21:07 Edited at: 29th Dec 2010 21:29
Link
svenB... I'm really confused now whether to use a column or a row vector... I had always used column vectors (not that I'm great with 3d matrix math).

[edit]
well this code kinda works

but... i don't get it :S

Back to top
Profile PM Email
Sven B
20
Years of Service
User Offline
Joined: 5th Jan 2005
Location: Belgium
Posted: 29th Dec 2010 22:20 Edited at: 30th Dec 2010 09:35
Link
Neuro Fuzzy,

When changing between the two, just inverse the order of matrix multiplication. I'm used to working with column vectors too, but Direct3D works with a row vector. I'm also used to working with a Right Handed axis having the Z-axis pointing up, but Direct3D likes a Left Handed axis having the Y-axis pointing up better.
Really, doesn't make things easier .

Anyways, here's an example on how to get if a vector is in the frustrum or not:


Cheers!
Sven B

Back to top
Profile PM Email
Neuro Fuzzy
17
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 29th Dec 2010 23:36 Edited at: 30th Dec 2010 00:18
Link
[edit]
I'm really confused, I think I've been doing some really stupid stuff with DBPro rotation matrices - that's what you get when you educate yourself on the internet xD
Is it true that "multiply matrix4 ret, a, b" actually says ret=A*B and not ret=B*A? I think that I was... trying... to fool myself into thinking I was using column vectors, and to get the right results, I had to mess up every multiplication operation like that, and fooled myself into thinking multiply matrix4 switches A and B around? (earlier if you had hasked me I would have said ret=B*A)

Arrgh, I feel stupid now... Uhh could you please confirm why I think I've been stupid is correct? I'm just not sure any more X_X

Back to top
Profile PM Email
enderleit
17
Years of Service
User Offline
Joined: 30th May 2007
Location: Denmark
Posted: 30th Dec 2010 01:31
Link
I know nothing of matrix math, but just thought I'd point out that in normal math it doesn't matter which order you multiply two items...

A*B = B*A

Don't know if there's something different in matrix math...

- Martin Enderleit
http://sites.google.com/site/menderleit
Back to top
Profile PM Email Website
Diggsey
19
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 30th Dec 2010 02:04
Link
There is

Order matters when multiplying matrices, ie. A*B ≠ B*A

[b]
Back to top
Profile PM Email Website
Neuro Fuzzy
17
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 30th Dec 2010 02:08
Link
OOh, right, I didn't say it yet... what I thought I had figured out in my post is wrong, "multiply matrix4 ret, a, b", does actually set ret=b*a. I've just been thinking some weird stuff and I've had weird consequences in my programs that confused me. Uhhh It's all clear to me now, I've just been confused ._.

Back to top
Profile PM Email
Sven B
20
Years of Service
User Offline
Joined: 5th Jan 2005
Location: Belgium
Posted: 30th Dec 2010 10:10 Edited at: 30th Dec 2010 10:12
Link
Hi NeuroFuzzy,

First of all: I made a mistake in my code last time. I edited it.
The line
divide vector4 3, z vector4(3) + Zn
had to be
divide vector4 3, w vector4(3)
It was a bit late yesterday...

Quote: "Is it true that "multiply matrix4 ret, a, b" actually says ret=A*B and not ret=B*A? I think that I was..."


Multiply matrix4 ret, A, B means ret = A * B if you're working with row vectors.
Though I advise you to 'think' in row vectors, it is not strictly necessary. Why?
You see, the transposed of a matrix multiplication is the multiplication in reverse order of the transposed matrices.
A * B * X = X' * B' * A'

This allows you to have a certain degree of freedom:

So if you were thinking to do X = A * B * X
X = column vector
B = first transformation
A = second transformation
Then it would translate to (using ret = second * first)


And if you were thinking X = X * B * A (which is the same transformation, but with a row vector where B and A are now transposed)
X = row vector
B = first transformation
A = second transformation
Then it would translate to (using ret = first * second)

which is clearly the same.

So basically, it doesn't have that big of an impact on how you interpret it, but you have to stick with one. However, if you use row vectors, the commands are more logical.

When you want to use column vectors
transform ****** Y, X, A changes to Y = A * X
multiply vector4 C, A, B changes to C = B * A
subtract matrix4 C, A, B does not change and stays C = A - B
get matrix4 element(Mat, E) now 'counts' downwards. E = 2 is element (3, 1), E = 4 is element (1, 2)
All other commands stay the same (they're either commutative or the parameters describe what it should be).

When you want to use row vectors, everything is pretty much as you would suspect:
transform ****** Y, X, A is Y = X * A
multiply vector4 C, A, B is C = A * B
subtract matrix4 C, A, B is C = A - B
get matrix4 element(Mat, E) counts to the right. E = 2 is the element (1, 3), E = 4 is element (2, 1).

So if you work with row vectors, you basically avoid a few problems, but technically it's possible to work with column vectors as well.

Cheers!
Sven B

Back to top
Profile PM Email
C0wbox
18
Years of Service
User Offline
Joined: 6th Jun 2006
Location: 0,50,-150
Posted: 30th Dec 2010 12:16 Edited at: 30th Dec 2010 12:19
Link
In case anyone wants a speedier option that won't cull everything exactly but still do a reasonable job you could have a dummy object (a 3D point) in the centre of the pyramid of view (exactly half way between the camera and the camera's range) and check simple vector distances to that point. - This would surely be faster than checking if something lies exactly within a pyramid as that would require 5 checks for each object instead of 1.

The maths being if you had 100 objects to check, that's 500 checks per loop, but with a dummy object in the middle of the camera's view that's only 100 checks per loop. - O(n) instead of O(5n)

Obviously there will be a bigger margin of error the greater the cameras range as the sphere of permitted objects will increase but I'd guess for the saved performance in the checking you could allow some models to creep into the render area outside the edge of the screen.

I drew all over the original diagram to try and illustrate what I mean but it's probably better to just read what I said carefully.


EDIT:
Re-reading the first post I realise this method may actually be better than 5 times faster as it wouldn't need to calculate things like the positions of the points in the pyramid, it's just calculating one point.

Attachments

Login to view attachments
Back to top
Profile PM Email Website
Green Gandalf
VIP Member
20
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 30th Dec 2010 15:17
Link
Quote: "check simple vector distances to that point"


How would that give just one check?
Back to top
Profile PM Email
C0wbox
18
Years of Service
User Offline
Joined: 6th Jun 2006
Location: 0,50,-150
Posted: 30th Dec 2010 16:11 Edited at: 30th Dec 2010 16:15
Link
!!!

I don't know, I don't do that kind of 3D maths usually but surely it's quicker (regardless of whether it's 1 check) to calculate the distance between 2 points than to calculate whether a point is on 1 side of 5 different planes?

It must be something along the lines of 3D trigonometry between the centre point and every object in the playarea and determining which lengths are within the range cameraview*0.5

(I just said vector because I was picturing lines going from that centre point to each object and checking the lengths of those lines to determine if they were inside the view sphere - I don't actually know if it would be practical to use vectors in this kind of application - I'd just use variables and 3D trigonometry) :S

Back to top
Profile PM Email Website
Michael P
19
Years of Service
User Offline
Joined: 6th Mar 2006
Location: London (UK)
Posted: 30th Dec 2010 16:25
Link
It is alot faster (I have just implemented it)!

Firstly we don't have to generate the square based pyramid, but this isn't actually that expensive because it only needs to be done once and can be reused for checking any number of objects.

The main thing is that the distance check is a simple case of Pythagoras which only needs to be done once per point. With the more precise method, checking the distance between a plane and a point is more expensive, and we have to do this 4 times (once for each plane).

DarkNet - multiplayer plugin
Back to top
Profile PM Email
Green Gandalf
VIP Member
20
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 30th Dec 2010 16:30
Link
Quote: "but surely it's quicker (regardless of whether it's 1 check) to calculate the distance between 2 points than to calculate whether a point is on 1 side of 5 different planes?"


I'm sure it is but what does that have to do with the pyramid check? Which two points are you talking about?
Back to top
Profile PM Email
C0wbox
18
Years of Service
User Offline
Joined: 6th Jun 2006
Location: 0,50,-150
Posted: 30th Dec 2010 16:45
Link
xD I'm not the worlds best at explaining things, I may have referred to a point but meant a different one.

What I mean overall is:

Checking the distance between each object and the point directly in front of the camera (at half the camera's range away from that camera) would be faster than checking whether each object is on 1 or the other side of 4 or 5 planes.

I did attempt to do some maths to calculate precisely how much faster it would be but given that the maths for checking distance between to 3D points is somewhat different to checking whether a point lies on 1 or the other side of a plane I just gave up and basically said "Yeah it'll be faster but I'm not sure how much faster."

The connection between the pyramid check is that my method will use the same area (if implemented correctly) and a little bit of extra area to achieve much the same effect.

The confusion is going to be somewhere in my explanation as I'll sometimes reference objects as separate points but should really keep calling them objects and only say point when I'm talking about the one positioned in front of the camera.

xD If that explanation still sucks as much as I do I'll code an example or ask Michael P to explain it.

Back to top
Profile PM Email Website
Green Gandalf
VIP Member
20
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 30th Dec 2010 17:23
Link
My main point is that you are not checking whether the point is inside the pyramid. Depending on the camera's FOV there could be a big difference between the simple sphere check (which is what I think you are doing) and the correct pyramid check.

Your check is certainly faster - but it's not checking the right thing.

Perhaps I've misunderstood what you are doing?
Back to top
Profile PM Email
C0wbox
18
Years of Service
User Offline
Joined: 6th Jun 2006
Location: 0,50,-150
Posted: 30th Dec 2010 17:32
Link
Yeah I tried to say that in my first sentence:
Quote: "won't cull everything exactly but still do a reasonable job"


My method isn't doing the same thing but offers a similar and faster alternative.

It gets more inaccurate the larger the camera range but it's checking far less each loop so it's a bit of a compromise.

Back to top
Profile PM Email Website
Green Gandalf
VIP Member
20
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 30th Dec 2010 17:39
Link
Quote: "it's a bit of a compromise"


A big bit?
Back to top
Profile PM Email
C0wbox
18
Years of Service
User Offline
Joined: 6th Jun 2006
Location: 0,50,-150
Posted: 30th Dec 2010 17:48 Edited at: 30th Dec 2010 18:07
Link
It depends on how accurate you want it to be.

If you just want to cull stuff that's behind the camera it's fine.

If you do actually need only what is in the camera's view and nothing else, it isn't.

I'm just giving an alternative here for a speed boost in game dev. - You don't need to be as accurate as a pyramid or frustum cull in a game in my experience so a spherical cull of this type would do the job just nicely.

Here's a diagram of the inaccuracies (in green) but the two triangular shaped ones near the base of the pyramid can be removed just by making the sphere bigger and further forward (dotted blue line).


Attachments

Login to view attachments
Back to top
Profile PM Email Website
Green Gandalf
VIP Member
20
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 30th Dec 2010 22:05
Link
Maybe, but that doesn't answer the question Michael P was asking in his first post.

I've just noticed Michael P's last comment that it is indeed faster (despite it's inaccuracies). That's odd because I would have thought the few extra numerical checks would be outweighed by the loss of culling. Perhaps that isn't relevant in what he was doing?
Back to top
Profile PM Email
C0wbox
18
Years of Service
User Offline
Joined: 6th Jun 2006
Location: 0,50,-150
Posted: 30th Dec 2010 23:07 Edited at: 30th Dec 2010 23:14
Link
Quote: "Maybe, but that doesn't answer the question Michael P was asking in his first post."


I know, I know, but the thread had been more or less solved so I thought I'd change the topic slightly to performance in game development rather than specific maths and offer people a faster alternative for an actual application rather than a maths question. - It wasn't exactly worth me making another thread just to tell people an idea I thought up based on this thread. (And I had no code to put it in the codebase.)

So I just put it up there for people to make of it what they liked.
And it would seems my prediction that Michael P wanted a fast camera culler was correct as he's implemented it and it works faster.

Back to top
Profile PM Email Website
Green Gandalf
VIP Member
20
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 31st Dec 2010 02:56
Link
You're probably right.
Back to top
Profile PM Email
Back to top

Login to post a reply

Server time is: 2025-05-28 03:47:47
Your offset time is: 2025-05-28 03:47:47