A few useful (for me) Erlang functions for 3D work

Here are some functions I have written for working with 3D points, vectors and angles. If you spot any issues, please let me know.

/*
Copyright (c) 2011, 2012 Julian Richardson

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

spherical_cartesian( { Phi, Theta, R } ) ->
    { R*sin(Phi)*cos(Theta), R*cos(Phi), R*sin(Phi)*sin(Theta) }.

cartesian_spherical( { X, Y, Z } ) ->
    R = math:sqrt(X*X+Y*Y+Z*Z),
    S = math:sqrt(X*X+Z*Z),
    AZS = if S > 0.0 -> math:asin(Z/S) ; true -> 0.0 end,
    { math:acos(Y/R), if 0.0 =< X -> AZS ; true -> math:pi() - AZS end, R }.

rotate_about_Z(Phi, V) ->
    RotationByPhiAboutZ = { { cos(Phi), sin(Phi), 0.0 }, % was -sin(Phi)
                            { -sin(Phi), cos(Phi), 0.0 }, % was sin(Phi)
                            { 0.0, 0.0, 1.0 } },
    mvmul3(RotationByPhiAboutZ, V).

rotate_about_Y(Theta,V) ->
    RotationByThetaAboutY = { { cos(Theta), 0.0, -sin(Theta) },
                              { 0.0,      1.0, 0.0 },
                              { sin(Theta), 0.0, cos(Theta) } },
    mvmul3(RotationByThetaAboutY, V).

mvmul3( { { A, B, C },
          { D, E, F },
          { H, I, J } },
        { K, L, M } ) ->
    { A*K+B*L+C*M, D*K+E*L+F*M, H*K+I*L+J*M }.

mmmul3( { { A, B, C },
          { D, E, F },
          { H, I, J } },
        { { K, L, M },
          { N, O, P },
          { Q, R, S} } ) ->
    { { A*K+B*N+C*Q, A*L+B*O+C*R, A*M+B*P+C*S },
      { D*K+E*N+F*Q, D*L+E*O+F*R, D*M+E*P+F*S },
      { H*K+I*N+J*Q, H*L+I*O+J*R, H*M+I*P+J*S } }.

smmul3(X, { A, B, C })  ->
    { svmul3(X, A), svmul3(X, B), svmul3(X,C) }.

mdet3( { { A, B, C },
         { D, E, F },
         { G, H, I } } ) ->
    A*E*I+B*F*G+C*D*H-A*F*H-B*D*I-C*E*G.

svmul2(S, {X,Y}) ->
    {S*X,S*Y}.

vvplus2({A,B},{C,D}) ->
    {A+C,B+D}.

vvminus2({A,B},{C,D}) ->
    {A-C,B-D}.

vvplus3({A,B,C},{D,E,F}) ->
    {A+D,B+E,C+F}.

vvminus3({A,B,C},{D,E,F}) ->
    {A-D,B-E,C-F}.

mvmul2({{A,B},{C,D}},{X,Y})->
    {A*X+B*Y,C*X+D*Y}.

svmul3(S,{X,Y,Z}) ->
    {S*X, S*Y, S*Z}.

normv3(V) ->
    svmul3(1/len(V),V).

len({X,Y,Z}) ->
    math:sqrt(X*X+Y*Y+Z*Z).

vdot2({A,B},{C,D}) ->
    A*C+B*D.

vdot3({A1,A2,A3},{B1,B2,B3}) ->
    A1*B1+A2*B2+A3*B3.

mid3() ->
    { { 1.0, 0.0, 0.0 },
      { 0.0, 1.0, 0.0 },
      { 0.0, 0.0, 1.0 } }.

crossProduct3( { A1, A2, A3 }, { B1, B2, B3 } ) ->
    { A2*B3-A3*B2, A3*B1-A1*B3, A1*B2-A2*B1 }.

vlen3(V) ->
    math:sqrt(distancev3(cartesian, V, { 0.0, 0.0, 0.0 } )).

vlen4({ X, Y, Z, W }) ->
    math:sqrt(X*X+Y*Y+Z*Z+W*W).

qlen(Q) ->
    vlen4(Q).

qnorm(Q) ->
    S = qlen(Q),
    { X, Y, Z, W } = Q,
    { X/S, Y/S, Z/S, W/S }.

angle_between(V1,V2) ->
    math:acos(vdot3(normv3(V1),normv3(V2))).

axis_angle_to_quaternion(V,Angle) ->
    { Ax, Ay, Az } = normv3(V),
    SinA = math:sin(Angle/2.0),
    CosA = math:cos(Angle/2.0),
    qnorm({ Ax*SinA, Ay*SinA, Az*SinA, CosA }).

quaternion_to_matrix(Q) ->
    { X, Y, Z, W } = Q,
    { { 1 - 2 * (Y*Y+Z*Z), 2 * (X*Y + Z*W), 2 * (X*Z - Y*W) },
      { 2 * (X*Y - Z*W), 1 - 2 * (X*X+Z*Z), 2 * (Y*Z + X*W) },
      { 2 * (X*Z + Y*W), 2 * (Y*Z-X*W), 1 - 2 * (X*X+Y*Y) } }.

New open source iOS search project SearchTouch

I just released the first version of SearchTouch, hosted on Github at https://github.com/spoogle/SearchTouch. This is a search engine written in Objective C which compiles and runs on Mac OS X or iOS. It is designed to allow searches to be efficiently carried out on a device.

The code builds an index for a document set consisting of an inverted index for each word in a document set. The index can be stored on the device, and can be efficiently searched to produce a ranked list of every document which contains all of any given set of search terms.

There is a strict separation between the search and indexing code, and the data structures used to store indexes. This separation is mainly achieved by defining the Index class as a class cluster, although a prototcol is also used.

The main storage backend uses Core Data. There is a second back end which is purely in memory using CFTrees.

My take on RIM

RIM is obviously in deep trouble. It’s stock price has fallen 75% in the last year and it just lost its dual CEO’s.

The value in RIM has always been twofold:

  • its technology: back end, phone OS, buy especially secure email and messaging.
  • its customer base

Its technology has failed to keep pace with innovation in iPhone and Android phones, and now in tablets. Its user base has been steadily eroded. I don’t know by how much.

Going forward, RIM’s value depends on how well it can retain its customer base, and how well it can dramatically improve its technology. Retaining its customer base relies on improving the technology, so in the end it is all about the technology.

There are two possible routes to take with the technology:

  • Follow the example of Nokia and others and ditch its proprietary OS in favour of Android or Windows OS. I don’t think that this way it retain anywhere near the revenue it needs to support its market cap. In addition, it would be a lot of work to integrate RIM’s proprietary network into another OS – it’s deep stuff.
  • Double down on its own technology. I think this is the way to go.

So, my advice to RIM is: double down on your technology. Use some cash or sell some assets to hire a wonder-team of developers and product people.

git

I started using version control using SCCS – a single user version control system. Then I moved to CVS, which almost made me through a CRT monitor out of a 3rd floor window. Then came SVN and that was better. Now I am using git. Since git’s version control model is distributed, it is taking bit of getting used to.

I found this succinct tutorial, which nicely explains commits, branches, staging etc.

Today I need to add a branch to a project, but I have already made some uncommitted changes. I need the stash.

That is all.

Not abusing UIViewControllers

I having been mulling for a while an interesting conundrum. I have some code, which is designed to work as a library. It makes no assumptions about any view controller which is active when it is used, and so directly adds things to the view using addSubview: on the application’s main window (view). The initial problem with this approach is that the newly added views have no view controller.

I fixed that by defining a view controller with an appropriate view, but then how to get that displayed. Without any assumptions about the context in which the code is used, the best I could do was instantiate the view controller and then add its view as a subview of the application’s main window as before. An immediate undesirable I discovered was that the new view controller’s viewDidLoad: was never called.

After some fishing around, I found a few useful articles:

Abusing UIViewControllers – presents the case that you should NOT do what I initially do above, force the new view controller’s view into the view hierarchy.

Writing high-quality view controller containers – discusses the same problem and how to write custom view controllers which manage multiple view controllers, like the iOS SplitViewController.

The solution I am going to adopt now is to require the code calling the library to provide a view controller onto which the new view can be pushed using pushModalViewController:

Caching 3D Printing Production for Economies of Scale

3D printed object made with netfabb
Image by Creative Tools licensed under Creative Commons Attribution 2.0 Generic (CC BY 2.0).

In a recent piece in Locus Magazine, Cory Doctorow discusses the economic and copyright consequences of a manufacturing model in which 3D printing enables production runs of zero, tens, thousands or millions of objects. The article mentions that the limited production capacity of 3D printing companies makes large production runs troublesome, but there is another problem with the economics of this kind of mass production: 3D printing is still quite expensive, and there are not significant economies of scale. The main cost driver for 3D printing is probably machine time, and printing a thousand model rabbits requires a thousand times as much machine time as printing one.

In large scale search – and many other internet services and computational domains – have a similar problem: computing a result can be quite expensive. Perhaps 3D printing services should adopt the same solution used in search (computation): caching. In caching, the results for commonly submitted queries (computations) are stored in a cache. Future results for a cached query can then be generated cheaply by returning copies of the cached result rather than rerunning the expensive computation needed to generate a result from scratch. Without such caching, search and other large scale internet services would be very significantly (3x-10x?) more expensive.

Maybe companies like Shapeways which operate a 3D printing service could use caching to significantly reduce costs? When a sufficient number of orders for an object have been made – or are anticipated – they print a mold, and produce future copies from the mold(s) rather than on the 3D printers. Just as in computational world, such caching could be performed entirely behind the scenes, and just as in the computational world, it could significantly reduce the cost producing commonly requested objects.

Casting is already a limited part of the 3D production process – on Shapeways, silver objects are exclusively produced using lost-wax casting.

As a footnote, perhaps what draws me to both 3D printing and computer science is the shared computational aspect. One of my current 3D projects concerns an object which is entirely procedurally (computationally) generated. So far that has required about two weeks of Erlang programming for a custom extension to Wings3d.

Vertex and face data structures in Wings3d

I could not find this information clearly stated anywhere else, so for the record, I will describe the Wings3d vertex and face data structures here. I did find some useful information about datastructures in this post on How To Write Wings3D Plugins (for beginners), but it was not complete. Note, I am NOT describing the winged edge data structure. That is something else which Wings3d uses internally to represent geometry data.

  • vertex: a triple of real numbers, {X, Y, Z}. When building a shape in a plugin, the vertices of the shape are enumerated in a list. Note, integers are not acceptable. Coordinates must be expressed as floating point numbers, e.g. 0.0 instead of 0.
  • face: a list of indexes of vertices in a vertex list. Vertexes must be enumerated ANTICLOCKWISE when viewed from OUTSIDE the constructed shape

A good concrete example is given by the code for constructing a cube:

Faces = [[0,3,2,1],[2,3,7,6],[0,4,7,3],[1,2,6,5],[4,5,6,7],[0,1,5,4]],
Vertices = [{-Xi,-Yi,Zi},{-Xi,Yi,Zi},{Xi,Yi,Zi},{Xi,-Yi,Zi},
{-Xi,-Yi,-Zi},{-Xi,Yi,-Zi},{Xi,Yi,-Zi},{Xi,-Yi,-Zi}],

The first face, [0,3,2,1] is the front one in the following drawing:

wings3d face orientation
Front face of cube

Note the directions of the axes – if +Y is up and +X is right, then +Z is towards the viewer. If you get the direction of the Z axis wrong in your code, then all the normals will be flipped.

The mental wanderings of Julian Richardson