-
Notifications
You must be signed in to change notification settings - Fork 1
/
bitgeom.tex
3073 lines (2743 loc) · 104 KB
/
bitgeom.tex
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[12pt,openany,a4,usenames,dvipsnames]{book}
\usepackage{polyglossia}
\usepackage{fontspec}
\setmainlanguage{english}
\setotherlanguage{greek}
\setmainfont{Redaction}
\usepackage{unicode-math}
%\setmathfont{Latin Modern Math}
\setmathfont{TeX Gyre Schola Math}
\setmonofont[Scale=1.1]{CMU Typewriter Text}
\newfontfamily\pixelfont{Redaction35-Regular}
\newfontfamily\fira[Scale=0.90]{Fira Sans}
\newfontfamily\thumbfont[Scale=0.9]{Redaction35-Bold}
\newfontfamily\pixeltitle[Scale=3.5]{Redaction35-Bold}
\newfontfamily\reduxtitle[Scale=3.5]{Redaction-Bold}
\newfontfamily\cm{CMU Serif}
\newfontfamily\symbola[Scale=5]{Symbola}
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{dot2texi}
\usepackage[breaklinks=true]{hyperref}
\hypersetup{
unicode,
verbose=false,
pdfpagelayout=TwoColumnRight,
bookmarksopen,
colorlinks,
citecolor=black,
filecolor=black,
linkcolor=black,
urlcolor=black
}
\usepackage{wrapfig}
\usepackage[nobiblatex]{xurl}
\usepackage{makeidx}
\makeindex
\usepackage[totoc]{idxlayout}
\usepackage{microtype}
\usepackage[perpage,symbol*]{footmisc}
\usepackage{marginnote}
\usepackage[noclrdblpg]{colophon}
\usepackage{bookmark}
\usepackage{amsmath}
\usepackage{float}
\usepackage{skeldoc}
\floatplacement{figure}{H}
\usepackage{tikz}
\usepackage{svg}
\usepackage{calc} % for inkscape pdf tex
\usepackage{attachfile2}
%\usepackage[showframe,marginparwidth=3cm,twoside=true]{geometry}
\usepackage[marginparwidth=3cm,twoside=true,a4paper]{geometry}
\usepackage{metalogo}
\usepackage{csquotes}
\usepackage[compact,nostruts,medium,noindentafter]{titlesec}
\titleformat{\chapter}[display]%
{\normalfont\huge\bfseries}{\chaptertitlename\ \thechapter}{0pt}{\Huge}
\newcommand{\chapterbreak}{}
\titlespacing*{\chapter}{0pt}{-50pt}{40pt}
\newcommand\makeskelfig{%
\begin{figure}[H]
{\centering%
\skelfig[width=0.4\textwidth]{2\baselineskip}%
\skelcaption[width=0.2\textwidth,lines=1]{}}
\end{figure}}
\usepackage{setspace}
\definecolor{blackoutline}{RGB}{14,14,14}
\definecolor{bgcolor}{rgb}{0.95,0.95,0.95}
\definecolor{red}{rgb}{1,0,0}
\definecolor{venetianred}{RGB}{200,8,21}
\definecolor{gray}{RGB}{24,24,24}
\definecolor{thered} {rgb} {0.65,0.04,0.07}
\definecolor{thegreen} {rgb} {0.06,0.44,0.08}
\definecolor{theblue} {rgb} {0.02,0.04,0.48}
\definecolor{sectioning}{gray}{0.44}
\definecolor{thegrey} {gray}{0.5}
\definecolor{theframe} {gray}{0.75}
\definecolor{theshade} {gray}{0.94}
\definecolor{thepeach} {RGB}{246,232,220}
\definecolor{punchbg}{RGB}{250, 230, 180}
\definecolor{punchframe}{RGB}{240, 220, 170}
\usepackage[cache=false,outputdir=build]{minted}
\setminted[rust]{labelposition=bottomline,bgcolor=thepeach,rulecolor=punchframe,fontsize=\scriptsize,baselinestretch=0.5,frame=leftline,breaklines=true,breakanywhere=true}
\setminted[c]{bgcolor=theshade,fontsize=\scriptsize,baselinestretch=0.5,frame=leftline,breaklines=true,breakanywhere=true}
%\setminted[tex]{breaklines=true,linenos=true,bgcolor=theshade,frame=single,framesep=5pt,rulecolor=theframe}
%\setminted[shell]{breaklines=true,linenos=true,bgcolor=theshade,frame=single,framesep=5pt,rulecolor=theframe}
%\definecolor{bg}{rgb}{0.95,0.95,0.95}
\usepackage{xspace}
\usepackage{xparse}
\usepackage{contour}
\usepackage[normalem]{ulem}
\usepackage{minted}
\usemintedstyle{bw}
\ExplSyntaxOn
\NewDocumentCommand{\TitleOutline}{m}
{
\seq_set_split:Nnn \l_tmpa_seq { ~ } { #1 }
\seq_map_inline:Nn \l_tmpa_seq { \contour{blackoutline}{##1} ~ } \unskip
}
\ExplSyntaxOff
\renewcommand{\ULdepth}{1.8pt}
\contourlength{0.8pt}
\makeatletter
\renewcommand\@dotsep{200}
\renewcommand{\l@chapter}{\@dottedtocline{0}{0pt}{2.6em}}
\renewcommand{\l@section}{\@dottedtocline{1}{1.5em}{2.6em}}
\renewcommand{\l@subsection}{\@dottedtocline{2}{4.0em}{3.6em}}
\renewcommand{\l@subsubsection}{\@dottedtocline{3}{7.4em}{4.5em}}
\makeatother
\newcommand\bitmap{{\pixelfont{}bitmap}}
\newcommand\bitmaps{{\pixelfont{}bitmaps}}
\newcommand\pixel{{\pixelfont{}pixel}}
\newcommand\pixels{{\pixelfont{}pixels}}
\newcommand\Rust{{\fira{}\textbf{Rust}}}
\newcommand\colorunderline[1]{\bgroup\markoverwith{\textcolor{#1}{\rule[-0.5ex]{2pt}{0.8pt}}}\ULon}
\newcommand{\myuline}[2]{%
\colorunderline{#1}{\phantom{#2}}%
\llap{\contour{white}{#2}}%
}
\DeclareRobustCommand{\myurl}[2]{%
\href{#1}{\myuline{blue}{#2}}%
}
\newcommand{\attachsource}[1]{%
\marginnote{\scriptsize{}%
\texttt{\tiny{}#1}:\\
\attachfile[icon=Paperclip]{#1}\hfill\\
This code file is a PDF attachment}%
}%
\DeclareRobustCommand{\sourceinlib}{%
\marginnote{\scriptsize{}%
This code is included in the distributed library file in the \emph{\nameref{ch:intro-library}} chapter.}%
}%
\newcommand\titletext{A {\pixeltitle{}Bitmapper}'s Companion}
\newcommand\covertitletext{\TitleOutline{A {\pixeltitle{}Bitmapper}'s Companion}}
\title{\titletext{}}
\newcommand\subtitle{an introduction to basic \bitmap{} mathematics and algorithms with code samples in \Rust{}}
\newcommand\coversubtitle{\TitleOutline{an introduction to basic \bitmap{} mathematics and algorithms with code samples in \Rust{}}}
\hypersetup{
pdftitle={\titletext{}},
pdfauthor={epilys},
pdfsubject={programming},
}
\usepackage{wallpaper}
\newsavebox{\mintedbox}
\usepackage[thumblink=line,height=50pt,minheight={50pt},width=50pt,distance={2mm},topthumbmargin={5cm},bottomthumbmargin={2pt},eventxtindent={0pt},oddtxtexdent={2pt},evenmarkindent={0pt},oddmarkexdent={0pt},evenprintvoffset={0pt},nophantomsection=false,ignorehoffset=true,ignorevoffset=true,final=true,hidethumbs=false,verbose=true]{thumbs}
\definecolor{ThumbBg} {rgb} {0.2,0.2,0.2}
\definecolor{DarkBg} {rgb} {0.17,0.17,0.17}
\definecolor{DarkFg} {rgb} {0.90,0.90,0.90}
\definecolor{LightBg} {rgb}{1.0,1.0,1.0}
\newcommand{\setbackgroundcolour}{\pagecolor{DarkBg}}
\newcommand{\settextcolour}{\color[rgb]{0.90,0.90,0.90}}
\newcommand{\invertbackgroundtext}{\setbackgroundcolour\settextcolour}
\newcommand{\revertbackgroundcolour}{\pagecolor{LightBg}}
\newcommand{\reverttextcolour}{\color[rgb]{0.19,0.19,0.19}}
\newcommand{\revertbackgroundtext}{\revertbackgroundcolour\reverttextcolour}
\newcommand\myaddthumb[2]{%
%\addtitlethumb{#1}{\fcolorbox{red}{black}{\parbox[t][45pt]{45pt}{\noindent%
\addtitlethumb{\hspace{5pt}#1}{%
\parbox[t][43pt]{43pt}{\centering
\vfill\noindent%
{\linespread{.7}\thumbfont{}#2\par\vfill}%
}%
}{white}{ThumbBg}{pagesLTS.0}%
}%
\pagenumbering{arabic}
\usepackage[textsize=tiny]{todonotes}
\DeclareRobustCommand{\Caption}[1]{\par%
\vspace{1em}
{\noindent{}#1}}
\usepackage{scalerel}
\DeclareRobustCommand\archat[1]{%
\begin{array}{c}
\stretchto{
\scaleto{
\scalerel*[\widthof{#1}]{\frown}
{\rule[-\textheight/2]{1ex}{\textheight}} %WIDTH-LIMITED BIG WEDGE
}{1.25\textheight} % THIS STRETCHES THE WEDGE A LITTLE EXTRA WIDE
}{0.5ex}\\ % THIS SQUEEZES THE WEDGE TO 0.5ex HEIGHT
#1\\ % THIS STACKS THE WEDGE ATOP THE ARGUMENT
\rule{0ex}{.01ex}
\end{array}
}
\DeclareRobustCommand\TheEnd{%
\par%
\thispagestyle{empty}%
{\vfill{}\noindent{}\centering{}\symbola{}⸎\par}%
}
\usepackage[
indexing=false,
bibstyle=numeric,
citestyle=numeric,
backref=true,
datecirca=true,
dateuncertain=true,
dateabbrev=false,
sorting=none,
datezeros=false,% pad date components with zeros?
dateera=secular,
defernumbers=true,
]{biblatex}
\addbibresource{cite.bib}
\begin{document}
\pagestyle{plain}
\assignpagestyle{\chapter}{plain}
\newgeometry{left=1cm,top=0.1cm,right=1cm,bottom=0.1cm}
\pdfbookmark{Title page}{title-page}%cover
\ThisLRCornerWallPaper{0.55}{figures/Holbein_Skull2_inverted.png}
\setstretch{1.1}
\invertbackgroundtext
\addtolength{\parskip}{5pt}%
\newlength\drop
\thispagestyle{empty}
\begingroup% Harry Carter
\setlength{\drop}{0.1\textheight}
\vspace*{\drop}
\begin{flushleft}
\textcolor{thegrey}{\rule{\textwidth}{1.6pt}}%
\vspace{-0.9\baselineskip}
\textcolor{sectioning}{\rule{\textwidth}{0.4pt}}\\[0.8\baselineskip]
{\centering
\contourlength{0.02em}
\scalebox{2.0}{\parbox{0.5\textwidth}{\centering{\reduxtitle{}\covertitletext{}}}}\\
\vspace{.8\baselineskip}
\par
\vspace{-0.4\baselineskip}
}\textcolor{thegrey}{\rule{\textwidth}{1.6pt}}%
\vspace{-0.9\baselineskip}
\textcolor{sectioning}{\rule{\textwidth}{0.4pt}}\\[0.2\baselineskip]
{\Large{}\TitleOutline{epilys}}\hfill{\small{}\TitleOutline{2021}}
\vfill%
\scalebox{1.5}{\parbox{0.28\textwidth}{\noindent%
{\LARGE\raggedleft\coversubtitle{}\par}
}}
\vfill%
\end{flushleft}%
\endgroup
\clearpage{}
\restoregeometry
\revertbackgroundtext
\clearpage{}
\thispagestyle{empty}
.
\clearpage{}
\thispagestyle{empty}
\thumbsoverview{map}
\clearpage{}
\thispagestyle{empty}
\marginnote{\includegraphics{figures/xface.png}}[-1.3\baselineskip]\noindent{}Manos Pitsidianakis (epilys)\\
\myurl{https://nessuent.xyz}{https://\-nessuent.xyz}\\
\myurl{https://github.com/epilys}{https://github.com/epilys}\\
\myurl{[email protected]}{[email protected]}\\
\noindent{}All non-screenshot figures were generated by hand in Inkscape unless otherwise stated.
\noindent{}The skull in the cover is a transformed \bitmap{} of the skull in the 1533 oil painting by Hans Holbein the Younger, \myurl{https://en.wikipedia.org/wiki/The_Ambassadors_(Holbein)}{\emph{The Ambassadors}}, which features a floating distorted skull rendered in anamorphic perspective.
\noindent{}\emph{A Bitmapper’s Companion}, 2021\\
\noindent{}\textbf{Special Topics} $\blacktriangleright{}$ \textbf{Computer Graphics} $\blacktriangleright{}$ \textbf{Programming}\\
\noindent{}006.6'6--dc20
\vfill{}
\noindent{}Copyright © 2021 by Emmanouil Pitsidianakis
\noindent{}This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. To view a copy of this license, visit\\\myurl{https://creativecommons.org/licenses/by-nc-sa/3.0/}{http\-:\-//\-creativecommons\-.\-org\-/\-licenses\-/\-by-nc-sa/3.0/} or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.
\noindent{}The source code for this work is available under the GNU GENERAL PUBLIC LICENSE version 3 or later. You can view it, study it, modify it for your purposes as long as you respect the license if you choose to distribute your modifications.
\noindent{}The source code is available here
\noindent{}\myurl{https://github.com/epilys/bitmappers-companion}{https://github.com/epilys/bitmappers-companion}
\clearpage{}
\myaddthumb{Table Of Contents}{toc}
\pdfbookmark{\contentsname}{toc}
\ThisLRCornerWallPaper{0.6}{figures/The-Ambassadors.png}
\tableofcontents
\ThisLRCornerWallPaper{0.4}{figures/Holbein_Skull.png}
\clearpage{}
\myaddthumb{Introduction}{intro}
\part{Introduction}
\chapter{Data representation}\label{ch:intro-library}
The data structures we're going to use is \emph{Point} and \emph{Image}. \emph{Image} represents a \bitmap{}, although we will use full RGB colors for our points therefore the size of a \pixel{} in memory will be \texttt{u8} instead of 1 bit.
We will work on the cartesian grid representing the framebuffer that will show us the \pixels{}. The \emph{origin} of this grid (i.e.\ the center) is at $(0,0)$.%
\begin{figure}%
\centering
\input{figures/cartesian_grid.pdf_tex}
\end{figure}%
%
We will represent points as pairs of signed integers. When actually drawing them though, negative values and values outside the window's geometry will be ignored (clipped).
%
\attachsource{src/lib.rs}
%
\begin{minted}{rust}
pub type Point = (i64, i64);
pub type Line = (i64, i64, i64);
pub const fn from_u8_rgb(r: u8, g: u8, b: u8) -> u32 {
let (r, g, b) = (r as u32, g as u32, b as u32);
(r << 16) | (g << 8) | b
}
pub const AZURE_BLUE: u32 = from_u8_rgb(0, 127, 255);
pub const RED: u32 = from_u8_rgb(157, 37, 10);
pub const WHITE: u32 = from_u8_rgb(255, 255, 255);
pub const BLACK: u32 = 0;
pub struct Image {
pub bytes: Vec<u32>,
pub width: usize,
pub height: usize,
pub x_offset: usize,
pub y_offset: usize,
}
impl Image {
pub fn new(width: usize, height: usize, x_offset: usize, y_offset: usize) -> Self;
pub fn magick_open(path: &str, x_offset: usize, y_offset: usize) -> Result<Self, Box<dyn Error>>;
pub fn from_xbm(path: &str, x_offset: usize, y_offset: usize) -> Result<Self, Box<dyn Error>>;
pub fn draw(&self, buffer: &mut Vec<u32>, fg: u32, bg: Option<u32>, window_width: usize);
pub fn draw_outline(&mut self);
pub fn clear(&mut self);
pub fn plot(&mut self, x: i64, y: i64);
pub fn get(&mut self, x: i64, y: i64) -> u32;
pub fn plot_ellipse(
&mut self,
(xm, ym): (i64, i64),
(a, b): (i64, i64),
quadrants: [bool; 4],
_wd: f64,
);
pub fn plot_line_width(&mut self, point_a: Point, point_b: Point, wd: f64);
pub fn flood_fill(&mut self, mut x: i64, y: i64);
}
\end{minted}
An RGB color with coordinates $(r, g, b)$ where $r, g, b: \textrm{\texttt{u8} values}$ is represented as a \texttt{u32} number with the red component shifted 16 bits to to the left, the green component 8 bits, and the final 8 bits are the blue component. It's essentially laying the $r, g, b$ values sequentially and forming a 32 bit value out of three 8 bit values.
Our \texttt{Image::plot(x,y)} function sets the $(x, y)$ pixel to black. To do that we set the element \texttt{y * width + x} of the \texttt{Image's} buffer to the black color as RGB.
\chapter{Displaying {\pixels{}} to your screen}
A way to display an \emph{Image} is to use the \texttt{minifb} crate which allows you to create a window and draw \pixels{} directly on it. Here's how you could set it up:
%
\attachsource{src/bin/introduction.rs}
%
%
\begin{minted}{rust}
use bitmappers_companion::*;
use minifb::{Key, Window, WindowOptions};
const WINDOW_WIDTH: usize = 400;
const WINDOW_HEIGHT: usize = 400;
fn main() {
let mut buffer: Vec<u32> = vec![WHITE; WINDOW_WIDTH * WINDOW_HEIGHT];
let mut window = Window::new(
"Test - ESC to exit",
WINDOW_WIDTH,
WINDOW_HEIGHT,
WindowOptions {
title: true,
//borderless: true,
//resize: false,
//transparency: true,
..WindowOptions::default()
},
)
.unwrap();
// Limit to max ~60 fps update rate
window.limit_update_rate(Some(std::time::Duration::from_micros(16600)));
let mut image = Image::new(50, 50, 150, 150);
image.draw_outline();
image.draw(&mut buffer, BLACK, None, WINDOW_WIDTH);
while window.is_open()
&& !window.is_key_down(Key::Escape)
&& !window.is_key_down(Key::Q) {
window
.update_with_buffer(&buffer, WINDOW_WIDTH, WINDOW_HEIGHT)
.unwrap();
let millis = std::time::Duration::from_millis(100);
std::thread::sleep(millis);
}
}
\end{minted}
Running this will show you something like this:
% FIXME reduce window size and resulting screenshot size
\begin{figure}[H]
\centering
\includegraphics{figures/introduction.png}
\end{figure}
By drawing each individual pixel with the \texttt{Image::plot} and \texttt{Image::plot\_color} functions, we can draw any possible RGB picture of the buffer size. In this book's chapters, we will usually calculate pixels by using discrete calculations of each pixels as integers, or by using rational values (with 64 bit floating point representation) and then calculating their integer values with the \texttt{floor} function. This can also be done by casting an \texttt{f64} type to \texttt{i64} with \texttt{as}:
\begin{minted}{rust}
let val: f64 = 5.5;
let val: i64 = val as i64;
assert_eq!(5i64, val);
\end{minted}
\chapter{Bits to byte \pixels{}}\label{ch:bitstobytes}
If we worked with 1 bit images (black and white) it could be a more space-efficient representation to store the pixels as bits: 8 pixels in 1 byte. For this book we accept that our images can have RGB colors. The \texttt{xbm} format stores pixels like that, and we might wish to convert them to our representation.
Let's define a way to convert bit information to a byte vector:
\begin{minted}{rust}
pub fn bits_to_bytes(bits: &[u8], width: usize) -> Vec<u32> {
let mut ret = Vec::with_capacity(bits.len() * 8);
let mut current_row_count = 0;
for byte in bits {
for n in 0..8 {
if byte.rotate_right(n) & 0x01 > 0 {
ret.push(BLACK);
} else {
ret.push(WHITE);
}
current_row_count += 1;
if current_row_count == width {
current_row_count = 0;
break;
}
}
}
ret
}
\end{minted}
\chapter{Loading graphics files in \Rust{}}
The book's library includes a method to load \texttt{xbm} files on runtime (see \emph{\nameref{ch:xbmtors}} for including them in your binary at compile time). If your system has \texttt{ImageMagick} installed and the commands \texttt{identify} and \texttt{magick} are in your \texttt{PATH} environment variable, you can use the \texttt{Image::magick\_open} method:
\begin{minted}{rust}
impl Image {
...
pub fn magick_open(path: &str, x_offset: usize, y_offset: usize) -> Result<Self, Box<dyn Error>>;
...
}
\end{minted}
It simply converts the image file you pass to it to raw bytes using the invocation \texttt{magick convert \emph{path} RGB:-} which prints raw \texttt{RGB} content to \texttt{stdout}.
If you have another way to load pictures such as your own code or a picture format library crate, all you have to do is convert the pixel information to an \texttt{Image} whose definition we repeat here:
\begin{minted}{rust}
pub struct Image {
pub bytes: Vec<u32>,
pub width: usize,
pub height: usize,
pub x_offset: usize,
pub y_offset: usize,
}
\end{minted}
\chapter{Including \texttt{xbm} files in \Rust{}}\label{ch:xbmtors}
\emph{The end of this chapter includes a short \Rust{} program to automatically convert \texttt{xbm} files to equivalent \Rust{} code.}
\texttt{xbm} files are C source code files that contain the \pixel{} information for an image as macro definitions for the dimensions and a static \texttt{char} array for the \pixels{}, with each bit column representing a pixel. If the width dimension doesn't have 8 as a factor, the remaining bit columns are left blank/ignored.
They used to be a popular way to share user avatars in the old internet and are also good material for us to work with, since they are small and numerous. The following is such an image:
\begin{figure}[H]
\centering
\includegraphics{figures/news.png}
\end{figure}
%FIXME
Then, we can convert the \texttt{xbm} file from C to \Rust{} with the following transformations:
\begin{minted}{c}
#define news_width 48
#define news_height 48
static char news_bits[] = {
\end{minted}
to
\begin{minted}{rust}
const NEWS_WIDTH: usize = 48;
const NEWS_HEIGHT: usize = 48;
const NEWS_BITS: &[u8] = &[
\end{minted}
And replace the closing \texttt{\}} with \texttt{]}.
We can then include the new file in our source code:
\begin{minted}{rust}
include!("news.xbm.rs");
\end{minted}
load the image:
\begin{minted}{rust}
let mut image = Image::new(NEWS_WIDTH, NEWS_HEIGHT, 25, 25);
image.bytes = bits_to_bytes(NEWS_BITS, NEWS_WIDTH);
\end{minted}
and finally run it:
\begin{figure}[H]
\centering
\includegraphics{figures/intro-2.png}
\end{figure}
The following short program uses the \texttt{regex} crate to match on these simple rules and print the equivalent code in \texttt{stdout}. You can use it like so:
\begin{minted}{shell}
cargo run --bin xbmtors -- file.xbm > file.xbm.rs
\end{minted}
\attachsource{src/bin/xbmtors.rs}
\begin{minted}{rust}
use regex;
use regex::Regex;
use std::fs::File;
use std::io::prelude::*;
fn main() {
let args = std::env::args().skip(1).collect::<Vec<String>>();
if args.len() != 1 {
println!("one argument expected, the xbm file path to convert.");
return;
}
let mut file = match File::open(&args[0]) {
Err(err) => panic!("couldn't open {}: {}", args[0], err),
Ok(file) => file,
};
let mut s = String::new();
if let Err(err) = file.read_to_string(&mut s) {
panic!("couldn't read {}: {}", args[0], err);
}
let re = Regex::new(
r"(?imx)
^\s*\x23\s*define\s+(?P<i>.+?)_width\s+(?P<w>\d\d*)$
\s*
^\s*\x23\s*define\s+.+?_height\s+(?P<h>\d\d*)$
\s*
^\s*static(\s+unsigned){0,1}\s+char\s+.+?_bits..\s*=\s*\{(?P<b>[^}]+)\};
",
)
.unwrap();
let caps = re
.captures(&s)
.expect("Could not convert file, regex doesn't match :(");
let ident = caps.name("i").unwrap().as_str().to_uppercase();
let out = re.replace_all(&s, format!("const {i}_WIDTH: usize = $w;\nconst {i}_HEIGHT: usize = $h;\nconst {i}_BITS: &[u8] = &[$b];", i = &ident));
println!("{}", out.trim());
}
\end{minted}
\clearpage{}
\myaddthumb{Points And Lines}{lines}
\part{Points And Lines}
\chapter{Distance between two points}\index{distance!between two points}
\begin{figure}[H]
\centering
\input{figures/fig1.pdf_tex}
\end{figure}
Given two points, $K$ and $L$, an elementary application of Pythagoras' Theorem gives the distance between them as
\begin{equation}
r = \sqrt{(x_{L} - x_{K})^{2} +(y_{L} - y_{K})^{2}}
\end{equation}
which is simply coded:
\begin{minted}{rust}
pub fn distance_between_two_points(p_k: Point, p_l: Point) -> f64 {
let (x_k, y_k) = p_k;
let (x_l, y_l) = p_l;
let xlk = x_l - x_k;
let ylk = y_l - y_k;
f64::sqrt((xlk*xlk + ylk*ylk) as f64)
}
\end{minted}
\chapter{Moving a point to a distance at an angle}\index{distance!moving a point}
Moving a point $P=(x,y)$ at distance $d$ at an angle of $r$ radians is solved with simple trigonometry:
$$P'=(x+d\times{}\cos{}r, y+d\times{}\sin{}r)$$
Why? The problem is equivalent to calculating the point of a circle with $P$ as the center, $d$ the radius at angle $r$ and as we will later\footnote{\emph{\nameref{sec:equations-circles}} page \pageref{sec:equations-circles}} see this is how the points of a circle are calculated.
\begin{minted}{rust}
pub fn move_point(p: Point, d: f64, r: f64) -> Point {
let (x, y) = p;
(x + (d * f64::cos(r)).round() as i64, y + (d * f64::sin(r)).round() as i64)
}
\end{minted}
\chapter{Equations of a line}\label{ch:equations-lines}\index{line!equations}
There are several ways to describe a line mathematically. We'll list the convenient ones for drawing \pixels{}.
The equation that describes every possible line on a two dimensional grid is the \emph{implicit} form $ax+by=c, (a,b) \neq{} (0,0)$. We can generate equivalent equations by adding the equation to itself, i.e.\ $ax+by=c \equiv 2ax+2by=2c \equiv a'x+b'y=c', a'=2a, b'=2b, c'=2c$ as many times as we want. To "minimize" the constants $a,b,c$ we want to satisfy the relationship $a^{2}+b^{2}=1$, and thus can convert the equivalent equations into one representative equation by multiplying the two sides with $\frac{1}{\sqrt{a^2+b^2}}$; this is called the normalized equation. % TODO: why? add footnote: in the normalized form, a is the cosine of the angle the normal vector makes with the x axis, and b the cosine of the angle with the y axis. and c = - (dist of line to the origin)
The \emph{slope intercept form} describes any line that intercepts the $y$ axis at $b \in{} \mathbb{R}$ with a specific slope $a$:
$$y=ax+b$$
The \emph{parametric} form\ldots{} % TODO
%% TODO: add conversion between forms
\section{Line through a point $P=(x_p,y_p)$ and a slope $m$}\index{line!through point and slope}
$$y-y_p=m(x-x_p)$$
\section{Line through two points}\label{sec:linethroughtwopoints}\index{line!through two points}
\begin{figure}[H]
\centering
\input{figures/line_through_points.pdf_tex}
\end{figure}
It seems sufficient, given the coordinates of two points $M, N$, to calculate $a, b$ and $c$ to form a line equation:
$$ax+by+c=0$$
If the two points are not the same, they necessarily form such a line. To get there, we start from expressing the line as parametric over $t$: at $t=0$ it's at point $M$ and at $t=1$ it's at point $N$:
$$c = c_M + (c_N - c_M)t, t\in R, c \in \{x, y\}$$
$$c = c_M, t\in R, c \in \{x, y\}$$
Substituting $t$ in one of the equations we get:
$$(y_M - y_N)x + (x_N-x_M)y+(x_{M}y_{N}-x_{N}y_{M})=0$$
Which is what we were after. We should finish by normalising what we found with $\frac{1}{\sqrt{a^2+b^2}}$, but our coordinates are integers and have no decimal or floating point accuracy.
\begin{minted}{rust}
fn find_line(point_a: Point, point_b: Point) -> (i64, i64, i64) {
let (xa, ya) = point_a;
let (xb, yb) = point_b;
let a = yb - ya;
let b = xa - xb;
let c = xb * ya - xa * yb;
(a, b, c)
}
\end{minted}
%
%
%
\chapter{Drawing a line}\index{line!drawing}
\begin{minted}{rust}
fn plot_line(image: &mut Image, (a, b, c): (i64, i64, i64)) {
let x = if a != 0 { -1 * (c) / a } else { 0 };
let mut prev_point = (x, 0);
for y in 0..(WINDOW_HEIGHT as i64) {
// ax+by+c =0 =>
// x=(-c-by)/a
let x = if a != 0 { -1 * (c + b * y) / a } else { 0 };
let new_point = (x, y);
image.plot_line_width(prev_point, new_point, 1.0);
prev_point = new_point;
}
}
\end{minted}
%
%
%
\chapter{Distance from a point to a line}\index{distance!point from a line}
\begin{figure}[H]
\centering
\input{figures/point_line_distance.pdf_tex}
\end{figure}
\section{Using the implicit equation form}
Let's find the distance from a given point $P$ and a given line $L$. Let $d$ be the distance between them. Bring $L$ to the implicit form $ax+by=c$.
$$d= \frac{|ax_p+by_p+c|}{\sqrt{a^2+b^2}}$$
\section{Using an $L$ defined by two points $P_1, P_2$}
With $P=(x_0, y_0)$, $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$.
$$d=\frac{|(x_2-x_1)(y_1-y_0)-(x_1-x_0)(y_2-y_1)|}{\sqrt{((x_2-x_1)^2+(y_2-y_1)^2}}$$
\section{Using an $L$ defined by a point $P_l$ and angle $\hat{θ}$}
$$d=\left|\cos{}(\hat{θ})(P_{ly}-y_p)-\sin{}(\hat{θ})(P_{lx} - P_x)\right|$$
\section*{The code}
This function uses the implicit form.
\sourceinlib%
\begin{minted}{rust}
type Line = (i64, i64, i64);
pub fn distance_line_to_point((x, y): Point, (a, b, c): Line) -> f64 {
let d = f64::sqrt((a * a + b * b) as f64);
if d == 0.0 {
0.
} else {
(a * x + b * y + c) as f64 / d
}
}
\end{minted}
\chapter{Perpendicular lines}\label{ch:perpendicular}\index{perpendicular}\index{line!perpendicular}
\section{Find perpendicular to line that passes through given point}
Now, we wish to find the equation of the line that passes through $P$ and is perpendicular to $L$. Let's call it $L_{⊥}$. $L$ in implicit form is $ax+by+c=0$. The perpendicular will be:
$$L_{⊥}: bx-ay+(aP_y-bP_x)=0$$
\subsection*{The code}
\sourceinlib%
\begin{minted}{rust}
type Line = (i64, i64, i64);
fn perpendicular((a, b, c): Line, p: Point) -> Line {
(b, -1 * a, a * p.1 - b * p.0)
}
\end{minted}
\section{Find point in line that belongs to the perpendicular of given point}
\subsection*{The code}
\sourceinlib%
\begin{minted}{rust}
fn point_perpendicular((a, b, c): Line, p: Point) -> Point {
let d = (a * a + b * b) as f64;
if d == 0. {
return (0, 0);
}
let cp = a * p.1 - b * p.0;
(
((-a * c - b * cp) as f64 / d) as i64,
((a * cp - b * c) as f64 / d) as i64,
)
}
\end{minted}
% From graphic gems vol 2 pdf page 40
\chapter{Angle between two lines}\index{angle!between two lines}
\begin{figure}[H]
\centering
\includegraphics[width=0.6\textwidth,keepaspectratio]{figures/line_angles.pdf}
\end{figure}
By angle we mean the angle formed by the two directions of the lines; and direction vectors start from the origin (in the figure, they are the \textcolor{red}{red arrows}). So if we want any of the other three angles, we already know them from basic geometry as shown in the figure above.
If you prefer using the implicit equation, bring the two lines $L_1$ and $L_2$ to that form ($a_1x+b_1y+c=0$ and $a_2x+b_2y+c_2=0$) and you can directly find $\hat{θ}$ with the formula:
$$\hat{θ} = \arccos{}\frac{a_{1}a_{2}+b_{1}b_{2}}{\sqrt{\left(a_1^2 + b_1^2\right)\left(a_2^2+b_2^{2}\right)}}$$
For the following parametric equations of $L_1$, $L_2$:
$$ L_{1} = \left(\{x=x_1 +f_1t\}, \{y=y_1+g_1t\}\right)$$
$$ L_{2} = \left(\{x=x_2 +f_2s\}, \{y=y_2+g_2s\}\right)$$
the formula is:
$$\hat{θ} = \arccos\frac{f_{1}f_{2}+g_{1}g_{2}}{\sqrt{\left(f_1^2 + g_1^2\right)\left(f_2^2+g_2^2\right)}}$$
\noindent{}The code:
\attachsource{src/bin/anglebetweenlines.rs}
\begin{minted}{rust}
fn find_angle((a1, b1, c1): (i64, i64, i64), (a2, b2, c2): (i64, i64, i64)) -> f64 {
let nom = (a1 * a2 + b1 * b2) as f64;
let denom = ((a1 * a1 + b1 * b1) * (a2 * a2 + b2 * b2)) as f64;
f64::acos(nom / f64::sqrt(denom))
}
\end{minted}
\begin{figure}[H]
\centering
\begin{minipage}{0.49\textwidth}
\includegraphics[width=\textwidth,keepaspectratio]{figures/anglelines1.png}
\end{minipage}
\hspace{.1em}
\begin{minipage}{0.49\textwidth}
\includegraphics[width=\textwidth,keepaspectratio]{figures/anglelines2.png}
\end{minipage}
\Caption{The \texttt{src/bin/anglebetweenlines.rs} example has two interactive lines and computes their angle with 64bit floating point accuracy.}
\end{figure}
%
%
%
%
\chapter{Intersection of two lines}\label{ch:intersection-lines}\index{line!intersection}
\begin{figure}[H]
\centering
\includegraphics[width=0.6\textwidth,keepaspectratio]{figures/intersection_lines.pdf}
\end{figure}
If the lines $L_1$, $L_2$ are in implicit form ($a_1x+b_1y+c=0$ and $a_2x+b_2y+c_2=0$), the result comes after checking if the lines are parallel (in which case there's no single point of intersection):
$$a_1b_2-a_2b_1 \neq{} 0$$
If they are not parallel, $P$ is:
$$P = \left(\frac{b_1c_2-b_2c_1}{a_1b_2-a_2b_1}, \frac{a_2c_1-a_1c_2}{a_1b_2-a_2b_1}\right)$$
\noindent{}The code:
\attachsource{src/bin/lineintersection.rs}
\begin{minted}{rust}
fn find_intersection((a1, b1, c1): (i64, i64, i64), (a2, b2, c2): (i64, i64, i64)) -> Option<Point> {
let denom = a1 * b2 - a2 * b1;
if denom == 0 {
return None;
}
Some(((b1 * c2 - b2 * c1) / denom, (a2 * c1 - a1 * c2) / denom))
}
\end{minted}
\begin{figure}[H]
\centering
\begin{minipage}{0.49\textwidth}
\includegraphics[width=\textwidth,keepaspectratio]{figures/lineintersection1.png}
\end{minipage}
\hspace{.1em}
\begin{minipage}{0.49\textwidth}
\includegraphics[width=\textwidth,keepaspectratio]{figures/lineintersection2.png}
\end{minipage}
\Caption{The \texttt{src/bin/lineintersection.rs} example has two interactive lines and computes their point of intersection.}
\end{figure}
%
%
%
%
\chapter{Line equidistant from two points}\index{line!equidistant}\index{equidistant line}
\begin{figure}[H]
\centering
\includegraphics[height=8\baselineskip,keepaspectratio]{figures/equidistant.pdf}
\end{figure}
Let's name this line $L$. From previous chapter\footnote{See \emph{\nameref{sec:linethroughtwopoints}}, page \pageref{sec:linethroughtwopoints}} we know how to get the line $L$ that's created by the two points $M$ and $N$:
%
$$L: (y_M - y_N)x + (x_N-x_M)y+(x_{M}y_{N}-x_{N}y_{M})=0$$%
%
We need the perpendicular line over the midpoint of $L$.\footnote{See \emph{\nameref{ch:perpendicular}}, page \pageref{ch:perpendicular}} The midpoint also satisfies $L$'s equation. The midpoint's coordinates are intuitively:\index{midpoint}
$$P_{mid} = \left(\frac{x_M + x_N}{2}, \frac{y_M + y_N}{2}\right)$$
The perpendicular's $L_{⊥}$ equation is
$$L_{EQ} = L_{⊥}: yx-ay+\left(aP_{mid_y}-bP_{mid_x}\right)=0$$
\noindent{}The code:
\attachsource{src/bin/equidistant.rs}
\begin{minted}{rust}
fn find_equidistant(point_a: Point, point_b: Point) -> (i64, i64, i64) {
let (xa, ya) = point_a;
let (xb, yb) = point_b;
let midpoint = ((xa + xb) / 2, (ya + yb) / 2);
let al = ya - yb;
let bl = xb - xa;
// If we had subpixel accuracy, we could do:
//assert_eq!(al*midpoint.0+bl*midpoint.1, -cl);
let a = bl;
let b = -1 * al;
let c = (al * midpoint.1) - (bl * midpoint.0);
(a, b, c)
}
\end{minted}
\begin{figure}[H]
\centering
\begin{minipage}{0.49\textwidth}
\includegraphics[width=\textwidth,keepaspectratio]{figures/equidistant1.png}
\end{minipage}
\hspace{.1em}
\begin{minipage}{0.49\textwidth}
\includegraphics[width=\textwidth,keepaspectratio]{figures/equidistant2.png}
\end{minipage}
\Caption{The \texttt{src/bin/equidistant.rs} example has two interactive points and computes their $L_{EQ}$.}
\end{figure}
%
%
%
%
%
\chapter{Reflection of point on line}\index{line!reflection of point}\index{reflection of point}\index{point!reflection on line}\index{mirroring!point to line}
\begin{figure}[H]
\centering
\includegraphics[height=8\baselineskip,keepaspectratio]{figures/mirror.pdf}
\end{figure}
Line $PP'$ will be perpendicular to $L: ax+by+c=0$, meaning they will satisfy the equation $L_{⊥}: bx-ay+(aP_y-bP_x)=0$.\footnote{See \emph{\nameref{ch:perpendicular}}, page \pageref{ch:perpendicular}} We will find the middlepoint $P_m$· $L$ and $L_{⊥}$ intercept at $P_m$, so substituting $L_{⊥}$'s $y$ to $L$ gives:
\begin{align*}
&a\textbf{x} + b\left(\frac{b\textbf{x}+(aP_y-bP_x)}{a}\right)+c=0\\
\implies{}&a\textbf{x} + \frac{b^2}{a}\textbf{x}+bP_y-\frac{b^2}{a}P_x+c=0\\
\implies{}&(a +\frac{b^2}{a})\textbf{x}=\frac{b^2}{a}P_x-c-bP_y\\
\implies{}&\textbf{x}=\left(\frac{\frac{b^2}{a}P_x-c-bP_y}{a +\frac{b^2}{a}}\right)
\end{align*}
\noindent{}$P_{m_{y}}$ is found by substituting $P_{m_x}$ to $L$. Now, knowing $\textrm{length of } PP_m = \textrm{length of } P_mP'$, we can find $P'_x$ and $P'_y$:
\begin{align*}
&P_{m_x}-P_x =P'_x-P_{m_x}\\
&P_{m_y}-P_y=P'_y-P_{m_y}\\
\implies{}&P'_x=2P_{m_x}-P_x\\
&P'_y=2P_{m_y}-P_y
\end{align*}
\section*{The code}
\attachsource{src/bin/mirror.rs}
\begin{minted}{rust}
fn find_mirror(point: Point, l: Line) -> Point {
let (x, y) = point;
let (a, b, c) = l;
let (a, b, c) = (a as f64, b as f64, c as f64);
let b2a = (b * b) / a;
let mx = (b2a * x as f64 - c - b * y as f64) / (a + b2a);
let my = (-a * mx - c) / b;
let (mx, my) = (mx as i64, my as i64);
(2 * mx - x, 2 * my - y)
}
\end{minted}
\begin{figure}[H]
\centering{}
\includegraphics[width=0.5\textwidth,keepaspectratio]{figures/mirror.png}
\Caption{The \texttt{src/bin/mirror.rs} example lets you drag a point and draws its reflection across a line.}
\end{figure}
%
%
%
\section{Find perpendicular to line segment $AB$ that passes through its middle (perpendicular bisector of $AB$)}\label{sec:perp-bisector}
Find midpoint $m_{AB}$ of $AB$:
\begin{align*}
m_{AB} = (\frac{x_a+x_b}{2}, \frac{y_a+y+b}{2})
\end{align*}
Slope of $AB$ is $m_l = \frac{y_b-y_a}{x_b-x_a}$
Slope of perpendicular will be $m_p \times{} m_l \implies{} m_p = \frac{-1}{m_l}$
Perpendicular satisfies line equation $y = mx+c$ and passes through midpoint $m_{AB}$:
$c = y_{AB} - m_p \times{} x_{AB}$.
\begin{minted}{rust}
fn perp_bisector((x_a, y_a): Point, (x_b, y_b): Point) -> (i64, i64, i64) {
let m_a = if x_b != y_b { (y_a - y_b) as f64 } else { -1.0 };
let m_b = (x_b - x_a) as f64;
let (x_m, y_m) = ((x_b + x_a) as f64 / 2.0, (y_b + y_a) as f64 / 2.0);
// slope form y=mx+b
// m_og = (y_m - y_n / x_m - x_n)
// m_og * m = -1 => m = (x_n - x_m) / (y_m - y_n) = m_b / m_a
//
// y = mx+b => y_m = m*x_m + b => b = y_m - m * x_m
//
// slope form y=mx+b -> implicit form αx+βy=γ
// y = m*x + y_m - m* x_m
(
m_b as i64,
-m_a as i64,
(((y_m * m_a) - (m_b * x_m)) as i64),
)
}
\end{minted}
\chapter{Angle sectioning}
\section{Bisection}\index{angle!bisectioning}
\todo[inline]{Add \emph{angle bisectioning}}
\skelpar%
\section{Trisection}\index{angle!trisectioning}
\todo[inline]{Add \emph{angle trisectioning}}
% https://www.geom.uiuc.edu/docs/forum/angtri/
If the title startled you, be assured it's not a joke. It's totally possible to trisect an angle\ldots{} with a ruler. The adage that angle trisection is impossible refers to using only a compass and unmarked straightedge.
\skelpar%
\clearpage{}
\chapter{Drawing a line segment from its two endpoints}
For any line segment with any slope, \pixels{} must be matched with the infinite
amount of points contained in the segment. As shown in the following figure, a segment \emph{touches} some \pixels{}; we could fill them using an algorithm and get a \bitmap{} of the line segment.
\begin{figure}[H]
\centering
\input{figures/fig2.pdf_tex}
\end{figure}
The algorithm presented here was first derived by Bresenham.\cite{bresenham1996}In the \emph{Image} implementation, it is used in the \texttt{plot\_line\_width} method.
% From graphic gems vol 1 p 99 (pdf page 124)
\begin{minted}{rust}
pub fn plot_line_width(&mut self, (x1, y1): (i64, i64), (x2, y2): (i64, i64)) {
/* Bresenham's line algorithm */