Module: Quake::Bsp::Vis

Defined in:
lib/quake/bsp/vis.rb

Overview

PVS (Potentially Visible Set) decompression and leaf lookup. Each leaf stores a compressed bitvector indicating which other leaves are visible from it. The compression is simple RLE: a zero byte is followed by a count of zero bytes to insert.

Class Method Summary collapse

Class Method Details

.all_visible(num_leafs) ⇒ Object 



106
107
108
 
# File 'lib/quake/bsp/vis.rb', line 106

def self.all_visible(num_leafs)
  Set.new(1..num_leafs)
end

.decompress_pvs(visibility, vis_offset, num_leafs) ⇒ Object

Decompress the PVS for a leaf into an array of visible leaf indices. visibility - raw visibility lump data (String) vis_offset - byte offset into visibility data for this leaf num_leafs - total number of leafs in the level (excluding leaf 0) Returns a Set of visible leaf indices (1-based, matching leafs array).



15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/quake/bsp/vis.rb', line 15

def self.decompress_pvs(visibility, vis_offset, num_leafs)
  return all_visible(num_leafs) if vis_offset < 0 || visibility.nil? || visibility.empty?

  num_bytes = (num_leafs + 7) / 8
  pvs = String.new("\0" * num_bytes, encoding: Encoding::BINARY)

  src = vis_offset
  dst = 0

  while dst < num_bytes
    byte = visibility.getbyte(src)
    # Vis data ended before filling the bitvector. Remaining bytes
    # are already zero (no additional visible leaves), which is safe.
    break if byte.nil?
    src += 1

    if byte != 0
      pvs.setbyte(dst, byte)
      dst += 1
    else
      # RLE: next byte is count of zero bytes
      count = visibility.getbyte(src) || 0
      src += 1
      dst += count # pvs already zeroed
    end
  end

  # Convert bitvector to set of leaf indices
  visible = Set.new
  num_leafs.times do |i|
    byte_idx = i / 8
    bit_idx = i % 8
    if pvs.getbyte(byte_idx) & (1 << bit_idx) != 0
      visible << (i + 1) # leaf indices are 1-based (leaf 0 is the solid leaf)
    end
  end
  visible
end

.point_in_leaf(level, point) ⇒ Object

Find which leaf a point is in by walking the BSP node tree.



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/quake/bsp/vis.rb', line 55

def self.point_in_leaf(level, point)
  node_index = 0

  loop do
    node = level.nodes[node_index]
    plane = level.planes[node.plane_index]

    dist = point.dot(plane.normal) - plane.dist
    child = dist >= 0 ? node.children[0] : node.children[1]

    # Negative child index means leaf: ~child gives leaf index
    if child < 0
      return ~child
    else
      node_index = child
    end
  end
end

.visible_faces(level, leaf_index) ⇒ Object

Mark which faces are visible from the given leaf. Returns a Set of face indices that should be rendered.



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/quake/bsp/vis.rb', line 76

def self.visible_faces(level, leaf_index)
  leaf = level.leafs[leaf_index]
  return Set.new if leaf.nil?

  num_leafs = level.leafs.size - 1 # exclude leaf 0
  # Leaf 0 is the universal SOLID leaf and has no real PVS; its
  # vis_offset is unused but Quake BSPs sometimes store 0 here, which
  # would otherwise decompress garbage. Match TyrQuake Mod_LeafPVS:
  # treat the solid leaf as all-visible so a camera that ends up in
  # solid space (noclip, edge cases) still sees the world.
  visible_leafs = if leaf_index == 0
                    all_visible(num_leafs)
                  else
                    decompress_pvs(level.visibility, leaf.vis_offset, num_leafs)
                  end

  face_set = Set.new
  visible_leafs.each do |li|
    vl = level.leafs[li]
    next if vl.nil?

    vl.num_marksurfaces.times do |i|
      face_idx = level.marksurfaces[vl.first_marksurface + i]
      face_set << face_idx
    end
  end

  face_set
end