tag:blogger.com,1999:blog-74712695454252464222024-03-12T19:56:28.599-07:00Andrew's Technical ThoughtsAndrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-7471269545425246422.post-16848722149816817932014-08-17T22:26:00.002-07:002014-08-17T22:26:25.992-07:00Homemade 3D rendering engine (X)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Final
thoughts, implementing this has been a fun exercise, it is emotionally pleasing
to see theory in practice. I learnt a big deal of these from Dave Mount’s
lecture notes and Computational Geometry for the binary space partitioning
algorithm.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
In
practice, however, this is entirely impractical. With a 30 frames per second
implementation it use up all the CPU time. When generating animation, we have
the clear the screen and draw again, which has poor performance in WPF. BSP
tree need to be built for each frame but not incrementally is also painful,
floating point errors add up, the list goes on and on.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
So
this whole thing is really done for the fun. It could be altered to make a
great exercise for students in Computer Graphics so that they grasp the basic
theory, but don’t really use it.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
A couple more meta-learning I had in this documenting exercise is that:</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
</div>
<ol>
<li>Document the idea now! Documenting it two years from now is a painful exercise to reverse engineer those idea back from code, and</li>
<li>Documenting the idea helps find bugs – case in point is the fourth case in the binary space partitioning tree.</li>
</ol>
<br />
<div style="text-align: justify;">
<br /></div>
<div class="MsoListParagraph" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -.25in; text-justify: inter-ideograph;">
<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-34545721425048528082014-08-17T14:14:00.000-07:002014-08-17T22:26:47.410-07:00Homemade 3D rendering engine (IX)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<div class="MsoNormal">
Now
we have laid out the basics for rendering. Let’s cover other topics that might
be useful to understand the whole game. One problem is event handling, when
user click on a particular cube face, how do I respond to that event? It turns
out to be rather simple, simply register a click event handler on the triangle,
and record the cube face with the triangle, and that’s it. A typical solution
might need to go back to the BSP tree to search from front to back.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
How
about animation? In my game, animation is abstracted under the model. A model
is a collection of triangle, during rendering, if an animation is needed (e.g.
rotating a particular face), a different set of triangles is returned using a
composite pattern. A model is a transform model of the underlying model which
is a cube, which is then a composition of six triangles.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
So
during each rendering, the whole screen is cleared, the set of triangles are
obtained from the composite model, a BSP tree is built, a back to end traversal
is used to determine rendering order, the projection is used to compute 2d
coordinates, and a triangle object is rendered to the screen. <o:p></o:p></div>
<br />
<div class="MsoNormal">
This
conclude the design of the whole system!<o:p></o:p></div>
</div>
<div class="MsoListParagraph" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -.25in; text-justify: inter-ideograph;">
<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-52321324465324616532014-08-17T14:13:00.008-07:002014-08-17T14:13:42.448-07:00Homemade 3D rendering engine (VIII)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
While
the binary space partitioning algorithm is conceptually simple, the
implementation of it is fairly complicated because a lot of details are missing
from the previous discussion. For example, how is the model represented? How do
we choose the plane to split? How to split the model? Apparently, to implement
the algorithm, all these questions has to be answered.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
In
my implementation, a model is a collection of triangles, with vertexes
represented in world’s coordinates. We just pick one triangle (which then
implies a plane) to split, the tricky part are the triangles that cross the
plane need to split, and the computation of that splitting can be fairly
complicated as shown below.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
First,
a plane can be represented by a point and its normal, crossing the two vectors
of the triangle gives the normal. Determine which half-space contains the
camera is straightforward.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Second,
if a triangle’s vertexes are all on the same side of the half-space (the plane
inclusive), we are lucky and just group that triangle in one of the left or
right sub-trees.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Third,
if a triangle’s vertexes are on both sides, there must be one on one side and
two on other side. Determine the lonely one, find the two intersection point on
the plane, that forms a triangle, the rest is a trapezoid which can easily
split into two triangles as well.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<br />
<div class="MsoNormal">
In fact, there is a fourth case, that one on one size, one
on the plane, and one on the other side, in that case we should split into two
triangles. The case was missing in my code and some triangles mysteriously
disappear … <span style="font-family: Wingdings; mso-ascii-font-family: Calibri; mso-ascii-theme-font: minor-latin; mso-char-type: symbol; mso-hansi-font-family: Calibri; mso-hansi-theme-font: minor-latin; mso-symbol-font-family: Wingdings;">L</span><br />
<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-18080857190376052392014-08-17T14:13:00.007-07:002014-08-18T22:44:35.756-07:00Homemade 3D rendering engine (VII)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
The
projection model we discussed above is good enough to produce wire frame
models, where models are lines and are projected to the screen from rendering.
In particular, we do not care about drawing lines that should appear behind
some other lines.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
But
for my purpose, I need to produce a cube with surface painted with colors, I
need to differentiate if the plane is in front of behind, and not draw anything
behind.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
While
the Painter’s algorithm is the most popular algorithm around, it requires too
much memory for my application and I cannot use hardware acceleration, so I
opted not to use that, instead, I have learnt and used the binary space
partitioning tree algorithm. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Let’s
start with defining half-space, a half-space is simply the region of the space
that is above/below a plane. So given a plane, the space is divided into two
half-spaces.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
So
given a plane, we can divide the model into three parts, one that is in the
half space where it contains the camera. One that is exactly on the plane, and
one that is in the other half-space.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Now
it comes a simple divide and conquer strategy. We start with the complex model,
finding a plane to split the model, build a node in the tree with that plane to
represent the split, and three children as the split models. Recursively do it
until it is just one plane, then we stop. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
The
resulting tree is the binary space partitioning tree, given a binary space partitioning
tree, we know that a model appearing in the half-space containing the camera
will always appear in front of the model on the plane, which is on turn appear
in front of the model in the other half-space, so by doing a tree-traversal, we
can render the items from back to front, effectively hiding the items that
should appear on the back.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-89631805788069454542014-08-17T14:13:00.006-07:002014-08-18T22:56:14.211-07:00Homemade 3D rendering engine (VI)<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
After
the detour to mathematics, it’s time to complete the projection. We note
firstly that, the projection we wanted is a function, given the world’s
coordinate, returns the point’s eye’s coordinate.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Remember
we knew the axis of the eye’s coordinate system as vectors in the world’s
coordinate system, it make the inverse problem of the projection easy. Given a
point $ (e_x, e_y, e_z)^T $ in the eyes coordinate system, all we need to do to compute $ (w_x, w_y, w_z)^T $ is to apply the axis as follow:<br />
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: center;">
$\left(\begin{matrix}{w_x\\w_y\\w_z}\end{matrix}\right) = e_x \vec{E_x} + e_y \vec{E_y} + e_z \vec{E_z} + \left(\begin{matrix}{c_x\\c_y\\c_z}\end{matrix}\right)$<br />
<br />
or simply<br />
<br />
$ \vec{w} = (\vec{E_x} \vec{E_y} \vec{E_z})\vec{e} + \vec{c} $<br />
<br />
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
So
all we need to do is to express $ (e_x, e_y, e_z)^T $ in terms of $ (w_x, w_y, w_z)^T $ in the
equation above. Note that the transformation is affine, so we could just form
the 4 x 4 matrix and invert it. But there is an easier way. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Since
$ \vec{E_x} $, $ \vec{E_y} $, $ \vec{E_z} $ is an orthonormal frame, we knew from linear algebra that the matrix
is orthonormal and its inverse is simply its transpose, so we have:<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div style="text-align: left;">
$\begin{eqnarray*}
\vec{w} & = & (\vec{E_x} \vec{E_y} \vec{E_z})\vec{e} + \vec{c} \\
\vec{w} - \vec{c} & = & (\vec{E_x} \vec{E_y} \vec{E_z})\vec{e} \\
\vec{e} & = & \left(\begin{matrix}{\vec{E_x} \\ \vec{E_y} \\ \vec{E_z}}\end{matrix}\right)(\vec{w} - \vec{c})
\end{eqnarray*}$</div>
</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Which
is yet another affine transformation that we can effectively code. Since the
projection matrix doesn’t change much, it make sense to simply compute the
matrix once and cache it for computing projections.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<span style="font-family: "Calibri","sans-serif"; font-size: 11.0pt; line-height: 107%; mso-ansi-language: EN-US; mso-ascii-theme-font: minor-latin; mso-bidi-font-family: "Times New Roman"; mso-bidi-language: AR-SA; mso-bidi-theme-font: minor-bidi; mso-fareast-font-family: 宋体; mso-fareast-language: ZH-CN; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-latin;">Since at the end of the day the screen is 2D, so
what we will do is to simply drop the z-coordinate. </span></div>Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-67411897544011484242014-08-17T14:13:00.005-07:002014-08-18T23:08:03.485-07:00Homemade 3D rendering engine (V)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">At this point, it does not harm for us to extend
the concept of homogeneous coordinates a little bit to fit our purposes. In
particular, for points, let’s define $ (cx, cy, cz, c)^T $ the same as $ (x, y, z, 1)^T $. This is nothing but just mapping the previously unused representation into
a single canonical representation.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">A linear transformation is defined as $ T(a\vec{x} + b\vec{y})
= aT(\vec{x}) + bT(\vec{y}) $, and it is typically represented as a matrix $ T(\vec{x}) = A\vec{x} $.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">A translation is defined as $ T(\vec{x}) = \vec{x} + \vec{v} $,
apparently, translation is not linear as $ T(\vec{0}) = \vec{v} \ne \vec{0} $.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">As we can see, to do the projection, we need
both translation and linear transformation, the fact that translation cannot be
represented as matrix makes computation cumbersome.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">Now the interesting thing happens, with
homogeneous coordinates, we can represent both translation and general linear
transformation as a matrix!<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">To see how, we can represent general linear
transformation as follow<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div align="center" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: center;">
<span style="font-family: Trebuchet MS, sans-serif;">$ \left(\begin{matrix} \mathbf{A} & 0 \\ 0 & 1 \end{matrix}\right) \left(\begin{matrix} \vec{x} \\ 1 \end{matrix} \right) = \left(\begin{matrix} \mathbf{A}\vec{x} \\ 1 \end{matrix}\right) $</span></div>
<div align="center" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: center;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">That’s doesn’t sound particularly useful, we
could have done it without the extra dimension, but this is amazing<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div align="center" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: center;">
<span style="font-family: Trebuchet MS, sans-serif;">$ \left(\begin{matrix} \mathbf{I} & \vec{v} \\ 0 & 1 \end{matrix}\right) \left(\begin{matrix} \vec{x} \\ 1 \end{matrix} \right) = \left(\begin{matrix} \vec{x} + \vec{v} \\ 1 \end{matrix}\right) $<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
</div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<span style="font-family: Trebuchet MS, sans-serif;">This also means we can compose translation and
general linear transformation into a single matrix, these more general
transformations are mathematically called affine transformations, and that’s
what we will use in the projection. Note, however, that by composing the
matrix, it might not be the case that we always ends with having a resulting
point ends with 1, that’s why we need to introduce the homogeneous coordinates.</span><span style="font-family: Times New Roman, serif; font-size: medium;"><o:p></o:p></span></div>
<div class="MsoNormal" style="text-align: center;">
<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-63070844703728975932014-08-17T14:13:00.004-07:002014-08-18T22:49:13.189-07:00Homemade 3D rendering engine (IV)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Once
we have both coordinate systems, we will do the transformation. In order to do
the transformation, let’s start with some basic math. We already know about
points can be represented as its coordinate, now we introduce vector. A vector
is simply an arrow (i.e. its direction) with a length (i.e. its magnitude). It
is floating in the space so we can move it around. Given two points, we can have
a vector, represented as this simple equation:</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div align="center" class="MsoNormal" style="text-align: center;">
Point – Point =
Vector<o:p></o:p></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
So
vector is also just an ordered list of numbers with the same dimension as
points do. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
It
also make sense to play with the vector’s length by scaling it, in particular,
we have this, meaning the length is scaled by s<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
Vector = s (as a
Positive Real Number) * Vector<o:p></o:p></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
As
well as reversing direction<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div align="center" class="MsoNormal" style="text-align: center;">
Vector = -1 * Vector<o:p></o:p></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
For
anyone who knew about vector in their math course, this would sound trivial,
now let’s add some new convention here that is particularly useful. Since
vector and point are both represented as an ordered list of numbers, there is
no way to distinguish points from vectors, which could be a problem, so let’s
add 1 dimension to the list at the end of the list of numbers, with points ends
with 1 and vector ends with 0. Note that if we treat the last dimension just
like any other dimensions, we have a nice type checking property – if the last
dimension is 0 or 1, the operation is valid, otherwise, it isn’t. For example,
it make no sense to add two points by coordinates, so it ends up with a list of
numbers ending with 2. We call this new representation <b>homogeneous coordinates</b> and we’ll see this is particularly useful
later on.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-58119368606861316692014-08-17T14:13:00.003-07:002014-08-18T23:10:09.956-07:00Homemade 3D rendering engine (III)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
We
starts by describing the camera. A typical way of defining the camera is to
define where the center of the camera is, as well as which direction is
pointing upwards. With that information, we can easy compute the surface normal
of the camera as $ \vec{E_z} = (-c_x, -c_y, -c_z)^T $, that will be the z-axis of the camera
coordinate system. Next, we compute $ \vec{E_x} = (\vec{E_z} \times \vec{Up}) $, that gives the x-axis of the
camera coordinate system, finally, we compute $ \vec{E_y} = (\vec{E_z} \times \vec{E_x}) $ to be our y axis, and
we are done with specifying the camera coordinate system. Of course, these
vectors need to be normalized to be an orthonormal basis.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Remember
the point of defining the camera is about defining the camera coordinate
system. We could have use any other ways to describe the camera, this is merely
a conventional way of doing this.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<br />
<div class="MsoNormal">
Suppose we wanted to look at the model from (500, 500, 500),
and the upwards direction as (0, 0, 1), we can compute EZ = (-500, -500, -500), EX = (-500, 500, 0) and EY = (-250000.0, -250000.0, 500000). <o:p></o:p></div>
</div>Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-15061050715037088472014-08-17T14:13:00.002-07:002014-08-17T14:13:19.003-07:00Homemade 3D rendering engine (II)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
The
key to 3D rendering is about being able to describe what we wanted to render in
3D coordinates and draw them on screen. That involves a mapping from the 3D
coordinates (on the world) to the 2D coordinate (on the screen). In this entry
we give an overview on how that can be done.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
First,
it is easy to describe a 3D coordinate system, to be consistent with the
literature, I will use a right-handed coordinate system, meaning the z-axis is
x-axis cross y-axis. With a 3D coordinate system, we can describe the model in
that coordinate system.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Second,
we need to specify how the projection is done. This is key to the construction
of the mapping. Imagine a camera is placed in the world. The camera is simply a
rectangle that represent the screen. Imagine a ray is shoot orthogonal to the
camera rectangle to the model. That is what we will be drawing on the screen.
For simplicity, we assume the camera is outside of the model to be rendered,
and it is assumed to be able to see the whole model through the camera. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Third,
we imagine another coordinate system is defined at the center of the camera.
The camera rectangle provides us with that coordinate system. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Last
but not least, we transform the world coordinates to the camera coordinate, and
then drop the z-axis information, that will be our projection.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
In
the next entries, we will describe in details how that can be done.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-12896449536520160272014-08-17T14:13:00.001-07:002014-08-17T14:13:14.879-07:00Homemade 3D rendering engine (I)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
During
fall 2012, I built a Rubik cube game for Windows Store. For various reasons, I
needed to complete the game quickly. I was a managed code programmer using C#
primarily, and at that time, WinRT does not support 3D rendering on Windows
Store using managed code, so I decided to roll my own. The code worked, but it
has poor performance with respect to current technologies since this is pure
software rendering. Take this as an attempt to write a 3D rendering engine
exercise.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Here
I am documenting the engine I have written. <o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-49163514657847594462014-06-20T09:25:00.003-07:002014-06-20T09:25:58.748-07:00Homemade Internet Service Relay (X)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Ready
for receive? Receive is much more complicated than send. Similar to Send, Read
happens mostly within Connection. As an overview, Connection spread the work
for receive to TransportReceiveActor and ChannelReceiveActor.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
TransportReceiveActor
deals with the data from transport, demultiplex it, and send to
ChannelReceiveActor. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
ChannelReceiveActor
response to Channel ReadRequest by providing data provided by
TransportReceiveActor, after copying back to Channel, ChannelReceiveActor will
response to TransportReceiveActor the data is consumed. This is to free buffer
to allow space for further receives.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Here
is a more detailed view:<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
TransportReceiveActor
maintains a buffer – this buffer is used to store data from TCP transport.
Before this buffer is full, TransportReceiveActor keep requesting transport for
data. This buffer also serve the purpose of choking the sender. Because of we
are at low capacity to process the data, the buffer will remain not empty and
receive will not proceed, effectively stopping sender because its TCP sliding
window is used up. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
After
data arrives in the buffer, TransportReceiveActor decodes them. Decoding is a
simple state machine – read the channel, read the size, read size bytes, and
repeats. However, since data is not available, the state machine must stop when
there is no data, and the state is saved until the next packet arrives. Here
the unread count is increased by the total size of the payload.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
The
decoded payloads are then sent to ChannelReceiveActor, one complication arise
here if the ChannelReceiveActor is not there yet. This is a new channel! There
must be someone else trying to accept the Channel, the payload will be enqueued
in pending accept list. If there are any pending accept request, the accept
request is satisfied. Beyond that, the data will be sent to the
ChannelReceiveActor. <o:p></o:p></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
After
ChannelReceiveActor received the data, it enqueues it into a queue. The queue
is then checked to see if there are any pending read request, and if there is
one, try to fill the buffer and return. After filling the buffer, the used
count is send back to TransportReceiveActor to reduce the unused count. Once
the unused count goes back to 0, transport receive can start again.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-76251490970145387172014-06-20T09:25:00.001-07:002014-06-20T09:25:31.760-07:00Homemade Internet Service Relay (IX)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Writing
data is considerably simpler, so we will start with looking at write.
Channel.Write() simply calls Connection.Write(), so the bulk of the logic is in
Connection. When Connection receive a Write request, it breakdown the request
into frames. Each frame contain a simple header that indicate which Channel it
comes from, and the size of the frame so that it can be decoded later, and the
bulk of the frame is then forwarded to SenderActor for processing. Note that
while frame headers are newly allocated memory blocks, the frames are simply
created using integer indexes so that the buffer is not copied.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
After
receiving frames, SenderActor keeps them in a list of SegmentHandlePairs. A
SegmentHandlePair is a pair of Segment (of data to send) and a Completion
handle to notify the sender the send is completed. Only the last frame has the
segment handle pair attached. Normally it will just send the data through the
socket, but it must be careful not to do it when the last sending is in
progress. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
On
writing to transport completed, TCP will give us a notification how many bytes
are written. SenderActor will receive this notification and then go back to the
segment handle pairs. A scanning of the list will be done to see if there are
completion handle to update. It is quite probable that not all data are sent,
in that case we need to update the list with the right index, and then request
the send to transport again.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
These
logic are best illustrated by an example. For simplicity, the frame size is 8
and the channel id/size take 1 byte.<o:p></o:p></div>
<table border="1" cellpadding="0" cellspacing="0" class="MsoTableGrid" style="border-collapse: collapse; border: none; mso-border-alt: solid windowtext .5pt; mso-padding-alt: 0in 5.4pt 0in 5.4pt; mso-yfti-tbllook: 1184;">
<tbody>
<tr>
<td style="border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; padding: 0in 5.4pt 0in 5.4pt; width: 647.5pt;" valign="top" width="863">
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Write request with
10 bytes comes from channel 1<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
1 2 3 4 5 6 7 8 9 10<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
The data are packed
into frames<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
[Channel 1, Size 8]
1 2 3 4 5 6 7 8 [Channel 1 Size 2] 9 10<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
The frames are sent
to SenderActor, sender Actor marks the last segment with the completion
handle<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
[Channel 1, Size 4]
1 2 3 4 [Channel 1 Size 4] 5 6 7 8 [Channel 1 Size 2] <b>9 10</b><o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Sender Actor send
these to the transports<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Write request with 7
bytes comes from Channel 2 <o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
The data are packed
into frames<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
[Channel 2, Size 7] A
B C D E F G<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
[Channel 1, Size 4]
1 2 3 4 [Channel 1 Size 4] 5 6 7 8 [Channel 1 Size 2] <b>9 10 </b>[Channel 2, Size 7] A B C D E F G<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Sender Actor can’t
send the data yet because it is transport write in progress.<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Transport reports 11
bytes are written<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Sender Actor updates
its data structure<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<s>[Channel 1, Size
4] 1 2 3 4 [Channel 1 Size 4] 5 6 7</s> 8 [Channel 1 Size 2] <b>9 10 </b>[Channel 2, Size 7] A B C D E F
G<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Sender Actor realize
there are more data to send, so it request transport to send these again.<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Transport reports 6
bytes are written<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Sender Actor updates
its data structure<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
<s>8 [Channel 1 Size
2] <b>9 10 </b>[Channel 2</s>, Size 7] A
B C D E F G<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Sender Actor knows
it needs to notify a completion handle a send is completed.<o:p></o:p></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: justify;">
Sender Actor realize
there are more data to send, so it request transport to send these again.<o:p></o:p></div>
</td>
</tr>
</tbody></table>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Hopefully
one can appreciate how actor makes the concurrency issue trivial here. If we
had to deal with concurrency here it would be more complicated. With
SenderActor, we can happily ignore the fact that the Channels and transport are
concurrent because we are processing the messages one by one, the data
structure need no locks.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-91878579468118037702014-06-20T09:24:00.001-07:002014-06-20T09:24:03.028-07:00Homemade Internet Service Relay (VIII)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Now
we switch to the highest level of abstraction that we provides. To use the
library, the client must first establish a TCP connection, and then constructs
a Connection object.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> Connection(</span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">Socket</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> socket, </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">ConnectionType</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> connectionType)</span><span style="font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><o:p></o:p></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Since
the connection is shared, one cannot send/receive data through the Connection
directly, instead, one create Channels. On the client side (i.e. initiator), he
can simply create a channel by calling Connect. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">Channel</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> ConnectChannel()</span><span style="font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><o:p></o:p></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Unlike
TCP, the call is synchronous because the connection is already established.
Currently we do not check if the other side is ready to accept this connection,
we simply assumes the server eventually will. <span style="background: yellow; mso-highlight: yellow;">This could be improved in the future</span>.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
On
the other hand, the server side will need to wait for a Channel establishment
request, this is done by calling Accept<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">IAsyncResult</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> BeginAcceptChannel(</span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">AsyncCallback</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> callback, </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">object</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> state)<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">Channel</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> EndAcceptChannel(</span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">IAsyncResult</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> ar)</span><o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
This
call is necessarily asynchronous not because it involves I/O, but because it
blocks on waiting. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Channel
itself is just a Stream. This design make it very easy for other stream
processing code (e.g. serialization) to use the library without modification.
In addition, it provides a teardown that stop sending data to model TCP one-way
shutdown.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">void</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> StopSending()<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">IAsyncResult</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> BeginStopSending(</span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">AsyncCallback</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> callback, </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">object</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> state)<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">void</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> EndStopSending(</span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">IAsyncResult</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> ar) <o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; mso-highlight: white;">Task</span><span style="background: white; font-family: Consolas; font-size: 9.5pt;"> StopSendingAsync()</span><o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<span style="font-family: "Calibri","sans-serif"; font-size: 11.0pt; line-height: 107%; mso-ansi-language: EN-US; mso-ascii-theme-font: minor-latin; mso-bidi-font-family: "Times New Roman"; mso-bidi-language: AR-SA; mso-bidi-theme-font: minor-bidi; mso-fareast-font-family: 宋体; mso-fareast-language: ZH-CN; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-latin;">In the next post we will talk about how the
connector work inside.</span></div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com1tag:blogger.com,1999:blog-7471269545425246422.post-64858786725847125602014-06-20T09:23:00.001-07:002014-06-20T09:23:01.965-07:00Homemade Internet Service Relay (VII)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
As
with any networking textbook, we could go top down or bottom up. To give the
journey an overview, we talk about the lowest level (i.e. TCP transport)
abstraction that we use and the highest level abstraction we provide for
caller. Interesting reader will then get a sense what could be in the middle.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
The
abstraction we use from TCP transport is the Sockets API, in particular, these
few calls are used.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">IAsyncResult</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> BeginReceive(</span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">byte</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;">[] buffer, </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">int</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> offset, </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">int</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> size, </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">SocketFlags</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> socketFlags, </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">AsyncCallback</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> callback, </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">object</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> state);</span><o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">public</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">IAsyncResult</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> BeginSend(</span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">IList</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><</span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">ArraySegment</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><</span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">byte</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;">>> buffers, </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">SocketFlags</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> socketFlags, </span><span style="background: white; color: #2b91af; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">AsyncCallback</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> callback, </span><span style="background: white; color: blue; font-family: Consolas; font-size: 9.5pt; line-height: 107%; mso-highlight: white;">object</span><span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"> state);</span><span style="font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><o:p></o:p></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span style="background: white; font-family: Consolas; font-size: 9.5pt; line-height: 107%;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
The
establishment/teardown of the socket (i.e. TCP bind/listen/accept/connect/close)
is outside of the scope of this library, this library simply assumes one.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Note
that we use a complicated variant for the send method. The flexibility of the
sockets API to read from discontinuous regions to send data allows me to avoid
copying data frames comes from various data streams.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<br />
<div class="MsoNormal">
<span style="background: yellow; mso-highlight: yellow;">The
current version ignored transport errors – a huge mistake – we should improve
it</span>.<br clear="all" style="mso-special-character: line-break; page-break-before: always;" />
<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-82755744294648640422014-06-20T09:22:00.004-07:002014-06-20T09:22:26.415-07:00Homemade Internet Service Relay (VI)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Before
we proceed to the detailed design of the service, I must confess I screwed up
in the initial versions. I underestimate how difficult it is to code this up. On
one hand, there isn’t much logic at all, this is not graph matching algorithm,
or assembly hacking techniques. On the other hand, there are many threads, and
at any time there are incomplete messages, and error conditions. Complexity
grows exponentially when all these get coupled together. We must decouple them.
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
My
first revision involves re-thinking about concurrency. At its core our concurrency
problem is about shared mutable states, and if we can be sure no such thing
existed, we can freely code without concerning about concurrent edits. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Think
about the human world, everyone thinks at the same time, that’s okay because
brains are not shared, they don’t interfere. When a group of people work
together, they talks and listen, and that message is shared. However, it is
immutable and is therefore also safe. We can model our computation as such. Actors
are objects that receives message, access it only by reading it, and can freely
modify its own state. They can also send messages, but they never reach each
other directly without going through messages. That way we can guarantee the no
shared mutable state guarantee. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
In
typical actor system implementation – such as Akka, these constraints (e.g.
always send message, don’t call methods, messages are immutable) are enforced
by the framework though various means (e.g. encapsulating the actor object
instances, staying immutable in a functional language, serializing the
message), but in mine, it is only the spirit that is important. I enforced
these constraint simply by following them myself, this is done so because they
is no need to invest in a framework, and in general that is more performant.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Each
actor is simply modeled as a concurrent safe queue of messages called a
mailbox, each actor override the OnReceiveMessage() method to respond to the
message object, make sure it don’t modify the message object, and that’s it.
When a message is sent to an actor, if the actor is not already processing a
message, a thread is requested from the ThreadPool and will call the
OnReceiveMessage() on it.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Last
but not least, an actor can voluntarily terminate itself, which is done by
returning ActorContinuation.Done in the OnReceiveMessage call, otherwise the
actor should return ActorContinuation.BlockOnReceive to get itself ready to
process another message.<o:p></o:p></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
With
this programming model, I can focus on the next level without worrying about
concurrency now.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-75647057989776312452014-06-20T09:21:00.003-07:002014-06-20T09:21:34.804-07:00Homemade Internet Service Relay (V)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
To
achieve high performance, my implementation do two things. Asynchronous I/O and
no redundant copies.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
First,
it never block any threads on I/O requests. This can reduces resource
consumption. When multiple requests arrives when all threads are in use
(blocked or not), requests need to be served by new threads. Thread creation
takes significant amount of time. If we eliminate the possibility that a thread
is blocked on I/O, we significantly decrease the need for thread creation.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Practical
experience is, if you can make sure the server don’t block on I/O for all
operations within a request, then we can save significant amount of time. But
if some operation block on I/O anyway, then we are essentially in the situation
of having one thread per request, and doing asynchronous I/O will be
meaningless. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Another
observation is that copying of the data take significant amount of time as most
of the relay is handshaking the messages and very little other processing. The
design attempts to reduce to amount of copy to minimum, except from the stream abstraction
we are required to copy the data to the user specified buffer, which we cannot
avoid if we wanted to reuse the same abstraction.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-8065587511415246232014-06-20T09:20:00.003-07:002014-06-20T09:20:40.686-07:00Homemade Internet Service Relay (IV)<div dir="ltr" style="text-align: left;" trbidi="on">
Once I started with the implementation, difficulty arise when we have more than one connection. There is just one TCP connection between the internal networks and there are more than one connections between the external world and the internal service. Clearly there is a need to multiplex more than one connections into a single connection. The situation is very much like multiple TCP connections are multiplexed a single piece of network cable.<br />
<br />
When multiple TCP connections use the same network cable, the input is broken down into multiple packets. At any time, only one packet got written to the cable. On the receiving end, the network pick up the packet, look at the header, and dispatch the packet to the right connection by port number.<br />
<br />
In our case, we will design our multiplexing the same way. First, we define streams. Streams are simply a user-level connection, being multiplexed on top of the underlying TCP connections. Each stream break down its input into frames (similar to an IP packet), and then they are sent through the connection. On the receiving end, the packets are received and re-assemble into a data stream.<br />
<br />
Streams are created when a new stream ID is sent. On the receiving a new stream ID a new stream object is created if there are pending accepts. The programming model is the same as normal TCP programming.<br />
<div>
<br /></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-27084053741813202252014-06-20T09:19:00.002-07:002014-06-20T09:19:46.500-07:00Homemade Internet Service Relay (III)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Instead
of relaying messages, we can relay connections. This way the relay is
completely agnostic to whatever the service is doing, which is good because
that will allow a wide range of services to be relayed without being known or modified
at all. Case in point could be Remote Desktop. We couldn’t possibly change
remote desktop, or we are interested in knowing the details of the protocol.
But if we relay the whole connection, we can make it possible to relay any
service on top of TCP.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
With
just a tiny twist from above, this can be easily done.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
1) The relay client service, live in the internal network, make a TCP
connection to the Azure relay server service.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
2) The Azure relay server service make itself available to the Internet.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
3) When Azure relay server service receives a connection, it sends to the relay
client service through the connection it established.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
4) The relay client service connects to the internal service<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
5.1) If the Azure relay server service receive a message, it sends to the relay
client service and the relay client service send to the connection. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
5.2) If the relay client service receive a message, it sends to the Azure relay
server services and the Azure relay server services send to the client.<o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
6.1) If the Azure relay server service receive a connection close, it sends to
the relay client service and the relay client service close the connection. <o:p></o:p></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Step
6.2) If the relay client service receive a connection close, it sends to the
Azure relay server service and the Azure relay server service close the
connection. <o:p></o:p></div>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
That
is something I wanted to build.<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-33080640039042373802014-06-20T09:18:00.004-07:002014-06-20T09:18:37.148-07:00Homemade Internet Service Relay (II)<div dir="ltr" style="text-align: left;" trbidi="on">
The key idea to make service hosted in an internal network available through the Internet is to allow the external world to send a message actively and get a response. Normally this is done by the external world to connect to the service through a new TCP connection and the service accepts, but this is frequently impossible because it is blocked by the firewall.<br />
<br />
However, most internal network do NOT block their user from connecting to somewhere else, for example, to browse the Internet. This creates an opportunity. TCP connections are actually full duplex, meaning that once a connection is established, either side can initiate to send a message. Here we will demonstrate how that can be leveraged to create an illusion that the internal network is available.<br />
<br />
Step 1) The internal service make a TCP connection to the Azure service.<br />
<br />
Step 2) The Azure service make itself available to the Internet.<br />
<br />
Step 3) When Azure receives a message, it sends to the internal service through the connection it established.<br />
<br />
Step 4) When Internal Service processing completes, it sends the response to Azure through the connection is established.<br />
<br />
Step 5) When Azure receives the message, it send the client as a response.<br />
<br />
Overall, to the client, it looks just like Azure is the internal service.<br />
<div>
<br /></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-18207075353524603172014-06-20T09:17:00.003-07:002014-06-20T09:17:49.105-07:00Homemade Internet Service Relay (I)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
Inspired
by the Service Bus Relay – I am interested in building a relay myself utilizing
the same basic principle. In the coming series of posts, I will document how I
build a usable Internet Service Relay leveraging Azure – stay tuned.</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<o:p></o:p></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7471269545425246422.post-67470621234091132582014-06-20T09:17:00.000-07:002014-06-20T09:17:15.341-07:00Andrew Technical Blog is now open<div dir="ltr" style="text-align: left;" trbidi="on">
Sometimes, I have some idea and got it implemented, but very often, the implementation is either lost or saved somewhere, but the reasoning about that idea is lost.<br />
<br />
This is unfortunate – because sometimes those are good ideas.<br />
<br />
This blog is used to save those reasoning in terms of blog posts. I hope this can be good for my future reference, as well as sharing those ideas to others.<br />
<br />
My ideas are quite diverse, so there is not a single thing (or theme) that covers them. This is not a distributed system blog, or a game programming blog, but just a general blog that talks about various ideas.<br />
<div>
<br /></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0