Skip to content

Commit 866c66f

Browse files
douiradouira
authored
Efficient CPU Translucency Sorting with BSP Trees and Heuristics (#2016)
This PR implements efficient CPU translucency sorting. See #2016 for a useful overview of the concepts. Closes #38
1 parent 2272018 commit 866c66f

File tree

81 files changed

+6223
-336
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

81 files changed

+6223
-336
lines changed

‎CONTRIBUTING.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ with some minor changes, as described below.
1111
- If you are using more than three levels of indentation, you should likely consider restructuring your code.
1212
- Branches which are only exceptionally or very rarely taken should remain concise. When this is not possible,
1313
prefer breaking out to a new method (where it makes sense) as this helps the compiler better optimize the code.
14-
- Use `this` to qualify member and field access, as it avoids some ambiguity in certain contexts.
14+
- Use `this` to qualify method and field access, as it avoids some ambiguity in certain contexts.
1515

1616
We also provide these code styles as [EditorConfig](https://editorconfig.org/) files, which most Java IDEs will
1717
automatically detect and make use of.

‎build.gradle.kts‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,7 @@ dependencies {
6565
minecraft(group = "com.mojang", name = "minecraft", version = Constants.MINECRAFT_VERSION)
6666
mappings(loom.officialMojangMappings())
6767
modImplementation(group = "net.fabricmc", name = "fabric-loader", version = Constants.FABRIC_LOADER_VERSION)
68+
include(implementation(group = "com.lodborg", name = "interval-tree", version = "1.0.0"))
6869

6970
fun addEmbeddedFabricModule(name: String) {
7071
val module = fabricApi.module(name, Constants.FABRIC_API_VERSION)

‎src/api/java/net/caffeinemc/mods/sodium/api/util/NormI8.java‎

Lines changed: 38 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
package net.caffeinemc.mods.sodium.api.util;
22

33
import net.minecraft.util.Mth;
4-
import org.joml.Vector3f;
4+
import org.joml.Vector3fc;
55

66
/**
77
* Provides some utilities for working with packed normal vectors. Each normal component provides 8 bits of
@@ -27,7 +27,7 @@ public class NormI8 {
2727
*/
2828
private static final float NORM = 1.0f / COMPONENT_RANGE;
2929

30-
public static int pack(Vector3f normal) {
30+
public static int pack(Vector3fc normal) {
3131
return pack(normal.x(), normal.y(), normal.z());
3232
}
3333

@@ -78,4 +78,40 @@ public static float unpackY(int norm) {
7878
public static float unpackZ(int norm) {
7979
return ((byte) ((norm >> Z_COMPONENT_OFFSET) & 0xFF)) * NORM;
8080
}
81+
82+
/**
83+
* Flips the direction of a packed normal by negating each component. (multiplication by -1)
84+
* @param norm The packed normal
85+
*/
86+
public static int flipPacked(int norm) {
87+
int normX = (((norm >> X_COMPONENT_OFFSET) & 0xFF) * -1) & 0xFF;
88+
int normY = (((norm >> Y_COMPONENT_OFFSET) & 0xFF) * -1) & 0xFF;
89+
int normZ = (((norm >> Z_COMPONENT_OFFSET) & 0xFF) * -1) & 0xFF;
90+
91+
return (normZ << Z_COMPONENT_OFFSET) | (normY << Y_COMPONENT_OFFSET) | (normX << X_COMPONENT_OFFSET);
92+
}
93+
94+
/**
95+
* Returns true if the two packed normals are opposite directions.
96+
*
97+
* TODO: this could possibly be faster by using normA == (~normB + 0x010101) but
98+
* that has to special case when a component is zero since that wouldn't
99+
* overflow correctly back to zero. (~0+1 == 0 but not if it's somewhere inside
100+
* th int)
101+
*
102+
* @param normA The first packed normal
103+
* @param normB The second packed normal
104+
*/
105+
public static boolean isOpposite(int normA, int normB) {
106+
// use byte to automatically sign extend the components
107+
byte normAX = (byte) (normA >> X_COMPONENT_OFFSET);
108+
byte normAY = (byte) (normA >> Y_COMPONENT_OFFSET);
109+
byte normAZ = (byte) (normA >> Z_COMPONENT_OFFSET);
110+
111+
byte normBX = (byte) (normB >> X_COMPONENT_OFFSET);
112+
byte normBY = (byte) (normB >> Y_COMPONENT_OFFSET);
113+
byte normBZ = (byte) (normB >> Z_COMPONENT_OFFSET);
114+
115+
return normAX == -normBX && normAY == -normBY && normAZ == -normBZ;
116+
}
81117
}

‎src/main/java/net/caffeinemc/mods/sodium/client/gui/SodiumGameOptionPages.java‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -312,6 +312,17 @@ public static OptionPage performance() {
312312
.build())
313313
.build());
314314

315+
groups.add(OptionGroup.createBuilder()
316+
.add(OptionImpl.createBuilder(boolean.class, sodiumOpts)
317+
.setName(Component.translatable("sodium.options.sort_behavior.name"))
318+
.setTooltip(Component.translatable("sodium.options.sort_behavior.tooltip"))
319+
.setControl(TickBoxControl::new)
320+
.setBinding((opts, value) -> opts.performance.sortingEnabled = value, opts -> opts.performance.sortingEnabled)
321+
.setImpact(OptionImpact.LOW)
322+
.setFlags(OptionFlag.REQUIRES_RENDERER_RELOAD)
323+
.build())
324+
.build());
325+
315326
return new OptionPage(Component.translatable("sodium.options.pages.performance"), ImmutableList.copyOf(groups));
316327
}
317328

‎src/main/java/net/caffeinemc/mods/sodium/client/gui/SodiumGameOptions.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
import com.google.gson.annotations.SerializedName;
77
import net.caffeinemc.mods.sodium.client.gui.options.TextProvider;
88
import net.caffeinemc.mods.sodium.client.util.FileUtil;
9+
import net.caffeinemc.mods.sodium.client.render.chunk.translucent_sorting.SortBehavior;
910
import net.fabricmc.loader.api.FabricLoader;
1011
import net.minecraft.client.GraphicsStatus;
1112
import net.minecraft.network.chat.Component;
@@ -44,6 +45,12 @@ public static class PerformanceSettings {
4445
public boolean useFogOcclusion = true;
4546
public boolean useBlockFaceCulling = true;
4647
public boolean useNoErrorGLContext = true;
48+
49+
public boolean sortingEnabled = true;
50+
51+
public SortBehavior getSortBehavior() {
52+
return this.sortingEnabled ? SortBehavior.DYNAMIC_DEFER_NEARBY_ONE_FRAME : SortBehavior.OFF;
53+
}
4754
}
4855

4956
public static class AdvancedSettings {

‎src/main/java/net/caffeinemc/mods/sodium/client/model/quad/BakedQuadView.java‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@
44

55
public interface BakedQuadView extends ModelQuadView {
66
ModelQuadFacing getNormalFace();
7-
7+
8+
int getNormal();
9+
810
boolean hasShade();
911
}

‎src/main/java/net/caffeinemc/mods/sodium/client/model/quad/ModelQuadView.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package net.caffeinemc.mods.sodium.client.model.quad;
22

33
import net.caffeinemc.mods.sodium.client.model.quad.properties.ModelQuadFlags;
4+
import net.caffeinemc.mods.sodium.api.util.NormI8;
45
import net.minecraft.client.renderer.texture.TextureAtlasSprite;
56
import net.minecraft.core.Direction;
67

@@ -61,4 +62,43 @@ public interface ModelQuadView {
6162
default boolean hasColor() {
6263
return this.getColorIndex() != -1;
6364
}
65+
66+
default int calculateNormal() {
67+
final float x0 = getX(0);
68+
final float y0 = getY(0);
69+
final float z0 = getZ(0);
70+
71+
final float x1 = getX(1);
72+
final float y1 = getY(1);
73+
final float z1 = getZ(1);
74+
75+
final float x2 = getX(2);
76+
final float y2 = getY(2);
77+
final float z2 = getZ(2);
78+
79+
final float x3 = getX(3);
80+
final float y3 = getY(3);
81+
final float z3 = getZ(3);
82+
83+
final float dx0 = x2 - x0;
84+
final float dy0 = y2 - y0;
85+
final float dz0 = z2 - z0;
86+
final float dx1 = x3 - x1;
87+
final float dy1 = y3 - y1;
88+
final float dz1 = z3 - z1;
89+
90+
float normX = dy0 * dz1 - dz0 * dy1;
91+
float normY = dz0 * dx1 - dx0 * dz1;
92+
float normZ = dx0 * dy1 - dy0 * dx1;
93+
94+
// normalize by length for the packed normal
95+
float length = (float) Math.sqrt(normX * normX + normY * normY + normZ * normZ);
96+
if (length != 0.0 && length != 1.0) {
97+
normX /= length;
98+
normY /= length;
99+
normZ /= length;
100+
}
101+
102+
return NormI8.pack(normX, normY, normZ);
103+
}
64104
}

‎src/main/java/net/caffeinemc/mods/sodium/client/model/quad/properties/ModelQuadFacing.java‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,14 @@
11
package net.caffeinemc.mods.sodium.client.model.quad.properties;
22

3+
import net.caffeinemc.mods.sodium.client.util.DirectionUtil;
4+
import net.caffeinemc.mods.sodium.api.util.NormI8;
35
import net.minecraft.core.Direction;
6+
import net.minecraft.util.Mth;
7+
import org.joml.Math;
8+
import org.joml.Vector3f;
9+
import org.joml.Vector3fc;
10+
11+
import java.util.Arrays;
412

513
public enum ModelQuadFacing {
614
POS_X,
@@ -14,10 +22,28 @@ public enum ModelQuadFacing {
1422
public static final ModelQuadFacing[] VALUES = ModelQuadFacing.values();
1523

1624
public static final int COUNT = VALUES.length;
25+
public static final int DIRECTIONS = VALUES.length - 1;
1726

1827
public static final int NONE = 0;
1928
public static final int ALL = (1 << COUNT) - 1;
2029

30+
public static final Vector3fc[] ALIGNED_NORMALS = new Vector3fc[] {
31+
new Vector3f(1, 0, 0),
32+
new Vector3f(0, 1, 0),
33+
new Vector3f(0, 0, 1),
34+
new Vector3f(-1, 0, 0),
35+
new Vector3f(0, -1, 0),
36+
new Vector3f(0, 0, -1),
37+
};
38+
39+
public static final int[] PACKED_ALIGNED_NORMALS = Arrays.stream(ALIGNED_NORMALS)
40+
.mapToInt(NormI8::pack)
41+
.toArray();
42+
43+
public static final int OPPOSING_X = 1 << ModelQuadFacing.POS_X.ordinal() | 1 << ModelQuadFacing.NEG_X.ordinal();
44+
public static final int OPPOSING_Y = 1 << ModelQuadFacing.POS_Y.ordinal() | 1 << ModelQuadFacing.NEG_Y.ordinal();
45+
public static final int OPPOSING_Z = 1 << ModelQuadFacing.POS_Z.ordinal() | 1 << ModelQuadFacing.NEG_Z.ordinal();
46+
2147
public static ModelQuadFacing fromDirection(Direction dir) {
2248
return switch (dir) {
2349
case DOWN -> NEG_Y;
@@ -40,4 +66,58 @@ public ModelQuadFacing getOpposite() {
4066
default -> UNASSIGNED;
4167
};
4268
}
69+
70+
public int getSign() {
71+
return switch (this) {
72+
case POS_Y, POS_X, POS_Z -> 1;
73+
case NEG_Y, NEG_X, NEG_Z -> -1;
74+
default -> 0;
75+
};
76+
}
77+
78+
public int getAxis() {
79+
return switch (this) {
80+
case POS_X, NEG_X -> 0;
81+
case POS_Y, NEG_Y -> 1;
82+
case POS_Z, NEG_Z -> 2;
83+
default -> -1;
84+
};
85+
}
86+
87+
public boolean isAligned() {
88+
return this != UNASSIGNED;
89+
}
90+
91+
public Vector3fc getAlignedNormal() {
92+
if (!this.isAligned()) {
93+
throw new IllegalStateException("Cannot get aligned normal for unassigned facing");
94+
}
95+
return ALIGNED_NORMALS[this.ordinal()];
96+
}
97+
98+
public int getPackedAlignedNormal() {
99+
if (!this.isAligned()) {
100+
throw new IllegalStateException("Cannot get packed aligned normal for unassigned facing");
101+
}
102+
return PACKED_ALIGNED_NORMALS[this.ordinal()];
103+
}
104+
105+
public static ModelQuadFacing fromNormal(float x, float y, float z) {
106+
if (!(Math.isFinite(x) && Math.isFinite(y) && Math.isFinite(z))) {
107+
return ModelQuadFacing.UNASSIGNED;
108+
}
109+
110+
for (Direction face : DirectionUtil.ALL_DIRECTIONS) {
111+
var step = face.step();
112+
if (Mth.equal(Math.fma(x, step.x(), Math.fma(y, step.y(), z * step.z())), 1.0f)) {
113+
return ModelQuadFacing.fromDirection(face);
114+
}
115+
}
116+
117+
return ModelQuadFacing.UNASSIGNED;
118+
}
119+
120+
public static ModelQuadFacing fromPackedNormal(int normal) {
121+
return fromNormal(NormI8.unpackX(normal), NormI8.unpackY(normal), NormI8.unpackZ(normal));
122+
}
43123
}

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

Lines changed: 28 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
import net.caffeinemc.mods.sodium.client.render.chunk.map.ChunkTracker;
1717
import net.caffeinemc.mods.sodium.client.render.chunk.map.ChunkTrackerHolder;
1818
import net.caffeinemc.mods.sodium.client.render.chunk.terrain.DefaultTerrainRenderPasses;
19+
import net.caffeinemc.mods.sodium.client.render.chunk.translucent_sorting.trigger.CameraMovement;
1920
import net.caffeinemc.mods.sodium.client.render.viewport.Viewport;
2021
import net.caffeinemc.mods.sodium.client.util.NativeBuffer;
2122
import net.caffeinemc.mods.sodium.client.world.LevelRendererExtension;
@@ -42,6 +43,8 @@
4243
import java.util.Iterator;
4344
import java.util.SortedSet;
4445

46+
import org.joml.Vector3d;
47+
4548
/**
4649
* Provides an extension to vanilla's {@link LevelRenderer}.
4750
*/
@@ -51,7 +54,7 @@ public class SodiumWorldRenderer {
5154
private ClientLevel level;
5255
private int renderDistance;
5356

54-
private double lastCameraX, lastCameraY, lastCameraZ;
57+
private Vector3d lastCameraPos;
5558
private double lastCameraPitch, lastCameraYaw;
5659
private float lastFogDistance;
5760

@@ -174,44 +177,50 @@ public void setupTerrain(Camera camera,
174177
throw new IllegalStateException("Client instance has no active player entity");
175178
}
176179

177-
Vec3 pos = camera.getPosition();
180+
Vec3 posRaw = camera.getPosition();
181+
Vector3d pos = new Vector3d(posRaw.x(), posRaw.y(), posRaw.z());
178182
float pitch = camera.getXRot();
179183
float yaw = camera.getYRot();
180184
float fogDistance = RenderSystem.getShaderFogEnd();
181185

182-
boolean dirty = pos.x != this.lastCameraX || pos.y != this.lastCameraY || pos.z != this.lastCameraZ ||
183-
pitch != this.lastCameraPitch || yaw != this.lastCameraYaw || fogDistance != this.lastFogDistance;
184-
185-
if (dirty) {
186-
this.renderSectionManager.markGraphDirty();
186+
if (this.lastCameraPos == null) {
187+
this.lastCameraPos = new Vector3d(pos);
187188
}
189+
boolean cameraLocationChanged = !pos.equals(this.lastCameraPos);
190+
boolean cameraAngleChanged = pitch != this.lastCameraPitch || yaw != this.lastCameraYaw || fogDistance != this.lastFogDistance;
188191

189-
this.lastCameraX = pos.x;
190-
this.lastCameraY = pos.y;
191-
this.lastCameraZ = pos.z;
192192
this.lastCameraPitch = pitch;
193193
this.lastCameraYaw = yaw;
194-
this.lastFogDistance = fogDistance;
195194

196-
profiler.popPush("chunk_update");
195+
if (cameraLocationChanged || cameraAngleChanged) {
196+
this.renderSectionManager.markGraphDirty();
197+
}
197198

198-
this.renderSectionManager.updateChunks(updateChunksImmediately);
199+
this.lastFogDistance = fogDistance;
199200

200-
profiler.popPush("chunk_upload");
201+
this.renderSectionManager.updateCameraState(pos, camera);
201202

202-
this.renderSectionManager.uploadChunks();
203+
if (cameraLocationChanged) {
204+
profiler.popPush("translucent_triggering");
205+
206+
this.renderSectionManager.processGFNIMovement(new CameraMovement(this.lastCameraPos, pos));
207+
this.lastCameraPos = new Vector3d(pos);
208+
}
203209

204210
if (this.renderSectionManager.needsUpdate()) {
205211
profiler.popPush("chunk_render_lists");
206212

207213
this.renderSectionManager.update(camera, viewport, frame, spectator);
208214
}
209215

210-
if (updateChunksImmediately) {
211-
profiler.popPush("chunk_upload_immediately");
216+
profiler.popPush("chunk_update");
212217

213-
this.renderSectionManager.uploadChunks();
214-
}
218+
this.renderSectionManager.cleanupAndFlip();
219+
this.renderSectionManager.updateChunks(updateChunksImmediately);
220+
221+
profiler.popPush("chunk_upload");
222+
223+
this.renderSectionManager.uploadChunks();
215224

216225
profiler.popPush("chunk_render_tick");
217226

0 commit comments

Comments
 (0)