The cl-voxelize Reference Manual

This is the cl-voxelize Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sat Dec 03 20:51:06 2022 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 cl-voxelize

Convert polygon models into voxel models for particle-based physics simulation.

Author

Masayuki Takagi

License

LLGPL

Long Description

# cl-voxelize

[![Build Status](https://travis-ci.org/takagi/cl-voxelize.svg)](https://travis-ci.org/takagi/cl-voxelize)
[![Coverage Status](https://coveralls.io/repos/takagi/cl-voxelize/badge.svg)](https://coveralls.io/r/takagi/cl-voxelize)

Cl-voxelize is a library to convert polygon models into voxel models for particle-based physics simulation.

## Example

Here shows an example of how to use cl-voxelize. With the Stanford bunny’s ply file, I illustrate how to load, voxelize and visualize it.

As an example data, use the Stanford bunny’s ply file from [the Stanford 3D Scanning Repository](https://graphics.stanford.edu/data/3Dscanrep/). Since the voxelization algorithm I adopt does not work well for polygon model with holes, I use Stanfords’s [Volfill](http://graphics.stanford.edu/software/volfill/) tool for hole filling. Additionally, I simplify the model with [QSlim](http://www.cs.cmu.edu/afs/cs/Web/People/garland/quadrics/qslim.html) for reducing voxelization time. This simplification make no effect on the result voxels in this case, because relatively coarse resolution is enough for particle-based simulation. A hole-filled and simplified Stanford bunny’s ply file is placed in this repository.

A hole-filled and simplified Stanford bunny in PLY format:
* https://github.com/takagi/cl-voxelize/blob/master/examples/bunny.ply

Read the Stanford bunny’s .ply file and convert it to a list of triangles which is input to ‘voxelize‘ function.

(defun triangles (vertices faces)
;; make a list of triangles from vertex array and face array
(let (ret)
(dotimes (i (array-dimension faces 0))
(let ((face (aref faces i)))
(let ((v0 (aref vertices (nth face 0)))
(v1 (aref vertices (nth face 1)))
(v2 (aref vertices (nth face 2))))
(push (list v0 v1 v2) ret))))
ret))

(defun ply-to-triangles (path)
(cl-ply:with-ply-for-reading (plyfile path)
(let ((vertices (make-array (cl-ply:ply-element-size plyfile "vertex")))
(faces (make-array (cl-ply:ply-element-size plyfile "face"))))
;; read vertices
(loop repeat (array-dimension vertices 0)
for i from 0
do (setf (aref vertices i)
(cl-ply:ply-read-element plyfile "vertex")))
;; read faces
(loop repeat (array-dimension faces 0)
for i from 0
do (setf (aref faces i)
(car (cl-ply:ply-read-element plyfile "face"))))
;; get triangles from vertices and faces
(triangles vertices faces))))

Voxelize the obtained triangles and get voxels as the result. The voxels are represented as a list of their center points.

(let ((triangles (ply-to-triangles "/path/to/bunny.ply"))
(delta 0.0045))
(voxelize triangles delta))

As an illustration, I show you the result voxels rendered with POV-Ray.

![Voxelized Stanford bunny](https://raw.githubusercontent.com/takagi/cl-voxelize/master/examples/bunny.png)

## Installation

You can install cl-voxelize via Quicklisp:

(ql:quickload :cl-voxelize)

## API

### [Function] voxelize

VOXELIZE triangles delta &optional antialias-p => voxels

Returns ‘voxels‘ with given ‘triangles‘ which is a list of triangles. ‘delta‘ is a floating point which specifies the resolution of voxels. ‘voxels‘ is represented as a list of voxels’ center points. If ‘antialias-p‘ is true, the result is antialiased.

### [Macro] do-voxelize

DO-VOXELIZE ((x y z) triangles delta &optional antialias-p) &body body => result

‘do-voxelize‘ is a ‘voxelize‘’s counterpart in ‘do-‘ style. Voxels’ center points are bound to ‘x‘, ‘y‘ and ‘z‘ symbols.

## FAQ

**Q. What are file formats to be voxelized?**

A. Any file formats are supported as far as they can be converted to fit cl-voxelize’s API interface.

**Q. How large polygon model? How long does it take to voxelize?**

A. Currently I do not set performance goal because relatively coarse resolution is enough for particle-based simulation.

**Q. Are there any restrictions for polygon models to be voxelized?**

A. The voxelization algorithm I adopt does not work well for polygon models with holes.

**Q. In a quadtree used in this implementation, how is a triangle which intersects with multiple sub-quadtrees treated?**

A. There are roughly two options how to treat a triangle which intersects with multiple sub-quadtrees:
* A triangle belongs to all sub-quadtrees with which it intersects
* A triangle belongs to only one of sub-quadtrees with which it intersects

To properly determine inside/outside in this case, I choose the former.

**Q. If a ray goes on a shared side of triangles through, is inside/outside rightly determined?**

A. To determine inside/outside in such case, duplicated intersections are removed.

**Q. What are tools used to make the Stanford bunny’s ply file in Example section?**

A. Tools I used were following:
* [ply2vri](http://grail.cs.washington.edu/software-data/ply2vri/) - a simple command line tool for converting triangle meshes in PLY format into signed-distance volumetric grids in VRI format
* [Volfill](http://graphics.stanford.edu/software/volfill/) - a program for filling in holes in dense polygon meshes using an algorithm based on volumetric diffusion
* [VRIP](http://graphics.stanford.edu/software/vrip/) - to convert a VRI file to a new triangle mesh in PLY format using the embedding implementation of Marching Cubes
* [QSlim](http://www.cs.cmu.edu/afs/cs/Web/People/garland/quadrics/qslim.html) - a program to simplify polygon model with QEM(Quadratic Error Metric)
* [Blender](http://www.blender.org/) - just for converting PLY format from/to OBJ format to apply QSlim

## Reference

* S. Thon, G. Gresquiere, and R. Raffin. "A low cost antialiased space filled voxelization of polygonal objects."

## Author

* Masayuki Takagi (kamonama@gmail.com)

## Copyright

Copyright (c) 2014 Masayuki Takagi (kamonama@gmail.com)

## License

Licensed under the LLGPL License.

Version

0.1

Dependency

alexandria (system).

Source

cl-voxelize.asd.

Child Component

src (module).


3 Modules

Modules are listed depth-first from the system components tree.


3.1 cl-voxelize/src

Source

cl-voxelize.asd.

Parent Component

cl-voxelize (system).

Child Component

cl-voxelize.lisp (file).


4 Files

Files are sorted by type and then listed depth-first from the systems components trees.


4.1 Lisp


4.1.1 cl-voxelize/cl-voxelize.asd

Source

cl-voxelize.asd.

Parent Component

cl-voxelize (system).

ASDF Systems

cl-voxelize.

Packages

cl-voxelize-asd.


4.1.2 cl-voxelize/src/cl-voxelize.lisp

Source

cl-voxelize.asd.

Parent Component

src (module).

Packages

cl-voxelize.

Public Interface
Internals

5 Packages

Packages are listed by definition order.


5.1 cl-voxelize-asd

Source

cl-voxelize.asd.

Use List
  • asdf/interface.
  • common-lisp.

5.2 cl-voxelize

Source

cl-voxelize.lisp.

Use List

common-lisp.

Public Interface
Internals

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


6.1 Public Interface


6.1.1 Macros

Macro: do-voxelize (((x y z) triangles delta &key antialias-p) &body body)
Package

cl-voxelize.

Source

cl-voxelize.lisp.


6.1.2 Ordinary functions

Function: voxelize (triangles delta &key antialias-p)
Package

cl-voxelize.

Source

cl-voxelize.lisp.


6.2 Internals


6.2.1 Special variables

Special Variable: *inside-eps*
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Special Variable: *max-capacity*
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Special Variable: *max-depth*
Package

cl-voxelize.

Source

cl-voxelize.lisp.


6.2.2 Macros

Macro: with-triangle (((x0 y0 z0) (x1 y1 z1) (x2 y2 z2)) triangle &body body)
Package

cl-voxelize.

Source

cl-voxelize.lisp.


6.2.3 Ordinary functions

Function: %%do-voxelize (fn triangles delta)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: %%do-voxelize-antialias (fn triangles delta)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: %do-voxelize (fn triangles delta antialias-p)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: %empty-quadtree (x0 y0 x1 y1 depth)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: %make-quadtree (&key triangles nw ne sw se boundary depth)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: copy-quadtree (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: devide-quadtree (quadtree)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: empty-quadtree (x0 y0 x1 y1)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: insert-quadtree (quadtree triangle)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: inside-p (z intersections-z)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: intersection-z (x y triangle)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: intersections-z (x y triangles)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: or! (&rest args)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: point-intersect-p (boundary x y)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: quadtree (triangles)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Reader: quadtree-boundary (instance)
Writer: (setf quadtree-boundary) (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Target Slot

boundary.

Reader: quadtree-depth (instance)
Writer: (setf quadtree-depth) (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Target Slot

depth.

Function: quadtree-leaf-p (quadtree)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: quadtree-max-capacity-p (quadtree)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: quadtree-max-depth-p (quadtree)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Reader: quadtree-ne (instance)
Writer: (setf quadtree-ne) (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Target Slot

ne.

Function: quadtree-node-p (quadtree)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Reader: quadtree-nw (instance)
Writer: (setf quadtree-nw) (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Target Slot

nw.

Function: quadtree-p (object)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: quadtree-root-p (quadtree)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Reader: quadtree-se (instance)
Writer: (setf quadtree-se) (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Target Slot

se.

Reader: quadtree-sw (instance)
Writer: (setf quadtree-sw) (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Target Slot

sw.

Reader: quadtree-triangles (instance)
Writer: (setf quadtree-triangles) (instance)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Target Slot

triangles.

Function: query-quadtree (quadtree x y)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: triangle-bounding-box (triangle)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: triangle-intersect-p (boundary triangle)
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Function: triangles-bounding-box (triangles)
Package

cl-voxelize.

Source

cl-voxelize.lisp.


6.2.4 Structures

Structure: quadtree
Package

cl-voxelize.

Source

cl-voxelize.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: triangles
Readers

quadtree-triangles.

Writers

(setf quadtree-triangles).

Slot: nw
Readers

quadtree-nw.

Writers

(setf quadtree-nw).

Slot: ne
Readers

quadtree-ne.

Writers

(setf quadtree-ne).

Slot: sw
Readers

quadtree-sw.

Writers

(setf quadtree-sw).

Slot: se
Readers

quadtree-se.

Writers

(setf quadtree-se).

Slot: boundary
Readers

quadtree-boundary.

Writers

(setf quadtree-boundary).

Slot: depth
Readers

quadtree-depth.

Writers

(setf quadtree-depth).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
C   D   E   F   I   M   O   P   Q   T   V   W  
Index Entry  Section

%
%%do-voxelize: Private ordinary functions
%%do-voxelize-antialias: Private ordinary functions
%do-voxelize: Private ordinary functions
%empty-quadtree: Private ordinary functions
%make-quadtree: Private ordinary functions

(
(setf quadtree-boundary): Private ordinary functions
(setf quadtree-depth): Private ordinary functions
(setf quadtree-ne): Private ordinary functions
(setf quadtree-nw): Private ordinary functions
(setf quadtree-se): Private ordinary functions
(setf quadtree-sw): Private ordinary functions
(setf quadtree-triangles): Private ordinary functions

C
copy-quadtree: Private ordinary functions

D
devide-quadtree: Private ordinary functions
do-voxelize: Public macros

E
empty-quadtree: Private ordinary functions

F
Function, %%do-voxelize: Private ordinary functions
Function, %%do-voxelize-antialias: Private ordinary functions
Function, %do-voxelize: Private ordinary functions
Function, %empty-quadtree: Private ordinary functions
Function, %make-quadtree: Private ordinary functions
Function, (setf quadtree-boundary): Private ordinary functions
Function, (setf quadtree-depth): Private ordinary functions
Function, (setf quadtree-ne): Private ordinary functions
Function, (setf quadtree-nw): Private ordinary functions
Function, (setf quadtree-se): Private ordinary functions
Function, (setf quadtree-sw): Private ordinary functions
Function, (setf quadtree-triangles): Private ordinary functions
Function, copy-quadtree: Private ordinary functions
Function, devide-quadtree: Private ordinary functions
Function, empty-quadtree: Private ordinary functions
Function, insert-quadtree: Private ordinary functions
Function, inside-p: Private ordinary functions
Function, intersection-z: Private ordinary functions
Function, intersections-z: Private ordinary functions
Function, or!: Private ordinary functions
Function, point-intersect-p: Private ordinary functions
Function, quadtree: Private ordinary functions
Function, quadtree-boundary: Private ordinary functions
Function, quadtree-depth: Private ordinary functions
Function, quadtree-leaf-p: Private ordinary functions
Function, quadtree-max-capacity-p: Private ordinary functions
Function, quadtree-max-depth-p: Private ordinary functions
Function, quadtree-ne: Private ordinary functions
Function, quadtree-node-p: Private ordinary functions
Function, quadtree-nw: Private ordinary functions
Function, quadtree-p: Private ordinary functions
Function, quadtree-root-p: Private ordinary functions
Function, quadtree-se: Private ordinary functions
Function, quadtree-sw: Private ordinary functions
Function, quadtree-triangles: Private ordinary functions
Function, query-quadtree: Private ordinary functions
Function, triangle-bounding-box: Private ordinary functions
Function, triangle-intersect-p: Private ordinary functions
Function, triangles-bounding-box: Private ordinary functions
Function, voxelize: Public ordinary functions

I
insert-quadtree: Private ordinary functions
inside-p: Private ordinary functions
intersection-z: Private ordinary functions
intersections-z: Private ordinary functions

M
Macro, do-voxelize: Public macros
Macro, with-triangle: Private macros

O
or!: Private ordinary functions

P
point-intersect-p: Private ordinary functions

Q
quadtree: Private ordinary functions
quadtree-boundary: Private ordinary functions
quadtree-depth: Private ordinary functions
quadtree-leaf-p: Private ordinary functions
quadtree-max-capacity-p: Private ordinary functions
quadtree-max-depth-p: Private ordinary functions
quadtree-ne: Private ordinary functions
quadtree-node-p: Private ordinary functions
quadtree-nw: Private ordinary functions
quadtree-p: Private ordinary functions
quadtree-root-p: Private ordinary functions
quadtree-se: Private ordinary functions
quadtree-sw: Private ordinary functions
quadtree-triangles: Private ordinary functions
query-quadtree: Private ordinary functions

T
triangle-bounding-box: Private ordinary functions
triangle-intersect-p: Private ordinary functions
triangles-bounding-box: Private ordinary functions

V
voxelize: Public ordinary functions

W
with-triangle: Private macros