bob wrote:
> Let's say you have a set of triangles, and you want to know which
> members of that set are visible from a given point. What is the most
> efficient way to calculate this?
It depends on what data you have available and/or what data you're
allowed to precompute and load with your set of triangles.
Sadly, if you have no other data available, you're up a creek; you've
pretty much got to transform the polygons into view space and see if the
triangles intersect the view. Simply checking to see if the vertices
are inside the frustum isn't enough since all vertices could lie outside
the frustum but you could still have edges going through the view****t.
The "most efficient" way is going to depend on your dataset, but
generally it'll be some sort of spatial partitioning.
The simplest to understand are quadtrees and octrees which split each
"box" of the world into four or eight smaller boxes (quadtrees are often
chosen when you don't care about height information or have unique
information when viewed from top-down, whereas octrees would be chosen
if you want to have a multi-floored building or something of that sort).
Alternatively (especially when your space doesn't divide naturally into
boxes), you could look at arbitrary binary space partitioning. This is
a scheme where you recursively split the world into two pieces using
"arbitrary" (although hopefully selected with some eye to why you're
choosing them!) planes.
Either of these space partitioning schemes, and any extensions and
variations to them, work by collecting some number of polygons into a
"space," with the hope/expectation that while it's costly to test a
space for whether or not is viewable, it's much less costly than testing
every single polygon inside it. So, you get to cull out a bunch of
polygons with a small number of tests.
Does the term "spatial partitioning" make sense now? I hope so. If
not, consider a "world" which is just a flat 10 x 10 grid of squares.
The top-level split that you'd get with a quadtree would be to split
into four 5x5 grids. In this way, you can then test the individual
spaces/boxes/whatever for visibility, and if a space isn't visible,
you've just determined with one fell swoop that all 25 of the squares
within the box are not visible.
Good luck,
-tom!
--
|
