GitPlanet

Cheap and reliable Node.js hosting starts at $3/month, and $1/month static HTML hosting

Created with love in Canada, visit hostnodejs.com today

Feel like to post an Ad? Learn Details
All Projects → thi-ng → C Thing

thi-ng / C Thing

Licence: apache-2.0
Geometry related data structures (C11)

Programming Languages

c
50402 projects - #5 most used programming language
  • 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:[email protected]][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]].

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].