CSE168Computer Graphics II, RenderingSpring 2006Matthias ZwickerPractical details• Assignment 1 due today• Problems with base code?• Assignment 2 available on the web site• Due May 1, 5pmLast time• Aggregate objects• Acceleration structures• Bounding volume hierarchies• Axis aligned bounding boxesAggregate objects• Object that holds groups of objects• Stores bounding box and pointers to children• Useful for instancing and BVHRay tracing cost• Naïve approach: linear complexity per ray• 6320 triangles * 1024 * 768 raysAcceleration structures• Goal: “sub-linear” complexity per ray• Don’t touch every single objectAcceleration structuresTwo fundamental approaches• Hierarchies of groups of objects“object subdivision”• Space partitioning“spatial subdivision”Bounding volume hierarchies• Hierarchies of groups of objectsBounding volume hierarchies• Hierarchies of groups of objectsBounding volume hierarchies• Hierarchies of groups of objectsBounding volume hierarchies• Tree structure• Internal nodes are aggregate objects• Leave nodes are geometric objects• Intersection testing involves tree traversalaggregate objectBVH constructionBVH construction• RootBVH construction• Split horizontallyBVH construction•RecursionBVH construction• Split verticallyBVH construction• Split verticallyEtc….Axis aligned bounding boxesToday• Binary space partitioning (BSP) trees• Construction• Optimization• TraversalSpace partitioning• Uniform gridSpace partitioning• Uniform gridSpace partitioning• Uniform gridSpace partitioning• Uniform grid?BSP trees• Binary space partitioning trees• Recursively divide space into two parts•Kdtrees– Dividing planes are axis alignedBSP treesExample• Subdivide until fewer than 3 objects in node• Left child below split plane• Right child above split planeBSP trees1234567890BSP treesAA1234567890BSP treesBABA1234567890BSP treesBABA1234567893,40BSP treesCBACA123456789BA3,40BSP treesCBACA1234567895,6BA3,40BSP treesCBACA1234567895,6BA3,490BSP treesDCBA123456789ABA3,4DC5,690BSP trees123456789EDCBAABA3,4DEC95,60BSP trees123456789EDCBAABA3,4DE3,6C95,60BSP trees123456789EDCBAABA3,4DE1,2 3,6C95,60BSP trees123456789EDCBAABA3,4D7,8E1,2 3,6C95,60BSP tree data structureBSP_tree : object {intersect( ray, &hit )build_tree( object *o[], bbox b ) BSP_node *root}BSP_node {float plane_posint axisBSP_node *above, *belowbool is_leafobject *obj_array}BSP tree constructionBSP_node BSP_tree::build_tree( object *o[], bbox b ) {if( termination criterion met ) {make leafreturn leaf}find split planemake nodeb_above = bbox above of planeb_below = bbox below of planeo_above = objects above of planeo_below = objects below of planenode.above = build_tree( o_above, b_above )node.below = build_tree( o_below, b_below )return node}BSP tree optimization• Where to place the split plane?• Locally minimize cost functionCost for no splitNumber of primitivesCost to intersect primitive iBSP tree optimizationCost for split• Depends on split plane positionCost to traverse interior nodeProbability to hit child below, above splitNumber of primitives below, above splitBSP tree optimization• Probability to hit childSurface area of child, rootBSP tree optimizationMinimizing the cost function• Evaluate at small number of fix locations• Advanced: evaluate at edges of object bounding boxes• For all 3 split directionsBounding boxesSplit directionBSP tree optimizationTweaking implementation• Determine parameters experimentally• Expect • Favor splits where one child is empty• Allow a number of bad splitsBSP tree optimizationTweaking your implementation• Optimize memory layout•BSP nodes– Reduce size to 8 bytes• Tree organization – Store left child always immediately after parent nodeBSP tree traversal• “Front-to-back” traversal• Traverse child nodes in order along rays• Stop traversing as soon as surface intersection is found• Maintain a stack of subtrees to traverse– More efficient than recursive function callsBSP tree traversal123456789EDCBAAProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBADBProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBABEProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBAB1,23,6ProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBAB3,6ProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBABProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBAC3,4ProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBACProcessStackABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBAProcessStack5,6ABA3,4D7,8E1,23,6C95,6BSP tree traversal123456789EDCBAProcessStack5,6ABA3,4D7,8E1,23,6C95,6BSP tree traversalBSP_stack_item {BSP_node *nodefloat tmin, tmax}tmintmaxnode.axisnode.plane_posBSP tree traversalnode = rootisect = FLT_MAXtmin, tmax = intersect root bounding boxwhile( node!=0 ) {if( isect < tmin ) breakif( node is not leaf ) {<process interior node>} else {isect = check for intersection inside leafnode, tmin, tmax = get item from stack}}BSP tree traversal<process interior node> =compute ray-split plane intersection<order of children><process children>• Which child node is (potentially) hit first?• Which child nodes are hit?BSP tree traversalWhich child is (potentially) hit first?axisplane_posbelowaboveee<order children> =if( e[axis] <plane_pos ) {first = belowsecond = above} else {first = abovesecond = below}BSP tree traversaltmintmaxtsplitWhich child nodes are hit?tsplit<process children>=if( tsplit>tmax ||tsplit<0 ) {node = first}BSP tree traversaltmintmaxtsplit<process children>+=else if( tsplit<tmin ) {node = second}Which child nodes are hit?BSP tree traversalOtherwise process first child, stack second childtmintmaxtsplit<process children>+=else {node = firstitem.node = seconditem.tmin = tsplititem.tmax = tmaxstack.add( item )}BSP tree traversalWhich intersection is found first?BSP tree traversalwhile( node!=0 ) {if( isect < tmin ) break...Which intersection is found first?BSP tree traversalMailboxing• Avoid intersecting the same object multiple times• Use unique ID tag for each ray• Tag each object when intersecting with rayOrganizational• Get assignment 2 from course web site!• Implement BSP tree