Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
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 4.0 beta 2 "William Riker" on Wed Jun 15 03:33:10 2022 GMT+0.
Table of Contents
Next: Systems, Previous: The cl-catmull-rom-spline Reference Manual, Up: The cl-catmull-rom-spline Reference Manual [Contents][Index]
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.
Next: Files, Previous: Introduction, Up: The cl-catmull-rom-spline Reference Manual [Contents][Index]
2 Systems
The main system appears first, followed by any subsystem dependency.
2.1 cl-catmull-rom-spline
Catmull-Rom Spline
- Author
Kevin Secretan <github@thejach.com>
- License
Public Domain
- Version
0.1.0
- Source
- Child Component
spline.lisp (file).
Next: Packages, Previous: Systems, Up: The cl-catmull-rom-spline Reference Manual [Contents][Index]
3 Files
Files are sorted by type and then listed depth-first from the systems components trees.
3.1 Lisp
Next: cl-catmull-rom-spline/spline.lisp, Previous: Lisp, Up: Lisp [Contents][Index]
3.1.1 cl-catmull-rom-spline/cl-catmull-rom-spline.asd
- Source
- Parent Component
cl-catmull-rom-spline (system).
- ASDF Systems
Previous: cl-catmull-rom-spline/cl-catmull-rom-spline.asd, Up: Lisp [Contents][Index]
3.1.2 cl-catmull-rom-spline/spline.lisp
- Source
- Parent Component
cl-catmull-rom-spline (system).
- Packages
- Public Interface
- add-knot (generic function).
- next-point (generic function).
- reset (generic function).
- scale (generic function).
- spline (class).
- Internals
- coeff->idx (function).
- coeff-x (function).
- coeff-y (function).
- coeffs (reader method).
- (setf coeffs) (writer method).
- coeffs-computed? (reader method).
- (setf coeffs-computed?) (writer method).
- compute-coefficients (function).
- compute-endpoints (method).
- cur-knot (reader method).
- (setf cur-knot) (writer method).
- cur-t (reader method).
- (setf cur-t) (writer method).
- dot-product (function).
- dt (reader method).
- (setf dt) (writer method).
- endpoints-computed? (reader method).
- (setf endpoints-computed?) (writer method).
- knot-i-x (macro).
- knot-i-y (macro).
- knots (reader method).
- (setf knots) (writer method).
- knots-count (reader method).
- (setf knots-count) (writer method).
- set-coeffs (function).
Next: Definitions, Previous: Files, Up: The cl-catmull-rom-spline Reference Manual [Contents][Index]
4 Packages
Packages are listed by definition order.
4.1 cl-catmull-rom-spline
- Source
- Nicknames
- com.thejach.cl-catmull-rom-spline
- cr-spline
- Use List
common-lisp.
- Public Interface
- add-knot (generic function).
- next-point (generic function).
- reset (generic function).
- scale (generic function).
- spline (class).
- Internals
- coeff->idx (function).
- coeff-x (function).
- coeff-y (function).
- coeffs (generic reader).
- (setf coeffs) (generic writer).
- coeffs-computed? (generic reader).
- (setf coeffs-computed?) (generic writer).
- compute-coefficients (function).
- compute-endpoints (generic function).
- cur-knot (generic reader).
- (setf cur-knot) (generic writer).
- cur-t (generic reader).
- (setf cur-t) (generic writer).
- dot-product (function).
- dt (generic reader).
- (setf dt) (generic writer).
- endpoints-computed? (generic reader).
- (setf endpoints-computed?) (generic writer).
- knot-i-x (macro).
- knot-i-y (macro).
- knots (generic reader).
- (setf knots) (generic writer).
- knots-count (generic reader).
- (setf knots-count) (generic writer).
- set-coeffs (function).
Next: Indexes, Previous: Packages, Up: The cl-catmull-rom-spline Reference Manual [Contents][Index]
5 Definitions
Definitions are sorted by export status, category, package, and then by lexicographic order.
Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]
5.1 Public Interface
Next: Classes, Previous: Public Interface, Up: Public Interface [Contents][Index]
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
- Source
- Methods
- 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
- Source
- Methods
- Generic Function: reset (spline) ¶
-
Reinitializes the spline state so the next call to next-poin will return the beginning point of the spline.
- Package
- Source
- Methods
- Generic Function: scale (spline factor) ¶
-
Multiplies each knot’s x and y values by the scale factor.
- Package
- Source
- Methods
Previous: Generic functions, Up: Public Interface [Contents][Index]
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
- Source
- Direct methods
- Direct slots
- Slot: knots ¶
-
- Initform
(make-array 1 :fill-pointer 0 :adjustable t)
- Readers
- Writers
- Slot: coeffs ¶
-
- Initform
(make-array 1 :fill-pointer 0 :adjustable t)
- Readers
- Writers
- Slot: knots-count ¶
-
- Initform
0
- Readers
- Writers
- Slot: current-knot ¶
-
- Initform
1
- Readers
- Writers
- Slot: current-t ¶
-
- Initform
0.0
- Readers
- Writers
- 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.
- Slot: endpoints-computed? ¶
-
- Readers
- Writers
- Slot: coeffs-computed? ¶
-
- Readers
- Writers
Previous: Public Interface, Up: Definitions [Contents][Index]
5.2 Internals
Next: Ordinary functions, Previous: Internals, Up: Internals [Contents][Index]
5.2.1 Macros
- Macro: knot-i-x (spline i) ¶
-
- Package
- Source
- Macro: knot-i-y (spline i) ¶
-
- Package
- Source
Next: Generic functions, Previous: Macros, Up: Internals [Contents][Index]
5.2.2 Ordinary functions
- Function: coeff->idx (coeff) ¶
-
- Package
- Source
- Function: coeff-x (spline coeff) ¶
-
- Package
- Source
- Function: coeff-y (spline coeff) ¶
-
- Package
- Source
- 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
- Source
- Function: dot-product (m1 m2) ¶
-
- Package
- Source
- Function: set-coeffs (spline i ax ay bx by cx cy dx dy) ¶
-
- Package
- Source
Previous: Ordinary functions, Up: Internals [Contents][Index]
5.2.3 Generic functions
- Generic Reader: coeffs (object) ¶
- Generic Writer: (setf coeffs) (object) ¶
- Generic Reader: coeffs-computed? (object) ¶
- Generic Writer: (setf coeffs-computed?) (object) ¶
- Generic Function: compute-endpoints (spline) ¶
-
- Package
- 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
- Generic Reader: cur-knot (object) ¶
- Generic Writer: (setf cur-knot) (object) ¶
- Generic Reader: cur-t (object) ¶
- Generic Writer: (setf cur-t) (object) ¶
- Generic Reader: dt (object) ¶
- Generic Writer: (setf dt) (object) ¶
-
- Package
- Methods
- Reader Method: dt ((spline spline)) ¶
- Writer Method: (setf dt) ((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
- Target Slot
- Generic Reader: endpoints-computed? (object) ¶
- Generic Writer: (setf endpoints-computed?) (object) ¶
- Generic Reader: knots (object) ¶
- Generic Writer: (setf knots) (object) ¶
- Generic Reader: knots-count (object) ¶
- Generic Writer: (setf knots-count) (object) ¶
Previous: Definitions, Up: The cl-catmull-rom-spline Reference Manual [Contents][Index]
Appendix A Indexes
A.2 Functions
| Jump to: | (
A C D E F G K M N R S |
|---|
| Jump to: | (
A C D E F G K M N R S |
|---|
Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]
A.3 Variables
| Jump to: | C D E K S |
|---|
| Jump to: | C D E K S |
|---|
A.4 Data types
| Jump to: | C F P S |
|---|
| Jump to: | C F P S |
|---|