Levels of DetailProblemSlide 3Slide 4LOD HierarchyPolygonal SimplificationVertex ClusteringSlide 8Slide 9Vertex RemovalEdge CollapseFoldoversVirtual Edge CollapseSlide 14Low-Pass FilteringMorphological OperatorsTopological Simplification Using Alpha-HullsSlide 18Discrete LODContinuous LODSlide 21View-Dependent LODSlide 23Slide 24Slide 25CHPMSlide 27Simplification ErrorHausdorff DistanceVertex Plane DistanceQuadric Error MetricAttributesSlide 33Slide 34Normal conesGAPSImage Driven SimplificationSimplification EnvelopesOther Forms of LODResourcesLevels of DetailLevels of DetailCOMP 770COMP 7703/25/093/25/09ProblemProblemModels can be very detailedModels can be very detailedLook great when close upLook great when close upLast week we explored one way of Last week we explored one way of attacking this problemattacking this problem13M Triangles8M Elevation Points1M TrianglesProblemProblemEven after visibility culling we can have too many Even after visibility culling we can have too many visible trianglesvisible trianglesWon’t this problem go away with faster GPUs?Won’t this problem go away with faster GPUs?–The real world has virtually infinite complexityThe real world has virtually infinite complexity–Our ability to model and capture this complexity Our ability to model and capture this complexity outpaces rendering performanceoutpaces rendering performance270M Elevation Points82M Triangles100M Triangles372M TrianglesQ: Why else might we want to reduce the working set size?Levels of DetailLevels of DetailBasic Idea: Render using fewer triangles Basic Idea: Render using fewer triangles when model is farther from viewerwhen model is farther from viewerMethods:Methods:–Multi-resolution modelingMulti-resolution modelingRemeshingRemeshingParametric SurfacesParametric SurfacesSubdivision SurfacesSubdivision Surfaces–Polygonal SimplificationPolygonal Simplification–Image ImpostorsImage ImpostorsLOD HierarchyLOD Hierarchy[Clark76] First LOD paper[Clark76] First LOD paper–Replace each object in the scene graph with a Replace each object in the scene graph with a hierarchy of objects at differing resolutionshierarchy of objects at differing resolutions–Select LOD based on size of screen-space Select LOD based on size of screen-space projectionprojectionIntegrates VFC with LOD searchIntegrates VFC with LOD searchSupports out-of-core renderingSupports out-of-core renderingMost LOD systems today are based on Most LOD systems today are based on this basic conceptthis basic conceptPolygonal SimplificationPolygonal SimplificationMethod for reducing the polygon count of meshMethod for reducing the polygon count of meshLocal Operators:Local Operators:–Vertex ClusteringVertex Clustering–Vertex RemovalVertex Removal–Edge CollapseEdge Collapse–Triangle CollapseTriangle CollapseGlobal Operators:Global Operators:–Low-Pass FilteringLow-Pass Filtering–Morphological OperatorsMorphological Operators–Alpha-HullAlpha-HullVertex ClusteringVertex Clustering[Rossignac & Borrel 93][Rossignac & Borrel 93]Weight vertices by:Weight vertices by:–Inverse of max angle between edges (why?)Inverse of max angle between edges (why?)–Size of largest adjacent face (why?)Size of largest adjacent face (why?)Impose a grid on the modelImpose a grid on the modelCompute weighted average vertex in each cellCompute weighted average vertex in each cellTriangles become:Triangles become:–TrianglesTriangles–LinesLines–PointsPointsKeep the unique primitivesKeep the unique primitivesVertex ClusteringVertex ClusteringHow do we create a set How do we create a set of LODs?of LODs?What are the limitations What are the limitations on this method?on this method?Main Benefits:Main Benefits:–Hard to target a polygon countHard to target a polygon count–Poor error controlPoor error control–Not invariant to rotation or Not invariant to rotation or translationtranslation–Mixed primitive typesMixed primitive types–SimpleSimple–RobustRobustVertex ClusteringVertex Clustering[Low & Tan 97][Low & Tan 97]Improve on R&B in a several ways Improve on R&B in a several ways including:including:–Floating-cell clusteringFloating-cell clustering–Improved angle weight [draw it]Improved angle weight [draw it]–Rendering using thick linesRendering using thick linesVertex RemovalVertex Removal[Schroeder et al. 92][Schroeder et al. 92]Designed for Marching Cubes OutputDesigned for Marching Cubes OutputRemove a triangle and re-triangulate Remove a triangle and re-triangulate holeholeIgnores non-manifold verticesIgnores non-manifold verticesProperties:Properties:–Preserves topologyPreserves topology–Uses original verticesUses original vertices–LinearLinearEdge CollapseEdge CollapseIntroduced by [Hoppe93]Introduced by [Hoppe93]Variation: Half-Edge CollapseVariation: Half-Edge Collapseabcedge collapsevertex splitFoldoversFoldoversCollapsing an edge can flip a faceCollapsing an edge can flip a faceabcedge collapsevertex splitVirtual Edge CollapseVirtual Edge CollapseExtension of edge collapse to two vertices Extension of edge collapse to two vertices not connected by an edgenot connected by an edgeAllows topological simplificationAllows topological simplificationAlso known as vertex-pair collapseAlso known as vertex-pair collapseUsually limited to small distance to avoid Usually limited to small distance to avoid O(nO(n22) virtual edges) virtual edgesEdge CollapseEdge CollapseAllows geomorphsAllows geomorphsFine-grained: 2 triangles removed for Fine-grained: 2 triangles removed for manifold casemanifold caseTopology preservingTopology preservingHalf-edge collapse preserves vertex setHalf-edge collapse preserves vertex setLow-Pass FilteringLow-Pass Filtering[He et al. 96][He et al. 96]Convert polygon mesh to volumetric Convert polygon mesh to volumetric representationrepresentationApply low-pass filter to volumetric dataApply low-pass filter to volumetric dataReconstruct the mesh using marching Reconstruct the mesh using marching cubescubesMorphological OperatorsMorphological Operators[Nooruddin99][Nooruddin99]Convert polygon mesh to volumetric Convert polygon mesh to volumetric representationrepresentationApply dilation operator followed by erosion Apply dilation operator followed by erosion operator operator Reconstruct with marching cubesReconstruct with marching cubesApply polygonal simplifcationApply polygonal simplifcationTopological Simplification Using Topological Simplification Using