diff options
Diffstat (limited to 'doc')
-rw-r--r-- | doc/bibliography.md | 109 | ||||
-rw-r--r-- | doc/releasing.md | 215 |
2 files changed, 324 insertions, 0 deletions
diff --git a/doc/bibliography.md b/doc/bibliography.md new file mode 100644 index 000000000..90a6cef20 --- /dev/null +++ b/doc/bibliography.md @@ -0,0 +1,109 @@ +Here's an effort to document some of the academic work that was +referenced during the implementation of cairo. It is presented in the +context of operations as they would be performed by either +cairo_stroke() or cairo_fill(): + +Given a Bézier path, approximate it with line segments: + + The deCasteljau algorithm + "Outillages methodes calcul", P de Casteljau, technical + report, - Andre Citroen Automobiles SA, Paris, 1959 + + That technical report might be "hard" to find, but fortunately + this algorithm will be described in any reasonable textbook on + computational geometry. Two that have been recommended by + cairo contributors are: + + "Computational Geometry, Algorithms and Applications", M. de + Berg, M. van Kreveld, M. Overmars, M. Schwarzkopf; + Springer-Verlag, ISBN: 3-540-65620-0. + + "Computational Geometry in C (Second Edition)", Joseph + O'Rourke, Cambridge University Press, ISBN 0521640105. + +Then, if stroking, construct a polygonal representation of the pen +approximating a circle (if filling skip three steps): + + "Good approximation of circles by curvature-continuous Bezier + curves", Tor Dokken and Morten Daehlen, Computer Aided + Geometric Design 8 (1990) 22-41. + +Add points to that pen based on the initial/final path faces and take +the convex hull: + + Convex hull algorithm + + [Again, see your favorite computational geometry + textbook. Should cite the name of the algorithm cairo uses + here, if it has a name.] + +Now, "convolve" the "tracing" of the pen with the tracing of the path: + + "A Kinetic Framework for Computational Geometry", Leonidas + J. Guibas, Lyle Ramshaw, and Jorge Stolfi, Proceedings of the + 24th IEEE Annual Symposium on Foundations of Computer Science + (FOCS), November 1983, 100-111. + +The result of the convolution is a polygon that must be filled. A fill +operations begins here. We use a very conventional Bentley-Ottmann +pass for computing the intersections, informed by some hints on robust +implementation courtesy of John Hobby: + + John D. Hobby, Practical Segment Intersection with Finite + Precision Output, Computation Geometry Theory and + Applications, 13(4), 1999. + + http://cm.bell-labs.com/who/hobby/93_2-27.pdf + +Hobby's primary contribution in that paper is his "tolerance square" +algorithm for robustness against edges being "bent" due to restricting +intersection coordinates to the grid available by finite-precision +arithmetic. This is one algorithm we have not implemented yet. + +We use a data-structure called Skiplists in the our implementation +of Bentley-Ottmann: + + W. Pugh, Skip Lists: a Probabilistic Alternative to Balanced Trees, + Communications of the ACM, vol. 33, no. 6, pp.668-676, 1990. + + http://citeseer.ist.psu.edu/pugh90skip.html + +The random number generator used in our skip list implementation is a +very small generator by Hars and Petruska. The generator is based on +an invertable function on Z_{2^32} with full period and is described +in + + Hars L. and Petruska G., + ``Pseudorandom Recursions: Small and Fast Pseurodandom + Number Generators for Embedded Applications'', + Hindawi Publishing Corporation + EURASIP Journal on Embedded Systems + Volume 2007, Article ID 98417, 13 pages + doi:10.1155/2007/98417 + + http://www.hindawi.com/getarticle.aspx?doi=10.1155/2007/98417&e=cta + +From the result of the intersection-finding pass, we are currently +computing a tessellation of trapezoids, (the exact manner is +undergoing some work right now with some important speedup), but we +may want to rasterize directly from those edges at some point. + +Given the set of tessellated trapezoids, we currently execute a +straightforward, (and slow), point-sampled rasterization, (and +currently with a near-pessimal regular 15x17 grid). + +We've now computed a mask which gets fed along with the source and +destination into cairo's fundamental rendering equation. The most +basic form of this equation is: + + destination = (source IN mask) OP destination + +with the restriction that no part of the destination outside the +current clip region is affected. In this equation, IN refers to the +Porter-Duff "in" operation, while OP refers to a any user-selected +Porter-Duff operator: + + T. Porter & T. Duff, Compositing Digital Images Computer + Graphics Volume 18, Number 3 July 1984 pp 253-259 + + http://keithp.com/~keithp/porterduff/p253-porter.pdf diff --git a/doc/releasing.md b/doc/releasing.md new file mode 100644 index 000000000..04c78e20a --- /dev/null +++ b/doc/releasing.md @@ -0,0 +1,215 @@ +Here are the steps to follow to create a new cairo release: + +0) Decide type of release and checkout the appropriate branch. + + The Cairo project makes three types of releases: Development + snapshot releases, stable minor releases, and stable micro (aka + "point") releases. Micro releases should be only bugfixes and + no API additions. If there are API additions consider making a + Minor release. Snapshot releases can be done of the current + development tree between Minor releases, as desired. + + For stable releases (both minor and micro), the work should be + done on the given release branch. E.g. for 1.14.12, check out + the 1.14 branch via "git checkout origin/1.14 -b 1.14". + +1) Ensure that there are no local, uncommitted/unpushed mods. + + You're probably in a good state if both "git diff + HEAD" and "git log master..origin/master" give no output. Also make + sure you have libglib2.0-doc installed (else you'll get + excessive gtk-doc cross reference warnings in the next step). + +2) Verify that the code passes "make distcheck" + + First, make sure you have 'nm' and 'readelf' commands in PATH. + this should be OK with any Linux distro. + + Running "make distcheck" should result in no warnings or + errors and end with a message of the form: + + ============================================= + cairo-X.Y.Z archives ready for distribution: + cairo-X.Y.Z.tar.gz + ============================================= + + (But the tar file isn't actually ready yet, as we still have + some more steps to follow). + + Note that it's allowed (and perhaps recommended) to run the + "make distcheck" step against an all-software X server such as + Xvfb to avoid getting tripped up by any X-server-driver-specific + bugs. See test/README for details + + If you get errors about local PLT entries, you get the list of + cairo entries with the error. For each of these, a call to + slim_hidden_def and slim_hidden_proto is needed in the cairo + implementation in the style of other similar calls. + + In the unfortunate case that you have to push a snapshot out + (note, I said snapshot, not release) without the entire test + suite passing, here's the magic env vars to set when doing + 'make distcheck' and 'make release-publish' that will let you + get away with it. At any cost, never ever release without + (implied) distchecking. Every time we got around it, it turned + out to be a disaster. Anyway, here's the pass code: + + DISPLAY= CAIRO_TEST_TARGET=" " + +3) Decide what the new version number for the release will be. + + Cairo uses even numbers for official releases, and odd numbers + for development snapshots. Thus, for a Minor release it would + be: + + LAST_RELEASE="X.Y.Z" # e.g. 1.12.0 + THIS_RELEASE="X.Y+2.0" # e.g. 1.14.0 + + While for a Micro release the version numbers should be: + + LAST_RELEASE="X.Y.Z" # e.g. 1.14.0 + THIS_RELEASE="X.Y.Z+2" # e.g. 1.14.2 + + Snapshots are similar but have odd minor versions. Also, the + first snapshot release in a new series will be .2 rather than + .0, e.g.: + + LAST_RELEASE="X.Y.Z" # e.g. 1.14.0 + THIS_RELEASE="X.Y+1.0" # e.g. 1.15.2 + + and subsequent snapshots in that series are just normal micro + releases: + + LAST_RELEASE="X.Y.Z" # e.g. 1.15.2 + THIS_RELEASE="X.Y.Z+2" # e.g. 1.15.4 + +4) Fill out an entry in the NEWS file + + Sift through the logs since the last release. This is most + easily done with a command such as: + + git log --stat ${LAST_RELEASE}.. + + Summarize major changes briefly in a style similar to other + entries in NEWS. Take special care to note any additions in + the API. These should be easy to find by noting modifications + to .h files in the log command above. And more specifically, + the following command will show each patch that has changed a + public header file since the given version: + + find src/ -name '*.h' ! -name '*-private.h' \ + ! -name 'cairoint.h' ! -name 'cairo-*features*.h' | \ + xargs git diff ${LAST_RELEASE}.. -- + + Include a link to the incremental ChangeLog for this release, + which we'll be uploading in a later step: + + https://cairographics.org/releases/ChangeLog.cairo-${THIS_RELEASE} + +4) Increment cairo_version_{minor|micro} in src/cairo-version.h: + + If there are backward-incompatible changes in the API, stop + now and don't release. Go back and fix the API instead. Cairo + is intended to remain backwards-compatible as far as API. + + So cairo_version_major will not be incremented unless we come + up with a new versioning scheme to take advantage of it. + + If there are API additions, then increment cairo_version_minor + and reset cairo_version_micro to 0. NOTE: The minor version is + only incremented for releases, not for snapshots. + + Otherwise, (i.e. there are only bug fixes), increment + cairo_version_micro to the next larger (even) number. + +5) For Minor releases, add an index entry to doc/public/cairo-docs.xml + + Towards the end of the file, add a new section for the stable + release. It'll look something like: + + <index id="index-X.Y" role="X.Y"> + <title>Index of new symbols in X.Y</title> + </index> + +6) Commit the changes to NEWS and src/cairo-version.h + + It's especially important to mention the new version number in your + commit log. + +7) Run "make release-publish" which will perform the following steps + for you: + + * Generate ChangeLog files out of git repository + * Check that ChangeLog files were generated properly + * Check that the version number ends with an even micro component + * Check that no release exists with the current version + * Verify that make distcheck completes successfully + * Generate the final tar file + * Generate an sha1sum file + * Sign the sha1sum using your GPG setup (asks for your GPG password) + * scp the three files to appear on https://cairographics.org/releases + * Generate a versioned manual and upload it to appear as both: + https://cairographics.org/manual-${THIS_RELEASE} + https://cairographics.org/manual + * Place local copies of the three files in the releases directory + * Create a LATEST-package-version file (after deleting any old one) + * Tag the entire source tree with a ${THIS_RELEASE} tag, and sign + the tag with your GPG key (asks for your GPG password, and you + may need to set GIT_COMMITTER_NAME and GIT_COMMITTER_EMAIL to match + your public-key's setting or this fails.) + * Provide some text for the release announcement (see below). + If for some reason you lost this message, "make release-publish-message" + prints it for you. + + Upload the incremental ChangeLog generated by the above. For + minor stable releases, this is: + + scp ChangeLog \ + cairographics.org:/srv/cairo.freedesktop.org/www/releases/ChangeLog.cairo-${THIS_RELEASE} + + for micro and snapshot releases, the command is: + + scp ChangeLog.cache-${LAST_RELEASE}.. \ + cairographics.org:/srv/cairo.freedesktop.org/www/releases/ChangeLog.cairo-${THIS_RELEASE} + + To undo a release-publish, before you've sent any emails or + pushed changes to master, delete the locally created tag (git + tag -d ${THIS_RELEASE}); then log into the webserver, repoint + the manual and LATEST-cairo-${THIS_RELEASE} symlinks to the + previous versions, remove manual-${THIS_RELEASE} and + release/cairo-${THIS_RELEASE}. + +8) Push the new tag out to the central tree with a command like: + + git push origin master ${THIS_RELEASE} + +9) Update master (or the stable branch) version number. + + For Micro releases (X.Y.Z+2), increment cairo_version_micro to + the next larger (odd) number in src/cairo-version.h, commit, and + push. + + DEVEL_VERSION="X.Y.Z+1" # e.g. 1.15.10 -> 1.15.11 + + For Minor releases (X.Y.0), increment cairo_version_minor to the + next larger (odd) number, and set cairo_version_micro to 1. Then + commit and push. + + DEVEL_VERSION="X.Y.Z+1" # e.g. 1.16.0 -> 1.17.1 + + git commit src/cairo-version.h -m "Bump version for ${DEVEL_VERSION}" + +10) Send out an announcement message. + + Send a message to cairo-announce@cairographics.org and CC + cairo@cairographics.org, gnome-announce-list@gnome.org and + ftp-release@lists.freedesktop.org (pr@lwn.net as well for major + releases) to announce the new release using the text provided from + "make release-publish", adding the excerpt from NEWS and + the shortlog of all changes since last release, generated by: + + git shortlog ${LAST_RELEASE}... + +11) Add the announcement to the website as a new entry in the news/ + dir. It will automatically get indexed onto the homepage when the + site refreshes. |