PyOpenGL中判断两点可视性及求直线与四边形/三角形交点的方法

Great question! Let’s tackle this from both the "ready-to-use function" angle and the PyOpenGL-specific intersection calculation approach.

1. Ready-to-Use Functions for Line-of-Sight Checks #

If you don’t want to reinvent the wheel, there are several Python libraries that handle visibility checks out of the box:

2D Scenarios #

• Shapely: A powerful geospatial library that makes 2D geometric operations trivial. You can create a LineString between points A and B, then check if it intersects with any obstacle polygons (including triangles/quads).
  Example code snippet:

  from shapely.geometry import LineString, Polygon
  
  def check_2d_visibility(point_a, point_b, obstacles):
      line = LineString([point_a, point_b])
      for obstacle in obstacles:
          # Obstacle can be a Polygon (triangle/quad)
          if line.intersects(Polygon(obstacle)):
              return False  # Obstacle blocks visibility
      return True
  

3D Scenarios #

• Trimesh: A fantastic library for 3D mesh operations. It has built-in ray casting that can directly check if a ray from A to B intersects any mesh faces (triangles/quads).
  Example code snippet:

  import trimesh
  
  def check_3d_visibility(point_a, point_b, mesh_list):
      ray_origin = point_a
      ray_direction = (point_b[0]-point_a[0], point_b[1]-point_a[1], point_b[2]-point_a[2])
      for mesh in mesh_list:
          # Mesh can be a trimesh.Trimesh object created from triangles/quads
          intersections = mesh.ray.intersects_location(ray_origin, ray_direction)
          if len(intersections[0]) > 0:
              # Check if intersection is between A and B (not beyond B)
              for hit_point in intersections[0]:
                  distance_to_hit = ((hit_point[0]-point_a[0])**2 + (hit_point[1]-point_a[1])**2 + (hit_point[2]-point_a[2])**2)**0.5
                  distance_ab = ((point_b[0]-point_a[0])**2 + (point_b[1]-point_a[1])**2 + (point_b[2]-point_a[2])**2)**0.5
                  if distance_to_hit < distance_ab - 1e-6:  # Epsilon to avoid floating point errors
                      return False
      return True
  

2. PyOpenGL-Based Intersection Calculations #

PyOpenGL itself is focused on rendering, so it doesn’t have built-in intersection functions. But you can implement classic geometric algorithms using OpenGL’s math utilities (like glm, the Python binding for OpenGL Mathematics) to handle rays and triangles/quads.

Key Algorithm: Möller-Trumbore Triangle-Ray Intersection #

This is the standard fast algorithm for checking if a ray intersects a triangle. We can wrap it into a function that accepts a list of triangles (or quads, by splitting them into two triangles).

First, install glm if you haven’t:

pip install pyglm

Then implement the core intersection function:

import glm

def ray_triangle_intersection(ray_origin, ray_dir, v0, v1, v2):
    # Convert to glm vectors for easy math
    orig = glm.vec3(ray_origin)
    dir = glm.vec3(ray_dir)
    v0 = glm.vec3(v0)
    v1 = glm.vec3(v1)
    v2 = glm.vec3(v2)

    edge1 = v1 - v0
    edge2 = v2 - v0
    h = glm.cross(dir, edge2)
    a = glm.dot(edge1, h)

    # Ray is parallel to triangle
    if a > -1e-6 and a < 1e-6:
        return None

    f = 1.0 / a
    s = orig - v0
    u = f * glm.dot(s, h)

    if u < 0.0 or u > 1.0:
        return None

    q = glm.cross(s, edge1)
    v = f * glm.dot(dir, q)

    if v < 0.0 or u + v > 1.0:
        return None

    # Calculate intersection point
    t = f * glm.dot(edge2, q)
    if t > 1e-6:  # Ignore intersections behind the ray origin
        hit_point = orig + dir * t
        return (hit_point.x, hit_point.y, hit_point.z)
    else:
        return None

def check_ray_intersections(ray_start, ray_end, geometry_list):
    ray_dir = (ray_end[0]-ray_start[0], ray_end[1]-ray_start[1], ray_end[2]-ray_start[2])
    ray_length_sq = (ray_dir[0]**2 + ray_dir[1]**2 + ray_dir[2]**2)

    for geom in geometry_list:
        if len(geom) == 3:
            # Triangle: 3 vertices
            hit = ray_triangle_intersection(ray_start, ray_dir, geom[0], geom[1], geom[2])
        elif len(geom) == 4:
            # Quad: split into two triangles (v0,v1,v2) and (v0,v2,v3)
            hit1 = ray_triangle_intersection(ray_start, ray_dir, geom[0], geom[1], geom[2])
            hit2 = ray_triangle_intersection(ray_start, ray_dir, geom[0], geom[2], geom[3])
            hit = hit1 or hit2
        else:
            continue  # Skip invalid geometry

        if hit is not None:
            # Check if hit is between ray_start and ray_end
            hit_vec = (hit[0]-ray_start[0], hit[1]-ray_start[1], hit[2]-ray_start[2])
            hit_dist_sq = (hit_vec[0]**2 + hit_vec[1]**2 + hit_vec[2]**2)
            if hit_dist_sq < ray_length_sq - 1e-6:
                return False  # Obstacle blocks the line of sight
    return True

3. Overall Workflow Suggestions #

• For quick prototyping: Use Shapely (2D) or Trimesh (3D) — they handle edge cases (like floating point precision, concave obstacles) much better than custom code.
• If you need tight integration with PyOpenGL: Implement the Möller-Trumbore algorithm with glm for vector math. This keeps your code within the OpenGL ecosystem and avoids external dependencies beyond pyglm.
• Quads handling: Always split quads into two triangles, as most low-level geometric algorithms are optimized for triangles (and quads can be non-planar, which complicates intersection checks).

内容的提问来源于stack exchange，提问作者matousc