steps toward full-campus walkthroughs in WK

[Seth Teller <teller@csail.mit.edu>]

[vitaly, michael:  since you'll be working more with
walkthru code in future, i'd like you to read through
and understand the following.  let's discuss as needed
over the next few weeks.  -- prof. t.]

[rick, laura, carlo:  i'm cc'ing you in hopes that you
will scan the following and point out any major flaws in
our thinking, and/or implementation hazards in the way
of our "encapsulating" a wk model as we plan to do.]

peter, there is a lot of material here, so this message
focuses only on the 5 technical steps you listed.  i'll
respond separately to the other sections.

comments below.

Luka wrote:
> [high-level idea:  get all-campus model to view inside WK]
>
> basic technical plans for making those start to happen:
>
> 1. i obtain sufficient data from mic (DONE - with some minor
>    changes requested but non-critical), and from vitaly (not
>    needed yet), to test with.

yes.  vitaly, i'd like to see your portion, namely the full
basemap with approximate height and coloring, integrated
this week, if possible.

> 2. i conjure up a walkthru DB for the campus model which is
>    composed of:
>    - a top level "outdoor" scene that instances two things.
>      at first just buildings and later also "outdoor details".
>    - individual building DB files that are just like what
>      walkthru already supports currently, except for the fact
>      that walkthru will be loading them within a larger
>      scene context now.

yes.  this may require a new command-line flag to wkadd,
to specify that a top-level scene description is being
supplied, which contains many encapsulated wk models.

a "major detail":  the subspaces will be axial in their own
coordinate system, but will in general be instanced into
world coordinates in a non-axial orientation.  this introduces
some complexity into partitioning, queries, etc., but if we
think it through it shouldn't be too bad.

> 3. i make walkthru deal with that 1 extra level of hierarchy,
>    updating all internal details needed to make the whole
>    system operate with the new world view.  (not as bad as
>    it sounds.  unless you think it sounds easy, in which
>    case you should think about that again.)

it sounds hard, but given how well the current system
is designed (thanks, rick!), it is definitely doable without
extreme pain.

> that was the hand-wavy logical description.  here's a 5 step
> implementation plan as i will actually be doing it:
>
> 1. "Exterior Queries"
>    modify portal traversal alg to handle queries originating
>    from a frustum that is outside the scene extents.  this
>    alone will not be exercised from the existing walkthru
>    prog yet, but is functionality required before stuff below
>    can be implemented.  i will put some simple temp hack in
>    walkthru to unit test it before going on.

yes.  i don't understand the "not be exercised" qualification
though.  since you're implementing this powerful new function,
why not simply enable the standard walkthrough application to
use it?  in other words, let the user fly anywhere s/he wishes,
and launch the correct query according to whether the eyepoint
is inside or outside the kd-tree root node's bounding box.

to satisfy an "exterior query," you'll need to write at least
the following functions:

  A) given a frustum F and a root cell R, recursively identify
     those child nodes of the cell that:
     (i) share a boundary face with R [otherwise, terminate]; and
     (ii) lie inside or partially inside F [otherwise, terminate]; and
     (iii) are leaf nodes [otherwise, recurse]; and
     (iv) contain F.eyepoint in their positive halfspace
          (where the halfspace is oriented to exclude the node bbox)

  B) given a frustum F and a leaf cell L, enumerate
     those portals into L that:
     (i) lie on a face of L that contains E in its positive halfspace; and
     (ii) lie inside or partially inside F;
     [NOTE:  there is code to loop over portals and check
      them against a frustum, inside several existing vis
      functions' inner loops.  rather than replicate it yet
      again, i recommend artfully invoking an existing
      function (perhaps with minor internal mods) so that
      it simply exercises existing code to check for portal
      incidence, and proceeds through the portal as usual.]

   C) finally, however A) and B) work, you'll need to
      launch a cell-portal traversal from F, identify
      visible objects as they are encountered(*), place them
      on wk's visible object list, and mark them so they
      won't be dual-counted.  this should happen exactly
      as it currently works in wk, with no new code if possible.
      (*): including exterior building faces!

> 2. "World/Bldg Encapsulation"
>    get the extra layer of hierarchy into walkthru so that it
>    can recognize a building as a subspace within a world model,
>    and [almost] do visibility traversal into and out of the
>    bldgs.  this step is basically DB layer mods, to support
>    the extra layer of hierarchy in its structs.  again, write
>    some hack to unit test it.

yes, again with the proviso that it should be tested on the
simplest possible case:  one world, with two separate axial
subspaces, each a simple wk model.  finally, a viewer free to
move through the world, launching vis queries as appropriate.

this brings up a question that we haven't yet answered:  given
a world model with N subspaces, each a (possibly rotated) axial
wk model, how should the eyepoint be point-located within the
world?  since N will probably be fairly small -- on the order
of a few hundred -- for the foreseeable future, and since we
have to launch an exterior query for each of N subspaces anyway,
we might as well just do a linear search.  but in future we
could think of smarter schemes (as when solving #5 below, when
N becomes 3, 4, 5 orders of magnitude larger).

> 3. "N+1 Isolated Queries"
>    first vis mods, enabling viewing of multi-bldg scenes.
>    for N bldgs in a scene, N+1 initial vis queries will be
>    made from any starting or continuing location in the
>    exterior world space: 1 for the exterior space (which
>    treats bldgs as sealed boxes), and 1 for each bldg.
>    the query going into a building treats it as its own
>    scene and works "automagically" by simply giving an
>    external query to start it (as enabled by <1> above).
>    in addition, traversal back out of the bldg scene should
>    be transformed and handed back to world space traversal
>    as well, being careful to avoid possible circularity
>    cases (but that might be better left to correct impl
>    within the framework to be provided by <5> below).

well, in the first iteration of <3>, there's no need to
handle "traversal back out the building scene," since by
definition an encapsulated vis query can identify visible
cells/objects only within the supplied root node, i.e., the
encapsulated space.

so, you need to solve 1 "world" query:  given a frustum,
and an *exterior* space and its contents (excluding the
building interiors), identify those elements of the
exterior space that are incident on the frustum, without
regard to occlusion caused by any subspaces.

you also need to solve N "subspace" queries of type <1>
above.  note that the *union* of the visible objects
identified by these N+1 *distinct* queries forms a valid
potentially visible set for the original query.  again,
careful to do marking to avoid double-counting!  this
becomes tricky if you parallelize (imagine two different
threads simultaneously discovering an object to be visible,
and both deciding to add it to wk's vis list for the frame).

so, summarizing:  no need to handle "emerging" queries, i.e.
a frustum leaving a building and entering the exterior
space, until #4 below.

> 4. "N 'Gated' Queries"
>    next step up in sophistication from the previous.  enhance
>    the "exterior traversal" alg to do bldg occlusion.  issue
>    queries going into bldgs which are restricted based on how
>    the frustum is already occluded by other bldgs.  (e.g. if
>    only one window of a bldg sticks around another, only enter
>    that window.  if half a window shows, constraints can be
>    synthesized to represent that to the traversal alg as well.
>    i know how to do this.)

actually, a cleaner way to think about this is in terms of
portals, rather than buildings.  think about a query that
originates inside an office, looking out through a window.
the query "emerges" into the exterior space having been
clipped to the window boundaries -- i.e., with a constraint
list containing the 4 frustum planes and 4 window edges.
as it traverses the exterior space, it "automatically"
excludes most invisible objects -- they don't lie inside
the intersection of the (many) planes on the constraint list.

now revisit the solution to <1> above.  instead of having
an exterior query that begins with "just" a frustum, you
want an exterior query that begins with an arbitrary list
of plane constraints, representing the frustum, and all
portals which the current query has traversed.  see <1>(B)
above -- a good solution to that issue basically solves
this one as well.

putting it all together, the last thing you need is a
top-level, front-to-back enumeration of the subspaces
(where FTB is defined with respect to the eyepoint).
note that this isn't trivial:  since in general the
sub-spaces are abutting and non-axial, a simple FTB
traversal of a kd-tree won't suffice -- basically, there
isn't a good partitioning kd-tree to traverse!  so we
have to do something smarter (i don't know the answer
to this yet).

> 5. "New Visibility Algs"
>    now i can implement everything i described in my AUP paper.
>    i won't try summarize any of it here.

yes.  once 1-4 exist, you'll be able to reuse many of the
crucial pieces in building <5>.

onward !  let's discuss this tuesday.  i think we agreed
that the group is going to convene at 430, and peter will
show up as soon after 5 as possib.e

prof. t.