• ### What is your GameDev Story?

#### Archived

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

# damn planes

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

## 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 on other sites
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];
}

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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 12
• 15
• 11
• 12
• ### Forum Statistics

• Total Topics
634153
• Total Posts
3015844
×