Skip to content

Commit cc4e254

Browse files
douiradouira
committed
remove GraphDirection.OPPOSITE since we can also just do a bitwise XOR on the direction index
propagate symmetry into the number of visibility data sets needed, reduce stack size to 3*16 since paths can no longer fold back in on themselves use symmetry to avoid doing half the work in generating visibility data use bitfield index based neighbor traversal instead of conversion to coordinate triplets in vis graph construction, skip origin directions that are opposite the allowed step directions since they cannot lead to any visibility Remove debug code, undo unnecessary changes, delete unused code Avoid continuing the search if all possible destination faces have already been reached Don't generate full visibility data arrays if they're just the same everywhere Fix crash when initializing air chunks and they have no visibility data Perspective based occlusion culling Improve accuracy of visibility data by not allowing the traversal to go backwards
1 parent 977f471 commit cc4e254

File tree

10 files changed

+305
-44
lines changed

10 files changed

+305
-44
lines changed

‎.editorconfig‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ tab_width = 4
99
ij_continuation_indent_size = 8
1010
ij_formatter_off_tag = @formatter:off
1111
ij_formatter_on_tag = @formatter:on
12-
ij_formatter_tags_enabled = false
12+
ij_formatter_tags_enabled = true
1313
ij_smart_tabs = false
1414
ij_wrap_on_typing = false
1515

‎common/src/main/java/net/caffeinemc/mods/sodium/client/render/SodiumWorldRenderer.java‎

Lines changed: 3 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,7 @@
11
package net.caffeinemc.mods.sodium.client.render;
22

3-
import com.llamalad7.mixinextras.sugar.ref.LocalBooleanRef;
4-
import com.mojang.blaze3d.systems.RenderSystem;
53
import com.mojang.blaze3d.textures.GpuSampler;
64
import com.mojang.blaze3d.vertex.PoseStack;
7-
import com.mojang.blaze3d.vertex.SheetedDecalTextureGenerator;
8-
import com.mojang.blaze3d.vertex.VertexConsumer;
9-
import com.mojang.blaze3d.vertex.VertexMultiConsumer;
105
import it.unimi.dsi.fastutil.longs.Long2ObjectMap;
116
import net.caffeinemc.mods.sodium.client.SodiumClientMod;
127
import net.caffeinemc.mods.sodium.client.gl.device.CommandList;
@@ -21,7 +16,6 @@
2116
import net.caffeinemc.mods.sodium.client.render.chunk.translucent_sorting.SortBehavior;
2217
import net.caffeinemc.mods.sodium.client.render.chunk.translucent_sorting.trigger.CameraMovement;
2318
import net.caffeinemc.mods.sodium.client.render.viewport.Viewport;
24-
import net.caffeinemc.mods.sodium.client.services.PlatformBlockAccess;
2519
import net.caffeinemc.mods.sodium.client.services.PlatformRuntimeInformation;
2620
import net.caffeinemc.mods.sodium.client.util.FogParameters;
2721
import net.caffeinemc.mods.sodium.client.util.NativeBuffer;
@@ -31,15 +25,14 @@
3125
import net.minecraft.client.Minecraft;
3226
import net.minecraft.client.multiplayer.ClientLevel;
3327
import net.minecraft.client.player.LocalPlayer;
34-
import net.minecraft.client.renderer.*;
35-
import net.minecraft.client.renderer.blockentity.BlockEntityRenderDispatcher;
28+
import net.minecraft.client.renderer.LevelRenderer;
3629
import net.minecraft.client.renderer.blockentity.state.BlockEntityRenderState;
3730
import net.minecraft.client.renderer.chunk.ChunkSectionLayerGroup;
3831
import net.minecraft.client.renderer.entity.EntityRenderer;
3932
import net.minecraft.client.renderer.entity.state.EntityRenderState;
4033
import net.minecraft.client.renderer.feature.ModelFeatureRenderer;
34+
import net.minecraft.client.renderer.rendertype.RenderType;
4135
import net.minecraft.client.renderer.state.LevelRenderState;
42-
import net.minecraft.client.resources.model.ModelBakery;
4336
import net.minecraft.core.BlockPos;
4437
import net.minecraft.core.SectionPos;
4538
import net.minecraft.server.level.BlockDestructionProgress;
@@ -50,9 +43,9 @@
5043
import net.minecraft.world.level.block.entity.BlockEntity;
5144
import net.minecraft.world.phys.AABB;
5245
import net.minecraft.world.phys.Vec3;
53-
import org.jspecify.annotations.Nullable;
5446
import org.joml.Matrix4f;
5547
import org.joml.Vector3d;
48+
import org.jspecify.annotations.Nullable;
5649

5750
import java.util.Collection;
5851
import java.util.Collections;

‎common/src/main/java/net/caffeinemc/mods/sodium/client/render/chunk/RenderSection.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ public class RenderSection {
2929
private final int chunkX, chunkY, chunkZ;
3030

3131
// Occlusion Culling State
32-
private long visibilityData = VisibilityEncoding.NULL;
32+
private long[] visibilityData = null;
3333

3434
private int incomingDirections;
3535
private int lastVisibleFrame = -1;
@@ -174,7 +174,7 @@ private boolean clearRenderState() {
174174

175175
this.built = false;
176176
this.flags = RenderSectionFlags.NONE;
177-
this.visibilityData = VisibilityEncoding.NULL;
177+
this.visibilityData = null;
178178
this.globalBlockEntities = null;
179179
this.culledBlockEntities = null;
180180
this.animatedSprites = null;
@@ -325,7 +325,7 @@ public int getFlags() {
325325
/**
326326
* Returns the occlusion culling data which determines this chunk's connectedness on the visibility graph.
327327
*/
328-
public long getVisibilityData() {
328+
public long[] getVisibilityData() {
329329
return this.visibilityData;
330330
}
331331

‎common/src/main/java/net/caffeinemc/mods/sodium/client/render/chunk/compile/tasks/ChunkBuilderMeshingTask.java‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
import net.caffeinemc.mods.sodium.client.render.chunk.compile.pipeline.BlockRenderer;
1313
import net.caffeinemc.mods.sodium.client.render.chunk.data.BuiltSectionInfo;
1414
import net.caffeinemc.mods.sodium.client.render.chunk.data.BuiltSectionMeshParts;
15+
import net.caffeinemc.mods.sodium.client.render.chunk.occlusion.DirectionalVisGraph;
1516
import net.caffeinemc.mods.sodium.client.render.chunk.terrain.DefaultTerrainRenderPasses;
1617
import net.caffeinemc.mods.sodium.client.render.chunk.terrain.TerrainRenderPass;
1718
import net.caffeinemc.mods.sodium.client.render.chunk.terrain.material.DefaultMaterials;
@@ -67,7 +68,7 @@ public ChunkBuilderMeshingTask(RenderSection render, int buildTime, Vector3dc ab
6768
public ChunkBuildOutput execute(ChunkBuildContext buildContext, CancellationToken cancellationToken) {
6869
ProfilerFiller profiler = Profiler.get();
6970
BuiltSectionInfo.Builder renderData = new BuiltSectionInfo.Builder();
70-
VisGraph occluder = new VisGraph();
71+
DirectionalVisGraph occluder = new DirectionalVisGraph();
7172

7273
ChunkBuildBuffers buffers = buildContext.buffers;
7374
buffers.init(renderData, this.render.getSectionIndex());
@@ -115,7 +116,10 @@ public ChunkBuildOutput execute(ChunkBuildContext buildContext, CancellationToke
115116
}
116117

117118
blockPos.set(x, y, z);
118-
modelOffset.set(x & 15, y & 15, z & 15);
119+
int localX = x & 15;
120+
int localY = y & 15;
121+
int localZ = z & 15;
122+
modelOffset.set(localX, localY, localZ);
119123

120124
if (blockState.getRenderShape() == RenderShape.MODEL) {
121125
BlockStateModel model = cache.getBlockModels()
@@ -142,7 +146,7 @@ public ChunkBuildOutput execute(ChunkBuildContext buildContext, CancellationToke
142146
}
143147

144148
if (blockState.isSolidRender()) {
145-
occluder.setOpaque(blockPos);
149+
occluder.setOpaque(localX, localY, localZ);
146150
}
147151
}
148152
}

‎common/src/main/java/net/caffeinemc/mods/sodium/client/render/chunk/data/BuiltSectionInfo.java‎

Lines changed: 12 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -9,8 +9,8 @@
99
import net.minecraft.client.renderer.texture.TextureAtlasSprite;
1010
import net.minecraft.core.Direction;
1111
import net.minecraft.world.level.block.entity.BlockEntity;
12+
import org.jetbrains.annotations.Nullable;
1213
import org.jspecify.annotations.NonNull;
13-
import org.jspecify.annotations.Nullable;
1414

1515
import java.util.*;
1616
import java.util.function.IntFunction;
@@ -23,7 +23,7 @@ public class BuiltSectionInfo {
2323
public static final BuiltSectionInfo EMPTY = createEmptyData();
2424

2525
public final int flags;
26-
public final long visibilityData;
26+
public final long[] visibilityData;
2727

2828
public final BlockEntity @Nullable[] globalBlockEntities;
2929
public final BlockEntity @Nullable[] culledBlockEntities;
@@ -33,7 +33,7 @@ private BuiltSectionInfo(@NonNull Collection<TerrainRenderPass> blockRenderPasse
3333
@NonNull Collection<BlockEntity> globalBlockEntities,
3434
@NonNull Collection<BlockEntity> culledBlockEntities,
3535
@NonNull Collection<TextureAtlasSprite> animatedSprites,
36-
@NonNull VisibilitySet occlusionData) {
36+
@NonNull VisibilitySet[] occlusionData) {
3737
this.globalBlockEntities = toArray(globalBlockEntities, BlockEntity[]::new);
3838
this.culledBlockEntities = toArray(culledBlockEntities, BlockEntity[]::new);
3939
this.animatedSprites = toArray(animatedSprites, TextureAtlasSprite[]::new);
@@ -54,7 +54,10 @@ private BuiltSectionInfo(@NonNull Collection<TerrainRenderPass> blockRenderPasse
5454

5555
this.flags = flags;
5656

57-
this.visibilityData = VisibilityEncoding.encode(occlusionData);
57+
this.visibilityData = new long[occlusionData.length];
58+
for (int i = 0; i < occlusionData.length; i++) {
59+
this.visibilityData[i] = VisibilityEncoding.encode(occlusionData[i]);
60+
}
5861
}
5962

6063
public static class Builder {
@@ -63,13 +66,13 @@ public static class Builder {
6366
private final List<BlockEntity> culledBlockEntities = new ArrayList<>();
6467
private final Set<TextureAtlasSprite> animatedSprites = new ObjectOpenHashSet<>();
6568

66-
private VisibilitySet occlusionData;
69+
private VisibilitySet[] occlusionData;
6770

6871
public void addRenderPass(TerrainRenderPass pass) {
6972
this.blockRenderPasses.add(pass);
7073
}
7174

72-
public void setOcclusionData(VisibilitySet data) {
75+
public void setOcclusionData(VisibilitySet[] data) {
7376
this.occlusionData = data;
7477
}
7578

@@ -99,11 +102,11 @@ public BuiltSectionInfo build() {
99102
}
100103

101104
private static BuiltSectionInfo createEmptyData() {
102-
VisibilitySet occlusionData = new VisibilitySet();
103-
occlusionData.add(EnumSet.allOf(Direction.class));
105+
VisibilitySet fullyVisible = new VisibilitySet();
106+
fullyVisible.add(EnumSet.allOf(Direction.class));
104107

105108
BuiltSectionInfo.Builder meshInfo = new BuiltSectionInfo.Builder();
106-
meshInfo.setOcclusionData(occlusionData);
109+
meshInfo.setOcclusionData(new VisibilitySet[] { fullyVisible });
107110

108111
return meshInfo.build();
109112
}

‎common/src/main/java/net/caffeinemc/mods/sodium/client/render/chunk/occlusion/DirectionalVisGraph.java‎

Lines changed: 199 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,199 @@
1+
package net.caffeinemc.mods.sodium.client.render.chunk.occlusion;
2+
3+
import net.caffeinemc.mods.sodium.client.util.collections.BitArray;
4+
import net.minecraft.client.renderer.chunk.VisibilitySet;
5+
6+
public class DirectionalVisGraph {
7+
private static final int SIZE = 16 * 16 * 16;
8+
private static final int STACK_SIZE = 3 * 16;
9+
10+
private static final int DX = 1;
11+
private static final int DY = 16 * 16;
12+
private static final int DZ = 16;
13+
14+
private static final int X_MASK = 0b1111;
15+
private static final int Y_MASK = 0b1111 << 8;
16+
private static final int Z_MASK = 0b1111 << 4;
17+
18+
private static final int[] DIRECTION_SETS = new int[] {
19+
// corresponding to GraphDirection from MSB to LSB:
20+
// east, west, south, north, up, down
21+
// half of the directions are omitted since their visibility is the same as the opposite direction set
22+
23+
//@formatter:off
24+
0b010101, // 0: west, north, down
25+
0b010110, // 1: west, north, up
26+
0b011001, // 2: west, south, down
27+
// 0b011010, // 3: west, south, up
28+
0b100101, // 4: east, north, down
29+
// 0b100110, // 5: east, north, up
30+
// 0b101001, // 6: east, south, down
31+
// 0b101010, // 7: east, south, up
32+
//@formatter:on
33+
};
34+
35+
private final BitArray blocks = new BitArray(SIZE);
36+
private int filled = 0;
37+
38+
private static int getIndex(int x, int y, int z) {
39+
return x | (z << 4) | (y << 8);
40+
}
41+
42+
public void setOpaque(int x, int y, int z) {
43+
this.blocks.set(getIndex(x, y, z));
44+
this.filled++;
45+
}
46+
47+
public VisibilitySet[] resolve() {
48+
// if all blocks are filled, nothing is visible
49+
if (this.filled == SIZE) {
50+
var visibilitySet = new VisibilitySet();
51+
visibilitySet.setAll(false);
52+
return new VisibilitySet[] {
53+
visibilitySet
54+
};
55+
}
56+
57+
// if fewer blocks are filled than necessary to block visibility between two faces, all faces are visible to each other
58+
if (this.filled < 256) {
59+
var visibilitySet = new VisibilitySet();
60+
visibilitySet.setAll(true);
61+
return new VisibilitySet[] {
62+
visibilitySet
63+
};
64+
}
65+
66+
// generate visibility data for each base perspective
67+
var results = new VisibilitySet[DIRECTION_SETS.length];
68+
for (int i = 0; i < DIRECTION_SETS.length; i++) {
69+
results[i] = resolveWithDirections(DIRECTION_SETS[i]);
70+
}
71+
72+
return results;
73+
}
74+
75+
private VisibilitySet resolveWithDirections(int directionSet) {
76+
var visibilitySet = new VisibilitySet();
77+
78+
// search starting at each face opposite an allowed step direction
79+
int originDirections = (~directionSet) & GraphDirectionSet.ALL;
80+
81+
var stackPos = new short[STACK_SIZE];
82+
var stackDirs = new byte[STACK_SIZE];
83+
for (int i = 0; i < 3; i++) {
84+
int originDirection = Integer.numberOfTrailingZeros(originDirections);
85+
originDirections &= ~(1 << originDirection);
86+
87+
int minX = 0, minY = 0, minZ = 0;
88+
int maxX = 15, maxY = 15, maxZ = 15;
89+
switch (originDirection) {
90+
case GraphDirection.DOWN -> maxY = 0;
91+
case GraphDirection.UP -> minY = 15;
92+
case GraphDirection.NORTH -> maxZ = 0;
93+
case GraphDirection.SOUTH -> minZ = 15;
94+
case GraphDirection.WEST -> maxX = 0;
95+
case GraphDirection.EAST -> minX = 15;
96+
}
97+
98+
var visited = this.blocks.copy();
99+
100+
for (int x = minX; x <= maxX; x++) {
101+
for (int y = minY; y <= maxY; y++) {
102+
for (int z = minZ; z <= maxZ; z++) {
103+
int originIndex = getIndex(x, y, z);
104+
if (!visited.getAndSet(originIndex)) {
105+
search(visited, visibilitySet, stackPos, stackDirs, originDirection, directionSet, originIndex);
106+
}
107+
}
108+
}
109+
}
110+
}
111+
112+
return visibilitySet;
113+
}
114+
115+
private void search(BitArray visited, VisibilitySet visibilitySet, short[] stackPos, byte[] stackDirs, int originFace, int directionSet, int originIndex) {
116+
int stackSize = 0;
117+
118+
stackPos[stackSize++] = (short) originIndex;
119+
stackDirs[0] = (byte) directionSet;
120+
121+
// the faces that we cannot move towards are the ones that cannot become visible because of teh perspective of the camera. This always includes the origin face.
122+
int connectedFaces = GraphDirectionSet.of(~directionSet);
123+
124+
while (stackSize > 0) {
125+
int stackIndex = stackSize - 1;
126+
int remainingDirs = stackDirs[stackIndex];
127+
128+
// backtrack when all directions have been tried
129+
if (remainingDirs == 0) {
130+
stackSize--;
131+
continue;
132+
}
133+
134+
int nextDir = Integer.numberOfTrailingZeros(remainingDirs);
135+
stackDirs[stackIndex] &= (byte) ~(1 << nextDir);
136+
137+
int currentIndex = stackPos[stackIndex];
138+
139+
int neighborIndex;
140+
boolean reachedFace;
141+
switch (nextDir) {
142+
case GraphDirection.DOWN -> {
143+
neighborIndex = currentIndex - DY;
144+
reachedFace = (neighborIndex & Y_MASK) == Y_MASK;
145+
}
146+
case GraphDirection.UP -> {
147+
neighborIndex = currentIndex + DY;
148+
reachedFace = (neighborIndex & Y_MASK) == 0;
149+
}
150+
case GraphDirection.NORTH -> {
151+
neighborIndex = currentIndex - DZ;
152+
reachedFace = (neighborIndex & Z_MASK) == Z_MASK;
153+
}
154+
case GraphDirection.SOUTH -> {
155+
neighborIndex = currentIndex + DZ;
156+
reachedFace = (neighborIndex & Z_MASK) == 0;
157+
}
158+
case GraphDirection.WEST -> {
159+
neighborIndex = currentIndex - DX;
160+
reachedFace = (neighborIndex & X_MASK) == X_MASK;
161+
}
162+
case GraphDirection.EAST -> {
163+
neighborIndex = currentIndex + DX;
164+
reachedFace = (neighborIndex & X_MASK) == 0;
165+
}
166+
default -> throw new IllegalStateException("Unexpected graph direction: " + nextDir);
167+
}
168+
169+
// check reaching the edge of the chunk
170+
if (reachedFace) {
171+
// reached the edge, mark visibility between origin face and this face
172+
connectedFaces |= GraphDirectionSet.of(nextDir);
173+
174+
// stop searching if all potentially reachable faces have been reached
175+
if (connectedFaces == directionSet) {
176+
break;
177+
}
178+
179+
continue;
180+
}
181+
182+
if (visited.getAndSet(neighborIndex)) {
183+
// already visited or opaque
184+
continue;
185+
}
186+
187+
// visit the neighbor
188+
stackPos[stackSize] = (short) neighborIndex;
189+
stackDirs[stackSize] = (byte) directionSet;
190+
stackSize++;
191+
}
192+
193+
for (int direction = 0; direction < GraphDirection.COUNT; direction++) {
194+
if (GraphDirectionSet.contains(connectedFaces, direction)) {
195+
visibilitySet.set(GraphDirection.toEnum(originFace), GraphDirection.toEnum(direction), true);
196+
}
197+
}
198+
}
199+
}

0 commit comments

Comments
 (0)