Movin' On Up

Member
Posts: 215
Joined: 2008.06
Post: #1
After months of silence and almost no games work, I have returned (gasp!), here to pick your brains as usual.

I have decided to step back and rewrite a lot of my original code. The new physics engine will have SAT collision detection (in 2D to start). But that's where the problems start (they never end...). I understand the principles behind SAT, but I'm uncertain what kind of information I should store in an object in order to perform tests. Additionally, I'm uncertain what kind of information I need to store to create objects other than rectangles: triangles, wedges, and pie-slices. I'm also unsure how to use the stored information in order to draw the object in my rendering engine. I have been using halfwidth vectors for my square objects, but I don't believe that will work for triangles and so forth. Thanks for the help in advance!

Mac users swear by their computers, PC users swear at their computers. ~Unknown

iSayz
Quote this message in a reply
Member
Posts: 260
Joined: 2005.05
Post: #2
Talyn Wrote:After months of silence and almost no games work, I have returned (gasp!), here to pick your brains as usual.

I have decided to step back and rewrite a lot of my original code. The new physics engine will have SAT collision detection (in 2D to start).
Even if you solve it for 2D, the move to 3D may not be easy. Also, beware of algorithms that demand your shapes to be convex, so you don't feed them non-convex objects.
Quote:But that's where the problems start (they never end...). I understand the principles behind SAT, but I'm uncertain what kind of information I should store in an object in order to perform tests. Additionally, I'm uncertain what kind of information I need to store to create objects other than rectangles: triangles, wedges, and pie-slices. I'm also unsure how to use the stored information in order to draw the object in my rendering engine. I have been using halfwidth vectors for my square objects, but I don't believe that will work for triangles and so forth. Thanks for the help in advance!
In 2D it isn't too bad. I represent my shapes by polygons, and all you need for that is a (dynamic) array of 2D points.

3D is a lot worse. Then I use arrays of vertices, triplets arrays of vertex indices (triangles), and also vertex-to-triangle indices (needed for moving over the surface).
Quote this message in a reply
Member
Posts: 215
Joined: 2008.06
Post: #3
Ingemar Wrote:Even if you solve it for 2D, the move to 3D may not be easy. Also, beware of algorithms that demand your shapes to be convex, so you don't feed them non-convex objects.

In 2D it isn't too bad. I represent my shapes by polygons, and all you need for that is a (dynamic) array of 2D points.

3D is a lot worse. Then I use arrays of vertices, triplets arrays of vertex indices (triangles), and also vertex-to-triangle indices (needed for moving over the surface).

Wow! Thanks, that helps to answer some of the questions. So you recommend storing the vertex positions for each "corner" and then passing half-width and axis vector information back based on position-vertex vectors to then project that without knowledge of it's shape? I suppose that makes sense. I don't plan on handling convex polygons until MUCH later (perhaps never with this engine), so no worries there. Thanks again for the suggestion.

Mac users swear by their computers, PC users swear at their computers. ~Unknown

iSayz
Quote this message in a reply
Member
Posts: 215
Joined: 2008.06
Post: #4
I've started using an array of points to keep track of vertexes for my test square. I have (mostly) implemented rotation of these points around the center of the square, but the entire polygon shrinks as I perform the changes. Any ideas as to why this is happening, or how to fix it? What I'm thinking right now is that I will have to find the vector between each of the vertexes and the position of the object, calculate the real distance from the halfwidth vector, and then force the vertex to be that distance away. Thanks in advance!

Mac users swear by their computers, PC users swear at their computers. ~Unknown

iSayz
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #5
If you are constantly re-transforming the same set of vertexes that could explain why it is shrinking.

I use SAT in my physics library (Chipmunk). I represent a shape as an array of vertexes and an array of axes. Each axis has a normal and a distance along that normal from the origin. I keep two copies of the polygon vertexes and axes. One copy is the original untransformed values, and the second copy is a cached set that is transformed to the current location of the shape. Before running any collision checks, I run through all the shapes and update the cached vertexes and axes.

Otherwise to make rotation of the vertexes fast, I precompute a rotation vector and use complex multiplication to rotate the vertexes and axis normals. For the axis distances, you just need to add the untransformed axis distance to the dot product of the shape offset and the axis normal.

One problem that you run into with SAT is that the time complexity is m*n where m and n are the vertex counts in your two polygons. I haven't found this to be too big of a problem as I rarely need more than 5 vertexes on a convex polygon used for a rough collision shape anyway so it's not so bad.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 63
Joined: 2005.12
Post: #6
Talyn Wrote:I've started using an array of points to keep track of vertexes for my test square. I have (mostly) implemented rotation of these points around the center of the square, but the entire polygon shrinks as I perform the changes. Any ideas as to why this is happening, or how to fix it? What I'm thinking right now is that I will have to find the vector between each of the vertexes and the position of the object, calculate the real distance from the halfwidth vector, and then force the vertex to be that distance away. Thanks in advance!
The shrinking sounds like accumulated error due to incremental rotation. You don't want to rotate the box vertices incrementally (i.e., relative to the last frame/update). Rather, keep a local-space copy around, and transform them to world space from scratch each update. (This will also eliminate the need to rotate relative to the current center of the square, as I gather you're doing now.)

As you've already gathered, you can apply the SAT uniformly by representing all convex polygons (even regular shapes such as rectangles) as a set of points. This is probably a good place to start, as it will simplify the implementation considerably. It isn't the best approach performance-wise, but unless you're performing many narrow-phase intersection tests per update, you're unlikely to notice any performance hit.

If at any point you do need to optimize, be aware that for regular shapes such as boxes and axis-aligned boxes, there are more optimal representations that a simple point set.
Quote this message in a reply
Member
Posts: 215
Joined: 2008.06
Post: #7
Skorche Wrote:If you are constantly re-transforming the same set of vertexes that could explain why it is shrinking.

I use SAT in my physics library (Chipmunk). I represent a shape as an array of vertexes and an array of axes. Each axis has a normal and a distance along that normal from the origin. I keep two copies of the polygon vertexes and axes. One copy is the original untransformed values, and the second copy is a cached set that is transformed to the current location of the shape. Before running any collision checks, I run through all the shapes and update the cached vertexes and axes.

Otherwise to make rotation of the vertexes fast, I precompute a rotation vector and use complex multiplication to rotate the vertexes and axis normals. For the axis distances, you just need to add the untransformed axis distance to the dot product of the shape offset and the axis normal.

One problem that you run into with SAT is that the time complexity is m*n where m and n are the vertex counts in your two polygons. I haven't found this to be too big of a problem as I rarely need more than 5 vertexes on a convex polygon used for a rough collision shape anyway so it's not so bad.

That's very helpful, thank you! What is are the axes and normals for? I don't quite understand. And what do you mean by rotation vector? I've been using a float for angle change per frame, is that incorrect/not complex enough?

How long did Chipmunk take to create and what resources/experiences did you draw upon in order to make it?

Thanks again for the help, Skorche! This little project has turned into one hell of a pain. I really appreciate the feedback!

Mac users swear by their computers, PC users swear at their computers. ~Unknown

iSayz
Quote this message in a reply
Member
Posts: 215
Joined: 2008.06
Post: #8
There's nothing quite like the feeling of seeing something you've been slaving over for a long while work correctly for the first time. There's also nothing quite like the feeling of realizing you had a simple, tiny, but grievous error that took you many hours to debug and was holding up your entire project.

Long story short, I now have simple rotation for my quad done and I would like to thank you all for your input. I suspect the road ahead will be quite...interesting and challenging, but I hope to return here with some new knowledge. Thanks again!

Mac users swear by their computers, PC users swear at their computers. ~Unknown

iSayz
Quote this message in a reply
Post Reply