“QSplat : A Multiresolution Point Rendering System for Large Data Meshes”MotivationSlide 3Rendering Large Data SetsWhat is QSplat ?General DescriptionRenderingRendering: Visibility CullingRendering: LOD ControlLOD ControlPreprocessingSlide 12Slide 13Design OverviewDesign DetailsSlide 16Slide 17Slide 18Slide 19Slide 20Design Details: SplattingSlide 22Slide 23Slide 24Slide 25Slide 26PerformanceSlide 28Slide 29Slide 30Slide 31ConclusionsFuture Work…Some final pictures…“QSplat : A Multiresolution Point Rendering System for Large Data Meshes”Authors:Szymon RusinklewiczMarc LevoyPresentation:Nathaniel FoutMotivation• A quick review…- Rendering time is a very strong function of scene complexity- Which class of rendering algorithms is this not true for ?- Does this pose a problem for rendering the Stanford Bunny in real time? What about 100 Bunnies? What about 1000 Bunnies? ( ~ 4.5 billion tri/sec)- Current graphics hardware:nVidia Quadro at 17 million tri/secMotivation• Who would want to render 1000 Bunnies in real time ?• Practical Applications :- rendering complex terrain (games, simulators)- rendering sampled models of physical objects•Advances in scanning technology have enabled the creation of very large meshes with hundreds of millions of polygons•Conventional rendering will not work. Why not?Obviously insufficient triangle throughput, but what about storage?1,000,000 triangles 36 MB100,000,000 triangles 3600 MBetc…Rendering Large Data Sets• Methodologies for dealing with this problem1) Visibility Culling – includes frustum culling, back- face culling, occlusion culling2) LOD Control – discrete or fine-grained control3) Geometric Compression – saves on storage costs, but must be decoded to render4) Point Rendering – use a simpler primitive, the point, instead of triangles•Many algorithms use some of these techniques; QSplat uses all of themWhat is QSplat ?QSplat is a point-based rendering system that uses the visibility culling, LOD control, and geometric compression to render very large triangular meshes. The core of the renderer is a hierarchical data structure consisting of bounding spheres.General Description• Basic Idea – instead of rendering all those polygons, let’s approximate the mesh with points along the surface• We can then splat these points on the image plane; z-buffer takes care of visibility as usual• Point samples are organized in a hierarchical fashion using bounding spheres – this facilitates easy visibility culling, LOD control, and rendering• Hierarchy construction is a preprocessing step – it is done once only and saved to a diskRendering• The rendering algorithm:TraverseHierarchy(node) { if (node not visible) skip this branch of the tree else if (node is a leaf node) draw a splat else if (benefit of recursing further is low) draw a splat else for each child in children(node) TraverseHierarchy(child)} Visibility Culling LOD ControlRendering: Visibility Culling• Frustum culling is performed by testing the bounding sphere against all six planes of the viewing frustum• Each node stores a normal conewhich is a collective representationof the normals of the subtree forthat node – this cone is usedfor back face culling• Occlusion culling is not usedNRendering: LOD Control• LOD control is accomplished by adjusting the depth of recursion when traversing the tree• There are two factors which control the depth of recursion:- projected screen space area of the bounding sphere- user selected frame rate• If the projected area of the sphere exceeds a threshold value then we descend to the next level•A feedback adjustment takes place to keep the frame rate at a user specified value; this adjustment is based simply on the ratio of actual to desired frame rate•Progressive refinement is initiated once the user stops moving – the area threshold is successively reduced until it is the size of a pixelLOD ControlThreshold: 15 pixelsPoints: 130,712Rendering Time: 132 msThreshold: 1 pixelPoints: 14,835,967Rendering Time: 8308 msMichelangelo’s statue of St. MatthewPreprocessing• Building the Hierarchy tree… What do the nodes look like?Leaf nodes correspond to verticesInterior nodes will have at most 4 childrenPreprocessing•Building the hierarchy tree…- we begin with a list of vertices- next we find a bounding box which contains the vertices- find the midpoint vertex along the longest axis of the bounding box- split the set of vertices into two parts- this creates the two children of the current node- the current node corresponds to the bounding sphere of the two child nodes- continue recursively…left childright childcurrent nodePreprocessing•Preprocessing Issues:- to ensure that there are no holes in the rendering we set the leaf node spheres to be a certain sizeIf two vertices are joined by an edge, then thespheres for those vertices are made largeenough to touch each other.Also, the size of a sphere at a vertex is set tothe size of the maximum sphere of thevertices which make up that triangle- to decrease the size of the tree, nodes are combined to increase the average branching factor to ~4- after the tree is created the properties of the nodes are calculatedDesign OverviewDesign Detailstree node layout:16214313position and radius•Position and radius of sphere encoded as offsets relative to parent and quantized to 13 values•Not all of 134 values are valid – in fact, only 7621 are valid•Incremental encoding of geometry essentially spreads out the bits of information among the levels of the hierarchy•Note that connectivity information is discarded•Encoding saves space but increases rendering time due to the necessity of decoding on-the-fly•Quantization saves space but pays for it by sacrificing accuracyDesign Detailstree node layout:16214313tree structure•Information as to the structure of the tree is necessary for traversal since the number of children may vary•Normally a pointer is kept for each child; however, if we store the tree in breadth-first order then we only need one pointer for each group of siblings•This one pointer (along with the tree structure bits) is enough for traversal•The first two bits represent the number of children: 0, 2, 3, or 4•The last bit indicates whether or not all children are leaf nodesDesign Detailstree node layout:16214313normal•Normals are quantized
View Full Document
Unlocking...