During new year holidays, the development on the Freestyle branch was quiet as the dev team was looking into the longstanding instability issues regarding the view map creation. As described in the previous blog post, the main cause of the instabilities concerning the view map constructoin was a bug in the previous image-to-world inverse transformation algorithm. In general, a 2D point in the image space cannot be transformed into a corresponding 3D point in the world space by means of the inverse of a projection transformation matrix since the 2D point does not have a Z component. The previous image-to-world conversion algorithm did the job by relying on an assumption that the unknown Z component of a 2D point to be converted could be substituted with a single global value that depended on the spatial extent of the scene being rendered. This assumption works well when the 2D point is transformed into a 3D point near the center of the scene. If this is not the case, however, the previous 2D-to-3D conversion yields an erroneous 3D point that leads to a fatal “out of range” error.
In order to address the issue above, a new iterative solver of the image-to-world inverse transformation problem was implemented. Instead of directly solving the problem in the backward direction from the 2D to 3D space, the new solver starts with an initial guess of an approximated solution and asymptotically approaches to the true solution by iteratively performing the forward 3D-to-2D transformation and improving the approximation. Preliminary tests with one simple and another complex scene showed that the solver is stable and quickly converges. The following two images are experimental results with the latter test scene (consisting of 71.7K vertices and 70.6K faces).
The left image is a render of the scene with the internal renderer plus Freestyle. During the rendering with Freestyle, 8193 2D points (i.e., intersections of feature edges in the 2D image space) were converted to 3D points by the new solver. The right image shows the distribution of iteration counts. As you see, the solver converges to a solution with more and less 20 iterations. The stopping criterion is a residual distance between the true and approximated solutions less than 1e-6 Blender Unit (BU). It is remarked that mesh data in Blender is represented with single-precision floating-point numbers (i.e., the number of significant digits is 6), so that a residual distance less than 1e-6 BU is negligible. A major drawback of the new algorithm is its computational cost. The previous algorithm required 106 floating-point operations for a 2D-to-3D conversion, while the new algorithm requires 30N + 9 operations where N is the number of iterations, meaning that the new algorithm carries out 609 (about 6 times more) operations in the case of N = 20. The higher computatoinal cost is conpensated by the numerical stability the new solver provides.
Branch users are encouraged to experiment with the latest revision of the branch and see if the stability with regard to the view map creation has been changed. If you run into new problems, please let us know (through blog comments, by email, via the BA Freestyle thread, and so on). At the moment any clipping does not take place, so that objects behind the camera may still result in unexpected strokes.