A library of distance and occlusion generation routines

Overview

Distance/Occlusion Library + Tool

From left to right: original, signed distance with zero at 0.5, red/green SDF, delta vectors to closest boundary point.

Intro

The DistanceOcclusionLib.* files here implement a number of algorithms for

  • Distance field generation
  • Signed distance field generation
  • Scalar and directional occlusion generation

for both 2d (images) and 3d (volumes). Bitmask inputs are supported to keep memory overhead down, which is particularly important for volumes.

The included tool, distocc, which uses this lib, will process 2D images or 3D .obj files, and can output the results in a number of different formats. By default the tool uses the 'Danielsson' algorithm, and signed border initialisation, in order to generate accurate results as quickly as possible, but other algorithms can be be selected via -m (see below). These include:

FastSweep        O(n), most accurate delta technique
Danielsson       O(n), ~30% faster than FastSweep, decent accuracy
JumpFlood        O(n log n), GPU-oriented algorithm, included to check accuracy
BruteForce       O(n^2), exact, for checking other algorithms at low n.
Chamfer          O(n), has issues on diagonals. Cheapest but quality suffers.
Felzenszwalb     O(n) but much larger overhead than the others. Accurate.

The first four algorithms provide deltas from cell to closest point, which can be used to evaluate distance, but also to answer nearest-point queries, or generate Voronoi diagrams. The last two are strictly distance-only. Finally, signed distances can be optionally generated via the more classic two-pass interior/exterior algorithm, but this is twice as slow and uses twice as much memory as the default.

A reasonably efficient mesh voxeliser is included in the support file MeshSupport.cpp.

Building and Running

To build the tool, run

c++ DistanceOcclusionTool.cpp DistanceOcclusionLib.cpp -o distocc

Then to see the tool options run

./distocc

which should give you something like:

Options:
  -d: generate distance field. Methods: 0, Danielsson; 1, Fast Sweep; 2, Jump Flood; 3, Brute Force; 4, Chamfer; 5, Felzenszwalb
  -s: generate signed distance field in a single pass. Methods: as for -d but Chamfer/Felzenszwalb unsupported.
  -S: generate signed distance field via orthodox two distance field passes.
  -x: generate occlusion. Methods 0: standard, 1: no self-occlusion, 2: directional components only

  -m 
   
    : select method variant for above

  -w 
    
      [
     
      ]        : set dimensions of image source
  -W 
      
        [
        
        
         ]: set dimensions of volume source -p [
          
          
           ] : add random points to image/volume (default) -b 
           
             : add test box with the given number of sides to image/volume -f 
            
             : specify input image -t 
             
               : specify 0-255 threshold for creating mask from image -r : reverse so white is occupied rather than black -F 
              
               : use given obj file to define mask. -o 
               
                : set base name for output file(s) -v : log detailed output -c : run checks on output 
               
              
             
            
           
          
         
        
       
      
     
    
   

E.g.,

./distocc -d -p 100               # Generate a DF for 100 random points
./distocc -d -W 16 -b 6           # Generate a DF for a test box within a 16^3 volume
./distocc -s -f data/tiger.png    # Generate an SDF for the given image
./distocc -d -W 32 -F data/plant2.obj # Generate a 32^3 DF for the given 3D mesh

On Windows just include these files in your visual studio project. The code has been tested under clang, gcc, and Visual C.

You might also like...
R integration for edlib, a C/C++ library for pairwise sequence alignment using edit distance (Levenshtein distance).

edlibR Introduction Main Features Usage Background Alignment Methods Algorithmic Design Installation References edlibR: R integration for edlib The R

An implementation of [Jimenez et al., 2016] Ground Truth Ambient Occlusion, MIT license
An implementation of [Jimenez et al., 2016] Ground Truth Ambient Occlusion, MIT license

XeGTAO Introduction XeGTAO is an open source, MIT licensed, DirectX/HLSL implementation of the Practical Realtime Strategies for Accurate Indirect Occ

Authors' implementation of our SIGGRAPH Asia 2021 Technical Communications (Viewport-Resolution Independent Anti-Aliased Ray Marching on Interior Faces in Cube-Map Space) demo II. Fast real-time volume rendering for an external volume texture with mesh occlusion.
Example code for the research paper "Masked Software Occlusion Culling"; implements an efficient alternative to the hierarchical depth buffer algorithm.

MaskedOcclusionCulling This code accompanies the research paper "Masked Software Occlusion Culling", and implements an efficient alternative to the hi

Hand tuned sort routines for different C types

c 2008,2009,2021 Andrew I. Schein See LICENSE file. Update for 2021 This repo disappeared from the internet when Bitbucket turned off its mercurial se

Simdutf - Unicode routines (UTF8, UTF16): billions of characters per second.
Simdutf - Unicode routines (UTF8, UTF16): billions of characters per second.

simdutf: Unicode validation and transcoding at billions of characters per second Most modern software relies on the Unicode standard. In memory, Unico

FFTW is a free collection of fast C routines for computing the Discrete Fourier Transform in one or more dimensions

FFTW is a free collection of fast C routines for computing the Discrete Fourier Transform in one or more dimensions

Header only, single file, simple and efficient C++ library to compute the signed distance function to a triangle mesh

TriangleMeshDistance Header only, single file, simple and efficient C++11 library to compute the signed distance function to a triangle mesh. The dist

GPU 3D signed distance field generator, written with DirectX 11 compute shader
GPU 3D signed distance field generator, written with DirectX 11 compute shader

GPU SDF Generator GPU 3D signed distance field generator, written with DirectX 11 compute shader Building git clone --recursive https://github.com/Air

multispectral monitoring of a sourdough starter; esp32 eink module, scd30 co2 sensor, vl6180 distance sensor

EINK STARTER MONITOR See full blogpost here Tracks height of starter with a VL6180 i2c distance sensor, and CO2/temperature/humidity with an SCD30. A

Example program demonstrating the Meijster's distance transform algorithm.
Example program demonstrating the Meijster's distance transform algorithm.

Distance Transform The distance transform operation consist in finding the shortest distance of a black pixel to a white one. This project demonstrate

Implementation of bounded Levenshtein distance (Ukkonen)

ukkonen Implementation of bounded Levenshtein distance (Ukkonen) port this is a port of ukkonen from javascript to c++ / python via cffi. installation

Distance matching plugin

Distance Matching This plug-in is custom implementation of the Distance Matching technique which was shown by Laurent Delayen at Nucl.ai 2016. In two

LightSeq: A High Performance Library for Sequence Processing and Generation
LightSeq: A High Performance Library for Sequence Processing and Generation

LightSeq is a high performance training and inference library for sequence processing and generation implemented in CUDA. It enables highly efficient computation of modern NLP models such as BERT, GPT, Transformer, etc. It is therefore best useful for Machine Translation, Text Generation, Dialog, Language Modelling, Sentiment Analysis, and other related tasks with sequence data.

An 802.11 Frame Generation and Parsing Library in C

libwifi 802.11 Parsing / Generation library Build Status OS Architecture Linux x86_64 What is this? libwifi is a C library with a permissive license f

A procedural geometry generation library for C++11
A procedural geometry generation library for C++11

Generator - A procedural geometry generation library. The purpose of this library is to easily generate procedural meshes of geometric primitives such

A static C++ library for the generation of discrete functions on a box-shaped domain
A static C++ library for the generation of discrete functions on a box-shaped domain

A static C++ library for the generation of discrete functions on a box-shaped domain. This is especially suited for the discretization of signed distance fields.

A command line and keyboard based strategy-game written in c++, where audio-input determines the AI-strategy and lays the seed for the map-generation.
A command line and keyboard based strategy-game written in c++, where audio-input determines the AI-strategy and lays the seed for the map-generation.

Table of contents Dissonance Premise Installation Requirements Installation Quick-guide Detailed installation guide Usage Logfiles Tests Uninstall Kno

Owner
Andrew Willmott
Andrew Willmott
A lean, efficient, accurate geohash encoder and decoder library implemented in C

Geohash encoder/decoder in C A lean, efficient, accurate geohash encoder and decoder library implemented in C. It does not depend on the C standard li

Christopher Wellons 20 Nov 20, 2022
C++ library for geographical raster data analysis

Pronto Raster library The Pronto Raster Library is a C++ library to work with raster data. The core idea of the library is to make raster data accessi

Alex Hagen-Zanker 43 Oct 5, 2022
Interactive, thoroughly customizable maps in native Android, iOS, macOS, Node.js, and Qt applications, powered by vector tiles and OpenGL

Mapbox GL Native A C++ library that powers customizable vector maps in native applications on multiple platforms by taking stylesheets that conform to

Mapbox 4.2k Nov 24, 2022
C++ implementation of R*-tree, an MVR-tree and a TPR-tree with C API

libspatialindex Author: Marios Hadjieleftheriou Contact: [email protected] Revision: 1.9.3 Date: 10/23/2019 See http://libspatialindex.org for full doc

null 624 Nov 24, 2022
2D and 3D map renderer using OpenGL ES

Tangram ES Tangram ES is a C++ library for rendering 2D and 3D maps from vector data using OpenGL ES. It is a counterpart to Tangram. This repository

Tangram 746 Nov 24, 2022
Terrain Analysis Using Digital Elevation Models (TauDEM) software for hydrologic terrain analysis and channel network extraction.

TauDEM (Terrain Analysis Using Digital Elevation Models) is a suite of Digital Elevation Model (DEM) tools for the extraction and analysis of hydrolog

David Tarboton 190 Nov 22, 2022
Alternative LAZ implementation for C++ and JavaScript

What is this? Alternative LAZ implementation. It supports compilation and usage in JavaScript, usage in database contexts such as pgpointcloud and Ora

Howard Butler 55 Oct 25, 2022
A command line toolkit to generate maps, point clouds, 3D models and DEMs from drone, balloon or kite images. 📷

An open source command line toolkit for processing aerial drone imagery. ODM turns simple 2D images into: Classified Point Clouds 3D Textured Models G

OpenDroneMap 3.9k Nov 28, 2022
Computational geometry and spatial indexing on the sphere

S2 Geometry Library Overview This is a package for manipulating geometric shapes. Unlike many geometry libraries, S2 is primarily designed to work wit

Google 1.9k Nov 26, 2022
A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)

A fast algorithm for finding polygon pole of inaccessibility, the most distant internal point from the polygon outline (not to be confused with centroid), implemented as a JavaScript library. Useful for optimal placement of a text label on a polygon.

Mapbox 1.2k Dec 3, 2022