* c.thi.ng

** Contents                                                        :toc_3_gh:
 - [[#cthing][c.thi.ng]]
     - [[#overview][Overview]]
         - [[#data-structures][Data structures]]
         - [[#memory-management][Memory management]]
         - [[#math][Math]]
         - [[#simulation][Simulation]]
         - [[#geometry][Geometry]]
     - [[#requirements][Requirements]]
     - [[#dependencies][Dependencies]]
     - [[#examples][Examples]]
         - [[#build-all-examples][Build all examples]]
         - [[#1d2d-cellular-automata][1D/2D Cellular automata]]
         - [[#convex-hull][Convex Hull]]
         - [[#diffusion-limited-aggregation][Diffusion-Limited Aggregation]]
         - [[#glfw-desktop--emscripten][GLFW (desktop & emscripten)]]
         - [[#poisson-disc-sampling-image-conversion][Poisson disc sampling image conversion]]
         - [[#polygon-clipping-greiner-hormann][Polygon clipping (Greiner-Hormann)]]
         - [[#polygon-offsetting][Polygon offsetting]]
         - [[#verlet-physics][Verlet physics]]
         - [[#voronoi][Voronoi]]
     - [[#build--test][Build & test]]
     - [[#build-static-library][Build static library]]
     - [[#build-source-x-ref][Build source x-ref]]
     - [[#disassemble--list-symbols][Disassemble & list symbols]]
     - [[#compile-with-emscripten][Compile with emscripten]]
         - [[#build-as-library-for-emcc][Build as library for emcc]]
         - [[#run-test-suite-in-browser][Run test suite in browser]]
     - [[#build-customization][Build customization]]
     - [[#contributors][Contributors]]
     - [[#license][License]]

** Overview

WIP

*** Data structures
- [[./src/data/adjacency.h][Adjacency matrix]] (undirected graph)
- Cons list ([[./src/data/consrc.h][with]] & [[./src/data/cons.h][without]] reference counting)
- [[./src/data/hashset.h][Hashset]] (generic)
- [[./src/data/hashtable.h][Hashtable]] (generic)
- [[./src/data/object.h][Object wrapper]] & protocol dispatch
- [[./src/data/octree.h][Octree]]
- [[./src/data/quadtree.h][Quadtree]]
- [[./src/data/spatialgrid.h][Spatial grid]] (1D, 2D, 3D)
- [[./src/data/soa.h][Structure of Array]] (SOA) wrapper & vector ops (SSE, AVX & serial)

*** Memory management

- [[./src/mem/mpool.h][Memory pool]] (auto-growth, manual compacts)
- [[./src/mem/ref.h][Reference counting]] utils

*** Math

- [[./src/math/hashfn.h][Murmur Hash]] (32bit version)
- [[./src/math/poisson.h][Poisson disc sampling]]

*** Simulation
- [[./src/sim/ca.h][Cellular Automata]] (1D/2D, w/ adjustable kernel sizes)
- [[./src/sim/verlet.h][Verlet physics]] (2D particles)

*** Geometry

- Convex Hull (2D)
- [[./src/math/matrix.h][Matrix 4x4]] (w/ opt SSE impls)
- [[./src/math/vec.h][Vec2/3/4]] (w/ opt SSE impls)
- [[./src/math/swizzle.h][Vector swizzling]]
- [[./src/geom/clip.h][Line clipping]] (Liang-Barsky)
- [[./src/geom/polygon.h][Polygon]] (2D)
  - [[#polygon-clipping-greiner-hormann][Polygon clipping]] (Greiner-Hormann)
  - [[#polygon-offsetting][Polygon offsetting / insetting]]
- [[./src/geom/voronoi.h][Voronoi]] (2D)
...

TBD
** Requirements

- [[https://premake.github.io/][Premake5]]
- [[http://www.gnu.org/software/make/][GNU Make]]
- GCC / Clang (w/ C11 support)
- [[https://github.com/emcrisostomo/fswatch][fswatch]] (only needed for =./autotest= runner)
- [[http://emscripten.org][emscripten]] & [[http://nodejs.org][node]] (only needed for asm.js x-compilation via
  =./compile= & =./compile-bc=)
- [[http://cscope.sourceforge.net/][cscope]] (only needed for =./browse=)
- [[https://wiki.gnome.org/Projects/LibRsvg][rsvg]] & [[http://ffmpeg.org/][ffmpeg]] (only needed for =./makevideo=)

** Dependencies

The library itself has no 3rd party dependencies. Some of the examples
however use these additional libs:

- [[https://github.com/thi-ng/ct-head][ct-head]] (included as submodule)
- [[https://github.com/nothings/stb][stb_image]] (bundled under =/examples/common=)
- [[http://www.glfw.org/][GLFW3.2+]]

** Examples
*** Build all examples

#+BEGIN_SRC shell
git clone --recursive https://github.com/thi-ng/c-thing

premake5 gmake
make config=release_sse
#+END_SRC

*** 1D/2D Cellular automata

[[./examples/ca/ca1d.c][Source (1D)]] | [[./examples/ca/ca2d.c][Source (2D)]]

[[./assets/ca1d.png]]

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-ca1d

# 1D sample invocation w/ Wolfram Rule 105
# Result will be written to /assets/ca-105.svg
# args: rule states kernelwidth res
bin/release/ex-ca1d 105 2 1

# Output all 255 wolfram rules
for i in {1..255}; do bin/release/ex-ca1d $i 2 1 128; done

# Another example w/ bigger kernel size
bin/release/ex-ca1d 522530942 32 3 128

# build 2D example app
make config=release_sse ex-ca2d

# frames will be written to /assets
bin/release/ex-ca2d
#+END_SRC

*** Convex Hull

[[./examples/convexhull/main.c][Source]]

[[./assets/chull.png]]

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-chull && bin/release/ex-chull > assets/chull.svg
#+END_SRC

*** Diffusion-Limited Aggregation

[[./examples/dla/main.c][Source]]

[[./assets/dla.png]]

[[./assets/dla-color.png]]

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-dla && bin/release/ex-dla > assets/dla.svg
#+END_SRC

*** GLFW (desktop & emscripten)

[[./examples/glfw/ex01.c][Source]] | [[http://c.thi.ng/glfw/01/][Online demo]]

[[./assets/glfw01.jpg]]

See [[#dependencies][dependencies]] for details...

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-glfw01 && bin/release/ex-glfw01
#+END_SRC

*Note:* Desktop version currently only has build settings for OSX.

To compile with Emscripten & open in browser: [[http://localhost:8000/glfw.html][http://localhost:8000/glfw.html]]

#+BEGIN_SRC shell
  # build LLVM bitcode of library (./obj/libcthing.bc)
  ./compile-bc

  # compile example for browser & link with lib
  emcc -O2 -DCT_FEATURE_LOG -DCT_NO_EXPORT -DNDEBUG \
       -s 'USE_GLFW=3' \
       -s 'ELIMINATE_DUPLICATE_FUNCTIONS=1' \
       -s 'NO_EXIT_RUNTIME=1' \
       --llvm-lto 1 \
       --closure 1 \
       --preload-file assets/suzanne.stl \
       -Isrc -Iext \
       -o glfw.html \
       examples/glfw/*.c obj/libcthing.bc

  # launch server
  python -m SimpleHTTPServer
#+END_SRC

*** Poisson disc sampling image conversion

[[./examples/poisson/main.c][Source]]

[[./assets/iris-poisson.png]]

#+BEGIN_SRC shell
  # build library & example app
  make config=release_sse ex-poisson

  # show usage
  bin/release/ex-poisson
  # Missing input file
  # Usage:  ex-poisson [options] image [ > out.svg ]
  #   -b HEX    bg color (default: ffffff)
  #   -f HEX    fg color (default: 0000ff)
  #   -g FLOAT  gamma (default: 3.00)
  #   -i        invert (also swaps fg/bg) (default: no)
  #   -m FLOAT  min distance (default: 2.00)
  #   -x FLOAT  max distance (default: 10.00)
  #   -r FLOAT  dot radius (default: 1.00)
  #   -q INT    quality (default: 100)
  #   -t        output points as text only (default: no)

  # concrete example (for image size roughly 700x1000px)
  bin/release/ex-poisson -g 1.25 -q 500 -m 1.5 -x 16 assets/iris.jpg > assets/iris.svg
#+END_SRC

*** Polygon clipping (Greiner-Hormann)

[[./examples/polyclip/main.c][Source]]

[[./assets/polyclip.png]]

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-polyclip && bin/release/ex-polyclip > polyclip.svg
#+END_SRC

*** Polygon offsetting

[[./examples/polyoffset/main.c][Source]]

[[./assets/polyoffset-all-small.png]]

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-polyclip && bin/release/ex-polyoffset > polyoffset.svg
#+END_SRC

*** Verlet physics

[[./examples/verlet/main.c][Source]] | [[https://www.instagram.com/p/BG2W1NHEGdk][Video example 1]] | [[https://www.instagram.com/p/BG2jR9jkGXi][Video example 2]]

[[./assets/verlet.png]]

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-verlet && bin/release/ex-verlet

# ouputs are stored as SVG sequence in /assets
# use script below to convert to mp4 (requires rsvg & ffmpeg) -> out.mp4
./makevideo verlet
#+END_SRC

*** Voronoi

[[./examples/voronoi/main.c][Source]]

[[./assets/poisson-voronoi.png]]

#+BEGIN_SRC shell
# build library & example app
make config=release_sse ex-voronoi && bin/release/ex-voronoi
#+END_SRC

**** Piping in points from external process

[[./assets/iris-voronoi.png]]

The image above was generated by first sampling a JPG with the [[#poisson-disc-sampling-image-conversion][poisson]]
example tool (configured to output points as text) and then piping
these points into the voronoi example.

#+BEGIN_SRC shell
bin/release/ex-poisson -b 00ffff -f 0000ff -q 500 -m 2 -x 16 -t assets/iris.jpg | \
bin/release/ex-voronoi -p -w 757 -h 450 > iris-voronoi.svg
#+END_SRC

** Build & test

Get further help for autogenerated =Makefile=:

#+BEGIN_SRC shell
  # checkout with submodules
  git clone --recursive https://github.com/thi-ng/c-thing

  # generate Makefiles
  premake5 gmake

  make help
  # Usage: make [config=name] [target]
  # CONFIGURATIONS:
  #   debug_sse
  #   debug_no_sse
  #   release_sse
  #   release_no_sse
  # 
  # TARGETS:
  #    all (default)
  #    clean
  #    test
  #    test_asan
  #    lib
  #    ex-ca1d
  #    ex-ca2d
  #    ex-chull
  #    ex-dla
  #    ex-poisson
  #    ex-verlet
  #    ex-verlet-pack
  #    ex-polyclip
  #    ex-polyoffset
  #    ex-voronoi
  #    ex-glfw01
#+END_SRC

#+BEGIN_SRC shell
# build & run tests manually
make config=debug_sse test && bin/debug/test
# or
make config=release_sse test && bin/release/test

# ...or use auto test w/ file watcher
# tests re-run automatically if files in /src or /test are changed
# if no args given, compiles w/ address sanitizer enabled
./autotest
# ...or provide build config (target config profile)
# (only test_msan requires linux & clang, other profiles also build w/ gcc etc.)
./autotest test_msan
./autotest test_asan debug
./autotest test release no_sse
#+END_SRC

** Build static library

#+BEGIN_SRC shell
make config=debug_sse lib
# or
make config=release_sse lib
#+END_SRC

** Build source x-ref

#+BEGIN_SRC shell
brew install cscope

./browse
#+END_SRC

** Disassemble & list symbols

#+BEGIN_SRC shell
# display disassembly (OSX)
otool -jtV bin/release/libcthing.a | less

# display global symbols defined in lib
nm -g -j bin/release/libcthing.a | grep --color=never _ct_
#+END_SRC

** Compile with emscripten
*** Build as library for emcc

Also see [[#glfw-desktop--emscripten][GLFW example]] for further details...

#+BEGIN_SRC shell
  # build LLVM bitcode version for future linking with other sources
  ./compile-bc
#+END_SRC

*** Run test suite in browser
#+BEGIN_SRC shell
  # help / usage
  ./compile -h
  # Usage:
  #   -a     : separate asm.js output
  #   -c     : enable Closure compiler step
  #   -d     : remove duplicate functions
  #   -D SYM : add define
  #   -h     : show this help
  #   -k     : enable runtime checks
  #   -m     : enable memory checks
  #   -s     : enable SSE (SIMD.js)
  #   -t     : include tests

  # compile with tests, closure pass & remove duplicate fns
  ./compile -tdc

  python3 -m http.server

  # in browser dev console - http://localhost:8000/
  cthing(); cthing._main()
#+END_SRC

** Build customization

This project utilizes feature macros defined in the [[https://github.com/thi-ng/ct-head][thi.ng/ct-head]]
project. Please see documentation there for further reference to
customize behavior.

** Contributors

| *Name*          | *Role*                          | *Website* |
| [[mailto:k@thi.ng][Karsten Schmidt]] | initiator & principal developer | [[http://thi.ng][thi.ng]]    |

** License

This project is open source and licensed under the [[http://www.apache.org/licenses/LICENSE-2.0][Apache Software License 2.0]].