Author Topic: My Game Engine is too Lame  (Read 58212 times)

0 Members and 1 Guest are viewing this topic.

Offline Mika

  • 28
Re: My Game Engine is too Slow
Quote
Really I'm just stuck on getting the rigid body physics working cleanly 

Right. So it's rigid body physics then.

Okay, what forces are you taking into account for the object? How do they progress through the body at the moment? Are you using a surface-surface contact model to model the leg friction, or is it just points?
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
@Mika, and others:

Context: rigid bodies in contact with one another:

If I only measure relative local velocities at a single point, and apply impulses for restitution and friction at that same point, a box will behave identically to a sphere.

That is my problem.

I can either solve this problem by creating multiple such "contact points" around the "corners" of the region of contact, or by modifying the ContactPoint struct to include the necessary extra data and modifying its DoConstraintAction method to use that extra data. Either way I need to modify the collision detection to compute that additional data.



@Mongoose: Well, I think in Bullet it only ever creates one "manifold point" between any pair of convex primitives... My ContactPoint struct is basically the same thing as one of Bullet's "manifold points". But I have no idea how Bullet deals with contact regions that aren't point-like.

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
Okay, I'm starting to get the hang of it. I even started to derive equations to see what is causing what! My differential calculus is a bit of rusty due to the severe neglect lasting for several years, but on the other hand, this stuff is interesting. Vector analysis on the other hand, is something I occasionally need to do at work.

I think using several points for analysis at the boundaries are a start, but as I started to think the formulation of the problem as a system of connected springs, there are several other factors popping up. Surface tension is one of them (otherwise ground conforms to the object shape, which doesn't happen in general case), then there is ground resistance towards pressure (must be an over dampened spring for typical landscapes). Additionally, the mass and the shape of the object on the surface become factors as well.

I think I need to check this out with pen and paper first, but heck, it's interesting!
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
@Mika: I don't mind that you're having fun exploring a new area, but that still sounds way more complicated than what I'm doing! The objects I am working with are rigid... they have a position, orientation, linear velocity, angular velocity, and mass, and defined in their local coordinate system they have a shape, center of mass, and a 3x3 moment of inertia matrix. No deformation, surface tension, or anything fancy like that :p

And what I'm doing is really more geometry that dynamics.



Givens:
  • Two rigid bodies whose shapes are "multisphere shapes", i.e. convex hulls around a collection of spheres.
  • The axis along which there is the least overlap between the two convex objects... similar to Separating Axis Theorem except without a convenient list of what directions to check. Basically this is the normal vector for my contact points.

What I'm trying to find:
  • One or more contact points (i.e. a point at which I will measure the relative local velocities between the objects, and apply impulses for restitution and friction), placed around the "corners" of the region of intersection of the two objects.



To simplify things a bit, I decided to have a plane with that axis as its normal vector, and to put all of the contact points I produce on that plane and use the same normal vector for all of them. The plane is situated half-way between the farthest extent of the first object along the axis and the nearest extent of the second object along the axis.



I've got my code set up to collect two lists of spheres I consider "relevant" to the collision... one is the list of which spheres of the first object extend beyond the nearest extent of the second object, and the second is the list of which spheres of the second object extend nearer than the farthest extent of the first object. Then I have a pair of nested switch statements, executing different cases according to how many spheres were deemed relevant in each object: either 1, 2, or 3+ spheres. In other words, the relevant parts of each object can either be a sphere, a tube, or a plane. This part has been implemented for a week now.

I've implemented all the cases where either object only has one relevant sphere... these are the easy ones, because the contact point is just the position of that sphere flattened onto the plane (or the average position in the sphere-sphere case). For each of the remaining cases, I can describe the solution geometrically, but I'm stuck on how to actually implement them:

  • Tube-tube: The intersection of two line segments. Except when the tubes are nearly parallel, in which case it should produce two contact points, one at each end of the "overlapping" region of the line segments... but they're not really line segments, they're tubes :blah:
  • Tube-plane: A line segment truncated where it intersects a convex polygon.
  • Plane-plane: Boolean intersection of two convex polygons; place a contact point at each vertex of the result.

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
Sorry about the delay, last weekend was spent doing something completely different.

For tube-tube intersection, you need to store one point of the tube, preferably the center point of either end. Additionally, you need to keep track of the basis vectors of the tube, or on other words, the local coordinate system of the tube so that you know it's orientation all the time. Typically the unit basis vectors are denoted with i, j and k. So, whenever your tube is rotating, you need to rotate these basis vectors as well so that itrans = ai + bj + ck for general case. Note that in a case of cylinder, you may not need the basis vectors after all since you have the surface normal, but I mention this for more general surfaces.

I'm gonna use the following notation in the text: P1 is the position vector from the GLOBAL origin to the center of the circular end of the tube. The radius of this tube is then R1, and the tube length to the center of the other end is h1. The local coordinate vectors for this vector are it1, jt1 and kt1, each of which may contain components i, j and k of the GLOBAL coordinate system.

So, every point on tube 1 can be described in the global coordinate system with vector S1 = P1 + rit1 + sjt1 + nkt1, where r s and n are just coefficients in front of the LOCAL basis vectors. Similar vector definition applies for Tube 2. Note that this places additional conditions to solution, r2 + s2 < R12.  Additionally, n = [0 ... h1] and ditto for Tube 2. Now, that there can be a collision, intersection or union, S1 = S2 at that point. This can be written as P1 + rit1 + sjt1 + nkt1 = P2 + mit2 + ujt2 + qkt2.

You can split this to three equations, that each must fulfil the abovementioned conditions so that the intersection can happen. I may take a look at this a bit later, I think rotationally symmetry and normal vector can be utilized to ease this up, but I hope you get the general jist of the above.
Relaxed movement is always more effective than forced movement.

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
Actually, don't start to code it yet, since the above would lead you to a triplet of equations that has three free parameters, which hints that the intersecting point may be anywhere in the combined volume of the two tubes. I have two additional approaches in mind for this set, I'll see where I get with them.
Relaxed movement is always more effective than forced movement.

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
Okay, I think I got it. I'll spend the first hour after waking up on tomorrow to double check the logic - you never know if I missed something at this point of day!
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
What... is this the math for how to find where the surfaces of the tubes intersect?

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
The above was valid for the volume where the two tubes intersect. To get it to surface level, it is possible to get rid of two unknowns in the equation by requiring the relevant basis vector coefficients to fulfill the surface radius on both tubes. But the result is nevertheless very messy and still leaves one parameter free. But whatever, I think there is a more clever way of doing this algorithm wise, but you'll have to wait for that for tomorrow.

Yes, surface surface intersection tests are messy. Surface line intersection is much easier, but even there you don't want to get into higher order polynomials or B-Spline surfaces... Ray-trace software always uses simplest possible algebraic surfaces, such as spheres, rectangular volumes or just planes to enclose more complex geometries. Occasionally, the intersection point can be solved analytically for simple surfaces (like cylinders), but often it is the case that iteration is required, and this is one of the reasons why it is difficult to do a real-time ray-tracing engine.
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
But... I've already determined that they're colliding?

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
Okay, the thing I thought about yesterday would have been okay for cylinders whose central axes intersect. However, this is not the case in general, and the larger the offset, the greater the error would have been.

Since I'm still not confident I understand your problem, could you draw me a formulation of the problem, tube-tube case first?

Meanwhile, for line-line intersection (I'm not sure whether you have already implemented this), the following should work:

P1 and P2 are points on the corresponding lines measured from GLOBAL origin, and thus vectors P1 and P2 are straightforward to define from the global origin. Additionally, you'll need the direction vectors for the both lines, be them n1 and n2 correspondingly. Normalize these vectors to unity.

First, compute n1 x n2. If the result is zero vector, the lines are parallel to each other and can only intersect if P1 = P2, otherwise no intersection is possible. If they do intersect, they'll intersect the whole distance they are defined at.

Second step, since we now know that n1 x n2  !=  0. We need to rule out the possibility that the three dimensional lines are skew, and thus could not possibly intersect. Compute (P1 - P2) * (n1 x n2). If the result is zero, intersection is possible. If the result non-zero, the lines are skew and cannot intersect.

Third step is the traditional solving free parameters r and s for P1 + n1r = P2 + n2s [1]
You could open up this to three equations for each coordinate axis, and solve for parameters s and r and substitute them to the last remaining equation to check whether it remains valid. The problem with this approach is that it gives rise for many possibilities of dividing by zero, or that some component of either normal vector is zero. Not good.

Instead, let's do the vector approach. Take a cross-product of [1] with n2. This eliminates one free parameter completely, one of the great things in vector algebra.
Result is n2 x (P1 + n1r) = n2 x (P2 + n2s), and because cross-product is distributive over addition, this can be written as
n2 x P1 - n2 x n1r = n2 x P2 + n2 x n2s, where n2 x n2 cancels. Re-arrange the remaining terms over right side, and leave r for the left, which leads to
n2 x n1 r = n2 x P2 - n2 x P1 = n2 x (P2 - P1). It sure would be nice to be able to leave r alone, but because this is a vector equation, we cannot divide the left side just with a vector. Instead, it pays off to multiply the equation with the dot-product of n2 x n1.

This results in (n2 x n1) * (n2 x n1) r = (n2 x n1) * [n2 x (P2 - P1)], and since the dot product of the vector itself is a scalar, it is now possible to divide the whole set with r's coefficient, leading to

r = [(n2 x n1) * [n2 x (P2 - P1)] /  | n2 x n1 |2

Substitute r to the P1 + n1r and you'll get the intersection coordinates. I'm not sure whether denominator normalizes to unity, so it is better to leave it that way.

Now, and this is a very big NOW, you cannot use these generally to determine the intersection points of the cylinders, especially if the cylinders have large base radii. Why? Because while skew lines do not intersect, skew cylinders can and will intersect when you least expect it, and this is the complicative issue.

The reason for the order of the three steps is the following. Since there is a multitude of pieces in the geometry and many of them needed to be tested, the intersection test should terminate as soon as possible if no intersection becomes apparent, and only go to heavy calculation as a last step - basically, we are sort of assuming that the intersection does not happen and this tends to be the case.
Relaxed movement is always more effective than forced movement.

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
And for line-tube intersection in general case, please refer to ye olde Graphical Gems.

It also contains code to compute the points of intersection, along with the theory.

Now, since others have noted that a tube isn't that great of an enclosing surface, they recommend using capsules for faster intersection testing. Select something like 20 points on the underlying base circle with equal angle steps, and record these points on to a structure. Whenever the cylinder is rotated or translated, apply same to these points as well. Then do the intersection test between the lines defined by these points and the tube axial direction vector and the opposing tube as shown in the above code.

Now, what was the next intersection test? Line and a plane, or a tube and a plane? Or a line and a polygon?
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
Dude, stop :(

I'm not trying to do collision detection. I have already determined that the objects are colliding. I am trying to pick points within the region of contact to do my constraint stuff at.



Edit: and now it's done! Mostly. Might need to do some tweaks to get tube-tube and tube-plane working a little better, but it seems to be working.

Still gotta do all of multisphere-triangle (of triangle mesh) though.
« Last Edit: February 25, 2013, 09:28:26 pm by Aardwolf »

 

Offline Tomo

  • 28
Re: My Game Engine is too Slow
My brain melted...

Great to hear you got it working! (Mostly)

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
Congratulations on progress!

The above two methods I listed DO produce the exact point where something hits, i.e., they are actually not used for collision detection, but telling the exact point of the collision (the intersection). I thought that was what you asked.

Triangle-line intersection had a really snappy algorithm with some clever mapping in it, I wonder if that method could be generalized for spheres somehow...
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
Speaking of progress...  :sigh:

For some reason I am thinking about ditching multisphere shapes in favor of convex polygon meshes... despite the huge amount of time I've spent getting multisphere shapes working. Bleh.

Arguments pro switching:
  • Maybe faster collision detection?
  • Maybe easier to do multi-contact-point generation?
  • Collisions between convex poly meshes and terrain mesh triangles can be handled by the same code that handles collisions between two convex poly meshes
  • Collision potentially less "grainy" than my current multisphere-multisphere algorithm (not sure how significant this is)
  • It's a more "well known" problem; I can probably find resources about it on the Internet

Cons:
  • A lot of work just to get to a state comparable to what I've got already
  • I'd have to make new collision models, and probably figure out how to decompose a non-convex model into convex submodels
  • Australian doofus who dislikes FreeSpace would be all like "told ya so"

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
What I would think about polygon based collision testing and intersection finding is that you can then use the same algorithm for pretty much everything. Well, maybe little tweaks here and there. Since most of the surfaces (read:all) I have programmed have been continuous to second derivative, I don't know how to deal with the discontinuities in the polygon mesh so don't ask me about that.

There was a graphics engine that was completely sphere based a couple of years ago, which made real-time illumination with ray-tracing a breeze compared to anything else. What you are now doing is programming sort of geometric primitives (more analytic and scientific method of finding intersections), where each of them have to be handled in a different way. Polygons are bit more universal if I have understood them right. You'll still not get rid of bounding volumes completely, typically polygons have them too to speed up the collision/intersection testing.

If you go on with geometric primitives, I'd recommend using simple geometric enclosing volumes, tube probably isn't one of them, but a rectangular volume is. Typically what are used are spheres, rectangular bounding volumes and planes where applicable. The nasty thing is that the bounding volume must also rotate and move accordingly on each update.

So it all depends on what you want to do. You'll learn much either way, but doing something differently is usually a better way of learning.
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
Was trying to type reply but twice now have lost my whole message due to some combination of keypresses causing firefox to exit while I was battling with these stupid ****ing loose keys on my keyboard. Will maybe try again when I've calmed down.



Well, I decided to do the convex meshes thing.

I've gotten a fair amount done on my new ConvexMeshShape class. I've got an Init method which takes an array of points as input and from that figures out the vertices, edges, and faces of the minimum convex polyhedron necessary to enclose those points. I've tested it on my beveled cube "crate" model, and it seems to be working, including getting rid of unnecessary colinear verts.

I've also implemented some collision detection functions for it... CollideRay and CollidePlane are done (but untested), and CollideTriangle (of TriangleMeshShaped) and CollideConvexMesh are done as far as detecting the collision, at which point they call a GenerateContactPoints method, which is not done yet. Basically I'm where I was like a month ago; I've got collision detection, but I need to generate multiple contact points for the collisions I've already detected. But unlike a month ago, all the code is going to be in one function (instead of separate setups for -triangle and -multisphere), and everything is points instead of spheres. That should simplify things this time around.

As far as how GenerateContactPoints is going to work, I've already started the way I did previously by figuring out the min an max extents of the region of overlap, and then only concerning myself with the verts of either object which extend into that region. Anyway, I think I can implement this.



I'm a little worried about the performance of the actual collision detection (not the contact point generation) potentially being worse, though, because...

With the MultiSphereShape representation of these crates, I had 8 rounded spheres... so evaluating the min and max extents of each cube (in a collision between two such crates) was 16 dot products. The algorithm for deciding which directions to test was basically to test 8 points around the previous best result, zooming in 2x if they all score worse, and repeating this for 5 iterations. More for better quality... because it's a numerical thing, I can tune it by changing the number of iterations... although I've never thoroughly examined it to see how many false positives it produces with different numbers of iterations (by seeing how many false positives get removed with each additional iteration).

With the new ConvexMeshShape representation, there are 24 verts, 48 edges, and 26 faces... evaluating the min and max extents along an axis is therefore 48 dot products (1 for each vert, x 2 objects). And if I'm going to be doing it analytically instead of with a numerical-ish search like I did previously, I'm pretty sure I have to evaluate once for each of (2 * 26 + 2 * 24 * 24 + 2 * 24 * 48 + 2 * 48 * 48) directions in order to be guaranteed to find a separating axis if one exists.

Maybe I can intelligently limit which verts/edges/faces I need to test, and which verts I consider when evaluating the min and max extents? Or should I just continue doing this numerical-ish searching business I've been doing?
« Last Edit: March 05, 2013, 03:10:50 pm by Aardwolf »

 

Offline Mika

  • 28
Re: My Game Engine is too Slow
Okay, convex polygon meshes should have more defined methods in the literature and in the game design side. There's not much I can say about any sort of polygon intersections rather than subdividing them to triangle intersections. Since a single polygon can easily have over thousand triangles, going to intersection testing of all of them is something one does not want to do voluntarily. So bounding volumes still remain important. Additionally, I'd look for structs and flags containing information about for example, which parts of the player model are supposed to hit the ground in which stance, or if he is airborne at the moment or not - I don't whether they do it this way, but that's what I'd look for.

I'm a bit curious though, why are you trying to find a specific solution for the collision between two boxes? I thought CollideConvexMesh would do that as well - if it is performance you are looking at, then that's a different thing - I'd first recommend going further and not stopping to optimize this routine until it becomes a bottleneck. Remember that the premature speed optimization is the root of all evil. When it DOES become a bottle neck, first thing I'd do to improve the efficiency are bounding volumes of the polygons, these should speed up the collision search - and then you are sort of back to square one.

Good luck, I'll be looking for this thread occasionally

EDIT: Oh, and occasionally, it is so that the numerical method is more efficient than analytical method - or that the difference is so small that it doesn't matter, while numerical method is numerically more simple to program and possibly less ill-conditioned. All these sorts of things happen in the ray-tracing world as well!
Relaxed movement is always more effective than forced movement.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Slow
@Mika: Yes, "the literature" was one of the pros for switching to convex meshes. Already been doing bounding volumes for a long time... at least for my broadphase collision detection anyway. What's this about boxes? I just searched for "box" and found nothing recent in this thread... Do you mean the crates? I'm just using those because it seems like a good example to test stuff with... and because you can't have an FPS without crates.



Anyway I finished implementing the methods I was working on, and got the things in-game... but there are a few problems...

First, it's unplayably slow! :ick: Significantly worse than multispheres. Maybe I can come up with something to get it working faster? Idunno. :sigh:

Second, there's some weirdness which seems to be arising from my "adhesion threshold" hack (threshold for local relative velocity, below which objects get pulled back together)... When I was doing multispheres I had it set at about 0.08 m/s to keep the crates (which had rounded corners) from jittering. But that's keeping these beveled-corner crates from rolling down hills when they ought to. But if I reduce the adhesion threshold, they jitter again!

Finally, there's an infinite loop that only seems to happen when I'm running a Release executable, and inconsistently then. Bleh.