Alexander Lonin, head of the Polygonal Modeling Team at C3D Labs, Ph.D. in Physics and Mathematics, presents our new product, the C3D PolyShaper polygonal kernel, and discusses new reverse engineering tools, mesh modification, diagnostics, and repairing.
Technically, C3D Labs has introduced polygonal half-edge objects. It is inherited from the Item object, and its structure is similar to the Solid object. PolyShaper uses a topology object that provides the mesh handling functions. It can also handle segmentation over the mesh. This object will support any further polygonal functionality. New functions and classes will be in action_polymesh.h, similar to other action files.
To estimate the scalability of the new solution, and to check what meshes we can handle, the C3D Labs team has conducted a special stress test. The picture shows a chest CT scan. This is a standard STL file consisting of 25 mln triangles. Mesh sewing, i.e., creating the topology directly from this file, takes about 100 seconds. After that, we can apply a range of algorithms to the resulting mesh. For example, trimming with a plane takes about 50 seconds. In other words, such meshes can be handled, but they push the average PC to its limits.
Now, let’s discuss what new features we added to the solution over the last year. We have always focused on reverse engineering tools.
The picture shows two applications of the new object registration function. For now, this function offers two options: “mesh-to-mesh” and “mesh-to-shell”. The following picture shows the result of registering two partially overlapping scans taken from different angles.
We have implemented the simplest auto registration for apriori similar objects (e.g., a model and its 3D scan). Such a registration applies to an object in any orientation.
PolyShaper can fit analytical surfaces while respecting constraints related to the object’s position and/or size. The example above shows a cylinder which is fit while maintaining its perpendicularity to a given plane.
We have also enhanced the fitting of surfaces of revolution and introduced the fitting of extrusion surfaces. These tools can handle noisy scanned mesh regions. In such regions, we can identify the optimal axis of rotation or direction of extrusion, resulting in a correctly constructed surface.
We have also implemented major improvements for reverse engineering organic shapes. Currently, we have a prototype that only handles watertight meshes. This scan of the vertebra demonstrates how it works.
The algorithm automatically partitions the surface into quadrangular regions, approximates them with NURBS patches, and stitches the patches into a watertight shell with reasonably good G1 quality. You can see quite a few T-junctions in this model. These are the regions where a patch on one side is bordered by multiple other patches. There are methods for constructing a regular grid, but the results are not always guaranteed. Therefore, we initially constructed a shell with T-junctions.
Shown above is the same shell, but with edge rendering turned off. You can appreciate the surface's smoothness.
The next batch of algorithms is for mesh modification and preprocessing.
One of the new challenges for C3D Labs is fabric drape modeling. In the picture above, the middle image shows the original shell with some cuts made based on the previous analysis. The left image shows the generated cells of the bidirectional fabric, and the right image shows the resulting unfolded surface. If we attach it to the green point and flatten it, it should cover the shell without creasing.
Another product enhancement is the triangulation refinement feature. Suppose we have a rough triangulation of a parametric cylinder, as shown in the left image above. Now we realize that the mesh should be more detailed in some regions. We can define such a region, for example, with a cube as shown. The algorithm makes the triangles inside the cube no larger than a predefined size, while outside the cube, the size changes smoothly to avoid abrupt transitions.
Since we have an underlying parametric cylinder (we know the origins of the mesh), the refinement is smooth because we attach all new vertices to the underlying parametric model.
Uniform remeshing is yet another aspect of triangulation. It is known that all conventional shell mesh linearization approaches produce low-quality meshes with a large number of corrupted triangles. Such quality is sufficient for rendering but unsuitable for many other applications. Remeshing can significantly improve the quality of such meshes. It produces triangles with a given edge size that are as close to equilateral as possible.
Such remeshing also applies to meshes without any underlying parametric geometry. For example, the mesh shown on the left is obtained by the marching cubes method, while the mesh on the right is the result of uniform remeshing.
In some cases, the user should be able to vary the size of the triangles in different regions of the model. For this, curvature-adapted remeshing is used To appreciate it, consider the image of a piece of a turbine blade. The curvature at its edge is high. Therefore, it is desirable to have smaller triangles around the tip, while the rest of the triangles can be larger to simplify the model without compromising its quality.
To apply this approach when there is no underlying geometry, we need to estimate the curvature of the mesh. The classical discrete differential operator approach gives poor results with 3D scans. This can be seen in the left image. To make them usable, we have introduced another curvature estimation option: fitting a polynomial surface. This method produces smoother results, as you can see in the right image.
The result can be used to control the size of the triangles. In this way, we perform curvature-adapted remeshing.
In the picture above, you can see another example of remeshing a scanned model. Why do we need such remeshing? Most algorithms, including reverse engineering of organic shapes, work well on a mesh like the one on the right. Also, these meshes can be used in some CAE applications.
Reverse engineering of freeform surfaces also performs well on a remeshed mesh. The left image shows a model after curvature-adapted remeshing, and the right image shows a watertight NURBS shell built from the mesh.
Another interesting area we are still exploring is quad or quad-dominant remeshing. Essentially, partitioning a surface into quad patches for reverse engineering is only one step away from building a quad mesh. The picture above shows objects constructed with minimal effort. The mesh size is adjustable: it is larger on the left and smaller on the right.
Let’s now focus on mesh diagnosis and patching. The first thing the C3D Labs team did was to create automatic algorithms to eliminate degenerate triangles. Such triangles come in two types: needles and caps. There is also a third type of degenerate triangle, a blend of the first two. While it is relatively easy to fix needles, clusters of caps are much more challenging. C3D PolyShaper offers an automatic mesh patch algorithm for such situations.
So far, the prototype can close open mesh edges using front advancing as shown in the image above.
This algorithm is also suitable for patching holes of various shapes and complexity.
It is highly promising, as we need to partially patch holes, build bridges, and consider whether the neighborhood is an analytical surface or not.
Finally, a few words about the future of C3D PolyShaper. First, we will enhance the Boolean operations by introducing half-edge data structures and support for non-manifold surfaces.
Next, C3D Labs will continue to improve the organic shape reverse engineering and manual patching tools. We are going to introduce a range of smart brushes. We are also refining the mesh diagnostics and repairing tools.
Now about the new module positioning in C3D Toolkit. It is not a stand-alone solution. the module is an integral part of the comprehensive solution. The Converter module reads and writes files in many formats. The Modeler and Solver modules support many parametric modeling algorithms. The Vision and Web Vision modules offer high-quality rendering functions. All these work together within C3D Toolkit.
Alexander Lonin,
Ph.D. (Phys&Math), Polygonal Modeling Team Leader, C3D Labs
