/
blocks.go
171 lines (136 loc) · 4.2 KB
/
blocks.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
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
package rasterize
import (
"github.com/RH12503/Triangula/geom"
"math"
)
// DDATriangleBlocks calls function line for each line a triangle covers, and
// calls function block for each block the triangle covers.
func DDATriangleBlocks(triangle geom.Triangle, blockSize int, line func(x0, x1, y int), block func(x, y int)) {
p0 := triangle.Points[0]
p1 := triangle.Points[1]
p2 := triangle.Points[2]
// Sort vertices by y value, where y0 has the lowest value
x0, y0 := p0.X, p0.Y
x1, y1 := p1.X, p1.Y
x2, y2 := p2.X, p2.Y
if y1 > y0 {
x0, x1 = x1, x0
y0, y1 = y1, y0
}
if y2 > y1 {
x1, x2 = x2, x1
y1, y2 = y2, y1
if y1 > y0 {
x0, x1 = x1, x0
y0, y1 = y1, y0
}
}
normalTriangleBlocks(x0, y0, x1, y1, x2, y2, blockSize, line, block)
}
// normalTriangleBlocks rasterizes the lines of a triangle, while trying to rasterize in blocks when possible.
func normalTriangleBlocks(x0, y0, x1, y1, x2, y2 int, blockSize int, line func(x0, x1, y int), block func(x, y int)) {
// Calculate the slopes of the first two lines
m0 := float64(x2-x0) / float64(y2-y0)
m1 := float64(x2-x1) / float64(y2-y1)
// Swap the slopes so m0 is the slope of the left line and m1 is the slope of the right line
swap := m0 > m1
if swap {
m0, m1 = m1, m0
}
// Start from the top vertex
lX0 := float64(x2)
lX1 := float64(x2)
// Starting from the bottom y coordinate, iterate upwards through the pixels using incrementing by blockSize
i := y1 - 1
for ; i > y2; i -= blockSize {
top := i - blockSize + 1
bottomX := m0*float64(i-y2) + lX0
topX := m0*float64((top)-y2) + lX0
maxX := math.Max(bottomX, topX)
bottomX = m1*float64(i-y2) + lX1
topX = m1*float64((top)-y2) + lX1
minX := math.Min(bottomX, topX)
// Leave the loop if the remaining triangle isn't wide enough to rasterize blocks
if float64(int(maxX)+blockSize) >= minX {
break
}
// Fill in the left section of the triangle where blocks can't be rasterized
for y := 0; y < blockSize; y++ {
pX0 := m0*float64((i-y)-y2) + lX0
line(int(pX0), int(maxX), i-y)
}
// Rasterize the middle section of the triangle in blocks
x := int(maxX)
for ; float64(x+blockSize) < minX; x += blockSize {
block(x, i-blockSize+1)
}
// Fill in the right section of the triangle where blocks can't be rasterized
for y := 0; y < blockSize; y++ {
pX1 := m1*float64((i-y)-y2) + lX1
line(x, int(pX1), i-y)
}
}
// Rasterize the remaining part of the top triangle with pixels
for ; i > y2; i-- {
pX0 := m0*float64(i-y2) + lX0
pX1 := m1*float64(i-y2) + lX1
line(int(pX0), int(pX1), i)
}
// Calculate the new slope for the line that changed, and repeat the process above
var d0, d1 int
if swap {
m0 = float64(x1-x0) / float64(y1-y0)
lX0 = float64(x1)
d1 = y1 - y2
} else {
m1 = float64(x1-x0) / float64(y1-y0)
lX1 = float64(x1)
d0 = y1 - y2
}
if y1 == y2 {
lX0 = float64(x2)
lX1 = float64(x1)
if lX0 > lX1 {
lX0, lX1 = lX1, lX0
}
if m0 < m1 {
m0, m1 = m1, m0
}
}
i = y1
// Starting from the top y coordinate, iterate downwards through the pixels using incrementing by blockSize
for ; i+blockSize < y0; i += blockSize {
top := i + blockSize - 1
bottomX := m0*float64(i-y1+d0) + lX0
topX := m0*float64(top-y1+d0) + lX0
maxX := math.Max(bottomX, topX)
bottomX = m1*float64(i-y1+d1) + lX1
topX = m1*float64(top-y1+d1) + lX1
minX := math.Min(bottomX, topX)
// Leave the loop if the remaining triangle isn't wide enough to rasterize blocks
if float64(int(maxX)+blockSize) >= minX {
break
}
// Fill in the right section of the triangle where blocks can't be rasterized
for y := 0; y < blockSize; y++ {
pX0 := m0*float64((i+y)-y1+d0) + lX0
line(int(pX0), int(maxX), i+y)
}
// Rasterize the middle section of the triangle in blocks
x := int(maxX)
for ; float64(x+blockSize) < minX; x += blockSize {
block(x, i)
}
// Fill in the right section of the triangle where blocks can't be rasterized
for y := 0; y < blockSize; y++ {
pX1 := m1*float64((i+y)-y1+d1) + lX1
line(x, int(pX1), i+y)
}
}
// Rasterize the remaining part of the bottom triangle with pixels
for ; i < y0; i++ {
pX0 := m0*float64(i-y1+d0) + lX0
pX1 := m1*float64(i-y1+d1) + lX1
line(int(pX0), int(pX1), i)
}
}