Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm familiar with various methods of triangulation (eg Delaunay), but since I have hundreds of thousands of regularly spaced points that may need to be revisited like this on each physics frame, I'm hoping that there's a more efficient way to do this.

What I need to do is, given a series of points like this:

Series of points spaced like on grid vertices but with an irregular perimeter.

locate the triangles and perimeter. While I haven't show it in this image, it should be possible to form holes in the mesh where there are points missing inside the blue perimeter shown below. Still, I do need to find all the interior perimeters.

The same series of points triangulated, with inner triangle edges highlighted in red, and perimeter edges highlighted in blue.

or, if it would be faster

The points triangulated, but without the interior removed.

My current plan is to use Delaunay triangulation to build the mesh, not merging the triangles at all, and then starting from an arbitrary point, select points which meet criteria for being an edge (being a member of less than 5 triangles?). Is there a more efficient way to do this?

share|improve this question
    
Will the distance between any two adjacent vertices on the perimeter always be at most sqrt(2)*dx? –  Mokosha Dec 13 '13 at 5:33
    
Yes. Another approach I've though about involves arranging the nodes into a 2d array, which would make it easy to locate the perimeters (marching squares, then same on the interior to find the holes), but that would still mean that I would have to perform another O(n) transformation on the data, and then something like an O(n) search inside. –  jzx Dec 13 '13 at 6:18
    
Can you have a completely new set of points on each physics frame, or is it more likely to be an incremental evolution? You may be able to focus on only the regions that change. The process that adds/removes/moves points may be able to leave some hint data about what it did, to help you compute a new triangulation faster. –  DMGregory Dec 13 '13 at 13:30
1  
Incremental - after the beginning points will only be removed. Currently, I'm gathering all the points that will be removed on the next frame and applying the changes all at once, and this would be the next step in the process. So that might help if I set the "perimeter flag" on points next to removed points. –  jzx Dec 13 '13 at 16:37
add comment

2 Answers 2

up vote 2 down vote accepted

I did something like this recently, working from a raster image each frame. My steps were:

  1. Read thresholded values from the image into an array.

  2. Scan the array, looking for a positive value.

  3. When I find one, walk the perimeter separating positive from negative space, accumulating points.

  4. Once the contour is completed, invert every point inside it (so holes become positives that will get their own contours traced). And continue scanning the array.

  5. Decimate the resulting contours, to eliminate points that have little impact on the shape.

  6. Run a monotone triangulation algorithm on the contours (split into monotone polygons and then triangulate)

As it turns out, step 5 is the worst bottleneck in my current version - the monotone triangulation runs insanely fast, even with many points. By not doing the decimation step, you may already get acceptable speed even from this simple approach.

If changes to your point set are localized and incremental, you can avoid the full scan each frame and only re-scan the neighbourhood of changes.

share|improve this answer
add comment

If you store the points using a run-length-encoding e.g.

[num_points][num_empty][pt1][pt2][pt3]...
(algo will now increment num_empty here)
[num_points][num_empty][pt1]...

Then visiting the points (for physics or to compute perimeter or to generate triangles) will be O(n) where n is the number of points, rather than n being the size of the space.

The perimeter can be used by decoding to a bitmap the last three scan-lines, and computing the adjacency on the middle scan-line.

This becomes more expensive to remove points after the RLE structure has been built, but it is doable. You can have a tombstone point type so you can put short runs of only one or more empty points in the middle of a span, and you can in-place write a new zero_num_points span every time you have enough adjacent deleted points so you can easier skip over them.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.