Hierarchical Segmentation of Automotive Surfaces and Fast Marching MethodsAutomated Trajectory GenerationChallengesRelated ResearchOverview of Our ApproachOur Approach: DecompositionRules for Trajectory generationChoice of Start CurveEffect of Surface CurvatureSelecting position of Start CurveSpeed and Index OptimizationOffset Pass Generation (Implementation)Level Set Method [Sethian]Fast Marching Method [Sethian]FMM: Similarity with DijkstraFMM Contd.FMM on triangulated manifoldsHierarchical Surface SegmentationGeometrical SegmentationSlide 20Topological SegmentationPass Based SegmentationRegion MergingRegion Merging ResultsSummaryFuture Work—Cell StitchingThank You! Questions?1Hierarchical Segmentation of Automotive Surfaces and Fast Marching MethodsDavid C. ConnerAaron GreenfieldHowie ChosetAlfred A. RizziBioRoboticsLabMicrodynamic SystemsLaboratoryPrasad N. Atkar2Automated Trajectory Generation•Generate trajectories on curved surfaces for material removal/deposition–Maximize uniformity–Minimize cycle time and material wasteSpray PaintingBone ShavingCNC MillingComplete CoverageUniform CoverageCycle time and Paint wasteProgramming Time3Challenges•Complex deposition patterns•Non-Euclidean surfaces•High dimensioned search-space for optimization0 Micr35.08Deposition PatternSpray GunTarget SurfaceWarping of the Deposition Pattern4Related Research•Index Optimization–Simplified surface with simplified deposition patterns (Suh et.al, Sheng et.al, Sahir and Balkan, Asakawa and Takeuchi)•Speed Optimization –Global optimization (Antonio and Ramabhadran, Kim and Sarma)5Overview of Our Approach•Divide the problem into smaller sub-problems–Understand the relationships between the parameters and output characteristics–Develop rules to reduce problem dimensionality–Solve each sub-problem independentlyConstraintsPath Variables SimulationOutput Characteristics Rule Based PlanningSystem ParametersModel Based PlanningOutputDimensionality Reduction6Our Approach: Decomposition •Segment surface into cells–Topologically simple/monotonic –Low surface curvature yx(t)•Generate passes in each cellSelect start curveOptimize end effector speedOptimize index width and generate offset curveRepeat offsetting and speed optimization7Rules for Trajectory generationSelect passes with minimal geodesic curvature (uniformity)Avoid painting holes (cycle time, paint waste)Minimize number of turns (cycle time, paint waste)8Choice of Start Curve•Select a geodesic curve–Select spatial orientation (minimizing number of turns)–Select relative position with respect to boundary (minimizing geodesic curvature)Average Normal9Effect of Surface Curvature•Offsets of geodesics are not geodesics in general!!•Geodesic curvature of passes depends on surface curvature –Gauss-Bonnet TheoremgeodesicNot ageodesic10Selecting position of Start Curve•Select start curve as a geodesic Gaussian curvature divider11Speed and Index Optimization•Speed optimization–Minimize variation in paint profiles along the direction of passes•Index optimization–Minimize variation in paint deposition along direction orthogonal to the passes12Offset Pass Generation (Implementation)•Marker points•Self-intersections difficulty•Topological changesInitial frontFront at a later instance Marker pt. soln.Images from http://www.imm.dtu.dk/~mbs/downloads/levelset040401.pdf13Level Set Method [Sethian]•Assume each front at is a zero level set of an evolving function of z=Φ(x,t)•Solve the PDE (H-J eqn)given the initial front Φ(x,t=0)http://www.imm.dtu.dk/~mbs/downloads/levelset040401.pdf14Fast Marching Method [Sethian]•Φ(x,t)=0 is single valued in t if F preserves sign•T(x) is the time when front crosses x•H-J Equation reduces to simpler Eikonal equationgiven•Using efficient sorting and causality, compute T(x) at all x quickly.T=0ГT=315FMM: Similarity with Dijkstra•Similar to Dijkstra’s algorithm–Wavefront expansion–O(N logN) for N grid points•Improves accuracy by first order approximation to distance16FMM Contd.In our example,For 2-D gridDijkstra FMMFirst order approximation11∞∞17FMM on triangulated manifolds•Evaluate finite difference on a triangulated domain–Basis: two linearly independent vectorsT(A)=10CT(B)= 855Dijkstra: T(C)=min(T(A)+5, T(B)+5)=13FMM: T(C)=8+4=124ABFront grad.218Hierarchical Surface Segmentation•Segment surface into cells •Advantages–Improves paint uniformity, cycle time and paint waste•Requirements–Low Geodesic curvature of passes–Topological monotonicity of the passes19Geometrical Segmentation•To improve uniformity of paint deposition–Minimize Geodesic curvature of passes–Restrict the regions of high Gaussian curvature to boundaries20Geometrical Segmentation•Watershed Segmentation on RMS curvature of the surface–Maxima of RMS sqrt((k12+k22)/2) ≈ Maxima of Gaussian curvature k1k2•Four Steps–Minima detection–Minima expansion–Descent to minima–Merging based on Watershed Heighthttp://cmm.ensmp.fr/~beucher/wtshed.html21Topological Segmentation•Improves paint waste and cycle time by avoiding holes•Orientation of slices–Planar Surfaces (cycle time minimizing)–Extruded Surfaces (based on principal curvatures)–Surfaces with non-zero curvature (maximally orthogonal section plane)SymmetrizedGauss MapMedial Axis22Pass Based Segmentation•Improves cycle time and paint waste associated with overspray•Segment out narrow regions–Generate slices at discrete intervals23Region Merging•Merge Criterion–Minimize sum of lengths of boundaries : reduce boundary ill-effects on uniformity •Merge as many cells as possible such that each resultant cell is–Geometrically simple•Inspect boundaries–Topologically monotonic (single connected component of the offset curve, and spray gun enters and leaves a given cell exactly once)•Partition directed connectivity graph such that each subgraph is a trail24Region Merging ResultsSegmentedMergedSegmented MergedSegmentedMerged25Summary•Rules to reduce dimensionality of the optimal coverage problem•Gauss-Bonnet theorem to select the start curve•Fast marching methods to offset passes•Hierarchical Segmentation of Surfaces26Future Work—Cell Stitching•Optimize ordering in which cells are painted•Optimize overspray to minimize the cross-boundary deposition•Optimize end effector velocity27Thank