Cell Decomposition required: cells are rectangles each face is either wholly transparent or wholly opaque cells are axis aligned there are no junctions of this form:

Process:

• at each vertex, add new transparent edges which continue until they meet an existing edge

• use the following patterns

Example:

Now consider the geometry of visible regions. They are made of triangles which have the focal point (fp) at one vertex.

The other vertices of these triangles are either (a) vertices of walls or (b) points on other walls where rays through vertices strike a wall.

If we can find these triangles efficiently, then we are basically done. Notice that it isn't good enough simply to cast rays through every vertex -- in a big maze, that would be hopelessly inefficient.

How do we construct triangles efficiently?
Use the cell deconposition.

Algorithm

• mark cell in which fp lies as processed
• for each wall vertex that lies on a vertex of this cell, split the world using this vertex; mark the vertex
• add every 4-neighbor of this cell that lies on the opposite side of a translucent edge to the "to-do" list; mark it? as in to-do

• cell = first(to-do list)
• split using unused visible vertices of cell
• add the neighbors of cell that are on the opposite side of the visible transparent edge to the to-do list
• mark cell as processed

e.g.

Example:

		to-do = a,b notice the 2 rays cast, splitting cells
	to-do = b,c a third ray was cast
	to-do = c,d a fourth ray was cast
	to-do = d,e a fifth ray was cast
	to-do = e,f,g,h sixth and last ray was cast

Notice that the role of the cell structure is to find us vertices through which to cast rays.

Enumerating visibility triangles

fp,1,2 fp,2,3 fp,3,4 fp,8,5 fp,5,6 fp,6,7

Main Question: How can you tell to stop at 8 in triangle f,8,5 ?

Rule: rays can look like this:

Clearly, travelling counter-clockwise, going out: (1) go to a (2) stop at vertex b (3) go to a (4) stop at vertex b

Splitting Cells

• Clearly, ray a affects visibility in cell 2, but not in 1. This means we check boundary b1, but not b2.
• This means that we must record the ray in 2, so we know what to check; in particular, we must record so we know which side is visible.
• The distinction between 1 and 2 is made by noticing that in 1, the ray has not yet encountered its first vertex; in 2, it has.

• A cell like c (above) may have several splitting rays; they affect the visibility of its boundaries and its edges. As a result, there is no ray through v1 in this picture, because v1 is not visible.
• Clearly, rays need to record which side is visible. The easiest way to do this is by a sign convention; store the ray as:
  (a, b, c) where ax + by + c = 0 is the equation. The convention we will use is:
  if ax + by + c >= 0 , then x,y is visible with respect to the ray. We'll denote this with an arrow, pointing toward the visible side.

Hence changes come from intersections; the actual sense of visiblility must come from the following figure:

Notice that the constraints that rays stop at walls and that they do not affect visibility until their first vertex means that we will never see:

or similar nonsense.

Hence, in a ray you need to record:

• (a, b, c) (for the visibility calculations)
• vert
• end (for constructing the triangles)

• boundaries
• edge vertices present
• flags for opaque/transparent boundary
• used or not
• rays affecting visibility
• neighbors on far side of transparent edges

The Process of Intersecting Rays

• slow & dumb: intersect with everything, sort interesections along rays.
• better: use quadrants, etc.

We can ignore:

• Vertical edges for which
  • y_max < mx + c
  • y_min > mx + c .
• Horizontal edges for which
  • x_max < (1/m)(y-c)
  • x_min > (1/m)(y-c).