{"id":170,"date":"2024-08-20T20:19:46","date_gmt":"2024-08-20T20:19:46","guid":{"rendered":"https:\/\/summergeometry.org\/sgi2024\/?p=170"},"modified":"2024-08-20T20:19:47","modified_gmt":"2024-08-20T20:19:47","slug":"approximating-surfaces-with-meshes-some-experiments","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2024\/approximating-surfaces-with-meshes-some-experiments\/","title":{"rendered":"Approximating Surfaces with Meshes: Some Experiments"},"content":{"rendered":"
\n
\"\"<\/figure>\n<\/div>\n\n\n

Project Mentor:<\/strong>\u00a0Nicholas Sharp\u00a0<\/p>\n\n\n\n

SGI Volunteer:<\/strong>\u00a0Qi Zhang<\/p>\n\n\n\n

This blog post is a follow up to “How to match the \u201cwiggliness\u201d of two shapes”, where we discussed the metrics we use to measure the similarity between two surfaces. In that post, we briefly talked about approximating a surface by using a regular grid to generate vertices for an approximation mesh. There we observed that as we increased the number of vertices, the surface approximation error decreases. This is somewhat intuitive – as you increase the “fineness” of the approximation mesh, the more closely you would expect it to approximate the actual surface. However, in practical applications we aim to keep the number of vertices as low as possible, in order to reduce both memory space and the amount of runtime computation.<\/p>\n\n\n\n

So what can we do to improve the surface approximation without increasing the number of vertices? Are there better ways to select vertices – such that we can minimize the chamfer distance error? This is what we will be exploring in this post.<\/p>\n\n\n\n

Regular grids<\/h2>\n\n\n\n
    <\/ol>\n\n\n\n

    Before we try different ways of selecting vertex positions. Hence we repeat the same experiment with a few different surfaces, using a regular grid to generate mesh vertices. First we start with three basic cases with different gaussian curvatures:<\/p>\n\n\n\n

      \n
    1. Sphere function (positive gaussian curvature)<\/strong><\/li>\n<\/ol>\n\n\n\n
        <\/ol>\n\n\n\n
        \n
        \"\"
        Figure 1. Sphere function approximated with regular grid vertices.<\/figcaption><\/figure>\n\n\n\n
        \"\"
        Figure 2. Log-log error plot of grid vertices dimensions and chamfer distance error for the sphere function<\/figcaption><\/figure>\n<\/div>\n\n\n\n

        2. Saddle function (negative gaussian curvature)<\/strong><\/p>\n\n\n\n

        \n
        \"\"
        Figure 3. Saddle function approximated with regular grid vertices.<\/figcaption><\/figure>\n\n\n\n
        \"\"
        Figure 4. Log-log error plot of grid vertices dimensions and chamfer distance error for the saddle function<\/figcaption><\/figure>\n<\/div>\n\n\n\n

        3. Quadratic function (0 gaussian curvature)<\/strong><\/p>\n\n\n\n

        \n
        \"\"
        Figure 5. Quadratic function approximated with regular grid vertices.<\/figcaption><\/figure>\n\n\n\n
        \"\"
        Figure 6. Log-log error plot of grid vertices dimensions and chamfer distance error for the quadratic function<\/figcaption><\/figure>\n<\/div>\n\n\n\n

        So far everything works well similarly to the previous blog post – the error decreases consistently as the grid resolution. <\/p>\n\n\n\n

        In order to really visualize the limitations of using the regular grid to sample points on the mesh, we decided to also include a more “extreme” function that looks harder to approximate – the Cross-in-tray function<\/a>, which has a few asymptotes. <\/p>\n\n\n\n

        4. Cross-in-tray function<\/strong><\/p>\n\n\n

        \n
        \"\"
        Figure 7. Cross-in-tray function approximated with regular grid vertices<\/figcaption><\/figure>\n<\/div>\n\n\n

        For this function, we noticed something unusual. When we increase the grid resolution from 6×6, to 7×7, to 8×8, we notice a sharp increase, then decrease in error, unlike the consistent decrease in error as we saw before. <\/p>\n\n\n

        \n
        \"\"
        Figure 8. Error plot of grid vertices dimensions and chamfer distance error for the quadratic function<\/figcaption><\/figure>\n<\/div>\n\n\n

        We decided to visualize what might be causing this in the figures 9-11 below, where the green transparent surface represents a close approximation of the actual surface, and the magenta surface shows the surface generated by sampling the regular grids with the different dimensions mentioned .<\/p>\n\n\n\n

        \n
        \"\"
        Figure 9. Approximation with 6×6 grid vertices<\/figcaption><\/figure>\n\n\n\n
        \"\"
        Figure 10. Approximation with 7×7 grid vertices<\/figcaption><\/figure>\n\n\n\n
        \"\"
        Figure 11. Approximation with 8×8 grid vertices<\/figcaption><\/figure>\n<\/div>\n\n\n\n

        As seem above, the increase in the approximation error for the 7×7 regular grid is caused by the alignment of the selected vertices with the planes that the asymptotes lie on. <\/p>\n\n\n\n

        This is an interesting observation, as we can visibly see that the alignment of the vertices to certain features or properties of a surface affects the surface approximation error. There have been works [1][2] that have touched on heuristics about how when the mesh edges are orthogonal to the direction of principal curvature of the original function it often (but not always!) results in a lower approximation error. The next two type of experiments look into this further.<\/p>\n\n\n\n

        Rotated surface function<\/strong><\/h2>\n\n\n\n

        We decided to test the alignment of the edges to the direction of principal curvature on the quadratic function, as we could easily identify this direction for this function. We rotated the surface by different angles and generated approximations using the same regular grid, then plotted its error.<\/p>\n\n\n\n

        \n
        \"\"
        Figure 12. Approximation of unrotated quadratic function<\/figcaption><\/figure>\n\n\n\n
        \"\"
        Figure 13. Approximation of quadratic function rotated 45 degrees around the z axis<\/figcaption><\/figure>\n<\/div>\n\n\n\n
        \n
        \"\"<\/figure>\n<\/div>\n\n\n\n

        Interestingly, the error is the lowest when the quadratic function is rotated 45 degrees and 225 degrees and highest. This is notable because when the function is rotated 0 or 90 degrees, the short edges of the triangles are in fact orthogonal to the direction of principal curvature, so according to the heuristic these cases should have given the lowest error. <\/p>\n\n\n\n

        After closer observation we realized that the 45 degrees and 225 degrees cases are when the longest<\/em> edge of the triangles are orthogonal with the curvature of the quadratic surface. Perhaps more work can be done to look into this in the future!<\/p>\n\n\n\n

        Re-meshed grid <\/strong><\/h2>\n\n\n\n

        We also use the Botsch-Kebbelt<\/a> re-meshing algorithm to re-mesh the regular grid, to generate more randomness in the alignment of the triangles to the principal curvature of the quadratic function. This algorithm takes in the surface as well as the desired average edge lengths of the the triangles in the mesh, and outputs to us a re-meshed surface. The images from left to right demonstrates what happens as we increase the average edge length that we pass in as a parameter. <\/p>\n\n\n\n

        \n
        \"\"
        Figure 15. Approximation of surface using a re-meshed grid with 0.15 desired edge length<\/figcaption><\/figure>\n\n\n\n
        \"\"
        Figure 16. Approximation of surface using a re-meshed grid with 0.07 desired edge length<\/figcaption><\/figure>\n<\/div>\n\n\n
        \n
        \"\"
        Figure 17. Error plot of input desired re-meshed edge length and chamfer distance error<\/figcaption><\/figure>\n<\/div>\n\n\n

        To make a more equal comparison, we converted the grid resolution to find the average edge length of the triangles in the regular grids and plotted its error together on a log-log graph. As we can see below, the regular grid does better than the Bosch-Kebbelt re-meshed grid. This is congruent with what we expected – that aligning the edges of the triangles would give us a lower error than just random orientations!<\/p>\n\n\n

        \n
        \"\"
        Figure 18. Comparison of the chamfer distance error for the regular grid and the botsch-kebbelt re-meshed grid<\/figcaption><\/figure>\n<\/div>\n\n\n

        References:<\/strong><\/h2>\n\n\n\n

        [1] Bommes, David, et al. \u201cMixed-integer quadrangulation.\u201d\u00a0ACM Transactions on Graphics, vol. 28, no. 3, July 2009, pp. 1\u201310, doi:10.1145\/1531326.1531383.<\/p>\n\n\n\n

        [2] Jakob, Wenzel, et al. \u201cInstant Field-aligned Meshes.\u201d\u00a0ACM Transactions on Graphics<\/em>, vol. 34, no. 6, Nov. 2015, pp. 1\u201315, doi:10.1145\/2816795.2818078.<\/p>\n\n\n\n

        <\/p>\n","protected":false},"excerpt":{"rendered":"

        Project Mentor:\u00a0Nicholas Sharp\u00a0 SGI Volunteer:\u00a0Qi Zhang This blog post is a follow up to “How to match the \u201cwiggliness\u201d of two shapes”, where we discussed the metrics we use to measure the similarity between two surfaces. In that post, we briefly talked about approximating a surface by using a regular grid to generate vertices for […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[37],"tags":[],"ppma_author":[32],"class_list":["post-170","post","type-post","status-publish","format-standard","hentry","category-research"],"authors":[{"term_id":32,"user_id":0,"is_guest":1,"slug":"cap-yixinlok","display_name":"yixinlok","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""}],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/170","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/comments?post=170"}],"version-history":[{"count":7,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/170\/revisions"}],"predecessor-version":[{"id":1989,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/170\/revisions\/1989"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/media?parent=170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/categories?post=170"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/tags?post=170"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/ppma_author?post=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}