文章仅供个人学习使用，如果对内容感兴趣的，可以直接参考最后的链接查看原文学习。

Visibility Determination is the process of deciding whether there is a clear & unimpeded line of sight from one game entity or point in space to another.

可见性判断是确定从一个游戏实体或空间点到另一游戏实体是否存在清晰且不受阻碍的视线的过程。

• Hit detection---确定一个实体是否应该受到类似射线的游戏效果的影响，例如射线拾取，光束武器或快速/短程子弹（忽略使子弹偏离直线较长距离的射弹物理特性）。
• Stealth gameplay mechanics---确定角色或安全设备是否可以看到可疑或敌对的事物。 在这种情况下，可见性可以考虑照明，部分遮挡或伪装，以表示某物是否“引人注目”，而不仅仅是视线可达。
• Light propagation and fog of war（战争迷雾）---确定从特定角色的角度来说，游戏世界的哪些区域以及其中的哪些实体是可见的，或者从特定光源接收光。 在2D游戏中，这通常是通过计算可见性多边形（visibility polygons）来实现的。
• Occlusion Culling---确定哪些对象在渲染的场景中不可见，因此可以从最密集的处理中将其省略。

补充：2d Visibility (in grid)

在2D top-down的地图中，有时候从给定点计算哪些区域可见是有用的。例如，您可能想隐藏从玩家位置不可见的内容，或者您想知道手电筒将照亮哪些区域。

链接中的作者实现了一个程序，可以拖动玩家位置来查看玩家的可见度：

https://www.redblobgames.com/articles/visibility/

该算法还可以计算给定光源下哪些区域被照亮。 每个灯光运行一次，都可以构建一个光照图，以显示哪些区域被照亮，感兴趣的可以去看下。 

正文：

为了以合理和正确的方式查看场景，必须省略从特定角度不可见的所有部分。 特别地，这些是不透明物体或被其他物体遮挡的部分的背面。 这称为hidden-line或hidden-surface-removal。根据场景的复杂性，对象的类型和数据结构，可用的硬件以及应用程序的要求，可以使用不同的可见性确定算法。使用对象空间object-space方法时，将对象的位置相互比较，并且仅绘制前（可见）部分。 使用图像空间image-space方法时，对于图像的每个部分，可见度都是单独确定的。 以下说明未考虑透明对象。

一、Backface Detection (Backface Culling)

Backface Culling不是完整的可见性判断方法。有了它，所有法线都指向远离观察者，因此不可见的多边形将被消除，以减少后续步骤的成本。平均而言，此过程会删除50％的多边形。为了计算使用正交投影时要删除的多边形，需要计算视图矢量与表面法线的标量积（Vview * N> 0→不可见）；对于透视投影，视点（x，y，z）为 代入平面方程式（Ax + By + Cz + D <0→不可见）

二、Z-Buffering (Depth Buffering)

z-buffering算法通过以下方式解决了特定图像分辨率的可见性问题：对于图像的每个点，除了颜色信息之外，有关显示对象位置的信息还存储在自己的存储器中。由于视角方向通常是（负）z方向，因此x和y值对应于像平面坐标，这样我们仅需要存储z值。

因此，除了图像缓冲区（帧缓冲区）之外，还需要一个额外的缓冲区，该缓冲区可以存储每个像素的z值。

此缓冲区称为z-buffer或depth-buffer。使用z缓冲区，可以按任意顺序绘制所有对象。计算要绘制的对象的z值（在大多数情况下为多边形），并将其与要在其上绘制对象的像素的z值进行比较。如果新的z值离viewer更近（因此通常更大），则将在此处绘制新的对象颜色，替换旧的图像值，并且z缓冲区中的z值也会更新。否则，该对象将被遮挡，并且无需采取任何措施：

for all (x,y) (* initializing the background *)
     depthBuff(x,y) = - ∞
     frameBuff(x,y) = backgroundColor
for each polygon P (* loop over all polygons *)
     for each position (x,y) on polygon P
         calculate depth z
         if z > depthBuff(x,y) then
             depthBuff(x,y) = z
             frameBuff(x,y) = surfColor(x,y)
 (* else nothing! *) 

可以为平面多边形有效地增量计算z值。 z-buffer的最大优点是不必对对象（多边形）进行排序。

三、Scan-Line Method

使用扫描线方法，将为每个水平线计算正确的可见性（在示例中，从上到下，因此y减小）。这样，可以利用的是，两条连续的像素线（扫描线）通常具有相似的可见性属性。

示例中，一共有三个多边形，分别为ABC(对应颜色)，我们对扫描线和与其相交的边记下来，形成我们图中的表。

从包含按最大y值排序的多边形所有边的表和关联的多边形表开始，为每条扫描线创建一个活动边列表。

从最后一条扫描线的边缘开始逐步进行此操作：

消除已结束的边缘，并检查已排序边缘表的下一条边缘（如果已开始）。用这种方法计算出一条扫描线与所有边缘的所有交点后，将按其x值（从左到右）对它们进行排序。 在每对相交点之间，必须确定哪个多边形最接近viewer； 这是可见的，将沿着此扫描线绘制。

四、Depth-Sorting Method

深度排序算法的原理是从后到前对所有多边形进行排序，然后按此顺序绘制它们。由于所有隐藏（被遮挡的）部分都比遮挡的部分远，因此生成的图像具有正确的可见性（painter’s algorithm）。

主要花费是排序，必须以一种方式进行，即没有多边形（部分）遮挡列表中后来出现（因此更靠近viewer）的任何其他多边形。

这分两个步骤完成：首先快速进行近似排序，然后检查排序是否正确。 如果不是，将使用该列表。

具体：

1.近似排序--Approximate sorting：根据最小的z值（最远的多边形）对多边形进行排序。

2.将每个多边形S与每个（！）其他多边形S’进行比较：

（*假设S位于S'*后面）

（*现在进行一系列测试，并且测试的复杂度不断提高，直到可以接受排序为正确*为止）

a.S的最大z值小于S’的最小z值→排序正确。

b.x或y间隔不交叉→排序正确

c.S的所有顶点都在S’的平面后面→排序正确

d.S’的所有顶点都在S平面的前面→排序正确

e.S和S’在xy平面上的投影不相交（请参见下面的图片）→排序正确

f.排序可能是错误的情况（请参见S隐藏在S后面的图片）→交换并再次检查排序。 如果排序再次错误，则发生了一种特殊情况（参见图片），必须通过分割一个多边形来解决：

五、Area-Subdivision Method

与图像的四叉树表示类似，通过将区域细分为四个四分之一，可以以低分辨率解决简单问题，并简化更复杂的问题。 如果递归地应用到图像分辨率，可以实现可见度问题的像素精确解决方案。

为此，需要一种方法来快速发现多边形投影在（二次）图像窗口上的位置。 有四种可能性：（1）多边形覆盖整个窗口，（2）多边形部分位于窗口的内部和部分外部，（3）多边形完全位于窗口的内部，或者（4）多边形完全位于窗口的外部 。

有三个简单的visibility decisions：

• 1. 所有多边形都在窗口外 → done
• 2.只有一个多边形与窗口相交→ draw this polygon
• 3.一个多边形覆盖整个窗口，并位于窗口区域中所有其他多边形的前面→ draw this polygon

如果所有三个测试均失败，则将窗口分为四个quarters，然后将其递归处理。

请注意，已经完全位于窗口外部的多边形也位于其子窗口之外。 同样，如果多边形已覆盖整个窗口，则其所有子窗口也将被该多边形覆盖。 如果子窗口仅达到一个像素的大小，则选择最近的多边形。 从示例中可以看出，这发生在可见性发生变化的所有边缘。

六、Octree

如果将场景表示为八叉树而不是多边形，那么对于每个视图方向，数据结构都已经知道哪一侧在前面，哪一侧在后面。

可以按以下方式递归地呈现数据结构：首先，在一个多维数据集中，呈现离viewer最远的子多维数据集，然后呈现下一个近三个子多维数据集，然后是下三个，最后是最近的子多维数据集。 在下面的示例中可以看到一种可能的排序方式：

或者，可以从前到后进行渲染。 然后，必须已经存储了绘制了某些东西的所有区域，以便仅绘制那些将保持可见的区域。 这种数据结构相对于其他数据结构的优势在于，它隐式知道哪些部分在前面，哪些部分在后面。

七、Ray-Casting

Ray-Casting是一种可见性判断的方法，可以为每个像素显式计算在那里可见的东西。为此，从每个像素向场景中射出一条直线，即一条直线。向后思考（Thinking backwards），通过该射线，光从场景传输到图像平面或分别传输到viewer。

如果此射线与场景的所有对象或多边形相交，则将获得一组交点，并选择最接近viewer的交点。在此相交点处的表面颜色决定了射线所穿过的像素的颜色。 如果对所有像素都执行此操作，则每个像素的结果就是最近的对象的颜色，即可见的对象。

通过射线投射，不仅可以以简单的方式渲染多边形，而且还可以计算与直线相交的其他类型的表面（例如，自由曲面）。如后面所述，通常在交点处需要表面法线，以便能够计算出有用的阴影。 相反，射线投射非常昂贵，因为必须为每个对象（每个像素可能要成千上万个）计算一个交点（每个像素全屏需要几百万个）。 这就是为什么必须有效执行交集测试和进一步优化的原因。

Ray-casting 是ray-tracing的简单变体，可以使用它模拟许多其他光学效果。 这将在后面的章节中进行解释。

Ray-Casting =
for each pixel of the image-plane:
 generate a line through the pixel in viewing-direction (“viewing-ray”)
 intersect the ray with all objects
 choose the nearest intersection point to the viewer
 color the pixel with the color of the surface at this intersect. point 

八 总结

让我们最后对上面提到的算法做一个分类：

Object-space methods：backface culling, depth sorting, octree

Image-space methods: z-buffering, scanline method, area subdivision method, ray-casting 

[1] Visibility Determination---Tag Info https://gamedev.stackexchange.com/tags/visibility-determination/info

[2]visibility polygons  https://www.redblobgames.com/articles/visibility/

[3]Visibility-Determination https://www.cg.tuwien.ac.at/courses/CG1/textblaetter/englisch/05%20Visibility%20Determination%20(engl).pdf

一、背景

在Android开发中有时候会遇到需要检查一个View是不是对用户可见，比如在消息流中，根据ImageView是否在屏幕中出现了再决定加载它，或者当视频滑入屏幕被用户可见时才播放、滑出屏幕就自动停止播放等等。乍一看好像都是在ListView、RecyclerView、ScrollView这些组件里面比较需要做这件事，今天总结一下我在实际开发中是怎么处理View可见性检查的。

二、检查View是否可见的基本方法（从外部检查View）

1 View.getVisibility()

很显然，我们可以用View.getVisibility()来检查一个它是否处于View.VISIBLE状态。这是最基本的检查，如果连这个方法得到的返回值都是View.INVISIBLE或者View.GONE的话，那么它对用户肯定是不可见的。

2. View.isShown()

这个方法相当于对View的所有祖先调用getVisibility方法。看下它的实现：

    /**
     * Returns the visibility of this view and all of its ancestors
     *
     * @return True if this view and all of its ancestors are {@link #VISIBLE}
     */
    public boolean isShown() {
        View current = this;
        //noinspection ConstantConditions
        do {
            if ((current.mViewFlags & VISIBILITY_MASK) != VISIBLE) {
                return false;
            }
            ViewParent parent = current.mParent;
            if (parent == null) {
                return false; // We are not attached to the view root
            }
            if (!(parent instanceof View)) {
                return true;
            }
            current = (View) parent;
        } while (current != null);

        return false;
    }

看代码注释便知，这个方法递归地去检查这个View以及它的parentView的Visibility属性是不是等于View.VISIBLE，这样就对这个View的所有parentView做了一个检查。

另外这个方法还在递归的检查过程中，检查了parentView == null，也就是说所有的parentView都不能为null。否则就说明这个View根本没有被addView过（比如使用Java代码创建界面UI时，可能会先new一个View，然后根据条件动态地把它add带一个ViewGroup中），那肯定是不可能对用户可见的，这里很好理解。

3 View.getGlobalVisibleRect

先看下什么是Rect：

Rect holds four integer coordinates for a rectangle. The rectangle is represented by the coordinates of its 4 edges (left, top, right bottom). Rect代表一个矩形，这个矩形可以由它左上角坐标(left, top)、右下角坐标(right, bottom)表示。所以每一个Rect对象里面都有left, top, right bottom这4个属性。

使用这个方法的代码非常简单，如下所示，直接可以得到rect对象和方法的返回值visibility：

Rect rect = new Rect();
boolean visibility = bottom.getGlobalVisibleRect(rect);

看一下该方法的注释：当这个View只要有一部分仍然在屏幕中（没有被父View遮挡，所谓的not clipped by any of its parents），那么将把没有被遮挡的那部分区域保存在rect对象中返回，且方法的返回值是true，即visibility=true。此时的rect是以手机屏幕作为坐标系（所谓的global coordinates），即原点是屏幕左上角；如果它全部被父View遮挡住了或者本身就是不可见的，返回的visibility就为false。

/**
     * If some part of this view is not clipped by any of its parents, then
     * return that area in r in global (root) coordinates. To convert r to local
     * coordinates (without taking possible View rotations into account), offset
     * it by -globalOffset (e.g. r.offset(-globalOffset.x, -globalOffset.y)).
     * If the view is completely clipped or translated out, return false.
     *
     * @param r If true is returned, r holds the global coordinates of the
     *        visible portion of this view.
     * @param globalOffset If true is returned, globalOffset holds the dx,dy
     *        between this view and its root. globalOffet may be null.
     * @return true if r is non-empty (i.e. part of the view is visible at the
     *         root level.
     */

举例子看一下，先看布局：

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
                xmlns:tools="http://schemas.android.com/tools"
                android:layout_width="match_parent"
                android:layout_height="match_parent">

    <View
        android:layout_width="100dp"
        android:layout_height="100dp"
        android:background="#0000ff"
        android:layout_marginLeft="-90dp"
        android:layout_marginTop="-90dp">
    </View>

</RelativeLayout>

在xml中定义了一个View，给它设置负值的marginLeft和marginTop，让它只有一部分可以显示在屏幕中。可以看到这个View只有10x10dp大小可以出现在屏幕里面，但是只要有这么点大小可以在屏幕中，上面的方法的返回值就是：visibility=true。

执行的效果如下图所示，可以看到100x100dp的蓝色矩形虽然只剩下左上角的10x10dp蓝色小方块可见，但是visibility仍然等于true。

此时的GlobalVisibleRect的左上角(left,top)和右下角(right,bottom)分别为(0, 280)和(36, 316)。在这里top不为0是因为标题栏和系统状态栏已经占据了一定的屏幕高度。

tips：这里写代码时测试getGlobalVisibleRect方法时，记得要等View已经绘制完成后，再去调用View的getGlobalVisibleRect方法，否则无法得到的返回值都是0。这和获取View的宽高原理是一样的，如果View没有被绘制完成，那么View.getWidth和View.getHeight一定是等于0的。

关于getGlobalVisibleRect方法的特别说明

这个方法只能检查出这个View在手机屏幕（或者说是相对它的父View）的位置，而不能检查出与其他兄弟View的相对位置。

比如说有一个ViewGroup，下面有View1、View2这两个子View，View1和View2是平级关系。此时如果View2盖住了View1，那么用getGlobalVisibleRect方法检查View1的可见性，得到的返回值依然是true，得到的可见矩形区域rect也是没有任何变化的。也就是说View1.getGlobalVisibleRect(rect)得到的结果与View2没有任何关系。

空说无凭，看个具体的例子，先看xml：

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent">

    <View
        android:id="@+id/bottom_view"
        android:layout_width="100dp"
        android:layout_centerInParent="true"
        android:layout_marginLeft="-90dp"
        android:layout_marginTop="-90dp"
        android:layout_height="100dp"
        android:background="#0000ff">
    </View>

    <!-- 这里为了看清bottom_view, 给top_view的背景色加了一个透明度 -->
    <View
        android:id="@+id/top_view"
        android:layout_width="200dp"
        android:layout_height="200dp"
        android:layout_centerInParent="true"
        android:background="#9000ffff">
    </View>

</RelativeLayout>

这个xml很简单，两个View，分别是下层的bottom_view（100x100dp，在父ViewGroup中居中）， top_view（200x200dp，也在父ViewGroup居中，因此可以完全盖住bottom_view）。

我们用getGlobalVisibleRect来获取一下bottom_view的visibleRect和visibility，得到的结果是：visibility=true，rect的左上角(left, top)和右下角(right, bottom)是(545, 1161)和(895, 1511)。

即使把top_view从xml里面删掉，我们得到visibility和rect也是一样的。

所以getGlobalVisibleRect方法并不是万能的，因为它只能检查View和他们的ParentView之间的位置进而判它断是不是在屏幕中可见。

PS：有一次我还想到个奇葩思路，那就是把这个View的兄弟View找出来，也拿出它的GlobalVisibleRect，然后对比兄弟View和这个View的GlobalVisibleRect，看是不是有重合的地方。但是这也只能表明屏幕这一块区域内有两个View，还是无法判断到底是谁遮挡住了谁。

4 View.getLocalVisibleRect

这个方法和getGlobalVisibleRect有些类似，也可以拿到这个View在屏幕的可见区域的坐标，唯一的区别getLocalVisibleRect(rect)获得的rect坐标系的原点是View自己的左上角，而不是屏幕左上角。

先看例子，仍然是使用上面第2个例子的代码，加上下面的代码，执行一下：

Rect localRect = new Rect();
boolean localVisibility = bottom.getLocalVisibleRect(localRect);

得到的local坐标结果是：localVisibility=true，localRect的左上角(left, top)和右下角(right, bottom)为(0, 0)和(350, 350)。

而global坐标的结果是：visibility=true，rect的左上角为(545, 1161)，右下角为(895,1511)。

看下getLocalVisibleRect的源码，原来就是先获取View的offset point（相对屏幕或者ParentView的偏移坐标），然后再去调用getGlobalVisibleRect(Rect r, Point globalOffset)方法来获取可见区域，最后再把得到的GlobalVisibleRect和Offset坐标做一个加减法，转换坐标系原点。

所以只要这个View的左上角在屏幕中，它的LocalVisibleRect的左上角坐标就一定是(0,0)，如果View的右下角在屏幕中，它的LocalVisibleRect右下角坐标就一定是(view.getWidth(), view.getHeight())。

public final boolean getLocalVisibleRect(Rect r) {
        final Point offset = mAttachInfo != null ? mAttachInfo.mPoint : new Point();
        if (getGlobalVisibleRect(r, offset)) {
            r.offset(-offset.x, -offset.y); // make r local
            return true;
        }
        return false;
    }

5. 判断手机屏幕是否熄灭or是否解锁

PowerManager pm = (PowerManager) context.getSystemService(Context.POWER_SERVICE);
boolean isScreenOn = pm.isScreenOn();
boolean isInteractive = pm.isInteractive();
// 可能有些版本上面isScreenOn方法隐藏了或者是deprecated了，可以尝试反射调用它，但是要记得用的时候catch异常
Method isScreenOnMethod = pm.getClass().getMethod("isScreenOn");
boolean isScreenOn = (Boolean) isScreenOnMethod.invoke(pm);

这里不深究解锁和屏幕是否熄灭的实现方法了，检查View的可见性虽然和屏幕的状态看起来没有直接关系，但是在做检查前先对屏幕的状态做一个检查也是很有必要的，如果屏幕都已经关闭了，那这个View当然是对用户不可见的。

三、ListView、RecyclerView、ScrollView中如何检查View的可见性

说实话感觉App开发中用得最多的就是各种列表啊、滚动滑动的View。在Android里面这几个可以滚动的View，都有着各自的特点。在用到上面的检测方法时，可以好好结合这几个View的特点，在它们各自的滚动过程中，更加有效的去检查View的可见性。我们可以先根据自己的业务需要，把上面提到的方法封装成一个VisibilityCheckUtil工具类，例如可以提供一个check方法，当View的物理面积有50%可见时，就返回true。

1. ScrollView

假设我们有一个mView在mScrollView中，我们可以监听mScrollView的滚动，在onScrollChanged中检查mView的可见性。

mScrollView.getViewTreeObserver().addOnScrollChangedListener(
        new ViewTreeObserver.OnScrollChangedListener() {

          @Override
          public void onScrollChanged() {
            // 可以先判断ScrollView中的mView是不是在屏幕中可见
            Rect scrollBounds = new Rect();
            mScrollView.getHitRect(scrollBounds);
            if (!mView.getLocalVisibleRect(scrollBounds)) {
                return;
            }
            
            // 再用封装好的工具类检查可见性是否大于50%
            if (VisibilityCheckUtil.check(mView)) {
                // do something
            }
          }
        });

2. ListView

假设我们在mListView的第10个位置（界面上是第11个item）有一个需要检查可见性的mView。

首先要监听mListView的滚动，接着在onScroll回调中，调用mListView.getFirstVisiblePosition和mListView.getLastVisiblePosition查看第10个位置是否处于可见范围，然后在调用封装好的VisibilityCheckUtil去检查mView是否可见。

mListView.setOnScrollListener(new OnScrollListener() {
      @Override
      public void onScrollStateChanged(AbsListView view, int scrollState) {
        mScrollState = scrollState;
      }

      @Override
      public void onScroll(AbsListView view, int firstVisibleItem, int visibleItemCount,
          int totalItemCount) {
        if (mScrollState == OnScrollListener.SCROLL_STATE_IDLE) {
          return;
        }

        int first = mListView.getFirstVisiblePosition();
        int last = mListView.getLastVisiblePosition();
        // 满足3个条件：先判断ListView中的mView是不是在可见范围中，再判断是不是大于50%面积可见
        if (10 >= first && 10 <= last && VisibilityCheckUtil.check(mView)) {
            // do something
        }
      }
    });

3. RecyclerView

和上面类似，还是把mView摆放在第10个位置，检查原理和ListView类似。

mLinearLayoutManager = new LinearLayoutManager(this);
mRecyclerView.setLayoutManager(mLinearLayoutManager);
mRecyclerView.addOnScrollListener(new RecyclerView.OnScrollListener() {

      @Override
      public void onScrolled(RecyclerView recyclerView, int dx, int dy) {
        super.onScrolled(recyclerView, dx, dy);
        if (mLinearLayoutManager == null) {
          return;
        }

        int firstVisiblePosition = mLinearLayoutManager.findFirstVisibleItemPosition();
        int lastVisiblePosition = mLinearLayoutManager.findLastVisibleItemPosition();
        // 同样是满足3个条件
        if (10 >= firstVisiblePosition && 10 <= lastVisiblePosition && VisibilityCheckUtil.check(mView)) {
          // do something
        }
      }
    });

实际的开发中肯定会遇到更多的场景，我们都要先分析界面的特点，再结合前面提到的几个方法，更有效地检查View的可见性。这里最后再给大家推荐一个开源的项目——VideoPlayerManager，里面就用到getLocalVisibleRect来检测View的可见面积，进而控制在ListView和RecyclerView中哪一个Item应该显示什么内容。

四、小结

本篇博客的思路，都是从View的外部去检查一个View的可见性。首先提到了一些基本的方法，然后介绍了几种常见的界面下可以怎么使用这些各种方法。

如果是App开发者的话，自己写的界面自己去判断View的可见性，有上面这些方法应该就够用了。但是如果你是一个SDK开发者，给App开发者提供第三方的library时（通常是自定义View这类的库），也能够检查开发者的使用到的View，并根据可见性来自动管理一些View的操作，那就非常棒了。这时从外部去检查一个View的可见性可能就不够用了，我们可以换一个角度，从内部去检查一个View的可见性

文章来源：http://unclechen.github.io