Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

damn planes

This topic is 5583 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i''ve been trying to make a thing that tells if you''ve collided with the polygon or just the plane but everything i try doesn''t work. can someone please write a bit of code to show me using this stuff. the players x,y,z position before movement the players x,y,z position after movement the triangles 3 x,y,z positions and the triangles normal normalized. please i''ve tried using dot products to find the angles between the players position and the triangle but that failed.

Share this post


Link to post
Share on other sites
Advertisement
I could write some code here however I''m sure you won''t like it so I try to explain the most simple way to solve the problem.
I don''t know, in how far you''re used to mathematics so what I write may be a bit hard.
You have to describe the movement as a straight line and the triangle as a plane, as you already suggested.

Let me describe the plane as (Letters with a ''_'' after are vectors):

Plane = A_ + V1_ * f1 + V2_ * f2

A_ is one of the three points of the triangle, while V1_ and V2_ are vectors defining, how to reach the two other points from the A_.
Not to hard to figure out that you can easily reach any point on the plane by altering f1 and f2.

The straight line would be:

Straight Line = B_ + V_ * f

I suggest you use the old point as B_ and the difference between the new point and the old point as V_.
Again, you can find any point on the straight line by altering f.

Now, what we seek is a point that is an element of the straight line as well as the plane by equalizing the two constructs:

Plane = Straight Line
A_ + V1_ * f1 + V2_ * f2 = B_ + V_ * f

Since each vector has three elements you get the three functions:
A.x + V1.x * f1 + V2.x * f2 = B.x + V.x * f
A.y + V1.y * f1 + V2.y * f2 = B.y + V.y * f
A.z + V1.z * f1 + V2.z * f2 = B.z + V.z * f


Now you need a bit of math. To figure out wether there is a collision or not you need to get all of the three values f, f1 and f2 by solving the three functions.
If each of the values is below 0 and 1 there is a collision. Else not.
The formular will end up in being very very comples and you can easily make mistakes. So be careful.

Second method:
Matrices:

Let''s write the above function

Plane = Straight Line
A_ + V1_ * f1 + V2_ * f2 = B_ + V_ * f

in a different way:

V1_ * f1 + V2_ * f2 + V_ * -f = B_ - A_

Note, that it MUST be "-f" not "f"
Now, using some of our knowledge about matrices we transform the function to:

(V1.x V2.x V.x) (f1) (B.x - A.x)
(V1.y V2.y V.y) * (f2) = (B.y - A.y)
(V1.z V2.z V.z) (-f) (B.z - A.z)

or written a bit easier:

M * X_ = B_ - A_

This looks much better.
Everything we need to do now would be to somehow move the "M" to the other side and everything is solved.
However it''s a bit more tricky.

the M * X_ is a matrix-multiplication and follows its own rules.
the expression

M * X_ = B_ - A_

is equal to

inv(M)*(B_ - A_) = X_

where inv stands for "invert"
The matrix_invert is defined by the equaliation:

M * inv(M) = Identity
where Identity (you may have read this name while programming OpenGL) in the case of 3*3 is:

(1 0 0)
(0 1 0)
(0 0 1)

Ok, how to get the invert.
I would suggest you use the Gauss-Invertation-Method. There are more methods, maybe you should wait for some more replies on those. The theorie is a bit complex so you might want to just use the code:

(core)
dimension is the dimensions of the matrix to be inverted. In this case it''s 3.
INVERT_D_BUFFER is a global array used to store the temporary invertation-values, while m is the matrix being inverted.

/*first we matrix_copy the content of the origin matrix to the buffer
*/
__copy(m,m_height,INVERT_D_BUFFER,dimension,dimension,dimension);
/*the function is defines as
__copy(origin_matrix, origin_matrix_height, destination_matrix, destination_matrix_height, final_width, final_height)
*/
__eye(&INVERT_D_BUFFER[dimension*dimension],dimension);
/*
then we load the identity-matrix to the right part of the the invertation-buffer

after these two our invertation-buffer (in this case) looks like this:

V1.x V2.x V.x 1 0 0
V1.y V2.y V.y 0 1 0
V1.z V2.z V.z 0 0 1

following the linear direction (I don''t actually use two dimensional arrays...)

V1.x V1.y V1.z V2.x V2.y V2.z V.x ...

*/

for (unsigned line = 1; line < dimension; line++)
{
for (unsigned i = 0; i < line; i++)
{
double a = -INVERT_D_BUFFER[i*dimension+line]/INVERT_D_BUFFER[i*dimension+i];
for (unsigned j = 0; j < 2*dimension; j++)
INVERT_D_BUFFER[j*dimension+line]+=a*INVERT_D_BUFFER[j*dimension+i];
};
}
__clear(out,dimension,dimension);
/*
"out" is a pointer to the output-array, which should be at least 3*3 of size
__clear, sets all the values to zero
*/
for (unsigned i = 0; i < dimension; i++)
for (unsigned line=dimension-1; line < dimension; line--)
{
double a = 0;
for (unsigned inner=0; inner < dimension-line; inner++)
a+=INVERT_D_BUFFER[(inner+line)*dimension+line]*out[i*dimension+(inner+line)];
out[i*dimension+line]=(INVERT_D_BUFFER[(dimension+i)*dimension+line]-a)/INVERT_D_BUFFER[line*dimension+line];
}

And this is it already.
The returned array should be matrix-multiplied with the (B_ - A_)-vector and the result is a vector with the three cutting-factors.

matrix-sorting.
Ok, I cheated a bit to shorten things for explaination. The above invertation will not work everytime. It works perfect however causes zero-devisions in several cases.
That''s why you will need to sort the matrix before invertation:
The complete code for invertation is (complete):
T_dUndefMatrix is an alias for double*, an array-pointer to a double-array


bool __invertGaussSelect(T_dUndefMatrix m, unsigned m_height, T_dUndefMatrix out,unsigned dimension)
{
__copy(m,m_height,INVERT_D_BUFFER,dimension,dimension,dimension);
__eye(&INVERT_D_BUFFER[dimension*dimension],dimension);
double dom = __dominant(INVERT_D_BUFFER,dimension,dimension);

//dominant will calculate the dominant-value of the matrix
if (positive(dom)//positive will return the positive value of "dom"

unsigned pos=0,skip_cnt=0,jump_cnt=0,n_pos=0,in_cnt=0;
bool swap;
while (skip_cnt < dimension && jump_cnt{
pos%=dimension;
in_cnt++;
swap=false;
for (unsigned next = 1; next < dimension && positive(INVERT_D_BUFFER[pos*dimension+pos]) {
n_pos=(pos+next)%dimension;
if (INVERT_D_BUFFER[pos*dimension+n_pos] && INVERT_D_BUFFER[n_pos*dimension+pos])
{
__swapRow(INVERT_D_BUFFER,2*dimension,dimension,pos,n_pos);
pos=n_pos;
jump_cnt++;
skip_cnt=0;
swap=true;
}
};
for (unsigned next = 1; next < dimension && positive(INVERT_D_BUFFER[pos*dimension+pos]) {
n_pos=(pos+next)%dimension;
if (INVERT_D_BUFFER[pos*dimension+n_pos])
{
__swapRow(INVERT_D_BUFFER,2*dimension,dimension,pos,n_pos);
pos=n_pos;
jump_cnt++;
skip_cnt=0;
swap=true;
}
};
if (!swap)
{
jump_cnt=0;
skip_cnt++;
pos++;
};
};
if (positive(dom) < 1)
for (unsigned i = 0; i < dimension-1; i++)
{
for (unsigned j = i+1; j < dimension; j++)
{
if (positive(INVERT_D_BUFFER[i*dimension+j])>positive(INVERT_D_BUFFER[i*dimension+i]) && INVERT_D_BUFFER[j*dimension+i])
__swapRow(INVERT_D_BUFFER,2*dimension,dimension,i,j);
};
};
for (unsigned line = 1; line < dimension; line++)
{
for (unsigned i = 0; i < line; i++)
{
double a = -INVERT_D_BUFFER[i*dimension+line]/INVERT_D_BUFFER[i*dimension+i];
for (unsigned j = 0; j < 2*dimension; j++)
INVERT_D_BUFFER[j*dimension+line]+=a*INVERT_D_BUFFER[j*dimension+i];
};
}
__clear(out,dimension,dimension);
for (unsigned i = 0; i < dimension; i++)
for (unsigned line=dimension-1; line < dimension; line--)
{
double a = 0;
for (unsigned inner=0; inner < dimension-line; inner++)
a+=INVERT_D_BUFFER[(inner+line)*dimension+line]*out[i*dimension+(inner+line)];
out[i*dimension+line]=(INVERT_D_BUFFER[(dimension+i)*dimension+line]-a)/INVERT_D_BUFFER[line*dimension+line];
}

return true;
};

Ok, if you ask for it, I will give you the other functions as well. They are quite easy though.
I hope, you will understand at least a bit of it.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!