3D Collision Detect Code

[Nigh™a®e]

For over 2 years im learning directX in VB.

Now im able to create a small game that loads a terrain, skybox, objects, full camera movements, fog, light effects, particle engine, console with scripting engine.

The next step in the development process is something i dont know how to do, after days of research and testing, only a bad result came out. The colision detection code.

To know the height of the camera and object, i need to know the hieght point of the exact x, y location im at.

It all starts with a square. Lets say our square is 100 * 100 and starts at 0 * 0

All 4 corners of the square have and different heightpoint (Z).
This means the height somewhere inside the 100 * 100 square is dynamic and has to be calculated.

Now the real question.
If all 4 corners are at a different height, then what is the height point inside that square at 30 * 70 (x=30, y=70)

The following points of the square are:

P(0).X = 0
P(0).Y = 0
P(0).Z = 3
P(1).X = 100
P(1).Y = 0
P(1).Z = 5
P(2).X = 0
P(2).Y = 100
P(2).Z = -8
P(3).X = 100
P(3).Y = 100
P(3).Z = 7

Player.X = 30
Player.Y = 70
Player.Z = ???

I managed to work something out that works on squares with corners of 90degrees. I calculates with triangles.

Using the P(0).X -> P(1).X line as length
Using the diffence of height of P(0).Z and P(1).Z as the height of the traingle
Using the Player.X as the position.

Using (Height * Position) / Length gives the exact point of height at Player.X with player.Y = 0

The same can be done on the bottom of the square to calculate the height point on the other side of the square.

Doing the same with the two calculated height point and using Y as position this time, should give the exact heightpoint of the players location.

I tried this code and it seems to look good. Only sometimes i end up bollow the terrain. But maybe thats just a little error in my script, cant find it at the first moment. Also if this code do the trick, it will only work on squares or rectangles with corners of 90 degrees.
I will review this code later this week and come back with the result of it. If the bug is fixed i will add the code to this topic (dont have it with me now, cause im at work) There is a little extra code next to the triangle calculation. to create a triable, you first need to find out what are the highest coordinates to calculate the L, H, P values. We want to work only with positive numbers (or is this my bug)

Once this code work i need to be able to upgrade the code for square with dynamic corners (so not allways 90 degrees)

==========

If you know any other way to get the collision detection, pls let me know.
You can reply here, contact my by ICQ (59781659), MSN ([email protected]) or Mail ([email protected])

Greets Nightmare

p.s. If you think you can help us with the game on any other way, do not wait to contact us.

[kedaman]

The camera could be assumed to be a sphere (so you don't go too close) and the
square could be considered two triangles, say of a square (A,B,C,D) you have
(A,B,C) and (B,C,D)

To test if the sphere collides or is in range of the vertexes, test the distance between the camera and vertex |C-V| for each vertex, if its smaller than the sphere radius |C-V|<R
To test if the sphere collides with the edges take the scala product for each edge (V1,V2) and the camera and one of the vertex in the edge say V1. now you have shortest distance to the edge from the sphere, test again if its smaller than the sphere radius (v1-V2).(C-V1) < R for each edge of course.
To test if the sphere collides with the plane inside the triangle, take the scalar trippleproduct between the plane (this is the shortest distance between the camera and the plane) and test if its smaller than the sphere radius (V1-V2)x(V1-V3).(V1-C) < R

reducing the formulas with vectors here into scalar algebra remember that calculating squareroots is always slower for your computer than calculating the second power.
You could check out some geometry and vector calculus pages or even more specifical collision detections, there's loads on the net.

[Zaei]

Or you can use interpolation...

float TOW_HeightMap::m_cosInterpolate(float a, float b, float s)
{
	float ft = s * 3.1415927f;
	float f = float(1.0 - cos(ft)) * 0.5f;

	return  a*(1.0f-f) + b*f;

}

float TOW_HeightMap::m_intNoise(float x, float y)
{
	int integer_X    = int(x);
	float fractional_X = x - integer_X;

	int integer_Y    = int(y);
	float fractional_Y = y - integer_Y;

	
	float v1, v2, v3, v4;
	v1 = GetRawHeight(integer_X, integer_Y);
	v2 = GetRawHeight(integer_X+1, integer_Y);
	v3 = GetRawHeight(integer_X+1, integer_Y+1);
	v4 = GetRawHeight(integer_X, integer_Y+1);

	
	float i1 = m_cosInterpolate(v1 , v2 , fractional_X);
	float i2 = m_cosInterpolate(v3 , v4 , fractional_X);

	return m_cosInterpolate(i1 , i2 , fractional_Y);

}

This is the code I use. GetRawHeight() gets a value straight out of my heightmap table, and using m_cosInterpolate, finds the height of the terrain at a given point. I use a cosine interpolation for smoother terrain. You could replace it with a linear interpolation function without any difficulty.

And yes, I know its C++, the algorithm is the same.

Z.

[kedaman]

Z: I'm a bit confused in what your approach is suppose to do, could you elaborate a bit?

[Zaei]

Grabs the 4 height points that surround the point that you want to find, and then interpolates across them using the fractional parts of the point you want to find.

Z.

[Nigh™a®e]

Thanks both

I gone try the code of Zaei first, its looks a little like the code i have for now (worked a lot of hours on it this weekend)

Trought the 4 height Points of a land tile, i think it should work with this code. Later i gone try the collision detection strategy of Kedaman for detecting object collisions.

I created a little collision detect code for my terrain this weekend.
The code works as:

Split the tile into 2 triangles.
Detect what triangle the object is in.
Calculate the heightpoint of the triangle

Now the only problem i have, is that sometimes my return value of the height is a positive number or a negative number, depending on the position of the tile i am.

I will keep you updated about this.

Greet Nightmare

[kedaman]

Perhaps I have miunderstood the problem, yes my code is for object/camera collision, about object/camera and object/object, especially the latter if you have large amounts of objects you'd have to test the amount of permutations between them, instead you coud narrow them down using quad or oct-tree's.

Z: I'm guessing that is for detecting the height in terrain correct? If so then how is this solving the situation with say each pair of diagonal corners are in the same height?

[Zaei]

Originally posted by kedaman
Perhaps I have miunderstood the problem, yes my code is for object/camera collision, about object/camera and object/object, especially the latter if you have large amounts of objects you'd have to test the amount of permutations between them, instead you coud narrow them down using quad or oct-tree's.

Z: I'm guessing that is for detecting the height in terrain correct? If so then how is this solving the situation with say each pair of diagonal corners are in the same height?

Yep, height on a terrain.

Just as an example, lets take a square with each diagonal at the same height (though different for each diagonal), and the query point being the center of the square. Using linear interpolation, your final point would be the average of the two diagonal heights. It IS an approximation =).

Z.

[kedaman]

what sort of surface would that approximation fit then

[Zaei]

Originally posted by kedaman
what sort of surface would that approximation fit then

One not built of triangles =).

Z.

[Nigh™a®e]

Yes, the terrain is build out of triangles.

Each tile has 2 traingles.
Like in the first post

P0 - P1 - P2 = Tri1
P2 - P3 - P0 = Tri2
P0 - P1 - P2 - P3 = Tile or Tri1 & Tri2

I found an example on the internet for calculating the heightpoint of a triangle. Its using vectore normalization and things like that.


Im not realy understanding what the code realy does, but its half working.
The problem for now is, 1 of the triangles returns a positive value and the other triangle returns a negative value. Also when im past the half of the tile (applied on both triangles) the positive and negative value swaps.

So this give the effect when im on the south part of the tile, the camera height is set by the height of the ground, so it looks good.
The moment i enter the norther part of my tile, the values swaps and im walking under the terrain instead of above.

This is a little bug i need to fix. Maybe it has something to do with the point positions.

As for the second triangle i use 2 -> 3 -> 0 and for the first 0 -> 1 -> 2

I should try if i put second tri as 0 -> 3 -> 2 or 3 -> 0 -> 2
This maybe could make a change. Im not sure.
First im kind of rewritting my code. After trying many things the engine got bugged, it slowed down and my 2D Font and 2D pictures as the console, map and compass where disapeared.
Currenty im getting 125 - 150 FPS in windowed mode using software rendering. Normaly the Framerate should be higher but im running it on .NET Server and it doesnt support my graphic card so i could test yet in HAL mode.

Screenshots will be avaiable soon. I created a little forum for the game.

http://www.nightmare-products.com/ub...ultimatebb.cgi

Everybody is welcome there an i will update the board daily with the newest dev updates. The board and site are still under contruction, so it can be that some things dont work properly or give errors.

Greets Nightmare

btw: If i knew before that game development has so much to do with math i would payed some more attention in shool

[Nigh™a®e]

After many hours testing i got closer to the sollution.

I can do a collision detect with triangles. Now the next challange.
If i take 2 points inside our 3D space. Lets say start and end point.

How can i detect what objects are on the track of the line from start to end.

Greets Nightmare

p.s. old topic; but din't had the time last weeks to work on it

[Zaei]

Look up ray-plane collisions. Once youve got a point on a plane, use a point-in-triangle function to test if the point hits a triangle.

Z.

[Nigh™a®e]

Long time ago, but i din't have much time to work on the game.

I have done some tests for the collisions detection and nothing worked.
I think DirectX9 has the perfect solution for this problem, but i don't realy understand how it works.
The Mesh object has an intersect function that uses ray intersection.

It seems to work but not good.
Does anyone can help me on that, using Mesh.Intersect


This is the code is use at this moment.

            '// Check Collesion
            Dim objDirection As Vector3
            Dim objHit As IntersectInformation

            objDirection.X = objCamera.Position.X - cHelper.UnitCircle(objCamera.Angle).X * 2
            objDirection.Z = objCamera.Position.Z - cHelper.UnitCircle(objCamera.Angle).Y * 2
            objDirection = Vector3.Normalize(objDirection)
            If objObject(0).Mesh.Intersect(objCamera.Position, objDirection, objHit) Then
                If objHit.Dist < 0.1 Then
                    objCamera.Reset()
                End If
            End If

Here are some screenshots of what i have.

16-01-2003 - 1
22-03-2003 - 1
22-03-2003 - 2
22-03-2003 - 3
22-03-2003 - 4
23-03-2003 - 1
23-03-2003 - 2
23-03-2003 - 3
23-03-2003 - 4
23-03-2003 - 5

[cyborg]

looks really nice!

[Nigh™a®e]

He, Zaei

The C++ code you provided looks a little like the code i found in some DirectX4VB Tutorials.

Also some parts of the engine are based on there tutorial.
As you can see on the screenshots, the side panel i use, is the same as in the DirectX4VB DirectX9 Tutorial.

Yesterday i discovered something that could be the problem of my non working collision detection code.

I have been working on it for a long time to get my lights working. The reasson its wasnt working, was becaus i dint normalize my vectors. In some tutors and examples i donwloaded they normalize some vectors in the collision detection code.

I will be working on this the hole weekend again.
If it finally works, i will put my code in here so other people can use it to.

If anybody is interested in helping me with the game, let me know (mail is currently not available, mailserver down)

You can contact me by MSN: [email protected]

This weekend the 3D objects of the first building will arive and build in. Monday i will post some new screenies.

[Nigh™a®e]

hehe, it finally starts working

This is the code is use
It work, but has some bug in it, doesnt work smooth, and sometimes im under the surface.
the X,Y world coordinates are X, Z vector values and the height has Y value.

The Return Value of the Function Test is the height of the ground.

    Function Test(ByVal CamPos As Vector3) As Single
        Dim varX As Integer = CamPos.X / varScale
        Dim varY As Integer = CamPos.Z / varScale
        Dim varA As Single = ((CamPos.X - objLandscape(varX)(varY).Vector(3).X) / (objLandscape(varX)(varY).Vector(0).X - objLandscape(varX)(varY).Vector(3).X))
        Dim varB As Single = ((CamPos.Z - objLandscape(varX)(varY).Vector(0).Z) / (objLandscape(varX)(varY).Vector(3).Z - objLandscape(varX)(varY).Vector(0).Z))

        Return FindHeightInQuad(objLandscape(varX)(varY).Vector(2).Y, objLandscape(varX)(varY).Vector(3).Y, objLandscape(varX)(varY).Vector(0).Y, objLandscape(varX)(varY).Vector(1).Y, varA, varB)
    End Function

    Public Function FindHeightInQuad(ByVal H0 As Single, ByVal H1 As Single, ByVal H2 As Single, ByVal H3 As Single, ByVal pX As Single, ByVal pY As Single) As Double
        Dim vN As Vector3
        Dim D As Double

        If pX - pY = 1 Then

        ElseIf pX - pY < 1 Then
            'we're in the top triangle
            vN = CalculateNormal(New Vector3(0, H0, 0), New Vector3(varScale, H1, 0), New Vector3(0, H2, varScale))
            D = -((vN.X * 0) + (vN.Y * H0) + (vN.Z * 0))
            Return -((vN.X * pX) + (vN.Z * pY) + D) / vN.Y
        ElseIf pX - pY > 1 Then
            'we're in the bottom triangle
            vN = CalculateNormal(New Vector3(varScale, H1, 0), New Vector3(varScale, H3, varScale), New Vector3(0, H2, varScale))
            D = -((vN.X * varScale) + (vN.Y * H1) + (vN.Z * 0))
            Return -((vN.X * pX) + (vN.Z * pY) + D) / vN.Y
        End If
    End Function

Later i want to try the code of Zaei, but how to put this in VB?

float f = float(1.0 - cos(ft)) * 0.5f;

[Nigh™a®e]

hmm, while playing a little with directx i found something else regarding collision detection.

     Direct3D.Geometry

This object seems to have all funtion for collision detection. Now its only ... how does it all wordk???

This seems to work on a simple object in my game

   '// Check Bounds
            Dim objBuffer As VertexBuffer = objObject(0).Mesh.VertexBuffer
            Dim objData As GraphicsStream = objBuffer.Lock(0, 0, LockFlags.NoSystemLock)
            Dim objectRadius As Single = 0.0F
            objectRadius = Geometry.ComputeBoundingSphere(objData, objObject(0).Mesh.NumberVertices, objObject(0).Mesh.VertexFormat, objObject(0).Position)
            objBuffer.Unlock()
            If Geometry.SphereBoundProbe(objObject(0).Position, objectRadius, objCamera.Position, objCamera.Target) Then
                objCamera.Reset()
            End If