# maxgpgpu

Members

258

206 Neutral

• Rank
Crossbones+
1. ## when is "center of gravity" simplification false?

My temporary short-term hack (which might be okay long-term too, since in actual practice we shouldn't have very many infinitely thin objects) is to make the gravity computation set a minimum on center-of-mass distance before it performs the computation.  I think my temporary choice was somewhere between 0.000001 and 0.001 meter.  What is especially convenient and efficient to model as infinitely thin surfaces is pieces of exploded objects.  To give an actual thickness not only requires twice as many triangles (to create both sides of the thin piece), but also more vertices to seal up the edge thickness.
2. ## when is "center of gravity" simplification false?

Okay, seems like you're saying the "center of mass" approximation isn't valid even when objects are far apart (further apart than the sum of their maximum radii).  Hmmmm. Two answers to your other question.  I consider the engine to be a 3D simulation/physics/game engine.  OTOH, I do admit that the focus is still real-time performance, so we do not anticipate pushing for exact formula in every situation, especially if it kills performance too much (below 30FPS minimum on highish-end CPUs/GPUs, probably). Also, our first couple planned games take place in space (zero gravity, except for local objects).  Well, sometimes.  It will also have to support being in the vicinity of one or a few large objects (planets and their moons) in addition to nearby small objects (asteroids, space-habitats, spacecraft).  Though gravity doesn't make floating objects move towards each other very fast, it is relevant over minutes, much less hours.  And because (in some situations) activity happens very slowly in space, the games will probably have a way to specify a sort of "fast forward" that increases the physics interval but keeps the frame interval.  In that situation, gravity in most space environments we envision will be quite relevant!
3. ## when is "center of gravity" simplification false?

Interesting stuff. However, none of these pages answers the primary question I wanted to ask (unless I missed something).  If we ignore any twisting or stretching of objects as they pass near each other, and only pay attention to the centers of mass, in what situations do the centers-of-mass actually in reality not move in the way indicated by treating them both as point masses at their centers-of-mass?  We know for the hollow and solid sphere cases that "things change when the objects overlap", but what about other shapes like the one I mentioned, namely "two triangles" or "two round disks"? Yes, I do realize I need to decide what second, third, fourth, twenty-third order effects to ignore, but this question seems to be the first I need to resolve.  After that, I will need to decide where to draw the line and accept approximations.  One factoid that I am hoping someone can confirm is... that the centers-of-mass approximation is accurate (in terms of positions of the two centers-of-mass) at least up until the centers of mass come closer than the sum of the maximum "radius" of the two centers-of-mass (where "radius" just means the distance from either center-of-mass to the furthest point on the object).
4. ## when is "center of gravity" simplification false?

Similarly for a solid sphere, the force of gravity gradually reduces to zero as you travel through the surface and approach the center... ...but most physics engines do not simulate the force of gravity between objects because gravity is too weak to be of any effect (instead we just simulate the force of gravity from the earth) so this is irrelevant :) Are you simulating gravity between objects?   It sounds like your actual problem is do to with resolving collisions? In general, resolving object penetrations is a difficult problem, and is made easier by having thick objects that only ever penetrate a small amount. You can limit penetration by increasing the time-step, or using swept-collision detection and resolving collisions at the moment that they occur instead of after penetration has occurred.   We do swept-collision detection and we do push objects back to t=toi before we compute collision response.  So I don't think that's the problem.  All collision response seems to work fine, but when these super-thin (well, infinitely thin) objects come together, you can see that their centers seem to pull together more quickly than you'd expect (they slide face-against-face to pull the centers together, which is correct behavior if you buy into the nominal center-of-mass simplification).  And when the centers do meet, there is that crazy explosion apart that happens.  I mean, it makes sense in a way that something wacko would happen when you think about (G*m1*m2)/(d*d).  When d approaches zero, any non-zero value divided by (d*d) quickly surges towards infinity. Yes, our engine supports gravity, because our first games will take place in outer space, and we want our game/physics engine to automatically support gravity (when the game designers want and enable gravity).  Even on conventional earth-surface games, don't you need some force to push objects towards the ground (or center of earth)?
5. ## when is "center of gravity" simplification false?

In almost all 3D physics we treat 3D objects as point masses, and in most cases this is either correct or "close enough".  I know of one physical configuration this simplification is totally wrong, but wonder whether others exist (including a specific one I'll mention). The case I've known about is a hollow sphere (with one or more holes in the surface).  When any other object is outside the skin of the hollow sphere, gravity can be computed as if the object is a point mass per usual practice.  However, if another object passes through the hole in the skin, all of a sudden the gravitational attraction becomes zero... everywhere inside the hollow sphere.  A bit strange, but I can see why that's true. While testing the physics engine in my 3D game engine, I noticed what appears to be strange behavior when flat triangles come close to each other.  In my tests, the triangles have mass, as if they are very thin.  In fact they are infinitely thin, because they are simply triangles, but they behave the same when I make them very thin [3-or-more-sided] disks.  Sometimes they even explode apart (I think when the centers come close together). I realized this might be slightly similar to the hollow sphere situation in a way.  When the centers of the triangles come closer than the radius of the triangles, the point mass representation seems to have the same characteristic that makes the hollow sphere case change behavior, namely (some physical parts of each object is in opposite directions from the center of gravity (or more precisely, "some physical parts of") the other object.  It doesn't feel like exactly the same situation as the hollow sphere, but the behavior is strange and I wonder if that's because this assumption (that point masses are a valid representation) is failing big time in a similar way as the hollow sphere case. Does anyone know about this stuff and provide some comments, links, references or something? PS:  The rigid body physics and contact routines seem to work and behave properly with thick objects (where the center of masses are not super close to the external surfaces).  I don't have code to handle stacking (objects with contacts with multiple other objects), but the behavior I am seeing happens with only two objects. BTW, on a separate issue, what's the best place to read about going from "simple contacts" like I have (only 1~4 contact points on each of any two objects) to support for "arbitrary stacking"?  I'm guessing "stacking" refers to the situation where more than two objects are in contact with each other, with each contact pair having 1~4 points in contact.  I say "not more than 4 contacts" simply because my code reduces cases of more-than-4 contacts to 4 contacts to simplify processing. Thanks in advance for any tips, ideas, references.

7. ## force and torque

Buckeye:  You apparently understood the rocket thruster configuration.  Great.  So, what series of steps (algebra equations or pseudo-code) compute the linear and angular acceleration, velocity, position and orientation for successive frames for that configuration given I know the object mass, thrust in grams, position of thrust in local-coordinates, direction of thrust in world-coordinates, object inverse inertia tensor, and duration of each frame?   Is that short enough?

11. ## inverted GJK --- you're a genius if you can solve this

Sorry, I was away for a couple days.   I think both of the last two posts have merit, at different phases of the process.  The algorithm that is most efficient at a rough approximation stage will probably not be best at the precision stage.  Which is why we have SAP (sweep and prune) for broad phase and GJK for narrow-phase in the first place.  And at this point, frankly, we have about 5 phases (or sub-phases), from "swept bounding sphere SAP", to "compute earliest-possible TOI based on bounding spheres (or possibly realize they do not collide)", to "compute earliest-possible TOI based upon AABBs of rotating objects", to "enhanced GJK that reports distance and a separating axis and perpendicular plane" (which again lets us compute earliest-possible TOI based upon knowing vertex at maximum distance from center-of-mass and rotation axis ala erin catto), and continued "sorta" conservative advancement based upon our enhanced GJK routine.  BTW, though they probably don't arise very often in most games, we've identified a whole slew of cases that completely hose conventional conservative advancement techniques, so we found ourselves needing to be a little more "clever" and practical than their conservative advancement techniques.  Or so we hope.   All that's great (if not a bit exhausting to create) for conventional convex objects.  But when it comes to this fairly common case of intentionally flying objects into voids in other objects, some new problems pop up, which we'd like to solve efficiently if not simply.   I think the approach mentioned by Jtippetts looks good at broad phase or perhaps one small notch down from there.  Actually, I think two variants of that probably work fine - the first based upon the bounding-sphere of the landing spacecraft (which only requires transformation of one point to world coordinates (plus the fixed radius)), and another [perhaps] based upon the AABB of the landing spacecraft versus the real (arbitrarily rotated) planes of the 5 walls of the landing bay.   I'll have to think more about the techniques proposed by clb.  First I better go read about Dobkin-Kirkpatrick to gain some background.  As for that hill-climbing approach, that sounds quite a bit like that approach I mentioned in my original post.  Fortunately the fundamental 3D shapes that everything is created from in my engine contains "n sides" and "m levels", and the indices of those vertices are retained in arrays in objects for later applications like these.  Which means, walking the vertices in objects is very efficient, and can be done intelligently for most purposes.   So, I'll fiddle.
12. ## inverted GJK --- you're a genius if you can solve this

Well, my experience is, during the process of brainstorming it is very wise to take a wide variety and attitudes (including, "I'm old, tired and lazy"), and see where they lead.  So... can't complain about that.  In fact, though I don't have the same attitude as you for reasons I'll mention later, you reminded me of an old idea from another problem.   Typically, a "landing bay" will be a big box, the entire volume of which is empty.  Of course, a mothership isn't some stationary object sitting flat on the ground, so the landing bay will always be oriented at some random fractional x, y, z angles.  Otherwise the landing bay would actually be an AABB itself.  However, I already have functions to transform from world to [object] local coordinates, so it is trivial to transform the 8 corner points of the landing bay to local-coordinates to create an AABB that exactly matches the open volume of the landing bay.   Now, I'm not sure what I need to do with the x,y,z position part of this world-to-local transformation matrix, but... I assume I can at least apply the 3x3 part of the matrix to rotate the AABB of the smaller spacecraft into the orientation of the corresponding coordinate system (the local coordinates of the landing-bay object).  So if I can also figure out how to fiddle the position.xyz of the smaller spacecraft to place it in the same relative position as the landing bay (hopefully just one or two vector subtracts), then we can first perform a quick bounding-sphere test on the smaller spacecraft, which if does not pass (says "overlapping"), we can then compare the AABBs of the "landing bay" and spacecraft for overlap, which if does not pass (says "overlapping"), would might then lead to a full GJK test against whichever of the 5 sides of the landing bay box the AABB tests indicates are "overlapping".   Actually, it is probably much smarter to transform the AABB instead of the hundreds or thousands of vertices in the small spacecraft, and the resulting AABB on the small spacecraft will almost always tightly and efficiently enclose that spacecraft.   By simply skipping AABB or GJK tests against the 6th face of the landing bay,  we avoid any problems of the spacecraft not being fully inside the landing bay (on that side).  And by testing against the sides of the landing bay box one at a time, we don't have to detect that elusive "fully contained" situation.  However, that is at the price of needing to run the GJK up to 5 times instead of only once!   Of course, this doesn't work so well when the shape of the landing bay isn't some convenient shape like a rectangular box.   As an aside, the technique you described is exactly what I did when I designed a PS2 game engine under contract for a video game company in the 1990s.   Now I'm creating a much more advanced game/simulation engine, as general purpose as possible (for many kinds of simulations and games).  So the notion of a limited number of collision points just doesn't meet the requirements of this new engine.  Also, one focus of this engine is "procedurally generated content", most definitely including 3D objects.  In fact, that's how the engine creates objects now, though it can load existing artist-drawn objects too.  The point being, the engine cannot depend on "artist identified anything", because brand new, never-before-seen objects will be created on-the-fly by the engine, depending on what is happening in the game (plus profiles of the players generated by watching them play, plus many other factors).   Which means, by the time all this works, we'll be "old and tired too".  But hopefully not until "after"... hahaha.   But this also means we are spending a lot of time and effort to make highly-efficient, highly-general (and/or specialized, and/or self-adaptive) mechanisms for many aspects of the engine.   Thanks for your suggestion... it got me thinking in another direction.
13. ## inverted GJK --- you're a genius if you can solve this

What's wrong with this? Just use a BVH of some kind (probably AABB tree) and then treat your mothership mesh as a surface. Then you can do collision detection against the surface of the mesh. Suddenly the mesh doesn't even need to be "water tight", since you only care about surfaces. If you can build your tree through insertion the tree can even represent deformable meshes. If needed adjacency information can be computed upon the surface to allow rigid shapes to roll around without catching triangle or polygon edges. If tunneling is a worry a time of impact (TOI) can be computed and tunneling can be entirely avoided. If the TOI computation is too hard to engineer or not enough time can be spent to develop it alternative forms of tunneling avoidance can be used.     Actually, I already have a collision detection function that works on concave objects in a similar manner (essentially two parallel sweep and prune routines on the triangles in the two objects).  It is totally general and works on absolutely everything for some of the reasons you mention.  The problem is, that routine is 2x to 20x slower than GJK.  As you say, one of the advantages over GJK is the fact these kinds of approaches work on overlap of object surfaces, not object volumes like GJK.  After the first frame the test is faster due to temporal coherency (the triangle sorts are much quicker).  But still... too slow, which is why I'm looking for alternatives.   Thanks for the suggestion though.  It is a good one.
14. ## inverted GJK --- you're a genius if you can solve this

Could you elaborate on that a bit?  What is the "union"?  Something related to the minkowski sum or difference?  And does any efficient way exist to perform this computation?
15. ## inverted GJK --- you're a genius if you can solve this

Right, there are at least two difficult cases:   #1:  object starts to enter landing bay, and therefore overlaps both landing bay and mothership, but is not fully contained in either.   #2:  object is fully in landing bay, and therefore fully contained by both landing bay and mothership.   Case #2 is solved if some genius figures out an efficient algorithm for "fully contained".   Case #1 is still a problem.  Seems so easy visually... just not algorithmically --- if that's a word?   -----   It is easy to say "decompose huge objects into zillions of convex objects", but not so easy in practice for a great many objects.  Also, my engine is optimized for procedurally generated content, and making procedures that support making great looking objects is difficult enough, without also trying to make them aware of how to automagically decompose objects into convex objects.   Incidentally, imagine a huge egg-shape or spherical mothership.  You must break that into EVERY SINGLE TRIANGLE to get "convex shapes".  That's just insane --- a big mothership could have millions of triangles!   A better way is called for.  We just need to figure out what it is.