For this project, I set out to create a program that would take a mesh figure and render it with the characteristics of amate paintings, which include:

•         Segmentation of Salient Parts

•         Repetition of design elements

•         Silhouette Outlining

•         Decorative borders

•         Second Contour

•         Use of bright colors

The techniques I used to simulate some of these characteristics can be divided into four categories:

1. Silhouette Outlining
2. Second Contours
3. Segmentation of Salient Parts
4. Pattern Elements
   
   
   

The following briefly describes each of these techniques:

1. Silhouette Outlining

This is done by finding the occluding contours, which are the locations of depth discontinuities from the current viewpoint, i.e. locations where the surface normal is perpendicular to the viewing direction (N·V = 0).

For meshes, this involves finding the edges that connect back facing polygons to front facing polygons, but the problem is that just doing can create noisy outlines as shown below:

To alleviate this problem, we interpolate the normals within the polygon face just like it is done with phong shading.

Results:

2. Second Contours

This refers to an additional contour found inside the silhouette that you often find in amate paintings.  To create this I use  the surface normals and view vectors to determine offset directions so that the outline moves towards the inside of the mesh.  I use mesh feature size to determine length of offset so that it is consistent among different sized figures.  Then, just like I did with the silhouette, I interpolate the points to create a smoother curve, but I also add discontinuities to give it a rougher look like something being done by hand.
 

Results:

3. Segmentation of Salient Parts
 

Most algorithms that do segmentation of salient parts of a figure are based on the minima rule theorized by Hoffman and Richard in their 1984 seminal paper “Parts of Recognition.”  In that paper they state that human perception divides shapes along negative minima of the principal curvatures, i.e. it divides objects into parts along the concave discontinuity of the tangent plane.  Hoffman, along with Singh later added further to this field with their 1997 paper ““Salience of Visual Parts.”  In this paper they state determination of salient parts is based on size relative to the whole object, the degree to which it protrudes, and the strength of its boundaries.

In recent years, there have been many publications dealing with the segmentation of 3D objects.  These include:
 

–        Clustering Techniques

–        Region Growing

–        Iterative Clustering

–        Spectral Clustering

–        Feature Point-Based Clustering

–        Fuzzy Clustering with Graph Cuts

–        Fast Marching Watersheds

–        Gaussian Curvature

–        Snakes-Based Methods

–        Feature Point and Core Extraction

The technique I ended up deciding to use is the last one listed above developed by Sagi Katz, George Leifman, and Ayellet Tal and explained in their 2005 paper “Mesh segmentation using feature point and core extraction.”  Their approach can be divided into three steps:

1. Conversion of the mesh to Multi-Dimensional Scaling (MDS) Space
2. Finding prominent Feature Points
3. Core Extraction via Spherical Mirroring
    
   

This techniques are summarized below:

MDS uncovers the geometric structure of a set of data items from similarity information about them, by representing dissimilarities as distances in an m−dimensional Euclidean space. The more dissimilar two items are, the larger the distance between them in this space.  In this case, the geodesic distance between points on the mesh is used as the dissimilarity between them.  Stress functions are then used to measure the degree of correspondence of the distances between vertices:

In the above equation, delta is the geodesic distance between vertices and d is the Euclidean distance between their corresponding points in the MDS space.

What all this essentially does is to stretch out the figure so that all the salient parts become extremities.  The benefit of this is that it makes the segmentation algorithm pose-invariant.  For example, segmentation results would not differ much between a figure of a human with folded arms and without folded arms.

The next step is feature point detection.  Feature points are used to distinguish the salient parts and are defined as local maximum of the sum of the geodesic distance function:

And that reside on the convex-hull of the figure in MDS space.

Example of Feature Points:

The next step is extraction of the object core via spherical mirroring.  A sphere bounding the object is found and then vertices of the mesh are mirrored using the following formula:

where R is the radius of the sphere and C is the center.  By doing this, vertices that correspond to the core component will reside on the convex hull of the mirrored shape, while feature points will become internal to the hull.  The figure below shows the basic idea of how this works.  On the figure to the left, the green curve corresponds to the points that belong to the core component, while the blue curves correspond to points that belong to salient parts of the figure.

Results:

As you can see from the image above, one problem that still remains is the way that the mesh is divided between segmented parts as they come out very rough as opposed to a more visually appealing smooth curve.  This can be improved by incorporating a better cut refinement algorithm.

4.  Pattern Elements
 

This was the part I had the least time to work on, and thus is not very robust and the results are not that visually appealing.  I basically create a set of parametric curves and randomly distribute them to faces on the mesh.  This can be greatly improved by creating a smarter algorithm for distributing the patterns across each segmented part.  Also, I would like to make the patterns rotation-invariant so that no matter what direction the object is facing, the orientation of the pattern will remain the same.

Results:

 Looks better on a bird:

Implementation
 

The program was built using OpenGL, GLUT, GLUI for the user interface, and trimesh for loading PLY files.

The program allows the user to show or hide the silhouette, the second contour and the patterns.  Also, you can randomly reassign the colors of the second contours, the model, and the patterns.

Future Work

 
As mentioned before, there still needs to be a better algorithm to cut the mush along the segmented parts.  This could be done by using snakes or a minimum cut algorithm.  The thing that needs the most work is pattern creation and layout to get more visually appealing results and closer to what you would find in amate paintings.  Another option that I would like to add is the ability to for the user to manually input a pattern design.  For example, the user could draw a pattern on a designated window, and that pattern would be used and automatically assigned onto the mesh. 

References

Please refer to the links pages for all the references.

Power Point Presentation