Fix a bug with run slice bresenham when dx >= dy

author: Bad Diode <bd@badd10de.dev> 2023-04-17 16:01:02 +0200
committer: Bad Diode <bd@badd10de.dev> 2023-04-17 16:01:02 +0200
commit: 547d1c6bacb43fe14c285f8ae8d96a16e933ae3c (patch)
tree: 164fe151da9900830ac0d334cf947429f07229e3
parent: cb73b66dc43672f18c0fcf75ab1e20691673ba05 (diff)
download: gba-renderers-547d1c6bacb43fe14c285f8ae8d96a16e933ae3c.tar.gz
gba-renderers-547d1c6bacb43fe14c285f8ae8d96a16e933ae3c.zip
2 files changed, 170 insertions, 55 deletions
diff --git a/src/main.c b/src/main.c
index aee8f56..2697b3c 100644
--- a/src/main.c
+++ b/src/main.c
@@ -126,19 +126,44 @@ int main(void) {
        bios_vblank_wait();
        PROF(test_clear(), test_clear_cycles);
+        // screen_fill(0);
+        // DX is bigger
+        // left -> right && top -> bot
+        //draw_line(0, 0, 239, 159, 1);
+        //// draw_line(10, 0, 229, 159, 1);
+        //// left -> right && bot -> top
+        //draw_line(0, 159, 239, 0, 2);
+        //// draw_line(10, 159, 229, 0, 2);
+        ////
+        //draw_line(0, 0, 239, 159, 1);
+        //draw_line(0, 129, 239, 40, 2);
+        //// right -> left && top -> bot
+        //draw_line(239, 81, 0, 129, 3);
+        //// right -> left && bot -> top
+        //draw_line(239, 129, 0, 40, 5);
+            // txt_render();
+            // txt_clear();
+        // draw_line(239, 149, 0, 10, 3);
+        // draw_line(0, 159, 239, 0, 2);
        // draw_line(0, 0, 100, 50, 2);
        // draw_line(0, 0, 100, 21, 5);
        // draw_line(0, 0, 15, 7, 2);
        // draw_line(0, 31, 100, 0, 5);
+        // draw_line(0, 159, 19, 0, 5);
+        // draw_line(0, 159, 19, 0, 5);
+        // draw_line(0, 0, 19, 159, 6);
        // txt_render();
        // txt_clear();
        PROF(test_lines(), test_lines_cycles);
-        PROF(test_rect(), test_rect_cycles);
+        // PROF(test_rect(), test_rect_cycles);
-        PROF(test_fill_rect(), test_fill_rect_cycles);
+        // PROF(test_fill_rect(), test_fill_rect_cycles);
-        PROF(test_chr(), test_chr_cycles);
+        // PROF(test_chr(), test_chr_cycles);
-        PROF(test_icn(), test_icn_cycles);
+        // PROF(test_icn(), test_icn_cycles);
-        draw_filled_rect(0, 0, 140, 60, 0);
+        // draw_filled_rect(0, 0, 140, 60, 0);
-        PROF_SHOW();
+        // PROF_SHOW();
        PROF(flip_buffer(), flip_cycles);
    }
diff --git a/src/renderer_m0.c b/src/renderer_m0.c
index 02f1e31..2548fea 100644
--- a/src/renderer_m0.c
+++ b/src/renderer_m0.c
@@ -179,72 +179,162 @@ draw_line(size_t x0, size_t y0, size_t x1, size_t y1, u8 clr) {
        draw_vline(x0, y0, y1, clr);
    } else {
 #if 1
-        // NOTE: WIP run slice bresenham
        int fp_bit = 6;
        int fp_one = FP_NUM(1, fp_bit);
        int fp_half = fp_one >> 1;
        int dx     = x0 > x1 ? x0 - x1 : x1 - x0;
        int dy     = y0 > y1 ? y0 - y1 : y1 - y0;
+        if (dx >= dy && x0 > x1) {
+            SWAP(x0, x1);
+            SWAP(y0, y1);
+        }
        int frac_x = x0 > x1 ? FP_NUM(x0 - x1, fp_bit) : FP_NUM(x1 - x0, fp_bit);
        int frac_y = y0 > y1 ? FP_NUM(y0 - y1, fp_bit) : FP_NUM(y1 - y0, fp_bit);
        int x_step = x0 > x1 ? -1 : 1;
        int y_step = y0 > y1 ? -1 : 1;
        int dxf = (dx << fp_bit);
        int dyf = (dy << fp_bit);
+        int distance = (frac_y - fp_one) * dx - (frac_x - fp_half) * dy;
        if (dx >= dy) {
-            int step = dx / dy;
+            int xp = x0;
-            if (step == 1) {
+            int yp = y0;
-                // If the line is mostly diagonal, default to regular bresengham.
-                int distance = (frac_y - fp_one) * dx - (frac_x - fp_half) * dy;
+            //
-                for (int i = 0; i <= dx; i++) {
+            // NOTE: REFERENCE
-                    if (distance >= 0) {
+            // for (int i = 0; i <= dx; i++) {
-                        distance -= 2 * dxf;
+            //     if (distance >= 0) {
-                        y0 += y_step;
+            //         distance -= 2 * dxf;
-                    }
+            //         yp += y_step;
-                    draw_pixel(x0, y0, clr);
+            //     }
-                    distance += 2 * dyf;
+            //     draw_pixel(xp, yp, clr);
-                    x0 += x_step;
+            //     distance += 2 * dyf;
-                }
+            //     xp += x_step;
-            } else {
+            // }
-                int distance = (frac_y - fp_one) * dx - (frac_x - fp_half) * dy;
+            // int step = dxf / dyf;
-                int remaining = dx;
+            //
-                while (remaining > (step - 1)) {
+            int step = dx;
-                    distance += step * 2 * dyf;
+            if (dy > 0) {
-                    if (distance >= 0) {
+                step = dx / dy;
-                        draw_hline(x0, x0 + step - 1, y0, clr);
+            }
-                        x0 += x_step * (step + 0);
+            int remaining = dx;
-                        remaining -= step;
+            int big_step = step;
-                    } else {
+            int small_step = step - 1;
-                        draw_hline(x0, x0 + step, y0, clr);
+            while (remaining > small_step) {
-                        distance += 2 * dyf;
+                distance += step * 2 * dyf;
-                        x0 += x_step * (step + 1);
+                if (distance >= 0) {
-                        remaining -= step + 1;
+                    draw_hline(xp, xp + small_step, yp, clr);
-                    }
+                    xp += x_step * step;
-                    distance -= 2 * dxf;
+                    remaining -= step;
-                    y0 += y_step;
+                } else {
-                }
+                    if (remaining < big_step) {
-                // Default to regular bresengham for the final segment.
+                        break;
-                for (int i = 0; i <= remaining; i++) {
-                    if (distance >= 0) {
-                        distance -= 2 * dxf;
-                        y0 += y_step;
                    }
-                    draw_pixel(x0, y0, clr);
+                    draw_hline(xp, xp + big_step, yp, clr);
                    distance += 2 * dyf;
-                    x0 += x_step;
+                    xp += x_step * (step + 1);
+                    remaining -= step + 1;
                }
+                distance -= 2 * dxf;
+                yp += y_step;
            }
-        } else {
+            if (remaining >= 0) {
-            int distance = (frac_x - fp_one) * dy - (frac_y - fp_half) * dx;
+                draw_hline(xp, xp + remaining, yp, clr);
-            for (int i = 0; i <= dy; i++) {
-                draw_pixel(x0, y0, clr);
-                if (distance >= 0) {
-                    distance -= 2 * dyf;
-                    x0 += x_step;
-                }
-                distance += 2 * dxf;
-                y0 += y_step;
            }
+            // for (int i = 0; i <= remaining; i++) {
+            //     if (distance >= 0) {
+            //         distance -= 2 * dxf;
+            //         y0 += y_step;
+            //     }
+            //     draw_pixel(xp, yp, clr);
+            //     distance += 2 * dyf;
+            //     xp += x_step;
+            // }
+            // txt_printf("steps: %d\n", step);
+            // if (step == 1) {
+            //     // If the line is mostly diagonal, default to regular Bresenham.
+            //     for (int i = 0; i <= dx; i++) {
+            //         if (distance >= 0) {
+            //             distance -= 2 * dxf;
+            //             y0 += y_step;
+            //         }
+            //         draw_pixel(x0, y0, clr);
+            //         distance += 2 * dyf;
+            //         x0 += x_step;
+            //     }
+            // } else {
+            //     // Run slice Bresenham.
+            //     int remaining = dx;
+            //     while (remaining > (step - 1)) {
+            //         distance += step * 2 * dyf;
+            //         if (distance >= 0) {
+            //             draw_hline(x0, x0 + step - 1, y0, clr);
+            //             x0 += x_step * (step + 0);
+            //             remaining -= step;
+            //         } else {
+            //             draw_hline(x0, x0 + step, y0, clr);
+            //             distance += 2 * dyf;
+            //             x0 += x_step * (step + 1);
+            //             remaining -= step + 1;
+            //         }
+            //         distance -= 2 * dxf;
+            //         y0 += y_step;
+            //     }
+            //     // Default to regular Bresenham for the final segment.
+            //     for (int i = 0; i <= remaining; i++) {
+            //         if (distance >= 0) {
+            //             distance -= 2 * dxf;
+            //             y0 += y_step;
+            //         }
+            //         draw_pixel(x0, y0, clr);
+            //         distance += 2 * dyf;
+            //         x0 += x_step;
+            //     }
+            // }
+        } else {
+            // int step = dy / dx;
+            // int distance = (frac_x - fp_one) * dy - (frac_y - fp_half) * dx;
+            // if (step == 1) {
+            //     for (int i = 0; i <= dy; i++) {
+            //         draw_pixel(x0, y0, clr);
+            //         if (distance >= 0) {
+            //             distance -= 2 * dyf;
+            //             x0 += x_step;
+            //         }
+            //         distance += 2 * dxf;
+            //         y0 += y_step;
+            //     }
+            // } else {
+            //     // Run slice Bresenham.
+            //     int remaining = dy;
+            //     while (remaining > (step)) {
+            //         distance += step * 2 * dxf;
+            //         if (distance >= 0) {
+            //             draw_vline(x0, y0, y0 + step, 2);
+            //             y0 += y_step * (step + 0);
+            //             remaining -= step;
+            //         } else {
+            //             draw_vline(x0, y0, y0 + step + 1, 3);
+            //             distance += 2 * dxf;
+            //             y0 += y_step * (step + 1);
+            //             remaining -= step + 1;
+            //         }
+            //         distance -= 2 * dyf;
+            //         x0 += x_step;
+            //     }
+            //     // Default to regular Bresenham for the final segment.
+            //     for (int i = 0; i <= dy; i++) {
+            //         draw_pixel(x0, y0, 6);
+            //         if (distance >= 0) {
+            //             distance -= 2 * dyf;
+            //             x0 += x_step;
+            //         }
+            //         distance += 2 * dxf;
+            //         y0 += y_step;
+            //     }
+            // }
        }
 #elif 0
        int fp_bit = 6;
author	Bad Diode <bd@badd10de.dev>	2023-04-17 16:01:02 +0200
committer	Bad Diode <bd@badd10de.dev>	2023-04-17 16:01:02 +0200
commit	547d1c6bacb43fe14c285f8ae8d96a16e933ae3c (patch)
tree	164fe151da9900830ac0d334cf947429f07229e3
parent	cb73b66dc43672f18c0fcf75ab1e20691673ba05 (diff)
download	gba-renderers-547d1c6bacb43fe14c285f8ae8d96a16e933ae3c.tar.gz gba-renderers-547d1c6bacb43fe14c285f8ae8d96a16e933ae3c.zip

diff --git a/src/main.c b/src/main.c index aee8f56..2697b3c 100644 --- a/src/main.c +++ b/src/main.c
@@ -126,19 +126,44 @@ int main(void) {
126	bios_vblank_wait();	126	bios_vblank_wait();
127		127
128	PROF(test_clear(), test_clear_cycles);	128	PROF(test_clear(), test_clear_cycles);
		129	// screen_fill(0);
		130
		131	// DX is bigger
		132	// left -> right && top -> bot
		133	//draw_line(0, 0, 239, 159, 1);
		134	//// draw_line(10, 0, 229, 159, 1);
		135	//// left -> right && bot -> top
		136	//draw_line(0, 159, 239, 0, 2);
		137	//// draw_line(10, 159, 229, 0, 2);
		138	////
		139	//draw_line(0, 0, 239, 159, 1);
		140	//draw_line(0, 129, 239, 40, 2);
		141	//// right -> left && top -> bot
		142	//draw_line(239, 81, 0, 129, 3);
		143	//// right -> left && bot -> top
		144	//draw_line(239, 129, 0, 40, 5);
		145	// txt_render();
		146	// txt_clear();
		147
		148	// draw_line(239, 149, 0, 10, 3);
		149
		150	// draw_line(0, 159, 239, 0, 2);
129	// draw_line(0, 0, 100, 50, 2);	151	// draw_line(0, 0, 100, 50, 2);
130	// draw_line(0, 0, 100, 21, 5);	152	// draw_line(0, 0, 100, 21, 5);
131	// draw_line(0, 0, 15, 7, 2);	153	// draw_line(0, 0, 15, 7, 2);
132	// draw_line(0, 31, 100, 0, 5);	154	// draw_line(0, 31, 100, 0, 5);
		155	// draw_line(0, 159, 19, 0, 5);
		156	// draw_line(0, 159, 19, 0, 5);
		157	// draw_line(0, 0, 19, 159, 6);
133	// txt_render();	158	// txt_render();
134	// txt_clear();	159	// txt_clear();
135	PROF(test_lines(), test_lines_cycles);	160	PROF(test_lines(), test_lines_cycles);
136	PROF(test_rect(), test_rect_cycles);	161	// PROF(test_rect(), test_rect_cycles);
137	PROF(test_fill_rect(), test_fill_rect_cycles);	162	// PROF(test_fill_rect(), test_fill_rect_cycles);
138	PROF(test_chr(), test_chr_cycles);	163	// PROF(test_chr(), test_chr_cycles);
139	PROF(test_icn(), test_icn_cycles);	164	// PROF(test_icn(), test_icn_cycles);
140	draw_filled_rect(0, 0, 140, 60, 0);	165	// draw_filled_rect(0, 0, 140, 60, 0);
141	PROF_SHOW();	166	// PROF_SHOW();
142	PROF(flip_buffer(), flip_cycles);	167	PROF(flip_buffer(), flip_cycles);
143	}	168	}
144		169


diff --git a/src/renderer_m0.c b/src/renderer_m0.c index 02f1e31..2548fea 100644 --- a/src/renderer_m0.c +++ b/src/renderer_m0.c
@@ -179,72 +179,162 @@ draw_line(size_t x0, size_t y0, size_t x1, size_t y1, u8 clr) {
179	draw_vline(x0, y0, y1, clr);	179	draw_vline(x0, y0, y1, clr);
180	} else {	180	} else {
181	#if 1	181	#if 1
182	// NOTE: WIP run slice bresenham
183	int fp_bit = 6;	182	int fp_bit = 6;
184	int fp_one = FP_NUM(1, fp_bit);	183	int fp_one = FP_NUM(1, fp_bit);
185	int fp_half = fp_one >> 1;	184	int fp_half = fp_one >> 1;
186	int dx = x0 > x1 ? x0 - x1 : x1 - x0;	185	int dx = x0 > x1 ? x0 - x1 : x1 - x0;
187	int dy = y0 > y1 ? y0 - y1 : y1 - y0;	186	int dy = y0 > y1 ? y0 - y1 : y1 - y0;
		187	if (dx >= dy && x0 > x1) {
		188	SWAP(x0, x1);
		189	SWAP(y0, y1);
		190	}
		191
188	int frac_x = x0 > x1 ? FP_NUM(x0 - x1, fp_bit) : FP_NUM(x1 - x0, fp_bit);	192	int frac_x = x0 > x1 ? FP_NUM(x0 - x1, fp_bit) : FP_NUM(x1 - x0, fp_bit);
189	int frac_y = y0 > y1 ? FP_NUM(y0 - y1, fp_bit) : FP_NUM(y1 - y0, fp_bit);	193	int frac_y = y0 > y1 ? FP_NUM(y0 - y1, fp_bit) : FP_NUM(y1 - y0, fp_bit);
190	int x_step = x0 > x1 ? -1 : 1;	194	int x_step = x0 > x1 ? -1 : 1;
191	int y_step = y0 > y1 ? -1 : 1;	195	int y_step = y0 > y1 ? -1 : 1;
192	int dxf = (dx << fp_bit);	196	int dxf = (dx << fp_bit);
193	int dyf = (dy << fp_bit);	197	int dyf = (dy << fp_bit);
		198	int distance = (frac_y - fp_one) * dx - (frac_x - fp_half) * dy;
194	if (dx >= dy) {	199	if (dx >= dy) {
195	int step = dx / dy;	200	int xp = x0;
196	if (step == 1) {	201	int yp = y0;
197	// If the line is mostly diagonal, default to regular bresengham.	202
198	int distance = (frac_y - fp_one) * dx - (frac_x - fp_half) * dy;	203	//
199	for (int i = 0; i <= dx; i++) {	204	// NOTE: REFERENCE
200	if (distance >= 0) {	205	// for (int i = 0; i <= dx; i++) {
201	distance -= 2 * dxf;	206	// if (distance >= 0) {
202	y0 += y_step;	207	// distance -= 2 * dxf;
203	}	208	// yp += y_step;
204	draw_pixel(x0, y0, clr);	209	// }
205	distance += 2 * dyf;	210	// draw_pixel(xp, yp, clr);
206	x0 += x_step;	211	// distance += 2 * dyf;
207	}	212	// xp += x_step;
208	} else {	213	// }
209	int distance = (frac_y - fp_one) * dx - (frac_x - fp_half) * dy;	214	// int step = dxf / dyf;
210	int remaining = dx;	215	//
211	while (remaining > (step - 1)) {	216	int step = dx;
212	distance += step * 2 * dyf;	217	if (dy > 0) {
213	if (distance >= 0) {	218	step = dx / dy;
214	draw_hline(x0, x0 + step - 1, y0, clr);	219	}
215	x0 += x_step * (step + 0);	220	int remaining = dx;
216	remaining -= step;	221	int big_step = step;
217	} else {	222	int small_step = step - 1;
218	draw_hline(x0, x0 + step, y0, clr);	223	while (remaining > small_step) {
219	distance += 2 * dyf;	224	distance += step * 2 * dyf;
220	x0 += x_step * (step + 1);	225	if (distance >= 0) {
221	remaining -= step + 1;	226	draw_hline(xp, xp + small_step, yp, clr);
222	}	227	xp += x_step * step;
223	distance -= 2 * dxf;	228	remaining -= step;
224	y0 += y_step;	229	} else {
225	}	230	if (remaining < big_step) {
226	// Default to regular bresengham for the final segment.	231	break;
227	for (int i = 0; i <= remaining; i++) {
228	if (distance >= 0) {
229	distance -= 2 * dxf;
230	y0 += y_step;
231	}	232	}
232	draw_pixel(x0, y0, clr);	233	draw_hline(xp, xp + big_step, yp, clr);
233	distance += 2 * dyf;	234	distance += 2 * dyf;
234	x0 += x_step;	235	xp += x_step * (step + 1);
		236	remaining -= step + 1;
235	}	237	}
		238	distance -= 2 * dxf;
		239	yp += y_step;
236	}	240	}
237	} else {	241	if (remaining >= 0) {
238	int distance = (frac_x - fp_one) * dy - (frac_y - fp_half) * dx;	242	draw_hline(xp, xp + remaining, yp, clr);
239	for (int i = 0; i <= dy; i++) {
240	draw_pixel(x0, y0, clr);
241	if (distance >= 0) {
242	distance -= 2 * dyf;
243	x0 += x_step;
244	}
245	distance += 2 * dxf;
246	y0 += y_step;
247	}	243	}
		244
		245	// for (int i = 0; i <= remaining; i++) {
		246	// if (distance >= 0) {
		247	// distance -= 2 * dxf;
		248	// y0 += y_step;
		249	// }
		250	// draw_pixel(xp, yp, clr);
		251	// distance += 2 * dyf;
		252	// xp += x_step;
		253	// }
		254
		255	// txt_printf("steps: %d\n", step);
		256	// if (step == 1) {
		257	// // If the line is mostly diagonal, default to regular Bresenham.
		258	// for (int i = 0; i <= dx; i++) {
		259	// if (distance >= 0) {
		260	// distance -= 2 * dxf;
		261	// y0 += y_step;
		262	// }
		263	// draw_pixel(x0, y0, clr);
		264	// distance += 2 * dyf;
		265	// x0 += x_step;
		266	// }
		267	// } else {
		268	// // Run slice Bresenham.
		269	// int remaining = dx;
		270	// while (remaining > (step - 1)) {
		271	// distance += step * 2 * dyf;
		272	// if (distance >= 0) {
		273	// draw_hline(x0, x0 + step - 1, y0, clr);
		274	// x0 += x_step * (step + 0);
		275	// remaining -= step;
		276	// } else {
		277	// draw_hline(x0, x0 + step, y0, clr);
		278	// distance += 2 * dyf;
		279	// x0 += x_step * (step + 1);
		280	// remaining -= step + 1;
		281	// }
		282	// distance -= 2 * dxf;
		283	// y0 += y_step;
		284	// }
		285	// // Default to regular Bresenham for the final segment.
		286	// for (int i = 0; i <= remaining; i++) {
		287	// if (distance >= 0) {
		288	// distance -= 2 * dxf;
		289	// y0 += y_step;
		290	// }
		291	// draw_pixel(x0, y0, clr);
		292	// distance += 2 * dyf;
		293	// x0 += x_step;
		294	// }
		295	// }
		296	} else {
		297	// int step = dy / dx;
		298	// int distance = (frac_x - fp_one) * dy - (frac_y - fp_half) * dx;
		299	// if (step == 1) {
		300	// for (int i = 0; i <= dy; i++) {
		301	// draw_pixel(x0, y0, clr);
		302	// if (distance >= 0) {
		303	// distance -= 2 * dyf;
		304	// x0 += x_step;
		305	// }
		306	// distance += 2 * dxf;
		307	// y0 += y_step;
		308	// }
		309	// } else {
		310	// // Run slice Bresenham.
		311	// int remaining = dy;
		312	// while (remaining > (step)) {
		313	// distance += step * 2 * dxf;
		314	// if (distance >= 0) {
		315	// draw_vline(x0, y0, y0 + step, 2);
		316	// y0 += y_step * (step + 0);
		317	// remaining -= step;
		318	// } else {
		319	// draw_vline(x0, y0, y0 + step + 1, 3);
		320	// distance += 2 * dxf;
		321	// y0 += y_step * (step + 1);
		322	// remaining -= step + 1;
		323	// }
		324	// distance -= 2 * dyf;
		325	// x0 += x_step;
		326	// }
		327	// // Default to regular Bresenham for the final segment.
		328	// for (int i = 0; i <= dy; i++) {
		329	// draw_pixel(x0, y0, 6);
		330	// if (distance >= 0) {
		331	// distance -= 2 * dyf;
		332	// x0 += x_step;
		333	// }
		334	// distance += 2 * dxf;
		335	// y0 += y_step;
		336	// }
		337	// }
248	}	338	}
249	#elif 0	339	#elif 0
250	int fp_bit = 6;	340	int fp_bit = 6;