Optimism in Design
Filter mode:
Topics
Media
data structure
geometry
language
meshing
performance
(null topic)
🗫Presentation🟉
Credits
?
?
W, K, P / S, J, N Jump to previous / next timestamp
t / T Toggle theatre / SUPERtheatre mode
V Revert filter to original state Y Select link (requires manual Ctrl-c)
X, ShiftSpace Toggle category and focus previous
v Invert topics / media as per focus
Keyboard Navigation
Global Keys
[, < / ], > Jump to previous / next episodeW, K, P / S, J, N Jump to previous / next timestamp
t / T Toggle theatre / SUPERtheatre mode
V Revert filter to original state Y Select link (requires manual Ctrl-c)
Menu toggling
q Quotes r References f Filter y Link c CreditsIn-Menu and Index Controls
a
w
s
s
d
h
j
k
l
←
↑
↓
↓
→
Esc Close menu / unfocus timestamp
Quotes and References Menus and Index
Enter Jump to timestampQuotes, References and Credits Menus
o Open URL (in new tab)Filter Menu
x, Space Toggle category and focus nextX, ShiftSpace Toggle category and focus previous
v Invert topics / media as per focus
Filter and Link Menus
z Toggle filter / linking modeCredits Menu
Enter Open URL (in new tab)⏫
Previous: ‘LibQuincy’
⏫
0:00: Welcome Davis
0:00: Welcome Davis
0:00: Welcome Davis
0:36: Clarification: Covering a rasterised version of voxel engines
0:36: Clarification: Covering a rasterised version of voxel engines
0:36: Clarification: Covering a rasterised version of voxel engines
0:50: Optimism in Design: A Talk About Voxels
0:50: Optimism in Design: A Talk About Voxels
0:50: Optimism in Design: A Talk About Voxels
0:54: Let's create a voxel engine
0:54: Let's create a voxel engine
0:54: Let's create a voxel engine
1:01: Well, what even is a voxel?
1:01: Well, what even is a voxel?
1:01: Well, what even is a voxel?
1:14: A Point in a 3D Grid
1:14: A Point in a 3D Grid
1:14: A Point in a 3D Grid
1:25: What space does our grid exist in?
1:25: What space does our grid exist in?
1:25: What space does our grid exist in?
1:37: What data should our voxel have?
1:37: What data should our voxel have?
1:37: What data should our voxel have?
1:47: What kinds of voxels do we want to start with?
1:47: What kinds of voxels do we want to start with?
1:47: What kinds of voxels do we want to start with?
2:01: Next, let's assign IDs
2:01: Next, let's assign IDs
2:01: Next, let's assign IDs
2:14: What does our voxel look like in memory?
2:14: What does our voxel look like in memory?
2:14: What does our voxel look like in memory?
2:21: A voxel with its type in a 3D grid
2:21: A voxel with its type in a 3D grid
2:21: A voxel with its type in a 3D grid
2:27: What is our volume? What kind of world do we want to have?
2:27: What is our volume? What kind of world do we want to have?
2:27: What is our volume? What kind of world do we want to have?
2:35: Instead of having one massive world…
2:35: Instead of having one massive world…
2:35: Instead of having one massive world…
2:50: …we can break it up into smaller chunks
2:50: …we can break it up into smaller chunks
2:50: …we can break it up into smaller chunks
3:01: Now we can be focused in how we update things
3:01: Now we can be focused in how we update things
3:01: Now we can be focused in how we update things
3:10: But what size should these smaller chunks be? It's a balancing act
3:10: But what size should these smaller chunks be? It's a balancing act
3:10: But what size should these smaller chunks be? It's a balancing act
3:24: For convenience later, let's go with a size of 64
3:24: For convenience later, let's go with a size of 64
3:24: For convenience later, let's go with a size of 64
3:43: Now our world is made up of 64³ chunks
3:43: Now our world is made up of 64³ chunks
3:43: Now our world is made up of 64³ chunks
3:49: What does our chunk look like in memory?
3:49: What does our chunk look like in memory?
3:49: What does our chunk look like in memory?
4:14: How to compose a 3D position into a single digit?
4:14: How to compose a 3D position into a single digit?
4:14: How to compose a 3D position into a single digit?
4:17: 3D Position to a Single Index: x
4:17: 3D Position to a Single Index: x
4:17: 3D Position to a Single Index: x
4:44: 3D Position to a Single Index: x, z
4:44: 3D Position to a Single Index: x, z
4:44: 3D Position to a Single Index: x, z
5:30: 3D Position to a Single Index: x, y, z
5:30: 3D Position to a Single Index: x, y, z
5:30: 3D Position to a Single Index: x, y, z
5:45: 3D Position to a Single Index: Completed Formula
5:45: 3D Position to a Single Index: Completed Formula
5:45: 3D Position to a Single Index: Completed Formula
5:59: Index Back to 3D Position
5:59: Index Back to 3D Position
5:59: Index Back to 3D Position
6:40: Now we can define what our chunk looks like in memory
6:40: Now we can define what our chunk looks like in memory
6:40: Now we can define what our chunk looks like in memory
6:53: What about our world?
6:53: What about our world?
6:53: What about our world?
7:21: Now that we have everything in memory, how do we get it all on the screen?
7:21: Now that we have everything in memory, how do we get it all on the screen?
7:21: Now that we have everything in memory, how do we get it all on the screen?
7:30: Let's start with a single voxel
7:30: Let's start with a single voxel
7:30: Let's start with a single voxel
7:37: How is a voxel going to be represented in our world?
7:37: How is a voxel going to be represented in our world?
7:37: How is a voxel going to be represented in our world?
7:45: Let's say our voxel is geometrically a cube. How can we draw it?
7:45: Let's say our voxel is geometrically a cube. How can we draw it?
7:45: Let's say our voxel is geometrically a cube. How can we draw it?
7:51: How can we draw a voxel?
7:51: How can we draw a voxel?
7:51: How can we draw a voxel?
8:13: What is our vertex made of?
8:13: What is our vertex made of?
8:13: What is our vertex made of?
8:48: Now, we can draw our cube
8:48: Now, we can draw our cube
8:48: Now, we can draw our cube
8:54: How do we do this for the entire world?
8:54: How do we do this for the entire world?
8:54: How do we do this for the entire world?
8:57: Wait, that's overkill
8:57: Wait, that's overkill
8:57: Wait, that's overkill
9:16: Naively extracting a mesh, or Naive Meshing
9:16: Naively extracting a mesh, or Naive Meshing
9:16: Naively extracting a mesh, or Naive Meshing
9:39: Next, let's do this for every voxel in our chunk
9:39: Next, let's do this for every voxel in our chunk
9:39: Next, let's do this for every voxel in our chunk
9:59: Great, so now we're done, right?
9:59: Great, so now we're done, right?
9:59: Great, so now we're done, right?
10:08: It's kind of slow
10:08: It's kind of slow
10:08: It's kind of slow
10:37: We can do better, with Greedy Meshing
10:37: We can do better, with Greedy Meshing
10:37: We can do better, with Greedy Meshing
10:41: What is Greedy Meshing?
10:41: What is Greedy Meshing?
10:41: What is Greedy Meshing?
10:50: How are we able to join faces?
10:50: How are we able to join faces?
10:50: How are we able to join faces?
11:17: That's great, but how does it actually work?
11:17: That's great, but how does it actually work?
11:17: That's great, but how does it actually work?
11:21: Let's take a 2D slice of our world
11:21: Let's take a 2D slice of our world
11:21: Let's take a 2D slice of our world
11:28: To start, we can focus on those sand blocks
11:28: To start, we can focus on those sand blocks
11:28: To start, we can focus on those sand blocks
11:32: Then, we'll start at the bottom left voxel
11:32: Then, we'll start at the bottom left voxel
11:32: Then, we'll start at the bottom left voxel
11:38: At first, we try to grow vertically
11:38: At first, we try to grow vertically
11:38: At first, we try to grow vertically
12:05: Since we can't grow vertically anymore, let's grow horizontally
12:05: Since we can't grow vertically anymore, let's grow horizontally
12:05: Since we can't grow vertically anymore, let's grow horizontally
12:30: Let's apply this algorithm to the rest of our scene
12:30: Let's apply this algorithm to the rest of our scene
12:30: Let's apply this algorithm to the rest of our scene
12:34: Nice! That's a significant reduction in faces
12:34: Nice! That's a significant reduction in faces
12:34: Nice! That's a significant reduction in faces
12:57: Can we do better?
12:57: Can we do better?
12:57: Can we do better?
13:19: What are we currently limited by?
13:19: What are we currently limited by?
13:19: What are we currently limited by?
13:37: What makes up our Vertex?
13:37: What makes up our Vertex?
13:37: What makes up our Vertex?
13:59: Instead, we can upload the type buffer directly to the GPU
13:59: Instead, we can upload the type buffer directly to the GPU
13:59: Instead, we can upload the type buffer directly to the GPU
14:29: We aren't getting rid of any data, we're just moving it around
14:29: We aren't getting rid of any data, we're just moving it around
14:29: We aren't getting rid of any data, we're just moving it around
14:40: Where does this leave us?
14:40: Where does this leave us?
14:40: Where does this leave us?
14:43: Now instead of having to only mesh similar types…
14:43: Now instead of having to only mesh similar types…
14:43: Now instead of having to only mesh similar types…
14:48: …it's become a binary problem!
14:48: …it's become a binary problem!
14:48: …it's become a binary problem!
14:58: We can now mesh all faces without discrimination
14:58: We can now mesh all faces without discrimination
14:58: We can now mesh all faces without discrimination
15:29: Okay, do we still have to work with IDs?
15:29: Okay, do we still have to work with IDs?
15:29: Okay, do we still have to work with IDs?
15:33: It's a binary problem, so we only need a binary representation of our scene
15:33: It's a binary problem, so we only need a binary representation of our scene
15:33: It's a binary problem, so we only need a binary representation of our scene
15:48: Right now, our chunk is a 3D grid of voxel structs stored in an array
15:48: Right now, our chunk is a 3D grid of voxel structs stored in an array
15:48: Right now, our chunk is a 3D grid of voxel structs stored in an array
16:01: What we can use as a binary representation of our voxel data is an array of bits
16:01: What we can use as a binary representation of our voxel data is an array of bits
16:01: What we can use as a binary representation of our voxel data is an array of bits
16:14: Let's make a bit array
16:14: Let's make a bit array
16:14: Let's make a bit array
16:17: Let's make a bit array: First, we take our current index formula and chop off the Y
16:17: Let's make a bit array: First, we take our current index formula and chop off the Y
16:17: Let's make a bit array: First, we take our current index formula and chop off the Y
16:22: Let's make a bit array: That index can then access a column in an array of unsigned 64-bit integers
16:22: Let's make a bit array: That index can then access a column in an array of unsigned 64-bit integers
16:22: Let's make a bit array: That index can then access a column in an array of unsigned 64-bit integers
16:26: Let's make a bit array: And then Y can be used to index into a voxel at a specific height in this column
16:26: Let's make a bit array: And then Y can be used to index into a voxel at a specific height in this column
16:26: Let's make a bit array: And then Y can be used to index into a voxel at a specific height in this column
16:49: So now that we can, let's turn our scene into binary
16:49: So now that we can, let's turn our scene into binary
16:49: So now that we can, let's turn our scene into binary
16:57: All set voxels become ones, and all air voxels become zeros
16:57: All set voxels become ones, and all air voxels become zeros
16:57: All set voxels become ones, and all air voxels become zeros
17:10: Before we combine our faces, what are 64-bit integers perfect for?
17:10: Before we combine our faces, what are 64-bit integers perfect for?
17:10: Before we combine our faces, what are 64-bit integers perfect for?
17:15: Bitwise Operations!
17:15: Bitwise Operations!
17:15: Bitwise Operations!
17:20: Bitwise ANDs
17:20: Bitwise ANDs
17:20: Bitwise ANDs
17:37: Considering 64 voxels at once with bitwise AND Meshing
17:37: Considering 64 voxels at once with bitwise AND Meshing
17:37: Considering 64 voxels at once with bitwise AND Meshing
18:26: We've significantly reduced the amount of operations too!
18:26: We've significantly reduced the amount of operations too!
18:26: We've significantly reduced the amount of operations too!
18:58: Alright, but there is a property of voxel worlds that we're ignoring
18:58: Alright, but there is a property of voxel worlds that we're ignoring
18:58: Alright, but there is a property of voxel worlds that we're ignoring
19:02: They often have a more complicated 3D scene
19:02: They often have a more complicated 3D scene
19:02: They often have a more complicated 3D scene
19:17: If we take that scene and turn it into bits…
19:17: If we take that scene and turn it into bits…
19:17: If we take that scene and turn it into bits…
19:20: …we see we need to take that bitwise AND idea and make it work with "3D" columns
19:20: …we see we need to take that bitwise AND idea and make it work with "3D" columns
19:20: …we see we need to take that bitwise AND idea and make it work with "3D" columns
19:34: We can do that by breaking down the problem into smaller parts
19:34: We can do that by breaking down the problem into smaller parts
19:34: We can do that by breaking down the problem into smaller parts
19:43: How can we extract the first two set bits here?
19:43: How can we extract the first two set bits here?
19:43: How can we extract the first two set bits here?
19:51: We can use something that 64-bit integers are also great for: intrinsics, specifically one called Trailing Zero Count
19:51: We can use something that 64-bit integers are also great for: intrinsics, specifically one called Trailing Zero Count
19:51: We can use something that 64-bit integers are also great for: intrinsics, specifically one called Trailing Zero Count
20:01: To start, we take the first column and invert it
20:01: To start, we take the first column and invert it
20:01: To start, we take the first column and invert it
20:06: Then we count the first series of zeros, which is our first set bits inverted
20:06: Then we count the first series of zeros, which is our first set bits inverted
20:06: Then we count the first series of zeros, which is our first set bits inverted
20:13: Now we can create a new mask
20:13: Now we can create a new mask
20:13: Now we can create a new mask
20:17: We can then use this mask to compare the rest of our columns
20:17: We can then use this mask to compare the rest of our columns
20:17: We can then use this mask to compare the rest of our columns
20:31: We then skip the zeros to get to the next column, and repeat the extraction process
20:31: We then skip the zeros to get to the next column, and repeat the extraction process
20:31: We then skip the zeros to get to the next column, and repeat the extraction process
20:55: Then, we mesh again using this new mask
20:55: Then, we mesh again using this new mask
20:55: Then, we mesh again using this new mask
21:02: We repeat this process for our entire chunk
21:02: We repeat this process for our entire chunk
21:02: We repeat this process for our entire chunk
21:10: We now have our more complicated scene, meshed binarily, using bitwise operations and intrinsics
21:10: We now have our more complicated scene, meshed binarily, using bitwise operations and intrinsics
21:10: We now have our more complicated scene, meshed binarily, using bitwise operations and intrinsics
21:20: Let's Talk About Speed
21:20: Let's Talk About Speed
21:20: Let's Talk About Speed
21:23: Old Greedy Meshing times (3–5ms) vs Now (0.12ms) for 64³ area
21:23: Old Greedy Meshing times (3–5ms) vs Now (0.12ms) for 64³ area
21:23: Old Greedy Meshing times (3–5ms) vs Now (0.12ms) for 64³ area
22:25: But we could be faster
22:25: But we could be faster
22:25: But we could be faster
22:28: Simple Thread Queue: on i7 8700k 0.01ms per 64³ chunk on average
22:28: Simple Thread Queue: on i7 8700k 0.01ms per 64³ chunk on average
22:28: Simple Thread Queue: on i7 8700k 0.01ms per 64³ chunk on average
24:02: Old Greedy Meshing times (3–5ms) vs Now (0.01ms) for 64³ area
24:02: Old Greedy Meshing times (3–5ms) vs Now (0.01ms) for 64³ area
24:02: Old Greedy Meshing times (3–5ms) vs Now (0.01ms) for 64³ area
24:12: But we could be even faster
24:12: But we could be even faster
24:12: But we could be even faster
24:16: If we think about it, what are we really doing with our meshing?
24:16: If we think about it, what are we really doing with our meshing?
24:16: If we think about it, what are we really doing with our meshing?
24:35: We could just use one face to represent all possible faces for any slice of voxels
24:35: We could just use one face to represent all possible faces for any slice of voxels
24:35: We could just use one face to represent all possible faces for any slice of voxels
25:12: Let's do this for an entire chunk
25:12: Let's do this for an entire chunk
25:12: Let's do this for an entire chunk
25:38: Let's use this for the entire world!
25:38: Let's use this for the entire world!
25:38: Let's use this for the entire world!
25:46: Global Lattice Stats
25:46: Global Lattice Stats
25:46: Global Lattice Stats
27:16: What does not having to mesh mean?
27:16: What does not having to mesh mean?
27:16: What does not having to mesh mean?
28:35: Statistics
28:35: Statistics
28:35: Statistics
28:58: Let's solve some problems with the Global Lattice
28:58: Let's solve some problems with the Global Lattice
28:58: Let's solve some problems with the Global Lattice
29:04: Global Lattice examples: 1) A Solution for Floating Point Precision, "The Treadmill"
29:04: Global Lattice examples: 1) A Solution for Floating Point Precision, "The Treadmill"
29:04: Global Lattice examples: 1) A Solution for Floating Point Precision, "The Treadmill"
30:14: Global Lattice examples: 1) A Solution for Floating Point Precision, "The Treadmill" illustration
30:14: Global Lattice examples: 1) A Solution for Floating Point Precision, "The Treadmill" illustration
30:14: Global Lattice examples: 1) A Solution for Floating Point Precision, "The Treadmill" illustration
30:48: Global Lattice examples: 2) Maximizing What's in View With Frustum Rotation
30:48: Global Lattice examples: 2) Maximizing What's in View With Frustum Rotation
30:48: Global Lattice examples: 2) Maximizing What's in View With Frustum Rotation
30:53: Global Lattice examples: 2) Frustum Rotation
30:53: Global Lattice examples: 2) Frustum Rotation
30:53: Global Lattice examples: 2) Frustum Rotation
31:39: Global Lattice examples: 2) Frustum Rotation with a lower FOV
31:39: Global Lattice examples: 2) Frustum Rotation with a lower FOV
31:39: Global Lattice examples: 2) Frustum Rotation with a lower FOV
32:03: In Conclusion
32:03: In Conclusion
32:03: In Conclusion
33:46: Thanks1
33:46: Thanks1
33:46: Thanks1
⏬
Next: ‘Optimism in Design – Q&A;’
⏬