ssdddasas

Eguru2007121614355056.zip

• Download demo project - 7.44 Kb
• Download source - 15.1 Kb

Introduction

This article describes how to detect the collision between two moving (2D) polygons. It's not the first tutorial on the topic, however, the tutorials on the net tend to be a bit too complex for a relatively simple problem. The source codes I could find also had too many abbreviations that I don't get, or were crippled with C optimizations. So here, I'll try to keep it as simple as possible. In any case, it should be possible to include the functions presented here to your C projects quite straightforwardly. The technique can be used to detect collisions between sprites as an alternative to pixel-perfect collisions which are usually too slow.

Background

To detect if two polygons are intersecting, we use the Separating Axis Theorem. The idea is to find a line that separates both polygons - if such a line exists, the polygons are not intersecting (Fig. 1). The implementation of this theorem is relatively simple, and could be summed up in this pseudo code:

• For each edge of both polygons:
  • Find the axis perpendicular to the current edge.
  • Project both polygons on that axis.
  • If these projections don't overlap, the polygons don't intersect (exit the loop).

This can be easily extended to deal with moving polygons by adding one additional step. After having checked that the current projections do not overlap, project the relative velocity of the polygons on the axis. Extend the projection of the first polygon by adding to it the velocity projection (Fig. 2). This will give you the interval spanned by the polygon over the duration of the motion. From there, you can use the technique used for static polygons: if the projections of polygons A and B don't overlap, the polygons won't collide. (NB: However, remember that if the intervals do overlap, it doesn't necessarily mean that the polygons will collide. We need to do the test for all the edges before knowing that.)

Once we have found that the polygons are going to collide, we calculate the translation needed to push the polygons apart. The axis on which the projection overlapping is minimum will be the one on which the collision will take place. We will push the first polygon along this axis. Then, the amount of translation will simply be the amount of overlapping on this axis (Fig. 3).

That is it! Now, each time a collision occurs, the first polygon will nicely slide along the surface of the other polygon.

Figure 1: Projections of the polygons onto an axis.

Figure 2: Projections for moving polygons.

Figure 3: Find the minimum interval overlapping, then calculate the translation required to push the polygons apart.

Using the code

The PolygonCollision() function does all of the above, and returns a PolygonCollisionResult structure containing all the necessary information to handle the collision:

// Structure that stores the results of the PolygonCollision function
public struct PolygonCollisionResult {
    // Are the polygons going to intersect forward in time?
    public bool WillIntersect;
    // Are the polygons currently intersecting?
    public bool Intersect;
    // The translation to apply to the first polygon to push the polygons apart.
    public Vector MinimumTranslationVector;
}

Two helper functions are used by the PolygonCollision function. The first one is used to project a polygon onto an axis:

// Calculate the projection of a polygon on an axis
// and returns it as a [min, max] interval
public void ProjectPolygon(Vector axis, Polygon polygon, 
                           ref float min, ref float max) {
    // To project a point on an axis use the dot product
    float dotProduct = axis.DotProduct(polygon.Points[0]);
    min = dotProduct;
    max = dotProduct;
    for (int i = 0; i < polygon.Points.Count; i++) {
        dotProduct = polygon.Points[i].DotProduct(axis);
        if (d < min) {
            min = dotProduct;
        } else {
            if (dotProduct> max) {
                max = dotProduct;
            }
        }
    }
}

The second one returns the signed distance between two given projections:

// Calculate the distance between [minA, maxA] and [minB, maxB]
// The distance will be negative if the intervals overlap
public float IntervalDistance(float minA, float maxA, float minB, float maxB) {
    if (minA < minB) {
        return minB - maxA;
    } else {
        return minA - maxB;
    }
}

Finally, here is the main function:

Collapse

// Check if polygon A is going to collide with polygon B.
// The last parameter is the *relative* velocity 
// of the polygons (i.e. velocityA - velocityB)
public PolygonCollisionResult PolygonCollision(Polygon polygonA, 
                              Polygon polygonB, Vector velocity) {
    PolygonCollisionResult result = new PolygonCollisionResult();
    result.Intersect = true;
    result.WillIntersect = true;

    int edgeCountA = polygonA.Edges.Count;
    int edgeCountB = polygonB.Edges.Count;
    float minIntervalDistance = float.PositiveInfinity;
    Vector translationAxis = new Vector();
    Vector edge;

    // Loop through all the edges of both polygons
    for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
        if (edgeIndex < edgeCountA) {
            edge = polygonA.Edges[edgeIndex];
        } else {
            edge = polygonB.Edges[edgeIndex - edgeCountA];
        }

        // ===== 1. Find if the polygons are currently intersecting =====

        // Find the axis perpendicular to the current edge
        Vector axis = new Vector(-edge.Y, edge.X);
        axis.Normalize();

        // Find the projection of the polygon on the current axis
        float minA = 0; float minB = 0; float maxA = 0; float maxB = 0;
        ProjectPolygon(axis, polygonA, ref minA, ref maxA);
        ProjectPolygon(axis, polygonB, ref minB, ref maxB);

        // Check if the polygon projections are currentlty intersecting
        if (IntervalDistance(minA, maxA, minB, maxB) > 0)\
            result.Intersect = false;

        // ===== 2. Now find if the polygons *will* intersect =====

        // Project the velocity on the current axis
        float velocityProjection = axis.DotProduct(velocity);

        // Get the projection of polygon A during the movement
        if (velocityProjection < 0) {
            minA += velocityProjection;
        } else {
            maxA += velocityProjection;
        }

        // Do the same test as above for the new projection
        float intervalDistance = IntervalDistance(minA, maxA, minB, maxB);
        if (intervalDistance > 0) result.WillIntersect = false;

        // If the polygons are not intersecting and won't intersect, exit the loop
        if (!result.Intersect && !result.WillIntersect) break;

        // Check if the current interval distance is the minimum one. If so store
        // the interval distance and the current distance.
        // This will be used to calculate the minimum translation vector
        intervalDistance = Math.Abs(intervalDistance);
        if (intervalDistance < minIntervalDistance) {
            minIntervalDistance = intervalDistance;
            translationAxis = axis;

            Vector d = polygonA.Center - polygonB.Center;
            if (d.DotProduct(translationAxis) < 0)
                translationAxis = -translationAxis;
        }
    }

    // The minimum translation vector
    // can be used to push the polygons appart.
    if (result.WillIntersect)
        result.MinimumTranslationVector = 
               translationAxis * minIntervalDistance;
    
    return result;
}

The function can be used this way:

Vector polygonATranslation = new Vector();

PolygonCollisionResult r = PolygonCollision(polygonA, polygonB, velocity);

if (r.WillIntersect) {
  // Move the polygon by its velocity, then move
  // the polygons appart using the Minimum Translation Vector
  polygonATranslation = velocity + r.MinimumTranslationVector;
} else {
  // Just move the polygon by its velocity
  polygonATranslation = velocity;
}

polygonA.Offset(polygonATranslation);

Eguru2007121614403756.zip

• Download binaries - 12.3 Kb
• Download source - 14.6 Kb

Introduction

Every week I take dozens of pictures during the soccer games of Kevin, my 7 year old son. Most of these pictures are placed on a web site created for his team. And every week I find myself performing the ever recurring task of resizing the images (mostly 3072 x 2048) to something more friendly (e.g.: 768 x 512). Why? Just for those less fortunate that have no ADSL or so.

Of course, every repeating task is prone to be automated, and a first application was born to resize the pictures according to my wishes. To cope with different source and target paths, as well as different ways of resizing, the application needed a user interface. Working on the application and its (simple, yet effective) user interface, generalizing the use of the application is evident. The next step then is to share it with all of you and hope you find the application or some code snippet useful.

Using Image Converter

Just download the zipped executable, unzip it, and open it. After you have opened ImageConverter, you can open the image files that you want to convert by pressing the Open... button. The target path for the converted images is automatically set to the source path, if not set already. By pressing the Browse... button, you can select an alternative path for the converted images.

Before you start the conversion process, you can define the image format after conversion, you can define how the images should be named, and you can define the required image size.

For naming the target images, you can use the original name, and the corresponding extension for the target image format is added. If a file with the resulting name already exists, it will be overwritten. Another option is to use a prefix defined by you. Each target image file will get a unique name based on this prefix and a sequence number.

The target size can be a specified size, which means that the original image will be stretched. If you are just interested in obtaining images for which the largest of width or height is less than or equal to the specified maximum, the image will be scaled if either width or height is larger than the specified maximum. The third option is to scale each image by the specified percentage.

Using the code

The main code for the application is in FormImageConverter.cs whilst the code for the Thumbnail control I use is in Thumbnail.cs.

Selecting Images

The images to be converted are selected by invoking the ShowDialog method of a standard OpenFileDialog instance. The selected image files are processed by the DisplayThumbnails method, which disposes off any Thumbnail control still present. Then for each image file, a Thumbnail control is created and added to panelThumbnails.Controls. Note that if the file to be loaded is not a (valid) image file, an OutOfMemoryException is thrown and the Thumbnail control will not be created.

Conversion Process Thread

Because I want some progress information displayed during the conversion process, the conversion process takes place in another thread. The thread is created and started from the event handler for the Convert button.

private void buttonConvert_Click(object sender, System.EventArgs e)
{
    this.Cursor = Cursors.WaitCursor;
    _convertThread = new Thread(new ThreadStart(ConvertImageFiles));
    _convertThread.Start();
}

The ConvertImageFiles method takes care of determining the extension and image format for the target image, as well as the name for the image file. Using this information and knowing the size for the target image, the original image as represented by the Thumbnail control can be converted.

Collapse

private void ConvertImageFiles()
{
    this.Cursor = Cursors.WaitCursor;
    _converting = true;
    this.EnableControls();
    try
    {
        ...
        // determine the target size
        System.Drawing.Size targetSize = this.DetermineTargetSize(thumbnail.Image);
        System.Drawing.Image targetImage = null; 

        try
        {
            // the new image is created and written based on
            // the original, the target size and the desired image format
            targetImage = new Bitmap(thumbnail.Image, targetSize);
            targetImage.Save(targetFileName, targetImageFormat); 
            // invoke the delegate for updating progress information
            this.Invoke(_imageInfoDelegate, 
                 new object[] { thumbnail, targetFileName, targetSize });
            targetImage.Dispose();
        }
        catch (System.Threading.ThreadAbortException e)
        {
            throw e;
        }
        catch {}
        ...
    }
    catch {}
    finally
    {
        this.Cursor = Cursors.Default;
        _converting = false;
        this.EnableControls();
    }
}

To prevent the user from changing the settings during the conversion process, the controls on the main form are disabled at the start, and the Close button becomes a Cancel button. Pressing the Cancel button causes the thread to be aborted by calling _convertThread.Abort method, which causes a System.Threading.ThreadAbortException to be thrown. The exception is caught and re-thrown until the outer try-catch is reached, and the controls can be enabled again.

To update the progress information during the conversion process, a delegate is executed using the Invoke method on the main form. The progress information uses the thumbnail, the target file name, and the target size. These objects are put in an object array, which holds the arguments for the DisplayImageInfo method to be called.

// the delegate
private delegate void ImageInfoDelegate(Thumbnail thumbnail, 
              string targetFile, System.Drawing.Size toSize);

private ImageInfoDelegate _imageInfoDelegate = null;

_imageInfoDelegate = new ImageInfoDelegate(DisplayImageInfo);

// invoke the delegate for updating progress information
this.Invoke(_imageInfoDelegate, new object[] { thumbnail, 
                                 targetFileName, targetSize });

Enabling/Disabling Controls

As noted, the various controls on the main form are disabled during the conversion process and the Close button changed into a Cancel button. Also, if no images have been selected or no target path defined, the Convert button is disabled. This is implemented in the EnableControls method, which has to be called every time the conditions queried in the method have changed.

private void EnableControls()
{
    this.buttonConvert.Enabled = 
        !_converting &&
        this.panelThumbnails.Controls.Count > 0 &&
        this.labelTargetPathValue.Text.Trim() != "";
    this.buttonBrowseTargetPath.Enabled = !_converting;
    this.buttonOpen.Enabled = !_converting;
    this.groupBoxOnConvert.Enabled = !_converting;
    this.groupBoxTargetSize.Enabled = !_converting;
    this.comboBoxTargetFormat.Enabled = !_converting;
    this.buttonClose.Text = _converting ? "Cancel" : "Close";
}

Thumbnail Control

The Thumbnail control is a UserControl on which a Panel is placed that contains a PictureBox and two Labels. The PictureBox holds the thumbnail image, the file name Label, and the original image size Label. The border around the control is obtained by setting the control's DockPadding to 2 for all sides. The thin line between the PictureBox and the file name Label is the BackColor of the underlying Panel 'shining' through. This is accomplished by setting both Labels to dock on the bottom and by giving the PictureBox the size of the remaining space with the height set to just one pixel less.

The main task of the Thumbnail control is to show a thumbnail for each loaded image file and to present easy access to the corresponding image and its file path. The file path is supplied to the constructor, and the file is loaded using the FromFile method.

public Thumbnail(string filePath)
{
    InitializeComponent();
    _filePath = filePath;
    try
    {
        _image = System.Drawing.Image.FromFile(_filePath);
    }
    catch (System.OutOfMemoryException e)
    {
        // file does not represent a valid image
        throw e;
    }

    ...

Loading a file that does not represent a (recognizable) image causes an OutOfMemoryException, so the exception is caught and thrown again to inform the code constructing the thumbnail.

If it is loadable, the size for the thumbnail image is calculated and the visual feedback is set.

    ...

    int max = Math.Min(this.pictureBox.Width, this.pictureBox.Height);
    int width = _image.Width;
    int height = _image.Height;
    // determine the size for the thumbnail image
    if (_image.Width > max || _image.Height > max)
    {
        if (_image.Width > _image.Height)
        {
            width = max;
            height = (int) (_image.Height * max / _image.Width);
        }
        else
        {
            width = (int) (_image.Width * max / _image.Height);
            height = max;
        }
    }
    // set feedback information
    this.pictureBox.Image = new Bitmap(_image, width, height);
    this.labelFileName.Text = Path.GetFileName(_filePath);
    this.labelImageSize.Text = string.Format("{0} x {1}", 
                       _image.Size.Width, _image.Size.Height);
}

Eguru2007121614445556.zip

• Download VB.NET source files - 276 Kb
• Download C source files - 275 Kb

Introduction

This article presents VB.NET code to create thumbnail images from a directory of Adobe Acrobat PDF documents.

Often when looking for documents it is much easier to find what you want visually, for example seeing the cover of a document.

The application was written for a website that I was developing that needed to display links to PDF documents. Instead of just showing a little PDF icon next to each document we wanted to display the front page of the actual document.

As shown below, this gives the listings better aesthetics and also enables the users to find documents quicker if they recognise it.

Note: please ignore the strange text, lorem ipsum is simply dummy text for this example

Hopefully people will agree that having the actual front cover displayed next to the hyperlink works better than the generic PDF icon.

Background

The web site was a Content Management System (CMS) so new PDF documents were uploaded to the site by the users. We then had this application scheduled as a batch service to run every 5 minutes and check for new files.

In the backend system the documents have metadata stored in a SQL Server 2000 database. We would then write a flag to say the thumbnail had been created and when we generated the HTML content for the page request in ASP/ASP.NET we would return the appropriate IMG tag and source as appropriate.

Using the Acrobat SDK also meant we could programmically read the PDF metadata and retrieve the number of pages in the document, which could then be displayed as well. Although the end users could have entered that information it meant less work for them and a better overall impression of the web site. Another advantage was that many users relied on the number of pages to determine how large the document was rather than the more technical Kb/Mb value.

Approach

To generate the thumbnail image for each document I used the Adobe Acrobat 5.0 SDK and the Microsoft .NET 1.1 Framework.

Note: do not confuse the thumbnails that are part of a PDF document with the .png files this application generates.

The Acrobat SDK combined with the full version of Adobe Acrobat (sadly the free reader does not expose the COM interfaces) exposes a COM library of objects that can be used to manipulate and access PDF information.

So using these COM objects via COM Interop, we can load the PDF document, get the first page and render that page to the clipboard. Then using the .NET Framework we can copy this to a bitmap, scale and combine that image and then save the result as a .gif or .png file.

At first I just saved the scaled down image, but then decided to “fancy” up the thumbnail with a drop-shadow and folded corner. To achieve this effect I created a transparent .gif, called pdftemplate_portrait.gif, using Macromedia Fireworks MX where the main body of the page template was transparent.

By making the bottom-left pixel transparent too we can easily set the transparent colour for a bitmap in .NET.

I keep the top-right of the image white where the corner folds over, that means I can just combine the images by drawing the transparent template directly over the PDF image to achieve the final look.

Pre-requisites

The full version of Adobe Acrobat (the free reader does not expose the COM interfaces) which exposes a COM library of objects to manipulate and access PDF information.

The Adobe Acrobat 5.0 SDK which is a free download from the Adobe Solutions Network website (note: the site requires registration). The latest SDK for Acrobat 6.0 requires paid membership, so we will use the previous SDK version.

To quickly see if you have the full version of Adobe Acrobat installed, use regedit.exe and look under HKEY_CLASSES_ROOT for entry entry called AcroExch.PDDoc.

You'll also need the .NET 1.1 Framework and some PDF files to test the solution.

The code was written in VB.NET using the .NET 1.1 Framework and Visual Studio.NET 2003 on Windows XP, but there is no reason it wouldn't work on Windows NT/2000 or .NET 1.0.

Using the code

The code is quite simple with a try/catch over the main body. It is purposely in one large block so it's easy to see what it happening and to step through and examine with the debugger.

Initially we create an instance of AcroExch.PDDoc using late-binding. The referenced Adobe Acrobat 5.0 Type Library (Acrobat.tlb from C:\Program Files\Adobe\Acrobat 5.0 SDK\InterAppCommunicationSupport\Headers) does not expose a COM class you can create using early-binding. By referencing the type library we can get the Intellisense and strong-typing of the other Acrobat objects.

Pass the filename of the PDF documents to be opened to the PDDoc object, which can then be accessed to get metadata on the document; GetNumPages() and GetInfo() for custom document properties.

' Create the document (Can only create the AcroExch.PDDoc object using
' late-binding)
pdfDoc = CreateObject("AcroExch.PDDoc")

' Open the document
ret = pdfDoc.Open(inputFile)

If ret = False Then
    Throw New FileNotFoundException
End If

' Get the number of pages
pageCount = pdfDoc.GetNumPages()

Set a reference to the first page of the document as pdfPage, which is of type Acrobat.CAcroPDPage. From this we can get a rectangle object of the actual page dimensions. One strange point to notice here is that the Adobe Acrobat SDK documentation seems incorrect, as the PDFRect that is returned from the GetSize() method has IDispatch properties x, y but the PDFRect we need to supply to CopyToClipboard must have left, right, top, bottom.

Finally we render the PDF page to the clipboard at full size. We could have Acrobat scale the image down for us by a percentage, but we can get better visual results using the .NET scaling algorithms of the Bitmap class.

It would have been more efficient to render directly to an off-screen bitmap, and also not have overwritten what ever was previously on the clipboard, but I found the clipboard method the most stable way to get a rendered bitmap of the page using Acrobat.

Although it looks like the pdfPage object has a DrawEx method that can take an H<CODE>DC I couldn't get the method to work in a consistently successful way. Calling DrawEx in the paint event of a Windows Forms application did work but it still wouldn't write to an off-screen bitmap directly. Therefore the clipboard method is used and if the process runs on a batch server it won't cause too much worry.

Note: the Draw method is deprecated, as it only works on Win16 systems where hWnd was unique to Windows and not to each process as on NT.

' Get the first page
pdfPage = pdfDoc.AcquirePage(0)

' Get the size of the page
' This is really strange bug/documentation problem
' The PDFRect you get back from GetSize has properties
' x and y, but the PDFRect you have to supply CopyToClipboard
' has left, right, top, bottom
pdfRectTemp = pdfPage.GetSize

' Create PDFRect to hold dimensions of the page
pdfRect = CreateObject("AcroExch.Rect")

pdfRect.Left = 0
pdfRect.right = pdfRectTemp.x
pdfRect.Top = 0
pdfRect.bottom = pdfRectTemp.y

' Render to clipboard, scaled by 100 percent (ie. original size)
' Even though we want a smaller image, better for us to scale in .NET
' than Acrobat as it would greek out small text
' see http://www.adobe.com/support/techdocs/1dd72.htm

Call pdfPage.CopyToClipboard(pdfRect, 0, 0, 100)

Dim clipboardData As IDataObject = Clipboard.GetDataObject()

Grab the rendered page bitmap from the clipboard and based on the pdfRectTemp object determine if it's a portait or landscape document. Set the correct file to load as the template, and if it is landscape, switch the width and height.

Dim pdfBitmap As Bitmap = clipboardData.GetData(DataFormats.Bitmap)

' Size of generated thumbnail in pixels
Dim thumbnailWidth As Integer = 38
Dim thumbnailHeight As Integer = 52
Dim templateFile As String

' Switch between portrait and landscape
If (pdfRectTemp.x < pdfRectTemp.y) Then
   templateFile = templatePortraitFile
Else
   templateFile = templateLandscapeFile
   ' Swap width and height (little trick not using third temp variable)
   thumbnailWidth = thumbnailWidth Xor thumbnailHeight
   thumbnailHeight = thumbnailWidth Xor thumbnailHeight
   thumbnailWidth = thumbnailWidth Xor thumbnailHeight
End If

Load the template file as as Bitmap and as an Image. We use both because the Bitmap class supports MakeTransparent and the image can easily be passed to the Graphics.DrawImage() method. It is slightly inefficent but speed isn't the primarly objective for this application.

Render the pdfImage using the GetThumbnailImage() method of the .NET Framework Bitmap class, this provides a very smooth scaled version of the image.

Next create a blank bitmap with room for the template border. Set the templateBitmap to use the bottom-left pixel of the image as the transparency colour using calling MakeTransparent(). See an article on Chris Sells website for more on transparencies in .NET.

Using the new blank bitmap, draw the rendered pdf page image to it and then the template with transparency directly over the top. Because it is transparent the main area of the page template will still appear through.

Finally, save the composited image back as a .png or .gif file, although .png does look better.

Collapse

' Load the template graphic
Dim templateBitmap As Bitmap = New Bitmap(templateFile)
Dim templateImage As Image = Image.FromFile(templateFile)

' Render to small image using the bitmap class
Dim pdfImage As Image = pdfBitmap.GetThumbnailImage(thumbnailWidth, _
  thumbnailHeight, _
  Nothing, Nothing)

' Create new blank bitmap (+ 7 for template border)
Dim thumbnailBitmap As Bitmap = New Bitmap(thumbnailWidth + 7, _
  thumbnailHeight + 7, _
  Imaging.PixelFormat.Format32bppArgb)

' To overlayout the template with the image, we need to set the transparency
' http://www.sellsbrothers.com/writing/default.aspx?
' content=dotnetimagerecoloring.htm
templateBitmap.MakeTransparent()

Dim thumbnailGraphics As Graphics = Graphics.FromImage(thumbnailBitmap)

' Draw rendered pdf image to new blank bitmap
thumbnailGraphics.DrawImage(pdfImage, 2, 2, thumbnailWidth, thumbnailHeight)

' Draw template outline over the bitmap (pdf with show through the
' transparent area)
thumbnailGraphics.DrawImage(templateImage, 0, 0)

' Save as .png file
thumbnailBitmap.Save(outputFile, Imaging.ImageFormat.Png)

Write some feedback to the console as we work through each of the files.

Then actively release the reference code to the COM objects as Acrobat it isn't the best suited application to opening and closing multiple PDF documents without falling over. Luckily the code doesn't cause Acrobat to display any UI that might cause the process to hang waiting for user interaction.

Console.WriteLine("Generated thumbnail... {0}", outputFile)

thumbnailGraphics.Dispose()

pdfDoc.Close()
Marshal.ReleaseComObject(pdfPage)
Marshal.ReleaseComObject(pdfRect)
Marshal.ReleaseComObject(pdfDoc)