Deep Accurate Solver for the Geodesic Problem

Saar Huberman; Amit Bracha; Ron Kimmel

Figure 1. Geodesic distances from a single point on each surface are presented as colors (white to red) and level sets painted on the surface. The proposed method produces substantially more accurate than state of the art distance maps while operating in quasi-linear time. The evaluation was done on shapes from the TOSCA dataset ( Bronstein et al., 2008 ) , whereas our solver was trained with a small number of

2^{nd}

order polynomial surfaces. Figure 1. Geodesic distance computed by our method is shown on shapes from the Tosca dataset as distance maps and iso-contours. Our method computes highly accurate distances.

Figure 2. The proposed local solver pipeline described in Section 4.1 . For each point in the Wavefront , the Visited points from from its local neighbourhood are chosen, and their coordinates and distance function are transformed into their canonical representation with respect to the target point. The processed input is fed into the neural network and the output is further processed to revert the centering and scaling transformations. Figure 2. illustration of the pipeline of our local solver. Fully described in the text.

Figure 3. The proposed network architecture described in Section 4.1 . The input coordinates and distance function are in their canonical form, after translation rotation and scale. Figure 3. Illustration of the architecture of our local solver. Fully described in the text.

Figure 4. Bootstrapping by training. Distance values computed for a high

h^{2}

-resolution sampled mesh of a continuous surface with an

r

accurate scheme yields

\mathcal{O}(h^{2r})

accurate distances given at the mesh points. The mesh can then be sampled into a lower

h

-resolution mesh of the same continuous surface, while keeping the corresponding

\mathcal{O}(h^{2r})

accurate distances at the vertices. See text for an elaborated discussion regarding data augmentation at high resolution and training more accurate update procedures at the low resolution. Figure 4. Present the proposed bootstrapping method used to create our training examples. Fully described in the text.

Figure 5. Order of accuracy: Right: Plots showing how the edge size effects the error. The accuracy of each scheme is defined by the corresponding slope. We used mesh approximations of a unit sphere with different edge size. Left: Errors presented on high resolution spheres for 2nd order methods and our presented method (when brighter colour indicates higher error). Figure 5. Numerical evaluation of the order of accuracy presented on spheres. The order of accuracy for the fast marching method is 0.68, for the MMP method 1.95, for the method presented by Lichtenstein et al. 2.1, and for our method 3.02. For high-resolution meshes with an average edge of less than 0.1, our method shows errors that are more than an order of magnitude smaller compared to all other methods

Figure 6. Polynomial surfaces: Errors presented for the polyhedral scheme and the proposed method. Local errors, represented as colors on the surface, were computed relative to exact polyhedral distances computed at a high-resolution sampled mesh of the continuous surface, as described in Subsection 4.3 . Figure 6. Visualized errors on hyperbolic parabolic surfaces comparing MMP methods and our method. Our method has significantly lower errors compared to MMP.

Surface	$L_{1}$ $(\times 10^{-2})$				$L_{\infty}$ $(\times 10^{-2})$
	FMM	LPK	MMP	Ours	FMM	LPK	MMP	Ours
$x^{2}-y^{2}$	2.86	0.21	0.09	0.04	7.95	1.17	0.24	0.16
$x^{2}+y^{2}$	2.05	0.34	0.28	0.09	6.80	1.44	0.67	0.26
$x^{2}-y^{2}+xy$	2.91	0.33	0.18	0.09	6.40	2.60	0.63	0.28

Table 1. Polynomial surfaces: Quantitative evaluation conducted on

2^{nd}

order paraboloids. The errors were computed relative to the polyhedral distance projected from high-resolution sampled meshes, as described in Subsection 4.3 .

Figure 7. Order of accuracy on parametric surfaces: Plots showing the effect of the edge size on the errors. The accuracy of each scheme is associated with its corresponding slope. Ground truth distances were evaluated using our bootstrapping method 4.3 . Left: Evaluation on hyperbolic paraboloid

x^{2}-y^{2}

. Right: Evaluation on regular paraboloid

x^{2}+y^{2}

. Figure 7. Numerical evaluation of the order of accuracy for a regular paraboloid and a hyperbolic paraboloid. For a regular paraboloid, the order of accuracy is 1.93 and 3.02 for the MMP method and our method, respectively. For a hyperbolic paraboloid, the accuracy is 1.74 for the MMP method and 3.01 for our method.

Shape	$L_{1}$ $(\times 10^{-1})$					$L_{\infty}$ $(\times 10^{-1})$
	Heat	FMM	LPK	Ours	Ours - Point clouds	Heat	FMM	LPK	Ours	Ours - Point clouds
Dog	0.728	0.110	0.123	0.037	0.072	8.688	1.514	1.318	0.465	2.968
Cat	1.260	0.101	0.278	0.043	0.045	5.379	0.735	3.949	0.474	0.863
Wolf	0.440	0.162	0.169	0.072	0.092	2.244	1.009	1.343	0.422	0.598
Horse	0.796	0.129	0.256	0.043	0.089	3.331	1.687	2.761	0.602	3.502
Michael	3.142	0.089	1.170	0.067	0.081	8.525	0.506	3.800	0.418	0.563

Table 2. Generalization to arbitrary surfaces: Quantitative evaluation tested on TOSCA. The errors are relative to the MMP scheme. Our solver and the one proposed in ( Lichtenstein et al., 2019 ) were trained using our bootstrapping method 4.3 with a limited number of

2^{nd}

order polynomial surfaces, the three paraboloids presented in Table 5 . In addition to shapes represented as triangulated meshes, we present results for applying the proposed method to point clouds, see Section 5.3 .

Figure 8. Generalization to arbitrary surfaces. Errors presented for the heat kernel method, fast marching, Lichtenstein et al. and the proposed method. Local errors presented as colors on the surface (brighter color indicates higher error), were computed relative to the polyhedral MMP distances. The evaluation was done on the TOSCA data base, whereas our solver and the solver proposed by Lichtenstein et al. were trained with a small number of

2^{nd}

order polynomial surfaces, the three paraboloid surfaces presented in Table 5 Figure 8. Present errors of the Heat method, FMM, Lichtenstein et al. and our method. Fully described in the text

Figure 9. Generalization to arbitrary shapes: Iso-contours shown for (left to right) the heat method, fast marching, Lichtenstein et al., our method and the exact polyhedral scehme, calculated by the MMP algorithm. The evaluation was conducted on shapes from TOSCA whereas our solver and the solver proposed by Lichtenstein et al. were trained with only limited number of

2^{nd}

order polynomial surfaces (the

3

surfaces presented in Table 5 ). Figure 9. Present iso-contours on shapes from the Tosca dataset for the Heat method, FMM, Lichtenstein et al., our method and the exact polyhedral distances. Our method shows more accurate iso-contours on sharp edges, even though it was trained on smooth surfaces. Fully described in the text.

Figure 10. Point clouds: Distance maps computed by the proposed method. The evaluation was done on shapes from the TOSCA dataset, given as point clouds. Our solver was trained using the suggested bootstrapping framework 4.3 with a limited number of

2^{nd}

order polynomial surfaces, represented by polygonal meshes. Figure 10. Point clouds. Geodesic distance computed by our method is plotted on shapes from the Tosca dataset represented as point clouds. Fully described in the text.

Figure 11. Order of accuracy for point clouds: Plots showing the effect of the edge size of the corresponding mesh or distances between nearby points in the point cloud case, on the errors. When applied to point clouds, the local neighborhood is given by KNN 3,6 as defined in Subsection 5.3 . Figure 11. Numerical evaluation of the order of accuracy shown on spheres. The variation of our method for point clouds shows a similar order of accuracy and errors as the variation of our method for triangulated meshes.

Figure 12. Point clouds and nearest neighbors: Local inaccuracies presented as colors on the surface (brighter color indicates higher error), were computed relative to distances computed on the polyhedral mesh representation of the surfaces. In the point cloud representation, the local neighborhood is defined using the KNN framework, which is based on the Euclidean distance between points in the extrinsic embedding space

\mathbb{R}^{3}

. This is in contrast to the intrinsic neighborhood defined by edge connectivity in the mesh representation. In the green regions, points from far away parts of the surface are wrongly identified as neighbors by the solver. It leads to loss of accuracy in distance approximation in such regions. Figure 12. Point clouds and nearest neighbors. Illustration of errors that occur when defining the local neighborhood using the extrinsic embedding space

\mathbb{R}^3

. Fully described in the text.

Figure 13. Left: Local neighborhood: Evaluation of the proposed method on spheres with different local neighborhoods support. Ring i corresponds to a neighborhood containing all vertices with at most i edges from the evaluated target. Right: Precision floating point representation: Evaluation of our method on spheres with different floating point precision representation of the neural network weights. Figure 13. Left: Local neighbourhood: numerical evaluation of the order of accuracy of our method for different local neighbourhoods. The order of accuracy for Ring1, Ring2, Ring3, and Ring4 are 0.98, 2.63, 3.02, and 2.97, respectively. Right: Precision floating point representation: numerical evaluation of the order of accuracy of our method with different floating point representations of the neural network weight. The order of accuracy for float16, float32, and float64 are 2.83, 3.00, and 3.02, respectively.

Error	FMM	Heat method	LPK	MMP	Ours
$L_{1}$	0.01804	0.01964	0.00510	0.00128	0.00099
$L_{2}$	0.01865	0.02048	0.00672	0.00142	0.00127
$L_{\infty}$	0.0270	0.0361	0.02278	0.0027	0.0041

Table 3. Robustness to triangulation: Quantitative evaluation of the ability of the proposed method to handle triangulations other than those for which it was trained for. The evaluation was conducted on randomly uniformly non-regularly sampled spheres whereas our solver and the solver proposed by Lichtenstein et al. were trained only on regularly sampled spheres.

Figure 14. Robustness to Triangulation: Errors presented for the “exact” MMP scheme and the proposed method. Local errors, represented as colors on the surface, were computed relative to the analytical geodesic distances. The proposed method was trained on regularly sampled spheres as can be seen in Figure 16 . Figure 14. Robustness to Triangulation. Visualization of errors on spheres containing ill condition triangulation. The methods presented are the MMP method and our method when trained on regularly sampled spheres. Fully described in the text.

Neural architecture	Residual connections	Activation	negative slope	Pooling
Model 1	✓	LeakyReLu	0.2	max
Model 2	✓	LeakyReLu	0.2	avg
Model 3	✓	LeakyReLu	0.001(default)	max
Model 4	✓	ReLu	✗	max
Model 5	✗	ReLu	✗	max
LPK	✗	ReLu	✗	max

Table 4. Neural Architectures: Various architectural modifications to the presented neural network 3 . The residual connections and the different activation functions are defined only for the shared weight MLP, while the fully connected network applied after the pooling operation has LeakyRelu activation with a negative slope of 0.001 in all variants of our neural network.

Figure 15. Neural architectures: Evaluation of the effects of different modifications to our neural network, presented in 6.3 . All different models use the same local neighborhood support, which includes all vertices with at most three edges from the evaluated target. Figure 15. Neural architectures: numerical evaluation of the order of accuracy on spheres for different architectures presented in Table \ref{table: Neural Architectures}. The order of accuracy for Model1, Model2, Model3, Model4, and Model5 are 3.02, 2.59, 2.73, 2.38, and 2.22, respectively.

Figure 16. Attention map showing the importance of each neighboring point in the network approximation. The source point is colored pink, the point whose distance is currently evaluated is colored red, and all other plotted points form the current local neighborhood. The Visited neighboring points that are fed into the neural network are colored according to the percentage of the corresponding features in the latent vector obtained from the max-pooling operation. It can be seen that the neural network pays more attention to the neighboring points that are closer to the geodesic path. Figure 16. Attention map showing the importance of each neighboring point in the network approximation. Fully described in the text.

Deep Accurate Solver for the Geodesic Problem

Abstract

Figures & tables

Neural PDE Solvers

A Neural Network Framework for Geodesic-Like Curve Computation on Parametric Surfaces

Parallelised Differentiable Straightest Geodesics for 3D Meshes

Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling

Abstract

Neural PDE Solvers

Explore similar work

A Neural Network Framework for Geodesic-Like Curve Computation on Parametric Surfaces

Parallelised Differentiable Straightest Geodesics for 3D Meshes

Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling