Introduction

The use of rust language in major companies is increasing and with it also the game dev community is growing.

New libraries are published almost weekly and, with enough patieance, it’s already possible to build a high-quality game. The open-world RPG Veloren is a notable example.

Pushed by some recently published, impressive games such as TLOU2 and Cyberpunk 2077 I decided to invest again part of my free time in gamedev experiments and to try out the new Bevy game engine.

Bevy is an ECS-based, 2D and 3D game engine currently under development, but it provides already many features for a simple game.

In this post, we will build a simple terrain visualization, while also exploring some of Bevy’s capabilities

Generating a mesh from a heightmap

Usually, terrain is described by a heightmap, usually a squared, grayscale image where each pixel encodes the height of the terrain at (x, z) coordinates

(note: we will work in a Y-up world).

Example Heightmap from Wikipedia

Our application will load the image and turn the heightmap into a mesh.

The simplest approach for doing this would be to partition a plane with a simple pattern of triangles, where the y component of each vector is sampled from the heightmap:

Simple triangle partition

For instance, by applying this approach on the simple heightmap on the left, we obtain the mesh on the right:

1
2

pub fn rtin_build_terrain_from_heightmap(
    heightmap: &HeightMapU16, error_threshold: f32) -> TerrainMeshData

1
2
3
4

pub struct TerrainMeshData {
   pub vertices: Vec::<Vec3>,
   pub indices: Vec::<u32>
}

1
2
3
4
5

let mut mesh = if enable_wireframe {
    Mesh::new(PrimitiveTopology::LineList)
} else {
    Mesh::new(PrimitiveTopology::TriangleList)
};

1
2
3

let mut vertices : Vec::<[f32; 3]> = Vec::new();
let mut indices : Vec::<u32> = Vec::new();
let mut colors  : Vec::<[f32; 3]> = Vec::new();

1
2
3
4
5
6
7
8
9

for vertex in &terrain_mesh_data.vertices {
    vertices.push([vertex.x, vertex.y, vertex.z]);

    let color = grad.get(vertex.y);
    let raw_float : Srgb::<f32> =
        Srgb::<f32>::from_linear(color.into());
    colors.push(
        [raw_float.red, raw_float.green, raw_float.blue]);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

if enable_wireframe {
    for i in 0..triangle_number {
        // three line for each triangle, 
        // we specify start index and end index of each line
        // (we are ignoring the duplicated lines ofc)
        for j in &[0, 1, 1, 2, 2, 0] {
            indices.push(terrain_mesh_data.indices[i*3+j]);
        }
    }
} else {
    for i in 0..triangle_number {
        // three vertex for each triangle
        for j in 0..3 {
            indices.push(terrain_mesh_data.indices[i*3+j]);
        }
    }
}

1
2
3
4
5
6
7
8

mesh.set_attribute(
    Mesh::ATTRIBUTE_POSITION,
    VertexAttributeValues::Float3(vertices));
mesh.set_attribute(
    TerrainMaterial::ATTRIBUTE_COLOR,
    VertexAttributeValues::Float3(colors)
);
mesh.set_indices(Some(Indices::U32(indices)));

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

#[derive(RenderResources, Default, TypeUuid)]
#[uuid = "0320b9b8-b3a3-4baa-8bfa-c94008177b17"]
pub struct TerrainMaterial {
}

impl TerrainMaterial {
    pub const ATTRIBUTE_COLOR: &'static str = "Vertex_Color";
}


pub fn add_terrain_pipeline(
    mut pipelines: ResMut<Assets<PipelineDescriptor>>,
    mut shaders: ResMut<Assets<Shader>>,
    mut render_graph: ResMut<RenderGraph>
) -> Handle<PipelineDescriptor> {

    // Create a new shader pipeline
    let pipeline_handle = pipelines.add(PipelineDescriptor::default_config(ShaderStages {
        vertex: shaders.add(Shader::from_glsl(ShaderStage::Vertex, VERTEX_SHADER)),
        fragment: Some(shaders.add(Shader::from_glsl(ShaderStage::Fragment, FRAGMENT_SHADER))),
    }));

    // Add an AssetRenderResourcesNode to our Render Graph. This will bind TerrainMaterial resources to our shader
    render_graph.add_system_node(
        "terrain_material_node",
        AssetRenderResourcesNode::<TerrainMaterial>::new(true),
    );

    // Add a Render Graph edge connecting our new "terrain_material_node" node to the main pass node. This ensures "terrain_material_node" runs before the main pass
    render_graph
        .add_node_edge(
            "terrain_material_node",
            base::node::MAIN_PASS,
        )
        .unwrap();

    pipeline_handle
}

1

let terrain_shaded_mesh_handle : Handle<Mesh> = meshes.add(terrain_shaded_mesh);

1
2
3
4
5

#[derive(Default)]
pub struct TerrainMeshResource {
    pub shaded: Handle<Mesh>,
    pub wireframe: Handle<Mesh>,
}

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

pub fn switch_mesh_system(
    keyboard_input: Res<Input<KeyCode>>,
    // query for selecting the entity with the terrain mesh
    mut terrain_query: Query<(Entity, &mut Handle<Mesh>, &Terrain)>,
    // resource for accessing the shaded and wireframe mesh handles
    terrain_mesh_res: Res<TerrainMeshResource>,
    commands: &mut Commands,
) {

    let new_mesh_handle =
        if keyboard_input.just_pressed(KeyCode::N) {
            Some(terrain_mesh_res.shaded.clone())
        } else if keyboard_input.just_pressed(KeyCode::M) {
            Some(terrain_mesh_res.wireframe.clone())
        } else {
            Option::None
        };

    if(new_mesh_handle.is_some()) {
        let handle = new_mesh_handle.unwrap();
        for (entity, mut mesh, _terrain) in terrain_query.iter_mut() {
            commands.remove_one::<Handle<Mesh>>(entity);
            commands.set_current_entity(entity);
            commands.with(handle.clone());
        }
    }
}

1
2
3
4
5
6
7
8
9
10

commands
    .spawn(MeshBundle {
        mesh: terrain_mesh_res.shaded.clone(),
        render_pipelines: RenderPipelines::from_pipelines(
            vec![RenderPipeline::new(pipeline_handle,)]),
        transform: Transform::from_translation(
            Vec3::new(0.0, 0.0, 0.0)),
        ..Default::default()
    })
    .with(Terrain{})

1
2
3
4
5
6
7

pub fn switch_mesh_system(
    //...
    mut terrain_query: Query<(Entity, &mut Handle<Mesh>, &Terrain)>,
    // ...
) {
    // ...
}

I am currently looking for a used car, old but good enough for lasting a few years.

Since I never owned a car, and I lack the anecdotal experience of the car market that many people have, I am likely going to buy a lemon.

Well, let me try to buy a cheap lemon at least.

Autoscout24

I think autoscout24.it is the eBay of used cars in Italy. The website lists many offers from car dealerships and private sellers, with powerful search functionality and a nice looking, website free of ads.

Autoscout24 does offer a RESTful API, but it seems targeted to dealerships.

The best way for getting the data would be to find out how the website or the mobile app uses the API. This is what you want to do if you want to build a program that lasts for more than a few months. However, this could take some time since it involves inspecting the traffic and possibly some reversing.

Let’s look at one page from the website instead:

That’s it. A simple table with the details we need. That’s really easy to parse with xpath.

How does the search work? You can choose many fields:

Let’s run the search and inspect the url:

1

https://www.autoscout24.it/lst?sort=standard&desc=0&offer=U&ustate=N%2CU&lon=7.683066&lat=45.068375&zip=Torino&zipr=10&cy=I&priceto=5000&pricefrom=2500&kmto=200000&kmfrom=10000&fregfrom=2010&atype=C

all the query parameters are nicely listed in the url. We can easily run any query.

Scrapy

Scrapy is a well-designed python framework for scraping. It provides all the functionalities you need while taking care of the boilerplate code.

You can use its shell to quickly play with xpath and css selectors. Just start it with an url:

1

scrapy shell 'https://www.autoscout24.it/annunci/volkswagen-polo-1-2-5p-trendline-benzina-nero-9c1c630f-ce6a-4d3a-b81b-be36702e318b'

and you get an IPython environment where the webpage result is ready to be processed.

Once you find out how to get the data you need from the page, you write a Spider. The core of a Spider is just a single parse() function, where you process the response of a GET request.

parse() conveniently uses the yield mechanism for processing each page. After extracting the data, you yield a simple dictionary (representing a single car in our case). This dictionary is appended to a designed output file (e.g. a simple csv). Then, you yield a new GET request so that you will process the next pages.

Less than 200 lines of python are enough for creating a dataset from autoscout.

Preview of the Dataset

I would have preferred to use Julia for this job, but there are no good scraping libraries currently. So, I will just use it for the data analysis part.

Let’s look at the dataset:

As you can see, I am interested in just a few properties: price, mileage (km), matriculation date, fuel, etc. There is some missing data, we will deal with it later. The dataset includes about 2000 vehicles from sellers in Turin.

I selected gasoline or LPG vehicles due to traffic restrictions rules in my city. I don’t really care about horsepower or model. Any 10 years old vehicle in the low price range will work for me. However, I will try to use many parameters for building a proper model for price prediction. Every time I will find a car I like, I will compare its price against the predicted one.

Actual analysis will be performed in the next post. Prepare yourself for a heavily technical post full of pie charts and linear regressions.

You can find the scraper code here.

Update 2021-04-01: as usual, my interests shifted on other stuff, so I am not going to write the second part of this blog post :P

I am in the mid of developing a personal project which involves cameras and videostreaming.

While working on this project, I built a small port of the HTTP streaming server of Sebastian Dröge from C into rust:

clynamen/basic_http_webm_server_rust

The server uses a minimal tokio server and the gstreamer-rs library (of which the same S. Dröge is the main contributor).

The main difference between the two version consists in the absence of the multisocketsink element, which is not currently available on rust. This element allows to connect multiple TCP sockets to the gstreamer pipeline, thus providing a simple way for sending the video to multiple clients. In the rust version, this is replaced (probably in a bad way) by an appsink and multiple mpsc queues.

In the last post, I was evaluating various solutions for generating the Julia-OpenCV bindings I dream of.

I am currently studying how the libcxxwrap library works, in order to check if it fits my requirements. I quickly noticed that it misses the capability of generating function with keywords (see the Github issue). This feature would be really interesting for the binding since OpenCV uses a lot of default and keyword arguments, both of which are nicely supported in python.

But no worries, Julia is a Lisp (or, at least, looks very much like it for many reasons). It should be easy to manipulate function code in order to add defaults, keyword, etc…

Let’s find out how.

Basics

The fundamentals of Julia metaprogramming are explained in the official documentation. You should read that before going further. However, we will start with the easy stuff.

First, let’s write a macro that creates a function.

1
2
3
4
5
6
7
8
9
10
11

macro make_fn1(name)
  name_str = "$name"
  quote
      function $(esc(name))()
          println("Hello ", $name_str, "!")
      end
  end
end

@make_fn1(world)
# Hello World!

What happens when macro make_fn1 is called? We first take value of the macro argument name and convert it into a string, which will be used later for printing. Then, we return an expression that defines a function. The name of the function comes from the same macro argument. When the macro is called, the returned expression is evaluated and thus the function ‘world’ is defined.

We can inspect the expression returned by make_fn1 by using the @macroexpand macro:

1
2
3
4
5
6

julia> @macroexpand @make_fn1(pizza)
quote
    function pizza()
        (Main.println)("Hello ", "pizza", "!")
    end
end

Note how in the function declaration we used $(esc(name)) instead of just using $(name). Otherwise, Julia hygiene rules will cause the function to have a random name:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

macro make_fn1_bad(name)
  name_str = "$name"
  quote
      function $(name)()
          println("Hello ", $name_str, "!")
      end
  end
end

julia> @macroexpand @make_fn1_bad(pizza)
quote
    function #18#pizza() # <- random name was generated
        (Main.println)("Hello ", "pizza", "!")
    end
end

Adding arguments

Ok, we can now generate function with arbitrary names, but we still miss arguments. A possible solution for this was discussed in this discourse thread.

This is the proposed solution:

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

macro make_fn2(name, args...)
   name_str = "$name"
   argstup = Tuple(args)

   quote
       function $(esc(name))($(map(esc, argstup)...))
           println($name_str)
           map(println, [($(map(esc, argstup)...))])
       end
   end
end

@make_fn2(example_fun, a, b, c)

julia> example_fun(1.2, "dog", 3)
1.2
dog
3
julia> @macroexpand @make_fn2(example_fun, a, b, c)
quote
    #= /home/clynamen/software/tests/julia/main.jl:50 =#
    function sum_all(a, b, c)
        #= /home/clynamen/software/tests/julia/main.jl:51 =#
        (Main.println)("sum_all")
        #= /home/clynamen/software/tests/julia/main.jl:52 =#
        (Main.map)(Main.println, [a, b, c])
    end
end

A more complex example

ok, how to add default arguments now?

I have tried to extend the previous solution and failed. I thought it was possible to use this substitution syntax again but I still didn’t figure out how the parser works with the macro output.

However, there is a better way to do this: We can easily manipulate the AST programmatically, by composing list of keywords and arguments. Even better, Julia allows you to inspect the AST via the @dump macro:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

julia> Meta.@dump( function(a, b, c="hello") end)
Expr
  head: Symbol function
  args: Array{Any}((2,))
    1: Expr
      head: Symbol tuple
      args: Array{Any}((3,))
        1: Symbol a
        2: Symbol b
        3: Expr
          head: Symbol =
          args: Array{Any}((2,))
            1: Symbol c
            2: String "hello"
    2: Expr
      head: Symbol block
      args: Array{Any}((1,))
        1: LineNumberNode
          line: Int64 1
          file: Symbol none

This is pretty handy: you can write an example of the expression you would like to build, inspect its AST and use it as a reference.

Note how the function arguments are just a list of Symbols and Expressions.

Finally, here an example of a macro that defines a function with default and keyword arguments:

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

macro makefn(name, args, kwargs)
   # Let's start defining the name and
   # arguments declaration
   call = Expr(:call)
   push!(call.args, Symbol(name))

   # keyword arguments of the new function
   kwargs_list = []

   # In julia, the keyword arguments are added at
   # the begin of the list, even if they appear
   # last in the syntax. So, process kwargs first:
   for arg in kwargs.args
      if typeof(arg) == Symbol
         # plain keyword arg
         push!(kwargs_list, esc(arg))
      elseif typeof(arg) == Expr
         # default keyword arg
         kw = Expr(:kw)
         push!(kw.args, esc(arg.args[1]))
         push!(kw.args, arg.args[2])

         push!(kwargs_list, kw)
      end
   end

   # Keyword arguments are defined in a
   # :parameters Expr
   parameters = Expr(:parameters)
   parameters.args = kwargs_list

   # add the keyword arguments at the begin of
   # the argument list
   push!(call.args, parameters)

   # now process plain arguments
   for arg in args.args
      if typeof(arg) == Symbol
         # normal arg
         push!(call.args, esc(arg))
      elseif typeof(arg) == Expr
         # default arg
         kw = Expr(:kw)
         push!(kw.args, esc(arg.args[1]))
         push!(kw.args, arg.args[2])
         push!(call.args, kw)
      end
   end

   # a function Expr has two arguments:
   # the declaration and the :block that defines the
   # function implementation.
   # For this example, we define an empty :block
   fn_args = [call, Expr(:block)]
   fn = Expr(:function)

   append!(fn.args, fn_args)
   fn
end

# example usage
@makefn("more_complex_fun", (a, b, c="hello"), (f=1, g="world"))

Check out the function generated by the macro:

1
2
3

julia> @macroexpand1 @makefn("more_complex_fun", (a, b, c="hello"), (f=1, g="world"))
:(function (Main.more_complex_fun)(a, b, c="hello"; f=1, g="world")
  end)

Conclusions

I think the AST manipulation offers what I need for extending libcxxwrap. Probably it will also be useful during the actual binding generation, allowing to automatically write Julia code that better integrates with the OpenCV interface.

Recently the Julia Cxx.jl package came back to life again. The package uses Clang for calling C++ at runtime, possibly making it the most interesting tool for interfacing with a lot of C++ libraries. Since Julia seems really promising for writing Computer Vision algorithms, both for support for Machine Learning and linear algebra in general with high performance, I wanted to try the OpenCV bindings. The idea seemed appealing to quite some people since there are three attempts in this application, that not surprisingly share the same name:

• OpenCV.jl
• OpenCV.jl
• ..and… OpenCV.jl

A bit sadly, all three projects seem abandoned now. I am not surprised since both Julia and OpenCV were undergoing many changes in the latest years. Even if bindings are a thin layer of intermixed language code, it is quite a burden to maintain them, especially during the initial phase where no one has a real interest in them.

The OpenCV project itself provides two main bindings, for python and java. I have never used the java binding, but I can assure you the python binding is damn good. Since all the hard work is done by the OpenCV library itself and, elsewhere, by numpy, it is possible to quickly use the complex algorithm offered by OpenCV with C++ performance. These bindings are two extra modules built along with the full source, so they are provided in almost all distributions. Most importantly, being included in the same repo, these bindings are maintained by the same OpenCV developers.

The generation of bindings for other languages, however, is left as an exercise to the reader.

As explained in the official documentation the generation of java and python binding is a quick and dirty process: A python script parses the headers and provides function signatures to a generator, which in turn generates the python (or java) code using template strings and some handcoded files. The process does not seem really modular, and probably today there are better options, especially for the parser (e.g. libclang). But being self-contained and targeted for opencv only, it just works.

As for Julia, lovers of other languages created their own bindings. Just to name a few:

• opencv-rust
• node-opencv
• haskell - opencv

Needless to say, these libraries use different implementation approaches:

• Writing a C library first, and then use the FFI for C
• Wrap the C++ code in a library that can be imported in the desired language.
• Perform a C++ low-level call

Now, all the three Julia implementation cited above seems to have taken the ‘Call C++ code directly’ approach using the Cxx.jl library. After all, clang is powerful enough to do this kind of magic today. It is kind of amazing that compiled and JIT code can talk each other, almost if as if we are using languages built upon a high-level runtime (e.g. C# and VisualBasic on CLR, Java and Scala on the JVM etc…).

So, coming back to the original problem, I would like to improve or write an OpenCV binding for Julia. Still, I am not sure which is the best approach. Using the Cxx.jl library, even if quite elegant and easy to read (since all the ugly stuff stays in the Cxx.jl module itself) involves writing most of the code manually. Whenever functions are added/removed/modified in OpenCV, we need to manually update our bindings. Of course, this happens often, but not so often to be an unmanageable burden (it is the interest of the same OpenCV developers to change the API slowly, without breaking changes).

However the parser approach used by OpenCV makes more sense: Code is generated automatically, except for a few special cases for convenience or performance reason. Only small updates should be required, new functions will be automatically supported, and maybe one day the binding can be merged in the same OpenCV library.

It is hard to chose one of the two paths without prototyping a bit with them. I am currently evaluating the generator approach. I will write about the progress in a new post, hopefully soon.

Es sind Jahre, Ich wollte etwas mit Rust machen. Als moderner C++ Programmierer zu sein mag ich natürlich Rust: Die Programmiersprache hat die Funktione, die mir am besten gefallen:

• Kompilierzeitprüfungen
• Guter package manager
• Kein garbage-collector, aber ein borrow-checker

Ich hatte die Idee, ein Videospiele zu machen. Aber Ich weiß, Ich brauche mehr Zeit. Rust is nicht so gut als C++ für Videospiele: es ist möglich, Opengl oder Vulkan zu verwenden. Aber es gibt keine or klein library dafür. Zum Beispiel, piston ist eine 2D Game library mit wenige, langsame Funktionen. Amethyst ist vielversprechender. Diese library ist insipiriert aus data-driven Prinzipen und es ist auf eine Entity Component System aufgebaut. Amethyst ist jedoch noch unreif. Die Entwicker versuchen, die Grafik-Engine schenller zu machen. Außerdem würde Ich gerne Opengl vergessen und geh direkt mit Vulkan, aber seine Gemeinschaft ist kleine.

Anstatt ein Videospiele zu machen, suchte Ich nach einer anderen Chance. Ich brauchte ein einfach Fahrzeug-Simulator auf Arbeit mit ROS-Unterstützung. Keine komplexen Grafiken, vielleicht etwas Physik. Die gegenwärtig verfügbar libraries für Rust sollten passen.

Roadsim2D

Roadsim2D ist nur a toy-project. Ich wollte ein Simulator wo man kannt 2D Autos Steuren

Ich schreibe roadsim2D als mein erstes rust Projekt. Ich lerne immer noch, wie die borrow-checker funktioniert. Ich muss sagen: am Anfang, man verschwendet Zeit auch im die einfachesten Dinge. Der compiler hilft dir mit Fehlerbeschreibung, doch die richtige Lösung ist oft spezifisch. Schließlich du musst lernen wie den Programm besser entwürfen. Du lernst wenn du spielst gegen den compiler. Ich habe piston benutzt, um basisch Form zeichen. Die Library steuert geometrisch Transform, so ist es leicht eine Kamera hinzufügen. Ich wollte das nicht kodieren.

Nach dem die Kamera, die Autos wurden hinzugefügt. Ihre Bewegungen folgen die Ackermann Lenkmodell. Ich hatte bald Probleme mit die Borrow-checker: zu viele Variables werden benutzen von zu viele Komponente. Es wurde klar, ich musste den Code umgestalten.

Beim Lesen über Amethyst, Ich habe specs entdeckt. specs ist eine library fur data-oriented programming, ein Paradigma in Game Development sehr bekannt. In diese library, der Programmierer musst Komponenten und Systemen definieren. Komponenten haben data, Systeme haben Code, die die Komponenten verändern. Nicht nur das macht das Programm (potenziell) schneller, das macht alles einfacher als voher zu codieren. Mit specs, es ist explizit, was ist konstant und was kannt änderen. Und du kannst das Leben von Komponenten mit die Entitäten steuern.

Zum Beispiel, schauen wir mal, wie die Physik von Autos ist aktualisiert:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

impl<'a, 'b> System<'a> for UpdateCarsSys<'b> {
    type SystemData = (ReadExpect<'a, UpdateDeltaTime>, WriteStorage<'a, PhysicsComponent>, ReadStorage<'a, Car>);

    fn run(&mut self, (update_delta_time, mut physics_components, mut cars): Self::SystemData) {
        for (physics_component, car) in (&mut physics_components, & cars).join() {

            let mut rigid_body = self.physics_world.rigid_body_mut(physics_component.body_handle).expect("car rigid body not found");
            let pos = rigid_body.position().translation.vector;
            let rot = rigid_body.position().rotation;
            let vel = rigid_body.velocity();

            let rot : Basis2<_> = Rotation2::<f64>::from_angle(Rad(rot.unwrap().re));
            let yaw_increment = vel.linear.x as f32 / (car.bb_size.height as f32 / 2.0f32)  *  car.wheel_yaw;


            rigid_body.set_angular_velocity(yaw_increment as f64);
        }
    }

}

UpdateCarsSys ist eine Klasse, die die Winkelgeschwindigkeit nach die Ackermann Lenkmodell verändern. Die Klasses tut nur das. Die run() Methode wird bei jedem Frame laufen. In ein System, man kannt eine Query ǘber die Komponenten tun. Dann, kannst du die Ergebnisliste iteriren. Die Komponenten, die du kannst ändern, können mit mut markiert werden.

Links

roadsim2d

General Motors kauft Strobe, solid-state lidar company

Note: This post was translated from English and reviewed with google translate

Dies ist die größte Wichtigste Neuigkeit der Woche. Wir wissen gany genau, dass viele Automobilhersteller mögen solid-state Lidars: Selbst wenn drehend Laser Scanner arbeiten für Forschung und Prototypen (hohe Leistung und Genaugigkeit, aber hohe Kosten) man denkt nicht, sie benutzen in Massenproduktion: rotierende Komponenten halten nicht lange für Anwendung wo Genauigkeit wichtig ist. Du willst nicht, dass die Benutzer ihre Autos zurückbringen, um Lidars zu reparieren

Solid State Lidars wirklich interessant aussehen: keine beweglichen Teile, alles unterbringet in ein Chip, mit geringen Kosten, vergleichbar Genaiugkeit und Reichweite. Aber es gibt ein nur Problem: Wir können sie leicht machen. Trotz sie sind bekannt für einegen Jahren, Solid State Lidars sind schwer zur produzieren. Naturlich dank Investitionen Firma verbessern ihre Lidars von Jahr zur Jahr und das Entwicklung von Konsumgütern ist in der nähe. Du erinnerst dich vielleicht, das Gleiche passiert mit ToF Cameras: Kosten ging von Tausende von Dollars bis ein paar 100$ in ein wenige Jahren (denke an Xbox One Kinect heutzutage).

Es gibt einigen Firmas wie Strobe auf dem Markt. Sie sind noch in ihrer Start-up Phase so es macht Sinn, sie jetzt zu kaufen. Die Entscheidung der Chefs von GM scheint gut wenn man bedenkt, dass andere Firma wird ähnlich tun: Ford investiert in Velodyne im letzen Jahr, Continental kauft ASC, Tesla…

…Nun, Tesls sagt: “Mann, keine Lidars, wir Haben Cameras”.

Und sie sind allein:

Comma.ai shares cool and shiny deep learning videos

Comma.ai teilt neue und glänzend deep learning Videos

Die Firma von George Hotz liebt cameras. Sie sind billig, Man kann finden sie an ein handy und am wichtigsten Sie sind menschliche Augen ähnlich. Und wenn ein Mesnch mit seinen Augen fahren kann, warum sollte dann kein Computer? Das is der gleich Ansatz von Tesla, aber Comma.ai scheint di meinsten seiner Resourcen auf Deep Learning investieren zu.

Zum Beispiel: image segmentation:

This is a single frame no context prediction. Imagine once I get the unsupervised temporal working. Computer vision is unreal! pic.twitter.com/FhoLSkURSF

— comma ai (@comma_ai) September 30, 2017

… oder, du weißt , ersetyen Lidars für Depth Data:

Depth. Trained entirely in simulation. pic.twitter.com/8sY8IATjfn

— comma ai (@comma_ai) October 10, 2017

Es ist interessant das Trainingsdaten wurden geniert mit annotiert Bilden (dank dem adult coloring books Projekt ) und Simulationen

So, as you can see it’s long time I don’t write anything on this blog. Despite the intention to write short tutorials, personal opinions, and other technical stuff, this blog was always at the bottom of my always-increasing to-do stack. Why am I then committing myself to write a weekly update on the status of self-driving car development and research? Well, as always there is both a practical argument and a leisure reason: I love talking about this field, which is continuously evolving with exciting changes every day, and I am currently learning German, thus I want to exercise my writing skills daily (which, at the moment, are really bad. But fear not: the posts will be published in English too.) This series of post will be mostly based on news published on other websites or forums. So don’t expect to find the latest rumors but, instead, a review of most important events happened during the week.

General Motors buys Strobe, solid-state lidar company

This is definitely the biggest news of the week. We know quite well that many cars manufacturers have high expectations on solid-state lidars: While rotating laser scanner works for research or prototypes (high performance and accuracy, yet high costs) it is unthinkable to use them in actual user mass-production: Moving an array of laser around accurately requires high manufacturing costs and, most importantly continuously high frequency rotating components do not last long for accurate applications. You don’t want users to bring their car back every year for replacing their faulty lidar.

Solid state lidars look really interesting instead: no moving parts, everything fits in a single chip, lower costs and comparable accuracy and range. Only problem: we are not quite there yet. Despite being known for a few years, solid-state lidars are quite hard to implement. Of course, now that money is poured into, companies are improving their lidars year by year and the development of off-the-shelf consumer solution looks near. You may remember the same happened to ToF cameras: cost decreased from thousands of dollars to a couple 100$ in a few years (think about the Xbox One Kinect today).

There are just a few companies like Strobe around. They are still in their start-up phase and thus it make sense to buy them now. We can agree that the decision of GM’s board seems quite good considering that other companies will probably do something similar in the future: Ford invested in Velodyne last year, Continental bought ASC, Tesla…

…Well, Tesla says “Fuck, we don’t use lidars, we have cameras”.

And they are not alone:

Comma.ai shares cool and shiny deep learning videos

George Hotz’s company loves cameras. They are cheap, they can be found on a mobile phone and most importantly they are the closest thing to an human eye. And if a human can drive a car with his eyes, why shouldn’t a computer? This is the same approach of Tesla, expect that Comma.ai seems to invest most of his resources on deep learning. We know that the Line Keeping Assistant algorithm of openpilot is based on an end-to-end deep neural network, but lately the company is looking to exploit DNN for other scopes:

For instance image segmentation:

This is a single frame no context prediction. Imagine once I get the unsupervised temporal working. Computer vision is unreal! pic.twitter.com/FhoLSkURSF

— comma ai (@comma_ai) September 30, 2017

… or, you know, replacing the previously cited Lidars for depth data

Depth. Trained entirely in simulation. pic.twitter.com/8sY8IATjfn

— comma ai (@comma_ai) October 10, 2017

It is interesting to note how the training data was respectively generated by manually annotated images (thanks to the adult coloring books project ) and simulations.

This post was originally published on my previous blog

Here I found a shader for Unity to obtain an outline of a mesh.

http://answers.unity3d.com/questions/141229/making-a-silhouette-outline-shader.html

This shader uses a pass to create a slightly bigger mesh behind the original one. This is a good solution (at least in Unity), but only for convex/non transparent object. The fragments of the outline will indeed appear behind the mesh:

We can remove the fragments behind the mesh modifying the depth buffer with a duplicated object. The original object writes to the z-buffer, so the duplicated object (i.e. the one that act as an outline) will be partially culled by the original one.

In order to obtain this, we can use these shaders:

Transparent shader for the original object

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Shader "Outline/Transparent" {
  Properties {
    _color ("Color", Color) = (1,1,1,0.5)
  }

    SubShader {
    Tags {"Queue" = "Geometry+1" }
      Pass {
        Blend SrcAlpha OneMinusSrcAlpha
        Lighting On
        ZWrite On

        Material {
          Diffuse [_color]
        }
      }
    }
}

Outline shader for the outline, it will be applied to the duplicated object (Note: this is a mod of the shader quoted at the begin)

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

Shader "Outline/Outline" {
    Properties {
      _OutlineColor ("Outline Color", Color) = (0,0,0,1)
      _Outline ("Outline width", Range (.002, 0.03)) = .005
    }

    CGINCLUDE
    #include "UnityCG.cginc"

    struct appdata {
    float4 vertex : POSITION;
    float3 normal : NORMAL;
    };

    struct v2f {
    float4 pos : POSITION;
    float4 color : COLOR;
    };

    uniform float _Outline;
    uniform float4 _OutlineColor;

    v2f vert(appdata v) {
      // just make a copy of incoming vertex data but scaled according to normal direction
      v2f o;
      o.pos = mul(UNITY_MATRIX_MVP, v.vertex);

      float3 norm = mul ((float3x3)UNITY_MATRIX_IT_MV, v.normal);
      float2 offset = TransformViewToProjection(norm.xy);

      o.pos.xy += offset * o.pos.z * _Outline;
      o.color = _OutlineColor;
      return o;
    }
    ENDCG

    SubShader {
    Tags {"Queue" = "Overlay"}

      Pass {
        Name "OUTLINE"
        Tags { "LightMode" = "Always" }
        Cull Front
        ZWrite On
        ZTest Less
        Blend SrcAlpha OneMinusSrcAlpha
        ColorMask RGB
        Offset 15,15

        CGPROGRAM
        #pragma vertex vert
        #pragma fragment frag
          half4 frag(v2f i) :COLOR { return i.color; }
        ENDCG
      }
    }

    SubShader {
      Tags {"Queue" = "Overlay" }
      CGPROGRAM
      #pragma surface surf Lambert

      sampler2D _MainTex;
      fixed4 _Color;

      struct Input {
        float2 uv_MainTex;
      };

      void surf (Input IN, inout SurfaceOutput o) {
        fixed4 c = tex2D(_MainTex, IN.uv_MainTex) * _Color;
        o.Albedo = c.rgb;
        o.Alpha = c.a;
      }
      ENDCG

      Pass {
        Name "OUTLINE"
        Tags { "LightMode" = "Always" }
        Cull Front
        ZWrite On
        ColorMask RGB
        Blend SrcAlpha OneMinusSrcAlpha

        CGPROGRAM
        #pragma vertex vert
        #pragma exclude_renderers gles xbox360 ps3
        ENDCG
        SetTexture [_MainTex] { combine primary }
      }
    }

    Fallback "Diffuse"
}

The result is pretty good:

Finally, here it is a Unity script that automatically creates the outline effect when applied to an object:

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

using UnityEngine;
using System.Collections;

public class Outliner : MonoBehaviour {

  public Color meshColor = new Color(1f,1f,1f,0.5f);
  public Color outlineColor = new Color(1f,1f,0f,1f);

  // Use this for initialization
  public void Start () {

    // Set the transparent material to this object
    MeshRenderer meshRenderer = GetComponent<meshrenderer>();
    Material[] materials = meshRenderer.materials;
    int materialsNum = materials.Length;
    for(int i = 0; i < materialsNum; i++) {
      materials[i].shader = Shader.Find("Outline/Transparent");
      materials[i].SetColor("_color", meshColor);
    }

    // Create copy of this object, this will have the shader that makes the real outline
    GameObject outlineObj = new GameObject();
    outlineObj.transform.position = transform.position;
    outlineObj.transform.rotation = transform.rotation;
    outlineObj.AddComponent<meshfilter>();
    outlineObj.AddComponent<meshrenderer>();
    Mesh mesh;
    mesh = (Mesh) Instantiate(GetComponent<meshfilter>().mesh);
    outlineObj.GetComponent<meshfilter>().mesh = mesh;

    outlineObj.transform.parent = this.transform;
    materials = new Material[materialsNum];
    for(int i = 0; i < materialsNum; i++) {
      materials[i] = new Material(Shader.Find("Outline/Outline"));
      materials[i].SetColor("_OutlineColor", outlineColor);
    }
    outlineObj.GetComponent<meshrenderer>().materials = materials;

  }

}

This post was originally published on my previous blog

A few words on Voxelization and SAT

In this post we will create a script for voxelize any kind of mesh in unity. Voxelization could be useful in physical simulations, terrain representation and every situation where we need to manipulate the hollow inside of a mesh. A great post about Voxelization can be found “here”, on Wolfire blog. The post explains how the voxelization of a triangle mesh is done in Overgrowth, we will use the same method in unity.

The creation of a voxel model that reproduces the mesh is achived trough a 3d grid of cubes and an intersection test for each triangle against each cube. The author states that he uses a AABB-AABB intersection test to check if a cube and a triangle are intersected. This is very fast and appropriate for most situations, but we want the general solution.

A slower but precise way to test the intersection is to use the Separating Axis Theorem. This paper explains the use of the SAT for Triangle-AABB intersection.

An implementation in C++ of this algorithm was written by Mike Vandelay and can be found planet-source-code.com. I rewrote the same code in unityscript.

Basically the SAT works like this

Take 13 axes: 3 axes are the cube face normals, 1 axis is the triangle face normal, 9 are the dot product between the first 3 axes and the triangles edges.

Project the AABB and the triangle on each axis. If the projections intersects on an axis, then the AABB and the triangle are intersected, otherwise they aren’t. here a much more detailed explanation of the SAT.

Now, let’s see how implement all this in unity.

Mesh Voxelization

The complete script for voxelization can be found here on my github.

We are going to use a grid for creating a voxel model. Each Grid is formed by cubes of the same size, these are the grid properties:

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

public class AABCGrid {

private var side : float;
private var width : short;
private var height : short;
private var depth : short;
private var origin : Vector3;
private var cubeSet : boolean[,,];
private var cubeNormalSum : short[,,];
private var debug = false;

...
}

/*
AABC stands for Axis Aligned Bounding Cube.
For performance purpose, I didn't add a 3 dimension array of AABCs, otherwise each cube had to store the side length, the set value etc...
However an AABC class is defined, but only for external use, while inside the AABCGrid class everything is evaluated starting from the class properties.
e.g. to obtain the vertices of a cube is it possible to use the method
AABCGrid.GetAABCCorners(x : short, y : short, z : short) : Vector3[]
or the method AABC.GetCorners().
The AABC.GetCorners() is actually defined like this:
*/
public function GetCorners(x : short, y : short, z : short) : Vector3[] {
    // grid is a reference to an AABCGrid
    return grid.GetAABCCorners(x, y, z);
}

All the public method call a CheckBound() function that check if the cube specified by the x, y, z variable is inside the grid, then the real implementation of the method is called. e.g.

1
2
3
4
5
6
7
8

public function IsAABCSet(x : short, y : short, z : short) : boolean {
   CheckBounds(x, y, z);
   return IsAABCSetUnchecked(x, y, z);
}

protected function IsAABCSetUnchecked(x : short, y : short, z : short) : boolean {
   return cubeSet[x, y, z];
}

Off course, inside the AABCGrid class and in the possible inheritors, only the unchecked method should be called for faster code.

Creating the voxel shell

Once the grid is defined, we need to ‘set’ all the cubes that are intersected by a triangle of the mesh. This is done in the AABCGrid.FillGridWithGameObjectMeshShell() method.

The result will be a voxel shell, an empty shape that reproduces the mesh.

Ignore the part relative to the normals of the triangles, I’m going to explain that later.

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

public function FillGridWithGameObjectMeshShell(gameObj : GameObject, storeNormalSum : boolean) {
    var gameObjMesh = gameObj.GetComponent(MeshFilter).mesh;
    var gameObjTransf = gameObj.transform;
    var triangle = new Vector3[3];
    var startTime = Time.realtimeSinceStartup;
    var meshVertices = gameObjMesh.vertices;
    var meshTriangles = gameObjMesh.triangles;
    var meshTrianglesCount = meshTriangles.length / 3;
    var x : short;
    var y : short;
    var z : short;
    var ignoreNormalRange = 0;
    // In this method we can also evaluate stores the normals of the triangles 
    // that intersect the cube.
    if (storeNormalSum) {
        cubeNormalSum = new short [width, height, depth];
    }
    if(debug) {
        Debug.Log("Start:");
        Debug.Log("Time: " + startTime);
        Debug.Log("     Mesh Description: ");
        Debug.Log("Name: " + gameObjMesh.name);
        Debug.Log("Triangles: " + meshTrianglesCount);
        Debug.Log("Local AABB size: " + gameObjMesh.bounds.size);
        Debug.Log("     AABCGrid Description:");
        Debug.Log("Size: " + width + ',' + height + ',' + depth);
    }

    // For each triangle, perform SAT intersection check with the AABCs within the triangle AABB.
    for (var i = 0; i < meshTrianglesCount; ++i) {
        triangle[0] = gameObjTransf.TransformPoint(meshVertices[meshTriangles[i * 3]]);
        triangle[1] = gameObjTransf.TransformPoint(meshVertices[meshTriangles[i * 3 + 1]]);
        triangle[2] = gameObjTransf.TransformPoint(meshVertices[meshTriangles[i * 3 + 2]]);
        // Find the triangle AABB, select a sub grid.
        var startX = Mathf.Floor((Mathf.Min([triangle[0].x, triangle[1].x, triangle[2].x]) - origin.x) / side);
        var startY = Mathf.Floor((Mathf.Min([triangle[0].y, triangle[1].y, triangle[2].y]) - origin.y) / side);
        var startZ = Mathf.Floor((Mathf.Min([triangle[0].z, triangle[1].z, triangle[2].z]) - origin.z) / side);
        var endX = Mathf.Ceil((Mathf.Max([triangle[0].x, triangle[1].x, triangle[2].x]) - origin.x) / side);
        var endY = Mathf.Ceil((Mathf.Max([triangle[0].y, triangle[1].y, triangle[2].y]) - origin.y) / side);
        var endZ = Mathf.Ceil((Mathf.Max([triangle[0].z, triangle[1].z, triangle[2].z]) - origin.z) / side);
        if (storeNormalSum) {
            for (x = startX; x <= endX; ++x) {
                for (y = startY; y <= endY; ++y) {
                    for (z = startZ; z <= endZ; ++z) {
                        if (TriangleIntersectAABC(triangle, x, y, z)) {
                            var triangleNormal = GetTriangleNormal(triangle);
                            cubeSet[x, y, z] = true;
                            if (triangleNormal.z < 0 - ignoreNormalRange) {
                                cubeNormalSum[x, y, z]++;
                            } else if (triangleNormal.z > 0 + ignoreNormalRange){
                                cubeNormalSum[x, y, z]--;
                            }
                        }
                    }
                }
            }
        } else {
            for (x = startX; x < endX; ++x) {
                for (y = startY; y < endY; ++y) {
                    for (z = startZ; z < endZ; ++z) {
                        if (!IsAABCSet(x, y, z) && TriangleIntersectAABC(triangle, x, y, z)) {
                            cubeSet[x, y, z] = true;
                        }
                    }
                }
            }
        }
    }
    if(debug) {
        Debug.Log("Grid Evaluation Ended!");
        Debug.Log("Time spent: " + (Time.realtimeSinceStartup - startTime) + "s");
        Debug.Log("End: ");
    }
}

The code finds the AABB of each triangle (2), then performs the SAT intersection test on each cube intersected by AABB (3).

triangles (1) the triangle in the grid.  (2) the triangle with its AABB and the AABCs intersected by the AABB. (3) the AABCs intersected by the triangle

Filling the hollow inside

When this method is finished we will have a voxel model that reproduce the mesh. But we have not finished yet, we may need also to know which voxel (AABC) is inside the mesh and which is out. In order to do that we use the scan fill algorithm like the post on overgrowth blog explains, except for a little thing: we don’t start to fill the cube when the normal of the last triangle faces to the left, instead we mark ‘Begin’ and ‘End’ cubes in FillGridWithGameObjectMeshShell(). If the z component of the triangle is positive, we decrease cubeNormalSum[x, y, z] by one, else we increase it. When all the triangles have been processed, a  positive cubeNormalSum means that the cube is a ‘Begin’ cube, if it is negative then the cube is an ‘End’ cube.

We can’t just check the normal of the last triangle because we don’t know the order of the triangles, we neither traverse the entire grid during the creation of the voxel shell.

The method FillGridWithGameObjectMesh() does the real scan lining once that FillGridWithGameObjectMeshShell() ends. It traverses all the grid, starting from the cube at 0, 0, 0. If a ‘Begin’ cube is found, an ‘End’ cube is searched. If an ‘End’ cube is found, all the cubes between the last ‘Begin’ and ‘End’ are set.

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

public function FillGridWithGameObjectMesh(gameObj : GameObject) {
   FillGridWithGameObjectMeshShell(gameObj, true);

   for (var x = 0; x < width; ++x) {
      for (var y = 0; y < height; ++y) {
         var fill = false;
         var cubeToFill = 0;
         for (var z = 0; z < depth; ++z) {
            if (cubeSet[x, y, z]) {
               var normalSum = cubeNormalSum[x, y, z];
               if (normalSum) {
                  if (normalSum > 0) {
                     // 'Begin' cube
                     fill = true;
                  } else {
                     // 'End' cube
                     fill = false;
                     while (cubeToFill > 1) {
                        cubeToFill--;
                        cubeSet[x, y, z - cubeToFill] = true;
                     }
                  }
               cubeToFill = 0;
             }
             continue;
         }
         if (fill) {
            cubeToFill++;
         }
      }
   }
}
 cubeNormalSum = null;
}

Performance

Performance are mainly determined by the number of triangles in the mesh and the side length of the AABCs. Here they are some of the tests made on my laptop:

Laptop specs: HP g6-1359el Intel Core i5-2450M - 2,5 GHz AMD Radeon HD 7450M

First Test

Mesh: construction_worke Time spent: 0.4051636s Triangles: 4020 Cube side: 0.05

Second Test

Mesh: construction_worker Time spent: 1.088864s Triangles: 4020 Cube side: 0.02

Third Test

Mesh: sphere

Time spent: 1.926165s Triangles:760 Cube side: 0.03

Memory could be saved storing cubeSet using a 3D bitarray class and cubeNormalSum using a 3D array of bytes

Try it yourself

For testing purpose there is also a VoxelizationTest.js script on my github. Attach it to an object with a mesh to try this voxelization script. Remember to enable Gizmos in the game window, otherwise the AABCs will not appear!