next »

[pgil]

This is probably really simple, but unfortunately I haven't been keeping up on my math skills.

Let's say I have a mountain in my game. The mountain is a pyramid shape with a rectangular base. Assuming I know the height, and the dimensions of the base, how would I find out whether a point at x,y,z is inside that pyramid?

[Entar]

There are probably a few methods for this, but one way would be to do a typical test by getting planes for each of the sides of the pyramid and testing to see if the point is behind all of them. If it is, then it is inside the pyramid.

[pgil]

I guess what I'm really looking for is a formula that I can test in a few if statements.

[Ishi]

(assuming here y is up)

You have the y position you want to check, and the height h of the pyramid, and base b of the pyramid. Of course if y < b or y > h then it is below or above the pyramid.

The next step is to find if the position is inside the pyramid on the horizontal plane.

At the base height, you could find if the point is inside the pyramid by comparing it with the base rectangle, centred at bx,bz of width and depth w,d.

The horizontal cross section of the pyramid at any point is just a scaled down version of its base, ranging from the full base at the bottom to nothing at the top.

Since the y position is in the pyramid's vertical range (b->h), it can be used to find a value between 0 and 1 for how high up the mountain it is; r = (y - b) / (h - b). This can be used as a scaling value for the pyramid's base size to calculate the size of the cross section at the height you are checking.

So the rectangle to check against is still centred at bx,bz, but the width and depth are (r * w),(r * d).

If that doesn't make sense just tell me. I usually end up rambling or being patronising when I'm trying to explain things clearly.

[Martin 2BAM]

Calculate the dot product between the point to test against all the normals of the pyramid faces.
If all results are negative, the point is inside.

To calculate the normal of a pyramid face you use the cross product

Code:

normal = v1 x v2 (v1 and v2 define the triangle)

let's say you take the top point of the pyramid as a reference, then for each point in the base:

Code:

for(i=0; i<4; i++) {
  v1 = pyramid[x].basePoint[i]         - pyramid[x].topPoint;
  v2 = pyramid[x].basePoint[(i+1) % 4] - pyramid[x].topPoint;
  pyramid[x].normal[i] = crossProduct(v1, v2); 
}

(also you should precache the normals for a speed ups)

and then check with the dot product (fix pointToTest to the reference point, the top point)

Code:

bool pointInside=true;
for(i=0; i<4; i++) {
  if(dotProduct(pointToTest - pyramid[x].topPoint, pyramid[x].normal[i]) >= 0) {
     pointInside=false;
     break;
  }
}

(you should also check the base, if no "hitting ground" checks are done)

I think this should work. You can find code to dot and cross product on the web.

Regards
-Martín

[Dacke]

I didn't read Ishi's entire explanation, but if he's saying what I think he's saying his method should be cheaper. But the Entar/nitram_cero solution is more general as it applies to all convex bodies.

[Martin 2BAM]

I don't think there is a big performance difference between them (other than the memory consumed in caching the normals).
Each interation check there uses simple operations (subtraction, multiplication and a comparison)

[pgil]

Ah... Lots to think about here, but this:

The horizontal cross section of the pyramid at any point is just a scaled down version of its base, ranging from the full base at the bottom to nothing at the top.

...is a really good explanation
I think I have a good idea of how to do this now.

EDIT:
Ok, here's some quick and dirty GML code. I haven't tested this at all, but I figured I'd share it anyway... because I left this page open in my browser. 

Code:

//scr_collision_pyramid(xwidth,ywidth,height,other.x,other.y,other.z)

//xwidth = base width (x-axis)
//ywidth = base width (y-axis)
//height = height of pyramid from ground
//other.x,y,z = x, y, and height of colliding object from ground

cross_section_x = abs(height-z)*xwidth
cross_section_y = abs(height-z)*ywidth

if other.x > x-(.5*cross_section_x) && other.x < x+(.5*cross_section_x) &&
other.y > y-(.5*cross_section_y) && other.y < y+(.5*cross_section_y) {
   return true        
}
else {
   return false
}

In this code, x and y are horizontal and z is vertical.

[Martin 2BAM]

I don't want to sound like a douche, but I didn't knew that the pyramid was regular (the pointy vertex is exactly on the axis given by the center of the base).

If the pyramids were not regular (i.e. "bent"), the cross section approach wouldn't work.

[pgil]

Well, a skewed pyramid might be helpful too. The actual mountain models are more detailed than just simple pyramids--I just want to see if I can get away with less detail for the collisions. 

[Dacke]

I don't want to sound like a douche, but I didn't knew that the pyramid was regular (the pointy vertex is exactly on the axis given by the center of the base).

If the pyramids were not regular (i.e. "bent"), the cross section approach wouldn't work.

Otherwise it wouldn't be pyramids, right?
http://en.wikipedia.org/wiki/Pyramid_%28geometry%29

But it's always nice with more general algorithms and plane-testing will cover skewed pyramids as well.

[Ishi]

If they were skewed you could still just offset the centre of the rectangle as you get higher up the pyramid. If the base edges aren't axis-aligned though then vectors are definitely required.

[Zaphos]

Otherwise it wouldn't be pyramids, right?
http://en.wikipedia.org/wiki/Pyramid_%28geometry%29

I don't see anything on that page that says the apex has to be centered ...

[Dacke]

Otherwise it wouldn't be pyramids, right?
http://en.wikipedia.org/wiki/Pyramid_%28geometry%29

I don't see anything on that page that says the apex has to be centered ...

I guess not. My (poor) "proof" was that pyramids with non-centric apexes weren't mentioned. I don't think I've ever heard of a skewed pyramid being called a pyramid. But that doesn't prove anything. So.. does anyone know if the apex has to be centred or not?

[Zaphos]

Non-centered apexes are kind of mentioned in the section on volume, where they say "This works for any location of the apex, provided that h is measured as the perpendicular distance from the plane which contains the base."  Also they would probably not feel the need to say "If the base is a regular polygon and the apex is above the center the polygon" if the apex were always above the center of the polygon.

[Martin 2BAM]

I don't want to sound like a douche, but I didn't knew that the pyramid was regular (the pointy vertex is exactly on the axis given by the center of the base).

If the pyramids were not regular (i.e. "bent"), the cross section approach wouldn't work.

Otherwise it wouldn't be pyramids, right?
http://en.wikipedia.org/wiki/Pyramid_%28geometry%29

But it's always nice with more general algorithms and plane-testing will cover skewed pyramids as well.

MathWorld is better for this stuff:
http://mathworld.wolfram.com/Pyramid.html

A right pyramid is a pyramid for which the line joining the centroid of the base and the apex is perpendicular to the base. A regular pyramid is a right pyramid whose base is a regular polygon. An n-gonal regular pyramid...

Anyway I was mistaken. I was calling a "right" pyramid, "regular".
But pyramid is a broad term: A pointy thing with a planar base.

[Dacke]

Thank you
For some reason I can't seem to read math in English properly. I'm fluent in both English and Math, but the two combined tend to throw me off.

[Martin 2BAM]

No problem, we all learned something new 

Regards
-Martín

[BadgerManufactureInc]

You could kick off with a Johnson solid (pyramid with single edge length equilateral faces).  Once that's been implemented proceed onto non uniformity, and keep referring to Euclid's window.

As ever keep it simple first with code, and think laterally, have patience and don't be afraid to apply trial and error.  1 significant step forward in 1 week is better than 10 hastily added functions.

Seriously, Euclidean geometry and De Cartian maths too, isn't a mandatory part of high level maths for no reason.

Archimedes also has some light to shed on it, his material is good reference for physics based functionality.

It is a shame that 99% of their material was burnt in Alexandria though.

If only...