PDA

View Full Version : Expanding 3D Objects!

uzu_manga
10-15-2002, 03:56 AM
I need to clone and expand a mesh... building a "shell" around the object so to speak. Anyone who knows how to do this with complex objects? C++ source is prefered, a plugin or script for 3ds max also works.

dorbie
10-15-2002, 04:01 AM
Extruding verts along their surface normals would be one simple way. Average the normals first ofcourse.

10-15-2002, 05:22 AM
dorbie's solution will only work with fully closed meshes. If there are any duplicated vertices on the same geometrical position (ie. adjacent edges of two polygons with different mapping) you'll get holes or - in the mostly worse case - a bunch of free floating triangles.
So you also need to fix this problem by searching for this "wrong" edges ("wrong" means: edges with the same position but not the same vertices) and create new polygons between them.

GeLeTo
10-15-2002, 05:58 AM
Here's one correct way to do this.
1. Break the mesh into convex volumes by using a BSP tree.
2. Get the set of planes for each volume. "Expand" the planes by adding some value to plane.D
3. Bevel the sharp edges by adding bevel planes (don't forget to "expand" them too) to the plane set.
4. Generate a mesh from each plane set.
5. CSG all expanded convex volume meshes.

This is a bit of overkill for complex meshes and also not very easy to implement unless you have a good BSP library at hand.

V-man
10-15-2002, 03:54 PM
dorbie's solution will only work with fully closed meshes. If there are any duplicated vertices on the same geometrical position (ie. adjacent edges of two polygons with different mapping) you'll get holes or - in the mostly worse case - a bunch of free floating triangles.
So you also need to fix this problem by searching for this "wrong" edges ("wrong" means: edges with the same position but not the same vertices) and create new polygons between them.

As long as the duplicate vertices have identical normals, no holes will occur. So all you need is a good normal computing algorithm that searches for these duplicates in your entire object.

The only problem is over expanding. The expansion could penetrate an oposing face on the same object and worst, could exit on the other side.

V-man

Sundy
10-17-2002, 12:58 PM
Tried Scaling the Mesh?

-Sundar

jwatte
10-18-2002, 06:52 PM
Scaling the mesh won't work right. Think about a donut. If you expand it, the inner hole will actually get bigger in the scaled version, instead of SMALLER which is what you want an "inflated" donut to look like.

Here's a solution that's usually sufficient:

1) generate the "fully welded" mesh of position verts. I e, collapse all verts whose position are (nearly) the same to one vert, ignoring normal and texture information

2) calculate the fully smoothed normal for each vert: add the face normal of all faces that share this vert, then normalize the result

3) move all vert positions in the direction of the thus-calculated vert normal, by your inflation distance

4) un-collapse the mesh, tieing all the "welded" verts back to all their ancestors (that you had to remember back in step 1)

dorbie
10-19-2002, 01:46 AM
Other parameters don't count for this calculation of shared normals, texcoords etc. Just the cross products, it will work. If there are degenerate tris and you don't delete (nasty you really should deal with that) the verts would be shared and they'd remain degenerate. The real problems occur with concave regions where geometry extrudes into eachother but that's another story.

[This message has been edited by dorbie (edited 10-19-2002).]

jwatte
10-19-2002, 01:46 PM
dorbie,

The algorithm I describe does reasonably well even for concave geometry and "reasonable" amounts of inflate. The reason is that the inner ("bottom") vertices will get normals that point "out" of hollowness. I e, for a "V", the normal for the vert at the bottom of the "V" would point straight up.

Of course, if you have a "U" and the two sides of the U contains verts with normals pointing straight at each other, if you inflate by more than the width of the "U" you'll get geometry interpenetration. Luckily, the rendered object will still look as you would expect it to (!) -- modulo Z fighting at the interpenetration, of course :-)