# `Vg` integration to the grader

> **Note:** I use _server mode_ and _browser mode_ to designate the different
> uses of Learn-OCaml but these are certainly not the correct denotations.

## Goal

The goal of this task is to add the possibility to grade `Vg` values returned
by student functions.

This means `Learn-OCaml` must be able:

1. <span id="goal-1">to compare two `Vg` values,</span>
2. to print the comparison result inside reports.

## Major issues

The main issue of this task is to be able to compare two SVG images
([1.](#goal-1)). Indeed, they need to be _rasterized_. This can be achieved by
retrieving in the DOM the canvas containing the rendered image. However, this
approach can't be used for the _server_ mode, because it can't used a web
browser to render SVG images.

There is multiple approaches in order to resolve this issue:

1. Using a binding to an **existing _rasterizer_** such as
[cairo2](https://opam.ocaml.org/packages/cairo2/) for both _browser_ and
_server_ mode. This was tried by Etienne Marais
([@maiste](https://github.com/maiste)), but it was **too heavy** to be
embedded and used in practice. The online grader wasn't able to start.
2. Writing a SVG **_rasterizer_ directly in OCaml**. This was also tried by
Etienne Marais ([@maiste](https://github.com/maiste)), but it's **too
difficult to be achieved in a couple of months** by an undergraduate
student not specialized in image representation.

## Suggested solution

According to me, our best shot is to add this feature only for the _browser_
mode by using the browser engine as _rasterizer_ and in the future, hiring a 2D
graphics expert to implement a custom one in OCaml, which can be used in both
modes.

> **Étienne**: the issue is that if someone cheats, the teacher isn't able to run
> a new grading. It means the teacher MUST verify manually all the answer.
> It's just a concern, but it should be raised. This solution seems indeed the
> best for now. However, the command line grader should exist for Vg image, give
> all the points to avoid issues but raise a warning to explain it's a work in
> progress feature.

Indeed, this solution will allow teachers to start writing exercises as soon as
possible.

### Implementation

Sequence diagram of the _hacking flow_ suggested by Yann Régis-Gianas (2021-07-28):

sequenceDiagram
    autonumber
    par 
        loop Every X time
            DOM->>img_to_rasterize (ref option): Checking for new Vg.image to rasterize.
            DOM->>DOM: Rasterizing the image.
            DOM-->>bitmap (ref option): Set the rasterized image.
        end
    and 
        Worker-->>img_to_rasterize (ref option): Set a new image to rasterize.
        loop While bitmap is set to None
            Worker->>bitmap (ref option): Checking if there is so bitmap.
        end
        Worker-->>bitmap (ref option): Get the rasterized image.
    end

## `Vgr_bitmap` ~~| `Vgr_pixmap` | `Vgr_ba`~~

> Exploring `Vg` renderer implementation in pure OCaml...

> Using `Vgr_bitmap` as module name seems the more adapted.
> Indeed, I count to use an interface to store the final rendered image.
> As a result, users will be able to choose to use their own implementations or use the provided one: `(float, float32_elt, c_layout) Array1.t`.
> (Is it too ambitious?)

### Roadmap

#### `v0.1.0` $\rightarrow$ _2021-08-31_

> The GitHub project is available [here](https://github.com/EmileRolley/vg/projects/1).

In order to be usable, the `Vgr_pixmap` should be able to render any path

* constructed with:
* `Vg.P.line` (straight line)
* `Vg.P.qcurve` (quadratic bézier curve)
* `Vg.P.ccurve` (cubic bézier curve)
* `Vg.P.earc` (elliptical arc)
* using as `Vg.P.area`:
* `Anz` (_non-zero winding rule_)
* with a simple outline (`width = 1.`)
* and using the `Vg.I.Const` `primitive`.

After reading the different existing renderers implementations, I feel like
there is some functions/patterns which could be factorized with a common interface and other to be refactored with utility functions provided by `Vg`.
It's not the priority, but a refactoring iteration at the end should not be long.
To discuss with Daniel.

### Semantics

A rendered segment
: Is a list of coordinates representing all the points of a rendered `Vg.P.segment`.

A rendered path
: Is a set of rendered `Vg` paths.

A render state
: Stores the current path being build, the current _cursor_ location.

A render bitmap
: Is an array containing the rendered `Vg` image.
Where pixel colors are stored like this:

    0        1        2        3        4           (x*w+y)*c
    +--------+--------+--------+--------+--------+-------+--------+---
    |        |        |        |        |        |       |        |
    | (0,0)  | (0,0)  | (0,0)  | (0,0)  | (0,1)  |  ...  | (x,y)  |
    |      r |      g |      b |      a |      r |       |      r |
    +--------+--------+--------+--------+--------+-------+--------+---

    The total size of the array is: w * h * c

    where:
        w = is the image width (nb of columns)
        h = is the image height (nb of lines)
        c = is the number of color channel

The render state OCaml record:

type r_state = {
    (*
        Should Bigarray be used instead of a simple list?
        TODO: benchmark efficiency between `list list`
        and `(float, float32_elt, c_layout) Array1.t list`.
        
        Rendered segments can only be stored in OCaml list because
        of the unpredictable size of segments which will complicate
        the implementation. Why not?
    *)
    path : v2 list list; 
    curr : v2;
    bitmap : (float, float32_elt, c_layout) Array1.t
} 

#### Main functions

##### Build a rendered path from Vg path

(* Structure taken from vg/vgr_cairo.ml and vg/vgr_htmlc.ml *)
let set_path
    (s : r_state)
    (p : Private.Data.path)
     : unit =
    let open P2 in
    let loop s = function
      | `Sub pt -> move_to s (x pt) (y pt)
      | `Line pt -> line_to s (x pt) (y pt))
      | `Qcurve (c, pt) -> quadratic_curve_to (x c) (y c) (x pt) (y pt)
      | `Ccurve (c, c', pt) ->
          bezier_curve_to (x c) (y c) (x c') (y c') (x pt) (y pt)
      | `Earc (large, cw, r, a, pt) ->
          begin match Vgr.Private.P.earc_params last large cw r a pt with
          | None -> line_to (x pt) (y pt)
          | Some (c, m, a, a') ->
              (* This part needs to be developed. *)
              let s = save s in
              let c = V2.ltr (M2.inv m) c in
              M2.(transform s (e00 m) (e10 m) (e01 m) (e11 m) (0.) (0.)));
              arc s (x c) (y c) ~r:1.0 ~a1:a ~a2:a'
              |> restore 
          end
      | `Close -> close_path s
    in
    ignore (P.fold ~rev:true loop { s with path=empty } p)

### `Vg` basics

#### The collage model

`Vg` use a _collage model_ instead of the usual _painter model_ -- _where paths are filled, stroked and blended on top of each other to produce a final image_.

The collage model

: paths define 2D areas in infinite images that are _cut_ to define new infinite images to be blended on top of each other.
> More about the collage model could be found here: [_Functional Image Synthesis_](http://conal.net/papers/bridges2001/).

#### Infinite images

Conceptually, `Vg` images could be seen as functions mapping pionts of the infinite 2D plane to colors.

#### Rendering

In order to be rendered, an image needs to be associates with a _finite_ view and specifications of that view physical size and render target.
These information are stored with the image in a [Renderable](https://erratique.ch/software/vg/doc/Vg/Vgr/index.html#renderable).

Renderables can be given to a renderer for display via the module [Rendering](https://erratique.ch/software/vg/doc/Vg/Vgr/index.html#render).
Renderers are created with `Vgr.create` and **need a `render target` value defining the concrete renderer implementation to use**.

> **Note:** In our case, the `render target` could be:
> * an `('a, 'b, 'c) Bigarray.Array1.t * int * int` (mb looking to [Gg.Ba](https://erratique.ch/software/gg/doc/Gg.Ba.html))
> * or maybe a [Gg.Raster](https://erratique.ch/software/gg/doc/Gg.Raster.html)?

#### The [Cutting images](https://erratique.ch/software/vg/doc/Vg/I/index.html#cut) combinator

This combiner takes a finite area of the plane defined by a path `path`
and a source image `img` to define the image `I.cut path img` that **has the
color of the source image in the area defined by the path and the
transparent black color `Gg.Color.void` everywhere else**.

> **Task:**
> * [ ] Use the [midpoint circle algorithm](https://en.wikipedia.org/wiki/Midpoint_circle_algorithm) to rasterize `P.circle`.
> The _mathematical_ circle can be modeled such as:
~~~ocaml
let area = `O { P.o with P.width = 0.04 } in
let black = I.const Color.black in
I.cut ~area circle black
~~~
> * [ ] Modify the algorithm to draw a disk as is supposed to be with the _cutting combinator_?

There is an optional `area` argument of type [P.area](https://erratique.ch/software/vg/doc/Vg/P/index.html#type-area) which determines how a path should be interpreted as an area of the plane.

> More information could be found here: [Semantics](https://erratique.ch/software/vg/doc/Vg/index.html#sempaths).

### Experimentation

> The source code of my experimentations is available [here](https://github.com/EmileRolley/vg/blob/experimentation/proto/bin/main.ml).

#### 2021-07-29

I started to read the `Vg` documentation.

I implemented the [Bresenham's line algorithm]( https://en.wikipedia.org/wiki/Bresenham's_line_algorithm).

I started to going through the internal representation of `Vg` images and paths.
At this point, I feel that I need to learn more about the _continuation passing style_, indeed, for now the line segment is render like this:
~~~ocaml
let render_segment : segment -> unit = function
| `Line v2 ->
let x = int_of_float (V2.x v2) in
let y = int_of_float (V2.y v2) in
plot_line pxmp 0 0 x y
(*...*)
~~~
However, this is not mean to be used this way and I have the intuition `Vg` images and segments need to be _stacked_ before being _flatten_ in some way.
I mean, each segment and image should/could not be render _in the fly_, they need to be _translate_ to an other representation?
> **Note:** it needs to be more comprehensive.

##### TODOs

* [x] Read [_Functional Image Synthesis_](http://conal.net/papers/bridges2001/).
* [x] Finish to read the documentation.
* [x] Find more resources about vector graphics rasterizations.
* [x] Find a lib to mimic? $\Rightarrow$ **Will mimic `Vgr_cairo` by replacing bindings to the cairo functions (e.g. `Cairo.line_to`) with equivalent one implemented in pure OCaml.
As a result, benchmarks could be made.**
* [x] Going deeper to current `Vg` renderers?
* [x] Send an email to Daniel Bünzli in order to get his opinion about using `Gg.Raster | Gg.Ba` as target.
> Daniel answers:
>
> _"I think that's fine, `Gg.Ba` and `Gg.Raster` are just convenience functions and metadata over linear bigarrays. In your tight loops you will likely rather end up working directly with bigarrays anyways."_
>
> _"Not that I'm aware of. But the thing is the collage model is totally compatible with the painter model. So basically if you have a standard vector graphics renderer you can use it for the collage model. I suggest you have a look for example at the HTML canvas 2D renderer [1] or the cairo [2] to see how that ends up working and what you will need."_

#### 2021-07-30

I started refactoring to use the `Vgr` interface to use the renderer `Vgr_raster`. I used the [Framebuffer_vg](https://github.com/cfcs/mirage-framebuffer/blob/master/framebuffer_vg/framebuffer_vg.ml) and `Vgr_cairo` modules as
For now, I'm using `(int, int_elt, c_layout) Array1.t` as raster.

##### Issues

* How to manage colors? Indeed, the _raster_ is a `Bigarray` storing integers and the `Gg.Color` is a `V4`...
$\Rightarrow$ **`f: Gg.Color -> int`**
* How to calculates discrete points from \`Line `V2` and the `Size2` or `Box2` (respectively the _size_ and the _view_)?

#### 2021-08-02

##### TODOs

* [x] Tackle hand-on the Cairo renderer.
* [ ] Dig into the Cairo context.
* [x] Render a basic `Vg.image` with `Vgr_cairo` to test the OCaml one.
* [ ] Try to mimic the logic flow to the OCaml one.
* [ ] Understand _color stop_.
* [ ] Render:
* [ ] Circles?
* [ ] Lines `plot_line`?

###### `Vgr_cairo` private functions

[`set_path s p`](https://github.com/EmileRolley/vg/blob/1607a3ce8487a91cce51c10d4c4febcf7f1a6044/src/vgr_cairo.ml#L182)
: Call drawing functions of the`Cairo` module such as `move_to` or `line_to`.
**It is these functions that should be implemented in OCaml**.
> **Remark:** these functions seem to set/build a path not drawing directly.
> Moreover, they update the `Cairo.context`.

[`r_image s k r`](https://github.com/dbuenzli/vg/blob/1607a3ce8487a91cce51c10d4c4febcf7f1a6044/src/vgr_cairo.ml#L275)
: Execute a command from the commands list.
##### What seems needed

According to the `Cairo2` renderer, the OCaml one should contains:

* a graphic state `gstate`, containing:

* _the current transform_,
* the current outline stroke (`P.outline`),
* the current stroke color (`?`),
**$\Rightarrow$ still need to choose the color representation**.
* the current fill color (`?`);

* a `state`, containing:

* the corresponding renderer (`Vgr.Private.renderer`),
* _a cost counter for limit_,
* the current renderable view rectangle (`Gg.box2`),
* commands to perform (`cmd list`),
* _cached fonts_ (font rendering is not the priority),
* _cached primitives_ (probably not needed),
* the current graphic state (`gstate`);

> **Remark:** the current point position should be store somewhere.

The idea is that for each `Vg.Vgr.Private.Data.image` the whole path is constructed by _combining_ segments/sub-paths in the current context/state.
Then, when a `Primitive` _is found_, stroke or fill the current path (available in the context) according to the given `area`.

~~Why not using the type [`image`]() of `ocaml-image`?~~

##### Issue

~~Strangling with colors: how to translate `Gg.Color` into a float value in order to store it in a bigarray.~~

$\Rightarrow$ Simply store RGBa values in a row:

0        1        2        3        4           (x*w+y)*c
+--------+--------+--------+--------+--------+-------+--------+---
|        |        |        |        |        |       |        |
| (0,0)  | (0,0)  | (0,0)  | (0,0)  | (0,1)  |  ...  | (x,y)  |
|      r |      g |      b |      a |      r |       |      r |
+--------+--------+--------+--------+--------+-------+--------+---

The total size of the array is: w * h * c

where:
    w = is the image width (nb of columns)
    h = is the image height (nb of lines)
    c = is the number of color channel

> **Question:** Does `w * c` represents the _stride value_?

> `Ba.get_vi` and `Ba.get_id` make sense now!

$\Rightarrow$ Pixmap = `(float, float32_elt, c_layout) Array1.t` (`Ba.create Float32`).

#### 2021-08-03

##### TODOs

* [x] Find out what is the representation of paths inside Cairo.
* [x] Find out how to fill masks/paths. $\Rightarrow$ With the [Nonzero-rule](https://en.wikipedia.org/wiki/Nonzero-rule).

#### 2021-08-24

Currently ([commit #87865cf](https://github.com/EmileRolley/vg/commit/87865cff3877864af0d84f6434057e2481d7a40e)), paths are _rasterized_ in the function `set_path` but it may not be the best way to go.
Indeed, after calculating all the coordinates of the points of the path, isn't possible anymore to apply transformation matrix...
Maybe, the `set_path` function should only calculates all the segments (lines) coordinates of the path and the calculations of all points are done at the end (where precisely?)?

### Waston report

Fixe:

Thu 01 January 1970 -> Thu 02 September 2021

learn-ocaml - 21h 13m 54s
        [fixdoc  1h 03m 42s]
        [notes  1h 22m 48s]
        [show-img-in-result  4h 45m 28s]
        [vg-grader  6h 08m 16s]
        [vg-grading     03m 13s]
        [vgr-pixmap  4h 53m 25s]
        [vgr-raster  9h 05m 18s]

vg - 69h 37m 06s
        [bitmap-module  5h 41m 15s]
        [setup 17h 01m 37s]
        [simple-filled-img  2h 59m 43s]
        [simple-stroke-line  3h 36m 10s]
        [vgr-bitmap 69h 37m 06s]

vgr-bitmap - 38m 00s

watson - 03m 28s
        [short-status     03m 28s]

Total: 91h 32m 28s

### Resources

#### Papers

* [_Graphics Programming Principles and Algorithms_, Zongli Shi](https://www.whitman.edu/Documents/Academics/Mathematics/2017/Shi.pdf)
* [_Scanline edge-flag algorithm for antialiasing_,
Kiia Kallio](http://mlab.uiah.fi/~kkallio/antialiasing/EdgeFlagAA.pdf)
* [_A Rasterizing Algorithm for Drawing Curves_, Alois Zingl](http://members.chello.at/easyfilter/bresenham.pdf)

#### Books

* [_Introduction to Computer Graphics_, David J. Eck](https://openlibra.com/en/book/download/introduction-to-computer-graphics)

#### Web pages

* [_Basic 2D Rasterization 1_](https://magcius.github.io/xplain/article/rast1.html)
* [_Basic 2D Rasterization 2_](https://magcius.github.io/xplain/article/rast2.html)
* [_Rosetta Code: Raster graphics operations_](https://rosettacode.org/wiki/Category:Raster_graphics_operations)
* [_Even-odd algorithm_](https://handwiki.org/wiki/Even%E2%80%93odd_rule)
* [_Arc approximation with Bezier curves_](https://forum.shapeoko.com/viewtopic.php?t=9624#p70466)

#### Libraries

* [_RasterX (golang)_](https://github.com/srwiley/rasterx), flatten curves into lines.