Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 19 Mar 2004
Offline Last Active Aug 03 2012 02:09 PM

Posts I've Made

In Topic: Sphere-triangle dynamic collision

01 July 2010 - 08:56 AM

The term you may want to search for is "swept sphere".

There are 2 issues here:
1) time of impact
2) tunneling (fast moving sphere passing through triangles)

I will not go into #1, in many practical situations you can ignore it. Collision response will be less accurate, but hardly noticeable in most situations. I also have no idea how to implement swept sphere collision correctly, some else might explain it.

There is a workaround for #2 however, usually sufficient for most games; after you've integrated the sphere position, do a ray-test from the old sphere position to the new position. Then, whenever the sphere center has passed the triangle plane, you can project an approximate contact point onto the triangle, and move the sphere back so it no longer intersects. Unless your trimesh has lots of concave features such as 'v-cliffs' or other tight spots, this should work fine. If it does, you can do another ray-test when correcting the sphere position (recursively; every time you apply a correction). It should never be able to pass through triangles, but remember to add a max recursion or you may get stuck in an infinite loop (3-5 is usually ok) in tight situations.

One thing I would suggest though, is to collect all sphere-triangle intersection points, before correcting the sphere position. Not just the deepest contact intersection, but every single sphere-triangle intersection point. Store them in an array, something like this:

struct contact
float3 position; // intersection point on triangle surface
float3 normal; // triangle normal
float depth; // penetration depth
int faceIndex; // index of trimesh face (useful to look up surface info such as bounce, friction etc)

Some raw trimesh-sphere col-det code that may give you some ideas:

// collides collider with sphere
void CCollider::SphereTest(const float3 &pos, float radius, CContactGroup &contacts) const
// quick bounds test
if (!bounds.QuickSphereTest(pos, radius)) return;

// test faces
for (int i=0; i<facenum; i++)
const float3 &v1 = vert[ face[i].v1 ];
const float3 &v2 = vert[ face[i].v2 ];
const float3 &v3 = vert[ face[i].v3 ];
const float3 &fn = face[i].n;

// backface culling
if (DotProduct(fn, pos - v1 ) < 0.0) continue;

// get closest point on triangle
const float3 cp = ClosestPointTriangle(pos, v1, v2, v3);

// dist to point
const float depth = Distance(pos,cp) - radius;

// no penetration
if (depth > 0.0) continue;

// create sphere contact
contact c;
c.pos = cp;
c.norm = Normalize(pos - cp);
c.depth = -depth;
c.collider = this;
c.face = i;
c.id = face[i].id;
contacts.Add( c );


Then once you've collided the sphere against every trimesh and other spheres in your world, you can filter out double/similar contacts. Loop through the contacts, and compute the average of contacts that lie on the same plane/position (don't forget to re-normalize the contact normal).
For example when a sphere rests on the center of flat quad (consisting of two triangles), the sphere will intersect both edges, resulting into two contacts. Both contacts will have the exact same position, but contact normal (and depth) may be diverging. If you merge these, it will result into a single contact with a normal facing straight up.

Once your contacts are all cleaned up, you can correct (solve) the sphere intersections all at once.

And this code shows how the contacts are solved. 'pos' is the position of the sphere, and 'vel' is it's motion vector.

void Constrain(const float3 &plane, float3 &force)
const float dp = MAX( DotProduct(-plane,force) ,0.0);
return force += plane * dp;

// solves constraints
void CContactGroup::Solve(float3 &pos, float3 &vel) const
for (int i=0; i<contacts.size(); i++)
const contact &c = contacts[i];

// correct the sphere position
pos += c.norm * c.depth;

// correct the motion vector as well
Constrain( c.norm, vel );

Notice that, as well as the sphere's position, you need to 'correct' the velocity vector. Otherwise gravity force applied will increase the velocity each timestep, even though the sphere is not moving. Perhaps this is related to the problem you mentioned.

In the code above, the motion vector is simply 'zeroed out' in the contact normal direction, but you can easily add friction and 'bounce' effect.

Hope that helps.

In Topic: wxWidgets external mainloop

14 October 2009 - 03:00 AM

Found a solution: custom implementation of the WX functions, and replacing GetMessage with PeekMessage. Sadly, Windows-only code, but likely you can do the equivalent on other platforms, or even more likely you won't have this problem on any platform but Windows anyway.

Code snippet:
// initializes editor
bool CEditor::Init()
// already initialized
if (app) return true;

// create app
app = new CEditApp;

// initialize wxWidgets
if (wxInitialize(0,0)) {
Console.Printf(">>> wxWidgets initialized.\n");
} else {
Console.Printf(">>> Failed to initialize wxWidgets.\n");
return false;

// initialize app

// success
return true;

// processes events for editor
void CEditor::ProcessEvents()
if (!app) return;
MSG msg;
HWND hwnd = (HWND)app->GetWindowHandle();
while (true)
if (!PeekMessage(&msg, hwnd, 0, 0, PM_REMOVE)) break;

// unloads editor
void CEditor::Unload()
if (!app) return;
delete app;
app = NULL;

If you use SDL like I did, you must call run the PeekMessage loop before SDL_PollEvents, because SDL will steal *all* messages headed to the application, not only the SDL window. Make sure to pass the WX window handle to PeekMessage, or you will intercept the messages intended for the SDL window in the same way, and your SDL window will starve to death.

*Edit: It appears that "wxCheckForInterrupt" can replace the entire content of CEditor::ProcessEvents() in the above code, it does the exact same and is cross-platform.

[Edited by - remdul on October 14, 2009 12:00:46 PM]

In Topic: force required for body to reach certain height

11 September 2009 - 06:37 AM

Oh, wow.

Yes I meant the force to be applied as impulse, not over time, though the latter may be interesting as well (for now i want to keep things simple).

I figured g * m * d would give me something usefull, but when plugged in it didn't quite work in my simulation. Seems the force is far to small, so I must be missing something (perhaps something to do with timestep).

I also could not imagine it would be easy to calculate with drag. I'll have a shot at implementing the above.

Thanks guys!

In Topic: OpenGL Causes PC Squeaking noise

14 July 2009 - 10:21 AM

Original post by AndyEsser
Having only experience with nVidia cards, but a beeping noise (similar to a BIOS/Mobo Beep) suggests the card is under powered.

It's not a beeping noise. It sounds more like an old fashioned teapot with boiling water, albeit a not as loud. And it's not a glitch, according to nVidia it is a 'feature' (I guess just like diesel V8 makes a roar). AFAIK, it happens just same with systems properly equipped with a proper PSU.

In Topic: Foliage Rendering

14 July 2009 - 04:18 AM

@swiftcoder, I did brief attempt, but the result was a bit disappointing for dense foliage (such as in the above screens). But I think it should work fairly well for grass and 'thinner' foliage. Of course the downside is that you need to do the art (or at least the alpha channel) at 8x or more resolution. 2x or 4x wasn't enough in my tests to make a noticeable difference.

@Schrompf: why, sure:

alpha blended trees

Note that this is with depth-testing, without the glDepthMask trick, so it has some ugly edges (reduced by alpha-test with very low cutoff value). We render the skybox after all major geometry, so it would completely overwrite anything above the horizon.
You can see that quality wise, it is close to alpha-to-coverage. Of course, less flexible.
For low-end hardware and non-multisampled framebuffer we fall back to regular alpha-testing. This actually makes non-anti-aliased images look more consistent.

@B_old: thanks, nope it was created by me and one of our artists. cgtextures.com and mayang is a good place to start if you're looking for free high-quality textures.

On another note: at some point we had alpha-tested vegetation, with only 4 mipmaps (512x512) to keep the textures sharp in the distance. However, we got complaints about this being 'noisy'. It may also be bad for performance on low-end systems, mipmaps can reduce texture caching traffic since in ideal situations only the mipmap is transfered to cache rather than the entire texture.