Geometric Tools for Computer Graphics

Philip J. Schneider, David H. Eberly

Mentioned 6

A collection of proven solutions to fundamental problems, including building primitives, distance calculation, approximation, containment, decomposition, intersection determination, separation, and more. This work covers problems relevant for both 2D and 3D graphics programming.

More on Amazon.com

Mentioned in questions and answers.

CGAL seems to do just about everything I need and a little more for my upcoming project. It can create polygons out of arc line segments and run boolean operations on them. It has spatial sorting packages already that would save me a lot of time regarding a few things and the whole library seems quite standardized and well planned.

There's just the issue with the license being QPL (GPL for the upcoming version 4.0) for most of the packages (except the very basic ones). I've got a meager budget and can likely not gather funds to buy the commercial licenses for those specific packages in CGAL that require it.

My specific needs of such a library would be:

  • Exact precision 2D euclidean space
  • Complex polygons
  • Polygons able to have curved line (arc) segments
  • Boolean operations on those polygons
  • Polygon offsetting
  • Polygon partitioning or effective triangulation
  • Inscribed area and polygon fitting algorithms
  • Possibly some spatial sorting structures with circular range searches

All in all, I'm looking for a well rounded 2D geometry C++ library with exact precision. Preferably with MIT, LGPL at a stretch, or a low cost one-time royalty-free license below $500.

Boost got some basic structures down, but from what I can tell they lack a lot of the higher level functionality. Any libraries that has expanded on this? I would consider doing it myself, but I lack the expertise to do it well and it'd prolong my project by quite a bit.

Just to be clear, I'm not looking for a 2D graphics library, just pure geometry structures.

Take a look at Geometric Tools for Computer Graphics.

  • Refined over a decade
  • Unbelievably good documentation, both in hard bound and extensively in PDF form
  • Boost license

It meets all your requirements:

  • Exact precision 2D euclidean space: Yes
  • Complex polygons : Yes
  • Polygons able to have curved line (arc) segments : Nonsensical. By definition, polygons are composed of line segments. If you are looking for splines and NURBS, the library has them.
  • Boolean operations on those polygons : Yes
  • Polygon offsetting : Unclear what you mean. The library certainly supports translation.
  • Polygon partitioning or effective triangulation: Yes, Delaunay triangulation and Voronoi regions
  • Inscribed area and polygon fitting algorithms :Yes
  • Possibly some spatial sorting structures with circular range searches : Yes, spatial sorting and a whole bushel of intersection functions.

All this comes from the book Geomtric Tools for Computer Graphics by Schneider and Eberly. The book is outstanding, with clear presentation of how the algorithms work and what their limitations are. The authors have made the code available online under the Boost license and include most (all?) of the book online as a PDF to accompany each code module. They maintain an very useful website that is indexed in various ways.

I have no connection to the authors nor any monetary interest. I used their book in my thesis and it was extremely pleased with it as an easy to use reference and a powerful library.

I have a 3D shape in a 3D binary image. Therefore, I have a list of all of the x,y,z points.

If I am to analyze a shape for various identification, such as "sphericity", "spiky"-ness, volume, surface area, etc., what are some of the choices do I have here?

Could you post a sample shape? Do you have a complete set of points on the surface and interior of the shape? Are the points evenly spaced? Is this synthetic data, or perhaps a point cloud from a 3D scan?

A few ideas:

  1. Calculate the 3D convex hull of the points. This will give you the outer "envelope" of the points and is useful for comparison with other measurements. For example, you can compare the surface area of the convex hull to the surface area of the outer surface points.
  2. Find the difference between "on" voxels in the convex hull and "on" voxels in the raw point set. You can then determine how many points are different, whether there is one big clump, etc. If the original shape is a doughnut, the convex hull will be a disk, and the difference will be the shape of the hole.
  3. To calculate spikiness, you can think of comparing the Euclidean distance between two points (the "straight line" distance) and the shortest distance on the outer surface between those two points.
  4. Compare the surface area of the raw data to the surface area after a 3D morphological "close" operation or some other smoothing operation.
  5. To suggest a type of volume calculation, we'd need to know more about the point set.
  6. Consider the Art Gallery Problem to 3D. Are there points on the surface not visible to certain points in the interior? Is the shape convex or star convex?

A good reference for geometric algorithms is Geometric Tools for Computer Graphics by Schneider and Eberly. It's pricey new, but you can probably find a cheap used copy in good condition at addall.com. I suspect you'll find all the answers you want and more in that book. http://www.amazon.com/Geometric-Computer-Graphics-Morgan-Kaufmann/dp/1558605940

One of the authors maintains a site on the same subject: http://www.geometrictools.com/

Another good textbook is Computational Geometry in C by Joseph O'Rourke. http://www.amazon.com/Computational-Geometry-Cambridge-Theoretical-Computer/dp/0521649765/ref=sr_1_1?s=books&ie=UTF8&qid=1328939654&sr=1-1

I've always had an interest in creating my own games, and now at university I have the opportunity to create some 2D and 3D games using Java and C++ for those who are that way inclined.

I've never really programmed a game before, let alone graphics, so I'm completely new to the area. After a quick trip to the library today I came across very little information on starting 2D game development or even graphics programming in Java or C++. I can program in Java at a reasonable level, but I have never touched C++.

  1. Can someone recommend any good books on starting Graphics Programming in Java or C++?
  2. I have no C++ experience, but I've programmed in C and Java and feel reasonably comfortable in both. Should I take the jump and dive into C++ when important marks are at stake? I hear a lot of good things about C++ as far as Games Programming goes so I'm unsure as to what is the best option for me.
  3. I'm looking to write a 2D game in my own time for a bit of fun before I start getting into the heavy work at university. Can anyone recommend some good resources for those interested in writing their own games using OpenGL and Java/C++.
  4. For those who have followed my other questions here I am terrible at Maths and hold very little knowledge of even the foundations. Is this going to be a serious problem for me? If I were to need Math knowledge what do you recommend I brush up on?

I apologise if my questions seem a bit vague, as I'm a complete newbie when it comes to a lot of these topics. Any help you could provide would be much appreciated.

EDIT: I've already checked out the question titled "game programming", but have found it to not really cater for my specific questions.

I have this book: Beginning C++ Through Game Programming. It might seem trivial at first, but it teaches you a-lot as you go through it. There is no GUI based programming in this book, just the console. Which is good to an extent if you want to see how an entire "story" of a game can come together.

You can also check out Gamedev.net, they have a vast amount of resources and articles to get you started. Good luck. :)

Game programming, especially where graphics are concerned, involves a fair amount of math. You'll at least want to have a basic familiarity with vectors and matrices, specifically with regard to representing rotation, translation, and scaling transformations. To that end, I recommend Geometric Tools for Computer Graphics. A course in linear algebra wouldn't hurt, as well, although that's probably already in your curriculum.

As far as game programming in Java, I recommend taking a look at jMonkeyEngine, an open source game engine with all sorts of fun example code to get you started. It was originally based on the engine presented in the book 3D Game Engine Design (same author as Geometric Tools above), which is another good source of information about game programming in 3D. There's also C++ code and papers on various topics in 3D graphics at that book's official site.

Here are a few books that I used when writing OpenGL code in C++:

Fundamentals of Computer Graphics

OpenGL SuperBible

OpenGL Red Book

OpenGL Primer

You might check out the MIT OpenCourse on computer graphics too. It might help supplement your development.

Best of luck!

I am going through a similar process to you at the moment. I found the following site helpful, it has a great tutorial (space invaders in Java):

http://www.cokeandcode.com/node/6

You can get the source code and mess around with it. You will probably benefit from an IDE, if you don't already have a favorite you could try Netbeans (netbeans.org) which is free and I think it's pretty good.

As for books this one is OK (it's java-centric):

http://www.amazon.com/Killer-Game-Programming-Andrew-Davison/dp/0596007302

I personally decided to use Java for games (for now) because I am very comfortable with Java and far less so with C++. But you will find that most people use C++ for commercial games. Actually I started with pygame (python games framework) which is also nice to get started, especially if you know python.

I´m trying to compute the perimeter of a region in binary images. When a region is simply connected, i.e. it has no "holes", everything is quite simple: I just check for every pixel if it belongs to the region and has at least a neighbor which is not belonging to the region... I have a variable that counts the number of pixels satisfying this condition.

In the case of region with holes I use a different way. I start from a pixel in the border and "jump" to a neighbor (increasing a counter) if it is itself a border pixel. The procedure, with some more quirks, ends when I go back to the initial pixels. Something like this:

int iPosCol = iStartCol, int iPosRow = iStartRow;
do 
{
  //check neighbors, pick point on the perimeter
  //condition: value == label, pixel at the border.
  check8Neighbors(iPosCol, iPosRow);
  updatePixPosition(iPosCol, iPosRow);
}
while ( iPosC != iStartC || iPosR != iStartR );

The problem is that this method won´t work if the holes in the region are close to the border (1-pixel distance).

Are there standard ways of computing perimeter of non simply connected regions, or am I approaching the problem in the wrong way?

As JCooper noted, connected component a.k.a. region labeling a.k.a. contour detection is an algorithm to find regions of connected pixels, typically in an image that has been binarized so that all pixels are black or white.

The Wikipedia entry for Connected-component labeling includes pseudocode for a "single pass" algorithm (http://en.wikipedia.org/wiki/Connected-component_labeling).

http://en.wikipedia.org/wiki/Connected-component_labeling

Another single-pass algorithm can be found in the paper "A Component-Labeling Algorithm Using Contour Tracing Technique" by Chang and Chen. This paper also includes a description of an edge-following algorithm you can use to find just the contour, if you'd like. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.3213

That paper describes edge-following well enough, but I'll describe the basic idea here.

Let's say the outer contour of a figure is represented by pixels a through f, and background pixels are represented by "-":

- - - - -
- a b - -
- - - c -
- - - d -
- f e - -
- - - - -

If we're scanning the image from top to bottom, and along each row from left to right, then the first pixel encountered is pixel a. To move from pixel a to pixel b, and then from b to c, we track the direction of each move using 8 directions defined relative to the current pixel, p:

6 7 8
5 p 1
4 3 2

The move from the background "-" to pixel "a" is along direction 1. Although we know where "b" is, the software doesn't, so we check all directions clockwise about "a" to find the next pixel along the contour. We don't need to check direction 5 (left) because we just came from the background pixel to the left of "a." What we do is check directions clockwise 6, 7, 8, 1, 2, etc., looking for the next contour pixel. We find "b" also along direction 1 after finding only background pixels in directions 6, 7, and 8 relative to "a."

If we look at the transition from c to d, we move in direction 3. To find the next contour pixel "e," we check directions 8, 1, 2, 3, 4, and we find contour pixel "e" by moving in direction 4.

The general rule is that if our last move was in direction d, the first direction we check for our next move is direction d - 3. If the last move was in direction 5 (moving left), then we start our next clockwise search at direction 2.

In code we would usually use directions 0 - 7, and clearly you'll make use of the modulo operation or similar math, but I hope the idea is clear. The Chang and Chen paper describes the basic contour-following algorithm reasonably well, and also mentions necessary checks if the algorithm needs to retrace certain pixels.


An edge-following algorithm may be sufficient for your needs, but for a variety of reasons you might want to find connection regions of pixels, too.

For a connected component algorithm, one thing to keep in mind is what you want to consider a "neighbor" of a pixel. You can look at just the "4-neighbors":

-  n  -
n  p  n
-  n  -

where "p" is the center pixel, "n" marks four neighbors, and "-" marks pixels that are not considered neighbors. You can also consider the "8-neighbors," which are simply all pixels surrounding a given pixel:

n  n  n
n  p  n
n  n  n

Typically, 4-neighbors are the better choice when checking connectivity for foreground objects. If you select an 8-neighbor technique, then a checkerboard pattern like the following could be considered a single object:

p - p - p - p - p
- p - p - p - p - 
p - p - p - p - p
- p - p - p - p - 
p - p - p - p - p
- p - p - p - p - 

Let's say you have a blob that looks like the one below, with foreground pixels labeled as "p" and background pixels labeled as "-":

- - - - - - - - - -
- - - - p p p - - -
- - p p p - p p - -
- - - p p - p p - -
- - - - p p p - - -
- p p p p p p - - -
- - - - - - - - - -

If you consider just the pixels of the outer contour, you'll see that it can be a little tricky calculating the perimeter. For the pixels 1, 2, 3, 4, and 5 below, you can calculate the perimeter using the pixels 1 - 5, moving in stepwise fashion from pixel 1 to 2, then 2 to 3, etc. Typically it's better to calculate the perimeter for this segment using only pixels 1, 3, and 5 along the diagonal. For the single row of pixels at bottom, you must be careful that the algorithm does not count those pixels twice.

- - - - - - - - - -
- - - - p p p - - -
- - 1 2 p - p p - -
- - - 3 4 - p p - -
- - - - 5 p p - - -
- p p p p p p - - -
- - - - - - - - - -

For relatively large connected regions without "peninsulas" jutting out that are a single pixel wide, calculating the perimeter is relatively straightforward. For very small objects it's hard to calculate the "true" perimeter in part because we have a limited number of discrete, square pixels representing a real-world object with a contour that is likely smooth and slightly curvy. The image representation of the object is chunky.

If you have an ordered list of the pixels found from an edge tracing algorithm, then you can calculate the perimeter by checking the change in X and the change in Y of two successive pixels in the list of contour pixels. You calculate the perimeter by calculating the sum of pixel-to-pixel distances along contour pixels.

For pixel N and pixel N + 1: if either X is the same or Y is the same then the direction from N to N + 1 is left, right, up, or down, and the distance is 1.

If both X and Y are different for pixels N and N + 1, then the direction moving from one pixel to the next is at a 45-degree angle to the horizontal, and the distance between pixel centers is the square root of 2.

Whatever algorithm you create, consider checking its accuracy against simple figures: a square, a rectangle, a circle, etc. A circle is particular helpful to check perimeter calculation because the contour of a circle (esp. a small circle) in an image will have jagged rather than smooth edges.

- - - - - - - - - -
- - - p p p p - - -
- - p p p p p p - -
- - p p p p p p - -
- - p p p p p p - -
- - - p p p p - - -
- - - - - - - - - -

There are techniques to find shapes and calculate perimeters in grayscale and color images that don't rely on binarization to make the image just black and white, but those techniques are trickier. For many applications the simple, standard technique will work:

  1. Choose a threshold to binarize the image.
  2. Run a connected component / region labeling algorithm on the binarized image
  3. Use the contour pixels of a connected region to calculate perimeter

An image processing textbook used in many universities has the answer to many of your questions about image processing. If you're going to delve into image processing, you should have at least one textbook like this one handy; it'll save you hours of hunting online for answers.

Digital Image Processing (3rd edition) by Gonzalez and Woods

Book website: http://www.imageprocessingplace.com/

You should be able to find an international edition for about $35 online.

If you end up writing a lot of code to perform geometric calculations, another handy reference book is Geometric Tools for Computer Graphics by Schneider and Eberly.

http://www.amazon.com/Geometric-Computer-Graphics-Morgan-Kaufmann/dp/1558605940

It's pricey, but you can find used copies cheap sometimes at multi-site search engines like

http://www.addall.com

Corrections, PDFs of theory, and code from the book can be found here: http://www.geometrictools.com/

How can I identify the circle ? I have a set of points(70) of which 80% percent always fall on the circumference of the circle and the rest 20% are garbage values.

What else do I have ? A 320*240 matrix in which, only these points have value "1", while the others have value "0".

Is there any way I can go about solving this. If not solve, at least reduce the problem somehow ?

I've dealt with a similar problem, detecting circles in 3D geometry. My solution, which works reasonably well, samples three points from the available set of points, using them to calculate candidate circles. Once enough of the candidates agree, the result is determined to be a circle.

The calculation itself takes place in a 2D plane, so points need to be projected beforehand. The actual function is this:

bool GetCircleCenter (const cPoint2 &P1, const cPoint2 &P2, const cPoint2 &P3, cPoint2 &Center)
{   const float X1 = P2.X - P1.X;
    const float X2 = P3.X - P1.X;
    const float Y1 = P2.Y - P1.Y;
    const float Y2 = P3.Y - P1.Y;

    const float Area = (X1 * Y2 - Y1 * X2);
    if (ABS (Area) < 0.0000001)
        return false;

    const float L1 = (P2 - P1).Length ();
    const float L2 = (P3 - P1).Length ();

    Center.X = P1.X + (Y2 * L1 * L1 - Y1 * L2 * L2) / (2 * Area);
    Center.Y = P1.Y + (X1 * L2 * L2 - X2 * L1 * L1) / (2 * Area);
    return true;
}

Source code is from page 800 of this book: http://www.amazon.com/Geometric-Computer-Graphics-Morgan-Kaufmann/dp/1558605940

I am trying to find a formula to determine if a line intersects a polygon. I have tried, but the code below is not working properly.

bool Check_Collision(float x1,float y1, float x2, float y2)
{
        int j=MyPolyVector.size()-1;
        for (int i=0;i<MyPolyVector.size();i++)
        {
                float x3=MyPolyVector[i].X;
                float x4=MyPolyVector[j].X;
                float y3=MyPolyVector[i].Y;
                float y4=MyPolyVector[j].Y;

                float denom= ((y4-y3)*(x2-x1))-((x4-x3)*(y2-y1));
                float ua = (((x4-x3)*(y1-y3))-((y4-y3)*(x1-x3)))/denom;
                float ub = (((x2-x1)*(y1-y3))-((y2-y1)*(x1-x3)))/denom;
                j=i;

                if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) return true;
        }
        return false;
}

I can suggest you to have a look at this book and also search for line line intersection 2D and range checking before your computation.

Also, your code requires division by zero check and further considerations about reciprocal line dimensions and tolerances.