Greiner-Hormann clipping algorithm for degenerate cases and curves

November 2nd, 2015
by admin

Today’s 200th aniversary of Goerge Boole‘s birth, so this is a post about polygon clipping – boolean operations on polygons.
Most popular (and quite simple and fast) algorithm for this task is Greiner-Hormann. Unfortunately, as wikipedia says, it has 1 big drawback – cannot handle shapes with common edges. So XOR boolean operation won’t work. And we won’t be able to clip following “rectangles” (AND operation in this example):

[[]][[]]

Original Greiner-Hormann consists of 3 phases:

  1. Compute intersections and add them to polygon
  2. Marking intersections as “entering” or “exiting”
  3. Final traversal and generating new polygons

The improved algorithm involves just adding additional phase of algorithm, just after the 1st one:
1.5 disabling “bad” intersections

Of course all intersections shouldn’t double themselves, so before adding intersections to polygon you should remove duplicate intersections. Doubling intersections are esp. possible when computing bezier intersections using traditional bezier clipping or computing intersections via approximation of bezier curves with polygons – the approximation leads to finding too many intersections for almost collinear curves.

Disabling bad intersections should mark intersections as “bad” and then they should be ignored in further steps of an algorithm.

The following pseudocode explains disabling bad intersections algorithm:

  1. Do this for each intersection of current polygon in intersections:
    compute 2 boolean properties in current intersection: previousInside and nextInside. These properties determine whether the edge that is before the intersection point and the edge that is after the intersection point lies inside the second polygon (not current). In practice, we will be checking whether the point in the middle of the next and previous edge is inside second polygon, using some PIP-check algorithm, for example winding or odd-even algorithm.Important remark: if previous or next edge is collinear with corresponding edge in the second polygon, we mark it always as inside, or always as outside. (we could also mark it as “collinear” and then during second phase use some advanced heuristic how to treat collinear edges, but I won’t cover that method in this article, maybe later…).
  2. Now traverse polygon. If we meet an intersection, and when intersection.nextInside == intersection.prevInside then disable this intersection

Remark: To apply this algorithm to curves, we can treat each curve segment as polygon segment. We just have to change the collinearity check to support curves, and the PIP check algorithm should be changed accordingly (e.g. check insideness through bezier subdivision).

As you can see, this simple change repairs Greiner-Hormann and there’s no need for perturbing vertices, as suggested in the original paper and on Wikipedia. Perturbing could generate random results in some cases.

Tags: , , , ,
Posted in Uncategorized | Comments (0)

JavaScript engine in JavaScript

November 2nd, 2015
by admin

Very useless post.

I’ve ported duktape javascript engine to javascript (using emscripten). No js interface for it, so you gotta call methods like this:

var result = Module.ccall('functionName' /*name of C function*/,
'number|string' /*return type*/,
['number|string',...]/*arg types*/, [666] /*args*/);

The API documentation is available at duktype site.

DEMO

source: dux.js

This can be used when eval is forbidden, or when we want to analyse js execution more closely.

Tags: , , ,
Posted in Uncategorized | Comments (0)

How to get the week number in a month

April 9th, 2015
by admin

Recently I wanted to display a number of week in a month. At first I wanted to get the formula from google instead of thinking, but there was no such formula. Also, I’ve found a lengthy discussion and only some indian guy gave the formula (which was incorrect of course:D)

Suppose that November the 1st is Thursday. Then for example, November 2nd is a 1st week of November, November 16th is a 3rd week, 30th is 5th week (basing on a fact that Monday starts the week)
Here’s the table that illustrates it:

​How to get the week number?

~~( ( m - w + 6 ) / 7 )

where m is an integer, a month day, 0 or 1-based
w is an integer, a week day, 0 or 1-based (e.g. Monday = 1, Thursday = 4)

Double bitwise negation is just a conversion to integer, you can use floor if you don’t care about speed (I guess that’s the case in times of virtual machine driven emulators and regex-based [greets angular;) ] js frameworks).

I’ll rebelliously leave it without a proof.

Posted in flash experiments | Comments (0)

Flower fractals super squished edition

March 9th, 2015
by admin

Recently I stumbled upon a challenge on challengepost.com – “20 lines of JavaScript”. The goal was to write a 20 line JS code that does something that can make the challenge judges vote for you. I thought the best idea would be to treat this challenge like a good ol’ demoscene compo. I’ve already had a good effect – the flower fractals. Unfortunately, after porting it to JavaScript it was 11 KBytes :( and 383 lines of code, not always shorter than the required 80 chars (or maybe even more, but I don’t remember where I put the first version). I used PIXI, great 2D javascript library because it uses several enhancements for JS canvas (it also supports WebGL, but WebGL isn’t really a vector-like drawing thing, the lines are aliased and poor quality, to obtain better quality I’d need to use textures and stuff, I thought it would be too complicated for 20 lines of code).

OK, so I’ve got 383 lines and 11 kilobytes. As we all know, 20 lines of 80 char code is 1600 bytes, so there’s way to go… I checked with google closure compiler, how I could squish that – after compressing, it was about 5 kilos. Still too much. After hours of merging functions, deleting smooth line bezier-based rendering, reusing some vars, it went down to about 3 kilos.

I started to think that its impossible to do, unless some miracle happens.

Then I stumbled upon this great method of utilising somehow buggy behaviour of browsers – treating PNG files like HTML, when compressed PNG data resembles HTML data. After changing the JS to one big eval(…) function and compressing it to PNG I went down to 1600 bytes. Well, exactly 1595. Changing some things inside eval and making the code larger allowed PNG to compress it enough. So there’s this curiosity – PNG JavaScript: 1600BYTES

This was of course no-go, because it wasn’t really javascript – it was png, and I it would be really really hard to intoduce line breaks inside zipped binary data. Also, it’s very ugly, you can see some errors appearing when running this code – some PNG IHDR data is displayed for a short period of time. I had to come up with something else. But how to squish the code better than the zip algorithm itself?

Then I had a moment of enlightning – it’s 20 lines of 80 characters challenge, not 1600 bytes challenge. How about UTF-16? I could write 2 bytes inside 1 UTF16 character.

It worked! Excited, I searched on google if anyone else did it – of course someone already came up with that idea ;/ And the idea was better because the decoder is like:
eval(unescape(escape('SOME STRING').replace(/uD./g,'')))

And mine was much longer and 2 lines:
function(s){A=[];for(i=0;i<s.length;i++){c=s.charCodeAt(i);A.push(c&255);
c>>8?A.push(c>>8):c;}return String.fromCharCode.apply(String,A)}("SOME STRING");

But my method used a bit different technique, so I could use normal letters and fit some ASCII art inside the code, not only some strange chinese letters.

OK, so after compiling with google closure, making big eval and changing to UTF-16, the code looks like this:

Zrzut ekranu 2015-03-09 02.21.38

And can be seen on the challengepost’s winners’ ( ͡° ͜ʖ ͡°)  gallery:
http://challengepost.com/software/20-lines-of-green

or here
or JSFiddle: http://jsfiddle.net/to267224/tbgad7uz/

ps. I will enhance this post later maybe, to provide some missing info on technical things and add some images, cause there’s too much unformatted text ; )

Tags: , , , ,
Posted in flash experiments | Comments (0)

Automatic drawing recognition in javascript

April 1st, 2014
by admin

When working on the android recognition app, I’ve also made version in JavaScript. Its around 60 megabytes site, so its quite unusable. And it loads so long that you can start doubting that it’s going to load at all.
To see it, better turn off AdBlock (it has a bug which prevents some sources from loading) and use chrome.
To make it harder and less usable (and lighter for my dropbox), to see this site you must first go to my experimental domain timmott-twerten.com, click and type “drawings”:
. This isn’t user friendly at all, so if you type something else in the box, or delete a letter, then the site will close itself and you will loose time that you wasted waiting for it.

It could be much more compact in flash/actionscript, but I wanted to check how fast is JS. It appears to be pretty fast ; )

The “save” button

… uploads your creation to imgur.

It is hosted on my dropbox, so when the transfer is exhausted, it won’t shutdown my blog ; )

ps. the javascript isn’t compressed or uglified, so you can see how it is all made.

Tags: ,
Posted in flash experiments | Comments (0)

ActionScript PSD Encoder with layer support and PSD specification explained

March 9th, 2014
by admin

[updated version: 1.1 at the end of this post]
At the end of this article you can find an as3 PSD document encoder that turns array of bitmaps into a layered photoshop document file.

I’ve decided to write this encoder because of several reasons:

  1. there is an actionScript PSD parser on the internet, but there are no encoders
  2. PSD encoders are parts of bigger projects and aren’t necessary fully compatible with PhotoShop
  3. I wanted to have a possibility of creation layered image files
  4. there are several formats that supports layers, but PSD is the most standard, supported by many apps
  5. Adobe specification of photoshop file format lacks some information that is necessary to create an encoder quickly and with no wandering in the dark

The encoder works like that:
//create two bitmaps, first will be a bottom layer, red rectangle, second will be a green rectangle in the center of the bottom layer
var bitmap1:Bitmap = new Bitmap( new BitmapData( 300, 300, true, 0xff0000 ) );
var bitmap2:Bitmap = new Bitmap( new BitmapData( 200, 200, true, 0x00ff00 ) );
bitmap2.x = 50; bitmap2.y = 50;
//encode 2 bitmaps into a PSD file
var byteArray:ByteArray = PSDEncoder.encodePSD( Vector.[ bitmap1 , bitmap2 ] );
// save the byteArray as a file
new FileReference().save( byteArray , "test_image.psd" );

This is the demo. The demo is very trivial, its just the code above in a button event handler, you just save the file after clicking, but I like demos, so here it is:



About the PSD specification pitfalls.

The specification can be found at: http://www.adobe.com/devnet-apps/photoshop/fileformatashtml/#50577409_pgfId-1030196
I will discuss things that I stumbled upon when writing the encoder or things that appears to be unclear. I will focus on most common features of PSD.

File header section
The PSD file header is pretty straightforward. The “bitmap” color mode of file is special mode that is used to draw vector graphics, so better use CMYK or RGB

Color Mode Data Section
We will skip this one…

Image Resources Section
First field – “Length of image resource section.” – it is unclear whether this length should include 4 bytes of this field. Answer: NO it shouldn’t.

The thumbnail (image resource ID 0x040C)

  • Supported formats for thumbnails, according to specification, are kJpegRGB and kRawRGB. The Raw RGB format however, doesn’t work on PhotoShop 7 (version that I’ve tested).
  • Pay attention to data in 12th byte – widthbytes. It must be computed using the formula in the specification:
    This is more fancy notation: widthbytes = width * 24 + 31 >> 5 << 2
    This basically adds 1 to 3 bytes to width in bytes of the image, to make it divisible by 4.
  • Also - pay attention to the length of JFIF data (what is JFIF? Most today's .JPG images are contained in a JFIF container, if you paste JFIF data in a file and add .JPG extension, it will be an ordinary JPG image file). If the length is uneven, you must add 1 byte to the end of JFIF data (it is mentioned under Image Resources Section description). Most photoshop documents has thumbnails with size limited to 127x127 rectangle.

Layer and mask information section
First field - "Length of the layer and mask information section" - this length, just like in Image Resources section, shouldn't include length of itself.

Then we have "Layer info" section.
"Length of the layers info section, rounded up to a multiple of 2." - this also shouldn't include the length of itself. But what about "rounded up to a multiple of 2"? This means that in case if the length of layer info is odd, you should not only add 1 to the length, you must also add this one byte to the end of the "channel image data" section. The very end.

Now "Layer records".
Third field is the "Channel information". It contains channel IDs and lengths of channel data. Length of channel data must include also 2 bytes that tells what kind of compression it is.
The RGB channels in Photoshop are in the following order: R,G,B,A. Every channel data entry contains type of compression and then colors. Photoshop 7 saves PSD in RLE format, but also reads raw layers. Channel image data entry, when compressed using RLE, looks like this (this isn't very straightforward when looking at the specification):
[1st layer 1st channel compression type]
[1st layer 1st channel RLE lengths]
[1st layer 1st channel data]
[1st layer 2nd channel compression type]
[1st layer 2nd channel RLE lengths]
[1st layer 2nd channel data]
...
[2nd layer 1st channel compression type]
[2nd layer 1st channel RLE lengths]
[2nd layer 1st channel data]
...

In case of raw data, we have a description: If the layer's size, and therefore the data, is odd, a pad byte will be inserted at the end of the row. - this is actually not true, we only insert this one byte that I've mentioned earlier (in case of data oddity).

Layer records field "Flags", there is a description:
"bit 1 = visible" - this actually means, that when bit 1 equals 1 - the layer IS NOT visible.

Layer records field "Length of the extra data field (=the total length of the next five fields)" - but there are 3 fields in the specification. So where is the rest? By looking at the PSD document, I can tell that there's some data after the "Layer name", the last documented field. So probably this isn't a mistake in the specification, but these fields aren't documented. So this is a mystery. Stripping them (and of course correcting all the fields that says "length of...") didn't corrupt the PSD file.

Last field - "layer name: Pascal string (...)" - funny thing that I didn't know what's that "Pascal string". Of course I remember strings in Turbo Pascal, they could be up to 255 chars long. Google didn't tell anything valuable about "Pascal string", funny thing that this Specification appeared in the beginning of search results. So what is that "Pascal string"? It is a string with an integer at the beginning, telling how long this string is (in contrary to c-string when we have null at the end).

Image Data section
Image data section contains all the pixel colors. It is a bit different from "channel image data" section, esp. when yo use RLE encoding. This is the description from the specification: "RLE compressed the image data starts with the byte counts for all the scan lines (rows * channels)"
This is the scheme of data layout in image data section:
[1st channel RLE lengths]
[2nd channel RLE lengths]
...
[1st channel data][2nd channel data]
...


** By following the rules below, you will create identical data in PSD to Photoshop's output (this way there's a greater chance that the generated documents will be opened in all Photoshop versions). **
About RLE compression
The description in the specification says, that when parsing PSD documents, we must compress using RLE (packbits algorithm) every scanline separately. Actually, Photoshop does this in 128 byte chunks.
That is:
y := 0
1: take the scanline at y
use packbits on all 128 byte chunks of the scanline bytes
- if there are less than 128 bytes left, then take the rest
y := y + 1
go to 1.

Also, if you take a look at the MacPaint's packbits algorithm: http://telegraphics.com.au/svn/macpaintformat/trunk/packbits.c
These lines (written in C):
if(run <= (dataend-3) && run[1] == run[0] && run[2] == run[0]){ for( p = run+3 ; p < (run+maxrun) && *p == run[0] ; ) in Photoshop are changed to:
if(run <= (dataend-2) && run[1] == run[0] ){ for( p = run+2 ; p < (run+maxrun) && *p == run[0] ; ) ... so that we are starting a RLE run in case we meet 2, not 3 similar bytes.

About colors in image data section.
Colors in image data section are premultiplied by alpha with white. Regardless of the "background" entry on "Image resources" section (personally I don't know what this entry does anyway). Alpha channel stays intact.
The premultiplication is done using following formula:
R = int( ( A * R + (255-A) * 255 ) / 255 + 0.5 )
G = int( ( A * G + (255-A) * 255 ) / 255 + 0.5 )
B = int( ( A * B + (255-A) * 255 ) / 255 + 0.5 )
(A = alpha channel byte, R = red byte, G = green byte, B = blue byte)


And these are the sources:
v. 1.0 PSD Encoder class

update 1.1:
v. 1.1 PSD Encoder class with 2 utility methods
as you can see in the comments section, a generous contributor (Tom Keen) made 2 routines that simplifies the usage of a class. Class works as previously, but has added 2 utility functions.
remark: DisplayObjects supplied to the method "exportDisplayObjects" must have a parent


Tags: , , ,
Posted in flash experiments | Comments (4)