Erwin Coumans wrote:Hi John,
This realtime-tuning looks really great, I will check it out again.
I'm also interested in your patch-collision detection. Are they bezier-patches? It would be great to extend COLLADA physics with such primitives. Do you have description of your curve/patch data?
There is support in Bullet for triangle-generation-on-the-fly, which could be used for a collision detection implementation.
Thanks,
Erwin
Hi Erwin,
The patches are bicubic Beziers, exported directly from 3DSMax. Any bicubic patch can be supported: Bezier, b-spline, tensed b-spline, Catmull-Rom, tau-spline, beta-spline, cardinal-spline, Hermite, etc. In practice I have only used Bezier, Catmull-Rom, and b-spline. Bezier is very useful in that you can have sharp edges as well as smooth edges between patches. It's also common to convert NURBS to Beziers with good accuracy (for time consuming ops, then convert back to NURBS). Thus, a NURBS model can be converted to an equivalent Bezier model. While working on a project with
http://npowersoftware.com/, Gary (lead dev) exposed some code to allow their NURBS patches to be converted to bicubic Bezier patches for direct use and export from 3DSMax. It would take a little bit of work to be more useful for game/sim work, but it was very cool to be able to take a quickly created NURBS surface, convert to Max bicubic Bezier, then export and interact with in real-time with the driving sim.
As far as data format, bicubic patches are 4x4 matrices (16 floats) per data channel. For Vec3's (geometry), it's 4x4x3 (x,y,z), texture coords, Vec2's, 4x4x2, and if desired, normals as 4x4x3 (perhaps to match Max's smoothing groups). Any data channel can be interpolated by the bicubic patch, though normals would have to be renormalized. For Amazing Curves Racing, the normals are computed from the patch surface (compute tangent, bi-tangent, cross, normalize, etc.). I also support general curves (track, objects), as well as so-called 'non-parametric' (NP) surfaces, which must be aligned to a regular grid (terrain only, limited use). NP surfaces allow fast terrain collisions (really just compute height; a full ray-patch intersection would still be complicated).
I am aware of the following methods for ray-patch collisions:
1. Tessellation to triangles. Works fine, as can be integrated into existing systems easily. However, unless fine tessellation, won't get full benefit of curved surface smoothness (very useful for driving sims).
2. For Bezier only, de Casteljau subdivision. Easy to implement, elegant, but slow.
3. For Bezier only, Bezier Clipping: clips away and computes new sub-Beziers (final step does a more direct computation). Not clear how fast this would be for real-time usage (perhaps useful for a generalized HW implementation).
4. Newton iteration with good initial guess (used in ACR). Requires extra data structures and various tricks (caching, etc.), but so far works fast enough for 64 cars for an online simulation (effectively 128 cars) on P4 3.2 or faster (50-100 FPS). IIRC, typically takes just 1 iteration to get a good answer, though for a miss, will iterate a few times before giving up. Initial root finding setup is somewhat expensive. Could probably use more optimization (currently all in C++, no fancy alignment, no asm, etc.).
