9
$\begingroup$

I'm working a little program that converges on vector-based approximations of raster images, inspired by Roger Alsing's genetic Mona Lisa. (I started on this after his first blog post two years ago, played a bit, and it's been on the back burner. But I'd like to un-back-burner it because I have some interesting further ideas.)

Roger Alsing's program uses randomly-generated sometimes-self-overlapping n-gons. Instead, I'm using Bézier splines linked into what, for lack of a math education, I am calling "Bézier petal" shapes. These are, simply, two cubic Bézier curves which share end points (but not control points). You can see this in action in this little youtube video.

The shapes I'm currently using are constructed by generating six random points. These are then sorted radially around their center of gravity, and two opposite points become the end-points of the two cubic Bézier curves, with the other four points used as control points where the fit into the order.

Because I, as I mentioned, have no math background, I can't prove it, but empirically this guarantees a non-degenerate petal, with no overlaps or twists. But, it's frustratingly limiting, since it will never produce crescents or S shapes — theoretically-valid "petals". (The results are not always convex, but concavities can only happen at the end points.)

(Here's a video of what happens if I allow self-intersecting shapes — not graceful.)

I'd love suggestions for a process which generates all possible non-intersecting shapes. It's clearly better for the application if the process can be done with minimal computation, although I'm willing to pay a bit of time in exchange for nicer results.

A further constraint is that small changes in the "source" data — in the current case, the six random points — needs to produce relatively small changes in the output, or else my stochastic hill-climbing approach can't get anywhere.

Also, it's fine if some input values produce no output — those will just get discarded.

Another possible way of asking the same question: is there an optimization for finding whether two cubic Bézier curves that share endpoints intersect? If I can calculate that quickly, I can simply discard the invalid ones.

$\endgroup$
5
  • 1
    $\begingroup$ Roughly speaking, the shape formed by drawing the polygon is an approximation to the shape formed by the curve. So if you consider all 60 distinct polygons formed by the 6 points and discard the self-intersecting polygons you're unlikely to get self-intersecting Béziers. Proving that you get none is harder. $\endgroup$
    – Peter Taylor
    Commented Feb 4, 2011 at 19:28
  • $\begingroup$ Thanks Peter. That makes sense. Basically, my current function makes star-shaped (including convex) polygons, but not all of them and not non-star simple concave ones. Including some of those would broaden the results, and I think you're right that non-self-intersecting hexagons are unlikely (if not unable) to yield invalid petals. Some self-intersecting polygons do produce valid results, so it's not perfect, but definitely better. Now, to figure out either a better connect-the-dots function or else a fast test for validity. I'll go do some "homework", and then maybe that's a 2nd question. $\endgroup$
    – mattdm
    Commented Feb 4, 2011 at 21:39
  • $\begingroup$ FWIW I actually thought that the video you posted with self-intersections had a pretty good use of them for the eyes. I've also played around with that Mona Lisa image and genetic algorithms, possibly even with Béziers (can't find the code atm), and it always annoyed me that it tended to converge on a solid bar for the eyes. $\endgroup$
    – Peter Taylor
    Commented Feb 4, 2011 at 23:07
  • $\begingroup$ Yeah, the mona-bar-eyes problem is interesting. The use of them in that example is effective, but not aesthetically appealing to me. $\endgroup$
    – mattdm
    Commented Feb 5, 2011 at 21:00
  • $\begingroup$ It goes beyond subjective aesthetics, though. One of the problems with the original program which inspired all of this is that it doesn't have enough limits. The end result is either a perfect representation of the original, or, if you give up before then, an inefficiently color-quantized version. In other words, an interesting process that gives boring results. By introducing limitations, the end results are more interesting. Matching the limitations to the source is then an interesting artistic experiment. (I think Mona lends herself well to circles, for example.) $\endgroup$
    – mattdm
    Commented Feb 5, 2011 at 21:03

1 Answer 1

Reset to default
3
$\begingroup$

One way of finding out whether two Bezier curves sharing the endpoints intersect is to calculate all the intersections of two general Bezier curves and discard the $0$ and $1$ parameters from the solutions.

One way of calculating the intersections of two Bezier curve is the well known "subdivision" method: when the convex hulls of two Bezier curves do not overlap, the curves cannot overlap neither. If they do overlap, subdivide both the curves with De Casteljau's algorithm and recurse with all the combinations so that you check each part of the first curve with each of the parts of the second curve. Stop if convex hulls are small enough or if they can be approximate by a line segment, in which case simply compute their intersection.

Alternatively, as you are interested in a visual setting, chop off the ends of one of the curves (i.e., remove the parts with parameter $[0, \epsilon]$ and $[1-\epsilon, 1]$, where $\epsilon$ is a small number), so that you don't look for intersection at the endpoints only to discard them later.

More on intersection methods of Bezier curves can be found in Comparison of three curve intersection algorithms by Sederberg and Parry (1986).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .