{"id":2099,"date":"2024-10-08T09:05:42","date_gmt":"2024-10-08T09:05:42","guid":{"rendered":"https:\/\/summergeometry.org\/sgi2024\/?p=2099"},"modified":"2024-10-08T09:05:44","modified_gmt":"2024-10-08T09:05:44","slug":"reduced-deformation-collision-detection","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2024\/reduced-deformation-collision-detection\/","title":{"rendered":"Reduced deformation collision detection"},"content":{"rendered":"<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/collision_detection.gif\" alt=\"\" class=\"wp-image-3356\" style=\"width:791px;height:auto\" \/><\/figure>\n<\/div>\n\n\n<p class=\"has-text-color has-link-color wp-elements-7afd5eb10413db15fff28eec14cf833b wp-block-paragraph\" style=\"color:#6b3131\"><strong><em>Project mentor:<\/em> <\/strong><em>Prof. Paul Kry<\/em><\/p>\n\n\n\n<p class=\"has-text-color has-link-color wp-elements-1119850772ee25c539ba4e24cf585e56 wp-block-paragraph\" style=\"color:#6b3131\"><strong><em>Students: <\/em><\/strong><em>Eleanor Wiesler, Sara Samy, Juan Serratos<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Collision detection is an important problem in interactive computer graphics and physics-based simulation that seeks to determine <em>if<\/em>, <em>when<\/em> and <em>where<\/em> two or more objects come into contact. <a href=\"#ref-4\" data-type=\"internal\" data-id=\"#ref-4\">[4]<\/a> In this project, we implement bounded deformation trees (BD-Trees) and adapt this method to represent complex deformations of any geometry as linear superpositions of displacement fields.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"modal-analysis\"><strong>Mesh deformations<\/strong> <strong>using modal analysis<\/strong><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">When an object collides with a surface, we should expect the object to deform in some way, e.g. if a bouncing ball is thrown against a wall or dropped from a building, it should momentarily be &#8220;squished&#8221; or flattened at the site of collision. This is the effect we aim to accomplish using modal analysis.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We start with a manifold triangular mesh e.g. <strong>Spot<\/strong> the cow, and tetrahedralize it using the <a href=\"https:\/\/tetgen.pyvista.org\/\" data-type=\"link\" data-id=\"https:\/\/tetgen.pyvista.org\/\">python library<\/a> of TetGen, a Delaunay-based tetrahedral mesh generator. <a href=\"#ref-1\" data-type=\"internal\" data-id=\"#ref-1\">[1]<\/a> The resulting mesh is given as a \\((V, C)\\), where \\(C\\) is a set of tetrahedral cells whose vertices are in \\(V\\), as shown in <a href=\"#fig-1\">Figure 1<\/a> below.<\/p>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\" id=\"fig-1\">\n<figure class=\"wp-block-image size-large\" id=\"fig-1\"><img decoding=\"async\" data-id=\"3217\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/spot-tetgen-1.gif\" alt=\"Tetrahedral mesh of Spot.\" class=\"wp-image-3217\" \/><\/figure>\n<figcaption class=\"blocks-gallery-caption wp-element-caption\">Figure 1: Tetrahedral mesh of Spot.<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">We use the Physics Based Animation Toolkit (<a href=\"https:\/\/github.com\/Q-Minh\/PhysicsBasedAnimationToolkit\/\">PBAT<\/a>) to compute the free vibrational modes of our model. Physically, one can describe vibration as the oscillatory motion of a physical structure, induced by energy exchanges of the potential (elastic deformation) and the kinetic (moving mass) energies. Vibrations are typically classified as either <em>free<\/em> or <em>forced<\/em>. In free vibrations, there are no continuous external forces acting on the structure, e.g. when a guitar string is plucked, while forced vibrations result from ongoing external forces. By looking at these free vibrations, we can determine the natural frequencies and normal modes of the structure.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">First, we convert our geometric<em> <\/em>mesh into a <em>FEM<\/em> mesh and compute its Jacobian determinants and gradients of its shape function. You can check the <a href=\"https:\/\/github.com\/Q-Minh\/PhysicsBasedAnimationToolkit\/blob\/master\/doc\/tutorial\/FEM\/README.md\" data-type=\"link\" data-id=\"https:\/\/github.com\/Q-Minh\/PhysicsBasedAnimationToolkit\/blob\/master\/doc\/tutorial\/FEM\/README.md\">documentation<\/a> to learn more about FEM meshes.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; gutter: false; title: ; notranslate\" title=\"\">\nimport meshio\nimport numpy as np\nimport pbatoolkit as pbat\n\nimesh = meshio.read(&quot;.\/spot.mesh&quot;)\nV, C = imesh.points, imesh.cells_dict&#x5B;&quot;tetra&quot;]\n\nmesh = pbat.fem.Mesh(V.T, C.T, element=pbat.fem.Element.Tetrahedron, order=1)\n\nGNeU = pbat.fem.shape_function_gradients(mesh, quadrature_order=1)\ndetJeM = pbat.fem.jacobian_determinants(mesh, quadrature_order=2)\ndetJeU = pbat.fem.jacobian_determinants(mesh, quadrature_order=1)\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">Using these <em>FEM<\/em> quantities, we can model a hyperelastic material given its Young&#8217;s modulus \\(Y\\), Poisson&#8217;s ratio \\(\\nu\\) and mass density \\(\\rho\\).<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; gutter: false; title: ; notranslate\" title=\"\">\nrho = 1000.\nY = np.full(mesh.E.shape&#x5B;1], 1e6)\nnu = np.full(mesh.E.shape&#x5B;1], 0.45)\n\n# Compute mass matrix\nM = pbat.fem.MassMatrix(mesh, detJeM, rho=rho, dims=3, quadrature_order=2).to_matrix()\n\n# Define hyperelastic potential\nhep = pbat.fem.HyperElasticPotential(mesh, detJeU, GNeU, Y, nu, energy=pbat.fem.HyperElasticEnergy.StableNeoHookean, quadrature_order=1)\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">Now we compute the Hessian matrix of the hyperelastic potential, and solve the generalized eigenvalue problem \\(Av = \\lambda M v\\) using <a href=\"https:\/\/scipy.org\/\" data-type=\"link\" data-id=\"https:\/\/scipy.org\/\">SciPy<\/a>, where \\(A\\) denotes the Hessian matrix (a real symmetric matrix) and \\(M\\) denotes the mass matrix.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nimport scipy as sp\n\n# Reshape matrix of vertices into a one-dimensional array\nvs = mesh.X.reshape(mesh.X.shape&#x5B;0]*mesh.X.shape&#x5B;1], order=&quot;f&quot;)\n\nhep.precompute_hessian_sparsity()\nhep.compute_element_elasticity(vs)\n\nHU = hep.hessian()\nleigs, Veigs = sp.sparse.linalg.eigsh(HU, k=30, M=M, sigma=-1e-5, which=&quot;LM&quot;)\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">The resulting eigenvectors represent different deformation modes of the mesh. They can be animated as time continuous signals, as shown in <a href=\"#fig-2\" data-type=\"internal\" data-id=\"#fig-2\">Figure 2<\/a> below.<\/p>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-2 is-layout-flex wp-block-gallery-is-layout-flex\" id=\"fig-2\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1546\" height=\"1546\" data-id=\"3199\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/spot-mode-6.gif\" alt=\"Spot the cow oscillating with mode 6\" class=\"wp-image-3199\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1546\" height=\"1546\" data-id=\"3209\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/spot-mode-10.gif\" alt=\"Spot the cow oscillating with mode 10\" class=\"wp-image-3209\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1546\" height=\"1546\" data-id=\"3212\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/spot-mode-8.gif\" alt=\"Spot the cow oscillating with mode 8\" class=\"wp-image-3212\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1546\" height=\"1546\" data-id=\"3206\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/spot-mode-26.gif\" alt=\"Spot the cow oscillating with mode 26\" class=\"wp-image-3206\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1546\" height=\"1546\" data-id=\"3205\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/spot-mode-22.gif\" alt=\"Spot the cow oscillating with mode 22\" class=\"wp-image-3205\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1546\" height=\"1546\" data-id=\"3201\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/spot-mode-15.gif\" alt=\"Spot the cow oscillating with mode 15\" class=\"wp-image-3201\" \/><\/figure>\n<figcaption class=\"blocks-gallery-caption wp-element-caption\">Figure 2: Six different deformation modes of Spot. Notice how each mode is characterized by deformations in a different local site of the mesh like its legs or neck.<\/figcaption><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Reduced Deformation Models<\/strong><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">The BD-Tree paper <a href=\"#ref-2\" data-type=\"internal\" data-id=\"#ref-2\">[2]<\/a> introduced the bounded deformation tree, which can perform collision detection for reduced deformable models at similar costs to standard algorithms for rigid bodies. But what do we mean exactly by <em>reduced deformable models<\/em>? First, unlike rigid bodies, where collisions affect only the position or movement of the object, deformable bodies can dynamically change their shape when forces are applied. Naturally, collision detection is simpler for rigid bodies than for deformable ones. Second, instead of explicitly tracking every individual triangle in a mesh, <em>reduced<\/em> deformable models represent complex deformations efficiently by a smaller set of parameters. This is achieved by using a linear superposition of pre-computed displacement fields that capture the essential ways a model can deform.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Suppose we have a triangular mesh with \\(|V| = n\\). Let \\(\\boldsymbol{p} \\in \\mathbb{R}^{3n}\\) denote the undeformed vertices locations, and let \\(U \\in \\mathbb{R}^{3n \\times r}\\) be a matrix with \\(r \\ll n\\). Then the new deformed vertices location \\(\\boldsymbol{p&#8217;}\\) are approximated by a linear superposition of \\(r\\) displacement fields given by the columns of \\(U\\) such that<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\" id=\"linear-eq\">\\(\\displaystyle \\boldsymbol{p&#8217;} = \\boldsymbol{p} + U\\boldsymbol{q},\\)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">where the amplitude of each displacement field is determined by the reduced coordinates \\(\\boldsymbol{q} \\in \\mathbb{R}^{r}\\). Both \\(U\\) and \\(\\boldsymbol{q}\\) must already be known in advance. In our case, the columns of \\(U\\) are the eigenvectors obtained from <a href=\"#modal-analysis\" data-type=\"internal\" data-id=\"#modal-analysis\">modal analysis<\/a> described earlier, although they could also result from methods, e.g. an interpolation process. The reduced coordinates \\(\\boldsymbol{q}\\) could also be determined by some possibly <em>non-linear<\/em> black box process. This is important to note: although the shape model is <a href=\"#linear-eq\" data-type=\"internal\" data-id=\"#linear-eq\">linear<\/a>, the deformation process itself can be arbitrary!<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Bounded deformation trees<\/strong><\/h4>\n\n\n\n<h5 class=\"wp-block-heading\">Welzl&#8217;s algorithm<\/h5>\n\n\n\n<p class=\"wp-block-paragraph\">The BD-Tree works by constructing a hierarchy of minimum bounding spheres. As a first step, we need a method to construct the smallest enclosing sphere for some set of points. Fortunately, this problem has been well studied in the field of computational geometry, and we can use the randomized recursive algorithm of Welzl <a href=\"#ref-3\" data-type=\"internal\" data-id=\"#ref-3\">[3]<\/a> that runs in expected linear time.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The Welzl&#8217;s algorithm is based on a simple observation: assume a minimum bounding sphere \\(S\\) has been computed a set of points \\(P\\). If a new point \\(p\\) is added to \\(P\\), then \\(S\\) needs to be recomputed only if \\(p\\) lies outside of \\(S\\), and the new point \\(p\\) must lie on the boundary of the new minimum bounding sphere for the points \\(P \\cup \\{p\\}\\). So the algorithm keeps track of the set of input points and a set of support, which contains the points from the input set that must lie on the boundary of the minimum bounding sphere. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The pseudocode below <a href=\"http:\/\/ref-4\">[4]<\/a> outlines the algorithm:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\nSphere WelzlSphere(Point pt&#x5B;], unsigned int numPts, Point sos&#x5B;], unsigned int numSos)\n{ \n\t\/\/ if no input points, the recursion has bottomed out.\n    \/\/ Now compute an exact sphere based on points in set of support (zero through four points)\n\tif (numPts == 0) {\n\t\tswitch (numSos) {\n\t\t\tcase 0: return Sphere();\n\t\t\tcase 1: return Sphere(sos&#x5B;0]);\n\t\t\tcase 2: return Sphere(sos&#x5B;0], sos&#x5B;1]);\n\t\t\tcase 3: return Sphere(sos&#x5B;0], sos&#x5B;1], sos&#x5B;2]);\n\t\t\tcase 4: return Sphere(sos&#x5B;0], sos&#x5B;1], sos&#x5B;2], sos&#x5B;3]); \n\t\t}\n\t}\n\t\/\/ Pick a point at &quot;random&quot; (here just the last point of the input set)\n\tint index = numPts - 1;\n\t\/\/ Recursively compute the smallest bounding sphere of the remaining points\n\tSphere smallestSphere = WelzlSphere(pt, numPts - 1, sos, numSos); \n\t\/\/ If the selected point lies inside this sphere, it is indeed the smallest\n\tif(PointInsideSphere(pt&#x5B;index], smallestSphere))\n\t\treturn smallestSphere;\n\t\/\/ Otherwise, update set of support to additionally contain the new point\n\tsos&#x5B;numSos] = pt&#x5B;index];\n\t\/\/ Recursively compute the smallest sphere of remaining points with new s.o.s. \n\treturn WelzlSphere(pt, numPts - 1, sos, numSos + 1);\n}\n<\/pre><\/div>\n\n\n<h5 class=\"wp-block-heading\">The BD-Tree Method<\/h5>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\" id=\"fig-3\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"248\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1-1024x248.png\" alt=\"\" class=\"wp-image-3435\" srcset=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1-1024x248.png 1024w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1-300x73.png 300w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1-768x186.png 768w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1-1536x372.png 1536w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1-1200x291.png 1200w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1.png 1900w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption class=\"wp-element-caption\">Figure 3: Wrapped BD-Tree for Spot at increasing recursion levels.<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Now that we can compute the minimum bounding spheres for any set of points, we are ready to construct a hierarchical sphere tree on the undeformed model, after which it can be updated following deformation. First we note that the BD-Tree is a <em>wrapped hierarchy<\/em>, wherein the bounding spheres tightly enclose the underlying geometry but any bounding sphere at one level need not contain its child spheres. This is different from a <em>layered hierarchy<\/em> in which spheres must enclose their child spheres, but can fit the underlying geometry more loosely (see <a href=\"#fig-4\" data-type=\"internal\" data-id=\"#fig-4\">Figure 4<\/a>).<\/p>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default wp-block-gallery-3 is-layout-flex wp-block-gallery-is-layout-flex\" id=\"fig-4\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"486\" data-id=\"3313\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-1024x486.png\" alt=\"Illustration of wrapped vs. layered BD-Trees\" class=\"wp-image-3313\" srcset=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-1024x486.png 1024w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-300x142.png 300w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-768x365.png 768w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-1536x729.png 1536w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-2048x972.png 2048w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-1200x570.png 1200w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/layered_wrapped_bd_tree-1980x940.png 1980w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<figcaption class=\"blocks-gallery-caption wp-element-caption\">Figure 4: An illustration\u2014re-created from <a href=\"#ref-2\" data-type=\"internal\" data-id=\"#ref-2\">[2]<\/a> of the wrapped hierarchy (left) and layered hierarchy (right). The underlying geometry is shown in green with five vertices and four edges.<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">As shown in <a href=\"#fig-5\" data-type=\"internal\" data-id=\"#fig-5\">Figure 5<\/a>, there are many possible approaches to building a binary tree. In our case, we use a simple top-down approach while partitioning the underlying geometry, i.e. we recursively split <strong>Spot<\/strong> at its median into two parts with respect to its local coordination axes, such that a leaf node (the lowest level) contains only one triangle.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\" id=\"fig-5\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"797\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1024x797.png\" alt=\"\" class=\"wp-image-3418\" srcset=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1024x797.png 1024w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-300x233.png 300w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-768x598.png 768w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1536x1195.png 1536w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw-1200x934.png 1200w, https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/10\/Drawing_2024-10-06_06-33-07.excalidraw.png 1971w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption class=\"wp-element-caption\">Figure 5: Hierarchical binary tree construction with four objects using a top-down (top), bottom-up (middle) and insertion approach (bottom).<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">As the object deforms, how do we compute the new bounding spheres quickly and efficiently? <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let \\(S\\) denote a sphere in the hierarchical tree with center \\(c\\) and radius \\(R\\) containing the \\(k\\) points of the geometry \\(\\{p_{i}\\}_{1 \\leq i \\leq k}\\). After the deformation, the center of the sphere \\(c\\) is displaced by a weighted average of the contained points\u2019 displacements \\(u_{i}\\) with weights \\(\\beta_i\\) e.g. \\(\\beta_i := 1\/k\\) for \\(1 \\leq i \\leq k\\). So the new center can be expressed as<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\">\\(\\displaystyle c&#8217; = c + \\sum_{i = 1}^{k} \\beta_i u_i.\\)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Using the <a href=\"#linear-eq\" data-type=\"internal\" data-id=\"#linear-eq\">displacement equation<\/a> above, we can write \\(u_i\\) as the sum \\(\\sum_{j = 1}^{r}  U_{ij} q_{j}\\) and substitute this into the previous equation to obtain:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\">\\(\\displaystyle c&#8217; = c + \\sum_{j = 1}^{r} \\left(\\sum_{i = 1}^{k} \\beta_i U_{ij}\\right) q_j = c + \\bar{U} \\boldsymbol{q}.\\)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To compute the new radius \\(R&#8217;\\), we make use of the triangle inequality<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\">\\(\\displaystyle \\max_{i = 1, \\dots, k} || p&#8217;_{i} &#8211; c&#8217;_{i} ||_{2} \\leq \\max_{i = 1, \\dots, k} \\left(||p&#8217;_{i}||_{2} +  ||c&#8217;_{i}||_{2}  \\right).\\)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Expanding both \\(p&#8217;_{i}\\) and \\(c&#8217;_{i}\\) using their displacement equations and re-arranging the terms, we get that<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\">\\(\\displaystyle R&#8217; = R + \\sum_{j = 1}^{r} \\left( \\max_{i = 1, \\dots, k} ||U_{ij} &#8211; \\bar{U}_{j}||_{2} \\right) |q_j|.\\)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Thus, we have an updated bounding sphere \\(S&#8217;\\) with its center \\(c&#8217;\\) and radius \\(R&#8217;\\) computed as functions of the reduced coordinates \\(\\boldsymbol{q}\\).<\/p>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-4 is-layout-flex wp-block-gallery-is-layout-flex\" id=\"fig-6\">\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" data-id=\"3349\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/bv_tree_spot_mode_9.gif\" alt=\"\" class=\"wp-image-3349\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" data-id=\"3351\" src=\"https:\/\/summergeometry.org\/sgi2024\/wp-content\/uploads\/2024\/09\/bv_tree_spot_mode_7.gif\" alt=\"\" class=\"wp-image-3351\" \/><\/figure>\n<figcaption class=\"blocks-gallery-caption wp-element-caption\">Figure 6: Spot colliding with ground plane. The colors of the spheres change based on the ratio of \\(R\\) in the undeformed state to \\(R&#8217;\\) in the deformed state.<\/figcaption><\/figure>\n\n\n\n<h5 class=\"wp-block-heading\">References<\/h5>\n\n\n\n<p class=\"wp-block-paragraph\" id=\"ref-1\">[1] Hang Si. <em>TetGen, a Delaunay-based quality tetrahedral mesh generator.<\/em> ACM Transactions on Mathematical Software, 41(2), 2015.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\" id=\"ref-2\">[2] Doug L. James and Dinesh K. Pai. <em>BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models.<\/em> ACM Transactions on Graphics, 23(3), 2004.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\" id=\"ref-3\">[3] Emo Welzl. <em>Smallest enclosing disks (balls and ellipsoids). <\/em>New Results and New Trends in Computer Science, 555, 1991.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\" id=\"ref-4\">[4] Christer Ericson. <em>Real-Time Collision Detection.<\/em> CRC Press, Taylor &amp; Francis Group. Chapter 4, p. 99-100. 2005.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Project mentor: Prof. Paul Kry Students: Eleanor Wiesler, Sara Samy, Juan Serratos Collision detection is an important problem in interactive computer graphics and physics-based simulation that seeks to determine if, when and where two or more objects come into contact. [4] In this project, we implement bounded deformation trees (BD-Trees) and adapt this method to [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[40,37],"tags":[159,158,57,160,6],"ppma_author":[7,12],"class_list":["post-2099","post","type-post","status-publish","format-standard","hentry","category-math","category-research","tag-bd-tree","tag-collision-detection","tag-math","tag-modal-analysis","tag-sgi2024"],"authors":[{"term_id":7,"user_id":0,"is_guest":1,"slug":"cap-hussein","display_name":"hussein","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""},{"term_id":12,"user_id":0,"is_guest":1,"slug":"cap-ewiesler","display_name":"ewiesler","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\/2099","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=2099"}],"version-history":[{"count":10,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/2099\/revisions"}],"predecessor-version":[{"id":3511,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/2099\/revisions\/3511"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/media?parent=2099"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/categories?post=2099"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/tags?post=2099"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/ppma_author?post=2099"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}