Triangle Intersection
Pages: 12
closed account (N36fSL3A)
I know I made a thread on Collision Detection a while back, but my triangle intersection was crap when I attempted that. I moved on for a bit, added some new stuff to my engine including spherical intersection(that's pretty easy, got it down in 1 day), and now I want more complex collision.
I find resources on the internet but it contains math I've never seen in my life, and I'm confused. Can someone explain it?
(This collision has to be able to work on separate planes)
I find resources on the internet but it contains math I've never seen in my life, and I'm confused. Can someone explain it?
(This collision has to be able to work on separate planes)
What do you want explained?
It is like saying to your math teacher before you final exam: "Explain it to me?"
It is like saying to your math teacher before you final exam: "Explain it to me?"
Are you asking for the way to determine whether two triangles defined in 3D coordinate space intersect each other?
For triangle intersections, you need to perform an algorithm like this:
1) Calculate the normals of both triangles
2) If the normals are parallel, then:
a) if the angle between one normal and the vertex point of the other normal is not 90, then the triangles do not intersect (they are in parallel planes)
b) if the angle is 90, then you need to test using a standard 2D collision (coplanar) algorithm
3) else you need to check to see if at least one of each triangle's edges intersects the other triangle.
A good place to start looking at the math is here:
http://www.realtimerendering.com/intersections.html
You probably want something like: http://geomalgorithms.com/a06-_intersect-2.html
The math looks scary, but it really isn't so bad. Most if it is high-school algebra.
(Though, if you are playing with 3D stuff, you should get used to doing transformations using matrices.)
Hope this helps.
For triangle intersections, you need to perform an algorithm like this:
1) Calculate the normals of both triangles
2) If the normals are parallel, then:
a) if the angle between one normal and the vertex point of the other normal is not 90, then the triangles do not intersect (they are in parallel planes)
b) if the angle is 90, then you need to test using a standard 2D collision (coplanar) algorithm
3) else you need to check to see if at least one of each triangle's edges intersects the other triangle.
A good place to start looking at the math is here:
http://www.realtimerendering.com/intersections.html
You probably want something like: http://geomalgorithms.com/a06-_intersect-2.html
The math looks scary, but it really isn't so bad. Most if it is high-school algebra.
(Though, if you are playing with 3D stuff, you should get used to doing transformations using matrices.)
Hope this helps.
closed account (N36fSL3A)
| Why not start with something simpler like 2D ? |
| (Though, if you are playing with 3D stuff, you should get used to doing transformations using matrices.) |
| Most if it is high-school algebra. |
Last edited on
| Lumpkin wrote: |
|---|
| I'm not even in highschool. |
Holy crap! That's right, you're like 14, right?
Hmm... you've got a little learning ahead of you.
You need to become comfortable with linear algebra and trigonometry. If you can get to the point where you can solve a system of equations with two variables by either substitution or elimination then you should know enough to get started. And you must be comfortable working with triangles.
A matrix is a 2D collection of numbers (which can be conveniently stored as a 2D array). Linear transformations can be applied to a vector (like moving it, rotating it, and scaling it) with a simple multiplication by the appropriate matrix.
I know they don't teach matrices in US high school math... alas, but it is a fairly simple thing to pick up. You should be able to have it down pat in a week.
The most difficult part is handling the word problems kind of stuff. Given a whole bunch of information about how things interrelate, what of that information do you need and how to you plug it into a formula to get the information you want.
I haven't touched it for a while -- but don't OpenGL and DirectX provide functions to detect collisions for you?
closed account (N36fSL3A)
| Holy crap! That's right, you're like 14, right? |
So you can see that in-school math doesn't help very much, I had to learn math solo for a few months now.
| Trigonometry |
OpenGL doesn't provide intersection functions, I'm not sure about DirectX though.
You must be thinking about XNA and C#.
-----
I don't understand the use of matrices at all.
I'm doing Direct3D rather than OpenGL, and I'm fairly confident in saying that I don't think it has any collision detection.
This is because Direct3D and OpenGL are only for "colouring in", they're API's that are only designed to render graphics and draw them to the screen. If you want anything to do with mechanics, you gotta do that yourself (or use something like UDK/Bullet )
How I've created my collision detection is so it only works by finding if a point is within a volume, while primitive I'm hoping it'll be enough for what I need it for, and also it should be faster than full detection.
This is because Direct3D and OpenGL are only for "colouring in", they're API's that are only designed to render graphics and draw them to the screen. If you want anything to do with mechanics, you gotta do that yourself (or use something like UDK/Bullet )
How I've created my collision detection is so it only works by finding if a point is within a volume, while primitive I'm hoping it'll be enough for what I need it for, and also it should be faster than full detection.
Last edited on
Point or ray the calculations required are about the same. What really speeds up collision detection is -- under various guises -- splitting the data up into non-intersecting partitions. By applying the appropriate granularity (there are several ways to do this, all reducing to about one calculation between objects/sections) you can reduce the amount of calculation by focusing only on those areas that actually need checking.
closed account (o1vk4iN6)
| XNA and C# |
Oddly enough microsoft dropped support for XNA and I think they dropped support for DirectX as well if they even supported it to begin with.
http://msdn.microsoft.com/en-us/library/windows/desktop/bb204928%28v=vs.85%29.aspx
Not really part of DirectX but microsoft does include an extended library where they define D3DXVector3 and the like.
closed account (3qX21hU5)
Microsoft didn't drop DirectX and has no plans of doing so (There were false reports saying it was going to but they are untrue). But you are right they did Drop XNA but the Mono project is still in full swing with it's version of it which can be deployed to IOS, Android, Linux, Windows, ect.
closed account (o1vk4iN6)
Not sure they even had it but there is definitely no directx for c# supported by microsoft.
Last edited on
closed account (3qX21hU5)
Didn't know we were talking specifically about C# since DirectX is a C/C++ API. I know there is a directX namespace in .NET though.
Last edited on
closed account (o1vk4iN6)
Yah i was talking about specifically C# i think actually they did support a wrapper for directx but they dropped it a couple years ago now. I guess they just kept it in there anyways. They just released another "direct"Xbox, so yah microsoft dropping directx would be foolishness.
Found this here:
http://www.codeproject.com/Articles/35716/Introduction-to-collision-detection-techniques-in
So DirectX supports collision detection between meshes (with the Mesh::Intersect() method).
http://www.codeproject.com/Articles/35716/Introduction-to-collision-detection-techniques-in
So DirectX supports collision detection between meshes (with the Mesh::Intersect() method).
closed account (N36fSL3A)
I'm using OpenGL. I don't have a problem with techniques, I've read up on them extensively earlier on, the problem is with detecting the intersection.
Well, like I keep saying... the way forward is to make sure you have some sort of partitioning, such as bounding boxes/spheres/shapes which give you a low-resolution idea of whether you need to check further for a given pair of objects.
Once you do, you'll need to test with the algorithm and links I gave you above. You won't find much faster methods.
Remember, full collision detection is an intensive process -- which is why most games use a collision mesh for characters and use it exclusively for collisions. Less stuff to calculate == faster game; users can't usually tell the difference.
Once you do, you'll need to test with the algorithm and links I gave you above. You won't find much faster methods.
Remember, full collision detection is an intensive process -- which is why most games use a collision mesh for characters and use it exclusively for collisions. Less stuff to calculate == faster game; users can't usually tell the difference.
closed account (N36fSL3A)
| Remember, full collision detection is an intensive process -- which is why most games use a collision mesh for characters and use it exclusively for collisions. Less stuff to calculate == faster game; users can't usually tell the difference. |
I'll look into the second link you gave, it's great that it actually has a C++ implementation that I can refer to for help.
EDIT: After looking into it more, I realized it only shows implementation for triangle-ray intersection.
Last edited on
...which is exactly what you need. A triangle is three points, which has three sides, which is three rays.
Pages: 12