The cl-catmull-rom-spline Reference Manual

Table of Contents

The cl-catmull-rom-spline Reference Manual

This is the cl-catmull-rom-spline Reference Manual, version 0.1.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Apr 28 10:48:56 2020 GMT+0.

1 Introduction

CL-Catmull-Rom-Spline

This is a Common Lisp library implementing Catmull-Rom splines as described by this paper: http://algorithmist.net/docs/catmullrom.pdf

Splines provide a way to designate an ordered list of control points (knots) in a 2D plane and find a "smooth" path that travels through or around the points. CR splines have particularly nice properties for game applications:

• The path actually goes through each knot
• If you relocate a knot then only the path near the knot changes
• You can have a looping path by using the same knot as the start and end point
• Paths (usually) look nicely smooth enough despite not being C²-continuous like cubic splines
• Cheap to calculate

System Outline

:cl-catmull-rom-spline is the main library code. The typical usage is to construct a new Spline object, add some knots, then repeatedly ask for the next point along the spline path.

:cl-catmull-rom-spline/test contains a few unit tests.

:cl-catmull-rom-spline/example contains a small SDL1-backed graphical example to show off adding knots and animating an object following the path. Simply load the system and execute (spline-example:launch). Note that testing on an Ubuntu 16 system, even after apt-getting libsdl1.2-dev, this system was raising an error on load trying to find libSDL_gfx. Continuing the load and launching still seemed to work anyway, though. But it's also resolveable by apt-getting libsdl-gfx1.2-dev.

License

This library is free software. The author disclaims copyright to this project's source code. All files in this project, unless explicitly stated otherwise, are in the public domain and distributed without any warranty. If you live in a country that does not recognize grants to the public domain, you may consider this licensed under the CC0.

Contributing

Though responses may not be very quick, contributions from pull requests or emailed patches are welcome, as are drive-by code reviews or reported issues. If you don't agree to have the changes released in the public domain, please mark them explicitly otherwise.

2 Systems

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

2.1 cl-catmull-rom-spline

Author

Kevin Secretan <github@thejach.com>

License

Public Domain

Description

Catmull-Rom Spline

Version

0.1.0

Source

cl-catmull-rom-spline.asd (file)

Component

spline.lisp (file)

3 Files

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

3.1 Lisp

3.1.1 cl-catmull-rom-spline.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/cl-catmull-rom-spline-20200325-git/cl-catmull-rom-spline.asd

Systems

cl-catmull-rom-spline (system)

3.1.2 cl-catmull-rom-spline/spline.lisp

Parent

cl-catmull-rom-spline (system)

Location

spline.lisp

Packages

cl-catmull-rom-spline

Exported Definitions

• add-knot (generic function)
• add-knot (method)
• next-point (generic function)
• next-point (method)
• reset (generic function)
• reset (method)
• scale (generic function)
• scale (method)
• spline (class)

Internal Definitions

• coeff->idx (function)
• coeff-x (function)
• coeff-y (function)
• coeffs (method)
• (setf coeffs) (method)
• coeffs-computed? (method)
• (setf coeffs-computed?) (method)
• compute-coefficients (function)
• compute-endpoints (method)
• cur-knot (method)
• (setf cur-knot) (method)
• cur-t (method)
• (setf cur-t) (method)
• dot-product (function)
• dt (method)
• (setf dt) (method)
• endpoints-computed? (method)
• (setf endpoints-computed?) (method)
• knot-i-x (macro)
• knot-i-y (macro)
• knots (method)
• (setf knots) (method)
• knots-count (method)
• (setf knots-count) (method)
• set-coeffs (function)

4 Packages

Packages are listed by definition order.

4.1 cl-catmull-rom-spline

Source

spline.lisp (file)

Nicknames

• com.thejach.cl-catmull-rom-spline
• cr-spline

Use List

common-lisp

Exported Definitions

• add-knot (generic function)
• add-knot (method)
• next-point (generic function)
• next-point (method)
• reset (generic function)
• reset (method)
• scale (generic function)
• scale (method)
• spline (class)

Internal Definitions

• coeff->idx (function)
• coeff-x (function)
• coeff-y (function)
• coeffs (generic function)
• coeffs (method)
• (setf coeffs) (method)
• (setf coeffs) (generic function)
• coeffs-computed? (generic function)
• coeffs-computed? (method)
• (setf coeffs-computed?) (method)
• (setf coeffs-computed?) (generic function)
• compute-coefficients (function)
• compute-endpoints (generic function)
• compute-endpoints (method)
• cur-knot (generic function)
• cur-knot (method)
• (setf cur-knot) (method)
• (setf cur-knot) (generic function)
• cur-t (generic function)
• cur-t (method)
• (setf cur-t) (method)
• (setf cur-t) (generic function)
• dot-product (function)
• dt (generic function)
• dt (method)
• (setf dt) (method)
• (setf dt) (generic function)
• endpoints-computed? (generic function)
• endpoints-computed? (method)
• (setf endpoints-computed?) (method)
• (setf endpoints-computed?) (generic function)
• knot-i-x (macro)
• knot-i-y (macro)
• knots (generic function)
• knots (method)
• (setf knots) (method)
• (setf knots) (generic function)
• knots-count (generic function)
• knots-count (method)
• (setf knots-count) (method)
• (setf knots-count) (generic function)
• set-coeffs (function)

5 Definitions

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

5.1 Exported definitions

5.1.1 Generic functions

Generic Function: add-knot SPLINE KNOT

Given a knot as a sequence pair representing an x,y point, add it to this spline’s control knots.

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Methods

Method: add-knot (SPLINE spline) (KNOT sequence)

Generic Function: next-point SPLINE

For the current segment between knots, calculates the next point and
returns it as a two element vector.

If the spline contains fewer than 3 knots, an error signal is raised.

This method returns two extra multiple values for special conditions:
* When the next point has reached or would reach beyond the final knot,
#(0.0 0.0) is returned along with a second value set to T.
Otherwise this second value is nil.
* When the returned point is the final point of a segment, a third value will be T.

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Methods

Method: next-point (SPLINE spline)

Generic Function: reset SPLINE

Reinitializes the spline state so the next call to next-poin will return the beginning point of the spline.

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Methods

Method: reset (SPLINE spline)

Generic Function: scale SPLINE FACTOR

Multiplies each knot’s x and y values by the scale factor.

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Methods

Method: scale (SPLINE spline) (FACTOR real)

5.1.2 Classes

Class: spline ()

Catmull-Rom splines are composed of a number of knots
(at least 3) with a piecewise path computed between
each knot, with the overall path from the first to
last knot appearing smooth. Each knot will be crossed
along the path.

Point: two-element vector representing an (x, y) coordiante.
Knots: control points determining the shape of the complete spline path. Spline segments: the path between knots. Can be thought of as functions of time path(t) : R -> point, from t=0 to t=1.
path(0) is the first knot in the segment, path(1) is the last knot.

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• compute-endpoints (method)
• next-point (method)
• reset (method)
• scale (method)
• add-knot (method)
• coeffs-computed? (method)
• coeffs-computed? (method)
• endpoints-computed? (method)
• endpoints-computed? (method)
• dt (method)
• dt (method)
• cur-t (method)
• cur-t (method)
• cur-knot (method)
• cur-knot (method)
• knots-count (method)
• knots-count (method)
• coeffs (method)
• coeffs (method)
• knots (method)
• knots (method)

Direct slots

Slot: knots

Initform

(make-array 1 :fill-pointer 0 :adjustable t)

Readers

knots (generic function)

Writers

(setf knots) (generic function)

Slot: coeffs

Initform

(make-array 1 :fill-pointer 0 :adjustable t)

Readers

coeffs (generic function)

Writers

(setf coeffs) (generic function)

Slot: knots-count

Initform

0

Readers

knots-count (generic function)

Writers

(setf knots-count) (generic function)

Slot: current-knot

Initform

1

Readers

cur-knot (generic function)

Writers

(setf cur-knot) (generic function)

Slot: current-t

Initform

0.0

Readers

cur-t (generic function)

Writers

(setf cur-t) (generic function)

Slot: delta-t

By default this 0.1 dt means that for the first
segment, it will take 11 calls (t goes from =0 to =1) to complete, but every other segment will start at t=0.1 to avoid repeating the knot value at t=0 and thus take 10 calls to go through. Use either shorter point distances, or a lower dt to have smoother interpolation.

Initargs

:dt

Initform

0.1

Readers

dt (generic function)

Writers

(setf dt) (generic function)

Slot: endpoints-computed?

Readers

endpoints-computed? (generic function)

Writers

(setf endpoints-computed?) (generic function)

Slot: coeffs-computed?

Readers

coeffs-computed? (generic function)

Writers

(setf coeffs-computed?) (generic function)

5.2 Internal definitions

5.2.1 Macros

Macro: knot-i-x SPLINE I

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Macro: knot-i-y SPLINE I

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

5.2.2 Functions

Function: coeff->idx COEFF

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Function: coeff-x SPLINE COEFF

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Function: coeff-y SPLINE COEFF

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Function: compute-coefficients SPLINE

A point on a segment can be found by applying the equation
p(t) = at^3 + bt^2 + ct + d
with coeffs a, b, c, d. The coeffs are computed below,
with e.g. a_x = 1/2(-x_{i-1} + 3x_i - 3_x{i+1} + x_{i+2})

Note the basis matrix for cardinal spline coeffs is:
[[-a 2-a a-2 a]
[2a a-3 3-2a -a]
[-a 0 a 0]
[0 1 0 0]]
where a is the spline ’tension’. As a approaches 1, the bend at each knot is less. Catmull-Rom splines typically use the value of 0.5, we use the same.

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Function: dot-product M1 M2

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

Function: set-coeffs SPLINE I AX AY BX BY CX CY DX DY

Package

cl-catmull-rom-spline

Source

spline.lisp (file)

5.2.3 Generic functions

Generic Function: coeffs OBJECT

Generic Function: (setf coeffs) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: coeffs (SPLINE spline)

automatically generated reader method

Source

spline.lisp (file)

Method: (setf coeffs) NEW-VALUE (SPLINE spline)

automatically generated writer method

Source

spline.lisp (file)

Generic Function: coeffs-computed? OBJECT

Generic Function: (setf coeffs-computed?) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: coeffs-computed? (SPLINE spline)

automatically generated reader method

Source

spline.lisp (file)

Method: (setf coeffs-computed?) NEW-VALUE (SPLINE spline)

automatically generated writer method

Source

spline.lisp (file)

Generic Function: compute-endpoints SPLINE

Package

cl-catmull-rom-spline

Methods

Method: compute-endpoints (SPLINE spline)

Should be called after all knots have been added. Called automatically by next-point if user forgot.

Once the user-facing knots are added, we need to compute two ’true’ auxilliary endpoints for the whole path. Currently this is done by duplicating the the first and last knots, though this can cause kinking.
A future approach is to use reflection, which can still cause pinching but may be better.
Of course, they can be set manually if needed. (Consider subclassing rather than direct knot access.)

Source

spline.lisp (file)

Generic Function: cur-knot OBJECT

Generic Function: (setf cur-knot) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: cur-knot (SPLINE spline)

automatically generated reader method

Source

spline.lisp (file)

Method: (setf cur-knot) NEW-VALUE (SPLINE spline)

automatically generated writer method

Source

spline.lisp (file)

Generic Function: cur-t OBJECT

Generic Function: (setf cur-t) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: cur-t (SPLINE spline)

automatically generated reader method

Source

spline.lisp (file)

Method: (setf cur-t) NEW-VALUE (SPLINE spline)

automatically generated writer method

Source

spline.lisp (file)

Generic Function: dt OBJECT

Generic Function: (setf dt) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: dt (SPLINE spline)

Method: (setf dt) NEW-VALUE (SPLINE spline)

By default this 0.1 dt means that for the first
segment, it will take 11 calls (t goes from =0 to =1) to complete, but every other segment will start at t=0.1 to avoid repeating the knot value at t=0 and thus take 10 calls to go through. Use either shorter point distances, or a lower dt to have smoother interpolation.

Source

spline.lisp (file)

Generic Function: endpoints-computed? OBJECT

Generic Function: (setf endpoints-computed?) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: endpoints-computed? (SPLINE spline)

automatically generated reader method

Source

spline.lisp (file)

Method: (setf endpoints-computed?) NEW-VALUE (SPLINE spline)

automatically generated writer method

Source

spline.lisp (file)

Generic Function: knots OBJECT

Generic Function: (setf knots) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: knots (SPLINE spline)

automatically generated reader method

Source

spline.lisp (file)

Method: (setf knots) NEW-VALUE (SPLINE spline)

automatically generated writer method

Source

spline.lisp (file)

Generic Function: knots-count OBJECT

Generic Function: (setf knots-count) NEW-VALUE OBJECT

Package

cl-catmull-rom-spline

Methods

Method: knots-count (SPLINE spline)

automatically generated reader method

Source

spline.lisp (file)

Method: (setf knots-count) NEW-VALUE (SPLINE spline)

automatically generated writer method

Source

spline.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types