Automatic Simplification of Particle System DynamicsOutlineIntroduction: MotivationPrevious WorkParticle SystemsSimulation Level of Detail (SLOD)Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12SLOD ParametersHow to Cluster?Physically-based Hybrid SubdivisionSlide 16SLOD System ArchitectureEfficient SLOD UpdatingSmooth SLOD SwitchingSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Regions of Interest (ROI)Slide 27Slide 28Results: Regions of InterestResults: Changing ROIsMaintaining Constant Frame RateSlide 32Error AnalysisResults: Frame RatesSlide 35Future WorkPrairie GrassLODsTransition: Near to MediumTransition: Medium to FarWind PrimitivesPostureVariation in Posture IndexSamplesSpeedView-dependent Culling of Dynamic Systems in VEsInfluence of Initial ConditionsParametersStart StateRun StateChaotic Behavior in Run StateStop StateDecay StateStationary StateRe-entering ViewBuilding the DistributionSimulation CostBumper Car ParametersSimulationInfluence of Initial StateAutomatic Simplification ofParticle System DynamicsDavid O’Brien Susan Fisher Ming C. Linhttp://gamma.cs.unc.edu/SLODUNC Chapel HillMing C. LinOutlineIntroduction and MotivationSimulation Level of Detail (SLOD)–Definitions and Parameters–Creation and Maintenance through Physically-based Spatial SubdivisionAdding Flexibility–Regions of Interest (ROI)–Switching ROIsResultsFuture WorkUNC Chapel HillMing C. LinIntroduction: MotivationReal-time VEs & Video Games–Increasingly use particle systems and physically based simulations–Despite recent advances, still can not simulate complex dynamical systems in real time.Goal:–Reduce Cost of Dynamics Computations through Simulation Acceleration Techniques–Analogous to Model Simplification & Rendering –Maintain Consistent Frame Rates for SimulationsUNC Chapel HillMing C. LinPrevious WorkModel Simplification & Simulation Levels of Detail–Fumkhouser et al created a generic framework for LOD and rendering techniques to maintain real-time frame rates–Carlson & Hodgins created Simulation Level of Details for groups of legged creatures.–Chenney et al proposed view-dependent culling of dynamic systemsUNC Chapel HillMing C. LinParticle SystemsWhy Particle Systems?–Natural Phenomena, Modeling, and Group BehaviorField System: Force can be applied to a particle in constant time–Gravity, Drag, Turbulence–Linear with respect to number of particlesN-Body Simulation: –Astronomical Simulation, Potential Calculations–n2 interactions, reduced to O(n lg n) with heuristics such as Barnes-Hut AlgorithmUNC Chapel HillMing C. LinSimplifying a Particle System:Simulation Level of Detail (SLOD)UNC Chapel HillMing C. LinGroup into Clusters:Simulation Level of Detail (SLOD)UNC Chapel HillMing C. LinCalculated Weighted Center of Mass Position:Simulation Level of Detail (SLOD)UNC Chapel HillMing C. LinCalculated Weighted Center of Mass Velocity:Simulation Level of Detail (SLOD)UNC Chapel HillMing C. LinApply Dynamics Engine to the just the Center of Masses:Simulation Level of Detail (SLOD)UNC Chapel HillMing C. LinUpdate particles to match movement of Center of Masses:Simulation Level of Detail (SLOD)UNC Chapel HillMing C. LinGiven a Particle Cluster C consisting of n particles:1. Computer Position Pcom and Velocity Vcom2. Update CoM using standard particle dynamics.3. Apply change in Pcom and Vcom to all particles.Simulation Level of Detail (SLOD)11ni iicomniimVVm11ni iicomniim PPmwhere, mi, Pi and Vi are mass, position and velocity of ith particleUNC Chapel HillMing C. LinMain Parameters (used to create clusters):–Cluster Size: maximum number of particles per cluster–Cluster Breadth: maximum spatial size of a clusterSecondary Parameters (when clusters can be combined):–Velocity Ratio:–Relative Angle:SLOD ParametersUNC Chapel HillMing C. LinHow to Cluster?Uniform Grids:Fast placement+lookupUneven particle sizesQuad-Trees:Adaptive, good clusteringO(n lg n) cost too highUNC Chapel HillMing C. LinPhysically-based Hybrid SubdivisionBase is a uniform grid–Give good insertion and query speedWhen needed, subdivide as a Kd-tree.Maximum Cluster BreadthUNC Chapel HillMing C. LinPhysically-based Hybrid SubdivisionWhy Physically-based?–We can subdivide on a physical parameter as well–Usually this is done only at the top of the SD hierarchyheavylightUNC Chapel HillMing C. LinSLOD System ArchitectureSet Parameters andMinimum Frame RateCreate Initial Subdivision Tree. Initialize SLODs.Advance Simulation Step.Update SLODs.Update Subdivision Tree.Render ParticlesUNC Chapel HillMing C. LinEfficient SLOD UpdatingCan not rebuild the Subdivision Tree on each Simulation Step.After each simulation step:–Remove and Reinsert each cluster that has moved out of its cell.–When inserting, merge nearby clusters when possible.–Prune the tree of unnecessary empty cells–Insert new particles into nearby clusters.•If clusters become too large, split them.Always taking into account changes in SLOD parametersUNC Chapel HillMing C. LinSmooth SLOD SwitchingOnly update clusters when they move out of their cell.–Max Cluster Size switches from 4 to 2UNC Chapel HillMing C. LinSmooth SLOD SwitchingOnly update clusters when they move out of their cell.–Max Cluster Size switches from 4 to 2UNC Chapel HillMing C. LinSmooth SLOD SwitchingOnly update clusters when they move out of their cell.–Max Cluster Size switches from 4 to 2UNC Chapel HillMing C. LinSmooth SLOD SwitchingOnly update clusters when they move out of their cell.–Max Cluster Size switches from 4 to 2UNC Chapel HillMing C. LinSmooth SLOD SwitchingOnly update clusters when they move out of their cell.–Max Cluster Size switches from 4 to 2UNC Chapel HillMing C. LinSmooth SLOD SwitchingOnly update clusters when they move out of their cell.–Max Cluster Size switches from 4 to 2UNC Chapel HillMing C. LinSmooth SLOD SwitchingOnly update clusters when they move out of their cell.–Only changed the SLOD parametersUNC Chapel HillMing C. LinRegions of Interest (ROI)System is still not flexible enough–Real particle systems are dynamic–Different Areas need Different SLOD levelsSolution:–Divide Simulation Space into many ROIs.–ROIs can independently:•have separate SLOD settings•size and reshape•move around the simulation space•be added or deleted dynamicallyUNC Chapel HillMing C. LinRegions of Interest