

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
Object dmj5:DMJ_PolyCurve
class
PolyCurve tool class.
PolyCurve is a helper class that you can use to define,
manage, and render a shape composed of connected lines
and curves. Each segment may be one of these:
 a straight line
 a quadratic Bézier curve; these are used to create
TrueType font shapes, because they are mathematically
easy to render at any resolution
 a cubic Bézier curve; these are used in highend
vector illustration programs (e.g. Adobe Illustrator)
and in PostScript fonts, as they are more flexible
than quadratic curves, but they are harder to render
Cubic Bézier curves are so difficult to render that this
class actually does not render them directly; instead,
it converts cubic curves to a set of very small straight
line segments, and renders from that. Usually this is
not noticeable, but you should be aware of this if you
use this class in unusual contexts.
This class is not derived from anything as it does not
have any userexposed parameters. Your code must provide
all the parameters you require. You must call Rasterize()
before making any queries about the curve, or you will
get erroneous results. Changing curve data after it has
been rasterized will not affect any queries.
This code is adapted from DeluxeClipping, which I wrote
for Janet Parke's course on Masking with Ultra Fractal.
The cubic Bézier support is new for UF5. The additional
query modes are also new.
class DMJ_PolyCurve { ; PolyCurve tool class. ; ; PolyCurve is a helper class that you can use to define, ; manage, and render a shape composed of connected lines ; and curves. Each segment may be one of these: ; ;  a straight line ;  a quadratic Bézier curve; these are used to create ; TrueType font shapes, because they are mathematically ; easy to render at any resolution ;  a cubic Bézier curve; these are used in highend ; vector illustration programs (e.g. Adobe Illustrator) ; and in PostScript fonts, as they are more flexible ; than quadratic curves, but they are harder to render ; ; Cubic Bézier curves are so difficult to render that this ; class actually does not render them directly; instead, ; it converts cubic curves to a set of very small straight ; line segments, and renders from that. Usually this is ; not noticeable, but you should be aware of this if you ; use this class in unusual contexts. ; ; This class is not derived from anything as it does not ; have any userexposed parameters. Your code must provide ; all the parameters you require. You must call Rasterize() ; before making any queries about the curve, or you will ; get erroneous results. Changing curve data after it has ; been rasterized will not affect any queries. ; ; This code is adapted from DeluxeClipping, which I wrote ; for Janet Parke's course on Masking with Ultra Fractal. ; The cubic Bézier support is new for UF5. The additional ; query modes are also new. public: import "common.ulb" ; $define debug func DMJ_PolyCurve() m_WindingMode = 0 m_Roots = new ComplexArray(3) endfunc ; set the winding mode ; pmode = winding mode: ; 0 = fully selfintersecting (default) (like "invert overlaps" in DeluxeClipping) ; 1 = individual loops not selfintersecting, subsequent loops may intersect ; 2 = entire curve not selfintersecting (like "all inside" in DeluxeClipping) func SetWindingMode(int pmode) m_WindingMode = pmode endfunc ; set the endpoint extension mode ; pmode = extension mode: ; 0 = none (cap endpoints) ; 1 = extend lines ; 2 = extend curves (not implemented) func SetExtensionMode(int pmode) m_EndpointExtensionMode = pmode endfunc ; set the number of curve segments ; you must call this prior to setting any curve data func SetSegmentCount(int ppoints) setLength(m_Anchors, ppoints) setLength(m_Control1, ppoints) setLength(m_Control2, ppoints) setLength(m_Lengths, ppoints) setLength(m_Types, ppoints) setLength(m_Auto, ppoints) m_AnchorNext = 0 m_AnchorHighest = 1 endfunc ; set parameters for a segment ; note: do not manually specify a close point; use the ; autoclose flag instead. Otherwise, your shape may not ; render correctly (it will "leak"). ; ppoint = slot number (use 1 for next slot) ; ptype = segment type: 0 = none (close), 1 = linear, 2 = quadratic (use pcontrol1), 3 = cubic (use pcontrol1 and 2) ; pauto = autocompute controls: 1 = close, 2 = smooth, 4 = curvature smooth func SetSegment(int ppoint, int ptype, int pauto, complex panchor, complex pcontrol1, complex pcontrol2) if (ppoint == 1) ppoint = m_AnchorNext m_AnchorNext = m_AnchorNext + 1 endif if (ppoint > m_AnchorHighest) m_AnchorHighest = ppoint endif print("segment ", ppoint, ": type ", ptype, " auto ", pauto, " ", panchor, " ", pcontrol1, " ", pcontrol2) m_Anchors[ppoint] = panchor m_Control1[ppoint] = pcontrol1 m_Control2[ppoint] = pcontrol2 m_Types[ppoint] = ptype m_Auto[ppoint] = pauto endfunc ; rasterize a set of curve segments that may contain ; cubic segments into lines and quadratic segments; ; also performs autocompute at this time ; pflags = extra computation flags: 1 = compute segment lengths (needed for ClosestPoint, DistanceAlongCurve), 2 = compute normals (needed for ClosestCurve) func Rasterize(int pflags) ; count number of straight/quadratic segments we will need ; and perform auto computations int j = 0 int k = 0 int l = 0 int m = 0 int n = 0 int segmentcount = 0 int quadraticcount = 0 int loopstart = 0 int loopnext int loopprevious int looprealstart bool computenormals = (pflags % 4 >= 2) bool computelengths = (pflags % 2 == 1) float s float t float totallength = 0 complex point complex point2 print("Rasterize() trace") while (j <= m_AnchorHighest) print("segment ", j) ; determine next loop segment (autoclose handled here) loopnext = j + 1 if (m_Auto[j] % 2 == 1) loopnext = loopstart segmentcount = segmentcount + 1 print("autoclose to segment ", loopnext) endif ; count the segment if (m_Types[j] < 2) segmentcount = segmentcount + 1 elseif (m_Types[j] == 2) segmentcount = segmentcount + 1 quadraticcount = quadraticcount + 1 if (m_Auto[j] % 4 >= 2) loopprevious = j  1 if (loopprevious < loopstart) ; autosmooth at the start of the curve; find the end k = j while (k < length(m_Anchors) && loopprevious < j) if (m_Auto[k] % 2 == 1  m_Types[k] == 0) loopprevious = k endif k = k + 1 endwhile if (m_Types[loopprevious] < 2) m_Anchors[j] = m_Anchors[loopprevious] else m_Anchors[j] = (m_Control1[j] + m_Control1[loopprevious]) / 2 endif else m_Anchors[j] = (m_Control1[j] + m_Control1[loopprevious]) / 2 endif print("smoothed to ", loopprevious, " ", m_Anchors[j]) endif else segmentcount = segmentcount + 1024 ; **** this number should be dynamic ; **** perform auto here endif if (m_Auto[j] % 2 == 1  m_Types[j] == 0) loopstart = j + 1 endif j = j + 1 endwhile print("total expanded segments: ", segmentcount) ; create updated arrays and copy over segments setLength(m_RealIsStartPoint, segmentcount) setLength(m_RealIsEndPoint, segmentcount) setLength(m_RealAnchors, segmentcount) setLength(m_RealControls, segmentcount) setLength(m_RealAnchorNormals, segmentcount) setLength(m_RealControlNormals, segmentcount) setLength(m_RealExitNormals, segmentcount) setLength(m_RealNormals, segmentcount) setLength(m_RealLengths, segmentcount) setLength(m_RealSummedLengths, segmentcount) setLength(m_RealTypes, segmentcount) setLength(m_RealA, segmentcount) setLength(m_RealB, segmentcount) if (computelengths) setLength(m_RealSubLengths, quadraticcount*256) setLength(m_RealIndex, segmentcount) endif j = 0 k = 0 l = 0 loopstart = 0 loopnext = 0 looprealstart = 0 while (j <= m_AnchorHighest) ; set up endpoint if (looprealstart == k) m_RealIsStartPoint[k] = true else m_RealIsStartPoint[k] = false endif m_RealIsEndPoint[k] = false ; determine next loop segment (autoclose handled here) loopnext = j + 1 if (m_Auto[j] % 2 == 1  m_Types[j] == 0) loopnext = loopstart loopstart = j + 1 endif ; copy over segment if (m_Types[j] == 0) ; explicit point (normally these are automatic) print("close point ", m_Anchors[j]) m_RealIsEndPoint[k] = true ; this marks an endpoint m_RealTypes[k] = 0 m_RealAnchors[k] = m_Anchors[j] m_RealSummedLengths[k] = totallength m_RealLengths[k] = 0 k = k + 1 looprealstart = k ; next segment will be a starting point else if (m_Types[j] == 1) print("line segment ", m_Anchors[j], " ", m_Anchors[loopnext]) m_RealTypes[k] = 1 m_RealAnchors[k] = m_Anchors[j] ; precompute length squared used to determine distance m_RealLengths[k] = m_Anchors[loopnext]  m_Anchors[j] m_RealSummedLengths[k] = totallength totallength = totallength + m_RealLengths[k] ; print("length: ", m_RealLengths[k]) ; print("summed: ", m_RealSummedLengths[k]) ; print("total: ", totallength) k = k + 1 elseif (m_Types[j] == 2) print("quadratic segment ", m_Anchors[j], " ", m_Control1[j], " ", m_Anchors[loopnext]) m_RealTypes[k] = 2 m_RealAnchors[k] = m_Anchors[j] m_RealControls[k] = m_Control1[j] ; precompute values used to determine distance m_RealA[k] = m_Anchors[j]  2*m_Control1[j] + m_Anchors[loopnext] m_RealB[k] = 2*m_Anchors[j]+2*m_Control1[j] t = m_RealA[k] if (t < 1e25) ; curve segment is too straight; call it a line! faster and avoids dividebyzero in ClosestPoint() print("straight quadratic (m = ", t, "), replacing with line") m_RealTypes[k] = 1 m_RealLengths[k] = m_Anchors[loopnext]  m_Anchors[j] m_RealSummedLengths[k] = totallength totallength = totallength + m_RealLengths[k] else if (computelengths) m_RealIndex[k] = l*256 m = m_RealIndex[k] n = m + 256 s = 0 t = 0 point = m_Anchors[j] ; $ifdef debug ; print("filling slot ", l, " from ", m, " to ", n) ; $endif while (m < n) t = t + 0.00390625 ; 1/256 point2 = InterpolateQuadratic(t, m_Anchors[j], m_Control1[j], m_Anchors[loopnext]) m_RealSubLengths[m] = cabs( point2point ) point = point2 s = s + m_RealSubLengths[m] ; $ifdef debug ; if (m % 16 == 0) ; print("sublength: ", m_RealSubLengths[m]) ; print("segment total: ", s) ; endif ; $endif m = m + 1 endwhile l = l + 1 m_RealLengths[k] = s ; total accumulated length m_RealSummedLengths[k] = totallength totallength = totallength + m_RealLengths[k] ; print("length: ", m_RealLengths[k]) ; print("summed: ", m_RealSummedLengths[k]) ; print("total: ", totallength) endif endif k = k + 1 elseif (m_Types[j] == 3) print("cubic segment ", m_Anchors[j], " ", m_Control1[j], " ", m_Control2[j], " ", m_Anchors[loopnext]) ; **** rasterize cubic curve here endif if (loopstart > j) ; this segment closed a loop m_RealIsStartPoint[looprealstart] = false ; make sure start/end points are cleared of endpoint status m_RealIsEndPoint[k] = false m_RealTypes[k] = 0 m_RealAnchors[k] = m_Anchors[loopnext] k = k + 1 looprealstart = k ; next segment will be a starting point endif endif j = j + 1 endwhile m_RealAnchorCount = k if (computenormals) ComputeNormals() endif endfunc ; Compute normals for a curve. ; For each segment, we compute the normal at the beginning, the ; control point, and the end. We then interpolate a "point normal" ; for each endpoint. Since computing normals is expensive, we don't ; automatically compute normals for every curve. func ComputeNormals() int segmentcount = m_RealAnchorCount int j = 0 complex exitnormal = 0 while (j < segmentcount) if (m_RealTypes[j] == 0) m_RealAnchorNormals[j] = exitnormal m_RealControlNormals[j] = exitnormal m_RealExitNormals[j] = exitnormal m_RealNormals[j] = exitnormal elseif (m_RealTypes[j] == 1) m_RealAnchorNormals[j] = m_RealAnchors[j+1]  m_RealAnchors[j] m_RealAnchorNormals[j] = m_RealAnchorNormals[j] / cabs(m_RealAnchorNormals[j]) exitnormal = m_RealAnchorNormals[j] m_RealControlNormals[j] = exitnormal m_RealExitNormals[j] = exitnormal elseif (m_RealTypes[j] == 2) m_RealAnchorNormals[j] = m_RealControls[j]  m_RealAnchors[j] m_RealAnchorNormals[j] = m_RealAnchorNormals[j] / cabs(m_RealAnchorNormals[j]) m_RealControlNormals[j] = m_RealAnchors[j+1]  m_RealAnchors[j] m_RealControlNormals[j] = m_RealControlNormals[j] / cabs(m_RealControlNormals[j]) m_RealExitNormals[j] = m_RealAnchors[j+1]  m_RealControls[j] m_RealExitNormals[j] = m_RealExitNormals[j] / cabs(m_RealExitNormals[j]) exitnormal = m_RealExitNormals[j] endif if (m_RealTypes[j] > 0) if (j > 0 && m_RealTypes[j1] > 0) ; not the first point, and previous segment has exit normal (not a point) m_RealNormals[j] = m_RealAnchorNormals[j] + m_RealExitNormals[j1] m_RealNormals[j] = m_RealNormals[j] / cabs(m_RealNormals[j]) else ; first point in a sequence; use starting normal for this segment m_RealNormals[j] = m_RealAnchorNormals[j] endif endif j = j + 1 endwhile endfunc ; query: is a point to the left of a line segment? ; positive value = no, negative value = yes, 0 = on line static float func IsLeftLine(complex pz, complex panchor1, complex panchor2) return ( (real(panchor2)  real(panchor1)) * (imag(pz)  imag(panchor1))  \ (real(pz)  real(panchor1)) * (imag(panchor2)  imag(panchor1)) ) endfunc ; query: is a point to the left of a parabolic segment? ; note that if the point is outside the triangle enclosing ; the segment, we treat this as the same as if the point ; is to the left of the lines bounding the parabolic arc ; (we extend the arc by straight lines) static float func IsLeftQuadratic(complex pz, complex panchor1, complex pcontrol, complex panchor2) ; see if it's within the triangle float isleft1 = IsLeftLine(pz, panchor1, panchor2) float isleft2 = IsLeftLine(pz, panchor2, pcontrol) float isleft3 = IsLeftLine(pz, pcontrol, panchor1) if ((isleft1 <= 0 && isleft2 < 0 && isleft3 < 0)  (isleft1 >= 0 && isleft2 > 0 && isleft3 > 0)) ; point is inside the triangle; determine if/where the ray ; intersects the parabola. return IsLeftQuadraticCore(pz, panchor1, pcontrol, panchor2) else float isleft5 = IsLeftLine(pcontrol, panchor1, panchor2) if (isleft5 > 0) if (isleft2 > 0 && isleft3 > 0) return 1.0 else return 1.0 endif elseif (isleft5 < 0) if (isleft2 < 0 && isleft3 < 0) return 1.0 else return 1.0 endif else return isleft1 endif endif endfunc ; query: is a point to the left of a parabolic segment? ; this does not care whether the point is inside the enclosing triangle static float func IsLeftQuadraticCore(complex pz, complex panchor1, complex pcontrol, complex panchor2) float isleft4 = 0 ; parabola flag complex c ; work variables for quadratic segments complex q complex s complex t float d float tx float ty float isy q = 2*conj(panchor2panchor1) / panchor2panchor1 ; rotation and scaling vector c = (panchor1 + panchor2) * 0.5 t = (pz  c) * q ; transform pixel so line segment is rotated to Xaxis and centered at origin s = (pcontrol  c) * q ; transform control point the same way isy = 1/imag(s) ; precalc tx = real(t)  imag(t)*real(s)*isy ; shear ty = imag(t)*isy ; squash d = 0.50.5*sqr(tx) ; height of parabola at this point isleft4 = ty  d ; parabola isleft flag if (imag(s) < 0) isleft4 = isleft4 endif return isleft4 endfunc ; query: is a point to the left of a particular curve segment? ; this determines the type of segment automatically float func IsLeft(complex pz, int psegment) while (psegment >= 0) if (m_RealTypes[psegment] == 0) ; point; if we have a previous segment, use it psegment = psegment  1 elseif (m_RealTypes[psegment] == 1) return IsLeftLine(pz, m_RealAnchors[psegment], m_RealAnchors[psegment+1]) elseif (m_RealTypes[psegment] == 2) return IsLeftQuadratic(pz, m_RealAnchors[psegment], m_RealControls[psegment], m_RealAnchors[psegment+1]) endif endwhile ; no valid segment, just points; answer "no" (not a valid answer) return 0 endfunc ; given a complex number pz, return whether it is inside ; the curve or not; this is the fastest query bool func IsInside(complex pz) int segmentcount = m_RealAnchorCount int j = 0 ; indices for current/next int k = 1 int fullwinding = 0 ; winding numbers int segmentwinding = 0 float isleft1 = 0 ; triangle flags float isleft2 = 0 float isleft3 = 0 float isleft4 = 0 ; parabola flag $ifdef debug int testx = 500 int testy = 480 if (#x == testx && #y == testy) print("IsInside() trace") print("total anchor count: ", m_RealAnchorCount) print("test point: ", testx, " ", testy, " = ", pz) endif $endif while (j < segmentcount) if (m_RealTypes[j] == 0) ; close point; deal with winding numbers if (m_WindingMode == 0) fullwinding = fullwinding + segmentwinding elseif (m_WindingMode == 1) if (segmentwinding != 0) fullwinding = fullwinding + 1 endif else if (segmentwinding != 0) fullwinding = 1 endif endif $ifdef debug if (#x == testx && #y == testy) print("segment ", j, " segmentwinding ", segmentwinding, " fullwinding ", fullwinding) endif $endif segmentwinding = 0 elseif (m_RealTypes[j] == 1) ; line segment; update winding number based solely on line segment ; The winding number method counts all line segments ; that cross the vertical position of the pixel to ; the RIGHT of it. Segments that cross up increment ; the count, segments that cross down decrement it. ; With a closed shape, this will equal zero if the ; point is not inside (regardless of the clockwise/ ; counterclockwise direction of points). Very ; clever algorithm. Google it. if (imag(m_RealAnchors[j]) <= imag(pz)) ; line segment imag <= point imag if (imag(m_RealAnchors[k]) > imag(pz)) ; upward crossing $ifdef debug if (#x == testx && #y == testy) print("segment ", j, " upward crossing") endif $endif if ( (real(m_RealAnchors[k])  real(m_RealAnchors[j])) * (imag(pz)  imag(m_RealAnchors[j]))  \ (real(pz)  real(m_RealAnchors[j])) * (imag(m_RealAnchors[k])  imag(m_RealAnchors[j])) > 0 ) segmentwinding = segmentwinding + 1 $ifdef debug if (#x == testx && #y == testy) print("winding + 1") endif $endif endif endif else if (imag(m_RealAnchors[k]) <= imag(pz)) ; downward crossing $ifdef debug if (#x == testx && #y == testy) print("segment ", j, " downward crossing") endif $endif if ( (real(m_RealAnchors[k])  real(m_RealAnchors[j])) * (imag(pz)  imag(m_RealAnchors[j]))  \ (real(pz)  real(m_RealAnchors[j])) * (imag(m_RealAnchors[k])  imag(m_RealAnchors[j])) < 0 ) segmentwinding = segmentwinding  1 $ifdef debug if (#x == testx && #y == testy) print("winding  1") endif $endif endif endif endif elseif (m_RealTypes[j] == 2) ; quadratic segment; update winding number based on a parabola ; Just so you know, I worked this out myself. No doubt there's ; source code I could have ripped into a formula, but I wanted ; the satisfaction of knowing I could do it. I am quite sure ; this is not the most optimal method, but it does work. Pay ; particular attention to the use of < vs. <= as if you make a ; mistake, you will have horizontal line segment errors in the ; drawn shape. ; This is essentially the same algorithm as arbitrary polygon, ; but extended so that each segment can be a quadratic Bézier ; curve rather than just a straight line. Each curve is ; described by a triangle, and a parabola inscribed within the ; triangle such that two sides of the triangle are tangents ; to the parabola. Points that do not lie within the triangle ; are treated the same as the arbitrary polygon (only the chord ; cutting across the parabola, the third side of the triangle, ; matters) but for points inside the triangle a determination ; must be made as to whether the point is to the left of the ; parabola or not. There are a few edge cases where the ; parabola loops back on itself and the winding number can be ; changed multiple times for each segment. ; three cases: pixel is below triangle containing curve, above it, or between top and bottom of it ; if either of the first two, don't examine this curve further (it is irrelevant to the winding number) if ((imag(pz) >= imag(m_RealAnchors[j]) && \ (imag(pz) < imag(m_RealAnchors[k])  imag(pz) < imag(m_RealControls[j])))  \ (imag(pz) < imag(m_RealAnchors[j]) && \ (imag(pz) >= imag(m_RealAnchors[k])  imag(pz) >= imag(m_RealControls[j])))) $ifdef debug if (#x == testx && #y == testy) print(j, " considered for curve segment") endif $endif ; pixel is between top and bottom of curve ; see if it's within the triangle isleft1 = (real(m_RealAnchors[k])  real(m_RealAnchors[j])) * (imag(pz)  imag(m_RealAnchors[j]))  \ (real(pz)  real(m_RealAnchors[j])) * (imag(m_RealAnchors[k])  imag(m_RealAnchors[j])) isleft2 = (real(m_RealControls[j])  real(m_RealAnchors[k])) * (imag(pz)  imag(m_RealAnchors[k]))  \ (real(pz)  real(m_RealAnchors[k])) * (imag(m_RealControls[j])  imag(m_RealAnchors[k])) isleft3 = (real(m_RealAnchors[j])  real(m_RealControls[j])) * (imag(pz)  imag(m_RealControls[j]))  \ (real(pz)  real(m_RealControls[j])) * (imag(m_RealAnchors[j])  imag(m_RealControls[j])) if ((isleft1 <= 0 && isleft2 < 0 && isleft3 < 0)  (isleft1 >= 0 && isleft2 > 0 && isleft3 > 0)) ; point is inside the triangle; determine if/where the ray ; intersects the parabola. start by normalizing the parabola ; and the ray $ifdef debug if (#x == testx && #y == testy) print(j, " considered inside triangle") endif $endif isleft4 = IsLeftQuadraticCore(pz, m_RealAnchors[j], m_RealControls[j], m_RealAnchors[k]) if (imag(m_RealAnchors[k]) > imag(m_RealAnchors[j])) ; upward crossing if (imag(pz) >= imag(m_RealAnchors[j]) && \ imag(pz) < imag(m_RealAnchors[k])) ; within line segment if (isleft4 > 0) segmentwinding = segmentwinding + 1 ; confirmed upward crossing endif else ; outside line segment if (isleft1 < 0) ; loop back occurs to the left if (isleft4 > 0) segmentwinding = segmentwinding + 1 endif else ; loop back occurs to the right if (isleft4 < 0) segmentwinding = segmentwinding  1 ; loop back; downward crossing endif endif endif else ; downward crossing if (imag(pz) < imag(m_RealAnchors[j]) && \ imag(pz) >= imag(m_RealAnchors[k])) ; within line segment if (isleft4 < 0) segmentwinding = segmentwinding  1 ; confirmed downward crossing endif else ; outside line segment if (isleft1 > 0) ; loop back occurs to the left if (isleft4 < 0) segmentwinding = segmentwinding  1 endif else ; loop back occurs to the right if (isleft4 > 0) segmentwinding = segmentwinding + 1 ; loop back; upward crossing endif endif endif endif ; upward/downward else $ifdef debug if (#x == testx && #y == testy) print(j, " tested against line segment only") endif $endif ; point is outside the triangle; all that matters is its relation to the line segment if (imag(m_RealAnchors[j]) <= imag(pz)) ; line segment imag < point imag if (imag(m_RealAnchors[k]) > imag(pz)) ; upward crossing if ( isleft1 > 0 ) segmentwinding = segmentwinding + 1 endif endif else if (imag(m_RealAnchors[k]) <= imag(pz)) ; downward crossing if ( isleft1 < 0 ) segmentwinding = segmentwinding  1 endif endif endif endif endif endif j = j + 1 k = k + 1 endwhile $ifdef debug if (#x == testx && #y == testy) print("final winding ", fullwinding) endif $endif ; set solid flag with results return (abs(fullwinding) % 2 != 0) endfunc ; given a complex number pz, locate the closest ; point on the curve, the segment number it is on, ; and the distance squared to that point; note ; that distance can never be negative (use IsLeft() ; to determine sign if you need it) complex func ClosestPoint(complex pz, float &psegment, float &psegmentoffset, float &pdistancesquared) int segmentcount = m_RealAnchorCount int j = 0 ; indices for current/next int k = 1 float t float t2 complex c ; third term of quadratic curve function (x and y parts) float m ; coefficients of distancesquared function (a cubic polynomial) float n float r float s int rootcount ; count of roots to cubic equation complex point complex pointmin = m_RealAnchors[0] ; closest point on curve; start with first point float ds = 0 float dsmin = pzm_RealAnchors[0] ; closest distance squared; start with simple distance to first point float segment float segmentoffset float segmentmin = 0 float segmentminoffset = 0 complex vl complex vp float vls float vps $ifdef debug int testx = 700 int testy = 400 if (#x == testx && #y == testy) print("ClosestPoint() trace") print("total anchor count: ", m_RealAnchorCount) print("test point: ", testx, " ", testy, " = ", pz) print("starting dsmin: ", dsmin) endif $endif while (j < segmentcount) if (m_RealTypes[j] == 1) ; compute distance from line segment to point ; start by finding closest point along the line vl = m_RealAnchors[k]  m_RealAnchors[j] ; vector for line vp = pz  m_RealAnchors[j] ; vector from line start to point t = real(vl)*real(vp) + imag(vl)*imag(vp) ; dot product, vl vp cos theta t2 = t / m_RealLengths[j] ; normalize = cos theta * vp/vl $ifdef debug if (#x == testx && #y == testy) print("segment ", j, " type 1 (line) ", m_RealAnchors[j], " ", m_RealAnchors[k]) print("start: ", m_RealIsStartPoint[j], ", end: ", m_RealIsEndPoint[k]) print("length: ", m_RealLengths[j]) print("line vector: ", vl) print("point vector: ", vp) print("dot product: ", t) print("normalized: ", t2) endif $endif ; cap position along line if we're not extending it in either direction if (t2 <= 0 && (m_EndpointExtensionMode == 0  !m_RealIsStartPoint[j])) point = m_RealAnchors[j] ds = pzpoint segment = j elseif (t2 >= 1 && (m_EndpointExtensionMode == 0  !m_RealIsEndPoint[k])) point = m_RealAnchors[k] ds = pzpoint segment = k else point = m_RealAnchors[j] + vl*t2 ds = pzpoint if (t2 < 0  t2 > 1) ; this result is not really "on" the curve; log it as a segment + offset segment = j segmentoffset = t2 else segment = j+t2 segmentoffset = 0 endif endif $ifdef debug if (#x == testx && #y == testy) print("ds: ", ds) print("point: ", point) endif $endif ; update closest point, if this one is closer if (ds < dsmin) dsmin = ds pointmin = point segmentmin = segment segmentminoffset = segmentoffset $ifdef debug if (#x == testx && #y == testy) print("updated: dsmin = ", dsmin, ", pointmin = ", pointmin, ", segmentmin = ", segmentmin, ", segmentminoffset = ", segmentminoffset) endif $endif endif elseif (m_RealTypes[j] == 2) ; compute distance from parametric parabola to point ; we define D(t) to be the distance from P(t) to pz ; and look for minimum values of D(t) by taking its ; derivative D'(t) and solving that; this gives us ; local minima and maxima, so we simply compute the ; distances at these points and choose the lowest ; ; this was a pain for me to work out, mainly because ; of a stupid mistake in my equation scribbling that ; I kept making over and over again... c = m_RealAnchors[j]  pz ; remaining coefficients (depend on point we're finding distance to) m = m_RealA[j] ; get coefficients to cubic equation n = real(m_RealA[j])*real(m_RealB[j]) + imag(m_RealA[j])*imag(m_RealB[j]) r = 2 * ( real(m_RealA[j])*real(c) + imag(m_RealA[j])*imag(c) ) + m_RealB[j] s = real(m_RealB[j])*real(c) + imag(m_RealB[j])*imag(c) ; D'(t) = 4mt^3 + 6nt^2 + 2rt + 2s ; note that only r and s vary with c rootcount = Math.SolveRealCubicPolynomial(2*m, 3*n, r, s, 3, m_Roots) $ifdef debug if (#x == testx && #y == testy) print("segment ", j, " type 2 (quadratic) ", m_RealAnchors[j], " ", m_RealControls[j], " ", m_RealAnchors[k]) print("start: ", m_RealIsStartPoint[j], ", end: ", m_RealIsEndPoint[k]) print("a: ", m_RealA[j]) print("b: ", m_RealB[j]) print("c: ", c) print("m: ", m) print("n: ", n) print("r: ", r) print("s: ", s) print("rootcount: ", rootcount) print("root 0: ", m_Roots.m_Elements[0]) print("root 1: ", m_Roots.m_Elements[1]) print("root 2: ", m_Roots.m_Elements[2]) endif $endif while (rootcount > 0) rootcount = rootcount  1 ; examine this root t = real(m_Roots.m_Elements[rootcount]) ; determine point at t ; we may need to compute the curve at the t value if it's within range ; also, if we are extending beyond endpoints, we may need to recompute ; t as well if (t <= 0) if (m_EndpointExtensionMode == 0  !m_RealIsStartPoint[j]) point = m_RealAnchors[j] t = 0 else vl = m_RealControls[j]  m_RealAnchors[j] ; vector for line vp = pz  m_RealAnchors[j] ; vector from line start to point t2 = real(vl)*real(vp) + imag(vl)*imag(vp) ; dot product, vl vp cos theta vls = vl vps = cabs(vp) t = t2 / vls ; normalize = cos theta point = m_RealAnchors[j] + vl*t t = t * sqrt(vls) $ifdef debug if (#x == testx && #y == testy) print("extended start line") print("line vector: ", vl) print("point vector: ", vp) print("line vector length sqd: ", vls) print("point vector length sqd: ", vps) print("dot product: ", t2) print("normalized: ", t) print("point: ", point) endif $endif endif elseif (t >= 1) if (m_EndpointExtensionMode == 0  !m_RealIsEndPoint[k]) point = m_RealAnchors[k] t = 1 else vl = m_RealAnchors[k]  m_RealControls[j] ; vector for line vp = pz  m_RealControls[j] ; vector from line start to point t2 = real(vl)*real(vp) + imag(vl)*imag(vp) ; dot product, vl vp cos theta vls = vl vps = cabs(vp) t = t2 / vls ; normalize = cos theta point = m_RealControls[j] + vl*t t2 = (t1) * sqrt(vls) $ifdef debug if (#x == testx && #y == testy) print("extended end line") print("line vector: ", vl) print("point vector: ", vp) print("line vector length sqd: ", vls) print("point vector length sqd: ", vps) print("dot product: ", t2) print("normalized: ", t) print("point: ", point) endif $endif endif else point = InterpolateQuadratic(t, m_RealAnchors[j], m_RealControls[j], m_RealAnchors[k]) endif ; update closest point ds = pzpoint $ifdef debug if (#x == testx && #y == testy) print("ds: ", ds) endif $endif if (ds < dsmin) dsmin = ds pointmin = point if (t < 0) segmentmin = j segmentminoffset = t elseif (t > 1) segmentmin = j+1 segmentminoffset = t2 else segmentmin = j+t segmentminoffset = 0 endif endif endwhile endif ; segment type j = j + 1 k = k + 1 endwhile $ifdef debug if (#x == testx && #y == testy) print("result t: ", segmentmin) print("result to: ", segmentminoffset) print("result B(t): ", pointmin) print("result ds: ", dsmin) endif $endif psegment = segmentmin psegmentoffset = segmentminoffset pdistancesquared = dsmin return pointmin endfunc ; Given a complex number pz, determine the closest ; similar curve to it. That is, assume the endpoints ; and control point can slide along their respective ; normals in unison; find the appropriate scaling ; factor that will allow them to create a curve that ; passes through our test point. This is useful for ; creating smooth mappings around curves without the ; discontinuities on the concave side that using ; ClosestPoint() would. complex func ClosestCurve(complex pz, float &psegment, float &pdistancesquared) return 0 endfunc ; given a fractional segment number, determine the ; distance from the curve start to that point ; if ptotal is set, the distance will be cumulative ; from all closed loops, not just from the start of ; the closest closed loop float func DistanceAlongCurve(float psegment, bool ptotal) int segment = floor(psegment) float s = 0 float t = psegment  segment int m int n ; to start with, use all the summed lengths of previous segments s = m_RealSummedLengths[segment] ; now determine a partial length within this segment if (t > 0) if (m_RealTypes[segment] == 1) ; linear segment s = s + t*m_RealLengths[segment] elseif (m_RealTypes[segment] == 2) ; quadratic segment ; determine number of subsegments to use t = t * 256 m = m_RealIndex[segment] n = m + floor(t) t = t  floor(t) while (m < n) s = s + m_RealSubLengths[m] m = m + 1 endwhile if (t > 0) s = s + t*m_RealSubLengths[m] endif endif endif ; if we're not using the total distance, find the loop start ; and subtract all the distance accumulated before it return s endfunc ; given an interpolant and two endpoints, compute a linear curve static complex func InterpolateLinear(float pt, complex panchor1, complex panchor2) return panchor1 + pt * (panchor2panchor1) endfunc ; given an interpolant, two endpoints, and a control point, compute a parabolic curve static complex func InterpolateQuadratic(float pt, complex panchor1, complex pcontrol, complex panchor2) return sqr(1pt)*panchor1 + 2*pt*(1pt)*pcontrol + sqr(pt)*panchor2 endfunc ; given an interpolant, two endpoints, and two control points, compute a cubic curve static complex func InterpolateCubic(float pt, complex panchor1, complex pcontrol1, complex pcontrol2, complex panchor2) return (1pt)^3*panchor1 + 3*pt*(1pt)^2*pcontrol1 + 3*pt^2*(1pt)*pcontrol2 + pt^3*panchor2 endfunc ; public variables ; you can set these yourself, but if you create invalid ; curve data it may not render correctly complex m_Anchors[] complex m_Control1[] complex m_Control2[] float m_Lengths[] int m_Types[] int m_Auto[] protected: int m_WindingMode int m_EndpointExtensionMode int m_AnchorNext int m_AnchorHighest bool m_RealIsStartPoint[] bool m_RealIsEndPoint[] complex m_RealAnchors[] complex m_RealControls[] complex m_RealAnchorNormals[] complex m_RealControlNormals[] complex m_RealExitNormals[] complex m_RealNormals[] float m_RealLengths[] float m_RealSummedLengths[] float m_RealSubLengths[] int m_RealIndex[] int m_RealTypes[] complex m_RealA[] complex m_RealB[] int m_RealAnchorCount ComplexArray m_Roots }
Constructor Summary  

DMJ_PolyCurve()
$define debug 
Method Summary  

complex 
ClosestCurve(complex pz,
float psegment,
float pdistancesquared)
Given a complex number pz, determine the closest similar curve to it. 
complex 
ClosestPoint(complex pz,
float psegment,
float psegmentoffset,
float pdistancesquared)
given a complex number pz, locate the closest point on the curve, the segment number it is on, and the distance squared to that point; note that distance can never be negative (use IsLeft() to determine sign if you need it) 
void 
ComputeNormals()
Compute normals for a curve. 
float 
DistanceAlongCurve(float psegment,
boolean ptotal)
given a fractional segment number, determine the distance from the curve start to that point if ptotal is set, the distance will be cumulative from all closed loops, not just from the start of the closest closed loop 
static complex 
InterpolateCubic(float pt,
complex panchor1,
complex pcontrol1,
complex pcontrol2,
complex panchor2)
given an interpolant, two endpoints, and two control points, compute a cubic curve 
static complex 
InterpolateLinear(float pt,
complex panchor1,
complex panchor2)
given an interpolant and two endpoints, compute a linear curve 
static complex 
InterpolateQuadratic(float pt,
complex panchor1,
complex pcontrol,
complex panchor2)
given an interpolant, two endpoints, and a control point, compute a parabolic curve 
boolean 
IsInside(complex pz)
given a complex number pz, return whether it is inside the curve or not; this is the fastest query 
float 
IsLeft(complex pz,
int psegment)
query: is a point to the left of a particular curve segment? this determines the type of segment automatically 
static float 
IsLeftLine(complex pz,
complex panchor1,
complex panchor2)
query: is a point to the left of a line segment? positive value = no, negative value = yes, 0 = on line 
static float 
IsLeftQuadratic(complex pz,
complex panchor1,
complex pcontrol,
complex panchor2)
query: is a point to the left of a parabolic segment? note that if the point is outside the triangle enclosing the segment, we treat this as the same as if the point is to the left of the lines bounding the parabolic arc (we extend the arc by straight lines) 
static float 
IsLeftQuadraticCore(complex pz,
complex panchor1,
complex pcontrol,
complex panchor2)
query: is a point to the left of a parabolic segment? this does not care whether the point is inside the enclosing triangle 
void 
Rasterize(int pflags)
rasterize a set of curve segments that may contain cubic segments into lines and quadratic segments; also performs autocompute at this time pflags = extra computation flags: 1 = compute segment lengths (needed for ClosestPoint, DistanceAlongCurve), 2 = compute normals (needed for ClosestCurve) 
void 
SetExtensionMode(int pmode)
set the endpoint extension mode pmode = extension mode: 0 = none (cap endpoints) 1 = extend lines 2 = extend curves (not implemented) 
void 
SetSegment(int ppoint,
int ptype,
int pauto,
complex panchor,
complex pcontrol1,
complex pcontrol2)
set parameters for a segment note: do not manually specify a close point; use the autoclose flag instead. 
void 
SetSegmentCount(int ppoints)
set the number of curve segments you must call this prior to setting any curve data 
void 
SetWindingMode(int pmode)
set the winding mode pmode = winding mode: 0 = fully selfintersecting (default) (like "invert overlaps" in DeluxeClipping) 1 = individual loops not selfintersecting, subsequent loops may intersect 2 = entire curve not selfintersecting (like "all inside" in DeluxeClipping) 
Methods inherited from class Object 


Constructor Detail 

public DMJ_PolyCurve()
Method Detail 

public void SetWindingMode(int pmode)
public void SetExtensionMode(int pmode)
public void SetSegmentCount(int ppoints)
public void SetSegment(int ppoint, int ptype, int pauto, complex panchor, complex pcontrol1, complex pcontrol2)
public void Rasterize(int pflags)
public void ComputeNormals()
public static float IsLeftLine(complex pz, complex panchor1, complex panchor2)
public static float IsLeftQuadratic(complex pz, complex panchor1, complex pcontrol, complex panchor2)
public static float IsLeftQuadraticCore(complex pz, complex panchor1, complex pcontrol, complex panchor2)
public float IsLeft(complex pz, int psegment)
public boolean IsInside(complex pz)
public complex ClosestPoint(complex pz, float psegment, float psegmentoffset, float pdistancesquared)
public complex ClosestCurve(complex pz, float psegment, float pdistancesquared)
public float DistanceAlongCurve(float psegment, boolean ptotal)
public static complex InterpolateLinear(float pt, complex panchor1, complex panchor2)
public static complex InterpolateQuadratic(float pt, complex panchor1, complex pcontrol, complex panchor2)
public static complex InterpolateCubic(float pt, complex panchor1, complex pcontrol1, complex pcontrol2, complex panchor2)


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 