Showing posts with label PAL. Show all posts
Showing posts with label PAL. Show all posts

Wednesday, October 27, 2010

Convex Hull Generation in Blender

Convex hulls are very useful for a number of optimized calculations such as fast intersection tests, fast spatial subdivision, and other early-out's used in computer graphics, computational physics and robotics.

When I implemented convex hull generation and convex decomposition in PAL I first used qhull and leveraged code from tokamak physics, but then used code by Stan Melax and John Ratcliff for PAL. Recently my work at Transmin has required generation of a number of Convex hulls, and so I combined these snippets of old code to create a plug-in for Blender.

The Blender plugin creates a bounding convex hull of the selected object.
It calls an external executable 'convex' which creates a convex hull based on an intermediate OBJ file.

Installing the plugin requires you to compile the code to generate the 'convex' executable, and copying the python code into Blender's scripts directory.

To compile the C code on linux/osx:
g++ createhull.cpp hull.cpp -o convex

Place the object_boundinghull.py script in your ".blender/scripts" directory.

On OSX Blender default installs to:
/Applications/blender-2.49b-OSX-10.5-py2.5-intel/blender.app/Contents/MacOS

Once the plugin is installed you can start creating convex hulls. You can select an object in blender and cut it into smaller objects to manually decompose the hulls. To do this, you can use the Knife tool (K) or split objects in edit-mode with 'P'. (Selection tools like 'B' and manual alignment of cameras ('N', Numpad 5) will help a lot).

Once you have the objects you would like to generate hulls for select one, and run the "Bounding Convex Hull" script. It will ask you to confirm the creation of the hull. The new hull will have the same name as the original object and have ".hull" appended to its name.

The plugin will generate a new object that represents the convex hull of the selected object, with the same transforms as the original object. (Ctrl-A to apply all down to the mesh, note: Blender 2.49 does not let you apply translation transforms, but Blender 2.5+ does). You can then decimate the hull to reduced the number of tri's used to represent your object. (Editing F9, under modifiers, select 'Add Modifier', decimate, and reduce the ratio).


Now your ready to export your scene for all your raytracing and collision detection needs!

Thanks to Transmin Pty Ltd for allowing me to release this plugin back to the Blender community under the GPL.

Follow the link to download the Blender Bounding Convex Hull plugin to generate editable bounding volumes directly in Blender.

Tuesday, March 09, 2010

Pixelux Digital Molecular Matter engine - Free license soon!

AMD have just announced there will be a free version of the DMM engine. It sounds like it will be closely integrated with Bullet Physics and provide OpenCL support.

I'm looking forward to this as DMM is the only realtime finite-element (FEM) based physics engine around. I'm interested to see how well it works.

Hopefully I can get a copy soon and some time to integrate it into the Physics Abstraction Layer.

Here is a video of DMM to refresh your memory:

Friday, January 22, 2010

Critical Mass Labs Presentation

Together with Ronald Jones from iVEC, I organized a presentation from CMLabs.

Michel Carignan, lead product engineer from CMLabs, discussed the internal structure of Vortex, a real-time physics-based simulation engine with collision detection. Michel covered issues in maintaining interactive performance with complex dynamical systems, and a number of applications from the areas of vehicle simulation, robotics and control.

Details of the constraint solver, collision detection, scene graph interaction, and the interactive editor were covered.

Vortex has a number of interesting features designed to support the simulation of cranes / booms with rigid-body chains for representing wires, etc. The simulation system features a highly accurate and fast solver (iterative/LCP, so I'm not sure what is so special about it..) and most constraint interactions are modeled as simple spring-damper systems. The package does not support continuous collision detection, but has 'Fast' objects, which perform iterative collision detection. A simple way to save computation time, while still achieving the goals of a CCD system, by putting some labor onto the programmer.

Constraints can be 'relaxed' to different degrees, enabling 'wobbly' links, eg: ropes. Each constraint can have a maximum force allowed, and this enables frictional forces with the ground to be simulated in a generic manner.

Vortex also has a few additional novel features including SPH fluids (and normal RB hydrodynamics), simulation of sonar sensors, cameras, etc.

One area where CMLabs seems to have put a lot of effort is the validation of the physics engine - quite an interesting topic, especially in validating motor models, etc.

The key new feature seems to be an interactive editor, however I was disapointed to hear they were building on their own file format and not supporting COLLADA (or let alone any other common 3d package like SolidEdge or Havok's physics format)

In any case it was an interesting talk, but unfortunately I had to leave early. Hopefully I can get the slides.

Thursday, December 31, 2009

Physics Engines Roundup '09

Physics engines are starting to conslidate into a few key solid products. When I first began the Physics Abstraction Layer (PAL) project there were only 4 freely available physics engines: Dynamo, ODE, Tokamak, and Newton (AERO and Dynamechs were also available but weren't really stand alone engines, I guess the same could be said about Dynamo). What followed was an explosion of physics engines. This years big trend has been parallelization (usually in the form of GPU support) and porting to Mac OS X.

PAL had some big changes in 2009 as well, including the new CMake build system, generic bodies, soft bodies and more.

Here is a run-down on 2009's progress in the freely available physics engines:
  • Bullet Physics: Bullet went official in a big way, a number of movies, games, DCC packages, etc using and supporting the engine. Some big additions were on the parallelization front, with the CUDA/GPU code maturing, and the support from AMD to add OpenCL to Bullet. The engine seems to be stabilizing and appears to have clearly taken the Open Source physics engine crown.

  • Chrono Engine: Added support for CUDA/GPU, Linux, and Matlab (vaugely).
  • Havok: No major changes (faster raytracing), mostly bugfix updates. Public release of the behaviour tool.

  • Newton Game Dynamics: Newton 2.xx was made public in 2009, with a whole raft of big changes (too many to list fully here), parallelization, multiplatform (Linux, Mac OSX, iPhone), Pascal, and a slowly maturing GPU/CUDA/OpenCL port.

  • nVidia PhysX: Official WHQL drivers for PhysX GPU acceleration.

  • OpenTissue: Improved SPH support, and OS X port.
  • PhysSim: Was renamed Moby, and has progressed with more examples and improved solvers.
  • Simple Physics Engine: Improved parallelization and Linux, Mac OS X, and iPhone support.
  • True Axis: Launched an iPhone game with their physics engine.

And that about wraps it up.

Saturday, May 30, 2009

Link post

Some assorted interesting sounding tech:

Thrust is a STL-like tech for CUDA programming. Could be interesting, certainly looks like it is easier to use than CUDA, but just from my feelings it probably won't be worth anything until nVidia let multiple CUDA functions execute in parallel..

5 optimization tips for CUDA, a nice succinct roundup of some good performance tips for CUDA, including Arithmetic Instruction optimization.

DANCE framework for Dynamic Animation and Control, definately something I want to check out for potential synergy with the Physics engine Abstraction Layer. Proper animation controllers is something PAL lacks.

ReactPhysics3d a new open source physics engine, very much in the early stages of development, I've seen a number of engines grow in time, I hope this one succeeds too, but it will need to find a niche if it is to survive..

Predictive-Corrective Incompressible SPH is a paper on estimating the SPH state without explicitly evaluating it, thereby saving some CPU cycles. I actually had a similar idea, so maybe this is a path for further research. Also on the SPH front, Co-rotated SPH for Deformable Solids, the idea is great, not convinced by their particular implementation though..

Perhaps these ideas might make it into the SPH routines for PAL..

and on the lighter side;

2D boy's prototyping framework for the world of goo.

Saturday, April 18, 2009

Soft Bodies

Since Bullet physics engine added soft body support that brings the number of publicly freely available physics engines that have soft body support to 3. PhysX, OpenTissue and Bullet. So that seemed like enough to justify adding softbody support to PAL.

PAL now supports cloth/patch based soft bodies, and tetrahedral deformable bodies.

Bullet has basically designed the softbody system as completely separate from the rigid body system, so this makes it a great system to abstract since it will make it possible to implement a softbody system that does not directly rely on the underlying physisc engine, bringing softbodies to ODE, Newton, and friends that do not have it yet. Same plan is for the SPH fluid code I've written, but those are both still on the TODO list to integrate to PAL.

Of course, the remaining issue is how to generate the tetrahedral descriptions.


Some options I've investigated:

  • The PhysXViewer should be able to do it.
  • Apparently Qhull can generate tetrahedron (how convenient!) using the 'qhull d QJ i' option. This would be a good option since Qhull is a widely employed library.
  • TetGen, seems to be a rather large library, given its special purpose nature (generating tetrahedron), but says it is optimized for finite volume/element methods.
  • GNU Triangulated Surface Library says it can create tetrahedra, but I'm not sure if this is only for isosurfaces.
  • NETGEN claims to create tetrahedral meshes from CSG
  • Cubit is a massive library from sandia that claims to generate tetrahedral meshes.
  • libmesh can work with tet4, but I've not investigated what inputs it can take.

And during my googling I came across SLFFEA an open source finite element analysis tool. Cool!

Monday, April 13, 2009

Shared Libraries

Shared libraries, dynamic linked libraries, .so, .dll, .dylib, whatever you might call them seem to be a bit of a black art of programming. Especially when you mix C++ into the picture.

One key part of PAL is the self-registering plugin system. This allows extra functionality to be extended to the system on demand. It was very useful to allow the development of various simulation systems where fixes or alterations to the physics system can be loaded on demand.

It also greatly simplifies the whole process of creating/managing objects. The big catch is getting it to work in a portable cross platform manner.

The basics of the system is this:
Abstract factory which will have plug-ins self register via either a static constructor, or add themselves to a list of available constructors that can be retrieved via a shared object function call.

For staticly constructed objects, its not a big deal, just have a single static version of each object which registers itself with the factory. This works fine as long as those static variables are initialized. Unfortunately, the Microsoft compiler does not link those symbols from a static library, unless a function in the static library is explicitly called. So your options are to link all the objects to your program, or have a 'stub' in the static library, that you are forced to call to populate all the objects. PAL follows this latter approach. (Note, if you put that static stub into a separate header file, you can save yourself a lot of include header problems)

For dynamic libraries, well, it's not such a big deal for Windows. Under MSVC you just create a DLL project, and load the library with LoadLibrary and GetProcAddress. Ofcourse you need to remember to '__declspec(dllexport)' the functions you need to access, or write the def file (far too complicated). Then make sure the compiler exports the symbols.

MacOSX didn't pose great problems either, again, just use dlopen and dlsym. Remember to compile with '-dynamiclib'.

That brings my to GCC/Linux. This one was a bit tricky, and I could only solve this with the kind help of B. Watson over on #slackware. The problem with GCC is the way it handles run time type information. You need RTTI for dynamic_cast's etc, to work. This is relatively critical for design patterns such as abstract factories and virtual inheritance, which are heavily employed in PAL.

Under Linux to open a shared object, dlopen and dlsym will do, however you need to specify RTLD_GLOBAL, otherwise the type info will be stored locally and not globally. Now this normally doesn't cause a problem, but with GCC class types are compared by pointer references and not strings, so of course, with each object having its own local address space, the code just wont work!

That fixes one problem, the other is getting the symbols to export. By default GCC won't export all the symbols that you need. To force GCC to do this we need to pass through to the linker from the compiler the '-rdynamic' flag. But, alas, we are hampered again, we need to actually make sure the symbols are visible. GCC has introduce the ability to have private/local symbols, and if only one person specifies something to be private then the whole subsystem becomes private. No major dramas though, just specify '__attribute__ ((visibility("default")))' everywhere.

So now finally your ready to compile a linux shared object with position independent code:
-fPIC -shared -rdynamic
But it still doesn't work!

Yes, for some reason I don't know, you need to make sure your MAIN program is also compiled with the '-rdynamic' flag.

I guess the lesson for the end of the day was, '-rdynamic' is your friend.

Heres a useful snippet that summerizes all this:

REMEMBER: Export ALL symbols (shared or not!)
Linux: RTLD_GLOBAL & rdynamic!



#if defined (OS_WINDOWS) || defined(WIN32)
# define DYNLIB_HANDLE hInstance
# define DYNLIB_LOAD( a ) LoadLibrary( a )
# define DYNLIB_GETSYM( a, b ) GetProcAddress( a, b )
# define DYNLIB_UNLOAD( a ) !FreeLibrary( a )

struct HINSTANCE__;
typedef struct HINSTANCE__* hInstance;

#elif defined (OS_LINUX) || defined(OS_OSX)
# define DYNLIB_HANDLE void*
# define DYNLIB_LOAD( a ) dlopen( a, RTLD_LAZY|RTLD_GLOBAL )
# define DYNLIB_GETSYM( a, b ) dlsym( a, b )
# define DYNLIB_UNLOAD( a ) dlclose( a )
#endif


To compile:

OSX:
main:
g++ main.cpp -o main
DLL:
g++ shared.cpp -o shared.dylib -dynamiclib

Linux:
main:
g++ main.cpp -o main -ldl -rdynamic -fPIC
g++ shared.cpp -o shared_single.so -fPIC -shared -rdynamic


And would you believe it took me almost 3 hours to figure this all out. (At least I didn't end up having to write my own RTTI system like the last guy.

You can check out the PAL self-registering abstract pluggable factory in the code. (see also the test programs and makefiles).

Monday, February 16, 2009

PAL evaluation - evaluated

Found a nice post evaluating my evaluation of PAL. Evaluating Physics Engines For Games - PAL.

I'm working with Evan author of Physsim on a more indepth analysis of some of the collision cases in the paper. What a timely post.