Cel's CompSci Project Blog
We're now at the end of the semester, and I've been given a choice: continue with this project for another semester, or try something else?
I've decided to switch to a different project. Why? This project has been very interesting, but I haven't been learning as much as I could have.
I'm going to focus on something that will, in and of itself, teach me something.
Still, I've wrapped up my work on this project, and it's a usable version! See the link at the end of this post for the downloadable version.
I'll be posting a link to my blog for the next project shortly.
Cheers, Cel Skeggs.
The current version of my code is v0.2.0: cd6b807311b9f373f80e418f186d74e572d890a9.
Better highlighting! (minipost)
More usability! Now it's clear which figure is currently selected.
(Look at the handles. The selected figure, at the left, has a different color.)
Better controls! (minipost)
It's a bit more usable! The buttons now have readable labels.
With a bit of work, I went from this:
There, smoothing is better and some of the weird visual artifacts are gone!
Back to work!
Now that school is back in session, it's now time to get back to work!
With a bit of work on posing, the feet started to look a bit better:
But I've digressed slightly to take care of line widths: note how that third small character has overly thick lines, since they aren't varied with scale.
To fix this, I changed the pen styles to be dynamically generated based on both scale and style, not just style:
The line width variance helped, but it probably needs to have a smarter nonlinear system.
(The feet still need some more work too.)
Spline Legs! (Minipost)
This change actually involved removing code, rather than adding it! (Because now it can share the same code as the arms.)
However, I'm not completely sure that I like it better like this.
I might revisit this decision later.
Cheers, Cel Skeggs.
At the left: the new arm drawing system. At the right: the old arm drawing system.
Why did I change this? The old version was naively using Racket's builtin spline drawing tool, which is given two endpoints and a control point. Unfortunately, the curve doesn't actually go through the control point. And it uses line segments on the ends. Bleh.
Now, it turns out that it's not easy to figure out how to draw a curve through a given point. Luckily, I found Rob Spencer's bezier curve fitting algorithm, which does exactly what I want!
I implemented this:
(: calc-control-points (-> Vector2D Vector2D Vector2D Float (Values Vector2D Vector2D)))
(define (calc-control-points v0 v1 v2 t)
(let ((d01 (vdist v0 v1))
(d12 (vdist v1 v2))
(r20 (v- v2 v0)))
(let ((fa (/ (* t d01) (+ d01 d12)))
(fb (/ (* t d12) (+ d01 d12))))
(values (v- v1 (v*c r20 fa))
(v+ v1 (v*c r20 fb))))))
After I did this, it still didn't work... as it turned out, you actually need to cut up the curve into two separate quadratic bezier curves, not one single cubic bezier curve!
Unfortunately, Racket doesn't have any methods for drawing quadratic bezier curves... but I searched around and found a post on the cairo mailing list (cairo is the vector graphics library that Racket uses as a backend for drawing) that explains how to convert.
Now I can implement that too:
(: quadratic->cubic (-> Vector2D Vector2D Vector2D (Values Vector2D Vector2D Vector2D Vector2D)))
(define (quadratic->cubic p0 p1 p2)
(vinterpolate p0 p1 (/ 2.0 3.0))
(vinterpolate p1 p2 (/ 2.0 3.0))
So, then, with that, I can use the control points and the endpoints to find two cubic curves:
(: fit-cubics (-> Vector2D Vector2D Vector2D Float (Values Vector2D Vector2D Vector2D Vector2D ; cubic 1
Vector2D Vector2D Vector2D Vector2D))) ; cubic 2
(define (fit-cubics v0 v1 v2 t)
(let-values (((cp1 cp2) (calc-control-points v0 v1 v2 t)))
(let-values (((ca0 ca1 ca2 ca3) (quadratic->cubic v0 cp1 v1))
((cb0 cb1 cb2 cb3) (quadratic->cubic v1 cp2 v2)))
(values ca0 ca1 ca2 ca3 cb0 cb1 cb2 cb3))))
And finally, it all worked!
Cheers, Cel Skeggs.
The current version of my code is v0.1.6: 95619bad551f93d084e43fd25e9cc5fbb50387e8.
These actually weren't that hard! However, I'm not completely satisfied with these - the lengths of the splines aren't preserved properly. Just look at those arms.
(Behind the scenes, I also abstracted out the limb handling code so that I didn't duplicate it across right-arm vs left-arm, which will come in handy once I start using it for legs too.)
I might want to try writing my own spline-handling code, but I'm not sure if that would be efficient enough compared to what's probably GPU-rendered splines.
Cheers, Cel Skeggs.
More faces! (Minipost)
I also fixed a bug causing the face to disappear in rare occasions, and a bug preventing me from saving any patterns with an 'n' in a setting name.
The ability to switch between faces also required some more rendering infrastructure.
Also, I figured out that running my program from the shell is slightly faster to typecheck than running it from DrRacket.
Face rotation! (Minipost)
The only previous option for face direction:
Some of the unlimited number of new options:
Remember the issues with expensive contracts?
The worst part was this:
To solve the problem (mostly), I extracted a separate untyped file that would wrap all of the drawing operations, so that none of the expensive interfaces would be typechecked.
I correspondingly wrapped everything in opaque types:
[#:opaque ColorInst wd:color?]
[#:opaque PenInst wd:pen?]
[#:opaque BrushInst wd:brush?]
[#:opaque Context wd:context?]
I tested the relative timing by thunking out the main code (wrapping it in a thunk call), which would run everything except actually running the program.
Hooray! That's nearly half the typechecking time chopped off.
A quick note - I've added a commenting system to this blog! It may undergo further evolution, but it works.
You can log in with a Google account and then post away.
We are shocked!
My figures have now developed faces!
Unfortunately, they've yet to develop emotions, so they all just look shocked thanks to fix mouth shapes.
How much work did this take to implement?
The hardest part was probably figuring out the math behind translating along a sphere:
(: x*c (-> Vector2D Float Vector2D))
(define (x*c v s)
(vec (* (vec-x v) s) (vec-y v)))
(: translate-along-sphere (-> Vector2D Vector2D Vector2D Float Vector2D))
(define (translate-along-sphere center top align tx)
(let* ((rel-top (v- top center))
(rel-align (v- align center))
(radius (vlen rel-top))
; such that (= (vrotate-rad rel-top rotation-to) (vec 0 radius))
(rotation-to (atan (vec-x rel-top) (vec-y rel-top)))
(rot-align (vrotate-origin-rad rel-align rotation-to))
(x-for-the-y (sqrt (- (sq radius) (sq (vec-y rot-align)))))
(scale-factor (/ x-for-the-y (vec-x rot-align)))
(inv-scale-factor (/ 1 scale-factor))
(scalerot-align (x*c rot-align scale-factor))
; (/ tx radius) is the translation of length tx around a circle of length radius, in radians!
(translation (- (/ tx radius)))
(scalerot-tx (vrotate-origin-rad scalerot-align translation))
(rel-tx (vrotate-origin-rad (x*c scalerot-tx inv-scale-factor) (- rotation-to)))
(final-tx (v+ rel-tx center)))
(This is approximate; I had to do a couple of other things to get it to typecheck.)
Essentially, this algorithm recenters and rotates the head, and then scales the target point out to the border, and moves it a fixed amount around the border based on radius and expected distance, and then reverses all of those transformations.
After I had that working, I needed a few more rendering styles:
(define eye-style (r:wrap-style "black" 1 'solid "black" 'solid))
(define nose-style (r:wrap-style "gray" 1 'solid "gray" 'solid))
(define mouth-style (r:wrap-style "black" 2 'solid "white" 'solid))
A handle for the face (the only part manipulatable right now, which controls the face's position):
(define face (attach-joint-rel! jts 20.0 0.0 head))
Which needs to be kept within the head area:
(attach-limited-bone! skel face head 0.6)
Three corners of the head circle:
(define top-of-head (dynamic-joint scale () () (head)
(v- head (vec 0.0 (scale* scale 0.7)))))
(define right-of-head (dynamic-joint scale () () (head)
(v+ head (vec (scale* scale 0.7) 0.0))))
(define left-of-head (dynamic-joint scale () () (head)
(v- head (vec (scale* scale 0.7) 0.0))))
And some virtual joints for the positions of the mouth, nose, and eyes via rotation around the sphere on axes defined by the head's corners:
(define nose (dynamic-joint scale () () (face head top-of-head)
(translate-along-sphere head top-of-head face (scale* scale 0.2))))
(define mouth (dynamic-joint scale () () (face head top-of-head)
(translate-along-sphere head top-of-head face (scale* scale 0.4))))
(define left-eye (dynamic-joint scale () () (face head top-of-head right-of-head)
(translate-along-sphere head right-of-head face (scale* scale 0.2))))
(define right-eye (dynamic-joint scale () () (face head top-of-head left-of-head)
(translate-along-sphere head left-of-head face (scale* scale 0.2))))
And finally some circles for the actual rendering:
(attach-circle! pat left-eye 0.07 eye-style)
(attach-circle! pat right-eye 0.07 eye-style)
(attach-circle! pat nose 0.03 nose-style)
(attach-circle! pat mouth 0.1 mouth-style)
This actually doesn't seem like all that much - that's the advantage of spending so long on infrastructure!
Here's the editor view of that scene:
(Which, by the way, I loaded from a savefile saved when I made the original image. And it came back exactly the same!)
The current version of my code is v0.1.5: ad10fe891548dae3a89561743ae1590c747b4b1a.
After a bunch of time chatting with people familiar with Typed Racket, including its developers on IRC, I determined one of the main causes of my slowdown.
(define-type Renderer (Pairof (-> (Instance DC<%>) Void) (-> Float Float Boolean)))
The worst part is this:
Essentially, this is a type specifier for instances conforming to an interface. Said interface,
DC<%>, is BIG. The generated contracts have to cover the entire interface to check that objects are properly behaved!
This is, of course, very annoying, as I don't actually NEED most of the contracts! They're primarily used for interactions between typed and untyped code, which isn't a thing I'm doing.
The worst part is that there is no easy fix.
- Wait until one of Typed Racket's developers gets around to improving contract generation for interfaces. (This would be a while.)
- Switch over to untyped Racket. (This would mean losing all of the benefits of Typed Racket.)
- Switch all of my modules to
typed/racket/no-check, which means that all the type declarations are ignored. (This also means losing all the benefits, but makes it possible to go back to Typed Racket more easily.)
typed/racket/unsafe, which skips contract generation. This might have some issues w/r/t being unsafe in the presence of typed-untyped interactions (not a thing), but also unsafe in the presence of casts (a thing.) (This might work.)
- Offload everything that needs to interact with DC<%> into a separate untyped file, and wrap it thoroughly enough that it doesn't affect any types. (This would add some runtime overhead, but it might be justified.)
I may choose the last one, but I'm going to do a bit more work on other things first.
Optimizations 2: Electric Boogaloo! (minipost)
I solved the optimization problem with a single solution!
(define (process-channel func channel)
(let loop ((value (async-channel-get channel)))
(let ((v2 (async-channel-try-get channel)))
(process-channel func channel)))
(define (dropping-worker func)
(define channel (make-async-channel))
(lambda () (process-channel func channel)))
(async-channel-put channel work)))
How does this snippet of code help?
It provides a useful abstraction for running operations in another thread: you call the function returned by
(dropping-worker f) on a parameter, which runs
f on that parameter in another thread! Easy!
... but how does that help? Well, we actually do a second thing, in
process-channel: we grab an item to run off of the message channel... and then, as long as there's something else available on the channel, we discard our current value and take the next one. This means that, essentially, we collapse everything remaining down into just one item to process. In our case, that works, because rendering twice should, in theory, give us the same result both times.
This now means that we don't have a huge number of rendering events to process - at any point in time, we just need to finish the current render and do one more in order to be up-to-date. This gets rid of the lag issue with trying to move around anything a significant amount.
What's the trade-off? Well, now we do have jitter, but it's minimal at low usage counts, and even with around 21 characters on the screen, it's still mostly usable:
At this point, the lag problem is solved. I still have the typed racket typechecking lag to think about - it takes about 35 seconds to typecheck my program! Since it does that every single time, iteration is very hard. I could be much more productive if this didn't take so long, so I plan to spend a bit of time trying to fix it.
Latest work: after a bunch of optimizations, involving a bunch of type specifying and other things according to the optimization helper, the lag in the viewer is much improved!
Specifically, the system now doesn't slow down at all, until the seventh figure, whereas the earlier version slowed significantly down at the third figure.
The old version became annoyingly slow here:
The new version got up to eight figures before being annoyingly slow:
I do plan to make this even better shortly, before I move on. Also, I may take a divergence to see if I can optimize Typed Racket's typechecking at all.
Just to show that I was actually working, here's the diffstat output for that last version:
editor.rkt | 12 +----------
entity.rkt | 29 ++-----------------------
functional-graphics.rkt | 10 ++++++++-
geometry.rkt | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++
gui-controls.rkt | 7 ++++---
joints.rkt | 147 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
main.rkt | 3 ++-
pattern-base.rkt | 94 ++++++++++++++++++++++++++++++++++++++++++++++++------------
pattern-box-figure.rkt | 90 ++++++++++++++++++++++++++++++++++++++----------------------
pattern-stick-figure.rkt | 44 +++++++++++++++++---------------------
saving.rkt | 5 +++--
setting-group.rkt | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
setting.rkt | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
skeleton.rkt | 190 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
utils.rkt | 68 +++++++++++++++++++++++++++++++++++++++++++++--------------
vector.rkt | 6 +++++-
16 files changed, 674 insertions(+), 293 deletions(-)
I've been very busy with everything else this past month, so my work on this project has been mostly limited to class time.
Unfortunately, that means that something that should have been faster took quite a while.
So what did I do? Settings!
Specifically, all entities have saveable-and-loadable settings, arbitrarily definable. This required lots of work on Setting Groups, Setting Prototype Groups, Settings, and Setting Prototypes, in addition to reworking of the scale setting to use the same system.
Currently, there are a few too many places where I snuck around typing issues with a
cast, but it all seems to work. Also, both compilation and running the program are starting to get pretty slow... the part of building the program being slow is a known Typed Racket issue, and the part with the probably is probably an inefficiency in my code.
Now, what did I do with settings?
I added a geometry module, which lets me do things like automatically choose the elbow's position based on hand position. However, there are two options for the elbow position for a specific hand position, so I needed options, which mean I needed the entire setting infrastructure, and that's why this feature took a month.
Behind the scenes, none of the elbow positions for these figures are specified:
Each one has options for whether the elbow is going up or down. This system, despite requiring a lot more code, is very useful from a usability standpoint.
(One other reason this took so long is that it also required extending the saving-and-loading system to handle settings, setting prototypes, setting groups, and setting prototype groups.)
Where do I go next with this? Well, unfortunately, the long compile times and the lag in the viewer are a big enough problem that I'm going to have to tackle them before going further. There's no sense in working with tools that slow you down.
The current version of my code is v0.1.4: 6416dae2250235017dfe29666e1a2beb3804af57.
Colors and Polygons! (minipost)
(: attach-poly! (->* (PatternDef (Listof JointRef)) (Style) Void))
(define (attach-poly! pat joints [style r:all])
(attach-renderer! pat (lambda ([vecs : (Listof Vector2D)] [scale : Scale])
(style (r:poly (for/list ((joint joints))
(joint-v-ref scale vecs joint)))))))
Bloopers I (minipost)
I made some mistakes with a different model...
And then finally got something slightly better:
This is supposed to vaguely mimic the original art style of the OOTS comics. These are a lot simpler than some of what I plan to get to, but require more advanced techniques than the stick figures.
The current version of my code is v0.1.3: 339c3c63effe0429d00eff08a8f0644e5d93fa0b.
Recently, I restructured everything in my codebase. This was because it wasn't designed well and was getting unwieldy. Now that's fixed!
As part of the restructuring, I added better support for multiple figures (namely, deleting them), added support for settings on each of these figures, and added the ability to save and load projects!
The current best example of a setting is the scale factor, as demonstrated in the above image.
The save files look something like this:
((#s(par-vec 248.35514557749573 228.90217394558664)
#s(par-vec 251 262)
#s(par-vec 251.57608258650384 309.4298349139509)
#s(par-vec 232.52938044236288 276.876709681069)
#s(par-vec 218.08089278361678 258.06922494352796)
#s(par-vec 239.18650979546277 282.56506083057087)
#s(par-vec 220.16354247181653 268.4014810577428)
#s(par-vec 246.0915057349493 337.3563638203401)
#s(par-vec 248.83407109419204 365.6839111065116)
#s(par-vec 251.45769568048397 337.8895886820439)
#s(par-vec 254.1542010763213 366.22155752732925))
They're saved with Racket's reading/writing capabilities, with a bit of processing on top to handle vectors.
One of the downsides to the current setup is that the descriptions for patterns are noticably longer... but that's because I realized that the brevity wasn't going to be helpful once I moved beyond stick figures.
The current interface looks something like this:
So, anyway, this means that I've completed three of the four next steps from two posts ago!
I haven't done Perspective yet, because I'm not 100% sure that it will be immediately helpful, and I don't want to have to rewrite a bunch of stuff again right now.
The good news: now I can do something more relevant to my actual project!
(I'll post again soon with more details.)
The current version of my code is v0.1.2: 6e13fbda269fe8911b6294736ec19e66fa9585b3.
Multiple Figures! (minipost)
What's next? (an addendum to 'Typed Racket!')
Some of my next steps include:
Currently, sizing is based on fixed bone lengths.
This would be accurate if the characters lived in Flatland, but they're supposed to look slightly 3d-ish.
It needs to be possible to edit options and settings (such as sizing or character-specific changes) in a way that isn't just dragging handles.
Saving and loading!
Currently, everything gets lost when you close the program. You can save images, but that's not the same.
Nothing you actually want to draw has only a single stick figure! I need to be able to put multiple on a canvas.
Recent updates on my progress:
I've switched to Typed Racket!
This is a dialect of Racket that has type annotations for everything. (In
the same vein as Haskell, but not as pure or well-developed.)
Here's a snippet of this:
(: vdist (-> v v Nonnegative-Real))
(define-provide (vdist v1 v2)
(sqrt (vdist-sq v1 v2)))
(: vin-origin-circle? (-> v Nonnegative-Real Boolean))
(define-provide (vin-origin-circle? v radius)
(< (vlen-sq v) (sq radius)))
(: vin-circle? (-> v v Nonnegative-Real Boolean))
(define-provide (vin-circle? needle center radius)
(vin-origin-circle? (v- needle center) radius))
Of course, it's not always helpful. I can't write this:
(: sq (-> Real Nonnegative-Real))
(define-provide (sq x)
(* x x))
because it only knows that
(: * (-> Real Real Real)) and can't realize
that a real number times itself is never negative.
It DOES know this, though:
(: * (-> Nonnegative-Real Nonnegative-Real Nonnegative-Real))
(: * (-> Negative-Real Negative-Real Nonnegative-Real))
so I was able to use the following:
(: sq (-> Real Nonnegative-Real))
(define-provide (sq x)
(if (positive? x)
(* x x)
(* x x)))
Annoying? Yes, but I've only had to do this once in my codebase so far.
(Why this works is left as an exercise to the reader, but it's really not
I finished the basic skeleton and stick figure!
As you can see, this looks better than before, namely because it has more
joints. While I could have done this with the previous system, I rewrote a
bunch of the bone handling code so that the main part of my code looks like
(r:define-style simple-style "black" 6 'solid "white" 'solid)
(compose simple-style 500 500
(root collar 250 250)
(line-bone pelvis collar 0 100)
(line-bone head collar 0 -70 (r:circle head 50))
(line-bone-chain (left-hand -50 0) (left-elbow -50 0) collar)
(line-bone-chain (right-hand 50 0) (right-elbow 50 0) collar)
(line-bone-chain (left-foot 0 60) (left-knee -42 42) pelvis)
(line-bone-chain (right-foot 0 60) (right-knee 42 42) pelvis))
This is a big improvement over previous versions where I would have to
specify the name of something (like, say, 'head') multiple times in different
places for the same bone. Now, I can make things easier by defining macros
(line-bone-chain (variant dx dy extra-renders ...) ... invariant) to
simplify the skeleton definition.
I have built-in image saving now!
I still have to take screenshots if I want to show the interface...
... but I can also just press the yellow button to save the current image.
(The first stick figure shown in this post is an example of that in action.)
Yes, having the buttons to control it be unmarked solid colors doesn't make
for a good user experience, but the point of this project isn't to build a
Let's see where this goes.
The current version of my code is v0.1.1: d1fb88b65e6c5376a3ff19d7343f7f8a59d29e01.
This blog is about Scribbles (final name pending), a computer science project about computer art.
Not art as in fractals or anything, but rather art as in illustration art as would be drawn by a human using a computer.
Here's an example of what I mean (a stick figure drawn by my current early prototype):
And with the handles visible:
As an example, take a look at this speedpaint from an artist.
That should make the (very approximate) art style clear; and examples like that of how humans can draw will be very useful - to draw like a human, one should probably use techniques used by humans.
This is an extremely difficult idea! I find it likely that I may fail, but I do understand that. In any case, it'll be an interesting learning experience!
Let's see where this goes.
The current version of my code is v0.1.0: c092f74d801a1f65e98ea1d6e5823343bf561a3b.