# The cl-voxelize Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

# The cl-voxelize Reference Manual

This is the cl-voxelize Reference Manual, version 0.1, generated automatically by Declt version 2.3 "Robert April" on Wed Mar 14 03:36:39 2018 GMT+0.

Next: , Previous: , Up: Top   [Contents][Index]

# 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. Since the voxelization algorithm I adopt does not work well for polygon model with holes, I use Stanfords's Volfill tool for hole filling. Additionally, I simplify the model with QSlim 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)
(let ((vertices (make-array (cl-ply:ply-element-size plyfile "vertex")))
(faces (make-array (cl-ply:ply-element-size plyfile "face"))))
(loop repeat (array-dimension vertices 0)
for i from 0
do (setf (aref vertices i)
(loop repeat (array-dimension faces 0)
for i from 0
do (setf (aref faces i)
;; 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.

## 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 - a simple command line tool for converting triangle meshes in PLY format into signed-distance volumetric grids in VRI format
• Volfill - a program for filling in holes in dense polygon meshes using an algorithm based on volumetric diffusion
• VRIP - to convert a VRI file to a new triangle mesh in PLY format using the embedding implementation of Marching Cubes
• QSlim - a program to simplify polygon model with QEM(Quadratic Error Metric)
• Blender - 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 (c) 2014 Masayuki Takagi (kamonama@gmail.com)

Next: , Previous: , Up: Top   [Contents][Index]

## 2 Systems

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

Previous: , Up: Systems   [Contents][Index]

### 2.1 cl-voxelize

Author

Masayuki Takagi

LLGPL

Description

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

Long Description

# cl-voxelize

[![Build Status](https://travis-ci.org/takagi/cl-voxelize.svg)](https://travis-ci.org/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)
(let ((vertices (make-array (cl-ply:ply-element-size plyfile "vertex")))
(faces (make-array (cl-ply:ply-element-size plyfile "face"))))
(loop repeat (array-dimension vertices 0)
for i from 0
do (setf (aref vertices i)
(loop repeat (array-dimension faces 0)
for i from 0
do (setf (aref faces i)
;; 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:

## 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 (c) 2014 Masayuki Takagi (kamonama@gmail.com)

Version

0.1

Dependency

alexandria

Source

cl-voxelize.asd (file)

Component

src (module)

Next: , Previous: , Up: Top   [Contents][Index]

## 3 Modules

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

Previous: , Up: Modules   [Contents][Index]

### 3.1 cl-voxelize/src

Parent

cl-voxelize (system)

Location

src/

Component

cl-voxelize.lisp (file)

Next: , Previous: , Up: Top   [Contents][Index]

## 4 Files

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

Previous: , Up: Files   [Contents][Index]

### 4.1 Lisp

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 4.1.1 cl-voxelize.asd

Location

cl-voxelize.asd

Systems

cl-voxelize (system)

Packages

Previous: , Up: Lisp files   [Contents][Index]

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

Parent

src (module)

Location

src/cl-voxelize.lisp

Packages
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 5 Packages

Packages are listed by definition order.

Next: , Previous: , Up: Packages   [Contents][Index]

### 5.1 cl-voxelize-asd

Source

cl-voxelize.asd

Use List
• asdf/interface
• common-lisp

Previous: , Up: Packages   [Contents][Index]

### 5.2 cl-voxelize

Source

cl-voxelize.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 6 Definitions

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

Next: , Previous: , Up: Definitions   [Contents][Index]

### 6.1 Exported definitions

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 6.1.1 Macros

Macro: do-voxelize ((X Y Z) TRIANGLES DELTA &key ANTIALIAS-P) &body BODY
Package
Source

cl-voxelize.lisp (file)

Previous: , Up: Exported definitions   [Contents][Index]

#### 6.1.2 Functions

Function: voxelize TRIANGLES DELTA &key ANTIALIAS-P
Package
Source

cl-voxelize.lisp (file)

Previous: , Up: Definitions   [Contents][Index]

### 6.2 Internal definitions

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.1 Special variables

Special Variable: *inside-eps*
Package
Source

cl-voxelize.lisp (file)

Special Variable: *max-capacity*
Package
Source

cl-voxelize.lisp (file)

Special Variable: *max-depth*
Package
Source

cl-voxelize.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.2 Macros

Macro: with-triangle ((X0 Y0 Z0) (X1 Y1 Z1) (X2 Y2 Z2)) TRIANGLE &body BODY
Package
Source

cl-voxelize.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.3 Functions

Function: %%do-voxelize FN TRIANGLES DELTA
Package
Source

cl-voxelize.lisp (file)

Function: %%do-voxelize-antialias FN TRIANGLES DELTA
Package
Source

cl-voxelize.lisp (file)

Function: %do-voxelize FN TRIANGLES DELTA ANTIALIAS-P
Package
Source

cl-voxelize.lisp (file)

Function: %empty-quadtree X0 Y0 X1 Y1 DEPTH
Package
Source

cl-voxelize.lisp (file)

Function: %make-quadtree &key (TRIANGLES TRIANGLES) (NW NW) (NE NE) (SW SW) (SE SE) (BOUNDARY BOUNDARY) (DEPTH DEPTH)
Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Function: empty-quadtree X0 Y0 X1 Y1
Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Function: inside-p Z INTERSECTIONS-Z
Package
Source

cl-voxelize.lisp (file)

Function: intersection-z X Y TRIANGLE
Package
Source

cl-voxelize.lisp (file)

Function: intersections-z X Y TRIANGLES
Package
Source

cl-voxelize.lisp (file)

Function: or! &rest ARGS
Package
Source

cl-voxelize.lisp (file)

Function: point-intersect-p BOUNDARY X Y
Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Package
Source

cl-voxelize.lisp (file)

Function: triangle-bounding-box TRIANGLE
Package
Source

cl-voxelize.lisp (file)

Function: triangle-intersect-p BOUNDARY TRIANGLE
Package
Source

cl-voxelize.lisp (file)

Function: triangles-bounding-box TRIANGLES
Package
Source

cl-voxelize.lisp (file)

Previous: , Up: Internal definitions   [Contents][Index]

#### 6.2.4 Structures

Package
Source

cl-voxelize.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: triangles

Writers

Slot: nw

Writers

Slot: ne

Writers

Slot: sw

Writers

Slot: se

Writers

Slot: boundary

Writers

Slot: depth

Writers

Previous: , Up: Top   [Contents][Index]

## Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.1 Concepts

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.2 Functions

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

Next: , Previous: , Up: Indexes   [Contents][Index]