John Ratcliff's Code Suppository

A place where I insert my code into the anus of the Internet.

 

Tuesday, May 06, 2008

SplitMesh in development release



I have just uploaded an extremely early developer release of my SplitMesh tool. You can download and install it using this link.

Let me give you a really quick walk-thru. The download is only about 8mb and comes with a handy Windows installer. Once it is installed, go to the start menu and run SplitMesh.exe

Once the program has started up you will see a series of yellow concentric circles on the screen that represents the current split plane. You can move the split plane up and down using the Plane-D offset slider. You can also use the combo box to change the main axis of the split plane. Even though this demo just lets you set up the X, Y, and Z axis, the code doesn't care what the plane equation is. On a future drop I will have some sliders that let you freely orient the split plane on all axes.

The next thing you need to do is import a Wavefront OBj file to experiment with. I have provided several with the install. Simply browse to "\Program Files\SplitMesh\media\PhysXViewer"

You might start by loading the file 'sphere.obj'. The character model 'beshon.obj' (pictured above) is also interesting to play with.

There are a number of checkboxes that allow you to selectively turn on and off the various visualizations of the exploded split mesh.

This release has the source code in it but, as I said, it is still in an early stage of development and does not represent what the final source will look like.

The finished version will be provided as a single CPP file which will allow you to split any mesh into two perfectly capped/closed meshes in a single API call.

This version has a number of bugs in it which I am still working on. I just released this build because it is kind of fun to play with the interactive visualization of the split mesh.

Right now my main blocking points are:

(1) Sometimes when I walk the edges to come up with perfectly matched polygonal rings, it fails. You will see this indicated at times when the split mesh is not properly capped.

(2) This version does not yet deal with holes. An example of a whole would be if you cut say a drinking glass in half. This is still a major todo item.

(3) Sometimes it classifies convex polygons as concave; I'm not quite sure why yet.

In the visualization if you see a capped surface in green, this indicates that it the polygon was properly identified as a convex surface. The triangulation will fan out from the center of the polygon.

If you see a split surface colored in a more reddish tint, this indicates that the polygon was detected as being concave and was sent through a more robust triangulation routine that can handle this case. I note that there are some cases where I still flag convex polygons as concave; I haven't quite figured this one out yet.

Here are the features I intend to add to the tool and the order of their release.

Release version #1:

(1) Should handle all cases for split meshes *without* holes.

(2) Will come with a single CPP file 'SplitMesh.cpp' and a header that prototypes a method that will allow you to split a mesh by a plane in a single function call.

(3) Will come with a simple console application 'SplitMeshObj', which will read a Wavefront OBJ file in, split it by a plane, and write two Wavefront OBJ files out. The only source required will be SplitMeshObj.cpp, SplitMesh.cpp and SplitMesh.h

(4) It will include the full interactive graphics demo as above to experiment with your own meshes.

(5) It will include a revised copy of the ConvexDecomposition library which will use the new SplitMesh routine to produce much more efficient and effective convex decomposition solutions.

Release #2

(1) Will handle splits with holes.

(2) Will allow the user to add perlin noise to the split surface to create jagged or rough edged splits.

(3) The convex decomposition library will be revised to return not only the convex hull pieces, but also the corresponding fracture graphics.

Release #3

(1) Will add support for textures, U/V co-ordinates, and user provided per-vertex interpolants.

(2) Will be integrated into the Nvidia PhysX SDK to demonstrate real-time fracture of graphics models, using the convex decomposition library and the create dynamics toolkit.

3 Comments:

  • At 3:36 PM, Anonymous JamesH said…

    Thanks for all of your work John, your Convex Decomposition code proved invaluable to me and I point as many people as I can to it. Really looking forward to these next steps.

    The link to the source by the way is incorrect.

     
  • At 5:10 PM, Anonymous Sean Barrett said…

    I haven't looked at your code, but I believe there is a missed case in the paper you linked to:

    The algorithm works as long as rings do not touch. [...] However,
    the current implementation ignores the case of touching rings, since
    this case can not occur if the original mesh was a true “volume”.


    Now, it may be that you said "hey, that's not general enough for a general purpose routine, I'm not going to accept that restriction anyway". But as far as I can tell, they're wrong that this case cannot happen with a "true volume" in the first place, so this is something you definitely need to implement.

    Consider two bent tubes (as shown in their illustration) which (unlike their illustration) merge together at some point. At the point that they merge, the two rings will be touching.

    Now, it's true that if you were building this shape in 2D, you wouldn't bother having an edge that's shared by both, since you'd be dividing the space between them for no reason. And you can't generate an edge between them by clipping, because this would require two coincident polygons at the clip location.

    But you CAN have an edge already there! At the point where the two tubes join, they may have a shared edge that's a sort of saddle point. If the clip plane passes exactly through that edge, obviously that edge will be output as part of the (non-plane) polygons, on both sides.

    To give an explicit example, which you can use to construct a test case, consider the letter "V" extruded in 3D. Consider the bottom "point" of the V; since it's a solid object, it's actually got some thickness. The bottom edge of it may be flat not a point, even, but the inner edge of the bottom of the V is the relevant part. That inner edge is shared by the two polygons forming the inner faces of the sides of the V.

    Align that inner bottom edge to integer coordinates (to make sure it's produced exactly on clipping), and then try clipping a horizontal plane through that edge.

    There might be some more complicated cases that come into play once you've got the hole-handling, too.

    There may also be similar cases for vertices (at a concave intersection of 3+ polygons), I'm not sure, I didn't bother thinking it through, and I didn't read enough of the algorithm to see if it could break anything.

    (Some of this stuff is basically the boundary case for switching from hole to non-hole.)

     
  • At 1:03 PM, Anonymous John Hurliman said…

    I'm eager to see any new development on the convex decomposition library

     

Post a Comment

<< Home