确定3D对象是否被另一3D对象隐藏

Question

我在Viewport3D中有一些GeometryModel3D球，它们中的一些是可见的，其中一些被蓝色立方体隐藏。 （下面的图片在2D中让我们假装所有的物体都是3D）

我想确定哪个红球可以被看到，哪些被隐藏。

我该怎么做？

Answer 1

这个问题也被称为Occlusion Culling，虽然你有兴趣计数闭塞元。鉴于你的场景，一个强力的办法来解决这个问题（假设你使用透视投影）的条件是以下伪代码：

occludedSpheresCount = 0 
spheres = {Set of spheres} 
cubes = {Set of cubes} 
normalizedCubes = {} 

# First, build the set of normalized cubes (it means, 
# take the cubes that are free in space and transform their 
# coordinates to values between [-1, -1, -1] and [1, 1, 1], they are the same 
# cubes but now the coordinates are laying in that range 
# To do that, use the 

 
     ProjectionMatrix

projectionMatrix = GetProjectionMatrix(perspectiveCamera) 
for each cube in cubes do 
    Rect3D boundingBox = cube.Bounds() 
    Rect3D normalizedBBox = projectionMatrix.transform(boundingBox) 
    cubes_normalized.add(normalizedBBox) 
end for 

# Now search every sphere, normalize it's bounding box 
# and check if it's been occluded by some normalized cube 
for each sphere in spheres do 
    Rect3D sphereBBox = sphere.Bounds() 
    Rect3D normalizedSphere = projectionMatrix.transform(sphereBBox) 
    for each normalizedCube in normalizedCubes do 
     x0 = normalizedCube.Location.X - (normalizedCube.Location.SizeX/2) 
     y0 = normalizedCube.Location.Y - (normalizedCube.Location.SizeY/2) 
     z0 = normalizedCube.Location.Z - (normalizedCube.Location.SizeZ/2) 

     xf = normalizedCube.Location.X + (normalizedCube.Location.SizeX/2) 
     yf = normalizedCube.Location.Y + (normalizedCube.Location.SizeY/2) 

     sx0 <- normalizedSphere.Location.X - (normalizedSphere.Location.SizeX/2) 
     sy0 <- normalizedSphere.Location.X - (normalizedSphere.Location.SizeY/2) 
     sz0 <- normalizedSphere.Location.X - (normalizedSphere.Location.SizeZ/2) 

     sxf <- normalizedSphere.Location.X + (normalizedSphere.Location.SizeX/2) 
     syf <- normalizedSphere.Location.X + (normalizedSphere.Location.SizeY/2) 

     # First, let's check that the normalized-sphere is behind the 
     # normalized-cube, to do that, let's compare their z-front values 
     if z0 > sz0 then 
      # Now that we know that the sphere is behind the frontface of the cube 
      # lets check if it is fully contained inside the 
      # the normalized-cube, in that case, it is occluded 

      if sx0 >= x0 and sxf <= xf and sy0 >= y0 and syf >= yf then 
        occludedSpheresCount++ 
        # Here you can even avoid rendering the sphere altogether 
      end if 
     end if 
    end for 
end for 

一种方式来获得的projectionMatrix使用以下代码（来自here萃取）：

private static Matrix3D GetProjectionMatrix(PerspectiveCamera camera, double aspectRatio) 
    { 
     // This math is identical to what you find documented for 
     // D3DXMatrixPerspectiveFovRH with the exception that in 
     // WPF the camera's horizontal rather the vertical 
     // field-of-view is specified. 
     double hFoV = MathUtils.DegreesToRadians(camera.FieldOfView); 
     double zn = camera.NearPlaneDistance; 
     double zf = camera.FarPlaneDistance; 
     double xScale = 1/Math.Tan(hFoV/2); 
     double yScale = aspectRatio * xScale; 
     double m33 = (zf == double.PositiveInfinity) ? -1 : (zf/(zn - zf)); 
     double m43 = zn * m33; 
     return new Matrix3D(
      xScale, 0, 0, 0, 
       0, yScale, 0, 0, 
       0, 0, m33, -1, 
       0, 0, m43, 0); 
    } 

这个方法的唯一缺点是在以下情况下：

 
    +--------------+--------------+ 
    |    -|-    | 
    |   /| \   | 
    |   | | |   | 
    |   \ |/   | 
    |    -|-    | 
    +--------------+--------------+ 

or 
      interception here 
        | 
        v 
    +----------+--+--------------+ 
    |   | -|-    | 
    |   /| | \   | 
    |  | | | |   | 
    |   \| |/   | 
    |   | -|-    | 
    +----------+--+--------------+ 

在这两个遮光立方体闭塞的领域，在这种情况下，你必须建立一套套标准化立方体（Set{ Set{ cube1, cube2}, Set{cube3, cube4}, ... }）当两个或多个立方体区域拦截（即可以在第一循环中完成）并且争用测试会更加复杂。不知道你的程序是否允许（立方体拦截），虽然

这个算法是O(n^2)因为是一个蛮力的方法，希望这可以给你一个提示的权威性解决方案，如果你正在寻找更高效的一般解决方案，请使用类似Hierarchical Z Buffering