Solution for Three-Dimensional Field of View

Sorry about adding yet another field-of-view post. But I couldn't
resist. I think that I have some kind of addiction to it.

This message is especially for Kenneth 'Bessarion' Boyd who got me
thinking about this a long time ago, but anyone else should feel free
to comment.

I've realized how to do 3D Field of View. What I will describe is in
terms of permissive field of view which is my own obsession, but it
could easily be generalized to shadow-casting or virtually any other
well-defined field of view.

Field of view, whether shadow-casting or permissive, has as its most
fundamental idea, something I will call a view (also called active
scans in http://roguebasin.roguelikedevelopment.org/index.php?title=FOV_using_recursive_shadowcasting).
In two-dimensions it is a pair of lines which delimit what is
viewable.

Those lines are each made from the information contained in two
points. The first point, the point nearest the source is always the
center of the source square in shadowcasting. In permissive schemes,
it can vary a bit more. The far point is the corner of the most recent
blocked square encountered. These two points may be abstracted away by
caching a slope. But regardless, they are still there in concept.

When a square which blocks sight is found which intersects a view, the
view is cut into two smaller views which extend past the square. There
are special cases, but they all boil down to that idea. Now I will
extend the concept of view to three dimensions.

Lets translate to three-dimensions. Now the world is made up of cubes
which are aligned with the three axes. Each cube is either completely
transparent or completely opaque. Lets do everything in the positive x
y and z octant and use reflection to do everything elsewhere. Each
cube is labeled by the point closest to the origin.

In a 3-dimensional world, a view is made up of six planes. Two are
parallel to the x axis, two to the y axis, and two to the z-axis.
These represent upper and lower bounds. Each one of these planes is
defined by two lines. And we can uniquely define that plane because
those two lines will be parallel with each other. There will be a near
line and a far line just like there were near points and far points
before in two dimensions. Again, for shadowcasting, the near line is
always going to be a line parallel to whatever axis its on and going
through the middle of the cube.

Now we need a way to determine if a point on a cube is within those
bounds. Actually, to be more specific we need to determine whether a
line on that cube is within these bounds. We can turn to our old
friend the slope. No, really.

Each plane is parallel to an axis. So that means that it has a slope
relative to that axis. We will be comparing with a line on the cube
that is also parallel to that axis. And the property of parallel-ity
is transitive. So that line on the cube will also be parallel to both
the near and the far lines (separately, not all at once). That gives
us the beautiful property above of being able to define a plane based
on those lines.

So if we take the slope of the plane defined by the near line and the
far line, and compare it to the slope of the plane defined by the near
line and the cube line, we know whether that line is below or above or
on that plane.

Ok. Now for the explosion of cases. Each pair of constraints parallel
to the same axis must be compared to a cube. If the cube is within all
of the constraints and blocks sight, then we have to generate a lot
more views. One axis will have to be split around the cube's bounds,
keeping the other bounds constant. And then another axis will have to
be split, but it gets more complicated. It will have to be outside of
the cube on this axis but inside of the cube on the first axis and
leave the third axis unchanged. The last axis will get split too but
will have to be inside the cube's bounds on the previous two axes.
This is really hard to visualize, but it is because you need to split
up in a way so that there is no overlap.

And there are even more cases if the cube intersects one or more
bounds, but not all of them. This part will have to be simplified
somehow. Perhaps just always splitting like above, and then detecting
views which can contain no points.

Finally, there is the notion of bumps. You can ignore it if you are
just doing shadowcasting. But if you are doing permissive fov, then
you have to keep track of them. All you do differently is that the
bumps are now lines parallel to a particular axis, and so you have six
reverse-trees of them that you need to keep track of. And you just
detect them and account for it in the same way, but using the lines
rather than points.

And that is all there is to it. The initial view is set up analagously
to the two-dimensional part. Now you have field of view in three
dimensions. I would tend to prefer permissive (as usual) because then
when you stand on a castle's rampart, you will be able to see the
enemies directly below. With shadow-casting, you couldn't.

Finally, the truly groundbreaking idea. What if the two-slit
experiment merely exposes a bug in God's FoV algorithm?!?! :-)
.

Relevant Pages

  • Re: Solution for Three-Dimensional Field of View
    ... cube is labeled by the point closest to the origin. ... parallel to the x axis, two to the y axis, and two to the z-axis. ... Two planes each orthogonal to said axes. ... And we can uniquely define that plane because ...
    (rec.games.roguelike.development)
  • Re: Spinning cube question
    ... path with one axis, as they would with two or three. ... are not relevant here), not the cube center. ... cube there's no method by which to attach a face-centered ... axis without more rods. ...
    (sci.physics)
  • Re: EXPERIMENTS THAT REFUTE RELATIVITY
    ... Cartesian N-dimensional coordinate system: ... - point on second axis ... If you play with a Rubic Cube in a space capsule, ... rotate, recognize that the experiment is rotating to ...
    (sci.physics.relativity)
  • Re: Solution for Three-Dimensional Field of View
    ... to the same axis must be compared to a cube. ... of the constraints and blocks sight, then we have to generate a lot ... One axis will have to be split around the cube's bounds, ... with a floor/roof we have an opaque square in three dimensions. ...
    (rec.games.roguelike.development)
  • Portfolio Analyzer displays incorrect actual work
    ... The project managers are accepting the updates and pushing them into Project Pro correctly. ... I have a Portfolio Analyzer view that displays projects as one axis and and resources as the other axis. ... In this view a user who has 10 actual hours on the project will show up in the cube as 40 hours. ...
    (microsoft.public.project.pro_and_server)
Loading