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

.add_to_fat_pvs(level, point, node_index, num_leafs, result) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/quake/bsp/vis.rb', line 87

def self.add_to_fat_pvs(level, point, node_index, num_leafs, result)
  loop do
    if node_index < 0
      leaf_index = ~node_index
      return if leaf_index == 0 # skip the universal solid leaf
      leaf = level.leafs[leaf_index]
      return if leaf.nil?
      result.merge(decompress_pvs(level.visibility, leaf.vis_offset, num_leafs))
      return
    end

    node = level.nodes[node_index]
    plane = level.planes[node.plane_index]
    d = point.dot(plane.normal) - plane.dist

    if d > 8.0
      node_index = node.children[0]
    elsif d < -8.0
      node_index = node.children[1]
    else
      # Straddling the plane within the fat radius - descend both sides
      add_to_fat_pvs(level, point, node.children[0], num_leafs, result)
      node_index = node.children[1]
    end
  end
end

.all_visible(num_leafs) ⇒ Object 



241
242
243
 
# File 'lib/quake/bsp/vis.rb', line 241

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

.fat_pvs(level, point) ⇒ Object

Compute a “fat” PVS by unioning the PVS of every leaf within ~8 units of the given point. Used near translucent water surfaces so the underwater leaves (which standard PVS excludes from above-water leaves) are included; without this the cave bed isn’t drawn and alpha-blended water shows the clear color through gaps. Port of quakespasm SV_FatPVS / SV_AddToFatPVS.



80
81
82
83
84
85
 
# File 'lib/quake/bsp/vis.rb', line 80

def self.fat_pvs(level, point)
  num_leafs = level.leafs.size - 1
  result = Set.new
  add_to_fat_pvs(level, point, 0, num_leafs, result)
  result
end

.liquid_face_to_leaves(level) ⇒ Object

Precompute, for each liquid (turb) face, the two leaves it physically separates (computed via BSP traversal of a point on either side of the face’s plane). The standard Quake VIS compiler treats water as opaque, so above-water and underwater leaves never see each other in the PVS. Marksurface lists are also unreliable here - many water faces are marked in only one leaf - so we use geometry instead. We use this index at runtime to “vis-through” water surfaces: when a water face is in the visible set, also include the leaves on its other side. Without this, translucent water alpha-blends against the clear color where the cave bed should be.



140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
 
# File 'lib/quake/bsp/vis.rb', line 140

def self.liquid_face_to_leaves(level)
  @liquid_face_to_leaves_cache ||= {}
  cached = @liquid_face_to_leaves_cache[level.object_id]
  return cached if cached

  index = {}
  level.faces.each_with_index do |face, face_idx|
    next if face.nil?
    ti = level.texinfo[face.texinfo_index]
    next if ti.nil?
    tex = level.textures[ti.miptex_index]
    next unless tex && tex.name.start_with?("*")

    # Compute face center
    cx = cy = cz = 0.0
    n = face.num_edges
    n.times do |i|
      se = level.surfedges[face.first_edge + i]
      edge = level.edges[se.abs]
      v = se >= 0 ? level.vertices[edge.v0] : level.vertices[edge.v1]
      cx += v.x; cy += v.y; cz += v.z
    end
    cx /= n; cy /= n; cz /= n

    plane = level.planes[face.plane_index]
    # Step a small distance along + and - the plane normal, find the
    # leaf each point lands in.
    offsets = [1.0, -1.0]
    leaves = offsets.map do |o|
      pt = Math::Vec3.new(
        cx + plane.normal.x * o,
        cy + plane.normal.y * o,
        cz + plane.normal.z * o
      )
      point_in_leaf(level, pt)
    end.uniq.reject { |l| l == 0 } # skip solid leaf

    index[face_idx] = leaves
  end

  @liquid_face_to_leaves_cache[level.object_id] = index
  index
end

.near_liquid_portal?(level, leaf) ⇒ Boolean

True if any of the given leaf’s marksurfaces is a turbulent (liquid) surface. Quakespasm’s “near water portal” check.

Returns:

  • (Boolean) 


116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/quake/bsp/vis.rb', line 116

def self.near_liquid_portal?(level, leaf)
  return false if leaf.nil?
  leaf.num_marksurfaces.times do |i|
    face_idx = level.marksurfaces[leaf.first_marksurface + i]
    face = level.faces[face_idx]
    next if face.nil?
    ti = level.texinfo[face.texinfo_index]
    next if ti.nil?
    tex = level.textures[ti.miptex_index]
    return true if tex && tex.name.start_with?("*")
  end
  false
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, point: nil) ⇒ Object

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



186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
 
# File 'lib/quake/bsp/vis.rb', line 186

def self.visible_faces(level, leaf_index, point: nil)
  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)
                  elsif point && near_liquid_portal?(level, leaf)
                    # Camera leaf touches a liquid surface. Use FatPVS
                    # so the underwater leaves are included and
                    # translucent water doesn't reveal void where the
                    # bed should be.
                    fat_pvs(level, point)
                  else
                    decompress_pvs(level.visibility, leaf.vis_offset, num_leafs)
                  end

  face_set = Set.new
  leafs_to_walk = visible_leafs.dup
  leafs_to_walk << leaf_index # also include current leaf

  # Vis-through water: any visible water face brings the leaves on its
  # other side into view too. Standard Quake PVS treats water as
  # opaque, so without this expansion translucent water from above
  # blends against void instead of the underwater cave bed.
  liquid_index = liquid_face_to_leaves(level)
  seen_leafs = Set.new
  worklist = leafs_to_walk.to_a

  while (li = worklist.shift)
    next unless seen_leafs.add?(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

      # If this is a water face, queue the leaves on its other side.
      other_leaves = liquid_index[face_idx]
      next unless other_leaves
      other_leaves.each do |other_leaf|
        worklist << other_leaf unless seen_leafs.include?(other_leaf)
      end
    end
  end

  face_set
end