[OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Denis Lila
dlila at redhat.com
Tue Oct 19 17:40:05 UTC 2010
Hi Jim.
> line 249,257 - these corrections are exponential compared to the
> sample code on the wikipedia page - was that the "slight modification" that
> you mentioned in the comments?
That's right. This turned out to be necessary because a lot of the numbers
dealt with in this code are very large. Increasing the scaling factor
exponentially makes it a lot faster and it doesn't behave much differently
when it gets close to the root since by that point side tends to change sign
so it never becomes larger than 2 or 3.
> ROCsq - I looked at the wikipedia article and it wasn't clear how it
> directly related to your function since the article is dealing with
> the curvature of a function graphed against its own t, but you are dealing
> with 2 parametric equations combined and graphed against each other.
> I think I'm going to have to just trust you on this one for now. :-(
http://en.wikipedia.org/wiki/Radius_of_curvature_%28applications%29
Did you look at the above wikipedia article? When researching I came across
2 of them, and one of them only mentions natural parameterizations, but
the above has the general equation for a R->Rn function, then below that
they have the special case where n=2, x(t)=t, and y(t)=f(t). I used the
first equation on that page.
Actually, I wrote a simple program to make sure the radius of curvature
function was correct. I have attached it. It's not a proof, but I think
it is convincing. Just hold down the mouse button and move it horizontally.
This will change the t value on the curve and the circle drawn will have
radius equal to Math.sqrt(ROCsq). You can also change the control points of
the curve. There's a bug where when you run it the window is really tiny, so
you have to manually resize it and maximize it.
> lines 621-626 and 643-646 - I'm not sure what the derivation of these
> lines are. I tried to do my own equations, but I seem to be heading
> in a different direction than you used and it didn't seem like I was
> going to converge. What equations did you set up to solve to get these
> calculations? From what I can see we have:
> - new p1,p4 are calculated
> - new p(0.5) is calculated
> - the corresponding dx,dy at t=0,0.5,1 (gives slopes)
> - slopes at t=0, 0.5 and 1 should be the same for all curves
> and what you are trying to compute are two scaling constants c1 and c2
> that represent how much to scale the dx1,dy1 and dx4,dy4 values to get
> a curve that interpolates both position and slope at t=0.5. A comment
> might help here... :-(
I see how (dxm,dym) was confusing. The only reason for computing the slope
at t=0.5 is to get the point of the offset curve at t=0.5. We don't make
the computed curve and the input curve have equal slopes at t=0.5 because
this would give us an overdetermined system. What we're trying to do in this
function is to approximate an ideal offset curve (call it I) of the input
curve B using a bezier curve Bp. The constraints I use to get the equations are:
1. The computed curve Bp should go through I(0) and I(1). These are computed
in lines 661,662,665,666. This gives us p1p and p4p. We still need to find
4 variables: the x and y components of p2p and p3p (i.e. x2p, y2p, x3p, y3p).
2. Bp should have slope equal in absolute value to I at the endpoints. So,
(by the way, "v1 || v2" below, means "vector v1 is parallel to vector v2")
I'(0) || Bp'(0) and I'(1) || Bp'(1). Obviously, I'(0) || B'(0) and
I'(1) || B'(1); therefore, Bp'(0) || B'(0) and Bp'(1) || B'(1).
We know that Bp'(0) || (p2p-p1p) and Bp'(1) || (p4p-p3p) and the same
is true for any bezier curve; therefore, we get the equations
(1) p2p = c1 * (p2-p1) + p1p
(2) p3p = c2 * (p4-p3) + p4p
We know p1p, p4p, p2, p1, p3, and p4; therefore, this reduces the number
of unknowns from 4 to 2 (i.e. just c1 and c2).
To eliminate these 2 unknowns we use the following constraint:
3. Bp(0.5) == I(0.5). I(0.5) is computed in lines 663,664, and I should
note that this is *the only* reason for computing dxm,dym. This gives us
(3) Bp(0.5) = (p1p + 3 * (p2p + p3p) + p4p)/8, which is equivalent to
(4) p2p + p3p = (Bp(0.5)*8 - p1p - p4p) / 3
We can substitute (1) and (2) from above into (4) and we get:
(5) c1*(p2-p1) + c2*(p4-p3) = (Bp(0.5)*8 - p1p - p4p)/3 - p1p - p4p
which is equivalent to
(6) c1*(p2-p1) + c2*(p4-p3) = (4/3) * (Bp(0.5) * 2 - p1p - p4p)
The right side of this is a 2D vector, and we know I(0.5), which gives us
Bp(0.5), which gives us the value of the right side.
The left side is just a matrix vector multiplication in disguise. It is
[x2-x1, x4-x3][c1]
[y2-y1, y4-y3][c2]
which, in Stroker, is equal to
[dx1, dx4][c1]
[dy1, dy4][c2]
At this point we are left with a simple linear system and we solve it by
getting the inverse of the matrix above. Then we use [c1,c2] to compute
p2p and p3p.
I think using Bp'(0.5) || I'(0.5) instead of Bp(0.5)==I(0.5) only eliminates
1 variable and leaves us with 1 unknown. This brings up the interesting possibility
of replacing constraint 3 with: Bp'(1/3) || I'(1/3) and B'(2/3) || I'(2/3). I guess
this is something to implement sometime in the future just to compare with the
current equations. But what we have now works pretty well, so I'm in no rush.
I've implemented everything else you suggested.
Regards,
Denis.
----- "Jim Graham" <james.graham at oracle.com> wrote:
> Round 4...
>
> On 10/6/2010 1:36 PM, Denis Lila wrote:
> >
> > webrev:
> > http://icedtea.classpath.org/~dlila/webrevs/noflatten/webrev/
>
> BezCurve.java:
>
> I'd add some "set()" methods to BezCurve/Curve and then use a scratch
>
> instance in Renderer (and other places?) to reuse those calculations,
>
> such as:
>
> Curve constructors (obviously)
> Renderer.curveOrQuadTo()
> Renderer.initQuad()
> Renderer.initCurve()
> Stroker.findSubdivPoints()
>
> lines 179,182 - using your d* variables, wouldn't these be:
> a = 2*(dax*dax + day*day)
> b = 3*(dax*dbx + day*dby)
> c = 2*(dax*cx + day*cy) + dbx*dbx + dby*dby
> d = dbx*cx + dby*cy
> It has fewer multiplies and more of the multipliers are powers of 2
> which are faster than non-power-of-2 multiplies.
>
> line 206,210 - a nit - it didn't really confuse me, but halfway
> through
> reading this it occurs to me that these are really t0 and t1, right?
>
> line 212 - if x0 (t0?) is 0 then you don't need to include it in the
> roots, no?
>
> line 303 - isn't it enough to just look at the previous T value (or
> keep
> a running "prevt" variable) rather than update every T value in the
> array? Isn't this enough?
> int prevt = 0; /* field in Iterator */
> next() {
> curt = Ts[next];
> split = (curt - prevt) / (1 - prevt);
> prevt = curt;
> }
>
> Done with BezCurve.java...
>
> Stroker.java:
>
> lines 558 (et al) - create a helper function for all of these
> (degenerates to a line) cases?
>
> line 687 - dup?
>
> line 856 - use a scratch Curve instance and set methods to reduce GC?
>
> line 857 - this is true if the first vector is parallel to either
> axis,
> but the comment after it says only "parallel to the x axis" - is that
> a
> problem? Also, if both are 0 then no parallel constraint is applied
> even if it does start out parallel. I imagine that this is all OK
> because the "both 0" case should be rare/non-existant and the y-axis
> case will also benefit from the same optimization...?
>
> lines 861-863: sin/cos and atan2 cancel each other out. It is faster
>
> to compute the hypotenuse and then divide the x and y by the
> hypotenuse
> to get the cos and sin. (cos = x/hypot; sin = y/hypot;)
>
> Cache and TileGenerator look ok...
>
> I think I'm done at this point except for not understanding the
> "parallel cubic" equations I mentioned above and the ROCsq method...
>
> ...jim
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ROCDemo.jar
Type: application/x-java-archive
Size: 22198 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20101019/3c0bb980/ROCDemo.jar>
More information about the 2d-dev
mailing list