3 (defclass basic-path-join
() ())
5 (defclass concatenate-path-join
(basic-path-join) ())
7 (defparameter *concatenate-path-join
* (make-instance 'concatenate-path-join
))
9 (defclass controls
(basic-path-join)
13 (defclass tensions
(basic-path-join)
17 (defclass direction-specifier
() ())
19 (defclass curl
(direction-specifier)
20 ((curl :initarg
:curl
)))
22 (defclass direction
(direction-specifier)
23 ((direction :initarg
:direction
)))
25 (defclass cycle
() ())
27 (defparameter *cycle
* (make-instance 'cycle
))
30 (loop for elem in list
31 append
(if (consp elem
)
36 ((%neighbor
:initform nil
:initarg
:neighbor
:accessor neighbor
)
37 (%curl
:initform nil
:initarg
:curl
:accessor curl
)
38 (%direction
:initform nil
:initarg
:direction
:accessor direction
)
39 (%tension
:initform nil
:initarg
:tension
:accessor tension
)
40 (%control
:initform nil
:initarg
:control
:accessor control
)
41 (%angle
:initform nil
:initarg
:angle
:accessor angle
)))
44 ((%point
:initarg
:point
:reader point
)
45 (%rank
:initform nil
:accessor rank
)))
47 (defclass left-context-point
(point)
48 ((%left-context
:initform
(make-instance 'context
)
49 :initarg
:left-context
:reader left-context
)))
51 (defclass right-context-point
(point)
52 ((%right-context
:initform
(make-instance 'context
)
53 :initarg
:right-context
:reader right-context
)))
55 (defclass left-endpoint
(right-context-point) ())
57 (defclass right-endpoint
(left-context-point) ())
59 (defclass corner-point
(left-context-point right-context-point
) ())
61 (defclass interior-point
(left-context-point right-context-point
) ())
63 (defun remove-concatenates (path)
64 (loop until
(null path
)
65 if
(and (not (null (cddr path
))) ; path has at least 3 elements
66 (eq (second path
) *concatenate-path-join
*))
67 collect
(prog1 (make-instance 'corner-point
:point
(car path
))
68 (setf path
(cdddr path
)))
69 else collect
(pop path
)))
71 (defun check-start-end (path)
72 (assert (numberp (car path
))
74 "the path must start with a point, but ~s was found" (car path
))
75 (assert (or (numberp (car (last path
))) (eq (car (last path
)) *cycle
*))
77 "the path must end with a point, but ~s was found" (car (last path
))))
79 (defun check-cycle (path)
80 ;; check that there is no `cycle' other than at
81 ;; the end of the path.
82 (assert (not (member-if (lambda (x) (eq x
*cycle
*)) (butlast path
)))
84 "only the last element of a path can be CYCLE"))
86 (defun check-syntax (path)
87 (check-start-end path
)
89 (loop for
(x y z
) on path
90 ;; check that each direction specifier is surrounded
91 ;; by a point on one side and a tensions object on the other
92 ;; or possibly a cycle object on the right
93 do
(when (typep y
'direction-specifier
)
94 (assert (or (and (typep x
'tensions
)
95 (or (numberp z
) (eq z
*cycle
*)))
99 "a direction specifier must have a point on one side and a tensions object on the other, but ~a and ~a were found" x z
))
100 ;; check that each controls object and each
101 ;; concatenate path join is surrounded by points
102 ;; or possibly a cycle object on the right
103 do
(when (or (eq y
*concatenate-path-join
*)
107 "a concatenate path join or a controls object must have a point to the left, but ~a was found" x
)
108 (assert (or (numberp z
) (eq z
*cycle
*))
110 "a concatenate path join or a controls object must have a point or `cycle' to the right, but ~a was found" z
))
111 ;; check that each tensions object is
112 ;; surrounded by a direction specifier or a point
113 ;; or possibly a cycle on the right
114 do
(when (typep y
'tensions
)
115 (assert (typep x
'(or number direction-specifier
))
117 "a tension object must have a direction specifier or a point to the left, but ~a was found" x
)
118 (assert (or (typep z
'(or number direction-specifier
)) (eq z
*cycle
*))
120 "a tension object must have a direction specifier, a point, or `cycle' to the right, but ~a was found" z
))
121 ;; check that each point or cycle object is surrounded by a
122 ;; direction specifier or a basic path join
123 do
(when (or (numberp y
) (eq y
*cycle
*))
124 (assert (typep x
'(or direction-specifier basic-path-join
))
126 "a point or a cycle object must have a direction specifier or a basic path joint to the left, but ~a was found" x
)
127 (assert (or (null z
) (typep z
'(or direction-specifier basic-path-join
)))
129 "a point must have a direction specifier or a basic path joint to the right, but ~a was found" z
))))
131 (defun propagate-direction-specifiers (path)
132 (loop for
(x y z
) on path
133 do
(when (typep y
'direction-specifier
)
136 (setf (curl (right-context x
)) (slot-value y
'curl
))
137 (setf (direction (right-context x
)) (slot-value y
'direction
)))
139 (setf (curl (left-context (if (eq z
*cycle
*) (car path
) z
)))
140 (slot-value y
'curl
))
141 (setf (direction (left-context (if (eq z
*cycle
*) (car path
) z
)))
142 (slot-value y
'direction
)))))))
144 (defun propagate-tensions-controls (path)
145 (loop for
(x y z
) on path
147 (tensions (setf (tension (right-context x
)) (slot-value y
'a
))
148 (setf (tension (left-context (if (eq z
*cycle
*)
152 (controls (setf (control (right-context x
)) (slot-value y
'a
))
153 (setf (control (left-context (if (eq z
*cycle
*)
156 (slot-value y
'b
))))))
158 (defun link-and-rank-points (path)
159 (when (eq (car (last path
)) *cycle
*)
161 (setf (neighbor (right-context (car (last path
)))) (car path
))
162 (setf (neighbor (left-context (car path
))) (car (last path
))))
163 (loop for
(x y
) on path
167 do
(setf (neighbor (right-context x
)) y
168 (neighbor (left-context y
)) x
)))
170 (defun propagate-directions (path)
171 (flet ((possibly-fill-in-curl (context)
172 (when (and (null (control context
))
173 (null (direction context
))
174 (null (curl context
)))
175 (setf (curl context
) 1.0))))
176 (loop for point in path
179 (possibly-fill-in-curl (right-context point
)))
181 (possibly-fill-in-curl (left-context point
)))
183 (possibly-fill-in-curl (right-context point
))
184 (possibly-fill-in-curl (left-context point
)))
186 (let ((lc (left-context point
))
187 (rc (right-context point
)))
188 (when (and (null (curl lc
))
189 (null (direction lc
))
191 (cond ((not (null (curl rc
)))
194 ((not (null (direction rc
)))
197 ((not (null (control rc
)))
199 (- (control rc
) (point point
))))))
200 (when (and (null (curl rc
))
201 (null (direction rc
))
203 (cond ((not (null (curl lc
)))
206 ((not (null (direction lc
)))
209 ((not (null (control lc
)))
211 (- (point point
) (control lc
))))))))))))
213 (defun solve (system)
214 (let* ((width (array-dimension system
1))
215 (height (array-dimension system
0))
216 (rows (loop for i from
0 below height collect i
)))
217 (flet ((eliminate (rows column
)
218 (flet ((eliminate-row (row1 row2
)
219 (let ((factor (/ (aref system row2 column
)
220 (aref system row1 column
))))
221 (loop for i from column below width
222 do
(decf (aref system row2 i
)
223 (* factor
(aref system row1 i
)))))))
224 (let ((pivot-row (member-if (lambda (row)
225 (not (zerop (aref system row column
))))
227 (rotatef (car pivot-row
) (car rows
))
228 (loop for row in
(cdr rows
)
229 do
(eliminate-row (car rows
) row
))))))
230 (loop for column from
0 below
(- width
2)
231 for remaining-rows on rows
232 do
(eliminate remaining-rows column
))
233 (let ((last-column (1- width
)))
234 (loop for rev-rows on
(reverse rows
)
235 for column downfrom
(- width
2)
236 do
(loop with row1
= (car rev-rows
)
237 for row2 in
(cdr rev-rows
)
238 do
(decf (aref system row2 last-column
)
239 (* (/ (aref system row2 column
)
240 (aref system row1 column
))
241 (aref system row1 last-column
)))
242 do
(setf (aref system row2 column
) 0.0)))
243 (loop for column from
0
245 do
(setf (aref system row last-column
)
246 (/ (aref system row last-column
)
247 (aref system row column
))))))
248 (let ((solution (make-array height
)))
249 (loop for i from
0 below height
250 do
(setf (aref solution i
) (aref system
(elt rows i
) (1- width
))))
253 (defun solve-angles (path)
254 (let* ((open-p (typep (car path
) 'left-endpoint
))
255 (length (length path
))
256 (nb-variables (- (* 2 (length path
))
258 (width (1+ nb-variables
))
259 (matrix (make-array (list nb-variables width
) :initial-element
0.0))
260 (equation-number -
1))
261 (labels ((out (i) (* 2 i
))
262 (in (i) (1- (* 2 (if (zerop i
) length i
))))
263 (handle-right-context (point context
)
264 (cond ((not (null (control context
)))
265 (let ((out-angle (phase (/ (- (control context
)
267 (- (point (neighbor context
))
269 (setf (aref matrix
(incf equation-number
) (out (rank point
)))
271 (setf (aref matrix equation-number
(1- width
))
273 ((not (null (direction context
)))
274 (let ((out-angle (phase (/ (direction context
)
275 (- (point (neighbor context
))
277 (setf (aref matrix
(incf equation-number
) (out (rank point
)))
279 (setf (aref matrix equation-number
(1- width
))
281 ((not (null (curl context
)))
282 (let* ((a0 (tension context
))
283 (b1 (tension (left-context (neighbor context
))))
285 (c1 (- (* a0 a0 a0
(- 1 (* 3.0 b1
)))
290 (setf (aref matrix
(incf equation-number
) (out (rank point
)))
292 (setf (aref matrix equation-number
(in (rank (neighbor context
))))
294 (handle-left-context (point context
)
295 (cond ((not (null (control context
)))
296 (let ((in-angle (phase (/ (- (point point
)
297 (point (neighbor context
)))
299 (control context
))))))
300 (setf (aref matrix
(incf equation-number
) (in (rank point
)))
302 (setf (aref matrix equation-number
(1- width
))
304 ((not (null (direction context
)))
305 (let ((in-angle (phase (/ (- (point point
)
306 (point (neighbor context
)))
307 (direction context
)))))
308 (setf (aref matrix
(incf equation-number
) (in (rank point
)))
310 (setf (aref matrix equation-number
(1- width
))
312 ((not (null (curl context
)))
313 (let* ((bn (tension context
))
314 (an-1 (tension (right-context (neighbor context
))))
317 (- (* gn an-1 an-1 an-1
))
319 (c2 (- (* bn bn bn
(- 1 (* 3.0 an-1
)))
320 (* gn an-1 an-1 an-1
))))
321 (setf (aref matrix
(incf equation-number
) (out (rank (neighbor context
))))
323 (setf (aref matrix equation-number
(in (rank point
)))
325 (loop for point in path
328 (handle-right-context point
(right-context point
)))
330 (handle-left-context point
(left-context point
)))
332 (handle-right-context point
(right-context point
))
333 (handle-left-context point
(left-context point
)))
335 (let ((lc (left-context point
))
336 (rc (right-context point
)))
337 (if (and (null (curl lc
)) (null (direction lc
)) (null (control lc
))
338 (null (curl rc
)) (null (direction rc
)) (null (control rc
)))
339 (let* ((ak-1 (tension (right-context (neighbor lc
))))
342 (bk+1 (tension (left-context (neighbor rc
))))
343 (lk (abs (- (point point
) (point (neighbor lc
)))))
344 (lk+1 (abs (- (point (neighbor rc
)) (point point
))))
345 (c1 (* bk bk bk
+1 lk
))
346 (c2 (* bk bk bk
+1 lk
+1 (- 1.0 (* 3.0 ak-1
))))
347 (c3 (- (* ak ak ak-1 lk
(- 1.0 (* 3.0 bk
+1)))))
348 (c4 (- (* ak ak ak-1 lk
))))
350 (incf equation-number
)
351 (out (rank (neighbor lc
))))
353 (setf (aref matrix equation-number
(in (rank point
)))
355 (setf (aref matrix equation-number
(out (rank point
)))
359 (in (rank (neighbor rc
))))
361 (setf (aref matrix
(incf equation-number
) (out (rank point
)))
363 (setf (aref matrix equation-number
(in (rank point
)))
365 (setf (aref matrix equation-number
(1- width
))
366 (- (phase (/ (- (point (neighbor rc
)) (point point
))
367 (- (point point
) (point (neighbor lc
))))))))
368 (progn (handle-left-context point
(left-context point
))
369 (handle-right-context point
(right-context point
))))))))
370 (let ((solution (solve matrix
)))
371 (loop for point in path
372 do
(when (typep point
'left-context-point
)
373 (setf (angle (left-context point
)) (aref solution
(in (rank point
)))))
374 do
(when (typep point
'right-context-point
)
375 (setf (angle (right-context point
)) (aref solution
(out (rank point
))))))))))
377 (defun hobby (theta phi
)
380 (- (sin theta
) (* 1/16 (sin phi
)))
381 (- (sin phi
) (* 1/16 (sin theta
)))
382 (- (cos theta
) (cos phi
))))
385 (* #.
(* 0.5 (- (sqrt 5.0) 1.0))
387 (* #.
(* 0.5 (- 3.0 (sqrt 5.0)))
390 (defun handle-point-pair (p0 p1 tr tl theta phi
)
393 (/ (* (exp (* #c
(0.0
1.0) theta
))
398 (/ (* (exp (* #c
(0.0 -
1.0) phi
))
403 (defun assign-control-points (path)
404 (loop for
(p0 p1
) on path
406 do
(let* ((rc (right-context p0
))
407 (lc (left-context p1
))
410 (when (null (control rc
))
411 (multiple-value-bind (c0 c1
)
412 (handle-point-pair (point p0
) (point p1
)
413 (tension rc
) (tension lc
) theta phi
)
414 (setf (control rc
) c0
416 (unless (typep (car path
) 'left-endpoint
)
417 (let* ((p0 (car (last path
)))
419 (rc (right-context p0
))
420 (lc (left-context p1
))
423 (when (null (control rc
))
424 (multiple-value-bind (c0 c1
)
425 (handle-point-pair (point p0
) (point p1
)
426 (tension rc
) (tension lc
) theta phi
)
427 (setf (control rc
) c0
428 (control lc
) c1
))))))
430 (defun point-to-complex (point)
431 "convert a point to a complex number"
432 (complex (clim:point-x point
) (clim:point-y point
)))
434 (defun complex-to-point (complex)
435 "convert a complex number to a point"
436 (clim:make-point
(realpart complex
) (imagpart complex
)))
438 (defun make-mf-path (&rest body
)
439 (let ((path (mapcar (lambda (x)
445 ;; replace each sequence of type `p & p' by a corner point
446 (setf path
(remove-concatenates path
))
447 ;; replace the end points if path is not a cycle
448 (unless (eq (car (last path
)) *cycle
*)
449 (setf (car path
) (make-instance 'left-endpoint
:point
(car path
)))
450 (setf (car (last path
)) (make-instance 'right-endpoint
:point
(car (last path
)))))
451 ;; replace all other points by interior points
452 (setf path
(loop for element in path
453 collect
(if (numberp element
)
454 (make-instance 'interior-point
:point element
)
456 ;; propagate direction specifiers to their respective points
457 (propagate-direction-specifiers path
)
458 ;; remove all direction specifiers
459 (setf path
(remove-if (lambda (x) (typep x
'direction-specifier
)) path
))
460 ;; propagate tensions and controls to their respective points
461 (propagate-tensions-controls path
)
462 ;; remove all tensions and controls objects
463 (setf path
(remove-if (lambda (x) (typep x
'(or tensions controls
))) path
))
464 ;; link and rank the points of the path, remove the cycle object
465 (link-and-rank-points path
)
466 ;; now the path contains only point objects
467 (propagate-directions path
)
469 (assign-control-points path
)
470 (if (typep (car path
) 'left-endpoint
)
471 (let ((segments (loop for point in
(butlast path
)
472 collect
(let ((rc (right-context point
)))
473 (climi::make-bezier-segment
474 (complex-to-point (point point
))
475 (complex-to-point (control rc
))
476 (complex-to-point (control (left-context (neighbor rc
))))
477 (complex-to-point (point (neighbor rc
))))))))
478 (make-instance 'climi
::bezier-curve
:segments segments
))
479 (let ((segments (loop for point in path
480 collect
(let ((rc (right-context point
)))
481 (climi::make-bezier-segment
482 (complex-to-point (point point
))
483 (complex-to-point (control rc
))
484 (complex-to-point (control (left-context (neighbor rc
))))
485 (complex-to-point (point (neighbor rc
))))))))
486 (make-instance 'climi
::bezier-area
:segments segments
)))))
488 (defparameter *infinity
* 4095.99998) ;see the MF book
490 (defmacro mf
(&body body
)
492 (make-instance 'controls
:a a
:b a
))
494 (make-instance 'controls
:a a
:b b
))
498 "tension values must be greater than 0.75: ~a"
500 (make-instance 'tensions
:a a
:b a
))
502 (assert (>= (min a b
) 0.75)
504 "tension values must be greater than 0.75: ~a"
506 (make-instance 'tensions
:a a
:b b
))
508 (make-instance 'direction
:direction d
))
510 (make-instance 'curl
:curl c
)))
511 (declare (ignorable (function control
)
517 (let* ((++ (tension 1.0))
518 (+++ (tension 1.0)) ; this is not right
519 (& *concatenate-path-join
*)
520 (--- (tension *infinity
*))
521 (-- (list (make-instance 'curl
:curl
1)
522 (make-instance 'tensions
:a
2 :b
2) ; should be 1 rather than 2
523 (make-instance 'curl
:curl
1)))
525 (up (direction #c
(0 1)))
526 (down (direction #c
(0 -
1)))
527 (left (direction #c
(-1 0)))
528 (right (direction #c
(1 0))))
529 (declare (ignorable +++ & --- -- cycle up down left right
))
533 (defun part-way (p0 p1 alpha
)
534 (+ (* (- 1 alpha
) p0
) (* alpha p1
)))
536 ;;; some standard paths
537 (defparameter +quarter-circle
+
538 (let* ((a (* 0.5 (- (sqrt 2) 1)))
539 (q0 (clim:make-point
0.5 0.0))
540 (q1 (clim:make-point
0.0 0.5))
541 (p0 (clim:make-point
(/ 0.5 (sqrt 2)) (/ 0.5 (sqrt 2))))
542 (p1 (clim:make-point
0.5 a
))
543 (p2 (clim:make-point a
0.5))
545 (climi::make-bezier-curve
547 (climi::part-way q0 p1 alpha
)
548 (climi::part-way p0 p1 alpha
)
550 (climi::part-way p0 p2 alpha
)
551 (climi::part-way q1 p2 alpha
)
554 (defparameter +half-circle
+
555 (let* ((tr (clim:make-rotation-transformation
(/ pi
2)))
556 (rotated-quarter-circle (clim:transform-region tr
+quarter-circle
+)))
557 (clim:region-union
+quarter-circle
+ rotated-quarter-circle
)))
559 (defparameter +full-circle
+
560 (let* ((tr (clim:make-rotation-transformation pi
))
561 (rotated-half-circle (clim:transform-region tr
+half-circle
+)))
562 (climi::close-path
(clim:region-union
+half-circle
+ rotated-half-circle
))))
564 (defparameter +unit-square
+
566 (mf #c
(0.5
0.5) --
#c
(-0.5
0.5) --
#c
(-0.5 -
0.5) --
#c
(0.5 -
0.5) --
#c
(0.5
0.5))))
568 (defun superellipse (r top l bot superness
)
569 (let ((xtr (part-way (realpart top
) (realpart r
) superness
))
570 (yrt (part-way (imagpart r
) (imagpart top
) superness
))
571 (xtl (part-way (realpart top
) (realpart l
) superness
))
572 (ylt (part-way (imagpart l
) (imagpart top
) superness
))
573 (xbl (part-way (realpart bot
) (realpart l
) superness
))
574 (ylb (part-way (imagpart l
) (imagpart bot
) superness
))
575 (xbr (part-way (realpart bot
) (realpart r
) superness
))
576 (yrb (part-way (imagpart r
) (imagpart bot
) superness
)))
577 (mf r up
+++ (complex xtr yrt
) (direction (- top r
)) +++
578 top left
+++ (complex xtl ylt
) (direction (- l top
)) +++
579 l down
+++ (complex xbl ylb
) (direction (- bot l
)) +++
580 bot right
+++ (complex xbr yrb
) (direction (- r bot
)) +++ cycle
)))
582 (defparameter +razor
+
583 (climi::close-path
(mf #c
(-0.5
0) --
#c
(0.5
0) --
#c
(-0.5
0))))
589 (defmacro with-pen
(pen &body body
)
593 (defun draw-path (path)
594 (climi::convolve-regions
*pen
* path
))