Previous | Next --- Slide 38 of 49
Back to Lecture Thumbnails

How do we locate regions with dense geometries?


Do we generate these regions, automatically based on the density of the primitives? Or is the generation completely arbitrary (by human control)?


@bunbohue Quad-trees (and octrees) involve recursively subdividing space into quadrants. Usually, the recursive subdivision continues until one of the quadrants no longer contains any more primitives, at which point there's no use in subdividing further. The illustration shown here might have been generated by subdividing only when K or more primitives are within a particular quadrant.

@Ken Using our quad-tree, we can potentially locate regions with dense geometry by looking at the structure of the tree. Take the quad-tree associated with the illustration above. If the leaf of a tree is several levels deep, then this is an indication that there are multiple (e.g., K) primitives packed into a small region of space. Leaf nodes at shallower levels of the tree represent regions of space with fewer primitives.